Transcript Document

Projective geometry of 2-space
Primitives
pt/line/conic
HZ 2.2
Projective
transform
HZ 2.3
Behaviour
at infinity
Hierarchy of maps
Invariants
HZ 2.4
Rectification
HZ 2.7
DLT alg
HZ 4.1
Computing a homography
•
given 2 images of a scene, we would
like to compute the homography H that
relates their pixels
–
•
H is a 3x3 matrix with 8 dof (9 – 1)
–
•
•
•
•
Hx = x’
how will we solve for these 8 degrees
of freedom?
solve for H using 4 point
correspondences (x1,x1’), ..., (x4,x4’)
–
•
excellent example of the system-ofequations approach to compute a matrix
(the homography) as a null vector
bootstrap from 4 matches to all matches
how will we find 4 point
correspondences? SIFT (later)
can also rectify using these ideas (Fig
2.4)
HZ87-88, HZ35, Figure 4.9a,b
Lessons of DLT
• using SIFT for feature detection and feature
matching
• developing the linear system of equations
appproach
• learning to precondition data
• learning how to solve least squares
– we have learned how to solve for null space
• learning RANSAC
Cross product as matrix
multiplication
• we know that cross product may be interpreted as a determinant
• it is even more useful to interpret it as a skew-symmetric matrix
• a x b = [0
-a2
a1]
[b0]
[a2
0
-a0]
[b1]
[-a1
a0
0]
[b2]
• this is now a matrix multiplication and fits seamlessly into our
algebraic schemes
• we abbreviate this matrix [ax] so that a x b = [ax] b
• cute: a is the null vector of [ax] (there’s no avoiding null space!)
• mnemonic: lower triangle is a2,-a1,a0
• later we will interpret cross product as a tensor!
• HZ581, Appendix A
Reducing H to a null space
•
•
•
•
idea: use Hxi = xi’ to solve for H
Hxi = xi’ (which is not true in projective space; think scale) becomes xi’ x Hxi = 0
let xi’ = (xi’, yi’, wi’), and use the skew-symmetric representation:
xi’ x Hxi = [0
- wi’ yi’] [h1t xi]
[wi’
0 -xi’] [h2t xi]
[-yi’
xi’ 0] [h3t xi]
OR
•
[0 -wi’ yi’] [xit h1]
[wi’ 0 -xi’] [xit h2] = 0
[-yi’ xi’ 0] [xit h3]
•
•
[0 -wi’xit yi’xit] [h1]
[wi’xit 0 -xi’xit] [h2] = 0
[h3]
OR
rd
(having removed the 3 equation, since it is linearly dependent on the others)
Ai h = 0
–
•
OR
where Ai is a 2x9 matrix and h is the row-major unrolling of H
this interprets H as the null vector of a 2x9 matrix
Preamble to DLT algorithm
•
Note: xi’ * row1 + yi’ * row2 = -wi’ * row3
•
DLT (Direct Linear Transformation) algorithm uses this transformation of
point correspondences into a solution for the homography H
Ai h = 0 encodes the restriction xi’ x Hxi = 0 (xi’ and Hxi are equivalent)
•
– but now in the form of a linear system (no cross product, H isolated)
•
•
•
•
set the projective coordinate w = 1 in all of the points
collect 4 of these pt-correspondence matrices Ai, yielding an 8x9 matrix A,
with a one-dimensional null space
solve Ah = 0 for null vector h using SVD (see above)
notice how this reverses the point of view: change the typical “solve Hxi = xi’
for xi“ into “solve Hxi = xi’ for H”
– translate the matrix into a vector by unrolling
•
HZ88-89
DLT algorithm
1.
2.
3.
4.
5.
6.
Find 4 point correspondences between 2 images of the same scene.
Precondition (see below).
Build the matrix Ai from each correspondence (xi , xi’).
Combine A1,...,A4 into A.
Find A’s null vector [see above: last column of V in SVD of A].
This is the homography matrix H (encoded in row-major unrolling)
that maps between the two images.
Preconditioning
•
essential to normalize the images before applying DLT algorithm
•
•
•
•
let {(xi , xi’): i = 1,...,n} be the point correspondences
translate and scale both pointsets
translate centroid of {xi} to origin
scale new {xi} so that average {dist(xi , origin)} = sqrt(2)
– motivation: typical point looks like (1,1)
•
do likewise to {xi’}, but entirely independently
– translate centroid to origin and scale so avg dist from origin is \sqrt(2)
•
this normalization ensures that changes in x, y and w have comparable effect
– e.g., if (100,100,1) is a feature point, changes in w will have 100 times more effect
than changes in x or y
•
HZ107-109
DLT with more than 4
correspondences
• we can solve for the homography using only 4 point correspondences,
but SIFT will typically find many more
• if n>4 point correspondences are known, we can collect them into a
2n-by-9 matrix A
• unless these correspondences are calculated exactly (highly unlikely!),
Ah=0 will not be solvable
• instead, minimize ||Ah|| subject to the constraint ||h||=1
– the constraint is added to avoid the zero solution
• this optimal solution is the last column of V in the singular value
decomposition A = UDV^t
– serendipitously, same technique as original DLT algorithm
• the vector h is reconstructed into H (see above)
• that is, DLT algorithm remains exactly the same with 4 replaced
by n
• HZ90-91, 593
Outliers and noise
• it is better to use all of the computed
correspondences, because some of them will be
unreliable
– cannot guess which 4 are reliable
– can use RANSAC to determine the highly unreliable
correspondences (the outliers)
– then use all of the remaining (still noisy)
correspondences
– when data is noisy, better to use lots of data
• Who wants to be a millionaire? studio audience poll