程序代写代做代考 Image Warping

Image Warping
http://www.jeffrey-martin.com
Many slides are from Alexei Efros (Berkeley) and Steve Seitz (U. of Washington)

CS3335 Visual computing Image Warping
• Parametrictransformations
– Linear transformations of images via 2×2 matrices
(a crash course on basic linear algebra)
– Homographies (3×3 transformation matrices)
• Estimation of parametric transformations (from corresponding points)
• Forwardandinversewarps – bilinear interpolation

Image Warping
image filtering: change range of image
g(x) = T(f(x))
ff xx
image warping: change domain of image g(x) = f(T(x))
ff xx
T
T

Image Warping
image filtering: change range of image g(x) = T(f(x))
fg
image warping: change domain of image g(x) = f(T(x))
T
f
g
T

Parametric (global) warping Examples of parametric warps:
translation rotation
aspect
affine
perspective
cylindrical

Parametric (global) warping
T
p = (x,y) p’ = (x’,y’) Transformation T is a coordinate-changing machine:
What does it mean that T is global?
• Is the same for any point p
• can be described by just a few numbers (parameters)
Let’s represent T as a matrix: p’ = Mp
x’  Mx  y ‘   y 
g(p’)g(Mp) f(p) f(M1p’)

Scaling
Scaling a coordinate means multiplying each of its components by a scalar
Uniform scaling means this scalar is the same for all components:
2

Scaling
Non-uniform scaling: different scalars per component:
X  2, Y  0.5

Scaling
Scaling operation: Or, in matrix form:
x’ax y’by
x’  a 0x  y’ 0 b y
scaling matrix S
What’s inverse of S?

2-D Rotation
(x’, y’)
(x, y)
x’ = x cos() – y sin() y’ = x sin() + y cos()


2-D Rotation
(x’, y’)
(x, y)

x = r cos (f)
y = r sin (f)
x’ = r cos (f + ) y’ = r sin (f + )
Trig Identity…
x’ = r cos(f) cos() – r sin(f) sin() y’ = r cos(f) sin() + r sin(f) cos()
Substitute…
x’ = x cos() – y sin() y’ = x sin() + y cos()
f

2-D Rotation
This is easy to capture in matrix form:
x’cos() sin()x
y’ sin( )
Even though sin() and cos() are nonlinear functions of ,
• x’ is a linear combination of x and y
• y’ is a linear combination of x and y
What is the inverse transformation?
• Rotationby– 1 T
• For rotation matrices R  R
cos( ) y
R

2×2 Matrices
What types of transformations can be represented with a 2×2 matrix?
2D Identity?
x’ x x’  1 y’ y y’ 0
2D Scale around (0,0)?
x’sx *x x’sx y ‘  s y * y  y ‘   0
0x 1y
0x s y   y 

2×2 Matrices
What types of transformations can be represented with a 2×2 matrix?
2D Rotate around (0,0)?
x’  cos  * x  sin  * y y’  sin  * x  cos  * y
2D Shear?
x’ x  shx * y y’shy*xy
x’cos sinx
y’ sin  x’   1
cos y shx x
y’ shy
1y

2×2 Matrices
What types of transformations can be represented with a 2×2 matrix?
2D Mirror about Y axis?
x’ x y’ y
2D Mirror over (0,0)?
x’ x y ‘   y
x’  1 y’  0
0x 1y
x’  1  y ‘   0
0 x  1   y 

2×2 Matrices
What types of transformations can be represented with a 2×2 matrix?
2D Translation?
x’ xtx y’ yty
NO!
Only linear 2D transformations can be represented with a 2×2 matrix

All 2D Linear Transformations
Linear transformations are combinations of …
• Scale,
• Rotation,
• Shear, and
• Mirror
Properties of linear transformations:
• Origin maps to origin
• Lines map to lines
• Parallel lines remain parallel
x’  a  y’ c
bx d  y
• Distance or length ratios are preserved on parallel lines
– scaling of length/distances depends on (line) orientation only (see next slide)
• Ratios of areas are preserved
• Closed under composition
x’  a bi js  y ‘   c d   k l   r
qx t   y 
• See pp. 40-41 of Hartley and Zisserman “Multiple View Geometry” (2nd edition)

All 2D Linear Transformations Decomposition into basic geometric transformations
a b   0  ARR1R
 c d 
     0  2    
