Nothing Special   »   [go: up one dir, main page]
Next Article in Journal
An Area Coverage and Energy Consumption Optimization Approach Based on Improved Adaptive Particle Swarm Optimization for Directional Sensor Networks
Previous Article in Journal
Classification Method for Viability Screening of Naturally Aged Watermelon Seeds Using FT-NIR Spectroscopy
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Sensors
Volume 19
Issue 5
10.3390/s19051191
sensors-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Review

A Review of Point Set Registration: From Pairwise Registration to Groupwise Registration

by
Hao Zhu
1,*,
Bin Guo
1,
Ke Zou
1,
Yongfu Li
1,
Ka-Veng Yuen
2,
Lyudmila Mihaylova
3 and
Henry Leung
4
1
Key Laboratory of Industrial IoT and Networked Control, Ministry of Education, and the Key Laboratory of Intelligent Air-Ground Cooperative Control for Universities in Chongqing, College of Automation, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
2
Faculty of Science and Technology, University of Macau, Macau 999078, China
3
Department of Automatic Control and Systems Engineering, University of Sheffield, Mappin Street, Sheffield S1 3JD, UK
4
Department of Electrical and Computer Engineering, University of Calgary, 2500 University Drive NW, Calgary, AB T2N 1N4, Canada
*
Author to whom correspondence should be addressed.
Sensors 2019, 19(5), 1191; https://doi.org/10.3390/s19051191
Submission received: 7 December 2018 / Revised: 25 February 2019 / Accepted: 5 March 2019 / Published: 8 March 2019
(This article belongs to the Section Remote Sensors)
Browse Figures
Figure 1
<p>Some challenges in the point set registration [<a href="#B22-sensors-19-01191" class="html-bibr">22</a>].</p> "> Figure 2
<p>Taxonomy of point set registration methods.</p> "> Figure 3
<p>Pairwise point set registration problem: find the correspondences and the transformation of two point sets.</p> "> Figure 4
<p>An example of GM problem.</p> "> Figure 5
<p>The forward approach of groupwise point set registration method in [<a href="#B108-sensors-19-01191" class="html-bibr">108</a>].</p> "> Figure 6
<p>The backward approach of groupwise point set registration method in [<a href="#B2-sensors-19-01191" class="html-bibr">2</a>].</p> "> Figure 7
<p>Registration results obtained from the application of pair-wise rivals on the Chinese characters set and fish shapes for different level of degradation. Data with different levels of deformation (first row) and the corresponding obtained results by KC (second row), ICP (third row), TPS-RPM (fourth row), CPD (fifth row), CPD-GL (sixth row), and SCGF (seventh row).</p> "> Figure 8
<p>MSED, in log-scale, achieved from the application of the under-comparison pair-wise registration algorithms on the Chinese characters set and fish shapes for different levels of degradation.</p> "> Figure 9
<p>Registration results obtained from the application of pair-wise rivals on a specific example generated from 3D COPD data. Initial unregistered point sets (first column) and the results of CPD (second column), CPD-GL (third column), and SCGF (fourth column).</p> "> Figure 10
<p>MSED achieved from the application of the under-comparison pair-wise registration algorithms on multiple point set groups generated by 3D COPD data (please see text for the details).</p> "> Figure 11
<p>Registration results obtained from the application of group-wise rivals on the Chinese characters set and fish shapes for different level of degradation. Data with different levels of deformation (first row) and the corresponding obtained results by CDF-HC (second row), JRMPC (third row), TMM (fourth row), and Rényi’s (fifth row).</p> "> Figure 12
<p>MSED, in log-scale, achieved from the application of the under-comparison group-wise registration algorithms on the Chinese characters set and fish shapes for different levels of degradation.</p> "> Figure 13
<p>Registration results obtained from the application of group-wise rivals on a specific example generated from 3D COPD data. Initial unregistered point sets (first column) and the results of JRMPC (second column) and TMM (third column).</p> "> Figure 14
<p>MSED achieved from the application of the under-comparison group-wise registration algorithms on multiple point set groups generated by 3D COPD data (please see text for the details).</p> ">
Versions Notes

Abstract

:
This paper presents a comprehensive literature review on point set registration. The state-of-the-art modeling methods and algorithms for point set registration are discussed and summarized. Special attention is paid to methods for pairwise registration and groupwise registration. Some of the most prominent representative methods are selected to conduct qualitative and quantitative experiments. From the experiments we have conducted on 2D and 3D data, CPD-GL pairwise registration algorithm and JRMPC groupwise registration algorithm seem to outperform their rivals both in accuracy and computational complexity. Furthermore, future research directions and avenues in the area are identified.

1. Introduction

Point set registration is a challenging aspect in pattern recognition [1,2,3,4,5], computer vision [6,7], robotics [8,9,10,11] and image processing [12,13,14]. For example, in medical image processing, in order to fuse multiple images by computed tomography (CT), magnetic resonance imaging (MRI) and positron emission tomography (PET), the fundamental step is to register the feature points from CT, MRI, and PET. In intelligent vehicles, pre-processing is an important step prior to feature points extraction from many sensors, such as radio detection and ranging (Radar), light detection and ranging (LiDAR) and camera. Point set registration methods [15,16] have then proposed to align the images and extract feature points that will be further used for localization and mapping. In face recognition, face landmarks are extracted from a face with different facial expressions or different viewpoints. Then, point set registration can be used to perform the task of face recognition [17].
The main purpose of the point set registration is to find correspondences and to estimate the transformation between two or more point sets. In practice, point set registration methods suffer from many challenges due to deformation and noise. Different viewpoints or different poses may cause the deformation between point sets. The noise between point sets includes occlusion and outliers. Missing points occur due to feature extraction in the case of occlusion. Outliers have no correspondence in the other point sets. These challenges are shown in Figure 1. Furthermore, high dimensionality and massive point sets are commonly encountered in the real world, e.g. about million points will be obtained by LiDAR scanning. The scale-invariant feature transform (SIFT) methods [18,19] have contributed to solving many challenging problems with LiDAR and other imagery data. Recently, some deep learning methods have also been developed to select the feature points from medical image and remote sensing image [20,21].
Normally, the point set registration methods fall into two categories: pairwise and groupwise. Pairwise registration only considers two point sets while groupwise registration performs more than two point sets simultaneously. According to the modeling methods of point set registration, they can be categorized into parametric models and non-parametric models. Parametric models include the classic iterative closest point (ICP) method [23,24], and probabilistic point set registration using Gaussian mixture model (GMM) [25]. Graph matching (GM) is the traditional method in the non-parametric model [26]. According to the difference in transformation, the point set registration methods can be roughly classified into rigid transformation and nonrigid registration. The rigid transformation only considers translation, rotation, and scaling. The affine transformation, which is a nonrigid transformation, allows anisotropic scaling and skews [25]. Compared with rigid transformation, the nonrigid transformation is more challenging as the true nonrigid transformation model is often unknown [27,28]. The methods of point set registration are summarized in Figure 2.
The rest of the paper is organized as follows. Section 2 describes the pairwise point set registration methods. Section 3 reviews the groupwise point set registration methods. Some representative point set registration algorithms are selected to conduct experiments comparison in Section 4. Finally, Section 5 concludes the paper and gives the future trends and research avenues in this area.

2. Pairwise Point Set Registration

Considering two point sets X = { x i x i ∈ ℜ D } i = 1 N and Y = { y j y j ∈ ℜ D } j = 1 M , where D denotes the dimension of these points. An example of pairwise point set registration is shown in Figure 3. The goal of pairwise point set registration methods is to find the suitable transformation and to establish the correct correspondences between X and Y . Many methods have been developed to address this problem. Some surveys on recent developments in pairwise point set registration can be found in [29,30]. These methods can be roughly classified into three categories: distance-based methods, filtering-based methods and probability-based methods.

2.1. Distance-Based Methods

