Digital Image Analysis (eBook)

Preface 6
About This Book 6
The Compact Disc 7
Acknowledgments 8
Contributors 10
Contents 16
List of Figures 23
List of Tables 30
Part I Mathematical Methods for Image Analysis 31
Introduction to Part I 32
1 Numerical Harmonic Analysis and Image Processing 35
1.1 Gabor Analysis and Digital Signal Processing 35
1.1.1 From Fourier to Gabor Expansions 36
1.1.2 Local Time-Frequency Analysis and Short-Time Fourier Transform 43
1.1.3 Fundamental Properties of Gabor Frames 45
1.1.4 Commutation Relations of the Gabor Frame Operator 46
1.1.5 Critical Sampling, Oversampling, and the Balian-Low Theorem 46
1.1.6 Wexler-Raz Duality Condition 51
1.1.7 Gabor Analysis on LCA Groups 52
1.1.8 Numerical Gabor Analysis 58
1.1.9 Image Representation and Gabor Analysis 62
1.2 Signal and Image Reconstruction 62
1.2.1 Notation 63
1.2.2 Signal Reconstruction and Frames 64
1.2.3 Numerical Methods for Signal Reconstruction 65
1.3 Examples and Applications 68
1.3.1 Object Boundary Recovery in Echocardiography 71
1.3.2 Image Reconstruction in Exploration Geophysics 72
1.3.3 Reconstruction of Missing Pixels in Images 74
2 Stochastic Shape Theory 76
2.1 Shape Analysis 76
2.2 Contour Line Parameterization 78
2.3 Deformable Templates 79
2.3.1 Stochastic Planar Deformation Processes 80
2.3.2 Gaussian Isotropic Random Planar Deformations 81
2.3.3 The Deformable Templates Model 82
2.3.4 Maximum Likelihood Classi.cation 83
2.4 The Wavelet Transform 85
2.4.1 Atomic Decompositions and Group Theory 86
2.4.2 Discrete Wavelets and Multiscale Analysis 89
2.4.3 Wavelet Packets 94
2.5 Wavelet Packet Descriptors 99
2.6 Global Nonlinear Optimization 101
2.6.1 Multilevel Single-Linkage Global Optimization 102
2.6.2 Implementation 104
3 Image Compression and Coding 107
3.1 Image Compression 107
3.1.1 Lossy Compression and Machine Vision 108
3.1.2 Multilevel Polynomial Interpolation 116
3.1.3 Enhancing the FBI Fingerprint Compression Standard 121
3.2 Multimedia Data Encryption 128
3.2.1 Symmetric Product Ciphers 128
3.2.2 Permutation by Chaotic Kolmogorov Flows 129
3.2.3 Substitution by AWC or SWB Generators 134
3.2.4 Security Considerations 137
3.2.5 Encryption Experiments 137
3.2.6 Encryption Summary 140
References 141
Part II Data Handling 157
Introduction to Part II 158
4 Parallel and Distributed Processing 159
4.1 Dealing with Large Remote Sensing Image Data Sets 159
4.1.1 Demands of Earth Observation 159
4.1.2 Processing Radar-Data of the Magellan Venus Probe 161
4.2 Parallel Radar Signal Processing 162
4.2.1 Parallelization Strategy 162
4.2.2 Evaluation of Parallelization Tools 163
4.2.3 Program Analysis and Parallelization 165
4.3 Parallel Radar Image Processing 167
4.3.1 Data Decomposition and Halo Handling 168
4.3.2 Dynamic Load Balancing and Communication Overloading 169
4.3.3 Performance Assessment 170
4.4 Distributed Processing 173
4.4.1 Front End 174
4.4.2 Back End 174
4.4.3 Broker 175
4.4.4 Experiences 177
5 Image Data Catalogs 178
5.1 Online Access to Remote Sensing Imagery 179
5.1.1 Remote Sensing Data Management 179
5.1.2 Image Data Information and Request System 181
5.1.3 Online Product Generation and Delivery 182
5.2 Content-Based Image Database Indexing and Retrieval 184
5.2.1 The Miniature Portrait Database 186
5.2.2 The Eigen Approach 189
5.2.3 Experiments 191
References 193
Part II Robust and Adaptive Image Understanding 197
Introduction to Part III 198
6 Graphs in Image Analysis 200
6.1 From Pixels to Graphs 200
6.1.1 Graphs in the Square Grid 201
6.1.2 Run Graphs 201
6.1.3 Area Voronoi Diagram 205
6.2 Graph Transformations in Image Analysis 212
6.2.1 Arrangements of Image Elements 212
6.2.2 Dual Graph Contraction 214
7 Hierarchies 219
7.1 Regular Image Pyramids 219
7.1.1 Structure 221
7.1.2 Contents 223
7.1.3 Processing 223
7.1.4 Fuzzy Curve Pyramid 225
7.2 Irregular Graph Pyramids 228
7.2.1 Computational Complexity 229
7.2.2 Irregular Pyramids by Hop.eld Networks 230
7.2.3 Equivalent Contraction Kernels 233
7.2.4 Extensions to 3D 236
8 Robust Methods 239
8.1 The Role of Robustness in Computer Vision 239
8.2 Parametric Models 240
8.2.1 Robust Estimation Methods 240
8.3 Robust Methods in Vision 241
8.3.1 Recover-and-Select Paradigm 241
8.3.2 Recover-and-Select applied to 247
9 Structural Object Recognition 256
9.1 2-D and 3-D Structural Features 256
9.2 Feature Selection 257
9.3 Matching Structural Descriptions 257
9.4 Reducing Search Complexity 258
9.5 Grouping and Indexing 258
9.5.1 Early Search Termination 259
9.6 Detection of Polymorphic Features 260
9.7 Polymorphic Grouping 260
9.8 Indexing and Matching 261
9.9 Polymorphic Features 261
9.10 3-D Object Recognition Example 262
9.10.1 The IDEAL System 262
9.10.2 Initial Structural Part Decomposition 263
9.10.3 Part Adjacency and Compatibility Graphs 264
9.10.4 Automatic Model Acquisition 266
9.10.5 Object Recognition from Appearances 267
9.10.6 Experiments 268
10 Machine Learning 269
10.1 What Is Machine Learning? 269
10.1.1 What Do Machine Learning Algorithms Need? 270
10.1.2 One Method Solves All? Use of Multistrategy 270
10.2 Methods 271
10.3 Operational 272
10.3.1 Discrimination and Classi.cation 274
10.3.2 Optimization and Search 274
10.3.3 Functional Relationship 275
10.3.4 Logical Operations 275
10.4 Object-Oriented Generalization 275
10.5 Generalized Logical Structures 276
10.5.1 Reformulation 277
10.5.2 Object-Oriented Implementation 278
10.6 Generalized Clustering Algorithms 279
10.6.1 Function Overloading 280
Conclusion 281
References 282
Part IV Information Fusion and Radiometric Models for Image Understanding 298
Introduction to Part IV 299
11 Information Fusion in Image Understanding 300
11.1 Active Fusion 301
11.2 Active Object Recognition 302
11.2.1 Related Research 304
11.3 Feature Space Active Recognition 305
11.3.1 Object Recognition in Parametric Eigenspace 306
11.3.2 Probability Distributions in Eigenspace 307
11.3.3 View Classi.cation and Pose Estimation 308
11.3.4 Information Integration 309
11.3.5 View Planning 310
11.3.6 The Complexity of the Algorithm 311
11.3.7 Experiments 312
11.3.8 A Counterexample for Conditional Independence in Equation ( 11.5) 318
11.3.9 Conclusion 319
11.4 Reinforcement Learning for Active Object Recognition 320
11.4.1 Adaptive Generation of Object Hypotheses 322
11.4.2 Learning Recognition Control 325
11.4.3 Experiments 327
11.4.4 Discussion and Outlook 332
11.5 Generic Active Object Recognition 332
11.5.1 Object Models 333
11.5.2 Recognition System 334
11.5.3 Hypothesis Generation 334
11.5.4 Visibility Space 338
11.5.5 Viewpoint Estimation 341
11.5.6 Viewpoints and Actions 344
11.5.7 Motion Planning 346
11.5.8 Object Hypotheses Fusion 348
11.5.9 Conclusion 349
12 Image Understanding Methods for Remote Sensing 351
12.1 Radiometric Models 353
12.2 Subpixel Analysis of Remotely Sensed Images 360
12.3 Segmentation of Remotely Sensed Images 364
12.4 Land-Cover Classi.cation 367
12.5 Information Fusion for Remote Sensing 369
References 372
Part V 3D Reconstruction 380
Introduction to Part V 381
13 Fundamentals 384
13.1 Image Acquisition Aspects 384
13.1.1 Video Cameras 385
13.1.2 Amateur Cameras with CCD Sensors 385
13.1.3 Analog Metric Cameras 385
13.1.4 Remote Sensing Scanners 386
13.1.5 Other Visual Sensor Systems 387
13.2 Perspective Transformation 387
13.3 Stereo Reconstruction 391
13.4 Bundle Block Con.gurations 393
13.5 From Points and Lines to Surfaces 394
13.5.1 Representation of Irregular Object Surfaces 396
13.5.2 Representation of Man-Made Objects 399
13.5.3 Hybrid Representation of Object Surfaces 401
14 Image Matching Strategies 403
14.1 Raster-Based Matching Techniques 405
14.1.1 Cross Correlation 405
14.1.2 Least Squares Matching 407
14.2 Feature-Based Matching Techniques 409
14.2.1 Feature Extraction 409
14.2.2 Matching Homologous Image Features 412
14.3 Hierarchical Feature Vector Matching (HFVM) 416
14.3.1 Feature Vector Matching (FVM) 416
14.3.2 Subpixel Matching 419
14.3.3 Consistency Check 419
14.3.4 Hierarchical Feature Vector Matching 419
15 Precise Photogrammetric Measurement: Location of Targets and Reconstruction of Object Surfaces 421
15.1 Automation in Photogrammetric Plotting 423
15.1.1 Automation of Inner Orientation 424
15.1.2 Automation of Outer Orientation 424
15.2 Location of Targets 425
15.2.1 Location of Circular Symmetric Targets by Intersection of Gradient Vectors 426
15.2.2 Location of Arbitrarily Shaped Targets 427
15.2.3 The OEEPE Test on Digital Aerial Triangulation 429
15.2.4 Deformation Analysis of Wooden Doors 430
15.3 A General Framework for Object Reconstruction 432
15.3.1 Hierarchical Object Reconstruction 433
15.3.2 Mathematical Formulation of the Object Models 437
15.3.3 Robust Hybrid Adjustment 439
15.3.4 DEM Generation for Topographic Mapping 440
15.4 Semiautomatic Building Extraction 441
15.4.1 Building Models 443
15.4.2 Interactive Determination of Approximations 444
15.4.3 Automatic Fine Reconstruction 446
15.5 State of Work 447
16 3D Navigation and Reconstruction 448
16.1 High Accurate Stereo Reconstruction of Naturally Textured Surfaces for Navigation and 3D- Modeling 448
16.1.1 Reconstruction of Arbitrary Shapes Using the Locus Method 448
16.1.2 Using the locus Method for Cavity Inspection 452
16.1.3 Stereo Reconstruction Using Remote Sensing Images 456
16.1.4 Stereo Reconstruction for Space Research 459
16.1.5 Operational Industrial Stereo Vision Systems 459
16.2 A Framework for Vision-Based Navigation 461
16.2.1 Vision Sensor Systems 462
16.2.2 Closed-Loop Solution for Autonomous Navigation 463
16.2.3 Risk Map Generation 464
16.2.4 Local Path Planning 464
16.2.5 Path Execution and Navigation on the DEM 465
16.2.6 Prototype Software for Closed-Loop Vehicle Navigation 467
16.2.7 Simulation Results 468
17 3D Object Sensing Using Rotating CCD Cameras 474
17.1 Concept of Image-Based Theodolite Measurement Systems 474
17.2 The Videometric Imaging System 476
17.2.1 The Purpose of the Videometric Imaging System 476
17.2.2 An Interactive Measurement System–A First Step 479
17.2.3 An Automatic System–A Second Step 482
17.3 Conversion of the Measurement System into a Robot System 490
17.4 Decision Making 491
17.5 Outlook 495
References 497
Index 507

2 Stochastic Shape Theory (P. 49)

Christian Cenker

Georg Pflug

Manfred Mayer

Stochastic models and statistical procedures are essential for pattern recognition. Linear discriminant analysis, parametric and nonparametric density estimation, maximumlikelihood classiffication, supervised and nonsupervised learning, neural nets, parametric, nonparametric, and fuzzy clustering, principal component analysis, simulated annealing are only some of the well-known statistical techniques used for pattern recognition. Markov models and other stochastic models are often used to describe statistical characteristics of patterns in the pattern space.

We want to concentrate on modeling and feature extraction using new techniques.We do not model the characteristics of the pattern space but the generation of the patterns, i.e., modeling the pattern generation process via stochastic processes. Furthermore, wavelets and wavelet packets will help us to construct a feature extractor. Applying our models to a sample application we noticed the lack of global non-linear optimization algorithms. Thus, we added a section on optimization, in which we present a modiffi- cation of a multi-level single-linkage technique that can be used in high-dimensional feature spaces.

2.1 Shape Analysis

A project on o.ine signature verification shows the need for new approaches. Standard methods do not show the wanted accuracy, nevertheless, they have been implemented at a first stage in order to compare the results. As all signatures of one person are of di.erent but similar shape we look for a description of the similarity and the difference. First, a signature is a special form of curve, we discard all color, thickness and "pressure" information from the scanned signature (cf. (AYF86)), leaving only a thinned polygonal shape. We have a connected skeleton of the "contour".

The first problem to solve is the parameterization of the curve, i.e., to get a onedimensional function that represents the two-dimensional signature, as our constraints are on the one hand to use as little data for storage of the signatures as possible and, on the other hand, to develop fast algorithms. Thus, using only one-dimensional objects (functions) seem to be a feasible solution. We choose a change-in-angle parameterization of the curve, which has the advantages of shift, rotation and scale invariance (cf. (Nie90)).

Features are then extracted forming a sampled version of the contour, stored in a k-dimensional vector, and used for discrimination and classiffication. Based on the change-in-angle parameterization we present three different approaches to match the patterns. Starting with the description of classes of signatures and their similarity by stochastic processes, i.e., stochastic deformation processes, describe the generation process of the signatures of an individual (see Section 2.3).

Secondly, we want to use new "standard" signal analysis methods to analyze the curve or polygonal shape, i.e., wavelet and frame methods, as they provide fast algorithms that produce patterns that have a nice easy interpretation (see Section 2.5).