Применение фракталов в машинной графике

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание

Введение

История фракталов

Применения фракталов в жизни

Системы итерируемых функций (IFS) и их применение

Пример систем итерируемых функций

Генерация фракталов. Фрактальное сжатие изображений

Заключение

Список использованной литературы

Введение

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

До недавнего времени геометрические модели различных природных конструкций традиционно строились на основе сравнительно простых геометрических фигур: прямых, многоугольников, окружностей, многогранников, сфер. Однако очевидно, что этот классический набор, вполне достаточный для описания элементарных структур, становится плохо применимым для характеристики таких сложных объектов, как очертание береговых линий материков, поле ско­ростей в турбулентном потоке жидкости, разряд молнии в воздухе, пористые материалы, форма облаков, снежинки, пламя костра, контуры дерева, кровеносно-сосудистая система человека, поверхность клеточной мембраны и др. В последние 15-20 лет для описания этих и им подобных образований ученые все чаще используют новые геометрические понятия. Одним из таких понятий, изменившим многие традиционные представления о геометрии, явилось понятие фрактала. Оно было введено в обращение замечательным французским математиком польского происхождения Бенуа Мандельбротом в 1975 году. И хотя в математике похожие конструкции в той или иной форме появились уже много десятков лет назад, в физике ценность подобных идей была осознана лишь в 70-е годы нашего столетия.

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

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

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

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

История фракталов

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

Большой вклад в будущую фрактальную геометрию внесли также знаменитые работы французских математиков Г. Жулиа и П. Фату, которые в начале 20 века занимались теорией рациональных отображений в комплексной плоскости. Практически полностью забытая, их деятельность получила неожиданное развитие в начале восьмидесятых годов, когда с помощью компьютеров математикам удалось получить прекрасные картины, показывающие примеры таких отображений. Это уже была эра фрактальной геометрии, поскольку незадолго до этого, в середине 70-х годов, в науке появился совершенно новый термин "фрактал", характеризующий нерегулярный, но самоподобный объект, который удобно было характеризовать нецелочисленной размерностью.

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

В результате усилий Бенуа Мандельброта такое отношение изменилось, и фрактальная геометрия стала уважаемой прикладной наукой. Мандельброт ввел в употребление термин фрактал, основываясь на теории фрактальной (дробной) размерности Хаусдорфа, предложенной в 1919 году. За много лет до появления его первой книги по фрактальной геометрии, Мандельброт приступил к исследованию появления монстров и других патологий в природе. Он отыскал нишу для имевших дурную репутацию множеств Кантора, кривых Пеано, функций Вейерштрасса и их многочисленных разновидностей, которые считались нонсенсом. Он и его ученики открыли много новых фракталов, например, фрактальное броуновское движение для моделирования лесного и горного ландшафтов, флуктуации уровня рек и биения сердца.

Траектории частиц броуновского движения, которым занимались Роберт Броун еще в 1828 году и Альберт Эйнштейн в 1905 году, представляют собой пример фрактальных кривых, хотя их математическое описание было дано только в 1923 году Норбертом Винером.

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

Применения фракталов в жизни

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

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

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

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

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

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

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

Аффинное преобразование - композиция линейного преобразования и параллельного переноса. В двумерном пространстве для полного представления аффинного преобразования достаточно задать 6 коэффициентов.

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

На основании этих идей Барнсли и Слоан создали алгоритм, который, по их утверждению, позволит сжимать информацию в 500-1000 раз. Вкратце метод можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), т.е. коэффициентами этих преобразований (в нашем случае 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). Выделим в этих структурах подобные части и, для каждой из них вычислим коэффициенты аффинного преобразования. В аффинный коллаж будет включено столько аффинных преобразований, сколько существует частей подобных целому изображению.

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

Построим IFS для "дракона" Хартера-Хейтуэя. Для этого расположим первое поколение этого фрактала на сетке координат дисплея 640 x 350 (Рис.7). Обозначим точки получившейся ломаной 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, после десятой итерации на экране получим фрактальную структуру, изображенную на рис.8, которая представляет собой "дракон" Хартера-Хейтуэя. Его кодом (сжатым описанием) является набор коэффициентов двух аффинных преобразований.

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

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

Рис 3. Заготовка для построения 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 + 130Y' = -0.289*X + 0.167*Y + 256

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

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

фрактал изображение образ

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

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

Пример систем итерируемых функций

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

Каждая строчка этой таблицы соответствует одному аффинному преобразованию с коэффициентами а, b, с, d, е, f в соответствии с выражением

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

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

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

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

Рис. 11. Увеличенный фрагмент листа папоротника

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

Генерация фракталов

Для генерации фрактальных рисунков можно написать алгоритм программы в Паскале, Бейсике или в других языках программирования. Есть множество литературы в которой подробно рассмотрено написание алгоритма программы для генерации фракталов, например, Р. М. Кроновер «Фракталы и хаос в динамических системах. Основы теории», в содержании рассмотрено теория о фракталах а так же примеры с написанием программ для генерации фракталов. Но на сегодняшний день существует большое количество уже написанных программ генерации фрактальных рисунков. Рассмотрим одну из них- Fractal Explorer версии 2.02.

При запуске Fractal Explorer появляется пустое окошко, сверху находится панель инструментов.

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

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

Заключение

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

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

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

Список использованной литературы

1. Джураев Р.Х Помехоустойчивые коды в телекоммуникационных системах. Учебное пособие - ТУИТ, Ташкент 2013.

2. Бондаренко В.А., Дольников В.Л. Фрактальное сжатие изображений по Барнсли-Слоану.

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

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

5. http://levinaleks.narod.ru/fractals2.htm

Размещено на Allbest.ru