Skip to main content

Отслеживание спортсменов в видеотрансляциях с помощью 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 инициализированных объектов).

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

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

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

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