Двоичное арифметическое кодирование, адаптивное к контексту

Метод энтропийного кодирования

Контекстно-адаптивное двоичное арифметическое кодирование ( CABAC ) — это форма энтропийного кодирования, используемая в стандартах H.264/MPEG-4 AVC ^{[1] [2]} и High Efficiency Video Coding (HEVC). Это метод сжатия без потерь , хотя стандарты видеокодирования, в которых он используется, обычно предназначены для приложений сжатия с потерями . CABAC отличается тем, что обеспечивает гораздо лучшее сжатие, чем большинство других алгоритмов энтропийного кодирования, используемых в видеокодировании, и является одним из ключевых элементов, который обеспечивает схему кодирования H.264/AVC с лучшей способностью сжатия, чем ее предшественники. ^[3]

В H.264/MPEG-4 AVC CABAC поддерживается только в основном и более высоких профилях (но не в расширенном профиле) стандарта, поскольку для его декодирования требуется больший объем обработки, чем для более простой схемы, известной как контекстно-адаптивное кодирование переменной длины (CAVLC), которая используется в базовом профиле стандарта. CABAC также трудно распараллелить и векторизовать, поэтому другие формы параллелизма (например, параллелизм пространственной области) могут быть связаны с его использованием. В HEVC CABAC используется во всех профилях стандарта.

Алгоритм

CABAC основан на арифметическом кодировании с несколькими нововведениями и изменениями, чтобы адаптировать его к требованиям стандартов кодирования видео: ^[4]

• Он кодирует двоичные символы, что снижает сложность и позволяет моделировать вероятности для наиболее часто используемых битов любого символа.
• Вероятностные модели выбираются адаптивно на основе локального контекста, что позволяет лучше моделировать вероятности, поскольку режимы кодирования обычно хорошо коррелируют локально.
• Он использует деление диапазона без умножения с использованием квантованных диапазонов вероятности и состояний вероятности.

CABAC имеет несколько режимов вероятности для разных контекстов. Сначала он преобразует все недвоичные символы в двоичные. Затем для каждого бита кодер выбирает, какую модель вероятности использовать, затем использует информацию из соседних элементов для оптимизации оценки вероятности. Наконец, для сжатия данных применяется арифметическое кодирование .

Метод энтропийного кодирования CABAC, используемый в стандарте сжатия видео H264 на английском языке

Контекстное моделирование обеспечивает оценки условных вероятностей кодирующих символов. Используя подходящие контекстные модели, заданную межсимвольную избыточность можно использовать, переключаясь между различными моделями вероятности в соответствии с уже закодированными символами в окрестности текущего символа для кодирования. Контекстное моделирование отвечает за большую часть примерно 10% экономии битрейта CABAC по сравнению с методом энтропийного кодирования CAVLC .

Кодирование символа данных включает следующие этапы.

• Бинаризация: CABAC использует двоичное арифметическое кодирование, что означает, что кодируются только двоичные решения (1 или 0). Недвоичный символ (например, коэффициент преобразования или вектор движения) «бинаризируется» или преобразуется в двоичный код перед арифметическим кодированием. Этот процесс похож на процесс преобразования символа данных в код переменной длины, но двоичный код дополнительно кодируется (арифметическим кодером) перед передачей.
• Этапы повторяются для каждого бита (или «бина») бинаризированного символа.
• Выбор контекстной модели: «Контекстная модель» — это вероятностная модель для одного или нескольких бинов бинаризированного символа. Эта модель может быть выбрана из набора доступных моделей в зависимости от статистики недавно закодированных символов данных. Контекстная модель хранит вероятность того, что каждый бин будет «1» или «0».
• Арифметическое кодирование: арифметический кодер кодирует каждый бин в соответствии с выбранной моделью вероятности. Обратите внимание, что для каждого бина есть только два поддиапазона (соответствующие «0» и «1»).
• Обновление вероятности: выбранная контекстная модель обновляется на основе фактического кодированного значения (например, если значение ячейки равно «1», количество частот «1» увеличивается).

Пример

1. Бинаризуем значение MVDx, разницу векторов движения в направлении x .

Первый бит двоичного кодового слова — это бин 1; второй бит — это бин 2 и т. д.

2. Выберите контекстную модель для каждого бина. Для бина 1 выбирается одна из 3 моделей на основе ранее закодированных значений MVD. Рассчитывается норма L1 двух ранее закодированных значений, e _{k :}

Если e _k мало, то существует высокая вероятность того, что текущий MVD будет иметь малую величину; и наоборот, если e _k велико, то более вероятно, что текущий MVD будет иметь большую величину. Мы выбираем таблицу вероятностей (контекстную модель) соответственно. Оставшиеся ячейки кодируются с использованием одной из 4 дополнительных контекстных моделей:

3. Кодировать каждый бин. Выбранная контекстная модель предоставляет две оценки вероятности: вероятность того, что бин содержит «1», и вероятность того, что бин содержит «0». Эти оценки определяют два поддиапазона, которые арифметический кодер использует для кодирования бина.

4. Обновите контекстные модели. Например, если для ячейки 1 была выбрана контекстная модель 2, а значение ячейки 1 было «0», то частота «0» увеличивается. Это означает, что в следующий раз, когда эта модель будет выбрана, вероятность «0» будет немного выше. Когда общее количество появлений модели превысит пороговое значение, частота «0» и «1» будет уменьшена, что фактически дает более высокий приоритет недавним наблюдениям.

Арифметический декодирующий движок

Арифметический декодер довольно подробно описан в Стандарте. Он имеет три различных свойства:

1. Оценка вероятности выполняется с помощью процесса перехода между 64 отдельными состояниями вероятности для «наименее вероятного символа» (LPS, наименее вероятного из двух бинарных решений «0» или «1»).
2. Диапазон R, представляющий текущее состояние арифметического кодера, квантуется в небольшой диапазон предустановленных значений перед вычислением нового диапазона на каждом шаге, что позволяет вычислять новый диапазон с помощью таблицы поиска (т.е. без умножения).
3. Определен упрощенный процесс кодирования и декодирования для символов данных с почти равномерным распределением вероятностей.

Определение процесса декодирования разработано для облегчения реализации арифметического кодирования и декодирования с низкой сложностью. В целом, CABAC обеспечивает улучшенную эффективность кодирования по сравнению с кодированием на основе CAVLC за счет большей вычислительной сложности.

История

В 1986 году исследователи IBM Коттапурам М. А. Мохиуддин и Йорма Йоханнен Риссанен подали патент на алгоритм двоичного арифметического кодирования без умножения. ^{[5] [6]} В 1988 году исследовательская группа IBM, в которую входили Р. Б. Арпс, ТК Труонг, DJ Lu, WB Pennebaker, L. Mitchell и GG Langdon, представила алгоритм адаптивного двоичного арифметического кодирования (ABAC), названный Q-Coder. ^{[7] [8]}

Вышеуказанные патенты и исследовательские работы, наряду с несколькими другими от IBM и Mitsubishi Electric , позднее были процитированы CCITT и Joint Photographic Experts Group в качестве основы для адаптивного алгоритма двоичного арифметического кодирования формата сжатия изображений JPEG в 1992 году. ^[5] Однако кодеры и декодеры формата файлов JPEG, который имеет опции как для кодирования Хаффмана , так и для арифметического кодирования, обычно поддерживают только опцию кодирования Хаффмана, что изначально было связано с патентными проблемами, хотя патенты на арифметическое кодирование JPEG ^[9] с тех пор истекли из-за возраста стандарта JPEG. ^[10] Первое сообщение об использовании адаптивного двоичного арифметического кодирования при сжатии видео в движении было сделано в предложении исследователей IBM группе MPEG в 1989 году. ^{[11] [12]} Это предложение расширило использование арифметического кодирования с внутрикадрового JPEG на межкадровое видеокодирование.

