一種基于倒排索引的音頻檢索方法

張雪源 賀前華 李艷雄 葉婉玲

(華南理工大學電子與信息學院 廣州 510640)

1 引言

隨著多媒體信息爆炸式的增長，如何從海量的、未經(jīng)手工標注的多媒體數(shù)據(jù)庫中快速、準確地搜索到最理想的內(nèi)容逐漸成為當前學術(shù)研究的熱點。音頻信息作為多媒體數(shù)據(jù)的重要組成部分，有時甚至是唯一的形式(如廣播、音樂和電話錄音等)，其索引和檢索算法受到了越來越多的關(guān)注[1]。

音頻的檢索方法可分為兩種：一種基于語義，另一種基于相似度?；谡Z義的檢索方法利用先驗模型對音頻數(shù)據(jù)進行語義索引，其索引內(nèi)容多為音效類型、音頻場景類型[2,3]。檢索時依據(jù)用戶提交的音效語義描述、場景語義描述進行基于文本的檢索。這種方法實現(xiàn)了多媒體內(nèi)容的自動標注和檢索，并且依靠語音識別系統(tǒng)實現(xiàn)了語音文檔檢索。但由于音頻內(nèi)容十分復雜、多變，文字在描述音頻內(nèi)容上不夠精細，如“槍聲”這一音效類型忽略了槍聲的強弱、密集程度以及槍的類型等重要信息，因此難以跨越的“語義鴻溝”嚴重影響了這種方法的效果。此外，這一類方法需要預先定義音效、場景類型，檢索時只能從事先定義好的類型中選擇檢索條目。近年來越來越多的研究開始關(guān)注基于相似度的檢索算法[4,5]。該方法直接利用音頻檢索音頻，不需要進行音效、場景識別，也不需要提前定義和訓練模型。用戶提交一段現(xiàn)有的或者自己制作的音頻作為查詢，檢索系統(tǒng)從數(shù)據(jù)庫中尋找與之最為相似的片段。該方法將數(shù)據(jù)庫的音頻流切割成片段作為候選，檢索時采用遍歷的方法從頭至尾依次計算查詢音頻和候選音頻之間的距離。由于采用遍歷策略，并且音頻段之間距離計算的計算量較大，此類方法在面對海量數(shù)據(jù)庫的檢索時的等待時間難以忍受。此外，在對音頻切割后，每一個候選片段便已經(jīng)確定，無法檢索到候選片段的一部分或者由連續(xù)多個候選片段組成的段落。文獻[6]提出了一種快速瀏覽檢索算法，該算法以直方圖描述經(jīng)矢量量化后的特征分布，并以動態(tài)步長跳過相似度低的部分從而加速檢索。雖然該方法在速度上有較大提升，但其本質(zhì)仍為順序索引，并且沒有很好地利用音頻時序信息。

遍歷式檢索方法的計算量與數(shù)據(jù)庫大小成線性關(guān)系，對于動輒上千小時的電影數(shù)據(jù)庫，遍歷式的檢索在響應時間上難以滿足要求。倒排索引由于其出色的表現(xiàn)被廣泛應用在文本檢索中。目前，倒排索引在音頻檢索領(lǐng)域的應用主要集中在語音文檔檢索[7]，依賴語音識別器進行語音識別后建立文字索引。此外，文獻[8]將其應用在音樂檢索上，文獻[9]將其應用在了鳥叫聲音的檢索上，目前尚未見文獻應用于一般音頻數(shù)據(jù)的索引和檢索。本文利用文本搜索引擎中的倒排索引方法，為音頻建立音頻字典和倒排索引，提出基于倒排索引的音頻檢索方法。本文將連續(xù)音頻流轉(zhuǎn)換為音頻字序列并建立倒排索引文檔。在檢索時利用倒排索引實現(xiàn)候選段落的直接定位，利用基于音頻字相似度的距離公式對候選段落進行排序。

2 倒排索引

