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

Введение 3
Обзор литературы 5
Постановка задачи 6
Глава 1. Детекторы особых точек 7
1.1. Детектор Моравеца 7
1.2. Детектор Харриса 8
1.3. Детектор Shi-Tomasi 10
1.4. Детектор FAST 10
1.5. Детектор SIFT 13
1.6. Детектор SURF 16
1.7. Детектор BRISK 16
Глава 2. Практическое сравнение работы детекторов 18
2.1. Детектор Харриса 18
2.2. Детектор Shi-Tomasi 23
2.3. Детектор FAST 27
2.4. Детектор SIFT 32
2.5. Детектор SURF 37
2.6. Детектор BRISK 41
2.7. Сравнение результатов работы методов 45
Выводы 48
Заключение 50
Список литературы 50

Купить

Сопоставление изображений является одним из фундаментальных аспектов многих задач компьютерного зрения, таких как распознавание объектов, построение трёхмерной сцены на основе нескольких изображений, создание стереопары, создание панорамных изображений, motion tracking (слежение за объектом в видеопоследовательности) и так далее. По причине того, что область знаний, решающая подобные проблемы, ещё молода (интенсивное изучение началось лишь в 1970-х годах), не существует определённого универсального метода, идеально подходящего для всех задач такого рода. Однако, существуют методы решения более узких задач, каждый из которых будет показывать лучшие результаты в зависимости от задачи.
Человеку несложно сравнить два изображения и выделить на них объекты, всё это происходит на интуитивном уровне и не вызывает затруднений. Но для компьютера изображение — лишь набор данных, не несущий информации об объектах, изображенных на нём. Можно описать два основных подхода к наделению машины таким умением.
Первый подход заключается в сравнении изображений на основе информации полученной от анализа всех пикселей изображения [3]. В общем случае алгоритм такого типа выглядит следующим образом: для каждого пикселя вычисляется значение некоторой функции, и на основе этих значений получается определенная характеристика всего изображения в целом. И тогда задача сводится к сравнению этих характеристик. И хотя такие алгоритмы просты и не требуют больших вычислительных затрат, результат их работы оставляет желать лучшего. Причина заключается в их основной идее, в характеристику изображения вносит вклад каждый пиксель, несмотря на ценность этого вклада. Метод будет выдавать неприемлемый результат в случае появления новых объектов, перекрытия одних объектов другими, появления шума, изменение положения объекта в трёхмерном пространстве и так далее.
Определение. Особой точкой изображения называется точка изображения, окрестность которой o(m) отличима от окрестности любой другой точки изображения o(n) в некоторой другой окрестности особой точки 02(m). [1]
В большинстве алгоритмов в качестве окрестности точки используется прямоугольное окно размером 5x5 пикселей. Харалик и Шапир [2] определили следующие требования, которым должны удовлетворять особые точки:
1. Отличимость: Особая точка должна выделяться на фоне и быть уникальной в своей окрестности.
2. Инвариантность: Выбор особых точек должен быть независимым от афинных преобразований.
3. Стабильность: Выбор особых точек должен быть устойчив к шуму и ошибкам.
4. Уникальность: Помимо локальной отличимости, особая точка должна также обладать свойством глобальной уникальности для того, чтобы улучшить различимость повторяющихся паттернов.
5. Интерпретируемость: Особые точки должны определяться таким образом, чтобы их можно было использовать для анализа соответствий и лучшей интерпретации изображения.
Процесс сравнения изображений разделяется на три этапа. Первый этап — нахождение множества особых точек с помощью методов, называемых детекторами. Данные методы обеспечивают инвариантность нахождения одних и тех же точек относительно преобразований изображения. Однако, недостаточно использования лишь детектора, так как результатом его работы
является множество координат особых точек, которые на каждом изображении различны. Для этого на втором этапе происходит построение дескрипторов. Дескриптор — это описание точки, уникально идентифицирующее её среди множества всех точек. Дескриптор должен обеспечивать инвариантность нахождения соответствий между точками относительно преобразований изображения. Некоторые методы выполняют сразу обе задачи, детектирование особых точек и построение дескрипторов. И третий этап заключается в сравнении дескрипторов и поиске точек, совпадающих на обоих изображениях.
Обзор литературы
В 1981 году с выходом работы Моравеца [4] начались исследования сопоставления изображений с помощью нахождения особых точек. Моравец предложил простой алгоритм поиска углов на изображении, который впоследствии был улучшен Харрисом и Стефенсом в 1988 году в работе «A combined corner and edge detector» [5], и был назван детектором Харриса (Harris and Stephens detector или Plessey operator). Его преимуществом была инвариантность детектора к поворотам. в 1994 году Ши и Томаси внесли небольшую модификацию в детектор Харриса, получив более точные результаты при детектировании в работе «Good Features to Track» [6]. В 2005 году Ростен и Драммонд предложили метод детектирования особых точек, который они назвали Features from Accelerated Segment Test (особенности ускоренных испытаний сегмента) в [7]. Главной целью его создания было значительное ускорение работы детектора. Однако FAST обладал рядом недостатков. С целью улучшить алгоритм, Э. Ростен, Р Портер и Т. Драммонд предложили использовать машинное обучение для определения особых точек в работе [8]. Этот алгоритм был назван FAST-ER (ER — Enhanced Repeatability, улучшенная повторяемость). И хотя FAST-ER оказался медленнее, качество детектирования повысилось. Все предыдущие методы не были инвариантны к изменению масштаба. Для решения этой проблемы, в 2004 году, Д. Лоув предложил новый алгоритм детектирования и вычисления дескрипторов особых точек, названный SIFT (Scale Invariant Feature Transform) в работе «Distinctive Image Features from Scale-Invariant Keypoints» [9], основывающийся на рассмотрении разностей Гауссианов. Метод SURF был представлен Г. Бэем в 2006 году в работе [10], он был создан с целью сохранить качества SIFT, повысив при этом скорость работы. Метод BRISK был предложен С. Леутнеггером, М. Чли и Р Сигвартом в 2011 году в [11]. Целью его создание было достижение высокой скорости работы, сопоставимой с FAST и инвариантности к масштабу.
Постановка задачи
Задача данной работы состоит в сравнении методов детектирования особых точек. Процесс её выполнения можно разделить на следующие этапы:
• Изучение принципов функционирования методов.
• Разработка инструментария, позволяющего обнаруживать особые точки каждым из рассмотренных детекторов.
• Анализ результатов работы методов на наборе тестовых изображений.
• Получение выводов о возможных сценариях использования каждого из них, основанных на выявленных во время анализа достоинствах и недостатках.

Купить