Linear Algebra and Machine Learning

../_images/math1.png

The Math module provides support classes for linear algebra as well as some basic machine learning tools. Like the Utils module, Math is independent from the Core module and therefore not directly correlated to computer vision only.

The DynMatrix class

The DynMatrix template is one of ICL’ fundamental utlity classes for linear algebra. It provides an intuitive object-based interface for handling 2D matrices with a templated element type. DynMatrix instances provide 1D and 2D element access (using the index or 2D-function operator) and also the ability to shallowly wrapping around existing data-pointers.

Note

It is very important that all ICL-Matrix classes use image-like 2D indexing, which is exactly the opposite of the common math-style indexing, which would mean Matrix(row,column) i.e. (y,x). In ICL, matrix 2D indices are (x,y), i.e. Matrix(column,row)

In addition to the standard mathematical operators, such as +,-,*=, … we support a large set of higher level functions:

DynRowVector

due to the row-major data layout of the DynMatrix class, the DynRowVector was realized by a simple type-def, to DynMatrix instances, that shallowly wraps the matrix’s row data pointer

DynColVector

extends the DynMatrix class by restricting instances to one column

The FixedMatrix class

The FixedMatrix template shows the same behavior as the DynMatrix template, except for the fact, that it uses a fixed data-array instead of a dynamic on. By these means, FixedMatrix instances can be created on the stack without the need for allocating dynamic data from the heap. Even though C++ allows for implementing abstract matrix classes that use template parameters to switch between static and dynamic data handling (as e.g. done in the Eigen matrix library), we decided to keep things simpler for the user by providing two separate matrix classes.

Again, also vector classes are derived from this matrix class. FixedColVector and FixedRowVector are defined in ICLUtils/FixedVector.h

The FixedMatrix class is used for typedefs in several other packages. I.e.:

  • core::Color is a typedef to FixedColVector<icl8u,3>

  • geom::Vec is a typedef to FixedColVector<float,4>

  • geom::Mat is a typedef to FixedMatrix<float,4,4>

Levenberg Marquard Optimizer

The LevenbergMarquardtFitter is a generic implementation of the Levenberg Marquardt algorithm for non-linear parameter fitting. The implementation can either use an analytic Jacobian or can be told to derive a numerical Jacobinan automatically. The class documentation provides several useful examples for different kinds of target functions.

Fast Fourier Transform (FFT)

The FFT package provides a huge set of 1D and 2D functions for Fast Fourier Transformation and several support functions for vectors and matrices with real and even complex data types. Internally, the FFT-framework uses Intel IPP and the Intel MKL if available for a significant speed up. All FFT support functions and classes are in the inner namespace math::fft.

Note

For image-FFT, a less general, but easier to use FFT-Filter is provided in the ICLFilter module: FFTOp

Generic RANSAC Optimization

The RansacFitter can be used for RANSAC based function fitting and optimization. It is implemented with template parameters for the vector-types for sample points and for the model parameter set. Here is an example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <ICLUtils/ProgArg.h>
#include <ICLUtils/StringUtils.h>
#include <ICLUtils/Random.h>
#include <ICLUtils/Point32f.h>

#include <ICLMath/FixedVector.h>
#include <ICLMath/RansacFitter.h>

using namespace icl::utils;
using namespace icl::math;

// the line model (y=mx+b) is defined by two values
typedef FixedColVector<float,2> Line;

// the fitting is done using standard least squares approach
Line fit_line(const std::vector<Point32f> &pts){
  int n = pts.size();
  DynMatrix<float> xs(n,2), ys(n,1);
  for(int i=0;i<n;++i){
    xs(i,0) = 1;
    xs(i,1) = pts[i].x;
    ys(i,0) = pts[i].y;
  }
  DynMatrix<float> fit = ys * xs.pinv(true);
  return Line(fit[0],fit[1]);
}

// distance function for single points (y-distance here)
double line_dist(const Line &line, const Point32f &p){
  return sqr(line[0] + line[1]*p.x - p.y);
}

// the original line
static const Line THE_LINE(1.23456, 7.89);

// create test data:
// 50% noisy point on the line
// 50% random outliers
const std::vector<Point32f> get_line_points(){
  Line l = THE_LINE;
  std::vector<Point32f> pts(100);
  URand r(-100,100);
  GRand gr(0,1);
  for(int i=0;i<50;++i){
    pts[i].x = r;
    pts[i].y = l[0] + l[1]* pts[i].x + gr;
  }
  for(int i=0;i<50;++i){
    pts[i+50] = Point32f(r,r);
  }
  return pts;
}

int main(int n, char **ppc){
  randomSeed();

  // create the fitter
  RansacFitter<Point32f,Line> fitLine(2,1000,fit_line,line_dist,1.5,30);

  // fit ...
  RansacFitter<Point32f,Line>::Result r = fitLine.fit(get_line_points());

  // show results
  std::cout << "original line was " << THE_LINE.transp() << std::endl;
  std::cout << "fitted result was " << r.model.transp() << std::endl;
  std::cout << "fitting error was " << r.error << std::endl;
}

Generic Self Organizing (SOM)

The math::SOM and it’s derived class math::SOM2D are generic self organizing map implementations. An algorithm overview is given in http://en.wikipedia.org/wiki/Self-organizing_map

Local Linear Maps Network (LLM)

The Local Linear Map algorithm can be used for general regression tasks. ICL provides two sample applications that use the icl::LLM network for 1D to 1D and from 2D to 3D regression tasks.

Simplex Optimizer

The Simplex (Downhill) algorithm is a very concise, yet powerful search algorithm, that can be used to minimize arbitrary well shaped functions. Our implementation, the SimplexOptimizer is implemented as a generic template that abstracts from the used scalar and vector types. Except for some optimization parameters, it can be instantiated by just passing an arbitrary error-function and an initial position in the search space.

Stochastic Optimizer

The StochasticOptimizer is a rather old implementation for stochastic search processes. It defines a virtual class interface, that can be implemented for specific optimization tasks.

Vector Quantisation

This algorithm is implemented by the KMeans class template. The class is implemented as a generic template, and can therefore be used for different Scalar and Vector types.

Least-Square based Model Fitting

The LeastSquareModelFitting is a generic implementation of the direct-least-square fitting approach presented in the paper Direct Least Square Fitting of Ellipses by Andrew W. Fitzgibbon et. al..

Generic Polynomial Regression

The PolynomialRegression is a generic template-based implementation for a polynomial regression network. It provides a string-based interface to define regression parameters.

QuadTree and Octree classes

The QuadTree and the Octree class templates provides an extremly fast interface for inserting points, nearest-neighbor search and aproximate nearest-neighbor search. In benchmarks, the octree was magnitudes faster then a comparable pcl-octree implementation. However, we buy this speedup by the loss of the ability to check whether a newly added point is already contained in the octree.

The classes are implemented as a template for float and double point types and it uses an extra template parameter CAPACITY that defines the number of points, that can be stored in each node of the tree. It basically provides optimized functions for

  • point insertion

  • nearest neighbor search

  • querying a rectangular sub-region