最近，BI.ZONE参加了HighLoad ++会议。 很显然，我们到达那里不仅是为了凝视别人的看台，还带来了一些有趣的东西。 公司不同部门的员工为会议嘉宾准备了任务，为此，我们提供了奖品。 Golang的任务之一是致力于声音识别。 我们请她的作者介绍一下她。
问题陈述
在我们的任务中，我们需要索引一定数量的曲目，并学习如何通过其样本在数据库中搜索原始成分。 在这种情况下，样本可能很吵，录制在不良的麦克风上，其频率可能不同。 大部分代码已经为参与者编写，他只需要实现指纹功能即可从轨道上删除指纹。
如何录制声音
显然，任何轨道都是具有模拟性质的机械波。 物理学中的波具有两个特征：频率和振幅。 关于声波，为简单起见，我们可以假设振幅是音量，频率是音高，尽管实际上，相同振幅的人听起来声音更大。
也就是说，从物理学的角度来看，每个乐曲都是用连续函数来描述的，这意味着任何一小首歌曲都将包含无限量的信息（尽管如果这是某种后朋克音乐，那么曲目中可能会包含少量信息）更少）。 因此，无法保存模拟信号；您将不得不处理其数字化。 模拟信号数字化的主要方法是脉冲编码调制，本节将对此进行讨论。 PCM包括三个阶段：离散化，量化和编码。 让我们简要分析一下它们各自发生的情况。
离散化
因此，我们具有幅度与时间的函数。 如果有人有疑问，频率在哪里，那么它将隐藏在功能图的折线后面。 她还不可见，但是稍后我们将把她拉出来。 由于我们在谈论模拟信号，因此该函数是连续的，并在整个可能的参数集中定义（从零到音轨结尾的任何实数）。 也就是说，我们随时都知道函数的值，并且有很多时间。 我们显然不需要那么多，因此只需要一些离散子集。 为此，我们将以固定的小间隔保存信号值。 它应该足够小，以免我们听到耳边的差异，但又要足够大，以免节省太多，因为这也是不可取的。
实际上，在数字化时，不是设置间隔，而是设置频率，称为“采样频率”。 根据任务的不同，采样频率可以从电话中的8 kHz到专业音频设备中的几千kHz。 在录音棚外进行普通聆听的音乐通常以44.1 kHz或48 kHz的频率存储。
量化
多亏了离散化，我们现在有了很多点，而不是连续的函数图，但是我们仍然无法使用它，我们需要进一步破坏声音。 幅度随时间变化的初始函数将连续幅度与连续时间进行了比较。 随着时间的流逝，我们已经弄清楚了，现在我们需要提出一个具有振幅的东西，因为它的当前值分散在实数集合中，太混乱了，以至于我们无法毫无问题地保存它们。 例如，其中肯定有一些非理性的东西，我们不舍入就无法以任何方式保存。
量化是一个过程，在此过程中，我们将幅度四舍五入为预选集中的值。 当然，我们希望幅度的数量为2的幂。 对于普通音频轨道，使用16位量化，即，振幅数将为65536（2到16度）。 专业录音的准确性更高，但是很少有人能分辨16位量化和24位量化。 因此，我们取二的幂，取一堆整数幅度，并将其称为量化级别。 然后可以说该信号在65 536个级别上进行了量化（声音权威，对吗？）。 每个振幅都舍入为一个电平，最终可以将其值存储为16位，并且通过耳朵，这种录音与模拟连续声音是无法区分的。
作为说明，您可以查看下面的图片，或使用Python生成自己的图片（代码甚至更低）。 插图的右上方显示了五个量化级别。 也就是说，该曲目将只有五个音量级别。
一些例子import numpy as np import matplotlib.pyplot as plt import math as m def f(x): return m.sin(x) q = 1/2
编码方式
在编码阶段，我们以易于理解的形式保存前面步骤的结果。 之前的所有操作通常都是由专用设备执行的，但是我们希望在计算机上有一个文件，或者在内存中有一个会出现振幅的阵列中。 因此，在此阶段，设备信号被转换为数字数组，我们将来将其称为PCM（脉冲编码调制）。 它的索引是条件时间（采样后的间隔索引），其振幅存储在其中，在量化阶段四舍五入为整数。
傅立叶变换
最初，我们有一个机械波，希望将其数字化，但是现在，我们有了一个数字化信号，并希望从中获取频率。 可以使用傅立叶变换实现所需的目标。 以防万一，我将在此问题上重述其应用价值。 傅立叶变换使您可以采用任何函数并将其分解为正弦和余弦之和。 我们对此感兴趣，因为正弦波和余弦波与振动有关，而声音与振动有关。 也就是说，使用傅立叶变换，您只需查看正弦和正弦（或余弦）参数前面的系数，就可以获取复杂振荡的成分，找出其幅度和频率。 例如，有这样的浪潮。
浪潮实际上，我们知道它是由函数10sin（3x）+ sin（x）+ 4sin（4x）+ 20sin（2x）定义的，但是现在，真正的声波由无数个这样的术语组成，我们希望能够使用它。 因此，让我们使用
FourierScope程序通过傅里叶变换运行此功能，并查看振幅频谱。
振幅谱这就是四个罪过的样子。 显而易见，该图对应于正弦系数及其参数。
应该澄清的是，实际上，它不是傅立叶变换本身的幂的证明，而是离散形式的幂的证明，适用于经过具有其所有离散化和量化的脉冲编码调制的信号。 提出一种用于离散傅立叶变换的算法将是多余的，因此，让我们就存在DFT及其改进的快速傅里叶变换（FFT）这一事实达成共识。 在这种情况下，FFT的应用含义如下：该算法在输入处接收一段PCM，并给出一个包含幅度的数组，而频点是索引。 由于转换是离散的，因此这是频率仓的问题，而不仅仅是频率问题。 实际上，期望您可以在整个文章中粗化信号，然后获得没有问题和不准确的频率是很天真的。 实际上，频率仓是FFT无法彼此区分的一整堆频率。
值得注意的是，从书籍和文章重写算法时，FFT的拼写经常不正确。 下面是使用FFT的更正确的代码，这正是我们期望其解决方案的参与者所期望的。
import "github.com/mjibson/go-dsp/fft" ... blocksCount := len(pcm) / fftWindowSize for i := 0; i < blocksCount; i++ { complexArray := fft.FFTReal(pcm[i*fftWindowSize : i*fftWindowSize+fftWindowSize]) // use complexArray... }
现代技术使您可以在短短几行中编写快速傅立叶变换。 FFT用于fftWindowSize大小的段，并返回一个复数数组，我们以后将使用该数组进行指纹识别。
通常，傅立叶变换是整个问题中最薄的地方。 首先，bin大小为$ \ frac {频率\采样} {大小\窗口} $。 因此，您可以扩大窗口并获得更多的频率，这很好，但是当然会带来负面影响。 窗口大小的增加导致我们以较大的间隔分析PCM并丢失短时声音的事实。 在不同的情况下，如果短声是作曲的一部分，这可能会使程序反复恶化，或者如果只是杂音，则可能会改善程序。 也许根本不影响任何事情。 在这种困难的情况下，程序员必须果断地采取行动：取一些好的数字，例如$ 2 ^ 9 $或$ 2 ^ {10} $，并尽量不要打扰那些不需要的复杂事物。 足以解决问题，但在严肃的应用程序中，您仍然必须使用一些汉明窗以及更多需要考虑的问题。
指纹识别
任务是学习如何具有可映射到轨道且对变化不敏感的哈希，并具有合成的频率和幅度。 它们可能非常不同：有些杂音，所有频率的偏移，并行播放另一首歌曲等等。 您还需要考虑到数据库可以同时包含许多需要彼此区分的相似磁道。 也许所有的轨道都不尽相同，问题不在于确定哪一个更合适，而是要了解没有一个合适。 通常，创造力有一定的范围。
您可以采用不同的方式进行打印。 假设以几种不同指标的列表形式进行散列。 其中包括，例如，零信号交叉的平均数量，BPM，平均频率值。 我在
Musicbrainz的先前版本中做了此操作，并且此方法的问题已
在此处编写。 而且，您可以考虑使用节奏算法等更抽象的概念，使用EM算法分析轨道（
本文 ）。 通常，完全的言论自由。 不幸的是，大多数提议的算法显然没有公开实现，因此仅采用和比较它们是行不通的。
本文介绍了主流实现。 可以分几行实现此算法特别好。 例如，在原始文章中，建议将频率划分为6个间隔，在每个间隔中找到最大幅度，取所有6个的平均值，并保存高于平均值的bin，但是许多其他实现方式也是可行的。
var freqBins = [...]int16{40, 80, 120, 180, 300} func getKeyPoints(frame []freq_domain) int { highScores := make([]float64, len(freqBins)) recordPoints := make([]uint, len(freqBins)) for bin := freqBins[0]; bin < freqBins[len(freqBins)-1]; bin++ { magnitude := frame[bin] binIdx := 0 for freqBins[binIdx] < bin { binIdx++ } if magnitude > highScores[binIdx] { highScores[binIdx] = magnitude recordPoints[binIdx] = (uint)(bin) } } return hash(recordPoints) }
上面的函数实现了指纹算法。 最后，将一组频率（或更确切地说是bins）传递给“ hash（）”函数，该函数应将多个数字数组转换为一个数字。 您可以通过任何合适的方式执行此操作，甚至可以尝试使用md5（尽管这不是一个好主意）。
关于测试
准备了几个测试用例：- 正常预测试，只有一首曲目。 原稿和样品完全重合。
- 另一个预测试有两个曲目。 原稿与样品重合。
- 索引了稍多一些的音轨，所有音轨都被交替搜索。
- 加载了大量曲目，但会对其进行搜索，但需要进行下采样。
- 降采样后对音轨建立索引，搜索原始音轨。
- 为多个相似的曲目建立索引，寻找相似的曲目，但不在数据库中。
- 索引了几条音轨，对其进行了搜索，但是有噪音。
一些有趣的链接
https://metacpan.org/pod/音频:: Ofa :: Utilhttps://www.researchgate.net/publication/228347102_A_Review_of_Audio_Fingerprintinghttp://www.freshmeat.net/projects/songprinthttps://link.springer.com/article/10.1007/s11265-005-4152-2https://github.com/acoustid/chromaprinthttps://laplacian.wordpress.com/2009/01/10/how-shazam-works/