PE&RS February 2017 Public - page 137

PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING February 2017 137
Automatic 3D Surface Co-Registration Using
Keypoint Matching
Ravi Ancil Persad and Costas Armenakis
Abstract
A framework for co-registering multi-temporal 3D point cloud
surfaces (PCSs) is presented, which addresses the co-regis-
tration of urban and non-urban 3D surfaces formed by 3D
points. These surfaces are acquired from different surface
measurement sensors and are in different coordinate systems.
No prior information about initial transformation parameters
or proximate matching is assumed. A keypoint matching
approach is proposed to co-register two PCSs. First, surface
curvature information is utilized for scale-invariant keypoint
extraction. Then, every keypoint is characterized by a scale,
rotation, and translation invariant surface descriptor called
the radial geodesic distance-slope histogram. Keypoints
with similar surface descriptors on the two PCSs are matched
using bipartite graph matching. Given scale, rotation and
translation changes between PCS pairs, co-registration tests
on multi-sensor urban and non-urban datasets gave rotation
errors from 0.017° to 0.023°, translation errors from 0.007 m
to 0.013 m and scale factor errors from 0.0002 to 0.0014.
Introduction
Automatic registration of 3D point cloud surfaces (PCSs) is an
active area of research in numerous fields of study includ-
ing photogrammetry, mobile mapping, computer vision, and
computer graphics. Typical registration tasks usually require
the alignment of 3D surfaces that are multitemporal or acquired
from different sensors or different viewpoints of the same or
similar sensors. More specifically, the co-registration of point
cloud data pairs is required for 3D surface completion or recon-
struction from partially overlapping surfaces located in different
coordinate systems. The co-registration of a source and target
dataset is achieved through a 3D conformal transformation when
both PCS s differ in terms of scale, rotation, and translation.
Fully automatic 3D alignment has two general steps: (a)
an initial, coarse alignment, and (b) a refined alignment.
The initial coarse global alignment may or may not require
discrete features (e.g., points, lines) to estimate the 3D confor-
mal transformation. “Refinement-based” registration methods
strongly depend on a very good initial point cloud alignment
with sufficient overlap between corresponding portions of
the 3D surfaces. The “refinement” methods do not require an
intricate feature-matching step as they are typically based on
minimizing the Euclidean distance between closest points.
If the initial alignment is inaccurate, the refinement-based
approaches are prone to various mis-registration factors such
as local minima solutions and exhaustive searching in the
solution space, which negatively affects computational effi-
ciency. In this paper, we address the problem of automating
the initial alignment.
There are two primary approaches for initial, coarse 3D-to-
3D PCS alignment: (a) global techniques, and (b) local tech-
niques, (Castellani and Bartoli, 2012). The global-based initial
alignment revolves around the use of the principal component
analysis (PCA) of the point clouds. PCA is used to approxi-
mate the rotation required to align the coordinate systems of
the source and target PCSs. The translation can be estimated
by the difference in centroids of the source and target data. On
the other hand, local techniques are based on the definition of
local surface attributes (or descriptors) for keypoints on each
PCS. These descriptors are then used to find corresponding
keypoints. The global co-registration approach suffers when
there is partial overlap and/or shape deformation between the
source and target surfaces. For instance, the centroids of both
shapes may differ due to deformations or when the source
and target have different coverage. This affects the estimation
of translation parameters. Difference in shape creates similar
problems when attempting to estimate rotation parameters.
Therefore, it can be argued that the local alignment technique
is better suited for co-registering the stable parts of PCSs when
dealing with natural terrain datasets which may have under-
gone deformation, for example, landslides, flow of glaciers, etc.
In the co-registration process, a mathematical mapping
has to be applied to transform the “source” PCS to its “target”
PCS. The challenge lies in establishing this “mapping.” We
describe this problem as the coupled “correspondence and
transformation problem.” The “correspondence problem” is to
automatically determine which source features match to their
corresponding target entities in the 3D space, hence enabling
us to solve for the desired mapping parameters. The “trans-
formation problem” is based on the automated recovery of
the unknown mapping parameters required to align 3D source
features with their 3D counterparts on the “target” PCS.
Previous Work on 3D Surface Matching and Registration
The classical Iterative Closest Point (ICP) algorithm (Besl and
McKay, 1992) is one of the most popular and widely applied
3D co-registration algorithms. ICP uses a point’s nearest neigh-
bor as its correspondence, which is then used to compute a
3D conformal transformation for alignment. This procedure
repeats itself until the quality of fitting between transformed
source and target shape meets some convergence thresh-
old. Over the years, there have been many variants of ICP
(Rusinkiewicz and Levoy, 2001). The ICP and its variants fall
into the class of refinement-based matching algorithms. There-
fore, their performance relies on a good, initial alignment.
In photogrammetric literature, numerous refinement-based
surface matching methods are also reported. Gruen and Akca
(2005) developed the so-called “Least Squares 3D Surface
Matching” (LS3D). Resembling the ICP approach, LS3D also iter-
atively minimizes the sum of squares of Euclidean distances
between two surfaces. However, LS3D differs from ICP in its
Geomatics Engineering, GeoICT Lab, Department of Earth and
Space Science and Engineering, Lassonde School of Engineer-
ing, York University, 4700 Keele St., Toronto, Ontario, M3J
1P3 Canada (ravi071@yorku.ca).
Photogrammetric Engineering & Remote Sensing
Vol. 83, No. 2, February 2017, pp. 137–151.
0099-1112/17/137–151
© 2017 American Society for Photogrammetry
and Remote Sensing
doi: 10.14358/PERS.83.2.137