Partitioning 3D Surface Meshes Using Watershed Segmentation
Alan P. Mangan, Ross T. Whitaker
IEEE Transactions on Visualization and Computer Graphics
Volume 5, Number 4, Pages 308-321, 1999
Partitioning a triangle mesh into meaningful segments is useful in many
applications including mesh reduction, reparameterization of irregularly
connected meshes for reduction and refinement algorithms, fitting higher-order
models to meshes, modification of existing 3D CAD models, and feature
detection. The problem of partitioning a triangle mesh into meaningful parts
is called mesh segmentation. Like the image segmentation problem
in computer vision, the mesh segmentation problem is not well posed; solutions
are often domain-specific and rely heavily on our definition of ``meaningful"
segments.
The authors wish to design an efficient, robust algorithm for segmenting
arbitrary triangle meshes into meaningful parts.
This paper presents an algorithm for mesh segmentation based on the concept of
``catchment basins" or "watersheds". The algorithm uses the total curvature
of the surface as an indication of region boundaries. Each patch in the
resulting segmentation has a relatively consistent curvature throughout and is
bounded by areas of higher or drastically different curvature. The algorithm
contains a region merging step after applying the basic watershed segmentation
in order to make up for oversegmentation.
Watershed segmentation for images, extended in this paper to 3D meshes.
Without the region merging step, the watershed segmentation algorithm in this
paper suffers badly from oversegmentation; any small defects or noise allows
formation of bumps on the surface.
The algorithm behaves on four simple types of surfaces as follows:
- Cube: Each of the six faces of a cube is its own segment, and the
faces are separated from each other by ``walls" of high curvature.
- Cylinder: Similar to a cube, the two flat faces of a cylinder
are separated from the rest of the shape by walls of high curvature.
- Sphere: A sphere has constant curvature throughout and thus the
whole surface of a sphere is left as a single segment.
- Torus: A torus is divided into two regions: the boundary between
the two regions is the intersection of the torus with the torus with the plane
containing its centroid and all of the centroids of the circular
cross-sections of the torus.
The algorithm's behavior in the presence of additive, uniform noise is as
follows:
- For small levels of noise (2.5% to 5%), the boundaries of the torus
move, but the torus is still divided into two regions.
- For higher levels of noise (10%), the torus becomes oversegmented; the
36 regions of its segmentation have no meaning in terms of its geometry
- For the cube, small levels of noise have negligible effect on the
segment boundaries. For high levels of noise, the segmentation breaks down as
with the torus.
The algorithm shows strong sensitivity to the user-specified threshold in the
region merging step. For low threshold values, there are large numbers of
segments. As the threshold value increases, there are fewer, more meaningful
segments. This behavior holds for both simple and complex surfaces.
Segmentations from surface-based input data seems more prone to high frequency
artifacts than segmentations produced from volumetric data (isosurfaces of 3D
volumes).
The curvature computation method for surface meshes is prone to high frequency
aliasing. The coarseness of the grid sampling significantly affects the
segmentation that is produced. Smoothing the curvature computed from surface
meshes should significantly improve results in future work.
ctj