Encadrants: Luce Morin, Raphaèle Balter Morphing 3D de modèles estimés Stage de fin d études...

Encadrants:Encadrants: Luce Morin, Raphaèle Balter Luce Morin, Raphaèle BalterEncadrants:Encadrants: Luce Morin, Raphaèle Balter Luce Morin, Raphaèle Balter

Morphing 3D de modèles estimésMorphing 3D de modèles estimés

Stage de fin d ’étudesStage de fin d ’études

Benjamin Le GuenBenjamin Le Guen

2

IntroductionIntroduction

• Temics, Janvier 2002 : Schéma de Temics, Janvier 2002 : Schéma de codage/transmission/décodage de codage/transmission/décodage de séquences vidéo réellesséquences vidéo réelles

• Représentation synthétique sous Représentation synthétique sous forme de modèles 3Dforme de modèles 3D

• ObjectifObjectif– Améliorer le rendu des séquences Améliorer le rendu des séquences

reconstruites et virtuelles reconstruites et virtuelles =>Mettre au point un =>Mettre au point un post-traitementpost-traitement

3

PlanPlan

• IntroductionIntroduction• ContexteContexte• Travail réaliséTravail réalisé• RésultatsRésultats• ConclusionConclusion

4

• IntroductionIntroduction• ContexteContexte• Travail réaliséTravail réalisé• RésultatsRésultats• ConclusionConclusion

5

La structure d ’accueilLa structure d ’accueil

• L ’IrisaL ’Irisa– Informatique et Signaux AléatoiresInformatique et Signaux Aléatoires– Unité mixte de recherche Unité mixte de recherche (INRIA, (INRIA,

CNRS, Rennes 1, INSA)CNRS, Rennes 1, INSA)– 25 équipes autour de grands thèmes 25 équipes autour de grands thèmes

scientifiquesscientifiques

• Le projet TemicsLe projet Temics– Analyse et modélisation de séquences vidéoAnalyse et modélisation de séquences vidéo,,– Codage conjoint source-canal,Codage conjoint source-canal,– TatouageTatouage

www.irisa.fr

6

La structure d ’accueilLa structure d ’accueil

• Environnement techniqueEnvironnement technique– OS : UNIX, LinuxOS : UNIX, Linux– Langage : C/C++Langage : C/C++– Librairie graphique : CGALLibrairie graphique : CGAL

www.cgal.org

7

Codage d ’une séquencevidéo par flux de modèles 3DCodage d ’une séquencevidéo par flux de modèles 3D• Modèles 3D obtenus à partir Modèles 3D obtenus à partir

d ’une vidéod ’une vidéo• Stéréo-reconstructionStéréo-reconstruction

• Maillage triangulaire uniformeMaillage triangulaire uniforme

8

Codage d ’une séquencevidéo par flux de modèles 3DCodage d ’une séquencevidéo par flux de modèles 3D• Modélisation dépendant Modélisation dépendant

du point de vue du point de vue• Un modèle pour 15-30Un modèle pour 15-30

images de la séquence images de la séquence (notion de (notion de GOPGOP))

Séquence originale Carte d ’élévationsModèle 3D

9

DécodageDécodage

10

ApplicationsApplications

Chemin virtuel Réalité augmentée

Codage 3D - 60 kbits/s H26L - 115 kbits/S

11

DifficultéTransition entre modèlesDifficultéTransition entre modèles

• CausesCauses– Saut géométrique (erreurs Saut géométrique (erreurs

d ’estimation/zones découvertes)d ’estimation/zones découvertes)– Saut de texture (erreurs/point de Saut de texture (erreurs/point de

vue/illumination)vue/illumination)– Saut de connectivité (élévations sur Saut de connectivité (élévations sur

maillage uniforme)maillage uniforme)

Transition

saut geom

12

Approches précédentesApproches précédentes• Fondu dans l ’espace des textures Fondu dans l ’espace des textures saut de saut de

géométrie/connectivitégéométrie/connectivité• Fondu 3D Fondu 3D effet fantômeeffet fantôme• Morphing d ’élévations Morphing d ’élévations saut topologiquesaut topologique

zones à occultationzones à occultation non traitéesnon traitées

nn

cn

tt

tt

tt

tt

1

1

13

