Géométrie discrète

Discussion autour de bibliothèques et de codes sur la géométrie discrète

Objectifs généraux

L'objectif est de fournir un noyau stable pour développer des applications utilisant des techniques de géométrie discrète. Autour de ce noyau, un certain nombre de petits applicatifs pourra être proposé. De même, la création de certains plug-in pour des plateformes classiques sera envisagé. Un tel effort collectif de la communauté vise à répondre aux enjeux suivants :

• faciliter le développement de nouveaux algorithmes/outils en géométrie discrète ;
• faciliter la communication de résultats concrets à la communauté, permettre par exemple des comparisons précisions/robustesse/temps de calcul entre différentes approches ;
• mieux diffuser les travaux de géométrie discrète dans d'autres communautés, notamment le traitement et l'analyse d'image, church management software, la reconnaissance des formes, la géométrie algorithmique
• accélérer la formation des nouveaux arrivants en géométrie discrète, faciliter le démarrage des thèses, accroître le développement de la communauté

Wishlist scientifique

Ce que doit pouvoir fournir la lib (attention c'est en vrac)

• Définition d'images nD
• I/O sur les images 2D et 3D (--> VKT/ITK ?)
  • Ne pas se limiter à 2/3 formats semble indispensable pour atteindre l'objectif de diffusion des outils GeoDis comme celui de démarrage des thèses. Sans tomber dans l'extrème des formats exotiques, mieux vaut prévoir large. Liste à compléter spécifique sur ce point ? (SebF 16 juin 2009)
  • Si on branche avec un truc comme VTK/ITK, on aura l'avantage de pas avoir à faire ça : ces bibliothèques ont déjà tous les loaders possibles--Dcoeurjo 17 juin 2009 à 14:38 (CEST)
  • Certes, mais on ajoute une dépendance très forte avec une autre lib. --SebF 17 juin 2009 à 17:15 (CEST)
  • Les I/O images peuvent être mis dans un package séparé du noyau."" --Lachaud 18 juin 2009 à 10:18 (CEST)
  • Mais il est peut-être bon d'avoir un mécanisme I/O minimal indépendant, genre pgm en 2D ou simplevol en dim sup. "" --Lachaud 18 juin 2009 à 10:34 (CEST)
• Modélisation de la surface d'un objet
• Modélisation d'une partition en objets (--> Carte combi)
  • Graphe d'adjacence --Gdamiand 26 juin 2009 à 17:32 (CEST) (pour avoir une sd light permettant de représenter les régions et les adjacences, ensuite mettre les cartes combinatoires à coté dans un module séparé car c'est gros...).
  • + arbre d'inclusion ? (ou une SD graphe avec arêtes valué)

• Itérateurs/Circulateurs
  • Sur le volume (ligne, colonne, coupe isothetique,...)
  • Sur une région (les voxels de la région)
  • Sur les régions (rag ? --> carte combi + arbre d'inclusion ?)
  • Sur la surface d'une région (border tracking, support géodésique autour d'un surfel,...)

• Noyau arithmétique (pgcd,...) ( --> passerelle BOOST ?)
• Noyau algèbre linéaire ( --> passerelle BOOST ?)
• Noyau GeoAlgo ( --> passerelle CGAL ??)

• Noyau Géométrique
  • objets : point, droite discrète, plan, cercles, polynomes, coniques, simplexes en dims sup (Je ferais la distincton objets euclidiens et discrets --Lachaud 18 juin 2009 à 10:15 (CEST))
    • objets (topologiques) discrets : pixel/voxel avec topologie Rosenfeld (couples), spel/surfel avec topologie Hermann/Udupa (couples aussi), cellules avec topologie cellulaire (standard)
    • objets (géométriques) discrets (arithmétique): point, droite, plan, cercle, polynome (fait-on beaucoup mieux en discret ?)
    • objets (géométriques) discrets (arithmétique + sous-ensemble): segments, morceaux de ce qu'il y a au-dessus
    • objets (géométriques) continus (?) : est-ce que nous prenons nos outils ou nous nous basons sur une bibliothèque externe même au niveau du noyau ?
  • Intersection objects
  • Reconnaissance
  • Reconstruction géométrique
  • (ex Algorithmes géo discrète (est-ce que ce serait pas dans le noyau géometrique ci dessus ça ?--dcoeurjo 17 juin 2009 à 16:21 (CEST)) ok pour moi --Lachaud 18 juin 2009 à 10:15 (CEST))
  • extraction segments maximaux, couverture tangentielle, en temps optimal
  • extraction segments flous maximaux, ..., en temps optimal
  • algorithmes basés préimage : extraction de droites, plans discrets
  • transformées en distance (chanfrein ou autres), extraction d'axe médian
  • algorithmes de polygonalisation, polyédrisation
  • estimateurs géométriques
  • convexité discrète
  • transformation d'objets, rajout de bruits suivant différents modèles.--Kerautret 23 juin 2009 à 21:58 (CEST)

