一種改進的Philips音頻指紋檢索算法

,, ,

(1.上海音樂學院 a.音樂聲學藝術重點實驗室;b.音樂學系,上海 200031;2.上海計算機軟件技術開發中心,上海 201112)

0 概述

音頻指紋可以看作是音頻信號的獨一無二標識符,是通過音頻特征提取算法,提取特定特征而形成的特征序列。因此,一段音頻指紋,可以看成一段音頻內容的概括,并且能夠唯一表達這段音頻信號。因為音頻指紋能夠唯一表達音頻信號的特征,被廣泛地應用于音頻識別、音樂檢索、內容識別、分類、版權內容監管等應用領域[1-3]。

音頻指紋研究,核心內容包括2個部分:特征提取和檢索算法。在音頻特征提取的算法研究方面,目前國內外研究者已經提出大量算法,如文獻[4-8]。其中,以荷蘭Philips研究所[6]提出的基于相鄰能力差的變化來提取指紋和英國Shazam公司[5]基于譜峰點對(Peak-Pairs)形成的特征對指紋序列為典型代表。

由于Philips指紋內容簡單、容易實現、復雜度小、檢索效率高等優點,被廣泛應用。在Philips音頻指紋檢索系統中,結合指紋的特點,構造一個232查詢表作為索引表,由于查詢表太大,在應用中,利用哈希表代替查詢表,并分別存放。本文針對Philips音頻檢索算法提出改進方法。結合斐波那契數列和右移運算,構造一個新的哈希函數,利用斐波那契數列優化哈希值分布,執行右移操作調整哈希表長度,優化內存使用,從而提升系統的實用性。

1 相關知識介紹

本文研究基于Philips系統模型,結合哈希表與斐波那契數列對Philips音頻檢索算法實施改進,本節先回顧相關知識。

1.1 Philips音頻指紋的研究概況

Philips音頻指紋研究包括指紋提取和音頻檢索。其音頻指紋提取模型如圖1所示。

圖1 指紋提取模型

從圖1可知,音頻指紋提取包括4個步驟。

1)預處理。音頻信號轉化統一格式:單聲道PCM(16 bit),44.1 KHz,MP3等操作。

2)分幀。即對音頻信息進行分幀,這里是按照固定長度來進行。使用31/32重疊率,目的是抵消幀的邊界誤差,確保在最壞的情況下,真實指紋與查詢指紋仍然相似。此外,對每一幀添加漢明窗。

3)提取頻率子帶。對每一幀執行傅里葉變換,將原始時域數字信號轉化成頻譜表示,選擇與人類聽覺最相關的頻域:300 Hz～2 000 Hz頻率帶。接著,使用對數空間,將選擇的頻率帶劃分成33個非重疊的子帶。

4)提取指紋。首先,基于相鄰的頻率子帶的能量差符號推導字節,則第n幀的第m比特fn(m)定義為:

(1)

其中:

E=E(n,m)-E(n,m+1)-

E(n-1,m)+E(n-1,m+1)

(2)

基于式(1)字節推導,從33個非重疊的頻率子帶中提取32個連續比特形成一個指紋。

由于一個指紋信息量太少,在應用中,通常使用指紋塊。設一個音頻片段的指紋序列FP=f1f2…fN,塊長為L,則第i指紋塊定義為:

(3)

在Philips音頻檢索算法中,構造一個232的哈希表,檢索模型如圖2所示。

圖2 指紋檢索模型

在Philips檢索模型中,將候選查詢指紋作為查詢表的關鍵字進行匹配,然后快速定位到真實的指紋文件,接著計算指紋塊的相似度,根據閾值判斷是否相似。

1.2 哈希表

哈希表是一種高效的數據結構,通過把關鍵字(key)映射到表中一個位置來訪問記錄,以加快查找的速度。其中,哈希函數即為映射函數,哈希表即是存放記錄的數組。在大部分應用中,哈希表查找速度最快,其時間復雜度通常為常量,而且編程實現也相對容易。哈希表的原理其實就是通過空間換取時間的做法,哈希表示意圖如圖3所示。

圖3 哈希表結構示意圖

在哈希表設計中,設計目標遵循2個原則[9]:

1)每一個key對應唯一一個哈希值。

2)哈希值能夠均勻地分布到整個哈希表中。

但是,在實際的應用中,這種理想的設計很難實現,即哈希沖突不可避免[10]。

哈希沖突現象:2個關鍵字key1和key2,且key1≠key2,但他們的哈希值相等,即通過哈希函數映射到哈希表同一地址上的現象。

在實際應用中,哈希沖突的現象是避免不了的,但沖突的程度是能夠通過一些手段和方法來減少的,例如改進哈希函數的性能。因此,解決哈希沖突的根本原則是設計一個好的哈希函數,減少沖突概率,即實現較好的哈希值分布。

1.3 斐波那契數列

在哈希表應用中,斐波那契散列發被廣泛使用,其設計思想[11]:找出一個理想的乘數和key做乘法,目標實現哈希值的良好分布。

