抗频率变换的采样计数音频检索方法

姚姗姗，牛保宁

1.山西大学 大数据科学与产业研究院，太原030006

2.太原理工大学 信息与计算机学院，山西 晋中030600

音频检索已被广泛应用于音乐识别、版权监测等任务。目前，真实环境下的音频大数据检索主要面临两方面的挑战：一方面，真实环境下的音频数据会受到不同噪声的干扰，降低检索的准确性；另一方面，音频数据规模的不断扩大要求检索方法高效。音频检索系统通常包括音频指纹和检索方法两部分，其中，音频指纹的鲁棒性决定了检索的准确性，检索方法的效率则决定了检索系统的效率。

理想的音频检索系统可以准确、快速地识别所有音频。目前已经有大量的研究提出了多种鲁棒的音频指纹提取方法[1-13]以及高效的音频检索方法[14-17]，但是目前还没有一种音频指纹可以应对所有的噪声干扰，并且由于检索方法与相应的音频指纹相关，整个系统会继承音频指纹无法抵抗相应噪声干扰的缺陷。例如，Philips指纹[1]是一种经典的音频指纹，由于其基于帧间的频带能量差，可以应对大多数的噪声和干扰，但无法抵抗±4%以上的线性变换。基于Philips指纹的采样计数音频检索方法（Sampling and Counting Retrieval Method，SC）[17]，利用Philips指纹重叠帧的特性，有效地提高了检索的效率，但是由于使用了Philips指纹，同时也继承了Philips指纹无法抵抗±4%以上的线性变换的缺点。如果能解决Philips指纹无法抵抗线性变换的缺点，则SC方法将进一步趋于理想。

线性变换作为一种常见的干扰方式，包括时间缩放（只有音频的长短发生变化）、频率变换（只有音调的高低发生变化）以及二者同时存在（时间和频率同时发生变化）这三种情况。目前解决线性变换问题的方法主要依赖于音频指纹的提取。常见的音频指纹主要包括两类，Philips类和Shazam类。Philips类的指纹基于频带的能量，其中，Philips指纹[1]无法抵抗±4%以上的线性变换，后续有一系列针对此类指纹的抗线性变换的改进[2-7]，Haitsma等人[2]在Philips指纹的基础上利用自相关函数的平移不变性将线性变换抵抗范围扩大到±6%；Seo等人[3]依据傅里叶-梅林变换的缩放不变性将范围进一步提升至±10%；Bardeli等人[4]通过计算相邻帧对应频率块的乘积之和得到指纹序列，抵抗线性变换的范围为±15%；Chu等人[7]只针对频率变换，实现了一种依据峰值点选取频带划分起始点的指纹提取方法，可以抵抗±30%的频率变换。Shazam类的指纹基于峰值点的信息[8]，对这类指纹的改进集中在寻找峰值点之间的不变关系[9-13]，其中Sonnleitner等人[13]利用4个峰值点的关系编码得到Quad指纹，可以有效抵抗±30%的线性变换。但是上述改进均改变了音频指纹的提取方式，需要重新提取指纹特征。由于存在版权限制和数据规模过大的问题，对于一个现存的音频检索系统来说，重新提取指纹特征并不容易。

本文旨在利用现有的Philips指纹，在其基础上进行改进，期望实现一个接近理想的音频检索系统。作者在文献[18]中利用Philips指纹的重叠特性，寻找到时间缩放的音频之间的指纹匹配关系，解决了时间缩放的问题，本文通过分析频率变换音频前后的特性，利用频带划分，重点解决Philips指纹无法抵抗频率变换的问题。具体创新如下。

本文提出了一种抗频率变换的采样计数音频检索方法，包括变频带间隔的查询指纹生成方法、多频率尺度的查询匹配方法，以及分步骤指纹提取和变过滤阈值两种加速策略，可以有效抵抗70%到130%的频率变换，以达到与目前效果最好的QUAD方法相匹敌的程度。本文的创新可以使SC方法抵抗频率变换，该方法可以扩展到任意使用Philips类指纹的检索系统中，以增强其抵抗频率变换干扰的能力。

1 准备工作

1.1 Philips指纹

Philips指纹[1]是一种经典的音频指纹提取方式。首先，通过对时域的音频信号重叠分帧加窗，进行快速傅里叶变换，得到频域的频谱图。然后，取人耳感知范围内的300 Hz至2 000 Hz之间的频谱图，按照对数间隔划分33个频率带，计算每相邻的两个频带之间的能量差，再比较相邻两帧之间对应的频带能量差，即可得到一帧32位的0/1子指纹。最后，依次计算所有相邻帧之间的频带能量差，即可得到整首音频的指纹。

