Simon Courtemanche Traitement et régularisation de surfaces 3D en mouvement resultats

De Ensiwiki
Aller à : navigation, rechercher


Traitement et régularisation de surfaces 3D en mouvement

Labo INRIA, LJK
Equipe EVASION
Encadrants Franck.Hetroy@imag.fr,estelle.duveau@inria.fr

Étudiant

Courtemanche, Simon


Introduction

Le but est de lisser une séquence d'objets 3D.

Chacun de ces objets provient d'une reconstruction 3D d'être vivant, comme un ras, ou un chercheur par exemple. La séquence de ces constructions donne le mouvement du sujet.


Le contexte global est l'étude du mouvement des êtres vivants. Mon travail se place dans le cadre du projet ANR Kameleon. Ce projet combine des données expérimentales (reconstructions 3D) et des données anatomiques d'un sujet pour étudier son mouvement.


Le problème particulier posé comme sujet de TER est l'amélioration du procédé de reconstruction 3D du mouvement. Cette amélioration se place au niveau d'un post-traitement des données issues du procédé de reconstruction existant.


La principale piste de recherche suivie est l'étude de l'extension d'une méthode de lissage statique. Cette méthode est l'opérateur de Laplace, présenté par Olga Sorkine dans [S05]. Cet opérateur peut-être utilisé de plusieurs façons. Je me suis plus particulièrement penché sur l'étude de ses propriétés spectrales, et sur leur implémentation.


Les résultats obtenus sont de deux types :

  • Théoriques, sous la forme d'une présentation de possibilités d'extension des méthodes de lissages statiques utilisant l'opérateur Laplacien, aux surfaces 3D animées.
  • Techniques, par une étude des librairies existantes pour l'implémentation des résultats théoriques.


La pertinences de ces résultats est limitée. L'extension faite ici du rapport sur l'état de l'art du traitement des maillages par Laplacien [S05] reste pauvre par rapport à d'autres études portant sur des sujets similaires, comme [KSMH09], [MHKCB08], [VZBH08] et [ZBVH09]. D'autre part, l'étude technique est non exhaustive. Des librairies, comme [cgal], [linalg] ou [ietl] sont encore à étudier. Néanmoins, l'étude technique présentée ici est inédite.

Éléments de pré-requis

Voici les notions indispensables pour la compréhension du travail effectué :

Extrait d'une séquence de maillages issue d'une expérimentation personnelle de la plateforme Grimage, INRIA.

Maillage

Un maillage M est un ensemble de sommets V, d'arêtes E, et de faces F.

M = { V, E, F }

Dans notre cas, chaque face est formées d'un triangle d'arêtes. On parle alors de maillage triangulaire.

Surface 3D animée

Une surface 3D animée est une séquence de maillages. Chaque maillage, qui représente une frame de l'animation, est obtenu par le procédé de capture suivant :

Le sujet est entouré de caméras. Chaque caméra permet d'obtenir une silhouette du sujet. Si l'on projette cette silhouette dans l'espace, selon la direction de la caméra, nous obtenons un volume. L'intersection des volumes obtenus pour chaque caméra donne un maillage. Ce maillage approche la forme du sujet.

Ainsi, deux maillages successifs dans l'animation n'ont pas nécessairement la même topologie. (Les nombres de sommets et de faces sont différents.)

Coordonnée différentielles

Les voisins d'un sommet i sont l'ensemble des sommets j tels que ij soit une arête.

Les coordonnées différentielles d'un sommet sont la différence entre le coordonnées cartésienne de ce sommet, et la moyenne des coordonnées cartésiennes de ses voisins.

Matrice Laplacienne

Un maillage et sa matrice Laplacienne L_s.

Soit un maillage comprenant N sommets.

Soit X les coordonnées Cartésiennes de ces sommets. Soit \delta leurs coordonnées différentielles.

X et \delta sont des vecteurs à N composantes, et représentent les coordonnées des sommets selon une dimension de l'espace.

On définit la matrice Laplacienne L par la relation :

 \delta = L.X

Détaillons mathématiquement l'expression de L.

Soit N(i) est le nombre de voisins du sommet i. Soit D la matrice diagonale telle que :

D(i,i) = N(i)

Soit A la matrice telle que :

A(i,j) = 1 ssi ij est une arête

Alors :

L = D^{-1}.(D - A)

Nous travaillons avec la forme symétrique de L :

L_s = D - A

Dans la suite, le terme "matrice Laplacienne" désigne L_s.

Cette matrice est donc creuse et symétrique. La puissance de l'opérateur Laplacien réside dans ces deux propriétés.

Travail réalisé

Deux travaux ont été menés en parallèles :

  • L'étude théorique de l'application aux surfaces animées des méthodes de lissage d'un maillage statique utilisant l'opérateur Laplacien.
  • L'étude technique de l'implémentation de ces méthodes.

Étude théorique

Propriétés présentées dans [S05]

Deux propriétés présentées dans [S05] peuvent être exploitées pour un lissage statique :

  • Comme la matrice Laplacienne d'un maillage est symétrique et semi-définie positive, il existe une base formée de ses vecteurs propres. Ordonnons cette base par valeurs propres croissantes. Nous pouvons alors décomposer les coordonnées Cartésiennes des sommets sur cette bases. Alors, les premières composantes de cette décomposition correspondent aux basses fréquences du maillage, et les dernières composantes correspondent aux hautes fréquences. En réduisant ces dernières composantes, nous lissons le maillage.
  • Les coordonnées différentielles d'un sommet représentent la courbure locale du maillage. Ainsi, avec les notations précédentes, ||\delta|| = ||L.X|| représente le caractère lisse d'un ensemble de points de coordonnées X, dont la connectivité est décrite par L. Si M est un maillage de matrice Laplacienne L, alors M peut être lissé en approximant, au sens des moindres carrés, un sous ensemble des sommets de M par un ensemble de points X, sous une contrainte de minimisation de la valeur ||L.X||.


Applications aux surfaces animées

L'idée principale pour appliquer l'opérateur Laplacien à une séquence de maillage est de considérer le temps comme une quatrième dimension. Alors, nous pouvons obtenir un unique grand maillage en construisant des arêtes entre les frames de la séquence.

Voici deux méthodes intuitives pour construire de telles arêtes :

Méthodes des points les plus proches appliquée à trois frames 1D
Méthode des points les plus proches

La méthode des point les plus proches consiste à lier chaque sommet d'une frame donnée avec les sommets les plus proches dans les deux frames voisines.

Avec un tel maillage, nous pouvons construire la matrice Laplacienne correspondante et appliquer directement les méthodes précédentes.

L'avantage de cette méthode est sa simplicité du point de vue théorique. Son inconvénient est qu'elle ne représente pas le mouvement de l'objet maillé. Par exemple, si nous appliquons cette méthode au maillage d'un train en marche avant, un sommet correspondant à l'avant du train pour une frame donnée, se retrouvera maillé avec des sommets de plus en plus proches de l'arrière du train dans les frames suivantes.

Méthode isométrique appliquées à trois frames 1D
Méthode isométrique

La méthode isométrique consiste à construire des arêtes de manière à ce que chaque sommet d'une frame donnée, ait un unique voisin dans la frame suivante.

Ceci requiert que chaque frame ait le même nombre de sommets, ce qui implique un pré-traitement des maillages initiaux.

Nous pouvons ensuite combiner deux types de lissage : un lissage statique par opérateur Laplacien sur chaque frame; et un lissage dynamique sur le mouvement, au cours de l'animation, de chaque sommet de la première frame. Pour ce dernier lissage, nous pouvons par exemple utiliser les transformées de Fourier 3D.

