Фракталы
Фракталы
Cреди всех картинок, которые может создавать компьютер, лишь немногие могут поспорить с фрактальными изображениями, когда идет речь о подлинной красоте. У большинства из нас слово "фрактал" вызывает в памяти цветные завитушки, формирующие сложный, тонкий и составной узор. Но на самом деле этот термин имеет гораздо более широкий смысл. Фрактал - объект, обладающий бесконечной сложностью, позволяющий рассмотреть столько же своих деталей вблизи, как и издалека. Земля -классический пример фрактального объекта. Из космоса она выглядит как шаp. Если приближаться к ней, мы обнаружим океаны, континенты, побережья и цепи гор. Будем рассматривать горы ближе - станут видны еще более мелкие детали: кусочек земли на поверхности горы в своем масштабе столь же сложный и неровный, как сама гора. И даже еще более сильное увеличение покажет крошечные частички грунта, каждая из которых сама является фрактальным объектом.
Компьютеры дают возможность строить модели таких бесконечно детализированных структур. Есть много методов создания фрактальных изображений на компьютере. Два профессора математики из Технологического института штата Джоржия разработали широко используемый метод, известный как Cистемы Итерируемых Функций (СИФ). С помощью этого метода создаются реалистичные изображения природных обьектов, таких, например, как листья папортника, деревья, при этом неоднократно применяются преобразования, которые двигают, изменяют в размере и вращают части изображения. В СИФ используется самоподобие, которое есть у творений природы, и объект моделируется как композиция множества мельчайших копий самого себя. Фрактальные изображения с многоцветными завитушками относятся обычно к разряду так называемых фракталов с вpеменным поpогом, которые изображаются точками на комплексной плоскости с цветами, отражающими время, требуемое для того, чтобы орбита данной точки перешла ("перебежала") определенную границу. Комплексная плоскость - как координатная плоскость с осями x и y. По паре координат точка строится на комплексной плоскости так же, как и точка на плоскости Oxy, но числа имеют другой, необычный смысл: они обладают мнимой компонентой, называемой i, которая равна квадратному корню из -1. ( Вот почему i - мнимая единица – в действительности корень из -1 не существует.) Это искажает обычные правила математики, так что такие общепринятые операции как умножение двух чисел, дают необычные результаты.
Наиболее известный фрактал, множество Мандельброта - фрактал с вpеменным поpогом. Для каждой точки на экране компьютер считает координаты серии точек, определяющих мнимый путь, называемый орбитой. Точки, чьи орбиты никогда не выходят за пределы мнимого цилиндра, расположенного в начале кооординат комплексной плоскости, считаются элементами множества Мандельброта и обычно закрашиваются черным. Точки, чьи орбиты выходят за пределы цилиндра, раскрашиваются в соответствии с быстротой "убегания": пиксел, чья орбита покидает цилиндр, например, на шестой итерации, можно раскрасить голубым, a тот - орбите которого требуется для этого семь итераций - красным. В результате на изображении получим множество Мандельброта и его окружение с "нестабильными" областями фрактала - областями, для которых малые изменения формулы ведут к большой разнице в орбитальном поведении. Это характеризуется густотой закраски рисунка. Меняя формулу для подсчета орбит, получим другие, такие же экзотические фракталы с вpеменным поpогом. Бесконечно детализированная структура множества Мандельброта становится "ясной", когда вы увеличиваете произвольную область. Неважно, сколь маленький участок вы рассматриваете: рисунок, который вы увидите, будет одинаково сложным. Почему? Потому что в двумерной плоскости, на которой строится множество Мандельброта, любая область содержит бесконечное число точек. Когда вы выбираете область для отображения, компьютер точкам из области ставит в соответствие точки на экране. И каждая точка, выбранная как угодно близко к другой, имеет свою характеристическую орбиту, порождающую соответствующий цветовой узор.
Фракталы - не только предмет математического любопытства, они имеют полезные приложения. Фрактальные пейзажи, например,использовались как декорации в научно-фантастических фильмах, например в "Star Trec - 2. The Wrath of Khan". СИФ-фракталы используются для сжатия изображений, и фрактальный метод часто дает лучшие результаты при многократном сжатии чем JPEG и другие методы сжатия, с малыми потерями качества изображения. Фракталы с вpеменным поpогом используются для моделирования поведения хаотических динамических систем (систем, в которых небольшие изменения входных данных влекут за собой большие изменения в выходе) таких, как поведение погоды. Но довольно разговоров. Давайте взглянем на некоторые фракталы и на бесконечное множество узоров, содержащихся в них. Для того чтобы улучшить Ваше понимание процесса создания фракталов, мы пройдемся по СФИ-алгоритму, используемому для рисования листа папортника и по алгоритму с временным порогом, который дает жизнь множеству Мандельброта.
Как строится множество Мандельброта?
1. Множество Мандельброта - самый известный фрактал в мире. Он также является классическим примером фрактала с временным порогом. Точки, составляющие множество Мандельброта, изображаются на комплексной плоскости, которая очень похожа на систему координат Oxy. Но если на обычной координатной плоскости изображаются действительные числа, то комплексная плоскость содержит комплексные числа - числа, с действительной и мнимой частью. Это полностью 'переворачивает' обычные правила математики и приводит к очень необычным результатам.
2. Для каждой точки на экране компьютер проводит серию вычислений, используя соответствующую точку на комплексной плоскости. Координаты точки входят в простое уравнение, по которому определяется новая пара координат. Эти координаты подставляются опять в то же уравнение и получается еще одна пара координат. Многократно повторяя этот процесс - обычно несколько сотен раз - получаем набор координат, определяющий мнимый путь, называемый орбитой. Хотя эта орбита полностью лежит в комплексной плоскости (она имеет 2 измерения, а не три), она нарисована здесь возвышающейся над плоскостью для лучшего зрительного восприятия.
3. Если орбита точки никогда не 'убегает' из цилиндра определенного диаметра расположенного в начале координат комплексной плоскости, то говорится, что эта точка - элемент множества Мандельброта. Точки, удовлетворяющие этому критерию, обычно закрашиваются черным цветом.
4. Если орбита точки 'убегает' из цилиндра, то соответствующему пикселу приписывается цвет, который отображает число точек орбиты, посчитанных прежде, чем эта точка выйдет из цилиндра. Этот промежуток времени, необходимый для выхода орбитальных точек из цилиндра называется временем убегания (escape-time).
5. . Когда эта процедура будет применена к каждому пикселу на экране, будет сгенерировано разноцветное изображение множества Мандельброта. Меняя уравнения для расчета орбит, но оставив тот же общий метод, получим другие сложные, детализированные фракталы c вpеменным поpогом.
Множества Жюлиа
Будем рассматривать последовательности комплексных чисел {Zn}. Возьмем произвольное комплексное число c. Теперь для любого комплексного числа k рассмотрим последовательность {Zn(k)}:
Z0 = k,
Zi+1= Zi2 + c
Зададим себе вопрос: сходится ли Zn к нулю или стремится к бесконечности при n стремящемся к бесконечности? Пусть J – множество всех комплексных чисел {k}, таких что {Zn(k)}стремится к 0, при n стремящемся к бесконечности. Если теперь мы возьмем все такие k и отобразим их на комплексной плоскости, то получим множество Жюлиа. Меняя c, мы получим бесконечный набор фантастических само подобных образов – множеств Жюлиа.
Множество Мандельброта
Рассмотрим набор множеств Жюлиа и зададимся вопросом: связно ли данное конкретное множество Жюлиа? Пусть M – множество всех множеств Жюлиа, которые связны. Это множество и называется множеством Мандельброта.
Теперь возьмем любое множество Жюлиа J, и комплексное число c, которое его породило. Если J содержится в M, то изобразим точку черным на комплексной плоскости, в противном случае белым. Это и дает нам того “своеобразного снеговика“, которого вы уже наверное видели миллион раз. Его - то мы и будем генерировать.
К счастью, есть более легкий путь изображения множества Мандельброта, чем рисование каждого множества Жюлия и выяснения, связно ли оно. Наш метод будет очень близок к построению множеств Жюлиа. Опять рассмотрим итерационную последовательность для любого k, и выясним, сходится ли она к нулю.
Zi+1= Zi2 + c
Заметим, что c здесь уже не константа.Для любой точки комплексной плоскости мы c присваиваем значение kи выполняем итерации. Этот метод, как ни странно, дает нам то же изображение множества Мандельброта. Итак, алгоритм:
For each point k on the complex plane do:
let x=0.
repeat infinite times:
x = x2 + k.
end repeat
if x goes to infinity,
k is not in the set. Color is white.
else
k is in the set. Color is black.
Понятно, что бесконечных циклов быть не должно. Поэтому возьмем некоторое большое число I и проитерируем I раз. Чем большее I мы взяли, тем, разумеется, точнее ответ мы получим. Из практики, число 4000 дает довольно хороший результат. Да, но 4000 раз “крутить“ цикл для каждого пиксела изображения, это многовато. К счастью, мы можем воспользоваться результатами многолетней работы математиков в этой области. Оказывается, если в любой конкретный момент вычислений, для k расстояние от zi(k) до начала координат больше 2, то мы можем принять, что данная {Zn(k)} уйдет в бесконечность. (При сравнении: расстояние < 2, поэтому его квадрат меньше 4 и корень извлекать не нужно.) Итак, теперь наш алгоритм выглядит так:
For each point k in the complex plane do:
let x=0.
repeat 4000 times
let x=x2+k
if x2 > 4 then
Color it white
Break
end repeat
if we reached 4000 then
Color is black.
Этот метод дает нам черно-белое изображение множества Мандельброта. Теперь надо подумать о том, как сделать его разноцветным.
Цветное изображение
Если точка принадлежит множеству Мандельброта, то с ней все ясно – рисуем ее черным. Но как быть с точками, не принадлежащими множеству? Общепринятый способ выбора цвета для них – это выбирать цвет в соответствии с тем, как быстро {Zn(k)} стремится к бесконечности (на какой итерации мы ее исключаем из рассмотрения). Например, точка, для которой расстояние до начала координат больше 2 уже на третьей итерации, должна быть почти белой, а та точка, которая “продержалась“ до 3995 итерации – почти черной. Перепишем алгоритм для изображения в градациях серого:
For each point k in the complex plane do:
let x:=0.
for i:=0 to 4000
let x=x2+k
if ( |x|2> 4) then
Color point k color i
Break;
end if
end for
if (i=4000)
Color of point k is black.
end if
Конечно, просто рисовать точку цветом i мы не можем. Считая, что у нас есть только 256 градаций серого, а i меняется до 4000.
Построение множества Мандельброта
Рассмотрим последовательность комплексных чисел zn и возьмем произвольное комлексное число c. теперь для каждого комлексного k рассмотрим последовательность вида z0=k, zn=zn-1*zn-1+c. Множество {k} таких, что данная последовательность стремится к нулю, называется множеством Жюлиа. Объединение всех связных множеств Жюлиа есть множество Мандельброта. Фракталы можно получить, строя множество Мандельброта и выбирая соответствующий способ раскраски. Вот один из примеров.
Метод Ньютона
Другой пример. Он основан на решении уравнений методом Ньютона. Решение уравнения f(z) = 0 имеет вид zk+1 = N(zk), где N(z) = z - f(z)/f'(z). Рассмотрим уравнение pow (z, 3)-1 = 0. Вот как будет выглядеть построение фракталов, используя метод Ньютона для решения уравнения
maxIterations = 64;
count = 0;
z = current;//комплексные переменные
delta = z;
z1 = z;
while (count < maxIterations && abs(z) < 1e6
&& abs (delta) > 1e-6)
{
z = z - (z*z*z-1)/(3*z*z);
delta = z1-z;
z1 = z;
}
SetColor (ColorPalette[count*256/maxIterations]); палитру можно сформировать по-разному, на данной картинке - градиентный переход цветов.
Рассмотрим этот метод более подробно. Возьмем рабочую область экрана S (равномерная двумерная сетка) как некоторую область G в комплексной плоскости (неравномерная двумерная сетка), то есть каждой точке (x,y) области S сопоставим точку (a,b) области G, так что a=L1(x) и b=L2(y), где L1 и L2 - линейные преобразования. Найдем корни уравнения (1) в области G, т.е. в каждой точке G (a0,b0) исследуем на сходимость итерационную последовательность {zk} с начальным приближением z0=(a0,b0). Каждой точке (x0,y0) из S поставим в соответствие целое число C(x0,y0) из диапазона от 0 до 255 (или тройку чисел (r,g,b), где r,g и b - целые числа от 0 до 255), причем число C определяется в зависимости от того, сходится ли и как сходится итерационная последовательность {zk} с начальным приближением z=(a,b), где a=L1(x0), b=L2(y0). Таким образом, получаем функцию от двух переменных C(x,y), которую можно рассмаривать как монохромное или цветное изображение или изображение в градациях серого. Различные варианты фракталов получаются варьированием параметра P1. Вот описание этого алгоритма на псевдокоде для всех точек рабочей области (x,y): begin
a=L1(x);
b=L2(y);
z0={a,b}; //z0-комплексное число
z_prev=z0; //начальное приближение
пока число итераций < MaxNumberOfIterations
begin
n=f(z_prev);
d=f'(z_prev)+P1;
z=z_prev-n/d;
число итераций увеличить на 1;
end
if (|n|=0) SetPixel(x,y,0);
else if (|n|=MaxPossibleValue) SetPixel(x,y,255)
else // в зависимости от того, насколько далеко значение функции на элементе
// последовательности от 0 после MaxNumberOfIterations итераций,
// выбрать цвет в данной точке, например,
SetPixel( x, y, |n|/MaxNumberOfIterations*255);
// |n| - модуль комплексного числа, n=f(zk)
// MaxPossibleValue - максимально возможное значение f(z) на итерационной
// последовательности после MaxNumberOfIterations итераций
end
Величины MaxNumberOfIterations и MaxPossibleValue выбитаются опытным путем. Например, можно взять MaxNumberOfIterations равным 100. Дополнительно прадлагается задать способ расцветки получившегося изображения. Алгоритм можно оптимизировать путем аппроксимации функций. Меняя параметры, можно получить различные интересные эффекты. Причем, если параметры отличаются незначительно, то картинки получающиеся при этих параметрах, тоже будут отличаться несильно. Таким образом можно получить плавные переходы между разными изображениями, сохранить их и создать видеопоследовательность.
Более сложный пример задания последовательности комплексных чисел
Общая идея проста. Берется некая последовательность комлексных чисел zn = F(zn - 1), где F может быть суперпозицией различных функций. Рассматривается сходимость (расходимость) этой последовательности. Обычно достаточно рассмотреть около 30 итераций. Далее в зависимости от скорости сходимости выбирается цвет в точке. Рассмотрим пример с розой - расчет цвета в одной точке. Диапазон изменения комлексного числа current (1.41243196908302890000, 0.43820235769674321000) до (1.41299091299888270000, 0.43876197245340087000) Разность действительных частей соответствует ширине изображения, разность мнимых - высоте.
tolerance = 1e-6;
z = current;
zold = [0, 0];//комлексное число, Re(zold)=Im(zold)=0
xmax = xmin = xtot = 0;//вещественные числа
ymin = ymax = ytot = 0;
mmin = mmax = mtot = 0;
stop = 0;
//собственно вычисления
z += log (z);//комплексные функции
while (stop == 0 && count<30)//30 итераций достаточно
{
if (abs (Re(z)-Re(zold))<= tolerance
&& abs (Im(z)-Im(zold))<= tolerance)
//критерий остановки
stop = 1;
else
{
sc = sec (z)*csc (z);//где sec(z)=1./cos(z), csc(z)=1./sin(z)
f_z = log (sc);
fp_z = 1/sc * (sc*tan(z)-sec(z)*pow(csc(z),2));
zold = z;
z = z - fp_z/f_z;//так определяется последовательность zn
value = csc(z);
//все что далее нужно для определения цвета
x = Re (value);
y = Im (value);
m = abs(value);//модуль комл. числа - sqrt (x*x + y*y)
xtot += x;
ytot += y;
mtot += m;
xmin = min (xmin, x);
xmax = max (xmax, x);
ymin = min (ymin, y);
ymax = max (ymax, y);
mmin = min (mmin, m);
mmax = max (mmax, m);
count++;
}
}
//теперь собственно определение цвета - немного изменив эту часть, получаем совсем др вид
r = g = b = 0;
if (count > 0)
{
r = ((xtot/count)-xmin)/(xmax-xmin);
g = ((ytot/count)-ymin)/(ymax-ymin);
b = ((mtot/count)-mmin)/(mmax-mmin);
//параметры для расчета цвета, можно менять по-разному, но так
// чтобы 0 < xStart < 255 и 0 < xStep < 2
rStart = 255;
gStart = 205;
bStart = 255;
rStep = 1.5;
gStep = 1.5;
bStep = 1.0;
//собственно расчет цвета, здесь цвета как бы "идут по кругу"
r = -cos (2*PI*r);
g = -cos (2*PI*g);
b = -cos (2*PI*b);
r = r*127+127;
g = g*127+127;
b = b*127+127;
r = r*rStep+rStart;
g = g*gStep+gStart;
b = b*bStep+bStart;
r /= 360.0;
g /= 360.0;
b /= 360.0;
r = sin (PI*r);
g = sin (PI*g);
b = sin (PI*b);
r = r*128+127;
g = g*128+127;
b = b*128+127;
}
SetColor (b, g, r);
Метод Тейлора
Вот еще один достаточно простой метод. Рассмотрим разложение exp(z) в ряд Тейлора. Z - комлексное число. Фактически раскраска определяется тем, насколько быстро сумма многочленов, взятых с некоторым коэффициентом (в его выборе можно поэксперементировать), приближается к значению экспоненты. Вот пример, как это может выглядеть Расчет цвета в данной точке
maxIterations = 15;
tolerance = 1e-6;
z = exp (current);//current - точка на комлексной плоскости,
//соответствующая данной точке получаемого изображения
xmax = xdev = xavg = 0;
ymax = ydev = yavg = 0;
mmax = mdev = mavg = 0;
zSum = 0;
double denominator = 1;//вещественная переменная
point = exp (current);//это и будет весовой коэффициент
//совсем необязательно брать здесь экспоненту,
// выглядет это может и так point[5, 5]; point = sin (point)
// и т.д.
//цикл, не более maxIterations, пока zSum не подойдет "достаточно близко" к z
while (count < maxIterations && norm (zSum-z) > tolerance)
{
zSum += exp (point)*((current-point)^count)/denominator;
if (count > 0)
denominator *= (count+1);
//теперь собственно определение цвета
value = cot (zSum);
x = abs (value^0.1);
y = abs (value^0.2);
m = abs (value^0.4);
xavg = (x+xavg*count)/(count+1);
yavg = (y+yavg*count)/(count+1);
mavg = (m+mavg*count)/(count+1);
xdev = sqrt ( (x-xavg)*(x-xavg) );
ydev = sqrt ( (y-yavg)*(y-yavg) );
mdev = sqrt ( (m-mavg)*(m-mavg) );
xmax = max (x, xdev);
ymax = max (y, ydev);
mmax = max (m, mdev);
xtot += xdev;
ytot += ydev;
mtot += mdev;
}
r = g = b = 0;
if (count > 0)
{
r = (xtot/count)/ xmax;
g = (ytot/count)/ ymax;
b = (mtot/count)/ mmax;
r = InterpolateColor (1, 255, r);
g = InterpolateColor (1, 255, g);
b = InterpolateColor (1, 255, b);
}
SetColor (r, g, b);
Бесконечно детализированная природа фракталов
1.Когда вы увеличиваете некоторое компьютерное изображение, точки на экране раздвигаются, представляя более крупный, но не более детализированный рисунок. Фрактальное изображение, однако, расширяется и открывает глазу новые детали. На этой цветной картинке множества Мандельброта изображены точки - элементы этого множества: точки, чьи орбиты остаются внутри цилиндра - изображены черными, а точки с убегающими орбитами - другими различными цветами. Каждый пиксел изображения представляет собой одну точку фрактала.
2. Увеличение области, выделенной прямоугольником на предыдущем изображении, предоставляет более подробную информацию о структуре фрактала. Каждый пиксел по-прежнему представляет одну точку на фрактале, но поскольку экран теперь покрывается меньшей областью, теоретические точки расположены ближе друг к другу. Заметьте сходство между бухтами побережья фрактала и большим озеро-подобным рисунком множества Мандельброта. Этот феномен, известный как самоподобие - свойство многих фракталов.
3. Повторное увеличение принесет новые детали. Не важно, как сильно вы увеличиваете изображение, вы никогда не исчерпаете множество Мандельброта. Новые детали будут появляться до бесконечности.
4. Цвета, используемые для выделения различных орбит, выбираются по усмотрению наблюдателя. Часто изменение цветовой гаммы позволяет подругому посмотреть на объект. Здесь изображен другой вид предыдущего изображения, где цвета изменены так, чтобы подчеркнутькристаллоподобную структуру этой области фрактала.
Как строятся IFS-фракталы
1. Прекрасный пример СИФ-фрактала - это сгенерированный компьютером лист папортника. Решающий элемент в построении папортника – так называемый "черный ящик", содержащий набор из четырех уравнений, известных как афинные пpеобразования. Вначале экран очищен и x-y координаты начальной точки помещены в черный ящик. Одно из уравнений выбирается случайным образом (случайный выбор определяется набором вероятностей, которые описывают в среднем частоту использования каждого уравнения), и по этому уравнению находится новая пара координат. Потом высвечивается точка экрана с этими координатами.
2. Пара точек, сгенерированная на предыдущем шаге, снова заносится в черный ящик и опять по случайным образом выбранному уравнению получают новую пару, и соответствующая точка рисуется на экране. Этот процесс повторяется тысячи раз. Постепенно из случайным образом разбросанных точек на экране складывается изображение.
3. Пока продолжается итерационный процесс генерации координат, точки на экране медленно, но верно принимают форму листа папортника. Меняющаяся яркость отдельных точек указывает на то, что мы "попали" в них более чем один раз. Чем чаще координаты данной точки извлекаются из черного ящика, тем ярче раскрашен на экране этот пиксел.
4. Результирующeе изображение - удивительно точная копия настоящего папортника. Заметьте явное самоподобие в структуре папортника: каждый листочек - уменьшенное изображение самого папортника. По этому же принципу работает фрактальное сжатие. Программа сжатия ищет самоподобие в изображении и подбирает набор уравнений - такой, который в процессе итерации воспроизведет картину, очень близкую к оригиналу. Распаковка тогда очень проста - достаточно задать начальное значение и запустить итерационный процесс до тех пор, пока не получим нужного качества изображения.
Фракталы