ГЛАВА 10
Возможность использования целочисленной арифметики при кодировании и значение словосочетания Context Adaptive в названии CABAC.
Итак, мы коротко разобрали алгоритмы арифметического кодирования и декодирования, обсудили процедуры преобразования значений синтаксических элементов, описывающих содержимое видеокадра в закодированном потоке, в двоичный поток бинов, который и подвергается собственно двоичному арифметическому кодированию. За рамками обсуждения остался еще ряд важных вопросов. Во-первых, до сих пор в рассмотренных алгоритмах кодирование и декодирование производится путем деления текущего отрезка на части. Длина отрезка всегда меньше 1. Таким образом, для выполнения вычислений необходимо использование нецелочисленной арифметики. Во-вторых, для кодирования и декодирования необходима информация о вероятностях появления кодирумых символов (вероятность появления в кодируемом потоке наименее вероятного символа $\displaystyle P_{LPS}$ и его значение). Откуда кодер и декодер берут эту информацию? Наконец, в-третьих, мы так и не обсудили, что же означает словосочетание Context Adaptive, содержащееся в названии CABAC. Давайте разберемся с этими оставшимися вопросами.
Что касается первого из оставшихся вопросов. Возможность использования целочисленной арифметики при кодировании, на первый взгляд, очевидна. Нужно только растянуть исходный интервал $\displaystyle [ 0,1) $ в целое число раз (например в 512 раз), представить вероятность $\displaystyle P_{LPS}$ целочисленным делителем, а результат деления округлить и можно все процедуры деления отрезка выполнять приближенно, используя целочисленную арифметику с заданной разрядностью чисел. Остается открытым только вопрос о том, к какой потере эффективности кодирования (т.е. потере степени сжатия) приведет приближенность вычислений. Еще в начале 90-х годов прошлого столетия по этому поводу был доказан и опубликован ряд теорем (например, в работе P. G. Howard, J. S. Vitter Analysis of Arithmetic Coding for Data Compression, Information Processing and Management 28 (1992), 749 – 763), позволивших оценить потери в степени сжатия. Эти потери, вызванные приближенным характером вычислений, оказались минимальными. Таким образом, была доказана возможность эффективной реализации алгоритмов двоичного арифметического кодирования на основе целочисленной арифметики.
Разработчики CABAC пошли еще дальше в этом направлении. Они предложили настолько загрубить значения величины $\displaystyle R$ текущего интервала и вероятности $\displaystyle P_{LPS}$, чтобы можно было заранее вычислить все возможные результаты произведения $\displaystyle R_{LPS} =R\cdotp P_{LPS}\\$. В результате, в предложенном алгоритме CABAC вычислительно затратная процедура умножения заменена на выборку заранее рассчитанных результатов умножения из таблицы (в стандарте Table 9-40 – Specification of rangeTabLps depending on the values of pStateIdx and qRangeIdx). Рассмотрим этот момент более детально.
Для представления длины $\displaystyle R$ текущего интервала в CABAC отведена 9-ти разрядная переменная ivlCurrRange. При инициализации процесса кодирования/декодирования она инициализируется значением 510. Значения этой переменной после выполнения кодирования/декодирования каждого бина и выполнения процедуры ренормализации всегда лежат в диапазоне от 257 до 511. Перед выполнением процедуры умножения $\displaystyle R_{LPS} =R\cdotp P_{LPS}\\$ значение $\displaystyle R$ квантуется, т.е. делится на 64 (квантование выполняется сдвигом вправо на 6 разрядов). Так как 8-й разряд этой переменной (при нумерации разрядов с 0 по 8) всегда равен 1, то четыре возможных квантованных значения величины $\displaystyle R$ представляют разряды 6 и 7 переменной ivlCurrRange. Именно значение $\displaystyle ( ivlCurrRange\gg 6) \&3$ используется в качестве одного из адресов при выборке заранее рассчитанных значений результатов умножения из двумерной таблицы rangeTabLps. Второй индекс лежит в диапазоне от 0 до 63 и представляет 64 возможных значения $\displaystyle P_{LPS}$. И здесь мы подходим к ответу на второй вопрос. Как происходит подсчет вероятности $\displaystyle P_{LPS}$ при кодировании/декодировании?
Значение вероятности $\displaystyle P_{LPS}$ обновляется рекурсивно при получении каждого нового значения $\displaystyle binVal$ кодируемого/декодируемого бина. На $\displaystyle k$-ом шаге (т.е. при кодировании/декодировании $\displaystyle k$-ого бина) новое значение $\displaystyle P^{k}_{LPS}$ вычисляется следующим образом:
где $\displaystyle α=\left(\frac{0,01875}{0,5}\right)^{\frac{1}{63}}$, а $\displaystyle valMPS$ – значение наиболее вероятного символа (0 или 1). Как уже было сказано, $\displaystyle P_{LPS}$ принимает 64 возможных значения, индексируемых в CABAC 6-ти разрядной переменной $\displaystyle pStateIdx$. Обновление вероятности сводится к обновлению индекса $\displaystyle pStateIdx$ и выполняется выборкой из заранее просчитанных таблиц (в стандарте Table 9-41 – State transition table). В том случае, когда $\displaystyle pStateIdx$ принимает значение 0 происходит смена значения $\displaystyle valMPS$ на противоположное. Значение переменной $\displaystyle pStateIdx$ также используется в качестве второго индекса при выборке значений из таблицы rangeTabLps, т.е. при определении результата произведения $\displaystyle R_{LPS} =R\cdotp P_{LPS}\\$.
Блок-схема модифицированного под целочисленную арифметику алгоритма декодирования представлена на рис. 1.
Рис. 1. Блок-схема процедуры декодирования бина
На рис. 2 представлена блок-схема процедуры ренормализации при декодировании.
Рис. 2. Блок-схема процедуры ренормализации при декодировании
Блок-схемы алгоритмов кодирования и ренормализации при кодировании представлены на рис. 3-4.
Рис 3. Блок-схема процедуры кодирования
Рис. 4. Блок-схема процедуры ренормализации при кодировании
Разберемся, наконец, со словосочетанием Context Adaptive в названии процедуры кодирования CABAC. Здесь все также достаточно просто. Значения всех бинов, подвергающихся арифметическому кодированию, получаются в результате бинаризации значений различных синтаксических элементов. Алгоритмы бинаризации различны для разных элементов. Как следствие, бины, представляющие значения различных синтаксических элементов имеют разные вероятности нулевого и единичного значений. Более того, вероятность $\displaystyle P_{LPS}$, как правило, зависит от порядкового номера бина в бинаризованном представлении значения синтаксического элемента. Эта вероятность, так же как и значение $\displaystyle valMPS$, может меняться в зависимости от значений этого синтаксического элемента в соседних блоках видеокадра. В такой ситуации представляется разумным вести оценку вероятности $\displaystyle P_{LPS}$ и значения $\displaystyle valMPS$ по отдельности для каждой группы бинов, имеющих примерно одинаковую статистику. Именно так и сделано в процедуре кодирования/декодирования CABAC. Как уже было сказано, дискретные значения вероятности $\displaystyle P_{LPS}$ в CABAC определяются семиразрядным индексом $\displaystyle pStateIdx$. Вместе с одноразрядным значением $\displaystyle valMPS$ этот индекс полностью определяет статистику бинов. Обновление значений $\displaystyle pStateIdx$ и $\displaystyle valMPS$ производится для отдельных групп однотипных бинов. Для всех таких бинов эти два значения (объединенные в одно 8-ми разрядное число) хранятся в специальной таблице ctxTable. Элементы этой таблицы названы в стандарте контекстом. Процедура моделирования контекста (эта процедура является составной частью алгоритмов кодирования/декодирования CABAC) заключается в определении индекса $\displaystyle ctxIdx$, для получения из этой таблицы значений $\displaystyle pStateIdx$ и $\displaystyle valMPS$. Значение $\displaystyle ctxIdx$ как раз и определяется по типу синтаксического элемента, бинаризованному представлению которого принадлежит текущий бин, номеру текущего бина в этом бинаризованном представлении и, возможно, по значениям этого синтаксического элемента в соседних блоках кодируемого видеокадра. Контекст, таким образом, адаптивно выбирается в зависимости от того, к какой группе статистически однородных бинов принадлежит текущий бин. По завершении процедур кодирования/декодирования, в которых происходит обновление $\displaystyle pStateIdx$ и $\displaystyle valMPS$, обновленные значения сохраняются в таблице ctxTable по соответствующему адресу ctxIdx.
На этом мы закончим с рассмотрением алгоритмов кодирования/ декодирования CABAC. За рамками рассмотрения осталось достаточно много моментов, разбору которых можно посвятить еще не одну публикацию. С другой стороны, нам удалось разобраться с основными идеями, заложенными в реализацию CABAC, пройти путь от простого примера арифметического кодирования до блок-схем, описывающих алгоритмы кодирования/декодирования в стандарте HEVC.
23 марта 2020
Читать другие статьи:
Глава 1. Просто о видеокодировании
Глава 2. Межкадровое (Inter) предсказание в HEVC
Глава 3. Пространственное (Intra) предсказание в HEVC
Глава 4. Компенсация движения в HEVC
Глава 5. Постпроцессинг в HEVC
Глава 6. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 1
Глава 7. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 2
Глава 8. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 3
Глава 9. Контекстно-адаптивное двоичное арифметическое кодирование. Часть 4
Автор:
Олег Пономарев - 16 лет занимается вопросами видео кодирования и цифровой обработки сигналов, специалист в области распространения радиоволн, статистической радиофизики, доцент кафедры радиофизики НИ ТГУ, кандидат физико-математический наук. Руководитель исследовательской лаборатории Elecard.
Инструмент для детального анализа этапов кодирования видеопоследовательности - Elecard StreamEye
Инструмент для сравнения параметров видео, закодированного разными энкодерами