de.unihalle.informatik.MiToBo.math.fitting

Class FitEllipseToPointSet

java.lang.Object

de.unihalle.informatik.Alida.operator.ALDOperator

de.unihalle.informatik.MiToBo.core.operator.MTBOperator

de.unihalle.informatik.MiToBo.math.fitting.FitEllipseToPointSet

All Implemented Interfaces:

de.unihalle.informatik.Alida.datatypes.ALDConfigurationValidator, de.unihalle.informatik.Alida.operator.events.ALDOperatorExecutionProgressEventListener, EventListener

@ALDAOperator(genericExecutionMode=NONE,
              level=STANDARD)
public class FitEllipseToPointSet
extends MTBOperator

Operator that fits an ellipse to a given set of 2D points.

An ellipse is a special case of a general quadratic curve defined by the following implicit equation:

\begin{equation*} a \cdot x^2 + 2 b \cdot x \cdot y + c \cdot y^2 + 2 d \cdot x + 2 e \cdot y + f = 0 \end{equation*}

The curve equation yields always an elliptical solution if

\begin{equation*} b^2 - 4ac = \vec p^{\;T} \cdot \left[\begin{array}{cccccc} 0 & 0 & -2 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ -2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right] \cdot \vec{p} = \vec{p}^{\;T} \cdot C \cdot \vec{p} < 0 \end{equation*}

This operator estimates the parameters of a conic in a least square sense. By including the above constraint, however, it guarantees to always return an ellipse as solution. The ellipse fits a given set of points in a least-squares sense.

The algorithm basically solves an eigenvalue problem:

\begin{equation*} D^TD\vec{p} = S \vec p = \lambda C \vec p \end{equation*}

with matrix D containing the data

\begin{equation*} D = \left[\begin{array}{cccccc} x_1^2 & x_1 \cdot y_1 & y_1^2 & x_1 & y_1 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ x_1^N & x_N \cdot y_N & y_N^2 & x_N & y_N & 1 \end{array}\right] \end{equation*}

and the parameter vector

\begin{equation*} \vec p = \left[\begin{array}{c} a \\ b \\ c \\ d \\ e \\ f \end{array}\right] \end{equation*}

This general eigenvalue problem can be transformed into an ordinary eigenvalue problem as follows:

\begin{eqnarray*} & D^TD\vec{p} = S \vec p &= \lambda C \vec p \\ \Rightarrow& S^{-1} S \vec p &= \lambda S^{-1} C \vec p \\ \Rightarrow& \frac{1}{\lambda} \vec p &= S^{-1} C \vec p \end{eqnarray*}

The solution vector is given by the (denormalized) eigenvector corresponding to the only negative eigenvalue calculated.

To ensure that the scatter matrix S is invertible, the algorithm expects a point set containing at least 6 points in general position, i.e. matrix S is required to have full rank. Note that this condition is also not fulfilled if the given points are all lying exactly (!) on a single ellipse, i.e., if the algebraic error is zero. In that case the operator will return no result, but the estimated curve will be null.

The result is returned as an object of class MTBQuadraticCurve2D with type ellipse.

Details concerning the algorithm can be found in
Pilu et al., Ellipse-specific Direct Least-Square Fitting, Proc. of IEEE International Conference on Image Processing, Lausanne, September 1996 (Webpage).

Author:

Birgit Moeller

See Also:

MTBQuadraticCurve2D, FitQuadraticCurveToPointSet, Ellipses on WolframMathWorld, Efficient Java Matrix Library

Nested Class Summary

Nested classes/interfaces inherited from class de.unihalle.informatik.Alida.operator.ALDOperator

de.unihalle.informatik.Alida.operator.ALDOperator.HidingMode, de.unihalle.informatik.Alida.operator.ALDOperator.HistoryConstructionMode

Field Summary

Fields

Modifier and Type	Field and Description
private MTBQuadraticCurve2D	curve Estimated curve.
private Vector<Point2D.Double>	points Input set of points.

Fields inherited from class de.unihalle.informatik.Alida.operator.ALDOperator

completeDAG, name, operatorExecutionEventlistenerList, portHashAccess, verbose, versionProvider

Constructor Summary

Constructors

Constructor and Description
FitEllipseToPointSet() Default constructor.

Method Summary

Modifier and Type	Method and Description
MTBQuadraticCurve2D	getEstimatedCurve() Get estimated curve.
protected void	operate()
void	setPointSet(Vector<Point2D.Double> p) Set input set of 2D points.
void	validateCustom()

Methods inherited from class de.unihalle.informatik.MiToBo.core.operator.MTBOperator

readResolve

Methods inherited from class de.unihalle.informatik.Alida.operator.ALDOperator

addOperatorExecutionProgressEventListener, addParameter, addParameter, addParameterUnconditioned, fieldContained, fireOperatorExecutionProgressEvent, getALDPortHashAccessKey, getConstructionMode, getDocumentation, getHidingMode, getInactiveParameterNames, getInInoutNames, getInInoutNames, getInNames, getInOutNames, getMissingRequiredInputs, getName, getNumParameters, getOutInoutNames, getOutNames, getParameter, getParameterDescriptor, getParameterDescriptorUnconditioned, getParameterNames, getParameterUnconditioned, getSupplementalNames, getVerbose, getVersion, handleOperatorExecutionProgressEvent, hasInOutParameters, hasParameter, isAnnotatedParameter, isConfigured, print, print, print, printInterface, printInterface, readHistory, reinitializeParameterDescriptors, removeOperatorExecutionProgressEventListener, removeParameter, runOp, runOp, runOp, setConstructionMode, setConstructionMode, setConstructionMode, setHidingMode, setName, setParameter, setParameterUnconditioned, setVerbose, toStringVerbose, unconfiguredItems, validate, validateGeneric, writeHistory, writeHistory, writeHistory

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

points

@Parameter(label="Point Set",
           required=true,
           dataIOOrder=0,
           direction=IN,
           description="Point Set.")
private Vector<Point2D.Double> points

Input set of points.

curve

@Parameter(label="Curve",
           dataIOOrder=1,
           direction=OUT,
           description="Estimated curve.")
private MTBQuadraticCurve2D curve

Estimated curve.

Constructor Detail

FitEllipseToPointSet

public FitEllipseToPointSet()
                     throws de.unihalle.informatik.Alida.exceptions.ALDOperatorException

Default constructor.

Throws:

de.unihalle.informatik.Alida.exceptions.ALDOperatorException - Thrown in case of operate failure.

Method Detail

validateCustom

public void validateCustom()
                    throws de.unihalle.informatik.Alida.exceptions.ALDOperatorException

Overrides:

validateCustom in class de.unihalle.informatik.Alida.operator.ALDOperator

Throws:

de.unihalle.informatik.Alida.exceptions.ALDOperatorException

operate

protected void operate()
                throws de.unihalle.informatik.Alida.exceptions.ALDOperatorException

Specified by:

operate in class de.unihalle.informatik.Alida.operator.ALDOperator

Throws:

de.unihalle.informatik.Alida.exceptions.ALDOperatorException

setPointSet

public void setPointSet(Vector<Point2D.Double> p)

Set input set of 2D points.

Parameters:

p - Set of points to process.

getEstimatedCurve

public MTBQuadraticCurve2D getEstimatedCurve()

Get estimated curve.

Returns:

Estimated curve.