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.