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

  • Подсчёт уникальных людей, зашедших в определённую зону или перешедших через границу в кадре
  • Определение типичных маршрутов машин на стоянке и людей в магазине
  • Автоматический поворот камеры видеонаблюдения при смещении объекта

Даже не глядя в литературу, я могу с уверенностью сказать, что наилучший способ решить поставленную задачу — использовать нейронные сети. В общем-то, дальше можно было бы ничего и не писать, но не всегда в задачу можно кинуться парой GTX 1080Ti. Кому интересно, как отслеживают объекты на видео в таких случаях, прошу под кат. Я попробую не просто объяснить, как работают ASEF и MOSSE трекеры, а подвести вас к решению, чтобы формулы показались очевидными.

Для начала ответим на предварительный вопрос: зачем что-то изобретать, когда можно скормить tensorflow пачку видео и отойти от компьютера на пару недель? У нейросетевых подходов есть один серьёзный недостаток: даже на современных видеокартах сложно добиться от сетей хорошей скорострельности. Это не проблема, если мы анализируем записанное видео, но вставляет палку в колёса, если хочется работать в реальном времени. Допустим, мы хотим обрабатывать видео с пяти камер в 10 FPS. Даже с такими сравнительно мягкими условиями нейронная сеть должна иметь inference time меньше чем $\frac{1000}{5 \times 10} = 20$ миллисекнуд (в условиях полной непараллельности). Для сравнения, YoloV3, сеть-классификатор со сравнительно простой архитектурой, может выплёвывать по картинке в $50$ миллисекунд. Кроме того, решения на базе мощных видеокарт могут быть банально дороги.

Эта статья предполагает, что вы уже имели дело с машинной обработкой изображений, знакомы с базовыми операциями линейной алгебры (свёртка, норма, обращение матриц) и в общих чертах понимаете преобразование Фурье.

Здесь и далее:

  • $A \odot B$ обозначает поэлементное умножение матриц $A$ и $B$
  • $A \otimes B$ обозначает свёртку матриц $A$ и $B$
  • $\hat{A}(\omega, \nu) = \mathcal{F}(A(x, y))$ обозначает что $\hat{A}(\omega, \nu)$ — матрица частот быстрого преобразования Фурье, применённого к изображению $A$.
  • $\parallel A\parallel_2$ — обозначает сумму квадратов элементов матрицы $A$

Тривиальное решение


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

Пусть у нас есть $T$ последовательных кадров видео $I_t$ размера $w$ на $h$ пикселей. На начальном кадре видео $I_0$ вокруг некоторого объекта обведён прямоугольник $F_0$ $m$ на $n$. Требуется найти местоположение этого тела на всех остальных кадрах $I_t$.

Уберём шум на изображениях, затем нормируем каждое из них в диапазон от -1 до 1, чтобы общие изменения яркости не влияли на детекции. Возьмём первый кадр видео без разметки $I_1$. Если $I_0$ и $I_1$ — соседние кадры видео с хорошим FPS, то вряд ли искомый объект далеко удалился от исходного положения. Воспользуемся этим. Вырежем из $I_1$ прямоугольник $F_1$ с места, где раньше находилось искомое тело. «Протащим» $F_0$ сквозь $F_1$ и в каждой точке посчитаем квадрат суммы разностей

$G_{L_2}(i,j) = \parallel F_{1}(i, j) - F_0 \parallel_{2}, i \in [0, m], j \in [0, n]$

где для вычисления разности в $G_{L_2}(i,j)$ нужно совместить центр $F_0$ с элементом $(i, j)$ в $F_1$, а отсутствующие значения занулить. После этого в матрице $G_{L2}$ ищется минимум; его местоположение минус координаты центра $F_1$ и будет смещением искомого объекта на $I_1$.

