Исследование показателей качества и быстродействия поиска опорных точек на изображениях методом SURF



Постановка проблемы

При рассмотрении задачи, когда имеется два изображения одного и того же объекта, ставится целью получить расширенную информацию об объекте. Для этого необходимо совместить эти изображения. Существует два способа решения проблемы. При прямом сопоставлении будет выполнен поиск преобразования, при котором большинство пикселей изображений будет совпадать. Но в ряде случаев (изменение масштаба, точки съемки, освещения или перекрытие объекта распознавания) попиксельное сопоставление приведет к неверному решению задачи. В таких случаях приходят на помощь локальные особенности (т. е. опорные точки). Опорная точка представляет собой точку с характерной окрестностью. Более конкретное определение опорной точки можно делать исходя из применяемого метода. Примерами опорных точек являются изолированные точки, углы, грани объектов или некоторые области. При таком решении ведется поиск и анализ лишь тех пикселей, вклад которых в общую характеристику изображения будет весомым.

Существует множество различных прикладных задач, в которых применение методов поиска локальных особенностей является целесообразным. К таким задачам можно отнести автоматическую локализацию и распознавание дорожных знаков на изображениях, идентификацию человека или автомобиля при видеонаблюдении, сопоставление изображений для построения панорам, воспроизведение 3D-модели объекта по его двумерными изображениям и другие.

Важность решения этих задач обусловлена широким спектром их практического применения. А в результате использования методов, основанных на поиске опорных точек, можно снизить нагрузку на вычислительные ресурсы систем.

Анализ существующих методов. Методы, основанные на сопоставлении опорных точек, оказались эффективными для целого класса других задач. Примером служат задачи поиска изображений по базе данных, распознавания объектов на сцене, классификация изображений, оценка движения и слежение за объектом.

Исходя из того, какой объект представляет собой опорную точку, все алгоритмы поиска (детекторы) особенностей можно разделить на классы. Удовлетворительная работа метода обеспечивается свойством инвариантности метода к искажениям изображений. Выделяют детекторы углов (детектор Харриса, детектор Моравеца), которые характеризуются инвариантностью к смещению, но отсутствием инвариантности к масштабированию. Детекторы пятен (LoG, DoG) инвариантны к масштабированию, а также выделяют те области, которые слишком сглажены для детекторов углов. Также выделяют детекторы областей (метод MSER). Количество найденных областей зачастую компенсируется вкладом особенностей в характеристику изображения. Отдельной группой можно выделить методы (SURF, SIFT), которые сочетают в себе и поиск опорных точек, и формирование вектора признаков, построенного по окрестности точки (дескриптора).

В данной работе для рассмотрения выбран метод SURF [1], поскольку он считается одним из самых эффективных современных алгоритмов. Реализации метода есть во многих математических библиотеках. Исследование метода необходимо для оценки значений показателей качества и быстродействия работы метода. Это позволит определить достоинства и недостатки метода, а также задачи, в которых применение SURF будет эффективным.

Алгоритм метода SURF. Алгоритм работы SURF предусматривает выполнение следующих этапов:

‒ масштабно-пространственное представление;

‒ расчет значений гессиана;

‒ поиск точек локальных максимумов;

‒ определение точки истинного максимума;

‒ определение ориентации опорной точки;

‒ формирование дескриптора опорной точки.

Обнаружение опорных точек в методе SURF основано на вычислении гессиана. Гессиан инвариантен к сдвигу яркости изображения, но не инвариантен к масштабу. Решением данной проблемы является перебор разных масштабов и фильтров, поочередное их применение к одному пикселю. Метод разбивает все множество масштабов на октавы.

Элементы матрицы Гессе вычисляются как свертка пикселей изображения на фильтры Fast-Hessian, которые представляют собой бинаризированную аппроксимацию Лапласиан Гауссиан. Таким образом, в SURF гессиан вычисляется по формуле

,

где , , — свертки пикселей на фильтры.

Следовательно, в качестве опорных точек выбираются локальные максимумы гессианов, соответствующие локальным максимумам изменения градиента яркости.

После нахождения точек локальных максимумов определяется точка истинного максимума гессиана. На этом шаге этап детектирования окончен.

Дескриптор представляет собой массив из 64 чисел, которые определяют опорную точку. Дескриптор SURF инвариантен к масштабу и вращению.

Полный алгоритм работы метода SURF представлен на рисунке 1.

Рис. 1. Алгоритм метода SURF

Исследование показателей качества и быстродействия метода. Исследование метода проводилось в три этапа.

Рассмотрим зависимость времени работы метода от размеров изображений. В таблице 1 приведены результаты, по которым видно, что при увеличении размерности изображений увеличивается и количество найденных опорных точек, но также возрастает и время работы. При анализе больших изображений (1600×1200) суммарное время составило около 3 с, что является ограничением для применения метода в системах, работающих в режиме реального времени.

Таблица 1

Количество найденных опорных точек ивремя распознавания взависимости от размеров изображений

Размер изображения, px		Опорные точки, шт.		Количество пар общих опорных точек, шт.	Время детектирования, мс		Время сопоставления, мс
объекта	сцены	объекта	сцены		объекта	сцены
320×320	790×470	552	728	38	193	418	205
520×520	990×590	757	830	68	385	553	220
720×720	1190×715	815	1401	84	641	744	263
920×920	1390×830	864	1562	142	996	1132	316

Следующим этапом исследования являлся анализ показателей точности

P (precision) и полноты R (recall) по методике, описанной в [2].

где - количество правильно выделенных объектов, - количество ошибочно выделенных объектов, — количество объектов, которые ошибочно не были выделены. Полагаем, что соответствие изображений является правильным, если область их пересечения составляет более 50 %.

Для тестирования был составлен набор изображений, которые имеют деформации масштаба и поворота, точки обзора, изменение уровня размытия, изменение качества JPEG-сжатия и изменение уровня яркости (рисунок 2).

Рис. 2. Тестовый набор изображений с деформациями JPEG-сжатия, точки обзора, уровня размытия, уровня яркости, масштаба и поворота.

Полученные результаты приведены в таблице 2. Установлено усредненное значение точности (precision) 0,7 и усредненное значение полноты (recall) 0,5.

Таблица 2

Средние значения точности иполноты для тестовых изображений

Особенность изображения	Среднее значение
	точности	полноты
Качество JPEG-сжатия	0.89	0.8
Изменение точки обзора	0.3	0.2
Изменение уровня размытия	0.85	0.7
Изменение уровня яркости	0.8	0.65
Изменение масштаба и поворота	0.7	0.4

Также на данном наборе изображений была проведена оценка количества правильно идентифицированных точек.

В результате двух различных оценок было отмечено, что лучше всего метод справился с изображениями с разным JPEG-сжатием, изменением уровней размытия и яркости. Наименее удовлетворительные результаты получены для случая изменения точки обзора изображения.

Выводы

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

Неудовлетворительные результаты также наблюдались при значительном изменении точки обзора изображения (более 45 градусов). Скорость обработки изображений (при анализе изображения с разрешением 1600×1200 составило около 3 с) накладывает ограничения на использование алгоритма в режиме реального времени.

Литература:

1. H. Bay, A. Ess, T. Tuytelaars, and L. Van Gool, “Speeded-up robust features (SURF)”, International Journal on Computer Vision and Image Understanding, vol. 110–346–359 pp. — 2008.
2. Nicolas Bourdis, Marraud Denis, Hichem Sahbi. Constrained optical flow for aerial image change detection. IEEE International Geoscience and Remote Sensing Symposium (IGARSS), Jul 2011, Vancouver, Canada — 4176–4179 pp. — 2011.