Тема 2.1.3. Энтропийное кодирование. Пропускная способность дискретного канала.

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Энтропийное кодирование неотъемлимый элемент любого стандарта видеокодирования. Данные, пропущенные через мясорубку временной и пространственной модели, необходимо представить в виде сжатого битового потока для последующей передачи по сети или сохранения на жестком диске - финальный шаг любого видеокодека.

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

На этом этапе впору говорить о кодировании информации в отрыве от видео. Методов предостаточно, однако наиболее широко используются коды переменной длины (variable length coding, VLC) и арифметическое кодирование (arithmetic coding, AC).

В данной лекции дан обзор существующий схем. Прежде, скажу, что все описанные схемы сжимают данные без потерь; все что можно было отсечь уже отфильтровано на предыдущих этапах.

Смысл VLC – отображение входных символов в кодовые слова, имеющие переменную длину. Если те или иные входные символы встречаются чаще, то их кодовые слова более короткие. Реже – кодовые слова более длинные. Наиболее известный пример – это код Хаффмана, который предварительно вычисляет вероятность вхождения каждого символа и, согласно построенной вероятностной модели, присвает каждому символу код VLC. Метод требует предварительного анализа всей входной последовательности, что приводит к значительной задерже на стороне приемника сигнала. Также динамическое построения таблицы вероятностей на уровне энкодера требует ее передачи в рамках битового потока для последующего декодирования сигнала, что сокращает степень сжатия. Так как оба этих недостатка связанны с динамическим построением таблицы вероятностей, то разработчики стандартов видеокодирования предложили подход предварительного построения таблицы на основе обобщенных видеоматериалов. То есть каждый стандарт использующий схему VLC, будь то код Хаффмана или его модификации, определяет статическую таблицу кодов, построенную на основе предварительного анализа специально подобранного видеоматериала. Замечу, впрочем, что адаптивный Хаффман решает обозначенные выше проблемы.

Context-based adaptive variable length coding (CAVLC) представляет собой модификацию VLC. Схема определяется стандартом H264 и используется для кодирования блоков остаточных коэффицентов. Схема специально разработанна с учетом особенностей и характеристик блоков: расположение элементов, количество нулей и прочее. Все эти знания влияют на построение вероятностной модели.

VLC отображает входные символы в кодовые слова, которые имеют целую длину бит. Согласно теории информации, выше изложенный факт не способствует получению теоретически оптимального сжатия, так как информационная емкость зачастую не является целым числом. Таким образом, символы имеющие наиболее высокую вероятность вхождения могут быть закодированы кодовыми словами минимум в 1 бит длиной, то есть наименьшей допустимой длиной кодового слова. В подобных случаях мы рискуем получить крайне слабый показатель сжатия.

Побороть эту проблему призвано арифметическое кодирование (arithmetic coding, AC), которое позволяет наиболее плотно приблизиться к теоретическим оценкам сжатия. Однако за эффективность приходиться платить более высокой вычислительной сложностью.

Context-adaptive binary arithmetic coding (CABAC), подобно тому как CAVLC расширяет собой VLC, представляет собой расширение для AC. Расширение использует стандартную схему AC, но при этом:

работает только с двоичными символами. Все символы имеющие недвоичные значения (коэффиценты, координаты векторов) приводятся в двоичный вид;

вводит сбор локальной статистики на основе которой выбирается вероятностная модель для кодирования последующих бит информации.

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

Все вышеописанное даст лишь крайне общие представления о существующих схемах энтропийного кодирования. Далее мы отдельно остановимся на VLC и AC, а также их расширениях.