Hierarchical Object Discovery and Dense Modelling From Motion Cues in RGB-D Video

1 Introduction

Motion is an important cue in object perception. While many static cues such as color or shape can be used to generate object hypotheses, common motion is a further fundamental grouping cue that is especially useful for active perception by robots. For novel, previously unseen objects, motion provides a clear segmentation hint for the constituent parts of an object. Some approaches to the unsupervised learning of object models have been proposed in the robotics community that exploit motion (e.g., [Fitzpatrick, 2003; Kenney et al., 2009; Sturm et al., 2011; Katz et al., 2012; Herbst et al., 2011]). In this paper, we propose a novel approach that simultaneously segments motion in image sequences, and builds dense 3D models of the moving segments. Our approach also reasons on the hierarchy of object parts on-the-fly.

We segment motion between images densely within an expectation-maximization framework using an efficient registration method for RGB-D images. This motion segmentation approach is integrated in a simultaneous localization and mapping framework to incrementally build maps of moving objects and the background. In this process of simultaneous motion segmentation, localization, and mapping (SMOSLAM), we incrementally extract key views and segment motion in these views. From the motion segments, we generate objects, optimize poses of partial views onto the objects, and deduce a hierarchy of object parts from the relations of the motion segments throughout the sequence.

We demonstrate in experiments that our approach is capable of finding moving objects, aligns partial views on the objects, and infers hierarchical relations between the objects.

2 RelatedWork

Bottom-up cues for single-image segmentation such as texture [Cremers et al., 2007; Delong et al., 2012] or 3Dshape [Holz and Behnke, 2012; Silberman et al., 2012] often do not suffice to find segment borders that coincide with the boundaries of objects. Thus, they are frequently combined with top-down cues to integrate spatial and semantic context (e.g., [Carreira and Sminchisescu, 2012]). Motion is a further important bottom-up cue that can be utilized in image sequences. In contrast to texture and shape, common motion provides unambiguous segmentation hints for the constituent parts of a rigid object.

Many approaches to motion segmentation employ point features in multi-body structure-from-motion [Zelnik-Manor et al., 2006; Gruber and Weiss, 2004; Schindler and Suter, 2006; Rothganger et al., 2007; Agrawal et al., 2005; Ross et al., 2010; Katz et al., 2012], but these methods do not provide a dense segmentation of objects like ours. Several dense methods [Cremers and Soatto, 2005; Unger et al., 2012; Kumar et al., 2005; Ayvaci and Soatto, 2009; Zhang et al., 2011; Wang et al., 2012; Roussos et al., 2012] have been proposed that demonstrate impressive results. These methods are, however, either computationally demanding and yet far from realtime performance, or they do not extract segments with common 3D rigid-body motion. Our motion segmentation approach makes use of dense depth available in RGB-D images to retrieve 3D rigid-body motion segments efficiently. We also take motion segmentation a step further by integrating it with simultaneous localization and mapping (SLAM) and deducing the hierarchical relations between the moving parts.

The mapping of static as well as dynamic parts of environments is an actively researched topic in the robotics community. Early work focused on 2D mapping using laser scanners. Anguelov et al. [2002] learned templates and object classes of non-stationary parts of an environment in a twolevel hierarchical model. Haehnel et al. [2003] proposed an EM algorithm that filters dynamic parts of the environment in order to make the 2D occupancy mapping of the static environment parts robust. They then extract 3D models of the dynamic parts by stitching the laser measurements. In simultaneous localization mapping and moving object tracking (SLAMMOT, [Wang et al., 2004]), dynamic objects are segmented in 2D laser scans through distance comparisons, and subsequently tracked while concurrently mapping the environment statics in a SLAM framework. We integrate 3D motion segmentation in a SLAM framework that also reasons about hierarchical relations between object parts. Van de Ven et al. [2010] recently proposed a graphical model that integrates CRF-matching [Ramos et al., 2007] and CRFclustering [Tipaldi and Ramos, 2009] within a single framework for 2D scan-matching, moving object detection, and motion estimation. They infer associations, motion segmentation, and 2D rigid-body motion through inference in the model using max-product loopy belief propagation. We formulate dense 3D motion segmentation of RGB-D images using efficient expectation-maximization and perform fast approximate inference of the motion segmentation using graph cuts.

3 Multi-ViewMotion Segmentation

We assume that an image I is partitioned into a set of discrete sites S = {si}Ni=1 such as pixels or map elements in a 3D representation (see Fig. 1). Let L = {li}Ni=1 be the labelling of the image sites. The labels denote the membership in distinct motion segments M = {mk}Mk=1 . All sites within a segment move with a common six degree of freedom (6-DoF) rigidbody motion θk between the image Iseg to be segmented and a reference image Iref .

