Entropy Coding: краткое введение (Huffman, Arithmetic, CABAC)

TL;DR

После того как кодек предсказал, преобразовал и проквантовал кадр, остаётся поток чисел – почти все маленькие, почти все нулевые, но записанные в неэффективном формате фиксированной ширины. Entropy coding – это финальный безпотерьный этап, на котором этот поток переписывается в максимально короткую последовательность бит: частым числам присваиваются короткие коды, редким – длинные. Три ключевые идеи легли в основу этой области: Huffman coding (1952, оптимальные коды с целым числом бит), arithmetic coding (1970-е, дробные биты на символ – почти точное приближение к пределу Шеннона) и CABAC (Context-Adaptive Binary Arithmetic Coding, 2003) – вариант, используемый в H.264, HEVC и VVC. AV1 пошёл другим путём и применяет мультисимвольный арифметический кодер из проекта Daala, жертвуя небольшой долей эффективности ради параллелизма на аппаратном уровне.

Зачем это нужно

Entropy coding – это последние 10–20% битового потока каждого видео, которое вы когда-либо смотрели. На этом этапе кодек не меняет, что он решил оставить или отбросить, а лишь оптимизирует, насколько компактно можно записать уже принятое решение. Поэтому эта стадия кажется «незаметной» – её работу невозможно визуально продемонстрировать – но она отвечает за ощутимую часть битрейта, задаёт жёсткий предел скорости декодирования в программном и аппаратном обеспечении, и именно из-за неё в H.264 существуют две версии (CAVLC и CABAC), относящиеся к разным профилям. Если вы продаёте, покупаете или разрабатываете стриминговое решение, понимание энтропийного кодирования поможет избежать выбора неподходящего пресета энкодера, неправильного профиля H.264 или неоптимального аппаратного пути для задач в реальном времени.

Что такое «энтропийное кодирование»

Слово энтропия здесь пришло из работы Клода Шеннона 1948 года. Если убрать жаргон, это просто счётчик: среднее число бит на символ, необходимое для оптимального кодирования данных при известных частотах появления символов.1 Если источник выдаёт только один символ – энтропия равна нулю: передавать нечего, ведь получатель и так знает, что придёт. Если источник выдаёт 256 равновероятных символов – энтропия составляет 8 бит на символ: каждый выбор полностью информативен, и сэкономить невозможно. Большая часть реальных данных находится между этими крайностями, и именно в этом диапазоне работает entropy coding.

Короткий пример. Рассмотрим поток из четырёх возможных символов – A, B, C, D – со следующими вероятностями:

• A: 50 % времени
• B: 25 % времени
• C: 12,5 % времени
• D: 12,5 % времени

Наивный кодер потратит по 2 бита на символ, потому что вариантов всего четыре. Формула Шеннона даёт настоящий минимум: энтропия равна 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 1.75 бит на символ. Кодер, достигающий этого предела, выдаст файл на 12,5% меньше, чем наивный – то же содержимое, то же качество, просто умная бухгалтерия.2 Эти 12,5% – реальные деньги в счетах за storage и CDN для любого, кто работает с большими объёмами видео.

Современный видеокодек выдаёт поток, сильно смещённый – как в примере выше. После стадии предсказания и квантования большинство чисел становятся нулями, векторы движения группируются вокруг малых значений, а ответ на вопрос «какой режим предсказания я только что использовал?» следует чёткому паттерну. Задача энтропийного кодирования – эффективно использовать эти закономерности в битовом потоке, не теряя данных, чтобы декодер мог точно восстановить те же самые значения, что отправил энкодер.

Полезная аналогия. Вспомните азбуку Морзе, придуманную в 1830-х годах, задолго до появления теории информации. Буква E – самая частая в английском языке – получила самый короткий код: одну точку. Редкая буква Q получила длинный код: «тире-тире-точка-тире». Телеграфист, который тратил бы на каждую букву четыре точки, всё равно передал бы сообщение, но провёл бы за ключом втрое больше времени. Entropy coding – это та же идея, только обобщённая: короткие коды – для частых символов, длинные – для редких, и такие выигрыши накапливаются на миллионах символов.

