peterd
peterd

Reputation: 99

Special Situation in Normalized Cross Correlation for template matching

I was working on the Normalized Cross Correlation for Template Matching in Spatial domain. While the method is slow, it works good enough for my purpose. But I saw a weird thing in there. Let me explain the situation below:

91 91                        91 91 9 9
91 91                        91 91 9 9
                                   8   6 7 8

pattern image          source image.

Now, when NCC goes through this: It finds the mean of the template image as 91 and underlying source image also as 91 and then it subtracts the intensity value from the pixel which essentially takes all terms in the formula to zero resulting in an undefined correlation value and no matches are found even when there is a perfect match.! How to get around this situation? I am using the following formula: from the excellent source by J. P. Lewis

enter image description here

Also, when I modified the formula to subtract (mean/2) from every pixel intensity, it seemed to work fine but I am concerned as to how much vulnerable to Illumination this new correlation coefficient is.

Edit: Conditions even worsened when I took a 1 X 1 pattern image and had multiple occurrences in source image. Using the above modified version I was unable to find appropriate matches. I would love to look into various work arounds many of you might have been using. Thanks.!

Upvotes: 2

Views: 2673

Answers (1)

Niki
Niki

Reputation: 15867

The idea of the normalized cross correlation is that the similarity doesn't change if you add an arbitrary number to every pixel or multiply every pixel by an arbitrary (non-negative) number. Now take any 2x2 pixel area in the search image, e.g.

91  9
 6  7

Multiply this by 0 and add 91 - and you have a perfect match. So in a nutshell: You can't match a "flat" template using normalized cross-correlation. Or a "flat" area in the search image, either.

Note that this isn't a "bug" in the normalized cross correlation. The effect you're seeing makes perfect sense. Imagine someone hands you a completely black photograph and asks you what you see. Your answer wouldn't be "I have perfect match for the batmobile, because it's completely black", your answer would be "I can't tell, there's too little contrast in the image". Which is precisely what the NCC is trying to tell you with the division by zero.

Also, when I modified the formula to subtract (mean/2) from every pixel intensity

You mean, you replaced the mean's in the numerator and denominator by mean/2? That doesn't sound like a good idea. If the template or search image area contains only zeros, you will still get a division by zero. More importantly: you're calculating a quantity that has no real meaning (at least none that I can think of). For example, the average brightness of the search area region will influence on the matching result.

I would love to look into various work arounds [...]

The obvious ad-hoc workaround would be to add a small quantity to the denominator, so a "flat" area in the search image won't lead to devision by zero. Then you get (more or less) a similarity measure that doesn't change if you add an arbitrary number to every pixel or multiply every pixel by an arbitrary (non-negative) number unless that number is very close to 0.

But that would give you a 0 match for any flat search area region or flat template. Which (as explained above) makes perfect sense. If you want different behavior in this case, you don't want a normalized cross correlation.

An alternative similarity measure might be squared euclidean distance. You can optionally subtract the mean of the template and search area before calculating the difference. Then you get a similarity measure that doesn't change if you add an arbitrary number to every pixel. But it will change if you multiply every pixel by some value.

Upvotes: 2

Related Questions