文本檢索中，順序的檢索意味著遍歷每一篇文章的每一個字并判斷是否與查詢關(guān)鍵字相匹配。當文章數(shù)量極大時，這種做法的效率極低。由于用戶等待時間、處理器、內(nèi)存上的限制，該方法不適用于現(xiàn)代大規(guī)模數(shù)據(jù)庫的搜索。

倒排索引是現(xiàn)代搜索引擎最常用的索引方式[10]。所謂“倒排”與順序的索引不同，它將文檔-詞信息流轉(zhuǎn)換為詞項-文檔信息[11]。該方法首先建立一個由索引項構(gòu)成的索引項詞表，索引項是描述數(shù)據(jù)庫文檔的最小單元，可以是單詞、字甚至音素(常見于基于網(wǎng)格的語音文檔檢索中)。之后，需要將每個索引項在文檔中的位置添加到倒排索引中。如以下3個文檔：文檔1：書本知識；文檔2：書中的知識；文檔3：這本書很好。

倒排索引表由兩部分構(gòu)成，即索引項列表和每個索引項自身的事件表，事件表中的每一項均是一個指針，指向了含有該索引項的內(nèi)容在文檔中的具體位置，每一個位置(a,b)中a代表文檔編號，b代表該索引項在文檔中的具體位置。文檔 1～文檔 3的倒排索引如表1所示。

表1 倒排索引

當用戶提交一個查詢時，如查詢?yōu)椤皶?，通過查詢索引項列表及該索引項對應的事件表，可以快速定位所有該索引項出現(xiàn)的位置，即{(1,1),(2,1),(3,3)}。當用戶提交的查詢?yōu)椤皶尽边@樣的短語時，首先依次確定各個索引項的位置：

其次確定所有索引項都命中的文檔，即對各索引項所命中的文檔編號取交集，{1,2,3} ∩ {1,3}={1,3}，即第1個文檔和第3個文檔命中所有索引項，但只有第1個文檔與查詢的索引項順序一致，因此第一返回結(jié)果應為文檔1的位置1～位置2。

3 基于倒排索引的音頻檢索方法

搜索引擎必須具備兩種功能：索引處理和查詢處理。索引處理的目的是建立可快速查找的數(shù)據(jù)結(jié)構(gòu)，查詢處理根據(jù)這些數(shù)據(jù)結(jié)構(gòu)和用戶提交的查詢生成排好序的檢索結(jié)果。

索引階段，對音頻流提取特征并進行分割，將持續(xù)若干小時的連續(xù)音頻分成短時音頻片段。之后根據(jù)事先訓練好的音頻字典，將短時音頻段序列轉(zhuǎn)換為音頻字序列。每一個音頻字都是這一段音頻的集中表示，可以看作文本索引中的“關(guān)鍵字”。之后為音頻字建立倒排索引。檢索階段，對用戶提交的查詢同樣進行特征提取、分割并轉(zhuǎn)換為音頻字，查找倒排索引后，將查找結(jié)果按照和查詢的相似度由高到低排序并返回給用戶。其過程如圖1所示。

3.1 特征提取

圖1 音頻索引和檢索系統(tǒng)方法

為了能充分反映各種類型音頻的特性，本文的研究中使用多種特征構(gòu)成的超向量作為音頻特征，包括短時能量、短時過零率等時域特征，譜能量、子帶能量比、譜質(zhì)心、譜帶寬等頻域特征，能反映人耳聽覺效果的梅爾(Mel)頻率倒譜特征[12]。每種音頻特征均描述了音頻信號某一方面特性，為了充分表征音頻內(nèi)容，本文將該15維超向量作為特征以充分表征語音、音樂和一般音頻等各類音頻信號的特性。由于各維特征數(shù)值范圍上有很大不同，如子帶能量比數(shù)值位于區(qū)間[0,1]，而譜質(zhì)心的數(shù)值可輕易達到1000以上，在后續(xù)處理中，例如計算歐氏距離時，數(shù)值范圍大的特征會輕易覆蓋掉其他特征的影響。因此需要對各維特征進行歸一化。事先收集各種音頻數(shù)據(jù)，包括電影、電視劇、電視訪談節(jié)目、體育比賽、廣播、頒獎典禮、音樂會等類型數(shù)據(jù)共210 h，提取特征后分別計算各維特征的均值和標準差當作規(guī)整向量。之后對其他數(shù)據(jù)提取特征時，用該規(guī)整向量按式(1)對特征進行規(guī)整。

