Вероятностные методы сегментации видеопотока как задача с недостающими данными

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

• -    пороговые методы сегментации, основанные на резких изменениях базовых свойств сигналов (яркости, разрывности, связности пикселей) и предназначенные для выращивания, слияния и разбиения областей;

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

Вероятностные методы сегментации относятся к задаче с недостающими данными. Рассмотрим задачу сегментации видеопотока на движущиеся области, которая заключается в сопоставлении моделей движения «перемещающимся» пикселям. Предположим, что в каждом пикселе изображения вычисляется ^-мерный характеристический вектор Х , в котором собрана информация о положении, цвете и текстуре. Данный вектор может содержать различные представления цвета и выходные реакции набора фильтров, центрированных на конкретных пикселях. Моделирование изображения заключается в том, что каждый пиксель считается порожденным одним из g сегментов изображения, имеющим соответствующую плотность распределения. Таким образом, для получения пикселя выбирается сегмент изображения, а затем по функции плотности распределения генерируется пиксель.

Предположим, что сегмент S_; выбирается с вероятностью Р, а плотность распределения определяется гауссианом с параметрами 9 _; = ( ц _;, о _;), зависящими от конкретного сегмента. Это означает, что вероятность генерации вектора пикселя можно записать в виде

P ( X ) = £ ДР ( X / 9 1 )•

l

Модель такого типа называется моделью смеси, поскольку она представляет собой взвешенную сумму элементов смеси, описываемых вероятностными моделями. Параметры Р; обычно называются весовыми коэффициентами элементов смеси. Модель смеси можно интерпретировать как обобщенную, когда осуществляется выбор ,-го компонента модели с вероятностью Р; и производится выборка из условных вероятностей Р(Х/9;). В этом случае модель представляет собой распределение плотностей вероятности в пространстве характеристических векторов, иными словами, модель состоит из набора g сегментов, каждый из которых соотнесен с фрагментом изображения. Требуется определить: а) параметры каждого сегмента; б) весовые коэффициенты элементов смеси и в) фрагмент изображения, породивший каждый пиксель.

Все указанные параметры запишем как вектор параметров, причем весовые коэффициенты обозначим как а, а параметры каждого фрагмента как 9 _; = ( ц _;, о _;). В результате получим вектор 9 = (а₁,..., a_g, 9^..., 9_g). Таким образом, модель смеси принимает следующий вид:

g

P ( X , 9 ) = £ a 1 P 1 ( X /9 1 ),

1 = 1

где плотность каждого компонента Р( Х / 9 _;) выражается гауссианом. Поскольку функция распределения вероятностей часто известна с точностью до значения параметров, то восстановление распределения вероятностей сводится к определению значений параметров на основе имеющейся выборки. Среди таких параметрических методов восстановления плотности распределения вероятностей наиболее эффективным является метод максимального правдоподобия, а также методы, основанные на байесовской оценке.

Метод максимального правдоподобия в задаче о восстановлении плотности распределения вероятностей в классе функций Р( Х / 9 _;) связан с исследованием функции правдоподобия Фишера. Функция правдоподобия равна [1]

L ( X 1 , X ₂,..., X n / 0 ) =

Ng

= П^ 1P( Xj/91 )= j=11=1                                    (1)

N

= П P ( X j , 0 ).

j = 1

Эта функция задается на выборкеХрХ2, .,Х^. Если величины дискретны, то функция правдоподобия для каждого 9 определяет вероятность того, что случайная и независимая выборка образует последовательностьХ1,Х2, . .,XN. Если же величины непрерывны, то функция правдоподобия понимается как плотность совместного распределения величинХ1,Х2, .,ХМ. При этом каждой выборке может быть поставлена в соответствие своя функция правдоподобия. Метод максимального правдоподобия заключается в нахождении таких значения параметра 9, которые доставляют максимум функции (1). Иногда вместо данной функции рассматривается логарифмическая функция вида lnL(X1,X2,....,XN /0) =

Ng

= 2 ln £ а i ? i ( X j /О I ) =            ₍₂₎

