Bases géométriques de l’informatique – Part deux Jean Ponce “Hauts du DI” Email:...
71
Bases géométriques de l’informatique – Part deux Jean Ponce “Hauts du DI” Email: [email protected]Web: http://www.di.ens.fr/~ponce Planches après les cours sur : http://www.di.ens.fr/~ponce/geomvis/lect1.pp http://www.di.ens.fr/~ponce/geomvis/lect1.pd
Bases géométriques de l’informatique – Part deux Jean Ponce “Hauts du DI” Email: [email protected]@di.ens.fr Web: ponceponce
Bases gomtriques de linformatique Part deux Jean Ponce Hauts du
DI Email: [email protected]@di.ens.fr Web:
http://www.di.ens.fr/~poncehttp://www.di.ens.fr/~ponce Planches
aprs les cours sur : http://www.di.ens.fr/~ponce/geomvis/lect1.pptx
http://www.di.ens.fr/~ponce/geomvis/lect1.pdf
Slide 2
References R. Hartley and A. Zisserman, Multiple View Geometry
in Computer Vision, Cambridge University Press, 2000. O.D.
Faugeras, Q.-T. Luong, and T. Papadopoulo, The Geometry of Multiple
Images, MIT Press, 2001. D.A. Forsyth and J. Ponce, Computer
Vision: A Modern Approach, Prentice-Hall, 2002, 2011 (2 nd
edition). J.J. Koenderink, Solid Shape, MIT Press, 1990. M. Berger,
Gomtrie, Nathan, 1992. D. Hilbert and S. Cohn-Vossen, Geometry and
the Imagination, Chelsea, 1952.
Slide 3
Images are two-dimensional patterns of brightness values. They
are formed by the projection of 3D objects.
Slide 4
Slide 5
How do we perceive depth?
Slide 6
Building large-scale 3D models from photographs Structure from
motionDense multiview stereo Snavely, Seitz, Szeliski, 2007
Vergauwen, Van Gool, 2006 Brown, Lowe, 2005 Schaffalitzky,
Zisserman, 2002 Furukawa, Ponce, 2007 Labatut, Pons, Keriven, 2009
Goesele, et al., 2007
http://phototour.cs.washington.edu/bundler/http://grail.cs.washington.edu/software/pmvs/
Slide 7
Google Maps Photo Tour Lucasfilm Weta Digital ( Bath &
Burke, Weta Digital, Siggraph11) PMVS
(http://www.di.ens.fr/pmvs)
Slide 8
A model built from 25,000 photos (Ubelmann, Dessales, Ponce,
2013)
Slide 9
What is a camera? x
Slide 10
What is a camera? x
Slide 11
What is a camera? x x c r y
Slide 12
x c r y c
Slide 13
x c r y x c
Slide 14
x c r y x c
Slide 15
x c r y x r y Linear family of lines x x c
Slide 16
Rank-4 (nondegenerate) families: Linear congruences Figures H.
Havlicek, VUT
Slide 17
Building a parabolic camera (Batog, Goaoc, Lavandier, Ponce,
2010)
Slide 18
Koenderink (1984) Solid shapes and their outlines
Slide 19
What does the occluding contour tell us about shape? (Marr
& Nishihara, 1978; Koenderink, 1984)
Slide 20
What does the occluding contour tell us about shape? (Marr
& Nishihara, 1978; Koenderink, 1984)
Slide 21
What does the occluding contour tell us about shape? M. Van
Hemskeerk Picasso Drer
Slide 22
The Geometry of the Gauss Map Gauss sphere Image of parabolic
curve Moving great circle Reprinted from On Computing Structural
Changes in Evolving Surfaces and their Appearance, By S. Pae and J.
Ponce, the International Journal of Computer Vision, 43(2):113-131
(2001). 2001 Kluwer Academic Publishers.
Slide 23
PLAN DU COURS: 1. Introduction gnrale 2. Camras Euclidiennes :
perspective centrale, projection parallle; paramtres intrinsques et
extrinsques; mires et talonnage Euclidien. 3. Camras affines :
lments de gomtrie affine; gomtrie multi vues, analyse du mouvement.
4. Camras projectives : lments de gomtrie projective; gomtrie multi
vues, analyse du mouvement. 5. talonnage Euclidien sans mire : la
conique absolue de Chasles et ses cousines; analyse du mouvement
Euclidien. 6. Camras purement projectives : lments de gomtrie des
droites; camras linaires gnrales . 7. Les surfaces Euclidiennes
lisses et leurs silhouettes : gomtrie diffrentielle descriptive; le
thorme de Koenderink et les graphes d'aspects.
Slide 24
Euclidean Cameras Pinhole perspective projection Orthographic
and weak-perspective models Non-standard models A detour through
sensing country Intrinsic and extrinsic parameters
Slide 25
Animal eye: a looonnng time ago. Pinhole perspective
projection: Brunelleschi, XV th Century. Camera obscura: XVI th
Century. Photographic camera: Niepce, 1816.
Slide 26
Slide 27
Massaccios Trinity, 1425 Pompei painting, 2000 years ago. Van
Eyk, XIV th Century Brunelleschi, 1415
Slide 28
Pinhole Perspective Equation NOTE: z is always negative..
Slide 29
Affine projection models: Weak perspective projection is the
magnification. When the scene relief is small compared its distance
from the Camera, m can be taken constant: weak perspective
projection.
Slide 30
Affine projection models: Orthographic projection When the
camera is at a (roughly constant) distance from the scene, take
m=-1.
Challenge: Illumination What is wrong with these pictures?
Slide 40
Photography (Niepce, La Table Servie, 1822) Milestones:
Daguerrotypes (1839) Photographic Film (Eastman, 1889) Cinema
(Lumire Brothers, 1895) Color Photography (Lumire Brothers, 1908)
Television (Baird, Farnsworth, Zworykin, 1920s) CCD Devices
(1970)
Slide 41
Image Formation: Radiometry What determines the brightness of
an image pixel? The light source(s) The surface normal The surface
properties The optics The sensor characteristics
Slide 42
Quantitative Measurements and Calibration Euclidean
Geometry
Slide 43
Euclidean Coordinate Systems
Slide 44
Planes
Slide 45
Coordinate Changes: Pure Translations O B P = O B O A + O A P,
B P = A P + B O A
Slide 46
Coordinate Changes: Pure Rotations
Slide 47
Coordinate Changes: Rotations about the z Axis
Slide 48
A rotation matrix is characterized by the following properties:
Its inverse is equal to its transpose, and its determinant is equal
to 1. Or equivalently: Its rows (or columns) form a right-handed
orthonormal coordinate system.
Slide 49
Coordinate Changes: Pure Rotations
Slide 50
Coordinate Changes: Rigid Transformations
Slide 51
Cameras and their parameters
Slide 52
Pinhole Perspective Equation
Slide 53
The Intrinsic Parameters of a Camera Normalized Image
Coordinates Physical Image Coordinates Units: k,l : pixel/m f : m :
pixel
Slide 54
The Intrinsic Parameters of a Camera Calibration Matrix The
Perspective Projection Equation
Slide 55
The Extrinsic Parameters of a Camera p M P
Slide 56
Explicit Form of the Projection Matrix Note: M is only defined
up to scale in this setting!!
Slide 57
Theorem (Faugeras, 1993)
Slide 58
Calibration Problem
Slide 59
Linear Camera Calibration
Slide 60
Linear Systems A A x xb b = = Square system: unique solution
Gaussian elimination Rectangular system ?? underconstrained:
infinity of solutions Minimize |Ax-b| 2 overconstrained: no
solution
Slide 61
How do you solve overconstrained linear equations ??
Slide 62
Homogeneous Linear Systems A A x x0 0 = = Square system: unique
solution: 0 unless Det(A)=0 Rectangular system ?? 0 is always a
solution Minimize |Ax| under the constraint |x| =1 2 2
Slide 63
How do you solve overconstrained homogeneous linear equations
?? The solution is e. 1 E(x)-E(e 1 ) = x T (U T U)x-e 1 T (U T U)e
1 = 1 1 2 + + q q 2 - 1 > 1 ( 1 2 + + q 2 -1)=0
Slide 64
Example: Line Fitting Problem: minimize with respect to
(a,b,d). Minimize E with respect to d: Minimize E with respect to
a,b: where Done !! n
Slide 65
Note: Matrix of second moments of inertia Axis of least
inertia
Slide 66
Linear Camera Calibration Linear least squares for n > 5
!
Slide 67
Once M is known, you still got to recover the intrinsic and
extrinsic parameters !!! This is a decomposition problem, not an
estimation problem. Intrinsic parameters Extrinsic parameters
Slide 68
Degenerate Point Configurations Are there other solutions
besides M ?? Coplanar points: ( )=( ) or ( ) or ( ) Points lying on
the intersection curve of two quadric surfaces = straight line +
twisted cubic Does not happen for 6 or more random points!
Slide 69
Analytical Photogrammetry Non-Linear Least-Squares Methods
Newton Gauss-Newton Levenberg-Marquardt Iterative, quadratically
convergent in favorable situations