Rigid Point Set Registration (EU FP7 GRASP project)

Point set registration is a fundamental problem in computational geometry with applications in the fields of computer vision, computer graphics, image processing and many others. The problem can be formulated as follows. Given two finite point sets M (for model) and D (for data) find a mapping T such that the point set T(D) is optimally aligned (in some sense) to the model M.

If T is a rigid transform we have the problem of rigid point set registration. This special case is of major importance for the tasks of object recognition, tracking, localization and mapping, and object modeling, just to name a few. The problem is especially hard when no initial pose estimation is available and the data point set is noisy, outlier corrupted and incomplete.

Figure 1. Left: Model point set. Middle: Data point set. Right: Registration result, i.e., the model and data point sets after registration.

Our Approach

We pay special attention to noise robustness, outlier resistance and global optimal alignment (without making any assumptions about the initial position and orientation of the input point sets). The problem of registering two point clouds in space is converted to a minimization of a nonlinear cost function. We propose a cost function that aims to reduce the impact of noise and outliers. Its definition is based on the input point sets and is directly related to the quality of a concrete rigid transform between them. In order to achieve a globally optimal registration, we develop a new stochastic approach for global minimization. Tests on a variety of point sets show that our registration algorithm performs very well on noisy, outlier corrupted and incomplete data.

  • Cost Function Definition: Our cost function is a six-dimensional scalar field which definition is based on an unsigned inverse distance field of the model point set. A perfect match between model and data (which maps all data points exact on the model points) corresponds to a global minimum of the cost function. The worse the match the greater is the cost function value.
  • Stochastic Global Minimization: The cost function we use is non-linear and therefore has many local minimizers which correspond to sub-optimal registration results. In order to achieve the best possible registration for the given input sets, we develop a global minimization method. The minimization problem is treated as a search over an n-dimensional box (in our case n = 6) which contains a global minimizer. Our algorithm subdivides the search space in smaller boxes and assigns to each box the function value at a randomly sampled point within the current box. The decision which box to subdivide further is based on a probabilistic scheme which favours boxes with low function value. Thus, more detail is added to "promissing" regions in the search space, i.e., to regions which are likely to contain a global minimizer of the objective function.

Experimental Results

In the following, we present our registration results for a variety of noisy, outlier corrupted and incomplete point sets. We present two main test scenarios:
  • Registration of low resolution, incomplete and outlier corrupted point sets of the Stanford bunny (shown in Figure 3) to the model point set shown on the left in Figure 2.
  • Registration of low resolution, incomplete and noisy point sets of the Stanford dragon (Figure 4) to the model point set shown on the right in Figure 2.

Figure 2: Model point sets used in our registration experiments. Although they are shown as meshes, no surface information is used for registration.

Figure 3: Low resolution, incomplete and outlier contaminated data point sets of the Stanford bunny used for registration. The number of outliers increases from left to right.

Figure 4: Low resolution, incomplete and noisy data point sets of the Stanford dragon used for registration. The amount of noise increases from left to right. Although all of them are shown as meshes, only points are used for registration.


The following images show typical registration results achieved by our registration method. Again, note that in all test scenarios no assumptions about initial position and orientation of the point sets are made. Each of the four bunny data point sets shown in Figure 3 is registered to the model set shown on the left of Figure 2. Results are shown in Figure 5. Figure 6 shows registration results for the data point sets in Figure 4 and the dragon model set on the right in Figure 2.

Figure 5: Registration results for the data point sets shown in Figure 3 and the model set on the left in Figure 2.

Figure 6: Registration results for the data point sets shown in Figure 4 and the model set on the right in Figure 2.

Publications

Chavdar Papazov and Darius Burschka. Stochastic Optimization for Rigid Point Set Registration. In Proceedings of the 5th International Symposium on Visual Computing (ISVC'09), volume 5875 of Lecture Notes in Computer Science, pages 1043-1054. Springer, December 2009. (paper, slides, more info)

Links

For more information about rigid/non-rigid registration, object recognition and other related topics can be found here.
GRASP - Emergence of Cognitive Grasping through Introspection, Emulation and Surprise

People