FFT based Cross Correlation ?!

Lutz_A_ — Fri, 24 Feb 2006 23:47:39 GMT

Hello,
i would like to know if the ippsCrossCorr function is based on the FFT ?

thanx,
Lutz Altmann

Re: FFT based Cross Correlation ?!

Vladimir_Dudnik — Thu, 16 Mar 2006 04:14:39 GMT

Hi,

as you can see from IPP header file

/* //////////////////////////////// Algorithm /////////////////////////////////////
// Let us examine two variants of cross-correlation:
// a) srcLen1 > srcLen2, for example
// pSrc1 = y0,y1,y2,y3,y4,y5,y6,y7,y8 ( srcLen1 = 9 )
// pSrc2 = x0,x1,x2,x3,x4 ( srcLen2 = 5 )
// lowLag = -8 ( full cross-correlation )
// Output will be as below: _
// x0*y8
// x0*y7+x1*y8 | this part has length = first ( see function ),
// x0*y6+x1*y7+x2*y8 | ownFirstTriangle function is used;
// x0*y5+x1*y6+x2*y7+x3*y8 _/
// x0*y4+x1*y5+x2*y6+x3*y7+x4*y8
// x0*y3+x1*y4+x2*y5+x3*y6+x4*y7 | this part has length = filter ( see function ),
// x0*y2+x1*y3+x2*y4+x3*y5+x4*y6 | ownBackFilter function is used;
// x0*y1+x1*y2+x2*y3+x3*y4+x4*y5_/
// x0*y0+x1*y1+x2*y2+x3*y3+x4*y4
// x1*y0+x2*y1+x3*y2+x4*y3 | this part has length = last ( see function ),
// x2*y0+x3*y1+x4*y2 | ownLastTriangle function is used,
// x3*y0+x4*y1 | note: this part starts from lag = 0;
// x4*y0 _/
//
// b) srcLen1 < srcLen2, for example
// pSrc1 = y0,y1,y2,y3,y4 ( srcLen1 = 5 )
// pSrc2 = x0,x1,x2,x3,x4,x5,x6,x7,x8 ( srcLen2 = 9 )
// lowLag = -4 ( full cross-correlation )
// Output will be as below: _
// x0*y4
// x0*y3+x1*y4 | this part has length = first ( see function ),
// x0*y2+x1*y3+x2*y4 | ownFirstTriangle function is used;
// x0*y1+x1*y2+x2*y3+x3*y4 _/
// x0*y0+x1*y1+x2*y2+x3*y3+x4*y4 note: this part starts from lag = 0,
// x1*y0+x2*y1+x3*y2+x4*y3+x5*y4 | this part has length = filter ( see function ),
// x2*y0+x3*y1+x4*y2+x5*y3+x6*y4 | ownForwFilter function is used;
// x3*y0+x4*y1+x5*y2+x6*y3+x7*y4_/
// x4*y0+x5*y1+x6*y2+x7*y3+x8*y4
// x5*y0+x6*y1+x7*y2+x8*y3 | this part has length = last ( see function ),
// x6*y0+x7*y1+x8*y2 | ownLastTriangle function is used,
// x7*y0+x8*y1 |
// x8*y0 _/
//
// As one can see from (a) and (b) the functions ownFirstTriangle and ownLastTriangle
// are symmetrical, so the same algorithm can be implemented. The same words can be said
// about the functions ownBackFilter and ownForwFilter.
//
// For long enough vectors ( "net" dstLen > IPPSCROSSCORR_START_FFT_USE ) the algorithm
// with FFT is used instead of direct calculations:
// pSrc1 = y0,y1,y2,...,y[n-1], srcLen1 = n,
// pSrc2 = x0,x1,x2,...,x[k-1], srcLen2 = k;
// l = n + k - 1 - full cross-correlation length;
// the order of FFT would be "m" from inequality: l <= 2^m;
// the vectors for transform would be formed as below: ( zero padded )
// y = y0,y1,y2,...,y[n-1],0,0[n+1],...,0[l-1] "0" means zero here;
// x = 0[0],0[1],...,0[n-2],x0,x1,x2,...,x[k-1],0,0,...,0[l-1];
// Y = FFT( y );
// X = FFT( x );
// Z = Y~ * X; (~ means complex conjugate );
// pDst = FFT^(-1)( Z );
////////////////////////////////////////////////////////////////////////////////////// */

#define IPPSCROSSCORR_REAL32f_START_FFT_USE 383
#define IPPSCROSSCORR_REAL64f_START_FFT_USE 511
#define IPPSCROSSCORR_CPLX32fc_START_FFT_USE 255
#define IPPSCROSSCORR_CPLX64fc_START_FFT_USE 511

Regards,
Vladimir

topic Re: FFT based Cross Correlation ?! in Intel® Integrated Performance Primitives

FFT based Cross Correlation ?!

Re: FFT based Cross Correlation ?!