Our goal is to explain the segmented image by the rigidbody motion of segments into the reference image, i. e., we seek rigid-body motions Θ = (θ1, . . . , θM) that maximize the observation likelihood of the segmented image in the reference image:

The labelling of the image sites is a latent variable that we estimate with the rigid-body motions of the segments using an expectation-maximization (EM) algorithm,

where Θ is the recent motion estimate of the segments from the previous iteration of the EM algorithm.

We model the likelihood of the labelling in a conditional random field

that incorporates the likelihood of the labelling given the observations zi at each site and the label's corresponding motion estimate. Pairwise interaction terms between direct neighbors in the image representation enforce spatial coherence within motion segments using a contrast-sensitive Potts model p(li, lj | Iseg) = γ(si, sj) δ(li, lj), where

and γ(si, sj) measures the dissimilarity of the image sites.

It is, however, intractable to compute the joint image labelling posterior exactly. Instead, we approximate it through the maximum likelihood labelling LML, given the motion estimates Θ. We find this labelling using efficient graph-cut optimization [Boykov et al., 2001]

Given this labelling, we determine the pseudo-likelihood of a site label li:

where η normalizes the probability over label values of li.

3.1 Resolving Ambiguous Data Associations

The image site labellings decide for an association of sites between both images. In order to prevent the graph-cut optimization from establishing labellings that would associate multiple times to a site in the reference image, we introduce additional pair-wise couplings. For sites i and j in the segmented image that map to the same site in the reference image for different motion segments k and k′ , repectively, we additionally model the pair-wise labelling log likelihood

where α sets the strength of the couplings.

3.2 Model Complexity

The pair-wise interaction terms prefer large motion segments and naturally control the number of segments to be small. In the case that a single 3D motion segment appears as multiple unconnected image segments in the image, our approach may still use different but redundant motion segments for the image segments. Furthermore, it may not be desirable to set the number of motion segments in advance. We thus adapt the number of motion segments to the data similar to the approach in [van de Ven et al., 2010].

We initialize the EM algorithm with a guess of the number of motion segments (M = 1 in our experiments). While this guess influences the number of required iterations, we found that it has only little effect on finding the correct number of segments. Initially, we label all sites to belong to the first segment. All sites in segments that are yet unsupported in the image are assigned the outlier data likelihood pO. By this, our EM algorithm prefers to explain sites that misalign with the already existing segments with new motion segments. We define a motion segment to be supported if it labels sites in the image and reject very small segments as outliers.

To let our approach possibly increase the number of segments, we append one additional, yet unsupported segment before the M-step. After the E-step, we reduce the number of motion segments in two ways. We discard unsupported segments (eventually also the additional segment) and merge redundant segments. We measure the redundancy of a segment k using the average effective number of segments of the image sites

within the segment [van de Ven et al., 2010]. It takes the average over the effective number of segments that the image sites within the segment are matching, i.e.,

Ideally, the image sites labelled as belonging to a motion segment are mainly explained by the segment and, hence, Neff (k) ≈ 1. We classify a motion segment k to be redundant, if Neff (k) is larger than a threshold (set to 1.8 in our experiments), and subsequently merge it with the most similar segment.

3.3 Segmentation Towards Multiple Reference Images

Our formulation supports the segmentation of an image in reference to multiple other images Iref = {Iref,r}Rr=1 which allows to include motion hints from multiple perspectives into the segmentation of an image. Each motion segment in Iseg then moves with a rigid-body motion θrk to the reference image Iref,r. We denote the set of motions towards one reference image r by θr . We may either optimize the segmentation for all reference images concurrently, i. e.,

or we may only estimate the motion estimate towards a specific reference image r while keeping the motion estimates of the other images fixed, i. e.,

In both cases, the label likelihood given the observations at a site is the product of the observation likelihoods in the individual reference images,

To keep the data term in balance with the pairwise interaction terms, we normalize the combined observation likelihood to the effect of a single image using α := 1/R.

3.4 Image Representation

In principle, any image representation is suitable for our motion segmentation method that defines data likelihood p(zi | θli , Iref ), image site neighborhood N(i), and dissimilarity γ(si, sj) for the pair-wise interaction terms. To solve for the motion estimates of the segments in Eq. (2), an image registration technique is required that allows to incorporate individual weights for the image sites.