Нажмите, чтобы увеличить

Идея 1 – Кодирование Хаффмана (1952)

Первый практичный энтропийный кодер опубликовал в 1952 году Дэвид Хаффман, тогда ещё аспирант MIT.3 Его алгоритм строит оптимальный префиксный код – таблицу битовых последовательностей переменной длины, по одной на каждый символ источника, с двумя важными свойствами. Во-первых, чем чаще встречается символ, тем короче его код. Во-вторых, ни один код не является началом другого, поэтому декодер может последовательно читать биты слева направо и всегда точно определяет, где заканчивается один код и начинается следующий, без необходимости использовать разделители.

Конструкция довольно проста. Каждый символ представлен листом с прикреплённой вероятностью. Два листа с наименьшими вероятностями объединяются в родительский узел, чья вероятность равна сумме их вероятностей; этот узел заменяет исходные в очереди. Процесс повторяется – каждый раз объединяются два узла с минимальной вероятностью – до тех пор, пока не останется один корневой узел. Затем для каждого листа считывается путь от корня: левой ветви присваивается значение «0», правой – «1». Полученная последовательность битов и является кодом символа.

Для примера A = 50 %, B = 25 %, C = 12,5 %, D = 12,5 % код Хаффмана имеет следующий вид:

A = 0
B = 10
C = 110
D = 111

Средняя длина кода: 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 1.75 бита на символ – ровно по Шеннону, потому что все вероятности оказались степенями ½. Когда вероятности не такие «удобные», код Хаффмана не совпадает с энтропией точно, но теряет не более одного бита на символ в среднем.4

Нажмите, чтобы увеличить

Где Хаффман выигрывает и где проигрывает

Хаффман – быстрый алгоритм: декодер по сути сводится к табличному поиску, и его реализация почти ничего не стоила на кремнии 1990-х, который позволил внедрить MPEG-2 в миллионы set-top box по всему миру. К тому же он самосинхронизирующийся – имея таблицу, декодер может начать обработку битового потока с любой границы кода и продолжить работу.

Слабость – штраф «один бит на символ». Huffman назначает каждому символу целое число бит, тогда как оптимальный код по Шеннону часто требует дробного числа бит. Если вероятность символа – 0,9, его информационное содержание составляет всего 0,15 бита, но алгоритм Хафмана вынужден выделить целый бит. На кадре видео, где один символ (например, «здесь ничего не изменилось, skip block») доминирует, такое округление оставляет на столе 10–20% возможной экономии.

Простое решение – расширить «символ»: кодировать сразу пары или тройки исходных символов. Это снижает потери от округления, но размер таблицы кодов растёт экспоненциально: 256 символов превращаются в 65 536 пар, а затем – в 16 миллионов троек. На определённом этапе сама таблица становится дороже той экономии, которую она даёт, и приходит время использовать другой инструмент.

Идея 2 – Arithmetic coding (1970-е)

Arithmetic coding обходит ограничение, связанное с «целым числом бит», не выделяя каждому символу отдельный код. Вместо этого всё сообщение кодируется одним числом – дробью от 0 до 1, точность которой увеличивается с каждым символом.

Классическая интуиция. Берём интервал [0, 1). Делим его на сегменты пропорционально вероятностям символов: A получает [0, 0.5), B – [0.5, 0.75), C – [0.75, 0.875), D – [0.875, 1). Приходит первый символ – выбираем соответствующий сегмент и делаем его новым рабочим интервалом. Делим его снова в тех же пропорциях для второго символа, выбираем подсегмент и повторяем процесс. После каждого символа интервал сужается; после обработки всего сообщения он становится настолько узким, что любое число из него однозначно идентифицирует исходное сообщение. Записываем это число в двоичном виде – и получаем наш битовый поток.

