Correlation without pre-whitening is often misleading

Peter KootsookosFebruary 19, 20089 comments

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.

Simple black and white image.

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.

Cross-correlation

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.


Next post by Peter Kootsookos:
   The Nature of Circles

Comments:

[ - ]
Comment by SteveSmithFebruary 19, 2008
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
[ - ]
Comment by kootsoopFebruary 19, 2008
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.
[ - ]
Comment by ShagufNovember 19, 2008
The time to act is now! Green is no longer in champagne activism territory; it has firmly positioned itself in the business mainstream as the next clean engine for economic growth. With rapid strides in technology, economic pressures, high energy prices, resource shortages, environmental threats, and compliance imperatives driving unprecedented growth in green energy, the pressure on scientists, technologists, government, and the industry to develop and adopt new methods for harnessing green energy has never been this overpowering. The first of its kind in India, Green Energy Summit 2009 will provide a unique platform for debate, dialogue and action between research, industry, academia, financial organisations, entrepreneurs and government bodies worldwide. The four tiers of the summit will see a congregation of the most intelligent minds and proactive organisations to create a sustained, result-oriented mindset, bringing into picture those questions that are most relevant for India at this juncture.
[ - ]
Comment by pkuappleDecember 7, 2008
good~
[ - ]
Comment by gusthyzshubMay 26, 2010
Hi Peter, thank you for the idea. Q1: Is this prewhitening equal (to some extend) to other whitening methods, e.g. subtracting the row (or column) means from the dataset? Q2: Does prewhitening make any sense when analyzing time-domain waveforms? e.g. sending a Gaussian shaped pulse (a range of frequencies) into an optical system, and sensing the output, which can be of arbitrary shape, but Gaussian. I would be thankful if you could point me to some direction, I can get some more basic info when to use whitening on a dataset. Thank you again for your time on the article!
[ - ]
Comment by gusthyzshubJune 10, 2010
Q3: By diff-ing a matrix the number of columns decreases by one (the first column vanishes). Is there any appropriate method to generate the missing column for later compatibility?
[ - ]
Comment by jutJanuary 18, 2012
This is not a blog post, it's a brain fart. Post links to interesting things on your facebook, not on a site dedicated to embedded.
[ - ]
Comment by driciMarch 14, 2014
Normalized correlation value in altboc programme in matlab PLEASE HELP ME this programe is a importance for me
[ - ]
Comment by driciMarch 14, 2014
sir please help me to make this program
Normalized correlation value in altboc modulation in gps Galileo(The Galileo E5 AltBOC) programme in matlab PLEASE HELP ME this programe is a importance for me

To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.

Registering will allow you to participate to the forums on ALL the related sites and give you access to all pdf downloads.

Sign up
or Sign in