Calculer des propriétés du monde 3D à partir d’une ou de plusieurs images numériques,

… propriétés :

• Géométriques : forme, position …

• Dynamiques : vélocité …

But :

Outils :

• Hardware, robotique

• Algorithmes-> objet de ce cours pour l’essentiel

• Image Analysis

• Scene Analysis

• Image Understanding

• Image Processing

• Pattern Recognition

• Photogrammetry

Disciplines :

•Image Feature Detection

•Contour Representation

•Feature-based segmentation

•Range Image Analysis

•Shape Modeling and Representation

•Shape Reconstruction from Single-image Cues (Shape from X)

•Stereo Vision

•Motion Analysis

•Color Vision

•Image Understanding…

Champs de Recherches :

•Industrial Inspection and Quality Control

•Surveillance and Security

•Road monitoring and Autonomous vehicles

•Hand-eye robotics systems

•Space, Medical, Virtual reality, telepresence and telerobotics…

Applications :

Réalité virtuelle

Conférences :•ICCV•CVPR•ECCV•ICIO•ICPR

Ressources :

Journaux :•Int. J. of Comp. Vision•IEEE Trans. PAMI•CVIU•MVA•PR•PRL

Internet :• Computer Vision Home Page : http://www-2.cs.cmu.edu/~cil/vision.html• peipa.essex.ac.uk• iris.usc.edu/Vision-Notes/bibliography/contents.html• http://www.math-info.univ-paris5.fr/map5/doc.html

Quelques périodiques en ligne accessibles depuis Paris 5 :

Computational Geometry (depuis Mars 1995). Image and Vision Computing (depuis Février 1995). International journal of computer vision (depuis 1995) International Journal of Imaging Systems and Technology (depuis 1996). Pattern Recognition Letters (depuis Janvier 1995).

Sont également accessibles de nombreux autrespériodiques, publiés par :

Elsevier - Science Direct Kluwer Online Wiley Interscience

Site web et catalogue de quelques bibliothèques :

Bibliothèque Universitaire de Paris 5 BIU Scientifique Jussieu (via telnet) : login=mlibrary et passwd=jussieu. Bibliothèque Informatique-Recherche (Jussieu - site du Capitaine Scott)

Methods based on image features :• Point sets analysis• Calibration• Stereo Analysis• Feature-based motion analysis

Problématiques abordées :

Methods based on images directly :• Shape from single image• Optical Flow methods

Inspection 3D : scanner laser + système à base de franges de Moiré

Images

Features Optical Flow

FEATUREEXTRACTION

DIFFERENTIALMOTION

ANALYSIS

CALIBRATION STEREOFEATURE-BASED

MOTION ANALYSISOPTICAL FLOW

ANALYSIS

SystemParameters

ObjectLocation

3D Structure 3D MotionChange Detection

Tracking

Intensity Image vs. Range Image

Objectifs :

• Comprendre comment est imagée le monde 3D sur unerétine 3D optique : capteur passif

Géométriquement Algébriquement

• Apprendre la notion de modèle de caméra pinhole et de matrice de projection

• Définir les paramètres extrinsèques et intrinsèques d’un capteur passif

• Illustrer un système d’acquisiton 3D actif

