top
parlab publications > thesesThe iterative closest point (ICP) algorithm is considered in this work as our basic registration method. The ICP algorithm processes iteratively. At each iteration, it first creates closest point correspondences between two datasets and it then minimizes the average distance of the couplings by a rigid transformation.
The matching quality and the robustness of the ICP can be improved by considering additional features, such as colour or curvature and by adding weights to the couplings found in the first step of each iteration.
The main practical difficulty of the ICP algorithm is that it requires heavy computations and, thus, several speeding up methods have been proposed. A fairly complete review of the different methods is proposed in this work. The main conclusion of this review is that most of the existing solutions lead to a tradeoff between speeding up and quality of the matching.
Two new algorithms are proposed to accelerate the ICP. First of all, the neighbour search algorithm, which relies on neighbourhood relationships in the datasets to restrict the search of the closest point to a local subset. Then, a multi-resolution scheme is also proposed and analysed. It proceeds from coarse to fine and successively improves a previous solution at the finer representation level. One can note that both solutions for the speeding up of the ICP have been developed in a perspective to avoid the tradeoff with matching quality that is imposed by most existing solutions.
Finally, a complete object digitising system is presented. It combines data from several unpositioned range images or 3D meshes taken from different viewpoints to create a complete virtual model. In addition to showing a practical use for the registration techniques described above, building the system also permitted the development of new algorithms and methods for colour digitising, mesh fusion and texture handling.
« appariement géométrique rapide pour la mise en correspondance de formes »
La recherche présentée dans ce travail de thèse contribue au développement de la vision tridimensionnelle (3D). Plus précisément, elle aborde le problème de la mise en correspondance géométrique de données 3D, qui consiste à déterminer l’alignement relatif correct de ces ensembles de données en se basant uniquement sur leurs propriétés intrinsèques. Parmi les applications typiques utilisant la mise en correspondance, on peut citer la modélisation d’objet 3D, la reconnaissance d’objet ou encore l’inspection de qualité.
L’algorithme ICP (pour « Iterative Closest Point ») est la méthode de mise en correspondance de base considérée dans ce travail. L’ICP procède itérativement, comme son nom l’indique. A chaque itération, les points correspondants les plus proches entre deux ensembles de données sont tout d’abord définis. La distance moyenne des couples précédemment créés est ensuite minimisée par une transformation rigide.
La qualité de la mise en correspondance ainsi que sa robustesse peuvent être améliorées en faisant appel à des caractéristiques supplémentaires liées aux objets, comme la couleur ou la courbure, et en pondérant les couples créés dans la première partie de chaque itération.
La principale difficulté pratique de l’ICP est qu’il nécessite un nombre élevé de calculs. En conséquence, plusieurs méthodes ont été développées afin de l’accélérer. Une revue aussi complète que possible de ces méthodes est proposée dans ce travail. Sa conclusion majeure est que la plupart des solutions existantes nécessitent un compromis entre accélération et qualité de la mise en correspondance.
Deux nouveaux algorithmes pour l’accélération de l’ICP sont aussi proposés. Premièrement l’algorithme de recherche de voisinage (neighbour search algorithm) qui compte sur les relations de voisinage existant dans les données pour restreindre l’espace de recherche des points les plus proches à un sous-ensemble des données. Deuxièmement, un schéma multi-résolution est suggéré et analysé. Il procède de façon « grossière à fine » et améliore successivement la mise en correspondance avec un niveau de représentation des données de plus en plus fin. On notera que ces deux solutions ont été développées dans l’optique d’éviter tout compromis avec la qualité de la mise en correspondance.
Finalement, un système complet de digitalisation 3D d’objets est présenté. Il combine les données de plusieurs images de profondeur ou de maillages 3D pris sous différents points de vue afin de créer un modèle virtuel complet. En plus d’illustrer une utilisation pratique des techniques de mise en correspondance décrites précédemment, la mise au point de ce système a également permis le développement de nouveaux algorithmes pour l’acquisition de la couleur, la fusion de maillages ainsi que l’utilisation de textures.