Επαναλαμβανόμενα συστήματα συναρτήσεων

Στα μαθηματικά, τα επαναλαμβανόμενα συστήματα συναρτήσεων (IFS) είναι μια μέθοδος κατασκευής φράκταλ- τα προκύπτοντα φράκταλ είναι συχνά αυτοομοιόμορφα. Τα φράκταλ IFS σχετίζονται περισσότερο με τη θεωρία συνόλων παρά με τη μορφοκλασματική γεωμετρία[1].

Έγχρωμο IFS που σχεδιάστηκε με το λογισμικό Apophysis και αποδόθηκε από το Electric Sheep.

Τα φράκταλ IFS, όπως συνήθως ονομάζονται, μπορούν να έχουν οποιονδήποτε αριθμό διαστάσεων, αλλά συνήθως υπολογίζονται και σχεδιάζονται σε 2Δ. Το φράκταλ αποτελείται από την ένωση πολλών αντιγράφων του εαυτού του, κάθε αντίγραφο του οποίου μετασχηματίζεται από μια συνάρτηση (εξ ου και "σύστημα συναρτήσεων"). Το χαρακτηριστικό παράδειγμα είναι το τρίγωνο Σιερπίνσκι. Οι συναρτήσεις είναι συνήθως συσταλτικές, πράγμα που σημαίνει ότι φέρνουν τα σημεία πιο κοντά μεταξύ τους και μικραίνουν τα σχήματα. Ως εκ τούτου, το σχήμα ενός IFS φράκταλ αποτελείται από πολλά, ενδεχομένως αλληλεπικαλυπτόμενα, μικρότερα αντίγραφα του εαυτού του, καθένα από τα οποία αποτελείται επίσης από αντίγραφα του εαυτού του, μέχρι το άπειρο. Αυτή είναι η πηγή της αυτοομοιόμορφης κλασματικής φύσης του.

Ορισμός

Κατασκευή ενός IFS με το παιχνίδι του χάους ("κινούμενη εικόνα")

Τυπικά, ένα σύστημα επαναλαμβανόμενων συναρτήσεων είναι ένα πεπερασμένο σύνολο απεικονίσεων συστολής σε έναν πλήρη μετρικό χώρο^[1] Συμβολικά,,

${\displaystyle \{f_{i}:X\to X\mid i=1,2,\dots ,N\},\ N\in \mathbb {N} }$

είναι ένα επαναληπτικό σύστημα συναρτήσεων αν κάθε ${\displaystyle f_{i}}$ είναι μια συστολή στον πλήρη μετρικό χώρο ${\displaystyle X}$.

Ιδιότητες

Το IFS είναι κατασκευασμένο με δύο συναρτήσεις.

Ο Χάτσινσον έδειξε ότι, για τον μετρικό χώρο ${\displaystyle \mathbb {R} ^{n}}$, ή γενικότερα, για έναν πλήρη μετρικό χώρο ${\displaystyle X}$, ένα τέτοιο σύστημα συναρτήσεων έχει ένα μοναδικό μη κενό συμπαγές (κλειστό και περιορισμένο) σταθερό σύνολο S. ^[2] Ένας τρόπος κατασκευής ενός σταθερού συνόλου είναι να ξεκινήσουμε με ένα αρχικό μη κενό κλειστό και περιορισμένο σύνολο S₀ και να επαναλάβουμε τις δράσεις των f_i, θεωρώντας το S_n+1 ως την ένωση των εικόνων του S_n κάτω από τις f_i- στη συνέχεια θεωρώντας το S ως το κλείσιμο του ορίου ${\displaystyle \lim _{n\rightarrow \infty }S_{n}}$. Συμβολικά, το μοναδικό σταθερό (μη κενό συμπαγές) σύνολο ${\displaystyle S\subseteq X}$ έχει την ιδιότητα

${\displaystyle S={\overline {\bigcup _{i=1}^{N}f_{i}(S)}}.}$

Το σύνολο S είναι επομένως το σταθερό σύνολο του τελεστή Χάτσινσον ${\displaystyle F:2^{X}\to 2^{X}}$ που ορίζεται για ${\displaystyle A\subseteq X}$ μέσω

${\displaystyle F(A)={\overline {\bigcup _{i=1}^{N}f_{i}(A)}}.}$

Η ύπαρξη και η μοναδικότητα του S είναι συνέπεια της αρχής της αντιστοίχισης με συστολή, όπως και το γεγονός ότι

${\displaystyle \lim _{n\to \infty }F^{n}(A)=S}$

για κάθε μη κενό συμπαγές σύνολο ${\displaystyle A}$ στο ${\displaystyle X}$. (Για συσταλτά IFS αυτή η σύγκλιση λαμβάνει χώρα ακόμη και για οποιοδήποτε μη κενό κλειστό περιορισμένο σύνολο ${\displaystyle A}$). Τυχαία στοιχεία αυθαίρετα κοντά στο S μπορούν να προκύψουν από το παιχνίδι του χάους, που περιγράφεται παρακάτω.

