Обработка изображений / [Из песочницы] Отслеживание спортсменов в видеотрансляциях с помощью Particle Filter

Добрый день!

Я хочу рассказать вам о трекинге спортсменов в видео.

Введение

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

Матчасть

Содержание

• Вычитание фона
• Инициализация объектов
• Фильтр частиц
• Классификация частиц
• Вычисление параметров объекта

Само отслеживание ведется в real-time, то есть для работы используются данные только текущего и предыдущего кадра. Для автоматического исправления ошибок (это будет сделано позже) могут использоваться ранее полученные данные или система будет ждать новых данных, но сам трекинг использует только новый кадр и информацию, вычисленную с предыдущего.

Первый шаг — вычитание фона

Для вычитания фона используется либо предварительно обученный, либо онлайн обучающийся алгоритм. Так же можно использовать какие-либо простые быстрые алгоритмы выделения фона типа смеси гауссиан, но во время разработки нам была больше важна точность и удобство использования, поэтому мы остановились на ViBe (http://www2.ulg.ac.be/telecom/research/vibe/)

Алгоритм доступен open source, но мы использовали свою реализацию на MatLab.

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

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

Инициализация спортсменов

Для инициализации спортсменов может использоваться два подхода — ручная и полуавтоматическая инициализация.

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

В случае полуавтоматической инициализации мы можем назначать метку каждому блобу без метки на изображении. Это может не сработать, если скажем, в начале два спортсмена стоят рядом или загораживают друг друга. Но как только они разойдутся — второй будет проинициализирован.

У каждого спортсмена есть метка, bbox, скорость, начальная гистограмма и набор частиц (об этом ниже), которые присваиваются при инициализации.

Фильтр частиц

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

Тут встает несколько подзадач:

Как генерировать новые частицы?

Есть несколько подходов:

• Каждый раз генерировать полный набор частиц размещая их в пространстве случайным образом (внутри bbox с прошлого кадра или вокруг центра масс);
• Генерировать набор частиц и испускать их из одной точки (например, из центра масс)
• Использовать набор частиц с предыдущего шага для генерации новых

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

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

Старые частицы участвуют в генерации новых с вероятностью пропорциональной весу (то есть из частиц с большим весом генерируется больше новых частиц с такими же параметрами + разброс)

Изображение взято с http://perception.inrialpes.fr/~chari/myweb/Research/

Как учитывать маску переднего плана при подсчете гистограммы

• Не учитывать (зачем тогда она нужна, правда);
• Отбрасывать частицы с большим количеством фона;
• Не учитывать пиксели фона при подсчете гистограммы
• Учитывать количество фона в результирующем взвешивании

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

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

Как вычислять модель движения

Модель движения по своей сути представляет решение уравнения движения в дифференциальной форме, считая что каждый кадр — это малый промежуток времени.

Для текущей работы мы остановились на следующих параметрах:

$position_new = $position_old + $velocity_old + nrand()*$error_p; $velocity_new = $alpha * $velocity_old + (1 - $alpha) * ($position_new - $position_old) + nrand()*$error_v; $size_new = $size_old + nrand()*$error_s; 

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

Классификация частиц

Для классификации частиц при инициализации спортсмена мы снимаем с него «слепок» — трехмерную гистограмму в HSV(медленней) или RGB(менее качественно). Трехмерные мы делаем потому, что для обычных, линейных гистограмм наборы синего, красного и зеленого оттенков в итоговой гистограмме дадут серое распределение. В то время как трехмерные гистограммы при том же количестве бинов дадут более четкую картину.

За это мы платим скоростью обработки таких гистограмм (в матлабе нет встроенных быстрых функций для работы с ними), но при релизе на более быстром языке эти проблемы уйдут.

Модель HSV была выбрана из-за большей устойчивости к перепадам освещения при классификации. Классификация производится с помощью сравнения по метрике Бхаттачария (http://en.wikipedia.org/wiki/Bhattacharyya_distance) или Пересечения (http://locv.ru/wiki/7.4.1_Сравнение_гистограмм).

Вычисление параметров объекта

Довольно простая часть. Центр масс и скорость объекта вычисляется как средневзвешенное значение этого параметра для всех частиц. Ширина и высота берется исходя из центра масс и взвешенной дисперсии.

Псевдокод

Итого псевдокод выгляди следующим образом (для ручной инициализации). PHP выбран исключительно ради подсветки (вообще прогаем на матлабе и плюсах)

	$frame = load(firstframe); 	$bgSub.Learn($frame); # Обучить вычитание фона первым кадром 	$fgMask = $bgSub.sub($frame); # Получить маску переднего плана 	while $region = $user.getRegion() 	  $trackers[] = new tracker(64,get3DHistogram($region,$frame,$fgMask),$region); # Проинициализировать всех выделенных пользователем футболистов  	while $frame=load_frame() 	  $fgMask = $bgSub.sub($frame); 	  foreach $tracker in $trackers 	    $tracker.motionModel(); # Сгенерировать и сдвинуть частицы используя модель движения - в нашем случае позиция = позиция + скорость + рандом 	    $tracker.observationModel($frame); # Измерить наблюдаемые параметры частиц 	    $data = $tracker.measureModel(); # Посчитать параметры объекта             $result[$tracker,$frame.id] = $data; # Записать данные 	  $bgSub.updateModel($fgMask); 	

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

Результаты

На данный момент алгоритм, реализованный на матлабе может тречить 11 футболистов со скоростью 1-2 кадра в секунду на 96 частицах на объект. Ошибается алгоритм в моменты когда идет полное перекрытие и рядом стоит похожий объект (см. Видео), но мы работаем над этими ошибками.

Видео с примером работы (5 кадров в секунду, чтобы уследить за происходящим. 5 инициализированных объектов).

• Алгоритм справляется с почти полными перекрытиями;
• Алгоритм справляется с пересечениями траекторий объектов;
• Алгоритм не справляется когда рядом с перекрытым игроком стоит такой же

Что еще нужно сделать?

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

Полезные ссылки

• http://user.uni-frankfurt.de/~muehlich/sci/TalkBucurestiMar2003.pdf — Годная презентация о фильтре частиц и других методах обработки данных в динамических системах;
• http://www2.ulg.ac.be/telecom/research/vibe/ — использованный алгоритм ViBe;
• http://courses.graphicon.ru/main/vision/2009/lectures — Много лекций по компьютерному зрению;
• http://en.wikipedia.org/wiki/Particle_filter — Статья на енВики по фильтру частиц;

Автор: ScayTrase