rotation by angle 
deformation (non-isotropic scaling)

1
1 f
Scaling directions are always orthogonal.
Areas are scaled (homogeneously over a plane) by a factor of det A = 1 2
2

Linear Transformation as Space Deformation qTp
j =(0,1)
i =(1,0)
p = (4,3)
q
Tp
coordinates of p in basis i,j
qx   ux vx 4 qy  uy vy 3
coordinates of q in basis i,j qqx iqy j
p4i3j point p is transformed into new point q

Linear Transformation as Change of Basis NOTE: q looks just like p
q = (qx,qy)
v =(vx, vy)
relative to coordinate system u,v q =(4,3)
j =(0,1)
i =(1,0)
vx ivy j
now interpret the columns of matrix T
u=(ux,uy)ux iuy j
as some vectors u and v (their coordinates in basis i, j)
qx   ux vx 4 qy  uy vy 3
coordinates of q in basis i,j
qqx iqy j ? q4u3v
qy Indeed, q4(ux iuy j)3(vx ivy j)  (4ux 3vx)i(4uy 3vy)j
u v qx
coordinates of q in basis u,v

Linear Transformation as Change of Basis
T
q = (qx,qy)
v =(vx, vy)
q =(4,3)
j =(0,1)
i =(1,0)
vx ivy j
now interpret the columns of matrix T
coordinates of q in basis i,j qqx iqy j
u=(ux,uy)ux iuy j
as some vectors u and v (their coordinates in basis i, j)
coordinates of q in basis u,v ? q4u3v
qx   ux vx 4 qy  uy vy 3
point q represented in different coordinate systems

Linear Transformation as Change of Basis
T
q = (qx,qy)
v =(vx, vy)
q =(4,3)
j =(0,1)
i =(1,0)
vx ivy j
now interpret the columns of matrix T
u=(ux,uy)ux iuy j
as some vectors u and v (their coordinates in basis i, j)
qx   ux vx 4 qy  uy vy 3
Any matrix can be seen as a (linear) coordinate system basis!!!
Question: What’s the inverse matrix T-1 ? 4  ? ?qx  3 ? ?qy 

Linear Transformation as Change of Basis
-1 T
q = (qx,qy)
v =(vx, vy)
q =(4,3)
j =(0,1)
i =(1,0)
vx ivy j
now interpret the columns of matrix T
u=(ux,uy)ux iuy j
as some vectors u and v (their coordinates in basis i, j)
Any matrix can be seen as a (linear) coordinate system basis!!!
Question: What’s the inverse matrix T-1 ?
4  ix 3 iy
jx qx  jy qy 
coordinates of i and j in basis u,v
iix uiy v j jx u jy v
qx   ux vx 4 qy  uy vy 3

Linear Transformation as Change of Basis
q
T=?
q
j =(0,1)
v =(vx, vy)
u =(ux, uy)
i =(1,0)
Any matrix can be seen as a (linear) coordinate system basis!!! Question: What if both coordinate systems have ortho-normal basis?

Linear Transformation as Change of Basis
q
T=R
q
j =(0,1)
v =(vx, vy)
u =(ux, uy)
i =(1,0)
Any matrix can be seen as a (linear) coordinate system basis!!!
Question: What if both coordinate systems have ortho-normal basis? Then as a linear transformation matrix T represents rotation

Homogeneous Coordinates
Q: Can we represent translation by matrix multiplication?
x’ xtx y’ yty
very simple, but
not a linear transformation
for 2D points p T ( p  q)  T ( p)  T (q)
T(p)  T(p) Answer: Yes, using homogeneous coordinates and 3×3 matrices
Homogeneous coordinates
• represent coordinates in 2 dimensions with a 3-vector
 y’  0 1 t y  yt 
x’ 1 0 tx x
xtx
yy
1 0 0 1 1  1 
  Translation     matrix (3×3)
x homogeneous x coordinates  
 y  y 1

Translation Example of translation
Homogeneous Coordinates
x’ 1 0 txx xtx y’0 1 t yyt 
1 0 0 11  1   
yy
tx = 2 ty = 1

Homogeneous Coordinates (in general)
Add a 3rd coordinate to every 2D point
• (x, y, w) represents a point at location (x/w, y/w) • (0, 0, 0) is not allowed
Advantages of homogeneous coordinate system:
y
2 1
12
(2,1,1) or (4,2,2) or (6,3,3)
x
(w2,w1,w)
represent the same 2D point for any value of w
– simple matrix representation of many useful transformations

