基于余弦距离的哼唱音乐检索算法的设计与实现.doc

基于余弦距离的哼唱音乐检索算法的设计与实现学 院计算机学院专 业计算机科学与技术班 级学 号姓 名指导教师负责教师2010年6月摘 要随着多媒体技术的发展，网络音乐日益增多。现在人们己经不满足于通过歌曲名、歌曲的演唱者等一些文本信息来检索。特别是对于那些种类繁多的音乐数据，人们也许只记得一个调子，也许只记得一个片断，如何快速有效的通过旋律来检索相关音乐就成为一个突出问题。本文对基于哼唱的音乐检索进行了相关的研究和实现。本文采用了microsoft visual c+编程技术和mysql server数据库，做了如下工作：(1) 通过对音乐信号基本理论的研究，提出了利用音高差和音长来描述音乐旋律特征的方法，有效地避免哼唱过程走调问题，因此提高了准确性。(2) 对于哼唱音乐片段，通过信号预处理、基音提取、特征提取、特征后处理，实现了从wav文件中提取音符音高差和音长特征，采用n_gram方法对音高序列进行切分，扩充查询集合以提高查询准确度。(3) 确定wav格式作为数据库音乐的文件存储格式，并建立歌曲的音高差和音长特征库。(4) 为提高查询速度，建立整数编码的哈希索引。(5) 采用余弦距离旋律匹配算法，从音高差和音长两方面进行旋律匹配，返回查询结果，并计算响应时间。关键词：哼唱检索；特征提取；余弦距离匹配；音高差usd和音长旋律特征design and implement of hummed melody retrieval based on consine distanceabstractwith rapid development of multimedia technology, a large number of online music can be obtained from the internet. now, people are no longer satisfied with searching music based on text information such as music name and singer. especially, with various kinds of music data, people might only remember the tune of a song, or perhaps fragment of it. how to quickly and effectively retrieve music data by melody information has become a prominent problem. in this dissertation, the music retrieval based on hummed melody is studied .in this dissertation, the hummed melody retrieval based on consine distance is implemented with microsoft visual c+ and mysql server, and the concrete work is as follows:firstly, through the study of music signal, proposing that pitch interval and duracion as the music melody feature, which is effective to avoid the pitch changing as well as improving the music retrieval accuracy. secondly, for the hummed melody, extracting the feature of music melody from wav musics format through signal preprocessing, keynote extraction, feature extraction, feature extraction postprocessing. using n_gram to syncopate the pitch interval in order to improve the accuracy. thirdly, making sure that wav as the musics format and set up pitch interval and duracion database. forthly, in order to improve the speed of retrieval, the dissertation uses hash index. finally, using cosine distance matching algorithm, the pitch interval and duracion as the vector to match then return the result, in the end calculating the retrieval time.keywords: hummed retrieval; feature extraction; cosine distance matching; usd pitch interval and duracion 目 录1 绪论11.1 课题背景及其意义11.1.1 音乐哼唱检索技术的发展11.1.2 音乐哼唱检索系统的意义11.2 课题目标21.2.1 课题研究的主要内容21.2.2 课题研究的价值32 系统需求分析42.1 需求分析42.2 可行性研究52.2.1 技术可行性52.2.2 经济可行性62.2.3 操作可行性62.3 目前可选择的技术62.4 技术开发工具概述62.4.1 c+开发语言概述62.4.2 mysqlserver数据库73 系统概要设计93.1 系统总体设计思想93.2 系统用例图103.3 数据库逻辑设计123.3.1 数据库设计方法简述123.3.2 概念模型设计123.3.3 数据库的关系模型设计134 系统详细设计及实现164.1 系统数据库详细设计164.1.1 用户哼唱片段信息表164.1.2 wav特征库设计164.1.3 索引表174.1.4 检索结果集184.2 系统功能详细设计194.2.1 wav特征提取194.2.2 哼唱音乐的记录和特征提取234.2.3 查询扩展234.2.4 哈希索引244.2.5 余弦匹配算法254.2.6 系统响应时间的计算275 系统的调试与测试285.1 系统的调试285.2 系统功能测试295.2.1 wav音乐文件特征提取测试295.2.2 用户哼唱片段特征提取305.2.3 n_gram算法测试315.2.4 哈希索引表测试315.2.5 系统检索匹配测试325.2.6 分析原因32结束语34参考文献35致 谢37iv1 绪论1.1 课题背景及其意义1.1.1 音乐哼唱检索技术的发展基于哼唱的音频信息检索技术的研究工作是从上世纪九十年代中后期开始的。近年来，它已经成为国内外研究的热点问题之一，引起了众多研究机构和学者的重视。具体来说，早期的研究以ghias和r.j.mcnab等为代表，他们的共同特点是采用时域上的自相关法提取音高值，根据音高值的变化把旋律表示成由字母“u”、“d”、“r”组成的符号串。其中，“u”表示后一个音符的音高比前一个高;“d”表示后一个音符的音高比前一个低;“r”表示前后音符的音高值相同。匹配引擎采用近似字符串模糊匹配算法。后来，一些学者在旋律特征表达方面和匹配检索方面进行了更多的探索。zhu等人使用了一种基于时间序列的方法。在该方法中，歌曲中的每个音符都被拆分成由若干时间片组成的时间序列，从而将整首歌曲中音符的组合转化为时间序列的组合。然后再计算时间序列间的距离，并将结果作为衡量歌曲间相似度的标准。该方法有利于使用dtw方法进行匹配，但是需要进行音符序列的平移和时间弯曲，还需要对每个时间序列进行匹配，时间复杂度非常高。大多数系统都使用近似字符串的匹配算法比较旋律，但近年来，基于隐马尔可夫模型(hmm)的匹配算法被越来越多的学者重视和研究。 wiiliamrand等提出使用马尔可夫统计模型比较旋律的相似性。该方法对音高误差比较敏感，但能较好地容忍遗漏音符和节奏上的哼唱误差。1.1.2 音乐哼唱检索系统的意义随着互联网技术和多媒体技术的迅速发展，网络音乐的下载己经占据了整个网络信息流量的很大份额。人们面临的问题不再是缺少音乐内容，而是如何在浩如烟海的多媒体世界中快速、准确、高效的查询音乐信息。常规的信息检索技术主要是基于文本的，目前已经发展得非常成熟。例如google、yahoo和百度等搜索引擎采用的就是这种技术。它是通过查询关键字的匹配来发现需要检索的文档。如果一个文档包含较多的查询项，就认为该文档比其它包含较少查询项的文档更“相关”。最后，将文档按照“相关”度排序并显示给用户作为检索结果。虽然最初对音频信息的检索也采用了文本检索技术，但却是通过人工方式生成音频信息的文本标注，如文件名、歌曲的演唱者等，然后采用文本检索技术实现对音频信息的检索。在实际应用中，这种基于文本的音频信息检索方式有其固有的无法克服的缺陷。首先，当音频数据量越来越多时，人工的注释强度加大；其次，人对音频的感知，例如音乐的旋律、音调、音质等，难以用文字注释表达清楚。最后，当听到熟悉却又陌生的旋律，但是想不起来它的作者或者表演者时，在现有的搜索引擎上，想要找到这样的乐曲是不可能的。而这正是基于内容的音频检索技术所要研究和解决的问题。可以想象，哼唱检索音乐具有极其广泛的应用前景，普通用户即使只记得音乐的某个片段也可以方便的从网上找到自己喜欢的音乐；在ktv人们只需要哼唱就可以点歌而不需要歌本；音乐创造者可以知道自己的创作是否与众不同；版权管理部门可以查出一首歌曲是否盗版侵权；利用手机哼唱点歌也将成为一种新的潮流。因此，对于哼唱音乐检索的研究具有重要的实用价值，也是富有挑战性的研究领域。本文的工作为音乐哼唱检索打下了一定的基础，对进一步的深入研究具有推动和借鉴意义。1.2 课题目标本次设计的目标是通过对用户哼唱的旋律片段的分析，在大型曲库中利用余弦距离匹配算法，检索出与用户的输入旋律在听觉上相近的歌曲。另外，在设计中，对音乐旋律的刻画考虑音高差和音长，尽可能提高音乐特征描述的准确度。采用整数哈希索引方法，提高了哼唱检索的速度。本设计实现了哼唱检索系统的基本功能，具有较强的实用性。1.2.1 课题研究的主要内容传统的歌曲搜索都是基于关键词的检索，在有些情况下很不实用。本文以基于内容的音乐哼唱检索为背景，系统的研究了记录哼唱音乐片段，哼唱音乐片段特征提取、建立音乐特征库、建立整数哈希索引、余弦距离匹配算法、计算检索响应时间。研究目标为用户不需要哼唱固定符号，更不用加入辅助手段，直接哼一段音乐或唱一段歌谱，将得到检索结果。本文的研究的主要内容如下：记录用户哼唱的音乐片段，存储格式采用wav。在记录过程中，要对录入的声音进行信号预处理、基音提取、特征提取、特征后处理。音乐旋律主要由音高和音长两大部分组成，音高描述该音节的频率高低(相对值)，音长描述该音节的持续长短(相对值)。相同音高序列配以不同的音长表示，或者相同的音长赋予不同的音高，其实际听觉感受差异是十分明显的。因此，采用音高差和音长来刻画旋律特征。音高差采用usd、音长采用lrs描述方式。采用n_gram方法对音高差序列进行切分，产生扩充的usd查询集合，以查询集合中的每个元素为查找项，查找哈希索引后，再进行余弦距离匹配，这样使系统具有良好的容错性。为提高查询效率，本文对旋律轮廓按照n_gram进行切分后，建立了顺序的哈希索引。具有相同的哈希码值的记录放在相同的块中，因此在哈希记录中只有乐曲的编码和片段中第一个音符在歌曲中的位置，提高了检索的效率。采用余弦距离旋律匹配算法，从音高差和音长两方面进行旋律匹配，返回查询结果，并计算响应时间。1.2.2 课题研究的价值哼唱音乐检索实现了所唱即所得的音乐检索方式。检索方式直接且方便，弥补了人们常用的基于文本音乐检索方法中文本信息完整的描述音乐丰富多变的内容难以及手工生成文本索引费时费力的不足。哼唱音乐检索技术在internet上音乐查找、音乐数据库的管理、以及人们的生活娱乐等方面都具有广泛的应用前景。2 系统需求分析2.1 需求分析目前几乎所有音乐网站在为用户提供音乐文件搜索服务时均使用字符检索方式(以标题/作者/歌词作为关键字)。对于音乐而言，这种方式事实上与人的生理与心理特征相违背。人对音乐最敏感的永远是旋律，人们即使忘记了一首歌的歌词，依然能够轻松的哼唱出它的主旋律，就是一个很好的证明。这种最容易让人产生共鸣的音乐旋律信息理应作为另一种检索条件被服务器接受并加以利用，无需借助基于标题、作者或歌词关键字而进行的检索，通过旋律一样可以找出用户所要求的音乐文件，而且这种方式更直观，更贴近音乐的本质。因此一种基于哼唱的音乐检索系统成为人们迫切的需要。该系统的主要功能如下：(1) 采用用户哼唱的内容作为关键信息检索只要使用者通过音频输入设备(如麦克风)哼唱一段音乐的旋律，计算机会自动处理输入的音乐片段，提取音乐特征后，利用这些特征，使用哈希索引方法，在海量的音乐库中寻找出用户需要的目标音乐。这种检索方式的好处显而易见，它十分符合人们的交互习惯、拉近了计算机与人之间的距离。(2) 无须人工干预的对音乐文件进行特征提取音乐的特征是用来区分不同音乐的属性。例如每一曲音乐的乐谱跟其他音乐的乐谱都不一样，乐谱就是其音乐特征之一。另外还包括其他类型的特征，如音乐节奏、音乐的风格等等。提取音乐的这些特征是为了与查询者哼唱的片段进行比较，以便将相近、相似的音乐提供给查询者。因此特征提取是该系统中重要的一环。本文使用音高差和音长来刻画旋律特征，该方法既形象又准确，并且便于进行旋律匹配。另外，intemet上的音乐资源十分巨大，由人工来完成这些音乐特征的提取工作量十分巨大，并且不太现实。而且这些音乐资源的数量还再快速的增长。因此我们需要计算机能代替人工，实现对音乐特征的提取。(3) 检索系统的鲁棒性人的哼唱往往带有很多错误。首先是人们在哼唱的过程中音高与歌曲的标准音高常常不一致，一般都会低于标准音高。其次由于一些人对音乐的旋律不太熟悉，哼唱的旋律中多了一些原本没有的音符或是少了一些原本乐曲中包含的音符。另外，也有人对节奏把握的不是很好，哼唱的速度高于或者低于乐曲的标准节奏。这些哼唱中产生的错误将严重影响系统查询效率。另外在麦克风输入的过程中也可能存在背景噪音等等干扰。为了减少上述情况对查询的影响，系统的各个环节中必须做好相应工作，以保证查询的效率。例如，在麦克风信号采集后，对音乐信号进行预处理和基音提取降低输入环节上的干扰。在特征提取中，使用usd形式的音高差，这样可以有效地避免在哼唱过程的走调现象。在检索过程中，建立了哈希索引，匹配过程中采用余弦距离匹配算法。这样在检索匹配过程中通过适合的算法来降低查询者在哼唱中所产生的错误。因此在系统的各个部分都要考虑的查询的鲁棒性。(4) 检索系统的高效性音乐检索系统的音乐库是十分庞大的。如果检索时匹配时间比较长则会让查询者感到不适应。因此需要检索速度必须较快。另外还需要有较高的准确性。绝大部分查询者通常只愿意浏览查询结果列表的前几项，如果在前几项中查不到用户想要的音乐，使用者将没有耐性继续查下去。因此系统必须考虑的查询的准确性。本文对用户哼唱的音高差序列按照n_gram算法进行切分，产生扩充的查询集合，再以查询集合中的每个元素为查找项，这样能够更准确的查找与输入片段相似的歌曲。此外，建立了顺序的哈希索引。使具有相同的哈希码值的记录放在相同的块中，因此在哈希记录中只有乐曲的编码和片段中第一个音符在歌曲中的位置，这样提高了检索的效率。2.2 可行性研究2.2.1 技术可行性本系统采用c+为开发语言、mysqlserver数据库和microsoft visual studio vc+ 6.0运行环境。c+语言具有面向对象、与平台无关、安全、稳定等优良特性，是目前软件设计中极为健壮的编程语言。microsoft visual studio vc+ 6.0支持如：c或c+语言编程，可运行在windows操作系统上，性能稳定，使用方便，并且提供可视化工具和向导。系统后台数据库采用mysql server 5.0，mysql是一个多用户、多线程的sql数据库，是一个客户机/服务器结构的应用，它由一个服务器守护程序mysql和很多不同的客户程序和库组成。mysql支持标准的ansi sql语句，支持多种平台，在unix系统上该软件支持多线程运行方式，从而能获得相当好的性能。对于windows用户，它可以在windows nt及xp系统上以系统服务方式运行，或者在windows 95/98系统上以普通进程方式运行。综上所述，系统的开发平台已成熟可行。2.2.2 经济可行性软件开发周期一般为23个月，开发所需硬件软件设施目前大多数pc机系统能够承担，开发费用不高。目前，大多数单位都拥有高性能微机和局域网，该软件系统的安装、部署、运行和维护，都不会给单位增加太高的费用。2.2.3 操作可行性目前，大多数pc机和局域网能够运行该系统，该系统的安装、调试、运行不会改变原计算机系统的设置和网络的布局，并且大多数用户几乎不用做任何培训都能够方便操作的软件。2.3 目前可选择的技术目前有许多软件开发人员都开发了类似的系统，所选择的技术都各有不同。数据库技术方面：可以采用mysqlserver、access、db2、oracle等；应用模式方面：可以采用b/s模式、c/s模式、b/s+c/s混合模式；开发工具方面：可以采用c语言、c+、c#、java等。这些技术都有这各自的优点和缺点，通过不同的技术的选择搭配，所开发出来的系统的效果也不同。但是根据该系统的经济可行性和操作可行性，本文选择了使用c+开发语言和mysqlserver数据库。2.4 技术开发工具概述2.4.1 c+开发语言概述c+语言是一种应用较广的面向对象的程序设计语言，使用它可以实现面向对象的程序设计。面向对象的设计与面向过程的设计是有很大区别的，面向对象的程序设计是在面向过程的程序设计的基础上一个质的飞跃。下面简单的介绍一下c+对面向对象程序设计方法的支持和实现。 支持数据封装就是支持数据抽象。在c+中，类是支持数据封装的工具，对象则是数据封装的实现。面向过程的程序设计方法与面向对象的程序设计方法在对待数据和函数关系上是不同的，在面向对象的程序设计中，将数据和对该数据进行合法操作的函数封装在一起作为一个类的定义，数据将被隐藏在封装体中，该封装体通过操作接口与外界交换信息。对象被说明具有一个给定类的变量，类类似于c语言中的结构，在c语言中可以定义结构，但这种结构中包含数据，而不包含函数。c+中的类是数据和函数的封装体。在c+中，结构可作为一种非凡的类，它虽然可以包含函数，但是它没有私有或保护的成员。类中的私有成员一般是不答应该类外面的任何函数访问的，但是友元函数便可打破这条禁令，它可以访问该类的私有成员(包含数据成员和成员函数)。友元可以是在类外定义的函数，也可以是在类外定义的整个类，前者称友元函数，后者称为友元类。友元打破了类的封装性，它是c+另一个面向对象的重要性。 c+支持多态性，c+答应一个相同的标识符或运算符代表多个不同实现的函数，这就称标识符或运算符的重载，用户可以根据需要定义标识符重载或运算符重载。 c+中可以答应单继续和多继续。一个类可以根据需要生成派生类。派生类继承了基类的所有方法，另外派生类自身还可以定义所需要的不包含在父类中的新方法。一个子类的每个对象包含有从父类那里继承来的数据成员以及自己所特有的数据成员。c+中可以定义虚函数，通过定义虚函数来支持动态联编。 综上所述，c+特点为封装性，继承性，多态性。封装是把数据与操作结合成一体，使程序结构更加紧凑，同时避免了数据紊乱带来的调试与维护困难；继承增强了软件的可扩充性 ，并为代码重用提供了强有力的手段；多态性使程序员在设计程序时，对问题进行更好的抽象，以设计出重用性和维护性具佳期的程序。因此，本次设计选择c+为开发语言。2.4.2 mysqlserver数据库mysql是一个小型关系型数据库管理系统，开发者为瑞典mysql ab公司。在2008年1月16号被sun公司收购。目前mysql被广泛地应用在internet上的中小型网站中。由于其体积小、速度快、总体拥有成本低，尤其是开放源码这一特点，许多中小型网站为了降低网站总体拥有成本而选择了mysql作为网站数据库。mysqlserver的特性：(1) 支持aix、freebsd、hp-ux、linux、mac os、novell netware、openbsd、os/2 wrap、solaris、windows等多种操作系统； (2) 为多种编程语言提供了api。这些编程语言包括c、c+、eiffel、java、perl、php、python、ruby和tcl等； (3) 支持多线程，充分利用cpu资源；(4) 优化的sql查询算法，有效地提高查询速度；(5) 既能够作为一个单独的应用程序应用在客户端服务器网络环境中，也能够作为一个库而嵌入到其他的软件中提供多语言支持，常见的编码如中文的gb 2312、big5，日文的shift_jis等都可以用作数据表名和数据列名；(6) 提供tcp/ip、odbc和jdbc等多种数据库连接途径；(7) 提供用于管理、检查、优化数据库操作的管理工具；(8) 可以处理拥有上千万条记录的大型数据库；(9) 使用c和c+编写，并使用了多种编译器进行测试，保证源代码的可移植性。3 系统概要设计3.1 系统总体设计思想根据需求分析的要求，总体设计是建立wav音乐特征库、根据哈希算法建立哈希索引表、记录用户哼唱的音乐片段、对输入的音乐片段进行特征提取、按照n_gram算法扩充查询集合、利用余弦距离匹配算法进行匹配、计算检索时间和将检索结果反馈给用户。(1) wav音乐特征库该模块首先对wav音乐文件格式进行分析。其次，根据wav格式特征，从音高差和音长两方面提取音乐旋律特征。最后，将提取的音乐特征存储到数据库中。(2) 建立哈希索引表为了提高系统检索速度，对wav音乐特征库中的歌曲建立整数哈希索引。对每首歌曲的音高差usd序列和音长lrs都按照哈希算法，将歌曲的id号和该片段的起始位置保存到哈希索引表中，便于用户检索。(3) 哼唱音乐的记录和特征提取在该模块中包括音乐信号预处理、音乐信号基音提取、基音提取后处理、音符切分、特征参数计算，并将处理后的数据存入数据中待检索时调用。(4) n_gram算法对用户哼唱的片段进行特征提取之后，要对音高差序列再进行切分，本文中采用的滑动窗口的大小是3，切分后得到的新查询集合中将有m-n+1个usd片段，其中m为原usd片段的长度，这样扩大查询集合，即所有可能的片段都进行检索和匹配，提高了系统的准确性。(5) 余弦匹配算法最后采用余弦距离的匹配算法，从音高差和音长两方面进行匹配，得到的余弦值是在0到1之间的小数，余弦值越接近于1，就说明匹配度越高。匹配后，将余弦值最大的三首歌曲的相关信息反馈给用户。音乐哼唱检索的主要框架设计如图3.1所示：图3.1 音乐哼唱检索总体功能图3.2 系统用例图用例图从用户的角度描述系统功能，并指出各个功能的角色。本次设计中可以分为两大模块，一个是用户哼唱处理功能模块，另一个是wav特征数据库建立模块。用户哼唱处理功能模块中，包括音乐文件记录、音乐片段特征提取、n_gram算法扩充查询集合、哈希索引等几部分功能。用户哼唱处理模块顶层的用例图如图3.2所示。图3.2 用户哼唱处理用例图在提取音乐片段特征中，又包括音乐信号预处理、音乐信号基音提取、基音提取后处理、音符切分、特征参数计算等功能。音乐片段特征提取的用例图如图3.2所示。图3.3 音乐片段特征提取的用例图wav特征数据库建立模块中包括wav音乐特征库。该模块首先对wav音乐文件格式进行分析。其次，根据wav格式特征，从音高差和音长两方面提取音乐旋律特征。最后，将提取的音乐特征存储到数据库中。wav特征数据库用例图如图3.3所示。图3.4 wav特征数据库的用例图为了进一步阐述执行者与用例的关系，还应画出相应的执行者描述模板及用例描述模板。角色描述模板如图3.5所示。图3.5 角色描述模板3.3 数据库逻辑设计对于音乐哼唱检索系统而言，数据库的设计很重要，数据库的选择上尤为重要，因为该系统要面对海量的音乐信息，选择良好的数据库以及设计方法，对于音乐检索和系统实现都有积极地作用。3.3.1 数据库设计方法简述十余年来，人们努力探索，提出了各种数据库设计方法，这些方法运用软件工程的思想和方法，提出了各种设计准则和规程，都属于规范设计方法。规范设计方法中比较著名的有新奥尔良方法。它将数据库设计分为四个阶段：需求分析（分析用户要求）、概念设计（信息分析和定义）、逻辑设计（设计实现）和物理设计（物理数据库设计）。基于e-r模型的数据库设计方法，基于3nf（第三范式）的设计方法，基于抽象语法规范的设计方法等，是在数据库设计的不同阶段上支持实现的具体技术和方法。规范设计法从本质上看仍然是手工设计方法，其基本思想是过程迭代和逐步求精。3.3.2 概念模型设计e-r图主要作用显示各个实体的属性以及实体之间关系。本系统中主要的实体有用户哼唱音乐片段，音高差库，音长库，歌曲库，音高差检索结果集，音长检索结果集，音长索引表，音高差索引表，索引结果集。图3.6 系统主要e-r图3.3.3 数据库的关系模型设计本系统中主要的关系模型设计及属性如下：(1) 用户哼唱音乐片段（自增id，音高差，音长）；图3.7 用户哼唱音乐片段及其属性图(2) 音高差库（歌曲id号，音高差，音高差序列长度）；图3.8 音高差库及其属性图(3) 音长库（歌曲id号，音长）；图3.9 音长库及其属性图(4) 歌曲库（歌曲id号，歌曲名称，歌手，专辑）；图3.10 歌曲库及其属性图(5) 音高差检索结果集（歌曲id号，歌曲名称，歌手，专辑，检索时间）图3.11 音高差检索结果集及其属性图(6) 音高差索引表（关键字，歌曲id，音高差片段位置）图3.12 音高差索引表及其属性图4 系统详细设计及实现4.1 系统数据库详细设计数据库的设计是系统进行详细设计的开始，它是系统的后台设计部分，用来存储信息以供前台调用和输出。数据库设计的是否合理将直接影响到系统的稳定性、安全性及可维护性，同时也会给后期的编码工作带来诸多不便。在进行了需求分析和概要设计后，接下来将详细介绍系统中各部分信息的存储方式。本系统设db为数据库名。4.1.1 用户哼唱片段信息表用户哼唱的音乐片段是以wav格式存储的，在对输入的音乐信号进行处理后，要提取音乐特征，分别为音高差和音长序列，因此为方便以后的数据处理，用户哼唱片段信息表的设计入表4-1。表4.1 用户哼唱音乐片段表 one_resouce字段名数据类型长度描述idint10自增idalturatext音高差序列lengthint10音高差序列长度duraciontext音长序列length2int10音长序列长度4.1.2 wav特征库设计wav文件作为多媒体中使用的声波文件格式之一，它是以riff格式为标准的，只要了解了文件的格式，就可以方便的将所需要的旋律特征提取出来。从编程的角度来看，其处理过程并不复杂，处理的速度更快，占用系统的资源也更少，是最方便、最容易实现的。因此在wav特征库中设计了音高差表、音长表、歌曲表。(1) 音高差表altura用来存放从音乐文件中提取出来的音高差序列。表4.2 音高差表 altura字段名数据类型长度描述idint10歌曲id号contexttext音高差序列lengthint10音高差序列的长度(2) 音长表duracion用来存储从音乐文件中提取出来的音长序列。表4.3 音长表 duracion字段名数据类型长度描述idint10歌曲id号timetext音长序列rightansint4正确答案(3) 歌曲表中记录了所有歌曲的信息，为音乐检索提供海量的数据。表4.4 歌曲表songs字段名数据类型长度描述idint10歌曲id号namevarchar45歌曲名称singervarchar45歌手姓名albumvarchar45歌曲所在专辑4.1.3 索引表由于本次设计中的数据量较大，因此在设计哈希表时如果采用定义数据结构来存储哈希值，那么会占用大量的内存空间，影响程序的运行速度，因此在数据库中设计了音高差和音长索引表，这样有效地节省了内存空间和提高了系统运行效率。另外哈希表的长度选择29，因为usd三个字符的所有组合有27种可能，选择29方便线性处理冲突。表4.5 音高差索引表 alturaindex字段名数据类型长度描述keyint10关键字大小（1-29）songidtext当前音高差片段所在歌曲的id号positiontext当前音高差片段在整首歌曲的音高差片段中的位置表4.6 音高长索引表 duracionindex字段名数据类型长度描述keyint10关键字大小（1-29）songidtext当前音长片段所在歌曲的id号positiontext当前音长片段在整首歌曲的音长片段中的位置4.1.4 检索结果集本次设计中要求根据音高差检索时，要将相似度最高的前三首歌的信息反馈给用户，当根据音长检索时，要将匹配度最高的前十首歌曲的信息反馈给用户，因此检索结果集中分为音高差检索结果表和音长检索结果表。(1) 音高差检索结果表：表4.7 音高差检索结果表 resultaltura字段名数据类型长度描述idint10歌曲id号namevarchar45歌曲名称singervarchar45歌手姓名albumvarchar45歌曲所在专辑timefloat检索时间(2) 音长检索结果表表4.8 音长检索结果表 resultduracion字段名数据类型长度描述idint10歌曲id号namevarchar45歌曲名称singervarchar45歌手姓名albumvarchar45歌曲所在专辑timefloat检索时间4.2 系统功能详细设计在上一章中对哼唱检索系统的各个功能模块的设计进行了初步的介绍，接下来这一节将要对各个功能模块的具体实现和设计过程中所采用的处理方法及所使用的各种相关技术展开详细的介绍。4.2.1 wav特征提取(1) 细化音乐旋律轮廓特征旋律的变化是指相邻音符的音高和音长变化。研究指出，人们很难准确的把握每个音符的音高和持续时间，但是对音高和音长的变化却能准确的哼唱出来。然而许多研究中将相邻音符音高和音长的变化分为u、s、d三种情况，u代表后一个音比前一个音高，s代表后一个音与前一个音高相同，d代表后一个音比前一个音低，音长的描述和音高差相类似。通过对midi音乐进行统计，相邻音符的音阶差大多在2，21之间，音长比大约在 0.8ms，1.2ms之间。3级轮廓图既能够清楚的区分旋律的变化又避免了返回过多的检索结果，取得了比较理想的效果。(2) 采用“音符起点一音符终点”的音长计算方式“音符起点一音符终点”是指从一个音符的起始时刻到音符的结束时刻之间的间隔。实验中发现:人们在哼唱的时候，对于每个音符的开始时间把握的很好。而且，当节奏比较慢或者某些音符比较长时，哼唱者并没有耐心去唱完整个音符，经常会提前结束。首先对旋律文件进行分帧处理，每帧时间长度去20ms，当一个帧的平均能量超过输入音频信号帧平均平方根能量的50%时，认为该帧是一个音符的起点，当一个帧的能量低于输入音频信号帧平均平方根能量的30%时，并持续时间超过60ms，就认为该帧是一个音符的终点。因此，系统将“音符起点一音符终点”作为每个音符的长度，大大提高了检索的准确程度。(3) 特征提取信号预处理 对于midi等不包含真实声音数据的音乐文件，可以将其中的内容当作字符串来处理。但是wav、mp3等格式的音乐文件存储的是真实的声音数据，必须对其进行音乐信号分析，进而提取特征并进行相应的处理。在按帧进行音乐信号分析、提取音乐信号参数之前，有一些经常使用的、共同的短时分析处理需要预先进行，如音乐信号的加窗分帧、滤波去噪、预加重等处理。在实际中，加窗分帧采用连续分段和汉明窗函数时较好的方法，考虑到在基音周期提取时，窗长应大于两个基音周期才能正确的提取出基音，所以系统的帧长选择20ms。带通滤波器可以减少噪音，起到滤波去噪的功效。但是由于本次设计的时间局限，因此只采用了加窗分帧的预处理方法。基音提取 自相关函数是对信号进行短时相关分析时最常用到的特征函数。假设音乐信号经过帧长为n的窗口截取为一段加窗信号，则的自相关函数为：= （4.1）其中k=(-n+1)(n-1)。由于信号的自相关函数在基音周期的整数倍位置上会出现峰值，因此可通过检测峰值的位置来提取基音周期，再取倒数就得到了最终的基音。当对音乐信号的每一帧信号提取基音后，可形成基音串，而基音串值的变化可对应音调的变化。在此基础上可提取音乐的内容特征如音高变化和音长变化等，并进行检索。自相关函数如图4.1所示。图4.1 自相关函数流程图 基音提取后处理当用户通过麦克风或手机哼唱一段音乐旋律时，所得到的声音波形不可避免的会掺杂有各种噪声，同时用户的哼唱并不一定连续、流畅，所以在波形的各个部分都很有可能出现无声段或噪声段。而这些无声段和噪声段中提取出的基音周期显然不是我们想要的结果，会对后面的旋律匹配产生很大的于扰。因此，基音提取后处理的任务就是要去除无声段和噪声段的基音曲线。具体方法是，使用能量检测来区分无声段，使用过零率和基音来区分噪声段。声音波形的振幅大小说明了声音的强度，在数字信号处理中用能量来表示。无声时波形的振幅理论上应该是零，但实际上受到各种内部和外部噪声的影响，有时会有比较小的振幅出现，而有声时的波形振幅就要大得多，因此可以通过声音波形振幅的大小来判断有声和无声的情况，系统是采用短时能量来进行能量检测的。首先对旋律文件进行分帧，每帧的时间长度取20ms，求每一帧的评价能量x，计算平均平方根能量。当一个帧的平均能量超过输入音频信号帧平均平方根能量的50%时，认为该帧是一个音符的开始，当一个帧的能量低于输入音频信号帧平均平方根能量的30%时，并持续时间超过60ms，就认为该帧是一个音符的结束。过零率是指在单位时间内信号跨越零值的次数，也就是信号符号改变的次数，是对信号频率的一种简单度量。对于窄带信号，如单一正弦波而言，其过零率是比较精确的，为信号频率的两倍。对于一个声音波形来说，如果频率越高，那么其过零率也越高;频率越低，则过零率也越低。对于人所发出的声音频率，一般合理的范围在8731hz和784hz之间 ，在此范围之外的波形就可以作为噪声过滤掉。在实际使用中，系统采用短时过零率，即一个短时帧内信号的过零率来去除噪声.中值平滑滤波是一种能有效抑止声音波形中非典型点的信号处理技术。由于本次设计中的处理有限，因此没有进行此步处理。 音符切分 去除了噪声、无声和非典型点的波形文件切分为一个个usd的片段，每个片段包含一个独立、完整的音符信息。声音波形的切分信息在声音波形预处理的能量检测阶段就可以得到，在判断有声和无声的同时，相应的音符切分位置也就可以确定了。 特征参数计算 有了声音波形的切分信息后，就可以从中计算出旋律特征了。音符的频率就是音高，同一音高的长度就是音长。只要比较相邻音符的过零率就可以获得相对音高差序列。音长的获得只要根据音符的切分就可以了。综合考虑到用户的广泛性和不同用户哼唱的习惯和哼唱能力，系统最终采用了(音高差、音长比)的二维特征。计算特征参数后，就完成了从用户哼唱音乐片段中提取旋律特征的工作。图4.2 wav音乐文件特征提取流程图4.2.2 哼唱音乐的记录和特征提取将哼唱的内容采集并存储到系统中，可以由系统自带的录音程序完成，最终以wav格式将录制的哼唱内容保存到相应的文件中。从保存的文件中提取特征与wav特征库的提取的方法和步骤相同。4.2.3 查询扩展在获取哼唱音乐特征后，如果直接进行匹配，只能是进行精确匹配，那么若输入有误的话，就会匹配失败，因此大大降低了匹配的准确度。最终，本次设计按照滑动窗口方法进行n_gram切分的查询扩展方法。本次提出的方法是将用户查询片段的旋律轮廓按照滑动窗口方法，进行n_gram切分，每次右移一个usd音符，假设一个usd序列的长度为m，则查询后所生成的分片数为m-(n-1)=m-n+1.本次设计中设n为3。设查询目标的usd序列为dddsududud，则进行n-gram切分后的片段为：ddd dds dsu sud udu dud udu dud。扩充查询集合后，以集合中的每个查找项作为新的查找项，查找哈希索引。n-gram方法的实现如图4.2所示。图4.3 n_gram算法流程图4.2.4 哈希索引为提高查询效率，对旋律轮廓按照n_gram方法切分后，建立了顺序的哈希索引。对每一段旋律片段取其音高差和音长的旋律轮廓作为索引项，与歌曲id号和片段中第一个音符在歌曲的位置共同组成数据记录，建立哈希索引。系统中的哈希表中，具有相同的哈希值的记录放在相同的块中，因此哈希记录中只有歌曲的id号和片段中第一个音符在歌曲中的位置。由于哈希表是一首一首建立的，之后没有更新操作，因此在哈希表的数据是有序的。这在索引查找后的处理时，可以大大提高效率，哈希算法的实现如图4.3。图4.4 哈希索引实现流程图4.2.5 余弦匹配算法余弦距离是目前被广泛应用的向量相关性比较的主要手段，基于“余弦距离”的旋律匹配算法在目前的旋律匹配算法中得到了广泛的应用，这种算法将与用户哼唱与存储在数据库中的乐曲片段看作是两个待比较的向量，通过“余弦距离”的计算，比较两段旋律向量的相似程度，余弦距离越接近1，说明旋律片段更接近,具体实现如图4.4。若用户输入的片段旋律特征作为一个向量，经过检索后的数据向量为，则余弦距离公式为： （4.2）图4.5 余弦匹配算法实现流程图4.2.6 系统响应时间的计算响应时间的计算，可以利用windows api中的函数直接获得系统当前时间，时间可以精确到毫秒级。在用户输入结束后，获得一次系统时间，并保存，当检索匹配结束后，再获得一次系统时间，两次时间差即为响应时间。获得系统时间的函数如下：#include systemtime getsystemtime( void ) systemtime sys; /定义系统时间对象getlocaltime( &sys ); /获得本地时间return sys; 5 系统的调试与测试5.1 系统的调试系统的调试与验证，是系统编码完成之后所进行的最后一步操作，通过本步的操作可以测试系统所实现的功能是否齐全，系统的运行是否稳定，运行过程中是否会出现异常的结果。下面将系统设计中的主要功能测试进行说明。在整个系统实现的过程中，遇到了很多需要解决的问题。在程序开发的初步阶段，对于题目中的一些算法还不是很了解，编程环境的使用也不够熟练，因此在初期的程序设计中，遇到了很多问题。以下是编码调试时遇到的一些问题以及问题的解决方法： (1) 在开始设计中，对于哼唱音乐没有进行任何预处理，就直接进行提取，经过对比后发现，特征描述不够准确，于是在提取特征之前，对音信号首先进行了预处理，并且在输入过程中，尽量避免不必要的噪音。(2) 设计中使用了mysql server数据库，开始的时候，vc+环境无法与数据库相连接，查阅资料之后，发现要在编程环境中使用数据库，要设置一些环境变量并且要将mysql的头文件放在vc+的运行路径下。(3) 对sql语句有一些了解，但是在vc+环境中执行sql语句，要进行一些变化，于是就对mysql中的类进行了深入了解，最终得出要在c+中执行sql语句，并对数据库进行跟新，一定要将sql的内容进行