Normalized Cross Correlation (NCC) is an excellent choice for finding a given pattern in an image given a known scale and orientation. Matlab's IP toolbox normxcorr2 function does this.
However there's no way to specify which pixels of the pattern are important. This is particularly problematic because the template (i.e. pattern) matrix inadvertently specifies a rectangular ROI. So if the pattern as it appears in the image has artifacts close enough to the pattern, it will be in range of the template window and so the response will be degraded. Assuming that the nature of the problem is such that such artifacts are not actually important to the pattern match, being able to de-weight pixels away from the pattern can mitigate this.
Note: This function is more expensive than normxcorr2. It uses 3 convolutions (technically correlation) between image and template sized matrices. The convolution implementation automatically switches between frequency and spatial domains and so the time is usually “reasonable” .
The WNCC formula (but not the implementation) is the same as NCC but it with weighted variance vs regular variance, i.e.
NCC = cov(x,y)/sqrt(cov(x,x)*cov(y,y))
WNCC = wcov(x,y,w)/sqrt(wcov(x,x,w)*wcov(y,y,w))
Where “wcov” is the weighted covariance w/r to the weights “w”
(see the comments in wncc for details)
In the example (picture) above, the “template” (i.e. pattern) is a cross. The “image” has such a pattern but within the rectangular region that contains it there are two bright artifacts that degrade the performance of NCC (bottom right). The “template weights” image shows that the WNCC matching will largely ignore anything not very close to a cross shaped ROI. In particular, this weighting will allow the artifacts to be ignored. The improved result (note colorbars) is shown in the WNCC image (bottom left).
Tested in 2008a, 2008b, 2008b, 2011a
Hi Raghavan, if you could share the updated code that would be great. Thanks.
Very neat! Worked like a charm.
There is an interesting property of wncc that can be used to speed it up and, in some cases, more than compensate for the extra computations needed when compared to unweighted correlation:
The size of FFT is often not optimal when unweighted correlation is performed. By padding the template, and setting the weights corresponding to the padded region to zero, the FFTs that are required can be sped up significantly (e.g. power of 2 FFT can be over 10X faster than a prime number FFT). I actually implemented this. If anyone is interested, I can share the code (I need to extract it and clean it up first).
Works great. Thanks!
I haven't yet tried this but I've needed something similar in the past, so thank you for this submission.