姚姍姍，牛保寧

1.山西大學(xué) 大數(shù)據(jù)科學(xué)與產(chǎn)業(yè)研究院，太原030006

2.太原理工大學(xué) 信息與計(jì)算機(jī)學(xué)院，山西 晉中030600

音頻檢索已被廣泛應(yīng)用于音樂識(shí)別、版權(quán)監(jiān)測(cè)等任務(wù)。目前，真實(shí)環(huán)境下的音頻大數(shù)據(jù)檢索主要面臨兩方面的挑戰(zhàn)：一方面，真實(shí)環(huán)境下的音頻數(shù)據(jù)會(huì)受到不同噪聲的干擾，降低檢索的準(zhǔn)確性；另一方面，音頻數(shù)據(jù)規(guī)模的不斷擴(kuò)大要求檢索方法高效。音頻檢索系統(tǒng)通常包括音頻指紋和檢索方法兩部分，其中，音頻指紋的魯棒性決定了檢索的準(zhǔn)確性，檢索方法的效率則決定了檢索系統(tǒng)的效率。

理想的音頻檢索系統(tǒng)可以準(zhǔn)確、快速地識(shí)別所有音頻。目前已經(jīng)有大量的研究提出了多種魯棒的音頻指紋提取方法[1-13]以及高效的音頻檢索方法[14-17]，但是目前還沒有一種音頻指紋可以應(yīng)對(duì)所有的噪聲干擾，并且由于檢索方法與相應(yīng)的音頻指紋相關(guān)，整個(gè)系統(tǒng)會(huì)繼承音頻指紋無法抵抗相應(yīng)噪聲干擾的缺陷。例如，Philips指紋[1]是一種經(jīng)典的音頻指紋，由于其基于幀間的頻帶能量差，可以應(yīng)對(duì)大多數(shù)的噪聲和干擾，但無法抵抗±4%以上的線性變換?；赑hilips指紋的采樣計(jì)數(shù)音頻檢索方法（Sampling and Counting Retrieval Method，SC）[17]，利用Philips指紋重疊幀的特性，有效地提高了檢索的效率，但是由于使用了Philips指紋，同時(shí)也繼承了Philips指紋無法抵抗±4%以上的線性變換的缺點(diǎn)。如果能解決Philips指紋無法抵抗線性變換的缺點(diǎn)，則SC方法將進(jìn)一步趨于理想。

線性變換作為一種常見的干擾方式，包括時(shí)間縮放（只有音頻的長(zhǎng)短發(fā)生變化）、頻率變換（只有音調(diào)的高低發(fā)生變化）以及二者同時(shí)存在（時(shí)間和頻率同時(shí)發(fā)生變化）這三種情況。目前解決線性變換問題的方法主要依賴于音頻指紋的提取。常見的音頻指紋主要包括兩類，Philips類和Shazam類。Philips類的指紋基于頻帶的能量，其中，Philips指紋[1]無法抵抗±4%以上的線性變換，后續(xù)有一系列針對(duì)此類指紋的抗線性變換的改進(jìn)[2-7]，Haitsma等人[2]在Philips指紋的基礎(chǔ)上利用自相關(guān)函數(shù)的平移不變性將線性變換抵抗范圍擴(kuò)大到±6%；Seo等人[3]依據(jù)傅里葉-梅林變換的縮放不變性將范圍進(jìn)一步提升至±10%；Bardeli等人[4]通過計(jì)算相鄰幀對(duì)應(yīng)頻率塊的乘積之和得到指紋序列，抵抗線性變換的范圍為±15%；Chu等人[7]只針對(duì)頻率變換，實(shí)現(xiàn)了一種依據(jù)峰值點(diǎn)選取頻帶劃分起始點(diǎn)的指紋提取方法，可以抵抗±30%的頻率變換。Shazam類的指紋基于峰值點(diǎn)的信息[8]，對(duì)這類指紋的改進(jìn)集中在尋找峰值點(diǎn)之間的不變關(guān)系[9-13]，其中Sonnleitner等人[13]利用4個(gè)峰值點(diǎn)的關(guān)系編碼得到Quad指紋，可以有效抵抗±30%的線性變換。但是上述改進(jìn)均改變了音頻指紋的提取方式，需要重新提取指紋特征。由于存在版權(quán)限制和數(shù)據(jù)規(guī)模過大的問題，對(duì)于一個(gè)現(xiàn)存的音頻檢索系統(tǒng)來說，重新提取指紋特征并不容易。

