How Is Template Matching Related To Cross-correlation

Prototype-Template matching using Cross-Correlation

A searching algorithm, merely for images

Prototype-Template matching is basically finding the location of a pocket-sized patch on a large epitome.

Why is it relevant?

Well, nosotros demand to practise this matching quite frequently than you might think. The most prominent example is creating a panorama similar the ane below.

To capture such panoramas a person slowly moves the photographic camera around horizontally. Various images are captured and stitched together to create a very broad-angle and (if the person taking the panorama doesn't accept shaky hands) beautiful panoramic landscapes.

This is one of the prominent examples, other examples include 3D reconstruction which requires us to match diverse key points between images captured by 2 different cameras (stereo camera setup).

Okay, now that we know that template matching is indeed an important and integral task to many of the advanced computer vision algorithms, the next question is how exercise nosotros actually exercise it? How do we really match various points between ii images?

Intro... Cross-Correlation

Cross-correlation is one of many powerful tools to:

Find certain image content in another image
Determine the exact location of the content in the paradigm

Only, there are some assumptions under which cantankerous-correlation works. The changes between source image (template) and target prototype should be limited to:

Translation
Brightness
Contrast

Cross-correlation can be extended to take rotation into business relationship as well only that adds quite a bit of complexity as we will discover out shortly.

Okay, now that we know cross-correlation is a affair, allow's swoop deeper and understand what cantankerous-correlation is exactly and how is it done to accomplish template matching.

Defining the goal: Template Matching

Template matching is basically finding the location of a small-scale template image within a larger image.

Ordinarily, the size of template paradigm << size of the search image

Template matching trouble (Epitome past Author)

So we need to find the location of a patch (template) in a bigger image. The location of the template can exist defined by a set of offsets describing the translation of the template from the origin of the prototype coordinate system. We need to discover these offsets.

Assumptions

The offsets we need to estimate are expressed every bit geometric transformations with some assumptions. As the cross-correlation supposition is that but a translation change is present betwixt source and destination, that nevertheless holds truthful, i.e. there would be no rotation, affine, similarity transform, etc. betwixt the template and the prototype.

Radiometric transformation is also taken into consideration. Radiometric transformation accounts for the changes in brightness and contrast of the template and prototype.

There can be limited changes between the intensity values of the template and the image. The intensity values of the template must be a constant starting time (change in brightness)+ a scale factor of intensity values of the paradigm (change in dissimilarity).

Hence, the intensity values of each pixel in the template (g2) are linearly dependent on those of the image (g1). This linear relationship is defined by parameters a and b as shown higher up.

The goal of template matching is to find two parameters of offsets [u, v] defining the location of the template in the paradigm but these offsets must exist invariant to[a, b], i.due east. the location offsets should be the same even if there is a difference in brightness and contrast of the template and the image.

Quantifying the results of template matching

Now that we know the goal of template matching, the next thing we need to effigy out is how to quantify similarity, how to measure that ane location is a better match than the other?

The typical ways of measuring similarity are:

Sum of squared differences
Sum of accented differences
Maximum of differences

The issue with the in a higher place-mentioned methods is that they are not invariant nether changes in brightness or contrast. If nosotros simply add 1 to all the intensity values of our template then the output would exist completely different for the higher up measures of similarity.

But as defined in our goal, nosotros want our template matching to be invariant to the changes in brightness and dissimilarity of template and prototype. The same intensity values of the template and prototype patch are not guaranteed even though they are matching.

Hence, in the cross-correlation template matching approach, the above techniques of similarity matching are not employed. Instead, the cross-correlation function is used for measuring similarity giving the method its name.

Offset estimation quantified goal (Source)

Nosotros judge the offset [u, five] which maximizes the normalized cross-correlation coefficient ( ρ ) between template and image patch over all possible locations.

Cross-Correlation Coefficient (ρ)

The normalized cross-correlation coefficient that gives united states a mensurate of similarity between the electric current epitome patch and the template is calculated as described in the images below (directly taken from the lecture slides)

Normalized cross-correlation adding (Source)

Normalized cross-correlation calculation (Source)

Normalized cantankerous-correlation calculation (Source)

The large values of the normalized cross-correlation coefficient indicate that the template and current epitome patch are matching.

Searching for template

Okay, we have all the edifice blocks for image-template matching. Now the question is where to look in the image?

Exhaustive Search

The straightforward and simple answer is… Yep, you guessed it right, everywhere!

So we take the template and slide it over the whole prototype, calculate the normalized cantankerous-correlation coefficient for each possible location on the image and consider the location [u, 5] having the highest normalized correlation coefficient as our matching region.

As mentioned at the beginning of the post, we can have rotation into account as well. Instead of merely sliding the pattern over all the possible locations on the image nosotros also consider all the possible rotations on each and every location. This would increase the complexity past a huge magnitude but theoretically, this would handle rotational geometric transformations as well.

Coarse-to-Fine Strategy

The exhaustive search is computationally intensive. A ameliorate arroyo is to utilise an image pyramid to cut down the search space.

Nosotros make a pyramid of different resolutions of the paradigm and we start searching from the smallest epitome. Once we get the best match region we search for the template in the next higher resolution image, but only in the region corresponding to the best lucifer of the previous image. This cuts down on possible locations of search.

Summary and Conclusion

If you've gone through the consummate post you lot know that

The problem of image-template matching is a building block for solving many bigger problems similar 3D reconstruction
The goal of image-template matching is to get the location of the template in an epitome
Image-template matching is invariant to changes in effulgence and dissimilarity
Standard similarity matching functions cannot be used for prototype-template matching
Normalized cross-correlation coefficient is used for epitome-template matching

I encourage readers to go through the Cross-Correlation lecture by Cyrill Stachniss.

The lecture contains some practical examples of cross-correlation calculations that would supplement the understanding forth with the advanced topic of subpixel estimation using cross-correlation.