A novel solution is presented to the Nearest Neighbor Problem that is specifically tailored for determining correspondences within the Iterative Closest Point Algorithm. The reference point set P is preprocessed by calculating for each point p/spl I.oarr//sub i//spl isin/P that neighborhood of points which lie within a certain distance /spl epsiv/ of p/spl I.oarr//sub i/. The points within each /spl epsiv/-neighborhood are sorted by increasing distance to their respective p/spl I.oarr//sub i/. At runtime, the correspondences are tracked across iterations, and the previous correspondence is used as an estimate of the current correspondence. If the estimate satifies a constraint, called the Spherical Constraint, then the nearest neighbor falls within the /spl epsiv/-neighborhood of the estimate. A novel theorem, the Ordering Theorem, is presented which allows the Triangle Inequality to efficiently prune points from the sorted /spl epsiv/-neighborhood from further consideration. The method has been implemented and is demonstrated to be more efficient than both the k-d tree and Elias methods. After /spl sim/40 iterations, fewer than 2 distance calculations were required on average per correspondence, which is close to the theoretical minimum of 1. Furthermore, after 20 iterations the time expense per iteration was demonstrated to be negligibly more than simply looping through the points.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A nearest neighbor method for efficient ICP


    Beteiligte:
    Greenspan, M. (Autor:in) / Godin, G. (Autor:in)


    Erscheinungsdatum :

    2001-01-01


    Format / Umfang :

    948106 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    A Nearest Neighbor Method for Efficient ICP

    Greenspan, M. / Godin, G. / National Research Council of Canada | British Library Conference Proceedings | 2001


    3DNN: 3D Nearest Neighbor

    Satkin, S. / Rashid, M. / Lin, J. et al. | British Library Online Contents | 2015


    Efficient Nearest Neighbor Search on Metric Time Series

    Schäfer, Jörg Peter | Deutsches Zentrum für Luft- und Raumfahrt (DLR) | 2022

    Freier Zugriff

    Nearest neighbor search for relevance feedback

    Tesic, J. / Manjunath, B.S. | IEEE | 2003


    LDA/SVM driven nearest neighbor classification

    Jing Peng, / Heisterkamp, D.R. / Dai, H.K. | IEEE | 2001