你在俱乐部或餐馆里听到一首熟悉的歌. 这首歌你早就听过一千遍了, 这首歌的感伤真的触动了你的心. 你迫切地想明天听到它，但你不记得它的名字! 幸运的是, in our amazing futuristic world, 你的手机安装了音乐识别软件, 你得救了. 你可以放松, 因为软件会告诉你歌曲的名字, 你知道你可以一遍又一遍地听到它，直到它成为你的一部分，或者你厌倦了它.

移动技术, along with the huge progress in audio 信号处理，给了我们 算法开发人员 the ability to create music recognizers. 最流行的音乐识别应用之一是 沙札姆. If you capture 20 seconds of a song, no matter if it’s intro, 节, 或合唱, 它会为记录的样本创建一个指纹, 查阅数据库, 并使用它的音乐识别算法来准确地告诉你正在听哪首歌.

But how does music recognition work? 沙札姆的算法 由其发明者王立中于2003年向世人展示. 在本文中，我们将介绍沙札姆音乐识别算法的基础知识，并回答以下问题:沙札姆是如何工作的?

Ana日志 to Digital - Sampling a Signal

搜索沙札姆 AI和沙札姆机器学习的读者可能会惊讶地发现，沙札姆算法不涉及这两种技术, 即使它们在当时确实以各种形式存在. 如果沙札姆不是人工智能音乐识别，那么它的具体方法是什么呢?

要回答这个问题，我们首先要问:声音到底是什么? 是某种神秘的物质，我们不能触摸，但它飞进我们的耳朵，让我们听到的东西吗?

当然, 这 is not quite the case. 我们知道，在现实中，声音是一种振动，它以 机械波 通过空气或水等介质的压力和位移. When that vibration comes to our ears, particularly the eardrum, 它移动小骨头，将振动进一步传递给内耳深处的小毛细胞. 最后, 这些小毛细胞产生电脉冲, 是通过听觉神经传递到大脑的吗.

录音设备相当接近地模仿了这一过程, 利用声波的压力将其转换成电信号. An actual sound wave in air is a 连续 压力信号. 在麦克风里, 遇到该信号的第一个电子元件再次将其转换为模拟电压信号, 连续. 这种连续的信号在数字世界中并不是很有用, so before it can be processed, it must be translated into a 离散信号 that can be stored digitally. 这是通过捕获代表信号幅度的数字值来完成的.

的 con版本 involves 量化 它必然会引入少量的误差. 的refore, instead of a single con版本, an ana日志-to-digital converter 对非常小的信号片段执行许多转换，这个过程称为 抽样

的 Nyquist-Shannon 的orem 告诉我们在连续信号中捕获某一频率所需的采样率. 特别是, 捕捉人类能在音频信号中听到的所有频率, 我们必须以人类听觉范围的两倍频率对信号进行采样. 人耳可以探测到大约在20赫兹到20,000赫兹之间的频率. 因此，音频通常以44100 Hz的采样率记录. This is the 抽样 rate of 光盘，也是最常用的比率 mpeg - 1 音频(VCD, SVCD, MP3). (这个特定的速率最初是由索尼公司选择的，因为它可以在修改后的视频设备上以每秒25帧的速度进行录制。朋友) or 30 frames per second (using an NTSC monochrome video recorder) and cover the 20,000赫兹的带宽被认为是与当时的专业模拟记录设备相匹配的必要条件.) So, 当选择需要记录的样本频率时，你可能会想要选择44,100 Hz.

Recording - Capturing the Sound

Let’s get into some 沙札姆 code.

Recording a sampled audio signal is easy. 因为现代声卡已经配备了模数转换器, just pick a programming language, find an appropriate library, set the frequency of the sample, number of channels (typically mono or stereo), 样本量(e).g. 16位样本). 然后像打开任何输入流一样打开声卡中的行，并写入字节数组. Here is how that can be done in 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
    返回新的AudioFormat(sampleRate, sampleSizeInBits, channels, signed, bigEndian);
}

