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

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

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

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