Компьютерная Графика и Мультимедиа Сетевой журнал

Извлечь из изображений структурированную и осмысленную информацию о наблюдаемой сцене невероятно сложно. В статье дан обзор существующих методов слежения за точечными особенностями сцены в потоке изображений.
1  Введение
1 Особенности или особые точки
2 Слежение за точечными особенностями
3 Простая и расширенная схема работы системы слежения
4 Нахождение набора особенностей
5 Математическая формулировка задачи слежения
6 Развитие алгоритмов слежения
7 Lucas-Kanade tracker
8 Tomasi-Kanade tracker
9 Shi-Tomasi-Kanade tracker
10 Модификация трекера для случая переменного освещения
11 Нормализация окрестностей изображения для учета изменений освещения
12 Автоматический отбор некачественных особенностей
13 Пример трекинга особенностей
14 Ссылки

0. Введение

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

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

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

1. Особенности или особые точки

Что же такое точечная особенность или особая точка сцены? Поскольку почти вся информация, известная нам о сцене, содержится в ее изображениях, то и особая точка сцены должна определятся через изображения.

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

Сразу встает множество вопросов - а что понимается под изображением точки и как изображение одной точки можно отличить от изображения другой точки, если у нас есть только дискретизированное представление изображения сцены (цифровое изображение - digital image)?

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

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

Воспользовавшись последним определением можно дать определение точечной особенности изображения:

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

Из этих определений хорошо видно, что между особенностями сцены и особенностями изображения есть соответствие: точечной особенности сцены должна соответствовать точечная особенности изображений. Обратное неверно: существуют такие особые точки изображения, которым не соответствует никакие особые точки сцены. Такие точки называется ложными особенностями сцены (false feature point).

Отделение ложных особенностей от настоящих является одной из основных проблем при отслеживании движении камеры или при реконструкции трехмерной сцены. Усугубляется она тем, что надежно решить ее, работая только с одним изображением, невозможно. Необходимо устанавливать соответствие между особенностями нескольких изображений, а затем построить некоторую модель, которой эти соответствия будут удовлетворять наилучшим образом. Особые точки, сответствия которых не будут удовлетворять такой модели, будут признаны ложными, или выбросами (outlier).

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

Для простоты в качестве окрестности точки изображения берется прямоугольное окно небольшого размера. Для сравнения таких прямоугольных окон могут использоваться различные меры на изображениях (например, обычное SSD - Sum of Squared Difference или кросс-корреляция).

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

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

2. Слежение за точечными особенностями

С точки зрения "черного ящика", без рассмотрения принципов работы, задача слежения за особенностями (feature tracking) формулируется так:

Дана последовательность изображений ImageSequence некоторой сцены S, полученная с движущейся или неподвижной камеры. Необходимо получить набор как можно более точных последовательностей координат проекции некоторых точек сцены в каждом кадре, т.е. набор SceneFeatureImage[i] = {x (t), y(t)}, где x(t), y(t) - координаты проекции особенности i в кадре, полученном в момент времени t.

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

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

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

Дана последовательность изображений ImageSequence одной и той же сцены S, полученная с движущейся или неподвижной камеры, и набор точечных особенностей {N}, выделенных в первом кадре последовательности. Для каждой точечной особенности n из {N} найти такие точки n(t) на всех изображениях, что их окрестности будут максимально близки к окрестности n(0), с учетом предполагаемой природы искажения ее окрестности и движения точки.

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

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

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

При изменении точки зрения меняется и освещенность окрестности точки сцены, а значит, меняется и яркость пикселей изображения этой окрестности. Эти изменения можно минимизировать, если воспользоваться нормализацией изображения окрестности особенности. С другой стороны, изменения освещенности при небольших смещениях камеры от кадра к кадру можно описать в форме аффинных искажений a * I + b. При поиске нового положения особенности в некоторых алгоритмах рассчитывается и параметры изменения освещения ее окрестности a и b.

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

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

3. Простая и расширенная схема работы системы слежения

Схема работы любой системы слежения за особенностями состоит из двух основных этапов:

Схема А.

Этап 1 (Детектирование):
Определить в первом кадре особенности изображения

Этап 2 (Слежение):
Для каждого последующего кадра:

