[link]
Summary by Anmol Sharma 5 years ago
Point pattern matching problem have been an active research topic in computation geometry and pattern recognition communities. These point sets typically arise in a variety of applications, where the problem lies in registration of these point sets which is encountered in stereo matching, feature based image registration and so on. Mathematically, the problem of registering two point sets translates to the following: Let $\{\mathcal{M}, \mathcal{S}\}$ be two finite set points which need to be registered, where $\mathcal{M}$ is the "moving" point set and $\mathcal{S}$ is the "fixed" or scene set. A transformation $\mathcal{T}$ is then calculated which can transform points from $\mathcal{M}$ to $\mathcal{S}$.
To this end, Jian and Vemuri propose to use a Gaussian Mixture Model based representation of point sets which are registered together my minimizing a cost function using a slightly modified version of the Iterative Closest Point (ICP) algorithm. In this setting, the problem of point set registration becomes as that of aligning two Gaussian mixture models by minimizing discrepancy between two Gaussian mixtures. The cost function for this optimization is chosen as a closed-form version of the $L_2$ distance between Gaussian mixtures, which allows the algorithm to be computationally efficient.
The main reason behind choosing Gaussian mixture models to represent discrete point sets was that it directly translates to interpreting point sets as randomly sampled data from a distribution of random point locations. This models the uncertainty of point sets well during feature extraction. The second reason was that hard discrete optimization problems that are encountered in point matching literature become tractable continuous optimization problems.
The probability density function of a general Gaussian mixture is defined as follows:
\begin{equation}
p(x) = \sum_{i=1}^{k}w_i \phi(x|\mu_i, \sigma_i)
\end{equation}
where:
$\phi(x|\mu_i, \sigma_i) = \dfrac{exp\left[-\frac{1}{2}(x - \mu_i)\sigma_{i}^{-1}(x-\mu_i)\right]}{\sqrt{(2\pi)^d |det(\sigma_i)|}}$
The GMM from the given point set is constructed as follows: i) the number of GMM components is equal to the number of points in the point set, and every component is weighted equally, ii) every component's mean vectors is represented by the spatial location of each point, iii) all components have same spherical covariance matrix.
An intuitive reformulation of the point set registration problem is to solve an optimization problem such that a certain dissimilarity measure between the Gaussian mixtures constructed from the transformed model set and the fixed scene set is minimized. For this method, L2 distance is chosen as the dissimilarity measure for measuring similarity between two Gaussian mixtures. The objective can then be minimized by either a closed-form numerical method (in case the function is convex) or an iterative gradient based method. The method was applied and tested on both rigid and non-rigid point set registration problems.

more
less