Сравнительный анализ дескрипторов особых точек изображений с внедрением алгоритмов под операционной системой 'Android'

Патин Михаил Владиславович

Сравнительный анализ дескрипторов особых точек изображений с внедрением алгоритмов под операционной системой 'Android'

В данной работе проводится сравнительный анализ методов ORB, BRISK, AKAZE, обнаруживающих особые точки и описывающих их дескрипторы на изображении. Разработан алгоритм, который на основе работы данных методов группирует фотографии по степени сходства. Сравнительный анализ методов проводится на нескольких коллекциях фотографий при разной степени сжатия и на различных значениях параметра сопоставления дескрипторов. Для проведения исследовательской работы была написана программа для мобильных устройств под ОС “Android”.

Общественные науки в целом

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36315f1be77c40d5890b

UUID: bb2c6df3-79ce-49a2-b80d-cee405271c21

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 51

Патин Михаил Владиславович

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 2316899 bytes

Поделиться работой

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА МОДЕЛИРОВАНИЯ ЭКОНОМИЧЕСКИХ СИСТЕМ Патин Михаил Владиславович Выпускная квалификационная работа бакалавра Сравнительный анализ дескрипторов особых точек изображений с внедрением алгоритмов под операционной системой «Android» Направление 010400.62 Прикладная математика и информатика Научный руководитель, кандидат физ.-мат. наук, доцент Ковшов А.М. Санкт-Петербург 2016

Оглавление Введение ..................................................................................................... 3 Цель ............................................................................................................. 5 Глава 1: Алгоритмы обнаружения особых точек и их дескрипторов ..... 6 1.1 ORB – Oriented FAST and Rotated BRIEF ........................................ 7 1.2 BRISK – Binary Robust Invariant Scalable Keypoints ....................... 9 1.3 AKAZE – Accelerated-KAZE .......................................................... 11 Глава 2: Сравнение изображений ............................................................ 13 2.1 Расстояние между дескрипторами ................................................. 13 2.2 Алгоритм RANSAC – Random sample consensus .......................... 14 2.3 Критерий сходства изображений. .................................................. 15 2.4 Группировка по степени сходства ................................................. 16 Глава 3: Программная реализация........................................................... 18 Глава 4: Результаты работы алгоритмов ................................................. 20 4.1 Тестирование программы ............................................................... 20 4.2 Сравнительный анализ. .................................................................. 23 4.1.1 Анализ результатов первой группы ........................................ 24 4.1.2 Анализ результатов второй группы ........................................ 26 4.1.3 Анализ результатов третьей группы ....................................... 27 4.1.4 Контрольное тестирование ...................................................... 28 Выводы ..................................................................................................... 29 Заключение ............................................................................................... 30 Список литературы. ................................................................................. 31 Приложение .............................................................................................. 33 2

Введение Уже несколько десятилетий ученые из разных стран занимаются разработкой алгоритмов, позволяющих научить компьютер видеть так же, как видит сам человек. Если для людей получать необходимую информацию посредством зрительного канала является чем-то простым и само собой разумеющимся, то обучить компьютер подобным вещам является и по сей не выполнимой задачей. Множество IT корпораций работают над её решением, но это требует большого вложения человеческого труда, финансовых затрат и вычислительных мощностей. Но существуют методы, которые позволяют, хоть и при использовании в узконаправленных задачах, получить желаемый результат при меньших затратах. Они основаны не на структуре человеческого аппарата анализа и интерпретации изображений, а непосредственно на особенностях самого изображения. Одни из таких методов основаны на нахождении особых точек и их численного описания, на которые люди даже не обращают внимания. Основываясь только на наборе таких данных цифрового изображения можно с достаточно высокой точностью позволить компьютеру работать с визуальными образами подобно человеку. Вопрос эффективности таких алгоритмов ставится наиболее остро при работе на мобильных устройствах – смартфонах, без которых сложно представить образ современного человека. С помощью мобильных устройств люди делают тысячи фотографий каждый день, нередко они получаются плохого качества и возникает необходимость делать повторные снимки. Со временем это может привести к засорению памяти из-за накопления большого количества похожих фотографий. В данной работе сравниваются несколько современных методов поиска особых точек и расчета их дескрипторов, по результатам их применения в классификаторе, объединяющего в группы снимки по степени сходства. 3

Обзор литературы Разработкой алгоритмов, обнаруживающих особые точки изображений и описывающие определенные их свойства, занимаются достаточно давно. Внедряются новые подходы для решения проблем скорости работы и качества находимых особенностей. Так же проводятся сравнения между методами по различным критериям. В [1] рассматривается алгоритм ORB (Oriented FAST and Rotated BRIEF), представляющий из себя комбинацию из модифицированных алгоритмов нахождения особых точек с помощью FAST [4] и последующим определением их особенностей в виде бинарной строки по модифицированному методу BRIEF [5]. Данный подход дает, по результатам их тестирования, значительный выигрыш в скорости при сопоставимой или лучшей точности, чем SIFT (Scale Invariant Feature Transform) [8] и SURF (Speeded Up Robust Features) [9] соответственно. В работе [2] представлен алгоритм BRISK (Binary Robust Invariant Scalable Keypoints), в котором особые точки обнаруживаются с использованием FAST [4] при линейном изменении масштаба начального изображения. Дескрипторы описываются в бинарном виде по улучшенному алгоритму BRIEF [5]. В сравнительных тестах получена сравнимая с SIFT [8] и SURF [9] точность на различном типе изображений, но при этом скорость работы алгоритма, по их результатам, в разы выше. В [7] представлен алгоритм A-KAZE, в котором поиск особых точек осуществляется при нелинейном масштабировании изображения с использованием схемы FED (Fast Explicit Diffusion) [8]. В качестве бинарного дескриптора применяется M-LDB (Modified-Local Difference Binary). Результаты работы алгоритма, по данным приведенных исследований, превосходят по всем параметрам ORB, BRISK, SIFT и SURF. 4

Цель Целью данной работы является проведение сравнительного анализа методов ORB, BRISK, AKAZE, нахождения особых точек изображения и их дескрипторов. Для достижения поставленной цели предполагается разработать прототип приложения под мобильные устройства под ОС “Android”. Решение данной задачи требует реализации следующих этапов: 1. Рассмотреть методы поиска особых точек и дескрипторов. 2. Применить алгоритмы сопоставления дескрипторов изображений. 3. Разработать критерий сходства изображений по содержанию. 4. Разработать алгоритм распределения по группам коллекции фотографий. 5. Создать программную реализацию для проведения исследований. 6. Провести оценку результатов на различного типа фотографиях и параметрах алгоритма сопоставления дескрипторов. 5

Глава 1: Алгоритмы обнаружения особых точек и их дескрипторов Для обнаружения признакового описания изображения необходимо привязываться к его локальным особенностям - особым точкам. Процесс поиска особых точек осуществляется с помощью детектора. Особая точка, или особенность – это точка изображения, удовлетворяющая ряду свойств: 1. Определенность (distinctness) – особенность должна выделяться на фоне среди соседних точек. 2. Устойчивость (repeatability) – изменение яркости, контрастности и цветовой гаммы не должны влиять на место особой точки на объекте или сцене. 3. Инвариантность (invariance) – особые точки должны обладать устойчивостью к повороту, изменению масштаба изображения и смене ракурса съемки. 4. Стабильность (stability) –зашумленность изображения, не превышающая определенный порог, не должна влиять на работу детектора. 5. Интерпретируемость (interpretability) – особые точки должны быть представлены в формате, пригодном для дальнейшей работы. 6. Количество (quantity) – количество обнаруженных особых точек должно обеспечивать требуемому их количеству для обнаружения объектов. Дескриптор (от лат. descriptor — описывающий) – описание особой точки, определяющее особенности её окрестности, представляет собой числовой или бинарный вектор определенных параметров. Длина вектора и вид параметров определяются применяемым алгоритмом. Дескриптор позволяет выделить особую точку из всего их множества на изображении, это необходимо для составления ключевых пар особенностей, принадлежащих одному объекту, при сравнении разных изображений. 6

