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

12 novembre 2019, Marseille

Présentation

Après Strasbourg (2010), Clermont-Ferrand (2011), Nantes (2012), Paris (2013), Reims (2014), Lyon (2015), Marseille (2016), Poitiers (2017) et Lyon (2018), la journée du Groupe de Travail de Géométrie Discrète et Morphologie Mathématique des groupements de recherche IM et IGRV est l'occasion pour les enseignants-chercheurs, chercheurs, doctorants de se rencontrer, d'échanger sur les travaux les plus récents, d'initier de nouvelles collaborations sur tous les thèmes de la géométrie discrète et de la morphologie mathématique.

Quand ? La journée du GT aura lieu le . Elle précède les journées JFIGRV 2019.

La géométrie discrète

Le contexte de la géométrie discrète s’intègre dans le cadre général de la modélisation et l’analyse géométrique et topologique d’objets définis sur des structures régulières (ex. des grilles de pixels ou de voxels) ou combinatoires (graphes, cartes, etc.). Généralement, les axiomes et propriétés de la géométrie euclidienne classique ne sont plus valides lorsque l’on considère des ensembles de pixels. La définition de concepts et notions adaptés à des structures discrètes, mais néanmoins compatibles avec les concepts et notions continus, est alors requise. L’originalité de cette approche réside dans le fait qu’en exploitant les propriétés du support sur lequel sont décris les objets, nous pouvons obtenir des algorithmes efficaces, certifiés et précis pour répondre à des problèmes de caractérisation géométrique ou topologique d’objets discrets (2D, 3D, nD, etc.). Le caractère discret des données à traiter, et donc l’utilité de l’approche discrète, se retrouvent dans de nombreux contextes applicatifs (analyse et traitements d’images, imagerie médicale, ingénierie des matériaux, etc.).

La morphologie mathématique

La morphologie mathématique est une théorie essentiellement non-linéaire, utilisée en particulier en analyse d’images, dont le but est l'étude des objets en fonction de leur forme, de leur taille, des relations avec leur voisinage (en particulier topologiques), de leur texture, et de leurs niveaux de gris ou de leur couleur. Par les transformations qu’elle propose, elle se situe à différents niveaux du traitement d’images (filtrage, segmentation, mesures, analyse de texture) et fournit ainsi des outils pour la reconnaissance des formes. La morphologie mathématique, développée à l’origine pour l'étude des matériaux poreux, trouve maintenant ses applications dans de nombreux domaines du traitement d’images, aussi bien 2D que 3D, en biologie et cytologie quantitative, en imagerie médicale, en imagerie aérienne et satellitaire, en robotique et vision par ordinateur, en contrôle industriel non destructif, dans les études sur les documents et les œuvres d’art. Hors du domaine du traitement des images, on trouve des applications par exemple en analyse de données, ou encore en théorie des jeux.

Modalités de soumission et inscription

Outre cette présentation invitée, plusieurs créneaux sont réservés à des présentations de travaux récents. Nous invitons donc les membres de la communauté, et en particulier les jeunes chercheurs, à faire une proposition de contribution sur un sujet relevant des thèmes du Groupe de Travail.

Les propositions de contribution devront indiquer les noms, prénoms et affiliations du/des contributeur(s), ainsi que le statut du contributeur principal (doctorant, post-doctorant, chercheur permanent). Un titre et un résumé devront être fournis. La date limite de soumission des propositions de contribution est fixée au .

Les informations suivantes sont requises (par courrier électronique à l'adresse gdmm2019@lis-lab.fr). Les participants qui ne proposent pas d’exposés doivent aussi envoyer un courrier électronique, car le repas du midi sera pris en charge par le Groupe de Travail.

Prénoms, noms des auteurs : 
Courriels et affiliations (université, laboratoire) : 
Titre de la soumission : 
Résumé de la soumission :

Programme

Heure Description
09h00Accueil
09h30Guilherme Dias da Fonseca : Recherche approximative dans un polytope avec des applications orateur invité
10h45Pause café
11h15Lama Tarsissi : Convexity Preserving Contraction of Digital Sets
11h40Jocelyn Meyron : Une approche générale pour les algorithmes de plane-probing
12h05Étienne Le Quentrec : Comparaison du µ-reach et du turn step
12h30Repas
14h30Loïc Crombez : Peeling digital potatoes
14h55Nicolas Boutry : An Equivalence Relation between Morphological Dynamics and Persistent Homology in 1D
15h20Yan Gerard : Reconstruction des convexes selon deux directions en tomographie discrète
15h45Pause
16h15Samy Blusseau : Pruning neural networks thanks to morphological layers
16h40Discussion sur le GT
17h30Fin
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 ⊂ Rd 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 ∈ Rd, 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).

  • Aldo Gonzalez-Lorenzo (LIS, Aix-Marseille Université)
  • Bertrand Kerautret (LIRIS, Université de Lyon 2)
  • David Coeurjolly (LIRIS, CNRS)
  • Étienne Le Quentrec (Icube, Université de Strasbourg)
  • Fabien Baldacci (LaBRI, Université de Bordeaux)
  • Guilherme Dias de Fonseca (LIS, Aix-Marseille Université)
  • Isabelle Sivignon (Gipsa-Lab, CNRS)
  • Jacques-Olivier Lachaud (Laboratoire de Mathématiques, Université Savoie Mont Blanc)
  • Jean-Luc Mari (LIS, Aix-Marseille Université)
  • Jocelyn Meyron (LIRIS, INSA Lyon)
  • Jonas Lamy (LIRIS, Université de Lyon 2)
  • Lama Tarsissi (LIGM, LAMA, Université Paris-Est)
  • Laurent Fuchs (XLIM, Université de Poitiers)
  • Loïc Crombez (LIMOS, Université Clermont Auvergne)
  • Maxime Chapuis (LIRMM, Université de Montpellier)
  • Nicolas Boutry (LRDE, EPITA)
  • Nicolas Passat (CReSTIC, Université de Reims Champagne-Ardenne)
  • Philippe Even (LORIA, Université de Lorraine)
  • Ricardo Uribe Lobello (LIS, Aix-Marseille Université)
  • Samy Blusseau (Centre de Morphologie Mathématique, Mines ParisTech)
  • Tristan Roussillon (LIRIS, INSA Lyon)
  • Yan Gerard (LIMOS, Université Clermont Auvergne)
  • Yukiko Kenmochi (LIGM, Université Paris-Est)

Plan

La journée du GT GéoDis aura lieu à l’École d’Ingénieurs Polytech (bâtiment A) sur le campus de Luminy, juste à côté du CIRM, au sud de Marseille.

Les coordonnées GPS de la porte d’accès au bâtiment A sont : 43.232842, 5.443403

Hébergement

Voici un liste d'hôtels allant du Vieux Port au campus de Luminy.

Des chambres pour chercheurs sont également disponibles sur le campus de Luminy (environ 40 euros par nuit). Contactez nathalie.prano@crous-aix-marseille.fr pour plus d’informations.

Contact

Pour toute question, contacter l’équipe organisatrice (Jean-Luc Mari, Aldo Gonzalez-Lorenzo et Ricardo Uribe Lobello) : gdmm2019@lis-lab.fr