Чтобы резкий переход в ноль не «звенел» при детекции, лучше изначально взять прямоугольник чуть больше, чем надо и плавно сводить к нулю значения ближе к границам $F_0$ и $F_1$. Для этого каждый из $F$ нужно умножить на маску. В случае квадратных объектов подойдёт старая добрая экспонента $A = \exp{\frac{(x - i)^2 + (y - j)^2}{\sigma^2}}$ (где $(x, y)$ — центр окна), но в общем случае лучше взять двумерное окно Хеннинга.

Для $I_2$ окно $F_2$ берётся с позиции, предсказанной на кадре $I_1$, и так далее.

Пример


Вместо $L_2$ нормы можно использовать $L_1$ ($G_{L_{1}}(i, j) = |F_1(i, j) - F_0|$) и минус кросс-корреляцию матриц ($G_{nCC}(i, j) = -\sum_{kl}{F_{1,kl}(i,j)F_{0,kl}}, k \in [0, m], l \in [0, n] $). И то и другое считается немного быстрее, чем $L_2$, но у них есть свои особенности. $L_1$ недифференцируема и менее чувствительна к большим отличиям в значениях пикселей. Кросс-корреляция может давать ложные срабатывания, если образец низкоконтрастный, и на изображении есть очень светлые или очень тёмные участки.

$L_2$-версия метрики не имеет такого недостатка:

$G_{L_2} = \sum{(F_{1,kl}(i,j) - F_{0,kl})^2}$

$= \sum{(F_{1,kl}(i,j))^2 - 2 F_{1,kl}(i,j) F_{0,kl} + (F_{0,kl})^2}$

$= \sum{(F_{1,kl}(i,j))^2} - \sum{2 F_{1,kl}(i,j) F_{0,kl}} + \sum{(F_{0,kl})^2}$

$= E_{F_1(i,j)} + 2 G_{nCC}(i,j) + E_{F_0}$

$E_{F_1(i,j)}$, «энергия» выбранного участка на $I_t$ выступает в качестве уравновешивающего фактора ($E_{F_0}$, сумма квадратов значений пикселей образца, одинакова для всех положений окна и не имеет здесь практической значимости).

Даже такой примитивный алгоритм довольно неплохо справляется в случае линейного движения объектов (например, камера, смотрящая сверху вниз на конвейер). Однако из-за простоты модели и исполнения у такого способа слежения есть несколько недостатков:

  1. Простое линейное движение объекта без изменений в природе встречается нечасто. Как правило тела в поле зрения камеры могут претерпевать некоторые классы изменений. В порядке увеличения сложности: увеличение/уменьшения размера, повороты, аффинные преобразования, проективные преобразования, нелинейные преобразования, изменения объекта. Даже если опустить изменения объекта и нелинейные преобразования, хотелось бы, чтобы алгоритм мог бы восстанавливаться после сравнительно простых поворотов и изменений размера. Очевидно, что вышеописанная процедура таким свойством не обладает. Вероятно, $F_0$ всё равно даст заметный отклик на объекте, но будет сложно определить точное местоположение образца, и трек будет прерывистым.

    Пример

  2. Мы показали алгоритму только один положительный образец, сложно сказать, какой отклик даст $F_0$, если в окно попадёт другой похожий объект. Хорошо, если искомый объект контрастный и имеет редко встречающуюся структуру, но что если мы хотим следить за машиной в потоке других машин? Трекер может непредсказуемо перепрыгивать с одного автомобиля на другой.
  3. На каждом кадре мы отбрасываем всю предысторию. Наверное, её тоже следует как-то использовать.
  4. Более того, мы обучаемся только на одной точке изображения. Будет лучше, если вблизи правильного местоположения объекта трекер тоже будет давать хороший отклик. Немного контринтуитивно, но подумайте: если фильтр в точном местоположении объекта на картинке $(x, y)$ даёт наилучшее значение, а в $(x+1, y+1)$ — какое-то случайное, значит, он слишком чувствителен к мелким деталям, которые могут легко измениться. И наоборот, если в $(x, y)$ и в $(x+1, y+1)$ примерно одинаковые хорошие значения, то фильтр «зацепился» за более крупные и, как мы надеемся, более постоянные признаки.
  5. При наивной реализации отслеживающей процедуры мы для каждого пикселя кадра умножаем всё окно с выбранным предметом на соответствующую часть этого кадра. Сложность этой операции — $O(m^2n^2)$. В таких случаях не очень приятно отслеживать даже объекты 50 на 50 пикселей. Эта проблема частично решается уменьшением размера видео, но при уменьшении картинки меньше 240 пикселей по ширине начинают теряться даже крупные значимые детали, что лишает алгоритм смысла.

