beat detection algorithm?

[Adam Murray]

Hello,

Does anyone know of any basic beat detection algorithms? Any research papers (that are comprehensible) or open source projects? It doesn't have to be particularly accurate, I just need a place to get started.

I'm looking to take a stream of MIDI input (which is getting reduced to a list of time offsets, possibly with velocity) and feed it into an algorithm that can guess the tempo. I don't really care about meter.

I have some books on this subject by David Temperley, but they're too complicated for me right now. I also don't want to have to train some machine learning system on a large body of music. I just want a simple, self-contained algorithm.

PS - later I'll be looking into scale/key detection too, so I'll take any pointers to info on that topic as well :)

Thanks for any pointers,

Adam

[Vlad Spears]

Hmmm... maybe there's a useful starter hiding in the [bonk~] source?

http://puredata.sourcearchive.com/documentation/0.42.5-3/bonk~_8c-source.html

Vlad

[karaokaze]

Perhaps you might ask the author(s) for the source to op.beatitude~
http://www.maxobjects.com/?v=objects&id_objet=3798&requested=tempo&operateur=AND&id_plateforme=0&id_format=0

or tristan jehan's beat~
http://cnmat.berkeley.edu/downloads
older version and original site here:
http://web.media.mit.edu/~tristan/maxmsp.html

or you can look on that older page and check out nick collin's supercollider port of beat~... might be some source there, or check out nick collin's supercollider bbcut and similar for supercollider sources:
http://www.informatics.sussex.ac.uk/users/nc81/index.html

and some good reading and extraneous patches from the c74 forums:
http://cycling74.com/forums/topic.php?id=30045
http://cycling74.com/forums/topic.php?id=23948

[Adam Murray]

Thanks for the response, guys, but I think I wasn't clear enough.

Like you, most of the algorithms I can find are for audio. I'm looking for something that works with MIDI. Discrete lists of timestamps...

I suppose it's possible to extract relevant parts of these algorithms, but I've been getting kind of overwhelmed with the technical details and DSP that's not useful to me. 

Hell, maybe I should just try to come up with my own... just need to think about it more, I guess.

Adam

[karaokaze]

oh, ok, but then, i wonder how it's beat-detection if it's confined to MIDI. beat detection would involve some kind of analysis to detect a beat from audio(then maybe using that DSP-based analysis you'd output MIDI time stamps)... maybe i'm still not clear...

In any case, detonate object in Max might help with creating your own(or maybe you could figure out some basic form of Recycle).
See the old recycler example in your Max examples folder for detonate/recycle usage:
Max5/examples/legacy-examples/recycler folder

But I must admit, I've never heard of anything else beyond Recycle that would be similar to what you're suggesting.
Sounds interesting, though, keep us posted!
-Raja

[Tim Thompson]

PS - later I'll be looking into scale/key detection too, so I'll take any pointers to info on that topic as well :)

The algorithm I've used to guess the root (i.e. key) of a phrase, given MIDI data, is something I got from Christopher John Rolfe (ro...@sfu.ca), who said it was culled from "Jazz Composition and Orchestration" by W. Russo, page 25, ex.7.  Below is the KeyKit code for it.

      ...Tim...

#=========================================================

#name findroot

#usage findroot(ph)

#desc Given a phrase, try to guess the root of what's being played.

#desc The algorithm was given to me by Christopher John Rolfe (ro...@sfu.ca),

#desc who says it was culled from W.Russo, Jazz Composition and Orchestration,

#desc p.25, ex.7.

Strength = [0=12,1=8,2=6,3=4,4=2,5=1,6=12,7=0,8=3,9=5,10=7,11=9]

function findroot(ph) {

n = sizeof(ph)

ph.time = 0 # so that notes are sorted by pitch

maxv = 999

root = ''

ph -= nonnotes(ph)

for ( n1=1; n1<=n; n1++ ) {

for ( n2=n1; n2<=n; n2++ ) {

v = Strength[dp=(ph%n2.pitch-ph%n1.pitch)]

if ( v < maxv ) {

if ( (v%2)==0 )

root = ph%n1

else

root = ph%n2

maxv = v

}

}

}

return(root)

}

#=========================================================

[David Lowenfels]

here's a short overview paper with references I found by googling
"midi beat detection algorithm"
http://www.music.mcgill.ca/~ich/classes/mumt611_05/casciato/MIDIRhythmTranscription.pdf

-David

[Mike Rotondo]

I haven't thought about it a ton but it seems like a good starting point would just be to create a dynamic histogram of possible tempos (represented as beat lengths) that you increment as you go through the stream and see certain time intervals occur between notes. You stop watching a note when you saw it longer ago than your longest acceptable beat length. At the end, your beat length is determined by some combination of {largest observed time-interval, time-interval with highest accumulated value}.

