Статья:

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

Конференция: III Студенческая международная научно-практическая конференция «Технические и математические науки. Студенческий научный форум»

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

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

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

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

 

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

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

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

Общий алгоритм фрактального сжатия представлен на рисунке 1.

Степень схожести рангового и доменного блока вычисляется как среднее квадратическое отклонение (СКО):

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

Подходящий доменный блок может выбираться несколькими способами:

1)  Первый встречный доменный блок, удовлетворяющий условие формулы 1. Если ни один доменный блок не удовлетворяет условию:

a.   Берем доменный блок с минимальный СКО;

b.  Разбиваем ранговый блок на 4 блока и для каждого из них ищем подходящий доменный блок.

2)  Доменный блок с минимальным СКО;

 

Рисунок 1. Общий алгоритм фрактального сжатия изображения

 

Для ускорения процесса сжатия можно выделить 2 подхода:

1) Предварительная классификация блоков [2];

2) Метод «эталонного» блока (эталонный подход).

Алгоритм эталонного подхода включает следующие шаги:

1) Выбираем эталонный блок (пример эталонного блока представлен на рисунке 2), размером соответствующий ранговому блоку;

2) Для каждого доменного блока ищем его СКО от эталонного блока;

3) Для каждого рангового блока:

a. Ищем его СКО от эталонного блока;

b. Выбираем доменный блок, удовлетворяющий условию ;

c. Сохраняем параметры найденного доменного блока.

 

Рисунок 2. Пример эталонного блока

 

Таким образом, мы избегаем необходимости вычислять СКО между каждым ранговым и каждым доменным блоками, единожды вычислив СКО между доменами и эталонным блоком.

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

 

Рисунок 3. Применение эталонного подхода: а) исходное изображение б) изображение, получившееся в результате декомпрессии

 

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

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

Исследование проводилось над изображением размером 160´160 пикселя, размером рангового блока 2, 4, 8 и 16 пикселей.

Таблица 1.

Зависимость времени компрессии изображения от выбранного метода

Подходы:

Минимальный доменный блок

Классификация центром масс

"Эталонный" метод

Размер рангового блока 4 пикселя

209,88

84,55

82,02

Размер рангового блока 8 пикселей

32,81

14,57

29,66

 

Рисунок 4. Зависимость времени компрессии изображения от выбранного метода

 

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

 

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