Διαφορική ή προβλεπτική κωδικοποίηση

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

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

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

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

Διακρίνουμε τρεις μορφές διαφορικής κωδικοποίησης: απλή διαφορική παλμοκωδική διαμόρφωση (differential pulse code modulation-DPCM), δέλτα διαμόρφωση (delta modulation) και προσαρμοστική διαφορική παλμοκωδική διαμόρφωση (adaptive pulse code modulation-ADPCM).

Απλή διαφορική παλμοκωδική διαμόρφωση

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

Δέλτα διαμόρφωση

Η δέλτα διαμόρφωση αποτελεί μια ειδική μορφή της DPCM. Ο μηχανισμός πρόβλεψης είναι ακριβώς ο ίδιος. Η διαφορά έγκειται στον τρόπο κωδικοποίησης των διαφορών:

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

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

Σχήμα 4-8. Τρία είδη διαφορικής κωδικοποίησης

Προσαρμοστική διαφορική παλμοκωδική διαμόρφωση

Η προσαρμοστική διαφορική παλμοκωδική διαμόρφωση (ADPCM) είναι μια πιο σύνθετη μορφή DPCM.

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

Κατά τα άλλα, όπως και στην απλή DPCM, μόνο η διαφορά μεταξύ της πραγματικής και της προβλεπόμενης τιμής κάθε δείγματος μεταδίδεται.

Διανυσματική κβαντοποίηση

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

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

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

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

Άρα η βασική αρχή αυτής της μεθόδου είναι:

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

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

Σχήμα 4-9. Η βασική αρχή της διανυσματικής κβαντοποίησης

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

Σχήμα 4-10. Η βασική αρχή της διανυσματική κβαντοποίησης με μετάδοση
όρου λάθους

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

Συμπίεση με fractals

Θα ολοκληρώσουμε την παρουσίαση των βασικών τεχνικών συμπίεσης με λίγα λόγια για μια πιο νέα τεχνική συμπίεσης, την συμπίεση με χρήση fractals.

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

Οι πρώτες χρήσεις των fractals ήταν στη δημιουργία εικόνων. Τα τελευταία χρόνια μελετώνται και τρόποι εφαρμογής αυτής της θεωρίας για την συμπίεση εικόνων. Η βασική αρχή αυτών των μεθόδων είναι η εξής:

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

Μπορούμε να παρατηρήσουμε κάποια ομοιότητα με την μέθοδο της διανυσματικής κβαντοποίησης. Το σύνολο των μαθηματικών μετασχηματισμών παίζει το ρόλο ενός εικονικού λεξικού (virtual code-book), που εξαρτάται άμεσα από την εικόνα που συμπιέζεται και πρέπει να μεταδίδεται ολόκληρο από τη διαδικασία συμπίεσης σε αυτήν της αποσυμπίεσης. Χαρακτηρίζεται εικονικό, γιατί προκύπτει με βάση τους μετασχηματισμούς fractal κατά το στάδιο της αποσυμπίεσης.

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

Συμμετρία των τεχνικών συμπίεσης

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

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

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