Алгоритм сжатия видео 'pixel behaviour check'
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
Алгоритм сжатия видео pixel behaviour check
Дмитрий Сахань
Если вы умеете программно оперировать видеоданными и имеете свободное время, предлагаю вам закодировать PBC-алгоритм сжатия видеопотока. Сразу скажу, что алгоритм новый и никем не опробованный (для справки: статье уже почти два года). По этой же причине не могу утверждать, что он лучше или хуже MPEG4 или DivX-алгоритмов. Мой алгоритм использует подход к кодированию видео, отличный от MPEG, и эффективен только для кодирования последовательности видеокадров.
Основные особенности MPEG
Для начала хочу коротко объяснить основную идею MPEG-алгоритма (DivX является одной из версий MPEG4). Шифрация видеоданных в MPEG в своей основе использует алгоритмы шифрации спецификации JPEG. Дополнительно в MPEG используются алгоритмы компенсации движения, I-кадры и т.д. и т.п. Но рассмотрим, как в JPEG кодируется статический кадр изображения.
Сначала все цветовое пространство кадра преобразуется из RGB в YCbCr. Необходимость этого преобразования заключается в том, что глаз более чувствителен к яркости цвета, чем к его оттенку. Y - это величина яркости цвета, а Cb и Cr - цветовые величины, определяющие оттенок и насыщение цвета (они определяют количество синей и красной составляющих в цвете). Уже на этом этапе происходят потери в информации, так как формулы преобразования RGB в YCbCr и обратно не позволяют точно (значение в значение) сохранить некоторые цвета. Как вы заметите в дальнейшем, JPEG-алгоритм рассчитан на максимальную потерю избыточной информации. Этим-то и достигается высокая степень сжатия.
Затем проводится дискретизация изображения. Это еще один способ потерять информацию, но уже в больших объемах. Идея в том, что яркость (Y) берется для каждого пикселя изображения, а цветоразность (Cb, Cr) - как среднее значение блока 2x2 пикселей. Вообще-то в стандарте JPEG для Y, Cb и Cr определено по два коэффициента дискретизации: по горизонтали и по вертикали. Поэтому хоть яркость, хоть цветоразность при желании можно брать как среднее значение любого по размерам блока (хоть 10x10 пикселей). В конечном итоге это отразится на качестве зашифрованного изображения. Большие значения дискретизации - первый шаг к получению "зубчатого" изображения.
После этого проводится дискретное косинусоидальное преобразование (DCT) изображения, которое делится на блоки 8x8 пикселей, и к каждому блоку применяется DCT-преобразование. Цель этого в том, чтобы получить по 64 амплитуды частотного пространства для каждого из блоков 8x8 пикселей. Затем 64 амплитуды зигзагообразно переставляются в блоке, чтобы получить вектор с 64 коэффициентами, отсортированный критериями пространственной частоты.
Теперь каждый вектор из 64 коэффициентов квантуется с помощью заранее заданных таблиц квантования. Это нужно для того, чтобы удалить высокие частоты, которые представляют собой высокую детализацию данного блока изображения. В результате квантованный вектор содержит большое количество расположенных подряд нулей. Ну и весь вектор кодируется уже с помощью самого обычного RLE-алгоритма (Run Length Encoding). В заключении к полученному набору байт применяется кодирование Хаффмана, которое позволяет записать байты длины RLE-кодирования с самыми минимальными затратами бит.
Алгоритм MPEG через определенное количество кадров всегда создает I-кадр, который кодируется подобно JPEG. В кадрах между I-кадрами закодирована компенсация движения блоков изображения. Как видите, MPEG имеет довольно сложный алгоритм.
Алгоритм "Pixel Behaviour Check"
Алгоритм имеет название "Контроль поведения пикселя". Основная идея в том, что мы рассматриваем каждый пиксель как объект, имеющий поведение. И кодирование ведется не относительно текущего кадра, а сквозь кадры. Как будто кадры расположены один над другим, а мы смотрим сквозь них и регистрируем поведение каждого пикселя. Поведение пикселя имеет три состояния: остается неизменным, начинает расти или уменьшаться. Пиксель остается неизменным, когда на протяжении нескольких кадров значение его цвета не изменяется. Пиксель растет, когда значение его цвета из кадра в кадр продолжает увеличиваться. Пиксель уменьшается, когда значение его цвета постоянно уменьшается.
В этом алгоритме отсутствует необходимость в алгоритмах компенсации движения. Потери в закодированном изображении присутствуют, но они малозначительны, поэтому незаметны. Также нет эффекта "зубчатости" изображения. Не менее важна простота работы алгоритма. Теперь перейду к его описанию. Для удобства буду сразу оперировать данными в виде структур. Начнем с заголовка видеопотока.
type PBCvideoHeader = record
Width: Word; // ширина кадра видеофильма
Height: Word; // высота кадра видеофильма
FrameCount: DWord; // количество кадров в видеофильме
FrameRate: Byte; // скорость кадров (кадров в секунду)
Properties: Byte; // свойства кодирования
StartRCr: Byte; // начальное заполнение плоскости красного цвета / Cr
StartGY: Byte; // .............................. зеленого цвета / Y
StartBCb: Byte; // .............................. синего цвета / Cb
end;
Думаю, с полями Width и Height все понятно - в них хранятся высота и ширина кадра в пикселях. Поле FrameCount содержит общее количество кадров в видеопотоке, а поле FrameRate - скорость следования кадров, измеряемую в кадрах в секунду. Поле Properties содержит сведения об особенностях кодирования видео. Дело в том, что алгоритм поддерживает как RGB-пространство, так и YCbCr. Кроме этого передача изменений пикселя может быть как в виде прямых значений, так и с помощью процентных отношений (позже объясню, что значит "