Analyse et mise en correspondance de formes 3D

De Ensiwiki
Révision de 17 juin 2010 à 08:58 par Hetroyf (discussion | contributions)

(diff) ← Version précédente | Voir la version courante (diff) | Version suivante → (diff)
Aller à : navigation, rechercher


Analyse et mise en correspondance de formes 3D
Projet Projet de spécialité 2A
Sous-projet Image
Étudiants Lukas RUMMELHARD (MMIS-IRVM), Yani SADOUDI (MMIS-IRVM), Franck VOURIOT (MMIS-IRVM)
Promo 2011
Tuteur Franck HETROY franck.hetroy@grenoble-inp.fr


Introduction

Contexte

Différentes techniques permettent de créer un modèle 3D en mouvement représentant un objet réél, à partir de vidéos par exemple. On obtient souvent une séquence de maillages certes fidèle à la réalité, mais sans cohérence temporelle : chacun a été créé séparement. On ne sait donc pas à priori isoler une partie de l'objet, et en suivre le mouvement.

Description du projet

L'objectif de ce projet est de développer un algorithme de liaison temporelle entre les points de différents maillages d'une animation 3D. Il doit permettre de suivre sur l'objet animé un point en particulier, et ce tout au long du mouvement représenté. Pour réaliser cette mise en correspondance, la méthode proposée est décomposée en 2 étapes :

- la construction sur chaque maillage d'un squelette. Pour cela, on s'appuie sur l'article de recherche de référence, Shape Analysis Using the Auto Diffusion Function, de K.Gebal, J.A. Baerentzen, H.Aanaes, et R.Larsen. On en soulignera les avantages, les inconvenients.

- développer une méthode originale de mise en correspondance des deux maillages, s'appuyant sur leurs squelettes


Projet

Calcul d'un squelette

L'article de référence propose en premier lieu de calculer une fonction particulière sur le maillage appelée Auto Diffusion Function (ADF). Cette fonction sera ensuite utilisée afin de construire un squelette basé sur un calcul du graphe de Reeb associé.

Auto Diffusion Function

On définit, pour un paramètre t donné:

 \displaystyle { ADFt(x) = \sum_{i = 0}^{\infty}} e^{- \lambda_{i} \frac{t}{\lambda_{1}}} \phi_{i} (x)^{2}  

 (\lambda_{0} < \lambda_{1} < .....) sont les valeurs propres de l'opérateur de Laplace-Beltami, l'équivalent discret du Laplacien sur notre maillage, et où  \displaystyle (\phi_{i}) sont les fonctions propres associées orthogonales deux à deux.

Cette fonction vient de la fonction K, solution d'équation de chaleur.

 \displaystyle { K(x, y, t) = \sum_{i = 0}^{\infty}} e^{- \lambda_{i} t} \phi_{i} (x) \phi_{i} (y)

Physiquement, si on injecte de la chaleur au point y, la fonction K(x, y, t) représente la quantité restante au point x au bout d'un temps t. Dans notre cas,  ADF(x, t) = K(x, x, \frac{t}{\lambda_{1}}) , donc le point d'origine est le même que le point observé.

Homer1.jpg
Homer3.jpg





Concrètement, la principale difficulté pour calculer cette fonction est de trouver les éléments propres de l'opérateur de Laplace-Beltrami. Pour ce faire, on cherche les éléments propres du Laplacien L de l'ensemble des points du maillage,

 L_{ij} = \left\{
    \begin{array}{ll}
        distance(i, j) & \mbox{si } i \ne j \\
        \displaystyle \sum_{k} distance(i, k) & \mbox{sinon}
    \end{array}
\right. 

La distance utilisée est la distance cotangente définie ainsi:  distance(i, j) = \frac{cotan(\alpha_{1}) + cotan(\alpha_{2})}{2}

Cotan.jpg



En pratique, on utilise que les éléments propres ayant une contribution suffisante dans l'ADFt, c'est à dire tels que:  e^{- \lambda_{i} \frac{t}{\lambda_{1}}} > 0,001

L'ADFt est utilisée car elle possède différentes propriétés interessantes : les valeurs qu'elle prend sur un maillage sont invariantes par orientation du repère, par rotation, par changement d'échelle. Elles sont de plus très locales. Pour toutes ces raisons, l'ADFt est interessante pour la construction de squelettes stables.

Graphe de Reeb

Le graphe de Reeb est obtenu en parcourant l'ensemble des points d'un maillage. Un traitement spécifique est fait sur chacun de ses points en fonction de leur valeur à travers une fonction f qui dans notre cas est l'Auto Diffusion Function. Ce graphe représente l'ensemble des composantes connexes d'un maillage comme représenté ci-dessous en prenant une fonction hauteur:

Reeb conn.jpg

Chaque point du maillage a un état ainsi qu'un traitement spécifique parmi les suivants:

- Minimum : l'ensemble de ses voisins a une valeur supérieure. Dans ce cas là, on crée un point dans le graphe et une arete (on ne sais pas où elle va).

Min.jpg

- Maximum : l'ensemble de ses voisins a une valeur inférieure. Dans ce cas là, on crée un point dans le graphe en finissant une arete.

Max.jpg

- Régulier : l'ensemble de ses voisins représente 2 groupes distincts de "+" et de "-". Dans ce cas là, on met juste à jour la ligne de niveau.

Regulier.jpg

- Selle :l'ensemble de ses voisins représente plus de 2 groupes distincts de "+" et de "-". Dans ce cas là, on crée un point dans le graphe avec autant d'aretes entrantes que de lignes de niveaux rouge et autant d'aretes sortantes que de lignes de niveaux bleu.

Selle.jpg

Construction du squelette

A partir du graphe de Reeb obtenu précedemment, on peut maintenant construire le squelette du maillage. Pour cela, il s'agit de simplifier ce graphe en fusionnant les points trop proche et enfin en extrayant les "joints" et les "os".

La dernière étape consiste à calculer un autre squelette du même maillage en utilisant encore une fois l'Auto Diffusion Function mais en prenant un t différent et à le fusionner avec le premier squelette trouvé. Cette fusion se fait en utilisant les "joints" et les "os" calculés.

Dans notre projet, dû à un manque de temps, nous n'avons pas implémenté cette fusion.

Voici quelques exemples de squelettes que nous avons obtenus pour t=2:

Dino+squel1.jpg
Homer+squel1.jpg



Voici maintenant un autre squelette obtenu pour t=0.1.

Homer+squel2.jpg

On remarque ici que le choix de t influe grandement sur le squelette. En effet, si t est grand, la condition  e^{- \lambda_{i} \frac{t}{\lambda_{1}}} > 0,001 élimine une grande partie des éléments propres, ne gardant que les premiers. Or les premiers éléments propres du squelette correspondent aux grandes direction du maillage. Dans le cas où t est petit, on a beaucoup plus de détail ce qui n'est pas toujours souhaitable.


Algorithme original de mise en correspondance

L'algorithme de mise en correspondance de deux maillages représentant le même objet d'animation que nous avons réalisé s'appuie sur les squelettes calculés précedemment, et sur leur stabilité au bruit, deformations mineures, etc...

Le concept est le suivant : Dans un premier temps, on associe à chaque point du squelette du premier maillage le point correspondant sur le deuxième. Ensuite, pour retrouver un point du premier maillage sur le second, on passe par le squelette :



Mise en correspondance des deux squelettes

Nous allons utiliser une distance sur le squelette : si un arc relie un point A et un point B, alors la distance entre A et B dans le squelette correspondra à la longueur de cet arc.

Arc.jpg









Pour réaliser l'association entre squelettes, on liste d'abord les points que nous appelerons “critiques” des deux squelettes, c'est à dire les points qui ont un seul voisin ou plus de deux voisins.

Oiseau 1.jpg
Oiseau 2.jpg


Ces points vont nous servir de repère pour identifier n'importe quel point du squelette : un point P est soit critique, soit situé entre deux points critiques A et B, et donc repérable sur l'arc [AB] par la longueur de l'arc [AP] ou [BP]. Si on associe les points critiques des deux squelettes, on peut en associer tous les points.

On dira que deux points critiques sont voisins critiques dans le squelette lorsqu'il existe un arc de points non critiques les reliant.

Une fois tous ces points critiques repérés, on leur associe à chacun un poids, correspondant à un doublet composé d'une part du nombre de voisins critiques, et d'autre part à la somme des distances aux voisins critiques, ayant une relation d'ordre lexicographique.

Même si l'objet change de pose, le squelette calculé est censé conserver la même topologie, le même nombre de points critiques, et chacun de ces points conserver son poids.

On se sert donc de ces poids pour associer les points critiques des deux squelettes : à chaque point critique du premier squelette on associe le point critique du deuxième squelette ayant le poids le plus proche.


Cette technique permet une association simple et rapide des deux squelettes. Cependant, elle repose sur la stabilité du squelette d'une part (expérimentalement bonne avec le squelette que nous calculons, et théoriquement encore meilleure avec le squelette avancé proposé dans l'article, fusionnant plusieurs squelettes) et sur le fait que chaque point a un poids différent sur un squelette (ce qui n'est pas le cas lorsque l'objet est trop symétrique). Lorsque ces conditions ne sont pas réunies, les associations sont erronées : le bras droit peut devenir le bras gauche, etc...


