2014-02-24
482
Идея алгоритма заключается в том, что мы сохраняем в файл разницу – число между средними значениями соседних блоков в изображении, которая обычно принимает значения, близкие к 
.
Так два числа 
и 
всегда можно представить в виде 
и 
, где 
, 
.
Это справедливо для последовательности 
любой длины.
Разберем конкретный пример.
Пусть мы сжимаем строку из 
значений яркости пикселов 
:
. Мы получим следующие последовательности 
и 
: 
и 
. Заметим, что значения достаточно близки к . Повторим операцию, рассматривая как 
. Данное действие выполняется как бы рекурсивно, откуда и название алгоритма. Мы получим из : 
. Полученные коэффициенты, округлив до целых и сжав, например, с помощью алгоритма Хаффмана с фиксированными таблицами, мы можем поместить в файл.
Заметим, что мы применяли наше преобразование к цепочке только два раза. Реально мы можем позволить себе применение 
-преобразования 
раз. Более того, дополнительное сжатие можно получить, используя таблицы алгоритма Хаффмана с неравномерным шагом (т.е. нам придется сохранять код Хаффмана для ближайшего в таблице значения). Эти приемы позволяют достичь заметных коэффициентов сжатия.
|
|
|
Алгоритм для двумерных данных реализуется аналогично. Если у нас есть квадрат из 
точек с яркостями 
и 
, то
Исходное B1 B2
изображение B3 B4
Используя эти формулы, мы для изображения 
пикселов получим после первого преобразования матрицы размером 
элементов:
 |
а) исходное изображение б) сжатое изображение
Рис. 3. Сжатие изображения.
В первой, как легко догадаться, будет храниться уменьшенная копия изображения. Во второй – усредненные разности пар значений пикселов по горизонтали. В третьей – усредненные разности пар значений пикселов по вертикали. В четвертой – усредненные разности значений пикселов по диагонали. По аналогии с двумерным случаем мы можем повторить наше преобразование и получить вместо первой матрицы 4 матрицы размером 
. Повторив наше преобразование в третий раз, мы получим в итоге: матрицы 
, 
матрицы и матрицы . На практике при записи в файл, значениями, получаемыми в последней строке 
, обычно пренебрегают (сразу получая выигрыш примерно на треть размера файла – 
...).
К достоинствам этого алгоритма можно отнести то, что он очень легко позволяет реализовать возможность постепенного “ проявления ” изображения при передаче изображения по сети. Кроме того, поскольку в начале изображения мы фактически храним его уменьшенную копию, упрощается показ “огрубленного” изображения по заголовку.
В отличие от JPEG и фрактального алгоритма данный метод не оперирует блоками, например, 
пикселов. Точнее, мы оперируем блоками 
, 
, и т.д. Однако за счет того, что коэффициенты для этих блоков мы сохраняем независимо, мы можем достаточно легко избежать дробления изображения на “мозаичные” квадраты.
|
|
|
Характеристики волнового алгоритма:
Коэффициенты компрессии: 
(задается пользователем).
Класс изображений: как у фрактального и JPEG.
Симметричность: 
Характерные особенности: При высокой степени сжатия изображение распадается на отдельные блоки.
