Методы нахождения особых точек изображения и их дескрипторов



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

Ключевые слова: особые точки, дескрипторы, изображение, сопоставление

Задача сопоставления изображений используется следующих целей:

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

Человек по изображению может интуитивно понять, что на нем находится. Для компьютера же любое изображение — ничем не говорящий набор данных. Необходимо определить, как же все-таки компьютер определяет изображение.

У каждого изображения есть некие особые точки. Что это такое?

Особые точки — такие точки, по которым можно классифицировать изображение, распознать его, некая особенность изображения, уникальность. Как правило — это угловые точки, либо те, где резко меняется цвет, яркость, и т. д. Нужно выбирать такие точки, которые вносят некий вклад в характеристику изображения, также необходимо считать особыми такие точки, которые с большой вероятностью будут найдены на другом изображении. Каждый метод обнаружения особых точек должен гарантировать инвариантность относительно любых преобразований изображения.

Осталось понять, каким образом компьютер понимает — какие ключевые точки разных изображений соответствуют друг другу. Ведь у каждой точки на разных изображениях разные координаты, каким образом идет их сопоставление? Для этого каждой особой точке необходимо присвоить описание, которое будет одинаковым на разных изображениях.

Дескриптор — идентификатор особой точки, который делает её уникальной относительно остальных особых точек. Разумеется, используя дескрипторы, нельзя забывать об инвариантности относительно преобразования изображений.

В итоге получается следующая инструкция по сопоставлению изображений:

1. На изображениях находятся особые точки и их дескрипторы
2. По дескрипторам среди этих точек выявляются пары соответствующих точек
3. По этим парам идет построение модели преобразования изображений

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

1. Изменение яркости
2. Изменение размера (масштабирование)
3. Изменение положения камеры
4. Вращение
5. Смещение

Постановка задачи

В текущей работе был использован программный пакет «MATLAB 2014a», а также набор функций «Computer Vision System Toolbox», рассматривались следующие методы поиска особых точек:

1. SURF
2. BRISK
3. Harris
4. FAST
5. MSER
6. Minimal Eigenvalue

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

Для исследования было взято 3 типа изображений: пейзаж, портрет и текстовый документ. Необходимо было проанализировать: какая пара «метод/дескриптор» наилучшим образом с минимальными ошибками и максимальным количеством пар особых точек подходит для того или иного типа изображений.

Дескрипторы же были использованы следующие:

1. SURF
2. BRISK
3. FREAK
4. Block

Реализация

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

Дескриптор		SURF			BRISK		FREAK	Block
Метод
SURF		Пейзаж			Пейзаж		Пейзаж	Пейзаж
	266/267 99 %			182/182 100 %			157/157 100 %	140/172 81 %
		Портрет			Портрет		Портрет	Портрет
	30/35 86 %			15/29 50 %			3/4 75 %	12/36 33 %
		Документ			Документ		Документ	Документ
	1000/1200 83 %			1450/1456 99 %			228/234 97 %	357/562 64 %
BRISK		Пейзаж			Пейзаж		Пейзаж	Пейзаж
	24/25 96 %			21/21 100 %			18/18 100 %	35/43 81 %
		Портрет			Портрет		Портрет	Портрет
	2/9 22 %			1/16 6 %			0/6 0 %	0/4 0 %
		Документ			Документ		Документ	Документ
	140/186 75 %			97/100 97 %			57/66 83 %	350/543 64 %
Harris		Пейзаж			Пейзаж		Пейзаж	Пейзаж
	343/346 99 %			330/330 100 %			211/211 100 %	383/386 98 %
		Портрет			Портрет		Портрет	Портрет
	5/16 31 %			5/5 100 %			0/3 0 %	7/7 100 %
		Документ			Документ		Документ	Документ
	600/782 76 %				1290/1298 99%		200/227 88 %	800/1043 80 %
FAST		Пейзаж			Пейзаж		Пейзаж	Пейзаж
	152/152 100 %			127/127 100 %			79/79 100 %	200/203 98 %
		Портрет			Портрет		Портрет	Портрет
	0/3 0 %			0/0 0 %			1/7 14 %	2/4 50 %
		Документ			Документ		Документ	Документ
	800/1284 62 %			1600/1665 96 %			500/556 90 %	1200/1500 80 %
MSER		Пейзаж			Пейзаж		Пейзаж	Пейзаж
	146/146 100 %			65/65 100 %			54/54 100 %	72/80 90 %
		Портрет			Портрет		Портрет	Портрет
		38/46 84%		0/0 0 %			3/4 75 %	1/2 50 %
		Документ			Документ		Документ	Документ
	100/126 79 %			68/72 94 %			23/27 85 %	200/272 74 %
MinEigen		Пейзаж			Пейзаж		Пейзаж	Пейзаж
	894/905 98 %				835/835 100%		392/394 99 %	700/767 91 %
		Портрет			Портрет		Портрет	Портрет
	111/172 65 %			36/40 90 %			3/3 100 %	14/15 93 %
		Документ			Документ		Документ	Документ
	500/939 53 %			270/297 90 %			240/297 80 %	600/1151 52 %

Выводы

Для пейзажей лучше всего подходит метод Minimal Eigenvalue, т. к. он схож с методом Harris, который инвариантен к афинным преобразованиям, но чувствителен к шумам, более стабильный поиск углов, которые встречаются на фотографиях зданий с высоты гор, деревья, и т. д. Дескриптор же лучше всего использовать BRISK.

Для портретов наиболее подходит метод MSER: инвариантность к вращениям, хорошо подходит для нахождения сходств по шаблону, метод ищет точки внутри регионов и на внешних границах. Наиболее подходящий дескриптор — SURF, где опять же встречается инвариантность к вращениям и изменениям масштаба; большинство точек находятся на границах и в ярко-выраженных местах, что свойственно данному дескриптору.

Для текстовых документов отлично подходит метод Harris, который может и чувствителен к шумам, но в данном случае этим можно пренебречь.

Метод FAST нашел больше точек, но соответствий при каждом дескрипторе значительно меньше. Больше всего соответствий при использовании дескриптора BRISK.

Заключение

На сегодняшний день существует множество программ по построению панорам. Известно, что при работе большинства из них в процессе склейки изображений на протяжении всей панорамы использовался один метод и дескриптор. Но что если на панораме будет несколько типов изображений? Рассмотрим ситуацию: пользователь фотографирует пейзаж, на кадре появляется портрет, после портрета идет макросъемка, а далее на кадре присутствует какой-либо документ. Большинство программ будет склеивать все одним способом. Проведенные исследования могут послужить для написания более универсальной программы, где при фотосъемке панорамы изначально будет определяться тип фотографии методом распознавания изображения (с использованием сегментаций, к примеру), затем будет подбираться метод нахождения точек и их описания, после чего произойдет сопоставление кадров с минимальными ошибками.

Литература:

1. Детекторы углов. https://habrahabr.ru/post/244541/
2. Ипатов Ю. А., Кревецкий А. В. Методы обнаружения и пространственной локализации групп точечных объектов // Журнал «Кибернетика и программирование». Содержание № 06, 2014
3. Золотых Н. Ю., Кустикова В. Д., Мееров И. Б. Обзор методов поиска и сопровождения транспортных средств на потоке видеоданных // Вестник Нижегородского университета им Н. И. Лобачевского. Выпуск № 5–2 / 2012
4. Применение метода SURF в системах контроля и управления доступом https://habrahabr.ru/post/152679/
5. М. О. Гончаренко. Сравнительный анализ методов формирования дескрипторов изображений в контексте задачи сегментации видеопотока. // Бионика интеллекта. 2015.