how does shazam work

2018-12-16

Algorithm

IR, MIR

音乐信息检索是一个复杂的工作，需要涉及信号处理、计算机算法等知识。以下是粗略介绍。

基本概念

声音的物理特性

中学物理告诉我们，声音来源于振动，声音需要在介质中传播。声音有纯音（pure tone）和实音（real tone）之分，前者是标准的正弦波，后者则是前者的复杂组合。中学数学告诉我们，正弦波有两个主要的特质，分别是振幅dB（amplitude）和频率（frequency）。

音乐简单背景

音符（musical notes）

乐谱是由多个音符构成的，每个音符都有持续时间（duration）和响度（loudness）这两个性质。乐谱的音符可以划分成八度音阶（octaves），每个八度音阶就是8个音符（A-G or Do-Si），八度音阶有如下特点：

一个八度音阶中的音符的频率是上一个八度音阶中的音符的频率的2倍

多数乐器都提供了不止8个音符，这些多出来的就叫做半音（半拍）。

音色（Timbre）

对于同一个音符，不同乐器也会有不同的音色。乐器的声音通常都是有一个基础频率加上多种弦外之音（overtones）合成的。多数乐器都产生和声，但是打击乐器不是。

频谱图

频谱图示例

以上是频谱图示例，信息包含时间、频率和振幅，振幅大小由颜色深度指示。这种图在深度学习处理声音数据的时候也要用到。

傅立叶变换

傅立叶变换FT可以将时域信号$x(t)$转变为频域信号$f(w)$，有如下几种：

连续时间傅立叶变换

$\begin{aligned} f(w)=\int_{-\infty}^{+\infty}x(t)e^{-jwt}\,dt \end{aligned}$

具体原理推导省略，其逆变换为：

$\begin{aligned} x(t)=\int_{-\infty}^{+\infty}f(w)e^{-jwt}\,dw \end{aligned}$

离散时间傅立叶变换

以上公式是连续时间信号的变换，离散信号的变换可以使用离散傅立叶变换DFT，公式如下：

$\begin{aligned} f(w)=\sum_{t=-\infty}^{+\infty}x(t)e^{-jwt} \end{aligned}$

为了在科学计算和数字信号处理等领域使用计算机进行傅里叶变换，必须将函数定义在离散点上而非连续域内，且须满足有限性或周期性条件。这种情况下有：

$\begin{aligned} f(k)=\sum_{t=0}^{N-1}x(t)e^{-j(2\pi tk/N)},\quad k\in \{0,...,N-1\} \end{aligned}$

N个结果，表示N个频率（每个k对应一个频率）以及其对应的振幅。也就是说其计算复杂度为O(N^2)，每个结果都是复数，其模就是对应的振幅。

基本过程

音频检索的基本思想和生物信息检索的思路比较类似，都是在server端建立大量样本构成的数据库，client发送检索请求后，server端提取请求特征，然后在数据库中进行检索匹配，最后将结果返回给client。

在音频检索的场景下，这里面比较重要的部分是

适用于部分匹配的特征提取
样本存储（上千万的歌曲）
高效、健壮的检索

由于部分匹配要求存在，所以音频检索的特征提取算法不可能使用MD5、SHA等，并且要能处理不同格式的音乐（MP2、WMA等）。shazam选择从声音的频谱图中提取特征。

采样

和信号处理的大多数case一样，人声输入是连续的音频，比如一段mp3，是连续信号，需要对信号进行采样、数字化。采样要做的就是信号损失和存储压力之间的tradeoff，奈奎斯特定理指出，要以大于2倍于原始信号的采样频率，才能从数字信号中恢复出原始信。人类听觉上限大约是20kHZ，所以标准的数字音乐采样频率是44.1kHZ，是20kHZ的两倍多一点。

量化

采样是针对频率上的数字化，振幅的数字化则需要量化来完成。振幅的大小受到设备音量的影响。所以振幅的表示则有相对量表示，可以选定整个音乐中振幅的最值，并将其离散化，然后用这些离散值表示。标准的量化方法将振幅范围编码为16个bit，也就是65536个level，这时的信息损失已经很小了。

脉冲编码调制

经过采样、量化两个步骤之后，设备会对数据进行编码（称为PCM信号）并且送到耳机/扬声器进行播放，PCM的样例如下：

16位的PCM信号数据

采样率为44.1kHZ的音乐，每秒钟有44100个这样的数据。

生成频谱图

本节讲的是如何由一段数字信号生成频谱图，需要用到离散傅立叶变换技术。将时序信号等时间间隔划分成多个bin，在每个bin内使用DFT得到其频率。

这里有个概念，每个bin在频率上的表示也是有固定间隔的，这个值叫做频率分辨率（frequency resolution），计算方法是：

