Обзор алгоритмов сжатия с потерями

Рекурсивный (волновой) алгоритм

Английское название рекурсивного сжатия – wavelet. На русский язык оно переводится как волновое сжатие, и как сжатие с использованием всплесков. Этот вид архивации напрямую исходит из идеи использования когерентности областей. Ориентирован алгоритм на цветные и черно-белые изображения с плавными переходами. Идеален для картинок типа рентгеновских снимков. Коэффициент сжатия задается и варьируется в пределах 5-100. При попытке задать больший коэффициент на резких границах, особенно проходящих по диагонали, проявляется "лестничный эффект" – ступеньки разной яркости размером в несколько пикселей.

Идея алгоритма заключается в том, что мы сохраняем в файл разницу – число между средними значениями соседних блоков в изображении, которая обычно принимает значения, близкие к 0.

Так два числа a_2i и a_2i+1 всегда можно представить в виде b¹_i=(a_2i+a_2i+1)/2 и b²_i=(a_2i-a_2i+1)/2. Аналогично последовательность a_i может быть попарно переведена в последовательность b^1,2_i.

Разберем конкретный пример: пусть мы сжимаем строку из 8 значений яркости пикселей (a_i): (220, 211, 212, 218, 217, 214, 210, 202). Мы получим следующие последовательности b¹_i, и b²_i: (215.5, 215, 215.5, 206) и (4.5, -3, 1.5, 4). Заметим, что значения b²_i достаточно близки к 0. Повторим операцию, рассматривая b¹_i как a_i. Данное действие выполняется как бы рекурсивно, откуда и название алгоритма. Мы получим из (215.5, 215, 215.5, 206): (215.25, 210.75) (0.25, 4.75). Полученные коэффициенты, округлив до целых и сжав, например, с помощью алгоритма Хаффмана с фиксированными таблицами, мы можем поместить в файл.

Мы применили преобразование к цепочке только два раза. Реально мы можем позволить себе применение wavelet-преобразования 4-6 раз. Более того, дополнительное сжатие можно получить, используя таблицы алгоритма Хаффмана с неравномерным шагом (т.е. нам придется сохранять код Хаффмана для ближайшего в таблице значения). Эти приемы позволяют достичь заметных коэффициентов сжатия.

Алгоритм для двумерных данных реализуется аналогично. Если есть квадрат из 4 точек с яркостями a_2i,2j, a_2i+1,2j, a_2i,2j+1, и a_2i+1,2j+1, то

Используя эти формулы, мы для изображения 512х512 пикселей получим после первого преобразования 4 матрицы размером 256х256 элементов:

В первой, как легко догадаться, будет храниться уменьшенная копия изображения. Во второй – усредненные разности пар значений пикселей по горизонтали. В третьей – усредненные разности пар значений пикселей по вертикали. В четвертой – усредненные разности значений пикселей по диагонали. По аналогии с двумерным случаем мы можем повторить наше преобразование и получить вместо первой матрицы 4 матрицы размером 128х128. Повторив преобразование в третий раз, мы получим в итоге: 4 матрицы 64х64, 3 матрицы 128х128 и 3 матрицы 256х256. На практике при записи в файл, значениями, получаемыми в последней строке (b⁴_ij), обычно пренебрегают (сразу получая выигрыш примерно на треть размера файла: 1 - 1/4 - 1/16 - 1/64...).

К достоинствам этого алгоритма можно отнести то, что он очень легко позволяет реализовать возможность постепенного "проявления" изображения при передаче изображения по сети. Кроме того, поскольку в начале изображения фактически хранится его уменьшенная копия, упрощается показ "огрубленного" изображения по заголовку.

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

Характеристики волнового алгоритма:

Коэффициенты компрессии: 2-200 (Задается пользователем).
Класс изображений: как у фрактального и JPEG.
Симметричность: ~1.5.
Характерные особенности: при высокой степени сжатия изображение распадается на отдельные блоки.