next up previous
Next: Υλοποίηση της κωδικοποίησης - Up: mythesis Previous: Σύστημα αναγνώρισης φωνής

Subsections

Κωδικοποίηση φωνής

Εισαγωγή

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

Στο Κεφάλαιο 1 είδαμε ότι το front-end παράγει τις παραμέτρους της φωνής με μορφή ακουστικών διανυσμάτων, τα οποία χρησιμοποιούνται από τα ακουστικά μοντέλα για να βρεθεί η βέλτιστη ακολουθία λέξεων από τον αναγνωριστή. Αναφέρθηκε ότι η χρήση διανυσματικού κβαντισμού επιτυγχάνεται με το κβαντισμό των διανυσμάτων εισόδου του front-end στα πρότυπα ακουστικά διανύσματα αναφοράς που περιέχονται στο codebook. Ειπώθηκε επίσης, ότι η χρήση του διανυσματικού κβαντισμού επιτρέπει τη χρησιμοποίηση ακουστικών μοντέλων που προκύπτουν από διακριτοποίηση μοντέλων με μείγματα συνεχών κατανομών, τα οποία δημιουργήθηκαν ειδικά για το σκοπό αυτής της εργασίας. Ο συνδυασμός του διανυσματικού κβαντισμού με χρήση των παραπάνω μοντέλων, έχει σαν αποτέλεσμα τη συμπίεση του σήματος της φωνής, αλλά και την επιτάχυνση της αναγνώρισης.

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

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

Πηγές πληροφορίας και κωδικοποίηση

Τα συστήματα επικοινωνιών σχεδιάζονται για να μεταδίδουν πληροφορία. Σε όλα αυτά τα συστήματα υπάρχει μια πηγή που παράγει την πληροφορία και σκοπός του συστήματος είναι να μεταδώσει την έξοδο της πηγής στον προορισμό της. Όλοι έχουμε εμπειρία από αυτό το μοντέλο : εκπομπές ραδιοφωνικού σήματος, τηλεόρασης, μετάδοση φωνής κ.τ.λ. Προκειμένου να μπορούμε να κάνουμε ανάλυση απόδοσης ενός τέτοιου μοντέλου όμως, χρειάζονται τα κατάλληλα εργαλεία : ποσοτικές μετρικές και κατάλληλα μαθηματικά μοντέλα. Στην ανάπτυξη των τελευταίων βοήθησαν καταλυτικά οι Hartley, Nyquist $\&$ Shannon.

Η πηγή πληροφορίας παράγει έξοδο που ο προορισμός της δεν την γνωρίζει από πριν - η πληροφορία έχει να κάνει με τι γνώση για κάτι. Η έξοδος της πηγής είναι μια μη-προβλέψιμη, χρονικά μεταβαλλόμενη διαδικασία, άρα μπορεί να μοντελοποιηθεί σαν μια τυχαία(στοχαστική) διαδικασία. Το χαρακτηριστικό των πηγών αυτών, είναι ότι μπορούν να μοντελοποιηθούν σαν bandlimited διαδικασίες. Για παράδειγμα, το σήμα της φωνής έχει σχεδόν όλη την ισχύ του στην μπάντα 300-3400Hz. Εκμεταλλευόμενοι αυτό το γεγονός, μπορούμε να κάνουμε δειγματοληψία σε συχνότητα Nyquist και πλέον θα έχουμε να κάνουμε με διακριτού χρόνου στοχαστικές διαδικασίες.

Μοντέλο πληροφορίας

Ένα απλό μοντέλο πληροφορίας είναι η πηγή να μοντελοποιείται από μια διακριτού χρόνου στοχαστική διαδικασία $\{X_{i}\}_{i=-\infty}^\infty$. Το αλφάβητο στο οποίο ορίζονται οι τυχαίες μεταβλητές $X_{i}$ μπορεί να είναι διακριτές ή συνεχείς (π.χ. δειγματοληπτημένη φωνή), ενώ οι στατιστικές ιδιότητες της διαδικασίας καθορίζονται από την ίδια τη πηγή. Για τη φωνή, ένα ικανοποιητικό τέτοιο μοντέλο, είναι μια διακριτού χρόνου και πλάτους τυχαία διαδικασία, όπου όλα τα $X_{i}$ παράγονται ανεξάρτητα (διαδικασία χωρίς μνήμη-memoryless process) και με την ίδια κατανομή.

Ας υποθέσουμε ότι η $X$ παίρνει τιμές από ένα σύνολο $A= \{a_{1},a_{2},...,a_{M}\}$ με πιθανότητες $p_{i} = p(X=a_{i})$, $i=1,2...M$. Μια παρατήρηση για την ``ποιοτική'' μέτρηση της πληροφορίας, είναι ότι αυτή πρέπει να μειώνεται όσο αυξάνει η πιθανότητα παρατήρησης του συμβόλου εξόδου. Για παράδειγμα, η είδηση ότι μέσα στον Ιούλιο έχουμε βροχή περιέχει περισσότερη πληροφορία από την είδηση ότι έχουμε ηλιοφάνεια. Μια άλλη παρατήρηση, είναι ότι μια μικρή αλλαγή στη πιθανότητα, έχει μικρή επίπτωση στο ποσό της πληροφορίας. Με άλλα λόγια, μια μετρική πληροφορίας θα πρέπει να είναι μια συνεχής και μειούμενη συνάρτηση της πιθανότητας της εξόδου της πηγής.

Μια τέτοια ``συμπεριφορά'' παρέχεται από την : $-log(p_{i})$ που ονομάζεται self-information. Η εντροπία μιας πηγής αποτελεί μια καλή μετρική σύμφωνα με τις παραπάνω παρατηρήσεις και ορίζεται από τη σχέση : $H(X) = - \sum_{i=1}^N p_{i}logp_{i}$ Η εντροπία της πηγής, μας δίνει ένα αρκετά ακριβές όριο του ρυθμού στον οποίο μπορεί να συμπιεστεί η έξοδος της πηγής, για ικανή ανακατασκευή του σήματος χωρίς απώλειες. Αυτό αποδεικνύεται από το θεώρημα κωδικοποίησης πηγής του Shannon, σύμφωνα με το οποίο για να έχουμε ικανή ανακασκευή του σήματος χωρίς απώλειες, θα πρέπει να ισχύει : $R > H$, με $R$ το ρυθμό μετάδοσης (συμπίεση).

