Fundamentals of Computer Vision
Lecture
Overview of today’s lecture
• Transformations in projective geometry.
• Classification of 2D transformations. Motivation: panoramas.
• Back to warping: image homographies.
• Computing with homographies.
Slide credits
Most of these slides were adapted from:
• Kris Kitani (15-463, Fall 2016), Ioannis Gkioulekas (16-385, Spring 2019), Robert Colin (454, Fall 2019s).
Some slides were inspired or taken from:
• Fredo Durand (MIT).
• James Hays (Georgia Tech).
How to interpret projective transformations here?
image point in pixel coordinates
image plane
image point in heterogeneous coordinates
X is a projection of a point P on the image plane
Determining unknown 2D transformations
Determining unknown transformations
Suppose we have two triangles: ABC and DEF.
• What type of transformation will map A to D, B to E, and C to F?
BE
C
D
A
F
Determining unknown transformations
Suppose we have two triangles: ABC and DEF.
• What type of transformation will map A to D, B to E, and C to F?
• How do we determine the unknown parameters?
BE
A
F
How many degrees of freedom do we have?
C
D
Affine transform: uniform scaling + shearing + rotation + translation
Determining unknown transformations
Suppose we have two triangles: ABC and DEF.
• What type of transformation will map A to D, B to E, and C to F?
• How do we determine the unknown parameters?
BE
C
D
A
F
unknowns
point correspondences
• One point correspondence gives how many equations?
• How many point correspondences do we need?
Determining unknown transformations
Suppose we have two triangles: ABC and DEF.
• What type of transformation will map A to D, B to E, and C to F?
• How do we determine the unknown parameters?
BE
C
D
A
F
How do we solve this for M?
unknowns
point correspondences
Review: Least squares line fitting
•Data: (x1, y1), …, (xn, yn) •Line equation: yi = m xi + b •Find (m, b) to minimize
y=mx+b (xi, yi)
E=ån (y-mx-b)2
i=1
ii
yx1 éùéù
ê1ú ê1 ú Y= ê!ú X=ê! !ú
émù B = êë b úû
êyú êx1ú ënûënû
E= Y-XB2 =(Y-XB)T(Y-XB)=YTY-2(XB)TY+(XB)T(XB)
dE =2XT XB-2XTY =0 dB
Normal equations: least squares solution to XB=Y 𝐵 = (𝑋%𝑋)'(𝑋%𝑌
X T XB = X T Y
Least Squares Error
Euclidean (L2) norm
squared!
predicted location
measured location
Least Squares Error
Residual (projection error)
Find parameters that minimize squared error
General form of linear least squares
(Warning: change of notation. x is a vector of parameters!)
(matrix form)
Determining Unknown Transformations
Affine transformation:
Vectorize transformation parameters:
Stack equations from point correspondences:
Notation in system form:
Solving the linear system
Convert the system to a linear least-squares problem:
Expand the error:
Minimize the error: Set derivative to 0
Solve for x
In Matlab: x =A \ b
Linear least squares estimation only works when the transform function is linear! (duh) Also doesn’t deal well with outliers
Least squares
• Least squares fit to the red points:
Least squares: Robustness to noise?
• Least squares fit with an outlier:
Problem: squared error heavily penalizes outliers
Motivation for Image Alignment: Panoramas.
How do you create a panorama?
Panorama: an image of (near) 360o field of view.
How do you create a panorama?
Panorama: an image of (near) 360o field of view.
1. Useaverywide-anglelens.
How do you create a panorama?
Panorama: an image of (near) 360o field of view.
1. Useaverywide-anglelens.
• Pros: Everything is done optically, single capture.
• Cons: Lens is super expensive and bulky, lots of distortion (can be dealt-
with in post).
Any alternative to this?
How do you create a panorama?
Panorama: an image of (near) 360o field of view.
1. Useaverywide-anglelens.
• Pros: Everything is done optically, single capture.
• Cons: Lens is super expensive and bulky, lots of distortion (can be dealt-
with in post).
2. Capturemultipleimagesandcombinethem.
Panoramas from image stitching
1. Capturemultiple images from different viewpoints.
2. Stitchthemtogether into a virtual wide-angle image.
How do we stitch images from different viewpoints?
Will standard stitching work?
1. Translateoneimagerelativetoanother. 2. (Optionally)findanoptimalseam.
How do we stitch images from different viewpoints?
Will standard stitching work?
1. Translateoneimagerelativetoanother. 2. (Optionally)findanoptimalseam.
left on top
Translation-only stitching is not enough to mosaic these images.
right on top
How do we stitch images from different viewpoints?
What else can we try?
How do we stitch images from different viewpoints?
Use image homographies.
Back to Warping: Image Homographies
Classification of 2D transformations
Euclidean
Similarity Affine
Projective (homography)
Classification of 2D transformations
Which kind of transformation is needed to warp projective plane 1 into projective plane 2?
PP 1
PP3
PP2
Classification of 2D transformations
Which kind of transformation is needed to warp projective plane 1 into projective plane 2?
PP 1
PP3
PP2
• A projective transformation (a.k.a. a homography).
Warping with different transformations
translation affine Projective (homography)
Virtual camera rotations
synthetic rotations
original view
A weird drawing
Holbein, “The Ambassadors”
Holbein, “The Ambassadors”
A weird drawing
What’s this???
Holbein, “The Ambassadors”
A weird drawing
rectified view
skull under anamorphic perspective
Holbein, “The Ambassadors”
A weird drawing
use a polished spoon to see the skull
View Warping: Image rectification
original view synthetic top view
4 3 2 1
p
p’
To unwarp (rectify) an image solve for homography H given pandp’: p’=Hp
Approach: unwarp, then measure
1234
Image Rectification
Two original images
Rectified and stitched
When can we use Homographies?
1. …thesceneis planar;; or
We can use Homographies when…
2. …thesceneisveryfaror has small (relative) depth variation → scene is approximately planar
We can use Homographies when…
3. …thesceneiscapturedundercamerarotationonly(notranslationorpose change)
Panoramas (Mosaic) from image stitching
How to stitch together a panorama?
• Basic Procedure
• Take a sequence of images from the same position • Rotate the camera about its optical center
• Compute the homography (transformation) between second image and first
• Transform the second image to overlap with the first
• Blend the two together to create a mosaic
• (If there are more images, repeat)
Modified from Steve Seitz
Image Reprojection
mosaic PP
• The mosaic has a natural interpretation in 3D
• The images are reprojected onto a common plane
• The mosaic is formed on this plane
• Mosaic is a synthetic wide-angle camera
Source: Steve Seitz
• Basic question
Image reprojection
•
How to relate two images from the same camera center? • how to map a pixel from PP1 to PP2
Answer
• Cast a ray through each pixel in PP1
• Draw the pixel where that ray intersects PP2
PP2
Observation:
Rather than thinking of this as a 3D reprojection, think of it as a 2D image warp from one image to another.
PP1
Source: Alyosha Efros
•
Image reprojection: Homography
A projective transform is a mapping between any two PPs with the same center of projection
•
• rectangle should map to arbitrary quadrilateral
• parallel lines aren’t
• but must preserve straight lines
called Homography
PP2
éwx’ù * * * éxù êúéùêú
êwy’ú = ê* * *úêyú w ê***ú1
PP1
ëûëûëû
p’ H p
Source: Alyosha Efros
Applying a Homography
1. Convert to homogeneous coordinates: 𝑝 = What is the size of the homography matrix?
𝑦𝑥 ⇒ 𝑃 = 𝑦𝑥 1
𝑃1 = 𝐻 ⋅ 𝑃
2. Multiply by the homography matrix:
𝑥1 51
𝑤1 51 𝑤
3. Convert back to heterogeneous coordinates:
𝑥1
𝑃1 = 𝑦1
⇒ 𝑝1 = 𝑦1 𝑤
1.
Applying a Homography
Convert to homogeneous coordinates: 𝑝 = 𝑦𝑥 ⇒ What is the size of the homography matrix?
𝑃 = 𝑦𝑥 1
Answer: 3 x 3
2.
𝑃1 = 𝐻 ⋅ 𝑃
Multiply by the homography matrix:
How many degrees of freedom does the homography matrix have?
Convert back to heterogeneous coordinates:
𝑥1 𝑥1 51
3.
𝑃1 = 𝑦1 ⇒ 𝑝1 = 𝑦1 𝑤
𝑤1 51 𝑤
1.
Applying a Homography
Convert to homogeneous coordinates: 𝑝 = 𝑦𝑥 ⇒ What is the size of the homography matrix?
𝑃 = 𝑦𝑥 1
Answer: 3 x 3
2.
𝑃1 = 𝐻 ⋅ 𝑃
Multiply by the homography matrix:
How many degrees of freedom does the homography matrix have? Answer: 8
Convert back to heterogeneous coordinates:
𝑥1 𝑥1 51
3.
𝑃1 = 𝑦1 ⇒ 𝑝1 = 𝑦1 𝑤
𝑤1 51 𝑤
Applying a Homography
What is the size of the homography matrix? Answer: 3 x 3
𝑃1 = 𝐻 ⋅ 𝑃
How many degrees of freedom does the homography matrix have? Answer: 8
How do we compute the homography matrix?
The Direct Linear Transform (DLT)
𝑝(
𝑝6
𝑝8
𝑝7
𝑝(1 𝑝61
Create point correspondences
Original image
Target image
To compute the homography given pairs of corresponding points in the images, we need to set up an equation where the parameters of H are the unknowns.
𝑃1 = 𝐻 ⋅ 𝑃
Slide credit: Kristen Grauman
We then need to find the best estimate of H such that: How many correspondences do we need?
𝑝81
…
…
Determining the Homography Matrix
Write out linear equation for each correspondence:
𝑃1 = 𝐻 ⋅ 𝑃
or Expand matrix multiplication:
Divide out unknown scale factor:
How do you rearrange terms to make it a linear system?
Just rearrange the terms
Re-write in matrix form:
How many equations from one point correspondence?
Determining the Homography Matrix
Determining the Homography Matrix
Stack together constraints from multiple point correspondences:
Homogeneous linear least squares problem
Determining the Homography Matrix
Stack together constraints from multiple point correspondences:
Homogeneous linear least squares problem • How do we solve this?
Determining the Homography Matrix
Stack together constraints from multiple point correspondences:
Homogeneous linear least squares problem • Solve with SVD
Basic reading:
• Szeliski textbook, Sections 6.1.
References
Additional reading:
• Hartley and Zisserman, “Multiple View Geometry,” Cambridge University Press 2003.
as usual when it comes to geometry and vision, this book is the best reference;; Sections 2 and 4 in particular discuss everything about homography estimation