Короткий числовой пример. Возьмём A = 50%, B = 25%, C = 12,5%, D = 12,5% и закодируем сообщение BAD:

Старт:    [0.0,    1.0)
После B:  [0.5,    0.75)         B занимает [0.5, 0.75) исходного интервала
После A:  [0.5,    0.625)        A занимает первую половину [0.5, 0.75)
После D:  [0.609375, 0.625)      D занимает верхние 12.5% от [0.5, 0.625)

Любое число в интервале [0.609375, 0.625) – например, 0.61 – кодирует последовательность BAD. Три символа несут log₂(1/(0.25 × 0.5 × 0.125)) ≈ 5.0 бит информации. Арифметическое кодирование попадает в этот интервал; кодирование Хаффмана не смогло бы этого достичь, потому что его коды имеют целочисленную длину (B=10, A=0, D=111 – это 6 бит, а не 5).

В этом и заключается структурное преимущество: arithmetic coding может тратить дробное число бит на символ, поэтому почти точно следует энтропии по Шеннону, независимо от того, насколько перекошены вероятности.4 Платой за это становятся вычисления. Каждый символ обновляет высокоточный интервал; в программной реализации это означает умножение, сложение и ренормализацию на каждый символ – постоянно. В аппаратной реализации зависимость по данным между символами – интервал после символа N нужен, прежде чем можно начать обработку символа N+1 – ограничивает параллелизм, и именно этот предел становится главным инженерным вызовом всей оставшейся статьи.

Почему отгрузили только через 20 лет

Математика арифметического кодирования была понятна уже к концу 1970-х, но в потребительские кодеки эта идея попала лишь спустя два десятилетия. Причин было две. Первая – патентный куст IBM на наиболее эффективные реализации, который истёк только к концу 1990-х. Вторая – целочисленные таблицы Хаффмана были достаточно быстры на кремниевых чипах того времени, а дополнительные 10–15 % от арифметического кодирования не оправдывали его сложности. Когда пришло HD-видео, эти 10–15 % стали важны, патенты начали истекать, и путь был открыт.

Нажмите, чтобы увеличить

Идея 3 – CABAC (2003): арифметическое кодирование с контекстом

К моменту финализации H.264 / AVC арифметическое кодирование уже существовало десятилетиями, а патентный ландшафт был достаточно проработан. Комитет H.264 предпринял два дополнительных шага, которые превратили арифметическое кодирование из учебного приёма в наиболее эффективный практический энтропийный кодер для видео.

Шаг один – бинаризация. Каждый синтаксический элемент, который выдаёт энкодер, независимо от количества возможных значений, сначала преобразуется в последовательность бинарных решений. Небинарный символ становится цепочкой битов «да/нет», называемых бинами (bins) – чтобы отличать их от выходных битов.5 Вектор движения с сотнями возможных значений, коэффициенты преобразования, режимы предсказания – всё проходит бинаризацию. Арифметический кодер теперь работает только с бинарным входом, что значительно упрощает аппаратную реализацию: на каждом шаге задаётся простой вопрос – «пришёл 0 или 1?» – с вероятностью от 0 до 1.

Шаг два – контекстное моделирование. Каждый бин кодируется с использованием собственной оценки вероятности, которая выбирается из пула контекстов в зависимости от того, что было закодировано рядом. Например, если кодируется флаг «в этом блоке есть ненулевой коэффициент», вероятность того, что флаг равен 1, зависит от наличия ненулевых коэффициентов в блоке слева и блоке сверху. CABAC поддерживает таблицу вероятностей для каждого контекста (399 контекстов в H.264, 153 в HEVC после редизайна ради throughput).6 Каждый раз при кодировании бина соответствующая запись в таблице обновляется. Вероятности адаптируются к локальной статистике потока в реальном времени.

