Метрическая морфология (стр. 3 )

 

Является ли функция ОГО метрикой?

Свойства метрики:

1)      dH(F,G) ³ 0 – неотрицательная определенность;

2)      dH(F,G) = 0 Û F=G – равенство нулю лишь для совпадающих форм;

3)      dH(F,G) = dH(G,F) – симметричность;

4)      dH(F,G) £ dH(F,W) + dH(W,G) – неравенство треугольника.

Справедливость свойств 1)-3) следует непосредственно из формулы (4) и того факта, что dH(Gj,Fi) является расстоянием, а KW(Fi,Gj) = Sij / S – неотрицательные весовые коэффициенты.

Нетривиальной задачей является лишь доказательство неравенства треугольника.

EMD-метрики

Y. Rubner, C. Tomasi, and L. J. Guibas. “The Earth Mover’s Distance as a Metric for Image Retrieval”, International Journal of Computer Vision, 40(2):99-121, 2000.

EMD-метрики используются для сравнения «гистограммоподобных» объектов-описаний, представленных конечным множеством (массивом) пар <Fi,hi>, где Fi – i-й «объект» описания, а hi – его «вес» (значимость в описании). При этом считается, что объекты принадлежат некоторому множеству O, а веса – неотрицательные действительные числа. Если при этом известная некоторая базовая (Earth) метрика dE, позволяющая попарно сравнивать объекты из O, то на основе этой «попарной» метрики может быть определена EMD-метрика для сравнения множества взвешенных пар таких объектов:

dEMD(F,G) = åj=1,..,m åi=1,..,n hij dE(Fi, Gj),

где:

åj=1,..,m hj = 1, åi=1,..,n hi = 1, åj=1,..,m åi=1,..,n hij = 1,

"i,j: hij ³0, Si = åj=1,..,m hij, hj = åi=1,..,n hij.

Функция ОГО как EMD-метрика

Легко убедиться, что выбрав в качестве «объектов» при описании форм-разбиений F и G элементарные области Fi и Gj, в качестве их «весов»

hi = KW(Fi,Fi) = Si / S,

hi = KW(Gj,Gj) = Sj / S,

в качестве «парных весов»

hij = KW(Fi,Gj) = Sij / S,

а в качестве базовой функции парного расстояния выбирается расстояние Хэмминга между областями разбиения Fi и Gj как плоскими бинарными фигурами, равное суммарной площади областей, где Fi и Gj не совпадают

dE(Fi, Gj) = dH(Gj,Fi) = Si + Sj – 2Sij,

то EMD-метрика (10) в частном случае превращается в ОГО-метрику (4):

dH(F,G) = åj=1,..,m åi=1,..,n KW(Fi,Gj) dH(Gj,Fi).

Таким образом, наиболее простым и кратким доказательством того, что функция ОГО (4) является метрикой, является доказательство через сведение к EMD-метрике.

 

Функция ОГО как трансформационная метрика

Лемма 1. dH(F,G) = dH(F,FÙG) + dH(FÙG,G).

Лемма 2. Если W есть разбиение F (FÙW =W) и G есть разбиение W (GÙW =G), то

dH(F,G) = dH(F,W) + dH(W,G).

Следствие 1. Если G есть разбиение F, то существует такая цепочка из k³0 элементарных разбиений, каждое из которых осуществляет разбиение только одной области формы:

W0=F®W1®…®Wk =G,

для которой справедливо следующее равенство:

dH(F,G) = åt=1,..,k dH(Wt-1,Wt).

Следствие 2. Если F есть разбиение G, то существует такая цепочка из l³0 элементарных слияний, каждое из которых осуществляет слияние только двух областей формы в одну:

W0=F®W1®…®Wl =G,

для которой справедливо следующее равенство:

dH(F,G) = åt=1,..,l dH(Wt-1,Wt).

Функция ОГО как трансформационная метрика

