Journées de Géométrie Discrète et Morphologie Mathématique

Recherche approximative dans un polytope avec des applications

Guilherme Dias da Fonseca orateur invité

Dans le problème d'appartenance à un polytope, on a un polytope convexe P ⊂ R^d pour une constante d ≥ 2, et l'objectif est de représenter P par une structure de données de façon que, si on reçoit un point de requête q ∈ R^d, on peut rapidement déterminer si q ∈ P. On considère ce problème dans un contexte d'approximation. Étant donné un paramètre ε > 0, la requête doit renvoyer une réponse positive si q ∈ P, une réponse négative si la distance de q à P est supérieure à ε·diam(P), et sinon on peut avoir n'importe quelle réponse, où diam(P) est le diamètre de P.

On a présenté les premières structures de données développées spécialement pour l'approximation de l'appartenance à un polytope. Initialement, on a montré comment répondre aux requêtes en temps O(1/ε^(d-1)/4) avec un stockage optimal de O(1/ε^(d-1)/2). Ensuite, on a raffiné l'analyse de la même structure de données pour obtenir temps de requête O(log(1/ε)/ε^(d-1)/8) avec le même stockage optimal. Finalement, on a étudié une approche différente pour obtenir une structure de données optimale avec temps de requête O(log(1/ε)) et stockage O(1/ε^(d-1)/2). Nos structures de données apportent d'énormes améliorations pour plusieurs problèmes classiques d'approximation géométrique : plus proche voisin, diamètre, ε-noyau, parmi d'autres.

Alors que notre solution initiale était basée sur de techniques bien connues comme les grilles et quadtrees, notre structure de données la plus efficace présente la première application algorithmique des régions de Macbeath, une structure classique de la géométrie convexe. La structure de donnés utilise une hiérarchie d'ellipsoïdes de John des régions de Macbeath, où chaque niveau de la hiérarchie fournit un certain degré d'approximation du bord du polytope.

Convexity Preserving Contraction of Digital Sets

Lama Tarsissi, David Coeurjolly, Yukiko Kenmochi, Pascal Romon

Convexity is one of the useful geometric properties of digital sets in digital image processing. There are various applications which require deforming digital convex sets while preserving their convexity.
In this article, we consider the contraction of such digital sets by removing digital points one by one. For this aim, we use some tools of combinatorics on words to detect a set of removable points and to define such convexity-preserving contraction of a digital set as an operation of rewriting its boundary word. In order to chose one of removable points for each contraction step, we present three geometrical strategies, which are related to vertex angle and area changes. We also show experimental results of applying the methods to repair some non-convex digital sets, which are obtained by rotations of convex digital sets.

Une approche générale pour les algorithmes de plane-probing

Jocelyn Meyron, Jacques-Olivier Lachaud, Tristan Roussillon

Nous proposons une approche générale permettant d'unifier des algorithmes de plane-probing pour l'estimation du vecteur normal d'un plan digital. La particularité de ces algorithmes est le fait qu'ils se basent tous sur le prédicat "est-ce qu'un point appartient au plan ?" et uniquement sur celui-ci afin d'estimer le vecteur normal. L'approche que nous proposons unifie toute une catégorie d'algorithmes existants en permettant notamment de partir de n'importe quel point de départ et pas uniquement de points spécifiques comme c'est le cas actuellement [1, 2]. Cette unification est basée sur un prédicat généralisé construit sur le prédicat "être dans le plan". Ce nouveau prédicat permet de comparer la position de deux points projetés dans la direction du vecteur normal inconnu. Nous montrons la correction de l'algorithme ainsi que sa complexité. Nous terminons en montrant quelques résultats préliminaires sur l'analyse de surfaces digitales en utilisant cette approche.

Comparaison du µ-reach et du turn step

Étienne Le Quentrec

La par(r)-régularité est une hypothèse couramment utilisée dans la littérature lorsqu'on souhaite garantir certaines propriétés topologiques de la discrétisation d'un objet continu. Cette hypothèse peut s’avérer trop contraignante : elle exclut les formes polygonales. C’est pourquoi des généralisations de cette notion ont été proposées : semi(r)-régularité, quasi(r)-régularité, turn step,...
Il a été démontré qu’une courbe est par(r)-régulière si et seulement si son reach est strictement positif, (c’est-à-dire la distance minimale entre l'objet et son axe médian). La notion de reach a également été étendue à des formes moins régulières avec le µ-reach.
Durant cette présentation, après avoir rappelé les notions de turn step et de µ-reach, nous montrerons qu’il est possible de minorer le µ-reach d’une certaine forme par son turn step et ainsi d'exploiter les propriétés du µ-reach sur des formes ayant un turn step non-nul.

Peeling digital potatoes

Loïc Crombez

Un ensemble S de ℤ² est digital convex si conv(S) ∩ ℤ² = S, où conv(S) désigne l'enveloppe convexe de S.
Etant donné un ensemble de point S de ℤ² nous proposons deux algorithmes pour trouver le plus grand sous ensemble K de S qui est digital convex, ainsi que la plus grande union de deux sous ensembles digital convex.

An Equivalence Relation between Morphological Dynamics and Persistent Homology in 1D

Nicolas Boutry, Thierry Géraud, Laurent Najman

We state in this paper a strong relation existing between Mathematical Morphology and Discrete Morse Theory when we work with 1D Morse functions. Specifically, in Mathematical Morphology, a classic way to extract robust markers for segmentation purposes, is to use the dynamics. On the other hand, in Discrete Morse Theory, a well-known tool to simplify the Morse-Smale complexes representing the topological information of a Morse function is the persistence. We show that pairing by persistence is equivalent to pairing by dynamics. Furthermore, self-duality and injectivity of these pairings are proved.

Reconstruction des convexes selon deux directions en tomographie discrète

Yan Gerard

We consider a problem of Discrete Tomography that has been open for 20 years: the reconstruction of convex lattice sets from their horizontal and vertical X-rays. By following the classical strategy initiated by E. Barcucci et al. for the reconstruction of horizontally and vertically convex 4-connected lattice sets, the reconstruction of regular lattice sets leads to regular switching components. We investigate their structural properties and show how they can be used to solve the most simple case in polynomial time: the one of the regular convex lattice sets.

Pruning neural networks thanks to morphological layers

Samy Blusseau, Yunxiang Zhang, Santiago Velasco-Forero, Isabelle Bloch, Jesús Angulo

Motivated by recent advances in morphological neural networks, we further study the properties of morphological units when incorporated in layers of conventional neural networks. We confirm and extend the observation that a Max-plus layer can be used to select relevant filters in its previous layer, without incurring performance loss. We present several experiments in image processing, showing that this filter selection property seems efficient and robust. We also discuss the close connection between Maxout networks and our pruned Max-plus networks. The code related to our experiments is available online (https://github.com/yunxiangzhang).