其中D為特征總維數(shù)，fd和分別為原始特征和規(guī)整后的特征，μd和σd分別為規(guī)整用的均值和標準差。該方法會將各維特征規(guī)整到均值為0，方差為1的分布中。

3.2 音頻分割

分詞是文本索引中的重要模塊，與之類似，連續(xù)音頻流的自動分割是音頻索引的首要步驟。音頻分割的目的是檢測出連續(xù)音頻流中的聲學特征變化點，從而把音頻流切分成具有某種相同性質(zhì)(如同一說話人、同一信道或者同一音效類型)的音頻片段。為了對連續(xù)音頻流用音頻字進行表示，本文將音頻數(shù)據(jù)切割成聲學特征變化較小的短時音頻段。由于多媒體數(shù)據(jù)動輒持續(xù)1 h以上(如電影或者音樂會)，有的甚至始終不停止(如 24 h播放的廣播或者新聞)。采用計算十分準確的分割方法會造成巨大的計算量需求，采用計算量低的方法分割效果又不令人滿意。本文提出一種3階段的自頂向下多層分割方法，使用由粗到細的多層分割策略，將長達數(shù)小時的連續(xù)音頻流分割成短時音頻段：第1階段利用能量對音頻進行粗略的分割；第2階段利用T2距離將音頻分成音頻類型一致的片段；第3階段利用聲學特征一階、二階統(tǒng)計量保證每個短時音頻段內(nèi)的聲學特征數(shù)值處于較小的變化范圍內(nèi)。

在多媒體數(shù)據(jù)中，靜音是最明顯的分割點，當超過連續(xù)2 s的音頻短時幀能量均小于能量門限則認為該音頻片段為靜音段。由于不同音頻文檔其能量浮動范圍很大，各文檔利用能量值自動確定能量門限。Emax,Emin和Emean分別代表當前音頻文檔短時幀能量的最大值、最小值和均值，Erange表示能量的浮動范圍。能量門限Eth應當在Emin和Emin+Erange之間，以靜音因子λs(λs∈[0,1])決定能量門限具體數(shù)值，計算方法為

λs的取值由實驗確定，為涵蓋盡可能廣的音頻類型，實驗數(shù)據(jù)選用 3.1節(jié)中用于計算規(guī)整向量的 210 h音頻，實驗結(jié)果顯示λs取0.1時有最好的分割效果。

在靜音分割的基礎(chǔ)上，繼續(xù)將音頻分割成音頻類型相同的段落。本文利用逐漸增長的分析窗，依次計算分,析窗內(nèi)部各測試點左右兩邊數(shù)據(jù)窗之間的Hotelling'sT2距離[13]，將超過預設(shè)門限的峰值位置當作改變點，距離公式計算如下：

其中N和Σ分別為分析窗總長度和數(shù)據(jù)的協(xié)方差矩陣，b和μ1分別為測試點左側(cè)數(shù)據(jù)窗長度和特征均值，μ2為右側(cè)數(shù)據(jù)窗特征均值。設(shè)定分析窗初始長度為3 s，如果窗內(nèi)未發(fā)現(xiàn)音頻類型改變點，則窗長增加1 s，如果窗內(nèi)找到改變點則將分析窗長重置為初始長度，并以該改變點位置作為起點繼續(xù)搜索下一改變點直至搜索至數(shù)據(jù)尾端。

利用T2公式可以將音頻數(shù)據(jù)分割為單一音頻類型段，下一步根據(jù)音頻特征的均值和方差進行分割。首先初始化長度為30幀的分析窗，計算其協(xié)方差矩陣為Σ，以中點分割分析窗得到分別為15幀的左右兩個數(shù)據(jù)窗，其特征均值分別記為μ1和μ2,D為特征維數(shù)，計算兩數(shù)據(jù)窗均值的歐氏距離為

