Размещено на http://www.allbest.ru/

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Поволжский государственный университет телекоммуникаций и информатики»

Факультет Информационных систем и технологий

Направление (специальность) Информатика и вычислительная техника

Кафедра Информационных систем и технологий

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

(БАКАЛАВРСКАЯ РАБОТА)

Построение SIFT дескрипторов и задача сопоставления изображений

Утверждаю зав.кафедрой, д.т.н., профессор Н.И. Лиманова

Руководитель доцент, к.т.н., с.н.с. О.Л.Куляс

Н. контролер ассистент А.С.Лошкарев

Разработал ПО-31 С.В.Маренков

Самара 2017

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Поволжский государственный университет телекоммуникаций и информатики»

ЗАДАНИЕ

по подготовке выпускной квалификационной работы

Студента Маренкова Сергея Васильевича

1 Тема ВКР

Построение SIFT дескрипторов и задача сопоставления изображений

Утверждена приказом по университету от 3.034.2017 № 74-2

2 Срок сдачи студентом законченной ВКР 15.06.2017

3 Исходные данные и постановка задачи

1. Изучить и проанализировать основные типы дескрипторов и алгоритмы их построения и сопоставления

2. Проанализировать основные типы детекторов, использующие дескрипторы для анализа границ объектов на изображении

3.Изучить характеристики сходства изображений, на основе которых осуществляется построение и сопоставление дескрипторов

4. Провести моделирование сопоставления изображений на основе одного проанализированного дескриптора

4 Перечень подлежащих разработке в ВКР вопросов или краткое содержание ВКР. Сроки исполнения 15.06.2017

1. Анализ основных типов дескрипторов изображения

2. Обзор основных типов детекторов, использующих дескрипторы для поиска и анализа границ объектов на изображении

3. Обзор характеристик сходства изображений

4. Моделирование алгоритма сопоставления изображений на основе дескрипторов SIFT

5 Перечень графического материала. Сроки исполнения 15.06.2017

Презентационные материалы

6 Дата выдачи задания « 4 » апреля 2017 г.

Кафедра Информационных систем и технологий

Утверждаю зав.кафедрой, д.т.н., доцент Н.И. Лиманова

Руководитель доцент, к.т.н., с.н.с. О.Л.Куляс

Задание принял к исполнению ПО-31 С.В.Маренков

Руководитель ВКР _______ ________________ ____________________

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Поволжский государственный университет телекоммуникаций и информатики»

ПОКАЗАТЕЛИ КАЧЕСТВА ВКР

Студент ПО-31 С.В.Маренков

Руководитель ВКР к.т.н., доцент, с.н.с. О.Л. Куляс

По ВКР студента Маренкова Сергея Васильевича

На тему Построение SIFT дескрипторов и задача сопоставления изображений

1 Работа выполнена :
- по теме, предложенной студентом
- по заявке предприятия
		наименование предприятия
- в области фундаментальных и поисковых научных исследований
		указать область исследований
2 Результаты ВКР:
- рекомендованы к опубликованию
		указать где
- рекомендованы к внедрению
		указать где
- внедрены
		акт внедрения
3 ВКР имеет практическую ценность		ПО для сопоставления изображений
		в чем заключается практическая ценность
4 Использование ЭВМ при выполнении ВКР:
(ПО, компьютерное моделирование, компьютерная обработка данных и др.)		Язык программирования Ruby
5. ВКР прошла проверку на объем заимствований		% заимствований
		электронная версия сдана

Введение

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

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

Объектом исследований является цифровая обработка изображений.

Предметом исследований являются алгоритмы и методы построения дескрипторов изображений и их дальнейшее сопоставление.

Целью данной дипломной работы является моделирование алгоритма поиска и построения дескрипторов изображения SIFT для дайнешего сопоставления. Задачи, которые необходимо решить в ходе исследований:

• Изучить и проанализировать основные типы дескрипторов изображений;

• Изучить и проанализировать основные типы детекторов границ объектов на изображении;

• Изучить и проанализировать основные характеристики схожести изображений;

• Провести моделирование алгоритма поиска и построения дескрипторов SIFT.