j = 1 I = 1

N

= £ ln P ( X j , 0 ).

j = 1

Поскольку максимумы функций (1) и (2) совпадают, они могут быть найдены либо из уравнения dL(X1,X2,...,Xn /0) = 0

^{д 0} j               ’               (3)

j = 1, 2,..., m , либо из уравнения дlnL(X1,X2,...,XN /0) = 0

д 0 j                ’             (4)

j = 1, 2,..., m .

Основное достоинство этого метода состоит в том, что для некоторых функцийР( Х / О _/), которые при достаточно большом объеме выборки аппроксимируются нормальным распределением, он обеспечивает асимптотическую несмещенность и асимптотическую эффективность оценки максимального правдоподобия. Если знать компонент, который породил пиксель, то вектор О определить просто. В этом случае для каждого элемента 0 _z можно использовать оценку по принципу максимального правдоподобия. Тогда значение a _z - это доля компонента / в изображении. Если знать вектор О , то для каждого пикселя можно определить компонент, который породил данный пиксель с наибольшей вероятностью.

Другой способ вычисления параметров распределения основан на применении формулы Байеса

P ( а / X ) = ^{P ( а ) P ( X} / ^о) .

P ( X )

Этот способ называется байесовским принципом восстановления параметров. Предположим, что плотность распределения параметраР( а ) заранее известна. Она характеризует предполагаемую возможность существования различных значений параметра а до проведения эксперимента. Апостериорная вероятность ^( аХ^Х , ^, Х _х) характеризует такую же возможность после получения информации из экспериментальной выборки Х^ Х ₂,..., X _v Если эксперименты случайны и независимы, то с учетом функции правдоподобия (1)по формуле Байеса получаем

P ( a ) L ( X 1 , X 2 ,..., X n / а )

( La / .^ X )                                                              ,

• ⁷      P ( X 1 , X 2 ,..., X N )

где

P ( X 1 , X 2 ,..., X N ) =

= J L ( X 1 , X ₂,..., X _N / a ) P ( a ) d a

S для непрерывных a (5- множество сегментов изображения) и

P ( X 1 , X 2 ,..., X N ) =

g

= £ L ( X 1 , X 2 ,..., X n / а 1 ) P ( a i )

l = 1

для дискретных а .

Теперь задача сводится к определению параметра а по известной величинеР(а/Х). Этот параметр можно оп ределить как математическое ожидание вида

M a = J a P ( a / X 1 , X ₂,..., X _N ) d a .

S

В качестве искомого значения параметра может быть выбрано такое значение а, которое доставляет максимум функцииР( а / Х ).

Рассмотренные методы оценки не являются равнозначными ни по сложности их реализации, ни по эффективности. Главная сложность реализации метода максимального правдоподобия состоит в отыскании решения системы уравнений (3) и (4). Реализация байесовской стратегии связана с громоздкими вычислениями. Как прави ло, эта стратегия реализуется лишь тогда, когда удается провести аналитическое интегрирование выражения Р(Х) =

