基于交叉遞歸圖和局部匹配的翻唱歌曲識別

楊　帆,　陳　寧

(華東理工大學信息科學與工程學院,上海 200237)

基于交叉遞歸圖和局部匹配的翻唱歌曲識別

楊帆,陳寧

(華東理工大學信息科學與工程學院,上海 200237)

摘要：基于Qmax算法,提出了一種新的序列局部匹配算法,用于翻唱歌曲識別。該算法通過改變所使用的步長條件使得匹配過程既能防止病態彎曲又能增加局部匹配分數。為了驗證該算法在翻唱歌曲識別中的有效性,采用基于節拍同步的音級輪廓(PCP)特征作為測試對象,并利用最佳移位索引(OTI)實現基調不變性;根據所提取的特征構造交叉遞歸圖(CRP),利用提出的局部匹配算法計算序列之間的相似度。實驗結果表明,該方法獲得了比傳統匹配算法,如動態時間規整(DTW)、互相關和Qmax算法更高的識別準確率。

關鍵詞：翻唱歌曲識別; 交叉遞歸圖; Qmax; 局部匹配

隨著信息技術的發展,音樂在互聯網上大量傳播,促進了基于內容的音樂信息檢索(Music Information Retrieval,MIR)技術的發展。翻唱歌曲識別(Cover Song Identification,CSI)作為MIR的一部分,在理論方面能為定義模糊、難以客觀量化的音樂相似性度量提供重要的依據和模型,為音樂認知的研究提供重要的數學模型[1],在實際應用中對音樂的版權保護和管理都有重要的意義。

翻唱歌曲是一個源自原始音樂的新的演唱、表演或重新錄音版本[2]。由于獲得翻唱歌曲方法的多樣化,如對原始歌曲進行混錄、不同歌手的再創作等,使得不同翻唱版本在音色、節拍速度、結構、基調等方面都可能存在巨大差異,造成了CSI面臨挑戰[1]。

現階段CSI研究主要集中在特征提取和相似性度量兩個方面。特征提取方面,多采用音級輪廓(Pitch Class Profile,PCP)或稱chroma特征[3]及其變種,如基于瞬時頻率的PCP(IF PCP)[4]和基于和聲的PCP(Harmonic PCP,HPCP)[5]。文獻[6]證明了PCP特征具有對噪聲和非調性聲音的魯棒性,以及與音色、力度無關等優點。相似性度量方面,Gomez等[7]采用動態時間規整(Dynamic Time Warping,DTW)進行全局匹配,該方法能夠自動尋找發現不同長度序列的最優匹配路徑,但可能會產生病態彎曲。Ellis等[4]計算兩首歌曲PCP特征序列的互相關,取最大峰值作為相似度,但準確率較低。Serra等[8]通過構建二值相似矩陣,采用Smith-Waterman算法通過打分的方式計算兩個序列之間的局部相似度,證明了局部匹配算法在結果上明顯優于全局匹配算法。Serra等[9]在文獻[8]的基礎上,提出了使用交叉遞歸圖(Cross Recurrence Plot,CRP)來構建相似矩陣,并采用遞歸量化分析從CRP中提取Qmax作為相似性度量,其中,Qmax是兩條序列的匹配分數。但是,由于文獻[8-9]為了防止病態彎曲的產生,改變了遞歸量化分析時的步長條件,因此導致最終匹配分數的減小。Degani等[10]同時使用Qmax和DTW方法,將歸一化后的Qmax和DTW度量組成二維向量,作為新的相似性度量,證明了使用多種相似性度量結合的結果要優于使用單一的方法。

針對Qmax的不足,本文提出了一種新的局部匹配算法,命名為Dmax。通過改變Qmax在遞歸量化分析中使用的步長條件,在不產生病態彎曲的條件下,盡可能地提高最終匹配分數。對于構建CSI系統,采用基于節拍同步的IF PCP特征作為輸入,并利用最佳移位索引(Optimal Transposition Index,OTI)算法[8]進行基調變換,構建CRP并從中提取Dmax以進行局部匹配。在算法的評估階段,采用著名的“covers80”數據庫[11]作為測試對象,實驗結果證明本文算法比傳統的算法獲得了更高的準確度。就平均準確率均值(Mean of Average Precisions,MAP)[12]和TOP-1而言,該算法比Qmax算法分別提高了3.1%和5%。

1翻唱歌曲識別系統

1.1概述

