Estimate Geometric Transformation

Estimate geometric transformation from matching point pairs

Library:
Computer Vision Toolbox / Geometric Transformations

Description

Use the Estimate Geometric Transformation block to find the transformation matrix which maps the greatest number of point pairs between two images. A point pair refers to a point in the input image and its related point on the image created using the transformation matrix. You can select to use the RANdom SAmple Consensus (RANSAC) or the Least Median Squares algorithm to exclude outliers and to calculate the transformation matrix. You can also use all input points to calculate the transformation matrix.

Ports

Input

expand all

`Pts1` — Point coordinates
M-by-2 matrix

Point coordinates, specified as an M-by-2 matrix of one-based [x y] point coordinates, where M represents the number of points.

The block outputs the same data type for the transformation matrix as the Pts1 and Pts2 image points.

`Pts2` — Point coordinates
M-by-2 matrix

Point coordinates, specified as an M-by-2 matrix of one-based [x y] point coordinates, where M represents the number of points.

The block outputs the same data type for the transformation matrix as the Pts1 and Pts2 image points.

`Num` — Number of valid points
scalar

Number of valid points to find in Pts1 and Pts2, specified as a scalar. This port appears when you enable the Allow variable-size signal input parameter.

Output

expand all

`TForm` — Transformation
3-by-2 matrix | 3-by-3 matrix

Transformation, returned as either a 3-by-2 or a 3-by-3 matrix. The block outputs the same data type for the transformation matrix as the Pts1 and Pts2 image points.

Dependencies

When Pts1 and Pts2 are single or double, the output transformation matrix will also have single or double data type.
When Pts1 and Pts2 images are built-in integers, the option is available to set the transformation matrix data type to either Single or Double.

Data Types: single | double

`Inlier` — Points used
M-by-1 vector

Points used to calculate TForm, returned as an M-by-1 vector.

Dependencies

The Inlier port appears when you enable the Output Boolean signal indicating which point pairs are inliers parameter.

Data Types: Boolean

Parameters

expand all

`Transformation type` — Transformation type
`Affine` (default) | `Nonreflective similarity` | `Projective`

Specify the transformation type as either Nonreflective similarity, Affine, or Projective. See Transformations for a more detailed discussion.

Dependencies

You can set additional parameters depending on the transformation type:

For Projective transformation, you can specify a scalar algebraic distance threshold for determining inliers.
For Affine or Projective transformation, you can specify the distance threshold for determining inliers in pixels.

`Find and exclude outliers` — Find and exclude outliers
on (default) | off

Enable to find and exclude outliers from the input points and use only the inlier points to calculate the transformation matrix. When you turn this parameter off, all input points are used to calculate the transformation matrix.

`Method` — Method to find outliers
`RANdom SAmple Consensus (RANSAC)` (default) | `Least Median of Squares`

Select the method to find outliers as either RANdom SAmple Consensus (RANSAC) or Least Median of Squares See RANSAC and Least Median Squares Algorithms for a more detailed discussion.

Dependencies

This parameter appears when you enable the Find and exclude outliers check box.

`Algebraic distance threshold for determining inliers` — Algebraic distance threshold for determining inliers
1.5 (default) | scalar

Specify a scalar threshold value for determining inliers. The threshold controls the upper limit used to find the algebraic distance in the RANSAC algorithm.

Dependencies

This parameter appears when you set the Method parameter to Random Sample Consensus (RANSAC) and the Transformation type parameter to Projective.

`Distance threshold for determining inliers (in pixels)` — Distance threshold for determining inliers (in pixels)
`1.5` (default) | scalar

Specify the upper limit distance a point can differ from the projection location of its corresponding point.

Dependencies

This parameter appears when you set the Method parameter to Random Sample Consensus (RANSAC) and you set the value of the Transformation type parameter to Nonreflective similarity or Affine.

`Determine number of random samplings using` — Determine number of random samplings using
`Specified value` (default) | `Desired confidence`

Select Specified value to enter a positive integer value for the number of random samplings. Select Desired confidence to set the number of random samplings as a percentage and a maximum number.

Dependencies

This parameter appears when you select the Find and exclude outliers check box, and you set the value of the Method parameter to Random Sample Consensus (RANSAC).

`Number of random samplings` — Number of random samplings
`500` (default) | scalar

Specify the number of random samplings for the algorithm to perform.

Dependencies

This parameter appears when you set the value of the Determine number of random samplings using parameter to Specified value.

`Desired confidence (in %)` — Desired confidence (in %)
`99` (default) | scalar

Specify a percent desired confidence by entering a number between 0 and 100. The value represents the probability of the algorithm to find the largest group of points that can be mapped by a transformation matrix.

Dependencies

This parameter appears when you set the Determine number of random samplings using parameter to Desired confidence.

`Maximum number of random samplings` — Maximum number of random samplings
`1000` (default) | integer

Specify an integer number for the maximum number of random samplings.

Dependencies

This parameter appears when you set the Method parameter to Random Sample Consensus (RANSAC) and you set the value of the Determine number of random samplings using parameter to Desired confidence.

`Stop sampling earlier when a specified percentage of point pairs are determined to be inlier` — Stop sampling
off (default) | on

Enable this parameter to stop random sampling when a percentage of input points have been found as inliers.

Dependencies

This parameter appears when you set the Method parameter to Random Sample Consensus (RANSAC).

`Perform additional iterative refinement of the transformation matrix` — Perform additional iterative refinement
off (default) | on

Specify whether to perform refinement on the transformation matrix.

Dependencies

This parameter appears when you select Find and exclude outliers check box.

`Output Boolean signal indicating which point pairs are inliers` — Output Boolean signal
off (default) | on

Enable this parameter to output the inlier point pairs that were used to calculate the transformation matrix.

Dependencies

This parameter appears when you select the Find and exclude outliers check box.
The block will not use this parameter with signed or double, data type points.

`When Pts1 and Pts2 are built-in integers, set transformation matrix date type to` — Set transformation matrix date type
`Single` (default) | `Double`

Specify transformation matrix data type as Single or Double when the input points are built-in integers.

Dependencies

The block will not use this parameter with signed or double, data type points.

`Allow variable-sized signal input` — Allow variable-sized signal input
on (default) | off

Enable this parameter to allow variable-sized signal input.

Dependencies

Block Characteristics

Data Types	`double` \| `integer^[a]` \| `single`
Multidimensional Signals	`no`
Variable-Size Signals	`yes`
^[a] Generated code will be restricted to MATLAB host computers when you set the FFT implementation parameter to FFTW, or when the transform length is not a power of two.

Algorithms

expand all

RANSAC and Least Median Squares Algorithms

The RANSAC algorithm relies on a distance threshold. A pair of points, $p_{i}^{a}$ (image a, Pts1) and $p_{i}^{b}$ (image b, Pts2) is an inlier only when the distance between $p_{i}^{b}$ and the projection of $p_{i}^{a}$ based on the transformation matrix falls within the specified threshold. The distance metric used in the RANSAC algorithm is as follows:

$d = \sum_{i = 1}^{N u m} \min (D (p_{i}^{b}, ψ (p_{i}^{a} : H)), t)$

The Least Median Squares algorithm assumes at least 50% of the point pairs can be mapped by a transformation matrix. The algorithm does not need to explicitly specify the distance threshold. Instead, it uses the median distance between all input point pairs. The distance metric used in the Least Median of Squares algorithm is as follows:

$d = m e d i a n (D (p_{1}^{b}, ψ (p_{1}^{a} : H)), D (p_{2}^{b}, ψ (p_{2}^{a} : H)), ..., D (p_{N u m}^{b}, ψ (p_{N}^{a} : H)))$

For both equations:

$p_{i}^{a}$ is a point in image a (Pts1)

$p_{i}^{b}$ is a point in image b (Pts2)

$ψ (p_{i}^{a} : H)$ is the projection of a point on image a based on transformation matrix H

$D (p_{i}^{b}, p_{j}^{b})$ is the distance between two point pairs on image b

$t$ is the threshold

$N u m$ is the number of points

The smaller the distance metric, the better the transformation matrix and therefore the more accurate the projection image.

Transformations

The Estimate Geometric Transformation block supports Nonreflective similarity, Affine, and Projective transformation types, which are described in this section.

Nonreflective similarity transformation supports translation, rotation, and isotropic scaling. It has four degrees of freedom and requires two pairs of points.

The transformation matrix is: $H = [\begin{matrix} h_{1} & - h_{2} \\ h_{2} & h_{1} \\ h_{3} & h_{4} \end{matrix}]$

The projection of a point ${[\begin{matrix} x & y \end{matrix}]}^{}$ by $H$ is: ${[\begin{matrix} \hat{x} & \hat{y} \end{matrix}]}^{} = [\begin{matrix} x & y & 1 \end{matrix}] H$

affine transformation supports nonisotropic scaling in addition to all transformations that the nonreflective similarity transformation supports. It has six degrees of freedom that can be determined from three pairs of noncollinear points.

The transformation matrix is: $H = [\begin{matrix} h_{1} & h_{4} \\ h_{2} & h_{5} \\ h_{3} & h_{6} \end{matrix}]$

