Алгоритм поэтапного уточнения проективного преобразования для совмещения изображений

АЛГОРИТМ ПОЭТАПНОГО УТОЧНЕНИЯ ПРОЕКТИВНОГО ПРЕОБРАЗОВАНИЯ ДЛЯ СОВМЕЩЕНИЯ ИЗОБРАЖЕНИЙ

А. И. Ефимов1, А. И. Новиков1 1 Рязанский государственный радиотехнический университет (РГРТУ), Рязань, Россия

Аннотация

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

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

Цитирование: Ефимов, А.И. Алгоритм поэтапного уточнения проективного преобразования для совмещения изображений / А.И. Ефимов, А.И. Новиков // Компьютерная оптика. -2016. - Т. 40, № 2. - С. 258-265. - Б01: 10.18287/2412-6179-2016-40-2-258-265.

Введение

Жёсткие ограничения, налагаемые на время обработки разноспектральных изображений в авиационных системах технического зрения (СТЗ), вынуждают искать быстрые алгоритмы решения задач в таких системах. Одной из наиболее сложных в комплексе задач, решаемых в бортовом вычислителе, является задача совмещения пары в общем случае разнородных изображений (телевизионное или тепловизионное, с одной стороны, и виртуальное изображение, построенное по цифровой карте местности, с другой). Корреляционные методы совмещения дают, как правило, гарантированный результат [1]. Однако из-за ошибок в навигационных параметрах летательного аппарата для получения этого результата требуется выполнить построение около 106 виртуальных изображений под различными ракурсами, осуществить совмещение каждого из этих изображений с реальным изображением и получить оценку критериальной функции. Такой подход требует недопустимо больших затрат машинного времени, исключающих применение методов этой группы в реальных СТЗ.

Использование методов контурного анализа для компактного описания наблюдаемой сцены [2] и методов проективной геометрии [3] для совмещения пары изображений является обнадёживающей альтернативой корреляционным методам совмещения. Основные шаги такой технологии таковы:

- выделение контуров объектов на реальном изображении;

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

- выбор угловых точек многоугольников в качестве ключевых и установление соответствия между ними;

- построение проективного преобразования и совмещение изображений;

- оценка качества совмещения.

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

держат проективные искажения. Они описываются дробно-линейными функциями, содержащими в общем случае 8 неизвестных параметров (в случае плоской гомографии) [3].

Проблема оценивания параметров проективного преобразования по опорным (ключевым) элементам рассматривалась многими авторами, в частности, в работах [4, 5]. В [4] предложена двухэтапная процедура формирования пространственного преобразования для совмещения изображений. В данной статье рассматривается аналогичная задача, для решения которой предлагается альтернативный алгоритм поэтапного уточнения проективного преобразования.

Поиск ключевых точек является наиболее важной задачей в методе совмещения изображений с помощью проективного преобразования. Далеко не всегда удается найти такие точки в автоматическом режиме. Технология получения множества пар ключевых точек в автоматическом режиме представлена в работе [6]. Но если даже найдено некоторое множество пар ключевых точек, то остаётся вопрос об их оптимальном использовании. Неудачный выбор ключевых точек может приводить к плохому и даже очень плохому качеству совмещения изображений. Один из широко применяемых методов автоматического выбора корректного набора точек - метод ЯАЖАС [7].

1. Технология и алгоритмы обработки изображений

Для учета проективных искажений можно использовать дробно-линейные преобразования [3]:

Ип х + И12 у + И13

у =

И31 х + Н32 у +1 И21 х + И22 у' + И23

К/ + И32 У' +1

или в матричной форме в однородных координатах

Г Хх ^

Ху = ¿21 И22 И23  У .

, Х

Г И 11 И12 13 Г /1

К И22 И23 г у

V ¿31 ¿32 1 J V1J

