抗頻率變換的采樣計數音頻檢索方法

姚姍姍，牛保寧

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次，在一定程度上降低了檢索的效率，未來需要加入多線程或其他解決方法，以進一步提升檢索的效率。