假設(shè)特征各維獨立，協(xié)方差矩陣Σ簡化為對角陣，則

當左右兩數(shù)據(jù)窗均值距離或者方差超過預設(shè)門限時，均認為分析窗內(nèi)部存在較大的數(shù)據(jù)變化，則當前分割點即為改變點。如果均值距離和方差均沒有超過門限，則將左側(cè)數(shù)據(jù)窗向后增加5幀，右側(cè)數(shù)據(jù)窗向后平移5幀，繼續(xù)計算直至找到改變點或者搜索至數(shù)據(jù)尾端。

經(jīng)過上述3層分割，可以將任意長度的連續(xù)音頻流準確而有效地分割為音頻特征數(shù)值波動幅度較小的短時段落。由于前兩分割階段分別采用能量極小值點和音效類型改變點進行分割，只有第3階段依賴均值和方差的統(tǒng)計，因此，當音頻數(shù)據(jù)起點略有偏移時，第3分割階段所造成的分割偏差累積主要存在于音頻的起始和結(jié)尾部分，而對音頻中間主體部分的分割影響較小，而音頻的主要內(nèi)容一般存在于中間主體部分，因此該分割方法具有起點魯棒性。

3.3 建立音頻字典

在文本檢索中，關(guān)鍵字或者關(guān)鍵詞是文檔的索引項，索引項的集合稱為索引項詞表。與之類似，我們定義音頻中劃分單元內(nèi)容的表示為“音頻字”，所有音頻字的集合構(gòu)成了“音頻字典”。本節(jié)介紹如何構(gòu)建音頻字和音頻字典。

音頻字的個數(shù)將影響檢索的效果：如果音頻字個數(shù)過多，極限情況是將每一幀特征都視為一個音頻字，一方面會產(chǎn)生尺寸十分巨大的音頻字典，另一方面也會將十分相似的音頻內(nèi)容判別為不同的音頻字，造成十分相似的音頻卻有完全不同的音頻字序列；反之，音頻字個數(shù)過少會導致音頻字對音頻內(nèi)容的區(qū)分能力下降，產(chǎn)生過多音頻字序列完全一致的段落。

本文依據(jù)音效類型(語音、槍聲、爆炸聲、歡呼聲等)的個數(shù)確定音頻字典大小。文獻[14]根據(jù)音源的不同將音效分成了400種類型。為了避免將不同音效判別為同一音頻字，每一種音效至少需要一個音頻字表征。同時，每一種音效由于存在多種變化形式，因此本文對每一種音效使用3個音頻字進行表征。訓練音頻字典時，首先為每一種音效收集100個樣本，進行特征提取后，將該音效的所有特征使用k-均值聚類算法[15]聚成3個類，所有音效總共產(chǎn)生1200個類中心。每一個聚類中心作為一個音頻字wi，由此產(chǎn)生的音頻字典為W={w1,w2,…,wK},K=1 200。

3.4 音頻索引

本節(jié)討論如何利用音頻字典將連續(xù)音頻數(shù)據(jù)轉(zhuǎn)換為音頻字序列并建立倒排索引。

圖2 音頻字序列示意圖

表2 音頻倒排索引表

3.5 音頻檢索

在文本檢索中，檢索的任務(wù)是接受用戶的查詢并利用檢索、排序算法返回給用戶一個排好序的文檔列表，排名越靠前的結(jié)果與用戶提交查詢的相似度應當越高。

所謂“命中”是指存在某音頻字既出現(xiàn)在查詢中也出現(xiàn)在音頻文檔中。假設(shè)查詢Q中qn對應的音頻字為wk，則qn命中的位置為：倒排索引表中wk對應事件表里的所有位置。對qn命中的任意一個位置(i,j)，可確定一個候選段落：文檔i中以第j-(n-1)個音頻字為起點，第j+(NQ-n)個音頻字為終點的段落，其長度和查詢一致，為NQ。

計算查詢和所有候選文檔的相似度，并按照由大到小的順序排列，將排好序的結(jié)果返回給用戶，完成檢索過程。

4 實驗仿真

為驗證本文方法，使用服務(wù)器(Intel(R)Xeon(R)CPU, E5606@2.13 GHz 2.13 GHz(2處理器，共8核)，32.0 GB內(nèi)存，64位Windows7操作系統(tǒng))進行實驗仿真，以Matlab 2010為仿真平臺。實驗數(shù)據(jù)為來自互聯(lián)網(wǎng)的187部電影，總時長200 h，依據(jù)IMDb分類標準[16]，各類電影數(shù)量見表3。

表3 各類電影數(shù)量分布

4.1 評價指標

從數(shù)據(jù)庫音頻中隨機截取不同長度的音頻段落作為查詢，記錄下該查詢音頻在數(shù)據(jù)庫中的音頻文檔編號及其在文檔中的段落位置(起點和終點)作為標簽，該標簽用來評價檢索算法的性能。檢索系統(tǒng)的返回結(jié)果列表中每一個結(jié)果項均為一個和查詢時長一樣的音頻片段，當該結(jié)果項所屬的音頻文檔編號和查詢一致，并且該結(jié)果項在該音頻文檔中的段落位置和查詢標簽所標示的段落位置重疊超過50%時，認為該結(jié)果項為一個“匹配項”。返回結(jié)果列表中匹配項排名越靠前意味著檢索算法性能越好。

本文以以下4項作為檢索性能評價指標，與文獻[6]提出的經(jīng)典快速順序搜索方法進行比較：

(1)在檢索結(jié)果列表中，匹配項的排名分布。本文分別統(tǒng)計第1返回結(jié)果和前10名返回結(jié)果中含有匹配項的查詢數(shù)占總查詢數(shù)的比例，分別記為PT1(Precision in Top 1)和PT10(Precision in Top 10)；

(2)前 10名檢索結(jié)果中和查詢屬于同一類型電影的平均個數(shù)STR(Same Type Ratio)。該項指標的值越高，則前10名返回結(jié)果中和查詢屬于同類電影的結(jié)果越多，和查詢無關(guān)的結(jié)果越少；

(3)匹配項和查詢在時間上的平均重疊比例 OR(Overlap Ratio)；

(4)平均檢索用時RT(Retrieval Time)。

4.2 實驗結(jié)果及分析

本文分別以5 s, 10 s, 15 s, 20 s作為查詢長度QL(Query Length)進行4次實驗，以驗證不同長度的查詢對檢索性能的影響，每次實驗均提交 21615次查詢。表4顯示了本文提出的方法和文獻[6]中的方法的實驗結(jié)果。

表4 檢索性能比較

由實驗結(jié)果可以看出，PT1方面，本文的方法和傳統(tǒng)方法都隨著查詢長度的增加而有更好的查詢效果；任一查詢長度，本文提出的方法均優(yōu)于傳統(tǒng)方法，相對提升比例分別為1.31%, 2.89%, 3.77%和4.65%。該統(tǒng)計說明，隨著查詢長度的增長，本文方法在性能上的提高越來越明顯。該指標性能提升的原因在于本文使用的相似度測度考慮了時序上的匹配，只有當查詢和候選段落在內(nèi)容和時序上均相似時才能得到很高的相似度值。在 PT10方面，本文的方法和傳統(tǒng)方法性能相當，說明兩種方法在前10名的返回結(jié)果中搜索到匹配項的能力相當。在STR方面，本文的方法較傳統(tǒng)方法均有一定的提升，即本文所產(chǎn)生的返回結(jié)果列表中，和查詢“相關(guān)”的結(jié)果更多，其原因在于本文所使用的音頻字典，能夠?qū)⑾嗨频囊纛l內(nèi)容劃分到一個音頻字上，即能夠很好地檢測到相似的音頻內(nèi)容。在OR方面，本文方法和傳統(tǒng)方法性能相當，均能保證平均在90%以上的重疊比例，即偏移小于10%。在時間上，由于本文使用了倒排文檔作為索引結(jié)構(gòu)，檢索用時大大減少，分別為原來用時的 1.04%, 1.36%, 1.61%和1.83%，速度提升均在50倍以上。

