Εικόνα

Εικόνες και Εφαρμογές

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

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

Στο επόμενο επίπεδο έχουμε τις εικόνες συνεχούς τόνου (continuous tone images). Αυτές ορίζονται, σε αντίθεση με της διτονικές, ως οι εικόνες στις οποίες τα γειτονικά σημεία δεν διαφέρουν σημαντικά μεταξύ τους δηλαδή χαρακτηρίζονται από ομαλές τονικές διαβαθμίσεις. Υπάρχουν δύο είδη εικόνων συνεχούς τόνου: κλίμακας του γκρίζου (gray scale) και έγχρωμες (colour). Το πρώτο είδος βρίσκει παρόμοιες εφαρμογές με τις διτονικές. Η διαφορά είναι ότι τα έγγραφα μπορούν τώρα να έχουν και εικόνες οι οποίες αποδίδονται με διαβαθμίσεις του γκρίζου. Για παράδειγμα, ιατρικές φωτογραφίες αποτέλεσμα ακτινογραφιών ή υπερηχογραφημάτων μπορούν να αποδοθούν ικανοποιητικά από εικόνες κλίμακας του γκρίζου. Οι έγχρωμες εικόνες, όπως είναι φυσικό, βρίσκουν τη μεγαλύτερη χρήση και έχουν το μεγαλύτερο ενδιαφέρον. Χρησιμοποιούνται τόσο σε επαγγελματικές όσο και σε εκπαιδευτικές και ψυχαγωγικές εφαρμογές.

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

Σύλληψη Εικόνων

Η σύλληψη των εικόνων γίνεται συνήθως με χρήση scanner. Ένας scanner αποτελείται από μια πηγή φωτός, ένα χώρο τοποθέτηση του εγγράφου και έναν ανιχνευτή φωτός. Το φως που εκπέμπει η πηγή διαπερνά το έγγραφο και φτάνει στο δέκτη. Ανάλογα με την αλλοίωση που έχει υποστεί το φως, δημιουργείται ένα ηλεκτρικό σήμα που βρίσκεται σε  αντιστοιχία με την μορφή της εικόνας. Στο τέλος, το ηλεκτρικό αυτό σήμα ψηφιοποείται. Το αποτέλεσμα είναι ένας πίνακας εικονοστοιχείων (pixels). Το μέγεθος του πίνακα εξαρτάται από το είδος της εικόνας:

  • Για διτονικές εικόνες αρκεί ένα bit για κάθε στοιχείο του πίνακα (ένα pixel είναι είτε άσπρο είτε μαύρο).
  • Αν μια εικόνα κλίμακας του γκρίζου έχει n διαβαθμίσεις, το μέγεθος του κάθε στοιχείου θα είναι (2n-1)bits.
  • Οι έγχρωμες εικόνες συντίθεται από μια τριάδα βασικών χρωμάτων, άρα απαιτούνται (3*(2n-1))bits για εικόνα με n χρώματα.

Επιπλέον, το μέγεθος του πίνακα εξαρτάται και από την πυκνότητα (density) που ορίζεται ως ο αριθμός των εικονοστοιχείων ανά ίντσα προς μια κατεύθυνση. Αυτό το μέγεθος ονομάζεται και ανάλυση (resolution) και μετριέται σε dpi (dots per inch). Η ανάλυση που επιλέγεται κατά την σύλληψη σχετίζεται άμεσα από την μονάδα εξόδου που θα χρησιμοποιηθεί και συνήθως είναι λίγο μεγαλύτερη αυτής ώστε να εξοικονομείται χώρος χωρίς να αλλοιώνεται η ποιότητα. Τυπικές τιμές είναι 70dpi για τις οθόνες, 600dpi για τους εκτυπωτές laser και 1000dpi για offset printing.

Εκτός από scanners, στη σύλληψη εικόνων υψηλής ανάλυσης[1][1] (2,200´1,700) χρησιμοποιούνται και κάμερες. Ένας άλλος τρόπος σύλληψης είναι από video με χρήση ψηφιοποιητή (video digitiser) ή ενός frame grabber.

Συμπίεση

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

Ανάλυση

(dpi)

Διτονική

(ΜΒ)

Κλίμακας του Γκρίζου με

4-6 bits/pixel

(ΜΒ)

