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

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

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

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

Таблица 2.

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

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

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