Фракталы
Из книги Джеф Проузиса " Как работает компьютерная графика"
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. Но если на обычной координатной
плоскости изображаются действительные числа, то комплексная плоскость содержит
комплексные числа - числа, с действительной и мнимой частью. Это полностью
'переворачивает' обычные правила математики и приводит к очень необычным
результатам.
Бесконечно детализированная природа фракталов 1.Когда вы увеличиваете некоторое компьютерное изображение, точки на
экране раздвигаются, представляя более крупный, но не более детализированный
рисунок. Фрактальное изображение, однако, расширяется и открывает глазу
новые детали. На этой цветной картинке множества Мандельброта изображены
точки - элементы этого множества: точки, чьи орбиты остаются внутри цилиндра
- изображены черными, а точки с убегающими орбитами - другими различными
цветами. Каждый пиксел изображения представляет собой одну точку фрактала.
Как строятся IFS-фракталы 1. Прекрасный пример СИФ-фрактала - это сгенерированный компьютером лист папортника. Решающий элемент в построении папортника – так называемый "черный ящик", содержащий набор из четырех уравнений, известных как афинные пpеобразования. Вначале экран очищен и x-y координаты начальной точки помещены в черный ящик. Одно из уравнений выбирается случайным образом (случайный выбор определяется набором вероятностей, которые описывают в среднем частоту использования каждого уравнения), и по этому уравнению находится новая пара координат. Потом высвечивается точка экрана с этими координатами. 2. Пара точек, сгенерированная на предыдущем шаге, снова заносится в черный ящик и опять по случайным образом выбранному уравнению получают новую пару, и соответствующая точка рисуется на экране. Этот процесс повторяется тысячи раз. Постепенно из случайным образом разбросанных точек на экране складывается изображение. 3. Пока продолжается итерационный процесс генерации координат, точки на экране медленно, но верно принимают форму листа папортника. Меняющаяся яркость отдельных точек указывает на то, что мы "попали" в них более чем один раз. Чем чаще координаты данной точки извлекаются из черного ящика, тем ярче раскрашен на экране этот пиксел. 4. Результирующeе изображение - удивительно точная копия настоящего папортника. Заметьте явное самоподобие в структуре папортника: каждый листочек - уменьшенное изображение самого папортника. По этому же принципу работает фрактальное сжатие. Программа сжатия ищет самоподобие в изображении и подбирает набор уравнений - такой, который в процессе итерации воспроизведет картину, очень близкую к оригиналу. Распаковка тогда очень проста - достаточно задать начальное значение и запустить итерационный процесс до тех пор, пока не получим нужного качества изображения. |
Главная страница | Темы лекций | Литература | Время лекций | Материалы лекций | Домашние задания | FAQ |
Hosted by Graphics & Media Lab
http://graphics.cs.msu.su |
mailto: Laboratory |