Méthode des Ensembles de Niveaux par Eléments Finis P 1 Jérôme Piovano Stage de DEA Sous...

Méthode des Ensembles de Niveaux par Eléments Finis P1

Jérôme PiovanoStage de DEA

Sous l’encadrement de Théodore Papadopoulo

INRIA – Sophia Antipolis

Projet Odyssée

Introduction1.

• Segmentation d’image• Trouver des regions d’images selon certaines caractéristiques

• Éléments finis • Méthode d’approximation discrète de fonctions continues

Implémenter la méthode des ensembles de niveaux à l’aide des éléments finis

• Ensembles de niveaux ou « Levels Sets »• Modélise l’évolution d’une hypersurface à travers une fonction continue• Application à la segmentation d’image

Plan

Définitions Ensemble de niveaux Éléments finis

Modélisation Équations d’évolution Discrétisation temporelle Discrétisation spatiale

Algorithmique Notion de bande Évolution de la bande Simplification des équations

Résultats Évolution par courbure moyenne Évolution pour contour géodésiques

Conclusion

Définitions

Évolution de l’interface par l’intermédiaire de la fonction distance

= 1 = Détection de contours géodésiques.

Schémas par « bande » à bases de différences finies instabilité

Ensembles de niveaux ou Levels Sets

t + |r| = 0;

 Interface représentée par le niveau 0 d’une « fonction distance  » 

Définitions

Approximation discrète d’une fonction continue1. Partitionnement de l’espace en éléments formant un maillage

2. Calcul des valeurs de aux sommets du maillage

3. Représentation de par interpolation linéaire de ses valeurs aux sommet

Méthode des éléments finis

Plan

Définitions Ensemble de niveaux Éléments finis

Modélisation Équations d’évolution Discrétisation temporelle Discrétisation spatiale

Algorithmique Notion de bande Évolution de la bande Simplification des équations

Résultats Évolution par courbure moyenne Évolution pour contour géodésiques

Conclusion

Modélisation

Soit u l’approximation de la fonction distance par élément finis

u définie par 2 facteurs :

Espacement constant entre ses différents niveaux

Vitesse d’évolution

Calculs des valeurs de u sur les sommets du maillage en minimisant une énergie associée a ces 2 termes

(rxu)2 - 1 = 0

ut - = 0

Calcul de la fonction distance grâce aux éléments finis

Modélisation

u(x, t + t) = u(x, t) + v(x, t)

v(x, t) = u(x, t + t) - u(x, t)

v(x, t) = t ut(x, t)

Exprimer l’évolution de u sous forme discrète dans le temps.

v = “Pas d’évolution”

Discretisation temporelle

(rxu)2 - 1 = 0

ut - = 0

( rxu + rxv)2 - 1 = 0

v - t = 0

Modélisation

Discretisation spatiale

Discretisation de Galerkin : Utilise des fonctions de « bases » comme des

fonctions tests mesurant la déviation au voisinage du sommet auquel elles sont attachées

( rxu + rxv)2 - 1 = 0

v - t = 0

s((ru + r v)2 - 1)i = 0 8 i 2 1 … n

s(v - t)i = 0 8 i 2 1 … n

Résolution d’un système de 2n équations à n inconnues qui est donc surdéterminé

Résolution par moindres carrés

Modélisation

On peut exprimer les équations précédente en fonction des valeurs aux sommets du maillage de u et v

Reformulation des équations

s((ru + r v)2 - 1)i (u + v)TQi(u + v) - si

s(v - t)i Pi v - tsi

Les vitesses nécessitent le calcul d’une dérivée seconde théoreme de Green

Plan

Définitions Ensemble de niveaux Éléments finis

Modélisation Équations d’évolution Discrétisation temporelle Discrétisation spatiale

Algorithmique Notion de bande Évolution de la bande Simplification des équations

Résultats Évolution par courbure moyenne Évolution pour contour géodésiques

Conclusion

Algorithmique

Adaptation du problème à un maillage 2D régulier

Algorithmique

La fonction distance n’est pas calculé sur la totalité de l’espace, mais au voisinage du niveau 0

Ajout des éléments proches du niveau 0 Suppression des éléments éloignés du niveau 0

Algorithmique

Dynamique d’évolution

Algorithmique

Les equations d’evolutions peuvent se simplifier sur des maillages 2D réguliers à des calculs par difference finies.

Sur un maillage de type:

(u + v)TQ0(u + v) 1/6((S2 - S3)2 + (S3 - S4)2 + (S5 - S6)2 + (S6 - S1)2) +

1/3((S1 - S0)2 + (S2 - S0)2 + (S4 - S0)2 + (S5 - S0)2 )

AlgorithmiqueAvantage de la methode

Les equations d’evolutions peuvent se simplifier sur des maillages 2D réguliers à des calculs par difference finies.

Sur un maillage de type:

Fin