Диссертация (1090939), страница 5
Текст из файла (страница 5)
В зависимости от количества пересекаемыхграней существуют разные виды углов: L , Y (или T ), и X связные[29]. Различные виды детекторы по-разному реагируют на каждый из такихвидов углов.Рис. 1.4. Различные виды углов на изображенииПодходы к определению особых точек могут быть разделены на 3категории [75]: 1) Основанные на интенсивности изображения: особые точкивычисляются напрямую из значений интенсивности пикселей изображения.2) Использующие контуры изображения: методы извлекают контуры и ищутместа с максимальным значением кривизны или делают полигональнуюаппроксимациюконтуровиопределяютпересечения.Этиметодычувствительны к окрестностям пересечений, поскольку извлечение частоможет быть неправильным в тех местах, где пересекаются 3 или более краев.3) На основе использования модели: используются модели с интенсивностьюв качестве параметров, которые подстраиваются к изображениям-шаблонамдо субпиксельной точности.
Имеют ограниченное применение с особыми29точками специальных видов (например, L-связными углами), зависят отиспользуемых шаблонов. Подходы, основанные на интенсивности изображения: особые точкивычисляютсянапрямуюиззначенийинтенсивностипикселейизображения; Подходы,использующиеконтурыизображения.Этиметодычувствительны к окрестностям пересечений, поскольку извлечениечасто может быть неправильным в тех местах, где пересекаются 3 илиболее краев Подходы, использующие сравнение с изображениями-шаблонами досубпиксельной точности. Они имеют ограниченное применение сособыми точками специальных видов и зависят от используемыхшаблонов.На практике, как правило, для широкого применения наиболеераспространены методы, основанные на интенсивности изображения [12].Детектор МоравецаДетектор Моравеца [61] является самым простым детектором углов.Автор данного детектора предлагает измерять изменение интенсивностипикселя ( x, y ) посредством смещения небольшого квадратного окна сцентром в ( x, y ) на один пиксель в каждом из восьми принципиальныхнаправлений (2 горизонтальных, 2 вертикальных и 4 диагональных).
Окнообычно представляет собой квадрат со стороной в 3, 5 или 7 пикселей взависимости от характера рассматриваемого изображения. Принцип работыдетектора определяется рядом последовательных шагов. Вначале для каждого направления смещения (1,1), (0,1), (1,1),(1,0), (1,0), (1,1), (0,1), (1,1)в окне Wизменение интенсивности:30вычисляется суммарное I u ,v ( x, y) = ( a ,b )W ( I ( x u a, y v b) I ( x a, y b)) 2 ,представляетсобойинтенсивностьпикселягдеI ( x, y )рассматриваемогоизображения с координатами ( x, y ) . Далее строится функция распределения вероятности нахождения углана изображении с помощью оценочной функции C( x, y) = minVu ,v ( x, y) .По существу, определяется направление минимального градиентаинтенсивности, так как угол должен иметь смежные ребра. По пороговому значению оценочной функции отсекается большаячасть пикселей. С помощью специального метода фильтрации [64] удаляютсяповторяющиеся значения.
Все полученные ненулевые элементысоответствуют углам на изображении.Основными недостатками рассматриваемого детектора являютсяотсутствиеинвариантностикпреобразованиютипа«поворот»ивозникновение ошибок детектирования при наличии большого количествадиагональных ребер. Очевидно, что детектор Моравеца обладает свойствоманизотропии в 8 принципиальных направлениях смещения окна.Детектор ХаррисаДетектор Харриса [84] строится на основании детектора Моравеца иявляется его улучшением, характеризующимся анизотропией по всемнаправлениям.
Харрисом и Стефаном (Stephen) вводятся в рассмотрениепроизводные по некоторым принципиальным направлениям, а функцияинтенсивности раскладывается в ряд Тейлора:( x u a , y v b) I ( x a , y b) u II ( x a, y b) xI u .y v 31IIv =x yКак следствие, изменение интенсивности Vu ,v ( x, y) в каждом пикселеможно рассматривать как функцию следующего вида: I I u 2Vu ,v ( x, y ) = a ,bW ( ) = x y v I I I u u [u , v](a ,bW ( xI ) = u v Au ,v ( x, y ) .v x y v y В автокорреляционной матрице ХаррисаAu ,v ( x, y) , как правило,выбирают взвешенную свертку производных c весовыми коэффициентамиГауссова окна. Вычисляя собственные значения полученной матрицы, точкиизображения можно классифицировать на ребра и углы: точка классифицируется как угол, если оба собственных числаавтокорреляционной матрицы достаточно большие, т.е.
небольшойсдвиг окна приводит к значительным изменениям интенсивности; точка принадлежит ребру, если одно собственное число значительнобольше другого, что означает ситуацию, когда окно было сдвинутоперпендикулярно выступу; если собственные значения близки к нулю, тогда текущая точка несодержит ни углов, ни ребер.Детектор Харриса по сравнению с ранее рассмотренным детекторомМоравеца требует большего количества вычислений за счет необходимостипостроения сверток с Гауссовым ядром. Кроме того он достаточновосприимчив к шумам. Для подавления шумов применяется Гауссово окнобольшего размера, но это приводит к значительному росту вычислительнойсложности алгоритма, поэтому необходимо находить компромисс междукачеством работы алгоритма и количеством выполняемых операций.Детектор Харриса обладает свойством анизотропии вдоль горизонтального ивертикального направлений, так как автокорреляционная матрица содержитпервые производные только вдоль указанных направлений.
По сравнению с32детектором Моравеца данный детектор инвариантен относительно поворота,количество ошибок детектирования углов не велико за счет введения сверткис Гауссовыми весовыми коэффициентами. Результаты детектированиязначительноменяютсяпримасштабированииизображения.Такжесуществуют модификации детектора Харриса, которые учитывают вторыепроизводные функции интенсивности [58].Детектор FASTОписанные ранее детекторы особых точек на изображении и, вчастности, углов, характеризуются тем, что оперируют напрямую спикселями исходного изображения.
Альтернативный подход состоит в том,чтобы использовать алгоритмы машинного обучения для тренировкиклассификатора точек на некотором множестве изображений. FAST-детектор(Features from Accelerated Test) [77] использует деревья решений дляклассификациипикселей.Длякаждогопикселяизображениярассматривается окружность с центром в этой точке, которая вписана вквадрат со стороной 7 пикселей, которая захватывает 16 пикселейокрестности.Рис. 1.5 Рабочая окрестность пикселя при использовании FAST детектораx 1,2,...,16Каждыйпиксельокрестностихарактеризуетсяопределенным состоянием S x , p относительно центрального пикселя p :33S x, pIx I p t= I p t < I x < I p t .I p t IxВыбирая x и вычисляя значение S x , p для каждого пикселяpмножества P обучающей выборки изображений – разделяем P на триподмножества – множества точек, которые темнее, светлее либо подобныисходный точке.
Далее выполняется построение дерева решений [72]. Накаждом уровне дерева решений множество, соответствующее узлу дерева,разбивается на подмножества посредством выбора значения с наибольшейэнтропией. Построенное дерево решений в результате используется дляопределения углов на тестовых изображениях.1.3.2. Дескрипторы особых точекРезультатом работы детекторов является множество особых точек, длякоторых необходимо построить математическое описание. Входнымиданными дескриптора является изображение и набор особых точек,выделенных на заданном изображении.
Результатом работы дескриптораявляется множество векторов признаков для исходного набора особых точек.Необходимо отметить, что существуют дескрипторы, которые решаютодновременно обе задачи, как поиск особых точек, так и построениематематического описания для этих точек.Дескриптор SIFTДля формирования дескриптора SIFT (Scale Invariant Feature Transform)[56] сначала вычисляются значения магнитуды и ориентации градиента вкаждом пикселе, принадлежащем окрестности особой точки размером 1616пикселей.
Значения магнитуды градиентов при этом учитываются с весами,пропорциональнымизначениюфункцииплотностинормальногораспределения с математическим ожиданием в рассматриваемой особойточке. Стандартное отклонение в этом случае является равным половине34ширины окрестности. Веса Гауссова распределения позволяют уменьшитьвлияние на итоговый дескриптор значений градиентов для пикселей,находящихся дальше от особой точки.Рис. 1.6 Окрестность особой точки и полученный на основе нее дескрипторВ каждом квадрате размером 4 4 пикселя вычисляется гистограммаориентированных градиентов путем добавления взвешенного значениямагнитуды градиента к одному из 8 бинов гистограммы.
Чтобы уменьшитьразличные «граничные» эффекты, связанные с ошибкой классификациипохожых значений градиента, используется билинейная интерполяция. Приэтом значение магнитуды каждого градиента добавляется как в гистограммуквадрата данного пикселя, так и к гистограммам соседних квадратов. Приэтомзначениемагнитудыдобавляетсясвесом,пропорциональнымрасстоянию от пикселя, в котором вычислен данный градиент, до центрасоответствующего квадрата.
Все вычисленные гистограммы объединяются водин вектор, размером, равным 8 4 4 = 128 .Полученный дескриптор преобразуется, чтобы уменьшить возможныеэффекты от изменения освещенности. В свою очередь изменение контрастаизображения приводит к такому же изменению в значениях магнитудградиентов. Поэтому очевидно, что данный эффект может быть нивелированпутемнормированиядескрипторанаединицу.Измененияяркостиизображения не влияют на значения магнитуд градиентов, таким образом,SIFT дескриптор является инвариантным по отношению к аффинным35изменениям освещенности.
Однако могут возникать и нелинейные измененияв освещенности вследствие, изменения ориентации источника света поотношению к поверхностям трехмерного объекта. Чтобы избежать этого,применяется отсечение по некоторому порогу (по результатам некоторыхэкспериментов показано, что оптимальным является значение 0.2), котороеприменяютккомпонентамнормализованногодескриптора.Послеприменения порога дескриптор вновь нормализуется. Таким образом,уменьшается значение больших магнитуд градиентов и увеличиваетсязначение распределения ориентаций данных градиентов в окрестностиособой точки.Одной из важных модификаций рассмотренного дескриптора являетсятехнология PCA-SIFT [49]. На начальном этапе процесс вычислениязначения магнитуды и ориентации градиента аналогичен действиям,выполняемым при построении SIFT дескриптора. Однако для каждой особойточки рассматривается окрестность размером 41 41 пиксель с центром вособой точке.
Далее строится карта градиентов вдоль вертикального игоризонтальногонаправлений.2 39 39 = 3042элемента.дескриптораотличаютсянедескриптора.осуществляетсяДляРезультрующийДальнейшиеотснижениедействиярассмотренныхрезультирующегоразмерностивекторнаборавекторовприсодержитпостроенииотносительноSIFTдоSIFTдескрипторов32элементовпосредством метода анализа главных компонент.Дескриптор SURFДескриптор SURF (Speeded up Robust Features) относится к числу техдескрипторов, которые одновременно выполняют как поиск особых точек,как и строят их описание, инвариантное к изменению масштаба и вращению[26]. Кроме того, сам поиск ключевых точек обладает инвариантностью в томсмысле, что повернутый объект сцены имеет тот же набор особых точек, чтои образец.36Определение особых точек на изображении выполняется на основанииматрицы Гессе или Гессиана [90].