Forums

Normalised Cross-correlation FFT

Started by dlh March 16, 2010
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&#2013266080;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&#2013266080;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. &#2013266080;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&#2013266080;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&#2013266080;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&#2013266172;el & Kj&#2013265926;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&#2013266080;am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 16 Mar, 15:13, Dirk Bell <bellda2...@cox.net> wrote: > > > > > > > On Mar 16, 8:14&#2013266080;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. &#2013266080;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&#2013266080;am, Rune Allnor <all...@tele.ntnu.no> wrote: > > > > > > > On 16 Mar, 15:13, Dirk Bell <bellda2...@cox.net> wrote: > > > > On Mar 16, 8:14&#2013266080;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. &#2013266080;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