Приложение 3. Использование сиф для сжатия изображений

Впервые СИФ были применены для сжатия изображений Майклом Барнсли в 90ых. С тех пор многое из его алгоритма поменялось, однако суть осталась неизменна.

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

Далее, как показано на рис. 5, обычным перебором всех доменных и ранговых областей подыскиваем аффинное преобразование.

Рис. 5 Та самая картинка с Леной используемая во всех примерах.

Каждому ранговому блоку ставится в соответствие такой доменный блок и преобразование, которое делает этот блок наиболее похожим на ранговый.

Недостаток такого алгоритма налицо: кодировка даже сравнительно небольшого изображения займёт весьма много времени. К сожалению, не могу точно сказать, сколько времени уйдёт на кодировку конкретного изображения, ибо все примеры очень старые.

Несмотря на столь трудоёмкий процесс сжатия, восстановление закодированного изображения производится в разы быстрее.

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

И последовательно заменяем ранговые области на результат применения соответствующих преобразований на доменный блок из восстанавливаемого изображения.

Делается всё это несколько раз, до тех пор, пока не получим что-то похожее на наше изначальное изображение.

Рис. 6 Восстановление изображения за 10 итераций с применением квадратных доменных блоков со стороной 10 пикселов