Алгоритм сжатия видео '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-алгоритма (RunLength 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.
typeColorPlane = 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; // опорный кадр
procedureCreateNextFrame;
var
I:DWord; // индекс плоскости в массиве опорного кадра
L:DWord; // количество элементов в массиве опорного кадра
C:Byte; // код только что прочитанного поведения
R:Word; // количество повторов поведения
E:Byte; // величина изменения плоскости за весь период поведения
begin
L := Length(Frame);
I := 0;
whileI
//если еще остались повторы для текущей цветовой плоскости,
//тогда вычислить значение цветовой плоскости для
// текущего кадра
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;
endelse 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;
endelse 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
//читаем следующее поведение набора (индекс следующего
//поведения уже находится в Frame[I].cpBehaviour),
//а результат чтения возвращается в переменные C, R и E
GetBehaviour(Frame[I].cpIndex, Frame[I].cpBehaviour, C, R, E);
//следующим циклом обеспечиваем поддержку безвозратной вложенности
//наборов поведений
whileC = 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;
endelse begin
//сбрасываем cpIndex в 0FFFFh, так как мы уже читаем поведение
//из видеопотока, а не из массива поведений
Frame[I].cpIndex := $FFFF;
Frame[I].cpBehaviour := 0;
//А теперь читаем поведение из видеопотока. Следующий фрагмент
//кода один в один похож на участок рассмотренного выше кода,
//поэтому здесь я его не комментирую
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;
GetBehaviour(Frame[I].cpIndex, Frame[I].cpBehaviour, C, R, E);
end;
Frame[I].cpCode := C;
Frame[I].cpRepeat := R;
Frame[I].cpExtent := E / R;
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;
Послецикла по всем элементам массива опорного кадра в полях cpCurrent элементовмассива находятся значения, которые должны быть занесены в реальный кадр наэкране. Собственно говоря, картинка реального кадра уже получена в опорномкадре, но данные картинки еще нужно перевести из процентных отношений в прямыезначения, если они не были такими (установлен бит RatioType поля Propertiesзаголовка видеопотока). Затем полученные прямые значения нужно перевести изYCbCr в RGB, если установлен бит ColorSpace поля Properties. Но нужно обратитьвнимание, что содержимое полей cpCurrent элементов массива опорного кадра ни вкоем случае нельзя изменять, так как нам нужны непереведенные значения длядекодирования следующего кадра. Для перевода из YCbCr в RGB необходимоизвлекать из массива опорного кадра сразу по три цветовых плоскости пикселя,потому что формулам преобразования YCbCr в RGB нужны значения трех плоскостей.Поэтому процедура отображения кадра на экране будет иметь два цикла — по высотеи по ширине кадра.
//глобальные переменные
var
Header:PBCvideoHeader; // заголовок видеопотока
Frame: array of ColorPlane; // опорный кадр
FrameNum: DWord; // номер текущего кадра
procedure ShowFrame;
var
W: Word; // ширина
H:Word; // высота
I:DWord; // индекс плоскости в массиве опорного кадра
Y:Double; // значение плоскости Y
Cb:Double; // значение плоскости Cb
Cr:Double; // значение плоскости Cr
R:Byte; // значение красного цвета
G:Byte; // значение зеленого цвета
B:Byte; // значение синего цвета
begin
//в цикле рисуем все пиксели на реальном экране
// (допустим его имя VideoScreen)
for H := 1 to Header.Height do begin
for W := 1 to Header.Width do begin
I := (H-1) * Header.Width * 3 + (W-1) * 3;
//читаем значения трех цветовых плоскостей пикселя
//из соответствующих элементов массива опорного кадра
Cr := Frame[I].cpCurrent;
Y := Frame[I+1].cpCurrent;
Cb:= Frame[I+2].cpCurrent;
//если значения заданы с помощью процентных
//отношений (установлен бит RatioType поля Properties),
//тогда перевести их в прямые значения
if Header.Properties and 2 0 then begin
Cr := Cr * (256 / 100);
Y := Y * (256 / 100);
Cb := Cb * (256 / 100);
end;
//если прямые значения необходимо перевести
//из YCbCr в RGB (установлен бит ColorSpace поля Properties),
//тогда перевести их в RGB, иначе они уже заданы в виде RGB
if Header.Properties and 1 0 then begin
R := Trunc(Y + 1.402 * (Cr — 128));
G := Trunc(Y — 0.34414 * (Cb — 128) — 0.71414 * (Cr — 128));
B := Trunc(Y + 1.772 * (Cb — 128));
end else begin
R := Trunc(Cr);
G := Trunc(Y);
B:= Trunc(Cb);
end;
//а теперь осталось занести цвет пикселя (он находится
//в переменных R, G и B) в реальный кадр на экране, где
//координаты пикселя заданы переменными W и H
//(в Canvas цвет хранится как BGR, а не как RGB)
VideoScreen.Canvas.Pixels[W-1, H-1] := (B * $10000) or (G * $100) orR;
end;
end;
//+1 кадр видеофильма показали на экране,
//и если видеопоток закончился (счетчик кадров
//достиг количества кадров в видео), тогда остановить программу
Inc(FrameNum);
if FrameNum >= 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. Такжедопускается не использовать массив поведений, но даже в этом случае он обязанприсутствовать в закодированном видеопотоке в виде пустого массива.
Вобщем видеопотоке находятся разрозненные поведения цветовых плоскостей пикселейи ссылки на уже существующие в массиве поведений наборы поведений. Разрозненноеповедение представляет собой одиночное поведение, мало встречающееся средиповедений цветовых плоскостей пикселей. Ссылка на набор поведений обозначает,что для некоторой цветовой плоскости под ссылкой подразумевается целаяпоследовательность из нескольких поведений, которая уже описана в ссылаемомнаборе поведений.
Алгоритмдопускает внедрять в общий видеопоток любые дополнительные данные. Такие данныеназываются внедренными блоками данных. Они игнорируются алгоритмом, но он имеетвозможность прерывать декодирование видео и передавать эти блоки на обработкуразным специальным функциям (при наличии таких), а после восстанавливатьдекодирование с прерванного места.
Декодированиевоссоздает кадры видео по содержимому закодированного видеопотока. На основеопорного кадра и извлекаемых из видеопотока данных строится первый кадр видео.Каждый следующий кадр строится на основании содержимого текущего кадра. Декодерпреобразует извлекаемые из общего видеопотока поведения в прямые линии изначение каждой цветовой плоскости пикселей кадра движется в точности по своемунабору прямых линий.
Следующееповедение в общем видеопотоке всегда принадлежит той цветовой плоскостипикселя, которая достигла края своей прямой (декодер уже отрисовал для неепрямую). Поэтому в алгоритме вообще нет необходимости в указывании каких-либокоординат. Как и при кодировании, каждый кадр декодируется анализом линий кадрасверху-вниз с проходом цветовых плоскостей пикселей каждой линии слева-направо.Координаты алгоритму не нужны, так как, двигаясь по пикселям линий, он следитза выполнением поведения каждой цветовой плоскости. У кого поведениезакончилось (прямая линия отрисована), значит, его новое поведение находитсясейчас в видеопотоке. А координаты декодеру уже известны, потому что оностановился на том месте (координатах), у кого закончилось поведение.
Список литературы
Дляподготовки данной работы были использованы материалы с сайта www.sciteclibrary.ru