在文獻[12]中,已經證明這個理想的數[13]與黃金分割法則[14]有關,其具體數字與黃金分割法則的經典表達斐波那契數列[15]吻合,其計算等式:

C≈Wλ-1

(4)

其中,W代表字長,λ-1代表黃金分割比例的倒數。根據式(4),容易計算不同字節的C值,結果如表1所示。

表1 斐波那契數列

在實驗中,研究者們還發現,基于斐波那契數列的哈希分布有這樣的現象:新添加的哈希值,落入按照黃金分割法則分割的最大空間中。

2 算法的改進

在Philips音頻檢索算法中,構造了一張232的查詢表,由于內存消耗太大,在實際應用中,用哈希表代替查詢表,并分別存儲。此外,哈希表的利用率很低,一方面由于指紋數量遠遠小于哈希表的長度;另一方面,由于哈希值分布不均勻造成。例如,1萬首歌曲大約對應2.5億個指紋,據統計利用率不到0.058。

針對Philips指紋檢索的上述缺陷,本文提出一個改進算法。首先,基于斐波那契數列和右移運算,構造一個新的哈希函數,基于這個哈希函數的映射,哈希值具有良好的分布;此外,根據實際的應用需求,執行右移操作控制哈希表的長度,具體實現將在下面子節中描述。

2.1 哈希函數的構造

針對Philips指紋檢索的問題,首先設計一個哈希函數。

設計思想為利用斐波那契數列優化哈希值分布;接著,利用右移運算,結合具體的應用需求,靈活調整哈希表的長度,構造的哈希函數為:

f(FP)=(FP×C)>>N

(5)

其中,FP代表一個指紋,即相當一個32位的整數。C為斐波那契數列,從表1可以,C等于2654435769。N代表右移位數,范圍1≤N≤32。N的取值主要取決于實際內存的大小。通過右移操作,得到的哈希值高N位全部變成0。

2.2 哈希表的構造

通過構造哈希函數,指紋的高N位變成0,基于這個事實,調整哈希表的長度:232-N,這樣Philips哈希表模型改進如圖4所示。

圖4 哈希表模型

為了優化檢索速度,提出如下的優化策略:

1)構造2個哈希表,一個叫做索引表,另一個叫做指針表。索引表存儲真實指紋的地址信息;遍歷索引表,從上到下,每一個關鍵字按照節點的先后順序,進行編號,每一個關鍵字的最后一個節點的編號存入對于位置的指針表中。

2)遍歷索引表,從上到下,每一個關鍵字按照節點的先后順序,將所有節點信息寫入文件,叫做索引表文件,接著銷毀索引表。

從優化策略可知,指紋的查詢、插入與刪除操作都是基于索引表文件,其復雜度為O(N),為常數級。

2.3 檢索模型

基于2.2節的哈希表,改進的檢索模型如圖5所示。

圖5 檢索模型

檢索過程描述如下:

1)進行音頻指紋的提取查詢,這里利用Philips指紋提取算法來實現。

2)按照先后順序,每次從查詢指紋中選取一個指紋作為查詢候選指紋,利用構造哈希函數,將查詢候選指紋映射成指針表的key。

3)根據key和key+1,計算出候選真實指紋集位置信息。

4)根據位置信息,從索引表文件中讀取真實指紋集的信息進行匹配,如果匹配成功,繼續計算對應的指紋塊相似度,基于閾值判斷是否相似,相似則返回查詢成功信息,否則繼續比較剩余的指紋集直到結束。

5)繼續比較下一個查詢候選指紋,重復第3)步和第4)步,直至結束。

最后,輸出前Top-N最相似歌曲。

從查詢過程可以看出,僅指針表存放在內存中,根據實際的內存情況,調整的指針表長度為232-N,可以全部放入內存,實現快速檢索,從而實現提升Philips指紋檢索系統的實用性。

3 實驗結果與分析

本文通過實驗評估改進算法性能。實驗設計從3個方面進行評估:查詢精度,查詢速度和空間利用率,并與Philips研究做比較分析。

實驗通用參數配置如下:

1)數據庫,包括8 740段音樂片段,MP3和wav格式。

2)音樂的類型,包括流行音樂,古典音樂,民族音樂等。

3)實驗算法參數設置,幀長0.37 frame/s;指紋塊長度為256,大約3 s;相似閾值0.35。

3.1 查詢精度的評估

為了評估查詢精度,從某音樂網站下載免費音樂片段用于查詢,實驗分2組觀察:

1)元音數據,未添加任何噪音,原版音樂。

2)噪音數據,觀察噪音情況下,改進算法的性能變化。選擇噪音場景為鼓掌、尖叫以及其他環境噪音,將噪音添加到查詢音頻中,信噪比為100 dB,屬于輕度噪音級別。

3)服務器配置,32 GB內存,可用內存20 GB左右。

共選擇100首歌曲用于評估,評估的數據結果如表2所示。

表2 查詢精度 %

從表2結果可以看出,2種方面查詢精度相同。事實上,2種查詢的原理完全一樣,從設計理論上也可以驗證。從分享結果可知,改進的方法可以實現相同的精度,為后面的實驗提供基礎。

