A triangle mesh in 3D is simply a collection of triangles and vertices that
approximate a surface in 3D. For computer vision tasks such as object
recognition, scene understanding, and feature modeling, however, a triangle
mesh alone is too low-level a description. Higher-level descriptions can be
obtained through mesh segmentation.
The minima rule is a human vision theory about how human perception
might decompose an object into its constituent parts. This rule defines
boundaries of parts to lie along lines of negative curvature minima. The
authors wish to use the minima rule in order to develop a mesh segmentation
algorithm that relates to how humans might decompose meshes.
This paper presents a mesh segmentation algorithm called fast marching
watersheds. The algorithm works by computing principal curvatures and
principal directions at each vertex of a given mesh, and then a hill-climbing
watershed algorithm finds regions bounded by contours of negative curvature
minima. These regions fit the definition of visual parts according to the
minima rule.
The fast marching watersheds mesh segmentation algorithm is able to segment a
scene consisting of a cylinder or prism standing on a flat plane into two
parts, namely the flat plane mesh and the cylinder or prism mesh. The
watersheds algorithm is subject to the drawbacks of the minima rule, however.
For instance, an L-shaped block of wood does not have a clear boundary
between its two orthogonal components, and so the watershed algorithm will
label the entire block as one segment. In general the segmentation appears to
be good for machine parts and other objects that have very sharp, uniform
curvature changes at part boundaries, whereas the segment boundaries tend to
be quite jagged in less uniform shapes such as a hand or the Stanford Bunny.
The fast marching watersheds algorithm, like all fast marching methods, runs
in time
O(n log n)
mathend000#.