Алгоритм фрактального метода сжатия изображения

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

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

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

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

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

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

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

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

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