Mise en correspondance des deux maillages

Pour associer les points des deux maillages, ils ne nous reste qu'à associer chaque maillage et son squelette : pour retrouver un point du premier maillage sur le deuxième, on associe à ce point le point de son squelette qui lui correspond, on le retrouve sur le deuxième squelette, et on repasse sur le maillage.

A un point du maillage, on associe le point du squelette qui a été créé à partir de lui dans graphe de reeb.

A un point du squelette on associe la ligne de niveau de la fonction ADFt à partir de laquelle il a été créé. A partir d'un point du squelette, on peut donc retrouver un ensemble de points. Il faut trouver un moyen d'isoler le point que l'on cherche. La technique que nous avons choisie consiste à calculer la courbure du point choisi sur le premier maillage, et à choisir le point de la ligne de niveau sur le deuxième ayant la courbure la plus proche. Cette technique fonctionne très bien sur les points du maillage situés dans des zones où la géométrie locale n'est que peu modifiée, autrement dit la plupart des points. Elle peut cependant génèrer des associations fausses au niveau des joints.


Résultats

Voici quelques exemples de résultats obtenus. Nous avons choisi un point (bleu) sur la figure de gauche, l'algorithme calcule le point associé sur le maillage de droite et l'affiche aussi en bleu:


Bird 11 23 bec.jpg
Bird11 23 epaule2.jpg
Bird11 23 epaule1.jpg
Bird11 28 bras1.jpg


On retrouve les erreurs mentionnées plus haut:

Problème de symétrie:

Bird 11 23 pb sym.jpg


Problème de courbure:

Bird11 23 pb courb1.jpg


Bilan

En conclusion, nous avons réussi lier temporellement deux maillages. Ainsi, il est possible de suivre un point au cours du temps. Cela a été possible grâce à la fonction d'Auto Diffusion car elle possède des propriétés de stabilité très utiles à notre algorithme de mise en correspondance. Cela dit, en implémentant la partie "fusion des squelettes", ce dernier algorithme aurait fonctionné dans avec une proportion plus élevée d'images.

Nous avons pu remarquer que le choix du paramètre t et du nombre de valeurs propres calculées sont à déterminer empiriquement afin d'obtenir des squelettes exploitables. De plus la détermination des éléments propres de l'opérateur de Laplce-Beltrami représente la quasi totalité temps de calcul, il faut donc faire très attention au nombre de valeurs propres calculées afin d'avoir un algorithme s'éxécutant en temps raisonnable.

Nous avons eu beaucoup de mal à installer les différentes librairies, en particulier Arpack (1 semaine et demie). De plus, les informations fournies par l'article de référence sont bien souvent supposée acquise. Nous nous sommes confrontés au problème des "poupées russes" car chaque article de recherche renvoie vers un autre...

Ce projet est le premier que nous ayons fait en partant de zéro, en devant faire nos propres recherches, nos propres choix de conceptions, ce que nous avons apprécié. De plus, le concept du projet ainsi que son côté visuel nous ont particulièrement plus

Bibliothèques

- OpenMesh : librairie permettant la gestion de maillages 3D. Elle fournit de nombreuses fonctionnalités (itérateurs sur les faces, les points, ...). Elle est assez simple d'accès mais la documentation reste très sommaire.

- Arpack : librairie permettant la résolution d'équation linéaire de grande taille, elle permet notamment la diagonalisation de grandes matrices creuses (ce qui nous servira dans la suite). Elle est particulièrement difficile à installer car elle est assez ancienne et ne marche pas avec les nouvelles versions des compilateurs (Cela nous a pris plus d'une semaine afin de l'installer)


Références

Article de référence : http://evasion.imag.fr/Membres/Franck.Hetroy/Teaching/ProjetsImage/2010/Bib/gebal_et_al-sgp2009.pdf

Calcul des éléments propres pour l'opérateur de Laplace-Beltrami : http://cyrille.rossant.net/files/irm_rapport.pdf

Calcul du graphe de Reeb : www-ljk.imag.fr/Publications/.../rapport_dea_aujay.pdf

Transparents de la présentation

Media:projet_image.pdf