3/4/2021
CSE 473/573
Introduction to Computer Vision and Image Processing
‘-
ALIGNMENT AND FITTING
Questions from last class?
Extra Friday Office Hour: 8-9 AM Quiz Tuesday through last lecture
‘-
1
3/4/2021
Hough transform
P.V.C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959
Given a set of points, find the curve or line that explains the data points best
ym
x
y = m x +b
‘-
b Hough space
Slide from S. Savarese
Incorporating image gradients
• Recall: when we detect an edge point, we also know its gradient direction
• But this means that the line is uniquely determined!
• Modified Hough transform:
• For each edge point (x,y)
θ = gradient orientation at (x,y) ρ = x cos θ + y sin θ
H(θ, ρ) = H(θ, ρ) + 1
end
‘-
2
3/4/2021
Hough transform
P.V.C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959
Given a set of points, find the curve or line that explains the data points best
ym
x
y = m x +b
‘-
b Hough space
Slide from S. Savarese
Hough transform for circles
• Conceptually equivalent procedure: for each (x,y,r), draw the corresponding circle in the image and compute its “support”
r
‘-
y
x
3
3/4/2021
Circles •Parameters: X,Y,R
• What is the complexity? • Find a point in 3D Space • Very sensitive to noise
• What can we do to constrain the problem?
‘-
7
Circles
• Use Gradient
• Reduced to R, Theta Space
‘-
4
3/4/2021
Circles – Hybrid Approach
• Use Gradient and Edge Pairs
• What is the new space?
‘-
Finding lines using Hough transform • Using m,b parameterization
• Using r, theta parameterization • Using oriented gradients
• Practical considerations • Bin size
• Smoothing
• Finding multiple lines • Finding line segments
‘-
5
3/4/2021
Hough transform conclusions
Good
• Robust to outliers: each point votes separately
• Fairly efficient (much faster than trying all sets of parameters) • Provides multiple good fits
Bad
• Some sensitivity to noise
‘-
• Bin size trades off between noise tolerance, precision, and speed/memory
• Can be hard to find sweet spot
• Not suitable for more than a few parameters
• grid size grows exponentially
Common applications
• Line fitting (also circles, ellipses, etc.)
• Object instance recognition (parameters are affine transform)
• Object category recognition (parameters are position/scale)
Fitting and Alignment: Methods
• Global optimization / Search for parameters • Least squares fit
• Robust least squares
• Other parameter search methods
• Hypothesize and test
• Generalized Hough transform
• General Alignment
• Homographies
• Rotational Panoramas • RANSAC
• Global alignment
• Warping
• Blending
‘-
6
3/4/2021
What are Fitting and Alignment?
Fitting: find the parameters of a model that best fit the data
‘-
Alignment: find the parameters of the transformation that best align matched points
Alignment Motivation(s): Recognition
‘-
Figures from David Lowe
7
3/4/2021
Motivation: medical image registration
‘-
Motivation: Mosaics
• Getting the whole picture
• Typical camera: 50 ̊ x 35 ̊
‘-
Slide from Brown & Lowe 2003
8
3/4/2021
Motivation: Mosaics
• Getting the whole picture
• Typical camera: 50 ̊ x 35 ̊
• Human Vision: 176 ̊ x 135 ̊
‘-
Slide from Brown & Lowe 2003
Motivation: Mosaics
• Getting the whole picture
• Typical camera: 50 ̊ x 35 ̊
• Human Vision: 176 ̊ x 135 ̊
‘-
• Panoramic Mosaic = up to 360 x 180°
Slide from Brown & Lowe 2003
9
3/4/2021
Alignment
• Homographies
• Rotational Panoramas • RANSAC
• Global alignment
• Warping
• Blending
‘-
Motion models
• What happens when we take two images with a camera
and try to align them?
• translation?
• rotation?
• scale?
• affine?
• perspective?
‘-
Szeliski
10
3/4/2021
Image Warping
• image filtering: change range of image
• g(x) = h(f(x)) ff
h
‘-
xx
• image warping: change domain of image • g(x) = f(h(x))
ff
h
xx
Szeliski
Image Warping
• image filtering: change range of image • g(x) = h(f(x))
fg
h
‘-
• image warping: change domain of image • g(x) = f(h(x))
f
g
h
Szeliski
11
3/4/2021
Parametric (global) warping • Examples of parametric warps:
‘-
translation rotation
affine perspective
aspect
cylindrical
Szeliski
Image Warping
• Given a coordinate transform x’ = h(x) and a source image f(x), how do we compute a transformed image g(x’) = f(h(x))?
‘-
h(x)
x f(x)
x’
g(x’)
Szeliski
12
3/4/2021
Forward Warping
• Send each pixel f(x) to its corresponding location x’ =
h(x) in g(x’)
• What if pixel lands “between” two pixels?
‘-
h(x)
x f(x)
x’
g(x’)
Szeliski
Forward Warping
• Send each pixel f(x) to its corresponding location x’ =
h(x) in g(x’)
• What if pixel lands “between” two pixels?
• Answer: add “contribution” to s‘-everal pixels,
normalize later
x f(x)
h(x)
x’ g(x’)
Szeliski
13
3/4/2021
Bilinear interpolation
Sampling at f(x,y):
Slide from Alyosha Efros, CMU
‘-
Interpolation
• Possible interpolation filters: • nearest neighbor
• bilinear
• bicubic (interpolating)
• sinc / FIR ‘-
• Needed to prevent “jaggies” and “texture crawl”
Szeliski
14
3/4/2021
Prefiltering
• •
Essential for downsampling (decimation) to prevent aliasing
MIP-mapping [Williams’83]:
1.
2.
build pyramid (but what decimation filter?):
• block averaging
• Burt & Adelson (5-tap binomial)
• 7-tap wavelet-based filter (better)
‘-
trilinear interpolation
• bilinear within each 2 adjacent levels
• linear blend between levels (determined by pixel size)
Szeliski
2D coordinate transformations
• translation: • rotation:
• similarity:
• affine:
x’ = x + t
x’ = R x + t
x’ = s R x + t
x’ = A x + t
x = (x,y)
‘-
x’ H x
(x is a homogeneous coordinate)
• perspective:
• These all form a nested group (closed w/ inv.)
x = (x,y,1)
Szeliski
15
3/4/2021
Basic 2D Transformations
• Basic 2D transformations as 3×3 matrices
x’ 1 0 tx x y’ 0 1 ty y
1 0 0 11
Translate
x’ cos sin 0x y’ sin cos 0y
10011
Rotate
x’
sx 0 0x 0 sy 0y
0 0 11
Scale
1 shx 0x
y’
1 ‘-
x’
y’ shy 1 0y
10011
Shear
Source: Alyosha Efros
Image alignment
• Two broad 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
‘-
Source: L. Lazebnik
16
3/4/2021
Fitting an affine transformation
‘-
Affine model approximates perspective projection of planar objects.
Figures from David Lowe, ICCV 1999
Fitting an affine transformation
• Assuming we know the correspondences, how do we get
(xi , yi )
the transformation?
x m mx t i 1 2 i1
y m m y t
i 3 4 i 2
( x i , y i )
‘-
Grauman
17
3/4/2021
Fitting an affine transformation
• Assuming we know the correspondences, how do we get
the transformation?
(xi , yi )
‘-
x y 0 0 1 0m x ii3i
x m mx t i 1 2 i1
(xi, yi) m1
m2
0 0 x y 0 1my ymmyt ii4i
i 3 4 i 2 t
1
t 2
Fitting an affine transformation
m2
m1
x y 0 0 1 0m x ii 3i
0 0 x y 0 1m y i i 4i
t
1 ‘-
t 2
• How many matches (correspondence pairs) do we need to solve for the transformation parameters?
• Once we have solved for the parameters, how do we compute the coordinatesofthecorrespondingpointfor (xnew,ynew)?
Grauman
18
3/4/2021
Panoramas
…
‘-
Obtain a wider angle view by combining multiple images.
Grauman
How to stitch together a panorama? • Basic Procedure
• Take a sequence of images from the same position • Rotate the camera about its optical center
• Compute transformation between second image and
‘-
• …but wait, why should this work at all?
• What about the 3D geometry of the scene? • Why aren’t we using it?
first
• Transform the second image to overlap with the first
• Blend the two together to create a mosaic
• (If there are more images, repeat)
Source: Steve Seitz
19
image from S. Seitz
3/4/2021
Panoramas: generating synthetic views
real camera
synthetic camera
‘-
Can generate any synthetic camera view
as long as it has the same center of projection!
Source: Alyosha Efros
Image reprojection
‘-
mosaic PP
• The mosaic has a natural interpretation in 3D • The images are reprojected onto a common plane • The mosaic is formed on this plane
• Mosaic is a synthetic wide-angle camera
Source: Steve Seitz
20
3/4/2021
Homography
• How to relate two images from the same camera center?
• how to map a pixel from PP1 to PP2?
• Think of it as a 2D image warp from one
PP2
PP1
image to another.
‘-
• A projective transform is a mapping between any two PPs with the same center of projection
• rectangle should map to arbitrary quadrilateral • parallel lines aren’t
• but must preserve straight lines
• called Homography
wx’ * * *x wy’ * * *y
w ***1
p’ H p Source: Alyosha Efros
x, y
To apply a given homography H
wx wy
w , w x, y
‘-
• Compute p’ = Hp (regular matrix multiply) wy’ * * * y
• Convert p’ from homogeneous to image * * * w1
wx’ * * * x
coordinates p’ H p
21
3/4/2021
x , y 11
x2 , y2 x ,y
x, y 11
x , y 22
x,y nn nn
‘-
To compute the homography given pairs of corresponding points in the images, we need to set up an equation where the parameters of H are the unknowns…
Grauman
Solving for homographies
wx’ a b cx
p’ = Hp wy’ d e f y
w g h i1
‘-
•Ah = b
•where vector of unknowns h = [a,b,c,d,e,f,g,h]T
•Need at least 8 eqs, but the more the better…
•Solve for h. If overconstrained, solve using least-squares:
min Ah b 2
•Can set scale factor i=1. So, there are 8 unknowns. •Set up a system of linear equations:
Grauman
22
…
…
3/4/2021
Recap: How to stitch together a panorama?
• Basic Procedure
• Take a sequence of images from the same position
• Rotate the camera about its optical center ‘-
• Compute transformation between second image and first
• Transform the second image to overlap with the first
• Blend the two together to create a mosaic
• (If there are more images, repeat)
Source: Steve Seitz
Image warping w/ homographies
image plane in front
‘-
image plane below
Source: Steve Seitz
black area where no pixel maps to
23
3/4/2021
Image rectification
p
‘-
p’
What is the shape of the b/w floor pattern?
Analyzing patterns and shapes
‘-
The floor (enlarged)
Slide from Criminisi
Automatically rectified floor
24
3/4/2021
Analysing patterns and shapes
Slide from Criminisi
‘-
From Martin Kemp The Science of Art (manual reconstruction)
Analysing patterns and shapes
What is the (complicated) shape of the floor pattern?
‘-
Automatically rectified floor
St. Lucy Altarpiece, D. Veneziano
Slide from Criminisi
25
Automatic rectification
3/4/2021
Analysing patterns and shapes
Automatic rectification
‘-
From Martin Kemp, The Science of Art (manual reconstruction)
Slide from Criminisi
changing camera center
synthetic PP
• Does it still work?
PP2
PP1
‘-
Source: Alyosha Efros
26
3/4/2021
Planar scene (or far away)
PP1
PP3
‘-
PP2
• PP3 is a projection plane of both centers of projection, so we are OK!
• This is how big aerial photographs are made
Source: Alyosha Efros
RANSAC
RANSAC
‘-
27
3/4/2021
RANSAC
• RANdom Sample Consensus
• Approach: we want to avoid the impact of ‘-
outliers, so let’s look for “inliers”, and use those only.
• Intuition: if an outlier is chosen to compute the current fit, then the resulting line won’t have much support from rest of the points.
RANSAC
RANSAC loop:
1. Randomly select a seed group of points on which to base transformation estimate (e.g., a group of matches)
2. Compute transformation from seed group ‘-
3. Find inliers to this transformation
4. If the number of inliers is sufficiently large, re-compute
least-squares estimate of transformation on all of the inliers
• Keep the transformation with the largest number of inliers
28
3/4/2021
RANSAC Line Fitting Example
Task:
Estimate best line
‘-
Slide credit: Jinxiang Chai, CMU
RANSAC Line Fitting Example
Sample two points
‘-
29
3/4/2021
RANSAC Line Fitting Example
Fit Line
‘-
RANSAC Line Fitting Example
Total number of points within a threshold of line.
‘-
30
3/4/2021
RANSAC Line Fitting Example
Repeat, until get a good result
‘-
RANSAC Line Fitting Example
Repeat, until get a good result
‘-
31
3/4/2021
RANSAC Line Fitting Example
Repeat, until get a good result
‘-
How to choose parameters? • Number of samples N
• Choose N so that, with probability p, at least one random sample is free from outliers (e.g. p=0.99) (outlier ratio: e )
• Number of sampled points s
• Minimum number needed to fit the model
‘-
proportion of outliers e
s 5% 10% 20% 25% 30% 40% 50%
2 2 3 5 6 7 11 17
• Distance threshold
• Choose so that a good point with noise is likely (e.g., prob=0.95) within threshold • Zero-mean Gaussian noise with std. dev. σ: t2=3.84σ2
s N log1 p/ log1 1 e
For p = 0.99
5 9 6 12 7 16 8 20 9 26
13 17 17 26 24 37 33 54 44 78
34 72 57 146 97 293
163 588
272 1177
3 3 4 3 5 4 6 4 7 4 8 5
4 7 9 11 19 35
modified from M. Pollefeys
32
3/4/2021
RANSAC example: Translation
‘-
Putative matches
Source: Rick Szeliski
‘-
Select one match, count inliers
33
3/4/2021
‘-
Select one match, count inliers
‘-
Find “average” translation vector
34
3/4/2021
RANSAC conclusions
Good
• Robust to outliers
• Applicable for larger number of model parameters than Hough transform • Optimization parameters are easier to choose than Hough transform
Bad
‘-
• Computational time grows quickly with fraction of outliers and number of parameters
• Not good for getting multiple fits
Common applications
• Computing a homography (e.g., image stitching)
• Estimating fundamental matrix (relating two views)
35