Paramètres agissants sur la rapidité des algorithmes de localisation

Paramètres agissants sur la rapidité des algorithmes de localisation 

L’un des soucis qui préoccupe un chercheur dans ce domaine est la rapidité des algorithmes utilisés pour la localisation, puisque le temps d’exécution est déterminant pour l’applicabilité et la rentabilité d’une technique dans l’industrie.

Les facteurs agissants sur la rapidité du processus de la localisation sont généralement : la méthode mathématique sur la quelle est basé l’algorithme de localisation, le nombre optimal de points nécessaire pour l ‘obtention de la précision voulue, et finalement la complexité de la géométrie de la pièce.

La méthode mathématique utilisée pour développer les algorithmes 

Dans ce contexte, YX Chu, J .B Go, H. Wu et Z. X. Li[ 1 0] ont testé trois algorithmes pour aligner un nuage de points, relevé sur un modèle théorique d’une pale de turbine, avec ce même modèle, de façon à connaître d’avance la solution exacte de l’alignement. Ces trois algorithmes sont: l’algorithme variationnel, l’algorithme de tangente et l’algorithme de Hong-Tan. Les résultats ont montré l’efficacité de tous ces algorithmes, pm· contre, celui de Hong-Tang s’est avéré le plus rapide.

D’autres résultats pertinents ont été présentés par Thoma M. Tucker et Thoma R. Kurfesse[ Il]. Leur idée est de reformuler la méthode de Newton, une méthode qui a été écartée dans le passé à cause de sa faiblesse, pour la rendre plus robuste. Comme il est connu, le principe de cette méthode est simple. Il s’agit de chercher le minimum d’une fonction en la développant en séries de Taylor. Il suffit donc de calculer sa dérivée première et seconde et de chercher le point oü la dérivée première s’annule et la dérivée seconde est positive. Mais pour calculer la dérivée seconde, les auteurs proposent quatre méthodes appelées : méthode de Newton, méthode de Gauss-Newton, méthode Quasi Newton et la méthode de Gauss-Newton augmentée.

Toutes ces méthodes ont été comparées à deux algorithmes couramment utilisés, et qui sont : l’algorithme ICP usuel et ICP accéléré. Les tests ont porté sur la comparaison du temps de calcul, la précision atteinte et la robustesse de chaque méthode (ici le mot robustesse fait allusion à la capacité de convergence vers un minimum global en fonction de la position relative initiale des deux objets à aligner).

Les résultats ont prouvé la prédominance de la méthode de Gauss-Newton sur les autres méthodes en ce qui concerne le temps de calcul et le nombre d’itérations. Les quatre méthodes de Newton se sont avérées plus précises que les deux autres, mais d’un point de vue robustesse, les algorithmes ICP restent les plus efficaces.

Nombre de points utilisés 

Un deuxième facteur qui peut influencer le temps d’exécution c’est le nombre de points à traiter lors de l ‘opération de localisation.

Il est presque évident que la précision de la localisation s’améliore de mieux en mieux si le nombre de points relevé sur l’objet à inspecter augmente jusqu’à un seuil à partir duquel l’amélioration de la précision devient négligeable. Ceci a été prouvé par ChiaHsiang et al [ 12], qui ont étudié l’ effet du nombre de points ainsi que de leur emplacement, sur la précision de l’alignement d’un ensemble de points avec des surfaces modélisées par la CAO. Leur conclusion stipulait que le choix de l’emplacement des points agit beaucoup sur le nombre de points nécessaires pour l’alignement avec une précision donnée. Cette précision dépend à son tour des tolérances demandées pour l’acceptation de l’ objet inspecté. Néanmoins, les critères aidant pour le choix de l’emplacement des points ne sont pas définis d’une façon explicite, ils sont laissés à l’intuition.

Caractéristiques géométriques des pièces 

Un autre élément qui peut intervenir dans la rapidité de ces algorithmes c’est la géométrie des pièces. En effet, l’alignement des pièces symétriques représente un cas spécial, puisque, théoriquement la solution n’est pas unique. L’existence de plusieurs ou d’une infinité de solutions peut engendrer la divergence de certains algorithmes dépendamment de leur base mathématique. D’ailleurs, Zexiang Li et al. [ 13] ont prouvé que l’algorithme de Hong-Tan n’est pas applicable à ce genre de pièce. Mais en contre partie, l’élaboration d’un algorithme exclusif à des pièces symétriques peut être bénéfique du point de vue temps de calcul.

Types d’alignement 

L’opération d’alignement peut se faire de trois façons: alignement type point/point, alignement type point/ surface et alignement type surface/surface. Les deux premiers types sont les plus utilisés à cause de leur simplicité mathématique. D’ailleurs, presque la totalité des travaux présentés dans ce chapitre utilisent l’alignement de type points/surface.

Malheureusement, peu de travaux se sont basés sur l’alignement surface/surface vue la complexité de ce problème. Cependant, K.H. Ko et al [14] ont proposé une nouvelle méthode pour aligner deux surfaces modélisées par les NURBS. La technique consiste à choisir manuellement trois points sur une première surütce, ensuite, et en chaque point, calculer la courbure moyenne et la courbure gaussienne. Les trois points sont choisis de telle sorte qu’ils ne soient pas alignés entre eux et que ce choix pourra assurer une solution unique  . D’autre part, la deuxième surface est subdivisée en de petites entités surfaciques afin de pouvoir calculer les courbures moyennes et gaussiennes au centre de chacune de ces entités. Ainsi, le problème se réduit en une résolution d’un système d’équations pour attribuer à chaque point du triplet choisi précédemment, son équivalent sur la deuxième surface. Avec un bon choix du triplet, la solution est vite obtenue.

On constate que le principal avantage de cette technique est son indépendance de la position relative des deux surfaces, qui est propice à l’automatisation de l’inspection.

Toutefois, plusieurs inconvénients constituent un handicap majeur pour la généralisation de cette technique, car il ne faut pas oublier que la première surface est reconstruite à partir d’un nuage de points relevé sur une pièce réelle, alors que la deuxième pièce représente la pièce nominale. Ce qui implique que ces deux surfaces ne possèdent pas nécessairement les mêmes caractéristiques géométriques. D’autre part, les courbures moyennes et gaussiennes sont des grandeurs de deuxième ordre, donc très sensibles aux bruits causés lors de l’opération de numérisation de la pièce à inspecter.