Audio Beat Detection Analysis?

An Anonymous Coward with a developing sense of rhythm asks: "I'm a CS student, and I'm interested in audio processing - specifically beat and pitch detection. Whilst there seems to be quite a lot on the Internet about tempo and pitch modification algorithms, I'm having trouble getting anything about the detection field, apart from a few PhD articles. Does anybody have any suggestions of a good place for a undergrad CS student to start? It's a complex subject I know, but I'd like to investigate it further, and am at a loss as to where to start"

Piece of cake

[Anonymous Coward]

Pitch detection is a simple FFT (Fast Fourier Transform). You can use Matlab or rip the code from Numerical Recipies. Note that you'll most likely want to do the STFT (Short Time Fourier Transform) if you want to detect "notes".

Tempo detection is a little trickier but still not that bad. You can take a local autocorrelation of the signal. From this, you should see some periodic hills and valleys. (as well as some noise... good time for a low pass filter?) To figure out the periodicity of the autocorrelation, we use our old friend the FFT again!

These are the sorts of tricks that Winamp plugins and dancing robots [caltech.edu] use.

Re:Piece of cake

[jbridge21]

There's a big difference between current practical beat detection, and theoretical beat detection. I have a feeling he's heading towards the latter, in which case the simple tricks that Winamp/XMMS plugins use won't be good enough.
-----

Good reference

[cbnewman]

Try The Computer Music Tutorial [fatbrain.com] by Curtis Roads. It should give you a good theoretical background for what you are talking about. Implementation is left as exercise to the reader. Welcome to the world of research.

Beat detection

[OmegaDan]

As a musician (and a cs undergrad myself) ... I can tell you the most you'll get out of beat detection is some multiple of the tempo ... once you've got your fft going -- have your software look for strong regular spikes in ceartin frequency ranges ... most reliable would be hte bass drum I would guess ... this is of course assuming the music your analyzing has a bass drum ...

But your plain screwd for music of any signifigant complextiy :) ... kicks are rarely in the same time everytime ... what you COULD do is overlay two pieces of the song ontop of eachother, and adjust the size and start position of the pieces and match up the beats ( Like holding two identical transperencies up to eachother) ... when alot of the rythmic components match then its a pretty good bet you've discovered a measure. The difficulty then becomes finding measures in the first place ... And you have the additional complexity of time signatures ... if you discover what you think is a measure ... who knows if its 4/4 with double time feel, or just 2/2 ... and odd meters like 3/4 (waltzes) and 5/4 (mission impossible theme ... take 5) ... and then you have compibanation time signatures which are a pain in the ass (to play and to detect I would immagine) ... Like 9/4 is usuall expressed as a 4/4 measure followed by a 5/4 measure (the song alternates like this every other measure) ... (off topic) I remember once playing with marshal hawking (minor jazz guy) at a jazz concert (idywild jazz festival in CA) and he handed us a piece he had just written in 12/4 which he wanted to perform in an hour!

all of this is not to mention that alot of pieces have "stop times" as well (sections where the rythm section stops completley ...

Another method might be to filter out ceartin frequency ranges, and then gate the result of that ... (this would be a good way to isolate bass drum impulses, cymbal impulses etc)

But if you really are interested -- I would suggest starting by checking out programs that convert spectral information into visual information -- ie XMMS visualazation plugins and I seem to recall a program for DOS back in the day called "Cthulu" which was essentailly a visualization program ... It had a beat detection mode that would change the visualaztion style with the beat -- the source code might be avaliable. (though I don't recall how well it worked!) ... when you see the sound waves expressed visually its very easy to pickout the beats by hand ... its a good way to get your mind thinking about the problem.

OmegaDan ...

MediaLab Work

[Hnice]

My girlfriend's brother did his phd at the MIT Medialab on this very subject. Check his stuff out at um, this [mit.edu], which is more or less exctly what you're talking about. He was in the "Machine Listening Group".

Beat Detection?

[Lish]

Think we could ever refine this to a device we could implant in guys with no rhythm who try to dance? ;-)

Girl to guy on dance floor: "Um, you're way off. Go replace the batteries in your beat detector."

Dude...

[NNland]

In taking a look at sound as merely a style of image, a'la winamp's VoicePrint (in the nullsoft fullscreen visualization library), there are many algorithms that deal with edge detection in images (I'm writing one myself). If you alter the algorithm ever so slightly in order to look for those particularly large edges that occur at roughly the same time (multiple pitches at the same time, rather than one pitch over a long time), you can create a table of times between large edges, then using some simple stats and a bit of number theory, I'm sure you could come up with a beat detection algorithm that would work fairly well.

Re:Beat detection

[tzanger]

I have been contemplating this (machine listening) for years and while I haven't written a lick of code yet I've got a few theories on how to do this stuff.

all of this is not to mention that alot of pieces have "stop times" as well (sections where the rythm section stops completley ...

I'd make the computer do it the same way I do... a type of phase locked loop. When the music starts I can very quickly acquire the beat and when the beat is missing I go on what was in the past to "manufacture" beats in the absence of them. Of course if there are several bars of silence my internal PLL starts to waver, just as an electronic one would. Piece of cake.

recycle

[pallex]

recycle is a win9x produce for arsing about with samples - takes a sample and finds the individual samples within and lets you move the trigger points around to change speed, feel etc.

i`ve not thought too hard about it, but i`m sure its just checking for (regular?) samples higher than a certain threshold?

Re:Piece of cake

[wik]

As far as an FFT engine goes, I've found that the FFTW library [fftw.org] (it's GNU!) is very easy to use and not particularly processor intensive. There's no reason to rewrite code when people have made the "Fastest Fourier Transform in the West!" :)

I used it on a real-time guitar sound effects processing program (never released) that I wrote a year ago and never had any problems using it.