Projet image 2013 : Descripteur de formes et mouvements 3D et application à la mise en correspondance d'animations

De Ensiwiki
Aller à : navigation, rechercher
Project schedule.png
Titre du projet Projet Image 2013 : Descripteur de formes et mouvements 3D et application à la mise en correspondance d'animations
Cadre Projets de spécialité
Page principale Projets de spécialité image

Encadrants Edmond Boyer, Franck Hetroy


L'équipe

Guillaume Georges (ISI)

Estelle Grémion (MMIS)

Marion Léonard (MMIS)


Contexte des travaux et problématique

Ce projet de spécialité s'inscrit dans le cadre de ceux proposés par les membres de l'équipe Morpheo de l'INRIA. Il s'agit donc d'un projet de recherche, dont les indications initiales ne sont que des pistes dont nous pouvions nous éloigner pour en développer d'autres, si nous arrivions à déterminer que les premières ne pouvaient pas aboutir.

La version originale du sujet est disponible ici.

Objectifs du projet

Ce projet avait plusieurs objectifs. Tout d'abord, il s'agissait d'implémenter un Laplacien en 4 dimensions, pour pouvoir l'appliquer à des maillages représentant des animations.

L'analyse spectrale des résultats devait permettre d'étudier les points intéressants (points qui seront à suivre pour suivre une animation ou chercher des correspondances dans les formes), les symétries et les courbures des différentes formes.

Ensuite, ce Laplacien était utilisé pour mettre en correspondance des images et des animations à l'aide du noyau de la chaleur.

Laplacien en quatre dimensions

Nous sommes partis du Laplacien en 3D+t réalisé par le groupe travaillant sur le projet 2012 (Laplacienne en statique et D'alembertienne pour les animations)

La principale différence pour le passage de la dimensions 3D+t à la 4D a été de ne plus considérer comme voisin temporel d'un point seulement lui-même au pas de temps précédent et au pas de temps suivant, mais aussi tous ses voisins spatiaux au temps t comme voisins spatio-temporels au temps t-\alpha et t+\alpha.

La matrice laplacienne que nous obtenons est donc une matrice carrée de taille Nb_frames x Nb_sommets, tridiagonale par blocs. Au vu du nombre de sommets et de maillages étudiés dans les cas généraux, nous nous sommes appuyés sur l'utilisation de matrices creuses.

Les packages intermédiaires

Afin de faciliter l'implémentation et notre travail comme celui d'un éventuel groupe poursuivant notre travail l'année prochaine, nous avons préalablement implémenté différents packages pour la géométrie en 4 dimensions:

  • Point4D: définition de points dans un espace spatio-temporel
  • Surface: génération de surfaces et calculs d'aires en quatre dimensions
  • Volume: génération et calcul de volumes en quatre dimensions
  • Dual: Calcul de duaux spatiaux, temporels, ou spatio-temporels

Amélioration du code fourni: les edge flips

Par ailleurs nous avons développé les packages déjà implémentés en codant un algorithme réalisant des edges flips. En considérant une arête diagonale d'un quadrilatère convexe, si l'un des angles opposés est obtus, alors il est possible de réduire sa mesure en matérialisant l'autre diagonale du quadrilatère.

Une illustration simple est la figure ci-dessous

exemple simple d'edge flip

Certains problèmes sont cependant apparus, même avec cet algorithme. Pour plus de précisions, voir le document concernant les edges flips contenu dans notre archive.

Poids combinatoires

Notre implémentation a été analogue à celle proposée en trois dimensions, pour des résultats similaires. Pour plus de détails:ici

Cette catégorie de poids est trop peu précise pour être exploitable.

Poids duaux

Les poids sur le fonctionnement desquels nous avons consacré la plus grande partie de notre temps sont les poids duaux. Le laplacien peut avec ces poids s'écrire sous cette forme:

< \Delta f, \sigma ^0 > = -\frac{1}{|\star \sigma^0|} \sum_{\sigma^1 = \sigma ^0 v > \sigma ^0} \frac{|\star \sigma^1|}{|\sigma^1|}(f(v) - f(\sigma^0))

Avec les notations suivantes  \sigma^0 : point auquel on applique l'opérateur laplacien  |\star \sigma^0| : dual spatio-temporel de ce point  \sigma^1 : arête considérée  |\star \sigma^1| : surface duale de l'arête considérée

Remarque: Il est important de noter que l'on considère ici des arêtes temporelles tout autant que des arêtes spatiales.

Les figures suivantes illustrent la représentation des différents duaux, pour les points ou arêtes représentés en vert.

Dual spatial
Dual temporel
Dual spatio-temporel

Remarque: Il est important de noter que chaque maillage possède un précédent et un suivant, les duaux représentés ci-dessus sont donc à calculer aussi entre le temps actuel et le temps t-\alpha


Poids gaussiens

Étant donné que la matrice Laplacienne obtenue à partir des poids duaux n'était pas semi-définie positive, nous avons choisi d'implémenter des poids gaussiens. Pour cela, nous sommes partis d'une formule du Laplacien en trois dimensions, que nous avons modifiée pour prendre en compte la dimension temporelle.

<\Delta f, w> =\frac{volume}{4 \pi h^2}\sum_{p\in V(w)}{e^{-\frac{||p-w||^2}{4h}}(f(p)-f(w))}

Dans cette formule, on a :

 - h = le nombre de voisins du point
 - volume = le volume du dual spatio-temporel du sommet
 - la norme euclidienne en dimension 4


Grâce à cette formule, nous avons pu obtenir une matrice Laplacienne semi-définie positive, qui pouvait donc être utilisée par les programmes Matlab. Par conséquent, c'est cette formule qui a été utilisée lors du calcul du HKS et du HKM.

Nous pouvons cependant noter qu'il ne s'agit que d'une première idée de poids gaussiens, et qu'il pourrait être intéressant d'améliorer cette formule.


Noyau de la chaleur

Le descripteur de formes que nous avons mis au point se base sur la diffusion de la chaleur dans un corps. Cette diffusion est en effet une propriété intrinsèque de la forme, et permet donc de la caractériser. L'équation qui régit cette diffusion se nomme équation de la chaleur. Une solution particulière de cette équation est le noyau de la chaleur (Heat Kernel), sur lequel se basent les méthodes étudiées.

Heat Kernel Signature

Lors de notre étude, nous avons utilisé une formule matricielle du noyau de la chaleur. Cette formule nécessite d'effectuer une décomposition spectrale de la matrice laplacienne. La formule utilisée est la suivante :

K_t = \Phi e^{-t\Lambda} \Phi^T

K_t est une matrice dont l'élément d'indice (i,j) représente la valeur du noyau de la chaleur aux points d'indices i et j, à l'instant t; \Phi est la matrice composée des vecteurs propres de la laplacienne; \Lambda est une matrice diagonale composée des valeurs propres correspondantes.

Afin de simplifier le descripteur obtenu, on ne conserve qu'une coordonnée spatiale, c'est à dire que l'on garde uniquement la diagonale de K_t. Ce sont les valeurs de cette diagonale qui constituent le HKS.

Applications

Ce descripteur de formes a différentes applications :

  • détection des points d'intérêt par recherche des maxima du HKS pour un pas de temps élevé
  • détection des courbures par affichage des valeurs du HKS pour un faible temps : les HKS élevés correspondent à des courbures positives, les HKS faibles à des courbures négatives
  • recherche des ressemblances entre points par affichage des différences entre les HKS des points. Un faible pas de temps correspond à un voisinage proche, un grand pas de temps à un voisinage plus large.


Résultats Obtenus

Détection des points d'intérêt
HKS sur le dinosaure et courbures
Distance de HKS sur le dinosaure pour un temps moyen

Heat Kernel Map

Afin d'effectuer une mise en correspondance entre deux maillages, ou de détecter une symétrie sur une forme, nous utilisons la fonction nommée Heat Kernel Map (HKM). Elle se base sur les valeurs du noyau de la chaleur.

L'algorithme simplifié de mise en correspondance de deux maillages M et N est le suivant :

  • détection des points d'intérêt des deux maillages grâce au HKS
  • pour un de ces points sur M nommé p, on cherche parmi les points d'intérêt de N un correspondant q
  • on calcule pour p et q les HKM correspondant : pour chaque x de M et chaque y de N on calcule

\Phi_p^M(x) = k_t(p,x) et \Phi_q^N(y) = k_t(q,y)

k_t(p,x) est le noyau de la chaleur aux points et temps souhaités

  • on cherche ensuite les plus proches voisins de chaque point de M parmi les points de N, en minimisant une distance bien choisie sur les valeurs des HKM en ces points : on obtient un correspondant pour chaque point

Cet algorithme permet donc de trouver une mise en correspondance entre deux maillages, ou une symétrie si l'on prend le même maillage pour M et N.

Problèmes Rencontrés

Un des premiers problèmes que nous avons rencontré est le fait que la matrice Laplacienne ne soit pas semi-définie positive. En effet ceci était une hypothèse nécessaire pour les calculs du noyau de la chaleur.

De plus, nous avons été limités par le temps de calcul nécessaire sous Matlab. En effet, les programmes liés au noyau de la chaleur dépendaient énormément des paramètres utilisés, et nécessitaient donc un grand nombre de tests pour obtenir des résultats satisfaisants. Ainsi, le fait de devoir attendre pendant plus d'une heure les-dits résultats pouvait se révéler problématique.

Pour finir, il nous a fallu trouver des maillages qui étaient bien manifold, c'est-à-dire représentés par des surfaces fermées. En effet, nous avons été confrontés à plusieurs maillages qui avaient un faible trou, non visible à l'aide de l'interface graphique si on ignore son emplacement exact, mais qui empêche le calcul du Laplacien de s'effectuer correctement.

Conclusion et Perspectives

Si quelqu'un souhaitait reprendre notre projet pour l'améliorer, nous lui conseillerions les pistes suivantes :

  • faire un face-flip pour le Laplacien avec les poids duaux,
  • optimiser le code, et essayer de réduire le temps de calcul, principalement dans le cas des fonctions Matlab, par exemple en utilisant une structure de donnée adaptée pour la recherche des plus proches voisins,
  • adapter l'interface graphique à la mise en correspondance d'animations, en permettant d'afficher le fantôme du maillage au temps précédent.

Références

Les données utilisées pendant le projet, autre que celles fournies par les enseignants, proviennent des sites suivants :

Triceratops : [1]

Main : [2]

Cône, Icosaèdre, Champignon, Octaèdre, Socket : [3]

Homer, Armadillo : [4]


Documents additionnels

Fichier:Soutenance projet spe georges gremion leonard.pdf