ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 4, с. 76-89
РАСПОЗНАВАНИЕ ОБРАЗОВ И ОБРАБОТКА ИЗОБРАЖЕНИЙ
УДК 004.932.2
МЕРЫ СХОДСТВА И МЕТРИКИ СРАВНЕНИЯ ФОРМ МОЗАИЧНЫХ ИЗОБРАЖЕНИЙ*
© 2014 г. Ю. В. Визильтер, С. Ю. Желтов
Москва, ФГУП "ГосНИИАС" Поступила в редакцию 31.01.14 г.
Рассмотрена задача определения процедуры морфологического сравнения мозаичных форм, согласованной с морфологическим анализом Пытьева в части сравнения изображений с формами. Исследованы четыре различных способа построения такой процедуры сравнения форм на основе: поиска критических точек морфологического коэффициента корреляции; анализа свойств суперпозиции соответствующих им проекторов; оценки раствора угла между многообразиями; метрики Хаусдорфа между соответствующими многообразиями на единичной гиперсфере. Для всех подходов независимо получены меры сходства или различия мозаичных форм. При этом меры сходства, основанные на использовании первых двух подходов (коэффициенты морфологической корреляции форм), совпали, а два других подхода привели к формированию мер отличия форм, связанных с коэффициентом морфологической корреляции форм взаимно-однозначными зависимостями.
DOI: 10.7868/S0002338814040167
Введение. Любые задачи распознавания образов на изображениях так или иначе должны опираться на методы оценки их сходства или различия. При этом могут сравниваться либо непосредственно изображения, либо какие-то их описания или модели, полученные в ходе анализа изображений. Современные модельные (model-based) подходы к обнаружению и распознаванию объектов, как правило, предполагают их описание не векторами независимых признаков, а сложными структурными моделями, которые могут быть описаны, например, графами, либо грамматическими конструкциями. Если такое структурное описание реализуется непосредственно на уровне изображения, причем по такому описанию изображение может быть с той или иной точностью восстановлено, то говорят об описании формы или морфологическом описании изображения. Классическими примерами таких морфологических подходов являются широко известные морфологии Серра [1] и Пытьева [2]. Более широкий спектр возможных морфологических систем был описан в наших предыдущих работах в рамках формализма так называемой проективной морфологии [3—6].
Морфологический анализ позволяет решать различные задачи обработки видеоданных — от фильтрации и сегментации до выделения отличий. Однако использование морфологических описаний в задачах распознавания требует, прежде всего, определить некоторый набор метрик или мер сходства для сравнения изображений по форме (сравнения изображений с формой других изображений) или сравнения собственно форм изображений, описываемых в тех или иных морфологических системах.
Эта задача не столь тривиальна, поскольку морфологические модели не являются векторами независимых признаков. В частности, в морфологии Пытьева так называемые мозаичные модели описывают форму изображения как набор непересекающихся областей разбиения кадра. Как сравнивать такие разбиения между собой? Априори вообще неясно, образуют ли они метрическое пространство, и если да, то какими свойствами должна обладать соответствующая метрика, чтобы быть практически полезной. Поэтому в морфологии Пытьева решается другая проблема — предлагаются средства сравнения не форм с формами, а изображений с формами. Таким образом, несмотря на многолетнее плодотворное развитие методов морфологического анализа Пытьева, задачу морфологического сравнения мозаичных форм до сих пор нельзя считать удовлетворительно решенной.
* Работа выполнена при финансовой поддержке РФФИ (грант № 14-07-00914-а).
Данная работа посвящена разработке таких методов оценки сходства и различия мозаичных форм, которые решали бы задачу сравнения форм и при этом были полностью согласованы с пы-тьевской морфологией в части сравнения изображений с формами, являясь в этом смысле ее логическим продолжением и развитием. Ниже будут исследованы четыре различных способа решения данной задачи, которые, как будет показано в итоге, приводят к эквивалентным конструкциям оценки сходства/различия мозаичных форм, представленных компактными многообразиями в пространстве изображений.
1. Задача сравнения изображений и морфологический анализ Пытьева. Опишем кратко подход, предложенный Пытьевым. Под изображением будем понимать двумерную функцию распределения яркости на кадре
f(x, y): D ^ R, О с R2,
где D — область кадра ограниченного размера, R — множество действительных чисел, R2 — плоскость кадра; х е R, у е R — соответственно горизонтальная и вертикальная декартовы координаты точек изображения. Кадр будем считать прямоугольным, хотя в общем случае форма кадра может быть произвольной.
Изображения рассматриваются как элементы гильбертова пространства L2(D) функций с интегрируемым квадратом, и следовательно определены скалярное произведение
(f, g) = Ц/(х, y)g(x, y)dxdy,
q
норма
||f || = //)
и евклидово расстояние между изображениями
dJJ, g) = |f- g||.
Это расстояние характеризует различия между изображениями как функциями яркости. В частности, при совпадении изображений dE( f, f) = 0. Однако оно не вполне соответствует нашим элементарным интуициям относительно визуального сравнения изображений. В частности, при линейных преобразованиях яркости изображений, расстояния между ними могут существенно меняться. Поэтому для того, чтобы сравнивать изображения инвариантно к линейным преобразованиям яркости, как правило, вводится нормированный коэффициент линейной корреляции вида
K(/,g)=ми •
При этом изображения также обычно центрируют, т.е. вычитают из них среднее постоянное значение яркости по кадру. В дальнейшем мы будем предполагать, что всюду, где специально не оговорено обратное, все рассматриваемые изображения центрированы по яркости.
В рамках простейшей морфологии Пытьева [2] изображения рассматриваются как кусочно-постоянные функции вида
n
f (х, y) = X/X я(х, У), (1.1)
i=1
где n — число областей разбиения F кадра D на связные непересекающиеся области постоянной яркости, F = {F1, ..., Fn}; f = (f1, ..., fn)T — вектор значений яркости, соответствующих каждой области разбиения; %л(х, y) е {0, 1} — характеристическая функция i-й области яркости:
(1, если (х, у) е F;
X в(х, У) =•.
[0 в противном случае.
Такие изображения называются мозаичными. Форма мозаичного изображения/определяется как множество изображений, имеющих то же разбиение кадра F, и представляет собой линейное подпространство Ш с Ь2(&):
F = \/(х,у) = X/XFi(x,у),f 6 Rn
i = 1
Рис. 1. Геометрическая иллюстрация морфологического проецирования
Для любого изображения g(x, у) е Ь2(0.) может быть определена проекция на форму Р:
ёв (х, у) = у) = ^ ёвХ п(х, у),
I = 1
Ы2'
I = 1, п.
Здесь РР — оператор проекции или проектор на Р. Следует отметить, что с точки зрения морфологии Пытьева описания формы изображения как разбиения F, линейного подпространства Р и проектора Рр — эквивалентны и взаимозаменяемы.
Для дальнейших построений важно также, что пытьевские формы образуют алгебраическую структуру типа "решетка", в которой для любых двух форм Ри О можно указать форму более сложную Рл О и менее сложную Р V О. Более сложные формы получаются из менее сложных разбиением, а менее сложные из более сложных — слиянием областей.
Морфологическое сравнение изображений /(х, у) и g(x, у) в рамках морфологии Пытьева осуществляется при помощи морфологических квазирасстояний
dMg, Р) = № - Рр£||,
¿м( /, О = ||/- Ро /1| и нормированных морфологических коэффициентов корреляции Пытьева:
Км (,, В) = Ы,
Км (Г, О) =
Здесь в первом случае изображение g сравнивается с формой (множеством изображений) Р, а во втором случае, наоборот, изображение/сравнивается с формой О. Легко убедиться, что в общем случае КМ&, Р) Ф Км(/, О).
Часто на практике используется не сам коэффициент Км, а его квадрат КМ, который имеет смысл статистического коэффициента детерминации, описывающего относительную долю дисперсии зависимой переменной g(x, у), объясняемую моделью линейной регрессии Р (1.1) по объясняющим переменным хР(х, у).
На рис. 1 показана геометрическая иллюстрация идей морфологического подхода (трехмерные векторы соответствуют изображениям, а плоскости - формам). Схема морфологического проецирования включает образы (изображения)/и g, формы Ри О и проекции/О и gр. При этом
п
К1 •8) = МИ =
Км (8, Р) = Ы = 008(8 л ^^),
Км (I, О =
1М
= 008(1 Л/о ),
где (/^) — угол между векторами / и g в рассматриваемом линейном пространстве.
Из рис. 1, в частности, сразу становится ясно, что морфологический коэффициент корреляции изображений никогда не может быть меньше их линейного нормированного коэффициента корреляции. Этот же рисунок позволяет ввести и основную идею сравнения мозаичных форм, которая будет далее исследоваться. Раз мозаичные формы Ш и О представляют собой линейные подпространства (гиперплоскости) в пространстве изображений, то между ними также имеется соответствующий "стереометрический угол" ШлО, который можно измерить и который соответственно должен характеризовать их сходство/различие. Идея достаточно очевидна и наглядна, однако при реализации в многомерных пространствах для достаточно сложных форм оценка таких "углов" может осуществляться разными способами, известными в математике.
Рассмотрим последовательно несколько таких подходов.
2. Морфологическое сравнение форм на основе поиска критических точек морфологического коэффициента корреляции. Известно, что морфологический коэффициент корреляции является критической точкой (экстремумом) нормированного линейного коэффициента корреляции. Именно это позволяет избавиться от учета особенностей яркости одного из изображений. Действительно, пусть имеется два кусочно-постоянных изображения типа (1.1) с различной формой, т.е. различной топологией разбиения кадра:
1(х, у) = X IX ш (х, у),
I = 1
ё(х, У) = X 8}Х о] (х, у),
1 = 1
тогда
К (1, 8)
XIXя(х,у), X 8]ХО](х,У) XX 1'8](хп(х,У),ХоДх,у))
1 = 1 У_ I = 11 = 1
п Л1/2 I т Л1/2
X1V/ X 82^ 1
V' =1 У V] =1 У
Л1/2 г
п ) I т
X1V / X
V=1 у
1/2
8
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.