10
$\begingroup$

I'm reading up on Autocorrelation, but I'm not sure I understand exactly how it works and what output I should expect. Am I right in thinking that I should input my signal to the AC function and have a sliding window input. Each window (of 1024 samples, for example) would output a coefficient between -1 and 1. The sign simply states if the line is upwards or downwards and the value states how strong the correlation is. For simplicity, lets say I don't have an overlap and just move the window 1024 samples each time. In a sample of 44100, would I get 43 coefficients and do I need to keep all of them?

Lets say I perform this for a 200 second signal, giving me 8600 coefficients. How would I use these coefficients to detect repetition and, in turn, tempo? Should I create some sort of neural network to group them, or is that overkill?

Thanks for any help.

$\endgroup$
  • 4
    $\begingroup$ Suppose your $1024$ samples are $x[1], x[2], \ldots, x[1024]$. Could you tell us what your AC function returns? Possible answers might be: "It returns $\sum_{i=1}^{1024} (x[i])^2$" or "It returns $1024$ numbers $R[k]$ where $R[k] = \sum_{i=1}^{1024-k}x[i]x[i+k]$" or "It returns $1024$ numbers $R[k]$ where $R[k] = \sum_{i=1}^{1024-k}x[i]x[i+k] + \sum_{i=1}^k x[1024-k+i]x[i]$". All three suggested answers are compatible with the notion of autocorrelation. $\endgroup$ – Dilip Sarwate Oct 9 '11 at 16:34
  • $\begingroup$ Hey Dilip, thanks for the help. I haven't implemented the AC function yet, I'm just trying to get my head around the theory first. The first equation looks to be the easiest but would the data need to be normalised beforehand? $\endgroup$ – XSL Oct 9 '11 at 16:53
  • 1
    $\begingroup$ Here's an example: gist.github.com/255291#L62 $\endgroup$ – endolith Oct 10 '11 at 16:48
23
$\begingroup$

The idea of autocorrelation is to provide a measure of similarity between a signal and itself at a given lag. There are several ways to approach it, but for the purposes of pitch/tempo detection, you can think of it as a search procedure. In other words, you step through the signal sample-by-sample and perform a correlation between your reference window and the lagged window. The correlation at "lag 0" will be the global maximum because you're comparing the reference to a verbatim copy of itself. As you step forward, the correlation will necessarily decrease, but in the case of a periodic signal, at some point it will begin to increase again, then reach a local maximum. The distance between "lag 0" and that first peak gives you an estimate of your pitch/tempo. The way I'm going to describe how to compute it in practice yields something slightly different (i.e. cyclic vs. acyclic mostly), but that's the conceptual basis for how it works.

Computing sample-by-sample correlations can be very computationally expensive at high sample rates, so typically an FFT-based approach is used. Taking the FFT of the segment of interest, multiplying it by its complex conjugate, then taking the inverse FFT will give you the cyclic autocorrelation. In code (using numpy):

freqs = numpy.fft.rfft(signal)
autocorr = numpy.fft.irfft(freqs * numpy.conj(freqs))

The effect will be to decrease the amount of noise in the signal (which is uncorrelated with itself) relative to the periodic components (which are similar to themselves by definition). Repeating the autocorrelation (i.e. conjugate multiplication) before taking the inverse transform will reduce the noise even more. Consider the example of a sine wave mixed with white noise. The following plot shows a 440hz sine wave, the same sine wave "corrupted" by noise, the cyclic autocorrelation of the noisy wave, and the double cyclic autocorrelation:

Autocorrelation

Note how the first peak of both autocorrelation signals is located exactly at end of the first cycle of the original signal. That's the peak you're looking for in order to determine the periodicity (pitch in this case). The first autocorrelation signal is still a little "wiggly", so in order to do peak detection, some kind of smoothing would be required. Autocorrelating twice in the frequency domain accomplishes the same thing (and is relatively fast). Note that by "wiggly", I mean how the signal looks when zoomed way in, not the dip that occurs in the center of the plot. The second half of the cyclic autcorrelation will always be the mirror image of the first half, so that kind of "dip" is typical. Just to be clear about the algorithm, here's what the code would look like:

freqs = numpy.fft.rfft(signal)
auto1 = freqs * numpy.conj(freqs)
auto2 = auto1 * numpy.conj(auto1)
result = numpy.fft.irfft(auto2)

Whether you would need to do more than one autocorrelation depends on how much noise is in the signal.

Of course, there are many subtle variations on this idea, and I'm not going to get into all of them here. The most comprehensive coverage I've seen (in the context of pitch detection) is in Digital Processing of Speech Signals by Rabiner and Schafer.


Now, as to whether autocorrelation will be sufficient for tempo detection. The answer is yes and no. You can get some tempo information (depending on the source signal), but it may be hard to make sense of what it means in all cases. For example, here's a plot of two loops of a breakbeat, followed by a plot of the cyclic autocorrelation of the entire sequence:

Breakbeat Autocorrelation

For reference, here's the corresponding audio:

Sure enough, there's a nice spike right in the middle corresponding to the loop point, but it came from processing quite a long segment. On top of that, if it wasn't an exact copy (e.g. if there were instrumentation with it), that spike wouldn't be as clean. Autocorrelation will definitely be useful in tempo detection, but it probably won't be sufficient by itself for complex source material. For example, even if you find a spike, how do you know whether it's a full measure, or quarter note, a half note, or something else? In this case it's clear enough that it's a full measure, but that won't always be the case. I'd suggest playing around with using AC on simpler signals until the inner workings become clear, then asking another question about tempo detection in general (as it's a "bigger" subject).

$\endgroup$
  • 2
    $\begingroup$ Hang on, is that the autocorrelation of the audio signal itself? That's certainly not very useful for tempo detection of anything but digital loops. The autocorrelation of some RMS envelope should work much better in general, preferrably for multiple frequency bands seperately. $\endgroup$ – leftaroundabout Oct 10 '11 at 12:55
  • 1
    $\begingroup$ Autocorrelation of the STFT in the time direction works pretty well, as long as the music has some kind of beat. This is essentially the same as running autocorrelation of lots of frequency bands and then summing them together. $\endgroup$ – endolith Oct 10 '11 at 16:51
  • 2
    $\begingroup$ @leftroundabout Right, there are any number of things that would need to be done for tempo detection (pre, post processing) besides autocorrelation by itself. I'm mainly responding to the first sentence of the OP's question (i.e. "how does autocorrelation work"), then suggesting he ask another question about tempo detection, beacause other processes will be involved. $\endgroup$ – datageist Oct 10 '11 at 17:25
  • $\begingroup$ @endolith what do you mean here by Autocorrelation of the STFT in the time direction? Specifically the time direction part $\endgroup$ – popctrl Mar 11 at 16:16
  • 1
    $\begingroup$ @popctrl Meaning to calculate the autocorrelation of each row of the STFT $\endgroup$ – endolith Mar 11 at 17:27
3
$\begingroup$

Sounds like you want to use autocorrelation to do beat detection. You can do this, but I suggest you massively downsample your audio. You're looking for a signal between 1 and 3 Hz (60 bpm to 180 bpm) so you don't need or want 44100 hz resolution. A properly computed and normalized autocorrelation is 1.0 at lag 0 (the signal perfectly correlates with itself). For a periodic signal, the ac drops below zero, then comes back up in a peak at the lag corresponding to the fundamental frequency, with smaller peaks at harmonics. You must pick a reasonable range in which to search for this peak. For noise, the autocorrelation drops and basically flatlines in squiggles around zero. As a rule of thumb, if you have a peak > 0.5 in the normalized ac, you have a periodic signal.

$\endgroup$
1
$\begingroup$

The auto correlation is simply the cross correlation of a signal with itself. An easy way to compute it is to do a convolution between the original signal and a time flipped version of the signal. If you have a signal that is 1000 samples long, than its auto correlation has 1999 (2*N-1) non-zero samples. Only 1000 of those samples are unique because the auto correlation (for a real signal) is always symmetric in time, i.e. ac[n] = ac[-n].

Continuous signals need to be broken down into finite segments. That is similar to the Fourier Transform: technically you need to integrate from -inf to +inf but breaking it down into segments (with overlap and/or windowing as needed) also yields useful results. Choice of window length, shape and overlap depends on the application.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.