沙赞如何运作？ 音乐识别算法、指纹识别和处理

您在俱乐部或餐厅听到熟悉的歌曲。 这首歌你听了一千遍了，这首歌的感伤真的触动了你的心。 你明天拼命想把它放在心上，但你不记得它的名字了！ 幸运的是，在我们令人惊叹的未来世界中，您有一部安装了音乐识别软件的手机，您就得救了。 您可以放松一下，因为软件会告诉您歌曲的名称，并且您知道您可以一遍又一遍地听到它，直到它成为您的一部分……或者您厌倦了它。

移动技术，以及音频信号处理方面的巨大进步，使我们的算法开发人员能够创建音乐识别器。 Shazam 是最受欢迎的音乐识别应用程序之一。 如果您捕获一首歌曲的 20 秒，无论是前奏、主歌还是合唱，它都会为录制的样本创建指纹，查询数据库，并使用其音乐识别算法准确地告诉您您正在听哪首歌.

但是，Shazam 是如何工作的？ Shazam 的算法由其发明者 Avery Li-Chung Wang 于 2003 年向世界展示。在本文中，我们将介绍 Shazam 音乐识别算法的基础知识。

模拟到数字 - 对信号进行采样

什么是真正的声音？ 它是某种我们无法触摸但飞入我们耳朵并让我们听到事物的神秘物质吗？

当然，情况并非如此。 我们知道，在现实中，声音是一种振动，它以压力和位移的机械波的形式通过空气或水等介质传播。 当这种振动传到我们的耳朵，尤其是耳膜时，它会移动小骨头，这些骨头会将振动进一步传递到我们内耳深处的小毛细胞。 最后，小毛细胞产生电脉冲，通过听耳神经传递到我们的大脑。

录音设备非常接近地模仿这个过程，利用声波的压力将其转换为电信号。 空气中的实际声波是连续的压力信号。 在麦克风中，第一个遇到该信号的电子元件将其转换为模拟电压信号——同样是连续的。 这种连续的信号在数字世界中不是那么有用，因此在对其进行处理之前，必须将其转换为可以以数字方式存储的离散信号。 这是通过捕获表示信号幅度的数字值来完成的。

转换涉及输入的量化，它必然会引入少量的误差。 因此，模数转换器不是单次转换，而是对非常小的信号片段执行多次转换——这一过程称为采样

Nyquist-Shannon 定理告诉我们在连续信号中捕获某个频率所需的采样率。 特别是，为了捕获人类可以在音频信号中听到的所有频率，我们必须以人类听觉范围两倍的频率对信号进行采样。 人耳可以检测到大约 20 Hz 到 20,000 Hz 之间的频率。 因此，音频最常以 44,100 Hz 的采样率记录。 这是光盘的采样率，也是 MPEG-1 音频（VCD、SVCD、MP3）最常用的采样率。 （这个特定的速率最初是由 Sony 选择的，因为它可以在以每秒 25 帧 (PAL) 或每秒 30 帧（使用 NTSC 单色视频录像机）运行的修改后的视频设备上录制，并覆盖认为必要的 20,000 Hz 带宽匹配当时的专业模拟录音设备。）因此，在选择需要录制的样本频率时，您可能希望使用 44,100 Hz。

录音 - 捕捉声音

