Normalised Cross-correlation FFT

Hi,

I have implemented cross-correlation using FFT's. Is
it possible to to normalised cross-correlation with FFT's?

If so, how? Sorry if it is a basic question - but I haven't
found a solution.

Thanks in advance.. 

On 16 Mar, 13:07, "dlh" <danhordern@n_o_s_p_a_m.hotmail.com> wrote:
> Hi,
>
> I have implemented cross-correlation using FFT's. Is
> it possible to to normalised cross-correlation with FFT's?
>
> If so, how? Sorry if it is a basic question - but I haven't
> found a solution.

Apart from keeping a sharp eye on the various scaling constants
involved in the FFT and correlation estimator, you might want
to scale the input data to unit norm:

xx = x/norm(x);
yy = y/norm(y);

and then compute the correlation between xx and yy.

Rune

On Mar 16, 8:14&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 16 Mar, 13:07, "dlh" <danhordern@n_o_s_p_a_m.hotmail.com> wrote:
>
> > Hi,
>
> > I have implemented cross-correlation using FFT's. Is
> > it possible to to normalised cross-correlation with FFT's?
>
> > If so, how? Sorry if it is a basic question - but I haven't
> > found a solution.
>
> Apart from keeping a sharp eye on the various scaling constants
> involved in the FFT and correlation estimator, you might want
> to scale the input data to unit norm:
>
> xx = x/norm(x);
> yy = y/norm(y);
>
> and then compute the correlation between xx and yy.
>
> Rune

That makes the assumption that all of each signal is involved in the
calculation for each offset.  Often not true.

Dirk

On 16 Mar, 15:13, Dirk Bell <bellda2...@cox.net> wrote:
> On Mar 16, 8:14&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
>
>
>
>
> > On 16 Mar, 13:07, "dlh" <danhordern@n_o_s_p_a_m.hotmail.com> wrote:
>
> > > Hi,
>
> > > I have implemented cross-correlation using FFT's. Is
> > > it possible to to normalised cross-correlation with FFT's?
>
> > > If so, how? Sorry if it is a basic question - but I haven't
> > > found a solution.
>
> > Apart from keeping a sharp eye on the various scaling constants
> > involved in the FFT and correlation estimator, you might want
> > to scale the input data to unit norm:
>
> > xx = x/norm(x);
> > yy = y/norm(y);
>
> > and then compute the correlation between xx and yy.
>
> > Rune
>
> That makes the assumption that all of each signal is involved in the
> calculation for each offset. &#4294967295;Often not true.

Sure. But if you want to use the FFT to compute the normalized
correlation, there aren't too many alternatives.

Rune

On Mar 16, 8:07&#4294967295;am, "dlh" <danhordern@n_o_s_p_a_m.hotmail.com> wrote:
> Hi,
>
> I have implemented cross-correlation using FFT's. Is
> it possible to to normalised cross-correlation with FFT's?
>
> If so, how? Sorry if it is a basic question - but I haven't
> found a solution.
>
> Thanks in advance..

you just encountered one of several limitations of using FFT for CC,
promises so much, then disappointment :)

On Mar 16, 5:07&#4294967295;am, "dlh" <danhordern@n_o_s_p_a_m.hotmail.com> wrote:
> Hi,
>
> I have implemented cross-correlation using FFT's. Is
> it possible to to normalised cross-correlation with FFT's?
>
> If so, how? Sorry if it is a basic question - but I haven't
> found a solution.
>
> Thanks in advance..

For some ideas on what how and why take a look at:

http://www.bksv.com/pdf/Bv0013.pdf
Dual Channel FFT Analysis (Part I)
Technical review No. 1 - 1984
The first part of this article introduces basic dual channel FFT
measurements. The physical interpretation of the Cross Spectrum, which
is the fundamental function in these measurements, and the Coherence
Function are dealt with in some detail. Two different methods for
estimating the complex Frequency Response Function of a system, from
the input and the output signals, are derived, and it is shown which
of the two estimates, H1(f) and H2(f), should be used in different
practical measurement situations. Various excitation techniques for
system analysis are described and their advantages and disadvantages
for specific applications outlined. A number of practical
measurements, using the Br&#4294967295;el & Kj&#4294967295;r Dual Channel Signal Analyzer Type
2032/2034, are presented to illustrate the function estimates obtained
with the different techniques. Part 2 of this article deals with the
applications of the time domain functions, Hilbert Transform and Sound
Intensity.

http://www.bksv.com/pdf/Bv0014.pdf
Dual Channel FFT Analysis (Part II)
Technical review No. 2 - 1984
In the first part of this article the basic dual channel FFT
measurement was introduced and Frequency Response Function estimates
and excitation techniques were discussed. In the second part of this
article the time domain functions, Impulse Response Function,
Autocorrelation and Cross Correlation and their physical
interpretation is dealt with in some detail. The implementation of the
Hilbert Transform on these time domain functions, to compute the
corresponding complex analytical signals, is introduced, and the
advantages of using the magnitude in the presentation of these
functions in some practical situations are illustrated. Calculation of
sound intensity from a dual channel measurement of the sound pressure
signals from two closely spaced microphones is discussed in terms of
advantages and disadvantages. Formulae for random errors on some of
the functions derived from a dual channel measurement on random data
are also given.

