Java code for correlation in frequency domain

46 views
Skip to first unread message

MyName

unread,
Feb 26, 2004, 12:14:43 AM2/26/04
to
I'm looking for java code or generic algorithm to compute fast correlation
between an image and a template using fft.
I'm using convolution to compute correlation by now, i.e. fast normalized
cross correlation (J. P. Lewis
http://www.idiom.com/~zilla/Work/nvisionInterface/nip.html#foot263) but
working in spatial domain it's too much expensive for my task.
Another question is about correlation by convolution. I've noticed that
correlation coefficent seems to give a spurious value in high contrast areas
of images, such as black and white stripes, or in general regions of an
image with a clear separation between black and white areas. Is this due to
the to the fact that in the formula mentioned in the URL above appears both
image mean and template mean? there's a way to deal with such problem?
Thanks

Navhpf

unread,
Feb 27, 2004, 4:28:04 PM2/27/04
to
Have a look at ImageJ at http://rsb.info.nih.gov/ij/

There are several FFT plugins and some correlation plugins as well.

Martin Leese

unread,
Mar 4, 2004, 12:24:25 AM3/4/04
to
MyName wrote:
...

> Another question is about correlation by convolution. I've noticed that
> correlation coefficent seems to give a spurious value in high contrast areas
> of images, such as black and white stripes, or in general regions of an
> image with a clear separation between black and white areas. Is this due to
> the to the fact that in the formula mentioned in the URL above appears both
> image mean and template mean? there's a way to deal with such problem?

Yes, it's because of the image mean (in this context, called the
energy in the image). The energy in the template is not a problem
because it is a constant, and so does not shift the position of
the maximum.

The way to deal with it is to not use cross-correlation. Instead
use the sum of the square of the error. Something like:
Sum over region( (template - image)**2 )
and this equals:
Sum over region( template**2 - 2*template*image + image**2 )
where:
Sum over region( template**2 ) is the energy in the template
Sum over region( template*image ) is the cross-correlation
Sum over region( image**2 ) is the energy in the image

Note that the sum of the square of the error only corresponds (in
position of the maximum) to the cross-correlation when the energy
in the image is zero. Hence, cross-correlation is only effective
for template matching when the image has a background which is
mostly dark and mostly uniform. White letters on a black
background, for example, fits this criteria. An image which has
large areas with a light background does not.

The catch -- and in your case a huge catch -- is that the sum of
the square of the error cannot be calculated in the frequency
domain; if you use this technique then you are stuck in the
spatial domain.

--
Regards,
Martin Leese
E-mail: ple...@see.Web.for.e-mail.INVALID
Web: http://members.tripod.com/martin_leese/

muckyduck

unread,
May 28, 2004, 7:29:42 PM5/28/04
to
In article <7hf%b.32353$IT2.1...@news4.tin.it>, MyName
<cic...@tiscalinet.it> wrote:

>
> > Another question is about correlation by convolution. I've noticed that
> > correlation coefficent seems to give a spurious value in high contrast areas
> > of images, such as black and white stripes, or in general regions of an
> > image with a clear separation between black and white areas. Is this due to
> > the to the fact that in the formula mentioned in the URL above appears both
> > image mean and template mean? there's a way to deal with such problem?
>

> Yes, it's because of the image mean (in this context, called the
> energy in the image). The energy in the template is not a problem
> because it is a constant, and so does not shift the position of
> the maximum.
>
> The way to deal with it is to not use cross-correlation.

I think you've got it wrong (or are referring to regular
cross-correlation).

The point of using the _normalized_ correlation described in article is
to avoid exactly this problem. The correlation is divided by the
energy at the local point in the image, so the brightness of the image
no longer matters, only the "shape" of the pattern in the image.

Reply all
Reply to author
Forward
0 new messages