Вероятностный метод сопоставления оринетиров
Постановка задачи
Сформулируем задачу выбора корректного ориентира на текущем изображении при наличии нескольких кандидатов. Данная задача может быть сведена к задаче маркировки объектов.
Введем понятия объекта и метки. Ориентиры- кандидаты в текущем изображении будем называть далее объектами, а ориентиры в базовом изображении — метками. Задача маркировки объектов сводится к построении ассоциативной связи между множествами объектов и меток, т.е. к присвоению каждому объекту некоторой метки из множества меток.Ориентиры на базовом изображении образуют множество меток
На текущем изображении, при помощи некоторого алгоритма, выделены 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) позволяет вычислить апостериорные вероятности гипотез на основании априорных вероятностей этих гипотез и некоторой «подкрепляющей» информации, условно связанной с гипотезами и выраженной через условные вероятности, словленная данным вариантом маркировки.

будет эта гипотеза варианта маркировки.
Получим выражение для вычисления условной вероятности Для этого введем некоторые эмпирические предположения, упрощающие получение такого выражения.
Предположение 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.