Τεχνικές που ``σέβονται'' το παραπάνω κριτήριο, δηλαδή κωδικοποίηση χωρίς απώλειες, (ονομάζονται lossles coding ή και entropy coding) είναι η κωδικοποίηση Huffman και Ziv-Lempel. Συχνά όμως, αποφασίζουμε ότι θέλουμε να συμπιέσουμε την έξοδο της πηγής περισσότερο, με κόστος κάποια μικρή απώλεια πληροφορίας (παραμόρφωση-distortion). Σε αυτή τη περίπτωση, λέμε ότι έχουμε κβαντισμό (quantization) ή κωδικοποίηση με απώλειες (lossy coding). Στην επόμενη παράγραφο αναλύονται δυο τέτοιες τεχνικές.

Τεχνικές κβαντισμού

Ένα σύστημα κβαντισμού απεικονίζει μια είσοδο σε μια έξοδο, χρησιμοποιώντας κάποιο κατάλληλο μηχανισμό απεικόνισης. Για παράδειγμα, απεικονίζοντας ένα πραγματικό αριθμό σε μια float μεταβλητή, έχουμε ήδη κβαντίσει τον πραγματικό αριθμό σε μια από τις διαθέσιμες τιμές (στάθμες) και έχουμε ήδη εισαγάγει θόρυβο. Απλά, επειδή ο αριθμός διαθέσιμων τέτοιων τιμών είναι αρκετά μεγάλος, ο θόρυβος είναι πολύ μικρός και δεχόμαστε ότι δεν έχουμε πρακτικά απώλεια αναπαράστασης κατά την απεικόνιση αυτή. Το ότι με χρήση π.χ. 32 μόνο bits πληροφορίας, μπορούμε να αναπαραστήσουμε ένα πραγματικό αριθμό, σημαίνει ότι έχουμε σημαντικά oφέλη από άποψη απαιτούμενης πληροφορίας(συμπίεση). Συνοψίζοντας, τα δυο σημαντικά χαρακτηριστικά που εισαγάγει ο κβαντισμός, είναι η συμπίεση από τη μια αλλά και η εισαγωγή θορύβου από την άλλη. Στο σχεδιασμό ενός συστήματος κβαντισμού, το παραπάνω trade-off παίζει καθοριστικό ρόλο.

Το ερώτημα που τίθεται από το παραπάνω trade-off είναι το εξής : ποιός είναι ο ελάχιστος ρυθμός μετάδοσης για να μπορέσουμε να αναπαριστήσουμε την πηγή πληροφορίας, δεχόμενοι ένα συγκεκριμένο επίπεδο απώλειας. Προκειμένου να απαντήσουμε στο παραπάνω ερώτημα, μπορούμε να χρησιμοποιήσουμε τη θεωρία ρυθμού-απώλειας (rate-distortion theory) και την αντίστοιχη συνάρτηση που παρέχει (rate-distortion function). Αυτή είναι αρκετά χρήσιμη στον σχεδιασμό συστημάτων κβαντισμού σε θεωρητικό όμως κυρίως επίπεδο. Και αυτό, γιατί εξαρτάται από τον ορισμό της απώλειας, αλλά και υποθέσεις για την κατανομή της πηγής πληροφορίας. Για παράδειγμα, εάν θεωρήσουμε μια πηγή με γκαουσιανή κατανομή μηδενικού μέσου και μεταβλητότητας $\sigma^2$, αποδεικνύεται ότι η συνάρτηση ρυθμού-απώλειας, δίδεται από τη σχέση $\frac{1}{2}log\frac{\sigma^2}{D}$ (με απώλεια D τετραγωνικού σφάλματος). Στην πράξη, η υπόθεση για την κατανομή μιας πηγής είναι αρκετά απλοποιημένη, αλλά επίσης δύσκολη είναι και η επιλογή μιας κατάλληλης μετρικής.

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

Βαθμωτός κβαντισμός

Στο βαθμωτό κβαντισμό, έχουμε απεικόνιση του συμβόλου εισόδου σε μια μόνο, από ένα σύνολο προκαθορισμένων τιμών που ονομάζονται στάθμες και μπορούμε να τις φανταστούμε σαν προεπιλεγμένα σημεία στον άξονα των πραγματικών αριθμών. Θεωρούμε ότι έχουμε Μ περιοχές που χωρίζουν τον άξονα των πραγματικών αριθμών. Κάθε τέτοια περιοχή $R_{k}, 1\leq k \leq M$ αντιπροσωπεύεται από μια στάθμη $\hat{x}_{k}$. Αν η τιμή εισόδου $x$ ανήκει στη περιοχή $R_{k}$, τότε απεικονίζουμε την είσοδο στην στάθμη της περιοχής. Αυτή η απεικόνιση (συνάρτηση κβαντισμού $Q$) ορίζεται ως : $Q(x) = \hat{x}_{k} \quad \forall x \in R_{k}$. Η συνάρτηση κβαντισμού είναι μη-γραμμική και μη-αναστρέψιμη, αφού όλα τα σημεία στην $R_{k}$ απεικονίζονται στην τιμή $\hat{x}_{k}$. Επειδή η απεικόνιση είναι μη-αναστρέψιμη, κάποια πληροφορία χάνεται για πάντα.

Οι στάθμες αναπαρίστανται ως δυαδική ακολουθία. Αφού έχουμε συνολικά Μ περιοχές ο ρυθμός πληροφορίας θα είναι logΜ. Υπάρχουν 2 κατηγορίες βαθμωτού κβαντισμού : ομοιόμορφος και μη-ομοιόμορφος κβαντισμός. Στη πρώτη κατηγορία οι περιοχές έχουν ίδιο μήκος ενώ στη δεύτερη όχι. Η μη ύπαρξη αυτού του περιορισμού, επιτρέπει την καλλίτερη επιλογή σταθμών στη δεύτερη περίπτωση, με αποτέλεσμα η δεύτερη κατηγορία να είναι πιο αποτελεσματική σε σχέση με τη πρώτη, για ίδιο αριθμό σταθμών. Τα κριτήρια βέλτιστης απόδοσης ενός κβαντιστή είναι γνωστά και ως συνθήκες Lloyd-Max και είναι τα εξής :

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

Διανυσματικός κβαντισμός - VQ

