Elsevier

Pattern Recognition Letters

Volume 33, Issue 15, 1 November 2012, Pages 2057-2064
Pattern Recognition Letters

A graph-based technique for semi-supervised segmentation of 3D surfaces

https://doi.org/10.1016/j.patrec.2012.03.015Get rights and content

Abstract

A wide range of cheap and simple to use 3D scanning devices has recently been introduced in the market. These tools are no longer addressed to research labs and highly skilled professionals, but rather, they are mostly designed to allow inexperienced users to acquire surfaces and whole objects easily and independently. In this scenario, the demand for automatic or semi-automatic algorithms for 3D data processing is increasing. In this paper we address the task of segmenting the acquired surfaces into perceptually relevant parts. Such a problem is well known to be ill-defined both for 2D images and 3D objects, as even with a perfect understanding of the scene, many different and incompatible semantic or syntactic segmentations can exist together. For this reason recent years have seen a great research effort into semi-supervised approaches, that can make use of small bits of information provided by the user to attain better accuracy. We propose a semi-supervised procedure that exploits an initial set of seeds selected by the user. In our framework segmentation happens by propagating part labels over a weighted graph representation of the surface directly derived from its triangulated mesh. The assignment of each element is driven by a greedy approach that accounts for the curvature between adjacent triangles. The proposed technique does not require to perform edge detection or to fit parametrized surfaces and its implementation is very straightforward. Still, despite its simplicity, tests made on a standard database of scanned 3D objects show its effectiveness even with moderate user supervision.

Highlights

► We introduce a graph-based semi-supervised technique for 3D surface segmentation. ► The implementation is simple and can be performed with little coding. ► Very good results can be achieved even with few hints supplied by the user. ► The result obtained are evaluated using well-known metrics and datasets. ► The approach is fast even with meshes of moderate size.

Introduction

Segmentation is an important preliminary task in many 2D and 3D data processing pipelines. For instance, splitting an image or a 3D object in smaller parts is very useful to perform high-level recognition (Kokkinos and Maragos, 2009, Ferrari et al., 2006), reverse engineering (Courtial and Vezzetti, 2008, Kim et al., 2002), parts retrieval (Antini et al., 2005) and even tracking (Colombari et al., 2007). Of course, the expected outcome of a segmentation procedure is different depending on the intended use of the resulting parts. If the goal is to produce a set of image macro pixels, segments will be searched at a purely syntactic level, i.e. by grouping together pixels of uniform color or texture, regardless of their belonging to one object or another. By contrast, different scenarios require a more semantical splitting, with the aim of separating foreground from background or finding the boundaries of the objects found in the scene. Obviously, these approaches tend to be more specialized, since the cues to exploit strongly depend on the problem context and on the availability of humans in the loop.

When dealing with the 3D domain, segmentation is mostly targeted at splitting an object or a surface into subdomains that can be later interpreted as parametrized primitives. The complexity of such primitives can range from basic items, such as planes, cylinders or spheres, to complete parametrized models, depending on the overall goal of the pipeline. Simple primitives are fitted to the segmented parts mainly for object simplification (Lafarge et al., 2010, Baillard and Zisserman, 1999), while completed models can be used for direct 3D object recognition with resilience to clutter (Mian et al., 2006) or invariance to scale (Bariya and Nishino, 2010). Finally, another important application that needs surface decomposition is the angle and distance-preserving piecewise parametrization needed to apply textures to objects (Wang et al., 2005).

Surface segmentation can happen through many different methods. Some of them use standard clustering techniques or borrow segmentation procedures from the 2D domain, other exploit graph partitioning algorithms, shape fitting or even the distribution of symmetry planes over watertight objects.

Shlafman et al. propose to use a variation of K-means to group the triangles of the mesh into clusters (Shlafman et al., 2002). This is a quite direct adaptation: first the user specify the desired number of clusters (k), then the process starts by randomly selecting a set of k well spaced seed triangles and it iterates by alternating an assignment step (where each non-seed triangle is assigned to the nearest seed) and an adjustment step (where new seeds are selected by picking the triangle nearest to the center of each cluster).

Another classical technique is adapted by Moumoun et al., that suggest the use the Watershed principle (Moumoun et al., 2010) on a hierarchical transformation of connected faces structure based on the principal curvature. An interesting perspective on 3D segmentation is supplied by Podolak et al. (2006), whose solution exploits the relation between mesh elements and the symmetry planes of the whole object.

Katz and Tal (2003) split the problem into two separate steps: first a probabilistic clustering is used in order to obtain meaningful but fuzzy components, then exact boundaries are constructed by assigning shared faces to the final cluster. A couple of years later, the same authors present an additional hierarchical method (Katz et al., 2005) that performs three steps: the transformation of the surface into a pose insensitive representation by means of Multi-Dimensional Scaling (MDS); the localization of prominent feature points to be used as seeds; the extraction of clusters by refinement of core components obtained using spherical mirroring.

