From: Xiaowei L. <ne...@bi...> - 2004-11-18 03:49:34
|
Hi vxl guys, I have several questions about estimate methods in VXL. 1 All these methods, both in RPI libraries and Oxford University Libraries, are all based on random sampling, right ? This point can be demonstrated in the source code, as in RPIL, there is a random sampling class, and in oxl's mvl, there exists Monte_Carlo function to achieve random sampling. 2 So, all these methods are different in residual computation and cost functions, including RANSAC itself, right? 3 If yes, delving in the source code, the final estimate value we get is surely a value solved from the minimal fit of certain sample, right ? Of course this value have the "most" number of inliers among all the data. But, 4 Is this estimate value reliable enough ? It is an algebraic solution of certain equations in a minimal fit. Though this fit must be made up from inliers, noise still exists and the final value is different from different minimal fits being used. It will result in this: 5 Though all the data are inliers, when we estimate certain parameters with them for many times, the final estimate value we get will be different, because we use different samples to generate the estimate value. Is this statement right ? Thanks in advance.;) Xiaowei Li Regards, |
From: Amitha P. <pe...@cs...> - 2004-11-18 15:52:05
|
On Wed 17 Nov 2004, Xiaowei Li wrote: > 1 All these methods, both in RPI libraries and Oxford > University Libraries, are all based on random sampling, right > ? The rpl/rrel implements both a random sampling search and a iteratively re-weighted least squares search. Some objective functions, such as MUSE and RANSAC, can only be effectively minimized using random sampling because the objective functions are complex (MUSE) or discontinuous (RANSAC). Others, like MSAC, the Beaton-Tukey weight, and least squares, can be minimized using either approach. When both options are available, random sampling has an advantage in that it does not need an initial estimate. IRLS has an advantage that the minimum need not be defined by exactly a few data points. > 2 So, all these methods are different in residual computation and cost functions, including RANSAC itself, right? There are, conceptually, two phases to finding a robust minimum. First, you have to compute residuals. This depends on your problem. Then you run the residuals through the robust loss function, and minimize the this. If the residuals and scale are estimated the same way, RANSAC is RANSAC. (I don't know the code in mvl to comment further.) > 3 If yes, delving in the source code, the final estimate > value we get is surely a value solved from the minimal fit of > certain sample, right ? Yes. (For random sampling.) > 4 Is this estimate value reliable enough ? > It is an algebraic solution of certain equations in a > minimal fit. Though this fit must be made up from > inliers, noise still exists and the final value is > different from different minimal fits being used. There will always be an error in your estimates. They are, after all, estimates. The more samples you have, the more likely that random sampling will give an estimate close to the true value. Suppose you need n points for the minimal esteimate. The idea is that if you have m >> n samples, then it is likely that there are n of these m that have very little noise. If you find this set, you can get an estimate very close to the true value. As m gets larger, it becomes more and more likely that there are n samples with zero error; in this case, you can find the true solution. Of course, all this becomes more complicated because you can only evaluate the quality of your solution using the samples. However, as m gets larger, it becomes more and more likely that the only the true solution will minimize the error function. If you have enough samples, and your samples meet the expected noise models, the estimate should be quite good. > It will result in this: > 5 Though all the data are inliers, when we estimate certain parameters with them for many times, the final estimate value we get will be different, because we use different samples to generate the estimate value. > Is this statement right ? Yes. For a given sample set, different runs of a random sampling search will yield slightly different results. Different runs of an iterative search will generally yield the same result. However, this repeatability does not mean the iterative search gives you the "true" solution: get another sample set, and the estimates from both approaches are different. Remember that the data you have is not "truth". It is a set of noisy samples from the truth that you are trying to estimate. Therefore, any estimate will not equal truth. (At least, you cannot be certain of it.) Amitha. |