CS代考 Matching: dealing with outliers

Matching: dealing with outliers
Whether a correlation-based method or a feature-based method is used, search is required to find points that are most similar.
These “most similar” points are putative matches
Some of these putative matches may be correct (“inliers”) but others may be wrong (“outliers”).
How do we find the true correspondence between images despite these matching errors?
SEARCH REGION
BEST MATCH
Computer Vision / Mid-Level Vision / Correspondence 37

Matching: dealing with outliers
Need to estimate transformation between images despite erroneous correspondences.
1. (Extract features – if using feature-based method)
2. Compute putative matches
3. Find most likely transformation (i.e. the one with the most inliers and fewest outliers)
use the RANSAC (= RANdom SAmpling & Consensus) algorithm Computer Vision / Mid-Level Vision / Correspondence 38
SEARCH REGION
BEST MATCH

RANSAC: algorithm
Objective:
Robust fit of model to data set which contains outliers
Requirements:
1. Data consists of inliers and outliers
2. A parameterized model explains the inliers
Procedure:
1. Randomly choose a minimal subset (a sample) of data points
necessary to fit the model
2. Fit the model to this subset of data
3. Test all the other data points to determine if they are consistent with
the fitted model (i.e. if they lie within a distance t of the model’s prediction)
4. Count the number of inliers (the consensus set). Size of consensus set is model’s support
5. Repeat from step 1 for N trials
After N trials select the model parameters with the highest support and re- estimate the model using all the points in this subset.
Computer Vision / Mid-Level Vision / Correspondence 39

RANSAC: simple correspondence example
Image shows a set of putative matches between points in two images
Assume the two images are related by a pure translation.
i.e. the model we wish to fit is a translation by Δx and Δy.
One putative match is sufficient to define Δx and Δy.
Computer Vision / Mid-Level Vision / Correspondence 40

RANSAC: simple correspondence example
1. Randomly choose a minimal subset (a sample) of data points necessary to fit the model
2. Fit the model to this subset of data
3. Test all the other data points to determine if they are consistent with the fitted model (i.e. if they lie within a distance t of the model’s prediction).
4. Count the number of inliers (the consensus set). Size of consensus set is model’s support
5. Repeat from step 1 for N trials
Computer Vision / Mid-Level Vision / Correspondence 41

RANSAC: simple correspondence example
Δ Δx x = = 2 2. .5 5, , Δ Δy y = = – -1 1
1. Randomly choose a minimal subset (a sample) of data points necessary to fit the model
2. Fit the model to this subset of data
3. Test all the other data points to determine if they are consistent with the
fitted model (i.e. if they lie within a distance t of the model’s prediction).
4. Count the number of inliers (the consensus set). Size of consensus set
is model’s support
5. Repeat from step 1 for N trials
Computer Vision / Mid-Level Vision / Correspondence 42

RANSAC: simple correspondence example
consensus set=1
1. Randomly choose a minimal subset (a sample) of data points necessary to fit the model
2. Fit the model to this subset of data
3. Test all the other data points to determine if they are consistent with the
fitted model (i.e. if they lie within a distance t of the model’s prediction).
4. Count the number of inliers (the consensus set). Size of consensus set
is model’s support
5. Repeat from step 1 for N trials
Computer Vision / Mid-Level Vision / Correspondence 43

RANSAC: simple correspondence example
Δ Δx x = = 2 2, , Δ Δy y = = 0 0
1. Randomly choose a minimal subset (a sample) of data points necessary to fit the model
2. Fit the model to this subset of data
3. Test all the other data points to determine if they are consistent with the
fitted model (i.e. if they lie within a distance t of the model’s prediction).
4. Count the number of inliers (the consensus set). Size of consensus set
is model’s support
5. Repeat from step 1 for N trials
Computer Vision / Mid-Level Vision / Correspondence 45

RANSAC: simple correspondence example
consensus set=4
1. Randomly choose a minimal subset (a sample) of data points necessary to fit the model
2. Fit the model to this subset of data
3. Test all the other data points to determine if they are consistent with the
fitted model (i.e. if they lie within a distance t of the model’s prediction).
4. Count the number of inliers (the consensus set). Size of consensus set
is model’s support
5. Repeat from step 1 for N trials
Computer Vision / Mid-Level Vision / Correspondence 46

RANSAC: simple correspondence example
Δx = 2.07, Δy = 0.02 After N trials select the model parameters with the highest support and re-
estimate the model using all the points in this subset.
Computer Vision / Mid-Level Vision / Correspondence 47

