Fractal Συμπίεση των Εικόνων

Η συμπίεση των δεδομένων είναι ίσως από τα πιό σημαντικά προβλήματα που συναντάμε όταν συζητάμε για την αποθήκευση της πληροφορίας και την μεταφορά της μέσω των γραμμών επικοινωνίας.

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

Σχεδόν κάθε πληροφορία μπόρει να παρουσιαστεί με την μορφη δεδομένων, μάλιστα η ίδια πληροφορία μπορεί να παρουσιαστεί με διάφορες μορφές δεδομένων. Για παράδειγμα το σκηνικό που ζωγράφισε ο ζωγράφος, ένας λογοτέχνης μπορεί να το περιγράψει με λόγια, έτσι η πληροφορια αποτυπώνεται με την μορφή κειμένου.

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

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

Σύμφωνα με την ψηφιακή αναπαράσταση της εικόνας θεωρείται ότι κάθε εικόνα αποτελείται από εικονοστοιχεία. Το εικονοστοιχείο (pixel, από το αγγλικό picture element) είναι στοιχειώδες τετραγωνικό τμήμα της εικόνας που δεν μπορεί να χωριστεί σε μικρότερα κομμάτια. Κάθε εικονοστοιχείο έχει δύο μοναδικές ακέραιες συντεταγμένες $(x,y)$, $0\leq x<X$ και $0\leq y<Y$, όπου $X$ και $Y$ είναι οι διαστάσεις (σε εικονοστοιχεία) της εικόνας. Επιπλέον, για ασπρόμαυρες εικόνες, σε κάθε εικονοστοιχείο αντιστοιχεί ένας ακέραιος από το μηδέν έως κάποιο αριθμό, αναλόγος για τι ποιότητα της εικόνας μιλάμε, που λέγεται ένταση. Στην ουσία η ένταση καθορίζει το πόσο σκούρο είναι το εικονοστοιχείο. Τώρα στις έγχρωμες εικόνες επικρατεί η ιδιά λογική, απλά αντι για μια ένταση του μαύρου χρώματος έχουμε τρεις μεταβλητές εντάσεων, που η κάθε μία αντιστοιχεί σε κάποιο βασικό χρώμα. Για παράδειγμα σε συστημα RGB, έχουμε τρία βασικά χρώματα, κόκκινο, πράσινο και γαλανό. Θεωρείται ότι με την μείξη των τριών αυτών χρωμάτων πετυχαίνουμε όποιο άλλο χρώμα θέλουμε. Στην συνέχεια θα ασχοληθούμε μόνο με ασπρόμαυρες ψηφιακές εικόνες.

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

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

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

Στην συνέχεια θα ασχοληθούμε με την συμπίεση με απώλειες της ψηφιακής ασπρόμαυρης εικόνας, ο αλγόριθμος της οποίας βασίζεται στην θεωρία των αυτοόμοιων συνόλων που παρουσιάστηκε στο προηγούμενο κεφάλαιο και φέρει το όνομα ((θραυσματική (fractal) συμπίεση)).