В связи с патентными ограничениями алгоритмов SIFT [12] и SURF [13], их не удалось реализовать в приложении для проведения сравнительных тестов. Поэтому далее рассматриваются только одни из свободно распространяемых ORB, BRISK, A-KAZE. Их выбор основан на том, что они имеют бинарный вид дескриптора. Такая структура обеспечивает высокую скорость при их сравнениях, что сделало их достаточно популярными. 1.1 ORB – Oriented FAST and Rotated BRIEF ORB представлен в 2011г [1]. В его основе лежит комбинация таких алгоритмов как детектор FAST (Features from Accelerated Segment Test) [4] и дескриптор BRIEF (Binary Robust Independent Elementary Features) [5] с некоторыми улучшениями. Детектор FAST. Для поиска угловых точек поочерёдно рассматриваются окрестности по 16 пикселей вокруг каждого пикселя p. Точка p считается подозрительной на особую, если существует N пикселей (в данной работе N=9) в её окружности длиной 16 пикселей, если все N ярче 𝐼𝑃 + 𝑡 или темнее 𝐼𝑃 − 𝑡, где 𝐼𝑃 – яркость точки p, t –пороговая величина. При выполнении этого условия далее исследуется значения яркости на окружности под номерами 1, 5, 9, 13 (рис. 1.1). Если для трех пикселей из четырех выполняется условие 𝐼𝑖 < 𝐼𝑃 − 𝑡 или 𝐼𝑖 > 𝐼𝑃 + 𝑡, 𝑖 = 1 … 4, тогда p считается особой точкой. Выбор только 4 пикселей на окружности позволяет быстро отсеять не подходящие точки, но в некоторых случаях возможно определение разных особенностей в одной окружности. В алгоритме ORB максимальное количество особых точек по умолчанию не более 500, если их больше, то к ним применяется детектор углов Харриса [10], для исключения наименее значимых. 7

