一種基於哼唱的音樂資料庫高效查詢方法
2023-05-11 05:27:31 2
專利名稱：一種基於哼唱的音樂資料庫高效查詢方法
技術領域：
本發明涉及一種查詢音樂資料庫的方法，尤其涉及一種基於哼唱實現查詢的音樂資料庫查詢方法，屬於多媒體資料庫技術領域。
背景技術：
在數字圖書館、網上音樂銷售、歌廳點歌服務、個人音樂欣賞、音樂研究、樂曲版權裁決等多個領域，每天都要大量使用數位化的音樂數據。這些音樂數據在使用上存在一個難題，就是很難滿足用戶基於內容查詢非格式化音樂數據的要求。也就是說，如果用戶聽到一段很好聽的音樂，想通過自己記憶的音樂片斷來查詢整首音樂的數據，目前在技術上仍然存在較大的實現難度。
現有的音樂資料庫管理系統只能有效地管理格式化數據，支持對於歌名、作曲、演唱人等格式化數據的查詢要求。但至今為止，沒有任何成熟的資料庫產品能滿足對基於內容的音樂數據查詢要求。近年來，基於內容的音樂檢索技術吸引了越來越多人的注意，包括資料庫技術、數位訊號處理、模式識別、知識發現等眾多領域的科學家開始共同探討這一新的技術挑戰。
在基於內容查詢的音樂資料庫檢索中，通過哼唱內容實現查詢是最基本的實現方式之一。它是指用戶輸入一段用樂器演奏的樂曲，或通過麥克風哼的一段曲子，吹的一段口哨，唱的一句歌，而且這些輸入還可能包括某些錯誤時，系統能正確地返回用戶想要查詢的樂曲。
在基於哼唱的音樂信息檢索領域中，查詢處理算法一直是一個關鍵的研究課題。目前，已經提出不少算法，但這些算法中，可以容錯的、查詢準確率高的算法一般效率較低；而效率較高的算法，一般容錯性能較差，只能執行精確查詢。另外，在音樂資料庫中，大多數情況下用戶的查詢輸入是包含某些錯誤的，但希望系統返回的卻是唯一的一首目標樂曲，而不是通常的一組結果。因此，有效評價一個音樂資料庫系統的查詢性能的不是查全率與查準率，而是查詢的前三位的命中率。針對這一特點，目前提出的查詢算法主要有三類第一類是使用最多的計算編輯距離的動態規划算法。第二類是計算基本的歐式距離和為改進查找精度的各種改進的距離的算法，如概率矩陣距離、轉移距離(Transportation distance)等等。第三類是隱馬爾科夫模型的方法。
在這三類算法中，計算編輯距離的方法與隱馬爾科夫模型的方法具有很好的容錯的功能，有關研究表明，隱馬爾科夫模型的方法對不同類型的音樂還有很好的適應性。但是這兩類算法對每個查詢均要檢查存放在資料庫中的所有樂曲的特徵表示，當資料庫中的曲目越來越多時，查詢的速度也越來越低。計算歐式距離及各種改進的距離的方法，雖然計算速度高於其它兩類算法，但算法的容錯性較差。
現有的技術已經可以實現在1000首到3000首的樂曲庫中取得的65％～75％的前5位命中率。但這些技術中有的要求必須從樂曲的開頭哼唱，違反了大部分查詢是對樂曲的主題或者是高潮進行的這個客觀事實；有的要求用戶整小節地哼唱旋律，而事實上有相當多的樂曲，樂句與小節的起始位置是不一樣的，即用戶的查詢不是從小節開始的；還有的要求用戶必須在一個節拍器伴奏下哼唱，以保證節奏基本上是正確的，這是很不方便也不切合實際的。
另外，在上述基於哼唱的音樂信息檢索領域中，實現較快的查詢速度也是十分重要的。索引技術是加快查詢速度的重要手段。在音樂資料庫研究中已經提出一些索引方法，如後綴樹索引，表列索引(1D-List，2D-List)，基於n-gram(n元語法)的索引等。在這些索引中，後綴樹索引，表列索引是內存索引結構，在數據量非常大時，顯然是不能滿足應用需要的。將n-gram方法和各類外存的索引結構結合，可以建立各類n-gram索引，但傳統的索引結構只支持精確查詢，要支持近似查詢，必然要採用查詢擴充的方法，將用戶給出的查詢，用添加錯誤的方法，擴充成包含1～n個錯誤的多個查詢，再利用索引進行查詢。對於音樂檢索的情況，一般查詢在12-25個音符之間，所擴充的查詢數目是n的指數級，查詢效率仍不理想。
公開號為CN1703734的發明專利申請「從聲音確定音符的方法和裝置」提供了一種提取高級別音樂結構的方法。利用該方法，哼唱或其他發音方式通過梯度分割等技術手段被轉換成為一序列音符，以代表用戶試圖表達的旋律。這些檢索音符的每一個包含信息，如音高，開始時間和持續時間，以及所述序列包含每個音符的相對順序。利用該方法，有利於實現基於內容查詢的音樂資料庫檢索。
公開號為CN1737797的發明專利申請「基於內容的數位音樂檢索旋律特徵資料庫及生成系統」公開了一種基於內容的數位音樂檢索旋律特徵資料庫及生成系統，包括數位音樂素材庫存儲部、數位音樂文件讀取和旋律特徵提取部、旋律分段特徵音符檢測部、旋律特徵模板生成部、音樂旋律特徵模板庫存儲部。數位音樂文件讀取和旋律特徵提取部讀取數位音樂素材庫存儲部的音樂文件，經過旋律分段特徵音符檢測部對其進行旋律段位置特徵的檢測及標註後，被送至旋律特徵模板生成部，得到旋律特徵模板數據文件，並被保存到音樂旋律特徵模板庫存儲部中，同時由旋律特徵模板生成部發出生成流程完畢的通知給數位音樂文件讀取和旋律特徵提取部。其中，旋律分段特徵音符檢測部是基於音符類別特徵及其音符長度特徵來進行的。先由消除可忽略靜音段處理模塊搜索標準旋律的音符特徵序列，若查找到的音符長度小於某一預先設定的靜音段長度閾值則將該音符加以刪除，並將此段併入前一個音符的發音段，在刪除了可忽略的靜音段後，則由特徵音符檢測處理模塊根據音符類別特徵及其音符長度特徵來對標準旋律中的每個音符進行檢測，特徵音符類別分為定位類特徵音符和休止類特徵音符，對於這兩類音符均按其各自的音符長度是否超過事先所設定的特徵音符閾值來確定該音符是否為分段特徵音符。該發明既能保持對用戶哼唱輸入的容錯性，同時還能提高系統對哼唱輸入的匹配檢索速度。
發明內容
本發明的目的在於，針對現有技術中可容錯的算法查詢效率低，而高效算法又難於容錯的現實問題，根據人對樂曲相似的理解，提供一種基於單側連續匹配、可容錯的音樂資料庫查詢方法。
為實現上述的發明目的，本發明採用下述的技術方案一種基於哼唱的音樂資料庫高效查詢方法，其特徵在於(1)提取用戶輸入的待查詢樂曲的旋律輪廓；(2)對所述旋律輪廓按照n元語法方法進行切分，並對生成的查詢集進行擴充；(3)以擴充後的查詢集中的每個元素為查找項，查找hash索引，獲得中間結果；(4)將所有的中間結果按照樂曲編碼排序，得到與輸入部分匹配的每個樂曲的旋律輪廓；(5)計算中間結果中的每個樂曲的匹配度；(6)選擇匹配度最高的若干樂曲編碼，取其相應樂曲名返回用戶。
其中，被查詢的音樂資料庫通過如下步驟獲得(1)提取樂曲的旋律輪廓；(2)對所述旋律輪廓按照n元語法方法進行切分；(3)對所有切分後的片段，將其二進位編碼作為旋律輪廓索引的hash碼，以樂曲編碼和片段的第一個音符在樂曲中的位置作為記錄項，建立順序的hash索引；(4)建立樂曲編碼與樂曲名的對照表；(5)將樂曲插入音樂資料庫。
所述旋律輪廓根據樂曲的音高和/或音長特徵值獲得。
將用戶查詢片段的旋律輪廓按照滑動窗口方法分片，每次右移一個音符，將查詢分成更小的片段，然後再對查詢結果進行合成計算，得到擴充的查詢集。
從第一個匹配位置開始，檢查輸入的特徵表示與中間結果的匹配位置，計算單側連續匹配長度，並從第一個匹配位置開始，加上輸入特徵長度，再加一個閾值計算相應總匹配音符數。
取最大的相應總匹配音符數和與之對應的單側連續匹配長度作為樂曲的總匹配音符數和單側連續匹配長度，將所餘樂曲的總匹配音符數和單側連續匹配長度排序，取排在前列的結果作為結果集，取其相應的樂曲名返回用戶。
對每一首樂曲的旋律輪廓按照滑動窗口的方法分片，對每一片段取其音高與音長的旋律輪廓的二進位編碼作為索引項，與樂曲的編碼和片段中第一音符在歌曲中位置共同組成數據記錄，建立hash索引文件；在所述hash索引文件中，按照樂曲的順序排列索引數據。
本發明所提供的基於哼唱的音樂資料庫高效查詢方法採用了順序hash索引，顯著提高了查詢的速度和精度。用本發明方法對217首MIDI樂曲和60個包含各種錯誤的查詢進行查詢測試，可以取得70％的第一位命中率和95％的前三位命中率。將數據集擴大為78000首網上收集的MIDI樂曲段，並將查詢擴充至1000個，可以取得70％的第一位命中率，79％的前三位命中率和85％的前十位命中率。
下面結合附圖和具體實施方式
對本發明作進一步的說明。
圖1為本發明所示方法中，提取樂曲的特徵、建立待查詢的音樂資料庫的流程示意圖。
圖2所示為進行音符基本切分時的音高示意圖。
圖3所示為進行音符細化切分時的音高示意圖。
圖4為通過上述的音樂資料庫實現基於哼唱的音樂數據查詢的過程示意圖。
圖5為基於本發明所述方法實現的一個基於內容查詢的音樂資料庫的整體框架示意圖。
具體實施例方式
本發明所提供的音樂資料庫查詢方法分為兩個過程。首先是如圖1所示的提取樂曲的特徵，建立待查詢的音樂資料庫的過程。其次是如圖4所示的通過已經建立的音樂資料庫，實現基於哼唱的音樂數據查詢的過程。下面，分別對此展開詳細的說明。
在音樂信息檢索中，對樂曲的處理都是通過對音樂特徵值進行的。因此在音樂文件中提取樂曲的特徵值是很重要的。在系統查詢時，用戶的哼唱也是先提取特徵值，再與資料庫中的樂曲特徵值進行相似比較。
樂曲的特徵值有多種，包括音高、音長、強度、音色等。在現有的技術中，通常檢索只採用音高、音長的特徵，也可以只採用音高特徵或音長特徵。
在本發明所提供的方法中，是按照樂曲的旋律的音高、音長輪廓計算樂曲的相似度的。因此如圖1所示，作為第一步，對所有入庫的樂曲，首先要提取樂曲音高、音長特徵值，並進一步提取樂曲的旋律輪廓。
對所有樂曲提取旋律輪廓特徵後，每首樂曲可以由其旋律輪廓特徵表示，索引的建立和用戶的查詢都是基於所提取的旋律輪廓特徵進行的。
目前，最常見的數位音樂格式是MIDI文件和波形文件，如.WAV文件等。其它格式的數位音樂文件很容易通過軟體轉換為MIDI文件或波形文件。因此，在本方法的實施例中，規定樂曲庫採用MIDI文件，而用戶的哼唱採用波形文件。
參照《數位訊號處理—原理、算法與應用》((美)John G.Proakis，Dimitris G.Manolakis著，ISBN 7-5083-2499-4)和《網上多媒體信息分析與檢索》(莊越挺、潘雲鶴、吳飛，ISBN 7-302-05584-X)中的有關說明，從MIDI文件中很容易提取出音符的音高和音長特徵，而從波形文件中很容易提取出音符的音高特徵。其具體的過程作為現有的技術，在此就不詳細說明了。
在本發明所述的方法中，為了清楚起見，對樂曲的音高、音長特徵採取相對表示的方法。具體而言，在樂曲中，後一個音符的音高與前一個音符的音高相比，只可能是高、低、相同三種情況，我們分別用U(p)、D(own)、S(ame)三個字母表示，因此一般的旋律音高輪廓可以用U、D、S序列來表示。另外，在樂曲中，後一個音符的音長與前一個音符的音長相比，只可能是長、短、相同三種情況，我們分別用L(ong)、S(hort)、E(qual)三個字母表示，因此一般旋律音長輪廓可以用L、S、E序列來表示。
對於音長特徵的提取，參照圖2所示的音高示意圖，本發明中採用基於能量變化和音高變化的方法進行音符切分，具體步驟如下1.利用能量變化進行基本切分(1)判斷起始點利用信號能量的變化得到哼唱輸入的起始點。當輸入信號的能量超過預先設定的門限值，則認為是哼唱輸入的起始點，濾除起始點的靜音部分。
(2)判斷結尾靜音點使用與上述相同的方法濾除結尾段的靜音部分。
(3)確定切分點使用動態門限的方法得到能量曲線的峰值點，將峰值點對應的音高曲線部分作為切分點(置為零)。
在完成基本的切分之後，將首尾部分的毛刺去除，得到音符的初步切分結果。這種對音符的初步切分方法在唱詞過於連貫的部分不易得到準確的切分結果，因此可以進一步根據音高曲線的變化進行細切分。
圖3為利用音符、音高變化進行進一步細切分的示意圖。參照圖3所示，在音高曲線上，從起始點開始，以一個很小的幀數值為窗長進行加矩形窗處理，計算窗內的音高均值，然後以步長1幀進行擴窗，每次擴窗的同時，計算窗內的音高均值，並對前後結果進行比較。如果差分結果在1個半音以內，則繼續進行擴窗，如果差分結果大於1個半音，則停止擴窗，並作切分標記。如果遇到零點則自動停止擴窗，並從下一個音高不為零的位置開始新的擴窗操作，直到結尾靜音點，得到最終切分結果。這一方法可以得到更準確的音符、音高切分結果。
在提取了樂曲的音高、音長旋律輪廓之後，下一步是對旋律輪廓按照n-gram(n元語法)方法進行切分。對所有切分後的片段，以其二進位編碼作為旋律輪廓索引的hash(哈希)碼，以樂曲編碼和片段的第一個音符在樂曲中的位置作為記錄項，建立hash索引。這裡所說的n-gram方法是自然語言計算機處理領域常用的方法，以前通常用在大詞彙連續語音識別技術中，。在音樂資料庫查詢中，由於與語音識別所處理的對象是類似的，n-gram方法很容易移植過來使用。
具體而言，本發明中，首先將所有樂曲的旋律輪廓按照滑動窗口的方法分片，窗口長度為n。對每一片段取其音高與音長的旋律輪廓的二進位編碼作為索引項(對U、S、D分別用01，10，11表示，對L、S、E分別用01，10，11表示)，與樂曲的編碼和片段中第一音符在歌曲中位置共同組成數據記錄，建立hash索引文件。
在上述步驟所產生的hash索引文件中，具有相同的hash碼值的記錄放在相同的塊中。hash記錄中只有樂曲的編碼和片段中第一音符在歌曲中的位置，其記錄格式為 。
由於在建立hash索引文件時是一首一首樂曲來順序建的，之後也沒有更新操作，因此在hash索引文件中，有關的數據是有序的。換句話說，建立的是順序hash索引。這種順序hash索引在以後的查找處理時，可以大大提高查詢的效率。
上述步驟完成之後，下面的步驟是建立樂曲編碼與樂曲名的對照表，並將樂曲插入樂曲庫。這是本領域一般技術人員都能勝任的簡單操作，在此就不詳細說明了。
通過上面所描述的步驟，就建立了一個待查詢的音樂資料庫。下面，結合圖4對如何利用該資料庫實現基於哼唱的樂曲查詢進行詳細的說明。
如圖4所示，用戶在通過哼唱進行查詢時，首先需要按照圖2和圖3所示的內容提取樂曲的音高、音長旋律輪廓，並將旋律輪廓按照n-gram方法進行切分，得到待查詢的數據。這在前文中已經有詳細的說明，在此不予贅述。
但是，這一步驟所得到的待查詢數據並不適合直接用作上述樂曲資料庫的查詢選項。這是因為由用戶所哼唱的旋律往往會包含很多的錯誤，特別是音高、音長等參數，錯誤的概率相當高。因此，直接使用用戶所哼唱的旋律進行查詢，往往不能獲得用戶所希望的結果。在實踐中，對於音樂資料庫的查詢，多採取近似查詢的思路。近似查詢的一般方法是將查詢輸入串的特徵表示與音樂資料庫中所有樂曲的特徵表示一一比較計算，找出最接近輸入串的樂曲作為查詢結果返回用戶。但是，當資料庫所存儲的樂曲較多的時候，這種方法因耗時太多，基本上是不可行的。支持快速查詢的基本方法是使用索引，在現有的成熟索引方法中，大多數索引方法只能支持嚴格匹配查詢。R樹類索引雖然能支持近似查詢，但當輸入的特徵向量的維數大於5時效率很低，不適用音樂檢索的情況。
在本發明中，為了減少用戶哼唱旋律錯誤所產生的影響，採取對已有的查詢集進行擴充，使之包含一定範圍內的錯誤查詢集的解決思路。
具體而言，為了得到該擴充的查詢集合，我們將用戶查詢片段的旋律輪廓按照滑動窗口方法分片，每次右移一個音符，將查詢分成更小的片段，然後再對查詢結果進行合成計算，給出最終結果。
滑動窗口的長度與資料庫中n-gram索引中的n相同。若用戶查詢所包含的音符數為m，則查詢所分片數為m-(n-1)＝m-n+1。將每一片作為一個查詢，則所生成的查詢數目遠小於一般查詢擴展方法。
例如若查詢片斷為「DDDSUDUDUD」，n＝4，m＝10，則查詢分解為「DDDS」、「DDSU」、「DSUD」、「SUDU」、「UDUD」、「DUDU」、「UDUD」7個片斷。所要執行的查詢只有7個，大大小於前兩種方法。
設查詢目標序列為「DDDSUDUDUD」，而查詢輸入中錯了一個音符，為「DDDSUUUDUD」(下劃線所示)，則做n-gram分解後為「DDDS」、「DDSU」、「DSUU」、「SUUU」、「UUUD」、「UUDU」、「UDUD」7個片斷。而將查詢結果按照片段位置合成後可以得到的目標序列及對應的音符位置為DDDSU D UDUD1 2 3 4 5 7 8 9 10可以計算得到目標序列的最長單側連續匹配長度為9，總匹配數為9。
對於上述擴充後的每一個查詢，查找hash索引。若擴充後的查詢集合為k個，則查找索引後得到的中間結果集合為k個。對k個中間結果集合，採用類似合併排序的方法，按照樂曲序號和音符位置拼湊結果特徵序列，計算中間結果中每個樂曲的匹配情況。
需要說明的是，這裡的匹配是一種近似匹配運算。在本匹配算法中，是根據樂曲片斷的總匹配音符數和最大單側連續匹配的長度，判斷哪一個目標樂曲的特徵表示更接近輸入串的特徵表示的。
由於每個查找項對應一個中間結果，而這些中間結果中的數據是按照樂曲編碼和片斷的第一個位置順序排列的，因此很容易找到同一樂曲與查找項匹配的所有位置。
為了便於理解上述的計算思路，下面介紹本發明人進行的一個有關實驗及其結果分析。
該試驗的具體內容是這樣的選10首中國傳統民歌，每個歌選擇一句，構造試驗。
試驗測試集是按照每隔3個音符，就按照旋律輪廓的方向提高或降低兩個半音的方法生成10首樂句的測試集，再分別按照旋律輪廓的方向提高或降低3個半音，4個半音、5個半音和按照旋律輪廓的相反方向提高或降低1個音的方法，生成50首樂句的測試集。再每隔4個音符按同樣的方法生成50首歌的樂句的測試集。再每隔5個音符按同樣的方法生成50首歌的樂句測試集。
通過初步試聽，我們得到如下結論1)人對旋律方向相同的錯誤的容錯性最好，如果每隔3個音在與旋律相同的方向上改變6個半音，人仍認為是同一支歌，只是走調兒(包含錯誤)而已。
2)人對旋律方向不同的錯誤的容錯性最差，對於80％以上的樂曲，如果每隔3個音在與旋律方向不同的方向上改變1-2個半音，人就認為不是同一支歌了。
3)人認為連續相同音符最多的兩段樂曲最相似。
如樂曲「兩隻老虎」的第一句，樂譜應為12 31|12 31|3 4|5-|3 4|5-|，若為12 31|12 31|3 4|5-|6 6|7-|，人們仍能分辨出是「兩隻老虎」，此時雖與原曲編輯距離為3，但連續正確的音符數為11。但如果改為下面樂譜12 35|12 35|3 4|5-|6 4|5-|，此時與原曲編輯距離也為3，但沒有一個人會認為要查詢的歌是「兩隻老虎」，而認為要查詢的是一首他們不知道的歌。將此查詢的特徵值與資料庫中「兩隻老虎」的特徵值比，發現連續正確的音符數為3、3、3、2，最長連續正確音符數只有3。
從這個例子可以看到，錯誤音符在查詢中的位置對相似的識別非常重要。當錯誤音符分散出現在音符序列中間，使序列中連續正確音符分成若干段，而每個段都少於4個音符，人則認為不是同一首歌。如查詢是8個音符，錯誤出現在第3、6兩個音符，則人們認為哼唱輸入的與目標樂曲不是一首歌。
通過上述的試驗結果發現，用戶輸入錯誤最多的是旋律輪廓所能包含的錯誤，如本來樂曲的第i個音應比第i-1個音高半個音，而輸入串中比第i-1個音高了一個音。其次是漏音符(稱為刪除音符)的錯誤，多音符(稱為插入音符)的錯誤，較少(少於10％)是在旋律輪廓方向上的錯誤(如本來應該第i個音比第i-1個音高一個音，卻唱成比第i-1個音低一個音)。
為了使查詢在包含不同的錯誤的情況下，仍能以接近人能容錯的標準查到目標樂曲，我們結合上述的實驗結果，提出了基於單側連續匹配(one sideconsecutive match)的近似匹配標準。
設有字符串a1，a2，…….an，和b1，b2，……bm，若其中bi＝aj，(m＞i＞＝1，n＞j＞＝1)，bi+1＝aj+1，…….bi+k＝aj+k，bi+k+r＝aj+k+p，(r可取值0-2，p為根據經驗給定的閾值)bi+k+r+1＝aj+k+p+1，…….bi+k+r+q＝aj+k+p+q，(m-k-i＞＝q＞＝0)則稱字符串a1，a2，…….an，和b1，b2，……bm滿足單側連續匹配，k+q記為單側連續匹配長度。
兩個字符串a1，a2，…….an和b1，b2，……bm可以有多個單側連續匹配長度，定義其中最大的一個為兩個字符串的最大單側連續匹配長度。
例如字符串「abcdefgh」與字符串「abckmdefgh」根據定義滿足單側連續匹配，其連續匹配長度為8。字符串「abcdefghijklm」與字符串「abcdexyzjklm」根據定義也滿足單側連續匹配，其連續匹配長度為5，4，最大單側連續匹配長度為5。
從給出的單側連續匹配的定義和上例中可以看出，儘管輸入串的特徵表示包含插入、刪除和唱錯音符方面的錯誤，但均可以與目標樂曲的特徵表示在不同程度上滿足單側連續匹配。根據視聽試驗的結論，在兩個片斷總匹配音符同樣的情況下，單側連續匹配長度越大，人認為越相似。
基於上述的分析思路，從第一個匹配位置開始，檢查輸入的特徵表示與中間結果的匹配位置，計算單側連續匹配長度，並從第一個匹配位置開始，加上輸入特徵長度，再加一個閾值(此閾值為允許用戶漏掉音符的個數，根據試驗，該數值以不大於5為好)計算相應總匹配音符數。
一首樂曲可能有多處音符與輸入相匹配，本發明中，取最大的相應總匹配音符數和與之對應的單側連續匹配長度作為樂曲的總匹配音符數和單側連續匹配長度。
若樂曲的總匹配音符數少於輸入長度的1/2，則將此樂曲放棄。
將所餘樂曲的總匹配音符數和單側連續匹配長度排序，取排在前列的結果例如前10名作為結果集，取其相應的樂曲名返回用戶。
在本發明中，將資料庫中樂曲與查詢的旋律輪廓特徵表示均按照n-gram方法分片，當n＝5時，每次查詢所得到的中間結果不多，查詢速度很快，一般在零點零幾秒到零點幾秒，但是這樣在有插入刪除錯誤或旋律方向錯誤，尤其是包含多個這類錯誤時，有可能得不到正確結果。對此可行的方法是減少滑動窗口長度，例如減為3，這樣可以對包含更多錯誤的輸入查出正確結果，但對於包含近10萬首歌曲的資料庫來說，查詢的效率要降低2～3個數量級。為此，本發明人給出了如下的優化策略1.對用戶給出的查詢按照長度n劃分。
如對查詢序列「DDDSUDUDUUD」按照長度3劃分，則得到「DDD」，「SUD」，「UDU」，「UDx」四個片斷。(其中x為通配符)2.用劃分的片段，查找hash索引。
3.將查詢結果按照片段所屬樂曲序號和片段第一個音符位置合成後，計算音符總匹配數，若音符總匹配數＝查詢音符總數。將結果直接返回。否則，執行4。
4.對用戶給出的查詢按照n-gram方法，取n＝3進行分片，查找索引，對查詢結果計算按照片段所屬樂曲序號和片段第一個音符位置合成後，計算總匹配數與單側連續匹配長度，並按照其排序，將結果返回。
以下利用圖5所示的基於內容查詢的音樂資料庫來介紹本發明所述方法在試驗中獲得的結果，以形象地說明本方法的優點。
為了檢驗算法的有效性，本發明人分別對217首經過人工篩選確認的MIDI樂曲庫和網上收集的、未經篩選的(可能有重複的)78000首MIDI樂曲庫分別作了對比試驗。
實際的樂曲庫為217首中國流行音樂MIDI樂曲時。得到如下結果當輸入不包含錯誤時，三種方法的前三位命中率均為100％。當用包含各種錯誤的60個查詢，查詢長度為15，進行測試時，本文提出的方法前三位命中率為95.5％，第一位的命中率為70％。
編輯距離的方法，查詢前三位命中率為92.5％，第一位的命中率為75％。計算歐氏距離的方法，對只包含一個錯誤的查詢，前三位命中率為55％，對包含兩個以上錯誤的查詢，前10位命中率低於30％。
測試結果由表1概括如下
表1三種方法對217首MIDI樂曲和60個查詢輸入的命中率對比查詢一首曲目所用時間，如表2所示。
表3三種方法對217首和1000首MIDI樂曲庫查詢時間對比從表2中可以看到，在217首的資料庫中，本發明所提出的方法查詢所用時間比編輯距離的方法快近兩個數量級。
當實際的樂曲庫為78000首中國MIDI樂曲時，計算編輯距離的方法與計算歐氏距離方法由於耗費時間太長，無法進行比較，本發明人只進行了本方法的測試。
由於實際大數據量的查詢測試集難於收集，我們隨機截取資料庫中1000個樂曲片段(平均長度為14個音符)，按照10％無錯誤，50％為與旋律輪廓方向相同的錯誤，10％為包含一個旋律輪廓方向相反的錯誤或有一個插入、刪除錯誤，10％為包含兩個旋律輪廓方向相反的錯誤或有一個插入、刪除錯誤，20％包含三個旋律輪廓方向相反的錯誤或有三個插入、刪除錯誤，且隨機選取錯誤的位置，構造了1000個查詢。這裡，我們將包含三個錯誤的查詢增加到20％，為的是更多的考驗效果最差的情況。
雖然只有較少的用戶會唱出與旋律輪廓方向相反的錯誤，但在產生插入和刪除錯誤時，也可能連帶產生與旋律輪廓方向相反的錯誤，如對樂譜12315，其音高的輪廓用USD序列表示則為*UUDU，唱成123165，則其音高輪廓為*UUUDD，不僅多了一位，而且由於這多出的一位，後面的一位也錯了，致使由於插入一個音符產生兩個錯誤。這也是我們在1000個查詢中構造40％的這類錯誤，以驗證我們算法有效性的原因。
測試結果如表3所示。
表3對78000首MIDI樂曲段，1000個查詢輸入的測試結果從試驗結果可以看到，當用戶輸入正確，或只包含與旋律輪廓方向相同的錯誤，可以得到100％的第一位命中率，因此，佔有很大比例的只有這一類錯誤的用戶，可以得到滿意的查詢結果。從試驗結果還可以看到用戶查詢中所包含的錯誤越少，前三位的命中率越高。
在上述測試中，我們是採用隨機的方法由程序自動產生錯誤音符的位置，檢查沒有進入前10位的，和沒有進入前三位的查詢，有相當多的部分是由於產生錯誤音符的位置在15個音符位置中是分散的，使得查詢輸入的旋律輪廓特徵表示與目標樂曲的旋律輪廓特徵表示的最大單側連續匹配的音符數只有3，這樣的輸入，在人聽來也不是目標樂曲，系統查不出來也是應當的。如果對來自網絡的樂曲數據作了清理，去掉重複，命中率還可以進一步提高。
上面雖然通過具體實施方式
描繪了本發明，但本領域普通技術人員知道，本發明有許多變形和變化而不脫離本發明的精神，所附的權利要求將包括這些變形和變化。
權利要求
1.一種基於哼唱的音樂資料庫高效查詢方法，其特徵在於(1)提取用戶輸入的待查詢樂曲的旋律輪廓；(2)對所述旋律輪廓按照n元語法方法進行切分，並對生成的查詢集進行擴充；(3)以擴充後的查詢集中的每個元素為查找項，查找哈希索引，獲得中間結果；(4)將所有的中間結果按照樂曲編碼排序，得到與輸入部分匹配的每個樂曲的旋律輪廓；(5)計算中間結果中的每個樂曲的匹配度；(6)選擇匹配度最高的若干樂曲編碼，取其相應樂曲名返回用戶。
2.如權利要求1所述的基於哼唱的音樂資料庫高效查詢方法，其特徵在於被查詢的音樂資料庫通過如下步驟獲得(1)提取樂曲的旋律輪廓；(2)對所述旋律輪廓按照n元語法方法進行切分；(3)對所有切分後的片段，將其二進位編碼作為旋律輪廓索引的哈希碼，以樂曲編碼和片段的第一個音符在樂曲中的位置作為記錄項，建立順序的哈希索引；(4)建立樂曲編碼與樂曲名的對照表；(5)將樂曲插入音樂資料庫。
3.如權利要求1或2所述的基於哼唱的音樂資料庫高效查詢方法，其特徵在於所述旋律輪廓根據樂曲的音高和/或音長特徵值獲得。
4.如權利要求3所述的基於哼唱的音樂資料庫高效查詢方法，其特徵在於通過如下步驟實現音符基本切分，獲得音長特徵(1)判斷起始點利用信號能量的變化得到哼唱輸入的起始點，當輸入信號的能量超過預先設定的門限值，則認為是哼唱輸入的起始點，濾除起始點的靜音部分；(2)判斷結尾靜音點使用與上述相同的方法濾除結尾段的靜音部分；(3)確定切分點使用動態門限的方法得到能量曲線的峰值點，將峰值點對應的音高曲線部分作為切分點。
5.如權利要求3所述的基於哼唱的音樂資料庫高效查詢方法，其特徵在於通過如下步驟實現音符的細切分，獲得音長特徵(1)在音高曲線上，從起始點開始，以一個很小的幀數值為窗長進行加矩形窗處理，計算窗內的音高均值；(2)以步長1幀進行擴窗，每次擴窗的同時，計算窗內的音高均值，並對前後結果進行比較，如果差分結果在1個半音以內，則繼續進行擴窗，如果差分結果大於1個半音，則停止擴窗，並作切分標記；(3)遇到零點則自動停止擴窗，並從下一個音高不為零的位置開始新的擴窗操作，直到結尾靜音點，得到最終切分結果。
6.如權利要求1所述的基於哼唱的音樂資料庫高效查詢方法，其特徵在於所述步驟(2)中，將用戶查詢片段的旋律輪廓按照滑動窗口方法分片，每次右移一個音符，將查詢分成更小的片段，然後再對查詢結果進行合成計算，得到擴充的查詢集。
7.如權利要求1所述的基於哼唱的音樂資料庫高效查詢方法，其特徵在於所述步驟(5)具體包括如下步驟從第一個匹配位置開始，檢查輸入的特徵表示與中間結果的匹配位置，計算單側連續匹配長度，並從第一個匹配位置開始，加上輸入特徵長度，再加一個閾值計算相應總匹配音符數。
8.如權利要求1所述的基於哼唱的音樂資料庫高效查詢方法，其特徵在於所述步驟(6)中，取最大的相應總匹配音符數和與之對應的單側連續匹配長度作為樂曲的總匹配音符數和單側連續匹配長度，將所餘樂曲的總匹配音符數和單側連續匹配長度排序，取排在前列的結果作為結果集，取其相應的樂曲名返回用戶。
9.如權利要求1所述的基於哼唱的音樂資料庫高效查詢方法，其特徵在於對於海量的音樂資料庫，進一步採取如下步驟(1)對用戶輸入的待查詢樂曲按照長度n進行劃分；(2)用劃分的片段，查找哈希索引；(3)將查詢結果按照片段所屬樂曲序號和片段第一個音符位置合成後，計算音符總匹配數，若音符總匹配數等於查詢音符總數，將結果直接返回；否則執行(4)；(4)對用戶輸入的待查詢樂曲按照n元語法方法進行分片，查找索引，對查詢結果計算按照片段所屬樂曲序號和片段第一個音符位置合成後，計算總匹配數與單側連續匹配長度，並按照其排序將結果返回。
10.如權利要求2所述的基於哼唱的音樂資料庫高效查詢方法，其特徵在於所述步驟(3)中，對每一首樂曲的旋律輪廓按照滑動窗口的方法分片，對每一片段取其音高與音長的旋律輪廓的二進位編碼作為索引項，與樂曲的編碼和片段中第一音符在歌曲中位置共同組成數據記錄，建立哈希索引文件；在所述哈希索引文件中，按照樂曲的順序排列索引數據。
全文摘要
本發明提供了一種基於哼唱的音樂資料庫高效查詢方法，其特徵在於(1)提取用戶輸入的待查詢樂曲的旋律輪廓；(2)對旋律輪廓按照n元語法方法進行切分，並對生成的查詢集進行擴充；(3)以擴充後的查詢集中的每個元素為查找項，查找哈希索引，獲得中間結果；(4)將所有的中間結果按照樂曲編碼排序，得到與輸入部分匹配的每個樂曲的旋律輪廓；(5)計算中間結果中的每個樂曲的匹配度；(6)選擇匹配度最高的若干樂曲編碼，取其相應樂曲名返回用戶。有關試驗結果表明，本發明所提供的方法的性能明顯優於現有的其它方法。
文檔編號G06F17/30GK1940926SQ20061006575
公開日2007年4月4日 申請日期2006年3月15日 優先權日2006年3月15日
發明者劉怡, 郝雲飛, 許潔萍, 胡楠, 袁斌 申請人:中國人民大學