本文旨在利用現(xiàn)有的Philips指紋，在其基礎(chǔ)上進(jìn)行改進(jìn)，期望實(shí)現(xiàn)一個(gè)接近理想的音頻檢索系統(tǒng)。作者在文獻(xiàn)[18]中利用Philips指紋的重疊特性，尋找到時(shí)間縮放的音頻之間的指紋匹配關(guān)系，解決了時(shí)間縮放的問題，本文通過分析頻率變換音頻前后的特性，利用頻帶劃分，重點(diǎn)解決Philips指紋無法抵抗頻率變換的問題。具體創(chuàng)新如下。

本文提出了一種抗頻率變換的采樣計(jì)數(shù)音頻檢索方法，包括變頻帶間隔的查詢指紋生成方法、多頻率尺度的查詢匹配方法，以及分步驟指紋提取和變過濾閾值兩種加速策略，可以有效抵抗70%到130%的頻率變換，以達(dá)到與目前效果最好的QUAD方法相匹敵的程度。本文的創(chuàng)新可以使SC方法抵抗頻率變換，該方法可以擴(kuò)展到任意使用Philips類指紋的檢索系統(tǒng)中，以增強(qiáng)其抵抗頻率變換干擾的能力。

1 準(zhǔn)備工作

1.1 Philips指紋

Philips指紋[1]是一種經(jīng)典的音頻指紋提取方式。首先，通過對(duì)時(shí)域的音頻信號(hào)重疊分幀加窗，進(jìn)行快速傅里葉變換，得到頻域的頻譜圖。然后，取人耳感知范圍內(nèi)的300 Hz至2 000 Hz之間的頻譜圖，按照對(duì)數(shù)間隔劃分33個(gè)頻率帶，計(jì)算每相鄰的兩個(gè)頻帶之間的能量差，再比較相鄰兩幀之間對(duì)應(yīng)的頻帶能量差，即可得到一幀32位的0/1子指紋。最后，依次計(jì)算所有相鄰幀之間的頻帶能量差，即可得到整首音頻的指紋。

Philips指紋的計(jì)算公式如下。其中，E(n,m)表示第n幀第m個(gè)頻帶的能量值，F(xiàn)(n,m)表示第n幀第m位的子指紋。

1.2 采樣計(jì)數(shù)檢索方法

采樣計(jì)數(shù)檢索方法[17]是近年來提出的先進(jìn)高效的音頻大數(shù)據(jù)檢索方法之一，可以抵抗大多數(shù)類型的噪聲和干擾。

SC方法適用于Philips這類基于頻帶能量的指紋。主要包括過濾和匹配兩步。首先，在過濾階段，使用斐波那契哈希函數(shù)建立索引表，利用采樣的子指紋在索引表中得到對(duì)應(yīng)的候選音頻，統(tǒng)計(jì)每個(gè)候選音頻的個(gè)數(shù)并排序，再通過動(dòng)態(tài)閾值過濾掉大量的不相關(guān)音頻，得到SC的候選集；然后，在匹配階段，對(duì)候選集中的音頻進(jìn)行精確匹配，利用固定間隔抽樣匹配方法加速精確匹配的過程，得到最終的結(jié)果。

2 抗頻率變換的采樣計(jì)數(shù)音頻檢索方法

首先分析SC方法無法抵抗頻率變換的原因，然后給出相應(yīng)解決方法、加速策略以及實(shí)現(xiàn)步驟。

2.1 研究思路

對(duì)于頻率變換的音頻，盡管變換前后的每幀數(shù)據(jù)一一對(duì)應(yīng)，每幀數(shù)據(jù)在頻率方向發(fā)生了改變。由于在生成一幀子指紋時(shí)，要先劃分頻帶，再計(jì)算能量差，所以使用固定的頻帶進(jìn)行劃分時(shí)得到的子指紋必然會(huì)發(fā)生改變。因此，SC候選集中不會(huì)包含真實(shí)音頻的ID，問題出在指紋的提取階段。

為此，首先對(duì)比了頻率變換前后的音頻的頻譜圖。使用Sonic Visualiser軟件，分別得到音頻10121.wav的原始音頻、頻率變換130%的音頻、以及頻率變換70%的音頻的頻譜圖，如圖1（a）～（c）所示?？梢钥闯鋈龔垐D之間存在下面的對(duì)應(yīng)關(guān)系：在時(shí)間方向一一對(duì)應(yīng)，在頻率方向發(fā)生了縮放。以圖中對(duì)應(yīng)的紅色叉點(diǎn)為例，選取其最低頻率，原始音頻的頻率在1 882.81 Hz左右，130%變換的音頻頻率在2 476.56 Hz左右，是原始音頻的1.3倍；70%變換的音頻頻率在1 289.06 Hz，是原始音頻的0.7倍。這與頻率變換的概念一致。

圖1 頻率變換前后的頻譜圖

然后，對(duì)比了大量的頻率變換前后的子指紋對(duì)，發(fā)現(xiàn)子指紋在變換前后也存在著一定的對(duì)應(yīng)關(guān)系。以音頻10121.wav為例，取原始音頻以及經(jīng)過130%和70%頻率變換后的音頻的第一個(gè)子指紋進(jìn)行對(duì)比。同時(shí)，為了對(duì)比相同音頻與不同音頻之間的差異，選取音頻203.wav的第一個(gè)子指紋，進(jìn)行不相關(guān)音頻子指紋的比特誤差對(duì)比。具體如圖2所示。其中，0/1串表示32位的Philips子指紋，左邊為高位，右邊為低位?？梢钥闯?，頻率變換130%以后得到的子指紋相較于原始子指紋左移了6位，比特誤差數(shù)為5，同樣位置與非相關(guān)音頻203.wav相比的比特誤差為14位；頻率變換70%以后得到的子指紋相較于原始子指紋右移了6位，比特誤差為4，同樣位置與非相關(guān)音頻203.wav的比特誤差為12位。上述分析可得結(jié)論如下：

（1）相關(guān)音頻在頻率變換前后通過子指紋移位，會(huì)存在一定的對(duì)應(yīng)關(guān)系；非相關(guān)音頻在同樣移位后的比特誤差依舊很大。

（2）相關(guān)音頻在頻率變換前后通過子指紋移位，可以得到較高的相似度，但并不是完全一一對(duì)應(yīng)。

圖2 頻率變換前后的子指紋對(duì)比

事實(shí)上，實(shí)驗(yàn)中使用的頻率變換音頻并未添加其他類型的噪聲干擾。因此，上述結(jié)論（2）可以表明，盡管經(jīng)過縮放后的能量值會(huì)出現(xiàn)一定程度的整體偏移，使用固定間隔的頻帶劃分會(huì)使其中一部分變換后的能量跨越到其他頻帶，從而造成移位后的子指紋不完全一致。

針對(duì)此，本文仔細(xì)研究了Philips指紋的提取過程。發(fā)現(xiàn)如果能在劃分頻帶的時(shí)候采用不同的間隔，則可以識(shí)別出經(jīng)過不同程度頻率變換的查詢音頻。

2.2 變頻帶間隔的查詢指紋生成方法

由于希望保持音頻指紋庫中的數(shù)據(jù)不變，即保持原始Philips指紋信息，為了應(yīng)對(duì)頻率變換，本文提出一種變頻帶間隔的查詢指紋生成方法，該方法只改變了查詢音頻的指紋和后續(xù)匹配過程，對(duì)于現(xiàn)有的音頻指紋庫和索引庫沒有影響。具體方法如下。

首先，利用短時(shí)傅里葉變換得到音頻數(shù)據(jù)的頻譜圖。用M×N表示頻譜圖，其中，M表示每一幀音頻數(shù)據(jù)經(jīng)過快速傅里葉變換（Fast Fourier Transform，F(xiàn)FT）之后得到的頻譜幅度值點(diǎn)的個(gè)數(shù)，N表示音頻數(shù)據(jù)幀的個(gè)數(shù)。實(shí)驗(yàn)中，取采樣率F s為8 000 Hz，幀長(zhǎng)Nl為0.512 s，幀間隔N h為0.016 s，一幀子指紋的采樣點(diǎn)個(gè)數(shù)N s為N s=F s×Nl=8 000×0.512=4 096，則經(jīng)過FFT之后的幅度值個(gè)數(shù)M為2 049，即頻譜圖大小為2 049×N。

然后，在頻譜圖上取300 Hz至2 000 Hz之間的頻率，再劃分33個(gè)對(duì)數(shù)間隔。在實(shí)驗(yàn)中使用自然對(duì)數(shù)，得到每個(gè)頻帶的間隔劃分公式如公式（2）所示：

其中，n b表示第n b個(gè)頻帶劃分點(diǎn)，取0到33，f b表示第n個(gè)頻帶劃分點(diǎn)的對(duì)應(yīng)頻率值。通過取不同的n b，即可得到34個(gè)對(duì)應(yīng)的頻率值f b。

由于在上一節(jié)中頻率縮放存在對(duì)應(yīng)關(guān)系，將查詢音頻的頻帶間隔劃分進(jìn)行了修改，得到公式（3）：

其中，設(shè)定C為頻率縮放因子，通過取不同的C，可計(jì)算出不同頻率縮放所對(duì)應(yīng)的頻帶劃分頻率。例如對(duì)于95%頻率變換的音頻，取C=0.95即可。

為了對(duì)頻譜圖上的采樣點(diǎn)進(jìn)行準(zhǔn)確劃分，需要計(jì)算采樣點(diǎn)與頻率之間的對(duì)應(yīng)關(guān)系，如公式（4）所示：

其中，nm表示頻率f對(duì)應(yīng)的第nm個(gè)幅度值點(diǎn)。將公式（3）得到的34個(gè)頻率值f b代入公式（4）的f中，得到對(duì)應(yīng)的34個(gè)劃分幅度值點(diǎn)n m，即可劃分33個(gè)頻帶。

最后，分別累加n m到nm+1之間的幅度值之和，得到第m+1個(gè)頻帶的能量值E(n,m+1)，利用公式（1），計(jì)算相鄰兩個(gè)頻帶之間的能量值的差值，再比較相鄰兩幀之間對(duì)應(yīng)頻帶的能量差，得到32位子指紋。

對(duì)于音頻數(shù)據(jù)庫中的參考音頻，指紋提取中均使用公式（2）。對(duì)于查詢音頻，由于事先并不知道一個(gè)未知查詢音頻片段的頻率縮放程度，需要分別利用公式（2）和公式（3）生成不同尺度的查詢指紋。

2.3 多頻率尺度的查詢匹配方法

在查詢匹配時(shí)，由于查詢音頻的頻率縮放尺度未知，需要使用本節(jié)的多頻率尺度的查詢匹配方法。

由于Philips指紋無法抵抗±4%以上的頻率變換，以5%的頻率縮放為間隔，從70%至130%共使用13種不同的頻率尺度，包括12種縮放尺度和1種原始音頻（即未經(jīng)過頻率變換的音頻）。在查詢時(shí)，首先比較原始音頻，若未得到結(jié)果，再比較不同頻率縮放的音頻。

設(shè)定兩個(gè)參數(shù)，位移方向δ和位移個(gè)數(shù)Nδ。其中δ取0和1，0代表頻率尺度縮小，1代表頻率尺度放大；Nδ取1到6，分別代表縮放的尺度，以5%為間隔遞增。比如，當(dāng)δ=1,Nδ=1時(shí)，代表頻率變換105%；當(dāng)δ=0，Nδ=2，代表頻率變換90%，以此類推。

在查詢匹配時(shí)，按照變換程度由低到高進(jìn)行匹配。逐次增加Nδ，在每個(gè)縮放尺度中，根據(jù)δ縮小或者放大，分別進(jìn)行兩次匹配，得到結(jié)果即匹配結(jié)束，否則繼續(xù)匹配。比如先匹配頻率變換為95%和105%的情況，若未成功，再匹配90%和110%，依次進(jìn)行。在最壞的情況下，即頻率變換130%時(shí)，需要一共匹配13次，才能得到檢索結(jié)果。

2.4 加速策略

為了保證檢索效率，提出了一些加速策略。

一方面，分步計(jì)算查詢音頻的指紋特征。首先，生成并保存查詢音頻的頻譜圖；然后，按照查詢的需要，依次根據(jù)頻率縮放尺度使用對(duì)應(yīng)的劃分幅度值點(diǎn)n m，在頻譜圖上計(jì)算對(duì)應(yīng)的頻帶能量值，求出查詢音頻在不同頻率縮放程度下的指紋。其中，不同頻率縮放尺度在頻譜圖上的34個(gè)劃分幅度值點(diǎn)n m已提前計(jì)算并寫入程序。

另一方面，改變SC方法的動(dòng)態(tài)過濾閾值。在實(shí)驗(yàn)中，原始查詢音頻的指紋和不同頻率尺度的指紋在使用SC方法檢索時(shí)，使用了不同的動(dòng)態(tài)過濾閾值[17]，設(shè)定后者的動(dòng)態(tài)過濾閾值更高，可以起到一定的加速作用。

2.5 實(shí)現(xiàn)步驟

音頻指紋數(shù)據(jù)庫和索引表的生成方式與SC方法一致。查詢階段具體步驟如下：

步驟1生成并存儲(chǔ)查詢音頻的頻譜圖S q，在頻譜圖基礎(chǔ)上得到原始查詢音頻指紋F q。

步驟2對(duì)F q采樣子指紋，到索引表中檢索，使用SC方法得到候選集。

步驟3將查詢F q與候選集中的音頻指紋匹配。

步驟4如果匹配未成功，進(jìn)入多頻率尺度的查詢匹配階段。

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

（2）對(duì)F qs采樣子指紋，到索引表中檢索，使用SC方法得到候選集。

（3）將查詢F qs與候選集中的音頻指紋匹配，如果匹配未成功，返回（1）；如果匹配成功，則檢索結(jié)束。

3 實(shí)驗(yàn)

將通過一系列實(shí)驗(yàn)來驗(yàn)證提出的方法抵抗頻率變換的能力，以及其對(duì)于其他類型干擾的效率和準(zhǔn)確率。

3.1 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)環(huán)境，本節(jié)的實(shí)驗(yàn)在配有1.8 GHz的4核CPU、96 GB內(nèi)存、8 TB硬盤的HP ML350e服務(wù)器上運(yùn)行，服務(wù)器操作系統(tǒng)為64位的Windows Server 2008 R2企業(yè)版，編程語言為C++。

數(shù)據(jù)集，實(shí)驗(yàn)使用的數(shù)據(jù)集來自文獻(xiàn)[13]，是從Jamendo下載的包含10萬首音頻的公開數(shù)據(jù)集。

查詢，依據(jù)文獻(xiàn)[13]的方式，從上述數(shù)據(jù)集中選擇300個(gè)查詢音頻，每個(gè)查詢音頻長(zhǎng)20 s，并經(jīng)過6種不同的噪聲干擾處理，以及從70%到130%范圍的頻率變換。因此，整個(gè)實(shí)驗(yàn)中使用的查詢包括1 800個(gè)經(jīng)過噪聲干擾的查詢片段，以及3 900個(gè)經(jīng)過不同程度頻率變換的查詢音頻片段。其中，噪聲包括帶通過濾（bandpass filtering），消除音頻信號(hào)的特定頻率信息；合唱（chorus），從一個(gè)音源中加入多個(gè)聲音；回聲（echo），通過對(duì)原始音頻片段的重復(fù)卷積向音頻添加回聲；鑲邊（flanger），通過延遲信號(hào)向音頻片段添加音效；通訊壓縮（GSM compression），一種用于傳輸電話會(huì)話的對(duì)音頻信號(hào)的有損壓縮；顫音（tremolo），通過細(xì)微短促的音量變化得到的音效。

方法，本文的方法將與原始的SC方法，以及另外兩種抵抗頻率變換的方法進(jìn)行對(duì)比。其中，抗頻率變換的采樣計(jì)數(shù)方法PSC，是本文方法；SC方法[17]，是原始的基于Philips指紋的采樣計(jì)數(shù)檢索方法；QUAD[13]，是利用Quad指紋，可以有效抵抗±30%線性變換的檢索方法；PPF[7]，是作者等人針對(duì)頻率變換問題，在SC檢索方法的基礎(chǔ)上，提出的基于峰值點(diǎn)的Philips指紋提取方法，可以在一定程度上抵抗±30%的頻率變換。

3.2 實(shí)驗(yàn)分析

使用精度、召回率和檢索時(shí)間為度量，來驗(yàn)證抗頻率變換的采樣計(jì)數(shù)檢索方法的準(zhǔn)確率和效率。

3.2.1 準(zhǔn)確性

表1展示了四種檢索方法在不同噪聲干擾下的精度和召回率。QUAD在chorus、gsm兩種干擾下效果很差，PPF在chorus干擾下效果較差，PSC的精度和召回率與SC方法的接近，在各種干擾的情況下表現(xiàn)都比較優(yōu)秀。

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

圖3顯示了四種檢索方法在70%到130%的頻率變換干擾下的精度和召回率。其中，SC方法無法抵抗頻率變換，PPF通過對(duì)Philips指紋提取方式的修改，可以提高一定的抵抗頻率變換的能力，QUAD抵抗頻率變換的效果較好。可以明顯看出，PSC的整體性能與QUAD相當(dāng)，要遠(yuǎn)優(yōu)于前兩種方法，其在80%以下的頻率變換中召回率略低于QUAD，但在120%以上的頻率變換中，召回率要高于QUAD。

圖3 頻率變換下的平均精度和召回率

3.2.2 效率

由于QUAD方法只提到在3.4 GHz的四核CPU上平均檢索時(shí)間為1.69 s，并未給出具體的檢索時(shí)間，只在圖4比較SC、PPF以及PSC的檢索時(shí)間，可以看出，在不同噪聲的干擾下，PSC繼承了SC的高效性，檢索時(shí)間都在0.3 s以下，遠(yuǎn)小于QUAD的1.69 s；由于SC無法抵抗頻率變換，故在最后一項(xiàng)頻率變換中，未列出SC的檢索時(shí)間，PSC對(duì)于不同范圍的頻率縮放的平均檢索時(shí)間在2.2 s，性能低于PPF 的0.7s和QUAD的1.69s。

圖4 不同干擾下的平均檢索時(shí)間

為了進(jìn)一步分析不同范圍頻率縮放下的檢索效率，圖5畫出了PPF和PSC在不同范圍的頻率縮放下的檢索時(shí)間，可以看出，頻率變換程度越大，檢索時(shí)間越長(zhǎng)。

圖5 不同頻率變換下的平均檢索時(shí)間

4 結(jié)束語

本文提出了一種抗頻率變換的采樣計(jì)數(shù)音頻檢索方法，包括變頻帶間隔的查詢指紋生成方法、多頻率尺度的查詢匹配方法，以及分步驟指紋提取和變過濾閾值兩種加速策略。該方法無需修改音頻庫中的指紋提取方式，利用提出的變頻帶間隔的查詢指紋生成方法和多頻率尺度的查詢匹配方法，即可有效地抵抗±30%的頻率變換，與目前最有效的QUAD方法相當(dāng)。

由于在最壞情況下，查詢音頻需要匹配13次，在一定程度上降低了檢索的效率，未來需要加入多線程或其他解決方法，以進(jìn)一步提升檢索的效率。