Lecture 1: Images and image filtering
Outliers
outliers
inliers
Slide set from Noah Snavely
Robustness
Let’s consider a simpler example… linear regression
How can we fix this?
Problem: Fit a line to these datapoints
Least squares fit
Idea
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
9
RAndom SAmple Consensus
Select another match at random, count inliers
10
RAndom SAmple Consensus
Output the translation with the highest number of inliers
11
RANSAC
Idea:
All the inliers will agree with each other on the translation vector; the (hopefully small) number of outliers will (hopefully) disagree with each other
RANSAC only has guarantees if there are < 50% outliers
“All good matches are alike; every bad match is bad in its own way.”
– Tolstoy via Alyosha Efros
RANSAC
Inlier threshold related to the amount of noise we expect in inliers
Often model noise as Gaussian with some standard deviation (e.g., 3 pixels)
Number of rounds related to the percentage of outliers we expect, and the probability of success we’d like to guarantee
Suppose there are 20% outliers, and we want to find the correct answer with 99% probability
How many rounds do we need?
RANSAC
x translation
y translation
set threshold so that, e.g., 95% of the Gaussian
lies inside that radius
RANSAC
Back to linear regression
How do we generate a hypothesis?
x
y
15
RANSAC
x
y
Back to linear regression
How do we generate a hypothesis?
16
RANSAC
General version:
Randomly choose s samples
Typically s = minimum sample size that lets you fit a model
Fit a model (e.g., line) to those samples
Count the number of inliers that approximately fit the model
Repeat N times
Choose the model that has the largest set of inliers
17
How many rounds?
If we have to choose s samples each time
with an outlier ratio e
and we want the right answer with probability p
proportion of outliers e
s 5% 10% 20% 25% 30% 40% 50%
2 2 3 5 6 7 11 17
3 3 4 7 9 11 19 35
4 3 5 9 13 17 34 72
5 4 6 12 17 26 57 146
6 4 7 16 24 37 97 293
7 4 8 20 33 54 163 588
8 5 9 26 44 78 272 1177
Source: M. Pollefeys
p = 0.99
How big is s?
For alignment, depends on the motion model
Here, each sample is a correspondence (pair of matching points)
RANSAC pros and cons
Pros
Simple and general
Applicable to many different problems
Often works well in practice
Cons
Parameters to tune
Sometimes too many iterations are required
Can fail for extremely low inlier ratios
We can often do better than brute-force sampling
20
Final step: least squares fit
Find average translation vector over all inliers
21
RANSAC
An example of a “voting”-based fitting scheme
Each hypothesis gets voted on by each data point, best hypothesis wins
Panoramas
Now we know how to create panoramas!
Given two images:
Step 1: Detect features
Step 2: Match features
Step 3: Compute a homography using RANSAC
Step 4: Combine the images together
https://www.mathworks.com/help/vision/ug/feature-based-panoramic-image-stitching.html
/docProps/thumbnail.jpeg