金國平，余宗橋，郭延文，蔣 和

(1. 南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，南京 21004 6；2. 南京師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，南京 21004 6)

基于GPU加速的音頻檢索技術(shù)

金國平1，余宗橋1，郭延文1，蔣 和2

(1. 南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，南京 21004 6；2. 南京師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，南京 21004 6)

由于數(shù)字音頻數(shù)據(jù)量極大的特點(diǎn)，采用傳統(tǒng)音頻檢索方法會(huì)導(dǎo)致等待時(shí)間過長(zhǎng)。為加快音頻檢索時(shí)間，提出一種基于GPU加速的數(shù)字音頻檢索方法。利用數(shù)字音頻的特征將連續(xù)的音頻劃分成等長(zhǎng)的多個(gè)短時(shí)音頻段，采用GPU加速算法計(jì)算每個(gè)短時(shí)音頻段的特征值，將各段的特征值構(gòu)成特征矩陣。使用后綴數(shù)組的變形算法找出2個(gè)特征值序列的公共特征段落集合，并將公共特征段落集合進(jìn)行精化和整體匹配，從而得出檢索結(jié)果。實(shí)驗(yàn)結(jié)果表明，該檢索方法的準(zhǔn)確率可以達(dá)到95%以上，與已有方法相比，可以大幅度地提高檢索速度，加速比可以達(dá)到10倍以上。

音頻檢索；GPU加速；后綴數(shù)組；音頻特征；特征值序列；整體匹配

1 概述

近年來隨著多媒體技術(shù)的迅猛發(fā)展，多媒體數(shù)據(jù)的數(shù)量呈指數(shù)增長(zhǎng)，音頻數(shù)據(jù)作為多媒體數(shù)據(jù)的一部分也得到了充分的發(fā)展。如何在海量的多媒體數(shù)據(jù)中找到感興趣的內(nèi)容成為了大家關(guān)注的焦點(diǎn)，音頻數(shù)據(jù)的檢索也不例外。音頻檢索是指通過對(duì)音頻特征的分析在對(duì)應(yīng)的音頻目標(biāo)中找出所對(duì)應(yīng)的音頻[1]。

目前音頻的檢索方法主要分為2類：一類是基于內(nèi)容的音頻檢索方法，其主要是利用音頻的特征，如利用音頻的振幅、頻率等物理特征，響度、音色等聽覺特征和節(jié)奏、聲紋等語義高層特征進(jìn)行分類和比較[2-3]，該類方法的缺點(diǎn)是技術(shù)較為復(fù)雜，檢索精度難以跨越語義鴻溝的影響[4]；另一類方法是基于相識(shí)度的方法，又稱為固定音頻檢索，它是指直接利用音頻檢索音頻，不需要識(shí)別音效和場(chǎng)景，也不需要提前定義模型和訓(xùn)練，直接提取音頻特征進(jìn)行遍歷查找得出檢索結(jié)果[5-6]，這類方法實(shí)現(xiàn)簡(jiǎn)單靈活，檢索正確率高，但是存在以下問題：計(jì)算代價(jià)隨著檢索目標(biāo)長(zhǎng)度呈正比，檢索時(shí)間隨著檢索目標(biāo)長(zhǎng)度增加而呈線性增加。文獻(xiàn)[7]中雖然提出將整個(gè)檢索目標(biāo)劃分為若干個(gè)小時(shí)段，并將小時(shí)段單獨(dú)檢出，但是總的檢索時(shí)間并沒有明顯減少。

針對(duì)基于相識(shí)度的音頻檢索方法存在的問題，本文提出一種基于GPU加速的音頻檢索方法。基于GPU的CUDA平臺(tái)并行提取特征，提高音頻檢索的速度，并與傳統(tǒng)的CPU檢索方法進(jìn)行比較。

2 GPU編程模型與線程結(jié)構(gòu)

