Nous annonçons la création de BESTREMA, un bureau d'études structure spécialisé dans les monuments anciens. Un des objectifs de cette société est de participer à la diffusion des connaissances sur la structure des monuments anciens auprès du grand public.

Les nouveaux articles que nous écrirons seront désormais mis en ligne sur bestrema.fr. Les anciens articles qui ont déjà été publiés ces deux dernières années resteront à votre disposition sur Combien ça porte. Nous vous remercions d'avoir suivi ce blog, et nous remercions tout particulièrement les lecteurs qui ont partagés avec nous leurs observations sur les structures des monuments anciens.


24 juillet 2012

La photogrammétrie : VisualSFM et MeshLab

1  Introduction

Il est généralement difficile aux étudiants de trouver les plans nécessaires pour étudier la structure d'un monument ancien. Les plans anciens, s'ils existent, sont souvent incomplets. Nous présentons ici un tutorial utilisant deux logiciels libres1 pour obtenir simplement à partir de photos les nuages de points et les maillages permettant d'établir les plans nécessaires à l'analyse structurelle. Il n'est pas nécessaire d'avoir de connaissances particulières en photogrammétrie pour utiliser ces logiciels, les principes de bases sont expliqués ci-dessous.
Les logiciels utilisés ici sont VisualSFM et MeshLab. Ils ont été développés par des étudiants dans un cadre universitaire, et leur usage combiné permet d'obtenir des nuages de points en 3D et des maillages, uniquement à partir de photos. Ils sont téléchargeables sur Internet sous forme compilée pour Windows, permettant leur usage par le plus grand nombre, sans nécessiter de connaissances informatiques poussées. De plus l'utilisation des cartes graphiques nVidia par VisualSFM permet d'accélérer grandement les temps de calcul pour la production des nuages de points : il n'est pas nécessaire d'avoir une machine très puissante pour accéder rapidement aux premiers résultats.
Nous présentons ci-dessous le principe de fonctionnement de ces logiciels, et l'illustrons sur quelques exemples. Notre objectif n'est pas de décrire précisément le fonctionnement de ces logiciels, mais de simplement de donner les grandes lignes du fonctionnement afin de permettre l'utilisation de leurs fonctions de base. Nous donnons à la fin de cet article les références de sites en anglais pour en apprendre plus sur ces logiciels.

2  VisualSFM

2.1  Principe de fonctionnement