= f Р(оДОМ^^       ^  (5)

Р(ХъХ2-Лу)

S

Численное интегрирование выражения (5) представляет собой очень трудную задачу.

Также для оценки параметров распределения может быть использован метод стохастической аппроксимации, общая схема которой представляется следующей процедурой [1]:

а [н] = а[н - 1] - g[n] Q(X[н], а[н - 1]), (6) где X [н] - изменяемая в процессе эксперимента величина; Q(X, a ) - некоторый функционал от фиксированного вектора Х .

Для отдельных классов распределений (например, для экспоненциальных распределений) критерий оптимальности можно представить как выборочное среднее. Тогда если функционал Q(X, a ) - квадратичная функция относительно а, то алгоритмы стохастической аппроксимации приводят к тем же результатам, что и байесовы алгоритмы. Если же параметры а находить из условия максимума функции правдоподобия, т. е. Q(X, a ) = L( X , а ), то получим оценки, равнозначные тем, которые получают по методу максимального правдоподобия.

Рассмотрим формальную постановку задачи с недостающими данными. Предположим, что имеются два пространства - полное пространство данных ПХи неполное пространство данных Пг Существует отображение/, переводящее пространство ПХ в пространство Пу.При таком отображении данные «теряются», порождая недостающие данные. В контексте сегментации изображения полный набор данных включает характеристики всех пикселей, а также набор переменных, указывающих, какой компонент смеси предоставил такие характеристики. Неполный же набор данных получается при отбрасывании второго набора переменных. Пусть также имеется пространство параметров П^, состоящее из весовых коэффициентов компонентов смеси и параметров каждого компонента смеси. Задача заключается в нахождении оценки указанных параметров по неполному набору данных с применением одного из вероятностных методов. Наиболее приемлемым из рассмотренных методов является метод максимального правдоподобия, поскольку он является компромиссным вариантом относительно других вероятностных методов с точки зрения сложности вычислений и величиной оценки потерь. Требуется найти оценку указанных параметров при наличии неполного набора данных.

Обозначим плотность вероятности полного набора данных какР( х , и ). Тогда логарифмическая функция вероятности полного набора данных в соответствии с формулой (2) запишется в виде

L ( x / u ) = ln П P ( x j , u ) =

j

= Х ^{ln( P (} x j , u ⁾⁾- j

Если известно, какой сегмент породил каждый пиксель, то с помощью логарифмического правдоподобия можно оценить параметры каждого сегмента изображения. Проблема заключается в том, что имеющиеся данные являются неполными. Обозначим плотность вероятности при неполном наборе данных какР( у , и ). Плотность вероятности для неполного пространства данных получается интегрированием плотности вероятности для полного пространства данных по всем значениям, равным у Таким образом,

Р( у , и ) = J P ( f ( x ), u ) d x ■ п ^y

Тогда функция правдоподобия для неполных данных в соответствии с формулой (1) записывается следующим образом:

N

LW) = П P ( У j , u )■ j = 1

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

Д у , и ) = ln П P ( У j , u ) = j

= £ ^ln( P ⁽ У j , ^u )) =

j

= £ ln J P ( f ( x ), u ) d x ■

j

п

y

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

Можно предложить следующую стратегию решения данной задачи:

• -    получить некоторую оценку компонента, породившего характеристический вектор пикселя, используя значение 6 , ;

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

Данная процедура повторяется до схождения, хотя гарантия полной сходимости отсутствует, так как объем неполных данных на изображении не известен. Эта процедура является частным случаем общего алгоритма. Предположим, что логарифм функции правдоподобия полного набора данных представляет собой линейную зависимость по отсутствующим переменным. Напомним, что в модели смеси недостающими данными являются переменные, указывающие, из какого компонента смеси извлечен элемент данных. Для этого с каждой информационной точкой сопоставим вектор z , имеющий g элементов. Если/-ая информационная точка поступила от ,-го компонента смеси, то элемент z , равен единице, в противном случае он равен нулю. Следовательно, х = [ у , z_y] и модель смеси можно переписать следующим образом:

P ⁽ У ) = £ P l Р( у , и )

Поскольку логарифм функции правдоподобия для полного набора данных линеен по отсутствующим пере менным, то он запишется в виде

^1пДу^{, и )} = ^ £ z j ln P ( y j / u ) ■ j 1 1 = 1                     ,

Основная идея алгоритма заключается в следующей итеративной процедуре. На шаге н формируется ожида емое значение полного набора данных на основе неполных данных и текущих значений параметров. Известно ожидаемое значение вектора у [н], поэтому требуется вычислить только ожидаемое значение вектора z. [н] для каждого параметра,/. Затем ожидаемое значение вектора z. [н] подставляется в логарифмическую функцию правдоподобия полного набора данных и находится макси мум относительно вектора и [н]. В этот момент ожидаемые значения вектора z. [н] могут изменяться. Таким образом, вычисляется величина

и [ n + 1] = arg max L ( x , u [ n ]) =

u

