[linux-audio-dev] for the interested: a simple algorithm for loop length correction / automatic sync / BPM calculation

New Message Reply About this list Date view Thread view Subject view Author view Other groups

Subject: [linux-audio-dev] for the interested: a simple algorithm for loop length correction / automatic sync / BPM calculation
From: Pieter Palmers (pieter.palmers_AT_student.kuleuven.ac.be)
Date: Wed Jan 15 2003 - 22:48:51 EET


Hi,

I conceived this increadably simple algorithm some time ago, while studying
for an exam. (you know how easy it is to get distracted ;)
Chances are that it's already 'invented' before, because it's just too simple
not to. It's closely related to the sync procedure of wireless digital
communication systems (like WLAN).

I thought it might be handy for any writer of DJ apps or audio/sample editors.
Use it as you wish. It's written in Matlab, and uses the high level functions
available in this environment. Actual C/C++/... implementation would require
an implementation for these functions too, but those are not hard to find.
It's sole purpose is to present the idea behind it, and prove it works.

greets

Pieter Palmers

PS: Should the idea of applying this to music & audio be new, I hereby claim
the 'invention' of this and explicitly post this as public domain. No patents
for this one. (such statements are ridiculous aren't they? I feel like a
complete idiot stating this. But you never know... the EVO sampler case
learned me that it doesn't hurt to explicitely state these things)

% ccdetect.m
% Pieter Palmers
% pieterpalmers at users.sourceforge.net
% --------------------------------------------------------------------------
% License: use it as you please. Public domain.
% --------------------------------------------------------------------------
% Algorithm to correct the loop length if begin & endpoints aren't
% accurate. Also detect tempo based on loop length
%
% Arguments:
% x0,x1: begin & end marks, relative to the begin of 'testdata'
% testdata: an array with the sound piece to work upon. Mono.
%
% more vars are defined as constants, but could as well be arguments
%
% precondition: x1 > x0
% L/2 < x0 < length(data)-L/2
% L/2 < x1 < length(data)-L/2
% remark: no arguments are tested for correctness.
%
%
% Description:
% The idea is that a user marks a begin and an end point for a loop within
% a song, eg by tapping, or by selecting a part of the waveform in an
% editor. The algorithm then selects two sections of length L+1, one at the
% loop start point, and one at the loop end point. Both sections are centered
% on the markers, ie they have L/2 samples before the marker and L/2 samples
% after the marker.
% The next step is to compute the crosscorrelation of the two segments (seg0 &
seg1).
% The maximum in the crosscorrelation matrix is then detected, and it's index
is
% extracted. This index is the amount of samples a section needs to be shifted
% to let the two sections mach as good as possible.
%
% I have tested this with several sorts of music, and I hav to say that it
works
% quite good. Especially on music with a strong tempo it's effective. And the
% computational complexity isn't very large if the window size is small.
% Using dance music, it's possible to extract good tempo with L=500 or so.
% Using rock music with strong tempo also needs L=500.
% When using dance music with L=1024 the calculated tempo was correct up to
% 0.01BPM. Even if the markers where displaced 400 samples, the algorithme
still
% gave the correct result.
%
% Needless to say that the better the markers are the better the correction
is,
% although the algorithm seems relatively insensitive to the marker positions.
% Also note that for the algorithm to work, the markers must be within L/2
samples
% of the 'correct' values. When using L=500 at 22050Hz this comes down to
10ms.
% It might be better to use a higher L or a lower samplerate, in order to make
this
% requirement upon the user a little less hard.
% Note that L is a function of the sample rate, because the 'tracking'
capability
% is dependant on the absolute (real) time. So if the samplerate is doubled, L
has
% to be doubled too (for the same tracking capability).
%
% Also note that the algorithm works by detecting the 'similarity' between
beginning
% and end of a loop, so there has to some in order for it to work.
%
% Crosscorrelation computational complexity: (approx)
% L*(L+1) multiply-accumulate operations
% when using the most naïve implementation (mirror & slide)
% (note that I'm not sure, I have to look this up)
% for L=500 this is 250500
% More efficient implementations exist.
% When using this matlab code on an Athlon TBird 1200 it takes about 0.1 sec
for
% L=4096.
%
% Shortcommings:
% Only the loop length is adjusted, not the loop start point.
%

L=4096; % window length
samplerate=22050;
NbBeats = 1 % number of beats in the loop

looplength=x1-x0; % in samples

% extract a segment of length L centered round position xi from the data
seg0=testdata(x0-L/2:x0+L/2);
seg1=testdata(x1-L/2:x1+L/2);

% perform the crosscorrelation between the two segments
[XCF, Lags, Bounds]=crosscorr(seg0,seg1,length(seg0)-1);

% take the absolute value of the crosscorrelation, because this is a complex
domain
% operation
XCFa=abs(XCF);

% find the maximum value of the crosscorrelation (maxval)
% and the position where to find it in the array (maxpos)
[maxval,maxpos]=max(XCFa);

% calculate the relative displacement of seg0 to seg1
% interpretation: shift seg0 for reldispl samples forward in time
% to obtain the best match. (backward if reldispl<0)
reldispl = maxpos-round(length(XCFa)/2);

% correct the loop length
corr_looplength=x1-(x0-reldispl);

% calculate the tempo
beatspersecond=NbBeats/(corr_looplength/samplerate);
beatsperminute=beatspersecond*60;

% output some values
disp(['Window length (samples): ', int2str(L)]);
disp(['Window length (seconds): ', num2str(L/samplerate)]);

disp(['Loop length (samples): ', int2str(looplength)]);
disp(['Loop length (seconds): ', num2str(looplength/samplerate)]);

disp(['Relative displacement (samples): ', int2str(reldispl)]);
disp(['Relative displacement (seconds): ', num2str(reldispl/samplerate)]);

disp(['Corrected loop length (samples): ', int2str(corr_looplength)]);
disp(['Corrected loop length (seconds): ',
num2str(corr_looplength/samplerate)]);

disp(['Tempo (beats/second): ', num2str(beatspersecond)]);
disp(['Tempo (beats/minute): ', num2str(beatsperminute)]);

% plot the results
figure(3);
% this plots the crosscorrelation values in funtion of the time lag applied
plot(Lags,XCFa);

figure(4);
xaxis=[1:length(seg0)];

% plot the begin of seg0 (uncorrected)
subplot(3,1,1);
plot([L/4:3*L/4],seg0(L/4:3*L/4));

% plot the begin of seg1 (uncorrected)
subplot(3,1,2);
plot([L/4:3*L/4],seg1(L/4:3*L/4));

% plot the begin of seg0 after correction
subplot(3,1,3);
plot([L/4:3*L/4],seg0(L/4-reldispl:3*L/4-reldispl));


New Message Reply About this list Date view Thread view Subject view Author view Other groups

This archive was generated by hypermail 2b28 : Wed Jan 15 2003 - 22:47:22 EET