Έγχρωμη με

32-128 bits/pixel

(ΜΒ)

200

0.48

1.9-7.7

15-61

300

1.09

4.4-17.4

35-140

400

1.93

7.7-30.9

62-247

Πίνακας 5-1. Απαιτήσεις αποθηκευτικού χώρου
 για σελίδα Α4 χωρίς συμπίεση

Στην ειδική περίπτωση εικόνων που προέρχονται από τη σύλληψη εγγράφων, μπορεί να μειωθεί το μέγεθος της εικόνας χωρίς συμπίεση. Αυτό επιτυγχάνεται αν μετατραπεί το κείμενο σε κώδικα ASCII. Αυτή η μετατροπή προϋποθέτει τεχνικές OCR και παρουσιάζει επιπλέον το πλεονέκτημα ότι το κείμενο που εξάγεται μπορεί να υποστεί περαιτέρω επεξεργασία. Σε αντιστοιχία με το κείμενο, εικόνες που περιέχουν γραμμικά σχέδια μπορούν να παρασταθούν πιο αποτελεσματικά διανυσματοποιώντας τα γραφικά αντικείμενα που υπάρχουν σε αυτή. Αυτό σημαίνει αναπαράσταση των γεωμετρικών σχημάτων της εικόνας με μαθηματικές εκφράσεις. Εικόνες που περιέχουν απλά σχήματα μπορούν να παρασταθούν πολύ αποτελεσματικά με αυτή τη μέθοδο (μέχρι και 200:1 βελτίωση). Δεν συμβαίνει όμως το ίδιο για πολύπλοκες εικόνες.

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

Το πρότυπο JPEG

Το JPEG είναι ένα πρότυπο του ISO το οποίο σχεδιάστηκε από την ομάδα Joint Photographic Expert Group σε συνεργασία με την Διεθνή Ένωση Τηλεπικοινωνιών (International Telecommunication Union, ITU-TS). Πρόκειται ίσως για το σημαντικότερο και πιο αποτελεσματικό πρότυπο συμπίεσης εικόνας, το οποίο κερδίζει συνεχώς έδαφος στις εφαρμογές πολυμέσων σε όλες τις πλατφόρμες. Γι’ αυτόν τον λόγο, θα σταθούμε στις γενικές αρχές του λίγο παραπάνω. Με δυο λόγια θα μπορούσαμε να περιγράψουμε το JPEG ως εξής:

To JPEG είναι ένα πρότυπο συμπίεσης εικόνων συνεχούς τόνου, είτε έγχρωμων είτε κλίμακας του γκρίζου. Χρησιμοποιεί ένα συνδυασμό τεχνικών διακριτού συνημιτονικού μετασχηματισμού Fourier, κβαντοποίησης, περιορισμού των επαναλαμβανόμενων χαρακτήρων και κωδικοποίησης Huffman και υποστηρίζει διάφορους τρόπους λειτουργίας. Μπορεί να έχει απώλειες με διάφορους συνδυασμούς λόγου συμπίεσης-ποιότητας ή και να λειτουργεί  χωρίς απώλειες.

