Представление изображений с помощью фракталов

В последние время фракталы стали очень популярны. Большую роль в этом сыграла книга франко-американского математика Бенуа Мандельброта "Фрактальная геометрия природы", изданная в 1975 году. Что же такое фрактал?

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

Для классификации фракталов часто используют деление на следующие классы:

§ геометрические фракталы;

§ алгебраические фракталы;

§ стохастические фракталы.

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

Геометрические фракталы

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

Рассмотрим один из таких фрактальных объектов - триадную кривую Коха. Построение кривой начинается с отрезка единичной длины (рис. 1.6) - это 0-е поколение кривой Кох. Далее каждое звено (в нулевом поколении один отрезок) заменяется на образующий элемент, обозначенный на рис.1 через n=1. В результате такой замены получается следующее поколение кривой Кох. В 1-ом поколении - это кривая из четырех прямолинейных звеньев, каждое длиной по 1/3. Для получения 3-го поколения проделываются те же действия - каждое звено заменяется на уменьшенный образующий элемент. Итак, для получения каждого последующего поколения, все звенья предыдущего поколения необходимо заменить уменьшенным образующим элементом. Кривая n-го поколения при любом конечном n называется предфракталом. На рис. 1.6 представлены пять поколений кривой. При n стремящемся к бесконечности кривая Кох становится фрактальным объектом.

Рис. 1.6. Построение триадной кривой Коха

Три копии кривой Коха, построенные (остриями наружу) на сторонах правильного треугольника, образуют замкнутую кривую, называемую снежинкой Коха.

Алгоритм построение фрактала можно описать словесно, как показано на примере построение кривой Коха, либо математически, как будет показано в следующем разделе для алгебраических фракталов. Но существует еще один способ описания алгоритма построения геометрических фракталов с помощью L-систем (системы Линдемайера). L-система это формальная грамматика, используемая для моделирования процессов роста и развития растений.

Изначально L-системы были введены при изучении формальных языков, а также использовались в биологических моделях селекции. С их помощью можно строить многие известные самоподобные фракталы, включая снежинку Коха и ковер Серпинского.

L-система определяется как кортеж G=(V, w, P), где V – алфавит, представляющий набор символов, содержащих элементы которые могут быть представлены графически, w – аксиома, которая представляет собой строку символов из V, определяющая начальное состояния системы, P - представляет собой набор правил производства новой строки, путем замены символов текущего состояния системы на ряд новых. Правила грамматики L-системы применяются итеративно, начиная с начального состояния.

Рассмотрим L-систему, где алфавит состоит всего из двух символов V={a,b}. Аксиома w=a. Правила производства описываются как p1: a→ab, p2: b→ab. Следуя итеративному принципу, каждое поколение кривой удваивается на каждом этапе: a, ab, abab, abababab. Графически a и b отображаются как два равных отрезка, соединенных под прямым углом (рис. 1.7).

Рис. 1.7. Графическое представление алфавита L-системы

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

Рис. 1.8. Графическое представление правил L-системы

На рис. 1.9 изображены пять первых итераций процесса построения фрактала.

Рис. 1.9. Первые итерации построения фрактальной кривой

Такая предельная фрактальная кривая (при числе итераций стремящимся к бесконечности) называется драконом Хартера-Хейтуэя и представлена на рис. 1.10.

Рис. 1.10. Дракон Хартера-Хейтуэя

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

Равносторонний треугольник M₀ делится прямыми, параллельными его сторонам, на 4 равных равносторонних треугольника. Из треугольника удаляется центральный треугольник. Получается множество M₁, состоящее из 3 оставшихся треугольников "первого ранга". Поступая точно так же с каждым из треугольников первого ранга, получим множество M₂, состоящее из 9 равносторонних треугольников второго ранга. Продолжая этот процесс бесконечно, получим бесконечную последовательность M₀, M₁,…, M_n,…пересечение членов которой есть треугольник Серпинского (рис. 1.11).

Рис. 1.11. Построение салфетки Серпинского

Алгебраические фракталы

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

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

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

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

В качестве примера рассмотрим множество Мандельброта.

Множество Мандельброта — это фрактал, определённый как множество точек c на комплексной плоскости, для которых итеративная последовательность

z₀ = 0

z_n+1 = z_n²+c

не уходит в бесконечность.

Таким образом, вышеуказанная последовательность может быть раскрыта для каждой точки c на комплексной плоскости следующим образом:

c = x + i ∙ y

Z₀ = 0

Z₁ = Z₀² + c

= x + i ∙ y

Z₂ = Z₁² + c

= (x + i ∙ y)² + x + i ∙ y

= x² + 2∙i∙x∙y – y² + x + i ∙ y

= x² – y² + x + (2 ∙ x ∙ y + y) ∙ i