Теоретические и практические вопросы, лежащие в основе дипломной работы, рассмотрены в большом количестве источников различного характера. К таким источникам относятся учебные и учебно-методические пособия, специальные издания и электронные источники информации. Классификация и математический аппарат основных типов дескрипторов изображений описываются в книгах Zitova B. [1], Mikolajczyk K. [2], Blokhinov Y.B. [3], Baumberg A. [4], Flusser J [6], Hu M.K. [5], Juan L [14], Tran P. [16], Valgren C. [16]. Вопросы, связанные характеристиками схожести изображений и детекторами границ объектов изложены в работах Lowe D.G. [7], Tola E. [8], Bay H. [9], Calondr M. [10], AlpaslanF. [11], Brown M. [12], Конушина А.С. [15], Meng Y. [17]. Вопросы, касающиеся реализации и моделировании алгоритмов, использующих дескрипторы SIFT рассмотрены в работах Гонсалеса Р [18], Kybic J. [19], Hartley R.I. [20]. Язык программирования Ruby подробно описан в работах Роганова Е.А. [21] и Фултона Х. [22].

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

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

Заключение содержит обобщённые результаты дипломной работы, выводы по работе и рекомендации по использованию её результатов.

1. Обзор дескрипторов ключевых точек на изображении

Человек может сравнить изображения и выделять на них объекты визуально, на интуитивном уровне. Однако, для машины изображение -- просто набор данных. В общих чертах можно описать два подхода к тому, чтобы как-то «наделить» машину этим человеческим умением.

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

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

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

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

Идентификация объектов - процесс тесно связанный с распознаванием, заключающийся в объединении всей полученной информации от процесса распознавания в единое целое с целью классифицировать объект.

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

Можно выделить два основных подхода к поиску сходства изображений:

поиск по глобальным дескрипторам;

поиск по локальным дескрипторам.

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

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

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

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

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

Точечной особенностью (в литературе также используются термины «характеристическая точка», «точка интереса», «контрольная точка», interestpoint) называется точка изображения, структура окрестности которой ковариантная заданным преобразованиям изображения. Для выявления точечных особенностей разрабатываются методы-детекторы. Результатом работы детекторов является множество особых точек, для которых необходимо построить математическое описание.

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

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

· повторяемость. На изображениях одного и того же объекта или сцены, сделанных с разных точек зрения и при разных условиях освещения, большинство признаков должны быть детектированы;

· локальность. Признаки должны быть максимально локальными, зависеть только от небольшой окрестности;

· специфичность (отличие для разных точек);

· репрезентативность. Количество признаков должно быть достаточным, чтобы разумное число признаков детектировалось даже на небольшом изображении объекта;

· точность. Признаки должны быть точно продетектированны по отношению к масштабу и форме объекта;

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

Набор дескрипторов составляет модель изображения (фрагмент- запрос), которая впоследствии используется для сопоставления изображений. Решение о том, являются ли сопоставляемые изображения нечеткими дубликатами или нет, принимается на основе анализа наборов дескрипторов - моделей изображений.

Сопоставление дескрипторов осуществляется в два этапа:

1. На первом этапе устанавливаются пары наиболее близких дескрипторов (тем самым устанавливаются соответствия между точечными особенностями);

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

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

Дескрипторы представляют собой структуру описания свойств объекта. Выбранные для описания признаки должны быть как можно менеечувствительными к изменению размеров области (масштаб) и ее перемещению по изображению (сдвиг и поворот).

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

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

Главный вопрос - каким образом определять, какая ключевая точка одного изображения соответствует ключевой точке другого изображения. Ведь после применения детектора можно определить только координаты особых точек, а они на каждом изображении разные. Для решения данной дилеммы необходимы дескрипторы. Дескриптор - идентификатор ключевой точки, выделяющий её из остальной массы особых точек. В свою очередь, дескрипторы должны обеспечивать инвариантность нахождения соответствия между особыми точками относительно преобразований изображений.

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

1. На изображениях выделяются ключевые точки и их дескрипторы.

2. По совпадению дескрипторов выделяются соответствующие друг другу ключевые точки.

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

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

Перечислим некоторые преобразования, относительно которых необходимо получить инвариантность:

1) смещения

2) поворот

3) масштаб (один и тот же объект может быть разных размеров на различных изображениях)

4) изменения яркости

5) изменения положения камеры

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

Рис.1.1 - Общая схема алгоритма вычисления дескрипторов

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

, (1.1)

, (1.2)

, (1.3)