Ο διανυσματικός κβαντισμός (VQ από εδώ και πέρα) αποτελεί μια γενίκευση του βαθμωτού (ή και αντίστροφα, ο βαθμωτός είναι ειδική περίπτωση του διανυσματικού). Πηγαίνοντας από την μια διάσταση στη πολυδιάστατη περίπτωση, νέες ιδέες, έννοιες και τεχνικές εμφανίζονται, που επιτρέπουν την δημιουργία αποτελεσματικών και επιτηδευμένων εφαρμογών συμπίεσης. Ένα διάνυσμα μπορεί να περιγράψει οποιοδήποτε πρότυπο (pattern) και από αυτή την άποψη ο VQ μπορεί να θεωρηθεί σαν μια μορφή αναγνώρισης προτύπων, όπου το διάνυσμα εισόδου ``προσεγγίζεται'' με ένα προκαθορισμένο από ένα σύνολο τέτοιων πρότυπων διανυσμάτων. Τα πρότυπα αυτά διανύσματα ονομάζονται codewords ή και centroids και το σύνολο αυτών codebook.

Μια μαθηματική αντιστοιχία των παραπάνω εκφράζεται με τα εξής : Θεωρούμε ότι έχουμε Μ περιοχές στον Ν-διάστατο χώρο $R_{k}, 1\leq k \leq Μ$ και μονάδα απεικόνισης είναι μπλοκ Ν συμβόλων εξόδου (ή αλλιώς διάνυσμα μήκους Ν). Αν $\mathbf{x}\in \mathbf{R}^Ν$ και $\mathbf{x}\in R_{k}$ τότε αυτό προσεγγίζεται (κβαντίζεται) σύμφωνα με την $Q(\mathbf{x}) = \hat{\mathbf{x}}_{k}$. Έχουμε δηλαδή μια απεικόνιση : $Q : \mathbf{R}^Ν \rightarrow C$, με $C = (\hat{\mathbf{x}}_{1},...,\hat{\mathbf{x}}_{k},...\hat{\mathbf{x}}_{Μ})$ και $\hat{\mathbf{x}}_{k} \in \mathbf{R}^N$. Αφού έχουμε Μ τέτοιες τιμές κβαντισμού (codebook C), απαιτείται ρυθμός μετάδοσης $R = \frac{logΜ}{Ν} bits/$σύμβολο εξόδου.

Aνάλυση απόδοσης και πλεονεκτήματα VQ

Σύμφωνα με τις θεμελιώδεις αρχές της θεωρίας ``ρυθμού-απώλειας'', αποδεικνύεται ότι με χρήση VQ, μπορεί να επιτευχθεί πάντα καλλίτερη απόδοση, από τη περίπτωση χρήσης βαθμωτού κβαντισμού. Στην πραγματικότητα, για πολύ καιρό η θεωρία αυτή είχε περιορισμένη απήχηση, γιατί από τη μια, η θεωρία του Shannon δεν παρείχε μεθοδολογίες σχεδιασμού VQ συστημάτων και από την άλλη οι βαθμωτοί κβαντιστές παρείχαν σχετικά ικανοποιητική απόδοση. Στο τέλος της δεκαετίας του '70, με την εισαγωγή του απλού επαναληπτικού αλγορίθμου για σχεδιασμό βαθμωτών κβαντιστών που βασίζεται στα κριτήρια βελτιστοποίησης (όπως είδαμε στην προηγούμενη παράγραφο - Lloyd), έγινε αντιληπτό, ότι αυτός είναι εύκολα προσαρμόσιμος στην περίπτωση του VQ, φέρνοντας έτσι στο προσκήνιο το ενδιαφέρον για VQ μεθοδολογίες. Από τότε μέχρι σήμερα υπάρχει έντονο ερευνητικό ενδιαφέρον και έχουν αναπτυχθεί πολλές αποτελεσματικές τεχνικές VQ, βασιζόμενες σε διάφορες παραλλαγές του επαναληπτικού αλγορίθμου, με εφαρμογές σε πολλά είδη πηγών πληροφορίας, όπως ομιλίας και εικόνας.

Είδαμε ότι η συνάρτηση ρυθμού απώλειας εξαρτάται από τη γνώση της κατανομής των συμβόλων εξόδου της πηγής και την επιλογή μιας μετρικής για τον υπολογισμό της απώλειας. Επειδή η κατανομή εξαρτάται από τα χαρακτηριστικά της πηγής, χρησιμοποιούμε για την εκτίμησή της, ένα μεγάλο αριθμό διανυσμάτων εκπαίδευσης (train set) που για την περίπτωση που έχουμε πηγή ομιλίας δεν είναι άλλα από τα ακουστικά διανύσματα που παράγει το front-end. Οι πιο συχνές επιλογές για την μετρική απώλειας στη περίπτωση πηγών φωνής, είναι η απώλεια τετραγωνικού σφάλματος με ή χωρίς χρήση βαρών και η απώλεια Itakura-Saito. Η τελευταία είναι ιδιαίτερα χρήσιμη για ακουστικά διανύσματα που παράγονται από τεχνικές κωδικοποίησης βασισμένες στο μοντέλο παραγωγής φωνής, που θα δούμε σε επόμενη παράγραφο. Στην τεχνική που αναπτύξαμε χρησιμοποιούμε την απώλεια τετραγωνικού σφάλματος με βάρη και συγκεκριμένα την Mahalanobis απώλεια που ορίζεται ως εξής :

\begin{displaymath}
d(\mathbf{x},\hat{\mathbf{x}}) = (\mathbf{x}-\hat{\mathbf{x}})^T W (\mathbf{x}-\hat{\mathbf{x}})
\end{displaymath} (2.1)

με πίνακα βαρών τον αντίστροφο πίνακα συνδιακύμανσης $W = E[(\mathbf{x}-\overline{\mathbf{x}})(\mathbf{x}-\overline{\mathbf{x}})^T]^{-1}$ και $\overline{\mathbf{x}}=E[\mathbf{x}]$.

Ο επαναληπτικός αλγόριθμος που χρησιμοποιούμε, περιγράφεται στη παράγραφο 2.9.2. Στόχος του αλγορίθμου είναι η ελαχιστοποίηση της μέσης απώλειας, δηλαδή του όρου $Ed(\mathbf{x}, \hat{\mathbf{x}})$ που στην πράξη μπορεί να αντικατασταθεί με τον επί μακρόν δειγματοληπτικό μέσο (long term sample average) : $lim_{n \rightarrow \infty} \sum_{i=0}^{n-1} d(\mathbf{x_{i}},\hat{\mathbf{x_{i}}})$, υπό την προϋπόθεση ότι η ακολουθία είναι εργοδική(ergodic) και στάσιμη(stationary). Ακόμα όμως και να μην ισχύει αυτή η συνθήκη, στην πράξη είναι αρκετό η πηγή να είναι ασυμπτωτικά στάσιμη στο μέσο (mean stationary), κάτι που όντως ισχύει στη περίπτωση της φωνής (long and short term stationary).

