Анализ мер близости для поиска объектов по шаблону

УДК 004.932.72

DOI 10.21685/2072-3059-2018-3-4

И. В. Борисова, В. Н. Легкий, Д. А. Утев, С. А. Кравец, Д. Е. Демидов

АНАЛИЗ МЕР БЛИЗОСТИ ДЛЯ ПОИСКА ОБЪЕКТОВ ПО ШАБЛОНУ

Аннотация.

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

Материалы и методы. Обнаружение объектов производится методом поиска экстремума критериальной функции. Рассматриваются следующие меры близости: корреляционная, компарационная и метрика расстояний до границ (Chamfer Distance). Анализ мер близости проводится на телевизионных и теп-ловизионных изображениях сцены с имитацией сложного фона и моделями наземной техники.

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

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

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

I. V. Borisova, V. N. Legkiy, D. A. Utev, S. A. Kravets, D. E. Demidov

ANALYSIS OF PROXIMITY MEASURES FOR SEARCHING OBJECTS USING THE STANDARD

Abstract.

Background. The analysis of proximity measures for comparison of images from different spectral ranges is carried out for the problem of search targets corresponding to the standard. Fragments of real images and generated pseudo-images are used as standards. The goal of the research is to choose a measure of proximity that provides stable object detection by their reference image.

© Борисова И. В., Легкий В. Н., Утев Д. А., Кравец С. А., Демидов Д. Е., 2018. Данная статья доступна по условиям всемирной лицензии Creative Commons Attribution 4.0 International License (http://creativecommons.org/ licenses/by/4.0/), которая дает разрешение на неограниченное использование, копирование на любые носители при условии указания авторства, источника и ссылки на лицензию Creative Commons, а также изменений, если таковые имеют место.

Materials and methods. Object detection is performed by searching for the extremum of the criterion function. The following proximity measures are considered: correlation, comparison, and Chamfer Distance. Analysis of proximity measures is carried out in television and thermal images of the simulated scene with models of ground equipment and complex background.

Results. It is shown that the contour and gradient orientation provide fewer errors of target detection compared to brightness. The width of the contour in binary images must be consistent with the number and size of the background elements.

Conclusions. The percentage of correct detection is higher when using a comparison measure than using normalized and binary correlation. The best results were obtained using Chamfer Distance, which does not require an exact match of the contours. This is important if the object and the standard don't match perfectly.

Keywords: image processing, target detection, measure of proximity, thermal image, gradient orientation.

Введение

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

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

1. Постановка задачи

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

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

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

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

2. Меры близости

2.1. Корреляционные меры близости

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

N-1K-1 _ _

г

X=0 у=0

или нормированной корреляционной функции (коэффициента корреляции):

N-1К-1 _ _

2 2

Ж-1, У1) = -7—-,

где t( ) - яркость элемента текущего фрагмента изображения; g() - яркость элемента эталона размером NxK; t - средняя яркость по фрагменту; g -средняя яркость эталона; Dt и Dg - дисперсии яркости по фрагменту и эталону соответственно.

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

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

N-1K -1

2 2^

x=0 y=0 x=0 y=0

где tb() и gb() - значения элементов фрагмента бинарного изображения и эталона соответственно.

Координаты объекта на изображении определяются по максимуму функции (1) или (2).

2.2. Расстояние до границ

Еще одной мерой близости бинарных контурных изображений является метрика Chamfer Distance [6]. Будем считать, что пиксели со значением 1 соответствуют границам объектов. Согласно метрике Chamfer Distance для каж-

дого ненулевого пикселя одного бинарного контурного изображения вычисляется расстояние до ближайшего ненулевого пикселя другого бинарного изображения и все найденные расстояния суммируются. Ближайшую границу на изображении можно найти с помощью преобразования Distance Transform [6]. Матрица расстояний до границ, соответствующая изображению, заполняется следующим образом: в местах контура ставятся нули, а в остальных точках - число пикселей до ближайшего контура. Далее найденная матрица совмещается с бинарным эталоном, все значения матрицы, соответствующие ненулевым точкам, суммируются:

