Выделение отличий на изображениях с помощью референтных EMD-фильтров

ВЫДЕЛЕНИЕ ОТЛИЧИИ НА ИЗОБРАЖЕНИЯХ С ПОМОЩЬЮ РЕФЕРЕНТНЫХ ЕМБ-ФИЛЬТРОВ

М.А. Лебедев 1, А.Ю. Рубис 1, Ю.В. Визильтер 1, О.В. Выголов 1 1 ФГУП «Государственный научно-исследовательский институт авиационных систем (ФГУП «ГосНИИАС»)», Москва, Россия

Аннотация

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

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

Цитирование: Лебедев, МА. Выделение отличий на изображениях с помощью референтных ЕМБ-фильтров / М.А. Лебедев, А.Ю. Рубис, Ю.В. Визильтер, О.В. Выголов // Компьютерная оптика. - 2018. - Т. 42, № 2. - С. 291-296. - Б01: 10.18287/2412-6179-2018-42-2-291-296.

Введение

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

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

1. Морфология Пытьева

Рассмотрим мозаичную модель изображения, используемую в морфологии Пытьева [4]:

I (х, у) = Хе (х, у),

где п - число областей разбиения Е кадра О на связные непересекающиеся области постоянной яркости

Е = {Е1, ..., Еп}; 1= (/1 ...,I) - вектор действительных значений яркости, соответствующих каждой области разбиения; Хе (х,у)е{0,1}- характеристическая функция г'-й области яркости:

|1, если (х,у) е Ег,

Хе (х, У) =

0, в противном случае.

Разбиение может быть получено посредством процедуры сегментации. Мозаичная форма изображения - это многообразие в пространстве изображений (линейное подпространство Ее Ь2(О)):

Р = {/(х,у) = ¿/^(х,у), 1 = {/1,...,/п}, 1 е яп}.

г=1

При этом для любого изображения gе ь2(0.) и как морфологический оператор в пространстве изображений (проектор на данное многообразие, содержащее изображения с данной структурой, в данном случае проекция изображения g на форму Е):

gЕ (х, у) = pЕg (х, у) = £ gft ХЕ (х, у),

г=1 ' '

gf¡ = (Хе ,g)/||ХЕ'|г , ' = !,•••,п.

Численной мерой сходства изображения с формой является нормированный морфологический коэффициент корреляции (МКК):

Км (g, Е) = Км(I, О) =

1к - Р> g|l

II/ - Р>/II

где Р0/=/0 = теап(/ (х, у)), Pog = go = теап^(х, у)) -средние значения яркостей проецируемых изображений.

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

а?е = к- ,

А/е =| f - PGf\ .

2. Проективные ЕМБ-морфологии мозаичных изображений

Рассмотрим случай, когда мозаичное тестовое изображение к(х, у) = Е;=1,..,т к] Хоу (х, у) сравнивается с формой эталонного изображения (1), где Хоу (х, у), Хк (х, у)е {0, 1} представляют собой характеристические функции, а к], - значения яркости для областей мозаичного разбиения кадра Gj и с площадями $ и $ соответственно.

Матрицей взаимного сходства пары мозаичных форм ¥ и О будем называть матрицу Н = [йу]пхт, такую что

й. > 0, I = 1,..., п, ] = 1,..., т,

у ^

X = й, ] = 1,_,т X й = й, 1 = 1,_,n,

г=1,_,п ] =1,_,т

X X <~.

г=1,___,п у =1,_,т

Соответственно, операции взаимной диффузной мозаичной фильтрации изображений f и к по матрице сходства областей Н = [йу] пхт определяются как

п

gFG Н (X, У) = Н к (X, У) = X (X, У^

1=1

кЕО,= X Руку, р] = , Й = X й.

]=1,_,т / I=1,_,т

т

^ Н (x, У) = Н f (X, У) = X (x, УХ

у=1

^ = X , ъ = к]1ку, йу = X К.

г=1,_,п / к =1 ,_,п

Суперпозиция Роеон = Роен Реон определяет референтный диффузный фильтр.

Пусть теперь каждая область мозаичной формы характеризуется некоторым вектором признаков V из метрического пространства признаков V с метрикой йу. И пусть ядро взаимного сходства представляется как набор площадей областей и их попарных пересечений: Н = 8 = [$у]пхт. При этом площади областей & и $ являются фиксированными (это наблюдаемые величины), а величины {$]}пхт будем считать переменными и подбирать, исходя из наших представлений о сходстве областей. Геометрический смысл такого подхода заключается в том, что площадь областей анализируемой тестовой формы рассматривается как некий «ресурс», который полностью делится между областями референтной эталонной формы на основе следующих принципов и ограничений:

