Transcript PPT - UNC Computer Science

Image alignment
Image from http://graphics.cs.cmu.edu/courses/15-463/2010_fall/
A look into the past
http://blog.flickr.net/en/2010/01/27/a-look-into-the-past/
A look into the past
Leningrad during the blockade
http://komen-dant.livejournal.com/345684.html
Bing streetside images
http://www.bing.com/community/blogs/maps/archive/2010/01/12/new-bingmaps-application-streetside-photos.aspx
Image alignment: Applications
Panorama stitching
Recognition
of object
instances
Image alignment: Challenges
Small degree of overlap
Intensity changes
Occlusion,
clutter
Image alignment
• Two families of approaches:
• Direct (pixel-based) alignment
– Search for alignment where most pixels agree
• Feature-based alignment
– Search for alignment where extracted features agree
– Can be verified using pixel-based alignment
Alignment as fitting
• Previous lectures: fitting a model to features in one image
M
xi
Find model M that minimizes
 residual ( x , M )
i
i
Alignment as fitting
• Previous lectures: fitting a model to features in one image
M
Find model M that minimizes
xi
 residual ( x , M )
i
i
• Alignment: fitting a model to a transformation between
pairs of features (matches) in two images
xi
T
x'i
Find transformation T
that minimizes
 residual (T ( x ), x)
i
i
i
2D transformation models
• Similarity
(translation,
scale, rotation)
• Affine
• Projective
(homography)
Let’s start with affine transformations
• Simple fitting procedure (linear least squares)
• Approximates viewpoint changes for roughly planar
objects and roughly orthographic cameras
• Can be used to initialize fitting for more complex
models
Fitting an affine transformation
• Assume we know the correspondences, how do we
get the transformation?
( xi , yi )
 xi   m1
 y   m
 i  3
m2   xi   t1 
 



m4   yi  t2 
( xi, yi)

x
 i
0


yi
0

0 0
xi yi

 m1 
 
 m2  
1 0  m3   xi 
 
0 1 m4   yi 
   
 t1

 
 t 2 
Fitting an affine transformation

x
 i
0


yi
0

0 0
xi yi

 m1 
 
 m2  
1 0  m3   xi 
 
0 1 m4   yi 
   
 t1

 
 t 2 
• Linear system with six unknowns
• Each match gives us two linearly independent
equations: need at least three to solve for the
transformation parameters
Fitting a plane projective transformation
• Homography: plane projective transformation
(transformation taking a quad to another arbitrary
quad)
Homography
• The transformation between two views of a planar
surface
• The transformation between images from two
cameras that share the same center
Application: Panorama stitching
Source: Hartley & Zisserman
Fitting a homography
• Recall: homogeneous coordinates
Converting to homogeneous
image coordinates
Converting from homogeneous
image coordinates
Fitting a homography
• Recall: homogeneous coordinates
Converting to homogeneous
image coordinates
Converting from homogeneous
image coordinates
• Equation for homography:
 x  h11 h12




  y   h21 h22
 1  h31 h32
h13   x 



h23   y 
h33   1 
Fitting a homography
• Equation for homography:
 xi   h11 h12
  yi   h21 h22
 1  h31 h32
h13   xi 
h23   yi 
h33   1 
 xi  H xi
xi  H xi  0
T
T
T
 xi  h1 x i   yi h 3 x i  h 2 x i 
 y   hT x    hT x  x hT x 
 i  2 i  1 i i 3 i 
 1  hT3 x i   xi hT2 x i  yi h1T x i 
 0T
 T
 xi
 yi xTi

 xTi
0T
xi xTi
yi xTi  h1 
 
T
 xi x i  h 2   0
0T  h 3 
3 equations,
only 2 linearly
independent
Direct linear transform
0T
 T
x1

 T
0
 xT
 n
 y1 x1T 
T
T 
0
 x1 x1  h1 
 

  h 2   0
T
T 
x n  yn x n  h 3 
T
T

0  xn x n 
x1T
Ah  0
• H has 8 degrees of freedom (9 parameters, but scale
is arbitrary)
• One match gives us two linearly independent
equations
• Four matches needed for a minimal solution (null
space of 8x9 matrix)
• More than four: homogeneous least squares