Homographies

Prévia do material em texto

2D Homographies 
 
 
 
 
Raul Queiroz Feitosa 
3/19/2013 2D Homographies 2 
Objective 
 
 
 To introduce the problem of estimating 
2D projective transformations as well 
as some basic tools for parameter 
estimation. 
 
3/19/2013 2D Homographies 3 
Outline 
 Motivation 
 Direct Linear Transformation (DLT) 
 Normalization 
 Robust Estimation 
 Non Linear Method 
 Assignment 
 
3/19/2013 2D Homographies 4 
Motivation: Panoramas 
3/19/2013 2D Homographies 5 
Building a Panorama 
 Step 1: find pairs of corresponding points 
p1 
p'2 p2 
p' p1 
p'i pi 
p'n 
pn 
p'j 
pj 
3/19/2013 2D Homographies 6 
Building a Panorama 
 Step 2: Estimate the matrix H (the homography) such 
that 
pi =H p'i 
 
 where pi and p'i are homogeneous vectors representing 
corresponding points, i.e. 
 
k ( ui vi 1 )
T =H( u'i v'i 1 )T 
 
 for some k≠0 (homogeneous) and for all 1≤ i≤ n. 
3/19/2013 2D Homographies 7 
Building a Panorama 
 Step 3: transform geometrically one image by 
using the matrix H 
3/19/2013 2D Homographies 8 
Building a Panorama 
 Step 4: align and blend (not here) the images 
3/19/2013 2D Homographies 9 
Outline 
 Motivation 
 Direct Linear Transformation (DLT) 
 Normalization 
 Robust Estimation 
 Non Linear Method 
 Assignment 
 
3/19/2013 2D Homographies 10 
Direct Linear Transformation 
Derivation: 
Let hj
T be the j-th row of H , so we may write 
 
 
 
 
Clearly . Thus 














i
T
i
T
i
T
i
p
p
p
p
3
2
1
h
h
h
H
0
hh
hh
hh















i
T
ii
T
i
i
T
ii
T
i
T
i
T
i
ii
vu
u
v
pp
pp
pp
pp
12
31
23
H
0
ii
pp H
T
T
T
hhh
hhh
hhh
3
2
1
987
654
321
 
h
h
h













H
3/19/2013 2D Homographies 11 
Direct Linear Transformation 
Derivation (cont.): 
After some manipulation, you obtain 
 
 
 
 
 
 
where 
0
h
h
h
0
0
0
























3
2
1
TT
ii
T
ii
i
T
ii
TT
i
i
T
ii
T
i
T
uv
u
v
pp
pp
pp






















987
654
321
3
2
1
 ,
hhh
hhh
hhh
H
h
h
h
h
3 
9 
3/19/2013 2D Homographies 12 
Direct Linear Transformation 
Derivation (cont.): 
Each pair of points generates two equations of the form 
 
 
 
With n pairs we get 2n equations on 9 unknowns! 
 
 4 pairs of points are enough! 
 
0
h
h
h
0
0




















3
2
1
T
ii
TT
i
T
ii
T
i
T
i
u
v
pp
pp

0
h
h
h





















3
2
11
n



3/19/2013 2D Homographies 13 
Outline 
 Motivation 
 The Direct Linear Transformation (DLT) 
 Normalization 
 Robust Estimation 
 Optimal Estimation 
 Assignment 
 
3/19/2013 2D Homographies 14 
Normalization 
 For improved estimation it is essential† for DLT 
to normalize the data sample, as follows 
1. The points are translated so that their centroid is at the origin 
2. The points are scaled so that the average distance from the 
origin is equal to . 
3. This transformation is applied to each of the two images 
independently. 
 
 
 
 †Multiple View Geometry in computer vision, 2nd Ed., R. Hartley and A. Zisserman, 2003, Cambridge, section 4.4.4, pp.107. 
2
. . . . . . . . . 
. . . . . . .
 . . . .
 
u 
v 
3/19/2013 2D Homographies 15 
Normalization 
 Normalization is carried out by multiplying the 
data vector by proper matrices T and T' 
 
 
 DLT is applied to to obtain , 
which is actually different from . 
 
 
iiii
pppp  
~
 and 
~
TT
 
~
H
ii
pp
~
 and 
~ 
H 
 
~~
 
1
iii
pppp 

TTTT HH
H 
3/19/2013 2D Homographies 16 
Normalization 
 The normalizing matrix T is given by 
 
 
 
 where are the mean values of ui ,vi respectively 
 
 and 
 
 The computation of T' is analogous. 
 
/100
10
01













s
v
u
sT
vu ,
    


n
i
ii
vvuuns
1
2
1
22
2
3/19/2013 2D Homographies 17 
Normalization 
 Step-by-step 
 Compute the normalization matrices T and T' 
 Perform normalization by computing 
 
 
 Apply DLT to and compute 
 
 Denormalize the result by computing 
 
 
 
