Венгерский алгоритм в задаче слежения за множеством движущихся объектов

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

В общем случае решение задачи слежения содержит три основных этапа:
– выделение сегментов;
– установление соответствия между выделенными сегментами и отслеживаемыми объектами;
– уточнение или прогнозирование положения объектов интереса.

Сегментом в данном случае называют связную область изображения, выделяемую по признаку движения. В рамках данной заметки нас будут интересовать 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-го сегмента не найдено подходящего объекта [ситуация (в)].

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

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

Конечно, описанная выше схема достаточно проста. В более сложных сценариях следовало бы обрабатывать заслонения объектов путем слияния и разделения треков. Однако, это уже совсем другая история…
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 2

    +1
    Мне в своё время показалось, что разумно использовать не 2, а 3 группы объектов: отслеживаемые найденные (уточнённые), отслеживаемые ненайденные (прогнозируемые) и недавно обнаруженные (предсказание которых ещё работает плохо, т.к. вектор состояния для Калмана ещё не определён, да и скорее всего просто шум зафиксировался как объект).

    «путем слияния и разделения треков»
    Это как?
      +1
      Спасибо за замечание. Действительно, объекты, которые были недавно обнаружены, стоит рассматривать отдельно. Однако, это вопрос вторичной обработки. На практике для каждого объекта подсчитываются время наблюдения, время в прогнозе, стабильность во времени и другие характеристики, которые позволяют принять решение о возможности сопровождения объекта. Между тем, с точки зрения рассматриваемого в статье алгоритма, объекты с малым временем жизни не отличаются от устойчивых объектов. Для них также необходимо искать соответствия с сегментами на текущем кадре и, в случае нахождения соответствия, уточнять их положение и другие параметры. Таким объектам можно присваивать уникальные метки только по прошествии какого-то времени, можно просто не показывать треки или что-то еще придумать. Это, на мой взгляд, зависит от конкретной задачи.

      Что касается слияния и разделения треков. Давайте посмотрим, что происходит сейчас при заслонении объектов. Один из объектов (причем заранее не ясно какой) остается наблюдаемым (с точки зрения алгоритма), другой уходит в прогноз. При этом алгоритм может перепутать объекты и для объекта, который едет влево, строить прогноз в правую сторону. Наоборот, для объекта, который алгоритм считает наблюдаемым (тот который на самом деле едет вправо), он начинает обновлять параметры фильтра Калмана таким образом, что искажает реальное положение дел. Кроме того, даже в случае правильной работы алгоритма, при слишком долгом слиянии или маневрах объектов для того из них, который находится в прогнозе, сам прогноз может оказаться уже некорректным и перезахвата не произойдет — объекту будет присвоена новая метка (что не совсем соответсвует желаемому результату).

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

    Only users with full accounts can post comments. Log in, please.