Анализ современных методов сжатия цифровых

видеопотоков

Злобин А. С. (zlobin@rt.mipt.ru)

Кафедра радиотехники МФТИ

1. Используемые сокращения

Jpeg - Joint Photographic Experts Group стандарт для хранения и сжатия цифровых изображений.

Mpeg - Moving Picture Experts Group стандарт используемый для кодирования аудио-, видеоинформации.

VOP - Video Object Plane (объектная видеоплоскость)

АС - Alternative Component (переменная составляющая)

DC - Direct Component (постоянная составляющая)

RLE - Run-Length Encoding (кодирование длин серий - метод сжатия, при котором последовательная серия одинаковых элементов заменяется на два символа: элемент и число его повторений)

PSNR - Power Signal-to-Noise Raito (отношение сигнал/шум по мощности)

RGB - способ хранения изображений, при котором каждый пиксел хранится в виде трех компонент: R- красная, G - зеленая, В - синяя.

Y Cr Cb - способ хранения изображений, при котором каждый пиксел хранится в виде трех компонент: Y- яркостная, Cr - хроматическая красная, Cb -хроматическая синяя.

2. Введение

В последнее время алгоритмы сжатия видеоданных получили большое распространение, в связи с чем количество алгоритмов стремительно растет и все чаще и чаще возникает вопрос выбора того или другого алгоритма сжатия. Методы сжатия видеоданных можно разделить на три типа: Jpeg- подобные, wavelet-подобные и фрактальные. Фрактальные методы сжатия не получили широкого распространения в связи со сложностью алгоритма и поэтому не рассматриваются в данной статье. Из семейства Jpeg-подобных алгоритмов были выбраны два наиболее часто используемых алгоритма: МJpeg (Motion Jpeg) и Mpeg4. Для исследования wavelet-подобных методов сжатия был выбран wavelet-кодек реализующий последовательное сжатие кадров видеопотока по wavelet-алгоритму (wavelet, вейвлет - небольшая волна). В данной статье дано краткое описание наиболее распространенных алгоритмов сжатия и производится сравнение этих алгоритмов между собой. Приведена оценка их эффективности.

3. Алгоритм MJpeg

Алгоритм MJpeg не стандартизован. Данный алгоритм основан на сжатии каждого кадра по отдельности с использованием сжатия по алгоритму Jpeg [1]. После выполнения

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

Известно, что человеческий глаз обладает большей чувствительностью к изменению яркости, нежели к изменению цвета. Поэтому при кодировании изображений с использованием Jpeg-подобных алгоритмов используется представление картинки не в RGB-формате, а в формате Y Cr СЬ [1]. При этом компоненты хроматического красного и хроматического синего усредняются, что позволяет уменьшить объем данных в 1.5 раза.

При кодировании изображение разбивается на блоки размером 8x8 пикселов, и дальнейшие операции выполняются над каждым из этих блоков. Кодирование производится в три фазы:

1. Быстрое преобразование Фурье.

2. Квантование.

3. Сжатие.

Преобразование Фурье осуществляет перевод сигналов из пространственной области в частотную. Для блока размером 8x8 пикселов оно задается следующим выражением [1]:

4 x=0 y=0 v 16 ! v 16 !

где a(u), a(v) = -1=, при u,v = 0 и a(u), a(v) = 1, при u,v 0

i(x,y) - значения пикселов (пространственная область),

l(u,v) - амплитуда спектральных составляющих (частотная область).

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

Сжатие осуществляется в три стадии. Сначала производится зигзаг-сканирование, как показано на рис.1. Эта операция по упорядочению коэффициентов Фурье необходима для того, чтобы получить возможно более длинные последовательности нулей, поскольку такие последовательности лучше сжимаются. Затем происходит RLE-сжатие, при котором каждый коэффициент кодируется двумя числами: первое число показывает, сколько нулевых элементов рис> 1. Схема зигзаг-сканирования предшествует данному коэффициенту, а второе

значение этого коэффициента. Затем производится либо сжатие по Хаффману [2], либо арифметическое кодирование [3]. Ниже при сравнении данного метода кодирования с другими алгоритмами применено сжатие по Хафману с использованием статических таблиц.

4. Алгоритм Mpeg4

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

