基于余弦距離的哼唱音樂檢索算法的設計與實現(xiàn)

1、基于余弦距離的哼唱音樂檢索算法的設計與實現(xiàn)學 院計算機學院專 業(yè)計算機科學與技術(shù)班 級學 號姓 名指導教師負責教師2010年6月摘 要隨著多媒體技術(shù)的發(fā)展，網(wǎng)絡音樂日益增多。現(xiàn)在人們己經(jīng)不滿足于通過歌曲名、歌曲的演唱者等一些文本信息來檢索。特別是對于那些種類繁多的音樂數(shù)據(jù)，人們也許只記得一個調(diào)子，也許只記得一個片斷，如何快速有效的通過旋律來檢索相關(guān)音樂就成為一個突出問題。本文對基于哼唱的音樂檢索進行了相關(guān)的研究和實現(xiàn)。本文采用了microsoft visual c+編程技術(shù)和mysql server數(shù)據(jù)庫，做了如下工作：(1) 通過對音樂信號基本理論的研究，提出了利用音高差和音長來描述音樂旋律

2、特征的方法，有效地避免哼唱過程走調(diào)問題，因此提高了準確性。(2) 對于哼唱音樂片段，通過信號預處理、基音提取、特征提取、特征后處理，實現(xiàn)了從wav文件中提取音符音高差和音長特征，采用n_gram方法對音高序列進行切分，擴充查詢集合以提高查詢準確度。(3) 確定wav格式作為數(shù)據(jù)庫音樂的文件存儲格式，并建立歌曲的音高差和音長特征庫。(4) 為提高查詢速度，建立整數(shù)編碼的哈希索引。(5) 采用余弦距離旋律匹配算法，從音高差和音長兩方面進行旋律匹配，返回查詢結(jié)果，并計算響應時間。關(guān)鍵詞：哼唱檢索；特征提??；余弦距離匹配；音高差usd和音長旋律特征design and implement of hum

3、med melody retrieval based on consine distanceabstractwith rapid development of multimedia technology, a large number of online music can be obtained from the internet. now, people are no longer satisfied with searching music based on text information such as music name and singer. especially, with

4、various kinds of music data, people might only remember the tune of a song, or perhaps fragment of it. how to quickly and effectively retrieve music data by melody information has become a prominent problem. in this dissertation, the music retrieval based on hummed melody is studied .in this dissert

5、ation, the hummed melody retrieval based on consine distance is implemented with microsoft visual c+ and mysql server, and the concrete work is as follows:firstly, through the study of music signal, proposing that pitch interval and duracion as the music melody feature, which is effective to avoid t

6、he pitch changing as well as improving the music retrieval accuracy. secondly, for the hummed melody, extracting the feature of music melody from wav musics format through signal preprocessing, keynote extraction, feature extraction, feature extraction postprocessing. using n_gram to syncopate the p

7、itch interval in order to improve the accuracy. thirdly, making sure that wav as the musics format and set up pitch interval and duracion database. forthly, in order to improve the speed of retrieval, the dissertation uses hash index. finally, using cosine distance matching algorithm, the pitch inte

8、rval and duracion as the vector to match then return the result, in the end calculating the retrieval time.keywords: hummed retrieval; feature extraction; cosine distance matching; usd pitch interval and duracion 目 錄1 緒論11.1 課題背景及其意義11.1.1 音樂哼唱檢索技術(shù)的發(fā)展11.1.2 音樂哼唱檢索系統(tǒng)的意義11.2 課題目標21.2.1 課題研究的主要內(nèi)容21.2.2

9、 課題研究的價值32 系統(tǒng)需求分析42.1 需求分析42.2 可行性研究52.2.1 技術(shù)可行性52.2.2 經(jīng)濟可行性62.2.3 操作可行性62.3 目前可選擇的技術(shù)62.4 技術(shù)開發(fā)工具概述62.4.1 c+開發(fā)語言概述62.4.2 mysqlserver數(shù)據(jù)庫73 系統(tǒng)概要設計93.1 系統(tǒng)總體設計思想93.2 系統(tǒng)用例圖103.3 數(shù)據(jù)庫邏輯設計123.3.1 數(shù)據(jù)庫設計方法簡述123.3.2 概念模型設計123.3.3 數(shù)據(jù)庫的關(guān)系模型設計134 系統(tǒng)詳細設計及實現(xiàn)164.1 系統(tǒng)數(shù)據(jù)庫詳細設計164.1.1 用戶哼唱片段信息表164.1.2 wav特征庫設計164.1.3 索引表

10、174.1.4 檢索結(jié)果集184.2 系統(tǒng)功能詳細設計194.2.1 wav特征提取194.2.2 哼唱音樂的記錄和特征提取234.2.3 查詢擴展234.2.4 哈希索引244.2.5 余弦匹配算法254.2.6 系統(tǒng)響應時間的計算275 系統(tǒng)的調(diào)試與測試285.1 系統(tǒng)的調(diào)試285.2 系統(tǒng)功能測試295.2.1 wav音樂文件特征提取測試295.2.2 用戶哼唱片段特征提取305.2.3 n_gram算法測試315.2.4 哈希索引表測試315.2.5 系統(tǒng)檢索匹配測試325.2.6 分析原因32結(jié)束語34參考文獻35致 謝371 緒論1.1 課題背景及其意義1.1.1 音樂哼唱檢索技術(shù)

11、的發(fā)展基于哼唱的音頻信息檢索技術(shù)的研究工作是從上世紀九十年代中后期開始的。近年來，它已經(jīng)成為國內(nèi)外研究的熱點問題之一，引起了眾多研究機構(gòu)和學者的重視。具體來說，早期的研究以ghias和r.j.mcnab等為代表，他們的共同特點是采用時域上的自相關(guān)法提取音高值，根據(jù)音高值的變化把旋律表示成由字母“u”、“d”、“r”組成的符號串。其中，“u”表示后一個音符的音高比前一個高;“d”表示后一個音符的音高比前一個低;“r”表示前后音符的音高值相同。匹配引擎采用近似字符串模糊匹配算法。后來，一些學者在旋律特征表達方面和匹配檢索方面進行了更多的探索。zhu等人使用了一種基于時間序列的方法。在該方法中，歌曲

12、中的每個音符都被拆分成由若干時間片組成的時間序列，從而將整首歌曲中音符的組合轉(zhuǎn)化為時間序列的組合。然后再計算時間序列間的距離，并將結(jié)果作為衡量歌曲間相似度的標準。該方法有利于使用dtw方法進行匹配，但是需要進行音符序列的平移和時間彎曲，還需要對每個時間序列進行匹配，時間復雜度非常高。大多數(shù)系統(tǒng)都使用近似字符串的匹配算法比較旋律，但近年來，基于隱馬爾可夫模型(hmm)的匹配算法被越來越多的學者重視和研究。 wiiliamrand等提出使用馬爾可夫統(tǒng)計模型比較旋律的相似性。該方法對音高誤差比較敏感，但能較好地容忍遺漏音符和節(jié)奏上的哼唱誤差。1.1.2 音樂哼唱檢索系統(tǒng)的意義隨著互聯(lián)網(wǎng)技術(shù)和多媒體技

13、術(shù)的迅速發(fā)展，網(wǎng)絡音樂的下載己經(jīng)占據(jù)了整個網(wǎng)絡信息流量的很大份額。人們面臨的問題不再是缺少音樂內(nèi)容，而是如何在浩如煙海的多媒體世界中快速、準確、高效的查詢音樂信息。常規(guī)的信息檢索技術(shù)主要是基于文本的，目前已經(jīng)發(fā)展得非常成熟。例如google、yahoo和百度等搜索引擎采用的就是這種技術(shù)。它是通過查詢關(guān)鍵字的匹配來發(fā)現(xiàn)需要檢索的文檔。如果一個文檔包含較多的查詢項，就認為該文檔比其它包含較少查詢項的文檔更“相關(guān)”。最后，將文檔按照“相關(guān)”度排序并顯示給用戶作為檢索結(jié)果。雖然最初對音頻信息的檢索也采用了文本檢索技術(shù)，但卻是通過人工方式生成音頻信息的文本標注，如文件名、歌曲的演唱者等，然后采用文本檢索

14、技術(shù)實現(xiàn)對音頻信息的檢索。在實際應用中，這種基于文本的音頻信息檢索方式有其固有的無法克服的缺陷。首先，當音頻數(shù)據(jù)量越來越多時，人工的注釋強度加大；其次，人對音頻的感知，例如音樂的旋律、音調(diào)、音質(zhì)等，難以用文字注釋表達清楚。最后，當聽到熟悉卻又陌生的旋律，但是想不起來它的作者或者表演者時，在現(xiàn)有的搜索引擎上，想要找到這樣的樂曲是不可能的。而這正是基于內(nèi)容的音頻檢索技術(shù)所要研究和解決的問題?？梢韵胂?，哼唱檢索音樂具有極其廣泛的應用前景，普通用戶即使只記得音樂的某個片段也可以方便的從網(wǎng)上找到自己喜歡的音樂；在ktv人們只需要哼唱就可以點歌而不需要歌本；音樂創(chuàng)造者可以知道自己的創(chuàng)作是否與眾不同；版權(quán)管

15、理部門可以查出一首歌曲是否盜版侵權(quán)；利用手機哼唱點歌也將成為一種新的潮流。因此，對于哼唱音樂檢索的研究具有重要的實用價值，也是富有挑戰(zhàn)性的研究領(lǐng)域。本文的工作為音樂哼唱檢索打下了一定的基礎，對進一步的深入研究具有推動和借鑒意義。1.2 課題目標本次設計的目標是通過對用戶哼唱的旋律片段的分析，在大型曲庫中利用余弦距離匹配算法，檢索出與用戶的輸入旋律在聽覺上相近的歌曲。另外，在設計中，對音樂旋律的刻畫考慮音高差和音長，盡可能提高音樂特征描述的準確度。采用整數(shù)哈希索引方法，提高了哼唱檢索的速度。本設計實現(xiàn)了哼唱檢索系統(tǒng)的基本功能，具有較強的實用性。1.2.1 課題研究的主要內(nèi)容傳統(tǒng)的歌曲搜索都是基于

16、關(guān)鍵詞的檢索，在有些情況下很不實用。本文以基于內(nèi)容的音樂哼唱檢索為背景，系統(tǒng)的研究了記錄哼唱音樂片段，哼唱音樂片段特征提取、建立音樂特征庫、建立整數(shù)哈希索引、余弦距離匹配算法、計算檢索響應時間。研究目標為用戶不需要哼唱固定符號，更不用加入輔助手段，直接哼一段音樂或唱一段歌譜，將得到檢索結(jié)果。本文的研究的主要內(nèi)容如下：記錄用戶哼唱的音樂片段，存儲格式采用wav。在記錄過程中，要對錄入的聲音進行信號預處理、基音提取、特征提取、特征后處理。音樂旋律主要由音高和音長兩大部分組成，音高描述該音節(jié)的頻率高低(相對值)，音長描述該音節(jié)的持續(xù)長短(相對值)。相同音高序列配以不同的音長表示，或者相同的音長賦予不

17、同的音高，其實際聽覺感受差異是十分明顯的。因此，采用音高差和音長來刻畫旋律特征。音高差采用usd、音長采用lrs描述方式。采用n_gram方法對音高差序列進行切分，產(chǎn)生擴充的usd查詢集合，以查詢集合中的每個元素為查找項，查找哈希索引后，再進行余弦距離匹配，這樣使系統(tǒng)具有良好的容錯性。為提高查詢效率，本文對旋律輪廓按照n_gram進行切分后，建立了順序的哈希索引。具有相同的哈希碼值的記錄放在相同的塊中，因此在哈希記錄中只有樂曲的編碼和片段中第一個音符在歌曲中的位置，提高了檢索的效率。采用余弦距離旋律匹配算法，從音高差和音長兩方面進行旋律匹配，返回查詢結(jié)果，并計算響應時間。1.2.2 課題研究的

18、價值哼唱音樂檢索實現(xiàn)了所唱即所得的音樂檢索方式。檢索方式直接且方便，彌補了人們常用的基于文本音樂檢索方法中文本信息完整的描述音樂豐富多變的內(nèi)容難以及手工生成文本索引費時費力的不足。哼唱音樂檢索技術(shù)在internet上音樂查找、音樂數(shù)據(jù)庫的管理、以及人們的生活娛樂等方面都具有廣泛的應用前景。2 系統(tǒng)需求分析2.1 需求分析目前幾乎所有音樂網(wǎng)站在為用戶提供音樂文件搜索服務時均使用字符檢索方式(以標題/作者/歌詞作為關(guān)鍵字)。對于音樂而言，這種方式事實上與人的生理與心理特征相違背。人對音樂最敏感的永遠是旋律，人們即使忘記了一首歌的歌詞，依然能夠輕松的哼唱出它的主旋律，就是一個很好的證明。這種最容易讓

19、人產(chǎn)生共鳴的音樂旋律信息理應作為另一種檢索條件被服務器接受并加以利用，無需借助基于標題、作者或歌詞關(guān)鍵字而進行的檢索，通過旋律一樣可以找出用戶所要求的音樂文件，而且這種方式更直觀，更貼近音樂的本質(zhì)。因此一種基于哼唱的音樂檢索系統(tǒng)成為人們迫切的需要。該系統(tǒng)的主要功能如下：(1) 采用用戶哼唱的內(nèi)容作為關(guān)鍵信息檢索只要使用者通過音頻輸入設備(如麥克風)哼唱一段音樂的旋律，計算機會自動處理輸入的音樂片段，提取音樂特征后，利用這些特征，使用哈希索引方法，在海量的音樂庫中尋找出用戶需要的目標音樂。這種檢索方式的好處顯而易見，它十分符合人們的交互習慣、拉近了計算機與人之間的距離。(2) 無須人工干預的對音

20、樂文件進行特征提取音樂的特征是用來區(qū)分不同音樂的屬性。例如每一曲音樂的樂譜跟其他音樂的樂譜都不一樣，樂譜就是其音樂特征之一。另外還包括其他類型的特征，如音樂節(jié)奏、音樂的風格等等。提取音樂的這些特征是為了與查詢者哼唱的片段進行比較，以便將相近、相似的音樂提供給查詢者。因此特征提取是該系統(tǒng)中重要的一環(huán)。本文使用音高差和音長來刻畫旋律特征，該方法既形象又準確，并且便于進行旋律匹配。另外，intemet上的音樂資源十分巨大，由人工來完成這些音樂特征的提取工作量十分巨大，并且不太現(xiàn)實。而且這些音樂資源的數(shù)量還再快速的增長。因此我們需要計算機能代替人工，實現(xiàn)對音樂特征的提取。(3) 檢索系統(tǒng)的魯棒性人的哼

21、唱往往帶有很多錯誤。首先是人們在哼唱的過程中音高與歌曲的標準音高常常不一致，一般都會低于標準音高。其次由于一些人對音樂的旋律不太熟悉，哼唱的旋律中多了一些原本沒有的音符或是少了一些原本樂曲中包含的音符。另外，也有人對節(jié)奏把握的不是很好，哼唱的速度高于或者低于樂曲的標準節(jié)奏。這些哼唱中產(chǎn)生的錯誤將嚴重影響系統(tǒng)查詢效率。另外在麥克風輸入的過程中也可能存在背景噪音等等干擾。為了減少上述情況對查詢的影響，系統(tǒng)的各個環(huán)節(jié)中必須做好相應工作，以保證查詢的效率。例如，在麥克風信號采集后，對音樂信號進行預處理和基音提取降低輸入環(huán)節(jié)上的干擾。在特征提取中，使用usd形式的音高差，這樣可以有效地避免在哼唱過程的走

22、調(diào)現(xiàn)象。在檢索過程中，建立了哈希索引，匹配過程中采用余弦距離匹配算法。這樣在檢索匹配過程中通過適合的算法來降低查詢者在哼唱中所產(chǎn)生的錯誤。因此在系統(tǒng)的各個部分都要考慮的查詢的魯棒性。(4) 檢索系統(tǒng)的高效性音樂檢索系統(tǒng)的音樂庫是十分龐大的。如果檢索時匹配時間比較長則會讓查詢者感到不適應。因此需要檢索速度必須較快。另外還需要有較高的準確性。絕大部分查詢者通常只愿意瀏覽查詢結(jié)果列表的前幾項，如果在前幾項中查不到用戶想要的音樂，使用者將沒有耐性繼續(xù)查下去。因此系統(tǒng)必須考慮的查詢的準確性。本文對用戶哼唱的音高差序列按照n_gram算法進行切分，產(chǎn)生擴充的查詢集合，再以查詢集合中的每個元素為查找項，這樣

23、能夠更準確的查找與輸入片段相似的歌曲。此外，建立了順序的哈希索引。使具有相同的哈希碼值的記錄放在相同的塊中，因此在哈希記錄中只有樂曲的編碼和片段中第一個音符在歌曲中的位置，這樣提高了檢索的效率。2.2 可行性研究2.2.1 技術(shù)可行性本系統(tǒng)采用c+為開發(fā)語言、mysqlserver數(shù)據(jù)庫和microsoft visual studio vc+ 6.0運行環(huán)境。c+語言具有面向?qū)ο?、與平臺無關(guān)、安全、穩(wěn)定等優(yōu)良特性，是目前軟件設計中極為健壯的編程語言。microsoft visual studio vc+ 6.0支持如：c或c+語言編程，可運行在windows操作系統(tǒng)上，性能穩(wěn)定，使用方便，并且

24、提供可視化工具和向?qū)?。系統(tǒng)后臺數(shù)據(jù)庫采用mysql server 5.0，mysql是一個多用戶、多線程的sql數(shù)據(jù)庫，是一個客戶機/服務器結(jié)構(gòu)的應用，它由一個服務器守護程序mysql和很多不同的客戶程序和庫組成。mysql支持標準的ansi sql語句，支持多種平臺，在unix系統(tǒng)上該軟件支持多線程運行方式，從而能獲得相當好的性能。對于windows用戶，它可以在windows nt及xp系統(tǒng)上以系統(tǒng)服務方式運行，或者在windows 95/98系統(tǒng)上以普通進程方式運行。綜上所述，系統(tǒng)的開發(fā)平臺已成熟可行。2.2.2 經(jīng)濟可行性軟件開發(fā)周期一般為23個月，開發(fā)所需硬件軟件設施目前大多數(shù)pc機

25、系統(tǒng)能夠承擔，開發(fā)費用不高。目前，大多數(shù)單位都擁有高性能微機和局域網(wǎng)，該軟件系統(tǒng)的安裝、部署、運行和維護，都不會給單位增加太高的費用。2.2.3 操作可行性目前，大多數(shù)pc機和局域網(wǎng)能夠運行該系統(tǒng)，該系統(tǒng)的安裝、調(diào)試、運行不會改變原計算機系統(tǒng)的設置和網(wǎng)絡的布局，并且大多數(shù)用戶幾乎不用做任何培訓都能夠方便操作的軟件。2.3 目前可選擇的技術(shù)目前有許多軟件開發(fā)人員都開發(fā)了類似的系統(tǒng)，所選擇的技術(shù)都各有不同。數(shù)據(jù)庫技術(shù)方面：可以采用mysqlserver、access、db2、oracle等；應用模式方面：可以采用b/s模式、c/s模式、b/s+c/s混合模式；開發(fā)工具方面：可以采用c語言、c+、c

26、#、java等。這些技術(shù)都有這各自的優(yōu)點和缺點，通過不同的技術(shù)的選擇搭配，所開發(fā)出來的系統(tǒng)的效果也不同。但是根據(jù)該系統(tǒng)的經(jīng)濟可行性和操作可行性，本文選擇了使用c+開發(fā)語言和mysqlserver數(shù)據(jù)庫。2.4 技術(shù)開發(fā)工具概述2.4.1 c+開發(fā)語言概述c+語言是一種應用較廣的面向?qū)ο蟮某绦蛟O計語言，使用它可以實現(xiàn)面向?qū)ο蟮某绦蛟O計。面向?qū)ο蟮脑O計與面向過程的設計是有很大區(qū)別的，面向?qū)ο蟮某绦蛟O計是在面向過程的程序設計的基礎上一個質(zhì)的飛躍。下面簡單的介紹一下c+對面向?qū)ο蟪绦蛟O計方法的支持和實現(xiàn)。 支持數(shù)據(jù)封裝就是支持數(shù)據(jù)抽象。在c+中，類是支持數(shù)據(jù)封裝的工具，對象則是數(shù)據(jù)封裝的實現(xiàn)。面向過程

27、的程序設計方法與面向?qū)ο蟮某绦蛟O計方法在對待數(shù)據(jù)和函數(shù)關(guān)系上是不同的，在面向?qū)ο蟮某绦蛟O計中，將數(shù)據(jù)和對該數(shù)據(jù)進行合法操作的函數(shù)封裝在一起作為一個類的定義，數(shù)據(jù)將被隱藏在封裝體中，該封裝體通過操作接口與外界交換信息。對象被說明具有一個給定類的變量，類類似于c語言中的結(jié)構(gòu)，在c語言中可以定義結(jié)構(gòu)，但這種結(jié)構(gòu)中包含數(shù)據(jù)，而不包含函數(shù)。c+中的類是數(shù)據(jù)和函數(shù)的封裝體。在c+中，結(jié)構(gòu)可作為一種非凡的類，它雖然可以包含函數(shù)，但是它沒有私有或保護的成員。類中的私有成員一般是不答應該類外面的任何函數(shù)訪問的，但是友元函數(shù)便可打破這條禁令，它可以訪問該類的私有成員(包含數(shù)據(jù)成員和成員函數(shù))。友元可以是在類外定義

28、的函數(shù)，也可以是在類外定義的整個類，前者稱友元函數(shù)，后者稱為友元類。友元打破了類的封裝性，它是c+另一個面向?qū)ο蟮闹匾浴?c+支持多態(tài)性，c+答應一個相同的標識符或運算符代表多個不同實現(xiàn)的函數(shù)，這就稱標識符或運算符的重載，用戶可以根據(jù)需要定義標識符重載或運算符重載。 c+中可以答應單繼續(xù)和多繼續(xù)。一個類可以根據(jù)需要生成派生類。派生類繼承了基類的所有方法，另外派生類自身還可以定義所需要的不包含在父類中的新方法。一個子類的每個對象包含有從父類那里繼承來的數(shù)據(jù)成員以及自己所特有的數(shù)據(jù)成員。c+中可以定義虛函數(shù)，通過定義虛函數(shù)來支持動態(tài)聯(lián)編。 綜上所述，c+特點為封裝性，繼承性，多態(tài)性。封裝是把數(shù)據(jù)

29、與操作結(jié)合成一體，使程序結(jié)構(gòu)更加緊湊，同時避免了數(shù)據(jù)紊亂帶來的調(diào)試與維護困難；繼承增強了軟件的可擴充性 ，并為代碼重用提供了強有力的手段；多態(tài)性使程序員在設計程序時，對問題進行更好的抽象，以設計出重用性和維護性具佳期的程序。因此，本次設計選擇c+為開發(fā)語言。2.4.2 mysqlserver數(shù)據(jù)庫mysql是一個小型關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，開發(fā)者為瑞典mysql ab公司。在2008年1月16號被sun公司收購。目前mysql被廣泛地應用在internet上的中小型網(wǎng)站中。由于其體積小、速度快、總體擁有成本低，尤其是開放源碼這一特點，許多中小型網(wǎng)站為了降低網(wǎng)站總體擁有成本而選擇了mysql作為網(wǎng)

30、站數(shù)據(jù)庫。mysqlserver的特性：(1) 支持aix、freebsd、hp-ux、linux、mac os、novell netware、openbsd、os/2 wrap、solaris、windows等多種操作系統(tǒng)； (2) 為多種編程語言提供了api。這些編程語言包括c、c+、eiffel、java、perl、php、python、ruby和tcl等； (3) 支持多線程，充分利用cpu資源；(4) 優(yōu)化的sql查詢算法，有效地提高查詢速度；(5) 既能夠作為一個單獨的應用程序應用在客戶端服務器網(wǎng)絡環(huán)境中，也能夠作為一個庫而嵌入到其他的軟件中提供多語言支持，常見的編碼如中文的gb

31、2312、big5，日文的shift_jis等都可以用作數(shù)據(jù)表名和數(shù)據(jù)列名；(6) 提供tcp/ip、odbc和jdbc等多種數(shù)據(jù)庫連接途徑；(7) 提供用于管理、檢查、優(yōu)化數(shù)據(jù)庫操作的管理工具；(8) 可以處理擁有上千萬條記錄的大型數(shù)據(jù)庫；(9) 使用c和c+編寫，并使用了多種編譯器進行測試，保證源代碼的可移植性。3 系統(tǒng)概要設計3.1 系統(tǒng)總體設計思想根據(jù)需求分析的要求，總體設計是建立wav音樂特征庫、根據(jù)哈希算法建立哈希索引表、記錄用戶哼唱的音樂片段、對輸入的音樂片段進行特征提取、按照n_gram算法擴充查詢集合、利用余弦距離匹配算法進行匹配、計算檢索時間和將檢索結(jié)果反饋給用戶。(1)

32、wav音樂特征庫該模塊首先對wav音樂文件格式進行分析。其次，根據(jù)wav格式特征，從音高差和音長兩方面提取音樂旋律特征。最后，將提取的音樂特征存儲到數(shù)據(jù)庫中。(2) 建立哈希索引表為了提高系統(tǒng)檢索速度，對wav音樂特征庫中的歌曲建立整數(shù)哈希索引。對每首歌曲的音高差usd序列和音長lrs都按照哈希算法，將歌曲的id號和該片段的起始位置保存到哈希索引表中，便于用戶檢索。(3) 哼唱音樂的記錄和特征提取在該模塊中包括音樂信號預處理、音樂信號基音提取、基音提取后處理、音符切分、特征參數(shù)計算，并將處理后的數(shù)據(jù)存入數(shù)據(jù)中待檢索時調(diào)用。(4) n_gram算法對用戶哼唱的片段進行特征提取之后，要對音高差序列

33、再進行切分，本文中采用的滑動窗口的大小是3，切分后得到的新查詢集合中將有m-n+1個usd片段，其中m為原usd片段的長度，這樣擴大查詢集合，即所有可能的片段都進行檢索和匹配，提高了系統(tǒng)的準確性。(5) 余弦匹配算法最后采用余弦距離的匹配算法，從音高差和音長兩方面進行匹配，得到的余弦值是在0到1之間的小數(shù)，余弦值越接近于1，就說明匹配度越高。匹配后，將余弦值最大的三首歌曲的相關(guān)信息反饋給用戶。音樂哼唱檢索的主要框架設計如圖3.1所示：圖3.1 音樂哼唱檢索總體功能圖3.2 系統(tǒng)用例圖用例圖從用戶的角度描述系統(tǒng)功能，并指出各個功能的角色。本次設計中可以分為兩大模塊，一個是用戶哼唱處理功能模塊，另

34、一個是wav特征數(shù)據(jù)庫建立模塊。用戶哼唱處理功能模塊中，包括音樂文件記錄、音樂片段特征提取、n_gram算法擴充查詢集合、哈希索引等幾部分功能。用戶哼唱處理模塊頂層的用例圖如圖3.2所示。圖3.2 用戶哼唱處理用例圖在提取音樂片段特征中，又包括音樂信號預處理、音樂信號基音提取、基音提取后處理、音符切分、特征參數(shù)計算等功能。音樂片段特征提取的用例圖如圖3.2所示。圖3.3 音樂片段特征提取的用例圖wav特征數(shù)據(jù)庫建立模塊中包括wav音樂特征庫。該模塊首先對wav音樂文件格式進行分析。其次，根據(jù)wav格式特征，從音高差和音長兩方面提取音樂旋律特征。最后，將提取的音樂特征存儲到數(shù)據(jù)庫中。wav特征數(shù)

35、據(jù)庫用例圖如圖3.3所示。圖3.4 wav特征數(shù)據(jù)庫的用例圖為了進一步闡述執(zhí)行者與用例的關(guān)系，還應畫出相應的執(zhí)行者描述模板及用例描述模板。角色描述模板如圖3.5所示。圖3.5 角色描述模板3.3 數(shù)據(jù)庫邏輯設計對于音樂哼唱檢索系統(tǒng)而言，數(shù)據(jù)庫的設計很重要，數(shù)據(jù)庫的選擇上尤為重要，因為該系統(tǒng)要面對海量的音樂信息，選擇良好的數(shù)據(jù)庫以及設計方法，對于音樂檢索和系統(tǒng)實現(xiàn)都有積極地作用。3.3.1 數(shù)據(jù)庫設計方法簡述十余年來，人們努力探索，提出了各種數(shù)據(jù)庫設計方法，這些方法運用軟件工程的思想和方法，提出了各種設計準則和規(guī)程，都屬于規(guī)范設計方法。規(guī)范設計方法中比較著名的有新奧爾良方法。它將數(shù)據(jù)庫設計分為四

36、個階段：需求分析（分析用戶要求）、概念設計（信息分析和定義）、邏輯設計（設計實現(xiàn)）和物理設計（物理數(shù)據(jù)庫設計）?；趀-r模型的數(shù)據(jù)庫設計方法，基于3nf（第三范式）的設計方法，基于抽象語法規(guī)范的設計方法等，是在數(shù)據(jù)庫設計的不同階段上支持實現(xiàn)的具體技術(shù)和方法。規(guī)范設計法從本質(zhì)上看仍然是手工設計方法，其基本思想是過程迭代和逐步求精。3.3.2 概念模型設計e-r圖主要作用顯示各個實體的屬性以及實體之間關(guān)系。本系統(tǒng)中主要的實體有用戶哼唱音樂片段，音高差庫，音長庫，歌曲庫，音高差檢索結(jié)果集，音長檢索結(jié)果集，音長索引表，音高差索引表，索引結(jié)果集。圖3.6 系統(tǒng)主要e-r圖3.3.3 數(shù)據(jù)庫的關(guān)系模型設

37、計本系統(tǒng)中主要的關(guān)系模型設計及屬性如下：(1) 用戶哼唱音樂片段（自增id，音高差，音長）；圖3.7 用戶哼唱音樂片段及其屬性圖(2) 音高差庫（歌曲id號，音高差，音高差序列長度）；圖3.8 音高差庫及其屬性圖(3) 音長庫（歌曲id號，音長）；圖3.9 音長庫及其屬性圖(4) 歌曲庫（歌曲id號，歌曲名稱，歌手，專輯）；圖3.10 歌曲庫及其屬性圖(5) 音高差檢索結(jié)果集（歌曲id號，歌曲名稱，歌手，專輯，檢索時間）圖3.11 音高差檢索結(jié)果集及其屬性圖(6) 音高差索引表（關(guān)鍵字，歌曲id，音高差片段位置）圖3.12 音高差索引表及其屬性圖4 系統(tǒng)詳細設計及實現(xiàn)4.1 系統(tǒng)數(shù)據(jù)庫詳細設計

38、數(shù)據(jù)庫的設計是系統(tǒng)進行詳細設計的開始，它是系統(tǒng)的后臺設計部分，用來存儲信息以供前臺調(diào)用和輸出。數(shù)據(jù)庫設計的是否合理將直接影響到系統(tǒng)的穩(wěn)定性、安全性及可維護性，同時也會給后期的編碼工作帶來諸多不便。在進行了需求分析和概要設計后，接下來將詳細介紹系統(tǒng)中各部分信息的存儲方式。本系統(tǒng)設db為數(shù)據(jù)庫名。4.1.1 用戶哼唱片段信息表用戶哼唱的音樂片段是以wav格式存儲的，在對輸入的音樂信號進行處理后，要提取音樂特征，分別為音高差和音長序列，因此為方便以后的數(shù)據(jù)處理，用戶哼唱片段信息表的設計入表4-1。表4.1 用戶哼唱音樂片段表 one_resouce字段名數(shù)據(jù)類型長度描述idint10自增idaltu

39、ratext音高差序列l(wèi)engthint10音高差序列長度duraciontext音長序列l(wèi)ength2int10音長序列長度4.1.2 wav特征庫設計wav文件作為多媒體中使用的聲波文件格式之一，它是以riff格式為標準的，只要了解了文件的格式，就可以方便的將所需要的旋律特征提取出來。從編程的角度來看，其處理過程并不復雜，處理的速度更快，占用系統(tǒng)的資源也更少，是最方便、最容易實現(xiàn)的。因此在wav特征庫中設計了音高差表、音長表、歌曲表。(1) 音高差表altura用來存放從音樂文件中提取出來的音高差序列。表4.2 音高差表 altura字段名數(shù)據(jù)類型長度描述idint10歌曲id號conte

40、xttext音高差序列l(wèi)engthint10音高差序列的長度(2) 音長表duracion用來存儲從音樂文件中提取出來的音長序列。表4.3 音長表 duracion字段名數(shù)據(jù)類型長度描述idint10歌曲id號timetext音長序列rightansint4正確答案(3) 歌曲表中記錄了所有歌曲的信息，為音樂檢索提供海量的數(shù)據(jù)。表4.4 歌曲表songs字段名數(shù)據(jù)類型長度描述idint10歌曲id號namevarchar45歌曲名稱singervarchar45歌手姓名albumvarchar45歌曲所在專輯4.1.3 索引表由于本次設計中的數(shù)據(jù)量較大，因此在設計哈希表時如果采用定義數(shù)據(jù)結(jié)構(gòu)來

41、存儲哈希值，那么會占用大量的內(nèi)存空間，影響程序的運行速度，因此在數(shù)據(jù)庫中設計了音高差和音長索引表，這樣有效地節(jié)省了內(nèi)存空間和提高了系統(tǒng)運行效率。另外哈希表的長度選擇29，因為usd三個字符的所有組合有27種可能，選擇29方便線性處理沖突。表4.5 音高差索引表 alturaindex字段名數(shù)據(jù)類型長度描述keyint10關(guān)鍵字大?。?-29）songidtext當前音高差片段所在歌曲的id號positiontext當前音高差片段在整首歌曲的音高差片段中的位置表4.6 音高長索引表 duracionindex字段名數(shù)據(jù)類型長度描述keyint10關(guān)鍵字大小（1-29）songidtext當前音長

42、片段所在歌曲的id號positiontext當前音長片段在整首歌曲的音長片段中的位置4.1.4 檢索結(jié)果集本次設計中要求根據(jù)音高差檢索時，要將相似度最高的前三首歌的信息反饋給用戶，當根據(jù)音長檢索時，要將匹配度最高的前十首歌曲的信息反饋給用戶，因此檢索結(jié)果集中分為音高差檢索結(jié)果表和音長檢索結(jié)果表。(1) 音高差檢索結(jié)果表：表4.7 音高差檢索結(jié)果表 resultaltura字段名數(shù)據(jù)類型長度描述idint10歌曲id號namevarchar45歌曲名稱singervarchar45歌手姓名albumvarchar45歌曲所在專輯timefloat檢索時間(2) 音長檢索結(jié)果表表4.8 音長檢索結(jié)

43、果表 resultduracion字段名數(shù)據(jù)類型長度描述idint10歌曲id號namevarchar45歌曲名稱singervarchar45歌手姓名albumvarchar45歌曲所在專輯timefloat檢索時間4.2 系統(tǒng)功能詳細設計在上一章中對哼唱檢索系統(tǒng)的各個功能模塊的設計進行了初步的介紹，接下來這一節(jié)將要對各個功能模塊的具體實現(xiàn)和設計過程中所采用的處理方法及所使用的各種相關(guān)技術(shù)展開詳細的介紹。4.2.1 wav特征提取(1) 細化音樂旋律輪廓特征旋律的變化是指相鄰音符的音高和音長變化。研究指出，人們很難準確的把握每個音符的音高和持續(xù)時間，但是對音高和音長的變化卻能準確的哼唱出來。

