CN107622774B - A kind of music-tempo spectrogram generation method based on match tracing - Google Patents

Abstract

The invention provides a method for generating a music velocity spectrogram based on matching and tracking, and relates to the field of content-based music information retrieval. The method includes the following steps: inputting a music signal, generating a note start point detection function o(n) and dividing it into frames ; Take the common music speed range and convert it into a frequency set; for each frequency in the frequency set, create a corresponding parent atom; perform a shift operation on the parent atom, and generate a new atom every time it is moved; combine all parent atoms and new atoms Assemble into a redundant dictionary; use the dictionary to perform matching and tracking on each frame of o(n), get the decomposition coefficient of each music speed, and finally generate the music speed spectrum of the music. The music velocity spectrogram generated by the present invention has the characteristics of high resolution and strong sparsity, and can flexibly set the resolution of the music velocity, the displacement granularity of the parent atom and the number of matching and tracking cycles according to its own requirements, thereby generating different resolutions and Music tempo spectrograms at different sparsities.

Description

A music tempo spectrogram generation method based on matching pursuit

technical field

The invention relates to the field of content-based music information retrieval, in particular to a music tempo spectrogram generation method based on matching and pursuit.

Background technique

1. Related concepts and application fields of the present invention

The speed of music progress is the music tempo (tempo). In modern music, "beats per minute" (beats per minute, bpm for short) is usually used as a measure of speed, such as music tempo marks Indicates that the speed of the music is 120 quarter notes per minute, that is, the duration of each quarter note is 0.5 seconds, and the larger the bmp value, the faster the speed.

Music speed is closely related to the beat and rhythm of music, and is one of the important characteristics of music. In the field of music information retrieval, speed estimation refers to estimating the traveling speed of music based on music content, starting from files containing music signal waveforms in the form of mp3 and wav. Tempo estimation itself is a challenging and important topic, and it is also the basic work of research directions such as music beat perception, music rhythm recognition, music type recognition, and music structure analysis. For example, in the process of music beat perception, it is often necessary to estimate the music speed first, and then infer the beat type and beat structure according to the speed; for example, in music genre recognition, rhythm and speed can be used as a significant feature of the recognition genre.

The speed of the music is constantly changing during the progress of the music. One reason for the change is that when the music is created, it is required to change. Changes; Another reason is the error of performance or singing, this form of change is inevitable, and generally exists in all parts of music. Therefore, estimating the music tempo actually requires estimating the tempo values at each time point. Due to the phenomenon of legato and rest, the music speed is blurred and difficult to distinguish; at the same time, there are errors in the speed, so the speed at each time point can actually be regarded as a vector composed of multiple speed components. The tempo of a piece of music at each time point can be described by a tempogram. Applications such as music beat tracking, rhythm recognition, and genre recognition can use the music tempo spectrogram to extract useful information.

2. The existing generation technology and process of music velocity spectrogram

The generation process of the music velocity spectrogram is generally divided into two stages. The first stage is the generation stage of the note onset detection function. The note onset refers to the moment when each note in the music begins to play or sing. In literature such as [1], this stage is called Novelty Curve generation; the second stage is the spectrum generation process.

The first stage mainly includes several parts such as signal transformation, feature extraction, and start point detection function generation. The purpose of signal transformation is to convert the music waveform signal from one-dimensional high-frequency data to low-frequency representation by means of signal transformation. Generally, the signal is divided into frames first, and then signal transformation is performed on each frame signal. The signal transformation methods include Short Time Fourier Transform (STFT for short), Wavelet Transform (WT for short), etc. Feature extraction is to extract features such as time domain, frequency domain, and time-frequency representation from the low-frequency representation of the signal in the previous stage. Typical time-domain features are amplitude envelope features, frequency-domain features such as spectral fluctuation features (Spectral Flux) and frequency-domain energy features, and time-frequency representation features are mainly based on wavelet transform or Cohen-like time-frequency distribution feature representation. The starting point detection function generation is to calculate the changes of the front and back frames based on the features extracted from each frame signal. The starting point of the note generally exists in the case of a sudden increase in the positive changes of the front and back frames. The typical note onset detection function generation process can refer to [1].

