Inondations dominées de graphes valués

Enjeux

Si on considère un niveau de gris comme une altitude, toute image à niveaux de gris peut être vue comme un relief topographique.
La morphologie mathématique a développé les nivellements, opérateurs puissants pour le filtrage de bruit ou la simplification d’images avant segmentation.
Les nivellements agissent localement comme des inondations, remplissant les cuvettes par des lacs ou comme des arasements, aplanissant les pics.
Ces opérations sont très coûteuses en temps de calcul et les images à traiter sont de plus en plus volumineuses.

L’enjeu est de trouver des algorithmes rapides, parallélisables, et pouvant s’exécuter sur des architectures variées.

Compétences développées

Considérons un relief topographique dont l’inondation a un niveau uniforme. A mesure que ce niveau augmente, de nouveaux lacs se créent dans des minima et d’autres lacs fusionnent. La suite des lacs ainsi créée a une structure arborescente. Cette remarque est à la base de notre travail :

• Construction à partir d’une image 2D ou 3D de la structure arborescente
• Modélisation mathématique des inondations sur une telle structure (structure de treillis des inondations, inondation maximale sous un plafond)
• Développement d’un algorithme d’inondation se factorisant en inondations multiples sur des sous-arbres beaucoup plus petits.
• Retour à l’image pour visualiser le résultat.

Impacts et persectives

Les algorithmes d’inondation sont l’ingrédient de base de nombreux filtres morphologiques, tels que les nivellements, indispensables pour traiter des problèmes complexes.
Pour une tâche donnée, de nombreux nivellements peuvent être nécessaires. Ils sont souvent utilisés en cascade pour une analyse multi-échelle de textures.
Ne trouveront leur place dans des applications industrielles ou médicales que les algorithmes suffisamment rapides et capables de traiter de gros volumes de données.
Il en va de même dans des applications interactives où le temps de réponse doit être immédiat.

Résultats

• Mise au point et validation d’un nouvel algorithme
• Conception d’un simulateur interactif
• Mise en œuvre efficace (20 millions de nœuds en quelques secondes)
• Parallélisation de la phase du calcul des hauteurs finales
• Mise en œuvre parallèle efficace
• Publication et présentation dans une conférence internationale