Object Tracking: SORT, DeepSORT, ByteTrack

Amazon Go магазины работают без кассиров - камеры отслеживают каждого покупателя и каждый товар одновременно. 100+ человек, 1000+ товаров, 30 FPS. Один ID switch - неправильный чек. Это не задача детекции: задача трекинга. SORT появился в 2016, ByteTrack в 2022 - и разрыв между ними в загроможденных сценах составляет 15% точности.

• Amazon Go: MOT с 300+ камерами для checkout-free shopping без единого кассира
• Tesla Autopilot: SORT-подобный трекинг в 8 камерах одновременно при 36 мс latency на кадр
• Waymo: трекинг пешеходов, велосипедистов, авто из 29 LiDAR + камера fusion на 40 000 ч/день данных
• Спортивная аналитика: ByteTrack для игроков на футбольном поле - статистика передвижений и тепловые карты

Предварительные знания

• Object detection: YOLO/DETR, bounding box, confidence score, IoU
• Венгерский алгоритм: оптимальное назначение по матрице стоимости за O(n³)
• Фильтр Калмана: предсказание и коррекция состояния по зашумлённым измерениям
• Cosine similarity и эмбеддинги признаков (для re-ID в DeepSORT)

• Object Detection: YOLO, SSD
• Video Understanding

SORT, DeepSORT, ByteTrack: эволюция tracking-by-detection

В 2016 году Alex Bewley с соавторами опубликовал SORT (Simple Online and Realtime Tracking) на ICIP. Работа доказала, что простая связка из фильтра Калмана и венгерского алгоритма по IoU даёт почти SOTA-качество трекинга на скорости в сотни кадров в секунду - без единой нейросети в самом трекере. Слабое место - перекрытия: после долгого occlusion SORT путал идентификаторы. В 2017 году Nicolai Wojke, Alex Bewley и Dietrich Paulus выпустили DeepSORT, добавив глубокий appearance-эмбеддинг (re-ID) и каскадный матчинг, что резко снизило число ID switch. В 2021 году Yifu Zhang с соавторами предложили ByteTrack (опубликован на ECCV 2022): ключевая идея - не выбрасывать низкодостоверные детекции, а на втором этапе ассоциировать их с потерянными треками. Это вернуло объекты, частично скрытые в толпе, и вывело ByteTrack в лидеры бенчмарков MOT17, MOT20 и DanceTrack при минимальной сложности.

SORT: трекинг за 20 строк кода

2016 год. Tesla Autopilot обрабатывал 8 камер одновременно при 36 мс на кадр. Детектор нашёл объекты. Вопрос: какой bbox кадра N соответствует bbox кадра N-1? Это задача трекинга. SORT (Simple Online and Realtime Tracking) решает её за 260 мкс на кадр - в 100 раз быстрее детектора.

**SORT = Kalman Filter + Hungarian Algorithm.** Kalman предсказывает позицию объекта в следующем кадре на основе текущей скорости. Hungarian Algorithm сопоставляет предсказанные позиции с детекциями текущего кадра по матрице IoU (Intersection over Union). Треки без совпадений за N кадров удаляются. Новые детекции без совпадений становятся новыми треками.

**Kalman State Vector.** SORT представляет каждый трек вектором состояния [x, y, s, r, dx, dy, ds], где x,y - центр bbox, s - площадь, r - aspect ratio, dx,dy,ds - скорости. Kalman предсказывает [x',y',s',r'] в следующем кадре. Это работает идеально для равномерного движения и даёт сбои при резких поворотах.

DeepSORT: re-ID эмбеддинги против ID switch

SORT теряет трек при перекрытии: объект A заслоняет объект B на 30 кадров, затем выходит - SORT выдаёт два новых ID вместо восстановления исходных. DeepSORT добавляет appearance embedding: компактный вектор (128 dim) описывает внешность объекта. Даже после длинного перекрытия re-ID матч восстанавливает трек.

**Каскадный матчинг.** DeepSORT использует двухэтапное сопоставление: сначала сопоставляет активные треки (time_since_update == 0) с детекциями через appearance + IoU, затем оставшиеся потерянные треки - только через IoU. Это важно: appearance модель менее надёжна для треков без недавних обновлений.

ByteTrack: используем все детекции, даже плохие

SORT и DeepSORT отбрасывают детекции с confidence < 0.5. В загроможденных сценах (стадион, перекрёсток) объект в толпе может давать confidence 0.3 - и трекер теряет его. ByteTrack (2022) переворачивает логику: сначала матчинг высокодостоверных детекций, затем попытка ассоциировать потерянные треки с низкодостоверными детекциями.

**ByteTrack HOTA метрика.** MOTA (традиционная) штрафует ID switch жёстко. HOTA (Higher Order Tracking Accuracy) балансирует detection accuracy и association accuracy. ByteTrack на DanceTrack (задача трекинга танцоров с перекрытиями): HOTA 47.7 против 45.7 у DeepSORT+ - без appearance модели. Причина:低confidence детекции содержат реальные объекты, которые DeepSORT полностью игнорирует.

Multi-Object Tracking: системные решения

Waymo ежедневно обрабатывает 40 000 часов сенсорных данных от роботакси. Трекинг пешеходов, велосипедистов, автомобилей - одновременно, при 10 FPS LiDAR + 30 FPS камера. На таком масштабе архитектурные решения важнее выбора алгоритма.

**Transformer-based tracking.** TrackFormer (2021) и MOTR объединяют детекцию и трекинг в один трансформер: track query - обучаемый вектор, который 'отслеживает' объект через кадры через cross-attention. Нет Kalman, нет Hungarian - всё заменяет attention. На MOT17: 74.1 MOTA у MOTR vs 76.5 у ByteTrack, но MOTR проще масштабируется на новые камеры без перебора гиперпараметров.

Ключевые идеи

• SORT: Kalman предсказывает позицию, Hungarian сопоставляет предсказания и детекции по IoU - 260 мкс/кадр
• DeepSORT: appearance embedding (128-dim re-ID) восстанавливает ID после длинных перекрытий
• ByteTrack: двухэтапный матчинг - сначала high-conf детекции, затем low-conf для потерянных треков
• Multi-class: отдельный трекер на класс - пешеход не может стать автомобилем
• HOTA метрика: балансирует detection accuracy и association accuracy лучше MOTA

Связанные темы

Трекинг строится на детекции и ведёт к системам понимания видео.

• Object Detection: YOLO, SSD — YOLO - стандартный источник bbox детекций для MOT пайплайна
• Video Understanding — Трекинг идентифицирует объекты; Video Understanding строит действия поверх треков
• Self-Supervised Vision — Re-ID embeddings DeepSORT обучаются через contrastive self-supervised learning

Вопросы для размышления

• SORT использует только IoU для матчинга. В каких сценариях это принципиально ломается даже при идеальном детекторе?
• ByteTrack не использует appearance features. Как это влияет на tradeoff между точностью и скоростью по сравнению с DeepSORT?
• MOTR и TrackFormer объединяют детекцию и трекинг в один transformer. Какие практические проблемы остаются нерешёнными?

Связанные уроки

• cv-14 — Video Understanding даёт детекцию по кадрам, на которой строится трекинг
• cv-06 — YOLO детектор - стандартный источник bbox для SORT и ByteTrack
• cv-16 — Re-ID эмбеддинги DeepSORT улучшаются через Self-Supervised обучение
• dsp-06 — Kalman фильтр в SORT - классический алгоритм теории ЦОС для сглаживания сигналов
• prob-04-bayes