CSI系統一般分為5個部分:特征提取、基調不變性、速度不變性、結構不變性和相似性計算[2]。特征提取和相似性計算為CSI的核心步驟,其余部分則可以有效地提高識別算法的準確率。如圖1所示,本文采用文獻[4]提出的IF PCP特征作為輸入,利用文獻[13]提出的算法對其進行節拍同步,以實現速度不變性;利用文獻[8]提出的OTI算法進行基調變換,以實現基調不變性;根據移位后的基于節拍的IF PCP特征構建CRP,通過遞歸量化分析,提取同步Dmax,完成兩首歌曲間的相似性計算。

圖1　翻唱歌曲識別系統總框圖

1.2基于節拍同步的IF PCP特征提取

PCP作為一種中層特征,充分保留了歌曲的旋律信息。IF PCP通過使用瞬時頻率,而非使用傅里葉變換后的頻率進行頻譜映射,有效地解決了傅里葉變換帶來的頻譜模糊問題[4]。根據求得的頻譜,將每一幀的能量壓縮到與8度無關的12個半音上,頻譜映射公式

(1)

其中:fref為參考頻率,可取鋼琴上的標準A所對應的440 Hz;fs(k)對應頻譜中第k個分量的頻率;round為四舍五入;mod為取模運算,在fs(k)

(2)

式中:X(k)為頻譜幅度;hp,n為第n幀PCP特征在音級p上的強度。

本文采用文獻[13]中的節拍跟蹤算法,該方法將短時傅里葉變換(Short Time Fourier Transform,STFT)后得到的頻譜轉化為40維的Mel頻譜,沿時間軸進行一維差分后沿頻率軸相加,通過0.4 Hz的高通截斷濾波器獲得起始能量包絡,并對其進行自相關,在對數域上加高斯窗,以最大滯后值對應的時間估計節拍速度。以起始能量包絡和節拍速度作為輸入,采用動態規劃獲得節拍位置。

通過節拍信息對IF PCP特征進行分段,得到基于節拍同步的IF PCP特征:

(3)

其中:M為一個節拍內PCP特征的幀數;hn={hp,n}為第n幀的PCP矢量;ki為第i拍的起始點幀位置；xi為第i拍的PCP矢量,i=1，…，Nx。

1.3最佳移位索引

OTI算法[8]是一個簡單的獲得基調不變性的方法,通過分別對歌曲A、B的PCP特征進行平均運算來獲得它們的全局PCP,記為xgl和ygl,通過式(4)獲得

(4)

其中:N為PCP的維數;circshiftR代表了向右的循環移位，且id為循環移位的位數。此時可將歌曲B的PCP特征變換到與歌曲A相同的基調上。

(5)

1.4序列的局部相似性計算

1.4.1交叉遞歸圖對基于節拍同步的PCP特征進行相空間重構是繪制交叉遞歸圖的第一步。令歌曲A的PCP特征矢量為x={xp,i},重構后為a={ai},其中

(6)

式中:i=1，…，Nx-(m-1)τ;m為插入的維數;τ為延時。

(7)

1.4.2Dmax提取采用不同的步長條件對Qmax算法進行改進,使用遞歸量化分析提取新的相似性度量Dmax進行局部匹配。

提取Dmax過程可以看作是對兩個序列進行比對打分的過程。根據所提取的CRP,可以構建相應的打分矩陣,將之記為D,該矩陣的大小為[Nx-(m-1)τ]×[Ny-(m-1)τ]。Dmax為矩陣D中的最大值,代表兩個序列比對過程中的最優局部匹配所獲得的最大分數。

(8)

式中:i=4，…，Nx-(m-1)τ;j=4，…，Ny-(m-1)τ;γ(z)為懲罰函數,

(9)

式中：γo為起始空位罰分項;γe則為延伸空位罰分項。

在創作翻唱版本的過程中,常常會有增減和弦或改變和弦的現象,從而使得歌曲的音調進程發生改變,造成序列比對過程中本應匹配的位置會出現空位或不匹配[9]。如果在構建打分矩陣的過程中,不采用罰分處理,而是在CRP中為0的點處直接將D中相對應的點進行0分化,可能會造成一個十分相似的片段,只因幾個不匹配的點而出現中間截斷的現象,減小最終匹配分數。通過罰分的方式,可以去除這種截斷現象,從而應對在創作翻唱歌曲過程中可能出現的和弦變化。

