Categories

Fast Peak Autocorrelation

So, I was at geekcon. It was a blast.

There were many interesting projects, and I didn’t get to play with them all. I did get to work a bit on the Lunar Lander from last year, and this year it was finished successfully. My part was the PC game which interfaced with the microcontroller controlling the lander. As you probably guessed, it was written in Python.

This year, as promised, I worked on the Automatic Improviser. I worked on it with Ira Cherkes.

While the final version worked, it didn’t work well enough, and there is still much work to be done. Still, we had excellent progress.
By the way, I know this subject has been tackled before, and I still wanted to try it myself, without reading too much literature about it.

One of the components of the system is a beat recognizer. My idea to discover the beat is simple: find the envelope (similar to removing AM modulation), and then find the low “frequency” of the envelope.
Instead of doing a Fast Fourier Transform for beat recognition, we were advised that autocorellation will do the trick better and faster. However, when trying to autocorellate using scipy.signal.correlate we discovered that autocorellation was too slow for real time beat recognition, and certainly wasteful.

To solve this issue, we decided to first do peak detection on the envelope, and then autocorellate the peaks. Since there shouldn’t be too many peaks, this has the potential of being really quick. However, there was no standard function to do autocorellation of peaks, so we implemented it ourselves. We were pretty rushed, so we worked fast. Here’s the code:

```def autocorrelate_peaks(peaks): peaks_dict = dict(peaks) indexes = set(peaks_dict.keys()) deltas = set() for i in indexes: for j in indexes: if j>i: continue deltas.add(i-j)   result = {} for d in deltas: moved = set(i+d for i in indexes) to_mult = moved & indexes assert to_mult <= indexes s = sum(peaks_dict[i-d]*peaks_dict[i] for i in to_mult) result[d] = s return result```

This function takes as input a list of tuples, each of the form (peak_index, peak_value), and returns a mapping between non-zero corellation offsets and their values.
Here’s is a sample run:

```In [7]: autocorrelate_peaks([(2, 2), (5,1), (7,3)]) Out[7]: {0: 14, 2: 3, 3: 2, 5: 6}```

After implementing this function, our recognition loop was back to real-time, and we didn’t have to bother with optimizing again.

Categories

Preparing PyImprov for GeekCon on Friday

A long long time ago, I wrote Pytuner. It was one of the first projects I published on this website.
For a long time it just sat there, doing nothing, while the library it’s based on – PyMedia, wasn’t being maintained anymore, and PyTuner could only work on Python 2.4.

Enter GeekCon – GeekCon is a get together of people looking to work on their wildest fantasy projects – things that they don’t get do because of their regular work. Last yet I worked on a real life 3d lunar lander, and this year I thought I’d take the opportunity to work on PyImprov – my wild fantasy project.
The idea is simple – I’ll play some simple chords, and the script will improvise some blues solo. To that purpose, I wrote (also a long time ago) a chord recognizer. Now I’m missing a beat recognizer, and a simple improviser, which I plan to complete during the GeekCon weekend.

In preparation for the event, I’ve opened up a subversion repository for PyImprov on Assembla, and patched the scripts to work with PyAudio instead of PyMedia.

So, onwards to GeekCon, see you on the other side, with a guitar and a Python script in hand!