录制采样的音频信号很容易。 由于现代声卡已经带有模数转换器，只需选择一种编程语言，找到一个合适的库，设置样本的频率，通道数（通常是单声道或立体声），样本大小（例如 16 位样本）。 然后像任何输入流一样打开声卡中的行，并写入字节数组。 以下是如何在 Java 中完成此操作：

 private AudioFormat getFormat() { float sampleRate = 44100; int sampleSizeInBits = 16; int channels = 1; //mono boolean signed = true; //Indicates whether the data is signed or unsigned boolean bigEndian = true; //Indicates whether the audio data is stored in big-endian or little-endian order return new AudioFormat(sampleRate, sampleSizeInBits, channels, signed, bigEndian); } final AudioFormat format = getFormat(); //Fill AudioFormat with the settings DataLine.Info info = new DataLine.Info(TargetDataLine.class, format); final TargetDataLine line = (TargetDataLine) AudioSystem.getLine(info); line.open(format); line.start();

只需从TargetDataLine读取数据。 （在这个例子中， running标志是一个被另一个线程停止的全局变量——例如，如果我们有带有 STOP 按钮的 GUI。）

 OutputStream out = new ByteArrayOutputStream(); running = true; try { while (running) { int count = line.read(buffer, 0, buffer.length); if (count > 0) { out.write(buffer, 0, count); } } out.close(); } catch (IOException e) { System.err.println("I/O problems: " + e); System.exit(-1); }

时域和频域

我们在这个字节数组中拥有的是时域中记录的信号。 时域信号表示信号随时间的幅度变化。

在 1800 年代初期，Jean-Baptiste Joseph Fourier 做出了惊人的发现，即时域中的任何信号都等效于一些（可能无限）简单正弦信号的总和，因为每个正弦分量都有一定的频率、幅度、和相。 一起形成原始时域信号的一系列正弦曲线称为傅里叶级数。

换句话说，可以通过简单地给出与构成信号的每个正弦曲线相对应的频率、幅度和相位的集合来表示任何时域信号。 信号的这种表示称为频域。 在某些方面，频域充当时域信号的一种指纹或签名，提供动态信号的静态表示。

以下动画演示了 1 Hz 方波的傅立叶级数，以及如何从正弦分量生成（近似）方波。 信号在上面的时域中显示，在下面的频域中显示。

在频域中分析信号极大地简化了许多事情。 在数字信号处理领域更方便，因为工程师可以研究频谱（信号在频域中的表示）并确定哪些频率存在，哪些频率缺失。 之后，可以进行过滤，增加或减少一些频率，或者只是从给定的频率中识别出确切的音调。

离散傅里叶变换

所以我们需要找到一种方法将我们的信号从时域转换到频域。 在这里，我们求助于离散傅里叶变换 (DFT)。 DFT 是一种对离散（采样）信号执行傅里叶分析的数学方法。 它通过考虑这些正弦曲线是否以相同的速率采样，将函数的等距样本的有限列表转换为复杂正弦曲线的有限组合的系数列表，按频率排序。

用于计算 DFT 的最流行的数值算法之一是快速傅里叶变换 (FFT)。 到目前为止，最常用的 FFT 变体是 Cooley-Tukey 算法。 这是一种分而治之的算法，它将一个 DFT 递归地划分为许多更小的 DFT。 直接评估 DFT 需要O( n 2 ) 次运算，而使用 Cooley-Tukey FFT 时，相同的结果需要O( n log n )次运算。

为 FFT 找到合适的库并不难。 以下是其中几个：

• C – FFTW
• C++ – 特征 FFT
• Java – JTransform
• Python ——NumPy
• Ruby – Ruby-FFTW3（FFTW 接口）

下面是一个用 Java 编写的 FFT 函数的示例。 （FFT 将复数作为输入。要了解复数和三角函数之间的关系，请阅读欧拉公式。）

 public static Complex[] fft(Complex[] x) { int N = x.length; // fft of even terms Complex[] even = new Complex[N / 2]; for (int k = 0; k < N / 2; k++) { even[k] = x[2 * k]; } Complex[] q = fft(even); // fft of odd terms Complex[] odd = even; // reuse the array for (int k = 0; k < N / 2; k++) { odd[k] = x[2 * k + 1]; } Complex[] r = fft(odd); // combine Complex[] y = new Complex[N]; for (int k = 0; k < N / 2; k++) { double kth = -2 * k * Math.PI / N; Complex wk = new Complex(Math.cos(kth), Math.sin(kth)); y[k] = q[k].plus(wk.times(r[k])); y[k + N / 2] = q[k].minus(wk.times(r[k])); } return y; }

以下是 FFT 分析前后的信号示例：

音乐识别：对歌曲进行指纹识别

FFT 的一个不幸的副作用是我们丢失了大量有关时间的信息。 （虽然理论上可以避免这种情况，但性能开销是巨大的。）对于一首三分钟的歌曲，我们可以看到所有的频率及其幅度，但我们不知道它们出现在歌曲中的时间。 但这是使这首歌成为现实的关键信息！ 不知何故，我们需要知道每个频率出现的时间点。

这就是为什么我们引入一种滑动窗口或数据块，并只转换这部分信息。 每个块的大小可以通过几种不同的方式确定。 例如，如果我们以 44,100 Hz 的 16 位样本以立体声录制声音，那么一秒钟的此类声音将是 44,100 个样本 * 2 字节 * 2 个通道 ≈ 176 kB。 如果我们选择 4 kB 作为块的大小，我们将在歌曲的每一秒中分析 44 个数据块。 这对于音频识别所需的详细分析来说已经足够了。

现在回到编程：

 byte audio [] = out.toByteArray() int totalSize = audio.length int sampledChunkSize = totalSize/chunkSize; Complex[][] result = ComplexMatrix[sampledChunkSize][]; for(int j = 0;i < sampledChunkSize; j++) { Complex[chunkSize] complexArray; for(int i = 0; i < chunkSize; i++) { complexArray[i] = Complex(audio[(j*chunkSize)+i], 0); } result[j] = FFT.fft(complexArray); }

在内部循环中，我们将时域数据（样本）放入一个虚部为 0 的复数中。在外部循环中，我们遍历所有块并对每个块执行 FFT 分析。

一旦我们获得了有关信号频率构成的信息，我们就可以开始形成歌曲的数字指纹。 这是整个 Shazam 音频识别过程中最重要的部分。 这里的主要挑战是如何在捕获的频率海洋中区分哪些频率是最重要的。 直观地说，我们搜索幅度最高的频率（通常称为峰值）。

然而，在一首歌曲中，强频率范围可能在低 C - C1 (32.70 Hz) 和高 C - C8 (4,186.01 Hz) 之间变化。 这是一个巨大的时间间隔。 因此，我们可以选择几个较小的间隔，根据重要音乐成分的共同频率选择，而不是一次分析整个频率范围，然后分别分析。 例如，我们可能会使用这个人为实现 Shazam 算法选择的间隔。 这些是 30 Hz - 40 Hz、40 Hz - 80 Hz 和 80 Hz - 120 Hz 用于低音（例如覆盖低音吉他），以及 120 Hz - 180 Hz 和 180 Hz - 300 Hz 用于中音和更高音（涵盖人声和大多数其他乐器）。

现在，在每个区间内，我们可以简单地确定幅度最高的频率。 这些信息形成了这首歌曲的签名，而这个签名成为整个歌曲指纹的一部分。

 public final int[] RANGE = new int[] { 40, 80, 120, 180, 300 }; // find out in which range is frequency public int getIndex(int freq) { int i = 0; while (RANGE[i] < freq) i++; return i; } // result is complex matrix obtained in previous step for (int t = 0; t < result.length; t++) { for (int freq = 40; freq < 300 ; freq++) { // Get the magnitude: double mag = Math.log(results[t][freq].abs() + 1); // Find out which range we are in: int index = getIndex(freq); // Save the highest magnitude and corresponding frequency: if (mag > highscores[t][index]) { points[t][index] = freq; } } // form hash tag long h = hash(points[t][0], points[t][1], points[t][2], points[t][3]); } private static final int FUZ_FACTOR = 2; private long hash(long p1, long p2, long p3, long p4) { return (p4 - (p4 % FUZ_FACTOR)) * 100000000 + (p3 - (p3 % FUZ_FACTOR)) * 100000 + (p2 - (p2 % FUZ_FACTOR)) * 100 + (p1 - (p1 % FUZ_FACTOR)); }

请注意，我们必须假设录音不是在完美的条件下完成的（即“聋人房间”），因此我们必须包括一个模糊因素。 应认真对待模糊因子分析，在实际系统中，程序应具有根据记录条件设置此参数的选项。

为了便于音频搜索，此签名成为哈希表中的键。 对应的值是这组频率出现在歌曲中的时间，以及歌曲 ID（歌曲名称和艺术家）。 下面是这些记录如何出现在数据库中的示例。

如果我们通过这个音乐识别过程运行一个完整的歌曲库，我们可以建立一个数据库，其中包含库中每首歌曲的完整指纹。

音乐算法：歌曲识别

为了识别俱乐部当前正在播放的歌曲，我们用手机录制歌曲，并通过与上述相同的音频指纹识别过程运行录制。 然后我们可以开始在数据库中搜索匹配的哈希标签。

碰巧的是，许多哈希标签将对应于多首歌曲的音乐标识符。 例如，可能某首歌曲 A 听起来与某首歌曲 E 完全一样。当然，这并不奇怪 - 音乐家总是“借用”彼此的 licks 和 riff，而现在制作人都对其他歌曲进行采样时间。 每次我们匹配一个哈希标签时，可能匹配的数量会变少，但仅此信息可能不会将匹配范围缩小到一首歌曲。 所以我们还需要用我们的音乐识别算法检查一件事，那就是时间。

我们在俱乐部中录制的样本可能来自歌曲中的任何一点，因此我们不能简单地将匹配哈希的时间戳与样本的时间戳进行匹配。 但是，对于多个匹配的哈希，我们可以分析匹配的相对时间，从而增加我们的确定性。

例如，如果您查看上表，您将看到哈希标签30 51 99 121 195对应于歌曲 A 和歌曲 E。如果一秒钟后，我们匹配哈希34 57 95 111 200 ，那就多了一个匹配歌曲 A，但在这种情况下，我们知道哈希和时间差都匹配。

 // Class that represents specific moment in a song private class DataPoint { private int time; private int songId; public DataPoint(int songId, int time) { this.songId = songId; this.time = time; } public int getTime() { return time; } public int getSongId() { return songId; } }

让我们将i 1和i 2作为录制歌曲中的时刻，将j 1和j 2作为数据库中歌曲中的时刻。 我们可以说我们有两个匹配时差匹配，如果：

<span style=font-family: TimesNewRoman;> RecordedHash(i 1 ) = SongInDBHash(j 1 ) AND RecordedHash(i 2 ) = SongInDBHash(j 2 ) </span>

<span style=font-family: TimesNewRoman;>AND</span>

<span style=font-family: TimesNewRoman;> abs(i 1 - i 2 ) = abs(j 1 - j 2 ) </span>

这使我们可以灵活地从开头、中间或结尾录制歌曲。

最后，我们在俱乐部录制的歌曲的每一个时刻都不太可能与我们在录音室录制的库中同一首歌曲的每一个对应时刻相匹配。 录音会包含很多噪音，会在比赛中引入一些错误。 因此，我们没有尝试从匹配列表中排除除正确歌曲之外的所有歌曲，而是在最后，按可能性降序对所有匹配歌曲进行排序，我们最喜欢的是排名列表中的第一首歌曲。

从上到下

要回答这个问题，“Shazam 是如何工作的？” 这是整个音乐识别和匹配过程的概述，从上到下：

对于这种系统，数据库可能会变得非常庞大，因此使用某种可扩展的数据库非常重要。 对关系没有特别的需求，而且数据模型最终非常简单，因此使用某种 NoSQL 数据库是一个很好的例子。

沙赞如何运作？ 现在你知道了

这种歌曲识别软件可以用来寻找歌曲之间的相似之处。 既然您了解了 Shazam 的工作原理，您就可以看到除了简单地对出租车收音机上播放的怀旧歌曲进行 Shazam 扫描之外，它还有哪些应用程序。 例如，它可以帮助识别音乐中的抄袭，或者找出谁是蓝调、爵士、摇滚、流行或任何其他流派先驱的最初灵感来源。 也许一个很好的实验是用巴赫、贝多芬、维瓦尔第、瓦格纳、肖邦和莫扎特的古典音乐填充歌曲样本数据库，并尝试找出歌曲之间的相似之处。 你会认为鲍勃·迪伦、猫王和罗伯特·约翰逊都是抄袭者！

但我们仍然无法定罪他们，因为音乐只是我们听到、记忆和在脑海中重复的一种波，它会在其中演变和变化，直到我们在录音室录制它并将其传递给下一个伟大的音乐天才。