Instead of labelling the RGB-D image pixel-wise, we choose to represent the image content in a multi-resolution 3D representation to gain efficiency. These multi-resolution surfel maps [St¨uckler and Behnke, 2012] respect the noise characteristics of the sensor, provide a probabilistic representation of the data, and support efficient registration of motion segments. They store the joint color and shape statistics of points within 3D voxels at multiple resolutions in an octree. The maximum resolution at a point is limited proportional to its squared distance in order to capture the disparitydependent noise of the RGB-D camera. In effect, the map exhibits a local multi-resolution structure which well reflects the accuracy of the measurements and compresses the image from 640×480 pixels into only a few thousand voxels. RGB-D images can be efficiently mapped into this representation and registered. We use an open-source implementation of multi-resolution surfel maps. 1

Observation Likelihood

Each voxel si in a multi-resolution surfel map contains a surfel observation zi specified by mean and covariance of the points falling into the voxel. The observation likelihood of a site sseg,i given label li = k and reference image Iref is the matching likelihood of the surfel zseg,i under the rigid-body motion θk for the labelling,

where T(θk) is the transformation matrix for the pose estimate θk and R(θk) is its rotation matrix. We only use the spatial components of the surfels.

Spatial Coupling and Local Dissimilarity Measure

Each voxel in the map is connected to its eight direct neighbors in the 3D grid. In addition, we connect each voxel to its parent and childs. For the contrast-sensitive Potts model in Eq. (4), we measure local dissimilarity through γ(si, sj) := 1 -min(1,max(ξ(si), ξ(sj))), where ξ(s) is a linear combination of the principal shape curvature [Pauly et al., 2003] and the trace of the color covariance within voxel s.

Motion Estimation

In order to maximize our EM objective function for the individual motion segments k, we augment our registration approach [St¨uckler and Behnke, 2012] with the weighting through the label likelihoods, i.e.,

Exemplary label likelihoods in two motion segments are visualized in Fig. 1.

Border and Occlusion Handling

Special care needs to be taken at image borders, background at depth discontinuities, and occlusions. We assign the last observed data likelihood to map nodes at such borders and occlusions.

4 Hierarchical Object Modelling through Simultaneous Motion Segmentation, Localization, andMapping

We extend our view-based SLAM approach [St¨uckler and Behnke, 2012] towards simultaneous motion segmentation, localization, and mapping (SMOSLAM) of objects O =

1 http://code.google.com/p/mrsmap/

{oi}Oi=1 . For each object, we maintain a graph of view poses for those key views that contain the object. The view poses are connected through edges that represent spatial relations which we estimate through motion segmentation between the key views. The poses of the pose graphs are optimized using the g2o graph optimization framework [Kuemmerle et al., 2011].

Not all objects may be visible in a single key view, or objects may split into sub-parts between different key views. This property enables us to learn part-of relations between the objects in a hierarchical object map. We infer these relations from the overlap of motion segments between key views.

We perform SMOSLAM incrementally, working sequentially on the images in a RGB-D video sequence. The current image is segmented towards the latest key view in the map in order to track the relative motion of the camera towards the objects in the reference key view. If one of the objects moved a specific distance or angle, we generate a new key view and resume tracking towards this view. We initialize the motion segmentation of the new key view with the segmentation of the previous one, and add the previous key view as a reference image to the segmentation. By this, the segmentation of the previous key view acts as a regularizing prior while the segmentation is further optimized with respect to the current image. Most importantly, we associate the motion segments of the previous key view with the object SLAM graph to discover object relations.

4.1 Discovering Objects and Hierarchical Relations

We analyze relations of motion segments between key views to associate motion segments with objects and to infer hierarchical relations between objects. We quantify the image overlap of the motion segments to set equivalence and partof relations between segments, i.e., we define a motion segment m to be part of another segment m′ , if m overlaps m′ at least by some threshold (e.g., set to 80% in our experiments) within the image:

The segments are defined equivalent, if both segments overlap each other significantly:

From these relations, we infer new objects, or equivalence and part-of relations of motion segments towards existing objects. If a motion segment m in a key view is equivalent part of an object o, i. e., equivalent(m, o), all motion segments m′ that are equivalent to m are also equivalent part of o:

Analogeously, for all motion segments m that are part of an object o, motion segments m′ from other key views in part-of relations to m are also contained in the same object,

Amotion segment that is not equivalent part of an object creates a new part. It is then equivalent part of the new object. For each pair of key views for which motion segments are part of the same object, we create an edge between the key views in the SLAM graph of the object.

Finally, we deduce hierarchical relations between objects from the relations between key views and objects. An object o is contained within another object o′ , if a motion segment m exists in a key view for which this segment is equivalent to the contained object o, but only part of the containing object o′ :

Isolated smallest objects have no further parts.

5 Results

