基於線性伸縮之哼唱選歌系統的比對加速

Speeding Up Query-by-Singing/Humming Systems Based on Linear Scaling

林俊源(Jun-Yuan Lin)

指導教授 ： 張智星 ； 張俊盛

國立清華大學/電機資訊學院/資訊工程學系/碩士(2013年)

https://doi.org/10.6843/NTHU.2013.00697

摘要

哼唱選歌系統是一個讓使用者哼唱旋律後，經由該旋律和資料庫比對，尋找該使用者所哼唱的歌曲之檢索系統。以往在比對方法法上，採用動態時間伸縮 (dynamic time warping, DTW)或線性伸縮 (linear scaling, LS)，後者的辨識效果略遜於前者，但能有較快的辨識速度。
本研究之目的在於針對現有的採用線性伸縮之哼唱選歌系統進行修改，使其能在不損失過多辨識率的前提下，有更快的比對速度。本研究主要採用下列方法進行加速：避免重複比對資料庫中的重覆片段、降低取樣率、先比對1.0附近的伸縮比率或人氣較高的歌曲。
依據以上方法進行實驗後，結果顯示避免重複比對，以及降低取樣率的作法，可以較有效地減少辨識時間，而先比對1.0附近的伸縮比率，以及先比對人氣較高的歌曲的作法，儘管實驗顯示能夠有效提升辨識速度，但是在某些條件下幫助並不明顯。

關鍵字

哼唱選歌 ； 線性伸縮 ； 降低取樣率

並列摘要

A query-by-singing/humming (QBSH) System is a song searching system that enables the user to find a song by singing or humming the melody. The sung or hummed melody is compared to the songs in the database to find the closest match. Two common comparing methods are dynamic time warping (DTW) and linear scaling (LS). The former method has the advantage of higher recognition accuracy, while the latter is more efficient in terms of computation time.
The goal of this research is to improve current LS-based QBSH system so that the comparing time is reduced while not sacrificing too much recognition accuracy. In this thesis, the following approaches are taken to speed up the system: avoiding comparing the repeated patterns in a song, reducing the sample rate, comparing using the scaling ratios around 1.0 first, and comparing the songs with higher hit rate first.
The experimental results show that the former two methods (avoiding comparing the repeated patterns in a song, and reducing the sample rate) are able to reduce the comparing time effectively, while the other two methods cannot speed up the system evidently in some conditions.

並列關鍵字

Query by Singing/Humming ； Linear Scaling ； Down Sample

參考文獻

[1] 林子喬，「哼唱選歌於嵌入式卡拉OK系統之研究與實作」，碩士論文，國立清華大學資訊工程學系，民國九十八年六月。

[2] 方一帆，「哼唱選歌的改進方法與實作」，碩士論文，國立清華大學資訊工程學系，民國九十九年十月。

[3] Eamonn Keogh et al., Exact indexing of dynamic time warping, 28th International Conference on Very Large Data Bases, 2002.

[4] Thanawin Rakthanmanon et al., Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping, SIGKDD, 2012.

[5] Xiao Wu et al., A Top-down Approach to Melody Match in Pitch Contour for Query by Humming, Institute of Acoustics, Chinese Academy of Sciences, 2006.