Department of Computer Science Technische Universitaet Muenchen
Home People Teaching Research Publications Info Sitemap
About | Research | Publications | Announcements

3D Semantic Mapping

The Plot

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.
Acquisition Acquisition Outlier Removal Curvature Estimation Normal Consistency Feature Persistence Histograms Resampling Resampling Registration Segmentation Reconstruction Model Fitting

The Producers

Principal investigator: Prof. Michael Beetz, PhD

The Cast

The current members of the team are:

The Script

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.

Individual chapters

imgPoint Cloud Data Acquisition
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:
  • B21 robot base, upgraded to AMD Athlon 64 X2 Dual Core 3800+;
  • Hokuyo URG-04 LX and SICK LMS-400 laser sensors mounted on the robot's end effectors;
  • Amtec Powercube 6-DOF arms;
  • Firewire stereo cameras, SICK LMS-200, ultrasonic rings, IR rings, etc (standard B21 hardware).

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.
imgSparse Outlier Removal
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.
imgNormal and Curvature Estimation
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.
imgNormal Consistency Propagation
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.
imgResampling
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.
imgFeature Persistence Analysis
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.
imgFeature Histograms
No content yet. Soon. Real soon.

The above flash video can be downloaded as XVID AVI here.

The above flash video can be downloaded as XVID AVI here.
imgRegistration
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.
imgSegmentation
No content yet. Soon. Real soon.

The above flash video can be downloaded as XVID AVI here.
imgSurface Reconstruction
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.
imgModel Fitting
No content yet. Soon. Real soon.

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