Homogeneous Coordinates (in general)
Add a 3rd coordinate to every 2D point
• (x, y, w) represents a point at location (x/w, y/w) • (0, 0, 0) is not allowed
• (x, y, 0) represents a point at infinity
Advantages of homogeneous coordinate system:
y
2 1
12
( 2 , 1 , 14 ) ( 2 , 1 , 12 )
(2,1,1)
x
– simple matrix representation of many useful transformations
-allowstoexpandR2 with“pointsatinfinity” (like R1 could be expanded with   )

Basic 2D Transformations Basic 2D transformations as 3×3 matrices
x’ 1 0 txx y’  0 1 ty y
1 0 0 11     
Translate
x’ cos sin 0x y’  sin  cos 0y
10 0 11     
Rotate
x’ sx 0 0x y’   0 sy 0y 1 0 0 11
Scale
x’ 1 shx 0x y’  shy 1 0y
1 0 0 11     
Shear
  
 

Affine Transformations
Affine transformations are combinations of … • Linear 2D transformations, and
• Translations
Properties of affine transformations:
• Origin does not necessarily map to origin
x’ a b cx y’d e fy
w 0 0 1w
• Lines map to lines
• Parallel lines remain parallel
• Length/distance ratios are preserved on parallel lines
• Ratios of areas are preserved
• Closed under composition

Affine Transformations
Example of a composition of basic transformations
x’ 1 0 txcos sin 0sx 0 0x y’0 1 tysin cos 00 sy 0y w’0010 01001w
   
  
p’ = T(tx,ty)
R()
S(sx,sy) p

Projective Transformations (a.k.a. homographies) transformations in homogeneous coordinate space via general 3×3 matrices
Projective transformations …
• Affine transformations, and
• Projective warps
Properties of projective transformations:
• Origin does not necessarily map to origin
x’ a b cx y’d e fy
w’ g h i 1     
• Lines map to lines indeed, points p (in hom. coord.) on a line are a∙p=0. Then, b∙Hp=0 for b=aH-1
• Parallel lines do not necessarily remain parallel
• Non-parallel lines may become parallel
• Distance/length or area ratios are not preserved
• Closed under composition
• Models change of basis

Projective Transformations (a.k.a. homographies)
• •
Parallel lines do not necessarily remain parallel Non-parallel lines may become parallel
H
3 a b c6 2   d e f 5
0 1 1 11   
(3,2,0)
y
(6,5,1) y x?x
(3,2,1)
NOTE: “finite” point may transform to “point at infinity”

Projective Transformations (a.k.a. homographies)
• •
Parallel lines do not necessarily remain parallel
Non-parallel lines may become parallel
H-1
12 a’ b’ c’3 10d’ e’ f’2
 2  g’ h’   
i’ 0  
(3,2,0)
y
(6,5,1) y x?x
(3,2,1)
NOTE: or “point at infinity” may transform to “finite” point

Projective Transformations
• Distance/length or area ratios are not preserved
(a.k.a. homographies)
A’
(3,2,0)
B’
C’ ?
xx
3 a b c6 2  d e f 5 0 g h i1
  
 
yAy (6,5,1)
B C
(3,2,1)
Example: distance |B’C’| remains finite, while |A’B’| is infinite

Projective Transformations (a.k.a. homographies) General property to keep in mind (Theorem 2.10 from Hartley&Zisserman)
An invertible mapping h from a (homogeneous) plane P2 onto P2 preserves straight lines iff there exists a non-singular 3×3 matrix H s.t.
for any x2
That is, any transformation of a plane onto a plane that preserves straight lines must be a homography.
h( x )  H  x

2D image transformations
These transformations are a nested set of groups
• Closed under composition and inverse is a member
See Hartley and Zisserman,
p. 44

Remaining parts of this lecture
• Estimation of parametric transformations (from corresponding points)
• Forward and inverse warps

Recovering Parametric Transformations
?
T(x,y) y y’
x f(x,y) x’ g(x’,y’)
What if we know f and g and want to recover transform T?
• e.g. to better align images (image registration)
• willing to let user provide correspondences
Q: How many pairs of corresponding points do we need?

Translation: # correspondences?
?
T(x,y) y y’
x x’
How many correspondences needed for translation? How many Degrees of Freedom (DOF)?
What is the transformation matrix?
1 0 cp’p
 