Το JPEG έχει τέσσερις ρυθμούς λειτουργίας:

  • Διαδοχική κωδικοποίηση (sequential encoding)

          Σε αυτόν το ρυθμό λειτουργίας το JPEG λειτουργεί με απώλειες και γίνεται μια μόνο σάρωση της εικόνας από αριστερά προς τα δεξιά και από πάνω προς τα κάτω. Πρόκειται για τον συνηθέστερο ρυθμό λειτουργίας.

  • Προοδευτική κωδικοποίηση (progressive encoding)

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

  • Κωδικοποίηση χωρίς απώλειες (lossless encoding)

          Αντίθετα με τις υπόλοιπες περιπτώσεις, το αποτέλεσμα αυτού του τρόπου συμπίεσης είναι πλήρως αντιστρέψιμο.

  • Ιεραρχική κωδικοποίηση (hierarchical encoding)

          Η κωδικοποίηση συνίσταται από διάφορα επίπεδα ευκρίνειας, τα οποία μπορούν να αποκωδικοποιηθούν ξεχωριστά.

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

  • Προετοιμασία των τμημάτων (data blocks)
    Όπως έχουμε δει, η εικόνα μπορεί να συντεθεί με διάφορους τρόπους. Κάθε pixel μπορεί να αντιστοιχεί στην τετράδα RGB ή YUV (Ευρωπαϊκή τηλεόραση) ή YIQ (Αμερικανική και Ιαπωνική τηλεόραση) και σε άλλες. Επίσης γνωρίζουμε ότι κάποιες από τις συνιστώσες αυτές είναι μικρότερης σημασίας, οπότε μπορούν να δειγματοληφθούν με μικρότερη συχνότητα. Το πρότυπο JPEG μπορεί να χειριστεί μέχρι και 255 χρωματικές συνιστώσες. Οι μετασχηματισμοί που ακολουθούν στο επόμενο βήμα δεν εφαρμόζονται σε ολόκληρη την εικόνα αλλά σε τμήματα μεγέθους 8´8pixels. Αν για παράδειγμα έχουμε μια εικόνα 640´480pixels που παριστάνεται με χρήση της τριάδας YUV θα έχουμε: έναν πίνακα 640´480 για τη συνιστώσα Υ (luminance) που θα χωριστεί σε 4800 τμήματα, δύο πίνακες 320´240 για τις δυο χρωματικές συνιστώσες (υπετέθει δειγματοληψία με το 1/4 της συχνότητας της φωτεινότητας) που θα χωριστούν σε 1200 τμήματα.
  •  Σε κάθε ένα από τα τμήματα που προέκυψαν από το προηγούμενο βήμα εφαρμόζεται ο ΔΣΜΦ. Στο πεδίο της συχνότητας, και εφόσον ικανοποιείται η προϋπόθεση για εικόνες συνεχούς τόνου, οι συντελεστές χαμηλών συχνοτήτων είναι πιο σημαντικοί. Πριν γίνει η κωδικοποίηση, οι συντελεστές του ΔΣΜΦ κανονικοποιούνται διαιρώντας τους με κάποιες προκαθορισμένες τιμές που περιέχονται στον πίνακα êâáíôïðïßçóçò (quantization table). Οι τιμές αυτές μεγαλώνουν όσο μεγαλώνει η συχνότητα, επιτυγχάνοντας με αυτόν τον τρόπο την επικέντρωση του ενδιαφέροντος στις χαμηλές συχνότητες. O συντελεστής μηδενικής συχνότητας κάθε τμήματος δεν επηρεάζεται καθόλου από την κανονικοποίηση (τιμή πίνακα κβαντοιποίησης=0) και ονομάζεται DC συντελεστής. Στην συνέχεια ακολουθεί η κωδικοποίηση των κανονικοποιημένων συντελεστών του ΔΣΜΦ με την τεχνική DPCM. Το προβλεπόμενο λάθος για κάθε τμήμα  είναι η DC τιμή του προηγούμενου τμήματος.
  • Κωδικοποίηση εντροπίας: περιορισμός των επαναλαμβανόμενων χαρακτήρων, κωδικοποίηση Huffman
    Οι κβαντοποιημένες τιμές μπαίνουν στη σειρά χρησιμοποιώντας το σχήμα zig-zag που έχει ως στόχο την μεγιστοποίηση της πιθανότητας εμφάνισης ίδιων γειτονικών τιμών. Τέλος, εφαρμόζεται η κωδικοποίηση Huffman ή μια πιο πολύπλοκη μορφή κωδικοποίησης πηγής που ονομάζεται αριθμητική κωδικοποίηση.

Βασικό χαρακτηριστικό του JPEG είναι ότι το αποτέλεσμα της συμπίεσης μπορεί να διαφέρει ανάλογα με τις απαιτήσεις που έχουμε για την ποιότητα της εικόνας και το λόγο συμπίεσης. Προφανώς, όσο μεγαλύτερος είναι ο λόγος συμπίεσης τόσο χειρότερη είναι η εικόνα. Τυπικές τιμές για το λόγο συμπίεσης είναι:

  • 10:1 έως 20:1 - Υψηλή ποιότητα εικόνας με μικρή ή μη παρατηρήσιμη διαφορά από την αρχική εικόνα
  • 30:1 έως 50:1 - Μέτρια ποιότητα
  • 60:1 έως 100:1 - Κακή ποιότητα

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

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

