Previous Approach: Cross-Correlation

The conventional approach to performing pattern detection utilized cross correlation. Cross correlation is identical to convolution, except that one of the sequences (images) is not flipped left to right and up and down. Because of this property, cross correlation accurately indicates the existence and location of a template in an image. The formula for the cross-correlation is as follows:

As the formula indicates, a copy of the template "h" is slid across the reference "f," and the two are multiplied together at each point. The results of each of these multiplications is summed, and we have the correlation. As the sum would indicate, we can expect the highest value to be returned when a template overlays its matching pattern within the image. In this special case, white maps to the highest number in a grayscale colormap. To accurately find the point at which the template is located, simply taking the correlation is not sufficient. The effect of passing an image over solid backgrounds must be eliminated, since such an operation generates an erroneous peak in the data. This problem is easily solved by normalizing the correlation function:

"i" is a matrix of ones with size equal to the size of the template. By dividing out this "magnitude," the resulting correlation has been normalized, and the problem mentioned above is eliminated.

Although the cross-correlation function accurately detects a pattern matching the template in the image, there are faster methods for detection.

Here is a matlab file which takes as its inputs to .gif files and returns the CROSS CORRELATION between them, or, in other words, finds the template within the picture if it exists.

function CORRloc

clear close all

tmpl = input('Template to find? ','s'); ref = input('Reference? ','s'); threshold = input('Threshold? ');

tic flops(0)

[templ,map] = gifread(tmpl); [refer,map] = gifread(ref);

refer=refer-1; templ=templ-1;

raw = xcorr2(refer,templ);

refersqr = refer.^2; flat = ones(size(templ)); norml = xcorr2(refersqr,flat); rtnormal=norml.^0.5;

rtnormal=rtnormal+0.1; normalized = raw./rtnormal;

most=max(max(normalized)); location = (normalized>=most-threshold)+1;

colormap(gray(2)); image(location);

flops toc

We have also included the Matlab file for implementing the CONVOLUTION. Notice that the pattern template is flipped in both directions before it is convolved with the image.

function CNVloc

clear close all

tmpl = input('Template to find? ','s'); ref = input('Reference? ','s'); threshold = input('Threshold? ');

tic flops(0)

[templ,map] = gifread(tmpl); [refer,map] = gifread(ref);

refer=refer-1; templ=flipud(fliplr(templ-1));

raw = conv2(refer,templ,'same');

refersqr = refer.^2; flat = ones(size(templ)); norml = conv2(refersqr,flat,'same'); rtnormal=norml.^0.5;

rtnormal=rtnormal+0.1; normalized = raw./rtnormal;

most=max(max(normalized)); location = (normalized>=most-threshold)+1; colormap(gray(2)); image(location);

flops toc

Last updated: December 17, 1996

Home Page