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

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

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

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

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

Мозаичные формы с упорядоченной яркостью

В рамках простейшей морфологии Пытьева [1] изображения традиционно рассматриваются как кусочно-постоянные функции вида f (x’ У) = X fF^ F-( x’ У),                       (1)

i =1,-, n где n - число областей разбиения F кадра Q площади S на связные непересекающиеся области постоянной яркости, F ={Fi,...,Fn}; f = (fF ь-..,fFn)T - вектор значений яркости; xF (x,y) e {0,1} - характеристическая функция области ^.Такие изображения называются мозаичными.

Класс изображений такой формы F имеет вид

F = ] f ( x , У ) = X f F Z F ( x , У ): f F ^{G R} ’ - = 1’"’ n p(²) [                   i = 1, - , n

Морфологический проектор Pf на класс F определяется условием gF = PFg = argmin(gF e F)||g(x, y) - gF(x, y)||2 (3) и вычисляется путем усреднения яркостей изображения g (x, y) по областям мозаичного разбиения F:

gF(x’у) = PFg(x’у) = X gF-ZFi(x’У)’ i=1,-, n gFi=(Z Fi ’ g )/||% Fi^ ’ i = I’-’ n ■                        (4)

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

^{f (} x ’ У ) = X ^f F- Z Fi⁽ x ’ У )’                          ⁽⁵⁾

i =1,-, n fFi < fR+1,i = 1,..,n-1.

Класс изображений такой формы имеет вид

F + ) = {f ( x , y ) = X / - Z f i ( x , У ): f F < f F + 1 , i =U , n - 1}. (6) i = 1, - , n

Морфологический проектор P_F (₊) на класс F (₊)

определяется условием gF (+) = PF (+)g =

= argmin ( g F ( + ) ^e F ( + ) )|| g ⁽ x ’ y ) ^- g F ( + ) ⁽ x ’ y ⁾||²

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

- функционально-атрибутное представление (2D-карта областей стекового представления р ( x , у ) + 2D-карта ранга яркости r_F ( x , y ) + 2D-карта распределения яркости f ( x , y )):

A f = a f ^{( x} ’ y ) = (p F ^{( x} ’ y ), ^{f ( x} ’ y )) =

= i pF1 (x, y), -, pFn (x, y), rF (x, y), f (x, y)} ’ pFi(x,y) = X ZFk(x’У)’i = 1,-,n ’ k=i,-, n rF(x’ у) = X -zF(x’ у);

i = 1, - , n

- функционально-реляционное представление (4D- карта отношения «пикселы меньше или равны по яркости» + 4D- карта отношения «яркость пикселов» ):

R _f = р _f ( x , y , и , v ) = e F_F ( x , y , и , v ), q_F ( x , y , u , v )^ =

= XX ^Fik ’ qFk ^Z Fi(x ’ У )Z Fk (u ’ v)’ i=1,-,n k=1,..,n

где e f ( x , y , и , v )= {1, если f( x , y ) <  f( и , v );

0 - в противном случае}, qf (x, y, u, v) = eF (x, y, u, v) (f (x, y) +f (u, v)) /2, bFik, qFik - значения этих отношений для пискселов пары облатей F и Fk;

- структурно-ресурсное атрибутное представление ( список L , содержащий n областей F с ресурсами S_Fi и признаками a _Fi = ( e _Fi , r_Fi , f_Fi ) - стековыми векторами, рангами и значениями яркости i -й области разбиения):

Lf = {{ F i =Z Fi ( x , У ), S f- , e Fi , r F -, / f )} , _{= 1 -} n,          (10)

eFi = X eFik 1 n (k)’ - = 1’ - ’ n ’ k=1,-,i rFi = i, i = 1,-, n;

- структурно-ресурсное реляционное представление ( граф G с вершинами-областями F_i , имеющими атрибуты ресурса S_Fi , и отношениями- стрелками r _Fik , имеющими атрибуты ресурса S_FiS_Fk ):

