Дмитрий Сахань

Если вы умеете программно оперировать видеоданными и имеете свободное время, предлагаю вам закодировать 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 с двумя полями используется, когда поведение цветовой плоскости пикселя кодируется некоторой последовательностью поведений, описанной в массиве наборов поведений. Типы полей структуры приведены русскими названиями, а ниже объясню, как работает каждый из этих типов.

type PBCvideoIdentical = record

Code: 2_бита;

Repeat: код_повторов;

end;

type PBCvideoChanged = record

Code: 2_бита;

Repeat: код_повторов;

Extent: Byte;

end;

type PBCvideoEncoded = record

Code: 2_бита;

Index: код_индекса;

end;

Поле Code содержит двухбитный код поведения цветовой плоскости пикселя. Всего можно задать четыре кода для поведения: 00 - не изменяется, 01 - увеличивается, 10 - уменьшается и 11 - закодирован в массиве поведений. Поле кода поведения идентично для всех трех указанных структур поведения.

Поле Repeat содержит в себе количество кадров, которые повторяется заданное поведение цветовой плоскости пикселя. Поведение повторяется хотя бы один кадр, но для эффективности использования поля Repeat количество кадров повторения перед сохранением в этом поле переводится в диапазон от 0 до N-1, а не от 1 до N. Это достигается вычитанием 1 из количества кадров, где 0 теперь будет означать 1 кадр, 1 будет означать 2 кадра и так далее. Поле Repeat может иметь длину 6 бит или 14 бит. Это компромиссное решение позволяет удерживать биты структуры в пределах байта или слова (чтобы не усложнять программирование, когда байт может содержать биты разных структур) и расходовать минимум бит как для небольших значений повторов, так и для больших. Фактически поля Code и Repeat занимают совместно один или два байта, где старшие два бита всегда принадлежат полю Code. Я опишу механизм извлечения значения из поля Repeat, и вы поймете, как оно там хранится.

1. Взять текущий байт

2. Старшие два бита принадлежат полю Code

3. Если 6-ой бит байта равен 0, тогда младшие 5 бит байта содержат значение

4. Иначе взять следующий байт, который является младшим байтом для текущего байта

5. Младшие 13 бит полученного слова содержат значение

К извлеченному значению необходимо добавить 1, чтобы получить реальное количество повторений. При повторах от 1 до 32 используются всего 6 бит (совместно с полем Code - один байт), а свыше 32 и до 8192 - 14 бит (с полем Code - два байта). Если количество повторов превышает 8192, тогда в одном поведении кодируется максимально возможное количество повторов, а в следующем поведении - оставшаяся часть повторов.

В поле Extent хранится величина изменения цветовой плоскости пикселя, которая в зависимости от бита RatioType поля Properties задана либо прямым значением, либо процентным отношением. В итоге мы получаем, что структура PBCvideoIdentical может занимать в байтовом представлении один или два байта, а структура PBCvideoChanged - два или три байта.

Прямое значение - это число, вычисленное как разница между текущим и предыдущим значениями цветовой плоскости пикселя. Прямое значение всегда положительное число и вычисляется как разница по модулю. Нужно заметить, что разница вычисляется между крайними точками диапазона изменения, когда значение цветовой плоскости пикселя закончило увеличиваться или уменьшаться. Ниже я привел рисунок в виде графика поведения цветовой плоскости пикселя. Красными черточками выделены места, где один код поведения сменяет другой, а в поведении кодируется количество кадров повторения и разница изменения, или только количество кадров повторения при отсутствии изменений. Для наглядности светло-зеленым цветом выделены поведения, когда цветовая плоскость пикселя остается неизменной.

Процентное отношение - это та же самая разница между значениями цветовой плоскости пикселя, но выраженная в диапазоне от 1 до 100 процентов. Если прямые значения приводят к минимуму потерь в цвете, то процентные отношения в обмен на небольшие потери хорошо справляются с так называемым цветовым шумом, когда цвет пикселя нестабильный и "скачет" с мизерными изменениями вокруг реального цвета.

