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

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

Таблица 12.6. Значения пикселов, выбранных в качестве опорных

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

Таблица 12.7. Значения пикселов в выбранных строках

Таблица 12.8. Значения пикселов, выбранных в качестве опорных

Таблица 12.9. Положения выбранных опорных пикселов в исходном макроблоке (опорные пикселы обозначены подчеркиванием)

12.2. Повышение эффективности анализа движения по опорным точкам

При поиске векторов движения для√выбора опорных пикселов необходимо выполнить порядка (16 · (16 + 1) · 16/2 + M · (16 + 1) · 16/2)/256 ≈ 10 обращений к одному пикселу макроблока, где M — число опорных пикселов (в данном случае M = 16), для поиска вектора движения с использованием SAD1 необходимо выполнить порядка 256M 3 · (2N + 1)2 операций. При окне поиска N > 10 количество операций, необходимых для поиска опорных пикселов, пренебрежимо мало по сравнению с числом операций, необходимых для вычисления SAD1 и поиска вектора движения. Поэтому достигается ускорение поиска векторов приблизительно в 256/M = 16 раз.

Эффективность этого способа поиска векторов движения иллюстрируется рисунках 12.17а–г. На рис. 12.17а показаны векторы движения, полученные стандартным эталонным алгоритмом с использованием всех пикселов макроблока. На рис. 12.17б, в приведены векторы движения, определенные в соответствии с описанными выше двумя вариантами обработки. Как видно из этих рисунков, векторы движения в большинстве случаев совпадают. Чтобы дать количественную оценку способа, рассмотрим результаты кодирования динамической последовательности кадров (табл. 12.10) в рамках стандарта MPEG-2 с использованием разработанного алгоритма поиска движения. Поскольку в рамках стандарта возможно использование векторов движения с точностью до половинных значений пикселов, рассмотрим два случая кодирования — без уточнения полученных векторов, и с уточнением в пределах ±0,5 пиксела с использованием интерполяции между пикселами. Для уточнения использована контрольная сумма (12.1) со всеми 256 пикселами макроблока. Уточнение векторов до половины пиксела требует порядка 3 · 9 = 27 дополнительных операций на каждый пиксел. Как следует из анализа результата кодирования, предложенные способы дают существенное ускорение поиска векторов движения (в 16 раз при 16 опорных точках), при этом коэффициент сжатия ухудшается не более 1–3% в случае использования точности векторов до 0,5 пиксела и 4–10% при точности векторов в один пиксел.

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

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

F (d)(x, y) = 14 (F (2x, 2y) + F (2x + 1, 2y) + F (2x, 2y + 1) + F (2x + 1, 2y + 1)).

Здесь F (d)(x, y) — значение пиксела после передискретизации. Отсчеты пикселов макроблока, показанного на рис. 12.15 и 12.16, после передискретизации будут иметь значения, представленные в табл. 12.11.

Согласно одному из вариантов способа вычисления векторов движения, передискретизированный макроблок размером 8 × 8 пикселов делят на несколько

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

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

Рис. 12.17. Векторы движения, найденные стандартным способом — а и тремя вариантами эффективной реализации способа — б, в и г соответственно

Таблица 12.10. Размер кода MPEG-2 (в байтах) для последовательности «Сад цветов», 97 кадров с разрешением 640 × 480 пикселов

Таблица 12.11. Значения пикселов в выбранном макроблоке после передискретизации

12.2. Повышение эффективности анализа движения по опорным точкам

Таблица 12.12. Разбиение макроблока на участки и порядок выбора опорных пикселов

В процессе минимизации нормы SAD1 в окне поиска ±N/2 пикселов по передискретизированным изображениям определяют K векторов V1d, V2d, . . . , VKd, дающих наименьшие значения SAD1:

Min = SAD1(V1d) SAD1(V2d) SAD1(V3d) ...

После нахождения наилучших векторов V1d, V2d, V3d, . . ., соответствующих передискретизированным опорному и текущему кадрам, значения векторов увеличивают в соответствии с отношением разрешений исходного и передискретизированного кадров, в данном случае — в 2 раза. Далее в небольшой окрестности (например, ±1 пиксел) от каждого из полученных значений векторов (2·V1d, 2·V2d, 2· V3d,. . . ) производят минимизацию контрольной суммы и определяют наилучший вектор движения. Данный вектор принимается за конечный вектор движения макроблока в случае использования точности векторов, равной 1 пикселу.

