Obtaining beat histogram using Tzanetakis algorithm

Question

I am working to make a music player with automatic genre classification application in Java. On Google searches I mostly found the works of George Tzanetakis who describe an algorithm from Music Genre Automatic Classification. I have big problems with obtaining the beat histogram.

http://dspace.library.uvic.ca:8080/bitstream/handle/1828/1344/tsap02gtzan.pdf?sequence=1 this is one of the documents that describes the algorithm and includes a flow diagram for beat analysis.

I have implemented all the functions from that flow diagram: the Full Wave Rectification, Low Pass Filtering, Downsampling, Normalization and Autocorrelation. I am pretty sure that these are correct because i found plenty of implementations and formulas in the internet.

What I find difficult is how to link these together to obtain the beat histogram.

What I do not figure is how to make the processing of those octaves and how to sum them. I understood that octaves are same thing as in music. I implemented the DWT transform that as it is described in this document and used the wikipedia page about DWT implementation that luckily is written in Java, just like my application.

What I think my problem is that I did not understand properly how to get the octaves from the DWT transform. I obtain a waveform just like in : http://en.wikipedia.org/wiki/File:Haar_DWT_of_the_Sound_Waveform_%22I_Love_Wavelets%22.png

After that DWT transform I have split the transform just like in the wiki page with waveform for that audio sample: second half is first octave and just like in wiki example it looks like the original signal. First half i split again and its second half is second octave and so on. Am I doing wrong at this stage? For about two weeks I was sure I did it correctly and now that I get a wrong signal after autocorrelation, with no peaks as it should be.

How I did to sum the octaves after processing each of them as in the diagram: I first took the largest one, and for the second one which is half size of first octave I added to the large one every second index in the array. From the third I added the values to every 4th index in the array and so on. I got about 6-7 octaves in total. And this is where I think I may be wrong again. Because those octaves are arrays with different sizes(each is half size of the other one) and had to split the smaller ones over the larger octave. Have I done wrong? I very much believe that the fact that my octaves arrays have different sizes could be where I am wrong.

Please tell me where I may be wrong in what I described about how I tried to implement that algorithm. I very much think that I did not understood what octaves and I should not have arrays with different sizes after the DWT transform.

After the autocorrelation I should have a signal with peaks while I have something linear so I cannot make Peak Detection(last stage of the algorithm) with this.

One more thing I would like to ask is how would I get that bpm from the signal after the autocorrelation? I have an array with size of 2048 because I started with 131072 samples and did a downsampling to have 65536 values as in the documentation(my wav files have 44100 frequency while in document they had 22050). After dwt and getting first octave I had 32768 samples for first octave and 2048 after the downsampling by 16. In the beat histograms shown in this document they have bpm values from 60 to 200. How am I obtaining those values? I understand that bpm is almost same thing as frequency but I do not know how to get frequency from this transform.

Edit

After summing the octaves, using the sample from the answer, I got something like this:

They are a bit different because I used DWT as filterbank. After I apply the usual autocorrelation I get something like this:

But the problem is that Tzanetakis used the enhanced autocorrelation which is a bit different and is based on Tolonen and Karjalainen algorithm.

Answer 1

The firsts steps by Tzanetakis can be described as an Scheirer algorithm(Tempo and beat analysis of acoustic musical signals by Eric Sheirer), you can use DTW, filterbanks or FFT to split your signal in N subbands!

I'll try to help you with what I did in the past, my steps are described below.

I can show a simple example of 6(six) (200, 400, 800, 1600, 3200, 6400) decomposed subbands aka "Scheirer 1998″, I used this sample to test:

After DTW or filterbanks you need extract the envelope of each subband:

1. Apply Full Wave Rectification
2. Apply Low Pass Filter
3. Apply Downsample
4. Apply Mean Removal

My envelopes from the six subbands above are:

OK now do you have six downsampled envelopes (Downsample can help you gain speed to compute the autocorrelation), you need sum all envelopes like:

Almost there, you need apply autocorrelation and to find bpm values between 60 and 200, you need compute the START and END position to be computeded from your summed envelopes:

start = (60 * downsampled_value) / (200)

end = (60 * downsampled_value) / (60)

Now you know the start and end to do the autocorrelation :-)

The next step is find the peak from your autocorrelation and convert to BPM:

BPM=60*downsampled_value/PEAK

And finally ride a histogram with the results of BPM's from each audio piece analyzed !

PS: Tzanetakis and Sheirer algorithm is not perfect its works well in strong rhythmic songs.