GPU通用計(jì)算通常采用CPU+GPU的異構(gòu)模式，由CPU負(fù)責(zé)執(zhí)行復(fù)雜邏輯處理和事務(wù)處理等不適合數(shù)據(jù)并行的計(jì)算，由GPU負(fù)責(zé)計(jì)算密集型的大規(guī)模數(shù)據(jù)并行。通常來說計(jì)算將CPU作為主機(jī)(host)，GPU作為計(jì)算設(shè)備(device)，在一個(gè)系統(tǒng)中可以有一個(gè)主機(jī)和若干個(gè)設(shè)備，CPU 和GPU各自擁有獨(dú)立的存儲(chǔ)地址空間，協(xié)同工作。首先CPU負(fù)責(zé)數(shù)據(jù)初始化工作和邏輯性強(qiáng)的事務(wù)處理，然后將CPU端的存儲(chǔ)數(shù)據(jù)發(fā)送到GPU端，GPU端進(jìn)行高度并行的數(shù)據(jù)處理任務(wù)，在任務(wù)完成好后將存儲(chǔ)數(shù)據(jù)再發(fā)送回CPU端[8]。

在GPU端運(yùn)行的函數(shù)稱作內(nèi)核函數(shù)(kernel)，CPU通過調(diào)用內(nèi)核函數(shù)調(diào)用GPU，每個(gè)內(nèi)核函數(shù)中的線程結(jié)構(gòu)包括工作塊(work-grid)和工作單元(work-block)。每個(gè)線程有一個(gè)唯一的標(biāo)示符(ID)，如果線程邏輯結(jié)構(gòu)是一維的，則其ID表示是線性的；如果線程邏輯結(jié)構(gòu)是二維的，若線程塊的大小為(Dx,Dy)，則索引號(hào)為(x,y)的線程的ID為(x+y·Dx)；如果線程邏輯結(jié)構(gòu)是三維的，若線程塊的大小為(Dx,Dy, Dz)，則索引號(hào)為(x,y,z)的線程的ID為(x+y·Dx+z·Dy·Dx)，當(dāng)主機(jī)調(diào)用內(nèi)核函數(shù)時(shí)，work-block被分配到不同的流處理器上，每個(gè)work-block中的線程在一個(gè)流處理器上執(zhí)行，當(dāng)一個(gè)線程塊結(jié)束后，新的線程塊將被喚醒并執(zhí)行。

3 基于GPU加速的音頻檢索方法

本文提出了一種基于GPU加速的音頻檢索方法，目的是提高檢索的時(shí)間，主要分為4個(gè)部分：音頻分割，音頻特征抽取，后綴數(shù)組查找以及結(jié)果精化和整體匹配。其主要算法流程如圖1所示。

圖1 基于GPU加速的音頻檢索算法流程

3.1 音頻分割

將待檢索的音頻p和目標(biāo)音頻q，分別按照其音頻的長(zhǎng)度劃分出長(zhǎng)度相等的2組音頻數(shù)據(jù)短時(shí)段。其中，待檢索音頻p劃分為短時(shí)段集合Cp，Cp={cp1,cp2,…,cpi,…,cpLp}，cpi表示短時(shí)段集合Cp中第i個(gè)音頻采樣值；1≤i≤Lp，Lp為短時(shí)段集合Cp的長(zhǎng)度；目標(biāo)音頻q劃分為短時(shí)段集合Cq，Cp={cq1,cq2,…,cqi,…,cqLq}，cqi表示短時(shí)段集合Cq中第i個(gè)音頻數(shù)據(jù)采樣值，1≤i≤Lq，Lq為短時(shí)段集合Cq的長(zhǎng)度。

3.2 音頻特征抽取