從式(8)中可以看出,算法通過將打分矩陣D中可能出現的負分變為0,使之成為一種局部匹配算法,每個成為0的點都可以作為一個新的局部匹配片段的起點,用來對抗創作翻唱版本時可能出現的歌曲結構改變。與原始歌曲相比翻唱歌曲,一般存在片段的插入或刪減,或改變片段出現的順序,造成歌曲的結構發生變化,從而引起兩首歌曲的相似路徑可能并非為CRP中的主對角線,因此在翻唱歌曲識別時采用局部匹配比采用全局匹配更加具有優勢。

獲得打分矩陣D后,從中提取Dmax,即矩陣D中的最大值,

Dmax=max(Di,j)

(10)

式中:i=1，…，Nx-(m-1)τ;j=1，…，Ny-(m-1)τ。

圖2示出了打分矩陣D的示意圖,其中圖2(a)為兩首翻唱歌曲的打分矩陣,地下絲絨樂隊的《AllTomorrow′sParties》作為橫軸,Japan樂隊的《AllTomorrow′sParties》作為縱軸,最終Dmax得分為577;圖2(b)所示為兩首非翻唱歌曲的打分矩陣,BrianWilson的《Caroline,No》作為橫軸,RobertPalmer的 《AddictedtoLove》作為縱軸,最終Dmax得分為108,兩者參數均為γo=1,γe=1.5。圖中黑色曲線為局部最優匹配路徑,是指在遞歸量化分析時,獲得局部最大分數時所經過的路徑,終點為最大分數在打分矩陣中的位置,起點則為兩條序列在這個局部匹配片段中的第1個匹配點。從圖中可以清晰地發現,兩首翻唱歌曲存在一個十分相似的片段。時間軸以節拍(beat)為單位。

圖2　翻唱歌曲與非翻唱歌曲打分矩陣比較

為了便于觀察Dmax和Qmax的不同,給出Qmax的計算公式如下：

(11)

式中Qmax為矩陣Q中的最大值。

從式(11)可以看出,Qmax采用的步長條件為pl+1-pl∈{[1,1],[2,1],[1,2]},與Dmax所采用的步長條件有著明顯的不同,其中pl為最優局部匹配路徑上的第l個點,l=1、2、…、L-1,L為最優局部匹配路徑的長度。圖3給出了兩種不同步長條件的示意圖[15]。

圖3(a)所示為Qmax采用的步長條件,圖3(b)所示為Dmax采用的步長條件。使用不同的步長條件,在進行局部匹配時會產生不同的最優局部匹配路徑,造成最終得到的匹配分數產生差異。

圖3　兩種不同的步長條件

2實驗仿真結果與分析

2.1實驗仿真環境與數據庫

為了驗證算法在CSI系統中的有效性,采用著名的“covers80”數據庫對算法進行評估。該數據庫由Ellis提供,專門用于進行CSI任務。數據庫中含有80組不同風格的翻唱歌曲,其中有一組包含4首歌曲,兩組包含3首歌曲,其他均為2首,總計164首歌曲。該數據庫中的大多數翻唱歌曲,無論是節奏、配樂、人聲還是基調等多個方面都存在明顯的差別,對算法的魯棒性來說是一個極大的考驗。歌曲均為MP3文件,采樣率均為16 kHz。在提供數據庫的同時,Ellis已經將歌曲分為兩組,一組含有80首原始歌曲作為查詢,從另一組80首翻唱歌曲中返回相似度列表,共使用160首歌曲。本文數據庫采用和Ellis一樣的設置,實驗環境采用MATLAB R2014a。

2.2評估度量選擇

為了有效地評估本文算法,選擇TOP-N和MAP度量作為評估標準。TOP-N是指將CSI的結果根據相似度從高到低排序后,返回的相似度列表中排名前N的歌曲中翻唱歌曲的個數。MAP度量是一種MIR領域的常規度量方法,并經常用于翻唱識別任務[1]。通過式(12)可得到MAP[12]。

(12)

式中Q代表識別過程中作為查詢的歌曲數目,本文中Q=80；AveP(q)為q歌曲作查詢時的平均準確率

(13)

式中:r為相似度列表中的名次;Cq為查詢歌曲q的翻唱版本數目,本實驗中Cq=1;N為識別結束后返回的歌曲數目,本文中N=80;Iq(r)代表當相似度列表在名次r處為查詢歌曲q的翻唱版本時,取值為1,否則取0;Pq(r)為在名次r處的精度,r=1,2,…,80。

