Convergence analysis and validation of low cost distance metrics for computational cost reduction of the Iterative Closest Point algorithm

Please use this identifier to cite or link to this item: http://hdl.handle.net/10045/51355
Información del item - Informació de l'item - Item information
Title: Convergence analysis and validation of low cost distance metrics for computational cost reduction of the Iterative Closest Point algorithm
Authors: Mora, Higinio | Mora Pascual, Jerónimo Manuel | Martínez González, Pablo | Garcia-Garcia, Alberto
Research Group/s: Informática Industrial y Redes de Computadores
Center, Department or Service: Universidad de Alicante. Departamento de Tecnología Informática y Computación
Keywords: Computational architecture | Iterative Closest Point | Computational geometry | Computational efficiency | Convergence of numerical methods | Error analysis
Knowledge Area: Arquitectura y Tecnología de Computadores
Issue Date: 5-Sep-2014
Publisher: Universitat Politècnica de València. Instituto Universitario de Matemática Multidisciplinar
Citation: Modelling for Engineering & Human Behaviour 2014 / Ed. by Lucas Jódar, Luis Acedo, Juan Carlos Cortés and Juan Ramón Torregrosa. Valencia: Instituto Universitario de Matemática Multidisciplinar, Universitat Politècnica de València, 2014. ISBN 978-84-606-5746-0, pp. 223-227
Abstract: The Iterative Closest Point algorithm (ICP) is commonly used in engineering applications to solve the rigid registration problem of partially overlapped point sets which are pre-aligned with a coarse estimate of their relative positions. This iterative algorithm is applied in many areas such as the medicine for volumetric reconstruction of tomography data, in robotics to reconstruct surfaces or scenes using range sensor information, in industrial systems for quality control of manufactured objects or even in biology to study the structure and folding of proteins. One of the algorithm’s main problems is its high computational complexity (quadratic in the number of points with the non-optimized original variant) in a context where high density point sets, acquired by high resolution scanners, are processed. Many variants have been proposed in the literature whose goal is the performance improvement either by reducing the number of points or the required iterations or even enhancing the complexity of the most expensive phase: the closest neighbor search. In spite of decreasing its complexity, some of the variants tend to have a negative impact on the final registration precision or the convergence domain thus limiting the possible application scenarios. The goal of this work is the improvement of the algorithm’s computational cost so that a wider range of computationally demanding problems from among the ones described before can be addressed. For that purpose, an experimental and mathematical convergence analysis and validation of point-to-point distance metrics has been performed taking into account those distances with lower computational cost than the Euclidean one, which is used as the de facto standard for the algorithm’s implementations in the literature. In that analysis, the functioning of the algorithm in diverse topological spaces, characterized by different metrics, has been studied to check the convergence, efficacy and cost of the method in order to determine the one which offers the best results. Given that the distance calculation represents a significant part of the whole set of computations performed by the algorithm, it is expected that any reduction of that operation affects significantly and positively the overall performance of the method. As a result, a performance improvement has been achieved by the application of those reduced cost metrics whose quality in terms of convergence and error has been analyzed and validated experimentally as comparable with respect to the Euclidean distance using a heterogeneous set of objects, scenarios and initial situations.
URI: http://hdl.handle.net/10045/51355
ISBN: 978-84-606-5746-0
Language: eng
Type: info:eu-repo/semantics/conferenceObject
Rights: © Los autores
Peer Review: si
Publisher version: http://jornadas.imm.upv.es/Modelling2014
Appears in Collections:INV - I2RC - Comunicaciones a Congresos, Conferencias, etc.

Files in This Item:
Files in This Item:
File Description SizeFormat 
ThumbnailResumen-extendido-ICP.pdf260,94 kBAdobe PDFOpen Preview


Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.