Компарационная мера близости основана на поэлементном сравнении квантованных значений направления градиента яркости объекта и эталона [1, 7]. Этим методом могут сравниваться изображения, полученные при разных условиях освещения, в разное время и в разных диапазонах или изображения реальных сцен и контурных эталонов.

Будем рассматривать локальные окрестности для каждой точки изображения. Размер окрестностей выбирается в зависимости от сюжета изображения от 3 X 3 элементов до 8 X 8. Разделим окрестности изображения на условные группы (классы) в зависимости от ориентации градиента яркости. Ориентация градиента является непрерывной величиной, лежащей в интервале [0, 2п) или [0, п) при использовании беззнакового градиента яркости. Но мы будем рассматривать ориентацию как дискретную величину, принимающую некоторое небольшое количество значений. Для дискретных изображений, заданных на квадратной решетке, выберем шаг дискретизации ориентации градиента равный п/4.

Для того чтобы найти ориентацию градиента яркости, проведем анализ энергии двумерного дискретного спектра Фурье по направлениям [1]. Двумерное дискретное преобразование Фурье матрицы отсчетов текущей окрестности изображения V размером п X п определяется в виде

Найдем суммы элементов энергетического спектра в направлениях, составляющих углы 0, п/4, п/2, 3п/4 с горизонталью, с помощью следующего оператора:

N -1K -1

x=0 у=0

где T - матрица расстояний до границ.

Координаты объекта определяются по минимуму функции (3).

2.3. Компарационная мера близости

где i2 = -1.

E2 =

и—1 In—1

£F2

u =1 V u=1

Направление, в котором будет получена максимальная суммарная энергия, определит ориентацию градиента яркости и номер класса окрестности:

п

Em = max Е,, 0 = m •—, V e Cm ,

j=0,...3 4

где Cj, j = 0,1,...,3 - классы окрестностей; 0 - направление градиента.

Номер класса окрестности рассматриваемой точки изображения принимается в качестве признака этой точки. Таким образом, формируется псевдоизображение, каждая точка которого кодируется номером класса окрестности.

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

Для определения степени анизотропии окрестности будем сравнивать максимальную суммарную энергию Em с энергией, полученной в перпендикулярном направлении En . Будем использовать следующий критерий для проверки окрестности на изотропность:

Г En / Em < Q, V g C4,

jEn /Em > Q, Ve C4,

где Q - порог анизотропности, C4 - класс изотропных окрестностей.

Предположим, что номер класса окрестности является случайной величиной, а его значения равновероятны, т.е. равновероятны анизотропные классы окрестностей. Возьмем два различных фрагмента размером W элементов и оценим вероятность того, что при совмещении этих фрагментов классы окрестностей совпадут в М точках. Эта вероятность рассчитывается по формуле Бернулли:

P

IM J

где р - вероятность совпадения классов в точке; q - вероятность несовпадения, p + q = 1.

Поскольку фрагментов, похожих на эталон, на изображении существенно меньше, чем остальных, для подавляющей части изображения совпадение с эталоном будет носить случайный характер. Таким образом, выполняя сканирование изображения выбранным эталоном, мы получим распределение вероятностей совпадения классов, близкое к биномиальному. При пороге анизотропности Q = 1 класс изотропных окрестностей отсутствует и распределение (8) имеет максимум в точке W /4 (рис. 1). При Q < 1 начинает формиро-

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

0,08 0,07 0,06 0,05 0,04 0,03 0,02 0,01 0,00

_ Q = Qn О ->0

---I M

51 64 128 256

Рис. 1. Схема смещения распределения при изменении порога анизотропности, Ж = 256

При уменьшении порога Q от 1 до некоторого значения Qo максимум распределения (8) смещается влево по оси М до точки Ж /5. Этой точки максимум достигает, когда все классы окрестностей становятся равновероятны. Дальнейшее уменьшение порога приводит к преобладанию изотропных окрестностей и максимум начинает смещаться вправо по оси М вплоть до Ж при Q = 0 . Этот эффект называется эффектом отскока [1], а точка Qo - точкой отскока. Для того чтобы найти точку отскока, строится кривая смещения координаты максимума реального распределения для разных порогов.

Мерой близости двух закодированных изображений одного размера служит компарационная функция:

N-1К -1

