Skip to main content

Cross-Correlation in JAI - What Am I Doing Wrong?

12 replies [Last post]
bilokon
Offline
Joined: 2005-04-04

Dear all,

I am trying to get cross-correlation between two images (source and template) to work in Java. As far as I understand, all I need to do is

1) dft both source and template;
2) conjugate the template;
3) multiply the dft of the source with the conjugate from (2);
4) idft.

I am trying to do this, but the result is certainly wrong.

You can see my code at

http://www.bilokon.co.uk/stuff/Correlation

- source.jpg is the "big" image.
- head.jpg is the template.
- target.png is the (strange) result.
- GraphicsUtilities.java contains some wrappers for JAI calls.
- Matcher.java is the main program file.

To run: java Matcher source.jpg head.jpg target.png

(This will overwrite target.png.)

I would be very much obliged to you for any help.

Best wishes,
Paul

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
Brian Burkhalter

If there are specific capabilities offered by mediaLib which JAI does not
currently support and which would be appropriate for JAI then please file an
enhancement request at

https://jai.dev.java.net/issues/enter_bug.cgi?issue_type=ENHANCEMENT

Thanks,

Brian

On Sat, 18 Jun 2005, carsten hammer wrote:

> Is the JAI mlib identical to the medialib? Is the JAI
> mlibwrapper_jai.jar similar to the medialib wrapper? If it is the same
> can I use the medialib on windows using JAI directly? I think JAI doesnt
> offer all the methods the medialib provides.

----------------
Brian Burkhalter
Advanced Development/Media & Entertainment
Market Development Engineering
Sun Microsystems, Inc.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
This email message is for the sole use of the intended recipient(s)
and may contain confidential and privileged information. Any
unauthorized review, use, disclosure or distribution is prohibited.
If you are not the intended recipient, please contact the sender by
reply email and destroy all copies of the original message.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@jai.dev.java.net
For additional commands, e-mail: interest-help@jai.dev.java.net

Brian Burkhalter

On Mon, 13 Jun 2005 jai-interest@javadesktop.org wrote:

> Still, the result is inferior to the output of IMAGIC
(http://www.imagescience.de), a FORTRAN program that seems to be using the same approach for computing the cross-correlation in spatial domain. IMAGIC gives clear peaks at the positions of the ducks' heads. It is also much worse than the cross-correlation I computed in the real space -- that seems to work quite well, too.

Do you know what algorithm is being used there?

Brian

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@jai.dev.java.net
For additional commands, e-mail: interest-help@jai.dev.java.net

bilokon
Offline
Joined: 2005-04-04

Dear Brian,

By the looks of it, they are doing exactly the same:

IDFT(MultiplyComplex(DFT(object),Conjugate(DFT(template))))

Perhaps, this has something to do with the scaling of their Fourier transforms?

Best wishes,
Paul

bilokon
Offline
Joined: 2005-04-04

Dear Brian,

Indeed it is impossible to find any examples for cross-correlation in Fourier space (other than convolution with small kernels, filtering essentially), most of the examples are done in real space. I think this is true for JAI and other libraries.

The problem in my case is that in reality I'm not searching for ducks. I'm looking for biomolecular particles in extremely noisy electron micrographs. The templates that I'm using, as well as the images themselves, are very big. E.g. a typical template would be 20 x 20 or even 30 x 30. In real space such computations take ages.

I know that some people resort to coarsening of both the image and the template, and that kind of works. But at the same time IMAGIC uses the same algorithm as I am - in Fourier space, I made a mistake in one of my previous posts - and the result is no worse than my spatial domain computations.

I wonder what's going on. Surely something is wrong. It looks like the procedure is biased towards high frequencies (hence the high level for the background in the ducks example). Perhaps squaring might help? If so, when do you reckon I should do the squaring? I would imagine, I need to square the amplitudes, leaving the phases as they are?

Best wishes,
Paul

Kevin Ryan

> Indeed it is impossible to find any examples for
> cross-correlation in Fourier space (other than convolution
> with small kernels, filtering essentially), most of the
> examples are done in real space. I think this is true for JAI
> and other libraries.

True enough. The shift by 1/2 the image size (for power of 2 images) is
so that the results you get are offset from the image origin, not the
origin plus the offset of your pattern. Your pattern should end up
centered on your 0,0 point, wrapping around into the four corners of
your image. Then the peaks in your correlation will appear at the
appropriate locations in your output image.

> The problem in my case is that in reality I'm not searching
> for ducks. I'm looking for biomolecular particles in
> extremely noisy electron micrographs. The templates that I'm
> using, as well as the images themselves, are very big. E.g. a
> typical template would be 20 x 20 or even 30 x 30. In real
> space such computations take ages.

FFT's are the right approach, then.

> I know that some people resort to coarsening of both the
> image and the template, and that kind of works. But at the
> same time IMAGIC uses the same algorithm as I am - in Fourier
> space, I made a mistake in one of my previous posts - and the
> result is no worse than my spatial domain computations.

A critical item is image padding. If you are padding with zeros, but
have a set of images with non-zero average values, you will get bad
results in the padded sections and near the edges. I would recommend
padding with the average value of the image, or with reflected subsets
of the image (reflect around the edge so that there is no sharp
transition at the edge) prior to the FFT. Otherwise you get false edges
and correlations there.

Given that you are looking at a dark pattern on a bright background,
with large background intensity variations, you might also consider
performing a phase only correlation rather than a full correlation.
Rather than multiplying the amplitudes and subtracting the phases, just
subtract the phases. That performs a correlation looking at edges and
pretty much ignoring intensities. You might get a number of false
positive peaks due to background noise, but it will do a better job with
varying background levels.

KWR

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@jai.dev.java.net
For additional commands, e-mail: interest-help@jai.dev.java.net

Brian Burkhalter

Paul,

Hello. While I was unable to find any coding errors per se in your sample code
I was wondering why you are shifting the IDFT output image using
shiftCorrection()?

Brian

On Sat, 11 Jun 2005 jai-interest@javadesktop.org wrote:

> Dear all,
>
> I am trying to get cross-correlation between two images (source and template) to work in Java. As far as I understand, all I need to do is
>
> 1) dft both source and template;
> 2) conjugate the template;
> 3) multiply the dft of the source with the conjugate from (2);
> 4) idft.
>
> I am trying to do this, but the result is certainly wrong.
>
> You can see my code at
>
> http://www.bilokon.co.uk/stuff/Correlation
>
> - source.jpg is the "big" image.
> - head.jpg is the template.
> - target.png is the (strange) result.
> - GraphicsUtilities.java contains some wrappers for JAI calls.
> - Matcher.java is the main program file.
>
> To run: java Matcher source.jpg head.jpg target.png
>
> (This will overwrite target.png.)
>
> I would be very much obliged to you for any help.
>
> Best wishes,
> Paul
> ---
> [Message sent by forum member 'bilokon' (Paul)]

