icl::math::LeastSquareModelFitting< T, DataPoint > Class Template Reference

Direct Least Square Fitting Algorithm. More...

#include <LeastSquareModelFitting.h>

List of all members.

Public Types
typedef Function< void, const DataPoint &, T * >	DesignMatrixGen
	fills the give float* with data from the given data point
typedef std::vector< T >	Model
	model type (defines the model parameters)
Public Member Functions
	LeastSquareModelFitting ()
	Empty constructor that creates a dummy instance.
	LeastSquareModelFitting (int modelDim, DesignMatrixGen gen, DynMatrix< T > *constraintMatrix=0)
	constructor with given parameters
icl64f	getError (const Model &model, const DataPoint &p)
	computes the error for a given data point
Model	fit (const std::vector< DataPoint > &points)
	fits the model to the given data points and returns optimal parameter set
Private Attributes
int	m_modelDim
	model dimension
DesignMatrixGen	m_gen
	design matrix row generator
DynMatrix< T >	m_D
	utility valiables
DynMatrix< T >	m_S
DynMatrix< T >	m_Evecs
DynMatrix< T >	m_Evals
DynMatrix< T >	m_svdU
DynMatrix< T >	m_svdS
DynMatrix< T >	m_svdVt
SmartPtr< DynMatrix< T > >	m_C
	constraint matrix
Model	m_model
	the model parameters

---

Detailed Description

template<class T, class DataPoint>
class icl::math::LeastSquareModelFitting< T, DataPoint >

Direct Least Square Fitting Algorithm.

The given algorithm is based on the paper Direct Least Square Fitting of Ellipses written byAndrew W. Fitzgibbon, Maurizio Milu and Robert B. Fischer.

Algorithms

Here, the algorithm is explained, later, some examples will be given.

Models

For this algorithm, models are defined by implicit equations f=da=0. d = [f1(x), f2(x), ...]^T defines features that are computed on the input data x. a = [a1,a2,...] are the linear coefficients. In other words, models are expressed as intersections between geometric primitives and the f=0 plane. The resulting models always have an extra parameter, which is disambiguated by finding solutions where |a|^2 = 1. Actually, this is just a special yet very common disambiguation technique. More generally spoken, a^T C a = 1 is used where C is the so called constraint matrix. If C is set to the identity matrix, the norm becomes |a|^2=1. In the following, some common 2D models are discussed.

lines
Straight lines in 2D are expressed by a simple parametric equation. The features d for a given input (x,y) are simply d=(x,y,1)^T. The resulting equation can be seen a scalar product (a1,a2)*(x,y)^T whose result is -a3. Geometrically, a line is defined by it's perpendicular vector (a1,a2) and an offset to the origin which is -a3.

circles
The standard coordinate-equation for a circle is (x-cx)^2 + (y-cy)^2 = r^2. By decoupling the coefficients, we can create a 4 parameter model:

          a1(x^2 + y^2) + a2 x + a3 y +a4 = 0
        
          where, cx = -a2/(2*a1),
                 cy = -a3/(2*a1)
            and  r = ::sqrt( (a2*a2+a3*a3)/(4*a1*a1) -a4/a1 )

ellipses
General ellipses are expressed by the 6 parameter model

        a1 x^2 + a2 xy + a3 y^2 +  a4 x + a5 y + a6 = 0;

If we want to restrict the ellipses to be non-rotated, the mixed term needs to be removed:

        a1 x^2 + a2 y^2 +  a3 x + a4 y + a5 = 0;

If a1 and a2 are coupled, we get the circle model shown above.

Direct Least Square Fitting

Instead of finding a solution da=0, for a single data point, we have a larger set of input data D (where the vectors d are the rows of d). Usually, the data is noisy. Therefore we try to minimize the error E=|Da|^2. D is the so called design matrix. In order to avoid receiving the trivial solution a=0, the constraint matrix C is introduced. The minimization is then applied by introducing Lagrange multipliers:

        minimize:         2 D^T Da - 2 lambda C a = 0
        with subject to                   a^T C a = 1

By introducing the the scatter matrix S = D^T D, we get a generlized eigen vector problem:

        minimize:         S a - lambda C a = 0
        with subject to            a^T C a = 1

Implementing the Configurable Interface

