On Jan 25, 2011, at 7:34 PM, Jan Baumgart wrote:
When the two signal portions are alike, they are strongly correlated
- so you get a maximum value for the correlation.
If they have nothing in common you get a correlation value near
zero.\
he said he was using periodic function generation.
For pitch detection you look for maxima in the auto-correlation.
yup, if P is the period (or *a* period - there is the octave
problem), then
x[n+P] = x[n] + something very small
or
something very small = x[n+P] - x[n]
or, making this error always positive
|something very small| = |x[n+P] - x[n]| (AMDF)
or
(something very small)^2 = (x[n+P] - x[n])^2 (ASDF)
Sum that up over n should result in something else quite small, if the
offset i is equal to (or very close to) P. that's where the AMDF or
ASDF get their answer.
for a very wide window (the size parameter), the ASDF can be shown
to be related to the autocorrelation. in fact, it's the
autocorrelation upside-down, so that when the ASDF is at a minimum,
the autocorrelation is maximum.
SUM{ (x[n+i] - x[n])^2 } = SUM{ (x[n+i])^2 + (x[n])^2 - 2*x[n
+i]*x[n] }
= SUM{ (x[n+i])^2 } + SUM{ (x[n])^2 } - 2*SUM{ x[n
+i]*x[n] }
the first two summations sum to roughly the same thing (so the first
summation isn't radically different for different i) which is a
measure of the power or signal energy. the last summation is your
autocorrelation which does depend on i a lot. so this is approximately
true:
(1/2)*SUM{ (x[n+i] - x[n])^2 } = SUM{ (x[n])^2 } - SUM{ x[n
+i]*x[n] }
Q[i]=R[0] -R[i]
or
SUM{ x[n+i]*x[n] } = SUM{ (x[n])^2 } - (1/2)*SUM{ (x[n+i] -
x[n])^2 }
R[i] = R[0]-Q[i]
this would be exactly true if the summations where infinite, but the
summations are finite, so this is only approximately true. one thing
that can be said, even for the approximation, is that Q[0] = 0 which
is when i=0, R[i] = R[0].
but, given the definition with a finite sum (and the approximation for
R[i]), you actually don't know that that R[0] is at a maximum. but it
should be close to a maximum. so find the maximum of R[i] around i=0
and when you find your other maximum (perhaps around i=P), then the
difference in location of those two peaks should be your period, P.
think of this autocorrelation
R[i] = SUM{ x[n+i]*x[n] } = SUM{ h[i-n]*x[n] }
as an FIR with this hypothetical impulse response h[n] = x[-n] (it's
a time-reversed copy of the fixed leg of x[n] in your summation). the
output of your autocorrelator is like that of an FIR filter. if a
periodic x[n] (with period P) goes in, then a periodic R[n] comes out,
with the same period, P. but that R[n] should have a peak around n=0,
because it's sorta-kinda like a true autocorrelation. so the next
peak should be P samples away from the peak around n=0 (but not
necessarily exact on 0).
There's also the other way you mention, taking the difference. This
is used in AMDF for example. In that case you look for minima.
yup, what he said.
--
r b-j r...@audioimagination.com
Imagination is more important than knowledge.
On 1/25/11 11:46 PM, Veronica Merryfield wrote:
I'm trying to understand autocorrelation as related to some pitch
detection algorithms I've been looking at.
In example code for the autocorrelation, it is the summation of a
sample at indexes multiplied by a sample at indexes plus an offset.
eg
for (i=0;isize;i++)
{
sum=0;
for (j=0;jsize;j++)
{
sum+=x[j]*x[j+i];
}
R[i]=sum;
}
When I graph this (R[i]) in a spreadsheet for various offsets, I do
not get a minima as expected when the samples match (I have tried
with a couple of generated periodic waves).
However, if I use the summation of the differences I do get the
minima as expected.
What am I missing?
Veronica
--
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
