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

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

Так два числа и всегда можно представить в виде и , где , .

Это справедливо для последовательности любой длины.

Разберем конкретный пример.

Пусть мы сжимаем строку из значений яркости пикселов :
. Мы получим следующие последовательности и : и . Заметим, что значения достаточно близки к . Повторим операцию, рассматривая как . Данное действие выполняется как бы рекурсивно, откуда и название алгоритма. Мы получим из : . Полученные коэффициенты, округлив до целых и сжав, например, с помощью алгоритма Хаффмана с фиксированными таблицами, мы можем поместить в файл.

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

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

Исходное B¹ B²

изображение B³ B⁴

Используя эти формулы, мы для изображения пикселов получим после первого преобразования матрицы размером элементов:

а) исходное изображение б) сжатое изображение

Рис. 3. Сжатие изображения.

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

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

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