I'm posting again to make sure you got that previous one. I guess I must have cut and pasted the text in wrong because I got that 'read more' link instead of the text. If you click on the 'read more' link, you have to scroll all the way to the bottom to see the post. I know I can get rid of it for this post by deleting all the quoted text above it. The problem with your code was easy to spot, and the suggested change was made in the Sept. 4, 11:52 post, so I won't repeat it here. Just click on the 'read more' link within that post and scroll down to the bottom. Sorrry for the inconvenience (perhaps one day I will learn to post correctly).
Image correlation via FFT. Not working, need help
Started by ●September 1, 2008
Reply by ●September 7, 20082008-09-07
Reply by ●September 9, 20082008-09-09
On Sep 2, 2:22 pm, naresh <nareshredd...@gmail.com> wrote:> 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 > NareshHi i want the paper can you send me.. mine is krsheshu@deeopl.com i don't have your mailing address... the groups doesn't provide it ( last bytes are just some dots) so please send it to me...
Reply by ●September 13, 20082008-09-13
hi thank you very much for your post. Sorry, i was out for some days so couldn't reply. I tried your multiplication code and the previous code which i used, i got two different results. I also tried correlation using matlab and got totaly different result. You can check the results here: matlab result: http://testftpc.awardspace.com/fft/matlab.bmp your multiplication code: http://testftpc.awardspace.com/fft/out.bmp previous multiplication code: http://testftpc.awardspace.com/fft/out1.bmp I am not able to understand what's going wrong. I am suspecting the multiplication is going wrong. I wish if its possible that I can take a look at your c++ template matching code, it would be a great help to me. Thanks Mickey>On Sep 4, 11:52=A0pm, kevinjmc...@netscape.net wrote: >> On Sep 4, 6:48=A0am, "devil6600" <devil6...@gmail.com> wrote: >> >> >> >> > >On Sep 2, 5:10=3DA0pm, "devil6600" <devil6...@gmail.com> wrote: >> > >> >On Sep 2, 12:42=3D3DA0am, kevinjmc...@netscape.net wrote: >> > >> >> On Sep 2, 12:34=3D3DA0am, kevinjmc...@netscape.net wrote: >> >> > >> >> > On Sep 1, 9:56=3D3DA0am, "devil6600" <devil6...@gmail.com>wrot=>e: >> >> > >> >> > > hi >> >> > >> >> > > I have written a program that performs correlation via FFT.T=>he >> > >> conce=3D3D >> > >> >pt is >> > >> >> > > to search a base image for occurrences of a particularshape.=> To >> > d=3D >> > >o >> > >> t=3D3D >> > >> >his >> > >> >> > > first I took the FFT of the base image, then FFT of theshape>> > >> (padded=3D3D >> > >> > with >> > >> >> > > zeros) which I want to search in the base Image. After thisI>> > got =3D >> > >4 >> > >> a=3D3D >> > >> >rrays >> > >> >> > > of real and imaginary data. Next I multiplied the array(real=> & >> > >> imagi=3D3D >> > >> >nary) >> > >> >> > > of the shape with the array of the base image and took its >> > IFFT. >> > >> Fina=3D3D >> > >> >lly, >> > >> >> > > after IFFT i got two arrays (real & imaginary), next Isquare=>d >> > and >> > >> ad=3D3D >> > >> >ded >> > >> >> > > both the arrays (the real and the imaginary) and took its >> > square >> > >> root=3D3D >> > >> >. >> > >> >> > > As expected, the result should be that I should get asharp>> > clear >> > >> pea=3D3D >> > >> >k. >> > >> >> > > But in fact I get a noisy image. Please correct me if theabo=>ve >> > >> proce=3D3D >> > >> >dure >> > >> >> > > is incorrect. >> >> > >> >> > > I think if there would have been any problem in my FFT &IFFT>> > >> routine=3D3D >> > >> > then >> > >> >> > > I should have not got my base image back, once I haveperform=>ed >> > a >> > >> FFT=3D3D >> > >> > on it >> > >> >> > > and then did a IFFT. >> >> > >> >> > > If anyone has the desire to take a look of my FFTcorrelation>> > >> results=3D3D >> > >> > 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=3D3D>ENA.bmp >> >> > >> >> > > IFFT performed on base >> >> > >> image:http://testftpc.awardspace.com/fft/(I)LE=3D3D>NA.bmp >> >> > >> >> > > Target shape:http://testftpc.awardspace.com/fft/ll.bmp >> >> > >> >> > > CorrelationResult:http://testftpc.awardspace.com/fft/CORR.bm=>p >> >> > >> >> > > FFT & IFFT >> >> > routine:http://testftpc.awardspace.com/fft/fft_ifft.txt >> >> > >> >> > > Convolution >> >> > >> routine:http://testftpc.awardspace.com/fft/CORRELATION.tx=3D3D >> >> > >> >t >> >> > >> >> > > Thanks very much in advance, >> >> > >> >> > > Mickey >> >> > >> >> > I didn't check your links, but from your description it seemsa=>s >> > if >> > >> >> > you're doing the convolution of your image and base image(or>> > >> >> > template). =3D3DA0To do a cross correlation, you've got toconj=>ugate >> > o=3D >> > >ne >> > >> of >> > >> >> > them in the frequency domain before doing themultiplication.>> > =3D3DA0T=3D >> > >he >> > >> >> > conjugation performs a 'time reversal' in the frequencydomain>> > (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 youconjugate.>> > =3D3DA0=3D >> > >In >> > >> >> > your case, since you're doing template matching, you'dconjugat=>e >> > the >> > >> >> > FFT result of your base image before doing the multiplicationo=>f >> > 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 baseima=>ge >> > >> >> > (change signs of all imaginary parts: i[n] =3D3D3D - i[n]). >> > =3D3DA0Then >> > >> multipy >> > >> >> > the 2 transforms and inverse FFT.- Hide quoted text - >> >> > >> >> > - Show quoted text - >> >> > >> >> Ooops. =3D3DA0Meant to say: conjugate the FFT results of yourzer=>o >> > padde=3D >> > >d >> > >> >> shape image in that last paragraph.- Hide quoted text - >> >> > >> >> - Show quoted text - >> >> > >> >Me again (third times the charm?). =3DA0I actualy did downloadone =>of >> > your >> > >> >links (the multiplication code) and printed it out. =3DA0After >> > attending >> > >> >to some other things, I decided to take a quick look at it.=3DA0I>> > cannot >> > >> >even remotely imagine how that code could be working properly.=3DA=>0You >> > >> >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). =3DA0It should be zero padded tobe>> > 128x128 >> > >> >points. >> > >> >3) 2D FFT the 128x128 template. >> > >> >4) conjugate the result of the template transform (a veryimportant>> > >> >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 int=>he >> > >> >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 amdoing>> > some >> > >> mistake in taking the conjugate of the imaginary part. What I didfo=>r >> > >> taking conjugate is just multiplied -1 with the imaginary arrayfor =>all >> > t=3D >> > >he >> > >> rows and columns in the template image. And then multiplied thebase>> > imag=3D >> > >e >> > >> and the template image for every pixel. Am i correct? >> >> > >> i have uploaded the conjugate and multiplication routine here, ifyo=>u >> > can >> > >> take a look i'd really appreciate >> >> > it:http://testftpc.awardspace.com/fft/m=3D >> >> > >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. =A0Here's some code from a C++ template matching programth=>at >> > >I've used. =A0Both the image and zero padded template have beenforwar=>d >> > >FFT'd, and the conjugation is done when doing the multiplies (Ihope>> > >it shows up with the correct indentation and all): >> >> > >// multiply 2D FFT of images; =A0conjugate 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:=A0(=>R1 >> > >+ I1j)*(R2 - I2j) =3D3D (R1*R2 + I1*I2) + (- R1*I2 + R2*1I)j >> >> > >for(col =3D3D 0; col < N; col++){ >> > > =A0 =A0for (row =3D3D 0; row < N; row++){ >> > > =A0 =A0 =A0 =A0t =3D3D image1r[row][col]*image2r[row][col] +image1i[=>row] >> > >[col]*image2i[row][col]; >> > > =A0 =A0 =A0 =A0image1i[row][col] =3D3D -image1r[row][col]*image2i[ro=>w][col] + >> > >image2r[row][col]*image1i[row][col]; >> > > =A0 =A0 =A0 =A0image1r[row][col] =3D3D t; >> > > =A0 =A0} >> > >} >> >> > >You've only got two multiplies in your code, so I strongly suspect >> > >that it's wrong (easy thing to do). =A0In the above, we'remultiplying>> > >the result of two FFT's, so we have real/imaginary times anotherreal/>> > >imaginary. =A0The temp variable 't' above is to avoid overwriting >> > >'image1r' (the original values are needed to compute 'image1i' =A0int=>he >> > >second line). =A0You'll have to change the variable names above tofit>> > >your program. >> >> > >I would also strongly suggest using a very simple image andtemplate>> > >at first. =A0I very often do that because it makes it a lot easierto>> > >verify that my code is working correctly. =A0So you might considerusi=>ng >> > >a simple square box of, say, 4x4 pixels (each with a value of, say, >> > >100). =A0Then place the upper left corner of the 4x4 square box at, >> > >perhaps, pixel location 50,50 within your 128x128 base image. =A0Allt=>he >> > >other pixels should be 0. =A0Then your template would be the exactsam=>e >> > >4x4 box starting at location 0,0. =A0You'd zero pad that to 128x128 >> > >with, of course, 0's. >> >> > >After the 2D FFT's, conjugation/ multiplication and IFFT, yourcross>> > >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 crossshaped>> > >bunch of smaller numbers around it, and even smaller numbersradially>> > >away from the peak. >> >> > >Once you've got it working, move the box in the base image aroundto>> > >different locations, recompile/run again, and you'll see that your >> > >result is locating it correctly. =A0After that, you can move on tomor=>e >> > >complex images. =A0And, as noted by the poster Naresh (thanks), you >> > >probably should be normalizing things (the spectral content mightbe>> > >very uneven, which could cause problems). =A0And you're probablyalrea=>dy >> > >aware that if your base image contains a rotated version of what >> > >you're trying to find with your template, then you may have tocross>> > >correlate with multiple templates where each of them containsrotated>> > >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 ifw=>e >> > multiply by -1 insted of 3D then will it work? >> > I have used your code in my program (leaving the 3D variable out),stil=>l i >> > am getting a noisy image in the output. >> >> > here's the multiplication code, where img3 & img11 are real part ofima=>ge >> > and template and img4 & img22 are imaginary part of image andtemplate:>> >> > for(row=3D0; row<128; row++) >> > { >> > for(col=3D0; col<128; col++) >> > { >> > =A0 =A0 =A0img1[row][col] =3D img3[row][col]*img11[row][col] + >> >> ... >> >> read more =BB- 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] >
Reply by ●September 14, 20082008-09-14
I sent and email to what I presumed to be your email address, and it was supposedly delivered, so I'm going to presume that you got it. It contains some attachments: 1) a .pdf file containing some simple image processing examples like filtering, cross correlation for motion detection, template matching, etc., and 2) some C++ code used as examples within the .pdf text. As for your revised results, ...... hmmm. The MATLAB result looks weird, almost as if there's no attempt to match with the edges. And the previous multiplication code doesn't look well at all (there's really something wrong with that one). And the result using my multiplication code doesn't look all that terrible, other than the fact that it's in the wrong place, and the cross shape appearance is rather disconcerting. In viewing your image and template, it seems that the template is taken directly from the 64,64 point in the LENA image, and it extends down and right by about 20 points. And both image and template are 128x128. And the template is properly located starting at the 0,0 point and it's zero filled. So far so good. What you should get after the template matching is a sharp peak at the 64,64 point. What it means is that the template matching process has found the template within the image, and it begins at that point (i.e.: the upper left corner of the template is located at that point). You wouldn't happen to be rotating your correlation outputs, would you? That's almost always done when doing motion detection using 2D cross correlation. But normally, you wouldn't do that with template matching. If in fact you are rotating the correlation result, then the peak (at 100, 98) shown using my multiplication would be just about right. In fact, it's just about perfect. But that's only if you're rotating outputs, and you'll probably quash my hopes by telling me that you're not doing it that way. And, as noted, I don't like that cross shaped appearance when using my multiplication at all. With no output rotation, there should be a peak at 64,64, and more of a circular appearance around it, where the numbers get smaller as you move away in a radial direction. One possibility is to add some simple attempt at normalization. The simplest way is: after transforming both image and template, zero out the DC points (the 0,0 point) for each of them before doing the rest of the processing. Typically, the DC component contains a lot of low frequency background stuff, and it's usually a large number. Since template matching is based on cross correlation, those big numbers can interfere with locating the template within the image. So try that at first, and see if that helps. Let me know what you get. I'll think a bit more as to what kind of problem could be causing those unusual outputs.