Рис. 1.1. Рассматриваемая окрестность точки p FAST детектора [1]. Для инвариантности к масштабированию применяется вышеописанный алгоритм на пирамиде Гаусса. Октавами 𝑐𝑖 которой является изначальное изображение 𝑐0 сжатое с линейным шагом. Введение параметра угловой ориентации позволяет добиться устойчивости детектирования при вращении объекта. Он основан на направлениях градиента яркости относительно центра точки, направление с наибольшей интенсивностью назначается ориентацией особой точки 𝜃. Дескриптор направленный BRIEF. Данный дескриптор представляется в виде вектора длиной 256, состоящего из результатов бинарных тестов вокруг особой точки. В окрестности 31 × 31 пиксель сравниваются средние значения яркостей между 𝑥 и 𝑦, где 𝑥, 𝑦 – области 5 × 5 пикселей: 𝜏(𝐼; 𝑥, 𝑦) ≔ { 1 ∶ 𝐼𝑥 <𝐼𝑦 ; 𝐼 – средняя яркость выбранной области. 0 ∶𝐼𝑥 ≥𝐼𝑦 Для достижения инвариантности к вращению область вычисления дескриптора ориентируется по ориентации особой точки 𝜃. Все 𝑛 = 256 наборов 𝑥𝑖 и 𝑦𝑖 формируют матрицу 𝑆 размерностью 2 × 𝑛. Далее 𝑆 с помощью матрицы поворота 𝑅𝜃 ориентируется в соответствии с углом 𝜃: 𝑆𝜃 = 𝑅𝜃 𝑆. А сам вектор дескриптора записывается как: 𝑔𝑛 (𝐼, 𝜃 ) ≔ 𝑓𝑛 (𝐼 )|(𝑥𝑖 , 𝑦𝑖 ) ∈ 𝑆𝜃 , где 𝑓𝑛 (𝐼 ) ≔ ∑1≤𝑖≤𝑛 2𝑖−1𝜏(𝐼; 𝑥𝑖 , 𝑦𝑖 ). 8

1.2 BRISK – Binary Robust Invariant Scalable Keypoints Данный метод представлен в 2011г. Детектирование особых точек осуществляется с помощью FAST (Features from Accelerated Segment Test), а дескриптор BRIEF, но в их работу были внесены некоторые изменения. Поиск особых точек. Для достижения инвариантности к масштабу, предлагается выбирать наилучшую особую точку с максимальным значением интенсивности в пирамиде, которая состоит из 4 октав 𝑐𝑖 и 4 внутренних октав 𝑑𝑖 , 𝑖 = 0. . .3. Октавы формируются как сжатие оригинального изображения с0 в 2𝑖 раза. Внутренние октавы расположены между 𝑐𝑖 и 𝑐𝑖+1 и представлены в виде сжатой с0 в 2 𝑖 2 3 раза. Поиск особых точек в октавах осуществляется детектором FAST. Рис. 1.2. Пример поиска особой точки с максимальным значением S [2]. 9

Дескриптор BRISK. Область вокруг особой точки разбивается на 60 участков 𝑝 (рис. 1.3): 𝒜 = {(𝑝𝑖 , 𝑝𝑗 ) ∈ 𝑅 2 × 𝑅 2|𝑖 < 𝑁 ∧ 𝑗 < 𝑖 ∧ 𝑖, 𝑗 ∈ ℕ} Рис 1.3. Область вычисления дескриптора [2]. Множество 𝒜 разбивается на 2а подмножества: 𝒮 = {(𝑝𝑖 , 𝑝𝑗 ) ∈ 𝒜|‖𝑝𝑗 − 𝑝𝑖 ‖ < 𝛿𝑚𝑎𝑥 } ⊆ 𝒜 ℒ = {(𝑝𝑖 , 𝑝𝑗 ) ∈ 𝒜|‖𝑝𝑗 − 𝑝𝑖 ‖ > 𝛿𝑚𝑖𝑛 } ⊆ 𝒜 где 𝛿𝑚𝑖𝑛 = 13.67𝑡, 𝛿𝑚𝑎𝑥 = 9.75𝑡, 𝑡 − размер особой точки. Вычисляется среднее значение градиента множества ℒ: 𝑔𝑥 1 𝑔 = (𝑔 ) = ∗ 𝑦 |ℒ| ∑ [(𝑝𝑗 − 𝑝𝑖 ) 𝐼(𝑝𝑗 , 𝜎𝑗 ) − 𝐼(𝑝𝑖 , 𝜎𝑖 ) (𝑝𝑖 ,𝑝𝑗 )∈ℒ ‖𝑝𝑗 − 𝑝𝑖 ‖ 2 ] Дескриптор состоит из бинарной строки длиной 512, заполненной результатами проведенных тестов в множестве 𝒮: 1, 𝐼(𝑝𝑗𝛼 , 𝜎𝑗 ) > 𝐼 (𝑝𝑖𝛼 , 𝜎𝑖 ) 𝑏={ ; ∀(𝑝𝑖𝛼 , 𝑝𝑗𝛼 ) ∈ 𝒮, 0, иначе где 𝐼 (𝑝𝑖𝛼 , 𝜎𝑖 ) интенсивность окрестности радиуса 𝜎𝑖 точки 𝑝𝑖 , 𝛼 = 𝑎𝑟𝑐𝑡𝑎𝑛2(𝑔𝑦 , 𝑔𝑥 ) − угол направления градиента 𝑔. 10

1.3 AKAZE – Accelerated-KAZE При разработке данного метода, представленного в 2013 году, старались добиться высокой скорости работы как детектора, так и дескриптора. При этом найденные особые точки и их дескрипторы должны были удовлетворять высоким показателям точности при сравнении изображений. Применение алгоритма FED - Fast Explicit Diffusion [6] на пирамидальной схеме позволяет построить нелинейную многомасштабную пирамиду. Применение нелинейного коэффициента масштабирования позволяет увеличить скорость нахождения нужной особой точки по сравнению с Гауссовой пирамидой: Вычисление данного коэффициента основано на изменении яркости изображения при масштабировании. Детектор. Для каждого октавы 𝐿𝑖 в пирамиде вычисляется определитель Гессиана. 𝐿𝑖𝐻𝑒𝑠𝑠𝑖𝑎𝑛 = 𝜎 2 𝑖,𝑛𝑜𝑟𝑚 (𝐿𝑖𝑥𝑥 𝐿𝑖𝑦𝑦 − 𝐿𝑖𝑥𝑦 𝐿𝑖𝑥𝑦 ), где 𝜎𝑖,𝑛𝑜𝑟𝑚 = 𝜎𝑖 2𝑜 𝑖 нормализированный относительно масштаба коэффициент, для вычисления 𝐿𝑖𝐻𝑒𝑠𝑠𝑖𝑎𝑛 с учетом размера октавы 𝜎𝑖 . Производные второго порядка вычисляются с помощью фильтра Шарра[11] с шагом 𝜎𝑖,𝑛𝑜𝑟𝑚 . Данный фильтр позволяет учитывать ориентацию особых точек. С помощью такого подхода ищем такие точки в октаве, значение фильтра которых выше заданного порога и является наибольшим из окрестности точки 3 × 3 пикселей. Далее, для каждой точки из потенциальных максимумов сравнивается её значение относительно результатов в соседних октавах 𝑖 + 1 и 𝑖 − 1 в окне размером 𝜎𝑖 × 𝜎𝑖 соответственно. В итоге расположение особой точки оценивается с субпиксельной точностью соответствуя квадратичной функции к определителю Гессиана в 3 × 3 соседних пикселей для поиска максимума. 11

Дескриптор M-LDB. Первоначальный дескриптор LDB [9] основывался на тех же принципах что и рассмотренный выше BRIEF, но к сравнениям яркостных показателей областей добавили сравнение значений градиентов яркости по оси 𝑥 и 𝑦, в итоге результат одного теста состоит из трех битов вместо одного. Проведение тестов проводилось в окне размером 20 × 20 пикселей, деленном на 4, 9 и 16 областей. Но LDB имеет недостатки такие как не инвариантность к вращению и масштабированию. И в качестве решения этих проблем в AKAZE используется его улучшенная версия – M-LDB: 1. Окно дескриптора ориентируется по ориентации особой точки. 2. Инвариантность к масштабу получена с помощью выбора размера окна дескриптора в зависимости от размера октавы 𝜎𝑖 в которой найдена его особая точка. В отличии от LDB в M-LDB тесты проводятся не между средним значением всех пикселей в области, а между заданным их количеством в зависимости от размера 𝜎𝑖 . Что позволяет ускорить вычисление дескриптора. Итоговый бинарный дескриптор имеет длину 486 по три составляющих. 12

Глава 2: Сравнение изображений С помощью вышеописанных методов, был получен набор дескрипторов по каждому изображению из коллекции, далее необходимо их сопоставить для поиска схожих. 2.1 Расстояние между дескрипторами Для сравнения пары изображений в основном используют метод сравнения основанный на вычислении расстояний всех возможный пар дескрипторов 𝜌(𝑑𝑖 , 𝑑𝑗 ′). { 𝑑 − дескриптор первого изображения, вектор из признаков 𝛼𝑘 𝑑 ′ − дескриптор второго изображения, вектор из признаков 𝛼′𝑘 Где ∀ 𝑑𝑖 ∈ 𝒟, ∀ 𝑑 ′𝑗 ∈ 𝒟′, 𝑖 = 1 … |𝒟|, 𝑗 = 1 … |𝒟′|, размерность вектора признаков |𝒦| определяется в зависимости от используемого метода описания точки. Для определения расстояний обычно используется евклидова метрика: |𝒦 | 𝜌(𝑑𝑖 , 𝑑𝑗′ ) = ∑|𝛼𝑘 − 𝛼𝑘′ |2 𝑘=0 Однако она применима только для дескрипторов, описываемых количественными переменными. Но рассматриваемые в данной работе методы, представляют описание особой точки в виде бинарной строки. И в таком случае рекомендуется применять расстояние Хемминга, которое вычисляется как количество не равных значений в векторах: |𝒦 | 𝜌(𝑑𝑖 , 𝑑𝑗′ ) = ∑ 𝐼( 𝛼𝑘 ≠ 𝛼 ′ 𝑘 ) 𝑘=0 Ближайший сосед Далее для каждого дескриптора 𝑑𝑖 выбираются два ему ближайших 𝑑𝑗′ и наоборот. Если у выбранного 𝑑 уже есть соответствующие ему два 13

дескриптора, то он пропускается и поиск продолжается. В итоге каждому дескриптору 𝑑𝑖 будут соответствовать не больше двух взаимно ближайших из 𝒟′. Вводится параметр отношения длин 𝜐 = 𝜌𝑖1 𝜌𝑖2 (𝜌𝑖1 < 𝜌𝑖2 ), по которому отсеваются дескрипторы не удовлетворяющие необходимому уровню определенности. Если 𝜐 больше заданного порога 𝜐𝑚𝑎𝑥 , то 𝑑𝑖 далее не рассматривается, иначе для 𝑑𝑖 ставится в соответствие дескриптор 𝑑𝑗 с расстоянием 𝜌𝑖1 . 2.2 Алгоритм RANSAC – Random sample consensus Отфильтровать дескрипторы только по дистанции недостаточно для достижения высокой точности определения схожих объектов на изображениях. Если объект переместился на сцене или снят с другого ракурса, то при применении трансформации «наложения» n точек одного изображения на соответствующие по ближайшему соседу n точек другого, можно выявить особенности, не относящиеся к общему объекту и тем самым уменьшить количество ложно определенных связей. Схема работы алгоритма RANSAC заключается в циклическом повторении поиска матрицы трансформации 𝐻 между случайно выбираемыми четырьмя особыми точками 𝑠𝑖 на одном изображении и соответствующе им четырём точкам на втором: 𝑥𝑖 𝑥′𝑖 𝑠𝑖 [𝑦𝑖 ] ~𝐻 [𝑦′𝑖 ] 1 1 Лучшая матрица трансформации считается той в которой достигнут минимум суммы отклонений всех особых точек изображений при преобразовании 𝐻, за заданное количество циклов (≤ 2000): 14

∑ [(𝑥𝑖 − 𝑖 ℎ11𝑥′𝑖 + ℎ12 𝑦 ′ 𝑖 + ℎ13 ℎ31 𝑥′ 𝑖 + ℎ32 𝑦′ 𝑖 + ℎ33 2 ) + (𝑦𝑖 − ℎ21 𝑥′𝑖 + ℎ22 𝑦 ′ 𝑖 + ℎ23 ℎ31 𝑥′ 𝑖 + ℎ32 𝑦′ + ℎ33 𝑖 )2 ] В итоговое множество 𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠′ включаются только те точки 𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠𝑖 отклонение которых не превосходит заданного порога: ‖𝑑𝑠𝑡𝑃𝑜𝑖𝑛𝑡𝑠𝑖 − 𝐻 ∗ 𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠𝑖 ‖ < 𝑟𝑒𝑝𝑟𝑜𝑗𝑇ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 Где 𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠 – множество всех особых точек на первом изображении, а 𝑑𝑠𝑡𝑃𝑜𝑖𝑛𝑡𝑠 соответствующие им особые точки на втором. 2.3 Критерий сходства изображений. Для того чтобы определить действительно ли на изображениях расположен один и тот же объект был разработан критерий сходства: 1) Рассматривается множество 𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠′, если |𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠 ′ | < 6, то изображения не сравниваются. Иначе выполняются следующие шаги. 2) Вычисляется шаг обхода 𝑠𝑡𝑒𝑝 = |𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠′| 3 3) В цикле 𝑛 = 0 … 2: 1. Выбираются четыре особых точки 𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠′𝑗 , 𝑗 = 𝑠𝑡𝑒𝑝 ∗ 𝑖 + 𝑛, 𝑖 = 0 … 3, в качестве вершин многоугольника 𝑃𝑛1 и соответствующий ему 𝑃𝑛2 из вершин 𝑑𝑠𝑡𝑃𝑜𝑖𝑛𝑡𝑠. Если 𝑗 ≥ |𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠 ′ |, то 𝑗 = |𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠′| − 𝑛 − 1. 2. Вычисляются суммы длин сторон треугольников из которых состоят 𝑃𝑛1 и 𝑃𝑛2 соответственно, по четыре на каждый из многоугольников (рис.2.1). 2 3 𝑡𝑟0…31 = ∑ √ 2 3 √ 0≤𝑐<𝑙 2 + (𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠′𝑐𝑦 − 𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠′𝑙𝑦 ) 0≤𝑐<𝑙 𝑡𝑟0…32 = ∑ (𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠 ′ 𝑐𝑥 − 𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠 ′ 𝑙𝑥 ) + (𝑑𝑠𝑡𝑃𝑜𝑖𝑛𝑡𝑠𝑐𝑥 − 𝑑𝑠𝑡𝑃𝑜𝑖𝑛𝑡𝑠𝑙𝑥 ) + 2 + (𝑑𝑠𝑡𝑃𝑜𝑖𝑛𝑡𝑠𝑐𝑦 − 𝑑𝑠𝑡𝑃𝑜𝑖𝑛𝑡𝑠𝑙𝑦 ) 3. 𝑎𝑣𝑎𝑟𝑔𝑒𝑇𝑟𝐷𝑖𝑣𝑛 = ∑3𝑖=0 𝑡𝑟𝑖1 𝑡𝑟𝑖2 /4. 15

