Характеристики сходства изображений. Сетка построения бинов для центрального пикселя. Хранение и обработка дескрипторов SIFT. Сравнивание дескрипторов SIFT для разных изображений. Преимущества и недостатки метода SIFT. Обзор существующих детекторов.
Аннотация к работе
Федеральное государственное бюджетное образовательное учреждение высшего образования «Поволжский государственный университет телекоммуникаций и информатики» Направление (специальность) Информатика и вычислительная техника Построение SIFT дескрипторов и задача сопоставления изображений Утверждаю зав.кафедрой, д.т.н., профессор Н.И.Построение SIFT дескрипторов и задача сопоставления изображений Проанализировать основные типы детекторов, использующие дескрипторы для анализа границ объектов на изображении 3.Изучить характеристики сходства изображений, на основе которых осуществляется построение и сопоставление дескрипторов Провести моделирование сопоставления изображений на основе одного проанализированного дескриптора Обзор основных типов детекторов, использующих дескрипторы для поиска и анализа границ объектов на изображенииВ первом разделе выполняется исследование основных типов дескрипторов изображений, характеристик сходства изображений и детекторов границ объектов на изображении. В общем случае это выглядит следующим образом: для каждой точки изображения вычисляется значение определенной функции, на основании этих значений можно приписать изображению определенную характеристику, тогда задача сравнения изображений сводится к задаче сравнения таких характеристик. Нахождение соответствий на изображениях - одна из основных проблем в машинном зрении, основанная на выявлении и сопоставлении точечных особенностей изображений. При решении данной задачи важно обнаружить сходство отдельных частей изображений, поэтому для данных целей обычно применяются локальные дескрипторы, описывающие особенности областей изображений. Главный вопрос - каким образом определять, какая ключевая точка одного изображения соответствует ключевой точке другого изображения.Вычисляется среднее значение градиента множества : Дескриптор состоит из бинарной строки длиной 512, заполненной результатами проведенных тестов в множестве : , (1.31) где - интенсивность окрестности радиуса точки ,-угол направления градиента g. Применение нелинейного коэффициента масштабирования позволяет увеличить скорость нахождения нужной особой точки по сравнению с Гауссовой пирамидой: Вычисление данного коэффициента основано на изменении яркости изображения при масштабировании. С помощью такого подхода ищем такие точки в октаве, значение фильтра которых выше заданного порога и является наибольшим из окрестности точки 3 ? 3 пикселей. Далее, для каждой точки из потенциальных максимумов сравнивается ее значение относительно результатов в соседних октавах ?? 1 и ?? - 1 в окне размером соответственно. Инвариантность к масштабу получена с помощью выбора размера окна дескриптора в зависимости от размера октавы???? в которой найдена его особая точка.Построение SIFT дескрипторов и задача сопоставления изображений Более того, это приводит к неопределенности в связи с повторяющимися случаями серых значений и изза шума на изображениях. Участок образа, вырезанный из одного изображения, так называемого шаблона, ищется во втором изображении. Далее данный шаблон проходит процедуру сравнения с участками такого же размера на втором изображении. На уровне лучшей геометрической разрешающей способности приближенные значения рассчитываемых параметров являются достаточно хорошими для позиционирования поиска окна с такой точностью, что методы сопоставления изображений, в результате точностью до субпикселя могут быть применены.В данной бакалаврской работе был произведен анализ предметной области, алгоритмов выделения особых точек, проанализированы и промоделирован алгоритм, необходимый для формирования панорамного изображения. Ограничением смоделированного алгоритма является обработка не более двух изображений (при большем числе изображений проявляется эффект дисторсии). Например, при поиске аффинных преобразований (или фундаментальной матрицы) по двум изображениям кирпичной стены может быть не найдено решения изза того, что стена состоит из повторяющихся объектов, которые делают похожими между собой дескрипторы разных ключевых точек.
Введение
При решении задачи сравнения изображений важнейшую роль играет иерархический анализ "первичных" особенностей изображений - так называемых "характерных черт". Такие "характерные черты" могут быть использованы для сравнения текущего и эталонного изображений в большом числе методов, например, при иерархической корреляционной обработке, методах голосования, или объемных схемах сравнения. При этом в качестве особенностей изображения используются особые точки, линии, области и структуры (группы особенностей).
Основной задачей, связанной с сопоставлением изображений является выбор сопоставляемого образа (элементарного по сравнению с примитивами других изображений), а также критерия сходства (количественная мера оценки соответствия образов). Совпадение "пиксель на пиксель" на всей площади перекрывающихся изображений требует очень большого объема вычислений. Более того, это приводит к неопределенности в связи с повторяющимися случаями серых значений и изза шума на изображениях. Таким образом, в целом сопоставление образов принадлежит к группе сложно решаемых задач. Она не отвечает критериям существования и уникальности решений, что является стабильным по отношению к малым вариациям в исходных данных. Для того, чтобы привести сопоставление образов к легко решаемым задачам, таким как соответствующие образы, критерий сходства, геометрические ограничения и предположения должны необходимо указать, что пространство всех возможных решений будет ограниченным.
Объектом исследований является цифровая обработка изображений.
Предметом исследований являются алгоритмы и методы построения дескрипторов изображений и их дальнейшее сопоставление.
Целью данной дипломной работы является моделирование алгоритма поиска и построения дескрипторов изображения 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). Если яркость в точке больше, чем яркость в точке , то i-я компонента дескриптора принимает значение 1, в противном случае она становится равной нулю. Фрагмент, по которому вычисляются дескрипторы, предварительно сглаживается. BRIEF-дескрипторы чрезвычайно просты в вычислении, поскольку их значения равны результату сравнения двух чисел. Они также очень компактны, поскольку результат элементарного теста - это число 0 или 1, то есть один бит. В стандартной реализации для построения одного BRIEF-дескриптора требуется выполнить 256 сравнений, что дает итоговую длину 64 байта. Это очень мало, учитывая, что SIFT-дескриптор состоит из 128 действительных чисел, то есть занимает как минимум 512 байтов. Наконец, сравнение BRIEF-дескрипторов занимает очень мало времени, поскольку сводится к вычислению расстояния Хэмминга между двумя последовательностями битов; эта элементарная операция выполняется чрезвычайно быстро на любом современном процессоре. Сами по себе дескрипторы BRIEF не инвариантны к повороту. Однако такой инвариантности можно добиться, если предварительно повернуть фрагмент вокруг точки интереса на угол, соответствующий, например, доминирующему направлению градиента яркости, как это делается для дескрипторов SIFT и SURF. Точно так же можно достичь инвариантности к другим ракурсным искажениям.
С развитием электронных вычислительных средств и средств регистрации зрительной информации все больше начали использоваться информация не только о форме объекта, но и о характеристиках ограничительной области объекта: текстура, скелет объекта и т.п. Область, которая представляет интерес, может быть описана формой ее границы или путем задания ее характеристик.
Дескрипторы границы включают в себя ряд наиболее распространенных методов: цепные коды, сигнатуры, аппроксимацию многоугольниками.
Цепные коды применяются для представления границы в виде последовательности отрезков прямых линий определенной длины и направления. В основе этого представления лежит 4- или 8- связная решетка. Длина каждого отрезка определяется разрешением решетки, а направления задаются выбранным кодом.
Недостатками метода является то, что получаемая цепочка кодов оказывается слишком длинной и любые малые возмущения вдоль границы области, вызванные наличием шума или и несовершенством алгоритма сегментации, приводят к изменениям кодовой последовательности, которые не связаны с общей формой границы.
Сигнатура - описание границы объекта с помощью одномерной функции, которая может строиться с различными способами. Наиболее простым способом создания сигнатур является построение отрезка из центра к границе как функции угла. Такие сигнатуры являются зависимыми от периметра области и начальной точки отрезка. Применение такого дескриптора границы возможно только при его нормировании. Целесообразность применения данного дескриптора заключается в получаемых выходных данных (несет информацию об основных характеристиках формы границы) - одномерные функции, которые проще обрабатывать при описании объекта.
Другим видом разложения границы объекта в дескриптор является представление ее в виде многоугольников - аппроксимация многоугольниками. При использовании цифровой обработки изображения границу объекта можно аппроксимировать с произвольной точностью. Для замкнутой границы аппроксимация многоугольниками является точной, тогда когда число сегментов в многоугольнике равно числу точек границы, так что каждая пара соседних точек определяет сегмент многоугольника.
Часто оказывается полезным разбиение границы на сегменты. При такой декомпозиции уменьшается сложность границы и тем самым упрощается процесс описания. Такой подход особенно привлекателен, когда границы содержат одну или несколько хорошо выраженных вогнутостей, несущих информацию о форме объекта. В этом случаи мощным инструментом для устойчивой декомпозиции границы является использование выпуклой оболочки области, находящейся внутри границы.
Среди структурных методов получения дескрипторов, следует отметить метод, основанный на получении описания области в виде графа - скелета области, т.е. схема области. Для получения скелета применяется большое количество, так называемых прореживающих (или же сокращающих) алгоритмов.
Методы скелетизации дают положительные результаты при работе с бинарными изображениями сцены, однако применение их для обработки градационных изображений ограниченно погрешностями при бинаризации области объекта.
Существующие системы технического зрения основываются на довольно простых дескрипторах области, что делает их более привлекательными с вычислительной точки зрения. Как следует ожидать, применение этих дескрипторов ограничено ситуациями, в которых представляющие интерес объекты различаются настолько, что для их идентификации достаточно несколько основных дескрипторов.
Площадь области определяется как число пикселей, содержащихся в пределах ее границы. Этот дескриптор полезен при сборе информации о взаимном расположении и форме объектов, от которых камера располагается приблизительно на одном и том же расстоянии. Типичным примером может служить распознавание системой технического зрения объектов, движущихся по конвейеру.
Большая и малая оси области полезны для определения ориентации объекта. Отношение длин этих осей, называемое эксцентриситетом области, также является важным дескриптором для описания формы области.
Периметром области называется длина ее границы. Хотя иногда периметр применяется как дескриптор, чаще он используется для определения меры компактности области, равной квадрату периметра, деленному на площадь.
Компактность является безразмерной величиной (и поэтому инвариантна к изменению масштаба) и минимальной для поверхности, имеющей форму диска.
Связной называется область, в которой любая пара точек может быть соединена кривой, полностью лежащей в этой области. Для множества связных областей (некоторые из них имеют отверстия) в качестве дескриптора полезно использовать число Эйлера, которое определяется как разность между числом связных областей и числом отверстий.
Для глобального описания областей на плоскости изображения часто оказываются полезными их топологические свойства. В общих чертах, топология изучает свойства фигур, на которые не влияют любые их деформации, если не происходит разрывов и склеек.
Если объекты представляют собой подобные по начертанию границы, но разные по характеру поверхности, то возможно применение дескрипторов текстуры. Дескриптор текстуры формального определения не получил - это, скорее всего, интуитивное описание поверхности (шероховатость, однородность, регулярность). На практике применяются два подхода для получения дескриптора текстуры объекта: структурный и статистический. Структурные методы позволяют установить взаимное расположение элементарных частей образа, таких как, описание текстуры, основанной на регулярном расположении параллельных линий. Статистические методы дают такие характеристики, как однородность, шероховатость, зернистость,узор и т.п. Состоит в использовании статистических характеристик, определяемых по гистограмме яркости всего изображения или его области.
Наиболее простой и получивший широкое применение в системах, связанных с обработкой объектов на основе текстуры, является метод, использующий моменты гистограммы интенсивности области объекта. Данный метод применяется к дискретизированному изображению, которое представляется интенсивностью отдельной точки изображения - пикселем. На первом этапе производится нахождение гистограммы интенсивности области объекта. На втором этапе производится вычисление моментов (до шестой степени) относительно среднего значения интенсивности области. Дескриптор, построенный по данному методу, включает в себя: второй момент - дисперсию интенсивности области объекта, которая представляет меру контраста интенсивности и применяется в дальнейшем для описания однородности поверхности объекта; третий момент, который представляет собой меру асимметрии гистограммы, а четвертый момент является мерой ее относительной ровности. Пятые и шестые моменты представляют скорее практический интерес, поскольку их не так легко связать с формой гистограммы, но они дают определенную количественную информацию о виде текстуры объекта.
Для определения сходства между изображениями обычно применяется некоторая мера расстояния или характеристики, с помощью которых можно получить численную оценку сходства изображений. Характеристики сходства изображений можно разделить на несколько основных групп.
1. Цветовое сходство;
2. Текстурное сходство;
3. Сходство формы;
Характеристики цветового сходства часто выбираются «простыми». Они позволяют сравнить цветовое содержание одного изображения сцветовым содержанием другого. Способ поиска похожих изображений основан на сопоставлении цветовых гистограмм.
Меры расстояния на основе цветовой гистограммы должны предусматривать оценку сходства двух различных цветов. Например, в системе 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)
Характеристики текстурного сходства несколько сложнее характеристик цветового сходства. Изображения, близкие по текстуре, должны иметь схожее пространственное распределение цветов, но при этом значение цветов может не совпадать.
Один из наиболее распространенных методов - построение вектора текстурного описания. Так называется вектор с числовыми компонентами, соответствующими обобщенным параметрам текстуры заданного изображения или некоторой области изображения. Вектор текстурного описания может использоваться относительного текстуры целого изображения, но тогда хорошие результаты будут достигнуты только при описании изображений с однородной текстурой. Для изображений с неоднородной текстурой, векторы вычисляются для каждого пиксела по небольшой окрестности этого пиксела. Затем пикселы группируются с помощью алгоритма кластеризации, который назначает уникальную метку каждой новой обнаруженной текстурной категории.
Цвет и текстура могут служить глобальными атрибутами изображения. Меры расстояния на основе цвета и текстуры предназначены для определения, содержит ли некоторое изображение заданный цвет или текстуру и расположены ли области этого цвета или текстуры в тех же местах, что и на изображении в запросе.
Форма в свою очередь не является атрибутом изображения. Понятие «форма» применимо к некоторой области изображения. Для выделения этих областей применяют специальные методы сегментации изображения, а также гистограммы формы. При использовании характеристик формы необходимы дополнительные (по сравнению с характеристиками цвета и текстуры) операции обработки, так как перед вычислением характеристик сходства формы требуется выполнить идентификацию областей. Часто это делается вручную, но в некоторых случаях удается применять автоматическую сегментацию. Сегментация, сама по себе, представляет важную и еще не до конца решенную задачу, решение которой необходимо для широкого распространения методов поиска на основе формы.
Методы распознания объектов по форме их двумерных образов играют важную роль в анализе изображений. Сравнение формы двух областей может быть выполнено с учетом глобальных свойств формы с помощью различных методов статистического распознавания образов. При сопоставлении формы областей могут также использоваться структурные методы, применительно к которым ф
Вывод
Авторы [11] приводят результаты экспериментов (качества распознавания) при выборе пар точек согласно закону равномерного распределения в патче, а также нормального распределения с разными значениями математического ожидания и среднеквадратичного отклонения. Отметим, что при одинаковых условиях проведения экспериментов на некоторых тестовых изображениях точность детектирования с помощью SIFT почти в 1.5 раза выше, чем с использованием SURF-дескрипторов.
SIFT дескрипторы не лишены недостатков. Не все полученные точки и их дескрипторы будут отвечать предъявляемым требованиям. Это будет сказываться на дальнейшем решении задачи сопоставления изображений. В некоторых случаях решение может быть не найдено. Например, при поиске аффинных преобразований по двум изображениям кирпичной стены может быть не найдено решения изза того, что стена состоит из повторяющихся объектов (кирпичей), которые делают похожими между собой дескрипторы разных ключевых точек. Несмотря на это обстоятельство, данные дескрипторы хорошо работают во многих практически важных случаях.
2. Построение SIFT дескрипторов и задача сопоставления изображений
Основной задачей, связанной с сопоставлением изображений является выбор сопоставляемого образа (элементарного по сравнению с примитивами других изображений), а также критерия сходства (количественная мера оценки соответствия образов). Совпадение "пиксель на пиксель" на всей площади перекрывающихся изображений требует очень большого объема вычислений. Более того, это приводит к неопределенности в связи с повторяющимися случаями серых значений и изза шума на изображениях. Таким образом, в целом сопоставление образов принадлежит к группе сложно решаемых задач. Она не отвечает критериям существования и уникальности решений, что является стабильным по отношению к малым вариациям в исходных данных. Для того, чтобы привести сопоставление образов к легко решаемым задачам, таким как соответствующие образы, критерий сходства, геометрические ограничения и предположения должны необходимо указать, что пространство всех возможных решений будет ограниченным. В таблице 1 приводится обзор трех основных методов сопоставления изображений, которые были разработаны и используются в фотограмметрии и компьютерном зрении.
Таблица 1
Методы сопоставления изображений
Метод сопоставления Критерий соответствия Сопоставляемый образ
Площадной Корреляция, метод наименьших квадратов Серые значения
Функциональный Весовая функция Значение точек, краев, областей
Реляционный Весовая функция Символическое описание изображения
Серые значения сопоставляемых образов в площадных методах. Совпадение в один пиксель приводит к двойственности решения. Поэтому используются серые значения нескольких соседних пикселей. Участок образа, вырезанный из одного изображения, так называемого шаблона, ищется во втором изображении. Шаблон состоит из m x n пикселей, в основном м = n. Позиция шаблон задается центральным пикселем, поэтому m и n являются нечетными номерами. Далее данный шаблон проходит процедуру сравнения с участками такого же размера на втором изображении. Примерное положение соответствующей точки на втором изображении, как правило, может быть получено (например, при известном приближенном значении элементов ориентирования двух перекрывающихся изображений). Ограниченный участок сравнения называется районом поиска или окном. Значение критерия подобия рассчитывается для каждой позиции шаблона в области поиска. В зависимости от степени критерия подобия, соответствующей точкой в центре шаблона, как правило, будет точка, когда достигаются максимальные или минимальные значения критерия подобия. В фотограмметрии, кросс-корреляции и методы наименьших квадратов являются являются наиболее распространенными для площадного алгоритма. Элементы взаимного ориентирования изображений были применены не только при регистрации MR (магнитный резонанс) или КТ (компьютерная томография) изображений, в генной инженерной, но также и в фотограмметрии. Независимо от того, какой выбран критерий соответствия, необходимо рассмотреть несколько вопросов.
2.1 Размер и расположение шаблона
Задача подбора шаблона изображения, более соответствующего требованиям уникальности при сопоставлении изображений решена. С другой стороны, геометрические искажения, вызванных рельефом и различиями ориентации изображений будут влиять на соответствие больших шаблонов. Требование уникальности не может быть достигнуто в районах с повторяющимся узором или рисунком или имеющих низкий контраст и структуру. Вода и песок в районах являются типичными примерами, для которых методы сопоставления изображения неэффективны. Участки, скрытых высокими объектами также должны быть исключены. Площадные методы с низкой эффективностью находят соответственные точки на участках, если хотя бы один из них встречается в изображении. Аналогичным образом, соответствие точек на транспортных средствах или в тени приводит к неправильному определению и возникновению параллаксов. В высокогорных районах проекция такого участка не является геометрической. Для того, чтобы получить приемлемый результат, размер шаблона должен быть небольшими или нужно изменить его форму с учетом геометрических искажений (например, трапециевидное окно). Одна из возможностей исключения нежелательных участков или участков, где нужно найти соответствующее изображение является о использование баз данных ГИС. Этот подход можно применять также и для DTM-генерации.
2.2 Размер и расположение поискового окна
Для того, чтобы избежать несоответствий, позиция поиска окна должна быть определена достаточно точно на участке с учетом соответствия. Аппроксимация расчетных параметров (например, параметры ориентирования, DTM) и иерархический подход, как правило, используется для этой цели. Иерархический подход или критерий грубых ошибок означает, что соответствующий процесс начинается на более высоких уровнях пирамиды изображение (уменьшение размера пикселя), где мелкие детали подавляются. Параметры рассчитываются из измерений на более высокий уровень пирамиды изображения затем используются в качестве начальной точки соответствия на более низком уровне. На уровне лучшей геометрической разрешающей способности приближенные значения рассчитываемых параметров являются достаточно хорошими для позиционирования поиска окна с такой точностью, что методы сопоставления изображений, в результате точностью до субпикселя могут быть применены.
При работе со стереопарой, в качестве дополнительных геометрических ограничений могут быть применены эпиполярные линии. Рис.2.1 показывает концепцию проведения эпиполярной линии ограничения. Эпиполярные линии являются линиями пересечения эпиполярной плоскости один и плоскости изображения. Эпиполярная плоскость задается проекцией центров О1, O2 и образом точки Р. Поэтому область соответствия точек P" и С"" должна лежать на пересечении соответствующих эпиполярных линий E" и E"". Для упрещения сопоставления вдоль эпиполярных линий, изображения могут быть преобразованы в так называемые нормированные изображения т.е. все эпиполярные линии изображения параллельны.
Рис.2.1 - Принцип эпиполярной геометрии. Эпиполярная плоскость задается проекцией центров O1 и O2, и образом точки Р. Эпиполярные линии E" и E"" являются пересечением эпиполярной плоскости с плоскостью изображения
Размер поискового окна зависит от того, насколько точно оно раположено и по геометрической деформации изза рельефа и ориентации изображения.
2.3 Принятие критериев для степени подобия
Исключение несоответствия является одной из задач, связанных с сопоставлением изображений. Одним из возможных вариантов избегания некоторых несоответствий при сопоставлении является установление пороговых значений для степени подобия. Пороговые значения редко могут быть установлены для всех случаев. Хотя некоторые значения по умолчанию, приведены в литературе, случается, что сопоставление не будет успешным, несмотря на превышение порога, и наоборот. После того, как «лучшая позиция» найдена, должна быть выполнена оценка точности и достоверности найденного соответствия. В дополнение к ограничению степени подобия, геометрические ограничения или корректировка как надежные методы используются в дальнейших расчетах, с тем чтобы исключить ложные сопоставления.
2.3.1 Корреляция
Нормализованный кросс-коэффициент корреляции R используется в фотограмметрии как одна из общих мер сходства. Он рассчитывается по формуле: (2.1) где r- нормализованный кросс-коэффициент корреляции;
, - стандартные отклонения серых значений в шаблоне и искомом участке изображения;
- ковариация серых значений на участке изображения;
, - серые значения для шаблона и искомой области изображения;
, -средние из средних значений;
R, C- число строк и столбцов участка изображения.
Если шаблон и искомый участок изображений представлены векторами VT, VS из 1XRC серых значений, уменьшая их средние значения GTANDGS, , коэффициент корреляции может быть вычислен как R = cos , где - угол между векторами, как показано на рис .2.2.
Значения нормализованного коэффициента корреляции находятся в диапазоне -1 0, где соответствует шкале фактора и РТ на переход между серыми значениями в и . Значения близки к 0 указывать на различие и значение -1 получается, когда негатив и позитив изображения совпадают. Таким образом, при сопоставлении изображений требуется, чтобы соответствующие положительные значения были близки к 1.
Шаблон передвигается пиксель за пикселем за окном поиска, а коэффициент корреляции рассчитывается в каждом положении. Позиция, когда коэффициент корреляции достигает своего наивысшего значения, является позицией лучшего соответствия.
Рис.2.3 - Принцип сопоставления изображений, основанный на поиске максимума коэффициент корреляции Р
На графике в середине показывает значения коэффициента корреляции, вычисленные для 13 х 13 позиций шаблона в области поиска. Коэффициент корреляции достигает своего максимума 0.79 на позиции строки =30 и столбца =32.
Коэффициент корреляции не сообщает о точности найденных позиций для наиболее подходящей. Ряд исследований свидетельствует о связи между решительным сдвигом от центра в окне поиска, шумом/сигналом, а также размером шаблона. Этот теоретический результат не был получен в практических расчетах до сих пор. Тем не менее, он ясно показывает, что надежность окончательной позиции из наиболее подходящих зависит от радиометрических свойств участков, которые изменяются в силу различных значений освещения и угла обзора, временными изменениями, или проекции сопоставляемых изображений. Тип почвенно-растительного покрова и рельефа также играет важную роль.
Стандарт отклонений серых значений и энтропии меры контраста и количества информации на участке изображения, могут быть использованы для оценки пригодности выбранного шаблона для сравнения. Автокорреляционная функция может быть использован для той же цели. В автоматизированных процедурах применяются свойства или края операторов. В следующем сопоставлении принимаются только те результаты, когда максимальный коэффициент корреляции превышает данный порог. Если в процессах с хорошо определены объекты измерения принимаются исходных точек отсчета или искусственных задач, то пороговый метод является успешным методом для устранения или, по крайней мере, существенного сокращения количества несоответствий. То есть.пороговые значения в 0,7 оказались пригодны для автоматического измерения исходных точек отсчета. В случае сетки крестов или сигнальных контрольных точек, когда фон не является однородным, порог должен быть несколько сокращен, например, до 0,5. Аналогичная ситуация с природными контрольными точками, хотя для практического применения значения порога в 0,7 зачастую является стандартным. В общем, установление порога для коэффициента корреляции не означает, что все несоответствия устранены. При работе с естественными целями, некоторые хорошие соответствия имеют низкий, а некоторые ложные соответствия имеют высокий коэффициент корреляции. Установление порога для ряда успешных соответствий, исключается из дальнейших расчетов, хотя некоторые несоответствия остаются. Поэтому алгоритмы для вычисления параметров ориентации или DTM поколения от соответствующих точек должны содержать стандарты для устранения несоответствий.
Если наиболее подходящее положение должно определяться с точностью субпикселя, то значения коэффициента корреляции вокруг своего максимального аппроксимируются непрерывной функцией, например, многочленом, параметры которого определяются методом наименьших квадратов. Позиция максимума полинома соответствует позиции наиболее подходящего в субпиксели диапазона. Основываясь на стандартах отклонений полиномиальных коэффициентов, полученных методом наименьших квадратов, можно вычислить стандартное отклонение улучшения позиций в наиболее подходящую. В случае поиска вдоль эпиполярной линии решение ограничено корреляционной кривой.
2.4 Построение дескрипторов
Дескриптором может выступать любой объект, но обычно дескриптором является некая информация об окрестности ключевой точки. Такой выбор сделан в силу нескольких причин: на маленькие области меньшее влияние оказывают эффекты искажений, некоторые изменения (изменение положения объекта на картинке, изменение сцены, перекрытие одного объекта другим, поворот) могут не повлиять на дескриптор вовсе.
В методе SIFT дескриптором является вектор. Как и направление ключевой точки, дескриптор вычисляется на гауссиане, ближайшем по масштабу к ключевой точке, и исходя из градиентов в некотором окне ключевой точки. Перед вычислением дескриптора это окно поворачивают на угол направления ключевой точки, чем и достигается инвариантность относительно поворота.
Рис.2.4 - Часть изображения и полученный на ее основе дескриптор
Пиксели на рисунке слева берутся из квадратного окна дескриптора, которое в свою очередь поделено еще на четыре равных части. Стрелка в центре каждого пикселя обозначает градиент этого пикселя. Центр этого окна находится между пикселями. Его необходимо выбирать как можно ближе к точным координатам ключевой точки. Круг обозначает окно свертки с гауссовым ядром (аналогично окну для вычисления направления ключевой точки). Для этого ядра определяется sigma, равное половине ширины окна дескриптора. В дальнейшем значение каждой точки окна дескриптора будет домножаться на значение гауссова ядра в этой точке, как на весовой коэффициент.
Справа схематически изображен дескриптор особой точки, размерности 2x2x8. Первые две цифры в значении размерности - это количество регионов по горизонтали и вертикали. Те квадраты, которые охватывали некоторый регион пикселей на левом изображений, справа охватывают гистограммы, построенные на пикселях этих регионов. Соответственно, третья цифра в размерности дескриптора означает количество компонент гистограммы этих регионов. Гистограммы в регионах вычисляются так же, как и гистограмма направлений с тремя небольшими но: 1. Каждая гистограмма так же покрывает участок в 360 градусов, но делит его на 8 частей;
2. В качестве весового коэффициента берется значение гауссова ядра, общего для всего дескриптора (об этом уже говорилось);
3. В качестве еще одних весовых коэффициентов берутся коэффициенты трилинейной интерполяции.
Каждому градиенту в окне дескриптора можно приписать три вещественные координаты (x, y, n), где x - расстояние до градиента по горизонтали, y - расстояние по вертикали, n - расстояние до направления градиента в гистограмме (имеется ввиду соответствующая гистограмма дескриптора, в которую вносит вклад этот градиент). За точку отсчета принимается левый нижний угол окна дескриптора и начальное значение гистограммы. За единичные отрезки берутся размеры регионов по горизонтали и вертикали для x и y соответственно, и количество градусов в компоненте гистограммы для n. Коэффициент трилинейной интерполяции определяется для каждой координаты (x, y, n) градиента как 1-d, где d равно расстоянию от координаты градиента до середины того единичного промежутка в который эта координата попала. Каждое вхождение градиента в гистограмму умножается на все три весовых коэффициента трилинейной интерполяции.
Дескриптор ключевой точки состоит из всех полученных гистограмм. Размерность дескриптора на рисунке 32 компоненты (2x2x8).
Полученный дескриптор нормализуется, после чего все его компоненты, значение которых больше 0.2, урезаются до значения 0.2 и затем дескриптор нормализуется еще раз.
2.5 Алгоритм формирования панорамного изображения
Формирование панорамного изображения состоит из следующих этапов: 1) определение особых точек двух соседних изображений;
2) нахождение соответствий между особыми точками;
3) вычисление матрицы преобразования;
4) наложение изображений и получение итогового.
На первом этапе определяются инвариантные характеристики двух соседних изображений путем выделения особых точек и их дескрипторов. Особая точка m - это точка изображения, окрестность которой o(m) можно отличить от окрестности любой другой точки изображения o(n) в некоторой другой окрестности особой точки o2(m). Дескриптор - это идентификатор особой точки, выделяющий ее из остального множества особых точек.
Для обнаружения особых точек используется модифицированный алгоритм преобразования масштабно-инвариантных характеристик (англ. Scale Invariant FEATURETRANSFORM, SIFT). Данный алгоритм позволяет определять особые точки в виде капель (англ. blobs), так как они инвариантны ко всем преобразованиям (к аффинным преобразованиям, изменениям освещенности, положению камеры и к шуму). Капли - это структуры, описываемые координатами центра, масштабом и направлением. Подобного вида структуры являются самыми сложными, высокоуровневыми среди всех видов форм особых точек, и поэтому обеспечивают устойчивое их обнаружение. Алгоритм SIFT показывает лучшие результаты обнаружения особых точек по качеству четкости и контрастности изображения, чем другие алгоритмы обнаружения капель, и подходит к предметной области. Недостатком SIFT является его вычислительная сложность, что ограничивает его применение в режиме постобработки.
Алгоритм SIFT разделяется на 5 частей: 1) построение пирамиды гауссиан и их разностей. На этом шаге обеспечивается инвариантность к масштабированию;
2) определение экстремумов;
3) уточнение особых точек;
4) определение ориентаций особых точек (обеспечивается инвариантность к повороту);
5) построение дескрипторов (обеспечивается инвариантность к освещению, шуму, изменению положения камеры).
На первом шаге алгоритма SIFT строится масштабируемое пространство изображения - набор изображений, сглаженных фильтром Гаусса
(2.2) где (x,y) - координаты точки;
- радиус размытия.
По ним строится разность ГАУССИАНD( ) - попиксельное вычитание изображений в одной октаве с разным коэффициентом размытия. Октава - изображение в одном масштабе, размытое фильтром Гаусса (4 изображения в одной октаве). На этом шаге обеспечивается инвариантность к масштабированию. Затем определяются экстремумы, которые заносятся в список потенциальных особых точек.
Далее происходит уточнение особых точек, которое состоит из двух составляющих: 1) исключаются точки с малой контрастностью с помощью вычисления экстремума разности гауссиан. Разность гауссиан раскладывается многочленом Тейлора второго порядка, взятого в точке вычисленного экстремума;
2) исключаются граничные точки (точки, имеющие большой локальный изгиб вдоль границы и малый в перпендикулярном направлении).
Класс для поиска особых точек: int main(intargc, char** argv)
На конечном шаге алгоритма SIFT для окрестности особой точки вычисляются изменения яркостей точек, по которым строится дескриптор. Дескриптор - это вектор из 64 чисел, позволяет получить инвариантность относительно положения камеры. Затем дескриптор нормализуется, за счет чего достигается инвариантность относительно изменения освещения.
На следующем этапе формирования панорамного изображения между особыми точками находятся соответствия на основе полученных инвариантных дескрипторов. Для этого строится kd-дерево - это структура, предназначенная для хранения конечного множества точек k-мерного пространства. В результате выделяется набор пар взаимосвязанных особых точек.
Полученная последовательность может иметь ложные соответствия. Для удаления ложных соответствий применяется метод согласования случайных выборок RANSAC (англ. Random Sample Consensus) - итерационный, вероятностный метод, в котором определяется минимальная симметрическая погрешность между парами точек, после чего вычисляются коэффициенты матрицы перспективного преобразования H размерности 3х3 (матрица гомографии) методом прямого линейного преобразования DLT (англ. Direct Linear Transformation). Решается система линейных алгебраических уравнений, в результате определяются 8 коэффициентов (параметров DLT), показывающих связь между системами координат плоскостей двух изображений.
Заключительный этап наложения изображений состоит из следующих частей: 1. определяется размер итогового панорамного изображения;
2. первое изображение без изменения копируется в плоскость итогового;
3. второе изображение накладывается на плоскость первого с помощью полученной матрицы преобразования;
4. общая часть накладывается путем линейной интерполяции.
Рис.2.5 - Результат создания панорамного изображенияВ данной бакалаврской работе был произведен анализ предметной области, алгоритмов выделения особых точек, проанализированы и промоделирован алгоритм, необходимый для формирования панорамного изображения. Ограничением смоделированного алгоритма является обработка не более двух изображений (при большем числе изображений проявляется эффект дисторсии).
SIFT дескрипторы не лишены недостатков. Не все полученные точки и их дескрипторы будут отвечать предъявляемым требованиям. Естественно это будет сказываться на дальнейшем решении задачи сопоставления изображений. В некоторых случаях решение может быть не найдено, даже если оно существует. Например, при поиске аффинных преобразований (или фундаментальной матрицы) по двум изображениям кирпичной стены может быть не найдено решения изза того, что стена состоит из повторяющихся объектов, которые делают похожими между собой дескрипторы разных ключевых точек. Несмотря на это обстоятельство, данные дескрипторы хорошо работают во многих практически важных случаях.
К основным направлениям развития следует отнести: - модификацию алгоритмов для использования в многопроцессорных системах;
- формирование более двух изображений в панорамное.