Статья:

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

Конференция: XLIV Студенческая международная заочная научно-практическая конференция «Молодежный научный форум: технические и математические науки»

Секция: Технические науки

Выходные данные
Сахибназарова В.Б. Исследование зависимости скорости фрактального сжатия изображения от параметров сжатия // Молодежный научный форум: Технические и математические науки: электр. сб. ст. по мат. XLIV междунар. студ. науч.-практ. конф. № 4(44). URL: https://nauchforum.ru/archive/MNF_tech/4(44).pdf (дата обращения: 18.10.2018)
Лауреаты определены. Конференция завершена
Эта статья набрала 0 голосов
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

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

Сахибназарова Виктория Бахтиёровна
студент, СНИУ им. академика С.П. Королева, РФ, г. Самара

 

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

В данной работе рассматривается алгоритм фрактального сжатия изображений, основанный на том, что мы представляем изображение в более компактной форме - с помощью коэффициентов системы итерируемых функций 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.

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

Размер рангового блока

2

4

8

16

64´64

0,0312

0,3900007

0,1092002

193

160´160

0,7800014

13,732785

5,838334

281

312´312

10,2024179

191,50594

85,28535

474

368´368

22,5662907

383,18492

165,85549

698

400´400

32,6388668

596,64913

237,55459

1133

 

 

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

 

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

Таблица 2.

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

Размер рангового блока/ коэффициент компрессии

2

4

8

16

100

14,9604263

18,252032

6,832812

380

200

0,0210012

9,599549

5,0272875

300

300

0,0180011

4,5722615

4.0362309

240

 

 

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

 

Таблица 3.

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

Коэффициент компрессии

10

20

50

100

200

64´64

0,962055003

0,8830505

0,5510315

0,4210241

0,242014

160´160

40,9073398

35,8182

24,903424

18,2510439

9,418539

312´312

617,9183429

493,53923

351,3979

257,6968526

143,1965

368´368

1279,203166

1003

794

515,2814724

259,2438

400´400

1721,814482

1519,0613

1100

800

413,5637

 

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

 

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

 

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

 

Список литературы:
1. Ансон Л., Барнсли М. Фрактальное сжатие изображения // Мир ПК, 1992, № 4, С. 52–58.
2. Кудрина М.А., Климентьев К.Е. Компьютерная графика.  Издательство СГАУ, 2013. – 140 с.