We demonstrate our approach in three RGB-D image sequences that contain 30 images per second at VGA (640×480) resolution. Note that our current implementation does not process the sequences in real-time, but achieves about 80 to 800msec per frame on a notebook PC with an Intel Core i7 3610QM 2.3GHz (max. 3.3GHz) QuadCore CPU. The first sequence shows two moving chairs from a static camera position (see Fig. 2). In the second sequence, a drawer of a container at a fixed position is opened while the camera is moving (see Fig. 3). The third sequence involves the same container which is now first moved before it is opened (Fig. 4). Since ground truth motion estimates are not available, we visualize resulting segmentations of key views, object relation graphs, and object SLAM graphs for the sequences.

5.1 Chairs Sequence

In the first sequence, two chairs are moved in the horizontal plane and rotated around the vertical axis while the camera is static. Both chairs move separately, starting with the rightmost chair (see Fig. 2).

We first demonstrate the performance of our dense motion segmentation approach. We compare the resulting labelling with a manual ground truth image through σ = true positives/(true pos. + false pos. + false neg.) as a measure of segmentation accuracy [Everingham et al., 2010]. The initial key view is sequentially segmented in reference to the images in the sequence, performing one iteration of our EM algorithm per frame. We project the 3D segmentation into the image to compare the image segmentation with the ground truth labelling, and associate each found segment to the ground truth segment with best overlap. The results in Fig. 5 show that our approach is well capable of segmenting the moving objects with high accuracy. The segmentation accuracy of the chairs rapidly reaches high values when the objects start to move. Note that due to sensor noise, occlusions, and parts of the objects leaving the field-of-view, the achievable segmentation accuracy is limited. This is handled through motion segmentation of key views towards both preceding and subsequent key views in our SMOSLAM approach.

Fig. 2 shows the key views extracted by our approach and the estimated motion segmentation of the views. The segments correspond well to the actual objects in the images. The objects and the poses of the key views in the object SLAM graphs are shown in Fig. 7. The trajectory of the camera with respect to the objects has been well recovered, such that the corresponding motion segments of the objects accurately align. Both chairs and the background segment are smallest parts in the object hierarchy. Since between the first two key views and their neighbors, the left chair does not move, left chair and background are found within a single segment. The object relation graph reflects the containment of both parts (left chair and background segment) within this combined object, which is inferred through the split of the segment in the third key view. Similar arguments apply for the left chair and the background in the last two key views.

5.2 Static Container Sequence

In the second sequence, a drawer is moved open by a person, while the container is kept fixed and the camera is slowly moved. Our algorithm succeeds in segmenting the drawer with good accuracy (see Fig. 3). From the object SLAM graphs it can be seen that the relative pose of the camera towards the objects is recovered and the motion segments accurately overlap for the estimated key view poses. Remarkably, the drawer segment makes the inside of the container explicit.

5.3 Moving Container Sequence

In the third sequence, our algorithm partially succeeds in segmenting the container from the background (see Fig. 4). Since the container moves parallel to the ground plane, our approach cannot well distinguish if the ground plane itself is moving or not. As a consequence, the drawer is part of the object combined from container, drawer, and background. The wall part is found twice, since it is not detected in the second key view.

6 Conclusions

In this paper, we introduced a novel method for learning object maps with hierarchical part relations from motion cues. Motion segmentation between RGB-D key views finds the rigid parts in images and estimates their motion. It is based on an efficient expectation-maximization algorithm and employs a compact local multi-resolution 3D representation of RGB-D images to process images efficiently.

We integrate our motion segmentation method with SLAM into a framework for simultaneous motion segmentation, localization, and mapping. Our mapping approach extracts moving objects from key views and aligns the parts by optimizing a graph of spatial relations. From the overlap of motion segments, we deduce a hierarchy of object parts.

In experiments, we demonstrated that our approach is capable of extracting motion segments and aligning multiple views on objects. In each of the sequences, our approach deduces hierarchical object relations.

The robustness and accuracy of our motion estimates and segmentation strongly depend on the underlying registration method. We currently work on including point features into the registration to further improve the range of applications of our approach. This would allow for tracking smaller objects, or reduce aperture problems along planar surfaces. One limitation of our method is that we currently only establish relations between segments in temporal sequence. In future work, we will also establish equivalence and part-of relations between parts that interrupt their motion. The robustness of our approach could further be increased by reasoning on the uncertainty of segmentation decisions and hierarchical relations. Our overlap measure between segments could be enhanced by tracking correspondences through time between key views. In order to scale our approach to larger scenes, graph pruning and map merging needs to be incorporated. We also plan to extract articulation models from the hierarchical object relations and the relative object trajectories. Finally, we will pursue the application of our approach for interactive perception of objects by robots.