Intensity image :images traditionnelles encodant les intensités lumineuses acquises par des caméras type TV (voir cours traitement d'images)

Range image :images codant la forme et la distance, acquises par des capteurs spécifiques comme le scanner laser. On parle d'images de profondeur ou topographiques.

Processus d'acquisition

Algorithmes d'extraction d'information

Objet de ce cours : l'Analyse du monde 3D en mouvement !!

Le processus inverse, la Synthèse 3D, utilise les mêmes principes théoriques. Computer Graphics is not so far !!

1. Paramètres optiques :• Type de lentille• Focale• Ouverture angulaire

2. Paramètres photométriques :• Type, intensité et direction de l'illumination• Propriétés de réflectance des surfaces observées

3. Paramètres géométriques :• Type de projection• Position et orientation de la caméra• Distorsions de perspective

4. Nature discrète des photorécepteurs5. Quantification de l'échelle d'intensité

Formation des Image d'intensités

Pinhole Camera

Nécessité de focaliser l'image …

Ouverture faible donc temps d'exposition long

Lentille mince

p’p

R

Q

Systèmes optiques réels

Champ visuel :Mesure de la portion d'espace 3D véritablement observée par la caméra

d

f

Fω

tan ω = d/2f

Problèmes :

• Aberrations sphériques et chromatiques• objets focalisés à des distances caméras différentes : notion dechamp de profondeur de la caméra (le modèle pinhole implique un champ de profondeur infini)

Intensity image :

1. Paramètres optiques :• Type de lentille• Focale• Ouverture angulaire

2. Paramètres photométriques :• Type, intensité et direction de l'illumination• Propriétés de réflectance des surfaces observées

3. Paramètres géométriques :• Type de projection• Position et orientation de la caméra• Distorsions de perspective

4. Nature discrète des photorécepteurs5. Quantification de l'échelle d'intensité

Communément, modèle de projection perspective pour un modèle de caméra pinhole

Modèle de la formation géométrique de l'image = Modèle de la projection géométrique opérée par le capteur

Modèle de caméra perspective

o o

Pp

O Oo o

Pp

o o

Pp

O O

Π

Π

Les équations fondamentales de la caméra perspective

Dans le repère caméra, on a :

x = f X/Zy = f Y/Zz = f

• On écrira p = [x,y]T

• Equations non linéaires

• Conservation de l'alignement et c'est tout

Voir coordonnées homogènes

Modèle orthographique : f -> ∞et Zmoyen -> ∞

δZ < Zmoyen/20

Math

[ ]

=

==

=⇔+=

=

ααα

•Coordonnées homogènes 2D :

• Une transformation affine générique v=Au+tdevient linéaire en coordonnées homogènes

=

=

Géométrie projective et coordonnées homogènes

u

v

Math

Définitions :Un point de l’espace projectif à n dimensions, ℘n , est représenté par un vecteur de dimension n+1 de coordonnées x = [x1,…,x n+1]T, avec au moins une des coordonnées xi non nulle

xi est appelée coordonnée homogène ou projectivex est appelé vecteur coordonnées

Deux vecteurs x = [x1,…,x n+1]T et y = [y1,…,y n+1]T représentent le même

point ssi +∈∀=≠∃ λλ

-> Il n’y a pas de correspondance biunivoque entre points et vecteurs de coordonnées ce qui rend l’application de l’algèbre linéaire à la géométrieprojective un peu plus compliquée qu’en géométrie euclidienne

Math

−=

=

=⇔

+=

!

!

θθθθ

θ

•Transformation Rigide 2D

• Identique en 3D

=

u

v

Classification des transformations 3DMath

Classification des transformations 3D ->2D d’un point de coordonnées (x,y,z) vers un point (x’,y’)

Math

=

== ""

Math

o o

Pp

=

==

Modèle de caméra perspective,version linéarisée dans le plan projectif !

Paramètres de caméra…

i

j

P(X,Y,Z)p(i,j)

Repère fenêtre ou pixellique ou frame

Repère MondeRepère ImageRepère Caméra

Paramètres intrinsèquesparamètres nécessaires pour lier les coordonnées pixelliquesd'un point image aux coordonnées correspondantes dans le repère caméra

Paramètres extrinsèques :paramètres qui définissent l'orientation et la localisation du repère caméra par rapport à un repère monde connu

Estimation de ces paramètres = calibration de caméra

…intrinsèques

x

y

o

xim

yim

Xcam

Ycam

Ocam

f

…extrinsèques

w

w

wOcam

w

Paramètres de caméra…

( )

( )

( )

( )

( )

( )

=

×

××

w

w

w

…extrinsèques

Pc=R(Pw-t)

Avec T=-Rt

w

w

wOcam

w

Paramètres extrinsèques :vecteur translation, T, et matrice de rotation, R (ou mieux ses paramètres libres), qui spécifient la transformation entre la caméra et le repère monde

=

=

#!$%&'

#(#')( #' !$&*(*( )')+),)'( -.&*' -.&&'

!.,)( -.& $&/##,)(#0

– Image Plane or Focal Plane Π– Focal Distance f– Camera Center Oc

– Principal Point o– Principal Axis (OcZc)– Principal Plane (Oc,Xc,Yc)– Camera Coords (Xc,Yc,Zc)– Image Coords (xim,yim)

…intrinsèques

11

22

33

44

xim

yim

Oco

Π

x

y

p

P

Pour un modèle de caméra perspectif, 3 ensembles de paramètres intrinsèques spécifiant :

1. La projection perspective caractérisant le passage repère caméra 3D (X,Y,Z) -> repère image projectif (x,y) : paramètre f

2. La numérisation caractérisant le passage repère image (x,y) -> repère fenêtre CCD (xim,yim) : paramètres ox,oy,sx,sy

3. La distorsion géométrique introduite par l'optique (en périphérie ou si large champ de profondeur), de nature radiale :paramètres k1 et k2.

1. Passage du repère caméra 3D (X,Y,Z) au repère image projectif (x,y) : paramètres f

=

==

2. Passage du repère caméra (x,y) au repère fenêtre CCD (xim,yim) : paramètres ox,oy,sx,sy

x

y

o

yim

xim

En négligeant toute distorsion géométrique introduite éventuellement par l'optique et sous l'hypothèse que le tableau CCD est constitué de grilles rectangulaires d'éléments photosensibles, on a :

x = - (xim-ox)sxy = - (yim-oy)sy

avec (ox,oy) les coordonnées en pixels du centre de l'image (le point principal) et (sx,sy) la taille effective des pixels (en mm) dans les directions horizontales et verticales respectivement.

3. Correction de la distorsion géométrique :paramètres k1,k2

x = xd(1+k1r2+k2r4)

y = yd(1+k1r2+k2r4)

avec r2 = xd2+yd

2

Le plus souvent, on néglige cette distorsion et sinon, on prend k2=0

CCD de 500x500, lentille de qualité moyenne, distorsion au coin de l'image ≈ 5 pixels

Paramètres intrinsèques :•la longueur focale f, •la localisation du centre de l'image en coordonnées pixelliques(ox,oy),•la taille pixellique effective dans les directions verticales et horizontales (sx,sy)•et si nécessaire le coefficient de distorsion radiale k1.

( )

( )

( )

=

==

−

−

=

−

−

=

"

==

==

( )

( )

( )

−−

=

!'( ! #(#,&'&(0

5

5

5

5

==

==

x

y

o

xim

yim

Xc

Yc

oc

f

!! L'origine du plan image peut être translatée

( ) ( ) ( ) ( ) ( ) ( )

! ! !' !' ===

( )

( )

( )

−−

=

×

××

L'équation linéaire matricielle de la projection perspective

==

w

w

wOcam

w

w

w

w

xim yim

Mint

Mext

avec

Images de profondeurs

Intérêts : • Éviter les obstacles• Estimer la forme des surfaces• Inspecter des objets manufacturés

Difficile à faire partir d'une image d'intensité-> voir suite du cours

Acquérir directement la forme : les "range sensors" produisant des "range data"

Range images :Ce sont des cas spéciaux d'images numériques. Chaque pixel d'une image de profondeur exprime la distance entre un repère référence connu et un point visible de la scène. Ainsi, une image de profondeur reproduit la structure 3D d'une scène et est visualisable comme une surface échantillonnée.

Représentation des « range data »

Sous la forme rij Sous la forme xyz

Range image = Depth image = xyz images = surface profile = 2.5D images

Active vs. Passive range sensors

Les capteurs de profondeurs passifs reposent seulement sur des images d'intensités pour reconstruire la profondeur (ex. : stéréoscopie). -> voir cours plus loin

Les capteurs de profondeurs actifs projettent de l'énergie (ex. : un motif de lumière, des impulsions sonars) sur la scène et détecte sa position pour réaliser la mesure ou exploitent l'effet de changements contrôlés de certains paramètres du capteur (ex. : focus).

•Radar et sonar•Interférométrie de Moiré•Focalisation/Défocalisation active•Triangulation active

Systèmes d’acquisition par Triangulation active

• basés sur caméras d’intensité

• OUTPUT : carte dense de coordonnées 3D précises

• faciles à comprendre et à construire Projecteur Caméra vidéo Repère monde = Repère caméra Plan lumière ⊥ (XZ)Angle (Plan lumière, (XY)) = θ : paramètre de balayage Plan lumière ∩ Surface Objet = Stripe (courbe planaire) observée par la caméra

−=

"

θ

Pour chaque point visible de la bande,

-> Profile 3D des points de la surface ou cross-section

En faisant varier θ,

-> ensemble de cross-sections 3D -> range image complète de l’objet

Comment rendre très visible la bande dans l’image :

• ligne claire : laser light : 3D laser scanner• ligne noire sur objet clair

Comment éviter les occlusions ?

Nécessiter de calibrer le système en f,b, et θ

θθ’

θ

Un système par calibration directe ?

Soit on procède à une calibration de f,b et θ comme précédemment,Soit on calibre directement, simplement mais manuellement, sans équation

Construction d’une LUT (look-up table) liant une image et ses coordonnées 3D, en mesurant les coordonnées image d’une grille de points 3D connus, et en stockant à la fois les coordonnées image et monde pour chaque point.

Les valeurs de profondeurs de tous les autres points sont obtenues par interpolation.

La procédure utilise quelques blocs rectangulaires de hauteur connue δ. Un bloc G doit avoir un nombre n de rainures parallèles de forme rectangulaires. On suppose enfin que la taille de l’image en pixels est xmax x ymax

Procédure RANGE_CAL

!"# $ % "&'

' (

) * + & &,+ -

. /) % (

0 1 (, -

%

2 3 4&!5 "'6 % 1

( % % % "!7 0) % 4&!5

2849!5 ,-

: ; ( 1 ( δ ) ' < %

1 9=!

>? .2:)+ ) 1 ( % "#

@3 AB C.8D & % 4&5 & # &&' # &' 49!5

&

& ) 0

E D %

Algorithme RANGE_ACQDD ?/(7F3/D

' ( ) % (.3 % 4&5 0)

%

2 & D % 4&5

1 49!5

E 28 & % "A%

1 C

Remarque : quand un bloc est ajouté à la scène de calibration, la raie doits’élever d’au moins 1 ou 2 pixels, sinon, la calibration ne discriminera pas entre les niveaux Z.

• “Basic Math for 16-720”, Martial Hebert, (mathprimer.pdf et mathfigures.pdf)

• “Trinocular Active Range Sensing”, A. Blake et al., IEEE PAMI, vol. 15, pp. 477-483, 1993 (Bibliothèque Informatique-Recherche -Jussieu - site du Capitaine Scott)

• “Shape from Focus”, S.K. Nayar et al., IEEE PAMI, vol. 16, pp. 824-831, 1994 (Bibliothèque Informatique-Recherche -Jussieu - site duCapitaine Scott)

• “3-D Digitizers”, T. Wohlers, Computer Graphics World, pp. 73-77, 1992

Bibliographie

%6

Objectifs :

• Redéfinir les paramètres extrinsèques et intrinsèquesd’un capteur passif

• Estimer ces paramètres un par un en utilisant la caméracomme instrument de mesure

• Apprendre la résolution d’équations par décompositionSVD

• Estimer la matrice de projection directement

+ intrinsic parameters ->

7c8c

?( )

( )

( )

−−

=

×

××

??

Problème de la calibration

Étant donné une ou plusieurs images d'un motif de calibration, estimer :

1. Les paramètres intrinsèques2. Les paramètres extrinsèques3. Les deux

-> pas indispensable mais ouvre la voie à des algorithmes de reconstruction et reconnaissance 3D performants

-> la caméra est utilisée comme instrument de mesure

( )

( )

( )

( )##

( )

( )

( )

( )###

( )

Motif de calibration

?

=

Yw

Xw

Zw

2 méthodes reconnues :

1.

2. par matrice de projection

=

( )

( )

( )

−−

=

×

××

par estimation directe des paramètres

9 8':,&$&($!!)&0; ($!!)&1&!<'(&=7 ,8 ,>* 7&/

; ($!!)& ,#+&=78> !,,

; ($!!)&#,)(#=423>

; ($!!)&,!$&=4?2?3?>

9 #(#,:'(&$&#,)(#0; #(#,:'(& !'( !:-.&=$&/##,&(#&'$.@1(#,& +(#AA&(@>0(&/ &

/&@ $".!* !' ,#+&* !'B&@

; #(#,:'(&&7'( !:-.&0$)1 ! &!'/#/#/ #' !&'/"( &!'#' !$.@ *#((#**('#.@

Zw

Xw

Yw

Y

X

Zx

yO

Pw

P

p

x im

y im

(x im,yim)

Pose / Camera

Object / World

Image frame

Frame Grabber

9 C(/$'#,&(#; #,&(#0D=423>

; C(/$0? D=4?2?3?>

; (#!1(,#' !0

9 #,&(#',#+&; #,&(#0D=423>

; ,#+&0*D=78>

; -.#' !!!/ !)# (&

9 ,#+&'E(#,&; '( ! !)+/ +)&

; E(#,&=7 ,8 ,>

9 C(/$'E(#,&; =4?2?3?> FG=7 ,8 ,>

; E#/& &11&' H&9 17 D1718D18

+

++

=

+++

++++++

=+=

>=

>=

−−=−−=

>=>=

=

++++++

−=−

++++++−=−

++++++

−=−

++++++−=−

• Ce qui est inaccessible disparaît : le repère caméra

• On se fonde sur ce qui est mesurable : x, y, X, Y et Z

• On compte sur un nombre minimum de mesures pour résoudre un système d'équations linéaire …

• 2 étapes :1. On suppose connues =78>/&&!'(&$&/" ,#+&&'

!&' ,&'./&#.'(&*#(#,:'(&

5 . !#/./&=78>5

9 #(#,:'(&7'( !:-.&0

; ,#'( &$&('#' !7

9 ( #!+/&α,β,γ; H&'&.('(#!/#' !F

9 #(#,:'(&!'( !:-.&0

− α D1718 D87&'17

; =78>0 !.**&/& FG=7"8">!!.&

; I&11 &!'$&$ '( !(#$ #/&0

++++++

−=−=

++++++

−=−=

"

"

Étape 1

Supposant que la localisation du centre de l'image =78>

&'!!., et que la distorsion radiale peut être négligée, on doit estimer 17α, R et T à partir des points images (xi,yi), i = 1 à N, projections des N points connus (Xi, Yi, Zi) dans le référentiel monde.

Même dénominateur dans les deux équations

>=">=" +++=+++

">=">= +++=+++

>=">=" +++=+++ α

>=>=>=>= =−−−−+++ αααα

=−−−−+++

>=

>=

αααα=

Pour chaque paire de points (Xi, Yi, Zi),(xi,yi)

Équation linéaire à 8 inconnus v = (v1,…,v8)T

=−−−−+++

=

−−−−⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅

−−−−−−−−

=

##############

Pour N points, on obtient un système linéaire homogènes à 8 inconnus et N équations.

Le système admet une solution non triviale (à un facteur d'échelle près) : Si N >= 7 et les N points sont non coplanaires => Rank (A) = 7

preuve dans le livre de Faugeras

Que l'on trouve grâce la décomposition SVD de A=UΣVT par exemple v est le vecteur colonne de V correspondant à la seule valeur propre nulle

singulière le long de la diagonale de D

Matlab, Scilab …. Lignes de VT: vecteurs propres ei de ATA Solution: v= e8 , la 8ème ligne correspondant à la seule valeur singulière

nulle σ8=0 Considération pratique : les erreurs de mesures peuvent rendre rang(A)=8,

on considère alors la seule valeur propre singulière la plus faible le long de la diagonale de Σ

σσσσ0

SingularValue Decomposition

Math

Cette décomposition s’applique à une matrice rectangulaire.

Elle permet 3 applications importantes :

• Résoudre des systèmes d’équations linéaires non homogènes,• Résoudre des des systèmes d’équations linéaireshomogènes de rang déficient,• Garantir que les entrées d’une matrice extraitenumériquement satisfont des contraintes données(orthogonalité par exemple).

),*' ! &!J#/&.( !+./ :(&

SingularValue Decomposition

Math Théorème :Toute matrice A ∈Μmxn peut s’écrire comme le produit de 3 matrices : A = UDVT telles que :

• U ∈Μmxn et V ∈Μnxn et leurs colonnescorrespondent à des vecteurs unités mutuellementorthogonaux;

• D ∈Μnxn est une matrice diagonale dont les élémentsdiagonaux, σi, appelés valeurs singulières, sont tels queσ1≥σ2≥σn≥0 .

Remarque : alors que U et D ne sont pas uniques, les valeurs singulières sont complètement déterminées par A

SingularValue Decomposition

Math Propriété 1 :Une matrice carrée A est non singulière ssitoutes les valeurs singulières sont différentesde 0.

Remarque : quand 1/c est comparable à la précisionarithmétique de votre machine, la matrice A est mal conditionnée et de façon pratique peut être considéréecomme singulière et donc non inversible.

Définition : conditionnement

Le ratio c= σ1/σn appelé conditionnement mesurele degré de singularité de A.

SingularValue Decomposition

Math Propriété 2 :Si A est une matrice rectangulaire, le nombrede σi non nuls égale le rang de A.

Remarque : en pratique on utilisera unetolérance ε≈10-6

Propriété 3 :Si A est une matrice carrée, non singulière, son inverse peut s’écrire A-1=V D-1 UT

Remarque : que A soit singulière ou non, la pseudo-inverse de A, A+ peut s’écrire A+=V D0

-1 UT avec D0-1 égale à D-1

pour toutes valeurs singulières non nulles et zéro sinon.Si A est non singulière, D0

-1 = D-1 et A+= A-1

SingularValue Decomposition

Math Propriété 4 :Les colonnes de U correspondant aux valeurssingulières non nulles décrivent l’image de A, les colonnes de V correspondant aux valeurs singulièresnulles décrivent le noyau de A.

σσσσ0

Propriété 5 :Les carrés des valeurs singulières non nulles sont les valeurs propresnon nulles de ATA ∈Μnxn et de AAT ∈Μmxm.Les colonnes de U sont les vecteurs propres de AAT et celles de V ceux de ATA.De plus, Auk= σk vk et ATvk= σk uk avec uk et vk les colonnes de U et V correspondantes à σk .

SingularValue Decomposition

Math

Première Application :Résolution de systèmes d’équationslinéaires non homogènes

Soit le système de m équations linéaires à n inconnues Ax=b• A ∈Μmxn la matrice du système linéaire non homogène• x ∈ℜn le vecteur des inconnues• b ∈ℜm le vecteur de données

""" =⇔=≠

( ) "" +=⇔=Cette solution est optimale aux sens des moindres carrés. De plus ATA estcarrée. On calcule (ATA)+ grâce à la SVD. Dans le cas de plus d’équationsque d’inconnues, la pseudo-inverse (ATA)+ est en effet plus apte à coïncideravec (ATA)-1 .

=A bx

SingularValue Decomposition

Math

Deuxième Application :Résolution de systèmes d’équationslinéaires homogènes de rang déficient

Soit le système de m équations linéaires à n inconnues Ax=0• A ∈Μmxn / rang(A)= n-1 et m ≥n-1• x ∈ℜn le vecteur des inconnues

Si on ignore la solution triviale, une solution unique à un facteur d’échelleprès peut être trouvée grâce à la SVD. Cette solution est simplement proportionnelle au vecteur proprecorrespondant à la seule valeur propre nulle de ATA (toutes les autresvaleurs propres étant >0 car rg(A)=n-1)Propriété 4 et 5 -> cette solution est la colonne de V correspondant à la seule valeur propre nulle de A (le noyau de A).

=A 0x

σσσσ0

SingularValue Decomposition

Math

Dernière Application :Assurer des contraintes

On génère souvent des estimées d’une matrice A, dont les entrées ne sontpas toutes indépendantes, mais satisfont des contraintes algébriques (voireles matrices orthogonales).

Or, les erreurs produites par le bruit et les altérations dues aux calculsnumériques abîment la matrice Â, si bien que ses entrées ne satisfont plus les contraintes données -> problème par la suiteLa SVD permet de trouver la matrice la plus proche de A au sens de la norme de Frobenius et qui satisfasse les contraintes exactement.

SingularValue Decomposition

Math

• Equations for scale factor γ and aspect ratio α

• Knowledge: R is an orthogonal matrix

• Second row (i=j=2):

• First row (i=j=1)

>= ααααγ=

( )

=

==×

$

≠=

=K 1

K 1$

=++

LL ++=γ

=++

LL ++=γα

α

LL γ

v1 v2 v3 v4 v5 v6 v7 v8

Scale Factor and Aspect Ratio

• Equations for first 2 rows of R and T given α and |γ|

• First 2 rows of R and T can be found up to a common sign s (+ or -)

• The third row of the rotation matrix by vector product

• Remaining Questions :

– How to find the sign s?– Is R orthogonal?– How to find T z and f x?

>=LL ααααγ=

×=×=

( )

=

==×

$

Rotation R and Translation T

Find the sign s

• Facts:– fx > 0– Zc >0– x known– Xw,Yw,Zw known

• SolutionCheck the sign of Xc

Should be opposite to x

++++++

−=−=

++++++−=−=

Zw

Xw

Yw

Y

X

Zx

yO

PwP

p

x im

y im

(x im,yim)

• Question: – First 2 rows of R are calculated

without using the mutual orthogonal constraint

• Solution: – Use SVD of estimate R

×=×=

( )

=

==×

$

MNN =

!" =N

" =

Replace the diagonal matrix D with the 3x3 identity matrix

Rotation R : orthogonality

9 /.' !

; /H&'O&8'&,1/ !&#(

&-.#' !? 'O'?.!I!?!P17

; %&#'-.#(&,&'O$

; J,&'O$'1 !$ !H&(&

++++++−=

=

>=>= ++−=++++

ai2ai1bi

+=

>=

N

N

Find Tz et fx

Étape 2

Estimation du centre de l'image =78>

Remarque : la précision de l’estimation du centre o de l’imagen’influe pas sur les autres paramètres mais est importante pour d’autres applications (telle que la modélisation du mouvement)

Définition : Point de fuite

Soient Li, i=1,…,N droites parallèles dans l’espace 3D, et li les droites images correspondantes. En raison de la projection perspective, les droites Li apparaissent comme se rencontrant en un point p, appelé point de fuite, défini comme l’intersection commune de toutes les droites images li.

VP1

Y

X

Z

OC

Théorème : Point de l’orthocentreCentre de l’image à partir des points de fuite

Soit T le triangle du plan image défini par les trois points de fuite de 3 ensembles mutuellement orthogonaux de droites parallèles de l’espace. Le centre de l’image est l’orthocentre de T.

VP1

VP2

VP1

VP2

VP3

VP1

VP2

VP3

h3

h1

h1

(ox,oy)

Piste pour la preuve du théorème :

Soit h la hauteur relaint le sommet (et point de fuite) v au côté s, et O le centre de projection. Comme s est à la fois orthogonal à h et vO, le plan passant par h et vO est orthogonal à s et donc au plan image…

http://w3.impa.br /~pcezar/3dp/original/CVL_html/appPage/calib_doc/index .html

C’est un problème inverse intéressant :étant donné une photographie prise par une caméra inconnu à partird’une position inconnue et qui a été rétrécie ou élargie, comment déterminer la position et l’orientation de la caméra mais aussi jusqu’àquel point l’image a été rétrécie ou élargie ?

Les applications sont nombreuses :En navigation autonome, un missile de croisière peut obtenir la matricede transformation caméra à partir d’un modèle de terrain embarqué et ainsi calculer les paramètres de la caméra qui définissent la localisationdu véhicule. Ou bien encore, une caméra stationnaire observant la zone de travail d’un bras robotisé peut déterminer la position et l’orientation du bras articulé par marquage de l’instrument de manipulation.

Math De la géométrie euclidienne à la géométrie projective

P Q

"0

">"Q=

* !'$&6 (#**('

%

&

%

&%& =

P

QM

"0

" %

&

%

&

Théorème 1

La projection conique de centre O sur le plan Π est une bijection de ∆\Mo sur ∆'\ωδ, si ∆ n'est pas parallèle à Π.Théorème 2

Une famille de droite toutes parallèles à une même direction δ a pour image une famille de droites dans Π qui concourent toutes en le même point ωδ lorsque δ n'est pas une direction de Π.Théorème 3

Aux différentes directions d'un même plan P non parallèle à Πsont associées des points ωδ tous situés sur la droite Lp = Po∩Π.Si P1 et P2 sont parallèles, LP1=LP2.

Le point ωδ s'appelle le point de fuite de la direction δ .La droite Lp s'appelle la ligne de fuite du plan P (l'horizon).

Math

Point de fuite – Ligne de fuite

O

(∆)

(∆ 1)

M0

Π

(∆’)(∆’1)

m

m1

ωωωωδδδδ

O

(D)

(D’)

M0

Π

(D’)(D’1)

m

m1

ωδ

P

P0

(LP)

(D0)ωα

Théorème 3

Aux différentes directions d'un même plan P non parallèle à Πsont associées des points ωδ tous situés sur la droite Lp = Po∩Π.Si P1 et P2 sont parallèles, LP1=LP2.

Le point ωδ s'appelle le point de fuite de la direction δ .La droite Lp s'appelle la ligne de fuite du plan P (l'horizon).

Adjonction des points à l'infiniDeux droites parallèles sont des droites qui se coupent à l'infini, en ajoutant un point à toute droite ∆ de E qu'on appellera son point à l'infini, noté ∞∆.On définit ce point à l'infini comme la direction δ de ∆.

$&*(K&' 1*/#!$&&!&,A/&N

$&*(K&' H&$( '&$&&!&,A/&N

*(K&' 15&*#&#**&/)N,<,&&

5$&*(K&' 1*/#!.!N&'

$& !1 ! /"B$( '&/##**&//&"&'$&$( '&$&

!1 ! /"B* !'$&&!&,A/&/"&'RN,<,&&

$&*(K&' H&$( '&$&*(K&' 1,*/)')N

=∞

=∆∞

∞=

∞∞∞=

∆∞∆=∆ ∆

'

'

Math

Plan affine augmenté

Avec ces définitions, deux droites projectives coplanaires distinctes de l'espace projectif se coupent toujours en un point de cet espace et un seul.Remarque : • 2 droites D et D’ parallèles ont le même point à l’infini,

• de plus, %

% =∞ ∆ >Q=

ou droite à l’infini

"(( ∞=∞

Math

Prolongement des projections

La projection conique p:E\ ΠO→Π de point de vue O se prolonge naturellement en une application :

Π→ NSN0 )'!

En particulier, elle établit une bijection entre

Ainsi, p(MO)=∞∆' et p(∞∆)= ∞δ

et la projection conique préserve le birapport de 4 points distincts quelconques de , pourvus qu'ils soient alignés sur une droite de ne passant par O. Cas intéressant d'un milieu de segment :

SN''N

>>=>=>==>Q= δω!%!!%

% ==∞∆

"N&'N ∆∆

AB

C∞∞∞∞δδδδ

&!(#**(',<,&$.H#/&.(/#B

)+#/&&'&!*(K&')&1 .!&6

H#/&.(%#

δ

δ

∞∞

%

0>Q= =∞∞

=∞δδ

δ%

%

%

Math

Sphère unité

Ray Space

Visualiser le plan projectif : ses points et ses droites

Math La géométrie projective et le plan projectif

• Une image plane est modélisée par le plan projectif ℘2

• Transformation d’un point du plan projectif [X,Y,W]T vers le plan euclidien [x,y]T

==

• Nécessité de points à l’infini ou points idéaux (cas où W=0) danschaque direction : ensemble des points [X,Y,0]T

• Droite idéale représentéepar (0,0,1)

Coordonnées Homogènes

La projection p est une bijection entre l'ensemble de toutes les droites de E passant par O, P(E), et .

En effet, si ∆O est une droite de Π0 passant par O et ∆ est une droite affine de Π parallèle à ∆O, on pose p(∆O)= ∞∆= ∞ ∆0.

ΠN

Coordonnées Homogènes

La projection conique p associe au point M de E\ΠO de coordonnées (X,Y,Z) (Z≠0) le point m de Π de coordonnées (x=X/Z, y=Y/Z).On dit que (X,Y,Z) est un système de coordonnées homogènes du point m et l'on note m=[X,Y,Z].

Dans le plan affine, le repère affine (Ω,i,j) donne :

ΠN

I3K2 4

$&>IK =#11 !&(&*:(&/&$#!I

++=

Ω=

+=Ω $

Math

p((OM))=m et tout point de (OM) définit un système de coordonnées homogènes de m ( λX,λY,λZ) (Z≠0)Or p(∆O)=∞∆ et si ux+vy+w=0 est l'équation affine dans le repère (Ω,i,j) de (∆), l'équation affine de ∆O dans (O,i,j,k) est uX+vY=0, or tout point de ∆O définit un système de coordonnées homogènes de ∞∆, donc ∞∆ = [-v,u,0] est un système de coordonnées homogènes de ∞∆.

Désormais tout point [X,Y,Z] définit un élément de pourvu que X,Y,Z ne soient pas tous nuls simultanément.

ΠN

∆N

Coordonnées Homogènes

Coordonnées HomogènesMath

X

Y

Z

x

y

O

ΩΠ

ΠOMO=(-v,u,0)

m=(x,y)

M=(X,Y,Z)M'=(aX,aY,aZ)

0 =+∆ )

0 =++∆

Coordonnées HomogènesMath

De même, la droite à l'infini du plan ∞Π a pour équation Z=0. Ainsi toutes les droites projectives de sont définies en coordonnées homogènes par une équation de la forme uX+vY+wZ=0 avec u,v,w non tous nuls.

ΠN

Avec ces conventions, le point [X,Y,Z] appartient àssi uX+vY+wZ=0.

C'est l'équation de en coordonnées homogènes.

∆N

∆N

Coordonnées Homogènes pour des (a) points (b) droites

Principe de dualité ou d’équivalencedes points et des droites

Math

• Equation d’une droite :•Euclidienne (a,b,c):

ax+by+c=0 aX+bY+cW=0 avec x=X/W et y=Y/W

•Projective u:

== !!

Principe de dualité ou d’équivalencedes points et des droites

Math

Nous dirons qu'un résultat, un concept, ou un problème de géométrie plane relève de la géométrie projective s'il peut s'exprimer en termes d'alignements de points, de concours de droites ou de plans et de birapports sans que l'on ait à distinguer les points à l'infini des autres.

Les concepts de conique est un concept de la géométrie projective. Le parallélisme appartient à la géométrie affine.

2 points du plan projectif sont alignés par définition.Donc, 2 droites du plan projectif s'intersectent toujours (en un point qui peut être à l'infini)

Math

−=

×

Principe d’équivalence des points et des droitesTout théorème du plan projectif peut être reformuléen substituant les points aux droites et inversement

Le théorème de Desargues

Math

! 0?'( #!+/&6#!$"6""#(&# $'A&*!!

1'O&(& #* !'.O'O#'"66"#!$"#(&#//'(# +O'

/ !&5!'O #&'O&8#(&# $'A& !*&(*&' H&1(,5

Les théorèmes de Desargues en 3D

#$ 1'?'( #!+/&6#!$"6""#(& !*&(*&' H&'O&!

'O&(&&7 '#/ !&/*# !+'O(.+O&H&(8* !'1 !'&(&' !1

=&7'&! !1>((&*!$ !+*# (1&$+&1'O&'?'( #!+/&5O#'

'O&(& #/ !&?O O!'# !0'O& !'&(&' !16#!$T6" 'O&

!'&(&' !1#!$T"#!$'O& !'&(&' !16#!$6T"5

%$ 16#!$"6""#(&'?'( #!+/&.O'O#''O&(& #/ !&

/*# !+'O(.+O#* !',,!'6#!$6""#* !',,!'

#!$""#!$#* !',,!'6#!$"6"'O&!'O&'( #!+/&#(&

!*&(*&' H&5

OA

A’

Math

&!'$&.7'( #!+/&T6TT &'TT6TTTT$".!

*/#!$!'/&,,&'!'$&.7B$&.7$ ' !'&'

$!'/&*(/!+&,&!'$&*# (&$&U')

O,/+.&T6T TT6TT &'5 &.*&!'&!$&

* !'V&'5

%&$( '&TTT 6T6TT&'TTT!'

!.(#!'&.*#(#//:/& &'&./&,&!' /&

* !'V&'!'#/ +!)5

Le théorème de Desargues en 2D

Remarque : tout résultat du plan projectif se montre plus facilement en immergeant la configuration dans l’espace et fournit des résultat euclidiens en considérant une ligne de fuite particulière

Math

Le théorème de Desargues généralSoient 6 points A’,B’,C’, A”, B”, C” formant deux triangles.Les droites A’A”, B’B”, et C’C” sont concourantes ssi les pointsdéfinis par les (intersections des) côtés correspondants (A’B’), (A”B”), (A’C’), (A”C”), (B’C’) et (B”C”) sont alignés.

Sa version dualeSoient 6 droites a’,b’,c’, a”, b”, c” formant deux triangles.Les points a’a”, b’b”, et c’c” sont alignés ssi les droitesdéfinies par les sommets correspondants (a’b’), (a”b”), (a’c’), (a”c”), (b’c’) et (b”c”) sont concourantes.

Math

Interprétation projective du théorème de Desargues

2 triangles perspectifs par rapport à un point ⇔

2 triangles perspectifs par rapport à une droite

Principe d’équivalence des points et des droitesTout théorème du plan projectif peut être reformuléen substituant les points aux droites et inversement

Math

Application aux ombres dans les images

O&.!=H &?&$##* !'/ +O'.(&>#'!'O&*/#!#(+(.!$'O&

O#$?"%""1#'( #!+./#((1%5! $&(#*&(*&' H& ,#+&1

#//'O #!$O?'O#' ' #&#(+.& #!!1 +.(#' !5?O O

/ !&$&'O&/ !&1 !'&(&' ! !&#(+.&'O&(&,((&*!$M1#

1.('O&(* !'( !'O&*/#!&% *($.&#O#$?("O?'O#' '

* A/&'(&!'(.''O& ,#+&1( 1(,'O#'1("5

Math

/&7 '& $&.7'O)(:,&-.&/&W),:'(&#**&//&!'& /".!$&/"#.'(&5!!!

/&.()!!)&!!H&!#!'*#(&7&,*/&$"#**&/&($( '&V/#$( '&-. *#&(# '*#(/&

$&.7* !'&'V&' $"#**&/&(* !'*- /&* !'-. &(# '/" !'&(&' !$&$&.7$( '&

*&'-5

'#0 &!'66"6@"@ 7* !'$".!*/#!5 /&$( '&6""6@&'6@

!'!.(#!'&$&,<,&-.&/&$( '&6@@6"&'6"#/(/&$( '&66@"

&'6"@!'#. !.(#!'&5

'%0 &!'AA"A@"@ 7$( '&$".!*/#!5 /&* !'A""A@&'A@!'

#/ +!)$&,<,&-.&/&* !'A@@A" &'A"#/(/&* !'AA@"&'A"@!'#.

#/ +!)5

Le théorème de Pappus

Math

%#+),)'( &$&( *' H&=*(K&' H&>&'/&$,# !&$&

,#'O),#' -.&-. ,$)/ &/&!' ! !'. ' H&$&!!

&'$"+5//&#$"#A($)') ,#+ !)&#.4J& :/&*#($&

,#'O),#' &!,,&##/ .&#(+.&#H#!'$&',A&(

$#!/".A/ K.-."B#(&$).H&('&*#(!&/&'&'#(&, &#.

+X'$.K.(*#(E)/ 7Y/& ! B/#1 !$.44& :/&5//&&'

#.K.($"O. /#(+&,&!'.' / )&*#(/&8':,&$&H .#/ #' !

.(($ !#'&.(W% &'*&!W% +(Z&!'#,,&!'B5E#.+&(#

=>5

Yw

Xw

Zw

Yw

Xw

Zw

Procédure PARAM_CAL % 1

' ; 28 0) 1 1 ; ":

. 8 1 % 0

G D % 1 H ,I%0-

G 7 % %

&

2 3 1 ' . 2 1 &

: 3 0 E % ' . 2E %

> / % J8 /

D J + % /

@ 8 α KγKL 8 & % ? &

M 3 % ? & % L 1 0% ?

J8

N 30 ) ,&&- 11 # %

,&&-,''9OP'.=

OP'2!QP&-R# 1 % & %

? &

'# ? / S 1&

E &α1& &)

2 méthodes reconnues :

1. par estimation directe des paramètres

2.

=

( )

( )

( )

−−

=

×

××

par estimation directe de la Matrice de Projection

=

&((

=

=

(

−−

=

!'

(

=

Rappels

=

(

Soit, en laissant tomber les indices im et w, pour un point Pi et son image pi dans le référentiel fenêtre (qu’on appelera image),

+−+−

++−+−+−+−+−+−

=

(

Avec, M à 10 paramètres (4 intrinsèques + 6 extrinsèques)

=

(

++++++==

++++++== =

D’où pour N paires (xi,yi),(Xi,Yi,Zi) liantles référentiels image et monde,

Avec

⋅⋅⋅⋅⋅⋅−−−−−−−−

=

[ ] =

On a affaire à un système d’équations linéaires en m à 2N équations

et 11 variables indépendantes :

-> Si N >=6 , la SVD indique que m sera connu à un facteurd’échelle près.

Etape 1 : Estimation de la matrice de projection M

[ ] N α=

&' .!& ,#'( & $&*(K&' !7

; !' &!' B /#1 /& !1(,#' ! !'( !:-.& &'&7'( !:-.&

+−+−

+−+−+−+−+−+−

=

(

(( γ=N

=

N

,

,

,

)

)

)

(

Etape 2 : Calculer les paramètres de caméra

Yw

Xw

Zw

Yw

Xw

Zw

Procédure PROJ_MAT_CAL % 1

'; 28 0) 1

1 ; ":

.8 1 % 0

GD % 1 H ,I%0-

G7 % %

&

27 % J8 /"8JD

J + % /

: KγK > ; + % σ

@ 3 !

L 3 ?2

M & ")')2 ").

)2

N E 1& 1

'#

'' % σ S R# EQ E 0% ?

0) J8

E &α1& &)

α=N

γγ =++=++

NNN

NNγ←

N σ=

Nσ=

,,,, −=−=

>N=>N=

>NN=>NN=

−=−=

−=−=

σσσσ

Propriétés en commun : On résoud D’abord un système linéaire puis on procède à unedécomposition en paramètres physiques;

Les résultats devraient être identiques.

Différences :

Le nombre de variablers dans les systèmes homogènes considérés : Méthode matricielle directe : tous les paramètres d’un coup, puis 2N Equations de 12 variables Méthodes paramétriques directe : N Equations de 8 variables, puis N équations de 2 Variables, puis trouver le Centre de l’Image – peut-être plus stable

Les hypothèses :Méthode matricielle directe : plus simple et plus général; parfois la matricede projection est suffisante et donc on n’a pas besoin de la décompositionen paramètres physiques réels.Méthodes paramétriques directe : elle suppose que le centre de l’imageest connue au départ puis que le rapport d’aspect est connu pour l’estimation du centre de l’image

la largeur de la pyramide du Louvres est 35,42m, et sa hauteur 21,64m

60 triangles de verre spécial et 603 losanges

• “Three-dimensional computer vision : A geometric Viewpoint”, O.D. Faugeras, MIT Press, Cambridge (MA), 1993

• “Introductory techniques for 3D computer vision”, E. Trucco et Alessandro Verri, Prentice Hall, 1998

Bibliographie