This paper presents a mutual information (MI) based algorithm for the estimation of full 6-degree-of-freedom (DOF) rigid body transformation between two overlapping point clouds. We first divide the scene into a 3D voxel grid and define simple to compute features for each voxel in the scan. The two scans that need to be aligned are considered as a collection of these features and the MI between these voxelized features is maximized to obtain the correct alignment of scans. We have implemented our method with various simple point cloud features (such as number of points in voxel, variance of z-height in voxel) and compared the performance of the proposed method with existing point-to-point and point-to-distribution registration methods. We show that our approach has an efficient and fast parallel implementation on GPU, and evaluate the robustness and speed of the proposed algorithm on two real-world datasets which have variety of dynamic scenes from different environments.
Iterative Closest Point (ICP) @cite_26 is one of the most popular scan registration algorithms used to estimate the optimal transformation between two overlapping scans. In ICP, closest points between scan @math and reference scan @math are used to obtain a closed-form solution by optimizing the sum of squared distances (usually Euclidean distance). Performing the nearest neighbor search in ICP becomes a bottleneck due to its high computational cost, however, using a K-D Tree @cite_21 does mitigate the problem to an extent. Iterative Dual Correspondence (IDC) @cite_9 generates corresponding points for both rotation and translation separately, with optimization done in an alternate fashion. This improves the alignment accuracy when the initial estimate has large rotational error. Iterative Closest Line (ICL) @cite_14 , @cite_12 , @cite_2 is a variant of ICP in which instead of matching the points in both the scans, the query points in scan @math are matched to lines extracted from points in reference scan @math . Generalized ICP (GICP) @cite_1 , attaches a probabilistic model in estimating the correct corresponding points by taking the covariance structure derived from the local neighborhood in the environment.
@cite_14 @cite_26 @cite_9 @cite_21 @cite_1 @cite_2 @cite_12
1971517213 2049981393 1538216801 2344109021 1709959390 2561423101 2159029220 2083624955 2119851068 2132512702 2148823327 2019563423 2023513943 1602060479 2034950486 2109323956 1501002176 2173117243 2004312117 2140711847
Point set registration is important for calibration of multiple cameras, 3D reconstruction and recognition, etc. The iterative closest point (ICP) algorithm is accurate and fast for point set registration in a same scale, but it does not handle the case with different scales. This paper instead introduces a novel approach named the scaling iterative closest point (SICP) algorithm which integrates a scale matrix with boundaries into the original ICP algorithm for scaling registration. At each iterative step of this algorithm, we set up correspondence between two m-D point sets, and then use a simple and fast iterative algorithm with the singular value decomposition (SVD) method and the properties of parabola incorporated to compute scale, rotation and translation transformations. The SICP algorithm has been proved to converge monotonically to a local minimum from any given parameters. Hence, to reach desired global minimum, good initial parameters are required which are successfully estimated in this paper by analyzing covariance matrices of point sets. The SICP algorithm is independent of shape representation and feature extraction, and thereby it is general for scaling registration of m-D point sets. Experimental results demonstrate its efficiency and accuracy compared with the standard ICP algorithm. The authors describe a general-purpose, representation-independent method for the accurate and computationally efficient registration of 3-D shapes including free-form curves and surfaces. The method handles the full six degrees of freedom and is based on the iterative closest point (ICP) algorithm, which requires only a procedure to find the closest point on a geometric entity to a given point. The ICP algorithm always converges monotonically to the nearest local minimum of a mean-square distance metric, and the rate of convergence is rapid during the first few iterations. Therefore, given an adequate set of initial rotations and translations for a particular class of objects with a certain level of 'shape complexity', one can globally minimize the mean-square distance metric over all six degrees of freedom by testing each initial registration. One important application of this method is to register sensed data from unfixtured rigid objects with an ideal geometric model, prior to shape inspection. Experimental results show the capabilities of the registration algorithm on point sets, curves, and surfaces. > In this work, we analyze three different registration algorithms: Chamfer distance matching, the well-known iterated closest points (ICP) and an optic flow based registration. Their pairwise combination is investigated in the context of silhouette based pose estimation. It turns out that Chamfer matching and ICP used in combination do not only perform fairly well with small offset, but also deal with large offset significantly better than the other combinations. We show that by applying different optimized search strategies, the computational cost can be reduced by a factor eight. We further demonstrate the robustness of our method against simultaneous translation and rotation. The Iterative Closest Point (ICP) algorithm is one of the most widely used methods for point-set registration. However, being based on local iterative optimization, ICP is known to be susceptible to local minima. Its performance critically relies on the quality of the initialization and only local optimality is guaranteed. This paper presents the first globally optimal algorithm, named Go-ICP, for Euclidean (rigid) registration of two 3D point-sets under the @math error metric defined in ICP. The Go-ICP method is based on a branch-and-bound scheme that searches the entire 3D motion space @math . By exploiting the special structure of @math geometry, we derive novel upper and lower bounds for the registration error function. Local ICP is integrated into the BnB scheme, which speeds up the new method while guaranteeing global optimality. We also discuss extensions, addressing the issue of outlier robustness. The evaluation demonstrates that the proposed method is able to produce reliable registration results regardless of the initialization. Go-ICP can be applied in scenarios where an optimal solution is desirable or where a good initialization is not always available. The iterative closest point (ICP) algorithm [2] is a popular method for modeling 3D objects from range data. The classical ICP algorithm rests on a rigid surface assumption. Building on recent work on nonrigid object models [5; 16; 9], this paper presents an ICP algorithm capable of modeling nonrigid objects, where individual scans may be subject to local deformations. We describe an integrated mathematical framework for simultaneously registering scans and recovering the surface configuration. To tackle the resulting high-dimensional optimization problems, we introduce a hierarchical method that first matches a coarse skeleton of scan points, then adapts local scan patches. The approach is implemented for a mobile robot capable of acquiring 3D models of objects. Despite the fact that original Iterative Closest Point(ICP) algorithm has been widely used for registration, itcannot tackle the problem when two point clouds are par-tially overlapping. Accordingly, this paper proposes a ro-bust approach for the registration of partially overlappingpoint clouds. Given two initially posed clouds, it firstlybuilds up bilateral correspondence and computes bidirec-tional distances for each point in the data shape. Based onthe ratio of bidirectional distances, the exponential functionis selected and utilized to calculate the probability value,which can indicate whether the point pair belongs to theoverlapping part or not. Subsequently, the probability val-ue can be embedded into the least square function for reg-istration of partially overlapping point clouds and a novelvariant of ICP algorithm is presented to obtain the optimalrigid transformation. The proposed approach can achievegood registration of point clouds, even when their overlappercentage is low. Experimental results tested on public da-ta sets illustrate its superiority over previous approaches onrobustness. This paper presents methodologies to accelerate the registration of 3D point cloud segments by using hue data from the associated imagery. The proposed variant of the Iterative Closest Point (ICP) algorithm combines both normalized point range data and weighted hue value calculated from RGB data of an image registered 3D point cloud. A k-d tree based nearest neighbor search is used to associated common points in x, y, z, hue 4D space. The unknown rigid translation and rotation matrix required for registration is iteratively solved using Singular Value Decomposition (SVD) method. A mobile robot mounted scanner was used to generate color point cloud segments over a large area. The 4D ICP registration has been compared with typical 3D ICP and numerical results on the generated map segments shows that the 4D method resolves ambiguity in registration and converges faster than the 3D ICP This paper describes a general purpose, representation independent method for the accurate and computationally efficient registration of 3-D shapes including free-form curves and surfaces. The method handles the full six-degrees of freedom and is based on the iterative closest point (ICP) algorithm, which requires only a procedure to find the closest point on a geometric entity to a given point. The ICP algorithm always converges monotonically to the nearest local minimum of a mean-square distance metric, and experience shows that the rate of convergence is rapid during the first few iterations. Therefore, given an adequate set of initial rotations and translations for a particular class of objects with a certain level of 'shape complexity', one can globally minimize the mean-square distance metric over all six degrees of freedom by testing each initial registration. For examples, a given 'model' shape and a sensed 'data' shape that represents a major portion of the model shape can be registered in minutes by testing one initial translation and a relatively small set of rotations to allow for the given level of model complexity. One important application of this method is to register sensed data from unfixtured rigid objects with an ideal geometric model prior to shape inspection. The described method is also useful for deciding fundamental issues such as the congruence (shape equivalence) of different geometric representations as well as for estimating the motion between point sets where the correspondences are not known. Experimental results show the capabilities of the registration algorithm on point sets, curves, and surfaces. The ICP (Iterative Closest Point) algorithm is widely used for geometric alignment of three-dimensional models when an initial estimate of the relative pose is known. Many variants of ICP have been proposed, affecting all phases of the algorithm from the selection and matching of points to the minimization strategy. We enumerate and classify many of these variants, and evaluate their effect on the speed with which the correct alignment is reached. In order to improve convergence for nearly-flat meshes with small features, such as inscribed surfaces, we introduce a new variant based on uniform sampling of the space of normals. We conclude by proposing a combination of ICP variants optimized for high speed. We demonstrate an implementation that is able to align two range images in a few tens of milliseconds, assuming a good initial guess. This capability has potential application to real-time 3D model acquisition and model-based tracking. We present a robot-pose-registration algorithm, which is entirely based on large planar-surface patches extracted from point clouds sampled from a three-dimensional (3-D) sensor. This approach offers an alternative to the traditional point-to-point iterative-closest-point (ICP) algorithm, its point-to-plane variant, as well as newer grid-based algorithms, such as the 3-D normal distribution transform (NDT). The simpler case of known plane correspondences is tackled first by deriving expressions for least-squares pose estimation considering plane-parameter uncertainty computed during plane extraction. Closed-form expressions for covariances are also derived. To round-off the solution, we present a new algorithm, which is called minimally uncertain maximal consensus (MUMC), to determine the unknown plane correspondences by maximizing geometric consistency by minimizing the uncertainty volume in configuration space. Experimental results from three 3-D sensors, viz., Swiss-Ranger, University of South Florida Odetics Laser Detection and Ranging, and an actuated SICK S300, are given. The first two have low fields of view (FOV) and moderate ranges, while the third has a much bigger FOV and range. Experimental results show that this approach is not only more robust than point- or grid-based approaches in plane-rich environments, but it is also faster, requires significantly less memory, and offers a less-cluttered planar-patches-based visualization. This paper presents a method for pairwise 3D alignment which solves data association by matching scan segments across scans. Generating accurate segment associations allows to run a modified version of the Iterative Closest Point (ICP) algorithm where the search for point-to-point correspondences is constrained to associated segments. The novelty of the proposed approach is in the segment matching process which takes into account the proximity of segments, their shape, and the consistency of their relative locations in each scan. Scan segmentation is here assumed to be given (recent studies provide various alternatives [10], [19]). The method is tested on seven sequences of Velodyne scans acquired in urban environments. Unlike various other standard versions of ICP, which fail to recover correct alignment when the displacement between scans increases, the proposed method is shown to be robust to displacements of several meters. In addition, it is shown to lead to savings in computational times which are potentially critical in real-time applications. Most range data registration techniques are variants on the iterative closest point (ICP) algorithm, proposed by Y. Chen and G. Medioni (1991, Proceedings of the IEEE Conference on Robotics and Automation) and P. J. Besl and N. D. McKay ( 1992, IEEE Trans. Pattern Anal. Mach. Intell. 14, 239-256). That algorithm, though, is only one approach to optimizing a least-squares point correspondence sum proposed by K. S. Arun. T. Huang, and S. D. Blostein (1987, IEEE Trans. Pattern Anal. Mach. Intell, 9, 698-700). In its basic form ICP has many problems, for example, its reliance on preregistration by hand close to the global minimum and its tendency to converge to suboptimal or incorrect solutions. This paper reports on an evolutionary registration algorithm which does not require initial prealignment and has a very broad basin of convergence. It searches many areas of a registration parameter space in parallel and has available to it a selection of evolutionary techniques to avoid local minima which plague both ICP and its variants. We present a robust plane finding algorithm that when combined with plane-based frame-to-frame registration gives accurate real-time pose estimation. Our plane extraction is capable of handling large and sparse datasets such as those generated from spinning multi-laser sensors such as the Velodyne HDL-32E LiDAR. We test our algorithm on frame-to-frame registration in a closed-loop indoor path comprising 827 successive 3D laser scans (over 57 million points), using no additional information (e.g., odometry, IMU). Our algorithm outperforms, in both accuracy and time, three state-of-the-art methods, based on iterative closest point (ICP), plane-based randomized Hough transform, and planar region growing. Robust registration of two 3-D point sets is a common problem in computer vision. The iterative closest point (ICP) algorithm is undoubtedly the most popular algorithm for solving this kind of problem. In this paper, we present the Picky ICP algorithm, which has been created by merging several extensions of the standard ICP algorithm, thus improving its robustness and computation time. Using pure 3-D point sets as input data, we do not consider additional information like point color or neighborhood relations. In addition to the standard ICP algorithm and the Picky ICP algorithm proposed in this paper, a robust algorithm due to Masuda and Yokoya and the RICP algorithm by are evaluated. We have experimentally determined the basin of convergence, robustness to noise and outliers, and computation time of these four ICP based algorithms. Data acquisition in large-scale scenes regularly involves accumulating information across multiple scans. A common approach is to locally align scan pairs using Iterative Closest Point (ICP) algorithm (or its variants), but requires static scenes and small motion between scan pairs. This prevents accumulating data across multiple scan sessions and or different acquisition modalities (e.g., stereo, depth scans). Alternatively, one can use a global registration algorithm allowing scans to be in arbitrary initial poses. The state-of-the-art global registration algorithm, 4PCS, however has a quadratic time complexity in the number of data points. This vastly limits its applicability to acquisition of large environments. We present Super 4PCS for global pointcloud registration that is optimal, i.e., runs in linear time (in the number of data points) and is also output sensitive in the complexity of the alignment problem based on the (unknown) overlap across scan pairs. Technically, we map the algorithm as an 'instance problem' and solve it efficiently using a smart indexing data organization. The algorithm is simple, memory-efficient, and fast. We demonstrate that Super 4PCS results in significant speedup over alternative approaches and allows unstructured efficient acquisition of scenes at scales previously not possible. Complete source code and datasets are available for research use at http: geometry.cs.ucl.ac.uk projects 2014 super4PCS . We propose a novel algorithm to register multiple 3D point sets within a common reference frame using a manifold optimization approach. The point sets are obtained with multiple laser scanners or a mobile scanner. Unlike most prior algorithms, our approach performs an explicit optimization on the manifold of rotations, allowing us to formulate the registration problem as an unconstrained minimization on a constrained manifold. This approach exploits the Lie group structure of SO 3 and the simple representation of its associated Lie algebra so 3 in terms of R3. Our contributions are threefold. We present a new analytic method based on singular value decompositions that yields a closed-form solution for simultaneous multiview registration in the noise-free scenario. Secondly, we use this method to derive a good initial estimate of a solution in the noise-free case. This initialization step may be of use in any general iterative scheme. Finally, we present an iterative scheme based on Newton's method on SO 3 that has locally quadratic convergence. We demonstrate the efficacy of our scheme on scan data taken both from the Digital Michelangelo project and from scans extracted from models, and compare it to some of the other well known schemes for multiview registration. In all cases, our algorithm converges much faster than the other approaches, (in some cases orders of magnitude faster), and generates consistently higher quality registrations. Proposed is a robust algorithm for scaling registration of point sets, in the way of introducing the bidirectional distance measurement into the least square problem, which is solved in the way the iterative closest point algorithm does by iterations. At each iterative step of this algorithm, bidirectional correspondence is set up between two m-dimensional point sets, and then a simple and fast iterative algorithm is used to compute the rotation, scale and translation transformations. Experimental results demonstrate its robustness and high accuracy over previous algorithms. Abstract In this paper we present a framework for the automatic registration of multiple terrestrial laser scans. The proposed method can handle arbitrary point clouds with reasonable pairwise overlap, without knowledge about their initial orientation and without the need for artificial markers or other specific objects. The framework is divided into a coarse and a fine registration part, which each start with pairwise registration and then enforce consistent global alignment across all scans. While we put forward a complete, functional registration system, the novel contribution of the paper lies in the coarse global alignment step. Merging multiple scans into a consistent network creates loops along which the relative transformations must add up. We pose the task of finding a global alignment as picking the best candidates from a set of putative pairwise registrations, such that they satisfy the loop constraints. This yields a discrete optimization problem that can be solved efficiently with modern combinatorial methods. Having found a coarse global alignment in this way, the framework proceeds by pairwise refinement with standard ICP, followed by global refinement to evenly spread the residual errors. The framework was tested on six challenging, real-world datasets. The discrete global alignment step effectively detects, removes and corrects failures of the pairwise registration procedure, finally producing a globally consistent coarse scan network which can be used as initial guess for the highly non-convex refinement. Our overall system reaches success rates close to 100 at acceptable runtimes 1 h, even in challenging conditions such as scanning in the forest. Abstract This paper introduces a new method of registering point sets. The registration error is directly minimized using general-purpose non-linear optimization (the Levenberg–Marquardt algorithm). The surprising conclusion of the paper is that this technique is comparable in speed to the special-purpose Iterated Closest Point algorithm, which is most commonly used for this task. Because the routine directly minimizes an energy function, it is easy to extend it to incorporate robust estimation via a Huber kernel, yielding a basin of convergence that is many times wider than existing techniques. Finally, we introduce a data structure for the minimization based on the chamfer distance transform, which yields an algorithm that is both faster and more robust than previously described methods. The problem of geometric alignment of two roughly preregistered, partially overlapping, rigid, noisy 3D point sets is considered. A new natural and simple, robustified extension of the popular Iterative Closest Point (ICP) algorithm (Besl and McKay, 1992) is presented, called the Trimmed ICP (TrICP). The new algorithm is based on the consistent use of the least trimmed squares (LTS) approach in all phases of the operation. Convergence is proved and an efficient implementation is discussed. TrICP is fast, applicable to overlaps under 50 , robust to erroneous measurements and shape defects, and has easy-to-set parameters. ICP is a special case of TrICP when the overlap parameter is 100 . Results of testing the new algorithm are shown.