спецкурс

Зачем нужны
алгоритмы?

Сегодня мы возьмём две задачи, которые выглядят как чистая теория графов — паросочетание минимального веса и поток минимальной стоимости, — и заставим их следить за людьми на видео. Ни одной строчки не написано заранее: всё, что вы увидите, считается прямо в этой вкладке.

? — помощь · → — дальше
01 · задача

Детектор у нас уже есть

Настоящее видео с камеры наблюдения. По нему прогнали настоящий детектор — YOLOv8s, класс «человек»: 795 кадров, 4717 рамок. Нейросеть отработала прекрасно. Ответьте на простой вопрос: сколько всего человек прошло через кадр?

выход детектора · YOLOv8s

пульт

табло

рамок в кадре0
человек прошло?
Детектор отвечает на вопрос «где», но не отвечает на вопрос «кто». Каждый кадр он начинает жизнь заново. Цвета мигают не для красоты: так выглядит мир, в котором нет понятия «тот же самый человек». Посчитать людей по такому выходу невозможно.
01 · задача

Что именно надо сделать

Парадигма называется tracking-by-detection. Детектор — не наша забота, он уже есть. Наша забота — то, что между кадрами.

дано
для каждого кадра t — множество рамок Dt

найти
разбиение всех рамок на траектории:
каждой рамке — номер объекта, один объект —
не больше одной рамки в кадре
Обратите внимание, что здесь уже нет ни пикселей, ни свёрток, ни нейросетей. Есть множества и связи между ними. Значит, дальше работают не глаза, а алгоритмы.

ЧЕМ МЕРЯЮТ КАЧЕСТВО

метрикачто считает
MOTAпропуски + ложные + перепутывания
IDSWсколько раз объект сменил номер
MOTPточность рамок
MT / MLдоля треков, пройденных до конца
FMсколько раз трек рвался
Сегодня нас интересует одна строка — IDSW. Она про личность объекта, а не про его координаты. И именно она отделяет хороший алгоритм от плохого при одном и том же детекторе.
ключевое наблюдение
детектор один и тот же —
разница только в алгоритме сшивки
02 · паросочетание

Решение, которое придумывает каждый

«Свяжем каждый трек с ближайшей рамкой». Берём самую дешёвую пару, потом следующую, и так далее — жадный алгоритм. Работает. Ровно до первой встречи двух людей.

синтетика · истина известна

кто сшивает

перепутываний ID за прогон

жадный0
оптимальный0
сейчас0
Куртка — настоящая личность, рамка — мнение трекера. Пока цвет рамки совпадает с курткой, стоит метка «✓»; после подмены рамка сидит на чужой куртке — «СБОЙ ID». Оба алгоритма видят одни и те же безликие рамки детектора. Красные метки на плёнке — кадры, где сломалось. В сцене «двое навстречу» жадная подмена не исправляется: рамки доезжают до края кадра на чужих куртках.
02 · паросочетание

Где именно живёт задача

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

кадр · выбранные пары
сумма · жадный0
сумма · оптимум0
переплата0
спорных кадров0
Жадный хватает глобально самую дешёвую клетку — и тем самым отнимает рамку у трека, которому она была нужнее. Тот берёт что осталось. Тонкой рамкой отмечено, что выбрал бы второй алгоритм.
И вот главное. Спорных кадров — единицы на сотню: почти всегда жадный прав. Но одного такого кадра хватает, чтобы два человека обменялись номерами навсегда: дальше видео поедет с перепутанными личностями. Вот почему «почти всегда правильно» — это не про алгоритмы.
02 · паросочетание

Задача о паросочетании
минимального веса

дано
двудольный граф: слева треки T, справа рамки D
вес ребра c(i, j) — «насколько неправдоподобно,
что рамка j — это трек i»

найти
паросочетание минимального суммарного веса

Это классическая задача о назначениях. Ей полтора века, у неё есть точный алгоритм — венгерский, — и он работает за O(n³).

Разбирать его мы сегодня не будем, и это принципиально. Работа исследователя — увидеть, что перед ним задача о назначениях. Дальше можно взять готовое: scipy.optimize.linear_sum_assignment. Одна строчка.
почему не перебор
n = 10 → 3 628 800 вариантов
n = 20 → 2 432 902 008 176 640 000
n = 20, венгерский → 8 000 операций

Вот и весь ответ на вопрос из заголовка лекции. Задача не изменилась — изменилось только то, как мы её решаем. Перебор честен, но столько времени нет ни у кого.

Дальше — самое интересное. Задачу мы поставили, но что писать в матрицу, никто не сказал. Именно здесь и живёт разница между статьями.
03 · SORT

Что писать в матрицу, часть 1: движение

Человек зашёл за столб — рамок нет. Просто подождать его? Попробуйте: поднимите «терпение» и выключите предсказание.

синтетика · столб посреди кадра

фильтр Калмана

табло

перепутываний0
выдано номеров2идеал — 2
Терпение без предсказания не спасает: трек ждёт у левого края столба, а человек выходит справа. Пунктирный эллипс — то, как быстро Калман теряет уверенность. Это и есть SORT: Калман + венгерский, больше ничего.
03 · SORT

