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
reweighted 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 BeatonTukey 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.
