We focus on point cloud based representation and reasoning techniques
for building accurate and meaningful 3D maps for mobile robots in both
indoor and outdoor environments. One of our main application and
deployement scenario is the Assistive Kitchen.
However, all our methods were carefully crafted with generality in mind,
therefore they have been also successfully applied to outdoor urban,
aerial, and underwater datasets.
In the Assistive
Kitchen we investigate how an autonomous mobile robot (see Point Cloud Data Acquisition below) can acquire
an environment object model of a kitchen, and more generally of human
living environments. The acquired environment model is to serve as a
resource for robotic assistants that are to perform household chores
including setting the table, cleaning up, preparing meals, etc. In
tasks like these ones it does not suffice to have models that serve
localization and navigation purposes. Rather the robot has to know about
cupboards, tables, drawers, shelves, etc, how to open and use them, what
is stored in them, etc. Finally, the models have to represent ovens,
dish washers and other appliances as specific kinds of cupboards.
A list of 3D Semantic Mapping related topics is given below. Please note that the descriptions are highly simplified and their purpose is only
to give some support for the movies/animations presented. For a comprehensive and in-depth mathematical explanation of each algorithm, please
consult our publication list given at the bottom of the page. Do not hesitate to contact us in case you are working on similar topics and/or you'd like
more information about a certain method.
Our standard method for acquiring point cloud datasets makes use of the
robot in the figure. While performing sweeping movements of its arm, we
record the laser sensor data and together with the joint angles
transform it into a 3D point cloud. Each point in the cloud is
represented by a tuple containing: the 3D position in world coordinates
{x, y, z}, intensity and distance values {i, d}, together with
additional scan information. Some technical characteristics of our
platform:
While this is our most used hardware platform, it is not the only one.
In fact, all our methods and algorithms are written to be completely
independent of the underlying hardware that is used to acquire the
datasets. We use point cloud data from a variety of sources (as you will
see below), ranging from stereo cameras, to all sorts of laser scanners
(indoors, outdoors, aerial, etc).
The following short movies depict the acquisition of point cloud
datasets (triangulated on the second row).
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
Laser scans typically generate PCDs of varying point densities.
Additionally, measurement errors lead to sparse outliers which corrupt
the results even more. This complicates the estimation of local point
cloud characteristics such as surface normals or curvature changes,
leading to erroneous values, which in turn might cause point cloud
registration failures. Some of these irregularities can be solved by
performing a statistical analysis on each point's neighborhood, and
trimming those which do not meet a certain criteria.
Our sparse outlier removal is based on the computation of the
distribution of point to neighbors distances in the input dataset. For
each point, we compute the mean distance from it to all its neighbors.
By assuming that the resulted distribution is Gaussian with a mean and a
standard deviation, all points whose mean distances are outside an
interval defined by the global distances mean and standard deviation can
be considered as outliers and trimmed from the dataset.
The following short movies depict the effects of the sparse outlier
analysis: the original datasets are shown on the left, while the
resulted processed ones on the right.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
Two of the most widely used geometric point features are the underlying
surface's estimated curvature and normal at a given point p. Both of
them are considered local features, as they characterize a point
using the information provided by its k closest point neighbors. For
determining these neighbors efficienctly, the input dataset is usually split
into smaller chunks using spatial decomposition techniques such as octrees
or kD-trees (see figure - left: kD-tree, right: octree), and then closest
point searches are performed in that space. Depending on the application one
can opt for either determining a fixed number of k points in the
vecinity of p, or all points which are found inside of a sphere of
radius r centered at p.
Unarguably, one the easiest methods for estimating the surface normals and
curvature changes at a point p is to perform an eigendecomposition
(i.e. compute the eigenvectors and eigenvalues) of the k-neighborhood point
surface patch. Thus, the eigenvector corresponding to the smallest
eigenvalue will approximate the surface normal n at point p,
while the surface curvature change will be estimated from the eigenvalues as
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
The estimated point normals give a good approximation of the surface
normals, but the results obtained using methods such as Principal Component
Analysis (PCA) are in general not consistently oriented (see figure right).
However, taking advantage of the known viewpoint* v (for 2.5D scans)
we can flip the normals that aren't pointing towards it. To do so, we flip
all normals n that do not satisfy:
The right part of the figure below shows the EGI (Extended Gaussian
Image, i.e. normal sphere) and the orientation of point normals directly
after PCA (top), as well as the results after re-orienting them consistently
towards the viewpoint (bottom). Notice how normals are dispersed on both
parts of the EGI before propagating the consistent orientation.
* - for a viewpoint estimation method, please see our relevant publications below.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
Some of the data irregularities (caused by small distance measurement
errors) are very hard to remove using statistical analysis. To create
complete models, glossy surfaces as well as occlusions in the data must be
accounted for. In situations where additional scans are impossible to
acquire, a solution is to use a resampling algorithm, which attempts to
recreate the missing parts of the surface by higher order polynomial
interpolations between the surrounding data points. By performing
resampling, these small errors can be corrected and the "double walls"
artifacts resulted from registering multiple scans together can be
smoothed.
To approximate the surface defined by a local neighborhood of points
p1, p2 ... pk at a point q we use a bivariate
polynomial height function defined on a on a robustly computed reference
plane. The values of the function at the points p are represented by
the F array, while the different powers of the points' 2D coordinates
(on the reference plane) are computed in the X matrix. The
coefficients of the polynomial are computed as follows:
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
When using point features as characteristics of an entire point cloud, it's
good to make sure that we find a compact subset of points Pf that
best represents the given point cloud P. The lesser the number of
feature points and the better they approximate the data, the more efficient
is the subsequent interpretation process.
In order to select the most persistent feature points for a point cloud, we
analyze the neighborhood of each point p multiple times, by enclosing
the point on a sphere S with radius r and the point p
as its center. We vary r over an interval depending on the point
cloud size and density, and compute different discrete values for a point
feature, say the surface curvature estimation. We then select all the points
in the cloud, compute the mean and standard deviation of the feature
distribution, and select those points whose features are outside an interval
mean +/- (std * x). We do this for every r and at the end, select the
features which are persistent in subsequent increasing radii r.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
Combining several datasets into a global consistent model is usually
performed using a technique called registration.
The key idea is to identify corresponding points between the data sets and
find a transformation that minimizes the distance (alignment error) between
corresponding points.
This process is repeated, since correspondence search is affected by the
relative position and orientation of the data sets.
Once the alignment errors fall below a given threshold, the registration is said
to be complete.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
For transforming sets of 3D points into polygonal surfaces, we developed a
triangulation method using a projection based greedy approach, which
generates a mesh representing the surface on which the points lie. The
algorithm is fast, generating surfaces comprised of millions of points in
only a few seconds. The resulted mesh can be used for representing
semantically unlabeled obstacles in the semantic map as well as for
collision checking. The algorithm takes an unorganized point cloud as input
and does not require watertight objects nor 2.5D scans, thus it is ideal for
triangulating any type of point cloud dataset.
While varying point densities do not pose any difficulties for the
triangulation method, it is usually desired to perform a resampling step
before the reconstruction, so that point redundancy is decreased and the
resulted triangle meshes are smoother.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
The above flash video can be downloaded as XVID AVI here.
Within the scope of our research, we created methods for the acquisition of point cloud data (PCD) models, outlier removal, feature estimation, point cloud resampling,
registration, model fitting, segmentation, and many more. Most of these methods have already been described in the publications listed below, with the rest following
shortly.
Relevant publications
Radu Bogdan Rusu, Wim Meeussen, Sachin Chitta, and Michael Beetz.
Laser-based Perception for Door and Handle Identification.
In Proceedings of the International Conference on Advanced Robotics (ICAR), Munich, Germany, June 22-26 2009.Best paper award.
[PDF]
Zoltan Csaba Marton, Lucian Goron, Radu Bogdan Rusu, and Michael Beetz.
Reconstruction and Verification of 3D Object Models for Grasping.
In Proceedings of the 14th International Symposium on Robotics Research (ISRR), Lucernce, Switzerland, August 31 - September 3 2009.
Zoltan Csaba Marton, Radu Bogdan Rusu, Dominik Jain, Ulrich Klank, and Michael Beetz.
Probabilistic Categorization of Kitchen Objects in Table Settings with a Composite Sensor.
In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), St. Louis, MO, USA, October 11-15 2009.
Radu Bogdan Rusu, Andreas Holzbach, Nico Blodow, and Michael Beetz.
Fast Geometric Point Labeling using Conditional Random Fields.
In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), St. Louis, MO, USA, October 11-15 2009.
[PDF]
Radu Bogdan Rusu, Ioan Alexandru Sucan, Brian Gerkey, Sachin Chitta, Michael Beetz, and Lydia E. Kavraki.
Real-time Perception-Guided Motion Planning for a Personal Robot.
In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), St. Louis, MO, USA, October 11-15 2009.
[PDF]
Radu Bogdan Rusu, Zoltan Csaba Marton, Nico Blodow, Andreas Holzbach, and Michael Beetz.
Model-based and Learned Semantic Object Labeling in 3D Point Cloud Maps of Kitchen Environments.
In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), St. Louis, MO, USA, October 11-15 2009.
Radu Bogdan Rusu, Nico Blodow, Zoltan Csaba Marton, and Michael Beetz.
Close-range Scene Segmentation and Reconstruction of 3D Point Cloud Maps for Mobile Manipulation in Human Environments.
In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), St. Louis, MO, USA, October 11-15 2009.
[PDF]
Zoltan Csaba Marton, Radu Bogdan Rusu, and Michael Beetz.
On Fast Surface Reconstruction Methods for Large and Noisy Datasets.
In Proceedings of the International Conference on Robotics and Automation (ICRA), Kobe, Japan, May 12-17, 2009.
[PDF]
Radu Bogdan Rusu, Nico Blodow, and Michael Beetz.
Fast Point Feature Histograms (FPFH) for 3D Registration.
In Proceedings of the International Conference on Robotics and Automation (ICRA), Kobe, Japan, May 12-17, 2009.
[PDF]
Radu Bogdan Rusu, Zoltan Csaba Marton, Nico Blodow, and Michael Beetz.
Learning Informative Point Classes for the Acquisition of Object Model Maps.
In Proceedings of the 10th International Conference on Control, Automation, Robotics and Vision (ICARCV), Hanoi, Vietnam, December 17-20, 2008.
[PDF]
Radu Bogdan Rusu, Zoltan Csaba Marton, Nico Blodow, Mihai Emanuel Dolha, and Michael Beetz.
Functional Object Mapping of Kitchen Environments.
In Proceedings of the 21st IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Nice, France, September 22-26, 2008.
[PDF]
Radu Bogdan Rusu, Nico Blodow, Zoltan Csaba Marton, and Michael Beetz.
Aligning Point Cloud Views using Persistent Feature Histograms.
In Proceedings of the 21st IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Nice, France, September 22-26, 2008.
[PDF]
Radu Bogdan Rusu, Zoltan Csaba Marton, Nico Blodow, Mihai Dolha, and Michael Beetz.
Towards 3D Point Cloud Based Object Maps for Household Environments.
In Robotics and Autonomous Systems Journal (Special Issue on Semantic Knowledge).
[PDF]
Radu Bogdan Rusu, Zoltan Csaba Marton, Nico Blodow, and Michael Beetz.
Persistent Point Feature Histograms for 3D Point Clouds.
In Proceedings of the 10th International Conference on Intelligent Autonomous Systems (IAS-10), Baden-Baden, Germany, 2008.
[PDF]
Radu Bogdan Rusu, Nico Blodow, Zoltan-Csaba Marton, Alina Soos, and Michael Beetz.
Towards 3D Object Maps for Autonomous Household Robots.
In Proceedings of the 20th IEEE International Conference on Intelligent Robots and Systems (IROS), San Diego, CA, USA, Oct 29 - 2 Nov., 2007.
[PDF]
Computer Science IX | Technische Universität München