Из Википедии, бесплатной энциклопедии
  (Перенаправлено из CABAC )
Перейти к навигации Перейти к поиску

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

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

Алгоритм [ править ]

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

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

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

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

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

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

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

Пример [ править ]

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

МВД хБинаризация
00
110
2110
31110
411110
5111110
61111110
711111110
8111111110

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

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

e kКонтекстная модель для корзины 1
0 ≤ е к <3Модель 0
3 ≤ е к <33Модель 1
33 ≤ e kМодель 2

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

КорзинаКонтекстная модель
10, 1 или 2 в зависимости от e k
23
34
45
5 и выше6

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

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

Механизм арифметического декодирования [ править ]

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

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

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

История [ править ]

В 1986 году исследователи IBM Коттапурам М.А. Мохиуддин и Йорма Йоханнен Риссанен подали патент на алгоритм двоичного арифметического кодирования без умножения. [4] [5] В 1988 году исследовательская группа IBM, в которую входили Р. Б. Арпс, Т. К. Труонг, Д. Лу, У. Б. Пеннебейкер, Л. Митчелл и Г. Г. Лэнгдон, представила алгоритм адаптивного двоичного арифметического кодирования (ABAC) под названием Q-Coder. [6] [7]

Вышеупомянутые патенты и исследовательские работы, а также несколько других от IBM и Mitsubishi Electric , были позже цитированы CCITT и Joint Photographic Experts Group в качестве основы для алгоритма адаптивного двоичного арифметического кодирования формата сжатия изображений JPEG в 1992 году. [4] Однако кодеры и декодеры формата файла JPEG, который имеет параметры как для кодирования Хаффмана, так и для арифметического кодирования, обычно поддерживают только вариант кодирования Хаффмана, который изначально был связан с патентными проблемами, хотя патенты на арифметическое кодирование JPEG [8] с тех пор истекли из-за возраста стандарта JPEG. [9]

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ↑ Richardson, Iain EG, H.264 / MPEG-4 Part 10 White Paper , 17 октября 2002 г.
  2. Перейти ↑ Richardson, Iain EG (2003). Сжатие видео H.264 и MPEG-4: кодирование видео для мультимедиа следующего поколения . Чичестер: John Wiley & Sons Ltd.
  3. ^ Марпе Д., Шварц Х. и Виганд Т. Контекстно-ориентированное адаптивное двоичное арифметическое кодирование в стандарте сжатия видео H.264 / AVC , IEEE Trans. Схемы и системы для видеотехники , Vol. 13, No. 7, pp. 620–636, июль 2003 г.
  4. ^ a b «T.81 - ЦИФРОВОЕ СЖАТИЕ И КОДИРОВАНИЕ НЕПРЕРЫВНЫХ ИЗОБРАЖЕНИЙ - ТРЕБОВАНИЯ И РЕКОМЕНДАЦИИ» (PDF) . CCITT . Сентябрь 1992 . Проверено 12 июля 2019 .
  5. ^ Патент США 4652856
  6. ^ Арпс, РБ; Чыонг, ТК; Лу, диджей; Паско, RC; Фридман, Т. Д. (ноябрь 1988 г.). «Многоцелевой чип СБИС для адаптивного сжатия данных двухуровневых изображений». Журнал исследований и разработок IBM . 32 (6): 775–795. DOI : 10.1147 / rd.326.0775 . ISSN 0018-8646 . 
  7. ^ Пеннебейкер, ВБ; Mitchell, JL; Langdon, GG; Арпс, РБ (ноябрь 1988 г.). «Обзор основных принципов адаптивного двоичного арифметического кодера Q-Coder». Журнал исследований и разработок IBM . 32 (6): 717–726. DOI : 10.1147 / rd.326.0717 . ISSN 0018-8646 . 
  8. ^ "Рекомендация T.81 (1992) Исправление 1 (01/04)" . Рекомендация T.81 (1992) . Международный союз электросвязи. 9 ноября 2004 . Проверено 3 февраля 2011 года .
  9. ^ Стандарт сжатия данных неподвижных изображений JPEG , WB Pennebaker и JL Mitchell , Kluwer Academic Press, 1992. ISBN 0-442-01272-1 
  10. ↑ Ортега, А. (октябрь 1999 г.). «Встроенное сжатие области изображений с использованием контекстных моделей». Труды Международной конференции по обработке изображений 1999 г. (Cat. 99CH36348) . 1 : 477–481 т.1. DOI : 10,1109 / ICIP.1999.821655 .
  11. ^ «Контекстно-ориентированное адаптивное двоичное арифметическое кодирование (CABAC)» . Институт Фраунгофера Генриха Герца . Дата обращения 13 июля 2019 .
  12. ^ «AVC / H.264 - Список патентов» (PDF) . MPEG LA . Дата обращения 6 июля 2019 .