（计算机软件与理论专业论文）在线音乐哼唱检索系统的算法与实现.pdf

生兰塑型堂墨堡主堂焦丝兰 垄苎童堡堕堡垒墨墨丝盟兰鲨i ! ! ! 翌 在线音乐哼唱检索系统的算法与实现 专业： 硕士生： 指导教师 计算机软件与理论 王鹤娴 李才伟 摘要 随着计算机网络技术的发展，互联网成为人们获取音乐资讯的一种越来越 重要的媒体。这种趋势对音乐信息检索提出了更高的要求。现有的网上音乐检 索局限于分类浏览和基于文字的查找功能。哼唱检索可以帮助用户通过哼唱旋 律的片断，在大规模的音乐数据库中找到想要的乐曲。这种新型的人机接口， 对于在互联网上实现基于内容的音乐检索有着巨大的现实意义。 近期对哼唱检索研究主要集中在大型乐曲库的检索上，随着乐曲库规模的 不断扩大，越来越多的人开始研究分层、分级的高效检索方法，除了算法的命 中率，算法的效率也成为我们追求的目标之一。本文提出了一种高效率的近似 旋律匹配的新方法“走势峰值匹配算法”，虽然因为精度不够，不能作为精 确匹配的算法，但因为效率高，可以作为过滤算法使用。试验结果证明了算法 的高效性和有效性。走势峰值匹配算法所使用的旋律表示方法是本文中提出的 一种新的旋律表示方法，即用( 旋律走势峰值，旋律走势时间比例) 的二元组 序列的形式表示旋律，除了达到减少检索信息量，提高检索算法效率的效果外， 还可以很好地容忍相同旋律在时间轴上的缩放变化。 本文还在走势峰值匹配算法和已有的线性对齐匹配算法的基础上采用分级 高效检索的方式，在，n e t 平台，用c 群和c + + 语言以及w e bs e r v i c e 技术实现了 一个针对m i d i 乐曲库的在线音乐哼唱检索系统的原型，可以做为实际应用中 针对w a y 、r a p 3 等格式构成的乐曲库的在线音乐哼唱检索系统的一个组成部分。 关键词：基于内容的音乐检索；哼唱检索：近似旋律匹配 生墨垫型兰墨堡圭堂焦丝壅 垄丝童堡堕堡垒室墨竺塑苎鲨兰塞翌 a l g o r i t h m a n d i m p l e m e n t a t i o n o fo n l i n e m u s i c q u e r y - b y - - h u m m i n gs y s t e m m a j o r ：c o m p u t e r s o f t w a r ea n d t h e o r y n a m e ：h e x i a n w a n g s u p e r v i s e r ：c a i w e il i a b s t r a c t a st h e r a p i dg r o w t ho fi n t e m e t ，t h en e t w o r kb e c o m e sam o r ea n dm o r e i m p o r t a n tc h a r m e lv i aw h i c ht h ep u b l i co b t a i n sm u s i ci n f o r m a t i o n t h ec u r r e n t o n l i n em u s i cs e a r c hs y s t e m sa r el i m i t e dt oc a t e g o r i z i n ga n dt e x tb a s e ds e a r c h i n g q u e r yb yh u m m i n g ，a sab r a n d - n e wm u s i cr e t r i e v a lm e t h o d ，c a nh e l pu s e r st ol o c a t e t h ew a n t e d p i e c ew i t h i nah u g em u s i cr e p o s i t o r yb ys i m p l ys i n gs e v e r a lt o n e s b e i n g an e ws t y l eo fh u m a nm a c h i n ei n t e r f a c e ，t h eq u e r yb yh u m m i n g t e c h n o l o g yh a s i m p o r t a n ta n dp r a c t i c a lm e a n i n g st oc o n t e n tb a s e dm u s i cr e t r i e v a lo n l i n e r e c e n t l y , t h er e s e a r c ho nq u e r yb yh u m m i n gc o n c e n t r a t eo nr e u i e v eo nl a r g e s c a l em u s i cd a t a b a s e a st h es c a l eo fm u s i cd a t a b a s ei s g e e i n gl a r g e ra n dl a r g e r , m o r ea n dm o r ep e o p l es t a r t e dt h er e s e a r c ho nh i e r a r c h i c a le f f i c i e n tq u e r ym e t h o d a s i d ef r o mt h es u c c e s sr a t e ，aa l g o r i t h m se f f i c i e n c yb e c o m eo n eo f o u ra i m s t h i s a r t i c l er e p r e s e n t sa h i g h - e f f i c i e n c yn e wm e t h o df o ra p p r o x i m a t em e l o d ym a t c h i n g ， c a l l e d ”t e n d e n c yp e a km a t c h i n g ”，a l t h o u g hi t sp r e c i s i o ni sn o th i g he n o u g h ，w h i c h m a d ei tn o tag o o da l g o r i t h mf o ra c c u r a t em a t c h i n g ，b u ti s s t i l lc a nb eu s e da sa t i l t i n gm e t h o di nh i e r a r c h i c a lm a t c h i n gb e c a u s eo fi t sh i g he f f i c i e n c y t h e s ew e r e p r o v e di n o u r e x p e r i m e n t s t e n d e n c yp e a km a t c h i n gm e t h o du s e s an e wm u s i c r e p r e s e n t a t i o nm e t h o dw h i c hi sp r e s e n t e di n t h i sa r t i c l e t h a ti st o r e p r e s e n tt h e m e l o d yb y as e r i a lo f p a i r sa s ( p i t c h t e n d e n c yp e a k ，p i t c ht e n d e n c yp r o p o r t i o n ) t h i s r e p r e s e n t a t i o nn o to n l yr a i s e st h ee f f i c i e n c yo fr e t r i e v eb y r e d u c i n gt h eq u a n t i t yo f i n f o r m a t i o ni ns e a r c h i n g ，b u ta l s ec a l ls t a n dt h e z o o m i n go f m e l o d ya l o n gt i m e a x i s t h i sa r t i c l ea l s or e p r e s e n t sao n l i n em u s i c q u e r y b y - h u m m i n gs y s t e mp r o t o t y p e u s i n g n e tp l a t f o r m ，c # a n dc + + l a n g u a g e ，w e bs e r v i c e t h es y s t e mb a s e so na h i e r a r c h i c a lq u e r ym e t h o du s i n gb o t h t e n d e n c yp e a km a t c h i n gm e t h o da n dak n o w n 计算机科学系硕士学位论文在线音乐哼唱检索系统的算法与实现 m e t h o dc a l l e dl i n e a ra l i g n m e n tm a t c h i n gm e t h o d t h es y s t e mu s e sam u s i cd a t a b a s e o f m i d i f i l e s ，n o tv e r yc o n v i n i e n ti nu s i n g ，b u ti tc a nb ep a r to f s y s t e m s u s i n g m u s i c d a b b l eo f ，a vo rm p 3f i l e s k e y w o r d s ：c o m e n t - b a s e dm u s i cr e t r i e v a l ，q u e r yb yh u m m i n g ，a p p r o x i m a t e m e l o d ym a t c h i n g i i l 计算机科学系硕士学位论文 在线音乐哼唱检索系统的算法与实现 第一章引言 随着数字化多媒体数据的飞速增长，对于这些资料的快速查找成为一个非 常迫切的需求。因此，基于内容的多媒体信息检索成为一个热门的研究领域， 它是对基于文本描述的检索方法的一个十分有效的补充。大多数已有的研究都 着眼于图像和视频检索，基于内容的音频检索( c b m r ) 是近年才兴起的一个 分支。哼唱检索( q u e r y b y h u m m i n g ，以下简称为q b h ) 系统是基于内容的大 型音乐数据库检索系统中的一种。用户利用该系统，通过对着麦克风哼唱歌曲 的一段旋律，便可以从音乐数据库中库中检索到对应的歌曲或者音乐片断。 这种方法相对于人们所熟悉的用歌曲的名称、演唱者、出版时间等检索音 乐的方法更加方便、自然。可以想象，“用哼唱检索音乐”具有极其广泛的应用 前景，普通的用户可以方便地从网上找到自己喜欢的音乐，在k t v 人们只要 哼唱就可点歌而不需要用歌本，音乐专业人士可以方便地判断他的创作是否具 有新意，版权管理部门可以方便地查出一首音乐作品是否是新的。人们梦想计 算机能够理解音乐，“用哼唱检索音乐”是向这个方向的有益探索。 我们的研究目的之一就是要开发一个可以进行在线音乐哼唱检索的q b h 系统原型。通过互联网，用户只需打开浏览器，对麦克风哼唱若干个音符，系 统就能够在数字乐曲库中匹配，查找出旋律一致的乐曲。从而即便用户不知道 乐曲的名称、作者或者其他文字信息，只要他能记得一小段旋律并哼唱出来， 系统还是能够帮助他找到想要的歌曲。 第二章哼唱检索系统综述 基于内容的音乐检索是基于内容的多媒体信息检索的一个分支。哼唱检索 是一种基于内容的音乐检索系统，允许用户通过哼唱的形式来寻找所需的歌曲。 从而，为了找到一首歌曲，记住曲名或者歌手名不再是必需的。用户只要能回 忆起其中的片断旋律，并用麦克风哼唱出来，检索系统就能找到所要的歌曲。 2 1 已有研究成果 a s i fg h i a s 等人基于哼唱来检索乐曲的研究被公认为是已知最早的。文【1 】 于1 9 9 5 年开创性地提出了哼唱检索的系统架构，详尽讨论和比较了各种音高提 取技术( 时域上和频域上) ，并提出音高轮廓( p i t c hc o n t o u r ) 的概念，把旋律的音 高起伏表示成( u ，d ，s ) 的符号序列，不考虑节奏特征。匹配的时候才用文【2 中经典的快速近似匹配法，在符号级别上比较序列的相似性。g h i a s 的实验乐 曲库仅包含1 8 3 首乐曲，但其检索命中率接近1 0 0 。 近期的一些研究把重心放在大型乐曲库的检索上，主要的突破是节奏信息 在检索中的使用，以及分层、分级的高效检索方法。 文 3 中，l i el u 等用( p i t c hc o n t o u r , p i t c hi n t e r v a l ，d u r a t i o n ) ，即( 音高轮廓， 音高差，音符长度) 三元组为单位表示旋律，并提出了一种两级匹配方法。对 输入音频做特征提取，分析能量曲线做音符切分，计算过零函数和自相关函数 提取音高，最终转换成三元组序列。匹配的过程中，先用d p 算法粗略比较p i t c h c o n t o u r ，对于误差小于一定阈值的旋律，再用更精确的算法比较对应的p i t c h i n t e r v a l 和d u r a t i o n 。他们对用户的哼唱发音没有限制，在1 0 0 0 首乐曲中检索， 获得了7 4 的前三位命中率。虽然他们的实验结果不十分令人满意，但这种分 级匹配提高系统性能的想法是有创意的。 文 4 】中，j y h - s i t i n g r o g e r j a n g 等采用每1 1 6 秒一个音高值方法表示旋律。 匹配前使用m e a l l a d j u s t m e n tm e t h o d 使输入和模板的音高在平均值上对齐。匹 配时，用一种称为h f m ( h i e r a r c h i c a lf i l t e r i n gm e m o d ，分级过滤算法) 的分层 匹配算法，先采用过滤算法筛去8 0 左右的候选乐曲，然后对剩下的用d t w ( d y n a m i c t i m ew a r p i n g ) 精确匹配。每1 1 6 秒一个音高值的方法使得他们的 系统对哼唱发音没有限制，但也同时导致了音高矢量的长度大增，带来匹配速 度的不足，要求用户必须从乐曲的开头哼唱。在规模为3 0 0 0 首的乐曲库中检索， 获得了6 8 的前三位命中率。 n a o k o k o s u g i 等也于文 5 】中提出了一种同时考虑音高和节奏，以适应大型 2 计算机科学系硕士学位论文 在线音乐哼唱检索系统的算法与实现 乐曲库检索的方法。他们的系统，称为s o u n d c o m p a s s ，可以在一秒钟内检索 1 0 0 0 0 首乐曲，并取得了7 5 的前五位命中率。但是，用户必须在一个节拍器 伴奏下哼唱，这常常是很不方便的。 除了上述的基于符号匹配的检索方案，文【6 中0m a i d l n 等还提出一种基 于音高轮廓几何相似性的匹配方法，大致思路是根据输入音频提取音高，并按 时间的变化画出音高曲线，而后在二维空间中比较两条音高曲线的几何相似性。 通过在音高轴上的平移对齐输入哼唱和旋律模板的平均音高，再通过计算夹在 两条曲线间的面积，判断两段旋律的匹配相似程度，面积越小相似度越高。 文【7 中，c f r a n c u 等又对这种几何相似性匹配方法加以改善，在比较前允 许对音高曲线在时间轴上作线性的延展，从而使得匹配不同节奏的相同旋律成 为可能。他们在研究中还提出一种为乐曲作索引的设想，大致上是一种层进式 的分类思想，可惜在论文中没有十分详细地阐述。他们的系统经过简单的性能 试验，在1 0 0 0 0 首乐曲中检索2 0 个哼唱片段，据称在每一次检索都成功定位到 正确乐曲的多个版本，且大多数情况下误判都小于三首。从数字上看，这样的 结果非常喜人。然而由于不同研究的实验样本集合都不同，缺乏一些可比性。 文【8 忡，李扬等提出了一种近似旋律匹配( a p p r o x i m a t em e l o d ym a t c h i n g ) 的新方法线性对齐匹配法( l i n e a ra l i g n m e n tm a t c h i n g ，以下简称l a m 算 法) ，该算法并非基于近似符号串匹配、统计模型或者特征空间，而是根据相近 旋律的音高轮廓在几何上的相似性，将音高和节奏特征一并考虑所设计而成的 全新算法。通过实验检验该算法的有效性，在含有3 8 6 4 首乐曲的搜索空问中， 检索6 2 段人声哼唱，线性对齐匹配法取得了9 0 3 的前三位命中率，相比传统 的近似符号匹配算法高出1 1 以上。是命中率极高的一种算法。 现有的大多数系统都使用近似字符串的匹配算法比较旋律，但也有另一些 不同的方法。w i l l i a mr a n d 等于文【9 】提出使用m a r k o v 统计模型比较旋律的相 似性，由于是对频率符号建模，他们的方法对音高不准比较敏感，但能较好地 容忍遗漏音符和节奏上的哼唱误差。文 1 0 】中，冯雅中等在对音乐库做了统计 分析的基础上，总结了一些启发式规则，帮助对哼唱输入进行基音检测、音符 分割，哼唱输入表达为音高轮廓图和节奏，音乐库中的音乐按音乐的节奏类型 分为不同的节奏区域，并从每首音乐中抽取旋律轮廓图和节奏信息，用递归神 经网络记忆旋律轮廓，音乐库的索引是神经网络的权值矩阵，将哼唱输入与音 乐库中的音乐匹配的过程就是计算神经网络的输出过程。他们在含有1 2 0 0 首乐 曲的搜索空间取得了6 5 的前三位命中率。虽然结果不能令人满意，但利用神 经网络进行音乐匹配也是一项创举。 计算机科学系硕士学位论文 在线音乐哼唱检索系统的算法与实现 2 2 核心问题和关键技术 从已有的研究中可以看出，哼唱作为输入的基于内容的音乐检索的核心问 题和关键技术主要有以下三项： 旋律的表示形式：提取得到的特征值以怎样的数据结构存储。 旋律的特征提取：特征提取是指在输入音频经过基本信号处理后，如 何从中量化和提取描述了旋律特征的参数值( 如音高、节奏等) 。 旋律的匹配算法：如何评价和计算旋律之间的相似性。 其中旋律的匹配算法的研究尤为重要。 围绕着如何解决这三个核心问题，已有的研究提出了多种不同的方案，每 一种方案都涉及了一系列关键技术。其中有些技术相对更通用一些，比如语音 信号处理，在所有的方案中都有出现，而另一些技术则针对性比较强，往往是 某种方案所特有的。 本文在旋律的表示形式和旋律的匹配算法这两个核心问题上均作出了一定 的创新。 4 第三章哼唱检索引擎及核心技术 本章主要介绍本文中哼唱检索引擎的工作流程以及流程中各个步骤的详细 过程，重点是走势峰值匹配算法的介绍。 3 1 哼唱检索引擎概述 本文中采用的哼唱检索系统引擎的工作流程如图3 - l 所示： m i d i 数据库 哼唱 输入 按相似度 由高到底 排列的歌 曲列表 旋律信息提取 翮陌 切分r _ 1 提取 音符序列 旋律信息 旋律匹配 鬣矛卜靥 旋律信息提取 主獬道hm 信i n 息i 提事取f , ：判断r 信息提取 音符序列 旋律信息 图3 - 1 哼唱检索引擎的工作流程 我们的实验是在一般噪音条件下进行的，使用普通的麦克风录制8 0 0 0h z 1 6b i t 单声道的哼唱音频，录音时可能的噪音包括：硬件设备( 例如麦克风、计 算机) 产生的噪音、环境噪音和呼吸噪音( 人们在唱歌时常常有换气的动作) 等。 之所以选用8 0 0 0h z 的采样率来录制哼唱旋律，是基于以下几点原因： 1 根据文 1 0 】中的启发式规则，人们所能哼唱的声音的范围在8 0 8 0 0h z 之间，即使是语音，范围也在4 0 h z 4 0 0 0 h z 之间，根据奈奎斯特采样 定律，8 0 0 0h z 的采样率已经足够。 2 因为是在线检索系统，w a v 文件要通过网络传输，过高的采样率将使文 件过大，影响系统性能。 计算机科学系硕士学位论文 在线音乐哼唱检索系统的算法与实现 哼唱输入的旋律信息提取模块的主要任务是对输入音频做一系列时域和频 域上的信号处理，从中提取出旋律特征。包括组成旋律的每个音符的频率和节奏， 最后转化成为匹配算法要求的音符序列。因为本文中的哼唱检索引擎要用到文 8 中的l a m 算法，该算法要求用户以“d a d a d a ”声哼唱，利用闭口声母在音符 之间留出低能量间隔，使得系统可以通过跟踪能量随时间变化的情况，确定每个 音符的边界，比较容易得出准确的音符频率和长度。因此在本文第四章中的开放 式哼唱检索系统中，我们也要求用户用“d a d a d a ”声哼唱。基音提取上， 我们采用了加窗、快速傅立叶变换( f f t ) 、去除嗓音等手段，确定每个音符的音 高。 要提取音乐的旋律特征以构成可供检索的旋律轮廓，首先必须确定使用什 么格式的音乐文件作为旋律提取的数据源。目前常用的计算机音乐文件格式有多 种，每种格式能支持的音频参数和使用环境各不相同。根据音频文件记录声音的 原理，通常可以分为三类：声音文件、m i d i 文件和模块文件。声音文件( w s v 、 a i f f 、a u 、m p 3 、r a 、w m a 等) 指的是直接记录了通过对真实声音的模拟波形进 行二进制采样而得到的数据，是对声音的真实反映。这样存储声音信息所产生的 声音文件是相当庞大的。m i d i 文件( m i d 、r m i 等) 记录的是音乐演奏指令序列，说 明了在什么时间、用什么乐器演奏什么音符，及如何演奏，并不包含真实声音的 数据，所以文件尺寸要比声音文件小得多。模块文件( m o d 、s 3 m 、x m 、m t m 、f a r 、 k a r 、i t 等) 同时具有m i d i 与声音文件的共同特性，也就是说模块文件中既包括 如何演奏乐器的指令，又保存了声音信号的采样数据。这三种类型文件的特点各 不相同，文 1 1 中根据三种音频文件格式的特点，从提取旋律的角度所注重的精 确度、方便性、通用性进行了如下分析： 1 精确度。音符包含音高、音强和音长三个特征。m i d i 文件和模块文件里 对于每一个音符的这三个特征都有完全量化的准确描述，而声音文件则 是记录了真实声音的波形采样数据，要从中提取出比较精确的旋律特征 就相对困难，就精确度而言，肯定不如另外两种文件格式。 2 方便性。m i d i 文件和模块文件记录了一系列演奏音乐的指令，只要了解 了文件的格式，就可以方便地将所需要的旋律特征提取出来。从编程的 角度来看，其处理过程并不复杂。而对于声音文件来说，必须进行特定 的数字音频处理，整个过程的难度和复杂程度要大大高于处理另外两种 格式。 3 通用性。声音文件和m i d i 文件通用性很好，适用于各种平台，而且相互 之间的转换也不难，有很多专门的音频文件格式转换工具可以使用。模 块文件曾经在网上风行一时，但随着m p 3 等格式的兴起，模块文件已经 6 计算机科学系硕士学位论文 在线音乐哼唱检索系统的算法与实现 很少使用了。而且模块文件只是一个总称，根据具体的编码方法又有 m o d 、s 3 m 、x m 、m t m 、f a r 、k a r 、“等多种不同格式，耍提取旋律必须针 对不同的编码格式作相应的处理。 从上面的分析可以看出，从声音文件中提取旋律特征处理过程复杂，难度高， 精确度不如另外两种格式；模块文件通用性很差，编码格式多；与它们相比，m i d i 文件显然更适合作为提取音乐旋律的数据源。 3 2m i d i 文件的旋律信息提取 m i d i 文件由多个音轨( m i d it r a c k ) 组成，通常每个音轨里的音符都占用 同一个通道( c h a n n e l ) ，但也有些情况下，一个音轨里的音符会占用多个通道。 由此可见，m i d i 文件的主旋律表现为某一个音轨中的某一个通道的形式。因 为用户哼唱的旋律通常都是主旋律，因此首先，我们要从m i d i 文件中提取包 含了主旋律信息的某一音轨中的某一通道( 以下简称为主通道) 。由于m i d i 文 件中并没有规定通道的使用规则，所以哪种乐器使用哪个通道、以哪个音轨作 为主音轨完全是由m i d i 音乐的创作者来决定，没有一定的规律可循。 在文 3 1 1 1 1 1 中提到了一些判别主音轨的方法，可总结为以下3 点： 1 m i d i 音乐的创作者通常会在m i d i 文件里作一些说明，有的可以从中 得到通道的分配情况，找到主通道。 2 打击乐通常是用于伴奏的，比较规范的m i d i 音乐创作者会将第1 0 号 通道分配给打击乐使用，所以主通道多半不会在1 0 号通道。 3 音符数量比较小的一般不会是主通道。 文f 3 对于没有标明主音轨的文件，将经过2 、3 两种方法排除之后剩下的 音轨合并，在同时发音的音符中，只保留最高音。但这种方法存在很大的问题， 因为有些非主音轨里音符数目极多，达到主音轨音符数量的数倍，如果将之与 主音轨合并，将使旋律产生比较大的改变，对检索产生负面的影响。因此，本 系统采用以下方法判断m i d i 文件的主通道： 1 有些m i d i 文件以“m e l o d y ”或“v o c a l s ”标记主音轨，我们通过程序 读出每个音轨的标记，若为“m e l o d y ”或“v o c a l s ”，则将它做为主音 轨。如果m i d i 文件中没有这样的音轨，则以第一条音轨做为主音轨。 2 排除1 0 号通道，从剩下的音轨中选取第一条音符个数在2 0 个以上的通 道做为主通道。 虽然大多数m i d i 文件都以第一条音轨和第一条通道做为主音轨和主通 道，但并非所有m i d i 文件都是如此。因此作者的方法会产生一些误判。但因 为本文中的哼唱检索系统只是一个原型，其主要作用是技术研究而并非商用， 计算机科学系硕士学位论文 在线音乐哼唱检索系统的算法与实现 只要我们在实验中选用没有误判的歌曲做为实验对象，便不会影响实验结果。 找出主通道后，因为m i d i3 c 4 牛是- - 个“事件”( e v e n t ) 的序列，我们通过 逐个找出其中“开始发音”的事件，再做简单的转换，便可以得到本文中的哼 唱检索引擎所需要的( 音差，音符开始时间) 的序列。 3 3 哼唱输入的旋律信息提取 本文中的哼唱检索引擎中，哼唱输入的旋律信息提取主要分为音符分割和 基音提取两个步骤。 3 3 1 音符分割 用户用“d a d a d a ”声哼唱时，可以在每个音符的边界形成一个约6 0 m s 以上的低能量间隔。因此，我们可以跟踪能量随时间的变化情况，确定每个音 符的边界。本文中的哼唱检索引擎主要参考了文献 1 2 】中的方法，具体如下： 首先，计算信号的平均能量。声音信号是一种典型的非平稳信号。但是相 比于声波振动的速度，发音器官的运动就显得非常缓慢了。因此，工程技术人 员通常认为1 0 m s 3 0 m s 这样长度的时间段中，声音信号是平稳信号。基于这 个假设，我们以1 0 m s 的信号作为一帧，得到的结果将被用来处理输入音频。 简单的切分音符的办法是设置阙值，当能量超过某个阈值的时候判断为个音 符的开始，当能量低于某个阈值的时候判断为一个音符的结束。 设置一个时间阈值来去除短时毛刺，如果判断出的音符达不到该阈值的长 度，则判为短时毛刺忽略掉。根据十六分之一音符量子化结果，我们假定每个 音符的长度至少为1 0 0 m s 。这样我们可以过滤掉无关的噪音，例如麦克风发出 的“噼啪”声。 由于信号不在稳定状态时，能量将会反复跨越阈值。意即哼唱一个音符的 过程中，由于发音不稳定，能量很可能因为反复跨越阈值而被判断为音符的结 束。针对这一情况，文献【1 2 】中将判断音符开始的阈值设置得相对高些，而将 音符结束的阈值设置得相对低些分别为5 0 和3 0 。即当一个帧的能量超 过输入音频信号帧平均平方根能量的5 0 时，认为该帧是一个音符的开始；当 一个帧的能量低于输入音频信号帧平均平方根能量的3 0 时，认为该帧是一个 音符的结束。 之所以用百分比来做阈值，是为了适应各种麦克风和录音环境，达到自适 应的效果。 计算机科学系硕士学位论文 在线音乐哼唱检索系统的算法与实现 3 3 2 基音提取 基音提取技术，就是从语音信号中提取出基音( 音高) 的技术。现有的方 法一般都是在短时域上作信号处理，按其分析的算法可分为时域分析和频域分 析两种。一些早期的基于内容的音乐检索( 比如文【l 】) 都对这些成熟的基音提 取技术作过比较，实验结论普遍认为各种算法的准确度相去不多。本文中的哼 唱检索引擎沿用了已有的成熟技术，采用了一些较为简单、通用的算法来提取 基音。 算法输入是一段比较短的音频数据，时长大约为l o o m s 。这些音频数据， 是在音符分割之后，取每个音符开始大约2 0 m s 之后的l o o m s 的数据。之所以 要取开始2 0 m s 之后的数据，是因为由实际的“d a d a ”哼唱音频波型看出，在 每个音符这个位置的音符频率比较稳定，使基音提取容易得到比较好的结果。 具体算法如下： 1 计算整段音频数据的r m s 能量。 2 对音频数据加h a m m i n g 窗。 3 对音频数据进行快速傅立叶变换( f f t ) ，得到频谱数据。 4 消除频谱数据的噪声。 5 找出基音频率。 根据人的发声极限，求出的频率被控制在6 0 h z 到1 0 0 0 h z 之间，并通过下 面这个公式，被转换成半音( s e m i t o n e ) 单位。 s e m i t o n e = 1 2 4 l 0 9 2 ( f r e q 4 4 0 ) + 6 9 其中f r e q 表示音符的频率。这种音高表示与m i d i 中的所采用的完全一致。 之后的音高计算都将以s e m i t o n e 为单位。 3 4 音乐旋律的表示方法 本系统采用分级匹配算法，其中用到了两种近似旋律比较算法。即文 8 中 的l a m 算法和本文中提出的走势峰值匹配算法( t e n d e n c yp e a km a t c h i n g ，以 下简称t p m 算法) 。l a m 算法用于精确匹配，t p m 算法因为效率高，用于初 步筛选。 l a m 算法中，音乐旋律表示为( 音差，音符开始时间) 的形式。音差，是 指当前音符与上一个音符在音高上的差距，以半音为单位。音符开始时间指音 符开始发音的时间，没有单位，其数值只有与其他音符的持续时间比较才有相 对意义。在决定t p m 算法所采用的音乐旋律表示方法时，我们对以往的旋律 表示方法做了以下分析： 9 汁算机科学系硕士学位论文 在线音乐哼唱检索系统的算法与实现 通过对已往研究的分析，我们可以发现，音乐旋律通常表示为一个二元组 或者三元组的序列，每一个二元组或者三元组表示一个音符。这个二元组或者 三元组里，至少有一个元素表示音高信息，通常有频率值、与前一音符的频率 差值、半音值、与前一音符的半音差值以及音高差距量化级别( 例如用u 、d 、 s 三个量级分别表示升高、降低、重复) 等形式，总体可以分为绝对音高和相 对音高两类：同时至少有一个元素表示时间信息，通常有开始时间、音符延续 时间、与某一固定时间长度的比值来表示。 对于表示音高信息的元素，如果采用绝对音高的形式，那么由于旋律比较 算法应该可以适应旋律的可平移性( 即同一段旋律，无论以哪一个音调哼唱， 依然是同样的旋律) ，旋律匹配算法中就要进行在比较前平移音高曲线的操作， 通过平移曲线启发式地优化匹配结果，这样需要花费成倍的计算时间。音高差 是经典哼唱检索系统常用的适应不同旋律起调的方法，虽然这种方法对音高误 差比较敏感，但拥有性能上的优势。因此尽管音高差的方法在准确度上的略有 损失，但还是被较多的哼唱检索系统所采用，因为t p m 算法的目的是提高检 索算法效率，因此也采用音高差来表示音高信息。 对于表示时间信息的元素，我们发现，当同一段旋律以不同速度演奏或哼 唱时，对应的音符之间相差的时间就会变化。因为目前，我们无法获得“速度” 这一信息，因此现有的各种匹配算法或者忽略这一差异，例如仅仅以音高信息 来表示旋律，或者用粗略的量化级别来表示下一音符延续时间与上一音符相比 的变化，( 例如文献 1 4 】中用l o n g e r 、s h o r t e r 、s a m e 三个量级来表示) ，以此来 提高匹配速度。有些算法( 例如文献 7 】) 在时间轴上对音高曲线作线性延展， 以适应不同速度的演唱或哼唱，但这样必然导致算法速度的下降。 我们知道，一段旋律在时间轴上伸缩的变化中，其各个音符之间相对比例 不会发生改变。例如下面以( 音差，音符开始时间) 表示的这两段旋律： 旋律1 ：( # ，o ) ，( - 4 ，3 0 ) ，( 3 ，6 0 ) ，( o ，1 0 5 ) ，( 0 ，1 2 0 ) ，( 3 ，1 5 0 ) 旋律2 ：( # ，o ) ，( - 4 ，6 0 ) ，( - 3 ，1 2 0 ) ，( 0 ，2 1 0 ) ，( 0 ，2 4 0 ) ，( 3 ，3 0 0 ) 显然旋律2 是旋律1 在时间轴上延伸了1 倍所得。如果这两段旋律中，我 们先计算出最后一个音符之前所有音符的平均长度，再用每个音符的长度除以 平均长度，得到的结果序列是完全相同的。如下所示( 最后一个音符没有结束 时间，长度按它之前所有音符的平均长度计) ： ( # ，1 ) ，( 一4 ，1 ) ，( 3 ，1 5 ) ，( 0 ，0 5 ) ，( 0 ，1 ) ，( 3 ，1 ) 这种表示方法可以很好地容忍相同旋律在时间轴上的缩放变化。同一段旋 律，无论在时间轴上以怎样的比例进行缩放，变化为这种表示方法后，都会得 到同样的结果。 此外，作者考虑到，如果减少检索算法中所处理的信息量，也可以达到提 1 0 盐簦苎! 型堂墨塑主兰垒笙苎 垄垡童至堕! ! 丝室墨竺箜簦鲨曼窒塑 高算法速度的目的。因此，作者按照平延、下降、上升三种走势区分歌曲的不 同片断，合并旋律中音高连续上升、下降以及平延的部分，以连续下降的最低 点、连续上升的最高点来表示趋势的峰值( 平延的峰值为o ) ，以这段走势占整 段旋律时间的比例来表示其长度，将旋律以( 旋律走势峰值，旋律走势时间比 例) 的二元组序列的形式来表示。实验证明，旋律以这种形式表示时，哼唱输 入的信息量平均减少了1 2 ，歌曲的信息量平均减少了1 ，3 。 该表示方法在本文3 5 3 中有进一步详细描述。 3 5 匹配算法 本文中的哼唱检索引擎采用t p m 算法初步过滤歌曲，再用l a m 算法精确 匹配的方法。下面我们分别来介绍这两种方法。 3 5 1l a m 算法简介 l a m 算法大致的思路是：先把两段旋律( 印两个音符序列) 在时问轴上线 性延展到相同的长度，并在一定的误差范围内对齐发声时刻接近的音符，考察 旋律在节奏上的相似性。之后，继续比较两段等长旋律在每个时间点上音高频 率的距离。采用音高差的形式表示旋律，保证了用户可以用任意的音调哼唱。 最后，综合考虑节奏和音高两方面的相似程度，给出匹配得分。 具体的算法是：设经过旋律提取后所产生的待查询音符序列为( p o 。t o ) ，( p l ， t 0 ，( p 。1 ，t 。1 ) 。尝试将其与乐曲库中的一段旋律( q o ，u o ) ，( q l ，u 1 ) ，( q 。_ 1 ， u 。1 ) 相匹配。这里p 和q 表示音高差，t 和u 表示音符发声时刻，它们满足： p o = t o = q o = u o = 0 3 4 + n r r 4 3 + n 匹配过程分两步。第一步是将t ) 作时间上的线性变换，向( q ，u ) 对齐， 以对齐音符占总数的比例评估节奏上的相似性。变换后的音符序列保存为( r ， v 1 。 线性变换后，( p ，t ) 被转换成( r ，v ) 。( r ，v ) 已经与( q ，u ) 对齐，在时间上完 全等长。下面的第二步比较( r ，v ) 和( q ，u ) 对应时刻上的音高差距，根据音高接 近的旋律片段占旋律总长度的比例，评估旋律在音高方面的相似度。 3 5 2l a m 算法的优缺点 根据文献【8 】，l a m 具有极高的命中率，在有3 8 6 4 首歌曲的乐曲库中，前 计算机科学系硕士学位论文 在线音乐哼唱检索系统的算法与实现 十位命中率为9 6 7 ，前三位命中率9 0 3 ，第一位命中率7 9 o ，比传统的近 似符号匹配算法高出1 1 以上。因此，我们选用它在哼唱检索引擎中进行精确 匹配。 然而通过试验，我们发现，l a m 算法的效率并不尽如人意。通过对其进行 复杂度分析，我们得到的结果如下： 设哼唱旋律长度p 为1 1 ，与之进行匹配的歌曲旋律q 长度为m ，歌曲总长 度为，。 1 一次完整匹配的复杂度是o ( n + m ) ，这一点文 8 】中有说明。 2 因为3 4 + n m 4 3 n 的关系，所以对于以歌曲中第i 个音符做为q 的 开始的情况，m 的长度变化范围为7 1 2 n ，所以需要进行7 1 2 n 次完 整匹配。 3 对于一首歌曲，一共要进行( 卜m ) 7 1 2 n 次完整匹配 4 所以对于一首完整歌曲进行一次完整比较，算法的复杂度为0 ( ( z - i n ) + n + ( n + m ) ) 根据该算法作者的试验结果，在有3 8 6 4 首歌曲的乐曲库中，每首歌的旋律 均经过优化，排除了重复乐段。在p e n t i u m i i i8 0 0 m h z 的机器上实验，输入2 0 个音符一般在1 5 秒左右，7 个音符在1 0 秒以内。 现在一般k t v 里的歌曲数量都在1 万首左右，而网络上的音乐文件更是 浩如烟海。以w w w i m o b i l e c o m c n 网站为例，就收录了m i d i 文件一万四千余 首。文 1 3 】中提到，在乐曲库规模越大，命中一首歌曲平均所需要的音符数目 越多。那么假设乐曲库规模为1 0 0 0 0 首，当用户输入2 0 个音符时，根据文【8 】 作者提供的测试数据，所需时间将在4 0 秒左右。如果歌曲旋律未经优化，时间 还将超过这个值。 为了提高系统性能，作者提出一种新的基于旋律轮廓峰值的近似旋律匹配 法走势峰值匹配法，即t p m 算法。 3 5 3t p m 算法描述 t p m 算法按照平延、下降、上升三种走势区分歌曲的不同片断，以连续下 降的最低点、连续上升的最高点来表示走势的峰值( 平延的峰值为0 ) ，以这段 走势占整段旋律时间的比例来表示其长度，将旋律以( 旋律走势峰值，旋律走 势时间比例) 的二元组序列的形式表示( 以下简称为形式p ) 。 因为l a m 算法需要以( 音差，音符开始时间) 的形式( 以下简称为形式l ) 来表示旋律，其中音高差表示当前音符与上一个音符频率的差值，以半音 ( s e m i t o n e ) 为单位，音符开始时间指音符开始发音的时间，没有单位，其数 值只有与其他音符的持续时间比较才有相对意义。我们认为以任意单位均可， 计算机科学系硕士学位论文 在线音乐哼唱检索系统的算法与实现 例如毫秒、m i d i 文件中的t i c k 等，只要可以表现出数值之间的倍数关系即可。 下面是一段以形式l 表示的旋律，记做旋律s ： ( # ，0 ) ，( 4 ，6 0 ) ，( 3 ，1 2 0 ) ，( 0 ，2 1 0 ) ，( 0 ，2 4 0 ) ，( 3 ，2 7 0 ) ，( 2 ， 3 0 0 ) ，( - 2 ，3 3 0 ) ( - 3 ，3 6 0 ) ，( 0 ，4 8 0 ) 第一个音符因为没有前者来对比，所以无法判断它与前一个音符的音高差， 因此用# 表示。 因为本文中的哼唱检索引擎接收的音乐旋律的输入是以形式l 表示的，为 了转化为t p m 算法使用的形式p ，需要进行以下变换： 1 合并相同走势的音符的音高差和音长，旋律变为以( 旋律走势峰值，旋 律走势时间) 表示的形式( 以下简称为形式d ) 。旋律s 变为形式d 后 如下： ( 一7 ，1 2 0 ) ，( 0 ，1 2 0 ) ，( 5 ，6 0 ) ，( 5 ，6 0 ) ，( 0 ，1 2 0 ) 其中“走势”的概念含义为：如果下一个音符的音差为负值，则这两 个音符之间的一段时间为下降走势；如果下一个音符的音差为正值，则 这两个音符之间的一段时间为上升走势；如果下一个音符的音差为0 ， 则这两个音符之间的一段时间为平延走势。得到每两个音符之间的走势 之后，我们将相同走势在时间上合并，得到一段走势。所谓“峰值”是 将连续几个相同走势音符的音差相累加而得。 音差 开始发音时间 1 亩1 畜i 才1 亩蠢1 打_ 茹 - r7 。一一 _ 1 2 0 一一一，唪1 2 0 一一一一，v 6 0 一一，r 6 0 一一j - 1 2 0 一一， 图3 2 旋律s 由形式l 到形式d 的变化图解 2 计算出这段旋律的所有走势总长度为4 8 0 ，平均每段走势的长度为9 6 ， 用每段走势的长度除以平均走势长度，得到每段走势的时间比例( 精度 为d o u b l e ) ，旋律表示为形式p 。旋律s 变为形式p 后如下： ( 一7 ，1 2 5 ) ，( 0 ，1 2 5 ) ，( 5 ，0 6 2 5 ) ，( 5 ，o 6 2 5 ) ，( 0 ，1 2 5 ) t p m 算法具体的步骤如下： 1 哼唱旋律