Фрактальная графика

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

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

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

Фрактальная графика

Рассматривается фрактальная геометрия как новое направление в исследовании поведения сложных систем. Дано определение фрактальной геометрии и графики, приведены примеры наиболее известных фракталов, описаны основные практические приложения фракталов.

Что такое фрактал?

Геометрия, которую мы изучали в школе и которой пользуемся в повседневной жизни, восходит к Эвклиду (примерно 300 лет до нашей эры). Треугольники, квадраты, круги, параллелограммы, параллелепипеды, пирамиды, шары, призмы - типичные объекты, рассматриваемые классической геометрией. Предметы, созданные руками человека, обычно включают эти фигуры или их фрагменты. Однако в природе они встречаются не так уж часто. Действительно, похожи ли, например, лесные красавицы ели на какой-либо из перечисленных предметов или их комбинацию? Легко заметить, что в отличие от форм Эвклида природные объекты не обладают гладкостью, их края изломаны, зазубрены, поверхности шероховаты, изъедены трещинами, ходами и отверстиями. Почему геометрию часто называют холодной и сухой? Одна из причин заключается в ее неспособности описать форму облака, горы, дерева или берега моря. Облака - это не сферы, горы - не конусы, линии берега - это не окружности, и кора не является гладкой, и молния не распространяется по прямой. «Природа демонстрирует нам не просто более высокую степень, а совсем другой уровень сложности», - этими словами начинается «Фрактальная геометрия природы» («The Fractal Geometry of Nature»), написанная Бенуа Мандельбротом. Именно он в 1975 году впервые ввел понятие фрактала - от латинского слова fractus «сломанный камень», «состоящий из фрагментов», «расколотый и нерегулярный». Оказывается, почти все природные образования имеют фрактальную структуру. Что это значит? Если посмотреть на фрактальный объект в целом, затем на его часть в увеличенном масштабе, потом на часть этой части и т. п., то нетрудно увидеть, что они выглядят одинаково. Фракталы самоподобны - их форма воспроизводится на различных масштабах.

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

Фракталы и размерность

В своей повседневной жизни мы постоянно встречаемся с размерностями. Мы прикидываем длину дороги (250 м), узнаем площадь квартиры (78 м²) и высчитываем объем емкости (0.33 дм³). Это понятие вполне интуитивно ясно и, казалось бы, не требует разъяснения.

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

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

Если смотреть с математической точки зрения, то размерность определяется следующим образом: для одномерных объектов - увеличение в два раза их линейного размера приводит к увеличению размеров (в данном случае длины) в два раза (2¹).

Для двумерных объектов увеличение в два раза линейных размеров приводит к увеличению размера (например, площади прямоугольника) в четыре раза (2²).

Для трехмерных объектов увеличение линейных размеров в два раза приводит к увеличению объема в восемь раз (2³) и так далее.

Таким образом, размерность D можно рассчитать исходя из зависимости увеличения «размера» объекта S от увеличения линейных размеров L. D=log(S)/log(L):

Для линии D=log(2)/log(2)=1.

Для плоскости D=log(4)/log(2)=2.

Для объема D=log(8)/log(2)=3.

Может быть, немного запутано, но в общем-то несложно и понятно.

Очертания гор, границы материков, русла горных рек, береговая линия и многое другое - все это фракталы. Часто, говоря о них, имеют в виду фрактальную кривую, обладающую нецелой (дробной) размерностью (1<D<2). Таким образом, фрактальная кривая - это геометрический объект, объединяющий в себе свойства линии и плоскости, в то же время не являющийся ни тем ни другим. Обратимся к классическому примеру, приведенному Мандельбротом и ставшему уже классическим. Рассмотрим береговую линию, которая представляет собой типичный фрактал. При попытке измерить её длину окончательный результат будет меняться в зависимости от масштаба единицы измерения. Полученная закономерность заключается в том, что измеренная длина береговой линии будет увеличиваться с уменьшением длины измерительного прибора. Зависимость увеличения измеренной длины контура от уменьшения длины измерительного прибора называется фрактальной размерностью. Береговая линия, в зависимости от её изрезанности, может иметь разное значение фрактальной размерности: при малой изрезанности размерность приблизится к 1, при большей к 2. Фрактальная кривая размерностью, близкой к 2, фактически заполняет пространство и становится полосой.

Примеры фракталов

Наиболее известными фрактальными объектами можно назвать:

1. Множество Мандельброта - это классический пример. Оно определяется следующим уравнением:Z_i+1 = Z_i*Z_i + C, где Z и C - комплексные числа.

2. Как бы линии, размерность которых больше единицы, но меньше двойки, - снежинка Коха и её родственники. Самый знаменитый родственник - множество Мандельброта.

3. Множества размерностью меньше единицы, но больше нуля - пыль Кантора и её родственники.

4. Множества точек на плоскости (как бы плоские фигуры), размерность которых меньше двух, - ковёр Серпинского и его родственники.

5. Множества точек в пространстве (как бы объёмные тела), размерность которых меньше трёх - губка Менгера и её родственники.

6. И, наконец, уж совсем чудо! Нашли кривую линию, размерность, которой равна в точности двойке! Знаменитая кривая Пеано. Это такая кривая, которая может заполнить весь квадрат полностью, т.е. она проходит через ВСЕ точки квадрата! Попробуем посчитать размерность для кривой Пеано. Итак, у нас исходная линия, состоящая из трех отрезков длины Х, заменяется на 9 отрезков втрое меньшей длины. Таким образом, при увеличении минимального отрезка в 3 раза длина всей линии увеличивается в 9 раз и D=log(9)/log(3)=2 - двумерный объект!!!

7. Потом нашли фракталы в природе, нашли физические явления, описываемые фрактальными кривыми. Например, оказалось, что траектория броуновской частицы - фрактал размерностью больше единицы.

Давайте посмотрим первый известный фрактал, созданный в 1870 году нарушителем спокойствия в математике Георгом Кантором (George Cantor).

Георг Кантор создал объект, чья размерность была больше 0, но меньше 1. То есть дырявый объект, который был больше точки (с 0 размерностью), но меньше линии (с 1 измерением). Его назвали пылью Кантора. Чтобы создать пыль Кантора, нарисуйте линию и вырежьте среднюю треть:

0_____________________________________1

0____________1/3 2/3____________1

Теперь вырежьте средние трети у каждой из двух оставшихся частей:

0____1/9 2/9____1/3 2/3____7/9 8/9____1

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

То, что останется в конце концов, и будет пылью Кантора.

На каждом шаге мы изменяли масштаб r = 3, потому что делили каждую остающуюся часть на 3 доли. (Каждая из этих долей имела 1/3 длины первоначальной части.) Затем мы отбрасывали среднюю часть. (Это похоже на то, как мы создавали отверстия.) Оставалось 2 части. На следующем шаге было 4 части, потом 8 и так далее. На каждом шаге число частей росло с коэффициентом N = 2. Таким образом, размерность для пыли Кантора:

D = log 2 / log 3 =0.6309.

На самом ли деле пыль Кантора - фрактал? Да, пока ее топологическая размерность отличается от 0.6309, что бесспорно. Но каков топологический размер пыли Кантора? Мы можем ответить на это, посмотрев, какую часть первоначальной линии (длиной 1) мы вырезали в процессе создания отверстий.

Первым шагом мы вырезаем среднюю треть, или длину 1/3. Следующим шагом мы вырезаем средние трети из двух оставшихся частей, или 2 длины (1/3) (1/3). И так далее. Вся вырезанная длина тогда:

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

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

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

1/3 + 2(1/9) + 4(1/27) + 8(1/81) + . . . = 1.

Мы вырезали всю длину линии (даже при том, что оставили бесконечное число точек) так, что оставшаяся пыль Кантора имеет нулевую длину. Ее топологическая размерность - ноль. Пыль Кантора - фрактал с фрактальной размерностью 0.6309 и топологической размерностью 0.

