Алгоритмы сжатия изображений


Фрактальный алгоритм - часть 3


Определение. Изображением называется функция S, определенная на единичном квадрате и принимающая значения от 0 до 1 или 

Пусть трехмерное аффинное преобразование 

, записано в виде

и определено на компактном подмножестве 

декартова квадрата [0..1]x[0..1]. Тогда оно переведет часть поверхности S

в область 

, расположенную со сдвигом (e,f) и поворотом, заданным матрицей

.

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

Определение. Конечная совокупность W сжимающих трехмерных аффинных преобразований 

, определенных на областях 
, таких, что 

и 

, называется системой итерируемых функций (IFS).

Системе итерируемых функций однозначно сопоставляется неподвижная точка — изображение. Таким образом, процесс компрессии заключается в поиске коэффициентов системы, а процесс декомпрессии — в проведении итераций системы до стабилизации полученного изображения (неподвижной точки IFS). На практике бывает достаточно 7-16 итераций. Области 

в дальнейшем будут именоваться ранговыми, а области 

доменными.

Построение алгоритма

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

В учебном варианте алгоритма, изложенном далее, сделаны следующие ограничения на области:

  1. Все области являются квадратами со сторонами, параллельными сторонам изображения. Это ограничение достаточно жесткое. Фактически мы собираемся аппроксимировать все многообразие геометрических фигур лишь квадратами.

  2. При переводе доменной области в ранговую уменьшение размеров производится ровно в два раза.


    - Начало -  - Назад -  - Вперед -