5

х=0 у=0

5 ((х + X, у1 + у), gk (X, у)) =

[1, tk (X1 + X, у + у) = gk (X, у),

[0, tk (Xi + х, у + у) Ф gk (X, у),

где ^(') и gk(') - значения элементов фрагмента закодированного изображения и закодированного эталона соответственно.

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

пик распределения фоновых элементов максимально смещен влево по оси М (рис. 1).

3. Экспериментальные результаты

Для сравнения мер близости применительно к привязке изображений была создана сцена с имитацией сложного фона и моделями различной техники. Тепловизор и телевизионная камера были конструктивно соединены и согласованы по полям зрения, было выполнено согласование масштаба изображений. Парные телевизионные и тепловизионные изображения принимались сериями по 10-15 кадров, затем сцена изменялась. В течение серии объект перемещался по сцене, изменялось освещение. Пример типичных парных кадров приведен на рис. 2.

а) б)

Рис. 2. Пример парных кадров для привязки с выделенными фрагментами: а - телевизионное; б - тепловизионное изображения

Результаты исследования сведены в табл. 1. На первом этапе исследования проводилась привязка изображений одного спектрального диапазона, но разных кадров серии (в табл. 1 обозначено ТВ-ТВ и ТПВ-ТПВ). Все меры близости показали стабильную привязку. Значения невязки, т.е. разности между координатами реперного фрагмента и фрагмента, полученного после обратного поиска, разбивались на группы. Если полученная невязка составляла от 1 до 5 пикселей, то выполнялась повторная привязка по полученному фрагменту. В большинстве случаев для значений первичной невязки 1-2 пикселя удавалось получить нулевую невязку. Для значений первичной невязки 3-5 пикселей в отдельных случаях также удавалось улучшить невязку.

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

При работе с бинарными изображениями использовалось два типа контуров. Перепады яркости подчеркивались оператором Собела. Для получения широкого контура амплитуда градиента считалась как среднеквадратическое значение градиентных функций и сравнивалась с порогом по методу Отсу [8]. Для получения тонкого контура дополнительно находилась точка перехода второй производной яркости через ноль. Примеры бинарных изображений

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

Таблица 1

Привязка изображений с использованием разных мер близости

Значения невязки Меры близости

Нормированная корреляция Компарация Бинарная корреляция Chamfer Distance

Тонкий контур Широкий контур Тонкий контур Широкий контур

ТВ-ТВ

0 100 % 100 % 90 % 98 % 100 % 100 %

1-2 - - 10 % 2 % - -

ТПВ-ТПВ

0 97 % 100 % 95 % 100 % 100 % 100 %

1-2 3 % - 5 % - - -

ТВ-ТПВ

0 1 % 90 % 88 % 95 % 94 % 100 %

1-2 10 % 10 % 12 % 5 % 6 % -

3-5 30 % - - - - -

>5 59 % - - - - -

а) б)

Рис. 3. Пример бинарных изображений: а - тонкий контур, б - широкий контур

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

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

Рис. 4. Примеры шаблонов

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

Таблица 2

Поиск объектов по шаблону

Меры близости

Бинарная корреляция Chamfer Distance

Компарация Тонкий Широкий Тонкий Широкий

контур контур контур контур

Обнаруженные объекты на ТПВ- 100 % 99 % 100 % 100 % 100 %

изображениях, %

Обнаруженные объекты на ТВ- 98 % 95 % 97 % 98 % 99 %

изображениях, %

Заключение

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

Лучшие результаты были получены с использованием меры близости Chamfer Distance, которая не требует точного совпадения контуров, что важно при неидеальном совпадении объекта и шаблона.

Библиографический список

1. Попов, П. Г. Практическое применение эффекта «отскока» в обработке изображений / П. Г. Попов, И. В. Борисова // Оптический журнал. - 1999. - Т. 66, № 4. -С. 94-101.

2. Блохинов, Ю. Б. Поиск трехмерных объектов на изображениях на основе динамически формируемых контурных эталонов / Ю. Б. Блохинов, А. С. Чернявский // Механика, управление и автоматика. - 2012. - № 8. - С. 181-188.

