通过音频指纹识别重复歌曲
4.96/5 (337投票s)
解释了声音指纹识别算法，并提供了检测用户本地驱动器上重复文件的实际示例。
目录
引言
作为一名软件工程师，我一直对计算机如何能够被教会以智能的方式行事感兴趣，至少在一些我们可以在几秒钟内轻松解决的简单任务上。其中一项就是音频识别，近年来受到了深入的分析。因此，在本文中，您将接触到计算机科学领域的一个复杂任务：数字格式的模拟信号的有效比较和识别。例如，考虑一个音频信号 Ψ1，您想将其与另一个 Ψ2 进行比较，以确定它们是否来自同一首歌曲或音频对象。任何人都可以毫不费力地完成这项任务，但计算机却不那么直观地“聪明”。困难在于，这些信号中的每一个都可能具有不同的数字化格式，从而导致它们的二进制签名完全相反（导致逐字节比较过时）。这种不匹配也可能源于同一音频格式的各种内部特性的组合（比特率、采样率、通道数（单声道、立体声等））。即使您将文件转换为某些预定义的规范（例如，44100 Hz，立体声，WAVE PCM格式），由于可能的时间不对齐、噪声、失真或同一首歌曲的“响度级别”（“响度”在技术上定义为幅度级别），您仍然可能遇到二进制表示不同的问题。
因此，本文的目的是展示一种有效的信号处理算法，该算法可以实现一个能够胜任的声音指纹识别和信号识别系统。接下来将要描述的算法是由Google的研究人员开发的，并发表在“使用小波进行内容指纹识别”。在这里，我将尝试对文章中的算法进行一些解释，并讨论如何使用C#编程语言来实现它。此外，我还会涵盖算法中使用的数字信号处理的主题，以便您能够更清晰地了解整个系统。作为概念验证，我将向您展示如何开发一个简单的WPF MVVM应用程序（如果您不知道MVVM是什么，请不要立即去谷歌搜索，因为它将在后面进行解释）。唯一目的是检测本地驱动器上的重复音乐文件并通过音频内容进行分析。
概念概述
简而言之，如果您想通过感知相等性比较音频文件，您应该创建所谓的“指纹”（类似于人类指纹，它们唯一地描述了一个人的身份），并查看从不同音频源收集到的这些对象的集合是否匹配。逻辑上，相似的音频对象应该生成相似的指纹，而不同的文件应该产生不同的签名。这些指纹的要求之一是它们应该充当“容错哈希”，以便处理格式差异、噪声、“响度”等。音频指纹识别的简化概念可以可视化如下。
基本上，音频指纹识别算法能够将简短的、未标记的音频内容片段与相应的有关该内容的数据链接起来（这一切都是为了找到歌曲的独特特征，这些特征可以用于稍后回忆一个未知样本，或在已处理歌曲的数据库中查找重复项）。这类算法可用于各种不同的应用程序。
- 自动填充歌曲元数据（MusicBrainz）
- 识别当前播放的歌曲（Shazam）
- 管理音效库
- 监控广播节目
尽管声音指纹识别系统具有所有优势，但它仍面临一些挑战。其中之一是一个巨大的数据库需要搜索（想象一下YouTube用于监控音频版权问题的视频内容数据库）。通常，每首歌曲都会生成大量的指纹（在所描述的算法中，每个指纹的粒度为1.48秒，因此一首歌曲大约有200个对象）。总之，需要使用一种高效的搜索算法，该算法在解决方案规模化时能良好运行。最简单的方法是执行查询点与数据库中每个对象之间的简单比较。但是，由于此方法过于耗时，因此将使用k-最近邻解决方案（最小哈希+局部敏感哈希）。
指纹作为哈希值
简而言之，音频指纹可以看作是相应音频对象的压缩摘要。从数学上讲，指纹函数F将由大量位组成的音频对象X映射到只有有限数量位的指纹。因此，提取指纹的整个机制可以看作是一个哈希函数H，它将对象X映射到哈希值（也称为消息摘要）。哈希函数在计算机科学领域得到广泛应用的主要优点是，它们可以通过仅比较各自的哈希值H(X)和H(Y)来比较两个大型对象X和Y。后者之间的相等性意味着X和Y之间的相等性，并且错误概率非常低（即使不能完全消除冲突）。接下来，您可以看到哈希函数功能的概念图。
在图中，字符串值充当键，映射到哈希桶（整数），这些哈希桶在设计上更小，并且更易于比较。然而，完全不同的键总是可能占据同一个桶（Steve和Mark冲突）。那么，为什么我们需要开发一个完全基于指纹的新系统，而不是仅仅使用加密哈希函数呢？答案很简单。尽管将音频对象压缩到MP3格式和压缩到WAVE格式之间的感知差异非常小，但它们的二进制表示完全不同，这意味着H(MP3(X))和H(WAVE(X))将产生完全不同的消息摘要（哈希桶）。更糟糕的是，加密哈希函数通常非常敏感：原始对象中一个位的差异会导致完全不同的哈希值（因此，键中的微小退化会导致完全不同的哈希摘要）。当然，这并不让我们满意。我们希望有一个系统，它不考虑任何低级细节（二进制签名），而只分析音频信号，就像人类一样（充当一个“容错哈希”，不会过多关注不相关的差异）。
通用模式（指纹创建）
将要构建的框架（整个系统将基于此）将由几个不同的概念部分组成。在下一张图中，您可以可视化活动图，它抽象地描述了指纹创建的逻辑流程（此流程与使用小波进行内容指纹识别中描述的理论抽象相匹配，该算法基于此论文）。接下来，我将更详细地描述涉及的每个活动以及哪个组件负责它。
广义地说，该算法可以逻辑地分解为两个主要部分：指纹创建（从歌曲中提取独特的感知特征）和指纹查找（查询数据库）。由于许多组件同时参与这两项活动，因此它们将一起进行描述。
预处理输入信号
实际上，任何人计算机上的所有音频文件都以某种格式编码。因此，算法中的第一步（1）是将输入文件解码为PCM（脉冲编码调制格式）。PCM格式可以被认为是模拟信号的原始数字格式，其中信号的幅度在均匀的间隔内定期采样，每个样本被量化到数字步长范围内的最接近值。解码后，进行单声道转换和采样率降低。特别是，采样率、样本率或采样频率定义了从连续信号中每秒（或其他单位）采集的样本数，以创建离散信号。对于时域信号，采样率的单位是1/s。采样频率的倒数是采样周期或采样间隔，即样本之间的时间。由于算法中分析的频率带在318 Hz到2000 Hz之间，因此将输入采样率降低到5512 Hz被认为是安全且必需的操作。在降低采样率（通常从44100 Hz）时，我们将丢弃从人类感知角度来看不相关的信息，并专注于信号的重要特征。预处理使用Bass.Net库完成（在我看来，这是处理音频文件的最佳库）。使用新版本的SoundFingerprinting框架，您可以为此目的使用NAudio库。NAudio唯一的麻烦是，它在支持的音频格式方面没有太多灵活性。
检索样本数据时，将收集32位浮点样本，范围从-1.0到+1.0（float/Single数据类型-未裁剪）。您可以通过BASS_ChannelGetData方法检索样本数据。请注意，任何压缩文件（例如，MP3、OGG、WMA、FLAC）都将首先被解码，以便您始终收到PCM样本（这就是使用Bass库的巨大好处-它将以对许多现代文件格式的良好支持将输入文件解码为PCM）。另外，请注意，“样本”由表示所有通道（立体声/单声道）的离散信号所需的所有字节组成（如果以浮点格式检索，则每个样本为4个字节）。以下是一些转换示例，以便您可以轻松地进行数学运算。示例：16位，立体声，44.1kHz。
- 16位=每个通道（左/右）2字节=每个样本4字节
- 采样率为每秒44100个样本
- 一个“样本”的长度为1/44100秒（或1/44毫秒）
- 44100个样本代表1秒，等于176400字节
要进行不同值之间的转换，可以使用以下公式
- 毫秒 = 样本 * 1000 / 采样率
- 样本 = 毫秒 * 采样率 / 1000
- 采样率 = 样本 * 1000 / 毫秒
- 字节 = 样本 * 位数 * 通道数 / 8
- 样本 = 字节 * 8 / 位数 / 通道数
如果您想更深入地了解不同格式如何被处理、转换，可以参考这篇文章以获取详细信息。
从理论构造的角度来看，奈奎斯特定理指出，当采样率大于被采样信号的最大频率的两倍时，信号可以完美重建，或者等效地说，奈奎斯特频率（采样率的一半）超过了被采样信号的带宽。如果使用较低的采样率，原始信号的信息可能无法从采样信号中完全恢复。这就是为什么标准音频CD使用44100Hz的采样率，因为人耳通常只能听到高达20000Hz的频率。接下来，您可以看到使用Bass.Net库进行解码、单声道转换和采样率降低的源代码。
/// <summary>
/// Read mono from file
/// </summary>
/// <param name="filename">Name of the file</param>
/// <param name="samplerate">Output sample rate</param>
/// <param name="milliseconds">Milliseconds to read</param>
/// <param name="startmillisecond">Start millisecond</param>
/// <returns>Array of samples</returns>
/// <remarks>
/// Seeking capabilities of Bass where not used because of the possible
/// timing errors on different formats.
/// </remarks>
public float[] ReadMonoFromFile(string filename, int samplerate,
int milliseconds, int startmillisecond)
{
int totalmilliseconds =
milliseconds <= 0 ? Int32.MaxValue : milliseconds + startmillisecond;
float[] data = null;
//create streams for re-sampling
int stream = Bass.BASS_StreamCreateFile(filename, 0, 0,
BASSFlag.BASS_STREAM_DECODE | BASSFlag.BASS_SAMPLE_MONO |
BASSFlag.BASS_SAMPLE_FLOAT); //Decode the stream
if (stream == 0)
throw new Exception(Bass.BASS_ErrorGetCode().ToString());
int mixerStream = BassMix.BASS_Mixer_StreamCreate(samplerate, 1,
BASSFlag.BASS_STREAM_DECODE | BASSFlag.BASS_SAMPLE_MONO |
BASSFlag.BASS_SAMPLE_FLOAT);
if (mixerStream == 0)
throw new Exception(Bass.BASS_ErrorGetCode().ToString());
if (BassMix.BASS_Mixer_StreamAddChannel(mixerStream, stream, BASSFlag.BASS_MIXER_FILTER))
{
int bufferSize = samplerate * 10 * 4; /*read 10 seconds at each iteration*/
float[] buffer = new float[bufferSize];
List<float[]> chunks = new List<float[]>();
int size = 0;
while ((float) (size)/samplerate*1000 < totalmilliseconds)
{
//get re-sampled/mono data
int bytesRead = Bass.BASS_ChannelGetData(mixerStream, buffer, bufferSize);
if (bytesRead == 0)
break;
float[] chunk = new float[bytesRead/4]; //each float contains 4 bytes
Array.Copy(buffer, chunk, bytesRead/4);
chunks.Add(chunk);
size += bytesRead/4; //size of the data
}
if ((float) (size)/samplerate*1000 < (milliseconds + startmillisecond))
return null; /*not enough samples to return the requested data*/
int start = (int) ((float) startmillisecond*samplerate/1000);
int end = (milliseconds <= 0) ? size :
(int) ((float) (startmillisecond + milliseconds)*samplerate/1000);
data = new float[size];
int index = 0;
/*Concatenate*/
foreach (float[] chunk in chunks)
{
Array.Copy(chunk, 0, data, index, chunk.Length);
index += chunk.Length;
}
/*Select specific part of the song*/
if (start != 0 || end != size)
{
float[] temp = new float[end - start];
Array.Copy(data, start, temp, 0, end - start);
data = temp;
}
}
else
throw new Exception(Bass.BASS_ErrorGetCode().ToString());
return data;
}
请注意，本文所示的源代码与SoundFingerprinting框架中的源代码不匹配。这是因为该库经常更新，我编译了这些方法以便于理解。
创建频谱图
将信号预处理为5512 Hz PCM后，指纹识别算法的下一步（2）是构建音频输入的频谱图。在数字信号处理中，频谱图是显示信号的频谱密度如何随时间变化的图像。将信号转换为频谱图涉及几个步骤。首先，信号应被切分成重叠的帧。然后，每个帧应通过快速傅立叶变换，以获得随时间变化的频谱密度。这些变换步骤中使用的参数将与在其他音频指纹识别研究中被发现效果良好的参数相同（特别是在“高度鲁棒的音频指纹识别系统”中）：音频帧长371毫秒（2048个样本），每11.6毫秒（64个样本）采集一次，因此有31/32的重叠。对输入信号进行切分和分帧的机制可以可视化如下。
构建图像的频谱图涉及整个算法中最耗费CPU的操作——快速傅立叶变换（O(n*log(n))）。最初我为此目的使用了Exocortex库，但事实证明，最快的实现是由FFTW库提供的。尽管它需要P-Invocation，但预构建的FFT计划运行速度相当快。
傅立叶分析是一系列数学技术，都基于将信号分解为正弦波。如下图所示，离散傅立叶变换将一个N点输入信号转换为两个点输出信号。输入信号包含被分解的信号，而两个输出信号包含分量正弦波和余弦波的幅度。输入信号称为时域，而输出称为频域。这是因为输入FFT的最常见信号类型是由在规则时间间隔（在本例中为371毫秒的切片）采集的样本组成的。
频域包含与时域完全相同的信息，只是形式不同。如果您知道一个域，您可以计算另一个域。给定时域信号，计算频域的过程称为分解、分析、前向FFT或简称为FFT。如果您知道频域，计算时域称为合成或逆FFT。合成和分析都可以用方程形式和计算机算法来表示。
带通滤波
在每个切片上完成FFT变换后，输出频谱图被裁剪，以获得318Hz-2000Hz的频段（研究人员认为该频段足以代表文件的感知内容）。一般来说，这个频段可以被认为是人类听觉系统最相关的频率空间。虽然任何人能够听到的频率范围在很大程度上与环境因素有关，但普遍接受的听觉频率标准范围是20到20000Hz。低于20Hz的频率通常可以被感觉到而不是被听到，假设振动的幅度足够大。年轻人有时可以感知到高于20000Hz的频率，但高频是由于年龄和/或长时间暴露于非常大的噪音而导致听力下降的首批受影响的频率。在下表中，您可以可视化频率范围及其主要描述。可以看出，大多数相关的音频内容位于512-8192Hz的频率范围内，因为它定义了正常语音。
| 频率（Hz） | 倍频程 | 描述 |
| 16 - 32 | 1 | 人类的感知阈值，以及管风琴的最低低音音符。 |
| 32 - 512 | 2 - 5 | 节奏频率，低音和高音的低音音符所在的位置。 |
| 512 - 2048 | 6 - 7 | 定义人类语音的可懂度，使声音具有喇叭般或尖锐的音质。 |
| 2048 - 8192 | 8 - 9 | 为语音提供临场感，舌唇音和摩擦音所在的位置。 |
| 8192 - 16384 | 10 | 明亮度，钟声和钹声。在语音中，“S”字母的声音（8000-11000 Hz） |
回到算法，为了最小化输出维度（FFT变换后的每个帧都是一个大小为[0-1025]的向量），指定的318-2000Hz范围应编码为32个对数间隔的桶（因此，时域中的2048个样本减少到频域中的1025个桶，然后将它们以对数刻度求和为32个项）。因此，算法将每个时间帧减少64倍。下面是创建频谱图的代码，它使用了前面步骤中讨论的所有功能。
/// <summary>
/// Create log-spectrogram
/// </summary>
/// <param name="proxy">Proxy used in generating the spectrogram</param>
/// <param name="filename">Filename to be processed</param>
/// <param name="milliseconds">Milliseconds to be analyzed</param>
/// <param name="startmilliseconds">Starting point</param>
/// <returns>Logarithmically spaced bins within the power spectrum</returns>
public float[][] CreateLogSpectrogram(IAudio proxy, string filename,
int milliseconds, int startmilliseconds)
{
//read 5512 Hz, Mono, PCM, with a specific proxy
float[] samples = proxy.ReadMonoFromFile(filename, SampleRate,
milliseconds, startmilliseconds);
NormalizeInPlace(samples);
int overlap = Overlap;
int wdftSize = WdftSize;
int width = (samples.Length - wdftSize)/overlap; /*width of the image*/
float[][] frames = new float[width][];
float[] complexSignal = new float[2*wdftSize]; /*even - Re, odd - Img*/
for (int i = 0; i < width; i++)
{
//take 371 ms each 11.6 ms (2048 samples each 64 samples)
for (int j = 0; j < wdftSize /*2048*/; j++)
{
complexSignal[2*j] = (float) (samples[i*overlap + j]);
complexSignal[2*j + 1] = 0;
}
//FFT transform for gathering the spectrum
Fourier.FFT(complexSignal, wdftSize, FourierDirection.Forward);
frames[i] = ExtractLogBins(complexSignal);
}
return frames;
}
小波分解
一旦绘制了对数频谱图（在318-2000Hz范围内分布有32个桶，每11.6毫秒），算法的下一步（4）是将整个图像分割成切片（光谱子图像128x32），对应于1.48秒的粒度。从编程角度讲，构建对数频谱图后，您将得到其整个图像编码为一个[N][32]的双精度float数组，其中N等于“信号长度（毫秒）除以11.6毫秒”，32表示频率带的数量。一旦得到分割后的光谱子图像，它们将通过在每个图像上应用标准Haar小波分解来进一步减小。小波在音频检索任务中的使用是由于它们在图像检索中的成功应用（快速多分辨率图像查询）。换句话说，小波是一种波动状的振荡，其幅度从零开始，增加，然后逐渐减小回到零。它通常可以可视化为地震仪或心电图上看到的“短暂振荡”。小波的制作目的是使其具有特定的属性，从而使其适用于信号/图像处理。它们可以通过使用称为卷积的“移位、乘法和求和”技术来组合，并与未知信号的部分相结合以提取该信号的信息。小波的基本思想是根据尺度进行分析。因此，回到我们的算法，对于每个光谱图像，计算一个小波签名。我们不使用所有小波，而只保留最能表征歌曲的小波（前200个被认为是好的选择），从而使签名对噪声和其他退化具有抵抗力。先前图像处理研究中发现的一个有趣之处是，无需保留顶层小波的幅度；相反，我们可以简单地保留其符号（+/-）。这些信息足以保留歌曲的感知特征。
此特定框架将使用以下符号编码：正数 - 01，负数 - 10，零 - 00。此位向量的两个最重要的特征是它是稀疏的，并且能抵抗信号中可能出现的小退化。稀疏性使其易于通过使用最小哈希进一步降低维度。值得一提的是，在此阶段（在前200个小波提取之后），我们为指纹获得的位向量长度为8192（其中只有200个元素等于1，其余等于0）。下面是标准Haar小波分解的源代码。
/// <summary>
/// Haar wavelet decomposition algorithm
/// </summary>
public class HaarWavelet : IWaveletDecomposition
{
#region IWaveletDecomposition Members
/// <summary>
/// Apply Haar Wavelet decomposition on the frames
/// </summary>
/// <param name = "frames">Frames to be decomposed</param>
public void DecomposeImageInPlace(float[][] frames)
{
DecomposeImage(frames);
}
#endregion
/// <summary>
/// Decomposition taken from
/// Wavelets for Computer Graphics: A Primer Part
/// by Eric J. Stollnitz Tony D. DeRose David H. Salesin
/// </summary>
/// <param name = "array">Array to be decomposed</param>
private static void DecomposeArray(float[] array)
{
int h = array.Length;
for (int i = 0; i < h; i++)
/*doesn't introduce any change in the final fingerprint image*/
array[i] /= (float)Math.Sqrt(h);
/*because works as a linear normalizer*/
float[] temp = new float[h];
while (h > 1)
{
h /= 2;
for (int i = 0; i < h; i++)
{
temp[i] = (float)((array[2 * i] + array[2 * i + 1]) / Math.Sqrt(2));
temp[h + i] = (float)((array[2 * i] - array[2 * i + 1]) / Math.Sqrt(2));
}
for (int i = 0; i < 2*h; i++)
{
array[i] = temp[i];
}
}
}
/// <summary>
/// The standard 2-dimensional Haar wavelet decomposition
/// involves one-dimensional decomposition of each row
/// followed by a one-dimensional decomposition of each column of the result.
/// </summary>
/// <param name = "image">Image to be decomposed</param>
private static void DecomposeImage(float[][] image)
{
int rows = image.GetLength(0); /*128*/
int cols = image[0].Length; /*32*/
for (int row = 0; row < rows /*128*/; row++) /*Decomposition of each row*/
DecomposeArray(image[row]);
for (int col = 0; col < cols /*32*/; col++) /*Decomposition of each column*/
{
float[] column = new float[rows];
/*Length of each column is equal to number of rows*/
for (int row = 0; row < rows; row++)
column[row] = image[row][col]; /*Copying Column vector*/
DecomposeArray(column);
for (int row = 0; row < rows; row++)
image[row][col] = column[row];
}
}
}
接下来，您可以看到使用Haar分解转换的图像（转换前后）。在音频指纹识别的情况下，通过对音频输入的频谱图应用这种变换，我们将看到连续指纹的易于识别的模式。稍后将给出示例。
在前面的段落中，我描述了指纹创建算法；接下来，您可以可视化执行实际任务的方法。正如您所见，首先创建对数频谱图，然后将图像分割成1.48秒的光谱图像（从中将构建实际的指纹）。我应该强调，两个连续指纹之间的“距离”可以通过使用IStride接口来确定。本质上，两个项目之间应该跳过多少秒没有最佳答案，这主要通过实际测试来确定。在“使用小波进行内容指纹识别”中，数据库创建使用了静态的928毫秒步幅，查询使用了随机的0-46毫秒步幅（使用随机步幅是为了最小化偶然时间对齐的不幸效果）。
/// <summary>
/// Create fingerprints according to the Google's researchers algorithm
/// </summary>
/// <param name="proxy">Proxy used in reading from file</param>
/// <param name="filename">Filename to be analyzed</param>
/// <param name="stride">Stride between 2 consecutive fingerprints</param>
/// <param name="milliseconds">Milliseconds to analyze</param>
/// <param name="startmilliseconds">Starting point of analysis</param>
/// <returns>Fingerprint signatures</returns>
public List<bool[]> CreateFingerprints(IAudio proxy, string filename,
IStride stride, int milliseconds, int startmilliseconds)
{
float[][] spectrum =
CreateLogSpectrogram(proxy, filename, milliseconds, startmilliseconds);
int fingerprintLength = FingerprintLength;
int overlap = Overlap;
int logbins = LogBins;
int start = stride.GetFirstStride() / overlap;
List<bool[]> fingerprints = new List<bool[]>();
int width = spectrum.GetLength(0);
while (start + fingerprintLength < width)
{
float[][] frames = new float[fingerprintLength][];
for (int i = 0; i < fingerprintLength; i++)
{
frames[i] = new float[logbins];
Array.Copy(spectrum[start + i], frames[i], logbins);
}
start += fingerprintLength + stride.GetStride() / overlap;
WaveletDecomposition.DecomposeImageInPlace(frames); /*Compute wavelets*/
bool[] image = ExtractTopWavelets(frames);
fingerprints.Add(image);
}
return fingerprints;
}
此方法返回实际指纹，这些指纹将通过最小哈希+LSH技术进一步降低维度。
对指纹进行最小哈希
在处理的这个阶段，我们已经获得了8192位长的指纹，我们希望通过创建每个项目的紧凑表示来进一步减小其长度。因此，在算法的下一步（5）中，我们探索使用最小哈希来计算这些稀疏位向量的子指纹。其使用已被证明在高效搜索相似集合方面非常有效。其工作原理如下：将一列视为具有1的行集（考虑C1和C2为两个指纹）。那么两个列C1和C2的相似度为Sim(C1, C2) = (C1∩C2)/(C1∪C2)。
这个相似度指标称为Jaccard相似度：它是一个介于0和1之间的数字；当两个集合不相交时为0，当它们相等时为1，否则介于0和1之间。在探讨最小哈希的工作原理之前，我将指出它一个非常有用的特性：MinHash(C1) = MinHash(C2)的概率恰好等于Jaccard相似度。这将使我们能够通过有效地将相似项（相似度指数大于60-70%）哈希到相同的桶中来使用该算法（这正是我们感兴趣的——一种“容错哈希”方法，它不会过多关注两个键之间的小差异）。最小哈希技术适用于二元向量：选择所有向量位置的一个随机但已知的重排。然后，对于每个向量排列，测量第一个‘1’出现在哪个位置。由于系统将使用8192位大小的指纹，因此排列向量将包含从0到8192的随机索引。对于给定的排列，如果第一个‘1’的位置在两个位向量中都相同，则哈希值一致；如果第一个‘1’的位置在一个向量中有‘1’而在另一个向量中没有，则它们不一致。请注意，这正是所需；它根据匹配的“开”位置来测量稀疏位向量的相似度。我们可以重复上述过程多次，每次使用新的位置排列。如果我们重复p次过程，使用p个不同的排列，我们将获得位向量的p个大致独立投影（例如，p=100个排列）。
您可以看到下面最小化给定指纹的方法。
/// <summary>
/// Compute Min-Hash signature of a given fingerprint
/// </summary>
/// <param name="fingerprint">Fingerprint to be hashed</param>
/// <returns>Min hashes of the fingerprint
/// (size equal to number of permutations)</returns>
public int[] ComputeMinHashSignature(bool[] fingerprint)
{
bool[] signature = fingerprint;
int[] minHash = new int[_permutations.Count]; /*100*/
for (int i = 0; i < _permutations.Count /*100*/; i++)
{
minHash[i] = 255;
/*The probability of occurrence of 1 after
position 255 is very insignificant*/
int len = _permutations[i].Length;
for (int j = 0; j < len /*256*/; j++)
{
if (signature[_permutations[i][j]])
{
minHash[i] = j; /*Looking for first occurrence of '1'*/
break;
}
}
}
return minHash; /*Array of 100 elements with bit turned ON if
permutation captured successfully a TRUE bit*/
}
如果您想知道排列是如何生成的，我很抱歉地告诉您，这个过程一点也不直接。该方法基于“排列分组：音频和图像检索的智能哈希函数”论文。它探讨了如何生成分布大致相同的随机排列。与其仅仅选择高熵排列放在一起，不如采用更严谨的方法，即利用排列之间的互信息（MI）来指导排列的分组。互信息是衡量知道一个变量的值能减少另一个变量的不确定性的度量。为了确定是否存在足够的互信息方差来使用它作为有效信号，对于100个排列，我们检查了所有对之间的互信息（100*99/2个样本）。为了创建低互信息排列的组以便将它们放在哈希块中，使用了贪婪选择过程，该过程大致基于“用依赖树逼近离散概率分布”中使用的算法。用于生成排列的实用工具以及与此研究相关的许多其他有用功能可以在此处找到（在编写应用程序和相关工具时使用的项目托管）。我不会描述整个排列分组算法，因为它超出了本文的范围。如果您有兴趣，可以使用本节中的材料来研究该主题。
使用局部敏感哈希解决k-最近邻问题
总的来说，到目前为止，我们已经通过使用不同的算法（如傅立叶变换、Haar小波分解、选择包含最相关信息的前T个小波以及最小哈希算法）成功地降低了初始向量的维度。从初始光谱子图像（128x32浮点数）开始，我们收集了一个包含100个8位整数的向量，这些整数代表了指纹本身。然而，即使经过如此高的维度降低，也很难创建一个有效的系统来搜索长度为100的向量。因此，在本文的下一步（6）中，我们探索了局部敏感哈希的使用，它是一类重要的寻找最近邻的算法。它在所需的比较数量方面被证明是高效的，并提供了鲁棒性的属性。特别是，最近邻问题定义如下：给定一组n个点，构建一个数据结构，该数据结构能够接收任何查询点，并报告最接近查询点的数据点。这个问题在几个领域中具有重要意义；例如数据压缩、数据库和数据挖掘、信息检索、图像和视频数据库、机器学习、模式识别、统计和数据分析。
通常，感兴趣的每个对象（文档、图像等）的特征被表示为R<sup>d</sup>中的一个点，并且使用距离度量来衡量对象的相似性。那么基本问题就是对查询对象进行索引或相似性搜索。特征的数量（即维度）范围从几十到数百万。例如，可以将一个1000x1000的图像表示为一个1,000,000维空间中的向量，每个像素对应一个维度。为了成功应用局部敏感哈希的概念，我们需要使用多个哈希函数对点进行哈希，以确保对于每个函数，与彼此靠近的对象发生冲突的概率远远高于远离的对象（最小哈希函数可以适应此要求）。然后，可以通过哈希查询点并检索存储在包含该点的存储桶中的元素来确定近邻。最近邻问题是一个优化问题的示例：目标是找到一个最小化特定目标函数（在此例中为到查询点的距离）的点。为了简化表示，我们说点p是点q的R近邻，如果p和q之间的距离最多为R。最容易想象的是：对表的经典SQL查询将返回您在where子句中提供的精确匹配。相反，k-最近邻算法将不仅返回精确匹配，还会返回与查询参数相似的项。例如，假设您想从数据库中选择所有包含“port”一词的图书。该算法不是返回精确匹配，而是不仅返回包含初始词的图书，还返回包含单词：support、report、airport、deport、portfolio等。这可能有什么用？某些应用程序可以使用此功能来解决特定问题（查找相似文本、网站、图像、音频项等）。在我们的案例中，这不仅仅是查找相似音频对象的一种方式，也是提高搜索速度的一种方式（如果应用程序规模化，在包含100个8位值的向量的数据库中进行搜索是不可行的）。
在本文讨论的音频指纹识别算法中，我们使用来自上一节讨论的最小哈希算法的L个哈希函数（其中每个哈希函数代表B个最小哈希的连接值）。例如，25个哈希函数（表示为4个连接的最小哈希）和25个相应的哈希表足以有效地将初始数据点划分到相应的空间地址。可以通过以与初始音频对象相同的方式划分探针特征向量并收集相应哈希桶中的条目来有效地检索候选邻居。最终的潜在邻居列表可以通过投票计数来创建，每个哈希为其索引桶中的条目投出选票，并保留获得一定最小选票数v的候选者。如果v = 1，则取候选列表的并集；如果v=L，则取交集。下面是使用最小哈希值构建LSH表的源代码。
/// <summary>
/// Compute LSH hash buckets which will be inserted into hash tables.
/// Each fingerprint will have a candidate in each of the hash tables.
/// </summary>
/// <param name = "minHashes">Min Hashes gathered from every fingerprint [N = 100]</param>
/// <param name = "numberOfHashTables">Number of hash tables [L = 25]</param>
/// <param name = "numberOfMinHashesPerKey">Number of min hashes per key [N = 4]</param>
/// <returns>Collection of Pairs with Key = Hash table index, Value = Hash bucket</returns>
public Dictionary<int, long> GroupMinHashToLSHBuckets(int[] minHashes,
int numberOfHashTables, int numberOfMinHashesPerKey)
{
Dictionary<int, long> result = new Dictionary<int, long>();
const int maxNumber = 8; /*Int64 biggest value for MinHash*/
if (numberOfMinHashesPerKey > maxNumber)
throw new ArgumentException("numberOfMinHashesPerKey cannot be bigger than 8");
for (int i = 0; i < numberOfHashTables /*hash functions*/; i++)
{
byte[] array = new byte[maxNumber];
for (int j = 0; j < numberOfMinHashesPerKey /*r min hash signatures*/; j++)
{
array[j] = (byte)minHashes[i * numberOfMinHashesPerKey + j];
}
long hashbucket = BitConverter.ToInt64(array, 0); //actual value of the signature
result.Add(i, hashbucket);
}
return result;
}
检索
最小哈希指纹被划分为LSH表后，可以认为从音频文件中提取签名过程已完成。现在，我们如何才能找到相似的歌曲，或者仅凭一个小片段检索有关未知音频的信息？整个检索过程（检测查询歌曲）与创建过程类似，只是此时不会对整首歌曲进行指纹识别。您可以选择任意秒数进行指纹识别，在准确性和处理时间之间进行权衡。重复这些步骤，直到指纹被划分为哈希表。完成后，将查询发送到存储中，以查看有多少哈希表包含相应的哈希值。如果在查询期间获得了超过v张选票（超过v个表返回相同的指纹），则该指纹被认为是潜在匹配（在“使用小波进行内容指纹识别”中，使用了2-5张选票的阈值）。所有匹配项都被选中并进行分析，以找到最佳候选者（可以通过计算查询与潜在候选者之间的简单汉明距离来查看哪个项目最相关）。在开发重复项检测器算法的情况下，提取的原理略有不同。阈值选票数增加到8（25个表中有8个应返回相同结果），并且至少有5%的总查询指纹应投票给同一首歌曲。一旦满足此标准，该歌曲就被认为是重复项。总的来说，所有这些参数都是凭经验确定的，所以您可能会找到比这里描述的更准确的配置。例如，您可以降低阈值选票数，以获得也包含与重复项匹配的歌曲的混音版本（这总是在假阳性和目标函数之间进行权衡）。下面是提取模式的代码。
/// <summary>
/// Get tracks that correspond to a specific hash signature and pass the threshold value
/// </summary>
/// <param name = "hashSignature">Hash signature of the track</param>
/// <param name = "hashTableThreshold">Number of threshold tables</param>
/// <returns>Possible candidates</returns>
public Dictionary<Track, int> GetTracks(HashSignature hashSignature, int hashTableThreshold)
{
Dictionary<Track, int> result = new Dictionary<Track, int>();
long[] signature = hashSignature.Signature;
for (int i = 0; i < numberOfHashTables; i++)
{
if (hashTables[i].ContainsKey(signature[i]))
{
HashSet<Track> tracks = hashTables[i][signature[i]]; // get the set of tracks that map to a specific hash signature
// select all tracks except the original one
foreach (Track track in tracks.Where(t => t.Id != hashSignature.Track.Id))
{
if (!result.ContainsKey(track))
{
result[track] = 1;
}
else
{
result[track]++;
}
}
}
}
// select only those tracks that passed threshold votes
Dictionary<Track, int> filteredResult = result.Where(item => item.Value >= hashTableThreshold).ToDictionary(item => item.Key, item => item.Value);
return filteredResult;
}
摘要
构建指纹需要许多步骤，因此丢失它们之间的所有连接并不罕见。为了简化解释，接下来您可以看到一个通用图像，它将帮助您将它们可视化在一起。这是一个处理44100Hz，立体声，.mp3文件（Prodigy - No Good）的完整示例。具体来说，活动流程如下。
- 从图像中可以看出，输入文件有两个通道（立体声）。在第一步中，歌曲被降采样到5512Hz，单声道。请注意，输入信号的形状没有改变。
- 一旦信号降采样，就会构建其对应的频谱图。
- 频谱图被对数化并分割成光谱图像，这些图像将进一步表示指纹本身。
- 每个光谱帧都使用Haar小波分解进行变换，并在原始图像中保留Top-200小波。注意连续指纹之间的明显模式。在时间上具有相似的小波签名将有助于我们识别歌曲，即使在创建和查询指纹之间存在小的时间不对齐。
- 每个指纹都编码为位向量（长度8192）。
- 使用最小哈希算法生成相应的签名。
- 最后，使用局部敏感哈希，每个指纹的最小哈希签名分布在25个哈希表中，这些表稍后将用于查找。
声音指纹框架
在实现算法的过程中，我启动了一个开源项目，它提供了易于使用的方法，这些方法利用了所描述的算法。如果您想在自定义项目中使用它，可以访问Sound Fingerprinting GitHub存储库以获取最新的源代码。在那里，您可以找到该库的详细描述以及可用于各种项目的配套源代码。下面是一个代码示例，展示了如何从音频文件中生成声音指纹，这些指纹可以存储并用于后续的识别。
public List<byte[]> CreateFingerprintSignaturesFromFile(string pathToAudioFile)
{
FingerprintUnitBuilder fingerprintBuilder = new FingerprintUnitBuilder();
return fingerprintBuilder.BuildFingerprints()
.On(pathToAudioFile)
.WithDefaultFingerprintingConfiguration()
.RunAlgorithmWithHashing()
.Result;
}
该框架利用了.NET的任务并行库，因此指纹识别以所谓的“工作单元”执行：每个单元（歌曲）在单独的线程中进行预处理。并行处理单元的数量由客户端代码控制。
生成指纹签名后，您可能希望将其存储以备将来检索。下面是一个使用ModelService类将指纹保存到默认底层存储的代码片段。默认存储是MSSQL数据库，其初始化脚本可以在此处找到。
public void StoreFingeprintSignaturesForTrack(List<byte[]> fingerprintSignatures, Track track)
{
ModelService modelService = new ModelService();
List<SubFingerprint> fingerprintsToStore = new List<SubFingerprint>();
foreach (var fingerprint in fingerprintSignatures)
{
fingerprintsToStore.Add(new SubFingerprint(fingerprint, track.Id));
}
modelService.InsertSubFingerprint(fingerprintsToStore);
}
一旦将指纹插入数据库，您可能希望稍后查询存储以识别您拥有样本的歌曲。查询样本的来源可能有所不同：文件、URL、麦克风、收音机调谐器等。这取决于您的应用程序从哪里获取样本。
public Track GetBestMatchForSong(string queryAudioFile)
{
FingerprintQueryBuilder fingerprintQueryBuilder = new FingerprintQueryBuilder();
return fingerprintQueryBuilder.BuildQuery()
.From(queryAudioFile)
.With<DefaultFingerprintingConfiguration, DefaultQueryConfiguration>()
.Query()
.Result
.BestMatch;
}
演示MVVM项目
将使用所描述算法的应用程序将检测本地计算机上的重复文件。总体任务非常简单。首先，它将处理选定文件夹中的所有音频文件，然后尝试检测哪些文件具有相同的签名，从而成为彼此的重复项。它将使用WPF框架构建，特别是MVVM模式，该模式随着去年的扩展而变得越来越受欢迎。Model-View-ViewModel (MVVM) 是软件工程中使用的架构模式，起源于Microsoft，是Martin Fowler引入的Presentation Model设计模式的特化。MVVM旨在利用WPF的特定功能，通过几乎移除视图层中的所有“代码隐藏”来更好地促进视图层开发与模式其他部分的剥离。MVVM模式的组成部分包括。
- 模型：与经典的MVC模式一样，模型指的是。
- 表示真实状态内容的面向对象模型（面向对象方法），或
- 表示该内容的數據存取層（以數據為中心的處理方法）。
- 视图：负责定义用户在屏幕上看到的结构的布局和外观。理想情况下，视图纯粹用XAML定义，除了构造函数中标准的
InitializeComponent()方法调用之外，没有代码隐藏。 - 视图模型：它充当视图和模型之间的中介，并负责处理视图逻辑。视图模型以视图可以轻松使用的方式提供数据。视图模型从模型中检索数据，然后使这些数据可供视图使用，并可能以某种方式重新格式化数据，使其更易于视图处理。视图模型还提供命令的实现，用户在视图中发起这些命令。例如，当用户单击UI中的按钮时，可能会触发视图模型中的命令。视图模型还可能负责定义影响视图中某些显示方面的逻辑状态更改，例如表示某个操作正在进行中。
除了理解这三个组件的职责外，理解组件之间的交互方式也很重要。最高层面，视图知道视图模型，视图模型知道模型，但模型不知道视图模型，视图模型也不知道视图。
MVVM依赖于WPF的数据绑定功能来管理视图和视图模型之间的链接。MVVM应用程序中利用这些数据绑定功能的重要特性是。
- 视图可以通过绑定到视图模型实例的属性来向用户显示丰富的格式化数据。如果视图订阅了视图模型中的事件，那么视图模型也可以使用这些事件将任何属性值更改通知视图。
- 视图可以通过使用命令调用视图模型中的方法来发起操作。
- 如果视图订阅了视图模型中定义的事件，那么视图模型可以使用这些事件将任何验证错误通知视图。
视图模型通常通过调用模型类中的方法来与模型进行交互。模型也可能需要能够通过使用视图模型订阅的标准事件集将错误报告回视图模型（请记住，模型不知道视图模型）。在某些场景中，模型可能需要能够将底层数据的更改报告回视图模型，并且模型也应该使用事件来执行此操作。MVVM模式中职责的清晰分离带来了许多好处。
- 在开发过程中，开发人员和设计人员可以更独立、更并发地处理他们的组件。设计人员可以专注于视图，如果他们使用Expression Blend，他们可以轻松地生成示例数据来工作，而开发人员可以处理视图模型和模型组件。
- 开发人员可以为视图模型和模型创建单元测试，而无需使用视图。视图模型的单元测试可以测试与视图完全相同的功能。
- 应用程序的用户界面（UI）可以轻松地重新设计，而无需更改代码，因为视图完全用XAML实现。新版本的视图应与现有视图模型配合使用。
- 如果存在封装现有业务逻辑的模型实现，那么更改可能会很困难或有风险。在这种情况下，视图模型充当模型类的适配器，使我们能够避免对模型代码进行任何重大更改。
下面是一个简单的示例，展示了视图模型如何绑定到视图，从而使开发人员能够完全将应用程序的底层逻辑与UI分离。
<Border CornerRadius="5">
<ItemsControl ItemsSource="{Binding Workspaces}" Margin="10,10,10,10"></ItemsControl>
</Border>
视图定义了一个ObservableCollection的Workspaces，任何派生自ViewModelBase的视图模型都可以添加到其中。通过这种方式，视图可以在其边界内封装任何组件。在下面的代码中，您可以看到所选的视图模型是如何通过将其添加到MainWindowViewModel的Workspaces集合中来绑定到MainWindow的。
/// <summary>
/// Main window view model
/// </summary>
public class MainWindowViewModel : ViewModelBase
{
ObservableCollection<ViewModelBase> _workspaces;
/// <summary>
/// Parameterless constructor
/// </summary>
public MainWindowViewModel()
{
/*Adding PathList view model to workspaces collection*/
ViewModelBase pathList = new PathListViewModel();
Workspaces.Add(pathList);
}
/// <summary>
/// Workspaces
/// </summary>
public ObservableCollection<ViewModelBase> Workspaces
{
get { return _workspaces ?? (_workspaces =
new ObservableCollection<ViewModelBase>()); }
private set { _workspaces = value; }
}
}
UI与底层视图模型之间的交互通过命令完成，这些命令最终取代了事件处理程序和发布-订阅模式的使用。这带来了许多巨大的好处。其中之一是您可以对UI逻辑进行自动化测试，而无需进行挂钩和其他棘手的变通方法。在MVVM模式中，实现操作的责任在于视图模型，您应该避免在代码隐藏类中放置代码。因此，您应该通过绑定将控件连接到视图模型中的方法。因此，在您的视图中，您定义了在执行操作后将调用的命令。例如，请考虑以下绑定到StartCommand命令的按钮。
<Button Command="{Binding StartCommand}" Content="Start" />
一旦绑定，您应该在相应的视图模型类中定义StartCommand命令。
/// <summary>
/// Start processing the songs
/// </summary>
public ICommand StartCommand
{
get
{
return _startCommand ?? (_startCommand = new RelayCommand(
StartProcessing, CanStartProcessing));
}
}
StartProcessing和CanStartProcessing只是委托到用户单击该按钮时将调用的方法（CanStartProcessing在每次UI刷新时调用，以查看用户是否允许执行操作）。这非常有用，一旦您开发了一个依赖于早期事件的方法（例如，处理一首歌曲依赖于其选择，因此在用户选择一首歌曲之前，开始命令将是禁用的）。
依赖注入及其容器
总的来说，MVVM模式最重要的特性之一是关注点分离。目标是使应用程序的组件尽可能独立，并尽可能减少相互依赖。在理想情况下，每个组件都不了解其他任何组件，并且只通过抽象接口处理应用程序的其他区域。这就是所谓的松耦合，它使得测试和修改应用程序更加容易。即使您只能通过接口定义组件之间的交互，但依赖于类的使用者和该类的实现之间仍然存在依赖关系。以“重复歌曲检测器”为例：指纹存储库负责运行实际算法并将结果存储在底层存储中。存储库使用的存储是未知的，因为它仅通过接口IStorage访问所有相关方法（CRUD操作）。尽管这种方法在一定程度上解耦了组件，但Repository类仍然负责实例化对象本身。
private IStorage _storage; //storage object
public Repository()
{
//Create RAM storage for the repository
_storage = new RamStorage(NUMBER_OF_HASH_TABLES);
}
这种类型的耦合将产生以下依赖。
正如您所看到的，存在一个实例化依赖，它不允许我们根据我们想要测试的不同场景来切换存储（除非我们更改代码并重新编译应用程序）。我们需要一种方法来获取实现给定接口的对象，而无需直接创建实现对象。这个问题的解决方案由依赖注入（DI）提供，也称为控制反转（IoC）。DI模式有两个部分。第一部分是我们从组件中移除对具体类的任何依赖——在本例中是Repository。我们通过将所需接口的实现传递给类构造函数来实现这一点。
public Repository(IStorage storage)
{
//repository doesn't know what storage it will use
_storage = storage; /*constructor injection*/
_manager = new FingerprintManager();
}
我们打破了Repository和RamStorage之间的依赖关系。Repository构造函数需要一个实现IStorage接口的对象，但它不知道也不关心该对象是什么，也不再负责创建它。依赖项在运行时注入到Repository中；也就是说，在实例化过程中，将创建一个实现IStorage接口的类的实例并将其传递给Repository构造函数。IStorage与实现它所依赖的接口的任何类之间没有编译时依赖。Repository类要求其依赖项，因此它们是通过其构造函数注入的。这被称为构造函数注入。我们还可以允许通过公共属性注入依赖项，称为setter注入。由于依赖项是在运行时处理的，因此我们可以在运行应用程序时决定使用哪些接口实现。我们可以选择不同的存储提供程序，或者注入模拟实现进行测试。此时，我们已经解决了依赖问题：我们将在运行时将依赖项注入到类的构造函数中。但是，我们仍然有一个问题需要解决：如何实例化接口的具体实现，而不必在应用程序的其他地方创建依赖项？这时DI的第二部分出现了：DI容器，也称为IoC容器。这是一个组件，它充当Repository等类所需的依赖项与这些依赖项的具体实现（如RamStorage）之间的代理。我们将应用程序使用的接口或抽象类型的集合注册到DI容器中，并告诉它在需要满足依赖项时应该实例化哪些具体类。因此，下面展示了我们如何将IStorage接口与容器注册，并指定每当需要IStorage实现时，都应创建RamStorage的实例。将接口绑定到相应类型的类称为ServiceInjector。
/// <summary>
/// Service injector loads all the services into Service Container on Application startup
/// </summary>
public static class ServiceInjector
{
/// <summary>
/// Add bindings that will be applied within the application runtime
/// </summary>
public static void InjectServices()
{
ServiceContainer.Kernel.Bind<IFolderBrowserDialogService>().To<FolderBrowserDialogService>();
ServiceContainer.Kernel.Bind<IMessageBoxService>().To<MessageBoxService>();
ServiceContainer.Kernel.Bind<IOpenFileDialogService>().To<OpenFileDialogService>();
ServiceContainer.Kernel.Bind<ISaveFileDialogService>().To<SaveFileDialogService>();
ServiceContainer.Kernel.Bind<IWindowService>().To<WindowService>();
ServiceContainer.Kernel.Bind<IGenericViewWindow>().To<GenericViewWindowService>();
ServiceContainer.Kernel.Bind<IStorage>().To<RamStorage>(); //IStorage to RamStorage
ServiceContainer.Kernel.Bind<IPermutations>().To<LocalPermutations>();
}
}
每当我们 H IStorage时，例如为了创建Repository的实例，我们都会转到DI容器（ServiceContainer）类，并获得先前注册的类的实现（在本例中将是RamStorage。您可以尝试自己编写DI容器，但我建议您使用Ninject或Unity，因为它们提供了许多您在绑定类型到实现时可能需要的有用功能。下面是应用依赖注入后产生的新的依赖图。
您可以看到我们的目标已经实现，RamStorage不再依赖于RamStorage。依赖注入在开发使用MVVM模式的应用程序时提供了极大的帮助。MVVM的经典问题之一是实例化新窗口并将其显示给用户。这个看似简单的操作，在传统的基于事件的编程中是这样的，现在需要一种更有趣的方法来完成。因为您不能直接在视图模型中实例化窗口对象（记住模式，视图模型对视图一无所知），所以您应该通过依赖注入模式来实现这一点。一旦发出显示对话框的请求，您就可以注入任何行为。例如，假设您有一个自动化测试来检查视图模型中的逻辑。考虑您的视图模型允许用户将文件保存到磁盘。在生产环境中，您希望实例化SaveFileDialog并允许用户选择要存储文件的文件夹。然而，在测试环境中，您不允许这样做（自动化测试不需要用户交互，因此没有测试人员会选择文件名和存储文件的文件夹）。通过实现依赖注入，您将能够在测试环境中注入模拟行为，而无需实例化弹出窗口。希望我证明了DI在MVVM中的重要性。有关使用Ninject的更多详细信息，请访问此处。此外，您可能也有兴趣在开发周期中实现模拟行为。我建议您看一下Moq框架。回到算法：由于本文的目的是向您介绍音频指纹识别的概念，我将不再深入探讨MVVM编程的更多细节。如果您有兴趣，我建议您阅读有关MVVM的内容，因为它为开发人员带来了许多新的机会。您可以查看以下文章以获取更多详细信息。
重复项检测器
在下一个用例图（use case diagram）中，您可以看到使用重复项检测器应用程序可以执行的任务。它们的数量有限，因为这是一篇解释性文章，侧重于音频指纹识别算法。
要开始处理，您可以选择一个或多个包含音乐文件的根文件夹。该应用程序将执行深入搜索，查找根文件夹和子文件夹中的音频音轨（扩展名为*.mp3、*.ogg、*.wav、*.flac的项目）。搜索结束后，它将显示找到文件的总数。如果发现两个以上的文件，您将可以开始搜索重复项。指纹将存储在RAM中，因此在应用程序退出时，所有数据都将丢失。按下“开始”按钮后，应用程序将开始读取找到文件的标签。标签中的信息仅用于输出目的；算法不会考虑歌曲/艺术家的名称，因为重复项检测器将尝试根据音频歌曲的感知身份查找相似项。曲目将被视为合格，前提是其长度不小于20秒且不超过10分钟。对于每个项目，将分析15秒（从第20秒开始）以创建相关的指纹，这些指纹将用于查找相似项。该应用程序仅处理单个文件中的单个歌曲。算法结束后，将显示一个新窗口，其中包含重复文件的信息。您将能够收听歌曲，并查看它们是否确实相同。
生产者-消费者模式
计算上，算法中最昂贵的操作是快速傅立叶变换。为了加快执行速度，可以使用多个线程进行处理。无论如何，在此特定应用程序中，多个线程同时工作存在一个问题：它们都将尝试同时访问您的硬盘驱动器上的不同位置进行读取。每个线程将尝试处理自己的文件。这将导致您的硬盘驱动器磁头在盘片上频繁地从一个位置跳到另一个位置，从而减慢运行时间（I/O操作始终很昂贵）。这个问题非常适合于我们希望有一个读取器仔细准备数据供多个线程处理单元（在本例中为执行音频样本FFT的对象）处理的场景。因此，我决定采用生产者-消费者模式，最多有2个生产者读取和下采样音频文件，以及可变数量的消费者执行FFT。消费线程的数量将取决于Environment.ProcessorCount变量返回的处理器数量。该模式的工作原理如下图所示。
使用此模式时需要解决的问题是同步对共享缓冲区的读/写操作。如果缓冲区已满，生产者不应向其中添加项目；如果缓冲区为空，消费者也不应从中取走项目。这种同步是通过.NET 4中TPL附带的BlockingCollection完成的。下面是负责此事的代码。
/// <summary>
/// Process files (get fingerprint signatures, hash them into storage)
/// </summary>
/// <param name = "files">List of files to be hashed</param>
/// <param name = "processed">Callback invoked once 1 track is processed</param>
/// <returns>List of processed tracks</returns>
public List<Track> ProcessFiles(List<string> files, Action<Track> processed)
{
/*preprocessing stage ended, now make sure to do the actual job*/
int numProcs = Environment.ProcessorCount;
//~317 songs are allowed to be added in buffer for 15 seconds snippet at 5512 Hz sample rate
const int buffersize = (int)((1024.0 * BUFFER_SIZE) /
((double)SAMPLE_RATE * MILLISECONDS_TO_PROCESS / 1000 * 4 / 1024));
var buffer = new BlockingCollection<Tuple<Track, float[]>>(buffersize);
List<Track> processedtracks = new List<Track>();
List<Task> consumers = new List<Task>();
List<Task> producers = new List<Task>();
CancellationToken token = _cts.Token;
ConcurrentBag<string> bag = new ConcurrentBag<string>(files);
int maxprod = numProcs > 2 ? 2 : numProcs;
for (int i = 0; i < maxprod; i++) /*producers*/
{
producers.Add(Task.Factory.StartNew(
() =>
{
while (!bag.IsEmpty)
{
if (token.IsCancellationRequested) return;
string file;
if (!bag.TryTake(out file)) return;
Track track;
float[] samples;
try
{
//producer - read and downsample
track = TrackHelper.GetTrackInfo(MIN_TRACK_LENGTH, MAX_TRACK_LENGTH, file, _proxy);
samples = TrackHelper.GetTrackSamples(track, _proxy, SAMPLE_RATE,
MILLISECONDS_TO_PROCESS, MILLISECONDS_START);
}
catch
{
continue;
}
try
{
/*producer*/
buffer.TryAdd(new Tuple<Track, float[]>(track, samples), 1, token);
}
catch (OperationCanceledException)
{
/*it is safe to break here, operation was canceled*/
break;
}
}
}, token));
}
/* When all producers ended with their operations, call the CompleteAdding()
* to tell Consumers no more items are available */
Task.Factory.ContinueWhenAll(producers.ToArray(), (p) => buffer.CompleteAdding());
for (int i = 0; i < numProcs * 4; i++) /*consumer*/
{
consumers.Add(Task.Factory.StartNew(
() =>
{
/*If OCE is thrown it will be caught in the caller's AggregateException*/
foreach (var tuple in buffer.GetConsumingEnumerable())
{
if (tuple != null)
{
/*Long running procedure*/
_repository.CreateInsertFingerprints(tuple.Item2, tuple.Item1,
_queryStride, _createStride, NUMBER_OF_HASH_TABLES, NUMBER_OF_KEYS);
processedtracks.Add(tuple.Item1);
if (processed != null)
processed.Invoke(tuple.Item1);
}
}
}, token));
}
Task.WaitAll(consumers.ToArray()); /*wait for all consumers to end*/
return processedtracks;
}
此代码最多运行2个生产者，它们将下采样后的音频文件添加到缓冲区（缓冲区大小限制为100 MB），而一组消费者将尝试读取新进数据并从中创建指纹。这将使应用程序运行顺畅，因为硬盘驱动器的读取将仅由1到2个生产者执行。我强烈建议您阅读更多有关TPL框架的信息，因为它不仅允许您创建多个线程，还可以轻松地同步它们，并在需要时优雅地取消操作。有关TPL的更多信息可以在此处和此处找到。
结论
本文的目的是向您介绍音频识别和分析的概念。随着这个主题（以及与数据挖掘相关的类似主题）日益普及，您可以进一步探索其理论构造，以获得更好的查找率。由于我启动了一个与所描述主题相关的开源项目，您可以在此处找到完整的研究代码和相关工具。如果您想在自己的项目中测试该算法，请从NuGet安装框架。此外，如果您考虑改进算法，您可能还想研究使用神经网络作为容错哈希函数生成器（我发现这是一个非常有趣的算法，但尚未实现）。我鼓励您评论本文，因为我乐于接受任何与实现细节相关的合理建议（以及您可以通过在GitHub上fork来提供的代码改进）。请注意，本文最初发布于2011年，因此演示项目中描述的一些概念（MVVM、依赖注入、TPL、生产者-消费者）听起来可能不像它们最初描述时那样新。编码功能发展很快：)。感谢您的阅读。
启发我的文章
- 使用小波进行内容指纹识别（算法描述）
- 排列分组：音频和图像检索的智能哈希函数设计
- 高度鲁棒的音频指纹识别系统
- 学习“容错”哈希函数：算法和大规模测试
- 高维近似最近邻的近最优哈希算法
- 通过哈希进行高维相似性搜索
- 快速多分辨率图像查询
- 用依赖树逼近离散概率分布
历史
- 2011年6月5日 - 首次发布。
- 2011年6月13日 - 在演示应用程序中实施了小的修复。
- 2011年6月16日 - 提高了性能，并在演示中进行了一些小的错误修复。
- 2011年11月11日 - 在解释中添加了DI和生产者-消费者模式。进行了几次错误修复和改进。
- 2012年1月29日 - 现在已正确关闭音乐文件句柄。增加了将重复项移动到单独文件夹的可能性。
- 2013年6月16日 - 重大改进。Sound Fingerprinting现已在NuGet上可用。
- 2013年6月20日 - 对文章进行了小的改进。在GitHub上获取源代码。
- 2016年12月6日 - 链接新的可执行文件
- 2018年7月 - 链接新的可执行文件
- 2020年6月 - 链接新的可执行文件。有关算法及其使用的更多详细信息，请访问此处。