POWRÓT DO STRONY GŁÓWNEJ

IFS - Iterated Functions System

Copyright © 2004   Robert Nowotniak

Kod źródłowy: https://github.com/rnowotniak/ifs2004.



Wstęp

Program IFS służy do tworzenia i badania fraktali, dziwnych atraktorów i układów dynamicznych opartych na systemie iterowanych odwzorowań. Obrazy mogą być tworzone przy pomocy klasycznego modelu Kopiarki Wielokrotnie Redukującej a także algorytmu probabilistycznego, tzw. modelu sprzężonego z ruletką (układ losowy). Przy wyborze losowym istnieje możliwość regulacji prawdopodobieństw wyboru odwzorowań, co pozwala dostrajać układy na różne sposoby. Program znacznie ułatwi także wyobrażenie sobie, w jaki sposób przekształcenia afiniczne - w szczególności liniowe - działają na płaszczyznę.


Jak to działa?

Iterowany układ odwzorowań jest matematycznym modelem Kopiarki Wielokrotnie Redukującej. Klasyczny model kopiarki działa na zasadzie sprzężenia zwrotnego przy użyciu układu soczewek, odwzorowujących płaszczyznę i wykonujących translacje, skalowania, pochylenia, obroty i odbicia. Pozwala to zakodować bardzo złożone, samoafiniczne obrazy przy użyciu jedynie niewielkiej liczby współczynników. Przekształcenie afiniczne odwzorowuje punkt płaszczyzny (x, y) na punkt (u, v) za pomocą równań:

,    (1°)

co odpowiada macierzy odwzorowania:

.

Aby móc wyrazić złożenie przekształceń w wygodny sposób, przyjmuje się oznaczenia:

.

Dzięki temu współczynniki r i s mogą być utożsamiane z rozciąganiem soczewki w poziomie i pionie, a φ i ψ z kątami obrotów.
Po podstawieniu otrzymujemy równoważną macierz:

.

Program pozwala posługiwać się obydwiema tymi notacjami w łatwy sposób:

Działanie polegające na sumowaniu obrazów uzyskanych z poszczególnych soczewek jest nazywane operatorem Hutchinsona, a wielokrotne przekształcanie jest iterowaniem tego operatora. Uzyskany ciąg obrazów dąży w granicy do obrazu, będącego atraktorem danego układu odwzorowań.

Drzewo uzyskane za pomocą sześciu układów równań KWR.
Czy to nie zadziwiające, jak bardzo jest podobne w swojej budowie do naturalnego drzewa?

Algorytm IFSP jest modelem urządzenia, łączącego determinizm z losowością. Wybór odwzorowania, któremu zostanie poddany rezultat poprzedniego kroku sprzężenia zwrotnego jest tu zupełnie losowy. Szczególnym i najprostszym przykładem takiego układu, opartego na chaosie, jest algorytm nazwany przez M. Barnsleya "grą w chaos", prowadzący do uzyskania trójkąta Sierpińskiego.

Ogromną zaletą algorytmu probabilistycznego IFSP jest znacznie mniejsza złożoność obliczeniowa, bo jedynie O(n), gdzie rozmiarem danych jest liczba punktów, poddawanych iterowaniu. Złożoność obliczeniowa w klasycznym przypadku IFS jest funkcją wykładniczą o podstawie równej ilości soczewek. W układach o bardzo małej liczbie soczewek (np. smok Hartera-Heighwaya) warto stosować model klasyczny nawet przy dość dużej liczbie powtórzeń. Natomiast model sprzężony z ruletką daje dobre rezultaty zwłaszcza po dobraniu odpowiednich prawdopodobieństw wyboru odwzorowań. Soczewki o dużych powierzchniach powinny być wybierane znacznie częściej niż wąskie patyczki.
Obraz uzyskany w modelu losowym jest też często trochę zaciemniony małą ilością punktów w niespodziewanych miejscach, jednak ostatecznie uwidacznia się pewien atraktor, o ile nie jest to układ niestabilny. Stąd lepiej nie stosować go w przypadku fraktali, w których jest to istotne (np. kurz Cantora).

W tym układzie jako obrazu wejściowego użyłem bitmapy ze zbiorem Mandelbrota. Po 6 cyklach widać, że uzyskany fraktal to krzywa Kocha.

Otrzymywanie stałego obrazu końcowego dla danego układu soczewek, niezależnie od danych podanych na wejściu przed pierwszym cyklem wynika z zasady Banacha o odwzorowaniu zwężającym. W tym przypadku punktami przestrzeni, na którą działa operator Hutchinsona są obrazy uzyskiwane w kolejnych cyklach, metryką jest natomiast odległość Hausdorffa między tymi obrazami. Operator działa zwężająco w zależności od tego, w jakiej skali kopiuje soczewka, która pomniejsza obraz w najmniejszym stopniu. Ponieważ odwzorowanie zwężające ma zawsze jeden punkt stały, końcowy obraz nie zależy od punktu (obrazu) początkowego, co pokazuje powyższy przykład. W szczególności taki sam atraktor uzyskuje się w sytuacji, gdy obraz początkowy składa się z pojedynczego punktu, na tym fakcie opiera się algorytm losowy.

Nakładanie bitmap przekształconych według podanej macierzy odbywa się w programie przez wyznaczenie macierzy przekształcenia odwrotnego. Każdy punkt docelowej bitmapy jest sprawdzany, czy nie jest on obrazem jakiegoś punktu należącego do bitmapy źródłowej w danym przekształceniu. Współrzędne takiego punktu znajduję za pomocą rozwiązania układu (1°) względem niewiadomych x i y, co daje:

.

Program może też użyć rekurencyjnego algorytmu znajdowania obrazu w n-tym cyklu. W ten sposób uzyskuje się stos macierzy przekształceń afinicznych. Tylko w najgłębszym poziomie rekurencji (równym żądanej ilości powtórzeń) wykonuje się rysowanie przy użyciu aktualnie obowiązującego przekształcenia. W innym przypadku dla każdej soczewki funkcja wywołuje samą siebie, ustalając nową obowiązującą macierz przekształcenia przez złożenie aktualnego przekształcenia z przekształceniem danej soczewki.
Zakładając, że mamy przekształcenia afiniczne f1:(x,y)→(u1,v1) i f2:(u1,v1)→(u2,v2):

    ,    

złożeniem tych przekształceń jest f3=f2(f1):(x,y)→(u2,v2):


Przykłady fraktali


Pobierz

Kod źródłowy dostępny jest w repozytorium: https://github.com/rnowotniak/ifs2004.

Licencja

Niniejszy program jest wolnym oprogramowaniem; możesz go rozprowadzać dalej i/lub modyfikować na warunkach Powszechnej Licencji Publicznej GNU, wydanej przez Fundację Wolnego Oprogramowania - według wersji 2-giej tej Licencji lub którejś z późniejszych wersji.

Obrazki na tej stronie zostały zrobione za pomocą mojego programu.


Bibliografia

POWRÓT DO STRONY GŁÓWNEJ