ASEF, MOSSE


Тривиальный подход++?


Закатаем рукава и попробуем решить вышеобозначенные проблемы.

Аугменитруем исходное изображение. Применим к нему несколько несильных аффинных трансформаций. Также можно добавить шум или изменить гамму. Таким образом вместо одного изображения получается микродатасет из $P$ картинок. Изображений стало много, а окно осталось одно. Значит теперь будем не просто вырезать прямоугольник с изображения, а искать некоторый фильтр $W$, который будет давать давал хороший отклик для каждого $I^p$. Преобразуем проблему в задачу минимизации:

$W: \min_W{\parallel F^p - W \parallel_2}, p \in [1, P]$

где $\parallel F^p - W \parallel_2$ — сумма квадратов попиксельных разностей между $W$ и соответствующим ему участку точного местоположения объекта на $p$-том синтетическом изображении, созданном из кадра, на котором есть истинная разметка.

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

С предложением, чтобы фильтр давал хороший отклик в точках рядом с точным местоположением объекта сложнее. Мы знаем что в $(x, y)$ применение фильтра с $L_2$-метрикой должно давать 0, рядом — больше, далеко — ещё больше. Причём, у нас нет какого-то предпочитаемого направления, отклик должен быть центрально симметричен относительно $(x, y)$. Выглядит так, будто мы можем математически выразить, как должен выглядеть отклик фильтра, применённого к опорным изображениям! Точный вид может разниться в зависимости от конкретной функции затухания отклика, но ведь все любят гауссианы? Значит, положим, что $W$, применённый к $F_p$ в идеальном случае должен давать результат $G_p = 1 - \exp{\frac{(x - i)^2 + (y - j)^2}{\sigma^2}}$. Следовательно, задача минимизации превращается в:

$ D_p(i,j) = \parallel F^p(i, j) - W \parallel_2$

$ W: \min_W{\parallel D_p(i,j) - G_p(i, j) \parallel_2}, p \in [1, P] $

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

Секундочку… У нас получилось $P \times m \times n$ уравнений с $m \times n$ переменными для минимизации. Кажется, мы перестарались. Вернёмся немного назад.

Основной приём


Из всех проблем наибольшие затруднения вызывает сложность $O(m^2n^2)$. Разве можно тут что-то придумать кроме хитрого разбиение одного окна поиска на несколько маленьких или поиска на картинке в маленьком разрешении и подстройки на высокоточной?

Оказывается, можно! Матанализ говорит нам, что свёртка функций в обычном пространстве — это перемножение их Фурье-образов. Применять быстрое преобразование Фурье к изображениям, умножать их частоты поэлементно, а затем превращать результат обратно в матрицу мы умеем за $O(mn\log{mn})$, что гораздо быстрее, чем сворачивать матрицы по-честному. Фурье! Кто бы мог подумать! В век tensorflow он всё ещё может помочь нам в компьютерном зрении.

(Это, кстати, демонстрирует общий математический принцип: если не хочешь решать задачу в пространстве $X$, перенеси её в пространство $Y$, реши там, и перенеси решение обратно. Обходной путь часто оказывается короче прямого.)

