Shape analysis and classification : theory and practice

Advances in shape analysis impact a wide range of disciplines, from mathematics and engineering to medicine, archeology, and art. Anyone just entering the field, however, may find the few existing books on shape analysis too specific or advanced, and for students interested in the specific problem of shape recognition and characterization, traditional books on computer vision are too general.

Shape Analysis and Classification: Theory and Practice offers an integrated and conceptual introduction to this dynamic field and its myriad applications. Beginning with the basic mathematical concepts, it deals with shape analysis, from image capture to pattern classification, and presents many of the most advanced and powerful techniques used in practice. The authors explore the relevant aspects of both shape characterization and recognition, and give special attention to practical issues, such as guidelines for implementation, validation, and assessment.

Shape Analysis and Classification provides a rich resource for the computational characterization and classification of general shapes, from characters to biological entities. Both students and researchers can directly use its state-of-the-art concepts and techniques to solve their own problems involving the characterization and classification of visual shapes.

1 Introduction	p. 1
1.1 Introduction to Shape Analysis	p. 1
1.2 Case Studies	p. 5
1.2.1 Case Study: Morphology of Plant Leaves	p. 5
1.2.2 Case Study: Morphometric Classification of Ganglion Cells	p. 7
1.3 Computational Shape Analysis	p. 9
1.3.1 Shape Pre-Processing	p. 9
1.3.2 Shape Transformations	p. 14
1.3.3 Shape Classification	p. 21
1.4 Organization of the Book	p. 24
2 Basic Mathematical Concepts	p. 27
2.1 Basic Concepts	p. 27
2.1.1 Propositional Logic	p. 28
2.1.2 Functions	p. 29
2.1.3 Free Variable Transformations	p. 31
2.1.4 Some Special Real Functions	p. 33
2.1.5 Complex Functions	p. 44
2.2 Linear Algebra	p. 51
2.2.1 Scalars, Vectors and Matrices	p. 52
2.2.2 Vector Spaces	p. 56
2.2.3 Linear Transformations	p. 62
2.2.4 Metric Spaces, Inner Products and Orthogonality	p. 65
2.2.5 More about Vectors and Matrices	p. 70
2.3 Differential Geometry	p. 90
2.3.1 2D Parametric Curves	p. 90
2.3.2 Arc Length, Speed and Tangent Fields	p. 94
2.3.3 Normal Fields and Curvature	p. 97
2.4 Multivariate Calculus	p. 101
2.4.1 Multivariate Functions	p. 101
2.4.2 Directional, Partial and Total Derivatives	p. 107
2.4.3 Differential Operators	p. 109
2.5 Convolution and Correlation	p. 110
2.5.1 Continuous Convolution and Correlation	p. 111
2.5.2 Discrete Convolution and Correlation	p. 117
2.5.3 Nonlinear Correlation as a Coincidence Operator	p. 120
2.6 Probability and Statistics	p. 122
2.6.1 Events and Probability	p. 122
2.6.2 Random Variables and Probability Distributions	p. 125
2.6.3 Random Vectors and Joint Distributions	p. 131
2.6.4 Estimation	p. 135
2.6.5 Stochastic Processes and Autocorrelation	p. 144
2.6.6 The Karhunen-Loeve Transform	p. 146
2.7 Fourier Analysis	p. 149
2.7.1 Brief Historical Remarks	p. 150
2.7.2 The Fourier Series	p. 151
2.7.3 The Continuous One-Dimensional Fourier Transform	p. 157
2.7.4 Frequency Filtering	p. 170
2.7.5 The Discrete One-Dimensional Fourier Transform	p. 176
2.7.6 Matrix Formulation of the DFT	p. 180
2.7.7 Applying the DFT	p. 184
2.7.8 The Fast Fourier Transform	p. 194
2.7.9 Discrete Convolution Performed in the Frequency Domain	p. 195
3 Shape Acquisition and Processing	p. 197
3.1 Image Representation	p. 198
3.1.1 Image Formation and Gray Level Images	p. 198
3.1.2 Case Study: Image Sampling	p. 201
3.1.3 Binary Images	p. 203
3.1.4 Shape Sampling	p. 206
3.1.5 Some Useful Concepts from Discrete Geometry	p. 208
3.1.6 Color Digital Images	p. 210
3.1.7 Video Sequences	p. 213
3.1.8 Multispectral Images	p. 215
3.1.9 Voxels	p. 216
3.2 Image Processing and Filtering	p. 216
3.2.1 Histograms and Pixel Manipulation	p. 218
3.2.2 Local or Neighborhood Processing	p. 223
3.2.3 Average Filtering	p. 224
3.2.4 Gaussian Smoothing	p. 226
3.2.5 Fourier-Based Filtering	p. 228
3.2.6 Median and Other Nonlinear Filters	p. 234
3.3 Image Segmentation: Edge Detection	p. 235
3.3.1 Edge Detection in Binary Images	p. 237
3.3.2 Gray-Level Edge Detection	p. 237
3.3.3 Gradient-Based Edge Detection	p. 239
3.3.4 Roberts Operator	p. 240
3.3.5 Sobel, Prewitt and Kirsch Operators	p. 242
3.3.6 Fourier-Based Edge Detection	p. 243
3.3.7 Second-Order Operators: Laplacian	p. 244
3.3.8 Multiscale Edge Detection: The Marr-Hildreth Transform	p. 245
3.4 Image Segmentation: Additional Algorithms	p. 248
3.4.1 Image Thresholding	p. 248
3.4.2 Region-Growing	p. 251
3.5 Binary Mathematical Morphology	p. 255
3.5.1 Image Dilation	p. 255
3.5.2 Image Erosion	p. 259
3.6 Further Image Processing References	p. 262
4 Shape Concepts	p. 265
4.1 Introduction to Two-Dimensional Shapes	p. 265
4.2 Continuous Two-Dimensional Shapes	p. 267
4.2.1 Continuous Shapes and their Types	p. 268
4.3 Planar Shape Transformations	p. 273
4.4 Characterizing 2D Shapes In Terms of Features	p. 275
4.5 Classifying 2D Shapes	p. 280
4.6 Representing 2D Shapes	p. 281
4.6.1 General Shape Representations	p. 283
4.6.2 Landmark Representations	p. 286
4.7 Shape Operations	p. 289
4.8 Shape Metrics	p. 290
4.8.1 The 2n Euclidean Norm	p. 291
4.8.2 The Mean Size	p. 295
4.8.3 Alternative Shape Sizes	p. 295
4.8.4 Which Size?	p. 296
4.8.5 Distances between Shapes	p. 298
4.9 Morphic Transformations	p. 301
4.9.1 Affine Transformations	p. 308
4.9.2 Euclidean Motions	p. 314
4.9.3 Rigid Body Transformations	p. 315
4.9.4 Similarity Transformations	p. 315
4.9.5 Other Transformations and Some Important Remarks	p. 316
4.9.6 Thin-Plate Splines	p. 317
5 Two-Dimensional Shape Representation	p. 331
5.1 Introduction	p. 331
5.2 Parametric Contour	p. 335
5.2.1 Contour Extraction	p. 335
5.2.2 A Contour Following Algorithm	p. 341
5.2.3 Contour Representation by Vectors and Complex Signals	p. 348
5.2.4 Contour Representation Based on the Chain Code	p. 350
5.3 Sets of Contour Points	p. 351
5.4 Curve Approximations	p. 352
5.4.1 Polygonal Approximation	p. 352
5.4.2 Ramer Algorithm for Polygonal Approximation	p. 354
5.4.3 Split-and-Merge Algorithm for Polygonal Approximation	p. 360
5.5 Digital Straight Lines	p. 365
5.5.1 Straight Lines and Segments	p. 366
5.5.2 Generating Digital Straight Lines and Segments	p. 367
5.5.3 Recognizing an Isolated Digital Straight Segment	p. 374
5.6 Hough Transforms	p. 376
5.6.1 Continuous Hough Transforms	p. 376
5.6.2 Discrete Image and Continuous Parameter Space	p. 378
5.6.3 Discrete Image and Parameter Space	p. 382
5.6.4 Backmapping	p. 389
5.6.5 Problems with the Hough Transform	p. 391
5.6.6 Improving the Hough Transform	p. 393
5.6.7 General Remarks on the Hough Transform	p. 400
5.7 Exact Dilations	p. 400
5.8 Distance Transforms	p. 405
5.9 Exact Distance Transform Through Exact Dilations	p. 407
5.10 Voronoi Tessellations	p. 408
5.11 Scale-Space Skeletonization	p. 412
5.12 Bounding Regions	p. 419
6 Shape Characterization	p. 421
6.1 Statistics for Shape Descriptors	p. 421
6.2 Some General Descriptors	p. 422
6.2.1 Perimeter	p. 423
6.2.2 Area	p. 424
6.2.3 Centroid (Center of Mass)	p. 425
6.2.4 Maximum and Minimum Distance to Centroid	p. 426
6.2.5 Mean Distance to the Boundary	p. 427
6.2.6 Diameter	p. 427
6.2.7 Norm Features	p. 429
6.2.8 Maximum Arc Length	p. 429
6.2.9 Major and Minor Axes	p. 429
6.2.10 Thickness	p. 432
6.2.11 Hole-Based Shape Features	p. 432
6.2.12 Statistical Moments	p. 433
6.2.13 Symmetry	p. 434
6.2.14 Shape Signatures	p. 435
6.2.15 Topological Descriptors	p. 438
6.2.16 Polygonal Approximation-Based Shape Descriptors	p. 438
6.2.17 Shape Descriptors based on Regions and Graphs	p. 439
6.2.18 Simple Complexity Descriptors	p. 439
6.3 Fractal Geometry and Complexity Descriptors	p. 442
6.3.1 Preliminary Considerations and Definitions	p. 442
6.3.2 The Box-Counting Approach	p. 443
6.3.3 Case Study: The Classical Koch Curve	p. 443
6.3.4 Implementing the Box-Counting Method	p. 445
6.3.5 The Minkowsky Sausage or Dilation Method	p. 447
6.4 Curvature	p. 449
6.4.1 Biological Motivation	p. 449
6.4.2 Simple Approaches to Curvature	p. 451
6.4.3 c-Measure	p. 456
6.4.4 Curvature-Based Shape Descriptors	p. 457
6.5 Fourier Descriptors	p. 459
6.5.1 Some Useful Properties	p. 461
6.5.2 Alternative Fourier Descriptors	p. 464
7 Multiscale Shape Characterization	p. 467
7.1 Multiscale Transforms	p. 467
7.1.1 Scale-Space	p. 468
7.1.2 Time-Frequency Transforms	p. 471
7.1.3 Gabor Filters	p. 472
7.1.4 Time-Scale Transforms or Wavelets	p. 473
7.1.5 Interpreting the Transforms	p. 476
7.1.6 Analyzing Multiscale Transforms	p. 480
7.2 Fourier-Based Multiscale Curvature	p. 484
7.2.1 Fourier-Based Curvature Estimation	p. 484
7.2.2 Numerical Differentiation Using the Fourier Property	p. 487
7.2.3 Gaussian Filtering and the Multiscale Approach	p. 490
7.2.4 Some Simple Solutions for the Shrinking Problem	p. 491
7.2.5 The Curvegram	p. 494
7.2.6 Curvature-Scale Space	p. 500
7.3 Wavelet-Based Multiscale Contour Analysis	p. 502
7.3.1 Preliminary Considerations	p. 502
7.3.2 The w-Representation	p. 504
7.3.3 Choosing the Analyzing Wavelet	p. 506
7.3.4 Shape Analysis from the w-Representation	p. 508
7.3.5 Dominant Point Detection Using the w-Representation	p. 509
7.3.6 Local Frequencies and Natural Scales	p. 515
7.3.7 Contour Analysis using the Gabor Transform	p. 518
7.3.8 Comparing and Integrating Multiscale Representations	p. 520
7.4 Multiscale Energies	p. 524
7.4.1 The Multiscale Bending Energy	p. 524
7.4.2 Bending Energy-Based Neuromorphometry	p. 527
7.4.3 The Multiscale Wavelet Energy	p. 530
8 Shape Recognition and Classification	p. 533
8.1 Introduction to Shape Classification	p. 533
8.1.1 The Importance of Classification	p. 534
8.1.2 Some Basic Concepts in Classification	p. 536
8.1.3 A Simple Case Study in Classification	p. 538
8.1.4 Some Additional Concepts in Classification	p. 545
8.1.5 Feature Extraction	p. 550
8.1.6 Feature Normalization	p. 556
8.2 Supervised Pattern Classification	p. 565
8.2.1 Bayes Decision Theory Principles	p. 565
8.2.2 Bayesian Classification: Multiple Classes and Dimensions	p. 571
8.2.3 Bayesian Classification of Leaves	p. 574
8.2.4 Nearest Neighbors	p. 574
8.3 Unsupervised Classification and Clustering	p. 577
8.3.1 Basic Concepts and Issues	p. 577
8.3.2 Scatter Matrices and Dispersion Measures	p. 580
8.3.3 Partitional Clustering	p. 583
8.3.4 Hierarchical Clustering	p. 589
8.4 A Case Study: Leaves Classification	p. 600
8.4.1 Choice of Method	p. 602
8.4.2 Choice of Metrics	p. 603
8.4.3 Choice of Features	p. 604
8.4.4 Validation Considering the Cophenetic Correlation Coefficient	p. 607
8.5 Evaluating Classification Methods	p. 608
8.5.1 Case Study: Classification of Ganglion Cells	p. 609
8.5.2 The Feature Space	p. 610
8.5.3 Feature Selection and Dimensionality Reduction	p. 612
9 Epilogue - Future Trends in Shape Analysis and Classification	p. 617
Bibliography	p. 621
Index	p. 649

Available:*

On Order

Summary

Summary

Table of Contents