RANSAC: Random Sample Consensus II

Loading...

From the course by University of Pennsylvania

Robotics: Perception

370 ratings

University of Pennsylvania

Robotics: Perception

370 ratings

Course 4 of 6 in the Specialization Robotics

How can robots perceive the world and their own movements so that they accomplish navigation and manipulation tasks? In this module, we will study how images and videos acquired by cameras mounted on robots are transformed into representations like features and optical flow. Such 2D representations allow us then to extract 3D information about where the camera is and in which direction the robot moves. You will come to understand how grasping objects is facilitated by the computation of 3D posing of objects and navigation can be accomplished by visual odometry and landmark-based localization.

From the lesson

Multi-View Geometry

Now we will use what we learned from two view geometry and extend it to sequences of images, such as a video. We will explain the fundamental geometric constraints between point features in images, the Epipolar constraint, and learn how to use it to extract the relative poses between multiple frames. We will finish by combining all this information together for the application of Structure from Motion, where we will compute the trajectory of a camera and a map throughout many frames and refine our estimates using Bundle adjustment.

Epipolar Geometry I23:02

Epipolar Geometry II14:20

Epipolar Geometry III24:53

RANSAC: Random Sample Consensus II6:54

Nonlinear Least Squares I3:25

Nonlinear Least Squares II6:17

Nonlinear Least Squares III13:51

Optical Flow: 2D Point Correspondences19:49

3D Velocities from Optical Flow16:26

3D Motion and Structure from Multiple Views18:30

Visual Odometry19:50

Bundle Adjustment I17:45

Bundle Adjustment II18:29

Bundle Adjustment III17:50

Meet the Instructors

Kostas Daniilidis
Professor of Computer and Information Science
School of Engineering and Applied Science
Jianbo Shi
Professor of Computer and Information Science
School of Engineering and Applied Science

Now we see RANSAC is a method that allows us to use the least squares method with

confidence in practice.

Even despite outliers in the data.

We will review this procedure in the context of fundamental matrix estimation.

Recall fundamental matrix is a relationship between two-dimensional

images.

In this case we see image on the left,

image on the right consists of simple left-right translation.

And we want to mark corresponding points.

If you find the corresponding points, and least eight of them

that allows us to estimate the fundamental matrix between them.

And through that we can triangulate points in 3D as well as figure out a camera

rotation translation between them.

If I were robots running in space,

I need to find an automatic way of finding correspondence between two views.

As you can imagine, we will sometimes make error.

Here we're shown the entire correspondence between points that were automatically

extract image to the left with points we extract automatically on the right.

As you can see, the lines connecting them should have just gone left and right.

Anything that's off from the horizontal direction is incorrect.

As expected, the computers not perfect and makes some errors.

If I take all the correspondence into the least squares solution or run svd,

I would totally get a disaster.

So we need to run RANSAC as a way of finding the good correspondence.

Together with the fundamental matrix estimations.

Let's take eight points, and what we want is to make sure we repeatedly

pick eight points until we find all eight points being the good models.

So in this case I randomly pick eight points and I share luck.

I was not very good at it, and I find bad corresponding points.

I don't know that yet, so precede it, take the eight point algorithm.

Working on those eight correspondence points, and

extract the fundamental matrix F as shown here.

Now I have the model that corresponding left to the right image.

I can try to pilot through all the other points of the image.

And in this case I count inliers that follows this mapping function.

There are only 65 of those points that fits.

Suppose I find the better points, eight points.

In this case I randomly run the sampling algorithm many,

many times until I find the lucky case.

In this case you can see the fundamental matrix computed showing here.

And if I count inliers I can illustrate that those inliers are a lot more.

So 118 of them.

So we know this a better correspondence and this is a better fundamental matrix.

So again in the case of the least squaring practice we don't run least square once.

We need to run least square multiple times.

Correspondent number of sample we need to pick.

And each time we compute the least square solution, and

then we check whether it's correct or not by doing a majority voting.

But the question is, what is the error function that we should look when

we know that it didn't follow epipolar constraints?

Recall at the point in left the image can be transformed to right image as

a epipolar line.

And it has this correspondence point automatically computed by computer.

And we can check whether the corresponding point in the zoom out view in fact,

is lighting on the line.

And due to the noise, and

the competition most likely you won't find that to be exactly on the line itself.

In fact at some distance offset from the epipolar line.

So we can measure this distance.

And then this is going to tell me whether this epipolar line and

corresponding point is matched up correctly.

So typically we want this area to be only one or two pixels large.

Equation bottom shows the distance between a line to a point.

So again a line you can think of a homogeneous point as a b c and

the point is xy1.

And this equation shows the inner power between xy1 the homogeneous corner

of a point x2 and abc, the line divide by the norm of a squared, b squared.

But in a more general form if I have a epipolar line written as a vector l.

And the corresponding point x2 written as homogenous coordinate.

We take the dot product between the two and divide by the first two elements of l.

The norm of that.

And recall that epipolar line is simply constructed.

This three dimensional vector is simply constructed by

taking the fundamental matrix f times on the right x1.

The homogeneous coordinates of a point on the left image.

So this equation shows the distance from x2 to

the epipolar line obtained from the point x1.

So what we want to check is inliers, outliers is freely determined by this

quantity e, the distance to the epipolar line.

Again, we pick set of eight points in the left image, construct an f matrix.

And then we check for all the other points in the right image,

whether this falls on a corresponding epipolar line by checking this distance.

So this, the thing we'll have a pixel error of exactly .7089 pixels.

And we will repeat this process many times.

At some point, we'll find a much better eight points.

I gave an inliers count of 443.

And that will give us fundamental matrix that we see.

So that concludes the least square with the RANSAC.

So any time we want to use a least squares solution, should think about using RANSAC

as a safety mechanism, allows to pick up the correct models from some noisy data.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play