Image Component Library (ICL)
Public Types | Public Member Functions | Private Attributes | List of all members
icl::math::LeastSquareModelFitting< T, DataPoint > Class Template Reference

Direct Least Square Fitting Algorithm. More...

#include <LeastSquareModelFitting.h>

Public Types

typedef utils::Function< void, const DataPoint &, T * > DesignMatrixGen
 fills the give float* with data from the given data point More...
 
typedef std::vector< T > Model
 model type (defines the model parameters) More...
 

Public Member Functions

 LeastSquareModelFitting ()
 Empty constructor that creates a dummy instance. More...
 
 LeastSquareModelFitting (int modelDim, DesignMatrixGen gen, DynMatrix< T > *constraintMatrix=0)
 constructor with given parameters More...
 
icl64f getError (const Model &model, const DataPoint &p)
 computes the error for a given data point More...
 
Model fit (const std::vector< DataPoint > &points) throw (utils::ICLException)
 fits the model to the given data points and returns optimal parameter set More...
 

Private Attributes

int m_modelDim
 model dimension More...
 
DesignMatrixGen m_gen
 design matrix row generator More...
 
DynMatrix< T > m_D
 utility valiables More...
 
DynMatrix< T > m_S
 
DynMatrix< T > m_Evecs
 
DynMatrix< T > m_Evals
 
DynMatrix< T > m_svdU
 
DynMatrix< T > m_svdS
 
DynMatrix< T > m_svdVt
 
utils::SmartPtr< DynMatrix< T > > m_C
 constraint matrix More...
 
Model m_model
 the model parameters More...
 

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 (Image Convolution)

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 utils::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)
throw (utils::ICLException
)
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

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

Member Data Documentation

template<class T, class DataPoint>
utils::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: