,, ,

(1.上海音樂學(xué)院 a.音樂聲學(xué)藝術(shù)重點(diǎn)實(shí)驗(yàn)室;b.音樂學(xué)系,上海 200031;2.上海計(jì)算機(jī)軟件技術(shù)開發(fā)中心,上海 201112)

0 概述

音頻指紋可以看作是音頻信號(hào)的獨(dú)一無二標(biāo)識(shí)符,是通過音頻特征提取算法,提取特定特征而形成的特征序列。因此,一段音頻指紋,可以看成一段音頻內(nèi)容的概括,并且能夠唯一表達(dá)這段音頻信號(hào)。因?yàn)橐纛l指紋能夠唯一表達(dá)音頻信號(hào)的特征,被廣泛地應(yīng)用于音頻識(shí)別、音樂檢索、內(nèi)容識(shí)別、分類、版權(quán)內(nèi)容監(jiān)管等應(yīng)用領(lǐng)域[1-3]。

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

由于Philips指紋內(nèi)容簡(jiǎn)單、容易實(shí)現(xiàn)、復(fù)雜度小、檢索效率高等優(yōu)點(diǎn),被廣泛應(yīng)用。在Philips音頻指紋檢索系統(tǒng)中,結(jié)合指紋的特點(diǎn),構(gòu)造一個(gè)232查詢表作為索引表,由于查詢表太大,在應(yīng)用中,利用哈希表代替查詢表,并分別存放。本文針對(duì)Philips音頻檢索算法提出改進(jìn)方法。結(jié)合斐波那契數(shù)列和右移運(yùn)算,構(gòu)造一個(gè)新的哈希函數(shù),利用斐波那契數(shù)列優(yōu)化哈希值分布,執(zhí)行右移操作調(diào)整哈希表長(zhǎng)度,優(yōu)化內(nèi)存使用,從而提升系統(tǒng)的實(shí)用性。

1 相關(guān)知識(shí)介紹

本文研究基于Philips系統(tǒng)模型,結(jié)合哈希表與斐波那契數(shù)列對(duì)Philips音頻檢索算法實(shí)施改進(jìn),本節(jié)先回顧相關(guān)知識(shí)。

1.1 Philips音頻指紋的研究概況

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

圖1 指紋提取模型

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

1)預(yù)處理。音頻信號(hào)轉(zhuǎn)化統(tǒng)一格式:單聲道PCM(16 bit),44.1 KHz,MP3等操作。

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

3)提取頻率子帶。對(duì)每一幀執(zhí)行傅里葉變換,將原始時(shí)域數(shù)字信號(hào)轉(zhuǎn)化成頻譜表示,選擇與人類聽覺最相關(guān)的頻域:300 Hz～2 000 Hz頻率帶。接著,使用對(duì)數(shù)空間,將選擇的頻率帶劃分成33個(gè)非重疊的子帶。

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

(1)

其中:

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

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

(2)

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

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

(3)

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

圖2 指紋檢索模型

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

1.2 哈希表

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

圖3 哈希表結(jié)構(gòu)示意圖

在哈希表設(shè)計(jì)中,設(shè)計(jì)目標(biāo)遵循2個(gè)原則[9]:

1)每一個(gè)key對(duì)應(yīng)唯一一個(gè)哈希值。

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

但是,在實(shí)際的應(yīng)用中,這種理想的設(shè)計(jì)很難實(shí)現(xiàn),即哈希沖突不可避免[10]。

哈希沖突現(xiàn)象:2個(gè)關(guān)鍵字key1和key2,且key1≠key2,但他們的哈希值相等,即通過哈希函數(shù)映射到哈希表同一地址上的現(xiàn)象。

在實(shí)際應(yīng)用中,哈希沖突的現(xiàn)象是避免不了的,但沖突的程度是能夠通過一些手段和方法來減少的,例如改進(jìn)哈希函數(shù)的性能。因此,解決哈希沖突的根本原則是設(shè)計(jì)一個(gè)好的哈希函數(shù),減少?zèng)_突概率,即實(shí)現(xiàn)較好的哈希值分布。

