基于交叉递归图和局部匹配的翻唱歌曲识别

杨　帆,　陈　宁

(华东理工大学信息科学与工程学院,上海 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