Понятие фрактала было введено французским математиком Б. Мандельбротом в 1975 г. Фрактал — самоподобная структура, чье изображение не зависит от масштаба. Это рекурсивная модель, каждая часть которой повторяет в своем развитии развитие всей модели в целом. То есть в простом случае каждая небольшая часть фрактала содержит информацию о всем фрактале. На сегодняшний день существует много различных математических моделей фракталов. Отличительной особенностью каждой из них является то, что в их основе лежит какая-либо рекурсивная функция, например, xi = f(xi-1). Примеры различных фрактальных структур можно встретить в очень многих явлениях природы. Многие достижения в науке о фракталах стали возможны только с развитием вычислительной техники. На сегодняшний день фракталы и фрактальные методы применяются во многих областях информатики и на стыке с другими науками.
Применительно к компьютерной графике, фрактальная геометрия незаменима при генерации сложных неевклидовых объектов, образы которых весьма похожи на природные, а также для генерации природных объектов в 3-хмерной графике: ландшафтов, деревьев, облаков, снега, береговых рельефов, текстур и др.
Фракталы на основе системы итерированных функций (Iterated Functions System – IFS) очень успешно применяются при сжатии изображений и видео. Метод IFS применительно к построению фрактальных изображений, изобретённый М. Барнсли и его коллегами из Технологического института шт. Джорджия, базируется на самоподобии элементов изображения и заключается в моделировании рисунка несколькими меньшими фрагментами его самого. Специальные уравнения преобразований позволяют переносить, поворачивать и изменять масштаб участков изображения таким образом, что эти участки служат компоновочными блоками всего изображения. С помощью IFS-фракталов можно сжимать большие растровые изображения до долей их исходных размеров. Выдвинуто предположение, что природа при кодировании генетической структуры растений и деревьев пользуется чем-то близким к методу IFS-фракталов [1].
Более того, зарождается тенденция использования принципов фрактального сжатия изображений в базах данных изображений для генерации ключей изображений на основе их графической информации. Такой подход значительно улучшает поиск изображений, когда в качестве запроса подается изображение, для которого необходимо найти в заданной мере подобные [3].
Теория фракталов тесно связана с кластерным анализом, решающим задачу выделения компактных групп объектов с близкими свойствами. Кластеризация сегодня применяется при реферировании больших документальных массивов, определении взаимосвязанных групп документов, для упрощения процесса просмотра при поиске необходимой информации, нахождения уникальных документов из коллекции, выявления дубликатов или близких по содержанию документов.
В настоящее время интересное применение фракталам находят в применении к нейронным сетям. Фрактальная нейронная сеть состоит из иерархично связанных самоподобных структур нейронов. Преимуществом таких нейронных сетей является хорошее моделирование когнитивных процессов на различных уровнях, подобно тому, как это происходит в мозге человека.
В криптографии используют фрактальные хаотические системы, которые обладают таким свойством, что их поведение существенно зависит от заданных начальных условий. При этом состояние системы в определенный момент времени невозможно выразить простой формулой. Хаотическое поведение фракталов используется в криптографии для шифрования данных и генерации случайных последовательностей чисел. В фрактальной криптографии нет циклов, используются итерации. И безопасность основана на непредопределённости рекурсивной функции. Так, для вычисления n-той итерации функции, необходимо сначала вычислить (n-1)-вую итерацию и т.д. до самой первой. Как и в обычной криптографии, чем больше использовано итераций — тем лучше, т.к. проитерированная много раз точка фрактала далеко удаляется от начала и невозможно вычислить траекторию точки не выполнив каждый шаг рекурсии. Следовательно, стойкость шифрования получается значительно более высокой по сравнению с обычными методами [2].
Интересно отметить, что в финансах теория фракталов является подтверждением известной рыночной аксиомы — а именно, что движения акции или валюты внешне похожи, независимо от масштаба времени и цены. То есть финансовые диаграммы являются фрактальными кривыми, что позволяет успешно применять фрактальные методы к анализу финансовых рынков. Основой этого анализа является изучение во времени динамики такой характеристики, как фрактальная размерность, которая является показателем сложности кривой. Анализируя чередование участков с различной фрактальной размерностью и тем, как на систему воздействуют внешние и внутренние факторы, можно предсказывать поведение системы и ее нестабильные состояния (обвалы курсов валют, акций) [4].
Одним из способов построения фракталов является применение L-системы. Датский математик и биолог А. Линденмеер в 1968 году придумал грамматику, названную им L-системой, чтобы облегчить написание трансляторов, и которая, как он полагал, моделирует также рост живых организмов, в особенности образование кустов и веток у растений. Принцип L-системы заключается в следующем. Задают алфавит — произвольный набор символов. Выделяют одно, начальное слово, называемое аксиомой, — можно считать, что оно соответствует исходному состоянию «организма». Затем описывают правила замены каждого символа алфавита определенным набором символов. Действуют правила так: прочитывается по порядку каждый символ аксиомы и заменяется на слово, указанное в правиле замены (если для данного символа определено правило). Таким образом, мы получаем новую строку символов, к которой снова применяем ту же процедуру. Шаг за шагом, рекурсивно, возникает все более длинная строка — каждый из таких шагов можно считать одной из последовательных стадий развития «организма». Ограничив число шагов, определяют, когда развитие считается законченным [1].
С целью отработки алгоритмов построения фракталов в учебных целях автором была разработана программа для построения и визуализации фракталов, заданных L-системой. Она позволяет построить практически любой фрактал, который можно задать L-системой. Из особенностей программы можно выделить следующие: раскраска фракталов, многопоточное вычисление и прорисовка изображения, возможность монтажа фракталов в единое изображение.
Литература
- Р. Кроновер. Фракталы и хаос в динамических системах. М.: Постмаркет, 2000
- С.В. Кулешов. Фрактальное шифрование // Труды СПИИРАН. Вып. 2 — СПб: СПИИРАН, 2004
- B. Cheng, A. Zhang. Using Fractal Coding to Index Image Content for a Digital Library.DCS. University of New York, 1999
- C. Evertsz. Fractal Geometry of Financial Time Series. Center for Complex Systems and Visualization, University of Bremen, 1995