對(duì)于每一個(gè)音頻短時(shí)段D={P0,P1,…,Pi,…PN}，提取其特征值W，N為該音頻短時(shí)段D的長(zhǎng)度。計(jì)算該音頻短時(shí)段D的特征值，將向量D通過通用計(jì)算架構(gòu)(Compute Unified Device Architecture, CUDA)的cudamalloc函數(shù)加載到GPU內(nèi)存中并設(shè)置線程塊block和線程thread，使得該設(shè)置動(dòng)態(tài)最優(yōu)的適合于向量D={P0,P1,…,Pi,…PN}，并用GPU上kernel計(jì)算其特征。

查詢音頻需要提取音頻數(shù)據(jù)的特征值作為比較的目標(biāo)對(duì)象，在音頻檢索中，所選取的特征應(yīng)該能夠充分表示音頻的重要區(qū)分度的特征并具有一定的魯棒性。在音頻的特征中，本文選取了以下3種特征來表征音頻數(shù)據(jù)：

(1)響度。比較常用的音頻特征，與短時(shí)能量密切相關(guān)。計(jì)算一般是在時(shí)域進(jìn)行的，對(duì)每幀數(shù)據(jù)的采樣值求平方和。其計(jì)算公式如下：為該特征段的平均采樣值。

(2)短時(shí)平均過零率。它是指在一個(gè)短時(shí)幀內(nèi)，離散采樣值由正到負(fù)和由負(fù)到正變化的次數(shù)。單位時(shí)間內(nèi)過零次數(shù)稱為過零率。一定程度上，它說明了平均信號(hào)頻率，它是區(qū)分音頻信號(hào)有聲或無聲的重要標(biāo)志之一[9]。過零率計(jì)算的公式如下：

(3)Mel變換對(duì)數(shù)倒譜系數(shù)(Mel-scaled Frequency Cepstral Coefficient, MF CC)。在表征音頻的多種特征中，Mel倒譜系數(shù)是一種非常重要的特征參數(shù)，它采用一種非線性的Mel頻率單位來模擬人耳的聽覺系統(tǒng)，充分考慮人耳聽覺的非線性特征，去除了因激勵(lì)影響而引起的音頻頻譜峰值的波動(dòng)，在音頻檢索中取得了非常好的效果[10]。這是音頻經(jīng)過Z變換和對(duì)數(shù)處理后得出的結(jié)果，一般對(duì)每幀數(shù)據(jù)取12個(gè)系數(shù)，可以很好地表現(xiàn)每幀的特征，計(jì)算得到的系數(shù)記為Mel[11-13]。Mel倒譜系數(shù)的提取流程如圖2所示。

圖2 Mel倒譜系數(shù)提取流程

計(jì)算特征段向量D={P0,P1,…,Pi,…,PN}的特征值w的過程分布到每個(gè)線程上，特征值 w的計(jì)算公式如下：

其中，Pi為音頻短時(shí)段D上的采樣點(diǎn)，N為音頻短時(shí)段D上的特征點(diǎn)的總數(shù)，0≤i≤N；α，β，γ為設(shè)定的權(quán)值，Energy(D)為音頻數(shù)據(jù)短時(shí)段D中采樣點(diǎn)的能量信息；Zn(D)為音頻數(shù)據(jù)短時(shí)段w中采樣點(diǎn)的過零率。

3.3 后綴數(shù)組查找

對(duì)待檢索音頻p和目標(biāo)音頻q的短時(shí)段計(jì)算特征值，得到特征值序列Wp={wp1,wp2,…,wpi,…,wpLp}和特征值序列Wq={wq1,wq2,…,wqj,…,wqLq}。其中，Lp，Lq分別為特征值序列的長(zhǎng)度，1≤i≤Lp,1≤j≤Lq；將特征值序列數(shù)值設(shè)為一個(gè)字符，構(gòu)建字符序列Vw={wp1,wp2,…,wpi,…,wpLp, X, wq1,wq2,…,wqj,…,wqLq}，X為隔斷標(biāo)記；構(gòu)建后綴數(shù)組[11]，其基本思路是計(jì)算Wp的所有后綴和Wq的所有后綴之間的最長(zhǎng)公共前綴的長(zhǎng)度，把最長(zhǎng)公共前綴長(zhǎng)度不小于k的部分全部加起來，k為設(shè)定的最小檢索長(zhǎng)度。掃描字符序列Vw={wp1,wp2,…,wpi,…,wpLp,X, wq1,wq2,…,wqj,…,wqLq}，每遇到一個(gè)Wq的后綴就統(tǒng)計(jì)與前面的Wp的后綴能產(chǎn)生多少個(gè)長(zhǎng)度不小于k的公共子串，這里Wp的后綴需要用一個(gè)單調(diào)的棧來高效地維護(hù)，其算法流程如圖3所示。

