Вейвлет-сжатие

Вейвлет-сжатие — это метод сжатия цифровых данных (изображений, аудио, видео) с потерями или без потерь, основанный на применении вейвлет-преобразования. В отличие от классического преобразования Фурье, которое раскладывает сигнал на синусоидальные компоненты, вейвлет-преобразование использует локализованные во времени и частоте функции — вейвлеты. Это позволяет эффективно представлять сигналы с резкими перепадами (например, края изображений) и достигать высоких степеней сжатия при сохранении приемлемого визуального или слухового качества.

История

Развитие вейвлет-сжатия началось в 1980-х годах. Основополагающие работы в области вейвлет-анализа принадлежат Жану Морле, Алексу Гроссману и Ингрид Добеши. В 1988 году Добеши предложила компактные ортогональные вейвлеты, которые стали основой для практических алгоритмов.

В 1990-х годах вейвлет-сжатие получило широкое распространение в обработке изображений. В 1993 году был опубликован алгоритм Embedded Zerotree Wavelet (EZW), предложенный Джеромом Шапиро, который впервые продемонстрировал возможность прогрессивной передачи изображений с использованием вейвлетов. В 1996 году Амир Саид и Уильям Перлман разработали более эффективный алгоритм Set Partitioning in Hierarchical Trees (SPIHT).

Ключевым этапом стало принятие в 2000 году стандарта JPEG 2000, который основан на вейвлет-сжатии и дискретном вейвлет-преобразовании (DWT). В области аудио вейвлет-сжатие используется в формате MPEG-4 Audio Lossless Coding (ALS) и некоторых других кодеках.

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

Вейвлет-преобразование

Вейвлет-преобразование разлагает сигнал на две компоненты:

Аппроксимирующие коэффициенты — низкочастотная составляющая, отражающая общую форму сигнала.
Детализирующие коэффициенты — высокочастотные составляющие, фиксирующие мелкие детали и шум.

Процесс выполняется итеративно: аппроксимирующие коэффициенты снова подвергаются преобразованию, что создаёт иерархическую структуру (пирамиду) вейвлет-коэффициентов. Для двумерных сигналов (изображений) применяется разделимое преобразование: сначала по строкам, затем по столбцам, что даёт четыре поддиапазона: LL (низкие-низкие), LH (низкие-высокие), HL (высокие-низкие) и HH (высокие-высокие).

Квантование и кодирование

После вейвлет-преобразования коэффициенты квантуются — округляются до определённого шага. Это основной источник потерь при сжатии с потерями. Затем квантованные коэффициенты кодируются с использованием энтропийного кодирования (например, арифметического кодирования или кода Хаффмана). Для повышения эффективности применяются специальные алгоритмы, учитывающие иерархическую структуру вейвлет-коэффициентов, такие как EZW, SPIHT и EBCOT (Embedded Block Coding with Optimized Truncation), используемый в JPEG 2000.

Сжатие без потерь

Вейвлет-сжатие может быть реализовано и без потерь, если используется целочисленное вейвлет-преобразование (например, вейвлет Ле Галла 5/3) и квантование не применяется. В этом случае достигается умеренное сжатие (обычно 2:1 — 3:1 для изображений), но без каких-либо искажений.

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

Сжатие изображений

JPEG (DCT): Использует дискретное косинусное преобразование (DCT) блоками 8×8 пикселей. При низких битрейтах (высоком сжатии) появляются характерные блочные артефакты. Вейвлет-сжатие (JPEG 2000) лишено этого недостатка, так как работает с изображением целиком, и артефакты проявляются как размытие или «муар» вокруг краёв.
JPEG 2000: Обеспечивает лучшее качество при одинаковом размере файла по сравнению с JPEG, особенно при сильном сжатии. Поддерживает прогрессивную передачу (сначала низкое разрешение, затем детали), сжатие без потерь и работу с большими изображениями (до 2^32 пикселей).
WebP: Использует как DCT (на основе VP8), так и вейвлет-сжатие (в режиме без потерь). В целом, JPEG 2000 часто превосходит WebP по качеству при низких битрейтах, но WebP имеет более широкую поддержку в вебе.

Сжатие аудио

MP3 (MDCT): Использует модифицированное дискретное косинусное преобразование (MDCT). Вейвлет-сжатие аудио менее распространено, но применяется в некоторых кодеках (например, в MPEG-4 ALS). Оно может быть эффективнее для сигналов с резкими атаками (ударные инструменты), но уступает MDCT в стационарных участках.

Сжатие видео

H.264/AVC, H.265/HEVC, AV1: Используют DCT и MDCT. Вейвлет-сжатие видео применяется редко из-за сложности обработки движения. Однако существуют экспериментальные кодеки (например, Dirac), основанные на вейвлетах, которые не получили широкого распространения.

Применение

JPEG 2000 (стандарт ISO/IEC 15444)

JPEG 2000 — наиболее известный стандарт, использующий вейвлет-сжатие. Он применяется в:

Медицинской визуализации (DICOM): для хранения рентгеновских снимков, МРТ и КТ. Требуется сжатие без потерь или с минимальными потерями.
Киноиндустрии: для цифрового кинопоказа (DCI — Digital Cinema Initiatives) и архивирования фильмов.
Геоинформационных системах (ГИС): для хранения спутниковых снимков и карт высокого разрешения.
Цифровых фотокамерах: некоторые модели (например, от компании Leica) используют JPEG 2000 для записи изображений.
Веб-графике: ограниченно, из-за слабой поддержки в браузерах (основные браузеры не поддерживают JPEG 2000, за исключением Safari).

Другие стандарты и форматы

DjVu: Формат для хранения отсканированных документов, использующий вейвлет-сжатие для разделения изображения на текст и фон.
ECW (Enhanced Compression Wavelet): Проприетарный формат для сжатия растровых изображений, широко используемый в ГИС.
MrSID (Multi-resolution Seamless Image Database): Ещё один формат для ГИС, основанный на вейвлетах.
FTS (Fractal Transform System): Экспериментальный формат, сочетающий фрактальное и вейвлет-сжатие.

Научные и промышленные приложения

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

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

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

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

Недостатки

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

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

Вейвлет-сжатие используется в формате DICOM для медицинских изображений с 2001 года.
Алгоритм SPIHT считается одним из самых эффективных для сжатия изображений с потерями и без потерь, и его реализация доступна в открытом доступе.
Вейвлет-преобразование применяется не только для сжатия, но и для анализа сигналов (например, в геофизике для обнаружения землетрясений) и для сжатия нейронных сетей (pruning).
Стандарт JPEG XS (2018) использует вейвлет-сжатие для кодирования видео с низкой задержкой (less than 1 ms) для профессионального вещания.

Источники

Mallat, S. (2009). A Wavelet Tour of Signal Processing: The Sparse Way. Academic Press.
Daubechies, I. (1992). Ten Lectures on Wavelets. SIAM.
Shapiro, J. M. (1993). "Embedded image coding using zerotrees of wavelet coefficients". IEEE Transactions on Signal Processing, 41(12), 3445–3462.
Said, A., & Pearlman, W. A. (1996). "A new, fast, and efficient image codec based on set partitioning in hierarchical trees". IEEE Transactions on Circuits and Systems for Video Technology, 6(3), 243–250.
Taubman, D. S., & Marcellin, M. W. (2002). JPEG2000: Image Compression Fundamentals, Standards and Practice. Springer.
ISO/IEC 15444-1:2004. Information technology — JPEG 2000 image coding system — Part 1: Core coding system.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →