评论摘要(共 0 条，得分 0 分，平均 0 分)
音乐旋律特征提取不是最终目的，在对哼唱片段进行音乐旋律特征提取之后，下一步的工作就是将这些特征与音乐数据库中的所有数据进行比较，寻找出最为匹配的若干首歌曲. 提取音乐旋律特征后，二进制的音乐数据已经转换为字符序列，从而搜索过程也将在字符串空间进行。字符串的搜索、匹配、相似度比较和计算在诸多领域有着广泛应用，已经有大量的技术积累，因而，通过对现有算法的了解，将有力的支持音乐检索匹配算法的研究工作。
1. 常用的匹配算法
BF(Brute Force)算法又称蛮力匹配算法[1]。KMP(Knuth-Morris-Pratt)算法[2] 动态时间归整(DTW)算法[3], 在语音识别或哼唱识别中，由于测试语料在说话或歌唱速度上与标准模板的不一致，就导致了匹配过程中在时间轴上的非线性偏差，这就为匹配过程带来了困难。动态规划算法是解决这一问题最经典的算法之一。
语音信号一般可以表示为特征向量的序列，如(1.1)式所示：
( 1.1)
一般来说 。DTW算法的目的就是要计算出一条最佳路径，经由这条最佳路径后 和 之间的距离为最短，这个最短的距离被称为DTW距离，表示 和 的相似程度。要计算 和 的DTW距离一般要建立一个 的表格 ，表格中的点表示路径通过的点。假设表格中任意一点可表示为 ，那么到达它的路径只有三种情况，如图 1 所示：
D(i-1,j) D(i-1,j-1)
D(i-1,j-1) D(i,j-1)
图1 DTW的最佳路径
表示i=1开始到（i,j）为止的最小距离，那么就可以推导出计算DTW距离需要的循环关系式，如(1.2)式所示：
(1.2)
其中 =1为权重，dist(ai,bj)是路径的匹配代价。
当 和 为一维向量时， 。则 和 的DTW距离为：
（1.3）
DTW(A,B) = DTW(A,B)/N （1.4）
其中 N= ，k的值就是匹配路径的匹配点数，计算DTW距离需要搜索的路径便如图 2 所示。从图中可知，当 和 的值增大时，计算量的增加是很明显的。
图2 所以需要搜索的路径 图 3 DTW最佳路径
通过上式的计算可以得到A，B两个特征向量的最小距离，其最佳匹配路径如图3所示：
2.系统算法改进和系统构建
利用Dynamic Time Warping (DTW)的方法来做旋律的识别，对于哼唱的背景噪声和哼唱者的节奏的不准确而造成多唱一个音或者少唱一个音的情况，都可以做到有效的比对。但是在记忆体和比对时间上的花费还是很大，而时间的多少也
是衡量一个系统优良的一个重要指标。因此在加快辨识速度方面的研究是很有必要的。本文从两个方面进行了大量的测试研究，提出两种可行的加快辨识速度方法.
2.1 哼唱识别的前处理--旋律相似因子的搜索算法
通过观察歌曲的资料库，我们发现歌曲虽然都是起伏不定，但是通过和测试的歌曲做比较可以看出它们在一段音符中的趋势存在相似性。如果测试的歌曲是一个上升的趋势，那么搜索的时候就只要和上升趋势的资料库歌曲做比对，这样就相应的减少了将进行比对的歌曲数，达到加速辨识的效果。
图 4 歌曲旋律特征（爱我中华为例）
为此，本文提出一种旋律相似因子的搜索算法：因为每个人的哼唱基准音高都不同，所以本文将相邻音符之间的音高差作为因子的基本单元，每三个音高差值作为一个相似因子。如上图歌曲，当后一个音符比前一个音符的音高高时我们标记为U，反之为D。图歌曲标记为（UDUUDUDUU DDU DUU DDU DUD UUD..）。其中划线的三个音高差组成一个相似因子。
旋律相似因子算法的主要思想是：在任何相似因子可能出现的地方，检测其前后一定范围内的的相似因子和当前相似因子的位置关系，如果它们满足时序性限定条件，我们就认为它们存在旋律相似性返回一个确认值，在一定范围内的返回值越大，则相似度越高，从而找到需要比对的旋律段。如下图：
图5相似因子搜索算法
从图中可以看出，当查询歌曲的A，B因子，通过因子序列的比较，它们的位置关系越保持一致，相似度就越高，从而去掉一些相似度低的歌曲。通过实验利用相似因子搜索算法可以减少5%～20%的搜索数量。
表1 相似因子效果表
测试歌曲 要匹配的歌曲数 实际匹配的歌曲数 减少率
阿里山的姑娘 206 192 7%
爱的奉献 206 168 18%
爱我中华 206 190 8%
把根留住 206 168 18%
长城长 206 170 17%
茉莉花 206 190 8%
党啊，亲爱的妈妈 206 190 8%
嘀哩嘀哩 206 170 17%
读书郎 206 165 18%
花心 206 170 17%
2.2 Dynamic Time Warping (DTW)的加速
在哼唱识别的前处理中，资料库的比对数量减少了5%～20%。剩下的再做完全的比对工作。通过对音乐的音高值提取了解到，音高序列的大小可以通过窗函数的大小，窗移动的大小来改变。本文哼唱歌曲长度为8秒，采样率为8000Hz，采样点为8bit。窗函数大小为420 ，1/38秒取一个音高点，每首歌有304个音高点。本文将通过不同的音高截取比率，将比对的歌曲音高点数按截取比率减小，再做比对。音高点数的减少，比对时间也就相应的减少。比如说：音高比率如果是1/2.则本文的歌曲的音高点数变为，304/2=152点。做法则是：对音高向量做处理，每两个点只取一点，另一点就忽略，对哼唱歌曲音高向量做预处理。同时做预处理是把标准资料库里的歌曲音高向量做相应的减少音高点数的处理，保存在资料库中。然后和标准库的歌曲音高向量做DTW的比对运算。下图是1/4的音高截取比率的音高向量示意图。
图6 截取比率为1/4的音高示意图（小背篓为例）
音高点数的减少，相应的比对时间也会减小。这时我们就会问多大的截取比率才是最好的，是不是为了减少比对时间越小越好。这些都需要在实验中总结，通过比较截取前和截取后的同一首歌、同一人哼唱的识别率。由于本文歌曲音高向量提取时特征点比较多，在截取率为1/2时，在识别率和减少比对时间上都取的比较好的效果。
表2 不同截取率下的耗时 表3 不同截取率下的误判率
截取率 0 1/2 1/3 1/4
50首总时间(s) 180 90 65 40
截取率 1/2 1/3 1/4
Top3 50首误判率（%） 2% 3.5% 6%
基于上述哼唱检索方法，开发了“哼哼 ”哼唱检索系统，系统的计算主要包含两大部分，一是特征提取[4]，二是搜索匹配。
3. 系统性能评价
3.1系统实验精度测试
歌曲来源于精心挑选的国内传唱最广的、最具地方味的500首民族歌曲。取用了100首歌，每首歌50个不同的人哼唱，共5000个歌曲片段做测试
表 4哼唱检索的总结果
检索结果位置 检索精度
前 3 位 84%
前 5 位 90%
前10 位 94%
3.2系统实验性能测试如表 5
表5系统搜索时间
时间统计方式 花费时间（单位秒）
系统搜索总时间 1.58
基频提取均耗时 0.38
系统识别均耗时 1.20
4. 系统特点总结
1）本系统在研制过程中充分考虑到音乐数据自身的音乐特性(即不把它仅仅作为一种二进制的普通数据)，通过对歌曲旋律的检索来实现音乐检索。
2）无需事先训练。在涉及语音技术的研究或系统实现中，经常会用到训练策略来加强系统的适应能力。但本系统在使用中无需事先进行训练，只要用户能够哼唱准确，往往能取得良好搜索精度。
3）有较好的搜索精度和搜索速度。但系统目前仍然是实验系统，在搜索技术和效率改进上还有很多可以完善的地方。
参考文献
[1]钱屹，侯义斌.一种快速的字符串匹配算法，小型微型计算机系统.2004.4. 2004.4:410-413.
[2] 李雪莹，刘宝旭，许榕生.字符串匹配技术研究，计算机工程，2004.11. 2004.11:24-26.
[3]王玮，蔡莲红.基于内容的音乐检索研究.[EB/OL]
http://hcsi.cs.tsinghua.edu.cn/Paper02/200220.pdf.
[4]李扬,吴亚栋,刘宝龙.一种新的近似旋律匹配方法及其在哼唱检索系统中的应用.计算机研究与发展,2003，40(11):1554-1560.
