Дмитрий Сахань
Если вы умеете программно оперировать видеоданными и имеете свободное время, предлагаю вам закодировать 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. Кроме этого передача изменений пикселя может быть как в виде прямых значений, так и с помощью процентных отношений (позже объясню, что значит "прямые значения", а что "процентные отношения"). Эти сведения указываются в двух младших битах поля Properties. Остальные биты поля зарезервированы для последующих модификаций и должны быть установлены в нуль.
Поле Properties (побитно)
биты 8..3 = зарезервированы и должны быть равны 0
бит 2 (RatioType) = 0 - изменения пикселя заданы в виде прямых значений
1 - изменения пикселя заданы с помощью процентных отношений
бит 1 (ColorSpace) = 0 - используется цветовое пространство RGB
1 - используется цветовое пространство YCbCr
Поля StartRCr, StartGY и StartBCb содержат начальные значения, которыми заполнены соответствующие цветовые плоскости опорного кадра (ниже описано, что это за кадр). Как вы понимаете, поле StartRCr содержит либо значение красного цвета, если в поле Properties (его битом ColorSpace) выбрано цветовое пространство RGB, либо значение красной цветоразности, если выбрано цветовое пространство YCbCr. Соответственно, поле StartGY - значение зеленого цвета в RGB или яркость в YCbCr, а поле StartBCb - синий цвет в RGB или синюю цветоразность в YCbCr. Сразу замечу, что начальные значения в зависимости от бита RatioType поля Properties задаются либо прямыми значениями, либо процентными отношениями.
Опорный кадр - это кадр, от пикселей которого выполняется кодирование или декодирование видеоряда. Иными словами, опорный кадр - это своеобразный цвет фона первого кадра видеоряда. Все пиксели опорного кадра заполнены одним и тем же цветом. Этот кадр вводится специально перед началом видео, чтобы эффективно начать кодирование первых кадров. В дальнейшем опорный кадр не используется. Но как вы видите, значение фона задается для каждой цветовой плоскости отдельно, так как кодирование пикселей осуществляется не по их общему цвету, а по каждой цветовой плоскости. А в каждой плоскости фоновое значение может быть своим. Таким образом, в кодировщике должна присутствовать функция, обеспечивающая поиск максимально повторяющихся значений в соответствующих плоскостях первого кадра видео (именно видео, а не опорного кадра) и занесение этих значений в поля StartRCr, StartGY и StartBCb. Полученным RGB- или YCbCr-значением заполняются все пиксели опорного кадра.
Сразу за заголовком видеопотока следует массив закодированных наборов поведений. Цель использования этого массива: максимально повысить степень сжатия видео. Представим, что в видео существует сцена, где луч света от фонарика освещает объекты в затемненной комнате. Луч двигается через весь кадр слева-направо. Сначала объекты в левой части кадра понемногу выходят из темноты, затем становятся отчетливо видны, затем постепенно уходят в темноту. Далее объекты средней части кадра, а затем и правой части. Несмотря на разные цветовые оттенки объектов комнаты, модели поведения многих пикселей на экране имеют сходные черты (одинаковые пропорции нарастания или убывания освещенности и т.п.). Закодировав в каком-нибудь элементе массива данный набор поведений (нарастание/убывание освещения) можно при кодировании пикселя просто указать индекс этого элемента массива. Независимо от цвета пикселя, будет максимально точно смоделировано его поведение на экране во всех похожих сценах видео.
type PBCvideoBehaviours = record
ItemCount: Word;
Behaviours: array of PBCvideoBehaviourSet;
end;
type PBCvideoBehaviourSet = record
Count: Byte;
Behaviour: array of Byte;
end;
Массив поведения состоит из поля ItemCount (количество элементов в массиве = количество наборов поведений в массиве) и самих элементов массива. Этот массив не может содержать более 8192 элементов, что объясняется способом хранения информации в поле индекса (рассматривается ниже) при кодировании поведения пикселя. Каждый элемент массива состоит из поля Count (количество закодированных поведений в данном наборе) и байтового массива с закодированными поведениями. В любом элементе массива можно закодировать набор максимум из 256 поведений (0 = 1 поведение, 1 = 2 поведения и так далее). Поведения в наборе кодируются так же, как они кодируются для пикселей. Кодирование поведений для пикселей рассматривается ниже.
С момента создания опорного кадра можно начинать кодирование видеоряда. Закодированный поток представляет собой последовательный набор поведений пикселей видео. Для каждого пикселя последовательно кодируются поведения по всем его цветовым плоскостям. Любое поведение в закодированном потоке задается в виде структуры из двух/трех полей. Ниже для наглядности я привел структуры поведений. Когда цветовая плоскость пикселя не изменяется, поведение кодируется двумя полями структуры PBCvideoIdentical. При изменении цветовой плоскости пикселя поведение кодируется тремя полями структуры PBCvideoChanged. Отдельная структура PBCvideoEncoded с двумя полями используется, когда поведение цветовой плоскости пикселя кодируется некоторой последовательностью поведений, описанной в массиве наборов поведений. Типы полей структуры приведены русскими названиями, а ниже объясню, как работает каждый из этих типов.