1. create the design matrix D
2. create the scatter matrix S = D^T D
3. create the constraint matrix C (usually id)
4. find eigen vectors and eigen values for S^-1 C
5. use the eigen vector to the largest eigen value as model

Example

Examples for usage are given in the interactive application icl-model-fitting-example located in the ICLQt package. Here, the icl::LeastSquareModelFitting is demonstrated and it is combined with the icl::RansacFitter class in order to show the advantages of using the RANSAC algorithm in presence of outliers and noise.

For the creation of a LeastSquareModelFitting instance, only the model dimension and the creation function for rows of the design matrix D. Optionally, a non-ID constraint matrix can be given.

---

Member Typedef Documentation

template<class T, class DataPoint>

typedef Function<void,const DataPoint&,T*> icl::math::LeastSquareModelFitting< T, DataPoint >::DesignMatrixGen

fills the give float* with data from the given data point

creates the rows of the design matrix

template<class T, class DataPoint>

typedef std::vector<T> icl::math::LeastSquareModelFitting< T, DataPoint >::Model

model type (defines the model parameters)

---

Constructor & Destructor Documentation

template<class T, class DataPoint>

icl::math::LeastSquareModelFitting< T, DataPoint >::LeastSquareModelFitting

(

)

[inline]

Empty constructor that creates a dummy instance.

template<class T, class DataPoint>

icl::math::LeastSquareModelFitting< T, DataPoint >::LeastSquareModelFitting	(	int	modelDim,
		DesignMatrixGen	gen,
		DynMatrix< T > *	constraintMatrix = 0
	)		[inline]

constructor with given parameters

---

Member Function Documentation

template<class T, class DataPoint>

Model icl::math::LeastSquareModelFitting< T, DataPoint >::fit

(

const std::vector< DataPoint > &

points

)

[inline]

fits the model to the given data points and returns optimal parameter set

Internally we use a workaround when the matrix inversion fails due to stability problems. If the standard matrix inversion fails, a SVD-based inversion is used

create design matrix D

create the scatter matrix S

use eigen vector for the largest eigen value

Reimplemented in icl::math::LeastSquareModelFitting2D.

template<class T, class DataPoint>

icl64f icl::math::LeastSquareModelFitting< T, DataPoint >::getError	(	const Model &	model,
		const DataPoint &	p
	)		[inline]

computes the error for a given data point

if model is 0, the last fitted model is used

Reimplemented in icl::math::LeastSquareModelFitting2D.

---

Member Data Documentation

template<class T, class DataPoint>

SmartPtr<DynMatrix<T> > icl::math::LeastSquareModelFitting< T, DataPoint >::m_C [private]

constraint matrix

template<class T, class DataPoint>

DynMatrix<T> icl::math::LeastSquareModelFitting< T, DataPoint >::m_D [private]

utility valiables

template<class T, class DataPoint>

DynMatrix<T> icl::math::LeastSquareModelFitting< T, DataPoint >::m_Evals [private]

template<class T, class DataPoint>

DynMatrix<T> icl::math::LeastSquareModelFitting< T, DataPoint >::m_Evecs [private]

template<class T, class DataPoint>

DesignMatrixGen icl::math::LeastSquareModelFitting< T, DataPoint >::m_gen [private]

design matrix row generator

template<class T, class DataPoint>

Model icl::math::LeastSquareModelFitting< T, DataPoint >::m_model [private]

the model parameters

template<class T, class DataPoint>

int icl::math::LeastSquareModelFitting< T, DataPoint >::m_modelDim [private]

model dimension

template<class T, class DataPoint>

DynMatrix<T> icl::math::LeastSquareModelFitting< T, DataPoint >::m_S [private]

template<class T, class DataPoint>

DynMatrix<T> icl::math::LeastSquareModelFitting< T, DataPoint >::m_svdS [private]

template<class T, class DataPoint>

DynMatrix<T> icl::math::LeastSquareModelFitting< T, DataPoint >::m_svdU [private]

template<class T, class DataPoint>

DynMatrix<T> icl::math::LeastSquareModelFitting< T, DataPoint >::m_svdVt [private]

---

The documentation for this class was generated from the following file:

• /home/jenkins/workspace/icl-manual-trunk/icl-manual/ICLMath/src/ICLMath/LeastSquareModelFitting.h