Диссертация (Автоматическая сшивка радиолокационных изображений земной поверхности при неизвестных элементах внешнего ориентирования), страница 6

В этой связиметоды на основе оптического потока незаменимы при поиске изменений напоследовательных кадрах видеопоследовательности, однако не применимы взадачах сшивки или совмещения РЛИ земной поверхности.В настоящее время существует множество методов автоматического поискаопорных точек на основе выделения, описания и сопоставления точек интереса[56, 61]. В составе данных методов выделяют алгоритмы:– поиска (выделения) точек интереса (LoG [62], DoG [63] и другие);33– вычисления векторов описания (дескрипторов) точек интереса (GLOH [64],LESH [65] и другие);– сопоставления векторов описания точек интереса с целью поиска опорныхточек (на основе k-мерных деревьев [66], RANSAC [67] и другие).Кроме того, существуют алгоритмы, объединяющие в себе как выделение,так и описание точек интереса.

К таким алгоритмам можно отнести SIFT и SURF,показывающие наилучший результат.Приведенный обзор показывает, что для поиска опорных точек наперекрывающихся РЛИ земной поверхности необходимо использовать алгоритмына основе выделения, описания и сопоставления точек интереса.1.4.1 Алгоритмы выделения и описания точек интереса на изображенииВыделение точек интереса в SURF (Speeded-Up Robust Features) [68]происходит путем обнаружения локальных максимумов детерминанта матрицследующего вида:‖H (x , y , σ)=‖L xx ( x , y , σ) L xy (x , y ,σ )L yx (x , y ,σ) L yy (x , y , σ)1 ∂2L xx (x , y , σ )=∑∑e2 πσ ∂ x 2 a b2,(4)2−((a) +(b ) )2σI (x −a , y −b) ,(5)где Lxy(x,y,σ), Lyx(x,y,σ), Lyy(x,y,σ) вычисляются аналогично (5), σ – степень размытияизображения фильтром Гаусса [69], а I(x,y) – обрабатываемое РЛИ.Пирамидойизображенияназываетсянаборуменьшенныхкопийизображения, включая исходное.Для обрабатываемого РЛИ строится набор пирамид с различной степеньюразмытости (σ) фильтром Гаусса, для каждом изображения которых и происходитпоиск точек интереса.

Таким образом, найденная точка интереса характеризуется34координатами (x,y), а так же параметрами изображения из пирамиды, на которомона была обнаружена, — масштабом (s) и степенью размытости (σ) фильтромГаусса.Рассмотрим одну найденную точку интереса. Для устойчивости вектораописания повороту семантики изображения между двумя РЛИ, его вычислениепроисходитотносительнонекоторогоугла (ориентацииточкиинтереса),получаемого следующий образом.В каждой точке окрестности точки интереса радиусом 6s проводитсядвумерное горизонтальное и вертикальное вейвлет-преобразования Хаара [69],при этом длина стороны вейвлета равна 4s (рисунок 1.4).а)б)в)Рисунок 1.4 – Горизонтальный (а) и вертикальный (б) вейвлеты Хаара, проекциягоризонтального вейвлета Хаара на плоскость, перпендикулярнуюизображению (в)Таким образом, каждую точку рассматриваемой окрестности можнопредставить в пространстве Odxdy, где по осям откладываются dx и dy – значениягоризонтального и вертикального двумерного вейвлет-преобразования Хаарасоответственно (рисунок 1.5, а).

Направление из начала координат, в которомсумма dx и dy всех точек, попавших в окно π/3 по этому направлению,максимальна, считается ориентацией данной точки интереса.35Далее, с учетом полученной ориентации точки, ее окрестность делится на16 квадратных сегментов (рисунок 1.5, б), размер которой зависит от масштабаизображения, на котором была найдена точка интереса. Для каждой точкисегментаокрестностисновавычисляютсязначениягоризонтальногоивертикального двумерного вейвлет-преобразования Хаара dx и dy соответственно(в связи с поворотом системы координат на угол ориентации точки интереса,предыдущие значения dx и dy не подойдут).

