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

The paper proposes a technique for reducing the complexity of the correlation image registration algorithms with a virtual terrain model, by specifying the angle of alignment in the plane of heel correlation method. Knowledge of the true roll angle and its exclusion from the definition of the cycle of combining correlation algorithm to reduce the complexity of the procedure for the latter.

Key words: non-correlation combination, compensation error roll, acronym combining the complexity of the correlation.

Myratov Evgeni Rashitovich, postgraduate, myratov eramail.ru, Russia, Ryazan, Ryazan State Radio Engineering University.

УДК 004.932

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

А.И. Новиков, В.А. Саблина, Е.О. Горячев

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

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

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

Таким образом, возникает задача исследования методов совмещения изображений различной природы, что необходимо для разработки алгоритмов совмещения, работающих в реальном времени. В качестве таких методов представляется целесообразным использовать методы контурного анализа [2].

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

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

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

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

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

Второй алгоритм лишен этого недостатка, однако для его работы необходимо выделить на совмещаемых контурах набор как минимум из четырех «идентичных» (соответствующих) точек. Эта задача решается с помощью специального алгоритма.

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

вляется на основе либо некоторого известного алгоритма, известного из научной литературы, либо оригинального алгоритма, разработанного авторами.

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

42)=п  4^ 2=х+іу,

где 2^’ и 2^’ - точки на исходном и подлежащем совмещению с ним втором контуре соответственно, 2пр = Хпр + Іупр - комплексное число, обеспечивающее приведение точек одного изображения к соответствующим точкам другого.

Для нахождения комплексного числа 2пр необходимо найти на одном и на втором контурах по паре «идентичных» точек. В данном варианте алгоритма в качестве таких точек выбирались точки, принадлежащие концам диаметра области, т. е.

{Мі,М2}= а^шах р

,М;єдВ

Точки Мі,М2 образуют вектор а = (х2 -хі;У2 -Уі), координаты которого и являются соответственно действительной и мнимой частями комплексного числа 2пр =(х2 - хі)+ І  (У2 - Уі).

Алгоритм нахождения точек Мі, М 2, принадлежащих концам диаметра, достаточно прост. Берется произвольная точка М на контуре, выбирается направление обхода контура, и в этом направлении находится ближайшая точка М', на которой реализуется локальный максимум

р

М^, М; єдВ *

Затем точка М' принимается за начальную, и теперь уже для нее находится следующая точка, на которой достигается локальный максимум вида (3). После полного обхода контура в выбранном направлении из множества локальных максимумов выбирается глобальный и, как следствие, находятся искомые точки Мі, М 2.

На рис.і а и б представлены контуры одной и той же группы островов, снятые с запаздыванием в несколько секунд, вместе с найденными диаметрами. Контуры островов выделялись с помощью алгоритма углового коэффициента [5]. На рис. і,в приведен результат совмещения контуров островов по изложенному алгоритму.

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

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

а б в

Рис. 1. Исходные контуры и результат совмещения: а -первый контур; б - второй контур; в - результат совмещения контуров с помощью диаметральных точек

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

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

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

' Ні і Н12 Ніз"

н = Н21 2 2 Н Н23

ч Н31 Н31 1 )

на вектор Хі = (х, Уі ,1)Т, і = 1, п, первые две компоненты которого являются координатами і - й точки совмещаемого контура (изображения). Элементы Ну матрицы гомографии находятся в результате решения систе-

мы линейных алгебраических уравнений

V • Он = У',

где V - матрица размера 8 х 8:

х1 У1 1 0 0 0 - х1 / • х1 / - х1 • У1

х2 у 2 1 0 0 0 - х 2 • х 2 - х 2 • у 2

х3 У3 1 0 0 0 - х 3 • х 3 - х 3 • у3

х4 у 4 1 0 0 0 - х 4 • х 4 - х 4 • У 4

0 0 0 х1 У1 1 - х1 • у1 - У1 • у1

0 0 0 х2 у 2 1 - х 2 •у 2 - у 2 •у 2

0 0 0 х3 у 3 1 - х 3 • у3 - У3 • у3

0 0 0 х4 у 4 1 - х 4 • у 4 - у 4 • у 4

Он - вектор-столбец размера 8 х1:

ОН = (Н11;Н12;Н13;Н21;Н22;Н23;Н31;Н32)Т ;

