Xref: utzoo comp.dsp:403 comp.graphics:9089 sci.math:9101
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uunet!portal!cup.portal.com!JDurand
From: JDurand@cup.portal.com (Gerald Joseph Durand)
Newsgroups: comp.dsp,comp.graphics,sci.math
Subject: Re: Correlation and FFT
Message-ID: <25475@cup.portal.com>
Date: 29 Dec 89 09:34:02 GMT
References: <8108@ingr.com>
Distribution: usa
Organization: The Portal System (TM)
Lines: 60

>Hello World!, Signal/Image Proc. Programmers or Simply Hackers!

>I ask your favor to solve a well-known problem in the signal/image 
>processing fields.  I want to compute the correlation of two signals 
using the Fourier Transform.  The two discrete signals are as follows:
> 
>	f(n) = {1,1,1,1,2,2,2,2,8,8,8,8,9,9,9,9},    n=0,1,....,15.
>	h(n) = {1,2}				     n=0,1.
>
>The result should have the highest correlation coefficients at 1,2 and 
>8,9 transitions.  In other words I want to do a pattern matching using FFT.
>I was able to get the expected results in the spatial domain, but not in
>the frequency domain. I haven't figured out the normalization steps to take
>care of the scale changes when I used the FFT.  
>Note that the lengths of the two signals are not the same, but we can 
>assume that they are a power of two. I've never posted a news before.
>You're more than welcome to call me if you have answers, questions and 
>problems.
>
>Thanks in advance.
>
>Name:	Youngsup Kim 
>Phone:	1-800-633-7207, 1-205-772-1999 USA
>mail: 	kimy@ingr.com 			
>	b15!ysk!youngsup@ingr.com		

                       Hi Kim
                       ------

    You may be helped by the following reference book

    "Multidimensional Digital Signal Processing"

    by DAN E. DUDGEON  & RUSSEL M. MERSEREAU

                PRENTICE-HALL 1984



                thank you Jerry Durand.

    	This routine simply calls the one-dimensional forward FFT after
	it conjugates and scales the input array.

	The size of the input array or the number of point to compute
	should be a power of 2.
	The input is scaled down by n.
	Also it assumes that n = 2**ln (NO checking will be done).
	The output is overwritten on the input or this is in-place
	operation.

Bug:	

History:
	11/1/89:	YSK	Initial implementation
\*-----------------------------------------------------------------------*/


int FFT_inverse (me, n, ln)
IM_p_CMPLX 	me;	/* input one-dimensional array			*/