Correlation using FFT

"Mark Borgerding" <markab@xetron.com> wrote in message
news:413871c0$1@news.xetron.com...
> Tom wrote:
> > If you don't put in the (1-beta) part then you get an offset ie you have
to
> > re-scale afterwards to get the right
> > answer.
>
> On the contrary, it is impossible to get the right answer if you DO put
> in the 1-beta part.
>
> ... if the question being answered is the one the original poster asked:
> how to correlate two sequences using the fft.
>
> Or perhaps I am also guilty of assuming too much.   Perhaps the OP
> wanted the single-valued correlation : cov(x,y) / sqrt( var(x)*var(y) )
> But I don't think so.  Covariance and variance operations are already
> linear complexity.  I can't see how FFTs would make them any faster.
> I'm pretty sure the OP wanted cross-correlation when he asked for
> correlation.
>
> There is a very specific definition for cross-correlation.
> See http://mathworld.wolfram.com/Cross-Correlation.html
> or http://cnx.rice.edu/content/m10686/latest/
> Notice the pure integration and infinite bounds.
>
> The formula you posted may have uses for continuous (open loop)
> processing, but it is NOT cross-correlation.
>
> I can only assume the question for your "right answer" is "how do I get
> a time-decaying approximation of cross-correlation".  That question was
> never asked.  You made a good suggestion that was certainly topical,
> considering more people read a thread than just the few persons writing
> it. But the OP had signals "up to 45 seconds long", far from infinite.
>
> -- Mark
> ]

It is certainly Cross Correlation. In fact the method is more general (with
modification) - I mentioned the Hannan-Thomson algorithm and the SCOT method
for instance.
In its simpler form it is just the Wiener-Kinchen theorem ie the Fourier
Transform  of cross-corr is power spectral density.
The basic idea is found here
http://www.paper.edu.cn/scholar/known/qiutianshuang/qiutianshuang-1.pdf

though it is much older.

You are confusing the pure integration in smoothing the cross-periodograms
with the pure integration of getting a Cross-Corr (as you point out). The
method I quoted is only to smooth the cross periodogram (PSD estimate).You
don't need pure integration as this happens when you do an inverse FFT ie
the Wiener Kinchen theorem again.
In fact you don't need to smooth the cross-periodograms at all but you would
get quite a noisy estimate.
Also ordinary cross-corr whether you do it in the freq domain or the
ordinary method has drawbacks with certain problems - particulalry
estimating time-delays (or multple time-delays) and this is why generalised
cross-corr is necessary.

Hope this helps you to understand.

Tom

Mark Borgerding wrote:

...
> never asked.  You made a good suggestion that was certainly
> topical, considering more people read a thread than just the few
> persons writing it. But the OP had signals "up to 45 seconds
> long", far from infinite.
> 
> -- Mark

I'm one other reading the thread...
maybe my contribution is far off the original goal of the OP.

Just to satisfy my interest (and enhance my knowledge...), I would 
like to put in two more general questions:

1) given two such signals of 45 seconds, which are equal.
   now cut 5s from the beginning of the first and paste it to the 
end of it .
  then correlating this modified signal with the other unmodified.
  I reckon that the frequency content is the same except on the 
borders where the signal has been cut/pasted.
  Therefore I would expect similar FFT results and probably a high 
degree of correlation. 
  My question: does correlation detect the shift of most of the 
signal and show good correlation?
  Or would the result be a low correlation because signal contents 
don't match at any point?

2) Given, I want to compare a signal (endless stream) with a certain 
pattern (short piece of signal).
I expect that the signal contains pieces which are similar to the 
pattern, but differ either 
* in amplitude or 
* in width or 
* in both.
Which method would be chosen to find the occurrences?
Is cross-correlation the right approach?
Or will it fail in one of the cases?

Remember: it's not a current task which bothers me,
it's only that I'm curious 
(maybe I'll need the answer soon, nevertheless ...)
so it's enough to give me a direction.

Bernhard 

Mark Borgerding wrote:

>> 2) Given, I want to compare a signal (endless stream) with a
>> certain pattern (short piece of signal).
>> I expect that the signal contains pieces which are similar to the
>> pattern, but differ either
>> * in amplitude or
>> * in width or
>> * in both.
>> Which method would be chosen to find the occurrences?
>> Is cross-correlation the right approach?
>> Or will it fail in one of the cases?
> 
> This is close to case b) above.
> 
> Caveat on "width": Cross-correlation will not "stretch" a pattern
> to
> find a match.  If a feature is "stretched", while keeping its
> shape, its frequency spectrum is shifted.
> 
> Perhaps there is a cepstral technique that could accomplish this
> task.
> 