Этот трёхступенчатый процесс – бинаризация, контекстное моделирование, бинарное арифметическое кодирование – и составляет расшифровку аббревиатуры C-A-B-A-C: Context-Adaptive Binary Arithmetic Coding.

Сколько реально экономит CABAC

Главное преимущество – на 10–15% лучшее сжатие по сравнению с альтернативным энтропийным кодером H.264, CAVLC (Context-Adaptive Variable-Length Coding, производным от кода Хаффмана), при том же качестве изображения.7 В некоторых исследованиях CABAC демонстрирует до 32% экономии по сравнению с чистым кодом Хаффмана на тех же данных.8 Большая часть выигрыша достигается за счёт контекстного моделирования: вероятность появления флага коэффициента преобразования в разреженном блоке существенно отличается от вероятности в плотном блоке, и CABAC учитывает обе ситуации.5

Цена – вычисления. Декодирование CABAC известно как бутылочное горло по пропускной способности: контекстная модель для бина N+1 зависит от результата бина N, что блокирует конвейеризацию и ограничивает параллелизм. CABAC был узким местом ещё в H.264, и HEVC унаследовал эту проблему.9 Ответ HEVC – переработка ради повышения пропускной способности: уменьшено количество контекстов, сокращено число бинов с контекстным моделированием на коэффициент (большинство бинов теперь обрабатываются в более быстром «bypass»-режиме без контекстного моделирования), уменьшены line buffers и добавлена явная поддержка параллелизма на верхнем уровне через tiles и wavefront parallel processing.

Реальное следствие – профили H.264

H.264 поставляется с двумя энтропийными кодировщиками, а не с одним. CAVLC обязателен во всех профилях. CABAC доступен только в Main, High и более высоких – его нет в Baseline и Extended.10 Это различие важно при развёртывании. Устройства на iOS и Android поддерживают Main/High с начала 2010-х, поэтому большая часть пользовательского стриминга идёт через CABAC; очень старые set-top box и дешёвые камеры наблюдения до сих пор используют Baseline, что приводит к файлам на 10–15% больше при том же качестве изображения. Причина, по которой «камера выглядит хуже телефона при одинаковом битрейте», часто заключается в том, что камера использует Baseline H.264, а телефон – High.

Таблица 1. Huffman/CAVLC против arithmetic/CABAC в сравнении.

Нажмите, чтобы увеличить

Что AV1 сделал иначе – мультисимвольный арифметический кодировщик

Когда Alliance for Open Media (AOMedia) разрабатывала AV1 в 2017–2018 годах, у команды было две серьёзные проблемы с подходом CABAC. Первая – патенты: CABAC находится в плотном патентном пуле H.264/HEVC, а AOMedia намеренно стремилась его избежать. Вторая – аппаратная реализация. Бинарная, последовательная природа CABAC плохо масштабировалась на разрешении 4K и 8K, где декодеру приходилось обрабатывать миллионы бинов в секунду.

AV1 принял daala_ec – небинарный арифметический кодировщик из исследовательского проекта Mozilla Daala – в качестве замены.11 В то время как CABAC обрабатывает за шаг одно бинарное решение, daala_ec работает с мультисимвольным алфавитом – до 16 символов на синтаксический элемент – за один шаг. Вероятности хранятся в виде 15-битных кумулятивных функций распределения (CDF) для каждого контекста и обновляются после кодирования каждого символа, а не раз в кадр.12

Это одно изменение имеет два следствия. Параллелизм на битовом уровне улучшается, потому что теперь каждый шаг обрабатывает сразу несколько CABAC-бинов – hardware-декодер достигает той же пропускной способности при более низкой тактовой частоте и потребляет меньше энергии.13 Уход от патентов также становится эффективнее – мультисимвольная формулировка выходит за пределы охвата патентов на бинарное арифметическое кодирование. Эффективность сжатия остаётся примерно на уровне CABAC для отдельных синтаксических элементов; основной выигрыш AV1 перед HEVC обеспечивается другими инструментами (более длинные преобразования, улучшенное предсказание, большее число reference frames), а энтропийное кодирование вносит заметный, но относительно скромный вклад.

