Learn more about Video and Image Processing Blockset

Template Matching - Locate a template in an image

Library

Analysis & Enhancement

Description

The Template Matching block finds the best match of a template within an input image. The block computes match metric values by shifting a template over a region of interest or the entire image, and then finds the best match location.

Algorithm

The match metrics use a difference equation with general form:

denotes the metric space for n > 1.

Sum of Absolute Differences (SAD)
This metric is also known as the Taxicab or Manhattan Distance metric. It sums the absolute values of the differences between pixels in the original image and the corresponding pixels in the template image. This metric is the norm of the difference image. The lowest SAD score estimates the best position of template within the search image. The general SAD distance metric becomes:
Sum of Squared Differences (SSD)
This metric is also known as the Euclidean Distance metric. It sums the square of the absolute differences between pixels in the original image and the corresponding pixels in the template image. This metric is the square of the norm of the difference image. The general SSD distance metric becomes:
Maximum Absolute Difference (MaxAD)
This metric is also known as the Uniform Distance metric. It sums the maximum of absolute values of the differences between pixels in the original image and the corresponding pixels in the template image. This distance metric provides the norm of the difference image. The general MaxAD distance metric becomes:

which simplifies to:

Main Dialog Box

The Main pane of the Template Matching block appears as shown in the following figure.

Match metric

Select one of three types of match metrics:

Sum of absolute differences (SAD)
Sum of squared differences (SSD)
Maximum absolute difference (MaxAD)

Output

Select one of two output types:

Metric matrix
Select this option to output the match metric matrix. This option adds the Metric output port to the block.
Best match location
Select this option to output the location index of the best match. This option adds the Loc output port to the block. When you select Best match location, the Search method, Output NxN matrix of metric values around best match, and Enable ROI processing parameter options appear.

Search method

This option appears when you select Best match location for the Output parameter. Select one of two search methods.

Exhaustive
Three-step

Output NxN matrix of metric values around best match

This option appears when you select Best match location for the Output parameter. Select the check box to output a matrix of metric values centered around the best match. When you do so, the block adds the NMetric and NValid output ports.

N

This option appears when you select the Output NxN matrix of metric values around best match check box. Enter an integer number that determines the size of the N-by-N output matrix centered around the best match location index. N must be an odd number.

Enable ROI processing

This option appears when you select Best match location for the Output parameter. Select the check box for the Template Matching block to perform region of interest processing. When you do so, the block adds the ROI input port and the Output flag indicating if ROI is valid check box appears.

Output flag indicating if ROI is valid

This option appears when you select the Enable ROI processing check box. Select the check box for the Template Matching block to indicate whether the ROI is within the valid region of the image boundary. When you do so, the block adds the ROIValid output port.

Fixed-point Dialog Box

The Fixed-point pane of the Template Matching block dialog box appears as shown in the following figure.

Rounding mode

Select the rounding mode for fixed-point operations.

Overflow mode

Select the overflow mode for fixed-point operations.

Wrap
Saturate

Accumulator

Use this parameter to specify how you would like to designate the accumulator word and fraction lengths.

When you select Same as product output the characteristics match the characteristics of the product output. See Multiplication Data Types for illustrations depicting the use of the accumulator data type in this block:
When you select Binary point scaling, you can enter the Word length and the Fraction length of the accumulator, in bits.
When you select Slope and bias scaling, you can enter the Word length, in bits, and the Slope of the Accumulator. All signals in the Video and Image Processing Blockset software have a bias of 0.
The block casts inputs to the Accumulator to the accumulator data type. It adds each element of the input to the output of the adder, which remains in the accumulator data type. Use this parameter to specify how to designate this accumulator word and fraction lengths.

Lock scaling against changes by the autoscaling tool

Select this parameter to prevent the autoscaling tool in the Fixed-Point Tool overriding any fixed-point scaling you specify in this block mask. For more information, see fxptdlg, a reference page on the Fixed-Point Tool in the Simulink documentation.

Supported Data Types

Port	Supported Data Types
I (Input Image)	Double-precision floating point Single-precision floating point Fixed point (signed, unsigned or both) Boolean 8-, 16-, and 32-bit signed integers 8-, 16-, and 32-bit unsigned integers
T (Template)	Double-precision floating point Single-precision floating point Fixed point (signed, unsigned or both) Boolean 8-bit unsigned integers
ROI (Region of Interest)	Double-precision floating point Single-precision floating point Fixed point (signed, unsigned or both) Boolean 8-bit unsigned integers
Metric (Match Metric Values)	Double-precision floating point Single-precision floating point Fixed point (signed, unsigned or both) Boolean 32-bit unsigned integers
Loc (Best match location [x,y])	32-bit unsigned integers
NMetric (Metric values in Neighborhood of best match)	Double-precision floating point Single-precision floating point Fixed point (signed, unsigned or both) Boolean 8-bit unsigned integers
NValid (Neighborhood valid)	Boolean
ROIValid (ROI valid)	Boolean

Reference

[1] Koga T., et. Al. Motion-compensated interframe coding for video conferencing. In National Telecommunications Conference. Nov. 1981, G5.3.1–5, New Orleans, LA.

[2] Zakai M., "General distance criteria" IEEE Transaction on Information Theory, pp. 94–95, January 1964.

[3] Yu, J., J. Amores, N. Sebe, Q. Tian, "A New Study on Distance Metrics as Similarity Measurement" IEEE International Conference on Multimedia and Expo, 2006 .