Диссертация (Методы и устройство формирования сигналов в цифровых видеоинформационных системах), страница 5

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

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

В зависимости от способа формирования кода, такиеалгоритмы кодирования принято разделять на три группы:1. Статические алгоритмы сжатия;2. Адаптивные алгоритмы сжатия;3. Динамические алгоритмы сжатия.К статическим алгоритмам сжатия относят код Хаффмана [5,6]. Идея этогокода заключается в том, что часто используемые символы в сообщениипередаются коротким кодом, реже используемые символы – длинным.

Процесскодирования по Хаффману является одним из самых простых и понятных.Вначале символы алфавита располагают в порядке убывания вероятностей ихпоявления. Далее два символа, вероятности которых наименьшие, объединяют водин новый составной символ, при этом вероятность составного символа будетравна сумме вероятностей символов, из которых он составлен. Затем символыснова располагают в порядке описанном в начале. Эти два процессапродолжаются до момента, когда все символы будут объединены. Назавершающей стадии последнему символу, вошедшему в состав составногосимвола, присваивают значение 0, а остальной части – 1. Процесс присвоенияпродолжается до тех пор, пока всем символам не будут присвоены значения.

Длянаглядности процесс формирования изображают в виде дерева или в нашемслучае схемой. На рисунке 1.7 представлена схема кодирования для сообщения а1а1 а1 а2 а2 а3 а3 а4 а5 а6.27а2а3а4а5а6P=0,3P=0,2P=0,2P=0,1P=0,1P=0,101а1а2а3а4а 5а 6P=0,3P=0,2P=0,2P=0,1P=0,201а1а2а 3а 4а 5а 6P=0,3P=0,2P=0,3P=0,201а1а 2а 5а 6а 3а 4P=0,3P=0,4P=0,301а 1а 3а 4а 2а 5а 6P=0,6P=0,401Направление присвоения “0” и “1”Направление объединения символова1а1а3а4а2а5а6P=1Рисунок 1.7. Схема кодирования кодом Хаффмана.После кодирования символам присваиваются префиксные коды различнойдлины. Пример присвоенных кодов для кодирования на рисунке 1.7 приведен втаблице 1.1.Таблица 1.1. Кодирование кодом Хаффмана для рисунка 1.7Символа1а2а3а4а5а6Код001001001111011128С момента открытия Хаффманом своего кодирования прошло немаловремени, но оно, в силу своей оптимальности для кодов переменной длины, всееще остается достаточно популярным в кодировании текста, изображений, аудиои видеоинформации.Не смотря на простоту реализации, испытанность временем и популярность,кодированиеХаффманаимеетсвоинедостатки.Основнымнедостаткомкодирования Хаффмана является то, что максимальная эффективность сжатиядостигается в случае отражения значений вероятности символов величиной 2-n,где n - целое число.

В противном случае действительная степень сжатияотличается от эффективного значения. Снижение эффективности обусловленопоявлениемизбыточностивкодесимволов,котораяпоявляетсяприиспользовании целого числа бит.Кроме этого, для каналов передачи данных играют роль и другиенедостатки этого кодирования: неодинаковые длины кодов, что приводит к неравномерным задержкамдекодирования; за счет снижения избыточности при кодировании, сжатый поток становитсяболее уязвимым к появлению в последовательности кода ошибок. Этоприводитктому,чтоодинневернодекодированныйбитвпоследовательности приводит к неверному декодированию последующихсимволов закодированной последовательности; при кодировании по Хаффману предполагается наличие известныхвероятностей появления символов, но в реальности эти вероятностинедоступны.

Это приводит к тому, что при реализации кодека необходимозаставлять кодек сжимать сообщение в два этапа – один для наборастатистикиисоставлениякодовойтаблицы,второй–длянепосредственного сжатия. Кроме того, эта же статистика должна бытьизвестна декодеру, что подразумевает её передачу вместе с закодированнымсообщением.29Примером адаптивного алгоритма служит модифицированное кодированиеХаффмана [5]. Отличительной чертой этого кодирования от классическогостатического кода Хаффмана является то, что нет необходимости знатьвероятностисимволовзаранее,кодированиепоступленияданных.Дерево,приэтом,осуществляетсяадаптивновпроцессеподстраиваетсякполучающейся последовательности.

