Алгоритм сопровождения TLD (aka Predator)

В данной статье исследован алгоритм надёжного длительного сопровождения заранее неизвестных объектов в естественной среде. Алгоритм выдерживаем разрывы между кадрами, быстрое движение камеры, полное исчезновение, а затем появление объекта. Подход, который использован в данном алгоритме называется Сопровождение-Моделирование-Обнаружение (Tracking-Modeling-Detection (TMD)), он сочетает адаптивное сопровождение объекта с обучением детектора объекта в процессе распознавания. После того как объект был захвачен при помощи какого-либо алгоритма захвата, траектория объекта начинает наблюдаться двумя процессами (расширяющее и урезающее события). Они строят детектор объекта на лету. Оба процесса делают ошибки, стабильность системы достигается отменой событий. Обучение на лету и классификация производятся при помощи рандомизированного леса.

 
 
 
 
 
 

Математическое описание алгоритма

Пусть F_t и B_t – кадр видео ряда и описанный прямоугольник сопровождаемого объекта в момент времени t. Пиксели внутри прямоугольника B_t описываются вектором признаков x_t, который содержит информацию о наличии объекта сопровождения. Множество последовательных описанных прямоугольников определяет трек T_t=\{B_0, B_1\ldots B_t\} длины t+1, который определяет траекторию объекта в пространстве изображений. T_t^f описывает соответствующую траекторию в пространстве признаков U, которое является подпространством L^*. L^* представляет все возможные состояния наблюдаемого объекта. L^* неизвестно в момент начала сопровождения, когда выбрано первое измерение x_0\in L^*. Это первое измерение описывает начальное состояние модели в момент времени t=0: L_0=\{x_0\}.

Компоненты алгоритма взаимодействуют, как описано ниже. Объект сопровождается при помощи краткосрочного трекера. Траектория в пространстве признаков анализируется двумя событиями, которые непрерывно пытаются расширить или уменьшить пространство, описываемое моделью. L_t расширяется измерениями, которые скорее содержат сопровождаемый объект. Эти измерения определяются при помощи расширяющего события. Из L_t удаляются измерения, которые определены как не содержащие объект. Эти измерения определяются при помощи обрезающих событий. События работают параллельно, стремясь достичь L_t\rightarrow L^* (рис. 1).


 
 
 
 
 
 
 
 
 
 
 
 
 
 
Рис. 1: Модель объекта инициализируется первым кадром. Она увеличивается расширяющими событиями, уменьшается урезающими событиями. Постепенно она приближается к реальному объекту.

Главная цель построения L_t – это предоставить алгоритму память, чтобы создать детектор объекта, который непрерывно обновляется и улучшается. Он сканирует входное изображение F_t и выдаёт на выход множество описанных прямоугольников, которые содержат измерения, входящие в L_t. Эти прямоугольники описывают альтернативные гипотезы к позиции, возвращённой трекером. Слияние гипотез производится взятием позиции, которая минимизирует расстояние до L_t. Отсюда следует, что если положение от трекера очень близко к L_t, то ложные отклики детектора не влияют на трэк (пока они не станут ещё ближе к L_t, чем позиция от трекера). Минимальное расстояние до L_t становится очками недоверия к результату, выданному алгоритмом. Опираясь на эти очки, алгоритм решает, виден объект или нет.

Алгоритм 1 TMD
  Require Выбрать x_0, L_0 = \{x_0\}
  for t = 1 \colon \infty do
    Отслеживать последний патч x_{t-1}.
    Определить патчи, содержащиеся в модели L_{t-1}.
    L_t \leftarrow L_{t-1} \cup Положительные измерения из расширения.
    L_t \leftarrow L_{t-1} \setminus Отрицательные измерения из урезания.
    x_t \leftarrow Наиболее подходящий патч (определённый или от трекера).
  end for

Ранее было сказано о событиях, которые наблюдают краткосрочный трекер. Рассмотрим как они работают. Мы различаем две части L_t: правильную часть L^c_t \subset L^* и ошибочную часть L^e_t \not\subset L^*, L^c_t \cup L^e_t = L_t, L^c_t \cap L^e_t = 0. Покрытие(coverage) является долей измерений с объектом уже открытых неконтролируемым процессом обучения, т.е. coverage(L_t)=|L^c_t|/|L^*|. Примесью(impurity) называется доля L_t, которая неверна, т.е. impurity(L_t)=|L^e_t|/|L^*|. Оператор || обозначает размер множества.

Расширяющие события. В момент времени t краткосрочный трекер создал траекторию T_t^f=\{x_0, x_1\ldots x_t\}. Расширяющее событие сначала выбирает определённую часть траектории, которая рассматривается положительной, P \subset T^f_t. Модель объекта L_t затем обновляется, т.е. L_t=L_{t-1}+P. После этого обновления покрытие модели увеличивается, если P содержит хотя бы одно измерение из L^*. Стратегию выбора части траектории обсудим несколько ниже.

Обрезающие события. Невозможно придумать стратегию выбора, которая бы выбирала только верные измерения. По этой причине примесь L_t постоянно увеличивается. Так как нашей целью является условие L_t\rightarrow L^*, то события, уменьшающие примесь модели, являются необходимыми. Если модель характеризуется определённым уровнем примеси, обрезающее событие необходимо, чтобы идентифицировать подмножество N, которое рассматривается как некорректное и удалить его из модели, т.е. L_t=L_{t-1}-N.

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

Реализация

Краткосрочный трекер

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

Модель

