基于小波包最优基的音乐指纹提取算法_图文

1、第35卷V01.35第9期No.9计算机工程Computer Engineering2009年5月May2009多媒体技术及应用文章编号tl伽肌3428(2009oHJ236-_02文献标识码t A中田分类号:TN912.3基于小波包最优基的音乐指纹提取算法陈芳”,李伟1,李晓强2(1.复旦大学计算机科学技术学院,上海200433;2.上海大学计算机科学与工程学院,上海200072;3.上海行知学院,上海200940蔓:数字音乐指纹提取的主耍目的是建立一种有效机制,用于比较2个音乐文件的听觉质量。提出一种基于小波包最优基分解的音乐指纹提取算法,利用与音频内容密切相关的小波包系数,将其作为特征进

2、行指纹提取。实验结果表明,该算法对MP3,WMA和RM压缩、噪声、Stirmark foraudio工具中常见的音频信号处理具有强鲁棒性,且在不同音乐之间具有较高可区分性。关健词:数字音乐指纹;小波包变换;最优基;鲁棒性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概述斟为音频压缩技术的进步和大容量存储器的出现使互联网上以音乐为主的音频信息量越来越大,所以几乎不可能手工选取某

6、首歌曲,因此,产生了可以进行音乐自动识别的数字音乐指纹技术。数字音乐指纹是指可以代表一段音乐重要声学特征、基于内容的紧致数字签名,其目的是建立一种用于比较2个音乐数据听觉质量的有效机制。它主要应用在进行未知音乐搜索的音乐识另0中。进行搜索时,不直接比较很大的音乐数据,而是比较它对应的较小数字指纹。大量音乐数据的指纹及其相应元数据,如歌曲名称、词曲作者、歌词等内容一起存储在一个数据库中,并采用指纹作为相应元数据的索引IIo 音乐指纹系统由一个计算听觉重要特征的指纹提取算法和一个在指纹数据库中进行有效比对的搜索算法构成,如图1所示。圈1音乐指纹系统框架上述系统模仿人耳识别音乐的过程。许多音乐作品的

7、指纹在离线情况下被计算出来,连同一些重要元数据一起存储到数据库中。需要识别一段未知音乐时,先按指纹提取算法.236.一计算其音乐特征,然后在存储于数据库的大量音乐指纹中进行搜索比对。有效指纹提取算法能使被提取出的、经过各种信号处理的未知音乐指纹与数据库中原始版本的音乐指纹一致。被提取的音乐指纹通常需要满足以下条件¨J:(1鲁棒性。未知音乐能对各种攻击保持稳定,在经受较严霞的音频信号处理后,仍然能在数据库中识别出其原始版本。(2区分性。不同歌曲之间的指纹应具有较大差异,而同一音乐不同版本间的指纹差异应很小。(3紧致性。用较短的指纹可以有效表示歌曲特征。(4简易性。算法简单易行,运算时无

8、须占用较多资源,且运行快速。多数指纹提取算法基于以下方法:将音乐信号分成互相重叠的帧,对每个帧计算一系列特征,此类特征需要对各种音频信号处理在一定程度E保持不变。已有特征主要包括傅立叶变换FFrIj J、小波变换wTHl、迈尔倒谱系数Mel Frequency CepstralCoefficients(MFCCpl、频谱平滑度Spectral Flatness【oj、尖锐度Sharpnessl01、线性预测编码Linear Predictive Coding(LPC161以及它们的导出量(如均值和方差。通常使用分类器技术(如隐含马尔可夫模型Hidden Markov Models(HMMH1或

9、量化技术将卜述特征映射为一个更简洁的表示。每帧算出的指纹称为子指纹(subfingerprint,一个子指纹通常无法包含足够信息来进行音乐识别。足以识别完整音乐基金项目:国家自然科学基金资助项N(61M02008作者筲介:陈芳(1972-,女,讲师、硕士研究生,主研方向音频识别与认证;李伟、李晓强,副教授、博士收藕日期:2008一l!-04Email:blueelain的未知音乐单元称为指纹块(fingerprint block,即指纹粒度。小波包变换(Wavelet Packet Transform,WPT是一种有效的信号时频分析工具,能有效刻画信号特性并反映其变化细节。本文提出一种基于小波

10、包变换并采用最佳子树分解选择最优基的音乐指纹提取算法,通过计算被优选的小波包系数能量与平均值之间的比值提取音乐指纹。将本文算法与现有数据库搜索算法相结合,可以构成有效的音乐指纹系统。2小波包变换与最优小波包基的选择特征提取是音乐指纹生成的关键步骤。在实际信号,尤其是非平稳信号的处理中,信号任意时刻的频域特征很霞要,因此,需要使用能将时域、频域信息结合起来,用于描述信号的时频分析方法。使用较多的一种时频分析方法是小波变换,它在时间域和频率(尺度域都具有表征信号局部特征的能力。在正交小波分解过程中,低频(近似系数被进一步分解成低频和高频(细节系数,而高频系数不再被分解。小波包变换是小波变换的莺要扩

11、展,它提供了更丰富且精确的信号分析方法。图2(a显示了尺度为3的小波包变换,信号的低频部分和高频部分被同时分解,保留了信号的完整能量信息,因此,可以更精确地反映局部情况。根据小波包的组织方式,对于给定的正交小波,一个长度为N=2L的信号的分解方式最多可以有2种,即一个深度为L的完整二叉树的子树数目,该值极大。在完整的二叉树结构中,并非所有二叉树都有价值,即不是每个节点都需要进一步分解为2个部分,因此,产生了如何实现小波包最佳分解的问题。需要根据一个简单可行的原则寻找一种最佳树结构(或最优小波包基(图2(b,如最小熵标准。(a小波包分解(b最优子树圈2小麓包分解与量倪子村遗择基于最小熵的最优小渡

12、包基生成步骤如下:(1计算每个节点的熵值e。(2沿叶子节点向根节点,对非叶子节点,如果ele2(el是节点N的熵值,2是节点子节点的熵值总和,则节点将被保留为最优树的一个节点,其下的子节点被去除。否则,节点Jv的熵值被P2替代,子节点保留。(3按从左到右、从下往上的顺序依次进行最优基的选择,直到根节点为止,最终得到整棵最优树,即最优基的集合。上述算法使整个小波包以及每个节点的分解都得到了优化。最优基的选取使信号分解后,小波包系数彼此间有较大差别、主次明显,易于舍去非关键数据并保留关键数据。其实质是在信息损失较少的前提下,使信号中隐含的信息能集中反映在少数几个分解系数上,以实现信号的分解和重建,

13、为信号处理中系数的取舍和减少数据量等提供前提条件。3指纹提取算法音乐指纹提取算法如图3所示,主要步骤如下:(1预处理。输入音乐被转换为16hit/sample,采样率为44。l kHz的单声道信号。(2分帧。音乐信号被分解为互相1li叠l,2的帧,每帧使用Hamming窗以平滑帧边缘。实验中帧长取为2048,约0.05S。(3小波包分解和最优基选取。采用“dbl”小波对每帧音乐信号进行3层小波包分解,并使用基于最小Shannon 熵的最优小波包基生成算法求出最佳子树。(4统计量计算。根据最佳子树每个叶子节点对应的系数,计算如下3个能量统计值:互=窆i工(甩l。,ESUMt=芝置,EAVG=二窆

14、ESUMr,其中,Hn是第k帧节点i的第n个系数;Ei表示第k帧第i个叶子节点的能鼍值;ESUMk表示第k帧信号能量值;EAVG 表示音乐信号所有帧的平均能量。(5Hash值生成和音乐指纹生成。将上述所有帧的ESUM分别与EAVG比较,每帧产生1位Hash比特值,Hk=:老翻w。将所有Hash 位连接起来即构成该音乐的指纹。圈3音曩指纹提取瘫程4实验结果本文使用误码率(Bit Error Rate,BER作为未知音乐指纹和原始音乐指纹问的相似性度量标准。实验主要验证使用本算法生成的音乐指纹对常见音频信号处理是否具有鲁棒性,以及不同歌曲指纹之间的可区别性。4.1鲁棒性实验随机选取classica

15、l,folk,R&B和POP风格的5段音乐,从中分鄹随机选取约lO.5s的音乐片段(16bit/sample、采样率为44.1kHz的单声道信号进行实验。每个音乐片段的指纹都将经过一些常见音乐信号处理,并分别与原始指纹进行比较,输出误码率作为音乐指纹鲁棒性的判断依据。鲁棒性测试结果如表1所示。袭1鲁棒佳舅试结果(下转第240页一237algorithm.FS,UMHexagonS(hybridUnsymmetrical-cross Multi Hexagongrid search一1算法和EPZS(Enhanced PredictiveZonalSearchp1算法进行比较。UMHex

16、agonS和EPZS已被商用,且它们的算法效率在H.264中较好,具有较高对比意义。主要比较了信噪比Ps懈、比特率和搜索时间。测试结果如表l一表3所示。由表l可以看出,新算法的峰值信噪比在一些测试序列上有所下降,但下降幅度很小,保持了图像质量,且对部分测试序列有所提高,能更好地重构图像。由表2可以看出,新算法的比特率比其他3种算法有所增加,但幅度在0.5%左右,且对部分序列有所降低,幅度在0.4%左右。由表3可以看出,本算法的搜索时间与FS,UMHexagonS,EPZS相比,分别节约了80%,28%,30%。综上所述,在保持再构图像质量和比特率基本不增加的前提下,本算法的搜索速度得到很大提高

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数据显示,对于上述常见音频信号处理,虽然

19、各个不同种类音乐的抵抗力有所差别,但所有误码率均低于0.13。尤其是对于一些常用编码,如MP3,WMA和RM,在高压缩率下仍能保持低于0.08的误码率,达到了很高的鲁棒性。4,2区别性实验若不同音乐片段具有相似指纹,则会在进行指纹检索时引起误判,本实验测试不同歌曲间的指纹是否具有足够大的距离,结果如图4所示。DestinYs Celilie 访鬈小提琴曲排莆Madonna child Dion 小提琴曲n00000400004II 1049330,5200捧箫0400000000446705333047J I DestinYlchild04ll 044670(N×0047784689

20、Madonna 04933O5333047780000O 05378Celille Dloll05200047l104689053780000圈4不同歌目的指坟臣膏图4数据显示,同类或不同类歌曲之间指纹比对的误码率介于0.4和0.5378之间,多数在0.5左右,即指纹间具有较大差别,不容易引起误判。可见,本文算法在不同歌曲间具有较强可区分性。5结束语本文算法提取的指纹对常见音频信号处理具有很高鲁棒性,可以有效应用于音乐识别系统。此算法有待改进,主要是对时间域信号处理的抵抗,如音乐片段的任意剪切和复制、局部时间伸缩等。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结束语本文算法能保证图像质量和比特率基本不变,并极大提高运动估计速度。下一步的研究方向

22、是使该算法能准确确定大运动序列中的运动矢量。参考文献【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