基于最大最小距离法的节拍跟踪

李 锵，何 凝，关 欣

（天津大学电子信息工程学院，天津　300072）

基于最大最小距离法的节拍跟踪

李 锵，何 凝，关 欣

（天津大学电子信息工程学院，天津300072）

将端点检测与聚类算法结合，提出一种基于最大最小距离法的节拍跟踪算法.首先，将音乐信号分解成多个频率互不重叠的子带进行频谱分析，分别利用半波整流，求和得到最终的端点强度曲线.其后，根据能量谱找到起始节拍点.最后，根据最大最小距离法并利用音乐速度与节拍的关系，对端点强度曲线峰值进行有效聚类，识别出节拍点.实验结果表明，该算法识别节拍点准确有效，4评估指标P-score、Cemgil、CMLc和AMLt分别达到57.355，10、38.705，37、17.152，40和47.259，12，与其他算法相比综合性能较好.

节拍跟踪；最大最小距离；端点检测；聚类

音乐速度与节拍是音乐的重要信息内容，是音乐信息检索领域的重要课题之一.节拍是驱动音乐进行和构成时间框架的稳定脉冲［1］，是一个时间间隔近似相等的与人们在听音乐时的拍手或跺脚过程一致的脉冲序列.

人在听音乐时常无意识地踮脚或拍手，而计算机对这种过程的模拟，称为节拍跟踪，旨在从音乐音频中提取音乐的节拍信息.Seppänen［2］将众多节拍跟踪算法分为5类：①基于规则的搜索模型，如Povel和Essens模型［3］，将重音分配给起始点，搜索最少反证的同步脉冲周期和相位；②多代理模型，如Dixon等［4］提出的从IOI（inter onset intervals）中计算和跟踪节拍；③多振动器模型，如Scheirer［5］采用滤波器组对音乐信号进行处理计算节拍及速度；④过程模型，如Smith等［6］模型，通过将信号进行连续小波分解变换计算节拍点；⑤统计模型，如Cemgil等［7］模型，以MIDI为输入，用线性动态系统计算节拍点.

大部分节拍跟踪模型由音符端点检测、端点强度曲线周期提取两部分组成.不论哪种模型，端点检测后的根本目的都是选取有效端点曲线的峰值，其本质上是极值点是否为节拍点的聚类问题.因此，本文从端点强度曲线峰值点聚类的角度提出了基于最大最小距离（max-min distance，MMD）法的节拍跟踪算法.

1　算法描述

乐曲是一系列音乐事件的组合，在音乐信号中，每个音乐事件都有一个波峰与之相对应，如图1所示，音乐节拍则隐藏在这些波峰当中［8］.

图1　音乐音频信号（节拍点标记为白色点）Fig.1 Music signal（beats marked as white）

本文提出的节拍跟踪算法由端点检测、起始节拍点检测、每分钟节拍数（beat per minute，BPM）特征值提取、基于最大最小距离法的峰值聚类组成.首先进行端点检测及起始节拍点检测，然后根据音乐速度与节拍的联系，基于最大最小距离法对峰值进行聚类，计算节拍点.系统框图如图2所示.

图2　基于最大最小距离法的节拍跟踪模型系统框图Fig.2 System chart of beat tracking model based on max-min distance means

1.1端点检测

端点检测在音乐信号处理中有举足轻重的作用，一般包括3部分：时频变换、检测函数生成及峰值检测［9］.端点检测是基于检测音乐信号中一个或多个特性突变的函数.

首先通过短时傅里叶变换，得音乐信号的频谱为

式中：K为每帧的采样点数；T为信号帧数；X（k，t）为第t帧的第k个采样点.实验时选用23，ms作为帧长.然后对频谱幅度|X|做对数运算，服从Y=lg（1+C X），常数C=1，000.其目的是调整信号动态范围，增强弱瞬态清晰度，尤其是高频区域的弱瞬态清晰度，符合音频强度的对数关系［10］.

为得到端点强度曲线，计算压缩频谱Y的离散导数为

在计算时，根据八度音与频率的关系和文献［5］中划分方法，将X的频带划分为互不重叠的5个子带.本文分为0～500、500～1，250、1，250～3，125、3，125～7，812.5和7，812.5～11，025，5个子带，每个子带包含1个八度的宽度.

利用半波整流分别去除5个子带的局部平均值，并去除负值，再对每个子带结果求和得到最终的端点强度曲线Δ，音乐信号中能量突变点与端点强度曲线中的峰值、时频图中能量突变处相对应，如图3所示，图3（c）时频图中颜色亮暗表示能量大小，能量越大颜色越亮.

1.2BPM特征值提取

自相关存在于任何有规律的周期结构中，音乐的周期性表现为节拍结构.通过计算音乐信号的自相关函数可确定非典型周期信号隐含的周期特征.节拍连续性表现为音乐的平均速度［11］，单位为BPM.利用端点强度曲线Δ（t）与延迟特性，提取音乐的平均速度，即BPM特征值.

基于人耳的听觉特性，对于BPM=120的旋律人们会更容易接受或喜欢［2］，根据这一特点，利用感知加权窗对原自相关曲线进行滤波，滤除与该值相差较大的峰值，选出更符合人类听觉系统的峰值作为节奏参考值.速度周期计算式为

式中W（τ）为高斯加权函数，且有

图3　时域音乐音频信号、端点强度曲线及时频图比较Fig.3 Comparison of charts of time domain music signal，onset strength curve and time frequency diagram

式中：τ为周期变量；0τ为节奏的周期偏差中心，0τ决定权重曲线的宽度（在八度意义上的）. 实验时，设定0τ=120，τσ=0.9，使TPS（τ）取得最大值的τ即为单位周期.

由于对节奏感知的不同，同一旋律的标记节奏有快慢之分.根据音乐片段的韵律结构，快节奏一般为慢节奏的2或3倍.考虑这一现象，选择（0.33，0.5，2，3）中变量乘以单位周期，改进音乐速度的算法为这里分别考虑2倍或3倍速度的节奏，用1/2或1/3的节奏作为相邻测量标准，计算两种估计的相对峰值得到两个相对权重.TPS2（τ）+TPS3（τ）取得最大值的τ，即为所求的音乐平均速度——BPM特征值.

1.3确定起始节拍点

在音乐信号的起始节拍点，能量通常会发生大幅度变化，因此，找出能量突变点，是确定起始节拍点的可靠依据.节拍具有周期性，起始节拍点的确定格外重要.音乐信号的BPM值通常在60～240之间，即时间间隔为0.25～1.00，s，只需1，s的片段，便可检测出1个节拍点.实验时选取检测片段为1～2，s.

音乐信号在10～30，ms的短时间范围内，可以看作是准稳态过程，即具有短时性.因此可以采用短时能量法确定起始节拍点.设时域信号为x（l）、加窗分帧处理后得到的信号为xn（m），则xn（m）满足

式中：n=0，T′，2T′，···，T′为帧移长度；N为帧长；w（m）为矩形窗，且有

设第n帧音乐信号xn（m）的短时能量En为

计算En时采用信号的平方，表明对高电平非常敏感.因此，本文利用衡量信号幅度值变化的函数，即短时平均幅度Mn取代En.Mn不会因取平方而造成较大差异，定义为

实验时，设定帧长N=12，ms，帧移长度T′= 4，ms，相邻帧存在66%的重叠.图4为音乐片段的能量曲线，曲线中突变最明显的点，即为起始节拍点B0.

1.4基于最大最小距离法的峰值选取

音乐的节拍点出现在端点强度曲线Δ峰值处的可能性较高，因此需要对峰值进行有目的的选取，这可以归结为峰值是否为节拍点的聚类问题.用节拍出现的时间点表示节拍点位置，相邻两个节拍点之间的时间间隔称为节拍间隔.用起始节拍点表示每个节拍点为

式中：Bi+1为第i+1个节拍点；Br为节拍间隔.

图4　1～2，s的音乐音频时域片段与能量谱Fig.4 Fragment of music and energy spectrum from the first to second seconds

定义｛Bn｝为理论节拍点序列，对端点检测峰值｛Peakn｝进行处理，计算每个峰值与距离其最近的理论节拍点的偏移量为

用最大最小距离法对｛offsetn｝进行聚类.最大最小距离聚类算法［12］以欧氏距离为基础，首先辨识最远的聚类中心，然后确定其他的聚类中心，直到没有新的中心产生，最后将待聚类数据按照最小距离的原则归入对应的分类.该算法可以解决K-means聚类问题在选取初始聚类中心时由于过于随机而导致聚类中心可能出现分布较为集中的情形，由此提高划分初始数据集的效率［13］.

由于本文提出的MMD算法仅需区分节拍点与非节拍点两类，为减少计算量，实验时以min｛ offsetn｝为初始聚类（候选节拍点）中心Z1，θ设置为更接近1的数.以图4所示音乐片段为例，说明最大最小距离聚类算法，步骤如下.

步骤1待聚类数据为｛offsetn｝，设定θ∈（0，1），min｛ offsetn｝为第1个聚类中心Z1，Sn中与min｛ offsetn｝距离最大的元素为第2个聚类中心Z2；

步骤 2分别计算｛offsetn｝中剩余元素xi到Z1、Z2的距离Di1、Di2，将其中较小的距离记为Di；

步骤3计算max（Di），若max（Di）＞θZ1-Z2，则xi为新的聚类中心；

步骤4重复上述处理，直到没有新的聚类中心产生；

步骤5不同于按照最小距离原则将所有元素归入距离最近的聚类中心，本文对此进行改进，仅当Di=Di2且Di＜50 ms 时，才会归入Z1类.基于人耳的听觉特性，在声音间隔超过1/15s≈66.67 ms，听觉系统才能分辨出是两种声音.由于提取错误或者音乐节奏的变化，端点强度曲线Δ的峰值可能在容差（50 ms）范围内没有峰值，将这样的峰值归入节拍集合，会产生较大误差.

图5为最大最小距离法选取聚类中心示意.对于同一标准节拍点，可能存在两个备选元素出现或没有备选元素，这里对Z1中的元素转换为对应峰值点后，进行如下处理：

（1） 若两峰值点之间的时间差小于50 ms× 2，则保留与理论节拍点距离最近的点为计算节拍点；

（2） 若理论节拍点没有峰值点与之对应，则该计算节拍点为Bi=Bi-1+Br；

经上述过程得到的｛Bn｝即为节拍点序列.

图5　最大最小距离法选取聚类中心示意Fig.5Schematic diagram of clustering center selection with max-min distance means

2　实验结果与分析

本文采用国际音乐信息检索评测比赛（MIREX）的节拍跟踪的测试数据库（practice data），共计20个曲风节奏各不相同的音乐片段.同时，每个音乐片段有39或40位专家对其节拍点进行了手工标记.

在评估标准方面，最基本的节拍跟踪评估是比较计算节拍序列与真实节拍序列的相似度.虽然已存在许多评估方法，但是目前尚未达成共识，因此没有统一标准.本文提出的MMD聚类算法以人工标注的节拍为标准节拍，采用文献［14］中提出的P-score、Cemgil、CMLc和AMLt 4个指标对算法的准确度进行评估.表1是MIREX2013节拍跟踪比赛采用的DAV Dataset、MAZ Dataset和MCK Dataset 3个数据库的平均数据（该数据源于MIREX2013节拍跟踪结果，目前为最新结果，可在MIREX官方网站查看原始数据），本文将其作为所提算法的对比数据.

表1　不同算法的评估指标数据对比Tab.1 Evaluation index comparison with different algorithms

P-score：通过计算标准节拍点的脉冲序列与待评估节拍点的脉冲序列之间有限的互相关的总数评估节拍的准确度.以标注节拍间隔中值的±20%为容差，计算节拍在容差范围内则认为是准确的.P-score是从2006年MIREX中加入节拍跟踪后沿用至今的评估指标，其算法如下：构建41个长度为25，s的脉冲序列（忽略音乐片段的前5，s），采样频率为100，Hz，其中40个在标准节拍点处有单位脉冲，每一个脉冲序列记为aS［n］，式中S表示该音乐片段的标签数（1～40），另一个序列在待评估节拍点处有单位脉冲，该序列记为y［ n］.通过一个极小的容差窗口W计算互相关函数aS［n］和y［ n］，平均40次实验结果，得到P-score为

式中：N′为脉冲序列aS［n］和y［ n］的长度；NP取aS［n］和y［ n］中最大的值，即

容差窗口W取标准节拍间隔的20%，其在MATLAB中表示为

本文提出的MMD算法的P-score结果如表1所示.需要指出，在文献［15］中提出对标准节拍点进行评估，所得P-score值在34～73之间，可见对于节拍点的选择有比较大的主观性，不同的人标准不同，这个问题在音乐领域可能有更合理的解释.

Cemgil：通过计算标准节拍点与待评估节拍点的时间误差评估节拍的准确度.用高斯误差函数来确定时间误差，待评估节拍越接近标准节拍，该评估指标值越高，结果如表1所示.Cemgil是4个指标中唯一没有容差的，因此只是单纯计算每个待评估节拍与标准节拍是否相同，不同则判为0.

CMLc：通过比对待评估节拍点与标准节拍点的连续相同的比例评估节拍的准确度.以当前标注节拍的±17.5%为容差，若待评估节拍在容差范围内则认为与标注节拍相同，当前节拍点的前一个节拍点也要符合上述条件，才认为是连续相同.结果如表1所示.

AMLt：与CMLc相似，但是条件更为宽泛，待评估节拍可以发生在弱拍处，也可以在标准节拍的2倍或1/2的位置.结果如表1所示.

与其他不同算法评估数据对比表明，本文提出的MMD聚类算法的P-score、Cemgil、CMLc和AMLt指标均居于前4位，不同指标从不同角度评估节拍跟踪算法，可以看出本文提出的MMD算法综合性能较稳定.对于不同类型和风格的音乐信号，无论是否包含鼓点，都能准确模拟人的听觉系统识别节拍.

从实验数据看来，SB5和SB6两种基于双向长短期记忆（BLSTM）递归神经网络的算法［16］的效果更好.BLSTM递归神经网络算法的节拍提取部分和本文提出的MMD算法类似，不同之处在于音乐速度的提取.BLSTM算法3次提取信号的幅度谱，并进行一阶差分计算.同时，神经网络算法还需要进行模型训练，运行时间较长.本文提出的MMD算法则不需要训练数据，对音乐信号仅进行一次端点检测，在运行时间和算法复杂度上均优于BLSTM递归神经网络算法.

3　结 语

本文提出的MMD聚类算法首先对音乐信号进行预处理，其后通过能量谱找到起始节拍，利用端点检测及音乐速度与节拍的关系，基于最大最小距离法对峰值聚类，识别出节拍点.通过P-Score、Cemgil、CMLc和AMLt 4项评估指标的对比可知，本文提出的MMD聚类算法有效准确.今后将继续对MMD聚类算法进行改进.一方面，由于人工标记的数据获取有一定难度，数据库歌曲数量有限，未来将增加实验数据的数量和质量，进一步检验此方法的可靠性.另一方面，通过与SB5和SB6两种算法的对比，本文提出的MMD聚类算法还可以在端点检测与BPM特征值提取部分进行改进，以达到更好的节拍识别效果.

［1］Sethares W A，Bañuelos D. Rhythm and Transforms［M］. Berlin：Springer，2007.

［2］Seppänen J. Computational Models of Musical Meter Recognition［D］. Finland：Department of Information Technology，Tampere University of Technology，2001.

［3］Povel D J，Essens P. Perception of temporal patterns［J］. Music Perception，1985，2（4）：411-440.

［4］Dixon S，Cambouropoulos E. Beat tracking with musical knowledge［C］// 14th European Conference on Artificial Intelligence （ECAI 2000）. Berlin，Germany，2000：626-630.

［5］Scheirer E D. Tempo and beat analysis of acoustic musical signals［J］. The Journal of the Acoustical Society of America，1998，103（1）：588-601.

［6］Smith L M，Honing H. Time-frequency representation of musical rhythm by continuous wavelets［J］. Journal of Mathematics and Music，2008，2（2）：81-97.

