Three-Dimensional Model Analysis and Processing

✍ Scribed by Faxin Yu, Zheming Lu, Hao Luo, Pinghui Wang

• Publisher: Springer
• Year: 2011
• Tongue: English
• Leaves: 437
• Series: Advanced Topics in Science and Technology in China
• Edition: 1st Edition.
• Category: Library

✦ Synopsis

"Three-Dimensional Model Analysis and Processing" focuses on five hot research directions in 3D model analysis and processing in computer science, i.e., on compression, feature extraction, content-based retrieval, irreversible watermarking and reversible watermarking. The book is based on a wide range of new content, systematic and theoretical, and fully reflects the state-of-the-art in 3D model analysis and processing technologies. This book is intended for researchers, engineers and graduate students working in 3D model analysis and processing. Faxin Yu is an Associate Professor at the School of Aeronautics and Astronautics, Zhejiang University, China; both Zheming Lu and Pinghui Wang are also Professors there; Hao Luo is a Lecturer there.

✦ Table of Contents

Cover......Page 1
ADVANCED TOPICS
IN SCIENCE AND TECHNOLOGY IN CHINA......Page 2
Three-Dimensional Model
Analysis and Processing......Page 4
ISBN 9783642126505......Page 5
Preface......Page 6
Table of Contents
......Page 10
1.1.1 Technical Development Course of Multimedia......Page 17
1.1.2 Information Explosion......Page 19
1.1.3 Network Information Security......Page 22
1.1.4 Technical Requirements of 3D Models......Page 25
1.2.1 3D Models......Page 27
1.2.2 3D Modeling Schemes......Page 29
1.2.2.1 Geometric-Modeling-Based Techniques......Page 30
1.2.2.2 3D Scanner-Based Techniques......Page 33
1.2.2.3 Image-Based Modeling Techniques......Page 35
1.2.3 Polygon Meshes......Page 36
1.2.4 3D Model File Formats and Processing Software......Page 38
1.2.4.2 AutoCAD......Page 39
1.2.4.4 Maya......Page 41
1.2.4.5 3DS File Format......Page 42
1.2.4.6 OBJ File Format......Page 43
1.2.4.7 OFF File Format......Page 45
1.2.4.8 DXF File Format......Page 46
1.3.1.1 Processing Techniques for 3D Model Construction......Page 47
1.3.1.2 Processing Techniques for 3D Model Transmission and Storage......Page 49
1.3.1.3 Processing Techniques for 3D Model Management and Retrieval......Page 50
1.3.2 Overview of 3D Model Analysis Techniques......Page 51
1.4.1 Concepts of Data Compression......Page 54
1.4.2.1 Lossless Audio Compression......Page 55
1.4.2.2 Lossy Audio Compression......Page 56
1.4.3 Overview of Image Compression Techniques......Page 58
1.4.3.1 Lossless Image Compression......Page 59
1.4.3.2 Lossy Image Compression......Page 60
1.4.4 Overview of Video Compression Techniques......Page 62
1.5.1 Requirement Background......Page 64
1.5.2 Concepts of Digital Watermarks......Page 66
1.5.3 Basic Framework of Digital Watermarking Systems......Page 67
1.5.4 Communication-Based Digital Watermarking Models......Page 68
1.5.5 Classification of Digital Watermarking Techniques......Page 70
1.5.6 Applications of Digital Watermarking Techniques......Page 72
1.5.7 Characteristics of Watermarking Systems......Page 74
1.6.1 Concepts of Information Retrieval......Page 78
1.6.2 Summary of Content-Based Multimedia Retrieval......Page 81
1.6.3 Content-Based Image Retrieval......Page 83
1.6.4.2 Video Structure and Related Algorithms......Page 86
1.6.4.3 Feature Extraction......Page 88
1.6.4.4 Video Retrieval and Browsing......Page 89
1.6.5.1 Some Concepts of Digital Audio......Page 90
1.6.5.2 Overview of Content-Based Audio Retrieval......Page 91
1.6.5.3 Sound Retrieval......Page 92
1.6.5.5 Music Retrieval......Page 94
1.7.1 Basic Concept of Hashing Functions......Page 96
1.7.2 Concepts and Properties of Perceptual Hashing Functions......Page 97
1.7.3 The State-of-the-Art of Perceptual Hashing Functions......Page 99
1.7.4.1 Pattern Recognition......Page 101
1.7.4.2 Multimedia Retrieval......Page 102
1.8 Main Content of This Book......Page 103
References......Page 104
2.1.1 Background......Page 106
2.1.2.1 Surface-Based Models......Page 109
2.1.2.2 Connectivity......Page 110
2.1.2.3 Geometry......Page 114
2.1.2.4 Triangle Meshes......Page 115
2.1.3 Algorithm Classification......Page 116
2.2 Single-Rate Connectivity Compression......Page 118
2.2.1 Representation of Indexed Face Set......Page 119
2.2.2 Triangle-Strip-Based Connectivity Coding......Page 120
2.2.3 Spanning-Tree-Based Connectivity Coding......Page 121
2.2.4 Layered-Decomposition-Based Connectivity Coding......Page 123
2.2.5 Valence-Driven Connectivity Coding Approach......Page 124
2.2.6 Triangle Conquest Based Connectivity Coding......Page 127
2.2.7 Summary......Page 131
2.3 Progressive Connectivity Compression......Page 132
2.3.1 Progressive Meshes......Page 133
2.3.1.2 Progressive Forest Split......Page 135
2.3.2 Patch Coloring......Page 137
2.3.3 Valence-Driven Conquest......Page 138
2.3.4 Embedded Coding......Page 140
2.3.5 Layered Decomposition......Page 141
2.3.6 Summary......Page 142
2.4 Spatial-Domain Geometry Compression......Page 143
2.4.1 Scalar Quantization......Page 144
2.4.2.2 Linear Prediction......Page 145
2.4.2.3 Parallelogram Prediction......Page 146
2.4.2.5 Other Improved Prediction Methods......Page 147
2.4.3 k-d Tree......Page 148
2.4.4 Octree Decomposition......Page 149
2.5 Transform Based Geometric Compression......Page 150
2.5.1 Single-Rate Spectral Compression of Mesh Geometry......Page 151
2.5.2 Progressive Compression Based on Wavelet Transform......Page 152
2.5.3 Geometry Image Coding......Page 155
2.5.4 Summary......Page 156
2.6 Geometry Compression Based on Vector Quantization......Page 157
2.6.2 Quantization of 3D Model Space Vectors......Page 158
2.6.3 PVQ-Based Geometry Compression......Page 159
2.6.4 Fast VQ Compression for 3D Mesh Models......Page 160
2.6.4.2 Online Steps......Page 161
2.6.5.1 Basic DRCVQ Idea......Page 163
2.6.5.2 Vector Quantizer Design......Page 164
2.6.5.3 Adjustable Parameter......Page 165
2.6.5.4 Other Considerations......Page 166
2.6.5.5 Simulation Results......Page 168
References......Page 171
3.1.1 Background......Page 177
3.1.1.1 Content-Based 3D Model Retrieval......Page 178
3.1.1.2 3D Scene Registration......Page 179
3.1.2.1 Features......Page 180
3.1.2.2 Feature Extraction......Page 181
3.1.2.4 Requirements for 3D Feature Extraction......Page 182
3.1.3 Classification of 3D Feature Extraction Algorithms......Page 183
3.2 Statistical Feature Extraction......Page 184
3.2.1.1 Sampling to Approximate the Moments......Page 185
3.2.1.2 Normalizing the Objects......Page 186
3.2.2 3D Zernike Moments......Page 187
3.2.3.1 3D Shape Histogram......Page 189
3.2.3.2 Crease Angle Histogram......Page 191
3.2.4 Point Density......Page 192
3.2.4.2 Equivalent Classes......Page 193
3.2.5 Shape Distribution Functions......Page 196
3.2.5.1 Selecting a Shape Function......Page 197
3.2.5.2 Constructing Shape Distributions......Page 198
3.2.5.3 Improved Methods......Page 200
3.2.6 Extended Gaussian Image......Page 201
3.2.6.3 Gaussian Curvature for Smoothly Curved Surfaces......Page 202
3.2.6.4 Extended Gaussian Image Definition for Smoothly Curved Surfaces......Page 203
3.3 Rotation-Based Shape Descriptor......Page 204
3.3.1.2 Rotation of the Model......Page 206
3.3.1.3 Calculation of Normal Distributions......Page 207
3.3.1.4 Construction of Histograms......Page 208
3.3.2 Experimental Results......Page 209
3.4.1 Detailed Procedure......Page 210
3.4.1.2 Computation of Subfeatures......Page 211
3.4.2 Experimental Results......Page 213
3.5 Global Geometry Feature Extraction......Page 214
3.5.1.2 Feature Extraction......Page 215
3.5.1.4 Other Methods......Page 216
3.5.2 Weighted Point Sets......Page 217
3.5.3 Other Methods......Page 218
3.6.1.1 Discrete Fourier Transform......Page 219
3.6.1.2 Vranie and Soupe’s Scheme......Page 220
3.6.1.3 Other Schemes......Page 221
3.6.2.1 Spherical Harmonics......Page 222
3.6.2.2 Rotation Invariant Descriptors......Page 223
3.6.2.3 Further Quadratic Invariance......Page 224
3.6.3 Wavelet Transform......Page 225
3.6.3.1 Spherical Wavelets for 3D Shape Description......Page 226
3.6.3.2 Spherical Wavelet-Based Descriptors......Page 227
3.7.1.1 Spin Images......Page 230
3.7.1.3 2D Slicing......Page 231
3.7.1.4 Harmonic Shape Images......Page 232
3.7.2.2 Aspect Graph......Page 234
3.7.2.3 Light Field Descriptor......Page 235
3.8.1 Introduction......Page 236
3.8.2.1 Reeb Graph......Page 238
3.8.2.3 MRG Feature Extraction......Page 239
3.8.3 Skeleton Graph......Page 240
3.9.1 Introduction......Page 242
3.9.2 Color Feature Extraction......Page 243
3.10 Summary......Page 244
References......Page 246
4.1.1 Background......Page 252
4.1.2.1 3D Model Benchmark Databases......Page 255
4.1.2.2 Performance Evaluation Methods......Page 256
4.2.1 Overview of Content-Based 3D Model Retrieval......Page 260
4.2.2 Challenges in Content-Based 3D Model Retrieval......Page 262
4.2.3 Framework of Content-Based 3D Model Retrieval......Page 263
4.2.4.1 Model File Format......Page 264
4.2.4.5 Index for Highly Efficient Search......Page 265
4.3.1 Overview......Page 266
4.3.2.1 PCA-Based Pose Normalization......Page 267
4.3.2.2 Finding the Only Bounding Box of the 3D Model......Page 270
4.3.3 Polygon Triangulation......Page 272
4.3.3.1 Ear Subtraction Method......Page 273
4.3.4 Mesh Segmentation......Page 274
4.3.5 Vertex Clustering......Page 276
4.4.1 Primitive-Based Feature Extraction......Page 277
4.4.1.2 Approximation of a 3D Segment......Page 278
4.4.1.4 Normalization in the 3D Space......Page 280
4.4.2.2 Antini et al.’s Method......Page 281
4.4.3 Geometry-Based Feature Extraction......Page 284
4.4.4 View-Based Feature Extraction......Page 288
4.5.1.1 Minkowski Distances......Page 289
4.5.1.4 Improved Earthmover’s Distances......Page 290
4.5.2 Graph-Matching Algorithms......Page 291
4.5.3 Machine-Learning Methods......Page 293
4.5.3.1 SVM......Page 294
4.5.3.2 SOM......Page 296
4.5.3.3 KNN Learning......Page 298
4.5.3.4 Relevance Feedback......Page 299
4.5.4 Semantic Measurements......Page 302
4.6.1 Query by Example......Page 304
4.6.2 Query by 2D Projections......Page 305
4.6.4 Query by 3D Sketches......Page 308
4.6.5 Query by Text......Page 309
4.6.6 Multimodal Queries and Relevance Feedback......Page 310
4.7 Summary......Page 311
References......Page 313
5.1 Introduction......Page 320
5.2 3D Model Watermarking System and Its Requirements......Page 323
5.2.1 Digital Watermarking......Page 324
5.2.2 3D Model Watermarking Framework......Page 325
5.2.3 Difficulties......Page 326
5.2.4.1 Imperceptivity (Transparency)......Page 327
5.2.4.2 Robustness and Security......Page 328
5.2.4.4 Space Utilization......Page 330
5.2.4.8 Minimum Preprocessing Overhead......Page 331
5.3.1.3 Encoding Redundancy......Page 332
5.3.2 Classification According to Robustness......Page 333
5.3.4 Classification According to Embedding Domains......Page 334
5.3.7 Classification According to Reversibility......Page 335
5.4 Spatial-Domain-Based 3D Model Watermarking......Page 336
5.4.1.1 Spread-Spectrum Mechanism......Page 337
5.4.1.2 Masking Based on Connected Vertices......Page 338
5.4.1.3 Dithered Modulation in the Ellipsoid Derived from Connected Vertices......Page 339
5.4.2.1 Modifying the Distances from the Centroid to Vertices......Page 341
5.4.2.3 Altering the Length of Specific Vectors......Page 344
5.4.3.1 Triangle Similarity Quadruple (TSQ)......Page 345
5.4.3.3 Quantization Index Modulation......Page 347
5.4.4 Using a Tetrahedron as the Embedding Primitive......Page 349
5.4.6 Modification of Surface Normal Distribution......Page 352
5.5 A Robust Adaptive 3D Mesh Watermarking Scheme......Page 353
5.5.1.1 Watermark Embedding Process......Page 354
5.5.1.2 Watermark Extraction Process......Page 356
5.5.2.1 Control of Watermark Embedding Strength......Page 358
5.5.2.2 Control of the Watermark Embedding Direction......Page 360
5.5.3.1 Noise Attacks......Page 363
5.5.3.3 Simplification Attacks......Page 364
5.5.3.4 Insection Attacks......Page 365
5.5.3.6 Combination Attacks......Page 366
5.6 3D Watermarking in Transformed Domains......Page 367
5.6.1 Mesh Watermarking in Wavelet Transform Domains......Page 368
5.6.2.1 3D Surface Transform......Page 369
5.6.3 Mesh Watermarking Based on the Burt-Adelson Pyramid......Page 370
5.6.3.1 Relaxation Operator and Burt-Adelson Pyramid......Page 371
5.6.3.2 Watermark Embedding......Page 373
5.6.3.3 Watermark Detection......Page 374
5.6.4.1 Laplacian-Operator-Based Discrete Fourier Analysis for 3D meshes......Page 375
5.6.4.2 Watermark Embedding......Page 376
5.6.5 Other Algorithms......Page 377
5.7.1 Watermarking Methods for NURBS Curves and Surfaces......Page 378
5.7.3 3D Animation Watermarking......Page 379
5.8 Summary......Page 380
References......Page 382
6 Reversible Data Hiding in 3D Models......Page 387
6.1.1 Background......Page 388
6.1.2 Requirements and Performance Evaluation Criteria......Page 389
6.2.1.2 Type-II Algorithms......Page 390
6.1.2.3 Type-III Algorithms......Page 391
6.2.2 Difference-Expansion-Based Reversible Data Hiding......Page 392
6.2.3 Histogram-Shifting-Based Reversible Data Hiding......Page 395
6.2.4.2 Digital Photography as Legal Evidence......Page 396
6.3.1 General System......Page 397
6.3.2 Challenges of 3D Model Reversible Data Hiding......Page 398
6.4 Spatial Domain 3D Model Reversible Data Hiding......Page 399
6.4.1 3D Mesh Authentication......Page 400
6.4.2 Encoding Stage......Page 401
6.4.3 Decoding Stage......Page 403
6.4.4 Experimental Results and Discussions......Page 404
6.5 Compressed Domain 3D Model Reversible Data Hiding......Page 406
6.5.1 Scheme Overview......Page 407
6.5.2 Predictive Vector Quantization......Page 408
6.5.3 Data Embedding......Page 409
6.5.5 Performance Analysis......Page 410
6.5.6 Experimental Results......Page 411
6.5.7.1 Data Embedding......Page 413
6.5.7.2 Data Extraction and Mesh Recovery......Page 414
6.6 Transform Domain Reversible 3D Model Data Hiding......Page 417
6.6.1 Introduction......Page 418
6.6.2 Scheme Overview......Page 419
6.6.2.2 Data Extraction......Page 420
6.6.3.2 Clustering......Page 421
6.6.3.4 Modulation of Coefficients......Page 422
6.6.4.3 Coefficient Demodulation......Page 424
6.6.5 Experimental Results......Page 425
6.6.6 Bit-Shifting-Based Coefficients Modulation......Page 426
6.7 Summary......Page 427
References......Page 428
Index......Page 433