Fractal Image Compression (Απειροστική Συμπίεση Εικόνας)

ΓΕΝΙΚΑ ΣΤΟΙΧΕΙΑ ΣΧΕΤΙΚΑ ΜΕ ΤΗΝ ΑΠΕΙΡΟΣΤΙΚΗ ΣΥΜΠΙΕΣΗ EΙΚΟΝΑΣ

Είναι μια καινούρια και πολλά υποσχόμενη τεχνολογία. Το αν είναι ανώτερη της συμπίεσης JPEG είναι ανοιχτό σε διάλογο.

  1. Είναι μέθοδος συμπίεσης χωρίς απώλειες.
  2. Τα απειροστικά τμήματα στην απειροστική συμπίεση εικόνας είναι επαναλαμβανόμενα συστήματα συναρτήσεων ( Iterated Function Systems).
  3. Είναι μια μορφή κβαντικού διανύσματος, κάτι που χρειάζεται ειδική ορολογία για να καταλάβουμε.
  4. Η αύξηση της ανάλυσης είναι ένα πανίσχυρο σημείο της μεθόδου αλλά δεν είναι κάτι το μαγικό που πετυχαίνει συμπίεση 1000:1.
  5. Η συμπίεση είναι αργή, η αποσυμπίεση είναι γρήγορη.

  6. Η τεχνολογία είναι πατενταρισμένη.

  7. Τα παραπάνω δίνουν μια γενική εικόνα. Για όποιον θέλει να εμβαθύνει, ακολουθεί ανάλυση.

ΣΥΝΤΟΜΗ ΙΣΤΟΡΙΚΗ ΑΝΑΔΡΟΜΗ ΓΙΑ ΤΗΝ ΑΠΕΙΡΟΣΤΙΚΗ ΣΥΜΠΙΕΣΗ ΕΙΚΟΝΑΣ

Η γέννηση της απειροστικής γεωμετρίας (ή μάλλον η αναγέννηση), αποδίδεται συνήθως στον μαθηματικό της IBM Benoit B. Madelbrot με την έκδοση του βιβλίου «Η Απειροστική Γεωμετρία της Φύσης» («The Fractal Geometry of Nature»).

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

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

Δεν πέρασε και πολύ καιρός από τότε που οι μαθηματικοί αναρωτήθηκαν εάν υπάρχει κάποια ενότητα μέσα σε όλους αυτούς τους διαχωρισμούς. Υπάρχει, όπως απέδειξε ο John Hutchinson το 1981. Είναι ο κλάδος των μαθηματικών που τώρα είναι γνωστός σαν Θεωρία των Επαναλαμβανόμενων Συναρτήσεων. Αργότερα, την ίδια δεκαετία, ο Michael Barnsley, ένας κορυφαίος ερευνητής από το Georgia Τech, έγραψε το διάσημο βιβλίο «Απειροστικά Oρια Παντού» («Fractals Everywhere»). Το βιβλίο παρουσιάζει με μαθηματικά τα επαναλαμβανόμενα συστήματα συναρτήσεων (IFS) και αποδεικνύει ένα θεώρημα γνωστό σαν το θεώρημα του Collage. Το θεώρημα αυτό λέει πώς πρέπει να είναι ένα IFS προκειμένου να αναπαριστά μια εικόνα.

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

Ο Barnsley όμως, οπλισμένος με το θεώρημα του Collage, νόμιζε πως το έλυσε κι αφού έκανε αίτηση, κατάφερε να πάρει μια πατέντα λογισμικού. Η ανακοίνωση της επιτυχίας του έγινε από τον ίδιο τον Ιανουάριο του 1988 στο τεύχος του περιοδικού BYTE. Στο άρθρο αυτό δεν αναφερόταν το αντίστροφο πρόβλημα, αλλά περιείχε ορισμένες εικόνες συμπιεσμένες σε βαθμό μεγαλύτερο από 10.000:1. Κι όμως, αυτό δεν ήταν καινοτομία. Οι εικόνες είχαν πάρει κάποιο όνομα όπως «Μαύρο Δάσος», αλλά ήταν όλες τεχνικά κατασκευασμένες. Η πατέντα του Barnsley κατάντησε να αποκαλείται χλευαστικά, «Ο αλγόριθμος του μεταπτυχιακού φοιτητή» («Graduate Student Algoritm»).

Αναλυτικά, ο αλγόριθμος αυτός λέει :

  • Bρείτε έναν μεταπτυχιακό φοιτητή.
  • Δώστε στον φοιτητή μία εικόνα.
  • Κι ένα δωμάτιο με ένα σταθμό εργασίας γραφικών.
  • Κλειδώστε την πόρτα.
  • Περιμένετε μέχρι ο φοιτητής να έχει αντιστρέψει μηχανικά την εικόνα.
  • Ανοίξτε την πόρτα.

Οι προσπάθειες να αυτοματοποιηθεί αυτή η διεργασία, έχουν ελάχιστη επιτυχία. Όπως παραδέχθηκε και ο ίδιος ο Barnsley το 1988: «Σύνθετες έγχρωμες εικόνες χρειάζονται σχεδόν 100 ώρες η κάθε μία για να κωδικοποιηθούν και 30 λεπτά για να αποκωδικοποιηθούν στο Massomp (σταθμός εργασίας με δύο επεξεργαστές)”. Αυτό σημαίνει 100 ώρες με κάποιο άτομο να επιβλέπει τη διαδικασία.

Η ειρωνεία είναι ότι εκείνος που έβγαλε άχρηστο τον «αλγόριθμο του μεταπτυχιακού» ήταν ένας από τους φοιτητές που έκαναν το διδακτορικό τους στον Barnsley. Το Μάρτιο του 1988, σύμφωνα με τον Barnsley, κατέληξε σε ένα μορφοποιημένο τρόπο για την απεικόνιση εικόνων που ονομάστηκε «Καταμερισμένα Επαναλαμβανόμενα Συστήματα Συναρτήσεων» («Partitioned Iterated Function Systems» - PIFS). Ο Barnsley έκανε αίτηση και πήρε μια δεύτερη πατέντα σε ένα αλγόριθμο που μπορεί αυτόματα να μετατρέψει μια εικόνα σε PIFS. Για να πάρει το διδακτορικό του, ο Arnaud Jacquin υλοποίησε τον αλγόριθμο σε λογισμικό, του οποίου μια περιγραφή υπάρχει στην εργασία του με τίτλο «Κωδικοποίηση εικόνας βασισμένη στην απειροστική θεωρία των επαναλαμβανόμενων συστολικών μετασχηματισμών εικόνας». Ο αλγόριθμος δεν ήταν πολύ έξυπνος ούτε πολύ γρήγορος, αλλά ήταν πλήρως αυτοματοποιημένος. Αυτό είχε και τις συνέπειές του: η υπόσχεση για συμπίεση 10.000:1 είχε χαθεί. Μία 24bit εικόνα μπορούσε τυπικά να συμπιεσθεί από 8:1 μέχρι 50:1 και να εξακολουθούσε να φαίνεται “αρκετά καλά”. Ωστόσο, όλα τα σύγχρονα προγράμματα απειροστικής συμπίεσης είναι βασισμένα στην εργασία του Jacquin.

Αυτό δε σημαίνει ότι υπάρχουν πολλά προγράμματα απειροστικής συμπίεσης διαθέσιμα. Αντιθέτως, είναι πολύ λίγα. Η εταιρία Iterated Systems διαθέτει τους μόνους εμπορικούς συμπιεστές/αποσυμπιεστές, ένα πρόγραμμα για MS-Windows, το οποίο ονομάζεται “Images Incorporated”. Υπάρχει επίσης κι ένας ολοένα αυξανόμενος αριθμός ακαδημαϊκών προγραμμάτων που είναι δωρεάν διαθέσιμα, αλλά είναι μάλλον δύσχρηστα και αμφιβόλου ποιότητας.

Η έλλειψη αυτή οφείλεται κυρίως στην πολιτική της εταιρίας Iterated Systems, που δεν επιτρέπει να διατίθεται η τεχνογνωσία της στη συμπίεση, αν και πουλάνε κάποιο Windows DLL αρχείο για τους προγραμματιστές. Βέβαια δεν ισχύει το ίδιο με την ατομική μελέτη κι ανάπτυξη της απειροστικής συμπίεσης από άλλους. Για αυτό αναμένεται η τεχνική της απειροστικής συμπίεσης να γίνει σταδιακά όλο και πιο γνωστή.