При использовании точности векторов движения, равной половине пиксела, как это, например, реализуется в стандарте MPEG-2, последний найденный выше вектор уточняется в окрестности ±0, 5 пиксела, либо сразу в малых окрестностях (например, ±1 пиксел) векторов 2·V1d, 2·V2d, 2·V3d,. . . с точностью до 0,5 пиксела.

Для поиска векторов движения на этапе их оценки в передискретизированном кадре число операций на один пиксел передискретизированного кадра составляет 3 6416 (2 · NZ + 1)2, где Z — отношение исходного и передискретизированного разрешений (в данном случае Z = 2), или 14 3 6416 (2 · NZ + 1)2 на пиксел в кадре исходного разрешения.

Уточнение векторов движения в окрестности каждого из найденных векторов занимает небольшое количество операций — порядка 3K(2·1+1)2 на пиксел в кадре исходного разрешения, где K — количество наилучших векторов, и не зависит

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

от N . При K 3 и N > 10 последним числом можно пренебречь. В этом слу-

чае ускорение по сравнению с эталонным способом полного перебора составляет

14 3 6416 (2 · NZ + 1)2/3 6416 (2 · NZ + 1)2 ≈ 16Z2 = 64 при Z = 2.

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

При этом вычисляют среднее значение выбранных пикселов макроблока:

выбранных точек в соответствующих

участках макроблока

Затем вычисляют модули разностей X(x, y) = |F (x, y, t) − Fср|, где (x, y) — координаты выбранных точек в соответствующих участках макроблока, и контрольную сумму вычисляют последовательно по координатам (x, y), для которых величины X(x, y) располагаются в убывающей последовательности.

В случае если текущий выбранный вектор x y не соответствует

V = (V , V )

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

Эффективность способа анализа движения по этому методу иллюстрируется в табл. 12.14. На рис. 12.17г приведены вектора движения, полученные с использованием способа при K = 3, а в табл. 12.14 даны результаты кодирования тестовой динамической последовательности кадров в рамках стандарта MPEG-2 (K=1, 2 и 3). Из таблицы следует, что этот способ при Z = 2 уступает по коэффициенту сжатия наилучшему эталонному способу перебора по всем пикселам не более 1% уже при K=2 и 3, и превосходит другие способы, не использующие передискретизацию. При этом коэффициент ускорения анализа движения по сравнению с эталонным способом составляет 64 раза при Z = 2.

Таблица 12.14. Размер кода MPEG-2 (в байтах) для последовательности «Сад цветов», 97 кадров с разрешением 640 × 480 пикселов (с фильтрацией)

Заметим, что использование фильтрации улучшает результат. Например, если бы передискретизация проводилась без фильтрации, а только за счет прореживания по формуле F (d)(x, y) = F (2x, 2y), то результат по коэффициенту сжатия был бы хуже на 1–2% (табл. 12.15).

12.3. Дополнительные возможности компенсации движения деталей

Таблица 12.15. Размер кода MPEG-2 (в байтах) для последовательности «Сад цветов», 97 кадров с разрешением 640 × 480 пикселов (с прореживанием)

Принципиальной особенностью рассмотренных выше методов является то, что улучшение межкадрового сжатия достигается за счет усложнения модели движения. После компенсации движения в рамках стандарта МРЕG-2 внутрикадровое сжатие приводит фактически к изменению истинных значений пикселов изображения (обусловленных квантованием коэффициентов спектра) без изменения положения этих пикселов в кадре. С другой стороны, можно незначительно изменить содержание кодируемого кадра таким образом, чтобы данное изменение было незаметно для глаза и улучшало компенсацию движения в рамках той или иной используемой модели. При этом дополнительное сжатие может быть достигнуто за счет небольших (в пределах долей пиксела) пространственных смещений деталей исходного изображения [4.45].

Поясним сказанное примером. На рис. 12.18 изображен одномерный импульсный сигнал, движущийся с постоянной скоростью вдоль оси ординат. Предположим, что данный сигнал должен быть закодирован и передан в рамках стандарта МРЕG. При дискретности передаваемого вектора движения после компенсации движения значение разностного сигнала отлично от нуля (кривая 4), и требуется определенное количество битов для передачи разностного сигнала. С другой стороны, сдвинутый сигнал в пределах долей пиксела (кривая 3) визуально мало отличается от исходного и не требует передачи дополнительной информации после компенсации движения. Поэтому выгоднее передать сдвинутый в пределах долей пиксела сигнал (кривая 3) вместо исходного сигнала (кривая 1).

Можно выделить две принципиально различные возможности пространственной передискретизации элементов изображения в предлагаемом способе:

–любым способом в пределах чувствительности человеческого зрения к небольшим пространственным перемещениям пикселов;

–определенным способом, который отвечает некоторой физической модели движения.

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

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

Рис. 12.18. Компенсация движения одиночного импульса: 1 — значение сигнала в текущий момент времени, 2 — значение сигнала в предыдущий момент времени, 3 — сдвинутое положение сигнала, обеспечивающее нулевой сигнал после компенсации движения, 4 — значение сигнала после компенсации движения

сточностью до целых значений пикселов

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

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

кретным значением вектора движения (рис. 12.19). В таком понимании приходим к новой модели кад-

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

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

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

12.3. Дополнительные возможности компенсации движения деталей

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

Основные уравнения

Рассмотрим видеопоследовательность кадров, содержащую кадры В-типа стандарта MPEG. В случае кодирования макроблока В-кадра на кодере вычисляется величина разности

при предсказании движения в обе стороны; Yx,y(n) — значение сигнала яркости пиксела в макроблоке в кадре с номером n, имеющего пространственные координаты (x, y); Xx,y(n) — предсказанное значение пиксела с учетом компенсации движения;

— расстояние до опорного кадра; (Vx, Vy ) — координаты вектора движения. При кодировании с векторами движения с точностью до полпиксела значения

(Vx, Vy ) вычисляются с помощью линейной интерполяции.

Будем считать, что вектор движения макроблока известен и определен, например, методом полного перебора и, соответственно, значения Xx,y(n) вычислены.

(n)

Сущность предлагаемого метода сводится к замене истинного значения Yx,y некоторым другим значением Yx,y(n), соответствующим небольшому смещению изображения во времени. Целью замены является уменьшение модуля разности Cx,y. Будем считать, что значения пикселов Yx,y(n) можно получить исходя из значений Yx,y(n) с использованием интерполяции между пикселами:

где Vx, Vy — координаты вектора небольшого смещения макроблока. Величи-

x,y

Суммирование здесь производится по всем пикселам макроблока.

Пусть ориентация вектора соответствует случаю, изображенному на ри-

V

сунке 12.20, на котором обозначено Y0 = Yi,k , Y1 = Yi+1,k, Y2 = Yi,k+1, Y3 = = Yi+1,k+1. Для вычисления промежуточного значения сигнала яркости в точке

будем использовать интерполяцию по четырем соседним точкам. Предпола-

V

12.3. Дополнительные возможности компенсации движения деталей

В формулах (12.15)–(12.17) независимыми величинами являются только координаты вектора (x1, x2), по которым необходимо произвести минимизацию в (12.14). С другой стороны, в (12.18) присутствует новый параметр q, поэтому минимизацию можно проводить по трем независимым параметрам (x1, x2, q). Нетрудно видеть, что в общем случае якобиан преобразования (12.19)

∂(α1, α2, α3)/(x1, x2, q) = 0,

поэтому величины (α1, α2, α3) являются независимыми и, следовательно, минимизацию можно проводить по величинам (α1, α2, α3).

После нахождения оптимальных значений (α1, α2, α3) необходимо вычислить, какому вектору движения они соответствуют. Формулы обратного преобразования имеют вид:

Координаты вектора движения (x1, x2) определяются простыми выражениями (12.23), (12.24).

Необходимо наложить условие, чтобы вектор движения находился внутри рассматриваемой области. Величины Vx, Vy не должны превышать доли пиксела, 0 x1, x2 p, откуда

где p — диапазон допустимого размера смещения элементов изображения при

передискретизации, 0 p 1/2. Величины (α1, α2, α3) находятся из условия:

H = (X0i − Y0i − α1(Y1i − Y0i) − α2(Y2i − Y0i) − α3(Y3i − Y0i))2 min.

(12.28) В (12.28) X0 = Xi,k — значение сигнала яркости в текущем кадре суммирование производится по всем точкам макроблока (индексу i).

Необходимыми условиями минимума являются:

∂H/∂α1 = ∂H/∂α2 = ∂H/∂α3 = 0,

откуда получаем линейную систему из трех уравнений для определения (α1, α2, α3):

Система (12.29)–(12.31) решается стандартными методами линейной алгебры. В вырожденном случае (детерминант матрицы равен нулю) передискретизацию проводить не будем (положим α1 = α2 = α3 = 0). Поскольку вектор смещения может иметь 4 различные ориентации, необходимо выбрать наилучшее

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

замена значений попиксельной яркости согласно (12.19).