IEEE Robotics & Automation Magazine - June 2011 - 28

that voted for the location. Some of these parts are incorrect, but their weights are low.
Our task is now to select the model and its pose from a
3-D model database that explains most of the detected
object parts. We employ a more detailed model database
for this to be able to account for the variations in shapes
and sizes of the different objects. To fit these models to our
3-D scans robustly and efficiently, we transform them to
noiseless point clouds by filling the outer triangle faces
with points and use a RANSAC-based algorithm to select
the best pose and the best model for each detected object.
Since we take the complete model into account at once
instead of each view sep* arately, we can reduce the
number of trials considWe use training examples
erably, and we do not
require the point cloud to
that are similar, but not
come from a single scan.
necessarily the same as the The search time is further
reduced by assuming that
objects encountered during objects are upright; thus,
only the location in 2-D
and the rotation around
the operation of the robot.
the up axis is required to
* be found.
In a regular RANSAC
algorithm, one can estimate the number of required iterations T to find the best model with probability psuccess as
1 À psuccess ¼ (1 À pgood )T ) T ¼

log (1 À psuccess )
: (7)
log (1 À pgood )

The value of pgood ¼ wn is the probability of randomly
selecting the best model and can be estimated after each fit
(that is better than the best one found so far) as the probability w of selecting a good sample to the power of the
number of samples n. As the algorithm finds models that
are increasingly better, the value of w can be updated as
#inliers=#points, resulting in a decrease in the number of
iterations needed. Thus, the number of iterations adapts to
the estimated number of matches, starting at infinity when
no inliers are known and decreasing to a number that
ensures that the chance of finding a better model than the
current one drops below 1 À psuccess .
As the run time depends on the number of samples, it is
advisable to keep it as low as possible. If we were to pick both
the model and the scan points at random, we would have
used pgood ¼ (#correct matches=#possible matches)2 a very
small number that is also hard to estimate. However, if we
assume that by selecting a random point from the scan we can
find the corresponding model point. This simplifies the equation to pgood ¼ #covered scan points=#all scan points. The
number of covered scan points can be found by nearest
neighbor searches with a maximum distance in a search tree.
We found that selecting the corresponding model point
to a scan point can be done by iterating over the possible
28

IEEE ROBOTICS & AUTOMATION MAGAZINE

JUNE 2011

matches (points at similar height), and selecting the one
that would result in a transformation that covers most scan
points. Significant speedups can be achieved by selecting
only a subset of the possible correspondences and scan
points. Our experiments provided good results with
around 50 % of the points checked. Additionally, by keeping track of the best score found, subsequent searches can
be stopped early if it becomes clear that they can not
produce better scores. The same principle can be applied
over multiple models as well.
Using these techniques, we were able to identify the best
pose of the good model in around 15 s on a standard dualcore laptop, without parallelization or other optimizations.
Our models contain between 5,000 and 15,000 points,
while the identified object parts around 2,500. For nonoptimally matching models, the verification takes around
60 s, while nonmatching models are rejected in under a
second. After each object model from the identified category is fitted to the object parts, we select the one that
explains the most model points.
Before this model and its pose can be used for various
applications, it first needs to be checked to filter out false
positives. We first check if the model covers less than
50 % of the points of the parts and reject such detections
(e.g., the chair in column two of Figure 5). The threshold
of 50 % is tied to how well the CAD models and the real
objects match. The real chair and the best-fitting model
are not identical; however, all CAD models we used
cover much more than 50 % of the points if a good
match is found.
We then check if the identified pose contradicts the
measurements, i.e., if it has faces that should have been
visible while scanning, but the laser returned points behind
them. This can be done efficiently by building one occupancy grid per scan, in which each voxel is labeled as free,
occupied, or unknown [33]. Such a grid is needed for the
operation of the robot for tasks like collision avoidance
and path planning. Thus, it is natural to use it for the verification of model-fittings attempts, as we did in our experiments involving smaller objects as well [20]. We reject
models that have large parts in free space, e.g., the sideboard in the first column of Figure 5.
Finally, when the scan point has a normal vector, which
is close to being parallel to the upright axis, the rotation of
the model cannot be accurately estimated. In these cases, we
use a random rotation, and since we check a high percentage
of points, the models are correctly identified. Tables are
especially affected by this, and we see larger fitting errors in
finding them, but the best models get identified correctly
and a subsequent fine registration using ICP [34] or one of
its many variants can be used to correct the pose.
Experiments
The goal of the experiments is to demonstrate that a robot
can learn models for 3-D office objects found on the Web
and, using these models, is able to locate and categorize

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - June 2011