pp. 149-162

149

Reconstruction 3D robuste du visage 9 approche duale - mouvement-structure , , Laurent P E Y R O N N Y * , Val6rie B U R D I N * , Christian R O U X * Faouzi G H O R B E L * *

R6sum6

Cet article pr~sente une approche originale de reconstruction et d'animation tridimensionnelle du visage humain & partir d'une s~quence monoculaire et non calibr~e d'images. Un processus d'analyse-synthbse de l'information contenue dans les images permet le clonage 2D--> 3D grace au fonctionnement combine de deux algorithmes de reconstruction fondUs sur le mouvement (synthbse), Le pr~traitement sur les images aboutissant ?t la raise en correspondance temporelle de points (analyse) est r~alis~ par un algorithme de d'appariement de blocs utilisant la grille fournie par la triangulation de Delaunay de la premibre image. La classification du mouvement est ensuite r~alis~e par l'utilisation d'une famille locale de descripteurs invariants. Quelques r~sultats exp6rimentaux validant la d~marche employee sont ~galement pr~sentEs.

synthesis assumptions. Experimental results on synthetic and noisy data set validate the entire approach. Key words: Image processing, Tridimensional image, Videophone, Image reconstruction, Image face.

Contents

I.

Introduction Pr~traitements 2D : appariements et analyse des projections III. Clonage 2D--> 3D : dualit~ mouvement - structure IV. Quelques r~sultats V. Conclusion Bibliographie (28 r~f.) II.

I. I N T R O D U C T I O N

Mots cl6s : Traitement image, Image tridimensionnelle, Visiophone, Reconstruction image, Visage.

R O B U S T 3D FACE R E C O N S T R U C T I O N : A "MOVEMENT-STRUCTURE " DUAL APPROACH Abstract

An original approach f o r three-dimensional reconstruction and animation of human face with a monocular and un-calibrated acquisition system is presented. This method is based on the classical analysis-synthesis scheme. A three-dimensional reconstruction of shape and movement is performed with a combination of two algorithms using the well-known "Z from motion" principle. Therefore a pre-processing step is needed to first detect the human face on videoconference sequence. Then, a set o f points is tracked with a new hybrid and adaptive block-matching algorithm using the Delaunay tessellation. A local algebraic projective invariant family performs the 3D movement classification to satisfy the 3D

L a v i s i o n t r i d i m e n s i o n n e l l e , et en p a r t i c u l i e r les a p p l i c a t i o n s de visiophonie 3D, ont fait l ' o b j e t de n o m breuses recherches ces derni6res ann6es. D e plus, l ' a v 6 n e m e n t de la n o r m e MPEG-4 est la c o n s 6 q u e n c e d ' u n int6r& grandissant sur les techniques m u l t i m 6 d i a s et de r6alit6 v i r t u e l l e , c o m m e la c r 6 a t i o n et l ' a n i m a t i o n de c l o n e s h u m a i n s [21, 22, 23]. L a p r o b l 6 m a t i q u e de la reconstruction tridimensionnelle a partir de l ' i n f o r m a t i o n dans les images a 6t6 l a r g e m e n t d6crite dans la litt6rature [25, 28]. L e processus de calibration des syst~mes st6r6os c o p i q u e s est relativement instable m a i s p e r m e t de form u l e r des a l g o r i t h m e s de r e c o n s t r u c t i o n de m a n i ~ r e assez s i m p l e [25]. Les techniques de vision m o n o c u l a i r e s i m p o s e n t , quant ~ elles, une c e r t a i n e c o n n a i s s a n c e a priori sur la structure ou le m o u v e m e n t t r i d i m e n s i o n n e l de la sc~ne observ6e. N o u s avons fait le c h o i x d ' u t i l i s e r

une seule camera non calibr~e pour r~aliser la reconstruction du mouvement et de la structure d'un objet dvoluant librement dans la sc~ne. Apr~s avoir d6tect6 puis suivi le v i s a g e p a r l'int6gration d ' u n profil elliptique, l ' a p p a r i e m e n t de points dans

*l~cole Nationale Sup6rieure des T616communications de Bretagne D6partement ITI Technop61e de Brest-Iroise, BP 832 - F-29285, Brest, Cedex France. Email : laurent, peyronny@enst-bretagne, fr **Centre d'l~tudeset de Recherchesen Tgl6communicationsde Tunisie(CERT)42, rue Asdrubal- 1002, Tunis,Cedex (Tunisie).faouzi.ghorbel@cert,mincom, tn 1/14

ANN. TI~LI~COMMUN.,55, n ~ 3-4, 2000

150

L. PEYRONNY

-- RECONSTRUCTION

3D R O I 3 U S T E D U V I S A G E : A P P R O C H E

la sequence d'images est rdalisE principalement par un algorithme d'appariement de blocs adaptatif <~hybride >~ (H-ABMA). L'algorithme de reconstruction admet comme hypothEse forte de fonctionnement la mise en mouvement rigide des points dans l ' e s p a c e tridimensionnel. Afin de converger idEalement vers la bonne solution, nous avons adjoint au traitement des images une dtape de classification fondde sur l'utilisation de descripteurs locaux et indEpendants de toute projection (cf w II.3). La reconstruction 3D du mouvement et de la profondeur est obtenue grfice h Faction conjointe de deux algorithmes fonctionnant sur le mEme principe d'analyse temporelle des projections d'un ensemble de points en mouvement rigide (cf w Nous conclurons au w IV par l'analyse des rdsultats obtenus sur des donndes synthEtiques et prdsenterons les perspectives de ce travail et notamment l'application de ces mEthodes h des donndes rEelles.

II. P R I ~ T R A I T E M E N T S 2D : A P P A R I E M E N T S ET ANALYSE DES PROJECTIONS

D U A L E << M O U V E M E N T

-- S T R U C T U R E

>>