The second stage is to extract the periodic characteristics according to the value of the note start point detection function in the previous stage to form a music velocity spectrogram. Currently, the main methods at this stage include Autocorrelation Function (ACF for short) and Fourier Transform (FT for short) [1].

ACF is through windowing the note onset detection function and performing autocorrelation calculations, extracting the periodicity of the note onset according to the delay, and converting the delay into a music velocity measure to form a music velocity spectrogram. Its calculation formula is [1]:

A(t,l)=∑ _n∈Z o(n)o(n+l)W(nt)/(2N+1-l) (1.1)

Where t, n are discrete time, l=1...N is the delay, o(n) is the note start point detection function, W(n) is the center point is t=0, and the support is [-N,N] rectangular window. Let f _s be the sampling frequency of o(n), then the period corresponding to the delay l is l/f _s , the frequency is f _s /l, and the corresponding music speed τ=60*f _s /l.

The FT method is to perform windowed Fourier transform on the note onset detection function to obtain the frequency domain characteristics, and convert the frequency domain measurement into a music velocity measurement, thereby forming a music velocity spectrogram. Its calculation formula is:

F(t,ω)=∑ _n∈Z o(n)W(nt)e ^-2πiωn (1.2)

Among them, t and n are discrete time, ω is frequency, o(n) is a note starting point detection function, W(n) is a Hanning window whose center point is t=0, and support is [-N,N]. For ω, there are currently two ways to determine it. One is to discretize ω>0 into N frequency points with an interval of f _s /NHz according to the Discrete Fourier Transform (DFT) method of literature [2]. ; The other is similar to the practice of literature [1], taking ω=τ/60Hz, τ∈[30,480]bpm as the common music speed range, and using the above formula to calculate the coefficient corresponding to ω at each time point.

3. Insufficiency of existing technology

The achievement of the present invention is embodied in the second stage of music tempo spectrogram generation. In order to illustrate the deficiencies of the existing technology, two concepts of music velocity resolution and music velocity spectrogram sparsity are introduced and explained separately. The music velocity resolution, here refers to the frequency resolution in the field, expressed by the interval between two adjacent effective points of the velocity component in the music velocity spectrogram, the larger the interval, the worse the velocity resolution. The sparsity of the music velocity spectrogram refers to the number of non-zero elements in all spectrogram coefficients. The less the number of non-zero elements, the stronger the sparsity and the better the resolution.

1. The existing technology cannot meet the speed resolution requirements of commonly used music speeds

The music speed resolution and the interval between two adjacent effective points in the spectrogram change in the opposite direction. The larger the interval, the worse the resolution. Conversely, the smaller the interval, the better.

In the ACF method, the difference between the two points before and after the velocity component is This shows that the speed interval decreases as the delay increases, and the greater the delay, the higher the speed resolution, that is, the speed resolution increases as the speed increases. We take f _s =1/0.023=43.5 according to literature [1]. When l=51(τ=51.2), Δτ=0.98. When l<51, the speed resolution is less than 1. When l=21( τ=124.2), Δτ=5.6, at this time it is impossible to distinguish the speed of commonly used music (τ∈[30,480]), let alone the case of l<21. And to make the maximum value of Δτ (when n=1) less than 1, f _s needs to be less than 1/30, that is, the frame length of the first stage of framing must be greater than 30 seconds, then the error of the note starting point will also be greater than or equal to 30 seconds, which is obviously not feasible. Therefore, for ACF, the music speed resolution is not constant. When the music speed is greater than 51bpm, the resolution is lower than 1, which cannot meet the resolution of commonly used music speeds.

Investigate the DFT method in the literature [2], the speed interval is 60*f _s /Nbpm, calculated according to f _s =1/0.023=43.5, if the music speed resolution of 1bpm is to be achieved, N≥f _s *60=2610 , and the window duration of such a length is 60 seconds, most of the music is below 300 seconds at present, therefore, the window length requirement does not adapt to the general music length. To improve the speed resolution, another way is to reduce f _s , but this is in conflict with the accuracy requirement of o(n), so it is not feasible.

