# Point Set Registration Based on Improved KL Divergence

Authors: Guangfu Qu; Won Hyung Lee
Journal: Scientific Programming
 (2021)

---

## Abstract

A point set registration algorithm based on improved Kullback–Leibler (KL) divergence is proposed. Each point in the point set is represented as a Gaussian distribution. The Gaussian distribution contains the position information of the candidate point and surrounding ones. In this way, the entire point set can be modeled as a Gaussian mixture model (GMM). The registration problem of two point sets is further converted as a minimization problem of the improved KL divergence between two GMMs, and the genetic algorithm is used to optimize the solution. Experimental results show that the proposed algorithm has strong robustness to noise, outliers, and missing points, which achieves better registration accuracy than some state-of-the-art methods.


---

## Body

## 1. Introduction

Point set registration is an important content of computer vision and pattern recognition, which is widely used in image registration [1], target recognition [2], image processing [3], etc. The task of point set registration is to find the corresponding relationship between the point patterns from two different point sets and solve the transformation parameters from one point set to another. However, in actual cases, the noises, outliers, and missing points exist, resulting in a sharp drop in the accuracy of point set registration. These problems have become a hot but difficult problem in current computer vision and pattern recognition field. Therefore, it is urgent to study and develop robust and high-precision point set registration algorithms.Point set registration algorithms can be basically divided into two categories. One is to find the correspondence relationship by estimating the space transformation parameters between two point sets. This type of algorithm mainly includes iterative closest point (ICP) [4], the thin-plate spline [5], etc. Another type is based on point features. The transformation relationship between point sets is found through the point feature recognition. This type of algorithm mainly includes the methods based on invariant features [6], the methods based on shape context [7], etc., which are validated to be robust to noise, outliers, and missing points. The ICP algorithm is one of the most basic and most commonly used point set registration algorithms. The basic principle of the ICP algorithm is to find the correspondence between the points in the two point sets according to the nearest neighbor criterion and calculate the average point pair between the two point sets. The transformed point set is used as the input. The square error is calculated between two point sets. The ICP algorithm is a simple and intuitive point set registration method. When the initial positions of the two point sets are not much different and there is a clear “one-to-one” correspondence between the two point sets, the registration accuracy of the ICP algorithm is higher. However, in the presence of outliers, missing points, and noise, the accuracy of the ICP algorithm drops sharply. Some researchers have proposed some improved algorithms for the problems of the ICP algorithm [8–10], but they basically require the initial positions between the two point sets to be relatively close.Different from the requirement for clear “one-to-one” correspondence, a registration algorithm with a “one-to-many” correspondence was proposed in [11]. The corresponding relationship between the two point sets is constructed into a matrix, and the solution of the optimization problem is sought by the method of simulated annealing. Andriy and Xubo improved the algorithm in [11], using the expectation-maximization (EM) algorithm to solve the correspondence between transformation parameters and points. At the same time, the Gaussian radial basis function (GRBF) was employed instead of the thin-plate spline model to represent the nonrigid change of the point set. Experiments show that this method achieved better robustness in nonrigid registration. In recent years, under the framework of EM algorithm optimization, some robust point set registration algorithms have been proposed [10, 12, 13]. This type of algorithm models the two point sets as Gaussian mixture models (GMMs). Afterwards, the problem of finding the corresponding relationship between the two point sets can be regarded as the problem of maximizing the posterior probability. This kind of algorithm has good robustness to noise, missing points, and outliers with high registration accuracy. However, in this type of algorithm, the accuracy of the transformation parameters between the point sets is affected by the point set modeling. In response to these shortcomings, some registration algorithms that do not need to solve the correspondence between points were proposed [12, 14–17]. These methods also model the two point sets as GMM, respectively, and then the point set registration problem is transformed into the problem of finding the difference between two GMMs. The corresponding parameter when the difference between the two GMMs is the smallest is adopted as the transformation parameter of the point sets. Experiments have proved the robustness of this type of algorithm to noise, outliers, and missing points, but the accuracy of the algorithm will decrease when there are more noise and outliers. In addition, in synthetic aperture radar (SAR) images, nonuniform GMM was used to model the edge point set of water bodies, and high-precision registration of water bodies was achieved [18–20].Based on the idea of robust point set registration algorithm, combined with the statistics of point set, this paper proposes a point set registration algorithm based on improved Kullback–Leibler (KL) divergence. The proposed method models the two point sets to be registered as GMMs, respectively, where each point in the point set is represented as a Gaussian distribution. The mean value is the position coordinate of the point, and the size of the root variance represents the influence of the surrounding points on this point size, using equal weight coefficients to mix Gaussian distribution. Based on the above modeling, the point set registration problem is transformed into a problem that minimizes the improved KL divergence between two GMMs. The transformation parameters of the registration are solved by genetic algorithm. Experiments have proved that the proposed method has good robustness to noise, outliers, and missing points in comparison with some existing point registration algorithms.


## 2. GMM of Point Set

In the point set registration process, it is necessary to fix a scene point set to be used as a registration template and another point set as a model set to perform registration according to changing transformation parameters. For the model setm and the scene set s, the numbers of points in the two point sets are usually different due to the presence of noise, outliers, and missing points. Assuming that the numbers of points in the point sets m and s are M and S, respectively, the GMMs are established for the two point sets as follows:(1)px|θ=∑i=1Mαiϕx|μi,Σi,py|Θ=∑j=1Sβjϕy|νj,Γj,where px|θ and py|Θ represent the GMMs with the parameters θ and Θ, respectively, in which θ includes αi, μi, and Σi and Θ includes βj, νj, and Γj; ϕx|μi,Σi and ϕy|νj,Γj represent the ith and jth Gaussian distributions in the two GMMs, respectively, in which μi and νj are the corresponding mean values andΣi and Γj are the corresponding covariance matrices; and αi and βj are the mixing coefficients in GMMs.In order to express the relationship between the points,μi and νj are denoted as the mean values and Σi and Γj are denoted as the covariance matrix Γj=Σi=σ2Ι. The Gaussian distribution can be modeled as follows [15]:(2)ϕx|μi,Σi=12πσ2exp−x−μi22σ2,ψx|νj,Γj=12πσ2exp−x−νj22σ2,where σ2 is the variance of the Gaussian distribution and ⋅ calculates the norm of the vector.Each point in the two point set is modeled as a Gaussian distribution as equation (2). M and S represent the numbers of points in the two point sets, which are also the numbers of GMM components. The above formula is formed for two-dimensional point sets, but it can be directly extended to three-dimensional in mathematics. The variance σ2 in each Gaussian distribution indicates the influence of points in the neighborhood. The larger the variance, the greater the influence from the surrounding points. On the contrary, a smaller variance indicates lower influences. The mixing coefficients αi and βj are determined in the equal forms, i.e., αi=1/M, βj=1/S.


## 3. Point Set Registration Based on Improved KL Divergence

### 3.1. Improved KL Divergence between Two GMMs

After getting the GMMs of two point sets, the registration problem is transformed into a minimization problem of optimally solving the difference between GMMs. In [21], the difference between GMMs is evaluated using a combination of KL divergence and distance to move. In [22], the KL divergence is used to calculate the difference between two GMMs. Since KL divergence does not satisfy symmetry and triangle inequality and is not a true distance measure, this paper employs an improved KL divergence, i.e., symmetry KL (SKL), to calculate the difference between two GMMs.For two GMMspx|θ and qx|Θ, which are denoted as px and qx in the following, the SKL divergence between them is calculated as follows:(3)SKLpx,qx=12KLpx,qx+KLqx,px,where KLpx,qx represents the SKL divergence between the GMM models px and qx. The core of equation (3) is to calculate the SKL divergence between two GMM models px and qx. Because there is no analytical expression for the SKL divergence, a numerical approximation method is required for calculation, and a matching approximation method is used in this paper.For two GMM modelspx and qx, they contain M and S Gaussian distributions as follows:(4)px=∑i=1Mαifix,qx=∑j=1Sβjgjx.The SKL divergence is given by the following equation:(5)SKLpx,qx=∫pxlnpxqxdx+∫qxlnqxpxdx.According to the properties of the convex function and substituting equation (4), the following inequality [23] can be obtained:(6)SKL∑i=1Mαifi∑j=1Sβjgj≤∑i,jαiβjSKLfigj.According to the principle of matching approximation, it can be further obtained as follows:(7)SKLp‖q≈∑i=1nαilogαifi+∑j=1nβjlogβjgj−∑i=1nαimaxj∫filogβjgj−∑i=1nβimaxj∫gilogαjfj=∑i=1nαiminjSKLfigj+logαiβj.According to the approximation of the equation (7), it can be seen that px and qx have a mapping relationship π:1,2,⋯,n⟶1,2,⋯,m. In this paper, the corresponding relationship is described as follows:(8)πi=argminjSKLfi‖gj−logβj.The corresponding relationship is substituted, and the simplification can be obtained as follows:(9)SKLmatchf‖g=∑i=1nαiSKLfi‖gπi+logαiβπi.According to the chain rule of divergence [24, 25], the above formula can be further simplified as follows:(10)SKLmatchp,q=∑i=1MSKLfi,gi−logCπ,where Cπ=∑i=1Mβπi. The above equation can be seen as an approximate calculation for the matching of SKL divergence between two GMMs.


### 3.2. Point Set Registration Algorithm

Based on the calculation of the SKL divergence between two GMMs, a transformationT = {R, s, t} is given to the model set s. The transformed point set is expressed as T (s). Then, the point set registration problem is to find the minimum value of the SKL divergence between the point set m and the point set s, namely, argminSKLm,Ts. In this paper, the genetic algorithm is used to solve the above optimization problem. The process of point set registration algorithm can be divided into the following steps:Step 1: give an initial transformation to the point setsR=I,s=1,t=0.Step 2: calculate the SKL divergence between the two GMMs and compare it with the preset threshold. If it is greater than the threshold, go to step 3. If it is less than the threshold, go to step 4.Step 3: the genetic algorithm is used to solve the problemargminSKLm,Ts with the optimization parameters.Step 4: the point set registration result is obtained according to the optimized parameters.


## 3.1. Improved KL Divergence between Two GMMs

After getting the GMMs of two point sets, the registration problem is transformed into a minimization problem of optimally solving the difference between GMMs. In [21], the difference between GMMs is evaluated using a combination of KL divergence and distance to move. In [22], the KL divergence is used to calculate the difference between two GMMs. Since KL divergence does not satisfy symmetry and triangle inequality and is not a true distance measure, this paper employs an improved KL divergence, i.e., symmetry KL (SKL), to calculate the difference between two GMMs.For two GMMspx|θ and qx|Θ, which are denoted as px and qx in the following, the SKL divergence between them is calculated as follows:(3)SKLpx,qx=12KLpx,qx+KLqx,px,where KLpx,qx represents the SKL divergence between the GMM models px and qx. The core of equation (3) is to calculate the SKL divergence between two GMM models px and qx. Because there is no analytical expression for the SKL divergence, a numerical approximation method is required for calculation, and a matching approximation method is used in this paper.For two GMM modelspx and qx, they contain M and S Gaussian distributions as follows:(4)px=∑i=1Mαifix,qx=∑j=1Sβjgjx.The SKL divergence is given by the following equation:(5)SKLpx,qx=∫pxlnpxqxdx+∫qxlnqxpxdx.According to the properties of the convex function and substituting equation (4), the following inequality [23] can be obtained:(6)SKL∑i=1Mαifi∑j=1Sβjgj≤∑i,jαiβjSKLfigj.According to the principle of matching approximation, it can be further obtained as follows:(7)SKLp‖q≈∑i=1nαilogαifi+∑j=1nβjlogβjgj−∑i=1nαimaxj∫filogβjgj−∑i=1nβimaxj∫gilogαjfj=∑i=1nαiminjSKLfigj+logαiβj.According to the approximation of the equation (7), it can be seen that px and qx have a mapping relationship π:1,2,⋯,n⟶1,2,⋯,m. In this paper, the corresponding relationship is described as follows:(8)πi=argminjSKLfi‖gj−logβj.The corresponding relationship is substituted, and the simplification can be obtained as follows:(9)SKLmatchf‖g=∑i=1nαiSKLfi‖gπi+logαiβπi.According to the chain rule of divergence [24, 25], the above formula can be further simplified as follows:(10)SKLmatchp,q=∑i=1MSKLfi,gi−logCπ,where Cπ=∑i=1Mβπi. The above equation can be seen as an approximate calculation for the matching of SKL divergence between two GMMs.


## 3.2. Point Set Registration Algorithm

Based on the calculation of the SKL divergence between two GMMs, a transformationT = {R, s, t} is given to the model set s. The transformed point set is expressed as T (s). Then, the point set registration problem is to find the minimum value of the SKL divergence between the point set m and the point set s, namely, argminSKLm,Ts. In this paper, the genetic algorithm is used to solve the above optimization problem. The process of point set registration algorithm can be divided into the following steps:Step 1: give an initial transformation to the point setsR=I,s=1,t=0.Step 2: calculate the SKL divergence between the two GMMs and compare it with the preset threshold. If it is greater than the threshold, go to step 3. If it is less than the threshold, go to step 4.Step 3: the genetic algorithm is used to solve the problemargminSKLm,Ts with the optimization parameters.Step 4: the point set registration result is obtained according to the optimized parameters.


## 4. Experiment and Analysis

In order to analyze and compare the robustness and effectiveness of the point set registration algorithm proposed in this paper, experiments are carried out using the point set data in the Chui dataset. At the same time, the results of rigid body point set registration based on SKL divergence are compared with ICP algorithm [4], kernel correlation (KC) algorithm [15], and coherent point drift (CPD) [11], respectively. The registration success rate (RSR) and MSE are used as indexes to measure registration accuracy.The “fish” point set data in the Chui dataset are used as the template point set, and random outliers and noise with a ratio of 0.2 and 0.8 are added to the sample point set, respectively. SKL algorithm and ICP are used for the template point set and the sample point set. The algorithm, KC algorithm and CPD algorithm are used for registration experiments. Because the registration results of the ICP algorithm are too poor when there are many outliers, the experimental results are not listed. The comparison results of the other algorithms are shown in Figures1–4. It can be seen from the results that when the outliers and noise are not serious, the equation registration accuracy of CPD, KC, and SKL algorithms is relatively higher. However, when the outliers and noise are severe, the registration accuracy of CPD is poor. Both KC and SKL have better registration accuracy, and the registration result of SKL in this paper is better than that of KC.Figure 1
Registration results of different algorithms at 20% outliers. (a) Original point set. (b) Results of KC. (c) Results of CPD. (d) Results of the proposed method.
(a)(b)(c)(d)Figure 2
Registration results of different algorithms at 80% outliers. (a) Original point set. (b) Results of KC. (c) Results of CPD. (d) Results of the proposed method.
(a)(b)(c)(d)Figure 3
Registration results of different algorithms at 20% noise. (a) Original point set. (b) Results of KC. (c) Results of CPD. (d) Results of the proposed method.
(a)(b)(c)(d)Figure 4
Registration results of different algorithms at 80% noise. (a) Original point set. (b) Results of KC. (c) Results of CPD. (d) Results of the proposed method.
(a)(b)(c)(d)In order to quantitatively compare the registration results of SKL, KC, CPD, and ICP, the experiments are conducted under “no outlier or noise” and different levels of interferences of 20%, 40%, 60%, 80%, and 100%. The registration success rate and MSE value of different registration algorithms are calculated. The results are shown in Tables1 and 2. From the experimental results, it can be seen that when the ratio of outliers and noise is less than 60%, the accuracy RSR of SKL and KC algorithms is equivalent to the value of MSE. Also, both are better than the registration results of CPD. ICP has the lowest registration accuracy. When the ratio of outliers to noise is greater than 60%, the RSR of SKL is the highest, and the error of MSE is the smallest. The above experimental results fully verify the robustness and effectiveness of the registration algorithm proposed in this paper.Table 1
Registration accuracy at different outlier proportions.
MethodProportion of outliers020%40%60%80%100%RSRMSERSRMSERSRMSERSRMSERSRMSERSRMSEProposed0.980.020.930.080.870.150.790.200.740.260.590.35ICP0.960.030.920.100.850.170.760.230.700.280.570.39KC0.970.030.920.120.840.160.750.250.720.300.520.42CPD0.970.030.910.130.830.190.760.240.690.320.530.43Table 2
Registration accuracy at different noise proportions.
MethodProportion of noises020%40%60%80%100%RSRMSERSRMSERSRMSERSRMSERSRMSERSRMSEProposed0.970.020.920.070.850.160.760.210.760.220.580.34ICP0.950.040.910.110.830.180.750.250.730.250.550.42KC0.940.030.900.110.850.170.740.230.730.310.550.46CPD0.940.020.910.120.820.210.740.220.740.300.540.45


## 5. Conclusion

This paper proposes a point set registration algorithm based on improved KL divergence. By separately modeling two point sets as GMMs, the point set registration problem is transformed into a problem of finding the minimum KL divergence between two GMMs. The genetic algorithm is used to solve the transformation parameters of the point set registration, and the SKL divergence between the two Gaussian mixture models is calculated by the matching approximation method. The registration experiment is carried out under different outliers and noise ratios, and the registration achievement rate and MSE are used to measure the registration accuracy of the algorithm. The experimental results verify the effectiveness of the algorithm in this paper.



---

*Source: 1207569-2021-10-06.xml*