I found many resources online talking about nearest neighbor concept in RANSAC. For example, figure 2 of this paper, this article and this repo talk about nearest neighbor in the context of RANSAC. But they dont explain it clearly exactly for what they are utilising nearest neighbor concept in RANSAC. May be I am too dumb to get the obvious intuition or may be because they have not put it in pseudocode.

I understand below pseudo code of RANSAC from wikipedia. Can you please explain at what step and for what nearest neighbor is used in RANSAC. Also, it will be best if you can modify below pseudocode to explain the same. Also, I am using RANSAC for aligning two point clouds. So it will be great if you can explain in that context. If not, thats fine too, as I can derive understanding for my problem context. You may just explain in the context of usual model fitting problem.

    data – A set of observations.
    model – A model to explain the observed data points.
    n – The minimum number of data points required to estimate the model parameters.
    k – The maximum number of iterations allowed in the algorithm.
    t – A threshold value to determine data points that are fit well by the model (inlier).
    d – The number of close data points (inliers) required to assert that the model fits well to the data.

    bestFit – The model parameters which may best fit the data (or null if no good model is found).

iterations = 0
bestFit = null
bestErr = something really large // This parameter is used to sharpen the model parameters to the best data fitting as iterations go on.

while iterations < k do
    maybeInliers := n randomly selected values from data
    maybeModel := model parameters fitted to maybeInliers
    confirmedInliers := empty set
    for every point in data do
        if point fits maybeModel with an error smaller than t then
             add point to confirmedInliers
        end if
    end for
    if the number of elements in confirmedInliers is > d then
        // This implies that we may have found a good model.
        // Now test how good it is.
        betterModel := model parameters fitted to all the points in confirmedInliers
        thisErr := a measure of how well betterModel fits these points
        if thisErr < bestErr then
            bestFit := betterModel
            bestErr := thisErr
        end if
    end if
    increment iterations
end while

return bestFit


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.