GéoDis 2014 – Sessions

Mercredi 26 novembre

  • 11:00-12:00 – Session D1 – Discrete differential geometry

    Yukiko Kenmochi, CR1 CNRS, LIGM Paris-Est

    A local algorithm to compute the normal vector of a 3D digital plane

    Jacques-Olivier Lachaud, Xavier Provençal, Tristan Roussillon

    Let P(N,u,w) be a 3D digital plane of normal vector N, shift u and thickness w. Given a point predicate that given a point X, answers the question « does X belongs to P(N,u,w) ? » Using this predicate, we want to provide a complete description of P(N,u,w) which consists of:

    – The values of N, u and w.
    – An upper leaning point (i.e. a point X such that <X,N> = w-1).
    – A lower leaning point (i.e. a point X such that <X,N> = 0).
    – a basis of the lattice { X | <X,N> = 0 }.
    – A Bezout vector (i.e. a vector V such that <V,N> = 1).

    Our approach tries to remain as local as possible and does not systematically test all points on the boundary of the plane. We developed a technique based on multidimensional continued fraction to test only relevant points.

    Digital geometry, digital planes, algorithm, continued fractions, Delaunay triangulation

    Binomial-based derivative estimation for noisy discretized curves with low complexity

    Henri-Alex Esbelin, Rémy Malgouyres

    Previous work on convolution-based derivative estimation provided an estimator with good theoretical and empirical properties of convergence. However it was expensive in term of computational complexity. We present here a new idea providing the same rate of convergence but with a very low computational complexity. This idea was previously used in connection with Taylor optimal masks. It turns out that it is more efficient with Binomial masks.

    digitized noisy curves, discrete derivation, derivative estimation, convolution

  • 13:20-14:20 – Session D2 – Exposé invité

    Aspects combinatoires en résolution de contraintes géométriques

    Pascal Schreck

  • 14:20-15:40 – Session D3 – Discrete transformations and discrete topology

    Isabelle Debled, PR, LORIA, Nancy

    Les Ω-AQA : représentation discrète des applications affines

    Éric Andres, Marie-Andrée Da Col, Laurent Fuchs, Gaëlle Largeteau-Skapin, Nicolas Magaud, Loïc Mazo, Rita Zrour

    La droite d’Harthong-Reeb est un modèle numérique du continu basé sur les entiers. La construction de cette droite en utilisant les Ω-entiers permet de décrire les objets mathématiques réels de manière discrète et constructive. En informatique graphique on est souvent amené à transformer des objets (images) par des applications affines réelles (rotations, translations, similitudes…). Des discrétisés (à une échelle donnée) de ces applications, appelées applications quasi-affines ont été définies et étudiées. Dans ce papier, nous rappelons les définitions et propriétés de base des Ω-entiers, de la droite de Harthong-Reeb et des applications quasi-affines. Nous montrons ensuite comment définir des Ω-AQAs qui sont les discrétisés «multi-échelle» des applications affines suivant la théorie des Ω-entiers et la définition initiale des AQAs. Enfin nous donnons les premières propriétés de ces Ω-AQAs.

    AQA, Applications Affines, Ω-entiers, droite de Harthong-Reeb

    Topological alterations of 3D digital images under rigid transformations

    Kacper Pluta, Yukiko Kenmochi, Nicolas Passat, Hugues Talbot, Pascal Romon

    Rigid transformations in R^n are known to preserve the shape, and are often applied to digital images. However, digitized rigid transformations, defined as digital functions from Z^n to Z^n do not preserve shapes in general; indeed, they are almost never bijective and thus alter the topology. In order to understand the causes of such topological alterations, we first study the possible loss of voxel information and modification of voxel adjacencies induced by applications of digitized rigid transformations to 3D digital images. We then show that even very simple structured images such as digital half-spaces may not preserve their topology under these transformations. This signifies that a simple extension of the two-dimensional solution for topology preservation cannot be made in three dimensions.

    digital topology, rigid transformation, digital image

    Extraction d’information homologique des objets discrets s’appuyant sur des graphes orientés

    Aldo Gonzalez-Lorenzo, Alexandra Bac, Jean-Luc Mari, Pedro Real

    Tout objet discret n-dimensionnel peut être transformé en complexe cubique, dont on peut étudier les groupes d’homologie pour mieux comprendre l’objet original. Une approche classique consiste à calculer la Forme Normale de Smith de matrices encodant le complexe cubique. Un certain nombre de travaux développent des méthodes permettant de réduire la taille de ces matrices. Dans cet article, nous proposons une nouvelle approche, initialement fondée sur la théorie discrète de Morse, calculant l’information homologique (nombres de Betti et cycles représentatifs) sans utiliser la Forme Normale de Smith. Notre approche s’applique en dimension quelconque et peut être utilisée pour n’importe quel type de complexe cellulaire régulier.

    Objet discret, complexe cubique, homologie, théorie de l’homologie effective, théorie discrète de Morse.

  • 16:00-17:40 – Session D4 – Methods and applications

    Isabelle Sivignon, CR1 CNRS, GipsaLab, Grenoble

    Feature extraction on digital surfaces

    Jérémy Levallois, David Coeurjolly, Jacques-Olivier Lachaud

    L’extraction de points caractéristiques à partir d’une forme a beaucoup été étudiée dans la littérature : de nombreux algorithmes traitent des maillages, des nuages de points, ou encore des données discrètes. Nous proposons une nouvelle méthode avec garanties théoriques permettant de les détecter sur des formes discrètes en analysant en espace-échelle des estimateurs récents de courbure ayant de bonnes propriétés mathématiques. Dans nos précédents travaux, nous avons proposé des estimateurs de courbures (moyennes, principales, gaussiennes) traitant des formes discrétisées 2D et 3D dont nous avons démontré la convergence asymptotique (sous certaines conditions de la forme), dépendant d’un paramètre : le rayon d’intégration. Nous proposons ici d’étudier ces estimateurs de courbures avec pour paramètre l’espace-échelle du rayon d’intégration, pour une forme discrète donnée. En analysant le comportement de ces estimateurs, nous pouvons en extraire les caractéristiques (singularités ponctuelles, arêtes, parties linéaires, parties à courbure constante, …) de la forme discrétisée.

    points caractéristiques, géométrie discrète, espace-échelle, courbure, convergence asymptotique, estimateur

    Re-projection without reconstruction

    Dimitri Pertin, Nicolas Normand

    Discrete tomography focuses on image representation by its discrete projections, and the related inversion algorithms (or image reconstruction). Our study is based on redundant representations (considering more than just few projections). We propose a new approach to compute further redundancy (i.e. new projections) from a set of existing projections. While this technique relies on the geometric properties of ghosts, which are elements of the 2D image that sum to zero following some projection directions, we show an equivalent method using 1D convolutions, thus avoiding the explicit image reconstruction. This technique has interesting applications in distributed storage systems, where the use of redundancy data is key for system reliability.

    Tomographie discrète, redondance, fantôme, convolution

    Segmentation de noeuds de bois à partir d’images tomodensitométriques : approches transversales et tangentielles

    Adrien Krähenbühl

    Le traitement automatique des images tomodensitométriques de bois doit permettre aux scieries d’optimiser le rendement et la qualité des planches. Les noeuds de bois sont le principal facteur de qualité d’une planche et déterminer une méthode de segmentation adaptée est un enjeu important. Cet article propose une revue de deux méthodes proposées qui considèrent les coupes transversales initiales et des coupes tangentielles aux cernes. Elles sont construites en intégrant les connaissances a priori sur la structure d’un tronc et la géométrie des objets étudiés, les noeuds. Ces connaissances permettent de spécialiser les approches théoriques classiques et d’obtenir des résultats très proches d’une segmentation manuelle. Ces deux approches entièrement automatiques sont comparées à trois approches nécessitant des marqueurs sur les objets ciblés, issues du cadre des Power Watershed. Elles sont implémentées dans le logiciel TKDetection, libre de droits.

    segmentation d’image, tomodensitométrie, nœuds de bois, analyse géométrique

    Watervoxel representation for supporting MRI volume segmentation

    David Cárdenas-Peña, Vaïa Machairas, Etienne Decencière, Thomas Walter, Germán Castellanos-Dominguez

    The use of Magnetic Resonance Image (MRI) volumes for neurology applications allows to study physiological and pathological processes on structural or functional properties of brain regions. For instance, to evaluate the evolution of neurodegenerative pathologies (like Alzheimer, dementia or schizophrenia) by estimating anatomical or functional structure changes through time or space. MRI is also employed for modeling head conductivity patterns required for brain mapping algorithms.

    For processing the MRI volumes, automatic techniques have been proposed, achieving significant performances. Nevertheless, for real medical applications, computational complexity is a constraint most of the techniques do not meet. Such a drawback is due to the large number of voxels in a regular MRI volume (10^7 voxels).

    Fortunately, due to the physical properties of head structures a brain MRI can be seen as a set of approximately piecewise constant regions. In this sense, it is possible to group all MRI voxels in a smaller set of meaningful elements with enforced connectivity, so reducing the high redundancy of voxel intensities. In the field of digital image processing such elements are known as superpixels (2D images) or supervoxels (3D volumes), and they are widely employed for reducing the computational complexity of imaging algorithms.

    For instance, superpixel representation was employed in a brain tissue classification task in [Verma et al., 2013]. Reported results in classification and complexity reduction proved that superpixels achieve significant performance at a lower cost than regular pixel representation. Also, authors in [Wu et al., 2014] proposed a brain tumor detection and segmentation algorithm based on conditional random fields using pixel-pairwise affinity and superpixel-level features. Presented results showed that superpixel-based appearance models allows to improve spatial smoothness while reducing the data sampling and computational cost. Finally, a medical segmentation method based on superpixel and fuzzy clustering was introduced in [Ji et al., 2014], where the well-known fuzzy c-means (FCM) algorithm is applied over previously computed superpixels to segment the brain in an MRI. Experiments revealed that the use of superpixels provides stability and artifact robustness to the FCM algorithm.

    Nonetheless, the use of superpixels implies the assumption of 2D independent slices on an MRI volume. Such a fact may induce a lack of agreement on adjacent slices and a reduction of performance. Additionally, there are topological features of the image which are not taken into account by the state-of-the-art superpixel generation methodologies.

    In this sense, we propose the use of marker controlled watershed transformation for the generation of 3D supervoxels, known as watervoxels, which has been previously introduced by [Machairas et al., 2014; Neubert and Protzel, 2014].

    First, a set of minima are chosen from a regularly distributed cubic grid to be used as the makers for the watershed flooding algorithm. The minimum selection criterion corresponds to the local gradient minimum with the largest volume extinction value inside each cell. Secondly, the image morphological gradient is regularized with an additive term as the normalized distance from the cell marker to each voxel in the cell. For the sake of tunable trade-off between superpixel regularity and boundary adherence, a scaling parameter is included in the regularization term. Such improvements in marker selection and gradient regularization are expected to provided single connected components as homogenous and regular supervoxels with a suitable boundary adherence.

    In order to test the proposed methodology, the well known BrainWeb dataset is used, consisting of 20 simulated MRI volumes of size 256x256x181 voxels and its provided anatomically labeled regions. For the sake of comparison two baseline approaches are considered. The first one is the simple linear iterative clustering (SLIC), as a the state of the art supervoxel generation technique. The second one is a probabilistic template-based brain tissue segmentation algorithm, which is specifically devoted for head MRI volumes but performing at voxel level.

    For quantitatively measure the supervoxel quality the boundary recall (BR) criterion is used, and defined as the percentage of ground-truth contour pixels falling less than 3 voxels away from supervoxel boundaries.

    Obtained results show a monotonically increasing BR with respect to the number of elements for both supervoxel techniques. Nevertheless, watervoxels are less sensitive to the regularization parameter than SLIC. Since watervoxels are mainly lead by image topological properties and SLIC compactness factor enhances the regularity, more ground-truth boundaries tend to be lost for SLIC than for watervoxels.

    Moreover, there is a number of supervoxels from which the baseline template-based approach is overperformed. In fact, in the extreme case, 100% BR is achieved when the number of supervoxels equals the image size. Nevertheless, 87% of BR is achieved by watervoxels using only 1% of the original image size (10^5 elements), while the baseline achieves 84% using the whole image.

    Additionally, the contour density (CD) criterion, being defined as the percentage of obtained contour voxels, is employed for measuring the partition irregularity. In this case, the template-based approach achieves the lowest CD (6%), as it does not over segment the image. On the other hand, watervoxels show a lower CD than SLIC for large numbers of supervoxels. Therefore, it is inferred that proposed approach outperforms SLIC as it achieves the lowest irregularity, while preserving the most boundaries.

    As a standard MRI tissue classification performance measure, the average Dice Index (DI) is computed. Such a value measures the percentage of matching between the ground-truth regions and the obtained high-level segmentation. In this case, regions are labeled as the most probable brain tissue inside a (super)voxel. Although the voxel-wise classification approach achieves the best average performance (91.6% ± 1%), results for both supervoxel approaches are statistically similar to the baseline, SLIC : 89.7% ± 1% and watervoxels : 89.4% ± 1%.

    superpixel, watervoxel, watershed, mathematical morphology, MRI segmentation

Posters

Characterization of bijective discretized rotations by Gaussian integers

Tristan Roussillon, David Coeurjolly

A discretized rotation is the composition of an Euclidean rotation with a rounding operation. It is well known that not all discretized rotations are bijective: e.g. two distinct points may have the same image by a given discretized rotation. Nevertheless, for a certain subset of rotation angles, the discretized rotations are bijective. In the regular square grid, the bijective discretized rotations have been fully characterized by Nouvel and Rémila (IWCIA’2005). We provide a simple proof that uses the arithmetical properties of Gaussian integers.

discretized rotation; algebraic integer;

Une généralisation du bien-composé à la dimension n

Nicolas Boutry, Thierry Géraud, Laurent Najman

The notion of well-composedness has been introduced by Latecki in 1995 for 2D sets and images and for 3D sets in 1997. Well-composed binary digital images enjoy important topological properties; in addition, many algorithms can take advantage from these topological properties. Up to now, well-composedness has not been studied in dimension n, with n > 3. In the presented work, we extend the characterizations of well-composed sets and images to any dimension. We also prove the fundamental theorem of equivalence of the connectivities for a well-composed set.

well-composed

Structuration du squelette en graphe pour une exploitation haut niveau par ses attributs

Rabaa Youssef, Sylvie Sevestre-Ghalila, Christine Chappard

La squelettisation est une opération morphologique qui résume un objet par ses lignes médianes tout en préservant la topologie et la géométrie de l’image initiale. La squelettisation est utilisée dans différents domaines d’application tels que la biométrie comme étant une étape cruciale du processus d’appariement, ainsi que l’imagerie médicale pour la quantification de la micro-architecture de l’os. Dans le contexte d’appariement ou de quantification, il est possible d’exploiter les attributs d’un squelette pour extraire un ensemble de descripteurs structurels d’objets et d’accéder à une analyse haut niveau de l’image. En effet, l’identification d’une personne grâce à son empreinte digitale ou le réseau veineux de sa main se fait grâce à l’appariement de minuties du squelette, composées de terminaisons de lignes et de bifurcations de crêtes. D’un autre côté, des études en imagerie biomédicale ont montré que les caractéristiques morphométriques de la micro-architecture osseuse constituent un indicateur de la qualité de l’os. La quantification de la microarchitecture de l’os rentre dans le champ d’application du projet ANR Voxelo qui a pour objectif de développer de nouvelles méthodes non invasives pour le diagnostic précoce de l’arthrose du genou. À cet effet, l’extraction du réseau trabéculaire par squelettisation est d’une grande importance pour analyser les paramètres morphologiques significatifs tels que la surface du squelette, le nombre de noeuds, d’extrémités, la longueur et la demi largeur de segments, etc. Notre contribution vise à développer une solution pour l’extraction des attributs d’un squelette binaire ou en niveaux de gris et de les enregistrer sous un format hiérarchique ré-exploitable. Nous proposons de construire un graphe qui stocke les différents attributs d’un squelette d’empreinte ainsi que les paramètres morphométriques de l’os. Étant donné qu’un squelette se compose de segments, de noeuds et d’extrémités, il est judicieux d’utiliser un graphe pour représenter cet objet. La correspondance des segments avec les arêtes, des noeuds et extrémités avec les sommets d’un graphe est naturelle et intuitive. Dans ce travail, la structure de graphe se compose de structures points et segments. La structure point détermine la configuration topologique d’un pixel à partir de l’image du squelette binaire, le classe en crête, noeud ou extrémité et pointe sur ses voisins « objet » afin d’établir le lien entre les différentes composantes du graphe. Quant à la structure segment, elle est composée de points stockés dans une pile, d’une tête et d’une queue pointant sur le noeud ou l’extrémité qui suit, ainsi que d’autres attributs tels que la longueur euclidienne et le niveau de gris moyen. La construction du graphe est possible en identifiant en premier lieu la nature de chaque point et en procédant à un suivi de segment pour établir les liens entre les arêtes et les sommets. Les attributs ainsi trouvés sont finalement stockés dans un fichier CSV. Cette solution s’applique à des squelettes binaires et en niveaux de gris, elle nous a permis d’évaluer notre méthode de squelettisation en niveaux de gris et d’implanter une procédure d’ébarbulage du squelette suivant le niveau de gris moyen et la longueur des barbules. En effet, d’après nos expérimentations, nous avons noté que la squelettisation en niveaux de gris est souvent sujette à l’apparition de barbules de faible contraste local. Une analyse des attributs extraits du squelette nous permet de déduire la longueur moyenne et le niveau de gris moyen de ces fausses terminaisons. On procède ainsi à un ébarbulage qui cible directement les segments concernés, les supprime et met à jour le fichier d’attributs.

squelette, graphe, attribut, morphologie mathématique

Tubular structure filtering by ranking orientation responses of path operators

Odyssée Merveille, Hugues Talbot, Laurent Najman, Nicolas Passat

Thin objects in 3D volumes, for instance vascular networks in medical imaging or various kinds of fibres in materials science, have been of interest for some time to computer vision. Particularly, tubular objects are everywhere elongated in one principal direction – which varies spatially – and are thin in the other two perpendicular directions. Filters for detecting such structures use for instance an analysis of the three principal directions of the Hessian, which is a local feature. In this article, we present a low-level tubular structure detection filter. This filter relies on paths, which are semi-global features that avoid any blurring effect induced by scale-space convolution. More precisely, our filter is based on recently developed morphological path operators. These require sampling only in a few principal directions, are robust to noise and do not assume feature regularity. We show that by ranking the directional response of this operator, we are further able to efficiently distinguish between blob, thin planar and tubular structures. We validate this approach on several applications, both from a qualitative and a quantitative point of view, demonstrating an efficient response on tubular structures.

Mathematical Morphology, Non-linear Filtering, Path Operators, Thin Structures, 3D Imaging

Traitement d’images multivariées avec l’arbre des formes

Edwin Carlinet, Thierry Géraud

L’Arbre des Formes (ToS) est un arbre morphologique qui fournit une représentation hiérarchique de l’image auto-duale et invariante par changement de contraste. De ce fait, il est adapté à de nombreuses applications de traitement d’images. Néanmoins, on se heurte à des problèmes avec l’Arbre des Formes lorsqu’on doit traiter des images couleurs car sa définition tient uniquement en niveaux de gris. Les solutions les plus courantes sont alors d’effectuer un traitement composante par composante (marginal) ou d’imposer un ordre total. Ces solutions ne sont généralement pas satisfaisantes et font survenir des problèmes (des artefacts de couleur, des pertes de propriétés…) Dans cet article, nous insistons sur la nécessité d’une représentation à la fois auto-duale et invariante par changement de contraste et nous proposons une méthode qui construit un Arbre des Formes unique en fusionnant des formes issues des composantes marginales tout en préservant les propriétés intrinsèques de l’arbre. Cette méthode s’affranchit de tout relation d’ordre totale en utilisant uniquement la relation d’inclusion entre les formes et en effectuant une fusion dans l’espace des formes. Finalement, nous montrerons la pertinence de notre méthode et de la structure en les illustrant sur de la simplification d’images et de la segmentation interactive.

Tree of shapes, colors, mathematical morphology