VisualSFM a été développé par Changchang Wu à l'université de Washington à Seattle. Ce logiciel permet de construire un nuage de points 3D à partir de photos, sans que l'utilisateur ait à entrer dans son ordinateur de données particulières autres que les photos. La particularité de VisualSFM réside d'une part dans son interface graphique, alors que la plupart des autres logiciels libres fonctionnent en lignes de code, et dans l'affichage en temps réel de la construction du nuage de points. Les étapes simplifiées2 du processus sont les suivantes :
  • Recherche des points-clés ["features"] pour chaque photo. En effet les photos ne sont pas comparées intégralement les unes aux autres. Seuls les points-clés vont être comparés entre-eux.
  • Recherche des correspondances ["feature matches"] pour chaque couple de photos. Ces correspondances sont des points-clés identiques apparaissant sur des photos différentes. Plus un couple de photos a de correspondances, plus les photos sont similaires (i.e. plus l'angle de vue et les zones couvertes par les photos sont similaires).
  • Recherche des inliner matches. Certaines correspondances trouvées lors de l'étape précédente peuvent être fausses, par exemple si un même motif se trouve plusieurs fois sur une surface. VisualSFM supprime ces erreurs dans le groupe des feature matches, et obtient ainsi les inliner matches. Le principe est grossièrement le suivant. Si on place les deux photos côte-à-côte, et si on trace des lignes entre les points-clés communs, la majorité de ces traits décrit une transformation géométrique commune. Ils peuvent par exemple être tous parallèles si la différence entre les photos est une simple translation. Cependant, les traits des erreurs de correspondances auront une direction incompatible avec la transformation géométrique globale. Ce sont ces erreurs de correspondance qui sont supprimés lors de cette étape, en passant des feature matches aux inliner matches. Les reflets sur les surfaces réfléchissantes (vitres, miroirs, pièces métalliques etc.) vont être supprimés lors de cette étape, c'est pourquoi ce type de surface n'apparaît généralement pas (ou mal) sur les nuages de points. La figure 1 illustre le résultat de cette étape sur un exemple.
  • Sparse reconstruction . Chaque photo est caractérisée par un ensemble de paramètres décrivant l'objectif et sa position (profondeur de focale de la lentille, déformation, orientation de l'objectif dans l'espace etc.). Ces paramètres caractérisent un système de projection des points de l'espace sur le plan de la photo. En partant des couples de photos ayant un nombre suffisant de inliner matches, visualSFM calcule les matrices de transformations permettant de passer d'un système de projection à l'autre. Les droites passant par les points-clés et par le centre des objectifs du couple de photos considérées sont alors calculées, puis la position dans l'espace des points-clés est déduite par intersection de ces droites. Les seuls points 3D créés lors de cette étape sont les points correspondant à des points-clés pour lesquels des correspondances ont été trouvés.
  • Dense reconstruction. Dans un second temps, il est possible d'augmenter considérablement le nombre de points 3D en utilisant l'algorithme "Dense Reconstuction". VSFM utilise Clustering Views for Multi-view Stereo (CVMS) pour réaliser cette étape.
VisualSFM permet donc d'obtenir un nuage de points en 3D, sous la forme d'un fichier .ply, qui sera ensuite exploitable par MeshLab, comme nous le verrons plus loin.
Fig 1: Feature matches3 à gauche et Inliner matches à droite
Façade occidentale de la cathédrale de Chartres

2.2  Installation du logiciel

Le dossier compressé à télécharger pour l'installation se trouve sur la page d'accueil du site de VisualSFM, dans la rubrique Download (choisir le lien "X64" ou "win32" suivant votre version de Windows). Il suffit dans un premier temps de décompresser les fichiers dans un dossier quelconque4 de votre ordinateur. Une fois les fichiers en place, suivez les instructions pour l'installation tirées du site de VisualSFM et traduites ci-dessous :
  1. Essayer de lancer VisualSFM.exe. Si cela ne marche pas, vous devez installer MSVC2010 runtime (64bit, 32bit).
  2. Faire une des actions suivantes pour PBA (Multicore Bundle Ajustment) :
    • Option 1, pour les systèmes avec carte graphique nVidia compatible CUDA, installer CUDA 4.0 toolkit (pas le driver pour développeur).
    • Option 2, pour les systèmes sans carte graphique nVidia, télécharger le driver pba.dll pour CPU seul, et remplacer celui compris dans le dossier compressé. NE PAS installer CUDA.
    • Option 3, pour les systèmes sans carte graphique nVidia, télécharger le code PBA, compiler pba(_x64).dll pour CPU-seul, et remplacer celui compris dans le dossier compressé.
  3. (facultatif) Si vous préférez CUDA à GLSL pour SiftGPU (celui dans le dossier compressé ne fonctionne qu'avec GLSL), téléchargez le code de SiftGPU, et compilez SiftGPU-avec-CUDA si vous avez une carte graphique nVidia. Remplacez le siftgpu(64).dll dans le dossier compressé avec le driver compatible CUDA. Vous aurez besoin du toolkit CUDA 4.0 dans ce cas.
  4. (facultatif) Si vous voulez utiliser Yasutaka Furukawa's patch-based dense reconstruction, téléchargez CMVS/PMVS (disponible ici). Placez les fichiers exe avec leurs drivers dll dans le même dossier que VisualSFM.exe

2.3  Tutorial

Les étapes à suivre pour produire votre premier nuage de points 3D sont indiquées ci-dessous. Pour pouvoir suivre l'avancement des calculs, il est utile de conserver affiché le "Task Viewer". Il peut être activé dans le menu Tools / Show TaskViewer si il a disparu.
  1. Importer une série de photos avec File / Open+ Multi Images.
  2. Chercher les feature matches avec SfM / Pairwise Matching / Compute Missing Match. Attention cette fonction compare toutes les photos deux à deux, et par conséquent le temps de calcul augmente rapidement avec le nombre des photos. Si vos photos ont été prises dans un certain ordre (par exemple si vous avez fait le tour du monument en prenant régulièrement des photos), utilisez plutôt SfM / Pairwise Matching / Compute Sequence Match, en indiquant le nombre de photos adjacentes qui doivent être comparées autour de chaque photo. Une fois la recherche terminée, vous pouvez afficher la matrice des correspondances (SfM / Pairwise Matching / Show Match Matrix) pour vérifier que les correspondances souhaitées ont bien été trouvées. Dans le cas de photos prises avec un certain ordre, la matrice doit avoir plus ou moins l'aspect de la figure 2. Si des lignes ou des colonnes entièrement vides apparaissent sur la matrice, des modèles séparés seront créés dans la suite.
  3. Exécuter la sparse reconstruction depuis le menu SfM / Reconstruct 3D. Vous devez voir apparaître progressivement les points de votre modèle lors de l'éxecution de cette étape.
  4. Exécuter la dense reconstruction depuis le menu SfM / Run CMVS/PMVS. Une fois les calculs terminés, utiliser la touche TAB pour passer de la vue "sparse" à la vue "dense". Le nuage de points est alors prêt à être ouvert avec MeshLab.
Les raccourcis claviers les plus utiles sont les suivants :
  • x : met à jour le temps de calcul écoulé depuis le début des calculs. L'étape la plus longue est la dense reconstruction
  • retour arrière (backspace) : afficher les aperçus des images (thumbnails)
  • z : adapter le zoom aux aperçus des images
  • tab : permet de passer de la vue "sparse" à la vue "dense" et vice-versa
  • haut-bas : permet de passer d'un modèle au suivant, si plusieurs modèles séparés ont été trouvés
Enfin, quelques mises en garde pour l'utilisation :
  • Il ne faut pas utiliser d'images avec des résolutions supérieures à 3200 pixels. Il est possible d'utiliser des images de dimensions supérieures mais il faut pour cela modifier les paramètres par défaut de VisualSFM.
  • Les points-clés et les correspondances de chaque photo sont sauvegardées dans les fichiers .sift et .mat dans le même répertoire que vos photos. Ces fichiers sont chargés en mémoire s'ils existent lors de l'ajout de nouvelles photos à votre projet, ce qui évite de recommencer les premières étapes de recherche des points-clés et des correspondances si vous réouvrez les mêmes images.. Il faut donc supprimer ces fichiers si vous souhaiter recommencer à zéro la recherche des points-clés et des correspondances.
  • Les fonctions du menu Rep correspondent à un autre programme de l'auteur de VSFM et ne sont pas nécessaires ici.
Fig 2: Matrice des correspondances pour les photos utilisées pour le nuage de points de la cathédrale de chartres ci-dessous

2.4  Vérification du fonctionnement

Avant de vous lancer avec vos propres images, il est utile de vérifier que votre installation fonctionne correctement. Téléchargez les deux images de statues ci-dessous, et importez les dans VisualSFM. Lancez la comparaison des images. Vous devriez obtenir des résultats de ce type : environ 6200-6400 features par image, et environ 900 feature matches - résultats obtenus avec la version v0.5.17 de VSFM. Les informations affichées dans le Task Viewer par VSFM lors de ce tests devraient être similaires à la reproduction ci-dessous. Si le nombre de features par image ou le nombre de feature matches est très éloignée des nombres données ici, il est possible que votre installation ne marche pas correctement et que vous ne réussissiez pas à obtenir de modèles lors des étapes ultérieures. Vous pouvez chercher des informations complémentaires sur ce site (en anglais) : Google Groups VSFM.
0: StatuesPortailSudA
image_size: 600x800
1: StatuesPortailSudB
image_size: 600x800
Loading image pixel data ...done

Compute Missing Pairwise Matching, begin...
********* WARNING ***********
More than 175MB of graphic memory may be allocated
under default settings. If the program halts here,
adjust parameters to save memory and rerun the task: 
Menu->Tools->Enable GPU->Set Maximum DIM
Note some octaves may be automatically skipped
SIFT: 600x800,  6254, 2.78sec
SIFT: 600x800,  6445, 0.22sec

###########-------timing------#########
2 Feature Detection finished, 3 sec used
#############################

1 pairs to compute match
0000 and 0001: 906 matches, 0.52sec, #0

###########-------timing------#########
1 Image Match finished, 1 sec used
#############################

NOTE: using 4 matching threads
0000 and 0001: E[847/906], H[54], 0.02sec

###########-------timing------#########
1 Putative Match finished, 1 sec used
1 Geometric Verification finished, 0 sec used
#############################
----------------------------------------------------------------
Compute Missing Pairwise Matching, finished
Totally 4.000 seconds used

Fig 3: Photos pouvant être utilisées pour la vérification du fonctionnement - features et feature matches
Statues du portail Nord de la cathédrale de Chartres

3  MeshLab

3.1  Principe de fonctionnement

Les nuages de points 3D sont comme leur nom l'indique un groupe de points (ou nœuds - "vertices"). A chaque point est affecté trois coordonnées, une couleur, et un vecteur normal5. VisualSFM produit à partir des photos un fichier .ply qui contient les coordonnées de chaque point du nuage de points 3D, sa couleur, mais pas d'information sur le vecteur normal correspondant. MeshLab permet de travailler sur le nuage de points, pour permettre son exploitation : par exemple pour diminuer le nombre de points, créer des maillages6, ajouter des textures sur des maillages etc. Une fois le maillage obtenu, MeshLab permet également d'extraire des coupes afin de produire les plans désirés.
MeshLab fonctionne un peu comme un logiciel de dessin, avec un système de calques où sont rangés les nuages de points et maillage, et sur lesquels il est possible d'appliquer des filtres prédéfinis.
Nous indiquons dans la suite les étapes à suivre pour exploiter le fichier avec .ply fourni par VisualSFM. Nous indiquons à chaque fois les filtres à appliquer sur les nuages de points et maillages. Ces filtres se trouvent dans le menu Filters de MeshLab.

3.2  Installation du logiciel

L'installation de MeshLab ne présente pas de difficulté particulière. La dernière version de l'installateur de ce programme sous Windows est disponible sur sourceforge.

3.3  Nuages de points

Si le nombre de points de votre nuage est trop important pour être manipulé rapidement sur votre ordinateur, ou si vous souhaitez créer un maillage, il faut rééchantillonner votre nuage de points, en appliquant le filtre Sampling / Poisson-disk Sampling. La case Base mesh subsampling doit être cochée (car pour l'instant les éléments du maillage n'existent pas). Entrez le nombre de points souhaités dans la case Number of samples. Nous ne travaillerons dans la suite qu'à partir de ce nouveau nuage de points, que nous appelerons "nuage de points complet" dans la suite, pour le distinguer du nuage de points de VisualSFM.
Si vous souhaitez travailler directement sur le nuage de points complets pour tracer des coupes ou prendre des mesures, il ne reste alors qu'à mettre à l'échelle ce nuage de points. Sinon, il faut effectuer les opérations suivantes avant de passer à la création du maillage :
  • supprimer les points ou groupes de points isolés correspondant à des artefacts lors de la "dense reconstruction" avec VisualSFM et CMVS. Pour la sélection des points isolés, il est possible d'appliquer le filtre Point set / Estimate radius from density qui calcule la distance moyenne de chaque point avec ses plus proches voisins, puis sélectionner les points isolés avec Selection / Conditional Vertex Selection en choisissant comme condition rad>0.01 (moduler la valeur pour ne garder que les points qui vous intéressent). Il faut à la fin de cette étape ne conserver que les points qui appartiennent au modèle désiré. Les points situés en dehors risquent de créer de nouveau artefacts lors de la création du maillage, et d'allonger inutilement les temps de calcul nécessaires.
  • Pour pouvoir travailler à la création de maillages sur un ordinateur portable avec des temps de calcul raisonnable, le nombre de points doit être compris entre 20k et 200k environ suivant la taille de votre nuage de départ et la précision souhaitée.
  • Le CGAL propose d'effectuer un lissage sur le nuage de points avant de commencer le maillage (Point Set Processing), mais nous n'avons pas encore trouvé comment appliquer ce lissage au nuage de points avec MeshLab.

3.4  Création d'un maillage

La création d'un maillage à partir d'un nuage de points peut s'effectuer à l'aide du filtre Remeshing, simplification and reconstruction / Surface Reconstruction : Poisson. Pour pouvoir appliquer cette méthode, il faut disposer d'un nuage de points ET des vecteurs normaux correspondant à ces points. Les normales ne sont pas calculées par défaut par VisualSFM, et il faudra donc commencer par les calculer.
Il existe plusieurs méthodes pour aboutir au maillage, nous proposons les étapes7 décrites ci-dessous.
  1. Création d'un petit nuage de point contenant environ 10k points, en appliquant la méthode de rééchantillonnage vue ci-dessus. On applique ensuite sur ce petit échantillon Point Set / Compute Normals for Point Set, avec la case Flip normals w.r.t. viewpoint cochée8, et en entrant les coordonnées d'un point fictif éloigné du maillage (par exemple 0,0,-1000).
  2. Création d'un premier maillage, qui va simplement servir à transférer les normales sur le nuage de points complet. Utiliser Filters /Remeshing, simplification and reconstruction / Surface Reconstruction : Poisson, avec Octree Depth égal à 6. Transférer ensuite les normales de ce maillage vers le nuages de points complets, avec Sampling / Vertex Attribute Transfer en cochant uniquement Transfer normal, et en choisissant votre premier maillage pour Source mesh et votre nuage de points complet pour Target mesh. Il est possible de remplacer ces deux premières étapes en appliquant directement le filtre Compute Normals for Point Set au nuage de points complet, si ce dernier est suffisamment petit. Si le nuage est trop grand, l'application du filtre peut-être très longue ou faire planter MeshLab.
  3. Maintenant que l'ensemble des points possède un vecteur normal, il est possible d'appliquer le filtre de construction du maillage : Remeshing, simplification and reconstruction / Surface Reconstruction : Poisson, en choisissant Octree Depth entre 6 et 12 selon la précision du maillage désiré, et Solver Divide entre la valeur de Octree Depth et cette valeur moins 2. Attention le temps de calcul augmente très rapidement avec Octree Depth, et il vaut mieux commencer avec Octree Depth égal à 6 et l'augmenter de 1 en 1. L'effet de la valeur de Octree Depth est illustrée sur la figure 4. Sur cet exemple on voit le raffinement du maillage au fur et à mesure que le paramètre Octree Depth augmente9. A la fin de l'étape (3), on obtient donc le maillage recherché, mais il ne possède pour l'instant pas de couleur.
  4. Pour transférer les couleurs contenues dans le nuage de point sur votre nouveau maillage, appliquez Sampling / Vertex Attribute transfer, en cochant Transfer color, et en choisissant votre nuage de points pour Source mesh et votre nouveau maillage pour Target mesh.
La méthode proposée ci-dessus génère des éléments indésirables aux extrémités du modèle, car la méthode de reconstruction de la surface cherche à créer un contour fermé. Ces éléments de bords sont facilement supprimables en utilisant Selection / Select Faces With Edges Longer Than, car ils possèdent des éléments dont les côtés sont plus long que les éléments standards au centre de votre maillage.
Pour forcer le maillage à respecter rigoureusement le nuage de points de départ de VisualSFM (ce qui n'est pas forcément souhaitable), il est possible de raffiner le maillage avec le filtre Remeshing, simplification and reconstruction / Subdivision surfaces : LS3 Loop, puis d'appliquer Sampling / Vertex Attribute Transfer en ayant coché Transfer geometry, et en choisissant votre nuage de points de VisualSFM pour Source mesh et votre maillage pour Target mesh : l'ensemble des nœuds du maillage sera repositionné au niveau des points correspondant les plus proches.
Fig 4: Maillage obtenu avec un Octree Depth de 6 à 10 (de g. à d.)
Statues du portail Nord de la cathédrale de Chartres
Exemples   Nous donnons ci-dessous une image tirée du nuage de points obtenu à partir de photos des façades, portails et bas-côtés de la cathédrale de Chartres. Le résultat n'est pas encore parfait, mais il est possible de tirer de ce modèle les coupes en plans à différentes hauteurs de la cathédrale.
Fig 5: Nuage de points obtenu par VSFM et affiché par MeshLab
Façade occidentale de la cathédrale de Chartres
Nous avons également réalisé un petit nuage de points de deux statues du portail Nord de la cathédrale.
Fig 6: Nuage de point obtenu par VSFM à g. - Maillage obtenu avec MeshLab à d.
Affichage sous MeshLab
Statues du portail Nord de la cathédrale de Chartres
Fig 7: Détail du nuage de point de la figure 6
Affichage sous MeshLab
Statues du portail Nord de la cathédrale de Chartres

4  Conclusion

Les relevés que nous avons obtenu en appliquant cette méthode sont moins précis que les relevés avec un laser 3D, mais ils sont beaucoup plus faciles à obtenir. Il suffit d'un appareil photo compact et d'un ordinateur portable muni d'une carte graphique nVidia ou équivalent. Les logiciels décrits ci-dessus peuvent donc apporter une aide non négligeable aux étudiants cherchant à obtenir à peu de frais des relevés fiables sur les structures qu'ils modélisent.
Afin de poursuivre la découverte des logiciels mentionnés ici, nous vous conseillons la visite des sites Internets suivants (en anglais).
Article mis en ligne le : 24/07/2012.
Révisé le : 27/10/2013.

Notes:

1 L'utilisation des logiciels présentés ici est libre pour l'usage personnel, non-lucratif, ou académique (voir les sites Internet des logiciels pour plus de détails sur les licences). L'utilisation de ces logiciels et des méthodes présentées ici se fait à vos risques et périls. Pensez à mettre à jour votre antivirus...
2 Les informations données ici concernant les mécanismes de construction des nuages de points à partir de photos ont été trouvées sur le tas, et sont juste suffisantes pour comprendre le fonctionnement global du processus de construction. Il est fort probable que des erreurs ou imprécisions se soient glissées dans cette description. N'hésitez pas à nous les signaler.
3 Nous avons choisit des images en faible résolution - environ 400 pixels de côté - pour obtenir ces résultats. Avec des images de bonne qualité, le nombre de feature matches est tellement important qu'il devient difficile de distinguer les traits les uns des autres.
4 Le chemin du dossier ne doit pas contenir d'espace de préférence.
5 Le vecteur normal est le vecteur perpendiculaire à la surface infinitésimale à laquelle appartient le point concerné.
6 Un maillage est un ensemble d'éléments. Les éléments les plus courants sont les triangles et les carrés, définis chacun par trois ou quatre nœuds, l'orientation de l'élément, et éventuellement d'autres informations (couleur, qualité etc.).
7 Des tutoriaux en anglais décrivant des méthodes similaires à partir de nuages de points obtenus par d'autres moyens sont disponibles en vidéo sur internet : Poisson Reconstruction in MeshLab et 3D Scanning : merging with Poisson filter
8 Il est également possible de ne pas cocher cette case, et d'obtenir de bons résultats. Les tutoriaux que nous avons trouvé sur internet recommandent cependant de cocher cette case et d'entrer un point éloigné du nuage de point pour avoir des orientations de vecteurs normaux cohérentes entre elles si le nuage de points n'est pas "continu".
9 Le résultat est à peu près équivalent entre 8 et 10 sur la figure 4 car le nombre de points du nuage (20k) pris pour cet exemple n'était pas suffisant.