Shape Analysis and Classification: Theory and Practice (Image Processing Series)

3493_pdf_toc.pdf......Page 1
Shape Analysis and Classification......Page 3
PREFACE......Page 6
TABLE OF CONTENTS......Page 10
1.1 INTRODUCTION TO SHAPE ANALYSIS......Page 19
Table of Contents......Page 0
1.2.1 Case Study: Morphology of Plant Leaves......Page 23
1.2.2 Case Study: Morphometric Classification of Ganglion Cells......Page 25
1.3.1 Shape Pre-Processing......Page 27
1.3.1.1 Shape Acquisition......Page 28
1.3.1.2 Shape Detection......Page 29
1.3.1.4 Shape Operations......Page 30
1.3.2.2 Shape Representation......Page 32
1.3.2.3 Shape Description or Characterization......Page 34
1.3.2.5 Shape Compression......Page 38
1.3.3.1 Unsupervised Shape Classification......Page 39
1.3.3.2 Supervised Shape Classification......Page 40
1.3.3.4 Shape Matching......Page 41
1.4 ORGANIZATION OF THE BOOK......Page 42
2.1 BASIC CONCEPTS......Page 44
2.1.1 Propositional Logic......Page 45
2.1.2 Functions......Page 46
2.1.3 Free Variable Transformations......Page 48
2.1.4 Some Special Real Functions......Page 50
2.1.5 Complex Functions......Page 61
2.1.5.1 Complex Numbers......Page 62
2.1.5.2 Complex Functions and Their Graphical Representation......Page 63
2.1.5.3 Analytical Functions and Conformal Mappings......Page 67
2.2 LINEAR ALGEBRA......Page 68
2.2.1 Scalars, Vectors and Matrices......Page 69
2.2.2 Vector Spaces......Page 73
2.2.3 Linear Transformations......Page 79
2.2.4 Metric Spaces, Inner Products and Orthogonality......Page 82
2.2.5.1 Some Basic Concepts......Page 87
2.2.5.2 Some Important Properties......Page 89
2.2.5.3 Determinants......Page 90
2.2.5.4 Orthogonality and Rotations......Page 91
2.2.5.5 Vector Product......Page 93
2.2.5.6 Rank and Echelon Form of Matrices......Page 94
2.2.5.8 Inverse and Pseudoinverse of a Matrix......Page 96
2.2.5.9 Eigenvalues and Eigenvectors......Page 101
2.2.5.10 Tricks with Matrices......Page 103
2.3.1 2D Parametric Curves......Page 107
2.3.2 Arc Length, Speed and Tangent Fields......Page 111
2.3.3 Normal Fields and Curvature......Page 114
2.4.1 Multivariate Functions......Page 118
2.4.2 Directional, Partial and Total Derivatives......Page 124
2.4.3 Differential Operators......Page 126
2.5 CONVOLUTION AND CORRELATION......Page 127
2.5.1 Continuous Convolution and Correlation......Page 128
2.5.2 Discrete Convolution and Correlation......Page 134
2.5.3 Nonlinear Correlation as a Coincidence Operator......Page 137
2.6.1 Events and Probability......Page 139
2.6.2.1 Random Variables......Page 142
2.6.2.2 Density Functions......Page 143
2.6.2.3 Statistical Moments......Page 144
2.6.2.4 Some Density Functions......Page 145
2.6.2.5 Random Variables Transformations, Conditional Density Functions and Discrete Random Variables......Page 146
2.6.3 Random Vectors and Joint Distributions......Page 148
2.6.4 Estimation......Page 152
2.6.4.1 Non-Parametric Estimation and Parzen Windows......Page 153
2.6.4.2 Parametric Estimation......Page 156
2.6.5 Stochastic Processes and Autocorrelation......Page 161
2.6.6 The Karhunen-Loève Transform r......Page 163
2.7 FOURIER ANALYSIS......Page 166
2.7.1 Brief Historical Remarks......Page 167
2.7.2 The Fourier Series......Page 168
2.7.3 The Continuous One-Dimensional Fourier Transform......Page 174
2.7.3.2 Time Shifting......Page 179
2.7.3.3 Time Scaling......Page 180
2.7.3.6 Linearity......Page 182
2.7.3.9 The Derivative Property......Page 183
2.7.3.11 Parity-Related Properties......Page 184
2.7.3.12 Discrete and Periodical Functions......Page 185
2.7.4 Frequency Filtering......Page 187
2.7.5 The Discrete One-Dimensional Fourier Transform......Page 193
2.7.6 Matrix Formulation of the DFT......Page 197
2.7.7 Applying the DFT......Page 201
2.7.8 The Fast Fourier Transform......Page 211
2.7.9 Discrete Convolution Performed in the Frequency Domain......Page 212
CHAPTER 3: SHAPE ACQUISITION AND PROCESSING......Page 214
3.1.1 Image Formation and Gray Level Images......Page 215
Definition: Gray-Level Digital Images......Page 216
3.1.2 Case Study: Image Sampling......Page 218
3.1.3 Binary Images......Page 220
3.1.4 Shape Sampling......Page 223
3.1.5 Some Useful Concepts from Discrete Geometry......Page 225
3.1.6 Color Digital Images......Page 227
3.1.7 Video Sequences......Page 230
3.1.8 Multispectral Images......Page 232
3.2 IMAGE PROCESSING AND FILTERING......Page 233
3.2.1 Histograms and Pixel Manipulation......Page 235
3.2.2 Local or Neighborhood Processing......Page 240
3.2.3 Average Filtering......Page 241
3.2.4 Gaussian Smoothing......Page 243
3.2.5 Fourier-Based Filtering......Page 245
3.2.6 Median and Other Nonlinear Filters......Page 251
3.3 IMAGE SEGMENTATION: EDGE DETECTION......Page 252
3.3.2 Gray-Level Edge Detection......Page 254
3.3.3 Gradient-Based Edge Detection......Page 256
3.3.4 Roberts Operator......Page 257
3.3.5 Sobel, Prewitt and Kirsch Operators......Page 259
3.3.6 Fourier-Based Edge Detection......Page 260
3.3.7 Second-Order Operators: Laplacian......Page 261
3.3.8 Multiscale Edge Detection: The Marr-Hildreth Transform......Page 262
3.4.1 Image Thresholding......Page 265
3.4.2 Region-Growing......Page 268
3.5.1 Image Dilation......Page 272
3.5.2 Image Erosion......Page 276
3.6 FURTHER IMAGE PROCESSING REFERENCES......Page 279
4.1 INTRODUCTION TO TWO-DIMENSIONAL SHAPES......Page 281
4.2 CONTINUOUS TWO-DIMENSIONAL SHAPES......Page 283
4.2.1 Continuous Shapes and their Types......Page 284
4.3 PLANAR SHAPE TRANSFORMATIONS......Page 289
4.4 CHARACTERIZING 2D SHAPES IN TERMS OF FEATURES......Page 291
4.5 CLASSIFYING 2D SHAPES......Page 296
4.6 REPRESENTING 2D SHAPES......Page 297
4.6.1 General Shape Representations......Page 299
4.6.2 Landmark Representations......Page 302
4.7 SHAPE OPERATIONS......Page 305
4.8 SHAPE METRICS......Page 306
4.8.1 The 2n Euclidean Norm......Page 307
4.8.3 Alternative Shape Sizes......Page 311
4.8.4 Which Size?......Page 312
4.8.5 Distances between Shapes......Page 314
4.9 MORPHIC TRANSFORMATIONS......Page 317
4.9.1 Affine Transformations......Page 324
4.9.2 Euclidean Motions......Page 330
4.9.4 Similarity Transformations......Page 331
4.9.5 Other Transformations and Some Important Remarks......Page 332
4.9.6 Thin-Plate Splines......Page 333
4.9.6.1 Single Thin-Plate Splines......Page 334
4.9.6.2 Pairs of Thin-Plate Splines......Page 341
5.1 INTRODUCTION......Page 347
5.2.1 Contour Extraction......Page 351
5.2.2 A Contour Following Algorithm......Page 357
5.2.3 Contour Representation by Vectors and Complex Signals......Page 364
5.2.4 Contour Representation Based on the Chain Code......Page 366
5.3 SETS OF CONTOUR POINTS......Page 367
5.4.1 Polygonal Approximation......Page 368
5.4.2 Ramer Algorithm for Polygonal Approximation......Page 370
5.4.3 Split-and-Merge Algorithm for Polygonal Approximation......Page 376
5.4.3.2 The Merge Step......Page 378
5.4.3.3 Controlling the Split and the Merge Procedures......Page 380
5.5 DIGITAL STRAIGHT LINES......Page 381
5.5.1 Straight Lines and Segments......Page 382
5.5.2 Generating Digital Straight Lines and Segments......Page 383
5.5.3 Recognizing an Isolated Digital Straight Segment......Page 390
5.6.1 Continuous Hough Transforms......Page 392
5.6.2 Discrete Image and Continuous Parameter Space......Page 394
5.6.3 Discrete Image and Parameter Space......Page 398
5.6.4 Backmapping......Page 405
5.6.5 Problems with the Hough Transform......Page 407
5.6.6.1 Connectivity Analysis......Page 409
5.6.6.2 Dilated Straight Bands, Progressive Elimination and DSLS Merging......Page 413
5.7 EXACT DILATIONS......Page 416
5.8 DISTANCE TRANSFORMS......Page 421
5.9 EXACT DISTANCE TRANSFORM THROUGH EXACT DILATIONS......Page 423
5.10 VORONOI TESSELLATIONS......Page 424
5.11 SCALE-SPACE SKELETONIZATION......Page 428
5.12 BOUNDING REGIONS......Page 435
6.1 STATISTICS FOR SHAPE DESCRIPTORS......Page 437
6.2 SOME GENERAL DESCRIPTORS......Page 438
6.2.1 Perimeter......Page 439
6.2.2 Area......Page 440
6.2.3 Centroid (Center of Mass)......Page 441
6.2.4 Maximum and Minimum Distance to Centroid......Page 442
6.2.6 Diameter......Page 443
6.2.9 Major and Minor Axes......Page 445
6.2.11 Hole-Based Shape Features......Page 448
6.2.12 Statistical Moments......Page 449
6.2.13 Symmetry......Page 450
6.2.14 Shape Signatures......Page 451
6.2.16 Polygonal Approximation-Based Shape Descriptors......Page 454
6.2.18 Simple Complexity Descriptors......Page 455
6.3.1 Preliminary Considerations and Definitions......Page 458
6.3.3 Case Study: The Classical Koch Curve......Page 459
6.3.4 Implementing the Box-Counting Method......Page 461
6.3.5 The Minkowsky Sausage or Dilation Method......Page 463
6.4.1 Biological Motivation......Page 465
6.4.2 Simple Approaches to Curvature......Page 467
Case I: Definition of alternative curvature measures based on angles between vectors......Page 468
Case II: Interpolation of x(t) and y(t) followed by differentiation......Page 470
6.4.3 c-Measure......Page 472
6.4.4 Curvature-Based Shape Descriptors......Page 473
6.5 FOURIER DESCRIPTORS......Page 475
6.5.1 Some Useful Properties......Page 477
6.5.2 Alternative Fourier Descriptors......Page 480
7.1 MULTISCALE TRANSFORMS......Page 483
7.1.1 Scale-Space......Page 484
7.1.2 Time-Frequency Transforms......Page 487
7.1.3 Gabor Filters......Page 488
7.1.4 Time-Scale Transforms or Wavelets......Page 489
7.1.5 Interpreting the Transforms......Page 492
7.1.6 Analyzing Multiscale Transforms......Page 496
7.2.1 Fourier-Based Curvature Estimation......Page 500
7.2.2 Numerical Differentiation Using the Fourier Property......Page 503
7.2.3 Gaussian Filtering and the Multiscale Approach......Page 506
7.2.4.1 Shrinking Prevention through Energy Conservation......Page 507
7.2.4.2 Shrinking Prevention through Perimeter Conservation......Page 508
7.2.5 The Curvegram......Page 510
7.2.6 Curvature-Scale Space......Page 516
7.3.1 Preliminary Considerations......Page 518
7.3.2 The w-Representation......Page 520
7.3.3.1 Gaussian Derivatives......Page 522
7.3.3.2 The Morlet Wavelet......Page 523
7.3.4 Shape Analysis from the w-Representation......Page 524
7.3.5 Dominant Point Detection Using the w-Representation......Page 525
7.3.6 Local Frequencies and Natural Scales......Page 531
7.3.7 Contour Analysis using the Gabor Transform......Page 534
7.3.8 Comparing and Integrating Multiscale Representations......Page 536
7.4.1 The Multiscale Bending Energy......Page 540
7.4.2 Bending Energy-Based Neuromorphometry......Page 543
7.4.3 The Multiscale Wavelet Energy......Page 546
8.1 INTRODUCTION TO SHAPE CLASSIFICATION......Page 549
8.1.1 The Importance of Classification......Page 550
8.1.2 Some Basic Concepts in Classification......Page 552
8.1.3 A Simple Case Study in Classification......Page 554
8.1.4 Some Additional Concepts in Classification......Page 561
8.1.5.1 Feature Organization and Visualization......Page 566
8.1.5.2 Feature Selection......Page 568
8.1.6.1 Normal Transformation of Features......Page 572
8.1.6.2 Principal Component Analysis......Page 576
8.2.1 Bayes Decision Theory Principles......Page 581
8.2.2 Bayesian Classification: Multiple Classes and Dimensions......Page 587
8.2.4 Nearest Neighbors......Page 590
8.3.1 Basic Concepts and Issues......Page 593
8.3.2 Scatter Matrices and Dispersion Measures......Page 596
8.3.3 Partitional Clustering......Page 599
8.3.4 Hierarchical Clustering......Page 605
8.3.4.1 Distances between Sets......Page 607
8.3.4.2 Distance-Based Hierarchical Clustering......Page 609
8.3.4.3 Dispersion Based Hierarchical Clustering – Ward’s Method......Page 611
8.3.4.5 Cophenetic Correlation Coefficient......Page 612
8.3.4.7 Determining the Relevance and Number of Clusters......Page 614
8.3.4.8 A Brief Comparison of Methods......Page 615
8.4 A CASE STUDY: LEAVES CLASSIFICATION......Page 616
8.4.1 Choice of Method......Page 618
8.4.2 Choice of Metrics......Page 619
8.4.3 Choice of Features......Page 620
8.4.4 Validation Considering the Cophenetic Correlation Coefficient......Page 623
8.5 EVALUATING CLASSIFICATION METHODS......Page 624
8.5.1 Case Study: Classification of Ganglion Cells......Page 625
8.5.2 The Feature Space......Page 626
8.5.3 Feature Selection and Dimensionality Reduction......Page 628
CHAPTER 9: EPILOGUE - FUTURE TRENDS IN SHAPE ANALYSIS AND CLASSIFICATION......Page 632
BIBLIOGRAPHY......Page 636