The distance-based point set registration methods involve a dual-step scheme. The first step is to compute a distance between two point sets and to find the correspondences. Then, the distance between two point sets with the determined correspondences is minimized in the second step. The ICP, introduced by Besl and McKay [23] and Zhang [24], is the well-known method in the field of point set registration for rigid transformation between two points. The ICP can be expressed an optimization problem
arg min R , t 1 M ∑ j = 1 M y j - ( R x j + t ) 2
where x j and y j is a correspondence pair, . 2 is the Euclidean norm, R and t are a rotation matrix and translation vector, respectively; and M is the number of correspondence pairs. Some surveys on recent developments in ICP method can be found in [31,32,33]. Many stages and efficient variants are given in the literature [31], such as selection of points, matching points, weighting of pairs, rejecting pairs, error metric and minimization, and high-speed variants. The aim of selection of point is to boost the convergence of ICP algorithm. The step of matching points is to find the correspondences between two point sets. Some methods have been proposed to assign the weights of correspondence [31], such as constant weight method, larger weight method, distance points method and smaller weight method. The purpose of rejecting pairs is to eliminate outliers for improving the performance of point set registration. Finally, the correspondence is computed using the current transformation and a new transformation is obtained by minimizing the sum of squared distances between the correspondence points.
However, the ICP method is sensitive to the initial conditions and can be trapped into local minima. A robust point matching (RPM) method [34] was proposed to solve this problem. RPM combines deterministic annealing and soft-assign optimization to convexify the objective function. However, the RPM method is restricted to perform rigid-body transformation. Therefore, a thin-plate spline robust point matching (TPS-RPM) method was developed in [35]. Deterministic annealing, soft-assign, thin-plate spline for spatial transformation and outlier rejection are used to perform both the correspondences and transformation parameters [35]. However, the TPS-RPM method can hardly be easily extended for higher dimension point sets.
In [36], a kernel correlation (KC) algorithm was proposed to align intensity images. KC is a function of point set entropy and an affinity measure. The point set registration is performed by maximizing the KC of point sets. In [37], point set registration was formulated by kernel density correlation metric, which is similar to the method in [36]. It is noted that a kernel function mainly determines the performance of point set registration in the KC method.
In [38], a GMMReg method was proposed to perform point set registration. Two point sets can be represented by two Gaussian mixture models (GMMs). The point set registration is considered as aligning the two GMMs. The Euclidean distance of two GMMs was minimized to estimate the transformation of two point sets. In [39], a support vector-parametrized Gaussian mixture (SVGM) method, which is an adaptive data representation method of point sets, was developed to improve the robustness to outliers, noises, and occlusions. In SVGM, the point set is represented by a one-class support vector model (SVM) and the output function is approximated by a GMM.
Graph matching (GM) is a popular method in the point set registration using non-parametric model [26]. An example of GM is shown in Figure 4. A graph consists of some vertices and edges. GM methods find the correspondences between two graphs using the feature descriptors with vertexes and edges [40,41]. Some surveys in the GM method are given in [42,43]. GM can be considered as an optimization problem. The objective function of the optimization problem incorporates with vertices and edges of two graphs. In the form of objective function, the GM methods can be classified into three categories as first-order GM methods, second-order GM methods and high-order GM methods. First-order GM methods only consider the local feature descriptors with the information of vertexes. This idea is similar to ICP and its variants.
Most current GM algorithms are second-order or high-order GM methods [22,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65]. Second-order GM methods combine the similarity of vertices-to-vertices and edges-to-edges. High-order GM methods involve the information of hyper-graph, which is hyper-edges incorporating the angles of tuples of vertices. The second-order or high-order GM methods are expressed as a quadratic assignment problem (QAP) [44].
Many second-order GM methods have been reported in the literature. In contrast to the linear assignment problem in first-order GM methods, which can be performed by the Hungarian algorithm, the QAP is an NP-hard problem [45]. Therefore, one issue of GM method is on the development of an accurate estimation algorithm. Many methods have been proposed to approximate the QAP problem. It can be classified into three categories: spectral relaxation, semi-definite programming relaxation, and doubly stochastic relaxation. In [46], a spectral relaxation was proposed to approximate the QAP problem, and then the spectral matching (SM) method was developed. In [47], a new SM method was incorporated with an affine constraint to provide a higher relaxation than the SM method. The semi-definite programming (SDP) relaxation is another method for approximating the QAP solution. The SDP methods relax the non-convex constraint using a convex semi-definite. The correspondence is approximated using a randomized algorithm [48] or a winner-take-all method [49]. Using a doubly stochastic matrix, the optimizing GM is transformed as a non-convex QAP problem. Therefore, many methods can be used to find a local optimum. In [50], the quadratic cost was approximated using a linear program, which was performed by a simplex-based algorithm. In [51], an integer projection algorithm was proposed to optimize the objective function in the integer domain. In [53], a probabilistic formulation of the SM method [46] was given. It estimates the assignment probabilities by maximum-likelihood. More recently, a factorized graph matching (FGM) method was developed in [22]. In FGM, the large pairwise affinity matrix was factorized into some smaller matrices. A path-following optimization algorithm was then proposed to improve the matching performance.
High-order GM methods involve high-dimensional of information of hyperedges. Third-order GM methods are usually considered. The advantage of high-order GM methods is that the high-order matching method is invariant to scale and affine changes. In [55], a probabilistic interpretation of high-order GM methods was formulated. In [56], the high-order matching problem was formulated as a tensor optimization problem. In [57], an high-order GM method was developed by adopting jumps with a reweighting scheme. In [58], a framework of tensor block coordinate ascent methods was proposed for high-order matching. Recently, In [65], a K-nearest-neighbor-pooling matching method, which integrates feature pooling into GM, was introduced for a second-order GM. A sub-pattern structure was then constructed for a high-order GM.

2.2. Filtering-Based Methods

The filter-based point set registration methods perform the point set registration using a state space model (SSM). In general, the SSM is formulated as:
x ˜ k = x ˜ k - 1 + v k y k = f ( x ˜ k , x k ) + w k
where x k and y k are the points from two sets; x ˜ k is the state at time k, and it can be written as x ˜ k = [ t k x , t k y , θ k ] T in 2D point sets; t k x and t k y are the translation parameters in x-axis and y-axis at time k, respectively; θ k is the rotation parameter at time k. For 3D point sets, the state is denoted as x ˜ k = [ t k x , t k y , t k z , θ k x , θ k y , θ k z ] T , where t k z is the translation parameter in z-axis at time k, θ k x , θ k y , θ k z are the rotation parameters in the x-axis, y-axis and z-axis at time k, respectively; f ( . ) is the measurement function; v k and w k are the process noise and measurement noise, respectively; v k and w k are assumed to be zero-mean Gaussian white noise.
In [66], an unscented particle filter (UPF) was used for rigid registration. The ICP algorithm was used to find correspondences and to compute the distance between data sets. This method is not sensitive to outliers. In [67], a particle filter was proposed for point set registration. An iterative-based local optimizer, which can be reinterpreted as a robust version of ICP, was formulated based on the correlation measure. In [68], a deformable registration framework, composed of simulated annealing with a particle filter, was proposed to point set registration. A variety of constraints on the registration are incorporated into this method. Furthermore, a novel method to regularize the deformation field was proposed to improve the registration performance. In [69], a map was generated by fusing inertial measurement unit (IMU), odometry, global positioning system (GPS) and LiDAR. Live laser data were aligned with the prior-map using a particle filter based point set registration method. In [70], an unscented Kalman filter (UKF) method was proposed to register two data sets in the presence of noise. However, the correspondences of these two point sets were assumed known. In [15,16], a local shape descriptor was proposed to obtain the correspondences of point sets. A rigid point set registration method based on cubature Kalman filter (CKF) was presented for localization in the intelligent vehicle. In [71], the authors considered that noise, outliers, false initialization, and other errors might exist simultaneously. A split covariance intersection filter (SCIF) was then proposed to point set registration under a filtering framework.

2.3. Probability-Based Methods