Προσφάτως αποδείχθηκε ότι τα IFS μη συσταλτικού τύπου (δηλαδή αποτελούμενα από χάρτες που δεν είναι συσταλτά σε σχέση με οποιαδήποτε τοπολογικά ισοδύναμη μετρική στο X) μπορούν να δώσουν ελκυστές. Προκύπτουν φυσικά στους προβολικούς χώρους, αν και η κλασική ανορθολογική περιστροφή στον κύκλο μπορεί επίσης να προσαρμοστεί.^[3]

Η συλλογή των συναρτήσεων ${\displaystyle f_{i}}$ παράγει ένα μονοειδές υπό σύνθεση. Αν υπάρχουν μόνο δύο τέτοιες συναρτήσεις, το μονοειδές μπορεί να απεικονιστεί ως ένα δυαδικό δέντρο, όπου, σε κάθε κόμβο του δέντρου, μπορεί κανείς να συνθέσει με τη μία ή την άλλη συνάρτηση (δηλαδή να πάρει τον αριστερό ή τον δεξιό κλάδο). Γενικά, αν υπάρχουν k συναρτήσεις, τότε μπορεί κανείς να απεικονίσει το μονοειδές ως ένα πλήρες k'-αριαίο δέντρο, γνωστό και ως δέντρο Κέιλι.

Κατατμημένα συστήματα επαναλαμβανόμενων συναρτήσεων

Τα PIFS (partitioned iterated function systems), που ονομάζονται επίσης συστήματα τοπικών επαναλαμβανόμενων συναρτήσεων,^[4] δίνουν εντυπωσιακή συμπίεση εικόνας, ακόμη και για φωτογραφίες που δεν φαίνεται να έχουν τα είδη της αυτοομοειδούς δομής που παρουσιάζουν τα απλά φράκταλ IFS^[5].

Κατασκευές

Φτέρη του Μπάρνσλεϊ, ένα πρώιμο IFS

Σπόγγος του Μένγκερ, ένα τρισδιάστατο IFS.

Σε ορισμένες περιπτώσεις, κάθε συνάρτηση ${\displaystyle f_{i}}$ απαιτείται να είναι ένας γραμμικός, ή γενικότερα ένας συγγενής, μετασχηματισμός, και συνεπώς να αναπαρίσταται από έναν πίνακα. Ωστόσο, τα IFS μπορούν επίσης να δομηθούν από μη γραμμικές συναρτήσεις, συμπεριλαμβανομένων των προβολικών μετασχηματισμών και των μετασχηματισμών Möbius. Η φλόγα φράκταλ είναι ένα παράδειγμα ενός IFS με μη γραμμικές συναρτήσεις.

Ο πιο συνηθισμένος αλγόριθμος για τον υπολογισμό των φράκταλ IFS ονομάζεται "παιχνίδι του χάους". Αποτελείται από την επιλογή ενός τυχαίου σημείου στο επίπεδο και στη συνέχεια την επαναληπτική εφαρμογή μιας από τις συναρτήσεις που επιλέγονται τυχαία από το σύστημα συναρτήσεων για να μετασχηματίσουν το σημείο ώστε να προκύψει ένα επόμενο σημείο. Ένας εναλλακτικός αλγόριθμος είναι η δημιουργία κάθε δυνατής ακολουθίας συναρτήσεων μέχρι ένα δεδομένο μέγιστο μήκος και στη συνέχεια η σχεδίαση των αποτελεσμάτων της εφαρμογής κάθε μιας από αυτές τις ακολουθίες συναρτήσεων σε ένα αρχικό σημείο ή σχήμα.

Έκαστος από αυτούς τους αλγορίθμους παρέχει μια σφαιρική κατασκευή η οποία παράγει σημεία κατανεμημένα σε ολόκληρο το φράκταλ. Εάν σχεδιάζεται μια μικρή περιοχή του φράκταλ, πολλά από αυτά τα σημεία θα βρίσκονται εκτός των ορίων της οθόνης. Αυτό καθιστά μη πρακτική τη μεγέθυνση σε μια κατασκευή IFS που σχεδιάστηκε με αυτόν τον τρόπο.

Παρότι η θεωρία του IFS απαιτεί κάθε συνάρτηση να είναι συσταλτική, στην πράξη τα λογισμικά που υλοποιούν το IFS απαιτούν μόνο να είναι ολόκληρο το σύστημα συσταλτικό κατά μέσο όρο^[6].

Το αντίστροφο πρόβλημα

Υπάρχουν πολύ γρήγοροι αλγόριθμοι για τη δημιουργία μιας εικόνας από ένα σύνολο παραμέτρων IFS ή PIFS. Είναι γρηγορότερο και απαιτεί πολύ λιγότερο αποθηκευτικό χώρο η αποθήκευση μιας περιγραφής του τρόπου δημιουργίας της, η μετάδοση αυτής της περιγραφής σε μια συσκευή προορισμού και η αναγέννηση αυτής της εικόνας εκ νέου στη συσκευή προορισμού, παρά η αποθήκευση και η μετάδοση του χρώματος κάθε εικονοστοιχείου της εικόνας^[4].

