Qualité de la détection des contours par notre algorithme alpha-shape en langage python

Les recherches scientifiques sur la donnée 3D

Des recherches scientifiques ont été menées sur ce sujet à l’échelle planétaire par différents laboratoires et organismes. En effet, avec l’émergence de la donnée 3D, les scientifiques se sont intéressés d’une part aux limites des appareils d’acquisition de données 3D et d’autre part, aux différentes possibilités de segmentation sur nuage de points permettant d’extraire les points de contours au sein du nuage.

Les paramètres influant sur les mesures d’acquisition 3D

Comme le démontre plusieurs études scientifiques, les erreurs de positionnement géométriques dépendent directement de la portée d’acquisition. En effet, plus la portée est petite, meilleure est la précision géométrique. S’agissant de l’intensité laser, celle-ci est peu influencée par la distance d’acquisition mais diminue lorsque l’angle d’incidence du laser s’éloigne de la normale au mur.

Justification du choix de la deuxième méthode

Après avoir établi deux processus permettant d’aboutir au résultat souhaité, nous avons décidé d’orienter la suite de notre étude sur la deuxième approche pour plusieurs raisons.
En effet, la première méthode est d’avantage chronophage que la seconde car elle nécessite plusieurs opérations avant de débuter véritablement la détection de contours. De plus, Définir les conditions d’acquisition : résolution, éclairage, distance lorsque les contours sont identifiés sur l’orthoimage, une dernière étape reste nécessaire pour intégrer ces contours sur le nuage de points initial . L a deuxième méthode, quant à elle, propose un traitement basé uniquement sur le nuage de points assurant ainsi non seulement un temps de traitement plus efficace mais aussi une continuité de la donnée. Par ailleurs, les bâtiments concernés par cette étude sont des édifices dont l’intérieur est relativement sombre (églises, châteaux). Ainsi, le traitement sur orthoimages proposé par la première méthode est limité ici car il s’appuie sur la couleur de l’image. Or, si l’image est sombre, la distinction des pierres et des joints de l’édifice est i mpossible. L’avantage que présente la deuxième méthode, et nous le verrons plus nettement dans la section suivante, c’est qu’il est possible de traiter le nuage de points selon la couleur mais aussi selon l’intensité laser.
Comme nous avons pu le voir précédemment, nous savons qu’il est possible de détecter différents types de matériaux (et donc de différencier les joints des pierres) par l’intensité laser.

Présentation des nuages de points

Dans cette partie, il s’agit de présenter quelques exemples de nuages de points acquis par laser scanner terrestre C10 (Leica) et de présenter de manière succincte leurs caractéristiques respectives.

Segmentation par croissance de régions

Présentation de l’algorithme

L’algorithme de croissance de régions consiste à ajouter à chaque point germe, choisi de manière aléatoire dans le nuage, les points situés dans un rayon R fixé autour de celui-ci (en général égal à deux fois la distance moyenne entre les points du nuage) afin de former une surface-germe. Cette surface-germe doit ensuite être validée par un test vérifiant que son critère d’homogénéité est bien en cohérence avec celui de l’élément recherché dans le nuage de points.
Une fois le test validé, la surface-germe s’accroit en se voyant attribuer de nouveaux points selon le principe suivant : pour chaque point constituant la surface-germe, on ajoute un à un les points situés dans un rayon R autour de celui-ci et qui vérifie le test d’homogénéité, agrandissant ainsi la surface-germe initiale. Le processus se poursuit de manière itérative jusqu’à ce qu’aucun point du nuage ne puisse être ajouté à la surface-germe.

Critère d’homogénéité et seuil de validation

La validation du critère d’homogénéité est une étape importante et délicate puisque c’est à partir de celle-ci qu’un point va être ajouté ou non à la liste des points de pierres.
Ainsi, il est important de savoir à quoi correspond le critère d’homogénéité pour pouvoir fixer un seuil de validation adéquate. Pour ce faire, nous avons défini le critère d’homogénéité comme étant égal à la variance des intensité s laser des points de la surface courante : et nous avons fixé la valeur du seuil de proche en proche jusqu’à obtenir un résultat correct. Cette méthode empirique nous a permis d’aboutir à un résultat qui reste exploitable pour la suite de notre étude.

Résultats de la segmentation par croissance de régions

Pour des raisons de rapidité de traitement algorithmique, nous avons testé cette méthode sur un extrait du nuage de points n°1 (Figure 45). En effet, sur le nuage n°1 entier, le traitement s’arrêtait brutalement et ne nous permettait pas d’obtenir de résultats. En revanche, nous avons pu tester la segmentation sur le nuage de points n°2 (Figure 46) car celui-ci possède moins de points que le nuage n°1.

Extraction des points de contours

L’algorithme alpha-shape

Présentation de l’algorithme

L’algorithme alpha-shape permet la reconnaissance de formes générées par des ensembles de points. Grâce à cette méthode basée sur la triangulation de Delaunay, nous sommes alors en mesure d’extraire les points de contours de ces ensembles de points.
La fonction permettant de créer la triangulation de Delaunay en langage python ne prend en arguments que des points définis par deux coordonnées. Ainsi, non seulement une projection sur un plan est nécessaire mais étant donné que nos points actuels constituent des triplets de coordonnées, il est également nécessaire de redéfinir notre système de coordonnées afin que chaque point soit défini par un doublet. À la dernière étape du traitement alpha -shape, nous attribuerons les coordonnées 3D résultant de la projection à chaque point.

Application au nuage résultant de la segmentation par  croissance de régions du nuage de points n°1

Pour appliquer notre méthode alpha-shape et obtenir un résultat satisfaisant, nous sommes contraints de nettoyer à la main notre nuage de points en supprimant les points de joints. En effet, un filtrage automatique sous 3Dreshaper ne nous donnera pas un résultat satisfaisant puisqu’il ne s’agit pas ici de supprimer des points isolés mais des portions de points de joints situées entre des points de pierres. Notons que sur un nuage de points de plus grande taille, ce nettoyage représente un travail long et fastidieux.

Qualité de la détection de contours par notre algorithme alpha-shape en langage python

Dans les deux cas (nuage classifié et filtré/nuage segmenté et nettoyé), nous pouvons considérer que la détection des contours est correcte. En effet, nous distinguons la présence des dix pierres sur les deux résultats. Un traitement manuel reste toutefois nécessaire pour supprimer les quelques anomalies présentent sur les deux résultats.
S’agissant des contours détectés sur le nuage de points classifié et filtré, la faible largeur du joint a entrainé la jonction de deux pierres à deux reprises. En effet, un point a été malencontreusement considéré comme étant un point commun à deux contours de pierres ce qu’il conviendra de rectifier manuellement par l’utilisateur.
Concernant la détection des contours du nuage de points segmenté et nettoyé, un contour a été dessiné à l’intérieur d’un autre. Ce phénomène est dû à la non-sélection de certains points au centre d’une pierre formant un trou qui a été considéré par notre algorithme comme étant un contour. Ceci pourrait être évité par la mise en place d’un contrôle de position des contours par notre algorithme : si un contour est contenu dans un a utre alors nous demandons à l’opérateur s’il est à supprimer ou non.
Ces résultats sont très satisfaisants avec néanmoins une qualité de détection légèrement supérieure sur le nuage de points segmenté et nettoyé puisqu’une seule rectification est à prévoir (au lieu de deux sur le nuage classifié et filtré) . Cela s’explique par le fait que nous avons nettoyé manuellement le nuage de points segmenté alors que le nuage classifié a été filtré par le logiciel 3Dreshaper. Ainsi, la suppression des points de joints sera plus efficace lorsqu’elle sera effectuée manuellement par l’opérateur plutôt que de manière automatique sous 3Dreshaper. Notons toutefois que sans filtrage ou nettoyage préalable du nuage de points , la détection des contours est de meilleure qualité sur le nuage de points classifié.

Détermination des contours avec le logiciel 3DReshaper

