Sujet 2 :
distinction des feuilles et des branches sur des arbres scannés


Eucalyptus
 Eucalyptus (zoom)
 Eucalyptus sans feuilles
Exemple d'un eucalyptus scanné Zoom du modèle précédent Exemple d'un eucalyptus sans feuilles scanné

Cadre du projet

Encadrants : Franck Hétroy et Dobrina Boltcheva (INRIA). Collaboration avec Eric Casella (Centre for Forestry and Climate Change, Royaume-Uni).
Nombre d'étudiants : 3 à 4.
Lieu : le projet aura lieu en salle D200, ou équivalente, à l'Ensimag.
Prérequis : cours de la filière MMIS + cours d'algorithmique et de programmation de 1A et 2A.

Contexte

Dans le domaine agronomique, botanique ou forestier, les ingénieurs et les chercheurs ont besoin de faire des mesures sur des plantes et des arbres : volume de bois, surface foliaire totale, distribution spatiale des feuilles, ... Pour l'instant, ces mesures se font par digitalisation : des capteurs (type Polhemus) sont placés aux frontières entre les différents éléments constituant la plante (branches, tiges, feuilles, etc.), et calculent les coordonnées 3D des points récupérés. Ensuite, chaque élément est modélisé par une forme géométrique particulière (cylindre ou cône tronqué pour une branche ou une tige, polygone le plus souvent plan pour une feuille). Cette digitalisation est faite manuellement, et souffre de deux défauts majeurs : le processus est très long (plusieurs heures voire plusieurs jours pour une seule plante !) et très approximatif.

Nous travaillons, en partenariat avec des chercheurs en agronomie, sur un projet de recherche dont le but est de résoudre ces problèmes en remplaçant ce processus de digitalisation par un scan laser de la plante. On récupère alors un nuage de points 3D, non structuré, décrivant la plante (voir les images ci-dessus). L'objectif du projet cité ci-dessus est de retrouver toutes les informations utiles sur la plante à partir de ce nuage de points, qui se trouve être extrêmement bruité (avec notamment beaucoup d'outliers, voir images ci-dessus) et de densité très inhomogène. Ce projet image s'inscrit dans ce contexte.

Plus spécifiquement, le but est de regrouper les points suivant la partie de l'arbre à laquelle ils appartiennent (branches ou feuilles), pour pouvoir distinguer chacune de ces parties. Pour cela, on appliquera et adaptera un algorithme de spectral clustering. Le spectral clustering est une technique très puissante, et très répandie en théorie des graphes et en vision par ordinateur, pour regrouper les sommets d'un graphe en des régions (connexes) "homogènes". Elle consiste en quatre étapes successives :
  1. calcul d'une matrice (dite Laplacienne) à partir du graphe ;
  2. calcul des vecteurs et des valeurs propres de cette matrice ;
  3. plongement des sommets du graphe dans l'espace engendré par les k premièrs vecteurs propres de la matrice ;
  4. regroupement des sommets avec un algorithme classique des k-means appliqué aux sommets plongés.
Dans notre cas, il existe trois problèmes principaux à résoudre pour pouvoir appliquer correctement cet algorithme à nos données d'arbres scannés :

Travail demandé

  1. Lire les articles cités ci-dessous et mettre en place l'environnement de travail.
  2. Tester un algorithme de spectral clustering classique sur les données fournies par les encadrants. Ces données sont de deux types : scans réels d'eucalyptus, avec ou sans feuilles (voir images ci-dessus), et scans "virtuels", où on connaît exactement l'élément auquel appartient chaque point. Ces scans virtuels serviront pour vérifier la validité de vos algorithmes, avant de tester sur les données réelles qui sont ultra bruitées. Vous pouvez recoder vous-mêmes un algorithme, mais vous trouverez également du code en ligne.
  3. Réfléchir à différentes solutions possibles pour les trois problèmes cités ci-dessus, les implémenter et les tester.
  4. Eventuellement, déduire du clustering une approximation de chaque élément par une primitive géométrique simple (cylindre, polygone, ...).
  5. Faire un bilan critique du projet.

Quelques pistes bibliographiques

Voici quelques points de départ bibliographiques. Vous êtes encouragés à trouver par vous-mêmes des lectures complémentaires. Les deux articles suivants expliquent la modélisation des plantes et arbres en biologie, et un exemple d'utilisation pour des calculs d'interception de la lumière :

Détails techniques et liens utiles

La programmation se fera en C++, sous Linux.

Logiciels utiles

L'usage d'un des deux logiciels suivants vous est fortement recommandé. Dans le cas où vous souhaiteriez développer vous-mêmes votre propre interface pas de souci, mais n'y passez pas trop de temps (ça n'est pas le but du projet !). Je peux vous fournir une mini interface graphique, qui tourne sous OpenGL, Qt et utilise libQGLViewer. Je vous conseille fortement libQGLViewer.

Calcul matriciel

Voici trois bibliothèques standards, extrecirc;mement utilisées dans le domaine de l'informatique graphique.