听歌识曲的原理

在进行深入的讨论之前, 我们需要先了解一些什么是音频. 首先, 声音是波, 那么起决定性作用的就是频率和振幅, 其中频繁决定声音的音调, 振幅决定声音的响度. 人耳一般能够听到20Hz~20kHz的声音.

频率

这也就是为什么我们通常使用44.1kHz采样的音频, 如果你的采样率小于等于频率的二倍, 就无法很好的表示出当前的正弦波. 如果你想很好的将音乐从模拟信号转化为数字信号, 你至少需要大于40kHz的采样率, 一般的工业标准是2.2倍频率预留一些空间, 也就是44kHz.

HIFI公司例如索尼选择44.1kHz因为它高于40kHz并且兼容NTSC和PAL. 其他的48kHz, 96kHz, 192kHz也是可以的, 但是如果你不是专业人士一般没法听出区别, 同时高采样率带来的问题是文件会占用更多的空间.

PCM

Pulse Coded Modulation是常见的音频存储格式, 我们使用的音频设备一般会直接播放这种音频, 比如一个AAC编码的音乐在解码后产生的PCM数据会送往音频设备的驱动程序进行播放. 其中每一组数据中存放每个声道的一个采样, 一个采样可以是16位整数或者32位浮点数等.

傅里叶变换

那么我们如何通过一堆采样来获取原始音频的频率呢? 对于模拟信号来说, 我们可以通过傅里叶变换(Fourier Transform)将关于时间的函数转化为关于频率的函数. 换句话来说, 你可以对音乐施加傅里叶变换来获得音乐中所有频率和他们的强度.

通俗来讲, 傅里叶变换就是将某一个时刻的音频波分解为多个不同振幅不同频率的标准波.

但是我们的问题是, 现在只有数字信号, 而不是模拟信号. 幸好还有离散傅里叶变换(Discrete Fourier Transform).

Note

离散傅里叶变换只能应用在单一通道上, 如果你有空间音频那么你就需要将它转化成一个单通道的音频

如下是离散傅里叶变化的公式:

X(n)=\sum^{N-1}_{k=0}x[k]e^{-j(2\pi kn/N)}

其中

N代表窗口的大小, 指的是当前我们有多少的采样暴露在当前窗口中.
X(n)表示第n个桶的频率组.
x(k)表示音频信号的第k个采样.

例如, 我们处理一个4096个采样的窗口的时候, 这个公式需要计算4096次. 其中

n=0时计算第0个桶的频率组
n=1时计算第1个桶的频率组
...

注意这里计算的结果时频率组而不是频率, 因为一个DFT给出的结果是离散的频谱. 一个频率组是DFT能够计算的最小单位. 其中我们分为了4096个桶, 每个桶就可以负责约10.7Hz的频率段. 比如第一个桶中的频率组是0~~5.38Hz(第一个桶是特殊的), 第二个是5.38~~16.15Hz, 这就代表当前DFT无法区分出一个频率组内相差10.77Hz以内的频率, 导致频率解析率的降低. 如果说两个音符的频率在这个同一个范围之内, 我们就无法区分它们.

我们可以通过提高窗口的大小来提高音频解析率, 但是同时也会增大计算开销.

但是使用离散傅里叶变换生成频谱图还有一个坑, 如果我们的采样率是44.1kHz, 因为高于44.1kHz一半的频率都无法正确表示, 当我们的频率为 $x+\frac{1}{2}S$ 的时候变换的结果与 $x$ 相同(其中x为当前频率, S为采样率), 所以进行变换的时候我们只需要关注一半的结果即可, 也就是0~22.05kHz的频谱.

窗口函数

因为DFT要求我们对音频进行划分, 如果我们想要分析某一个很短的时间段内的频谱, 就需要一个窗口函数来对音频采样进行划分.

音频划分会导致频谱泄露, 由于使用窗口划分函数导致真正的频率的能量泄露到其他频率, 比如你的采样率是 $f_S$ , 窗口大小是 $N$ , 那么如果你的频率不是 $\frac{f_S}{N}$ 的整数倍, 就会产生频谱泄露. 你可以通过选择更恰当的窗口函数来减小频谱泄露的影响, 但是你无法完全避免它.

FFT

直接进行离散傅里叶变换的时间复杂度是 $O(N^2)$ , 我们可以通过使用分治法来加速这一过程, 使用快速傅里叶变换的时间复杂度仅有 $O(NlogN)$ . 但是这样需要输入的长度是2的次幂, 如果原始数据的长度不是2的次幂我们可以通过填充0来调整长度.

听歌识曲

频谱过滤

因为听歌识曲需要容忍噪音, 我们需要对输入音频进行过滤, 提取出响度最大的音频. 但是这里我们并不能直接对于每个时间段求出前X大的频率, 因为人耳对低频率和高频率的音频更不敏感, 所以很多音乐在发行之前会先进行预处理增强低频, 如果这么做的话会让两个鼓点相似的音乐在频谱图上十分相似.

一个比较好的解决方案就是进行频谱划分, 将整个频率划分为低频中频高频, 每个频带中选择较强的峰值.

进行频谱过滤之后, 提取出频谱图中能量较强的特征点, 记录下歌曲ID, 出现时间, 频率等信息作为歌曲的音频指纹, 每秒提取出若干个这样的音频指纹, 就可以在数据库中匹配音乐.