ГЛАВА 8
Как двоичный характер закодированной информации изменяет процедуру кодирования и декодирования
Входной поток символов должен быть двоичным!
Из самого названия CABAC (Context Adaptive Binary Arithmetic Coding) следует, что в HEVC используется двоичная версия арифметического кодирования, когда алфавит входного сообщения состоит всего из двух символов (0 и 1). Чтобы различать слова, используемые для обозначения битов выходного потока, представляющего результат кодирования, и двоичные символы, представляющие кодируемое сообщение, эти символы называют «бинами». Посмотрим, что изменится, если в представленных на рис. 2 – 4 блок-схемах учесть двоичный характер кодируемого сообщения.
Прежде всего, необходимо отметить, что из алфавита исчезает символ EOF, использовавшийся для обозначения конца сообщения. Информация об окончании сообщения необходима при декодировании. При отсутствии такой информации процедура декодирования будет продолжаться даже после правильного декодирования всего сообщения. Как в HEVC реализуется передача информации о конце сообщения мы рассмотрим позднее. Здесь же отметим только необходимость реализации процедуры такой передачи.
Что еще поменяется в случае кодирования сообщения, состоящего только из двух символов? Массив $\displaystyle P$, содержащий кумулятивные вероятности символов, будет содержать теперь только три значения: $\displaystyle P=\{0,P_{MPS} ,1\}$. За $\displaystyle P_{MPS}$ здесь обозначена вероятность появления в сообщении более вероятного символа (если мы из нашего 20-ти символьного сообщения {b, a, b, b, b, b, b, b, b, b, a, b, b, b, b, b, b, b, b, EOF} уберем символ EOF, то длина сообщения станет равна 19, а вероятность более вероятного символа «b» будет равна $\displaystyle \frac{17}{19}$). Т.о. текущий отрезок $\displaystyle [ L,H)$ теперь при кодировании будет все время делиться на две части. Длина большей части определяется вероятностью $\displaystyle P_{MPS}$, меньшей – вероятностью $\displaystyle P_{LPS} =1-P_{MPS}$. Массив $\displaystyle P$, по сути дела, выродился в одно число. Этим числом может быть $\displaystyle P_{MPS}$, но с тем же успехом этим числом может быть и $\displaystyle P_{LPS}$.
До сих пор положение на числовой оси текущего отрезка, который мы делим при кодировании сообщения, характеризовалось положением конечных точек этого отрезка $\displaystyle L$ и $\displaystyle H$. Очевидно, что описывать текущее состояние процедуры арифметического кодирования (положение отрезка на числовой оси) можно и с помощью чисел $\displaystyle L$ и $\displaystyle R$, где $\displaystyle R$ – длина отрезка. Именно такое описание используется в стандарте HEVC.
Итак, пусть число, характеризующее соотношение частей отрезка при его итеративном делении, будет равно $\displaystyle P_{LPS}$. Обозначим, используя обозначения из стандарта HEVC, значение (0 или 1) наиболее вероятного бина в кодируемой последовательности за $\displaystyle valMPS$. Значение текущего кодируемого бина будем характеризовать величиной $\displaystyle binVal$. Положение левой границы текущего интервала по-прежнему будем обозначать значением $\displaystyle L$. Длину текущего интервала – $\displaystyle R$. В том случае, если значение текущего кодируемого бина равно $\displaystyle valMPS$, вычисление новых значений $\displaystyle L$ и $\displaystyle R$ по их текущим значениям и $\displaystyle P_{LPS}$можно вычислить как (рис. 1):
\begin{array}{l}R=R( 1-P_{LPS}) =R-R\cdotp P_{LPS},\\\end{array}
\begin{array}{l}L=L.\end{array}
Рис. 1. Определение значений $\displaystyle L$ и $\displaystyle R$ при $\displaystyle binVal\equiv valMPS$
В том же случае, когда значение кодируемого бина не совпадает со значением $\displaystyle valMPS$, новые значения $\displaystyle L$ и $\displaystyle R$ определяются выражениями (рис. 2):
\begin{array}{l}R=R\cdotp P_{LPS},\\\end{array}
\begin{array}{l}L=L+R( 1-P_{LPS}).\end{array}
Рис. 2. Определение значений$\displaystyle L$ и $\displaystyle R$ при $\displaystyle binVal!=valMPS$
В результате получаем несколько обновленную блок-схему (рис. 3) алгоритма теперь уже двоичного арифметического кодирования.
Рис. 3. Блок-схема алгоритма процедуры кодирования бина
Процедуру ренормализации при переходе к двоичному кодированию можно было бы и не менять. С другой стороны, небольшие изменения процедуры ренормализации могут несколько упростить алгоритм и снизить вычислительные затраты. В новых терминах $\displaystyle L$ и $\displaystyle R$ процедура ренормализации выполняется циклически до тех пор, пока значение $\displaystyle R< \frac{1}{2} $. Если при этом $\displaystyle L+R< \frac{1}{2}$, то значение закодированного бита определено и равно 0. Если же $\displaystyle L >\frac{1}{2}$ , то значение закодированного бита равно 1 (упрощенно, детально процедура описана на рис. 2 Части 2 и в пояснениях к нему). Очевидно, что значения закодированных битов будут полностью определены и в том случае, когда $\displaystyle R< \frac{1}{4}$. Если при этом $\displaystyle L< \frac{1}{4}$, то текущий отрезок полностью лежит в области $\displaystyle \left[ 0,\frac{1}{2}\right] $ и, таким образом, значение закодированного бита равно 0. В том случае, когда $\displaystyle R< \frac{1}{4}$ и $\displaystyle L\geqslant \frac{1}{2}$, текущий отрезок полностью лежит в области $\displaystyle \left[\frac{1}{2} ,1\right] $, а значение закодированного бита равно 1. Блок-схема модифицированной процедуры ренормализации при кодировании приведена на рис. 4.
Рис. 4. Блок-схема алгоритма ренормализации при кодировании
Посмотрим теперь, как двоичный характер закодированной информации изменит процедуру декодирования. Процедура арифметического декодирования заключается в этом случае в итеративном делении текущего отрезка на две части, длины которых пропорциональны $\displaystyle 1-P_{LPS}$ и $\displaystyle P_{LPS}$. При каждом делении производится проверка какому из двух интервалов принадлежит двоичное число, представляющее закодированное сообщение. Этот интервал и становится текущим.
Пусть несколько бит закодированного сообщения содержатся в переменной $\displaystyle ivl0ffset$ (используем здесь обозначение этой переменной из стандарта HEVC). Текущий отрезок по-прежнему будем характеризовать положением на числовой оси его левого конца $\displaystyle L$ и его длиной $\displaystyle R$. Процедура декодирования иллюстрируется на рис. 5, где представлены две последовательные итерации. В первой из них число $\displaystyle ivlOffset$ (положение числа внутри текущего отрезка отмечено кружком) содержится внутри отрезка $\displaystyle [ L,L+R( 1-P_{LPS})]$. Как следствие, декодированный бин имеет значение $\displaystyle valMPS$. На второй итерации $\displaystyle ivlOffset$ попадает в меньший из интервалов и декодированный бин имеет значение $\displaystyle!valMPS$.
Рис. 5. Деление отрезка при декодировании
Из рисунка видно, что выбор отрезка на каждой итерации определяется сравнением значения $\displaystyle ivlOffset$ с правой границей интервала $\displaystyle L+R\cdotp ( 1-P_{LPS})$. В случае, когда $\displaystyle ivlOffset$ попадает в больший отрезок, соответствующий вероятности $\displaystyle P_{MPS}$, величина $\displaystyle R$ приобретает новое значение $\displaystyle R\cdotp ( 1-P_{LPS})$, а величина $\displaystyle L$ не меняется. В том же случае, когда $\displaystyle ivlOffset$ попадает в меньший отрезок, соответствующий вероятности $\displaystyle P_{LPS}$, левая граница интервала смещается на точку $\displaystyle L+R\cdotp ( 1-P_{LPS})$, а новое значение $\displaystyle R$ определяется как $\displaystyle R\cdotp P_{LPS}$. Заметим также, что во втором случае вместо изменения значения $\displaystyle L$ можно изменить значение величины $\displaystyle ivlOffset$ на значение $\displaystyle ivlOffset-R\cdotp ( 1-P_{LPS})$. Теперь значение $\displaystyle ivlOffset$ характеризует не само двоичное число, представляющее закодированное сообщение, а положение этого числа относительно левой границы текущего интервала. Тогда величина $\displaystyle L$, сама по себе, перестает использоваться в процедуре декодирования. Для принятия решения о том, какой из двух отрезков на каждой итерации сделать текущим, достаточно сравнить значение $\displaystyle ivlOffset$ с величиной $\displaystyle R\cdotp ( 1-P_{LPS})$. Блок-схема алгоритма декодирования приведена на рис. 6.
Рис. 6. Блок-схема алгоритма декодирования
Изменение смысла величины $\displaystyle ivlOffset$ при двоичном декодировании также существенно меняет (упрощает) и процедуру ренормализации. Процедура ренормализации запускается в том случае, когда длина текущего интервала становится меньше $\displaystyle \frac{1}{4}$. Также как и ранее ренормализация удваивает величину $\displaystyle R$. Однако, теперь вычислять величину $\displaystyle L$ нет необходимости. Т.к. теперь значение $\displaystyle ivlOffset$ – это разница между числом, представляющим закодированное сообщение и левой границей текущего интервала, то при нормализации достаточно безусловно удвоить число $\displaystyle ivlOffset$, а в освободившийся разряд добавить бит из закодированного сообщения, повышая точность представления $\displaystyle ivlOffset$. Блок-схема модифицированного алгоритма ренормализации при двоичном декодировании представлена на рис. 7.
Рис. 7. Блок-схема алгоритма ренормализации при декодировании
В представленной блок-схеме используется функция read_bit(), выполняющая очевидное из ее названия действия: эта функция считывает очередной бит из битового потока, представляющего закодированное сообщение. Также в блок-схеме использовано обозначения «|» побитовой операции «или» из языка C.
10 декабря 2019
Читать другие статьи:
Глава 1. Просто о видеокодировании
Глава 2. Межкадровое (Inter) предсказание в HEVC
Глава 3. Пространственное (Intra) предсказание в HEVC
Глава 4. Компенсация движения в HEVC
Глава 5. Постпроцессинг в HEVC
Глава 6. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 1
Глава 7. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 2
Глава 9. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 4
Глава 10. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 5
Автор:
Олег Пономарев - 16 лет занимается вопросами видео кодирования и цифровой обработки сигналов, специалист в области распространения радиоволн, статистической радиофизики, доцент кафедры радиофизики НИ ТГУ, кандидат физико-математический наук. Руководитель исследовательской лаборатории Elecard.
Инструмент для детального анализа этапов кодирования видеопоследовательности - Elecard StreamEye
Инструмент для сравнения параметров видео, закодированного разными энкодерами