CS计算机代考程序代写 scheme Lecture 1: Images and image filtering

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