Correlation without pre-whitening is often misleading

Posted by Peter Kootsookos on Feb 18 2008 under Matlab | Basics | Tips and Tricks   

White Lies

Correlation, as one of the first tools DSP users add to their tool box, can automate locating a known signal within a second (usually larger) signal. The expected result of a correlation is a nice sharp peak at the location of the known signal and few, if any, extraneous peaks.

A little thought will show this to be incorrect: correlating a signal with itself is only guaranteed to give a sharp peak if the signal's samples are uncorrelated --- for example if the signal is composed of white noise.

Most interesting signals are not white noise.

Interesting Images Are Not White

When the signals of interest are images, the problem is exacerbated because the images are very different from white noise. Eight bit gray-scale images have pixel values from 0 to 255, so they almost always have a "DC offset".

Take the following simple image as an example. The image contains 5 blobs, some of which overlap.

Suppose we wish to automate finding the blob indicated by the red line (the "known" signal). Simply using two-dimensional cross-correlation will yield the following image.

The localization of the peak in the image is not good due to the large, coalesced blob at the bottom of the image.

Make A Difference: Twice!

A simple way to both remove the DC component of the image, and to make the image "whiter" is to row-difference the image (i.e. subtract from each row the previous row). In Matlab this can be achieved with the "diff" function.

Note that both the "known" image and the image which is being searched require this pre-whitening.

Discrimination

After performing the diff operation on both the known image and the searched image, the following results.

The red point indicates the peak of the new cross-correlation. A side view of this image shows how well the peak is discriminated from other peaks.

Rate this article:
posted by Peter Kootsookos
Peter Kootsookos has worked in a mixture of academic research and commercial interests in Australia, Ireland, and the United States. His DSP interests are in estimation, filtering and extraction of information from images and video.

all articles by Peter Kootsookos

Would you like to be notified by email when Peter Kootsookos publishes a new blog?

  

Hi Peter,
This is a nice method. Any reason you want to use the difference operator in only the vertical direction? Does it make make the method better to use a full edge detection?
Regards,
Steve
tSTev

Hi Steve, thanks for the comment!
There's no reason to prefer the vertical direction over any other; that was chosen primarily for simplicity of the example. I'd have to think about whether full edge detection would improve things. The aim is spectral whiteness or uncorrelated samples. The "best" one could hope for in this regard is to filter by the inverse of the spectrum of the known signal --- "best" in the sense that if the searched image and known image are the same, this form of filtering will make the result completely spectrally white.