CABAC

CABAC (Context-Adaptive Binary Arithmetic Coding) — это метод энтропийного кодирования, используемый в стандартах сжатия видео, в частности в H.264/AVC, H.265/HEVC, H.266/VVC и AV1. Он обеспечивает более высокую степень сжатия по сравнению с другими методами, такими как CAVLC (Context-Adaptive Variable-Length Coding), за счёт использования вероятностных моделей, адаптирующихся к контексту кодируемых данных. CABAC является основным инструментом для кодирования синтаксических элементов битового потока, таких как коэффициенты преобразования, векторы движения и флаги режимов.

Принцип работы

CABAC основан на арифметическом кодировании, которое позволяет представлять последовательность символов в виде одного числа из интервала [0, 1). В отличие от кодирования Хаффмана, где каждому символу присваивается целое число битов, арифметическое кодирование может использовать дробное количество битов, что приближает его к теоретической энтропии источника.

Этапы кодирования

Процесс CABAC состоит из трёх основных этапов:

1. Бинаризация — преобразование недвоичных синтаксических элементов (например, значений коэффициентов) в двоичную последовательность (бинарный код). Для этого используются различные схемы, такие как усечённое унарное кодирование, экспоненциальное кодирование Голомба или фиксированное кодирование. Выбор схемы зависит от статистических свойств элемента.

1. Контекстное моделирование — для каждого бита (или группы битов) выбирается вероятностная модель (контекст), которая отражает статистику кодируемых данных в текущем окружении. Контекст определяется на основе ранее закодированных элементов, таких как соседние блоки, типы макроблоков или значения флагов. В H.264/AVC используется 460 контекстов, в H.265/HEVC — около 600, а в H.266/VVC — более 1000.

1. Арифметическое кодирование — на основе выбранной вероятностной модели выполняется арифметическое кодирование битов. Модель содержит два параметра: вероятность появления наиболее вероятного символа (MPS) и состояние (State), которое определяет вероятность. После кодирования каждого бита модель обновляется (адаптируется) в соответствии с фактическим значением бита, что позволяет подстраиваться под изменяющуюся статистику данных.

Адаптация вероятностей

В CABAC используется конечный автомат с 64 состояниями для представления вероятностей. Каждое состояние соответствует определённой вероятности MPS. После кодирования бита вероятность обновляется по следующему правилу: если закодированный бит равен MPS, вероятность MPS увеличивается; если бит равен LPS (наименее вероятный символ), вероятность MPS уменьшается. Скорость адаптации регулируется фиксированными таблицами переходов, что обеспечивает баланс между точностью и вычислительной сложностью.

Преимущества и недостатки

Преимущества

• Высокая эффективность сжатия: CABAC обеспечивает на 10–15% лучшую степень сжатия по сравнению с CAVLC при той же скорости передачи данных. Это особенно заметно на низких битрейтах, где каждый бит имеет значение.
• Адаптивность: контекстное моделирование позволяет учитывать локальные статистические особенности видео, что повышает точность вероятностных моделей.
• Гибкость: поддержка различных типов синтаксических элементов и возможность настройки контекстов под конкретные приложения.

Недостатки

• Высокая вычислительная сложность: арифметическое кодирование и обновление контекстов требуют значительных вычислительных ресурсов, что усложняет реализацию в реальном времени на устройствах с ограниченной производительностью.
• Задержки: последовательный характер кодирования и декодирования (каждый бит зависит от предыдущего) затрудняет параллельную обработку, что может увеличивать задержки при потоковой передаче.
• Чувствительность к ошибкам: из-за адаптивного характера модели ошибка в одном бите может привести к рассинхронизации декодера и потере данных до следующего синхромаркера.

Применение

CABAC используется в следующих стандартах и технологиях:

• H.264/AVC (Advanced Video Coding) — в профилях Main и High, где CABAC является обязательным элементом. В профиле Baseline используется только CAVLC.
• H.265/HEVC (High Efficiency Video Coding) — CABAC является единственным методом энтропийного кодирования для всех профилей, за исключением некоторых упрощённых профилей, где допускается CAVLC.
• H.266/VVC (Versatile Video Coding) — CABAC был расширен и оптимизирован, включая новые контексты и методы бинаризации, такие как многоуровневое кодирование.
• AV1 (Alliance for Open Media) — использует модифицированную версию CABAC, называемую «Symbol Adaptive Coding» (SAC), которая включает элементы арифметического кодирования и контекстного моделирования.
• VP9 — использует собственный вариант арифметического кодирования, основанный на принципах CABAC, но с упрощённой адаптацией вероятностей.

Реализация и оптимизация

Реализация CABAC в кодеках обычно включает аппаратное ускорение (например, в видеокартах и мобильных процессорах) или программные оптимизации, такие как:

• Табличные вычисления: предварительно рассчитанные таблицы для вероятностей и переходов состояний ускоряют обновление моделей.
• Параллельная обработка: в H.265/HEVC и H.266/VVC введены механизмы для параллельного кодирования независимых фрагментов битового потока, таких как тайлы (tiles) и волны (wavefronts).
• Снижение точности: использование целочисленной арифметики вместо плавающей позволяет уменьшить вычислительную нагрузку без значительной потери качества сжатия.

Сравнение с другими методами

CABAC остаётся стандартом де-факто для высокоэффективного сжатия видео благодаря балансу между степенью сжатия и вычислительной сложностью, хотя в некоторых современных кодеках (например, в AV1) предпринимаются попытки заменить его на более простые или параллелизуемые методы.

Источники

• Marpe, D., Schwarz, H., & Wiegand, T. (2003). Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard. IEEE Transactions on Circuits and Systems for Video Technology, 13(7), 620–636.
• Sullivan, G. J., Ohm, J.-R., Han, W.-J., & Wiegand, T. (2012). Overview of the High Efficiency Video Coding (HEVC) standard. IEEE Transactions on Circuits and Systems for Video Technology, 22(12), 1649–1668.
• Bross, B., Chen, J., Ohm, J.-R., Sullivan, G. J., & Wang, Y.-K. (2021). Developments in International Video Coding Standardization After AVC, with an Overview of Versatile Video Coding (VVC). Proceedings of the IEEE, 109(9), 1451–1495.
• ISO/IEC 14496-10:2014. Information technology — Coding of audio-visual objects — Part 10: Advanced Video Coding.
• ISO/IEC 23008-2:2017. Information technology — High efficiency coding and media delivery in heterogeneous environments — Part 2: High Efficiency Video Coding.