У' - вектор-столбец размера 8 х 1: У' = (х'; х2; х3; х4; у'; у2; у3 ; у4 ).

В составе матрицы V и вектора У' числа Хі, Уі , і = 1,2,3,4 и числа х', у', і = 1,2,3,4 соответственно координаты четырех точек на одном контуре (изображении) и отвечающих им «идентичных» четырех точек на втором контуре.

Опишем по шагам алгоритм совмещения контуров с помощью матрицы гомографии.

1) Находим четверку точек

Х1 (х1;У1), X2(х2;У2), X3 (Х3;У3), X4(Х4;У4) на первом контуре (рис. 2,а) и отвечающие им четыре точки Х1(х';у'),X2(х2;у2),X3(х3;у3),X4(х4;у4) на втором контуре (рис. 2,б).

2) Формируем матрицу V и вектор столбец Он .

3) Решаем систему линейных алгебраических уравнений V • ОН = У':

ОН = V_1 • У'

и формируем из элементов вектора-столбца Он матрицу гомографии Н.

4) Осуществляем совмещение контуров Г и Г' - находим либо образы точек Хі є Г по формуле X' = н • X, либо образы точек X' є Г' по

формуле X = н_1 • X', т. е. налагаем либо контур Г на контур Г', либо наоборот - контур Г' на Г.

На рис. 2,в приведен результат совмещения контуров островов по данному алгоритму.

а б в

Рис. 2. Контуры для совмещения с выбранными точками и результат совмещения (вариант 1): а -первый контур; б - второй контур; в -результат совмещения контуров с помощью матрицы гомографии

От выбора соответствующих наборов из четырех пар точек на совмещаемых контурах может существенно зависеть качество совмещения. На рис. 3 а и б изменено положение только одной пары X 3 и X 3 из четырех пар точек по сравнению с рис. 2 а и б соответственно.

а б в

Рис. 3. Контуры для совмещения с выбранными точками и результат совмещения (вариант 2): а -первый контур; б - второй контур; в -результат совмещения контуров с помощью матрицы гомографии

В результате такого выбора соответствующих точек получено практически идеальное совмещение контуров (рис. 3,в).

Рассмотренный вариант совмещения контуров с помощью матрицы гомографии предполагает идентификацию на совмещаемых контурах как минимум четырех пар соответствующих точек. Ниже излагается алгоритм поиска идентичных точек на совмещаемых контурах с помощью аппарата комплексного контурного анализа (ККА).

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

Алгоритм основан на выборе в качестве вершин аппроксимирую-

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

В каждой точке контура вычисляется косинус

угла между прямыми ^ : у = ^ х и ^ : У = ^ х, проходящими через данную точку и через т пикселей слева и справа от этой точки. Оптимальные оценки угловых коэффициентов каждой прямой находится методом наи-

В этой формуле (х-; у-) - координаты точек Л- , I = 1, т в подвижной системе координат Оху для углового коэффициента к и (х-; у-) - координаты точек В- , I = 1, т - для углового коэффициента к2 .

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

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

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

ооб а -

Р1Р2+К к2

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

Каждый подконтур одного контура в дальнейшем сравнивается со всеми подконтурами другого контура с целью нахождения похожих участков имеющихся контуров. В качестве меры сходства подконтуров предлагается использовать автокорреляционную функцию в комбинации с дополнительными параметрами вершины. Автокорреляционную функцию предлагается вычислять следующим образом. Пусть Г = ((х1, у), (х2, у2),..., (хп, уп)} - координатное описание контура Г. Тогда автокорреляционная функция представляет собой вектор, компоненты которого

Для выявления локального сходства контуров предлагается для каждого построенного подконтура вычислить автокорреляционную функцию

рого контура с некоторым фиксированным подконтуром у 0 первого контура по формуле

Полученные значения Dm сравниваются с некоторым заданным порогом. Подконтур ут включается в множество контуров, близких к под-контуру у0, если Dm < e, и исключается в противном случае.

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

Альтернативный и менее затратный вариант поиска идентичных точек основан на вычислении в каждой вершине аппроксимирующего многоугольника критерия 8 ^ = 8(М1, М ^^) «похожести» углов АМ-+1 и

где

т=1

т=1

(Тк }П=0 (3). Затем вычислить меру сходства каждого подконтура ут вто

к=1

АМ_,М 'М

] -ММ+1-

cos ai - cos b

al - k b1 a2 - k b2

