# CS代考 Matching: dealing with outliers – cscodehelp代写

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

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 44

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 55

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

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 57

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 58

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