5 ms·

Beat Detection Algorithms, Part 1

61 points by snickmy 11y ago

hmage 11y ago
This algorithm won't work on music without kick drums while it still has beat.
- betenoire 11y ago
  Though the article mentions a low-pass strategy, it doesn't specify anything about needing a kick. There is a lot of frequency overlap between a kick and say toms, snares, so any percussive element should do. And if you have no beat in that range, then you'd probably not use the low-pass strategy described there. I would add that a song must have percussive elements in order to have a "beat" as described by the article. It can have a tempo without a beat (think organ music), but this is called beat detection, not tempo detection.
  - stephencanon 11y ago
    > a song must have percussive elements in order to have a "beat" as described by the article. "You can think to the beat of a song as the rythm you tap your foot at while listening to it." By the stated definition, almost all music has a beat, whether or not it has percussive elements.
    - betenoire 11y ago
      a percussive element has little to no attack, and a quick decay. It doesn't have to be drums, you can play a trumpet or flute "percussively". The article also says it's the "beat" that makes you dance. A barbershop quartet can have a beat with just vocals. I'm not disagreeing with what you wrote, just explaining why I think a kick isn't necessary for beat detection, even though it makes it easier.
  - smosher_ 11y ago
    Did you even read the article? The article's description of "beat" doesn't conflict with the musical term but yours does. In fact the article even relates beats to tempo and describes the results in terms of tempo. This is about tempo detection. The reason this technique is called "beat detection" is it can be used to collect the individual beats from the stream contrasted with knowing the just the tempo doesn't tell you where the beats are exactly (and doesn't help a lick with finding the off-beats.) Tempo detection is only one product of these algorithms, and guesses can be constructed from any of them, though sometimes additional heuristics are needed. The accuracy of the LPF technique is well worth criticizing. Yes, it's fairly good, but it's not the best one we have and the article says part 2 will describe a better technique. I should note that even organs and vocals can create transients that are often associated with beats. The LPF probably does better simply by eliminating false-positives.
    - betenoire 11y ago
      who the fuck are you arguing with? Yes I read the article, and the linked-to articles within. I've read much more too. I'm simply saying a kick isn't necessary to do beat detection. Would you like to address that point?
- CountHackulus 11y ago
  This is clearly marked part 1, I'd maybe wait for part 2 before saying that everything is broken.
- shabble 11y ago
  There are alternatives, such as some of the work done by Masataka Goto in drum-free tempo/beat detection, see [1] for some literature. I haven't kept up with the literature, but his work is quite old now, so I wouldn't be surprised if there were better approaches along similar lines. There's also Beatroot[2] which operates in a similar fashion to the OP described solution, but AIUI more flexible in looking for certain spectral flux signatures in various bands to determine beat onsets. I'm also intrigued by the cliffhanger in the original article posted here - wavelet or other approaches for accuracy/resilience, and so will be looking forward to when it's released. [1] https://staff.aist.go.jp/m.goto/PROJ/bts.html https://staff.aist.go.jp/m.goto/PROJ/bts.html [2] http://www.eecs.qmul.ac.uk/~simond/beatroot/ http://www.eecs.qmul.ac.uk/~simond/beatroot/
mrdmnd 11y ago
Autocorrelation may also be a useful tool here - have you considered it at all?
- peterb 11y ago
  Yeah, that's what I would do. First apply an IIR low pass filter (e.g. 200 Hz), downsample, apply a window function (e.g. Hamming, but there are probably better choices) and then autocorrelate the window. The peaks in the autocorrelation should give you the beat. If you use a higher frequency you can get the sub-beats. This should work with all music types ... kick drum or no kick drum.
j_m_b 11y ago
yay for sensible names like left[i] and right[i]!
j2kun 11y ago
The topic sounds interesting, but I can't tell whether the interesting part is supposed to be the preprocessing, I.e. going from a raw music file to some sort of binary vector, or the actual beat detection, which could ostensibly work on any binary vector. Wouldn't one just do a Fourier transform for the second part?
escherize 11y ago
Aww. I read this title as Beat Detection-Algorithms, hoping it would help with some gray-hat marketing we've been doing. Still interesting though.
- faitswulff 11y ago
  I read it as "Bear Detection Algorithms" and was similarly excited for the wrong reasons.
sagargv 11y ago
Would harmonic product spectrum would work here? In my experience, it works very well for detecting the note frequency of guitar, piano etc.
- hamiltonkibbe 11y ago
  It would probably not be practical just because you'd need extremely long Fourier transform windows. At 100bom and 44.1khz, downbeats are 26000+ samples between downbeats. It may work with shorter windows for music that is rhythmically complex (more subdivisions would be analogous to more harmonics in the typical pitch detection application) but would certainly fall apart at lower tempos.
jawngee 11y ago
I wrote my own algorithm for my video editor Vix, which takes a song and then automatically edits videos to the beats it finds. Sound energy algorithm is not very good imho. Low pass is a step in the right direction, but I've found a combo of low pass and band pass to be more accurate. Here's a vid of Vix in action: https://vimeo.com/90104152 https://vimeo.com/90104152
Qantourisc 11y ago
I still believe the best option for accuracy is actual instrument/voice recognition. Might however not be the fastest or easiest. Also I'm not sure if it's out there already or not.
bobowzki 11y ago
I'm surprised it doesn't mention autocorrelation. Maybe that's in part 2.

