УДК 681.3

Сергеева Ю. В.

Национальный горный университет, Украина

Фрактальные методы сжатия изображений

Задача хранения и передачи информации в компактном виде всегда являлась актуальной в информатике. И если относительно текстовой информации разработаны довольно эффективные методы сжатия данных, то разработки качественной компрессии статических изображений и динамической видеоинформации только набирают обороты. На сегодняшний день существуют и широко применяются стандартные методы сжатия. Однако потребность в хранении все больших объемов информации и желание передачи её по каналам связи с максимальной скоростью обусловили интерес к исследованию и разработке более совершенных методов. Развитие теории фракталов и соответствующего математического аппарата в конце XX в. повлекло разработку принципиально нового алгоритма сжатия изображений — фрактального. Данный алгоритм сжатия потенциально способен обеспечить наилучшее соотношение степени сжатия и качества восстановленного изображения.

Фрактал — это бесконечно самоподобная геометрическая фигура, каждый фрагмент которой повторяется при уменьшении масштаба. Масштабная инвариантность, наблюдаемая во фракталах, может быть либо точной, либо приближённой. В более широком смысле под фракталами понимают множества точек в евклидовом пространстве, имеющие дробную метрическую размерность (в смысле Минковского или Хаусдорфа), либо метрическую размерность, строго большую топологической. Термин «фрактал» был введён Бенуа Мандельбротом в 1975 году и получил широкую популярность с выходом в 1977 году его книги «Фрактальная геометрия природы».

Алгоритм фрактального сжатия изображения относят к алгоритмам архивации с частичной потерей информации. Основа метода фрактального кодирования — это обнаружение самоподобных участков в изображении. Идея компрессии изображения основана на применений систем итерируемых функций (Iterated Function System или IFS). Впервые возможность применения теории IFS к проблеме сжатия изображения была исследована Майклом Барнсли. Джеквин представил метод фрактального кодирования, в котором используются системы доменных и ранговых блоков изображения (domain and range subimage blocks), блоков квадратной формы, покрывающих все изображение. Этот подход стал основой для большинства методов фрактального кодирования. Согласно методу изображение должно быть разбито на множество неперекрывающихся ранговых подизображений, также определяется множество перекрывающихся доменных подизображений. Для каждого рангового блока алгоритм кодирования находит наиболее подходящий доменный блок и аффинное преобразование, которое переводит этот доменный блок в данный ранговый блок. Структура изображения отображается в систему ранговых блоков, доменных блоков и преобразований. Идея заключается в следующем: предположим, что исходное изображение является неподвижной точкой некоего сжимающего отображения. Тогда можно вместо самого изображения запомнить каким-либо образом это отображение, а для восстановления достаточно многократно применить это отображение к любому стартовому изображению. По теореме Банаха, такие итерации всегда приводят к неподвижной точке, то есть к исходному изображению.

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

Например, к наглядным примерам фрактальных изображений полученных с помощью IFS можно отнести «треугольник Серпинского» и «папоротник Барнсли» рис.1.

Рис.1. «Треугольник Серпинского» и «папоротник Барнсли»

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

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

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

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

вычислительных ресурсов.

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

Подавляющее большинство исследований в области фрактального сжатия сейчас направлены на уменьшение времени архивации, необходимого для получения качественного изображения. На данный момент известно достаточно большое количество алгоритмов оптимизации перебора, возникающего при фрактальном сжатии. Для увеличения скорости кодирования велась работа по двум направлениям. Первый подход разрешал задачу классификации доменов (classification of domains), при котором за счет уменьшения количества доменов среди которых ведется поиск, сокращается количество вычислений. Второй подход основан на методе выделения особенностей (feature extraction), увеличение скорости кодирования происходит за счет сравнения доменных и ранговых блоков. Интересное решение проблемы длительного кодирования предложил Д.С. Ватолин в своей работе «Использование ДКП для ускорения фрактального сжатия изображений». Дискретное косинусное преобразование (ДКП) используется для разбиения всего множества блоков в изображении на 256 классов, что позволяет достичь почти 100-кратного ускорения работы алгоритма при приемлемых потерях в качестве изображения.

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

Фрактальные методы можно рассматривать, как альтернативу технологиям, основанным на преобразовании Фурье, например, таким как JPEG. Новые технологии, такие как фрактальные должны рассматриваться не только как конкуренты, но и как союзники в установлении новых стандартов.

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

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

1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов. Сжатие изображений и видео. — М.: ДИАЛОГ-МИФИ, 2003

2. С. Уэлстид. Фракталы и вейвлеты для сжатия изображений в действии. Учебное пособ.-М.: Издательство «Триумф»,2003-320с.

3. Д.С. Ватолин, Алгоритмы сжатия изображений. Методическое пособие: Москва, 1999.

4. Д.С. Ватолин. Использование ДКП для ускорения фрактального сжатия изображений. Журнал «Программирование» №3 1999, с. 51-57

5. Кроновер Р.М. Фракталы и хаос в динамических системах. Основы теории: М., Постмаркет, 2000.