Типы фракталов

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

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

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

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

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

Это самая крупная группа фракталов. Свое название они получили за то, что их строят на основе алгебраических формул преобразования исходных данных по правилу, описываемому этими формулами, и каждый последующий шаг зависит от результатов выполнения предыдущего. Методов получения алгебраических фракталов несколько. Один из методов представляет собой многократный (итерационный) расчет функции Z_n+1=f(Z_n), где Z= X+Yi - комплексное число, а f - некая функция. Расчет данной функции продолжается в цикле до выполнения определенного условия. И когда это условие выполнится, на экран выводится точка c координатами X, Y. При этом значения функции для разных точек комплексной плоскости может иметь разное поведение:

1. С течением времени стремится к бесконеч-ности.

2. Стремится к 0.

3. Принимает несколько фиксированных значений и не выходит за их пределы.

4. Поведение хаотично, без каких-либо тенденций.

Множество Мандельброта - это классический пример алгебраического фрактала.

А вот еще один вариант алгебраического фрактала:

X_i+1=А₁*Х_i²+А₂*X_i+A₃*Y_i²+A₄*Y_i+A₅*X_i*Y_i+A₆;

Y_i+1=B₁*Х_i²+B₂*X_i+B₃*Y_i²+B₄*Y_i+B₅*X_i*Y_i+B₆.

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

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

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

Существует два наиболее распространенных способа генерирования фрактальных изображений, применяемых на сегодняшний день. Это - системы IFS (iterated function systems) - в данном случае изображение генерируется с использованием набора аффинных преобразований, приводящих к масштабированию (уменьшению) исходного изображения, и L-системы - они строят изображения путем проведения преобразований над геометрическими примитивами по определенным правилам. С точки зрения математики интереснее оказывается построение с применением IFS. В качестве примера приведу построение описанной выше снежинки Коха этим методом.

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

2. Для очередного отрезка, образующего кривую Коха, на данном шаге N раз выполняем следующую последовательность действий:

- производим масштабирование отрезка, т.е. уменьшаем его в три раза, получаем первое звено;

- для построения следующего звена снова уменьшаем длину исходного отрезка в три раза, производим поворот на 600, затем - параллельный перенос вдоль направления первого звена на длину 1/3 длины исходного отрезка;

- третье звено: уменьшаем первоначальный отрезок в три раза, поворачиваем его на 600, передвигаем на 1/2 длины первоначального отрезка параллельно ему;

- уменьшаем исходный отрезок в три раза, параллельный перенос на 2/3 длины первоначального отрезка;

- возвращаемся к пункту 2, если число оборотов вокруг оси меньше N.

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

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

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

В качестве примера можно рассмотреть определение фрактального множества через понятие самоподобия. Как известно, это понятие неприменимо для описания многих фрактальных множеств - например, для множеств Жюлиа и Мандельброта - их фрагменты, строго говоря, не переводятся во все множество с помощью преобразования подобия. Чтобы выйти из этого положения, Мандельброт говорит о том, что можно расширить описания фракталов через преобразования фрагмента фрактального множества во всё множество, используя и подыскивая не только преобразования подобия, но и другие виды геометрических преобразований (например, аффинные). Действительно, видно, что фрактал - фигура Коха и фрактал - множество Мандельброта - это разные типы фракталов. У них есть общее - наличие рекурсивной процедуры их генерации, но есть и отличия. В первом случае мы имеем дело с инвариантным относительно масштабных преобразований фракталом, во втором можно говорить о ковариантности - о нарушениях инвариантности при масштабных преобразованиях. Поэтому можно говорить о том, что фигура Коха - это инвариантный фрактал, а множество Мандельброта - это ковариантный (или - если взять на вооружение термин Тимофеева-Ресовского - ковариантно редуплицированный) фрактал.

Исходя из этого, можно ввести представление о двух пониманиях самоподобия - жесткого самоподобия - самоподобия типа самоподобия фигур Коха, связанного инвариантностью относительно масштабных преобразований и, и нежесткого самоподобия - ковариантного самоподобия типа самоподобия множества Мандельброта, когда преобразование фрагмента во все множества нетривиально.

Жесткое и нежесткое самоподобие есть фундаментальные предикаты описания категории фрактала. Именно на поиске и интерпретации самоподобий основаны поиск и интерпретация фрактальных структур в конструктах прикладных теорий.

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

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

Физическая интерпретация фракталов

Чтобы понять алгебраический фрактал, начнем с простого опыта. Шарик, подвешенный на нитке, отклоняют от вертикали и отпускают. Возникают колебания. Если шарик отклонили немного, то его движение описывается линейными уравнениями. Если отклонение сделать достаточно большим, уравнения будут уже нелинейными. Что при этом изменится? В первом случае частота колебаний (и, соответственно, период) не зависит от степени начального отклонения. Во втором - такая зависимость имеет место. Полный аналог механического маятника как колебательной системы - колебательный контур, или «электрический маятник». В простейшем случае он состоит из катушки индуктивности, конденсатора (емкости) и резистора (сопротивления). Если все три указанных элемента линейны, то колебания в контуре эквивалентны колебаниям линейного маятника. Но если, к примеру, емкость нелинейна, период колебаний будет зависеть от их амплитуды.

Динамика колебательного контура определяется двумя переменными, например током в контуре и напряжением на емкости. Если откладывать эти величины вдоль осей Х и Y, то каждому состоянию системы будет соответствовать определенная точка на полученной координатной плоскости. Такую плоскость называют фазовой. (Соответственно, если динамическая система определяется n переменными, то вместо двумерной фазовой плоскости ей можно поставить в соответствие n-мерное фазовое пространство).

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

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

Роль фракталов в современном мире

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

Если задуматься, то легко увидеть, что в обществе, как и в природе, многие системы построены по принципу фракталов: из малых элементов образуются некоторые комплексы, они в свою очередь служат элементами для более крупных комплексов и т. д. Как, например, организованы жизнеспособные экономические и производственные структуры? Две крайние позиции: крупные транснациональные компании и «мелкий бизнес». Каждая из них в отдельности нежизнеспособна. Большие компании, обладая огромной экономической мощью, малоподвижны и не могут быстро реагировать на изменения в окружающей экономической среде. «Малый бизнес» не способен решать крупные задачи, обеспечивать развитие инфраструктуры. Где же золотая середина? В средних по размеру предприятиях? Отнюдь. Устойчивая экономическая инфраструктура обеспечивается (при необходимой подкачке нужных ресурсов) совокупностью разномасштабных (вот он фрактал!) эко-номических объектов, образующих пирамиду. У основания ее находится множество мелких компаний и фирм, выше по пирамиде размер предприятий постепенно увеличивается, а их число, соответственно, сокращается, и, наконец, наверху находятся самые крупные компании. При этом мелкие предприятия наиболее мобильны: они часто рождаются и умирают, являясь основными поставщиками новых идей и технологий.

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

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

Как считают многие исследователи, именно комбинация этих двух свойств служит причиной того, что хаотическая динамика характерна для поведения многих систем живых организмов. Например, хаотический характер ритма сердца позволяет ему гибко реагировать на изменение физических и эмоциональных нагрузок, подстраиваясь под них. Известно, что регуляризация сердечного ритма приводит через некоторое время к летальному исходу. Одна из причин заключается в том, что сердцу может не хватить «механической прочности» для того, чтобы скомпенсировать внешние возмущения. На самом деле ситуация более сложная. Упорядочение работы сердца служит индикатором снижения хаотичности и в других, связанных с ним, системах. Регулярность свидетельствует об уменьшении сопротивляемости организма случайным воздействиям внешней среды, когда он уже не способен адекватно отследить изменения и достаточно гибко на них отреагировать.

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

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

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

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

Фракталы и сжатие информации

