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

 Рис 4. Участок границы  множества Мандельброта, увеличенный в 200 pаз.

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

 

2.3 Стохастические фракталы

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

Существуют и другие классификации фракталов, например деление фракталов на детерминированные (алгебраические и геометрические) и недетерминированные (стохастические).

 

3. Системы итерируемых  функций

Метод "Систем Итерируемых Функций" (Iterated Functions System - IFS) появился в середине 80-х годов как простое средство получения фрактальных структур.

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

X' = A*X + B*Y + C

Y' = D*X + E*Y + F

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

На основании этих идей Барнсли и Слоан создали алгоритм, который, по их утверждению, позволит сжимать информацию в 500-1000 раз. Теоретическое обоснование метода изложено в [1]. Вкратце метод можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), т.е. коэффициентами этих преобразований (в нашем случае A,B,C,D,E,F).

Например, закодировав какое-то изображение двумя аффинными преобразованиями, мы однозначно определяем его с помощью 12-ти коэффициентов. Если теперь задаться какой-либо начальной точкой (например X=0 Y=0) и запустить итерационный процесс, то мы после первой итерации получим две точки, после второй - четыре, после третьей - восемь и т.д. Через несколько десятков итераций совокупность полученных точек будет описывать закодированное изображение. Но проблема состоит в том, что очень трудно найти коэффициенты IFS, которая кодировала бы произвольное изображение.

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

X' = (A1*X + B1*Y + C1) / (D1*X + E1*Y + F1)

Y' = (A2*X + B2*Y + C2) / (D2*X + E2*Y + F2)

или квадратичные:

X' = A1*X*X + B1*X*Y + C1*Y*Y + D1*X + E1*Y + F1

Y' = A2*X*X + B2*X*Y + C2*Y*Y + D2*X + E2*Y + F2

преобразования на плоскости.

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

 Рис 5. Заготовка для  построения IFS "дракона" Хартера-Хейтуэя.

Построим IFS для "дракона" Хартера-Хейтуэя. Для этого расположим первое поколение этого фрактала на сетке координат дисплея 640 x 350 (Рис.5). Обозначим точки получившейся ломаной A, B, C. По правилам построения (раздел 2.1) у этого фрактала две части, подобные целому - на рис.5 это ломаные ADB и BEC. Зная координаты концов этих отрезков, можно вычислить коэффициенты двух аффинных преобразований, переводящих ломаную ABC в ADB и BEC:

X' = -0.5*X -0.5*Y + 490

Y' = 0.5*X -0.5*Y + 120

X' = 0.5*X -0.5*Y + 340

Y' = 0.5*X +0.5*Y - 110

Задавшись начальной стартовой точкой (например X=0 Y=0) и итерационно действуя на нее этой IFS, после десятой итерации на экране получим фрактальную структуру, изображенную на рис.6, которая представляет собой "дракон" Хартера-Хейтуэя. Его кодом (сжатым описанием) является набор коэффициентов двух аффинных преобразований.

 Рис 6. "Дракон" Хартера-Хейтуэя, постpоенный с помощью IFS в пpямоугольнике 640x350.

Аналогично можно построить IFS для кривой Кох. Нетрудно видеть, что эта кривая имеет четыре части, подобные целой кривой (раздел 2.1 Рис 1.). Для нахождения IFS опять расположим первое поколение этого фрактала на сетке координат дисплея 640 x 350 (Рис.7).

 Рис 7. Заготовка для построения IFS кpивой Кох.

Для ее построения требуется набор аффинных преобразований, состоящий из четырех преобразований:

X' = 0.333*X + 13.333

Y' = 0.333*Y + 200

 

X' = 0.333*X + 413.333

Y' = 0.333*Y + 200

 

X' = 0.167*X + 0.289*Y + 130

Y' = -0.289*X + 0.167*Y + 256

 

X' = 0.167*X - 0.289*Y + 403

 Y' = 0.289*X + 0.167*Y + 71

Результат применения этого аффинного коллажа после десятой итерации можно увидеть на рис.8.

 Рис 8. Кpивая Кох, постpоенная с помощью IFS в пpямоугольнике 640x350.

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

 

Библиографический список

 

[1] Бондаренко В.А.,Дольников В.Л. Фрактальное сжатие изображений по Барнсли-Слоану. // Автоматика и телемеханика.-1994.-N5.-с.12-20.

[2] Витолин Д. Применение фракталов в машинной графике. // Computerworld-Россия.-1995.-N15.-с.11.

[3] Федер Е. Фракталы. Пер. с англ.-М.: Мир,1991.-254с. (Jens Feder, Plenum Press, NewYork, 1988)

[4] Application of fractals and chaos. 1993, Springer-Verlag, Berlin.