(по цифровому вещанию) Dvorkovich_V_Cifrovye_videoinformacionnye_sistemy

Глава 12. Методы анализа и компенсации движения

Как правило, используют квадратичную меру D(Δb) = (Δb)2 или абсолютную меру D(Δb) = | b|, причем последняя предпочтительна с точки зрения экономии вычислительной мощности.

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

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

Рис. 12.1. К анализу движения: а и б — опорный и текущий кадры, в — разностный сигнал без учета компенсации движения, г — вектора движения

На рис. 12.1 и 12.2 приведены иллюстрации результатов анализа и компенсации движения с различной точностью:

–рис. 12.2а, б — опорный кадр (в котором производится поиск эквивалентных блоков) и текущий кадр (движение блоков которого анализируется) соответственно;

–рис. 12.2в — прямой разностный сигнал текущего и опорного кадров полученный без учета движения (нулевые вектора движения);

–рис. 12.2г — схема векторов движения блоков текущего кадра;

12.1. Основные методы анализа движения

Рис. 12.2. Разностные сигналы с компенсацией движения с точностью до полпиксела —

аи с точностью до действительного значения — б

–рис. 12.2а — разностный сигнал текущего и опорного кадров, полученный при компенсации движения с точностью до половины пиксела;

–рис. 12.2б — разностный сигнал текущего и опорного кадров, полученный при компенсации движения с дальнейшим уточнением векторов движения.

Из сравнения изображений на рис. 12.2а и б видно, что эффективная компенсация движения резко уменьшает объем информации о динамическом изображении.

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

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

Согласно стандартам MPEG все кадры видеопоследовательности делятся на 3 основных типа: I, P и B. I-кадр передается без использования предсказания движения (обычно он встречается один раз в группе кадров, и является опорным для кодирования и восстановления остальных кадров). P-кадр кодируется с предсказанием движения в одну сторону («вперед»), и для его восстановления необходим I- или другой опорный P-кадр. Для кодирования P-кадра все изображение разбивается на макроблоки размером, например, 16 × 16 пикселов, и каждому макроблоку ставится в соответствие наиболее «похожий» участок изображения из опорного кадра, сдвинутый на вектор движения. Кодером передаются только разности сигналов яркости и цветности между макроблоком и соответствующим участком изображения опорного кадра. В случае B-кадра исключение межкадровой избыточности производится с предсказанием во времени в обе стороны, для чего используются два вектора движения и два опорных кадра (I- или P-типа). Такой способ позволяет увеличить сжатие примерно в 2 раза по сравнению с кодированием, только с предсказанием во времени в одну сторону.

Глава 12. Методы анализа и компенсации движения

В обоих способах для текущего и опорного кадров необходимо определить набор векторов движения макроблоков.

12.1.1. Метод полного перебора

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

да является низкое быстродействие. Для поиска вектора движения x y

V = (V , V )

рассматривается норма разницы сигналов яркости макроблока в текущем кадре

и участка опорного кадра со сдвигом на вектор движения:

x−x0,y−y0=0,...,15

Здесь F — значение яркости, t — временной индекс кадра, (x, y) — пространственные координаты пикселов в кадре, (x0, y0) — координаты левого верхнего угла макроблока, суммирование производится по всем пикселам макроблока. Значе-

ние , для которого сумма абсолютных разностей 0 имеет наименьшее

V H H

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

Векторы движения определяются в заданной ограниченной окрестности −NVx, Vy N . Для нахождения вектора движения одного макроблока необходимо выполнить операции вычитания, взятия модуля и сложения, в сумме их количество равно 3 · 256 · (2N + 1)2 операций. На один пиксел макроблока количество операций составляет 3 · (2N + 1)2, что уже при типичном значении N = 15 равно значительной величине 3 · 103 операций/пиксел.

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

12.1.2.Логарифмический, комбинированный по двум направлениям, трехшаговый, иерархический методы

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

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

12.1. Основные методы анализа движения

Рис. 12.3. Схема поиска векторов движения в логарифмическом методе

не будет найден локальный минимум H, после чего значение вектора движения уточняется с шагом в один пиксел в окрестности этого минимума, как показано на рис. 12.3 [4.25]. На этом рисунке цифрами обозначен порядок, в котором рассматриваются кандидаты в векторе движения и вычисляется контрольная сумма H.

Методика комбинированного поиска по двум направлениям показана на рис. 12.4. В этом методе проводится полный перебор по горизонтали, начиная

сцентра макроблока, в результате чего находится точка 1, являющаяся локальным минимумом в строке. Затем поиск ведется по вертикали и находится точка 2, локальный минимум в столбце. Процедура поиска продолжается с чередованием направлений и с уменьшением диапазона поиска вплоть до нахождения конечного оптимума [4.26].

Вблизком к логарифмическому 3-х шаговом методе поиск векторов движения, как показано на рис. 12.5, ведется первоначально по всей окрестности

сшагом в 4 пиксела, затем вокруг найденного минимума — с шагом в 2 пиксела и, наконец, — с шагом в один пиксел [4.27].

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

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

ошибкам вследствие достаточно сложной зависимости . Эта функция может

H(V )

12.1.Основные методы анализа движения

12.1.3.Методы, основанные на оптическом уравнении

