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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

каждый элемент которой показывает, насколько предсказанный bbox совпадает с истинным по IoU (Intersection over Union). Оптимальное соответствие достигается тогда, когда сумма

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

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

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

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

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

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

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

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

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

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

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

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

Пример расчета MOTA

Пусть имеется видео с одним истинным треком gt, представленным на всех 100 кадрах видео. Первая модель (A) предсказала траекторию на первых 50 кадрах видео, а затем не смогла найти его. Вторая модель (B) предсказала трек на первых 70 кадрах, но ошибочно поменяла идентификатор предсказания (произошел разрыв траектории). Третья модель (C) смогла полностью найти трек, но трижды ошиблась и поменяла идентификатор предсказания. В таком случае MOTA для трех моделей рассчитывается как:

Из этого примера видно, что MOTA, хоть и учитывает ошибки трекинга через величину IDSW, но все равно в большей степени концентрируется на ошибках детекции благодаря большему вкладу FN и FP.

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

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

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

где в учитываются случаи, когда предсказанная детекция либо не сопоставилась ни с каким истинным bbox-ом по порогу на IoU, либо сопоставилась с другим объектом ; в же учитываются случаи, когда истинный bbox не сопоставился ни с какой детекцией по порогу на IoU, либо сопоставился с детекцией с другим идентификатором . В обоих случаях суммирование происходит по всей предыстории пар треков.

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

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

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

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

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

Пример расчета IDF1

Расчет метрики IDF1 на том же примере, что и для MOTA:

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

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

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

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

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

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

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

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

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

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

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

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

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

Для расчета метрики для сопоставления с порогом применяется следующая формула:

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

Значение HOTA варьируется от до и для идеальной модели трекинга .

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

Также отметим, что можно выразить через и следующим образом:

Пример расчета HOTA

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

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

Заключение

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