Είδαμε στην αρχή της παραγράφου, ότι ο ρυθμός μετάδοσης για VQ, είναι $R = \frac{logM}{N} bits/$σύμβολο εξόδου. Αν συγκρίνουμε αυτό το ρυθμό με το ρυθμό στη περίπτωση του βαθμωτού κβαντισμού (logM) βλέπουμε ότι ο ίδιος αριθμός bits αυτή τη φορά μοιράζεται μεταξύ πολλών συμβόλων εξόδου. Αυτό βέβαια δεν σημαίνει ότι απαιτείται ίδια ποσότητα πληροφορίας στις 2 περιπτώσεις, αλλά ότι στην 2η περίπτωση κατανέμεται σε περισσότερα σύμβολα εξόδου, με μικρότερη πιθανότητα σπατάλησης bits. Στην περίπτωση αυτή, ένα σύμβολο εξόδου μπορεί να απαιτεί κλασματικό (fractional) ποσό πληροφορίας όπως π.χ. 0.38 bits και αυτό δεν είναι το μοναδικό πλεονέκτημα του VQ. Αποδεικνύεται ότι οι τεχνικές VQ δίνουν καλλίτερη απόδοση, καθώς εκμεταλλεύονται καλλίτερα την ύπαρξη γραμμικής (correlation) και μη γραμμικής εξάρτησης μεταξύ των συμβόλων εξόδου, αλλά αποδίδουν καλλίτερα ακόμα και στη περίπτωση που αυτή δεν υπάρχει. Τέλος εκμεταλλεύονται καλλίτερα την κατανομή της πηγής και επιτρέπουν τον σχηματισμό περιοχών με σχήμα χωρίς περιορισμούς στον N-διάστατο χώρο.

Είδη VQ, παράμετροι σχεδιασμού και τεχνικές

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

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

Επιλογή αρχικού codebook

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

Product VQ

Μια άλλη επιλογή που έχουμε, είναι να χωρίσουμε το αρχικό διάνυσμα σε μικρότερα και να εφαρμόσουμε VQ για καθένα από αυτά. Αυτό προκύπτει, γιατί πολλές φορές μπορούμε να διακρίνουμε τέτοια μικρότερα γκρουπ μέσα στο διάνυσμα, βάσει κάποιων κοινών χαρακτηριστικών. Στη περίπτωση της φωνής, η μέθοδος αυτή επιλέγεται κυρίως για ακουστικά διανύσματα που παράγονται από model-based τεχνικές (βλέπε 2.8). Για front-ends όπως αυτά που είδαμε στο Κεφάλαιο 1, ο τρόπος αυτός χρησιμοποιείται σχετικά σπάνια, με πιο κοινό χαρακτηριστικό διαχωρισμού, την ποικιλία τιμών (dynamic range) των στοιχείων του ακουστικού διανύσματος. Σύμφωνα με το τελευταίο, ο πιο εμφανής διαχωρισμός είναι ανάμεσα στην ενέργεια και τις υπόλοιπες 12 cepstral παραμέτρους.

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

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

Ενας καλλίτερος διαχωρισμός είναι αυτός που θα μοιράσει το διάνυσμα των 13 στοιχείων σε ένα μεγαλύτερο αριθμό υποδιανυσμάτων (π.χ. 5) καθένα από τα οποία απαιτεί περίπου ίδιο αριθμό bits. Ας υποθέσουμε ότι οι δυο μέθοδοι απαιτούν τον ίδιο αριθμό bits (αφού αντιπροσωπεύουν το ίδιο διάνυσμα με 2 διαφορετικές μορφές), έστω 20 και ότι στη δεύτερη περίπτωση τα 5 διανύσματα απαιτούν 5, 5, 4, 4 και 2 bits αντίστοιχα. Χρησιμοποιώντας την πρώτη προσέγγιση απαιτούνται $2^{20}$, δηλαδή πάνω από ένα εκατομμύριο centroids στο μοναδικό codebook, ενώ στη δεύτερη 5 codebooks με $2^5 + 2^5 + 2^4 + 2^4 + 2^2$, δηλαδή 32, 32, 16, 16 και 4 centroids αντίστοιχα (σύνολο 100). Τα ωφέλη είναι απίστευτα, από άποψη χρόνου κβαντισμού και αποθήκευσης, ακόμα και αν έχουμε μικρή απώλεια ως προς τη βέλτιστη θεωρητική συμπίεση (δηλαδή για την ίδια συμπίεση η πρώτη μέθοδος να απαιτούσε τελικά 18 ή ακόμα και 15 bits, κάτι που δεν αλλάζει όμως την εικόνα).

Τεχνικές ψαξίματος

Τέλος, η τελευταία επιλογή που θα εξετάσουμε, είναι ο τρόπος που είναι δομημένα τα centroids μέσα στα codebooks, ο οποίος καθορίζει και τον αριθμό των συγκρίσεων που απαιτούνται για να βρεθεί το ``πλησιέστερο'' στο διάνυσμα εισόδου centroid (nearest-neighbour search). Ο πιο απλός τρόπος, είναι να χρησιμοποιηθεί πλήρες ψάξιμο, δηλαδή όλα τα centroids. Αν και εξαιρετικά απλός, για μεγάλα codebooks αυτός ο τρόπος είναι πολύ αργός. Η άλλη επιλογή είναι να δομηθούν τα centroids με ένα ιεραρχικό τρόπο (π.χ. δυαδικό δέντρο). Με αυτό τον τρόπο, για M centroids απαιτούνται μόλις logM συγκρίσεις αντί για M που απαιτούνται στην προηγούμενη περίπτωση. Αν και πολύ γρηγορότερος, αυτός ο τρόπος απαιτεί αλλαγές στον αλγόριθμο εκπαίδευσης, αλλά είναι και υποβέλτιστος σε σχέση με τον πρώτο, αφού τα διανύσματα που χρησιμοποιούνται για την εκπαίδευση των centroid σε κάθε επανάληψη, δεν είναι το σύνολο αυτών του σετ εκπαίδευσης, αλλά ένα όλο και μικρότερο γκρουπ αυτών, τα οποία σε προηγούμενη επανάληψη ομαδοποιήθηκαν στην περιοχή του παρόντος centroid. Με δεδομένη την χρήση υποδιανυσμάτων, τα codebooks είναι αρκετά μικρά, άρα δεν έχει τόσο μεγάλη σημασία η χρήση της δεύτερης μεθόδου αφού επιπλέον είναι και μη βέλτιστη.

Τεχνικές κωδικοποίησης φωνής

