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

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.

Quantitative stability of linear infinite inequality systems under block perturbations with applications to convex systems

The original motivation for this paper was to provide an efficient quantitative analysis of convex infinite (or semi-infinite) inequality systems whose decision variables run over general infinite-dimensional (resp. finite-dimensional) Banach spaces and that are indexed by an arbitrary fixed set J. Parameter perturbations on the right-hand side of the inequalities are required to be merely bounded, and thus the natural parameter space is l ∞(J). Our basic strategy consists of linearizing the parameterized convex system via splitting convex inequalities into linear ones by using the Fenchel–Legendre conjugate. This approach yields that arbitrary bounded right-hand side perturbations of the convex system turn on constant-by-blocks perturbations in the linearized system. Based on advanced variational analysis, we derive a precise formula for computing the exact Lipschitzian bound of the feasible solution map of block-perturbed linear systems, which involves only the system’s data, and then show that this exact bound agrees with the coderivative norm of the aforementioned mapping. In this way we extend to the convex setting the results of Cánovas et al. (SIAM J. Optim. 20, 1504–1526, 2009) developed for arbitrary perturbations with no block structure in the linear framework under the boundedness assumption on the system’s coefficients. The latter boundedness assumption is removed in this paper when the decision space is reflexive. The last section provides the aimed application to the convex case.

Lower semicontinuity of the feasible set mapping of linear systems relative to their domains

This paper deals with stability properties of the feasible set of linear inequality systems having a finite number of variables and an arbitrary number of constraints. Several types of perturbations preserving consistency are considered, affecting respectively, all of the data, the left-hand side data, or the right-hand side coefficients.

Stability in Linear Optimization Under Perturbations of the Left-Hand Side Coefficients

This paper studies stability properties of linear optimization problems with finitely many variables and an arbitrary number of constraints, when only left hand side coefficients can be perturbed. The coefficients of the constraints are assumed to be continuous functions with respect to an index which ranges on certain compact Hausdorff topological space, and these properties are preserved by the admissible perturbations. More in detail, the paper analyzes the continuity properties of the feasible set, the optimal set and the optimal value, as well as the preservation of desirable properties (boundedness, uniqueness) of the feasible and of the optimal sets, under sufficiently small perturbations.

On Gruenhage spaces, separating σ-isolated families, and their relatives

We prove that, given a topological space X, the following conditions are equivalent. (α) X is a Gruenhage space. (β) X has a countable cover by sets of small local diameter (property SLD) by F∩G sets. (γ) X has a separating σ-isolated family M⊂F∩G. (δ) X has a one-to-one continuous map into a metric space which has a σ-isolated base of F∩G sets. Besides, we provide an example which shows Fragmentability ⇏ property SLD ⇏ the space to be Gruenhage.