Shazam如何工作？音乐识别算法，指纹识别和处理

本文概述

• 模数转换-信号采样
• 录音-捕捉声音
• 时域和频域
• 离散傅立叶变换
• 音乐识别：对歌曲进行指纹识别
• 音乐算法：歌曲识别
• 从上到下
• Shazam如何工作？现在你知道了

你会在俱乐部或餐厅听到熟悉的歌曲。你很久以前就听过这首歌, 这首歌的感伤感动你的内心。你迫切希望明天能记住它, 但是你不记得它的名字了！幸运的是, 在我们这个令人惊叹的未来世界中, 你拥有一部安装了音乐识别软件的手机, 并且你已保存。你可以放轻松, 因为软件会告诉你歌曲的名称, 并且你知道可以一次又一次地听到它, 直到它成为你的一部分……否则你就厌倦了。

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

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

模数转换-信号采样

真的是什么声音？是我们无法触摸但飞入我们的耳朵并使我们听到声音的某种神秘材料吗？

当然, 事实并非如此。我们知道, 实际上, 声音是一种振动, 它是压力和位移的机械波, 通过空气或水等介质传播。当这种振动传到我们的耳朵, 特别是耳膜时, 它会移动细小的骨头, 进而将这种振动进一步传播到我们内耳深处的细毛细胞。最终, 小毛细胞产生电脉冲, 通过听觉耳神经传递到我们的大脑。

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

转换涉及输入的量化, 并且必然引入少量误差。因此, 模数转换器不是对单个信号进行转换, 而是对非常小的信号进行多次转换-这个过程称为采样

奈奎斯特-香农定理告诉我们, 要捕获连续信号中的某个频率, 必须采用哪种采样率。特别是, 要捕获人类可以在音频信号中听到的所有频率, 我们必须以两倍于人类听力范围的频率对信号进行采样。人耳可以检测到大约20 Hz至20, 000 Hz之间的频率。结果, 音频通常以44100 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读取数据即可。 (在此示例中, 运行标志是一个全局变量, 该变量由另一个线程停止-例如, 如果我们具有带有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方波的傅立叶级数, 以及如何从正弦分量中生成(近似)方波。信号在上方的时域和下方的频域中显示。

资料来源：RenéSchwarz

在频域中分析信号极大地简化了许多事情。由于工程师可以研究频谱(信号在频域中的表示)并确定存在哪些频率和丢失哪些频率, 因此在数字信号处理领域更加方便。之后, 你可以进行滤波, 增加或减少某些频率, 或者仅从给定的频率中识别出准确的音调。

离散傅立叶变换

因此, 我们需要找到一种将信号从时域转换到频域的方法。在这里, 我们调用离散傅立叶变换(DFT)寻求帮助。 DFT是一种用于对离散(采样)信号执行傅里叶分析的数学方法。通过考虑那些正弦波是否以相同的速率采样, 它将一个函数的等距采样的有限列表转换成复杂正弦波的有限组合的系数列表, 该列表按其频率排序。

快速傅立叶变换(FFT)是DFT计算中最受欢迎的数值算法之一。到目前为止, FFT最常用的变种是Cooley–Tukey算法。这是一种分而治之的算法, 可将DFT递归地分为许多较小的DFT。评估DFT直接需要O(n2)运算, 而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的一个不幸的副作用是, 我们丢失了大量有关时序的信息。 (虽然从理论上讲可以避免, 但是性能开销很大。)对于一首三分钟的歌曲, 我们可以看到所有的频率及其幅度, 但是对于它们出现在歌曲中的时间我们一无所知。但这是使歌曲变得如此重要的关键信息！我们需要以某种方式知道每个频率出现在什么时间点。

这就是为什么我们引入一种滑动窗口或数据块, 然后仅转换这部分信息的原因。每个块的大小可以通过几种不同的方式确定。例如, 如果我们以44100 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的完全一样。当然, 这并不奇怪-音乐家们总是互相”借”舔和即兴演奏, 如今, 制作人都在采样其他歌曲时间。每当我们匹配一个哈希标签时, 可能匹配的次数就会减少, 但是仅此信息可能不会将匹配范围缩小到一首歌曲。因此, 我们还需要使用音乐识别算法检查另一件事, 那就是时机。

我们在俱乐部中记录的样本可能来自歌曲中的任何一点, 因此我们不能简单地将匹配的哈希值的时间戳与样本的时间戳进行匹配。但是, 使用多个匹配的哈希, 我们可以分析匹配的相对时间, 因此可以提高确定性。

例如, 如果你在上面的表中查找, 你将看到哈希标签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;
    }
}

让我们以i1和i2作为已录制歌曲中的时刻, j1和j2作为数据库中歌曲中的时刻。可以说我们有两个匹配, 其中时差匹配满足以下条件：

<span style = font-family：TimesNewRoman;> RecordedHash(i1)= SongInDBHash(j1)AND RecordedHash(i2)= SongInDBHash(j2)</ span>

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

<span style = font-family：TimesNewRoman;> abs(i1-i2)= abs(j1-j2)</ span>

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

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

从上到下

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

对于这种系统, 数据库可能会变得非常庞大, 因此使用某种可伸缩的数据库非常重要。不需要特殊的关系, 数据模型最终变得非常简单, 因此使用某种NoSQL数据库是一个很好的例子。

Shazam如何工作？现在你知道了

这种歌曲识别软件可用于查找歌曲之间的相似性。现在, 你已经了解了Shazam的工作原理, 你将看到, 除了Shazaming在出租车广播中播放的那首怀旧歌曲之外, 它还可以用于其他应用。例如, 它可以帮助识别音乐中的窃, 或者找出谁是布鲁斯, 爵士, 摇滚, 流行或任何其他流派的先驱者的最初灵感。也许一个很好的实验是用巴赫, 贝多芬, 维瓦尔第, 瓦格纳, 肖邦和莫扎特的古典音乐填充歌曲样本数据库, 并尝试找出歌曲之间的相似之处。你可能会认为, 甚至鲍勃·迪伦(Bob Dylan), 猫王(Elvis Presley)和罗伯特·约翰逊(Robert Johnson)都是窃者！

但是我们仍然不能对它们定罪, 因为音乐只是我们在脑海中听到, 记忆和重复的一种波, 在音乐中不断发展和变化, 直到我们将其录制在录音室中并传递给下一个伟大的音乐天才。

相关：机器学习理论及其应用简介：带有示例的可视教程