Οι τεχνικές κωδικοποίησης χωρίζονται σε 3 κατηγορίες :

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

Waveform Coding τεχνικές

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

Τεχνικές στο πεδίο του χρόνου

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

Pulse Code Modulation (PCM)

Αποτελεί την πιο απλή μέθοδο. Το σήμα δειγματοληπτείται στη συχνότητα Nyquist και κάθε δείγμα κβαντίζεται στην κοντινότερη στάθμη και στη συνέχεια μεταδίδεται σαν δυαδικός αριθμός. Όσα περισσότερα bits διαθέσουμε, τόσες περισσότερες στάθμες έχουμε, με αποτέλεσμα να έχουμε πιο πιστή αναπαράσταση του σήματος. Το σήμα της φωνής χαρακτηρίζεται από το γεγονός ότι μικρά πλάτη (amplitudes) συμβαίνουν πολύ συχνότερα από τα μεγάλα. Μια βελτίωση είναι επομένως, οι στάθμες να απέχουν λιγότερο μεταξύ τους στα μικρά πλάτη και περισσότερο στα μεγάλα. Αυτό οδηγεί στη χρήση μη ομοιόμορφου βαθμωτού κβαντιστή, ο οποίος συμπιέζει το σήμα χρησιμοποιώντας κάποια λογαριθμική συνάρτηση και στη συνέχεια το κβαντίζει χρησιμοποιώντας ομοιόμορφο κβαντιστή. Τέτοιοι λογαριθμικοί συμπιεστές χρησιμοποιούνται για τη μετάδοση φωνής στα τηλεφωνικά δίκτυα και είναι γνωστοί σαν $\mu-law$ & A-law compressors.

Differential PCM (DPCM)

Μια πρώτη βελτίωση στην PCM μέθοδο είναι ο κβαντισμός να γίνεται στην διαφορά μεταξύ 2 διαφορετικών δειγμάτων. Αυτή είναι μια σημαντική βελτίωση, αφού στο σήμα της φωνής, διαδοχικά δείγματα έχουν μεγάλο βαθμό συσχέτισης και επομένως η διαφορά μεταξύ 2 διαφορετικών δειγμάτων είναι μικρή. Μια βασική επέκταση της παραπάνω ιδέας είναι να κάνουμε κάποια πρόβλεψη για το τρέχον δείγμα, και να κβαντίζουμε τη διαφορά μεταξύ του πραγματικού δείγματος και της προβλεπόμενης τιμής του. Έτσι περιμένουμε να μειώσουμε ακόμα περισσότερο το απαιτούμενο bandwidth.
Σημείωση : Για την πρόβλεψη του επόμενου δείγματος χρησιμοποιείται ένας γραμμικός προβλέπτης της μορφής : $\widehat x_{n} = \sum_{i=1}^p a_{i} x_{n-i}$ ,όπου p είναι τα προηγούμενα δείγματα που χρησιμοποιούμε και $a_{i}$ είναι το βάρος για το αντίστοιχο προηγούμενο δείγμα.

Adaptive DPCM (ADPCM)

Οι παραπάνω τεχνικές βασίζονται στην υπόθεση ότι το σήμα εισόδου είναι στάσιμο (stationary), δηλαδή οι στατιστικές του ιδιότητες (π.χ. μεταβλητότητα, αυτοσυσχέτιση ) είναι σταθερές με το χρόνο. Στην περίπτωση του σήματος της φωνής οι παραπάνω ιδιότητες μεταβάλλονται αργά με το χρόνο (quasi-stationary). Για να εκμεταλλευτούμε και αυτό το χαρακτηριστικό του σήματος της φωνής οι κωδικοποιητές πρέπει να μπορούν να προσαρμοστούν στις χρονικά μεταβαλλόμενες αλλαγές των στατιστικών μεταβολών του σήματος. Έτσι έχουν αναπτυχθεί προσαρμοστικές εκδόσεις του DPCM, που χρησιμοποιούν προσαρμοστικό κβαντιστή ή/και προβλέπτη. Ο κβαντιστής γίνεται προσαρμοστικός αλλάζοντας τις στάθμες κβαντισμού ανάλογα με την ισχύ του σήματος, και ο προβλέπτης αλλάζοντας τους συντελεστές ανάλογα με το φάσμα του σήματος. Τέλος υπάρχουν και άλλες ανάλογες τεχνικές όπως π.χ. Delta Modulation.

Tεχνικές στο πεδίο της συχνότητας

Παραδείγματα τεχνικών που χρησιμοποιούνται στο πεδίο της συχνότητας είναι οι : Sub-band coding (SBC), Adaptive transform coding (ATC) & Filterbank Spectrum Analyzer. Οι τεχνικές αυτές στηρίζονται στην ιδέα του φιλτραρίσματος του σήματος σε διαφορετικές μπάντες στο πεδίο της συχνότητας και τη κωδικοποίηση σε ένα από τα δυο πεδία στη συνέχεια. Μάλιστα, η περιγραφή του front-end μηχανισμού που είδαμε στο Κεφάλαιο 1, ανήκει στη τρίτη μέθοδο και στηρίζεται στη χρήση μιας σειράς από φίλτρα σε διαφορετικές μπάντες συχνοτήτων (filterbanks). Στη παράγραφο 2 του Κεφαλαίου 3 θα δούμε αναλυτικότερα πως χρησιμοποιείται αυτή η τεχνική για να παράγουμε τελικά τα ακουστικά διανύσματα. Ένα εναλλακτικό τύπο front-end μηχανισμού θα δούμε επίσης στην αμέσως επόμενη παράγραφο.

Figure: Μοντέλο παραγωγής φωνής.
[scale = 0.450]images/coding-images/eps/model.eps

Model based τεχνικές (Vocoders)

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

Το μοντέλο φαίνεται στο σχήμα 2.1. Όπως φαίνεται, υπάρχουν 2 δυνατές πηγές. Η πρώτη πηγή αντιστοιχεί στον ήχο χωρίς φωνή και η δεύτερη σε αυτόν με φωνή (unvoiced & voiced sounds). Στην 2η πηγή η φωνή παράγεται όταν οι φωνητικές χορδές πάλλονται σε κάποια βασική συχνότητα $f_{0}$. Μια πηγή κάθε χρονική στιγμή διεγείρει το φίλτρο που αναπαριστάνει το φωνητικό σωλήνα και έτσι παράγεται το σήμα της φωνής. Η παραγωγή των παραμέτρων του φωνητικού σωλήνα γίνεται με χρήση γραμμικής πρόβλεψης (linear prediction coding). Το σύνολο των παραμέτρων που προκύπτουν περιλαμβάνουν τους συντελεστές πρόβλεψης, το κέρδος (gain) του σήματος, το είδος εισόδου που έχουμε και τη συχνότητα $f_{0}$ , εφόσον η είσοδος είναι voiced. Οι παραπάνω παράμετροι μεταδίδονται στον δέκτη όπου χρησιμοποιώντας το ίδιο μοντέλο ανακατασκευάζεται το αρχικό σήμα (για αυτό το λόγο οι τεχνικές αυτές ονομάζονται επίσης analysis by synthesis τεχνικές). Για κάθε 20-30 msecs που το σήμα της φωνής μπορεί να θεωρηθεί stationary υπολογίζονται οι συντελεστές του φίλτρου σύμφωνα με την εξίσωση :