圖3 后綴數(shù)組變形算法流程

將得到公共子串集合按照位置對(duì)應(yīng)關(guān)系得出特征值向量Wp和Wq中對(duì)應(yīng)的公共序列集合Seq；合并整理，將公共交叉的數(shù)據(jù)段落合并，將連續(xù)的部分整理連接得到公共段落集合。

3.4 結(jié)果精化和整體匹配

將公共序列集合Seg整理，得到相同區(qū)域集合WSeg= {Seg1(p,q), Seg2(p,q),…,Segh(p,q),…,SegLw(p,q)}。其中，Segh(p,q)即為p、q兩音頻的第h段公共區(qū)域，h介于1～Lw之間，Lw為短時(shí)音頻段相同區(qū)域集合的長(zhǎng)度；按照順序?qū)⒍虝r(shí)音頻段相同區(qū)域集合進(jìn)行排序，遍歷短時(shí)段相同區(qū)域集合，若Segs(p,q)和Segt(p,q)存在數(shù)據(jù)段上交叉，則將其合并，整理得集合WSeg*={Seg1*(p,q),…,Segh*(p,q),…, SegLw*(p,q)}；遍歷新的集合，如滿足下列條件則將其合并：

條件1 若存在Segs*(p,q)和Segt*(p,q)不相鄰分別相隔1個(gè)短時(shí)段cpx、cqx，且Segs*(p,q)中音頻p的短時(shí)段特征值為wps，音頻q的短時(shí)段特征值為wqs，Segt*(p,q)中音頻p的短時(shí)段特征值為wpt，音頻q的短時(shí)段特征值為wqt，短時(shí)段cpx、cqx特征值為wpx、wqx。

條件2 若wps= wqs且wpt= wqt。

條件3 若wpx= wqx或| wpx-wqx|＜T，T為閾值。

重復(fù)上述合并過程，直至不能合并為止，合并后得到的新的集合即為最簡(jiǎn)短時(shí)段相同區(qū)域集合。

4 實(shí)驗(yàn)結(jié)果和分析

本文實(shí)驗(yàn)數(shù)據(jù)文件有3組，3組文件都來自于Testronic的數(shù)據(jù)庫：

(1)第1組文件是Testronic的shortTest文件，待檢索文件是shortTest-Original，長(zhǎng)度為190’，目標(biāo)文件是shortTest-Edit，長(zhǎng)度為600 s；

(2)第2組文件是音樂文件，來自Disney的Tangled片段，待檢索文件為Tangle-TLR，長(zhǎng)度為11’15’，目標(biāo)文件是Tangle-TLR-Clean，長(zhǎng)度為32’11’。

(3)第3組文件是電影文件Disney的Lionking片段，待檢索文件是LionKing-C，長(zhǎng)度為19’59’，目標(biāo)文件是LionKing-C-Clean，長(zhǎng)度為1°28’45’。

3組測(cè)試數(shù)據(jù)格式都是單聲道，采樣率為44.1 kHz，量化精度為24 bit。實(shí)驗(yàn)時(shí)發(fā)現(xiàn)將音頻分割片段設(shè)為5 s，閾值設(shè)為0.95時(shí)效果較好。

本文使用查全率(RR)、查準(zhǔn)率(PR)和時(shí)間(T)來評(píng)價(jià)算法的檢索性能，其定義如下：

