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

Для установлениявзаимно-однозначного соответствия между угловыми точками многоугольников,полученных на предыдущем шаге (поиска пар ключевых точек) предлагаетсяследующий алгоритм [54].В каждой точке M i ij   M i , M jкритерия71первого многоугольника вычисляются значение«похожести»угловi  M i 1M i M i 1и j  M j 1M j M j 1 :a1  k  b1a2  k  b 21ij  cos  i  cos  j 2a1  b1a2  b 2Здесь a1  M i M i 1,p1 ,p2a2  M i M i 1 ; b1  M j M  j 1, b2  M j M  j 1 k (2.8)p1, гдеp2– периметры первого и второго контуров соответственно.

Прификсированном значении индекса i проходим все точки M 'j второго контура изmсписка {M j } j 1 , вычисляем в каждой из них значение критерия (2.8) и находиминдексj0точкиM j0 ,длякоторой M i , M j  min  ij , j  1, n ,т.е.j0  arg min ij . Найденная точка M j0 на втором контуре ставится в соответствиеj 1, nточке M i на первом контуре.

Это соответствие можно будет считать взаимнооднозначным после прохождения всех точек первого контура при условии, что накаком-то шаге алгоритма точка M j0 не будут поставлена в соответствие ещеодной точке первого контура.Нужно заметить, что на втором контуре может быть найдена более чем однаточка M j с близкими значениями критерия  ij . При этом одна из набора такихточек может быть действительно «идентичной» точке M i 1 , а другие – нет. Дляразрешения возникающего противоречия вводится дополнительная проверка«идентичности» сравниваемых точек. Формируются векторы d1  a1  a2 иd1  b1  b2 , и вычисляется косинус cos  d1, d1  угла между ними.d1  d1Если cosφ>c, где, например, c  0,966 , что соответствует углу в 15 градусов,то точки M i и M j признаются «идентичными».

В противном случае выносится072решение о том, что точка, «идентичная» точке M i , на втором контуре не найдена.Иллюстрация установления соответствия между точками контуров приведена нарисунке 2.17.Рисунок 2.17 – Установленные соответствия между угловыми точками контуров2.3.7 Разработка алгоритма отбраковки недостоверных пар ключевыхточекЧасто в наборах точек, выбранных в качестве ключевых, содержатсянедостоверные,включениекоторыхввычислениеэлементовматрицыгомографии негативно сказывается на итоговом результате.

Наличие таких парточек можно объяснить шумами на исходном изображении, ошибками,возникающими при выделении границ и последующем оконтуривании. Поэтомувозникает потребность в отбрасывании пар точек, снижающих качествосовмещения изображений.В качестве исходных выступает 2 контура, содержащих 5 000 и 5 700 точексоответственно.Особенностьконтурногоописаниявтом,чтокаждаяпоследующая точка принадлежит восьмисвязной окрестности предыдущей.Простое наложение исходных изображений приведено на рисунке 2.18.В ходе выполнения исследования в качестве ключевых были отмечены 18пар точек. Один из контуров с отмеченными точками приведен на рисунке 2.19.

Сбольшой вероятностью часть из 18 пар ключевых точек также можно исключить73из рассмотрения, однако, для большей массовости результата дальнейшееисследованиепроводитсясиспользованиемименноэтогонаборасоответствующих точек. В таблице 2.2 приведено соответствие ключевых точекна первом контуре ключевым точкам на контуре втором, а также указаныкоординаты ключевых точек.Рисунок 2.18 – Результат простого наложения контуровРисунок 2.19 – Один из контуров с отмеченными ключевыми точками74Таблица 2.2 – Соответствие точек контуровНомер точки по порядку123456789101112131415161718Первый контурХУ490813406103818716513411472342146935014203441426595133659413701372564116353211155231056626898809717978654876773419776415Второй контурХУ641693440107325916003971446396143440014064061400616134462313641295648111059010625831025676879842719998662907753469755462Для вычисления коэффициентов матрицы гомографии необходимо какминимум 4 пары точек, соответственно возможны С 4m m!, то есть 30604!m  4!вариантов выбора точек.На рисунке 2.20 представлен результат лучшего из 3060 возможныхсовмещений по критерию минимального среднего евклидова расстояния R междуключевыми точками после преобразования одного из контуров.

Величина Rопределяется как:R1 m ( xi  xi ' ' ) 2  ( yi  yi ' ' ) 2 .m i 1В лучшем по критерию R совмещении используются следующие 4 парыключевых точек: 4, 9, 14, 18. Значение описанного критерия для приведенногосовмещениясоставляетR=8,29.рассматривать как эталонное.Этосовмещениевдальнейшембудем75Рисунок 2.20 – Лучшее из 3060 совмещенийВычисленная в этом случае матрица гомографии имеет следующий вид: 0,865H   0,045  1,5  10  5Дальнейшиеэкспериментыбудут0,0180,910 2  10  561,023 40,3031 осуществлятьсясиспользованиемалгоритма нахождения матрицы гомографии по произвольному количеству парключевых точек, описанному ранее в настоящей работе.На рисунке 2.21 приведен результат совмещения в том случае, когда матрицагомографии посчитана по всем 18 парам ключевых точек. Вычисленная матрица 0,206 429,721 0,2110,320301,693  , значениегомографии имеет следующий вид: H   0,144  0,0003  0,00031 критерия R=32,84.Как визуально, так и по значению показателя R видно, что данноесовмещение далеко от идеального.

