So template matching using correlation is available in a lot of computational packages; OpenCV matchTemplate(), scipy.signal.correlate2d(), IPP CrossCorrNorm, etc.

But they all either evaluate offsets for which the template is fully inside the image, or use a boundary condition like padding or wrapping to evaluate offsets where the template hangs outside the image. I don't like that, because in general there's no good reason to believe those various kinds of pads are going to correlate with the overhanging portion of the template.

Is there any implementation out there which includes a boundary condition like 'truncate', where normal 'full' correlation is computed for all template offsets within the image, but also for all offsets where the template sticks out, the correlation is computed only for the subset of template pixels within the image?

At the extreme offsets, the template and image would share only one pixel, at which point normalized correlation is undefined (because of divide by standard deviation of 1 sample = 0), but those corners of the correlation surface can just be 0.

The benefit would be to be able to match a template even if it appears only partially in the image (see illustration below). It would be up to the caller to determine how close to the edge of the extended correlation surface (what fraction of the template) to accept as a match.

For an Image of size HxW and a template of size hXw, the resulting full correlation surface is (H-h+1)x(W-w+1), but for this extended/dynamic/partial template matching the correlation surface would be of size (H+h-1)x(W+w-1) (and again, the corners would be 0 because they are undefined)

I have an implementation of this, it's not that hard, but it's also not efficient. Well-optimized image correlation takes good advantage of repeated sums/products. Before I spend effort on optimizing my own implementation, it would be good to know if there is already a good implementation out there.

Normal template matching finds a template only if it is fully within the image; extended/partial template matching can find templates that are only partially in the image, by correlating only within-image pixels, and not using a pad or wrap outside the image boundary


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.