Такой подход позволяет исключить изработы кодека этап набора вероятностной статистики и дальнейшей ее передачина декодер.К динамическим алгоритмам сжатия следует отнести арифметическоекодирование [5]. Арифметическое кодирование является хорошей альтернативойалгоритмамХаффмана.Крометого,наэффективностьсжатияприарифметическом кодировании не влияет зависимость вероятностей символов отвеличины 2-n. Идея арифметического кодирования заключается в присвоении кодане отдельным символам, образующим сообщение, а сообщению в целом.Объяснить идею кодирования проще на следующем примере. Имеется сообщение,представленное набором символов a1 a2 a3 a1 a1 a4 a5 a3 a1 a1.

Вероятности появленияэтих символов равны: a1 = 0,5; a2 = 0,1; a3 = 0,2; a4 = 0,1; a5 = 0,1.Варифметическом кодировании символы выражаются значениями из интервала вдиапазоне чисел [0; 1). Диапазон каждого символа определен в соответствии свероятностями появления этих символов. Для нашего сообщения символы будутвыражены интервалами, представленными на рисунке 1.8.Рисунок 1.8.

Присвоенные символам интервалы в диапазоне чисел [0,1)Далее кодек последовательно считывает символы из сообщения ираспределяет их вероятности в диапазоне чисел, который будет меняться взависимости от вероятности предыдущего символа, т.е., если первым следуетсимвол а1 и соответственно его интервал [0,5; 1), следующий за ним символ a2должен укладываться в интервале символа а1 с соблюдением пропорций30интервала присвоенного a2 на начальном этапе. Эта идея поясняется на рисунке1.9.Рисунок 1.9. Процесс арифметического кодирования сообщенияДля того, чтобы вычислить новый интервал для последующего символа сучетом пропорций, пользуются формулами 1.3 и 1.4.y   x   y  x   y ',(1.3)x  x   y  x   x ',(1.4)где:x – нижняя граница интервала предыдущего символа;y – верхняя граница интервала предыдущего символа;x’ – нижняя граница присвоенного, на начальном этапе, интервалатекущего символа;y’ – верхняя граница присвоенного, на начальном этапе, интервалатекущего символа;x’’ – новая нижняя граница текущего символа в интервалепредыдущего символа;y’’ – новая верхняя граница текущего символа в интервалепредыдущего символа.Процесс вычисления новых интервалов продолжается до получениязначения переменной x’’ конечного символа сообщения, при этом в записи этого31значения исключается целая часть, т.е.

0. В нашем случае число 0,71753375 будетпредставлено значением 71753375.Окончательным кодом арифметического кодирования, который будетприсвоен нашему сообщению, является любое число из диапазона [0,71753375;0,717535). Для примера, с учетом исключения “0,” это может быть число 717534как самое короткое.На практике идея арифметического кодирования в чистом виде, описаннаявыше, не используется, вследствие того, что конечный результат такойарифметической операции может приобретать бесконечную точность, что нереализуемо на любой из современныхаппаратных частях кодирующегоустройства.

Поэтому для реализации применяют модифицированный вариантэтойидеи.Вмодифицированномвариантеимеетместоискусственноеограничение точности, где значения переменных x’’ и y’’ не превышают длины в16 или 32 бита. В этом случае все переменные в формулах 1.3 и 1.4представляются целыми числами, апеременной y’’ присваивается, вместозначения 1, значение 9999, которое соответствует бесконечной десятичной дроби0,(9). Поэтому, если вначале символ а1 с интервалом [0;1) имел границы спределамиy   x   y  x   y   0, 0  1, 0  0, 0   1,0  1,x  x   y  x   x  0,0  1,0  0, 0   0,5  0,5,то, с учетом необходимости представление переменных целыми значениями, вмодифицированном варианте границы символа а1 будут иметь пределыy  x   y  x   y   0  10000  0   1,0  10000,x  x   y  x   x  0  10000  0   0,5  5000,учитывая тот факт, что граница переменной y’’ является открытой – 10000 невключается, нам необходимо из этой переменной вычесть 1.

