3D point cloud video segmentation based on interaction analysis

3D Point Cloud Video Segmentation Based on Interaction Analysis Xiao Lin, Josep R.Casas and Montse Pard`as Image Processing Group, Technical University of Catalonia (UPC) [email protected] Abstract. Given the widespread availability of point cloud data from consumer depth sensors, 3D segmentation becomes a promising building block for high level applications such as scene understanding and interaction analysis. It benefits from the richer information contained in actual world 3D data compared to apparent (projected) data in 2D images. This also implies that the classical color segmentation challenges have recently shifted to RGBD data, whereas new emerging challenges are added as the depth information is usually noisy, sparse and unorganized. In this paper, we present a novel segmentation approach for 3D point cloud video based on low level features and oriented to the analysis of object interactions. A hierarchical representation of the input point cloud is proposed to efficiently segment point clouds at the finer level, and to temporally establish the correspondence between segments while dynamically managing the object split and merge at the coarser level. Experiments illustrate promising results for our approach and its potential application in object interaction analysis. . . . Keywords: object segmentation, 3D point clouds, dynamic split and merge management, object interactions 1 Introduction Segmentation is an essential task in computer vision. It usually serves as the foundation for solving higher level problems such as object recognition, interaction analysis and scene understanding. Traditionally, segmentation is defined as a process of grouping homogeneous pixels into multiple segments on a single image, which is also known as low level segmentation. The obtained segments are somehow more homogeneous and more perceptually meaningful than raw pixels. Based on that, the concept of semantic segmentation/labeling is proposed. It is devoted to segment an image into regions which ideally correspond to meaningful objects in the scene. To achieve this goal, high level knowledge is usually incorporated into the segmentation process, such as object models [2] exploited in constrained scenes, accurate object annotations required in the initialization [12, 16] and large databases containing fully annotated data in, for instance, label transfer approaches such as [9]. These approaches yield outstanding segmentation results; however, most computer vision applications involve large amounts 2 X. Lin, J.R. Casas and M. Pard`as of data with different types of scenes containing several objects, which difficult the adaptation to generic scenes of those methods based on manual initialization or predefined/learned object models. To generalize the methodology from constrained situations, larger attention has been drawn on investigating the spatial relation between segments and their temporal correspondences when temporal video (stream) data is available. A bunch of methods focusing on the spatio-temporal relation between segments are proposed [4, 15, 3, 5, 6, 1]. These methods mainly focus on tackling two problems: a higher level representation, which abstracts the raw data from scratch, and a method to establish the spatio-temporal correspondences. Several methods employ a generic model to represent the objects in the scene. Husain et al. [6] maintains a quadratic surface model to generally represent the object segments in the scene. The model is then updated along the sequence to obtain the final segmentation result. But it is difficult to handle objects with large displacement in successive frames. Similarly, a Gaussian Mixture Model (GMM) is used in [8] to represent the objects, while the model is incrementally updated for new frames in the sequence. However, it establishes the correspondence between the object model and the point cloud in the new frame by using the Iterative Closest Point (ICP) technique, which may lead to the accumulation of registration errors in the object model due to the deformation of the objects. More generally in scene representation, Richtsfeld et al. [13] propose to represent the 3D point cloud with a graph of surface patches detected in the scene, such as planes and non-uniform rational B-splines (NURBs). A SVM based learning process is then employed to decide the relation between surface patches for a sub-sequent graph cut segmentation. Grundmann et al. [3] use a graph-based model to hierarchically construct a consistent video segmentation from over-segmented frames. Similarly, Hickson et al. [5] extend the method to RGBD stream data. But the over-segmentation for each frame in these two approaches is still calculated independently, without the temporal coherence constraint, which may lead to a temporal inconsistency problem due to changes of corresponding over-segments in different frames. Abramov et al. [1] perform label transfer in the pixel level between frames by using optical flow. Then, they minimize the label distribution energy in the Potts model to generate labels for objects in the scene. This establishes the temporal correspondences in the pixel level, which makes the approach highly rely on the performance of optical flow estimation. Motivated by the problems mentioned above, we propose a segmentation algorithm based on the definition of objects as ”compact point clouds” in the 3D-space plus time domain. However, point clouds corresponding to an object can break into different compact sub-clouds due to occlusions, or can merge with compact point clouds corresponding to other objects, producing a single compact point cloud, when they become spatially close (object interaction). Our system aims to produce a robust spatio-temporal segmentation of the point clouds by analyzing their connectivity to define the objects according to the evidence observed up to a given temporal point. Our primary contributions are: 3D Point Cloud Video Segmentation Based on Interaction Analysis 3 –We propose a novel tree structure representation for the point cloud of the scene which allows us to temporally update the similarities between nodes in the tree –We propose to approach the temporal correspondences establishment task by a labelling assignment problem regarding the tree structure. –A dynamic management of object splits and merges is exploited in our approach for generating a better segmentation result based on all low-level features available –An over-segmentation method based on the compactness of the connection between neighboring super voxels in the graph is proposed. The rest of the paper is organized as follow. In section 2 we explain how the 3D point cloud segmentation problem is modeled. Sections 3 and 4, present the framework of the proposed segmentation approach and show experimental results, respectively. Finally, section 5 discusses the results and yields conclusions. 2 Problem modeling and definition In this section, we explain how the 3D point cloud segmentation task is modeled by the proposed tree structure. 2.1 Tree structure representation of the point cloud Given a stream of RGBD data, our goal is to segment the foreground point cloud in each frame into meaningful sub-clouds and associate these sub-clouds in consecutive frames to maintain the trajectories for them without explicit object models or accurate initialization. More precisely, we represent the input point cloud as a graph G(shown in Fig.1(b)) with a super-voxel approach [10]. Nodes in the graph are homogeneous sub-cloud patches and edges define the spatial connections among patches. In this manner, the connectivity of a point cloud is interpreted as the connectivity in the corresponding graph representation. The set of connected nodes in the graph corresponds to the compact parts of the input point cloud, which we call blobs (shown in Fig.1(c) and marked in different colors). Then a tree structure with 4 levels varying from coarse to fine is exploited to represent the input point cloud at different scales of objectconnectivity. Fig.1(a) shows the constructed tree structure for the point cloud data in the second row. The root of the tree represents the scene. The second level of the tree is the object level, in which each node stands for an object proposal. The next level, named component level, is employed to handle potential splits and merges of point clouds representing these objects. An object is represented by more than one component if it splits in different blobs in the graph. Components from different objects can be part of the same blob, because of the interactions between objects. Splits and merges of components are managed by maintaining the similarities among object components along time, which provides a temporally coherent way to obtain object proposals based on point cloud 4 X. Lin, J.R. Casas and M. Pard`as A B A Object Level Component Level A root component object A1 B1 A1 A2 Over-Segmentation A1 similarity similarity B A A A B2 B1 A1 A1 A1 A2 Scene Level Level B2 Blob (a) (b) (c) (d) (e) Fig. 1. An example of tree structure representation. (a) A tree structure representation of the input point cloud data. (b) The graph built on the input point cloud. (c) Blobs in the input point cloud. (d) Components for each object. (e) Objects segmentation obtained from the tree structure. connectivity. The final level of the tree is the over-segmentation level. We oversegment components using normalised cut in their graphs in order to correctly establish correspondences between trees along time and update its structure, that is, the temporal coherent assignment of labels to the segmented objects. Note that three kinds of labels are used in Fig.1(a) to differentiate the nodes in the tree while showing their relationships, which are object label (color), component label (alphabet) and segment label (number). We aligned the color used in Fig.1(a) with the real point cloud data plots (Fig.1(c) and Fig.1(e)). In Fig.1(e), we present the object segmentation result obtained in this tree structure, while Fig.1(d) shows the components of each object from the point cloud view. Fig.1(c) presents the blobs in the input point cloud which is related to the ellipses marked with the same color in Fig.1(a). 2.2 Tree structure creation Taking the point cloud in frame tas input data, we abstract it with super voxels, using the method proposed in [10]. The graph representation simplifies the input data by grouping homogeneous points on the point cloud into super voxels while preserving the boundary information. Then, a graph Gis constructed regarding the spatial connectivity between super voxels. We group the point cloud into blobs by detecting the connected components in the graph. The tree in the first 3D Point Cloud Video Segmentation Based on Interaction Analysis 5 B A A A frame t-1 frame t ? (a) A A frame t-1 B1 B2 frame t A (b) Fig. 2. An example of temporal inconsistency problem. (a) The problem when establishing the correspondence between components in the previous frame and blobs in the current frame. (b) Using the segments instead of components solves this problem. frame is created by simply taking the detected blobs as the objects, as no prior information about the objects is provided. Accordingly, we create one component for each object and over-segment each component into segments. Apart from the first frame, the tree is built in a bottom-up way, starting at the component level. First, a correspondence is made between the connected components of the graph (blobs) in the current frame and the segments at the over-segmentation level of the tree structure in the previous frame. This over-segmentation level is employed to avoid temporal inconsistency problem. Fig.2(a) shows an example of it, where the component B of the blue object in frame t−1 splits into two blobs in frame t. In this case, no correct association is found between components and blobs. The problem may be tackled by over-segmenting the component Bof the blue object into segments B1 and B2 (shown in Fig.2(b)) and associating the segments in frame t−1 with blobs in frame t. Establishing the correspondence between the blob labels and the segments is a problem of assigning Mbblob labels to Mssegments. This is a nonlinear integer programming problem which is solved using a Genetic Algorithm to minimize an energy function which is composed of three terms: one for representing the appearance changes Ea, one for the displacements Edand the other one Eofor the penalty when objects move out of the scene. A further segmentation is needed when segments that correspond to different objects in the previous frame are assigned to the same blob. A restricted graph cut method is employed to segment the graph of the blob by minimizing a segmentation energy function, in which we consider the degree that a graph cut fits the current data while being coherent with the minimum cut in the previous frame. Once the current segmentation is done, the components and objects in the current tree are created initially from it regarding the previous tree structure. To dynamically manage object splits and merges along time, we maintain similarities between nodes at the component and object level respectively and update the tree based on it. The component similarities are measured among components which belong to the same object while the object similarities are measured among objects. These similarities are computed considering spatial distance and apprearance difference, which reveal the likelihood of object splits and merges. 6 X. Lin, J.R. Casas and M. Pard`as We accumulate them along time by averaging the current similarity and the previous accumulated similarity regarding the established correspondences. Then object splits and merges are confirmed by thresholding the accumulated similarities. Finally, an over-segmentation is performed at the component level to generate segments for correctly establishing the correspondence to the next frame. Specifically, a normalized cut is performed in the graph representing the component iteratively until the cut cost is larger than a threshold. 3 Graph based dynamic 3D point cloud segmentation In this section, we present the frame work of the proposed approach including data acquisition and initialization, temporal correspondences establishment and segmentation, the proposed dynamic management of object splits and merges mechanism and the over-segmentation method. 3.1 Data acquisition and initialization We can transform the per-pixel distances provided in an RGBD image into a 3D point cloud CI⊆R3using camera parameters. We focus on the interest area of the foreground cloud Cfg ⊆R3in 3D space. Taking the foreground point cloud at frame tas input data, a graph representation is constructed f(Cfg)→G(v, e) via a graph building method f, where vis the set of vertices or nodes and ethe edges of the graph. The super voxel method introduced in [10] is employed as the graph building method fin our approach. It aggregates points on the point cloud into homogeneous sub-cloud patches (super voxels) with respect to the point proximity and appearance similarity while preserving the boundary information. Then a graph Gis built for the super voxels regarding their adjacency. The connectivity of Cfg is interpreted as the connectivity on G. Our system is initialized by building the tree structure for the first frame. Nodes in the tree are denoted as Ni level, where we specify which level the node belongs to and its node number in this level. Each node is described by its related point cloud and graph Ni level ∼Ci level, Gi level, where Ci level ⊆Cfg and Gi level ⊆ G. A node for the tree root is created as N1 sc ∼(Cfg, G). As mentioned in Section 2.2, we base the construction of the tree for the first frame only on the connectivity of the input point cloud. Thus, we extract blobs from Cfg by detecting connected components on graph G. Each blob is treated as one object proposal while accordingly we create one object node Ni oin the tree. For each object node, one component node Ni cis created. Components are over-segmented into Mssegments via an over segmentation method OSeg(Ni c)→N1 s···NMs s. 3.2 Correspondences establishment and segmentation Apart from the first frame, we create the current tree structure with respect to the tree in the previous frame T r0. Similarly, a graph Gis obtained for the current point cloud and blobs are detected on G. Then, the tree building process 3D Point Cloud Video Segmentation Based on Interaction Analysis 7 is started by establishing the correspondences between the current data and T r0. Associating a set of labels to another set of labels is treated as an assignment task, in which we optimize different assignment proposals with respect to an energy function. Since the problem scale increases exponentially with the number of labels, it is critical to limit the number of the labels. Therefore, we propose to assign the blob labels in the current frame to the segments in the previous tree T r0. The blobs represent the few compact sub-clouds of the input point cloud. Assigning blob labels to segments reduces the problem scale while it respects the spatial disconnection between the compact sub-clouds, which may coincide with the object boundaries. The problem now becomes a task of assigning Mb blob labels in the current frame to Ms 0segments in the previous frame. To cope with the situation when objects go out of the scene, we employ a virtual blob Bout which stands for the space out of the interest area and does not represent any point cloud. Then, the assignment energy function is defined as: Eass(A) = Ea+Ed+Eo(1) Where Ais an assignment proposal which maps a segment label in the previous frame ls 0to a blob label lbin the current frame, Als 0→lb.Eastands for the summation of the energy of the appearance difference between the set of the point clouds Cj s 0related to the segment Nj s 0and the point cloud Ci brelated the blob Bi, where the segment label lj s 0is associated to the blob label li bregarding the assignment A. The appearance difference is measured by comparing the number of points NoP (·) on the point cloud. Ea(A) = Mb X i=1  NoP Ci b−X A(lj s 0)==li b NoP Cj s 0 (2) Edis the summation of the energy of the displacement which is calculated by measuring the Hausdorff distance disth(·) between the point cloud Cj s 0and the point cloud Ci b, where Alj s 0== li b. Ed(A) = Mb X i=1 X A(lj s 0)==li b disthCj s 0, Ci b(3) Eois the summation of the distance between the point cloud of the segment Nj s 0, which is associated with blob Bout, to the closest boundary bdi. The boundaries are predefined planes which are also used in the data acquisition step in Sec.3.1. The distance is calculated as the Euclidean distance (diste(·)) from the centroid of the point cloud of the segment to the closest boundary plane. Eo(A) = X A(lj s 0)==lout b min bdi∈Boundary disteCj s 0, bdi (4) 8 X. Lin, J.R. Casas and M. Pard`as Optimizing this energy function is a nonlinear integer programming problem. We employed the Genetic Algorithm to solve it. After the best assignment A∗is obtained, the blobs in the current frame are associated with segments in the previous frame. A further segmentation is needed when segments that correspond to different objects in the previous frame (according to the privous tree Tr 0) are assigned to the same blob. Given a blob Bi∼Ci b, Gi band the Munique object labels related to the associated segment labels lj s|A∗lj s== li b, our goal is to segment the graph Gi binto Mparts. To this end, we employ the restricted graph cut approach proposed in [17] to seek for the minimal cut on graph Gi b, which further segments this blob considering both spatial/feature homogeneity and the temporal consistency. The minimal cut is obtained by minimizing a segmentation energy function with the way introduced in [7]. The energy function for graph cut is usually defined as the summation of the data energy and the smoothness energy (E(L) = Edata +Esmooth), where L stands for the label proposal for the graph. The data energy is an unary energy term representing the degree that the label proposal fits the current data. The smoothness energy is a pair-wise energy which manages the label smoothness between nodes in the graph. The method proposed in [17] introduces a novel smoothness energy term considering the label smoothness regarding not only the current data but also the minimal cut obtained in the previous frame. The further segmentation performed on the blob with segment labels related to multiple object labels yields the object partitions for this blob while establishing their correspondences to the objects in the previous tree. As mentioned in Section 2.1, an object is represented by more than one component if it splits in different blobs, in the current or previous frames. Thus, for each object partition in the blobs, we create one component for the related object. Accordingly, the correspondences between the current components and the components in the previous tree are made. Note that there is no correspondence established for the newly generated components in the current tree. In this step, the first three levels of the current tree structure are initially built regarding the established correspondences to the previous tree at each of the three levels. 3.3 Dynamic management of merge and split Given the current tree obtained in the last step, an object proposal is implicit at the object level. This object proposal for the current input data is temporally coherent with the object proposal in the previous frame. However, it may not be a correct object proposal, since no accurate initialization is guaranteed at the beginning of this process in our approach. That is to say, this object proposal needs to be further analyzed, in order to cope with the errors in the previous information. In this case, we exploit the established correspondences and analyze the behaviors of related nodes in trees along time. More specifically, we compute the similarities among the components corresponding to the same object, which forms a similarity matrix for each object in the tree. The object similarities are computed among objects in the tree producing an object similarity matrix. In 3D Point Cloud Video Segmentation Based on Interaction Analysis 9 blob ... ... blob ... accumulated similarity matrix split Object Component Level Level (a) blob ... blob ... accumulated similarity matrix merge Object Component Level Level (b) Fig. 3. Example of dynamic management of split (a) and merge (b) our approach, the similarity between node Niand Njis defined as the Euclidean distance between their related point clouds in Eq.(5). Sim Ni, Nj=(0disteCi, Cj> ψ 1−diste(Ci,Cj) ψotherwise (5) Note that here the Euclidean distance between two point clouds is calculated as the distance between the closest point pair from them. ψis a normalizing factor. Afterwards, the similarities are accumulated along time by averaging them with the corresponding accumulated similarity in the previous frame, in order to dynamically manage the merges and splits of objects in the scene on the fly. The accumulated similarity reveals the likelihood of object splits and merges regarding the evidence observed up to the current frame. Thus, the decisions for split and merge are made by thresholding the accumulated similarity regarding two thresholds, T hsplit and T hmerge. Fig.3 shows an example how the object merge and split are dynamically managed. Specifically, a split for an object node is confirmed when a set of its child component nodes have all the accumulated similarities smaller than T hsplit with respect to the rest of the child component nodes. Then a new object node is created as the parent node of the split component nodes. In Fig.3(a), the red component node splits from its parent object node and a new object node marked in blue is created as its new parent. A merge between object nodes is confirmed when they are physically connected while the accumulated similarities between them are larger than T hmerge. In Fig.3(b), a merge is confirmed between the blue object node and the green object node which is physically connected with each other. The nodes are merged to the one with the larger number of the points on the related point cloud (the green node). Their child component nodes are all connected to the green object node in the tree. Then the blue object node is removed from the tree. 3.4 Over segmentation The first three levels in the current tree structure are built and updated in the last two steps. In this section, we introduce an over segmentation process in order to build the forth level of the tree. In the over-segmentation level, we generate segments for each component in the current tree. This is treated as the preparation for establishing the correspondence between segments in the