Received April 2015

ABSTRACT

The Coherent Point Drift (CPD) algorithm which based on Gauss Mixture Model is a robust point set registration algorithm. However, the selection of robustness weight which used to describe the noise may directly affect the point set registration efficiency. For resolving the problem, this paper presents a CPD registration algorithm which based on distance threshold constraint. Before the point set registration, the inaccurate template point set by resampling become the initial point set of point set matching, in order to eliminate some points that the distance to target point set is too close and too far in the inaccurate template point set, and set the weights of robustness as. In the simulation experiments, we make two group experiments: the first group is the registration of the inaccurate template point set and the accurate target point set, while the second group is the registration of the accurate template point set and the accurate target point set. The results of comparison show that our method can solve the problem of selection for the weight. And it improves the speed and precision of the original CPD registration.

Keywords:

Point Set Registration, Coherent Point Drift, Distance Threshold Constraint, Gauss Mixture Model

1. Introduction

The point set registration technology is widely used in image registration, target recognition, computer vision, image retrieval and classification, the mobile robot and so on. The registration usually falls into two categories: rigid or non-rigid. The goal of point set registration is to find the corresponding relationship between two sets of points and to solve the transform relationship. However, two sets of points were obtained from different imaging equipment, different perspectives, different time or different conditions (weather, illumination), so the relationship between two sets of points is not sure, and also due to deformation, noise and outliers, the point set matching is a very difficult problem.

Currently, point set registration algorithm is roughly divided into two categories: the one is based on the transformation parameter estimation algorithm, such as Coherent Point Drift [1], the iterative closest point [2], based on thin plate spline point set registration (TPS-RPM) [3]; and another kind is based on the feature registration algorithm, such as based on the algorithm of shape context [4], based on invariant features (SIFT) [5], based on spectral graph theory [6] and so on. Iterative closest Point(ICP) algorithm [2] [7] can better solve the problem of rigid registration, is based on a closest distance criterion and finds corresponding points through continuous iteration to establish corresponding relationship between two sets of points, and to solve transformation model, then to redetermine the corresponding relationship, and until it reaches the local minimum. Its structure is simple, computational complexity is low, but it may be more sensitive for noise and outliers, requires that the initial position of the two point sets be adequately close. TPS-RPM [3] effectively solve the defect of ICP, not only applies to the rigid registration, also to the non-rigid, and has the very strong robustness. However this algorithm is easy to fall into local optimum, and the iteration speed slower. The algorithm based on the feature usually requires the size, location, neighborhood structure between the two point sets cannot vary widely.

Compared with other point set registration algorithms, CPD has higher registration precision, not only to the rigid registration, also to the non-rigid. However, it finds the corresponding relationship between the two point sets by EM iteration minimizing the expectation of the negative log-likelihood function, there are two major defects: the one is that the selection of the weight parameters which is used to account for the noise and outliers directly affects the precision and efficiency of registration. Another is that the selection of initial registration parameters has important influence to the whole, may be trapped in local optimal solution. For the problem, this paper simply introduces the process of original CPD algorithm, and then presents a CPD registration algorithm based on distance threshold constraint. Before the point set registration, the inaccurate template point set by resampling becomes the initial point set of point set matching, in order to eliminate some points that the distance to target point set is too close and too far in the inaccurate template point set. And the experiment proves that it can improve the speed and precision of the original CPD registration.

2. The Coherent Point Drift Algorithm

2.1. The Introduction of CPD Algorithm Principle [1]

In fact, the CPD can be seen as a kind of probability density parameter estimation problem, where one point set represents the Gaussian mixture model centroids, and the other one represents the data points, the problem changes into maximum likelihood estimation by establishing the logarithmic likelihood function of the data points, We define the correspondence probability between two points sets as the posterior probability of the GMM centroids given the data point, the optimal registration place is likely to be the largest posterior probability.

Set up two sets of points: we define the template point set as, and the target point set as, represent the number of points, is the dimensions of the point set. We defines an uniform distribution as, the weight is. And the probabilities for all GMM components. So we get the weighted GMM probability density function [8]. And to see (1):

(1)

where. In registration process, when the template point set geome-

try transformation, is also changing. Through the covariance analysis, we consider that larger value of show that multiple points in the template point set corresponding to a point in the target point set. In order to find a one-to-one relationship, must be infinitely close to a minimum. So, we define geometric transformation relations of the template point set and the target point as, where R is a rotation matrix, t is a translation vector and s is a scaling parameter. We define the registration parameter set as, and according to the maximization likelihood function method, the parameter values are then found by minimizing the expectation of the negative log-likelihood function in (2):

(2)

CPD algorithm finds parameters by Expectation Maximization (EM) iteration [9]. E-step: to estimate the initial parameters, and use the Bayes’ theorem to compute a posterior probability distributions of mixture components. Then the objective function Q is an upper bound of the negative log-likelihood function in (2). M-step: to update parameters by minimizing the objective function in (3).

(3)

where, and computing the posterior probability in (4).

(4)

where.

Although the EM [9] [10] iterative algorithm can converge to the minimum of the negative logarithm likelihood function, the selection of directly affect the precision and efficiency of the point set registration. So, this paper presents a CPD registration algorithm which based on distance threshold constraint, in order to eliminate some points that the distance to target point set is too close and too far in the inaccurate template point set. And set the weights of robustness as. When the initial point set of registration is accurate point set, it has a good effect. The detailed process is as follows.

2.2. The Improvement of CPD Algorithm

For the template point set Y and the target point set X, for a point in the X, and computing the distance of to each point in the Y, we search for five points which ordered from small to large, such as. A polygon is formed with five points and computing (i = 1, 2, 3, 4, 5), where is the Euclidean Distance between two points. If, refers to Equation (5), is variable constant). Then computing where is the center of the polygon, is the minimum distance of to all point of the target point set Y. If, then eliminate.

We have found, the following is to find the maximum distance. For a point in the X, we search for five points which ordered from large to small according to the distance of to each point in the Y, such as. If, we find as same as the above algorithm. Finally, we get the distance threshold value interval of the target point set to the template point set:. The algorithm steps are as follows [11] [12]:

Fist-step: For the template point set Y and the target point set X, we search for five points which ordered from small to large according to the distance of to each point in the Y, such as. We get the coordinates of five points, then jumping Three-step. We determine whether the five points exist noise points according to the result of Three-step, If, then eliminate, and continue One-step . Otherwise jumping Four-step, in order to get the coordinates of the center of the polygon. Finally, we compute the minimum distance, then jumping Five-step.

Second-step: As same as One-step, we search for five points which ordered from large to small according to the distance of to each point in the Y, such as. We get the coordinates of five points, jumping Three-step.We determine whether the five points exist noise points according to the result of Three-step, if the result has noise points, then eliminate, and search Two-step again. Otherwise jumping Four-step, in order to get center of the polygon. Finally, we compute the maximum distance, then jumping Five-step.

Third-step: Firstly, we compute the average distance between the adjacent point of Point set X by Equation (5). Assume that the coordinates of the five points are, , , , , then compute the Euclidean distance between the adjacent two points in (6).

(5)

(6)

Fourth-step: Computing the coordinates of the center of the polygon by Equation (7).

(7)

where.

Fifth-step: We get the distance threshold value interval of the target point set to the template point set. We weed out the noise points which are away from the template point set with. Put the precise template point set and the target point set X as the initial iteration point sets of EM iteration.

Sixth-step: If and, then exiting the loop. The values of and are obtained by Equation (8). The latest parameters set is. the transformed template point sets is, where is column vector of all ones.

2.3. Experiment and Analysis

We use Windows XP system, Intel Pentium Dual, the memory of 1.81 GHz, 2 GB and the development environment is Matlab 2011b. We prepare Two groups of non-rigid images from different light, different perspective shooting as our experimental data. Converting the color images to the grayscale by Matlab, and extracting the image edge by canny method. In the process of extracting edges, in order to ensure the integrity and continuity of the image edge, there may be some noise points in extracted images. Figure 1(a) is shoot under the condition of the weak illumination change, after a series of operations, there is less noise in the extracted image. However, Figure 1(b) is shoot under the condition of the strong light change, there is more noise in the image edge. And the rotation, translation, scaling transformation will exist between the two images.

In order to verify the algorithm in this paper, Figure 1(a) is the inaccurate template point set, Figure 1(b) is the accurate target point set. Figure 2 show the process of registration between the inaccurate template point set and the accurate target point set with the original algorithm of CPD. We can see that CPD has very strong robustness for noise and outliers, eventually achieve a precise matching. But the number of iteration is as high as 117 times, 12 minutes 20.9318 seconds. If we make a precise processing for the inaccurate data before registration, on the basis of ensuring the integrity of the target edge character, we eliminate some noise points. The verification results are shown in Figure 3. Figure 3 show that after eliminating the noise points, the template point set quickly find the matching position, and the registration error is very small when the iteration times are 10 , always takes 2.6792 seconds and iteration 46 times. So the experiment proves that this algorithm can improve the speed and precision of the original CPD registration.

This experiment uses two critical condition of iteration as registration accuracy standard, namely covariance and standard tolerance. Refer to (8):

(8)

where, respectively is the logarithmic likelihood function values of iteration registration for the last

time and the previous logarithmic likelihood function values.

Figure 4 shows the comparison experiment on the registration accuracy between the inaccurate template point set and the accurate template point set. The X axis is the number of iterations. With the increase of the number of iterations, the changes on the covariance and standard tolerance. We can see that when we use the accurate template point set, curve is monotone decreasing, and soon reach a steady state. For inaccurate templates point set, due to the interference of noise, may cause relevant points registration errors or fall into local optimum, curve is not smooth, and achieve the speed of smaller registration error is slow.

In the Table 1, , , where said the norm of the matrix, is the rotation error value of the transformed template point set and the target point set. is the scaling error value of the transformed template point set and the target point set. Although the two algorithms

achieve a smaller value on the registration accuracy, this algorithm is better than the original algorithm on the accuracy.

4. Conclusion

The Coherent Point Drift is a kind of efficient point set registration algorithm, and obtains better effect, but the selection of robustness weight may directly affect the point set registration efficiency. So this paper presents a CPD registration algorithm which based on distance threshold constraint. The experiment proves that these point sets which resampling by this algorithm are involved in CPD registration algorithm, the weight of robustness is. We can see that it can reduce the number of iteration registration and time, and can obtain the smaller registration error.

Cite this paper

Wei Guang Liu,Tian Wang, (2015) Image Registration Technique Based on a Fast CPD Algorithm. Journal of Computer and Communications,03,182-188. doi: 10.4236/jcc.2015.35023

References