Xreferat.com » Рефераты по информатике и программированию » Алгоритм сжатия видео 'pixel behaviour check'

Алгоритм сжатия видео 'pixel behaviour check'

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

Если вы умеете программно оперировать видеоданными и имеете свободное время, предлагаю вам закодировать PBC-алгоритм сжатия видеопотока. Сразу скажу, что алгоритм новый и никем не опробованный (для справки: статье уже почти два года). По этой же причине не могу утверждать, что он лучше или хуже MPEG4 или DivX-алгоритмов. Мой алгоритм использует подход к кодированию видео, отличный от MPEG, и эффективен только для кодирования последовательности видеокадров.

Основные особенности MPEG

Для начала хочу коротко объяснить основную идею MPEG-алгоритма (DivX является одной из версий MPEG4). Шифрация видеоданных в MPEG в своей основе использует алгоритмы шифрации спецификации JPEG. Дополнительно в MPEG используются алгоритмы компенсации движения, I-кадры и т.д. и т.п. Но рассмотрим, как в JPEG кодируется статический кадр изображения.

Сначала все цветовое пространство кадра преобразуется из RGB в YCbCr. Необходимость этого преобразования заключается в том, что глаз более чувствителен к яркости цвета, чем к его оттенку. Y - это величина яркости цвета, а Cb и Cr - цветовые величины, определяющие оттенок и насыщение цвета (они определяют количество синей и красной составляющих в цвете). Уже на этом этапе происходят потери в информации, так как формулы преобразования RGB в YCbCr и обратно не позволяют точно (значение в значение) сохранить некоторые цвета. Как вы заметите в дальнейшем, JPEG-алгоритм рассчитан на максимальную потерю избыточной информации. Этим-то и достигается высокая степень сжатия.

Затем проводится дискретизация изображения. Это еще один способ потерять информацию, но уже в больших объемах. Идея в том, что яркость (Y) берется для каждого пикселя изображения, а цветоразность (Cb, Cr) - как среднее значение блока 2x2 пикселей. Вообще-то в стандарте JPEG для Y, Cb и Cr определено по два коэффициента дискретизации: по горизонтали и по вертикали. Поэтому хоть яркость, хоть цветоразность при желании можно брать как среднее значение любого по размерам блока (хоть 10x10 пикселей). В конечном итоге это отразится на качестве зашифрованного изображения. Большие значения дискретизации - первый шаг к получению "зубчатого" изображения.

После этого проводится дискретное косинусоидальное преобразование (DCT) изображения, которое делится на блоки 8x8 пикселей, и к каждому блоку применяется DCT-преобразование. Цель этого в том, чтобы получить по 64 амплитуды частотного пространства для каждого из блоков 8x8 пикселей. Затем 64 амплитуды зигзагообразно переставляются в блоке, чтобы получить вектор с 64 коэффициентами, отсортированный критериями пространственной частоты.

Теперь каждый вектор из 64 коэффициентов квантуется с помощью заранее заданных таблиц квантования. Это нужно для того, чтобы удалить высокие частоты, которые представляют собой высокую детализацию данного блока изображения. В результате квантованный вектор содержит большое количество расположенных подряд нулей. Ну и весь вектор кодируется уже с помощью самого обычного RLE-алгоритма (Run Length Encoding). В заключении к полученному набору байт применяется кодирование Хаффмана, которое позволяет записать байты длины RLE-кодирования с самыми минимальными затратами бит.

Алгоритм MPEG через определенное количество кадров всегда создает I-кадр, который кодируется подобно JPEG. В кадрах между I-кадрами закодирована компенсация движения блоков изображения. Как видите, MPEG имеет довольно сложный алгоритм.

Алгоритм "Pixel Behaviour Check"

Алгоритм имеет название "Контроль поведения пикселя". Основная идея в том, что мы рассматриваем каждый пиксель как объект, имеющий поведение. И кодирование ведется не относительно текущего кадра, а сквозь кадры. Как будто кадры расположены один над другим, а мы смотрим сквозь них и регистрируем поведение каждого пикселя. Поведение пикселя имеет три состояния: остается неизменным, начинает расти или уменьшаться. Пиксель остается неизменным, когда на протяжении нескольких кадров значение его цвета не изменяется. Пиксель растет, когда значение его цвета из кадра в кадр продолжает увеличиваться. Пиксель уменьшается, когда значение его цвета постоянно уменьшается.

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

type PBCvideoHeader = record

Width: Word; // ширина кадра видеофильма

Height: Word; // высота кадра видеофильма

FrameCount: DWord; // количество кадров в видеофильме

FrameRate: Byte; // скорость кадров (кадров в секунду)

Properties: Byte; // свойства кодирования

StartRCr: Byte; // начальное заполнение плоскости красного цвета / Cr

StartGY: Byte; // .............................. зеленого цвета / Y

StartBCb: Byte; // .............................. синего цвета / Cb

end;

Думаю, с полями Width и Height все понятно - в них хранятся высота и ширина кадра в пикселях. Поле FrameCount содержит общее количество кадров в видеопотоке, а поле FrameRate - скорость следования кадров, измеряемую в кадрах в секунду. Поле Properties содержит сведения об особенностях кодирования видео. Дело в том, что алгоритм поддерживает как RGB-пространство, так и YCbCr. Кроме этого передача изменений пикселя может быть как в виде прямых значений, так и с помощью процентных отношений (позже объясню, что значит "прямые значения", а что "процентные отношения"). Эти сведения указываются в двух младших битах поля 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 - два или три байта.

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

Алгоритм сжатия видео 'pixel behaviour check'

Процентное отношение - это та же самая разница между значениями цветовой плоскости пикселя, но выраженная в диапазоне от 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-поля следует продолжение видеопотока. Декодер знает размер блока внедренных данных, знает адрес (или смещение) этого блока, и может вызывать некоторую специальную функцию, обрабатывающую ваши внедренные данные. Затем декодер на основе размера блока

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: