В качестве алгоритма поиска близких дескрипторов используется алгоритм поиска ближайшего соседа. Под «близостью» дескрипторов понимается Евклидово расстояние между двумя дескрипторами.

1.6.7 Сравнивание дескрипторов SIFT для разных изображений

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

1.6.8 Преимущества и недостатки метода SIFT

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

К недостаткам метода можно причислить то, что метод обладает большой вычислительной сложностью: например, обработка изображений размером 1440х900 (при использовании разработанной реализации алгоритма SIFT) не может быть выполнена в реальном времени на обычном ПК.

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

Так же метод не работает корректно в следующих случаях:

· Условия освещения кардинально отличаются (например, день и ночь);

· Изображение имеет фрактальную или себе подобную структуру (например, кирпичная стена);

1.7 Обзор существующих детекторов

1.7.1 ORB

ORB представлен в 2011г. В его основе лежит комбинация таких алгоритмов как детектор FAST (Features from Accelerated Segment Test) и дескриптор BRIEF (Binary Robust Independent Elementary Features) с некоторыми улучшениями.

Для поиска угловых точек поочерёдно рассматриваются окрестности по 16 пикселей вокруг каждого пикселя p. Точка p считается подозрительной на особую, если существует N пикселей (в данной работе N=9) в её окружности длиной 16 пикселей, если все N ярче или темнее , где - яркость точки p, t -пороговая величина. При выполнении этого условия далее исследуется значения яркости на окружности под номерами 1, 5, 9, 13. Если для трех пикселей из четырех выполняется условие или , ?? = 1 … 4, тогда p считается особой точкой.

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

Рис.1.10 - Рассматриваемая окрестность точки p FAST детектора

сходство изображение пиксель дескриптор

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

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

Дескриптор направленный BRIEF. Данный дескриптор представляется в виде вектора длиной 256, состоящего из результатов бинарных тестов вокруг особой точки. В окрестности 31 Ч 31 пиксель сравниваются средние значения яркостей между ?? и ??, где ??, ?? - области 5 Ч 5 пикселей:

, (1.25)

где I - средняя яркость выбранной области.

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

Все ?? = 256 наборов и формируют матрицу ?? размерностью 2 Ч ??. Далее ?? с помощью матрицы поворота ориентируется в соответствии с углом ??:

(1.26)

А сам вектор дескриптора записывается как:

(1.27)

1.7.2 BRISK

Данный метод представлен в 2011г. Детектирование особых точек осуществляется с помощью FAST (FeaturesfromAcceleratedSegmentTest), а дескриптор BRIEF, но в их работу были внесены некоторые изменения.

Поиск особых точек. Для достижения инвариантности к масштабу, предлагается выбирать наилучшую особую точку с максимальным значением интенсивности в пирамиде, которая состоит из 4 октав и 4 внутренних октав , ?? = 0. . .3. Октавы формируются как сжатие оригинального изображения в 2 ?? раза. Внутренние октавы расположены между и и представлены в виде сжатой в раза. Поиск особых точек в октавах осуществляется детектором FAST.

Рис.1.11 - Пример поиска особой точки с максимальным значением S

Дескриптор BRISK. Область вокруг особой точки разбивается на 60 участков p.

(1.28)

Рис.1.12 - Область вычисления дескриптора

Множество разбивается на два подмножества:

(1.29)

(1.30)

Вычисляется среднее значение градиента множества:

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

, (1.31)

где - интенсивность окрестности радиусаточки ,

-угол направления градиента g.

1.7.3 AKAZE

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

Применение алгоритма FED - FastExplicitDiffusion на пирамидальной схеме позволяет построить нелинейную многомасштабную пирамиду. Применение нелинейного коэффициента масштабирования позволяет увеличить скорость нахождения нужной особой точки по сравнению с Гауссовой пирамидой:

Вычисление данного коэффициента основано на изменении яркости изображения при масштабировании.

Детектор. Для каждой октавыв пирамиде вычисляется определитель Гессиана:

, (1.32)

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

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

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

Первоначальный дескриптор LDB основывался на тех же принципах что и рассмотренный выше BRIEF, но к сравнениям яркостных показателей областей добавили сравнение значений градиентов яркости по оси ?? и ??, в итоге результат одного теста состоит из трех битов вместо одного. Проведение тестов проводилось в окне размером 20 Ч 20 пикселей, деленном на 4, 9 и 16 областей.

Но LDB имеет недостатки такие как не инвариантность к вращению и масштабированию. И в качестве решения этих проблем в AKAZE используется его улучшенная версия - M-LDB:

1. Окно дескриптора ориентируется по ориентации особой точки;

