normxcorr2 for template matching: old error in documentation ?

In the current r2015a online documentation's example of template matching using normxcorr2 ( mathworks.com/help/images/ref/normxcorr2.html ), the offset of correlation array, because of zero padding is assumed to be the size of template:

yoffSet = ypeak-size(onion,1);
xoffSet = xpeak-size(onion,2);

However, when I run through the example on my machine (r2011b), and extract the rectangle matching region of 'peppers' based on the above values ...

match = peppers(yoffSet:yoffSet+size(onion,1)-1, xoffSet:xoffSet+size(onion,2)-1);

... the resulting crop is not equal to 'onion'. It is in fact offset by 1*1 pixel. Don't know if this can be caused by my older Matlab version.

From what I can understand from normxcorr2 code and conv2 help, the padding is in fact of width (size(T)-1)/2 on each side for a template with an odd size (for an even template size, the padding is size(T)/2 on the left and top, and size(T)/2 - 1 on the right and bottom). These would be the correct offset values for the central pixel of template (when there is one, i.e. odd template size).

In the end, the offset for the top-left pixel of the template-matching region should rather be size(T) -1. Am I right ?

Answer 1

[Alex Taylor]

Hi Emmanuel,

Sorry for the long delay since you posted this question. Hopefully this will still help. A few points of clarification and a bit of code should hopefully help.

1) If you think about this problem in the spatial domain as a convolution, the size of the resulting correlation matrix is not related to a chosen "zero padding". By definition, the full convolution of a 2-D matrix A of size [Ma,Na] and a matrix B of size [Mb,Nb] produces an output correlation matrix C of size: [Ma+Mb-1,Na+Nb-1].

2) You can see that the computation of the offset is correct most easily by creating a small problem in which you adjust where the template image is sliced from the original image and see if you accurately can recover the offset. To be clear, the meaning of "offset" is the translation of the template image that is required to have the content in both images align starting from an alignment in which first row and first column of both images are assumed to be the aligned (the upper left corner of both images).

A = magic(5);
template = A(2:4,3:5);

c = normxcorr2(template,A);

[ypeak, xpeak] = find(c==max(c(:)))

yoffSet = ypeak-size(template,1)
xoffSet = xpeak-size(template,2)

If you run this example, you would expect xoffset to be 2 and yoffset to be 1, and that's what you get. If you change the definition of template to be a different subset of A, you will again see that the recovered offset is correct.

3) I'm not clear on how R2011b factors into this, however, the definition of the normalized cross correlation matrix and how you compute offsets has not changed release to release. The current example is the correct way to recover the offset. I can't run R2011b easily at the moment, so hopefully this will be enough.

Answer 2

[Emmanuel]

Thank you Alex for clarifying this. Especially useful was the "translation" definition of offset you gave. Hence if the xoffset is n, then the first, 'top-left' pixel of matching region in image A has x = n + 1. My mistake, I forgot that the pixel coordinates system starts at 1 of course.

I will correct my code as such:

 match = peppers((yoffSet+1):yoffSet+size(onion,1), (xoffSet+1):xoffSet+size(onion,2));

Still, I think there is indeed an error in the matlab doc ( http://fr.mathworks.com/help/images/ref/normxcorr2.html ). For identifying the matching region, the given code is:

 imrect(hAx, [xoffSet, yoffSet, size(onion,2), size(onion,1)]);

in the imrect doc, position of rectangle has the form [xmin ymin width height]. This is not in accordance with the above-mentioned definition of offset, is it ?

[Alex Taylor]

Emmanuel,

That is correct. I will make sure that this error in the documentation is corrected. The correct positioning of imrect given the computed x and y translations (offsets) should be:

imrect(hAx,[xoffSet+1,yOffset+1,size(onion,2),size(onion,1)]);

Thanks for pointing this out.