In this paper, we investigate methods for affine registering point sets. We assume that the point sets are represented (as inputs)
as probability density functions, and our goal is to develop a method that can quickly determine a good affine transformation that can register
the two point sets (or density functions). For example,
the two different camels when placed together at their own centroids do not align well. Our algorithm takes in the
two point sets and estimates an affine transformation that aligns the point sets well.
The basic idea behind our approach is NOT to match the points or PDFs directly. Instead, we will match the first few moments of the two density functions. This is possible because an affine transformation induces linear transformations among polynomials of the same degree, and these induced transformations tell us how the moments should transform under the given affine transformation. It will turns out that we can formulate the matching problem using a polynomial cost function, whose global minimum (not just local minimums) can be located.
The moments of a density function are by definition the expected values of polynomials. For a given density function p and a polynomial q, the corresponding moment is given by
Moments are in fact expected values of polynomials. For example, the most well-known first-degree moments (in R^2) are the x and y-moments,
which are the integrals of the polynomials x and y:
which are simply the averaged x and y-coordinates. Similarly, the three quadratic (degree two) moments are given by
The moments are well-known to characterize the distribution, and in particular, the first few moments capture some statistical/geometric properties of the density. For example, the linear moments are related to the mean, and the quadratic moments are related to the variance. The cubic and quartic moments are related to skew and kurtosis of the distribution.
As the moments are the expected values of polynomials, it is not surprising to find that the moments transformed exactly as polynomials under an affine transform. For example, under the following affine transform
the quadratic polynomials (using the 3 monomials are the basis) transformed according to
and the cubic polynomials transformed according to
It is important to note that the entries in the matrix for cubic polynomials are cubic polynomials in a, b, c and d, and of course, the entries in the matrix for quadratic polynomials are quadratic polynomials in a, b, c and d. So if we define the cost function that we want to minimize as
where D is the highest degree used in the matching and the omegas are the weights. Omegas are needed because in general the weights for lower-degree moments should be higher than the weights for higher-degree moments. In particular, if we only use up to degree three (D=3) moments, w1, and w2 are generally set at higher values than w3. In most cases, we can find affine transformation that exactly matches the linear and quadratic moments.
Solving Polynomial Equation
The cost function is in fact a polynomial. So that to find its global minimums, we simply have to solve for the critical points which are the solutions to the system of polynomial equations
These equations (particularly for small number of variables and low degrees) can be solved using, e.g. MAPLE.
Once the critical points are known, the global minimum can be determined from them easily.
A full implementation of the algorithm outlined above uses both MATLAB and MAPLE.
A simplified MATLAB implementation is here. In this (2D) implementation, moments up to degree three
are used for matching. Furthermore, the linear and quadratic moments are matched exactly.
This significantly simplifies the computation since in this case we are essentially matching the cubic moments using only the
Results on 2D Alignment
Results on 3D Alignment
Stanford bunny with roughly 3500 points
A randomly generated affine transform is applied to the points (shown in three different views)
The registration result (shown in two different views with 5% of the original points deleted)