uzluga.ru
добавить свой файл
Элементы фрактального анализа

информационных потоков


Дмитрий Ландэ


Мрак первозданный. Тишина. Вдруг луч,

Пробившийся над рваным краем туч,

Ваяет из небытия слепого

Вершины, склоны, пропасти, хребты,

И твердость скал творя из пустоты,

И невесомость неба голубого.


Герман Гессе. «Игра в бисер»

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



Термин фрактал (от латинского слова fractus – дробный), был предложен Бенуа Мандельбротом в 1975 году для обозначения нерегулярных самоподобных математических структур. Популярная сегодня фрактальная геометрия получила свое название лишь в 1977 году благодаря его книге «The Fractal Geometry of Nature». В работах ученого использованы научные результаты многих ученых, работавших в этой же области (прежде всего, Пуанкаре, Кантора, Хаусдорфа). Основное определение фрактала, данное Мандельбротом, звучало так: "Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому".

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

Однако самоподобие – это хотя и необходимое, но далеко не достаточное свойство фракталов. Ведь нельзя же, в самом деле, считать фракталом точку, или плоскость, расчерченную клетками. Главная особенность фракталов заключается в том, что их размерность не укладывается в привычные геометрические представления. Фракталам характерна геометрическая «изрезанность». Поэтому используется специальное понятие фрактальной размерности, введенное Феликсом Хаусдорфом (1868-1942) и Абрамом Самойловичем Безиковичем (1891-1970). Применительно к идеальным объектам классической евклидовой геометрии она давала те же численные значения, что и известная задолго до нее так называемая топологическая размерность (иначе говоря, была равна нулю для точки, единице - для гладкой плавной линии, двум - для фигуры и поверхности, трем - для тела и пространства). Но совпадая со старой, топологической, размерностью на идеальных объектах, новая размерность обладала более тонкой чувствительностью ко всякого рода несовершенствам реальных объектов, позволяя различать и индивидуализировать то, что прежде было безлико и неразличимо. Так, отрезок прямой, отрезок синусоиды и самый причудливый меандр неразличимы с точки зрения топологической размерности - все они имеют топологическую размерность, равную единице, тогда как их размерность Хаусдорфа - Безиковича различна и позволяет числом измерять степень извилистости. Размерность фрактальных объектов не является целым числом, характерным для привычных геометрических. Вместе с тем, в большинстве случаев фракталы напоминают объекты, плотно занимающие реальное пространство, но не использующее его полностью.

Пусть есть множество G в пространстве Rn. Разобьем пространство Rn на n-мерные кубы с длиной ребра δ и обозначим число кубов, необходимых для покрытия ими множества G, через N(δ). Тогда величина размерности Хаусдорфа-Безиковича (называемой также фрактальной размерностью) D должна удовлетворять следующему условию:



Данное определение можно упростить, сделав его более удобным для практического применения. Видно, что при δ ≈ 0, оно эквивалентно:

D ≈ - ln N(δ) / ln δ.

2) Примеры абстрактных фракталов




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

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

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




Множество Мандельброта


Так как количество итераций соответствует номеру цвета, то точки, находящиеся ближе к множеству Мандельброта, имеют более яркий цвет.



Увеличенный участок границы множества Мандельброта


Построение другого фрактального множества, снежинки Коха, начинается с правильного треугольника, длина стороны которого равна 1. Сторона треугольника считается базовым звеном для исходного положения. Далее, на любом шаге итерации каждое звено заменяется на образующий элемент – ломанную, состоящую по краям из отрезков длиной 1/3 от длины звена, между которыми размещаются две стороны правильного треугольника со стороной в 1/3 длины звена. Все отрезки - стороны полученной кривой считаются базовыми звеньями для следующей итерации. Кривая, получаемая в результате n-й итерации при любом конечном n, называется предфракталом, и лишь при n, стремящемся к бесконечности, кривая Коха становится фракталом. Получаемое в результате итерационного процесса фрактальное множество представляет собой линию бесконечной длины, ограничивающую конечную площадь. Действительно, при каждом шаге число сторон результирующего многоугольника увеличивается в 4 раза, а длина каждой стороны уменьшается только в 3 раза, т.е. длина многоугольника на n-й итерации равна 3*(4/3)n и стремится к бесконечности с ростом n.














Первые 5 поколений снежинки Коха


Площадь под кривой, если принять площадь образующего треугольника за 1, равна:



В 80-х годах ХХ века как простое средство получения фрактальных структур появился метод "Систем Итерационных Функций" (Iterated Functions System - IFS). IFS представляет собой систему функций, отображающих одно многомерное множество на другое. Наиболее простая реализация IFS представляет собой аффинные преобразования плоскости:

X' = A*X + B*Y + C
Y' = D*X + E*Y + F


В 80-х годах американские ученые М. Барнсли и А. Слоан предложили идею сжатия и хранения графической информации, основанную на соображениях теории фракталов и динамических систем. На основании этой идеи был создан алгоритм фрактального сжатия информации, позволяющий сжимать некоторые образцы графической информации в 500-1000 раз. При этом каждое изображение кодируется несколькими простыми аффинными преобразованиями. Закодировав какое-то изображение двумя аффинными преобразованиями, оно однозначно определяется с помощью 12-ти коэффициентов. Если определить начальную точку итерационного процесса (например, X=0 Y=0) и запустить этот процесс, то через несколько итераций совокупность полученных точек будет описывать закодированное изображение.


В качестве примера использования IFS для построения фрактальных структур, можно привести кривую "дракона" Хартера-Хейтуэя.



"Дракон" Хартера-Хейтуэя


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

Фракталы с большой точностью описывают многие физические явления и природные образования: облака, турбулентные течения, ветви деревьев, кровеносные сосуды. Мандельброт в свое время заметил: "Почему геометрию часто называют холодной и сухой? Одна из причин заключается в ее неспособности описать форму облака, горы, дерева или берега моря. Облака - это не сферы, горы - не конусы, линии берега - это не окружности, и кора не является гладкой, и молния не распространяется по прямой. Природа демонстрирует нам не просто более высокую степень, а совсем другой уровень сложности."


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