"Δέντρο" IFS κατασκευασμένο με μη γραμμική συνάρτηση Julia

Το αντίστροφο πρόβλημα είναι πιο δύσκολο: δεδομένου ότι υπάρχει κάποια αρχική αυθαίρετη ψηφιακή εικόνα, όπως μια ψηφιακή φωτογραφία, προσπαθήστε να βρείτε ένα σύνολο παραμέτρων IFS το οποίο, όταν αξιολογείται με επανάληψη, παράγει μια άλλη εικόνα οπτικά παρόμοια με την αρχική. Το 1989, ο Αρνό Ζακίν παρουσίασε μια λύση σε μια περιορισμένη μορφή του αντίστροφου προβλήματος χρησιμοποιώντας μόνο PIFS- η γενική μορφή του αντίστροφου προβλήματος παραμένει άλυτη^[7][8][4].

Από το 1995, όλο το λογισμικό συμπίεσης φράκταλ βασίζεται στην προσέγγιση του Ζακίν^[8].

Παραδείγματα

Το διάγραμμα απεικονίζει την κατασκευή ενός IFS από δύο affine συναρτήσεις. Οι συναρτήσεις αναπαρίστανται με την επίδρασή τους στο διμερές τετράγωνο (η συνάρτηση μετατρέπει το περιγεγραμμένο τετράγωνο στο σκιασμένο τετράγωνο). Ο συνδυασμός των δύο συναρτήσεων σχηματίζει τον τελεστή Χάτσινσον. Παρουσιάζονται τρεις επαναλήψεις του τελεστή και στη συνέχεια η τελική εικόνα είναι του σταθερού σημείου, του τελικού φράκταλ.

Πρώιμα παραδείγματα φράκταλ που μπορούν να παραχθούν από ένα IFS περιλαμβάνουν το σύνολο του Κάντορ, που περιγράφηκε για πρώτη φορά το 1884, και τις καμπύλες de Rham, έναν τύπο αυτοομοιομορφικής καμπύλης που περιγράφηκε από τον Ζορζ ντε Ραμ το 1957.

Ιστορία

Τα IFS επινοήθηκαν υπό τη σημερινή τους μορφή από τον Τζον Ε. Χάτσινσον το 1981^[2] και διαδόθηκαν από το βιβλίο του Μάικλ Μπάρνσλεϊ με τίτλο Fractals Everywhere.

Τα IFS παρέχουν μοντέλα για ορισμένα φυτά, φύλλα και φτέρες, λόγω της αυτοομοιότητας που εμφανίζεται συχνά στις δομές διακλάδωσης στη φύση.

- Μάικλ Μπαρνσλεϊ κ.ά.^[9].

Δείτε επίσης

• Χαλί του Σιερπίνσκι
• Φτέρη του Μπάρνσλεϊ
• Νιφάδα του Κοχ
• Καμπύλη Χίλμπερτ
• Καμπύλη του δράκου
• Σπόγγος του Μένγκερ

• Σύνολο Μάντελμπροτ
• Σύνολο Julia
• Οικοδομήσιμο Σύμπαν

Παραπομπές

1. Michael Barnsley (1988). Fractals Everywhere, p.82. Academic Press, Inc. (ISBN 9780120790623).
2. Hutchinson, John E. (1981). «Fractals and self similarity». Indiana Univ. Math. J. 30 (5): 713–747. doi:10.1512/iumj.1981.30.30055. https://maths-people.anu.edu.au/~john/Assets/Research%20Papers/fractals_self-similarity.pdf.
3. M. Barnsley, A. Vince, The Chaos Game on a General Iterated Function System
4. Bruno Lacroix. "Fractal Image Compression". 1998.
5. Fischer, Yuval (1992-08-12). «SIGGRAPH'92 course notes - Fractal Image Compression». Στο: Przemyslaw Prusinkiewicz, επιμ. Fractals - From Folk Art to Hyperreality. SIGGRAPH. ACM SIGGRAPH. Αρχειοθετήθηκε από το πρωτότυπο στις 2017-09-12. https://web.archive.org/web/20170912012035/https://karczmarczuk.users.greyc.fr/matrs/Dess/RADI/Refs/fractal_paper.pdf. Ανακτήθηκε στις 2017-06-30.
6. Draves, Scott· Erik Reckase (Ιουλίου 2007). «The Fractal Flame Algorithm» (PDF). Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 9 Μαΐου 2008. Ανακτήθηκε στις 17 Ιουλίου 2008.
7. Dietmar Saupe, Raouf Hamzaoui. "A Review of the Fractal Image Compression Literature".
8. John Kominek. "Algorithm for Fast Fractal Image Compression".

   doi:10.1117/12.206368

   .
9. Michael Barnsley, et al.,«V-variable fractals and superfractals» (PDF). (2.22 MB)