4. 𝑎𝑣𝑒𝑟𝑎𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛𝑛 = ∑3𝑖=0 (𝑎𝑣𝑎𝑟𝑔𝑒𝑇𝑟𝐷𝑖𝑣𝑛 − ∑3𝑖=0 𝑡𝑟𝑖1 𝑡𝑟𝑖2 )/4. 4) Если 𝑎𝑣𝑒𝑟𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 = 𝑚𝑖𝑛𝑛 (𝑎𝑣𝑒𝑟𝑎𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛𝑛 ) < 0.2, то 𝑎𝑙𝑖𝑘𝑒𝑉𝑎𝑙𝑢𝑒 = (1 − 1,5 ∗ 𝑎𝑣𝑒𝑟𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 ) ∗ |𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠′ |, иначе 𝑎𝑙𝑖𝑘𝑒𝑉𝑎𝑙𝑢𝑒 = 0. Экспериментальным путем было выделено оптимальное пороговое значение 𝑎𝑣𝑒𝑟𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 < 0.2, если неравенство выполняется то изображения считаются похожим по содержанию. Рис 2.1. Пример работы алгоритма. Данный подход достаточно точно позволяет определить сходство двух изображений при условии корректного сопоставления дескрипторов. Параметр 𝑎𝑙𝑖𝑘𝑒𝑉𝑎𝑙𝑢𝑒 определяет степень сходства изображений, он учитывает количество связей и их геометрические отклонения 𝑎𝑣𝑒𝑟𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 между изображениями. 2.4 Группировка по степени сходства Для решения задачи группировки, был разработан классификатор, основывающийся на значениях 𝑎𝑣𝑒𝑟𝑎𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 и 𝑎𝑙𝑖𝑘𝑒𝑉𝑎𝑙𝑢𝑒. 1) Рассматривается симметричная матрица 𝑘 × 𝑘, 𝑘 − количество входных изображений. Необходимо вычислить 𝑘 ∗ заполнения. Главная 𝑎𝑙𝑖𝑘𝑒𝑉𝑎𝑙𝑢𝑒 = −1 диагональ 𝑘−1 2 матрицы и 𝑎𝑣𝑒𝑟𝑎𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 = 100. попарных сравнений для её заполняется Каждому значениями изображению 16

присваивается номер от 0 до 𝑘 − 1. Строки матрицы 𝑖 = 0 … 𝑘 − 1, состоят из ячеек 𝑗 = 0…𝑘 − 1 𝑎𝑣𝑒𝑟𝑎𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛, , содержащих информацию о значениях 𝑎𝑙𝑖𝑘𝑒𝑉𝑎𝑙𝑢𝑒 и номере изображения 𝑗, с которым проводилось сравнение изображения 𝑖. 2) Далее каждая строка сортируется по убыванию 𝑎𝑙𝑖𝑘𝑒𝑉𝑎𝑙𝑢𝑒. Рассмотрим алгоритм группировки: В цикле 𝑖 = 0 … 𝑘 − 1, построчно: 1) Если изображение 𝑖 не имеет группы, то выбирается первая ячейка 𝑖1 . 2) Если у изображения с номером 𝑖1 в первой ячейке стоит номер 𝑖: 1. Если 𝑎𝑣𝑒𝑟𝑎𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 < 0.2, то 𝑖 и 𝑖1 формируют одну группу. 3) Иначе если у 𝑖1 в первой ячейке номер 𝑗, то сравниваются 𝑖 и 𝑗: 1. Если между 𝑖 и 𝑗 𝑎𝑣𝑒𝑟𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 < 0.2: а) Если 𝑖1 и 𝑗 не имеют группы, то 𝑖, 𝑖1 и 𝑗 формируют одну группу. б) Иначе 𝑖 назначается в группу к 𝑖1 . 4) Иначе если 𝑎𝑣𝑒𝑟𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 > 0.2, то 𝑖 выбывает из рассмотрения и считается что группа не найдена. 5) Рассматривается следующее значение 𝑖. Пример работы алгоритма рассмотрен в приложении 1. 17

Глава 3: Программная реализация Для проведения исследований написано приложение, для мобильных устройств под ОС “Android”, с использованием языка Java. Рассмотренные алгоритмы поиска особых точек, вычисление дескрипторов и их сопоставление на изображениях реализованы с помощью библиотеки OpenCV 3.1.0 [14]. Реализована возможность сохранения результатов работы методов ORB, BRISK, AKAZE для каждого изображения в файл в формате JSON [15]. Для разработки использовалась интегрированная среда Android Studio 2.1, основанная на программном обеспечении IntelliJ IDEA от компании JetBrains. Необходимая минимальная версия ОС на смартфоне для установки приложения − Android 4.4 KITKAT. Тестирование работы приложения проводилось на ноутбуке под ОС Windows 10 с процессором Intel(R) Core(TM) i5-6300HQ 2.30 ГГц с использованием эмулятора Android - Genymotion (Fast And Easy Android Emulator) версии 2.6.0 для некоммерческого использования, и смартфоне Samsung Galaxy S4 mini, на чипсете Qualcomm Snapdragon 400 с процессором Krait 1.7 ГГц (28 нм, ARMv7), работающем под управлением ОС Android 4.4.2. Возможности программы:  Создание снимка с помощью стороннего приложения фотокамеры.  Сравнение двух изображений.  Поиск наиболее схожего изображения из директории к выбранному изображению.  Группировка коллекции изображений по степени сходства из выбранной директории. Настройки программы включают:  Выбор одного из методов ORB, BRISK, AKAZE.  Сжатие входных изображений - 300, 450 или 600 пикселей на большую сторону. 18

 Величина порогового значения 𝜐𝑚𝑎𝑥 .  Величина порогового значения 𝑟𝑒𝑝𝑟𝑜𝑗𝑇ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑. Вывод результатов сравнения и поиска схожего представлен в виде двух изображений, расположенных рядом и с отображенными, различного цвета, связями, связывающими найденные соответствующие особые точки. В текстовом поле указывается затраченное время, степень сходства, количество связей. Вывод найденных групп представлен в виде сетки с максимальной шириной в 3 изображения, группы разделены текстовым полем с указанием номера группы. По завершению группировки отображается общее затраченное время. С интерфейсом программы можно ознакомиться в приложении 2. 19

Глава 4: Результаты работы алгоритмов 4.1 Тестирование программы Приведем пример работы поиска связей и их фильтрации в приложении. Время замерялось как среднее между тремя запусками. В тестировании применялся метод ORB. Входное изображение масштабируется до 300 пикселей на большую сторону. На рис. 4.1 изображены найденные методом ближайшего соседа связи, с порогом фильтрации 𝜐𝑚𝑎𝑥 . При уменьшении порога остаются наиболее значимые связи. (а) (б) (в) (г) Рис. 4.1 сопоставление дескрипторов по методу ближайшего соседа: а) Без фильтрации по 𝜐𝑚𝑎𝑥 , |𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠′| = 477. б) 𝜐𝑚𝑎𝑥 = 0.9, |𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠′| = 107. в) 𝜐𝑚𝑎𝑥 = 0.85, |𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠′| = 50. г) 𝜐𝑚𝑎𝑥 = 0.8, |𝑠𝑟𝑐𝑃𝑜𝑖𝑛𝑡𝑠′| = 22. 20

На рис. 4.2 показан результат применения алгоритма RANSAC, с различным порогом 𝑟𝑒𝑝𝑟𝑜𝑗𝑇ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑. В дальнейшей работе 𝑟𝑒𝑝𝑟𝑜𝑗𝑇ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 = 20, такое значение обеспечивает необходимый уровень фильтрации связей. (а) (б) (в) (г) Рис. 4.2 работа фильтра трансформации при 𝜐𝑚𝑎𝑥 = 0.9: а) 𝑟𝑒𝑝𝑟𝑜𝑗𝑇ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 = 5, связей = 26. б) 𝑟𝑒𝑝𝑟𝑜𝑗𝑇ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 = 10, связей = 39. в) 𝑟𝑒𝑝𝑟𝑜𝑗𝑇ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 = 20, связей = 53. г) 𝑟𝑒𝑝𝑟𝑜𝑗𝑇ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 = 𝑖𝑛𝑓, связей = 107. На рис. 4.3 показан результат работы алгоритма сравнения изображений. По результатам тестов данный подход дает верный результат с высокой точностью при вращении, изменении масштаба объекта на изображении и перспективных искажениях. 21