ΜΙΑ ΠΙΟ ΚΟΝΤΙΝΗ ΜΑΤΙΑ

Τα απειροστικά τμήματα που χρησιμοποιούνται στην απειροστική συμπίεση της εικόνας δεν είναι αυτά που γνωρίζουμε από την ανάλυση, αλλά από τη θεωρίας της επαναλαμβανόμενης συνάρτησης. Ο μαθηματικός Heinz-Otto Peitgen μας δίνει μια ωραία εισαγωγή στη θεωρία αυτή χρησιμοποιώντας μεταφορικά ένα αντιγραφικό μηχάνημα πολλαπλής ελάττωσης (Multiple Reduction Copying Machine). Το MRCM υποτίθεται πως είναι ένα απλό αντιγραφικό μηχάνημα, με τις εξής διαφορές :

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

Κάθε μία ρύθμιση των φακών μειώνει το μέγεθος του αρχικού.

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

            Το πρώτο είναι αυτό που κάνει το IFS να είναι σύστημα. Το τρίτο είναι αυτό που το κάνει επαναλαμβανόμενο. Όσο για το δεύτερο, υπονοεί ότι οι συναρτήσεις μιας επαναλαμβανόμενης συνάρτησης είναι συστολικές.

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

 Αυτό το IFS αποτελείται από τρεις συνθετικούς μετασχηματισμούς ( τρεις διαφορετικοί φακοί στο μηχάνημα MRCM ). Κάθε ένας απ’ αυτούς συρρικνώνει το αρχικό κατά 2, και μετά μεταφράζει το αποτέλεσμα σε μια νέα τοποθεσία. Μπορεί προαιρετικά να ρυθμίσει και να μετακινήσει τη φωτεινότητα του ορθογωνίου, με ένα τρόπο παρόμοιο με αυτό της ρύθμισης που κάνουμε στη φωτεινότητα και τη διαύγεια της τηλεόρασης.

ΑΠΩΛΕΙΑ ΚΛΙΜΑΚΑΣ ΚΑΙ ΑΥΞΗΣΗ ΤΗΣ ΑΝΑΛΥΣΗΣ

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

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

Πρακτικά, αυτό σημαίνει ότι αν μεγεθύνουμε μία απειροστική εικόνα, θα εξακολουθεί να δείχνει “όπως πρέπει” χωρίς τα φαινόμενα που εμφανίζει η μεγέθυνση των εικονοστοιχείων. Η σημαντικότητα των παραπάνω έχει δημιουργήσει μερικές διαφωνίες και γι’ αυτό θα πρέπει να πούμε τα παρακάτω :

Η Iterated Systems υποστηρίζει τα εξής: Πάρτε ένα πορτραίτο που είναι, ας πούμε, μια ασπρόμαυρη εικόνα κι έχει μέγεθος 250x250 pixel, με ένα byte ανά pixel. Την περνάτε από το δικό της πρόγραμμα κι έχετε ένα αρχείο μεγέθους 2500 byte (συντελεστής συμπίεσης = 25:1). Μεγεθύνετε τώρα τα μαλλιά του ατόμου της φωτογραφίας τέσσερις φορές. Τι βλέπετε; Μια εικόνα που μοιάζει πάλι με μαλλιά. Επομένως, είναι σα να έχετε μια εικόνα μεγέθους 1000x1000. Άρα και ο συνολικός συντελεστής συμπίεσης που καταφέρατε να πάρετε είναι 25x16=400.

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

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

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

ΤΟ ΠΡΟΒΛΗΜΑ ΤΑΧΥΤΗΤΑΣ

Η ουσία της διαδικασίας της συμπίεσης είναι ο συνδυασμός κάθε μπλοκ περιοχής σε ένα κυρίαρχο μπλοκ έτσι ώστε η διαφορά με το αρχικό να είναι ελάχιστη. Αυτό χρειάζεται πολύ ψάξιμο.

Στην πραγματικότητα, δεν υπάρχει κανόνας που να λέει ότι τα μπλοκ περιοχής πρέπει να είναι τετράγωνα, ούτε καν ορθογώνια. Αυτό είναι μια απλή παραδοχή που κάναμε για να κατανοήσουμε το πρόβλημα. Γενικά, η μέθοδος για να βρεθούν καλά PIFS για οποιαδήποτε εικόνα, περιλαμβάνει τα πέντε παρακάτω θέματα :

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