44、然而許多研究中將相鄰音符音高和音長的變化分為u、s、d三種情況，u代表后一個音比前一個音高，s代表后一個音與前一個音高相同，d代表后一個音比前一個音低，音長的描述和音高差相類似。通過對midi音樂進行統(tǒng)計，相鄰音符的音階差大多在2，21之間，音長比大約在 0.8ms，1.2ms之間。3級輪廓圖既能夠清楚的區(qū)分旋律的變化又避免了返回過多的檢索結(jié)果，取得了比較理想的效果。(2) 采用“音符起點一音符終點”的音長計算方式“音符起點一音符終點”是指從一個音符的起始時刻到音符的結(jié)束時刻之間的間隔。實驗中發(fā)現(xiàn):人們在哼唱的時候，對于每個音符的開始時間把握的很好。而且，當節(jié)奏比較慢或者某些音符比較長時，哼唱

45、者并沒有耐心去唱完整個音符，經(jīng)常會提前結(jié)束。首先對旋律文件進行分幀處理，每幀時間長度去20ms，當一個幀的平均能量超過輸入音頻信號幀平均平方根能量的50%時，認為該幀是一個音符的起點，當一個幀的能量低于輸入音頻信號幀平均平方根能量的30%時，并持續(xù)時間超過60ms，就認為該幀是一個音符的終點。因此，系統(tǒng)將“音符起點一音符終點”作為每個音符的長度，大大提高了檢索的準確程度。(3) 特征提取信號預處理 對于midi等不包含真實聲音數(shù)據(jù)的音樂文件，可以將其中的內(nèi)容當作字符串來處理。但是wav、mp3等格式的音樂文件存儲的是真實的聲音數(shù)據(jù)，必須對其進行音樂信號分析，進而提取特征并進行相應的處理。在按幀

46、進行音樂信號分析、提取音樂信號參數(shù)之前，有一些經(jīng)常使用的、共同的短時分析處理需要預先進行，如音樂信號的加窗分幀、濾波去噪、預加重等處理。在實際中，加窗分幀采用連續(xù)分段和漢明窗函數(shù)時較好的方法，考慮到在基音周期提取時，窗長應大于兩個基音周期才能正確的提取出基音，所以系統(tǒng)的幀長選擇20ms。帶通濾波器可以減少噪音，起到濾波去噪的功效。但是由于本次設計的時間局限，因此只采用了加窗分幀的預處理方法?；籼崛?自相關(guān)函數(shù)是對信號進行短時相關(guān)分析時最常用到的特征函數(shù)。假設音樂信號經(jīng)過幀長為n的窗口截取為一段加窗信號，則的自相關(guān)函數(shù)為：= （4.1）其中k=(-n+1)(n-1)。由于信號的自相關(guān)函數(shù)在基音

47、周期的整數(shù)倍位置上會出現(xiàn)峰值，因此可通過檢測峰值的位置來提取基音周期，再取倒數(shù)就得到了最終的基音。當對音樂信號的每一幀信號提取基音后，可形成基音串，而基音串值的變化可對應音調(diào)的變化。在此基礎上可提取音樂的內(nèi)容特征如音高變化和音長變化等，并進行檢索。自相關(guān)函數(shù)如圖4.1所示。圖4.1 自相關(guān)函數(shù)流程圖 基音提取后處理當用戶通過麥克風或手機哼唱一段音樂旋律時，所得到的聲音波形不可避免的會摻雜有各種噪聲，同時用戶的哼唱并不一定連續(xù)、流暢，所以在波形的各個部分都很有可能出現(xiàn)無聲段或噪聲段。而這些無聲段和噪聲段中提取出的基音周期顯然不是我們想要的結(jié)果，會對后面的旋律匹配產(chǎn)生很大的于擾。因此，基音提取后處

48、理的任務就是要去除無聲段和噪聲段的基音曲線。具體方法是，使用能量檢測來區(qū)分無聲段，使用過零率和基音來區(qū)分噪聲段。聲音波形的振幅大小說明了聲音的強度，在數(shù)字信號處理中用能量來表示。無聲時波形的振幅理論上應該是零，但實際上受到各種內(nèi)部和外部噪聲的影響，有時會有比較小的振幅出現(xiàn)，而有聲時的波形振幅就要大得多，因此可以通過聲音波形振幅的大小來判斷有聲和無聲的情況，系統(tǒng)是采用短時能量來進行能量檢測的。首先對旋律文件進行分幀，每幀的時間長度取20ms，求每一幀的評價能量x，計算平均平方根能量。當一個幀的平均能量超過輸入音頻信號幀平均平方根能量的50%時，認為該幀是一個音符的開始，當一個幀的能量低于輸入音頻

49、信號幀平均平方根能量的30%時，并持續(xù)時間超過60ms，就認為該幀是一個音符的結(jié)束。過零率是指在單位時間內(nèi)信號跨越零值的次數(shù)，也就是信號符號改變的次數(shù)，是對信號頻率的一種簡單度量。對于窄帶信號，如單一正弦波而言，其過零率是比較精確的，為信號頻率的兩倍。對于一個聲音波形來說，如果頻率越高，那么其過零率也越高;頻率越低，則過零率也越低。對于人所發(fā)出的聲音頻率，一般合理的范圍在8731hz和784hz之間 ，在此范圍之外的波形就可以作為噪聲過濾掉。在實際使用中，系統(tǒng)采用短時過零率，即一個短時幀內(nèi)信號的過零率來去除噪聲.中值平滑濾波是一種能有效抑止聲音波形中非典型點的信號處理技術(shù)。由于本次設計中的處理

