1 Introduction 1
1.1 Background 1
1.1.1 Technical Development Course of Multimedia 1
1.1.2 Information Explosion 3
1.1.3 Network Information Security 6
1.1.4 Technical Requirements of 3D Models 9
1.2 Concepts and Descriptions of 3D Models 11
1.2.1 3D Models 11
1.2.2 3D Modeling Schemes 13
1.2.3 Polygon Meshes 20
1.2.4 3D Model File Formats and Processing Software 22
1.3 Overview of 3D Model Analysis and Processing 31
1.3.1 Overview of 3D Model Processing Techniques 31
1.3.2 Overview of 3D Model Analysis Techniques 35
1.4 Overview of Multimedia Compression Techniques 38
1.4.1 Concepts of Data Compression 38
1.4.2 Overview of Audio Compression Techniques 39
1.4.3 Overview of Image Compression Techniques 42
1.4.4 Overview of Video Compression Techniques 46
1.5 Overview of Digital Watermarking Techniques 48
1.5.1 Requirement Background 48
1.5.2 Concepts of Digital Watermarks 50
1.5.3 Basic Framework of Digital Watermarking Systems 51
1.5.4 Communication-Based Digital Watermarking Models 52
1.5.5 Classification of Digital Watermarking Techniques 54
1.5.6 Applications of Digital Watermarking Techniques 56
1.5.7 Characteristics of Watermarking Systems 58
1.6 Overview of Multimedia Retrieval Techniques 62
1.6.1 Concepts of Information Retrieval 62
1.6.2 Summary of Content-Based Multimedia Retrieval 65
1.6.3 Content-Based Image Retrieval 67
1.6.4 Content-Based Video Retrieval 70
1.6.5 Content-Based Audio Retrieval 74
1.7 Overview of Multimedia Perceptual Hashing Techniques 80
1.7.1 Basic Concept of Hashing Functions 80
1.7.2 Concepts and Properties of Perceptual Hashing Functions 81
1.7.3 The State-of-the-Art of Perceptual Hashing Functions 83
1.7.4 Applications of Perceptual Hashing Functions 85
1.8 Main Content of This Book 87
References 88
2 3D Mesh Compression 91
2.1 Introduction 91
2.1.1 Background 91
2.1.2 Basic Concepts and Definitions 93
2.1.3 Algorithm Classification 100
2.2 Single-Rate Connectivity Compression 102
2.2.1 Representation of Indexed Face Set 103
2.2.2 Triangle-Strip-Based Connectivity Coding 104
2.2.3 Spanning-Tree-Based Connectivity Coding 105
2.2.4 Layered-Decomposition-Based Connectivity Coding 107
2.2.5 Valence-Driven Connectivity Coding Approach 108
2.2.6 Triangle Conquest Based Connectivity Coding 111
2.2.7 Summary 115
2.3 Progressive Connectivity Compression 116
2.3.1 Progressive Meshes 117
2.3.2 Patch Coloring 121
2.3.3 Valence-Driven Conquest 122
2.3.4 Embedded Coding 124
2.3.5 Layered Decomposition 125
2.3.6 Summary 126
2.4 Spatial-Domain Geometry Compression 127
2.4.1 Scalar Quantization 128
2.4.2 Prediction 129
2.4.3 k-d Tree 132
2.4.4 Octree Decomposition 133
2.5 Transform Based Geometric Compression 134
2.5.1 Single-Rate Spectral Compression ofMesh Geometry 135
2.5.2 Progressive Compression Based on Wavelet Transform 136
2.5.3 Geometry Image Coding 139
2.5.4 Summary 140
2.6 Geometry Compression Based on Vector Quantization 141
2.6.1 Introduction to Vector Quantization 142
2.6.2 Quantization of 3D Model Space Vectors 142
2.6.3 PVQ-Based Geometry Compression 143
2.6.4 Fast VQ Compression for 3D Mesh Models 144
2.6.5 VQ Scheme Based on Dynamically Restricted Codebook 147
2.7 Summary 155
References 155
3 3D Model Feature Extraction 161
3.1 Introduction 161
3.1.1 Background 161
3.1.2 Basic Concepts and Definitions 164
3.1.3 Classification of 3D Feature Extraction Algorithms 167
3.2 Statistical Feature Extraction 168
3.2.1 3D Moments of Surface 169
3.2.2 3D Zernike Moments 171
3.2.3 3D Shape Histograms 173
3.2.4 Point Density 176
3.2.5 Shape Distribution Functions 180
3.2.6 Extended Gaussian Image 185
3.3 Rotation-Based Shape Descriptor 188
3.3.1 Proposed Algorithm 190
3.3.2 Experimental Results 193
3.4 Vector-Quantization-Based Feature Extraction 194
3.4.1 Detailed Procedure 194
3.4.2 Experimental Results 197
3.5 Global Geometry Feature Extraction 198
3.5.1 Ray-Based Geometrical Feature Representation 199
3.5.2 Weighted Point Sets 201
3.5.3 Other Methods 202
3.6 Signal-Analysis-Based Feature Extraction 203
3.6.1 Fourier Descriptor 203
3.6.2 Spherical Harmonic Analysis 206
3.6.3 Wavelet Transform 209
3.7 Visual-Image-Based Feature Extraction 214
3.7.1 Methods on Based 2D Functional Projection 214
3.7.2 Methods on Based 2D Planar View Mapping 218
3.8 Topology-Based Feature Extraction 220
3.8.1 Introduction 220
3.8.2 Multi-resolution Reeb Graph 222
3.8.3 Skeleton Graph 224
3.9 Appearance-Based Feature Extraction 226
3.9.1 Introduction 226
3.9.2 Color Feature Extraction 227
3.9.3 Texture Feature Extraction 228
3.10 Summary 228
References 230
4 Content-Based 3D Model Retrieval 237
4.1 Introduction 237
4.1.1 Background 237
4.1.2 Performance Evaluation Criteria 239
4.2 Content-Based 3D Model Retrieval Framework 244
4.2.1 Overview of Content-Based 3D Model Retrieval 244
4.2.2 Challenges in Content-Based 3D Model Retrieval 246
4.2.3 Framework of Content-Based 3D Model Retrieval 247
4.2.4 Important Issues in Content-Based 3D Model Retrieval 248
4.3 Preprocessing of 3D Models 250
4.3.1 Overview 250
4.3.2 Pose Normalization 251
4.3.3 Polygon Triangulation 256
4.3.4 Mesh Segmentation 258
4.3.5 Vertex Clustering 260
4.4 Feature Extraction 261
4.4.1 Primitive-Based Feature Extraction 261
4.4.2 Statistics-Based Feature Extraction 265
4.4.3 Geometry-Based Feature Extraction 268
4.4.4 View-Based Feature Extraction 272
4.5 Similarity Matching 273
4.5.1 Distance Metrics 273
4.5.2 Graph-Matching Algorithms 275
4.5.3 Machine-Learning Methods 277
4.5.4 Semantic Measurements 286
4.6 Query Style and User Interface 288
4.6.1 Query by Example 288
4.6.2 Query by 2D Projections 289
4.6.3 Query by 2D Sketches 292
4.6.4 Query by 3D Sketches 292
4.6.5 Query by Text 293
4.6.6 Multimodal Queries and Relevance Feedback 294
4.7 Summary 295
References 297
5 3D Model Watermarking 305
5.1 Introduction 305
5.2 3D Model Watermarking System and Its Requirements 307
5.2.1 Digital Watermarking 308
5.2.2 3D Model Watermarking Framework 309
5.2.3 Difficulties 310
5.2.4 Requirements 311
5.3 Classifications of 3D Model WatermarkingAlgorithms 316
5.3.1 Classification According to Redundancy Utilization 316
5.3.2 Classification According to Robustness 317
5.3.3 Classification According to Complexity 318
5.3.4 Classification According to Embedding Domains 318
5.3.5 Classification According to Obliviousness 319
5.3.6 Classification According to 3D Model Types 319
5.3.7 Classification According to Reversibility 319
5.3.8 Classification According to Transparency 320
5.4 Spatial-Domain-Based 3D Model Watermarking 320
5.4.1 Vertex Disturbance 321
5.4.2 Modifying Distances or Lengths 325
5.4.3 Adopting Triangle/Strip as Embedding Primitives 329
5.4.4 Using a Tetrahedron as the Embedding Primitive 333
5.4.5 Topology Structure Adjustment 336
5.4.6 Modification of Surface Normal Distribution 336
5.4.7 Attribute Modification 337
5.4.8 Redundancy-Based Methods 337
5.5 A Robust Adaptive 3D Mesh Watermarking Scheme 337
5.5.1 Watermarking Scheme 338
5.5.2 Parameter Control for Watermark Embedding 342
5.5.3 Experimental Results 347
5.5.4 Conclusions 351
5.6 3D Watermarking in Transformed Domains 352
5.6.1 Mesh Watermarking in Wavelet Transform Domains 352
5.6.2 Mesh Watermarking in the RST Invariant Space 353
5.6.3 Mesh Watermarking Based on the Burt-Adelson Pyramid 354
5.6.4 Mesh Watermarking Based on Fourier Analysis 359
5.6.5 Other Algorithms 361
5.7 Watermarking Schemes for Other Types of 3D Models 362
5.7.1 Watermarking Methods for NURBS Curves and Surfaces 362
5.7.2 3D Volume Watermarking 363
5.7.3 3D Animation Watermarking 363
5.8 Summary 364
References 366
6 Reversible Data Hiding in 3D Models 371
6.1 Introduction 372
6.1.1 Background 372
6.1.2 Requirements and Performance Evaluation Criteria 373
6.2 Reversible Data Hiding for Digital Images 374
6.2.1 Classification ofReversible Data Hiding Schemes 374
6.2.2 Difference-Expansion-Based Reversible Data Hiding 376
6.2.3 Histogram-Shifting-Based Reversible Data Hiding 379
6.2.4 Applications of Reversible Data Hiding for Images 380
6.3 Reversible Data Hiding for 3D Models 381
6.3.1 General System 381
6.3.2 Challenges of 3D Model Reversible Data Hiding 382
6.3.3 Algorithm Classification 383
6.4 Spatial Domain 3D Model Reversible Data Hiding 383
6.4.1 3D MeshAuthentication 384
6.4.2 Encoding Stage 385
6.4.3 Decoding Stage 387
6.4.4 Experimental Results and Discussions 388
6.5 Compressed Domain 3D Model Reversible Data Hiding 390
6.5.1 Scheme Overview 391
6.5.2 Predictive Vector Quantization 392
6.5.3 Data Embedding 393
6.5.4 Data Extraction and Mesh Recovery 394
6.5.5 Performance Analysis 394
6.5.6 Experimental Results 395
6.5.7 Capacity Enhancement 397
6.6 Transform Domain Reversible 3D Model Data Hiding 401
6.6.1 Introduction 402
6.6.2 Scheme Overview 403
6.6.3 Data Embedding 405
6.6.4 Data Extraction 408
6.6.5 Experimental Results 409
6.6.6 Bit-Shifting-Based Coefficients Modulation 410
6.7 Summary 411
References 412
Index 417