On Dec 2, 2010, at 7:52 AM, Stefan Stenzel wrote:
Now I wonder, am I the only one to calculate ACF using FFT?
the version of ACF that you calculate using the FFT is
Rv[tau] = SUM{ v[n]*v[n+tau] }
where
v[n] = x[n]*w[n] where w[n] is a window function,
supposedly much wider than any period of x[n].
this results in an ACF for x[n] that approximates as
Rx[tau] ~= Rv[tau] = SUM{ x[n]*w[n] * x[n+tau]*w[n+tau] }
if P is a period for your input x[n], then x[n+P] = x[n] for all n.
at lags that are integer multiples of that period
Rv[m*P] = SUM{ x[n]*x[n+m*P] * w[n]*w[n+m*P] }
= SUM{ x[n]*x[n] * w[n]*w[n+m*P] }
note that
Rv[0] = SUM{ x[n]*x[n] * w[n]*w[n] }
the partially overlapped windows w[n]*w[n+m*P] sum to less than the
fully overlapped window w[n]*w[n], so Rv[m*P] will sum to something
less than Rv[0]. that something less is like an envelope on the ACF
that you are looking for. even for a perfectly periodic x[n], the
peaks in your ACF do not reach the height of Rx[0]. to within a
scaling factor
Rv[m*P] = Rv[0] * Rw[m*P] where
Rw[tau] = SUM{ w[n]*w[n+tau] }
so that leads me to two questions for you, Stefan:
i presume that you find peaks that are reduced by that envelope.
1. how do you discriminate between peaks that are unequally weighted
by that envelope? which peak do you pick?
2. for a real-time operation, what kind of delay are you dealing
with? you must input in your buffer, window it, pass that to the FFT,
magnitude square, and iFFT before you see your ACF (with an
envelope)? even with an infinitely fast computer, you still have the
delay of filling the entire buffer.
for comparison, with a time-domain ACF, you can calculate R[tau] for
increasing lags on the fly as more audio data comes in. you can
always correlate the most current slice of audio against a slice of
audio fixed farther in the past. as time goes on, the lag difference
increases until you are done with this particular ACF and you start
over.
Regarding seamless loops, I found that quantizing frequencies
to integer numbers of periods in the loop works extremely well.
that's the whole point to using the ACF (or AMDF) in splicing audio
for loops in samplers or loops in real-time pitch shifters. the only
way to get *all* frequencies present to displace an integer number of
periods, is for the data to have some periodicity. if you choose 2
periods of the fundamental, the same displacement is 4 periods of the
2nd harmonic and 6 periods of the 3rd harmonic. if it's not quasi-
periodic, your ACF (or AMDF) will not give you good candidates, so you
pick the best candidate you can, take the glitch that results, and
consider whether frequency-domain shifting or time-scaling is better.
--
r b-j r...@audioimagination.com
"Imagination is more important than knowledge."
--
dupswapdrop -- the music-dsp mailing list and website:
subscription info, FAQ, source code archive, list archive, book reviews, dsp
links
http://music.columbia.edu/cmc/music-dsp
http://music.columbia.edu/mailman/listinfo/music-dsp
