ressearch project afm

parlab

research> activities

Research projects

Fast geometric matching

Timothée Jost

Keywords

Computer vision, geometric matching, iterative closest point, algorithms, complexity

Matching complexity

The iterative closest point (ICP) algorithm is widely used for the registration of geometric data.One of the main drawback of the algorithm is its time complexity O(N2), quadratic with the shape size N, which implies long processing time, especially when using high resolution data.

Fig. 1. Initial configurations of shapes to be matched by ICP

Fast matching

An effective method used to accelerate the matching uses a tree search (k-D tree) to establish closest point relationships and reduces the complexity to O(N logN). In this work a new, even less complex ICP algorithm, that uses a heuristic approach to find the closest points was proposed and analyzed. Based on a local search it permits to reduce the complexity to O(N) and to greatly accelerate the process.

Neighbor search

Results from a series of registration experiments show that the proposed neighbor search algorithm performs significantly better than a tree search.

Fig. 2. Initial configurations of shapes to be matched by ICP

The theoretical complexity of O(N) was practically reached. Also, the method improves the computation speed of the ICP algorithm, without altering the matching error and the domain of convergence. The results show that, in nearly all cases, the ICP registration that uses the neighbor search still converges toward the same position as when using an exact closest points search. This confirms the good potential of the proposed method.

References

[1] T. Jost & H. Hugli, "A multi-resolution scheme ICP algorithm for fast shape registration", Proc. Int. Symp. 3D Data Processing , Visualisation and Transmission, Padova, Italy, June 19-21, 2002

[2] T. Jost & H. Hügli, "Fast ICP algorithms for shape registration", submitted