Реляционные модели формы изображений и метрики их сравнения Ю. В. Визильтер, А. Ю. Рубис, gosniias. ru Москва, ФГУП «Государственный научно-исследовательский институт авиационных систем»

Задача : сравнение изображений по форме f g Насколько похожи ли эти изображения ? Ответ на этот вопрос дает морфология Пытьева, позволяющая осуществлять сравнение изображений не по яркости, а по форме. Пытьев Ю. П., Чуличков А. И. Методы морфологического анализа изображений // М.: ФИЗМАТЛИТ, с.

Задача : сравнение изображения с формой Морфологические квази - расстояния Морфологические коэффициенты корреляции Пытьева: В общем случае K M (g,F) K M (f,G). Изображения – векторы, Формы – гиперплоскости. Это схема яркостно- геометрического сравнения изображений с формами

Задача : сравнение форм Необходимо перейти от яркостно-геометрического сравнения изображений с формами к чисто геометрическому сравнению форм TV IR Контурные методы работают плохо Нужно определить метрики или меры сходства форм

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

Трансформационные метрики. Расстояние Левенштейна Трансформационное расстояние – минимальная стоимость цепочки преобразований, переводящей A в B : ДЫМ ДЫМА ДАМА МАМА Расстояние Хемминга d H между строками одинаковой длины определяется как число позиций, в которых символы не совпадают ( равно числу операций замены символа ). Расстояние Левенштейна d L равно минимальному числу операций для преобразования одной строки в другую, когда множество элементарных операций состоит из операций вставки, удаления и замены.

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

где n и m – соответствующе количества областей разбиения F и G ; S – площадь кадра ; S i – площадь области разбиения F i ; S j – площадь области разбиения G j ; S ij – площадь пересечения F i G j ; p i = S i / S – нормированная площадь области разбиения F i ; p j = S j / S – нормированная площадь области разбиения G j ; p ij = S ij / S – нормированная площадь пересечения F i G j ; d H ( G j, F i ) = p i + p j – 2 p ij – нормированное расстояние Хэмминга между областями разбиения F i и G j. Метрика оценки геометрических отличий ( ОГО ) pipi pjpj p ij

Метрика ОГО как трансформационная метрика Утверждение. Для любых форм F и G всегда существует такая проходящая через F G цепочка преобразований w, состоящая из k элементарных разбиений и l элементарных слияний, причем сначала следуют все разбиения, а затем все слияния : F = W 0 W 1 … W k - 1 W k = F G W k + 1 … W k+l-1 W k+l =G, для которой справедливо следующее равенство : ( Сумма расстояний между последовательными элементами цепочки равна расстоянию от первого до последнего элемента ) Вывод : Метрика d H ( F, G ) имеет структуру трансформационного расстояния с элементарными операциями слияния и разбиения областей, стоимость которых определяется на каждом шаге расстоянием d H ( W t - 1, W t ) между исходной и получившейся после данного элементарного преобразования формами.

Легко убедиться, что ОГО-метрика не является евклидовой. Пример пучка геодезических траекторий, отличающихся порядком разбиений и слияний Свойства метрического пространства с ОГО - метрикой : геодезические линии не являются единственными

Свойства метрического пространства с ОГО - метрикой : геодезические многообразия являются дискретными d H ( F, G ) = d H ( F, V ( x )) + d H ( V ( x ), G ) (x-a) 2 + (b-x) 2 – (b-a) 2 = 0 x 2 – (b+a)x +ba = 0 ( x = a ) или ( x = b ). Значит, из всех форм семейства V ( x ) геодезическому многообразию D ( F, G ) принадлежат лишь сами формы F = V ( a ) и G = V ( b ). Иллюстрация дискретности геодезических многообразий в пространстве мозаичных форм на примере семейства бинарных форм

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

Предыдущие работы ( Источник 1) В морфологии Пытьева [1] предложена схема описания формы изображений на основе базисных функций, связанных с разбиением кадра на непересекающиеся области. Порождаемые таким образом модели формы можно назвать T- моделями ( Tessellation based shape models ). [1] Пытьев Ю. П., Чуличков А. И. Методы морфологического анализа изображений // М.: ФИЗМАТЛИТ, с. F1F1 F2F2 F3F3 Image f ( x,y ) Tessellation F F4F4

Предыдущие работы ( Источник 2) В работах [2], [3] был предложен альтернативный способ описания формы изображений, названных авторами знаковым представлением изображений и основанный на рассмотрении множества яркостных отношений между пикселами изображения, что эквивалентно частично упорядоченным по яркости T - моделям. [2] Каркищенко А. Н., Гончаров А. В. Исследование устойчивости знакового представления изображений // Автоматика и телемеханика. 9. С [3] Броневич А. Г., Гончаров А. В. Аксиоматический подход к измерению информативности знаковых представлений изображений // Известия РАН. Теория и системы управления. 6. C

Предыдущие работы ( Источник 3) В работе [4] было введено понятие т. н. EMD - метрик *, используемых для сравнения « гистограммоподобных » описаний, представленных конечным множеством пар, где F i – i - й « объект » описания, а h i – его « вес » ( значимость в описании ): Здесь d E – базовая ( Earth ) метрика, а веса удовлетворяют условиям : [4] Y. Rubner, C. Tomasi, and L. J. Guibas. The Earth Movers Distance as a Metric for Image Retrieval, International Journal of Computer Vision, 40(2):99-121, * Частный случай метрик Монжа - Канторовича

Предыдущие работы ( Источник 3) i hjhj j hihi h ij Задача решается методом линейного программирования Оптимизация «перевозок» весов из гистограммы в гистограмму = «Транспортная задача»

В данной работе ( анонс результатов ): 1.Для рассмотрения произвольных типов отношений между областями разбиения кадра ( не только по яркости, но и по размеру, по форме, по текстуре, по взаимному расположению и т. п.) будет определен более общий класс реляционных моделей формы изображений или T R - моделей ( Tessellation based Relational shape models ). 2.Будет описан формализм TR - моделей и показаны перспективы их практического применения в задаче сравнения изображений по форме. 3.Будет показано, что метрики сравнения TR - моделей представляют собой специальный класс EMD - метрик, который предлагается называть RMD - метриками.

Морфология Пытьева. Описание форм Множество изображений одной формы разбиения кадра F – выпуклое и замкнутое подпространство F L 2 ( ): Для любого изображения g ( x, y ) L 2 ( ) может быть определена проекция на форму F : P F – оператор проекции или проектор на F. Формы – замкнутые и выпуклые подпространства линейного пространства изображений.

Морфология Пытьева. Сложность форм Формы - разбиения частично упорядочены по сложности : Для любых форм F и G можно указать форму более сложную F G и менее сложную F G. Более сложные формы получаются из менее сложных разбиением, Менее сложные из более сложных – слиянием областей.

Альтернативное описание форм отношениями пикселов Введем предикат бинарного отношения пикселов « равно / неравно по яркости »: Определим L 1 - норму TR - формы F ( x,y,u,v ): Пусть изображения из F и G имеют вид тогда то есть TR - формы будут кусочно - постоянными 4D функциями.

Альтернативное описание форм отношениями областей Рассмотрим форму W = F G с областями W ij = F i G j. Для нее можно записать Любые операции над T- формами F и G могут быть описаны в терминах операций над такими бинарными матрицами размера ( m n ) 2. В частности где S ij, S kl – площади областей разбиения W ij,W kl.

Матрицы отношений " равно / неравно " для 1D- функций f F = SF1SF1 SF2SF2 SF3SF g G = SG1SG1 SG2SG