В стандарте Mpeg4 так же, как и в стандарте JPEG, видеоданные представляются в формате Y Cr Cb [5]. Кодирование видеопотоков производится с использованием объектных видеоплоскостей (VOP-плоскостей) [6]. При сжатии видеопотока каждое изображение можно представить в виде суперпозиции VOP-плоскостей, которые в дальнейшем кодируются независимо друг от друга. VOP-плоскость содержит определенную часть кадра, хранящую некоторую визуально различимую область исходного изображения. Поскольку на данный момент не существует эффективных методов разделения изображений на отдельные объекты, чаще всего используется всего одна видео-плоскость, целиком содержащая исходное изображение. При сжатии видеоплоскость разделяется на последовательность кадров. В стандарте Mpeg4 используются три типа кадров: I и Р и В .

I кадры кодируются целиком, без использования информации о других кадрах. Р кадры кодируются с использованием информации о предыдущих I и Р кадрах. В кадры используют информацию как о предыдущих, так и о последующих I и Р кадрах.

Теперь рассмотрим непосредственно кодирование кадров. Кадры разбиваются на макроблоки. Для Y-компоненты макроблоки имеют размер 16x16 пикселов, а для Сг и СЬ компонент размер макроблоков равен 8x8. Макроблоки бывают двух типов: intra-макроблоки и inter-макроблоки. Макроблоки разных типов кодируются по-разному. I кадр состоит только из intra-макроблоков, а Р кадр содержит и inter и intra-макроблоки. Макроблоки Y-компоненты разбиваются на подблоки размером 8x8, и кодирование происходит в следующей последовательности:

Y- Y

Рассмотрим кодирование intra-макроблоков для Сг и -компонент и подблоков Y-компоненты. Сначала производится преобразование Фурье точно такое же, как описано выше в стандарте Jpeg. После этого производится квантование коэффициентов Фурье. Старший из коэффициентов Фурье отражает среднее значением яркости в данном блоке, поэтому его называют DC-коэффициентом. Поскольку чаще всего яркость соседних блоков одинакова, кодирование DC-коэффициента целиком является избыточным, достаточно закодировать разность между текущим и одним из предыдущих блоков. Подобное предсказание производится и для старших АС-коэффициентов. Если при предсказании количество информации не уменьшается, то блок кодируется без учета предсказания. Если АС-предсказание осуществляется, то - в зависимости от того, по отношению к какому блоку оно производится, - выбирается один из трех возможных методов зигзаг-сканирования. После этого выполняется RLE-сжатие и сжатие по Хаффману так же, как и в стандарте Jpeg.

Для inter-макроблоков сначала производится операция компенсации движения [6], и только после этого они кодируются. Для каждого макроблока используется один вектор скорости; при этом предсказание осуществляется с точностью до 0.125-0.5 пиксела. Для нахождения вектора скорости производится поиск наиболее похожего места на предыдущих I и Р кадрах. Поиск векторов движения производится только для Y-компоненты, для Сг и -компонент вектор движения получается путем деления пополам вектора для компоненты

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

5. Wavelet

В основе Wavelet-подобных алгоритмов сжатия лежит теория вейвлет преобразования [7]. При Wavelet преобразовании производится разложение сигнала по базисным функциям. В отличие от преобразования Фурье в качестве базовых функций используются не косинусы, а вейвлеты. Вейвлеты это хорошо локализованные солитоноподобные функции. На рисунке 2 представлены четыре семейства вейвлет функций [8].

Для сжатия изображений используются два вейвлет

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

сигнала оставшуюся после

фильтрации будем далее обозначать буквой - L, а высокочастотную - Н. Поскольку обрабатываемая картинка двумерна, производится двумерное рис. 2. Четыре наиболее известных семейства вейвлет преобразование, при этом вейвлет функций [8] сначала осуществляется фильтрация по

строкам, а затем по столбцам, либо наоборот. В результате двумерного вейвлет преобразования мы получаем четыре компоненты: LL, LH, HL и НН. Наибольшее количество информации содержит LL- компонента. В LH- и HH-компонентах большое количество нулей, а элементы НН- компоненты практически все равны нулю (см. Рис.3). Для увеличения коэффициента сжатия низкочастотная LL-компонента снова подвергается двумерному вейвлет преобразованию и т.д. [9]

Рис. 3. LL-, LH-, HL-, НН- компоненты, получившиеся в результате двумерного вейвлет преобразования Y-составляющей изображения. Чем темнее пиксел, тем ближе соответствующее ему значение к нулю

Рассмотрим операцию сжатия. Изображение представляется в виде компонент Y Cr Cb, каждая из компонент обрабатывается отдельно. Кодирование каждой компоненты происходит в 4 стадии:

1. Дискретное двумерное вейвлет преобразование (может быть несколько шагов).

2. Квантование.

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

4. Арифметическое кодирование.

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