G f =({( F - =Z Fi ( x , y ), S f- )} , _ , _ n, {^ ^r Fik == ( ^e Fik ’ ^r Fik ’ ^q Fik )’ S Fi S Fk ^} . = 1     k = 1    ^

e_Fik = {1: i <  k ;0: i >  k },

rFik = {k - i: i < k;0: i > k}, qFik - {(F + f№)/2: i < k;0: i > k).

Оператор реконструкции изображения по модели (8- 11)

f -8 м ( M f )

для каждого из представлений имеет вид соответственно:

f(x, y) - 8A (Af) - (1 n+2 (n + 2), af (x, y)),(12)

f(x,y) -8r (Rf)- qF (x, y, x, y),(13)

f (x, y)-8 l (Lf)-(ff , % f (x, y)), f (x, y)- 8G(Gf)- (qF,%f (x,y)),qF - qqFij=v.n ■(15)

Атрибутные представления асимметричных реляционных моделей

Рассмотрим, как для таких асимметричных реляционных моделей могут быть построены эквивалентные атрибутные представления. В (8)-(11) мы использовали в качестве базывых вариантов две такие модели: стековые и ранговые представления.

Стековые модели мы ранее подробно рассматривали в [4]-[6]. Опишем их теперь в рамках единого реляционно-атрибутного формализма.

Стековые функции n _Fi ( x, y ) являются в четких ориентированных моделях аналогом характеристических функций % Fi ( x, y ) в четких неориентированных моделях. Четкими будем называть ориентированные или неориентированные модели, в которых функции отношений принимают значения {0,1}. Нечеткими -если функции отношений принимают значения из [0,1]. Неотрицательными, если диапазон значений - R ⁺. Произвольными - если диапазон значений функций отношения не ограничен.

Как мы отмечали ранее в [7], в модели (1)-(4) характеристические функции % Fi ( x, y ) могут быть рассмотрены как индикаторы класса эквивалентности пикселов по отношению «равно по яркости» b_F ( x, y, u, v ). Такие индикаторы можно определить для любой точки с координатами ( u, v ):

% F ( u , v ) ( x , y ) - b F ( u , v , x , y ).

При этом, очевидно,

V(u,v)g F :%F(u,v)(x,y)-%Fi(x,y), откуда следует, что на мозаичном изображении с разбиением F ={F1,..., Fn} существует ровно n различных классов по отношению «равно по яркости» bF(x, y, u, v) с индикаторами {%Fi (x, y)}i = 1,.., n.

Аналогично для ориентированной модели (8) - (11) стековые функции n _Fi ( x, y ) могут быть рассмотрены как индикаторы класса по отношению «меньше или равно по яркости» e F ( x, y, u, v ). Такие индикаторы можно определить для любой точки с координатами ( u, v ):

n F ( u , v ) ( x , y ) - C f ( u , v , x , y ).

При этом

V(u, v) g Fl: nF(u,v)(x, y) -nя(x, y), откуда следует, что на мозаичном изображении с разбиением F ={F1,...,Fn} существует ровно n различных классов по отношению «меньше или равно по яркости» Cf (x, y, u, v) с индикаторами {nfi (x, y)} i = 1,.., n. Отсюда для мозаичных моделей реляционная форма может быть восстановлена по стековому представлению обратным преобразованием

Cf ( x, y, u, v) - Z % И( x, y )П Fi ( u, v) - i-1,., n

- z z %Fi (x, y )%Fk (u, v)• i-1,^,n k-i,...,n

Если области упорядочены по яркости в соответствии с (5), то из (16) автоматически следует, что, как мы указали в (8),

П Fi (x , y ) - Z % Fk ( x , y ), i - 1, . , n .

k - i , . , n

Это и определяет стековое свойство таких функций:

П Fi ( x , y ) > n Fi + 1 ( x , y ), i - 1,.., n - 1.

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

C fg ( x , y , u , v ) - Z % Gi ( x , y ) n FGi ( u , v ).

i - 1, . n

Ранговую функцию r_F ( x, y ) для четкого отношения e_F ( x, y, u, v ) теперь можно ввести как интегральную характеристику набора стековых функций n F ( x, y ) в точке ( x, y ):

r F ( x , y ) - Z n Fi ( x , y ). (18) i - 1, . n

Заметим, что для нечетких или произвольных моделей C f ( u, v, x, y ) g R стековое представление теряет смысл (становится слишком много классов), зато интегральную ( ресурсную ) характеристику относительной упорядоченности E F ( x, y ) по-прежнему можно ввести:

E_F ( x , y ) - jj ^ c_f ( x , y , u , v ) dudv . (19)

Еще одним достинством ресурсной характеристики по отношению EF (x, y) по сравнению с ранговой характеристикой rF (x, y) является то, что диапазон значений ранговой характеристики сильно зависит от количества уровней яркости n, в то время как ресурсная характеристика от n не зависит. В то же время ресурсная характеристика зависит от размера кадра S и, следовательно, в отличие от ранговой, неинвариантна к изменениям масштаба. Однако мы всегда можем перейти к соответствующим нормированным характеристикам rF * (x, y) = rF (x, y) / n,

Ef *( x, y) = Ef (x, y)/ S, в результате обе эти проблемы в значительной степени нивелируются.

Для четких дискретных моделей E F ( x,y ) превращается в ресурсную характеристику классов Д _Fi ( x, y ):

E f, = E ^S Fk , i = !,-, n

Легко увидеть и обратную аналогию: ресурсные характеристики четких пытьевских форм S_Fi имеют в качестве источника интегральную характеристику яркостной эквивалентности B f ( x, y ):

B_F ( x , y ) = |j_n b_F ( x , y , u , v ) du dv .

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

e_F ( x , y , u , v ) = { 1, если r_F ( x , y ) <  r_F ( u , v )

0 - в противном случае}, eF (x, y,u, v) = {1, если EF (x, y) > EF (u, v);

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

При этом подобно тому, как в пытьевской модели (1)-(4) мы имеем стандартную форму мозаичной реконструкции изображения по набору индикаторов классов и яркостей классов ( f _F , X _F ):

f(x, y)= E fFiXf,(x, y), i =1,..., n в модели (8)-(11) мы имеем такую же стандартную форму стековой (уровневой) реконструкции изображения по набору индикаторов классов и яркостей классов (fF, ДF):

f ( x , y ) = max , = 1 1, _ , n f F^ Fi ( x , y ). (24)

Можно также использовать аддитивную форму стековой (уровневой ) реконструкции изображения по набору индикаторов классов и межуровневых разностей яркости ( A f _F , Д _F ):

^{f ( x} , y ) = E ^{A f} F-^ Fi⁽ x , y ) ⁽²⁵⁾ i =1,..., n

A f F 1 = f F 1 , A f F, = f_R - f F - 1 >  0, i = 2, _ , n .

Наконец, следует затронуть и проблему инвариантности ориентированной модели к преобразованиям изображений. В оригинальной морфологии Пы-тьева большой акцент делается на идее инвариантности, и она служит способом классификации моделей. Мозаичная модель (1)-(4) отличается тем, что она инвариантна к произвольным «перекрашиваниям» областей, а модель (8) - (11) инвариантна лишь к монотонным изменениям яркости. Однако нам представляется, что с точки зрения реляционных представлений модели это не первичная, а вторичная классификация. Она означает дословно следующее: «Модели инварианты к таким группам преобразований изображений, которые сохраняют те отношения, на которых построены модели». Иными словами, тип отношений в модели сразу определяет тип преобразований изображения, при которых эти отношения сохраняются. Значит, классификация морфологических моделей по типам отношений (которой мы придерживаемся в данной работе) определяет также их классификацию по классам инвариантности к преобразованиям.

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

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

Сравнение изображений с формами на основе направленных реляционных моделей

Простейший вопрос о сравнении изображения с моделью звучит так: «Соответствует ли изображение g модели F ?» Или наоборот: «Описывает ли модель F изображение g ?». Если модель представлена в реляционной форме, то этот вопрос принимает вид: «Все ли отношения, содержащиеся в модели F , справедливы для изображения g ?». Этот ответ предполагает бинарный ответ {1,0} = {да, нет}. Поэтому функцию

Z ( g , F ) = {1, если g g F ;

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

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

Для модели (8)-(11) проверочный предикат можно построить, например, следующим образом. Введем бинарное отношение:

h e ( p , q ) - {1, если p <  q ;0 - в противном случае}.

Тогда проверочный предикат по отношению e_F ( x , y , u , v ) можно записать как

Z e ⁽ g . ^F ) = П {( x , У ),( u , v ): c f ( x , y,u , v ) = 1} h e ⁽ g ⁽ x , У ), g ⁽ u , v )X ⁽²⁷⁾

