Automatic Image Alignment (feature-based)
© Mike Nese
with some slides stolen from Steve Seitz and Rick Szeliski
CS3335 Visual Computing
Automatic Image Alignment
• • •
feature detectors (e.g. DOG, LOG, Harris corners) and feature descriptors (e.g. MOPS)
(pi ,p’i )
there are many other popular descriptor (e.g. SIFT, SURF, HOG, BRIEF)
• Automatic feature detection and matching • Remember:
• Model fitting
• How many points to choose?
• Least square model fitting
• RANSAC (robust model fitting)
Flashbacks: feature detectors
Harris corners
Flashbacks: feature detectors
Harris corners
from skimage.feature import corner_harris, corner_subpix, corner_peaks
hc_filter = corner_harris(image_gray) peaks = corner_peaks(hc_filter)
Dog
from skimage.feature import blob_dog blobs = blob_dog(image_gray)
Flashbacks: feature descriptors We know how to detect points
Next question: How to match them?
?
Point descriptor should be:
1. Invariant 2. Distinctive
Example: MOPS descriptor
8×8 oriented patch
• Sampled at 5 x scale
Bias/gain normalisation: I’ = (I – )/
8 pixels
Another popular idea: use gradient orientations inside the patch as a descriptor (also invariant to gain/bias)
Example: MOPS descriptor
8×8 oriented patch
• Sampled at 5 x scale
Bias/gain normalisation: I’ = (I – )/
8 pixels
Other popular descriptors: SIFT, SURF, HOG, BRIEF, many more…
Feature matching
?
Python example (BRIEF descriptor)
from skimage.feature import (corner_harris, corner_peaks, plot_matches, BRIEF, match_descriptors)
keypointsL = corner_peaks(corner_harris(imL), threshold_rel=0.0005, min_distance=5) keypointsR = corner_peaks(corner_harris(imR), threshold_rel=0.0005, min_distance=5)
extractor = BRIEF()
extractor.extract(imL, keypointsL) keypointsL = keypointsL[extractor.mask] descriptorsL = extractor.descriptors
extractor.extract(imR, keypointsR) keypointsR = keypointsR[extractor.mask] descriptorsR = extractor.descriptors
find the closest match p’ for any feature p
crosscheck: keep pair (p,p’)
only if p is the best match for p’
matchesLR = match_descriptors(descriptorsL, descriptorsR, cross_check=True)
How to fit a homorgaphy???
What problems do you see for homography estimation?
How to fit a homorgaphy???
What problems do you see for homography estimation? Issue 1: too many matched pairs (pi ,p’i )
Answer: model fitting via “least squares”
(pi,p’i ) Answer: robust model fitting via RANSAC
Issue 2: too many wrong pairs
Remember: homography from 4 points
p
p’
Computing Homography from 4 points
Consider one point correspondence
p(x,y) p’(x’, y’)
wx’ a b cx wy’ d e f y
p’ Hp
x’ gxhyi gxhyi inHartleyand
Two equations linear w.r.t unknown coefficients of matrix H and quadratic w.r.t. known point coordinates (x,y,x’,y’)
w g h i1
axbyc axbycgxx’hyx’ix’0
See p.35
y’ dxey f
Zisserman
dxey f gxy’hyy’iy’0
Computing Homography from 4 points
Consider 4 point correspondences
i ax by c gx x’ hy x’ ix’ 0
p’ Hp ii
ii i wy’d e fy
for i=1,2,3,4
Special case of DLT method
pi (xi,yi) p’i (x’i, y’i ) wx’ a b cx
iii
w g h i1
ii iiiii (seep.89
dx ey f gx y’ hy y’ iy’ 0 ii iiiii
in Hartley and Zisserman)
Can be written as matrix multiplication Ai h 0
where h [ a b c d e f g h i ]T is a vector of unknown coefficients in H
and Ai is a 2×9 matrix based on known point coordinates xi , yi , x’i , y’i
for i=1,2,3,4
Computing Homography from 4 points
pi (xi,yi) p’i (x’i, y’i ) p’i Hpi Ai h0 fori=1,2,3,4
Consider 4 point correspondences
All four matrix equations can be “stacked up” as
A2
A h 0
or
3 8×1
A4 8×9
Ah 0
2×9 9×1 2×1 A1
8×9 9×1 8×1
Computing Homography from 4 points
Consider 4 point correspondences
pi (xi,yi) p’i (x’i, y’i ) (*)
p’i Hpi for i=1,2,3,4
Questions: 8 linear equations, 9 unknowns?
A simple solution:
set value for one of coefficients in h to 1, e.g. i=1 (Why OK?)
8×8 8×1 8×1
Ah 0
8×9
9×1
8×1
trivial solution h=0?
A1:8 h1:8 A9
first 8 columns of A first 8 rows of h 9th columns of A
Computing Homography Consider 4 point correspondences
pi (xi,yi) p’i (x’i, y’i )
A1:8 h1:8 A9
p’i Hpi for i=1,2,3,4
Questions:
What if 4 points correspondences are known with error?
Are there any benefits from knowing more point correspondences?
First, consider a simpler model fitting problem…
8×8 8×1 8×1
Simpler example: line fitting
Assume a set of data points ( X ,X’ ), ( X ,X’ ), ( X ,X’
), …
(e.g. person’s height vs. weight) We want to fit a model (e.g. a line) to predict X ‘ from
How many pairs
X 1 a b X 1′ X 2 a b X 2′
( Xi ,Xi’ )
do we need to find
a
aX b X’
X and b?
aX b X’
112233
X 1 1 a X 1′ ’
X 2′ X 1′
X2 1b X2 AxB
X1 X2
x A1 B
Simpler example: line fitting
Assume a set of data points ( X ,X’ ), ( X ,X’ ), ( X ,X’
), …
(e.g. person’s height vs. weight) We want to fit a model (e.g. a line) to predict X ‘ from
aX b X’
What if the data points ( Xi ,Xi’ ) are noisy?
X
X1 1 X1’ X’ X2 1a X’
this problem is also known as “linear regression” problem
aX b X’
112233
X 1b 2 3 X3′
… … …
AxB
min AxB2 x
(least-squares)
X
where A1 V W 1 U T is a pseudo-inverse based on SVD decomposition A U W V T
(in python use svd function in library numpy.linalg)
x A1 B
over-constrained
SVD: rough idea
M ≥ N: 2
x
embed scale rotate T A U W V
MxN MxN NxN NxN
Ax 3×2
where U and V are matrices with ortho-normal columns and W is diagonal with elements w ≥0
(see “Numerical Recipes in C”, edition 2, Sec. 2.6)
3
B
U1 U2
i
How does SVD help to solve least-squares ?
Ax
range of transformation A (2D subspace of 3 )
Ui (column-vectors of U) form the basis of this subspace)
min AxB2 x
projection of B onto range of A V W 1 U T B
Also, check equivalent expression
T -1 T
x = (AA) ∙A∙B
Nx1 NxN NxM Mx1
To get inverse (ATA)-1 one can directly computeSVD ofpositivesemi-definite NxN matrix ATA related to SVD of A:
ATA = VWUTUWVT = VW2VT
x A1 B
Least squares line fitting
Datageneratedas X a X bX for a=0.2,b=20 and NormalnoiseX iii i
X i
Xi
Least squares line fitting
Datageneratedas X a X bX for a=0.2,b=20 and NormalnoiseX iii i
X i
+ outliers
Xi
For cases with outliers we need a more robust method (e.g. RANSAC, coming soon)
Computing Homography from N points
Consider N point correspondences
compute SVD U·W·VT for A
then
1:8
1:8
pi (xi,yi) p’i (x’i, y’i ) (*)
p’i Hpi
for i=1,…,N over-constrained system
A solution (choosing i =1): So, there are only 8 unknowns.
Set up a system of linear equations for vector of unknowns h1:8 =[a,b,c,d,e,f,g,h]T
solve
A1:8 h1:8 2Nx8 8×1
BA9 2Nx1
(least-squares)
(or AT A ) as in the line fitting example
minA h B2
h1:8
2Nx9 9×1 2Nx1
1:8 1:8
1:8
hVW1UT (A9)
Ah 0
Least squares fail in presence of outliers
Least squares work if using “inliers” only
imR projected from inliers only
Question: how can one remove outliers automatically?
Model fitting robust to outliers
We need a method that can separate inliers from outlliers
RANSAC
random sampling consensus
[Fischler and Bolles, 1981]
RANSAC (for line fitting example)
1. randomly sample
two points, get a line
l
X i
Xi
RANSAC (for line fitting example)
# of inlilers = 30
2T
X i
l
1.
2.
randomly sample two points,
get a line count inliers p
for threshold T || p l || T
Xi
RANSAC (for line fitting example)
# of inlilers = 150
l
1.
2.
randomly sample two points,
get a line count inliers p
for threshold T || p l || T
X i
2T
Xi
3. repeat N times and select model with most inliers
RANSAC (for line fitting example)
# of inlilers = 150
l
1.
2.
randomly sample two points,
get a line count inliers p
for threshold T || p l || T
X i
Xi
3. repeat N times and select model with most inliers
4. Use least squares to fit a model (line) to this
largest set of inliers
RANSAC (for line fitting example)
X i
line model estimated via RANSAC
line model
based on least squares fit to all points
Xi
RANSAC for robust homography fitting
only two differences: 1. need to randomly sample four pairs ( p, p) the minimum number of matches to estimate a homography H
2. pair ( p, p) counts as an inlier for a given homography H if || pHp|| T
RANSAC for robust homography fitting
Homography for corrupted four matches is likely to have only a few inliers ( p, p) || pHp|| T
(randomly sampled)
RANSAC for robust homography fitting
Homographyforgoodfourmatcheshas21inliers (p,p)
|| pHp|| T
(randomly sampled)
RANSAC for robust homography fitting
Inliers for the randomly sampled homography with the largest inlier set
RANSAC for robust homography fitting
artefacts
in the area with no matches
The final automatic panorama result
RANSAC for robust homography fitting
In general (for other models):
always sample the smallest number
of points/matches needed to estimate a model
RANSAC loop:
1. Select four feature pairs (at random)
2. Compute homography H (exact)
3. Count inliers (p, p) where || pHp|| T
4. Iterate N times (steps 1-3). Keep the largest set of inliers.
5. Re-compute least-squares H estimate on all of the inliers