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

Сопоставление изображений является одним из фундаментальных аспектов многих задач компьютерного зрения, таких как распознавание объектов, построение трёхмерной сцены на основе нескольких изображений, создание стереопары, создание панорамных изображений, 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 и инвариантности к масштабу.
Постановка задачи
Задача данной работы состоит в сравнении методов детектирования особых точек. Процесс её выполнения можно разделить на следующие этапы:
• Изучение принципов функционирования методов.
• Разработка инструментария, позволяющего обнаруживать особые точки каждым из рассмотренных детекторов.
• Анализ результатов работы методов на наборе тестовых изображений.
• Получение выводов о возможных сценариях использования каждого из них, основанных на выявленных во время анализа достоинствах и недостатках.

Купить

На основе полученных результатов, автор работы может заявить, что среди рассмотренных в работе алгоритмов нет единственного, который подойдет для любой задачи, в которой используется поиск особых точек на изображении. Каждый из рассмотренных методов обладает своими достоинствами и недостатками и может быть наиболее подходящим для решения какой-либо задачи.
Основными достоинствами метода Харриса является инвариантность к повороту и шуму, а также достаточно высокая скорость работы. Он лучше всего подойдёт для задач, при решении которых используется поиск особых точек на изображениях с ярко-выраженными углами, наличием шума. Он не подойдёт для задач, в которых производится сравнение изображений разного масштаба и с большими различиями в яркости. Также стоит обратить внимание на детектор Харриса, если важна скорость работы метода. Примером задач, в которых детектор Харриса покажет хорошие результаты могут быть задачи, в которых используется поиск простых фигур на изображениях, созданных с помощью средств компьютерной графики, так как в таком случае все углы этих фигур будут хорошо заметны для алгоритма.
Детектор Shi-Tomasi очень похож по результатам на детектор Харриса, поэтому может использоваться в задачах похожего вида. Однако стоит учитывать меньшую скорость работы. По сравнению с методом Харриса он обладает более высоким качеством детектирования. Как результат, этот метод станет лучшим решением, если в задаче более важна точность, и не так важна скорость работы.
Детектор FAST обладает несравнимой скоростью работы, однако уступает предыдущим методам в качестве детектирования и показывает гораздо худший результат при анализе изображений с присутствующим на них шуме. Детектор FAST лучше всего подходит для задач, в которых время
Метод SIFT показал худший результат среди исследованных детекторов по многим характеристикам, однако обладает хорошим качеством детектирования и устойчивостью к изменениям яркости. SIFT оказался самым медленным из рассмотренных детекторов и не подойдёт для большинства задач, однако если в задаче совершенно не важна скорость работы и в сравниваемых изображениях нет шума и изображенные объекты не повёрнуты, но необходима высокая точность, то SIFT может быть выбран в качестве наиболее подходящего метода.
Метод SURF работает не так быстро как FAST или Harris, но обладает крайне высокой степенью устойчивости к афинным преобразованиям, изменениям яркости и качеством детектирования в целом. SURF будет лучшим выбором для задач, в которых критически важна точность детектирования. Примерами таких задач может быть построение стереопары, панорам и поиск объектов снятых с разных ракурсов и при разном освещении.
Последний из рассмотренных детекторов, BRISK отличается высокой скоростью работы на изображениях высокого разрешения. При качестве детектирования, сравнимом с качеством детектора SURF и независимостью от поворотов и изменения масштаба, он подойдёт для работы с большими изображениями, например при поиске совпадений на фотографиях со спутников, так как для таких фотографий характерно большое разрешение.
Задачей данной выпускной квалификационной работы было исследование принципов работы детекторов особых точек на изображении и их сравнение на практике. Для этого было разработано программное обеспечение, реализующее методы детектирования и использовано для сравнения результатов их работы. На основе полученных результатов были сделаны выводы о сильных и слабых сторонах алгоритмов и возможных сценариях применения каждого из них.

Купить