Следствие 3. Для любых форм F и G всегда существует такая проходящая через FÙG цепочка преобразований w, состоящая из k элементарных разбиений и l элементарных слияний, причем сначала следуют все разбиения, а затем все слияния:

W0=F®W1®…®Wk-1®Wk=FÙG®Wk+1®…®Wk+l-1®Wk+l =G,

для которой справедливо следующее равенство:

dH(F,G) = åt=1,..,k+l dH(Wt-1,Wt).

 

Вывод: dH(F,G) – трансформационное расстояние (расстояние редактирования) с элементарными операциями слияния и разбиения областей. Однако в отличие от рассмотренных ранее структурных расстояний редактирования, стоимость этих операций не является постоянной, а определяется на каждом шаге расстоянием dH(Wt-1,Wt) между исходной и получившейся после данного элементарного преобразования формами.

 

Функция ОГО как трансформационная метрика. Характеристическая квадратичная форма

Доказательство неравенства треугольника без сведения к EMD-метрике.

Лемма 3. dH(F,G) £ dH(F,FÚG) + dH(FÚG,G).

Примечание. Как известно, евклидово расстояние связано со скалярным произведением, которое, в свою очередь, определяется через неотрицательно определенную симметрическую квадратичную форму (метрический тензор).

ОГО dH(F,G) также может быть представлена в виде квадратичной формы:

dH(F,G) = (1/S) åi=1,..,n åj=1,..,m Sij (Si + Sj – 2Sij) =

= (1/S) åi=1,..,n Si2 + (1/S) åj=1,..,m Sj2 – (2/S) åi=1,..,n åj=1,..,m Sij2.

Чтобы избавиться от знаменателя помножим на S:

åi=1,..,n Si2 + åj=1,..,m Sj2 – 2 åi=1,..,n åj=1,..,m Sij2

и подставим следующие выражения:

Si = åj=1,..,m Sij, Sj = åi=1,..,n Sij.

Получим характеристическую квадратичную форму QH относительно {Sij}:

QH = åi=1,..,n (åj=1,..,m Sij)2 + åj=1,..,m (åi=1,..,n Sij)2 – 2 åi=1,..,n åj=1,..,m Sij2.

В данной форме из общего числа парных произведений элементов из {Sij} ненулевые единичные веса имеют:

n´m2 + т´n2 – 2 n´m = (n´m) (m + n)

парных произведений. Это число больше нуля при любых n и m больше 0. Отсюда следует, что форма QH является положительно определенной. Кроме того, легко убедиться, что она является симметрической.·

 

Функция ОГО как трансформационная метрика. Неравенство треугольника

Доказательство неравенства треугольника без сведения к EMD-метрике.

Утверждение 1 (неравенство треугольника для ОГО): dH(F,G) £ dH(F,W) + dH(W,G).

Доказательство. Пусть существует такая форма W, для которой

dH(F,G) > dH(F,W) + dH(W,G)…

Таким образом, мы получили противоречие с исходным предположением, ч.т.д.¨

 

Метрические меры сходства форм-разбиений

Мера сходства, основанная на неравенстве треугольника.

Учитвая особую роль «пустой формы» O, из которой все остальные формы могут быть получены путем последовательных разбиений, запишем:

dH(F,G) £ dH(O,F) + dH(O,G),

что позволяет определить метрический коэффициент сходства форм-разбиений (МКС)

KH(F,G) = ( dH(O,F) + dH(O,G) – dH(F,G) ) / ( dH(O,F) + dH(O,G) ) (5)

со свойствами

1)      KH(F,G)Î[0,1];

2)      KH(F,F)=1;

3)      KH(F,G)=KH(G,F);

4)      KH(F,O)=0,

кроме того, KH(O,O) не определен.

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

Метрические меры сходства форм-разбиений

Мера сходства, основанная на известном верхнем пределе.

dH(F,G) £ S,

что позволяет определить коэффициент метрического сходства форм-разбиений (КМС)