В 1999 году Юнгджун Ю ( Texas Instruments ), Юнг Гап Квон и Антонио Ортега ( Университет Южной Калифорнии ) представили контекстно-адаптивную форму двоичного арифметического кодирования. ^[13] Современный алгоритм контекстно-адаптивного двоичного арифметического кодирования (CABAC) был коммерчески представлен с форматом H.264/MPEG-4 AVC в 2003 году. ^[14] Большинство патентов на формат AVC принадлежат Panasonic , Godo Kaisha IP Bridge и LG Electronics . ^[15]

Смотрите также

• Арифметическое кодирование
• Сжатие данных
• Сжатие без потерь
• Контекстно-адаптивное кодирование переменной длины (CAVLC)

Ссылки

1. Ричардсон, Иэн Э.Г., H.264 / MPEG-4 Часть 10 Белая книга, 17 октября 2002 г.
2. Ричардсон, Иэн Э. Г. (2003). Сжатие видео H.264 и MPEG-4: Видеокодирование для мультимедиа следующего поколения . Чичестер: John Wiley & Sons Ltd.
3. Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 апреля 2014 г.). Основы мультимедиа. Springer Science & Business Media. ISBN 978-3-319-05290-8.
4. Марпе, Д., Шварц, Х. и Виганд, Т., Адаптивное двоичное арифметическое кодирование на основе контекста в стандарте сжатия видео H.264/AVC, IEEE Trans. Схемы и системы для видеотехнологий , т. 13, № 7, стр. 620–636, июль 2003 г.
5. "T.81 – ЦИФРОВОЕ СЖАТИЕ И КОДИРОВАНИЕ НЕПРЕРЫВНЫХ ТОНАЛЬНЫХ ИЗОБРАЖЕНИЙ – ТРЕБОВАНИЯ И РУКОВОДСТВО" (PDF) . CCITT . Сентябрь 1992 . Получено 12 июля 2019 .
6. Патент США 4,652,856
7. Arps, RB; Truong, TK; Lu, DJ; Pasco, RC; Friedman, TD (ноябрь 1988 г.). «Многоцелевой чип VLSI для адаптивного сжатия данных двухуровневых изображений». IBM Journal of Research and Development . 32 (6): 775–795. doi :10.1147/rd.326.0775. ISSN  0018-8646.
8. Пеннебейкер, У. Б.; Митчелл, Дж. Л.; Лэнгдон, Г. Г.; Арпс, Р. Б. (ноябрь 1988 г.). «Обзор основных принципов адаптивного двоичного арифметического кодера Q-Coder». IBM Journal of Research and Development . 32 (6): 717–726. doi :10.1147/rd.326.0717. ISSN  0018-8646.
9. "Рекомендация T.81 (1992) Исправление 1 (01/04)". Рекомендация T.81 (1992) . Международный союз электросвязи. 9 ноября 2004 г. Получено 3 февраля 2011 г.
10. Стандарт сжатия данных неподвижных изображений JPEG , WB Pennebaker и JL Mitchell , Kluwer Academic Press, 1992. ISBN 0-442-01272-1 
11. Кодирование DCT для хранения видеоданных с использованием адаптивного арифметического кодирования , CA Gonzales. L. Allman, T. McCarthy, P. Wendt и AN Akansu, Обработка сигналов: передача изображений, 2, 145, 1990.
12. Кодирование видеопоследовательностей движения для среды MPEG с использованием арифметического кодирования , Э. Вишито и К. Гонсалес, SPIE Visual Communications and Image Processing '90, 2–4 октября 1990 г.
13. Ортега, А. (октябрь 1999 г.). «Встроенное сжатие области изображений с использованием контекстных моделей». Труды Международной конференции по обработке изображений 1999 г. (кат. 99CH36348) . Том 1. стр. 477–481 том 1. doi :10.1109/ICIP.1999.821655. ISBN 0-7803-5467-2. S2CID  27303716.
14. "Контекстно-ориентированное адаптивное двоичное арифметическое кодирование (CABAC)". Институт Фраунгофера Генриха Герца . Получено 13 июля 2019 г.
15. "AVC/H.264 – Список патентов" (PDF) . MPEG LA . Получено 6 июля 2019 г. .