Dale B. Dalrymple

On Mar 16, 10:58&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 16 Mar, 15:13, Dirk Bell <bellda2...@cox.net> wrote:
>
>
>
>
>
> > On Mar 16, 8:14&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > On 16 Mar, 13:07, "dlh" <danhordern@n_o_s_p_a_m.hotmail.com> wrote:
>
> > > > Hi,
>
> > > > I have implemented cross-correlation using FFT's. Is
> > > > it possible to to normalised cross-correlation with FFT's?
>
> > > > If so, how? Sorry if it is a basic question - but I haven't
> > > > found a solution.
>
> > > Apart from keeping a sharp eye on the various scaling constants
> > > involved in the FFT and correlation estimator, you might want
> > > to scale the input data to unit norm:
>
> > > xx = x/norm(x);
> > > yy = y/norm(y);
>
> > > and then compute the correlation between xx and yy.
>
> > > Rune
>
> > That makes the assumption that all of each signal is involved in the
> > calculation for each offset. &#4294967295;Often not true.
>
> Sure. But if you want to use the FFT to compute the normalized
> correlation, there aren't too many alternatives.
>
> Rune- Hide quoted text -
>
> - Show quoted text -

It is doable. What part of the caclulation cannot be done with an FFT
(besides divides and square roots)?

Dirk

On 16 Mar, 20:51, Dirk Bell <bellda2...@cox.net> wrote:
> On Mar 16, 10:58&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
>
>
>
>
> > On 16 Mar, 15:13, Dirk Bell <bellda2...@cox.net> wrote:
>
> > > On Mar 16, 8:14&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > > On 16 Mar, 13:07, "dlh" <danhordern@n_o_s_p_a_m.hotmail.com> wrote:
>
> > > > > Hi,
>
> > > > > I have implemented cross-correlation using FFT's. Is
> > > > > it possible to to normalised cross-correlation with FFT's?
>
> > > > > If so, how? Sorry if it is a basic question - but I haven't
> > > > > found a solution.
>
> > > > Apart from keeping a sharp eye on the various scaling constants
> > > > involved in the FFT and correlation estimator, you might want
> > > > to scale the input data to unit norm:
>
> > > > xx = x/norm(x);
> > > > yy = y/norm(y);
>
> > > > and then compute the correlation between xx and yy.
>
> > > > Rune
>
> > > That makes the assumption that all of each signal is involved in the
> > > calculation for each offset. &#4294967295;Often not true.
>
> > Sure. But if you want to use the FFT to compute the normalized
> > correlation, there aren't too many alternatives.
>
> > Rune- Hide quoted text -
>
> > - Show quoted text -
>
> It is doable. What part of the caclulation cannot be done with an FFT
> (besides divides and square roots)?

It depends a bit about the exact specifications of what
one wants to do. One normalized correlation I might
use is a normalized-magnitude matched filter: The output
is +/- 1 if an exact copy of the waveform is found.

The quick description of how I would do that, is to
regard the correlation signal as a sequence of inner
products between the matched FIR filter and frames
from the data sequence. I'd normalize both the FIR
filter and each data frame to magnitude 1. While
the FIR filter can be normalized once and for all,
data must be normalized on a per-frame basis.

The same type of argument can be generalized to
cross correlations.

These types of things can't be computed via FFTs.

Rune

On Mar 16, 2:03=A0pm, Rune Allnor <all...@tele.ntnu.no> wrote:

> On 16 Mar, 20:51, Dirk Bell <bellda2...@cox.net> wrote:
> > ...
> > It is doable. What part of the caclulation cannot be done with an FFT
> > (besides divides and square roots)?...

>
> It depends a bit about the exact specifications of what
> one wants to do....

>
> Rune

The normalized correlation calculated by fft is described in section 3
on page 15 of:

http://www.bksv.com/pdf/Bv0013.pdf
Dual Channel FFT Analysis (Part I)
Technical review No. 1 - 1984

Dale B. Dalrymple

On Mar 16, 7:03=A0pm, dbd <d...@ieee.org> wrote:
> On Mar 16, 2:03=A0pm, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > On 16 Mar, 20:51, Dirk Bell <bellda2...@cox.net> wrote:
> > > ...
> > > It is doable. What part of the caclulation cannot be done with an FFT
> > > (besides divides and square roots)?...
>
> > It depends a bit about the exact specifications of what
> > one wants to do....
>
> > Rune
>
> The normalized correlation calculated by fft is described in section 3
> on page 15 of:
>
> http://www.bksv.com/pdf/Bv0013.pdf
> Dual Channel FFT Analysis (Part I)
> Technical review No. 1 - 1984
>
> Dale B. Dalrymple

Dale,

Interesting reference.  Using FFTs aren't they computing the frequency
dependend coherence function rather than the normalized cross-
correlation?

Dirk