61 points by snickmy 11y ago

hmage 11y ago

This algorithm won't work on music without kick drums while it still has beat.

betenoire 11y ago
Though the article mentions a low-pass strategy, it doesn't specify anything about needing a kick. There is a lot of frequency overlap between a kick and say toms, snares, so any percussive element should do. And if you have no beat in that range, then you'd probably not use the low-pass strategy described there. I would add that a song must have percussive elements in order to have a "beat" as described by the article. It can have a tempo without a beat (think organ music), but this is called beat detection, not tempo detection.
- stephencanon 11y ago
  > a song must have percussive elements in order to have a "beat" as described by the article. "You can think to the beat of a song as the rythm you tap your foot at while listening to it." By the stated definition, almost all music has a beat, whether or not it has percussive elements.
  - betenoire 11y ago
    a percussive element has little to no attack, and a quick decay. It doesn't have to be drums, you can play a trumpet or flute "percussively". The article also says it's the "beat" that makes you dance. A barbershop quartet can have a beat with just vocals. I'm not disagreeing with what you wrote, just explaining why I think a kick isn't necessary for beat detection, even though it makes it easier.
- smosher_ 11y ago
  Did you even read the article? The article's description of "beat" doesn't conflict with the musical term but yours does. In fact the article even relates beats to tempo and describes the results in terms of tempo. This is about tempo detection. The reason this technique is called "beat detection" is it can be used to collect the individual beats from the stream contrasted with knowing the just the tempo doesn't tell you where the beats are exactly (and doesn't help a lick with finding the off-beats.) Tempo detection is only one product of these algorithms, and guesses can be constructed from any of them, though sometimes additional heuristics are needed. The accuracy of the LPF technique is well worth criticizing. Yes, it's fairly good, but it's not the best one we have and the article says part 2 will describe a better technique. I should note that even organs and vocals can create transients that are often associated with beats. The LPF probably does better simply by eliminating false-positives.
  - betenoire 11y ago
    who the fuck are you arguing with? Yes I read the article, and the linked-to articles within. I've read much more too. I'm simply saying a kick isn't necessary to do beat detection. Would you like to address that point?
CountHackulus 11y ago
This is clearly marked part 1, I'd maybe wait for part 2 before saying that everything is broken.
shabble 11y ago
There are alternatives, such as some of the work done by Masataka Goto in drum-free tempo/beat detection, see [1] for some literature. I haven't kept up with the literature, but his work is quite old now, so I wouldn't be surprised if there were better approaches along similar lines. There's also Beatroot[2] which operates in a similar fashion to the OP described solution, but AIUI more flexible in looking for certain spectral flux signatures in various bands to determine beat onsets. I'm also intrigued by the cliffhanger in the original article posted here - wavelet or other approaches for accuracy/resilience, and so will be looking forward to when it's released. [1] https://staff.aist.go.jp/m.goto/PROJ/bts.html https://staff.aist.go.jp/m.goto/PROJ/bts.html [2] http://www.eecs.qmul.ac.uk/~simond/beatroot/ http://www.eecs.qmul.ac.uk/~simond/beatroot/

mrdmnd 11y ago

Autocorrelation may also be a useful tool here - have you considered it at all?

peterb 11y ago
Yeah, that's what I would do. First apply an IIR low pass filter (e.g. 200 Hz), downsample, apply a window function (e.g. Hamming, but there are probably better choices) and then autocorrelate the window. The peaks in the autocorrelation should give you the beat. If you use a higher frequency you can get the sub-beats. This should work with all music types ... kick drum or no kick drum.

j_m_b 11y ago

yay for sensible names like left[i] and right[i]!

j2kun 11y ago

The topic sounds interesting, but I can't tell whether the interesting part is supposed to be the preprocessing, I.e. going from a raw music file to some sort of binary vector, or the actual beat detection, which could ostensibly work on any binary vector. Wouldn't one just do a Fourier transform for the second part?

escherize 11y ago

Aww. I read this title as Beat Detection-Algorithms, hoping it would help with some gray-hat marketing we've been doing. Still interesting though.

faitswulff 11y ago
I read it as "Bear Detection Algorithms" and was similarly excited for the wrong reasons.

sagargv 11y ago

Would harmonic product spectrum would work here? In my experience, it works very well for detecting the note frequency of guitar, piano etc.

hamiltonkibbe 11y ago
It would probably not be practical just because you'd need extremely long Fourier transform windows. At 100bom and 44.1khz, downbeats are 26000+ samples between downbeats. It may work with shorter windows for music that is rhythmically complex (more subdivisions would be analogous to more harmonics in the typical pitch detection application) but would certainly fall apart at lower tempos.

jawngee 11y ago

I wrote my own algorithm for my video editor Vix, which takes a song and then automatically edits videos to the beats it finds. Sound energy algorithm is not very good imho. Low pass is a step in the right direction, but I've found a combo of low pass and band pass to be more accurate. Here's a vid of Vix in action: https://vimeo.com/90104152 https://vimeo.com/90104152

Qantourisc 11y ago

I still believe the best option for accuracy is actual instrument/voice recognition. Might however not be the fastest or easiest. Also I'm not sure if it's out there already or not.

bobowzki 11y ago

I'm surprised it doesn't mention autocorrelation. Maybe that's in part 2.