Как было показано выше, мы можем использовать для локализации образца на изображении кросс-корреляцию. Но кросс-корреляция — это свёртка с горизонтально и вертикально отражённым $W$. Матанализ подсказывает, что в этом случае нужно будет умножить частоты $F$ на комплексно-сопряжённую матрицу к матрице частот $W$:

$\hat{W}(\omega, \nu) = \mathcal{F}(W(x, y))$

$\hat{F}(\omega, \nu) = \mathcal{F}(F(x, y))$

$\hat{G}_{conv}(\omega, \nu) = \mathcal{F}(G_{conv}(x, y))$

$G_{conv} = F \otimes W \rightarrow \hat{G}_{conv} = \hat{F} \odot \hat{W}^*$

где $G_{conv} = \exp{\frac{(x - i)^2 + (y - j)^2}{\sigma^2}}$ — функция идеального отклика на опорном изображении. Обратите внимание, что $L_2$-метрику мы минимизировали, а свёрточную — максимизируем, так что теперь, чем больше отклик, тем лучше.

Будь у нас одно изображение, то мы бы найти точную матрицу частот фильтра:

$\hat{W}^* = \frac{\hat{G}_{conv}}{\hat{F}}$

где в правой части имеется в виду поэлементное деление. Но чуть ранее мы сгенерировали $P$ изображений из исходного. Мы можем применить их и с Фурье-подходом. Нет фильтра с такими частотами, которые бы идеально удовлетворяли бы всем изображениям, но можно получить что-то достаточно хорошее. Есть два способа, которыми можно решить проблему:

  1. Можно найти набор идеальных фильтров, а потом усреднить их в один. Таким путём идут авторы работы Average of Synthetic Exact Filters (ASEF):

    $\hat{W}^* = \frac{1}{P}\sum_{p=1}^{P}\hat{W}^*_p = \frac{1}{P}\sum_{p=1}^{P}{\frac{\hat{G}_p}{\hat{F}^p}}$

    Здесь мы пользуемся свойством линейности Фурье-образов. Складывая частоты, как показано выше, мы как будто усредняем несколько весов фильтров.
  2. Можно найти частоты фильтра, которые удовлетворяют всем картинкам в среднем, примерно как для $L_2$:

    $ \hat{W}^*: \min_{\hat{W}^*}{\sum_{p=1}^{P}{ \parallel \hat{F}^p \odot \hat{W}^* - \hat{G}_p \parallel_2}} $

    Чтобы найти минимум, нужно взять производную по элементам фильтра:

    $\frac{\delta}{\delta\hat{W}^*}\sum_{p=1}^{P}{ \parallel \hat{F}^p \odot \hat{W}^* - \hat{G}_p \parallel_2} = 0$

    Честное взятие этой производной можно посмотреть в работе Visual Object Tracking using Adaptive Correlation Filters, которая предлагает фильтры Minimum Output Sum of Squared Error (MOSSE-фильтры). Результат получится такой:

    $\hat{W}^* = \frac{\sum_{p=1}^{P}{\hat{G}_p \odot \hat{F}^{p*}}}{\sum_{p=1}^{P}{\hat{F}^p \odot \hat{F}^{p*}}}$


Хм, как будто бы в формулах участвуют похожие элементы. При $P = 1$ формулы для ASEF и MOSSE и вовсе совпадают. $\hat{W}^*$ для одного изображения можно представить как

$\hat{W}^* = \frac{\hat{G_p}}{\hat{F^p}} = \frac{\hat{G_p} \odot \hat{F}^{p*}}{\hat{F^p} \odot \hat{F}^{p*}}$

Подставим в формулу для ASEF и получим

$\hat{W}^* = \sum_{p=1}^{P}{ \frac{\hat{G}_p \odot \hat{F}^{p*}}{\hat{F}^p \odot \hat{F}^{p*}}}$

Ага! Теперь гораздо лучше видно, что ASEF и MOSSE отличаются лишь в способе усреднения фильтров! Утверждается, что MOSSE порождает более хорошие фильтры, чем ASEF. Звучит логично: подстройка под всю пачку изображений в целом это лучше, чем усреднение фильтров.

