Контекстно-адаптивное двоичное арифметическое кодирование. Часть 2

ГЛАВА 7

Последовательность действий, выполняемых при арифметическом кодировании, представленная в виде блок схемы. 

Попробуем представить последовательность действий, выполняемых при арифметическом кодировании в виде блок-схемы. Пусть алфавит передаваемого сообщения состоит из набора символов  (в рассмотренных выше примерах этот алфавит состоял из трех символов , при этом для символа  значение i равно 1, для символа , соответственно, i равно 2, для EOF – i равно 3). Сформируем массив из значений , где  относительная частота появления в сообщении i-го символа.  положим равным нулю, а , где N – количество символов в алфавите. (Опять, если вернуться к рассмотренному выше примеру кодирования, то , а . При введенных обозначениях, последовательность действий, выполняемых при арифметическом кодировании каждого символа, можно представить в виде диаграммы, изображенной на рис. 1.

Рис 1. Блок-схема процедуры арифметического кодирования

Процедура EncodeSymbol() принимает два аргумента: i – номер кодируемого символа в алфавите, P – массив значений . Как видно из блок-схемы, на первом этапе кодирования выполняется вычисление длины текущего интервала  (при этом используются текущие значения нижней  и верхней  границ интервала). Величина  используется для вычисления новых обновленных значений границ интервала. Таким образом, на первом этапе кодирования каждого символа сообщения выполняется деление текущего отрезка. Второй этап кодирования представляет собой процедуру ренормализации, блок-схема которой представлена на рис. 2.

Рис 2. Блок-схема процедуры ренормализации

Как уже было сказано при описании процедуры ренормализации, если текущий интервал полностью лежит в диапазоне [0, 1), т.е. если , то в выходной битовый поток записывается значение 0 и последовательность из значений 1, длина которой равна значению переменной bitsOutstanding. Все эти действия выполняются процедурой put_bits(), блок-схема которой представлена на рис. 3. Значения границ интервала  и  удваиваются.

Если текущий интервал полностью лежит в диапазоне , т.е. если , то в выходной поток записывется 1 и последовательность из 0, длина которой равна значению переменной bitsOutstanding (здесь опять используется процедура put_bits()). Изменение значений границ интервала в этом случае происходит таким образом, чтобы в два раза увеличилось расстояние от  и  до 1. Обновленные значения  и , таким образом, можно рассчитать как:

,

,

что и выполняется в этой ветви процедуры RenormE.

Наконец, если текущий интервал полностью лежит в диапазоне , т.е. если , и , то значение величины bitsOutstanding увеличивается на 1, а границы интервала сдвигаются таким образом, чтобы в два раза увеличилось расстояние от  и  до  :

,

,

что и выполняется в этой ветви процедуры RenormE.

На рис. 3 представлена блок-схема процедуры put_bits(). Эта процедура принимает в качестве аргумента значение бита (0 или 1) и записывает его в выходной битовый поток, представляющий результат арифметического кодирования. Процедура записи бита в поток на блок-схеме условно обозначена как write_bit(). После выполнения записи производится проверка значения переменной bitsOutstanding. Производится запись в поток последовательности значений !b (здесь в блоксхеме использовано обозначение операции «НЕ» из языка C), длина которой равна значению bitsOutstanding.

Рис 3. Блок-схема процедуры put_bits()

13 июня 2019

Читать другие статьи:

Глава 1. Просто о видеокодировании

Глава 2. Межкадровое (Inter) предсказание в HEVC

Глава 3. Пространственное (Intra) предсказание в HEVC

Глава 4. Компенсация движения в HEVC

Глава 5. Постпроцессинг в HEVC

Глава 6. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 1

Глава 8. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 3

Глава 9. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 4

Глава 10. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 5

Автор:

Олег Пономарев - 16 лет занимается вопросами видео кодирования и цифровой обработки сигналов, специалист в области распространения радиоволн, статистической радиофизики, доцент кафедры радиофизики НИ ТГУ, кандидат физико-математический наук. Руководитель исследовательской лаборатории Elecard.

Инструмент для детального анализа этапов кодирования видеопоследовательности - Elecard StreamEye

Инструмент для сравнения параметров видео, закодированного разными энкодерами