［7］Cemgil A T，Kappen B，Desain P，et al. On tempo tracking： Tempogram representation and Kalman filtering［J］. Journal of New Music Research，2000，29（4）：259-273.

［8］胡建建，曾培峰，唐莉萍，等. 基于高斯低通滤波的音乐节拍提取［J］. 东华大学学报：自然科学版，2011，37（1）：72-75.

Hu Jianjian，Zeng Peifeng，Tang Liping，et al. Music beat extraction based on low pass Gaussian filter［J］. Journal of Donghua University：Natural Science，2011，37（1）：72-75 （in Chinese）.

［9］Bello J P，Daudet L，Abdallah S，et al. A tutorial on onset detection in music signals［J］. IEEE Transactions on Speech and Audio Processing，2005，13（5）：1035-1047.

［10］Grosche P，Müller M. A mid-level representation for capturing dominant tempo and pulse information in music recordings［C］//10th International Society for Information Retrieval（ISMIR 2009）. Kobe，Japan，2009：189-194.

［11］陈 哲，许洁萍. 基于内容的音乐节拍跟踪［J］. 电子学报，2009，37（B04）：156-160.

Chen Zhe，Xu Jieping. Content based music beat tracking［J］. Acta Electronica Sinica，2009，37（B04）：156-160 （in Chinese） .

［12］李金宗. 模式识别导论［M］. 北京：高等教育出版社，1994.

Li Jinzong. Guide of Pattern Recognition［ M］. Beijing：Higher Education Press，1994 （in Chinese）.

［13］吕 佳. 基于最大最小距离和动态隧道的聚类算法［J］. 计算机工程与设计，2010 （8）：1775-1778.

Lü Jia. Clustering algorithm based on max-min distance and dynamic tunneling ［J］. Computer Engineering and Design，2010 （8）：1775-1778 （in Chinese）.

［14］Davies M E P，Degara N，Plumbley M D. Measuring the performance of beat tracking algorithms using a beat error histogram［J］. Signal Processing Letters，IEEE，2011，18（3）：157-160.

［15］Dixon S. Evaluation of the audio beat tracking system beatroot［J］. Journal of New Music Research，2007，36（1）：39-50.

［16］Böck S，Schedl M. Enhanced beat tracking with contextaware neural networks［C］//Proc of the 14th International Conference on Digital Audio Effects （DAFx-11）. Paris，France，2011：DAFx-135-DAFx-139.

（责任编辑：孙立华）

Beat Tracking Based on Max-Min Distance Means

Li Qiang，He Ning，Guan Xin
（School of Electronic Information Engineering，Tianjin University，Tianjin 300072，China）

In this paper，combining onset detection and clustering algorithm，a novel beat tracking algorithm based on max-min distance（MMD） means was proposed. First，the spectrum of music signal was decomposed into several non-overlapping sub-bands. Second，by utilizing the half-wave rectifier on these sub-bands respectively，the final onset strength curve was found. Then，the first beat was discovered based on the energy spectrum of the starting point. Finally，based on MMD means，the beats of the music signal were identified according to the relationship between music tempo and beat，together with effective clustering of curve peaks of onset strength. Experimental results proved that the proposed algorithm can track beats accurately. The four evaluation indicators of the algorithm P-score，Cemgil，CMLc and AMLt，reached 57.355，10，38.705，37，17.152，40 and 47.259，12，respectively. Compared with other algorithms，the proposed algorithm possesses better comprehensive performance.

beat tracking；max-min distance（MMD）；onset detection；clustering

TP18

A

0493-2137（2015）12-1105-06

10.11784/tdxbz201406031

2014-06-11；

2014-07-30.

国家自然科学基金资助项目（60802049，61101225，61471263）；天津大学自主创新基金资助项目（60302015）.

李 锵（1974—），男，博士，教授，liqiang@tju.edu.cn.

关 欣，guanxin@tju.edu.cn.

网络出版时间：2014-10-10. 网络出版地址：http://www.cnki.net/kcms/doi/10.11784/tdxbz201406031.html.