(a) (б) (в) (г) Рис. 4.3 Пример работы алгоритма сравнений изображений 𝜐𝑚𝑎𝑥 = 0.85: а) Связей=63, 𝑎𝑣𝑒𝑟𝑎𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 = 0.19, 𝑎𝑙𝑖𝑘𝑒𝑉𝑎𝑙𝑢𝑒 = 50.6. б) Связей = 44, 𝑎𝑣𝑒𝑟𝑎𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 = 0.1, 𝑎𝑙𝑖𝑘𝑒𝑉𝑎𝑙𝑢𝑒 = 39.6. в) Связей = 29, 𝑎𝑣𝑒𝑟𝑎𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 = 0.16, 𝑎𝑙𝑖𝑘𝑒𝑉𝑎𝑙𝑢𝑒 = 24.2. г) Связей = 59, 𝑎𝑣𝑒𝑟𝑎𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 = 0.23, 𝑎𝑙𝑖𝑘𝑒𝑉𝑎𝑙𝑢𝑒 = 0. На рис. 4.4 изображены найденные группы, определенные классификатором после обработки коллекции фотографий. Количество групп, затраченное время и количество ложных совпадений может варьироваться в зависимости от заданного 𝜐𝑚𝑎𝑥 и применяемого метода поиска особых точек и их дескрипторов. Рис. 4.4 Примеры работы классификатора. 22

4.2 Сравнительный анализ. На данном этапе будет проведено сравнение рассматриваемых методов ORB, BRISK, Параметры AKAZE основываясь на результатах классификатора. 𝜐𝑚𝑎𝑥 = {0.7, 0.75, 0.8, 0.85, 0.9}, 𝑟𝑒𝑝𝑟𝑜𝑗𝑇ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 = 20, размер входных изображений рассматривается в двух вариантах – сжатие до 300 и 600 пикселей на большую сторону. Входные данные разделены на следующие группы: 1. 100 фотографий с большим количеством деталей:  Высокого качества.  С наличием цветного Гауссова шума:  Подверженных Гауссову размытию. 2. 30 фотографий текстур. 3. 30 фотографий лиц людей. Примеры фотографий представлены в приложении 3. Пояснение к таблицам:  “𝐾𝑃 мс.” – общее затраченное время на поиск особых точек в миллисекундах.  “кол-во 𝐾𝑃”– общее количество найденных особых точек на входном множестве изображений.  “𝐷 мс.” – общее затраченное время на расчет дескрипторов в миллисекундах.  “Затраты”− "𝐾𝑃 мс."+"𝐷 мс." “кол−во 𝐾𝑃” среднее затраченное время на поиск одной особой точки и расчет ее дескриптора.  “Время”– общее затраченное время на работу программы в секундах, без учета поиска особых точек, расчета дескрипторов и чтения из директории.  “Групп” – количество определенных групп.  “Ложные группы”− группы, в которых все фотографии различны.  “Ошибки в группах”− если есть как минимум 2е схожих фотографии в 23

группе, то каждая не схожая с этими двумя считается ошибкой.  “Фотографий без группы” − фотографии, которые не были определены в какую-либо группу.  “Кол-во связей”– суммарное число связей, по которым были определены группы, связи фотографий без групп не учитываются. 4.1.1 Анализ результатов первой группы Изображения имеют большое количество деталей и почти все имеют четко выраженный объект на переднем плане, количество групп − 42: 1. 100 фотографий высокого качества. Результаты тестов приведены в таблице 2. 300 600 кол-во KP мс. KP ORB 43944 1370 BRISK 102380 46296 AKAZE 23286 5240 метод кол-во KP мс. KP 17159 0,4217 ORB 49444 2538 44275 0,8847 BRISK 271132 55831 5372 0,4557 AKAZE 89031 20623 D мс. затраты метод D мс. затраты 20402 0,464 46917 0,379 19775 0,4538 Таблица 1. Влияние размера изображений на работу методов. Наибольшее количество особых точек найдено с помощью метода BRISK. Метод ORB оказался не сильно чувствительным к изменению размера изображений в выбранных пределах. Наименьшее время на вычисление дескриптора у метода AKAZE. метод ORB ORB BRISK BRISK AKAZE AKAZE 𝑣𝑚𝑎𝑥 сжатие 0,8 0,75 0,8 0,75 0,8 0,9 300 600 300 600 300 600 время ложных ошибок в фотографий кол-во групп сек. групп группах без группы связей 35 39 3 1 12 4002 35 38 1 0 15 4024 115 42 0 0 2 6695 550 43 0 0 0 13862 26 38 0 1 14 3315 262 41 0 0 5 14631 Таблица 2. Лучшие результаты работы программы. Фотографии высокого качества. В данном тесте применение метода BRISK показало лучший результат. Метод ORB, хоть и дает преимущество во времени, но достаточно много 24

фотографий не определилось в группы. Хорошие результаты с AKAZE, но при меньшем сжатии изображения. 2. 100 фотографий с шумом. Результаты тестов приведены в таблице 4. noise 300 кол-во метод KP мс. KP ORB 43619 1535 BRISK 191953 47667 AKAZE 20394 8468 noise 600 кол-во D мс. затраты метод KP мс. KP 15844 0,3984 ORB 49439 4359 44673 0,4811 BRISK 670454 59870 8110 0,8129 AKAZE 78257 22985 D мс. затраты 18993 0,4723 51488 0,1661 20440 0,5549 Таблица 3. Влияние размера изображений на работу методов. Влияние наличия шума на изображении привело к тому, что метод BRISK определил большое количество особых точек. При этом ORB и AKAZE незначительно изменили этот показатель. метод ORB ORB BRISK BRISK AKAZE AKAZE 𝑣𝑚𝑎𝑥 сжатие 0,8 0,9 0,85 0,8 0,8 0,85 300 600 300 600 300 600 время ложных ошибок в фотографий кол-во групп сек. групп группах без группы связей 34 35 2 2 19 2073 176 38 0 3 12 4655 430 41 0 1 6 4250 3264 42 0 1 2 6044 23 34 3 6 20 1996 219 40 0 1 5 6165 Таблица 4. Лучшие результаты работы программы. Фотографии с шумом. В данном случае лидером является метод AKAZE. Наличие большого количества особых точек у BRISK привело к многократному возрастанию времени, затраченному на фильтрацию ложных связей дескрипторов. ORB снова дает выигрыш во времени, но при меньших результатах. 25

3. 100 фотографий с размытием: Результаты тестов приведены в таблице 6. blur 300 кол-во метод KP мс. KP ORB 30503 917 BRISK 10152 41005 AKAZE 12461 9924 blur 600 кол-во KP мс. KP 12521 0,4405 ORB 21225 1481 39827 7,9622 BRISK 8874 44933 8693 1,494 AKAZE 24655 25382 D мс. затраты метод D мс. затраты 9062 0,4967 41727 9,7656 22549 1,9441 Таблица 5. Влияние размера изображений на работу методов. При добавлении размытия на изображение у методов BRISK и AKAZE значительно возросли затраты на вычисления, в отличии от ORB. Количество особых точек у BRISK резко уменьшилось. время ложных ошибок в фотографий кол-во метод 𝑣𝑚𝑎𝑥 сжатие групп сек. групп группах без группы связей ORB 0,75 300 21 34 0 0 26 2246 ORB 0,85 600 32 32 4 4 23 2734 BRISK 0,75 300 6 22 1 0 51 994 BRISK 0,8 600 6 30 4 1 34 1272 AKAZE 0,85 300 17 33 4 6 21 1922 AKAZE 0,8 600 21 38 0 0 14 2936 Таблица 6. Лучшие результаты работы программы. Размытые фотографии. В работе с размытыми изображениями наилучшей результат при применении AKAZE, худший при BRISK. ORB показывает средние результаты группировки при худшем времени. 4.1.2 Анализ результатов второй группы 30 фотографий с изображением текстур, количество групп – 13. texture 300 texture 600 кол-во кол-во метод KP мс. D мс. затраты метод KP мс. D мс. затраты KP KP ORB 7465 204 2875 0,4125 ORB 8728 732 3635 0,5003 BRISK 33360 13285 12573 0,7751 BRISK 108285 16570 13986 0,2822 AKAZE 3322 1425 1317 0,8254 AKAZE 15675 7320 7215 0,9273 Таблица 7. Влияние размера изображении на работу методов. Хоть BRISK и обнаружил большое количество особых точек, но 26