После того как мы получили $\hat{W}^*$, мы вычисляем отклик в частотной области $\hat{G}_{conv} = \hat{F} \odot \hat{W}^*$, затем переводим его в пространственную область и ищем максимум в получившейся матрице $G$. Где максимум — там и новое положение объекта.

Дополнительные моменты


  • Члены суммы в знаменателях формул имеют интересный физический смысл. $\hat{F}^p \odot \hat{F}^{p*}$ — это энергетический спектр прямоугольника с $p$-того изображения.
  • Обратите внимание на интересную симметрию. Нужно было умножить частоты фильтра на частоты изображения, чтобы получить отклик. Теперь нужно умножить частоты отклика на частоты изображения (и нормализовать), чтобы получились частоты фильтра.
  • В реальной жизни при поэлементном делении может возникнуть деление на ноль, так что в знаменатель обычно добавляют регуляризующую константу $\epsilon$. Утверждается, что такая регуляризация заставляет фильтр больше обращать внимание на низкие частоты, что улучшает обобщающую способность.
  • При обработке реального видео обычно хочется сохранять информацию об отслеживаемом объекте, полученную с предыдущих кадров. При переходе на следующий кадр можно не вычислять $\hat{W}$ с нуля, а обновить предыдущий. Формула обновления для ASEF:

    $\hat{W}^*_i = \frac{\eta}{P}\sum_{p=1}^{P}{\frac{\hat{G_p}}{\hat{F^p}}} + (1 - \eta)\hat{W}^*_{i-1}$

    Для MOSSE нужно накапливать числитель и знаменатель отдельно:

    $A_i = \eta \sum_{p=1}^{P} \hat{G}_p \odot \hat{F}^{p*} + (1 - \eta) A_{i-1}$

    $B_i = \eta \sum_{p=1}^{P} \hat{F}^p \odot \hat{F}^{p*} + (1 - \eta) B_{i-1}$

    $\hat{W}^*_i = \frac{A_i}{B_i}$

    где $\eta$ — скорость обучения.
  • Важно помнить, что преобразование Фурье — не совсем то же самое, что и вычисление $G$ по-честному, как описано в начале статьи. При вычисление БПФ отсутствующие элементы не зануляются, а подставляются с обратной стороны, как если бы изображение зацикливалось справа-налево и снизу-вверх. Но в самом начале статьи мы уже решили затемнять края $F$, так что эта проблема не окажет заметного влияния.
  • Как упомянуто выше, кросс-корреляция имеет неприятную особенность: в целом светлый фильтр может давать сильный отклик на белых областях изображения, даже если они не совпадают в контрастных участках. Этим проблемы не ограничиваются. Даже один совпадающий пиксель с сильноположительным или сильноотрицательным значением может внести помехи в работу фильтра, если образец в целом низкоконтрастный. Чтобы сгладить этот эффект, в препроцессинг нужно включить нелинейное преобразование пикселей изображения, которое «прижмёт» слишком светлые и слишком тёмные участки к среднему. Благодаря этому совпадение настоящих контрастных участков вносит более сильный вклад в метрику. В статьях ASEF и MOSSE используется логарифм:

    $I = \log{I + 1}$

    где пиксели $I$ от 0 до 255. На мой взгляд, это слишком жёстко, и игнорирует проблему сильного отклика тёмного фильтра на чёрных участках. Лучше работает такая схема:

    $I = sign(I - 127)\sqrt{|I - 127|}$

    После чего идёт нормализация, и оказывается, что большинство элементов сосредоточены вокруг нуля.
  • Как при таком алгоритме определить, что отслеживаемый объект пропал с кадра? Здесь поможет более детальный анализ отклика, полученного с очередного кадра. Создатели MOSSE предлагают показатель PSR — Peak to Sidelobe Ratio. Пусть $g_{max}$ — максимальный элемент $G$, соответствующий новому положению объекта $(x, y)$. Исключим из рассмотрения квадрат $11 \times 11$ вокруг этого максимума. Посчитаем по остальным пикселям среднее и среднеквадратчное отклонение ($\mu_{sl}, \sigma_{sl}$). Тогда

    $PSR = \frac{g_{max} - \mu_{sl}}{\sigma_{sl}}$

    Если это значение выше определённого порога, то детекция считается удачной. Порог обычно берётся в районе между 3 и 10. Для уверенных детекций PSR обычно держится выше 20.

    (заметьте, что здесь PSR означает совсем не то, что он обычно означает в теории обработки сигналов; так что не гуглите его применение, ничего хорошего не выйдет)
  • Алгоритм чрезвычайно прост. Выполнение процедуры трекинга на Core-i7 на картинках с 320x400 при использовании OpenCV-имплементации занимает от 0.5 до 2 миллисекунд в зависимости от размера отслеживаемого объекта.

