Descripteur de Formes et de Mouvements

De Ensiwiki
Aller à : navigation, rechercher

Mycomputer.png  Deuxième Année  CDROM.png  Informatique  Mathematiques.png  Mathématiques 

Project schedule.png
Titre du projet Projet de spécialité Descripteur de Formes et de Mouvements
Cadre Projets de spécialité
Page principale Projet de spécialité Descripteur de Formes et de Mouvements

Encadrants Franck Hetroy


Introduction

L'étude, la comparaison et la classification de formes 3D ont toujours présenté un grand intérêt dans différents domaines, tels que la médecine, la CAO ou encore la reconnaissance faciale. Par ailleurs, l'extension de cette étude dans le domaine dynamique, afin de comparer des animations, pourrait avoir de nombreuses applications, en médecine ou dans les jeux vidéos par exemple.

En ce qui concerne le domaine statique (formes 3D), différentes méthodes ont déjà été développées, mais rien n'a encore été étendu dans le domaine dynamique (animations 3D). L'objectif de ce projet de spécialité est donc d'implémenter une méthode de comparaisons de formes 3D puis d'étudier la possibilité de l'étendre aux animations (3 dimensions spatiales et une dimension temporelle).

Le projet a été divisé en deux parties :

  • Implémentation d'un descripteur de formes : le Laplacien
  • Recherche de l'existence d'un descripteur de mouvements : le D'Alembertien

Laplacien : Descripteur de Formes

Préambule

Afin de comparer deux formes 3D, on s'intéresse à leur représentation discrète, sous forme de maillage. On rappelle qu'un maillage est la donnée du triplet {S,A,F}, où S est la liste des sommets du maillage, A la liste des arêtes, reliant 2 sommets, et F la liste des faces triangulaires, joignant 3 arêtes.

Cette représentation discrète permet également de travailler sur différentes matrices caractéristiques de ces maillages :

  • D : la matrice d'incidence.
  • W : la matrice d'adjacence.

A partir de ces deux matrices, on construit la matrice Laplacienne L du maillage, sur laquelle on va travailler afin de comparer deux maillages différents.

Pour plus d'informations sur ces matrices, on pourra se référer à la page suivante : Construction de la Laplacienne.

Traitement de la Laplacienne

Une fois la Laplacienne construite, il faut en extraire les vecteurs propres et les valeurs propres. En effet, le spectre de la matrice Laplacienne, après avoir subi un certain nombre d'opérations, possède des propriétés très intéressantes.

En notant  v_{1},...,v_{n} les vecteurs propres de la matrice L, et \lambda_{1},...,\lambda_{n} les valeurs propres associées, nous avons construit une nouvelle matrice, colonne par colonne, nommée matrice GPS, de la manière suivante :  GPS(:,i) = \frac{v_{i}}{\sqrt{\lambda_{i}}}

C'est sur cette dernière que nous avons principalement travaillé, et effectué les deux traitements suivants :

  • L'étude de chaque vecteur de la matrice GPS.
  • L'étude des distances au sein de cette matrice.

Etude des vecteurs de la matrice GPS

Après avoir calculé le GPS de la Laplacienne du maillage, il s'agit ensuite de visualiser à l'écran les directions du maillage qui correspondent à une colonne du GPS (un vecteur propre). Pour le vecteur propre j, on associe au point i du maillage une couleur en fonction de la valeur GPS(i, j). On compare cette valeur aux minimums et maximums du vecteur propre et on lui associe une couleur (allant du bleu au rouge) selon sa position dans l'intervalle des valeurs. On obtient ainsi les directions du maillage. La visualisation du premier vecteur propre nous donne par exemple la direction principale.

Les 5 premières direction principales d'un maillage d'humain

Comparaison de deux matrices GPS

Première approche : la norme

Afin de comparer deux matrices GPS, la première idée à été d'étudier leur norme. Cette idée présentait deux avantages, à savoir la simplicité d'implémentation et la rapidité de calcul.