Consider the FT method in the literature [1]. This method actually calculates the coefficient of the frequency ω corresponding to the commonly used music speed by calculating the Discrete Time Fourier Transform (DTFT) method after adding a window to the music signal. In fact, this method only approximates ω at discrete points, and its actual frequency resolution has not been improved.

To sum up, the existing technology cannot meet the speed resolution requirements of commonly used music speed, that is, some areas of the generated music speed spectrogram will be blurred.

2. The music velocity spectrogram generated by the existing technology is not good enough

The stronger the sparsity of the music tempo spectrogram, the better its resolution. On the other hand, the strong sparsity of the spectrum shows that the energy of the spectrum is concentrated, the property is good, and the application effect is good.

For the ACF method, when the music speed exceeds 51bpm, its component coefficients are at normal precision (such as 1bpm), and the coefficients need to be calculated by interpolation method, which will inevitably lead to a decrease in sparsity. For the FT method, due to the existence of spectrum leakage and resolution problems, the sparsity of frequency domain coefficients will obviously also decrease. Therefore, the sparsity of the music velocity spectrogram generated by the prior art is not good enough, and the energy concentration is poor.

In summary, the music velocity spectrogram generated by the prior art has defects in resolution and sparsity, and the present invention can generate a music velocity spectrogram with higher resolution and better sparsity. The references used in this patent are as follows:

1.P.Grosche,M.Müller,F.Kurth.Cyclic tempogram—a mid-level temporepresentation for musicsignals[C]. in Acoustics Speech and Signal Processing(ICASSP),2010IEEE International Conference on.2010:IEEE.

2.G.Peeters.Time variable Tempo Detection and beat Marking[C].inICMC.2005.

3. MIREX. MIREX music test data set.

http://www.music-ir.org/evaluation/MIREX/data/2006/tempo/tempo_train_2006.zip.2017.

Contents of the invention

The object of the present invention is to provide a music tempo spectrogram generation method based on matching pursuit to overcome the insufficient resolution and sparsity of the music tempo spectrogram generated in the prior art.

In order to solve the problems of the technologies described above, the technical solution adopted in the present invention is:

1. Input a music signal to generate a note start point detection function o(n);

2. Framing o(n) to form several frame signals;

3. Take the commonly used music speed range, and convert the speed set into a frequency set according to a certain music speed resolution;

4. For each frequency in the frequency set, create a corresponding parent atom;

5. Perform a shift operation on all parent atoms at a certain granularity, generate an atom at each step, and combine the atoms generated by these shifts together with the parent atoms to form an atomic set of the frequency corresponding to the parent atom;

6. Assemble the atomic sets corresponding to all frequencies in the frequency set into a redundant dictionary;

7. For each frame signal of o(n), use the redundant dictionary to perform matching and tracking, and cycle for a certain number of times to generate a series of decomposition coefficients and corresponding atoms;

8. According to the relationship between the atom and the music speed in the redundant dictionary, assign the decomposition coefficient of each frame signal of o(n) to the coefficient of a certain music speed;

9. Merge the music velocity spectrum vectors of each frame signal to form a music velocity spectrum graph.

Beneficial effects of the present invention:

The present invention is characterized in that it generates a music speed spectrogram based on a redundant dictionary matching and tracking algorithm. The beneficial effect is the good resolution and sparse nature of the generated spectra.

The good resolution of the present invention benefits from the flexible setting of atoms in the redundant dictionary, which can generate higher-resolution atoms to form a redundant dictionary according to the resolution requirements of music speed, so that the resolution of the spectrogram is higher. Figure 2-Figure 4 is a piece of music (train1.wav) in the test data set [3] of the Music Information Retrieval Evaluation eXchange (MIREX) using the autocorrelation function method (Figure 2 ), Fourier transform method (Fig. 3), and the matching pursuit method (Fig. 4) of the present invention, the music velocity spectrogram that generates. The adjacent intervals of the music speed axis are 1bpm (571 points in total). From the resolution point of view, the autocorrelation function method in Figure 2 is acceptable in the low-speed part, but blurred in the high-speed part, and the band gradually widens. Resolution is significantly reduced. In Fig. 3 Fourier transform method, at high-speed and low-speed parts, strips are all wider, and the resolution is obviously not as good as the result of Fig. 4 of the present invention (for comparing with autocorrelation function method and Fourier transform method, the number of cycles is 571).

The excellent sparsity feature of the present invention benefits from the fact that the redundant dictionary provides highly similar atoms to the original signal, and the matching and tracking algorithm ensures that the decomposition coefficients of these highly similar atoms are relatively large, and the coefficients of dissimilar atoms are small or even zero. From the comparison of Figure 2-Figure 4, it can be seen that the coefficients in Figure 4 are significantly sparse, and the proportion of zero or near-zero coefficients is significantly larger.

The music tempo spectrogram generated by the invention not only has good resolution and sparseness, but also has application flexibility. The flexibility is reflected in the resolution of the music speed, the granularity of the displacement of the parent atom, and the adjustability of the cycle number of the matching pursuit. The adjustment of the velocity resolution can be carried out during the process of converting the common velocity range into the frequency set; the shift granularity of the parent atom can be set when generating the atomic set. The smaller the granularity, the larger the atomic set, the higher the accuracy of the spectrum, 8-10 are the three cases of shift granularity 50, 20, and 5 respectively. From the comparison results, it can be seen that the accuracy is getting higher and higher; the number of cycles is set in the matching pursuit algorithm. The larger the number of cycles, the more coefficients are generated, and the spectrum The denser the graph is, the order of the coefficients remains unchanged. Figures 5-7 show the three cases of cycle times 20, 10, and 5 respectively. Obviously, the coefficients of the spectrum are getting fewer and fewer, but the larger coefficients remain unchanged.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention or the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the drawings described below are only For some drawings of the embodiments of the present invention, those skilled in the art can also obtain other drawings based on these drawings without creative work.

Fig. 1 is the flow chart of music tempo spectrogram generation that the embodiment of the invention provides;

Fig. 2 is the music velocity spectrogram that adopts autocorrelation function method to generate;

Fig. 3 is the music velocity spectrogram that adopts Fourier transform method to generate;

Fig. 4 is that the present invention adopts the music tempo spectrogram (number of cycles is 571, and the displacement granularity is 2) that the method based on matching pursuit generates;

Fig. 5 is that the present invention adopts the music velocity spectrogram (number of cycles is 20, and the displacement granularity is 2) that the method based on matching pursuit generates;

Fig. 6 is that the present invention adopts the music tempo spectrogram (number of cycles is 10, and the displacement granularity is 2) that the method based on matching pursuit generates;

Fig. 7 is that the present invention adopts the music tempo spectrogram (number of cycles is 5, and the displacement granularity is 2) that the method based on matching pursuit generates;

Fig. 8 is that the present invention adopts the music tempo spectrogram (number of cycles is 20, and the displacement granularity is 50) that the method based on matching pursuit generates;

Fig. 9 is that the present invention adopts the music tempo spectrogram (number of cycles is 20, and the displacement granularity is 20) that the method based on matching pursuit generates;

Fig. 10 is the music tempo spectrogram generated by the method based on matching pursuit in the present invention (the number of cycles is 20, and the shift granularity is 5).

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some of the embodiments of the present invention, not all of them. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

The music velocity resolution, here refers to the frequency resolution in the field, expressed by the interval between two adjacent effective points of the velocity component in the music velocity spectrogram, the larger the interval, the worse the velocity resolution. The sparsity of the music velocity spectrogram refers to the number of non-zero elements in all spectrogram coefficients. The number of non-zero elements is small, and its sparsity is strong and the resolution is good. Embodiments of the present invention provide a method for generating a music velocity spectrogram based on matching and pursuit, as shown in Figure 1, the method includes:

1. Input the music signal and generate the note start point detection function o(n)

The input music signal is generally in the form of wav, mp3, etc., and contains waveform files. The first stage of music velocity spectrogram generation includes signal transformation, feature extraction, onset detection function generation and other processes, and the output length is N note onset detection function o(n), that is, a vector. This stage can be implemented with reference to literature [1].

2. Framing o(n) to form several frame signals

Carry out framing to o(n), preferably, the frame length of framing is 6 seconds (assuming that there are M points in the frame), and each hop (hopsize) is about 0.2 seconds, forming a hop size with M rows and N rows Detection function matrix X=X(m,n)m∈[1...M]n∈[1...N].

3. Take the commonly used music speed interval τ∈[30,480], τ∈R, and convert the speed set into a frequency set according to the music speed resolution requirements

In the prior art, the user cannot select the music tempo resolution to generate the required music tempo spectrogram, but the present invention can freely select the music tempo resolution, generate the corresponding redundant dictionary, and generate the corresponding music tempo spectrogram through the matching and tracking algorithm, This reflects the flexibility of the present invention to set the music speed resolution according to the application. The value of the music speed resolution of the present invention can be 1, 2... positive integer value and the same in all sub-intervals, or can be valued according to the value method of the autocorrelation function method or the Fourier transform method, and can even be divided into sub-intervals , and select values according to different music speed resolutions in each sub-interval. For example, in the most commonly used speed interval of music [80,150], the music speed resolution is set to 0.25, while other sub-intervals are set to 0.5. For the convenience of comparison, in the embodiment, the music speed resolution is set to 1 for the entire interval, so for τ∈[30,480], τ∈Z, it is converted into a frequency set set {f _b |f _b =τ/60,τ=[30 ,31,...480],b=[1..B]}, where b is the frequency sequence number in the corresponding frequency set, and B is the maximum value of the sequence number.

4. For each frequency in the frequency set, create a corresponding parent atom

Specifically, for the frequency set obtained in step 3, for each frequency f _b in the set, create the cosine function of the frequency as the corresponding parent atom α _b , whose length is the frame length M of o(n) , the form is: α _b ＝cos(2πf _b t), t=(0...M-1)/f _o , f _o is the sampling rate of o(n), and t represents time.

5. Perform a right shift operation on all parent atoms at a certain granularity, generate an atom at each step, and combine the atoms generated by these shifts together with the parent atom to form an atomic set of the frequency corresponding to the parent atom

The support domain of the parent atom α _b is [0, M-1], and the shift granularity d=1, 2, 3... is a positive integer, and the parent atom α _b is moved to the right by d*j bits (j=1 ,2,3...), after the parent atom α _b is shifted to the right, the value of the [0,Md*j-1] support domain on its left is cos(-2πf _b t),t=(Md*j... 1)/f _o is added, so that every time you move, you can get a new atom. Here the parent atom is a periodic function, therefore, the maximum number of moving digits is set to be no more than one period. All the parent atoms α _b and the displaced atoms constitute the atom set d _b corresponding to the parent atom.

The tunability of the parent atom translocation granularity in this step again reflects the flexibility of applying the present invention. The smaller the particle size, the larger the atomic set, and the higher the accuracy of the spectrogram, but at the same time, the calculation of the entire music velocity spectrogram takes more time. Figure 8-10 shows the three cases of shift granularity of 50, 20, and 5 respectively. From the comparison results, it can be seen that the accuracy of the spectrum is getting higher and higher. When the present invention is applied, the displacement granularity of the parent atom can be determined according to the calculation time-consuming requirement and the spectrogram accuracy requirement.

6. Assemble the atomic sets corresponding to all frequencies in the frequency set in step 5 into a redundant dictionary

Assemble the atomic set d _b corresponding to all frequencies f _b in the frequency set into a redundant dictionary D.

7. For each frame signal of o(n), use the redundant dictionary to perform matching and tracking, and cycle for a certain number of times to generate a series of decomposition coefficients and corresponding atoms:

For each frame signal of o(n), that is, for each column X _i , i∈[1..N] of the detection function matrix, use the redundant dictionary D to implement the matching pursuit algorithm:

(1) Set the remaining signal y _n =X _i , n=0, and start to execute the loop;

(2) Calculate the inner product <y _n , g _j > of all atoms g _j ∈ D of the redundant dictionary and the remaining signal y _n , and select the atom g _k corresponding to the largest absolute value of all inner products as the current cycle match Atom, save the decomposition coefficient s _n =|<y _n ,g _k >| and the corresponding atom g _n =g _k of the nth cycle;