\begin{displaymath}
X_{n} = \sum_{i=1}^p a{i}X_{n-1} + Gw_{n}
\end{displaymath} (2.2)

όπου $G$ είναι το κέρδος, $w{n}$ η ακολουθία εισόδου, ${a_{i}}$ οι συντελεστές του φίλτρου και p ο αριθμός πόλων του φίλτρου.

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

Βασικό χαρακτηριστικό των vocoders είναι οι χαμηλοί ρυθμοί μετάδοσης αλλά και η χαμηλή ποιότητα. Υπάρχουν πολλές υλοποιήσεις vocoders με πιο διαδεδομένους όσους στηρίζονται σε τεχνικές γραμμικής πρόβλεψης, σαν αυτή που μόλις περιγράφτηκε. Οι υβριδικοί κωδικοποιητές (επίσης vocoders), προσπαθούν να χρησιμοποιήσουν μια πιο σύνθετη διέγερση από τους LPC vocoders, καταφέρνοντας έτσι καλή ποιότητα για χαμηλούς-μέσους ρυθμούς μετάδοσης. Υλοποιήσεις vocoders (υβριδικών και μη) είναι οι channel, phase, cepstral & formant vocoders, καθώς και οι RELP, CELP & VSELP vocoders. Μάλιστα η κωδικοποίηση GSM στη κινητή τηλεφωνία δευτέρας γενεάς, βασίζεται σε RPE-LTP υβριδικό κωδικοποιητή, ενώ οι CELP αποτελούν το πρότυπο για κινητή τηλεφωνία στην Βόρειο Αμερική.

Το σχήμα κωδικοποίησης που χρησιμοποιήσαμε

Στις προηγούμενες παραγράφους είδαμε αναλυτικά τεχνικές κβαντισμού και κωδικοποίησης της φωνής. Σημειώθηκε ότι η χρήση του Filterbank Spectrum Analyzer σαν μηχανισμού front-end, καθώς και η χρήση διανυσματικού κβαντισμού βάσει μικρότερων υποδιανυσμάτων (product VQ), παίζουν σημαντικό ρόλο στην επιτυχία του σχήματος κωδικοποίησης αυτής της εργασίας, την οποία και παρουσιάζουμε σε αυτό το δεύτερο μέρος.

Ο front-end μηχανισμός παράγει τα ακουστικά διανύσματα με τους 13 ή 39 MFCC συντελεστές για κάθε frame (δηλαδή διάστημα 10 msecs), με αποτέλεσμα ο ρυθμός πληροφορίας να είναι 1300 (ή 3900) συντελεστές αντίστοιχα ανά second. Αφού κάθε συντελεστής αντιπροσωπεύεται από μια float μεταβλητή απαιτούνται 1300 ή 3900 * 32 bits/sec, δηλαδή 41,6 ή 124.8 kbps αντίστοιχα. Αυτός ο ρυθμός είναι μικρότερος σε σχέση με αυτό της αρχικής πηγής πληροφορίας (δειγματοληπτημένη κυματομορφή σε 8 ή 16Khz και με 16bits ανά σύμβολο) και σκοπός μας είναι να τον μειώσουμε ακόμα περισσότερο , χρησιμοποιώντας τεχνικές κβαντισμού.

Θυμίζουμε ότι με τον κβαντισμό, ουσιαστικά περιορίζουμε τον αριθμό συμβόλων εξόδου, σε ένα μικρό σύνολο προτύπων συμβόλων εξόδου, καταφέρνοντας να συμπιέσουμε από τη μια το σήμα αλλά και δυστυχώς να εισάγουμε θόρυβο από την άλλη. Στην εισαγωγή αυτού του κεφαλαίου, τονίσαμε ότι επειδή στόχος μας δεν είναι η όσο πιο πιστή αναπαραγωγή του σήματος, αλλά η καλλίτερη δυνατή αναγνώριση, την απώλεια πληροφορίας που έχουμε με τον κβαντισμό, τη μετράμε με βάση τα αποτελέσματα της αναγνώρισης. Αυτό μας βοηθάει πρακτικά στο να αξιολογήσουμε τα διάφορα σχήματα κωδικοποίησης που θα αναπτύξουμε. Τα σημαντικότερα αποτελέσματα από τα πειράματα που διεξάχθηκαν προκειμένου να καταλήξουμε στο καλλίτερο μέχρι στιγμής αποτέλεσμα, με ρυθμό μετάδοσης μόλις 2kbps, παρατίθενται στο τέλος του κεφαλαίου. Στο Κεφάλαιο 4, παραθέτουμε κάποια άλλα ενδεικτικά πειράματα που έγιναν, πριν καταλήξουμε στα αποτελέσματα που παρουσιάζουμε σε αυτό το κεφάλαιο.

Σε αυτή την ενότητα, θα θυμίσουμε κάποιες βασικές έννοιες-ορολογίες, όπως αυτές των codebooks, centroids και θα ορίσουμε κάποιες άλλες. Στη συνέχεια θα εξετάσουμε τις διαδικασίες εκπαίδευσης (δημιουργία codebooks με βάση τον επαναληπτικό αλγόριθμο k-means) και κβαντισμού, στην περίπτωση της (product VQ) τεχνικής, η οποία αποτελεί και την ``καρδιά'' της κωδικοποίησης. Τα παραπάνω πλαισιώνονται με αρκετά σχήματα, προκειμένου να γίνουν ακόμα πιο ξεκάθαρες οι παραπάνω έννοιες και διαδικασίες που περιγράφονται.

Βασικές έννοιες

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