50、有限，因此沒有進行此步處理。 音符切分 去除了噪聲、無聲和非典型點的波形文件切分為一個個usd的片段，每個片段包含一個獨立、完整的音符信息。聲音波形的切分信息在聲音波形預處理的能量檢測階段就可以得到，在判斷有聲和無聲的同時，相應的音符切分位置也就可以確定了。 特征參數(shù)計算 有了聲音波形的切分信息后，就可以從中計算出旋律特征了。音符的頻率就是音高，同一音高的長度就是音長。只要比較相鄰音符的過零率就可以獲得相對音高差序列。音長的獲得只要根據(jù)音符的切分就可以了。綜合考慮到用戶的廣泛性和不同用戶哼唱的習慣和哼唱能力，系統(tǒng)最終采用了(音高差、音長比)的二維特征。計算特征參數(shù)后，就完成了從用戶哼唱音樂片段

51、中提取旋律特征的工作。圖4.2 wav音樂文件特征提取流程圖4.2.2 哼唱音樂的記錄和特征提取將哼唱的內(nèi)容采集并存儲到系統(tǒng)中，可以由系統(tǒng)自帶的錄音程序完成，最終以wav格式將錄制的哼唱內(nèi)容保存到相應的文件中。從保存的文件中提取特征與wav特征庫的提取的方法和步驟相同。4.2.3 查詢擴展在獲取哼唱音樂特征后，如果直接進行匹配，只能是進行精確匹配，那么若輸入有誤的話，就會匹配失敗，因此大大降低了匹配的準確度。最終，本次設計按照滑動窗口方法進行n_gram切分的查詢擴展方法。本次提出的方法是將用戶查詢片段的旋律輪廓按照滑動窗口方法，進行n_gram切分，每次右移一個usd音符，假設一個usd序列

52、的長度為m，則查詢后所生成的分片數(shù)為m-(n-1)=m-n+1.本次設計中設n為3。設查詢目標的usd序列為dddsududud，則進行n-gram切分后的片段為：ddd dds dsu sud udu dud udu dud。擴充查詢集合后，以集合中的每個查找項作為新的查找項，查找哈希索引。n-gram方法的實現(xiàn)如圖4.2所示。圖4.3 n_gram算法流程圖4.2.4 哈希索引為提高查詢效率，對旋律輪廓按照n_gram方法切分后，建立了順序的哈希索引。對每一段旋律片段取其音高差和音長的旋律輪廓作為索引項，與歌曲id號和片段中第一個音符在歌曲的位置共同組成數(shù)據(jù)記錄，建立哈希索引。系統(tǒng)中的哈希

53、表中，具有相同的哈希值的記錄放在相同的塊中，因此哈希記錄中只有歌曲的id號和片段中第一個音符在歌曲中的位置。由于哈希表是一首一首建立的，之后沒有更新操作，因此在哈希表的數(shù)據(jù)是有序的。這在索引查找后的處理時，可以大大提高效率，哈希算法的實現(xiàn)如圖4.3。圖4.4 哈希索引實現(xiàn)流程圖4.2.5 余弦匹配算法余弦距離是目前被廣泛應用的向量相關(guān)性比較的主要手段，基于“余弦距離”的旋律匹配算法在目前的旋律匹配算法中得到了廣泛的應用，這種算法將與用戶哼唱與存儲在數(shù)據(jù)庫中的樂曲片段看作是兩個待比較的向量，通過“余弦距離”的計算，比較兩段旋律向量的相似程度，余弦距離越接近1，說明旋律片段更接近,具體實現(xiàn)如圖4.

54、4。若用戶輸入的片段旋律特征作為一個向量，經(jīng)過檢索后的數(shù)據(jù)向量為，則余弦距離公式為： （4.2）圖4.5 余弦匹配算法實現(xiàn)流程圖4.2.6 系統(tǒng)響應時間的計算響應時間的計算，可以利用windows api中的函數(shù)直接獲得系統(tǒng)當前時間，時間可以精確到毫秒級。在用戶輸入結(jié)束后，獲得一次系統(tǒng)時間，并保存，當檢索匹配結(jié)束后，再獲得一次系統(tǒng)時間，兩次時間差即為響應時間。獲得系統(tǒng)時間的函數(shù)如下：#include systemtime getsystemtime( void ) systemtime sys; /定義系統(tǒng)時間對象getlocaltime( &sys ); /獲得本地時間return sys;

55、 5 系統(tǒng)的調(diào)試與測試5.1 系統(tǒng)的調(diào)試系統(tǒng)的調(diào)試與驗證，是系統(tǒng)編碼完成之后所進行的最后一步操作，通過本步的操作可以測試系統(tǒng)所實現(xiàn)的功能是否齊全，系統(tǒng)的運行是否穩(wěn)定，運行過程中是否會出現(xiàn)異常的結(jié)果。下面將系統(tǒng)設計中的主要功能測試進行說明。在整個系統(tǒng)實現(xiàn)的過程中，遇到了很多需要解決的問題。在程序開發(fā)的初步階段，對于題目中的一些算法還不是很了解，編程環(huán)境的使用也不夠熟練，因此在初期的程序設計中，遇到了很多問題。以下是編碼調(diào)試時遇到的一些問題以及問題的解決方法： (1) 在開始設計中，對于哼唱音樂沒有進行任何預處理，就直接進行提取，經(jīng)過對比后發(fā)現(xiàn)，特征描述不夠準確，于是在提取特征之前，對音信號首先進行了預處理，并且在輸入過程中，盡量避免不必要的噪音。(2) 設計中使用了mysql server數(shù)據(jù)庫，開始的時候，vc+環(huán)境無法與數(shù)據(jù)庫相連接，查閱資料之后，發(fā)現(xiàn)要在編程環(huán)境中使用數(shù)據(jù)庫，要設置一些環(huán)境變量并且要將mysql的頭文件放在vc+的運行路徑下。(3) 對sql語句有一些了解，但是在vc+環(huán)境中執(zhí)行sql語句，要進行一些變化，于是就對mysql中的類進行了深入了解，最終得出要在c+中執(zhí)行sql語句，并對數(shù)據(jù)庫進行跟新，一定要將sql的內(nèi)容進行提交。(4) 起初，設計