• Для каждой особенности Feature(i):
  • Найти новое положение особенности в кадре t

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

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

С учетом оценки качества особенностей, и дополнения множества отслеживаемых особенностей схема А расширяется до:

Схема B.

Этап 1 (Детектирование и оценка)

1. Найти набор особенностей {Features}
2. Определить качество всех особенностей - Quality({Features})
3. Оставить только особенности, чье качество выше некоторого заранее или динамически определенного порога, получив множество {GoodFeatures}

Этап 2 (Слежение и оценка)
Для каждого последующего кадра:

1. Найти в текущем кадре новое положение всех особенностей из {GoodFeature} - слежение (tracking)
2. Определить текущее качество всех {GoodFeatures}
3. Оставить только те особенности, чье качество удовлетворяет некоторому критерию
4. Если число отслеживаемых точек падает ниже требуемого, применить детектор к текущему изображению и добавить в {GoodFeatures} новые точки.

4. Нахождение набора особенностей

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

Чаще всего используется детектор Харриса [1]. Для каждого пикселя изображения вычисляется значение особой функции отклика угла (corner response function), оценивающая степень похожести изображения окрестности точки на угол.

Для этого вначале рассчитывается матрица:

где I(x,y) - яркость изображения в точке (x,y)

Если оба ее собственных значения велики, то даже небольшое смещение точки (x,y) в сторону вызывает значительные изменения в яркости. Что и соответствует особенности изображения. Функция отклика угла записывается в следующем виде:

Параметр k обычно полагается 0.04 (предложено Харрисом). Точки изображения, соответствующие локальным максимумам этой функции и признаются особенностями. Для достижения субпиксельной точности может использоваться квадратичная (quadratic) интерполяция.

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

Во многих случаях находится чересчур большое количество углов, из-за чего в дальнейшем их будет сложно отслеживать. Поэтому вводится ограничение на минимальное расстояние между найденными особенностями, и все лишние отбрасываются.

Окрестность с субпиксельной точностью

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

GoodFeaturesToTrack:

Для повышения качества слежения за особенностями детектор Харриса был в последующем модифицирован [4]. Главное отличие заключается в суммировании матриц по окну W (потенциальной особенности)

Для каждого пикселя изображения вычисляется матрица H:

Точка считается особенностью, если минимальное собственные значение (eigenvalue) больше некоторого заданного порога:

5. Математическая формулировка задачи слежения

Пусть I(x, t) - яркость изображения-кадра со временем t в точке x, где x - вектор. Движение изображения (image motion), вдали от границ видимости (occluding boundaries), описывается с помощью уравнения вида: I(x,t) = I (delta(x), t+t1) (*), где delta(x) - движение точки x при переходе от кадра (t) к (t+t1).

Перемещение особенности от кадра к кадру описывается этим уравнением для всех точек x из окрестности особенности W.

Отметим, что в этом случае полагается, что освещение точки сцены, соответствующей особенности, остается постоянным.

При малых изменениях изображения от кадра к кадру можно считать, что окно особенности просто смещается, и движение delta(x) принимает вид delta(x) = x +d. Однако при увеличении длительности слежения, изображение точки сцены искажается. Это искажение может быть приближенно описано аффинной трансформацией, поэтому движение точек описывается аффинным преобразованием delta(x) = Ax + d, где A - матрица размерности 2*2.

Задача трекера заключается в отыскании значения движения delta(x) для всех точек окна особенности W. Т.к. в реальных условиях (*) никогда строго не выполняется, то ищется такое движение, при котором минимизируется разница между окнами при текущем и будущем положении особенности, т.е. такое delta(x), при котором достигается минимум
e = |I(delta(x), t+t1) - I(x, t)|,
или
,
если норма разности изображений L₂

6. Развитие алгоритмов слежения

Все современные алгоритмы слежения за особенностями опираются на работу 1981 году Лукаса и Канаде. В 1991 году математическая формулировка этого алгоритма была изменена, и стала основой для всех последующих обобщений с учетом аффинных искажений окрестности и освещенности. Путем замены соответствующих переменных на константы любой из них превращается в обычный алгоритм Lucas-Kanade.

