哼唱检索中基于分段信息的

匹配算法研究SegmentationbasedMelodyMatchinQuery-by-Humming(申请清华大学工学硕士学位论文)培养单位:计算机科学与技术系学科:计算机科学与技术研究生:曹文晓指导教师:郑方研究员二一年六月关于学位论文使用授权的说明本人完全了解清华大学有关保留、使用学位论文的规定,即:清华大学拥有在著作权法规定范围内学位论文的使用权,其中包括:(1)已获学位的研究生必须按学校规定提交学位论文,学校可以采用影印、缩印或其他复制手段保存研究生上交的学位论文;(2)为教学和科研目的,学校可以将公开的学位论文作为资料在图书馆、资料室等场所供校内师生阅读,或在校园网上供校内师生浏览部分内容.
本人保证遵守上述规定.
(保密的论文在解密后遵守此规定)作者签名:导师签名:日期:日期:摘要I摘要哼唱检索是基于音乐内容的检索,比传统的基于描述信息的音乐检索更人性化.
在哼唱检索系统中,用户通过麦克风等音频输入设备哼唱几句歌词,接着系统通过提取一定的特征,将哼唱语音特征与预先建立的旋律特征数据库中的特征进行比对并排名,给出检索结果.
目前哼唱检索的旋律匹配算法主要有字符串匹配、编辑距离、HMM、线性伸缩、动态规划、指纹匹配等,其中基于线性伸缩的方法效果较好.
对于基于线性伸缩的方法,线性伸缩参数包括拉伸系数和音高偏移的估计依然是难点,另外当旋律较长时由于不同局部的线性伸缩参数不同,线性伸缩方法应用统一的线性伸缩参数效果较差.
本文提出基于极值点分段信息和基于停顿点分段信息来解决上述问题.
极值点分段信息是指由旋律中最高点对旋律进行划分构成的分段结构,通过极值点分段信息增加启发式估计线性伸缩参数时的候选起点来提高对拉伸系数和音高偏移估计的准确性.
停顿点分段信息是指通过哼唱过程中的停顿位置对旋律构建的分段信息,通过停顿点分段信息对旋律采用动态规划或递归匹配的方法进行分段地线性伸缩匹配,可以达到更好的匹配效果.
本文通过多项实验验证了所提出的两种分段信息的有效性.
本文使用355大小的哼唱数据库和5223大小的MIDI旋律数据库进行实验来评估新算法的改进.
实验结果表明,在最好的情况下,基于停顿点分段信息的分段匹配算法比传统的LS、DP、RA算法Top-1分别提高17%、14.
7%和4.
8%,相应的MRR分别提高15.
3%、12.
9%和4.
8%.
另外,使用RALS作为精确匹配算法时新的启发式估计算法使系统的Top-1和MRR准确率分别提高了1.
8%和3.
3%.
实验结果验证了极值点分段信息和停顿点分段信息的有效性,同时也说明了基于停顿点分段信息的分段匹配算法是比传统线性伸缩算法更有效的算法.

关键词:哼唱检索线性伸缩动态规划递归匹配AbstractIIAbstractQuery-by-Humming(QBH)isacontentbasedretrievalmethod,whichismorepersonalizeddesignedthantheconventionalonebasedonmetadata.
InQBHsystem,auserhumsseveralphrasesrecordedbyaudiorecordingdevice.
Thesystemthenextractsmelodyfeaturesfromthehummingspeech,comparesthemwiththefeaturesfromapre-builtmelodydatabase,andfinallygivesTop-Nresults.
Currently,therearemanyalgorithmsformelodymatching,suchasFastStringMatch,EditDistance,HMM,LinearScaling,DynamicTimeWarping,Fingerprintandsoon.
Mostoftheresearchworkconductsbasedonthelinerscalingmethod.
Butitstillremainstwodifficultproblemstomanyresearchers,oneistheestimationofparametersoftemporatioandkeytransposition,theotheristhematchingresultgetsworseundertheidenticalparameterswhenthehummingquerylastslonger.
Inordertosolvethesetwoproblems,weproposedatwosegmentationinformationmethodwhichusedtheinformationfromtheextremepointandsingingpausingpoint.
Theinformationisdefinedassegmentationinformation,whichdescribesthephrasessegmentedbyextremepointsorsingingpausingpoints.
Extremepointaddsnewintialparameterstoheuristicparameterestimationsothatthesystemcanachievemoreaccurateestimation.
Singingpausingpointisusefulforphrase-levelmelodymatchingwithDynamicProgrammingorrecursivealignmentformoreefficientscoring.
Inthisthesis,wedidmanyexperimentstoprovetheefficiencyoftheproposedsegmentationinformation.
Weusedaquerydatabasewith355hummingqueriesandaMIDIdatabasewith5223MIDIstoevaluatetheimprovementofthenewheuristicparameterestimationandphrase-levelmelodymatchingalgorithmsusingtheproposedsegmentationinformation.
Itisshownthatthenewphrase-levelmelodymatchingalgorithmhas17%,14.
7%and4.
8%improvementinTop-1accuracyrelativetoLS,DPandRAmethodsatmost.
ThecorrespondingimprovementsinMRRare15.
3%,12.
9%andAbstractIII4.
8%,respectively.
Atthesametime,thenewheuristicparameterestimationimprovedtheTop-1andMRRperformanceby1.
8%and3.
3%.
ThusthesegmentaioninformationbasedonextremepointandsingingpausingpointisefficientformeldoymatchinginQBH,andphrase-levelmelodymatchingalgorithmsaremoreefficientalgorithms.
Keywords:Query-by-HummingLinearScalingDynamicProgrammingRecursiveAlignment目录IV目录第1章引言11.
1研究背景与研究意义.
11.
2旋律匹配算法的研究现状.
31.
3本文的研究内容及主要贡献.
8第2章哼唱检索的基本原理102.
1本章引论.
102.
2MIDI文件格式与旋律表示102.
3音符与基频之间的关系.
132.
4哼唱语音旋律特征的提取.
162.
4.
1音高的提取.
162.
4.
2音符的提取.
192.
5哼唱旋律与MIDI旋律的匹配.
232.
5.
1匹配的定义.
232.
5.
2匹配的特征.
232.
5.
3匹配的难点.
232.
5.
4匹配的分类.
252.
6哼唱旋律与MIDI旋律的匹配算法.
252.
6.
1基于字符串匹配的方法.
252.
6.
2线性伸缩.
262.
6.
3动态规划.
272.
6.
4基于递归的线性伸缩方法.
282.
7本章小结.
30第3章分段信息313.
1本章引论.
313.
2基于极值点的分段信息.
323.
2.
1极值点的定义.
323.
2.
2极值点的估计.
34目录V3.
3基于停顿点的分段信息.
353.
3.
1停顿点的定义.
353.
3.
2停顿点的物理意义.
373.
3.
3停顿点的估计.
393.
3.
4估计参数的确定.
413.
4实验.
423.
5本章小结.
44第4章基于分段信息的匹配算法454.
1本章引论.
454.
2基于极值点分段信息的线性伸缩参数估计.
454.
3基于停顿点分段信息的动态规划.
494.
4基于停顿点分段信息的递归匹配.
514.
5系统结构与实验数据.
534.
6实验验证及结果分析.
564.
6.
1评价准则及各算法描述.
564.
6.
2基于停顿点分段信息的精确匹配.
574.
6.
3候选分段点数对动态规划分段匹配的影响.
594.
6.
4递归分段匹配准确率与递归层次的关系.
604.
6.
5基于极值点的启发式线性伸缩参数估计算法.
614.
6.
6实验小结.
624.
7本章小结.
62第5章结论与展望63参考文献66致谢与声明70个人简历、在学期间发表的学术论文与研究成果.
71第1章引言1第1章引言1.
1研究背景与研究意义音乐检索作为与越来越庞大的音乐数据库的交互接口,在多媒体信息检索中起着至关重要的作用.
传统音乐检索利用歌曲描叙信息(metadata)如歌名等,对描述信息进行索引并建立数据库,当用户通过文本查询时,按照文本检索的方式检索数据库中与查询文本相关度最大的数据返回给用户.
图1.
1哼唱检索系统的一般结构哼唱检索是基于内容的音乐检索方式,如图1.
1为一般的哼唱检索系统的系统结构,检索系统主要包括三部分:(1)旋律特征数据库旋律特征数据库是哼唱检索系统的模板库,系统对原始的音乐数据进行特征提取,然后将特征索引并储存到特征数据库中.
一般的哼唱检索系统使用MIDI数据库作为旋律特征数据库.
(2)用户输入与特征提取这是系统与用户交互的接口,当用户检索音乐时,通过麦克风等录音设备哼唱几句歌词,一般为几秒到几十秒不等.
哼唱形式可以是带歌词哼唱或以哒哒哒、吹口哨等方式哼唱.
录音完毕后,系统对哼唱语音进行旋律特征提第1章引言2取,并输入到匹配模块中.
(3)旋律匹配与候选输出提取用户哼唱语音的旋律特征后,系统将该特征与数据库中的旋律特征进行比对,最后给出与用户查询相关度最大的前N条记录.
哼唱检索系统相比传统的音乐检索系统的优势有:一,更加精准;传统的音乐检索引擎通过歌曲的歌名,歌手,歌词等信息作为关键词来检索,随着流行音乐歌曲数量的快速增长,经常会有同歌名的歌曲出现,同一个歌手的歌曲数目也较多,尽管可以按专辑划分,要记住每一专辑中的歌名并非易事.

要精确地记住歌词也比较困难,同时不同歌曲的歌词也可能出现重复,通过歌词检索时若输入歌词太少则很难精确地找到目标歌曲.
因此通过传统的音乐检索引擎检索歌曲具有一定复杂度,同时必须结合一定的检索技巧.
而哼唱检索则不同,一首歌的旋律一般比较独特,尤其歌曲中高潮或旋律优美的部分更易于记忆.
由于旋律的"唯一性",当用户将对应旋律以哼唱或唱的方式输入到哼唱检索系统时,系统便可以通过一定的匹配算法,找出对应的歌曲.
因此,在哼唱检索系统的算法足够好的条件下,哼唱检索方式比传统检索方式更加精准.
二,更加人性化;通过哼唱检索的方式,用户仅需要麦克风或者其他录音设备,通过语音输入方式,来进行检索.
而传统检索方式需要通过键盘等文字设备输入文字进行检索.
就普通用户而言,文字输入的方式比语音输入的方式复杂,并且输入速度慢,因为文字输入受用户使用的输入法、盲打等计算机水平的影响,而语音输入与平常说话类似.
因此哼唱检索的方式比传统的音乐检索方式更加人性化,更易于使用.
从提出哼唱检索概念开始,哼唱检索就一直是国内外研究的重点课题.
最早的哼唱检索研究由Ghias在1995年发表的一篇论文[1]开始,文中使用了较简单的方法,将旋律的升高降低和保持不变转化成字符串并进行字符串匹配.

由于这种旋律表示方法过于粗糙,需要的哼唱语音比较长,在Ghias的论文中使用的数据库为183首.
McNab则实现了第一个可以通过互联网进行哼唱检索的系统[2],尽管使用了字符串匹配方法,在特征和数据库上却有进一步的研究.
台湾清华大学的张智星也在哼唱检索方面做了很多研究工作[3-5],通过研究线性伸缩及动态规划等方法,开发出了多个哼唱检索系统.
上海交通大学的李扬等通过使用近似旋律匹配即线性对齐方法进行哼唱检索,并构造了哼第1章引言3唱检索系统的原型,其中数据库中使用了3864首歌曲[6].
Shifrin[7,8]以及国内深圳大学的陈知困[9]等研究了使用HMM方法进行哼唱检索匹配.
还有加利福尼亚大学的Unal尝试使用类似指纹的方法进行哼唱检索[10].
总体而言,目前的研究方法主要包括字符串匹配、编辑距离、动态规划、HMM、线性伸缩、指纹等方法.
由于算法以及数据等方面的原因,哼唱检索目前还难以达到实际应用的要求.
尽管哼唱检索系统比传统音乐检索方式在本质上有很大优势,要取代传统音乐检索方式尚为时过早.
在哼唱检索的实验环境下,使用较小的数据库(这里指几百到几万不等)可以得到较好的准确率,但实际应用时会遇到一定的困难.
一者,数据库的收集难度较大.
目前多数算法的研究是基于MIDI音乐格式,而对于MIDI音乐格式如果要建立全面的数据库需要通过手工录入的方式,增加了数据库的工作量,同时数据库的更新维护也过于繁琐.
二者,匹配算法的准确率难以达到实际应用要求.
实际应用环境条件下,受各种因素如噪声、哼唱质量差等因素影响,匹配算法的准确率会大大下降.
目前哼唱检索还有较大的研究空间,如何进行更有效的旋律匹配依然是研究中的难点.
本文的研究工作旨在以目前已有的匹配算法为基础,通过研究旋律中的分段信息并用于匹配,达到提高匹配效果的目的,为今后的哼唱检索研究提供有效的参考.
1.
2旋律匹配算法的研究现状哼唱检索中的关键算法是计算哼唱旋律与数据库中旋律间的相似度,大多数对哼唱检索匹配的研究是基于哼唱旋律与MIDI旋律进行的.
由于哼唱旋律和MIDI旋律间存在固有的差异,如MIDI中的三个音符可能在歌曲中对应2个歌词,因此哼唱语音经过提取后也是2个音符,这种特殊的性质要求哼唱检索的匹配算法对错误的容忍度较高.
国外主要的旋律匹配方法有字符串匹配、编辑距离、动态规划、线性伸缩、HMM、指纹等,大部分的研究工作基于某一种方法或多种方法结合的思路进行.
字符串匹配的方法是最早用于哼唱检索的方法,其主要思想是将旋律表示为字符串,然后通过字符串检索、快速匹配等方法进行匹配.
快速字符串匹第1章引言4配已经有许多成熟的方法,但应用于哼唱检索时须考虑一定的错误容忍,即在匹配结果中能容忍一定数量的错误匹配.
目前已有不少对可容忍k次错误的字符串匹配方法的研究[11-14].
对于可容忍k错误的快速字符串匹配算法,基于Boyer-Moore的字符串匹配算法被认为是实际应用中最好的算法,同时该方法的代码相比暴力搜索而言更简单[14].
文献[1]使用Baesa-Yates和Perleberg提出的可容忍k次错误的字符串匹配算法[12]进行哼唱检索,在含183首歌曲的MIDI数据库上用10~12个音符构成的字符串序列进行检索,能够达到90%的准确率.
使用字符串检索的方法对特征提取的要求比较高,文献中该方法特征提取占用的时间较大.
McNab[15]在哼唱检索中使用音高、节奏、旋律的上升下降曲线等特征来进行检索,并且只从歌曲的起始点使用字符串匹配进行检索,同时研究了从数据库中检索到正确歌曲所需要的特征数量如音符个数,是否使用节奏信息等,还研究了所需要的音符个数随数据库大小变化的关系.
通过字符串快速匹配的方法进行哼唱检索,优点是较直观,匹配速度较快,缺点是特征提取的难度及要求比较高.
由于字符难以表示旋律变化的丰富性,假如以字符表示绝对音高,则哼唱旋律与数据库旋律间存在整体的音高偏移,因而表示的字符串不一致的概率大大增加.
而对于以字符表示音高变化,若单纯表示音高的升降或保持不变,则过于简略,很难将目标旋律与其他旋律区分开,导致返回数据集过大.
而若以字符表示音高变化的不同程度,则存在程度分界的问题,两个不同的音高变化值极相近,但可能被归类成不同音符,导致错误.
编辑距离又称Levenshtein距离,用于计算一个字符串转化为另一个字符串所需要的最少编辑操作次数,一般使用动态规划方法计算.
Prechel[16]使用类似快速字符串匹配的方法,将旋律根据音高的升降和保持不变转化为U/D/S表示的字符串,然后通过从数据库中检索与哼唱旋律的特征字符串间编辑距离最小的歌曲作为匹配结果.
通过在Parsons[17]数据库的10370首古典音乐数据库上使用106个录音片段进行哼唱检索,得到Top-1正确率为44%,Top-40正确率为77%,并指出大部分的错误是由于呼吸导致,如果能在录制哼唱语音时不呼吸,则上述对应的准确率可提高到59%、86%.
编辑距离的方法与字符串匹配类似,相比可容忍k错误的字符串匹配,编辑距离可以容忍插入、删除及替换三种错误类型,比可容忍k错误的字符串匹配更鲁棒.
缺点也与字符串匹配类似,对旋律的表示过于简化,同时基于动态规划来计算编辑距第1章引言5离的耗时也比快速字符串匹配大.
动态规划是计算机科学中常用的用于求解可分解为子问题的最优化方法,它将求解当前问题最优解的问题,转化为求解子问题的最优解问题.
因此不少哼唱检索匹配算法的研究都基于动态规划的方法[3,18-20].
Jyh-ShingRogerJang使用多次的动态规划并同时估计音高偏移以达到最好的匹配效果,在估计音高偏移时使用启发式估计算法.
通过在800首歌曲的数据库上使用200个哼唱片段进行测试,每两段旋律间的匹配调用5次动态规划,在限制哼唱旋律均从歌曲的起始部分开始哼唱并哼唱5至8秒的条件下,得到Top-1的准确率为76%,Top-20为86.
5%,说明这种基于动态规划的方法能够满足一般哼唱水平的人的使用要求.
动态规划方法的优点是对匹配旋律的要求不严格,抗噪性强,可以通过搜索不同路径达到最优匹配结果,缺点是匹配时间长,计算量大,数据库增大时系统时间响应的变化尤为明显.
考虑到哼唱旋律与标准MIDI旋律间存在的线性关系,线性伸缩的方法被引入到哼唱检索的旋律匹配算法中,线性伸缩方法通过将其中一旋律的曲线进行横向的拉伸和纵向平移来与另一旋律曲线对齐,最终调整到最好的对齐效果计算分数.
Jyh-ShingRogerJang提出使用线性伸缩匹配的方法作为距离函数并利用树结构搜索哼唱旋律的最近邻作为检索结果[4],通过使用普通哼唱水平的人的1000个哼唱语音在包含3000首歌曲的数据库上进行测试,Top-20的准确率达到73%,对应的系统响应时间为2秒.
同时认为,旋律可能存在非线性的速度变化,这时使用动态规划能够达到更好的匹配效果,但动态规划的时间消耗较大,因此必须在系统准确率和时间响应上作适当的平衡.
线性伸缩方法的优点是计算简单且直观,缺点是匹配起点的确定困难,一般假设哼唱旋律从句子的起始点或歌曲的起始点开始来降低搜索的空间.
另一问题是线性伸缩的参数包括拉伸系数(Tempovariation)和音高偏移(Keytransposition)的估计问题,由于没有直观的办法获取这两个参数,一般通过多次使用不同参数计算并选最优的方法来估计.
再者,当哼唱旋律较长时,整体进行线性伸缩匹配的效果下降,因为哼唱旋律的局部可能存在不同的线性伸缩参数.
HMM作为语音识别中的重要工具,同样也被用于哼唱检索的研究.
HMM全称是隐马尔科夫模型,用于描述隐含了未知参数的马尔科夫过程.
使用HMM进行哼唱检索时,数据库中的旋律表示为HMM的模型,而查询旋律则第1章引言6作为观察序列,当进行哼唱检索时根据每一数据库旋律输出该哼唱旋律的后验概率进行排序.
Shifrin[8]将哼唱旋律表示成音符序列,定义HMM中的每一个状态具有2个属性,一是音高变化,即音符相对上一音符的音高差,二是时间变化,即音符的持续时间.
状态间的转移概率则使用MIDI数据库训练得到.
在哼唱检索时利用HMM的前向算法计算匹配的似然度作为匹配概率.
通过使用24个哼唱语音在包含277首MIDI的数据库上进行检索,并和字符串匹配方法对比.
结果表明,字符串匹配方法得到的Top-1和Top-5准确率分别为16.
7%和20.
8%,而HMM方法的对应准确率分别为41.
7%和58.
3%.
该方法的局限是对于查询旋律长度大于HMM中的最长路径时会导致错误,同时查询旋律中存在个别音符丢失的情况时也易导致错误.
通过使用更大的数据库进行进一步研究[7],系统对于哼唱旋律越长的情况则检索结果越准确,同时对于不理想的哼唱旋律也能做较好的匹配.
使用HMM的方法进行匹配的优点是引入了概率的概念,可以通过对现有数据的统计达到较好的匹配效果,缺点是需要训练模型,并且识别的准确率与训练数据的关系较大.
另外还有指纹识别(FingerPrint)的方法,指纹识别最早用于人的身份辨识,由于在哼唱检索中这一方法与身份辨识中的指纹识别方法相似,因此也称为指纹识别.
文献[10]中使用HMM的方法提取旋律特征,将哼唱旋律切割成音符,并提取RPD(relativepitchdifference)和RDD(relativedurationdifference)两种特征,然后取RPD和RDD曲线中的极值点来建立指纹样本.
哼唱检索时通过计算哼唱旋律与MIDI旋律间在RPD,RDD上的平方差作为匹配分数,最终保留前5个候选.
通过使用来自80人的400个哼唱查询语音及大小为1500的MIDI数据库进行哼唱检索,结果表明在受过音乐教育的人对应的哼唱数据集上可达到88%的准确率,而对于未受过音乐教育的对应准确率为70%.
对应的使用传统的编辑距离匹配的方法得到的准确率分别为86%和62%.
说明这种指纹识别的方法对于未受过音乐教育的人的哼唱查询具有更好的鲁棒性.
指纹识别的优点是仅使用旋律中的少量但独特的信息,便于快速匹配和索引,缺点是确定有效的指纹信息并在哼唱旋律与MIDI旋律之间保持一致比较困难.
相比身份识别中的二维指纹,哼唱检索中的指纹是一维信息,因而表示的信息量也较少,要做到精确匹配,必须联合同一旋律中的多个指纹进行计算.
国内对于旋律匹配算法的研究起步相对晚一些,主要的算法分类与国外的第1章引言7算法大致相同,也包括字符串匹配、编辑距离、动态规划、线性伸缩及HMM的方法,目前对类似指纹识别的哼唱检索研究较少见.
字符串匹配仍是常用的方法[21,22],文献[21]首先提取歌谱轮廓特征,通过构造标准音调差值图将哼唱旋律表示为歌谱特征,然后通过动态规划方法计算歌谱字符串间的相似度.
通过在405首歌曲的数据库上进行检索,得到的Top-5准确率超过90%.
编辑距离的方法也被用于旋律匹配,文献[23]使用动态规划计算哼唱旋律和MIDI旋律间的编辑距离,通过在动态规划中引入模糊隶属度函数计算两音高差间的相似度,同时引入音长比信息进行相似度计算,最终以两种相似度的加权作为最终的编辑距离分数.
通过在包含2500个MIDI文件的数据库上使用90个哼唱片段进行测试,结果表明算法相比音高差5阶量化方法在Top-10的准确率上由59%提高到了75%.
动态规划的方法继续用于哼唱检索匹配.
和传统的哼唱语音检索MIDI旋律的方式不同,文献[24]考虑了哼唱语音和哼唱语音间的直接匹配,通过对哼唱语音提取MFCC1~3及过零率特征并进行适当简化,再与数据库中的哼唱语音特征使用DTW计算相似度.
数据库中的候选歌曲都标注了句子起始点,因此取哼唱旋律与数据库中对应歌曲的多个候选片段中匹配分数最好时的分数作为与该歌曲的匹配分数.
通过对6位哼唱者的70余次哼唱检索进行测试,排名在前15位的概率超过60%,说明系统是有效的.
除此之外,还有包先春提出两层的DTW算法[25],罗凯等提出在DTW中同时考虑音高差和音长差作为代价函数[26],马志欣等提出模糊集合的概念并在DTW中使用音高差和音长比加权作为代价函数的方法[23]等.
线性伸缩的方法也获得了较好的效果.
中科院声学所的吴晓等人[27]使用线性伸缩的方法,通过对哼唱旋律和数据库旋律进行递归的自顶向下的分段匹配来进行检索.
在确定要匹配的哼唱旋律片段和数据库旋律片段后,取数据库旋律的中间音符,根据预先设定多种线性伸缩系数和音高偏移系数的组合,按对应的划分比例确定哼唱旋律中的对应音符,将两段旋律划分成两组片段,并计算两组片段对应的线性伸缩匹配分数,取分数最优的一种对哼唱旋律的划分方式,如果已经达到设定的递归次数,则直接返回前述分数,否则继续对划分的两对子片段进行同样的匹配过程,直到达到预设的递归次数.
通过简化该方法的计算过程,由该方法衍生出三种快速匹配的方法,用于快速过第1章引言8滤.
通过在包含1180首歌曲的MIDI数据库上,使用875个哼唱查询语音进行测试,实验结果表明该方法比LS、DTW方法具有更好的性能.
同时指出当查询旋律的长度在7~15秒时具有较好的匹配准确率,大于13秒时结果变差,可能由于该递归方法在查询旋律过长时不再有效.
另外也有李扬等人[6]同时考虑音高和节奏来进行线性伸缩匹配,也获得了较好的效果.
国内也有对HMM匹配方法的改进工作[9,28].
中国人民大学的袁斌等人[28]通过对哼唱语音的音高差和音长比进行统计分析,并合成产生新的旋律和节奏训练数据库,同时对HMM的特征和训练方法都提出了改进.
通过在包含1500个音乐片段的数据库上使用27个检索片段进行检索,前5位命中率达到85.
5%,得到了满意的效果.
还有中国人民大学的刘怡等人[29]研究了大型音乐哼唱系统中不同近似匹配算法的算法性能,并比较了后缀树、HMM、编辑距离、DTW及单侧连续匹配(OSCM)的匹配方法.
单侧连续匹配的方法采用N-GRAM的顺序哈希索引来加快查询处理速度.
通过在包含72000首音乐片段的数据库上构造1500个不同类型错误的查询来比较其中3类方法,结果表明单侧连续匹配的方法查询速度快,在用户哼唱旋律只包含与旋律轮廓方向相同的错误时查询准确率能达到100%,而哼唱包含两个以内与旋律轮廓方向相反的错误时,前10位的命中率在90%左右,说明单侧连续匹配的方法是适用于大型哼唱检索系统的有效算法.
目前国内的研究起步晚,还有很大的研究空间.
由于目前免费开放的中文相关的数据库资源较少,给不同研究工作间的比较带来一定困难.
1.
3本文的研究内容及主要贡献旋律匹配算法一直是领域内的研究重点,在旋律匹配中利用的是音高特征(pitch),通过对音高特征序列中的音高使用特定算法进行分割可以得到音符序列,从而将旋律匹配的问题,归结为哼唱旋律的音高序列和音符序列与MIDI旋律的音符序列间的匹配分数问题.
线性伸缩方法作为一种效果比较好且计算简单的方法,面临的主要难点是线性伸缩参数的估计和局部参数精确化的问题.
首先,进行线性伸缩需要确定两个必要参数,一是拉伸系数,即两旋律间的拉伸比例,二是音高偏移,第1章引言9指对其中一旋律与另一旋律对齐最好时纵向平移的尺度.
尽管估计这两个参数时可使用枚举的方法(如[27]中方法),但会导致大量计算,因此从速度角度考虑,枚举方法并不可取.
另一种估计方法是通过启发式估计来确定最优参数,这种启发式方法在[5]中也已用过,只不过是基于动态规划的启发式方法.
由于线性伸缩的匹配分数与它的两个参数间并非单调的关系,这种方法可能导致陷入局部最优点,不能获取全局最优参数,导致结果的准确率下降.
另一个问题局部参数精确化的问题,当使用同一的线性伸缩参数进行精确匹配时,某些局部对齐得好,而某些则较差,不同局部需要的线性伸缩参数是不同的,如何对各部分使用相应的参数进行匹配,是精确匹配的关键问题.
为解决线性伸缩匹配中面临的上述问题,本文中提出了两种分段信息,一种是基于极值点的分段信息,极值点即旋律中的最高点,这种信息被用来增加启发式估计线性伸缩参数时的候选起点,提高估计参数的准确性.
另一种是基于停顿点的分段信息,停顿点是哼唱过程中换气的位置,相当于音乐乐谱中的休止符.
本文同时提出了使用停顿点的分段信息并利用动态规划以及递归匹配的方法来优化对MIDI旋律的分段匹配,从而实现哼唱旋律和MIDI旋律之间的分段匹配.
本文的主要贡献是:(1)提出两种分段信息特征;(2)利用极值点分段信息实现了一种基于极值点分段信息的启发式估计算法;(3)利用停顿点分段信息实现了两种分段匹配方法,一种使用动态规划的策略,另一种使用递归匹配的策略.
本文最后给出的实验结果验证了所提出算法的有效性.
本文后续的内容安排如下:第二章介绍哼唱检索的基本原理,包括MIDI旋律、音符与基频的关系、特征提取及旋律匹配算法;第三章介绍极值点分段信息及停顿点分段信息;第四章研究利用分段信息进行匹配并提高检索的准确率,并研究动态规划和递归匹配两种优化策略;最后在第五章给出结论.

第2章哼唱检索的基本原理10第2章哼唱检索的基本原理2.
1本章引论本章阐述哼唱检索系统的基本原理.
首先简单介绍MIDI文件格式及MIDI旋律的表示方法,接着通过阐述音符与语音基频间的关系,说明音符的音高与基频间存在固定的关系,而后以此为基础介绍了基频提取,基频到音符的转化方法,通过提取基频及音符来提取哼唱语音的旋律特征,最后介绍基于已提取的旋律特征的多种匹配算法,其中主要介绍了最早的字符串匹配方法及与本文研究相关的几种匹配方法,包括线性伸缩(LS)、动态规划(DP)、递归匹配(RA)三种方法.
2.
2MIDI文件格式与旋律表示本文的哼唱检索是基于哼唱旋律与MIDI旋律进行匹配的.
MIDI即乐器数字接口(MusicalInstrumentDigitalInterface,简称MIDI),是一项工业标准的通信协议,通常用于电子乐器等演奏设备,它定义了电子乐器演奏所需要的数据包括音调、音乐强度、节拍、节拍速度等.
MIDI标准是戴夫·史密斯于1981年向音频工程协会提出的,MIDI规范的1.
0版本发布于1983年.
MIDI可以说是电子乐器的电子乐谱,MIDI乐器演奏一个音符包括了三个要素:(1)按下的MIDI乐器中的特定键如中央C,MIDI乐器中的每个键对应了特定的MIDI音符编号,这指定了音符的频率,MIDI音符编号可以参考MIDI标准[30].
(2)按下音符键时的力度用户按压键的力度越大,音符发声的强度就越大.
(3)释放按键的时间第2章哼唱检索的基本原理11释放按键和按下键间的时间差就是音符的时长.
若再通过一定的演奏速度弹奏各种音符,便构成了一首完整的音乐旋律.