Πολλές πιθανές λύσεις υπάρχουν για κάθε θέμα. Οι επιλογές που πρότεινε ο Jacquin στην εργασία του είναι :

Ένα τετράγωνο δύο επιπέδων με 8x8 εικονοστοιχεία για τα μπλοκ μεγάλων περιοχών και 4x4 για εκείνα των μικρών.

Τα κυρίαρχα μπλοκ είναι μεγέθους 16x16 και 8x8 pixels με βήμα δείγματος μεγέθους 4 (τέσσερα). Οι οκτώ ισομετρικές συμμετρίες επεκτείνουν το κυρίαρχο μπλοκ σε ένα εικονικό μπλοκ οκτώ φορές μεγαλύτερο.

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

Χρησιμοποιείται το σφάλμα ελαχίστου τετραγώνου.

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

Η σημαντικότητα της κατηγοριοποίησης μπορεί να φανεί αν υπολογίσουμε το συνολικό μέγεθος του κυρίαρχου μπλοκ. Ας υποθέσουμε ότι η εικόνα χωρίζεται σε μπλοκ 4x4. Μια εικόνα 256x256 περιέχει συνολικά (256-8+1)2 = 62.001 διαφορετικά 8x8 κυρίαρχα μπλοκ. Συμπεριλαμβάνοντας και τις 8 ισομετρικές συμμετρίες αυξάνει το μέγεθος αυτό σε 496.008. Υπάρχουν (256-4+1)2 = 64.009 4x4 μπλοκ περιοχών, που μας κάνουν ένα μέγιστο 31.748.976.072 πιθανών συνδυασμών να εξεταστούν. Ακόμα και σε γρήγορους σταθμούς εργασίας το ψάξιμο είναι απελπιστικά αργό. Το να αυξηθεί η ταχύτητα του ψαξίματος είναι η κύρια πρόκληση που έχει να αντιμετωπίσει η απειροστική συμπίεση εικόνας.

ΟΜΟΙΟΤΗΤΕΣ ΜΕ ΤΗΝ ΔΙΑΝΥΣΜΑΤΙΚΗ ΚΒΑΝΤΟΠΟΙΗΣΗ (VECTOR QUANTIZATION (VQ))

Για την κοινότητα της VQ, ένα διάνυσμα είναι ένα μικρό ορθογώνιο από pixels. Η βασική υπόθεση της διανυσματικής κβαντοποίησης είναι ότι μερικά πρότυπα εμφανίζονται πολύ πιο συχνά από άλλα. Eτσι η έξυπνη ιδέα είναι να αποθηκεύσουμε λίγα από αυτά τα πρότυπα σε ξεχωριστό αρχείο που ονομάζουμε κωδικό-βιβλίο (codebook). Το πως ακριβώς θα φτιαχτεί ένα τέτοιο βιβλίο είναι ολόκληρη ιστορία. Το βασικό είναι ότι σε κάθε στοιχείο του βιβλίου (κάθε κυρίαρχο μπλοκ) έχει δοθεί ένας αριθμός. Τότε, κάθε εικόνα χωρίζεται σε έναν απλό πίνακα. Κάθε στοιχείο του πίνακα (κάθε μπλοκ περιοχής) αναπαριστάται στο βιβλίο της κωδικοποίησης. Το να αποσυμπιεστεί ένα VQ αρχείο σημαίνει να φτιάξουμε την εικόνα αντιστοιχώντας τα νούμερα σε αυτά του βιβλίου. Η ομοιότητα με την απειροστική είναι προφανής, με μερικές σημαντικές διαφορές.

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

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

ΣΥΝΤΕΛΕΣΤΕΣ ΣΥΜΠΙΕΣΗΣ

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

Για ευκολία, και προκειμένου να μπορέσουμε να κάνουμε σύγκριση με το JPEG, ας υποθέσουμε ότι μια εικόνα μεγέθους 256x256x8 χωρίζεται σε μπλοκ των 8x8. Υπάρχουν 1024 μπλοκ περιοχής και κατά συνέπεια 1024 μετασχηματισμοί για να αποθηκευτούν. Πόσα bits χρειάζονται για το καθένα;

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

