Важно помнить, что универсального рецепта нет, поэтому творите, пробуйте что-то новое.
Виктор Петрович Баринов, шеф-повар ресторана «Claude Monet»

Привет, Хабр! С вами Матвей Шелухан и Тимур Мамедов из команды распознавания силуэтов в Tevian. Сегодня поговорим про метрики в задаче трекинга объектов, которая по праву считается одной из самых сложных в компьютерном зрении. Когда мы только приступали к её изучению, то принялись разбирать, какие есть датасеты, бейзлайны и метрики для оценки качества построенных траекторий. Будем честны: последнее было одним из самых сложных. Во-первых, метрик в рассматриваемой задаче довольно много, и ни одну из них не встретишь в стандартном курсе по машинному обучению. Во-вторых, в каждую из них порой сложно въехать, пока не придумаешь конкретные примеры (да, поэтому в этой статье будет много примеров). И, наконец, практически каждой посвящена отдельная научная статья, поэтому всю информацию приходилось собирать по крупицам. Кроме того, в процессе изучения литературы мы поняли, что универсальной метрики в данной задаче нет, поэтому для оценки качества алгоритмов необходимо смотреть на целый комплекс показателей. Данная статья будет полезна тем, кто занимается (либо просто интересуется) задачей трекинга и хочет понять, как устроены метрики оценки качества алгоритмов её решения. Как вы уже могли догадаться, мы за вас собрали всю нужную информацию в одну статью. Поехали!

Постановка задачи трекинга

Мы выпускники ВМК МГУ, поэтому немного формализма. Извините. Итак, прежде чем рассказывать о метриках, нужно понять, в чем вообще заключается сама задача трекинга. Если говорить верхнеуровнево, то она сводится к детекции множества объектов на кадрах видео с последующей ассоциацией этих детекций между соседними кадрами. Совсем «на пальцах»: для каждого объекта нужно понять его расположение на всех кадрах видео. Результатом работы алгоритма трекинга являются траектории движения (или, как говорят, треки) этих объектов.

Математически трек объекта

$IMAGE3$

можно записать как упорядоченный список

$IMAGE4$

состоящий из пар

$IMAGE5$

, где

$IMAGE6$

— координаты объекта, а

$IMAGE7$

— номер кадра, на котором были получены эти координаты. В нашем случае в качестве координат объектов выступают bounding box-ы или просто bbox-ы (прямоугольники, ограничивающие объект). Число

$IMAGE8$

обозначает количество кадров, на которых был найден объект. Кроме того, каждый трек характеризуется своим идентификатором

$IMAGE9$

.

Проблемы в задаче трекинга

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

Не ограничивая общности, в качестве отслеживаемых «объектов» будут выступать люди. Допустим, что человек на небольшое время зашел за какое-то препятствие (это может быть что угодно, даже другой человек) и тем самым пропал из зоны видимости камер. Такие ситуации принято называть окклюзиями (от англ. occlusion). По его возвращении нам бы хотелось сохранить его идентификатор, с чем большинство трекеров не всегда справляется. На словах может показаться, что это достаточно простая для решения задача. Однако практика показала, что люди двигаются достаточно хаотично и неравномерно. Не броуновское движение, но все же.

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

Кроме того, важным ограничением является качество работы модели детекции. Довольно часто бывает, что детектор на сложных доменах (например, камеры с низким разрешением, где объекты едва различимы) может выдавать некорректные bbox-ы, вследствие чего возникают ложные треки или неточная локализация объектов.

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

MOTA, MOTP и иже с ними

Одни из первых метрик в задаче трекинга появились почти 17 лет назад в статье Evaluating Multiple Object Tracking Performance: The CLEAR MOT Metrics. В ней авторы заложили фундамент, на котором впоследствии будут базироваться дальнейшие подходы к созданию новых мер оценки качества трекинга. Их подход к расчету метрик можно свести к трем этапам:

1. Нахождение оптимального соответствия между предсказанными и истинными треками на каждом кадре.

2. Подсчет ошибок оптимального соответствия на каждом кадре.

3. Агрегация полученных ошибок по всем кадрам.

Нахождение оптимального соответствия

Пусть у нас есть набор истинных треков

$IMAGE10$

и траекторий, предсказанных некоторой моделью

$IMAGE11$

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

Пусть на некотором кадре

$IMAGE12$

есть набор истинных bbox-ов

$IMAGE13$

с идентификаторами

$IMAGE14$

и набор предсказанных моделью трекинга bbox-ов

$IMAGE15$

с идентификаторами

$IMAGE16$

. Для нахождения оптимального соответствия авторы строят так называемую матрицу стоимостей сопоставления:

$IMAGE17$

каждый элемент которой

$IMAGE18$

показывает, насколько предсказанный bbox

$IMAGE19$

совпадает с истинным

$IMAGE20$

по IoU (Intersection over Union). Оптимальное соответствие достигается тогда, когда сумма

$IMAGE21$

$IMAGE22$

минимальна, где

$IMAGE23$

— бинарная величина, определяющая само соответствие (

$IMAGE24$

если истинный bbox

$IMAGE25$

сопоставился с предсказанным

$IMAGE26$

, иначе

$IMAGE27$

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

Подсчет ошибок

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

• Ошибка локализации для сопоставленных пар

$IMAGE28$

• Количество истинных bbox-ов, не сопоставленых ни с каким предсказанием

  $IMAGE29$

  ,

• Количество предсказанных bbox-ов, не сопоставленых ни с каким истинным

  $IMAGE30$

  ,

• Количество сопоставленных пар, для которых поменялся идентификатор предсказания

  $IMAGE31$

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

Как можно видеть, первые три типа ошибок возникают из-за неправильных предсказаний детектора, и только последняя ошибка относится к трекингу напрямую.

Агрегация ошибок

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

$IMAGE32$

где

$IMAGE33$

— количество истинных объектов на кадре

$IMAGE34$

,

$IMAGE35$

— количество сопоставленных пар на кадре

$IMAGE36$

.

На практике часто рассматривают только последние две метрики, MOTP и MOTA. MOTP (Multiple Object Tracking Precision) изменяется в пределах от

$IMAGE37$

до

$IMAGE38$

и показывает способность модели правильно локализовывать объекты и напрямую зависит от качества работы детектора. MOTA (Multiple Object Tracking Accuracy) выражает в том числе качество самой модели трекинга за счет вклада IDSW. Чем больше значение MOTA, тем лучше наша модель трекинга.

IDF1: усовершенствованный поиск оптимального соответствия

Как вы уже могли догадаться, главный недостаток MOTA и MOTP заключается в том, что они обе слишком сильно концентрируются на ошибках детектора и мало штрафуют за ошибки самого трекинга. Для того, чтобы избавиться от этого недостатка, в статье Performance Measures and a Data Set for Multi-Target, Multi-Camera Tracking была предложена метрика IDF1. Ее авторы меняют процедуру нахождения наилучшего соответствия между предсказанными и истинными треками. В отличие от предыдущих метрик, где соответствие вычислялось на каждом кадре по отдельности, при расчете IDF1 предлагается находить общее оптимальное соответствие сразу на всех кадрах видео.

Матрица стоимостей сопоставления между истинными

$IMAGE39$

и предсказанными

$IMAGE40$

треками записывается как:

$IMAGE41$

где в

$IMAGE42$

учитываются случаи, когда предсказанная детекция либо не сопоставилась ни с каким истинным bbox-ом по порогу

$IMAGE43$

на IoU, либо сопоставилась с другим объектом

$IMAGE44$

; в

$IMAGE45$

же учитываются случаи, когда истинный bbox не сопоставился ни с какой детекцией по порогу

$IMAGE46$

на IoU, либо сопоставился с детекцией с другим идентификатором

$IMAGE47$

. В обоих случаях суммирование происходит по всей предыстории пар треков.

$IMAGE48$

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

$IMAGE49$

и

$IMAGE50$

для данной пары треков в результате их сопоставления.

В таком случае

$IMAGE51$

(так как серая траектория вначале три раза неверно сопоставилась с оранжевым истинным треком и в конце три раза неверно сопоставилась с зеленым истинным треком) и

$IMAGE52$

(так как синий трек вначале три раза неверно сопоставился с черной предсказанной траекторией и в конце три раза неверно сопоставился с желтым предсказанным треком). В сумме получаем

$IMAGE53$

.

Аналогичным образом заполняется оставшаяся часть матрицы. Затем по полученной матрице стоимостей вычисляется оптимальное соответствие при помощи того же Венгерского алгоритма. Домашнее задание: рассчитайте матрицу сопоставления целиком и покажите, что оптимальное соответствие достигается при сопоставлении серого трека с синим, желтого — с зеленым и черного — с оранжевым.

По найденным соответствиям считается метрика IDF1:

$IMAGE54$

где

$IMAGE55$

— это количество верно сопоставленных пар по порогу

$IMAGE56$

, согласно найденному оптимальному сопоставлению (в примере на предыдущей картинке для синего и серого треков

$IMAGE57$

), а

$IMAGE58$

и

$IMAGE59$

— такие же, как и в матрице стоимостей. Отметим, что значение IDF1 варьируется от

$IMAGE60$

до

$IMAGE61$

и для идеальной модели трекинга

$IMAGE62$

.

HOTA: текущий эталон метрик трекинга

В настоящее время метрика HOTA, представленная в статье HOTA: A Higher Order Metric for Evaluating Multi-Object Tracking, является одной из основных в задаче трекинга. К слову, статья написана прекрасно и очень подробно объясняет предложенный подход к оценке качества алгоритмов и основные проблемы предшественников, так что особенно советуем к прочтению. Здесь же мы просто скажем, что главное достоинство HOTA по сравнению с IDF1 и MOTA/MOTP в том, что она обеспечивает сбалансированную и всестороннюю оценку всех аспектов трекинга (детекция, ассоциация и локализация) в рамках единой согласованной меры качества.

Оптимальное соответствие между предсказанными и истинными треками, аналогично метрикам MOTA и MOTP, авторы ищут на каждом отдельном кадре. Однако, в отличие от них, в HOTA вводится целый набор матриц стоимостей для разных порогов по IoU. Но прежде чем выписать эти матрицы, необходимо ввести несколько понятий.

Пусть на кадре

$IMAGE63$

некоторый bbox

$IMAGE64$

истинного трека хорошо пересекается с детекцией предсказанного трека

$IMAGE65$

(

$IMAGE66$

). Тогда будем считать эту пару за true positive (

$IMAGE67$

) при заданном пороге

$IMAGE68$

на текущем кадре

$IMAGE69$

и вместе с тем введем три множества объектов для заданной пары:

$IMAGE70$

где

$IMAGE71$

и

$IMAGE72$

- функции, возвращающие идентификатор предсказанного и истинного трека соответственно. Множество TPA (True Positive Associations) состоит из TP пар на всех кадрах видео, для которых идентификаторы истинного и предсказанного трека совпадают. Множество FNA (False Negative Associations) состоит из bbox-ов истинных треков с тем же идентификатором, что и у bbox-а

$IMAGE73$

, но для которых либо сопоставленная с ней детекция имеет отличный от

$IMAGE74$

идентификатор, либо сопоставления вовсе не нашлось (т.е. пары не прошли по порогу

$IMAGE75$

на IoU). Множество FPA (False Positive Associations) состоит из bbox-ов предсказанных треков с тем же идентификатором, что и у

$IMAGE76$

, но для которых либо сопоставленный с ним истинный bbox имеет отличный от

$IMAGE77$

идентификатор, либо сопоставления вовсе не нашлось (т.е. пары не прошли по порогу

$IMAGE78$

на IoU).

Если вы слабо поняли, что произошло выше, то ничего страшного. Разберем все это дело на следующем примере:

$IMAGE79$

На картинке сверху имеются два истинных трека (синий и голубой) и две предсказанные траектории (черная и серая) в разные моменты времени. Пусть пара синего истинного объекта и черного предсказания (выделена красной рамкой) прошла по порогу по IoU. Тогда эта пара считается

$IMAGE80$

и для нее

$IMAGE81$

(зеленые рамки),

$IMAGE82$

(коричневые рамки),

$IMAGE83$

(желтые рамки). На этом моменте попробуйте вернуться к формулам и текстовым пояснениям выше и понять, почему именно выделенные рамки являются TPA, FNA и FPA.

Введенные понятия позволяют определить величину

$IMAGE84$

, которая в дальнейшем будет использована для расчета оптимального соответствия:

$IMAGE85$

$IMAGE86$

показывает, насколько большой является мощность множества TPA по сравнению с FPA и FNA. В случае идеальной модели трекинга

$IMAGE87$

. Подчеркнем, что в результате мы получили не одно, а сразу несколько значений

$IMAGE88$

для разных порогов

$IMAGE89$

на IoU. Набор матриц стоимостей конструируется из

$IMAGE90$

следующим образом:

$IMAGE91$

где

$IMAGE92$

- заданная константа для выравнивания вкладов

$IMAGE93$

и IoU. Оптимальное соответствие достигается за счет одновременной максимизации качества ассоциации

$IMAGE94$

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

$IMAGE95$

на IoU, что будет приводить к разным сопоставлениям. Тем самым авторы косвенно учитывают качество локализации при поиске оптимального сопоставления. Стандартная реализация HOTA вычисляет матрицы стоимостей для порогов

$IMAGE96$

от

$IMAGE97$

до

$IMAGE98$

с шагом

$IMAGE99$

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

Для расчета метрики для сопоставления с порогом

$IMAGE100$

применяется следующая формула:

$IMAGE101$

Введенные выше

$IMAGE102$

усредняются согласно заранее выбранному набору порогов для расчета финальной метрики HOTA:

$IMAGE103$

Значение HOTA варьируется от

$IMAGE104$

до

$IMAGE105$

и для идеальной модели трекинга

$IMAGE106$

.

Можно показать, что рассматриваемая метрика содержит в себе три величины: качество ассоциации (Association Accuracy), качество детекции (Detection Accuracy) и качество локализации (Localization Accuracy):

$IMAGE107$

Также отметим, что

$IMAGE108$

можно выразить через

$IMAGE109$

и

$IMAGE110$

следующим образом:

$IMAGE111$

$IMAGE112$

Заключение

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