final AudioFormat format = getFormat(); //Fill AudioFormat with the settings
DataLine.Info info = new DataLine.信息(TargetDataLine.类,格式);
final TargetDataLine 行 = (TargetDataLine) Audio系统.getLine(信息);
行.打开(格式);
行.开始();

读取数据 TargetDataLine. (在这个例子中， 运行 Flag是一个全局变量，它被另一个线程停止，例如, if we have GUI with the STOP button.)

OutputStream 出 = new ByteArrayOutputStream();
Running = true;

尝试{
    While (运行) {
        Int count = 行.读取buffer, 0, buffer.长度);
        if (count > 0) {
            出.write(buffer, 0, count);
        }
    }
    出.close ();
} catch (IOException e) {
    系统.犯错.println("I/O problems: " + e);
    系统.退出(1);
}

Time-Domain and Frequency-Domain

这个字节数组中的信号被记录在 时间域. 时域信号表示信号随时间的幅度变化.

在19世纪早期, 让-巴蒂斯特·约瑟夫·傅立叶做出了一个了不起的发现，即时域中的任何信号都相当于一些(可能是无限)数量的简单正弦信号的和, 假设每个正弦波分量都有一定的频率, 振幅, 和相位. 共同构成原始时域信号的一系列正弦波被称为its 傅里叶级数.

换句话说, 只要给出一组频率，就可以表示任何时域信号, 振幅, 和组成信号的每个正弦波相对应的相位. 信号的这种表示形式被称为 频域. 在某些方面, 频域充当时域信号的一种指纹或签名, 提供动态信号的静态表示.

下面的动画演示了1hz的傅立叶级数 方波，以及如何从正弦分量中产生(近似)方波. 信号显示在上面的时域和下面的频域.

来源: 雷内·施瓦兹

在频域中分析信号大大简化了许多事情. 在数字信号处理领域，由于工程师可以研究频谱(信号在频域中的表示)并确定存在哪些频率，因此更方便, 哪些是缺失的. 在那之后, 可以进行过滤, increase or decrease some frequencies, 或者只是从给定的频率中识别出确切的音调.

的 Discrete Fourier Transform

所以我们需要找到一种方法把信号从时域转换到频域. 这里我们呼吁 Discrete Fourier Transform (DFT)寻求帮助. DFT是一种用于执行的数学方法 傅里叶分析 on a discrete (sampled) signal. 它将函数的等间隔样本的有限列表转换为复正弦波的有限组合的系数列表, ordered by their frequencies, 通过考虑这些正弦波是否以相同的速率采样.

计算DFT最常用的数值算法之一是 快速傅里叶变换 (FFT). 到目前为止，FFT最常用的变体是 Cooley-Tukey算法. 这是一种分治算法，它递归地将一个DFT分成许多更小的DFT. Whereas evaluating a DFT directly requires O(n2) 操作，使用Cooley-Tukey FFT计算相同的结果 O(n 日志 n) 操作.

找到适合FFT的库并不难. 以下是其中的一些:

• C – FFTW
• C++ – EigenFFT
• Java – JTransform
• Python – NumPy
• Ruby – Ruby-FFTW3 (FFTW接口)

下面是一个用Java编写的FFT函数的例子. (FFT takes complex numbers as input. 要了解复数和三角函数之间的关系，请阅读 欧拉公式.)

public static Complex[] fft(Complex[] x) {
    int = x.长度;
    
    //偶数项的FFT
    Complex[] even = new Complex[N / 2];
    for (int k = 0; k < N / 2; k++) {
        偶[k] = x[2 * k];
    }
    Complex[] q = fft(even);

    //奇数项的FFT
    Complex[] odd = even; // reuse the array
    for (int k = 0; k < N / 2; k++) {
        奇数[k] = x[2 * k + 1];
    }
    Complex[] r = fft(奇数);

    / /把
    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.因为(k),数学.sin (k));
        Y [k] = q[k].+(周.次(r [k]));
        y[k + N / 2] = q[k].-(周.次(r [k]));
    }
    返回y;
}