Mortara et al. (2003) propose a multi-scale method based on blowing bubbles. The surface segmentation happens by clustering vertices with respect to their morphological behavior at different scales. This is done by centering on each vertex spheres of increasing diameter and using the curves resulting by their intersection with the mesh as a characterizing descriptor for the clustering process.

Shapira et al. (2008) describe a method that exploits the Shape Diameter Function (SDF), a measure related to the object volume in the neighborhood of each point that is computed for the barycenter of each triangle. The segmentation procedure relies on a two phase process. In the first phase, a Gaussian Mixture Model is used to fit k Gaussians to the histogram of all SDF values in order to produce a probability vector of length k for each triangle indicating its likelihood to be assigned to each of the SDF clusters. In the second step the segmentation is refined using the alpha expansion graph-cut algorithm, which is used to minimize an energy function that combines the vectors obtained in the first phase along with boundary smoothness and concaveness.

Attene et al. (2006a) introduce the use of geometric primitives to drive a hierarchical segmentation. Specifically, at an initial stage each surface triangle represents a singleton cluster associated to the primitive that best fits it. Such primitives can be planes, spheres and cylinders. At each step, all the adjacent clusters are considered for merging and those that can be better approximated with one of the primitives form a new single cluster. The process stops when the desired number of segments has been obtained.

Lai et al. (2008) describe a procedure based on Random Walks that operates in two steps. Initially a set of seeds is chosen and the mesh is over-segmented by assigning each face to the seed that has the highest probability of reaching it by a random walk. The obtained segments are then hierarchically merged until the desired number of clusters is obtained. This is done following an order based on the relative lengths of the intersections and total perimeters of adjacent segments.

Golovinskiy and Funkhouser (2008) use both normalized cuts and randomized cuts. In a similar manner to Attene et al. (2006a), normalized cut segmentation happens by first assigning each face of the mesh to its own cluster and then by merging them hierarchically in an order determined by the area-normalized cut cost, i.e. the sum of each segment perimeter (weighted by concavity) divided by its area. In this way it is possible to obtain segments that exhibit small boundaries along concave seams while maintaining segments with roughly similar areas. Differently, randomized cuts segmentation is initially applied to a strongly decimated mesh, obtaining very large segments. Those segments are then hierarchically splitted in a top–down manner, starting with all the faces in a single segment. For each split, a set of randomized cuts is computed over the segment, and the cut that is most consistent with others in the randomized set is identified. Among this set of candidates, the one that results in the minimal normalized cut cost is chosen. In both cases, the process stops when the required number of segments has been reached.

More recently Berretti et al. (2009) introduced an approach based on Reeb graphs that is motivated by perceptual principles and supports identification of salient object protrusions.

For a recent review and comparison of the most well known mesh segmentation techniques see Attene et al. (2006) or Shamir (2008).

In this paper we introduce a novel graph-based segmentation approach aimed at achieving high speed on triangulated meshes. The proposed method is designed to exploit the connected graph induced by the mesh itself and thus can not be applied directly to unstructured or partially structured 3D data such as point clouds or sets of range images. However many segmentation techniques exist to deal with such scenarios (Golovinskiy and Funkhouser, 2009, Zou and Ye, 2007, Min and Bowyer, 2005). The described algorithm adopts a greedy label propagation approach based only on easily computable curvature information along the edges of the mesh. While an initial seeding is required by the user, our approach is very simple to implement and the experimental validation highlights its speed and its good performance when compared with other graph-based systems.

Section snippets

Weighted graph-based seeded segmentation

Graph-based segmentation has been previously explored by several authors (Golovinskiy and Funkhouser, 2008, Lai et al., 2008, Zhang et al., 2008). Most of the approaches found in literature perform some global computation over the graph in order to evaluate random walk reachability or optimal cuts. The algorithm presented in this paper (see Fig. 2), after building a weighted dual graph, adopts a straightforward greedy approach that directly extends an initial set of seeds by picking one new

Experimental validation

The evaluation of the result produced by a segmentation technique has proven to be a difficult task for a number of different reasons. The first hurdle is related to the fact that the segmentation problem itself tends to be elusive with respect to a clear definition. In fact, it is not always clear if the goal of the process is to isolate different object parts by virtue of their semantic or rather split them by the characteristics of their surface boundaries or even by clustering them in

Conclusions

In this paper we introduced a simple yet effective segmentation procedure for 3D objects and surfaces. While our method requires an initial set of user hints, results that are on par with fully supervised segmentations can be obtained even with a very limited amount of seeds placed without special care by the user. Moreover the time required to perform a segmentation is in the order of few millisecond with meshes that count tens of thousands of vertices. This allows for the inclusion of the

References (35)

  • S. Berretti et al.

    3d mesh decomposition using reeb graphs

    Image Vision Comput.

    (2009)
  • A. Colombari et al.

    Segmentation and tracking of multiple video objects

    Pattern Recognition

    (2007)
  • M.L. Fredman et al.

    Surpassing the information theoretic bound with fusion trees

    J. Comput. Syst. Sci.

    (1994)
  • J. Min et al.

    Improved range image segmentation by analyzing surface fit patterns

    Comput. Vision and Image Understanding

    (2005)
  • G. Antini et al.

    3D mesh partitioning for retrieval by parts applications

    IEEE Int. Conf. on Multimedia and Expo

    (2005)
  • M. Attene et al.

    Hierarchical mesh segmentation based on fitting primitives

    Vis. Comput.

    (2006)
  • Attene, M., Katz, S., Mortara, M., Patane, G., Spagnuolo, M., Tal, A., 2006b. Mesh segmentation-a comparative study....
  • Baillard, C., Zisserman, A., 1999. Automatic reconstruction of piecewise planar models from multiple views. In: IEEE...
  • Bariya, P., Nishino, K., 2010. Scale-hierarchical 3D object recognition in cluttered scenes. In: IEEE Conf. on Computer...
  • Benhabiles, H., Vandeborre, J.P., Lavoué, G., Daoudi, M., Jun. 2009. A framework for the objective evaluation of...
  • H. Benhabiles et al.

    A comparative study of existing metrics for 3D-mesh segmentation evaluation

    Vis. Comput.

    (2010)
  • X. Chen et al.

    A benchmark for 3D mesh segmentation

    ACM Trans. Graph. (Proc. SIGGRAPH)

    (2009)
  • M. Corsini et al.

    Watermarked 3D mesh quality assessment

    IEEE Trans. Multimedia

    (2007)
  • Courtial, A., Vezzetti, E., 2008. New 3d segmentation approach for reverse engineering selective sampling acquisition....
  • V. Ferrari et al.

    Simultaneous object recognition and segmentation from single or multiple model views

    Internat. J. Comput. Vision

    (2006)
  • Gerig, G., Jomier, M., Chakos, M., 2008. Valmet: A New Validation Tool for Assessing and Improving 3D Object...
  • A. Golovinskiy et al.

    Randomized cuts for 3D mesh analysis

    ACM Trans. Graph. (Proc. SIGGRAPH ASIA)

    (2008)
  • Cited by (18)

    • C2F-3DToothSeg: Coarse-to-fine 3D tooth segmentation via intuitive single clicks

      2022, Computers and Graphics (Pergamon)
      Citation Excerpt :

      There are different criteria and methods of mesh segmentation [16]. These methods include region growing [17,18], the watershed method [19,20], iterative clustering [21,22], and hierarchical clustering [23,24]. These segmentation results do not need to match those recognized by human vision: that is, they are not necessarily meaningful from the human point of view.

    • Enhanced Invariance Class Partitioning using Discrete Curvatures and Conformal Geometry

      2021, CAD Computer Aided Design
      Citation Excerpt :

      Zhang et al. introduced an approach with five steps to segment 3D mesh, including the core step of region growing regarding curvature [15]. Bergamasco et al. proposed a semi-supervised region-growing method by propagating part labels over a weighted graph representation of the surface directly derived from its triangulated mesh [16,17]. Region growing method is a commonly used method in mesh segmentation due to its simplicity.

    • An improved 3D shape visibility graph with application to mesh segmentation

      2020, Signal Processing: Image Communication
      Citation Excerpt :

      While these methods capture concavities from surface measurements, in [22] the distance metrices proposed in [9] are combined with a visibility realization. In [23] a semi-supervised method is proposed where the minima rule is realized by computing the curvature between adjacent faces. However, these measures are limited from the local nature of surface (noise).

    • A salience measure for 3D shape decomposition and sub-parts classification

      2018, Graphical Models
      Citation Excerpt :

      Supervised methods are based on user-segmented data and learning methods, offering a perceptually coherent segmentation as in [16,17]. Unsupervised methods make use of other tools, such as clustering methods or region-growing based on various shape characteristics (e.g. [18,19], or see [15] for a comparison), spectral analysis (e.g. [20]), spatial subdivision methods or explicit boundary extraction (e.g. [13,21]), or probabilistic models [22,23]. Other segmentation methods are based on topological information, like Reeb graphs [24] but depend on the function chosen for defining the graph [25].

    View all citing articles on Scopus
    View full text