Pourquoi la topo discrète n'auraient elle pas son "noyau" ? La notion de connexité, comme celle de point simple, est aussi centrale en GeoDis que la reconstruction géométrique, non ? --SebF 17 juin 2009 à 17:56 (CEST) Je suis d'accord aussi. Néanmoins, il faut sans doute un noyau de noyaux qui décrit les éléments de bases : pixels/voxels, surfels, objets ? --Lachaud 18 juin 2009 à 10:15 (CEST)

• Algorithmes topo discrète
  • suivi de surface (ouvert/fermé), suivi de bord
  • test de connexité, découpage en composantes connexes, étiquetage en composante connexe
  • points simples binaires, points simples multilabels
  • amincissement, squeletisation
  • complexes cubiques, effondrements

Ce qu'il pourrait y avoir autour (dans le cadre de plug-in ?):

• visualisation 2D/3D d'objets discrets. Visualiser des données associées à chaque cellule. Interaction ?
• synthèse d'objets discrets
  • Oui (pas pourrait). Indispensable pour le côté comparaisons des méthodes. Tout monde doit pouvoir facilement travailler sur les même objets synthétiques. --SebF 17 juin 2009 à 17:28 (CEST)
• outil de visu et d'analyse de primitives discretes
• plugins de calcul d'estimateurs discrets pour l'analyse quantitative

• Page web permettant de d'obtenir directement des résultats d'estimateur ou autres sans passer par du code? Appel d'un script php sur un serveur. --Kerautret 23 juin 2009 à 21:58 (CEST)

• Algo de segmentation ?
  • split and merge
  • modèle déformables

Tentative structure

• Niveau 1
  • NombresArithmétiqueAlgèbre
  • ObjetsDiscrets

  <Geometrical Kernel>                  <Topological Kernel>
   {droite,plan,...,reco,inter}             {bord, region, iterateurs,tracking}

  <Topological Analysis Toolbox>    <Border Processing ToolBox>      <Region Processing Toolbox>    <Arith. Image Processing Toolbox>
  {Euler, ...}                       {Estimateurs, MC,...}           {Skel Topo, DT, Axe median}     {rotation arith., scaling}

  <Visualisation Toolbox> <CGAL Binding>  <VTK Binding>       <VIGRA Binding>  ...
                                               |
                                               |
                                        <Paraview Plugin>




Structuration ImaGene (je mets ici ma structure pour voir comment je peux la projeter dans un tel découpage --Lachaud 18 juin 2009 à 14:46 (CEST))

Wishlist technique

• Langage, systèmes
  • Langage choisi : C++ ?
  • Systèmes : Linux, MacOS, Windows ?

• Noyau(x) commun(s)
  • Contenu du ou des noyaux
  • dépendance par rapport à d'autres bibliothèques

Cette question me semble très importante pour définir ce qui est dans le noyau et ce qui est extérieur. Par exemple, il ne me semble pas souhaitable que l'on dépende d'un gros truc comme VTK. On peut éventuellement dépendre de bibliothèques bas-niveau (BOOST), ou algèbre linéaire, ou structure de données (LEDA ?). Une vraie question est : est-ce qu'on dépend de CGAL ? Sur ce point-là, je me demande même si on ne doit pas en dépendre, d'un point de vue scientifique et/ou marketing. En gros, la géo discrète n'a pas besoin de la géo algo pour exister. Bref, je lance le débat. --Lachaud 18 juin 2009 à 10:28 (CEST)