(14)

2.3實驗結果與分析

在同樣的條件下,將本文算法在CSI中的結果與互相關算法[4]、DTW算法[15]及Qmax算法[9]的結果進行了比較。其中Qmax算法為翻唱歌曲識別領域識別準確率最高的算法之一。DTW算法分別采用了Sakoe-Chiba約束和Itakura平行四邊形約束兩種不同約束條件。對于Dmax和Qmax兩種算法,本文都對罰分項的參數選擇進行了大量的實驗,找到最適合本數據庫的罰分參數,使得兩種算法分別獲得各自的最優結果。其中Dmax的最優罰分參數為γo=1,γe=1.5,最終CSI結果如表1所示。

表1　不同匹配算法的翻唱歌曲識別結果

從實驗結果可以看出,與互相關算法、DTW算法這些全局匹配算法相比,局部匹配算法Qmax和Dmax都獲得了更高的識別準確率,證明了在CSI任務中使用局部匹配算法比使用全局匹配算法更加具有優勢。與Qmax算法相比,Dmax算法獲得了更高的識別準確率,TOP-1提高了5%,TOP-3提高了2.5%,MAP提高了3.2%。

Dmax算法與Qmax算法相比,采用了不同的步長條件。Qmax算法所采用的步長條件,雖然能解決在序列比對過程中最優局部匹配路徑可能會產生病態彎曲的問題,但是可能會錯過部分匹配點,同時由于該步長條件的局部約束邊界斜率較窄，減小了Qmax算法對特征長度差異的適應范圍，從而減小了最終匹配分數。所謂病態彎曲,是指在最優局部匹配路徑上,存在一條序列中的某一點與另一條序列中的眾多相鄰點匹配的現象,在打分矩陣示意圖中表現為最優局部匹配路徑某一段為橫線或豎線的現象。與Qmax算法相比,Dmax使用的步長條件,既能有效地防止病態彎曲的產生,又能盡可能少地錯過CRP中的匹配點,且由于Dmax算法步長條件的局部約束斜率寬于Dmax算法步長條件的局部約束斜率，擴大了Dmax對特征長度差異的適應范圍，從而提高了最終的匹配分數,造成了在CSI任務中使用Dmax算法比使用Qmax算法能獲得更高的識別準確率。

圖4示出了使用Dmax算法時能夠正確識別、而在使用Qmax算法時未能正確識別的翻唱歌曲打分矩陣示意圖,并給出了使用步長條件pl+1-pl∈{[1,1],[0,1],[1,0]}時的打分矩陣示意圖。其中圖4(a)為使用步長條件pl+1-pl∈{[1,1],[0,1],[1,0]}時的打分矩陣示意圖,圖4(b)為Dmax的打分矩陣示意圖,圖4(c)為Qmax的打分矩陣示意圖,三者參數均為r0=1，re=1.5，且3幅圖均以Tina Turner的《Addicted to Love》作為橫軸,Robert Palmer的《Addicted to Love》作為縱軸。這一對翻唱歌曲,雖然節奏相似,但存在一定的變調現象,并且在人聲上有著極大的不同,Tina版為女聲,Robert版為男聲,并因為Tina版為演唱會版,存在一定的背景雜音。圖中的黑線為局部最優匹配路徑。從圖4(a)中可以發現,它的局部最優匹配路徑上有一段明顯的病態彎曲,而在Qmax和Dmax的最優局部匹配路徑上都沒有這種現象發生。但是,在使用Qmax時,這兩首歌曲的最終局部匹配分數僅為79.5,未能正確識別,而在使用Dmax時,最終匹配分數為492,明顯高于使用Qmax時所得到的分數,并且正確識別。從圖4(b)中可以觀察到,使用Dmax算法時兩首翻唱歌曲的打分矩陣有一個明顯的相似片段,而在圖4(c)中卻沒有。實驗結果表明,與Qmax算法相比,Dmax算法對可能存在于翻唱版本之間的差異具有更強的魯棒性。

圖4　使用3種不同步長條件時的打分矩陣

3結束語

本文基于Qmax局部序列匹配算法,提出了一種該算法的變種:Dmax算法。與Qmax算法相比,Dmax采用了不同的步長條件,使得算法既能防止病態彎曲的產生又能提高最終匹配分數。基于“covers80”翻唱歌曲曲庫的實驗結果表明,Dmax在翻唱歌曲檢索任務中取得了比Qmax算法、DTW算法和互相關算法更高的識別準確率。但由于Dmax算法采用了CRP和遞歸量化分析,造成了算法運行速度較慢。在之后的研究中,我們將尋找方法來提高算法的運行速度,并繼續對算法進行改進,進一步提高算法在CSI任務中的準確率。

