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

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 ?
>