程序代写代做代考 AI python Automatic Image Alignment (feature-based)

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 cx wy’  d e f y
p’ Hp
 x’ gxhyi gxhyi 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 i1  
axbyc axbycgxx’hyx’ix’0
See p.35
y’ dxey f
Zisserman
dxey 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 fy
for i=1,2,3,4
Special case of DLT method
pi (xi,yi)  p’i (x’i, y’i ) wx’ a b cx
iii
 w  g h i1
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 h0 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
Ah  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
Ah  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
aX b X’
X and b?
aX b X’
112233
 X 1 1   a    X 1′   ’
X 2′ X 1′
X2 1b X2  AxB
X1 X2
x  A1 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
aX b X’
What if the data points ( Xi ,Xi’ ) are noisy?
X
X1 1 X1’ X’ X2 1a X’ 
this problem is also known as “linear regression” problem
aX b X’
112233
X 1b 2 3 X3′
 … …  …  
AxB
min AxB2 x
(least-squares)
X
where A1  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  A1 B
over-constrained

SVD: rough idea
M ≥ N: 2
x
embed scale rotate T A  U W V
MxN MxN NxN NxN
Ax 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 AxB2 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  A1 B

Least squares line fitting
Datageneratedas X a X bX for a=0.2,b=20 and NormalnoiseX iii i
X i
Xi

Least squares line fitting
Datageneratedas X a X bX for a=0.2,b=20 and NormalnoiseX 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
BA9 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
hVW1UT (A9)
Ah  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 || pHp||  T

RANSAC for robust homography fitting
Homography for corrupted four matches is likely to have only a few inliers ( p, p) || pHp||  T
(randomly sampled)

RANSAC for robust homography fitting
Homographyforgoodfourmatcheshas21inliers (p,p)
|| pHp||  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 || pHp||  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