Тогда переменная y’’будет иметь значениеy  x   y  x   y   0  10000  0   1,0  1  9999.32Если в процессе вычисления кода самые левые цифры в переменных x’’ иy’’ совпадают, то переменные x’’ и y’’ сдвигаются на одну позицию влево, затем всамую правую позицию переменной x’’ записывается 0, а в самую правуюпозицию переменной y’’ записывается 9.Промежуточные результаты процесса кодирования модифицированнымметодом нашего примера сообщения представлены в таблице 1.2.Таблица 1.2.

Результаты расчеты числового кода для сообщения a1 a2 a3 a1 a1 a4 a5 a3a1 a1КодируемыйсимволОперация вычислениясообщенияa1a2a3a1a1a4a5a3a1a1y’’ = 0+(10000-0)*0.5x’’ = 0+(10000-0)*1.0-1y’’ = 5000+(10000-5000)*0.4x’’ = 5000+(10000-5000)*0.5y’’ = 0+(5000-0)*0.2x’’ = 0+(5000-0)*0.4-1y’’ = 0+(10000-0)*0.5x’’ = 0+(10000-0)*1.0-1y’’ = 5000+(10000-5000)*0.5x’’ = 5000+(10000-5000)*1.0-1y’’ = 7500+(10000-7500)*0.0x’’ = 7500+(10000-7500)*0.1-1y’’ = 5000+(7500-5000)*0.1x’’ = 5000+(7500-5000)*0.2y’’ = 2500+(5000-2500)*0.2x’’ = 2500+(5000-2500)*0.4-1y’’ = 0+(5000-0)*0.5x’’ = 0+(5000-0)*1.0-1y’’ = 2500+(5000-2500)*0.5x’’ = 2500+(5000-2500)*1.0-1РезультатПрисваиваемоеоперациикодирующеевычислениязначение500099997000749910001999500099997500999975007749525054993000349925004999375049997175337504999По завершению кодирования получается диапазон [0,717533750; 0,717535).Таким образом, для того чтобы закодировать сообщение a1 a2 a3 a1 a1 a4 a5 a3 a1a1 нам потребуется число 717534, которое будет занимать 20 бит –3310101111001011011110.

Такой объем очень близок к энтропии нашего сообщения,которая составляет 19,6 бит и соответственно показывает высокую эффективностьарифметического кодирования.Если сообщение a1 a2 a3 a1 a1 a4 a5 a3 a1 a1 закодировать кодом Хаффмана, то навыходе также получим 20 битовую последовательность, но при кодированииболее длинных последовательностей в сообщениях, арифметическое кодированиеокажется наиболее эффективным для применения.

В силу этого, кодеры,реализующие арифметическое кодирование, являются одними из лучших средиэнропийных кодеров сжатия.Однако в отличие от кодирования по Хаффману, арифметическое являетсяболее сложным для реализации из-за не полноценной универсальности идеиработы этого алгоритма. Речь идет о том, что для сообщений, символы которыхимеют специфический набор вероятностей или последовательность следования,кодек должен работать несколько иначе и в случае, если в кодере непредусмотрены режимы для сжатия таких последовательностей, сообщениеокажется сжато не эффективно. Кроме этого, арифметическое сжатие производитбольшееколичествоарифметическихопераций,чемХаффмана,чтоподразумевает использование больших мощностей аппаратных ресурсов.Одним из самых современных на данный момент энтропийных методоварифметическогокодирования,полностьюадаптированныйдлясжатиявидеоинформационного сигнала, является метод CABAC (Context-adaptive binaryarithmeticcoding-Контекстно-адаптивноедвоичноеарифметическоекодирование) [7, 47].