где S -сумма яркости по круглой окрестности точки (, ) радиуса R.

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

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

Хронологически первые дескрипторы основывались на теории алгебраических инвариантов. Для них была построена строгая математическая теория, доказан ряд теорем. Эти идеи нашли отражение в инвариантах Ху и Флюссера, которые представляют собой функции от комплексных моментов изображения:

, (1.4)

где i - мнимая единица;

I(x,y) - яркость изображения в точке.

В дискретном случае интегрирование заменяется суммированием. Значения инвариантов Ху и Флюссера не изменяются при повороте изображения, поэтому для их вычисления необязательно предварительно поворачивать фрагменты изображений.

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

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

Дескриптор SIFT стал де-факто стандартом в компьютерном зрении. На идее использования локальных гистограмм градиентов яркости изображения основывается большинство современных дескрипторов. Отличия более новых дескрипторов состоят в использовании ячеек в форме круговых секторов и колец (например, дескрипторы GLOH и DAISY).

В 2008 был представлен ближайший конкурент SIFT-дескриптора, SURF-дескриптор. В идейном смысле он похож на своего предшественника, но процедура описания окрестности интересной точки несколько иная, поскольку в ней используются не гистограммы взвешенных градиентов, а отклики исходного изображения на вейвлеты Хаара. На первом шаге получения дескриптора вокруг точки интереса строится квадратная область, которую ориентируют по некоторому предпочтительному направлению. Затем область разделяется на квадратные сектора. В каждом из секторов в точках, принадлежащих регулярной сетке, вычисляются отклики на два вида вейвлетов - горизонтально и вертикально направленные. Отклики взвешиваются Гауссианом, суммируются по каждому сектору, и образуют первую часть дескриптора.

Вторая часть состоит из сумм модулей откликов. Это сделано для того, чтобы учитывать не только факт изменения яркости от точки к точке, но и сохранить информацию о направлении изменения. SURF-дескриптор имеет длину 64. Как и SIFT, SURF-дескриптор инвариантен к аддитивному изменению яркости. Инвариантность к мультипликативному изменению яркости достигается путем нормировки дескриптора.

Рис.1.2 - Построение дескриптора SIFT

Рис.1.3 - Вейвлеты Хаара, используемые для вычисления SURF-дескрипторов, и области, по которым они вычисляются



Рис.1.4 - Компоненты SURF-дескриптора указывают на структуру изображения. Слева направо: однородная область, сильно анизотропная текстура, градиентная текстура

Среди алгоритмов поиска точек интереса существует разделение на более математические обоснованные, но относительно медленные (детектор Харриса, детектор SIFT), и более эвристические, но быстрые (SURF, FAST). То же разделение применимо к описанию точечных особенностей, только здесь в качестве разделяющего признака выступает компактность и простота вычисления дескриптора. Чем меньше длина дескриптора, тем меньше памяти требуется для его хранения, и меньше времени на сравнение его с другими. Эта черта очень важна при обработке большого числа изображений. К наиболее компактным относится дескриптор BRIEF. Для вычисления дескриптора в точкеpсравниваются значения яркостей точек, расположенных в ее окрестности. При этом сравниваются значения яркости не всех точек со всеми, а анализируется лишь небольшое подмножество соседних пар точек, координаты которых распределены случайно (но одинаковым образом для каждой анализируемой точки p). Если яркость в точке больше, чем яркость в точке, то i-я компонента дескриптора принимает значение 1, в противном случае она становится равной нулю. Фрагмент, по которому вычисляются дескрипторы, предварительно сглаживается. BRIEF-дескрипторы чрезвычайно просты в вычислении, поскольку их значения равны результату сравнения двух чисел. Они также очень компактны, поскольку результат элементарного теста - это число 0 или 1, то есть один бит. В стандартной реализации для построения одного BRIEF-дескриптора требуется выполнить 256 сравнений, что дает итоговую длину 64 байта. Это очень мало, учитывая, что SIFT-дескриптор состоит из 128 действительных чисел, то есть занимает как минимум 512 байтов. Наконец, сравнение BRIEF-дескрипторов занимает очень мало времени, поскольку сводится к вычислению расстояния Хэмминга между двумя последовательностями битов; эта элементарная операция выполняется чрезвычайно быстро на любом современном процессоре. Сами по себе дескрипторы BRIEF не инвариантны к повороту. Однако такой инвариантности можно добиться, если предварительно повернуть фрагмент вокруг точки интереса на угол, соответствующий, например, доминирующему направлению градиента яркости, как это делается для дескрипторов SIFT и SURF. Точно так же можно достичь инвариантности к другим ракурсным искажениям.

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

Дескрипторы границы включают в себя ряд наиболее распростран?нных методов: цепные коды, сигнатуры, аппроксимацию многоугольниками.

Цепные коды применяются для представления границы в виде последовательности отрезков прямых линий определ?нной длины и направления. В основе этого представления лежит 4- или 8- связная реш?тка. Длина каждого отрезка определяется разрешением реш?тки, а направления задаются выбранным кодом.

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

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

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

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

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

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

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

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

Большая и малая оси области полезны для определения ориентации объекта. Отношение длин этих осей, называемое эксцентриситетом области, также является важным дескриптором для описания формы области.

Периметром области называется длина ее границы. Хотя иногда периметр применяется как дескриптор, чаще он используется для определения меры компактности области, равной квадрату периметра, деленному на площадь.

Компактность является безразмерной величиной (и поэтому инвариантна к изменению масштаба) и минимальной для поверхности, имеющей форму диска.

Связной называется область, в которой любая пара точек может быть соединена кривой, полностью лежащей в этой области. Для множества связных областей (некоторые из них имеют отверстия) в качестве дескриптора полезно использовать число Эйлера, которое определяется как разность между числом связных областей и числом отверстий.

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

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

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

1.1 Характеристики сходства изображений

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

1. Цветовое сходство;

2. Текстурное сходство;

3. Сходство формы;

1.1.1 Характеристики цветового сходства

Характеристики цветового сходства часто выбираются «простыми». Они позволяют сравнить цветовое содержание одного изображения сцветовым содержанием другого. Способ поиска похожих изображений основан на сопоставлении цветовых гистограмм.

Меры расстояния на основе цветовой гистограммы должны предусматривать оценку сходства двух различных цветов. Например, в системе QBIC (Queryby Image Content, запрос по содержанию изображений) компании IBM, расстояние на основе цветовой гистограммы определено следующим образом:

, (1.5)

где h(I), h(Q) - гистограммы изображений;

I, Q, A - матрица сходства.

В матрице сходства элементы, значения которых близки к 1, соответствуют похожим цветам, близкие 0 соответствуют сильно различающимся цветам.

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

Характеристики сходства на основе цветового макета, в которых используется закрашенная сетка, требуют меры, которая учитывала бы содержание двух закрашенных сеток. Эта мера d должна обеспечивать сравнение каждой клетки сетки, указанной в запросе, соответствующей клеткой сетки сравниваемого изображения. Результаты сравнения всех клеток комбинируются для получения значения расстояния между изображениями:

, (1.6)

где - цвета клетки gв изображениях I,Qсоответственно.

Для представления цветов клеток могут использоваться различные способы:

1. Среднее значение цвета в пределах клетки сетки;

2. Среднее значение и среднеквадратическое отклонение цвета;

3. Многоразрядная цветовая гистограмма.

Мера расстояния между клетками сеток должна учитывать выбранный способ представления цвета и обеспечивать получение поддающихся интерпретации значений рассеяния. Например, если среднее значение представлено в виде тройки чисел (R,G,B), то очевидным (но не обязательно наилучшим) вариантом меры могла бы быть мера вида:

(1.7)

1.1.2 Характеристики текстурного сходства

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

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

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

1.1.3 Характеристики сходства формы

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

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

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

1.2 Дескриптор SURF

Дескриптор SURF (Speededup Robust Features) относится к числу тех дескрипторов, которые одновременно выполняют поиск особых точек и строят их описание, инвариантное к изменению масштаба и вращения. Кроме того, сам поиск ключевых точек обладает инвариантностью в том смысле, что повернутый объект сцены имеет тот же набор особых точек, что и образец.

Определение особых точек на изображении выполняется на основании матрицы Гессе (FAST-Hessiandetector,). Использование Гессиана обеспечивает инвариантность относительно преобразования типа "поворот", но не инвариантность относительно изменения масштаба. Поэтому SURF применяет фильтры разного масштаба для вычисления Гессиана. Предположим, что исходное изображение задается матрицей интенсивностей I, текущий рассматриваемый пиксель обозначим через X=(x,y), а у - масштаб фильтра. Тогда матрица Гессе имеет вид:

, (1.8)

где,, - свертки аппроксимации второй производной Гауссова ядра изображением I.

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

Далее для каждой найденной особой точки вычисляется ориентация - преобладающее направление перепада яркости. Понятие ориентации близко к понятию направления градиента, но для определения ориентации особой точки применяется фильтр Хаара.

На основании имеющейся информации выполняется построение дескрипторов для каждой особой точки:

· Вокруг точки строится квадратная окрестность размером20s, где s - масштаб, на котором получено максимальное значение детерминанта матрицы Гесса.

· Полученная квадратная область разбивается на блоки, в результате область будет разбита на 4x4 региона.

· Для каждого блока вычисляются более простые признаки. Как следствие, получается вектор, содержащий 4 компоненты: 2 - это суммарный градиент по квадранту, 2 - сумма модулей точечных градиентов.

· Дескриптор формируется в результате склеивания взвешенных описаний градиента для 16 квадрантов вокруг особой точки. Элементы дескриптора взвешиваются на коэффициенты Гауссова ядра. Веса необходимы для большей устойчивости к шумам в удаленных точках.

· Дополнительно к дескриптору заносится след матрицы Гессе. Эти компоненты необходимы, чтобы различать темные и светлые пятна. Для светлых точек на темном фоне след отрицателен, для темных точек на светлом фоне - положителен.

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

1.3 Дескриптор GLOH

Дескриптор GLOH (Gradientlocation-orientationhistogram) является модификацией SIFT-дескриптора, который построен с целью повышения надежности. По факту вычисляется SIFT дескриптор, но используется полярная сетка разбиения окрестности на бины: 3 радиальных блока с радиусами 6, 11 и 15 пикселей и 8 секторов. В результате получается вектор, содержащий 272 компоненты, который проецируется в пространство размерности 128 посредством использования анализа главных компонент (PCA).



Рис.1.5 - Полярная сетка разбиения на бины

1.4 Дескриптор DAISY

Детектор DAISY изначально вводится для решения задачи сопоставления изображений (matching) в случае значительных внешних изменений, т.е. данный дескриптор в отличие от ранее рассмотренных работает на плотном множестве пикселей всего изображения. При этом авторы DAISY в работе показали, что дескриптор работает в 66 раз быстрее, чем SIFT, запущенный на плотном множестве пикселей. В DAISY использованы идеи построения SIFT и GLOH дескрипторов. Аналогично GLOH выбирается круговая окрестность особой точки, при этом бины представляются не частичными секторами, а окружностями.

Рис.1.6 - Сетка построения бинов для центрального пикселя

Для каждого такого бина выполняется та же последовательность действий, что и в алгоритме SIFT, но взвешенная сумма магнитуд градиентов заменяется сверткой исходного изображения с производными Гауссова фильтра, взятыми по 8 направлениям. Авторы показали, что построенный дескриптор обладает инвариантностью, как и SIFT, и GLOH, при этом для решения задачи сопоставления (matching) в случае, когда все пиксели считаются особыми, требует меньших вычислительных затрат.

1.5 Дескриптор BRIEF

Цель создания BRIEF-дескриптора (Binary Robust Independent Elementary Features) состояла в том, чтобы обеспечить распознавание одинаковых участков изображения, которые были сняты с разных точек зрения. При этом ставилась задача максимально уменьшить количество выполняемых вычислений. Алгоритм распознавания сводится к построению случайного леса (randomize classification trees) или наивного Байесовского классификатора на некотором тренировочном множестве изображений и последующей классификации участков тестовых изображений. В упрощенном варианте может использоваться метод ближайшего соседа для поиска наиболее похожего патча в тренировочной выборке. Небольшое количество операций обеспечивается за счет представления вектора признаков в виде бинарной строки, а как следствие, использования в качестве меры сходства расстоянии Хэмминга.

Схема построения векторов признаков достаточно простая. Изображение разбивается на патчи (отдельные перекрывающиеся участки). Допустим патч P имеет размеры SxS пикселей. Из патча выбирается некоторым образом множество пар пикселей для которых строится набор бинарных тестов:

, (1.9)

где I(X) - интенсивность пикселя X.

