[Из песочницы] Венгерский алгоритм в задаче слежения за множеством движущихся объектов
Хочу рассказать об известном, но мало освещенном в литературе подходе к слежению за множеством движущихся объектов. Сложность этой задачи во многом заключается в том, что алгоритмы обнаружения и выделения объектов часто дают сбои, а сами объекты могут заслоняться другими объектами и элементами фона.
В общем случае решение задачи слежения содержит три основных этапа:
– выделение сегментов;
– установление соответствия между выделенными сегментами и отслеживаемыми объектами;
– уточнение или прогнозирование положения объектов интереса.
Сегментом в данном случае называют связную область изображения, выделяемую по признаку движения. В рамках данной заметки нас будут интересовать 2-й и 3-й из перечисленных этапов.
Общая постановка задачи
Будем считать, что в текущем кадре по признаку движения выделены один или более сегментов. Для этого можно использовать вычитание фона, оптический поток, методы на основе смеси гауссовских распределений и др. В результате вместо исходного полутонового изображения получим бинарное изображение, как это показано на рисунке ниже.
В виду наличия шума и различных атмосферных искажений, результаты выделения содержат ошибки, которые легко можно устранить с помощью методов математической морфологии. Вначале следует применить морфологическое открытие, что позволит убрать малоразмерные сегменты и точечный шум. Затем можно применить морфологическое закрытие, чтобы восстановить форму объектов. В результате получим очищенное изображение (см. рисунок), которое в дальнейшем подвергается разметке и параметризации. Список найденных сегментов и их параметры являются исходными данными для алгоритма слежения.
Итак, в результате работы алгоритма выделения объектов может быть получен список обнаруженных на данном кадре сегментов, однако, чтобы решить задачу слежения за объектами, необходимо сопоставить каждому из этих сегментов объект, известный на предыдущем кадре, либо принять решение об обнаружении нового объекта. Иногда ошибочно обнаруженные сегменты являются достаточно устойчивыми во времени и существуют в близких точках пространства на протяжении нескольких кадров. С другой стороны, иногда правильно обнаруженные сегменты кратковременно исчезают. Поэтому должен быть механизм, который, во-первых, принимает решение об обнаружении нового объекта, во-вторых, фильтрует неустойчивые во времени ложные сегменты, в-третьих, устанавливает соответствие между известными ранее объектами и новыми сегментами, в-четвёртых, прогнозирует координаты объектов при кратковременном пропадании, в-пятых, принимает решение о потере объекта.
Для придания алгоритму слежения устойчивости к временному закрытию объекта участками фона для каждого объекта вводится персональный траекторный фильтр, главная задача которого – прогноз координат объекта в следующем кадре на основе анализа траектории движения объекта. Обычно в качестве такого фильтра используется фильтр Калмана.
При временном закрытии объекта участками фона или другими объектами уточнение параметров траектории не выполняется, и траекторный фильтр работает в режиме прогнозирования координат.
При наличии в последовательности изображений множества объектов слежения возникает вероятность перепутывания объектов в ситуациях пересечения траекторий их движения. После пересечения траекторий объекты должны получать те же идентификаторы, что были у них до пересечения. Пример правильного назначения идентификаторов показан на рисунке.
Слежение за объектами на основе венгерского алгоритма
В качестве первого шага алгоритма слежения необходимо установить соответствие между сегментами, найденными в текущем кадре, и отслеживаемыми объектами. С этой целью между каждым i-м объектом и каждым j-м сегментом вычисляется количественная мера сходства. В качестве такой меры можно использовать евклидово расстояние между прогнозируемыми координатами объекта 
и центром сегмента 
, т.е.
Следует учесть, что на изображении могут появляться новые объекты, а прослеживаемые в течение некоторого времени объекты могут покидать пределы кадра или временно заслоняться препятствиями. Будем рассматривать три вида ситуаций:
а) найдено соответствие между объектом и сегментом;
б) для данного объекта не найдено соответствия среди сегментов;
в) для данного сегмента не найдено соответствия среди объектов.
Евклидово расстояние можно рассматривать как стоимость принятия решения (а) о соответствии между i-м объектом и j-м сегментом. Введем величину Et, задающую стоимость решения (б), и величину Es, задающую стоимость решения (в).
В итоге приходим к решению следующей задачи: необходимо установить соответствие между сегментами и объектами или принять решение о невозможности такого сопоставления таким образом, чтобы суммарная стоимость всех решений была минимальной. Данная задача известна как задача о назначениях, для ее решения используется венгерский алгоритм.
Чтобы применить венгерский алгоритм, необходимо составить квадратную матрицу стоимости размера NM=Nt+Ns, где Nt – число отслеживаемых объектов, а Ns – число найденных сегментов. Матрица стоимостей имеет следующий вид:
где Dmax – достаточно большое число, такое что Dmax >> Eij. По строкам матрицы отсчитываются отслеживаемые объекты, по столбцам – найденные сегменты.
В результате выполнения венгерского алгоритма получим список пар (t,s)k, k,t,s=1..NM.
Если t<=Nt и s<=Ns, то между t-м объектом и s-м сегментом установлено соответствие [ситуация (а)].
Если t<=Nt и s>Ns, то для t-го объекта не найдено соответствующего ему сегмента [ситуация (б)].
Если t>Nt и s<=Ns, то для s-го сегмента не найдено подходящего объекта [ситуация (в)].
Каждая из перечисленных ситуаций приводит к необходимости выполнения различных действий. В первом случае следует обновить список параметров объекта на основе параметров соответствующего ему сегмента. Во втором случае обновление невозможно, однако отсутствие соответствующего сегмента может объясняться временным заслонением объекта. Поэтому в этом случае следует перейти к прогнозированию параметров объекта на основе предыдущих наблюдений. Для уточнения и прогнозирования координат объектов используется фильтр Калмана. Наконец, в третьем случае сегмент соответствует вновь появившемуся объекту.
В ходе наблюдения объекты могут покидать пределы кадра. В этом случае следует прекратить слежение за ними. Критерием определения подобных ситуаций является невозможность в течение достаточно длительного времени установить соответствие между данным объектом и каким-либо из выделенных в текущем кадре сегментов.
Конечно, описанная выше схема достаточно проста. В более сложных сценариях следовало бы обрабатывать заслонения объектов путем слияния и разделения треков. Однако, это уже совсем другая история…