實(shí)驗(yàn)采用的機(jī)器配置為Intel Core2、2.80 GHz CPU、4 GB內(nèi)存、NVIDIA GeForce GT440顯卡。表1是對(duì)上述3組音頻文件進(jìn)行檢索得到的結(jié)果。

表1 3組文件檢索結(jié)果

由實(shí)驗(yàn)結(jié)果可以看出：

(1)在速度方面，使用本文基于GPU加速的檢索方法比文獻(xiàn)[7]中基于CPU的算法節(jié)省了時(shí)間，且比較的音頻的時(shí)間越長(zhǎng)，節(jié)省的時(shí)間越多。shortTest組的加速比為10.86，Tangled組的加速比為11.39，LionKing組的加速比為13.58，可見音頻長(zhǎng)度越長(zhǎng)其加速比越大。這與GPU編程在數(shù)據(jù)量越大加速比越大是一致的。

(2)在查全率和查準(zhǔn)率方面，本文基于GPU加速的檢索方法與文獻(xiàn)[7]中CPU的算法性能相當(dāng)，均能保證查全率和查準(zhǔn)率在95%以上。

實(shí)驗(yàn)的3組數(shù)據(jù)分別為標(biāo)準(zhǔn)音頻測(cè)試數(shù)據(jù)、音樂數(shù)據(jù)和電影數(shù)據(jù)，本文方法對(duì)這3種數(shù)據(jù)都有較好的實(shí)驗(yàn)結(jié)果。這是由于本文方法是通過計(jì)算相似性進(jìn)行檢索的，不關(guān)心其具體的語義信息，故這種方法可以用來檢索任意類型的音頻數(shù)據(jù)。

5 結(jié)束語

本文提出了一種基于GPU加速的音頻檢索方法，利用GPU的并行計(jì)算能力減少了音頻檢索的時(shí)間。實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法的可行性和優(yōu)越性。音頻檢索是目前多媒體信息檢索領(lǐng)域研究的重點(diǎn)，未來會(huì)進(jìn)一步改進(jìn)算法結(jié)構(gòu)，如引進(jìn)更快的查找算法、基于Hash索引的方法[14]、引入模式匹配算法[15]等。本文創(chuàng)新點(diǎn)在于提出的方法首先使用數(shù)字音頻的特征將連續(xù)的音頻劃分成等長(zhǎng)的多個(gè)短時(shí)音頻段，并利用GPU加速算法計(jì)算每個(gè)短時(shí)音頻段的特征值，采用后綴數(shù)組得出初步檢索結(jié)果，進(jìn)一步精化和整體匹配后得到檢索結(jié)果，提高了檢索效率。

[1] Heryanto H, Akbar S, Sitohang B. Direct Access in Contentbased Audio Inf ormation Retrieval: A S tate of th e Art and Challenges[C]//Proc. of International Conference on Electrical Engineering and Informatics. Bandung, Indonesia: [s. n.], 2011: 1-6.

[2] Hansen J H L, Huang Rongqing. Speech Find: Advances in Spoken Docume nt Retrieval for a National Gallery of the Spoken Word[J]. IE EE T ransactions on Sp eech and Audio Processing, 2005, 13(5): 712-730.

[3] Chechil G, Le E, Rehn M, et al. Lar ge Scale Content Based Audio Retrieval from Text Queries[C]//Proc. of the 1st ACM International Conference on Multimedia Information Retrieval. New York, USA: [s. n.], 2008: 105-112.

[4] 齊曉倩, 陳鴻昶, 黃 海. 基于K-L距離的兩步固定音頻檢索方法[J]. 計(jì)算機(jī)工程, 2011, 37(19): 160-162.

[5] Su J H, W u C W, Fu Shaoyu, et al. Empirical Analysis of Content-based M usic R etrieval for Music Identific ation[C]// Proc. of International Co nference on Multimedia Technology. Hangzhou, China: [s. n.], 2011: 3516-3519.

[6] Jurkas P, S tefin A M, Novak D, et al. Audio Similarity Retrieval Engine[C]//Proc. of the 3rd International Conference on Similarity Search and Applications. Istanbul, Turkey: [s. n.], 2011: 121-122.

[7] Kashino K, Kurozumi L, Murase H. A Quick Search Method for Audio and Video Signals Based on Histogram Pruning[J]. IEEE Transactions on Multimedia, 2003, 5(3): 348-357.

[8] 談會(huì)星, 陳福才, 李邵梅. 基于模板子空間的快速固定音頻檢索方法[J]. 計(jì)算機(jī)工程, 2012, 38(20): 260-263.

[9] K edem B. Spectral Analysis and Discrimination by Zerocrossings[J]. Pro ceedings of the IEEE, 1986, 74(11): 147 7-1493.

[10] Li S Z. Content-based Classification and Retrieval of Audio Using the Nearest Feature Line Method[J]. IEEE Transactions on Speech Audio Processing, 2000, 8(5): 619-625.

[11] Johnson S E, Woodland P C. A Method for Direct Audio Search with Application to Indexing and Retrieval[C]//Proc. of IEEE International Co nference o n Acoustics, Spee ch and Signal Processing. New York, USA: [s. n.], 2000: 1427-1430.

[12] 江星華, 李 應(yīng). 基于LPCMCC的音頻數(shù)據(jù)檢索方法[J].計(jì)算機(jī)工程, 2009, 35(11): 246-247, 253.

[13] Manber U, Myers G. Suffix Arrays: A New Method for On-line String Searches[C]//Proc. of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms. Philadephia, USA: [s. n.], 1990: 319-327.

[14] Gionis A, I ndyk P, Mot wani R. Similarity Search in High Dimensions via Hashing[C]//Proc. of the 25th International Conference on Very Large Data Bases. San Francisco, USA: [s. n.], 1999: 518-529.

[15] Cheng Deyuan, Gersho A, Rama murthi B, e t al. Fast Search Algorithm for Vector Quantization and Pattern Mat ching[C]// Proc. of IEEE International Conference on Acoustics, Speech and Signal Processing. San Diego, USA: [s. n.], 1984: 372-375.

編輯 顧逸斐

Audio Retrieval Technology Based on GPU Acceleration

JIN Guo-ping1, YU Zong-qiao1, GUO Yan-wen1, JIANG He2

(1. Department of Computer Science and Technology, Nanjing University, Nanjing 210046, China; 2. School of Mathematical Sciences, Nanjing Normal University, Nanjing 210046, China)

As digital audio has a feature of great data volume, traditional audio retrieval method results are used in intolerable response time. In order to speed up audio retrieval, this paper proposes a GPU acceleration audio retrieval method. The audio is divided into multiple short audio segments based on the features, and the characteristic matrix is constituted by the eigenvalues which is calculated from e ach short audio segment using the GPU acceleration algorithm. The suffix array deformation algorithm is used to find the common set from the two eigenvalues sequence. The common set is refined and overall matched to get the retrieval resu lt. Experimental re sults show that the retrieval accuracy is over 95% and compared with existing algorithms, this method can significantly improve the retrieval speed and speedup can be achieved in more than 10 times.

audio retrieval; GPU acceleration; suffix array; audio characteristic; eigenvalue sequence; overall match

10.3969/j.issn.1000-3428.2014.05.055

國家自然科學(xué)基金資助項(xiàng)目(61073098, 61021062)；國家“973”計(jì)劃基金資助項(xiàng)目(2010CB327903)；江蘇省自然科學(xué)基金資助項(xiàng)目(BK2009081)。

金國平(1988－)，男，碩士研究生，主研方向：多媒體信息檢索；余宗橋，碩士研究生；郭延文(通訊作者)，副教授、博士、CCF會(huì)員；蔣 和，本科生。

2013-04-15

2013-05-15E-mail：ywguo@nju.edu.cn