Le logiciel 3DReshaper ne permet pas de traiter les nuages de points selon l’intensité laser. À la lecture du nuage de points, le logiciel ne considère que les données de positionnement (x,y,z) et les valeurs R, G et B qui colorisent les points du nuage. Ainsi, nous traiterons dans un premier temps une méthode de reconnaissance des contours sur des nuages ayant fait l’objet d’une segmentation préalable selon l’intensité laser et dans un second temps, une détection des contours basée sur les caractéristiques géométriques du nuage.

Détection des contours à partir d’un maillage : alpha-shape

Ce procédé est constitué de deux étapes : la réalisation d’un maillage 3D sur un nuage de points segmenté et la détection des contours de ce maillage. Ainsi, il s’agit de la méthode alpha-shape. Le maillage utilisé par le logiciel 3DReshaper tient compte de la densité de points pour détecter la présence de trous et compare les dimensions des rayons des cercles circonscrits des triangles voisins pour créer un maillage cohérent. De cette manière, les triangles éliminés sont ceux dont le rayon des cercles circonscrits est supérieur à un maximum prédéfini par le logiciel.
Pour tester cette méthode, nous utilisons les nuages de points résultant de la classification et représentant les points de pierre. En effet, nous ne traiterons pas ce procédé sur les nuages segmentés car, comme nous avons pu l’observer précédemment, la segmentation ne produit pas actuellement de résultats assez satisfaisants pour permettre une dé tection automatique optimale des contours.

Traitement du nuage de points n°1

Nous allons procéder aux étapes suivantes :
– nettoyage du nuage de points
– création d’un maillage 3D
– création des polylignes de contours 3D
– calcul du plan moyen au nuage de points
– projection des polylignes 3D sur le plan pour obtenir des polylignes 2D

Nettoyage du nuage de points n°1

Afin d’obtenir un résultat convenable, il est nécessaire de nettoyer préalablement notre nuage de points. En effet, bien que la classification réalisée soit satisfaisante, celle-ci comporte des erreurs. Nous pouvons observer par endroit des jonctions entre les pierres qui ne devraient pas exister et qui résultent d’une mauvaise classification des points de joints en points de pierres .
Ces jonctions seront source d’erreurs pour notre détection de contours puisque si les pierres ne sont pas bien séparées les unes des autres, le logiciel considérera l’ensemble comme une seul entité et formera un contour englobant plusieurs pierres.
S’agissant de la qualité de détection du second nuage, celle-ci est beaucoup moins satisfaisante que pour le premier nuage. Cette qualité découle directement de la qualité de classification du nuage réalisée dans la partie II.1. En effet, cette détection de contours se base sur cette classification qui, comme nous avons pu le voir précédemment, est de moins bonne qualité que celle du premier nuage de points.
Cette première méthode proposée par 3DReshaper nous permet non seulement d’obtenir les polylignes des contours des pierres en 3D et 2D mais présente également l’avantage de pouvoir les exporter au format DXF et de les exploiter sous AutoCAD comme il est demandé dans le cahier des charges.
De plus, la dégradation des données lors de la projection des polylignes 3D sur un plan est négligeable au vue des faibles valeurs de l’écart-type et de la variance des écarts entre le nuage de points et le plan ce qui nous assure une bonne qualité des coordonnées.
En outre, la qualité de détection des contours dépend directement de la qualité de classification du nuage de points à l’entrée du processus. Ainsi, pour un nuage correctement classifié, la détection est très satisfaisante avec un taux de réussite de l’ordre de 95,62%.
Ainsi, nous pouvons considérer que cette méthode répond à la problématique de ce TFE tout en respectant le cahier des charges.

Détection des contours par extraction des lignes de rupture de pente

Cette deuxième méthode consiste en la création d’un maillage du nuage de points initial à partir duquel seront extraites les lignes de rupture de pente correspondantes aux contours des pierres. L’application de ce procédé nécessite donc un nuage de points où les joints doivent être en léger retrait par rapport aux pierres, comme c’est le cas sur notre nuage.