II" al + bl II" a2 +

Здесь k = , где Pi, P2 - периметры первого и второго контуров

P2

соответственно.

Для вычисления значения критерия 8 j

1) Фиксируем произвольную точку Mi из списка {Mi на первом контуре и формируем векторы Щ = MiM i _1 и «2 = MiM i+1 .

Вычисляем cos ai = (a1, f21.

\a1\' Щ2

2) Берём произвольную точку Mj из списка {mj на втором

контуре, формируем векторы b = M'jM'j _1 и &2 = MjMj+1.

(b

Вычисляем cos b j = |Ы

, =(bl^ j lb I •

I 1 ^2]

3) Вычисляем значение критерия 8у = 8(М;, М у).

Проходим все точки М'у второго контура из списка {Му .

4) Находим индекс у о точки Муо, для которой

8(М;, Mj) = шт 8 у, у = 1, т,

те. Уо = а^плп8у .

У=1, т

5) Переходим к следующей точке МI+1 первого контура и выполняем вновь процедуры 1).. .5) по всем точкам М'у, у = 1, т второго контура.

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

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

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

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

Список литературы

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

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

3. Логинов А.А., Новиков А.И., Саблина В.А., Щербакова О.В. Исследование возможности применения комплексного контурного анализа в задачах классификации и совмещения контуров // Вестник РГРТУ, №1 (выпуск 43). Рязань, 2013. С. 20-25.

4. Ларкин Е.В., Рудианов Н.А., Ву Зуй Нгхиа. Поле зрения ТВ-модуля при наличии эффекта «загораживания» // Интеллектуальные и информационные системы. Материалы Всероссийской научно-технической конференции «Интеллект-2011». - Тула: Изд-во ТулГУ, 2011. С. 66-69.

5. Никифоров М.Б., Новиков А.И., Саблина В.А., Щербакова О.В. Алгоритм выделения границ перепада яркости при обработке видеоизображений // Информационные и телекоммуникационные технологии, № 18, 2013. С. 17-24.

6. Sablina V.A., Novikov A.I., Nikiforov M.B., and Loginov A.A. “An Approach to the Superimposition Problem in Multispectral Computer Vision Systems”, 2nd Mediterranean Conference on Embedded Computing (MECO) Proceedings. Budva, Montenegro: IEEE Catalog Number CFP1339T-ART, 2013. P. 117-120.

Новиков Анатолий Иванович, канд. эконом. наук, доц., доц. каф. высшей математики, novikovanatoly@,yandex.ru, Россия, Рязань, Рязанский государственный радиотехнический университет,

Саблина Виктория Александровна, канд. техн. наук, доц. каф. ЭВМ,

sablina.v.a@evm.rsreu.ru, Россия, Рязань, Рязанский государственный радиотехнический университет,

Горячев Евгений Олегович, магистрант, goryacheoagmail.com, Россия, Рязань, Рязанский государственный радиотехнический университет

CONTOUR ANALYSIS APPLICATION FOR IMAGE SUPERIMPOSITION

A.I. Novikov, V.A. Sablina, E.O. Goryachev

The research reveals a relatively high efficiency of contour analysis to solve problems of pattern recognition contours and their superimposition, as well as the possibility of its application for image superimposition of different nature in the development of multispectral computer vision system.

Key words: image, contour, contour analysis, complex plane, matrix of homography.

Novikov Anatoly Ivanovich, candidate of economical sciences, docent, docent of Higher Mathematics Department, no viko vanatolya, yandex. ru, Russia, Ryazan, Ryazan State Radio Engineering University,

Sablina Victoria Alexandrovna, candidate of technical sciences, docent of Electronic Computers Department, sablina. v. a@evm. rsreu. ru, Russia, Ryazan, Ryazan State Radio Engineering University,

Goryachev Evgeny Olegovich, student, goryacheoagmail. com, Russia, Ryazan, Ryazan State Radio Engineering University

УДК 004.932

ПОСТРОЕНИЕ СИСТЕМЫ ВИДЕОАНАЛИТИКИ

В. Л. Токарев, Д. А. Абрамов

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

Ключевые слова: система видеоаналитики, выделение движущихся объектов.

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

Одной из наиболее сложных и актуальных задач обработки видеоизображения является проблема выделения и распознавания движущихся объектов при наличии различного рода помех и создание на этой основе системы мониторинга. Главная задача таких систем - информировать чело-