В итоге каждый сегмент определяютчетыре величины ∑dx, ∑|dx|, ∑dy, ∑|dy|, где суммируются значения dx и dy каждойточки данного сегмента. Искомый дескриптор состоит из описания всех16 сегментов – является вектором с размерностью 16∙4=64.б)а)Рисунок 1.5 – Определение ориентации точки интереса по двумерномувейвлет-преобразованию Хаара в точках ее окрестности (а) и разбиениеокрестности точки интереса при вычислении вектора описания (б)В SIFT (Scale-invariant feature transform) [70] поиск точек интереса основанна определении точек локального экстремума функции дифференциала размытогофильтром Гаусса изображения:361D(x , y , σ)= ∂∑e∂ σ 2π σ ∑ab22−((a) +( b) )2σ(6)I (x−a , y−b) .Значения данной функции вычисляются путем попиксельного вычитаниядвух копий изображений одинакового масштаба (в SIFT обработка такжепроводится по набору пирамид изображения) с различной степенью размытости(σ) фильтром Гаусса.Далее, происходит уточнение координат найденной точки интереса спомощью аппроксимации рядом Тейлора второго порядка в этой точке:∂DT1 T ∂2 DD(x)=D+x+ xx ,∂x2∂ x2(7)x=(x , y , σ)T .(8)В (8) первая производная D является градиентом, вторая – матрицей Гессе.Экстремум многочлена Тейлора находится путем приравнивания нулю егопроизводной, при этом смещение найденной точки относительного точныхкоординат экстремума:−∂2 D −1 ∂ Dx^ =.∂ x2 ∂ x(9)Далее, проверяется на малость значение функции (6) в полученной точке.Не прошедшие проверку точки интереса выкидываются.Ориентацияточкиинтересавычисляетсяисходяизгистограммынаправлений градиентов точек ее окрестности радиусом 1,5s.

Гистограммасостоит из 36 компонент, которые равномерно покрывают 360 градусов. Искомойориентацией считается направление максимальной компоненты гистограммы.Далее, как и в SURF, учитывая ориентацию точки интереса, для вычислениявектора описания используется окрестность найденной точки интереса, разбитая37на 16 сегментов (рисунок 1.5, б).

Каждый сегмент характеризуется гистограммойградиентов пикселей региона из 8 компонент, разбивающих 360 градусов наравные сектора по 40 градусов. Каждая компонента является суммой величинградиентов ее направления. Гистограмма нормируется, после чего все еекомпоненты, значение которых больше 0,2, принимают значение 0,2, и проводитсяповторная нормировка. Таким образом, вектор описания в SIFT имеет размерность128 (16 сегментов имеют гистограмму из 8 компонент).При приблизительно схожем качестве получаемых точек интереса кпреимуществам SIFT перед SURF можно отнести большее их количество (до1,5 раз) при обработке одного и того же изображения, однако при этом SIFTзатрачивает примерно в 2,5 раза больше времени, чем SURF.

Объем ОЗУ,потребляемый SIFT при обработке РЛИ большой площади значительно превышаетобъем ОЗУ, необходимый для SURF, что существенно ужесточает требования кЭВМ. Оба алгоритма в одинаковой степени устойчивы к смене угла обзораподстилающей поверхности (до 50 градусов) в угломестной плоскости [68].Две точки интереса на различных изображениях считаются совпавшими(составляют опорную точку), если евклидово расстояние между их векторамиописания не превышает порогового значения.

