Lecture 1: Images and image filtering
What is the geometric relationship between these two images?
?
Answer: Similarity transformation (translation, rotation, uniform scale)
Slide set from Noah Snavely
What is the geometric relationship between these two images?
?
2
Image alignment
Why don’t these image line up exactly?
What is the geometric relationship between these two images?
Very important for creating mosaics!
First, we need to know what this transformation is.
Second, we need to figure out how to compute it using feature matches.
Richard Szeliski
Image Stitching
5
Image Warping
image filtering: change range of image
g(x) = h(f(x))
image warping: change domain of image
g(x) = f(h(x))
f
x
h
g
x
f
x
h
g
x
5
Richard Szeliski
Image Stitching
6
Image Warping
image filtering: change range of image
g(x) = h(f(x))
image warping: change domain of image
g(x) = f(h(x))
h
h
f
f
g
g
6
Richard Szeliski
Image Stitching
7
Parametric (global) warping
Examples of parametric warps:
translation
rotation
aspect
7
Parametric (global) warping
Transformation T is a coordinate-changing machine:
p’ = T(p)
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 consider linear xforms (can be represented by a 2×2 matrix):
T
p = (x,y)
p’ = (x’,y’)
Common linear transformations
Uniform scaling by s:
(0,0)
(0,0)
Common linear transformations
Rotation by angle θ (about the origin)
(0,0)
(0,0)
What is the inverse?
For rotations:
θ
2×2 Matrices
What types of transformations can be
represented with a 2×2 matrix?
2D mirror about Y axis?
2D mirror across line y = x?
What types of transformations can be
represented with a 2×2 matrix?
2D Translation?
Translation is not a linear operation on 2D coordinates
NO!
2×2 Matrices
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
Ratios are preserved
Closed under composition
Homogeneous coordinates
Trick: add one more coordinate:
homogeneous image
coordinates
Converting from homogeneous coordinates
x
y
w
(x, y, w)
w = 1
(x/w, y/w, 1)
homogeneous plane
Translation
Solution: homogeneous coordinates to the rescue
Affine transformations
any transformation represented by a 3×3 matrix with last row [ 0 0 1 ] we call an affine transformation
Basic affine transformations
Translate
2D in-plane rotation
Shear
Scale
Affine Transformations
Affine transformations are combinations of …
Linear transformations, and
Translations
Properties of affine transformations:
Origin does not necessarily map to origin
Lines map to lines
Parallel lines remain parallel
Ratios are preserved
Closed under composition
Where do we go from here?
affine transformation
what happens when we mess with this row?
Projective Transformations aka Homographies aka Planar Perspective Maps
Called a homography
(or planar perspective map)
Homographies
What happens when the denominator is 0?
Points at infinity
Image warping with homographies
image plane in front
image plane below
black area
where no pixel
maps to
Homographies
Homographies
Homographies …
Affine transformations, and
Projective warps
Properties of projective transformations:
Origin does not necessarily map to origin
Lines map to lines
Parallel lines do not necessarily remain parallel
Ratios are not preserved
Closed under composition
26
2D image transformations
These transformations are a nested set of groups
Closed under composition and inverse is a member
Implementing image warping
Given a coordinate xform (x’,y’) = T(x,y) and a source image f(x,y), how do we compute an xformed image g(x’,y’) = f(T(x,y))?
f(x,y)
g(x’,y’)
x
x’
T(x,y)
y
y’
28
Forward Warping
Send each pixel f(x) to its corresponding location (x’,y’) = T(x,y) in g(x’,y’)
f(x,y)
g(x’,y’)
x
x’
T(x,y)
What if pixel lands “between” two pixels?
y
y’
29
Forward Warping
Send each pixel f(x,y) to its corresponding location x’ = h(x,y) in g(x’,y’)
f(x,y)
g(x’,y’)
x
x’
T(x,y)
What if pixel lands “between” two pixels?
Answer: add “contribution” to several pixels, normalize later (splatting)
Can still result in holes
y
y’
30
Inverse Warping
Get each pixel g(x’,y’) from its corresponding location (x,y) = T-1(x,y) in f(x,y)
f(x,y)
g(x’,y’)
x
x’
T-1(x,y)
Requires taking the inverse of the transform
What if pixel comes from “between” two pixels?
y
y’
31
Inverse Warping
Get each pixel g(x’) from its corresponding location x’ = h(x) in f(x)
What if pixel comes from “between” two pixels?
Answer: resample color value from interpolated (prefiltered) source image
f(x,y)
g(x’,y’)
x
x’
y
y’
T-1(x,y)
32
Interpolation
Possible interpolation filters:
nearest neighbor
bilinear
bicubic
sinc
Needed to prevent “jaggies”
and “texture crawl”
(with prefiltering)
33
Computing transformations
Given a set of matches between images A and B
How can we compute the transform T from A to B?
Find transform T that best “agrees” with the matches
Computing transformations
?
Simple case: translations
How do we solve for
?
Mean displacement =
Simple case: translations
Displacement of match i =
Another view
System of linear equations
What are the knowns? Unknowns?
How many unknowns? How many equations (per match)?
Another view
Problem: more equations than unknowns
“Overdetermined” system of equations
We will find the least squares solution
Least squares formulation
For each point
we define the residuals as
Least squares formulation
Goal: minimize sum of squared residuals
“Least squares” solution
For translations, is equal to mean (average) displacement
Least squares formulation
Can also write as a matrix equation
2n x 2
2 x 1
2n x 1
Least squares
Find t that minimizes
To solve, take derivative w.r.t. t and equate to 0
43
Least squares: linear regression
y = mx + b
(yi, xi)
Linear regression
residual error
Linear regression
Affine transformations
6 unknowns
2 equations per matched points
Affine transformations
Residuals:
Cost function:
Affine transformations
Matrix form
2n x 6
6 x 1
2n x 1
Homographies
To unwarp (rectify) an image
solve for homography H given p and p’
solve equations of the form: wp’ = Hp
linear in unknowns: w and coefficients of H
H is defined up to an arbitrary scale factor
p
p’
50
Solving for homographies
Not linear!
51
Solving for homographies
Solving for homographies
Defines a least squares problem:
Since is only defined up to scale, solve for unit vector
Solution: = eigenvector of with smallest eigenvalue
Works with 4 or more points
2n × 9
9
2n
53
Recap: Two Common Optimization Problems
Problem statement
Solution
Problem statement
Solution
(matlab)
Image Alignment Algorithm
Given images A and B
Compute image features for A and B
Match features between A and B
Compute homography between A and B using least squares on set of matches
What could go wrong?
Outliers
outliers
inliers
Required reading
ú
û
ù
ê
ë
é
ú
û
ù
ê
ë
é
=
ú
û
ù
ê
ë
é
y
x
d
c
b
a
y
x
‘
‘
ú
û
ù
ê
ë
é
ú
û
ù
ê
ë
é
ú
û
ù
ê
ë
é
ú
û
ù
ê
ë
é
=
ú
û
ù
ê
ë
é
y
x
l
k
j
i
h
g
f
e
d
c
b
a
y
x
‘
‘
ú
ú
ú
û
ù
ê
ê
ê
ë
é
ú
ú
ú
û
ù
ê
ê
ê
ë
é
–
=
ú
ú
ú
û
ù
ê
ê
ê
ë
é
1
1
0
0
0
cos
sin
0
sin
cos
1
‘
‘
y
x
y
x
q
q
q
q
ú
ú
ú
û
ù
ê
ê
ê
ë
é
ú
ú
ú
û
ù
ê
ê
ê
ë
é
=
ú
ú
ú
û
ù
ê
ê
ê
ë
é
1
1
0
0
1
0
0
1
1
‘
‘
y
x
t
t
y
x
y
x
ú
ú
ú
û
ù
ê
ê
ê
ë
é
ú
ú
ú
û
ù
ê
ê
ê
ë
é
=
ú
ú
ú
û
ù
ê
ê
ê
ë
é
1
1
0
0
0
1
0
1
1
‘
‘
y
x
sh
sh
y
x
y
x
ú
ú
ú
û
ù
ê
ê
ê
ë
é
ú
ú
ú
û
ù
ê
ê
ê
ë
é
=
ú
ú
ú
û
ù
ê
ê
ê
ë
é
1
1
0
0
0
0
0
0
1
‘
‘
y
x
s
s
y
x
y
x
ú
ú
û
ù
ê
ê
ë
é
ú
ú
û
ù
ê
ê
ë
é
=
ú
ú
û
ù
ê
ê
ë
é
w
y
x
f
e
d
c
b
a
w
y
x
1
0
0
‘
‘
0
1
2
3
4
5
6
0
2
4
6
8
10
12
Time
Mileage
1
s.t.
minimize
=
x
x
Ax
A
x
T
T
T
0
o
solution t
lsq
trivial
–
non
=
Ax
1
..
2
1
:
)
eig(
]
,
[
v
x
A
A
v
=
<
=
n
T
l
l
l
b
Ax
=
o
solution t
squares
least
b
A
x
\
=
2
minimize
b
Ax
-
(
)
b
A
A
A
x
T
T
1
-
=
/docProps/thumbnail.jpeg