Find the beats in an MP3 file

Question

In this challenge, your task is to take an simple recording in mp3 format and find the time offsets of the beats in the file. Two example recordings are here:

https://dl.dropboxusercontent.com/u/24197429/beats.mp3 https://dl.dropboxusercontent.com/u/24197429/beats2.mp3

Here is the third recording with much more noise than the two previous:

https://dl.dropboxusercontent.com/u/24197429/noisy-beats.mp3

For example, the first recording is 65 seconds long and contains exactly (unless I miscounted!) 76 beats. Your job is to devise a program that takes such an mp3 file as input and outputs a sequence of the time offsets in milliseconds of the beats in the file. A beat is defined to occur, of course, when the guitarist playing plucks one or more strings.

Your solution must:

• Work on any mp3 file of similar "complexity". It can fail on to noisy recordings or to quickly played melodies -- I don't care.
• Be fairly precise. Tolerance is +/- 50 ms. So if the beat occurs at 1500 ms and your solution reports 1400, then that is unacceptable.
• Use only free software. Calling ffmpeg is allowed as is using any freely available third party software for your language of choice.

The winning criteria is ability to successfully detect beats despite noise in the supplied files. In case of a tie, the shortest solution wins (length of 3rd party code isn't added to the count).

Answer 1

Python 2.7 492 bytes (beats.mp3 only)

This answer can identify the beats in beats.mp3, but will not identify all notes on beats2.mp3 or noisy-beats.mp3. After the description of my code, I'll go into detail as to why.

This uses PyDub (https://github.com/jiaaro/pydub) to read in the MP3. All other processing is NumPy.

Golfed Code

Takes a single command line argument with the file name. It will output each beat in ms on a separate line.

import sys
from math import *
from numpy import *
from pydub import AudioSegment
p=square(AudioSegment.from_mp3(sys.argv[1]).set_channels(1).get_array_of_samples())
n=len(p)
t=arange(n)/44.1
h=array([.54-.46*cos(i/477) for i in range(3001)])
p=convolve(p,h, 'same')
d=[p[i]-p[max(0,i-500)] for i in xrange(n)]
e=sort(d)
e=d>e[int(.94*n)]
i=0
while i<n:
 if e[i]:
  u=o=0
  j=i
  while u<2e3:
   u=0 if e[j] else u+1
   #u=(0,u+1)[e[j]]
   o+=e[j]
   j+=1
  if o>500:
   print "%g"%t[argmax(d[i:j])+i]
  i=j
 i+=1

Ungolfed Code

# Import stuff
import sys
from math import *
from numpy import *
from pydub import AudioSegment

# Read in the audio file, convert from stereo to mono
song = AudioSegment.from_mp3(sys.argv[1]).set_channels(1).get_array_of_samples()

# Convert to power by squaring it
signal = square(song)
numSamples = len(signal)

# Create an array with the times stored in ms, instead of samples
times = arange(numSamples)/44.1

# Create a Hamming Window and filter the data with it. This gets rid of a lot of
# high frequency stuff.
h = array([.54-.46*cos(i/477) for i in range(3001)])
signal = convolve(signal,h, 'same') #The same flag gets rid of the time shift from this

# Differentiate the filtered signal to find where the power jumps up.
# To reduce noise from the operation, instead of using the previous sample,
# use the sample 500 samples ago.
diff = [signal[i] - signal[max(0,i-500)] for i in xrange(numSamples)]

# Identify the top 6% of the derivative values as possible beats
ecdf = sort(diff)
exceedsThresh = diff > ecdf[int(.94*numSamples)]

# Actually identify possible peaks
i = 0
while i < numSamples:
 if exceedsThresh[i]:
  underThresh = overThresh = 0
  j=i
  # Keep saving values until 2000 consecutive ones are under the threshold (~50ms)
  while underThresh < 2000:
   underThresh =0 if exceedsThresh[j] else underThresh+1
   overThresh += exceedsThresh[j]
   j += 1
  # If at least 500 of those samples were over the threshold, take the maximum one
  # to be the beat definition
  if overThresh > 500:
   print "%g"%times[argmax(diff[i:j])+i]
  i=j
 i+=1

Why I miss notes on the other files (and why they are incredibly challenging)

My code looks at changes in signal power in order to find the notes. For beats.mp3, this works really well. This spectrogram shows how the power is distributed over time (x axis) and frequency (y axis). My code basically collapses the y axis down to a single line. Visually, it's really easy to see where the beats are. There's a yellow line that tapers off again and again. I highly encourage you to listen to beats.mp3 while you follow along on the spectrogram to see how it works.

Next I'll go to noisy-beats.mp3 (because that's actually easier than beats2.mp3. . Once again, see if you can follow along with recording. Most of the lines are fainter, but still there. However, in some spots, the bottom string is still ringing when the quiet notes start. That makes finding them especially hard, because now, you have to find them by changes in frequency (the y axis) rather than just amplitude.

beats2.mp3 is incredibly challenging. Here's the spectrogram In the first bit, there some lines, but some notes really bleed over the lines. To reliably identify notes, you'd have to start tracking the pitch of the notes (fundamental and harmonics) and seeing where those change. Once the first bit is working, the second bit is twice as hard as the tempo doubles!

Basically, to reliably identify all of these, I think it takes some fancy note detection code. Seems like this would be a good final project for someone in a DSP class.