Блочный метод сжатия

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

Основные принципы

Блочный метод сжатия основан на предположении о том, что в пределах небольшого участка данных (например, квадрата пикселей 8×8 или отрезка аудиосигнала длиной 512 отсчётов) статистические свойства (корреляция, распределение амплитуд) относительно однородны. Это позволяет применять к каждому блоку оптимальные для него алгоритмы, не затрагивая соседние области.

Ключевые этапы блочного сжатия включают:

• Разбиение на блоки: исходные данные делятся на непересекающиеся или частично перекрывающиеся блоки. Размер блока выбирается как компромисс: малые блоки лучше адаптируются к локальным изменениям, но требуют больше служебной информации; большие блоки эффективнее сжимают однородные области, но могут приводить к артефактам на границах.
• Преобразование (опционально): для снижения корреляции внутри блока применяется ортогональное преобразование (например, дискретное косинусное преобразование (ДКП), вейвлет-преобразование). Это концентрирует энергию сигнала в небольшом числе коэффициентов.
• Квантование: коэффициенты преобразования (или исходные отсчёты) округляются с заданным шагом. На этом этапе происходит потеря информации, если сжатие производится с потерями.
• Кодирование: полученные значения кодируются энтропийным кодом (например, кодом Хаффмана или арифметическим кодированием) для уменьшения избыточности.

История

Идея разбиения данных на блоки для сжатия впервые была предложена в 1960-х годах в контексте обработки изображений. Одним из ранних примеров является алгоритм блочного кодирования с использованием преобразования Адамара (1969). В 1974 году Насир Ахмед, Т. Натараджан и К. Р. Рао опубликовали работу, в которой впервые применили дискретное косинусное преобразование (ДКП) для сжатия изображений. ДКП оказалось особенно эффективным, так как его коэффициенты близки к оптимальным для естественных изображений с точки зрения декорреляции.

В 1992 году блочный метод сжатия с ДКП лёг в основу стандарта JPEG (Joint Photographic Experts Group), который стал одним из самых распространённых форматов сжатия изображений с потерями. В 1993 году был принят стандарт MPEG-1 для сжатия видео, также использующий блочное ДКП. В 2000-х годах блочный подход с ДКП был применён в стандартах H.264/AVC и H.265/HEVC для видео, а также в аудиокодеках (например, MP3, AAC).

Классификация

По типу сжатия

• Сжатие с потерями: применяется квантование, что приводит к необратимой потере части данных. Используется в JPEG, MP3, видеоформатах.
• Сжатие без потерь: квантование не применяется, или используется только энтропийное кодирование. Примеры: PNG (использует фильтрацию и сжатие Deflate на блоках), FLAC (аудио, блочное предсказание).

По способу обработки блоков

• Фиксированные блоки: все блоки имеют одинаковый размер (например, 8×8 пикселей в JPEG, 16×16 макроблоков в H.264).
• Переменные блоки: размер блока может меняться в зависимости от содержимого (например, в H.265/HEVC используются блоки от 4×4 до 64×64).
• Перекрывающиеся блоки: блоки частично накладываются друг на друга для уменьшения блочных артефактов. Используется в некоторых аудиокодеках (например, в модифицированном дискретном косинусном преобразовании (MDCT) в MP3).

По области применения

• Сжатие изображений: JPEG, JPEG 2000 (использует вейвлет-преобразование, но также разбивает на блоки — тайлы), WebP, HEIF.
• Сжатие видео: MPEG-2, H.264/AVC, H.265/HEVC, AV1, VP9.
• Сжатие аудио: MP3, AAC, Ogg Vorbis, Opus.
• Сжатие объёмных данных: медицинские изображения (DICOM), геофизические данные.

Применение в стандартах

JPEG

В стандарте JPEG изображение разбивается на блоки размером 8×8 пикселей. К каждому блоку применяется ДКП, затем коэффициенты квантуются с использованием таблицы квантования, зависящей от частоты. После квантования коэффициенты кодируются кодом Хаффмана или арифметическим кодом. При сильном сжатии возникают характерные блочные артефакты — видимые границы между блоками.

H.264/AVC

В стандарте H.264/AVC (разработан Joint Video Team, включает ITU-T и ISO/IEC) используется блочное сжатие с переменным размером макроблоков (16×16, 8×8, 4×4). Для каждого блока применяется предсказание (внутрикадровое или межкадровое), затем остаточный сигнал преобразуется с помощью ДКП и квантуется. Этот стандарт широко используется в цифровом телевидении, видеоконференциях, Blu-ray.

H.265/HEVC

H.265/HEVC (High Efficiency Video Coding) — стандарт, принятый в 2013 году, использующий иерархическую блочную структуру. Блоки могут быть размером от 4×4 до 64×64, что позволяет более эффективно сжимать как мелкие детали, так и большие однородные области. По сравнению с H.264, HEVC обеспечивает снижение битрейта на 30–50% при том же визуальном качестве.

MP3

В аудиокодеках, таких как MP3, используется блочное сжатие на основе модифицированного дискретного косинусного преобразования (MDCT). Аудиосигнал разбивается на кадры (блоки) длительностью около 26 мс (1152 отсчёта при частоте дискретизации 44,1 кГц). Для каждого кадра применяется MDCT, затем коэффициенты квантуются и кодируются с использованием психоакустической модели, которая определяет, какие частоты можно отбросить без заметного ухудшения качества.

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

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

• Адаптивность: возможность подбирать параметры квантования и преобразования для каждого блока, что улучшает сжатие на неоднородных данных.
• Параллелизация: блоки независимы, поэтому их можно обрабатывать одновременно на многоядерных процессорах или графических ускорителях.
• Простота реализации: алгоритмы для блоков фиксированного размера хорошо изучены и оптимизированы.
• Устойчивость к ошибкам: потеря данных в одном блоке не влияет на соседние блоки, что важно для передачи по каналам с помехами.

Недостатки

• Блочные артефакты: при сильном сжатии с потерями на границах блоков возникают видимые или слышимые искажения (например, «квадратики» в JPEG, «музыкальные шумы» в MP3).
• Служебные накладные расходы: для каждого блока необходимо хранить или передавать заголовки с параметрами (например, таблицы квантования, режимы предсказания), что снижает общую степень сжатия при малых размерах блоков.
• Неоптимальность для однородных данных: на плавных градиентах или в областях с низкой текстурой блочный метод может быть менее эффективен, чем фрактальные или вейвлет-методы.

Альтернативы

Блочному методу сжатия противопоставляются методы, не использующие разбиение на блоки:

• Вейвлет-сжатие: применяется в JPEG 2000, где изображение обрабатывается целиком с помощью вейвлет-преобразования, что позволяет избежать блочных артефактов.
• Фрактальное сжатие: основано на поиске самоподобия в изображении, но не получило широкого распространения из-за высокой вычислительной сложности.
• Сжатие на основе нейронных сетей: современные методы (например, на основе автоэнкодеров) могут работать как с блоками, так и с целыми изображениями, но пока уступают традиционным по скорости.

Интересные факты

• В стандарте JPEG размер блока 8×8 был выбран эмпирически: при меньшем размере (4×4) снижалась эффективность сжатия, при большем (16×16) возрастали блочные артефакты.
• В аудиокодеках для уменьшения блочных артефактов используется перекрытие блоков (например, в MDCT блоки перекрываются на 50%).
• В стандарте H.265/HEVC для обработки блоков применяется асимметричное разбиение (например, 32×8 или 8×32), что позволяет лучше адаптироваться к текстурам с направленными элементами.

Источники

• Ахмед Н., Натараджан Т., Рао К. Р. «Discrete Cosine Transform» (1974).
• Стандарт ISO/IEC 10918-1 (JPEG).
• Стандарт ITU-T H.264 (AVC).
• Стандарт ITU-T H.265 (HEVC).
• Сэломон Д. «Сжатие данных, изображений и звука» (2004).
• Рао К. Р., Йип П. «Discrete Cosine Transform: Algorithms, Advantages, Applications» (1990).