RANSAC - Random Sample Consensus (Cyrill Stachniss)

so welcome everyone I want to talk today about the Rancic algorithm which is one approach for dealing with outliers in your data so if you have real-world data from laser range scanner or from at the camera images you will need to make data Association between those measurements between parts and the image number one and parts in the image number two or between parts of a laser range scan and scan one and parts of a second skin and those data decisions are often correct but they are not outlier free and the approach here gives us a chance on identifying those outliers and eliminating those outliers in order to make our state estimation algorithms more robust so let's start with an example with a pair of images taken from different viewpoints that you have seen already and what I want to do is I want to make dat associations between those two images so saying this point in this image number 1 corresponds to this point in image number 2 I need those correspondences in order to compute for example the relative orientation so where has this image been taken with respect to the other image or the other viewpoint for the simultaneous localization and mapping problem and a large number of other applications and what we can do we can extract features from those images and make feature correspondences based on a feature descriptor value for example so if you run the sift algorithm and draw now all found correspondences on top of each these two images we can see that there are a lot of correct ones or seem to be consistent ones that say that way which are those going from this to the other side-- but we see a lot of random lines going all over the image and these are typically the outliers the incorrect date associations and what we want to do is we want to take this outlier set and turn it into this outlier set which is a set of in Liars and here we can see all those correspond sees is are rather consistent with each other and this consistency is something that we will actually exploit in the ransac algorithm in order to find the in liars in outliers and get rid of those outliers so this was an example for image based matching that we want to match the content of two images but we can also fit models in laser range data so consider you have area laser range skin so taken from top and you want to estimate the ground plane so you want to actually estimate this plane or in this 2d illustration line over here that corresponds to the ground plane although there are measurement points which are reflected from the trees the robot the building whatever but you want to say which one are in Liars for the ground plane and which are outliers and this is also a technique or a problem where Remnick can help you in order to identify those points which lie on that line so today we're looking into the UN's ik algorithm an approach which is nearly 40 years old by now but still the gold standard today for dealing with outlier situations so when you have data and made data associations and those data stations are affected by outliers or you have outliers you want to fit the model for that and you need to identify which of the data points are in line outliers for your model estimation technique okay how does it work so it is a trial and error approach actually quite easy to explain quite easy to grasp and has the advantage that can deal with high fractions of outliers so even with 50% outliers in your data set you're typically able to find the in layer set and then perform your state estimation algorithm so it's actually a very powerful algorithm so the key idea is to partition the data points into in liars and outliers and then use only the in layers to perform the subsequent state estimation task and it does so by a very simple approach it basically guesses in liars thus model computations use those guests in liars and then take all the other points which have not been used so far to evaluate how consistent they are with the computed model and then this process is repeated over and over and over again and then in the end I take the model which has the highest agreement of the data points and this is basically all what rancic is about and again it's very simple to explain very simple to implement and maybe you should go through this with a concrete example so again we have the three steps the first one is the sampling step and second one the model computation step and the third moogle scoring step so the sampling step what it does it basically picks a few data associations and it's they are in liars and I need to pick a small number of those in Liars and this to be the number we call s the number of data point that I need in order to compute my model so for example if I want to compute the trans the relative orientation between two camera images I am using an algorithm here which is called the five-point algorithm so it needs five data points in order to do the computations this means I would sample five data points in order to do the computation or if I want to fit a line through data points I need to between two data points and/or to fit a line through those two points so the model determines how many data points I need to sample so after assemble my data points I use those data points as perfect in liars for no outliers and do my standard model computation so this is my background knowledge this describes the tasks that I actually want to do and then in the third step I take all the remaining data points all the data points I haven't used so far in the model computation and estimate or score them how consistent are those data points with the model that I have computed so far ah how many of the remaining points are in liars and outliers and the in liars give me a counter score and the higher the score the better and then I repeat this process again sample in Liars do the model computations do the scoring repeat this over and over again and always store the model which has the highest number of in liars so that in the end I found the best model and can split my data sets into in liars and outliers again let's go to a very concrete example we have points in 2d and you want to fit a line through those two points so I assume there is one line that passes through these points some of the points are in liar a liar some of the points are outliers but I do not know which one they are so if line could go over here line it could be over here or maybe even here so what the best line given these data points well the first thing I need to do I need to sample the number of data points needed to fit my model in order to fit a line for data point I need two points so I need to sample two s equals two points let's randomly pick these two points out here so I pick these two points sample those points step number one is done now come to step number two I need to fit a line through those two so line which passes through these two points also something that I can do in a straightforward fashion so this is my line i computed my model and I'm happy with my model and then the third step is to say how many of the remaining data points of the red data points are actually agree with this line so this point clearly agrees with this line that's what probably as well those two maybe but all the other is actually far away from that line so they typically don't agree to that line so what I need are typically have a parameter like this Delta parameter over here which tells me how far can I be away from the model and still be considered in in laia so then in this example I have count four in layers one two three four these two points are not counted because I used them to compute the mode and then I get an inlay account of four so this model will lead to four in buyers that are found in the remaining data set and then I simply repeat this process so start from scratch saved up safe the best models start from scratch and now I accept those two points over here so these are my two points now I need to fit a line and this line goes pass through this one so that's my line and again I need to do my my scoring and so now score one two three four five six seven eight nine ten eleven twelve points so the Enlai account goes to 12 and this yourself so the model was 12 in liars is better than the multi-purpose for the data points so I know I forget the model before and say this is not my best one and then I repeat this process over and over and over and over again until I say I'm done let's say 1,000 trials and then I say okay that was my best data set I found my separation in unless an outlier so all the blue points plot those two are now used to estimate the line and all the others outliers red points are thrown away what one typically does after running the rancic so after having thrown away all the outliers is then performed even better or computationally more demanding algorithm for fitting the line for example at least square fit through these lines or something so here's another example where we want to compute the translation based on two images and consider we have five possible data associations here shown in through the errors in red and in white red are two outliers the white one are in liars in this illustration so what would Rancic do we would select a random match out of the possible matches let's say the black one over there and then evaluate all the others how well this translation is in line with all the other data associations and it turns out none of them is actually a good fit all of them are shown in red so they are inconsistent with the black one and so we have an in liar count of zero then we repeat the process we do another select another data point like this one and then see how the translation between those images would actually look like and count all the others so this example we have one two three four green ones which are consistent and one two outliers which are inconsistent and so this translation hypotheses would give us an inlay account of four and then we repeat this process n times or T times over and over again select image count in lire select the match count in Liars until we find the most consistent set and return the one which has the highest number of in liars which would be exactly this transformation so just as a small example as an illustration how you can actually use it to find the data associations between image pairs so that a translation between those images is consistently explained the next example I'm going to look into is feature based alignment where I want to stitch two images together based on the feature that I found so you see here two images taking of the scene with the partial overlaps of the images overlapped approximately in this part so this is at the same mountain and I want to stitch those images together how can I actually do this what I do is I extract my features so these are all the white points my key points that I've found and then based on the image descriptor I compute potential of putative matches so these are the red lines over here so some seem to be very consistent over here some seem to be more likely to be wrong and so what I do is I hypothesize a transformation by selecting a small subset of data points s equal three for example those three and I hypothesize the transformation that is generated from these three associations and then I verify that with all the others so in this case these are all the associations which support this transformation that I computed and then I repeat this process over and over and over again until I find the largest number of in liars or supporting other data sessions which is the case here so they can then stack those two images together and find here the correct stitching for the correct transformation how I need to transform image number two into image number one so that they are in the same reference frame of course the proper stitching algorithm I will still need to do some color Corrections or color fading from one image to the other but from the transformation point of view that's the way to go so I can again look back to the you know to dummy example so this is my two images I compute for example Harrah's key points which are the points now shown in here with different colors and then I can make the data session based on descriptor that are computed for all those Harris key points and so this may be my data Association I can see some of them seem to be correct but others are more likely to be wrong like this one over here where the left hand side of the tower is matched with its own right hand side and the other image we can see this as happens because they are simply repetitive structures or very similar local regions in the images and then what I do I can run my Rancic algorithm and separate my point set into in liars and outliers and I can see all of those which are shown here in green are in liars all others are outliers and so that I would remove those data associations for all those red points keep the green ones and then can compute for example my relative orientation between those two images and that's basically what I need to do I run my three steps and then run them over and over and over again until I identified my in line outliers I throw away the outliers and continue working with the entire the only question we haven't answered yet is often do we need to try right so we said repeat this process but how often do I need to repeat this process and this is actually something which is not that easy to answer because it requires knowledge about the underlying outlier distribution and if you have no idea what your outlier distribution is or what not necessary outline distribution what about the number of outliers is so the outlier ratio is in your data set then it can be tricky so you typically need that in order to have a good estimate so let's see which parameters are involved in my Rancic algorithm and how they affect the number of trials that I need to do so the important parameters start with a number of sample data points s so how many of the data points in the first step do I need to a sample and there's a number of data point that I need in order to compute my model so I need five data points for computing my model I need to sample five of the points here and since they all must be in Liars you know to get the right result the larger that number S is the more difficult it is to actually draw those liars a second important parameter is the outlier a Shoei given by the number of outliers divided by the number of overall data points and so if you have ten percent outliers and every tenth point is an outlier and this also important information so what we want to have is we want to have a number T that we want to compute that tells us how often do we need to try let's say that's T our interests in computing T so T is what I want to have the question is how big should that T be how can I actually compute it and I cannot give you an exact guarantee by saying you need to try five times and then you for sure have the right result because we are drawing samples and there's only a probability with which I can provide that so let's say I want to be certain with 99% probability that I get the right result how should t look like and that's actually something that I can do so a given s given e given a probability that I specified it's a 99% of the cases I want to do the right thing then we can actually compute T and what we're looking to is how do we actually obtain that T how we can we estimate how many trials we actually need assuming that we really have random outliers here and there's no systematics in the umpires itself so let's look to one read SEC iteration so one step of sampling model computation scoring how likely it is to succeed to find the right result what does it mean to find the right result to find the right result means sampling with s the in only in liar point so there there's no single outlier in this set of size s that I can then compute the model only using in Liars and then have a correct result so what is the probability of only drawing in Liars so what are probably drawing a single entire probability of throwing a single in liar is 1 minus e so 1 minus the outlier ratio is the probability that a data point is an in liar so if I draw one in liar it's 1 minus e I however need to do this s times makers need to have s in Liars so it's 1 minus e times 1 minus e times 1 minus e and the whole thing s times there's a probability for drawing on the in Liars so 1 minus e to the power of s and now I'm actually interested what's the probability of actually making a failure of failing if I want to fail that means I need to have at least one of those data points maybe even more is an outlier so it's 1 minus the expression that I have so the probability of failing ones so piece of probability of success so 1 minus P is the probability of failing once so in one iteration of Rancic is 1 minus e to the power of s this is of drawing only in Liars and this is the opposite probabilities 1 minus of having only drawn in Liars it means one data point is an outlier so this is the probability of failing once in one iteration so now I need to look what's the probability actually of failing T times have T iterations what the probably of failing always never succeeding at all it's taking both expression 2 or take the expression to the power of T and so if it is 1 minus the success probability always so it's failing T times of the he is not slightly different meanings normal iterations all iterations it's the same expression F before ^ t right because I'm repeating the same thing T times and what's the probability of failing T times it's just failing once to the power of T okay so that means all the time I'm actually failing so what I now have I have an expression over here where pops up P my stack overall success probability the outlier ratio the number of data points s I need to sample and T so I know P because I said it I assume to know e for my data set and I know s because I need to fit my model T is the only unknown in here so it's great so I can now move T to one other side of the equation and then I'm actually able to compute teeth based on P E and s so how do I do this I compute the logarithm of both sides so log of 1 minus P and the logarithm of this equation so if I do this I get block 1 minus P over here since I have the a-team the exponent here this T moves down as a product times the log of the remaining expression ok great so I've T over here I only need to divide this equation by this expression over here move it to the other side and then have my equation for T and that's exactly what I get so the number of trials that I need depends on my success probability that I want to achieve on my outlier ratio and my number of data points that I need to sample so if I have a 40% outlier ratio s equals 5 and I want to have a 99.9 percent success probability I will put in a year 99.9% or 0.999 this is 0.4 and this is 5 and then I can do my expression and compute T and this is number of trial that I need in order to come up with the right solution in a 99.9% of all cases ok so let's have a look on how this T actually looks like for different numbers of data point that I need out by our probabilities and so on so see let's assume we have an outlier probability of 10% so this is shown over here and this is my success probability that I want to have so activities let's say with 95% probability want to be successful always 99 or 99.9 or 99.99 and this is the s so if my out of meets two data points for fitting a line or three or four or five or 10 15 20 you can see the number of trial that you need which are shown in the table increases for increasing success probability and increasing number of data points I need to sample you can see for 10 percent of the outlier cases even for me to estimate 20 parameters and I want to be certain with 99.99% I just need 72 trials that's actually not too much something I can do if the outlier ratio however increases it gets more complicated so with a 30 percent outlier ratio was a small number of parameters s it's still everything looks good but if I have larger number of outlier three points on each sample I'm easily ending up in far more than 10,000 data points than any which is to be something at least can't do for applications that require real time operation and we may even increase it to 50 percent outlier outliers then it turns out that maybe was kind of five parameters you want to estimate you have around 300 trials something you may be able to do but not much more for applications that have strict computational bounds for the operations and if I increase the outlier ratio something like 80 percent I can still say with two three parameters I'm still able to do this but with twenty parameters I have something like 10 to the power of 15 number of trials which is obviously nothing you want to compete in any reasonable amount of time so what we can see is of course the outlier ratio matters the higher the number of outliers are more complicated your problem actually is but the other parameters this s which also plays an important role so even if you have high outliers if you just have a small s you're still good if s increases then it becomes problematic and that's the reason why we are often interested in points for SEO in data acetone sorry in algorithms for estimating our models that require a smaller number of data points small number of data points so for example if you think about the relative orientation so estimating how one camera moved with respect to another if there's an eight-point algorithm in a five-point algorithm eight-point is much easier to do to implement with the five-point algorithms you could say I'm fine with eight points these three points more it's not worth implementing the the additional algorithm but it turns out if you need to do this in the context of rancic which is something you need to do in reality it actually matters because five point is far better than eight points in the context of a large number of outliers so you want to go for those algorithms which requires a small number of s so small s is better especially in situations where you have a large number of outliers and then there's another parameter just to be complete here this threshold when a point is considered to be in there or an outlier that's something which really depends on the model and the quality of your sensor that you're considering parameter you need to put in there but it doesn't affect the number of trials that you actually need to do but with this approach we are able to estimate how many trials do we need assuming we know roughly our outlier ratio and all the other parameters or actually something that I'm supposed to know so rancic in sum is an interesting algorithm because it's very easy to implement very easy to understand and it allows us to robustly deal with outliers it separates our data points into Eliassen outliers so that I can continue working with the in layers I forget the outliers and can run my state estimation algorithm based on the entire zone it works well for real-world situation with something like 1 to maybe eight to ten parameters it of course depends on your outlier ratio but you want to keep as small if if possible if you have parameters with or models as 2030 parameters or anything it's probably not your algorithm of choice the downsides of a rancic is that the computational complexity grows quickly as a fraction of outliers increase especially for larger values or not small values of s something you keep in mind to keep in mind and what rancic also doesn't do very well is estimating multiple fits so you're going to have multiple lines or multiple hypotheses for something being extracted rancic is also not the algorithm that you would actually consider using so common rancic applications are finding correspondence corresponding points and images which is needed for example for computing the fundamental matrix or the essential matrix versus five-point algorithm I was mentioning this is needed for computing visual odometry information so to estimate how a camera moved through the environment which is basically stacking those essential matrices together for commuting tomography x' for finding the ground plane for doing ICP in the context of laser based scan matching were in the context of connect based matching of images they're all techniques where rancic plays an important role again the problem with rancic is may be computationally expensive if you have a lot of outliers but it's the standard gold standard way today for separating data points into Elias and outliers so to summarizes rancic is the standard tool for performing fitting tasks in the presence of outliers it's a trial and error approach and if I need to explain it in 30 seconds or even less we could say guess a subset of inliers from a data points computer model given this guesst data points and then score the model by testing how the remaining data points and the model are consistent with each other count it repeat the process over and over again and take the result which has the highest score and that's basically and the number of repetitions you need to do depends on this T that I showed on how to compute so thank you very much for attention I hope that was useful for performing state estimation problems in the presence of outliers and helps you to get the idea on how Branson actually works thank you

Channel: Cyrill Stachniss

Views: 12,815

Keywords: robotics, photogrammetry

Id: Cu1f6vpEilg

Length: 25min 51sec (1551 seconds)

Published: Tue Apr 14 2020