Η x θέση του κυρίαρχου μπλοκ           8     6

Η y θέση του κυρίαρχου μπλοκ           8     6

Η ρύθμιση της φωτεινότητας                8     5

Η αντιστάθμιση της φωτεινότητας        8     6

Ο δείκτης συμμετρίας                           3     3

Σύνολο :                                              35    26   bits

Στην πρώτη στήλη, ένα byte δίνεται σε κάθε αριθμό εκτός από το δείκτη συμμετρίας. Το μέγιστο όριο συμπίεσης είναι επομένως (8x8x8)/35=14,63. Στη δεύτερη στήλη, τα κυρίαρχα μπλοκ έχουν περιοριστεί στις προηγούμενες συντεταγμένες μείον δυο. Επίσης, πειράματα έχουν δείξει ότι 5 bits για τη ρύθμιση και 6 για την αντιστάθμιση εξακολουθούν να έχουν καλά οπτικά αποτελέσματα. Έτσι, το όριο της συμπίεσης είναι τώρα 19,69 αξιοσημείωτο αλλά όχι εξωπραγματικό.

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

ΠΟΙΟΤΗΤΑ : ΑΠΕΙΡΟΣΤΙΚΟΤΗΤΑ ΕΝΑΝΤΙΟΝ JPEG

Η μεγάλη ειρωνεία για την επιτροπή κωδικοποίησης είναι ότι μεγάλη φροντίδα δίνεται προκειμένου να μετρηθεί ακριβώς και να προσδιορισθεί το ποσοστό λάθους σε μία συμπιεσμένη εικόνα, και γίνεται μεγάλη προσπάθεια προκειμένου να μειωθεί το λάθος που μετριέται το οποίο πολύ συχνά είναι αμφίβολο. Αυτές οι μετρήσεις περιλαμβάνουν λόγο σήματος προς θόρυβο, μέθοδο ελαχίστων τετραγώνων και απόλυτη τιμή του λάθους. Ένα απλό παράδειγμα είναι η συνεχής μετακίνηση (shift): προσθέτουμε την τιμή 10 σε κάθε pixel. Σταθερές μετρήσεις λάθους υποδεικνύουν μεγάλη παραμόρφωση, αλλά η εικόνα έχει γίνει ελάχιστα πιο φωτεινή.

Με σεβασμό σε αυτές τις αμφίβολες μετρήσεις λάθους, και με το φόβο της υπεραπλούστευσης, τα αποτελέσματα αποκαλύπτουν τα ακόλουθα :

Για μικρούς συντελεστές συμπίεσης το JPEG είναι καλύτερο, για υψηλούς συντελεστές η απειροστική κωδικοποίηση είναι καλύτερη. Το διαχωριστικό σημείο διαφέρει, αλλά συνήθως είναι γύρω στο 40:1. Η τιμή αυτή προμηνύει ανωτερότητα του JPEG αφού έτσι κι αλλιώς πέρα από αυτό το βαθμό συμπίεσης οι εικόνες έχουν συνήθως τέτοια αταξία που δεν αξίζει να χρησιμοποιηθεί.

Υποστηρικτές της απειροστικής συμπίεσης υποστηρίζουν ότι ο λόγος σήματος προς θόρυβο δεν είναι καλό μέτρο για τη μέτρηση του λάθους και ότι η παραμορφωμένη εικόνα που δίνει είναι πολύ πιο “φυσική”, από τα τετράγωνα μπλοκ του JPEG, τόσο στις χαμηλές όσο και στις υψηλές αναλύσεις. Αυτό είναι ένα λογικό επιχείρημα αλλά σε καμία περίπτωση δεν είναι αποδεκτό παγκόσμια. Iσως αυτό που χρειάζεται η επιτροπή κωδικοποίησης να είναι ένας τρόπος που θα μετρά με ακρίβεια και αντικειμενικότητα την εντύπωση που δίνει το σήμα (εδώ η εικόνα) στον άνθρωπο. Μέχρι τότε τα μάτια σας είναι οι καλύτεροι κριτές.



[1][1] Ο όρος ανάλυση (resolution) έχει επιπλέον τη σημασία: το μέγεθος μιας εικόνας σε εικονοστοιχεία.