Ітераційні Функціональні Системи: Підліс Барнслі та Гра… |…

Ітераційні Функціональні Системи: Підліс Барнслі та Гра Шале

Двигун, що лежить в основі IFS, є Теорема про Фіксова Точкову Контракцію Банаха: будь-яка контракційна функція має унікальну фіксова точку, і повторне застосування збігається до неї з будь-якої початкової позиції. Ітераційна Функціональна Система (IFS) - це кінцевий набір контракційних функцій {f₁, …, fₙ} на ℝⁿ, зазвичай афінних (fᵢ(x) = Aᵢx + bᵢ, де всі власні значення Aᵢ менші за 1 за величиною). Атрактор IFS (A) є унікальним компактним набором, що задовольняє наступному: A = f₁(A) ∪ f₂(A) ∪ ... ∪ fₙ(A) Починаючи з будь-якого компактного набору S₀: S_{k+1} = f₁(Sₖ) ∪ ... ∪ fₙ(Sₖ) → A (метрика Хаусдорфа, експоненціально швидко) Незалежно від того, чи починаєте ви з точки, заповненого квадрата або випадкового нарису, орбіта збігається до одного і того ж фрактального атрактора — самосхожість за визначенням.

A = f₁(A) ∪ f₂(A) ∪ ... ∪ fₙ(A)

Starting from ANY compact set S₀:
S_{k+1} = f₁(Sₖ) ∪ ... ∪ fₙ(Sₖ)  →  A  (Hausdorff metric, exponentially fast)

Гра з хаосом

Відстеження експоненційно зростаючих функцій є недоцільним, тому гра з хаосом Майкла Барнслі (1988) відслідковує окрему випадкову орбіту замість цього: вибирайте трансформацію випадковим чином, зважену ймовірністю pᵢ, застосовуйте її, малюйте точку, повторюйте сотні тисяч разів (пропускаючи перші ~20 для розігріву). Природним вибором є pᵢ ∝ |det(Aᵢ)|, пропорційне площі, яку покриває кожна трансформація, що забезпечує рівномірну щільність на аттракторі. Весь алгоритм працює за часом O(N) – будь-який IFS фрактал рендериться за мілісекунди.

жива демонстрація · пов'язана симуляція● LIVE

Гортна бамбук: чотири лінійні перетворення, одна листка

Лише чотири лінійні трансформації створюють структуру, візуально ідентичну справжньому бамбуку: одне (p=0.01) стискає весь бамбук до мізерного стебла, друге (p=0.85) копіює бамбук у масштабі 85% для основного листка, а ще два (p=0.07 кожен) генерують лівий та правий листочки, повернуті приблизно на 83° та 37°. Ймовірності закодовані відносний вага кожного перетворення в області притягування — встановіть їх усі однакові, і гра хаосу все ще збігається до тієї ж форми бамбука, але стебло та листочки будуть надмірно представлені, а основне тіло позбавлене точок.

Розмір фрактальності та теорема колажу

Для самосхожої IFS (ітераційної функціональної системи), що задовольняє умову відкритого множини (трансформовані копії не перекриваються), розмір Гаусдорфа d розв’язує рівняння Морана Σᵢ rᵢᵈ = 1, де rᵢ – коефіцієнт стиснення кожної трансформованої копії — що дає трикутник Sierpiński розмір log(3)/log(2) ≈ 1.585 та крива Коха розмір log(4)/log(3) ≈ 1.262.

Розв’язування задачі назад є теоремою колажу: якщо можна покрити цільове зображення трансформованими копіями самого себе з похибкою ε, то IFS-атрактор приблизно відповідає цільовому зображенню з похибкою, обмеженою ε/(1−c), де c – максимальний коефіцієнт стиснення. Це є основою для фрактального стиснення зображень – кодування зображення як невеликий набір самовідносних трансформацій замість безпосередніх пікселів.

Часті запитання

Що таке Ітераційна Функціональна Система?

Ітераційна Функціональна Система (IFS) – це кінцетий набір скоротливих відображень, зазвичай афінних трансформацій, унікальний фіксований пункт у просторі компактних множин – це фрактальний притягуючий об’єкт A, що задовольняє A = f1(A) ∪ f2(A) ∪ ... ∪ fn(A). Починаючи з будь-якої форми та повторювано застосовуючи ці відображення, ми сходимося до одного й того ж притягуючого об’єкта незалежно від початкової точки.

Як гра Chaos Game рендерить фрактал IFS?

Замість відстежувати експоненційно зростаючі множини, Chaos Game відслідковує одну випадкову орбіту: починаючи з будь-якої точки, повторно вибирається одна трансформація на рандом (зважена ймовірністю) та застосовується, а кожна нова точка малюється після короткого розігріву. Після кількох сотень тисяч ітерацій притягуючий об’єкт стає видимим, а алгоритм працює за часом O(N).

Що таке Теорема Колажу?

Теорема Колажу – це зворотна задача: якщо задано цільове зображення, і якщо його можна покрити трансформованими копіями самого себе (колажем) з похибкою епсилон, то отриманий IFS фрактал буде наближатися до цільового зображення з похибкою, обмеженою епсилоном поділеним на (1 мінус максимальне скоротливе співвідношення). Це математична основа для стиснення фрактальних зображень.

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.

▶ Відкрити симуляцію the simulation