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

↑

▷ Содержание

⇐ ПредыдущаяСтр 7 из 9Следующая ⇒

Английское название рекурсивного сжатия - 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 раз. Более того, дополнительное сжатие можно получить, используя таблицы алгоритма Хаффмана с неравномерным шагом (т.е. нам придется сохранять код Хаффмана для ближайшего в таблице значения). Эти приемы позволяют достичь заметных коэффициентов сжатия.

Для изображения 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 и т.д. Однако за счет того, что коэффициенты для этих блоков мы сохраняем независимо, мы можем достаточно легко избежать дробления изображения на «мозаичные» квадраты.

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

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

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

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

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

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

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

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология