Paper reading - beat tracking by dynamic programming

1 summary

When splicing short videos with background music , If the splicing point of the two videos happens to be on a beat point of the background music , So the composite video looks , Sound , Very comfortable , This is a bonus item for short video synthesis , This kind of video is what we often call "stuck video" . The premise of making a video clip is to find a point in the background music that can be stuck ,beats It is one of the points that can be stuck , This article is to use the vernacular to talk about the thesis Beat Tracking by Dynamic Programming How to find it beats Of . Common audio signal processing library librosa Medium librosa.beat.beat_track That's how it works . The name of this task is beat tracking, This will be called in the following paragraphs .

2 General framework

The paper introduces beat tracking It can be divided into three steps ：

（1） Calculation Onset Strength Envelope（Onset Energy envelope of ）

（2） Calculate the global Tempo

（3） Based on dynamic programming beats

I saw these three steps for the first time , It's also confused , If it's someone who specializes in signal processing , You may already know what happened , But the target audience of this article is like me , A little friend who has learned or understood signal processing but has forgotten about it . therefore , These three steps will be analyzed in detail below .

If you just want to know how to use it ,librosa Everything has been packed for us , Three lines of code .

import librosa

y, sr = librosa.load(“your/music/file/path”)
tempo, beats = librosa.beat.beat_track(y=y, sr=sr)

3. Calculation Onset Strength Envelope

onset It refers to the starting point of a note , For example, the moment you press the piano key , Another example is the moment when the strings are plucked , The picture below shows onset The location of . In this part , Is to put all of the onset Find out the energy envelope of . The audio given may be a drum track , Piano tracks , The violin track , A mix of vocal tracks, etc . No matter which track , Will be found by us .

chart 1：onset Sketch Map

look for onset The method of energy envelope is not proposed in this paper , Using an existing common method , be called crude perceptual model. The steps are as follows ：

（1） use 8kHz Read audio files at the sampling rate of .

（2） use 32ms Of window_size and 4ms Of step_size, Short time Fourier transform (STFT), Get the picture 2 The top picture in .

（3） Map the spectrum onto the Mel spectrum , The vertical axis is divided into 40 individual bands, Get the picture 2 Figure in the middle of .

（4） Along the timeline for each band First order difference , And set all negative values to 0, And then put all of them at each time point band The positive value after the difference is accumulated .

（5） Yes （4） High pass filtering is performed on the results obtained in , To filter out 0.4kHz The following information , Make its local zero mean , Reuse window_size by 20ms Gaussian window for smoothing , Get the picture 2 The bottom figure in , That is to say onset strength envelope, Write it down as $O(t)$.

chart 2： spectrum , Mel spectrum and onset strength envelope Comparison of the figure

$O(t)$ The local peaks in the are where the energy increases abruptly , Why does the energy change dramatically ？ Of course it's because a new note sounds . Be careful , I don't think the crest here is onsets The exact time , It is onsets The time of the wave crest produced . But different articles seem to refer to this onsets The candidate for . But we don't care onsets Where exactly , As long as there is $O(t)$ That's enough , So don't worry about the definition .

The other one is , I wonder why the author of the paper should use （5） Such normalization , That's what we got $O(t)$ There will be many negative values , But we don't want these negative values .Tempo and Beat Tracking I think the normalization method in is more reasonable , Direct subtraction local average, That's all right. . The figure below 3 The top red line in is local average, The result obtained after subtraction is figure 3 The picture in the middle , chart 3 The icons below show local peaks and onsets.

chart 3：onset strength envelope normalization

4 Calculate the global Tempo

Tempo It refers to the beat of music , Usually use bpm(beats per minute) To measure , such as 120bpm It means one minute 120 individual beats, The period of the beat is 0.5s. In this paper, we use the period of the beat to express Tempo. A musical Tempo It may change over time , But it's rare , We only discuss the whole audio here tempo Are consistent . Changing Tempo Inspection can be found in predominant local pulse, The general idea is to segment , It's not discussed here .