SORT целиком

весь алгоритм
1. Калман предсказывает, где трек будет
2. c(i, j) = 1 − IoU(предсказаниеi, рамкаj)
3. венгерский алгоритм по матрице c
4. пары дороже порога — разорвать
5. рамки без пары → новые треки
6. треки без рамок дольше Amax → удалить

Всё. Ни одной обучаемой детали. Двести строк на Python.

Авторы честно пишут в аннотации: это рудиментарная комбинация знакомых приёмов — фильтра Калмана и венгерского алгоритма. И заодно — что 260 Гц, в двадцать с лишним раз быстрее конкурентов того времени.

MOT16, ОДНИ И ТЕ ЖЕ ДЕТЕКЦИИ

методрежимMOTA ↑IDSW ↓Гц ↑
SORTонлайн59.8142360
Deep SORTонлайн61.478140
POIонлайн66.180510
EAMTTонлайн52.591012
LMPофлайн71.04340.5
NOMTwSDP16офлайн62.24063
MCMOT HDMофлайн62.4139435
таблица 2 из статьи [2]
Смотрите на два последних столбца. Офлайн-методы уверенно выигрывают по IDSW — и так же уверенно проигрывают по скорости. Запомните это: мы к этому вернёмся.
04 · Deep SORT

Что писать в матрицу, часть 2: внешность

Синий зашёл за столб и там притормозил. Калман об этом не знает и продолжает вести его вправо. А из-за столба выходит совсем другой человек — и оказывается ровно там, где Калман ждал синего. Геометрия уверенно указывает на самозванца.

синтетика · предсказание уводит не туда

c = λ · геометрия + (1−λ) · внешность

0 — только внешность

перепутываний · λ (8 случайных сцен)

сейчас0
График строится сейчас, при вас. Внешность у нас — цвет куртки; у Deep SORT — 128-мерный вектор со свёрточной сети. Арифметика одна и та же: косинусное расстояние.
04 · Deep SORT

Deep SORT: та же задача,
другая матрица

Изменилось только содержимое клеток. Двудольный граф тот же, венгерский алгоритм тот же, строчка linear_sum_assignment та же.

было (SORT)
c(i, j) = 1 − IoU

стало (Deep SORT)
c(i, j) = λ · dМахаланобиса + (1 − λ) · dкосинусное
плюс: пару отбрасываем, если любая из двух метрик
считает её невозможной
Плюс «каскад»: сначала сшиваем треки, которых видели недавно, и только потом — давно потерянных. Иначе давно потерянный трек с огромным эллипсом неуверенности перехватывает чужие рамки: чем хуже он знает, где объект, тем ближе ему кажется всё вокруг. Сейчас увидим это вживую.
IDSW · SORT1423
IDSW · Deep SORT781
это−45%
MOT16, одни и те же детекции · статья [2]

И отдельная деталь, ради которой стоит читать статьи целиком. Авторы сообщают, что при заметном движении камеры разумным выбором оказалось λ = 0 — то есть в стоимости остаётся только внешность, а от геометрии остаётся лишь право вето.

Полминуты назад вы видели, как ползунок λ приехал ровно туда же. Это не совпадение: когда движение непредсказуемо, предсказание движения — не помощь, а источник уверенных ошибок.
04 · Deep SORT

Каскад: кто сшивается первым

Голубой надолго скрылся за опорой — его эллипс неуверенности растёт, и чем он больше, тем «ближе» потерянному треку кажется всё вокруг. Жёлтый просто стоит рядом. Досмотрите до конца: потерянный трек дотянется до чужой рамки — и украдёт её.

синтетика · потерянный трек ворует рамку

порядок сшивки

табло

перепутываний0
выдано номеров2идеал — 2
Каскад: сначала сшиваются треки, видевшие свою детекцию только что, потом — потерянные кадр назад, и так далее. Свежий трек забирает свою рамку первым, и украсть её потерянный уже не может. Это не новый алгоритм — это очередь из тех же венгерских задач, от свежих треков к старым.
05 · поток

Всё, что было до сих пор, решало задачу
по одному кадру за раз.

А зачем?

Видео уже записано. Оно целиком лежит на диске. Мы имеем полное право посмотреть, что будет дальше, — и только потом решить, кто есть кто в текущем кадре. Это меняет не решение. Это меняет задачу.

05 · поток

Задача о потоке
минимальной стоимости

Строим один граф на всё видео сразу.

вершины
каждая детекция расщеплена надвое: вход → выход
ребро между ними имеет пропускную способность 1
— один объект не пройдёт через рамку дважды

рёбра
выход(a) → вход(b), если b в следующих кадрах и близко
стоимость = расстояние

исток и сток
S → вход(любой): цена «здесь трек начался»
выход(любой) → T: цена «здесь трек кончился»
фокус
стоимость ребра вход→выход отрицательна
— это награда за объяснённую детекцию