• ни одна область не может отдать больше площади, чем у нее есть;

• ни одна область не может принять больше площади, чем у нее есть;

• процесс распределения площадей областей должен выполняться в соответствии с их сходством до полного исчерпания «ресурса», то есть область, более похожая на текущую, получит больше площади;

• распределение (перетекание) площадей должно быть оптимальным для всего изображения в целом, а не для каждой области в отдельности.

Преимуществом такого подхода по сравнению с подходом из [1] является, прежде всего, то, что если в качестве референтной формы для тестового изображения g мы используем его собственную эталонную форму G, то в результате фильтрации, основанной на описанных принципах, изображение не изменится. То есть такая фильтрация проективна, как и традиционное Пытьевское проецирование (2). В самом деле, если G = F, то для каждой области из G у нас есть одна в точности соответствующая ей область в F, причем сходство с этой областью максимально, а объемы «ресурса», который может быть передан и, соответственно, принят - равны. Следовательно, каждая область передаст весь свой «ресурс» только одной соответствующей области, так что результат референтной фильтрации будет идентичен исходному тестовому изображению.

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

Для численной реализации изложенных выше принципов введем EMD-метрику (Earth Mover's Distance [2]) для сравнения множества взвешенных пар форм-разбиений как решение оптимизационной задачи:

dEMD (F, G) =

= minH X X hd

j=1,...,m i=1,...,n

где dv(v(Fi),v(Gj)) - некоторая заданная метрика сравнения векторов признаков формы областей; hj - парные веса из матрицы H, удовлетворяющие условиям (3). Для нахождения оптимальной матрицы взаим-

ного сходства мозаичных форм ^ и О задача (3) решается методом линейного программирования.

Матрицу взаимного сходства Н, формируемую описанным способом, будем называть ЕМБ-матрицей взаимного сходства на базе признаков V и метрики Взаимный диффузный фильтр с ЕМБ-матрицей взаимного сходства будем называть взаимным ЕМБ-фильтром. Референтный диффузный фильтр с ЕМБ-матрицей взаимного сходства будем называть референтным ЕМБ-фильтром.

Как показано выше, взаимные и референтные диффузные фильтры с ЕМБ-матрицей взаимного сходства являются проекторами (идемпотентными операторами). Таким образом, взаимные и референтные диффузные фильтры с ЕМБ-матрицей взаимного сходства можно называть соответственно взаимными и референтными ЕМБ-проекторами, а результаты такой фильтрации соответственно взаимными и референтными ЕМБ-проекциями.

3. Алгоритм морфологического выделения отличий

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

Алгоритм состоит из следующих основных этапов:

1) Сформировать векторы признаков областей v(F') и v(Оj) из форм Е и О соответственно, таким образом, чтобы они не зависели от яркости и расположения областей, но описывали только их форму. В экспериментах в качестве дескрипторов формы использовались бинарные маски областей.

2) Выбрать базовую функцию йЕ, позволяющую попарно сравнивать сформированные векторы признаков областей. В экспериментах в качестве расстояния между дескрипторами формы используется функция нормы симметрической разности ^(Е')^(О/)).

3) Сформировать ЕМБ-метрику для сравнения множества взвешенных пар форм-разбиений йЕМБ (Е, О) согласно формуле (4) с ограничениями для матрицы взаимного сходства, описанными в (3).

4) Найти оптимальное решение задачи линейного программирования ¿емб (Е, О)^штн одним из множества известных алгоритмов.

5) Вычислить референтно-сглаженное изображение Роеон g.

6) Вычислить нормализованную разность изображений ^ - Роеон g).

7) Выделить элементы нормализованной разности, превышающие заданный порог изменения яркости.

4. Результаты экспериментов

Тестирование реализованной схемы референтной ЕМБ-фильтрации проводились на модельных и реальных изображениях. На рис. 1 показаны примеры выделения отличий при помощи суперпозиции Пыть-евских проекторов (середина) [4] и морфологического выделения отличий на мозаичных изображениях на основе референтных ЕМБ-фильтров. Как видно из примера, незначительные изменения в геометрии сцены могут оказывать влияние на результат суперпозиции Пытьевских проекторов: помимо выделения нового объекта сцены, появляются артефакты. Результатом сравнения с изображением, полученным при помощи морфологического выделения отличий на основе ЕМБ-фильтров, является выделение только новых объектов сцены.

Рис. 1. Выделение отличий в случае изменения геометрии сцены и добавления новых объектов на примере суперпозиции Пытьевских проекторов

Для применения предложенного метода выделения отличий на основе ЕМБ-фильтров на реальных изображениях необходимо обеспечить устойчивое построение мозаичных форм к яркостным и геометрическим изменениям. В экспериментах был использован алгоритм сегментации [5], результат которого сильно зависит от ручных параметров настройки. На рис. 2 приводится морфологическое выделение отличий на основе референтных ЕМБ-фильтров на примере реальных изображений.

Рис. 2. Морфологическое выделение отличий на основе референтных ЕМО-фильтров на реальных изображениях: эталонное изображение

Заключение

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

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

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

Благодарности

Работа выполнена при поддержке РНФ, грант 1611-00082.

Литература

1. Лебедев, М.А. Выделение отличий на мозаичных изображениях на основе референтных фильтров / М.А. Лебедев, А.Ю. Рубис, В.С. Горбацевич, Ю.В. Визильтер, О.В. Выголов // Компьютерная оптика.

- 2016. - Т. 40, № 1. - С. 80-86. - DOI: 10.18287/24126179-2016-40-1-80-86.

2. Rubner, Y. The earth mover's distance as a metric for image retrieval / Y. Rubner, C. Tomasi, L.J. Quibas // International Journal of Computer Vision - 2000. - Vol. 40, Issue 2. - P. 99-121 - DOI: 10.1023/A:1026543900054.

3. Vizilter, Yu. Shape-based image matching using heat kernels and diffusion maps / V. Gorbatsevich, A. Rubis, S. Zheltov // ISPRS Technical Commission III Symposium.

- 2014. - Vol. XL-3. - P. 357-364. - DOI: 10.5194/isprsarchives-XL-3-357-2014.

4. Pyt'ev, Yu. Morphological image analysis / Yu. Pyt'ev // Pattern Recognition and Image Analysis. - 1993. - Vol. 3, Issue 1. - P. 19-28.

5. Felzenszwalb, P.F. Efficient graph-based image segmentation / P.F. Felzenszwalb, D.P. Huttenlocher // International Journal of Computer Vision. - 2004. - Vol. 59, Issue 2. -P. 161-182. - DOI: 10.1023/B:VISI.0000022288.19776.77.

6. Визильтер, Ю.В. Диффузные морфологии мозаичных изображений / Ю.В. Визильтер, М.А. Лебедев, А.Ю. Рубис // Научно-техническая конференция «Техническое зрение в системах управления» (ТЗСУ - 2015): Тезисы. - 2015. - С. 110-111.

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

Лебедев Максим Алексеевич, 1990 года рождения, в 2013 году окончил «Московский авиационный институт (национальный исследовательский университет)». В настоящее время является инженером 2-й категории ФГУП «ГосНИИ Авиационных систем» (ГосНИИАС). Является автором и соавтором более 20 научных трудов. Круг научных интересов: обработка изображений, системы улучшенного видения, распознавание образов, программирование. E-mail: mlebedev@gosniias. ru.

Рубис Алексей Юрьевич, 1986 года рождения, в 2009 году окончил ФГБОУ ВПО «Московский авиационный институт (национальный исследовательский университет)». В настоящее время является инженером ФГУП «ГосНИИ Авиационных систем» (ГосНИИАС). Является автором и соавтором 17 научных трудов. Круг научных интересов: обработка изображений, системы улучшенного видения, распознавание образов, программирование. E-mail: arubis@gosniias. ru.

Визильтер Юрий Валентинович, 1970 года рождения, в 1992 году окончил ФГБОУ ВПО «Московский авиационный институт (национальный исследовательский университет)». В 1997 г. защитил кандидатскую, а в 2009 году - докторскую диссертацию. В настоящее время является начальником подразделения ФГУП «Гос-НИИ Авиационных систем» (ГосНИИАС). Опубликовал более 80 научных работ. Область научных интересов: обработка и анализ изображений, цифровая фотограмметрия, машинное зрение, математическая морфология, распознавание образов, машинное обучение, биометрия. E-mail: viz@gosniias.ru .

Выголов Олег Вячеславович, 1977 года рождения, в 2000 году окончил ФГБОУ ВПО «Московский авиационный институт (национальный исследовательский университет)». В 2007 г. защитил кандидатскую диссертацию, кандидат технических наук. В настоящее время является начальником лаборатории ФГУП «ГосНИИ Авиационных систем» (ГосНИИАС). Область научных интересов: обработка и анализ изображений, математическая морфология, комплексирование информации в технических системах, навигация и управление мобильными объектами с использованием технического зрения. E-mail: o. vygolov @gosniias. ru .

