Nicolas Boutry

A tutorial on well-composedness

By Nicolas Boutry, Thierry Géraud, Laurent Najman

2017-10-12

In Journal of Mathematical Imaging and Vision

Abstract

Due to digitization, usual discrete signals generally present topological paradoxes, such as the connectivity paradoxes of Rosenfeld. To get rid of those paradoxes, and to restore some topological properties to the objects contained in the image, like manifoldness, Latecki proposed a new class of images, called well-composed images, with no topological issues. Furthermore, well-composed images have some other interesting properties: for example, the Euler number is locally computable, boundaries of objects separate background from foreground, the tree of shapes is well-defined, and so on. Last, but not the least, some recent works in mathematical morphology have shown that very nice practical results can be obtained thanks to well-composed images. Believing in its prime importance in digital topology, we then propose this state-of-the-art of well-composedness, summarizing its different flavours, the different methods existing to produce well-composed signals, and the various topics that are related to well-composedness.

Continue reading

Well-composedness in Alexandrov spaces implies digital well-composedness in $Z^n$

By Nicolas Boutry, Laurent Najman, Thierry Géraud

2017-06-01

In Discrete geometry for computer imagery – proceedings of the 20th IAPR international conference on discrete geometry for computer imagery (DGCI)

Abstract

In digital topology, it is well-known that, in 2D and in 3D, a digital set $X \subseteq Z^n$ is digitally well-composed (DWC), i.e., does not contain any critical configuration, if its immersion in the Khalimsky grids $H^n$ is well-composed in the sense of Alexandrov (AWC), i.e., its boundary is a disjoint union of discrete $(n-1)$-surfaces. We show that this is still true in $n$-D, $n \geq 2$, which is of prime importance since today 4D signals are more and more frequent.

Continue reading

La pseudo-distance du dahu

By Edwin Carlinet, Yongchao Xu, Nicolas Boutry, Thierry Géraud

2017-03-21

In Actes d’ORASIS

Abstract

La distance de la barrière minimum est définie comme le plus petit intervalle de l’ensemble des niveaux de gris le long d’un chemin entre deux points dans une image. Pour cela, on considère que l’image est un graphe à valeurs sur les sommets. Cependant, cette définition ne correspond pas à l’interprétation d’une image comme étant une carte d’élévation, c’est-à-dire, un paysage continu d’une manière ou d’une autre. En se plaçant dans le cadre des fonctions multivoques, nous présentons une nouvelle définition pour cette distance. Cette définition, compatible avec l’interprétation paysagère, est dénuée de problèmes topologiques bien qu’en restant dans un monde discret. Nous montrons que la distance proposée est reliée à la structure morphologique d’arbre des formes, qui permet de surcroît un calcul rapide et exact de cette distance. Cela se démarque de sa définition classique, pour laquelle le seul calcul rapide n’est qu’approximatif.

Continue reading

Introducing the Dahu pseudo-distance

By Thierry Géraud, Yongchao Xu, Edwin Carlinet, Nicolas Boutry

2017-02-23

In Mathematical morphology and its application to signal and image processing – proceedings of the 13th international symposium on mathematical morphology (ISMM)

Abstract

The minimum barrier (MB) distance is defined as the minimal interval of gray-level values in an image along a path between two points, where the image is considered as a vertex-valued graph. Yet this definition does not fit with the interpretation of an image as an elevation map, i.e. a somehow continuous landscape. In this paper, based on the discrete set-valued continuity setting, we present a new discrete definition for this distance, which is compatible with this interpretation, while being free from digital topology issues. Amazingly, we show that the proposed distance is related to the morphological tree of shapes, which in addition allows for a fast and exact computation of this distance. That contrasts with the classical definition of the MB distance, where its fast computation is only an approximation.

Continue reading

A study of well-composedness in $n$-d

By Nicolas Boutry

2016-12-01

In

Abstract