H.266 / VVC, финализированный в 2020 году, пошёл по иному пути: сохранил бинарный CABAC, но внедрил мультигипотезный оценщик вероятности, который параллельно запускает два независимых обновления вероятностей и усредняет их результаты, а также использует более крупные контекстные таблицы. В результате достигается экономия битрейта на уровне 3–5% от общего выигрыша VVC, напрямую связанная с энтропийным кодированием.14

Таблица 2. Кодировщики энтропии по поколениям кодеков

Типичная ошибка – не стоит экономить на энтропийном кодировании

Распространённая ошибка: считать, что переключение entropy-кодера с CAVLC на CABAC заметно улучшит картинку. Не улучшит. Entropy coding – без потерь, его единственная задача – сжать то, что остальной пайплайн уже решил сохранить. Выбор CABAC вместо CAVLC при том же битрейте даёт ту же картинку; выигрыш проявляется только в меньшем файле или в более высоком битрейте при том же целевом размере. Если картинка изменилась – значит, энкодер заодно поменял что-то ещё под капотом (другое квантование, другой rate control feedback). Смешивание этих двух стадий – одна из самых частых ошибок при анализе бенчмарков энкодеров. Решения по качеству картинки принимаются на этапах prediction и quantisation; решения по бюджету битрейта частично зависят от entropy coding.

Вторая ловушка: предположение, что «CABAC всегда включён в H.264». На самом деле – не включён: профиль Baseline использует только CAVLC, и удивительно большое число live-стриминговых и систем видеонаблюдения по умолчанию выбирают именно Baseline. Всегда проверяйте профиль битстрима, который вы отгружаете, а не только название кодека.

Где здесь Фора Софт

Мы строим видео-пайплайны, в которых компромисс между профилем энкодера, энтропийным кодером и целевой аппаратной платформой – вопрос ежедневный. Это видеоконференции, видеостриминг, OTT и интернет-ТВ, видеонаблюдение, e-learning, телемедицина, AR/VR. Мы поставляли системы, где отказ от H.264 Baseline в пользу Main + CABAC позволял сократить расходы на пропускную способность на двузначные проценты без ущерба для качества изображения; и другие, где издержки по пропускной способности при использовании CABAC на ограниченном ARM SoC заставляли нас возвращаться к CAVLC. Правильный выбор всегда зависит от контента и целевого устройства; а неверный – почти всегда сводится к «используем настройки по умолчанию энкодера и надеемся на лучшее».

Ключевые выводы

• Энтропийное кодирование – это финальный этап сжатия без потерь, при котором поток данных кодека переписывается с использованием минимально возможного количества бит.
• Кодирование Хаффмана (1952) обеспечивает оптимальные коды с целым числом бит на символ, но при этом теряет до одного бита на символ по сравнению с пределом Шеннона.
• Арифметическое кодирование использует дробное число бит на символ и практически достигает предела Шеннона.
• CABAC (в H.264 Main/High, HEVC, VVC) объединяет бинаризацию, контекстное моделирование и бинарное арифметическое кодирование, обеспечивая экономию 10–15% по сравнению с CAVLC за счёт производительности.
• AV1 применяет многосимвольный арифметический кодировщик (daala_ec) ради аппаратного параллелизма и обхода патентов на бинарное арифметическое кодирование.
• Энтропийное кодирование влияет на размер файла, но не на качество изображения при фиксированном битрейте; путаница между этими понятиями – самая распространённая ошибка.

Что читать дальше

• Пространственная избыточность пикселей: что внутри одного кадра
• Временная избыточность: связи между кадрами
• Quantization: где теряется качество