參考文獻：

[1]SERRA J,GOMEZ E,HERRERA P.Audio Cover Song Identification and Similarity:Background,Approaches,Evaluation,and Beyond[M].Berlin Heidelberg:Springer,2010.

[2]肖川,李偉,殷玥,等.多版本音樂識別技術研究綜述[J].小型微型計算機系統,2012,33(8):1841-1846.

[3]FUJISHIMA T.Realtime chord recognition of musical sound:A system using common lisp music[C]//Proceedings of the 1999 International Computer Music Conference.Beijing,China:ICMA,1999:464-467.

[4]ELLIS D P W,POLINER G E.Identifying ′cover songs′ with chroma features and dynamic programming beat tracking[C]//Proceedings of IEEE International Conference on Acoustics,Speech and Signal Processing 2007.Honolulu,Hawaii:IEEE,2007:1429-1432.

[5]GOMEZ E.Tonal description of music audio signals[D].Barcelona:Universitat Pompeu Fabra,2006.

[6]張秀,李念祖,李偉.Chroma特征的魯棒性驗證[J].計算機科學,2014,41(z1):24-28.

[7]GOMEZ E,HERRERA P.The song remains the same:identifying versions of the same piece using tonal descriptors[C]//Proceeding of 7th International Conference on Music Information Retrieval.Victoria,Canada:ISMIR,2006:180-185.

[8]SERRA J,GOMEZ E,HERRERA P,etal.Chroma binary similarity and local alignment applied to cover song identification[J].IEEE Transactions on Audio,Speech,and Language Processing,2008,16(6):1138-1151.

[9]SERRA J,SERRA X,ANDRZEJAK R G.Cross recurrence quantification for cover song identification[J].New Journal of Physics,2009,11(9):093017.

[10]DEGANI A,DALAI M,LEONARDI R,etal.A heuristic for distance fusion in cover song identification[C]//Proceedings of 14th International Workshop on Image Analysis for Multimedia Interactive Services.Paris:IEEE,2013:1-4.

[11]ELLIS D P W.The ‘covers80’ cover song data set[EB/OL].[2015-06-01].http://labrosa.ee.columbia.edu/projects/coversongs/covers80/.

[12]XIAO Chuan.Cover song identification using an enhanced chroma over a binary classifier based similarity measurement framework[C]//Proceedings of 2012 International Con-ference on Systems and Informatics.Yantai:IEEE,2012:2170-2176.

[13]ELLIS D P W.Beat tracking by dynamic programming[J].Journal of New Music Research,2007,36(1):51-60.

[14]王峰.美爾音級輪廓特征在音樂和弦識別算法中的應用研究[D].太原:太原理工大學,2010.

[15]MULLER M.Information Retrieval for Music and Motion[M].Berlin Heidelberg:Springer,2007.

Cover Song Identification Based on Cross Recurrence Plot and Local Alignment

YANG Fan,CHEN Ning

(School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

Abstract:In this paper,a new local alignment algorithm based on Qmax is proposed to identify the cover versions.By changing the step size condition,the proposed algorithm can prevent the generating of pathological warping and improve the final score of local alignment.To verify the effectiveness of the proposed algorithm in cover song identification,the beat-synchronous pitch class profile (PCP) feature is taken as test object and the optimal transposition index (OTI) is used to achieve the key invariance.According to the extracted features,the cross recurrence plot (CRP) is constructed and the similarity is computed.It is shown from the experimental results that the proposed algorithm can achieve higher identification accuracy than the traditional alignment algorithms,e.g.,dynamic time warping (DTW),cross-correlation and Qmax.

Key words:cover song identification; cross recurrence plot (CRP); Qmax; local alignment

收稿日期：2015-06-09

基金項目：國家自然科學基金(61271349)

作者簡介：楊帆(1991-),男,黑龍江人,碩士生,主要研究方向為音樂信息檢索。E-mail:yang8910fan@163.com 通信聯系人：陳寧,E-mail:chenning_750210@163.com

文章編號：1006-3080(2016)02-0247-07

DOI:10.14135/j.cnki.1006-3080.2016.02.015

中圖分類號：TP391

文獻標志碼：A