1.3 斐波那契數(shù)列

在哈希表應(yīng)用中,斐波那契散列發(fā)被廣泛使用,其設(shè)計(jì)思想[11]:找出一個(gè)理想的乘數(shù)和key做乘法,目標(biāo)實(shí)現(xiàn)哈希值的良好分布。

在文獻(xiàn)[12]中,已經(jīng)證明這個(gè)理想的數(shù)[13]與黃金分割法則[14]有關(guān),其具體數(shù)字與黃金分割法則的經(jīng)典表達(dá)斐波那契數(shù)列[15]吻合,其計(jì)算等式:

C≈Wλ-1

(4)

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

表1 斐波那契數(shù)列

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

2 算法的改進(jìn)

在Philips音頻檢索算法中,構(gòu)造了一張232的查詢表,由于內(nèi)存消耗太大,在實(shí)際應(yīng)用中,用哈希表代替查詢表,并分別存儲(chǔ)。此外,哈希表的利用率很低,一方面由于指紋數(shù)量遠(yuǎn)遠(yuǎn)小于哈希表的長(zhǎng)度;另一方面,由于哈希值分布不均勻造成。例如,1萬(wàn)首歌曲大約對(duì)應(yīng)2.5億個(gè)指紋,據(jù)統(tǒng)計(jì)利用率不到0.058。

針對(duì)Philips指紋檢索的上述缺陷,本文提出一個(gè)改進(jìn)算法。首先,基于斐波那契數(shù)列和右移運(yùn)算,構(gòu)造一個(gè)新的哈希函數(shù),基于這個(gè)哈希函數(shù)的映射,哈希值具有良好的分布;此外,根據(jù)實(shí)際的應(yīng)用需求,執(zhí)行右移操作控制哈希表的長(zhǎng)度,具體實(shí)現(xiàn)將在下面子節(jié)中描述。

2.1 哈希函數(shù)的構(gòu)造

針對(duì)Philips指紋檢索的問題,首先設(shè)計(jì)一個(gè)哈希函數(shù)。

設(shè)計(jì)思想為利用斐波那契數(shù)列優(yōu)化哈希值分布;接著,利用右移運(yùn)算,結(jié)合具體的應(yīng)用需求,靈活調(diào)整哈希表的長(zhǎng)度,構(gòu)造的哈希函數(shù)為:

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

(5)

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

2.2 哈希表的構(gòu)造

通過構(gòu)造哈希函數(shù),指紋的高N位變成0,基于這個(gè)事實(shí),調(diào)整哈希表的長(zhǎng)度:232-N,這樣Philips哈希表模型改進(jìn)如圖4所示。

圖4 哈希表模型

為了優(yōu)化檢索速度,提出如下的優(yōu)化策略:

1)構(gòu)造2個(gè)哈希表,一個(gè)叫做索引表,另一個(gè)叫做指針表。索引表存儲(chǔ)真實(shí)指紋的地址信息;遍歷索引表,從上到下,每一個(gè)關(guān)鍵字按照節(jié)點(diǎn)的先后順序,進(jìn)行編號(hào),每一個(gè)關(guān)鍵字的最后一個(gè)節(jié)點(diǎn)的編號(hào)存入對(duì)于位置的指針表中。

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

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

2.3 檢索模型

基于2.2節(jié)的哈希表,改進(jìn)的檢索模型如圖5所示。

圖5 檢索模型

檢索過程描述如下:

1)進(jìn)行音頻指紋的提取查詢,這里利用Philips指紋提取算法來實(shí)現(xiàn)。

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

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

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

5)繼續(xù)比較下一個(gè)查詢候選指紋,重復(fù)第3)步和第4)步,直至結(jié)束。

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