Описание форм с упорядоченной яркостью пикселов Для описания форм - разбиений с частично упорядоченной яркостью введем векторный бинарный предикат = 1, 2 для описания всех возможных отношений упорядоченности по яркости « пикселы больше / меньше / равны / неравны по яркости »: Значение 1,1 означает, что данная пара пикселов в данной форме F не упорядочена по яркости. Определим L 1 - норму TR - формы F ( x,y,u,v ): где | F (x,y,u,v) | = F (x,y,u,v) 1 + F (x,y,u,v) 2.

Описание форм с упорядоченной яркостью пикселов Пусть изображения из F и G имеют вид кусочно - постоянных функций, причем все значения { f i } являются различными, как и все значения { g j }. Тогда

Описание форм с упорядоченной яркостью областей Следовательно, такие TR- формы также можно записать в виде векторных бинарных матриц размера ( m n ) 2 : Выражение для L 1 - нормы :

Матрицы отношений "больше" для 1D-функций f 1F = SF1SF1 SF2SF2 SF3SF g SG1SG1 SG2SG G =

Матрицы отношений "меньше" для 1D-функций f 2F = SF1SF1 SF2SF2 SF3SF g SG1SG1 SG2SG G =

Описание форм - разбиений произвольными отношениями Обобщение 1. Пусть дано некоторое изображение f ( x, y ) и некоторый упорядоченный набор ( вектор ) r функций отношения TR(a,b): R 2 R, t = 1,…,p. R - моделью изображения f по набору отношений r между пикселами назовем векторную функцию TR - моделью изображения f формы F по набору отношений r между областями разбиения назовем векторную матрицу При сравнении TR - моделей изображений f и g формы F и G соответственно, TR - модели F ( F i, F k ) и G ( G j, G l ) эквивалентно преобразуются к виду F ( W ij,W kl ) и G ( W ij,W kl ), где W ij = F i G j. При этом L 1 - норма обобщенной TR - модели F ( x,y,u,v ) определяется выражением

L 1 - метрика в пространстве T- моделей Рассмотрим расстояние Хэмминга ( L 1 - метрику ) между формами - отношениями « равно / неравно по яркости » F ( x,y,u,v ) и G ( x,y,u,v ): Для кусочно - постоянных функций выражение (1) можно преобразовать к виду где S ij, S kl – площади областей W ij,W kl, причем

L 1 - метрика T- моделей и ОГО - метрика Введем обозначение Тогда где S i и S j – площади областей F i и G j. Таким образом, при S=1 мы получаем метрику оценки геометрических отличий ( ОГО - метрику ) для T - форм F и G : где d H ( F i,G j ) = S i + S j – 2 S ij – расстояние Хэмминга ( L 1 - метрика ) между парами областей F i и G j.

f F = SF1SF1 SF2SF2 SF3SF g G = SG1SG1 SG2SG L 1 -метрика отношений "равно / неравно" для 1D-функций | F - G | =

L 1 - метрики в пространстве TR- моделей Аналогичным образом можно ввести L 1 - метрику для сравнения « знаковых представлений »: Обобщение 2. В общем случае для сравнения TR - моделей можно ввести L 1 - метрику вида

L 1 -метрики отношений "больше" для 1D-функций f 1F = SF1SF1 SF2SF2 SF3SF g SG1SG1 SG2SG | 1F - 1G | = 1G =

L 1 -метрики отношений "меньше" для 1D-функций f 2F = SF1SF1 SF2SF2 SF3SF g SG1SG1 SG2SG | 2F - 2G | = 2G =

Метрики сравнения TR- моделей как EMD- метрики EMD - метрики используются для сравнения « гистограммо - подобных » описаний, представленных конечным множеством пар, где F i – i - й « объект » описания, а h i – его « вес » ( значимость в описании ): Здесь d E – базовая ( Earth ) метрика, а веса удовлетворяют условиям : При выборе в качестве « объектов » элементарных областей F i и G j, в качестве их « весов » h i = S i / S, h j = S j / S, h ij = S ij / S, а в качестве базовой метрики расстояния Хэмминга d H ( F i, G j ), EMD - метрика (5) превращается в ОГО - метрику (2).

Метрики сравнения TR- моделей как E B D- метрики Назовем E B D- метрикой сравнения форм - разбиений ( Earth Based Shape Distance, E B SD- метрика ) метрику следующего вида : где d E ( F i, G j ) – любая базовая ( Earth ) метрика d E, позволяющая попарно сравнивать какие - либо характеристики областей F i и G j. В частности, для сравнения форм - разбиений с частично или полностью упорядоченной яркостью определим EBD - метрика (8) эквивалентна ранее введенной L 1 - метрике (3).

R B D- метрики для сравнения форм - отношений Обобщение 3. EBD-метрики второго порядка вида где d ( F ( W ij,W kl ), G ( W ij,W kl )) – предбазовая метрика сравнения отношений предлагается называть R B D- метриками ( Relation Based Distance ).

RMD- метрики и задачи оптимизации RBD-метрик Обобщение 4. Если значения S ij трактовать не как набор площадей пересечения областей кадра фиксированной геометрии, а как набор переменных мер соответствия между элементами обобщенной реляционной модели формы, то для определения RMD- метрики ( Relation EMD ) необходимо решать оптимизационную задачу следующего вида : Это задача квадратичного программирования, разрешимая по Куну - Такеру.

Потенциальные области применения Сравнение моделей сегментированных изображений сцен с наборами пространственных и семантических отношений между объектами ; Сравнение описаний формы сегментированных 2 D и 3 D фигур с наборами топологических, геометрических и других отношений между частями фигур ; Сравнение результатов классификации и кластеризации в многомерных пространствах признаков в задачах машинного обучения. Сравнение теорий ( онтологий ), описывающих единую предметную область.

Сравнение моделей сегментированных изображений сцен с наборами пространственных и семантических отношений между объектами 2. Сохранены относительные расположения 3. Сохранены только площади 1. Сохранены площади, относительные ориентации и расположения 1 23

Сравнение описаний формы сегментированных 2D и 3D фигур с наборами топологических, геометрических и других отношений между частями фигур

Сравнение результатов классификации и кластеризации в многомерных пространствах признаков в задачах машинного обучения GXGX X gXgX gXgX X fXfX FXFX fXfX

Заключение 1.В работе предложен обобщенный класс моделей описания формы сегментированных изображений набором произвольных отношений между областями разбиения кадра – T R - модели ( Tessellation based Relational shape models ). 2.Показано, что получаемые на основе TR - моделей метрики сравнения форм в общем случае представляют собой специальный класс EMD - метрик второго порядка, который предложено называть RMD - метриками ( Relation Moving Distance ). 3.Возможные направления дальнейших исследований могут быть связаны с построением конкретных прикладных RMD - метрик, а также с построением RMD - метрик для сравнения предметных онтологий ( онтологических метрик ).

Литература [1] Пытьев Ю. П., Чуличков А. И. Методы морфологического анализа изображений // М.: ФИЗМАТЛИТ, с. [2] Каркищенко А. Н., Гончаров А. В. Исследование устойчивости знакового представления изображений // Автоматика и телемеханика. 9. С [3] Броневич А. Г., Гончаров А. В. Аксиоматический подход к измерению информативности знаковых представлений изображений // Известия РАН. Теория и системы управления. 6. C [4] Y. Rubner, C. Tomasi, and L. J. Guibas. The Earth Movers Distance as a Metric for Image Retrieval, International Journal of Computer Vision, 40(2):99-121, [5] Визильтер Ю. В., Рубис А. Ю. Морфологические коэффициенты корреляции форм изображений для задач комплексирования многоспектральной видеоинформации // Вестник компьютерных и информационных технологий, N3, 2012, с [6] H. Ling and K. Okada. EMD-L1: An Efficient and Robust Algorithm for Comparing Histogram-Based Descriptors, European Conference on Computer Vision (ECCV), LNCS 3953, III: , 2006.