Ниже мы рассмотрим, как Z e ( g, F) можно записать и в различных других формах, в частности, в стандартной для морфологии форме с использованием морфологических операторов. Заметим сразу, что такая форма проверки не специфична для направленных моделей. В случае модели (1)-(4) проверочный предикат по отношению b_F ( x, y, u, v ) мы также можем записать как

^Z b ⁽ g . ^F ) = П {( X , У ),( u , v ): b F ( x , y,u , v ) = 1} h b ⁽ g ^{( x} , У ), g ⁽ u , ^v )), ⁽²⁸⁾ h_b ( p , q ) - {1, если p - q ;

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

Легко заметить, что проверочные предикаты типа (27)-(28) слишком жесткие и мало применимы к реальным зашумленным изображениям. Достаточно, чтобы h_b ( g ( x, y ) , g ( u, v )) = 0 для единственной пары пикселов, для которых e_F ( x, y, u, v ) = 1, и Z ( g, F) принимает нулевое значение. С практической точки зрения хотелось бы смягчить проверочный предикат Z e ( g, F) g {0,1}, перейдя к мере сходства K e ( g, F) g [0,1]. При этом также можно рассмотреть три случая сравнения по отношению с :

• •    сравнение изображений K e ( g,f);

• •    сравнение изображения с моделью K e ( g,F);

• •    сравнение моделей / форм K e ( G,F ).

Введем реляционное описание изображения g по отношению e :

e g ^{( x} , y , ^u , v ) - ⁽ g ^{( u} , v ) - g ^{( x} , y )) h e ⁽ g ^{( x} , y X g ⁽ и , v )X ⁽²⁹⁾ которое, естественно, отличается от такого же описания формы

C g ( x , y , u , v ) - he ( g ( x , y ), g ( u , v )).

Тогда все три интересующие нас вида сравнения можно было бы записать в одинаковой форме, например, на основе нормированного коэффициента корреляции реляционных описаний (4D-функций) ( НККРО ):

KNe (g, f) = ( eg , ef ) / (| legllllef ||) ,

Knc (g, F)-(Cg, Cf ) / (I |cg||||cF| I),(31)

Knc ( G, F)-( Cg , CF ) / (||cg||||cf||) .(32)

Основная идея нормированной корреляции с учетом отношения e здесь заключается в том, что скалярное произведение ( c_g , c f ), по сути, возвращает сумму (интеграл) произведений вида