Réalisation d’un maillage en deux étapes

Cette méthode nécessite la réalisation d’un maillage en deux étapes afin d’assurer une précision des contours (Figure103) :
– maillage selon un échantillonnage régulier de 2cm.
– maillage affiné par interpolation de nouveaux points et calcul de l’« erreur cordale avec les meilleurs points uniquement » (pour ne sélectionner que les points les moins bruités).

Analyses et choix des méthodes

Étape 2 : Détection des points de pierres par classification ou segmentation par croissance de régions

Comme nous avons pu le voir précédemment, cette étape de détection des points de pierres est la plus importante de notre processus puisque c’est à partir de ce résultat que la reconnaissance des contours va être effectuée.
Actuellement, la méthode de classification nous donne de meilleurs résultats que celle de segmentation par croissance de régions. En effet, une étude plus approfondie sur la fixation du seuil de validation du critère d’homogénéité serait nécessaire pour une meilleure sélection des points de pierres. Les taux de réussite et de fausses alarmes de la segmentation, respectivement de 98,88% et de 8,60% pour le nuage de ponts n°1, illustrent parfaitement le phénomène rencontré : trop de points du nuage ont été sélectionnés.
Ainsi, nous retenons la méthode de classification avec un taux de bonne détection des points de pierres de 93,39% et un taux de fausses alarmes de seulement 3,36% pour assurer un meilleur résultat de notre processus de détection de contours.
Cependant, des travaux complémentaires seront nécessaires pour rendre robuste le choix du seuil de binarisation à un panel plus large de cas possibles.

Étape 3 : Élimination des points isolés par filtrage/nettoyage du nuage

Pour assurer une détection correcte des contours de pierres, il est indispensable d’éliminer les points isolés correspondant aux points malencontreusement conservés lors de la classification du nuage. L’outil de filtrage proposé par 3DReshaper permet de les supprimer automatiquement selon un critère de distance. Toutefois, il peut arriver que certains points de joints, notamment situés en bordure des pierres, ne soient pas éliminés lors du filtrage ce qui nécessite alors un nettoyage manuel obligatoirement réalisé par l’opérateur. Cette opération de nettoyage peut être plus ou moins longue selon la qualité de la classification effectuée précédemment.

Étape 4 : Reconnaissance des contours par l’algorithme alpha-shape en langage python ou par le logiciel 3DReshaper

La méthode mise en avant par notre algorithme et par le logiciel 3DReshaper pour la reconnaissance des contours est celle de l’alpha -shape. Si l’algorithme développé en langage python pour cette étude produit de bons résultats, celui-ci n’est actuellement pas en mesure de traiter une grande quantité de données contrairement au logiciel 3DReshaper. De plus, des recherches seraient encore nécessaires sur le moyen d’exporter directement les polylignes 2D dans un format compatible avec le logiciel AutoCAD.
De ce fait, la méthode proposée par 3DReshaper répond aujourd’hui le mieux au cahier des charges (traitement d’une grande quantité de données et exports des polylignes au formatDXF, exploitables sous le logiciel AutoCAD).