----------------
Brian Burkhalter
Advanced Development, Graphics and Media
Software Chief Technology Office
Sun Microsystems, Inc.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
This email message is for the sole use of the intended recipient(s)
and may contain confidential and privileged information. Any
unauthorized review, use, disclosure or distribution is prohibited.
If you are not the intended recipient, please contact the sender by
reply email and destroy all copies of the original message.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@jai.dev.java.net
For additional commands, e-mail: interest-help@jai.dev.java.net

bilokon
Offline
Joined: 2005-04-04

Dear Brian,

For some reason, the image is shifted by 1/2 width, 1/2 height of the padded image/template size.

I am not sure why this is the case. If you consider one of your older posts,

http://archives.java.sun.com/cgi-bin/wa?A2=ind0309&L=jai-interest&F=&S=&...

you will find that Gilmar "used a periodic shift operator to correct some problems..." I suppose I was having the same problems as he was.

Moreover, if either the image or the template did not have the dimensions 2^m x 2^n, the shift was different from 1/2 width, 1/2 height. In fact, I couldn't figure out what it was! It seemed to be a function of the dimensions of both the image and the template.

This was fixed when I padded the image and the template to the same size, so that their width and height were both powers of two and the images were located in the centre. This ensured that the periodic shift was predictable and I could correct it.

Still, the result is inferior to the output of IMAGIC (http://www.imagescience.de), a FORTRAN program that seems to be using the same approach for computing the cross-correlation in spatial domain. IMAGIC gives clear peaks at the positions of the ducks' heads. It is also much worse than the cross-correlation I computed in the real space -- that seems to work quite well, too. If you look at my result, also at

http://www.bilokon.co.uk/stuff/Correlation/

the peaks are not very clear. Plus it seems to accentuate high frequencies of the original image (see the background -- it also gives some peaks).

Do you know why this might be the case?

Thank you very much for your reply,

Best wishes,
Paul

bilokon
Offline
Joined: 2005-04-04

Brian,

P.S. Perhaps you have a sample program that achieves what I need? I would have thought that Fourier space correlation is a very common technique in template matching. Yet I couldn't find anything in jaistuff and JAI examples.

Thank you,
Paul

Brian Burkhalter

On Mon, 13 Jun 2005 jai-interest@javadesktop.org wrote:

> P.S. Perhaps you have a sample program that achieves what I need? I would have thought that Fourier space correlation is a very common technique in template matching. Yet I couldn't find anything in jaistuff and JAI examples.

We don't have an examples of that. The approach you implemented

IDFT(MultiplyComplex(DFT(object),Conjugate(DFT(template))))

is correct for cross correlation as far as I know.

In my experience I have most frequently observed a spatial domain approach
used for locating a template in an image. The template is moved around in a
search region in the image and the (normalized) cross correlation coefficient
is computed for each offset. The peak of the resulting surface then provides
the best estimate of the location of the template in the image.

Brian

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@jai.dev.java.net
For additional commands, e-mail: interest-help@jai.dev.java.net

James Cheng

Hi Paul,

On 06/13/05 06:08 PM, Brian Burkhalter wrote:
> In my experience I have most frequently observed a spatial domain approach
> used for locating a template in an image. The template is moved around in a
> search region in the image and the (normalized) cross correlation coefficient
> is computed for each offset. The peak of the resulting surface then provides
> the best estimate of the location of the template in the image.

I'd like to second Brian's point that the *normalized* cross correlation
is probably a better tool for template matching. You might find this
article about a fast NCC useful:

http://www.idiom.com/~zilla/Work/nvisionInterface/nip.html

BTW, both unnormalized and normalized cross correlation functions are
available in the latest release of mediaLib at

http://www.sun.com/processors/vis/mlib.html

where the latter was added recently per a customer's request. Currently,
both of them are implemented in spatial domain. I have just tried those
functions with your images and got a result similar to your target.png
when using CC, but a better result when using NCC.

Hope this helps,

-James

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@jai.dev.java.net
For additional commands, e-mail: interest-help@jai.dev.java.net

carsten hammer

Is the JAI mlib identical to the medialib? Is the JAI
mlibwrapper_jai.jar similar to the medialib wrapper? If it is the same
can I use the medialib on windows using JAI directly? I think JAI doesnt
offer all the methods the medialib provides.
If I understand it right the medialib is officially only on Solaris
supported.
Best regards,
Carsten

James Cheng wrote:

>Hi Paul,
>
>On 06/13/05 06:08 PM, Brian Burkhalter wrote:
>
>
>>In my experience I have most frequently observed a spatial domain approach
>>used for locating a template in an image. The template is moved around in a
>>search region in the image and the (normalized) cross correlation coefficient
>>is computed for each offset. The peak of the resulting surface then provides
>>the best estimate of the location of the template in the image.
>>
>>
>
>I'd like to second Brian's point that the *normalized* cross correlation
>is probably a better tool for template matching. You might find this
>article about a fast NCC useful:
>
> http://www.idiom.com/~zilla/Work/nvisionInterface/nip.html
>
>BTW, both unnormalized and normalized cross correlation functions are
>available in the latest release of mediaLib at
>
> http://www.sun.com/processors/vis/mlib.html
>
>where the latter was added recently per a customer's request. Currently,
>both of them are implemented in spatial domain. I have just tried those
>functions with your images and got a result similar to your target.png
>when using CC, but a better result when using NCC.
>
>Hope this helps,
>
>-James
>
>
>---------------------------------------------------------------------
>To unsubscribe, e-mail: interest-unsubscribe@jai.dev.java.net
>For additional commands, e-mail: interest-help@jai.dev.java.net
>
>
>
>
[att1.html]

James Cheng

Hi Carsten,

> Is the JAI mlib identical to the medialib? Is the JAI
> mlibwrapper_jai.jar similar to the medialib wrapper?

They are similar but not identical. The one for JAI is a subset of the
mediaLib available at http://www.sun.com/processors/vis/mlib.html .

> If it is the same
> can I use the medialib on windows using JAI directly? I think JAI doesnt
> offer all the methods the medialib provides.

A .dll or .so library for JAI is a combination of native functions and
the native part of JNI glue code, so the symbols (i.e., function names)
exported by the library are different from those in an original/full
mediaLib library. In theory, a .dll for JAI on windows can be used
directly (without JAI), but it has to be called from Java and it's not
supported by Sun.

> If I understand it right the medialib is officially only on Solaris
> supported.

That's right for the full mediaLib.

Regards,
-James

---------------------------------------------------------------------
To unsubscribe, e-mail: interest-unsubscribe@jai.dev.java.net
For additional commands, e-mail: interest-help@jai.dev.java.net