Adaptive extraction and representation of geometric structures from unorganized 3D point sets [Elektronische Ressource] / von Patric Keller

Sujets

• Informatik

Informations

• Publié par: technische_universitat_kaiserslautern
• Publié le: 01 janvier 2009
• Nombre de lectures: 41
• Langue: English
• Poids de l'ouvrage: 7 Mo

Extrait

Adaptive Extraction and Representation of
Geometric Structures from Unorganized 3D
Point Sets
Dissertation
Eine dem Fachbereich Informatik der Technischen Universit at Kaiserslautern
vorgelegte Arbeit zur Erlangung des akademischen Grades
Doktor-Ingenieur (Dr.-Ing.)
vonPatric Keller
Kaiserslautern, 22. Juni 2009
Termin der wissenschaftlichen Aussprache: 20.11.2009
Dekan: Prof. Dr. Karsten Berns
Vorsitzender des Prufungsaussc husses: Prof. Dr. Karsten Berns
1. Berichterstatter: Prof. Dr. Hans Hagen
2. Berich Prof. Dr. Bernd Hamann
3. Berichterstatter: Dr. habil. Martin Hering-Bertram
D 386This work is devoted to
my parents
Regina and Hans Kellerc Copyright 2009
by Patric KellerAcknowledgements
First of all I want to thank my supervisors Dr. Martin Hering-Bertram at the Fraun-
hofer Institute fur Techno- und Wirtschaftsmathematik (ITWM) in Kaiserslautern, Prof.
Hans Hagen at the University of Kaiserslautern and Prof. Bernd Hamann at the Uni-
versity of California, Davis for providing me with ideas and valuable advice. Especially,
I want to thank Prof. Hagen for giving me the opportunity to perform all these studies.
One special thank to Dr. Martin Hering-Bertram for his all-time support and guidance
during this work. I also want to thank the members of the DFG’s International Research
Training Group (IRTG) and the Computer Graphics Research Group at Kaiserslautern
for their advice and the interesting discussions. I thank Mady Bold and Inga Scheler for
helping me managing all my foreign research stays and conference visits.
At the University of California, Davis I want to thank Louise H. Kellogg and Eric
S. Cowgill of the Department of Geology and the other members of the KeckCAVES
Research Group as well as the members of the LIDAR Research Group for providing
me with valuable feedback and data sets. I also want to thank Oliver Kreylos, Marek
Vanco for providing me with advice and data sets. I want to thank the scienti c sta
including Christoph Garth, Eduard Deines and Mario Hlawitschka at the Institute of
Data Analysis and Visualization (IDAV) at the University of California, Davis for their
support.Abstract
The primary emphasis of this thesis concerns the extraction and representation of intrin-
sic properties of three-dimensional (3D) unorganized point clouds. The points establish-
ing a point cloud as it mainly emerges from LiDaR (Light Detection and Ranging) scan
devices or by reconstruction from two-dimensional (2D) image series represent discrete
samples of real world objects. Depending on the type of scenery the data is generated
from the resulting point cloud may exhibit a variety of di erent structures. Especially,
in the case of environmental LiDaR scans the complexity of the corresponding point
clouds is relatively high. Hence, nding new techniques allowing the e cient extraction
and representation of the underlying structural entities becomes an important research
issue of recent interest.
This thesis introduces new methods regarding the extraction and visualization of struc-
tural features like surfaces and curves (e.g. ridge-lines, creases) from 3D (environmental)
point clouds. One main part concerns the extraction of curve-like features from environ-
mental point data sets. It provides a new method supporting a stable feature extraction
by incorporating a probability-based point classi cation scheme that characterizes indi-
vidual points regarding their a liation to surface-, curve- and volume-like structures.
Another part is concerned with the surface reconstruction from (environmental) point
clouds exhibiting objects that are more or less complex. A new method providing multi-
resolutional surface representations from regular point clouds is discussed. Following the
applied principles of this approach a volumetric surface reconstruction method based on
the proposed classi cation scheme is introduced. It allows the reconstruction of surfaces
from highly unstructured and noisy point data sets. Furthermore, contributions in the
eld of reconstructing 3D point clouds from 2D image series are provided. In addition,
a discussion concerning the most important properties of (environmental) point clouds
with respect to feature extraction is presented.Zusammenfassung
Diese wissenschaftliche Arbeit handelt von der Extraktion und der Darstellung intrinsi-
scher Eigenschaften von dreidimensionalen (3D) Punktwolken. Die zugeh origen Punkte
in Form von 3D Ko- odinaten, wie sie z.B. von Laser-/LiDaR (Light Detection and
Ranging) Scannern generiert, oder mithilfe von speziellen Algorithmen aus einer Se-
rie von zweidimensionalen (2D) Bildern rekonstruiert werden, repr asentieren Objekte
aus der realen Welt. Abh angig von der fokussierten Szenerie weisen die resultieren-
den Punktewolken eine Vielfalt unterschiedlichster Strukturen auf. Speziell im Fall von
Landschafts- und Umgebungsscans besitzen diese eine hohe Komplexit at. Die Entwick-
lung neuer und e zienter Methoden, um solche strukturellen Informationen zu ltern
und darzustellen, ist ein wichtiger Forschungszweig in der Computer Gra k.
Diese Arbeit leistet einen Beitrag hinsichtlich der Extraktion und der Visualisierung
besonderer Merkmale wie z.B. achen- oder kurven ahnlicher Strukturen (ridge-lines,
creases) aus 3D Punktewolken. Ein Teil besch aftigt sich dabei mit der Extraktion von
kurven ahnlichen Strukturen aus Landschafts- und Umgebungscans. Das vorgestellte
Verfahren verwendet ein neuartiges wahrscheinlichkeitsbasiertes Punkte-Klassi zierungs-
schema, welches die einzelnen Punkte entsprechend ihrer Zugeh origkeit zu achen-,
kurven- und volumenartigen Strukturen analysiert. Ein weiterer Teil dieser Arbeit
betri t die Rekonstruktion von Fl achen aus 3D Punktewolken, welche eine moderate
bis hohe Komplexit at aufweisen. Dabei wird eine neue Methode vorgestellt, welche
die Rekonstruktion von Fl achen in multiplen Au osungen erlaubt. Auf diesem Ansatz
beruhend wird eine volumen-basierte, implizite Rekonstruktionsmethode eingefuhrt, die
die Rekonstruktion von Fl achen aus hochgradig komplexen und verrauschten Punkte-
wolken, unter Verwendung des vorgestellten Punkte-Klassi zierungsschemas, gestattet.
Zudem werden Beitr age hinsichtlich der Rekonstruktion von 3D Punktewolken aus einer
Serie von 2D Bilder pr asentiert, sowie einige der wichtigsten Eigenschaften von 3D Punk-
tewolken, wie sie haupts achlich von Umgebungsscans generiert werden, diskutiert. Diese
Diskussion ist speziell auf die Extraktion von achen- und kurvenahnlichen Strukturen
hin ausgerichtet.Contents
List of Figures vii
List of Tables ix
1 Introduction 1
1.1 Unorganized/Unstructured Data . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Problems with Unstructured Point Data . . . . . . . . . . . . . . . . . . 3
1.3 Contribution of Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Motivating Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 Applications in Geoscience . . . . . . . . . . . . . . . . . . . . . . 6
1.4.2 Ap in Reverse Engineering . . . . . . . . . . . . . . . . . 7
1.4.3 Applications in Creating and Populating Virtual Environments . . 7
1.5 Overview of Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Point Sets 9
2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Data Acquisition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 LiDaR Scanners . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Radar . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.3 CT/MRI Scanners . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Reconstruction of Point Clouds from 2D Images . . . . . . . . . . . . . . 14
2.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.2 The Projection Model . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.3 Epipolar Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.5 Point Reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.6 Resolving Image Correspondences . . . . . . . . . . . . . . . . . . 22
iContents
2.3.7 Maximum-Likelihood Based Parameter Reconstruction . . . . . . 27
2.3.8 Point Cloud Reconstruction . . . . . . . . . . . . . . . . . . . . . 32
2.3.9 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.3.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.4 Properties of Point Clouds . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.4.1 Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.4.2 Object Occlusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4.3 Sampling Density . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4.4 Overlapping Point Samples . . . . . . . . . . . . . . . . . . . . . . 42
2.5 Data structures for Organizing Point Clouds . . . . . . . . . . . . . . . . 43
2.5.1 Binary Space Partitioning Trees . . . . . . . . . . . . . . . . . . . 43
2.5.2 KD-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.5.3 Octrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46