一种基于最长匹配子序列算法的哼唱计算机音乐检索方法

摘要

本发明公开了一种基于最长匹配子序列算法的哼唱计算机音乐检索方法，主要包括以下步骤：(1)基音频率提取；(2)音乐特征数据库的构建；(3)特征表达实现；(4)检索匹配；本发明的优点是提升了相似度计算的总体速度，提高了搜索引擎的搜索效率，为卡拉OK和基于内容搜索网络引擎及多功能智能移动终端平台构建了精确的音乐检索平台；可广泛地应用在网络搜索引擎的相关插件等领域，本发明所提供的音乐特征的提取、音乐特征的表达以及相似度的精确计算方法可提供哼唱检索系统的准确计算，使音乐的检索准确、轻松、愉快，具有较强的实用价值和现实意义。

说明书

技术领域

本发明涉及一种基于最长匹配子序列算法的哼唱计算机音乐检索方法，属于基于音乐信 息内容检索的计算机应用技术领域。

背景技术

近年随着Internet的发展，音频数据呈几何级数增长。传统的基于文字标注的检索方法已 经不能满足海量多媒体数据的检索需要，因此基于内容的音乐信息检索(Music Information  Retrieval，MIR)技术已经成为信号处理、模式识别和数据挖掘等领域的热点技术之一。基于 内容的多媒体信息检索技术的研究主要集中在图像和视频方面，目前，国内外应用在音频检 索上的技术还不多见。随着用户对网络分类和检索的兴趣提升，使得建立音频web数据检索 机制至关重要。制约基于内容音乐检索技术发展的关键技术问题是如何提取音频特征实现音 乐内容表征并描述音乐特征以及用何种方法进行特征匹配。旋律特征的提取和表达是基于内 容的音乐检索中的基础环节，从音乐片段中提取的旋律特征的能否客观、准确的表达音乐的 语义信息，决定着音乐特征的正确传递，直接关系到后续的匹配和检索是否切实有效；音乐 片段的相似度计算算法以及相应的匹配机制能否符合普遍的听觉、心理感受，是决定检索结 果是否准确的关键因素。因此旋律特征的提取表达与相似度的计算评估是影响一个哼唱检索 或内容的音乐检索系统性能的最重要环节。

对于声学信号而言，其听觉上的音高是由其基音频率序列(Fundamental Frequency)所 决定的。音高提取的目是把用户的输入的声学信号转化成基音频率序列。目前，在特征提取 方面的常见算法如：自相关函数算法(Autocorrelation)、倒谱分析法(Cepstral Analysis)、交 叉相关函数算法(CCF)、平均幅度差函数算法(AMDF)、标准化交叉相关函数算法(NCCF)、 整合音高提取算法(Integrated Pitch Tracker)，但随着相关技术的发展在很多应用场景中，这 些算法的处理效果已经达不到应用的要求，极易造成特征表达与真实音乐语义内容的偏差和 模糊。

目前在特征表达方面的常见方法及缺点如下所示：

1、音高轮廓表达法无法对音高变化进行量化，易造成特征表达与真实音乐语义内容模糊， 随着歌曲样本扩张，极易出现音高轮廓相同但实际旋律相差很大的情况。

2、MIDI音符近似表达法将用户哼唱的自然音高近似归一到离散的MIDI音符的整数值， 会产生旋律表达不准确的问题。如图1所示，展示的是同一段旋律在C大调和A大调中的表 达，两段旋律片段所有对应音的MIDI音高值完全不同，但给人的听觉和音乐认知上感受却 是几乎完全一致。在合理的特征表达方法中，应视这两段旋律具有相同的旋律特征；基于这 一点就体现出MIDI音符近似表达法显得不够恰当与全面。

3、绝对音高表达法虽然解决了近似化产生的表达错误的问题，但配合串比较类和一些动 态规划的相关算法时所产生的音高纵向整体偏移(Pitch Shiftiness)会带来严重的匹配误差， 所以这种特征表达方法并不适合一般的相似度计算机制。

