IEEE Robotics & Automation Magazine - December 2015 - 115

structure of the input data exist. Most notably, a special two-dimensional (2-D) variant (" CorrespondenceRejectorSampleConsensus2D ) of the RANSAC-based
correspondence rejector discards pairs based on their pixel
distance in the image plane after the source point is transformed and projected into the target camera plane.
5) Rejection Based on Normal Compatibility: This filter uses the
normal information about the points and rejects those pairs
that have inconsistent normals, i.e., the angle between their
normals is larger than a given threshold. It can reject erroneous pairs that seem correct when judged only by the distance
between the points, such as the case depicted in Figure 3(b)
(" CorrespondenceRejectorSurfaceNormal).
6) Rejection Based on Surface Boundaries: Furthermore, when
two point clouds captured by a projective sensor represent
surfaces that have a partial overlap, accepting correspondences containing surface boundary points can introduce
errors [Figure 3(d)]. To detect such points, we can exploit
the organized nature of the depth maps and eliminate the
correspondences that contain points on depth discontinuities by moving a window across the depth image and checking if there are enough points in the window that are within
a threshold depth from the center point (" CorrespondenceRejectorBoundaryPoints).
7) Rejector Pipelines: Most often, not only is a single rejector
applied, but several correspondence rejectors are queued to
implement a filtering pipeline. For example, Diebel et al.
[7] apply a combination of different solutions for rejecting
point pairs in their active stereo point clouds, emphasizing
the importance of rejecting points on mesh boundaries
(see the RGB-D example in the "Transformation Estimation and Weighting" section). They also reject pairs based
on their normal compatibility and based on their point-topoint distance using a distance threshold based on the median distance. In the PCL, multiple rejectors can be easily
concatenated using the output correspondences of the previous rejector as input to the next one.
We provide a usage example for PCL correspondence rejection in Listing 5. Given the input point clouds and a set of estimated correspondence pairs, getCorrespondences runs
the rejection and returns the vector of filtered correspondence
pairs. Moreover, all correspondence rejection methods in the
PCL feature getRejectedQueryIndices to retrieve the
Listing 5. Correspondence rejection
(based on distance).
#include 
(...)
CorrespondenceRejectorDistance rejector;
rejector.setInputSource (cloud_src);
rejector.setInputTarget (cloud_tgt);
rejector.setInputCorrespondences
(corresps_in);
rejector.setMaximumDistance (max_dist);
rejector.getCorrespondences (corresps_
filtered);

indices of query points of rejected correspondence pairs. This
information is useful, for example, to determine nonoverlapping parts between the source and the target point cloud.
Alignment-Error Metrics and
Transformation Estimation
Over the years, there have been numerous mathematical approaches for solving for the rigid transformation T that minimizes the error of the point pairs. T is composed of a rotation
R and a translation t. Note that when referring to a transform
T and a point p, homogeneous coordinates will be used.
There are two main error metrics to be minimized that
have been considered in literature: point-to-point (2) and
point-to-plane (3), where ^ p l, q lh is the l th of the N pair
correspondences from the source cloud to the target cloud:
N

E point - to - point ^T h = / w k || T p k - q k || 2, and
k =1
N

E point - to - plane ^T h = / w k ^^T p k - q kh $ n q kh2 .
k =1

(2)
(3)

The optional w l can be used for weighting the pairs to give
them more or less importance in the least squares formulation (w l = 1 if no weighting is applied).
1) Standard Point-to-Point Error Metric: The standard error
metric used in the ICP algorithm is the point-to-point
error metric (2). When it was first mentioned by Arun [8],
researchers proposed various ways of minimizing it, which
led to the introduction of the ICP algorithm [2]. Eggert et
al. [9] evaluated each of these methods in terms of numerical stability and accuracy, reaching the conclusion that they
are close performers.
PCL provides an implementation using a closed-form
singular value decomposition (SVD) that was first proposed
by Horn [10] (" TransformationEstimationSVD).
2) Point-to-Plane Error Metric: Chen and Medioni [3] introduced the point-to-plane metric (3) and proved that it was
more stable and faster to converge than the previous approaches. This algorithm uses the distance between the
source point p l and the plane described by the target point
q l and its local surface normal n q k . Unlike the point-topoint metric, it does not have a closed-form solution, so the
minimization is done with nonlinear solvers (such as Levenberg-Marquadt, as proposed by [11]) or by linearizing it [12]
(under the assumption of small rotation angles, i.e.,
sin i + i and cos i + 1h .
Depending on the underlying surface and the distribution of points, using the point-to-plane error metric can be
considerably more robust. A standard procedure for minimizing it relies on the Levenberg-Marquardt nonlinear
optimizer [11] (" TransformationEstimationPointToPlane).
3) Linear Least Squares Point-to-Plane: The PCL also features
an alternative method that accumulates the point-to-plane
constraints of all the correspondences in a matrix A and estimates the rotation and translation in the least squares sense
by solving a linear system of the form A T A v = A T b, with
DECEMBER 2015

*

IEEE ROBOTICS & AUTOMATION MAGAZINE

*

115
Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - December 2015
