Géométrie inverse : du nuage de points brut à la surface 3D : théorie et algorithmes, Inverse geometry : from the raw point cloud to the 3d surface : theory and algorithms

Julie Digne

Description

Sous la direction de Jean-Michel Morel
Thèse soutenue le 23 novembre 2010: École normale supérieure de Cachan
De nombreux scanners laser permettent d'obtenir la surface 3D a partir d'un objet. Néanmoins, la surface reconstruite est souvent lisse, ce qui est du au débruitage interne du scanner et aux décalages entre les scans. Cette these utilise des scans haute precision et choisit de ne pas perdre ni alterer les echantillons initiaux au cours du traitement afin de les visualiser. C'est en effet la seule façon de decouvrir les imperfections (trous, decalages de scans). De plus, comme les donnees haute precision capturent meme le plus leger detail, tout debruitage ou sous-echantillonnage peut amener a perdre ces details.La these s'attache a prouver que l'on peut trianguler le nuage de point initial en ne perdant presque aucun echantillon. Le probleme de la visualisation exacte sur des donnees de plus de 35 millions de points et de 300 scans differents est ainsi resolu. Deux problemes majeurs sont traites: le premier est l'orientation du nuage de point brut complet et la creation d'un maillage. Le second est la correction des petits decalages entre les scans qui peuvent creer un tres fort aliasing et compromettre la visualisation de la surface. Le second developpement de la these est une decomposition des nuages de points en hautes/basses frequences. Ainsi, des methodes classiques pour l'analyse d'image, l'arbre des ensembles de niveau et la representation MSER, sont etendues aux maillages, ce qui donne une methode intrinseque de segmentation de maillages. Une analyse mathematiques d'operateurs differentiels discrets, proposes dans la litterature et operant sur des nuages de points est realisee. En considerant les developpements asymptotiques de ces operateurs sur une surface reguliere, ces operateurs peuvent etre classifies. Cette analyse amene au developpement d'un operateur discret consistant avec Ie mouvement par courbure moyenne (l'equation de la chaleur intrinseque) definissant ainsi un espace-echelle numerique simple et remarquablement robuste. Cet espace-echelle permet de resoudre de maniere unifiee tous les problemes mentionnes auparavant (orientation et triangulation du nuage de points, fusion de scans, segmentation de maillages) qui sont ordinairement traites avec des techniques distinctes.
-Reconstruction de surfaces
-Flots géométriques
-Cao
-Segmentation de surfaces
-Maillages
-Nuage de points
Many laser devices acquire directly 3D objects and reconstruct their surface. Nevertheless, the final reconstructed surface is usually smoothed out as a result of the scanner internal de-noising process and the offsets between different scans. This thesis, working on results from high precision scans, adopts the somewhat extreme conservative position, not to loose or alter any raw sample throughout the whole processing pipeline, and to attempt to visualize them. Indeed, it is the only way to discover all surface imperfections (holes, offsets). Furthermore, since high precision data can capture the slightest surface variation, any smoothing and any sub-sampling can incur in the loss of textural detail.The thesis attempts to prove that one can triangulate the raw point cloud with almost no sample loss. It solves the exact visualization problem on large data sets of up to 35 million points made of 300 different scan sweeps and more. Two major problems are addressed. The first one is the orientation of the complete raw point set, an the building of a high precision mesh. The second one is the correction of the tiny scan misalignments which can cause strong high frequency aliasing and hamper completely a direct visualization.The second development of the thesis is a general low-high frequency decomposition algorithm for any point cloud. Thus classic image analysis tools, the level set tree and the MSER representations, are extended to meshes, yielding an intrinsic mesh segmentation method.The underlying mathematical development focuses on an analysis of a half dozen discrete differential operators acting on raw point clouds which have been proposed in the literature. By considering the asymptotic behavior of these operators on a smooth surface, a classification by their underlying curvature operators is obtained.This analysis leads to the development of a discrete operator consistent with the mean curvature motion (the intrinsic heat equation) defining a remarkably simple and robust numerical scale space. By this scale space all of the above mentioned problems (point set orientation, raw point set triangulation, scan merging, segmentation), usually addressed by separated techniques, are solved in a unified framework.
-3D surface reconstruction
-High precision point clouds
-Point cloud scale space
Source: http://www.theses.fr/2010DENS0038/document

Sujets

• Nuage de points

Informations

• Publié par: Thesee
• Nombre de lectures: 76
• Langue: English
• Poids de l'ouvrage: 14 Mo

Extrait

ÉcoleNormaleSupérieuredeCachan
Thèse
Présentéepar
JulieDIGNE
pourl’obtentiondutitrede
Docteurdel’ÉcoleNormaleSupérieuredeCachan
Spécialité: MathématiquesAppliquées
Géométrieinverse:dunuagedepointsbrutà
lasurfaceD
ThéorieetAlgorithmes
InverseGeometry:fromtheRawPointCloud
totheDSurface
TheoryandAlgorithms
Directeurdethèse: Jean-MichelMorel
soutenueleNovembreàl’ENSCachan
Jury:
Président: YvesMeyer - CMLA-ENSCachan
Rapporteurs: PierreAlliez - INRIASophiaAntipolis
RonKimmel - Technion
GuillermoSapiro - UniversityofMinnesota
Directeur: Jean-MichelMorel - CMLA-ENSCachan
Examinateurs: TamyBoubekeur - TelecomParisTech
FrédéricChazal - INRIASaclay
ClaireLartigue - LURPA-ENSCachan
Invité: JacquesBlanc-Talon - DGA
tel-00557589, version 1 - 19 Jan 2011tel-00610432, version 1 - 22 Jul 2011tel-00557589, version 1 - 19 Jan 2011tel-00610432, version 1 - 22 Jul 2011Remerciements
Trois ans de travail sont résumés dans les pages qui vont suivre. Cela semble
presquetroppeu(leslecteursmecontredirontsansdoutesurcepoint).
Je voudrais remercier Jean-Michel Morel de m’avoir dirigée pendant ces trois
ans. Cette thèse a été riche en apprentissages grâce à sa grande disponibilité
et sa patience. J’aimerais remercier mon jury : Pierre Alliez, Ron Kimmel et
GuillermoSapiroquiontacceptéderapportermathèse,JacquesBlanc-Talon,Tamy
Boubekeur, Frédéric Chazal, Claire Lartigue et Yves Meyer qui ont accepté de faire
partiedujury. CettethèseaétéelaboréeautourdesdonnéesfourniesparleLURPA
quejeremercievivement. J’aimeraisaussiremercierlaDGApouravoirfinancéces
troisansderecherche.
Merci à tous les chercheurs rencontrés au cours de cette thèse et avec qui j’ai
puavoirdesconversationstrèsintéressantes: FreddyBruckstein,GuillermoSapiro,
Pierre Alliez, Frédéric Chazal, Steve Oudot, José-Luis Lisani, Tony Buades, Pascal
Monasseettoutel’équipeduprojetMISS.
Travailler au CMLA a été un vrai plaisir, merci en particulier à Véronique Al-
madovar, Micheline Brunetti, Sandra Doucet, Virginie Pauchont et Carine Saint-
Prixpourleurefficacitéetlabonnehumeurqu’ellesrépandentdanslelaboratoire.
Tous mes remerciements vont aux thésards qui m’ont accompagnée pendant
ces trois ans : Neus Sabater pour des séances piscines intensives et des conseils
cuisine pour couronner le tout. Eric Bughin, pour la pause café du matin. Aude
Champmartin, pour me rappeler que, non, au labo tout le monde n’est pas sous
linuxetmetraineràlagym. AdinaCiomagapourêtreunpeustrrrresséeavantles
rendez-vous. BrunoGalerne,pourdesdiscussionscinématographiquesintenseset
Zhongweipourm’avoirfaitcomprendrelastéréorectification(enfin!). Merciaussià
Nicolas,parcequelaDsansproblèmeinformatiqueneseraitplusdelaD.Mercià
Rafapourunegentillesseetunepatiencesansbornemêmequandjereposedixfois
lesmêmesquestions. Merciàtouslesthésardsetpost-docsquiontrendulavieau
labotrèsagréableentrepausescaféaupavillondesjardinsetrepasgastronomiques
le soir : Adina, Aude, Ayman, Benjamin, Bruno, Eric, Frédéric, Frédérique, Gaël,
Ives, Jean-Pascal, Julien, Marc, Mauricio, Miguel, Morgan, Neus, Nicolas C., Nico-
las L., Romain, Saad, Yohann et Zhongwei. Merci enfin aux visiteurs : Alex, Anne,
Pascal,GloriaetPablo...
Cettethèseanécessité:
Lalecturede398articles;
Larédactionde30rapports;
tel-00557589, version 1 - 19 Jan 2011tel-00610432, version 1 - 22 Jul 2011ii
3réinstallationsdeLinux;
1changementdecartemère;
1remplacementdedisquedur;
xplantagesgénéralisésdesserveursdecalculdulabo;
255009lignesdecode;
26programmes;
11cahiers;
25stylosetcrayonsdivers;
1350litresdethé;
126litresdecafé;
421200 minutes de musique écoutée (dont une bonne moitié de Händel et
Rossini).
Jevoudraisremerciercertainsprofesseursquim’ontbeaucoupmarquéeparleur
grande pédagogie : Jean-Louis Garcin, Jean-Aristide Cavaillès au lycée Chaptal et
FrancisSchmitt,disparutroptôt,àTélécomParisTech. MesremerciementsàYann
GousseauetHenriMaitrepourleursconseilsd’orientation.
Finalement, je voudrais remercier mes parents et mes soeurs, Jeanne et Char-
lotte, pour leur soutien sans lequel cette thèse n’aurait pas existé. Merci à Nicolas,
qui a réussi à me supporter même pendant que je rédigeais! Merci à Hugo aussi et
bon courage pour ta thèse. Merci enfin à tous mes amis télécommiens et non télé-
commiens,àmaprofdechant, àmonensemblevocaletàmonclubthéâtre, parce
que la thèse c’est bien, mais l’oublier une ou deux heures ça permet de prendre du
recul.
Etcommeilnefautoublierpersonne,merciàtousceuxquinefigurentpasdans
cesremerciements.
tel-00557589, version 1 - 19 Jan 2011tel-00610432, version 1 - 22 Jul 2011Contents
 Introduction 
 StateoftheArt 
. DAcquisition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
.. Stereoscopy . . . . . . . . . . . . . . . . . . . . . . . . . . 
.. Time-of-flightlaserscanner . . . . . . . . . . . . . . . . . 
.. Triangulationlaserscanner . . . . . . . . . . . . . . . . . 
. Someacquisitionprojects . . . . . . . . . . . . . . . . . . . . . . 
. LURPAacquisitionsystem . . . . . . . . . . . . . . . . . . . . . . 
. RepresentationofDdata . . . . . . . . . . . . . . . . . . . . . . 
. Fromapointcloudtoamesh . . . . . . . . . . . . . . . . . . . . 
.. Mergingmultipleviews . . . . . . . . . . . . . . . . . . . 
.. Meshing . . . . . . . . . . . . . . . . . . . . . . . . . . . 
.. Remeshing . . . . . . . . . . . . . . . . . . . . . . . . . . 
. Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. Post-processingandlinedetection . . . . . . . . . . . . . . . . . . 
. ThedifferencebetweenImageProcessingandDsurfaceprocessing 
 ScaleSpaceMeshingofRawDataPointSets 
. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
.. Buildingamesh . . . . . . . . . . . . . . . . . . . . . . . 
.. Rawdatapointsetprocessing . . . . . . . . . . . . . . . . 
.. Computingcurvatures . . . . . . . . . . . . . . . . . . . . 
. Continuoustheory . . . . . . . . . . . . . . . . . . . . . . . . . . 
.. Sphericalneighborhoodsvscylindricalneighborhoods . . 
.. Curvatureestimation . . . . . . . . . . . . . . . . . . . . 
.. Surface motion induced by projections on the regression
plane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. Thediscretealgorithm . . . . . . . . . . . . . . . . . . . . . . . . 
.. Higherorderregressionsurfaces . . . . . . . . . . . . . . . 
. Firstapplication: scalespacerawdatapointorientation . . . . . . 
. Secondapplication: scalespacemeshing . . . . . . . . . . . . . . 
. Comparativeexperimentsonhighresolutiondata . . . . . . . . . 
. Complexityanalysisandcomputationtimemeasures . . . . . . . . 
. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
tel-00557589, version 1 - 19 Jan 2011tel-00610432, version 1 - 22 Jul 2011iv Contents
 HighFidelityScanMerging 
. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. PreviousWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
.. RigidScanregistration . . . . . . . . . . . . . . . . . . . . 
.. Non-rigidscanregistration . . . . . . . . . . . . . . . . . 
.. Super-resolutionfromseveralscans . . . . . . . . . . . . . 
.. Meshing . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. ScanMerging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
.. Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . 
.. Low/Highfrequencysurfacedecomposition . . . . . . . . 
.. Findingacommonsmoothbasisforallsurfaces . . . . . . 
.. Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 
.. One-dimensionalstudy . . . . . . . . . . . . . . . . . . . 
. ImplementationandResults . . . . . . . . . . . . . . . . . . . . . 
. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
 FillingHolesinScaleSpaceMeshes 
. PreviousWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
.. Volumetricmethods . . . . . . . . . . . . . . . . . . . . . 
.. Patchfillingmethods . . . . . . . . . . . . . . . . . . . . . 
.. Inpaintingforsurfaces,holefillingbasedonsimilarity . . . 
.. Pointclouds . . . . . . . . . . . . . . . . . . . . . . . . . 
. Aholefillingalgorithm . . . . . . . . . . . . . . . . . . . . . . . 
.. Fillingthehole: findinganinitialpatch . . . . . . . . . . . 
.. Refiningthepatch . . . . . . . . . . . . . . . . . . . . . . 
.. Givingshapetothepatch . . . . . . . . . . . . . . . . . . 
.. Specialholes . . . . . . . . . . . . . . . . . . . . . . . . . 
. Resultsonsynthetic