AKAZE, при сопоставимой итоговой точности, оказался значительно быстрее. метод ORB ORB BRISK BRISK AKAZE AKAZE 𝑣𝑚𝑎𝑥 сжатие 0,8 0,8 0,8 0,7 0,7 0,9 300 600 300 600 300 600 время ложных ошибок в фотографий кол-во групп сек. групп группах без группы связей 1 8 1 1 12 792 1 8 1 0 12 1309 9 7 0 0 14 1840 72 7 0 0 13 5125 <1 5 0 0 19 359 6 7 0 0 13 3272 Таблица 8. Лучшие результаты работы программы. Фотографии текстур. Количество фотографий без групп достаточно велико для всех применяемых алгоритмов. Это связано с особенностями дескрипторов, так как если изображения не имеют четко выраженных уникальных особенностей, то при сравнении дескрипторов, образуются связи между равными по описанию, но не соответствующими по местоположению, особыми точками, в итоге, это приводит к увеличению показателя 𝑎𝑣𝑒𝑟𝑎𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛. 4.1.3 Анализ результатов третьей группы Фотографии лиц людей, количество групп – 11. face 300 face 600 кол-во кол-во метод KP мс. D мс. затраты метод KP мс. KP KP ORB 12344 286 4642 0,3992 ORB 14490 589 BRISK 15064 17326 17959 2,3423 BRISK 34156 15003 AKAZE 4997 1867 1531 0,68 AKAZE 17770 8105 D мс. затраты 5580 0,4257 12799 0,814 7052 0,853 Таблица 9. Влияние размера изображении на работу методов. метод ORB ORB BRISK BRISK AKAZE AKAZE 𝑣𝑚𝑎𝑥 сжатие 0,9 0,8 0,9 0,8 0,8 0,9 300 600 300 600 300 600 время ложных ошибок в фотографий кол-во групп сек. групп группах без группы связей 6 12 4 1 5 934 3 10 2 3 7 317 12 9 4 1 10 826 13 9 4 1 9 517 1 9 4 0 12 412 18 11 3 2 4 946 Таблица 10. Лучшие результаты работы программы. Фотографии лиц. 27

Так же, как и с текстурными изображениями, рассматриваемые методы не предназначены для сопоставления лиц людей, в частности для этих целей применяются алгоритмы основывающиеся на пропорциях лица. С подробными результатами тестов можно ознакомиться в приложении 4. 4.1.4 Контрольное тестирование По совокупности результатов проведенных тестов лучшая точность работы классификатора достигнута при применении метода AKAZE и сжатии изображений до 600 пикселей на большую сторону. Далее найдем среднее значение 𝑣𝑚𝑎𝑥 для AKAZE и проведем контрольные тестирования на 150 фотографиях, с 60 группами, без наличия “дефектных” фотографий и с набором 20 размытых и 20 с шумом. метод AKAZE AKAZE AKAZE AKAZE AKAZE AKAZE AKAZE 𝑣𝑚𝑎𝑥 сжатие 0,9 0,85 0,8 0,9 0,9 0,87 0,87 600 600 600 600 600 600 600 время ложных ошибок в фотографий кол-во групп тест сек. групп группах без группы связей 262 41 0 0 5 14631 hight 219 40 0 1 5 6165 noise 21 38 0 0 14 2936 blur 6 7 0 0 13 3272 texture 18 11 3 2 4 946 face 521 58 0 2 8 22720 150 451 57 0 4 12 16016 110х20х20 Таблица 11. Контрольное тестирование метода AKAZE. Оптимальные параметры программы:  Метод AKAZE.  𝑣𝑚𝑎𝑥 = 0,87.  Сжатие изображений до 600 пикселей на большую сторону. Пусть ошибки в группах считаются с весом 2.  Точность на первом контрольном множестве “150”: (1 − 2∗2+8 150 ) ∗ 100% = 90.66%;  Точность на втором контрольном множестве “110x20x20”: (1 − 2∗4+12 150 ) ∗ 100% = 86.66%; 28

Выводы Метод ORB имеет лучшую скорость в вычислении особых точек и расчета их дескрипторов, что позволяет использовать его в задачах, где необходима обработка изображений в реальном времени. Одной из таких задач является слежение за движущимся объектом. Но высокая скорость работы сказывается на точности сопоставления дескрипторов не в лучшую сторону. Наличие цифрового шума или размытие изображений еще больше ухудшает результат их сравнения. BRISK отличается от остальных методов тем, что он определяет наибольшее количество особых точек, но, к сожалению, в них попадает и цифровой шум, при этом на фильтрацию образовавшихся ложных связей затрачивается значительное количество времени, хотя итоговая точность достаточно высока. При этом на размытых изображениях было определено малое количество особенностей, что в результате привело к неудовлетворительным показателям работы классификатора, ввиду нехватки данных. Метод AKAZE проявил себя с лучшей стороны, хоть он и не обладает такой же скоростью как ORB и не имеет такого количества особых точек как BRISK. Но при этом, из-за особенностей его структуры, таких как поиск особых точек на нелинейной многомасштабной пирамиде и описание дескрипторов по трем параметрам, вместо одного, как у ORB и BRISK, получаем высокую точность при сопоставлении изображений и дальнейшего их распределения по группам. 29

Заключение В данной работе был проведен сравнительный анализ методов поиска особых точек и их дескрипторов. Для достижения поставленной задачи была разработана программа для мобильных устройств под ОС “Android”. Данная программа включает в себя: 1. Реализацию методов ORB, BRISK, AKAZE. 2. Сопоставление дескрипторов изображений. 3. Фильтрация полученных связей дескрипторов. 4. Сравнение изображений, по разработанному критерию сходства. 5. Распределение по группам схожих изображений, на основе разработанного алгоритма классификации. Были проведены сравнительные тесты работы алгоритмов: 1. При различных параметрах алгоритма сопоставления дескрипторов. 2. На двух степенях сжатия изображений. 3. На трех различных группах фотографий. В результате выделен наилучший метод поиска особых точек и расчета их дескрипторов, определены оптимальное пороговое значение алгоритма сопоставления и необходимый уровень сжатия исходных изображений. 30

Список литературы. 1. Ethan Rublee, Vincent Rabaud, Kurt Konolige, Gary Bradski: "ORB: an efﬁcient alternative to SIFT or SURF", Computer Vision (ICCV), IEEE International Conference on. IEEE, pp. 2564 – 2571, 2011. 2. Stefan Leutenegger, Margarita Chli, Roland Siegwart: “BRISK: Binary Robust Invariant Scalable Keypoints”. Computer Vision (ICCV), pp. 2548 – 2555, 2011. 3. Pablo F. Alcantarilla, Jesús Nuevo, Adrien Bartoli: “Fast Explicit Diffusion for Accelerated Features in Nonlinear Scale Spaces”. In British Machine Vision Conference (BMVC), 2013. 4. Rosten, Edward, Tom Drummond: "Machine learning for high-speed corner detection”, 9th European Conference on Computer Vision (ECCV), pp. 430 – 443, 2006. 5. Michael Calonder, Vincent Lepetit, Christoph Strecha, Pascal Fua, “BRIEF: Binary Robust Independent Elementary Features”, 11th European Conference on Computer Vision (ECCV), pp. 778 – 792, 2010. 6. S. Grewenig, J. Weickert, C. Schroers, A. Bruhn: “Cyclic Schemes for PDEBased Image Analysis”, In International Journal of Computer Vision, 2013. 7. X. Yang, K. T. Cheng: “LDB: An ultra-fast feature for scalable augmented reality”. In IEEE and ACM Intl. Sym. on Mixed and Augmented Reality (ISMAR), pp. 49 – 57, 2012. 8. Lowe, David G.: “Object recognition from local scale-invariant features”. Proceedings of the International Conference on Computer Vision, pp. 1150 – 1157, 1999. 9. Herbert Bay, Tinne Tuytelaars, Luc Van Gool, "SURF: Speeded Up Robust Features”. Proceedings of the ninth European Conference on Computer Vision, pp. 404 – 417, 2006. 10. Harris, C., Stephens, M.: “A Combined Corner and Edge Detector”. Proceedings of the 4th Alvey Vision Conference, pp. 147 – 151, 1988. 31