И последнее поле Index по способу хранения информации сходно с 6/14-битным полем Repeat. В поле Index хранится индекс закодированного в массиве поведений целого набора поведений для данной цветовой плоскости пикселя. Способ хранения информации в поле Index указывает, что в массиве поведений может быть не более 8192 наборов поведений. Кодирование с помощью закодированных наборов поведений значительно увеличивает степень сжатия, так как многие участки поведений пикселей имеют сходные модели поведения. Кодировщик может и не использовать кодирование поведений через массив поведений, но тогда он не должен использовать поведения с кодом 11 (когда поле Code = 11) и массив поведения оставить пустым. Замечу, что структура PBCvideoEncoded в точности повторяет структуру PBCvideoIdentical, только вместо поля Repeat используется поле Index.

Внедрение данных в видеопоток

Чтобы вы могли внедрять в видеопоток собственные данные, предусмотрен специальный код. Возможно, вы хотите параллельно в видеопотоке кодировать звук или внедрить на каких-то участках потока другие методы кодирования. Может, вам понадобится внедрить в поток собственные метки, текст или еще что-нибудь. Для этих целей используется код на основе структуры PBCvideoIdentical, где поле Repeat содержит максимальное количество повторов. Получается, что при поведении цветовой плоскости пикселя, когда она не изменяется на протяжении нескольких кадров (поле Code = 00), максимально можно указать 8191 повтор, а не 8192 как в других структурах. Если же в структуре PBCvideoIdentical количество повторов равно 8192, тогда эта структура обозначает специальный код внедрения других данных в видеопоток.

За таким кодом всегда должно следовать DWord-поле размера блока внедренных данных. Декодер, прочитав код внедрения данных (содержимое PBCvideoIdentical = 3FFFh), читает следующее DWord-поле, по которому узнает, через сколько байт после DWord-поля следует продолжение видеопотока. Декодер знает размер блока внедренных данных, знает адрес (или смещение) этого блока, и может вызывать некоторую специальную функцию, обрабатывающую ваши внедренные данные. Затем декодер на основе размера блока внедренных данных вычисляет адрес (смещение) продолжения данных видеопотока.

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

Работа декодера

Чтобы вам было понятнее, рассмотрим шаг за шагом работу декодера. Не стоит считать описанные мной методы реализации декодера и его структуры истинно верными. Я лишь стремился проще объяснить принцип декодирования, не особо вдаваясь в вопросы качества реализации декодера. Вы сами в состоянии определить, как максимально качественно написать его начинку. Если есть желание, можете скачать исходники примера PBC Player'а здесь (205 Кбайт). Исходники написаны в Delphi, а программный код (стиль программирования) не гарантирует высокую производительность и безошибочность реализации.

Нам понадобится опорный кадр. Спроектируем его структуру так, чтобы хранить в нем сведения не только для декодирования первого кадра, но и каждого следующего. Опорный кадр будет представлять собой динамический массив с данными о поведении всех пикселей изображения. В каждом пикселе имеется по три цветовых плоскости, поэтому количество элементов в этом массиве будет равно ШИРИНА * ВЫСОТА * 3. Теперь опишем массив, элементы которого будут представлены структурой ColorPlane. Я намеренно добавил префикс "cp" к именам полей этой структуры, чтобы вы не путали их со сходными полями структур PBCvideoIdentical, PBCvideoChanged и PBCvideoEncoded.

type ColorPlane = record

cpIndex: Word; // индекс закодированного набора поведений

cpBehaviour: Byte; // индекс текущего поведения, выполняемого из набора

cpCode: Byte; // код выполняемого поведения

cpRepeat: Word; // количество кадров повторения поведения

cpCurrent: Double; // текущее значение цветовой плоскости пикселя

cpExtent: Double; // величина изменения плоскости за один кадр

