MQ-кодер

MQ-кодер — это арифметический энтропийный кодер, используемый в алгоритмах сжатия изображений и видео, в частности, в стандартах JPEG 2000 и JBIG2. Он предназначен для эффективного кодирования бинарных символов (битов) с адаптивной оценкой вероятности, что позволяет достичь высокой степени сжатия без потерь. MQ-кодер является развитием идей арифметического кодирования, но с рядом оптимизаций, делающих его пригодным для аппаратной реализации и работы в реальном времени.

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

MQ-кодер, как и любой арифметический кодер, представляет последовательность входных символов (битов) в виде числа в интервале [0, 1). В отличие от классического арифметического кодирования, где каждый символ кодируется с использованием точной вероятности, MQ-кодер оперирует двумя состояниями: вероятный символ (MPS — Most Probable Symbol) и маловероятный символ (LPS — Least Probable Symbol). Вероятность LPS (обозначается как Qe) оценивается адаптивно в процессе кодирования.

Основные этапы кодирования

1. Инициализация: Кодер начинает с интервала [0, 1) и начальной оценки вероятности LPS (Qe). В стандарте JPEG 2000 используется 47 фиксированных состояний вероятности, каждое из которых имеет своё значение Qe.
2. Кодирование символа: Для каждого входного бита определяется, является ли он MPS или LPS. В зависимости от этого интервал сужается:

• Если символ — MPS, новый интервал становится [нижняя граница, нижняя граница + Qe * длина_интервала).
• Если символ — LPS, новый интервал становится [нижняя граница + Qe * длина_интервала, нижняя граница + длина_интервала).

1. Адаптация вероятности: После кодирования каждого символа происходит обновление оценки вероятности. Если был закодирован MPS, оценка Qe может остаться неизменной или уменьшиться (в зависимости от состояния). Если был закодирован LPS, оценка Qe увеличивается, что отражает изменение статистики входного потока. Переходы между состояниями вероятности заданы таблицей, что исключает сложные вычисления.
2. Перемасштабирование (Renormalization): Чтобы избежать бесконечного сужения интервала, после каждого кодирования выполняется проверка на необходимость перемасштабирования. Если длина интервала становится меньше 0,5, интервал удваивается, а в выходной поток записывается один или несколько битов. Этот процесс гарантирует, что интервал всегда остаётся в пределах [0, 1).

Декодирование

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

Особенности MQ-кодера

• Адаптивность: MQ-кодер автоматически подстраивается под изменяющуюся статистику входных данных, что делает его эффективным для сжатия изображений, где локальные свойства (например, резкие перепады яркости) могут сильно различаться.
• Табличная реализация: Вместо сложных арифметических операций с плавающей точкой MQ-кодер использует предопределённые таблицы состояний и правил перехода. Это позволяет реализовать его как на программном, так и на аппаратном уровне с высокой производительностью.
• Отсутствие умножения: В классическом арифметическом кодировании требуется умножение длины интервала на вероятность. В MQ-кодере эта операция заменяется на более простые операции сдвига и сравнения, что значительно ускоряет работу.
• Бинарное кодирование: MQ-кодер работает только с бинарными символами. Для кодирования многоуровневых данных (например, значений пикселей) они предварительно преобразуются в бинарную последовательность с помощью битовых плоскостей или других методов.

Применение

JPEG 2000

В стандарте JPEG 2000 MQ-кодер используется для энтропийного кодирования коэффициентов вейвлет-преобразования. После кодирования битовых плоскостей и контекстного моделирования, полученные бинарные символы подаются на вход MQ-кодера. Это обеспечивает высокую степень сжатия, особенно для изображений с большим динамическим диапазоном и медицинских снимков.

JBIG2

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

Другие области

MQ-кодер или его модификации применяются в некоторых специализированных алгоритмах сжатия данных, где требуется высокая производительность и адаптивность, например, в системах видеонаблюдения и телеметрии.

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

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

• Высокая степень сжатия: Благодаря адаптивной оценке вероятности и эффективному арифметическому кодированию, MQ-кодер обеспечивает сжатие, близкое к теоретическому пределу для бинарных источников.
• Простота аппаратной реализации: Табличная структура и отсутствие умножения делают MQ-кодер идеальным для реализации в виде специализированных микросхем (ASIC) или программируемых логических интегральных схем (FPGA).
• Низкая задержка: Алгоритм позволяет кодировать и декодировать данные с минимальной задержкой, что важно для систем реального времени.

Недостатки

• Ограничение на бинарные данные: MQ-кодер не может напрямую кодировать многоуровневые символы, что требует предварительной обработки.
• Чувствительность к начальной оценке: Неправильный выбор начальной вероятности LPS может привести к временному снижению эффективности сжатия, хотя адаптация со временем исправляет это.
• Сложность контекстного моделирования: Эффективность MQ-кодера сильно зависит от качества контекстного моделирования, которое предшествует кодированию. Плохое моделирование может свести на нет преимущества кодера.

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

• Арифметический кодер Хаффмана: Код Хаффмана является более простым и быстрым, но менее эффективным для данных с неравномерным распределением вероятностей. MQ-кодер обеспечивает лучшее сжатие, особенно для данных с высокой энтропией.
• Классический арифметический кодер: Классический арифметический кодер (например, в CABAC в H.264/AVC) использует более сложные вычисления, но может быть более гибким в настройке. MQ-кодер выигрывает в скорости и простоте реализации.
• Кодер LZ (Lempel-Ziv): Словарные методы, такие как LZ77 и LZ78, хорошо подходят для сжатия текстов и повторяющихся шаблонов, но менее эффективны для изображений, где важна точность вероятностной модели. MQ-кодер лучше справляется с данными, имеющими сложную статистическую структуру.

Источники

1. ISO/IEC 15444-1:2004 — Information technology — JPEG 2000 image coding system: Core coding system.
2. ISO/IEC 14492:2001 — Information technology — Lossy/lossless coding of bi-level images (JBIG2).
3. Taubman, D. S., & Marcellin, M. W. (2002). JPEG2000: Image compression fundamentals, standards and practice. Springer.
4. Rabbani, M., & Joshi, R. (2002). An overview of the JPEG 2000 still image compression standard. Signal Processing: Image Communication, 17(1), 3-48.