Для каждого патча выбирается множество, содержащеепар точек, которые однозначно определяют набор бинарных текстов. Далее на основании этих текстов строится бинарная строка:

(1.10)

1.6 Дескриптор SIFT

Алгоритм SIFT (Scale-invariant feature transform) был предложен Девидом Лоу в 1999 году. Он позволяет сравнивать изображения, подвергнутые таким трансформациям как изменение масштаба, смещение объекта на сцене, повороты камеры или объекта. Алгоритм работает с чёрно-белыми изображениями.

Алгоритм SIFT достаточно популярный и часто используемый, поэтому существуют многочисленные реализации этого алгоритма. Реализация алгоритма SIFT входит в состав таких библиотек компьютерного зрения как VLFeat и OpenCV. Однако они содержат версии алгоритма с различными доработками.

1.6.1 Построение пирамид гауссиан

Основным моментом в нахождении особых точек изображения является построение пирамиды разностей гауссиан, которая строится следующим образом:

1. Выбираются числа такие что

2. Из исходного изображения формируются s изображений ,такие что размер в два раза меньше размера

3. К исходному изображению применяется функция Гауссова размытия (фильтр Гаусса) с разными радиусами :

(1.11)

(1.12)

где - изображение, .

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

(1.13)

5. Формируется hпирамид разностей гауссианов:

(1.14)

Рис.1.7 - Иллюстрация процесса построения пирамиды гауссиан

1.6.2 Определение экстремумов

После построения пирамид разностей необходимо найти список особых (ключевых) точек-кандидатов. Для этого необходимо сравнить точку с 26 соседями: 8 точек на её уровне в пирамиде гауссиан и по 9 точек на предыдущем и следующих уровнях пирамиды. Если точка является минимум или максимумом, то она включается в список точек-кандидатов.

Рис.1.8 - Положение точки предполагаемого экстремума

Далее необходимо уточнить положение экстремума. Это делается с помощью многочлена Тейлора второго порядка, взятого в точке вычисленного экстремума:

, (1.15)

где - функция ;

- вектор смещения относительно точки разложения

Продифференцировав и приравняв к нулю, в итоге получим смещение точки вычисленного экстремума, относительно точного:

(1.16)

1.6.3 Фильтрация особых точек

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

Сначала считается значение функции D(Z) и если оно мало, то такая точка отбрасывается. Эта проверка отсеивает точки с низким уровнем контраста.

(1.17)

Далее необходимо отфильтровать точки, лежащие на границе объектов.

Для этого считается матрица:

(1.18)

Пусть Tr(H) - след матрицы, - определитель:

(1.19)

(1.20)

Пусть , тогда

(1.21)

Точка продолжает рассматриваться дальше, если:

 (1.22)

1.6.4 Ориентация ключевых точек

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

, (1.23)

, (1.24)

где m(x,y) - величина градиента;

- направление градиента.

Конечное направление ключевой точки находится из гистограммы направлений ключевых точек окна. В гистограмме 36 компонент, которые равномерно покрывают весь интервал в 360 градусов. Каждая точка окна (x,y) вносит вклад, равный в ту компоненту гистограммы, которая покрывает промежуток, содержащий направление градиента .

Направление ключевой точки лежит в промежутке, покрываемом максимальной компонентой гистограммы. Если в гистограмме есть ещё компоненты с величинами не меньше 80% от максимальной величины, то они считаются дополнительными направлениями ключевой точки

1.6.5 Построение дескрипторов

На этой стадии алгоритма вычисляются значения дескрипторов. Перед вычислением дескриптора выбирается, сколько точек вокруг ключевойбудетучитываться (чаще всего учитываются 16 точек). Далее для каждой точки строится гистограмма, аналогичная гистограмме ориентации ключевой точки, но с меньшим числом компонент (8 компонент вместо 36). Далее формируется вектор из 128 (16 гистограмм с восемью компонентами в каждой) чисел. Этот вектор и есть дескриптор SIFT.

Рис.1.9 - Ключевая точка с гистограммами 16 точек

1.6.6 Хранение и обработка дескрипторов SIFT

Так как дескриптор представляет собой массив большой размерности и для изображения формируется несколько сотен или тысяч дескрипторов, то требуются специальные алгоритмы и структуры данных для хранения и обработки дескрипторов. Часто используются такие структуры данных, как K-мерное дерево, R*-дерево, SR- дерево.

...