DSPRelated.com
Forums

Image correlation via FFT. Why doesn't this work?

Started by typewriter April 20, 2007
On Apr 25, 5:58 pm, "typewriter" <kristopher.coll...@gmail.com> wrote:
> >>I have a program that performs FFT convolution to search > >> for occurrences of a small image inside another image. > >> Online Applet :http://www.viz.nu/fft/ > > Rune said: > > >First: Correlation methods only looks for "similar" results, not "the > >same." So if the texture of your image is similar across, you might > >find partial matches all over, meaning that the actual match does > >not stand as clearly out as you might have hoped for. > > Right, but if the small image is cut out directly from the larger one, > the convolution should generate a maximum at the match point(however > unclear it may be to the naked eye). Also, I *want* to see "similar" > areas, but have the "best" match appear as the maximum, as I understand > this method to work. (see:http://www.dspguide.com/ch24/6.htm) > > >As for correlaion: I am not sure is is the correct method to use. > >Correlation works for zero-mean signals, as found in radar, sonar > > Perhaps I'm not performing "textbook" correlation. Correct, images are > not zero mean, but it should still work. This method has been used > succesfully by others, ( see :http://www.gamedev.net/reference/programming/features/imageproc/page3... > ). I could subtract the mean, but doing so for each subframe would really > slow it down. > > I am using the same test images as the URL above, with which the author > sucessfully demonstrated this concept. Although those images are among > the ones that my program fails on! But it *does* work with others.. > > _____________________________________ > Do you know a company who employs DSP engineers? > Is it already listed athttp://dsprelated.com/employers.php?
By simply doing correlation you have no guarantee that the maximum will be at the proper alignment. I would expect the proper alignment would be at a local maximum, but there may be many of those. It does not have to be at the global maximum. Rune has jogged my memory, we computed a "covariance coefficient" for each offset to align the images. At worst the mean and variance estimated for every point can be computed with 2 more FFT filtering operations. So doing the filtering this way costs about 3X the computations required for the original filtering. There might be a more optimal way computationally but this simplified the code by using the same FFT filtering 3X. Dirk
First, Dirk, Rune, and the others I really appreciate your time to help
me.

I renormalized image data to [-1.0,1.0], which has improved the results of
the program.  Now, 6 out of the 8 test images are performing as expected! 
This is good news.  I wish one of my cited resources had mentioned this
explicetly.  My uni Fourier course never got into non-zero-mean stuff, or
2D/images so I'm still learning!  

>I would expect the proper alignment would be at a local maximum. >It does not have to be at the global maximum.
Yes, the alignment seems to always be represented by a local maximum. I'm just trying to wrap my head around WHY there would be a global maximum from convolution that would NOT be the exact match.. And my matches are EXACT, since the kernel image is copied straight from the large image. _____________________________________ Do you know a company who employs DSP engineers? Is it already listed at http://dsprelated.com/employers.php ?
<clipped>
> > Yes, the alignment seems to always be represented by a local maximum. > I'm just trying to wrap my head around WHY there would be a global > maximum from convolution that would NOT be the exact match.. And my > matches > are EXACT, since the kernel image is copied straight from the > large image. >
<clipped> typewriter, Suppose you had a section of the larger image that was constant at value 0.5 and another section that was constant at 1.0, each of a size larger than the smaller image to be convolved with it. One will give you twice the convolution output than the other, but the match detail is no better. Next, in addition, suppose you have a section identical to the smaller image (rotated as required), but scaled so that the maximum image value is 0.49. Now the convolution with the correct image will give a convolution value less than the convolution with either of the other constant examples, but clearly it would still be the section you were looking for. Without any control on the gain, any none-zero section can be scaled to produce a larger convolution output than the uscaled desired section. Clearly there is a great deal of potential to get a global max "match" that has nothing to do with the section you are trying to find. Dirk
On 26 Apr, 22:22, "typewriter" <kristopher.coll...@gmail.com> wrote:

> >I would expect the proper alignment would be at a local maximum. > >It does not have to be at the global maximum. > > Yes, the alignment seems to always be represented by a local maximum. > I'm just trying to wrap my head around WHY there would be a global > maximum from convolution that would NOT be the exact match..
These are two questions: 1) Why is there always a global maximum? 2) Why is a pattern match not the global maximum? Question 1 first, the only way to NOT have a global maximum, is to have a constant match all over. That's an almost impossible event, so there is always at least one global maximum. As for why the match with an exact template is not the global maximum, there are two factors: The effect of normalization, as Dirk mentioned, and the effect of a non-zero mean, as I mentioned in my first post. Just play with the numbers and see that either one might easily mess up the correlation coefficients. Rune
did you take the conjugate, and do you need to use fftshift to move it to
the center?

in matlab, try:

im1 = randn(15);
im2 = zeros(15);
im2(6:10, 6:10) = im1(8:12, 8:12);
imagesc(fftshift(ifft2(fft2(im1).*conj(fft2(im2)))))



> >Hello, > >I have a program that performs FFT convolution to search >for occurrences of a small image inside another image. > >I feel like I understand the concept, but my program doesn't >do what it should. The small search image is simply cut out from the >larger image, so I should see a bright spike in the resultant FFT >convolution. But I am seeing a very ambiguous result. > >I created a web page with pictures and my fairly basic source code, if >anyone has the desire to take a look.. I'd really appreciate it. > >The web page is located at: http://viz.nu/fft/ > >Thanks very much in advance, > >Kristopher > > >_____________________________________ >Do you know a company who employs DSP engineers? >Is it already listed at http://dsprelated.com/employers.php ? >