Thanks for taking the challenge.

Measuring the correlation with such a normalized pattern will 
probably be a future task, so I'm really interested in any ideas.

What I bear in mind to solve this task has grown from the wavelet 
theory, and your response reminds me of that:

If I generate a series of related patterns which differ only in 
width (time), sort of correlation with every pattern should bring 
up a vector which gives me a "best fit" result.

Instead of working with generic sine and/or cosine signals which 
would certainly lead to something like FFT, it seems as if this 
were more a task for wavelet transform, which uses short patterns.

Currently, I have no idea which would be the best approach, not 
even, if the results would be acceptable for a real application, 
just looking around ...

Bernhard

  

Bernhard Holzmayer wrote:
> Mark Borgerding wrote:
> I'm one other reading the thread...
> maybe my contribution is far off the original goal of the OP.

You raise some good points.  Ones that should've been addressed early on.

In hand-waving terms, cross-correlation can be applied to
a) two short signals,
b) one long + one short, or
c) two long signals

For the first two scenarios, it is feasible to compute the 
cross-correlation in its entirety. The last scenario is basically 
defined as one where it is impractical to calculate the entire CC 
sequence.  The latter case is what I've been talking about.

For a), you can transform both signals into the frequency domain by zero 
padded ffts (length >= N+M-1), then conjugate multiply their spectral 
components to affect cross-correlation in the time domain.

Note cross-correlation is is just time-reverse, conjugate convolution. 
Also note multiplication in the freq domain <==> conv in time D.
Also^2 note conjugate in the freq D is time reversal and conjugation in 
time D.

To apply this idea back to the original poster: To cross-correlate two 
audio signals of 45s at 44kS/s, ( roughly 2e6 samples each), an FFT of 
4e6 points would be needed.  Probably feasible for the OP's purpose.  I 
probably should've suggested this straightaway due to its simplicity.
tic;
nf = ng = 2e6;
nfft=2^nextpow2(nf+ng-1);
f=randn(nf,1);
g=randn(ng,1);
F=fft(f,nfft);
G=fft(g,nfft);
cc=ifft( F.*conj(G) ); % time-shifted cross-correlation
toc

It took less than 30s on my computer.  Sorry rg.


Anyway ...

For b), you can extend the above solution to work in a buffer-by-buffer 
case by applying overlap-add or overlap-save filtering, with the shorter 
sequence reversed and conjugated.


For case c), it is impractical to compute the entire non-zero 
cross-correlation sequence. It is easy to calculate only a range of 
delay(aka lag) values.
This is where the matlab script I posted earlier comes into play.
It performs blockwise computation of only those cross-correlation values 
of interest.  It postpones the ifft until an answer is needed by 
exploting the identity f + g <==> F + G.


> Just to satisfy my interest (and enhance my knowledge...), I would 
> like to put in two more general questions:
> 
> 1) given two such signals of 45 seconds, which are equal.
>    now cut 5s from the beginning of the first and paste it to the 
> end of it .
>   then correlating this modified signal with the other unmodified.
>   I reckon that the frequency content is the same except on the 
> borders where the signal has been cut/pasted.
>   Therefore I would expect similar FFT results and probably a high 
> degree of correlation. 
Yes. In fact for this case, they two would vary only in phase, |F1| == |F2|

There would be a linear phase shift in the frequency domain 
corresponding to the constant time shift in the time domain.
(Think about linear phase(AKA constant group delay) FIR filters)

>   My question: does correlation detect the shift of most of the 
> signal and show good correlation?
>   Or would the result be a low correlation because signal contents 
> don't match at any point?

The cross-correlation sequence would be large and positive at the lag 
where t = 5s

The CC seq is maximized when the two sequences have matching spectral 
phase components that match (linear scaling of either only affects the 
magnitude, of the CC).

> 
> 2) Given, I want to compare a signal (endless stream) with a certain 
> pattern (short piece of signal).
> I expect that the signal contains pieces which are similar to the 
> pattern, but differ either 
> * in amplitude or 
> * in width or 
> * in both.
> Which method would be chosen to find the occurrences?
> Is cross-correlation the right approach?
> Or will it fail in one of the cases?

This is close to case b) above.

Caveat on "width": Cross-correlation will not "stretch" a pattern to 
find a match.  If a feature is "stretched", while keeping its shape, its 
frequency spectrum is shifted.

Perhaps there is a cepstral technique that could accomplish this task.

> 
> Remember: it's not a current task which bothers me,
> it's only that I'm curious 
> (maybe I'll need the answer soon, nevertheless ...)
> so it's enough to give me a direction.
> 
> Bernhard 

I hope I helped.

-- Mark