end;

// глобальные переменные

var

Frame: array of ColorPlane; // опорный кадр

Отмечу, что структура ColorPlane в таком виде не позволит использовать кодирование наборов поведений через другие наборы, когда один набор на каком-то своем участке может ссылаться на содержимое другого набора. В наборах поведений допустимо использовать поведения с кодом 11 (закодирован в массиве поведений), а значит, можно реализовать высокую вложенность наборов поведений. Это может помочь сильнее сжимать видео. Приведу пример, где зацикленные друг на друга наборы приводят к эффективному сжатию.

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

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

Первым делом декодер читает заголовок видеопотока. Получив ширину и высоту кадра видеофильма (поля Width и Height структуры PBCvideoHeader), декодер устанавливает размер массива опорного кадра по формуле Width * Height * 3. Значения полей StartRCr, StartGY и StartBCb заносятся в поля cpCurrent соответствующих элементов массива опорного кадра. Декодеру нужно сразу заполнить цветовые плоскости опорного кадра соответствующими начальными значениями. Первые три элемента массива принадлежат первому пикселю (его координаты = 0,0), следующие три элемента - второму пикселю (0,1), следующие - третьему, и так далее. Поэтому в поле cpCurrent первого элемента массива заносится значение поля StartRCr, во второй элемент массива - значение поля StartGY, в третий элемент - значение поля StartBCb, в четвертый элемент - снова поле StartRCr, в пятый - поле StartGY, и так далее. Все остальные поля элементов массива обнуляются. Замечу, что поле cpIndex обнуляется значением 0FFFFh. Декодер использует это поле, чтобы выяснить, обслуживается ли в настоящий момент для данной цветовой плоскости пикселя поведение из видеопотока или оно берется из массива поведений. Индекс набора поведений может лежать только в пределах от 0 до 8191 (всего получается 8192 набора поведений), а значение 0FFFFh находится за пределами массива, поэтому декодер легко определяет, что текущее поведение взято не из массива поведений, а прямо из видеопотока. Для наглядности приведу фрагмент программы.

// глобальные переменные

var

Header: PBCvideoHeader; // заголовок видеопотока

Behaviours: PBCvideoBehaviours; // массив поведений

Frame: array of ColorPlane; // опорный кадр

FrameNum: DWord; // номер текущего кадра

procedure InitFrame;

var

W: Word; // ширина

H: Word; // высота

I: DWord; // индекс плоскости в массиве опорного кадра

begin

// читаем заголовок видеопотока из некоторого файла

BlockRead(F1, Header, SizeOf(Header));

// устанавливаем размер массива опорного кадра

I := Header.Width * Header.Height * 3;

SetLength(Frame, I);

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

// (поле cpIndex обнуляем значением 0FFFFh)

repeat

Dec(I);

Frame[I].cpIndex := $FFFF;

Frame[I].cpBehaviour := 0;

Frame[I].cpCode := 0;

Frame[I].cpRepeat := 0;

Frame[I].cpExtent := 0;

until I = 0;

// теперь занесем значения полей StartRCr, StartGY и StartBCb

// в соответствующие цветовые плоскости опорного кадра

for H := 1 to Header.Height do begin

for W := 1 to Header.Width do begin

// вычисляем в переменной I индекс элемента массива

// опорного кадра, с которого расположены подряд

// три цветовых плоскости пикселя с координатами W и H

// (где W = X, H = Y)

I := (H-1) * Header.Width * 3 + (W-1) * 3;

// а теперь заносим в три плоскости пикселя

// начальные цветовые значения

Frame[I].cpCurrent := Header.StartRCr;

Frame[I+1].cpCurrent := Header.StartGY;

Frame[I+2].cpCurrent := Header.StartBCb;

end;

end;

// читаем массив поведений из файла в переменную Behaviours

ReadBehavioursData(F1, Behaviours);

// сбрасываем внутренний счетчик декодированных кадров,

// а по нему будем определять, что видеопоток закончился

FrameNum := 0;

end;

За заголовком декодер должен прочитать из видеопотока массив поведений. Это обычный массив и декодер должен "сложить" его где-нибудь у себя в памяти, чтобы иметь к нему быстрый доступ в случае кодирования поведения цветовой плоскости пикселя набором поведений из массива. В конце приведенного фрагмента кода указан вызов якобы уже написанной процедуры ReadBehavioursData, которая загружает массив поведений из файла в переменную с именем Behaviours. Эта переменная содержит в себе количество элементов в массиве (поле ItemCount) и массив Behaviours с элементами, представляющими собой наборы поведений. У каждого набора есть поле Count (количество поведений в наборе) и поле Behaviour с набором этих поведений. Отмечу, что в наборе поведений всегда есть хотя бы одно поведение, поэтому поле Count со значение 0 обозначает одно поведение, со значением 1 - два поведения, и так далее до 255, что обозначает 256 поведений.

За массивом поведений следует набор сведений о поведении конкретных цветовых плоскостей пикселей изображения - общий видеопоток. Декодер извлекает эти сведения, опираясь на данные элементов массива опорного кадра. Если в некотором элементе массива поле cpIndex равно 0FFFFh (поведение цветовой плоскости пикселя было взято прямо из видеопотока) и поле cpRepeat равно нулю (повторы поведения закончились), значит, сейчас в видеопотоке находятся данные о следующем поведении текущей цветовой плоскости пикселя, и эти данные нужно извлечь и занести в текущий элемент массива. Если же это не так, и поле cpRepeat не равно нулю (еще остались повторы поведения), тогда нужно в текущем элементе массива уменьшить на 1 поле cpRepeat и, в зависимости от поля cpCode (00, 01 или 10), либо оставить без изменения, либо увеличить или уменьшить поле cpCurrent на величину поля cpExtent.

Образно говоря, декодирование каждого кадра начинается с того, что декодер проходит последовательно все элементы массива опорного кадра - от первого до последнего элемента (фактически проходит по всем цветовым плоскостям пикселей видеокадра). Если в поле cpRepeat остались повторы, тогда уменьшить поле cpRepeat на 1, а к полю cpCurrent прибавить или отнять (в зависимости от значения поля cpCode) значение поля cpExtent. Новое значение поля cpCurrent и будет тем, что заносится в соответствующую цветовую плоскость пикселя реального кадра на экране. Но перед этим значение поля должно быть еще обработано, о чем будет рассказано ниже.

// глобальные переменные

var

Header: PBCvideoHeader; // заголовок видеопотока

Behaviours: PBCvideoBehaviours; // массив поведений

Frame: array of ColorPlane; // опорный кадр

procedure CreateNextFrame;

var

I: DWord; // индекс плоскости в массиве опорного кадра

L: DWord; // количество элементов в массиве опорного кадра

C: Byte; // код только что прочитанного поведения

R: Word; // количество повторов поведения

E: Byte; // величина изменения плоскости за весь период поведения

begin

L := Length(Frame);

I := 0;

while I < L do begin

// если еще остались повторы для текущей цветовой плоскости,

// тогда вычислить значение цветовой плоскости для

// текущего кадра

if Frame[I].cpRepeat 0 then begin

Dec(Frame[I].cpRepeat);

// при поведении 00 цветовая плоскость не изменяется,

// поэтому в структуре CASE не используется проверка на 00,

// а код 11 всегда заменяется реальным поведением из набора поведений,

// поэтому его проверка тоже не нужна

case Frame[I].cpCode of

01: Frame[I].cpCurrent := Frame[I].cpCurrent + Frame[I].cpExtent;

10: Frame[I].cpCurrent := Frame[I].cpCurrent - Frame[I].cpExtent;

end;

end else begin

// этот фрагмент смотрите ниже, где рассматривается, что происходит,

// если в поле cpRepeat не осталось повторов