Модель представлена множеством 15*15 нормированных по интенсивности патчей. Расстояние между патчами определено при помощи нормированной кросс-корреляции, т.е. distance(x_i,x_j)=1-NCC(x_i,x_j). Расстояние от измерения x_i до модели L_t определено как distance(x_i,L_t)=\min_{x \in L_t}(distance(x_i,x)). Модель основывается на патчах, чтобы построить эффективный и способный к обобщению детектор объекта.

Детектор объекта

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

Признаки

Наш детектор объекта основан на двухбитных бинарных шаблонах. Эти признаки измеряют ориентацию градиента внутри определённой зоны, квантуют её и выдают 4 возможных кода (рис. 2).


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Рис. 2: Двухбитные бинарные шаблоны - признаки, используемые в детекторе объекта.

Последовательный рандомизированный лес

Каждый патч описывается некоторым количеством бинарных шаблонов, положение, масштаб и сотношение между собой которых выбраны случайным образом. Эти признаки случайным образом разделены на несколько одинаковых по количеству групп. Каждая группа описывает различные измерения одного патча. Отклик патча на конкретную группу является дискретным вектором и называется ветка. Классификатор, используемый для распознавания, имеет форму рандомизированного леса. Он может обновляться во время работы. Возможно последовательное улучшение. Лес состоит из нескольких деревьев, каждое дерево построено для одной группы признаков. Каждый признак является измерением, взятым на определённом уровне дерева.

Уменьшение или увеличение леса – это последовательный процесс, в каждый момент времени обрабатывается только одно измерение. В начале каждое дерево содержит только одну ветку, определённую при помощи первого измерения. После каждого позитивного распознавания, определённого расширяющим событием, новый набор веток добавляется к лесу. Урезающее событие удаляет ветки, определённые как ложные.

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

Главное отличие рандомизированного леса от остальных реализаций – это то, что обучение производится только на положительных примерах. Если урезающее событие находит неверное положительное решение, то соответствующая ветка удаляется. Чтобы ещё больше поднять точность распознавания, алгоритм отфильтровывает распознавания, которые не похожи на модель(измеряется при помощи кросс-корреляции). Это делается только для самых перспективные патчей, так как большинство уже были отклонены рандомизированным лесом. Структура леса была подобрана эмпирически, чтобы достичь высокой способности к обобщению, учитывая необходимость работы в реальном времени. Алгоритм содержит 8 деревьев, каждое содержит 10 признаков, это соответствует 4^{10} возможных наблюдений объекта.

События

В математическом описании алгоритма не рассмотрены расширяющие и урезающие события, т.к. они могут быть различны для разных проблемных областей. Рассмотрим события, которые подойдут для большинства адаптивных трекеров, использующих сканирующие окна. Механизм этих событий основан на пороге сходства \Theta: два патча считаются похожими, если расстояние между ними меньше \Theta.

Расширяющие события

Расширяющие события состоят из выбора подходящих измерений из траектории с трекера и обновления модели. Существует три стратегии выбора измерений:

  • Модуль расстояния до первого патча (ABS). Выбирают все патчи x_t, похожие на первый x_0.
  • Разность между последовательными патчами (DIFF). Выбирается патч x_t, если он похож на патч x_{t-1}.
    Эта стратегия принимает медленные изменения внешнего вида.
  • Временной шаблон (LOOP). Эта стратегия сначала конвертирует траекторию в последовательность расстояний до модели, а затем ищет соответствующий шаблон в этой последовательности. Шаблон закрытого цикла определён следующим образом: начиная с первого патча похожего на модель, расстояние сначала превышает порог \Theta, а после некоторого количества кадров становиться похожей опять (рис. 3). В этом случае все кадры внутри шаблона используются для обновления модели. Эта стратегия использует свойство адаптивного трекера. Если трекер удаляется от объекта, то он приспосабливается к появлению фону, поэтому маловероятно, что он случайно вернётся к объекту. Если он вернулся, то это наводит на мысль, что изменялся внешний вид объекта или появлялись какие-то шумы на изображении. Эта стратегия позволяет принимать патчи с сильным изменением внешнего вида, но до сих пор описывающие объект.


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Рис. 3: Два варианта поведения трекера: объект потерян и текер приспособился к фону, объект менял внешний вид - трекер его успешно отследил.

Урезающие события

Эта часть вначале анализирует патчи предлагаемые расширяющими событиями, выявляя наиболее надёжные.

Вычислительный эксперимент

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


 
 
 
 
 
 
 
 
 
 
 
 
 
Рис. 4: Число неверных распознований быстро растёт со временем, если не используются урезающие события.

На рис. 5 показана модель, составленная временым шаблоном LOOP. Как видно объект сильно изменялся в процессе наблюдения, но модель всё равно составлена верно.


 
 
 
 
 
 
 
Рис. 5: Модель объекта составленная временным шаблоном LOOP.

На рис. 6 приведены примеры сопровождения объектов алгоритмом TMD и приведены графики точности распознования на том же видео ряде других алгоритмов. Как видно алгоритм TMD демонстрирует более высокую точность распознования.


Рис. 6: Как видно, алгоритм TMD демонстрирует более высокую точность распознования, чем AdaBoost или метод Лукаса-Канаде.

TLD (aka Predator) в действие.

Оригинальная статья разработчиков алгоритма: Z. Kalal, J. Matas, "Online learning of robust object detectors during unstable tracking"

Оффициальный сайт алгоритма TLD: http://info.ee.surrey.ac.uk/Personal/Z.Kalal/tld.html.

Git репозитарий авторов c кодом на Matlab: https://github.com/zk00006/OpenTLD.

Git репозитарий c кодом на С++(OpenCV): https://github.com/arthurv/OpenTLD.

Leave a Reply

You must be logged in to post a comment.