Алгоритм сжатия видео 'pixel behaviour check'
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
?з 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 кадров красной цветовой плоскости верхнего пикселя (прямо над текущим) в точности повторяли значения текущего пикселя. Значения красной цветовой плоскости пикселя справа тоже в точности повторяли текущий пиксель, но были как бы смещены на один кадр. Машина ехала через кадр с правой стороны, поэтому первым зацепила правый пиксель, а текущий пиксель воспроизвел ту же последовательность поведений цветовой плоскости, но с запозданием в один кадр. Нечего и говорить о том, что верхний пиксель над правым почти полностью походил по поведению (все же у него имелись различия в нескольких кадрах) на правый пиксель. Сбросив в свободный элемент массива п