Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
ОТЦС_Ч1_2008.doc
Скачиваний:
13
Добавлен:
01.07.2025
Размер:
5 Мб
Скачать
☆

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

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

Идея алгоритма заключается в том, что вместо кодирования собственно изображений сохраняется разница между средними значениями соседних блоков в изображении, которая обычно принимает значения, близкие к нулю. Так, два числа a2i и a2i+1 всегда можно представить в виде b i 1 = (a2i + a2i+1)/2 и b i 2 = = (a2i – a2i+1)/2. Аналогично последовательность ai может быть попарно переведена в последовательность b i 1,2.

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

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

Если имеется квадрат из четырех точек с яркостями a2i ,2j , a2i+1 , a 2j, a2i ,2j+1 , и a2i+1 , a 2j+1 , то

(2.39)

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

Исходное

изображение

B1

B2

B3

B4 

 

Рис. 2.35 Рис. 2.36

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

По аналогии с двумерным случаем можно повторить преобразование и получить вместо первой матрицы четыре матрицы размером 128 х 128. Применять операцию к трем остальным (уже разностным) матрицам особого смысла нет, поскольку абсолютные значения разностей уже и так малы.

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

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