MIDI文件是MIDI旋律的数字表示,一个MIDI文件的内容由多个块(chunk)组成,每个块的数据格式如表2.
1所示.
MIDI文件中包含两种类型的块,一种是头部块(HeaderChunk),用于描述整个MIDI文件的基本信息,对应块标识是MThd,另一种是轨道块(TrackChunk),用于描述MIDI的每个轨道的音乐数据,对应块标识是MTrk.
一个MIDI文件通常由一个头部块和多个轨道块组成,轨道块的数量取决于MIDI是单轨还是多轨及轨道的数量.
如表2.
2显示了MIDI文件由一个头部块和多个轨道块组成时的数据格式,其中各参数含义在错误!
未找到引用源.
中说明.
从表2.
2中可看出,MIDI文件主要用来表示MIDI中的事件信息,每一个轨道由多个事件构成,每一个事件设定了持续时间.
有关MIDI事件的详细描述可参考[30].
表2.
4中列出了几种常用的事件,由旋律轨数据格式及表2.
4中的几种事件看出,MIDI中每一轨的旋律演奏过程是发声、停止发声、…、发声、停止发声循环重复的过程,每次发声的过程都持续一定时间,且具有指定的音高.
表2.
1MIDI文件中的块格式组成部分描述块标识占4字节,ASCII字符串,表示块的类型头部数据长度占4字节,表示当前块的长度,不包含前面8字节数据占用空间由头部数据长度描述,存放块的所有内容表2.
2MIDI文件的块组成块类型块长度数据MThd6MTrk,…,…MIDI文件MTrk,…,第2章哼唱检索的基本原理12表2.
3表2.
2中的各变量说明变量说明表示MIDI文件的格式,占2个字节,有效的数值是0、1、和2.
0表示MIDI文件只有一个轨道块,1表示只有一个或多个轨道块,2表示只有一个或多个独立的轨道块表示轨道块的数量表示的单位时间长度表示块的长度,具体值由块内容的长度决定相对于前一个事件的时间长度事件表2.
4MIDI中的几种事件事件二进制格式说明开始发声0x9nnotespeedn表示轨道号,可取0~F,对于多轨MIDI可同时演奏多个轨道,n指定在哪一轨道发声,note为音高的MIDI编号,如中央C为60,speed为按键速度,也表示音的强度.
停止发声0x8nnotespeed参数与开始发声一致,停止发声也可使用0x9nnote0来代替.
设置音量大小0xbn07size0xbn39size7表示设置主音量的高字节值,39表示设置主音量的低字节值.
通过以上对MIDI文件格式的分析可看出,MIDI音乐的每一轨旋律可以使用一条音符曲线表示.
音符是乐谱中的基本单元,每个音符具有固定的音高,并且持续一定时间.
如图2.
1所示,表示了MIDI中某一轨的旋律,图中标注音符的音高为52即为对应的MIDI编号.
在MIDI播放时,当播放到所标注音符时,音符在7.
8秒发声,持续到10.
5秒时停止发声,然后继续播放下一个音符,由此演奏完整的MIDI旋律.
本文中我们主要研究单轨MIDI旋律,因此所有MIDI旋律均可以表示成如下的音符序列:(2-1)其中表示第个音符的持续时间,表示第个音符的音高值.
第2章哼唱检索的基本原理13图2.
1MIDI旋律及音符的发声与停止发声事件2.
3音符与基频之间的关系在音乐中,通常会提到音高的概念,同时根据不同人发声的音高范围将男性分成男低音、男中音、男高音,将女性分为女低音、女中音、女高音.
这种音高,即音调的高低实际上是语音信号基频大小的表现.
尽管在语音信号中任何复合乐音实际上是由基频和许多谐波组成,通常我们所说的音调高低,是说它的基频的高低,而不管它的谐波成分[31].
音高仅仅取决于基频大小,而音符作为旋律的基本组成元素,代表了一段时间内某一音高的声音.
音符是西方音乐中的基本元素,是乐谱中构成音乐的最小单元,它使得音乐得以让人演奏、理解和分析.
如果两个音符的频率相差整数倍,则听觉上会感觉非常相似,因此通常将这种频率相差整数倍的音符归入同一音高集合.
两音符之间如果频率相差一倍的话,就称它们相差一个八度.

因此在音乐中,要确定一个音符,必须知道它所在的音高集合及所在的八度.

在传统音乐中,可以使用7个拉丁字符:A,B,C,D,E,F,G来表示音高集合的分类,在不同的八度中,这些音符按照顺序不断地重复,为了区分不同八度的同一分类的音符,通常使用一些辅助标记.
在科学音调记号法中,利用分类的字母及表示其所在八度的阿拉伯数字来表示音符.
以标准音高440赫兹为例,其对应第2章哼唱检索的基本原理14的音名记号是A4,表示属于标识为A的分类,且在第4个八度上.
A4后面的音符为B4,C4,D4,E4,F4,G4,A5,B5,B6,….
在传统的音乐系统中,一个八度的标记通常由C音符开始,也就是说,C4所在八度的所有音符是C4,D4,E4,F4,G4,A5,B5.
由于发展的需要,后来在音名后面加上变音记号,如升号或降号.
表示在原来音高基础上再升高或降低半音,根据十二平均律(目前最广泛的调音法),即将原频率升高或者降低到1.
0594倍.
升高标记符号为,降音符号为,如C,D表示降D,可知B与C事实上表示相同音符.
这样半音阶在原有的七个音高集合中又增加五个集合,并且任意两相邻的音高集合刚好相差一个半音.
对应的12个集合在一个八度上的音符如表2.
5所示,表中任意两相邻音符间相差一个半音,同时表中标记了每个音符对应的MIDI编号.
任何一个音符与MIDI编号都有唯一的对应关系.
不同音符具有不同的频率,相差一个八度的两个音符,音调高的音符频率是音调低的音符频率的两倍.
由前述已知,在一个八度中,总共划分了12种音高集合,每两相邻集合的对应音符间刚好相差一个半音阶,从而一个八度中有十二个特定频率的音符.
这些固定频率之间存在固定的数学关系.
一般最基本的音符是A4,该音符的标准音高一般取440HZ.
表2.
5自C4(中央C)开始往上八度内的半音阶及对应MIDI编号主音第二音第三音第四音第五音第六音第七音自然音CDEFGAB升半音CDFGAMIDI音符编号606162636465666768697071按惯例,音乐中的音名通常由一个字符、变音记号及用来代表其在哪一八度的阿拉伯数字构成.
所有的音符都可用中央A(A4)的整数倍表示,假设任何一音符与A4音符之间的这个整数倍为n,那么如果一个音符高于A4音符,则n为正值,否则为负值.
由此任何一个音符的对应频率为:(2-2)第2章哼唱检索的基本原理15根据表2.
5的编号规律,不难得出MIDI编号与频率之间的关系:(2-3)(2-4)其中表示音符对应的MIDI编号,这里可以为小数,表示音符对应的频率.
由上述的关系表达式可知,MIDI编号与音符频率,即基频之间存在固定的转化关系.
为了更直观的说明这一关系,我们使用一MIDI文件边播放边录音,然后对录音提取基频,再将基频通过上述公式转化为MIDI音符编号,来验证这一结论.
结果如图2.
2所示,图中第一条曲线为原始的MIDI旋律曲线,最后一条曲线为由录音通过提取基频再按上述公式转化得到的MIDI旋律.
可以看出,从录音提取的MIDI旋律与原始MIDI旋律保持一致,说明通过提取哼唱语音的基频作为特征并转化为音符是一种合理的方案.
10121416182022506070时间MIDI音高原始MIDI旋律0123456789x104-0.
500.
5时间幅度由MIDI录制的旋律语音024681012200300400由录制语音提取的基频时间频率024681012506070时间MIDI音高由基频计算得到的MIDI旋律图2.
2由MIDI录制语音并提取基频转化为MIDI旋律第2章哼唱检索的基本原理162.
4哼唱语音旋律特征的提取2.
4.
1音高的提取音高提取是语音处理中经常碰到的问题,从上世纪六十年代开始对基频的研究以来,已有很多的研究和改进工作.
尽管没有明确的模型来计算音高,但音高和基频之间存在直接关系,且这种关系表明它们之间可以通过公式相互转化,这一点在上一节中已经证明.
因此可以将音高提取转化为基频提取,因此音高提取也称为基频提取或F0提取.
基频(F0)是准周期语音信号的最低频率,基频仅仅针对周期语音信号而言.

基频和基音周期是相互关联的概念,它们之间有如下关系:(2-5)因此,通常将基频提取的问题,归结为基音周期的估计问题.
如图2.
3展示了一段周期语音的基音周期,其中每两个箭头所指位置相差的时间为一个基音周期.
音高提取的关键是对基频或基音周期的准确提取,目前已经有很多的方法来实现,并且大部分算法只要参数选择恰当都可以达到实时计算的要求,因此对于本文的哼唱检索,只需考虑算法特征提取的准确率.
一般提取基频的方法有:基于时域的方法、基于频域的方法和基于统计的方法.
(1)基于时域的方法.
图2.
3基音周期第2章哼唱检索的基本原理17这一类方法利用了语音信号的周期性.
这种特性使得这些方法遇到非和谐波信号或信号的主要能量集中于高频部分时变得异常脆弱.
这里仅以最常用的自相关法为例.
设语音信号为,则其自相关函数定义为:(2-6)对于周期信号,其自相关函数的周期与原始信号的周期保持一致[32].
因此,可以利用这一特点来估计语音信号的基音周期.
(2)基于频域的方法这里介绍基于倒谱(Cepstrum)方法,语音信号的倒谱定义为:(2-7)其中表示的傅里叶变换,对于周期信号,同样有信号倒谱的周期性与原始语音信号一致的结论[33],因此求原始信号的周期,可以转化为求倒谱信号的周期.
在实际提取过程中,需要对原始语音信号进行加窗处理,由于这种方法和(1)中的方法都是用于估计原始信号的基音周期,要求窗长不能太短,所加窗内至少包含两个基音周期,也不能太长,如果窗长太长,则窗内包含了多种基音周期,对基音周期的估计会出现偏差.
对于人在哼唱中的基频,与正常语音的基频范围大致相同,一般男声的最低基频可达到40赫兹,而女声总体比男声高,女声最高基频可达到600赫兹.
在对哼唱语音提取基频时,应当根据人发声的基频范围,设置合适的窗长提取.
(3)基于统计的方法这类方法利用的是具有相同音高的语音帧之间的相似度.
对语音中每一帧,通过提取和基频有关的特征,再通过统计的方法进行分类,根据在基频上的差异分成不同类别.
这些方法的弱点是必须使用训练数据.
因此,训练数据的质量及训练过程都会影响最终模型输出结果时的准确率.
目前这类方法主要有基于神经网络[34,35]和HMM[36,37]的方法.
以HMM的方法为例,从统计学观点来看,一段哼唱语音信号,可以看成是一个未知过程第2章哼唱检索的基本原理18输出的观察序列,而这个未知过程正是哼唱者想要哼唱的内容,但所能观察到的只有语音信号,及提取的语音特征.
因此,这一过程可以使用HMM进行模拟.
HMM中的转移概率需要考虑给定音符自身的过程包括音符开始发声、持续及停止的过程,还要考虑音符转移到其他音符的过程.
一个音符完整的发声过程可以认为由开始发声(由其他音符转移到当前音符,音高逐渐变为音符的标准音高)、持续(音高保持不变,并持续一定时间)和停止(音高逐渐变化开始为哼唱下一个音符做准备)三种状态组成.
HMM中的输出概率可以认为是某一音符输出对应的语音信号特征的概率.
这样音高提取过程就变成搜索音符内及音符间迁移使这一过程输出对应的语音信号特征的概率达到最大的过程,这一搜索过程可以使用Viterbi解码来解决.
定义了音符内的状态迁移及音符间的迁移,便可以构造一个两层的HMM结构.
这点类似于使用HMM进行汉语语音识别的过程,音符类比于汉语中的词,音符内的状态类比于汉语中的声韵母.
假设我们定义音符之间的迁移所在的层次为事件层次,而音符内的迁移为发声层次.
在事件层次上的每一状态对应了不同的基频,哼唱的旋律被描述成这些状态构成的序列.
如图2.
4中(a)所示为事件层次上不同状态之间的迁移过程,每个状态迁移到其他状态的概率和状态的持续时间有关.
这可以通过对旋律数据进行统计得到.
而在发声层次中的每一状态表示了音符发声的某一阶段,如图2.
4中的(b)所示,图中a表示开始发声,s表示持续,r表示声音停止,其中一个音符可以不需要停止就直接由持续状态迁移到另一音符的发声状态.
定义了HMM中的状态,对应的语音模型便可以通过训练数据得到,然后通过Viterbi解码过程得到语音信号中的音高,这种方式同时提取了音符信息.
第2章哼唱检索的基本原理19图2.
4HMM中两个层次的状态转移2.
4.
2音符的提取音符提取方法大致可分为非统计和统计的方法.
(1)基于非统计的方法对于基于非统计的方法,关键问题是音符起点的估计问题,估计出每个音符的起点后,便可结合语音信号中的静音、音高等其他特征进行音符分割,从而给出语音信号的音符序列.
如图2.
5为音符起点(onset)的示意图,一般在哼唱的音符开始时,语音信号能量会突然上升(attack),然后持续一段瞬时时间(transient),再逐渐下降(decay),这段瞬时时间的起始点,称为音符起点.
onsetattacktransientdecay图2.
5音符起点第2章哼唱检索的基本原理20音符起点检测是音符提取中一个重要的步骤,通过音符起点检测,将每一个音符从语音信号中分割出来,并得到每一个音符的时长信息.
再结合预先提取的音高信息,计算每个音符的音高,便将一段旋律表示成了具有音高和时长的音符组成的序列.
经过这种处理的特征,和MIDI旋律的音符特征保持一致,便可以和MIDI旋律进行匹配了.
在哼唱检索系统中,音符起点检测、音符分割的好坏,直接影响匹配环节,对整个系统的准确率有很大影响.
因此,对于基于非统计方法进行音符提取的哼唱系统,音符起点检测在系统性能中扮演了重要角色.
对于音符起点检测的相关研究中[38,39],一般将音符起点检测分成预处理、简化、峰值提取及决策四个阶段.
语音信号经过预处理,将原始语音信号转换到频域用于分析或进行其他特征计算.
然后通过简化处理,从转换后的信号中提取能够表现音符起点的特征序列如能量,一般在音符起点之后,语音信号的能量会出现突然上升的趋势,因此这种能量突然上升可作为音符起点检测的依据,这一简化过程也被称为检测函数.
经过检测函数处理后的信号,在音符起点部分与其他部分有显著的区别.
接着进行峰值点提取,峰值点提取的主要目的是从检测函数的输出结果中,选取可能为音符起点的特征点,作为音符起点候选.
如当检测函数对音符起点的能量突变有较大输出值时,根据峰值提取得到的大部分候选时间点,即是音符起点.
最后进行决策,决策的过程是通过一定的判断函数,来决定由检测函数给出的峰值点是否是音符起点,最后给出所有音符起点.
(2)基于统计的方法基于统计的方法较为常用的是基于HMM的方法,已知语音信号的观察序列为,则语音识别的目的是找出这样一个词序列,使得该词序列对观察序列具有最大的后验输出概率.
最大后验输出概率定义为:(2-8)在哼唱检索中,音符提取同样可看成是语音识别的过程,上述的可以看成旋律中的音符序列,可以看作音符序列对应的观察特征向量.
然后训练一个语音模型用于计算输出概率,同时训练一个语言模型计算先验概率第2章哼唱检索的基本原理21.
最后通过一种"oneglobalsearchprocess"[40]的方法来进行语音到音符间的转换.
通常音符提取是以音高序列为基础再通过对音高序列进行分割归并得到音符的过程,每一个音符由一段对应的音高序列转化得到.
尽管这种方式比较直观,在语音与非语音之间给出明确的界限却比较困难.
即便是最好的音高提取算法,也不免会有分类错误的情况存在,这些错误对算法提取音符造成不利影响,如果语音带噪情况比较明显时这种影响就更严重.
为了提高语音模型的鲁棒性,在HMM中,可以使用高维的倒谱特征作为音符的表达形式,而不再使用音高序列来表示[36].
如图2.
6所示为音符C4(对应MIDI编号为60,基频为220HZ)的某一语音帧的倒谱(上)及一非语音帧的倒谱(下).
倒谱图(a)中的低频部分由于不可能包含任何音符信息,因此被截去.
可以看出,对于语音帧而言,其倒谱图中有多个峰值点,而对于非语音则不存在明显的峰值点.
在倒谱中,横轴参数与对应频率及采样率之间有如下的关系:(2-9)其中表示对应的基频.
已知语音帧的基频为220HZ,并且已知语音的采样率为16kHZ,按此公式计算得到的峰值位置应当在,与图中(a)对应倒谱的第一峰值点符合.
倒谱特征再经过一定的预处理便可用于训练语音模型.
首先,从倒谱中取出与基频相关的区域特征,这个区域的下限值对应人可能的最高基频,上限值对应人可能的最低频率.
对男性的哼唱语音而言,在采样率为16kHZ的条件下,可取到之间的区域,这正好对应于音符C2到E4(对应的MIDI编号为36到64)之间的音的频率范围,转化为对应的基频则为66.
6HZ~333.
3HZ,符合男性的基频范围.
对于女性哼唱,同样在16kHZ的条件下,可取到的区域用于提取特征,这对应于音符C3到E5(对应MIDI编号为48-76)之间的音符发音,表示的基频范围为133.
3HZ到666.
6HZ,也符合女性基频范围.
确定倒谱中的区域后,对应区域被压缩成固定长度,并根据压缩比率对倒谱中的特征值进行适当调整.
由于在以上过程中,男性的区域宽度是女性的区域宽度的两倍,被压缩后就相当于将男性的音高提高了一个八度.
第2章哼唱检索的基本原理22倒谱中的区域经过压缩,归一化到同样长度,便可以提取倒谱特征训练语音模型了.
在HMM中,除了语音模型,还需训练语言模型.
如前文所述,在西方音乐记号系统中,一个八度内有7个主音,包含12个半音音符.
即有些半音音符可能在一首歌的所有旋律中都不出现.
因此,在基于HMM的音符提取系统中加入语言模型有利于系统正确率的提高.
有两种方法可以用来训练语言模型,一种是音符相关的,另一种是主符无关的,对于前一种,需要对每一个主音建立一个语言模型并且语言模型是跟哼唱信号相关的.
如果语言模型使用不当,反而会使结果变差.
而对于音符无关的方式,用于训练的旋律中的音符被调整到其他的11种音符,这样原始的旋律与被调整的旋律构成一个更大的数据库来训练n-gram的语言模型,这里的n一般取值为4.
训练得到语音模型和语言模型后,即可按照HMM的方式,对任何一输入的哼唱语音,通过提取每一语音帧的特征构成观察向量,得到最终提取的音符序列.
图2.
6(a)为音符为C4的语音帧的倒谱,(b)为非语音帧的倒谱第2章哼唱检索的基本原理232.
5哼唱旋律与MIDI旋律的匹配2.
5.
1匹配的定义哼唱检索中的匹配,是指根据用户以歌词唱、哼唱或者吹口哨、打拍子等形式录制的哼唱语音,提取一定的特征,并和数据库中预先存储的特征计算相关度.
2.
5.
2匹配的特征用于匹配的特征根据不同匹配算法可以使用多种形式的特征,如基音周期、节拍、停顿、音高的升降等,一般常用的特征是哼唱语音的基音周期(Pitch),基音周期的提取可以使用自相关法[41]、循环AMDF方法[42]、基于CEP和LPC谱的方法[43]、小波分析[44]等,通过提取得到基音周期的序列,转化成对应的MIDI音高,再对音高进行归并,得到MIDI音符序列,至此即可使用音高序列和音符序列作为特征来进行检索匹配.
本文使用的提取基音周期的方法是基于CEP的方法,提取音符序列则使用HMM的方法[36],而数据库使用MIDI数据库.
获得基音周期后,可以计算得到对应的基频,基频和MIDI的音符之间存在对应的转化关系,在使用MIDI标准时,MIDI音符的音高和频率之间的对应关系为:(2-10)其中表示频率,表示MIDI音符的音高,440是的标准音高(440赫兹).
由此可以看出,比较哼唱查询语音和MIDI旋律之间的差异,实质上是比较它们之间在频率变化上的差异.
2.
5.
3匹配的难点通过将每帧基频转化为音高,构成音高的序列,同时再使用HMM的方法对音高序列归并提取音符序列,再与数据库中MIDI音符序列进行比对.
如图2.
7所示,第一条曲线为查询语音的音高序列曲线,第二条为查询语音的音符序列曲线,第三条为数据库中对应的目标MIDI的音符序列曲线.
第二条曲线中的非水平部分为哼唱查询语音中的非语音部分.
可以看出,MIDI音符序列比较标准,音符长度的变化较为平缓,而查询语音的音符序列则不规则,但是总体第2章哼唱检索的基本原理24变化趋势和目标MIDI音符序列基本一致.
同时哼唱语音的速度和MIDI旋律的速度有一定缩放,总体的音符音高和MIDI音符之间也存在一定的纵向偏移.
由此可以看出,对于匹配算法,必须考虑如下情形:(1)音高偏移:哼唱查询语音的音符与实际的目标旋律音符存在一定差异,即音调总体偏高或偏低;(2)线性伸缩:哼唱查询语音的速度和目标MIDI旋律的速度存在一定差异,或快或慢或快慢不均;(3)音符不匹配:尽管哼唱查询语音与目标MIDI的旋律在大体轮廓一致,哼唱语音中的音符相比目标MIDI中的对应音符,或长或短,或缺失或被分成2个音符等.
对于如上所述的3种情形是研究匹配算法需考虑的,也是匹配算法要解决的难点.
前2条针对两段旋律间的整体情况而言,第3条是针对两段旋律间每个音符之间匹配的情况.
图2.
7哼唱查询语音的音高、音符序列及目标MIDI的音符序列片段第2章哼唱检索的基本原理252.
5.
4匹配的分类根据匹配算法的层次,可以将匹配算法分成快速匹配和精确匹配.
快速匹配的目的是对系统由MIDI数据库生成的大量候选,利用一定的算法,快速从大量候选中去除可能性较小的候选,减少后期匹配的计算量,提高系统时间响应性能.
快速匹配强调匹配速度,同时也强调在一定程度内保持正确的候选.
[27]中就使用了多种不同的特征和不同的方法来进行快速匹配,如使用前几个音符、方差、最大音高等特征,并用线性分类器及简化版的递归方法进行快速匹配以保证计算速度.
精确匹配的目的是将哼唱旋律片段和所有候选旋律片段进行更精确的相似度计算以获取最终候选列表.
精确匹配的特点是计算量大、时间消耗大但计算结果更精确.
精确匹配一般处于系统后端,其计算结果直接输出作为最终候选.

如常用的DTW算法在精确匹配中使用较多,DTW方法能较好地解决上述提到的匹配难点中的后2条,而对于音高偏移,则难于解决,必须依靠其他方法估计音高偏移,或通过设置不同音高偏移计算DTW来估计最佳音高偏移同时获得最小差异值.
如[3]中使用启发式方法来估计最佳音高偏移,通过以当前音高偏移值附近的其他值来计算DTW分数并和当前音高偏移对应的DTW分数比较,不断调整当前音高偏移值直到DTW分数不再下降,来计算最佳的匹配分数.
2.
6哼唱旋律与MIDI旋律的匹配算法2.
6.
1基于字符串匹配的方法字符串匹配方法源于对旋律变化的直观感觉,是对旋律变化信息作一定的简化处理进行的匹配.
通过将旋律提取为音符序列,再根据两相邻音符之间的升高、降低或音高不变的情况将旋律表示为特定的字符串.
当然,也可以使用其他的方式将旋律转化为字符串,这里以最简单的即音符的升降为例来介绍.

在获取旋律的音符序列后,为描述旋律的变化信息,字符串匹配方法将旋律的变化根据上升、下降和不变,分别标记成U/D/S三个字符,由此构成一个由U/D/S三个字符组成的字符串序列.
如图2.
8所示为一段示例旋律的字符串表示,该旋律对应字符串为UDDDDDUSUUDD.
第2章哼唱检索的基本原理2699.
51010.
51111.
51212.
51313.
514-4-20246810时间音高字符串匹配中的字符串表示UDDDDDUSUUDD图2.
8字符串匹配中音符变化的字符串表示在将数据库旋律及哼唱旋律都转化为字符串之后,使用字符串匹配算法计算二者的距离,由于音符提取时会存在一定的错误,要求字符串匹配算法必须容忍一定的错误,由于具体算法与本文研究课题无关,可参考相关文献[12,14].
2.
6.
2线性伸缩线性伸缩方法通过将其中一旋律进行拉伸及音高平移,达到与另一旋律对齐匹配的目的.
由于不同人的音域不同,导致哼唱同一旋律时,音调或比数据库标准旋律高,或低,但变化基本一致,因而在人听来依然是同一歌曲.
同理,不同人对速度的把握也不一致,因而也存在不同人的哼唱旋律与数据库旋律存在不同速度比的情形.
在拉伸系数及音高偏移得到有效估计的条件下,线性伸缩方法能够有效地检索出目标旋律.
如图2.
9所示为线性伸缩的示例,这里没有标记音高偏移,哼唱旋律经过不同拉伸系数进行拉伸后,再经过纵向平移(即音高整体加一个偏移值),然后与数据库MIDI旋律进行对齐计算相似度.
线性伸缩方法计算起来简单,同时较直观,在旋律起点对齐正确的情况下,只要找到正确的拉伸系数和音高偏移,就能找到目标旋律.
其缺点是:1.
对起点对齐的要求较高,如果对齐出现错误,则哼唱旋律无论如何拉伸平移,都很难与目标旋律达到理想的匹配结果.
如果对数据库旋律中的每一音符都作为起第2章哼唱检索的基本原理27点与哼唱旋律进行线性伸缩匹配并估计伸缩参数,则计算量太大.
2.
必须选择适当的拉伸系数和音高偏移.
哼唱旋律和MIDI旋律一般不适合直接进行匹配,必须预先估计拉伸系数和音高偏移,尽管可以使用穷举法计算最佳参数,但计算量太大.
因而需要在不增加过多计算量的前提下估计出合适的拉伸系数和音高偏移;3.
当哼唱旋律长度较大时,使用同一的拉伸系数和音高偏移效果不再明显.
使用线性伸缩进行匹配的理想条件是哼唱旋律在各处的音符与目标MIDI旋律中的对应音符具有一致的音高偏移和拉伸系数.
但这一条件在实际中很难达到,从图2.
3可以看到,当哼唱旋律经过拉伸与MIDI旋律局部对齐较好时,其他部分的对齐则可能较差,很难达到各处均达到最佳对齐的效果.
024681012141618时间哼唱旋律经过线性伸缩与MIDI旋律的对齐结果MIDI旋律曲线哼唱旋律,拉伸比率1哼唱旋律,拉伸比率1.
1哼唱旋律,拉伸比率1.
2图2.
9线性伸缩进行匹配的示例:哼唱旋律经1倍、1.
1倍及1.
2倍拉伸后与MIDI旋律对齐匹配2.
6.
3动态规划动态规划应用于哼唱检索,在实现时必须施加一定的限制,受特征提取等方面的影响,可能会出现MIDI旋律中的一个音符对应于哼唱旋律中的几个音符的情况,但无论如何,该音符的时间和对应的几个音符的累积时间之间的比率应当不会超过某一比率值.
假设哼唱旋律的音符序列为,其中,表示第个音符,表示第个音符的音高,表示第个音符的时长.
MIDI旋律的音第2章哼唱检索的基本原理28符序列为,其中,表示第个音符,表示第个音符的音高,表示第个音符的时长.
同时假设哼唱旋律相对MIDI旋律的音高偏移为,假设在动态规划过程中会有一个音符匹配多个音符的情况,且无论是MIDI音符匹配哼唱旋律中的多个音符,还是哼唱旋律中的一个音符匹配MIDI旋律中的多个音符,均限制MIDI旋律的累计时间与哼唱旋律的累计时间之间的比值必须在区间内.
则与的动态规划距离可描述为:(2-11)其中满足:(2-12)其中表示使用动态规划方法计算和之间的差异值.
表示使用线性伸缩方法并且设置音高偏移系数为计算音符序列和之间的差异值.
则表示使用线性伸缩方法并设置音高偏移系数为计算音符序列与之间的差异值.

动态规划的问题,实际上是一个递归最优的问题,并且在递归的过程中需要使用线性伸缩匹配.
这里的线性伸缩匹配两段旋律的左右边界已经确定,并且音高偏移已经预先提供,因而线性伸缩较为容易计算.
同时,这种动态规划方法将线性伸缩细化到了不能再细化的地步,对匹配中的每个音符给予不同拉伸系数.
相对而言比直接进行线性伸缩匹配更为灵活,当然,这种方法的计算量也比较大.
2.
6.
4基于递归的线性伸缩方法这种方法采用递归的按中点切分进行线性伸缩匹配来探索最优的匹配结果[27].
由于这种方法属于分段匹配的方法,与本文研究内容关系较密切,因此做详细介绍.
这种称为递归对齐(RecursiveAlignment,RA)的方法从线性伸缩匹配第2章哼唱检索的基本原理29扩展而来但是比线性伸缩方法更好.
它克服了线性伸缩在匹配时对旋律总体使用单一的拉伸系数和音高偏移而导致的匹配不够精确的问题.
同时,这种方法既满足了线性伸缩的要求,又是一种自顶向下、由粗而细的方法,对旋律粗轮廓的匹配优于直接动态规划的方法.
根据原文,该种算法中MIDI旋律使用音符表示,而哼唱旋律使用的是音高序列.
音高序列即未进行归并得到音符前的序列,由每一帧的音高构成.
设哼唱旋律,其中表示第帧的音高,表示音高序列的总长度.
设MIDI旋律为,其中表示第个音符的音高和时长,这里的时长以帧数表示,与哼唱旋律相对应.
设为预先设定的拉伸系数和音高偏移的可选参数列表.
再设为最大可递归的深度,一般设置为3或4.
则算法描述如下::上述算法中的表示使用线性伸缩的方法对音高序列和音符序列计算差异值,亦同理.
则表示对子序列和继续使用参数再做层的递归调用.
第2章哼唱检索的基本原理30该算法实际上是通过不断的分段调用线性伸缩方法计算差异值,同时递归调用获取最佳分段方案及最小差异值.
这种方法的弊端也是很明显的,线性伸缩的拉伸系数及音高偏移均是预先设定的,由于拉伸系数和音高偏移的组合比较多,如果中的组合数太少,则对准确率有一定的影响,而如果中的组合数太多,则会增加不必要的计算量.
2.
7本章小结本章从哼唱检索的基本原理出发,介绍了MIDI的数据格式,从而引出音符与基频之间的关系,接着分析了音高和音符特征的提取,最后阐述了旋律匹配的相关概念,并详细介绍和分析了最早的及跟本文研究关系较为密切的几种方法,分析了这些方法的优缺点.
当然,实际上还存在其他的一些算法,但是由于与本文的研究关系不大,因此不做详细介绍.
第3章分段信息31第3章分段信息3.
1本章引论在第2章中描述了匹配的难点,哼唱查询语音的旋律曲线与目标MIDI旋律曲线之间,尽管大致轮廓及变化趋势保持一致,却并非完全一致.
使用线性伸缩方法进行旋律匹配,首先面临的问题是旋律归一化的问题,即在旋律进行对齐之前需要先对哼唱旋律和MIDI旋律进行归一化,以使二者尽量保持相同的速度和音高,尽管启发式估计算法有利于找到最优的拉伸系数和音高偏移两个参数,但可能陷入局部最优解.
另一个问题是线性伸缩的全局参数问题,对于音高偏移,由于哼唱者的个人音色不同,不同人与同一MIDI旋律之间有不同的音高偏移,同时由于个人水平、对歌曲的熟悉度等原因,同一人哼唱同一首歌的不同旋律片段时也很难保持与MIDI完全一致的音高偏移,因而音高偏移是随人随时间不同而变化的.
对于拉伸系数,也有相同情形,哼唱者很难做到哼唱的每一片段都与MIDI的对应旋律在速度上保持完全一致的速度比,同时在哼唱句子的切换过程中最容易导致拉伸系数的改变.
从另一个角度来看,哼唱旋律与目标MIDI旋律的线性伸缩参数在局部保持稳定,只是由于在特定时间点由于换气等原因导致变化而影响了参数.
针对旋律归一化以及匹配时局部参数不一致的问题,本文提出了两种特征来解决这两个问题,一种是基于极值点的分段信息,由于其对齐的效果比较好,用于增加启发式估计算法的候选起点.
另一种是基于停顿点的分段信息,由于这种信息可以合理的将哼唱旋律分成不同句子,相当于乐谱中的小节,可以利用这种信息进行分段地线性伸缩匹配.
本章主要阐述极值点和停顿点两种旋律特征点,主要介绍它们的定义,优点以及估计方法等.
第3章分段信息323.
2基于极值点的分段信息3.
2.
1极值点的定义极值点即在旋律音符曲线中升到最大值再转而下降的点,或者是降低到最小时转而升高的点,本文主要讨论最高点,如无特别说明,以下所说的极值点都指最高点.
本文所说的旋律曲线的极值点和一般的极值点定义稍有不同.
旋律曲线中的最高点(最低点),只有当其相对两侧"升高"("降低")的幅度超过指定阈值,这样的最高点(最低点)才称为极值点.
这里升高或降低幅度的计算方法也和一般的计算方法不同,在计算最高点对左侧上升的幅度时,从该最高点往前追溯,并跳过伪最高点和伪最低点,直到追溯到一个最低点,则该最高点和追溯到的最低点之间的音高差即为该最高点左侧相对升高的幅度值,最高点对右侧升高的幅度也通过类似方法计算.
如图3.
1所示为一最高点及两侧追溯到的最低点的示例.
02468101214-10-8-6-4-20246810时间轴音高旋律中的极值点特征图示最低点B最高点A最低点C图3.
1旋律中极值点特征图示极值点中的伪最高点和伪最低点,可以认为是旋律的升高或降低等过程中因干扰或旋律本身变化不大的凹凸变化,由于这种小的凹凸变化至少对一侧相对升高的幅度太小,认为是伪最高点或伪最低点.
以伪最高点为例,图3.
2列出了三种类型的伪最高点,第一种为旋律上升过程中的伪最高点,第二种为旋第3章分段信息33律下降过程中的伪最高点,第三种则为旋律保持平稳过程中的伪最高点.
由于伪最高点的变化较小,特征不明显,极有可能是因为哼唱过程中的不稳定或噪声等因素导致的短时起伏,因此在提取极值点过程中需将此类极值点作为伪极值点去除.
旋律中的极值点代表了旋律中较高亢的部分,同时预示了旋律音高局部变化的边界值,因此是重要的参考点.
假如一段旋律由最低点升高到最高点再降低到最低点,那么可以认为另一段旋律也应当做类似的升降变化,在听觉上才认为相似.
如图3.
3所示为歌曲"冬季到台北来看雨"的前3句哼唱以及对应MIDI旋律的最高点标注.
通过将图中哼唱的语音信号与旋律的极值点标注可以看出,极值点的位置对应的语音信号能量也比较强,这就印证了极值点是旋律中高亢部分的说法.
另外,图中哼唱旋律的第一个最高点和第二个最高点之间跳过了一个伪最高点.
从图中还可看出,通过对旋律做最高点分割后,每两段对应的片段在变化上极相似.
若通过此种方式分段后,利用这种分段信息向启发式线性伸缩参数估计算法增加候选起点来估计线性伸缩参数,将有利于对线性伸缩参数的估计.
00.
511.
522.
533.
544.
50510第二类伪最高点00.
511.
522.
533.
544.
50510第一类伪最高点00.
511.
522.
533.
544.
50510第三类伪最高点图3.
2伪最高点的三种类型第3章分段信息34024681012x104-101采样点幅值哼唱语音02468101214-10010时间轴音符哼唱旋律的音符旋律10121416182022242628506070音符MIDI旋律的音符旋律片段图3.
3哼唱旋律和MIDI旋律的最高点3.
2.
2极值点的估计对极值点估计的思路是:先从旋律中找到比左右音符音高大的最高点,然后对最高点的左右两侧分别计算相对升高的幅度,根据升高的幅度是否满足预先设定的阈值,决定是否将最高点作为伪最高点舍弃.
估计算法思路如下:对旋律中每一个比左右两侧高的音符:(1)对左侧向前追溯,跳过伪最高点,计算相对升高的幅度(2)对右侧向后追溯,跳过伪最高点,计算相对升高的幅度(3)如果有任何一侧的下降幅度小于设定值,则当前最高点作为伪最高点去除,否则加入极值点列表.
具体算法描述如下:将旋律中每一音符的音高构成音高序列,假设为:,其中表示音符个数.
(1)对从左往右直到找到位置,满足:(2)令索引位置,,,当时重复:若,则:第3章分段信息35如果,转3.
否则:(3)若,转1继续.
(4)令索引位置,当时重复:若,则:如果,转5.
否则:(5)若,转1继续.
(6)将位置加入最高点的位置列表,若转(1)继续,否则算法结束,返回位置列表.
上面的算法中用到了2个参数,,,这两个参数均为预先设定的阈值,具体含义解释如下:指针最高点往两侧移动以估计其升高的幅度,如果碰到一段音高上升的旋律,考虑可能碰到伪最高点,指针继续移动,直到旋律连续上升超过了值,此时指针停止移动,并将最后一次下降到的音高值作为估计的最低点的值,和最高点计算音高差值,作为升高的幅度,只有当最高点相对两侧所升高的幅度值均超过时,此最高点才被确认为最高点,否则作为伪最高点被舍弃.
3.
3基于停顿点的分段信息3.
3.
1停顿点的定义停顿点是指在旋律哼唱过程中停顿的位置,所谓停顿,是指发声过程的停止并保持一段时间.
由于这种声音的停止,造成在语音信号中存在短暂的非语音信号并持续一定时间.
因此,停顿点实际上表现为一个非语音片段.
如图3.
4所示为停顿点的示例,图中的哼唱语音总共哼唱了5句歌词,共出现了4个较第3章分段信息36长的非语音片段,即该哼唱语音中包含4个停顿点.
图3.
4停顿点示例停顿点的产生是基于旋律节奏的需要,在乐谱中每一段旋律都由小节组成,在人哼唱旋律的过程中,需要在不同小节的切换过程中换气,或停顿,以保证下一小节的哼唱及旋律的节奏感,从而导致哼唱的语音信号中出现持续一定长度的非语音信号.
Time(s)0.
26332.
954Pitch(Hz)755000.
2632932522.
95423456图3.
5语音信号中的停顿以及在音高提取的表现如图3.
5所示,由于人在换气或者停顿的过程中,对应的语音信号中就不存在包含人声的语音流,经音高提取,对应的音高旋律曲线中会出现一定的"空缺"片段.
当音高旋律经过特征提取算法分割成音符序列时,这部分"空缺"第3章分段信息37片段被归并成一个单独的音符,称为静音音符.
这种持续一定时间的静音音符,即为本文中所说的停顿点.
3.
3.
2停顿点的物理意义停顿点是由于旋律中小节的切换产生的,休止符作为小节的结束标志,是音乐乐谱中表示乐音休止的符号.
在一首特定的旋律中,每个休止符具有固定的时间长度,长度大小与旋律速度有关.
根据休止时间的不同把休止符分成不同类别,相邻的两类休止符之间的时间长度是两倍的关系.
表3.
1乐谱中的休止符记号五线谱记谱简谱记法休止符名称全休止符二分休止符四分休止符八分休止符十六分休止符三十二分休止符六十四分休止符如表3.
1所示为乐谱中的不同休止符记号,在旋律的速度固定的情况下,按照停顿的长度,定义了不同的休止符.
全休止符的时间长度计算公式是:(3-1)其中表示旋律速度,即每分钟的拍数,表示以几分音符为一拍.
如在一首每分钟120拍,4分音符为一拍的旋律中,一个全休止符的时间长度是2秒,对应的二分休止符时间长度是1秒.
在乐谱中,休止符的时间长度根据其为几分休止符与对应的乐音音符的时间长度保持一致,每个乐音音符都有对应的休止符,如图3.
6所示.
休止符的音高与对应音符的音高一致.
第3章分段信息38图3.
6乐谱中的休止符和对应的乐音音符在MIDI旋律中,休止符在音符曲线上表现为持续时间较长的音符,由于乐器在弹奏此类较长的音符时,乐弦只会触发一次,而随着时间的变化,振动的能量逐渐衰弱.
当遇到休止符时停止弹奏,随时间的变化能量可能衰减到0,并持续一定时间静音.
人在哼唱过程中的停顿与休止符是一样的道理,如图3.
7所示,展示了哼唱旋律中的停顿点与MIDI旋律中的休止符之间的对应关系,每一个停顿点对应了一个MIDI中的休止符.
可见停顿点实际上是旋律中小节的分割点.
图3.
7停顿点与MIDI中的休止符对应关系音乐旋律中的停顿使得人在哼唱的过程中可以进行换气以保证哼唱的继续进行,同时也有时间来思考准备下一句的哼唱过程,而对于停顿点的时间,哼第3章分段信息39唱者可能因为各种因素的影响,停顿的时间长度不再与目标MIDI旋律中的停顿时间保持线性变化的关系.
同时不同哼唱的不同句子之间可能存在不同的线性变化参数.
基于这两种假设,可以考虑在旋律匹配的过程中,以哼唱旋律的停顿点为分界点,并且在MIDI旋律中寻找最合适的对应分段方案,对哼唱旋律和MIDI旋律之间的对应片段进行线性伸缩匹配,将能够获得更好的匹配效果.
3.
3.
3停顿点的估计如图3.
5中所示,停顿点在音高特征上的表现是在一定的时间段内不存在音高的信息,同时语音信号能量下降到最低的幅值.
对旋律中停顿点的估计,主要利用旋律中的静音片段,方法描述如下:(1)按照指定的静音长度阈值,从哼唱旋律中找出静音时间长度大于该阈值的位置,作为候选停顿点;(2)对上述提取的任意两停顿点,若两停顿点之间的时间间隔小于指定阈值,则对比两停顿点之间的静音长度,将静音长度小的一个去除;(3)经上述处理后得到最终的停顿点列表.
由于一般哼唱的小节都会保持一定的长度,在哼唱旋律中相距较近的两个停顿点,其中一个可能是非停顿点,因此需要去除这些停顿点.
在上述算法中,通过比较两个停顿点的静音长度,将长度较小的一个去除,这是因为静音长度大的比长度小的是真正的停顿点的可能性更大.
具体算法描述如下:输入:哼唱旋律的音符序列,最小静音长度,停顿点最小间距输出:停顿点位置音符列表算法:第3章分段信息40上述算法中的用于判断是否是静音音符,取中最后一次添加的音符,表示从中移除最后一次添加的音符.
通过上述算法,可以通过一遍运算得到所有的停顿点音符.
对于MIDI旋律,由于MIDI文件中已经手动标记了每小节的起点,也就是每个句子的起始点,因此可以直接获取.
如图3.
8展示了哼唱语音和其旋律的停顿点标注以及目标MIDI旋律的停顿点标注.
从图中可以看出,哼唱旋律与MIDI旋律在停顿点的音符时间比例与旋律的分段片段内的时间比例是明显不一致的.
这也就说明通过停顿点来切分然后进行分段匹配是一种合理的方案.

024681012x104-101采样点幅值哼唱语音02468101214-10010时间轴音符哼唱旋律的音符旋律10121416182022242628506070音符MIDI旋律的音符旋律片段图3.
8歌曲"冬季到台北来看雨"的前三句哼唱分段结果:根据停顿信息对哼唱及MIDI分段,哼唱旋律及目标MIDI旋律均被分成三个片段第3章分段信息413.
3.
4估计参数的确定在停顿点的估计算法中要用到两个参数,一个是最小静音间隔,另一个是两个停顿点的最小间隔.
对停顿点的估计应当尽量的准确,如果最小静音间隔设置太小,则提取的停顿点过多,伪停顿点多,对分段匹配不利,而如果设置过大,则提取的停顿点太少,分段匹配的效果不明显.
对于停顿点最小间隔也有类似结论.
如图3.
9与图3.
10所示,通过对100个哼唱语音进行标注停顿点,并进行统计来分析上述的静音间隔与停顿点间隔的分布.
图3.
5中,以0.
01秒为间隔,统计了每个时间段上停顿点的个数,而在图3.
10中,以0.
1秒为间隔,统计了相邻停顿点之间时间间隔在对应时间范围内的样本个数.
从统计结果可以看出,最小静音间隔的取值区间应当为较为合适,而相邻停顿点的最小间隔合适的取值范围是.
当然由于理论上不能确定哪一个参数值对于分段匹配来说是最优的,具体参数值可以在实验中根据情况确定.
01020304050607080901000510152025停顿点时间长度(以0.
01秒为单位)样本个数图3.
9不同时间长度的停顿点标注样本数分布第3章分段信息4201020304050607080901000510152025相邻停顿点间隔时间(以0.
1秒为单位)样本数图3.
10相邻停顿点间隔时间上标注样本的分布3.
4实验对启发式线性伸缩参数估计算法的描述见0节,本章中提出原有启发式估计算法由于起点单一可能无法得到全局最优参数,而极值点分段信息可用于增加启发式估计算法的候选起点来提高估计线性伸缩参数的准确性.
为验证启发式估计算法可能无法得到全局最优线性伸缩参数的情况,本文设计了如下实验:在进行线性伸缩参数估计时,使用两种方法.
第一种是启发式估计算法,第二种是遍历方法,遍历方法即对拉伸系数及音高偏移的所有可能值都计算线性伸缩匹配分数并取匹配分数最优时对应的线性伸缩参数作为最终估计值.
由于对哼唱旋律与目标MIDI旋律之间的线性伸缩参数估计越准确,则目标MIDI所在的排名越靠前,因此可以通过对所有候选进行参数估计后取最佳的线性伸缩匹配分数进行排名,以Top-N的准确率来衡量线性伸缩参数估计的准确性.
实验中所使用的数据库是355大小的哼唱数据库及106大小的MIDI数据库(数据库说明见0节).
实验结果如图3.
11所示,图中的横轴表示统计的Top-N中的不同N值的准确率,纵轴则表示对应的准确率.
蓝色所标注的柱状图即为启发式估计的结果,红色标注的为遍历式估计的结果.
图中遍历式估计算法得到的Top-10的准确率相比启发式估计算法由0.
85提高到了0.
88,Top-30对应的结果则从0.
92提高到0.
94,由此可以看出,通过使用遍历所有可能参数进行线性伸缩参数估计的方第3章分段信息43法能够使匹配结果中目标MIDI旋律所在的排名更靠前,对于与目标MIDI旋律之间的线性伸缩参数估计更为准确.
这也就说明启发式估计算法估计得到的线性伸缩参数并不一定是全局最优的线性伸缩参数.
由以上分析表明,使用基于极值点的分段信息增加启发式线性伸缩参数估计算法的候选起点,以提高线性伸缩参数估计的准确性,是可行的.
top-10top-20top-300.
80.
820.
840.
860.
880.
90.
920.
940.
960.
981top-N准确率启发式估计遍历式估计图3.
11启发式估计算法与遍历式估计算法的准确率对于基于停顿点的分段信息,可以用于对哼唱旋律进行分段的线性伸缩匹配,这种分段的线性伸缩匹配比LS、RA方法更有效的前提条件是,由停顿点分割的每一哼唱旋律片段与对应的目标MIDI旋律片段的线性伸缩参数是不一致的.
由停顿点分割的片段即为哼唱的句子,为了验证哼唱旋律中的每一句子与目标MIDI旋律片段之间具有不同的线性伸缩参数,本文设计了如下的实验:取一哼唱旋律以及对应的目标MIDI旋律,提取哼唱旋律的停顿点,对哼唱旋律中的每一停顿点,在目标MIDI旋律中找到对应的最佳分段点(手工),然后对哼唱旋律中的每一片段,计算与对应的目标MIDI旋律片段之间的最佳线性伸缩参数.
这里的最佳线性伸缩参数的获取是通过遍历的方式得到的,拉伸系数的所有候选值是区间[0.
5,2]中间隔为0.
05的所有点,如0.
5,0.
55,0.
6等.
假设两旋律片段的第一个音符音高相差为,则音高偏移的所有候选值是区间中间隔为1的所有值.
最终得到的哼唱旋律上每一片段的参数估计结果如图3.
12所示,图中的第3章分段信息44ratio表示两个片段估计得到的拉伸系数,shift为估计得到的音高偏移,红色的箭头表示对应片段的起点,MIDI旋律中的红竖线表示每一句的起始点位置.
图中旋律曲线提取了2个停顿点,将哼唱旋律分成3段,每个片段与目标MIDI旋律片段之间的拉伸系数分别为1.
0,0.
9,0.
95,音高偏移则保持一致,均为8.
从这个结果可以看出,哼唱旋律中的不同片段与目标MIDI的旋律片段之间达到最佳匹配时的线性伸缩参数是不同的.
因此可以说明,使用分段匹配的方法对不同的片段使用不同的线性伸缩参数进行匹配可以达到更好的匹配效果,说明了使用停顿点分段信息进行分段匹配的可行性.
图3.
12停顿点分割的每一片段的最优线性伸缩参数由上述两个实验说明了极值点分段信息应用于启发式估计及停顿点分段信息应用于精确匹配中的分段匹配是合理的.
3.
5本章小结本章介绍了基于极值点和停顿点的分段信息.
对于基于极值点的分段信息,由于其对齐效果较好,可用于在启发式线性伸缩参数估计时增加候选起点,提高参数估计的准确性.
而对于基于停顿点的分段信息,由于它反映了旋律的小节结构,而小节上哼唱旋律与目标MIDI旋律的线性伸缩参数保持稳定,小节切换时则不稳定,因此可以利用停顿点分段信息进行分段地线性伸缩匹配,达到更好的效果.
下一章将介绍利用基于极值点的分段信息提高启发式估计参数的准确性及利用基于停顿点的分段信息进行分段地线性伸缩匹配.
第4章基于分段信息的匹配算法45第4章基于分段信息的匹配算法4.
1本章引论在前文中介绍了基于极值点和基于停顿点的分段信息,基于这两种分段信息可以对旋律做不同的分段.
基于极值点的分段信息,描述了旋律中低音向高音变化再变为低音的转换过程以及变化的程度和时间位置等.
而基于停顿点的分段信息,其物理含义是休止符,通过分段信息描述了哼唱的旋律哼唱了多少个句子.

因此分段信息可以看作是旋律所表现出来的整体的、粗略的结构信息.
对于这些信息我们可以直接用来进行简单匹配,或者对旋律进行适当的调整、对齐,或者对精确匹配起到框架的作用.
简单匹配即单纯以分段信息计算哼唱旋律和MIDI旋律之间的差异,并去除一部分不可能的结果,又称为快速匹配,本文中我们不作考虑.
而精确匹配中的框架作用,则表示在哼唱旋律和MIDI旋律之间进行匹配时,利用分段信息来控制两段旋律之间的整体对齐,对于局部的两个旋律片段之间,通过适当的调整进行线性伸缩匹配.
本章主要研究利用分段信息来对旋律进行更有效的匹配,包括归一化和精确匹配,同时也会通过在实验数据集上进行算法的测试,来比较通过加入分段信息的匹配过程和其他匹配算法之间的区别.
本章的内容安排如下:第二节介绍基于极值点分段信息的启发式线性伸缩参数估计算法;第三节介绍利用分段信息的动态规划算法;第四节介绍利用分段信息的递归匹配算法;第五节给出实验的环境条件;第六节中对实验结果进行分析;最后在第七小节中对本章内容进行小结.

4.
2基于极值点分段信息的线性伸缩参数估计在哼唱旋律和MIDI旋律匹配前,需要对哼唱旋律和MIDI旋律进行初步的归一化操作,以增加后面进行精确匹配时匹配到目标旋律的概率.
归一化的过程是将MIDI旋律整体进行适当的线性拉伸及纵向平移,使得哼唱旋律与MIDI旋律之间的差异达到最小.
如图4.
1,图4.
2所示为哼唱旋律和MIDI旋律整体进行归一化前后的对齐结果,通过归一化,使得哼唱旋律与MIDI旋律有了基本的对齐结果,之后可以通过精确匹配的方法,对哼唱旋律和MIDI旋律进行更精确的对第4章基于分段信息的匹配算法46齐并计算相似度.
024681012141618-10010203040506070哼唱旋律MIDI旋律图4.
1哼唱旋律与MIDI旋律未标准化前的对齐结果051015-50510哼唱旋律MIDI旋律图4.
2哼唱旋律与MIDI旋律经过标准化后的对齐结果对旋律整体拉伸系数及音高偏移的估计本文采用了类似[3]中的算法,进行启发式的估计,所不同的是[3]中通过启发式方法进行多次的动态规划来计算精确匹配的分数,而本文则通过启发式进行多次的线性伸缩来估计最优的整体线性伸缩参数.
具体的估计算法描述如下:首先,初始化音高偏移为哼唱旋律和MIDI旋律的第一个音符的音高差值,系统首先估计拉伸系数的最佳值,并且限定估计的区间为:第4章基于分段信息的匹配算法47(1).
初始化拉伸系数:,并令这里所代表的含义是将区间分割成份,本文中设定为.
(2).
分别使用拉伸系数,,及三个参数计算哼唱旋律和数据库旋律间的距离(计算距离使用线性伸缩方法),假设计算的距离分别为.
(3).
如果或者已经到达区间的边界值,停止算法;否则转(4).
(4).
更新的值:如果,则;如果,则.
然后转第(2)步.
实际算法中,第(2)步计算得到的距离分数需要缓存起来,防止多次使用时造成重复计算.
通过上述步骤计算得到了最佳的拉伸系数.
再经过类似的搜索过程来估计最佳的音高偏移,不同的是估计音高偏移时的取值序列为,同时取值间隔为1,这里的表示从往两侧搜索的半径.
这样得到最优的拉伸系数和音高偏移后,就能对哼唱旋律和MIDI旋律进行归一化了.
上述的启发式估计过程,由于其启发式估计从一个单一的起点开始估计,而线性伸缩的匹配分数与其拉伸系数及音高偏移参数之间并非单调的变化关系.
因此在估计中可能找到局部的最优点,导致对参数的估计结果不够准确,这一点在0节中也已做证明.
可以通过增加启发式估计的候选起点来解决这一问题,从图3.
3中可以看出哼唱旋律中的极值点与目标旋律中的极值点对应非常整齐,哼唱旋律和目标MIDI旋律中从起点到对应的极值点之间的旋律保持一致,因此可以利用这一特点来增加启发式估计时的候选线性伸缩参数值.
增加候选起点的基本思想是:(1)对哼唱旋律中的每一极值点,在MIDI旋律中一定范围内搜索对应极值点.
(2)如果对找到对应极值点,则计算与之间的音高差,并加入启发式估计的候选音高偏移参数列表,计算相对哼唱旋律起点的时间与相对MIDI旋第4章基于分段信息的匹配算法48律起点的时间之比,作为拉伸系数候选增加到启发式估计候选拉伸系数列表中.

(3)对所有候选的拉伸系数,计算各自对应的线性伸缩匹配分数,并取分数最优者对应的拉伸系数作为启发式估计新的起点,对所有候选音高偏移系数作相同的处理.
(4)使用新的拉伸系数和音高偏移进行启发式估计.
具体算法描述如下:输入:哼唱旋律的极值点列表MIDI旋律的极值点列表哼唱旋律与MIDI旋律哼唱极值点搜索对应极值点时的搜索时间比例,比如[0.
5,2].
输出:极值点对的集合算法:其中表示判断极值点和是否满足时间比例限制.
最终可以将集合中每一极值点对的音高差和拉伸比例加入到启发式估计的候选起点中.
如图4.
3是一个增加候选起点的示例,图中哼唱旋律有3个极值点,每个极值点都找到了对应的极值点,因此总共会对启发式估计增加3组候选参数.
第4章基于分段信息的匹配算法49图4.
3利用极值点分段信息增加启发式估计候选起点4.
3基于停顿点分段信息的动态规划基于分段信息的动态规划,是指根据分段信息对哼唱旋律进行分段,并按逐个片段进行匹配,对于每一个片段,根据其时间信息在MIDI旋律中找到对应的旋律片段,与MIDI旋律片段进行线性伸缩匹配,同时对MIDI旋律片段的分段点可以进行适当调整,构造对MIDI旋律的多种分段方案,通过动态规划,从这些分段方案中找到最佳的分段方案,同时获取最佳匹配分数.
这种方法是在整体上进行动态规划,对片段而言则进行线性伸缩匹配.
这里的分段信息,即为前一章中所提出的基于停顿点的分段信息.
通过这种分段匹配的方式,保证在每个分段上进行线性伸缩匹配,使用独立的拉伸系数和音高偏移,同时利用动态规划对MIDI旋律的分段边界点进行调整得到的多种方案,并在这些方案中选择最佳的分段方案.
如图4.
4所示为一哼唱旋律与MIDI旋律匹配的情形,在哼唱旋律中检测到2个停顿点,将哼唱旋律分割成3段,图中的黄线表示停顿点的位置.
在进行匹配时,对哼唱旋律从左往右,对第一个停顿点即图中的第一分段点,在MIDI旋律中找到对应的分段点,并且计算对应划分分段的线性伸缩匹配分数,由此得到多种分段方案,接着对第二个分段点,也搜索MIDI中的候选分段点,计算匹配分数,假设对于图中的哼唱旋律的每个停顿点,在MIDI旋律中有3个对应的候选分段点,则对MIDI旋律可以有9种分段方法,动态规划的目的便是从这些分段方案中找出一种最好的分段方式.
第4章基于分段信息的匹配算法50图4.
4使用基于停顿点的分段信息进行动态规划匹配假设哼唱旋律的音符序列为,其中表示哼唱旋律中的第个音符.
MIDI旋律的音符序列为,其中表示MIDI旋律中的第个音符.
同时假设两段旋律之间已经估计过拉伸系数和音高偏移并进行了归一化.
则基于分段信息的动态规划算法可以描述如下:(4-1)上述公式中的表示哼唱旋律中最后一个停顿点对应的音符,而则表示停顿点音符在MIDI旋律中对应的候选分段点.
上述公式的实际含义是:对哼唱旋律中的最后一个停顿点音符,从其在MIDI旋律中的对应候选音符中找出一个音符,按照这两个音符分别对两段旋律划分成两段,然后对左边进行动态规划,对右边进行线性伸缩匹配.
最后从候选音符中找出一个使得两边匹配的分数和达到最小的候选音符作为最佳分段点.
在最终对旋律进行分段后进行线性伸缩匹配时,使用哼唱旋律的音高序列与MIDI旋律的音符序列进行匹配.
第4章基于分段信息的匹配算法514.
4基于停顿点分段信息的递归匹配基于停顿点分段信息的递归匹配方法和基于停顿点分段信息的动态规划方法类似,不同之处只是从另一个角度进行分段,二者的差别仅仅是按照不同的分段方式进行匹配.
递归匹配每次将哼唱旋律和MIDI旋律分别分割成2段,并分别对两侧再进行递归匹配,直到达到指定的递归次数,或不可再分,此时直接返回线性伸缩匹配的结果.
递归匹配的方法相比动态规划的匹配方法在对旋律整体的把握上具有优势,它克服了动态规划的方法在匹配路径过长时容易导致丢失最佳路径的缺点.

