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), лежащие в разных профилях. Если вы продаёте, покупаете или строите стриминг, понимание entropy coding убережёт вас от выбора неправильного пресета энкодера, неправильного профиля H.264 или неправильного hardware-пути для live-задач.

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

Слово энтропия здесь пришло из одной работы Клода Шеннона 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 для любого, кто гоняет большие объёмы видео.

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

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

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

Идея 1 – Huffman coding (1952)

Первый практичный entropy-кодер опубликовал в 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 бита, но Huffman вынужден потратить целый бит. На кадре видео, где один символ (например, «здесь ничего не изменилось, 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 бит информации. Arithmetic coding попадает в это число; Huffman не смог бы, потому что его коды имеют целые длины (B=10, A=0, D=111 – это 6 бит, не 5).

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

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

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

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

Идея 3 – CABAC (2003): arithmetic coding с контекстом

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

Шаг один – бинаризация. Каждый синтаксический элемент, который выдаёт энкодер, независимо от количества возможных значений, сперва превращается в последовательность бинарных решений. Не-бинарный символ становится цепочкой да/нет-битов, называемых бинами (bins) – чтобы отличать их от выходных бит.5 Motion vector с сотнями возможных значений, transform-коэффициент, режим предсказания – всё бинаризуется. Арифметический кодер теперь видит только бинарный вход, что радикально упрощает железо: каждый шаг – это просто «пришёл 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% лучше сжатие, чем у альтернативного entropy-кодера H.264, CAVLC (Context-Adaptive Variable-Length Coding, производный от Huffman), при том же качестве картинки.7 В некоторых исследованиях CABAC показывает до 32% экономии относительно чистого Huffman на том же материале.8 Большая часть выигрыша приходит из контекстного моделирования – из того, что флаг transform-коэффициента в разреженном блоке имеет совсем другую вероятность, чем тот же флаг в плотном блоке, и CABAC отслеживает обе ситуации.5

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

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

H.264 поставляется с двумя entropy-кодерами, а не с одним. 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 сделал иначе – мультисимвольный arithmetic coder

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

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

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

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

Таблица 2. Entropy-кодеры по поколениям кодеков.

Типичная ошибка – entropy coding не место экономить качество

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

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

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

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

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

• Entropy coding – это финальная стадия без потерь, переписывающая поток кодека в минимально возможное число бит.
• Huffman (1952) даёт оптимальные коды целым числом бит, но теряет до бита на символ относительно предела Шеннона.
• Arithmetic coding тратит дробные биты на символ и почти точно совпадает с пределом Шеннона.
• CABAC (H.264 Main/High, HEVC, VVC) сочетает бинаризацию, контекстное моделирование и бинарное AC, экономя 10–15% против CAVLC за счёт throughput.
• AV1 использует мультисимвольный arithmetic coder (daala_ec) ради hardware-параллелизма и обхода binary-AC патентов.
• Entropy coding меняет размер файла, а не качество картинки при заданном битрейте; путать эти две вещи – самая частая ошибка.

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

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

Talk to us / See our work / Download

• Поговорить с видео-инженером – назначить 30-минутный звонок про ваш профиль энкодера и битрейт-лестницу.
• Посмотреть кейсы – портфолио Фора Софт видеопроектов.
• Скачать cheat sheet по entropy coding – одна страница: какой entropy-кодер ставится в какой кодек, дефолты профилей H.264 и быстрая шпаргалка для энкодер-разработчиков: Скачать PDF.