Исследование зависимости скорости фрактального сжатия изображения от параметров сжатия

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

В данной работе рассматривается алгоритм фрактального сжатия изображений, основанный на том, что мы представляем изображение в более компактной форме - с помощью коэффициентов системы итерируемых функций Iterated Function System (IFS). IFS представляет собой набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (х_координата, у_координата, яркость) [2].

По своей сути, фрактальное сжатие (или фрактальная компрессия) - это процесс поиска самоподобных областей изображения и определения для них параметров аффинных преобразований.

Для реализации алгоритма компрессии необходимо учитывать следующие правила [1]:

1)  исходное изображение разбивается на подобласти, которые представляют из себя квадраты, называемые ранговыми блоками. Ранговые блоки пересекаться не могут;

2)  на исходном изображении выделяются домены – совокупности четырех ранговых блоков. Домены могут пересекаться. Все ранговые блоки и домены – это квадраты со сторонами, параллельными изображению;

3)  для каждого рангового блока производится попытка найти на изображении домен, такой чтобы этот домен можно было преобразовать в ранговый блок при помощи аффинных преобразований;

4)  перевод домена в ранговый блок производится с помощью поворота домена на 0°, 90°, 180°, 270° и с помощью зеркального преобразования;

5)  при переводе доменной области в ранговую, ее линейный размер уменьшается в 2 раза;

6)  изменение яркости производится кратно некоторому коэффициенту;

7)  совпадение преобразованного домена с ранговым блоком может производиться при помощи среднеквадратичного отклонения:

где:  – точка в домене;  – точка в блоке;  – пороговое значение «похожести»;

8)  если же для некоторого рангового блока не было найдено ни одного удовлетворяющего среднеквадратичному отклонению домена, то ранговый блок разбивается на 4 подобласти, и для каждой из них ищутся домены;

9)  координаты, которые будут сохраняться в файл:

·     координата 2 числа;

·     3 бита (номер аффинного преобразования);

·     изменение яркости.

При фрактальном сжатии может использоваться несколько различных алгоритмов разбиения на ранговые блоки; также программная реализация сжатия отличается для цветных изображений и изображений в градациях серого.

Для проведения данного исследования была разработана программа, производящая фрактальное сжатие изображения в градациях серого с использованием алгоритма разбиения изображения на множество блоков фиксированного размера.

Исследование проводилось над изображением, сохраненным в размерах 64´64, 160´160, 312´312, 368´368 и 400´400. Исследовалась зависимость времени сжатия от размера рангового блока и коэффициента компрессии  (порогового значения «похожести»).

Результаты исследований можно видеть на следующих таблицах и рисунках:

Таблица 1.

Зависимость времени компрессии изображений разных размеров от размера рангового блока

Рисунок 1. Зависимость времени компрессии изображений разных размеров от размера рангового блока

Как видно из рисунка 1 уменьшение или увеличение рангового блока не может гарантированно уменьшать или увеличивать время компрессии.

Таблица 2.

Зависимость времени компрессии изображения размером 160´160 от размера рангового блока и коэффициента компрессии

Рисунок 2. Зависимость времени компрессии изображения размером 160´160 от размера рангового блока и коэффициента компрессии

Таблица 3.

Зависимость времени компрессии изображений разного размера от коэффициента компрессии

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

Рисунок 3. Зависимость времени компрессии изображений разного размера от коэффициента компрессии

Из рисунка 3 следует что увеличение коэффициента компрессии для любого размера изображения приводит к уменьшению времени компрессии.