这是一个信号在FFT分析前后的例子:

Music Recognition: Fingerprinting a 首歌

FFT的一个不幸的副作用是我们丢失了大量关于时间的信息. (虽然理论上这是可以避免的，但性能开销是巨大的.) For a three-minute song, 我们看到了所有的频率和它们的大小, 但我们不知道它们是什么时候出现在歌里的. 但这正是这首歌的关键信息! 我们需要知道每个频率出现的时间点.

That’s why we introduce kind of sliding window, 或者数据块, 然后变换这部分信息. 每个块的大小可以通过几种不同的方式确定. 例如, 如果我们把声音录下来, 在音响, 使用16位样本, at 44,100 Hz, one second of such sound will be 44,100 samples * 2 bytes * 2 channels ≈ 176 kB. If we pick 4 kB for the size of a chunk, 在这首歌的每一秒，我们将有44个数据块来分析. 对于音频识别所需的详细分析来说，这个密度已经足够了.

Now back to programming:

Byte audio [] = 出.toByteArray ()
int totalSize =音频.长度
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分析.

一旦我们知道了信号的频率构成, 我们可以开始形成这首歌的数字指纹. 这是整个沙札姆音频识别过程中最重要的部分. 的 main challenge here is how to distinguish, in the ocean of frequencies captured, which frequencies are the most important. 直观地，我们搜索具有最高幅度的频率(通常称为峰值).

然而，在一首歌中，强频率的范围可能在低C - C1(32)之间变化.70 Hz) and high C - C8 (4,186.01 Hz). This is a huge interval to cover. 所以不用一次分析整个频率范围, we can choose several smaller intervals, 根据重要音乐成分的共同频率选择的, and analyze each separately. 例如, we might use the intervals 这家伙 选择了沙札姆算法的实现. 这些是30 - 40赫兹, 40赫兹- 80赫兹和80赫兹- 120赫兹的低音(覆盖低音吉他), 例如), 120赫兹- 180赫兹和180赫兹- 300赫兹用于中高音调(包括人声和大多数其他乐器).

现在在每个区间内，我们可以简单地识别出具有最高幅度的频率. 这些信息构成了歌曲这一段的特征, 这个特征成为了整首歌的指纹的一部分.

public final int[] RANGE = new int[] {40,80,120,180,300};

// find 出 in which range is frequency
public int getIndex(int freq) {
    Int I = 0;
    while (RANGE[i] < freq)
        i++;
    返回我;
}
    
//结果是上一步得到的复矩阵
for (int t = 0; t < result.长度; t++) {
    for (int freq = 40; freq < 300 ; freq++) {
        //获取大小:
        double mag =数学.日志(结果[t](频率).Abs () + 1);

        // Find 出 which range we are in:
        int index = getIndex(freq);

        //保存最高幅度和相应频率:
        if (mag > highscores[t][index]) {
            points[t][index] = freq;
        }
    }
    
    //表单散列标签
    长h =散列(点[t] [0], [t][1],分[t][2],点[t] [3]);
}

private static final int FUZ_FACTOR = 2;

私有长散列(长p1，长p2，长p3，长p4) {
    return (p3 - (p3 % FUZ_FACTOR)) * 100000000 + (p3 - (p3 % FUZ_FACTOR))
            * 100000 + (p2 - (p2 % FUZ_FACTOR)) * 100
            + (p1 - (p1 % FUZ_FACTOR));
}

请注意，我们必须假设录音不是在完美的条件下完成的.e.例如“聋哑房间”)，因此我们必须包含模糊因素. 模糊因子分析应引起重视, 在一个真实的系统中, 程序应该有一个选项来根据记录的条件设置这个参数.

为了方便音频搜索，此签名将成为散列表中的键. 对应的值是这组频率在歌曲中出现的时间, 以及歌曲ID(歌曲名称和歌手). 下面是这些记录如何在数据库中显示的示例.