= arg max L ([ y / z [ n ]], u [ n ])■

u

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

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

Q(u, u[n]) = JL(x, u) P([x/ u [n]], y) dx, которая представляет собой зависимость от оценки пара- метров на предыдущем шаге итерации. Теперь найдем максимум данной функции относительно вектора и:

u [ n + 1] = arg max Q ( u , u [ n ]).

u

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

Применим рассмотренный выше вероятностный метод сегментации на основе вычисления функции максимального правдоподобия к анализу видеопотоков, снятых движущейся камерой. Видеопотоки часто состоят из больших сегментов, имеющих близкие параметры движения (направление, скорость, ускорение). Предположим, что дана последовательность из двух следующих друг за другом кадров, и требуется определить наличие движения в каждом пикселе первого кадра. Требуется определить набор уровней движения, которые сопоставляются с объектами, расположенными на различных расстояниях от движущейся камеры. При этом возникает впечатление, что объекты, расположенные ближе к камере, «перемещаются» быстрее, чем удаленные объекты. В этом случае модель движения можно назвать многоуровневой. Предположим, что для получения уровня движения используется модель смеси, причем сегменты не обязательно имеют гауссову плотность распределения. Базовая модель видеопотока основана на следующих фактах:

• -    в каждом пикселе текущего кадра имеется вектор движения, соединяющий его с пикселем следующего кадра;

• -    имеется набор различных параметрических уровней движения, каждое из которых получено на основе собственной вероятностной модели;

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

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

Пусть пиксель в точке с параметрами (и, v) первого изображения принадлежит /-му уровню движения, имеющему параметры 9 _/. Это означает, что на втором изображении этот пиксель переместился в точку с параметрами (и, v) + т (и, v, 9 _/) и яркости этих двух пикселей ^(и, v) и 7₂(и, v) равны с точностью до ошибки измерения С. Уровень движения можно обозначить переменной V_{uv /}, которая принимает значение единицы, если пиксель с параметрами (и, v) относится к /-му уровню движения, и нуль в противном случае. Предполагается, что на значения интенсивностей пикселей изображения влияет гауссов шум с дисперсией s. Тогда логарифм функции правдоподобия полного набора данных запишется следующим образом:

L (V , 0 ) =

= - L V uv , l uv , l

( 1 1 ( u , v ) - 1 2 ( u + m i ( u , v , 6 1 ), v + m 2 ( u , v , 6 1 ))) ²

2 _O ²

где 9 = ( 9 ₁,^, 9 _g).

Далее следует определить величины вероятностей уровней движения:

P(V uv , l = 1| I 1 , 1 2 , 0 ).

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

( m i в ( a il ^a 12 ( ^u ,( ^a 13

⁽ и , v , ⁶ 1 ⁾ = I                 I +1          ,

(m2 J           (a21 a22 J(v J (a23 J где 9/ = (я11,^,я23).

Карту можно упростить, оставив только выбранный уровень движения, для того, чтобы проверить, насколько движение соседних пикселей согласуется с движением пикселей на предыдущих и последующих кадрах. Модель многоуровневого движения полезна по ряду соображений: во-первых, она связывает пиксели, «движущиеся» в одном направлении, во-вторых, имеется возможность оп ределения границ движения, и в-третьих, последовательности кадров можно восстанавливать по имеющимся уровням движения, когда некоторые уровни отсутствуют

Однако возможна ситуация появления посторонних объектов в зоне видеонаблюдения, поскольку модель не предсказывает частоту их появления. Как правило, вероятность появления посторонних объектов на изображении мала, и требуется уделить внимание «хвостовым» частям функции нормального распределения. Для этого можно построить явную модель посторонних значений, учитывающую взвешенную функцию правдоподобия Р(измерения | модель) и член посторонних значений Р(выбросы):

(1-1) Р(измерения | модель) +1 Р(выбросы), где параметр 10 [0,1] моделирует частоту появления посторонних значений, а Р(выбросы) - некоторая вероятностная модель посторонних значений.

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

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

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