Z₃ = Z₂² + c = …

и так далее.

Если переформулировать эти выражения в виде итеративной последовательности значений координат комплексной плоскости x и y, т. е. заменив z_n на x_n + i ∙ y, а c на p + i ∙ q, мы получим:

Суть метода построения множества Мандельброта состоит в следующем. Для каждого пикселя, отображающего некоторую точку с координатами (a, b), проводят серию вычислений по формулам (*). При этом исходные значения x₀ и y₀ для каждой новой точки (a, b) изначально всегда равны нулю. На каждом шаге, кроме очередных значений x_i+1 и y_i+1, вычисляют величину r_i = . Эта величина представляет собой не что иное, как расстояние от точки (x_i, y_i) до начала координат. Точка (a, b) считается принадлежащей множеству Мандельброта, если она в процессе вычислений никогда не удаляется от начала координат на критическое расстояние, большее или равное двум. Такой пиксель окрашивается в черный цвет. Для всех прочих значений a и b величина r_i может переходить запретный рубеж в две единицы за разное количество шагов. В зависимости от этого, точку окрашивают в соответствующий цвет.

Критическое значение при программировании имеет скорость вычислений. Существенно влияют на время расчетов операции возведения в степень и извлечение квадратного корня. Возведение в квадрат целесообразно заменить умножением. Возводить координаты в квадрат следует лишь один раз, сохраняя результаты в промежуточных переменных (x2 и y2). От извлечения квадратного корня вообще следует отказаться. Вместо самого значения расстояния r_i можно вычислять лишь сумму квадратов x² + y², сравнивая ее не с двойкой, а с четверкой.

Функции для генерации множества Мандельброта приведены ниже. В зависимости от полученного значения k (обратного счетчика итераций), очередная точка закрашивается в соответствующий цвет (в данном случае точка окрашивается в различные градации серого цвета). Если k оказывается равным нулю, то точка с координатами (a, b) принадлежит множеству Мандельброта. В отношении всех прочих точек имеет значение, насколько велико или мало значение k. Оно характеризует скорость убегания величины r_i за дозволенный предел при данных значениях a и b.

private Color GetColor(double a, double b)

// Функция, возвращающая цвет точки (a, b)

{

double x = 0, y = 0, r = 0;

//количество итераций для каждой точки

int k = 100;

while ((r<4) && (k>0))

{

Double x2 = x * x;

Double y2 = y * y;

Double xy = x * y;

x = x2 - y2 + a;

y = 2 * xy + b;

r = x2 + y2;

k--;}

k = 255*k/100;

Color p = Color.FromArgb(255, k, k, k);

return p;

}

private void Mbut_Click(object sender, EventArgs e)

//Функция построения множества Мандельброта

//в квадрате размером 400 x 400 пикселей

{

//Определение области построения

const double xmin = -2;

const double xmax = 1;

const double ymin = -1.5;

const double ymax = 1.5;

//длинна стороны квадрата

const int n = 400;

//определение приращения по x и по y

double hx = (xmax - xmin) / n;

double hy = (ymax - ymin) / n;

Bitmap bmp;

bmp = new Bitmap(this.ClientSize.Width, this.ClientSize.Height);

double x = xmin;

double y = ymax;

for (int j = 1; j < n; j++)

{

for (int i = 1; i < n; i++)

{

Color c = GetColor(x, y);

bmp.SetPixel(i, j, c);

x = x + hx;

}

y = y - hy;

x = xmin;

}

Graphics gr = CreateGraphics();

gr.DrawImage(bmp, 0, 0);

}

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

Пример работы программы и приближения к множеству Мандельброта в диапазоне для x от -2 до 1 и для y от -1,5 до 1,5 приведен на рис. 1.12.

Рис. 1.12. Множество Мандельброта

Используя туже самую итеративную последовательность z_n+1 = z_n²+c, что и для построения множества Мандельброта, можно построить другой алгебраический фрактал: множество Жюлиа. Множество Жюлиа получается, если зафиксировать в формуле значение комплексной константы (a+i∙b), которая будет одинакова для всех точек, а начальные значения x и y принимать равными значениям координатам вычисляемой точки. В этом случае, код функции получения цвета точки будет выглядеть следующим образом:

private Color GetColorJ(double x, double y)

{

//задаем произвольно начальную точку

double a = -0.55, b = -0.55

double r = 0;

int k = 100;

while ((r < 4) && (k > 0))

{

Double x2 = x * x;

Double y2 = y * y;

Double xy = x * y;

x = x2 - y2 + a;

y = 2 * xy + b;

r = x2 + y2;

k--;

}

k = 255 * k / 100;

Color p = Color.FromArgb(255, k, k, k);

return p;

}

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: