哼唱檢索中基于分段信息的 匹配算法研究 申請清華大學(xué)工學(xué)碩士學(xué)位論文) 培 養(yǎng) 單 位 ： 計算機科學(xué)與技術(shù)系 學(xué) 科 ： 計算機科學(xué)與技術(shù) 研 究 生 ：曹文曉 指 導(dǎo) 教 師 : 鄭方研究員 二一年六月 摘 要 要 哼唱檢索是基于音樂內(nèi)容的檢索，比傳統(tǒng)的基 于描述信息的音樂檢索更人性化。 在哼唱檢索系統(tǒng)中，用戶通過麥克風(fēng)等音頻輸 入設(shè)備哼唱幾句歌詞，接著系統(tǒng)通過提取一定的特征，將哼唱語音特征與預(yù)先建立的旋律特征數(shù)據(jù)庫中的特征進行比對并排名，給出檢索結(jié)果。 目前哼唱檢索的旋律匹配算法主要有字符串匹配、編輯距離、 性伸縮、動態(tài)規(guī)劃、指紋匹配等，其中基于線性伸縮的方法效果較好。對于基于線性伸縮的方法，線性伸縮參數(shù)包括拉伸系數(shù)和音高偏移的估計依然是難點，另外當(dāng)旋律較長時由于不同局部的線性伸縮參數(shù)不同，線性伸縮方法應(yīng)用統(tǒng)一的線性伸縮參數(shù)效果較差。 本文提出基于極值點分段信息和基于停頓點分 段信息來解決上述問題。極值點分段信息是指由旋律中最高點對旋律進行劃分構(gòu)成的分段結(jié)構(gòu)，通過極值點分段信息增加啟發(fā)式估計線性伸縮參數(shù)時的候選起點來提高對拉伸系數(shù)和音高偏移估計的準(zhǔn)確性。停頓點分段信息是指通過哼唱過程中的停頓位置對旋律構(gòu)建的分段信息，通過停頓點分段信息對旋律采用動態(tài)規(guī)劃或遞歸匹配的方法進行分段地線性伸縮匹配，可以達到更好的匹配效果。本文通過多項實驗驗證了所提出的兩種分段信息的有效性。 本文使用 355 大小的哼唱數(shù)據(jù)庫和 5223 大小的 律數(shù)據(jù)庫進行實驗來評估新算法的改進。實驗結(jié)果表明，在最好的情況下，基于停頓點分段信息的分段匹配算法比傳統(tǒng)的 法 別提高 17%、 相應(yīng)的 別提高 另外，使用 為精確匹配算法時新的啟發(fā)式估計算法使系統(tǒng)的 確率分別提高了 實驗結(jié)果驗證了極值點分段信息和停頓點分段 信息的有效性，同時也說明了基于停頓點分段信息的分段匹配算法是比傳統(tǒng)線性伸縮算法更有效的算法。 關(guān)鍵詞： 哼唱檢索 線性伸縮 動態(tài)規(guī)劃 遞歸匹配 is a is on BH a by a so of on it to is of of is In to we a is as by or to so is or In we to of We a 55 a 223 to of It is 7%, S, DP A at RR At RR on is 錄 錄 第 1 章 引言 .研究背景與研究意義 .旋律匹配算法的研究現(xiàn)狀 .本文的研究內(nèi)容及主要貢獻 . 2 章 哼唱檢索的基本原理 .本章引論 .件格式與旋律表示 .音符與基頻之間的關(guān)系 .哼唱語音旋律特征的提取 . 音高的提取 . 音符的提取 .哼唱旋律與 律的匹配 . 匹配的定義 . 匹配的特征 . 匹配的難點 . 匹配的分類 .哼唱旋律與 律的匹配算法 . 基于字符串匹配的方法 . 線性伸縮 . 動態(tài)規(guī)劃 . 基于遞歸的線性伸縮方法 .本章小結(jié) . 3 章 分段信息 .本章引論 .基于極值點的分段信息 . 極值點的定義 . 極值點的估計 . 錄 基于停頓點的分段信息 . 停頓點的定義 . 停頓點的物理意義 . 停頓點的估計 . 估計參數(shù)的確定 .實驗 .本章小結(jié) . 4 章 基于分段信息的匹配算法 .本章引論 .基于極值點分段信息的線性伸縮參數(shù)估計 .基于停頓點分段信息的動態(tài)規(guī)劃 .基于停頓點分段信息的遞歸匹配 .系統(tǒng)結(jié)構(gòu)與實驗數(shù)據(jù) .實驗驗證及結(jié)果分析 . 評價準(zhǔn)則及各算法描述 . 基于停頓點分段信息的精確匹配 . 候選分段點數(shù)對動態(tài)規(guī)劃分段匹配的影響 . 遞歸分段匹配準(zhǔn)確率與遞歸層次的關(guān)系 . 基于極值點的啟發(fā)式線性伸縮參數(shù)估計算法 . 實驗小結(jié) .本章小結(jié) . 5 章 結(jié)論與展望 .考文獻 .謝與聲明 .人簡歷、在學(xué)期間發(fā)表的學(xué)術(shù)論文與研究成果 . 1 章 引言 1 第1章 引言 研究背景與研究意義 音樂檢索作為與越來越龐大 的音樂數(shù)據(jù)庫的交互接口， 在多媒體信息檢索中起著至關(guān)重要的作用。 傳統(tǒng)音樂檢索利用歌曲描敘信息 (歌名等，對描述信息進行索引并建立數(shù)據(jù)庫，當(dāng)用戶通 過文本查詢時，按照文本檢索的方式檢索數(shù)據(jù)庫中與查詢文本 相關(guān)度最大的數(shù)據(jù)返回給用戶。 圖 哼唱檢索系統(tǒng)的一般結(jié)構(gòu) 哼唱檢索是基于內(nèi)容的 音樂檢索方式，如圖 一般的哼唱檢索系統(tǒng)的系統(tǒng)結(jié)構(gòu)，檢索系統(tǒng)主要包括三部分： （ 1）旋律特征數(shù)據(jù)庫 旋律特征數(shù)據(jù)庫是哼唱 檢索系統(tǒng)的模板庫， 系統(tǒng)對原始的音樂數(shù)據(jù)進行特征提取，然后將特征索引并儲存到特征數(shù)據(jù)庫 中。一般的哼唱檢索系統(tǒng)使用據(jù)庫作為旋律特征數(shù)據(jù)庫。 （ 2）用戶輸入與特征提取 這是系統(tǒng)與用戶交互的接口，當(dāng)用戶檢 索音樂時，通過麥克風(fēng)等錄音設(shè)備哼唱幾句歌詞，一般為幾秒到幾十秒不等。哼 唱形式可以是帶歌詞哼唱或以噠噠噠、吹口哨等方式哼唱。錄音完畢后，系 統(tǒng)對哼唱語音進行旋律特征提第 1 章 引言 2 取，并輸入到匹配模塊中。 （ 3）旋律匹配與候選輸出 提取用戶哼唱語音的旋律特征后， 系統(tǒng)將該特征與數(shù)據(jù)庫中的旋律特征進行比對，最后給出與用 戶查詢相關(guān)度最大的前 N 條記錄。 哼唱檢索系統(tǒng)相比傳統(tǒng)的音樂檢索系 統(tǒng)的優(yōu)勢有：一，更加精準(zhǔn)；傳統(tǒng)的音樂檢索引擎通過歌曲的歌名，歌手，歌詞等 信息作為關(guān)鍵詞來檢索，隨著流行音樂歌曲數(shù)量的快速增長，經(jīng)常會有同歌 名的歌曲出現(xiàn)，同一個歌手的歌曲數(shù)目也較多，盡管可以按專輯劃分， 要記住每一專輯中的歌名并非易事。要精確地記住歌詞也比較困難，同時不同歌曲 的歌詞也可能出現(xiàn)重復(fù)，通過歌詞檢索時若輸入歌詞太少則很難精確地找到 目標(biāo)歌曲。因此通過傳統(tǒng)的音樂檢索引擎檢索歌曲具有一定復(fù)雜度，同時必 須結(jié)合一定的檢索技巧。而哼唱檢索則不同，一首歌的旋律一般比較獨特， 尤其歌曲中高潮或旋律優(yōu)美的部分更易于記憶。由于旋律的“唯一性” ，當(dāng)用戶將對應(yīng)旋律以哼唱或唱的方式輸入到哼唱檢索系統(tǒng)時，系統(tǒng)便可以通過一 定的匹配算法，找出對應(yīng)的歌曲。因此，在哼唱檢索系統(tǒng)的算法足夠好的條 件下，哼唱檢索方式比傳統(tǒng)檢索方式更加精準(zhǔn)。二，更加人性化；通過哼唱 檢索的方式，用戶僅需要麥克風(fēng)或者其他錄音設(shè)備，通過語音輸入方式，來 進行檢索。而傳統(tǒng)檢索方式需要通過鍵盤等文字設(shè)備輸入文字進行檢索。就 普通用戶而言，文字輸入的方式比語音輸入的方式復(fù)雜，并且輸入速度慢， 因為文字輸入受用戶使用的輸入法、盲打等計算機水平的影響，而語音輸入 與平常說話類似。因此哼唱檢索的方式比傳統(tǒng)的音樂檢索方式 更加人性化，更易于使用。 從提出哼唱檢索概念開始，哼唱檢索 就一直是國內(nèi)外研究的重點課題。最早的哼唱檢索研究由 1995 年發(fā)表的一篇論文1開始，文中使用了較簡單的方法，將旋律的升高降低和保持不 變轉(zhuǎn)化成字符串并進行字符串匹配。由于這種旋律表示方法過于粗糙，需要的哼唱語音比較長，在 論文中使用的數(shù)據(jù)庫為 183 首。 實現(xiàn)了第一個可以通 過互聯(lián)網(wǎng)進行哼唱檢索的系統(tǒng)2，盡管使用了字符串匹配方法，在特征和數(shù)據(jù)庫上卻有進一步的研究。臺灣清華大學(xué)的張智星也在 哼唱檢索方面做了很多研究工作3通過研究線性伸縮及動態(tài)規(guī)劃等方法，開發(fā)出了多個 哼唱檢索系統(tǒng)。上海交通大學(xué)的李揚等通過使用近似旋律匹配即線性對齊方 法進行哼唱檢索，并構(gòu)造了哼第 1 章 引言 3 唱檢索系統(tǒng)的原型，其中數(shù)據(jù)庫中使用了 3864 首歌曲6。 , 8以及國內(nèi)深圳大學(xué)的陳知困9等研究了使用 法進行哼唱檢索匹配。 還有加利福尼亞大學(xué)的 試使用類似指紋的方法進行哼唱檢索10?？傮w而言，目前的研究方法主要包括字符串匹配 、編輯距離、動態(tài)規(guī)劃、 性伸縮、指紋等方法。由于算法以及數(shù)據(jù)等方面的原因 ，哼唱檢索目前還難以達到實際應(yīng)用的要求。 盡管哼唱檢索系統(tǒng)比傳統(tǒng)音樂檢 索方式在本質(zhì)上有很大優(yōu)勢， 要取代傳統(tǒng)音樂檢索方式尚為時過早。在哼唱檢索的實驗環(huán)境下，使用較小的數(shù)據(jù)庫（這里指幾百到幾萬不等）可以得到較好的準(zhǔn)確率 ，但實際應(yīng)用時會遇到一定的困難。一者，數(shù)據(jù)庫的收集難度 較大。目前多數(shù)算法的研究是基于 樂格式， 而對于 樂格式如果要建立全面的數(shù)據(jù) 庫需要通過手工錄入的方式，增加了數(shù)據(jù)庫的工作量，同時數(shù)據(jù)庫的更 新維護也過于繁瑣。二者，匹配算法的準(zhǔn)確率難以達到實際應(yīng)用要求。實際 應(yīng)用環(huán)境條件下，受各種因素如噪聲、哼唱質(zhì)量差等因素影響，匹 配算法的準(zhǔn)確率會大大下降。 目前哼唱檢索還有較大的研究空間， 如何進行更有效的旋律匹配依然是研究中的難點。本文的研究工作旨在以目前已有 的匹配算法為基礎(chǔ)，通過研究旋律中的分段信息并用于匹配，達到提高匹配 效果的目的，為今后的哼唱檢索研究提供有效的參考。 旋律匹配算法的研究現(xiàn)狀 哼唱檢索中的關(guān)鍵算法是計算哼唱旋 律與數(shù)據(jù)庫中旋律間的相似度， 大多數(shù)對哼唱檢索匹配的研 究是基于哼唱旋律與 律進行的。 由于哼唱旋律和 律間存在固有的差異，如 的三個音符可能在歌曲中對應(yīng) 2個歌詞，因此哼唱語音經(jīng)過提取后也是 2 個音符，這種特殊的性質(zhì)要求哼唱檢索的匹配算法對錯誤的容忍度較高。 國外主要的旋律匹配方法有字符串匹配、編輯距離、動態(tài)規(guī)劃、線性伸縮、紋等，大部分的研究工作基于某 一種方法或多種方法結(jié)合的思路進行。 字符串匹配的方法是最 早用于哼唱檢索的方法， 其主要思想是將旋律表示為字符串，然后通過字符串檢索、快速匹配等 方法進行匹配?？焖僮址サ?1 章 引言 4 配已經(jīng)有許多成熟的方法，但應(yīng)用于哼唱檢索 時須考慮一定的錯誤容忍，即在匹配結(jié)果中能容忍一定數(shù)量的錯誤 匹配。目前已有不少對可容忍 k 次錯誤的字符串匹配方法的研究11對于可容忍 k 錯誤的快速字符串匹配算法，基于 字符串匹配算法被認為是實際 應(yīng)用中最好的算法，同時該方法的代碼相比暴力搜索而言更簡單14。文獻1使用 出的可容忍 k 次錯誤的字符串匹配算法12進行哼唱檢索， 在含 183首歌曲的 據(jù)庫上用 1012 個音符構(gòu)成的字符串序列進行檢索， 能夠達到 90%的準(zhǔn)確率。使用字符串檢索的方法對特征提取的要求比較高，文獻中該方法特征提取占用的時間較大。 5在哼唱檢索中使用音高、節(jié)奏、旋律的上升下降曲線等特征來進行檢索，并且 只從歌曲的起始點使用字符串匹配進行檢索，同時研究了從數(shù)據(jù)庫中檢索到 正確歌曲所需要的特征數(shù)量如音符個數(shù)，是否使用節(jié)奏信息等，還研究了所 需要的音符個數(shù)隨數(shù)據(jù)庫大小變化的關(guān)系。通過字符串快速匹配的方法進行 哼唱檢索，優(yōu)點是較直觀，匹配速度較快，缺點是特征提取的難度及要求比 較高。由于字符難以表示旋律變化的豐富性，假如以字符表示絕對音高，則 哼唱旋律與數(shù)據(jù)庫旋律間存在整體的音高偏移，因而表示的字符串不一致的 概率大大增加。而對于以字符表示音高變化，若單純表示音高的升降或保持 不變，則過于簡略，很難將目標(biāo)旋律與其他旋律區(qū)分開，導(dǎo)致返回數(shù)據(jù)集過 大。而若以字符表示音高變化的不同程度，則存在程度分界的問題，兩個不 同的音高變化值極相近，但可能被歸類成不同音符，導(dǎo)致錯誤。 編輯距離又稱 離，用于計算一個字 符串轉(zhuǎn)化為另一個字符串所需要的最少編輯操作次數(shù)，一般 使用動態(tài)規(guī)劃方法計算。 6使用類似快速字符串匹配的方法， 將旋律根據(jù)音高的升降 和保持不變轉(zhuǎn)化為 U/D/后通過從數(shù)據(jù)庫中檢索與哼 唱旋律的特征字符串間編輯距離最小的歌曲作為匹配結(jié)果。通過在 7數(shù)據(jù)庫的 10370 首古典音樂數(shù)據(jù)庫上使用 106 個錄音片段進行哼唱檢索，得到 確率為 44%， 7%，并指出大部分的錯誤是由于呼吸導(dǎo)致，如果能在錄制哼唱語音時不呼吸，則上述對應(yīng)的準(zhǔn)確率可提高到 59%、 86%。編輯距離的方法與字符串匹配類似，相比可容忍 k 錯誤的字符串匹配，編輯 距離可以容忍插入、刪除及替換三種錯誤類型，比可容忍 k 錯誤的字符串匹配更魯棒。缺點也與字符串匹配類似，對旋律的表示過于簡化，同 時基于動態(tài)規(guī)劃來計算編輯距第 1 章 引言 5 離的耗時也比快速字符串匹配大。 動態(tài)規(guī)劃是計算機科學(xué)中常用的用于 求解可分解為子問題的最優(yōu)化方法，它將求解當(dāng)前問題最優(yōu)解的問題，轉(zhuǎn)化為求解 子問題的最優(yōu)解問題。因此不少哼唱檢索匹配算法的研究都基于動態(tài)規(guī)劃的方法3, 18 用多次的動態(tài)規(guī)劃并同時估計音高偏移以達到最好的匹配效果，在估計音高偏移時使用啟發(fā) 式估計算法。通過在 800 首歌曲的數(shù)據(jù)庫上使用 200個哼唱片段進行測試，每兩 段旋律間的匹配調(diào)用 5 次動態(tài)規(guī)劃，在限制哼唱旋律均從歌曲的起始部 分開始哼唱并哼唱 5 至 8 秒的條件下， 得到 準(zhǔn)確率為 76%， 說明這種基于動態(tài)規(guī) 劃的方法能夠滿足一般哼唱水平的人的使用要求。動態(tài)規(guī)劃方法 的優(yōu)點是對匹配旋律的要求不嚴(yán)格，抗噪性強，可以通過搜索不同路徑達到最優(yōu)匹 配結(jié)果，缺點是匹配時間長，計算量大，數(shù)據(jù)庫增大時系統(tǒng)時 間響應(yīng)的變化尤為明顯。 考慮到哼唱旋律與標(biāo)準(zhǔn) 律間存在的線性關(guān)系，線性伸縮的方法被引入到哼唱檢索的旋律匹配算法中，線性伸縮 方法通過將其中一旋律的曲線進行橫向的拉伸和縱向平移來與另一旋律曲線 對齊，最終調(diào)整到最好的對齊效果計算分?jǐn)?shù)。 出使用線性伸縮匹 配的方法作為距離函數(shù)并利用樹結(jié)構(gòu)搜索哼唱 旋律的最近鄰作為檢索結(jié)果4， 通過使用普通哼唱水平的人的 1000 個哼唱語音在包含 3000 首歌曲的數(shù)據(jù)庫上進行測試， 3%，對應(yīng)的系統(tǒng)響應(yīng)時間為 2 秒。同時認為，旋律可能存在非線性的速度變化，這時使用動態(tài)規(guī)劃能夠達 到更好的匹配效果，但動態(tài)規(guī)劃的時間消耗較大，因此必須在系統(tǒng)準(zhǔn)確率和 時間響應(yīng)上作適當(dāng)?shù)钠胶狻＞€性伸縮方法的優(yōu)點是計算簡單且直觀，缺點是 匹配起點的確定困難，一般假設(shè)哼唱旋律從句子的起始點或歌曲的起始點開 始來降低搜索的空間。另一問題是線性伸縮的參數(shù)包括拉伸系數(shù)（ 音高偏移（ 估計問題，由于沒有直觀的辦法獲取這兩個參數(shù)，一般通過多次使用不同參數(shù)計算并選最優(yōu)的方法來估計 。再者，當(dāng)哼唱旋律較長時，整體進行線性伸縮匹配的效果下降，因為哼唱 旋律的局部可能存在不同的線性伸縮參數(shù)。 為語音識別中的重要工具，同樣也被用于哼唱檢索的研究。 于描述隱含了未知參數(shù)的馬爾科夫過程。使用行哼唱檢索時，數(shù)據(jù)庫中的旋律表示為 模型，而查詢旋律則第 1 章 引言 6 作為觀察序列，當(dāng)進行哼唱檢索時根據(jù)每一數(shù) 據(jù)庫旋律輸出該哼唱旋律的后驗概率進行排序。 將哼唱旋律表示成音符序列，定義 的每一個狀態(tài)具有 2 個屬性，一是音高變化，即音符 相對上一音符的音高差，二是時間變化，即音符的持續(xù)時間。狀態(tài)間的轉(zhuǎn)移概率則使用 據(jù)庫訓(xùn)練得到。在哼唱檢索時利用 前向算法計算匹配的 似然度作為匹配概率。通過使用 24 個哼唱語音在包含 277 首 數(shù)據(jù)庫上進行檢索，并和字符串匹配方法對比。結(jié)果表明，字符串匹配方法得到的 確率分別為 而 法的對應(yīng)準(zhǔn)確率分別為 該方法的局限是對于查詢旋律長度大于 的最長路徑時會導(dǎo)致錯誤，同時查詢旋律中存在個別音符丟失的情況時也易 導(dǎo)致錯誤。通過使用更大的數(shù)據(jù)庫進行進一步研究7，系統(tǒng)對于哼唱旋律越長的 情況則檢索結(jié)果越準(zhǔn)確，同時對于不理想的哼唱旋律也 能做較好的匹配。使用 方法進行匹配的優(yōu)點是引入了概率的概念，可以通過對現(xiàn) 有數(shù)據(jù)的統(tǒng)計達到較好的匹配效果，缺點是需要訓(xùn)練模型，并且識別的準(zhǔn) 確率與訓(xùn)練數(shù)據(jù)的關(guān)系較大。 另外還有指紋識別（ 方法，指紋識別最早用于人的身份辨識，由于在哼唱檢索中這一方法與身份辨識中 的指紋識別方法相似，因此也稱為指紋識別。文獻10中使用 方法提取旋律特征，將哼唱旋律切割成音符， 并提取 種特征，然后取 線中的極值點來建立 指紋樣本。哼唱檢索時通過計算哼唱旋律與 律間在 的平方差作為匹配分?jǐn)?shù)，最終保留前 5個候選。 通過使用來自 80人的 400個哼唱查詢語音及大小為 1500的 據(jù)庫進行哼唱檢索， 結(jié)果表明在受過音樂教 育的人對應(yīng)的哼唱數(shù)據(jù)集上可達到 88%的準(zhǔn)確率，而對于未受過音 樂教育的對應(yīng)準(zhǔn)確率為 70%。對應(yīng)的使用傳統(tǒng)的編輯距離匹配的 方法得到的準(zhǔn)確率分別為 86%和 62%。說明這種指紋識別的方法對于未受過音樂教育的人的哼唱查詢具有更好的魯棒性。指紋識別的優(yōu)點是僅使用旋律中的少量但 獨特的信息，便于快速匹配和索引， 缺點是確定有效的指紋信 息并在哼唱旋律與 律之間保持一致比較困難。相比身份識別中的二維指紋，哼唱檢 索中的指紋是一維信息，因而表示的信息量也較少，要做到精確匹配，必須 聯(lián)合同一旋律中的多個指紋進行計算。 國內(nèi)對于旋律匹配算法 的研究起步相對晚一些， 主要的算法分類與國外的第 1 章 引言 7 算法大致相同，也包括字符串匹配、 編輯距離、動態(tài)規(guī)劃、線性伸縮及 前對類似指紋識 別的哼唱檢索研究較少見。 字符串匹配仍是常用的方法21, 22，文獻21首先提取歌譜輪廓特征，通過構(gòu)造標(biāo)準(zhǔn)音調(diào)差值圖將哼唱旋律表示為歌譜特 征，然后通過動態(tài)規(guī)劃方法計算歌譜字符串間的相似度。通過在 405 首歌曲的數(shù)據(jù)庫上進行檢索，得到的確率超過 90%。 編輯距離的方法也被用于旋律匹配， 文獻23使用動態(tài)規(guī)劃計算哼唱旋律和律間的編輯距離，通過在動態(tài)規(guī)劃 中引入模糊隸屬度函數(shù)計算兩音高差間的相似度，同時引入音長比信息進行相似 度計算，最終以兩種相似度的加權(quán)作為最終的編輯距 離分?jǐn)?shù)。通過在包含 2500 個 件的數(shù)據(jù)庫上使用 90 個哼唱片段進行測試，結(jié)果表明算法相比音高差 5 階量化方法在 9%提高到了 75%。 動態(tài)規(guī)劃的方法繼續(xù)用于哼唱檢 索匹配。和傳統(tǒng)的哼唱語音檢索 律的方式不同，文獻24考慮了哼唱語音和哼唱語音間的 直接匹配，通過對哼唱語音提取 及過零率特征并進行適當(dāng)簡化， 再與數(shù)據(jù)庫中的哼唱語音特征使用 算相似度。數(shù)據(jù)庫中的候選歌 曲都標(biāo)注了句子起始點，因此取哼唱旋律與數(shù)據(jù)庫中對應(yīng)歌曲的多個候選 片段中匹配分?jǐn)?shù)最好時的分?jǐn)?shù)作為與該歌曲的匹配分?jǐn)?shù)。通過對 6 位哼唱者的 70 余次哼唱檢索進行測試，排名在前 15 位的概率超過 60%，說明系統(tǒng)是有效的。除此之外，還有包先春提出兩層的 法25，羅凱等提出在 同時考慮音高差和音長差作為代價函數(shù)26， 馬志欣等提出模糊集合的概念并在 使用音高差和音長比加權(quán)作為代價函數(shù)的方法23等。 線性伸縮的方法也獲得了較好的效果。 中科院聲學(xué)所的吳曉等人27使用線性伸縮的方法，通過對哼唱旋律和數(shù)據(jù)庫旋律 進行遞歸的自頂向下的分段匹配來進行檢索。在確定要匹配的哼唱旋律片段 和數(shù)據(jù)庫旋律片段后，取數(shù)據(jù)庫旋律的中間音符，根據(jù)預(yù)先 設(shè)定多種線性伸縮系數(shù)和音 高偏移系數(shù)的組合，按對應(yīng)的劃分比例確定哼唱 旋律中的對應(yīng)音符，將兩段旋 律劃分成兩組片段，并計算兩組片段對應(yīng)的線性伸縮匹配分?jǐn)?shù)，取 分?jǐn)?shù)最優(yōu)的一種對哼唱旋律的劃分方式，如果已經(jīng)達到設(shè)定的遞歸次數(shù)，則 直接返回前述分?jǐn)?shù)，否則繼續(xù)對劃分的兩對子片段進行同樣的匹配過程，直 到達到預(yù)設(shè)的遞歸次數(shù)。通過簡化該方法的計算過程，由該方法衍生出三種 快速匹配的方法，用于快速過第 1 章 引言 8 濾。通過在包含 1180 首歌曲的 據(jù)庫上，使用 875 個哼唱查詢語音進行測試，實驗結(jié)果表明該方法比 法具有更好的性能。同時指出當(dāng)查詢旋律的長度在 715 秒時具有較好的匹配準(zhǔn)確率，大于 13 秒時結(jié)果變差，可能由于該遞歸方法在查詢旋律 過長時不再有效。另外也有李揚等人6同時考慮音高和節(jié)奏來進行線性伸縮 匹配，也獲得了較好的效果。 國內(nèi)也有對 配方法的改進工作9, 28。中國人民大學(xué)的袁斌等人28通過對哼唱語音的音高差和音長比進行統(tǒng)計分 析，并合成產(chǎn)生新的旋律和節(jié)奏訓(xùn)練數(shù)據(jù)庫，同時對 特征和訓(xùn)練方法都提 出了改進。通過在包含1500 個音樂片段的數(shù)據(jù)庫上使用 27 個檢索片段進行檢索， 前 5 得到了滿意的效果。 還有中國人民大學(xué)的劉怡等人29研究了大型音樂哼唱系統(tǒng)中不同近似匹配算法的算法性能，并比較了后綴樹、 輯距離、 單側(cè)連續(xù)匹配（ 匹配方法。單側(cè)連 續(xù)匹配的方法采用 順序哈希索引來加快查詢處理速度。 通過在包含 72000首音樂片段的數(shù)據(jù)庫上構(gòu)造 1500個不同類型錯誤的查詢來比較其中 3 類方法，結(jié)果表明單側(cè)連續(xù)匹配的方法查詢速度快，在用戶哼唱旋律只包含與旋律輪 廓方向相同的錯誤時查詢準(zhǔn)確率能達到 100%，而哼唱包含兩個以內(nèi)與旋律輪廓方向相反的錯誤時，前 10位的命中率在 90%左右，說明單側(cè)連續(xù)匹配的方法是適用于大型哼唱檢索系統(tǒng)的有效算法。 目前國內(nèi)的研究起步晚，還有很大的研 究空間。由于目前免費開放的中文相關(guān)的數(shù)據(jù)庫資源較少，給不同研究 工作間的比較帶來一定困難。 本文的研究內(nèi)容及主要貢獻 旋律匹配算法一直是領(lǐng) 域內(nèi)的研究重點， 在旋律匹配中利用的是音高特征（ ，通過對音高特征序列中的音高使用 特定算法進行分割可以得到音符序列， 從而將旋律匹配的問題， 歸結(jié)為哼唱旋律的音高 序列和音符序列與 線性伸縮方法作為一種效果 比較好且計算簡單的方法， 面臨的主要難點是線性伸縮參數(shù)的估計和局部參數(shù)精確化的問題 。首先，進行線性伸縮需要確定兩個必要參數(shù)，一是拉伸系數(shù)，即兩旋律間 的拉伸比例，二是音高偏移，第 1 章 引言 9 指對其中一旋律與另一旋律對齊最好時縱向平 移的尺度。盡管估計這兩個參數(shù)時可使用枚舉的方法（如27中方法） ，但會導(dǎo)致大量計算，因此從速度角度考慮，枚舉方法并不可取。另一種估計方法是 通過啟發(fā)式估計來確定最優(yōu)參數(shù)，這種啟發(fā)式方法在5中也已用過，只不過是基于 動態(tài)規(guī)劃的啟發(fā)式方法。由于線性伸縮的匹配分?jǐn)?shù)與它的兩個參數(shù)間并 非單調(diào)的關(guān)系，這種方法可能導(dǎo)致陷入局部最優(yōu)點，不能獲取全局最優(yōu)參數(shù) ，導(dǎo)致結(jié)果的準(zhǔn)確率下降。另一個問題局部參數(shù)精確化的問題，當(dāng)使用同一 的線性伸縮參數(shù)進行精確匹配時，某些局部對齊得好，而某些則較差，不同 局部需要的線性伸縮參數(shù)是不同的，如何對各部分使用相應(yīng)的參數(shù) 進行匹配，是精確匹配的關(guān)鍵問題。 為解決線性伸縮匹配中面臨的上述問 題，本文中提出了兩種分段信息，一種是基于極值點的分段信息，極值點即旋律中 的最高點，這種信息被用來增加啟發(fā)式估計線性伸縮參數(shù)時的候選起點，提 高估計參數(shù)的準(zhǔn)確性。另一種是基于停頓點的分段信息，停頓點是哼唱過程 中換氣的位置，相當(dāng)于音樂樂譜中的休止符。本文同時提出了使用停頓點的 分段信息并利用動態(tài)規(guī)劃以及遞歸匹配的方法來優(yōu)化對 律的分段匹配，從而實現(xiàn)哼唱旋律和 本文的主要貢獻是： （ 1）提出兩種分段信息特征； （ 2）利用極值點分段信息實現(xiàn)了一種基于極值點分段信息的啟發(fā)式估計算法； （ 3）利用停頓點分段信息實現(xiàn)了兩種分段匹配方法，一種使用動態(tài) 規(guī)劃的策略，另一種使用遞歸匹配的策略。本文最后給出的實驗結(jié) 果驗證了所提出算法的有效性。 本文后續(xù)的內(nèi)容安排如下：第二章介 紹哼唱檢索的基本原理，包括 符與基頻的關(guān)系、特征提取及旋律匹 配算法；第三章介紹極值點分段信息及停頓點分段信息；第四章研究利用分 段信息進行匹配并提高檢索的準(zhǔn)確率，并研究動態(tài)規(guī)劃和遞歸匹配兩種 優(yōu)化策略；最后在第五章給出結(jié)論。 第 2 章 哼唱檢索的基本原理 10 第2章 哼唱檢索的基本原理 本章引論 本章闡述哼唱檢索系統(tǒng)的基本原理。首先簡單介紹 件格式及 著通過闡述音符與語音基 頻間的關(guān)系，說明音符的音高與基頻間存在固定的關(guān)系，而后以此為基礎(chǔ)介紹 了基頻提取，基頻到音符的轉(zhuǎn)化方法，通過提取基頻及音符來提取哼唱語音的 旋律特征，最后介紹基于已提取的旋律特征的多種匹配算法，其中主要介紹了 最早的字符串匹配方法及與本文研究相關(guān)的幾種匹配方法，包括線性伸縮 (動態(tài)規(guī)劃 (遞歸匹配 (種方法。 件格式與旋律表示 本文的哼唱檢索是基于哼唱旋律與 律進行匹配的。 樂器數(shù)字接口 (簡稱 是一項工業(yè)標(biāo)準(zhǔn)的通信協(xié)議，通常用于電子樂器等演奏設(shè)備，它定義 了電子樂器演奏所需要的數(shù)據(jù)包括音調(diào)、音樂強度、節(jié)拍、節(jié)拍速度等。 準(zhǔn)是戴夫 史密斯于 1981 年向音頻工程協(xié)會提出的， 范的 本發(fā)布于 1983 年。 以說是電子樂器的電子樂譜， 器演奏一個音符包括了三個要素： （ 1）按下的 器中的特定鍵 如中央 C， 器中的每個鍵對應(yīng)了特定的 符編號，這指定了音符的頻率， 符編號可以參考 準(zhǔn) 30。 （ 2