Стохастичні фрактали

Ще одним відомим класом фракталів є стохастичні фрактали, які виходять в тому випадку, якщо коли в ітераційному процесі випадковим чином міняти які-небудь його параметри. При цьому утворюються об’єкти дуже схожі на природні – несиметричні дерева, порізані берегові лінії і так далі Двовимірні стохастичні фрактали використовуються при моделюванні рельєфу місцевості і поверхні моря. У зв’язку з цим двовимірні стохастичні фрактали дуже часто використовуються під час моделювання різних природних об’єктів: рельєфу місцевості, поверхні моря тощо (рис. 16).

Рис. 16. Використання стохастичних фракталів для моделювання природних об’єктів

Плазма – найвідоміший стохастичний фрактал (рис. 17). Покроковий алгоритм побудови:

1. Нехай потрібно заповнити плазмою квадрат точок.

2. Задається яким-небудь чином, наприклад, випадково, кольори кутів квадрата.

3. Визначається колір середини кожної сторони як середнє між кольорами інцидентних їй вершин плюс / мінус деяка випадкова величина.

4. Визначається колір центру квадрата як середнє між кутами плюс / мінус деяка випадкова величина.

5. Виходить 4 квадрати із заданими вершинами – для кожного з них повторюється алгоритм з третього кроку.

Розмах випадкової величини має залежати від розміру квадрата – чим менший квадрат, тим менше відхилення.

Рис. 17. Плазма

Існують і інші класифікації фракталів, наприклад поділподіл фракталів на детерміновані (алгебраїчні і геометричні) і недетермінованих (стохастичні).

4. Iterated Functions System (система ітераційних функцій)

Метод Iterated Functions System (IFS) з’явився в середині 80-х років як простий засіб отримання фрактальних структур.

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

(2)

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

На підставі цих ідей Барнслі і Слоан створили алгоритм, який, за їх твердженням, дозволить стискувати інформацію в 500–1000 разів. Коротко метод можна описати таким чином. Зображення кодується декількома простими перетвореннями (у нашому випадку афінними), тобто коефіцієнтами цих перетворень (у нашому випадку A,B,C,D,E,F).

Наприклад, закодувавши якесь зображення двома афінними перетвореннями, ми однозначно визначаємо його за допомогою 12-ти коефіцієнтів. Якщо тепер задати яку-небудь початкову точку (наприклад, X =0 Y =0) і запустити ітераційний процес, то після першої ітерації отримаємо дві точкиточки, після другої – чотири, після третьої – вісім і так далі. Через декілька десятків ітерацій сукупність отриманих точок описуватиме закодоване зображення. Але проблема полягає в тому, що дуже важко знайти коефіцієнти IFS, які кодували б довільне зображення.

Для побудови IFS застосовують окрім афінних і інші класи простих геометричних перетворень, які задаються невеликим числом параметрів. Наприклад, проектні:

(3)

або квадратичні:

(4)

Як приклад використання IFS для побудови фрактальних структур, розглянемо “дракон” Хартера-Хейтуея (рис.18, 19) і криву Коха. Виділимо в цих структурах подібні частини і для кожної з них обчислимо коефіцієнти афінного перетворення. У афінний колаж буде включено стільки афінних перетворень, скільки існує частин подібних цілому зображенню.

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

Побудуємо IFS для “дракона” Хартера-Хейтуея. Для цього розташуємо перше покоління цього фрактала на сітці координат дисплея 640 350 (рис. 18). Позначимо точки ламаної, що отримали, як A, B, C. За правилами побудови у цього фрактала дві частини подібні цілому – на рис.18 це ламані ADB і BEC. Знаючи координати кінців цих відрізків, можна обчислити коефіцієнти двох афінних перетворень, що переводять ламану ABC в ADB і BEC:

(5)

Задавши початкову стартову точку (наприклад, X =0, Y =0), й, ітераційно діючи на неї IFS, після десятої ітерації на екрані отримаємо фрактальну структуру, зображену на рис.19, яка є “драконом” Хартера-Хейтуея. Його кодом (стислим описом) є набір коефіцієнтів двох афінних перетворень.

Рис. 19. “Дракон” Хартера-Хейтуея, побудований за допомогою IFS в прямокутнику 640 350

Аналогічно можна побудувати IFS для кривої Коха. Неважко бачити, що ця крива має чотири частини, подібні до цілої кривої (рис. 20). Для знаходження IFS знову розташуємо перше покоління цього фрактала на сітці координат дисплея 640 350.

Рис. 20. Заготовкавка для побудови IFS кривої Коха

Для її побудови потрібний набір афінних перетворень, що складається з чотирьох перетворень:

(6)

Результат застосування цього афінного колажа після десятої ітерації можна побачити на рис. 21.

Рис. 21. Крива Коха, побудована за допомогою IFS у прямокутнику 640 350

Використання IFS для стиску звичайних зображень (наприклад, фотографій) засноване на виявленні локальної самоподібності, на відміну від фракталів, де спостерігається глобальна самоподібність. За алгоритмом Барнслі відбувається виділення в зображенні пар областей, менша з яких подібна більшій, і збереження декількох коефіцієнтів, що кодують перетворення та переводять велику область в меншу. Потрібно, щоб безліч “менших” областей покривали все зображення. При цьому у файл, що кодує зображення будуть записані не тільки коефіцієнти, що характеризують знайдені перетворення, але і місцеположення та лінійні розміри “великих” областей, які разом з коефіцієнтами описуватимуть локальну самоподібність кодованого зображення. Алгоритм відновлення у цьому випадку повинен застосовувати кожне перетворення не до всієї множини крапок, що вийшли на попередньому кроці алгоритму, а до деякої підмножини, що належить області, відповідній перетворенню.