递归匹配的方法最终也是在音高序列上计算匹配分数.
设哼唱旋律的音高序列为,其中表示第帧的音高,表示哼唱旋律音高序列的总长度.
设候选的MIDI旋律片段为,其中表示第个音符的音高和时长,这里的时长以帧数表示,每帧窗宽与哼唱旋律的帧窗宽一致.
设哼唱旋律中的停顿点对MIDI旋律按时间对齐后找到候选分段点后可继续选取的提取候选距离该分段点的音符个数范围为,设为最大可递归的深度,一般设置为3或4.
则算法描述如下::第4章基于分段信息的匹配算法52上述算法中表示获取哼唱旋律中最接近中点的停顿点的位置,取停顿点的最后一帧位置,而则表示在MIDI旋律中按时间对齐后找到与位置对应的位置,表示使用线性伸缩的方法对音高序列和音符序列计算差异值,,亦同理.
则表示对子序列和继续使用参数再做层的递归调用.
在上述算法中,每一次对哼唱旋律取分段点时,取离中点最近的停顿点,如果递归过程中哼唱旋律已经没有停顿点可选,并且还没有达到递归的层次限制,则直接返回线性伸缩匹配的结果.
上述的递归过程中,不直接选择中点,而是选择离中点最近的停顿点.
这是因为一般在哼唱时,在句子内部变化哼唱的速度和音高等特征的概率相对比较小,在句子内部哼唱旋律相对于目标MIDI旋律的拉伸系数和音高偏移而言比较稳定,而在两个句子之间的换气点,则可能是两个句子之间线性伸缩参数变化的分界点,比如一个人哼唱了一个句子后,经过换气,哼唱的音调和速度就可能出现稍微的变动,这取决于每个人的哼唱水平.
总之对于哼唱而言,在句子之间变换速度和音高的可能性比在句子中间变化的可能性要大.
因此,这里在递归匹配中,我们使用停顿点作为分段的边界,而不是直接使用中点.
由算法可以看出,当递归到一定程度,可能旋律过短不再有任何停顿点分段信息,算法将直接进行线性伸缩匹配并返回对应分数.
因此,算法在最坏的情况下,没有任何分段点可分时,与线性伸缩的方法性能相同.
如图4.
5所示为一段哼唱旋律与MIDI旋律进行匹配的例子.
图中的哼唱旋律具有三个停顿点,将旋律分成4段,其中黄线标注的是停顿点的位置.
在递归匹配开始时,先对哼唱旋律和MIDI旋律做一遍线性伸缩匹配,再取哼唱旋律的中第4章基于分段信息的匹配算法53间停顿点,即图中的第一分段点,对哼唱旋律进行分段,对应的在MIDI旋律中找到多个候选分段点,将MIDI旋律分成对应的两段.
然后对哼唱旋律和MIDI旋律进行分段匹配,并保留最优的分段方案及结果,与直接线性伸缩的结果相比较,返回较好的结果.
在分段匹配过程中,需要计算两侧的递归匹配分数,同样也是按中间停顿点进行分段的方法,如图中的第二分段点和第三分段点,从而计算得到左右两侧的递归匹配分数.
图4.
5基于停顿点分段信息的递归匹配示例4.
5系统结构与实验数据提取特征并索引归并成音符按帧提取音高原始MIDI旋律特征数据库用户哼唱语音音高序列音符序列旋律归一化精确匹配初始候选歌曲最终候选歌曲第4章基于分段信息的匹配算法54图4.
6QBH系统的结构及匹配流程图本文使用的QBH系统的流程图如图4.
6所示,系统主要由四个模块组成:(1)MIDI旋律数据库模块MIDI旋律数据库模块的主要功能是提取MIDI文件的旋律信息并提取特征,对特征进行索引.
本文所使用的MIDI信息为XML格式的MIDI,这种MIDI可以是通过一款称为美得理简朴制作软件的工具录制而成,由软件录制的XML格式的MIDI信息再经过简化处理便得到最终的表示MIDI的XML文件.
XML文件的格式如下:0065.
mid_0115726.
68958327.
1291660.
4395831.
0135927.
12916627.
4989580.
3697920.
0…XML格式中的标签表示一个音符,标签表示MIDI中音符的音高,表示音符的起始时间,表示音符的结束时间,表示持续时间,表示是否为句子的起始点,当该值为1.
0时表示句子的起始点,第4章基于分段信息的匹配算法55否则为非起始点.
经过处理后的XML文件经过提取音符、归并音符、提取极值点并做索引等操作,便构成了MIDI数据库.
在匹配过程中,MIDI数据库的作用是生成用于匹配的候选MIDI旋律,由于数据库中的MIDI标注了句子的起始点,而且本文中我们假设哼唱查询语音都是从歌曲的某一句子开头开始哼唱的,因此数据库生成候选时,按照每首MIDI的句子起始点标注信息,对每一个句子起始点标注生成一个候选旋律,用于匹配.

这样生成的候选旋律只指定了旋律的起点,而终点没有指定.
(2)哼唱输入处理模块哼唱输入处理模块的主要功能是对哼唱输入的语音进行分帧,并估计每一帧的基频,经过转化后得到音高的序列,这个序列再经过一定的算法处理,归并成音符序列,由此得到两种序列用于匹配算法.
在本文中音高特征及音符特征的提取使用的是文献[36]中的算法,这种方法在0节中已做相关介绍,音高序列的提取使用一种改进的自相关算法提取得到,在音高提取之前,哼唱的语音通过基于统计的音符转化算法被解码成音符和静音的片段序列,和传统的自相关方法在全局检索基频峰值不同的是,这里的基频提取的算法只在解码得到的音符的局部区域内检索相关峰值,这种方法对于带噪声的输入语音具有更好的鲁棒性.
(3)旋律归一化模块在进行旋律的精确匹配前,由于哼唱旋律和数据库旋律间存在整体的速度及音高的不一致,需要对哼唱旋律与数据库旋律进行音高偏移和拉伸系数估计,以将数据库旋律规整为与哼唱旋律一致的速度及音高.
在本文的系统中,这一过程是通过一个启发式的搜索过程完成的,具体的算法请参考0.
尽管这一模块的主要功能是对数据库旋律进行规整,但在这一过程中已经对旋律整体做了线性伸缩匹配,因此可以使用此步中得到的最优匹配分数对初始候选集合进行排序,然后排除一部分不可能的结果.
因此这一模块同时也作为候选过滤模块使用.
(4)精确匹配模块精确匹配模块的主要功能是对旋律规整后剩余的候选旋律进行更精确的匹配第4章基于分段信息的匹配算法56分数计算,并按照最终得到的匹配分数排序,给出Top-20候选作为系统的输出结果.
精确匹配是本文的研究重点,具体算法已在0节,0节中介绍.
本文使用的哼唱测试数据库总共由355个哼唱语音组成,哼唱语音的格式为wav文件,哼唱语音以8kHZ的采样率16比特编码录制得到,总长度约为71分钟,平均每个哼唱语音的长度为12.
4秒.
数据库中的哼唱语音多数是以带歌词的形式哼唱的,哼唱者都是一般音乐水平的人,没有经过特殊的音乐知识训练.
这个数据库由中科院声学所中科信利实验室提供,曾经被作为2008年的MIREXQBHevaluation[45]中的一个标准测试集.
需要说明的是,所有的哼唱语音均是从歌曲中某一句子的开始处开始哼唱,一般大致哼唱3~4个句子,但是哼唱语音可能会在某一句子的中间结束.
本文实验中所使用的MIDI数据库有2个,一个总共包含5223首歌曲,该5223的数据库由我们自己使用录制工具录制得到.
数据库中包含106首为哼唱数据库的目标MIDI歌曲,MIDI数据库中所有的MIDI旋律都标注了MIDI旋律中的句子起始点,其中106首目标歌曲被标注成了2213段.
另一个数据库则是106首目标MIDI数据库,该数据库属于5223数据库的子集,主要用于测试算法的参数.
4.
6实验验证及结果分析4.
6.
1评价准则及各算法描述本文中提出利用极值点分段信息增加启发式估计线性伸缩参数的候选起点,同时提出利用停顿点分段信息进行动态规划以及递归匹配的方法,对此使用实验来验证算法的合理性.
在实验中,匹配的准确率可以使用Top-1及MRR来衡量,MRR是在MIREX的QBH评测中对系统准确率的一种标准的评价方式,可以通过目标MIDI所在的排名来计算,计算公式如下:(4-2)这里表示第个哼唱查询得到的返回结果中其目标MIDI所在排名的倒数,但如果目标MIDI不在前20的返回结果中,则对应的的值为0.
可以看出,的取值范围在内.
本文也实现了前面介绍的线性伸缩(LS)、动态规划(DP)、递归的线性伸缩(RA)第4章基于分段信息的匹配算法57的方法作为对比,表4.
1给出了各算法的简要介绍.
LS的方法直接进行整体的线性伸缩匹配,DP算法作为传统算法,研究得比较多,本文也实现作为参考,本文实现的动态规划算法是带约束的动态规划算法,即对满足要求的路径上的每一个点,对应的哼唱旋律和MIDI旋律之间的时间比必须在指定的范围内,一般限定的范围为[0.
5,2].
RA方法与本文中RALS的方法比较类似,区别是RA的方法直接以其中一旋律的中点进行分段匹配,而RALS的方法则是以最靠近中点的停顿点作为切分点进行分段匹配.
表4.
1各算法的介绍算法简写算法介绍LS线性伸缩算法,见0节中描述.
DP动态规划的方法,具体算法见0节.
RA递归匹配的方法,以中点切分递归匹配,见0节.
DPLS本文方法,基于停顿点分段信息的分段地线性伸缩匹配,同时用动态规划计算最佳分段方式.
RALS本文方法,基于停顿点分段信息的分段线性伸缩匹配,同时使用递归的方式获取最佳的分段方式.
DPLS_EP本文方法,在DPLS的基础上,基于极值点分段信息增加启发式估计线性伸缩参数的候选起点对旋律进行归一化.
RALS_EP本文方法,在RALS的基础上,基于极值点分段信息增加启发式估计线性伸缩参数的候选起点对旋律进行归一化.
4.
6.
2基于停顿点分段信息的精确匹配为了验证基于停顿点分段信息进行分段匹配的有效性,对0中列出的各算法,本文在前述355大小的哼唱数据库和5223大小的MIDI数据库上进行实验,系统的其他模块保持一致,精确匹配算法分别使用LS、DP、RA、DPLS以及RALS共6种算法.
测试得到各算法的准确率如表4.
2所示,图4.
7给出了更直观的图示.
从图4.
7的结果可以看出,LS、DP、RA、DPLS及RALS对应的准确率逐渐升高,Top-1的准确率基于停顿点分段信息的匹配算法最好性能相比LS、DP及RA算法分别提高了17%、14.
7%及4.
8%,而对应的MRR提高分别是15.
3%、12.
9%、4.
8%.
第4章基于分段信息的匹配算法58LSDPRADPLSRALS0.
50.
550.
60.
650.
70.
75TOP-1MRR图4.
7LS、DP、RA、DPLS、RALS算法的性能比较表4.
2各算法的实验结果LSDPRADPLSRALSTop-10.
5750.
5870.
6420.
6510.
673MRR0.
6080.
6210.
6690.
6820.
701由实验结果可知,DPLS和RALS的方法优于LS、DP及RA三种方法.
DP优于LS的方法,是因为LS的方法对哼唱旋律以整体的方式与MIDI旋律进行伸缩匹配,导致其估计得到的拉伸系数及音高偏移过于粗略.
而DP方法由于在实现时使用了一定的方法控制哼唱旋律与MIDI旋律之间匹配的速度比在一定的范围之内,因此比LS的方法更好.
而RA的方法较LS的方法不同的是,它使用递归的方式分段的估计并优化线性伸缩匹配,更好地把握了旋律的整体轮廓进行匹配.
DPLS及RALS均优于前面的三种算法,DPLS及RALS都限定了线性伸缩匹配的过程以句子为单位进行,并且对句子的边界作动态调整估计最佳的句子分段方式,两种算法优于LS、DP算法说明,基于分段信息进行分段地线性伸缩匹配算法更有效.
而DPLS、RALS优于RA的方法也说明,基于停顿点进行分段比基于中点进行分段的方法更合理.
另外,RALS优于DPLS表明递归匹配这种自顶向下的分段方式优于动态规划从前往后的分段方式.
本实验中的实验结果证明了停顿点分段信息在分段匹配中的有效性,也印证了本文在第3章中的分析.
第4章基于分段信息的匹配算法594.
6.
3候选分段点数对动态规划分段匹配的影响在DPLS算法中,对哼唱旋律中的每一个停顿点,需要在MIDI旋律中取多个候选分段点对MIDI旋律进行对应的分段.
候选的分段点数越多,算法消耗的时间就越长,在实验中每一次对哼唱旋律中的一个停顿点搜索了MIDI旋律的分段后,会对所有的分段方案得到的匹配分数进行排序,并保留前N个最好的分段结果,然后继续进行下一个停顿点搜索.
本文实验中考虑了候选分段点数对动态规划的影响,通过在前述355大小的哼唱数据库及5223大小的MIDI数据库上进行实验,得到的结果如表4.
3所示,表中的beam表示对每一个停顿点计算所有MIDI可能的分段方案后保留前beam个分段方案.
t则表示候选分段点的搜索范围,比如t=1则表示通过时间对齐在MIDI中找到与哼唱旋律中的停顿点对应的分段点后,将其左侧及右侧的1个音符作为候选分段点,因此总共的候选分段点数是3个.
TIME表示算法的平均响应时间.
由表中的结果可以看出,DPLS算法的准确率并非随候选分段点数的增加而提高,算法在t=2时的准确率优于t=1及t=4时的准确率,而计算时间则随着t的增大而增大.
算法准确率不随t增大而提高的原因是获取候选分段点时并未考虑分段的时间比率是否满足要求,在本文中,进行精确匹配前已经对MIDI旋律进行了归一化处理,进行了适当的拉伸.
当t过大时,会导致某些候选分段点切分的片段与哼唱旋律的对应片段之间的拉伸比例超出了合理的范围(本文认为[0.
5,2]为合理的拉伸比例),反而导致引入错误的匹配结果.
实验结果中t参数的变化导致的时间消耗的相对增加比例不大,这是因为在本文的系统中,主要的时间消耗集中在归一化旋律的处理过程.
由以上分析可知,在分段匹配过程中获取候选分段点时应当使得对应片段的拉伸比例满足在合理的范围内.
表4.
3候选分段点数对DPLS的影响beam=5,t=1beam=5,t=2beam=5,t=4Top-10.
58030.
62250.
6197MRR0.
61730.
65330.
6532TIME27.
4526.
6128.
05第4章基于分段信息的匹配算法604.
6.
4递归分段匹配准确率与递归层次的关系递归匹配的方法通过递归的方式逐步对旋律进行分段进行匹配而达到最优化的效果,随着递归层次的增大,计算的复杂度也相应的增大.
为研究递归匹配算法的准确率与递归的层次之间的关系,本文在上述的355大小的哼唱数据库以及106大小的MIDI数据库上进行实验,计算不同的递归层次下的算法性能,系统中其他模块的配置保持一致.
实验中我们仅测试了RA算法,RALS的方法与RA的分段方法基本一致,区别之处是RALS使用停顿点进行分段而RA使用中点进行分段.
实验结果如图4.
8和图4.
9所示.
在图4.
8中,本文使用了目标覆盖率这一指标,即Top-N准确率.
图中的横轴表示返回的前N个候选,纵轴表示对应的目标覆盖率.
从图中横轴上0到50之间的结果可以看出,递归层次在1、2、3时对应的结果差异比较大,而当递归层次超过3时,对应的目标覆盖率基本相差不大.
图4.
9则给出了递归层次为1-5时的Top-1与MRR随递归层次的变化情况,随着递归层次的增加,Top-1准确率不断上升,但上升的幅度逐渐趋于平缓,特别是从递归4层增加到递归5层时,准确率的提高已不明显.
上述的结果是由哼唱数据库的特点决定的,在实验使用的355大小的哼唱数据库中,几乎所有的哼唱语音哼唱的句子数都不超过5句,大部分是哼唱3句或4句.
因此当使用递归匹配的方法进行分段,分段超过一定次数时,再增加分段数则相当于对句子的片段再进行分段,而由于句子内部的线性伸缩参数是保持稳定的,因此分段匹配的效果不再明显,也导致准确率提高幅度变小.
图4.
8递归匹配方法的目标覆盖率与递归层次的关系第4章基于分段信息的匹配算法61图4.
9递归匹配方法的Top-1及MRR准确率与递归层次之间的关系4.
6.
5基于极值点的启发式线性伸缩参数估计算法为了证明基于极值点分段信息增加启发式估计算法中的候选起点的有效性,本文设计了一组对比实验.
对DPLS及RALS两种算法在精确匹配前的归一化操作,分别使用原有的启发式估计算法及新的启发式算法进行实验.
实验数据集使用前述的355大小哼唱数据库及5223大小的MIDI数据库.
实验结果如表4.
4所示,DPLS及RALS表示不使用基于极值点的分段信息时的系统性能,DPSL_EP及RALS_EP则表示对应的在启发式线性伸缩参数估计算法中使用基于极值点的分段信息增加候选起点后的系统性能.
使用RALS作为精确匹配算法时新的启发式估计算法使系统的Top-1和MRR准确率分别提高了1.
8%和3.
3%.
这是因为当使用基于极值点的分段信息增加了启发式估计候选起点后,有效地避免了在启发式估计线性伸缩参数的过程中陷入局部极值点.
在第3章的实验中已经证明了启发式估计算法陷入局部最优解是可能的,因此本实验中的结果也是合理的.
通过本实验证明了基于极值点的分段信息在估计线性伸缩参数中的有效性.

表4.
4新的启发式估计算法与原有估计算法对应系统性能对比DPLSRALSDPLS_EPRALS_EPTop-10.
6510.
6730.
6700.
685MRR0.
6820.
7010.
6930.
724第4章基于分段信息的匹配算法624.
6.
6实验小结在0节的实验中,基于停顿点分段信息的分段匹配算法相比传统的LS算法在Top-1上最高提高了17%,而在0节中,使用新的启发式估计算法后,还可以将RALS的Top-1提高1.
8%.
两个实验验证了本文提出方法的有效性.
同时同为分段匹配方法的RALS和RA方法的对比实验表明,在同等条件下,RALS相比RA在Top-1上从0.
642提高到0.
673,相对提高了4.
8%,证明了以停顿点进行分段匹配的方式比以旋律中点进行分段匹配的方式更有效.
因此,上述的实验充分证明了本文提出方法的合理性和有效性.
4.
7本章小结在本章中,为了验证基于极值点分段信息对于启发式线性伸缩参数估计的有效性以及基于停顿点的分段信息对于分段匹配的有效性.
本文设计了三种算法,基于极值点的分段信息增加启发式估计算法中的候选起点,同时利用基于停顿点的分段信息对旋律进行分段匹配,而分段匹配的过程使用了动态规划和递归匹配的方式来对与哼唱旋律对应的MIDI旋律的分段方式进行优化.
通过在355大小的哼唱数据库以及5223大小的MIDI数据库上进行实验.
实验结果表明,无论是利用基于极值点进行启发式线性伸缩参数估计的算法,还是基于停顿点分段信息进行动态规划或递归分段匹配的算法,均有利于旋律之间的匹配准确率的提高.

从而说明,基于极值点的分段信息与基于停顿点的分段信息是两种有效的分段信息,同时基于这两种分段信息的匹配算法也是更有效的匹配算法.
第5章结论与展望63第5章结论与展望哼唱检索相比传统基于描述信息的音乐检索方式更加人性化.
线性伸缩方法是用于计算哼唱检索中旋律匹配分数的一种较好的算法,针对线性伸缩方法的启发式估计算法起点单一的问题及旋律局部线性伸缩参数不精确的问题,本文提出了两种分段信息,一种是基于极值点的分段信息,另一种是基于停顿点的分段信息.
由于极值点位置在哼唱旋律和目标MIDI旋律之间的对应性,有利于估计线性伸缩的参数.
停顿点分段信息则反映了哼唱旋律中的小节(句子)信息,停顿点对应于乐谱中的休止符,按小节的方式进行分段匹配更为合理.

本文研究了利用极值点分段信息来提高对哼唱旋律与MIDI旋律之间线性伸缩参数估计的准确性,通过利用极值点分段信息增加启发式估计算法中的候选起点来防止估计算法陷入局部最优解.
本文同时也研究了对旋律基于停顿点分段信息进行分段匹配,由于旋律中的速度音高等描述旋律的重要参数在句子内部保持稳定,而在句子之间切换时易发生改变,因此以句子为单位进行的分段匹配更适用于基于线性伸缩的匹配方式.
更进一步的,本文还探讨了使用动态规划和递归匹配两种不同的方式来获取对MIDI旋律的最佳分段方式,通过搜索对MIDI旋律的最佳分段方式,将哼唱旋律和MIDI旋律进行一致的分段,进行分段匹配,达到最优的匹配结果.
通过在包含355个哼唱语音的哼唱数据库及包含5223首MIDI的旋律数据库上进行实验,实验结果表明,使用LS、DP、RA方法得到的Top-1准确率分别为0.
575、0.
587及0.
642,对应的MRR分别为0.
608、0.
621及0.
669,而在最好的情况下,基于停顿点分段信息的分段匹配算法比LS、DP、RA算法在Top-1上分别提高17%、14.
7%和4.
8%,相应的MRR提高分别为15.
3%、12.
9%和4.
8%.
另外,使用RALS作为精确匹配算法时的Top-1和MRR准确率分别为0.
673和0.
701,使用新的启发式估计算法后系统的Top-1和MRR准确率分别提高了1.
8%和3.
3%.
RALS和RA方法的比较也说明以停顿点作为分段点进行分段匹配的方式比直接以中点进行分段的分段匹配方法效果更好.
另外,在基于停顿点的分段匹配方式中,使用递归的方式进行分段匹配比使用动态规划的效果好,说明了递归的方式对整体匹配的把握比动态规划的方法要好.
本文提出的RALS的方法相比传统的LS方法在Top-1上提高了17%.
相比第5章结论与展望64传统方法,本文方法的优点是既利用了启发式估计快速的特点,又通过增加候选起点保证了线性伸缩参数估计的准确性.
本文方法的另一优点是通过利用停顿点对旋律进行合理地分段匹配,既解决了传统方法中局部线性伸缩参数不准确的问题,又使得对局部参数的估计达到最优.
实验结果验证了极值点分段信息在线性伸缩参数估计中的有效性以及停顿点分段信息在分段匹配中的有效性,同时也说明了基于停顿点分段信息的分段匹配方法是更有效的旋律匹配算法.
但本文的研究工作仍然有很多需要改进的地方,主要包括:(1)极值点分段信息的提取对于基于极值点的分段信息,其提取的结果会受到旋律不稳定因素的影响,由于旋律的不稳定因素可能导致提取的特征中包含伪最高点或者去除了不该去除的极值点,因此在本文中仅用来增加启发式估计线性伸缩参数的候选点.
但极值点的信息反映了旋律整体的变化趋势,是描述旋律结构很重要的信息,如果同时利用停顿点和极值点的信息来对旋律进行对齐,应该可以达到更好的效果.
(2)停顿点的估计本文中的基于停顿点的分段信息使用了按最小静音间隔提取并进行归并的方法.
最小静音间隔是绝对值,对不同的人,其哼唱的方式有所不同,自然也会导致这种按时间间隔提取的方式受到不同的影响.
对于哼唱音色较好,哼唱的句子比较连续,同时句子之间的换气间隔比较明显的情况下,这种提取方式能够获得准确的分段信息.
但假如哼唱者的声音沙哑或者哼唱时因无法发颤音等情况导致句子内部也出现静音时,这种方式提取的停顿点就多于实际的停顿点数量,从而会导致对匹配过程造成不利的影响.
因此,如何更好地提取哼唱过程中的停顿信息,还需要进一步的研究.
(3)停顿点信息的利用停顿点的信息在旋律中实际上代表了旋律小节的结束,是一类重要的参考点.
在旋律的匹配过程中,也可以利用此类特征点做其他的匹配.
比如利用停顿点附近的旋律特征对候选进行快速过滤,或者直接根据哼唱旋律中的停顿点第5章结论与展望65位置信息对候选进行快速过滤.
再者,也可以考虑对停顿点分割的片段进行特征提取,并进行索引,通过索引特征达到快速匹配的目的,这种方式类似于乐纹的方法.
参考文献66参考文献[1]AsifGhias,JonathanLogan,DavidChamberlin,etal.
QueryByHumming--MusicalInformationRetrievalinanAudioDatabasein:ACMMultimedia95-ElectronicProceedings.
1995.
[2]RodgerJ.
McNab,LloydA.
Smith,IanH.
Witten,etal.
TuneRetrievalintheMultimediaLibrary.
MultimediaToolsandApplications,2000,10(2-3).
[3]Jyh-ShingRogerJang,M.
-Y.
Gao.
AQuery-by-SingingSystembasedonDynamicProgramming.
in:InternationalWorkshoponIntelligentSystemsResolutions(the8thBellmanContinuum).
2000.
85~89.
[4]Jyh-ShingRogerJang,Hong-RuLee,M.
-Y.
Kao.
Content-basedMusicRetrievalUsingLinearScalingandBranch-and-BoundTreesearch.
in:Proc.
ofIEEEInternationalConferenceonMultimediaandExpo.
2001.
[5]Jyh-ShingRogerJang,H.
-R.
Lee.
SuperMBox:AnEfficient/EffectiveContent-basedMusicRetrievalSystem1.
in:ProceedingsoftheNinthACMInternationalConferenceonMultimedia.
2001.
401~410.
[6]李扬,吴亚栋,刘宝龙.
一种新的近似旋律匹配方法及其在哼唱检索中的应用.
计算机研究与发展,2003,40(11).
[7]JonahShifrin,W.
Birmingham.
EffectivenessofHMM-basedRetrievalonLargeDatabases.
in:Proc.
ofInternationalSymposiumofMusicInformationRetrieval(ISMIR).
2003.
[8]JonahShifrin,BryanPardo,ColinMeek,etal.
HMM-BasedMusicalQueryRetrieval.
in:JointConferenceonDigitalLibraries.
2002.
[9]陈知困,徐明,黄云森.
一种高效的基于CHMM的哼唱式旋律检索方法.
见:第三届和谐人机环境联合学术会议(HHME2007).
2007.
[10]ErdemUnal,ElaineChew,PanayiotisG.
Georgiou,etal.
ChallengingUncertaintyinQuerybyHummingSystems:AFingerprintingApproach.
in:Proceedingsofthe6thACMSIGMMinternationalworkshoponMultimediainformationretrieval.
2004.
113~118.
[11]GadM.
Landau,U.
Vishkin.
Efficientstringmatchingwithkmismatches.
TheoreticalComputerScience,1986,43(2-3):239~249.
[12]R.
A.
Baesa-Yates,C.
H.
Perleberg.
Fastandpracticalapproximatestringmatching.
in:CombinatorialPatternMatching,ThirdAnnualSymposium.
1992.
185~192.
参考文献67[13]Z.
Galil,R.
Giancarlo.
Improvedstringmatchingwithkmismatches.
ACMSIGACTNews,1986,17(4):52~54.
[14]RicardoA.
Baeza-Yates,G.
H.
Gonnet.
FastStringMatchingwithMismatches.
InformationandComputation,1994,108(2):187~199.
[15]RodgerJ.
McNab,LloydA.
Smith,IanH.
Witten,etal.
TowardstheDigitalMusicLibrary:TuneRetrievalfromAcousticInput.
in:Proc.
ACMDigitalLibraries.
1996.
11~18.
[16]LutzPrechelt,R.
Typke.
AnInterfaceforMelodyInput.
ACMTransactionsonComputer-HumanInteraction,1998,8(2):133~149.
[17]D.
Parsons.
Thedirectoryoftunesandmusicalthemes.
SpencerBrown,Cambridge,1975.
[18]YunyueZhu,D.
Shasha.
WarpingIndexeswithEnvelopeTransformsforQuerybyHumming.
in:Proceedingsofthe2003ACMSIGMODInternationalConferenceonManagementofData.
2003.
[19]RogerB.
Dannenberg,N.
Hu.
UNDERSTANDINGSEARCHPERFORMANCEINQUERY-BY-HUMMINGSYSTEMS.
in:InternationalConferenceonMusicInformationRetrieval(ISMIR).
2004.
205~211.
[20]RogerB.
Dannenberg,WilliamP.
Birmingham,GeorgeTzanetakis,etal.
TheMUSARTTestbedforQuery-By-HummingEvaluation.
ComputerMusicJournal,2004,28(2):34~48.
[21]王小凤,周明全,耿国华,等.
一个使用歌谱信息进行哼唱检索的系统.
计算机辅助设计与图形学学报,2007,19(7).
[22]魏维,罗凯,谢青松.
一种提高哼唱匹配效果的新算法.
黑龙江电子技术,2007(7).

[23]马志欣,付少锋,周利华.
哼唱检索中一种新的旋律模糊匹配方法.
西安电子科技大学学报,2006.
[24]王玮,蔡莲红,杨洪涛.
基于内容的音乐检索研究.
见:第十一届全国多媒体技术学术会议.
2002.
[25]包先春,戴礼荣.
哼唱检索系统中一种有效的旋律匹配方法.
计算机仿真,2008.