# Linear Algebra and Machine Learning¶

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.

## Table of Contents¶

- The DynMatrix class
- The FixedMatrix class
- Levenberg Marquard Optimizer
- Fast Fourier Transform (FFT)
- Generic RANSAC Optimization
- Generic Self Organizing (SOM)
- Local Linear Maps Network (LLM)
- Simplex Optimizer
- Stochastic Optimizer
- Vector Quantisation
- Least-Square based Model Fitting
- Generic Polynomial Regression
- QuadTree and Octree classes

## 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:

- QR and RQ decomposition (DynMatrix::decompose_QR and DynMatrix::decompose_RQ)
- LU decomposition (DynMatrix::decompose_LU)
- matrix inverse (DynMatrix::inv)
- matrix pseudo-inverse (DynMatrix::pinv)
- eigenvalue decomposition (DynMatrix::eigen)
- singular value decomposition (SVD) (DynMatrix::svd)
- linear equation solving (DynMatrix::solve)
- LU decomposition based
- SVD based
- matrix inverse based
- QR decomposition based

- matrix trace (DynMatrix::trace)
- matrix condition (DynMatrix::cond)
- matrix determinant (DynMatrix::det)

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

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 68 69 | ```
#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