JPEG2000 на пальцах. Часть 1. Вейвлеты
Добрый день, пикабушники! По просьбе @SimplyFree, делаю серию постов про JPEG2000.
Для начала, поговорим об основных преимуществах этого формата сжатия
изображений в сравнении с JPEG:
1. Большая степень сжатия при том же качестве
2. Поддержка кодирования отдельных областей с лучшим качеством
3. Основной алгоритм сжатия заменен на вейвлет
4. Для повышения степени сжатия в алгоритме используется арифметическое сжатие
5. На уровне формата поддерживается прозрачность
Описание начну с отдельных частей алгоритма, а потом уже приведу схему.
В данном посте будет рассказано о вейвлетах. Вейвлет — это
преобразование, которое позволяет разделить сигнал на высокие и низкие
частоты.
“Стоп. Что еще за сигнал?“ — возможно, спросите Вы.
Изображение, как и звук, является сигналом. Вообще, любая
информация может быть представлена сигналами, но об этом как-нибудь в
другой раз.
Алгоритмы сжатия любят длинные последовательности одинаковых чисел.
Почему? Их легко можно представить в виде последовательности нулей,
которые можно эффективно сжать.
Пример: 155, 155, 155, 155, 155, 155, 155, 155
При использовании дельта-кодирования: 154, 0, 0, 0, 0, 0, 0, 0
(дельта-кодирование — разность между соседними элементами)
Но в реальных изображениях (фотореалистичных) соседние пиксели
отличаются на небольшие значения, которые человеческий глаз уловить не в
силах, а вот эффективность алгоритма они снижают.
Пример: 154, 155, 156, 157, 157, 157, 158, 156
При использовании дельта-кодирования: 154, 1, 1, 1, 0, 0, 1, -2
Напрашивается вопрос, а почему бы не сгладить эти неровности? Для начала, разобьем все числа на пары:
(154, 155), (156, 157), (157, 157), (158, 156)
И вычислим полусуммы и полуразности:
(154.5, 0.5), (156.5, 0.5), (157, 0.0), (157, -1.0)
Из них с помощью простых операций можно вычислить оба значения в паре.
Как можно увидеть, второе число в новой паре маленькое, а значит, его можно сжать эффективнее.
Описанный метод называется преобразованием Хаара. Это преобразование как раз и разделяет сигнал на низкочастотную и высокочастотную части.
Эффективности сжатия при использовании вейвлетов добиваются при небольших потерях на высокочастотных составляющих (квантование), т.к. их человеческий глаз не способен определить.
Такой трюк с разделением на высокие и низкие частоты может повторяться много раз. В JPEG2000 он может проделываться до 32 раз.
Вообще, в самом алгоритме используется Преобразование Добеши, которое позволяет сжать изображение еще сильнее, при этом без видимых шакалов артефактов. Принцип его схож с преобразованием Хаара, только коэффициенты другие.
Конечно, в этой статье не были рассмотрены многие математические детали. Но нельзя объять необъятное. Да и многое сложно объяснить не повышая градус матана. Надеюсь, что и написанное оказалось кому-то полезным.
Спасибо за внимание!