Технологии и алгоритмы сжатия видео

Run Length Encoding

Компрессорами, использующими технологию RLE, являются:

Microsoft RLE (MRLE) RLE используется также для кодирования коэффициентов в БДКП, применяющемся в MPEG-1234, H.261, H.263 и JPEG.

Достоинства и недостатки

1. Работает исключительно с 8-битовыми изображениями.

2. Не подходит для сжатия полноцветного видео.

Обзор

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

Векторная квантизация (Vector Quantization,VQ)

Компрессорами, использующими технологию VQ, являются Indeo 3.2 и Cinepak. Оба они применяют цветовую схему YUV (а не RGB).

Достоинства и недостатки

1. Процесс кодирования очень трудоемок и практически неосуществим без специального дополнительного оборудования.

2. Процесс декодирования очень быстр.

3. Блоковые искажения при высоких коэффициентах сжатия.

4. Технологии, использующие алгоритмы БДКП, ДВП могут достигать более высоких уровней сжатия.

Обзор

Основная идея векторной квантизации заключается в разбиении изображения на блоки (размером 4x4 пиксела в цветовой схеме YUV для компрессоров Indeo и Cinepak). Как правило, некоторые блоки оказываются похожими друг на друга. В этом случае компрессор идентифицирует класс похожих блоков и заменяет их одним общим блоком. Кроме того, генерируется двоичная таблица (карта) таких общих блоков из самых коротких кодовых слов. VQ-декодер затем, используя таблицу, собирает изображение поблочно из общих блоков. Ясно, что данный способ кодирования с потерями качества, так как, строго говоря, схожесть блоков весьма относительна. Здесь допускается аппроксимация реальных блоков изображения к общему, их объединяющему. Процесс кодирования длителен и трудоемок, так как кодеру необходимо выявлять принадлежность каждого блока изображения к какому-нибудь общему блоку. Однако задача декодирования в этом случае сводится к задаче построения изображения по заданной карте из общих блоков и не занимает много аппаратных и временных ресурсов. Таблицу или карту также называют еще и кодовой книгой, а двоичные коды, входящие в нее, - кодовыми словами, соответственно. Наибольшее сжатие с использованием алгоритма VQ достигается путем уменьшения числа классов общих блоков, то есть предположением о схожести относительно большего числа блоков изображения, и, как следствие, уменьшением кодовой книги. По мере уменьшения размеров кодовой книги качество воспроизводимого видео ухудшается. В результате на изображении появляется искусственная «блочность».

Простой пример: сравним три следующих блока 4 x 4.

(Блок 1) 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128

(Блок 2) 128 127 128 128 128 128 128 128 128 128 127 128 128 128 128 128

(Блок 3) 128 127 126 128 128 128 128 128 127 128 128 128 128 128 128 128

Эти три блока для человеческого глаза неотличимы. Таким образом, 2-ой и 3-ий блоки можно спокойно заменить первым. Тогда кодовая книга будет иметь следующий вид:

Кодовая Книга[1] = 128 128 128 128

128 128 128 128

128 128 128 128

128 128 128 128

Важной особенностью технологии VQ является то, что при сжатии видео одна и та же кодовая книга может использоваться для нескольких кадров изображения.

Дискретное Косинусное Преобразование (ДКП)

Компрессоры, использующие ДКП: Motion JPEG; Editable MPEG; MPEG-1; MPEG-2; MPEG-4.

Достоинства и недостатки

1. «Блочность» при высокой компрессии.

2. Закругление острых углов изображения. Случайное «размывание» острых краев изображений.

3. Кодирование очень трудоемко. Только в последнее время удалось осуществить процесс кодирования программно, а не аппаратно.

Обзор

ДКП является широко используемым при сжатии изображений преобразованием. Стандарт сжатия статической графики JPEG, используемый в видеоконференциях стандарт H.263, цифровые видеостандарты MPEG (MPEG-1, MPEG-2 и MPEG-4) — все они используют ДКП. В этих стандартах используется, в частности, 2-мерное ДКП, применяемое последовательно к блокам изображения размерностью 8 x 8 пикселов. ДКП вычисляет 64 (8x8 = 64) коэффициента, которые затем квантизуются, обеспечивая тем самым реально сжатие. В большинстве изображений большинство ДКП-коэффициентов в силу своей малости после квантизации обнуляется. Это свойство ДКП и лежит в основе множества алгоритмов сжатия, использующих ДКП.

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

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

ДКП(m,n) = sqrt( (1 - delta(m,1) ) / N ) * cos( (pi/N) * (n - 1/2) * (m-1) )

, где

ДКП (m,n) есть одномерная матрица ДКП

m, n = 1,...,N

pi = 3.14159267...

N = число выборок в блоке

delta(m,1) = 1 если m = 1 и 0 в противном случае

cos(x) = косинус x, измеряемый в радианах.

Естественно, применение ДКП на блоке из N выборок потребует N*N операций умножения и суммирования. Однако благодаря рекурсивной структуре матрицы ДКП реально потребуется гораздо меньшее количество математических операций, а именно N log(N). Это свойство делает ДКП реально применимым на современных математических процессорах персональных ЭВМ.

Дискретное Wavelet-преобразование (DWT)

Компрессоры, использующие DWT (Discrete Wavelet Transform): Intel Indeo 5.x; Intel Indeo 4.x