以區域敏感雜湊函數進行哼唱選歌

Query By Singing/Humming using Locality Sensitive Hashing

張廷漢

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

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

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

摘要

摘要
在本論文中，我們使用區域敏感雜湊函數(LSH, locality sensitive hashing)來實作哼唱選歌(QBSH, query by singing/humming)系統，此系統可提供使用者哼或唱一首曲子，接著會將此使用者唱的曲子與資料庫當中的歌曲進行比對，最後回傳最相似的歌曲給使用者。
我們首先為了讓LSH能夠篩選出盡可能正確的結果，我們會對哼唱輸入的歌曲以及資料庫的歌曲使用線性伸縮來做前處理以及切成片段，接下來再使用LSH來找出與哼唱輸入的小片段較相似的資料庫片段，並將這些片段對應的歌曲列為候選歌曲，最後將相對應的哼唱輸入片段與資料庫片段延伸並做一對一的計算距離，最後從中選出距離最近的前十名來回傳給使用者。
在我們的實驗中，我們所使用的哼唱輸入總共有454首wav檔案，資料庫歌曲則是2048首midi檔案，Top1的正確率是61.23%，Top10的正確率是76.87%，平均一首哼唱輸入所花費的計算時間是3.87秒。
關鍵字： 哼唱選歌、線性伸縮、區域敏感雜湊函數

關鍵字

區域敏感雜湊函數 ； 哼唱選歌

並列摘要

Abstract
This paper proposes a query by singing/humming (QBSH) method based on locality sensitive hashing (LSH).The QBSH system allows a user to sing or hum a song, and the system compares this song with the songs in the database and returns the most similar song to the user.
First, we perform linear scaling to the segmented pitch vector of the user-sung or hummed tune in order to maximize the performance of LSH. LSH is then used to efficiently find relatively similar song segments in the database, and the corresponding songs of these song segments are labelled as candidate songs. Lastly the input pitch vector is compared with the candidate song segments to obtain the top-10 list.
In our experiments, we use a dataset with 454 input queries and 2048 MIDI songs in the database. Our method achieves a 61.23% top-1 accuracy, 76.87% top-10 accuracy. The average computation time is 3.87 second per query.
Keywords: QBSH、Linear Scaling、LSH

並列關鍵字

LSH ； QBSH

參考文獻

[1]Alexandr Andoni and Piotr Indyk "Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions". Communications of the ACM, vol. 51, no. 1, 2008, pp. 117-122.

[2]M. Datar, N. Immorlica, P. Indyk, and V. Mirrokni. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions. In Symposium on Computational Geometry (SOCG), 2004.

[3]M. Ryynänen and A. Klapuri, “Transcription of the singing melody in polyphonic music,” in Proc. 7th International Conference on Music Information Retrieval, 2006.

[4]Zhiyuan Guo, Qiang Wang, Gang Liu, Jun Guo, “Query By Humming By Using Locality Sensitive Hashing Based On Combination Of Pitch And Note” in Proc. Signal Processing, 2012.

[5]Zhiyuan Guo, Qiang Wang, Gang Liu, Jun Guo, “A Query By Humming System Based On Locality Sensitive Hashing Indexes” in Proc. 2012 IEEE, ICMEW.2012.58