IEEE Robotics & Automation Magazine - September 2013 - 53

p ! si

(2)

where z ^x, yh is the measured depth at ^x, yh, f j (x, y) is the
estimated depth value at ^x, yh, and n i is the number of points
in segment s i . The fitting error E j/i is defined accordingly.
The surface parameters have been estimated before, hence no
surface fitting has to be performed at this step. Then the
smaller error of E i/j and E j/i is selected, yielding e d .
Graph-Based Merging of Segments
The pairwise dissimilarities between segments are used to sort
the graph edges in an order of increasing dissimilarity. For this
purpose, we define a label l enumerating the edges in an
ascending order. The total number of edges is n . We further
define a merging threshold d merge, which in our case should
be chosen in the range of 1-5 cm 2 to be proportional to the
expected range of target-fitting errors in the given scenario.
The surface models of all graph nodes or segments are stored
in a list because they may be updated during the procedure.
The algorithm then proceeds as follows.
1) We select the first edge of the ordered list labeled l = 1.
2) The two segments linked by the edge labeled l are merged, if
the edge dissimilarity e d (l) < d merge . In this case, a new
region s i , j is created and the respective surface model
fi , j is found. The surface models of region s i and s j are
replaced by the new surface model fi , j . A flag is set indicating whether the surface model of a segment has been
updated or not. If e d (l) F d merge, nothing needs to be done.
3) We select the next edge of the ordered list labeled
l = l + 1. If one of the segments linked by the respective
edge has been updated previously and thus flagged, the
edge dissimilarity between the segments is recomputed
using the current surface models.

Image Acquisition
Infrared-Intensity
Segmentation
Segment Selection

/ 6 f j (x, y) - z (x, y)@2,

Segment Graph
Construction

E i/j = 1/n i

Graph-Based
Clustering

Segment Dissimilarity
We define a dissimilarity measure e d between two segments
s i and s j by estimating how well the surface model of segment
s i describes the depth data of segment s j, and vice versa. Let
fi be the surface model of segment s i, and f j, the surface
model of segment s j . Then, we compute the fitting error

4) Steps 2 and 3 are repeated until l = n.
Working consecutively along the ordered list and updating
the surface models along the way allows us to avoid testing for
all possible merging combinations, which otherwise could
lead to a combinatorial explosion. This strategy gives preference to the merges of segments with large similarity. The
method is related to Kruskal's algorithm for finding the minimum spanning tree of a graph, except that certain graph
edges have to be updated after each merge.

Identification of Grasping
Points Using Leaf Models

Segment Graph
A nearest-neighbor graph is constructed from the image segments. For each image segment, the boundary points are
extracted and the local neighborhood within a radius of 1 px
of each point is searched for points belonging to other
segments that lie within a predefined absolute depth distance. For computing the depth distance, the fitted depth
derived for the respective segment point is used, i.e.,
fi (x i, y i) - f j (x j, y j) , where i and j denote neighboring pixels belonging to different segments respectively. Two segments are considered neighbors if the respective boundary
points are less than d 3D = 1 cm apart. The segments define
the nodes V of the segment graph ^V, eh . An edge e exists
between two segments if they are neighbors according to the
condition given above.

Intensity (PMD)

Level 0

Depth (PMD)

Level 1

Level 2

Selected Segments

Segment Graph

Final Segments

Fitted Depth +
Segment Boundaries

0.6
0.5
0.4
0.3
1
0.2
0.1
0
Segment Validity +
Identified Grasp Point

Figure 3. The schematic of the leaf-extraction algorithm. ToF
data (depth and infrared intensity) is acquired and the infraredintensity image is segmented at different resolutions (levels
0-2). The surface models are fitted to the segments and those
segments along the segmentation hierarchy that fit the depth
data best are selected. From the selected segments, a segment
graph is constructed and a graph-based segment merging
procedure is employed. Final segment contours are fitted to
predefined model contours, and grasping points are determined.

september 2013

IEEE ROBOTICS & AUTOMATION MAGAZINE

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - September 2013