II.l.1. Principe de fonctionnement Le principe de recalage est l'ajustement de l'ellipse sur le contour de la t~te obtenu par le gradient (grad) de l'image I (cf Fig. 1.b). La somme des valeurs des gradients binarisEs sur les diffErents contours elliptiques possibles dans l'espace de recherche constitue le <
IIgrad(l(bcos(o~ - 0) - x o, asin(~x - 0) -Yo) I[.

Le contour elliptique de paramEtre (Xo,Yo, a,b,~) maximisant cette s o m m e est alors choisi (cf Fig. 1.c). La detection et le suivi du visage peuvent ~tre bornEs grace ~ des heuristiques d ' o r d r e m o r p h o m d t r i q u e s (hypothEse de f o r m e elliptique) et cinEmatiques (hypoth~se des faibles m o u v e m e n t s ) . Enfin, des considerations sur la dimension (n c x nl) et la nature (sEquence visiophonique) des images compl~tent les hypotheses p e r m e t t a n t de borner des paramOtres de l'ellipse [1, 3, 6] II.1.2. Complexit~ algorithmique et temps de calcui

I L l . S u i v i d u visage : r e c a l a g e d ' u n m o d u l e elliptique Nous avons adoptE une mEthodologie utilisant l'information de forme bidimensionnelle c o m m e principe de detection du visage. Le processus de recalage de la fonction paramEtrique elliptique sur le visage dans une sequence d'images visiophoniques utilise deux principes [10] : un principe de detection fondE sur l'hypoth~se de forme elliptique du visage et un principe de suivi fondE sur l'hypothEse de mouvements faibles et continus. Dans notre cas, il s'agit d'estimer les 5 parambtres (xo,Yo,a,b, ct) ok (X~Yo) est le centre, a et b respectivement le grand et le petit rayon c~, et l'orientation (angle de rotation autour du centre) de la representation paramEtrique d'une ellipse (cf Fig. 1.a).

Le principal inconvenient de ce type d'approche reside dans la grande dimension de l'espace de recherche. Cette derni~re depend de la taille de l'image. Dans le cas d'une sequence d'images visiophonique au format HALF-CIF (de dimension 288 x 360), la dimension de l'espace de recherche vaut approximativement 2.1011 ! Dans l'Etape de suivi, l'hypothEse de faibles mouvements permet de ne faire varier l'amplitude des param~tres de l'ellipse que dans des proportions restreintes. Si on nEglige la premiere image de la sequence Miss America, le temps d'occupation moyen du cPc pour le calcul des parambtres de l'ellipse est d'environ 0.5 s par image et la dimension de l'espace de recherche est rEduite h environ 5.103. (PC-Linux, 2 x PII-266MHz, 256 Mo RAM).

FIG. 1. - - Ajustement du profil elliptique sur l'image

Ellipticalfitting on the gradient image A N N , TI~LI~COMMUN,, 5 5 ,

n~3-4, 2000

2/14

L. PEYRONNY-- RECONSTRUCTION3D ROBUSTEDU VISAGE" APPROCHEDUALE<

15 1

FIG. 2. - - Adaptation 5 la photom6trie de l ' i m a g e

Adaptation to imagephotometry

II.2. Suivi r o b u s t e d e p o i n t s : l ' a l g o r i t h m e H - - A B M A

A contrario des mdthodes de reconstruction <~ orientdes module >~ qui tentent d'ajuster la projection d ' u n module tridimensionnel a priori sur l'image [4, 19, 15], l'approche que nous avons adopt6e ndcessite le suivi de points sur la sdquence d'images. Afin d'apparier ces points, nous avons choisi d'utiliser un algorithme d'appariements de blocs en assignant le point au centre du bloc. Aprbs compensation du mouvement global (obtenu grace h l'estimation du mouvement de l'ellipse prdc6demment recalde), nous recherchons pour chaque bloc de la grille un bloc similaire au sens d ' u n e certaine mesure de similarit6 (i.e. m o y e n n e quadratique intdgr6e) dans une zone de taille variable. Le calcul d ' u n e mesure de confiance appelde <~ arrange et ordonne les distances euclidiennes entre les P points. Elle aboutit h une complexit6 de calcul en O(P log P) [ 14]. Afin d'am61iorer les performances globales de cette mdthode, nous avons adjoint deux dtapes suppldmentaires au processus de mise en correspondance : l'adaptation glla photom~trie de l'image par rd-dchantillonage des niveaux de gris et la structuration du voisinage des points obtenue par triangulation de la premibre image. II.2.1. Adaptation : la photomdtrie de l'image

La redistribution des niveaux de gris de l ' i m a g e permet d ' d v i t e r les problbmes de saturation sur le visage qui p r o v o q u e n t l ' a p p a r i t i o n de zones h o m o gbnes ne c o n v e n a n t pas pour l ' a l g o r i t h m e de blockmatching. A partir des rdsultats expdrimentaux, nous avons constatd que les histogrammes correspondant au visage, sous des conditions d ' i l l u m i n a t i o n non extremes, ont toujours une forme proche d ' u n e gaussienne. N o u s observons ~ la figure 2a les histogrammes de la zone d ' i n t 6 r & (ROI) pour la premiere image de la sdquences missa. Le rd-dchantillonage des niveaux de

3/14

gris s ' e f f e c t u e au travers de la f o n c t i o n de rddchantillonnage p o l y n o m i a l e illustrde dans la figure 2b.

II.2.3. Hybridation : structuration des donn~es

L'initialisation de la grille gdndratrice des centres des blocs par les nceuds de la triangulation de Delaunay de la premibre image de la s6quence offre les propridtds suivantes : - Facilit~ de comparaison : la triangulation de Delaunay est obtenue grace aux informations de m o y e n n e et de variance de la texture locale de t'image. Les nceuds sont alors les centres des blocs possddant des caractdristiques relativement identifiables et discriminantes ; - Facilit~ d'identification des voisins : grace ~ la triangulation, les voisins d ' u n point sont directement obtenus dans la structure des donn6es ; -Facilit~ de representation 2D : la triangulation obtenue n'est autre que la projection sur l ' i m a g e de la triangulation de l ' o b j e t 3D que l ' o n souhaite reconstruire ; - Facilit~ d'identification des occultations et apparitions : l'identification des occultations et des apparitions de points dans la s6quence sera facilitde par cette reprdsentation (Z-buffering). L'algorithme de triangulation <~ SPHT O4 KEEP AND MERGE >> [1, 6] permet une repr6sentation multidchelle de la grille des points a suivre (cf. Fig. 3-c).

II.3. C l a s s i f i c a t i o n d u m o u v e m e n t des points

tridimensionnel

Les algorithmes de reconstruction que nous avons dtablis formulent l'hypothbse de rigiditd du mouvement tridimensionnel [12, 13, 24, 28]. Or, nous ne possddons que les projections sur les images des m o u v e m e n t s tridimensionnels des points de la sc~nes (primitives appa-

ANN. Tt~LI~COMMUN.,55, n~ 3-4, 2000

152

L. PEYRONNY

-- RECONSTRUCTION

FIG. 3. - -

3D ROBUSTE DU VISAGE : APPROCHE

DUALE

<< M O U V E M E N T

-- S T R U C T U R E

>>

Hybridation par structuration des donndes

Data set neighbourhoods computation

rides). Nous cherchons ~ ddterminer un descripteur qui reste inchang6 par l ' a p p l i c a t i o n d ' u n e transformation projective sur un e n s e m b l e de points en m o u v e m e n t rigide dans l ' e s p a c e tridimensionnel. Quelques familles d'invariants de ce type sont proposdes dans la littdrature et sont construites ~ partir de la gdomdtrie diffdrentielle ou directement par des propridtds gdomdtriques [19]. II.3.1. T r a n s f o r m a t i o n s , p r o j e c t i o n s et i n v a r i a n c e

Les transformations les plus gdn6rales que l'on rencontre en vision se c o m p o s e n t d ' u n m o u v e m e n t euclidien de l'espace, not6 H et de l'action d'une projection, notde P, dont la forme la plus gdndrale est la perspective. Nous ddsirons obtenir une description I par rapport h toute projection de IP 3 dans IP2. Nous notons par convention IP2 le plan projectif rdel P(IR 2) (l'espace quotient IR2/S l) et respectivement IP 3 l ' e s p a c e projectif rdel (P(IR3)= IR3/S2 ) . Il n 'existe pas de descripteurs invariants par rapport aux projectives agissant de IP3 vers IP:. Nous trouvons, ndanmoins, des formulations de descripteurs invariants pour la varidtd plane de ce groupe ; c'est-a-dire pour d e s transformations projectives de IP2 vers IP2. Ces transformations projectives sont un <>groupe au sens topologique (i.e. P devient inversible). 11.3.2. I n v a r i a n t s a l g 6 b r i q u e s de 5 p o i n t s c o p l a n a i r e s

Une forme d'invariant se rdvdle souvent utile dans la vision. Elle agit sur une topologie de 5 points coplanaires ; c'est-h-dire par rapport h la varidtd plane des projectives [5]9, 19] :

(1)

I - det(M431)det(M521) det(M421)det(M532) 1 det(M531)det(M421) et 1 2 - det(M432)det(M52~)

ofa M i j k ; i c j c k est la matrice constitude en colonne par les coordonndes de Pi, Pj et Pk :

Mijk =

Yi

~

Yk

z, xJ zj 1

La famille d'invariants (I 1, 12) peut s'utiliser de manibre rdciproque par la propridtd suivante : PROPRII~Tt~- INVARIANCE Si la famille d'invariants (I1, 12) appliqude sur les projections P de 5 points de IR 3 reste inchangde lorsque les points sont mis en mouvement, alors, il existe une homographie H (similitude de IR 3) qui transforme les 5 points considdrds. D e plus, ils sont coplanaires dans [R 3. La mesure de comparaison des invariants doit possdder la propridtd fondamentale de stabilitd : PROPRII~TI~- STABILITI~ Cette propridtd introduit Ia notion de proximitd entre les descripteurs de f o r m e : la continuitd de l'espace des f o r m e s doit induire la continuitd de l'espace des invariants et rdciproquement. On s'approche de cette ddfinition en adoptant la mesure d=d2/(d2 + 1) oh d 2 est la distance euclidienne. Enfin, nous formulons la classification des points selon la nature du m o u v e m e n t 3D en appliquant localement (sur chaque groupe de 5 points) la propridt6 de d i s c r i m i n a t i o n suivante :

DI~FINITION - INVARIANTS DE CINQ POINTS COPLANA1RES

PROPRII~TI~- DISCRIMINATION

Soient 5 p o i n t s Pi = (Xi, Yi, Zi, 1)Tcoplanaires dans IR 3 et non colindaires trois p a r trois, la famille (11, I2) est invariante p a r rapport gt toute projective de IP 2 vers IP 2 :

Si d[l(.), I(H(.))] < e ; alors, les points considdrYs sont en mouvement rigide dans 1173;sinon, le mouvement tridimensionnel est de type dlastique ou alors les points ne sont pas coplanaires.

A N N . TI~LI~COMMUN., 5 5 ,

n~ 3-4, 2000

4/14

L. PEYRONNY

-- R E C O N S T R U C T I O N

3D ROBUSTE DU VISAGE : APPROCHE

Deux probl6mes pratiques persistent encore : - Permutation de points : la description invariante I e s t affect6e par toute permutation de ces 5 points et ces derniers doivent v6rifier l'hypoth~se de coplanarit6. En effet, il existe 5 ! = 120 permutations de 5 points possibles et donc 120 couples (I 1,/2) de descripteurs. Pratiquement, nous 6vitons cette probl6matique car nous avons appari6 les points dans la s6quence d'images. Nous poss6dons ainsi une et une seule correspondance possible par quintupl6s de points. - Coplanaritd des points : Afin de pouvoir comparer les invariants par groupe de 5 points, nous devons v6rifier l'hypothbse de coplanarit6. Les groupes de 5 points seront choisis dans des zones <~petites (cette famille est un descripteur local de la forme). Comme toute homographie pr6serve la topologie de l'espace projectif, la formulation pr6c6dente reste valable quelle que soit la transformation hom6omorphe H (d6placement de IR3). II.3.3. R6sultats, contraintes, limitations et perspectives de notre approche

Analyse complete et temps de calcul

Pour d6terminer tous les invariants des groupes de 5 points clans une image contenant P points, nous devons calculer O(P 5) invariants ; alors que seulement O(P) sont fonctionnellement ind6pendants. Une approche pr6sent6e dans [5] tente de r6duire ce coflt de calcul h l'ordre O(P) mais au d6triment de l'oubli potentiel de certains appariernents ; par exemple, lors d'une occultation. Limitation de la stabilit~ des descripteurs

Les simulations que nous avons r6alis6es montrent que, malgr6 l'utilisation de la mesure que nous avons propos6e, le couple de descripteurs I = (11, I2) est relativernent instable si l ' o n applique des variations sur les coordonn6es des points dans l'image de l'ordre du pixel lorsque l'objet est relativement petit (dimension d'une image HALF-CIF). Cette 6tude confirme les r6sultats obtenus par Coehlo [5]. Calculons la pr6cision ol=va~(ll) de ces deux formes alg6briques invariantes 1l;l=1,2 en fonction de la variation des coordonn6es des points Pi=(~Xi,~Yi,~zi)T : 5,~ r l ~I l \ 2

[

~I l \ 2

/

~I t \ 2

2

Cette propridtd de lindaritd entre la prdcision des invariants alg6briques de 5 points coplanaires et l'amplitude de leurs descripteurs nous am~nent naturellement h la r6flexion suivante : PROPRIt~TI~- ESTIMATION DES INVARIANTS ET BRUITS EXTRINSI~QUES DE PROJECTION t~tant donn~e l'estimation de la valeur des invariants, de l'erreur introduite p a r le capteur (camdra) et la

5/14

DUALE

<< M O U V E M E N T

-- STRUCTURE

~>

153

connaissance des ddviations introduites p a r les bruits d'appariement, nous pouvons calculer la valeur exacte des descripteurs invariants ; et inversement. Le probl~me de la contrainte de coplanarit~

Dans l'6tude qui vient d'etre prdsentde, nous avons utilis6 un couple de descripteurs invariants pour uue configuration de P = 5 points que nous calculons sur chaque image N = 1. Nous comparons ensuite les couples de descripteurs (I 1, 12) deux ~ deux sur les images successives dans la s6quence. Dans la pratique, la difficult6 h v6rifier l'hypothese de coplanarit6 tridimensionnelle des quintuplds de points, outre les probl6mes de stabilit6 que nous avons par ailleurs d6jh relatds, est la base de r6sultats peu concluants obtenus sur des s6quences monoculaires d'images r6elles. Nos interrogations se portent alors sur la recherche d'une topologie d'invariants permettant la formulation de descripteurs plus stables et n'imposant pas la contrainte de coplanarit6 tridimensionnelle. De mani6re sch6matique, les dtudes actuelles tentent de profiter de la redondance temporelle et spatiale de 1'inf o r m a t i o n dans les projections (images). Ainsi, le probl6me de l'invariance en vision par ordinateur trouve des solutions plus 616gantes d6s lors que l ' o n utilise plus de deux images et plus de cinq points. Le lecteur trouvera dans [1 l, 18, 27] quelques applications de ces m6thodologies.

III. C L O N A G E 2D---> 3D : DUALITI~ MOUVEMENT - STRUCTURE

Diff6rentes approches sont propos6es dans la litt6rature pour r6soudre la probl6matique de 1' estimation de la structure (profondeur) et des param~tres de mouvement d'un objet tridimensionnel solide dont seule l'6volution de ses projections au cours de la s6quence d'images est disponible. Parmi les diff6rentes approches rencontr6es, nous avons choisi 1' approche bas6e mouvement qui appara~t c o m m e fournissant le meilleur compromis robustesset e m p s de calcul - complexitd algorithmique. Ces approches sont couramment d6nomm6es << profondeur partir du m o u v e m e n t ~>. Ces derni~res font l ' h y p o th~se d ' u n m o u v e m e n t tridimensionnel rigide relatif entre l ' o b j e t surfacique et la cam6ra. Dans ce cadre, nous avons, d'une part, les formulations des syst~mes actifs de vision ofa c ' e s t la cam6ra qui est en mouvement, l'objet restant fixe, et, d'autre part, les m6thodologies agissant sur une cam6ra fixe mais avec un objet mobile dans l'espace. Nous distinguons deux approches compl6mentaires : - L'approche <>( M o u v e m e n t par la Structure) qui utilise la connaissance de la structure que l'on doit estimer afin de calculer le mouvement 3D ; A N N . TI~LI~COMMUN., 5 5 ,

n~3-4, 2000

154

L. PEYRONNY-- RECONSTRUCTION3D ROBUSTEDU VISAGE: APPROCHEDUALE<>

- L'approche < 3D pr6sent6 au paragraphe III.4.

III.1. C o n t r a i n t e s , n o t a t i o n s et p r i n c i p e s g 6 n 6 r a u x

Ce prEambule prEsente, le plus simplement possible, l'ensemble des contraintes que nous associons aux algorithmes. Nous pr6senterons 6galement les notations qui seront utilis6es dans la suite de notre travail. Enfin, l'Etude de la condition d'unicit6 de la solution de reconstruction de la structure et du m o u v e m e n t tridimensionnel fournira le principe de base sur lequel seront construites hog solutions. III.l.1. Sensibilit6 relative des algorithmes face aux bruits

D a n s l e s cas pratiques, les erreurs principalement gEn6rEes par le syst6me d'acquisition causent des divergences dang l'estimation des param~tres du mouvement et de la structure. MalgrE quelques rEsultats empiriques illustrEs dans la litt6rature [25, 11], il n'existe, 5 notre connaissance, aucune demarche coh6rente fournissant un cadre math6matique strict de l'6tude de cette influence. Nous avons pu toutefois identifier cinq sources gEnEratrices de bruits agissant de mani6re conjuguEe sur la qualitE de la reconstruction tridimensionnelle : - e r r e u r d ' a p p a r i e m e n t : l o r s q u ' u n Echange ou un mauvais appariement s'effectue localement (zone de l ' i m a g e faiblement texturEe), - m a u v a i s e classification des p o i n t s 2 D : les conditions de fonctionnement des algorithmes de reconstruction ne sont alors pas satisfaites, - bruit optique : la physique des syst~mes d'acquisition n'est pas parfaite et introduit un flou optique et des distorsions radiales et tangentielles, - b r u i t p r o j e c t i f : lorsque l ' o b j e t s'61oigne de la camera, le module orthographique (adoptE dans notre approche) modifie de mani6re importante les coordonnEes des points sur l'image, - anisotropie de la grille cartdsienne : l'image fournit des coordonnEes discr~tes des points suivis. Pour les algorithmes de type linEaire, on peut rEaliser une analyse numErique de l'erreur au premier ordre simultanEment avec l'estimation du m o u v e m e n t [25]. Nous obtenons ainsi, non seulement les param6tres de structure et de mouvement, mais aussi une estimation de l'erreur qu'ils contiennent. Les r6sultats de l'estimation ANN. TI~LI~COMMUN.,55, n ~ 3-4, 2000

du mouvement et de la structure seront alors acceptEs, si et seulement si, l'erreur qui leur est associEe, et qui vient d'etre calculEe, est relativement faible. Cependant cette approche devient rapidement tr6s difficile h maitriser et mettre en oeuvre lorsque les algorithmes sont fondEs sur une approche non linEaire. Dans la litt6rature, deux types d'approche tentent d'apporter des rEponses au paradoxe density d ' a p p a r i e m e n t s / quality de reconstruction. La premiOre de ces approches consiste en la minimisation au sens des moindres carrYs d' un certain critbre off les effets des bruits sont amoindris en utilisant le plus de donnEes possibles. Les algorithmes de type RANSACeffectuent la demarche inverse : moins de donnYes mais de la meilleure qualitY possible p o u r rdaliser la reconstruction. Donnons un exemple de son fonctionnement. Cet algorithme tire au hasard un sous-ensemble de points h rnettre en correspondance. Le meilleur 6chantillon (au sens de la mesure choisie) est conserve pour la reconstruction [8]. III.1.2. Muitiplicit6 et d6g6n6rescence des solutions

Dang leg probl~mes de d6termination de la structure/mouvement, il existe un intEr~t, tant pratique que thEorique, de savoir dang quelle mesure le n o m b r e de solutions depend du n o m b r e de correspondances entre les primitives. Soit done P l e nombre d'appariements et m(P) le nombre de solutions. Alors, pour un probl~me particulier, il existe un nombre critique d'appariements P0 tel que pour P < P 0 ; m(P)=oo(ind6nombrable). De la m~me mani~re, si l'on consid~re P0 appariements, alors nous obtenons m ( P o) =m o solutions possibles et finies notre probl~me. Enfin, en prenant plus d'appariements (i.e. P > Po) nous obtenons m ( P ) = l solution (unicitE). L'Etude du cas particulier P = Po est tr~s intEressant. En effet, il dEfinit la contrainte de limite infYrieure du nombre d ' a p p a r i e ments nYcessaires & la reconstruction tridimensionnelle. Les deux questions importantes que soul~ve cette contrainte sont : - conditions d'unicitd de la solution : pour P > P0, quelles sont les conditions nEcessaires et suffisantes sur les primitives et le m o u v e m e n t telles que 1 < re(P) < 0%

- oo - dYgYndrescence des solutions : pour P > P0, quelles sont les conditions nEcessaires et suffisantes telles que m ( P ) = ~o. Ces questions sont intimement liEes h la sensibilit6 des algorithmes face aux bruits d'appariements amenant des formulations real conditionn6es. Malheureusement, les rEponses sont loin d'etre compl6tes. Les connaissances actuelles sur ce d o m a i n e sont synthEtisEes au tableau I. 111.1.3. Condition d'unicit6 de la solution

Dans ce paragraphe nous nous intEressons ~ Etablir les contraintes minimales ndcessaires b la ddtermination unique d ' u n e solution de reconstruction tridimensionnelle p a r le mouvement. 6/14

155

L. PEYRONNY -- RECONSTRUCTION 3D ROBUSTE DU VISAGE : APPROCHE DUALE <
Unicity and multiplicity conditions for 3D reconstruction

type

appariements primitives

m(Po)

Po

non-unicit6

-d6gdn6rescence

points

colin6aires

colin6aires

droites

parallflisme

parall61isme

3D--+3D

points

<_4

essentiellement colin6aires

droites

<_8

quelques conditions de parall61isme

points

<10

2D---~3D

points 3D sur une surface particuli6re

2D---)2D

? (r6sultats partiels)

droites

Nous consid6rons donc P points P/k= (X/k, y/k, Z/k)T appari6s pour les N images (k= 1,2 .... N) de la s6quence et mis en m o u v e m e n t rigide par Faction des d6placements de IR3. Notons X k, Y~ et Z~ 0 (3)

V i = I ..... P;

Xk- X~

V k = l ..... N; Xk=

i

i

1

k k XKp-X1

0

0

l ] [ 1 i

et

Zk=

zkz

,

i--! 1

z~-zlk

La conservation du produit scalaire entre les instants k - l et k s'6crit alors :

x~ xkr+ Vk YkT+Z~ZkT =Xk-I

Xk-lT+

Yk-1 rk-lT + Zk-1 Zk-1 T

En manipulant l'6quation pr6c6dente, regroupant les termes connus et inconnus, nous obtenons :

Le problbme n'admet donc pas de solution unique, m6me avec un nombre de points quelconque / Nous avons donc montr6 l'impossibilit6 de rdsoudre le problbme du clonage 2D ~ 3D lorsque le mod61e de projection est un mod61e orthographique et que nous ne disposons que de N = 2 images de la marne sc6ne en mouvement. Cette d 6 m o n s t r a t i o n peut atre g6n6ralis6e aux autres mod61es de p r o j e c t i o n s (i.e. perspective, para p e r s p e c t i f .... ). D e plus, le n o m b r e de points P doit ~tre sup6rieur ou 6gal ~ 4 afin que la matrice C~_1, k, poss~de ( P - 2 = 2 ) v e c t e u r s p r o p r e s U 1 tels que U Iz kT = O. Ces derni6res remarques nous permettent de formuler le crit6re d'unicit6 des estimations de structure et de m o u v e m e n t dans le cas d ' u n syst6me monoculaire non calibr6 : PRINCIPE - C O N D I T I O N D'UNICITI~ DE LA S O L U T I O N

II f a u t au moins 3 images et 4 points a p p a r i ( s pour obtenir l'information tridimensionnelle de mouvement et de structure d ' u n e sc~ne en m o u v e m e n t rigide.

(4) Ck_l,l=XkXk T - Xk_ 1Xk_l T +Irk YkT--Yk-1 Yk-1T

=Zk_ 1Zk_lT--Zk Zk T. Dans un premier temps, consid6rons le cas de N = 2 images. L a matrice C1, 2 peut &re diagonalis6e sous la forme diag0~l,)~2,0 ..... 0) off ~,1,)~2~0 sont les valeurs propres associ6es aux vecteurs propres U 1 et U 2 ; c'est-~dire C1,2U 1= )~IUI et C1,2U2= ~,2U2. De plus, il est ais6 de remarquer que l'une sera positive et l'autre n6gative. Enfin, en imposant les contraintes

Cl,2=U2U2T--uIU1T.

[fll@lkl[ et IU2I=~/IL2[, nous 6crivons Ces derni6res 6quations montrent que Z I = U 1et Z2-- U 2 sont des solutions admissibles de notre probl6me. Pour toute valeur d ' u n certain param6tre O, les solutions suivantes sont 6galement admissibles : 1

Z 1 - cos(e) Ua+tan(O)U 1 et Z2= co (0) U2+tan(O)U2 7/14

111.2. A p p r o c h e <
P a r la S t r u c t u r e >>

Le principe de 1' algorithme Mouvement Par la Structure (MPS) est de retrouver le mouvement 3D de l'objet rigide apr&s avoir estim~ sa profondeur it partir de ses projections sur le plan image : PROBLI~MATIQUE - R E C O N S T R U C T I O N 3D DE LA S T R U C T U R E (MPS)

l~tant donngs P points apparids de l'objet et 3 images, ddterminons la structure Z 1 (profondeur it l'instant 1), ainsi que la profondeur instantande Z k. Deux estimations successives de Z k dgterminent les paramOtres de mouvement (rotation). ANN. TI~Lt~COMMUN.,55, n ~ 3-4, 2000

156

L. PEYRONNY

-- R E C O N S T R U C T I O N

3D ROBUSTE DU VISAGE " APPROCHE

'"

111.2.1. Principe de fonctionnement

Vk>l; Ck=X1X1T-xkxkT+Y1Y1T-YkYk

T

La construction de cette matrice introduit certaines propri6tds qui seront exploit6es dans l'estimation de la profondeur h l'image 1 not6e Z I (structure de l'objet). La matrice C k 6tant sym6trique : ses vecteurs propres, not6s Uk,l, sont orthogonaux entre eux. L'expression (5) permet de calculer une matrice dont le rang est 4. Cependant, en regardant l'6quation (4) nous avons rang(Ck)=2. I1 existe alors P - 2 vecteurs propres Ukt tels que CkUkl=O. Si un vecteur Uk,, appartient au noyau'de C k alors UkfrZl=O. Dans le cas oiJ les donndes (coordonn6es des points) sont bruit6es, il s'agit de trouver les P - 2 vecteurs U~,~ satisfaisant au mieux la relation U~,[Tz1 = 0 Nous proposons de retrouver la structure au sens des moindres carr6s sous la contrainte z~ =Z~/IZ~I. Les propri6tds de la matrice structure-mouvement permettent de calculer cette derni6re ~ l'instant k (not6 -~(k)) en minimisant la fonctionnelle suivante : kP-2

(6)

~ , Z (Ui, ITZl)2=ZlBkZl T i=1/=

1

avec B~ la matrice sym6trique (P - 2) x(P - 2) suivante :

<~ M O U V E M E N T

-- S T R U C T U R E ~>

>

1 instant k _ 3 , la structure gl (k) alors obtenue est :

Toute composition de similitudes 6tant une similitude, nous pouvons alors f o r m u l e r l'expression vectorielle de la conservation du produit scalaire entre les instants 1 et k (cf 6quation (4)). Nous ddfinissons ainsi la matrice Ck=CI, k de taille P x P d d n o m m d e ~< matrice structure-mouvement >>: (5)

DUALE

carr6e

de

%1(k) = V~,n= arg min V~kV,. T. V~

~.~ A

~

I11.2.2. A l g o r i t h m e d e r e c o n s t r u c t i o n

L'algorithme que nous proposons permet de retrouver la structure g(k) de mani6re robuste et d ' e n d6duire la profondeur et le mouvement qui l'anime a l'image courante (k). III.2.3. Crit~re d'arr~t de l'algorithme MPS

Chaque it6ration de l ' a l g o r i t h m e devrait th6oriquement minimiser l'effet des bruits issus des variations de position des points appari6s. I1 nous parait judicieux de formuler un crit6re permettant de cesser la partie estimatrice de la structure de l'algorithme MPS afin de ne pas surcharger le temps de calcul de l'algorithme (dtape 3). CRITERE - ARRt~T DE L ' A L G O R I T H M E MPS

L'algorithme MPS s'arrOte, si la fonctionnelle suivante est respectde, notons s > k + 3 la taille de la fen~tre d' observation et ~ une petite valeur arbitrairement fixge ." median LJ1 l=k-s

#1

(l - 1). z I (l )[] < E.

La structure obtenue & cet instant (-#1(k)) est dite ~ optimale au sens clu critkre choisi ~. Elle est alors conserv~e pour les images suivantes.

taille

kP--2

Bk:Z

2 (Ui, lUi, lT)"

i=ll = 1

Soit V~AV~ T la d6composition en vecteurs propres de la matrice B k. La fonctionnelle de l'6quation (6) est minimis6e si l ' o n prend le vecteur propre V~m,~ associ6 la plus petite valeur propre ~min ~ diag(A) de B k.

III.3. A p p r o c h e ~ S t r u c t u r e p a r le M o u v e m e n t >> (SPM)

Le principe de l'algorithme Structure Par le Mouvement r6alise le contraire de l'approche Mouvement par

ALGORITHME I. - - Reconstruction <~Mouvement par la Structure

>>

~ Motion from Structure ,~ reconstuction principle

l~tape 1 estimation de la structure

l~,tape2

,~ l'image courante k, nous utilisons la formule (5) pour calculer la matrice C k. La ddcomposition en vecteur propres de C~ nous fournit les P - 2 vecteurs propres Ukd v6rifiant la propridt6 CkUk,l=O. La structure gl (~) est le vecteur propre de la matrice B k de plus petite valeur propre. La profondeur

ffStape 3 crit6re d'arr~t de l'algorithme

Fftape 4 calcul des param6tres de mouvement

ANN. TI~LI~COMMUN.,55, n ~ 3-4, 2000

-~k(k) de l'objet ~ l'instant k est obtenue grace ~ (5) par : X, xIT XkXkm y, r T

estimation de la profondeur instantanEe

La convergence de l'algorithme MPS 6tant assur6e par son fonctionnement

YkYkT

1Wtape2, nous proposons d'Etablir un critbre d'arrdt de

(cf w m.2.3). Nous pouvons ~ pr6sent calculer la matrice de passage R k entre l'instant k - 1 et l'instant k pr6c6demment calcul6 h l'(tape 2.

[xb'l

[x l

vi= L..p,./~/+'/=R, / ~/. LZ~+'J Lz~J 8/14

L. PEYRONNY-- RECONSTRUCTION 3D ROBUSTE DU VISAGE " APPROCHE DUALE <~ la Structure ; c'est-?~-dire, il s'agit de retrouver la profondeur de l'objet gt partir de l'estimation des parambtres de mouvement tridimensionnel d'un objet rigide g~partir de ses projections orthographiques sur un plan image. Le problrme que nous devons traiter est dual de celui prrsent6 au w 2II.2 et s'rnonce de la manirre suivante :

111.3.1. Principe de fonctionnement

Nous analyserons le mouvement tridimensionnel ~t partir de l'observation des trajectoires de points sur trois images successives, c'est h dire les projections des mouvements; respectivement not6s TR=P(R), Ts=P(S), et Tw=P(W)=P(S(R)) aux images k - 2 , k - 1 et k. Les notations employ6es sont r6sum6es sur le diagramme suivant : W

I

> Pk- 1

-

-

S

>

I

P

(r23, r13, r31, r32)=~(P23 , P13, 1331, 1332),

(w23, w13, w31, w32) :'~(0)23 , 0013, (-031, (-032).

IEtant donnds P points apparids de l'objet et 3 images, dgterminons les matrices de rotations R = [rift, S= [sif t et W= [wij],correspondant respectivement au mouvement entre les instants k - 2 ---)k - 2, k - 1 ~ k et k - 2 ---)k. Nous avons alors W = S R .

R

Nous pouvons conna~tre quatre des six parambtres des matrices de rotations R, S e t W au sens des moindres carrds et sous contrainte de norme unitaire (cf dtape 1 de l'algorithme II) :

($23, s13, $31, $32)=~($23 , s13, $31, $32),

PROBLt~MATIQUE - RECONSTRUCTION 3D PAR LE MOUVEMENT (SPM)

Pk- 2 - -

157

Pk

I

P

P

III.3.2. Algorithme de reconstruction

Par souci de grn6ralisation, nous noterons selon le contexte ~ = [q)ij] soit la matrice R, S ou W. Le lecteur pourra avantageusement se rrfrrer ~ [11] pour plus de drtails sur les calculs. Nous proposons alors, l'algorithme de reconstruction prrsent6 ici. III.3.3. Estimation robuste de la matrice de mouvement instantan4

L'algorithme SPM estime, ~ chaque instant k, trois matrices de rotation Rk, S k et W k qui correspondent respectivement au mouvement entre les instants k - 2 ~ k 1, k - 1 b t k e t k - 2 ~ t k . Remarquons, alors, qu'~ l ' i m a g e k + 1 l'estimation Sk+ 1 est en fait la matrice de rotation R k estim6e l'image pr6c6dente (k). De mani6re h r6duire le biais de chacun de ces estimateurs, notons F k la matrice de rotation agissant sur les points entre les images k - 2 et k - 1 : Fk_ Sk+l +Rk 2

~w

m

Pour tout point pk_ i - - -(Xki' ~ i' zk~ i- T"' Vi = 1.... P;3 <-k < N, nous 6crivons les transformations suivantes :

(7-a)

(7-b) (7-c)

Ix/k-1 ] = [r12 r12 ] [szk-2 ] zk-2 L y~/-lJ Lr21 r22J [yk/-2 +[r13 r23] i ,

Ixk]=[s12sl2][xki-1]+[s13$23]Z k-a yk/

[s21 s:2J [ yk/-1 -1

,

]

L ~#J-- LW21W22J L yk#-i j-F[Wl3

'

W23] Z/k-1

.

Orfice aux identitrs trigonomrtriques de la matrice de rotation, les 6quations (7-a), (7-b) et (7-c) se r66crivent respectivement sous la forme suivante : [r23 r13 r32

r31][Xk-2--Yk-2Xk-1 -Yk-1] =[r23 r13 r32 r31]AR=0, (8-a)

[$23 S13 $32 S3ll[Xk -YI~ Xk-1 - Y ~ - l l =[$23 S13 $32 S31]As=0, (8-b) [w23 w13 w32 w31][Xk-2 - Y k - 2 X~ -Y~] =[W23 W13 W32 w31]Aw=0. 9/14

(8-c)

III.4. C o l l a b o r a t i o n des a l g o r i t h m e s SPM et MPS De mani~re g r n r r a l e , les deux algorithmes que nous avons pr6sent6 aux p a r a g r a p h e s 211.2 et 111.3 effectuent pour leur partie estimatrice la rrsolution au sens des moindres carrrs d ' u n s y s t r m e surdrtermin6 d ' r q u a t i o n s . L ' a l g o r i t h m e MPS p r o p o s e de rrsoudre de m a n i r r e itrrative la structure 2~k) (cf drape 1 de l ' a l g o r i t h m e I) tandis que l ' a l g o r i t h m e SPM fournit une estimation robuste du m o u v e m e n t instantan6 F~ (cf. dtape 1 ~ 5 de l ' a l g o r i t h m e II et paragraphe 111.3.3). Grfice ~ deux estimations obtenues ~t des instants successifs, ils calculent la transformation ainsi o p r r r e en r r a l i s a n t une inversion matricielle. Nous rappelons 5 la figure 4 a u - d e s s o u s les principaux calculs et estimations r6alis6s par cette dualit6 algorithmique <>: Nous pouvons <?a la partie estimatrice des algorithmes au sens du critrre des moindres carr6s, que nous avons employ6e pour rrsoudre les syst~mes linraires sous-jacents. L'algorithme combin6 que nous proposons tire les avantages individuels du calcul de la structure et du ANN. TI~Lt~COMMUN.,55, n ~ 3-4, 2000

L. PEYRONNY -- RECONSTRUCTION 3D ROBUSTE DU VISAGE : APPROCHE DUALE <>

158

ALGOR1THME II. - - Reconstruction <>

<
F,tape 1 estimation homog~ne des param6lres q0j

Soit vA, le ie vecteur propre deA,, une solution des 6quations (8) sous la contrainte ']r = 1 s'dcrit :

[%3 %3

II(P23 il ,I(P13 ]j II%2 ,'1 ,'i%1 II

x ~ . i=l

,~ l'aide de la composition de mouvement, nous pouvons calculer les rapports de facteurs d'6chelle c(/y et ~/y :

Fftape 2 calcul des rapports de facteurs d'dchelle

O~ (Y230)13--O130)23 et J3 P320331--P31(t)32 Y

(~31P13- 032023

Y

032913-031023

[F33] ---~(~31p13-~32~23)~(0"132+0"232) 1-,ro)1~,3+~,~;~2[.

t~tape 3 d6termination unique de r33 et S33

Les deux triplets de solutions (%,l]o,Y0) et ( - % , - ~I0,-Yo) sont envisageables pour (oq~,y), avec :

f;tape 4 estimation des facteurs d'6chelle ~, [5 et y

/

1+r3~2

_ /

1+s332

O~0=u P132+P232, p0-- /G132+(~232

Y Y et y0=%~-=13013 -.

Nous calculons pour les 2 triplets de solutions (%,~0,Yo) et (-O~o,-[3o,-Y0) (cf dtape 4) les param6tres ((pZ3,(P13,(P31,(P32) grgce aux 6quations (7). Les param~tres restant ((PlI,(DlZ,(P21et (P22) sont calcul6s par :

t~tape 5 estimation compl6te du mouvement

(Pl ']__ [(P31 (P32]- 1I-- q)33(P13] et F(P21] _ [ -- (P31 -- q132]- 11(P33(P23] q)12J--[q)32 --g)31J [ --q023 J [qO22J--[--q032 qO31J [ (P13 J" Les 6quations (7-a) et (7-b) sont utilisdes pour calculer le vecteurs de profondeur Zk_ 2 et Zk_ 1 :

F,tape 6 calcul de la profondeur

-Slzy -rl2y et Zk_ l ._ 1 . X - S. u x . Zk ~=I~x, -rllX -z rl 3 ~-1 rl 3 k 2 rl 3 k-2 Sl 3 k Sl 3 k-1 Sl 3 k 1"

m o u v e m e n t r e s p e c t i v e m e n t p a r l e s a l g o r i t h m e s M P S et S P M e n c a l c u l a n t , ta c h a q u e i n s t a n t , le m o u v e m e n t c o r n b i n 6 F l , k d e l ' o b j e t d e l ' i m a g e 1 ti k p a r : k Fl,k = l ~ FI "

FIG. 4 . -

A i n s i , l o r s q u e le c r i t ~ r e q u e n o u s a v o n s p r 6 c 6 d e m m e n t formul6 est satisfait, les calculs du mouvement et de la s t r u c t u r e r e s p e c t i v e m e n t p a r les a l g o r i t h m e s NIPS e t S P M s o n t arrSt6s. C e t a r t e f a c t a l g o r i t h m i q u e a p o u r c o n s 6 q u e n c e d e d i m i n u e r le t e m p s d e c a l c u l g l o b a l c a r la s t r u c t u r e n ' e s t alors plus estim6e. Le d6bit moyen est de 3 images par

Dualit6 S t r u c t u r e - M o u v e m e n t

Duality between stucture and motion ANN. TI~LI~COMMUN.,55, n ~ 3-4, 2000

10/14

L. P E Y R O N N Y

-- RECONSTRUCTION

3D ROBUSTE DU VISAGE : APPROCHE

ALGORITHMEIII.

-

-

D U A L E << M O U V E M E N T

-- STRUCTURE

159

))

Algorithme de reconstruction ~ combine >~

Proposed ,~ structure and motion ~ algorithme principle

FIG. 5.

-

-

Reconstruction de l'objet ~ ken71 ~>(non bruitd)

Reconstructed ~ ken71 ~ 3D object (no noise)

seconde avant que le critEre d'arrat MPS ne soit satisfait puis de environ 5 ?a7 images par seconde pour les suivantes.

IV. Q U E L Q U E S R I ~ S U L T A T S

Les c o u r b e s figure 5-c reprEsentent l ' E v o l u t i o n de l'erreur que nous avons choisie. R e m a r q u o n s que, dans le cas off t o u t e s l e s c o n t r a i n t e s d e s a l g o r i t h m e s de r e c o n s t r u c t i o n s o n t s a t i s f a i t e s , nous obtenons u n e erreur nulle des la 3 e image. E n fixant une fen&re d ' o b s e r v a t i o n de taille s = 10 p o u r le critEre d ' a r r ~ t de l ' a l g o r i t h m e MPS, nous utilisons le calcul de la matrice de rotation F k f o u m i e par l ' a l g o r i t h m e SPM ~t partir de la 13 e image.

Comportement g6n6ral et convergence des algorithmes Nous pr6sentons ~t la figure 5 le comportement de l'algorithme de reconstruction sur une sequence de N = 100 i m a g e s d ' u n objet synthEtique h P = 7 1 points <~mis en m o u v e m e n t rigide dans IR 3. La distance de Hausdorff ayant les caractEristiques de temps de calcul que nous lui connaissons, nous avons prEfdr6 dEfinir la mesure d ' e r r e u r suivante fondEe sur le produit scalaire : e=ll-zv~ll

off z 1 est la p r o f o n d e u r th6orique normalis6e ~ l ' i m a g e 1 et z 1 la p r o f o n d e u r reconstmite.

11/14

FIG. 6. - - Reconstruction ~ la 100e image par 1'algorithme combine R e c o n s t r u c t e d ~, ken71 ~ 3 D object at image # 1 0 0

A N N . TI~Lt~COMMUN., 5 5 ,

n~ 3-4, 2000

160

L. PEYRONNY -- RECONSTRUCTION3D ROBUSTEDU VISAGE : APPROCHEDUALE <~

Reconstruction de l'objet ~
F i e . 7. - -

Reconstructed ~ ken71 ~ 3D object (synthetic noise)

FIG. 8.

-

-

Caractdrisation du bruit apport6 ~tla s6quence de la figure 7 Synthetic noise added to Figure 7 images sequence

Robustesse

de l'algorithme

face aux bruits

La figure 7 illustre les rdsultats obtenus sur la structure l ' o b j e t ~, mis en m o u v e m e n t rigide lorsque les donndes sont bruit6es. A f i n d ' i l l u s t r e r la robustesse des algorithmes de c l o n a g e 2D--~ 3D, nous avons ajout4 artificiellement h la s4quence originale utilis4e pour produire les r4sultats de la figure 5 un bruit al6atoire sur les coordonn4es des points. L ' a m p l i t u d e des d6viations des coordonndes des points est de l ' o r d r e de 10 % de la taille de l'objet. La solution p o u r la structure fournie par la m4thode c o m b i n 6 e est o b t e n u e ~t l ' i m a g e n ~ 26. N o u s avons pu c e p e n d a n t observ6 que la c o n v e r g e n c e de l ' a l g o r i t h m e MPS est t h 4 o r i q u e m e n t assur4e l o r s q u e le n o m b r e d ' i m a g e s o b s e r v d e s et le n o m b r e de p o i n t s d o n t la variance du bruit est faible augmentent. N o u s p o u v o n s d~s h p r d s e n t 6 v a l u e r les l i m i t e s de notre a p p r o c h e en r e m a r q u a n t d ' u n e part que route translation selon l ' a x e d e s z ne p o u r r a atre retrouv4e et, d ' a u t r e part, que l ' o b j e t reconstruit sera de taille normaliANN.TELECOMMUN.,55, n~ 3-4, 2000

s6e h 1. Ce n ' e s t pas ganant puisque, dans le contexte de la r6alit6 virtuelle, c ' e s t l ' u t i l i s a t e u r (d4codeur) qui choisit son point de vue. D e plus, nous supposons possdder P points visibles tout au long des N i m a g e s pour faire fonctionner les algorithmes de reconstruction. D e plus, des d y s f o n c t i o n n e m e n t s de l ' a l g o r i t h m e SPM p e u v e n t 6 g a l e m e n t a p p a r a l t r e lors de r o t a t i o n s pures autour de l ' a x e des z. En effet, dans ce cas la matrice prdsentde l'6tape 3 de l ' a l g o r i t h m e SPM n ' e s t pas diagonalisable. Enfin, et de mani6re p l u s p r a g m a t i q u e , nous p o u v o n s observer au cours de la s6quence que certains points peuvent apparaitre et dispara~tre.

V. C O N C L U S I O N

Nous avons pr4sent6 un syst6me original de reconstruction tridimensionnelle p o u r la mod41isation et l'anim a t i o n du v i s a g e dans une s d q u e n c e v i s i o p h o n i q u e . 12/14

L. PEYRONNY -- RECONSTRUCTION 3D ROBUSTE DU VISAGE : APPROCHE DUALE <>

161

FIG. 9. - - Schdma de clonage 2D --9 3D

2D--9 3D reconstruction coding schema

Notre stratrgie globale du clonage 2D--4 3D est illustrre ~t la figure 9. Les prrtraitements comprenant entre autres un processus de classification des points suivis en utilisant une famille d'invariants projectifs locaux ont fourni de bons rrsultats. Nos 6tudes actuelles se portent sur la formulation d'invariants algObriques projectifs qui, d'une part, ne sont pas soumis ~ la contrainte de coplanaritr, et d'autre part, 6tablissent de meilleures proprirtrs quant ~ la discrimination et ~ la stabilit6 [17, 18, 27]. Par exemple, pour une configuration de P = 6 clans IP3, il existe trois invariants projectifs sous l'action du groupe linraire GL(3) dans 1173. I1 est connu que ces invariants ne peuvent &re drterminrs sur une seule image pour ensuite ~tre comparrs deux ~t deux comme nous l'avons fait dans le cas d'une configuration invariante de cinq points coplanaires [17]. La grndralisation de cette drmarche ~ N = 4 images permet de trouver un invariant unique pour une configuration quelconque de P -- 6 points. La combinaison des deux algorithmes complrmentaires a abouti ~t une reconstruction robuste de la structure et du mouvement 3D m~me si le bruit est relativement fort. En effet, le crit~re lindaire de minimisation tol~re jusqu'g environ 10 % de bruit en moyenne. L'ensemble des pr&raitements sur les images de la s6quence doit donc &re le plus robuste possible. Nous nous int6ressons 6galement ~t la g6n6ralisation de cette m6thodologie pour des modMes de cam& ras non ou faiblement calibr6s et plus complets (i.e. para perspectif, perspectif-faible, affine). L' application de la m6thodologie employ6e trouvera 6galement une application dans le domaine de la calibration de syst~me d'acquisition st6rEovision. Les techniques que nous avons d6veloppdes ouvrent des fonctionnalit~s multim6dia h la visiophonie classique et la communication de groupe; notamment avec l'av6nement de la norme MPEG 4 et plus particuli~rement des travaux du groupe synthetic natural hybrid coding (SNHC) [15, 21]. -

13/14

-

D'autres perspectives d'application de nos m6thodologies sont 6galement envisag6es en mdtrologie, en robotique et en analyse du mouvement.

Remerciements Les auteurs tiennent ?t remercier GYrard EUDE (France Telecom R&D/DSRD) p o u r le soutien a p p o r t ( gt ce travail p a r le f i n a n c e m e n t de la CT1 n ~ 3 G N 6 9 5 intitul~e ~ Outils multim(dia de navigation de scbne 3D ~. Un remerciement particulier est a d r e s s ( ?t Thierry BLU, Thierry CHONAVEL et Olivier AVARO p o u r leur aide p r ( c i e u s e et leurs discussions toujours fructueuses. Manuscrit r e f u le 3 d ( c e m b r e 1999 accept6 le 24 j a n v i e r 2000

BIBLIOGRAPHIE

[11

[2]

[3]

[4]

[5]

BERG (M.), KREVELD (A.), OVERMARS (M.), SCHWARTZKOPF(0.), Computational Geometry, Algorithms and applications, Springer, 1997. BEYMER(D.-J.), Face recognition under varying pose, Massachusetts Institute of Artificial Intelligence, Technical Report n ~ 1461, December 1993. BICHSEL(M.) Human face recognition : From views to models from models to views, International Workshop on Automatic Face and Gesture Recognition, Zurich (Suisse), 1995. BOURGES-SI~VENIER(M.), HORAIN (P.), PRI~TEUX (E), LERAY (P.), Recalage d'un modOle grnOrique sur une srquence d'images 2D, Actes 36mes Journres COmpression et REprrsentation des Signaux Audiovisuels (CORESA'97), Issy-les-Moulineaux, pp. 163-171, mars 1997. COELHO(C.), HEELER (A.), MUNDY (J.-L.), FORSYTH (D.), ZlSSERMAN (A.), An experimental evaluation of projective invariants, in << Geometric invariance in computer vision ,> Chapter 4, ANN. TELI~COMMUN.,55, n ~ 3-4, 2000

162 [6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

L. PEYRONNY -- RECONSTRUCTION 3D ROBUSTE DU VISAGE : APPROCHE DUALE ~ J. L. Mundy and A., Zisserman eds., MITPress, pp. 87-104, 1992. DAVOINE(E), Compression d'images par fractales basde sur la triangulation de Delaunay, Thrse de Doctorat de l'Institut National Polytechnique de Grenoble, d6cembre 1995. ESSA (I.-A.), DARELL (T.), PENTLAND (A.), Tracking facial motion, IEEE Workshop Motion of Nonrigid and Articulated Objects, 1994. FISCHLER(M.), BOLLES (R.C.), Random sample consensus : a paradigm for model fitting with applications to image analysis and automated cartography, Comun. ACM, 24, n ~ 1, pp. 33-44, june 1981. FORSYTH(D.), MUNDY (J.L.), ZISSERMAN(A.), COELHO (C.) et al., lnvariant descriptors for 3-D object recognition and pose, Pattern Analysis and Machine Intelligence (PAMI), 13. n ~ 10, pp. 971989, October 1991. GALAN FERRAGUT (I.), Ddtection et suivi du visage et de points dans des sdquences d'images, MastOre IIA, ENST de Bretagne Ddpartement ITI, septembre 1998. HUANG (T.S.), LEE (C.H.), Motion and structure from orthographic projections, IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), 11, n ~ 5, pp. 536-540, 1989, HOFFMAN(D.D.), BENNET (B.M.), Computation of structure from fixed axis motion: rigid structure, Biological Cybernetics, 54, pp. 71-83, 1986. LIu (Y.), HUANG (T.S.), Estimation of rigid body motion using straight line correspondences, further results, Proc. of 8th International Conference on Pattern Recognition (ICPR), pp. 306307, Paris (France), octobre 1986. MURPHY (M.), SmNKA (S.), A study of data structures for orthogonal range and nearest neighbour queries in high dimensional spaces, Master Thesis, Dept. of Computer Science - State University of New York, 1996 PEYRONNY (L.), SOLIGON (O.), ROUX (C.), BLU (T.), AVARO(O.), HOW to construct an MPEG-4/ SNHC API : a videoeonference application example, Proc, IEEE Image and Multi-Dimensional Signal Processing (IMDSP'98), Alpach (Autriche), july 1998. PRI~TEUX(F,), MALCIU (M.), Model-based head tracking and 3D pose estimation, Proceedings SP1E Conference on Mathematical Modelling and Estimation Techniques in Computer Vision, pp. 94-110, San Diego, July 1998.

ANN. TE,LI~COMMUN.,55, n ~ 3-4, 2000

[171 QUAN (L.), Invariants of 6 points from 3 uncalibrated images, Proc. of 3rd European Conference on Computer Vision (ECCV), vol. II, pp. 459-470, Springer Verlag. Stockholm, May 1994. [181 QUAN (L.), Invariant of six points a projective reconstruction from three uncalibrated images, IEEE Trans. Pattern Analysis and Machine Intelligence (PAM1), 17, n ~ 1, pp.34-36, January 1995. [191 REINDERS (M.-J.-T.), Model adaptation for image coding, PhD thesis Cambridge University, 1986. [201 MUNDY (J.), ZISSERMANN(A.), Geometric invariance in computer vision, J.-L. Mundy and A. Zisserman eds., The MIT Press, 1992. [21] SOLIGON (O.), Moddlisation et animation du buste humain pour la compression de sdquence d'images visiophoniques, Th~se de l'Universit6 de Rennes I, mai 1998. [221 SOLIGON (O.), LE MflHAUTI~(A.), ROUX (C.), Toward 3D model based video coding, Ann. Tdldcommunie. 53, n ~ 5-6, pp. 229241, 1998. [23] SOLIGON (O.), LE MI~HAUTt~ (A.), R o u x (C.), Modrlisation et reprrsentation du visage humain et de ses expressions, Reconnaissance de Formes et Intelligence Articielle (RFIA'98), vol. 1, pp. 199-207, janvier 1998. [24] TSA! (R.Y.), HUANG (T.S.), Uniqueness and estimation of 3D motion parameters of rigid bodies with curved surfaces, IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), 6, pp. 13-27, 1984. [251 VII~VILLE (T.), LUONG (Q.T.), Motion of points and lines in the uncalibrated case, Rapport de Recherche RR-2054, INRIA Sophia-Antipolis (France), 1993. [26] WENG (J.), AHUJA (N.), HUANG (T.), Matching two perspective views, IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), 14, n ~ 8, 1992. [27] YAN (X.), JIA-XIONG (R), MING-YUE (D.), DONG-HuI (X.), The unique solution of projective invariants of six points from four uncalibrated images, Pattern Recognition, 30, n ~ 3, pp. 513-517, 1997. [28] YENANS (B.L.), HUANG (T.S.), Determining 3-D motion and structure of a rigid object using straight lines correspondences, T.S. Huang eds., Springer Verlag, 1983.

14/14