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

Английское название рекурсивного сжатия — 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.

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

Алгоритм для двумерных данных реализуется аналогично.

Если у нас есть квадрат из четырех точек с яркостями a_2i ,_2j , a_2i+1 , a _2j, a_2i , _2j+1 , и a_2i+1 , a _2j+1 , то

(2.21)

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

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

Рис. 2.14 Рис. 2.15

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

По аналогии с двумерным случаем можно повторить преобразование и получить вместо первой матрицы 4 матрицы размером 128х128.

Повторив преобразование в третий раз, получим в итоге 4 матрицы 64х64, 3 матрицы 128х128 и 3 матрицы 256х256. Дальнейшее сжатие происходит за счет того, что в разностных матрицах имеется большое число нулевых или близких к нулю значений, которые после квантования эффективно сжимаются.

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

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

Дата добавления: 2014-01-07