Вероятностный метод сопоставления оринетиров

Постановка задачи

Сформулируем задачу выбора корректного ориентира на текущем изображе­нии при наличии нескольких кандидатов. Данная задача может быть сведена к задаче маркировки объектов.

Ориентиры на базовом изображении образуют множество меток

На текущем изображении, при помощи некоторого алгоритма, выделены N объектов O_iє О, образующие множество объектов О = {θ₁,O₂,-.-, O_n].Пе­регруппируем объекты во множестве О в Mподмножеств

I где подмножество O_a C=O включает в себя те объекты (ориентиры- кандидаты), которые могут быть сопоставлены с меткой λ_k. Если для каждой из меток на базовом изображении отобрано равное количество кандидатов К, то подмножества O_kбудут иметь равный размер

Объект на текущем изображениисчитается промаркированным,

если он поставлен в соответствие метке λ_kиз базового изображения. В данном случае будем считать, что объект O_ki, промаркирован меткой λ_k. Введем сокра­

щенное обозначение этого факта как O_ki: A_k.

Введем понятие нулевой метки Aq.

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

Каждая метка A_kв базовом изображении имеет набор атрибутов A_kи набор связей с другими метками R_i. Атрибуты и связи вычисляются по ин­формации базового изображения. Такая постановка задачи позволяет пред­ставить набор меток базового изображения в виде графа, каждый узел кото­рого имеет свой набор атрибутов, а соединяющие узлы дуги — веса. Веса дуг являются некоторой функцией от набора связей метки с другими метками. Полное множество атрибутов записывается как

Полное множество связей:

В результате имеем граф с множеством узлов Л с атрибутами А, кото­рые связаны множеством дуг R.

Примером атрибута метки, связаной с ориентиром на базовом изображе­нии, может служить среднее значение интенсивностей пикселей в некоторой

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

Аналогично меткам, объекты в совмещаемом (текущем) изображении также имеют набор атрибутов a_z∙, и набор связей r_i, и также могут быть представлены в виде графа с множеством узлов О с атрибутами а, которые связаны множеством дуг г. Полное множество атрибутов имеет вид а множество связей

гдеТаким образом, задача маркировки объек­

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

Вероятностная формулировка задачи маркировки объектов

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

Из всех возможных вариантов маркировки объекта в качестве истинного варианта принимается гипотеза маркировки с наибольшей вероятностью. Ос­новываясь на принятых в предыдущем разделе условных обозначениях, за­пишем вероятностную задачу маркировки объекта O_ki: λ_kкак

где- условная вероятность гипотезы маркировки объек­

та O_kiметкой Λ_jt.

247

Таким образом, в вероятностной постановке задача маркировки сводится к вы­числению условной вероятности гипотезы маркировки объекта всеми допусти­мыми метками и выбора варианта маркировки с наибольшей вероятностью.

Задача маркировки объектов, для упрощения, решается для каждого объекта в отдельности. Ее сложность имеет вид— для каждого из Nобъектов

возможно M +1 вариантов маркировки. Если бы задача маркировки решалась для всех объектов в совокупности, то ее сложность была бычто не позво­

ляет ее решить в приемлемое время.

Вычисление условной вероятности гипотезы сопоставления ориентиров

Вероятность гипотезы маркировки объектаявляется ус­

ловной вероятностью, так как она зависит от множества значений атрибутов объектов а и связей г. Данный раздел посвящен выводу выражения для вы­числения этой условной вероятности.

Так как гипотезы маркировки объектов попарно несовместны, условная вероятность гипотезы H_iиз множества попарно несовместных гипотез Н, обусловленная неким событием E, вычисляется по формуле Байеса

t

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

будет эта гипотеза варианта маркировки.

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

Предположение 1: Атрибуты объектов а и связи между объектами г услов­но независимы друг от друга.

Иными словами, атрибуты объектов могут изменяться совершенно неза­висимо от связей между объектами. Это приводит к ограничению, что атри­буты объектов не могут быть использованы для вычисления связей между объектами. На основании сделанного предположения и свойств независимых случайных событийполучим

Получим выражения для вычисления условных вероятностей в (5.9).

Условная вероятностьявляется вероятностью того, что множе­

ство атрибутов объекта а будет совпадать с множеством атрибутов метки А при условии, что объект O_kiпомечен меткой λ_k. Выражение для вычисления данной условной вероятности можно получить в упрощенном и полном виде.

1. Упрощенное выражение для p(a ∣ O_ki: λ_k) имеет вид

Данное упрощенное выражение учитывает вероятность совпадения атрибу­тов а₍ и A_kпри маркировке объекта

Но данное выражение не учитывает вероятности совпадения атрибутов дру­гих объектовс атрибутами меток при всех возможных вариантах мар­кировкиУсловное обозначение ∀определяет операцию «для всех».

2. Полное выражение для) учитывает указанное в предыдущем

абзаце обстоятельство и имеет вид

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

(маркировка объекта одной меткой исключает маркировку этого же объекта другой меткой).

Так как все объекты должны быть маркированы, то в этом случае необ­ходимо вычислить вероятность совмещения всех событий. Согласно аксиоме о совмещении независимых в совокупности событий

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

Условная вероятностьявляется вероятностью того, что мно­

жество связей между объектами г будет соответствовать множеству связей между метками R при условии, что объект O_kiпомечен меткой λ_k. Введем следующие упрощающие задачу предположения:

Предположение 2: Предположим, что подмножества связей η объекта O_iи r_y∙ объекта Ojусловно независимы друг от друга.

Предположение 3: Предположим также, что все связи r_ijв подмножестве ■ связей r_z∙ объекта O_iусловно независимы друг от друга.

На основании предположения 3 выражение для вычисления условной ве­роятностиупрощается до

Согласно постановке задачи, каждая связь r_ijв подмножестве г,- является бинарным отношением между объектами O_iи Oj. Эта бинарная связь зависит не только от того, какая метка присвоена объекту O_i, но и от того какая метка присвоена объекту Oj. Таким образом, для каждой связи r_ijдолжна быть полу­чена условная вероятностьгде в условной части имеется

не только гипотеза маркировкино и гипотеза маркировки

Проведя цепочку рассуждений, аналогичную рассуждениям, использо­ванным для получения выражения (5.10), получим выражение для

Согласно аксиоме о вероятности совмещения двух событий 250

вероятность совмещения двух гипотез маркировки для различных объектов в выражении (5.11) запишется в виде где- априорная вероятность гипотезы маркировки O_lj : λ∣.

Подставив выражения (5.9), (5.10) и (5.12) в (5.8) получим где

5.3.2.