240
In this first step, the surface points in overlapping regions are pulled towards each other. The amount of
displacement and its direction are calculated using a modified Kalman minimum-variance estimator which
reduces the measurement error. After this, we still have two separate representations, which now have to
be merged by doing a retriangulation using a strictly local approach. The final description contains explicit
boundaries of the surface patches so that regions with no data are clearly identified. Figure 2a)-c) show an
example scene. [Rutishauser et al. 1994] give a detailed description of the merging algorithm.
3.3 Segmentation
The goal of segmentation is to partition the surface description of the whole scene into surface patch assemblies
(or surface regions) that hopefully have a one-to-one correspondence with objects in the scene. An object,
however, can consist of several “parts”. Usually, parts are isolated by cutting the description at surface discon-
tinuities, i.e., step-edges and areas with high concave curvature. A post-processing step will have to “reconnect”
parts to form objects.
The cutting is performed mainly in areas of high curvature. Curvature calculation is notoriously noise sensitive,
but due to the refinements to the data acquisition described earlier the signal-to-noise ratio is reduced to an
acceptable level. Vertices where one of the main curvatures exceeds a certain threshold are removed. This cuts
the surface into parts. After a connected component labeling of the remaining vertices, the part segmentation
is completed. (see Figure 2d) for an example).
(b) (c) (d)
Figure 2: Merging and segmentation of range images. (a) Surface seen by 1st sensor (b) Surface seen by 2nd sensor (c)
Result after merging (d) Result after segmentation, different gray values of the surfaces denote different "parts".
4 FINDING GRASPING OPPORTUNITIES
At this stage our representation of the scene consists of several surface regions. Each region is described by
a set of connected triangles, their corresponding vertices and at least one polygonal line which describes its
boundary. For the rest of the paper we assume that each such region corresponds to a single object in the scene.
This clearly can result in the generation of *phantom" objects, i.e., à single real object in the scene may give
rise to several smaller pieces in the description. This is especially true for highly textured objects where the
range sensors fail to produce reliable depth information. In these cases no large connected surface region will be
recognized. We intentionally allow this over-segmentation. This is because we have come to realize ever more
clearly that it is not necessary to insist on complete object recovery, but just to detect grasping opportunities
(for a gripper of a certain type) in the scene.
During grasping it would be desirable to have each finger of the robot touching the object and thus supporting
the grasp. For a two finger gripper this means that we have to find two suitable contact points on the surface.
We allow all vertices of a specific object to be candidate contact points. The problem of finding grasping
opportunities can therefore be formulated as finding a most suitable vertez pair. For one object, this process
has the complexity O(n?) where n is the number of vertices of this object's surface description.
Instead of calculating grasping points for all objects in the scene we first try to determine which object to remove
next. So we define a “region of interest”. This greatly reduces the computational cost involved in computing
grasping opportunities. Notice that this behavior can also be observed when a human is confronted with this
very same task. Most likely, he will not try to figure out all possible grasping positions for all the objects in
the scene, but merely consider a single object: namely the most appealing one. We believe that this appeal
IAPRS, Vol. 30, Part 5W1, ISPRS Intercommission Workshop "From Pixels to Sequences", Zurich, March 22-24 1 995