11. J. Weickert, H. Scharr.: “A scheme for coherence-enhancing diffusion filtering with optimized rotation invariance”, Journal of Visual Communication and Image Representation, pp. 103–118, 2002. 12. Patent SIFT: https://www.google.com/patents/US6711293 13. Patent SURF: http://www.google.com/patents/US20090238460 14. OpenCV: http://opencv.org 15. JSON, A Java serialization/deserialization library: https://github.com/google/gson 32

Приложение Приложение 1. Пример работы классификатора Пусть на вход подано 6 изображений.  imageN – номер изображения, с которым проводилось сравнение изображения 𝑖.  avD – 𝑎𝑣𝑒𝑟𝑎𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛.  alV – 𝑎𝑙𝑖𝑘𝑒𝑉𝑎𝑙𝑢𝑒, степень сходства изображения. Для заполнения симметричной матрицы классификатора необходимо произвести 15 сравнений, сравнение фотографии с собой не производится (главная диагональ матрицы). i\j 0 1 2 3 4 5 0 imageN= 0 avD= 100 alV=-1 imageN= 0 avD= 0.22 alV=0 imageN= 0 avD= 0.25 alV=0 imageN= 0 avD= 0.17 alV= 34,27 imageN= 0 avD= 0.81 alV=0 imageN= 0 avD= 0.75 alV=0 1 imageN= 1 avD= 0.22 alV=0 imageN= 1 avD= 100 alV=-1 imageN= 1 avD= 0.34 alV=0 imageN= 1 avD= 0.42 alV=0 imageN= 1 avD= 0.06 alV=30.94 imageN= 1 avD= 0.13 alV= 58,76 2 imageN= 2 avD= 0.25 alV=0 imageN= 2 avD= 0.34 alV=0 imageN= 3 avD= 100 alV=-1 imageN= 2 avD= 0.18 alV=8.76 imageN= 2 avD= 0.53 alV=0 imageN=2 avD=0.68 alV=0 3 imageN= 3 avD= 0.17 alV= 34,27 imageN= 3 avD= 0.42 alV=0 imageN= 3 avD= 0.18 alV=8.76 imageN= 3 avD= 100 alV=-1 imageN= 3 avD= 0.63 alV=0 imageN=3 avD=0.88 alV=0 4 imageN= 4 avD= 0.81 alV=0 imageN= 4 avD= 0.06 alV=30.94 imageN= 4 avD= 0.53 alV=0 imageN= 4 avD= 0.63 alV=0 imageN= 4 avD= 100 alV=-1 imageN=4 avD=0.19 alV=7.15 5 imageN= 5 avD= 0.75 alV=0 imageN= 5 avD= 0.13 alV= 58,76 imageN=5 avD=0.68 alV=0 imageN=5 avD=0.88 alV=0 imageN=5 avD=0.19 alV=7.15 imageN=5 avD=100 alV=-1 Таблица 1. Матрица результатов попарных сравнений изображений. 33

Далее каждая строка сортируется по убыванию 𝑎𝑙𝑖𝑘𝑒𝑉𝑎𝑙𝑢𝑒: 0 1 2 3 4 5 imageN= 3 avD= 0.17 alV= 34,27 imageN= 5 avD= 0.13 alV= 58,76 imageN= 3 avD= 0.18 alV=8.76 imageN= 0 avD= 0.17 alV= 34,27 imageN= 1 avD= 0.06 alV=30.94 imageN= 1 avD= 0.13 alV= 58,76 imageN= 1 avD= 0.22 alV=0 imageN= 4 avD= 0.06 alV=30.94 imageN= 0 avD= 0.25 alV=0 imageN= 2 avD= 0.18 alV=8.76 imageN=5 avD=0.19 alV=7.15 imageN=4 avD=0.19 alV=7.15 imageN= 2 avD= 0.25 alV=0 imageN= 0 avD= 0.22 alV=0 imageN= 1 avD= 0.34 alV=0 imageN= 1 avD= 0.42 alV=0 imageN= 0 avD= 0.81 alV=0 imageN= 0 avD= 0.75 alV=0 imageN= 4 avD= 0.81 alV=0 imageN= 2 avD= 0.34 alV=0 imageN= 4 avD= 0.53 alV=0 imageN= 4 avD= 0.63 alV=0 imageN= 2 avD= 0.53 alV=0 imageN=2 avD=0.68 alV=0 imageN= 5 avD= 0.75 alV=0 imageN= 3 avD= 0.42 alV=0 imageN=5 avD=0.68 alV=0 imageN=5 avD=0.88 alV=0 imageN= 3 avD= 0.63 alV=0 imageN=3 avD=0.88 alV=0 imageN= 0 avD= 100 alV=-1 imageN= 1 avD= 100 alV=-1 imageN= 2 avD= 100 alV=-1 imageN= 3 avD= 100 alV=-1 imageN= 4 avD= 100 alV=-1 imageN=5 avD=100 alV=-1 Таблица 2. Сортировка по значению 𝑎𝑙𝑖𝑘𝑒𝑉𝑎𝑙𝑢𝑒. Сгруппируем изображения: 0. Для изображения с номером 𝑖 = 0 в первой ячейке 𝑖1 = 3, у 𝑖 = 3 − 𝑖1 = 0 => номера 0 и 3 формируют группу 1. 1. Для 𝑖 = 1 − 𝑖1 = 5, а для 𝑖 = 5 − 𝑖1 = 1 => номера 1 и 5 формируют группу 2. 2. Для 𝑖 = 2 − 𝑖1 = 3, но у 𝑖 = 3 − 𝑖1 = 0, рассмотрим значение 𝑎𝑣𝑒𝑟𝑎𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 между 2 и 0: avD > 0.2 => для изображения 2 группы нет. 3. 𝑖 = 3 не рассматривается, т.к. группа уже есть. 4. Для 𝑖 = 4 − 𝑖1 = 1, но у 𝑖 = 1 − 𝑖1 = 5, рассмотрим значение 𝑎𝑣𝑒𝑟𝑎𝑔𝑒𝐷𝑒𝑣𝑖𝑎𝑡𝑖𝑜𝑛 между 4 и 5: avD < 0.2 => изображение 4 добавляется в группу 2. 5. 𝑖 = 5 не рассматривается, т.к. группа уже есть. 34

Приложение 2. Интерфейс программы Интерфейс программы на смартфоне Samsung Galaxy S4 mini. 35

Приложение 2. Примеры изображений Группа 1: Фотографии с большим количеством ярко выраженных деталей. Цифровой шум и размытие: Справа пример добавления цифрового шума. Слева пример размытия фотографии. 36

Группа 2: Фотографии текстурного содержания. Группа 3: Фотографии лиц. 37