The projection of a point ${[\begin{matrix} x & y \end{matrix}]}^{}$ by $H$ is: ${[\begin{matrix} \hat{x} & \hat{y} \end{matrix}]}^{} = [\begin{matrix} x & y & 1 \end{matrix}] H$

Projective transformation supports tilting in addition to all transformations that the affine transformation supports.

The transformation matrix is : $h = [\begin{matrix} h_{1} & h_{4} & h_{7} \\ h_{2} & h_{5} & h_{8} \\ h_{3} & h_{6} & h_{9} \end{matrix}]$

The projection of a point ${[\begin{matrix} x & y \end{matrix}]}^{}$ by $H$ is represented by homogeneous coordinates as: ${[\begin{matrix} \hat{u} & \hat{v} & \hat{w} \end{matrix}]}^{} = [\begin{matrix} x & y & 1 \end{matrix}] H$

Distance Measurement

For computational simplicity and efficiency, this block uses algebraic distance. The algebraic distance for a pair of points, ${[\begin{matrix} x^{a} & y^{a} \end{matrix}]}^{T}$ on image a, and $[\begin{matrix} x^{b} & y^{b} \end{matrix}]$ on image b , according to transformation $H,$ is defined as follows;

For projective transformation:

$D (p_{i}^{b}, ψ (p_{i}^{a} : H)) = {({({\hat{u}}^{a} - {\hat{w}}^{a} x^{b})}^{2} + {({\hat{v}}^{a} - {\hat{w}}^{a} y^{b})}^{2})}^{\frac{1}{2}}$ , where $[\begin{matrix} {\hat{u}}^{a} & {\hat{v}}^{a} & {\hat{w}}^{a} \end{matrix}] = [\begin{matrix} x^{a} & y^{a} & 1 \end{matrix}] H$

For Nonreflective similarity or affine transformation: $D (p_{i}^{b}, ψ (p_{i}^{a} : H)) = {({({\hat{x}}^{a} - x^{b})}^{2} + {({\hat{y}}^{a} - {\hat{y}}^{b})}^{2})}^{\frac{1}{2}}$ ,

where ${[\begin{matrix} {\hat{x}}^{a} & {\hat{y}}^{a} \end{matrix}]}^{} = [\begin{matrix} x^{a} & y^{a} & 1 \end{matrix}] H$

Algorithm

The block performs a comparison and repeats it K number of times between successive transformation matrices. If you select the Find and exclude outliers option, the RANSAC and Least Median Squares (LMS) algorithms become available. These algorithms calculate and compare a distance metric. The transformation matrix that produces the smaller distance metric becomes the new transformation matrix that the next comparison uses. A final transformation matrix is resolved when either:

K number of random samplings is performed
The RANSAC algorithm, when enough number of inlier point pairs can be mapped, (dynamically updating K)

The Estimate Geometric Transformation algorithm follows these steps:

A transformation matrix $H$ is initialized to zeros
Set count = 0 (Randomly sampling).
While count < K , where K is total number of random samplings to perform, perform the following;
1. Increment the count; count = count + 1.
2. Randomly select pair of points from images a and b, (2 pairs for Nonreflective similarity, 3 pairs for affine, or 4 pairs for projective).
3. Calculate a transformation matrix $H$ , from the selected points.
4. If $H$ has a distance metric less than that of $H$ , then replace $H$ with $H$ .
  (Optional for RANSAC algorithm only)
  1. Update K dynamically.
  2. Exit out of sampling loop if enough number of point pairs can be mapped by $H$ .
Use all point pairs in images a and b that can be mapped by $H$ to calculate a refined transformation matrix $H$
Iterative Refinement, (Optional for RANSAC and LMS algorithms)
1. Denote all point pairs that can be mapped by $H$ as inliers.
2. Use inlier point pairs to calculate a transformation matrix $H$ .
3. If $H$ has a distance metric less than that of $H$ , then replace $H$ with $H$ , otherwise exit the loop.

Number of Random Samplings

The number of random samplings can be specified by the user for the RANSAC and Least Median Squares algorithms. You can use an additional option with the RANSAC algorithm, which calculates this number based on an accuracy requirement. The Desired Confidence level drives the accuracy.

The calculated number of random samplings, K used with the RANSAC algorithm, is as follows:

$K = \frac{\log (1 - p)}{\log (1 - q^{s})}$

where

p is the probability of independent point pairs belonging to the largest group that can be mapped by the same transformation. The probability is dynamically calculated based on the number of inliers found versus the total number of points. As the probability increases, the number of samplings, K , decreases.
q is the probability of finding the largest group that can be mapped by the same transformation.
s is equal to the value 2, 3, or 4 for Nonreflective similarity, affine, and projective transformation, respectively.

Iterative Refinement of Transformation Matrix

The transformation matrix calculated from all inliers can be used to calculate a refined transformation matrix. The refined transformation matrix is then used to find a new set of inliers. This procedure can be repeated until the transformation matrix cannot be further improved. This iterative refinement is optional.

References

[1] R. Hartley and A. Ziserman, “Multiple View Geometry in Computer Vision,” Second edition, Cambridge University Press, 2003

Documentation

Estimate Geometric Transformation

Description

Ports

Input

Pts1 — Point coordinates M-by-2 matrix

Pts2 — Point coordinates M-by-2 matrix

Num — Number of valid points scalar

Output

TForm — Transformation 3-by-2 matrix | 3-by-3 matrix

Dependencies

Inlier — Points used M-by-1 vector

Dependencies

Parameters

Transformation type — Transformation type Affine (default) | Nonreflective similarity | Projective

Dependencies

Find and exclude outliers — Find and exclude outliers on (default) | off

Method — Method to find outliers RANdom SAmple Consensus (RANSAC) (default) | Least Median of Squares

Dependencies

Algebraic distance threshold for determining inliers — Algebraic distance threshold for determining inliers 1.5 (default) | scalar

Dependencies

Distance threshold for determining inliers (in pixels) — Distance threshold for determining inliers (in pixels) 1.5 (default) | scalar

Dependencies

Determine number of random samplings using — Determine number of random samplings using Specified value (default) | Desired confidence

Dependencies

Number of random samplings — Number of random samplings 500 (default) | scalar

Dependencies

Desired confidence (in %) — Desired confidence (in %) 99 (default) | scalar

Dependencies

Maximum number of random samplings — Maximum number of random samplings 1000 (default) | integer

Dependencies

Stop sampling earlier when a specified percentage of point pairs are determined to be inlier — Stop sampling off (default) | on

Dependencies

Perform additional iterative refinement of the transformation matrix — Perform additional iterative refinement off (default) | on

Dependencies

Output Boolean signal indicating which point pairs are inliers — Output Boolean signal off (default) | on

Dependencies

When Pts1 and Pts2 are built-in integers, set transformation matrix date type to — Set transformation matrix date type Single (default) | Double

Dependencies

Allow variable-sized signal input — Allow variable-sized signal input on (default) | off

Dependencies

Block Characteristics

Algorithms

RANSAC and Least Median Squares Algorithms

Transformations

Distance Measurement

Number of Random Samplings

Iterative Refinement of Transformation Matrix

References

Extended Capabilities

C/C++ Code Generation Generate C and C++ code using Simulink® Coder™.

Fixed-Point Conversion Design and simulate fixed-point systems using Fixed-Point Designer™.

See Also

Computer Vision Toolbox Documentation

Support

`Pts1` — Point coordinates
M-by-2 matrix

`Pts2` — Point coordinates
M-by-2 matrix

`Num` — Number of valid points
scalar

`TForm` — Transformation
3-by-2 matrix | 3-by-3 matrix

`Inlier` — Points used
M-by-1 vector

`Transformation type` — Transformation type
`Affine` (default) | `Nonreflective similarity` | `Projective`

`Find and exclude outliers` — Find and exclude outliers
on (default) | off

`Method` — Method to find outliers
`RANdom SAmple Consensus (RANSAC)` (default) | `Least Median of Squares`

`Algebraic distance threshold for determining inliers` — Algebraic distance threshold for determining inliers
1.5 (default) | scalar

`Distance threshold for determining inliers (in pixels)` — Distance threshold for determining inliers (in pixels)
`1.5` (default) | scalar

`Determine number of random samplings using` — Determine number of random samplings using
`Specified value` (default) | `Desired confidence`

`Number of random samplings` — Number of random samplings
`500` (default) | scalar

`Desired confidence (in %)` — Desired confidence (in %)
`99` (default) | scalar

`Maximum number of random samplings` — Maximum number of random samplings
`1000` (default) | integer

`Stop sampling earlier when a specified percentage of point pairs are determined to be inlier` — Stop sampling
off (default) | on

`Perform additional iterative refinement of the transformation matrix` — Perform additional iterative refinement
off (default) | on

`Output Boolean signal indicating which point pairs are inliers` — Output Boolean signal
off (default) | on

`When Pts1 and Pts2 are built-in integers, set transformation matrix date type to` — Set transformation matrix date type
`Single` (default) | `Double`

`Allow variable-sized signal input` — Allow variable-sized signal input
on (default) | off

C/C++ Code Generation
Generate C and C++ code using Simulink® Coder™.

Fixed-Point Conversion
Design and simulate fixed-point systems using Fixed-Point Designer™.