Θεωρητική Ιδέα της Fractal Συμπίεσης

Έστω ότι έχουμε μετρικό χώρο $(X,D)$ όπου $D$ είναι η μετρική Hausdorff. Θυμίζουμε ότι $X$ είναι σύνολο μη κενών συμπαγών συνόλων. Από το θεώρημα 3.4.1 έχουμε ότι, αν ορίσουμε ένα σύστημα επαναλαμβανόμενων συναρτήσεων, $(f_1\ldots f_n)$, εφαρμοσμένο σε μια συστελλόμενη λίστα λόγου, τότε υπάρχει ένα μοναδικό στοιχείο (σύνολο) $K$ του $X$ ώστε για οποιοδήποτε στοιχείο $A_0$ του $X$ να ισχύει

$$K=\lim_{k\rightarrow \infty} \bigcup_{i=1}^{n} f_i[A_{k}] \quad \hbox{όπου}\ A_{k}=\bigcup_{i=1}^{n}f[A_{k-1}]$$

Οπότε αν πάρουμε οποιοδήποτε στοιχείο $K$ του $X$ τότε ίσως (όχι όμως κατ'' άναγκη) μπορούμε να βρούμε ένα σύστημα επαναλαμβανόμενων συναρτήσεων που να αποτελείται από συστολές και για το οποίο το $K$ να είναι αναλοίωτο σύνολο. Έτσι εφαρμόζοντας άπειρες φορές το σύστημα επαναλαμβανόμενων συναρτήσεων πάνω σε οποιοδήποτε στοιχείο του $X$ θα πάρουμε το $K$.

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

Άλλο ένα πρόβλημα που παρουσιάζει η θεωρία είναι το ερώτημα αν υπάρχει κατάλληλο σύστημα επαναλαμβανόμενων συναρτήσεων για το οποίο το $K$ είναι αναλλοίωτο. Το λημμά 3.4.2 μας λέει ότι σίγουρα μπορούμε να βρούμε ένα σύστημα επαναλαμβανόμενων συναρτήσεων, το αναλλοίωτο σύνολο του οποίου είναι όσο πιο κοντά θέλουμε στο $K$. Και επειδή στην παράξη πάντα μιλάμε για προσέγγιση, (αφού το άπειρο είναι απλά ένας μεγάλος αριθμός) ορίζοντας το μεγεθός του σφάλματος, το λήμμα 3.4.2 μας καλύπτει ικανοποιητικά.

Τέλος η θεωριά δεν μας λέει καθόλου πως βρίσκουμε το σύστημα επαναλαμβανόμενων συναρτήσεων ώστε να είναι αναλλοίωτο ως προς αυτό. Μας μένει παρά να εξετάσουμε όλα τα συστήματα επαναλαμβανόμενων συναρτήσεων με συστελλόμενες λίστες λόγου και να επιλέξουμε το κατάλληλο. Το πρόβλημα είναι οτι υπάρχουν υπεραριθμήσημα τέτοια συστήματα επαναλαμβανόμενων συναρτήσεων, οπότε υπολογιστικά είναι αδύνατον να εξετάσουμε όλες τις περιπτώσεις. Θα δούμε αργότερα πως θα χειριστούμε αυτή την δυσκολία.

Έτσι λοιπόν μπορούμε να περιγράψουμε την εικόνα με μια σειρά από συστήματα επαναλαμβανόμενων συναρτήσεων (κάθε κομμάτι της εικόνας θα έχει δικό της ξεχωριστό σύστημα επαναλαμβανόμενων συναρτήσεων), τα οποία αν εφαρμόσουμε ((πολλές φορές)) σε οποιαδήποτε αρχική εικόνα θα πάρουμε, τις προσέγγισεις των τμημάτων της αρχικής μας εικόνας. Ευελπιστώντας ότι η παρουσίαση τέτοιων συστημάτων επαναλαμβανόμενων συναρτήσεων σε μορφή δεδομένων καταλαμβάνει ((πολύ)) λιγότερο όγκο απ'' ότι η ίδια η εικόνα μπορούμε να αποθηκεύουμε και να στέλνουμε από τα κανάλια επικοινωνίας μόνο τα συστήματα επαναλαμβανόμενων συναρτήσεων έτσι ώστε στην συνέχεια να μπορούμε να ανασχηματίσουμε την αρχική μας εικόνα χρησιμοποιώντας κάποιο κατάλληλο λογισμικό. Όπως έχει ειπωθεί υπάρχουν κάποιες δυσκολίες με τις πραγματικές εικόνες, οπότε και η συμπίεση τους έχει την ιδιοτροπία της, με την οποία και θα ασχοληθούμε στην συνέχεια.

Έστω ότι έχουμε την εικόνα $K$. Θα θεωρούμε ότι η $K$ είναι κωδικοποιημένη αν παρουσιάζεται ως μια ακολουθία τών συστημάτων επαναλαμβανόμενων συναρτήσεων (εννοείται ότι όλες οι συναρτήσεις των συστημάτων επαναλαμβανόμενων συναρτήσεων είναι συστολές). Στη ιδανική περίπτωση κάθε κομμάτι τις διαμερισμένης εικόνας θα ήταν αναλλοίωτο για το Σ.Ε.Σ που του αντιστοιχεί.

Όπως ειπώθηκε για να το επιτύχουμε είναι σχεδόν αδύνατον, οπότε από εδώ και πέρα θα μιλάμε για την προσέγγιση της εικόνας και όχι ακριβές αντίγραφο.

Έτσι λοιπόν στην εύρεση των συστημάτων επαναλαμβανόμενων συναρτήσεων θα βάλουμε κάποιους περιορισμούς. Αντί να ψάχνουμε όλο το σύνολο συστολών που υπάρχουν, μπορούμε να περιοριστούμε σε κάποιες κλάσεις των συναρτήσεων. Σ'' αυτήν την πτυχιακή εργασιά, θα χρησιμοποιησούμε συστήματα επαναλαμβανόμενων συναρτήσεων που αποτελούνται από συνδιασμό τριών διαφορετικής φύσεως συστολών.

Παρακάτω παρουσιάζουμε τα βήματα της κατασκευής του αλγορίθμου της ((fractal συμπίεσης)) της εικόνας.

1. Στην αρχή ορίζουμε ένα πεπερσμένο το πλήθος κλάσεις συσχετιζόμενων συστολών.
2. Μετά ορίζουμε την μέθοδο διαμέρισης της εικόνας σε κομμάτια (για τα οποία θα ψάχνουμε τα αντίστοιχα συστήματα επαναλαμβανόμενων συναρτήσεων.
3. Τέλος ορίζουμε την διαδικασία εύρεσης των συστημάτων επαναλαμβανόμενων συναρτήσεων τέτοιων ώστε το λάθος της προσέγγισης να είναι στα επιτρεπτά όρια.