к компьютерному моделированию   к компьютерной графике   к визуальному программированию

Введение во фракталы

  1. Понятие "фрактал"
  2. Классификация фракталов
  3. Системы итерируемых функций
  4. Генераторы фракталов
  5. Графические движки
  6. Физические движки
  7. Библиографический список
  8. Примеры изображений фракталов

1. Понятие "фрактал"

Понятия фрактал и фрактальная геометрия, появившиеся в конце 70-х, с середины 80-х прочно вошли в обиход математиков и программистов. Слово фрактал образовано от латинского fractus и в переводе означает состоящий из фрагментов. Оно было предложено Бенуа Мандельбротом в 1975 году для обозначения нерегулярных, но самоподобных структур, которыми он занимался. Рождение фрактальной геометрии принято связывать с выходом в 1977 году книги Мандельброта `The Fractal Geometry of Nature'. В его работах использованы научные результаты других ученых, работавших в период 1875-1925 годов в той же области (Пуанкаре, Фату, Жюлиа, Кантор, Хаусдорф). Но только в наше время удалось объединить их работы в единую систему.

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

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

Определение фрактала, данное Мандельбротом, звучит так: "Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому" [3].

2. Классификация фракталов

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

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

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


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

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


Рис 2. Построение "дракона" Хартера-Хейтуэя.

Для получения другого фрактального объекта нужно изменить правила построения. Пусть образующим элементом будут два равных отрезка, соединенных под прямым углом. В нулевом поколении заменим единичный отрезок на этот образующий элемент так, чтобы угол был сверху. Можно сказать, что при такой замене происходит смещение середины звена. При построении следующих поколений выполняется правило: самое первое слева звено заменяется на образующий элемент так, чтобы середина звена смещалась влево от направления движения, а при замене следующих звеньев, направления смещения середин отрезков должны чередоваться. На рис.2 представлены несколько первых поколений и 11-е поколение кривой, построенной по вышеописанному принципу. Предельная фрактальная кривая (при n стремящемся к бесконечности) называется драконом Хартера-Хейтуэя [3].

В машинной графике использование геометрических фракталов необходимо при получении изображений деревьев, кустов, береговой линии. Двухмерные геометрические фракталы используются для создания объемных текстур (рисунка на поверхности обьекта) [2,3].

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

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

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


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

В качестве примера рассмотрим множество Мандельброта (см. pис.3 и рис.4). Алгоритм его построения достаточно прост и основан на простом итеративном выражении:

Z[i+1] = Z[i] * Z[i] + C, 

где Zi и C - комплексные переменные. Итерации выполняются для каждой стартовой точки C прямоугольной или квадратной области - подмножестве комплексной плоскости. Итерационный процесс продолжается до тех пор, пока Z[i] не выйдет за пределы окружности радиуса 2, центр которой лежит в точке (0,0), (это означает, что аттрактор динамической системы находится в бесконечности), или после достаточно большого числа итераций (например 200-500) Z[i] сойдется к какой-нибудь точке окружности. В зависимости от количества итераций, в течении которых Z[i] оставалась внутри окружности, можно установить цвет точки C (если Z[i] остается внутри окружности в течение достаточно большого количества итераций, итерационный процесс прекращается и эта точка растра окрашивается в черный цвет).


Рис 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. По правилам построения у этого фрактала две части, подобные целому - на рис.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 для кривой Кох. Нетрудно видеть, что эта кривая имеет четыре части, подобные целой кривой. Для нахождения 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.

Примеры изображений фракталов

Знаете ли Вы, в чем ложность понятия "физический вакуум"?

Физический вакуум - понятие релятивистской квантовой физики, под ним там понимают низшее (основное) энергетическое состояние квантованного поля, обладающее нулевыми импульсом, моментом импульса и другими квантовыми числами. Физическим вакуумом релятивистские теоретики называют полностью лишённое вещества пространство, заполненное неизмеряемым, а значит, лишь воображаемым полем. Такое состояние по мнению релятивистов не является абсолютной пустотой, но пространством, заполненным некими фантомными (виртуальными) частицами. Релятивистская квантовая теория поля утверждает, что, в согласии с принципом неопределённости Гейзенберга, в физическом вакууме постоянно рождаются и исчезают виртуальные, то есть кажущиеся (кому кажущиеся?), частицы: происходят так называемые нулевые колебания полей. Виртуальные частицы физического вакуума, а следовательно, он сам, по определению не имеют системы отсчета, так как в противном случае нарушался бы принцип относительности Эйнштейна, на котором основывается теория относительности (то есть стала бы возможной абсолютная система измерения с отсчетом от частиц физического вакуума, что в свою очередь однозначно опровергло бы принцип относительности, на котором постороена СТО). Таким образом, физический вакуум и его частицы не есть элементы физического мира, но лишь элементы теории относительности, которые существуют не в реальном мире, но лишь в релятивистских формулах, нарушая при этом принцип причинности (возникают и исчезают беспричинно), принцип объективности (виртуальные частицы можно считать в зависимсоти от желания теоретика либо существующими, либо не существующими), принцип фактической измеримости (не наблюдаемы, не имеют своей ИСО).

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

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

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

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

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 24.05.2017 - 20:22: СОВЕСТЬ - Conscience -> ПРОБЛЕМА КРИМИНАЛИЗАЦИИ ЭКОНОМИКИ - Карим_Хайдаров.
24.05.2017 - 19:39: СОВЕСТЬ - Conscience -> Просвещение от О.Н. Четвериковой - Карим_Хайдаров.
24.05.2017 - 16:55: СОВЕСТЬ - Conscience -> Декларация Академической Свободы - Карим_Хайдаров.
24.05.2017 - 14:52: СОВЕСТЬ - Conscience -> КОЛЛАПС МИРОВОЙ ФИНАНСОВОЙ СИСТЕМЫ - Карим_Хайдаров.
24.05.2017 - 06:20: Беседка - Chatter -> ЭПИСТОЛЯРНАЯ ФИЗИКА - Карим_Хайдаров.
24.05.2017 - 06:19: ЦИТАТЫ ЧУЖИХ ФОРУМОВ - Outside Quotings -> Гипотеза о причине смещения линии апсид эллиптических орбит - Карим_Хайдаров.
23.05.2017 - 16:17: СОВЕСТЬ - Conscience -> Проблема народного образования - Карим_Хайдаров.
23.05.2017 - 13:07: СОВЕСТЬ - Conscience -> Просвещение от Сергея Салля - Карим_Хайдаров.
15.05.2017 - 05:53: ЦИТАТЫ ЧУЖИХ ФОРУМОВ - Outside Quotings -> Украинский сайт ЭкоТехника - Карим_Хайдаров.
13.05.2017 - 07:01: ЭКСПЕРИМЕНТАЛЬНАЯ ФИЗИКА - Experimental Physics -> Опыты Майкельсона-Морли,Маринова и увлечение эфира - Сергей_Юдин.
11.05.2017 - 16:32: ЭКОЛОГИЯ - Ecology -> Биологическая безопасность населения - Карим_Хайдаров.
11.05.2017 - 11:36: СОВЕСТЬ - Conscience -> Просвещение от Ю.Ю. Болдырева - Карим_Хайдаров.
Bourabai Research Institution home page

Bourabai Research - Технологии XXI века Bourabai Research Institution