7.2.2.1. Оценка движения на основе блоков

Меры энергии. Целью компенсации движения является минимизация энергии квантованных коэффициентов преобразования остаточных данных, получающихся при вычитании прогнозной области из исходной. Энергия преобразованного блока, очевидно, зависит от энергии остаточного блока (получающегося до преобразования), поэтому кодер при компенсации движения стремится обнаружить в ссылочной области блок, больше других «похожий» на текущий сжимаемый блок, который минимизирует энергию остаточного блока. Обычно процедура такого поиска вычисляет энергию остатков для большого числа различных смещений блоков на ссылочной области. Выбор меры энергии значительно влияет на вычислительную сложность алгоритма поиска, а также на точность процесса оценки движения. Уравнения (7.1), (7.2) и (7.3) задают три возможные меры энергии, а именно MSE (Mean Square Error, среднеквадратическое отклонение), МАЕ (Mean Absolute Error, среднее абсолютное отклонение) и SAE (Sum of Absolute Errors, сумма абсолютных отклонений). Блок сэмплов компенсации движения имеет размеры , а величины  и  обозначают соответственно сэмплы текущего и ссылочного блока с координатами .

                           (7.1)

                              (7.2)

                     (7.3)

По всей видимости, самой популярной мерой энергии остатков является величина SAE в силу простоты ее вычисления. Справочная программа для Н.264 [5] использует в прогнозах меру SA(T)D -  сумму абсолютных разностей преобразованных остаточных данных (в обеих модах intra и inter). Преобразование остатка для каждого смещения блока увеличивает объем вычислений, но при этом улучшается мера энергии. Поскольку используется простое преобразование, не применяющее операцию умножения, вычислительная сложность возрастает не намного.

В предыдущем примере наилучшим вектором компенсации движения служил вектор (+2, 0). Минимумы мер MSE и SAE в этой точке позволяют надеяться на то, что соответствующее смещение дает также минимум энергии квантованных разностей. Вектор движения следует послать декодеру, однако чем он больше, тем больше бит потребуется на его кодирование по сравнению с малым вектором (см. гл. 3). Поэтому, возможно, будет лучше уменьшить вектор движения до (0,0). Для этого достаточно будет вычесть константу из MSE или SAE в точке (0,0). Более изощренный метод заключается в нахождении вектора, разрешающего соответствующую задачу условной оптимизации [6]. Справочная модель кодека [5] стандарта Н.264 использует параметры стоимости для каждого кодируемого элемента (MVD, моду прогноза и т.п.) при определении минимальной общей стоимости прогноза компенсации движения.

Рис. 7.3. Мера энергии MSE.

Рис. 7.4. Мера энергии МAЕ.

Рис 7.5. Мера энергии SAE.

Рис. 7.6. Полный перебор (растровое сканирование).

Возможно, что вычислять SAE (или МАЕ, или MSE) придется не для всех смещений блока на ссылочной области. Обычный ускоренный метод заключается в прекращении вычислений, как только происходит превышении предыдущего минимального значения SAE. Например, после вычисления каждой внутренней суммы в формуле (7.3) () кодер может сравнивать общую сумму SAE с предыдущим минимумом. Если общая сумма, вычисленная к этому моменту, превосходит предыдущий минимум, вычисления обрываются (нет смысла продолжать суммирование, раз результат заведомо будет иметь большее значение SAE).

Полный перебор. Метод полного перебора при оценке движения предполагает вычисление меры SAE по формуле (7.3) для каждого вектора смещения окна поиска (±S сэмплов вокруг центра текущего макроблока). Полный перебор гарантированно обнаруживает минимальное значение SAE (или МАЕ, или MSE) в окне поиска, однако этот метод имеет достаточно высокую вычислительную сложность, поскольку энергетическую меру (т.е. сумму (7.3)) придется вычислять для каждого из  смещений.

На рис. 7.6 приведен пример стратегии полного перебора. Первый блок помещается в верхний левый угол поискового окна (координаты вектора смещения (-S,S)), и дальнейший поиск осуществляется в растровом порядке до полного исчерпания всех блоков. В типичной видеопоследовательности большинство векторов компенсации движения концентрируются вокруг вектора (0,0). Вычисления по алгоритму полного перебора можно ускорить, если начать поиск со смещения (0,0) и двигаться по спирали вокруг этой точки (см. рис. 7.7). Если использовать метод раннего прерывания вычислений (см выше), то происходит заметное ускорение всей процедуры за счет сокращения числа вычислений по мере удаления от начальной точки (0,0).

