JPEG 2000

Сравнение моего вейвлета с JPEG 2000 было не в мою пользу. ) Понятно, что там люди профессионально подошли к решению задачи, задействовали математиков и все вот это вот. ) Но, тем не менее, было обидно. )

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

1. JPEG2000 использует более продвинутый вейвлет, построенный с использованием лифтинга. Я не настолько хорошо знаю математику, но, по моим прикидкам, он примерно соответствуют вейвлету Добеши 8 порядка. Правда, в отличие от вейвлета Добеши, он наверняка обладает какими-то дополнительными полезными свойствами. С ходу можно отметить его симметричность. А использование лифтинга позволяет существенно снизить вычислительные затраты на его получение, правда, за счет немного большей потребности в памяти и потенциальном усложнении его оптимизации под SIMD команды.
2. Сэкономив на вычислениях вейвлет-преобразования, разработчики JPEG2000 потратили освободившиеся ресурсы процессора на более сложную процедуру энтропийного сжатия. Они отказались от использования квантизатора, подобного тому, что применяется в обычном JPEG. Вместо этого они, похоже, анализируют вейвлет-коэффициенты, и в зависимости от них, определяют значимость того или иного коэффициента и то, насколько точным его необходимо сохранить. Академический английский, используемый в тексте, труден для понимания, поэтому пока еще не до конца въехал в смысл данного алгоритма. Но алгоритм реально крут, потому как, кроме эффективного сжатия, еще и обеспечивает сохранение четких границ без ряби вокруг них.
   Дело в том, что и рассматриваемые вейвлет-преобразования, и преобразование Фурье для функций, имеющих разрыв первого рода, дают ненулевые и существенные значения для всех  коэффициентов ряда. Если в результате сжатия с потерями (обнулением некоторых коэффициентов) восстановить данные по таким коэффициентам, то вблизи разрыва мы получим волновую функцию, вид которой зависит от исходной базисной функции преобразования.
   Для изображений таким разрывом в функции является любая четкая граница между объектом и фоном. В результате после восстановления с потерями в изображении возле границы появляются затухающие волны на основе какого-либо полинома (для рассматриваемого вейвлет преобразования). И чем выше порядок вейвлет-преобразования, тем длиннее получается волна.
   Так вот, алгоритм JPEG2000 позволяет очень эффективно бороться с такими искажениями даже при сильном сжатии изображения.
3. Завершающим этапом энтропийного сжатия является арифметическое кодирование, которое несколько эффективнее Хаффмана. Я пока арифметический кодер к своей программке не прикрутил.

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

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

Или причиной может быть та же самая особенность формата JPEG, ведь исходное изображение для сравнения было именно в этом формате, хоть и максимально высокого качества.

Но не меньшее значение имеет и внутренний формат представления данных в моем алгоритме. Дело в том, что я преобразую простейшим способом формат RGB в каналы яркости и цветности. При этом я их не нормирую, и канал яркости может принимать значение от 0 до 3, а каналы цветности - от -2 до 2.

Отказался от нормирования я сознательно, так как это снизит вычислительные затраты алгоритма. Но, с учетом вейвлет преобразования, возникает одна тонкость. После каждого этапа преобразования низкочастотные коэффициенты фильтра возрастают в sqrt(2) раз от среднего.  В случае яркости коэффициенты на каждом этапе возрастали, так как большинство изображений имеют яркость в районе среднего, а очень темные встречаются относительно редко. В то время как каналы цветности, хоть и отклонялись сильно от нуля, но в среднем были к нулю близки. То есть после полного преобразования всего изображения множество коэффициентов в каналах цветности были близки к нулю, а в канале яркости - были как раз далеки от него. Естественно, нули при переходе к энтропийному сжатия отбрасываются и каналы цветности оказываются гораздо меньше по размеру.

Поэтому я решил провести нормировку, и теперь все каналы имеют диапазон от -1 до +1. Только применение этого подхода позволяет снизить размер изображения до 20% (если средняя яркость близка к среднесерому). Если в предыдущем варианте сжатия лучше всего сжимались темные изображения, а хуже всего - светлые, то сейчас преимущество имеют изображения со средней яркостью, коих, как мне кажется, большинство.

Но самое главное, что упустил самый важный момент при сжатии изображения с потерями - высокочастотные детали не так заметны человеческому глазу, по сравнению с низкочастотными. Конечно, там есть нюансы. Например, если человек полчаса любуется картиной, он рассмотрит там самые крошечные детали. Но в обычной обстановке это не так.

Так как я использую при энтропийном сжатии тот же подход, что и обычный JPEG, то есть простой квантизатор, в зависимости от значение которого отбрасываются несущественные данные, то и проблемы возникают примерно одинаковые.

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

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

Единственный вопрос, во сколько раз низкочастотные данные более важны для человеческого зрения, чем низкочастотные? С учетом того, что на каждом этапе преобразования разрешение по каждой размерности изображения снижается в два раза.