The coherent point drift (CPD) [25] is a popular method in field of probability-based point set registration. In the CPD method, a rigid and non-rigid point set registration is formulated as a maximum likelihood (ML) estimation problem using GMM method. One point set is represented by GMM centroids, and the another point set is fitted to those of the first point set by moving coherently:
p ( Y ) = ∏ j = 1 M ∑ i = 1 N π i N ( y j g ( x i ) , σ 2 I D )
where N ( . ) is the Gaussian distribution; g ( . ) is the rigid or non-rigid transformation; σ 2 is the equal isotropic covariances; I is the identity matrix; and π i is the mixing coefficient. Then, an expectation-maximization (EM) algorithm is applied to perform this ML optimization. Many algorithms were proposed to extend the CPD method [1,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92]. These algorithms can be summarized as follows:
(1)
Selecting a suitable non-rigid transformation function: In the CPD method, only one non-rigid transformation function is considered. Therefore, multiple kernel functions were used to represent non-rigid transformations in [72]. By automatically adjusting the kernel weights, this method can prune the ineffective kernels and evaluate the importance of each kernel. Considering the multi-layer motion between two sets of points, a robust point set registration using the GMM model was proposed in [73].
(2)
Choosing the distribution of point set: In [74], the Student’s-t distribution was used to replace the Gaussian distribution for tackling the outliers in the point set registration. Similar to the CPD method, one point set is treated as Student’s-t mixture model centroids, while another point set is fitted to those of the Student’s-t mixture model centroids by moving coherently.
(3)
Setting the membership probabilities: In the CPD method, equal membership probabilities were used. To improve the performance of point set registration, the shape context was proposed to assign the membership probabilities of the mixture model in [1].
(4)
Developing the local structure descriptors: In the CPD method, the GMM centroids were forced to move coherently to fit the data points by maximizing the likelihood, which only encodes the global structure of the two point sets. To preserve the local structure of point sets, the idea of local linear embedding (LLE) was proposed. The local neighbors in the point set could be preserved after the non-rigid transformed. Each point can be represented by a weighted linear of its neighbors. Then, an EM algorithm was derived for the ML optimization constrained with both CPD and LLE terms [75]. Similar to the LLE, the locally linear transforming (LLF) was developed for constructing the local structure [76]. In [1], the local features were used to assign the membership probabilities of the GMM. A non-rigid point set registration, which preserves both global and local structures, was developed. In [78], the shape context and LLF were proposed to the nonrigid point set registration. In [17], a non-rigid point set registration using spatially constrained Gaussian fields (SCGF) was developed. The shape context was also used for the membership probabilities initialization. A graph Laplacian regularized Gaussian fields was proposed to preserve the local structure of point sets. Furthermore, two local structure descriptors were embedded in the CPD framework in [79]. The first descriptor was LLE. The Laplacian coordinate was used in the second descriptor to keep the size of neighborhood structure. Therefore, the objective function of point set registration was composed of the global distance item, non-rigid transformation constraint item and two local structure constraints items.
(5)
Extraction the feature of point sets: The spatial location of point sets is a traditional feature for registration. In [86], the color information of point sets was used to extend the CPD algorithm. In [87], the correlation of color information and spatial location information was formulated. Then, a probabilistic point set registration framework with color information and spatial location information was given.
(6)
Performing algorithm: The disadvantage of the traditional CPD algorithm is that the CPD method has a high computation cost. Therefore, In [88], an accelerated CPD (ACPD) method was proposed to register a 3-D point cloud. In ACPD, a global squared iterative EM algorithm was developed to speed up the process of likelihood maximization. The dual-tree improved fast Gauss transform method was used to accelerate the process of Gaussian summation. In [92], the regression and clustering for performing point set registration in a Bayesian framework were presented. The coarse-to-fine variational inference algorithm was used to estimate the unknown parameters.

2.4. Discussion

As the distance-based methods possess acceptable performance and computation load, they are widely used in many fields, such as target tracking [93]. The filter-based methods have the capability to register the massive point set online. However, the correspondences of the point set should be computed in advance. From the literature, the probability-based methods with some local structures perform better than other methods, but the former have higher computation cost than the distance-based methods and the filter-based methods.

3. Groupwise Point Set Registration

Let M j = [ M j 1 , M j 2 . . . M j N j ] be the j-th point set. Let M = { M j } j = 1 M denote the union of multiple point sets, where M is the number of sets. One important issue is on the registration of these point sets. Traditionally, this problem is performed using pairwise registration repeatedly [2], such as sequentially strategy [94,95,96,97,98] and one-versus-all strategy [99,100,101]. In the sequentially pairwise registration strategy, the parameters are updated by a ICP method or a probabilistic method when additional point sets are available. The main drawback of sequentially pairwise registration strategy consists in the error propagation in the subsequent steps [2,3]. For the one-versus-all pairwise registration strategy, the reference point set should be chosen in advance. The other point sets are used to register with the reference point set.
Simultaneous registration of multiple point sets is another method which brings further improvement to the point set methods. They are called groupwise point set registrations. In [102], some correspondences between the point sets were assumed known in advance, and the transformation parameters were estimated. Furthermore, in [103], the same formulation as [102] was extended to perform unknown correspondences. The above literature also developed the simultaneous multiple point sets registration with a pairwise strategy. Some methods have been developed to register multiple point sets simultaneously without the resource of a pairwise strategy. It can be categorized as information theoretic-based methods and probability-based methods.
For information theoretic-based methods, the joint multiple point sets registration is performed according to some information theoretic measures. In [104], an information theoretic measure, which is named as cumulative distribution functions Jensen Shannon (CDF-JS) method, was proposed to register multiple point sets. As the CDF-JS method is symmetric and had no bias to any point sets, it can register the multiple point sets simultaneously. The cost function was defined as the CDF-JS divergence and was minimized by computing analytic gradients in a quasi-Newton scheme. However, this method has a high computation cost for the CDF-JS and has no closed-form solutions. In [105], another information theoretic measure, called cumulative distribution functions Havrda-Charvát (CDF-HC) method, was developed. The CDF-HC method uses the same idea as the CDF-JS method but with a different divergence for the cumulative distribution functions. In the CDF-HC method, the Havrda-Charvát divergence was proposed instead of Jensen Shannon divergence. Compared with CDF-JS method, the CDF-HC method is much simpler to implement and has lower computation cost [105]. Recently, a Rényi’s second order entropy method was proposed for groupwise point set registration in [106]. It is a closed-form solution to the cost function.
For probability-based methods, the multiple point sets are formulated as some probability functions and cast into a clustering problem. It can be classified as forward and backward approaches [107]. In the forward approach [108], the multiple point sets are assumed to be noisy observations of the mean point set. In the backward approach [2,3,109], the mean point set is assumed to be a noisy observation of multiple point sets. Both the forward and backward approaches consist of two steps:
  • the construction of the mean point set.
  • the estimation of the transformation between the multiple point sets and mean point set.
These two steps are iteratively computed to register the multiple point sets. In [108], the forward approach of groupwise point set registration method was proposed and it is shown schematically in Figure 5. It is assumed that the multiple point sets are noisy observations of mean point set:
p ( M j i ) = ∑ k = 1 K α k N ( M j i ϕ j ( Γ k ) , Ω k )
where Γ k and Ω k are the mean vector and covariance matrix, respectively; α k is the mixing coefficient; and ϕ j ( . ) is the transformation function for the forward approach. Γ k is assumed as the mean point set in the forward approach. In [108], the EM algorithm was proposed to estimate the mean point set and the parameters in the transformation function.
In [2,3], the backward approach of groupwise point set registration method was developed and it is shown schematically in Figure 6. It is assumed that the multiple point sets are transformed realizations of mean point set:
p ( M j i ) = ∑ k = 1 K β k N ( φ j ( M j i ) Υ k , Ξ k )
where Υ k and Ξ k are the mean vector and covariance matrix, respectively; β k is the mixing coefficient; and φ j ( . ) is the transformation function for the backward approach. The Υ k is assumed as the mean point set in the backward approach. The EM algorithm is also used to register the multiple point sets simultaneously. Table 1 summarizes some representative methods for point set registration.

4. Experiments

In this section, 10 representative point set registration algorithms are selected to conduct some experiments. These 10 representative methods are as follows: ICP (Available at http://www.cvlibs.net/software/libicp/) [110], TPS-RPM (Available at https://www.cise.ufl.edu/~anand/publications.html) [35], KC (Available at http://www.cs.cmu.edu/~ytsin/KCReg/) [36], CPD (Available at https://sites.google.com/site/myronenko/research/cpd) [25], CPD-GL (Available at https://sites.google.com/site/jiayima2013/) [1], SCGF (Available at https://sites.google.com/site/2013gwang/SCGF.zip) [17], CDF-HC (Available at https://www.cise.ufl.edu/~anand/publications.html) [105], Rényi’s second order entropy (Rényi’s) [106], Student’s t-mixture model (TMM) [111], and groupwise probability-based method (JRMPC) (Available at https://team.inria.fr/perception/research/jrmpc/) [2,3]. The ICP, TPS-RPM, KC, CPD, CPD-GL, and SCGF are pairwise point set registration methods. The CDF-HC, Rényi’s, TMM, and JRMPC are groupwise point set registration methods. The performance of these representative point set registration algorithms is validated on the toy data sets from [35]. The validation considers different levels of noise, to object deformation, rotation, and occlusion. To evaluate the performance of the rivals, the cost function of the optimization problem defined in (1), that is the Mean Squared Error Distance (MSED), is used. These representative point set registration algorithms were implemented compared in Matlab. The transformed function in the TPS-RPM, CPD, CPD-GL, and SCGF are chosen using a nonrigid transformation. The parameters in these representative algorithms are set as in the original papers. Each algorithm is carried out until it is converged or runs at least 50 iterations.
In the pairwise point set registration experiments, the fish and Chinese character datasets [35] are considered. The qualitative results of these pairwise point set registration algorithms are given in Figure 7. It is observed that most algorithms can register under deformation degradations. The distance metrics for correspondence matching of these pairwise point set registration algorithms under varying deformation in fish and Chinese dataset are shown in Figure 8. It is observed that the SCGF has better registration accuracy performance than other algorithms. The average runtime of these algorithms are given in Table 2, which illustrates that the CPD is computationally most efficient.
The 3D COPD data http://www.dir-lab.com/index.html is employed here. The “COPD I D _300_iBH_xyz” is chosen as the model point set, while “COPD I D _300_eBH_xyz” is considered as the scene point set. Thus, ten pairs of point sets are generated, where “ I D ” ∈ [ 1 , 10 ] . The example of the registration results of pairwise point set registration algorithms on “COPD1_300_iBH_xyz” vs. “COPD1_300_eBH_xyz” is depicted in Figure 9, which demonstrates that SCGF and CPD-GL can register the 3D COPD point set. Furthermore, the comparison results using registration error are illustrated in Figure 10. It can be observed that the CPD-GL has almost same registration accuracy performance with SCGF.
In brief, the SCGF algorithm have more accuracy, while it needs more computational effort. The CPD-GL algorithm has almost same registration accuracy performance with SCGF, but it has a lower computation load than SCGF algorithm. Therefore, the CPD-GL algorithm has the tradeoff between accuracy and computational complexity.
In the groupwise point set registration experiments, the fish and Chinese character datasets are also considered and there are four-point sets. To generate the multiple point set groups, parameters of deformation in a rigid transformation are chosen uniformly in the following range: [0.02, 0.08]. The qualitative results of the groupwise point set registration experiments are shown in Figure 11. The distance metrics for correspondence matching of these groupwise point set registration algorithms under varying deformation in fish and Chinese dataset are depicted in Figure 12. From the Figure 11 and Figure 12, it can be observed that JRMPC, TMM, and Rényi’s algorithms can register under deformation degradations. The average runtime of these algorithms are given in Table 3, which illustrates that the JRMPC is the computationally most efficient.
Then, multiple 3D COPD point set groups are generated. It has ten point set groups, where each group has four point sets. The four point sets in each group are generated, where deformation parameters in a rigid transformation are chosen uniformly in the following range: [0.02, 0.08] on “COPD I D _300_eBH_xyz”, where “ I D ” ∈ [ 1 , 10 ] , respectively. The example of the registration results of JRMPC and TMM algorithms on COPD data are depicted in Figure 13, which demonstrates that JRMPC and TMM algorithms can register this point set group. The statistics for the compared results are given in Figure 14, which unfolds that JRMPC algorithm has almost the same performance with the TMM algorithm.
Thus, from the results in the point set group experiment, the JRMPC and TMM algorithms present almost the same registration accuracy performance, but the JRMPC has lower computational load.

5. Conclusions

This paper presents a review of the state-of-the-art point set registration methods. From the pairwise point set registration to groupwise point set registration, the modeling methods are discussed with a summary of their pros and cons. In the pairwise point set registration, the point set registration methods can be classified as distance-based methods, filtering-based methods and probability-based methods. In the groupwise point set registration, the point set registration methods have been classified as information theoretic-based methods and probability-based methods. Some evaluation metrics to evaluate the performance of point set registration are given. Furthermore, several experiments with some representative point set registration algorithms are performed. From the numerical experiments, the CPD-GL pairwise registration [1] and the JRMPC groupwise registration algorithms [2,3] offer a tradeoff between accuracy and computational burden.
Although many methods have been proposed for point set registration, there are still many challenges necessary for further study:
(1)
Object localization for the purpose of autonomous vehicles and in health systems requires point set registration over massive and high-dimensional point sets. One direction for alleviating this problem relies on point or feature selection. Clustering algorithms can then be used to cope with such challenges. Sparse Bayesian learning methods are also capable of identifying the suitable features for point set registration.
(2)
There is a need for more benchmark examples and large scale datasets with ground truth for thorough performance evaluation of the developed approaches.
(3)
Point set registration is an essential step towards target tracking and pattern recognition. There is a scope of assessing its impact on the entire monitoring system of interest, with different levels of autonomy.

Author Contributions

Major framework for the review, H.Z. and Y.L.; software, B.G., and K.Z.; writing—original draft preparation, H.Z.; writing–review and editing, K.-V.Y. and L.M.; supervision, H.L.

Funding

This work is jointly supported by the National Key Science and Technology Program of China (Grant No. 2018ZX03001023), by the Scientific and Technological Research Program of Chongqing Municipal Education Commission (Grant No. KJ1704078), by the Research Funds of Chongqing Science and Technology Commission (Grant No. cstc2017jcyjAX0293), by the National Natural Science Foundation of China (Grant No. 61773082), by the Foundation of Chongqing (Grant No. CSTC2017JCYJBX0018 and No. CX2017044), by the Key Project of Crossing and Emerging Area of CQUPT (Grant No. A2018-02), by the Research Fund of young-backbone university teacher in Chongqing province, by Chongqing Overseas Scholars Innovation Program, by Wenfeng Talents of Chongqing University of Posts and Telecommunications, by Innovation Team Project of Chongqing Education Committee (Grant No.CXTDX201601019), by the Research Funds of Chongqing University of Posts and Telecommunications (Grant No. A2018-174), by the National Key Research and Development Program (Grant No. 2016YFB0100906).

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Ma, J.; Zhao, J.; Yuille, A.L. Non-Rigid Point Set Registration by Preserving Global and Local Structures. IEEE Trans. Image Process. 2016, 25, 53–64. [Google Scholar] [PubMed]
  2. Evangelidis, G.D.; Kounades-Bastian, D.; Horaud, R.; Psarakis, E.Z. A Generative Model for the Joint Registration of Multiple Point Sets. In Proceedings of the European Conference on Computer Vision, Zurich, Switzerland, 6–12 September 2014; pp. 109–122. [Google Scholar]
  3. Evangelidis, G.D.; Horaud, R. Joint Alignment of Multiple Point Sets with Batch and Incremental Expectation-Maximization. IEEE Trans. Pattern Anal. Mach. Intell. 2018, 40, 1397–1410. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  4. He, Y.; Liang, B.; Yang, J.; Li, S.; He, J. An Iterative Closest Points Algorithm for Registration of 3D Laser Scanner Point Clouds with Geometric Features. Sensors 2017, 17, 1862. [Google Scholar] [CrossRef]
  5. Weng, R.; Lu, J.; Tan, Y.P. Robust Point Set Matching for Partial Face Recognition. IEEE Trans. Image Process. 2016, 25, 1163–1176. [Google Scholar] [CrossRef] [PubMed]
  6. Cheng, L.; Chen, S.; Liu, X.; Xu, H.; Wu, Y.; Li, M.; Chen, Y. Registration of Laser Scanning Point Clouds: A Review. Sensors 2018, 18, 1641. [Google Scholar] [CrossRef] [PubMed]
  7. Zhu, H.; Wang, M.; Yuen, K.V.; Leung, H. Track-to-Track Association by Coherent Point Drift. IEEE Signal Process. Lett. 2017, 24, 643–647. [Google Scholar] [CrossRef]
  8. Zhang, X.; Wang, J.; Fang, Y.; Yuan, J. Multilevel Humanlike Motion Planning for Mobile Robots in Complex Indoor Environments. IEEE Trans. Autom. Sci. Eng. 2018, 1–15. [Google Scholar] [CrossRef]
  9. Li, Y.; Tang, C.; Peeta, S.; Wang, Y. Nonlinear Consensus-Based Connected Vehicle Platoon Control Incorporating Car-Following Interactions and Heterogeneous Time Delays. IEEE Trans. Intell. Transp. Syst. 2018, 1–11. [Google Scholar] [CrossRef]
  10. Zhang, X.; Wang, R.; Fang, Y.; Li, B.; Ma, B. Acceleration-Level Pseudo-Dynamic Visual Servoing of Mobile Robots With Backstepping and Dynamic Surface Control. IEEE Trans. Syst. Man Cybern. Syst. 2018, 1–11. [Google Scholar] [CrossRef]
  11. Zhu, H.; Yuen, K.V.; Mihaylova, L.; Leung, H. Overview of Environment Perception for Intelligent Vehicles. IEEE Trans. Intell. Transp. Syst. 2017, 18, 2584–2601. [Google Scholar] [CrossRef] [Green Version]
  12. Zhu, H.; Li, Y.; Yu, J.; Leung, H.; Li, Y. Ensemble Registration of Multisensor Images by a Variational Bayesian Approach. IEEE Sens. J. 2014, 14, 2698–2705. [Google Scholar] [CrossRef]
  13. Tumer, N.; Kok, A.C.; Vos, F.M.; Streekstra, G.J.; Askeland, C.; Tuijthof, G.J.M.; Zadpoor, A.A. Three-Dimensional Registration of Freehand-Tracked Ultrasound to CT Images of the Talocrural Joint. Sensors 2018, 18, 2375. [Google Scholar] [CrossRef] [PubMed]
  14. Zhu, X.; Ding, M.; Huang, T.; Jin, X.; Zhang, X. PCANet-Based Structural Representation for Nonrigid Multimodal Medical Image Registration. Sensors 2018, 18, 1477. [Google Scholar] [CrossRef] [PubMed]
  15. Li, L.; Yang, M.; Wang, C.; Wang, B. Cubature Kalman Filter based point set registration for SLAM. In Proceedings of the 2016 IEEE 19th International Conference on Intelligent Transportation Systems, Rio de Janeiro, Brazil, 1–4 Novmber 2016; pp. 847–852. [Google Scholar]
  16. Li, L.; Yang, M.; Wang, C.; Wang, B. Rigid Point Set Registration Based on Cubature Kalman Filter and Its Application in Intelligent Vehicles. IEEE Trans. Intell. Transp. Syst. 2018, 19, 1754–1765. [Google Scholar] [CrossRef]
  17. Wang, G.; Zhou, Q.; Chen, Y. Robust Non-Rigid Point Set Registration Using Spatially Constrained Gaussian Fields. IEEE Trans. Image Process. 2017, 26, 1759–1769. [Google Scholar] [CrossRef]
  18. Lowe, D.G. Distinctive Image Features from Scale-Invariant Keypoints. Int. J. Comput. Vis. 2004, 60, 91–110. [Google Scholar] [CrossRef] [Green Version]
  19. Zheng, Z.; Li, Y.; Jun, W. LiDAR point cloud registration based on improved ICP method and SIFT feature. In Proceedings of the 2015 IEEE International Conference on Progress in Informatics and Computing, Nanjing, China, 18–20 December 2015; pp. 588–592. [Google Scholar]
  20. Wu, G.; Kim, M.J.; Wang, Q.; Munsell, B.; Shen, D. Scalable High Performance Image Registration Framework by Unsupervised Deep Feature Representations Learning. IEEE Trans. Biomed. Eng. 2016, 63, 1505–1516. [Google Scholar] [CrossRef]
  21. Ye, F.; Su, Y.; Xiao, H.; Zhao, X.; Min, W. Remote Sensing Image Registration Using Convolutional Neural Network Features. IEEE Geosci. Remote Sens. Lett. 2018, 15, 232–236. [Google Scholar] [CrossRef]
  22. Zhou, F.; la Torre, F.D. Factorized Graph Matching. IEEE Trans. Pattern Anal. Mach. Intell. 2016, 38, 1774–1789. [Google Scholar] [CrossRef]
  23. Besl, P.J.; McKay, N.D. A method for registration of 3-D shapes. IEEE Trans. Pattern Anal. Mach. Intell. 1992, 14, 239–256. [Google Scholar] [CrossRef]
  24. Zhang, Z. Iterative point matching for registration of free-form curves and surfaces. Int. J. Comput. Vis. 1994, 13, 119–152. [Google Scholar] [CrossRef] [Green Version]
  25. Myronenko, A.; Song, X. Point Set Registration: Coherent Point Drift. IEEE Trans. Pattern Anal. Mach. Intell. 2010, 32, 2262–2275. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  26. Conte, D.; Foggia, P.; Sansone, C.; Vento, M. Thirty years of graph matching in pattern recognition. Int. J. Pattern Recognit. Artif. Intell. 2004, 18, 265–298. [Google Scholar] [CrossRef]
  27. Zheng, Y.; Doermann, D. Robust point matching for nonrigid shapes by preserving local neighborhood structures. IEEE Trans. Pattern Anal. Mach. Intell. 2006, 28, 643–649. [Google Scholar] [CrossRef] [PubMed]
  28. Yang, J. The thin plate spline robust point matching (TPS-RPM) algorithm: A revisit. Pattern Recognit. Lett. 2011, 32, 910–918. [Google Scholar] [CrossRef]
  29. Tam, G.K.L.; Cheng, Z.Q.; Lai, Y.K.; Langbein, F.C.; Liu, Y.; Marshall, D.; Martin, R.R.; Sun, X.F.; Rosin, P.L. Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid. IEEE Trans. Vis. Comput. Graph. 2013, 19, 1199–1217. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  30. Maiseli, B.; Gu, Y.; Gao, H. Recent developments and trends in point set registration methods. J. Visual Commun. Image Represent. 2017, 46, 95–106. [Google Scholar] [CrossRef]
  31. Rusinkiewicz, S.; Levoy, M. Efficient variants of the ICP algorithm. In Proceedings of the Third International Conference on 3-D Digital Imaging and Modeling, Quebec City, QC, Canada, 28 May–1 June 2001; pp. 145–152. [Google Scholar]
  32. Pottmann, H.; Huang, Q.X.; Yang, Y.L.; Hu, S.M. Geometry and Convergence Analysis of Algorithms for Registration of 3D Shapes. Int. J. Comput. Vis. 2006, 67, 277–296. [Google Scholar] [CrossRef]
  33. Liu, Y. A mean field annealing approach to accurate free form shape matching. Pattern Recognit. 2007, 40, 2418–2436. [Google Scholar] [CrossRef]
  34. Gold, S.; Rangarajan, A.; Lu, C.P.; Pappu, S.; Mjolsness, E. New algorithms for 2D and 3D point matching: Pose estimation and correspondence. Pattern Recognit. 1998, 31, 1019–1031. [Google Scholar] [CrossRef]
  35. Chui, H.; Rangarajan, A. A new point matching algorithm for non-rigid registration. Comput. Vis. Image Underst. 2003, 89, 114–141. [Google Scholar] [CrossRef] [Green Version]
  36. Tsin, Y.; Kanade, T. A Correlation-Based Approach to Robust Point Set Registration. In Proceedings of the European Conference on Computer Vision, Prague, Czech Republic, 11–14 May 2004; pp. 558–569. [Google Scholar]
  37. Singh, M.; Arora, H.; Ahuja, N. Robust Registration and Tracking Using Kernel Density Correlation. In Proceedings of the 2004 Conference on Computer Vision and Pattern Recognition Workshop, Washington, DC, USA, 27 June–2 July 2004; p. 174. [Google Scholar]
  38. Jian, B.; Vemuri, B.C. Robust Point Set Registration Using Gaussian Mixture Models. IEEE Trans. Pattern Anal. Mach. Intell. 2011, 33, 1633–1645. [Google Scholar] [CrossRef] [PubMed]
  39. Campbell, D.; Petersson, L. An Adaptive Data Representation for Robust Point-Set Registration and Merging. In Proceedings of the 2015 IEEE International Conference on Computer Vision, Santiago, Chile, 7–13 December 2015; pp. 4292–4300. [Google Scholar]
  40. Sousa, S.D.; Kropatsch, W.G. Graph-based point drift: Graph centrality on the registration of point-sets. Pattern Recognit. 2015, 48, 368–379. [Google Scholar] [CrossRef]
  41. Park, H.M.; Yoon, K.J. Multi-Attributed Graph Matching With Multi-Layer Graph Structure and Multi-Layer Random Walks. IEEE Trans. Image Process. 2018, 27, 2314–2325. [Google Scholar] [CrossRef] [PubMed]
  42. Foggia, P.; Percannella, G.; Vento, M. GRAPH MATCHING AND LEARNING IN PATTERN RECOGNITION IN THE LAST 10 YEARS. Int. J. Pattern Recognit. Artif. Intell. 2014, 28, 1428–1481. [Google Scholar] [CrossRef]
  43. Emmert-Streib, F.; Dehmer, M.; Shi, Y. Fifty years of graph matching, network alignment and network comparison. Inf. Sci. 2016, 346, 180–197. [Google Scholar] [CrossRef]
  44. Loiola, E.M.; de Abreu, N.M.M.; Boaventura-Netto, P.O.; Hahn, P.; Querido, T. A survey for the quadratic assignment problem. Eur. J. Oper. Res. 2007, 176, 657–690. [Google Scholar] [CrossRef]
  45. Cho, M.; Alahari, K.; Ponce, J. Learning Graphs to Match. In Proceedings of the 2013 IEEE International Conference on Computer Vision, Sydney, NSW, Australia, 1–8 December 2013; pp. 25–32. [Google Scholar]
  46. Leordeanu, M.; Hebert, M. A spectral technique for correspondence problems using pairwise constraints. In Proceedings of the Tenth IEEE International Conference on Computer Vision, Beijing, China, 17–21 October 2005; Volume 2, pp. 1482–1489. [Google Scholar]
  47. Cour, T.; Srinivasan, P.; Shi, J. Balanced graph matching. In Proceedings of the Conference on Advances in Neural Information Processing Systems, Vancouver, BC, Canada, 4–7 Decmeber 2006; pp. 313–320. [Google Scholar]
  48. Torr, P.H.S. Solving Markov Random Fields Using Semi-Definite Programming. In Proceedings of the International Workshop on Artificial Intelligence & Statistics, Key West, FL, USA, 3–6 January 2003; pp. 1–8. [Google Scholar]
  49. Schellewald, C.; Schnorr, C. Probabilistic Subgraph Matching Based on Convex Relaxation. In Proceedings of the 5th International Workshop Energy Minimization Methods in Computer Vision and Pattern Recognition, St. Augustine, FL, USA, 9–11 November 2005; pp. 171–186. [Google Scholar]
  50. Almohamad, H.A.; Duffuaa, S.O. A linear programming approach for the weighted graph matching problem. IEEE Trans. Pattern Anal. Mach. Intell. 1993, 15, 522–525. [Google Scholar] [CrossRef] [Green Version]
  51. Leordeanu, M.; Hebert, M.; Sukthankar, R. An integer projected fixed point method for graph matching and MAP inference. In Proceedings of the International Conference on Neural Information Processing Systems, Vancouver, BC, Canada, 7–10 December 2009; pp. 1114–1122. [Google Scholar]
  52. van Wyk, B.; van Wyk, M. Kronecker product graph matching. Pattern Recognit. 2003, 36, 2019–2030. [Google Scholar] [CrossRef]
  53. Egozi, A.; Keller, Y.; Guterman, H. A Probabilistic Approach to Spectral Graph Matching. IEEE Trans. Pattern Anal. Mach. Intell. 2013, 35, 18–27. [Google Scholar] [CrossRef]
  54. Liu, Z.Y.; Qiao, H.; Jia, L.H.; Xu, L. A graph matching algorithm based on concavely regularized convex relaxation. Neurocomputing 2014, 134, 140–148. [Google Scholar] [CrossRef] [Green Version]
  55. Zass, R.; Shashua, A. Probabilistic graph and hypergraph matching. In Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition, Anchorage, AK, USA, 23–28 June 2008; pp. 1–8. [Google Scholar]
  56. Duchenne, O.; Bach, F.; Kweon, I.S.; Ponce, J. A Tensor-Based Algorithm for High-Order Graph Matching. IEEE Trans. Pattern Anal. Mach. Intell. 2011, 33, 2383–2395. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  57. Lee, J.; Cho, M.; Lee, K.M. Hyper-graph matching via reweighted random walks. In Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition, Colorado Springs, CO, USA, 20–25 June 2011; pp. 1633–1640. [Google Scholar]
  58. Ngoc, Q.N.; Gautier, A.; Hein, M. A flexible tensor block coordinate ascent scheme for hypergraph matching. In Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition, Boston, MA, USA, 7–12 June 2015; pp. 5270–5278. [Google Scholar]
  59. Yan, J.; Cho, M.; Zha, H.; Yang, X.; Chu, S.M. Multi-Graph Matching via Affinity Optimization with Graduated Consistency Regularization. IEEE Trans. Pattern Anal. Mach. Intell. 2016, 38, 1228–1242. [Google Scholar] [CrossRef] [PubMed]
  60. Dutta, A.; Llados, J.; Bunke, H.; Pal, U. Product Graph-based Higher Order Contextual Similarities for Inexact Subgraph Matching. Pattern Recognit. 2017, 76, 596–611. [Google Scholar] [CrossRef]
  61. Jiang, B.; Tang, J.; Cao, X.; Luo, B. Lagrangian relaxation graph matching. Pattern Recognit. 2017, 61, 255–265. [Google Scholar] [CrossRef]
  62. Wang, T.; Ling, H.; Lang, C.; Feng, S. Symmetry-aware graph matching. Pattern Recognit. 2016, 60, 657–668. [Google Scholar] [CrossRef] [Green Version]
  63. Yuan, Y.; Wang, G.; Chen, L.; Ning, B. Efficient pattern matching on big uncertain graphs. Inf. Sci. 2016, 339, 369–394. [Google Scholar] [CrossRef]
  64. Li, T.; Dong, H.; Shi, Y.; Dehmer, M. A comparative analysis of new graph distance measures and graph edit distance. Inf. Sci. 2017, 403–404, 15–21. [Google Scholar] [CrossRef]
  65. Zhang, R.; Wang, W. Second- and High-order Graph Matching for Correspondence Problems. IEEE Trans. Circuits Syst. Video Technol. 2018, 28, 2978–2992. [Google Scholar] [CrossRef]
  66. Ma, B.; Ellis, R.E. Surface-Based Registration with a Particle Filter. In Proceedings of the 2004 International Conference Medical Image Computing and Computer-Assisted Intervention, Saint-Malo, France, 26–29 September 2004; pp. 266–273. [Google Scholar]
  67. Sandhu, R.; Dambreville, S.; Tannenbaum, A. Point Set Registration via Particle Filtering and Stochastic Dynamics. IEEE Trans. Pattern Anal. Mach. Intell. 2010, 32, 1459–1473. [Google Scholar] [CrossRef] [Green Version]
  68. Kolesov, I.; Lee, J.; Sharp, G.; Vela, P.; Tannenbaum, A. A Stochastic Approach to Diffeomorphic Point Set Registration with Landmark Constraints. IEEE Trans. Pattern Anal. Mach. Intell. 2016, 38, 238–251. [Google Scholar] [CrossRef] [PubMed]
  69. Li, L.; Yang, M.; Guo, L.; Wang, C.; Wang, B. Hierarchical Neighborhood Based Precise Localization for Intelligent Vehicles in Urban Environments. IEEE Trans. Intell. Veh. 2016, 1, 220–229. [Google Scholar] [CrossRef]
  70. Moghari, M.H.; Abolmaesumi, P. Point-Based Rigid-Body Registration Using an Unscented Kalman Filter. IEEE Trans. Med. Imaging 2007, 26, 1708–1728. [Google Scholar] [CrossRef] [PubMed]
  71. Li, L.; Yang, M.; Wang, C.; Wang, B. Cubature Split Covariance Intersection Filter-based Point Set Registration. IEEE Trans. Image Process. 2018, 27, 3942–3953. [Google Scholar] [CrossRef] [PubMed]
  72. Nguyen, T.M.; Wu, Q.M.J. Multiple Kernel Point Set Registration. IEEE Trans. Med. Imaging 2016, 35, 1381–1394. [Google Scholar] [CrossRef]
  73. Ma, J.; Chen, J.; Ming, D.; Tian, J. A mixture model for robust point matching under multi-layer motion. PLoS ONE 2014, 9, e92282. [Google Scholar] [CrossRef] [PubMed]
  74. Zhou, Z.; Zheng, J.; Dai, Y.; Zhou, Z.; Chen, S. Robust Non-Rigid Point Set Registration Using Student’s-t Mixture Model. PLoS ONE 2014, 9, e91381. [Google Scholar] [CrossRef] [PubMed]
  75. Ge, S.; Fan, G.; Ding, M. Non-rigid Point Set Registration with Global-Local Topology Preservation. In Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition Workshops, Columbus, OH, USA, 23–28 June 2014; pp. 245–251. [Google Scholar]
  76. Ma, J.; Zhou, H.; Zhao, J.; Gao, Y.; Jiang, J.; Tian, J. Robust Feature Matching for Remote Sensing Image Registration via Locally Linear Transforming. IEEE Trans. Geosci. Remote Sens. 2015, 53, 6469–6481. [Google Scholar] [CrossRef]
  77. Fu, M.; Zhou, W. Non-rigid point set registration via mixture of asymmetric Gaussians with integrated local structures. In Proceedings of the 2016 IEEE International Conference on Robotics and Biomimetics, Qingdao, China, 3–7 December 2016; pp. 999–1004. [Google Scholar]
  78. Bai, L.; Yang, X.; Gao, H. Nonrigid Point Set Registration by Preserving Local Connectivity. IEEE Trans. Cybern. 2018, 48, 826–835. [Google Scholar] [CrossRef]
  79. Ge, S.; Fan, G. Non-rigid articulated point set registration with Local Structure Preservation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, Boston, MA, USA, 7–12 June 2015; pp. 126–133. [Google Scholar]
  80. Ma, J.; Zhao, J.; Ma, Y.; Tian, J. Non-rigid visible and infrared face registration via regularized Gaussian fields criterion. Pattern Recognit. 2015, 48, 772–784. [Google Scholar] [CrossRef]
  81. Ma, J.; Jiang, J.; Liu, C.; Li, Y. Feature Guided Gaussian Mixture Model with Semi-Supervised EM and Local Geometric Constraint for Retinal Image Registration. Inf. Sci. 2017, 417, 128–142. [Google Scholar] [CrossRef]
  82. Ma, J.; Zhao, J.; Jiang, J.; Zhou, H. Non-Rigid Point Set Registration with Robust Transformation Estimation Under Manifold Regularization. In Proceedings of the AAAI Conference on Artificial Intelligence, San Francisco, CA, USA, 4–9 February 2017; pp. 4218–4224. [Google Scholar]
  83. Ma, J.; Jiang, J.; Zhou, H.; Zhao, J.; Guo, X. Guided Locality Preserving Feature Matching for Remote Sensing Image Registration. IEEE Trans. Geosci. Remote Sens. 2018, 56, 4435–4447. [Google Scholar] [CrossRef]
  84. Lei, H.; Jiang, G.; Quan, L. Fast Descriptors and Correspondence Propagation for Robust Global Point Cloud Registration. IEEE Trans. Image Process. 2017, 26, 3614–3623. [Google Scholar] [CrossRef] [PubMed]
  85. Tao, W.; Sun, K. Asymmetrical Gauss Mixture Models for Point Sets Matching. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Columbus, OH, USA, 23–28 June 2014; pp. 1598–1605. [Google Scholar]
  86. Saval-Calvo, M.; Azorin-Lopez, J.; Fuster-Guillo, A.; Villena-Martinez, V.; Fisher, R.B. 3D non-rigid registration using color: Color Coherent Point Drift. Comput. Vis. Image Underst. 2018, 169, 119–135. [Google Scholar] [CrossRef] [Green Version]
  87. Danelljan, M.; Meneghetti, G.; Khan, F.S.; Felsberg, M. A Probabilistic Framework for Color-Based Point Set Registration. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Las Vegas, NV, USA, 27–30 June 2016; pp. 1818–1826. [Google Scholar]
  88. Lu, M.; Zhao, J.; Guo, Y.; Ma, Y. Accelerated Coherent Point Drift for Automatic Three-Dimensional Point Cloud Registration. IEEE Geosci. Remote Sens. Lett. 2016, 13, 162–166. [Google Scholar] [CrossRef]
  89. Zhang, S.; Yang, K.; Yang, Y.; Luo, Y.; Wei, Z. Non-rigid point set registration using dual-feature finite mixture model and global-local structural preservation. Pattern Recognit. 2018, 80, 183–195. [Google Scholar] [CrossRef]
  90. Gang, W.; Chen, Y. Fuzzy Correspondences Guided Gaussian Mixture Model for Point Set Registration. Knowl. Based Syst. 2017, 136, 200–209. [Google Scholar]
  91. Yu, D.; Yang, F.; Yang, C.; Leng, C.; Cao, J.; Wang, Y.; Tian, J. Fast Rotation-Free Feature-Based Image Registration Using Improved N-SIFT and GMM-Based Parallel Optimization. IEEE Trans. Biomed. Eng. 2016, 63, 1653–1664. [Google Scholar] [CrossRef]
  92. Qu, H.B.; Wang, J.Q.; Li, B.; Yu, M. Probabilistic Model for Robust Affine and Non-Rigid Point Set Matching. IEEE Trans. Pattern Anal. Mach. Intell. 2017, 39, 371–384. [Google Scholar] [CrossRef]
  93. Kim, D.; Kim, D. A Fast ICP Algorithm for 3-D Human Body Motion Tracking. IEEE Signal Process. Lett. 2010, 17, 402–405. [Google Scholar]
  94. Blais, G.; Levine, M.D. Registering multiview range data to create 3D computer objects. IEEE Trans. Pattern Anal. Mach. Intel. 1995, 17, 820–824. [Google Scholar] [CrossRef]
  95. Chen, Y.; Medioni, G. Object modelling by registration of multiple range images. Image Vis. Comput. 1992, 10, 145–155. [Google Scholar] [CrossRef]
  96. Masuda, T.; Yokoya, N. A robust method for registration and segmentation of multiple range images. In Proceedings of the IEEE 2nd CAD-Based Vision Workshop, Champion, PA, USA, 8–11 February 1994; pp. 106–113. [Google Scholar]
  97. Izadi, S.; Kim, D.; Hilliges, O.; Molyneaux, D.; Newcombe, R.; Kohli, P.; Shotton, J.; Hodges, S.; Freeman, D.; Davison, A. KinectFusion: Real-time 3D reconstruction and interaction using a moving depth camera. In Proceedings of the ACM Symposium on User Interface Software and Technology, Santa Barbara, CA, USA, 16–19 October 2011; pp. 559–568. [Google Scholar]
  98. Newcombe, R.A.; Izadi, S.; Hilliges, O.; Molyneaux, D.; Kim, D.; Davison, A.J.; Kohi, P.; Shotton, J.; Hodges, S.; Fitzgibbon, A. KinectFusion: Real-time dense surface mapping and tracking. In Proceedings of the 10th IEEE International Symposium on Mixed and Augmented Reality, Basel, Switzerland, 26–29 October 2011; pp. 127–136. [Google Scholar]
  99. Bergevin, R.; Soucy, M.; Gagnon, H.; Laurendeau, D. Towards a general multi-view registration technique. IEEE Trans. Pattern Anal. Mach. Intell. 1996, 18, 540–547. [Google Scholar] [CrossRef]
  100. Castellani, U.; Fusiello, A.; Murino, V. Registration of Multiple Acoustic Range Views for Underwater Scene Reconstruction. Comput. Vis. Image Underst. 2002, 87, 78–89. [Google Scholar] [CrossRef]
  101. Huber, D.F.; Hebert, M. Fully automatic registration of multiple 3D data sets. Image Vis. Comput. 2003, 21, 637–650. [Google Scholar] [CrossRef] [Green Version]
  102. Williams, J.; Bennamoun, M. Simultaneous Registration of Multiple Corresponding Point Sets. Comput.Vis. Image Underst. 2001, 81, 117–142. [Google Scholar] [CrossRef]
  103. Mateo, X.; Orriols, X.; Binefa, X. Bayesian perspective for the registration of multiple 3D views. Comput. Vis. Image Underst. 2014, 118, 84–96. [Google Scholar] [CrossRef]
  104. Wang, F.; Vemuri, B.C.; Rangarajan, A. Groupwise point pattern registration using a novel CDF-based Jensen-Shannon Divergence. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, New York, NY, USA, 17–22 June 2006; pp. 1283–1288. [Google Scholar]
  105. Chen, T.; Vemuri, B.C.; Rangarajan, A.; Eisenschenk, S.J. Group-wise Point-set registration using a novel CDF-based Havrda-Charvat Divergence. Int. J. Comput. Vis. 2010, 86, 111–124. [Google Scholar] [CrossRef]
  106. Giraldo, L.G.S.; Hasanbelliu, E.; Rao, M.; Principe, J.C. Group-Wise Point-Set Registration Based on Renyi’s Second Order Entropy. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Honolulu, HI, USA, 21–26 July 2017; pp. 2454–2462. [Google Scholar]
  107. Durrleman, S.; Pennec, X.; Trouve, A.; Ayache, N. Statistical models of sets of curves and surfaces based on currents. Med. Image Anal. 2009, 13, 793–808. [Google Scholar] [CrossRef] [Green Version]
  108. Rasoulian, A.; Rohling, R.; Abolmaesumi, P. Group-Wise Registration of Point Sets for Statistical Shape Models. IEEE Trans. Med. Imaging 2012, 31, 2025–2034. [Google Scholar] [CrossRef]
  109. Chui, H.; Rangarajan, A.; Zhang, J.; Leonard, C.M. Unsupervised learning of an Atlas from unlabeled point-sets. IEEE Trans. Pattern Anal. Mach. Intell. 2004, 26, 160–172. [Google Scholar] [CrossRef] [PubMed]
  110. Geiger, A.; Lenz, P.; Urtasun, R. Are we ready for Autonomous Driving? The KITTI Vision Benchmark Suite. In Proceedings of the Conference on Computer Vision and Pattern Recognition, Providence, RI, USA, 16–21 June 2012; pp. 3354–3361. [Google Scholar]
  111. Ravikumar, N.; Gooya, A.; Cimen, S.; Frangi, A.F.; Taylor, Z.A. Group-wise similarity registration of point sets using Student’s t-mixture model for statistical shape models. Med. Image Anal. 2018, 44, 156–176. [Google Scholar] [CrossRef] [PubMed]
Sensors 19 01191 g001 550
Figure 1. Some challenges in the point set registration [22].
Figure 1. Some challenges in the point set registration [22].
Sensors 19 01191 g001
Sensors 19 01191 g002 550
Figure 2. Taxonomy of point set registration methods.
Figure 2. Taxonomy of point set registration methods.
Sensors 19 01191 g002
Sensors 19 01191 g003 550
Figure 3. Pairwise point set registration problem: find the correspondences and the transformation of two point sets.
Figure 3. Pairwise point set registration problem: find the correspondences and the transformation of two point sets.
Sensors 19 01191 g003
Sensors 19 01191 g004 550
Figure 4. An example of GM problem.
Figure 4. An example of GM problem.
Sensors 19 01191 g004
Sensors 19 01191 g005 550
Figure 5. The forward approach of groupwise point set registration method in [108].
Figure 5. The forward approach of groupwise point set registration method in [108].
Sensors 19 01191 g005
Sensors 19 01191 g006 550
Figure 6. The backward approach of groupwise point set registration method in [2].
Figure 6. The backward approach of groupwise point set registration method in [2].
Sensors 19 01191 g006
Sensors 19 01191 g007 550
Figure 7. Registration results obtained from the application of pair-wise rivals on the Chinese characters set and fish shapes for different level of degradation. Data with different levels of deformation (first row) and the corresponding obtained results by KC (second row), ICP (third row), TPS-RPM (fourth row), CPD (fifth row), CPD-GL (sixth row), and SCGF (seventh row).
Figure 7. Registration results obtained from the application of pair-wise rivals on the Chinese characters set and fish shapes for different level of degradation. Data with different levels of deformation (first row) and the corresponding obtained results by KC (second row), ICP (third row), TPS-RPM (fourth row), CPD (fifth row), CPD-GL (sixth row), and SCGF (seventh row).
Sensors 19 01191 g007
Sensors 19 01191 g008 550
Figure 8. MSED, in log-scale, achieved from the application of the under-comparison pair-wise registration algorithms on the Chinese characters set and fish shapes for different levels of degradation.
Figure 8. MSED, in log-scale, achieved from the application of the under-comparison pair-wise registration algorithms on the Chinese characters set and fish shapes for different levels of degradation.
Sensors 19 01191 g008
Sensors 19 01191 g009 550
Figure 9. Registration results obtained from the application of pair-wise rivals on a specific example generated from 3D COPD data. Initial unregistered point sets (first column) and the results of CPD (second column), CPD-GL (third column), and SCGF (fourth column).
Figure 9. Registration results obtained from the application of pair-wise rivals on a specific example generated from 3D COPD data. Initial unregistered point sets (first column) and the results of CPD (second column), CPD-GL (third column), and SCGF (fourth column).
Sensors 19 01191 g009
Sensors 19 01191 g010 550
Figure 10. MSED achieved from the application of the under-comparison pair-wise registration algorithms on multiple point set groups generated by 3D COPD data (please see text for the details).
Figure 10. MSED achieved from the application of the under-comparison pair-wise registration algorithms on multiple point set groups generated by 3D COPD data (please see text for the details).
Sensors 19 01191 g010
Sensors 19 01191 g011 550
Figure 11. Registration results obtained from the application of group-wise rivals on the Chinese characters set and fish shapes for different level of degradation. Data with different levels of deformation (first row) and the corresponding obtained results by CDF-HC (second row), JRMPC (third row), TMM (fourth row), and Rényi’s (fifth row).
Figure 11. Registration results obtained from the application of group-wise rivals on the Chinese characters set and fish shapes for different level of degradation. Data with different levels of deformation (first row) and the corresponding obtained results by CDF-HC (second row), JRMPC (third row), TMM (fourth row), and Rényi’s (fifth row).
Sensors 19 01191 g011
Sensors 19 01191 g012 550
Figure 12. MSED, in log-scale, achieved from the application of the under-comparison group-wise registration algorithms on the Chinese characters set and fish shapes for different levels of degradation.
Figure 12. MSED, in log-scale, achieved from the application of the under-comparison group-wise registration algorithms on the Chinese characters set and fish shapes for different levels of degradation.
Sensors 19 01191 g012
Sensors 19 01191 g013 550
Figure 13. Registration results obtained from the application of group-wise rivals on a specific example generated from 3D COPD data. Initial unregistered point sets (first column) and the results of JRMPC (second column) and TMM (third column).
Figure 13. Registration results obtained from the application of group-wise rivals on a specific example generated from 3D COPD data. Initial unregistered point sets (first column) and the results of JRMPC (second column) and TMM (third column).
Sensors 19 01191 g013
Sensors 19 01191 g014 550
Figure 14. MSED achieved from the application of the under-comparison group-wise registration algorithms on multiple point set groups generated by 3D COPD data (please see text for the details).
Figure 14. MSED achieved from the application of the under-comparison group-wise registration algorithms on multiple point set groups generated by 3D COPD data (please see text for the details).
Sensors 19 01191 g014
Table
Table 1. The representative methods for point set registration.
Table 1. The representative methods for point set registration.
Research StudyPairwise/GroupwiseMethodRigid/Non-RigidParametric/Non-Parametric ModelCharacteristics
Besl and McKay [23]PairwiseDistance-based methodRigidParametric Model(1) Sensitive to the initialization
(2) Trapping into local minima
Gold et al. [34]PairwiseDistance-based methodRigidParametric Model(1) Combining deterministic annealing and softassign optimization
(2) Restricting to perform the rigid-body transformation
Chui et al. [35]PairwiseDistance-based methodNon-rigidParametric ModelDifficult to extend to perform higher dimension
Tsin et al. [36]PairwiseDistance-based methodRigid and Non-rigidParametric ModelMaximizing the KC of point sets
Jian et al. [38]PairwiseDistance-based methodRigid and Non-rigidParametric ModelMinimizing the Euclidean distance of two GMMs
Leordeanu et al. [46]PairwiseDistance-based methodRigid and Non-rigidNon-Parametric ModelConvexifying the QAP problem by spectral relaxation method
Cour et al. [47]PairwiseDistance-based methodRigid and Non-rigidNon-Parametric ModelConvexifying the QAP problem by semidefinite-programming relaxation
Almohamad et al. [50]PairwiseDistance-based methodRigid and Non-rigidNon-Parametric ModelConvexifying the QAP problem by doubly stochastic relaxation
Zhou et al. [22]PairwiseDistance-based methodRigid and Non-rigidNon-Parametric ModelFactorizing the large pairwise affinity matrix into some smaller matrices
Sandhu et al. [67]PairwiseFilter-based methodRigidNon-Parametric ModelUsing a particle filter to register the point sets
Li et al. [16]PairwiseFilter-based methodRigidNon-Parametric Model(1) Using a cubature Kalman filter to register the point sets
(2) The correspondence should be computed in advance
Myronenko et al. [25]PairwiseProbability-based methodRigid and Non-rigidParametric Model(1) Using a GMM model to formulate the distribution of the point sets
(2) Maximizing the likelihood of GMM
Ma et al. [76]PairwiseProbability-based methodRigid and Non-rigidParametric ModelDeveloping a locally linear transforming for local structure constrict
Wang et al. [104]GroupwiseInformation theoretic measureRigid and Non-rigidParametric ModelProposing a CDF-JS divergence as the cost function
Chen et al. [105]GroupwiseInformation theoretic measureRigid and Non-rigidParametric ModelDeveloping a CDF-HC divergence as the cost function
Giraldo et al. [106]GroupwiseInformation theoretic measureRigid and Non-rigidParametric ModelUsing a Rényi’s second order entropy divergence as the cost function
Rasoulian et al. [108]GroupwiseProbability-based methodNon-rigidParametric ModelAssumed that the multiple point sets are the noisy observations of mean point set
Evangelidis et al. [2,3]GroupwiseProbability-based methodRigidParametric ModelAssumed that the multiple point sets are transformed realizations of mean point set
Table
Table 2. Runtime of pairwise point set registration algorithms on different datasets.
Table 2. Runtime of pairwise point set registration algorithms on different datasets.
MethodKCICPTPS-RPMCPDCPD-GLSCGF
Fish0.41 s0.47 s2.37 s0.22 s0.42 s37.04 s
Chinese0.39 s0.50 s2.38 s0.22 s0.73 s27.64 s
Table
Table 3. Runtime of groupwise point set registration algorithms on different datasets.
Table 3. Runtime of groupwise point set registration algorithms on different datasets.
MethodCDF-HCJRMPCTMMRényi’s
Fish58.34 s20.06 s27.11 s60.06 s
Chinese77.70 s20.17 s31.70 s72.72 s

Share and Cite

MDPI and ACS Style

Zhu, H.; Guo, B.; Zou, K.; Li, Y.; Yuen, K.-V.; Mihaylova, L.; Leung, H. A Review of Point Set Registration: From Pairwise Registration to Groupwise Registration. Sensors 2019, 19, 1191. https://doi.org/10.3390/s19051191

AMA Style

Zhu H, Guo B, Zou K, Li Y, Yuen K-V, Mihaylova L, Leung H. A Review of Point Set Registration: From Pairwise Registration to Groupwise Registration. Sensors. 2019; 19(5):1191. https://doi.org/10.3390/s19051191

Chicago/Turabian Style

Zhu, Hao, Bin Guo, Ke Zou, Yongfu Li, Ka-Veng Yuen, Lyudmila Mihaylova, and Henry Leung. 2019. "A Review of Point Set Registration: From Pairwise Registration to Groupwise Registration" Sensors 19, no. 5: 1191. https://doi.org/10.3390/s19051191

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop