Laurent Najman

Connected filtering on tree-based shape-spaces

By Yongchao Xu, Thierry Géraud, Laurent Najman

2015-06-05

In IEEE Transactions on Pattern Analysis and Machine Intelligence

Abstract

Connected filters are well-known for their good contour preservation property. A popular implementation strategy relies on tree-based image representations: for example, one can compute an attribute characterizing the connected component represented by each node of the tree and keep only the nodes for which the attribute is sufficiently high. This operation can be seen as a thresholding of the tree, seen as a graph whose nodes are weighted by the attribute. Rather than being satisfied with a mere thresholding, we propose to expand on this idea, and to apply connected filters on this latest graph. Consequently, the filtering is performed not in the space of the image, but in the space of shapes built from the image. Such a processing of shape-space filtering is a generalization of the existing tree-based connected operators. Indeed, the framework includes the classical existing connected operators by attributes. It also allows us to propose a class of novel connected operators from the leveling family, based on non-increasing attributes. Finally, we also propose a new class of connected operators that we call morphological shapings. Some illustrations and quantitative evaluations demonstrate the usefulness and robustness of the proposed shape-space filters.

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

Efficient computation of attributes and saliency maps on tree-based image representations

By Yongchao Xu, Edwin Carlinet, 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

Tree-based image representations are popular tools for many applications in mathematical morphology and image processing. Classically, one computes an attribute on each node of a tree and decides whether to preserve or remove some nodes upon the attribute function. This attribute function plays a key role for the good performance of tree-based applications. In this paper, we propose several algorithms to compute efficiently some attribute information. The first one is incremental computation of information on region, contour, and context. Then we show how to compute efficiently extremal information along the contour (e.g., minimal gradient’s magnitude along the contour). Lastly, we depict computation of extinction-based saliency map using tree-based image representations. The computation complexity and the memory cost of these algorithms are analyzed. To the best of our knowledge, except information on region, none of the other algorithms is presented explicitly in any state-of-the-art paper.

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

Tree-based morse regions: A topological approach to local feature detection

By Yongchao Xu, Thierry Géraud, Pascal Monasse, Laurent Najman

2014-10-03

In IEEE Transactions on Image Processing

Abstract

This paper introduces a topological approach to local invariant feature detection motivated by Morse theory. We use the critical points of the graph of the intensity image, revealing directly the topology information as initial “interest” points. Critical points are selected from what we call a tree-based shape-space. Specifically, they are selected from both the connected components of the upper level sets of the image (the Max-tree) and those of the lower level sets (the Min-tree). They correspond to specific nodes on those two trees: (1) to the leaves (extrema) and (2) to the nodes having bifurcation (saddle points). We then associate to each critical point the largest region that contains it and is topologically equivalent in its tree. We call such largest regions the Tree-Based Morse Regions (TBMR). TBMR can be seen as a variant of MSER, which are contrasted regions. Contrarily to MSER, TBMR relies only on topological information and thus fully inherit the invariance properties of the space of shapes (e.g., invariance to affine contrast changes and covariance to continuous transformations). In particular, TBMR extracts the regions independently of the contrast, which makes it truly contrast invariant. Furthermore, it is quasi parameter-free. TBMR extraction is fast, having the same complexity as MSER. Experimentally, TBMR achieves a repeatability on par with state-of-the-art methods, but obtains a significantly higher number of features. Both the accuracy and the robustness of TBMR are demonstrated by applications to image registration and 3D reconstruction.

Continue reading

Practical genericity: Writing image processing algorithms both reusable and efficient

By Roland Levillain, Thierry Géraud, Laurent Najman, Edwin Carlinet

2014-09-10

In Progress in pattern recognition, image analysis, computer vision, and applications – proceedings of the 19th iberoamerican congress on pattern recognition (CIARP)

Abstract

An important topic for the image processing and pattern recognition community is the construction of open source and efficient libraries. An increasing number of software frameworks are said to be generic: they allow users to write reusable algorithms compatible with many input image types. However, this design choice is often made at the expense of performance. We present an approach to preserve efficiency in a generic image processing framework, by leveraging data types features. Variants of generic algorithms taking advantage of image types properties can be defined, offering an adjustable trade-off between genericity and efficiency. Our experiments show that these generic optimizations can match dedicated code in terms of execution times, and even sometimes perform better than routines optimized by hand. Digital Topology software should reflect the generality of the underlying mathematics: mapping the latter to the former requires genericity. By designing generic solutions, one can effectively reuse digital topology data structures and algorithms. We propose an image processing framework focused on the Generic Programming paradigm in which an algorithm on the paper can be turned into a single code, written once and usable with various input types. This approach enables users to design and implement new methods at a lower cost, try cross-domain experiments and help generalize results.

Continue reading

Espaces des formes basés sur des arbres : Définition et applications en traitement d’images et vision par ordinateur

By Yongchao Xu, Thierry Géraud, Laurent Najman

2014-07-01

In Actes du 19ème congrès national sur reconnaissance des formes et l’intelligence artificielle (RFIA)

Abstract

Le cadre classique des filtres connexes consiste à enlever d’un graphe certaines de ses composantes connexes. Pour appliquer ces filtres, il est souvent utile de transformer une image en un arbre de composantes, et on élague cet arbre pour simplifier l’image de départ. Les arbres ainsi formés ont des propriétés remarquables pour la vision par ordinateur. Une première illustration de leur intérêt est la définition d’un détecteur de zones d’intérêt, vraiment invariant aux changements de contraste, qui nous permet d’obtenir des résultats à l’état de l’art en recalage d’images et en reconstruction 3D à base d’images. Poursuivant dans l’utilisation de ces arbres, nous proposons d’élargir le cadre des filtres connexes. Pour cela, nous introduisons la notion d’espaces des formes basés sur des arbres : au lieu de filtrer des composantes connexes du graphe correspondant à l’image, nous proposons de filtrer des composantes connexes du graphe donné par l’arbre des composantes de l’image. Ce cadre général, que nous appelons morphologie basée sur les formes, peut être utilisé pour la détection et la segmentation d’objets, l’obtention de segmentations hiérarchiques, et le filtrage d’images. De nombreuses applications et illustrations montrent l’intérêt de ce cadre.

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

Meaningful disjoint level lines selection

By Yongchao Xu, Edwin Carlinet, Thierry Géraud, Laurent Najman

2014-05-26

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

Abstract

Many methods based on the morphological notion of shapes (i.e., connected components of level sets) have been proved to be very efficient in shape recognition and shape analysis. The inclusion relationship of the level lines (boundaries of level sets) forms the tree of shapes, a tree-based image representation with a high potential. Numerous applications using this tree representation have been proposed. In this article, we propose an efficient algorithm that extracts a set of disjoint level lines in the image. These selected level lines yields a simplified image with clean contours, which also provides an intuitive idea about the main structure of the tree of shapes. Besides, we obtain a saliency map without transition problems around the contours by weighting level lines with their significance. Experimental results demonstrate the efficiency and usefulness of our method.

Continue reading

Search

Tags