1. Lucas-Kanade - особенность считается только смещающейся, без искажений
2. Tomasi-Kanade - переформулирование Lucas-Kanade. Движение считается смещением, и рассчитывается путем итеративного решения построенной системы линейных уравнений.
3. Shi-Tomasi-Kanade - учитывает аффинные искажения особенности
4. Jin-Favaro-Soatto - модификация Shi-Tomasi-Kanade с учетом аффинных изменений освещенности особенности

7. Lucas-Kanade tracker [2]

Этот алгоритм в принципе применим для функций любой размерности n. Пусть x - особенность первой функции F, необходимо найти такую точку x+h функции G, что разность окрестностей этих точек по мере - минимальна.

Расстояние между окрестностями записывается в виде:

где F(x), G(x) - две функции

Функцию F(x) с помощью разложения в ряд Тейлора можно приближенно представить в виде:

где
- градиент.

Используя это приближение, ищется минимум E путем дифференцирования и приравнивания производной к нулю:

Отсюда смещение h можно получить как

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

8. Tomasi-Kanade tracker [3]

В этом алгоритме движение особых точек также описывается смещением вида:

Как и в предыдущем алгоритме, задача заключается в поиске такого d, при котором минимизируется разность окон особенностей:

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

где

Тогда разницу между окнами по мере можно переписать в виде:

Дифференцировав это выражение по d и приравняв производную к нулю, получаем линейную систему относительно d:

где:

Из этой системы d получается как:

С учетом приближения функции изображения с помощью ряда Тейлора, решение получается неточным. Для его уточнения удобно применить итеративную процедуру Ньютона-Рафсона. Т.е. полученное на первом шаге решение берется за новое первое приближение, уравнение снова и снова.

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

Если интервал времени между кадрами принять за 1, получается следующий алгоритм:

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

9. Shi-Tomasi-Kanade tracker [4]

В этом алгоритме впервые учитываются аффинные искажения изображения окрестности особых точек, поэтому движение пикселей окна особенности описывается в виде Ax + d, где A - матрица (2*2), а d - смещение (2*1).

Задача слежения за особенностью сводится к проблеме проблема определения параметров движения и искажения окна особенности, при которой минимизируется разность:

где W - окно особенности, а w - весовая функция (может использовать, а может и быть равна 1 во всем окне), J(x) и I(x) - два изображения.

Выражение дифференцируется относительно параметров движения, и производная приравнивается к 0. Затем система линеаризуется с помощью разложения функции изображения в ряд Тейлора:

Это дает нам линейную 6*6 систему:

, где в векторе z объединены все искомые параметры:

Вектор ошибки a записывается в виде:

А матрицу размерности 6*6 T можно представить следующим образом:

Полученная система решается также итеративно по методу Ньютона-Рафсона.

Если движение считается не аффинным, а просто смещением, то первые четыре элемента искомого вектора z обращаются в 0, и значимыми остаются только последние два. Алгоритм превращается в алгоритм Tomasi-Kanade .

10. Модификация трекера для случая переменного освещения ([2],[10])

Пусть поверхность сцены, на которой найдена особенность сцены, является ламбертовой. Тогда интенсивность освещения точки x = P(X), где X - точка сцены, P - оператор проектирование, x - точка на изображении может быть описана как:

где E(X) - альбедо (отражающая способность) точки сцены, U - окрестность точки сцены, v & e - постоянные параметры, которые представляют изменения контраста и яркости изображения соответственно. При движении камеры эти параметры меняются, т.е. зависят от времени. Изменения освещенности во времени можно записать как:

где

при t > 0.

Объединив аффинное движение окрестности особенности с изменением освещенности, получим выражение:

Из-за шума в изображении, а также из-за приближенного моделирования движения и изменения освещенности это уравнение в реальности никогда не будет выполняться, поэтому задача слежения состоит в минимизации разности между окрестностями текущего и нового положения особенности:

где w(x) - весовая функция.

С помощью разложения в ряд Тейлора в окрестности d=0, v = 1, (кси) = 0 получим:

Переписав получившееся равенство в матричной форме, получим следующее уравнение:

где

Домножив на , и проинтегрировав по всему окну особенности W с весовой функцией w мы получим систему уравнений 8*8:

Заменив интегрирование на сумму по всем пикселям в окне W, мы приходим к следующей системе линейных уравнений:

Если матрица S получается обратимой, то решение системы линейных уравнений можно записать в виде:

Как во всех алгоритмах слежения, система решается итеративно по методу Ньютона-Рафсона. Итерации происходят до тех пор, пока изменения решения не становятся пренебрежимо малы.

11. Нормализация окрестностей изображения для учета изменений освещения

Для учета изменения освещенности можно использовать вместо стандартной меры SSD нормализованную:

где ν - средний уровень яркости в окне, а σ - стандартная дисперсия уровня яркости в окне.

12. Автоматический отбор некачественных особенностей

Авторы Shi-Tomasi-Kanade в своей работе показывают, что непосредственно для слежения за особенностями больше всего подходит обычный Tomasi-Kanade алгоритм. Алгоритм с учетом аффинных искажений в этом случае можно использовать для определения текущего качества особенности, т.е. степени близости ее окна к окну детектированной особенности. Однако они не предлагают никаких автоматических методов определения порога, когда особенность признается плохой и перестает отслеживаться. Этот недостаток попытались исправить авторы [6]-[9], с помощью введения правила X84.

Предположим, что после точного вычисления движения особенности, яркость соответствующих пикселей будет совпадать с точностью до некоторой ошибки, распределенной по нормальному закону (гауссову шуму):

Т.к. квадрат нормального распределения представляет собой распределение хи-квадрат, мы получаем:

Сумма n переменных, с распределением по хи-квадрат с одной степень свободы, распределена как хи-квадрат с n степенями свободы. Поэтому, разница между особенностями по окну N*N W имеет вид:

При возрастании степени свободы, распределение хи-квадрат приближается к нормальному распределению. При степени свободы больше 30, нормальное распределение можно использовать как приближение хи-квадрат. Если размер окна особенности, по крайней мере, 7*7, то можно спокойно утверждать, что:

Поэтому, если два окна, которые мы сравниваем, принадлежат плохой особенности, то разница должна быть выбросом (outlier) по отношению к нормальному распределению разницы между хорошими особенностями. Для определения таких выбросов предлагается использовать правило Х84, являющееся устойчивым за счет использования медианы и медианной дисперсии, вместо обычного среднего и дисперсии.

Согласно правилу, все значения, отклоняющиеся от медианы на более чем k Медианных абсолютных дисперсий (МАД, Median Absolute Deviation - MAD):

где e - разница между текущим окном особенности и ее окном в первом кадре.

При значении k=5.2 это соответствует примерно 3.5 стандартным дисперсиям, и интервал [u-3.5sigma, u+3.5sigma) содержит более 99.9% значений нормального распределения.

Как утверждается, правило позволяет эффективно определять уменьшение качества особенности и отсекать ее во всех случаях, при которых количество выбросов меньше 50%.

13. Пример трекинга особенностей

14. Ссылки:

1. Pollefey "Tutorial on 3d reconstruction" 2000
   http://www.esat.kuleuven.ac.be/~pollefey/tutorial/
2. Lucas, Kanade "An iterative image registration technique with an application to stereo vision" 1981
3. Tomasi, Kanade "Detection and tracking of point features" TR Carnegie-Melon University, 1991
4. Shi, Tommasini "Good features to track" 1994
5. Smith, Sinclair, Cipolla, Wood "Effective corner matching"
6. Tommasini, Fusiello, Roberto, Trucco "Robust feature tracking" 1998
7. Tommasini, Fusiello, Trucco, Roberto "Making good features track better" 1998
8. Fusiello, Trucco, Tommasini, Roberto "Improving feature tracking with robust statistics"
9. Tommasini, Fusiello, Roberto, Trucco "Robust feature tracking in underwater sequence"
10. Jin, Favaro, Soatto "Real-time tracking and outlier rejection with changes in illumination" 2001

Дополнительная информация

Ссылка: 

Антон Конушин. Слежение за точечными особенностями сцены (Point feature tracking). Компьютерная графика и мультимедиа. Выпуск №1(5)/2003. http://cgm.computergraphics.ru/content/view/54

Выпуск: 

Выпуск №1(5)/2003