Причина заключается в том, что в наборе из 18пар точек есть недостоверные, координаты которых определены недостаточнонеточно.76Рисунок 2.21 – Совмещение по всем 18 парам ключевых точекВ таблице 2.3 приведены значения расстояний в пикселях между ключевымиточками. Видно, что существенный выброс относительно среднего значениянаблюдается в парах точек с номерами 1 и 10.В таблице 2.4 приведены евклидовы расстояния между соседними точкамиконтуров. Учитывая весьма большие размеры исследуемых изображений,расстояние менее 35-40 пикселей между двумя соседними точками можно считатьдостаточным для того, чтобы оставить из этих точек только одну.Таблица 2.3 – Расстояние в пикселях между ключевыми точками первого контураи образами соответствующих им точек второго контура№ парыточек123456789Расстояние между точками(% от среднего)192,87(300,8)48,79(76,1)88,23(137,6)61,74(96,3)64,35(100,4)51,92(80,9)67,23(104.9)22,47(35,0)29,61(46,2)№ парыточек101112131415161718Расстояние между точками(% от среднего)113,95(177,8)78,56(122,5)80,05(124,9)58,83(91,8)38,07(59,4)20,09(31,3)32,01(49,9)53,85(83,9)51,47(80,3)77Таблица 2.4 – Расстояние между соседними точками каждого из контуровРасстояниемеждуточками1-22-33-44-55-66-77-88-99-10ПоПервый контур Второй контур240,16650,94236,123,1649,648,48266,6434,011120,23результатам389,17570,69217,7812,0429,128,48257,1720,021057,32проведенныхРасстояниемеждуточками10-1111-1212-1313-1414-1515-1616-1717-1818-1исследованийПервыйконтурВторойконтур211,4348,83118,70241,77247,63119,88472,235490,10216,8948,50110,13229,17238,94110,67453,877,61257,59зависимостикачествасовмещения изображений от набора пар ключевых точек, применяемых длярассчета элементов матрицы гомографии, предлагается 2 критерия поотсеиванию пар ключевых точек:1) выбор из нескольких близко расположенных точек только одной;2) удаление пар точек, расстояние между образами которых превышает 1,75среднего расстояния по всему множеству.По первому критерию для рассматриваемых контуров требуется следующаязаменагруппточек:{4,5,6,7}→{4|5|6|7};{8,9}→{8|9};{11,12}→{11|12};{17,18}→{17|18}.По второму критерию требуется исключить пары ключевых точек подномером 1, и, возможно, 10.Результат совмещения по 17 парам точек, исключая первую пару приведен нарисунке 2.22.

Вычисленная матрица гомографии имеет следующий вид: 0,941H   0,047 8,3  10 60,05221,935 1,01817,863  , значение критерия R= 7,98.3.74  10 51 Результат совмещения без первой пары и в условии {4,5,6,7}→{4};{8,9}→{8}; {17,18}→{17} приведен на рисунке 2.23. Вычисленная матрица78гомографииимеетследующийвид: 0,9430,048H   0,0441,0231,13  10 5 3.99  10 526,654 20,255  ,1 значение критерия R= 8,63.Рисунок 2.22 – Совмещение по всем парам ключевых точек, кроме первойРисунок 2.23 – Результирующее совмещениеДля сопоставления предлагаемого авторами подхода с результатами, которыедает RANSAC, было проведено микроисследование. Оно заключалось в79многократном (30 раз) запуске RANSAC на рассматриваемом множестве из 18 парключевых точек, вычислении с его помощью матрицы гомографии, выполнениисовмещения и оценки качества совмещения.

Результаты таковы: всего получено 9различных вариантов совмещения, 1 из них оказался совершенно некачественным(проявился в 6 случаях), 4 варианта «средних» совмещений (проявились в 2, 9, 2,2 случаях соответственно), а также 4 варианта хороших совмещений (проявилисьв 6, 1, 1, 1 случаях). Повторяемость получаемых результатов обуславливается тем,что при различных запусках RANSAC возможно получить одинаковый результат(набор так называемых инлаеров модели). Это позволяет говорить о том, чтооднократного запуска RANSAC недостаточно, примерно в 20 % случаевполучаемый результат совмещения будет полностью непригоден для дальнейшейобработ-ки и визуализации, в половине случаев результат будет не слишкомхорошим и лишь 30 % результатов можно классифицировать как качественные.При исследовании применялась версия RANSAC, реализуемая функциейestimateGeometricTransform из пакета MATLAB R2014a.Основные выводы: поиск матрицы гомографии не обязательно осуществлятьлишь по четырем парам точек, возможен расчет по произвольному количеству.Основное преимущество предложенного подхода – если в результирующий наборпопала пара точек с зашумленными координатами, её влияние на итоговыйрезультат будет сглажено [53].2.3.8 Пошаговый алгоритм поиска матрицы гомографииВ случае нахождения на изображении k пар ключевых точек (k>>4)предлагается применять пошаговый алгоритм поиска матрицы гомографии,состоящий из следующих шагов:1) нахождение матрицы гомографии по всему множеству пар ключевыхточек и совмещение изображений с её помощью;2) оценка качества совмещения изображений (правильности нахожденияматрицы гомографии).