GraphSeg: Segmented 3D Representations
via Graph Edge Addition and Contraction

Segment Anything (SAM)[23] is an open-world segmentation model that produces high-quality mask proposals for any object in an image without relying on predefined semantic categories. Given an rgb image $I\in\mathbb{R}^{H\times W\times 3}$, SAM automatic mask generator output a set binary mask proposals

It is trained on a large and diverse 2D dataset so that it generalizes across domains in 2D single image segmentation without being restricted to any semantic class. Combining with DINO[30] visual-semantic embedding, we can use a semantic prompt to reliably extract a specific instance mask, such as the bare tabletop from a single image.

3D Foundation models projects sets of 2D images into 3D. Suppose we have a pair of RGB images with width $W$ and height $H$, i.e. $I_{1},I_{2}\in\mathbb{R}^{W\times H\times 3}$, 3D foundation models, such as DUST3R[32] specifically, produces pointmaps $X^{1,1},X^{1,2}\in\mathbb{R}^{W\times H\times 3}$, which map each 2D pixel to its predicted 3D coordinates aligned under the first image’s coordinate frame. It also generates confidence maps $C^{1,1},C^{1,2}\in\mathbb{R}^{W\times H}$ for each pointmap to quantify the uncertainty in the foundation model’s predictions at each pixel. By matching each pixel’s predicted 3D coordinates in one pointmap with the nearest coordinates in the corresponding pointmap, dense correspondences between pixels in the image pair can be established without relying on handcrafted features. The point cloud of the pair of $I_{1}$ and $I_{2}$ are then aligned to reversely predict the corresponding camera poses $P_{1},P_{2}$. As a result, we can obtain pixel-wise correspondence, an aligned 3D point cloud, camera poses by using these foundation models as a black box function. 3D foundation models have been used to understand the geometry of objects during grasping [33], and can enable the construction of 3D photorealistic representations [34, 35, 36].

In a typical graph, we have a set of vertices and edges. A graph partition divides the graph into subsets, where each subset consists of vertices that are associated with a representative vertex of that partition. The process of graph contraction—a classical concept in theoretical computer science—aims to produce such a partition by mapping together vertices that are connected, grouping them into the same subset. Formally, for a given graph $(V,E)$,

and $\tilde{V}$ denotes the set of representative vertices corresponding to the graph partition.

The overview of our method is given in Figure 2. The crux of our method lies in finding correspondences between the abundant segmentation mask classes over a set of multi-view images. The main challenges in extending 2D segmentation to consistent multi-view image segmentation are that each of the images may contain different sets of objects, and that over-segmentation may occur in many of the images.

Our key insight is to formulate the matching of potentially inconsistent segmentation masks over multiple images as graph edge addition and contraction problems. We begin by assuming that each individual class in a mask of each image is a vertex. Through edge addition and graph contraction, we reduce the set of vertices, where each new vertex is a combination of previous vertices. The process of edge addition and graph contraction is illustrated in fig. 3. Vertices are contracted together if they are masks of the same object captured over different views, and the final set of vertices corresponds to each segmented object, as shown in fig. 5.

Here, we seek to leverage both the image-level information and the estimated 3D spatial properties. This is achieved by constructing dual correspondence graphs through an edge addition process. One of these graphs estimates 2D pixel-level correspondences, and the other correspondence graph is constructed based on the 3D structure captured in each image, obtained by lifting the 2D image representation into 3D via 3D foundation model. After the edge addition process, these graphs are contracted with connected vertices being absorbed into a single vertex.

We seek to leverage the visual information between the images in the collected image set to produce initial correspondences between masks from different images. Here, we each pass a pair of images into a pre-trained dense feature matching model [37]. We obtain a set of pixel-pairs across the two different input images, along with confidence estimates. We keep all confident pairs of pixel matches, and denote the set of matching pixels by $\mathcal{F}$. Figure 4 illustrates several pixel-level matches between two images captured as different camera views. We add edges between two masks if the proportion of matching pixels in the mask exceeds a proportion threshold. That is, let $h(m_{1},m_{2})$ be the number of matching pixel pairs detected between masks $m_{1}$, $m_{2}$, i.e.

We add the edge between the vertices $m_{1}$ and $m_{2}$, if the number of matched pixels relative to the size of the smaller mask exceeds a threshold, i.e.,

where $g(\cdot)$ is the pixel area of the mask, and $\tau_{2D}$ is a threshold for which we consider two masks to be correspondent and assign an edge. We then have a graph $G_{2d}=(V,E)$, where $V$ contains the set of all 2D segmentation masks, and $E$ contains all of the correspondence edges found by pixel-to-pixel matching. Here, we note that due to over-segmentation, a mask from one image may match with multiple masks in another image. The graph $G_{2d}$ is then contracted to obtain the set $\{m^{\prime}_{1},\ldots m^{\prime}_{p}\}$ where each $m^{\prime}$ is a super-vertex contains multiple 2D masks, which have been identified to be the same object, over the image set and corresponds to an initial estimate of the 3D segmentation.

Advances in learning-based dense 3D reconstruction have enabled even sparse sets of multi-view images to be lifted into 3D. We seek to leverage the structural information of the 3D representations to further refine the initial segmentation obtained from contracting the pixel-to-pixel correspondence graph. Using only 2D pixel-to-pixel graph contraction, the resulting multi-image mask can segment the point cloud reasonably well. However, we can still observe over-segmentation in the set of super-vertices. A key reason is due to excessive surface detail. The initial 2D segmentation model often produces multiple small masks on the same object surface in many images. This typically occurs for objects with rich surface features, making it difficult for the generator to determine whether surface regions still belong to the same object across views.

We add further graph edges over the set of super-vertices. As the 3D foundation model produces a 3D point for each pixel in the input images, for each super-vertex, there is a one-to-one mapping to a point cloud. We measure the directed Chamfer distance of the corresponding points in 3D between two super-vertices, given by

where $X$ and $Y$ are 3D point clouds corresponding to the super-vertex masks. A small distance indicates that $X$ is subsumed in $Y$ and we can connect an edge correspondence, giving us a resulting graph $G_{3D}=(\hat{V},\hat{E})$. Here, $\hat{V}=\{m^{\prime}_{1},\ldots m^{\prime}_{p}\}$ contains the solutions from contracting the pixel-to-pixel correspondence graph, and $\hat{V}$ contains edges if $D(m^{\prime}_{1},m^{\prime}_{2})\leq\tau_{3D}$, for any $m^{\prime}_{1}\neq m^{\prime}_{2}$. Running graph contraction on the corresponding $G_{3D}$ produces our solution super-vertices which each represents a 3D segmentation.

To contract the constructed correspondence graphs, we leverage a variant of randomized star contraction algorithm, designed for efficient graph reduction. Each vertex $v$ in the graph $G=(V,E)$ is assigned a random label $L(v)\in[0,1]$ to break symmetry. For every vertex, define its closed neighborhood as

A vertex becomes a star center if its label is the smallest in its neighborhood:

Otherwise, it contracts to the neighbor with minimum label:

and the edge $(v,v^{*})$ is contracted, merging $v$ into the supervertex represented by $v^{\prime}$. This contraction step is performed in parallel across all vertices and recursively applied to the resulting graph until a trivial structure remains. The use of random labels $L$ ensures unbiased decision-making and balanced contraction, preserving essential connectivity while significantly reducing the graph’s complexity.

After obtaining our super-vertices, we can easily obtain the entire 3D point cloud of any segmented object simply by specifying the 2D mask of the object in the set of images, by searching through each super-vertex for the ID of the 2D mask and checking which super-vertex the mask was subsumed into.

When implementing GraphSeg, we can leverage several heuristics to enable more efficient and robust performance. We outline several implementation details in GraphSeg.

Background Class: We can leverage the properties of the tabletop manipulation problem structure for greater efficiency. We introduce a background class, which is captured by a single mask. As the 3D foundation model provides pixel-wise depth estimate, pixels that are significantly far out of the manipulation’s reach will be filtered out and along with the table surface to be added into the background class.

Speeding up the search for pixel-to-pixel correspondences: We can build highly connected graphs without resorting to iterating over all the masks in other images. Given the set of input images, for each image we only find pixel-wise correspondence with images taken at a ”nearby” camera pose. As the 3D foundation models provide both 3D structure and the camera poses where the images were taken, when considering the correspondences of an image, we can filter out images which we taken from a vastly different pose, as it would be exceedingly unlikely that they contain pixel-level correspondences.

Datasets and Implementation: GraspNet-1Billion [7] dataset is a large and comprehensive dataset which consists of three large subsets of objects (main, similar, and unseen) and 97,280 images, along with camera poses, and fine-grained instance annotations on each pixel, which make it an optimal choice to evaluate our 3D segmentation method. The dataset has been carefully labelled, with a ground truth class assigned to each pixel. GraphSeg uses vision information only, and does not require any depth information included in the data. All of our experiments were conducted on a computer with Intel i9-14900HX CPU and NVIDIA GeForce RTX 4090 GPU. We use the default parameters provided by the original authors for the comparison methods, MaskClustering and SAM3D; We select the following hyperparameters for GraphSeg: the threshold for edge addition based on 2D correspondence is selected as the value of the $78^{th}$ percentile of all considered values. During the pixel-to-pixel edge construction, we subsample the number of sampled 2D correspondence points to 10000. The threshold for adding correspondence in the 3D edge addition step is given by $\tau_{3D}=5e-4$. In practice, we have observed that GraphSeg is not overly sensitive to hyper-parameters, with values in the rough ballpark providing strong results.

Metrics: To evaluate the quality of 3D segmentation, we first want to find the subset of the segmented point cloud that corresponds to the target object. For each object in a scene, we find the corresponding point cloud by selecting (1) the segmented object class with the highest intersection over union (IoU) or (2) finding the segmented object class with the lowest chamfer distance, where the chamfer distance is defined by