Алгоритм MOSSE


Соберём всё вместе.

Общее состояние:

Матрица частот фильтра: $\hat{W}$
Вспомогательные матрицы для вычисления частот фильтра: $A, B$
Матрица частот желаемого идеального отклика: $\hat{G}$
Скорость обучения во время трекинга: $\eta$
Прямоугольник текущего положения объекта: $R$
Количество трансформаций: $P$
Порог отклика: $PSR_{thr}$

Вспомогательная функция: Тренировка. Вход: изображение $I$, текущая скорость обучения $\eta_{current}$

  1. $A_{new} := 0, B_{new} := 0$
  2. Пока не набралось $P$ трансформаций:
    1. Применить к изображению небольшую случайную аффинную трансформацию с центром в центре $R$
    2. Вырезать из изображения с прямоугольник с объектом $F$
    3. Применить к нему маску, чтобы плавно занулить края
    4. Перевести $F$ в частотную область: $\hat{F}$
    5. $A_{new} = A_{new} + \hat{G} \odot \hat{F}^*$
    6. $B_{new} = B_{new} + \hat{F} \odot \hat{F}^*$

  3. Если $\eta_{current} \geq 1.0$, то заменить $A$ и $B$ на $A_{new}$ и $B_{new}$. Иначе:

    $B := \eta B_{new} + (1 - \eta) B$

    $A := \eta A_{new} + (1 - \eta) A$

  4. Вычислить частоты фильтра:

    $\hat{W}^* = \frac{A}{B}$


Инициализация. Вход: изображение $I$, прямоугольник вокруг положения объекта $R_{init}$

  1. $R := R_{init}$
  2. Приготовить желаемый отклик $G$. Обычно это полностью занулённая матрица с небольшой гауссианой в центре.
  3. Тренировка: $I$, 1.0
  4. Перевести $G$ в частотную область: $\hat{G}$

Трекинг: Вход: изображение $I$

  1. Вырезать прямоугольник $F$ из $I$ для имеющегося предыдущего положения объекта $R$
  2. Применить к нему маску, чтобы плавно занулить края
  3. Перевести $F$ в частотную область: $\hat{F}$
  4. $\hat{G}_{response} = \hat{W} \odot \hat{F}^*$
  5. Перевести $\hat{G}_{response}$ в пространственную область: $G_{response}$
  6. Найти максимум в $G_{response}$: $g_{max}, (x, y)$
  7. Посчитать силу отклика $PSR := \frac{g_{max} - \mu_{sl}}{\sigma_{sl}} $
  8. Если $PSR < PSR_{thr}$, выйти с неудачей
  9. Обновить положение $R$. Подстроить R, если он вышел за пределы изображения, или было решено, что объект увеличился/уменьшился.
  10. Тренировка: $I$, $\eta$
  11. Вернуть $R$