Приложение 3. Подробные результаты тестов 1. Первая группа. Тесты изображений высокого качества. 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 hieght ORB 300 время ложных ошибок в фотографий кол-во групп сек. групп группах без группы связей 30 30 0 0 34 2256 31 34 1 0 24 2945 35 39 3 1 12 4002 45 35 2 12 9 5147 85 33 2 4 23 6846 hieght BRISK 300 время ложных ошибок в фотографий кол-во групп сек. групп группах без группы связей 102 38 0 0 14 3940 103 41 0 0 5 5150 115 42 0 0 2 6695 174 43 0 1 2 8501 257 39 0 1 8 11082 hieght AKAZE 300 время ложных ошибок в фотографий кол-во групп сек. групп группах без группы связей 17 36 4 0 19 2301 20 36 2 2 16 2704 26 38 0 1 14 3315 48 36 2 4 17 3898 94 38 2 2 13 4798 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 hieght ORB 600 время ложны ошибок в фотографий кол-во групп сек. х групп группах без группы связей 34 33 1 0 27 3264 35 38 1 0 15 4024 40 38 1 2 13 5011 66 38 1 3 10 6159 158 38 1 2 11 7656 hieght BRISK 600 время ложны ошибок в фотографий групп сек. х групп группах без группы 524 40 0 0 9 550 43 0 0 0 599 43 1 0 1 670 41 0 0 3 696 42 0 1 3 кол-во связей 11143 13862 16989 21028 25480 hieght AKAZE 600 время ложны ошибок в фотографий групп сек. х групп группах без группы 98 38 1 2 8 120 39 0 0 11 171 41 1 1 4 231 39 0 2 5 262 41 0 0 5 кол-во связей 7549 8757 10300 12261 14631 Тесты изображений с цифровым шумом. 𝑣𝑚𝑎𝑥 время сек. 0,7 36 0,75 37 0,8 42 0,85 71 0,9 176 noise ORB 600 ложных ошибок в фотографий кол-во групп групп группах без группы связей 27 0 0 40 2022 35 2 0 22 2095 41 4 0 9 2439 38 1 5 10 3181 38 0 3 12 4655 noise BRISK 300 𝑣𝑚𝑎𝑥 время групп ложны ошибок в фотографий кол-во 𝑣𝑚𝑎𝑥 время сек. х групп группах без группы связей сек. 0,7 295 30 0 0 33 1947 0,7 3180 0,75 298 37 0 0 18 1949 0,75 3173 0,8 324 39 0 2 9 2808 0,8 3264 0,85 430 41 0 1 6 4250 0,85 3165 0,9 475 40 2 0 11 6718 0,9 3225 noise BRISK 600 ложных ошибок в фотографий кол-во групп групп группах без группы связей 38 0 0 14 4136 41 0 0 7 4446 42 0 1 2 6044 42 0 0 6 8785 40 2 0 10 12792 noise AKAZE 300 время ложны ошибок в фотографий кол-во время 𝑣𝑚𝑎𝑥 групп сек. х групп группах без группы связей сек. 15 30 4 2 34 1380 0,7 80 17 33 5 0 29 1641 0,75 103 23 34 3 6 20 1996 0,8 160 41 33 4 5 25 2470 0,85 219 84 36 6 1 22 3161 0,9 251 noise AKAZE 600 ложных ошибок в фотографий кол-во групп групп группах без группы связей 37 1 1 15 3536 39 1 1 8 4236 38 0 2 10 5046 40 0 1 5 6165 39 1 1 7 7342 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 noise ORB 300 время ложны ошибок в фотографий кол-во групп сек. х групп группах без группы связей 28 25 0 0 45 1424 32 32 2 0 28 1566 34 35 2 2 19 2073 46 38 3 4 12 2845 92 36 4 4 17 4308 38

Тесты размытых изображений. 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 blur ORB 300 время ложных ошибок в фотографий кол-во групп сек. групп группах без группы связей 20 27 0 0 41 1900 21 34 0 0 26 2246 24 37 2 4 16 2558 35 37 4 4 16 3487 72 34 4 5 20 4689 blur BRISK 300 время ложных ошибок в фотографий кол-во групп сек. групп группах без группы связей 6 19 0 0 57 753 6 22 1 0 51 994 6 31 8 1 33 1305 9 30 10 6 28 1557 17 29 4 9 25 1956 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 blur ORB 600 время ложных ошибок в фотографий кол-во групп сек. групп группах без группы связей 14 28 3 0 38 1455 15 35 8 1 22 1796 18 36 8 1 17 2124 32 32 4 4 23 2734 80 35 7 3 19 3326 blur BRISK 600 время ложных ошибок в фотографий кол-во групп сек. групп группах без группы связей 5 18 0 0 60 788 5 22 1 0 51 947 6 30 4 1 34 1272 9 31 4 4 29 1482 25 31 6 7 25 1696 blur AKAZE 300 blur AKAZE 600 𝑣𝑚𝑎𝑥 время групп ложных ошибок в фотографий кол-во сек. групп группах без группы связей 𝑣𝑚𝑎𝑥 время групп ложных ошибок в фотографий кол-во сек. групп группах без группы связей 0,7 0,75 0,8 0,85 0,9 0,7 0,75 0,8 0,85 0,9 8 9 11 17 35 30 31 34 33 33 6 8 7 4 7 2 1 5 6 6 34 30 21 21 21 1387 1477 1683 1922 2557 17 18 21 52 127 31 37 38 36 38 0 0 0 1 1 0 0 0 8 2 31 22 14 9 12 2329 2643 2936 3438 4103 2. Вторая группа. Тесты фотографий текстур. 𝑣𝑚𝑎𝑥 время сек. 0,7 1 0,75 1 0,8 1 0,85 2 0,9 4 texture ORB 300 ложных ошибок в фотографий кол-во время 𝑣𝑚𝑎𝑥 групп групп группах без группы связей сек. 7 2 0 15 431 0,7 1 7 3 0 15 555 0,75 1 8 1 1 12 792 0,8 1 8 3 1 12 1030 0,85 3 8 1 0 13 1390 0,9 8 texture ORB 600 ложных ошибок в фотографий кол-во групп групп группах без группы связей 8 1 0 12 1089 8 1 0 12 1089 8 1 0 12 1309 9 3 1 9 1632 8 0 2 11 2285 𝑣𝑚𝑎𝑥 время сек. 0,7 9 0,75 9 0,8 9 0,85 11 0,9 13 texture BRISK 300 ложных ошибок в фотографий кол-во время 𝑣𝑚𝑎𝑥 групп групп группах без группы связей сек. 5 0 0 19 994 0,7 9 6 0 0 17 1371 0,75 9 7 0 0 14 1840 0,8 9 7 2 0 15 2188 0,85 11 6 2 0 13 3875 0,9 13 texture BRISK 300 ложных ошибок в фотографий кол-во групп групп группах без группы связей 5 0 0 19 994 6 0 0 17 1371 7 0 0 14 1840 7 2 0 15 2188 6 2 0 13 3875 𝑣𝑚𝑎𝑥 время сек. 0,7 <1 0,75 <1 0,8 <1 0,85 1 0,9 1 texture AKAZE 300 ложных ошибок в фотографий кол-во время 𝑣𝑚𝑎𝑥 групп групп группах без группы связей сек. 5 0 0 19 359 0,7 2 4 0 0 21 389 0,75 3 4 0 0 21 447 0,8 4 5 1 0 19 547 0,85 5 7 2 0 15 657 0,9 6 texture AKAZE 600 ложных ошибок в фотографий кол-во групп групп группах без группы связей 6 0 0 15 1947 6 0 0 15 2236 6 0 0 15 2577 6 0 0 15 2926 7 0 0 13 3272 39

3. Третья группа. Тесты фотографий лиц. 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 face ORB 300 время ложных ошибок в фотографий кол-во 𝑣 время групп 𝑚𝑎𝑥 сек. групп группах без группы связей сек. 2 2 1 0 26 43 0,7 2 2 7 4 0 16 212 0,75 3 3 8 4 2 10 279 0,8 3 3 11 4 2 5 503 0,85 6 6 12 4 1 5 934 0,9 13 face ORB 600 ложных ошибок в фотографий кол-во групп групп группах без группы связей 3 0 0 24 90 7 3 0 16 209 10 2 3 7 317 9 4 3 7 466 8 3 0 14 795 face BRISK 300 время ложных ошибок в фотографий кол-во 𝑣 время групп 𝑚𝑎𝑥 сек. групп группах без группы связей сек. 3 1 0 0 28 93 0,7 10 3 6 3 0 18 228 0,75 11 4 11 5 0 8 350 0,8 13 5 7 2 7 6 499 0,85 20 12 9 4 1 10 826 0,9 24 face BRISK 600 ложных ошибок в фотографий кол-во групп групп группах без группы связей 5 1 0 19 254 7 3 0 14 385 9 4 1 9 517 8 2 3 11 726 9 4 3 8 1094 face AKAZE 300 𝑣𝑚𝑎𝑥 0,7 0,75 0,8 0,85 0,9 face AKAZE 600 время ложных ошибок в фотографий кол-во время 𝑣𝑚𝑎𝑥 групп сек. групп группах без группы связей сек. <1 1 1 2 4 5 8 9 8 10 3 7 4 2 4 1 1 0 3 2 19 12 12 10 7 222 327 412 507 687 0,7 0,75 0,8 0,85 0,9 4 4 6 12 18 групп 10 11 10 11 11 ложных ошибок в фотографий кол-во групп группах без группы связей 5 4 4 3 3 0 1 2 4 2 10 7 7 2 4 341 458 532 670 946 40

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв