基于指纹的音乐检索 – 听歌识曲算法

 

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

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

提取指纹的算法很多,主要有三大类: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 即可。

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

关于检索的详细步骤,请参考:基于指纹的音乐检索原理详述

.

发布者

胡中元

《中原驿站》站长

发表评论

您的电子邮箱地址不会被公开。