[music-dsp] AMDF shortcuts for SOLA time stretching?

[Ross Bencina]

Hi Guys

Mmmm, lots of tasty acronyms today :-)

I've been playing around with some textbook overlap-add timestretching 
algorithms over the weekend (DAFX textbook). SOLA for example slightly 
shifts time segments to try to maximise cross-correlation (minimise AMDF) 
around the crossfade region. I'm looking for good ways to compute the 
location of the correlation maxima or equivalently, the Average Magnitude 
Difference Function (AMDF) minima without having to evaluate the function at 
every possible time lag.

I remember seeing somewhere an attempt to speed up the correlation 
computation by only comparing offsets local to regions where the signals 
shared zero crossings. I'm wondering if other techniques like this have been 
proposed/studied?. Perhaps I'm just missing the right google terms.. So far 
I've looked at quite a lot of F0 estimation papers and some Time Delay 
Estimation stuff... most work seems to look at improving accuracy rather 
than reducing complexity.

I'm thinking of things like:

- performing correlation on decimated signals to find regions of interest 
before considering every sample

- doing some kind of adaptive search of the space of potential lag offsets

- computing some kind of simplified representation of the signal. Such as 
reducing it to a chain of splines with only zerocrossings and maxima/minima 
between zero crossings positioned correctly, and then somehow analyitically 
compute the best correlation on those.

I guess I'm thinking about both fast heuristics which trade speed for 
accuracy, and optimisations which have little/no error.

Any thoughts/suggestions gratefully received..

Best wishes

Ross.