We recently introduced watershed cuts, a notion of watershed in edge-weighted graphs. In this paper, our main contribution is a thinning paradigm from which we derive three algorithmic watershed cut strategies: The first one is well suited to parallel implementations, the second one leads to a flexible linear-time sequential implementation, whereas the third one links the watershed cuts and the popular flooding algorithms. We state that watershed cuts preserve a notion of contrast, called connection value, on which several morphological region merging methods are (implicitly) based. We also establish the links and differences between watershed cuts, minimum spanning forests, shortest path forests, and topological watersheds. Finally, we present illustrations of the proposed framework to the segmentation of artwork surfaces and diffusion tensor images.

A point of a discrete object is called simple if it can be deleted from this object without altering topology. In this article, we present new characterizations of simple points which hold in dimensions 2, 3 and 4, and which lead to efficient algorithms for detecting such points. In order to prove these characterizations, we establish two confluence properties of the collapse operation which hold in the neighborhood of a point in spaces of low dimension. This work is settled in the framework of cubical complexes, which provides a sound topological basis for image analysis, and allows to retrieve the main notions and results of digital topology, in particular the notion of simple point.

We study the watersheds in edge-weighted graphs. We define the watershed cuts following the intuitive idea of drops of water flowing on a topographic surface. We first establish the consistency of these watersheds: They can be equivalently defined by their "catchment basins" (through a steepest descent property) or by the "dividing lines" separating these catchment basins (through the drop of water principle). Then, we prove, through an equivalence theorem, their optimality in terms of minimum spanning forests. Afterward, we introduce a linear-time algorithm to compute them. To the best of our knowledge, similar properties are not verified in other frameworks and the proposed algorithm is the most efficient existing algorithm, both in theory and in practice. Finally, the defined concepts are illustrated in image segmentation, leading to the conclusion that the proposed approach improves, on the tested images, the quality of watershed-based segmentations.

In Ref. 6, two similar characterizations of discrete surfaces of ℤ3 are proposed which are called strong 18-surfaces and strong 26-surfaces. The proposed characterizations consist in some natural global properties of surfaces. In this paper, we first give local necessary conditions for an object to be a strong 26-surface. An object satisfying these local properties is called a near strong 26-surface. Then we construct continuous analogs for near strong 26-surfaces and, using the continuous Jordan Theorem, we prove that the necessary local conditions previously introduced in fact give a complete local characterization of strong 26-surfaces: the class of near strong 26-surfaces coincides with the class of strong 26-surfaces.

In this paper, we propose an original method to segment bi-class images into regions. It is based on the use of low-level operators and works automatically, without any threshold or size criteria. This method is purely topological. We define a topology for grey-level images, called section topology, and two basic topological notions, the topological numbers and the topological values. We propose four fundamental operators built with these notions. Each of them consists of a simple iterative process which selectively modifies the section topology of an image in order to segment it.

Presents a new method for recognizing and locating an object in an image. The contours of the shapes are described by line segments. The basic idea consists in generating paths in a table where the columns represent the model segments and the rows the scene segments. Each path represents a matching between a part of the model contour and a part of the scene contour. The longest path is considered as the best match.>

The paper concerns computational models and languages for iterative cellular automata for image processing applications. The authors present some formal models, with different computational resources, that can be useful in the solution of certain algorithmic problems. They introduce some concepts such as memory splitting, conditional functions, dynamic neighborhood and supervisor automaton. The models defined lead to a parallel language structure that can express low-level image processing algorithms in a clear and concise way. The language allows a transparent description of the algorithms and can be easily expandable to reflect the needs of people working in different branches of image processing.>

A new characterization of 3D simple points has recently been proposed by the authors (2nd European Conf. Computer Vision (1992)). Unlike previous characterizations, it does not need the calculation of the genus or the number of holes. It only needs the computation of two connected components numbers in the neighborhood of the considered point. An implementation of this characterization is presented.>

A generalized distance transformation (GDT) of binary images and the related medial axis transformation (MAT) are discussed. These transformations are defined in a discrete space of arbitrary dimension and arbitrary grids. The GDT is based on successive morphological operations using alternatively N arbitrary structuring elements: N is called the period of the GDT. The GDT differs from the classical distance transformations based on a point-to-point distance. However, the well-known chessboard, city-block, and hexagonal distance transformations are special cases of the one-period GDT, whereas the octagonal distance transformation is a special case of the two-period GDT. In this paper, both one- and two-period GDTs are discussed. Different sequential algorithms are proposed for computing such GDTs. These algorithms need a maximum of two scannings of the image. The computation of the MAT is also discussed.>

An approach to the segmentation of a discrete 3-D object into a structure of characteristic topological primitives with attached qualitative features is proposed. This structure can be seen as a qualitative description of the object. The approach concentrates on topological properties of discrete surfaces. These surfaces may correspond to the external surface of the objects, or to the skeleton surface. The labeling algorithm is based on very local computations, allowing massively parallel and real-time computations.>

A parallel 3-D thinning algorithm which conserves medial surfaces is presented. A new characterization of simple points is proposed and some new topological predicates are given which are very simple to calculate. Some new geometrical predicates are also given. It is proved that the thinning operation based on those new predicates does not disconnect a 3-D object. Experiments show that the method gives a satisfactory result.>

A fast algorithm for skeletonization is presented. A derived grid and derived object are used to get a well-defined skeleton. This skeleton has several properties: one-point thickness, good centering, preservation of the object topological properties, reconstruction of the object from its skeleton. The construction of the skeleton involves three steps: first a distance function is constructed from the derived object, then basic points are determined, and finally, connecting paths are realized between these basic points. The algorithm needs only four sequential scans through the image and a following of the connecting paths.>

A generalized distance transformation of binary images based on successive Minkowski operations is discussed. This distance transformation is obtained by using a two-scan algorithm. A related medial axis for image compression is defined. As an example of the transformation's application, a fast algorithm for elementary morphological operations with an arbitrary structuring element is given.>