2. Инвариантность к масштабу получена с помощью выбора размера окна дескриптора в зависимости от размера октавы???? в которой найдена его особая точка.

В отличии от LDB в M-LDB тесты проводятся не между средним значением всех пикселей в области, а между заданным их количеством в зависимости от размера .Что позволяет ускорить вычисление дескриптора. Итоговый бинарный дескриптор имеет длину 486 по три составляющих.

1.7.4 Оператор Local Binary Patterns

Оператор LBP может быть использован для поиска объекта на изображении (например лица), а также проверки этого объекта на принадлежность некоторому классу (верификация, распознавание эмоций, пола по лицу).

Оператор LBP впервые был предложен T.Ojala в 1996 году. Он представляет собой эффективный оператор, который представляет каждый пиксель изображения в виде бинарного числа, зависящего от интенсивностей соседних пикселей изображения.

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

Рис.1.13 - Классический LBP, который применяется к пикселю изображения

Он принимает центральный пиксель в качестве порога и сравнивает значение яркости в каждом пикселе окрестности с ним. Если это значение больше порога(или равное значение), то пиксель принимает значение 1. Если же меньше -- 0. Полученное восьмибитное число характеризует окрестность пикселя. Всего вариантов таких чисел 2^8=256. Таким образом можно присвоить каждому пикселю изображения одну из 256 меток, характеризующих его. Далее из этих данных не составляет труда построить гистограмму и сравнивать текстуры по гистограммам LBP.

Однако хотелось бы использовать окрестности произвольного радиуса с произвольным числом значащих пикселей. В 2002 году был предложен метод eLBP (extended LBP), который удовлетворяет этим условиям. Теперь окрестность выглядит следующим образом:

Рис.1.14 - Иллюстрация методаeLBP

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

