IEEE Robotics & Automation Magazine - December 2015 - 114

projections from source points in world coordinates to the
camera plane of the target frame using the intrinsic and extrinsic camera parameters:
R p xV
S W d$u
fx 0 c x 0
S p yW
@
6
f
c
R
|
t
(1)
0
0
> y y H
S p zW = >d $ vH,
S
W
0 0 1 0
d
S W
T1X
where the first matrix is the intrinsic calibration matrix of the
source camera with ^ fx, f y h being the focal length (divided
by image width and height, respectively) and ^c x, c y h the
camera projection center, the matrix 6R t] is the transformation of the source camera, d is the depth of the projected
point p = ^ p x p y p z hT in the target camera, and u, v are the
coordinates of p in the target camera plane. After projection,
the query point is assigned to its closest point in the image
space (if uand v lie within image boundaries) or considered
part of the nonoverlapping volume between the source and
target cloud.
Listing 4. Correspondence estimation using
projections.
#include 
(...)
CorrespondenceEstimationOrganizedProjection
 est;
est.setInputSource (cloud_source);
est.setInputTarget (cloud_target);
est.setFocalLengths (f_x, f_y);
est.setDepthThreshold (epsilon);
CorrespondencesPtr corresps (new
Correspondences ());
est.determineCorrespondences (*corresps);

nqj

qj

qj
npi
qj

pi
(a)

pi
(b)

qj

qj

pi

pi

(c)

(d)

Figure 3. An example of correspondence rejection. Good
correspondence pairs (green) are kept while outliers (red) are sorted
out to improve convergence. (a) The rejection of pairs based on the
distance between the points, (b) the rejection of pairs based on
normal compatibility, (c) the rejection of pairs with duplicate target
matches, and (d) the rejection of pairs that contain boundary points.

114

*

IEEE ROBOTICS & AUTOMATION MAGAZINE

*

DECEMBER 2015

This approach is fast but imprecise for point clouds with
large depth discontinuities or for frames that are far away
from each other. That is why this method is recommended to
be used only after the two point clouds have been brought
close together, making it good for aligning consecutive point
clouds in a stream recorded at a high frame rate. A code snippet for projection-based correspondence estimation is presented in Listing 4.
Rejecting and Filtering Correspondences
Since invalid correspondences can negatively affect the registration results, most registration pipelines feature a rejection
step. This step consists of filtering the point pairs matched in
the previous stage to facilitate the transformation estimation
algorithm toward convergence to the global minimum. This
step can take advantage of auxiliary information available
from the input point clouds, such as local surface normals or
statistics about the correspondences. Referring to Figure 3,
the following correspondence rejection methods are commonly deployed and available in the PCL.
1) Correspondence Rejection Based on Distance: This method
filters out point pairs with a distance larger than a given
threshold [see Figure 3(a)]. It is used in [1] and was already
mentioned in the original formulation of the ICP algorithm
[2] (" CorrespondenceRejectorDistance).
2) Rejection Based on Median Distance: Unlike the previous
rejector, this one does not use a fixed threshold but computes it as the median of all point-to-point distances in
the input set of correspondences. Hence, it considers the
distribution of the distances between the points and
adapts to it, becoming smaller as the two point clouds get
closer during ICP iterations. Compared with an adaptive
threshold based on the mean value, the median is often
more effective in reducing the influence of outliers
(" CorrespondenceRejectorMedianDistance).
3) Rejecting Pairs with Duplicate Target Matches: Usually, each
sampled point in the source cloud is assigned to a correspondence in the target cloud. Hence, a point in the target cloud
could be assigned multiple corresponding source points [see
Figure 3(c)]. This rejector only keeps a single pair ^ p i min, q jh,
the one with the minimum distance out of all the pairs
"^ p i, q jh, (" CorrespondenceRejectorOneToOne).
4) RANSAC-Based Rejection: This method applies random
sample consensus (RANSAC) [6] to estimate a transformation for subsets of the given set of correspondences and
eliminates the outlier correspondences based on the Euclidean distance between the points after the computed transformation is applied to the source point cloud. It is effective
in keeping the ICP algorithm from converging into local
minima, as it always produces slightly different correspondences and is good at filtering outliers. In addition, it provides good initial parameters for the transformation
estimation with all inlier correspondence that follows
(" CorrespondenceRejectorSampleConsensus).
For the registration of point clouds coming from projective
sensors, correspondence rejectors that exploit the image-like
Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - December 2015