end;

Inc(I);

end;

end;

Когда же в поле cpRepeat не осталось повторов, декодер должен проанализировать поле cpIndex. Если там не указан индекс обслуживаемого набора поведений цветовой плоскости пикселя (cpIndex = 0FFFFh), тогда нужно взять следующее поведение прямо из видеопотока и занести его данные в текущий элемент массива опорного кадра. Как уже было сказано ранее, декодер должен уметь обслуживать специальный код внедрения других данных в видеопоток, и продолжать декодирование видео после внедренного блока данных. Заметьте, что в элементах опорного кадра хранятся коды реальных поведений, чтобы знать, что в действительности происходит с цветовой плоскостью пикселя. Поэтому при встрече кода "закодирован в массиве поведений" (cpCode = 11), декодер должен извлечь первое поведение из указанного набора и использовать код этого поведения. Описанный мной фрагмент кода поддерживает безвозвратную вложенность наборов поведений, но с возвратной не справится.

Итак, допишем недостающий фрагмент процедуры CreateNextFrame. Для простоты считаем, что у нас уже написана процедура ReadBehaviour, читающая из потока одно поведение по описанным выше правилам (смотрите описание содержимого структур PBCvideoIdentical, PBCvideoChanged и PBCvideoEncoded). Также считаем, что у нас уже есть процедура чтения N-го поведения из указанного набора в массиве поведений - GetBehaviour.

if Frame[I].cpIndex = $FFFF then begin

// читаем из видеопотока поведение для текущей

// цветовой плоскости пикселя

// в переменную C возвращается код поведения

// в R - количество повторов поведения или индекс,

// если поведение задано в массиве поведений

// (в этом случае переменная C = 11)

// в E - величина изменения плоскости за весь период поведения

// или 0, если C = 00 или C = 11

ReadBehaviour(C, R, E);

// с помощью цикла делаем обслуживание возможных

// внедренных в видеопоток блоков данных

while (C = 00) and (R = 8192) do begin

// здесь должен быть вызов вашей функции обработки

// внедренного в видеопоток блока данных

// а затем продолжаем читать из потока поведение

// для текущей цветовой плоскости пикселя

ReadBehaviour(C, R, E);

end;

// Если поведение закодировано в массиве набором поведений,

// тогда необходимо прочитать первое поведение из набора

// и использовать его данные, так как в опорном кадре

// используются только коды реальных поведений.

// Следующим циклом обеспечивается выбор первого поведения

// при кодировании с помощью набора, а также он обеспечивает

// поддержку безвозратной вложенности наборов поведений.

while C = 11 do begin

Frame[I].cpIndex := R;

Frame[I].cpBehaviour := 0;

// читаем поведение с индексом Frame[I].cpBehaviour = 0

// из набора поведений с индексом Frame[I].cpIndex,

// а результат чтения возвращается в переменные C, R и E

GetBehaviour(Frame[I].cpIndex, Frame[I].cpBehaviour, C, R, E);

end;

// в поле cpExtent заносится величина изменения цветовой

// плоскости за один кадр повтора, а не за весь его период

Frame[I].cpCode := C;

Frame[I].cpRepeat := R;

Frame[I].cpExtent := E / R;

// а теперь нам осталось вычислить поле cpCurrent для прочитанного

// поведения

Dec(Frame[I].cpRepeat);

case Frame[I].cpCode of

01: Frame[I].cpCurrent := Frame[I].cpCurrent + Frame[I].cpExtent;

10: Frame[I].cpCurrent := Frame[I].cpCurrent - Frame[I].cpExtent;

end;

end else begin

// этот фрагмент приведен ниже и описывает, что происходит,

// когда поле cpIndex содержит индекс обслуживаемого набора поведений

end;

Теперь пришло время объяснить, почему поля cpCurrent и cpExtent заданы типами с плавающей точкой. Дело в том, что в поле cpExtent элемента массива опорного кадра хранится величина изменения цветовой плоскости за один кадр повтора, а не за весь его период. Когда величина изменения за весь период делится на количество повторов, остаются дробные части. Отбрасывать дробные части нельзя, потому что динамика изменения цветовой плоскости может быть разная. Из кадра в кадр поле cpCurrent изменяется на величину поля cpExtent. Представьте, что за 100 кадров цветовая плоскость пикселя изменилась всего на 1 процент. Разделив 1 на 100 кадров и округлив результат, мы получим 0. В результате точка на протяжении 100 кадров не изменится на 1 процент, ведь мы будем добавлять к полю cpCurrent нулевое значение поля cpExtent. А вот если мы будем добавлять с дробными частями, точка за 100 кадров плавно достигнет изменения в 1 процент. Округление до целого числа выполняется только в момент вывода цветовых плоскостей пикселя в реальный кадр на экране, но внутри опорного кадра все вычисления делаются исключительно с дробными частями.

И снова возвратимся к программному коду декодера. Нам осталось рассмотреть часть кода, когда в поле cpRepeat не осталось повторов, а в поле cpIndex указан индекс обслуживаемого набора поведений цветовой плоскости. В этом случае нужно взять следующее поведение из обслуживаемого набора и занести его данные в текущий элемент массива опорного кадра. Если же в наборе пройдены все поведения (выполненное поведение было последним в наборе), тогда нужно взять следующее поведение прямо из видеопотока и уже его данные занести в текущий элемент массива опорного кадра. Еще раз вспомним, что при чтении из видеопотока декодер должен уметь обслуживать специальный код внедрения других данных в видеопоток.

// вычисляем индекс следующего поведения в наборе

Inc(Frame[I].cpBehaviour);

// если в наборе еще не закончились поведения, тогда

// читаем следующее поведение из набора, иначе

// сбрасываем cpIndex в 0FFFFh и читаем поведение из общего видеопотока

if (Frame[I].cpBehaviour 0) and 

(Frame[I].cpBehaviour = Header.FrameCount then Halt;

end;

Если из приведенного кода убрать все комментарии, можно заметить, что программный код декодера небольшой. К тому же алгоритм декодирования оказывается простым и быстрым. Кстати, программный код декодера можно оптимизировать еще в более компактный, так как перестановкой проверки поля cpIndex сначала на реальный индекс (а не на 0FFFFh) можно добиться исключения одинаковых фрагментов кода, читающих поведение из общего видеопотока или набора поведений из массива поведений. Но это уже вы сами решайте, как вам будет удобнее.

За счет чего происходит сжатие

В качестве примера я взял из фильма "Шестой день" поведение красной цветовой плоскости произвольного пикселя в центральной части кадра. Всего взято 100 кадров, что равно 4 секундам фильма при скорости 25 кадров в секунду. Специально выбрал фрагмент фильма, где развивается динамичное действие. Через кадр быстро проезжает машина, а за ней появляется новая сцена с вертолетом. А теперь посмотрим, как вела себя цветовая плоскость R на протяжении 100 кадров.

185, 193, 194, 194, 192, 197, 197, 207, 207, 204, 204, 201, 201, 197, 200, 197, 208, 210, 208, 206, 209, 209, 216, 216, 216, 215, 214, 214, 214, 214, 214, 214, 217, 217, 216, 216, 215, 216, 079, 030, 028, 009, 047, 021, 008, 017, 060, 025, 024, 018, 013, 015, 015, 017, 017, 017, 017, 017, 017, 016, 016, 016, 012, 011, 015, 015, 015, 014, 005, 006, 008, 008, 008, 008, 008, 004, 011, 012, 012, 012, 012, 012, 012, 012, 012, 012, 012, 012, 012, 012, 007, 007, 006, 053, 054, 058, 053, 052, 050, 047

Здесь указаны непосредственные значения красной цветовой плоскости пикселя для каждого из 100 извлеченных кадров. Значение цветовой плоскости всегда лежит в пределах одного байта, а значит, изменяется только от 0 до 255. Как вы можете заметить, в малых значениях добавлены ведущие нули. Я сделал это для того, чтобы выровнять значения для их удобного просмотра при любом размере текстового окна.

Можно сразу заметить, что в наборе байт встречается очень мало смежных повторений одного и того же состояния цветовой плоскости, чтобы кодировать этот фрагмент любым аналогом RLE-алгоритма. Но мы-то рассматриваем фрагмент 100 представленных байт как окончательный и готовый к сжатию, поэтому не находим, что этот набор байт пригоден для эффективного RLE-сжатия. Кодировщику же не интересен сам набор байт, поскольку ему важна только разница между каждыми смежными байтами. И теперь посмотрите, как с помощью разниц набор байт начинает превращаться в эффективный для RLE-алгоритма блок. Нужно отметить, что кодировщик всегда берет разницу по модулю между каждыми смежными байтами.

000, 008, 001, 000, 002, 005, 000, 010, 000, 003, 000, 003, 000, 004, 003, 003, 011, 002, 002, 002, 003, 000, 007, 000, 000, 001, 001, 000, 000, 000, 000, 000, 003, 000, 001, 000, 001, 001, 137, 049, 002, 019, 038, 026, 013, 009, 043, 035, 001, 006, 005, 002, 000, 002, 000, 000, 000, 000, 000, 001, 000, 000, 004, 001, 004, 000, 000, 001, 009, 001, 002, 000, 000, 000, 000, 004, 007, 001, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 005, 000, 001, 047, 001, 004, 005, 001, 002, 003

Получившийся набор состоит из 100 разниц и выглядит уже легче для визуального восприятия. Хотя еще ничего особого не произошло. Тот же самый набор байт, но выраженный через разницы между смежными байтами. Заметьте, в нем стало еще меньше повторяющихся смежных и одинаковых по значению байт. Поэтому для RLE-алгоритма новый набор байт еще не эффективен, разве что содержимое его байт занимает в битовом представлении намного меньше места.

Обратите внимание, что в первом кадре первого набора находилось значение 185, а в наборе разниц находится разница 0. В этот момент предполагалось, что мы кодируем 100 кадров не из середины фильма, а как будто они у нас будут началом отдельного закодированного фрагмента. Допустим, красная цветовая плоскость опорного кадра была заполнена значением 185, поэтому для первого кадра разница между ним и плоскостью опорного кадра равна нулю.

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

00, 03, 00, 00, 00, 01, 00, 03, 00, 01, 00, 01, 00, 01, 01, 01, 04, 00, 00, 00, 01, 00, 02, 00, 00, 00, 00, 00, 00, 00, 00, 00, 01, 00, 00, 00, 00, 00, 53, 19, 00, 07, 14, 10, 05, 03, 16, 13, 00, 02, 01, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 01, 00, 01, 00, 00, 00, 03, 00, 00, 00, 00, 00, 00, 01, 02, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 01, 00, 00, 18, 00, 01, 01, 00, 00, 01

Вы видите, какие получились маленькие значения, какое количество нулей. К слову сказать, MPEG стремится к такому же большому количеству нулей, но за счет множественных потерь информации. Но PBC-кодировщику мало достигнуто результата. В его арсенале есть еще массив поведений. Закодировав полученный набор из 100 байт аналогично RLE (PBC-алгоритм в своей основе использует метод, похожий на RLE, но несколько измененный), кодировщик начинает отыскивать в сжатом фрагменте похожие участки. Нужно сказать, что данный сжатый фрагмент представляет собой поток поведений 100 кадров красной цветовой плоскости. Когда в потоке поведений (общий видеопоток) обнаруживается более одного похожего участка, кодировщик извлекает их из потока и забрасывает в свободный элемент массива поведений, а на место извлеченных участков ставит одно единственное поведение со ссылкой (с индексом) на этот элемент массива. Помещаемые в массив похожие участки поведений называются наборами поведений. Например, в окончательном наборе байт часто повторяются "не эффективно" кодируемые участки типа (00, 01), (00, 02) и (00, 03), которые сбрасываются в массив, а вместо них в поток поведений ставится одно поведение со ссылкой на соответствующие элементы массива поведений. Естественно, участки типа (00, 01) и т.п. забрасываются в массив поведений не как значения 0 и 1, а как их PBC-сжатый вариант. Принцип заполнения массива поведений чем-то похож на LZW-сжатие.

Если кодировщик привел набор байт к удобному сжатию, то массив поведений дополнительно "сгладил" неудобные для сжатия участки. Хочу обратить ваше внимание на тот факт, что при ссылке на первые 32 элемента массива поведений в общем видеопотоке расходуется всего лишь один байт, поэтому в эти элементы желательно заносить самые "корявые" с точки зрения эффективности кодирования наборы поведений. Ссылкой на остальные элементы массива всегда расходуется два байта в видеопотоке.

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

И это еще не все. Когда мы рассматривали, как кодировщик готовит набор байт для сжатия, я указал самый простой вариант подготовки байт, когда кодировщик "глупо" берет и заносит в подготавливаемый набор разницы цветовой плоскости между каждым смежным кадром. PBC-алгоритм предоставляет кодировщику достаточные возможности для еще более качественной подготовки набора байт для сжатия. Самый лучший подход, когда разница берется не между двумя смежными кадрами, а между начальным и конечным кадрами изменения цветовой плоскости. Если значение цветовой плоскости начало нарастать, то кодировщик ждет кадра, в котором плоскость перестанет нарастать. За время нарастания цветовой плоскости кодировщик просто подсчитывает, сколько же кадров она нарастала, а затем в видеопоток заносит, что плоскость нарастала столько-то кадров, а изменение ее значения составило столько-то процентов. Если значение цветовой плоскости начало убывать, снова ждет окончания убывания плоскости и заносит в видеопоток, что она столько кадров убывала на столько-то процентов. Когда же плоскость не изменяется, кодировщик ждет начала любого ее изменения, а в видеопоток заносит, сколько кадров она не изменялась.

Краткая справка по PBC-сжатию

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

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

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

Алгоритм допускает любой подход к наблюдению за изменением цветовых плоскостей. Самый простой (и самый неэффективный) подход заключается в записи данных об изменении между двумя смежными кадрами. Для этого из байтового массива текущего кадра отнимается по модулю байтовый массив предыдущего кадра (побайтно - байт массива текущего кадра минус байт с таким же смещением массива предыдущего кадра). Получившийся массив разниц заносится в закодированный видеопоток.

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

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

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

Алгоритмом поддерживаются цветовые пространства RGB и YCbCr. Декодирование всегда осуществляется в цветовое пространство RGB. Задание изменений цветовых плоскостей может быть сделано как в виде прямых значений, так и в виде процентных отношений. Прямое значение - это натуральная величина изменения цветовой плоскости. Процентное отношение - величина изменения, выраженная в диапазоне от 0 до 100 процентов.

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

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

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

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

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

Следующее поведение в общем видеопотоке всегда принадлежит той цветовой плоскости пикселя, которая достигла края своей прямой (декодер уже отрисовал для нее прямую). Поэтому в алгоритме вообще нет необходимости в указывании каких-либо координат. Как и при кодировании, каждый кадр декодируется анализом линий кадра сверху-вниз с проходом цветовых плоскостей пикселей каждой линии слева-направо. Координаты алгоритму не нужны, так как, двигаясь по пикселям линий, он следит за выполнением поведения каждой цветовой плоскости. У кого поведение закончилось (прямая линия отрисована), значит, его новое поведение находится сейчас в видеопотоке. А координаты декодеру уже известны, потому что он остановился на том месте (координатах), у кого закончилось поведение.