~
H
iiii
pppp  
~
 and 
~
TT
TT  HH
~
 
-1
ii
pp
~
 and 
~ 
3/19/2013 2D Homographies 18 
Outline 
 Motivation 
 The Direct Linear Transformation (DLT) 
 Normalization 
 Robust Estimation 
 Non Linear Method 
 Assignment 
 
3/19/2013 2D Homographies 19 
Robust Estimation 
RANSAC robust estimation 
1. Repeat for k iterations 
a) Select a random sample of 4 pairs of corresponding points 
and compute H. 
b) Calculate for each putative correspondence the “distance”, 
d (pi,Hp'i ) =|| pi - Hp'i || 
 from the projected to the actual point position. 
c) Determine the number of inliers consistent with H i.e., 
 d (pi,Hp'i ) < t pixels. 
 
2. Choose the Hwith the largest number of inliers. 
3. Recompute H with the inliers. 
3/19/2013 2D Homographies 20 
Robust Estimation 
The geometric distance 
 It is the distance between the projected and the actual 
position of the corresponding points 
 
 
 
 
 
d (pi,Hp'i ) =|| pi - Hp'i|| 
H
p'i 
pi 
H p'i 
image 1 image 2 
d (pi,Hp'i ) 
3/19/2013 2D Homographies 21 
Outline 
 Motivation 
 The Direct Linear Transformation (DLT) 
 Normalization 
 Robust Estimation 
 Non Linear Method 
 Assignment 
 
3/19/2013 2D Homographies 22 
Non Linear Method 
 Reprojection error 
 Sum of the squared errors of the forward and the 
backward transformation, i.e., 
 
 
 
2
1-2
iiiii
D p-pp-p HH 
H
H-1 ii
p-p
-1
H
ii
p-p H
p'i 
pi 
H p'i H-1pi 
image 1 image 2 
3/19/2013 2D Homographies 23 
Non Linear Method 
 Computing H from the reprojection error 
 By finding a solution that minimizes the sum of 
reprojection errors of all n correspondences, i.e., if 
 
 the homography is obtained by solving the non linear 
equation system below 
 
 
 
2
1-2
iiiii
D p-pp-p HH 
0D 













n
D
D
D

2
1
3/19/2013 2D Homographies 24 
Panorama Example 
 Input Images 
 
 
 
 Panorama 
 
3/19/2013 2D Homographies 25 
Outline 
 Motivation 
 The Direct Linear Transformation (DLT) 
 Normalization Robust Estimation 
 Non Linear Method 
 Assignment 
 
 
3/19/2013 2D Homographies 26 
Assignment 
General Formulation 
i. Take a set of images of the same scene, rotating the 
camera around its optical center. 
ii. For a pair of images collect manually a set of 
corresponding points (hint: use the function 
captura_pontos). 
iii. Compute the homography H from these 
correspondences. 
iv. Create a panorama from both images and from H. 
(hint: use the function Panorama2). 
v. Add new images by repeating steps i to iv. 
3/19/2013 2D Homographies 27 
Assignment 
Assignment 1 
1. Write a MATLAB program that implements the 
solution for the problem formulated in the previous 
slide 
i. By using DLT without normalization 
ii. By using DLT with normalization (hint: use the function 
NormalizaPontos) 
 Compare the results obtained by each approach. 
 
3/19/2013 2D Homographies 28 
Assignment 
Assignment 1 (cont.) 
1. Your main task here is the development of a function 
that implements DLT, which may have the following 
help 
 
% H=DLT(u2Trans,v2Trans,uBase,vBase,) 
% Computes the homography H applying the Direct Linear Transformation 
% The transformation is such that 
% p = H p' 
% (uBase vBase 1)'=H*(u2Trans v2Trans 1)' 
% 
% INPUTS: 
% u2Trans, v2Trans - vectors with coordinates u and v of the image to be transformed (p') 
% uBase, vBase - vectors with coordinates u and v of the base image p 
% 
% OUTPUT 
% H - 3x3 matrix with the Homography 
% 
% your name - date 
3/19/2013 2D Homographies 29 
Assignment 
Assignment 2 
2. Provide a new solution for the same general problem 
where DLT is replaced by the non linear method. 
 Some hints: 
 use the MATLAB function lsqnonlin. 
 the result of H p'i is in homogeneous coordinates, i.e., it 
must be scaled to make the third vector component equal 
1, and to obtain the actual column-row coordinates. 
 
3/19/2013 2D Homographies 30 
Assignment 
Assignment 3 
3. Provide a new solution for the same general problem 
where DLT/ the non linear method is replaced by 
RANSAC. 
 Some hints: 
 use DLT to obtain a initial solution 
 Use the reprojection error in RANSAC step 3 (you have it 
from previous assignment) 
3/19/2013 2D Homographies 31 
Next Topic 
 
Image Matching