Philips指纹的计算公式如下。其中，E(n,m)表示第n帧第m个频带的能量值，F(n,m)表示第n帧第m位的子指纹。

1.2 采样计数检索方法

采样计数检索方法[17]是近年来提出的先进高效的音频大数据检索方法之一，可以抵抗大多数类型的噪声和干扰。

SC方法适用于Philips这类基于频带能量的指纹。主要包括过滤和匹配两步。首先，在过滤阶段，使用斐波那契哈希函数建立索引表，利用采样的子指纹在索引表中得到对应的候选音频，统计每个候选音频的个数并排序，再通过动态阈值过滤掉大量的不相关音频，得到SC的候选集；然后，在匹配阶段，对候选集中的音频进行精确匹配，利用固定间隔抽样匹配方法加速精确匹配的过程，得到最终的结果。

2 抗频率变换的采样计数音频检索方法

首先分析SC方法无法抵抗频率变换的原因，然后给出相应解决方法、加速策略以及实现步骤。

2.1 研究思路

对于频率变换的音频，尽管变换前后的每帧数据一一对应，每帧数据在频率方向发生了改变。由于在生成一帧子指纹时，要先划分频带，再计算能量差，所以使用固定的频带进行划分时得到的子指纹必然会发生改变。因此，SC候选集中不会包含真实音频的ID，问题出在指纹的提取阶段。

为此，首先对比了频率变换前后的音频的频谱图。使用Sonic Visualiser软件，分别得到音频10121.wav的原始音频、频率变换130%的音频、以及频率变换70%的音频的频谱图，如图1（a）～（c）所示。可以看出三张图之间存在下面的对应关系：在时间方向一一对应，在频率方向发生了缩放。以图中对应的红色叉点为例，选取其最低频率，原始音频的频率在1 882.81 Hz左右，130%变换的音频频率在2 476.56 Hz左右，是原始音频的1.3倍；70%变换的音频频率在1 289.06 Hz，是原始音频的0.7倍。这与频率变换的概念一致。

图1 频率变换前后的频谱图

然后，对比了大量的频率变换前后的子指纹对，发现子指纹在变换前后也存在着一定的对应关系。以音频10121.wav为例，取原始音频以及经过130%和70%频率变换后的音频的第一个子指纹进行对比。同时，为了对比相同音频与不同音频之间的差异，选取音频203.wav的第一个子指纹，进行不相关音频子指纹的比特误差对比。具体如图2所示。其中，0/1串表示32位的Philips子指纹，左边为高位，右边为低位。可以看出，频率变换130%以后得到的子指纹相较于原始子指纹左移了6位，比特误差数为5，同样位置与非相关音频203.wav相比的比特误差为14位；频率变换70%以后得到的子指纹相较于原始子指纹右移了6位，比特误差为4，同样位置与非相关音频203.wav的比特误差为12位。上述分析可得结论如下：

（1）相关音频在频率变换前后通过子指纹移位，会存在一定的对应关系；非相关音频在同样移位后的比特误差依旧很大。

（2）相关音频在频率变换前后通过子指纹移位，可以得到较高的相似度，但并不是完全一一对应。

图2 频率变换前后的子指纹对比

事实上，实验中使用的频率变换音频并未添加其他类型的噪声干扰。因此，上述结论（2）可以表明，尽管经过缩放后的能量值会出现一定程度的整体偏移，使用固定间隔的频带划分会使其中一部分变换后的能量跨越到其他频带，从而造成移位后的子指纹不完全一致。

针对此，本文仔细研究了Philips指纹的提取过程。发现如果能在划分频带的时候采用不同的间隔，则可以识别出经过不同程度频率变换的查询音频。

2.2 变频带间隔的查询指纹生成方法

由于希望保持音频指纹库中的数据不变，即保持原始Philips指纹信息，为了应对频率变换，本文提出一种变频带间隔的查询指纹生成方法，该方法只改变了查询音频的指纹和后续匹配过程，对于现有的音频指纹库和索引库没有影响。具体方法如下。