( e g , e f ) ^- JJJ J_n ⁽ g ^{( u} , ^v ) ^- g ^{( x} , у ⁾⁾⁽ f ^{( u} , ^v ) ^-

• - f ( x , y )) h_e ( g ( x , y ), g ( u , v )) h_e ( f ( x , y ), f ( u , v )) dx dy du dv , которая максимальна в случае, если изображения g и f в каждой паре пикселов имеют одинаковый знак разности, а в случае положительного знака - еще и одинаковую амплитуду.

Проанализируем выражения (30)-(32) формально. Прежде всего, заметим, что из-за неотрицательности (29) нормированный коэффициент корреляции в данном случае будет являться мерой сходства:

K nc ( g , f ) G [0,1],

K nc ( g , F ) G [0,1],

K nc ( G , F ) G [0,1].

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

K nc ( f , f ) - 1.

То же самое справедливо и для сравнения идентичных форм:

K nc ( F , F ) - 1.

Также из симметрии выражений (30) - (32) следует симметрия значений:

K nc ( g , f ) - K nc ( f , g ), K nc ( G , F ) - K nc ( F , G ).

Однако при сравнении изображения с формой это не так:

K nc ( f G F , F ) <  1, K nc ( g , F ) ^ K nc ( f , G ).

Чтобы решить первую проблему, меру сходства изображений с формами нужно определить несколько иначе - как морфологический коэффициент корреляции (МКК) реляционных описаний (МККРО):

K mc ²( g , F ) - ( C g ²( x , y , u , v ), C f ( x , y , u , v ) ) /| e g 11². (33)

Теперь в числителе дроби находится выражение

( e g ^{2 ( x} , y , ^u , ^v X e F ^{( x} , У , ^u , ^v ) ) ^- JJJ J_a ⁽ g ^{( u} , ^v ) ^-

• -    g ( x , y )) ² h e ( g ( x , y ), g ( u , v )) h e ( f ( x , y ), f ( u , v )) dx dy du dv ,

а в знаменателе

У e g ^{( x} , У , ^u , ^v ) ||^{2 -} JJJJ_n ⁽ g ^{( u} , ^v ) ^-

• -    g ( x , y )) ² h e ( g ( x , y ), g ( u , v )) dx dy du dv .

Если h e ( g ( x, y ) , g ( u, v )) = h e ( f ( x, y ) ,f ( u, v )), то числитель и знаменатель совпадают, т.е.

К ме ( f е F , F ) - 1.

Если h e ( g ( x, y ) , g ( u, v )) * h e ( f ( x, y ) ,f ( u, v )), то числитель уменьшается на сумму квадратов значений ( g ( u, v )- g ( x, y ))² для всех пар

{ ( x , y ), ( u , v ): e_G ( x , y , u , v ) * e_F ( x , y , u , v ) } .

При этом морфологический коэффициент корреляции по-прежнему асимметричен (ведь сравнение здесь разносортное - изображение сравнивается с формой):

К м _е ( f , G ) * К м _е ( g , F ).

Аналогичный асимметричный МКК можно ввести и для форм:

К м _е ² ( G , F ) - ( e G ²( x , y , u , v ), e_F ( x , y , u , v ) ) /11 e G 1 1 ², (34) причем

К м _е ( F , F ) - 1, К м _е ( G , F ) * К м _е ( F , G ).

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

Очевидно, этот прием можно обобщить для реляционных моделей общего вида (как ориентированных, так и не ориентированных).

Пусть для любого изображения f ( x, y ) определена некоторая процедура описания по отношению 9 .

е ₆ : f ( x , y ) >9 f ( x , y , u , v ) е R ⁺.

Пусть также определено некоторое правило нятия решения 0 , задающее отображение:

• 0 : 9 f ( x , y , u , v ) > 9 _F ( x , y , u , v ) е {0,1}.

Простейшим правилом такого рода может пороговое правило 0 ( 9 1 ):

• 9 _F ( x , y , u , v ) - { 1, если 9 f ( x , y , u , v ) > 9 1 0 - в противном случае }.

  при-

  быть

  
  

Функции 9 f ( x, y, u, v ) и 9 f ( x, y, u, v ) будем называть соответствено реляционным описанием изображения f ( x, y ) и реляционным описанием формы F по отношению 9 . При этом возникает класс формы f по отношению 9 :

F _e - { g ( x , y ): 0e ₆ g ( x , y ) - 9 g ( x , y , u , v ) -- 9 f ( x , y , u , v ) - 0e _e f ( x , y )}.

Эти реляционные описания можно сравнивать при помощи следующих НККРО:

K n 9 ( g , f ) - ( 9 g , 9 f ) / (| e g || |e f | I) ,                     (38)

Kn 9 ( G , F ) - ( 9 G , 9 F ) / (|| 9 g|| ||9 f| I)                      (39)

• и МККРО:

К м 9 ² ( g , F ) - ( 9 g ² ( x , y , u , v ), 9 F ( x , y , u , v )) /119 g 11², (40)

