Operations Fast Marching Watersheds Fast Marching Figure 1 Block diagram of Fast Marching Watersheds 2 Theory Our Fast Marching Watersheds algorithm?both the

Abstract:  name and the algorithm?derive inspiration from Fast Marching Methods [6] for computing shortest geodesic paths on a mesh. Kimmel and Sethian?s algorithm employs a heap data structure to control the geodesic ?walk ? across the surface of the mesh. For our watershed algorithm, we use a similar heap structure to control the ?flooding ? across the mesh. Unlike Kimmel and Sethian, however, our heap keys on local height values, and not cumulative geodesic distances, and it tracks the progression of regions, and not geodesic paths. These differences mark our contribution of extending Kimmel and Sethian?s algorithm into the different application of mesh segmentation and the formulation of a flooding-based watershed algorithm. A block diagram of the algorithm appears in Fig. 1. The input to the algorithm is a triangle mesh M. The first three blocks in the diagram create the marker set F ' on M to initialize the watershed algorithm. Then, the last block grows the marker regions into the final watershed catchment basins Mr that cover the entire mesh.