Είσοδος συστήματος κβαντισμού.
Η είσοδος στο σύστημα κβαντισμού είναι το MFCC διάνυσμα, όχι όμως απαραίτητα με τη μορφή μονάχα του ενός διανύσματος. Μπορούμε να το αναπαραστήσουμε με περισσότερα (υπο-)διανύσματα, αρκεί αυτά συνδυαζόμενα να μας δίνουν την το αρχικό διάνυσμα. Έτσι, αν υποθέσουμε ότι το MFCC διάνυσμα έχει μέγεθος 13 (high quality - χωρίς χρήση των παραγώγων), τότε έχουμε επιλογές όπως :

  1. Να χρησιμοποιήσουμε το διάνυσμα ως έχει : [1 2 3 ...13]
  2. Να χρησιμοποιήσουμε 13 βαθμωτούς : 1, 2, 3, ..., 13
  3. Να χρησιμοποιήσουμε $L ( 1 \leq L \leq 13 )$ υποδιανύσματα, όπως π.χ. :
    [1 2 ...7], [8 ...12], [13] ή [1 3 5 7 ...13] [2 4 6 ...12] κ.λ.π.
  4. Οποιαδήποτε άλλη επιλογή κριθεί κατάλληλη. Θα δούμε στη συνέχεια το τρόπο επιλογής υποδιανυσμάτων

Και οι 3 παραπάνω επιλογές είναι περιπτώσεις του διανυσματικού κβαντισμού (Vector quantization). Η 2η είναι περίπτωση βαθμωτού κβαντισμού, ενώ η 3η είναι ο code product κβαντισμός. Στην 1η περίπτωση χρησιμοποιούμε ένα μόνο κβαντιστή, στη 2η δεκατρείς & στη 3η τρεις και δυο κβαντιστές αντίστοιχα.

Αναπαράσταση της εξόδου του συστήματος κβαντισμού.
Αφού εξετάσαμε τις δυνατές εισόδους, ας κάνουμε το ίδιο για την έξοδο. Πρώτα όμως να θυμίσουμε ότι στη διαδικασία κβαντισμού απεικονίζουμε ένα δείγμα εισόδου σε ένα μόνο δείγμα, από ένα πεπερασμένο αριθμό δειγμάτων εξόδου (έστω M), τα οποία προκύπτουν κατάλληλα από την διαδικασία εκπαίδευσης των δεδομένων εκπαίδευσης. Το γεγονός ότι τα δείγματα εξόδου είναι πεπερασμένα, μας δίνει ένα επιπλέον τρόπο απεικόνισης. Έτσι έχουμε 2 τρόπους απεικόνισης, αν κβαντίσουμε το δείγμα εισόδου στο i-οστό από τα πεπερασμένα δείγματα :
το i-οστό διάνυσμα (codeword) ή απλά τον αριθμό i (index). Το είδος της απεικόνισης είναι αυτό που καθορίζει και το είδος ακουστικών μοντέλων στον αναγνωριστή. Στην 1η περίπτωση όπου απεικονίζουμε ένα δείγμα-διάνυσμα μεγέθους N σε ένα επίσης διάνυσμα μεγέθους N μιλάμε για Centroid Coded κβαντισμό. Στη 2η περίπτωση, όπου απεικονίζουμε το δείγμα-διάνυσμα μεγέθους N στον ακέραιο που χαρακτηρίζει το i-οστό αυτό διάνυσμα (δηλ. το i) μιλάμε για Index Coded κβαντισμό.

Centroid και Codebook
Χωρίζοντας τον N-διάστατο χώρο σε M περιοχές, κάθε μια από αυτές τις περιοχές έχει ένα σημείο αναφοράς, το centroid. Όλα τα σημεία που ανήκουν σε μια περιοχή λέμε ότι έχουν κβαντιστεί στο centroid αυτής της περιοχής. Η απόσταση2.1 των σημείων που ανήκουν σε μια περιοχή με το centroid της ίδιας περιοχής, είναι μικρότερη από την απόσταση με όποιο άλλο centroid του χώρου : αυτό είναι και το κριτήριο (nearest neighbour), με βάση το οποίο τα σημεία του χώρου κβαντίζονται σε κάποιο centroid και σχηματίζουν κάποια περιοχή. Το codebook, εμπεριέχει τα Μ centroids του N-διάστατου χώρου (βλέπε σχήμα 2.2).

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

Διαδικασία εκπαίδευσης

Η διαδικασία εκπαίδευσης αποσκοπεί στην δημιουργία των codebooks, τα οποία στη συνέχεια θα χρησιμοποιηθούν από τον κβαντιστή. Για κάθε frame στο train set, χωρίζουμε το MFCC διάνυσμα σε μικρότερα έστω L υποδιανύσματα, σύμφωνα με το σχήμα εκπαίδευσης που έχουμε επιλέξει. Αν συμβολίσουμε με $N_{i}$ το μέγεθος του υποδιανύσματος i και $M_{i}$ το αριθμό των centroids στο i codebook, τότε με το τέλος της διαδικασίας εκπαίδευσης, (μέσω των L εκπαιδευτών) θα έχουν παραχθεί τα αντίστοιχα L codebooks μεγέθους $M_{i}$ και διάστασης $N_{i}$ το καθένα (βλέπε σχήμα 2.3).

