Skip to content

Commit d25ee8a

Browse files
vpisarevvpisarev
committed
Merge pull request opencv#9761 from Jazmann:ellipseFitAMS&Direct
2 parents 6c6900a + 800da72 commit d25ee8a

File tree

8 files changed

+1596
-37
lines changed

8 files changed

+1596
-37
lines changed

‎doc/opencv.bib

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -295,6 +295,66 @@ @INPROCEEDINGS{Fitzgibbon95
295295
pages = {513--522},
296296
organization = {BMVA Press}
297297
}
298+
@ARTICLE{fitzgibbon1999,
299+
abstract = {This work presents a new efficient method for fitting
300+
ellipses to scattered data. Previous algorithms either
301+
fitted general conics or were computationally expensive. By
302+
minimizing the algebraic distance subject to the constraint
303+
4ac-b<sup>2</sup>=1, the new method incorporates the
304+
ellipticity constraint into the normalization factor. The
305+
proposed method combines several advantages: It is
306+
ellipse-specific, so that even bad data will always return
307+
an ellipse. It can be solved naturally by a generalized
308+
eigensystem. It is extremely robust, efficient, and easy to
309+
implement},
310+
author = {Fitzgibbon, Andrew and Pilu, Maurizio and Fisher, Robert B.},
311+
doi= {10.1109/34.765658},
312+
isbn= {0162-8828},
313+
issn= {01628828},
314+
journal = {IEEE Transactions on Pattern Analysis and Machine
315+
Intelligence},
316+
number = {5},
317+
pages= {476--480},
318+
pmid= {708},
319+
title= {{Direct least square fitting of ellipses}},
320+
volume = {21},
321+
year= {1999}
322+
}
323+
@Article{taubin1991,
324+
abstract = {The author addresses the problem of parametric
325+
representation and estimation of complex planar curves in
326+
2-D surfaces in 3-D, and nonplanar space curves in 3-D.
327+
Curves and surfaces can be defined either parametrically or
328+
implicitly, with the latter representation used here. A
329+
planar curve is the set of zeros of a smooth function of
330+
two variables <e1>x</e1>-<e1>y</e1>, a surface is the set
331+
of zeros of a smooth function of three variables
332+
<e1>x</e1>-<e1>y</e1>-<e1>z</e1>, and a space curve is the
333+
intersection of two surfaces, which are the set of zeros of
334+
two linearly independent smooth functions of three
335+
variables <e1>x</e1>-<e1>y</e1>-<e1>z</e1> For example, the
336+
surface of a complex object in 3-D can be represented as a
337+
subset of a single implicit surface, with similar results
338+
for planar and space curves. It is shown how this unified
339+
representation can be used for object recognition, object
340+
position estimation, and segmentation of objects into
341+
meaningful subobjects, that is, the detection of `interest
342+
regions' that are more complex than high curvature regions
343+
and, hence, more useful as features for object
344+
recognition},
345+
author = {Taubin, Gabriel},
346+
doi= {10.1109/34.103273},
347+
isbn= {0162-8828},
348+
issn= {01628828},
349+
journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
350+
number = {11},
351+
pages= {1115--1138},
352+
title= {{Estimation of planar curves, surfaces, and nonplanar
353+
space curves defined by implicit equations with
354+
applications to edge and range image segmentation}},
355+
volume = {13},
356+
year= {1991}
357+
}
298358
@INPROCEEDINGS{G11,
299359
author = {Grundmann, Matthias and Kwatra, Vivek and Essa, Irfan},
300360
title = {Auto-directed video stabilization with robust l1 optimal camera paths},

‎modules/core/include/opencv2/core/utils/logger.hpp

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616
//
1717
//! @{
1818

19+
namespace cv {
1920
namespace utils {
2021
namespace logging {
2122

@@ -77,7 +78,7 @@ enum LogLevel {
7778
#endif
7879

7980

80-
}} // namespace
81+
}}} // namespace
8182

8283
//! @}
8384

‎modules/imgproc/include/opencv2/imgproc.hpp

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4066,6 +4066,88 @@ border of the containing Mat element.
40664066
*/
40674067
CV_EXPORTS_W RotatedRect fitEllipse( InputArray points );
40684068

4069+
/** @brief Fits an ellipse around a set of 2D points.
4070+
4071+
The function calculates the ellipse that fits a set of 2D points.
4072+
It returns the rotated rectangle in which the ellipse is inscribed.
4073+
The Approximate Mean Square (AMS) proposed by @cite Taubin1991 is used.
4074+
4075+
For an ellipse, this basis set is \f$ \chi= \left(x^2, x y, y^2, x, y, 1\right) \f$,
4076+
which is a set of six free coefficients \f$ A^T=\left\{A_{\text{xx}},A_{\text{xy}},A_{\text{yy}},A_x,A_y,A_0\right\} \f$.
4077+
However, to specify an ellipse, all that is needed is five numbers; the major and minor axes lengths \f$ (a,b) \f$,
4078+
the position \f$ (x_0,y_0) \f$, and the orientation \f$ \theta \f$. This is because the basis set includes lines,
4079+
quadratics, parabolic and hyperbolic functions as well as elliptical functions as possible fits.
4080+
If the fit is found to be a parabolic or hyperbolic function then the standard fitEllipse method is used.
4081+
The AMS method restricts the fit to parabolic, hyperbolic and elliptical curves
4082+
by imposing the condition that \f$ A^T ( D_x^T D_x + D_y^T D_y) A = 1 \f$ where
4083+
the matrices \f$ Dx \f$ and \f$ Dy \f$ are the partial derivatives of the design matrix \f$ D \f$ with
4084+
respect to x and y. The matrices are formed row by row applying the following to
4085+
each of the points in the set:
4086+
\f{align*}{
4087+
D(i,:)&=\left\{x_i^2, x_i y_i, y_i^2, x_i, y_i, 1\right\} &
4088+
D_x(i,:)&=\left\{2 x_i,y_i,0,1,0,0\right\} &
4089+
D_y(i,:)&=\left\{0,x_i,2 y_i,0,1,0\right\}
4090+
\f}
4091+
The AMS method minimizes the cost function
4092+
\f{equation*}{
4093+
\epsilon ^2=\frac{ A^T D^T D A }{ A^T (D_x^T D_x + D_y^T D_y) A^T }
4094+
\f}
4095+
4096+
The minimum cost is found by solving the generalized eigenvalue problem.
4097+
4098+
\f{equation*}{
4099+
D^T D A = \lambda \left( D_x^T D_x + D_y^T D_y\right) A
4100+
\f}
4101+
4102+
@param points Input 2D point set, stored in std::vector\<\> or Mat
4103+
*/
4104+
CV_EXPORTS_W RotatedRect fitEllipseAMS( InputArray points );
4105+
4106+
4107+
/** @brief Fits an ellipse around a set of 2D points.
4108+
4109+
The function calculates the ellipse that fits a set of 2D points.
4110+
It returns the rotated rectangle in which the ellipse is inscribed.
4111+
The Direct least square (Direct) method by @cite Fitzgibbon1999 is used.
4112+
4113+
For an ellipse, this basis set is \f$ \chi= \left(x^2, x y, y^2, x, y, 1\right) \f$,
4114+
which is a set of six free coefficients \f$ A^T=\left\{A_{\text{xx}},A_{\text{xy}},A_{\text{yy}},A_x,A_y,A_0\right\} \f$.
4115+
However, to specify an ellipse, all that is needed is five numbers; the major and minor axes lengths \f$ (a,b) \f$,
4116+
the position \f$ (x_0,y_0) \f$, and the orientation \f$ \theta \f$. This is because the basis set includes lines,
4117+
quadratics, parabolic and hyperbolic functions as well as elliptical functions as possible fits.
4118+
The Direct method confines the fit to ellipses by ensuring that \f$ 4 A_{xx} A_{yy}- A_{xy}^2 > 0 \f$.
4119+
The condition imposed is that \f$ 4 A_{xx} A_{yy}- A_{xy}^2=1 \f$ which satisfies the inequality
4120+
and as the coefficients can be arbitrarily scaled is not overly restrictive.
4121+
4122+
\f{equation*}{
4123+
\epsilon ^2= A^T D^T D A \quad \text{with} \quad A^T C A =1 \quad \text{and} \quad C=\left(\begin{matrix}
4124+
0 & 0 & 2 & 0 & 0 & 0 \\
4125+
0 & -1 & 0 & 0 & 0 & 0 \\
4126+
2 & 0 & 0 & 0 & 0 & 0 \\
4127+
0 & 0 & 0 & 0 & 0 & 0 \\
4128+
0 & 0 & 0 & 0 & 0 & 0 \\
4129+
0 & 0 & 0 & 0 & 0 & 0
4130+
\end{matrix} \right)
4131+
\f}
4132+
4133+
The minimum cost is found by solving the generalized eigenvalue problem.
4134+
4135+
\f{equation*}{
4136+
D^T D A = \lambda \left( C\right) A
4137+
\f}
4138+
4139+
The system produces only one positive eigenvalue \f$ \lambda\f$ which is chosen as the solution
4140+
with its eigenvector \f$\mathbf{u}\f$. These are used to find the coefficients
4141+
4142+
\f{equation*}{
4143+
A = \sqrt{\frac{1}{\mathbf{u}^T C \mathbf{u}}} \mathbf{u}
4144+
\f}
4145+
The scaling factor guarantees that \f$A^T C A =1\f$.
4146+
4147+
@param points Input 2D point set, stored in std::vector\<\> or Mat
4148+
*/
4149+
CV_EXPORTS_W RotatedRect fitEllipseDirect( InputArray points );
4150+
40694151
/** @brief Fits a line to a 2D or 3D point set.
40704152
40714153
The function fitLine fits a line to a 2D or 3D point set by minimizing \f$\sum_i \rho(r_i)\f$ where

0 commit comments

Comments
 (0)