首先，利用短时傅里叶变换得到音频数据的频谱图。用M×N表示频谱图，其中，M表示每一帧音频数据经过快速傅里叶变换（Fast Fourier Transform，FFT）之后得到的频谱幅度值点的个数，N表示音频数据帧的个数。实验中，取采样率F s为8 000 Hz，帧长Nl为0.512 s，帧间隔N h为0.016 s，一帧子指纹的采样点个数N s为N s=F s×Nl=8 000×0.512=4 096，则经过FFT之后的幅度值个数M为2 049，即频谱图大小为2 049×N。

然后，在频谱图上取300 Hz至2 000 Hz之间的频率，再划分33个对数间隔。在实验中使用自然对数，得到每个频带的间隔划分公式如公式（2）所示：

其中，n b表示第n b个频带划分点，取0到33，f b表示第n个频带划分点的对应频率值。通过取不同的n b，即可得到34个对应的频率值f b。

由于在上一节中频率缩放存在对应关系，将查询音频的频带间隔划分进行了修改，得到公式（3）：

其中，设定C为频率缩放因子，通过取不同的C，可计算出不同频率缩放所对应的频带划分频率。例如对于95%频率变换的音频，取C=0.95即可。

为了对频谱图上的采样点进行准确划分，需要计算采样点与频率之间的对应关系，如公式（4）所示：

其中，nm表示频率f对应的第nm个幅度值点。将公式（3）得到的34个频率值f b代入公式（4）的f中，得到对应的34个划分幅度值点n m，即可划分33个频带。

最后，分别累加n m到nm+1之间的幅度值之和，得到第m+1个频带的能量值E(n,m+1)，利用公式（1），计算相邻两个频带之间的能量值的差值，再比较相邻两帧之间对应频带的能量差，得到32位子指纹。

对于音频数据库中的参考音频，指纹提取中均使用公式（2）。对于查询音频，由于事先并不知道一个未知查询音频片段的频率缩放程度，需要分别利用公式（2）和公式（3）生成不同尺度的查询指纹。

2.3 多频率尺度的查询匹配方法

在查询匹配时，由于查询音频的频率缩放尺度未知，需要使用本节的多频率尺度的查询匹配方法。

由于Philips指纹无法抵抗±4%以上的频率变换，以5%的频率缩放为间隔，从70%至130%共使用13种不同的频率尺度，包括12种缩放尺度和1种原始音频（即未经过频率变换的音频）。在查询时，首先比较原始音频，若未得到结果，再比较不同频率缩放的音频。

设定两个参数，位移方向δ和位移个数Nδ。其中δ取0和1，0代表频率尺度缩小，1代表频率尺度放大；Nδ取1到6，分别代表缩放的尺度，以5%为间隔递增。比如，当δ=1,Nδ=1时，代表频率变换105%；当δ=0，Nδ=2，代表频率变换90%，以此类推。

在查询匹配时，按照变换程度由低到高进行匹配。逐次增加Nδ，在每个缩放尺度中，根据δ缩小或者放大，分别进行两次匹配，得到结果即匹配结束，否则继续匹配。比如先匹配频率变换为95%和105%的情况，若未成功，再匹配90%和110%，依次进行。在最坏的情况下，即频率变换130%时，需要一共匹配13次，才能得到检索结果。

2.4 加速策略

为了保证检索效率，提出了一些加速策略。

一方面，分步计算查询音频的指纹特征。首先，生成并保存查询音频的频谱图；然后，按照查询的需要，依次根据频率缩放尺度使用对应的划分幅度值点n m，在频谱图上计算对应的频带能量值，求出查询音频在不同频率缩放程度下的指纹。其中，不同频率缩放尺度在频谱图上的34个划分幅度值点n m已提前计算并写入程序。

另一方面，改变SC方法的动态过滤阈值。在实验中，原始查询音频的指纹和不同频率尺度的指纹在使用SC方法检索时，使用了不同的动态过滤阈值[17]，设定后者的动态过滤阈值更高，可以起到一定的加速作用。

2.5 实现步骤

音频指纹数据库和索引表的生成方式与SC方法一致。查询阶段具体步骤如下：

步骤1生成并存储查询音频的频谱图S q，在频谱图基础上得到原始查询音频指纹F q。

步骤2对F q采样子指纹，到索引表中检索，使用SC方法得到候选集。

步骤3将查询F q与候选集中的音频指纹匹配。

步骤4如果匹配未成功，进入多频率尺度的查询匹配阶段。

（1）利用S q生成不同频率尺度的F qs。

（2）对F qs采样子指纹，到索引表中检索，使用SC方法得到候选集。

