Качественное определение глобального движения кадра с использованием векторов движения

Качественное определение глобального движения кадра с использованием векторов движения

Стрельников К.Н., Солдатов С.А., Ватолин Д.С.

МГУ им. Ломоносова, факультет Вычислительной Математики и Кибернетики,

лаборатория Компьютерной Графики kstrelnikov@graphics.cs.msu.ru, stass@graphics.cs.msu.ru, dmitriy@graphics.cs.msu.ru

Аннотация

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

1. Введение

Задача определения глобального движения кадра (Global Motion) исследуется давно. Существующие алгоритмы применяются как для сжатия [1], так и для обработки видео. Например, в задачах построения панорамного изображения [2] или стабилизации видео с дрожанием кадра [3]. Алгоритмы определения глобального движения кадра можно разделить на три группы:

1) использующие для работы особые точки (Feature);

2) использующие для работы вектора движения (Motion Vector);

3) глобальный поиск.

Алгоритмы из каждой группы имеют характерные сильные и слабые стороны.

Использование аппарата особых точек требует значительных временных затрат на выбор особых точек (Feature Selection) и на их отслеживание (Feature Tracking) [4]. Преимуществом же данного подхода является высокая надежность определения смещений. Как пример использования особых точек для определения глобального движения, можно привести алгоритм 2D Ridge Motion [3]. Надежность определения смещений при использовании векторов движения гораздо ниже, чем при использовании особых точек. Но у алгоритмов определения векторов движения (Motion Estimation) [5] есть большое преимущество - это скорость. Алгоритмы, использующие для определения глобального движения вектора движения, описаны в статьях [3,6]. Под алгоритмами глобального поиска мы

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

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

2. Фильтрация ошибочных векторов

Аппарат векторов движения (Motion Estimation) давно и очень активно

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

Рисунок 1. Вектора движения для 3-его кадра из видео последовательности «flower»

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

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

• error (х, у) - ошибка приближения (сумма абсолютных разностей пикселей блока

в позиции (х, у) и сопоставленного ему блока из предыдущего

кадра);

• disp(х, у) - дисперсия блока в позиции (х, у);

• dev( х, у) - среднеквадратичное отклонение вектора от четырех соседних

векторов:

devx у =1 • ^(mv(х, у)X - mv(х, у)X J + (mv(х, у)г - mv(х, у) f

4 i=-1;1 j=-i;i

mv(х, у)X, mv(х, у)г - проекции вектора движения. Мы предлагаем функцию доверия векторам движения, задаваемую формулой (l), которая позволяет получить адекватное значение достоверности вектора (belief ).

V1

belief(х, у) =

a • error

Ъ_

disp( х, у) а, Ъ, с - параметры.

Опытным путем было установлено, что наилучший результат достигается при следующих значения параметров: а=0.25; Ъ=32; с=1.

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

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

Наша задача минимизировать погрешность, связанную с недостатками векторов движения, поэтому далее будем использовать только вектора для которых belief (x, y) > T (некоторого порога).

кадр с векторами движения

дисперсии блоков

ошибка приближения блоков

среднеквадратичное отклонение

функция доверия векторам движения Рисунок 2. Определение достоверности векторов движения

3. Определение глобального движения кадра

Имея информацию о движении фрагментов кадра в виде векторов движения,

можно определить, как двигался весь кадр в целом. Глобальное движение кадра

можно аппроксимировать разными моделями. Мы определяем глобальное движение между кадрами 11 и 12, как преобразование вида (2).

5 • cosр - 5 • smр

ч5 • Smр 5 • СОЭ^ у

у1

+

V Ь У

= F

Где (х ; у ) - точки кадра 11, а (х ; у ) - соответствующие точки кадра 12. а, Ь, 5,ф -параметры модели: сдвиг по горизонтали, сдвиг по вертикали, увеличение и поворот.

Задача определения глобального движения сводится к минимизации функции от четырех параметров (3).

F (а, Ь, 5, ф) = ^

(5 • cos ф • х11,] - 5 • sin ф • у + а - х21,] )2 (5 • sin ф • х11,] + 5 • COS ф • у11,] + Ь - у2/,] )2

+

3.1. Определение увеличения

Важно максимально точно определить значение параметра 5, так как он

может вносить наибольшую погрешность в модель. Опишем наш алгоритм определения значения параметра 5 . Заметим, что для двух векторов задача об определении параметра 5 решается очень просто.

Рисунок 3. Определение параметра 5 для двух векторов

Возьмем два вектора, приведенных на рисунке 3. Для них справедлива формула (4).

V у,- у

Г51 2 • С08 ( - 51 2 • (Л V512 • ( 512 • С08(

х, а

+ V Ь у

V у, у

, = 1,2

Проведя несложные вычисления, получаем формулу (5), определяющую значение параметра 5.

S1,2

UX2 - Х1 )2 +(У2 - У )2 Далее из множества достоверных векторов выбираем N произвольных. Для каждого выбранного вектора Vn (n е 1..N) определяем параметр zn, который задает значение увеличения для конкретного вектора движения. Для этого из множества достоверных векторов выбираем произвольные М векторов mvm (m el.M).

Используя формулу (5) вычисляем набор значений sn m для векторов Vn и mvm, где m el.M. И определяем zn по формуле (6), как медиану от набора значений sn m.

zn = median

m el.. M

Получив значения параметров zn (п е 1..Ы), определяем 5 аналогично формуле (6), как медиану от набора значений zn.

Некоторые вектора могут соответствовать движущимся или более близким к камере объектам, как на рисунке 4. Их нельзя использовать при определении движения кадра, так как они будут вносить ошибку.

кадр с векторами движения параметр 2 для всех векторов

Рисунок 4. Дополнительная фильтрация векторов

Такие вектора можно отбросить, проведя фильтрацию по найденным для них значениям zn. Фильтрация осуществляется следующим образом: из множества векторов Vn (n е 1..N) оставляем 90% векторов VFk (k е 1..K,K < N) для которых

значение параметра z мало отличается от значения параметра 5 для всего кадра.

3.2. Определение угла поворота и сдвигов вдоль осей координат

Теперь определим оставшиеся параметры модели. Для этого минимизируем

значение функции потерь F(a, Ъ, р), задаваемой формулой (7).

(5 • cosp^VFX\ - 5 • sin (p-VFY 1k + a - VFX2 k )2 + ((5 • sin p • VF X 1k + 5 • cosp • VFy 1k + Ъ - VFy 2 k )2

• VFX1, VFY1 -координаты начала вектора;

• VFX 2, VFY 2 - координаты конца вектора.

Для этого нужно продифференцировать выражение (7) по каждому параметру, прировнять результат к нулю и решить полученную систему из трех уравнений. В результате, получим выражения (8-10) для определения параметров a,Ъ и р.

F (a Ъ,р) = Y

ke[1;K ]

f Г "1 2 Г "1 2 Л

р = arccos K • YVFX2k 2 + K Yvfy 2 k2 - YVFX 2 k - YVFY 2 k

ke[1;K ] ke[1;K ] ke[1;K ] _ ke[1;K ] _ У

' Y/FX 1k • Y/FX2k + XVFX1k • Y/FY2k - XVFY1k • Y/FX2k + Y/F"k • Y^2k

ke[1;K ] ke[1;K ] ke[1;K ] ke[1;K ] ke[1;K ] ke[1;K ] ke[1;K ] ke[1;K ]

- K • XVFX1k •VFX2k - K • XVFX1 k •VFY2k + K • YVFX1k ^VFY2k - K • %VFY1 k •VF^k

ke[1;K ] ke[1;K ] ke[1;K ] ke[1;K ]

1

a = — K

Ъ = !•

K

f

YVFX2k -5 • cosp• XVFX V + 5 • sinp • XVFY \

yke[1;K ] ke[1;K ] ke[1;K ]

YVFY2k -5• sin(• YVFY1k -5• cosp• YVF

л

У Л

y ke[1;K ] ke[1;K ] ke[1;K ]

На рисунке 5 представлена полная схема работы алгоритма.

+

5

Рисунок 5. Схема алгоритма определения глобального движения 4. Результаты

Сравним предложенный нами алгоритм с определения параметров предложенной модели движения и метод наименьших квадратов без предварительной фильтрации ошибочных векторов. Для сравнения качества работы, приведем примеры панорамы, построенной по найденным параметрам движения. Алгоритм построения панорамы использовался один. Из рисунка 6 видно, что предложенный алгоритм значительно превосходит конкурента по точности определения параметров движения.

метод наименьших квадратов

предложенный алгоритм Рисунок 6. Сравнение алгоритмов

5. Заключение

Предложенный алгоритм с высокой точностью определяет глобальное движение кадра, описываемое моделью (2). Также достигнута высокая скорость рабаты. Алгоритм позволяет обрабатывать 60 кадров видео формата 352x288 в секунду на Pentium 4 1.6GHz. Алгоритм можно с успехом применить при решении соответствующих задач. Например, для построения панорамного изображения или стабилизации видео.

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

[1] Y.Keller, A.Averbuch. "Fast Global Motion Estimation for MPEG-4 Video Compression". PACKET VIDEO 2003, April 2003.

[2] A.Bartoli, N.Dalal, B.Bose, R.Horaud. "From Video Sequences to Motion Panoramas". IEEE Workshop on Motion and Video Computing, December 2002, pp. 201-207.

[3] Kwong Kin Wah Eric. "Video Stabilization Algorithms". ELEC 533 Project Report, spring 2003

[4] Shi, J., Tomasi, C. "Good Features to Track". IEEE Conference on Computer Vision and Pattern Recognition, pp. 593-600, 1999

[5] G. de Haan, "Progress in motion estimation for video format conversion". IEEE Transactions on Consumer Electronics, Vol. 46, No. 3, Aug. 2000, pp. 449-459.

[6] Irani M., Rousso B., Peleg S. "Recovery of Ego-Motion Using Image Stabilization". Computer Vision and Pattern Rocognition '94, pp. 454-460, 1994

[7] A.Litvin, J.Konrad, W.C.Karl. "Probabilistic Video Stabilization Using Kalman Filtering and Mosaicking". Proceedings of SPIE Conference on Electronic Imaging, 2003.