RANSAC: real correspondence example
Generally, the correspondence between views will be more complex than a pure translation.
Translation and rotation of the camera results in more complex transformations between images.
We can still estimate the parameters of this transformation by sampling more pairs of points (e.g. 4 pairs of putative matches)
In this example approx 500 interest points have been extracted with the Harris corner detector
Computer Vision / Mid-Level Vision / Correspondence 48

RANSAC: real correspondence example
For each interest point the best match has been found within a square search window (here 300 pixels) using SSD
These putative matches are shown using a line pointing from the interest point in the left image to the pixel location of the corresponding point in the right image
Computer Vision / Mid-Level Vision / Correspondence 49

RANSAC: real correspondence example
This results in 188 initial matches (which exceed some similarity threshold)
Computer Vision / Mid-Level Vision / Correspondence 50

RANSAC: real correspondence example
Applying RANSAC to determine the transformation between the camera locations, results in a model that is consistent with 99 matches and inconsistent with 89 matches.
Note, RANSAC allows correspondence to be found even in the presence of many outliers.
99 inliers 89 outliers
Computer Vision / Mid-Level Vision / Correspondence
51

RANSAC for fitting
Recall, fitting algorithms (used for segmentation):
A class of methods that try to use a mathematical model to represent a set of tokens.
e.g. to fit a straight line to a set of points
One algorithm for fitting a model to data is the RANSAC can also be used
Computer Vision / Mid-Level Vision / Correspondence 52

RANSAC: line fitting example
Our model is a straight line
Fitting a straight line requires two points.
Hence, our sample size is two.
1. Randomly choose a minimal subset (a sample) of data points necessary
to fit the model
2. Fit the model to this subset of data
3. Test all the other data points to determine if they are consistent with the fitted model (i.e. if they lie within a distance t of the model’s prediction).
4. Count the number of inliers (the consensus set). Size of consensus set is model’s support
5. Repeat from step 1 for N trials
Computer Vision / Mid-Level Vision / Correspondence 53

RANSAC: line fitting example
1. Randomly choose a minimal subset (a sample) of data points necessary to fit the model
2. Fit the model to this subset of data
3. Test all the other data points to determine if they are consistent with the
fitted model (i.e. if they lie within a distance t of the model’s prediction).
4. Count the number of inliers (the consensus set). Size of consensus set
is model’s support
5. Repeat from step 1 for N trials
Computer Vision / Mid-Level Vision / Correspondence 54

RANSAC: line fitting example
1. Randomly choose a minimal subset (a sample) of data points necessary to fit the model
2. Fit the model to this subset of data
3. Test all the other data points to determine if they are consistent with the fitted model (i.e. if they lie within a distance t of the model’s prediction).
4. Count the number of inliers (the consensus set). Size of consensus set is model’s support
5. Repeat from step 1 for N trials
Computer Vision / Mid-Level Vision / Correspondence 56

RANSAC: line fitting example
After N trials select the model parameters with the highest support and re- estimate the model using all the points in this subset.
Computer Vision / Mid-Level Vision / Correspondence 59

RANSAC: pros and cons
Advantages:
Simple and effective
General method suited for a wide range of model fitting problems
» e.g. for segmentation by model fitting
» e.g. for finding camera transformation given stereo views » e.g. for finding object trajectory given video
Disadvantages:
● Sometimesverymanyiterationsarerequiredifpercentageof outliers is high.
● Lots of parameters to tune
● ●
Computer Vision / Mid-Level Vision / Correspondence 60

Summary
Correspondence Problem
Finding matching image elements across images
• •
•
•
•
•
•
general problem arising in: stereo (multiple cameras)
video (multiple times)
object recognition (comparing images)
similar to grouping:
grouping is looking for similar elements in a single image
correspondence is looking for the same elements in multiple images
Computer Vision / Mid-Level Vision / Correspondence 61

Summary
Solving the Correspondence Problem
1. Which image locations to match
a. all locations (correlation-based method)
b. selected interest points (feature-based methods: Harris, SIFT)
2. What properties to match
a. image intensities
b. a descriptor of image properties (SIFT)
3. Where to look for matches
a. exhaustive search across entire image
b. restricted search (constrained by task knowledge)
4. How to evaluate matches
a. similarity (correlation, normalised correlation, correlation coefficient) b. differences (SSD, Euclidean distance, SAD)
5. How to find true correspondence (eliminate false matches) RANSAC
Computer Vision / Mid-Level Vision / Correspondence 62

Related Posts