Image Alignment
http://www.wired.com/gadgetlab/2010/07/camera-software-lets-you-see-into-the-past/
Reading • Szeliski: Chapter 6.1
Copyright By PowCoder代写 加微信 powcoder
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
Simple case: translations
How do we solve for ?
Simple case: translations
Displacement of match i =
Mean displacement =
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 – 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
Least squares
• Find t that minimizes
• To solve, form the normal equations
Image Alignment Algorithm Given images A and B
1. Compute image features for A and B
2. Match features between A and B
3. Compute homography between A and B using least squares on set of matches
What could go wrong?
Robustness
• Let’s consider a simpler example… linear regression
Problem: Fit a line to these datapoints Least squares fit • How can we fix this?
Least squares: linear regression
00 1 2 3 4 5 6 Time
y = mx + b
Linear regression
residual er
00 1 2 3 4 5 6 Time
• Given a hypothesized line
• Count the number of points that “agree” with the line
– “Agree” = within a small distance of the line – I.e., the inliers to that line
• For all possible lines, select the one with the largest number of inliers
Counting inliers
Counting inliers
Inliers: 3
Counting inliers
Inliers: 20
How do we find the best line?
• Unlike least-squares, no simple closed-form solution
• Hypothesize-and-test
– Try out many lines, keep the best one – Which lines?
Translations
RAndom SAmple Consensus
Select one match at random, count inliers
RAndom SAmple Consensus
Select another match at random, count inliers
RAndom SAmple Consensus
Output the translation with the highest number of inliers
– All the inliers will agree with each other on the translation vector; the (hopefully small) number of outliers will (hopefully) disagree with each other
– “All good matches are alike; every bad match is bad in its own way.”
– Tolstoy via
y translation
set threshold
x translation
RANSAC • Back to linear regression
• How do we generate a hypothesis? y
• Back to linear regression
• How do we generate a hypothesis?
RANSAC • General version:
1. Randomly choose s samples
• Typically s = minimum sample size that lets you fit a
2. Fit a model (e.g., line) to those samples
3. Count the number of inliers that approximately fit the model
4. Repeat N times
5. Choose the model that has the largest set of inliers
Final step: least squares fit
Find average translation vector over all inliers
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com