Подробности имплементации могут варьироваться. Например,

  • Препроцесситься может только $F$, а не всё изображение.
  • $G$ может пересоздаваться для каждой трансформации изображения с варьированием функции и ширины отклика.
  • Можно одновременно обучать несколько различных фильтров на нескольких масштабах объекта, чтобы обнаруживать перемещения вдаль и вблизь.

Как это выглядит


Для начала, несколько примеров двумерного Фурье-преобразования.

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

Вертикальные линии:





Картинка изменяется слева направо одинаково для любого положения по вертикали. Более того, изменение периодическое, с чётким периодом и явным паттерном. Поэтому на картинках частот вы видите только частоты вдоль оси $x=0$.

Клетка:





Обратите внимание, что есть как ожидаемые серии частот вдоль осей $x=0$ и $y=0$, так и странные паразитные частоты. Они появились из-за того, что во-первых, картинка конечна, тогда как Фурье-образ разлагается в красивую сумму только для бесконечного периодического сигнала. Во-вторых, можно заметить, что изображение не образует точный период на краях.

Наклонные линии:





Снова видны как частоты, соответствующие основному направлению, так и паразитные частоты.

Наклонные линии плюс дисторсия:





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

Для изображений настоящего мира представить картинку в голове по её частотам ещё сложнее:





(частоты в центре закрыты, чтобы они не «засвечивали» остальной спектр)

Теперь перейдём к реальному примеру работы:

Пачка картинок
Изображение с размеченным объектом:



Вырезанный и предобработанный объект, его спектр в обычном и логарифмическом масштабе ($F, |\hat{F}|, \log{|\hat{F}|}$):





Желаемый отклик ($G$):



Частоты фильтра в обычном и логарифмическом масштабе ($W, |\hat{W}|$):




Явно выраженные веса фильтра (без применения трансформаций $F$):



Обратите внимание, что они нигде не участвуют в алгоритме — их можно посчитать разве что ради интереса. Также обратите внимание, что фильтр выглядит как чёрте что. Можно было бы ожидать, что фильтром оказалось бы что-то похожее на изначальное изображение, но это отнюдь не всегда правда. Фильтр, похожий на само изображение вряд ли бы дал желаемую гауссиану откликом.

Отклик от следующего кадра:



Хоть он и не такой чистый, как желаемый отклик, на нём легко определить максимум.

Тот же пример с более узким желаемым откликом:

Пачка картинок
Уже:


$W$:


Ещё уже:


$W$:


При очень узком максимуме на фильтре вместо чёрного пятна становится явно виден глаз.

$W$ для предыдущих трёх случаев $G$ при использовании для обучения 16 трансформаций входного изображения:

Ещё пачка картинок
Широкий максимум:



Средний максимум:



Узкий максимум:



Чем больше трансформаций, тем меньше фильтр цепляется за случайные элементы. Особенно хорошо видно, что пропали случайные чёрно-белые пятна из середины $W$. С другой стороны, для узкой гауссианы обучение на нескольких картинках может сыграть в минус: посмотрите на «звон» образовавшийся в фильтре вокруг глаза.

Если вы хотите увидеть, как это выглядит вживую, скачайте отсюда мой тестовый репозиторий с имплементацией MOSSE с выводом отладочных картинок. На гитхабе можно найти больше вариантов MOSSE. Кроме того, он есть в OpenCV.

Заключение


Спасибо за внимание, хабровчане. MOSSE и ASEF трекинг — не самые сложные алгоритмы на свете. Тем легче не только их эффективно применить, но и и понять, чем руководствовались их создатели. Я надеюсь, что моё объяснение помогло вам проникнуть в голову исследователей, проследить за ходом их мысли. Это может оказаться полезным: машинное обучение — не статическая область знаний, в ней есть место для творчество и собственных исследований. Попробуйте поковыряться в каком-нибудь устоявшемся алгоритме: поотпиливать ненужные конечности для ускорения или добавить парочку, чтобы он стал работать лучше в вашем частном случае. Вам понравится!

Статья написана при поддержке компании DSSL.