К м 9 ² ( G , F ) - ( 9 g ² ( x , y , u , v ), 9 f ( x , y , u , v ))/1 19 g 11² ,(41)

которые, как мы показали выше, обладают следующими свойствами:

K n 9 ( g , f ) е [0,1], K n 9 ( G , F ) е [0,1], K n 9 ( f , f ) - 1,

K n 9 ( F , F ) - 1, K n 9 ( g , f ) - K n 9 ( f , g ),

K n 9 ( G , F ) - K n 9 ( F , G );

К м 9 ( g , F ) е [0,1], К м 9 ( G , F ) е [0,1], К м 9 ( f е F , F ) - 1,

К м 9 ( F , F ) - 1, К м 9 ( f , G ) * К м 9 ( g , F ),

К м 9 ( G , F ) * К м 9 ( F , G ).

Морфологические операторы на основе направленных реляционных моделей

Выше мы построили НКК и МКК для сравнения изображений и мозаичных форм по заданному отношению непосредственно на основе реляционного представления модели, без перехода к операторной форме. Однако традиционно в морфологическом анализе изображений для проверки принадлежности изображения g классу формы F (в данном случае нас интересует класс F 9 = F (₊) по отношению 9 = e ) мы должны построить проектор на класс :

g F ( + ) ^- P F ( ₊ ) g ^: g ⁽ x , y ) >  g F ( ₊ ) ⁽ x , y ) ^{е F} ( ₊ ) .        ⁽⁴²⁾

Такой проектор P_F (₊) является оператором (модификатором), приводящим изображение g ( x, y ) к модели e_F , т.е. изменяющим g (превращая его в g_F (+> ) так, чтобы e_GF = e_F . Если такой приводящий оператор (морфологический проектор) построен, тогда проверочный предикат по отношению e F ( x, y, u, v ) (27) можно эквивалентно записать как

[ 1, если g - P_F(+Ag ;       1

Z e ( g , F ) - ^ , ^S     F ^(+)S’        ^ ,             (43)

[0, в противном случае J а мера сходства по отношению eF (x, y, u, v) (МКК) принимает стандартный вид:

^К м ( + ) ( ^g , ^F ( + ) ) ^{- К} м ( + ) ( ^g , ^P F ( + ) ) ^-

-I p F ( + ) g | |/ H g н , К м ( + ) ( g , F ( + ) ) е [0,1].

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

Морфологические операторы типа Серра

Рассмотрим первый вариант построения приводящего оператора, основанный на независимом локальном исправлении элементов изображения, которые не соответствуют заданной модели. Пусть для некоторого пиксела ( x, у ) наблюдается g ( x, у )> g ( u, v ), тогда как модель требует, чтобы e_F ( x, у, u, v ) = 1, т.е. должно стать g ( x, у ) <  g ( u, v ). Минимально возможное изменение данного пиксела состоит в замене

g ( x , у ) ^ g F <+х x , у ) = ^min( g ⁽ x , у ), g ⁽ u , v )).

Поскольку такая проверка требуется для всех пикселов, связанных с данным отношением e_F ( x, у, u, v ) = 1, приводящий оператор E F (₊) можно сформировать как:

g F ( E ) - E f ( + ) g ( x , у ) - min ( u , v ): e_F ( x , у , „ ^ _{) =} i g ( u , v ). (45)

В данном случае мы обозначили морфологический оператор (45) как E , поскольку он имеет смысл и форму оператора эрозии Серра [8] с переменным бинарным структурирующим элементом e_F ( х, _у ) ( u, v ). Легко убедиться, что:

• a )    g F ( e ) ⁽ x , у ) <  g ⁽ x , у );

• b )    h ( x , у ) <  g ( x , у ) ^ h F ( e ) ( x , у ) <  g F ( e ) ( x , у ),

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

• c )    ^g F ( e ) ^{- E} F ( + ) ^g F ( E ) ,

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

g F ( e ) ( x , у ) - max i ₌i„ „ , n g ( e ) Fi p Fi ( x , у ), (46) g ( E ) Fi ^{- min} ( u , v ): п _и( u , v ) - 1 g ^{( u} , ^v ) ^ g F ( E ) ^{( x} , у ) ^- ₍ 47 ) - max _{i =} 1, ^ , n min_{( u} , v F ( u , v ) - g ( u , v ).

В форме (47) структура оператора E F (₊) уже четко опознается как структура оператора открытия Серра -в каждой точке берется максимум по минимумам внутри структурирующих элементов, в роли которых выступают в данном случае стековые функции П Fi (x, у ).

Заметим, что операция (45) в терминах полутоновой морфологии Серра является операцией открытия с плоским (flat) бинарным структурирующим элементом (СЭ):

g F ( e ) ^{- E} F ( + ) g ^{( x} , у ) ^- g ^{( x} , у ) ° ^e F ( x , у ) ^{( u} , ^v )•

Это значит, что в рамках отношения e мы можем рассмотреть также и полутоновое открытие Серра с полутоновым СЭ:

g f ( E ) ^- g ⁽ x , у ) ° e f ( x , у ) ^{( u} , v ) ^-                          (48)