4、调内音级表达法虽然避免了音高整体偏移和不同调式哼唱所带来的影响。但该方法需 要加入调式主音和调式属性作为附加信息，而在哼唱应用的使用场景中，绝大多数情况下主 音和调式的属性无法直接获得，在哼唱片段较短、包含信息不够丰富的情况下，该方法可能 出现很大偏差。如图2所示，这是一段C大调的旋律片段，但同时也符合G大调的调式属性。 这是由于G大调的音节相对于C大调只存在一个变化音#F。所以，当旋律片段中未出现这个 变化音时或其还原音时，由其他音符组成的旋律片段符合C大调和G大调两个调式的属性。 这会导致利用调式内每个音符到主音的度数(Degrees of the Scale from the Tonic)定音方法的 失效。且许多音乐风格在创作的过程中频繁采用包含转调、调外音等打破单一调式属性的音 乐创作技巧，在这些情况下，采用该方法进行哼唱检索会产生很大误差。

5在传统的三重旋律表达法中，音程这一属性表达的是相邻音符之间的频率变化幅度，以赫 兹为单位。音乐体系中所使用的音高单位是半音，尽管半音与赫兹成正相关但并非是线性相 关，半音与赫兹呈现对数关系，因此在不同的音高区域，相差相等单位的半音的两个音之间 对应的频率之差不同。如果采用频率之差作为相邻两个音之间音程衡量标准，这将导致同一 旋律在不同音高区域产生不同的音程序列，进而出现严重音乐特征扭曲，例如图4所示：旋 律1和旋律2包含相同的旋律特征，但在不同的调式下哼唱，其各个自然音在频率维度上分 布的差别鲜明，使得三重旋律表达法无法客观表示旋律特征。

目前在相似度计算方面的现有方法如下：

1、编辑距离算法

传统的编辑距离算法，编辑距离是用来计算两个字符串之间，把一个字符串A转换到另 一个字符串B的最小操作代价。朴素的编辑距离算法(Levenshtein Distance)只适用于字符 串之间的计算，无法直接应用与构成音乐旋律的相似度计算。而拓展后的编辑距离算法可以 用于实数串的距离计算，这种方法的优势是可以量化比较相互匹配的两个实数序列之间的转 化代价，以衡量两个实数序列所代表的两段旋律间的相似度。但这种拓展到实数范围的编辑 距离算法更适用于全局比较，作为输入的两个旋律序列间不匹配时，其相似性计算性能明显 降低。例如：当用户哼唱的某乐句片段与一首音乐的完整信息进行匹配时，编辑距离算法会 计算大量插入元素或删除元素所带来的额外代价，这会使得旋律相似度大大降低，从而导致 算法失效。如图5虚线圈定的部分所示，尽管旋律B与旋律A的局部具有很高的相似度，可 视为匹配的旋律片段。但由于旋律B被机械的与旋律A的整体进行相似度计算，其相似度被 大大降低，这也是编辑距离算法的缺陷所在。

2、最长公共子序列算法

最长公共子序列算法的作用和优势在于，该算法可以从两个字符串A、B中找到相互匹 配的子序列，从而可以用来实现从两段旋律中取得匹配的片段。但由于最长公共子序列算法 不考虑元素插入和删除的代价，因此，当用户哼唱的某乐句片段与一首音乐的完整旋律信息 进行匹配时，用户输入的较短的旋律序列会被无限制的拉伸，两段毫不相关的旋律通过把其 中一段强行拉伸的进行匹配。这种匹配方式极大地扭曲了音乐旋律的特征，即便两段旋律经 过拉伸得以匹配，但是这种方法实际上已经失效。

3、动态时间规整算法

用户哼唱的语音信号具有很强的随机性，不同的发音习惯，发音时所处的环境不同都会 导致发音持续时间长短不一的现象。动态时间规整算法是把语音信号伸长或缩短，直到与标 准模式的长度一致期间，未知单词的时间轴会产生扭曲或弯折，以便其特征量与标准模式对 应。该算法特征使序列可以在时间轴上进行伸缩，从而使相似的轮廓能够对相互对齐，因此 被广泛应用于基于内容的音乐检索、信号处理、语音识别等领域。但是，该算法同样有一些 缺点，首先是时间复杂度太高，在对不定长的整句进行匹配且整句音符相差不多时，容易造 成匹配结果区分度不高的问题。

4、隐马尔可夫模型

隐马尔可夫模型(Hidden Markov Model，HMM)是一种统计分析模型，可用于非特定 人的语音识别中。在哼唱检索领域，由于用户输入的哼唱旋律本身也是语音信号，可以作为 隐马尔科夫模型的观测向量，而旋律特征数据库中的音高特征序列特征具有概率统计特性， 可以作为模型的隐状态。在实现中，通过对不同歌曲的旋律特征进行建模构成检索空间，并 对模型进行相应的训练；在检索过程中，可以反馈用户哼唱的语音信号和检索空间内的歌曲 模型相互匹配的概率。基于隐马尔可夫模型实现的哼唱检索系统，对于不同演唱水平的用户 均能返回查准率良好的结果。但同时其也有不可避免的缺点：隐马尔可夫模型对于音乐特征 数据库中的每条记录，需要分别建立相应的训练模型，随着特征库容量增长，训练的工作量 将会十分庞大，因此隐马尔可夫模型实用性较差。

发明内容

本发明的目的在于提供一种能够克服上述技术问题的使计算机主动识别音乐音调变化的 基于最长匹配子序列算法的哼唱计算机音乐检索方法。本发明的基本技术思路是：在分析对 目前音乐特征提取与表达方法的基础上，确定以相邻音之间的半音音程构成的特征序列；采 用RAPT算法实现音乐基音频率的提取；在技术效果上避免了在不同调式哼唱的造成的特征 提取偏差，为旋律特征的准确提取创造了前提和基础。在旋律特征表达方面，以十二平均律 作为生律基础，将基频轮廓序列经过对数变换，转化为以半音为单位的音程序列，避免了不 同用户在调式哼唱时对旋律特征的影响，同时实现对MIDI问题特征提取的归一化，以 MOMEL算法实现宏观旋律轮廓建模，并以基于十二平均律的对数转化作为技术实现的特征 提取与表达方法，使原本长度10³数量级基频序列，在不丢失旋律特征的前提下，排除了歌 词、语调对宏观旋律基频信号的波动影响，并使得到基频轮廓序列的长度缩减为10数量级， 为进一步提高整体系统的匹配速度提供了重要支持。在相似度计算方面，采用基于最长匹配 子序列(Longest Matched Subsequence，LMS)的相似度计算机制与传统串匹配计算方法相结 合的方法，有效地避免了其它相关算法在应用中的局限性。

本发明的主要步骤为：

(1)基音频率提取；通过音频处理，采用RAPT算法进行基音频率提取、采用低通滤波器 和高通滤波器进行基音频率序列规整、采用中值滤波和线性平滑进行基音频率序列平滑、采 用MOMEL算法进行旋律建模的步骤实现将用户哼唱的语音信号转化为基音频率轮廓序列。

(2)音乐特征数据库的构建；将数据库中所有歌曲的MIDI文件进行预处理，提取出其中 的MIDI音高序列，并以独立字段存入音乐特征数据库，在后续的检索环节中省去了MIDI 文件处理的步骤，而是直接从特征数据库中提取音高序列。

(3)特征表达实现；将从音频处理模块得到的基音频率轮廓序列和音乐特征数据库提取 的MIDI音高序列，转化为统一旋律音程序列，分别代表用户哼唱和数据库记录的旋律特征。

(4)检索匹配；将从用户哼唱音频提取的旋律特征序列分别与检索空间中的所有音乐特征 序列进行相似度计算，并按照最长匹配子序列(LMS)算法机制，将每次匹配的结果进行相 似度排序。

本发明的优点是，提升了相似度计算的总体速度，提高了搜索引擎的搜索效率，为卡拉 OK和基于内容搜索网络引擎及多功能智能移动终端平台构建了精确的音乐检索平台；可广 泛地应用在网络搜索引擎的相关插件等领域，本发明所提供的音乐特征的提取、音乐特征的 表达以及相似度的精确计算方法可提供哼唱检索系统的准确计算，使音乐的检索准确、轻松、 愉快，具有较强的实用价值和现实意义。

附图说明

图1是同一段旋律分别在C大调和G大调中的表达示意图；

图2是同时符合C大调和G大调调式属性的一段旋律示意图；

图3是半音与赫兹的数值关系示意图；

图4是相同旋律在不同调式下的频率变化曲线示意图；

图5是局部旋律与整体旋律进行匹配示意图；

图6是本发明的音频特征提取总体流程示意图；

图7是相同旋律在不同音高区域的音程曲线

图8是本发明的基于MOMEL算法的旋律建模示意图；

图9是本发明的基于LMS算法的相似度计算流程图。

具体实施方式

下面结合附图和实施例对本发明进行详细描述。本发明的主要步骤为：

(1)基音频率序列提取及处理

在基于音乐信息内容检索的技术中，对音频输入的特征提取的准确性对于音乐信息检索 系统的整体性能起着至关重要的作用。理想的音频特征提取需要客观准确地表达用户所输入 的音频检索信息中的音乐旋律，为提升检索准确率和检索效率，本发明提出了一种包含基音 频率提取、频域滤波、中值滤波、旋律建模等多步骤的结合的旋律特征提取流程，本发明的 基音频率序列提取及处理总体流程如图6所示：

1)对输入的WAV波形文件应用RAPT算法进行基音频率提取，从而得到基音频率序列；

2)将原始的基音频率序列将经过高通滤波器和低通滤波器处理，去除毛刺和噪声点，平 滑基频曲线。人类的音域宽度范围一般在E2(82Hz)～C6(1047Hz)之间，根据人类自然发 声范围，将高通滤波的阈值设置为80Hz，低通滤波的阈值设置为1100Hz，用以除去处在高 低阈值之外的基频值；

3)用线性平滑处理对基音频率序列进行线性滤波处理，去除基音频率序列中的噪声点并 且对基音频率序列的曲线轮廓进一步平滑。在本发明的实施例中，滤波窗口设置为50毫秒。

4)将所得到的基音频率序列，通过中值滤波去除噪声点，有效地去除了基音频率序列中 的噪声点，且完好地保留基音频率序列中连续曲线之间的阶跃变化。在本发明的实施例中， 经过基音频率提取后的到基音频率序列采样率为100点/秒，中值滤波窗口设置为77毫秒。

(2)音乐特征表达

1)基音频率曲线的特征表达

以半音作为单位，以相邻两个音之间的音程所构成的序列作为旋律特征。包含n个自然 音符的旋律片断，可被表达为n-1个实数构成的音程序列，以量化的方式表达旋律特征，不 同旋律的音乐特征具有区分度，为后续的相似度计算提供有效的结果；对整体音高整体偏移 不敏感，允许用户在任意调式中哼唱，相同的旋律特征仍能被提取；具有良好的稳定性，即 使在旋律信息有限的情况下，特征表达方法仍然不会失效等优点。对用户通过哼唱输入的音 频信息，音程计算定义如公式(1)所示：

$\mathrm{Pitch}{\mathrm{Interval}}_n=12*{\log }_2\left(\frac{{\mathrm{freq}}_{n+1}}{{\mathrm{freq}}_n}\right)---\left(1\right)$

根据以上定义，可将音高频率序列Fx＝(freq₁，freq₂，freq₃，...，freq_n)映射到音程序列Pi＝ (pitch_interval₁，pitch_interval₂，pitch_interval₃，...，pitch_interval_n-1)。

对于音乐特征数据库中存储的MIDI文件，需要采用同样的旋律特征表达方式，使得从 用户输入端和从数据库端提取的旋律特征具有相同的格式。对MIDI文件，音程计算定义如 公式(2)所示，其中MIDI_note_n+1和MIDI_note_n代表MIDI文件中的音高值：

Pitch Interval_n＝MIDI_note_n+1-MIDI_note_n  (2)

经过以上转化，可将不同调式下的同一旋律特征进行归一化，同时消除了不同哼唱调式 对旋律特征提取的影响，如图7所示，显然两条曲线的对应点已经完全重合，不同调式中同 一旋律的特征被成功的以归一化的方式提取出来。基于相同的特征表达方式可以设计一个相 似度评价机制，来完成检索信息与数据库中的特征信息的匹配，对经过处理的基音频率序列 进行旋律建模，得到一组由离散点构成的旋律骨架；旋律骨架经过对数转化，输入的相邻音 之间音程被提取出来，并以此作为输入音频的特征序列，最终提取出的旋律特征，被送入匹 配模块与音乐特征数据库中的信息进行相似度计算，得到匹配结果。

2)旋律的特征表达

通过基音频率提取、滤波的得到基音频率轮廓曲线，可被拆分成为两种相互独立旋律成 份的组合：宏观旋律成份和微观旋律成份。其定义分别如下：

宏观旋律成份：反应语音信息中的声调模式，与基音频率的全局音高变化密切相关。

微观旋律成份：反应语音信息中的音素成份，影响基音频率曲线的局部变化。

同理，哼唱信息作为语音信息的一种，亦可视为两种旋律成份的组合。对于人声哼唱的 音乐旋律，音高变化只和其基频曲线的宏观旋律成份相关，而哼唱的音标、歌词等音素信息， 则由其基音频率曲线微观旋律成份决定，利用二次样条函数，通过插值近似得到基音频率曲 线的宏观旋律。所得到的宏观旋律以离散目标点序列的形式呈现，并代表了该基音频率序列 对应的音高旋律特征，哼唱旋律特征基于音高序列而与音标、音素信息无关。所以，利用 MOMEL算法对经过滤波的基音频率轮廓曲线进行处理，可以获取基音频率轮廓曲线中的宏 观旋律序列，并作为后续旋律特征表达的基础。

如图8所示的是MOMEL算法的处理的一个实例。经过旋律建模，基音频率轮廓曲线(上 方)的宏观旋律(下方)被成功的提取出来。然而，MOMEL算法输出的直接结果对于后续 的旋律特征表达仍存在明显不足。例如，图8中基音频率轮廓曲线最后两段中，代表一个音 高的基音频率轮廓曲线被标记出两个数值十分相近的目标点。为解决此类问题，本发明设置 一个参数化的阈值，用以控制相邻音之间的音程。当两个音之间的音程低于此阈值的时候， 这个音程会基于具体情况被删除或者与其他相邻音程进行合并。

(3)相似度计算-检索匹配算法

(a)最长匹配子序列算法(Longest Matched Subsequence，LMS)

基于本发明中的特征提取方法所获得的旋律特征是一组实数序列，而音乐特征数据库中 存储的旋律特征均为整数序列。此时，如果机械的利用最长公共子序列算法计算两个序列的 相似度，那么很多原本可以匹配的元素可能被遗漏。

最长匹配子序列算法正可解决最长公共子序列算法(LCS)在应用中存在问题。最长匹 配子序列算法作为对最长公共子序列算法的一种改进，其输出结果是独立的两个子序列A’、 B’，分别是输入序列A、B的子序列。

按照如下方式定义最长匹配子序列：

给定输入序列A＝(a1，a2，a3，...，an)和B＝(b1，b2，b3，...，bm)，

即产生子序列A’＝(a’1，a’2，a’3，...，a’1)和B’＝(b’1，b’2，b’3，...，b’1)。

子序列A’、B’满足如下条件：

1)子序列A’、B’中的每个元素都在另一子序列中有与之匹配的元素，且符合如下条件：

在子序列A’、B’中：

A’的元素a’k对应A的元素ai；

B’的元素b’k对应B的元素bj。

满足：LD(ai，bj)≤δ，其中δ为给定局部相似度最大值。

2)子序列A’和B’分别在各自的原始序列中相对连续，即符合如下条件：

在子序列A’、B’中：

A’的元素a’k对应A的元素ai，A’的的元素a’k+1对应A的元素as；

B’的元素b’l对应B的元素bj，B’的的元素b’l+1对应B的元素at；

满足：s-i≤L且t-j≤L，其中L为子序列中允许插入元素的最大值。

3)子序列A’和B’具有相同的长度。并且A’、B’分别是A、B所有满足条件1)和2)的 子序列中最长的，即|A’|＝|B’|＝max{|Ak|，|Bl|}。

在最长匹配子序列算法中，元素相等的概念被匹配的概念所替换。与最长公共子序列算 法不同，A’与B’并非机械地完全相等，而是A、B所有子序列中最长且拥有相似度最高的一 组。

(b)局部相似度计算

作为最长匹配子序列算法的基础，下面就局部相似度的计算方式进行介绍。

首先，定义实数序列的编辑距离算法：

对给定输入的实数序列：X＝(x1，x2，x3，...，xm)、Y＝(y1，y2，y3，...，yn)。

按照公式3定义实数序列中元素之间相互转化的权值，其中δ为判定相等的阈值：

$w(a,b)=\left(\begin{array}{c}0,\mathrm{if}|a-b|<\delta \\ |a-b|,\mathrm{if}|a-b|\ge \delta \end{array}\right)---\left(3\right)$

初始化编辑距离矩阵Dm，n，初始化条件如下所示：

d0，0＝0；

di，0＝di-1，0+w(xi，0)，其中1≤i≤m；

d0，j＝d0，j-1+w(0，yj)，其中1≤j≤n。

对1≤i≤m且1≤j≤n的矩阵单元，计算编辑距离矩阵Dm，n，递归方程如公式4所示， 其中Wdel、Wsub和Wins分别为删除、替换、插入三种操作的权值：

$d_{i,j}=\min \left(\begin{array}{c}{d}_{i-1,j}+W_{\mathrm{del}}*w(x_i,0)\\ d_{i-1,j-1}+W_{\mathrm{sub}}*w(x_i,y_j)\\ d_{i,j-1}+W_{\mathrm{ins}}*w(0,y_j)\end{array}\right)---\left(4\right)$

最终，输入的实数序列X和Y之间的编辑距离ED(X，Y)可以从矩阵Dm，n的右下角dm， n得到，如公式5所示：

ED(X，Y)＝dm，n。(5)

然后，给出元素的局部相似度的具体定义：

对给定输入的旋律特征序列：A＝(a1，a2，a3，...，an)，B＝(b1，b2，b3，...，bm)。

从A、B中各取一个元素构成二元组(ai，bj)，对于每一对二元组，其局部相似度定义如下， 其中k为局部半径：

定义局部子序列X＝(ai-k，...，ai，...，ai+k)和Y＝(bj-k，...，bj，...，bj+k)。

则二元组(ai，bj)附近的局部相似度LD(ai，bj)可由局部子序列X和Y之间的编辑距离 ED(X，Y)得到，如公式6所示：

LD(ai，bj)＝ED(X，Y)。(6)

(c)动态规划计算最长匹配子序列

明确了原始序列A、B中元素ai、bj附近局部相似度的计算规则，可以利用动态规划 (Dynamic Programming)的策略计算出符合定义的最长匹配子序列A’、B’。

首先，利用动态规划结算最长公共子序列算法(LCS)的计算流程：

给定输入序列A＝(a1，a2，a3，...，am)和B＝(b1，b2，b3，...，bn)。

构造LCS矩阵Cm，n，按照如下条件初始化该矩阵：

ci，0＝0，c0，j＝0，其中0≤i≤m且0≤j≤n；