3. Цветков, О. В. Метод предварительного кодирования изображений в корреляционно-экстремальных системах / О. В. Цветков, Л. В. Тананыкина // Компьютерная оптика. - 2015. - Т. 39, № 5. - С. 738-743.

4. Новиков, А. И. Применение контурного анализа для совмещения изображений / А. И. Новиков, В. А. Саблина, Е. О. Горячев // Известия Тульского государственного университета. Технические науки. - 2013. - Вып. 9, Ч. 1. - С. 260-270.

5. Zitova, B. Image registration methods: a survey / B. Zitova, J. Flusser // Image and Vision Computing. - 2003. - Vol. 21. - P. 977-1000.

6. Borgefors, G. Distance transformations in digital images / G. Borgefors // Computer Vision, Graphics, and Image Processing. - 1986. - Vol. 34, № 3. - P. 344-371.

7. Борисова, И. В. Применение ориентации градиента яркости для систем автосопровождения объектов / И. В. Борисова, В. Н. Легкий, С. А. Кравец // Компьютерная оптика. - 2017. - Т. 41, № 6. - С. 931-937.

8. Otsu, N. A threshold selection method from gray-level histograms / N. Otsu // IEEE Transactions on systems, MAN, and CYBERNETICS. - 1979. - Vol. SMC-9, № 1. -P. 62-66.

References

1. Popov P. G., Borisova I. V. Opticheskiy zhurnal [Optical journal]. 1999, vol. 66, no. 4, pp. 94-101.

2. Blokhinov Yu. B., Chernyavskiy A. S. Mekhanika, upravlenie i avtomatika [Mechanics, control and automatics]. 2012, no. 8, pp. 181-188.

3. Tsvetkov O. V., Tananykina L. V. Komp'yuternaya optika [Computer optics]. 2015, vol. 39, no. 5, pp. 738-743.

4. Novikov A. I., Sablina V. A., Goryachev E. O. Izvestiya Tul'skogo gosudarstvennogo universiteta. Tekhnicheskie nauki [Proceedings of Tula State University. Engineering sciences]. 2013, iss. 9, part 1, pp. 260-270.

5. Zitova B., Flusser J. Image and Vision Computing. 2003, vol. 21, pp. 977-1000.

6. Borgefors G. Computer Vision, Graphics, and Image Processing. 1986, vol. 34, no. 3, pp. 344-371.

7. Borisova I. V., Legkiy V. N., Kravets S. A. Komp'yuternaya optika [Computer optics]. 2017, vol. 41, no. 6, pp. 931-937.

8. Otsu N. IEEE Transactions on systems, MAN, and CYBERNETICS. 1979, vol. SMC-9, no. 1, pp. 62-66.

Борисова Ирина Валентиновна

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

E-mail: i.v.borisova@corp.nstu.ru

Borisova Irina Valentinovna Candidate of engineering sciences, associate professor, sub-department of autonomous information and control systems, Novosibirsk State Technical University

Легкий Владимир Николаевич

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

E-mail: sniios@mail.ru

Утев Дмитрий Андреевич студент, Новосибирский государственный технический университет

E-mail: yoh60438@gmail.com

Кравец Сергей Александрович аспирант, Новосибирский государственный технический университет

E-mail: santoserg@yandex.ru

Демидов Дмитрий Евгеньевич аспирант, Новосибирский государственный технический университет

E-mail: dmdem91@yandex.ru

Legkiy Vladimir Nikolaevich Doctor of engineering sciences, associate professor, head of sub-department of autonomous information and control systems, Novosibirsk State Technical University

Utev Dmitriy Andreevich Student, Novosibirsk State Technical University

Kravets Sergey Aleksandrovich Postgraduate student, Novosibirsk State Technical University

Demidov Dmitriy Evgen'evich

Postgraduate student, Novosibirsk State Technical University

УДК 004.932.72

Анализ мер близости для поиска объектов по шаблону / И. В. Борисова, В. Н. Легкий, Д. А. Утев, С. А. Кравец, Д. Е. Демидов // Известия высших учебных заведений. Поволжский регион. Технические науки. - 2018. -№ 3 (47). - С. 36-46. - БОТ 10.21685/2072-3059-2018-3-4.