• IntroductionIntroduction• ContexteContexte• Travail réaliséTravail réalisé• RésultatsRésultats• ConclusionConclusion

14

Morphing 3DMorphing 3D

• ObjectifObjectif– Passer des cartes d ’élévations à de la vraie Passer des cartes d ’élévations à de la vraie

3D3D

• MéthodeMéthode– ParamétrisationParamétrisation pour fixer les pour fixer les

correspondancescorrespondances– FusionFusion des paramétrisations pour des paramétrisations pour

construire la connectivité communeconstruire la connectivité commune– InterpolationInterpolation des géométries pour générer des géométries pour générer

les modèles intermédiairesles modèles intermédiaires

15

Morphing 3DMorphing 3D

– MMn n : modèle source: modèle source

– MMn+1n+1 : modèle destination : modèle destination

– HHnn : paramétrisation de M : paramétrisation de Mnn

– HHn+1n+1 : paramétrisation de M : paramétrisation de Mn+1n+1

– HHcc : fusion des paramétrisations : fusion des paramétrisations

– FFnn : connectivité fusion + géométrie n : connectivité fusion + géométrie n

– FFn+1n+1 : connectivité fusion + géométrie n+1 : connectivité fusion + géométrie n+1

16

Morphing 3DMorphing 3D

• ParamétrisationParamétrisation• FusionFusion• InterpolationInterpolation

17

La paramétrisationLa paramétrisation

• PrincipePrincipe– correspondance bijective entre une surface correspondance bijective entre une surface

3D discrète et un maillage planaire3D discrète et un maillage planaire– mesure de distorsionmesure de distorsion

• conformeconforme• authaliqueauthalique

– choix d ’épingleschoix d ’épingles– résolution d ’un système linéairerésolution d ’un système linéaire

Intrinsic parameterizations of Intrinsic parameterizations of surface meshes.surface meshes.

[Alliez 02][Alliez 02]

CU

UMMMU

fixées

libresA 0

I 0

18

Adaptation au contexteAdaptation au contexte

• Bords de deux modèle successifs non Bords de deux modèle successifs non superposés superposés

=> paramétrisation à bords libres=> paramétrisation à bords libres• Exacte superposition des textures Exacte superposition des textures

pour éviter l ’effet fantôme pour éviter l ’effet fantôme => nombreuses épingles=> nombreuses épingles

• Modèles bruités Modèles bruités => caractéristiques => caractéristiques

géométriques non fiablesgéométriques non fiables

19

Choix du critère d ’optimisationChoix du critère d ’optimisation

• Paramétrisation de FloaterParamétrisation de Floater– angles inférieurs àangles inférieurs à– bords épinglés bords épinglés

2/

20

ImplémentationImplémentation

• Espace de paramétrisation: IEspace de paramétrisation: I55

• Paramétrisation de MParamétrisation de Mn+1n+1

– Grille triangulaire uniformeGrille triangulaire uniforme

• Paramétrisation de MParamétrisation de Mnn

– Paramétrisation connue sur IParamétrisation connue sur I00

– Correspondances dans ICorrespondances dans I55 données par le données par le champ de mouvement champ de mouvement

21

ImplémentationImplémentationReconstruction du champ de mouvement

22

ImplémentationImplémentation

• Paramétrisation de MParamétrisation de Mnn

– Traitement des correspondances données Traitement des correspondances données par le champ de mouvement par le champ de mouvement

=> choix des points à libérer=> choix des points à libérer

• Algorithme de paramétrisationAlgorithme de paramétrisationddl = 0;Tant que (param non valide)

Choix des points à libérer(ddl);Construction du système linéaire;Résolution;Etudier la validité du résultat;ddl = ddl +1;

Fin Tant que

23

Résultat de la paramétrisationRésultat de la paramétrisation

n n+1

24

Morphing 3DMorphing 3D

• ParamétrisationParamétrisation• FusionFusion• InterpolationInterpolation

25

La fusionLa fusion

• ObjectifObjectif– construire une connectivité communeconstruire une connectivité commune

• IdéeIdée– tirer partie des paramétrisations obtenues tirer partie des paramétrisations obtenues

dans un même espace 2Ddans un même espace 2D– principe:principe:

26

Etapes de la fusionEtapes de la fusion