利用公式7中的递归方程计算矩阵，其中1≤i≤m且1≤j≤n：

$c_{i,j}=\left(\begin{array}{c}{c}_{i-1,j-1}+1,\mathrm{if}{a}_i=b_j\\ \max (c_{i,j-1},c_{i-1,j}),\mathrm{else}\end{array}\right)---\left(7\right)$

最终，最长公共子序列可由Cm，n的右下角cm，n得出。

最长匹配子序列算法(LMS)可按如下方式计算：

给定输入序列A＝(a1，a2，a3，...，am)和B＝(b1，b2，b3，...，bn)。

定义矩阵Cm，n、Rm，n和Sm，n，用以计算最长匹配子序列，详细定义分别如下：

整形矩阵Cm，n，其单元ci，j储存子序列(a1，a2，a3，...，ai)和(b1，b2，b3，...，bj)之间的最 长匹配子序列长度；

整数矩阵Rm，n，其单元ri，j储存这两个子序列中不连续元素的个数；

字符矩阵Sm，n，其单元si，j储存矩阵Cm，n、Rm，n的内部演算路径，对每一次计算记 录正常最长匹配子序列增长的方向。

按照以下条件初始化这三个矩阵：

ci，0＝0，c0，j＝0，r0，j＝0，ri，0＝0，s0，j＝‘_’，si，0＝‘_’，其中0≤i≤m且0≤j≤n；

利用公式8-10中的递归方程计算矩阵Cm，n、Rm，n和Sm，n，其中1≤i≤m且1≤j≤n：

$c_{i,j}=\left(\begin{array}{c}{c}_{i-1,j-1}+1,\mathrm{ifLD}(a_i,b_j)\le \mathrm{\delta and}{r}_{i-1,j-1}\le L\\ 1,\mathrm{ifLD}(a_i,b_j)\le \mathrm{\delta and}{r}_{i-1,j-1}>L\\ \max (c_{i,j-1},c_{i-1,j}),\mathrm{ifLD}(a_i,b_j)>\mathrm{\delta and}{r}_{i,j-1},r_{i-1,j}\le L\\ c_{i,j-1}+1,\mathrm{ifLD}(a_i,b_j)>\mathrm{\delta and}{r}_{i,j-1}\le L<r_{i-1,j}\\ c_{i-1,j}+1,\mathrm{ifLD}(a_i,b_j)>\mathrm{\delta and}{r}_{i-1,j}\le L<r_{i,j-1}\\ 0,\mathrm{ifLD}(a_i,b_j)>\mathrm{\delta and}{r}_{i-1,j},r_{i,j-1}>L\end{array}\right)---\left(8\right)$

$r_{i,j}=\left(\begin{array}{c}0,\mathrm{ifLD}(a_i,b_j)\le \delta \\ r_{i,j-1}+1,\mathrm{ifLD}(a_i,b_j)>\delta ,r_{i,j-1},r_{i-1,j}\le \mathrm{Land}{c}_{i,j-1}>c_{i-1,j}\\ r_{i-1,j}+1,\mathrm{ifLD}(a_i,b_j)>\delta ,r_{i,j-1},r_{i-1,j}\le \mathrm{Land}{c}_{i,j-1}<c_{i-1,j}\\ \min \left(r_{i,j-1,}{r}_{i-1,j}\right)+1,\mathrm{ifLD}(a_i,b_j)>\delta ,r_{i,j-1},r_{i-1,j}\le \mathrm{Land}{c}_{i,j-1}=c_{i-1,j}\\ r_{i,j-1}+1,\mathrm{ifLD}(a_i,b_j)>\mathrm{\delta and}{r}_{i,j-1}\le L<r_{i-1,j}\\ r_{i-1,j}+1,\mathrm{ifLD}(a_i,b_j)>\mathrm{\delta and}{r}_{i-1,j}\le L<r_{i,j-1}\\ 0,\mathrm{ifLD}(a_i,b_j)>\mathrm{\delta and}{r}_{i-1,j},r_{i,j-1}>L\end{array}\right)---\left(9\right)$