Идея данных методов заключается в моделировании движения в плоскости кадра стандартным уравнением в частных производных гиперболического типа, используемым в физике для описания процессов переноса различных сред [4.29]:

где F = ( ∂F∂x , ∂F∂y ) ≡ (∂xF, ∂y F ) есть пространственный градиент функции, ∂tF — производная по времени.

В этом уравнении, называемом «оптическим уравнением», под «переносимой средой» понимается яркость изображения F , а член S в правой части моделирует источник, определяющий изменения яркости, не сводимые лишь к пространственному движению. Задача состоит в определении поля векторов движения из (12.2) на основе знания сигнала яркости в двух соседних кадрах. Например, за вектор движения можно принять вектор, минимизирующий правую часть уравнения (12.2) по всей площади макроблока:

(12.4) В (12.3) и (12.4) суммирование производится по всем пикселам макроблока.

Для практического применения системы уравнений (12.4) дифференциальные операторы необходимо заменить на разностные. Простейшими формулами могут быть:

∂tF = F (x, y, t) − F (x, y, t − 1),

∂xF = (F (x + 1, y, t) − F (x − 1, y, t))/2, ∂y F = (F (x, y + 1, t) − F (x, y − 1, t))/2.

Для анализа движения предлагались также другие разностные формулы различной степени сложности на основе оптического уравнения (12.2) [4.30]. Количество операций для определения вектора движения на один пиксел можно оценить как 10Z арифметических операций (умножений и сложений), где Z — среднее количество арифметических операций, необходимое для вычисления одного значения производной в системе уравнений (12.4). Для приведенных выше простейших формул производных это составит около 17 операций на пиксел.

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

12.1. Основные методы анализа движения

Рис. 12.6. Схема поиска векторов движения по модели Маркова 1-го порядка. Цифрами обозначены: 0 — вектор движения макроблока в кадре с номером t − 1, 1 — вектор движения макроблока в кадре t, 2 — различные кандидаты на вектор движения макроблока в кадре t − 1, 3 — различные кандидаты на вектор движения макроблока в кадре t, 4 — выбранный вектор движения макроблока в кадре t, 5 — окно поиска векторов движения

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

12.1.5.Использование временной и пространственной корреляции векторов с оптимизацией возмущения битового потока

Всвязи со значительно возросшими в настоящее время потребностями кодирования и передачи видеоизображений по сетям с низкой скоростью битового потока масштаба 10–30 кбитов/с (например, при передаче видео по коммутируемым телефонным линиям или радиотелефону) были предложены алгоритмы компенсации движения, учитывающие малую величину потока [4.32, 4.33]. Оказывается, что при таких низких значениях битового потока кодирование передаваемых векторов движения может занимать до 50% всей передаваемой информации. Чтобы уменьшить эту величину, было предложено заменить критерий (12.1) на функ-

x−x0,y−y0=0,...,15

Последний в (12.7) член R > 0 представляет собой битовый размер кода, необходимый для кодирования векторов движения, λ — параметр. Идея метода заключается в поиске такой совокупности векторов движения, которая минимизирует одновременно разностный сигнал после компенсации движения и объем кода, необходимый для передачи векторов движения.

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

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

12.1.6.Метод полного перебора с преобразованием Фурье

Вработе [4.34] был предложен простой алгоритм, позволяющий ускорить поиск векторов движения в 4–5 раз. Особенностью метода является то, что найденные вектора движения точно совпадают с векторами движения, найденными методом полного перебора, т. е. в этом смысле метод можно считать точным. Рассмотрим критерий (12.1), в котором в качестве нормы разности сигналов яркости используется не модуль, а квадрат разности:

(12.8)

Первое слагаемое в правой части соотношения (12.8) не зависит от величины вектора движения и не требует минимизации. Расчет последнего слагаемого может

12.1. Основные методы анализа движения

быть существенно оптимизирован, если учесть, что для макроблока размером, например, 16 × 16 пикселов изменение значения вектора движения на один пиксел эквивалентно лишь добавлению к раннее рассчитанной сумме 16 новых и вычитанию 16 старых значений квадратов F , что требует только 2 · 16/256 = 1/8 операций на пиксел.

Наибольшую сложность представляет вычисление 2-го слагаемого в правой части (12.8), которое, тем не менее, может быть оптимизировано с использованием свертки, вычисляемой с применением Фурье-преобразования. В результате при использовании быстрого преобразования Фурье для вычисления свертки при N 1 общее количество действий на макроблок оказывается порядка 25(2N + 16)2(log2(2N + 16))/2 [4.34], что при окне поиска ±15 пикселов дает выигрыш в 5 раз по сравнению с методом полного перебора.

12.1.7. Методы фазовой корреляции

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

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

С другой стороны, главным преимуществом метода по сравнению с методом полного перебора является то, что метод может использоваться в достаточно большой области изображения, в которой происходит движение нескольких различных объектов, что позволяет существенно снизить вычислительные затраты. Если вектора движения ищутся одновременно для группы соседних макроблоков, число которых равно n · n, то количество действий на пиксел определяется главным образом числом операций на вычисление двух прямых и одного обратного Фурье-преобразований и составляет 3·10 (1+N/8n)2 log2(16n+2N ) 3·(2N +1)2, если n 1 и размер окна поиска каждой из компонент вектора движения равен ±N .

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