5 結(jié)束語

本文針對音頻實例檢索提出了基于倒排索引的檢索算法。通過音頻字轉(zhuǎn)換可以將連續(xù)音頻流轉(zhuǎn)換為音頻字序列，通過建立倒排文檔可以實現(xiàn)候選段落直接定位，通過融合時序信息的相似度計算公式可實現(xiàn)候選段落排序。實驗結(jié)果顯示了該算法的準確性和有效性。

[1]Heryanto H, Akbar S, and Sitohang B. Direct access in content-based audio information retrieval: a state of the art and challenges[C].2011 International Conference on Electrical Engineering and Informatics, Bandung, Indonesia,July 17-19, 2011: 1-6.

[2]Ghoraani B and Krishnan S. Time-frequency matrix feature extraction and classification of environmental audio signals[J].IEEE Transactions on Audio,Speech, and Language Processing, 2011, 19(7): 2197-2209.

[3]Fu Zhou-yu, Lu Guo-jun, Ting Kai-ming,et al.. Music classification via the bag-of-features approach[J].Pattern Recognition Letters, 2011, 32(14): 1768-1777.

[4]Su Ja-hwung, Wu Cheng-we, Fu Shao-yu,et al.. Empirical analysis of content-based music retrieval for music identification[C]. 2011 International Conference on Multimedia Technology, Hangzhou, China, July 26-28, 2011:3516-3519.

[5]Jurkas P, Stefina M, Novak D,et al.. Audio similarity retrieval engine[C]. Proceedings of the Third International Conference on Similarity Search and Applications, Istanbul,Turkey, Sep. 18-19, 2010: 121-122.

[6]Kashino K, Kurozumi T, and 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.

[7]Matthews B, Chaudhari U, and Ramabhadran B. Fast audio search using vector space modeling[C]. IEEE Workshop on Automatic Speech Recognition & Understanding, Kyoto,Japan, Dec. 9-13, 2007: 641-646.

[8]Cha Guang-ho. An effective and efficient indexing scheme for audio fingerprinting[C]. 5th FTRA International Conference on Multimedia and Ubiquitous Engineering, Loutraki, Greece,June 28-30, 2011: 48-52.

[9]Bardeli R. Similarity search in animal sound databases[J].IEEE Transactions on Multimedia,2009, 11(1): 68-76.

[10]黃少林, 王華, 張玉紅, 等. 基于Lucene的索引系統(tǒng)的設(shè)計與實現(xiàn)[J]. 現(xiàn)代情報, 2009, 29(7): 169-171.

Huang Shao-lin, Wang Hua, Zhang Yu-hong,et al.. The design and implementation of indexing system based on lucene[J].Journal of Modern Information, 2009, 29(7):169-171.

[11]Bruce C, Donald M, and Trevor S. Search Engines:Information Retrieval in Practice[M]. Upper Saddle River:Addison-Wesley, 2010: 22-23.

[12]韓紀慶, 馮濤, 鄭貴濱, 等. 音頻信息處理技術(shù)[M]. 北京: 清華大學出版社, 2007: 32-46.

Han Ji-qing, Feng Tao, Zheng Gui-bin,et al.. Audio Information Processing Technology[M]. Beijing: Tsinghua University Press, 2007: 32-46.

[13]Zhou Bo-wen and Hansen J H L. Efficient audio stream segmentation via the combined T2 statistic and Bayesian information criterion[J].IEEE Transactions on Speech and Audio Processing, 2005, 13(4): 467-474.

[14]劉成太. 音效分類數(shù)據(jù)庫[OL]. http://www.yinxiao.net/,2012-04-20.

[15]Lloyd S. Least squares quantization in PCM[J].IEEE Transactions on Information Theory, 1982, 28(2): 129-137.

[16]亞馬遜公司. 在線影視數(shù)據(jù)庫[OL]. http://www.imdb.com,2012-04-20.