Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/14185
Title: Audio-fingerprinting via the k-svd algorthm
Other Titles: Αναγνώριση μουσικών κομματιών βάσει τεχνικών εκμάθηση λεξικών
Authors: Σαραβάνου, Χριστίνα
Keywords: Song identification
Audio-fingerprinting
Signal processing
Compressive sensing
Dictionary learning
Orthogonal Matching Pursuit (OMP)
K-SVD
Keywords (translated): Ακουστικό αποτύπωμα
Αναγνώριση μουσικών κομματιών
Επεξεργασία σημάτων
Συμπιεσμένη δειγματοληψία
Εκμάθηση λεξικού
Αλγόριθμος OMP
Abstract: Music has always played an elemental and unique role in human entertainment and communication. At the end of the 19th century, music was, initially, employed and since then, has been established as a fundamental tool for scientific, medical and educational purposes. In the mid-1960’s, a novel research field, known to most as Music Information Retrieval (MIR)- emerged which aspires to solve various music related problems, such as the song identification and the music genre classification problems, by combing several signal processing and Information Retrieval (IR) techniques. Solving the song identification problem has always been one of the most challenging conundrums of MIR. Throughout the years, several approaches, with the most promising being the audio-fingerprinting scheme, have been proposed to solve this arduous problem. The audio-fingerprinting paradigm, which was introduced in the 1990’s, aims to construct a unique and concise representation -similar to that of a human fingerprint, ergo the name- of an audio track’s signal content. In the last twenty or so years, several alternates of the original audio-fingerprinting scheme have been proposed: Some of which rely on the conventional signal processing and statistical approaches, e.g. the Short-Time Fourier Transform (STFT), while others employ methods and concepts which are applied by several contemporary schemes, such as the Matching Pursuit (MP) algorithm and time-frequency dictionaries-which are used by the Compressive Sensing (CS) and Dictionary Learning (DL) paradigms. This thesis introduces an innovative alternate of the audio-fingerprinting scheme, which aims by employing the Orthogonal Matching Pursuit (OMP) and the K-SVD algorithms -two state-of-the-art techniques applied by the CS and DL paradigms respectively- to construct unique and concise representations of several audio signals to identify their content. Particularly, the suggested approach, initially, aims to create a global dictionary via the K-SVD algorithm and several tens of audio tracks, which uphold the database. The dictionary aspires not only to capture the acoustic/perceptual attributes of the audio signals, but also to apprehend the descriptiveness, the robustness and the discriminability of the audio-fingerprints. Afterwards, the songs-which maintain the database- and the audio excerpt of an unknown audio track- which are used during the querying process-are segmented into several audio frames respectively. Thereupon, the sparse representations of both the audio tracks and clip are computed via the OMP algorithm and the dictionary. Then, the atoms, i.e. the coefficients of an audio signal’s sparse representation, with the highest weight values are extracted and considered equivalent to the most descriptive points of the respective signal’s spectrogram. The landmark pairs, namely four-point peak-pairs, are constructed by using the atoms which were previously selected and are used to construct hash tables. The proposed scheme constructs separate hash tables for every audio track in the database for the audio clip. During the querying process of the suggested paradigm, several voting methods are employed to determine from which song, the audio segment was extracted from and the metadata of the respective song is returned. During the evaluation process of the introduced alternate, several experiments were performed by employing dictionaries of different dimensions. The dictionaries were constructed by using the content of various audio tracks- extracted from two datasets of different size- in both the temporal or the spectral domains. The proposed technique was, initially, assessed to determine which dictionary i.e. which dictionary size and domain, can provide the most accurate results. Moreover, the suggested audio-fingerprinting technique was gauged against its robustness, scilicet whether an audio clip which has been distorted by ambient noise can be identified. Furthermore, the suggested scheme aims to regulate whether an audio clip extracted from a song, which did not partake in the learning process can be identified. In every case, the suggested alternate of the audio-fingerprinting scheme culminated in promising results.
Abstract (translated): Η μουσική, ανέκαθεν, έπαιζε ένα σημαντικό και μοναδικό ρόλο στην ανθρώπινη διασκέδαση και επικοινωνία. Στα τέλη του 19ου αιώνα, η χρήση της μουσικής προτάθηκε και πλέον έχει καθιερωθεί ως ένα βασικό εργαλείο που εφαρμόζεται σε ποικίλους ιατρικούς, επιστημονικούς και εκπαιδευτικούς τομείς. Στα μέσα της δεκαετίας του 1960, ένα πρωτοπόρο ερευνητικό πεδίο- γνωστό ως Ανάκτηση Μουσικής Πληροφορίας (Music Information Retrieval)- αναδείχθηκε, το οποίο στοχεύει, συνδυάζοντας τεχνικές επεξεργασίας σημάτων και Ανάκτησης Πληροφορίας, να λύσει διάφορα μουσικά προβλήματα, όπως για παράδειγμα τα προβλήματα αναγνώρισης μουσικών κομματιών και κατηγοριοποίησης μουσικού είδους. Η επίλυση του προβλήματος της αναγνώρισης μουσικών κομματιών αποτελεί το πιο δύσκολο πρόβλημα της Ανάκτησης Μουσικής Πληροφορίας. Κατά καιρούς, έχουν προταθεί διάφορες τεχνικές- από τις οποίες η πιο υποσχόμενη, ως προς τα αποτελέσματα, είναι το σχήμα των ακουστικών αποτυπωμάτων (the audio-fingerprinting scheme). Η μέθοδος εξαγωγής των ακουστικών αποτυπωμάτων προτάθηκε, για πρώτη φορά, τη δεκαετία του 1990, και επιδιώκει να δημιουργήσει μια μοναδική και συμπαγής αναπαράσταση -όμοια με εκείνη του ανθρώπινου δακτυλικού αποτυπώματος και ως εκ τούτου πήρε τη συγκεκριμένη ονομασία - του περιεχομένου σήματος ενός τραγουδιού. Με την πάροδο του χρόνου, διάφορες εναλλακτικές τεχνικές της καινοτόμου μεθόδου των ακουστικών αποτυπωμάτων έχουν προταθεί: Ορισμένες από τις οποίες βασίζονται στις συμβατικές τεχνικές επεξεργασίας σημάτων και στατιστικής, π.χ. ο Βραχυχρόνιος Μετασχηματισμός Fourier (Short-Time Fourier Transform), ενώ άλλες χρησιμοποιούν τεχνικές και έννοιες που εφαρμόζονται σε πιο πιονέροι σχήματα, όπως για παράδειγμα ο αλγόριθμος της Αντιστοιχισμένης Επιδίωξης (the Matching Pursuit algorithm) και τα λεξικά χρόνο-συχνότητας (time-frequency dictionaries) που χρησιμοποιούνται στα παραδείγματα της Συμπιεσμένης Δειγματοληψίας (Compressive Sensing) και Εκμάθησης Λεξικού (Dictionary Learning) αντίστοιχα. Στόχος της συγκεκριμένης διπλωματικής εργασίας είναι να προταθεί μια ρηξικέλευθη εναλλακτική προσέγγιση της τεχνικής εξαγωγής των ακουστικών αποτυπωμάτων. Η προτεινόμενη μέθοδος επιδιώκει να δημιουργήσει μοναδικές και συμπαγείς αναπαραστάσεις των ακουστικών σημάτων βάσει των αλγορίθμων της Ορθογώνιας Αντιστοιχισμένης Επιδίωξης (the Orthogonal Matching Pursuit algorithm) και K-SVD, δύο τεχνικές τελευταίας τεχνολογίας που εφαρμόζονται στα σχήματα της Συμπιεσμένης Δειγματοληψίας και Εκμάθησης Λεξικού αντίστοιχα. Η προτεινόμενη τεχνική, αρχικά, επιδιώκει να κατασκευάσει ένα καθολικό λεξικό χρησιμοποιώντας ποικίλα τραγούδια, που αποτελούν τη βάση δεδομένων, και του αλγορίθμου K-SVD. Το λεξικό επιχειρεί να συλλάβει όχι μόνο τα αντιληπτικά/ακουστικά γνωρίσματα των μουσικών σημάτων αλλά και την περιγραφικότητα, την ευρωστία και τη διακριτικότητα των ακουστικών αποτυπωμάτων. Στη συνέχεια, τα μουσικά κομμάτια που αποτελούν τη βάση δεδομένων καθώς και το απόσπασμα ενός άγνωστου τραγουδιού -που χρησιμοποιείται στο στάδιο της αναζήτησης του προτεινόμενου σχήματος- τεμαχίζονται σε πολλαπλά ακουστικά πλαίσια μικρής διάρκειας. Έπειτα, οι αραιές αναπαραστάσεις των μουσικών κομματιών- της βάσης δεδομένων- και του αποσπάσματος υπολογίζονται με τη βοήθεια του αλγορίθμου της Ορθογώνιας Αντιστοιχισμένης Επιδίωξης και του λεξικού, που κατασκευάστηκε προηγουμένως. Ύστερα, τα άτομα, δηλ. οι συντελεστές της αραιής αναπαράστασης ενός μουσικού σήματος, με τις υψηλότερες τιμές στάθμισης επιλέγονται και θεωρούνται ισοδύναμα με τα πιο περιγραφικά σημεία του φασματογραφήματος του εκάστοτε σήματος. Τα ζεύγη ορόσημων ( landmark pairs), δηλ. τα ζεύγη κορυφών που αποτελούνται από τέσσερα σημεία, κατασκευάζονται βάσει των εξαγόμενων ατόμων και χρησιμοποιούνται στη δημιουργία πινάκων κατακερματισμού. Το προτεινόμενο σχήμα κατασκευάζει ξεχωριστούς πίνακες κατακερματισμού για καθένα από τα τραγούδια της βάσης δεδομένων και για το απόσπασμα του άγνωστου μουσικού κομματιού. Στο στάδιο της αναζήτησης της προτεινόμενης τεχνικής, εφαρμόζονται διάφορες μέθοδοι ψηφίσματος, ώστε να βρεθεί σε ποιο μουσικό κομμάτι αντιστοιχεί το απόσπασμα. Τέλος, επιστρέφονται τα αντίστοιχα μετά-δεδομένα του τραγουδιού. Κατά την αξιολόγηση της προτεινόμενης προσέγγισης, πραγματοποιήθηκαν πολλαπλά πειράματα εφαρμόζοντας λεξικά διαφόρων διαστάσεων. Τα λεξικά κατασκευάστηκαν χρησιμοποιώντας δύο ακουστικά σύνολα δεδομένων, διαφορετικού μεγέθους, στο φασματικό και στο χρονικό πεδίο. Αρχικά, η προτεινόμενη μέθοδος εξετάστηκε ως προς ποιο λεξικό, δηλ. ποιες διαστάσεις και ποιο πεδίο, δίνει τα καλύτερα αποτελέσματα. Έπειτα, το προτεινόμενο σχήμα αξιολογήθηκε έναντι της ευρωστίας του. Με άλλα λόγια, η συγκεκριμένη τεχνική αξιολογήθηκε για το αν μπορεί να αναγνωρίσει αποσπάσματα άγνωστων τραγουδιών τα οποία έχουν παραμορφωθεί εξαιτίας της παρουσίας σθεναρού θορύβου. Τέλος, η προτεινόμενη τεχνική αξιολογήθηκε για το αν μπορεί να αναγνωρίσει αποσπάσματα άγνωστων μουσικών κομματιών, τα οποία δεν συμμετείχαν στην διαδικασία εκμάθησης των λεξικών. Αξίζει να σημειωθεί ότι, σε κάθε περίπτωση, η προτεινόμενη εναλλακτική προσέγγιση της τεχνικής της εξαγωγής των ακουστικών αποτυπωμάτων επέστρεψε αξιόλογα αποτελέσματα.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
text_v4.pdfΜετατυχιακή Διπλωματική Εργασία7.73 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.