Рис. 7.7. Полный перебор (сканирование по спирали).

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

Популярный метод поиска «в три шага» TSS (Three Step Search) или более общий алгоритм NSS поиска «за N шагов» проиллюстрирован на рис. 7.8. Мера SAE вычисляется для смещения (0, 0) (центр рисунка), а также еще для восьми смещений  (для окна поиска в  сэмплов). На рисунке число S равно 7 и первые девять смещений обозначены цифрой 1. Смещение, имеющее минимальное SAE, выбирается в качестве нового центра поиска, к которому добавляется 8 смещений на расстоянии в два раза меньшем от предыдущего центра (все они помечены на рисунке цифрой 2). Опять «наилучшее» из этих смещений выбирается за центр, и весь алгоритм повторяется до тех пор, пока нельзя будет делать дальнейшее деление. Метод TSS работает значительно быстрее алгоритма полного перебора ( смещений в TSS по сравнению с  смещениями при полном переборе), но TSS (как и другие алгоритмы быстрого поиска) не так эффективен, как метод полного перебора. График SAE на рис. 7.5 имеет единственную точку минимума, и TSS, вероятно, найдет эту точку правильно, но график SAE для блока со сложными деталями и/или разными движущимися компонентами может иметь несколько точек локального минимума (см., например, рис. 7.9). Алгоритм полного перебора всегда отыщет среди этих точек глобальный минимум, а метод быстрого поиска может попасть в точку локального минимума, дающую лишь подоптимальный результат.

Рис. 7.8. Поиск в три шага.

Были предложены и другие алгоритмы быстрого подоптимального поиска, например логарифмический поиск, иерархический поиск, перекрестный поиск и одномоментный поиск [7 - 9]. Для каждого такого метода его эффективность можно определить, сравнивая с алгоритмом полного перебора. Подходящими критериям сравнения служат степень сжатия (насколько хорошо он минимизирует объем остатков после компенсации движения) и вычислительная сложность (какая часть вычислении сокращена по сравнению с полным перебором). Другие критерии могут также оказаться полезными. Например, некоторые «быстрые» алгоритмы типа иерархического поиска лучше других подходят при аппаратных реализациях.

Рис. 7.9. График SAE с несколькими локальными минимумами.

Поиск по ближайшим соседям NNS (Nearest Neighbors Search) [10] является быстрым алгоритмом оценки движения, имеющим малую вычислительную сложность, который по степени сжатия приближается к алгоритму полного перебора в рамках простого профиля MPEG-4. В стандарте MPFG-4 Visual каждый вектор движения макроблока или блока кодируется с помощью разностей. Делается прогноз вектора (на основе ранее закодированных векторов соседних блоков), и разность (MVD) между вектором и его прогнозом кодируется и передается. Алгоритм NNS использует это свойство, отдавая предпочтение векторам движения, которые близки к прогнозируемому вектору (т.е. минимизируется MVD). Сначала SAE вычисляется для смещения (0,0). Затем центр поиска помещается в точку спрогнозированного вектора, и SAE вычисляется для соседних смещений из окрестности в форме ромба [они помечены как 1 на рис. 7.10). Следующий шаг зависит от того, какому вектору соответствует самая низкая величина SAE. Если это вектор (0,0) или центр ромба, то поиск прекращается. Если таким вектором является вершина ромба (на рисунке она обведена жирным кружком), то он становится центром нового ромба, и поиск продолжается. В этом примере процедура обрывается после обнаружения векторов, помеченных цифрой 3. Сдвиг в сторону уже спрогнозированного вектора дает хорошие результаты по степени сжатия, которые близки к показателям метода полного перебора, но при этом этот метод имеет малую вычислительную сложность.

Рис. 7.10. Поиск по ближайшим соседям.

Подпиксельное оценивание движения. В гл. 3 было показано, что лучшую компенсацию движения можно построить, допустив использование нецелых смещений (векторов движения) на ссылочном кадре. Например, голова женщины необязательно переместится на целое число пикселов от предыдущего кадра (рис. 7.2) к текущему кадру (рис. 7.1). Повысив точность шага смещения (полпиксела в простом профиле MPEG-4, четверть пиксела в расширенном простом профиле и в Н.264), можно добиться лучшего совпадения блоков и тем самым сократить энергию остаточного блока компенсации движения. Полученный выигрыш компрометируется необходимостью пересылать нецелые векторы движения (повышается число бит, требуемых для представления таких величин), а также повышением сложности вычислений при подпиксельном оценивании и компенсации движения.

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