Efficient point-cloud processing with primitive shapes [Elektronische Ressource] / vorgelegt von Ruwen Schnabel

Ruwen Schnabel

Sujets

• Informatik

Informations

• Publié par: rheinische_friedrich-wilhelms-universitat_bonn
• Publié le: 01 janvier 2010
• Nombre de lectures: 69
• Langue: Deutsch
• Poids de l'ouvrage: 63 Mo

Extrait

Efficient Point-Cloud Processing
with Primitive Shapes
Dissertation
zur
Erlangung des Doktorgrades (Dr. rer. nat.)
der
Mathematisch-Naturwissenschaftlichen Fakultät
der Rheinischen Friedrich-Wilhelms-Universität Bonn
vorgelegt von
Dipl.-Inf. Ruwen Schnabel
aus
Konstanz
Bonn, Dezember 2009
Universität Bonn
Institut für Informatik II
Römerstraße 164, D-53117 BonnAngefertigt mit Genehmigung der Mathematisch-Naturwissenschaftlichen
Fakultät der Rheinischen Friedrich-Wilhelms-Universität Bonn
1. Gutachter: Prof. Dr. Reinhard Klein
2. Prof. Dr. Stefan Gumhold
Tag der Promotion: 27.9.2010
Erscheinungsjahr: 2010CONTENTS
List of Figures v
List of Tables xi
Abstract xiii
Zusammenfassung xv
Acknowledgements xvii
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5.1 Normals . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5.2 Moving Least-Squares Surface . . . . . . . . . . . . . . . 9
1.5.3 Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Primitive Detection 17
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Previous work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.1 Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2 Reverse engineering . . . . . . . . . . . . . . . . . . . . 20
2.2.3 Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.4 RANSAC . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4 Shape estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5.1 Probabilities . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 Sampling strategy . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6.1 Localized sampling . . . . . . . . . . . . . . . . . . . . . 28
iCONTENTS
2.6.2 Number of candidates . . . . . . . . . . . . . . . . . . . 30
2.7 Score . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.7.1 Connected components . . . . . . . . . . . . . . . . . . . 32
2.8 Score evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.8.1 Random subsets . . . . . . . . . . . . . . . . . . . . . . 32
2.8.2 Octree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.9 Refitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.10 Out-of-core detection . . . . . . . . . . . . . . . . . . . . . . . . 35
2.10.1 Maximal primitive extent . . . . . . . . . . . . . . . . . . 35
2.11 Alternate score . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.11.1 Minimum Description Length . . . . . . . . . . . . . . . 37
2.12 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.12.1 Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.12.2 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.12.3 Out-of-core detection . . . . . . . . . . . . . . . . . . . . 50
2.12.4 Alternate score . . . . . . . . . . . . . . . . . . . . . . . 51
2.13 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3 Compression 55
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.2 Previous work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.4 Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.4.1 Resampling . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.4.2 Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.4.3 Vector quantization . . . . . . . . . . . . . . . . . . . . . 62
3.4.4 Codebook generation . . . . . . . . . . . . . . . . . . . . 63
3.4.5 Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.4.6 On-disk compression . . . . . . . . . . . . . . . . . . . . 70
3.5 Decompression . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.6 Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.6.1 Level-of-detail . . . . . . . . . . . . . . . . . . . . . . . 72
3.6.2 Hole-free rendering . . . . . . . . . . . . . . . . . . . . . 72
3.6.3 Normal estimation . . . . . . . . . . . . . . . . . . . . . 73
3.7 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.8.1 Limitations and future work . . . . . . . . . . . . . . . . 78
iiCONTENTS
4 Recognition 81
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.2.1 3D city reconstruction . . . . . . . . . . . . . . . . . . . 82
4.2.2 Graph-based matching . . . . . . . . . . . . . . . . . . . 83
4.2.3 Matching with local features . . . . . . . . . . . . . . . . 84
4.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.4 Topology Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.5 Shape Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.5.1 Query graph . . . . . . . . . . . . . . . . . . . . . . . . 87
4.5.2 Constrained subgraph matching . . . . . . . . . . . . . . 88
4.5.3 First results . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.5.4 Query Graph Extensions . . . . . . . . . . . . . . . . . . 90
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.6.1 Future work . . . . . . . . . . . . . . . . . . . . . . . . . 96
5 Completion and Reconstruction 97
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.2 Previous work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.3 Shape primitive guided completion . . . . . . . . . . . . . . . . . 101
5.3.1 Shape primitive detection . . . . . . . . . . . . . . . . . . 103
5.4 Primitive adherence . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.4.1 Discrete global minimization . . . . . . . . . . . . . . . . 105
5.4.2 Placement of inside and outside constraints . . . . . . . . 107
5.5 Primitive connectivity . . . . . . . . . . . . . . . . . . . . . . . . 108
5.6 Reconstruction of detail . . . . . . . . . . . . . . . . . . . . . . . 109
5.7 Surface extraction . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.7.1 Consistent edge labeling . . . . . . . . . . . . . . . . . . 111
5.8 Height-fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.9 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . 114
5.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6 Conclusion 121
6.1 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
Bibliography 127
Data Sources 148
Publications 153
iiiCONTENTS
ivLIST OF FIGURES
1.1 Several scanned point-clouds from typical application scenarios.
From left to right: (a) A scanned street of houses for city plan-
ning (courtesy of the Institute for Cartography and Geoinformat-
ics Hannoverhttp://www.ikg.uni-hannover.de/en/).
(b) Lobby of an office building scanned for building redesign
(courtesy of Autodesk Researchhttp://www.digital210king.
org). (c) A point-cloud of an industrial complex acquired for
change management (courtesy of scannTec GmbH & CO. KG,
http://scanntec.com). (d) A turbine blade for reverse en-
gineering (courtesy of Georgia Tech Large Geometric Models Archive
www.cc.gatech.edu/projects/large_models/). . . . 2
1.2 Normal estimation: a) and d) The oil-pump and the box model
without normals rendered as OpenGL point primitives. b) and e)
The estimated normals using an adaptive neighborhood as pro-
posed in Jenke et al. [JKS08]. c) and f) Points colored according
to the normal confidence computed as suggested by Pauly et al.
+[PMG 05] (blue high confidence, red low confidence). Surface
edges, registration errors and sampling irregularities reduce the
confidence in the normal estimation. . . . . . . . . . . . . . . . . 8
1.3 Ray-traced MLS-Surfaces. On the left the point-clouds are shown
rendered as simple OpenGL point primitives with normals. Nor-
mals are for visualization purposes only and are not required for
finding the MLS-Surface. On the right the corresponding ray-
traced MLS-Surfaces are shown. The MLS-Surfaces are smooth
and contiguous. . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 The shape primitives considered in this work from left to right:
Plane, sphere, cylinder, cone and torus. The coloring in this figure
is used throughout this thesis to signify primitive type: red for
planes, yellow for spheres, green for cylinders, purple for cones
and grey for tori. . . . . . . . . . . . . . . . . . . . . . . . . . . 13
vLIST OF FIGURES
2.1 A small cylinder that has been detected by our