pseudocode, probably got some bugz:

notes = queue

accumulated_time = 0

time_intervals = {}

last_note_time = 0

for note in note_stream:

  accumulated_time += note.time - last_note_time // don't do this for the first note

  last_note_time = note.time

  // you'll want to not double/triple/n-ple count simultaneous notes (as in a chord)

  // again this could fuck things up if your first note is at time 0, so handle that case yourself :)

  if (note.time == last_note_time)

    continue

  // add the new note to the queue
  notes.push(note)

  // get rid of notes that occurred too long ago

  while (accumulated_time - notes.peek.time > longest_acceptable_beat)

    notes.pop()

  for past_note in notes:

    time_interval = note.time - past_note

    if (time_interval not in time_intervals)

      time_intervals[time_interval] = 0

    time_intervals[time_interval] += 1 // you might need to do some fuzziness here if your time intervals are not all exactly quantized, float equality sucks also so you might need to be smarter anyway

// Done processing notes

return choose_best_time_interval(time_intervals)

def choose_best_time_interval(time_intervals)

  time_intervals_scores = {}

  sort time_intervals descending

  score = 1

  falloff = 0.5 // Tune this exponential decay, or do the falloff differently. We're just trying to give the larger time intervals more emphasis

  for time_interval in time_intervals.keys

    time_intervals_scores = time_intervals[time_interval] * score

    score *= falloff

  return the key in time_intervals_scores that has the highest value

or something! good luck!  

[Matt Ridenour]

Adam,

I think a good approach might be to disregard the time between notes at first and instead pay attention to the relative duration of the notes.  Cleaned up with some averaging and some sort of weighting/quantization, you could identify relationship between notes, i.e. most notes are x duration with a few of 2x duration, 4x duration and some of 1/2x duration.  Making some assumptions, perhaps based on the shortest duration notes, you could then extrapolate a base tempo from the duration differences.  Once that tempo is established, you could then compare it with the note on events and give it a weighted score.

-Matt Ridenour

[Mike Rotondo]

I agree, that's a better idea :)

[Adam Murray]

Lots of good ideas. I will play around. To provide more context:

I am recording realtime MIDI into some custom (Ruby) software. I am sticking all the recorded notes into a data structure I call Timeline, which maps timestamps to lists of MIDI events.

Because this is realtime, human input, it's messy. Notes don't land on the beat, and I also don't know how to establish a tempo without any a priori tempo information. I considered playing a metronome tick and recording against that, but I rather like the idea of just free-form improvising on my MIDI keyboard, and then trying to extract useful musical patterns (like rhythmic motifs) from the raw data. As a first step, I want to "clean up" the input and quantize it. But I can't quantize it without knowing where the beats fall, and so I need to figure out the tempo to establish the pulse.

I just want a rough, "good enough" solution. If it guesses a tempo that's off by a factor of 2, 3, 4, etc, I think it will still be useful.

If you want to know more, my project is here: https://github.com/adamjmurray/mtk . It is not well documented yet and there are a bunch of things I want to rework (so the API will change). The realtime MIDI input currently relies on my jsound gem for JRuby (http://rubygems.org/gems/jsound). It's also going to work in Max and Max for Live (I have big plans for enhancing Live's MIDI editing possibilities) using my "JRuby for Max" project which is close to 1.0 launch (see http://compusition.com/web/news/2011/06/06 for a beta version of that). Oh damn, Matt, I should have got you involved in the beta. You still doing Ruby scripting in Max? I've been really bad about promoting my projects... it's more fun coding than talking about it ;)

Anyway, back to the discussion...

The paper David linked to sounds very relevant, but it merely references other papers that contain the information I am looking for. However, it led me to here  http://www.ismir.net/proceedings/index.php where I found a ton of papers on all sorts of computational music topics! I already got distracted with a bunch of other papers that sound interesting :) 

Mike, thanks for taking a stab at a pseudo-algorithm. I see Matt's point, but I think I will probably get the best results by considering both inter-note onset time and note duration (i.e. long notes tend to fall on stronger beats).

As Mike mentioned in the comment: // you might need to do some fuzziness here if your time intervals are not all exactly quantized...

That's a big part of my problem since I'm using "messy" input. I am getting a handle on how to make a rough guess at tempo, and how to quantify the quality of a guessed tempo, but I'm not sure how I will improve the guess without resorting to some sort of inefficient brute force algorithm. (Perhaps I want something like Newton's method?) Hopefully some of these research papers will give me ideas.

And Tim, thanks so much for that code. I will try porting it to my project, if that's ok, and of course I will give you and the others credit. Once I know the root of the key, I suppose guessing the scale should be fairly easy using some basic statistics.

-Adam (jeez, that was a long email)