The beat is a tune that keeps cycling , We have to find out the period of this cycle . Autocorrelation function is suitable for finding period , We calculate different delay times $O(t)$ The value of the autocorrelation function of , The highest value corresponds to a delay time beat The length of .

But there is a problem , Pictured 4 Of raw autocorrelation Shown , The value of autocorrelation function of periodic function on the multiple of its base period is very large . To solve this problem , This paper introduces a weight coefficient , Make the periodic result tend to a certain empirical value . The formula for calculating the autocorrelation coefficient is

$$TPS(\tau )=W(\tau )\sum _{t}O(t)O(t-\tau )$$

among ,$\tau$ Is the delay time ,TPS by Tempo Period Strength Abbreviation , It is the name given to this autocorrelation calculation method in this paper , bring $TPS(\tau )$ The biggest one $\tau$, That's the cycle we're looking for .

$W(\tau )$ Is a Gaussian weight coefficient , Expressed as

$$W(\tau )=exp\{-\frac{1}{2}(\frac{lo{g}_2\tau /{\tau }_0}{{\sigma }_{\tau }}{)}^2\}$$

among ,${\tau }_0$ Is the default biased cycle size ,${\sigma }_{\tau }$ Is a coefficient indicating the degree of bias .${\tau }_0$ and ${\sigma }_{\tau }$ All experience values , The paper starts from MIREX-06 Beat Tracking From the centralized statistics of training . The statistical method is to fill in different ${\tau }_0$ and ${\sigma }_{\tau }$, bring $TPS(\tau )$ The maximum value obtained from and marked in the data Tempo The group with the highest consistency ${\tau }_0$ and ${\sigma }_{\tau }$ Is it .

The final result is ${\tau }_0$ by 0.5s, That is to say 120bpm,${\sigma }_{\tau }$ by 1.4. Under this group of parameters $TPS(\tau )$ Pictured 4 As shown in the figure at the bottom of . In the picture Primary Tempo Period Is the final cycle .

chart 4：onset strength envelope, Primitive autocorrelation function and TPS Comparison of the figure

librosa.beat.beat_track One of the input parameters in is start_bpm, Refers to ${\tau }_0$, It can be modified manually , The default is 120.

In actual use , Would be right $TPS(\tau )$ Do some optimization , become

$$TPS2(\tau )=TPS(\tau )+0.5TPS(2\tau )+0.25TPS(2\tau -1)+0.25TPS(2\tau +1)$$

or

$$TPS3(\tau )=TPS(\tau )+0.33TPS(3\tau )+0.33TPS(3\tau -1)+0.33TPS(3\tau +1)$$

Either way ,$TPS(\tau )$ Corresponding to the peak of $\tau$ That's the cycle we're looking for .

5 Based on dynamic programming beats

The paper 4ms One step （250Hz） Divide the time into , Used the second 3 Section and section 4 The results of this section , The following objective function is designed ：
$$C(\{t_i\})=\sum _{i=1}^{N}O(t)+\alpha \sum _{i=2}^{N}F(t_i-t_{i-1},{\tau }_p)$$

among ,$\{t_i\}$ Found for $N$ individual beats;$O(t)$ That is the first. 3 Section Onset Strenghth Envelope;$\alpha$ Is the coefficient that balances the two objective terms ;${\tau }_p$ That is the first. 4 Period obtained in section ;$F(△t,{\tau }_p)$ Is used to measure every two adjacent beats Spacing and ${\tau }_p$ The gap between , This can be defined by itself , In the paper, it is expressed as

$$F(△t,{\tau }_p)=-(log\frac{△t}{{\tau }_p}{)}^2$$

