基于小波包最優(yōu)基的音樂指紋提取算法_圖文

1、第35卷V01.35第9期No.9計算機工程Computer Engineering2009年5月May2009多媒體技術(shù)及應(yīng)用文章編號tl伽肌3428(2009oHJ236-_02文獻標(biāo)識碼t A中田分類號:TN912.3基于小波包最優(yōu)基的音樂指紋提取算法陳芳”,李偉1,李曉強2(1.復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院,上海200433;2.上海大學(xué)計算機科學(xué)與工程學(xué)院,上海200072;3.上海行知學(xué)院,上海200940蔓:數(shù)字音樂指紋提取的主耍目的是建立一種有效機制,用于比較2個音樂文件的聽覺質(zhì)量。提出一種基于小波包最優(yōu)基分解的音樂指紋提取算法,利用與音頻內(nèi)容密切相關(guān)的小波包系數(shù),將其作為特征進

2、行指紋提取。實驗結(jié)果表明,該算法對MP3,WMA和RM壓縮、噪聲、Stirmark foraudio工具中常見的音頻信號處理具有強魯棒性,且在不同音樂之間具有較高可區(qū)分性。關(guān)健詞:數(shù)字音樂指紋;小波包變換;最優(yōu)基;魯棒性Music Fingerprint Extraction AlgorithmBased on腸velet Packet Best.basisCHEN Fan91j,Ll Weil,LI Xiao.qian92(1.School of Computer Science and Technology,Fudan University,Shanghai200433;2.School

3、of Computer Science and Engineering,Shanghai University,Shanghai200072;3.Shanghai Xingzhi College,Shanghai200940 AbstractThe main purpo!;e of digital music fingerprint extraction is to establish an effective mechanism used to compare the auditory quality between two pieces of audio.This paper presen

4、ts a music fingerprint extraction algorithm based on wavelet packet bestbasis decomposition.It uses wavelet packet coefficients related to radio content as the feature to extract fingerprint.Experimental results show that this algorithm is robust against con'lnlon audio signal operations like MP

5、3,WMA and RM compression.noise addition,and audio processing in Stirmark for audio.This algorithm exhibits high ability to differentiate between different songs.Key wordsl digital music fingerprint;Wavelet Packet Transform(wPr;bestbasis;robust1概述斟為音頻壓縮技術(shù)的進步和大容量存儲器的出現(xiàn)使互聯(lián)網(wǎng)上以音樂為主的音頻信息量越來越大,所以幾乎不可能手工選取某

6、首歌曲,因此,產(chǎn)生了可以進行音樂自動識別的數(shù)字音樂指紋技術(shù)。數(shù)字音樂指紋是指可以代表一段音樂重要聲學(xué)特征、基于內(nèi)容的緊致數(shù)字簽名,其目的是建立一種用于比較2個音樂數(shù)據(jù)聽覺質(zhì)量的有效機制。它主要應(yīng)用在進行未知音樂搜索的音樂識另0中。進行搜索時,不直接比較很大的音樂數(shù)據(jù),而是比較它對應(yīng)的較小數(shù)字指紋。大量音樂數(shù)據(jù)的指紋及其相應(yīng)元數(shù)據(jù),如歌曲名稱、詞曲作者、歌詞等內(nèi)容一起存儲在一個數(shù)據(jù)庫中,并采用指紋作為相應(yīng)元數(shù)據(jù)的索引IIo 音樂指紋系統(tǒng)由一個計算聽覺重要特征的指紋提取算法和一個在指紋數(shù)據(jù)庫中進行有效比對的搜索算法構(gòu)成,如圖1所示。圈1音樂指紋系統(tǒng)框架上述系統(tǒng)模仿人耳識別音樂的過程。許多音樂作品的

7、指紋在離線情況下被計算出來,連同一些重要元數(shù)據(jù)一起存儲到數(shù)據(jù)庫中。需要識別一段未知音樂時,先按指紋提取算法.236.一計算其音樂特征,然后在存儲于數(shù)據(jù)庫的大量音樂指紋中進行搜索比對。有效指紋提取算法能使被提取出的、經(jīng)過各種信號處理的未知音樂指紋與數(shù)據(jù)庫中原始版本的音樂指紋一致。被提取的音樂指紋通常需要滿足以下條件¨J:(1魯棒性。未知音樂能對各種攻擊保持穩(wěn)定,在經(jīng)受較嚴霞的音頻信號處理后,仍然能在數(shù)據(jù)庫中識別出其原始版本。(2區(qū)分性。不同歌曲之間的指紋應(yīng)具有較大差異,而同一音樂不同版本間的指紋差異應(yīng)很小。(3緊致性。用較短的指紋可以有效表示歌曲特征。(4簡易性。算法簡單易行,運算時無

8、須占用較多資源,且運行快速。多數(shù)指紋提取算法基于以下方法:將音樂信號分成互相重疊的幀,對每個幀計算一系列特征,此類特征需要對各種音頻信號處理在一定程度E保持不變。已有特征主要包括傅立葉變換FFrIj J、小波變換wTHl、邁爾倒譜系數(shù)Mel Frequency CepstralCoefficients(MFCCpl、頻譜平滑度Spectral Flatness【oj、尖銳度Sharpnessl01、線性預(yù)測編碼Linear Predictive Coding(LPC161以及它們的導(dǎo)出量(如均值和方差。通常使用分類器技術(shù)(如隱含馬爾可夫模型Hidden Markov Models(HMMH1或

9、量化技術(shù)將卜述特征映射為一個更簡潔的表示。每幀算出的指紋稱為子指紋(subfingerprint,一個子指紋通常無法包含足夠信息來進行音樂識別。足以識別完整音樂基金項目:國家自然科學(xué)基金資助項N(61M02008作者筲介:陳芳(1972-,女,講師、碩士研究生,主研方向音頻識別與認證;李偉、李曉強,副教授、博士收藕日期:2008一l!-04Email:blueelain的未知音樂單元稱為指紋塊(fingerprint block,即指紋粒度。小波包變換(Wavelet Packet Transform,WPT是一種有效的信號時頻分析工具,能有效刻畫信號特性并反映其變化細節(jié)。本文提出一種基于小波

10、包變換并采用最佳子樹分解選擇最優(yōu)基的音樂指紋提取算法,通過計算被優(yōu)選的小波包系數(shù)能量與平均值之間的比值提取音樂指紋。將本文算法與現(xiàn)有數(shù)據(jù)庫搜索算法相結(jié)合,可以構(gòu)成有效的音樂指紋系統(tǒng)。2小波包變換與最優(yōu)小波包基的選擇特征提取是音樂指紋生成的關(guān)鍵步驟。在實際信號,尤其是非平穩(wěn)信號的處理中,信號任意時刻的頻域特征很霞要,因此,需要使用能將時域、頻域信息結(jié)合起來,用于描述信號的時頻分析方法。使用較多的一種時頻分析方法是小波變換,它在時間域和頻率(尺度域都具有表征信號局部特征的能力。在正交小波分解過程中,低頻(近似系數(shù)被進一步分解成低頻和高頻(細節(jié)系數(shù),而高頻系數(shù)不再被分解。小波包變換是小波變換的鶯要擴

11、展,它提供了更豐富且精確的信號分析方法。圖2(a顯示了尺度為3的小波包變換,信號的低頻部分和高頻部分被同時分解,保留了信號的完整能量信息,因此,可以更精確地反映局部情況。根據(jù)小波包的組織方式,對于給定的正交小波,一個長度為N=2L的信號的分解方式最多可以有2種,即一個深度為L的完整二叉樹的子樹數(shù)目,該值極大。在完整的二叉樹結(jié)構(gòu)中,并非所有二叉樹都有價值,即不是每個節(jié)點都需要進一步分解為2個部分,因此,產(chǎn)生了如何實現(xiàn)小波包最佳分解的問題。需要根據(jù)一個簡單可行的原則尋找一種最佳樹結(jié)構(gòu)(或最優(yōu)小波包基(圖2(b,如最小熵標(biāo)準(zhǔn)。(a小波包分解(b最優(yōu)子樹圈2小麓包分解與量倪子村遺擇基于最小熵的最優(yōu)小渡

12、包基生成步驟如下:(1計算每個節(jié)點的熵值e。(2沿葉子節(jié)點向根節(jié)點,對非葉子節(jié)點,如果ele2(el是節(jié)點N的熵值,2是節(jié)點子節(jié)點的熵值總和,則節(jié)點將被保留為最優(yōu)樹的一個節(jié)點,其下的子節(jié)點被去除。否則,節(jié)點Jv的熵值被P2替代,子節(jié)點保留。(3按從左到右、從下往上的順序依次進行最優(yōu)基的選擇,直到根節(jié)點為止,最終得到整棵最優(yōu)樹,即最優(yōu)基的集合。上述算法使整個小波包以及每個節(jié)點的分解都得到了優(yōu)化。最優(yōu)基的選取使信號分解后,小波包系數(shù)彼此間有較大差別、主次明顯,易于舍去非關(guān)鍵數(shù)據(jù)并保留關(guān)鍵數(shù)據(jù)。其實質(zhì)是在信息損失較少的前提下,使信號中隱含的信息能集中反映在少數(shù)幾個分解系數(shù)上,以實現(xiàn)信號的分解和重建,

13、為信號處理中系數(shù)的取舍和減少數(shù)據(jù)量等提供前提條件。3指紋提取算法音樂指紋提取算法如圖3所示,主要步驟如下:(1預(yù)處理。輸入音樂被轉(zhuǎn)換為16hit/sample,采樣率為44。l kHz的單聲道信號。(2分幀。音樂信號被分解為互相1li疊l,2的幀,每幀使用Hamming窗以平滑幀邊緣。實驗中幀長取為2048,約0.05S。(3小波包分解和最優(yōu)基選取。采用“dbl”小波對每幀音樂信號進行3層小波包分解,并使用基于最小Shannon 熵的最優(yōu)小波包基生成算法求出最佳子樹。(4統(tǒng)計量計算。根據(jù)最佳子樹每個葉子節(jié)點對應(yīng)的系數(shù),計算如下3個能量統(tǒng)計值:互=窆i工(甩l。,ESUMt=芝置,EAVG=二窆

14、ESUMr,其中,Hn是第k幀節(jié)點i的第n個系數(shù);Ei表示第k幀第i個葉子節(jié)點的能鼉值;ESUMk表示第k幀信號能量值;EAVG 表示音樂信號所有幀的平均能量。(5Hash值生成和音樂指紋生成。將上述所有幀的ESUM分別與EAVG比較,每幀產(chǎn)生1位Hash比特值,Hk=:老翻w。將所有Hash 位連接起來即構(gòu)成該音樂的指紋。圈3音曩指紋提取癱程4實驗結(jié)果本文使用誤碼率(Bit Error Rate,BER作為未知音樂指紋和原始音樂指紋問的相似性度量標(biāo)準(zhǔn)。實驗主要驗證使用本算法生成的音樂指紋對常見音頻信號處理是否具有魯棒性,以及不同歌曲指紋之間的可區(qū)別性。4.1魯棒性實驗隨機選取classica

15、l,folk,R&B和POP風(fēng)格的5段音樂,從中分鄹隨機選取約lO.5s的音樂片段(16bit/sample、采樣率為44.1kHz的單聲道信號進行實驗。每個音樂片段的指紋都將經(jīng)過一些常見音樂信號處理,并分別與原始指紋進行比較,輸出誤碼率作為音樂指紋魯棒性的判斷依據(jù)。魯棒性測試結(jié)果如表1所示。襲1魯棒佳舅試結(jié)果(下轉(zhuǎn)第240頁一237algorithm.FS,UMHexagonS(hybridUnsymmetrical-cross Multi Hexagongrid search一1算法和EPZS(Enhanced PredictiveZonalSearchp1算法進行比較。UMHex

16、agonS和EPZS已被商用,且它們的算法效率在H.264中較好,具有較高對比意義。主要比較了信噪比Ps懈、比特率和搜索時間。測試結(jié)果如表l一表3所示。由表l可以看出,新算法的峰值信噪比在一些測試序列上有所下降,但下降幅度很小,保持了圖像質(zhì)量,且對部分測試序列有所提高,能更好地重構(gòu)圖像。由表2可以看出,新算法的比特率比其他3種算法有所增加,但幅度在0.5%左右,且對部分序列有所降低,幅度在0.4%左右。由表3可以看出,本算法的搜索時間與FS,UMHexagonS,EPZS相比,分別節(jié)約了80%,28%,30%。綜上所述,在保持再構(gòu)圖像質(zhì)量和比特率基本不增加的前提下,本算法的搜索速度得到很大提高

17、。襲l船糯比較出刮PSNRIdB 奉算法與其他算法的PSNR差異/dB廳明一一FSUMHexagonS EPZS本算法AFSAUMHexagonSAEPZS akiyo 38873885388638850.020.0000lsuzie 37.45374437.4337.45000+0.01.tO 02coastguard 350l35.0235.0l 35.02+o 010.00+0.0l earphone 37.03369636993692.010004.0.07highway3S i538,133S.1038.07.008.0.06.0.03序列比特率/(KbsJ奉算法與其他算法的比特率差

18、異.:!l j !:!.一FSUMHexagonSEPZS本算法AFSAUMHexagonSAEPZS akiyo 188.16188.32188.32188,24+o,04.0.04.0,04suzie184.1618368184.4018368-0.260.00.0.39coastguard33280333363338433328-tO.140.02.0.17earphone28680287.922869629056+I.3I -t092+1.25highway 147.28147761483214808+054+022.0.16(上接第237頁表1數(shù)據(jù)顯示,對于上述常見音頻信號處理,雖然

19、各個不同種類音樂的抵抗力有所差別,但所有誤碼率均低于0.13。尤其是對于一些常用編碼,如MP3,WMA和RM,在高壓縮率下仍能保持低于0.08的誤碼率,達到了很高的魯棒性。4,2區(qū)別性實驗若不同音樂片段具有相似指紋,則會在進行指紋檢索時引起誤判,本實驗測試不同歌曲間的指紋是否具有足夠大的距離,結(jié)果如圖4所示。DestinYs Celilie 訪鬈小提琴曲排莆Madonna child Dion 小提琴曲n00000400004II 1049330,5200捧簫0400000000446705333047J I DestinYlchild04ll 044670(N×0047784689

20、Madonna 04933O5333047780000O 05378Celille Dloll05200047l104689053780000圈4不同歌目的指墳臣膏圖4數(shù)據(jù)顯示,同類或不同類歌曲之間指紋比對的誤碼率介于0.4和0.5378之間,多數(shù)在0.5左右,即指紋間具有較大差別,不容易引起誤判?？梢?本文算法在不同歌曲間具有較強可區(qū)分性。5結(jié)束語本文算法提取的指紋對常見音頻信號處理具有很高魯棒性,可以有效應(yīng)用于音樂識別系統(tǒng)。此算法有待改進,主要是對時間域信號處理的抵抗,如音樂片段的任意剪切和復(fù)制、局部時間伸縮等。24廿一表3搜索時聞比較li_-_-_-_-_-_lll。I。_-_-_-_l

21、l_l一序列搜索時Ib/ms本算法與其他算濁的搜索時間差異/f%FS UMHexagonS EPZS本算法AFS AUMHexagonSAEPZSakiyo 0799O 235O 2170.126-8423-46384194suzie07330.2180,32001557885.2890-5156coastguard O.816O.283O.328O.2197316226l 33.23earphone 0784O 283O.359O 233701917.6735101:!:!:!:!:罌!:!:!:罌:堅14結(jié)束語本文算法能保證圖像質(zhì)量和比特率基本不變,并極大提高運動估計速度。下一步的研究方向

22、是使該算法能準(zhǔn)確確定大運動序列中的運動矢量。參考文獻【l】LiRenxiang,ZengBing,Liou M L.A New Threestep SearchAlgorithmforBlock Motion EstimationlJ.IEEE TransactionsonCircuits and Sysmms for Video Technology,1994,嘶4:438-442.【2】Zhn Ce,Lin Xiao,Chau Lappui.Hexagonbased Search Pattern forFastBlock MotionEstimationJ.正EE Transactions

23、onCircuitsand Systems forVideoTechnology,2002,12(5:349355.【3】P0LaiMan,Ma WingChung.ANewCenter-basedSearchAlgorithm for Block MotionEstimationC/Proceedingsofthe1995International ConferenceonImage Processing.Washington,USA:【s.n.1,1995:410一413.【4】I.am Chiwai,Po Laiulan.Fast Block Motion Estimation with

24、 EarlyAcceptanceTechniquein H.2641J-VTCllProceedingsofIntlSymposium onCircuitsandSystems.【S.I.1:IEEE Press,2005:1513.1516.【5】ToumpisAM.Enhanced Predictive Zonal Search for Single andMultiple Frame MotionEstimationCl/proeeedings of Conf.onVisual Communications and Image Processing.San Jose,USA:【s.n.1

25、20012:10691079.編輯陳暉參考文獻【l】Cano PBaffle E,Gomez E,et a1.Audio Fingerprinting:ConceptsandApplicationsC/Proc.of the1stInternational ConferenceonFuzzySystemsand Knowledge Discovery.Singapore:【s.n.】。2002.【2】C.ano只Baffle EKalker L eta1.A ReviewofAlgorithmsfor AudioFingerprintingC/proc.of International WorkshoponMultimediaSignalProcessing.VirginIslands,USA:【s.n.】,2002:169-173.【3】Ramalingam