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

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

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

Так два числа a _{2 i} и a _{2 i+1} всегда можно представить в виде b¹_i =(a _{2 i} + a _{2 i+1} )/2 и b²_i =(a _{2 i} - a _{2 i+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 раз. Более того, дополнительное сжатие можно получить, используя таблицы алгоритма Хаффмана с неравномерным шагом (т.е. нам придется сохранять код Хаффмана для ближайшего в таблице значения). Эти приемы позволяют достичь заметных коэффициентов сжатия.

Исходное изображение	B^1	B^2
	B^3	B^4

Для изображения 512×512 пикселов получим после первого преобразования 4 матрицы размером 256×256 элементов:

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

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

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

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

Алгоритм	Особенности изображения, за счет которых происходит сжатие
RLE	Подряд идущие одинаковые цвета: 2 2 2 2 2 2 15 15 15
LZW	Одинаковые подцепочки: 2 3 15 40 2 3 15 40
Хаффмана	Разная частота появления цвета: 2 2 3 2 2 4 3 2 2 2 4
CCITT-3	Преобладание белого цвета в изображении, большие области, заполненные одним цветом
Рекурсивный	Плавные переходы цветов и отсутствие резких границ
JPEG	Отсутствие резких границ
Фрактальный	Подобие между элементами изображения

 

Алгоритм	Коэффициенты сжатия	Симметричность по времени	На что ориентирован	Потери	Размерность
RLE	32, 2, 0.5	1	3,4-х битные	Нет	1D
LZW	1000, 4, 5/7	1.2-3	1-8 битные	Нет	1D
Хаффмана	8, 1.5, 1	1-1.5	8 битные	Нет	1D
CCITT-3	213(3), 5, 0.25	~1	1-битные	Нет	1D
JBIG	2-30 раз	~1	1-битные	Нет	2D
Lossless JPEG	2 раза	~1	24-битные, серые	Нет	2D
JPEG	2-20 раз	~1	24-битные, серые	Да	2D
Рекурсивное сжатие	2-200 раз	1.5	24-битные, серые	Да	2D
Фрактальный	2-2000 раз	1000-10000	24-битные, серые	Да	2.5D

В приведенной таблице отчетливо видны тенденции развития алгоритмов графики последних лет:

1) ориентация на фотореалистичные изображения с 16 миллионами цветов (24 бита);

2) использование сжатия с потерями, возможность за счет потерь регулировать качество изображений;

3) использование избыточности изображений в двух измерениях;

4) появление существенно несимметричных алгоритмов;

5) увеличивающаяся степень сжатия.