Другое практическое применение фракталов - это сжатие информации. Масштабирование - уникальная особенность, присущая фрактальной компрессии. Со временем ее, видимо, будут активно использовать как в специальных алгоритмах масштабирования, так и во многих приложениях. Было бы неплохо, если бы изображение, показываемое в окне 100х100, хорошо смотрелось при увеличении на полный экран - 1024х768. Фрактальная архивация основана на том, что с помощью коэффициентов системы итерируемых функций изображение представляется в более компактной форме. Процесс архивации основан на принципах построения изображения с помощью IFS. Строго говоря, IFS - это набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (X - первая координата точки, Y - вторая координата точки, Z - ее яркость).

Наиболее наглядно этот процесс продемонстрировал Барнсли в своей книге «Фрактальное сжатие изображения». В ней введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка и системы линз, проецирующих изображение на другой экран. Каждая линза проецирует часть исходного изображения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. На линзы накладывается требование: они должны уменьшать в размерах проектируемую часть изображения. Кроме того, они могут менять яркость фрагмента и проецировать не круги, а области с произвольной границей. Один шаг Машины состоит в построении с помощью проецирования по исходному изображению нового. Утверждается, что на некотором шаге изображение перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз и не будет зависеть от исходной картинки. Это изображение называется неподвижной точкой или аттрактором данной IFS. Collage Theorem гарантирует наличие ровно одной неподвижной точки для каждой IFS. Поскольку отображение линз является сжимающим, каждая линза в явном виде задает самоподобные области в нашем изображении. Благодаря самоподобию мы получаем сложную структуру изображения при любом увеличении. Наиболее известные изображения, получаемые с помощью IFS: треугольник Серпинского и папоротник Барнсли. Первое задается тремя, а второе - пятью аффинными преобразованиями (или, в нашей терминологии, линзами). Каждое преобразование задается буквально считанными байтами, в то время как изображение, построенное с их помощью, может занимать и несколько мегабайт. В результате можно получить потрясающие коэффициенты сжатия. Например, рисунок папоротника кодируется с помощью 28!!! цифр и один и тот же рисунок получается вне зависимости от того, что взяли за основу - прямоугольник, круг, треугольник или что-либо еще.

Набор коэффициентов для построения листа папоротника:

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

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

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

Литература

1. Бондаренко В.А., Дольников В.Л. Фрактальное сжатие изображений по Барнсли-Слоану // Автоматика и телемеханика. - 1994. - №5. - С.12-20.

2. Витолин Д. Применение фракталов в машинной графике // Computerworld-Россия. - 1995. - №15. - С.11.

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

4. Шабаршин А.А., Введение во фракталы. Екатеринбург, 1998.

5. Пайтген Х.-Щ., Рихтер П.Х. Красота фракталов / Пер. с англ. - М.: Мир, 1993.

ПРИЛОЖЕНИЕ 1

{Простейший вариант программы построения алгебраического фрактала}

PROGRAM uzor;

USES GRAPH,DOS,CRT;

VAR GraphDriver : Integer; { для графического адаптера }

GraphMode : Integer; { для графического режима }

ErrorCode : Integer; { для кода ошибки }

I,X,X1,Y,a,b,c : INTEGER;

BEGIN

GraphDriver:= Detect; { режим автоопределения }

InitGraph(GraphDriver,GraphMode,''); { инициализация}

settextstyle(1,0,1) ;

repeat

gotoxy(1,1) ;

x:=100 ; y:=100 ; {1}

read(a); if a=0 then exit; read(b,c);{ввод коэффициентов, определяющих узор}

SETFILLSTYLE(1,0) ; BAR(0,0,640,480);

for i:=1 to 1000 do begin

x1:=x ; x:=trunc(y-sqrt(abs(b*x1-c)))-100; {2}

y:=a-x1;

setcolor(trunc(i/100)+4); {3}

outtextxy(x+300,y+100,'*'); {звездочка мо-жет быть заменена на любой другой символ}

end;

UNTIL KEYPRESSED;

END.

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