Deep SORT

Deep SORT — это алгоритм многократного отслеживания объектов (Multi-Object Tracking, MOT), основанный на комбинации методов оценки состояния (фильтр Калмана) и метрик внешнего вида, извлекаемых с помощью свёрточной нейронной сети. Алгоритм является расширением базового метода SORT (Simple Online and Realtime Tracking) и предназначен для повышения устойчивости к перекрытиям объектов и кратковременным потерям трека за счёт использования дескрипторов внешнего вида. Deep SORT широко применяется в системах компьютерного зрения, в частности, в задачах видеонаблюдения, автономного вождения и анализа поведения.

История

Метод SORT был предложен в 2016 году группой исследователей (Alex Bewley и др.) как простой и быстрый алгоритм для онлайн-отслеживания множества объектов. Основу SORT составляли фильтр Калмана для предсказания положения объекта и венгерский алгоритм для решения задачи сопоставления (data association). Недостатком SORT была низкая устойчивость к идентификационным переключениям (ID switches) при перекрытиях объектов, так как алгоритм полагался исключительно на метрики движения (пересечение по объединению — IoU).

В 2017 году та же исследовательская группа (Nicolai Wojke, Alex Bewley, Dietrich Paulus) представила улучшенную версию — Deep SORT. Основным нововведением стало использование глубоких нейронных сетей для извлечения признаков внешнего вида (appearance features) объектов. Это позволило сопоставлять треки не только по движению, но и по визуальному сходству, что значительно сократило количество ошибок при повторном появлении объекта в кадре после окклюзии.

Принцип работы

Deep SORT решает задачу многократного отслеживания в два основных этапа: оценка состояния и сопоставление треков с обнаружениями.

Оценка состояния (State Estimation)

Каждый отслеживаемый объект представляется в виде состояния, описывающего его положение и скорость в пространстве изображения. Deep SORT использует стандартную модель фильтра Калмана с постоянной скоростью (constant velocity model). Вектор состояния включает 8 параметров: координаты центра ограничивающей рамки (u, v), её высоту (h), соотношение сторон (r, обычно принимается постоянным), а также их производные по времени (скорости). Фильтр Калмана предсказывает положение объекта на следующем кадре и обновляет оценку на основе новых измерений (обнаружений).

Извлечение признаков внешнего вида (Appearance Feature Extraction)

Ключевое отличие Deep SORT от SORT — использование глубокой свёрточной нейронной сети для получения дескриптора внешнего вида каждого обнаруженного объекта. Сеть, как правило, представляет собой предобученную архитектуру (например, Wide ResNet), которая принимает на вход изображение объекта (ограничивающую рамку) и выдаёт нормализованный вектор признаков фиксированной размерности (например, 128 или 512). Этот дескриптор кодирует визуальные характеристики объекта (цвет, текстуру, форму) и используется для вычисления косинусного расстояния (cosine similarity) между треками и новыми обнаружениями.

Сопоставление (Data Association)

Deep SORT комбинирует две метрики для решения задачи сопоставления:

1. Метрика движения (Motion Metric): Махаланобиса расстояние между предсказанным положением трека (по фильтру Калмана) и новым обнаружением. Эта метрика учитывает неопределённость предсказания и отсеивает невероятные сопоставления (например, слишком далёкие объекты).
2. Метрика внешнего вида (Appearance Metric): Косинусное расстояние между вектором признаков трека (хранящимся в галерее последних дескрипторов) и вектором признаков нового обнаружения. Эта метрика позволяет сопоставлять объекты, даже если их траектории движения временно расходятся.

Итоговая метрика сопоставления представляет собой взвешенную сумму двух расстояний. Для решения задачи назначения используется венгерский алгоритм (или алгоритм Кана — Манкреса), который находит оптимальное соответствие между треками и обнаружениями, минимизируя суммарное расстояние.

Управление треками (Track Management)

Deep SORT управляет жизненным циклом треков с помощью трёх состояний:

• Подтверждённый трек (Confirmed Track): Объект, который был последовательно обнаружен на нескольких кадрах (обычно ≥ 3). Для таких треков выполняется полное сопоставление.
• Неопределённый трек (Unconfirmed Track): Объект, обнаруженный на одном-двух кадрах. Для них сопоставление может быть ограничено или выполняться только по метрике движения.
• Потерянный трек (Lost Track): Трек, для которого не было найдено соответствие на текущем кадре. Он сохраняется в течение определённого числа кадров (параметр n_init), и если объект не появляется вновь, трек удаляется. Если же объект появляется снова и успешно сопоставляется (например, по внешнему виду), трек восстанавливается.

Ключевые особенности

• Онлайн-режим: Алгоритм обрабатывает кадры последовательно, не требуя доступа к будущим кадрам, что делает его пригодным для реального времени.
• Устойчивость к окклюзиям: Благодаря метрике внешнего вида, Deep SORT значительно лучше справляется с перекрытиями объектов, чем SORT, и реже меняет идентификаторы (ID switches).
• Модульность: Алгоритм не привязан к конкретному детектору объектов. Он может работать с любым детектором, выдающим ограничивающие рамки (например, YOLO, Faster R-CNN, SSD).
• Простота реализации: Несмотря на использование нейронных сетей, базовая архитектура Deep SORT остаётся относительно простой для понимания и реализации.

Применение

Deep SORT нашёл широкое применение в различных областях компьютерного зрения:

• Видеонаблюдение: Отслеживание людей и транспортных средств в системах безопасности, подсчёт посетителей, анализ потоков.
• Автономное вождение: Отслеживание пешеходов, велосипедистов и других автомобилей для прогнозирования их траекторий и принятия решений.
• Спортивная аналитика: Отслеживание игроков и мяча для анализа тактики и статистики.
• Робототехника: Навигация мобильных роботов и взаимодействие с динамическими объектами.
• Биология и медицина: Отслеживание движения клеток или микроорганизмов в микроскопии.

Критика и ограничения

• Зависимость от детектора: Качество отслеживания напрямую зависит от качества детектора объектов. Пропуски или ложные обнаружения приводят к ошибкам трекинга.
• Параметры настройки: Алгоритм имеет несколько гиперпараметров (веса метрик, пороги сопоставления, время жизни потерянного трека), которые требуют ручной настройки для каждой конкретной сцены.
• Вычислительные затраты: Извлечение признаков внешнего вида с помощью нейронной сети требует дополнительных вычислительных ресурсов, что может быть критично для встраиваемых систем.
• Проблема повторной идентификации: Несмотря на улучшения, Deep SORT может ошибаться при повторном появлении объекта после длительной окклюзии, особенно если объекты внешне похожи (например, люди в одинаковой одежде).
• Отсутствие модели взаимодействия: Алгоритм не учитывает возможные взаимодействия между объектами (например, обгон, остановка), что может приводить к неоптимальным траекториям.

Источники

• Wojke, N., Bewley, A., & Paulus, D. (2017). Simple online and realtime tracking with a deep association metric. In 2017 IEEE International Conference on Image Processing (ICIP) (pp. 3645–3649). IEEE.
• Bewley, A., Ge, Z., Ott, L., Ramos, F., & Upcroft, B. (2016). Simple online and realtime tracking. In 2016 IEEE International Conference on Image Processing (ICIP) (pp. 3464–3468). IEEE.
• Kalman, R. E. (1960). A new approach to linear filtering and prediction problems. Journal of Basic Engineering, 82(1), 35–45.
• Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2), 83–97.