Monthly Archives: March 2005

Adventures in Beat Detection

I have been playing around with beat detection, because two games that I have been working on would really benefit from having strong beat detection. I think I’m on to something with this one (maybe), so I’ll post my methods and results here. I don’t have any schoolin’ in fourier analysis, so things I’m doing may seem naive to the experienced fouriereer. If you’re one of these, please please please point me in the right direction.

I came up with this algorithm on the bus to school this morning. When I got home I couldn’t wait to try it on some real data with Mathematica. I describe my findings here:

I started with this 5-second sound sample (sorry about the WAViness… that’s the format I loaded it in as). It’s an excerpt from Rachmaninoff’s symphonic dances, which I chose because it has a wide frequency spectrum but is still very rhythmic. Mathematica plots the samples like so:

    In[1]:=   wav = Import["symphonic_dances_fourier_field.wav"];
    In[2]:=   samples = wav[[1,1]];
    In[3]:=   ListPlot[samples]

Listen to the sample and notice how you can see the beats in the wave. These are raw intensity, and these are what a naive detector would use to pick the beats out. This example isn’t good enough to tell if my beat detector is any better than naive.

Next I compute the “fourier field” of a particular window size, in this case 8192 samples (about 0.18 seconds). This takes successive windows at a given step (in this case 256 samples) and computes their fourier transforms, and sticks it in a two-dimensional array indexed by [time; frequency]. Here’s the code:

    In[4]:=   fourierfieldtime[data_, window_, time_] :=
                  Fourier[data[[Range[time-window, time+window-1] ]] ]
    In[5]:=   fourierfield[data_, window_, step_] :=
                  Table[fourierfieldtime[data, window, i],
                      {i, window+1, Length[data]-window, step}]
    In[6]:=   field = fourierfield[samples, 4096, 256];
    In[7]:=   ListDensityPlot[Abs[field], Mesh -> False]

The next thing I do is take each frequency band (which gives that frequency’s “presence” over the time of the song) and do another fourier transform on it, and put it in a table. This should tell me how each frequency is pulsating in time, with the theory that most frequencies repeat themselves with the beat. Note that I take the absolute value of the previous transform, disregarding the phase. Otherwise I just run round-trip and get a strangely-averaged and phase-rotated version of what I started with.

    In[8]:=   timefield[data_] :=
                  Table[Fourier[Abs[data[[All, i]] ] ], {i, Length[data[[1]] ]}]
    In[9]:=   times = timefield[field];
    In[10]:=  ListDensityPlot[Abs[times], Mesh -> False]

Finally I just add all of these together vertically to get the rough correlation of frequencies of each frequency. We’re only interested in the very low frequencies (of each frequency)—things that happen between 1 and 40 times during the sample—so I only plot those.

    In[11]:=  compose[data_] := Plus @@ data
    In[12]:=  beats = compose[times];
    In[13]:=  ListPlot[Abs[beats[[Range[1, 40] ]] ],
                  PlotJoined -> True, PlotRange -> {0, 320}]

This is our final analysis, so let’s look at it carefully. What is it saying? We want to look at the dominant frequencies, the ones with the strongest correlation. Frequency one is of no interest; it is always high in phaseless fourier transforms. The largest is six, followed by four. What happens six times during this sample? The half notes, which are the strongest orchestra hits. I can’t figure out four yet. The next one is twelve, which corresponds to the quarter notes: that’s the one we’re really interested in. I can’t quite tell how we’re going to communicate that to a reading program. We might just report the five highest levels or something, and let the program determine what kind of tempo range it is looking for.

The final step in the process is to do an inverse fourier transform on this data, to get back something that resembles our beats over time (a very dumbed-down version of the song, as it were). This is pretty cool:

    In[14]:= orig = InverseFourier[beats];
    In[15]:= ListPlot[orig, PlotJoined -> True]

You can see each of the strong beats that you associate with the song. I can’t tell whether the beats occur at the tips of those or at the heavy turnarounds right before the tips. I’m inclined to say the latter. But this information that we’ve reconstructed could easily have been created by a dumb volume analysis. Next week (when I finally have some time again, damn homework—I’m procrastinating a huge project as I speak), I’ll try it on a harder song, a baroque piece or some jazz. My ultimate goal in this project is to get it to beat-detect jazz, which has a very implicit pulse rather than a strong beat.

Second movement sketch

I’ve been beating my creative head against the wall awhile, and finally, today, I came up with something. The melody is beautiful in its simplicity. The star player most of the time is the piccolo, which should make it happy, since it only got to play about three lines of music in the first movement. Anyway, this is just a sketch: I’ll probably keep the melody and the impressionistic piano stuff, but how those end up realizing themselves in anybody’s guess (Oh, and by no means do I consider the end of this recording an ending; it was just where I decided to stop today). This is a turning point in the dynamical system of composition, so feedback will have the most effect now. If you have any ideas, please speak up before I get too attached to what I’ve done. MIDI|MP3

Quantum Particle Demo

This blog is named after a popular saying about quantum mechanics, but there has been little or nothing quantum mechanical mentioned here. Well, my modern physics class at CU is finally getting into the (first-order) details of QM, so I might make the blog live up to its name soon enough. In particular, Namaste and I are working on a game that might have a very elegant quantum-mechanical premise. More on that later. I just wanted to show you guys this. The “1-D Quantum Mechanics Applet” impressed me. It’s something that I’ve been looking for for a while: a visual representation of time dependent distributions. Anyway, check it out.

