【畢業(yè)學(xué)位論文】哼唱檢索中基于分段信息的匹配算法研究-計(jì)算機(jī)應(yīng)用技術(shù)

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