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

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

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

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

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

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

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

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

1 概述

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

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

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

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

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

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

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

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

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

3.1 音頻分割

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

3.2 音頻特征抽取

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

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

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

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

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

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

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

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

3.3 后綴數(shù)組查找

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

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

將得到公共子串集合按照位置對應(yīng)關(guān)系得出特征值向量Wp和Wq中對應(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為短時音頻段相同區(qū)域集合的長度；按照順序?qū)⒍虝r音頻段相同區(qū)域集合進行排序，遍歷短時段相同區(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個短時段cpx、cqx，且Segs*(p,q)中音頻p的短時段特征值為wps，音頻q的短時段特征值為wqs，Segt*(p,q)中音頻p的短時段特征值為wpt，音頻q的短時段特征值為wqt，短時段cpx、cqx特征值為wpx、wqx。

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

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

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

4 實驗結(jié)果和分析

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

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

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

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

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

本文使用查全率(RR)、查準率(PR)和時間(T)來評價算法的檢索性能，其定義如下：

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

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

由實驗結(jié)果可以看出：

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

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

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

5 結(jié)束語

本文提出了一種基于GPU加速的音頻檢索方法，利用GPU的并行計算能力減少了音頻檢索的時間。實驗結(jié)果驗證了該方法的可行性和優(yōu)越性。音頻檢索是目前多媒體信息檢索領(lǐng)域研究的重點，未來會進一步改進算法結(jié)構(gòu)，如引進更快的查找算法、基于Hash索引的方法[14]、引入模式匹配算法[15]等。本文創(chuàng)新點在于提出的方法首先使用數(shù)字音頻的特征將連續(xù)的音頻劃分成等長的多個短時音頻段，并利用GPU加速算法計算每個短時音頻段的特征值，采用后綴數(shù)組得出初步檢索結(jié)果，進一步精化和整體匹配后得到檢索結(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]. 計算機工程, 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] 談會星, 陳福才, 李邵梅. 基于模板子空間的快速固定音頻檢索方法[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].計算機工程, 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

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

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

2013-04-15

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