$s_{i,j}=\left(\begin{array}{c}\prime S\prime ,\mathrm{ifLD}(a_i,b_j)\le \mathrm{\delta and}{c}_{i,j}=1\\ \prime O\prime ,\mathrm{ifLD}(a_i,b_j)\le \mathrm{\delta and}{c}_{i,j}\ne 1\\ \prime R\prime ,\mathrm{ifLD}(a_i,b_j)>\delta ,r_{i,j-1},r_{i-1,j}\le \mathrm{Land}{c}_{i,j-1}>c_{i-1,j}\\ \prime D\prime ,\mathrm{ifLD}(a_i,b_j)>\delta ,r_{i,j-1},r_{i-1,j}\le \mathrm{Land}{c}_{i,j-1}<c_{i-1,j}\\ \prime R\prime ,\mathrm{ifLD}(a_i,b_j)>\delta ,r_{i,j-1}\le r_{i-1,j}\le \mathrm{Land}{c}_{i,j-1}=c_{i-1,j}\\ \prime D\prime ,\mathrm{ifLD}(a_i,b_j)>\delta ,r_{i-1,j}\le r_{i,j-1}\le \mathrm{Land}{c}_{i,j-1}=c_{i-1,j}\\ \prime R\prime ,\mathrm{ifLD}(a_i,b_j)>\mathrm{\delta and}{r}_{i,j-1}\le L<r_{i-1,j}\\ \prime D\prime ,\mathrm{ifLD}(a_i,b_j)>\mathrm{\delta and}{r}_{i-1,j}\le L<r_{i,j-1}\end{array}\right)---\left(10\right)$

最终，本发明的最长匹配子序列算法的输出结果可通过对符号矩阵Sm，n的记录的路径 和Cm，n中储存的数值计算得到。而最长匹配子序列的长度则可由cm，n直接获得。

本发明的旋律相似度的最长匹配子序列算法的具体流程如图9所示：

1)：给定输入旋律特征序列A、B，采用LMS算法计算取得A、B之间彼此相似度最高的 子序列A’、B’，即最长匹配子序列；

2)通过原始特征序列A、B的长度和匹配子序列A’、B’的长度计算出原始特征序列A、B 之间的匹配部分所占比率；

3)采用实数域的编辑距离算法计算A’、B’之间编辑距离；

4)：对检索过程中每一组参与匹配的特征序列，以A、B之间的匹配部分所占比率作为第 一关键字进行降序排列，A’、B’之间编辑距离作为第二关键字进行升序排列，对其相似度进 行排序，构成相似度降序列表。

本发明在实施例的测试效果验证中随机选择了六名被试对象，该六名对象以哼唱形式为 系统提供待检索信息。此外，为保证每一次哼唱的有效性，避免实验结果受到被试对象主观 因素的影响，实验过程中，每一人次的哼唱只有其他五名被试对象半数以上认可，认为该哼 唱者所哼唱的歌曲确实是目标歌曲时，才被算作一次有效的哼唱，否则将不记为一次有效实 验数据。87条有效的音频检索信息在实验中产生，对于大部份的检索信息，所预期的歌曲都 命中可接受的搜索结果顺位。对58.62％的检索，目标歌曲命中了搜索结果的第一名；所占百 分比在所有顺位的结果中排名第一。此外对超过88.51％的检索，目标歌曲都能命中搜索结果 的前五位；并且95.40％的检索，目标歌曲能够命中前十位。对每一次独立检索，其执行时间 在150ms到550ms，均值289.47ms，考虑的实验的硬件环境，对于一个拥有上百首歌曲的音 乐特征数据库来说，其运行时间也在可接受的范围内，取得了理想的准确率效果，总体的实 验结果表明本发明所提出的特征提取、表达方法和旋律相似度的计算方法切实有效。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉 本技术领域的技术人员在本发明公开的范围内，能够轻易想到的变化或替换，都应涵盖在本 发明权利要求的保护范围内。