Logic.pm preview

Due to a request from several people, I am releasing a not-yet-CPAN-ready module called Logic.pm. The development of the idea to write this module is long and boring. But it’s my blog, not yours, so I’ll talk about it.

Many of the problems that I have been solving recently in programming have involved backtracking: rule matching, a simple-minded expert system, pattern matching in argument lists (the first and third are for Perl 6). So I decided to write a backtracking engine module that would help me out. Since I couldn’t find a good namespace to put it in, it was just going to be called Backtracker. I began that on saturday at about 1:00 pm, and finished at about 2:00 pm. You see, the backtracking algorithm is very simple in concept, and a module that implements it doesn’t buy you much. Essentially all a backtracker is is an object interface, plus two combinators: and and or.

Unsatisfied with my result, I decided that I was going to include a proof-of-concept implementation of my Argument Patterns proposal. In my prior art research, I downloaded gprolog, and started playing around. When I saw:

  | ?- append(X, Y, [1,2,3,4]).

  X = []
  Y = [1,2,3,4]

  X = [1]
  Y = [2,3,4]

  X = [1,2]
  Y = [3,4]

  X = [1,2,3]
  Y = [4]

  X = [1,2,3,4]
  Y = []

I was totally impressed. I decided that I must implement prolog unification in my engine. One hour and 135 lines of code later, I had finished Logic::Data::Unify. Wow. It’s amazing how simple and elegant the extremely powerful unification algorithm is.

Anyway, the status of the module: the logic subsystem works pretty well. It’s low on primitives, but those are pretty easy to write. There’s no syntax; you write everything out in essentially syntax-tree form (see examples/append.pl). There’s no documentation, but there are tests (and more than the one-test-for-every-ten-lines-of-code ratio that I like to maintain). The design is solid, but needs a little refactoring, as I’m seeing some limitations as far as custom backtracking control.

Here’s where I’m going: I have to implement some sort of global statefulness so you don’t have to pass that pesky $state object around. Then I’ll try to make some intuitive operator syntax based on overload (but that is a large challenge given the available operators). Maybe I’ll punt and make it look like lisp with the head moved out front. Then I plan to implement junctions using Logic, and finally multimethod dispatch. Then it’s CPAN time.

Two modules in One day

I just wrote and uploaded Perl6::Attributes to CPAN. It came out of frustration for code like this:

    sub populate {
        my ($self, $n) = @_;
        for (1..$n) {
            push @{$self->{organisms}}, Organism->new(rand($self->{width}), rand($self->{height}));
        }
    }

Which I can now write like this:

    sub populate {
        my ($self, $n) = @_;
        for (1..$n) {
            push @.organisms, Organism->new(rand($.width), rand($.height));
        }
    }

Much nicer, no?

Hypotheticals in Perl 5

In Appendix C of Apocalypse 12, Larry speculatively mentioned the syntax:

    let foo();

Which would “try” foo, and then revert things back to the way they were before that if something failed in your block. Well, I’ve implemented a Perl 5 module, Data::COW (which hasn’t been indexed at my time of writing, but will be at your time of reading), which could, er, hypothetically let you do that. Interestingly, I implemented it so you could do that on a smaller scale for the logic programming module I’m writing.

First, assume that all external state in your program is accessed through %$state, and everything other than that is purely functional. This seems like a big assumption, and it kind of is, and it kind of isn’t. If you don’t change the state of any modules (a fairly easy thing to do, depending on what modules you’re using), it would be fairly trivial, though maybe not easy easy, to massage all your own state into a single global hash. (Note that all stateful things need not be in the hash: the hash is just your “root set”, corresponding quite closely to all of your globals and file-scoped lexicals.)

Then I can easily write temp foo():

    my $old = $state;
    $state = make_cow_ref $state;
    foo();
    # remaining code in the block
    $state = $old;

foo() is allowed to change whatever it likes, and it will be restored (of course, only those things that can be copied can be restored) after the block ends. let() is approximately the same:

    my $old = $state;
    $state = make_cow_ref $state;
    eval {
        foo();
        # remaining code in block
        1 } or $state = $old;

It’d be sweet if Perl 6 could allow that kind of thing to operate on the global state instead of a single hash. Sweet indeed, but I don’t know how practically useful.

Continuation-passing style in Perl 5

While I was thinking about my latest perl module, a logic programming framework, I realized that it would be really nice to have continuations. So after going through all the contortions of getting around that limitation using closures, I discovered that it’s possible to use continuation-passing style in Perl:

sub fibo {
    my ($x, $c) = @_; sub {
    if ($x < 2) { sub {
        $c->(1);
    }}
    else { sub {
        fibo($x-1, sub {
        my $f1 = $_[0];
        fibo($x-2, sub {
        my $f2 = $_[0]; sub {
        $c->($f1 + $f2);
    }})})}}}
}

my $next = fibo(10, sub { print "$_[0]\n"; exit });

# kernel
$next = $next->() while 1;

Don’t you just dream of programming like that? It’s scary how reminiscent of LISP that is… (Note that the big slew of braces at the end of fibo() has two closing parentheses in it). If you’re having trouble reading that, you’re not alone. But the basic idea is that each time you call a routine, it does something and then returns what it should do next. You can’t use traditional control structures like while() with this style, but you can get the same behavior by passing continuations around.