Looking for ideas for a simple pattern matching algorithm to run on a microcontroller

Question

I'm working on a project to recognize simple audio patterns. I have two data sets, each made up of between 4 and 32 note/duration pairs. One set is predefined, the other is from an incoming data stream. The length of the two strongly correlated data sets is often different, but roughly the same "shape". My goal is to come up with some sort of ranking as to how well the two data sets correlate/match.

I have converted the incoming frequencies to pitch and shifted the incoming data stream's pitch so that it's average pitch matches that of the predefined data set. I also stretch/compress the incoming data set's durations to match the overall duration of the predefined set. Here are two graphical examples of data that should be ranked as strongly correlated:

http://s2.postimage.org/FVeG0-ee3c23ecc094a55b15e538c3a0d83dd5.gif

(Sorry, as a new user I couldn't directly post images)

I'm doing this on a 8-bit microcontroller so resources are minimal. Speed is less an issue, a second or two of processing isn't a deal breaker.

It wouldn't surprise me if there is an obvious solution, I've just been staring at the problem too long. Any ideas?

Thanks in advance...

Answer 1

Couldn't see the graphic, but... Divide the spectrum into bins. You've probably already done this already , but they may be too fine. Depending on your application, consider dividing the spectrum into, say 16 or 32 bins, maybe logarithmically, since that is how we hear. Then, compare the ratios of the power in each bin. E.g, compare the ratio of 500 Hz to 1000 Hz in the first sample with that same ratio in the 2nd sample. That gets rid of any problem with unequal amplitudes of the samples.

Answer 2

1D signal matching is often done with using the convolution function. However, this may be processor intensive.

A simpler algorithm that could be used is to first check if the durations of each note the two signals are roughly equal. Then if check the next-frequency pattern of the two signals are the same. What I mean by next-frequency pattern is to decompose the ordered list of frequencies to an ordered list of whether or not the next frequency is higher or lower. So something that goes 500Hz to 1000Hz to 700Hz to 400Hz would simply become Higher-Lower-Lower. This may be good enough, depending on your purposes.