基于指纹的音乐检索

基于指纹的音乐检索是一种新型的音乐检索方式，它让用户录制一段正在播放的音乐，然后上传到服务器进行匹配，最后返回对应的歌曲信息。与哼唱检索相比，它适用范围更广，使用也更加方便。

基于指纹的音乐检索核心是从原始的波形音乐中提取指纹，然后利用指纹进行匹配。指纹可以看做一首歌的哈希值，相同的歌有相同的指纹，不同的歌有不同的指纹。但是和哈希值不同，一首歌的指纹并不是一个单独的数字或者字符串，而是一个附属有时间属性的数字集合。

提取指纹的算法很多，主要有三大类：echoprint，chromaprint和landmark等，具体可参考论文《Evaluatingmusicalfingerprinting systems》。目前最常用的指纹提取算法是shazam公司03发表的论文《AnIndustrial-Strength Audio Search Algorithm》提出的landmark算法。由于landmark算法的检索准确率较高，因而获得了广泛的研究和应用。最近根据上面的论文做了一个开源实现，下面详细介绍一下算法流程。

 

图1 基于指纹的音乐检索算法流程

1 算法流程

图一描述了算法的流程。首先需要将原始波形音乐由时域变换到频域，方法就是采用FFT快速傅里叶变换。这个地方有一个可调参数是每一帧的位移是多少，一般会选择10~40毫秒之间。变换之后会得到一个频谱图，如图二所示。频谱图是一个三维图，X坐标是时间，Y坐标是频率，Z坐标是能量。算法的第二步是从频谱图中提取一系列的landmark。Landmark就是频谱图中的一些能量峰值，如图2(a)中的黑点所示。选取landmark的规则不固定，根据不同的方法和参数选定的landmark也不同。但是可以通过控制参数调节每秒选取的landmark点数。第三步就是利用选定的landmark构造一系列指纹。构造指纹的方法很简单，根据shazam算法中描述，就是将两个landmark组合在一起。最后利用提取的指纹从指纹库中检索得到结果。

 

(a) 立体图

(b) 平面图

图2 频谱图

2 FFT变换

FFT是很多音频算法中的第一步，算是一个算法预处理。可以采用的库有FFTW。如果采用openMP多线程编程，需要在配置fftw时指定—enable-openmp参数。具体的使用方法今后会详细介绍。

3求landmark

Landmark是频谱图中的一系列能量极大值点。根据shazam论文，能量极大值点的抗噪能力很强。求法多种多样，目的就是在二维平面中寻找峰值。通过调节参数可以控制每秒选取的landmark个数。一般情况下每秒保留20~30个点即可。

4 构造指纹

       指纹的构造方法和shazam算法一样。首先针对每一个landmark都有一个targetzone。事实上，这个target  zone就是一个landmark构造指纹的范围，这个也是人为指定的。然后，将landmark和target  zone中的所有landmark两两组合，构成一个指纹。指纹由三部分构成：两个landmark的频率和时间差。同时每个指纹都有一个对应的时间，也即landmark的时间，表示这个指纹出现的时刻。

       如果我们是从原始音乐库构造指纹库，提取的指纹就放入指纹库。指纹库可以用散列表实现，每个表项表示相同指纹对应的音乐id和time。如果我们是检索音乐，则利用提取的指纹访问指纹库。

 

           图3 构造指纹

5 检索

       检索是算法的核心，生成的指纹通过检索指纹库即可返回要检索的歌曲。根据前面的描述，生成的指纹可以放入散列表中，每一个表项都是相同指纹对应的音乐数据。音乐数据包括：音乐的id和该指纹在该音乐中出现的时间。

       有了指纹库，当从用户传递的音乐片段到达服务器之后，首先对该片段提取指纹，然后将所有的指纹与散列表中的指纹进行匹配。当找到匹配的指纹后，获得该指纹对应的音乐的id和该指纹在该音乐中出现的时刻time。然后将提取的指纹对应的time减去从指纹库中获得的time得到一个时间差。最后将这些id和时间差进行排序：id放在long型数据的高位，时间差放在long型的低位，排序后的结果就是针对每个id都有一系列的时间差。

       Shazam算法然后依据这样一个假设选择结果：要检索的片段肯定来自于某一首完整音乐从某个时刻开始的片段，而它们的生成的指纹应该相同，则对应的时间差也应该相同。所以排序完了之后就寻找含有最多相同时间差的音乐id即可。

       算法的整体流程如上面所述，但是具体实现可以有不同的方案，不同的参数也会导致指纹数目和检索准确率的不同，而这些都需要不停地调试。