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.