27

Recherche des intersections Algorithme généralRecherche des intersections Algorithme général [Kent 92][Kent 92]

• Initialisation d ’une liste de travail WLInitialisation d ’une liste de travail WL• Tant que WL non videTant que WL non vide

– Prendre 1ère arête de WLPrendre 1ère arête de WL– Rechercher ses Rechercher ses

intersectionsintersections– Compléter WLCompléter WL

28

Algorithme généralAlgorithme général [Kent 92][Kent 92]

• Rechercher ses intersections?Rechercher ses intersections?• Initialiser une liste Initialiser une liste

d ’arêtes candidates CLd ’arêtes candidates CL– Tant que CL non videTant que CL non vide

• Prendre 1ère arête Prendre 1ère arête de CLde CL

• Intersection?Intersection?– Succès: ajouter Succès: ajouter

sommetsommet

• Compléter CLCompléter CL

29

Algorithme généralAlgorithme général [Kent 92][Kent 92]

• Parcours de CLParcours de CL

30

Algorithme généralAlgorithme général [Kent 92][Kent 92]

• Fin de la rechercheFin de la recherche

31

Gestion des cas particuliersGestion des cas particuliers

• Tenter de déjouer tous les cas Tenter de déjouer tous les cas particuliersparticuliers

• Un exempleUn exemple– v1a est v1a est superposedsuperposed ou ou

on_edgeon_edge• problème intrinsèque problème intrinsèque

à la manipulation des réels à la manipulation des réels• astuce: partager CL en deuxastuce: partager CL en deux

32

Créations des liens entre intersectionsCréations des liens entre intersections

• Liste des intersections retenues pour Liste des intersections retenues pour chaque arêtechaque arête

• AlgorithmeAlgorithme

Pour chaque arête ea = [v1a,v2a] de Hn

Si sa liste d ’intersections a plus d ’un élément Trier la liste; Pour i = 0 à taille(liste_inter) - 1 Joindre(liste_inter[i],liste_inter[i+1]); i++; Fin Pour; Fin Si;Fin Pour;

33

Joindre()?Joindre()?

34

Etapes de la fusionEtapes de la fusion

35

Ajout des sommets non singuliers de Mn

Ajout des sommets non singuliers de Mn

• ProblèmeProblème– maintenir la cohérence du polyèdremaintenir la cohérence du polyèdre

• Solution proposéeSolution proposée– liens vers les liens vers les

premières premières intersections intersections

– ajout face ajout face par facepar face

36

Ajout des sommets non singuliers de Mn

Ajout des sommets non singuliers de Mn

• 2 liens ou plus : ajout direct2 liens ou plus : ajout direct• 0 ou 1 lien : traitement a posteriori0 ou 1 lien : traitement a posteriori

37

Résultat de la fusionRésultat de la fusion

38

Morphing 3DMorphing 3D

• ParamétrisationParamétrisation• FusionFusion• InterpolationInterpolation

39

InterpolationInterpolation

• Construire les arguments source et Construire les arguments source et destinationdestination

• Les interpoler linéairementLes interpoler linéairement• Avant tout…Avant tout…

– Triangulation de la fusionTriangulation de la fusion• parcours des facettes de Hparcours des facettes de Hcc,,

• subdivision (algorithme récursif) en subdivision (algorithme récursif) en commençant par les angles les plus grands.commençant par les angles les plus grands.

40

Résultats de la triangulationRésultats de la triangulation

41

Résultats de la triangulationRésultats de la triangulation

42

Résultats de la triangulationRésultats de la triangulation

43

Construction des argumentsConstruction des arguments• On a:On a:

– connectivité n et géométrie n,connectivité n et géométrie n,

– leur union représentée par Mleur union représentée par Mnn,,

– connectivité n+1 et géométrie n+1,connectivité n+1 et géométrie n+1,

– leur union représentée par Mleur union représentée par Mn+1n+1,,

– la connectivité fusion.la connectivité fusion.

• On voudrait,On voudrait,– l ’union de la connectivité fusion et de la l ’union de la connectivité fusion et de la

géométrie n => argument source,géométrie n => argument source,– l ’union de la connectivité fusion et de la l ’union de la connectivité fusion et de la

