Контекстно-адаптивное двоичное арифметическое кодирование

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

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

Алгоритм

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

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

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

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

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

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

Пример

МВД _х	Бинаризация
0	0
1	10
2	110
3	1110
4	11110
5	111110
6	1111110
7	11111110
8	111111110

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

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

я _к	Контекстная модель для бункера 1
0 ≤ е _к < 3	Модель 0
3 ≤ е _к < 33	Модель 1
33 ≤ е _к	Модель 2

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

Бин	Контекстная модель
1	0, 1 или 2 в зависимости от e _k
2	3
3	4
4	5
5 и выше	6

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

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

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

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

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

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

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

История

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

Вышеупомянутые патенты и исследовательские работы, а также несколько других от IBM и Mitsubishi Electric , были позже процитированы CCITT и Объединенной группой экспертов по фотографии в качестве основы для 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]

См. также

Ссылки

↑ Ричардсон, Иэн Э.Г., Технический документ H.264 / MPEG-4, часть 10 , 17 октября 2002 г.
^ Ричардсон, Иэн Э.Г. (2003). Сжатие видео H.264 и MPEG-4: кодирование видео для мультимедиа нового поколения . Чичестер: John Wiley & Sons Ltd.
^ Цзэнянь Ли; Марк С. Дрю; Цзянчуань Лю (9 апреля 2014 г.). Основы мультимедиа . Springer Science & Business Media. ISBN 978-3-319-05290-8 .
^ Марпе Д., Шварц Х. и Виганд Т., Контекстно-ориентированное адаптивное двоичное арифметическое кодирование в стандарте сжатия видео H.264/AVC , IEEE Trans. Схемы и системы для видеотехнологий , Vol. 13, № 7, стр. 620–636, июль 2003 г.
^ Jump up to: ^а ^б «T.81 – ЦИФРОВОЕ СЖАТИЕ И КОДИРОВАНИЕ НЕПРЕРЫВНЫХ СТАЦИОНАРНЫХ ИЗОБРАЖЕНИЙ – ТРЕБОВАНИЯ И РУКОВОДСТВА» (PDF) . ССИТТ . Сентябрь 1992 года . Проверено 12 июля 2019 г.
^ Патент США 4652856.
^ Арпс, РБ; Труонг, ТК; Лу, диджей; Паско, Колорадо; Фридман, Т.Д. (ноябрь 1988 г.). «Универсальная СБИС для адаптивного сжатия данных двухуровневых изображений». Журнал исследований и разработок IBM . 32 (6): 775–795. дои : 10.1147/rd.326.0775 . ISSN 0018-8646 .
^ Пеннебейкер, Всемирный банк; Митчелл, Дж.Л.; Лэнгдон, Дж.Г.; Арпс, РБ (ноябрь 1988 г.). «Обзор основных принципов адаптивного двоичного арифметического кодера Q-Coder». Журнал исследований и разработок IBM . 32 (6): 717–726. дои : 10.1147/rd.326.0717 . ISSN 0018-8646 .
^ «Рекомендация T.81 (1992) Исправление 1 (01/04)» . Рекомендация Т.81 (1992 г.) . Международный союз электросвязи. 9 ноября 2004 года . Проверено 3 февраля 2011 г.
^ Стандарт сжатия данных неподвижных изображений JPEG , У. Б. Пеннебейкер и Дж. Л. Митчелл , Kluwer Academic Press, 1992. ISBN 0-442-01272-1
^ Кодирование DCT для хранения движущегося видео с использованием адаптивного арифметического кодирования , Калифорния Гонсалес. Л. Оллман, Т. Маккарти, П. Вендт и А.Н. Акансу, Обработка сигналов: передача изображений, 2, 145, 1990.
^ Кодирование последовательностей движущегося видео для среды MPEG с использованием арифметического кодирования , Э. Висцито и К. Гонсалес, SPIE Visual Communications and Image Processing '90, 2–4 октября 1990 г.
^ Ортега, А. (октябрь 1999 г.). «Встроенное сжатие домена изображения с использованием контекстных моделей». Материалы Международной конференции по обработке изображений 1999 г. (кат. 99CH36348) . Том. 1. С. 477–481, т. 1. дои : 10.1109/ICIP.1999.821655 . ISBN 0-7803-5467-2 . S2CID 27303716 .
^ «Контекстное адаптивное двоичное арифметическое кодирование (CABAC)» . Институт Фраунгофера Генриха Герца . Проверено 13 июля 2019 г.
^ «AVC/H.264 – Список патентов» (PDF) . MPEG Лос-Анджелес . Проверено 6 июля 2019 г.

[H.264_overview-1] Ричардсон, Иэн Э.Г., Технический документ H.264 / MPEG-4, часть 10 , 17 октября 2002 г.

[H.264_book-2] Ричардсон, Иэн Э.Г. (2003). Сжатие видео H.264 и MPEG-4: кодирование видео для мультимедиа нового поколения . Чичестер: John Wiley & Sons Ltd.

[LiDrew2014-3] Цзэнянь Ли; Марк С. Дрю; Цзянчуань Лю (9 апреля 2014 г.). Основы мультимедиа . Springer Science & Business Media. ISBN 978-3-319-05290-8 .

[CABAC_paper-4] Марпе Д., Шварц Х. и Виганд Т., Контекстно-ориентированное адаптивное двоичное арифметическое кодирование в стандарте сжатия видео H.264/AVC , IEEE Trans. Схемы и системы для видеотехнологий , Vol. 13, № 7, стр. 620–636, июль 2003 г.

[t81-5] Jump up to: ^а ^б «T.81 – ЦИФРОВОЕ СЖАТИЕ И КОДИРОВАНИЕ НЕПРЕРЫВНЫХ СТАЦИОНАРНЫХ ИЗОБРАЖЕНИЙ – ТРЕБОВАНИЯ И РУКОВОДСТВА» (PDF) . ССИТТ . Сентябрь 1992 года . Проверено 12 июля 2019 г.

[6] Патент США 4652856.

[7] Арпс, РБ; Труонг, ТК; Лу, диджей; Паско, Колорадо; Фридман, Т.Д. (ноябрь 1988 г.). «Универсальная СБИС для адаптивного сжатия данных двухуровневых изображений». Журнал исследований и разработок IBM . 32 (6): 775–795. дои : 10.1147/rd.326.0775 . ISSN 0018-8646 .

[8] Пеннебейкер, Всемирный банк; Митчелл, Дж.Л.; Лэнгдон, Дж.Г.; Арпс, РБ (ноябрь 1988 г.). «Обзор основных принципов адаптивного двоичного арифметического кодера Q-Coder». Журнал исследований и разработок IBM . 32 (6): 717–726. дои : 10.1147/rd.326.0717 . ISSN 0018-8646 .

[9] «Рекомендация T.81 (1992) Исправление 1 (01/04)» . Рекомендация Т.81 (1992 г.) . Международный союз электросвязи. 9 ноября 2004 года . Проверено 3 февраля 2011 г.

[10] Стандарт сжатия данных неподвижных изображений JPEG , У. Б. Пеннебейкер и Дж. Л. Митчелл , Kluwer Academic Press, 1992. ISBN 0-442-01272-1

[11] Кодирование DCT для хранения движущегося видео с использованием адаптивного арифметического кодирования , Калифорния Гонсалес. Л. Оллман, Т. Маккарти, П. Вендт и А.Н. Акансу, Обработка сигналов: передача изображений, 2, 145, 1990.

[12] Кодирование последовательностей движущегося видео для среды MPEG с использованием арифметического кодирования , Э. Висцито и К. Гонсалес, SPIE Visual Communications and Image Processing '90, 2–4 октября 1990 г.

[13] Ортега, А. (октябрь 1999 г.). «Встроенное сжатие домена изображения с использованием контекстных моделей». Материалы Международной конференции по обработке изображений 1999 г. (кат. 99CH36348) . Том. 1. С. 477–481, т. 1. дои : 10.1109/ICIP.1999.821655 . ISBN 0-7803-5467-2 . S2CID 27303716 .

[14] «Контекстное адаптивное двоичное арифметическое кодирование (CABAC)» . Институт Фраунгофера Генриха Герца . Проверено 13 июля 2019 г.

[patents-15] «AVC/H.264 – Список патентов» (PDF) . MPEG Лос-Анджелес . Проверено 6 июля 2019 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]