基于指纹的音乐检索是一种新型的音乐检索方式，它让用户录制一段正在播放的音乐，然后上传到服务器进行匹配，最后返回对应的歌曲信息。与哼唱检索相比，它适用范围更广，使用也更加方便。
基于指纹的音乐检索核心是从原始的波形音乐中提取指纹，然后利用指纹进行匹配。指纹可以看做一首歌的哈希值，相同的歌有相同的指纹，不同的歌有不同的指纹。但是和哈希值不同，一首歌的指纹并不是一个单独的数字或者字符串，而是一个附属有时间属性的数字集合。
提取指纹的算法很多，主要有三大类：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 即可。
算法的整体流程如上面所述，但是具体实现可以有不同的方案，不同的参数也会导致指纹数目和检索准确率的不同，而这些都需要不停地调试。
关于检索的详细步骤，请参考：基于指纹的音乐检索原理详述
.