géométrie n+1 => argument destination.géométrie n+1 => argument destination.

44

Application des géométries n et n+1Application des géométries n et n+1

• Données disponibles pour un sommet Données disponibles pour un sommet v de Hv de Hcc V non singulier

ou on_edge de Mn

Géométrie n

Coord barydans facette de

Hn+1

V non singulier de Mn+1

Coord bary dans facette de

Hn

Géométrie n+1

V superposed

Géométrie n

Géométrie n+1

V split

Coord barysur arete de Hn+1

Coord barysur arete de Hn

indexa,b,cα,β,γ

45

Calcul des coordonnées barycentriques

Calcul des coordonnées barycentriques• Coordonnées des sommets de MCoordonnées des sommets de Mnn dans dans

HHn+1n+1

– calcul au moment de la rétro-projection,calcul au moment de la rétro-projection,– direct sur grille uniforme avec coordonnées direct sur grille uniforme avec coordonnées

cartésiennes (i,j).cartésiennes (i,j).

• Si v est non singulier de MSi v est non singulier de Mn+1n+1

– parcourir chaque facette de Hparcourir chaque facette de Hnn,,

– si v est dans la facettesi v est dans la facette• calculer ses coordonnées barycentriques calculer ses coordonnées barycentriques

dans la facette.dans la facette.

46

Application d ’une texture à Fn et Fn+1

Application d ’une texture à Fn et Fn+1

• Texture de FTexture de Fnn : I0 : I0– sommets ne provenant pas de Msommets ne provenant pas de Mn n : :

combinaison barycentrique des textures combinaison barycentrique des textures des sommets de Mdes sommets de Mn n voisins.voisins.

• Texture de FTexture de Fn+1n+1 : I5 : I5

47

Calcul des modèles intermédiairesCalcul des modèles intermédiaires

• Interpolation linéaireInterpolation linéaire

1)1( nnc FFM nn

cn

tt

tt

tt

tt

1

1

48

• IntroductionIntroduction• ContexteContexte• Travail réaliséTravail réalisé• RésultatsRésultats• ConclusionConclusion

49

RésultatsSaut géométrique/topologiqueRésultatsSaut géométrique/topologique

Sans post-traitement Morphing d ’élévations Morphing 3D

50

RésultatsSaut géométrique/topologiqueRésultatsSaut géométrique/topologique

51

RésultatsReconstruction de la séquenceRésultatsReconstruction de la séquence

• Suppression de l’effet ghostSuppression de l’effet ghost

original fondu

Morphing élévations

Morphing 3D

52

RésultatsNavigation virtuelleRésultatsNavigation virtuelle

originalesans

post-traitement

Morphingd ’élévations

Morphing 3D

53

RésultatsDéfautsRésultatsDéfauts• Flou dans certains GOP Flou dans certains GOP

– cause:mise en cause:mise en correspondance correspondance inexacte lors de la inexacte lors de la

paramétrisation de Mparamétrisation de Mnn

• Méthode lourde à l ’encontre du schéma Méthode lourde à l ’encontre du schéma de reconstruction temps réelde reconstruction temps réel

54

• IntroductionIntroduction• ContexteContexte• Travail réaliséTravail réalisé• RésultatsRésultats• ConclusionConclusion

55

ConclusionConclusion

• Vrai morphing tridimensionnelVrai morphing tridimensionnel– suppression des sauts topologiquessuppression des sauts topologiques– suppression des sauts géométriquessuppression des sauts géométriques– suppression de l ’effet ghostsuppression de l ’effet ghost

• Mais…Mais…– GOP pièges à gérerGOP pièges à gérer– perspective temps réelperspective temps réel

56

PerspectivesPerspectives

• Poursuivre les tests sur la fusion pour Poursuivre les tests sur la fusion pour gérer des cas particuliers non traitésgérer des cas particuliers non traités

• Gestion des GOP piègesGestion des GOP pièges– tenter une paramétrisation moins tenter une paramétrisation moins

contraintecontrainte

• Problème du temps réelProblème du temps réel– calcul des arguments de l ’interpolation au calcul des arguments de l ’interpolation au

codagecodage

• Amélioration du renduAmélioration du rendu– interpolation plus courbeinterpolation plus courbe

57

Questions?Remarques?Questions?

Remarques?