Video and Image Processing Blockset™

SAD - Perform 2-D sum of absolute differences (SAD)

Library

Analysis & Enhancement

Description

The SAD block finds the similarity between two input images by performing the sum of absolute differences. The greater the similarity between the two matrices, the smaller the SAD values that result. Assume that input matrix I has dimensions (Mi, Ni) and the input matrix Template has dimensions (Mt, Nt). The equation for the two-dimensional discrete SAD is

where

and

Port	Input/Output	Supported Data Types	Complex Values Supported
I	Matrix of intensity values	Double-precision floating point Single-precision floating point Fixed point Boolean 8-, 16-, and 32-bit signed integer 8-, 16-, and 32-bit unsigned integer	No
Template	Matrix of intensity values	Same as I port	No
ROI	Four-element vector that defines the ROI	Double-precision floating point Single-precision floating point 8-, 16-, and 32-bit signed integer 8-, 16-, and 32-bit unsigned integer	No
Val	Matrix of SAD values	Double-precision floating point Single-precision floating point Fixed point 8-, 16-, and 32-bit signed integer 8-, 16-, and 32-bit unsigned integer	No
Idx	Scalar value that represents the zero-based index location of the minimum SAD value	32-bit signed integers	No
NVals	N-by-N matrix of SAD values centered around the minimum SAD value	Same as Val port	No
NValid	Boolean 0 or 1 that represents whether or not the block went beyond the dimensions of the SAD value matrix to construct an N-by-N matrix around the minimum SAD value	Boolean	No

The data type of the two input signals must be the same. The output signal is the same data type as the input signals.

The dimensions of the output at the Val port are determined by the sizes of the inputs at ports I and Template. If the input at port I has dimensions (Mi, Ni) and the input at the Template port dimensions (Mt, Nt), then the output has dimensions (Mi-Mt+1, Ni-Nt+1).

Use the Output parameter to determine the output of the block. If you select SAD values, the block outputs the SAD values at the Val port. If you select Minimum SAD value index, the block outputs the zero-based index location of the minimum SAD value at the Idx port.

If, for the Output parameter, you select Minimum SAD value index, the Search method parameter appears in the dialog box. If you select Exhaustive, the block searches the two input matrices for the minimum difference pixel-by-pixel. This process is described by the previous equation and is computationally expensive.

If, for the Search method parameter, you select Three-step, the block searches the two input matrices for the minimum difference using a steadily decreasing step size. The block begins with a step size approximately equal to half the maximum search range. In each step, the block compares the central point of the search region to eight search points located on the boundaries of the region and moves the central point to the search point whose values is the closest to that of the central point. The block then reduces the step size by half, and begins the process again. This option is less computationally expensive, though it might not find the optimal solution.

If, for the Output parameter, you select Minimum SAD value index, the Use ROI for input I check box appears in the dialog box. If you select this check box, the ROI port appears on the block. Use this port to define a region of interest (ROI) in the input matrix, I, over which you want to compute the SAD. The input to this port must be a four-element vector, [row column height width]. The first two elements define the upper-left corner of the ROI, and the second two elements define the height and width of the ROI.

Use the Invalid ROI parameter to specify the block's behavior if you enter a ROI that is outside the bounds of the input matrix, I. The options are

Ignore -- Proceed with the computation and do not issue an alert. The output is not valid.
Warn -- Display a warning message in the MATLAB^® Command Window, and continue the simulation. The output is not valid.
Error -- Display an error dialog box and terminate the simulation.

If, for the Output parameter, you select Minimum SAD value index, the Output NxN matrix of SAD values around minimum check box appears on the dialog box. If you select this check box, the NVals and NValid ports appear on the block. The block outputs an N-by-N matrix of SAD values centered around the minimum SAD value at the NVals port. Use the Size (N) of square matrix parameter to determine the size of this matrix. The value you enter must be a real-valued, odd integer that is greater than or equal to 1.

If the block must go beyond the dimensions of the SAD value matrix to construct an N-by-N matrix around the minimum SAD value, the values outside the SAD value matrix are 0. In this case, the block outputs a Boolean 0 at the NValid port. If the block does not go beyond the dimensions of the SAD value matrix to construct an N-by-N matrix around the minimum SAD value, the block outputs a Boolean 1 at the NValid port.

Fixed-Point Data Types

The following diagram shows the data types used in the SAD block for fixed-point signals.

You can set the accumulator, and output data types in the block mask as discussed in the next section.

Dialog Box

The Main pane of the SAD dialog box appears as shown in the following figure.

Output: Specify the output of the block. Your choices are SAD values or Minimum SAD value index. If you select Minimum SAD value index, the block outputs the zero-based index location of the minimum SAD value.
Search method: Specify how the block searches for the minimum difference between the two input matrices. If you select Exhaustive, the block searches for the minimum difference pixel-by-pixel. If you select Three-step, the block searches for the minimum difference using a steadily decreasing step size. This parameter is visible if, for the Output parameter, you select Minimum SAD value index.
Use ROI for input I: If you select this check box, the ROI port appears on the block. Use this port to define a region of interest (ROI) in the input matrix, I, over which you want to compute the SAD. This parameter is visible if, for the Output parameter, you select Minimum SAD value index.
Invalid ROI: Specify the block's behavior if you enter a ROI that is outside the bounds of the input matrix, I. The options are Ignore, Warn, or Error.
Output NxN matrix of SAD values around minimum: If you select this check box, the NVals and NValid ports appear on the block. The block outputs an N-by-N matrix of SAD values centered around the minimum SAD value at the NVals port. If the block must go beyond the dimensions of the SAD value matrix to construct the N-by-N output matrix, the block outputs a Boolean 0 at the NValid port. Otherwise, the block outputs a Boolean 1 at the NValid port. This parameter is visible if, for the Output parameter, you select Minimum SAD value index.
Size (N) of square matrix: Enter an odd number that determines the size of the N-by-N matrix of SAD values. This parameter is visible if you select the Output NxN matrix of SAD values around minimum check box.

The Fixed-point pane of the SAD 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.

Accumulator

As depicted in the previous figure, inputs to the accumulator are cast to the accumulator data type. The output of the adder remains in the accumulator data type as each element of the input is added to it. Use this parameter to specify how to designate this accumulator word and fraction lengths.

When you select Same as first input, these characteristics match those of the input to the block. When you have a Boolean input, you cannot select this choice.
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. The bias of all signals in the Video and Image Processing Blockset™ is 0.

Output

Choose how to specify the word length and fraction length of the output of the block:

When you select Same as first input, these characteristics match those of the first input to the block. When you have a Boolean input, you cannot select this choice.
When you select Binary point scaling, you can enter the word length and the fraction length of the output, in bits.
When you select Slope and bias scaling, you can enter the word length, in bits, and the slope of the output. The bias of all signals in the Video and Image Processing Blockset is 0.

This parameter is not visible if, for the Output parameter you select Minimum SAD value index, and you clear the Output NxN matrix of SAD values around minimum check box.

Lock scaling against changes by the autoscaling tool

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

References

[1] Koga, T., et al. Motion-compensated interframe coding for video conferencing. In Nat. Telecommun. Conf., Nov. 1981, G5.3.1-5, New Orleans, LA.

[2] Wang, Yao, Jorn Ostermann, Ya-Qin Zhang. Video Processing and Communications. Upper Saddle River, NJ: Prentice Hall, 2002.

Rotate

Shear