ПРИМЕНЕНИЕ ПРЕДВАРИТЕЛЬНОЙ КЛАССИФИКАЦИИ ДАННЫХ ДЛЯ ПОВЫШЕНИЯ СКОРОСТИ ФРАКТАЛЬНОГО СЖАТИЯ

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

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

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

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

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

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

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

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

1. Первый встречный доменный блок, удовлетворяющий условие формулы 1. Если ни один доменный блок не удовлетворяет условию:
   
   1. Берем доменный блок с минимальный СКО;
   2. Разбиваем ранговый блок на 4 блока и для каждого из них ищем подходящий доменный блок.
2. Доменный блок с минимальным СКО.

Так как многочисленные рекурсии при фрактальном сжатии отнимают большое количество времени, были разработаны различные способы ускорения процесса сжатия.

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

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

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

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

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

Таблица 1.

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

Рисунок 1. Зависимость времени выполнения фрактального сжатия от способа выбора подходящего доменного блока и типа классификации

Таблица 2.

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

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

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

Список литературы:

1. Кудрина М.А., Климентьев К.Е. Компьютерная графика. - Издательство СГАУ, 2013. – 140 с.
2. Шарабайко М., Осокин А. Быстродействующий алгоритм фрактального сжатия изображений //Известия Томского политехнического университета, 2011, №5, c. 52 – 57.