（3）将查询F qs与候选集中的音频指纹匹配，如果匹配未成功，返回（1）；如果匹配成功，则检索结束。

3 实验

将通过一系列实验来验证提出的方法抵抗频率变换的能力，以及其对于其他类型干扰的效率和准确率。

3.1 实验设计

实验环境，本节的实验在配有1.8 GHz的4核CPU、96 GB内存、8 TB硬盘的HP ML350e服务器上运行，服务器操作系统为64位的Windows Server 2008 R2企业版，编程语言为C++。

数据集，实验使用的数据集来自文献[13]，是从Jamendo下载的包含10万首音频的公开数据集。

查询，依据文献[13]的方式，从上述数据集中选择300个查询音频，每个查询音频长20 s，并经过6种不同的噪声干扰处理，以及从70%到130%范围的频率变换。因此，整个实验中使用的查询包括1 800个经过噪声干扰的查询片段，以及3 900个经过不同程度频率变换的查询音频片段。其中，噪声包括带通过滤（bandpass filtering），消除音频信号的特定频率信息；合唱（chorus），从一个音源中加入多个声音；回声（echo），通过对原始音频片段的重复卷积向音频添加回声；镶边（flanger），通过延迟信号向音频片段添加音效；通讯压缩（GSM compression），一种用于传输电话会话的对音频信号的有损压缩；颤音（tremolo），通过细微短促的音量变化得到的音效。

方法，本文的方法将与原始的SC方法，以及另外两种抵抗频率变换的方法进行对比。其中，抗频率变换的采样计数方法PSC，是本文方法；SC方法[17]，是原始的基于Philips指纹的采样计数检索方法；QUAD[13]，是利用Quad指纹，可以有效抵抗±30%线性变换的检索方法；PPF[7]，是作者等人针对频率变换问题，在SC检索方法的基础上，提出的基于峰值点的Philips指纹提取方法，可以在一定程度上抵抗±30%的频率变换。

3.2 实验分析

使用精度、召回率和检索时间为度量，来验证抗频率变换的采样计数检索方法的准确率和效率。

3.2.1 准确性

表1展示了四种检索方法在不同噪声干扰下的精度和召回率。QUAD在chorus、gsm两种干扰下效果很差，PPF在chorus干扰下效果较差，PSC的精度和召回率与SC方法的接近，在各种干扰的情况下表现都比较优秀。

表1 不同噪声干扰下的平均精度和召回率 %

图3显示了四种检索方法在70%到130%的频率变换干扰下的精度和召回率。其中，SC方法无法抵抗频率变换，PPF通过对Philips指纹提取方式的修改，可以提高一定的抵抗频率变换的能力，QUAD抵抗频率变换的效果较好。可以明显看出，PSC的整体性能与QUAD相当，要远优于前两种方法，其在80%以下的频率变换中召回率略低于QUAD，但在120%以上的频率变换中，召回率要高于QUAD。

图3 频率变换下的平均精度和召回率

3.2.2 效率

由于QUAD方法只提到在3.4 GHz的四核CPU上平均检索时间为1.69 s，并未给出具体的检索时间，只在图4比较SC、PPF以及PSC的检索时间，可以看出，在不同噪声的干扰下，PSC继承了SC的高效性，检索时间都在0.3 s以下，远小于QUAD的1.69 s；由于SC无法抵抗频率变换，故在最后一项频率变换中，未列出SC的检索时间，PSC对于不同范围的频率缩放的平均检索时间在2.2 s，性能低于PPF 的0.7s和QUAD的1.69s。

图4 不同干扰下的平均检索时间

为了进一步分析不同范围频率缩放下的检索效率，图5画出了PPF和PSC在不同范围的频率缩放下的检索时间，可以看出，频率变换程度越大，检索时间越长。

图5 不同频率变换下的平均检索时间

4 结束语

本文提出了一种抗频率变换的采样计数音频检索方法，包括变频带间隔的查询指纹生成方法、多频率尺度的查询匹配方法，以及分步骤指纹提取和变过滤阈值两种加速策略。该方法无需修改音频库中的指纹提取方式，利用提出的变频带间隔的查询指纹生成方法和多频率尺度的查询匹配方法，即可有效地抵抗±30%的频率变换，与目前最有效的QUAD方法相当。

由于在最坏情况下，查询音频需要匹配13次，在一定程度上降低了检索的效率，未来需要加入多线程或其他解决方法，以进一步提升检索的效率。