Οι trainers χρησιμοποιούν τον k-means αλγόριθμο τον οποίο και θα περιγράψουμε στη συνέχεια. Τα σύμβολα Ν, Μ, Β που εμφανίζονται στον αλγόριθμο (θεωρούμε ότι $M=2^B$), αντιστοιχούν στα $N_{i}$ και $M_{i}$ για το κάθε υποδιάνυσμα (και κατ' επέκταση για τον αντίστοιχο από τους L trainers).

Figure: Codebook & Centroids. Παράδειγμα για N=2 και M=36 όπου φαίνεται ο διδιάστατος χώρος με 36 περιοχές. Κάθε περιοχή έχει κι ένα centroid, το οποίο έχει την ιδιότητα να αντιπροσωπεύει καλλίτερα όλα τα σημεία της περιοχής. Το σύνολο των 36 αυτών centroids αποτελεί το codebook δηλαδή τα 36 διδιάστατα διανύσματα
[scale = 0.500]images/coding-images/eps/codebook-centroids.eps

Figure: Διαδικασία εκπαίδευσης. Χωρίζουμε κάθε MFCC διάνυσμα σε L υποδιανύσματα με μέγεθος $N_{i}$ το καθένα. Για κάθε υποδιάνυσμα, αποφασίζουμε πόσους και ποιους συντελεστές θα περιέχει, καθώς και πόσα centroids στο codebook (στη συγκεκριμένη περίπτωση 4).
[scale = 0.450]images/coding-images/eps/fig3.eps

Figure: Εκπαίδευση και δημιουργία codebookΠαράδειγμα δημιουργίας 4 centroids στο codebook. Ξεκινώντας από την αρχική τιμή και εφαρμόζοντας διαδοχικά διαδικασίες splitting και επανεκπαίδευσης των centroids, παίρνουμε το τελικό codebook (με 4 centroids)
[scale = 0.470]images/coding-images/eps/tr-algo.eps

Αλγόριθμος εκπαίδευσης :

Ας υποθέσουμε ότι θέλουμε να χωρίσουμε τον N-διάστατo χώρο σε $Μ=2^B$ περιοχές. Το N είναι το μέγεθος του υποδιανύσματος & το B είναι ο αριθμός των bits που θέλουμε να χρησιμοποιήσουμε. Αν π.χ. έχουμε B=5, αυτό σημαίνει ότι τελικά θα έχουμε 32 centroids στο codebook. Ο αλγόριθμος εκπαίδευσης που χρησιμοποιούμε είναι ο k-means ( σε κάποιες παραλλαγές είναι γνωστός και ως generalized Lloyd, LBG ή και ISODATA αλγόριθμος), εφαρμόζεται για κάθε ένα από τα υποδιανύσματα που έχουμε ορίσει και δίνεται παρακάτω :

Αρχικοποίηση (Initialization):
Θέσε αρχικό μοναδικό centroid, το υποδιάνυσμα που αντιστοιχεί στη μέση τιμή όλων των τιμών του υποδιανύσματος στο train set(σετ εκπαίδευσης). Η επιλογή αυτή είναι αρκετά αντιπροσωπευτική και είμαστε τώρα έτοιμοι να περάσουμε στον επαναληπτικό αλγόριθμο.

Σε κάθε βήμα $i : (0 \leq i < B)$
Βήμα 1 : Χώρισε κάθε ένα από τα n centroids $(1 \leq n \leq 2^i)$ σε 2 νέα, εφαρμόζοντας δυαδικό χωρισμό (binary splitting).
Αυτό σημαίνει ότι από κάθε centroid $y_{n}$ παίρνουμε 2 νέα, τα : ( $y_{n}^+ = y_{n} + ε$) & ( $y_{n}^- = y_{n} - ε$) τα οποία όμως δεν είναι αρκετά αντιπροσωπευτικά και χρειάζονται εκπαίδευση για να γίνουν. Η τιμή του $ε$ είναι της τάξης του 0.05
Βήμα 2 : Για κάθε επανάληψη j (Ο αριθμός των επαναλήψεων αυξάνει γραμμικά με το βήμα : π.χ. j=i+5)
  1. Για κάθε υποδιάνυσμα του σετ εκπαίδευσης (Clustering - Nearest Neighbour search):
    Υπολόγισε την απόστασή του από όλα τα υπάρχοντα centroids και ομαδοποίησέ το στο centroid με το οποίο το μέτρο της μεταξύ τους απόστασης είναι ελάχιστο. Το μέτρο της απόστασης που χρησιμοποιείται παίζει μεγάλο ρόλο. Συνήθως χρησιμοποιείται η Mahalanobis απόσταση.
  2. Υπολόγισε τις νέες τιμές των centroids (Reestimation - Centroid Update):
    Η νέα τιμή για κάθε centroid, είναι η μέση τιμή όλων των υποδιανυσμάτων που έχουν ομαδοποιηθεί στην προηγούμενη τιμή του centroid
Ο αλγόριθμος φαίνεται καλλίτερα στο σχήμα 2.4

Διαδικασία κβαντισμού

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

Figure: Διαδικασία κβαντισμού.Για κάθε υποδιάνυσμα i, ο κβαντιστής βρίσκει το centroid που το αντιπροσωπεύει καλλίτερα, δηλαδή το centroid με το οποίο η απόσταση είναι μικρότερη. Όσο για την έξοδο του κβαντιστή, αυτή μπορεί να είναι ή το ίδιο το centroid ή το index του. Στη συγκεκριμένη περίπτωση, το υποδιάνυσμα i λέμε ότι κβαντίστηκε στο 3ο centroid.
[width=360pt,height=100pt]images/coding-images/eps/fig4-2.eps

Figure: Έξοδος συστήματος κβαντιστών και αναγνώριση.Αν έχουμε centroid coded κβαντισμό, από το σύστημα των κβαντιστών προκύπτει ένα ανακατασκευασμένο MFCC διάνυσμα, αφού τα elements κάθε centroid παίρνουν την θέση τους στο αρχικό διάνυσμα. Η αναγνώριση για centroid coded κβαντισμό, γίνεται από ένα Recognizer με συνεχή HMM μοντέλα. Αν έχουμε index coded κβαντισμό, η έξοδος των κβαντιστών είναι ένα διάνυσμα από τα αντίστοιχα των centroid indices. Προκύπτει έτσι ένα διάνυσμα μήκους L, όσο και ο αριθμός των υποδιανυσμάτων. Η αναγνώριση για index coded κβαντισμό γίνεται από ένα Recognizer με μείγματα διακριτών HMMs.
[width=360pt,height=150pt]images/coding-images/eps/fig5.eps

Αξιολόγηση κωδικοποίησης

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

Συμπεράσματα

Παραπομπές

Δυο κλασικές εργασίες στη χρήση διανυσματικού κβαντισμού παρουσιάζονται στα [#!VQ1!#] και [#!VQ2!#]. Στη πρώτη δίνεται έμφαση στις διαφορές βαθμωτού και διανυσματικού κβαντισμού και παρουσιάζεται η αποτελεσματικότητα του δεύτερου, καθώς βελτιστοποιεί την παρουσία γραμμικής και μη γραμμικής εξάρτησης, σχήματος συνάρτησης πυκνότητας πιθανότητας (probability density function) και της διάστασης του διανύσματος. Στη δεύτερη παρουσιάζεται μια σειρά διαφορετικών τεχνικών βασισμένων σε διανυσματικό κβαντισμό. Για πιο ολοκληρωμένη εικόνα το [#!VQ3!#] είναι ένα βιβλίο αφιερωμένο σε τέτοιες τεχνικές. Τεχνικές κωδικοποίησης φωνής παρουσιάζονται επίσης στο βιβλίο [#!VQ4!#] , ενώ στο [#!SRS5!#] δίνεται έμφαση στις τεχνικές κωδικοποίησης πηγής.


next up previous
Next: Υλοποίηση της κωδικοποίησης - Up: mythesis Previous: Σύστημα αναγνώρισης φωνής
root 2001-02-24