On Fast Surface Reconstruction Methods for Large and Noisy Point Clouds
Zoltan Csaba Marton, Radu Bogdan Rusu, Michael Beetz
Intelligent Autonomous Systems, Technische Universit
¨
at M
¨
unchen
{marton,rusu,beetz}@cs.tum.edu
Abstract— In this paper we present a method for fast surface
reconstruction from large noisy datasets. Given an unorganized
3D point cloud, our algorithm recreates the underlying surface’s
geometrical properties using data resampling and a robust
triangulation algorithm in near realtime. For resulting smooth
surfaces, the data is resampled with variable densities according
to previously estimated surface curvatures. Incremental scans
are easily incorporated into an existing surface mesh, by deter-
mining the respective overlapping area and reconstructing only
the updated part of the surface mesh. The proposed framework
is flexible enough to be integrated with additional point label
information, where groups of points sharing the same label
are clustered together and can be reconstructed separately,
thus allowing fast updates via triangular mesh decoupling. To
validate our approach, we present results obtained from laser
scans acquired in both indoor and outdoor environments.
I. INTRODUCTION
Autonomous mobile robots need continuous surface mod-
els of real-word scenes for navigation and manipulation.
The accuracy of these models (often referred to as maps)
is crucial for 3D collision detection while moving along a
planned path, but also for supporting environment modelling
and scene classification. Moreover, they need to have low
computational requirements, as a mobile robotic platform
has limited computational power capabilities which need to
be shared between its different software components (e.g.
perception, navigation, task planning, manipulation, etc).
Due to the latter constraint, most of the robotic navigation
systems today rely on 2D discrete representations of the
world, such as large scale 2D occupancy maps. This is in
contrast with applications in computer graphics – like the
reconstruction of architectural heritage [1] or 3D watertight
objects [2] – which build extremely accurate models whose
appearance has to be as close as possible to the original
surface, but at a much smaller scale.
Recent advances in 3D sensing devices made their deploy-
ment possible on mobile robotic platforms, and enabled the
acquisition of large 3D point cloud datasets (PCD). However,
these datasets represent discrete, sampled representations of
the world, so a transformation into continuous surfaces is
required. To this end, we investigate the following compu-
tational problem: given a noisy 3D point cloud model of a
real-world scene as depicted in Figure 1, create a contin-
uous triangular mesh surface representation which reliably
represents the scene, as fast as possible.
Our approach for creating the triangular mesh is based on
the incremental surface growing principle (as devised by [3]),
because it can deal with all types of surfaces where points
Fig. 1. Top: point cloud dataset of an indoor kitchen environment (15
millions of points) shown in grayscale intensity. Bottom: its continuous
mesh representation (downsampled for visualization).
on two different layers can be distinguished by a distance
criterion. Our algorithm selects a starting triangle’s vertices
and connects new triangles to it until either all points are
considered or no more valid triangles can be connected.
In the second case a new seed triangle is placed in the
unconnected part and the triangulation is restarted.
In contrast to well known surface reconstruction methods
from computer graphics [4], [5], [6], [7], our methods works
reliably on noisy 2.5D data scans acquired by mobile robots
navigating in indoor and outdoor environments.
The proposed surface reconstruction algorithm is partially
based on the triangulation algorithm presented in [4]. The
method has the advantage that it is a greedy type approach,
where edges are written directly and are never deleted,
making it fast and memory efficient, yielding the first correct
triangulation.
Triangulation is done incrementally: i) for each point p,
a k-neighborhood is selected by searching for the point’s
nearest k neighbors in a sphere with radius r = µ · d
0
that
adapts to the local point density (d
0
is the distance of p to its
closest neighbor and µ is a user-specified constant); ii) the
neighborhood is projected on a plane that is approximately
tangential to the surface formed by the neighborhood and
ordered around p; iii) then the points are pruned by visibility
and connected to p and to consecutive points by edges,
forming triangles that have a maximum angle criterion and
an optional minimum angle criterion.
The projection along the estimated surface normal occurs
in the last two steps previously mentioned. In [4], this normal
is estimated as the average of the normals of the triangles
that have p as one of their vertices. This simplification makes
sense only if the underlying surface is assumed to be smooth,
that is the deviation between the normals of any two incident
triangles on a vertex is less than 90
◦
. The projection of the
2009 IEEE International Conference on Robotics and Automation
Kobe International Conference Center
Kobe, Japan, May 12-17, 2009
978-1-4244-2789-5/09/$25.00 ©2009 IEEE 3218
- 1
- 2
- 3
前往页