Visible when $△t$ and ${\tau }_p$ The closer the ,$F(△t,{\tau }_p)$ The bigger it is , The maximum is 0, Otherwise, the smaller . besides , The formula is log symmetrical , such as $F(k{\tau }_p,{\tau }_p)=F({\tau }_p/k,{\tau }_p)$.

Our goal is to make $C(\{t_i\})$ The bigger the better , Look at the , When $\alpha =0$ when , Select all the time points ,$C(\{t_i\})$ It's the biggest ; When $\alpha =+\infty$ when , Select a time interval of ${\tau }_p$ A set of points can make $C(\{t_i\})$ The biggest . It's not hard to see. , With $\alpha$ Balance , The resulting column of points is spaced at ${\tau }_p$ Fine tuning left and right , And make the point fall $O(t)$ A group of points near a local peak .

This paper uses the method of dynamic programming , With linear time complexity , That solved the problem . First defined $C^{\ast }(t)$, It means that only the time point not greater than the time is considered $t$ when , In time $t$ For one beat Of $C(\{t_i\})$ The maximum of , This is the state transition function in dynamic programming , The expression is ：

$$C^{\ast }(t)=O(t)+\underset{\tau =0...t-4ms}{\max }\{\alpha F(t-\tau ,{\tau }_p)+C^{\ast }(\tau )\}$$

This is a little different from the standard dynamic programming , Have a good taste , I've been thinking about this place for a long time , This approach can avoid calculating state transitions , The previous best beats The sequence changes . This $C^{\ast }(t)$ One more benefit , It can be used to find the ending , When $C^{\ast }(t)$ When the increment of , It's just that the music gets weaker , That's the end .

meanwhile , It will also record what makes $C^{\ast }(t)$ The largest sequence is $t$ The previous one beat by

$$P^{\ast }(t)=arg\underset{\tau =0...t-4ms}{\max }\{\alpha F(t-\tau ,{\tau }_p)+C^{\ast }(\tau )\}$$

That is to say, take $\tau$ How much is the . adopt $P^{\ast }(t)$ Can backtrack the choice of beats route , To get the final beats Sequence .

In the actual search $\tau$ When , Not from 0 To t-4ms To do , This will calculate many unnecessary situations . Yes F The punishment is , We just search $\tau =t-2{\tau }_p...t-{\tau }_p/2$.

We will 0 To the total time , All the time $t$ Corresponding $C^{\ast }(t)$ After all the calculations , Take the largest one $C^{\ast }(t_N)$,$t_N$ It's the last one beat spot , then $t_{N-1}=P^{\ast }(t_N)$, Then the whole sequence is traced all the way back $\{t_i\}$. One thing is for sure ,$t_N$ Must be in $[totalwhenLong-{\tau }_p,totalwhenLong]$ Within the scope of , Or you can add another one beat.

At this point, the text has been finished . Let's talk about it briefly , Why not follow the standard dynamic planning approach , Otherwise, I may have to think about it for a long time next time . According to standard practice , Will define $C^{\ast }(t_j)$ The time point is not greater than the time $t_j$ when ,$C(\{t_i\})$ The maximum of . The state transition function is

$$C^{\ast }(t_j)=\max \{O(t_j)+\underset{\tau =0...t_{j-1}}{\max }\{\alpha F(t_j-P^{\ast }(\tau ),{\tau }_p)+C^{\ast }(\tau )\},C^{\ast }(t_{j-1})\}$$

Explain that , There are two options , The former one is to $t_j$ As a beat, The other is not to $t_j$ As a beat. That's the problem $P^{\ast }(\tau )$, When we put $t_j$ As a beat, bring $C^{\ast }(t_j)$ The previous one as big as possible beat Is not necessarily $P^{\ast }(\tau )$. In other words , hold $t_j$ As a beat after , The best in front beats May change . If we follow the standard practice , Many time points will be missed as beat The situation of . Fine products , Fine products .

6 reference

[1] Beat Tracking by Dynamic Programming
[2] Tempo and Beat Tracking