3.2 查詢速度的評估

本文改進的算法目標是優化Philips內存使用,所以查詢速度,主要觀察普通PC下,改進算法的查詢速度。

實驗設置:

1)觀察平均查詢速度,通過增加歌曲數量觀察查詢速度的變化,這里僅僅考察元音數據。

2)PC配置:4 GB內存,可用內存1.6 GB。

最后,實驗結果如圖6所示。

圖6 評估查詢效率

從圖6可以看出,隨著音樂數量的增加,查詢速度一直在0.97 s附件波動,相對比較平穩變化。查詢速度平穩的變化主要原因是由斐波那契數列優化效果。此外,針對查詢效率,本文提出一個優化策略,構造2個哈希表,指針表存儲索引表偏移信息;索引表存儲真實指紋的位置信息。通過指針表可以快速訪問索引表文件,定位真實指紋位置信息。索引表文件的優點是可以實現海量數據的快速訪問。

3.3 空間利用率的評估

Philips檢索算法的主要缺陷,就是內存消耗太大,本文針對這個缺陷提出改進。由于音樂數量較少,而Philips哈希表的長度太大,內存消耗改進的效果不言而喻,因此僅僅考察空間利用率性能,即基于相同的哈希表長度,考察斐波那契數列的作用。

將空間利用率定義(UR)為在哈希表中,已經利用的空占總空間的比例。UR為:

(6)

其中,UN代表已經占用的空間,L代表哈希表的總空間。實驗結果如圖7所示。

圖7 空間利用率

從圖7可以看出,提出的算法空間利用率顯著優于Philips方法,即哈希值呈現良好的分布。可見,基于構造哈希函數和哈希表,實現了哈希值的較好分布,空間利用率得到提升。

4 結束語

本文針對Philips音頻檢索算法對內存消耗太大的缺陷,提出改進算法。利用斐波那契數列和右移運算,實現了新哈希函數的構造和哈希值分布的優化,并且可以靈活地調整哈希表的長度。為提高查詢速度,提出優化策略。實驗結果表明,改進的算法具有相同的查詢精度,而且空間利用率顯著提升,即解決了Philips內存消耗過大的問題。下一步將深入研究噪音環境,針對如何提高音頻檢索的精度和檢索算法的健壯性展開研究。

[1] ZHAO Yong,ZHANG Aixin,LU Songnian.A Group-Based Fingerprinting Scheme for Digital Wholesale and Retail [J].China Communications,2014,11(10):126-135.

[2] DALIBOR M,MATTHIAS Z,CHRISTIAN B.Features for Content-based Audio Retrieval[J].Advances in Computers,2010,78:71-150.

[3] 牛憲華,曾柏森,陳思利.基于頻域和時域差分的音頻指紋算法研究[J].西華大學學報(自然科學版),2014,33(5):10-15.

[4] 孟建華,陳 寧.基于Gammachirp耳蝸能量譜特征提取的音頻指紋算法[J].華東理工大學學報(自然科學版),2015,41(5):666-670.

[5] WANG A.An Industrial Strength Audio Search Algorithm[C]//Proceedings of International Conference on Music Information Retrieval.Baltimore,USA:[s.n.],2003:7-13.

[6] HAITSMA J,KALKER T.A Highly Robust Audio Fingerprinting System[C]//Proceedings of International Conference on Music Information Retrieval.Washington D.C.,USA:[s.n.],2002:107-115.

[7] 明建成,韓 威.基于音頻指紋的壓縮域音頻識別方法研究[J].西華大學學報(自然科學版),2014,14(16):10-15.

[8] XIAO Q,SUZUKI M,KITA K.Fast Hamming Space Search for Audio Fingerprinting Systems[C]//Proceedings of International Conference on Music Information Retrieval.Washington D.C.,USA:[s.n.],2011:133-138.

[9] DAMGARD I B.A Design Principle for Hash Functions[C]//Proceedingsof Conference on the Theory and Application of Cryptology.Berlin,Germany:Springer,1989:416-427.

[10] BELLARE M,ROGAWAY P.Collision-resistant Hashing:Towards Making UOWHFs Practical[C]//Proceedings of the 17th Annual International Cryptology Conference.New York,USA:ACM Press,1997:416-427.

[11] AYDIN F,DOGAN G.Development of a New Integer Hash Function with Variable Length Using Prime Number Set[J].Balkan Journal of Electrical & Computer Engineering,2003,1(1):10-14.

[12] ULLANATT V.Summary Representation for Service Discovery Protocols [D].North Carolin,USA: North Carolina State University,2001.

[13] SHIU P,NIVEN I,ZUCKERMAN H S,et al.An Introduction to the Theory of Numbers[J].Mathematical Gazette,2013,39(328):401-405.

[14] MARKOWSKY G.Misconceptions About the Golden Ratio[J].The College Mathematics Journal,1992,23(1):2-19.

[15] DUNCAN R I.Application of Uniform Distribution to the Fibonacci Numbers[J].Fibonacci Quarterly,1967,5(5):137-140.