hi I have written a program that performs correlation via FFT. The concept is to search a base image for occurrences of a particular shape. To do this first I took the FFT of the base image, then FFT of the shape (padded with zeros) which I want to search in the base Image. After this I got 4 arrays of real and imaginary data. Next I multiplied the array (real & imaginary) of the shape with the array of the base image and took its IFFT. Finally, after IFFT i got two arrays (real & imaginary), next I squared and added both the arrays (the real and the imaginary) and took its square root. As expected, the result should be that I should get a sharp clear peak. But in fact I get a noisy image. Please correct me if the above procedure is incorrect. I think if there would have been any problem in my FFT & IFFT routine then I should have not got my base image back, once I have performed a FFT on it and then did a IFFT. If anyone has the desire to take a look of my FFT correlation results I'd really appreciate it. Base image: http://testftpc.awardspace.com/fft/LENA.bmp FFT performed on base image: http://testftpc.awardspace.com/fft/(FFT)LENA.bmp IFFT performed on base image: http://testftpc.awardspace.com/fft/(I)LENA.bmp Target shape: http://testftpc.awardspace.com/fft/ll.bmp Correlation Result: http://testftpc.awardspace.com/fft/CORR.bmp FFT & IFFT routine: http://testftpc.awardspace.com/fft/fft_ifft.txt Convolution routine: http://testftpc.awardspace.com/fft/CORRELATION.txt Thanks very much in advance, Mickey
Image correlation via FFT. Not working, need help
Started by ●September 1, 2008
Reply by ●September 2, 20082008-09-02
On Sep 1, 9:56�am, "devil6600" <devil6...@gmail.com> wrote:> hi > > I have written a program that performs correlation via FFT. The concept is > to search a base image for occurrences of a particular shape. To do this > first I took the FFT of the base image, then FFT of the shape (padded with > zeros) which I want to search in the base Image. After this I got 4 arrays > of real and imaginary data. Next I multiplied the array (real & imaginary) > of the shape with the array of the base image and took its IFFT. Finally, > after IFFT i got two arrays (real & imaginary), next I squared and added > both the arrays (the real and the imaginary) and took its square root. > As expected, the result should be that I should get a sharp clear peak. > But in fact I get a noisy image. Please correct me if the above procedure > is incorrect. > > I think if there would have been any problem in my FFT & IFFT routine then > I should have not got my base image back, once I have performed a FFT on it > and then did a IFFT. > > If anyone has the desire to take a look of my FFT correlation results I'd > really appreciate it. > > Base image:http://testftpc.awardspace.com/fft/LENA.bmp > > FFT performed on base image:http://testftpc.awardspace.com/fft/(FFT)LENA.bmp > > IFFT performed on base image:http://testftpc.awardspace.com/fft/(I)LENA.bmp > > Target shape:http://testftpc.awardspace.com/fft/ll.bmp > > Correlation Result:http://testftpc.awardspace.com/fft/CORR.bmp > > FFT & IFFT routine:http://testftpc.awardspace.com/fft/fft_ifft.txt > > Convolution routine:http://testftpc.awardspace.com/fft/CORRELATION.txt > > Thanks very much in advance, > > MickeyI didn't check your links, but from your description it seems as if you're doing the convolution of your image and base image (or template). To do a cross correlation, you've got to conjugate one of them in the frequency domain before doing the multiplication. The conjugation performs a 'time reversal' in the frequency domain (look at the time domain equations for both convolution and cross correaltion - the sign is different). And it makes a difference as to which transform you conjugate. In your case, since you're doing template matching, you'd conjugate the FFT result of your base image before doing the multiplication of the 2 transforms (if you were doing cross correaltion for motion detection, it'd be a different story). So try conjugating the FFT results of your zero padded base image (change signs of all imaginary parts: i[n] = - i[n]). Then multipy the 2 transforms and inverse FFT.
Reply by ●September 2, 20082008-09-02
On Sep 2, 12:34�am, kevinjmc...@netscape.net wrote:> On Sep 1, 9:56�am, "devil6600" <devil6...@gmail.com> wrote: > > > > > > > hi > > > I have written a program that performs correlation via FFT. The concept is > > to search a base image for occurrences of a particular shape. To do this > > first I took the FFT of the base image, then FFT of the shape (padded with > > zeros) which I want to search in the base Image. After this I got 4 arrays > > of real and imaginary data. Next I multiplied the array (real & imaginary) > > of the shape with the array of the base image and took its IFFT. Finally, > > after IFFT i got two arrays (real & imaginary), next I squared and added > > both the arrays (the real and the imaginary) and took its square root. > > As expected, the result should be that I should get a sharp clear peak. > > But in fact I get a noisy image. Please correct me if the above procedure > > is incorrect. > > > I think if there would have been any problem in my FFT & IFFT routine then > > I should have not got my base image back, once I have performed a FFT on it > > and then did a IFFT. > > > If anyone has the desire to take a look of my FFT correlation results I'd > > really appreciate it. > > > Base image:http://testftpc.awardspace.com/fft/LENA.bmp > > > FFT performed on base image:http://testftpc.awardspace.com/fft/(FFT)LENA.bmp > > > IFFT performed on base image:http://testftpc.awardspace.com/fft/(I)LENA.bmp > > > Target shape:http://testftpc.awardspace.com/fft/ll.bmp > > > Correlation Result:http://testftpc.awardspace.com/fft/CORR.bmp > > > FFT & IFFT routine:http://testftpc.awardspace.com/fft/fft_ifft.txt > > > Convolution routine:http://testftpc.awardspace.com/fft/CORRELATION.txt > > > Thanks very much in advance, > > > Mickey > > I didn't check your links, but from your description it seems as if > you're doing the convolution of your image and base image (or > template). �To do a cross correlation, you've got to conjugate one of > them in the frequency domain before doing the multiplication. �The > conjugation performs a 'time reversal' in the frequency domain (look > at the time domain equations for both convolution and cross > correaltion - the sign is different). > > And it makes a difference as to which transform you conjugate. �In > your case, since you're doing template matching, you'd conjugate the > FFT result of your base image before doing the multiplication of the 2 > transforms (if you were doing cross correaltion for motion detection, > it'd be a different story). > > So try conjugating the FFT results of your zero padded base image > (change signs of all imaginary parts: i[n] = - i[n]). �Then multipy > the 2 transforms and inverse FFT.- Hide quoted text - > > - Show quoted text -Ooops. Meant to say: conjugate the FFT results of your zero padded shape image in that last paragraph.
Reply by ●September 2, 20082008-09-02
On Sep 2, 12:42�am, kevinjmc...@netscape.net wrote:> On Sep 2, 12:34�am, kevinjmc...@netscape.net wrote: > > > > > > > On Sep 1, 9:56�am, "devil6600" <devil6...@gmail.com> wrote: > > > > hi > > > > I have written a program that performs correlation via FFT. The concept is > > > to search a base image for occurrences of a particular shape. To do this > > > first I took the FFT of the base image, then FFT of the shape (padded with > > > zeros) which I want to search in the base Image. After this I got 4 arrays > > > of real and imaginary data. Next I multiplied the array (real & imaginary) > > > of the shape with the array of the base image and took its IFFT. Finally, > > > after IFFT i got two arrays (real & imaginary), next I squared and added > > > both the arrays (the real and the imaginary) and took its square root. > > > As expected, the result should be that I should get a sharp clear peak. > > > But in fact I get a noisy image. Please correct me if the above procedure > > > is incorrect. > > > > I think if there would have been any problem in my FFT & IFFT routine then > > > I should have not got my base image back, once I have performed a FFT on it > > > and then did a IFFT. > > > > If anyone has the desire to take a look of my FFT correlation results I'd > > > really appreciate it. > > > > Base image:http://testftpc.awardspace.com/fft/LENA.bmp > > > > FFT performed on base image:http://testftpc.awardspace.com/fft/(FFT)LENA.bmp > > > > IFFT performed on base image:http://testftpc.awardspace.com/fft/(I)LENA.bmp > > > > Target shape:http://testftpc.awardspace.com/fft/ll.bmp > > > > Correlation Result:http://testftpc.awardspace.com/fft/CORR.bmp > > > > FFT & IFFT routine:http://testftpc.awardspace.com/fft/fft_ifft.txt > > > > Convolution routine:http://testftpc.awardspace.com/fft/CORRELATION.txt > > > > Thanks very much in advance, > > > > Mickey > > > I didn't check your links, but from your description it seems as if > > you're doing the convolution of your image and base image (or > > template). �To do a cross correlation, you've got to conjugate one of > > them in the frequency domain before doing the multiplication. �The > > conjugation performs a 'time reversal' in the frequency domain (look > > at the time domain equations for both convolution and cross > > correaltion - the sign is different). > > > And it makes a difference as to which transform you conjugate. �In > > your case, since you're doing template matching, you'd conjugate the > > FFT result of your base image before doing the multiplication of the 2 > > transforms (if you were doing cross correaltion for motion detection, > > it'd be a different story). > > > So try conjugating the FFT results of your zero padded base image > > (change signs of all imaginary parts: i[n] = - i[n]). �Then multipy > > the 2 transforms and inverse FFT.- Hide quoted text - > > > - Show quoted text - > > Ooops. �Meant to say: conjugate the FFT results of your zero padded > shape image in that last paragraph.- Hide quoted text - > > - Show quoted text -Me again (third times the charm?). I actualy did download one of your links (the multiplication code) and printed it out. After attending to some other things, I decided to take a quick look at it. I cannot even remotely imagine how that code could be working properly. You seem to be using 2 different sizes (128x128 - the 'LENA' image, and 20x20). Here's the process you should be following: 1) 2D FFT the 'LENA' image (a 128x128 image). 2) zero pad the template (i.e.: target, shape or 'object you're trying to find' in the 'LENA' image). It should be zero padded to be 128x128 points. 3) 2D FFT the 128x128 template. 4) conjugate the result of the template transform (a very important step, otherwise, you'll be getting a convolution, not a cross correlation). 5) multiply both 128x128 transform results, point by point. 6) inverse 2D transform. The result is the cross correlation of the 2 images - the peak in the cross correlation tells you where the upper left corner of your template (or shape or 'target', or 'thing you're trying to find' is located within the 'LENA' image).
Reply by ●September 2, 20082008-09-02
On Sep 2, 12:38�pm, kevinjmc...@netscape.net wrote:> On Sep 2, 12:42�am, kevinjmc...@netscape.net wrote: > > > > > > > On Sep 2, 12:34�am, kevinjmc...@netscape.net wrote: > > > > On Sep 1, 9:56�am, "devil6600" <devil6...@gmail.com> wrote: > > > > > hi > > > > > I have written a program that performs correlation via FFT. The concept is > > > > to search a base image for occurrences of a particular shape. To do this > > > > first I took the FFT of the base image, then FFT of the shape (padded with > > > > zeros) which I want to search in the base Image. After this I got 4 arrays > > > > of real and imaginary data. Next I multiplied the array (real & imaginary) > > > > of the shape with the array of the base image and took its IFFT. Finally, > > > > after IFFT i got two arrays (real & imaginary), next I squared and added > > > > both the arrays (the real and the imaginary) and took its square root. > > > > As expected, the result should be that I should get a sharp clear peak. > > > > But in fact I get a noisy image. Please correct me if the above procedure > > > > is incorrect. > > > > > I think if there would have been any problem in my FFT & IFFT routine then > > > > I should have not got my base image back, once I have performed a FFT on it > > > > and then did a IFFT. > > > > > If anyone has the desire to take a look of my FFT correlation results I'd > > > > really appreciate it. > > > > > Base image:http://testftpc.awardspace.com/fft/LENA.bmp > > > > > FFT performed on base image:http://testftpc.awardspace.com/fft/(FFT)LENA.bmp > > > > > IFFT performed on base image:http://testftpc.awardspace.com/fft/(I)LENA.bmp > > > > > Target shape:http://testftpc.awardspace.com/fft/ll.bmp > > > > > Correlation Result:http://testftpc.awardspace.com/fft/CORR.bmp > > > > > FFT & IFFT routine:http://testftpc.awardspace.com/fft/fft_ifft.txt > > > > > Convolution routine:http://testftpc.awardspace.com/fft/CORRELATION.txt > > > > > Thanks very much in advance, > > > > > Mickey > > > > I didn't check your links, but from your description it seems as if > > > you're doing the convolution of your image and base image (or > > > template). �To do a cross correlation, you've got to conjugate one of > > > them in the frequency domain before doing the multiplication. �The > > > conjugation performs a 'time reversal' in the frequency domain (look > > > at the time domain equations for both convolution and cross > > > correaltion - the sign is different). > > > > And it makes a difference as to which transform you conjugate. �In > > > your case, since you're doing template matching, you'd conjugate the > > > FFT result of your base image before doing the multiplication of the 2 > > > transforms (if you were doing cross correaltion for motion detection, > > > it'd be a different story). > > > > So try conjugating the FFT results of your zero padded base image > > > (change signs of all imaginary parts: i[n] = - i[n]). �Then multipy > > > the 2 transforms and inverse FFT.- Hide quoted text - > > > > - Show quoted text - > > > Ooops. �Meant to say: conjugate the FFT results of your zero padded > > shape image in that last paragraph.- Hide quoted text - > > > - Show quoted text - > > Me again (third times the charm?). �I actualy did download one of your > links (the multiplication code) and printed it out. �After attending > to some other things, I decided to take a quick look at it. �I cannot > even remotely imagine how that code could be working properly. �You > seem to be using 2 different sizes (128x128 - the 'LENA' image, and > 20x20). > > Here's the process you should be following: > > 1) 2D FFT the 'LENA' image (a 128x128 image). > 2) zero pad the template (i.e.: target, shape or 'object you're trying > to find' in the 'LENA' image). �It should be zero padded to be 128x128 > points. > 3) 2D FFT the 128x128 template. > 4) conjugate the result of the template transform (a very important > step, otherwise, you'll be getting a convolution, not a cross > correlation). > 5) multiply both 128x128 transform results, point by point. > 6) inverse 2D transform. > > The result is the cross correlation of the 2 images - the peak in the > cross correlation tells you where the upper left corner of your > template (or shape or 'target', or 'thing you're trying to find' is > located within the 'LENA' image).- Hide quoted text - > > - Show quoted text -Hi All, Once you do the above processing also you may not get match. So you have to use normalized cross correlation to get the exact match. If you want the reasons i can giveyou the paper, which talks about this. So somebody wants paper,please send me a blank mail. Thanks Naresh
Reply by ●September 2, 20082008-09-02
>On Sep 2, 12:42=A0am, kevinjmc...@netscape.net wrote: >> On Sep 2, 12:34=A0am, kevinjmc...@netscape.net wrote: >> >> >> >> >> >> > On Sep 1, 9:56=A0am, "devil6600" <devil6...@gmail.com> wrote: >> >> > > hi >> >> > > I have written a program that performs correlation via FFT. Theconce=>pt is >> > > to search a base image for occurrences of a particular shape. To dot=>his >> > > first I took the FFT of the base image, then FFT of the shape(padded=> with >> > > zeros) which I want to search in the base Image. After this I got 4a=>rrays >> > > of real and imaginary data. Next I multiplied the array (real &imagi=>nary) >> > > of the shape with the array of the base image and took its IFFT.Fina=>lly, >> > > after IFFT i got two arrays (real & imaginary), next I squared andad=>ded >> > > both the arrays (the real and the imaginary) and took its squareroot=>. >> > > As expected, the result should be that I should get a sharp clearpea=>k. >> > > But in fact I get a noisy image. Please correct me if the aboveproce=>dure >> > > is incorrect. >> >> > > I think if there would have been any problem in my FFT & IFFTroutine=> then >> > > I should have not got my base image back, once I have performed aFFT=> on it >> > > and then did a IFFT. >> >> > > If anyone has the desire to take a look of my FFT correlationresults=> I'd >> > > really appreciate it. >> >> > > Base image:http://testftpc.awardspace.com/fft/LENA.bmp >> >> > > FFT performed on baseimage:http://testftpc.awardspace.com/fft/(FFT)L=>ENA.bmp >> >> > > IFFT performed on baseimage:http://testftpc.awardspace.com/fft/(I)LE=>NA.bmp >> >> > > Target shape:http://testftpc.awardspace.com/fft/ll.bmp >> >> > > Correlation Result:http://testftpc.awardspace.com/fft/CORR.bmp >> >> > > FFT & IFFT routine:http://testftpc.awardspace.com/fft/fft_ifft.txt >> >> > > Convolutionroutine:http://testftpc.awardspace.com/fft/CORRELATION.tx=>t >> >> > > Thanks very much in advance, >> >> > > Mickey >> >> > I didn't check your links, but from your description it seems as if >> > you're doing the convolution of your image and base image (or >> > template). =A0To do a cross correlation, you've got to conjugate oneof>> > them in the frequency domain before doing the multiplication. =A0The >> > conjugation performs a 'time reversal' in the frequency domain (look >> > at the time domain equations for both convolution and cross >> > correaltion - the sign is different). >> >> > And it makes a difference as to which transform you conjugate. =A0In >> > your case, since you're doing template matching, you'd conjugate the >> > FFT result of your base image before doing the multiplication of the2>> > transforms (if you were doing cross correaltion for motiondetection,>> > it'd be a different story). >> >> > So try conjugating the FFT results of your zero padded base image >> > (change signs of all imaginary parts: i[n] =3D - i[n]). =A0Thenmultipy>> > the 2 transforms and inverse FFT.- Hide quoted text - >> >> > - Show quoted text - >> >> Ooops. =A0Meant to say: conjugate the FFT results of your zero padded >> shape image in that last paragraph.- Hide quoted text - >> >> - Show quoted text - > >Me again (third times the charm?). I actualy did download one of your >links (the multiplication code) and printed it out. After attending >to some other things, I decided to take a quick look at it. I cannot >even remotely imagine how that code could be working properly. You >seem to be using 2 different sizes (128x128 - the 'LENA' image, and >20x20). > >Here's the process you should be following: > >1) 2D FFT the 'LENA' image (a 128x128 image). >2) zero pad the template (i.e.: target, shape or 'object you're trying >to find' in the 'LENA' image). It should be zero padded to be 128x128 >points. >3) 2D FFT the 128x128 template. >4) conjugate the result of the template transform (a very important >step, otherwise, you'll be getting a convolution, not a cross >correlation). >5) multiply both 128x128 transform results, point by point. >6) inverse 2D transform. > >The result is the cross correlation of the 2 images - the peak in the >cross correlation tells you where the upper left corner of your >template (or shape or 'target', or 'thing you're trying to find' is >located within the 'LENA' image). >hi, thank you very much for your time. I tried what you told, but didn't got the result. I think i am doing some mistake in taking the conjugate of the imaginary part. What I did for taking conjugate is just multiplied -1 with the imaginary array for all the rows and columns in the template image. And then multiplied the base image and the template image for every pixel. Am i correct? i have uploaded the conjugate and multiplication routine here, if you can take a look i'd really appreciate it: http://testftpc.awardspace.com/fft/multiply.txt and the result here: http://testftpc.awardspace.com/fft/out.bmp on the whole i did these steps: 1) 2D fft of base image. 2) 2D fft of template(zero padded). 3) Multiplied -1 with the imaginary array of template. 4) Multiplied 2Dfft of base image with 2Dfft of template. 5) IFFT of 4th step. thanks again. Mickey.
Reply by ●September 3, 20082008-09-03
On Sep 2, 5:10�pm, "devil6600" <devil6...@gmail.com> wrote:> >On Sep 2, 12:42=A0am, kevinjmc...@netscape.net wrote: > >> On Sep 2, 12:34=A0am, kevinjmc...@netscape.net wrote: > > >> > On Sep 1, 9:56=A0am, "devil6600" <devil6...@gmail.com> wrote: > > >> > > hi > > >> > > I have written a program that performs correlation via FFT. The > conce= > >pt is > >> > > to search a base image for occurrences of a particular shape. To do > t= > >his > >> > > first I took the FFT of the base image, then FFT of the shape > (padded= > > with > >> > > zeros) which I want to search in the base Image. After this I got 4 > a= > >rrays > >> > > of real and imaginary data. Next I multiplied the array (real & > imagi= > >nary) > >> > > of the shape with the array of the base image and took its IFFT. > Fina= > >lly, > >> > > after IFFT i got two arrays (real & imaginary), next I squared and > ad= > >ded > >> > > both the arrays (the real and the imaginary) and took its square > root= > >. > >> > > As expected, the result should be that I should get a sharp clear > pea= > >k. > >> > > But in fact I get a noisy image. Please correct me if the above > proce= > >dure > >> > > is incorrect. > > >> > > I think if there would have been any problem in my FFT & IFFT > routine= > > then > >> > > I should have not got my base image back, once I have performed a > FFT= > > on it > >> > > and then did a IFFT. > > >> > > If anyone has the desire to take a look of my FFT correlation > results= > > I'd > >> > > really appreciate it. > > >> > > Base image:http://testftpc.awardspace.com/fft/LENA.bmp > > >> > > FFT performed on base > > image:http://testftpc.awardspace.com/fft/(FFT)L=>ENA.bmp > > >> > > IFFT performed on base > > image:http://testftpc.awardspace.com/fft/(I)LE=>NA.bmp > > >> > > Target shape:http://testftpc.awardspace.com/fft/ll.bmp > > >> > > Correlation Result:http://testftpc.awardspace.com/fft/CORR.bmp > > >> > > FFT & IFFT routine:http://testftpc.awardspace.com/fft/fft_ifft.txt > > >> > > Convolution > > routine:http://testftpc.awardspace.com/fft/CORRELATION.tx= > > > > > > >t > > >> > > Thanks very much in advance, > > >> > > Mickey > > >> > I didn't check your links, but from your description it seems as if > >> > you're doing the convolution of your image and base image (or > >> > template). =A0To do a cross correlation, you've got to conjugate one > of > >> > them in the frequency domain before doing the multiplication. =A0The > >> > conjugation performs a 'time reversal' in the frequency domain (look > >> > at the time domain equations for both convolution and cross > >> > correaltion - the sign is different). > > >> > And it makes a difference as to which transform you conjugate. =A0In > >> > your case, since you're doing template matching, you'd conjugate the > >> > FFT result of your base image before doing the multiplication of the > 2 > >> > transforms (if you were doing cross correaltion for motion > detection, > >> > it'd be a different story). > > >> > So try conjugating the FFT results of your zero padded base image > >> > (change signs of all imaginary parts: i[n] =3D - i[n]). =A0Then > multipy > >> > the 2 transforms and inverse FFT.- Hide quoted text - > > >> > - Show quoted text - > > >> Ooops. =A0Meant to say: conjugate the FFT results of your zero padded > >> shape image in that last paragraph.- Hide quoted text - > > >> - Show quoted text - > > >Me again (third times the charm?). �I actualy did download one of your > >links (the multiplication code) and printed it out. �After attending > >to some other things, I decided to take a quick look at it. �I cannot > >even remotely imagine how that code could be working properly. �You > >seem to be using 2 different sizes (128x128 - the 'LENA' image, and > >20x20). > > >Here's the process you should be following: > > >1) 2D FFT the 'LENA' image (a 128x128 image). > >2) zero pad the template (i.e.: target, shape or 'object you're trying > >to find' in the 'LENA' image). �It should be zero padded to be 128x128 > >points. > >3) 2D FFT the 128x128 template. > >4) conjugate the result of the template transform (a very important > >step, otherwise, you'll be getting a convolution, not a cross > >correlation). > >5) multiply both 128x128 transform results, point by point. > >6) inverse 2D transform. > > >The result is the cross correlation of the 2 images - the peak in the > >cross correlation tells you where the upper left corner of your > >template (or shape or 'target', or 'thing you're trying to find' is > >located within the 'LENA' image). > > hi, > > thank you very much for your time. > I tried what you told, but didn't got the result. I think i am doing some > mistake in taking the conjugate of the imaginary part. What I did for > taking conjugate is just multiplied -1 with the imaginary array for all the > rows and columns in the template image. And then multiplied the base image > and the template image for every pixel. Am i correct? > > i have uploaded the conjugate and multiplication routine here, if you can > take a look i'd really appreciate it:http://testftpc.awardspace.com/fft/multiply.txt > > and the result here:http://testftpc.awardspace.com/fft/out.bmp > > on the whole i did these steps: > > 1) 2D fft of base image. > 2) 2D fft of template(zero padded). > 3) Multiplied -1 with the imaginary array of template. > 4) Multiplied 2Dfft of base image with 2Dfft of template. > 5) IFFT of 4th step. > > thanks again. > Mickey.- Hide quoted text - > > - Show quoted text -- Hide quoted text - > > - Show quoted text -I looked at your multiply code, and I doubt very much that it works correctly. Here's some code from a C++ template matching program that I've used. Both the image and zero padded template have been forward FFT'd, and the conjugation is done when doing the multiplies (I hope it shows up with the correct indentation and all): // multiply 2D FFT of images; conjugate the result of image 2 (the template); i.e: if R1 + I1j is the FFT of the // 1st image and R2 + I2 is the FFT of image2 (the template) use: (R1 + I1j)*(R2 - I2j) = (R1*R2 + I1*I2) + (- R1*I2 + R2*1I)j for(col = 0; col < N; col++){ for (row = 0; row < N; row++){ t = image1r[row][col]*image2r[row][col] + image1i[row] [col]*image2i[row][col]; image1i[row][col] = - image1r[row][col]*image2i[row][col] + image2r[row][col]*image1i[row][col]; image1r[row][col] = t; } } You've only got two multiplies in your code, so I strongly suspect that it's wrong (easy thing to do). In the above, we're multiplying the result of two FFT's, so we have real/imaginary times another real/ imaginary. The temp variable 't' above is to avoid overwriting 'image1r' (the original values are needed to compute 'image1i' in the second line). You'll have to change the variable names above to fit your program. I would also strongly suggest using a very simple image and template at first. I very often do that because it makes it a lot easier to verify that my code is working correctly. So you might consider using a simple square box of, say, 4x4 pixels (each with a value of, say, 100). Then place the upper left corner of the 4x4 square box at, perhaps, pixel location 50,50 within your 128x128 base image. All the other pixels should be 0. Then your template would be the exact same 4x4 box starting at location 0,0. You'd zero pad that to 128x128 with, of course, 0's. After the 2D FFT's, conjugation/ multiplication and IFFT, your cross correlation result (often referred to as the cross correlation surface) is the real part of the output. You should get a peak at location 50,50 in the real array outputs, plus a kind of cross shaped bunch of smaller numbers around it, and even smaller numbers radially away from the peak. Once you've got it working, move the box in the base image around to different locations, recompile/run again, and you'll see that your result is locating it correctly. After that, you can move on to more complex images. And, as noted by the poster Naresh (thanks), you probably should be normalizing things (the spectral content might be very uneven, which could cause problems). And you're probably already aware that if your base image contains a rotated version of what you're trying to find with your template, then you may have to cross correlate with multiple templates where each of them contains rotated versions of whatever it is you're trying to find. The above should clear up your problems, but let me know if you run into any more of them.
Reply by ●September 4, 20082008-09-04
>On Sep 2, 5:10=A0pm, "devil6600" <devil6...@gmail.com> wrote: >> >On Sep 2, 12:42=3DA0am, kevinjmc...@netscape.net wrote: >> >> On Sep 2, 12:34=3DA0am, kevinjmc...@netscape.net wrote: >> >> >> > On Sep 1, 9:56=3DA0am, "devil6600" <devil6...@gmail.com> wrote: >> >> >> > > hi >> >> >> > > I have written a program that performs correlation via FFT. The >> conce=3D >> >pt is >> >> > > to search a base image for occurrences of a particular shape. Tod=>o >> t=3D >> >his >> >> > > first I took the FFT of the base image, then FFT of the shape >> (padded=3D >> > with >> >> > > zeros) which I want to search in the base Image. After this Igot =>4 >> a=3D >> >rrays >> >> > > of real and imaginary data. Next I multiplied the array (real & >> imagi=3D >> >nary) >> >> > > of the shape with the array of the base image and took itsIFFT.>> Fina=3D >> >lly, >> >> > > after IFFT i got two arrays (real & imaginary), next I squaredand>> ad=3D >> >ded >> >> > > both the arrays (the real and the imaginary) and took itssquare>> root=3D >> >. >> >> > > As expected, the result should be that I should get a sharpclear>> pea=3D >> >k. >> >> > > But in fact I get a noisy image. Please correct me if the above >> proce=3D >> >dure >> >> > > is incorrect. >> >> >> > > I think if there would have been any problem in my FFT & IFFT >> routine=3D >> > then >> >> > > I should have not got my base image back, once I have performeda>> FFT=3D >> > on it >> >> > > and then did a IFFT. >> >> >> > > If anyone has the desire to take a look of my FFT correlation >> results=3D >> > I'd >> >> > > really appreciate it. >> >> >> > > Base image:http://testftpc.awardspace.com/fft/LENA.bmp >> >> >> > > FFT performed on base >> >> image:http://testftpc.awardspace.com/fft/(FFT)L=3D>ENA.bmp >> >> >> > > IFFT performed on base >> >> image:http://testftpc.awardspace.com/fft/(I)LE=3D>NA.bmp >> >> >> > > Target shape:http://testftpc.awardspace.com/fft/ll.bmp >> >> >> > > Correlation Result:http://testftpc.awardspace.com/fft/CORR.bmp >> >> >> > > FFT & IFFTroutine:http://testftpc.awardspace.com/fft/fft_ifft.txt>> >> >> > > Convolution >> >> routine:http://testftpc.awardspace.com/fft/CORRELATION.tx=3D >> >> >> >> >> >> >t >> >> >> > > Thanks very much in advance, >> >> >> > > Mickey >> >> >> > I didn't check your links, but from your description it seems asif>> >> > you're doing the convolution of your image and base image (or >> >> > template). =3DA0To do a cross correlation, you've got to conjugateo=>ne >> of >> >> > them in the frequency domain before doing the multiplication.=3DA0T=>he >> >> > conjugation performs a 'time reversal' in the frequency domain(look>> >> > at the time domain equations for both convolution and cross >> >> > correaltion - the sign is different). >> >> >> > And it makes a difference as to which transform you conjugate.=3DA0=>In >> >> > your case, since you're doing template matching, you'd conjugatethe>> >> > FFT result of your base image before doing the multiplication ofthe>> 2 >> >> > transforms (if you were doing cross correaltion for motion >> detection, >> >> > it'd be a different story). >> >> >> > So try conjugating the FFT results of your zero padded base image >> >> > (change signs of all imaginary parts: i[n] =3D3D - i[n]).=3DA0Then>> multipy >> >> > the 2 transforms and inverse FFT.- Hide quoted text - >> >> >> > - Show quoted text - >> >> >> Ooops. =3DA0Meant to say: conjugate the FFT results of your zeropadde=>d >> >> shape image in that last paragraph.- Hide quoted text - >> >> >> - Show quoted text - >> >> >Me again (third times the charm?). =A0I actualy did download one ofyour>> >links (the multiplication code) and printed it out. =A0Afterattending>> >to some other things, I decided to take a quick look at it. =A0Icannot>> >even remotely imagine how that code could be working properly. =A0You >> >seem to be using 2 different sizes (128x128 - the 'LENA' image, and >> >20x20). >> >> >Here's the process you should be following: >> >> >1) 2D FFT the 'LENA' image (a 128x128 image). >> >2) zero pad the template (i.e.: target, shape or 'object you'retrying>> >to find' in the 'LENA' image). =A0It should be zero padded to be128x128>> >points. >> >3) 2D FFT the 128x128 template. >> >4) conjugate the result of the template transform (a very important >> >step, otherwise, you'll be getting a convolution, not a cross >> >correlation). >> >5) multiply both 128x128 transform results, point by point. >> >6) inverse 2D transform. >> >> >The result is the cross correlation of the 2 images - the peak in the >> >cross correlation tells you where the upper left corner of your >> >template (or shape or 'target', or 'thing you're trying to find' is >> >located within the 'LENA' image). >> >> hi, >> >> thank you very much for your time. >> I tried what you told, but didn't got the result. I think i am doingsome>> mistake in taking the conjugate of the imaginary part. What I did for >> taking conjugate is just multiplied -1 with the imaginary array for allt=>he >> rows and columns in the template image. And then multiplied the baseimag=>e >> and the template image for every pixel. Am i correct? >> >> i have uploaded the conjugate and multiplication routine here, if youcan>> take a look i'd really appreciateit:http://testftpc.awardspace.com/fft/m=>ultiply.txt >> >> and the result here:http://testftpc.awardspace.com/fft/out.bmp >> >> on the whole i did these steps: >> >> 1) 2D fft of base image. >> 2) 2D fft of template(zero padded). >> 3) Multiplied -1 with the imaginary array of template. >> 4) Multiplied 2Dfft of base image with 2Dfft of template. >> 5) IFFT of 4th step. >> >> thanks again. >> Mickey.- Hide quoted text - >> >> - Show quoted text -- Hide quoted text - >> >> - Show quoted text - > >I looked at your multiply code, and I doubt very much that it works >correctly. Here's some code from a C++ template matching program that >I've used. Both the image and zero padded template have been forward >FFT'd, and the conjugation is done when doing the multiplies (I hope >it shows up with the correct indentation and all): > >// multiply 2D FFT of images; conjugate the result of image 2 (the >template); i.e: if R1 + I1j is the FFT of the >// 1st image and R2 + I2 is the FFT of image2 (the template) use: (R1 >+ I1j)*(R2 - I2j) =3D (R1*R2 + I1*I2) + (- R1*I2 + R2*1I)j > >for(col =3D 0; col < N; col++){ > for (row =3D 0; row < N; row++){ > t =3D image1r[row][col]*image2r[row][col] + image1i[row] >[col]*image2i[row][col]; > image1i[row][col] =3D - image1r[row][col]*image2i[row][col] + >image2r[row][col]*image1i[row][col]; > image1r[row][col] =3D t; > } >} > >You've only got two multiplies in your code, so I strongly suspect >that it's wrong (easy thing to do). In the above, we're multiplying >the result of two FFT's, so we have real/imaginary times another real/ >imaginary. The temp variable 't' above is to avoid overwriting >'image1r' (the original values are needed to compute 'image1i' in the >second line). You'll have to change the variable names above to fit >your program. > >I would also strongly suggest using a very simple image and template >at first. I very often do that because it makes it a lot easier to >verify that my code is working correctly. So you might consider using >a simple square box of, say, 4x4 pixels (each with a value of, say, >100). Then place the upper left corner of the 4x4 square box at, >perhaps, pixel location 50,50 within your 128x128 base image. All the >other pixels should be 0. Then your template would be the exact same >4x4 box starting at location 0,0. You'd zero pad that to 128x128 >with, of course, 0's. > >After the 2D FFT's, conjugation/ multiplication and IFFT, your cross >correlation result (often referred to as the cross correlation >surface) is the real part of the output. You should get a peak at >location 50,50 in the real array outputs, plus a kind of cross shaped >bunch of smaller numbers around it, and even smaller numbers radially >away from the peak. > >Once you've got it working, move the box in the base image around to >different locations, recompile/run again, and you'll see that your >result is locating it correctly. After that, you can move on to more >complex images. And, as noted by the poster Naresh (thanks), you >probably should be normalizing things (the spectral content might be >very uneven, which could cause problems). And you're probably already >aware that if your base image contains a rotated version of what >you're trying to find with your template, then you may have to cross >correlate with multiple templates where each of them contains rotated >versions of whatever it is you're trying to find. > >The above should clear up your problems, but let me know if you run >into any more of them. >hi thanks for the code. I am little bit confused regarding the 3D variable in the code, exactly what is 3D, it is a conjugate? If its a conjugate then in the code if we multiply by -1 insted of 3D then will it work? I have used your code in my program (leaving the 3D variable out), still i am getting a noisy image in the output. here's the multiplication code, where img3 & img11 are real part of image and template and img4 & img22 are imaginary part of image and template: for(row=0; row<128; row++) { for(col=0; col<128; col++) { img1[row][col] = img3[row][col]*img11[row][col] + img4[row][col]*img22[row][col]; img2[row][col] = -(img3[row][col]*img22[row][col]+img11[row][col]*img4[row][col]); } } thanks mickey
Reply by ●September 5, 20082008-09-05
On Sep 4, 6:48�am, "devil6600" <devil6...@gmail.com> wrote:> >On Sep 2, 5:10=A0pm, "devil6600" <devil6...@gmail.com> wrote: > >> >On Sep 2, 12:42=3DA0am, kevinjmc...@netscape.net wrote: > >> >> On Sep 2, 12:34=3DA0am, kevinjmc...@netscape.net wrote: > > >> >> > On Sep 1, 9:56=3DA0am, "devil6600" <devil6...@gmail.com> wrote: > > >> >> > > hi > > >> >> > > I have written a program that performs correlation via FFT. The > >> conce=3D > >> >pt is > >> >> > > to search a base image for occurrences of a particular shape. To > d= > >o > >> t=3D > >> >his > >> >> > > first I took the FFT of the base image, then FFT of the shape > >> (padded=3D > >> > with > >> >> > > zeros) which I want to search in the base Image. After this I > got = > >4 > >> a=3D > >> >rrays > >> >> > > of real and imaginary data. Next I multiplied the array (real & > >> imagi=3D > >> >nary) > >> >> > > of the shape with the array of the base image and took its > IFFT. > >> Fina=3D > >> >lly, > >> >> > > after IFFT i got two arrays (real & imaginary), next I squared > and > >> ad=3D > >> >ded > >> >> > > both the arrays (the real and the imaginary) and took its > square > >> root=3D > >> >. > >> >> > > As expected, the result should be that I should get a sharp > clear > >> pea=3D > >> >k. > >> >> > > But in fact I get a noisy image. Please correct me if the above > >> proce=3D > >> >dure > >> >> > > is incorrect. > > >> >> > > I think if there would have been any problem in my FFT & IFFT > >> routine=3D > >> > then > >> >> > > I should have not got my base image back, once I have performed > a > >> FFT=3D > >> > on it > >> >> > > and then did a IFFT. > > >> >> > > If anyone has the desire to take a look of my FFT correlation > >> results=3D > >> > I'd > >> >> > > really appreciate it. > > >> >> > > Base image:http://testftpc.awardspace.com/fft/LENA.bmp > > >> >> > > FFT performed on base > > >> image:http://testftpc.awardspace.com/fft/(FFT)L=3D>ENA.bmp > > >> >> > > IFFT performed on base > > >> image:http://testftpc.awardspace.com/fft/(I)LE=3D>NA.bmp > > >> >> > > Target shape:http://testftpc.awardspace.com/fft/ll.bmp > > >> >> > > Correlation Result:http://testftpc.awardspace.com/fft/CORR.bmp > > >> >> > > FFT & IFFT > > routine:http://testftpc.awardspace.com/fft/fft_ifft.txt > > > > > > >> >> > > Convolution > > >> routine:http://testftpc.awardspace.com/fft/CORRELATION.tx=3D > > >> >t > > >> >> > > Thanks very much in advance, > > >> >> > > Mickey > > >> >> > I didn't check your links, but from your description it seems as > if > >> >> > you're doing the convolution of your image and base image (or > >> >> > template). =3DA0To do a cross correlation, you've got to conjugate > o= > >ne > >> of > >> >> > them in the frequency domain before doing the multiplication. > =3DA0T= > >he > >> >> > conjugation performs a 'time reversal' in the frequency domain > (look > >> >> > at the time domain equations for both convolution and cross > >> >> > correaltion - the sign is different). > > >> >> > And it makes a difference as to which transform you conjugate. > =3DA0= > >In > >> >> > your case, since you're doing template matching, you'd conjugate > the > >> >> > FFT result of your base image before doing the multiplication of > the > >> 2 > >> >> > transforms (if you were doing cross correaltion for motion > >> detection, > >> >> > it'd be a different story). > > >> >> > So try conjugating the FFT results of your zero padded base image > >> >> > (change signs of all imaginary parts: i[n] =3D3D - i[n]). > =3DA0Then > >> multipy > >> >> > the 2 transforms and inverse FFT.- Hide quoted text - > > >> >> > - Show quoted text - > > >> >> Ooops. =3DA0Meant to say: conjugate the FFT results of your zero > padde= > >d > >> >> shape image in that last paragraph.- Hide quoted text - > > >> >> - Show quoted text - > > >> >Me again (third times the charm?). =A0I actualy did download one of > your > >> >links (the multiplication code) and printed it out. =A0After > attending > >> >to some other things, I decided to take a quick look at it. =A0I > cannot > >> >even remotely imagine how that code could be working properly. =A0You > >> >seem to be using 2 different sizes (128x128 - the 'LENA' image, and > >> >20x20). > > >> >Here's the process you should be following: > > >> >1) 2D FFT the 'LENA' image (a 128x128 image). > >> >2) zero pad the template (i.e.: target, shape or 'object you're > trying > >> >to find' in the 'LENA' image). =A0It should be zero padded to be > 128x128 > >> >points. > >> >3) 2D FFT the 128x128 template. > >> >4) conjugate the result of the template transform (a very important > >> >step, otherwise, you'll be getting a convolution, not a cross > >> >correlation). > >> >5) multiply both 128x128 transform results, point by point. > >> >6) inverse 2D transform. > > >> >The result is the cross correlation of the 2 images - the peak in the > >> >cross correlation tells you where the upper left corner of your > >> >template (or shape or 'target', or 'thing you're trying to find' is > >> >located within the 'LENA' image). > > >> hi, > > >> thank you very much for your time. > >> I tried what you told, but didn't got the result. I think i am doing > some > >> mistake in taking the conjugate of the imaginary part. What I did for > >> taking conjugate is just multiplied -1 with the imaginary array for all > t= > >he > >> rows and columns in the template image. And then multiplied the base > imag= > >e > >> and the template image for every pixel. Am i correct? > > >> i have uploaded the conjugate and multiplication routine here, if you > can > >> take a look i'd really appreciate > > it:http://testftpc.awardspace.com/fft/m= > > > > > > >ultiply.txt > > >> and the result here:http://testftpc.awardspace.com/fft/out.bmp > > >> on the whole i did these steps: > > >> 1) 2D fft of base image. > >> 2) 2D fft of template(zero padded). > >> 3) Multiplied -1 with the imaginary array of template. > >> 4) Multiplied 2Dfft of base image with 2Dfft of template. > >> 5) IFFT of 4th step. > > >> thanks again. > >> Mickey.- Hide quoted text - > > >> - Show quoted text -- Hide quoted text - > > >> - Show quoted text - > > >I looked at your multiply code, and I doubt very much that it works > >correctly. �Here's some code from a C++ template matching program that > >I've used. �Both the image and zero padded template have been forward > >FFT'd, and the conjugation is done when doing the multiplies (I hope > >it shows up with the correct indentation and all): > > >// multiply 2D FFT of images; �conjugate the result of image 2 (the > >template); i.e: if R1 + I1j is the FFT of the > >// 1st image and R2 + I2 is the FFT of image2 (the template) use: �(R1 > >+ I1j)*(R2 - I2j) =3D (R1*R2 + I1*I2) + (- R1*I2 + R2*1I)j > > >for(col =3D 0; col < N; col++){ > > � �for (row =3D 0; row < N; row++){ > > � � � �t =3D image1r[row][col]*image2r[row][col] + image1i[row] > >[col]*image2i[row][col]; > > � � � �image1i[row][col] =3D - image1r[row][col]*image2i[row][col] + > >image2r[row][col]*image1i[row][col]; > > � � � �image1r[row][col] =3D t; > > � �} > >} > > >You've only got two multiplies in your code, so I strongly suspect > >that it's wrong (easy thing to do). �In the above, we're multiplying > >the result of two FFT's, so we have real/imaginary times another real/ > >imaginary. �The temp variable 't' above is to avoid overwriting > >'image1r' (the original values are needed to compute 'image1i' �in the > >second line). �You'll have to change the variable names above to fit > >your program. > > >I would also strongly suggest using a very simple image and template > >at first. �I very often do that because it makes it a lot easier to > >verify that my code is working correctly. �So you might consider using > >a simple square box of, say, 4x4 pixels (each with a value of, say, > >100). �Then place the upper left corner of the 4x4 square box at, > >perhaps, pixel location 50,50 within your 128x128 base image. �All the > >other pixels should be 0. �Then your template would be the exact same > >4x4 box starting at location 0,0. �You'd zero pad that to 128x128 > >with, of course, 0's. > > >After the 2D FFT's, conjugation/ multiplication and IFFT, your cross > >correlation result (often referred to as the cross correlation > >surface) is the real part of the output. You should get a peak at > >location 50,50 in the real array outputs, plus a kind of cross shaped > >bunch of smaller numbers around it, and even smaller numbers radially > >away from the peak. > > >Once you've got it working, move the box in the base image around to > >different locations, recompile/run again, and you'll see that your > >result is locating it correctly. �After that, you can move on to more > >complex images. �And, as noted by the poster Naresh (thanks), you > >probably should be normalizing things (the spectral content might be > >very uneven, which could cause problems). �And you're probably already > >aware that if your base image contains a rotated version of what > >you're trying to find with your template, then you may have to cross > >correlate with multiple templates where each of them contains rotated > >versions of whatever it is you're trying to find. > > >The above should clear up your problems, but let me know if you run > >into any more of them. > > hi > > thanks for the code. > I am little bit confused regarding the 3D variable in the code, exactly > what is 3D, it is a conjugate? If its a conjugate then in the code if we > multiply by -1 insted of 3D then will it work? > I have used your code in my program (leaving the 3D variable out), still i > am getting a noisy image in the output. > > here's the multiplication code, where img3 & img11 are real part of image > and template and img4 & img22 are imaginary part of image and template: > > for(row=0; row<128; row++) > { > for(col=0; col<128; col++) > { > � � �img1[row][col] = img3[row][col]*img11[row][col] + > img4[row][col]*img22[row][col]; > � � �img2[row][col] = > -(img3[row][col]*img22[row][col]+img11[row][col]*img4[row][col]); > > } > } > > thanks > mickey- Hide quoted text - > > - Show quoted text -- Hide quoted text - > > - Show quoted text -- Hide quoted text - > > - Show quoted text -Sorry about that previous post - the indentation was fine, but I forgot about the wrap-around problem. But I kind of thought that you�d figure it out. I think you�ve got it almost right. Just delete the parentheses in the second line, and keep the minus sign in front of the first multiply. Remember that the data is complex, so if R1 + I1j is the base image, and the template is R2 + I2j, then conjugating the latter is R2 - I2j, and your multiplication becomes: (R1+I1j)*(R2-I2j) = R1*R2 + I1*I2 (real result) - R1*I2 + I1*R2 (imaginary result) Your code has a negation of the entire imaginary result. So if (img3, img4) is (R1, I1) and (img11, img22) is (R2, I2), your code should work if you delete the parentheses and keep the minus sign in front of the first multiply (check it using the above). And with the variable names that you�re using, you don�t have to worry about overwriting. And if you�re using the more complicated �LENA� image, you�re probably going to have to do some normalization. Without going into any details, just zero out the 0,0 or �DC� component of both your base image and template. This can be accomplished easily once you have 2D transformed them into the frequency domain. There are more complicated ways of doing things, but I�d rather avoid that until you�ve got the code working right. Let me know how it works out.
Reply by ●September 5, 20082008-09-05
On Sep 4, 11:52�pm, kevinjmc...@netscape.net wrote:> On Sep 4, 6:48�am, "devil6600" <devil6...@gmail.com> wrote: > > > > > >On Sep 2, 5:10=A0pm, "devil6600" <devil6...@gmail.com> wrote: > > >> >On Sep 2, 12:42=3DA0am, kevinjmc...@netscape.net wrote: > > >> >> On Sep 2, 12:34=3DA0am, kevinjmc...@netscape.net wrote: > > > >> >> > On Sep 1, 9:56=3DA0am, "devil6600" <devil6...@gmail.com> wrote: > > > >> >> > > hi > > > >> >> > > I have written a program that performs correlation via FFT. The > > >> conce=3D > > >> >pt is > > >> >> > > to search a base image for occurrences of a particular shape. To > > d= > > >o > > >> t=3D > > >> >his > > >> >> > > first I took the FFT of the base image, then FFT of the shape > > >> (padded=3D > > >> > with > > >> >> > > zeros) which I want to search in the base Image. After this I > > got = > > >4 > > >> a=3D > > >> >rrays > > >> >> > > of real and imaginary data. Next I multiplied the array (real & > > >> imagi=3D > > >> >nary) > > >> >> > > of the shape with the array of the base image and took its > > IFFT. > > >> Fina=3D > > >> >lly, > > >> >> > > after IFFT i got two arrays (real & imaginary), next I squared > > and > > >> ad=3D > > >> >ded > > >> >> > > both the arrays (the real and the imaginary) and took its > > square > > >> root=3D > > >> >. > > >> >> > > As expected, the result should be that I should get a sharp > > clear > > >> pea=3D > > >> >k. > > >> >> > > But in fact I get a noisy image. Please correct me if the above > > >> proce=3D > > >> >dure > > >> >> > > is incorrect. > > > >> >> > > I think if there would have been any problem in my FFT & IFFT > > >> routine=3D > > >> > then > > >> >> > > I should have not got my base image back, once I have performed > > a > > >> FFT=3D > > >> > on it > > >> >> > > and then did a IFFT. > > > >> >> > > If anyone has the desire to take a look of my FFT correlation > > >> results=3D > > >> > I'd > > >> >> > > really appreciate it. > > > >> >> > > Base image:http://testftpc.awardspace.com/fft/LENA.bmp > > > >> >> > > FFT performed on base > > > >> image:http://testftpc.awardspace.com/fft/(FFT)L=3D>ENA.bmp > > > >> >> > > IFFT performed on base > > > >> image:http://testftpc.awardspace.com/fft/(I)LE=3D>NA.bmp > > > >> >> > > Target shape:http://testftpc.awardspace.com/fft/ll.bmp > > > >> >> > > Correlation Result:http://testftpc.awardspace.com/fft/CORR.bmp > > > >> >> > > FFT & IFFT > > > routine:http://testftpc.awardspace.com/fft/fft_ifft.txt > > > >> >> > > Convolution > > > >> routine:http://testftpc.awardspace.com/fft/CORRELATION.tx=3D > > > >> >t > > > >> >> > > Thanks very much in advance, > > > >> >> > > Mickey > > > >> >> > I didn't check your links, but from your description it seems as > > if > > >> >> > you're doing the convolution of your image and base image (or > > >> >> > template). =3DA0To do a cross correlation, you've got to conjugate > > o= > > >ne > > >> of > > >> >> > them in the frequency domain before doing the multiplication. > > =3DA0T= > > >he > > >> >> > conjugation performs a 'time reversal' in the frequency domain > > (look > > >> >> > at the time domain equations for both convolution and cross > > >> >> > correaltion - the sign is different). > > > >> >> > And it makes a difference as to which transform you conjugate. > > =3DA0= > > >In > > >> >> > your case, since you're doing template matching, you'd conjugate > > the > > >> >> > FFT result of your base image before doing the multiplication of > > the > > >> 2 > > >> >> > transforms (if you were doing cross correaltion for motion > > >> detection, > > >> >> > it'd be a different story). > > > >> >> > So try conjugating the FFT results of your zero padded base image > > >> >> > (change signs of all imaginary parts: i[n] =3D3D - i[n]). > > =3DA0Then > > >> multipy > > >> >> > the 2 transforms and inverse FFT.- Hide quoted text - > > > >> >> > - Show quoted text - > > > >> >> Ooops. =3DA0Meant to say: conjugate the FFT results of your zero > > padde= > > >d > > >> >> shape image in that last paragraph.- Hide quoted text - > > > >> >> - Show quoted text - > > > >> >Me again (third times the charm?). =A0I actualy did download one of > > your > > >> >links (the multiplication code) and printed it out. =A0After > > attending > > >> >to some other things, I decided to take a quick look at it. =A0I > > cannot > > >> >even remotely imagine how that code could be working properly. =A0You > > >> >seem to be using 2 different sizes (128x128 - the 'LENA' image, and > > >> >20x20). > > > >> >Here's the process you should be following: > > > >> >1) 2D FFT the 'LENA' image (a 128x128 image). > > >> >2) zero pad the template (i.e.: target, shape or 'object you're > > trying > > >> >to find' in the 'LENA' image). =A0It should be zero padded to be > > 128x128 > > >> >points. > > >> >3) 2D FFT the 128x128 template. > > >> >4) conjugate the result of the template transform (a very important > > >> >step, otherwise, you'll be getting a convolution, not a cross > > >> >correlation). > > >> >5) multiply both 128x128 transform results, point by point. > > >> >6) inverse 2D transform. > > > >> >The result is the cross correlation of the 2 images - the peak in the > > >> >cross correlation tells you where the upper left corner of your > > >> >template (or shape or 'target', or 'thing you're trying to find' is > > >> >located within the 'LENA' image). > > > >> hi, > > > >> thank you very much for your time. > > >> I tried what you told, but didn't got the result. I think i am doing > > some > > >> mistake in taking the conjugate of the imaginary part. What I did for > > >> taking conjugate is just multiplied -1 with the imaginary array for all > > t= > > >he > > >> rows and columns in the template image. And then multiplied the base > > imag= > > >e > > >> and the template image for every pixel. Am i correct? > > > >> i have uploaded the conjugate and multiplication routine here, if you > > can > > >> take a look i'd really appreciate > > > it:http://testftpc.awardspace.com/fft/m= > > > >ultiply.txt > > > >> and the result here:http://testftpc.awardspace.com/fft/out.bmp > > > >> on the whole i did these steps: > > > >> 1) 2D fft of base image. > > >> 2) 2D fft of template(zero padded). > > >> 3) Multiplied -1 with the imaginary array of template. > > >> 4) Multiplied 2Dfft of base image with 2Dfft of template. > > >> 5) IFFT of 4th step. > > > >> thanks again. > > >> Mickey.- Hide quoted text - > > > >> - Show quoted text -- Hide quoted text - > > > >> - Show quoted text - > > > >I looked at your multiply code, and I doubt very much that it works > > >correctly. �Here's some code from a C++ template matching program that > > >I've used. �Both the image and zero padded template have been forward > > >FFT'd, and the conjugation is done when doing the multiplies (I hope > > >it shows up with the correct indentation and all): > > > >// multiply 2D FFT of images; �conjugate the result of image 2 (the > > >template); i.e: if R1 + I1j is the FFT of the > > >// 1st image and R2 + I2 is the FFT of image2 (the template) use: �(R1 > > >+ I1j)*(R2 - I2j) =3D (R1*R2 + I1*I2) + (- R1*I2 + R2*1I)j > > > >for(col =3D 0; col < N; col++){ > > > � �for (row =3D 0; row < N; row++){ > > > � � � �t =3D image1r[row][col]*image2r[row][col] + image1i[row] > > >[col]*image2i[row][col]; > > > � � � �image1i[row][col] =3D - image1r[row][col]*image2i[row][col] + > > >image2r[row][col]*image1i[row][col]; > > > � � � �image1r[row][col] =3D t; > > > � �} > > >} > > > >You've only got two multiplies in your code, so I strongly suspect > > >that it's wrong (easy thing to do). �In the above, we're multiplying > > >the result of two FFT's, so we have real/imaginary times another real/ > > >imaginary. �The temp variable 't' above is to avoid overwriting > > >'image1r' (the original values are needed to compute 'image1i' �in the > > >second line). �You'll have to change the variable names above to fit > > >your program. > > > >I would also strongly suggest using a very simple image and template > > >at first. �I very often do that because it makes it a lot easier to > > >verify that my code is working correctly. �So you might consider using > > >a simple square box of, say, 4x4 pixels (each with a value of, say, > > >100). �Then place the upper left corner of the 4x4 square box at, > > >perhaps, pixel location 50,50 within your 128x128 base image. �All the > > >other pixels should be 0. �Then your template would be the exact same > > >4x4 box starting at location 0,0. �You'd zero pad that to 128x128 > > >with, of course, 0's. > > > >After the 2D FFT's, conjugation/ multiplication and IFFT, your cross > > >correlation result (often referred to as the cross correlation > > >surface) is the real part of the output. You should get a peak at > > >location 50,50 in the real array outputs, plus a kind of cross shaped > > >bunch of smaller numbers around it, and even smaller numbers radially > > >away from the peak. > > > >Once you've got it working, move the box in the base image around to > > >different locations, recompile/run again, and you'll see that your > > >result is locating it correctly. �After that, you can move on to more > > >complex images. �And, as noted by the poster Naresh (thanks), you > > >probably should be normalizing things (the spectral content might be > > >very uneven, which could cause problems). �And you're probably already > > >aware that if your base image contains a rotated version of what > > >you're trying to find with your template, then you may have to cross > > >correlate with multiple templates where each of them contains rotated > > >versions of whatever it is you're trying to find. > > > >The above should clear up your problems, but let me know if you run > > >into any more of them. > > > hi > > > thanks for the code. > > I am little bit confused regarding the 3D variable in the code, exactly > > what is 3D, it is a conjugate? If its a conjugate then in the code if we > > multiply by -1 insted of 3D then will it work? > > I have used your code in my program (leaving the 3D variable out), still i > > am getting a noisy image in the output. > > > here's the multiplication code, where img3 & img11 are real part of image > > and template and img4 & img22 are imaginary part of image and template: > > > for(row=0; row<128; row++) > > { > > for(col=0; col<128; col++) > > { > > � � �img1[row][col] = img3[row][col]*img11[row][col] + > > ... > > read more �- Hide quoted text - > > - Show quoted text -Dang! One of these days I'll learn how to post - just click on the 'read more' in the last one (must have pasted it in wrong). [Message to self: engage brain before posting]