如果我们通过这个音乐识别过程来运行整个歌曲库, 我们可以建立一个数据库，拥有库中每首歌曲的完整指纹.

的 Music 算法: 首歌 Identification

识别当前在俱乐部中播放的歌曲, we record the song with our phone, 然后用上面提到的音频指纹识别程序对录音进行分析. 然后我们可以开始在数据库中搜索匹配的散列标签.

碰巧的是，许多散列标签将对应于多首歌曲的音乐标识符. 例如，歌曲A的某些片段听起来可能与歌曲E的某些片段完全相同. 当然, 这并不奇怪——音乐家们总是互相“借用”舔舐和即兴演奏, 如今，制作人一直在尝试其他歌曲. Each time we match a hash tag, the number of possible matches gets smaller, 但很可能仅凭这一信息并不能将匹配范围缩小到一首歌曲. 还有一件事我们需要用我们的音乐识别算法来验证, 这就是时机.

我们在俱乐部录制的样本可能来自这首歌的任何一点, 因此，我们不能简单地将匹配散列的时间戳与样本的时间戳进行匹配. 然而，使用多个匹配的哈希，我们可以分析 相对 比赛的时间，从而增加我们的确定性.

例如，如果您查看上面的表，您将看到该散列标签 30 51 99 121 195 corresponds to both 首歌 A and 首歌 E. If, one second later, we match the hash 34 57 95 111 200, 这是歌曲A的另一个匹配，但在这种情况下，我们知道哈希值和时差都是匹配的.

//表示歌曲中特定时刻的类
private class DataPoint {

    Private int time;
    private int songId;

    public DataPoint(int songId, int time) {
        这.songId = songId;
        这.Time =时间;
    }
    
    public int getTime() {
        返回时间;
    }
    public int get首歌Id() {
        返回songId;
    }
}

让我们把$i_1$和$i_2$作为录制歌曲中的时刻, $j_1$和$j_2$作为来自数据库的歌曲中的时刻. 我们可以说我们有两个匹配，如果三个东西是时间差匹配 所有真正的:

• $RecordedHash(i_1) = 首歌InDBHash(j_1)$
• $RecordedHash(i_2) = 首歌InDBHash(j_2)$
• $abs(i_1 - i_2) = abs (j_1 - j_2)$

这给了我们从开头、中间或结尾录制歌曲的灵活性.

最后, 我们在俱乐部录制的歌曲的每一个瞬间都不可能与我们库中同一首歌的每一个对应时刻相匹配, 录音棚录制. 录音中会有很多杂音，这会给比赛带来一些误差. 所以我们不需要从匹配列表中剔除除正确歌曲之外的所有歌曲, 在最后, 我们将所有匹配的歌曲按可能性降序排序, 我们最喜欢的是排行榜上的第一首歌.

从上到下

To answer the question, “沙赞是如何工作的?以下是整个音乐识别和匹配过程的概述，从上到下:

对于这种系统, the database can get pretty huge, 所以使用某种可扩展的数据库是很重要的. 的re is no special need for relations, 数据模型最终变得非常简单, 所以它是使用某种NoSQL数据库的好例子.

沙札姆是如何工作的? 现在你知道了

这种歌曲识别软件可以用来寻找歌曲之间的相似之处. Now that you understand how 沙札姆 works, 你可以看到它的应用不仅仅是在出租车收音机里播放怀旧歌曲. 例如, it can help to identify plagiarism in music, 或者找出谁是蓝调先驱的最初灵感来源, 爵士乐, 岩石, 流行音乐或任何其他流派. 也许一个好的实验是用巴赫的古典音乐填充歌曲样本数据库, 贝多芬, 维瓦尔第, 瓦格纳, 肖邦和莫扎特，试着找出歌曲之间的相似之处. 你可能会认为，就连鲍勃·迪伦、埃尔维斯·普雷斯利和罗伯特·约翰逊都是剽窃者!

But still we cannot convict them, because music is just a wave that we hear, memorize and repeat in our heads, 直到我们在录音室录制并将其传递给下一个伟大的音乐天才.