Однако видно, что с увеличением окрестности, увеличивается количество разрядов в числах, с которыми требуется вести работу. То есть для окрестности радиуса 2 из 16 точек требуется работать уже с числами, состоящими из 16 бит. И количество бинов гистограммы становится огромным. Через некоторое время было выяснено, что больше всего информации несут так называемые uniformpatterns. Суть заключается в том, что эти паттерны содержат не более определенного числа переходов от 0 к 1 в записи и наоборот. То есть числа 00011000 или 00000000 будут являться uniformpatterns, а 00100100 -- нет, если заданное число переходов -- два (000 переход 11 переход 000 -- uniform (2 перехода), 00 переход 1 переход 00 переход 1 переход 00 -- нет (4 перехода).

Оператор LBP применяется как составная часть многих классификаторов. Самое простое применение -- это составление гистограмм и сравнение их. Также он используется с такими алгоритмами машинного обучения, как SVM и AdaBoost.

1.7.5 Детектор LIFT

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

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

· Инвариантность к расположению на картинке;

· Инвариантность к углу поворота;

· Инвариантность к масштабу.

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

· Для каждого изображения сцены находим особые точки;

· Находим соответствия между особыми точками с разных изображений;

· Но основе этой информации вычисляем пространственное расположение каждого кадра (параметризуемое через[R,t]т.е. поворот и трансляцию относительно начала координат);

· При помощи процедуры триангуляции находим 3D положения всех особых точек.

· Используя развесистую оптимизацию BundleAdjustment (чаще всего алгоритм, производные от метода Левенберга-Марквардта), получаем более точную информацию о расположении точек в пространстве.

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

Как побочный продукт работы такого алгоритма, мы получаем облако точек, где каждой 3D точке соответствует несколько её 2D положений(проекций) на кадрах сцены. Вот такое облако -- это как раз тот dataset, который нам нужен.

Всю сетку можно разделить на 3 логических блока:

· Detector -- отвечает за поиск особых точек на всем изображении в целом.

· Rotation Estimator -- определяет ориентацию точки и доворачиваетпатч вокруг неё так, чтобы угол поворота стал равен нулю.

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

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



Рис.1.15 - Поиск особых точек и вычисление их дескрипторов

Поиск особых точек и вычисление их дескрипторов происходит в несколько этапов:

· Построение пирамиды изображения (т.е. приводим исходное изображение к нескольким масштабам, для получения инвариантных к изменениям масштаба изображений) для исходного изображения;

· Каждый слой пирамиды проходит через сеть-детектор и вычисляется пирамида ScoreMap;

· При помощи процедуры Non-MaximumSuppression находим наиболее сильные кандидаты в особые точки;

· Для каждой особой точки выбираетсяпатч, включающий в себя особую точку и некоторую её окрестность;

· Выравниваем ориентацию каждого патча при помощи OrientationEstimator;

· Вычисляем дескриптор для каждого выровненного патча.

· Используем полученные дескрипторы для стандартной процедурыfeaturematching;

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

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

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

(1.33)

Затем вычисляется положение особой точки:

, (1.34)

гдеsoftargmax-- это функция, вычисляющая взвешенный центр масс с весами, являющимися результатом вычисленияsoftargmax:

, (1.35)

где y - позиция внутри ScoreMap;

в - гиперпараметр, отвечающий за коэффициент "размытия" softmax-функции.

При тренировке детектора выбирается по четыре патча (), где , - проекции одной и той же особой точки, - проекция другой особой точки, - патч не принадлежащий особой точке.

Для наобратакихпатчей будем минимизировать следующую loss-функцию:

(1.36)

где- параметр балансировки для двух членов loss-функции.

Член лосса, отвечающий за корректную классификацию на позитивы и негативы:

(1.37)

Член лосса, отвечающий за точную локализацию особых точек:

(1.38)

Рис.1.16 - Тренировка сети по алгоритму End-to-End

LIFT c успехом применяются вместо и вместе с Хаар-подобными признаками при AdaBoost-обучении. Они захватывают высокочастотную информацию, которую пропускают интегральные признаки.

Выводы

Авторы [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.

Рис.2.2 - Геометрическая интерпретация коэффициента корреляции R=cosи

Значения нормализованного коэффициента корреляции находятся в диапазоне -1<=R<=1. Значение 1 достигается только тогда, когда участки изображений and связаны линейной связью =+, > 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)

{

assert(argc == 3);

ccv_enable_default_cache();

ccv_dense_matrix_t* object = 0;

ccv_dense_matrix_t* image = 0;

ccv_read(argv[1], &object, CCV_IO_GRAY | CCV_IO_ANY_FILE);

ccv_read(argv[2], &image, CCV_IO_GRAY | CCV_IO_ANY_FILE);

unsignedintelapsed_time = get_current_time();

ccv_sift_param_tparams = {

.noctaves = 3,

.nlevels = 6,

.up2x = 1,

.edge_threshold = 10,

.norm_threshold = 0,

.peak_threshold = 0,

};

ccv_array_t* obj_keypoints = 0;

ccv_dense_matrix_t* obj_desc = 0;

ccv_sift(object, &obj_keypoints, &obj_desc, 0, params);

ccv_array_t* image_keypoints = 0;

ccv_dense_matrix_t* image_desc = 0;

ccv_sift(image, &image_keypoints, &image_desc, 0, params);

elapsed_time = get_current_time() - elapsed_time;

inti, j, k;

int match = 0;

for (i = 0; i<obj_keypoints->rnum; i++)

{

float* odesc = obj_desc->data.f32 + i * 128;

intminj = -1;

double mind = 1e6, mind2 = 1e6;

for (j = 0; j <image_keypoints->rnum; j++)

{

float* idesc = image_desc->data.f32 + j * 128;

double d = 0;

for (k = 0; k < 128; k++)

{

d += (odesc[k] - idesc[k]) * (odesc[k] - idesc[k]);

if (d > mind2)

break;

}

if (d < mind)

{

mind2 = mind;

mind = d;

minj = j;

} else if (d < mind2) {

mind2 = d;

}

}

if (mind < mind2 * 0.36)

{

ccv_keypoint_t* op = (ccv_keypoint_t*)ccv_array_get(obj_keypoints, i);

ccv_keypoint_t* kp = (ccv_keypoint_t*)ccv_array_get(image_keypoints, minj);

printf("%f %f => %f %f\n", op->x, op->y, kp->x, kp->y);

match++;

}

}

printf("%dx%d on %dx%d\n", object->cols, object->rows, image->cols, image->rows);

printf("%d keypoints out of %d are matched\n", match, obj_keypoints->rnum);

printf("elpased time : %d\n", elapsed_time);

ccv_array_free(obj_keypoints);

ccv_array_free(image_keypoints);

ccv_matrix_free(obj_desc);

ccv_matrix_free(image_desc);

ccv_matrix_free(object);

ccv_matrix_free(image);

ccv_disable_cache();

return 0;

}

На конечном шаге алгоритма SIFT для окрестности особой точки вычисляются изменения яркостей точек, по которым строится дескриптор. Дескриптор - это вектор из 64 чисел, позволяет получить инвариантность относительно положения камеры. Затем дескриптор нормализуется, за счёт чего достигается инвариантность относительно изменения освещения.

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

Нахождение соответствий между дескрипторами:

exit unless ARGV.length == 3 or ARGV.length == 4

matches = File.new("/tmp/matches.txt", "w+") if ARGV.length == 4

object_size = Array.new

image_size = Array.new

pairs = Array.new

STDIN.each_linedo |line|

print line

args = line.split(" ")

break if args[1] == "keypoints"

ifargs[0].include? "x"

object_size = args[0].split("x")

object_size = {:width =>object_size[0].to_i, :height =>object_size[1].to_i}

image_size = args[2].split("x")

image_size = {:width =>image_size[0].to_i, :height =>image_size[1].to_i}

else

ifmatches.nil?

pairs<< {:object => {:x =>args[0].to_f, :y =>args[1].to_f},

:image => {:x =>args[3].to_f, :y =>args[4].to_f}}

else

matches.putsargs[0] + " " + args[1] + " " + args[3] + " " + args[4] + "\n"

end

end

end

ifmatches.nil?

%x[#{sprintf("convert %s -extent %dx%d %s", ARGV[0], object_size[:width] + image_size[:width], [object_size[:height], image_size[:height]].max, ARGV[2])}]

%x[#{sprintf("composite -gravity southEast %s %s %s", ARGV[1], ARGV[2], ARGV[2])}]

lines = ""

pairs.each do |pair|

lines += sprintf("-draw \"line %d,%d,%d,%d\" ", pair[:object][:x], pair[:object][:y], pair[:image][:x] + object_size[:width], pair[:image][:y])

end

%x[convert #{ARGV[2]} -stroke red #{lines}#{ARGV[2]}]

else

matches.close

output = %x[#{ARGV[3] + " /tmp/matches.txt"}]

line = output.split("\n")

h = Array.new

h[0] = line[4].split(" ")

h[0] = [h[0][0].to_f, h[0][1].to_f, h[0][2].to_f]

h[1] = line[5].split(" ")

h[1] = [h[1][0].to_f, h[1][1].to_f, h[1][2].to_f]

h[2] = line[6].split(" ")

h[2] = [h[2][0].to_f, h[2][1].to_f, h[2][2].to_f]

points = [{:x => 0, :y => 0},

{:x =>object_size[:width], :y => 0},

{:x =>object_size[:width], :y =>object_size[:height]},

{:x => 0, :y =>object_size[:height]}]

frame = Array.new

points.each do |point|

x = h[0][0] * point[:x] + h[0][1] * point[:y] + h[0][2]

y = h[1][0] * point[:x] + h[1][1] * point[:y] + h[1][2]

z = h[2][0] * point[:x] + h[2][1] * point[:y] + h[2][2]

frame<< {:x => x / z, :y => y / z}

end

%x[#{sprintf("convert %s -stroke red -strokewidth 3 -draw \"line %d,%d,%d,%d\" -draw \"line %d,%d,%d,%d\" -draw \"line %d,%d,%d,%d\" -draw \"line %d,%d,%d,%d\" %s", ARGV[1], frame[0][:x], frame[0][:y], frame[1][:x], frame[1][:y], frame[1][:x], frame[1][:y], frame[2][:x], frame[2][:y], frame[2][:x], frame[2][:y], frame[3][:x], frame[3][:y], frame[3][:x], frame[3][:y], frame[0][:x], frame[0][:y], ARGV[2])}]

end

Полученная последовательность может иметь ложные соответствия. Для удаления ложных соответствий применяется метод согласования случайных выборок RANSAC (англ. Random Sample Consensus) - итерационный, вероятностный метод, в котором определяется минимальная симметрическая погрешность между парами точек, после чего вычисляются коэффициенты матрицы перспективного преобразования H размерности 3х3 (матрица гомографии) методом прямого линейного преобразования DLT (англ. Direct Linear Transformation). Решается система линейных алгебраических уравнений, в результате определяются 8 коэффициентов (параметров DLT), показывающих связь между системами координат плоскостей двух изображений.

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

1. определяется размер итогового панорамного изображения;

2. первое изображение без изменения копируется в плоскость итогового;

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

4. общая часть накладывается путём линейной интерполяции.



Рис.2.5 - Результат создания панорамного изображения

Заключение

В данной бакалаврской работе был произведён анализ предметной области, алгоритмов выделения особых точек, проанализированы и промоделирован алгоритм, необходимый для формирования панорамного изображения. Ограничением смоделированного алгоритма является обработка не более двух изображений (при большем числе изображений проявляется эффект дисторсии).

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

К основным направлениям развития следует отнести:

- модификацию алгоритмов для использования в многопроцессорных системах;

- формирование более двух изображений в панорамное.

Размещено на Allbest.ru

...