Трекинг (компьютерная графика)

Трекингом называется определение местоположения движущегося объекта (нескольких объектов) во времени с помощью камеры. Алгоритм анализирует кадры видео и выдает положение движущихся целевых объектов относительно кадра.

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

Примерами таких простых моделей движения являются:

трекинг плоских объектов, модель движения – 2D преобразование (аффинное преобразование или гомография) изображения объекта (например, исходного кадра)
когда целевым является жесткий 3D объект, модель движения определяет вид в зависимости от его положении в пространстве и ориентации
для сжатия видео, ключевые кадры (key frames) разделяются на макроблоки (macroblocks). Модель движения представляет собой разрыв ключевых кадров, где каждый макроблок преобразуется при помощи вектора движения полученного из параметров движения
изображение деформируемого объекта может быть покрыто сеткой (mesh), движение объекта задается положением вершин этой сетки

Основная задача алгоритма трекинга – это последовательный анализ кадров видео для оценки параметров движения. Эти параметры характеризуют положение целевого объекта.

Основные алгоритмы^[1]

Система визуального наблюдения (трекинга) состоит из двух основных частей:

Представление и Локализация Целевого Объекта (Target Representation and Localization)
Фильтрация и Объединение Данных (Filtering and Data Association)

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

Blob tracking: Сегментация интерьера объекта (например blob detection, block-based correlation или оптический поток (optical flow))
Kernel-based tracking (Mean-shift tracking): Итеративная процедура локализации, основанная на максимизации критерия подобия (Bhattacharyya coefficient).
Contour tracking (трекинг контуров): Поиск границы объекта (например активные контуры или Condensation algorithm)
Визуальное согласование особенностей (feature matching): Регистрация (Image registration)
Point feature tracking^[2] (Слежение за точечными особенностями сцены): Задача формулируется так - дана последовательность изображений некоторой сцены, полученная с движущейся или неподвижной камеры. Необходимо получить набор как можно более точных последовательностей координат проекции некоторых точек сцены в каждом кадре.

Фильтрация и Объединение Данных представляет собой по большей части нисходящий процесс (top-down process), который включает в себя объединение априорной информации о сцене или объекте, соотносящейся с динамикой объекта и вычислением различных гипотез. Вычислительная сложность этих алгоритмов обычно намного выше. Вот некоторые стандартные алгоритмы фильтрации^[3]:

Фильтр Кальмана: оптимальный рекурсивный (Bayesian filter) для линейных функций, подверженных шуму по Гаусу.
Фильтр частиц (Particle filter): полезно для семплинга базового пространства состояний распределения нелинейных и негауссовых(non-Gaussian) процессов.

См. также

Примечания

↑ Alper Yilmaz, Omar Javed and Mubarak Shah, "Object Tracking: A Survey", ACM Journal of Computing Surveys, Dec 2006.
↑ Статья CGM "Слежение за точечными особенностями сцены (Point feature tracking)" (неопр.). Дата обращения: 17 мая 2010. Архивировано из оригинала 23 мая 2012 года.
↑ M. Arulampalam, S. Maskell, N. Gordon, and T. Clapp, "A Tutorial on Particle Filters for Online Nonlinear/Non-Gaussian Bayesian Tracking", IEEE Trans. on Signal Processing, Vol. 50, no. 2, Feb. 2002.