Тогда единица потока из S в T — это ровно одна траектория: цепочка детекций от рождения до смерти. Пропускная способность 1 гарантирует, что треки не поделят рамку между собой.

Пустить k единиц потока минимальной стоимости = найти k траекторий, объясняющих видео как можно лучше. В статье [3] это называется k кратчайших путей. Дальше берём готовый алгоритм — и всё.
и лучшее
когда очередной путь стоит дороже нуля —
новый трек уже не окупает своё рождение.
k не надо задавать. Алгоритм найдёт его сам.
05 · поток

Плёнка становится осью времени

Разворачиваем видео в график: по горизонтали — кадры, по вертикали — где объект был в кадре. Точки — детекции. Траектория превращается в линию, а поиск треков — в протягивание k путей слева направо.

пространство × время · 4 человека, 60 кадров

сколько путей тянуть

табло

треков0
стоимость0
Цены путей растут — каждый следующий трек объясняет всё более сомнительные точки. Как только цена перевалит за ноль, тянуть дальше незачем. Отсюда и «пусть решит сам».
05 · поток

То же самое на настоящем видео

Те же 4717 рамок из первого слайда. Всё видео развёрнуто в пространство и время: по горизонтали — кадры, по вертикали — где человек был в кадре.

4717 детекций · 795 кадров целиком

чем сшивать

что произошло

Онлайн видит только прошлое — его линии рвутся там, где детектор моргнул, и каждый обрыв стоит нового номера. Поток видит всё видео сразу и протягивает линии сквозь дыры. Цена — та самая колонка «Гц» из таблицы.
05 · поток

Вернёмся к вопросу

Те же кадры, тот же детектор, что двадцать минут назад. Изменилось одно: поверх рамок поработали алгоритмы. Теперь на вопрос «сколько человек прошло» есть ответ.

то же видео · теперь с номерами

что показываем

человек прошло

…
Номера больше не мигают: они держатся на человеке, пока он идёт через кадр. Ровно этого нам и не хватало на первом слайде — и ровно это дали две задачи из учебника по алгоритмам.
05 · поток

Где ломается и это

Было бы нечестно закончить на том, что поток всё решает. У него есть врождённый изъян, и он виден прямо из формулировки.

стоимость перехода
c(a → b) = расстояние(a, b)

чего здесь нет
скорости

Стоимость ребра зависит только от двух соседних детекций. Граф не помнит, откуда объект пришёл. Если двое встретятся в одной точке, поток с равным удовольствием протянет линии насквозь или развернёт их обратно — для него это одна и та же цена.

На лекции это можно проверить: верните ползунок «расхождение» на слайде 4 в ноль. Там ломались все.

ЧЕМ ЛЕЧАТ

  • Внешность в стоимость ребра. Ровно как в Deep SORT: разные куртки — дорогое ребро. Ползунок λ, только теперь в графе.
  • Скорость в вершину. Вершина — не «детекция», а «детекция + откуда пришёл». Граф раздувается, зато помнит инерцию.
  • Сетка вместо детекций. Именно так сделано в [3]: вершины — это клетки пола × кадры, а не рамки. Тогда «два объекта в одной клетке» просто запрещено пропускной способностью.
Заметьте: ни одно из трёх лечений не меняет алгоритм. Меняется только граф. Алгоритм остаётся тем же самым потоком минимальной стоимости, который придумали задолго до всякого компьютерного зрения.
итог

Одна задача, три формулировки

SORTDeep SORTk-поток
задачапаросочет.паросочет.поток
область1 кадр1 кадрвсё видео
алгоритмвенгерскийвенгерскийk кратч. путей
что меняли—клетки матрицыграф
онлайндаданет
IDSW1423781меньше
Ни одна из трёх работ не изобрела алгоритм. Венгерскому алгоритму — 70 лет, потокам — 70 лет. Изобрели другое: как перевести видео на язык, где эти алгоритмы уже есть.

Так зачем нужны алгоритмы?

Не чтобы их писать. Готовый венгерский лежит в scipy, готовый min-cost flow — в networkx и OR-Tools. Написать их вы, скорее всего, не будете никогда.

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

Между этими двумя нет разницы в уме. Есть разница в словаре.
что почитать
[1] Bewley et al. Simple Online and Realtime Tracking · arXiv:1602.00763
[2] Wojke et al. SORT with a Deep Association Metric · arXiv:1703.07402
[3] Berclaz et al. MOT Using K-Shortest Paths Optimization · TPAMI 2011
видео: PETS 2009, сцена S2L1 (samples/data/vtest.avi из репозитория OpenCV)
детекции: YOLOv8s, класс «person», порог 0.35 — прогнаны по этим же кадрам
синтетические сцены, венгерский алгоритм, фильтр Калмана и поток — написаны для этой лекции

Управление

→ пробелследующий слайд
←предыдущий
Home Endв начало / в конец
Fполный экран
Tтаймер: пауза / пуск
Rсбросить таймер
?эта справка

Всё считается вживую. Ползунки можно крутить при аудитории — ничего не сломается, все результаты настоящие.