Радченко Д.С., Козаченко А.А.

Национальный горный университет, Украина

Обоснование выбора метода отслеживания точек на видеоизображениях

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

Изображение по своей структуре — это матрица двумерных чисел, которая содержит большое количество информации о наблюдаемой сцене. Извлечь структурированную информацию из этой сцены является довольно сложной задачей. Если же речь идет видеоданных, т.е. о последовательности изображений, то задача еще более усложняется, так как между кадрами существуют пространственно-временные связи. Таким образом, требуется некоторая техника, которая позволила бы извлекать и анализировать информацию, заложенную в видеопоследовательности.

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

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

Пример трекинга точки

Особые точки

Точечная особенность изображения m — это такая точка изображения, окрестность которой o(m) можно отличить от окрестности любой другой точки изображения o(n) в некоторой другой окрестности особой точки.

Для простоты в качестве окрестности точки изображения берется прямоугольное окно небольшого размера. Для сравнения таких прямоугольных окон могут использоваться различные меры на изображениях.

Особая точка сцены или точечная особенность (point feature) – это такая точка сцены, изображение которой можно отличить от изображений всех соседних с ней точек сцены.

Для сравнения и описания точек можно использовать их окрестности. Т.е. под точечной особенностью понимается такая точка сцены M, лежащая на плоском участке поверхности сцены PlaneSegment, изображение окрестности I(PlaneSegment) которой можно отличить от изображений окрестностей всех других точек сцены N из некоторой другой окрестности этой точки O(M).

Существует целый набор функций, которые можно использовать для обнаружения точечных особенностей. Чаще всего для задач отслеживания точек сцены применяются функции, находящие в изображении структуры, похожие на угол – уголки. (corners). Детекторы, использующие такие функции, называются детекторами углов. Они чаще всего применяются для решения задач отслеживания точечных особенностей сцены.

Формальная постановка задачи

Пусть есть последовательность изображений I(x,t), в которой изображения представляются как некоторая дискретная двумерная функция (массив) интенсивностей пикселей в каждый момент времени t.
Цель алгоритма состоит в том, чтобы найти такую точку v=u+d на изображении I(v,t+1), что u и v «похожи», u=[u_x, u_y] и принадлежит I(x,t). В общем случае, для определения степени похожести вычисляется определенный дескриптор точки, и они сравниваются по некоторой метрике. Дескриптор и метрика выбираются в зависимости от алгоритма.

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

Существующие методы

Существующие потребности в создании систем отслеживания объектов накладывают жесткие ограничения на скорость работы алгоритмов, которые должны работать в режиме близком к реальному времени. Однако даже наиболее быстрые из существующих подходов (Viola 2001, Lienhart 2002, Shneiderman 2004) позволяют обнаруживать лица в реальном времени лишь при вертикальном положении лица и непригодны для обнаружения лиц, повернутых в плоскости изображения под произвольным углом.

Все работы опираются на работы Lukasa и Kanade 1981 года [1]. Позже формулировки были изменены. Следующие алгоритмы написаны на ее основе с учетом различных аффинных преобразований [2] движения и изменения освещения.

Lucas-Kanade. В этом алгоритме движение рассчитывается самым простым образом и не учитывает возможные изменения структуры региона вокруг отслеживаемой точки.

Метод Лукаса и Канаде подразумевает, что смещение между двумя кадрами мало и одинаково в пределах соседей некоторой точки p по определению. 

Где q₁,q₂,…,q_n — точки внутри окна поиска, и I_x(q_i),I_y(q_i),…,I_t(q_i) частные производные изображения I по x, y и времени t, вычисляемые в точке q_i в текущий момент времени.

Эти выражения можно переписать в матричной форме Av=b, где

Эта система уравнений обычно сильно избыточна, поэтому ее решают методом наименьших квадратов.

суммы берутся от i=1 до n.

Tomasi-Kanade. В целом алгоритм повторяет основной, за исключением того, что после решения методом наименьших квадратов смещение уточняется с помощью метода Ньютона-Рафсона [3]. На каждом шаге используется интерполяция для получения субпиксельной точности [4]. Фактически используется градиентный спуск.

Shi-Tomasi-Kanade. В этом алгоритме учитываются возможные аффинные искажения [5]. Модель смещения принимает вид Ax+d, где A — аффинное искажение размером 2х2, а d — смещение, размером 2х1. Для вычисления смещения ищутся параметры, минимизирующие

где   — окно поиска, W(x) — весовая функция в окне.

Для поиска минимума выражение дифференцируется и приравнивается к нулю. Потом производится разложение в ряд Тейлора:

J(Ax+d)=J(x)+g^t(u).

Такое разложение дает нам систему Tz=a, где z=[d_xxd_yxd_xyd_yyd_xd_y].

Тогда вектор ошибки можно записать, как

Матрицу T можно разложить как 

В результате проведения сравнительного анализа методов отслеживания точек на видеоизображениях, можно сделать вывод, что наиболее перспективным является метод Shi-Tomasi-Kanade, учитывающий аффинные искажения. Возможность учета этих искажений позволяет для каждой наблюдаемой точки строить вектор перемещения, на основании которого появляется возможность прогнозирования следующего местоположения точек. Это в свою очередь позволит определить возможные изменения плоскости наблюдаемого объекта и идентифицировать ситуацию, когда какие-то из наблюдаемых точек выйдут за пределы видимости камеры.

Список литературы

1. Lucas, Kanade “An Iterative Image Registration Technique with an Application to Stereo Vision”, 1981 [Электронный ресурс]. Режим доступа:

http://www.ces.clemson.edu/~stb/klt/lucas_bruce_d_1981_1.pdf

2. Аффинные преобразования. Википедия [Электронный ресурс]. Режим доступа:

http://ru.wikipedia.org/wiki/Аффинное_преобразование

3. Метод Ньютона-Рафсона [Электронный ресурс]. Режим доступа:

http://avti15.ru/eor/index.php?glava=8&razdel=2

4. Субпиксельная точность [Электронный ресурс]. Режим доступа:

http://algolist.manual.ru/graphics/3dfaq/articles/71.php

5. Аффинные искажения [Электронный ресурс]. Режим доступа:

http://www.stereokino.ru/slovar/slovar%201.htm