xxx  
M M   0 0 1 1 cp ‘  p yyy
 
0 0 11   

Euclidian: # correspondences?
?
T(x,y) y y’
x x’
How many correspondences needed for translation+rotation? How many DOF?
Transformation matrix?
cos sin cx
M  sin cos cy 
001 

Affine: # correspondences?
?
T(x,y) y y’
x x’
How many correspondences needed for affine? How many DOF?
Transformation matrix?
Geometric point of view:
a b c
Mc d f
0 0 1 
??? perhaps 3 pairs specifying a maps for 2 lines should be enough to define an affine transform

Algebraic point of view
p’i M pi 
p’i M pi x’i a b cxi
for any given pair of corresponding points
(pi,p’i ) 6 unknown
parameters (variables)
y’id e fyi 1 0 0 11
  xax by c
iii
y  dx  ey  f iii
gives with known point coordinates for pi and p’i
3 pairs of corresponding points give 3×2 (=6) linear equations allowing to resolve 6 unknown parameters
Each pair of corresponding points (pi ,p’i )
two linear equations w.r.t 6 unknown coefficients of matrix M

Affine: # correspondences?
?
T(x,y) y y’
x x’
How many correspondences needed for affine?
How many DOF? Transformation matrix?
=3
gives 3×2 (6) equations for 6 unknowns
a b c
Mc d f
0 0 1 

Projective: # correspondences?
?
T(x,y) y y’
x x’
=4
Easy to check that 4 pairs give only 4×2 (=8) equations! What about 9 unknowns?
a b c
How many correspondences needed for projective?
How many DOF? Transformation matrix?
Homographies have only 8 DOF since scale is irrelevant (multiplying M by any factor does not change the actual transformation). To choose one unique matrix M we can fix one parameter (e.g. i=1)
or restrict matrix norm ||M||F =1 (the sum of squares of all entries). Either way, one can get one additional (9th) constraint for parameters of M.
Md e f
g h i  

Example: warping triangles
B
B’
?
T(x,y)
Given two triangles: ABC and A’B’C’ in 2D (3 corresponding pairs)
Need to find (linear) transform T to transfer all pixels from one to the other.
(affine)
a b c
Mc d f
0 0 1 
A Source C
C’
What kind of transformation is T?
How can we compute the transformation matrix?
(solve 6 linear equations with 6 unknons)
A’ Destination

Image warping
T(x,y) y y’
x f(x,y) x’ g(x’,y’)
Given a coordinate transform (x’,y’) = T(x,y) and a source image f(x,y), how do we compute a transformed image g(x’,y’) = f (x,y)?

Forward warping
T(x,y) y y’
x f(x,y) x’ g(x’,y’)
Send each pixel (x,y) in the first image to its corresponding
location (x’,y’) = T(x,y) in the second image Q: what if pixel lands “between” two pixels?

Inverse warping
-1
T (x,y)
y y’
x f(x,y) x’ g(x’,y’)
Get each pixel (x’,y’) in the second image from its corresponding location (x,y) = T-1(x’,y’) in the first image
Q: what if pixel comes from “between” two pixels?

Linear interpolation in vector spaces
Q
Any point between P and Q can be obtained as a linear combination
 P + (1) Q
v=Q-P
P
e.g.
P + 0.5(Q – P)
P + 0.5v =
= 0.5P + 0.5 Q

Linear interpolation for functions
Assume 1D image (scan line) with intensity f(P) and f(Q) for 2 pixels P and Q
Linear interpolation of function f between P and Q:
f
f(P)
f( P + (1) Q) f(Q)
f(  P + (1) Q ) =  f(P) + (1) f(Q)
PQ
 P + (1) Q

Bilinear interpolation (2 variate image intensity function) Sampling of f at (x,y):
1-a
a
1-a
a
(i, j+1)
(i+1, j+1)
a
b
(x, y)
(i, j)
pixels viewed as points in 2D
(i+1, j)
pixels viewed as square regions in 2D
Interpolated intensity at (x,y) can be seen as a weighted average of 4 near-by pixels intensities where weights based on overlap area

Forward vs. inverse warping Q: which is better?
A: usually inverse—eliminates holes
•however, it requires an invertible warp function—not always possible…
x’
x’
x
x
?
3 pixels
12 pixels

Related Posts