Nous avons ici utilisé la norme 2 :sur différentes matrices GPS, au préalablement normalisées selon la norme D : \| \|_{D} et avons pu constater que cette méthode donnait des résultats convenables, puisque des objets semblables possédaient des normes semblables et inversement.

Néanmoins, la norme ne paraissait pas être un outil assez robuste pour comparer plus en profondeur deux maillages différents, et nous avons donc utilisé une autre méthode par la suite.

Deuxième approche : la distance

Par la suite, nous avons utilisé la méthode développée dans l'article scientifique [2].

L'idée est de calculer les distances D2 (cf. [4]) entre les points de la matrices GPS et de les ranger dans un histogramme. On compare ensuite les histogrammes des deux matrices GPS à différencier.

Pour plus de détails, on se reportera à la page suivante : Comparaison de deux matrices GPS


Comparaison de deux maillages de chat

Résultats

En conclusion, nous avons mis en évidence qu'il existait effectivement un moyen de comparer et de classer les formes 3D à l'aide de l'opérateur Laplacien.

  • Au niveau théorique, à l'aide de la norme et des distances D2, il a été mis en évidence que des formes différentes présentaient des résultats différents.
  • Au niveau graphique, à l'aide de la visualisation des directions principales de chaque forme, on constate que deux maillages représentant des objets différents possèdent des axes directeurs différents.

Cependant cette partie, nous n'avons présenté qu'un petit nombre de résultats. Pour plus de détails, merci de se reporter à cette page : Résultats du Laplacien

D'Alembertien : Descripteur de Mouvements ?

Préambule

On s'intéresse ici à des animations temporelles. De même que pour la partie statique, on étudie une matrice représentative du maillage, ici sa matrice D'Alembertienne.

Cependant, à l'inverse de la Laplacienne, il n'est pas garanti que la D'Alembertienne d'un maillage animé possède des propriétés intéressantes. L'essentiel des travaux effectués ici ont donc consisté en l'étude de cette matrice et à la détermination de l'existence ou non d'un descripteur de mouvements qui lui serait lié.

De manière simple, la matrice D'Alembertienne peut être constituée à peu de choses près comme un assemblage de matrice Laplacienne, une pour chaque frame du maillage, mises bout à bout en diagonale dans une grande matrice. En effet, l'opérateur D'Alembertien discret est défini de la manière suivante :  \square = \triangle - \alpha , où  \triangle est l'opérateur Laplacien discret et  \alpha est un paramètre que nous allons faire varier.

Pour plus d'informations sur la création de la matrice D'Alembertienne d'un maillage, on pourra se référer à cette page : Matrice D'Alembertienne d'un maillage.

Traitement de la matrice D'Alembertienne

Résultats

On remarquera tout d'abord qu'à priori les résultats pour la matrice D'Alembertienne calculée avec les poids cotangents sont loin d'être concluants et utilisables. En effet, la visualisation des vecteurs propres sur l'animation ne semble pas exploitables.

L'utilisation des poids combinatoires semble donc plus intéressante.


////// Insertion de la vidéo d'Human ///////

Conclusion et Travaux Futurs

  • Le Laplacien est donc bien un descripteur de formes efficace
    • Comparaison mathématique entre divers objets possible.
    • Représentation visuelle parlante.
  • Le D'Alembertien, à l'heure actuelle n'est pas de manière certaine un descripteur de mouvements
    • A poursuivre, avec une étude plus approfondie selon les valeurs de alpha.
    • Problèmes des vecteurs propres complexes.

Outils

  • Construction des matrices : Le langage C++ ainsi que la librairie Eigen
  • Exploitation des données : Matlab
  • Visualisation : Le langage C++, OpenGL et QglViewer

Bibliographie

Auteurs

Projet de Spécialité Descripteur de Formes et de Mouvements
Projet de Spécialité 2012 Descripteur de Formes et de Mouvements et Application à la Classification d'animations 3D
Equipe Mehdi Benjelloun, Quentin Lebas, Celine Michaud
Encadrant Franck Hetroy
École Grenoble INP -- Ensimag
Date Juin 2012