Discrete Morse Functions and Watersheds

Authors

Gilles Bertrand, Nicolas Boutry, Laurent Najman

Journal

Journal of Mathematical Imaging and Vision (Special Edition)

Type

article

Date

2023-01-01

Abstract

Any watershed, when defined on a stack on a normal pseudomanifold of dimension $d$, is a pure $(d-1)$-subcomplex that satisfies a drop-of-water principle. In this paper, we introduce Morse stacks, a class of functions that are equivalent to discrete Morse functions. We show that the watershed of a Morse stack on a normal pseudomanifold is uniquely defined, and can be obtained with a linear-time algorithm relying on a sequence of collapses. Last, we prove that such a watershed is the cut of the unique minimum spanning forest, rooted in the minima of the Morse stack, of the facet graph of the pseudomanifold.

Bibtex (lrde.bib)

@Article{	  boutry.23.jmiv,
  author	= {Gilles Bertrand and Nicolas Boutry and Laurent Najman},
  title		= {Discrete Morse Functions and Watersheds},
  year		= {2023},
  journal	= {Journal of Mathematical Imaging and Vision (Special
		  Edition)},
  abstract	= {Any watershed, when defined on a stack on a normal
		  pseudomanifold of dimension $d$, is a pure
		  $(d-1)$-subcomplex that satisfies a drop-of-water
		  principle. In this paper, we introduce Morse stacks, a
		  class of functions that are equivalent to discrete Morse
		  functions. We show that the watershed of a Morse stack on a
		  normal pseudomanifold is uniquely defined, and can be
		  obtained with a linear-time algorithm relying on a sequence
		  of collapses. Last, we prove that such a watershed is the
		  cut of the unique minimum spanning forest, rooted in the
		  minima of the Morse stack, of the facet graph of the
		  pseudomanifold. }
}