C'est effectivement une question cruciale.. Perso, je ne vois la la différence entre BOOST/LEDA et VTK, toutes ces libs sont des gros trucs. Là ou je te rejoins, c'est que ces libs ne sont pas au même niveau dans une hierarchie Noyau vs. toolbox. Pour la dépendance avec CGAL (ou autre d'ailleurs), on peut sans doute prévoir des Toolbox spécifiques. Je m'explique : le coeur du projet pourrait être "self-contained" (modulo des trucs très bas niveau) , et on isole les Toolbox ayant de dépendances fortes avec autre chose dont la compilation serait optionnelle : "si vous voulez faire de l'I/O en DICOM, il vous faut compiler le Wrapper "VTKWrapper" ayant VTK en dependance". Avec cmake, cela ne pose pas de prblm. --dcoeurjo 18 juin 2009 à 10:40 (CEST)

Disons que VTK a par exemple besoin de visu genre OpenGL, peut-etre d'une interface genre Qt (je ne sais pas). En fait, on ne peut s'appuyer que sur des trucs extremement standards et stables (genre STL C++). Je pense qu'on peut mettre le lien avec CGAL au-dessus du noyau. Neanmoins, peut-on vraiment faire un noyau geo discrete sans la notion de point euclidien ! --Lachaud 18 juin 2009 à 11:00 (CEST)

• Packages

• Plugs-in

• Ponts avec d'autres bibliothèque (non GeoDis) au niveau structure de données.
  • Rendus possibles et faciles à mettre en place ? C'est un minimum. Un utilisateur peut être contraint pour une raison X ou Y de combiner l'utilisation du noyau avec une autre bibliothèque, au niveau structure de données au moins.
  • Offrir d'emblée un certain nombre de ponts ?
  • Oui, notamment ponts pour faciliter le développement de plugs-in (ex Paraview), importer/exporter de CGAL ou de bibliothèques image

Bibliothèques/Outils existants

• Bibliothèques "image"
  • VIGRA (Ullrich Köthe)
  • ITK (opensource, kitware) : bibliothèque de manipulation/transfo d'images (très orientée image médicale)
    • + Compatible VTK
    • + implementation C++ mais des wrappers python/java/tcl existent
    • + Format d'images générique, itérateurs,...
  • CImg (D. Tschumperlé, GREYC) : Bibliothèque C++ avec type de pixel générique.
    • Orientée traitement d'image
    • +/- (à discuter) Non-séparation des structures et des algorithmes.
      • Tous les algos liés à la lib sont des méthodes
      • L'extension est possible grâce à un système de plug-ins
    • + Images jusqu'à la 4D
    • + Orientée "code concis"
• Visualisation
  • VTK (opensource, kitware)
  • Paraview (opensource, kitware) : outils de visualisation de données scientifiques basées sur les pipeline VTK
    • + Interface très bien pensée
    • + Système de plugin basé sur les classes VTK très simple
    • + Tous les filtres VTK sont utilisables dans Paraview
    • + Gestion utlra-simple de cluster de calcul de rendu via MPI
  • QVox (Seb Fourey) : interface de visualistion/manipulation d'objets discrets
    • + Très efficace même sur de gros volumes
    • + mécanisme de plugin 'ligne de commande + interface automatique' très utile
    • - ne permet pas de visualiser d'autres types d'objets (maillages,...)
    • Englobe une bibliothèque générique (+/- ?) de manipulation de volumes jusqu'à 4D.
• Géométrie/topologie discrète
  • ImaGene (J.-O. Lachaud) : bibliothèque de représentation des sous-ensembles de la grille discrète: objets, surfaces discrètes, ensembles de cellules, contours, etc.
    • + une bonne partie des outils, algorithmes, structures de données sont écrits en dimension quelconque, e.g. suivi de surface nD, estimateurs discrets nD, export en surface triangulée
    • + la géométrie discrète 2D arithmétique est assez complète (couverture tangentielle, tangentes, courbures) et assez générique
    • + pas mal d'outils de type ligne de commande pour traiter les images binaires 2D, contours, analyser/afficher les segments max, avec exportation sous Xfig
    • - la visu 3D est externe (ImaGeneUtils), utilise Coin/OpenInventor et est non-interactive
    • - manque des I/O nD (seul le cas 2D est bien traité)
    • - documentation en ligne essentiellement, peu de doc utilisateur
  • Simplevol : bibliothèque KISS (Keep it Simple & Stupid) de definition/manipulation d'images discrètes (profondeur : uchar)
  • MAEVA Toolkit (david) : bibliothèque d'analyse volumique d'objets discrets 3D (DT, REDT, Axe médian, Power diagram,...)
    • + Assez efficace (multi-thread)
    • - 3d uniquement
• Gestion projet/compilation/...
  • cmake langage de description d'un projet pour une compilation multi-plateforme (Makefile sous linux, Visual Project, KDevelop, Xcode...)

Méthodologie

• Concepts
• Style Code

• groupe de travail réduit couvrant les différents champs de la géométrie discrète
• discussion et préparation par interaction sur wiki, mail, téléphone, rencontre
  • mise en valeur des qualités et défauts des codes existants
  • se mettre d'accord sur les objectifs, sur l'architecture générale et le découpage
  • identifier les tâches prioritaires, les intérêts communs, les cibler et attribuer des responsables
  • identifier les codes qui doivent servir de base de travail
  • prévoir le programme des journées prévues
• 3 jours de rencontre/travail en continu fin août/début septembre 2008
  • ...