• -    min ( u , v ): e f ( _х ,у , u , v »0 g ( u , v ) - e f ( x , у , u , v ),

e f ( x , у , u , v ) - ( f ( u , v ) - f ( x , у )) e F ( x , у , u , v ).

Здесь, хотя функция e f ( x, у, u, v ) описывает конкретное изображение f ( x, у ), речь, тем не менее, идет о проекторе E f (₊) на класс изображений:

F f ( + ) = { ^g ( x , у ): e g ( x , у , u , v ) >  e f ( x , у , u , v ) } ,      (49)

который, впрочем, отличается от рассматриваемого нами класса (6)

F ( + ) - { g ( x , у ): e_G ( x , у , u , v ) >  e F ( x , у , u , v ) } .       (50)

Класс F f(+) содержит изображения, для которых соответствующие парные перепады яркости между пикселами не только имеют тот же знак, но и по величине не меньше, чем в эталонном образе f ( x, у ), который определяет полутоновой структурирующий элемент e f ( х, _у ) ( u, v ). Такую реляционную модель можно назвать аддитивной нечеткой моделью формы, в отличие от мультипликативных нечетких моделей, которые мы рассматривали ранее.

Морфологические операторы типа Пытьева

Теперь необходимо заметить, что морфологические фильтры типа Серра имеют много достоинств, но они на самом деле не решают задачу (7)

^g F ( + ) ^- P F ( + ) ^{g -}

• -    arg min ( g f ( + ) ^{G F} ( + ) ) h g ^{( x} , у ) ^- g F ( + ) ^{( x} , у ) 1 1² ,

точнее говоря, они ее решают с дополнительным ограничением на монотонность: g_F ( _E ) ( x, у ) < g ( x, у ). Между тем, задача (7) имеет точное решение. Существует известный эффективный алгоритм решения этой задачи ( МНК-аппроксимации , т.е. аппроксимации монотонной функции методом наименьших квадратов), основанный на построении нижней выпуклой оболочки наблюдаемых данных. Опишем такой алгоритм МНК-проецирования (7) в терминах стекового представления изображения.

Обозначим ^Fn+1(x, у) = 0 , mean(,. k >„ (g, Fw) - mean( g (x, у), pf (x, у) - П Fk+1 (x, у)) -

• ^-    ^ ^mean ( g ⁽ x , у X% Fj ⁽ x , у ) ) S Fj / ^ S Fj ^- j - i ' ,^., k                                                               j = i ' , „ , k

• ^-    ^ g Fj S Fj I ^ S Fj . j - i ' , -• , k                j - i' ,-•, k

Будем последовательно (итеративно) формировать стековое представление формы проекции g F (+) как набор стековых функций { p GFj ( x, у )} j= 1 ,..,m . и соответствующих значений яркости {g GFj } j= 1 ,..,m .

Алгоритм 1: Approx(F (₊) ,mean) .

( МНК-проецирование на форму с упорядоченными яркостями ).

На первом шаге положим m = 1, r = 0 и определим

B gf i ( x , У ) = B f i ( x , У ).

На каждом следующем шаге вычисляем:

q = argmin k = r ₊ i,.., „ mean ( r ₊ i, k ) ( g , F _w) ;

g GFm = mean ( r + i, q , ( g , F _{( + )} ) .

Если q = n , завершаем процесс итераций, в противном случае

• r = q ;

• m = m + 1;

B GFm ( x , У ) = B Fr + 1 ( x , У );

• и переходим к следующей итерации.

На завершающем шаге алгоритма восстанавливаем изображение МНК- проекции:

g F ( + ) ( x , y ) = maX j ₌ i^. m g G р GFj (x , y ).

Конец Алгоритма 1 .

Как видно, в результате такого алгоритма мы сразу получаем не только проекцию изображения g_F (₊) , но и форму проекции G f (+) ={ B gfj ( x, У )} j= i ,..,m . Форма проекции, естественно, всегда проще формы класса, на которую мы проецируем: стековые функции выбираются из того же набора, но их может стать существенно меньше (все функции сохранятся, только если g е F уф

Формирование оценки яркости gGFm = mean( r+i, g, (g, F(+))

при помощи функции взятия среднего значения (mean) связано, естественно, как и в пытьевском проецировании, с гипотезой о нормальном распределении ошибки пиксельного наблюдения и, соответственно, с критерием МНК-проецирования (7). В связи с этим такой МНК-проектор естественно обозначить как P ( _{F +}, mean ) . При других предположениях о характере наблюдения и соответствующих критериях проецирования тем же алгоритмом оценивания монотонно неубывающей стековой модели Approx ( F (+) ,*) с другими базовыми операциями могут быть реализованы аналогичные проекторы на основе других статистических операторов: P ( f +, med ) , P ( f +, min ), P ( _F +, mode ) и другие. При этом легко заметить, что P ( F +, min ) = E f (+) .

Интересно также отметить, что по критерию «исправления минимума элементов» P(F+,mode) превосходит P(F+,min). В самом деле, введем функцию стоимости редактирования в точке как dE01 (a, b) = {0, если a = b

^g ( F + , mode )    ^P ( F + , mode ) ^g

= argmin ( _{f e} f ( + )) d E ( g ( x , У ), f ( x , У ).

Это показывает, что «жадная» стратегия локального поэлементного редактирования изображения далеко не всегда приводит к оптимальным результатам даже с той точки зрения, на основе которой строились такие «жадные» алгоритмы.

Морфологические операторы в атрибутном и реляционном домене

Итак, теперь у нас есть два варианта МКК для моделей с направленными отношениями:

• - МКК по отношению e_F ( x, y, u, v ) на основе оператора проецирования (45) привычного вида:

K M ( + ) ^{( g} , ^F ( + ) ⁾ = K M ( + ) ^{( g} , P F ( + ) ⁾ = I P F ( + ) ^g | | / | | ^g | |,

- МККРО (33) непосредственно по реляционной модели e F (x, y, u, v):

K Me ² ( g , F ) - ( e g ² ( x , y , u , v ), e F ( x , y , u , v ) ) /1 e g 11².

Можно ли установить какую-то связь между ними или хотя бы описать их с единых позиций?

Рассмотрим сначала МКК (45). Как мы уже отмечали выше, в результате алгоритма Approx( F (₊) ,mean) мы сразу получаем не только проекцию изображения g F (+) , но и форму проекции G f (+) ={ Н GFj ( x, y )} j= i ,..,m . При этом легко увидеть, что

^P F ( + ) g ⁽ x , У ) ^- P GF g ⁽ x , У ) ^-

^- ^ ^mean ( g ^{( x} , y ), % GF j ^{( x} , У ) ) x GF ,^{( x} , У ), j = 1, ^ , m

G GF = ^{ % GFj ⁽ x , ^У ) = B GFj⁽ x , ^У ) B GFj + 1 ⁽ x , ^{y )}} j = 1, ^ , m ,

ПFm+1(x, У ) = 0, где PGf - стандартная пытьевская проекция g (x, y) на (неупорядоченную) форму GGf, которая является базовой мозаичной формой для упорядоченной мозаичной формы GF(+).

Таким образом, отображение (51) можно представить как цепочку преобразований:

P f ( + ) : g ( x , y ) ^ G f ( + ) ^ G gf ^ P GF g GF ( x , y ),    (53)

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

Иными словами, оператор фильтрации (проектор) определяется в модельном домене, после чего этот оператор применяется в исходном домене (изображений). Такая схема фильтрации «прямое преобразование в модельный домен - преобразование в модельном домене - обратное преобразоване в исходный домен» является одной из стандартных в цифровой обработке сигналов, где в качестве преобразований выступают, например, преобразование Фурье, вейвлет-преобразование и т.п., а модельные домены являются соответственно частотным, пространственно-частотным и т.д. В данном случае мы говорим о преобразовании в домен морфологических описаний и модульном представлении морфологических операторов по схеме «образ ^ описание ^ преобразование описания ^ реконструкция образа по преобразованному описанию». Такие модульные представления морфологических операторов мы рассматривали и ранее [9]-[10].

Запись проектора P F(+) в форме (52) также позволяет сразу показать, что

G GF ^С G F ^ | ^p F (+) g || < || P F g || ^                  (54)

^ Km(+) (g, F(+)) < Km (g, F), т.е. оператор PF(+) упрощает сильнее, чем PF. Этот факт, очевидно, определяется тем, что Fу) с F, причем мощности этих множеств различаются драматически:

II F + ) Н с Н F II / n !                                      (55)

где n! = P_n = A nn - число перестановок рангов областей в форме F . Естественно, проекция на одно из п! равновероятных подмногообразий должна изменять проецируемый образ всегда не слабее, а в среднем существенно сильнее, чем проекция на все многообразие.

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

GF(+) -{ЛGFj(x,y)}j=1^m , rGF(x,y) - £ ЛGFj(x,У), j=1,..., m однозначно соответствует реляционное представление модели GF(+):

C gf ( x , y , u , v ) = h e ( r GF ( X , У ), r GF ( u , v ) ) ,              (56)

причем можно формально ввести оператор проекции формы F (+) с учетом изображения g ( x , y ):

^P (g ) ^: F g ( + ) = ^P (g ) ^F ( + ) = ^gf ( + ) ^О                       (57)

О P(g) : Cf (x, y, u, V) ^ 6gf (x, y, u, v), который, очевидно, явля ется идемпотентным, поскольку

P (g GF ) : C gf ( x , y , u , v ) ^ C gf ( x , y , u , v ).

Здесь примечательно то, что выражение (57) описывает новую схему двухэтапной взаимной адаптивной фильтрации изображения g и формы F :

Шаг 1: Упростить (спроецировать) форму F c учетом изображения g .

Шаг 2: Упростить (спроецировать) изображение g c учетом формы F .

Казалось бы, раньше мы не встречались с такой взаимной коррекцией формы и изображения - форма F всегда выступала как постоянная составляющая, а изображение изменялось (проецировалось). Однако и в стандартном пытьевском проецировании форма также изменялась (упрощалась) в тех случаях, когда яркости некоторых областей выравнивались. Если в проецируемом мозаичном изображении g некоторые области целиком включают какие-либо группы областей формы F , то после проецирования эти группы областей сольются и результат проецирования g F будет на самом деле иметь не форму F , а форму F_g с F . Значит, на самом деле форма и изображение всегда взаимно упрощают друг друга. Только в обычных мозаичных формах это происходит сравнительно редко, а для форм с упорядоченной яркостью это происходит в большинстве случаев, поскольку, как мы указали выше, в каждой форме с п областями имеется п ! равновероятных упорядоченных форм, и лишь для одного варианта упорядочения проекции g F итоговую форму g F ( + ) не приходится упрощать.

Рассмотрим теперь случай (33), когда проецирование происходит только в модельном домене, без возвращения в исходный домен изображения. Легко заметить, что МККРО (33) можно также переписать в традиционной пытьевской форме как отношение нормы проекции к норме проецируемой функции, только морфологическое проецирование и оценка нормы при этом происходит не в исходном, а в модельном домене:

K Me¹ ( g , ^F ( + ) ) = | | P eF e g ⁽ x , y , u , ^{V )}||^2/| | e g | I" =

2      2                                (58)

= || e gF ⁽ x . y . u . ^V )|| /|| e g || .

e_gF ( x , y , u , v ) = P_eFe_g ( x , y , u , v ) = e g ( x , y , u , v ) e_F ( x , y , u , v ).

Как видно, проецирование здесь имеет форму по-пиксельного умножения функции-образа e_g ( x, y, u, v ) на функцию-фильтр e_F ( x, y, u, v ) e {0,1}. Такой оператор, естественно, будет идемпотентным , неувеличивающим и сохраняющим порядок :

P eF C gF ( x , y , u , v ) = C gF ( x , y , u , v ),

PeFCg (x, y, u, v) < Cg (x, y, u, v), eh (x, y, u, v) < eg (x, y, u, v) ^ ^ PeFCh (x, y, u, v) < PeFCg (x, y, u, v), т.е. PeF является морфологическим фильтром (открытием) Серра, действующим в домене реляционных описаний. По сути, поэлементное умножение на функцию-фильтр eF (x, y, u, v) е {0,1} в явном виде реализует здесь введенную Матероном и развитую Серра идею морофологического «сита» (sieving) [8], удаляющего из образа те элементы, которые не соответствуют модели.

Заметим, что, по аналогии с (48), в реляционной области мы можем также ввести не только плоское (flat) открытие Серра на основе бинарной маски «сита» e F ( x,y ) ( u, v ), но и полутоновое открытие Серра вместе с соответствующим морфологическим коэффициентом корреляции:

K Me 2 ( g , ^F f (+) ) = || P f e g ⁽ x , У , u , v ⁾||2 / |l e g 1 1" =

= | e gf ⁽ x , У , u , v f/j e g 1

egf (x, y, u, v) = Pfeg (x, y, u, v) = eg (x, y,u,v), если eg (x, y,u, v) > ef (x, y,u, v); (60) 0, в противном случае.

Другая возникающая здесь аналогия - операция свертки в частотном домене, которая, согласно теореме о свертке , имеет вид поэлементного умножения Фурье-образов:

f ( x , y ) * g ( x , y ) = JJ f ( u , v ) * g ( x - u , y - v ) du dv ^

^ F ( p ) G ( p ).

Здесь также происходит фильтрация изображения при помощи реляционной модели g ( x, y, u, v ) = g ( x - u, y - v ), и в частотном домене такая реляционная фильтрация выражается в поэлементном произведении образов исходных функций. В случае четких реляционных моделей аналогами теоремы о свертке являются утверждения:

e_W ( x , y , u , v ) = e_F ( x , y , u , v ) e_G ( x , y , u , v ) ^ W _{( + )} =

= F ( + ) ^A G ( + ) ,

bW (x, y, u, v) = bF (x, y, u, v) bG (x, y, u, v) ^ W = F a G, где W(+) (W) - общая составляющая формы для F(+) и G(+) (F и G) соответственно.

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

А e_gF ( x , y , u , v ) = e g ( x , y , u , v ) - P_eFe_g ( x , y , u , v ) = = e g ( x , y , u , v ) - e_gF ( x , y , u , v ).

Ее образом в исходном домене будет 2D- карта отличий по отношению e :

А g ( f , e ) ( x , y ) = max ( u , v ) А e gF ( x , y , u , v ),               (63)

которая содержит в каждом пикселе максимальные значения «неверных» (обратных) контрастов на изображении g с точки зрения модели F (₊) , наблюдавшиеся в парах, где участвовал данный пиксел. Естественно, такая техника морфологического выделения отличий может быть распространена на любые отношения 9 , так же, как мы это показали выше для морфологического сравнения по сходству.

Заключение

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

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

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

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

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

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