We introduce the homotopic alternating sequential filter as a new method for smoothing two-dimensional (2D) and three-dimensional (3D) objects in binary images. Unlike existing methods, our method offers a strict guarantee of topology preservation. This property is ensured by the exclusive use of homotopic transformations defined in the framework of digital topology. Smoothness is obtained by the use of morphological openings and closings by metric disks or balls of increasing radius, in the manner of an alternating sequential filter. The homotopic alternating sequential filter operates both on the object and on the background, in an equilibrated way. It takes an original image X and a control image C as input, and smooths X "as much as possible" while respecting the topology of X and geometrical constraints implicitly represented by C. Based on this filter, we introduce a general smoothing procedure with a single parameter which allows to control the degree of smoothing. Furthermore, the result of this procedure presents small variations in response to small variations of the parameter value. We also propose a method with no parameter for smoothing zoomed binary images in 2D or 3D while preserving topology.
In this paper, we investigate topological watersheds. For that purpose we introduce a notion of “separation between two points” of an image. One of our main results is a necessary and sufficient condition for a map G to be a watershed of a map F, this condition is based on the notion of separation. A consequence of the theorem is that there exists a (greedy) polynomial time algorithm to decide whether a map G is a watershed of a map F or not. We also show that, given an arbitrary total order on the minima of a map, it is possible to define a notion of “degree of separation of a minimum” relative to this order. This leads to another necessary and sufficient condition for a map G to be a watershed of a map F. At last we derive, from our framework, a new definition for the dynamics of a minimum.
The Marching Cubes algorithm is a popular method which allows the rendering of 3D binary images, or more generally of iso-surfaces in 3D digital gray-scale images. Yet the original version does not give satisfactory results from a topological point of view, more precisely the extracted mesh is not a coherent surface. This problem has been solved in the framework of digital topology, through the use of different connectivities for the object and the background, and the definition of ad-hoc templates. Another framework for discrete topology is based on an heterogeneous grid (introduced by E.D. Khalimsky) which is an order, or a discrete topological space in the sense of P.S. Alexandroff. These spaces possess nice topological properties, in particular, the notion of surface has a natural definition.
This article introduces a Marching Chains algorithm for the 3D Khalimsky grid H3. Given an object X which is a subset of H3, we define, in a natural way, the frontier of X which is also an order. We prove that this frontier order is always a union of surfaces. Then we show how to use frontier order to design a Marching Cubes-like algorithm. We discuss the implementation of such an algorithm and show the results obtained on both artificial and real objects.
Several approaches have been proposed for the study of topological properties of binary digital images: the digital topology, the connected ordered topological space approach, and the cell complex approach. The topology which is used in the last two approaches is a discrete topology. In fact, the datum of a discrete topology is equivalent to the datum of a partially ordered set (order). One of the authors has proposed a study of homotopy in orders, and has introduced the notion of (alpha) -simple point. An (alpha) -simple point is an 'inessential point' for the topology in orders. A fundamental characteristic concerning (alpha) -simple points is that they can be deleted in parallel from an object, while preserving its topological properties. This led us to propose, in a recent work, two parallel thinning algorithms based on the parallel deletion of (alpha) -simple points, for 2D and 3D binary images. Very few parallel thinning algorithms for 2D grayscale images have already been proposed. The most recent ones have been developed by extending binary notions with the cross-section topology. In the same way, we extend our previous works in orders to the case of 2D grayscale images, and we propose two parallel thinning algorithms for such images.
One of the authors has proposed a study of homotopy and simplicity in partially ordered sets (or posets). The notion of unipolar point was introduced: a unipolar point can be seen as an 'inessential' element for the topology. Thus, the iterative deletion of unipolar points constitutes a first thinning algorithm. We show in this paper, that such an algorithm does not 'thin enough' certain images. This is the reason why we use the notion of (alpha) -simple point, introduced in the framework of posets, in Ref. 1. The definition of such a point is recursive. As we can locally decide whether a point is (alpha) -simple, we can use classical techniques (such as a binary decision diagram) to characterize them more quickly. Furthermore, it is possible to remove in parallel (alpha) -simple points in a poset, while preserving the topology of the image. Then, we discuss the characterization of end points in order to produce various skeletons. Particularly, we propose a new approach to characterize surface end points. This approach permits us to keep certain junctions of surfaces. Then, we propose very simple parallel algorithms based on the deletion of (alpha) - simple points, consisting in the repetition of two subiterations.
In recent work, we introduced topological notions for grayscale images based on a cross-section topology. In particular, the notion of destructible point, which corresponds to the classical notion of simple point, allows to build operators that simplify a grayscale image while preserving its topology. In this paper, we introduce new notions and operators in the framework of the cross-section topology. In particular, the notion of (lambda) -destructible point allows us to selectively modify the topology, based on a local contrast parameter (lambda) . By combining homotopic and non-homotopic operators, we introduce new methods for filtering, thinning, segmenting and enhancing grayscale images.
In this paper, we introduce a new motion of surfaces in Z3, called simplicity surfaces. In the continuous space, a surface is characterized by the fast that the neighborhood of each point of the surface is homomorphic to an Euclidean disc. The chosen approach consists in characterizing a surface in Z3 by the condition that the neighborhood of any point constitutes a simple closed curve. The major problem is than, if we consider only the usual adjacency relations, this condition is not satisfied even for the simplest surfaces, e.g. digital planes. We thus have to consider another relation. We use a relation for points in Z3 which is based on the notion of homotopy. This allows to define a surface as a connected set of points in which the neighborhood of each point constitutes a simples closed curve for this relation; such a surface is called a simplicity surface. We give two different local characterizations of simplicity surfaces. We then show that a simplicity surface may also be seen as a combinatorial manifold, that is, a set of faces which are linked by an adjacency relation. Furthermore, we show that the main existing notions of surfaces, for the 6- and the 26- adjacency, are also simplicity surfaces.
We propose an original approach to the watershed problem, based on topology. We introduce a 1D topology for grayscale images, and more generally for weighted graphs. This topology allows us to precisely define a topological grayscale transformation that generalizes the action of a watershed transformation. Furthermore, we propose an efficient algorithm to compute this topological grayscale transformation,a nd we give an example of application to image segmentation.
A basic property of a simple closed surface is the Jordan property: the complement of the surface has two connected components. We call back-component any such component, and the union of a back-component and the surface is called the closure of this back-component. In an earlier work, we introduced the notion of strong surface as a surface which satisfies a global homotopy property: the closure of a back- component is strongly homotopic to that back-component. It means that we can homotopically remove any subset of a strong surface from the closure of a back-component. It was proved that the simple closed 26-surfaces defined by Morgenthaler and Rosenfeld, and the simple closed 18- surfaces defined by one of the authors are both strong surfaces. In this paper, some necessary local conditions for strong 26-surfaces are present. This is a first step towards a complete local characteristics of these surfaces.
We consider a cross-section topology that is defined on grayscale images. The main interest of this topology is that it keeps track of the grayscale information of an image. We define some basic notions relative to that topology. Furthermore, we indicate how to acquire a homotopic kernel and a leveling kernel. Such kernels can be seen as "ultimate" topological simplifications of an image. A kernel of a real image, though simplified, is still an intricated image from a topological point of view. We introduce the notion of an irregular region. The iterative removal of irregular regions in a kernel enables us to selectively simplify the topology of the image. Through an example, we show that this notion leads to a method for segmenting some grayscale images without the need to define and tune
This work addresses a catchment basins merging algorithm developed to automate the segmentation of microscopic images, which is directly derived from the traditional non- hierarchical watershed algorithm. The proposed merging algorithm, based on digital topology concepts, employs regional criteria to merge the non-significant minima. It can be classified as a region growing method by flooding simulation, working at the scale of the main structures. The shape of the structures is absolutely irrelevant to the merging process. As a characteristic of the flooding simulation methods, the gray level image is viewed as a relief where each gray level is assigned a height. In the proposed method the relief is always flooded from all its local minima which are progressively detected and merged as the flooding takes place. The catchment basins merging process is guided by two parameters: a depth criterion and an area criterion. This solution suppresses the characteristic over-segmentation of the traditional watershed enabling the direct segmentation of the original image without the need of a previous pre-processing step. Due to the automatic detection of all local minima there is not need of the explicit marker extraction step often required by other flooding simulation methods. It is shown that this solution produces excellent segmentation results allowing the characterization of several materials from their microscopic images.
This work reports and illustrates the application of morphological and topological algorithms to enhance sketch contours on infrared photographies of wood paintings. the procedure involves two steps: the application of a morphological chain to enhance the desired sketches, followed by a topological chain to 'clean up' the undesired artifacts generated at the first step.
We consider a cross-section topology which is defined on grayscale images. The main interest of this topology is that it keeps track of the grayscale information of an image. We define some basic notions relative to that topology. Furthermore, we indicate how to get an homotopic kernel. Such a kernel may be seen as an `ultimate' topological simplification of an image. A kernel of a real image, though simplified, is still an intricated image from a topological point of view. We introduce the notion of irregular region. The iterative method of irregular regions in a kernel allows to selectively simplify the topology. Through an example, we show that this notion leads to a method for segmenting some grayscale images without the need of defining and tuning parameters.
A simple point of an object is a point whose removal does not change the topology. However, the simultaneous deletion of simple points may change the topology. A popular way for overcoming this problem is to use a directional strategy. This method has good properties in 2D discrete spaces but it does not work in 3D. Through the notion of P-simple point we propose a general strategy for removing points in parallel without altering the topology of a 3D space. We derive some new sufficient conditions such that any parallel thinning algorithm satisfying these conditions is ensured to preserve topology.
A three-dimensional parallel thinning algorithm is presented. This algorithm works in cubic grid with the 26-connectivity. It is based upon two topological numbers introduced elsewhere. These numbers allow us to check if a point is simple or not and to detect end points. The strategy which is used for removing points in parallel without altering the topology of the image is a strategy based upon subfields: the cubic grid is divided into 8 subfields which are successively activated. The use of 4 subfields is also considered. One major interest of the subfield approach is that it is `complete,' i.e., all simple points which are not considered as skeletal points are removed. The proposed algorithm allows us to get a curve skeleton, a surface skeleton as well as a topological kernel of the objects. Furthermore it is possible to implement it by using only Boolean conditions.