Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

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

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

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

Так, два числа a-ц и а^п всегда можно представить в виде Ь1 ^{ау+агмЩ и Ь2,=(агга2н-\У2- Аналогично последовательность а, может быть попарно переведена в последовательность Ь''2{.

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

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

cS< Упражнение. Мы восстановили из файла цепочку (215, 211) (0, 5) (5, -3, 2, 4) (см. пример). Постройте строку из восьми значений яркости пикселов, которую воссоздаст алгоритм волнового сжатия.

Алгоритм для двумерных данных реализуется аналогично. Если у нас есть квадрат из четырех точек с яркостями ая,у, a»+i,$> ая,#+1 и fl«+i,#+i>T0

Kj = («21.27 + «2,41.2, +av.2j+\ + «2,41.2,4. )/45

kfj ~ («2,.2/ + «2,41.2/ ~«2,.2,4I ~ «2,41,2/4 )/45

6Л,' = («2,.2, -«2,41,2/ + «2,,2,4I ~ «2,41,2,41 )/4J

ft,\/ = («2,,2/ - «2,41,2, ~ «2/.2,41 + «2,41.2/+l ) 7 4'

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



Рис. 2.7. Вид двумерного wavelet-преобразования

В первой, как легко догадаться, будет храниться уменьшенная копия изображения. Во второй - усредненные разности пар значений пикселов по горизонтали. В третьей - усредненные разности пар значений пикселов по вертикали. В четвертой - усредненные разности значений пикселов по диа­гонали. По аналогии с двумерным случаем мы можем повторить наше пре­образование и получить вместо первой матрицы 4 матрицы размером 128x128. Повторив наше преобразование в третий раз, мы получим в итоге: 4 матрицы 64x64, 3 матрицы 128x128 и 3 матрицы 256x256. На практике при записи в файл значениями, получаемыми в последней строке {b*j),

обычно пренебрегают (сразу получая выигрыш примерно на треть размера файла-1-1/4-1/16-1/64...).

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

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

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

Характерные особенности: кроме того, при высокой степени сжатия I изображение распадается на отдельные блоки..