Если у точки есть два совпадения,выбирается ближайшее.В [71] к недостаткам SURF относят большую уязвимость дескрипторовточек интереса к повороту семантики изображения в сравнении с SIFT.Действительно, при сопоставлении дескрипторов точек интереса двух РЛИ состопроцентным перекрытием имеет место существенное уменьшение количестванайденных совпадений (опорных точек) при приближении угла поворотасемантики к значениям α = π/4 + πn/2, где n – целое число (рисунок 1.6).Уменьшение количества найденных опорных точек влияет на точностьопределения взаимной ориентации двух РЛИ.38Рисунок 1.6 – Количество найденных совпадений между точками интереса SURFдвух РЛИ со стопроцентным перекрытием при различных углах поворота ихсемантики друг относительно другаУчитывая меньшие требования к ЭВМ и более оперативную обработкуизображений, для эффективного поиска точек интереса на РЛИ необходимомодернизировать алгоритм SURF с целью ослабления уязвимости дескрипторовточек интереса к повороту семантики изображения.1.4.2 Интегральные изображенияНавсехэтапахалгоритмаприменяются интегральные:SURFвместоисходныхизображений39i≤x j≤ yI ∑ (x , y )=∑ ∑ I (i , j) ,(10)i=0 j=0где I(i,j) – исходное изображение.

Стоит отметить, что размер интегральногоизображения равен размеру исходного изображения, из которого оно былополучено.Интегральное изображение позволяет оперативно находить сумму значенийпикселей исходного изображения в заданной прямоугольной области. Например,для прямоугольника ABCD (рисунок 1.7) на исходном изображении имеем:∑L∈ ABCDI (L)=I ∑ (C )+ I ∑ ( A)−I ∑ (B)− I ∑ (D) .(11)Стоит отметить, что выражение (11), содержащее всего 4 операции сложения,справедливо для области ABCD любого размера.Использованиеинтегральныхизображенийвзначительнойстепениускоряет вычисление вейвлет-преобразование Хаара, так как вне зависимости отмасштаба (параметр s, описанный в подразделе 1.4.1) заданной точки O свертка ееокрестности с двумерным вейвлетом Хаара (рисунок 1.4) потребует всего 6операций сложения [68] (рисунок 1.7):[ I ∑ (F)+ I ∑ ( A)−I ∑ (E)−I ∑ (D)]−[I ∑ (C)+ I ∑ ( E)− I ∑ (B)−I ∑ (F)]==2 I ∑ ( F)+ I ∑ ( A)−2 I ∑ ( E)− I ∑ ( D)− I ∑ (C)+ I ∑ (B) .(12)Стоит отметить, что умножение на 2 не является трудоемкой операцией для ЭВМ,так как в случае двоичной записи представляет собой сдвиг вправо на 1 бит.40Рисунок 1.7 – Двумерный вейвлет Хаара, наложенный на изображениеПриблизительное вычисление второй производной из (5) алгоритма SURF в[68] происходит также с использованием интегральных изображений, что даетзначительный выигрыш в производительности по сравнению с традиционнымиметодами.Из вышесказанного следует, что при обработке изображений целесообразноприменение методов, основанных на интегральных изображениях.1.4.3 Краткий обзор алгоритмов поиска ближайшего соседаДля решения задачи перебора и сравнения дескрипторов точек интересаразных РЛИ целесообразно рассмотреть алгоритмы поиска ближайшего соседа.Данные алгоритмы делятся на точные (найденная точка гарантированно будетближайшей к заданной) и неточные (найденная точка будет ближайшей илидальше ближайшей не более чем на заданное ε), а также классифицируются поспособу разбиения пространства элементов (точек), среди которых проводитсяпоиск [72].

В связи с необходимостью получения наиболее достоверных опорныхточек исключим из рассмотрения неточные алгоритмы поиска.41В настоящее время существует множество точных алгоритмов поискаближайшего соседа, среди которых можно выделить:– полный перебор или линейный поиск (без разбиения пространстваэлементов);– поиск в BSP-дереве;– поиск в R-дереве;– поиск в k-мерном дереве (kd-дереве);– поиск в VP-дереве.Пусть оба РЛИ имеют по n точек интереса (n ~ 104-107, как правило напрактике), с размерностью k их дескрипторов (64 для SURF).Наиболее простым способом поиска опорных точек является полныйперебор точек интереса каждого изображения и сравнение их дескрипторов.Однако, принимая во внимание возможное огромное количество точек интереса,этот способ требует значительных вычислительных затрат.