我第一次用 Shazam 的时候，简直惊呆了。除了 GPS 功能和从楼梯摔下仍然没坏之外，能用一段音频片段识别歌曲是我所见过我手机能做到的最不可思议的事了。识别是通过一个叫音频特征识别的过程来实现的，例子包括：
经过几个周末在学术论文和代码中求索，我想出了一个基于 Python 语言开发的，开源的音频特征识别项目，名字叫 Dejavu。 你可以在 GitHub 上找到它：
https://github.com/worldveil/dejavu
按照我的测试数据集，Dejavu 可以通过从磁盘上读取一段未知的波形文件，或者听取 5 秒以上的录音实现 100% 准确率的识别。
以下是你需要了解的所有关于音频特征识别的知识。对信号处理有研究的读者可以略过，从 “Peak Finding” 开始读。
把音乐当作信号处理
作为一名计算机科学家，我之前理解的快速傅立叶变换 (FFT) ，只是一种很高效地能在O(nlog(n)) 时间内计算多项式乘法的方法。但实际上，它在信号处理方面也有很好的应用场景。
音乐，其实就是与一长串数字相似的数字编码。在未压缩的 .wav 文件里，有很多这样的数字 — 每个声道每秒钟 44100 个数字。这意味着三分钟长的歌曲有近 1600 万个数字。
3 分钟 * 60 秒 * 44100 个样本每秒 * 2 声道 = 15,876,000 个信号样本
声道是指，可以用扬声器播放的，独立的信号样本序列。两个耳塞 — 可以想成是立体声，两个声道。一个声道也被称作‘单声道’。现代的环绕音系统可以支持更多的声道。但除非声音在被录制或者混录时已经是多声道，否则多出来没有对应的扬声器就会播放跟其他扬声器一样的信号流。
信号样本
为什么是每秒 44100 个信号样本？这样选择的原因看起来随意，其实与奈奎斯特-香农采样定理有关。这个很长的，数学推导的方法告诉我们，可以准确采集录音的最大频率是有一个理论上限的。这个最大的频率取决于我们信号采样有多快。
如果你没理解，可以想象看一个扇叶每秒转一个整圈(1Hz)的电风扇。现在闭上你的眼睛，精确地每秒钟快速睁开一下。如果扇叶也是精确的每秒转一圈，对你来说扇叶并没有移动！每次你睁开眼睛，扇叶都会转到相同的位置。但这有问题，实际上，如你所知，扇叶每秒钟可以转 0，1，2，3，10，100，甚至 100万圈。但你却永远感知不到 — 它看起来是静止的！因此为了保证你可以准确地采样（或者‘看到’）高频率的运动（如‘转圈’），你需要以更高的频率采样（或者说‘睁眼’），准确的说，我们需要用运动两倍的频率采样才能确定我们可以觉察到。
就音频录制来说，广泛接受的规则是可以忽略掉 22050Hz 以上的信号，因为人类的耳朵无法听到 20000Hz 以上的频率。因此根据奈奎斯特定理，我们需要加倍地采样：
每秒需要采样的 = 最高频率 * 2 = 22050 * 2 = 44100
MP3 格式的文件压缩了这个采样率，以 1）节省你的硬盘空间，2）惹恼音乐发烧友，但其实纯 .wav 格式文件不过是一串 16 比特的数字序列（加上一个小小的文件头）。
频谱图
因为这些音频样本其实就是信号，我们可以不断地在一小段时间窗口内的歌曲样本上，用快速傅立叶变换生成歌曲的频谱图。下面就是 Robin Thicke 的 “Blurred Lines” 这首歌开始几秒的频谱图。
如你所见，这是一个用横轴表示时间，纵轴表示频率，以颜色表示振幅大小的矩阵。快速傅立叶变换展示给我们信号在特定频率的的强度（振幅）。如果我们计算足够次数的滑动窗口 FFT，我们可以把它们拼在一起组成一个矩阵频谱。
重要的是要注意，频率和时间的值是离散的，每对代表一个 “bin”，振幅是实值。颜色表示在离散化（时间，频率）的坐标系中的振幅的实值（红 -> 较高，绿 -> 较低）。
现在思考，如果我们记录一个单音并创建频谱，我们会在单音的频率上得到一条直的水平线的。这是因为频率不随窗口变化而变化。
很好，那么这如何帮我们识别音频呢？我们想用这个频谱图来唯一地标记这首歌。问题是如果你当车上使用手机，识别的还是收音机上播放的歌曲时，会有噪音 — 背景音里有说话声，另一辆车按喇叭等。我们不得不找一个稳健的方法来获取音频信号的“数字指纹”。
Peak Finding
现在我们有了根据音频信号生成的频谱图，我们可以从在振幅里面寻找‘峰值’开始。我们这里定义峰值为振幅在附近“临域”极大值对应的时频。周围的时频对应的振幅都比它小，更有可能是背景噪音。
查找峰值本身就是个问题。我最后把频谱图当作图片处理，用图片处理工具和scipy库里的技术查找峰值。用一组高通滤波器（强调高振幅）和 scipy查找局部极大值的算法可以实现。
一旦我们提取出这些抗噪声峰值，我们就发现了可以识别一首歌曲的关键点。一旦我们找到峰值，我们就可以有效地“压缩”频谱图。振幅已经完成了它们的使命，我可以不再关注。
让我们来绘制下，看看它是什么样：
你会注意到很多这样的点。实际上，每首歌数以万计。妙处就在，我们已经消除了振幅，只有两个东西要关注，时间和频率，我们可以把它们很方便地转换成离散的整数值。本质上，我们已经将它们合并了。
我们面对的是一个自相矛盾的情况：一方面，我们有一个可以将峰值从信号合并成离散数值对（时间，频率）的系统，让我们避开噪音的干扰。另一方面，因为我们已经离散化，我们将峰值的所包含的信息从无限减少至有限，这意味着一首歌中可以找到的峰值可能（提示：真的会）和其他歌曲中提取的碰撞重合。不同的歌曲可以，并且很可能提取出相同的峰值！现在怎么办呢？
数字指纹哈希
所以我们可能遇到相似的峰值特征。没问题，让我们把这些峰值转换成数字指纹哈希！我们可以用一个哈希函数来实现。
哈希函数接受一个整数作为输入，返回另一个整数作为输出。奇妙的是，一个好的哈希函数不仅在每次输入相同时返回相同的输出整数，而且极少出现输入不同返回输出相同的情况。
通过观察我们的频谱峰值和合并的峰值频率以及它们之间的时间差，我们可以得到一个可以当作歌曲的唯一数字指纹的的哈希。
hash(频谱峰值, 峰值之间时间差) = 数字指纹哈希值
这有很多种实现方式，Shazam 用自己的算法，SoundHound 用另外的。你可以通过读我的源码来看我是怎样实现的。但是关键是，因为考虑多个单一的峰值，你创建的数字指纹有更多的熵，也就是包含更多的信息。因此它们是歌曲更有说服力的标识符，因为它们碰撞重复的几率更小。
你可以将通过下面这个放大的有注释标记的频谱片段来将这个过程在脑海中可视化：
Shazam 白皮书把这些峰的组合比做一种用于识别歌曲的峰组成“星座”。实际上，他们使用的是成堆的峰值以及峰值之间的时间增量。你可以想象许多不同方法来给这些点和数字指纹分组。一方面，数字指纹中有更多的峰值意味着更指纹更罕见，可以更准确地识别一首歌。但是峰值采集的更多，也意味着在有噪音的情况下，更不准确。
学习一首歌曲
现在我们可以开始研究这些系统是怎样工作的了，音频特征系统有两个任务：
- 通过对音乐的特征识别学习一首歌曲
- 通过在存储了已学习的歌曲的数据库中查询来识别未知歌曲
为了实现这个，我们用我们的知识和 MySQL 作为数据库。我们的数据库结构包含下面两个表：
数字指纹表
表有以下字段：
CREATE TABLE fingerprints (
hash binary(10) not null,
song_id mediumint unsigned not null,
offset int unsigned not null,
INDEX(hash),
UNIQUE(song_id, offset, hash)
);
首先，注意我们不只有哈希值和歌曲 ID，还有偏移量。这对应于哈希源自频谱图的时间窗口。当我们需要过滤匹配的哈希时将要用到。只有“对齐”的哈希值才是源自我们要识别的真实信号的（更多关于“数字指纹对齐”的部分在下面）。
其次，我们在哈希值这列建一个索引，有很好的理由。所有的查询都需要匹配哈希值，所以我们需要在这里有一个真正快速的读取。
接下来，UNIQUE所以保证我们不会有重复的项目。不需要浪费空间或过度地匹配重复的音频。
如果你搞不清楚为什么我用binary(10)来指定哈希值存储的类型，原因是，我们会存储很多这样的哈希值，节省空间是必要的。下面是每首歌曲提取数字指纹数量的图表：
最前面的是 Justin Timberlake 的 "Mirrors"，有超过 24 万个数字指纹，接着是 Robin Thicke 的 "Blurred Lines"，有 18 万个数字指纹。最下面的是清唱的"Cups"，无伴奏音乐，只有歌声和一个真的杯子伴奏。相对的，听 “Mirrors”时，你会注意到明显的“噪音墙”乐器和编曲，将频谱从高到低填充满，这意味着频谱充斥着高频和低频，对这个数据集，每首歌的平均有超过10万个数字指纹。
有了这么多指纹，我们需要从哈希值的维度上减少不必要的磁盘存储。对于我们的数字指纹哈希，我们可以从用SHA1开始，将其减少成一半的尺寸（只是前20个字符）。这可以使我们每个哈希值所占用的字节数减半：
char(40) => char(20) 从 40 bytes 到 20 bytes
接下来，我们将十六进制编码转还成二进制，再次大幅度地减少了空间：
char(20) => binary(10) 从 20 bytes 到 10 bytes
好多了，我们将 hash 字段从 320 比特减少到 80 比特，减少了75%的空间利用。
我第一次试用系统时，我用一个 char(40)字段来存储每个哈希 - 这导致仅数字指纹的数据就占了超过 1GB 的空间。通过用binary(10)，存储 520 万个数字指纹仅需要 377M 空间。
我们确实丢失了一些信息 - 我们的哈希值，从统计的角度讲，会碰撞的更频繁。我们大大减少了哈希的“熵”。然而，重要的是要记得我们的熵（或者说信息）还包含4 字节的 offset 字段。这使我们每个数字指纹的总的熵达到：
10 bytes (哈希值) + 4 bytes (偏移量) = 14 bytes = 112 bits = 2^112 ~= 5.2+e33 可能的数字指纹
还不赖。我们省下了 75% 的空间，但仍有难以想象多的数据指纹需要处理。保证关键点的分配是很难的，但我们肯定有足够的熵来回避。
歌曲表
歌曲表就相当普通，我们会用它来查询关于歌曲的信息。我们用song_id来匹配出歌曲的字符串形式的名字。
CREATE TABLE songs (
song_id mediumint unsigned not null auto_increment,
song_name varchar(250) not null,
fingerprinted tinyint default 0,
PRIMARY KEY (song_id),
UNIQUE KEY song_id (song_id)
);
fingerprinted标记是 Dejavu 内部用的，来决定是否要提取一个文件的特征值。我们初始设置为 0，只有当提取特征过程（一般来说两个声道）完成之后才将它设置为 1。
指纹对齐
太棒了，所以现在我们听取了一个音轨，在重叠的时间窗口执行 FFT，提取峰值，形成数字指纹。现在该做什么呢？
假设我们已经在已知的音轨上提取了数字指纹，将其存入数据库，并用歌曲 ID 标记，可以查找直接匹配。
伪代码看起来是这样的：
channels = capture_audio()
fingerprints_matching = [ ]
for channel_samples in channels
hashes = process_audio(channel_samples)
fingerprints_matching += find_database_matches(hashes)
predicted_song = align_matches(fingerprints_matching)
对于哈希来说，对齐是指什么呢？让我们把正在听的样本想成原始音轨的子段落。这样，我们从样本里提取的哈希就会有一个相对于样本开始的偏移量。
问题当然是，当我们最初提取数字指纹，我们记录哈希的是绝对偏移量。来自样本的相对哈希和数据库里的绝对哈希永远不会匹配。除非我们从歌曲的开头开始记录样本，这不太可能。
但是他们也许不是一样的，我们知道所有相关偏移量都是相隔相同的距离。这需要假定音轨被播放和被采样时速率是一致的。实际上，当录音播放的速率不同时，我们就不这样幸运了，因为这会影响录音的频率，继而影响生成频谱中的峰值。无论如何，录音的速度是一个好的（并且重要的）假设。
在这种假设下，对于每个匹配，我们计算偏移量之间的差：
偏移量差 = 库中数据相对原音轨的偏移 - 样本相对于录音的偏移
这会产生一个正整数，因为数据库里的音轨始终至少是样本的长度。所有的真正的匹配都有相同的区别，因此，我们从数据库匹配会被改成：
(song_id, difference)
现在我们只要查看所有的匹配并预测差异数最大的歌曲 ID。如果你能把这想象成直方图，就很容易。
大功告成！
工作的如何
为了真正的获得音频数字指纹系统带来的好处，它不能耗费很长时间来提取指纹。这是糟糕的用户体验，此外，用户可能只是在广播电台插播广告的前的珍贵几秒，尝试匹配歌曲。
为了测试 Dejavu 的速度和准确度，我提取了 2013 年 7 月的美国 VA Top 40 的 45 首（我知道，他们数错了）歌曲的数字指纹。用三种方式测试：
- 直接从硬盘读取原始 mp3， wav 数据
- 用 Dejavu 通过笔记本的麦克风听取音乐
- 在我的 iPhone 上播放压缩流音乐
下面是结果。
1. 从磁盘读取
从磁盘读取的准确率是不可阻挡的 100% — 在我提取特征的 45 首歌里面没有错误。因为 Dejavu 获取到歌的全部样本（没有噪音干扰），如果每次从磁盘读取相同文件都不能成功，那就太糟了。
2.通过笔记本的麦克风获取音频
这里我写了一个脚本，可以随机选取原始 mp3 文件的n秒的音频，让 Dejavu 通过麦克风听。为了结果可信，我选取的音频片段刨除了距歌曲开始或结束10秒内的部分，以防听取不到声音。
另外，在整个过程中，我朋友在说话，我在跟着哼，以加入噪音。
这是听取的时间不同（n)的结果：
结果很棒，正确率如下：
| 录音时长（秒） | 正确结果／总数 | 正确率 |
|---|---|---|
| 1 | 27 / 45 | 60.0% |
| 2 | 43 / 45 | 95.6% |
| 3 | 44 / 45 | 97.8% |
| 4 | 44 / 45 | 97.8% |
| 5 | 45 / 45 | 100.0% |
| 6 | 45 / 45 | 100.0% |
即使只听取一秒，随机选取歌曲的任意部分，Dejavu 的准确率也达到了 60%！两秒的话准确率可以达到约 96%，5秒或以上，结果就趋近于完美了。老实说，当我测试的时候，我发现 Dejavu 赢了我，只听一两秒就识别出歌曲是相当难的。我甚至已经 debugging 的时候连续听了两天相同的歌。
结论是，即便在提供的数据少到几乎没有的情况下，Dejavu 工作的也非常出色。
3. 在我的 iPhone 上播放的压缩音乐流
只是尝试一下，我尝试用我的 iPhone 扬声器从我的 Spotify 账户播放音乐（已压缩160 kbit/s），Dejavu 仍从我的 MacBook 的麦克上听取。正确率没有下降， 1 到 2 秒仍足以识别出任何歌曲。
性能：速度
在我的 MacBook Pro上，以 3 倍速只要很少的开销就可以完成匹配。为了测试，我尝试了不同的录音时长，并记下录音时长加与匹配用时的对应关系。由于匹配速度主要取决于频谱图的长度，和具体哪首歌没有关系，我只测试了一首歌， Daft Punk 的《Get Lucky》:
如你所见，关系是非常线性相关的。你看到的直线是对数据的最小二乘线性回归拟合。相应的方程是：
1.364757 * 录音时长 - 0.034373 = 匹配需要的时间
注意， 因为匹配本身是单线程的，匹配时间也包含录音的时间。这解释了用三倍速匹配时：
1 (录音) + 1/3 (匹配) = 4/3 ~= 1.364757
如果我们忽略微小的常数项。
peak finding 算法的开销是瓶颈 — 我尝试用多线程和实时匹配，这注定不是 Python 的强项。等效的 Java 或 C/C++ 实现应该不难完成实时 FFT 和峰值查找的需求。
重要的警告是，为了匹配数据的往返时间（RTT）。因为我的 MYSQL 实例是本地的，我不用处理无限传输造成的延迟。在计算总的用时时需要加上 RTT，但这不影响匹配的过程。
性能：存储
对于我提取了特征的 45 首歌，数据库用 377MB 的空间存了 5400 万个特征标示。为了比较，磁盘用量如下：
| 音频文件类型 | 占用空间（MB） |
|---|---|
| mp3 | 339 |
| wav | 1885 |
| fingerprints | 377 |
这是一个相当直接的在记录时间和存储空间之间的折衷。调整峰值的振幅阈值和数字指纹采集时的采样频率，可以增加指纹数量， 并以更多空间占用为代价换取更高的准确度。
真的，数字指纹占用惊人的存储空间（比原始的 MP3 文件稍大）。这似乎令人震惊，直到你考虑到每首歌有成百上千，甚至有时成千上万条哈希值记录。我们已经把波形文件中的整个音频信号折衷成数字指纹占用的 20%。我们可以在五秒内非常可靠地匹配到歌曲，所以我们的空间／时间取舍似乎得到了回报。
结论
当我第一次见到音频特征识别的时候，它似乎很神奇。但随着我们掌握一小部分信号处理和基础数学的知识之后，这其实是相当入门的领域。