Cependant, cette méthode n'est pas toujours efficace. Supposons que notre séquence du train ait été pré-traité pour obtenir les propriétés voulues ci-dessus. Alors rien n'empêche de relier successivement l'avant du train à l'arrière du train et inversement.


Nous pouvons alors penser à une combinaison de deux méthodes précédentes. Ceci permet de résoudre le dernier problème soulevé, mais ne permet pas de modéliser le mouvement de rotation d'une roue de notre train sur elle-même par exemple.


Cohérence spectrale de [KSMH09]

Une autres approche est proposée dans [KSMH09].

Pour chaque frame, on projette les coordonnées Cartésiennes des sommets sur les premiers vecteurs propres de la matrice Laplacienne. On trace ensuite les histogrammes de répartition des sommets sur les espaces vectoriels à une dimension engendré par ces vecteurs propres. D'une frame à l'autre, il est ainsi possible de mettre en correspondance ces histogrammes, pour identifier les positions de chaque sommet dans la structure de l'objet modélisé. Grâce à ces positions, nous pouvons relier les frames de la séquence d'une manière cohérente.

Mais cette méthode ne permet pas de représenter le mouvement d'un objet, présentant une symétrie axiale, en rotation autour de son axe de symétrie, puisque la position d'un point de cet objet ne peut pas être identifier par rapport aux formes de cet objet. Nous pouvons donc qualifier cette méthode de futuriste, puisqu'elle ne permet de modéliser que des trains électromagnétiques.

Étude technique

Dans cette étude nous nous penchons sur les outils disponibles pour l'implémentation des méthodes décrites ci-dessus.

Nous distinguons deux tâches essentiel : l'affichage des maillages, et le traitements des maillages. Cette dernière tâche consiste essentiellement en la manipulation de la matrice Laplacienne. Nous avons donc recherché des outils fournissant un format explicite pour les matrices creuses, ainsi que des méthodes de calcul de vecteurs propres.

Les librairies marquées d'une étoile (*) sont décrites dans le rapport fournit en document additionnel.


Outils pour l'affichage
Programmes interactifs
  • [cortona] * (affichage de séquences de maillages)
  • [meshlab]
  • [graphite] *
  • [matlab] *
Librairies d'affichage
  • [openmesh] *
  • [qt] *
  • [libQGLViewer] *
  • [glew] *
  • [opengl] *


Outils pour le traitement
Librairies orientées maillages
  • [cgal] (très complète)
  • [openmesh] *
  • [gts] (simple d'utilisation)
Programme intéractifs
  • [meshlab]
  • [graphite] * (peut aussi être utilisé comme librairie)
Programme de calcul
  • [matlab] *
Autre librairies
  • [opencv] * (computer vision)
  • [lapack] * (fortran 90)
  • [blas] * (bas niveau)
  • [taucs] * (non maintenue)
  • [eigen] * (en cours de développement)
  • [linalg]
  • [ietl]


Conclusion

Du point de vue théorique, j'ai personnellement imaginé les deux méthodes intuitives d'extensions de la méthode du Laplacien aux séquences de maillages. Malheureusement, ces méthodes existaient déjà dans la littérature scientifique. Ces méthodes n'ayant pas été implémentées durant cette étude, seul le raisonnement permet de juger de leur efficacité.


Du point de vue technique, j'ai passé en revu plusieurs outils informatiques susceptibles d'être utilisés pour l'implémentation des méthodes théoriques. Cet liste de librairies est non exhaustive, mais offre un point de départ pour l'énumération de l'ensemble des librairies existantes. L'exactitude des renseignements fournis peut être vérifiée par des tests expérimentaux. De tels tests peuvent se baser sur les codes fournis en document additionnel.


Un prolongement immédiat sur le plan théorique serait la lecture des travaux récents sur le Laplacien, et l'étude de leur application à notre cas. Sur le plan technique, la liste des librairies d'algèbre linéaires existantes demande à être complétée. L'étude de chacune de ces librairies pourraient également être approfondie.


Références



Documents additionnels