We compute the IoU and $F1$ score between the ground truth object point cloud, and the corresponding segmented object point cloud found via highest IoU, denoted as IoU and $F1$. We also report the chamfer distance (denoted as $d_{\text{chamfer}}$) and IoU (denoted as $\text{IoU}_{sel}$) between the ground truth object point cloud and the corresponding segmented object point cloud found via the lowest chamfer distance. To show the necessity of considering correspondences based on both 2D structural 3D information, we also report the same metrics compute on the output of our method without the 3D graph edge addition and contraction, denoted as $\text{GraphSeg}^{-}$. The mean of IOU, $F1$, $d_{\text{chamfer}}$, and $\text{IoU}_{sel}$ over all objects in all scenes in each dataset is reported in table I.

As the quantitative result shown in table I, our method achieved the state-of-the-art performance in all metrics except $d_{\text{chamfer}}$ in all datasets. Although the best $d_{\text{chamfer}}$ is reached by $\text{GraphSeg}^{-}$, it is because $\text{GraphSeg}^{-}$ tend to over-segment the scene as shown in fig. 6, which is supported by the corresponding lower $\text{IoU}_{sel}$ compared to GraphSeg with 3D graph edge addition and contraction. MaskClustering (MC) reaches good $d_{\text{chamfer}}$ but poor IoU, which is likely because it filters out many points, and it is challenging to find 3D relations in a sparse view setup. SAM3D provides reasonable performance in some scenes but not in all scenes. Compared to the two baseline methods, our method can robustly segment the scene and out-performs the very recent baselines significantly. Additionally, we also compare the precision between our method and the baseline methods. Methods such as MaskClustering aggressively filter out points which are uncertain, resulting in low recall, F1, and IoU measure, but do not adversely impact precision, lower Chamfer distance. As shown in table II, MaskClustering produces reasonable results as measured by precision and also Chamfer distance. However, our method still outperforms the compared baselines, measured by all of the metrics.

To qualitatively assess our method, we visualize the result of our method against MaskClustering [24] and SAM3D [25] in GraspNet-1B [7] in fig. 7. As shown, our method avoids the under-segmentation, displayed by SAM3D, by using 2D correspondence to first get an initial fine-grained segmentation. This reduces aggressive merging, when relying heavily 3D structure as is done by SAM3D. MaskClustering has an over-segmentation issue in the experiment, which is likely caused by the challenging sparse multi-view setup where the spatial relationship is harder to derive. Our method solves this by fusing 2D correspondence and 3D correspondence information to build additional edges and contracting the segmentation graph more robustly. An illustration of GraphSeg relative to comparison methods is also shown in fig. 8.

Downstream robotics tasks generally benefit from denser and more complete point clouds. The process of constructing 3D representation, including the 3D foundation model, along with previous methods to construct consistent segmentation masks, filters out pixels for which the models are not confident. This is particularly true for MaskClustering, which relies on aggressively filtering out uncertain points. More 2D pixels being utilized to project into 3D space provides us with a denser point cloud. Here, we seek to measure, for non-background pixels across images, how many are utilized by the resulting masks. The pixel utility is therefore computed by taking the number of non-background pixels identified by each method over the actual number of non-background pixels in ground truth across images, shown in table III. Our method has high ($>90\%$) pixel utility comparing to other methods. Therefore, compared to baseline methods, GraphSeg retains a significantly larger number of pixels, as highlighted in fig. 9. This means that GraphSeg can extract object level representations that are represented as much denser point clouds.

To further evaluate the performance of GraphSeg, we test it under a more challenging scenario where the view is becoming increasingly sparse. Specifically, we evaluate the performance of GraphSeg, in which only $N=5$ and $N=3$ number of images are provided. This condition challenges GraphSeg with less pixel correlation and significantly less 3D spatial information. We visualize the result in fig. 10, from which we observe that GraphSeg retains its performance and provides reliable 3D segmentation even under sparse view conditions.

Segmentation of tabletop scenes to reveal object-level representations is crucial for robot manipulation. Typically, object representations, such as point clouds, are given to off-the-shelf grasp generators to generate feasible grasps for the robot. We demonstrate the effectiveness of GraphSeg on a real-world Unitree Z1 manipulator. A RGB camera is mounted on the end-effector of a robot manipulator, and objects are placed on the table top in front of the robot manipulator, then the robot manipulator moves around to take several RGB images of the tabletop. We utilize a 3D foundation model to generate point cloud and camera poses, and align it to the robot base via a hand-eye calibration method [39, 40];

We run GraphSeg on the point cloud and RGB images, and output the segmentations of objects that we can grasp. We leverage GraphSeg to extract individual object point clouds from a set of multi-view RGB images of an unstructured table setup. These point clouds are then inputted, alongside gripper parameters, to a grasp generator. We use grasp generator [38], and filter infeasible solutions based on collision-checking against a signed distance field of the environment. An example is illustrated in fig. 11. The robot then executes the corresponding grasps generated. We demonstrate successful grasp, on the real-world manipulator, for a variety of objects, including a surveyor’s level, a hammer, a small cup, a battery package, and a remote controller. A planner can be integrated to generate collision-free motions [41, 42, 43]. The experimental setup, 3D reconstruction, along with masks over nearby objects on the table, are all illustrated in fig. 12. In fig. 13, we illustrate the resulting grasps computed, over object-level representations, along with the successful grasps given in the subsequent rows.