<<
>>

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

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

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

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

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

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

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

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

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

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

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

Данная метка будет использоваться то­гда, когда объекту на текущем изображении не может быть поставлена в соот­ветствие любая из меток базового изображения. Данная ситуация может возни­кать когда на текущем изображении, из-за шумов и погрешностей, ошибочно выделены какие-либо ложные объекты. При корректной маркировке объектов в подмножестве О kтолько одному из объектов может быть поставлена в соответ­ствии ненулевая метка Ak, остальные объекты должны быть промаркированы нулевой меткой Aq . Таким образом, множество меток, которыми можно промар­кировать объекты в подмножестве Okсоставляет подмножество Ak = {λk, Λq} .

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

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

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

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

Атрибуты и связи нулевой метки Aqне за­даны, так как ее атрибуты включают все возможные атрибуты других меток, а связи нулевой метки — все возможные связи с другими метками.

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

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

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

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

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

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

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

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

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

та Okiметкой Λjt.

Поскольку AhRвсегда являются константами (базовое изображение всегда одно и то же) и они всегда находятся в условной части рассматриваемых величин, то мы их будем опускать при записи дальнейших выражений. C учетом данного замечания выражение (5.5) будет иметь вид

247

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

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

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

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

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

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

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

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

t

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

Здесь атрибуты объектов и связи между ними выступают в роли «подкрепляющей» информации, доказываю­щей или опровергающей рассматриваемую гипотезу. Чем более полно атри­буты объектов а и связи между объектами г будут соответствовать атрибу­там меток А и связям между метками R при условиитем вероятнее

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.3.2.

<< | >>
Источник: ЛУКЬЯНОВ АНДРЕЙ АНАТОЛЬЕВИЧ. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В ПРОБЛЕМЕ ОБЕСПЕЧЕНИЯ ТОЧНОСТИ ДВИЖЕНИЯ И ПОЗИЦИОНИРОВАНИЯ МОБИЛЬНЫХ МАНИПУЛЯЦИОННЫХ РОБОТОВ. ДИССЕРТАЦИЯ на соискание ученой степени доктора технических наук. Иркутск - 2005. 2005

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