Table des matières
Remerciements
Table des matières 
Introduction 
I OBJECTIFS ET CONTEXTE SCIENTIFIQUE 
I.1 PRESENTATION DES OBJECTIFS
I.2 LA LITTERATURE SCIENTIFIQUE ET LA DETECTION DE CONTOURS
I.2.1 Définitions des données images et nuages de points
I.2.1.1 L’image numérique
I.2.1.2 Le nuage de points
I.2.1.3 Comparaison des données
I.2.2 La détection de contours sur image
I.2.2.1 Détection de contours par filtrage linéaire et classification
I.2.2.2 Détection de contours par la transformée de Hough
I.2.2.3 Segmentation par croissance de régions (Region Growing)
I.2.3 Les recherches scientifiques sur la données 3D
I.2.3.1 Les paramètres influant sur les mesures d’acquisition 3D
I.2.3.2 L’algorithme de croissance de régions sur nuage de points
I.2.3.3 L’algorithme alpha-shape sur nuage de points
I.3 LES METHODES ENVISAGEES
I.3.1 Détection des contours à partir d’orthoimages extraites du nuage de points texturé
I.3.2 Détection des contours directement sur le nuage de points
I.3.3 Justification du choix de la deuxième méthode
I.4 PRESENTATION DES NUAGES DE POINTS
II CLASSIFICATION ET SEGMENTATION
II.1 CLASSIFICATION DU NUAGE DE POINTS SELON L’INTENSITE LASER
II.1.1 Définition de la classification
II.1.2 Etude des histogrammes selon l’intensité laser
II.1.3 Seuillage simple
II.1.3.1 Le principe du seuillage simple
II.1.3.2 Détermination d’un seuil S : la méthode adaptive thresholding
II.1.4 Résultats de la classification selon l’intensité laser
II.1.4.1 Qualité de la détection par classification
II.2 SEGMENTATION PAR CROISSANCE DE REGIONS
II.2.1 Présentation de l’algorithme
II.2.2 Critère d’homogénéité et seuil de validation
II.2.3 Résultats de la segmentation par croissance de régions
II.2.4 Qualité de la détection par croissance de régions
II.3 COMPARAISON DES DEUX METHODES
III EXTRACTION DES POINTS DE CONTOURS
III.1 L’ALGORITHME ALPHA-SHAPE
III.1.1 Présentation de l’algorithme
III.1.2 Résultats obtenus par la méthode alpha-shape
III.1.2.1 Test sur un extrait du nuage de points n°1
III.1.2.1.1. Application au nuage résultant de la classification du nuage de points n°1
III.1.2.1.2. Application au nuage n°1 classifié et filtré
III.1.2.1.3. Application au nuage résultant de la segmentation par croissance de régions du nuage de points n°1
III.1.2.1.4. Qualité de la détection des contours par notre algorithme alpha-shape en langage python
III.1.2.2 Test sur un extrait du nuage de points n°2
III.1.2.2.1. Application au nuage résultant de la classification du nuage de points n°2
III.1.2.2.2. Application au nuage résultant de la segmentation du nuage de points n°2
III.1.2.2.3. Qualité de la détection des contours par notre algorithme alpha-shape en langage python
III.2 DETERMINATION DES CONTOURS SOUS LE LOGICIEL 3DRESHAPER
III.2.1 Détection des contours à partir d’un maillage : alpha-shape
III.2.1.1 Traitement du nuage de points n°1
III.2.1.1.1. Traitement du nuage de points n°1
III.2.1.1.2. Création d’un maillage 3D
III.2.1.1.3. Création des polylignes 3D de contours
III.2.1.1.4. Calcul d’un plan moyen au nuage de points
III.2.1.1.5. Obtention des polylignes 2D et qualité des données
III.2.1.1.6. Export des polylignes 2D au format DXF
III.2.1.2 Traitement du nuage de points n°2
III.2.1.3 Qualité de la détection de contours par la méthode alpha-shape de 3DReshaper
III.2.2 Détection des contours par extraction des lignes de rupture de pente
III.2.2.1 Réalisation d’un maillage en deux étapes
III.2.2.2 Extraction des lignes de rupture de pente
IV DISCUSSIONS DES RESULTATS 
IV.1 LES PROCEDES DE RECONNAISSANCE AUTOMATIQUE DE CONTOURS DE PIERRES SUR NUAGES ….. DE POINTS
IV.2 ANALYSES ET CHOIX DES METHODES
IV.2.1 Etape 2 : Détection des points de pierres par classification ou segmentation par croissance de régions
IV.2.2 Etape 3 : Elimination des points isolés par filtrage/nettoyage du nuage
IV.2.3 Etape 4 : Reconnaissance des contours par l’algorithme en langage python ou par le logiciel 3DReshaper
Conclusion 
Bibliographie 
Liste des figures 
Liste des tableaux
Résumé 
Poster Scientifique 
Abstract

Télécharger le rapport complet