Статья:

Повышение скорости фрактального сжатия изображения при помощи классификации

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

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

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

Повышение скорости фрактального сжатия изображения при помощи классификации

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На практике может понадобиться сохранить в файл дополнительную информацию, например, изначальный размер рангового блока, или (в случае разбиения рангового блока на 4 подобласти) степень разбиения конкретного блока.

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

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

В данной работе используется классификация на основе нахождения центра масс. То есть, для каждого блока ищется среднее значение яркости. Разбиение идет на 5 классов: с яркостью меньше 50, от 50 до 99, от 100 до 149, от 150 до 199 и от 200 до 256.

Классификация проводится путем обхода всех доменных блоков до начала непосредственного процесса сжатия. Установка класса рангового блока происходит перед началом поиска для него подходящего домена.

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

Исследование проводилось над изображением, сохраненным в размерах 64´64, 160´160, 312´312, 368´368 и 400´400. Размер рангового блока брался равный 4 пикселям.

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

Таблица 1.

Зависимость времени компрессии изображений от использования классификатора (коэффициент сжатия – 10)

Размер изображения

64´64

160´160

312´312

368´368

400´400

Без классификатора

0,393022

16,21093

179,6333

306,8195491

437,97705

С классификатором

0,141008

2,469141

23,23533

27,9115393

35,816049

 

 

Рисунок 1. Зависимость времени компрессии изображений от использования классификатора (коэффициент сжатия – 10)

 

Таблица 2.

Зависимость времени компрессии изображений от использования классификатора (коэффициент сжатия – 100)

Размер изображения

64´64

160´160

312´312

368´368

400´400

Без классификатора

0,099006

4,328248

52,92103

93,7883644

127,22628

С классификатором

0,011001

0,046003

0,218013

0,3640208

0,4710269

 

 

Рисунок 2. Зависимость времени компрессии изображений от использования классификатора (коэффициент сжатия – 100)

 

Как видно из таблиц и рисунков, использование предварительной классификации, даже при разной степени сжатия изображения позволяет значительно повысить скорость сжатия изображения.

 

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