6. Метод анализа эффективности алгоритмов

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

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

PSNR

1Г>*1 1=1 У=1

720 576

xx P( x, y) - p( x, y)\

720 576

xxIP( x A

x=1 y=1

Р(х,у) - значение яркостной(цветовой) компоненты пиксела исходного кадра, а Р'(х,у) -кадра, полученного после декомпрессии сжатого кадра.

Для сжатых видеофрагментов вычислялся коэффициент сжатия. Далее на графике по оси абсцисс откладывался коэффициент сжатия, а по оси ординат соотношение сигнал/шум (рис. 4).

Поскольку эффективность Mpeg4 алгоритма сильно зависит от реализации поиска векторов скоростей для компенсации движения, для большей наглядности были исследованы две реализации данного алгоритма, а именно реализации созданные группами DIVX и XVID.

7. Результаты сравнения эффективности кодеков

На рисунке 4 представлены результаты сравнительного анализа различных алгоритмов сжатия цифровых видеопотоков. Сравнивались три типа алгоритмов: MJpeg, Mpeg4 и wavelet. Чем выше расположение линии графика, тем выше эффективность кодека.

Рассмотрим взаимное расположение графиков для MJpeg и Mpeg4. He составляет труда заметить, насколько большой вклад в сжатие дает компенсация движения. При одинаковом соотношении сигнал/шум Mpeg4 обеспечивает в 3 раза больший коэффициент сжатия по сравнению с MJpeg. Однако на эффективность работы кодека влияет не только алгоритм, по которому производится сжатие, но и то насколько хорошо реализован этот алгоритм. Это следует из взаимного расположения графиков для Mpeg4.3vx и Mpeg4.divx. Понятно, почему алгоритм, реализованный группой DIVX, пользуется большей популярностью.

Наибольший интерес представляет график для wavelet сжатия. Хотя в алгоритме wavelet сжатия ни коим образом не устраняется временная избыточность, эффективность данного алгоритма не намного ниже эффективности алгоритма Mpeg4, а при низких коэффициентах сжатия даже превышает её.

-к-Mjpeg -к-Wavelet

-*-Mpeg4.3vx - -Mpeg4.divx

500 Коэф. сжатия

Рис. 4. График, отображающий отношение сигнал/шум при разных коэффициентах сжатия, для алгоритмов MJpeg, Mpeg4, Wavelet. Чем выше и правее лежит график, тем выше эффективность алгоритма.

8. Выводы

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

Одним из наиболее перспективных Wavelet подобных методов сжатия видеопотоков является Wavelet 3D, в котором временная ось рассматривается как третье измерение и по этому измерению также производится wavelet преобразование. К основным недостаткам этого метода следует отнести большую ресурсоемкость, а также тот факт, что временная ось имеет более грубый шаг дискретизации, чем пространственные оси. Однако данные проблемы вполне преодолимы.

В России разработан Motion Wavelet алгоритм, который по утверждению авторов сжимает в 1.7 раза компактней, чем Mpeg4 реализованный группой DIVX. Данный алгоритм держится в секрете. Это в очередной раз доказывает перспективность развития Wavelet подобных методов сжатия.

Литература

[1] Wallace, G. (1991), The JPEG algorithm for image compression standard , Vol 34 No 4 pp

31-44 Communications of the ACM [2] Huffman, D. (1962), A method for the construction of minimum redundancy codes , Vol

40 pp 1098-101 In proceedings IRE [3] Witten, I., Radford, M., Cleary, J. (1987), Arithmetic coding for data compression , Vol 30

No 6 pp.520-40 Communications of the ACM

[4] Jacklin, M. (2002), MPEG-4 - The Media Standard , MPEG-4 Industry Forum

[5] Niedemayer, M. (2003), DIVX3 / MS-MPEG4v1-v3 / WMV7-8 , GNU Free

Documentation

[6] Li, W., Ohm, .1., Schaar, M., Jiang, H., Li, S. (2001), Coding of Moving Pictures and Audio: MPEG-4 Video Verification Model , v 18,N3908 (ISO/IEC JTC1/SC29/WG11), Pisa

[7] Astafeva, N. (1996), Wavelet analysis: basic theory and some applications , Space Research Institute, Russian Academy of Science

[8] Graps, A. (1995), An Introduction to Wavelets , Vol 2 Num 2 IEEE Computational Science and Engineering

[9] Stollnitz, E., DeRose, Т., Salesin, D. (1994), Wavelets for Computer Graphics: A Primer , Tech.Rep.94-09-11 Departament of Computer Science And Engeneering Unicersity of Washington