(3) Recalculate the residual signal y _n+1 =y _n -|<y _n , g _k >|g _k ;

(4) If the number of cycles or the energy ratio of the remaining signal and the original signal meets the accuracy requirement, exit the cycle, otherwise set n=n+1, and continue to execute from step (2).

Preferably, the present invention generally terminates the cycle according to the number of cycles, and the number of cycles can be set according to the requirements of the music tempo spectrogram, such as K=10 times, 20 times...etc. After the loop is terminated, s _n , g _n , n=[1...K] are obtained.

The present invention provides atoms highly similar to the original signal based on the redundant dictionary generated by the commonly used music speed intervals, and the matching and tracking algorithm ensures that the decomposition coefficients of these highly similar atoms are relatively large, and the coefficients of dissimilar atoms are small or even zero, so that The music tempo spectrogram generated by the invention has more sparse characteristics. From the comparison of Figure 2-Figure 4, it can be seen that the coefficients in Figure 4 are significantly sparse, and the proportion of zero or near-zero coefficients is significantly larger.

The number of cycles of the matching pursuit algorithm is adjustable. The larger the number of cycles, the more coefficients will be generated and the denser the spectrogram (the size of the coefficients and the order of generation will remain unchanged), but the calculation time will increase with the increase of the number of cycles. Big and increase. Figures 5-7 show the three cases of cycle times 20, 10, and 5 respectively, and it is obvious that the coefficients of the spectrum are getting fewer and fewer. In some applications, a small number of large coefficients is enough to complete the task. At this time, the number of cycles can be set to a small value, and the required calculation time is less; while other applications require a large number of coefficients to provide sufficient information, just increase the number of cycles. . This also reflects the flexibility of the application of the present invention, and this is not available in the prior art.

8. According to the relationship between atoms and music speed in the redundant dictionary, assign the decomposition coefficient of each frame signal of o(n) to the coefficient of a certain music speed

For each frame signal, first create a music velocity spectrum vector S _n with an initial value of 0, n=[1..N], the serial number of each component is the music velocity serial number b, b=[1..B], each The value of the component is the decomposition factor of the tempo of the music. Then, for the decomposition coefficient s _n of each frame signal, find the corresponding music speed sequence number b according to the corresponding frequency of the atom g _n in the redundant dictionary, and use the decomposition coefficient s _n as the decomposition coefficient of the music speed. If there are multiple The atoms correspond to the same music tempo serial number, and then multiple decomposition coefficients are accumulated and summed, and then used as the decomposition coefficient of the music tempo.

9. Merge the music velocity spectrum vectors of each frame signal to form a music velocity spectrum

The music velocity spectrum vectors S _n of all frames are assembled and merged into a music velocity spectrum graph S=S(b,n), b=[1..B],n=[1...N].

The above is only an embodiment of the present invention, and does not limit the patent scope of the present invention. Any equivalent structure or equivalent process transformation made by using the description of the present invention and the contents of the accompanying drawings, or directly or indirectly used in other related technologies fields, are equally included in the scope of patent protection of the present invention.

Claims (2)

1. a kind of music-tempo spectrogram generation method based on match tracing, specifically comprises the following steps：

S1. music signal is inputted, note starting point detection function o (n) is generated；

S2. to o (n) framings, several frame signals are formed；

Framing is carried out to o (n), it is preferable that the frame length of framing is 6 seconds, if there is M point in frame, often jumps 0.2 second, then forms line number Detection function matrix X=X (m, n) m ∈ [1...M] the n ∈ [1...N] for being N for M, columns；

S3. take common music-tempo section τ ∈ [30,480], τ ∈ R that sets of speeds is converted by music-tempo resolution requirement At frequency sets:

Positive integer value that the value of music-tempo resolution ratio is 1,2 ..., and it is identical in all subintervals；Or press auto-correlation function The obtaining value method value of method or Fourier transform；Subinterval is either divided, and in each subinterval by different music speed Resolution ratio value is spent, when it is 1 that entire section, which takes music-tempo resolution ratio, then for τ ∈ [30,480], τ ∈ Z, Z expression are just Integer is converted into frequency sets { f_b|f_b=τ/60, τ=[30,31 ... 480], b=[1..B] } and, wherein b is corresponding frequency Frequency serial number in set, B are serial number maximum value；

S4. to each frequency in frequency sets, a corresponding parent is created:

For the frequency sets obtained in step S3, by each frequency f in the set_b, create the cosine function conduct of the frequency Corresponding parent α_b, the framing length M of the length of o (n), form is：α_b=cos (2 π f_bT), t=(0...M-1)/f_o,f_o For the sampling rate of o (n), t indicates the time；

S5. all parents are carried out by certain particle size moving to right bit manipulation, often moves one atom of generation that moves a step, these is moved The atom of generation forms the atom set of the corresponding frequency of the parent together with parent:

Parent α_bSupporting domain be [0, M-1], shift granularity d=1,2,3... be a positive integer, by parent α_bIt moves right It moves d*j (j=1,2,3...), parent α_bAfter moving to right, value cos (- 2 π f of the left side [0, M-d*j-1] supporting domain_bt),t =(M-d*j...1)/f_oSupplement, it is often mobile primary in this way, a new atom can be obtained；Parent is period letter herein Therefore number is arranged maximum mobile digit and is no more than a cycle；All parent α_bThe atom obtained with these displacements group together At the corresponding atom set d of the parent_b；

S6. being assembled into redundant dictionary by the corresponding atom set of all frequencies in frequency sets in step S5：

All frequency f in frequency sets_bCorresponding atom set d_b, it is assembled into a redundant dictionary D；

S7. match tracing is carried out with redundant dictionary to each frame signal of o (n), recycles certain number, generates a series of points Solve coefficient and corresponding atom：

To each frame signal of o (n), i.e., to each row X of detection function matrix_i, i ∈ [1..N], with redundant dictionary D, implementation Matching pursuit algorithm：

(1) residual signal y is set_n=X_i, n=0 starts to execute cycle；

(2) all atom g of computing redundancy dictionary_j∈ D and residual signal y_nInner product<y_n,g_j>, select in all inner products absolutely It is worth the corresponding atom g of the maximum_kFor this matched atom of cycle, the decomposition coefficient s of n-th cycle is preserved_n=|<y_n,g_k>| With corresponding atom g_n=g_k；

(3) residual signal y is recalculated_n+1=y_n-|<y_n,g_k>|g_k；

(4) if cycle-index or residual signal reach required precision with original signal energy ratio, cycle is exited, n=n+ is otherwise set 1, it is continued to execute since step (2)；

S8. the decomposition coefficient of each frame signal of o (n) is belonged to according to the relationship of atom in redundant dictionary and music-tempo The coefficient of a certain music-tempo：

To each frame signal, the music-tempo that an initial value is 0 is created first and composes vector S_n, n=[1..N], the sequence of each component Number it is music-tempo serial number b, b=[1..B], the value of each component is the decomposition coefficient of the music-tempo；Then, each frame is believed Number decomposition coefficient s_n, according to atom g in redundant dictionary_nRespective frequencies find corresponding music-tempo serial number b, resolving system Number s_nAs the decomposition coefficient of the music-tempo, identical music-tempo serial number is answered if there is multiple atom pairs, then it will be multiple After the cumulative summation of decomposition coefficient, then as the decomposition coefficient of the music-tempo；

S9. merge the music-tempo spectrum vector per frame signal, form music-tempo spectrogram：

The music-tempo spectrum vector S of all frames_n, assembled by row mode and be merged into music-tempo spectrogram S=S (b, n), b= [1..B], n=[1...N].

2. a kind of music-tempo spectrogram generation method based on match tracing, it is characterised in that (4) step in step S7 is exited and followed The condition of ring is to terminate to recycle by cycle-index, cycle-index is arranged according to the requirement of music-tempo spectrogram, i.e., to K as cycle Number carries out assignment and exits cycle when K reaches preset value；S is obtained after loop termination_n,g_n, n=[1...K].