frequency resolution = 采样率 / 窗口大小

这里窗口大小是每个bin内采样窗口（window）。比如在44.1kHZ的标准采样率情况下，4096个样本的窗口对应的频率分辨率是10.7HZ。所以一个窗口的时长大约是4096/44100=0.1s，也就是说每隔0.1s就能检测出一个变化。

为了处理一个1s长度的音频，就需要分别处理10个bin的数据。实际上也就是是用了窗口函数（处理第一个bin的时候其他的系数为0）。简单的窗口函数是矩形，也还有hamming窗口和blackbox窗口，图示如下：

不同的窗口效果不同，如下所示，左图是完美的图，右图是是用了不同的窗口函数的图像，可以看到，右图中存在被称为频谱泄漏的现象，即真是频率对应的数据蔓延到邻居点。

图中blackman窗口函数的效果要优于其他窗口函数，但是换一个大小不同的窗口也许就不一样了，他们的特性如下：

矩形窗口函数：可比振幅的正弦曲线效果较好，完全不同的振幅情况则比较差（音乐的振幅变动就比较大）
blackman窗口函数：擅长处理频谱泄漏时出现的强频率掩盖弱频率的问题，同时也导致了噪声会掩盖更多的频率
hamming窗口函数：上面两者的均衡

DFT的计算复杂度较高，在数量为1000的曲库上计算可能需要数天甚至上月才能完成。这里可以使用两个方面的优化：

使用快速傅立叶变换FFT
降采样：因为一首歌中大多数重要的部分都在0-5kHZ区间上，所以我们只需要11kHZ的采样率即可（奈奎斯特）。为了保持相同的频率分辨率，窗口大小降为1024即可。可以将之前4个sample的数据求均值作为一个，采样频率降为原来的1/4

0.1s的bin size, bin的频率分辨率10.7HZ，512个可能的频率（5kHZ/10.7HZ），频率范围0-5kHZ

这里我们就得到了频谱图，考虑到对噪声的鲁棒性问题，可以将振幅最大的音符留下，但是这样会存在如下问题：

许多歌曲中都会包含一些人耳不容易听见的声音（<500HZ），发行前都会特意加强这些音符。只保留振幅最大的可能导致保留的都是这些人耳不容易听见的声音
频谱泄露问题导致不存在的频率出现，要确保不会选中不存在的

解决上述问题的方法如下

对每一个FFT结果（N个），把512个当成6个bands（6是超参数），bands由振幅区间划分，把这些结果放到这些bin中
每个band只保留最大值
计算6个band中最大值的均值（由于开头、结尾可能振幅较小，均值较小，但是我们并不想要这部分频率，所以可以考虑计算整首歌振幅最大的6个的均值）
保留大于均值的band值作为结果（可以乘一个参数）

以下是示例：

特征存储与匹配

如上图所示，特征数据是<time, frequency>对，根据时长进行滑动窗口逐一匹配的复杂度过高。shazam中使用多个点同时匹配的方法，引入target zone的概念。

阐述方便，将目标区域的大小固定为5，将二维数据线性化，需要严格的先后顺序保持唯一性，比如time相同时，frequency小的在前面。所以m个<time, frequency>对的数据，可以生成m-4个目标区域。

下一步是为每个目标区域创建一个地址，当然这是在server端做的。我们还需要一个anchor锚点，anchor的选取不限制，只要是可重复的即可（比如当前目标区域之前的一个点或者前三个啥的）。把每个目标位置当做一个key<anchor频率, 首位频率, 首位和anchor的时间差>，每个key映射到一个地址，地址的形式为<anchor在歌曲中的绝对位置/时间, 歌曲ID>。

在检索阶段，对输入的音频，算法生成一个个<<anchor频率, 首位频率, 首位和anchor的时间差>, 锚点在音频中的绝对位置>，并上传到server端。server进行检索，可能会返回大量结果，这里由于没有逐一比较target zone的每个数据点，所以即使命中了也可能不一样，但是这样节省了时间，也能过滤掉大部分negative样本。细致的比较下面继续。

对于上一步得到的结果，我们需要进一步比较，策略如下

去除没有target zone完全匹配的结果
卡一下阈值

最后还需要考虑时间先后的问题，必要性见上图，这时需要

计算候选歌曲中的音符及其在歌曲中的绝对位置
计算输入音频中的音符及其在输入中的绝对位置
匹配的音符应该满足：音符在歌曲中的绝对位置=音符在输入中的绝对位置+匹配开始的位置。对于每首歌，我们需要找到匹配音节最多的开始位置
返回音符匹配最多的候选

引用

[1]. How does Shazam work