Motion analysis in dynamic point clouds is an emerging area, required by various applications such as surveillance, autonomous driving, and robotic manipulation. Our human-made environments are dominated by rigid body movements, ranging from articulated objects to solids like furniture or vehicles. These settings require us to address rigid motions of objects or object parts -which is often referred to as the multi-body motion estimation problem. Despite its importance, previous work has mainly focused on specific scenarios with known category semantics, like category-level articulated object segmentation [41], indoor scene instance relocalization [65], or car movement detection [72], leaving the literature of generic motion segmentation relatively unexplored. Different from traditional single scan analysis algorithms like semantic segmentation [39], the most challenging part in multi-body motion analysis is to disambiguate and distinguish rigid bodies. There, we are naturally required to jointly process and relate multiple inputs, to effectively find consistent motion-based part/object segmentations as well as point correspondences to enable a multi-way registration. It is even more challenging when the capture is not temporally dense, i.e., an intermittent acquisition that does not follow a stream such as a video, and might contain large pose variations, hampering naive temporal tracking.
In this paper, we introduce a multi-scan multi-body segmentation and motion estimation problem, where the goal is to simultaneously discover and register rigid bodies from multiple scans, represented either as full or partial point clouds, where objects come from unseen categories. As an effective solution, we present MultiBodySync, a fully end-to-end trainable deep declarative architecture [23] able to process an arbitrary number of unordered point sets. As shown in Fig. 1, given a set of scans, MultiBodySync begins relating pairs of scans via 3D scene flow [78,64] and con-fidence estimation. Then, the following two differentiable (permutation and segmentation) synchronization modules, which are central to our approach, respectively enforce the consistency of pairwise point correspondences and motion segmentation labelings across different scans. Our design explicitly decouples geometry and motion, making Multi-BodySync generalizable to unseen categories without sacrificing robustness.
We evaluate MultiBodySync on various datasets composed of full synthetic point clouds and partial real scans with articulated and solid objects. We also contribute a new dataset DynLab with 8 scenes and 64 scan fragments of distinctly moving objects. Our extensive evaluations demonstrate that our algorithm outperforms the state-of-the-art by a large margin on both multi-body motion segmentation and motion estimation. In brief, our contributions are: 1. We introduce a novel end-to-end trainable architecture for solving the multi-scan multi-body motion estimation and segmentation problem. 2. We theoretically analyze the spectral characteristics of the proposed weighted permutation synchronization. 3. To the best of our knowledge, we showcase the first cross-category generalization for the task at hand on both synthetic and real datasets, for both articulated part-level and object-level regimes.
Dynamic scene understanding. The modeling of 3D dynamic scenes in deep learning literature is often formulated as a 4D data analysis, as done in seminal works like [43,19]. Ability to infer spatiotemporal geometric properties has recently motivated research in 3D scene flow as a form of lowlevel dynamic scene representation [42,60,69,51,47,54,44]. Domain-specific knowledge can be employed to give better predictions as done in autonomous driving [29,5,72] or articulated object analysis [77,68]. The most recent dynamic SLAM works [31,7,81,75] also rely heavily on semantic cues. While some works [47,54] advocates continuous temporal-dynamics modeling, we instead assume discrete non-sequential input and enforce consistency using synchronization. Similarly, [26,65] propose to perform instance-level re-localization in a changed scene. Nevertheless, we do not assume a pre-segmentation of the scene, but instead perform joint motion segmentation.
Multi-body motion. Provided point correspondences between two point clouds/images, rigid-body motion segmentation becomes a multi-model fitting problem, amenable for factorization techniques [20,40,76], clustering [32], graph optimization [45,35,11] or deep learning [38]. Among others, [78] handles raw scans and segments the rigidly moving parts using a Recurrent Neural Network (RNN). [28] fits non-parametric part models to sequential 3D data without needing explicit correspondences. However, to our best knowledge, no prior work can handle multiple scans while enforcing multi-way consistency like we do.
Synchronization. The art of consistently recovering absolute quantities from a collection of ratios is now a basic component of the classical multi-view/shape analysis pipelines [56,14,15]. Various aspects of the problem have been vastly studied: different group structures [25,24,12,2,1,33,27,1,66,18,59,62,4,6], closed-form solutions [4,2,1], robustness [17], certifiability [55], global optimality [13], learning-to-synchronize [34,50,22] and uncertainty quantification [61,10,9,12]. In this work, we are concerned with synchronizing correspondence sets, otherwise known as permutation synchronization (PS) [48] and motion segmentations [3]. PS is rich in the variety of algorithms: low-rank formulations [80,67], convex programming [30], distributed optimization [30], multi-graph matching [57] or Riemannian optimization [12]. Out of all those, we are interested in the spectral methods of [2,46] as they provide efficient, closed-form solutions deployable within a deep declarative network [23] like ours.
To the best of our knowledge, synchronization of correspondences [46] or motion segmentation [3] have not been explored in the context of deep learning. This is what we do in this paper to tackle the consistent multi-body motion estimation and segmentation.
Problem setting and notation. Suppose we observe a set of
where each point cloud X k = x k 1 , ..., x k i , ..., x k N contains N points in R 3 and sampled from the same object with S independently moving rigid parts indexed by s. Each point is assumed to belong to one of the S rigid parts and we denote the binary point-part association matrices as
i belongs to the s th rigid part and G k is = 0 otherwisefoot_0 . The rigid motions for each part s in each point cloud k is defined as
and the translational part being t k s ∈ R 3 . Our final goal is to infer G and T given X . Summary. The core of our approach is a fully differentiable deep network fusing rigid dynamic information from multiple 3D scans as outlined in Fig. 2. We begin by explicitly predicting pairwise soft correspondences across all pairs of point clouds while enforcing consistency via a weighted permutation synchronization ( § 3.1). Next, the point clouds are segmented using a novel motion-based segmentation network and also further synchronized by a subsequent motion segmentation synchronization module ( § 3.2). Finally, the correspondences and segmentations are used to recover the 6-DoF transformation for each of the individual rigid parts. The whole procedure can be iterated to refine the results. The pipeline can be readily trained endto-end and we describe our training procedure in § 3.3.
Our approach starts with point correspondence estimation between all K 2 pairs of point clouds. We tackle this problem by predicting a 3D scene flow
= X l holds up to a permutation. The architecture of ϕ flow inspired by Point PWC-Net [73] is detailed in the supplementary material.
Flow signals, estimated in a pairwise fashion, are not informed about the multiview configuration at our disposal. To ensure multi-way consistent flows, we employ the weighted variant of permutation synchronization [46] inspired by [22,34] where a closed-form solution is given under spectral relaxation. We begin by the observation that any flow F kl would induce a soft assignment matrix P kl ∈ M N ×N based on the nearest-neighbor distances:
where τ is the temperature of the softmax. The multinomial manifold M of row-stochastic matrices is a continuous relaxation of the (partial) permutation group P.
Outlier filtering. To take into account the noise, missing points, or errors in the network, we further associate a confidence value c kl i ∈ R to each point x k i and its corresponding flow vector f kl i through another network ϕ conf (•) : R 7×N → R N inspired from OANet [82]. The input to this network are the tuples {(x k i ,
i=1 and we provide the architectural details in the supplementary. The last dimension of this tuple measures the quality of the flow vector via the distance between the transformed points and their nearest neighbors, thereby detect-ing spurious flow predictions. The final w kl in Eq (3) reflects the overall quality of the corresponding P kl . Here we choose w kl as the average confidence of all points, i.e., w kl = N i=1 c kl i /N . Consistent correspondences. We now use the predictions {P kl , w kl } (k,l) to achieve multiview consistent assignments. To this end, we deploy a differentiable synchronization algorithm inspired by [46]. We first introduce absolute permutation matrices P k which map each point in X k to a universe space and stack them as p = [. . . , (P k ) ⊤ , . . . ] ⊤ . We solve for the best p minimizing:
Theorem 1 (Weighted synchronization). The spectral solution to the weighted synchronization problem in Eq (2)
p is given by the N eigenvectors of L corresponding to the smallest N eigenvalues, where L ∈ R KN ×KN is the weighted Graph Connection Laplacian (GCL) constructed by tiling all P kl matrices weighted by the related w kl :
Proof. Please refer to the supplementary material.
This spectral solution requires only an eigendecomposition lending itself to easy differentiation [34,22]. The synchronized soft correspondence Pkl is then extracted as the (k, l)-th N × N block of pp ⊤ . As a consequence of the relaxation, we cannot ensure that each sub-matrix of pp ⊤ would be a valid permutation. To preserve differentiability we avoid Hungarian-like projection operators [46] and propose to directly compute the induced flow Fkl = ..., f kl i , ... using a softmax normalization on the synchronized soft correspondences:
Intuitively, this amounts to using the normalized synchronized result as a soft-assignment matrix, diminishing the effect of non-corresponding matches (false positives).
Based upon the multiview consistent flow output Fkl , we now predict the point-part associations G. Since we are not provided with consistent labeling of the parts, instead of predicting G k directly, we estimate for all K 2 point cloud pairs a relative motion segmentation matrix ζ kl ∈ [0, 1] N ×N , where ζ kl ij is 1 when x k i and x l j belong to the same rigid body, and 0 otherwise.
Our motion segmentation network ϕ mot (•) : R 12×N → R N ×N illustrated in Fig. 3 takes the point cloud pair X k , X l as well as flow Fkl , Flk estimated from the last step as input and outputs the matrix ζ kl . It begins with a PointNet++ [53] predicting a transformation Tkl i for each point in x k i ∈ X k2 . The predictions map the part in X k containing x k i to X l . We then compute a residual matrix β kl ∈ R 3×N ×N based on Tkl i , whose element is:
where • denotes the action of T. One can easily verify that the smaller the norm of the (i, j)-th entry of β kl is, the more likely that x k i and x l j are in the same rigid part. Therefore, it contains valuable information for deducing the motion segmentation ζ kl . We apply N denoising mini-PointNet [52] ϕ mlp (•) to each horizontal 3 × N slice of β kl , concatenated with X l to get a likelihood score for each pair of points (x k i ∈ X k , x l j ∈ X l ). The network output ζ kl net is subsequently computed by applying a sigmoid on the output:
Motion segmentation consistency. Given all pairwise motion information ζ kl , we adopt the method of Arrigoni and Pajdla [3] to compute an absolute motion segmentation g ∈ R KN ×S as a stack of matrices in G. Once again, this is an instance of a synchronization problem, with the stacked relative and absolute motion segmentation matrices being:
A spectral approach similar to the one in § 3.1 optimizes for g so that Z = gg ⊤ is best satisfied. Then, g is just the S leading eigenvectors of Z, scaled by the square root of its S largest eigenvalues. Here, the point-part association matrices G k are relaxed to fuzzy segmentations by allowing its entries to take real values. As a subsequent step similar to § 3.1, we replace the projection step with a row-wise softmax on g to maintain differentiability. Note that the output ζ kl net of ϕ mot is unnormalized, meaning that any submatrix in Z can be written as ζ kl = σ kl ζ kl net , where σ acts as a normalizer. This is akin to encoding a confidence in the norm of the matrix ζ kl net and requires us to solve a weighted synchronization. However, as we prove in the following theorem, such a solution would involve an anisotropic scaling in the eigenvectors as a function of the number of points belonging to each part. As this piece of information is not available in runtime, we take an alternative approach and approximate the scaling factor as q kl = mean(ζ kl net ) and pre-factor it out of ζ kl net , by letting ζ kl = ζ kl net /q kl . In this way, we ensure that the eigenvectors yield the synchronized motion segmentation.
Theorem 2. Under mild assumptions, the solution to the segmentation synchronization problem using a nonuniformly weighted matrix will result in a proportionally scaled version of the solution obtained by the eigenvectors of the unweighted matrix Z.
Proof. Please refer to the supplementary material.
As we show in our supplement, entry k in the decomposed eigenvalues is related to the number of points belonging to motion k. To compute the number of rigid bodies S, i.e., determine how many eigenvectors to use in g, the spectrum of Z is analyzed during test time: We estimate S as the number of eigenvalues that are larger than α-percent of the sum of the first 10 eigenvalues. For training, we just fix S = 6 as an over-parametrization.
Pose Computation and Iterative Refinement. We finally estimate the motion for each part using a weighted Kabsch algorithm [37,22] followed by a joint pose estimation. During test time we also iterate our pipeline several times to gradually refine the correspondence and segmentation estimation by transforming input point clouds according to the estimated T and adding back the residual flow onto the flow predicted at the previous iteration. The details are provided in our supplementary.
We propose to train each learnable component of our pipeline separately in a pairwise manner and then fine-tune their parameters using the full pipeline. Specifically, we first train the flow estimation network ϕ flow supervised with ground-truth flow: L kl flow = F kl -F kl,gt 2 F . Given the trained ϕ flow , the confidence estimation network ϕ conf is trained based on its output using a binary cross-entropy (BCE) loss supervised by comparing whether the error of the predicted flow is under a certain threshold:
with c kl,gt i = 1 if we have f kl if kl,gt i 2 2 < ǫ f and 0 otherwise. The motion segmentation network ϕ mot is trained using joint supervision over the estimated transformation residual and the final motion segmentation matrix: L kl seg = L kl trans + L kl group where each term is defined as:
After we train all the networks (i.e., ϕ flow , ϕ conf and ϕ mot ), the entire pipeline is trained end-to-end with the supervision on both the pariwise flow K k=1 K l=1 L kl flow and the IoU (Intersection-over-union) loss, defined as:
where A is an S × S binary assignment matrix which we found using the Hungarian algorithm. The flow supervision is added to both the output of flow network, and the final pairwise rigid flow computed as
Datasets. Our algorithm is tested on two main datasets: SAPIEN [74] and DynLab dataset contributed by this work: SAPIEN consists of realistic simulated articulated models with part mobility annotated. We ensure that the categories used for training and validation do not overlap with the test set, finally leading to 720 articulated objects with 20 dif- ferent categories. We then perform K virtual 3D scans of the models, with each scan capturing the same object with a different camera (and hence object) pose and object articulating state. Later, furthest point sampling is applied to down-sample the number of points to N . DynLab (Dynamic Laboratory) contains 8 different scenes in a laboratory, each with 2-3 rigidly moving solid objects from various categories. Each of the scenes is captured 8 times, reconstructed using ElasticFusion [71] and between each capture, the object positions are randomly changed. The dataset also contains manual annotations of the object segmentation mask and rigid absolute transformations. For benchmarking, in each scene we choose different combinations of the 8 captures, leading to a total of 8 • 8 4 = 560 dataset items. We believe the two different scenarios (articulated single object and moving rigid bodies) reflected in the test sets are sufficient to verify the robustness and the general applicability of our algorithm.
The training data for articulated objects are generated using the dataset from [79], containing manually annotated semantic segmentation of 16 categories. Similar to [78], we generate K random motions for each connected semantic part of the shapes. For the training data of solid objects, we randomly sample independent motions for multiple objects taken from ShapeNet [16] as if they are floating and rotating in the air. Please refer to supplementary material for detailed data specifications and visualizations.
Metrics. Two main metrics are used: (1) EPE3D (End-Point Error in 3D) of all K 2 pairs of point clouds. The mean and standard deviation (+/-) measures the rigid 3D flow estimation quality: While the mean reflects an overall error in the transformation, the standard deviation shows how consistent the estimate is among all pairs -a desirable property in the multi-scan setting. (2) Segmentation accuracy assesses the motion segmentation quality. We use mIoU (mean Intersection-over-Union) and RI (Rand Index) to score the output based on 'Multi-Scan' and 'Per-Scan' segmentations. For 'Multi-Scan', we evaluate the points from all K clouds altogether, revealing the consistency of the labeling across multiple scans. For 'Per-Scan', we compute the score for each of the clouds separately and evaluate the mean and standard deviation across all scans.
Training. ϕ flow , ϕ mot and ϕ conf are trained using Adam optimizer with initial learning rate of 10 -3 and a 0.5/0.7/0.7 decay every 400K iterations for the three networks. The batch sizes are set to 32/8/32, respectively. The entire pipeline is trained end-to-end using K = 4 point clouds, with a learning rate of 10 -6 . The gradient computation for eigen-decomposition will sometimes lead to numerical instabilities [21], so we roll back that iteration when the gradient norm is large. Our algorithm is implemented using PyTorch [49] with N = 512, τ = 0.01, ǫ f = 0.1. We set α = 0.05 for articulated objects and α = 0.15 for solid objects.
Baselines. Given our new multi-scan multi-body setting, we made adaptations to previous methods and compared to the following 4 baselines: Flow Accuracy. Tab. 1 shows that despite being based on [78], our method gives the lowest flow error and variance across different view pairs. This is thanks to the correspondence consistency among the provided K scans enforced by our synchronization module. The NPP method suffers from a surprisingly high flow error mainly because the point-level correspondence is not explicitly modeled. Note that Point-Net++ and MeteorNet are excluded because they only output point-wise segmentations.
Segmentation Accuracy. For the segmentation benchmark, we achieve a significantly better result than all the baselines as shown in Tab. 2. Among the baselines, Me- One important aspect of our network is that it can generalize to different objects and motions without re-training. To qualitatively showcase this, we use two additional dynamic RGB-D sequences from [63] and [58]. For each sequence, we use four views and back-project the depth map into point clouds for inference. As shown in Fig. 5, our model trained on full objects of synthetic SAPIEN dataset, can generalize to real dynamic depth sequences producing consistent motion-based segmentation. This is possible thanks to the property that our network anchors on the motion and not on the specific geometry.
In DynLab, each rigid body (i.e. object) is now semantically meaningful, so apart from the 4 baseline methods from § 4.1, we additionally compare to the following two alternatives: (5) InstSeg (Instance Segmentation): We take the state-of-the-art indoor semantic instance module Point-Group [36] trained on ScanNet dataset to segment for each input cloud. ( 6) Geometric: We use the Ward-linkage [70] to agglomeratively cluster the points in each scan. In order to obtain consistent segmentation across multiple inputs, we associate the segmentations between two different scans using a Hungarian search over the object assignment matrix, whose element is the root mean squared error measuring the fitting quality between any combinations of the object associations.
Interestingly, as listed in Tab. 3, all the previous deep methods lead to unsatisfactory results on this dataset. Point-Net++ and MeteorNet are found to be inaccurate because by design they associate labels in the level of semantics (not motion) and no explicit consistencies across scans are considered. Even though the InstSeg method is trained on large-scale scene dataset, it is impossible for it to cover all real-world categories so wrong detections are observed in some scenes. The geometric approach is less robust in cluttered scenes where no obvious geometric cues can be used. Our method is motion-induced and is hence robust to geometric variations and out-of-distribution semantics, outperforming all baselines. A typical failure scenario for these approaches is visualized in Fig. 6. We show additional qualitative results in Fig. 7, demonstrating our ability to accurately segment, associate, and compute correct object transformations even if there are large pose changes.
Tab. 4 shows the rigid flow estimation result against the baselines. Apart from the influence of wrong per-scan segmentation and cross-scan associations, the iterative closest point (ICP) [8] method used to register object scans can also suffer from poor initializations. Our approach not only reaches the lowest mean error, but also respects the motion consistency across multiple scans.
Effect of synchronization. For permutation synchronization ( § 3.1), we can directly feed the network-predicted flow vector F kl to subsequent steps instead of using synchronized Fkl (Ours: NS, NW), or use an unweighted version of the synchronization by setting all w kl = 1 (Ours: S, NW). However, as shown quantitatively in Tab. 1, both variants result in higher flow error due to the failure to find consistent correspondences. Similar results can be observed on DynLab dataset as demonstrated in the two sub-figures of Fig. 6, where direct flow prediction failed because the geometric variation is too large between two scans.
Effect of K. Our method can be naturally applied to an arbitrary number of views K even if we train using 4 views, because by design the learnable parameters are unaware of the input counts. As shown in Fig. 9, the segmentation accuracy improves given more views. This is because the introduction of additional scans helps build the connection between existing scans and benefits the 'co-segmentation' process.
As pointed out in § 3.2, our pipeline can be run multiple iterations to refine the results and an example is given in Fig. 8. Shown in Fig. 9, our method works better with more iterations because we estimate more accurate flows. Moreover, more iterations are demonstrated to be unnecessary because previous iterations already lead to converged results. Timing. Our experiments are conducted using an Nvidia GeForce GTX 1080 card. For the input of 4 scans, the running time of our full model is ∼870ms per iteration. The entirety of a 4-iteration scheme hence takes ∼3.5s, while [78] and [28] take 11.5s and 60s resp. in comparison.
We presented MultiBodySync, a pipeline for simultaneously segmenting and registering multiple dynamic scans with multiple rigid bodies. We, for the first time, incorporated weighted permutation synchronization and motion segmentation synchronization into a fully-differentiable pipeline for generating consistent results across all input point clouds. However, currently MultiBodySync is not scalable to a large number (like hundreds) of scans or rigid bodies. Future directions include improvement of the pipeline's scalability and robustness in more complicated and dynamic settings.
Throughout our paper we use superscript k, l to index point-clouds, subscript i, j to index points and subscript s to index rigid parts.
In practice, instead of predicting Tkl i directly, we estimate a residual motion w.r.t. the already obtained flow vectors similar to the method in[78]. This procedure is detailed in our supplementary material.