Abstract
This work is settled in the framework of abstract simplicial complexes. We propose a definition of a watershed and of a collapse (i.e., a homotopic retraction) for maps defined on pseudomanifolds of arbitrary dimension. Then, we establish two important results linking watersheds and homotopy. The first one generalizes a property known for distance transforms in a continuous setting to any map on pseudomanifolds: a watershed of any map is a subset of an ultimate collapse of the support of this map. The second result establishes, through an equivalence theorem, a deep link between watershed and collapse of maps: any watershed of any map can be straightforwardly obtained from an ultimate collapse of this map, and conversely any ultimate collapse of the initial map straightforwardly induces a watershed.
Similar content being viewed by others
Notes
Note that some of these properties were first presented in a conference article [24] without proof.
Note that all simplicial complexes considered in this paper are finite. Indeed, in general, the extension of the proposed notions to the case of infinite complexes is not direct and is beyond the scope of this paper.
A property similar to Property 10 was proposed in [52] (Lemma 3.1) for the so-called \(k\)-deletable sets in the 2D square grid.
References
Arcelli, C., Di Baja, G.S.: A width-independent fast thinning algorithm. IEEE Trans. Pattern Anal. Mach. Intell. 7(4), 463–474 (1985)
Attene, M., Katz, S., Mortara, M., Patane, G., Spagnuolo, M., Tal, A.: Mesh segmentation—a comparative study. In: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006, SMI ’06, 7 pp., 2006
Bertrand, G.: On topological watersheds. J. Math. Imaging Vis. 22(2–3), 217–230 (2005)
Bertrand, G.: On critical kernels. Comptes Rendus de l’Académie des Sciences. Série Math. I 345, 363–367 (2007)
Bertrand, G., Couprie, M.: Two-dimensional parallel thinning algorithms based on critical kernels. J. Math. Imaging Vis. 31(1), 35–56 (2008)
Bertrand, G., Everat, J.C., Couprie, M.: Image segmentation through operators based upon topology. J. Electron. Imaging 6(4), 395–405 (1997)
Bertrand, G., Couprie, M., Cousty, J., Najman, L.: Chapter 3—Watersheds in discrete spaces. In: Najman Laurent, T.H. (ed.) Mathematical Morphology: From Theory to Applications, pp. 81–107. ISTE/Wiley, London/New York (2010)
Beucher, S., Meyer, F.: The morphological approach to segmentation: the watershed transformation. In: Dougherty, E. (ed.) Mathematical Morphology in Image Processing, pp. 443–481. Marcel Decker, New York (1993)
Bing, R.: Some aspects of the topology of 3-manifolds related to the Poincaré conjecture. In: Lectures on Modern Mathematics, vol. 2, pp. 93–128. Wiley, New York (1964)
Blum, H.: An associative machine for dealing with the visual field and some of its biological implications. In: Bernard, E.E., Kare, M.R. (eds.) 2nd Annual Bionics Symposium, Cornell University. Plenum Press, New York (1961)
Blum, H.: A transformation for extracting descriptors of shape. In: Models for the Perception of Speech and Visual Forms, pp. 362–380. MIT Press, Cambridge (1967)
Boussinesq, J.: Essai sur la théorie des eaux courantes. Mémoires présentés par divers savants à l’Académie des Sciences pp. 162–178 (1872). Digression sur les thalwegs et les faîtes à la surface du sol et sur leur rapports avec les lignes de déclivités minima. Institut de France
Cardoso, M., Clarkson, M., Modat, M., Ourselin, S.: Longitudinal cortical thickness estimation using Khalimsky’s cubic complex. In: Fichtinger, G., Martel, A., Peters, T. (eds.) Medical Image Computing and Computer-Assisted Intervention—MICCAI 2011. Lecture Notes in Computer Science, vol. 6892, pp. 467–475. Springer, Berlin (2011)
Cardoso, M., Clarkson, M., Modat, M., Ourselin, S.: On the extraction of topologically correct thickness measurements using Khalimsky’s cubic complex. In: Székely, G., Hahn, H. (eds.) Information Processing in Medical Imaging, Lecture Notes in Computer Science, vol. 6801. Springer, Berlin, pp. 159–170 (2011)
Cayley, A.: On contour and slope lines. Philos Mag Ser 4 18, 264–268 (1859)
Chaussard, J., Couprie, M.: Surface thinning in 3D cubical complexes. In: Wiederhold, P., Barneva, R.P. (eds.) Combinatorial Image Analysis, 13th International Workshop, IWCIA 2009, Proceedings. Lecture Notes in Computer Science, vol. 5852, pp. 135–148. Springer, Berlin (2009)
Comic, L., Mesmoudi, M.M., Floriani, L.D.: Smale-like decomposition and Forman theory for discrete scalar fields. In: Debled-Rennesson, I. et al. (eds.) Discrete Geometry for Computer Imagery. Lecture Notes in Computer Science, vol. 6607, pp. 477–488. Springer, Berlin (2011)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)
Couprie, M., Bertrand, G.: Topological grayscale watershed transform. Proc. SPIE Vis. Geom. V 3168, 136–146 (1997)
Couprie, M., Bertrand, G.: New characterizations of simple points in 2D, 3D, and 4D discrete spaces. IEEE Trans. Pattern Anal. Mach. Intell. 31(4), 637–648 (2009)
Couprie, M., Bezerra, F.N., Bertrand, G.: Topological operators for grayscale image processing. J. Electron. Imaging 10(4), 1003–1015 (2001)
Cousty, J., Bertrand, G., Couprie, M., Najman, L.: Fusion graphs: merging properties and watersheds. J. Math. Imaging Vis. 30(1), 87–104 (2008)
Cousty, J., Najman, L., Bertrand, G., Couprie, M.: Weighted fusion graphs: merging properties and watersheds. DAM 156(15), 3011–3027 (2008)
Cousty, J., Bertrand, G., Couprie, M., Najman, L.: Collapses and watersheds in pseudomanifolds. In: Wiederhold, P., Barneva, R.P. (eds.) Combinatorial Image Analysis, 13th International Workshop, IWCIA 2009, Proceedings. Lecture Notes in Computer Science, vol. 5852, pp. 397–410. Springer, Berlin (2009)
Cousty, J., Bertrand, G., Najman, L., Couprie, M.: Watershed cuts: minimum spanning forests and the drop of water principle. IEEE Trans. Pattern Anal. Mach. Intell. 31(8), 1362–1374 (2009)
Cousty, J., Bertrand, G., Najman, L., Couprie, M.: Watershed cuts: thinnings, shortest-path forests and topological watersheds. IEEE Trans. Pattern Anal. Mach. Intell. 32(5), 925–939 (2010)
de Saint-Venant, M.: Surfaces à plus grande pente constituées sur des lignes courbes. Bulletin de la Soc. Philomath. de Paris, pp. 24–30 (1852)
Digabel, H., Lantuéjoul, C.: Iterative algorithms. In: 2nd European Symposium Quantitative Analysis of Microstructures in Material Science, Biology and Medicine, pp. 85–89 (1978)
Edelsbrunner, H., Harer, J.: The persistent Morse complex segmentation of a 3-manifold. In: Magnenat-Thalmann, N. (ed.) Modelling the Physiological Human. Lecture Notes in Computer Science, vol. 5903, pp. 36–50. Springer, Berlin (2009)
Floriani, L.D., Mesmoudi, M.M., Danovaro, E.: A Smale-like decomposition for discrete scalar fields. In: Proceedings 16th ICPR on Pattern Recognition, pp. 184–187 (2002)
Jerse, G., Kosta, N.M.: Ascending and descending regions of a discrete Morse function. Comput. Geom. 42(6–7), 639–651 (2009)
Jordan, C.: Nouvelles observations sur les lignes de faîtes et de thalweg. Comptes Rendus des Séances de l’Académie des Sciences 75, 1023–1025 (1872)
Kong, T.Y.: Topology-preserving deletion of 1’s from 2-, 3- and 4-dimensional binary images. In: Ahronovitz, E., Fiorio, C. (eds.) Discrete Geometry for Computer Imagery. Lecture Notes in Computer Science, vol. 1347, pp. 3–18. Springer, Berlin (1997)
Kong, T., Rosenfeld, A.: Digital topology: introduction and survey. Comput. Vis. Graphics Image Process. 48(3), 357–393 (1989)
Kovalevsky, V.A.: Finite topology as applied to image analysis. Comput. Vis. Graph. Image Process. 46(2), 141–161 (1989)
Lavoué, G., Vandeborre, J.P., Benhabiles, H., Daoudi, M., Huebner, K., Mortara, M., Spagnuolo, M.: SHREC’12 Track: 3D mesh segmentation. In: Eurographics 2012 Workshop on 3D Object Retrieval, pp. 93–99. Cagliari, Italie (2012)
Lieutier, A.: Any open bounded subset of \(\text{ R }^{{\rm n}}\) has the same homotopy type as its medial axis. Computer-Aided Des. 36(11), 1029–1046 (2004)
Liu, L., Chambers, E.W., Letscher, D., Ju, T.: A simple and robust thinning algorithm on cell complexes. Comput. Graph. Forum 29(7), 2253–2260 (2010)
Mangan, A.P., Whitaker, R.T.: Partitioning 3D surface meshes using watershed segmentation. IEEE Trans. Vis. Comput. Graph. 5(4), 308–321 (1999)
Matheron, G.: Quelques propriétés topologiques du squelette. http://cg.ensmp.fr/bibliotheque/public/MATHERON_Rapport_00213.pdf. Rapport interne du centre de géoostatistique de l’Ecole Nationale Supérieure des Mines de Paris (1978)
Matheron, G.: Examples of topological properties of skeletons. In: J. Serra (ed.) Image Analysis and Mathematical Morphology, vol. 2: Theoretical Advances, chap. 11, pp. 217–238. Academic Press, London (1988)
Maunder, C.R.F.: Algebraic Topology. Dover, New York (1996)
Maxwell, J.: On hills and dales. Philos. Mag. 4 40, 421–427 (1870)
Najman, L., Schmitt, M.: Watershed of a continuous function. Signal Process. 38(1), 68–86 (1993)
Noël, L., Chaussard, J., Biri, V.: Coarse irradiance estimation using curvilinear skeleton. In: ACM SIGGRAPH 2012 Posters, pp. 101:1–101:1. ACM, New York (2012)
Philipp-Foliguet, S., Jordan, M., Najman, L., Cousty, J.: Artwork 3D model database indexing and classification. Pattern Recognit 44(3), 588–597 (2011)
Ranwez, V., Soille, P.: Order independent homotopic thinning for binary and grey tone anchored skeletons. Pattern Recognit. Lett. 23(6), 687–702 (2002)
Rivière, A.: Classification des points d’un ouvert d’un espace euclidien relativement à la distance au bord: Etude topologique et quantitative des classes obtenues. Ph.D. Thesis, Université de Paris-sud, centre d’Orsay (1987)
Rivière, A.: Nervure d’un Ouvert d’un Espace Euclidien. J. Sci. Univ. Tehran (Sec. A: Math) 1, 1–24 (1996)
Robins, V., Wood, P.J., Sheppard, A.P.: Theory and algorithms for constructing discrete Morse complexes from grayscale digital images. IEEE Trans. Pattern Anal. Mach. Intell. 33(8), 1646–1658 (2011)
Roerdink, J.B.T.M., Meijster, A.: The watershed transform: definitions, algorithms and parallelization strategies. Fundam. Inf. 41(1–2), 187–228 (2001)
Ronse, C.: A topological characterization of thinning. Theor. Comput. Sci. 43(0), 31–41 (1986)
Ronse, C.: Partial partitions, partial connections and connective segmentation. J. Math. Imaging Vis. 32(2), 97–125 (2008)
Saùde, A.V., Couprie, M., Lotufo, R.A.: Discrete 2D and 3D Euclidean medial axis in higher resolution. Image Vis. Comput. 27(4), 354–363 (2009)
Serra, J.: Image Analysis and Mathematical Morphology. Academic Press, New York (1982)
Shamir, A.: A survey on mesh segmentation techniques. Comput. Graph. Forum 27(6), 1539–1556 (2008)
Vincent, L., Soille, P.: Watersheds in digital spaces: an efficient algorithm based on immersion simulations. IEEE Trans. Pattern Anal. Mach. Intell. 13(6), 583–598 (1991)
Whitehead, J.H.C.: Simplicial spaces, nuclei and m-groups. Proc. Lond. Math. Soc s2–45(1), 243–327 (1939)
Acknowledgments
This work received funding from the Agence Nationale de la Recherche, contract ANR-2010-BLAN-0205-03.
Author information
Authors and Affiliations
Corresponding author
Appendix 1: Local cycles (proof of Lemma 5)
Appendix 1: Local cycles (proof of Lemma 5)
This appendix section is devoted to a property of pseudomanifolds that allows Lemma 5 to be established. Let us first illustrate this property on an example. In Fig. 11, the set \(\{x_0, \ldots , x_7\}\) is a cycle. This cycle is said “local to the point \(x\)” in the sense that any of its elements belongs to \(star({x})\). We prove in this appendix section that there exists a cycle local to each \((n-2)\)-face, in any \(n\)-pseudomanifold. More remarkably, Theorem 44 states, for any \((n-2)\)-face \(x\) of any \(n\)-pseudomanifold, that the set of \(n\)-faces of any connected component of \(star({x})\) is a cycle. From this result, the proof of Lemma 5 will be easily derived.
Let \(X\) be a nonempty set of \(n\)-faces of \(\mathbb {M}\). We say that \(X\) is a cycle (for \(\mathbb {M})\), if there exists a simple path \(\pi = \langle x_0, \ldots , x_\ell \rangle \) in \(\mathbb {M}\) such that \(X = \{x_0, \ldots , x_\ell \}\) and such that \(x_0 \cap x_\ell \) is a \((n-1)\)-face of \(\mathbb {M}\).
Theorem 44
Let \(x\) be an \((n-2)\)-face of \(\mathbb {M}\). The set of \(n\)-faces of any component of \(star({x})\) is a cycle for \(\mathbb {M}\).
In order to prove Theorem 44, we first state Lemma 45 and Corollary 46.
By its very definition, any \(k\)-face (with \(k \in \{0,\ldots ,n\}\)) contains \(k+1\) elements. Using this fact the following result can be proved easily.
Lemma 45
Let \(x\) be an \((n-2)\)-face of \(\mathbb {M}\), and let \(x_0\) be an \(n\)-face in \(star({x})\). Then, there exist exactly two distinct \((n-1)\)-faces in \(star({x})\) that are included in \(x_0\).
Corollary 46
Let \(x\) be an \((n-2)\)-face of \(\mathbb {M}\), and let \(x_1\) be an \(n\)-face in \(star({x})\). Then, there exist exactly two distinct \(n\)-faces \(x_0\) and \(x_2\) in \(star({x})\) whose intersections with \(x_1\) are \((n-1)\)-faces.
Proof
(of Theorem 44) Since any component of \(star({x})\) is a star, and since any nonempty star contains an \(n\)-face of \(\mathbb {M}\) (Remark 7), to study all components of \(star({x})\), it is sufficient to consider, for any \(n\)-face \(x_0\) in \(star({x})\), the component of \(star({x})\) that contains \(x_0\). Let \(x_0\) be any \(n\)-face in \(star({x})\), and let \(X\) be the set of all \(n\)-faces of the component of \(star({x})\) that contains \(x_0\).
-
(1)
Let us first prove that \(X\) includes a cycle. As a consequence of Corollary 46, we may always find \(x_1 \in X\) such that \(\langle x_0, x_1 \rangle \) is a simple path in \(star({x})\). Using again Corollary 46, we can construct, by induction, a simple path \(\pi = \langle x_0, \ldots , x_\ell \rangle \) in \(star({x})\) such that the only two \(n\)-faces in \(star({x})\) whose intersections with \(x_\ell \) are \((n-1)\)-faces of \(\mathbb {M}\) both belong to \(\{x_0, \ldots x_\ell \}\). By construction, one of these two \(n\)-faces is \(x_{\ell -1}\). Let us denote the other one by \(z\). Necessarily \(z = x_i\), for some \(i \in \{0, \ldots , \ell - 2\}\). If \(i > 0\), then \(x_{i-1}\), \(x_{i+1}\) and \(x_\ell \) are three distinct faces in \(star({x})\) whose intersections with \(x_i\) are \((n-1)\)-faces of \(\mathbb {M}\), which constitutes a contradiction with Corollary 46. Thus, we necessarily have \(z = x_0\). Hence, the set \(\{x_0, \ldots , x_\ell \} \subseteq X\) is a cycle.
-
(2)
Let us now prove, by contradiction, that \(X = \{x_0, \ldots , x_\ell \}\), hence, by (1), that \(X\) is a cycle. Suppose that there exists an element \(z\) in \(X\) such that \(z \notin \{x_0, \ldots , x_\ell \}\). By definition of \(X\), there exists, in \(star({x})\), a simple path \(\pi ' = \langle y_0, \ldots y_m \rangle \) from \(x_0 = y_0\) to \(z = y_m\). Let \(k \in \{1, \ldots , m\}\) be the lowest index such that \(y_k \notin \{x_0, \ldots , x_\ell \}\). Hence, \(y_{k-1} \in \{x_0, \ldots , x_\ell \}\). By Corollary 46, there exist exactly two \(n\)-faces in \(star({x})\), whose intersections with \(y_{k-1}\) are \((n-1)\)-faces of \(\mathbb {M}\). By construction of \(\pi \), these two \(n\)-faces belong to \(\{x_0, \ldots , x_\ell \}\). Hence, we have \(y_k \in \{x_0, \ldots , x_\ell \}\), a contradiction. Thus, since by (1), we have \(\{x_0, \ldots , x_\ell \} \subseteq X\), we deduce that \(X = \{ x_0, \ldots , x_\ell \}\). \(\square \)
Theorem 44 can be easily verified on Fig. 11. It can also be verified on the 2-pseudomanifold shown in Fig. 9b. In particular, let \(x\) denote the 0-face represented by a light gray dot. It can be seen that \(star({x})\) includes two components: one is made of the triangles and edges at the left of \(x\), and the other is made of the triangles and edges at the right of \(x\). It can be easily seen that the sets of triangles associated to these two components are cycles for the considered \(2\)-pseudomanifold.
Remark also that, if \(\mathbb {M}\) is a not a pseudomanifold, then Theorem 44 is, in general, not true. For instance, let us consider the complex of Fig. 9c, which is not a pseudomanifold, and let \(x\) be any of the two points that belong to the edge depicted in light gray (i.e., the pinching). The set \(star({x})\) itself is the only component of \(star({x})\). However, it can be verified that the set of all triangles in \(star({x})\) is not a cycle.
Proof
(of Lemma 5) Clearly, the two \(n\)-faces \(x_0\) and \(x_1\) belong to the same component \(X\) of \(star({x})\). The set \(X_n\) of all \(n\)-faces of \(X\) is, by Theorem 44, a cycle. Thus, as \(x_0\) and \(x_1\) belong to \(X\), it can be seen that there exists, in \(star({x})\), two distinct simple paths \(\pi = \langle y_0 = x_0, \ldots , y_\ell =x_1 \rangle \) and \(\pi ' = \langle z_0 = x_0, \ldots , z_m =x_1 \rangle \) from \(x_0\) to \(x_1\) such that \( \{y_1, \ldots , x_\ell \} \cap \{z_1, \ldots , z_{m-1}\} = \emptyset \). At least one of \(\pi \) and \(\pi '\) is a path in \(star({X}) \setminus \{y\}\). Therefore, \(x_0\) and \(x_1\) are linked for \(star({x}) \setminus \{y\}\). \(\square \)
Rights and permissions
About this article
Cite this article
Cousty, J., Bertrand, G., Couprie, M. et al. Collapses and Watersheds in Pseudomanifolds of Arbitrary Dimension. J Math Imaging Vis 50, 261–285 (2014). https://doi.org/10.1007/s10851-014-0498-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-014-0498-z