從查詢過程可以看出,僅指針表存放在內(nèi)存中,根據(jù)實(shí)際的內(nèi)存情況,調(diào)整的指針表長(zhǎng)度為232-N,可以全部放入內(nèi)存,實(shí)現(xiàn)快速檢索,從而實(shí)現(xiàn)提升Philips指紋檢索系統(tǒng)的實(shí)用性。

3 實(shí)驗(yàn)結(jié)果與分析

本文通過實(shí)驗(yàn)評(píng)估改進(jìn)算法性能。實(shí)驗(yàn)設(shè)計(jì)從3個(gè)方面進(jìn)行評(píng)估:查詢精度,查詢速度和空間利用率,并與Philips研究做比較分析。

實(shí)驗(yàn)通用參數(shù)配置如下:

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

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

3)實(shí)驗(yàn)算法參數(shù)設(shè)置,幀長(zhǎng)0.37 frame/s;指紋塊長(zhǎng)度為256,大約3 s;相似閾值0.35。

3.1 查詢精度的評(píng)估

為了評(píng)估查詢精度,從某音樂網(wǎng)站下載免費(fèi)音樂片段用于查詢,實(shí)驗(yàn)分2組觀察:

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

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

3)服務(wù)器配置,32 GB內(nèi)存,可用內(nèi)存20 GB左右。

共選擇100首歌曲用于評(píng)估,評(píng)估的數(shù)據(jù)結(jié)果如表2所示。

表2 查詢精度 %

從表2結(jié)果可以看出,2種方面查詢精度相同。事實(shí)上,2種查詢的原理完全一樣,從設(shè)計(jì)理論上也可以驗(yàn)證。從分享結(jié)果可知,改進(jìn)的方法可以實(shí)現(xiàn)相同的精度,為后面的實(shí)驗(yàn)提供基礎(chǔ)。

3.2 查詢速度的評(píng)估

本文改進(jìn)的算法目標(biāo)是優(yōu)化Philips內(nèi)存使用,所以查詢速度,主要觀察普通PC下,改進(jìn)算法的查詢速度。

實(shí)驗(yàn)設(shè)置:

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

2)PC配置:4 GB內(nèi)存,可用內(nèi)存1.6 GB。

最后,實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 評(píng)估查詢效率

從圖6可以看出,隨著音樂數(shù)量的增加,查詢速度一直在0.97 s附件波動(dòng),相對(duì)比較平穩(wěn)變化。查詢速度平穩(wěn)的變化主要原因是由斐波那契數(shù)列優(yōu)化效果。此外,針對(duì)查詢效率,本文提出一個(gè)優(yōu)化策略,構(gòu)造2個(gè)哈希表,指針表存儲(chǔ)索引表偏移信息;索引表存儲(chǔ)真實(shí)指紋的位置信息。通過指針表可以快速訪問索引表文件,定位真實(shí)指紋位置信息。索引表文件的優(yōu)點(diǎn)是可以實(shí)現(xiàn)海量數(shù)據(jù)的快速訪問。

3.3 空間利用率的評(píng)估

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

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

(6)

其中,UN代表已經(jīng)占用的空間,L代表哈希表的總空間。實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 空間利用率

從圖7可以看出,提出的算法空間利用率顯著優(yōu)于Philips方法,即哈希值呈現(xiàn)良好的分布?？梢?基于構(gòu)造哈希函數(shù)和哈希表,實(shí)現(xiàn)了哈希值的較好分布,空間利用率得到提升。

4 結(jié)束語(yǔ)

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

[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] 牛憲華,曾柏森,陳思利.基于頻域和時(shí)域差分的音頻指紋算法研究[J].西華大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,33(5):10-15.

[4] 孟建華,陳 寧.基于Gammachirp耳蝸能量譜特征提取的音頻指紋算法[J].華東理工大學(xué)學(xué)報(bào)(自然科學(xué)版),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] 明建成,韓 威.基于音頻指紋的壓縮域音頻識(shí)別方法研究[J].西華大學(xué)學(xué)報(bào)(自然科學(xué)版),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.