ГРНТИ: 28.23.15

Поступила в редакцию 29 декабря 2017 г. Окончательный вариант - 20 февраля 2018 г.

DETECTING IMAGE DIFFERENCES BASED ON REFERENCE EMD-FILTERS

M.A. Lebedev1, A.Yu. Rubis1, Yu.V. Vizilter1, O.V. Vygolov1

1 Federal State Unitary Enterprise "State Research Institute of Aviation Systems" (FGUP "GosNIIAS"), Moscow, Russia

Abstract

In our previous works dealing with detecting differences in images in the case of substantial variations in brightness and geometry of an object, we proposed a morphological scheme for image analysis based on diffusion and reference mosaic filters. The filters were defined through the heat kernels of the similarity of image fragments. In this paper, we propose an implementation of this morphological scheme using original reference Earth mover's distance (EMD) filters, in which the optimal matrices of the mutual similarity of mosaic forms are calculated through a linear programming method.

Keywords: mathematical morphology, image matching, diffusion maps.

Citation: Lebedev MA, Rubis AYu, Vizilter YuV, Vygolov OV. Detecting image differences based on reference EMD-filters. Computer Optics 2018; 42(2): 291-296. - DOI: 10.18287/24126179-2018-42-2-291-296.

A cknowledgements: The work was funded by the Russian Science Foundation (RSF), grant No. 16-11-00082.

References

[1] Lebedev MA, Rubis AY, Gorbatsevich VS, Vizilter YV, Vygolov OV. Change detection in segmented images based on reference filters [In Russian]. Computer Optics 2016; 40(1): 80-86. DOI: 10.18287/2412-6179-2016-40-1-80-86.

[2] Rubner Y, Tomasi C, Quibas LJ. The earth mover's distance as a metric for image retrieval // International Journal of Computer Vision 2000; 40(2): 99-121. DOI: 10.1023/A: 1026543900054.

[3] Vizilter Yu, Gorbatsevich V, Rubis A, Zheltov S. Shape-based image matching using heat kernels and diffusion

maps. ISPRS Technical Commission III Symposium 2014; XL-3: 357-364. DOI: 10.5194/isprsarchives-XL-3-357-2014.

[4] Pyt'ev Yu. Morphological image analysis. Pattern Recognition and Image Analysis 1993; 3(1): 19-28.

[5] Felzenszwalb PF, Huttenlocher DP. Efficient graph-based image segmentation. International Journal of Computer Vision 2004; 59(2): 161-182. DOI: 10.1023/B:VISI.0000022288.19776.77.

[6] Vizilter YuV, Lebedev MA, Rubis AY. Diffuse morphology of mosaic images. Scientific and Technical Conference "Technical Vision in Control Systems" (TVCS - 2015) 2015: 110-111.

Author's information

Maxim Alekseevich Lebedev (b. 1990) graduated from Moscow Aviation Institute (National Research University) in 2013. Currently he works as the engineer of the 2-nd category at the FGUP "GosNIIAS". Author and coauthor of 20 scientific papers. Research interests are image processing, enhanced vision systems, pattern recognition, programming. E-mail: mlebedev@gosniias.ru .

Aleksey Yurievich Rubis (b.1986) graduated from Moscow Aviation Institute (National Research University) in 2009. Currently he works as the engineer of the 2-nd category at the FGUP "GosNIIAS". Author of 17 scientific papers.

Research interests are image and video analysis, pattern recognition, programming, enhanced vision systems. E-mail: E-mail: arubis@gosniias.ru .

Yuri Valentinovich Vizilter (b.1970) graduated from Moscow Aviation Institute (National Research University) in 1992. Since 1997 is the Candidates of Technical Sciences, 2009 - the Doctor of Technical Sciences. Currently he works as the head of department at the FGUP "GosNIIAS". Author of more than 80 scientific papers. Research interests are processing and image analysis, digital photogrammetry, computer vision, mathematical morphology, pattern recognition, machine learning, biometry. E-mail: viz@gosniias.ru .

Oleg Viacheslavovich Vygolov (b.1977) graduated from Moscow Aviation Institute (National Research University) in 2000 and received Ph.D. degree in Technical Sciences in 2007. He has been working at FGUP "GosNIIAS" since 2000, currently holds the position of head of laboratory for Enhanced and Synthetic Vision Systems. His research interests include image processing and analysis, mathematical morphology, data fusion in technical systems, vision-based mobile objects navigation and guidance. E-mail: o.vygolov@gosniias.ru .

Received December 29, 2017. The final version - February 20, 2018.