Estimate geometric transformation from matching point pairs
Geometric Transformations
visiongeotforms
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.
Port | Input/Output | Supported Data Types | Complex Values Supported |
---|---|---|---|
Pts1/Pts2 | M-by-2 Matrix of one-based [x y] point coordinates, where M represents the number of points. |
| No |
Num | Scalar value that represents the number of valid points in Pts1 and Pts 2. |
| No |
TForm | 3-by-2 or 3-by-3 transformation matrix. |
| No |
Inlier | M-by-1
vector indicating which points have been used to calculate | Boolean | No |
Ports Pts1
and Pts2
are
the points on two images that have the same data type. The block outputs
the same data type for the transformation matrix
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
.
The TForm
output provides the transformation matrix.
The Inlier
output port provides the Inlier points
on which the transformation matrix is based. This output appears when
you select the Output Boolean signal indicating which point
pairs are inliers checkbox.
The RANSAC algorithm relies on a distance threshold. A pair of points, $${p}_{i}^{a}$$(image a, Pts1) and $${p}_{i}^{b}$$(image b, Pts 2) 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={\displaystyle \sum _{i=1}^{Num}\mathrm{min}(D({p}_{i}^{b},}\psi ({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=median(D({p}_{1}^{b},\psi ({p}_{1}^{a}:H)),D({p}_{2}^{b},\psi ({p}_{2}^{a}:H)),\mathrm{...},D({p}_{Num}^{b},\psi ({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
)
$$\psi ({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
$$Num$$is the number of points
The smaller the distance metric, the better the transformation matrix and therefore the more accurate the projection image.
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=\left[\begin{array}{cc}{h}_{1}& -{h}_{2}\\ {h}_{2}& {h}_{1}\\ {h}_{3}& {h}_{4}\end{array}\right]$$
The projection of a point $${\left[\begin{array}{cc}x& y\end{array}\right]}^{}$$ by $$H$$is: $${\left[\begin{array}{cc}\widehat{x}& \widehat{y}\end{array}\right]}^{}=\left[\begin{array}{ccc}x& y& 1\end{array}\right]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=\left[\begin{array}{cc}{h}_{1}& {h}_{4}\\ {h}_{2}& {h}_{5}\\ {h}_{3}& {h}_{6}\end{array}\right]$$
The projection of a point $${\left[\begin{array}{cc}x& y\end{array}\right]}^{}$$ by $$H$$is: $${\left[\begin{array}{cc}\widehat{x}& \widehat{y}\end{array}\right]}^{}=\left[\begin{array}{ccc}x& y& 1\end{array}\right]H$$
Projective transformation supports tilting in addition to all transformations that the affine transformation supports.
The transformation matrix is : $$h=\left[\begin{array}{ccc}{h}_{1}& {h}_{4}& {h}_{7}\\ {h}_{2}& {h}_{5}& {h}_{8}\\ {h}_{3}& {h}_{6}& {h}_{9}\end{array}\right]$$
The projection of a point $${\left[\begin{array}{cc}x& y\end{array}\right]}^{}$$ by $$H$$is represented by homogeneous coordinates as: $${\left[\begin{array}{ccc}\widehat{u}& \widehat{v}& \widehat{w}\end{array}\right]}^{}=\left[\begin{array}{ccc}x& y& 1\end{array}\right]H$$
For computational simplicity and efficiency, this block uses algebraic distance. The algebraic distance for a pair of points, $${\left[\begin{array}{cc}{x}^{a}& {y}^{a}\end{array}\right]}^{T}$$ on image a, and $$\left[\begin{array}{cc}{x}^{b}& {y}^{b}\end{array}\right]$$ on image b , according to transformation $$H,$$is defined as follows;
For projective transformation:
$$D({p}_{i}^{b},\psi ({p}_{i}^{a}:H))={({({\widehat{u}}^{a}-{\widehat{w}}^{a}{x}^{b})}^{2}+{({\widehat{v}}^{a}-{\widehat{w}}^{a}{y}^{b})}^{2})}^{\frac{1}{2}}$$, where $$\left[\begin{array}{ccc}{\widehat{u}}^{a}& {\widehat{v}}^{a}& {\widehat{w}}^{a}\end{array}\right]=\left[\begin{array}{ccc}{x}^{a}& {y}^{a}& 1\end{array}\right]H$$
For Nonreflective similarity or affine transformation: $$D({p}_{i}^{b},\psi ({p}_{i}^{a}:H))={({({\widehat{x}}^{a}-{x}^{b})}^{2}+{({\widehat{y}}^{a}-{\widehat{y}}^{b})}^{2})}^{\frac{1}{2}}$$,
where $${\left[\begin{array}{cc}{\widehat{x}}^{a}& {\widehat{y}}^{a}\end{array}\right]}^{}=\left[\begin{array}{ccc}{x}^{a}& {y}^{a}& 1\end{array}\right]H$$
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;
Increment the count; count = count + 1
.
Randomly select pair of points from images a and b, (2 pairs for Nonreflective similarity, 3 pairs for affine, or 4 pairs for projective).
Calculate a transformation matrix $$H$$, from the selected points.
If $$H$$has a distance metric less than that of $$H$$, then replace $$H$$ with $$H$$.
(Optional for RANSAC algorithm only)
Update K
dynamically.
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)
Denote all point pairs that can be mapped by $$H$$ as inliers.
Use inlier point pairs to calculate a transformation matrix $$H$$.
If $$H$$has a distance metric less than that of $$H$$, then replace $$H$$ with $$H$$, otherwise exit the loop.
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={\scriptscriptstyle \frac{\mathrm{log}(1-p)}{\mathrm{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.
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.
Specify transformation type, either Nonreflective similarity
, affine
,
or projective
transformation. If you select projective
transformation,
you can also specify a scalar algebraic distance threshold for determining
inliers. If you select either affine
or projective
transformation,
you can specify the distance threshold for determining inliers in
pixels. See Transformations for
a more detailed discussion. The default value is projective
.
When selected, the block finds and excludes outliers from the input points and uses only the inlier points to calculate the transformation matrix. When this option is not selected, all input points are used to calculate the transformation matrix.
Select either the RANdom SAmple Consensus (RANSAC)
or
the Least Median of Squares
algorithm to find outliers.
See RANSAC and Least Median Squares Algorithms for a more detailed
discussion. This parameter appears when you select the Find
and exclude outliers check box.
Specify a scalar threshold value for determining inliers. The
threshold controls the upper limit used to find the algebraic distance
in the RANSAC algorithm. This parameter appears when you set the Method parameter
to Random Sample Consensus (RANSAC)
and the Transformation
type parameter to projective
. The default
value is 1.5
.
Specify the upper limit distance a point can differ from the
projection location of its associating point. 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
.
The default value is 1.5
.
Select Specified value
to enter a positive
integer value for number of random samplings, or select Desired
confidence
to set the number of random samplings as a percentage
and a maximum number. This parameter appears when you select Find
and exclude outliers parameter
, and you set the value of
the Method parameter to Random Sample
Consensus (RANSAC)
.
Specify the number of random samplings for the algorithm to
perform. This parameter appears when you set the value of the Determine
number of random samplings using parameter to Specified
value
.
Specify a percent by entering a number between 0
and 100
.
The Desired confidence
value represents the probability
of the algorithm to find the largest group of points that can be mapped
by a transformation matrix. This parameter appears when you set the Determine
number of random samplings using parameter to Desired
confidence
.
Specify an integer number for the maximum number of random samplings.
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
.
Specify to stop random sampling when a percentage of input points
have been found as inliers. This parameter appears when you set the Method parameter
to Random Sample Consensus (RANSAC)
.
Specify whether to perform refinement on the transformation matrix. This parameter appears when you select Find and exclude outliers check box.
Select this option to output the inlier point pairs that were used to calculate the transformation matrix. This parameter appears when you select Find and exclude outliers check box. The block will not use this parameter with signed or double, data type points.
Specify transformation matrix data type as Single
or Double
when
the input points are built-in integers. The block will not use this
parameter with signed or double, data type points.
Examples of input data and application of the Estimate Geometric Transformation block appear in the following figures. Figures (a) and (b) show the point pairs. The points are denoted by stars or circles, and the numbers following them show how they are paired. Some point pairs can be mapped by the same transformation matrix. Other point pairs require a different transformation matrix. One matrix exists that maps the largest number of point pairs, the block calculates and returns this matrix. The block finds the point pairs in the largest group and uses them to calculate the transformation matrix. The point pairs connected by the magenta lines are the largest group.
The transformation matrix can then be used to stitch the images as shown in Figure (e).
To see an example of the Estimate Geometric Transformation block used in a model with other blocks, see the Video Mosaicking example.
The success of estimating the correct geometric transformation
depends heavily on the quality of the input point pairs. If you chose
the RANSAC or LMS algorithm, the block will randomly select point
pairs to compute the transformation matrix and will use the transformation
that best fits the input points. There is a chance that all of the
randomly selected point pairs may contain outliers despite repeated
samplings. In this case, the output transformation matrix, TForm
,
is invalid, indicated by a matrix of zeros.
To improve your results, try the following:
Increase the percentage of inliers in the input points. |
Increase the number for random samplings. |
For the RANSAC method, increase the desired confidence. |
For the LMS method, make sure the input points have 50% or more inliers. |
Use features appropriate for the image contents |
Be aware that repeated patterns, for example, windows in office building, will cause false matches when you match the features. This increases the number of outliers. |
Do not use this function if the images have significant parallax.
You can use the estimateFundamentalMatrix function
instead. |
Choose the minimum transformation for your problem. |
If a projective transformation produces the error message, "A portion of the input image was transformed to the location at infinity. Only transformation matrices that do not transform any part of the image to infinity are supported.", it is usually caused by a transformation matrix and an image that would result in an output distortion that does not fit physical reality. If the matrix was an output of the Estimate Geometric Transformation block, then most likely it could not find enough inliers. |
R. Hartley and A. Ziserman, "Multiple View Geometry in Computer Vision," Second edition, Cambridge University Press, 2003
Image Processing Toolbox™ | |
vipmosaicking | Computer Vision System Toolbox™ |