Digitization of the real world using real sensors has many drawbacks; in particular, we loose “well-composedness” in the sense that two digitized objects can be connected or not depending on the connectivity we choose in the digital image, leading then to ambiguities. Furthermore, digitized images are arrays of numerical values, and then do not own any topology by nature, contrary to our usual modeling of the real world in mathematics and in physics. Loosing all these properties makes difficult the development of algorithms which are “topologically correct” in image processing: e.g., the computation of the tree of shapes needs the representation of a given image to be continuous and well-composed; in the contrary case, we can obtain abnormalities in the final result. Some well-composed continuous representations already exist, but they are not in the same time $n$-dimensional and self-dual. In fact, $n$-dimensionality is crucial since usual signals are more and more 3-dimensional (like 2D videos) or 4-dimensional (like 4D Computerized Tomography-scans), and self-duality is necessary when a same image can contain different objects with different contrasts. We developed then a new way to make images well-composed by interpolation in a self-dual way and in $n$-D; followed with a span-based immersion, this interpolation becomes a self-dual continuous well-composed representation of the initial $n$-D signal. This representation benefits from many strong topological properties: it verifies the intermediate value theorem, the boundaries of any threshold set of the representation are disjoint union of discrete surfaces, and so on.

Continue reading

How to make $n$D images well-composed without interpolation

By Nicolas Boutry, Thierry Géraud, Laurent Najman

2015-05-14

In Proceedings of the IEEE international conference on image processing (ICIP)

Abstract

Latecki et al. have introduced the notion of well-composed images, i.e., a class of images free from the connectivities paradox of discrete topology. Unfortunately natural and synthetic images are not a priori well-composed, usually leading to topological issues. Making any $n$D image well-composed is interesting because, afterwards, the classical connectivities of components are equivalent, the component boundaries satisfy the Jordan separation theorem, and so on. In this paper, we propose an algorithm able to make $n$D images well-composed without any interpolation. We illustrate on text detection the benefits of having strong topological properties.

Continue reading

How to make $n$D functions digitally well-composed in a self-dual way

By Nicolas Boutry, Thierry Géraud, Laurent Najman

2015-04-07

In Mathematical morphology and its application to signal and image processing – proceedings of the 12th international symposium on mathematical morphology (ISMM)

Abstract

Latecki et al. introduced the notion of 2D and 3D well-composed images, i.e., a class of images free from the “connectivities paradox” of digital topology. Unfortunately natural and synthetic images are not a priori well-composed. In this paper we extend the notion of “digital well-composedness” to $n$D sets, integer-valued functions (gray-level images), and interval-valued maps. We also prove that the digital well-composedness implies the equivalence of connectivities of the level set components in $n$D. Contrasting with a previous result stating that it is not possible to obtain a discrete $n$D self-dual digitally well-composed function with a local interpolation, we then propose and prove a self-dual discrete (non-local) interpolation method whose result is always a digitally well-composed function. This method is based on a sub-part of a quasi-linear algorithm that computes the morphological tree of shapes.

Continue reading

Une généralisation du <i>bien-composé</i> à la dimension $n$

By Nicolas Boutry, Thierry Géraud, Laurent Najman

2014-11-17

In

Abstract

La notion de bien-composé a été introduite par Latecki en 1995 pour les ensembles et les images 2D et pour les ensembles 3D en 1997. Les images binaires bien-composées disposent d’importantes propriétés topologiques. De plus, de nombreux algorithmes peuvent tirer avantage de ces propriétés topologiques. Jusqu’à maintenant, la notion de bien-composé n’a pas été étudiée en dimension $n$, avec $n > 3$. Dans le travail présenté ici, nous démontrons le théorème fondamental de l’équivalence des connexités pour un ensemble bien-composé, puis nous généralisons la caractérisation des ensembles et des images bien-composés à la dimension $n$.

Continue reading

On making $n$D images well-composed by a self-dual local interpolation

By Nicolas Boutry, Thierry Géraud, Laurent Najman

2014-05-28

In Proceedings of the 18th international conference on discrete geometry for computer imagery (DGCI)

Abstract

Natural and synthetic discrete images are generally not well-composed, leading to many topological issues: connectivities in binary images are not equivalent, the Jordan Separation theorem is not true anymore, and so on. Conversely, making images well-composed solves those problems and then gives access to many powerful tools already known in mathematical morphology as the Tree of Shapes which is of our principal interest. In this paper, we present two main results: a characterization of 3D well-composed gray-valued images; and a counter-example showing that no local self-dual interpolation with a classical set of properties makes well-composed images with one subdivision in 3D, as soon as we choose the mean operator to interpolate in 1D. Then, we briefly discuss various constraints that could be interesting to change to make the problem solvable in nD.

Continue reading

Search

Tags