Contributions Au Developpement D Algorithmes Robustes Pour L Identification Des Defauts Geometriques De Forme A Partir D Un Nuage De Points

Contributions au développement d'algorithmes robustes pour l'identification des défauts géométriques de forme à partir d'un nuage de points

Reconstruction de formes tubulaires à partir de nuages de points

Le coeur de cette thèse porte sur la modélisation géométrique et introduit une méthode robuste d'extraction de formes tubulaires à partir de nuages de points. Nous avons choisi de tester nos méthodes dans le contexte applicatif de la foresterie pour mettre en valeur la robustesse de nos algorithmes.Nos méthodes intègrent les normales aux points, il est donc nécessaire de les pré-calculer. Notre premier développement a alors consisté à présenter une méthode rapide d'estimation de normales. Pour ce faire nous avons approximé localement la géométrie du nuage de points en utilisant des "patchs" lisses dont la taille s'adapte à la complexité locale des nuages de points.Nos travaux se sont ensuite concentrés sur l'extraction robuste de formes tubulaires dans des nuages de points occlus, bruités et de densité inhomogène. Nous avons développé une variante de la transformée de Hough que nous avons couplé à une proposition de contours actifs indépendants de leur paramétrisation. Notre méthode a été validée en environnement forestier pour reconstruire des troncs d'arbre afin d'en relever les qualités par comparaison à des méthodes existantes.La reconstruction de troncs d'arbre ouvre d'autres questions dont la segmentation des arbres d'une placette forestière. Nous proposons également une méthode de segmentation pour isoler les différents objets d'un jeu de données.Durant nos travaux nous avons utilisé des approches de modélisation pour répondre à des questions géométriques, et nous les avons appliqué à des problématiques forestières. Il en résulte un pipeline de traitements cohérent qui, bien qu'illustré sur des données forestières, est applicable dans des contextes variés.

Détermination automatique de structures géométriques destinées à la reconstitution de courbes et de surfaces à partir de données ponctuelles

CETTE ETUDE CONSISTE A ELABORER DES ALGORITHMES, BASES SUR DES CRITERES GEOMETRIQUES, PERMETTANT DE RECONSTRUIRE UNE COURBE OU UNE SURFACE, A PARTIR D'UNE REPRESENTATION SOUS FORME PONCTUELLE. IL S'AGIT, CONNAISSANT UNIQUEMENT LES COORDONNEES D'UN ENSEMBLE DE N POINTS, DE DETERMINER SOIT UNE LIGNE POLYGONALE, SOIT UNE SURFACE POLYEDRALE A FACES TRIANGULAIRES, AYANT POUR SOMMETS CES POINTS, ET QUI CONVERGE UNIFORMEMENT VERS LA COURBE OU LA SURFACE INITIALE, LORSQUE LE NOMBRE DE POINTS N TEND VERS L'INFINI. L'ORIGINALITE DE CETTE ETUDE RESIDE A LA FOIS DANS LE FAIT QU'AUCUNE STRUCTURE SUR LES DONNEES N'EST CONNUE INITIALEMENT, ET DANS L'APPROCHE THEORIQUE DEVELOPPEE POUR VALIDER LES METHODES PROPOSEES. DE NOMBREUSES APPLICATIONS PRATIQUES EN RECONNAISSANT DE FORME, EN VISION PAR ORDINATEUR, EN IMAGERIE MEDICALE, ONT SUSCITE DE L'INTERET POUR CE TYPE D'ETUDE, QUI PEUT EGALEMENT CONSTITUER UNE ETAPE PRELIMINAIRE A DES PROBLEMES D'INTERPOLATION DE DONNEES. DANS LE CAS OU LES POINTS SONT SITUES SUR UNE COURBE, CE PROBLEME REVIENT A DETERMINER UN ORDRE SUR CES DONNEES. NOUS PRESENTONS DEUX CRITERES QUI NOUS PERMETTENT D'OBTENIR LES RESULTATS DE CONVERGENCE SOUHAITES, POUR UNE GRANDE VARIETE DE COURBES. NOUS DEMONTRONS EGALEMENT QUE CES DEUX ALGORITHMES, DONT LA COMPLEXITE TEMPORELLE MOYENNE EST EN O(N LOG N), PERMETTENT DE SEPARER LES POINTS SELON CHAQUE COMPOSANTE CONNEXE DE LA COURBE SUR LAQUELLE ILS SE TROUVENT ET DE DETERMINER SES EVENTUELLES EXTREMITES. CES DEUX ALGORITHMES SONT ILLUSTRES PAR DE NOMBREUX EXEMPLES ET DIVERSES APPLICATIONS PRATIQUES, DONT DEUX ONT ETE REALISEES EN COLLABORATION AVEC L'AEROSPATIALE ET LE CENTRE D'ETUDE ET DE RECHERCHE DE TOULOUSE. DANS UNE SECONDE PARTIE, NOUS ETENDONS CETTE ETUDE AU CAS OU LES POINTS INITIAUX SONT SITUES SUR UNE SURFACE CONNEXE. NOUS PRESENTONS UN PREMIER ALGORITHME, QUI CONSISTE A MAXIMISER L'ANGLE DIEDRE SITUE ENTRE DEUX FACES ADJACENTES DE LA SURFACE POLYEDRALE, ET QUI PERMET DE TRAITER LE CAS DE SURFACES FERMEES CONVEXES. PUIS NOUS ADAPTONS CE CRITERE AU CAS DE SURFACES FERMEES NON CONVEXES ET NOUS PRESENTONS UNE HEURISTIQUE PERMETTANT DE TRAITER LE CAS DE SURFACES A BORD. LA COMPLEXITE TEMPORELLE MOYENNE DE CES ALGORITHMES, QUI ONT ETE ILLUSTRES PAR DIVERS EXEMPLES NUMERIQUES, EST EN O(N LOG N)