Матрица гомографии H= (h¿,)зхэ в составе формулы (1) содержит 8 неизвестных параметров, для нахождения которых необходимо как минимум 4 пары ключевых точек на сопоставляемых изображениях. Формирование множества пар ключевых точек, с одной стороны, и выбор из этого множества оптимального набора точек, обеспечивающих корректное определение элементов матрицы гомографии, с другой стороны, -две основные задачи в проблеме совмещения изображений с помощью матрицы гомографии.

Для решения первой задачи предложено большое число методов (SURF, SIFT [9, 10], методы, основанные на идеях контурного анализа [6]). Первые два метода (SURF, SIFT) дают хорошие результаты при поиске ключевых точек на паре изображений, полученных с помощью однотипных датчиков, и неприемлемы для сопоставления разнородных изображений, особенно если последние представлены контурами основных объектов на подстилающей поверхности. Именно такие изображения приходится сопоставлять в авиационных СТЗ. Для поиска ключевых точек на контурных изображениях в [6] предложены методы, дающие достаточно хорошие результаты.

Для каждой пары ключевых точек X, = (x,, yt)T и

X' = ( x, У,')T, i = 1, k в соответствии с формулами (1) можно составить пару уравнений

[ xtx;h31 + Xiy'ih32 + Х,. = X'hn + уХ2 + h13 , 1 У,Х'^3! + yy;h32 + y, = X;h2l + y.h22 + h23 .

Система линейных алгебраических уравнений (СЛАУ) вида (3), преобразованная к стандартной форме записи СЛАУ, имеет следующий вид

ЛОн = В,

где Л - основная матрица системы,

°Н = (К К К К К Кг К ЮТ - ККТОр-столбец подлежащих определению элементов матрицы гомографии, В = (х1 х2 х3 х4 у у2 у3 у4 )Т -вектор-столбец координат ключевых точек первого изображения, записанных в указанном порядке. Матрицу Л и вектор-столбец В в составе (4) можно записать в

блочной форме A =

' Z о wO f B ^

A= 1 , B =

ч 0 Z W W2 , B2 J

. Здесь

Z =

(x;

V Х4

y1 y2 у3

y4

о = ( 0)3

X X / \ - X,y1 f / - y1 X1 - УхУх

X X r - X2 у2 / , W2 = - y 2 X2 / - y2 у2 /

- X3 X3 -X3 y3 - y3 X3 - У3 У3

—X Xr X4 y4 J ч - y 4 X4 - У4 у4

W =

СЛАУ (4) будет иметь единственное решение, если ранг её основной матрицы равен 8.

Выбор из множества к(к>>4) пар ключевых точек четырёх наилучших является непростой задачей. Как

показывают исследования, даже применение алгоритма ЯА№АС для решения этой задачи не всегда обеспечивает получение хорошего результата [8]. Поэтому естественным представляется желание использовать всё множество пар ключевых точек для поиска матрицы гомографии. Однако в этом множестве могут быть пары либо с ложным соответствием, либо пары, в составе которых координаты одной точки в паре определены недостаточно точно. В этом случае предлагается использовать процедуру поэтапного уточнения матрицы гомографии, а именно:

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

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

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

Описанная технология поиска матрицы гомогра-фии, обеспечивающей наилучшее совмещение изображений по имеющемуся множеству пар ключевых точек, предполагает изменение алгоритма нахождения элементов матрицы гомографии. Если мы используем все к пар ключевых точек, то система (4) будет состоять из 2к уравнений. Её решение с помощью любого численного алгоритма, не обладающего вычислительной устойчивостью (метод Гаусса и др.), может приводить к ошибочным результатам. Поэтому от СЛАУ вида (4) целесообразно перейти к нормальной СЛАУ:

(ATA) Gh = ATB.

Решать СЛАУ (5) целесообразно любым методом, предназначенным для решения систем с симметричной и положительно определённой основной матрицей (например, метод квадратного корня [11]).

Переход от системы (4) к нормальной СЛАУ (5) эквивалентен поиску преобразования Н, минимизирующего сумму квадратов уклонений образов НХ точек Хот соответствующих им точек X, т.е.

f (Gh ) = x

k i ( X (Xj, 4 y) )2 + ^

min,

К

К +

где Ф1 = ХК11 + У'К12 + К13 - хх%1 - ХУ/^зг , Фг = Х'К21 + У'К22 + К23 - УХ'К31 + У/У/К32 .

В рамках стандартного метода наименьших квадратов из необходимого условия минимума [(Э^(Он))/(ЭОн)] = 0 функции Г(Ои) получаем систему уравнений (5).

Тогда СЛАУ (5) можно переписать в равносильной форме

X

X

(1Т1

О

Т

О ZTW¡

ZTZ ZTW2 W¡1 Z W2T Z W1TW¡ + W2TW2)

( ZTB1 ^ ZTB2

wTв1 + w2Tв2

сн =

2. Экспериментальные исследования.

Оценка качества совмещения

В процессе апробирования алгоритмов были выполнены эксперименты по совмещению пары изображений, полученных от однотипных датчиков (телевизионных), а также от датчиков разных типов (видео- и тепловизионный датчики). В первом случае выполнялось совмещение видеоизображений островов, полученных с борта воздушного судна с задержкой в несколько секунд. На рис. 1 приведен один из двух сопоставляемых контуров островов, полученный в результате предварительной обработки видеоизображения (обнаружение границ перепада яркости, замыкание контурных линий, аппроксимация замкнутых контуров многоугольниками, поиск ключевых точек и установление соответствия между ними). Знаком «звёздочка» с номерами указаны ключевые точки первого контура (18 точек). На горизонтальной и вертикальной осях приведена масштабная сетка, которая автоматически формируется средствами пакета МЛТЬЛБ и характеризует размер изображений в пикселях.

-200

-400 -600 -800 -1000 -1200

-1400

/

--'--^^ Г* ^ Цс -

" у ! /

X — Контур * Ключевые точки

<У

400 600 800 1000 1200 1400 1600 1800

Рис. 1. Контуры острова с найденными на нём ключевыми точками

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

Для нахождения наилучшего варианта приведения одного изображения к плоскости другого в работе [8] был выполнен полный перебор сочетаний из 18 точек по четыре точки. В итоге были построены 3060 матриц томографии (3060 = С18), выполнены совмещения изображений и в каждом случае оценено качество такого совмещения. Матрицы гомографии в этом ва-

61,023 ^ 40,303 1

рианте находились в результате решения СЛАУ (4). На рис. 2 приведено лучшее из 3060 совмещений контуров, найденное с помощью соответствующей матрицы гомографии в процессе полного перебора ключевых точек. Ему отвечают пары точек: 6, 9, 14, 18 и матрица гомографии

^ 0,865 0,018

0,045 0,910

-1,51х10-5 -2,06 х 10-5

\ /

Это совмещение в дальнейшем мы будем рассматривать как эталонное.

0

-200

-400 -600 -800 -1000 -1200 -1400

- Контур 1  Контур 2

200 400 600 800 1000 1200 1400 16001800

Рис. 2. Лучшее из 3060 совмещений

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

Основная идея предлагаемого метода заключается в следующем. Изображение разбивается на квадратные блоки (клетки) определённого размера, например, 100^100 пикселей. Это даёт возможность получать не только интегральную оценку качества совмещения, но и локальные оценки в каждом из выделенных квадратных блоков. В каждой клетке для всех информативных (отличных от цвета фона) точек одного из изображений ищутся информативные точки другого изображения, лежащие в некоторой квадратной окрестности размером (2&+1)*( 2&+1) с центром в

обрабатываемой информативной точке. Как правило, к = 1 или к = 2. Значение к = 1 равносильно утолщению тонкой линии в один пиксель первого контура до трёх пикселей, а к = 2 - до пяти.

Скользящее окно выбранного размера (в рассматриваемом эксперименте 5*5) перемещается по строкам изображения. Как только информативная точка первого изображения попадает в центр этой окрестности, то ищутся и помечаются информативные пиксели второго изображения, попавшие в эту окрестность и не помеченные на предыдущих этапах. После того, как выполнено сканирование всего изображения, в каждом квадратном блоке подсчитывается число ш, помеченных точек совмещаемого (второго) контура и находится отношение этого числа к общему числу информативных точек М^ первого контура, т.е. а,- = Шi /М,-. Коэффициент а,- логично назвать показателем качества совмещения в ,-м блоке изображения, а коэффициент а = (^ ш1 I ^М1) - интегральным

показателем качества совмещения всего контура.

Интегральные оценки качества совмещения контуров для 9 лучших наборов из 4 пар ключевых точек приведены в таблице. Данные результаты получены при разбиении исходного изображения на блоки размером 100*100 пикселей и значении параметра к=2. Исходные изображения островов имеют размер 1700*1500 пикселей.

Табл. 1. Показатели качества совмещения

№ п/п Номер в наборе из 3060 групп Набор точек (рис. 1) Показатель а качества совмещения

1 1959 4, 9, 12, 17 0,824

2 1960 4, 9, 12, 18 0,805

3 2017 4, 11, 14, 17 0,828

4 2459 6, 9, 11, 17 0,815

5 2460 6, 9, 11, 18 0,816

6 2465 6, 9, 12, 17 0,835

7 2474 6, 9, 14, 17 0,843

8 2475 6, 9, 14, 18 0,848

9 2538 6, 12, 11, 17 0,812

Приведённые в табл. 1. результаты достаточно интересны. Визуальный анализ рис. 1 позволяет предположить, что наилучшими должны были бы быть наборы ключевых точек 3, 10, 15 или 16, и 17 или 18. Указанные наборы также дают достаточно высокое качество совмещения, например, для набора 3, 10, 15, 18 значение показателя а качества совмещения равно 0,795. Однако приведённые в таблице оценки качества совмещения выше (все больше 0,8). Для автоматизации процесса поиска наилучшего набора из 4 пар точек нужна специальная технология отбора таких точек. Второй вывод этого этапа исследования - «хороший» набор из 4 точек на контуре не единственен, важно лишь правильно его найти.

На следующем этапе исследований поиск оптимальной матрицы томографии выполнялся сразу по

всему множеству пар ключевых точек с последующим удалением из него «плохих» точек и вычислением новой матрицы гомографии. Для сравнения получаемых совмещений использовались показатель качества совмещения а, матрица гомографии и евклидово расстояние р( X,, ИХ'), , = 1, к между ключевыми точками

одного контура и отвечающими им образами точек другого контура. Результат совмещения контуров островов с использованием всех 18 точек представлен на рис. 3. Как визуальный анализ, так и анализ значений перечисленных показателей свидетельствуют о том, что данное совмещение далеко от идеального (а = 0,176). Причина данного явления заключается в том, что в наборе из 18 пар точек есть «неудачные».

Среднее значение расстояния в евклидовой метрике между ключевыми точками первого контура и отвечающими им образами точек второго контура - 1 к

(ЯИ = — ^р(Х,,ИХ')) по всем 18 точкам равно

к ,=1

38,59. Тогда как для эталонного совмещения оно равно 18,41. Свидетельством неудачного совмещения является и матрица гомографии ' 0,211 -0,206 429,72^ -0,144 0,320 301,69

^0,0003 -0,0003 1 )

для данного варианта в сравнении с матрицей гомо-графии (7) эталонного совмещения.

Рис. 3. Совмещение контуров с помощью матрицы гомографии, найденной по всем 18 ключевым точкам

Анализ расстояний р(Х1,X,'), , = 1,18 в евклидовой метрике между соответствующими точками первого и второго контуров показал, что наибольшее уклонение наблюдается на паре точек под номером 1 (р(Х„ Х[) = 192,87 ) (табл. 2).

Удалим пару точек под номером 1 из набора и выполним процедуру совмещения по набору из 17 точек. Результат этого совмещения приведён на рис. 4.

Уже визуальный анализ говорит о том, что положение изменилось кардинально - совмещение близко к идеальному. Показатель качества в данном случае а = 0,730.

рые из них расположены близко друг к другу и, значит, в каждой такой группе можно оставить только одну точку. Такие группы в нашем примере образуют, например, подмножества{4, 5, 6, 7}, {8, 9}, {17, 18}. Сократим каждое подмножество до одной точки: {4, 5, 6, 7}{4}, {8, 9}{8}, {17, 18}{17}.

Выполним теперь поиск матрицы томографии с удалённой парой под номером 1 и удалёнными парами под номерами 5, 6, 7, 9, 18. Показатели качества совмещения при этом ухудшились, но, заметим, совсем несущественно: Ян = 19,21, а=0,768, матрица гомографии

' 0,943 0,048 26,65^ 0,044 1,022 20,26

ч1,13х10-5 3,99 х10-5 1 ,

незначительно отличается от матрицы (8). Альтернативная и достаточно распространённая методика определения «оптимальных» значений параметров проективного преобразования заключается в использовании метода ЯАЖАС. Для сопоставления предлагаемого авторами подхода с результатами, которые даёт ЯА№АС, было проведено микроисследование. Оно заключалось в многократном (30 раз) запуске ЯА№АС на рассматриваемом множестве из 18 пар ключевых точек, вычислении с его помощью матрицы гомографии, выполнении совмещения и оценки качества совмещения. Результаты таковы: всего получено 9 различных матриц гомогра-фии и соответственно вариантов совмещения, один из них оказался совершенно некачественным и повторился 6 раз в 30 экспериментах (рис. 5) (а = 0,056), 4 различных варианта матриц гомографии с невысоким качеством совмещения (рис. 6) (а = 0,214-0,368) и 4 варианта матриц гомографии с хорошим качеством совмещения (а = 0,801), причём хорошие результаты совмещения были получены только в 9 из 30 запусков ЯА№АС (применялась версия ЯА№АС, реализуемая функцией е8Иша1еОеошейсТгап81огш из пакета МАТЬАБ И2014а).

Основные выводы данного этапа:

- поиск матрицы гомографии необязательно осуществлять строго по 4 ключевым точкам, возможен расчёт по произвольному количеству ключевых точек;

- соседние точки контуров, расстояние между которыми невелико, можно заменить одной из них, без существенной потери качества;

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

Отметим, что близкие к нулю значения элементов Лз1, к32 в третьей строке найденных матриц гомогра-фии во всех экспериментах говорят фактически об отсутствии проективных искажений между сравниваемыми изображениями и, соответственно, о возможности упрощения алгоритма. Однако предлагаемый алгоритм рассчитан на использование в реальных авиационных СТЗ и должен учитывать возможное нали-

Табл. 2. Расстояния в пикселях между ключевыми точками первого контура и образами соответствующих им точек второго контура

№ пары Расстояние между № пары Расстояние

точек точками точек между точками

1 192,87 10 113,95

2 48,79 11 78,56

3 88,23 12 80,05

4 61,74 13 58,83

5 64,35 14 38,07

6 51,92 15 20,09

7 67,23 16 32,01

8 22,47 17 53,85

9 29,61 18 51,47

0 -200 -400 -600 -800 -1000 -1200 -1400

- Контур 1

- Контур 2

200 400 600 800 1000 1200 1400 1600 1800

Рис. 4. Совмещение контуров по 17 ключевым точкам

Это заключение подтверждается и объективными характеристиками: значение Ян = 18,95 близко к оптимальному значению Ян = 18,41, матрица гомогра-фии также несущественно отличается от матрицы

0,052 21,93^ 1,018 17,86

( 0,941 0,047

8,32 х 10-6 3,74 х10-5 1

/

Теперь можно сформулировать критерии сокращения множества пар ключевых точек. Мы должны исходить из того, что сокращение должно приводить либо к улучшению качества совмещения, либо не должно существенно ухудшать его. Первое требование должно достигаться при удалении «плохих» ключевых точек. Как правило, это пары точек, в которых расстояние р(Х1,X') между точками одного контура и отвечающими им точками другого контура существенно больше среднего расстояния по всему множеству ключевых точек. Второй критерий отсеивания - выбор из нескольких близко расположенных ключевых точек одной.

По первому критерию, как это следует из табл. 2, должна быть удалена пара точек под номером 1 и, быть может, под номером 10. Выше было показано, что удаление пары точек под номером 1 кардинально меняет качество совмещения.

Анализ расстояний между соседними точками на одном и втором контурах говорит о том, что некото-

чие проективных искажений между сравниваемыми изображениями. -200

-400 -600 -800 -1000 -1200 -1400

-1600

Y^r 'rJs

' h

- 7 "Г У (i '

у , и V ¿J

" ' ST

/У Контур 1 -----------]£0}imyp 2

{S

-1000 -500 0 500 1000 1500 2000 Рис. 5. Пример неудачного результата RANSAC

- Контур 1 -Контур 2

-1400

400 600 800 1000 1200 1400 1600 1800 Рис. 6. Пример результата RANSAC с невысоким качеством совмещения

Приведём пример совмещения телевизионного и тепловизионного изображений. Телевизионная и теп-ловизионная камеры жёстко закреплены на некотором расстоянии друг от друга на борту воздушного судна. Параметры камер: телевизионная - горизонтальный угол обзора - 41°, вертикальный - 30,7°, тепловизи-онная система имеет поле зрения 20°*16° по горизонтали и вертикали соответственно. Поскольку положение камер в процессе полета не меняется, то естественно ожидать, что матрица томографии для данного фиксированного положения камер в процессе полета также не будет меняться. Значит, можно выбрать любую пару чётких изображений подстилающей поверхности, содержащей чётко выделенные (на исходном изображении) контуры объектов, отметить на них по 4 пары ключевых точек, пусть даже вручную, и вычислить матрицу гомографии. Проведённые эксперименты подтвердили это предположение. Корректно рассчитанная один раз матрица гомографии обеспечивала хорошее совмещение телевизионного и тепловизионного изображений на протяжении всего полёта.

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

ний подстилающей поверхности), полученные с этих камер в некоторый момент времени, результат их совмещения с помощью найденной матрицы гомографии

г 0,5 0,03 159,13Л -0,02 0,55 174,64

0 0 1 .

V У

Также было выполнено совмещение других кадров из видеоряда на протяжении всего полёта с помощью найденной матрицы гомографии. Результат совмещения во всех случаях хороший._

* -2013/07/18 08:06:40.-

>;

е)\

2013/07/18 08:06:40

Рис. 7. Совмещение изображений подстилающей поверхности

Заключение

В статье предложена технология совмещения изображений в условиях неопределённости относительно качества сформированного множества ключевых точек. Технология основана на обнаружении и поэтапном отсеивании неудачных пар ключевых точек. Приведена методика получения локальных и интегральных оценок качества совмещения изображений. Приводятся результаты совмещения изображений подстилающей поверхности с применением предлагаемого подхода.

Литература

1. Баклицкий, В.К. Корреляционно-экстремальные методы навигации и наведения / В.К. Баклицкий. - Тверь: ТО «Книжный клуб», 2009. - 360 с.

2. Введение в контурный анализ. Приложения к обработке изображений и сигналов / Я.А. Фурман, А.В. Кревецкий,

A.К. Передреев, А. А. Роженцов, Р.Г. Хафазов, И. Л. Его-шина, А.Н. Леухин; под ред. Я.А. Фурмана. - Изд. 2-е, испр. - М.: Физматлит, 2003. - 592 с.

3. Грузман, И. С. Цифровая обработка изображений в информационных системах / И.С. Грузман, В.С. Киричук,

B.П. Косых, Г.И. Перетрягин, А.А. Спектор. - Новосибирск: Изд-во НГТУ, 2002. - 351 с.

4. Гошин, Е.В. Двухэтапное формирование пространственного преобразования для совмещения изображе-

ний / Е.В. Гошин, А.П. Котов, В.А. Фурсов // Компьютерная оптика. - 2014. - Т. 38, № 4. - С. 886-891.

5. Алпатов, Б.А. Электронная юстировка изображений при мультиспектральном наблюдении / Б.А. Алпатов, П.В. Бабаян // Цифровая обработка сигналов. - 2003. -№ 1. - С. 24-26.

6. Novikov, A.I. The Contour Analysis and Image-Superimposition Problem in Computer Vision Systems / A.I. Novikov, V.A. Sablina, M.B. Nikiforov, A.A. Loginov // Pattern Recognition and Image Analysis. - 2015. -Vol. 25(1). - P. 73-80. - DOI: 10.1134/S1054661815020194.

7. Hast. A. Optimal RANSAC - Towards a Repeatable Algorithm for Finding the Optimal Set / A Hast, J. Nysjo, A. Marchetti // Journal of WSCG. - 2013. - Vol. 21(1). - P. 21-30.

8. Novikov, A.I. Image Superimposition and the Problem of Selecting the Set of Corresponding Point Pairs / A.I. Novikov, V.A. Sablina, A.I. Efimov // 4th Conference on Embedded Computing (MECO) Proceedings, Budva, Montenegro. - 2015. - P. 139-142.

9. Herbert, B. Speeded-Up Robust Features (SURF) / B. Herbert, E. Andreas, T. Tinne, L. Van Gool // Computer Vision and Image Understanding. - 2008. - Vol. 110, Issue 3. - P. 346359. - DOI: 10.1016/j. cviu.2007.09.014.

10. Lowe, D. Distinctive Image Features from Scale-Invariant Keypoints / D.G. Lowe // International Journal of Computer Vision. - 2004. - Vol 60, Issue 2. - P. 91-110.

11. Демидович, Б.П. Основы вычислительной математики: учеб. пособие / Б.П. Демидович, И.А. Марон; под общ. ред. Б.П. Демидовича. - 2-е изд., испр. - М.: Физматгиз, 1963. - 659 с.

Сведения об авторах

Ефимов Алексей Игоревич, 1990 года рождения, в 2013 году окончил Рязанский государственный радиотехнический университет по специальности 23.01.01 «Вычислительные машины, комплексы, системы и сети», работает инженером в научно-образовательном центре «СпецЭВМ» РГРТУ. Область научных интересов: обработка графических изображений, программирование. E-mail: lexie62rus@mail.ru.

Новиков Анатолий Иванович, 1950 года рождения, в 1972 году окончил механико-математический факультет Горьковского государственного университета имени Н.И. Лобаческого (ныне - Нижегородский государственный университет имени Н.И. Лобачевского) по специальности «Прикладная математика», работает доцентом кафедры высшей математики Рязанского государственного радиотехнического университета. Область научных интересов: математические методы обработки изображений, анализ временных рядов, численные методы линейной алгебры. E-mail: novikovanatoly@yandex.ru .

Поступила в редакцию 18 января 2016 г. Окончательный вариант - 21 февраля 2016 г.

AN ALGORITHM FOR MULTISTAGE PROJECTIVE TRANSFORMATION ADJUSTMENT FOR IMAGE

SUPERIMPOSITION

A.I. Efimov 1, A.I. Novikov1

1 Ryazan State Radio Engineering University, Ryazan, Russia Abstract

We propose a multistage algorithm for constructing a projective transformation based on arbitrary sets of keypoint pairs, with the sets containing more than four keypoint pairs. In the course of calculation of a homography matrix, unsuccessful keypoint pairs are detected and rejected. Experimental results on image superimposition using projective transformations for homogeneous and heterogeneous images are presented. Methods for assessing the quality of image superimposition, which include the local and integral estimates of the superimposition quality, are proposed.

Keywords: mixed-spectrum images, contour analysis methods, keypoints (special, corresponding), projective transformations, homography matrix, quality of image superimposition.

Citation: Efimov AI, Novikov AI. An algorithm for multistage projective transformation adjustment for image superimposition. Computer Optics 2016; 40(2): 258-265. DOI: 10.18287/24126179-2016-40-2-258-265.

References

[1] Baklickiy VK. Correlation-extreme methods of navigation and guidance [In Russian]. Tver: "Knizhniy Klub" Publisher, 2009.

[2] Furman YaA, Kreveckiy AV, Peredreev AK, Rozhencov AA, Hafazov RG, Egoshina IL, Leuhin AN. Introduction to the contour analysis. Applications to image and signal processing [In Russian]. Moscow: "Fizmatlit" Publisher; 2003.

[3] Gruzman IS, Kirichuk VS, Kosih VP, Peretryagin GI, Spector AA. Digital image processing in information systems [In Russian]. Novosibirsk: 'Novosibirsk State Technical University" Publisher; 2002.

[4] Goshin EV, Kotov AP, Fursov VA. Two-stage formation of a spatial transformation for image matching Computer Optics 2014; 38(4): 886-891.

[5] Alpatov BA, Babayan PV. Digital adjustment of multispectral images observation [In Russian]. Digital signal processing 2003; 1: 24-26.

[6] Novikov AI, Sablina VA, Nikiforov MB, Loginov AA. The contour analysis and image-superimposition problem in computer vision systems. Pattern Recognition and Image Analysis 2015; 25(1): 73-80. DOI: 10.1134/S1054661815020194

[7] Hast A, Nysjö J, Marchetti A. Optimal RANSAC - towards a repeatable algorithm for finding the optimal set. Journal of WSCG 2013; 21(1): 21-30.

[8] Novikov AI, Sablina VA, Efimov AI. Image Superimposition and the Problem of Selecting the Set of Corresponding Point Pairs. Proceedings of MECO 2015: 139-142.

[9] Herbert B, Andreas E, Tinne T, Van Gool L. Speeded-Up Robust Features (SURF). Computer Vision and Image Understanding 2008; 110(3): 346-359.

[10] Lowe, DG. Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision 2004; 60(2): 91-110.

[11] Demidovich BP, Maron IA. Fundamentals of Computational Mathematics [In Russian]. Moscow: "Fizmatgiz" Publisher; 1963.

Authors' information

Aleksey Igorevich Efimov (b. 1990) graduated from Ryazan State Radioengineering University in 1990, majoring in Electronic Machines, Systems and Networks. Currently he works as the engineer at the RSREU education and research center of specialized computers. Research interests are computer graphics processing and programming. E-mail:

lexie62rus@mail. ru.

Anatoly Ivanovich Novikov (b. 1950) graduated from Mechanics and Mathematics faculty of Gorky State University named after NI Lobachesky (now - Nizhny Novgorod State University named after Lobachevsky) in 1972, majoring in Applied Mathematics. Currently he works as associate professor at Higher Mathematics department in RSREU. Research interests are computer graphics processing, time series analysis, numerical methods of linear algebra. E-mail:

novikovanatoly@yandex.ru .

Received January 18, 2016. The final version - February 21, 2016.