# A Novel Tempogram Generating Algorithm Based on Matching Pursuit
## 2 Related Work  
Generally, there are two steps to generate the tempogram. The first step concerns onset detection, in which the musical signal is processed and the output is the novelty curve [8], which is the frame-to-frame difference and roughly describes the temporal context of onsets. To obtain the novelty curve, the musical signal is preprocessed firstly by separating the signal into multiple frequency bands, transient/steady state separation, etc. [14], and then predefined signal features, such as temporal features and spectral features [15; 16; 17], are extracted. Probabilistic methods [18; 19; 20] can also be employed to generate the novelty curve.  
In the second step, periodicities or tempi are derived from the novelty curve, and the tempogram is created based on tempi at all of the musical proceeding time finally. In this paper, we focus on the second step, generating the tempogram, in which extracting periodicity from the novelty curve is the key procedure essentially. There are two main methods in this step [8], autocorrelation function (ACF) and Fourier transform (FT). Besides these two methods, [PERSON] reviewed some other methods that could implicitly be used to generate tempogram [21]. The approach of comb filtering [22; 23] was proposed to estimate periodicity by [PERSON] and [PERSON], where the output energy of the filterbank of comb filter indicated resonance at a tempo period. An enhanced ACF approach, called beat histogram [24], was provided by [PERSON] to use for genre classification, and to estimate tempo in his later work [25]. Also, trying to improve upon traditional ACF, the autocorrelation phase matrix (APM) was introduced by [PERSON] [26], which was aiming at adding beat phase information to the traditional ACF. Unlike the ACF of a novelty curve, [PERSON] [27] proposed the beat spectrum approach to compute ACF over either the frames of rows or columns directly, in which melodic and harmonic patterns were declared to be retained. In addition, an enhanced FT approach was introduced by [PERSON] [28], where the phase information of STFT was added, aiming at beat alignment. It is worthwhile to note that there were some approaches whose ideas of matching template is similar to this paper. [PERSON] [29] introduced the approach of matching the energy flux function, which is a type of novelty curve with a set of metrical templates to derive tempo information, in which he constructed the metrical templates on the assumption of the duple meter. [PERSON] [30] used a similar template matching approach, but with no metrical information, to determine the initial beat phase hypotheses. [PERSON] [31] also proposed the beat template matching method in their beat and downbeat tracking system, however, they learned templates from data with annotated beat times using linear discriminant analysis (LDA), rather than hard-coded templates. [PERSON] [32] generated templates by the generalized autocorrelation function (GACF), and then employed k-Nearest Neighbor (k-NN) regression to find the matches to periodicity vectors with annotated tempi.  
In this paper, we prominently introduce the two main approaches that were explicitly proposed for tempogram generation and also practically used for many research fields of MIR, and we use them for comparison in experiments as well. The ideas of the other approaches that are mentioned above can implicitly be adopted to tempogram generation, but they all were not designed for tempogram explicitly, most of which were used only for beat tracking, and needed to be modified or expanded if being used for tempogram generation.