Digital Pattern Recognition

Since its publication in 1976, the original volume has been warmly received. We have decided to put out this updated paperback edition so that the book can be more accessible to students. This paperback edition is essentially the same as the original hardcover volume except for the addition of a new chapter (Chapter 7) which reviews the recent advances in pattern recognition and image processing. Because of the limitations of length, we can only report the highlights and point the readers to the literature. A few typographical errors in the original edition were corrected. We are grateful to the National Science Foundation and the Office of Naval Research for supporting the editing of this book as well as the work described in Chapter 4 and a part of Chapter 7. West Lafayette, Indiana March 1980 K. S. Fu Preface to the First Edition During the past fifteen years there has been a considerable growth of interest in problems of pattern recognition. Contributions to the blossom of this area have come from many disciplines, including statistics, psychology, linguistics, computer science, biology, taxonomy, switching theory, communication theory, control theory, and operations research. Many different approaches have been proposed and a number of books have been published. Most books published so far deal with the decision-theoretic (or statistical) approach or the syntactic (or linguistic) is still far from its maturity, many approach.

1. Introduction.- 1.1 What is Pattern Recognition?.- 1.2 Approaches to Pattern Recognition.- 1.3 Basic Non-Parametric Decision ― Theoretic Classification Methods.- 1.3.1 Linear Discriminant Functions.- 1.3.2 Minimum Distance Classifier.- 1.3.3 Piecewise Linear Discriminant Functions (Nearest Neighbor Classification).- 1.3.4 Polynomial Discriminant Functions.- 1.4 Training in Linear Classifiers.- 1.5 Bayes (Parametric) Classification.- 1.6 Sequential Decision Model for Pattern Classification.- 1.7 Bibliographical Remarks.- References.- 2. Topics in Statistical Pattern Recognition.- 2.1 Nonparametric Discrimination.- 2.1.1 Introduction.- 2.1.2 The Deterministic Problem.- 2.1.3 The Bayesian Problem.- 2.1.4 Probability of Error Estimation.- 2.1.5 Density Estimation.- 2.2 Learning with Finite Memory.- 2.2.1 Time-Varying Finite Memory.- 2.2.2 Time-Invariant Finite Memory.- 2.3 Two-Dimensional Patterns and Their Complexity.- 2.3.1 Pattern Complexity.- Kolmogorov Complexity.- 2.3.2 Inference of Classification Functions.- References.- 3. Clustering Analysis.- 3.1 Introduction.- 3.1.1 Relations between Clustering and Pattern Recognition.- Definition of Classification and Identification.- A Definition of Clustering.- 3.1.2 A General Model of Clustering.- 3.2 The Initial Description.- 3.2.1 Interpretation of the Initial Structured Data.- 3.2.2 Resemblance and Dissemblance Measures.- Definition of a Similarity Measure and of a Dissimilarity Measure.- Quantitative Dissemblance Measures.- Qualitative Resemblance Measure.- Qualitative Ordinal Coding.- Binary Distance Measures.- Resemblance Measures between Elementary Variables.- Resemblance Measures between Groups of Objects.- 3.3 Properties of a Cluster, a Clustering Operator and a Clustering Process.- 3.3.1 Properties of Clusters and Partitions.- Homogeneity.- Stability of a Cluster or of a Partition.- 3.3.2 Properties of a Clustering Identification Operator S or of a Clustering Process.- ? Admissibility.- ? Admissibility.- 3.4 The Main Clustering Algorithms.- 3.4.1 Hierarchies.- Definition of a Hierarchy.- Definition and Properties of an Ultrametric.- 3.4.2 Construction of a Hierarchy.- Roux Algorithm.- Lance and William General Algorithm.- Single Linkage.- Complete Linkage.- Average Linkage.- Centroid Method.- Ward Technique.- The Chain Effect.- 3.4.3 The Minimum Spanning Tree.- Prim Algorithm.- Kruskal Algorithm.- 3.4.4 Identification from a Hierarchy or a Minimum Spanning Tree.- 3.4.5 A Partition and the Corresponding Symbolic Representations.- Algorithm ?.- Algorithm ?.- 3.4.6 Optimization of a Criterion.- 3.4.7 Cross-Partitions.- Definition of the Strong Patterns.- Fuzzy Sets.- Presentation of the Table of the “Strong Patterns”.- 3.5 The Dynamic Clusters Method.- 3.5.1 An Example of h, g, ? in Hierarchies.- 3.5.2 Construction of h, g, ? in Partitioning.- 3.5.3 The Dynamic Clusters Algorithm.- 3.5.4 The Symbolic Description is a Part of X or ?n.- Non-Sequential Techniques.- Sequential Techniques.- 3.5.5 Partitions and Mixed Distributions.- The Dynamic Cluster Approach.- Gaussian Distributions.- 3.5.6 Partitions and Factor Analysis.- The Dynamic Clusters Algorithm.- An Experiment: Find Features on Letters.- 3.6 Adaptive Distances in Clustering.- 3.6.1 Descriptions and Results of the Adaptive Distance Dynamic Cluster Method.- The Criterion.- The Method.- The Identification Function ?: Lk??k.- The Symbolic Description Function g: ?k?Lk.- Convergence Properties.- 3.6.2 A Generalization of the Adaptive Distance Algorithm.- The Criterion.- The Algorithm.- Convergence of the Algorithm.- 3.7 Conclusion and Future Prospects.- References.- 4. Syntactic (Linguistic) Pattern Recognition..- 4.1 Syntactic (Structural) Approach to Pattern Recognition.- 4.2 Linguistic Pattern Recognition System.- 4.3 Selection of Pattern Primitives.- 4.3.1 Primitive Selection Emphasizing Boundaries or Skeletons.- 4.3.2 Pattern Primitives in Terms of Regions.- 4.4 Pattern Grammar.- 4.5 High-Dimensional Pattern Grammars.- 4.5.1 General Discussion.- 4.5.2 Special Grammars.- 4.6 Syntax Analysis as Recognition Procedure.- 4.6.1 Recognition of Finite-State Languages.- 4.6.2 Syntax Analysis of Context-Free Languages.- 4.7 Concluding Remarks.- References.- 5. Picture Recognition.- 5.1 Introduction.- 5.2 Properties of Regions.- 5.2.1 Analysis of the Power Spectrum.- 5.2.2 Analysis of Local Property Statistics.- 5.2.3 Analysis of Joint Gray Level Statistics.- 5.2.4 Grayscale Normalization.- 5.3 Detection of Objects.- 5.3.1 Template Matching.- 5.3.2 Edge Detection.- 5.4 Properties of Detected Objects.- 5.4.1 Moments.- 5.4.2 Projections and Cross-Sections.- 5.4.3 Geometrical Normalization.- 5.5 Object Extraction.- 5.5.1 Thresholding.- 5.5.2 Region Growing.- 5.5.3 Tracking.- 5.6 Properties of Extracted Objects.- 5.6.1 Connectedness.- 5.6.2 Size, Compactness, and Convexity.- 5.6.3 Arcs, Curves, and Elongatedness.- 5.7 Representation of Objects and Pictures.- 5.7.1 Borders.- 5.7.2 Skeletons.- 5.7.3 Relational Structures.- References.- 6. Speech Recognition and Understanding..- 6.1 Principles of Speech, Recognition, and Understanding.- 6.1.1 Introduction.- 6.1.2 The Nature of Speech Communication.- 6.1.3 Approaches to Automatic Recognition.- 6.2 Recent Developments in Automatic Speech Recognition.- 6.2.1 Introduction.- 6.2.2 Isolated Word Recognition.- 6.2.3 Continuous Speech Recognition.- 6.3 Speech Understanding.- 6.3.1 Introduction.- 6.3.2 Relevant Sources of Knowledge.- 6.3.3 Present Speech Understanding Systems.- 6.4 Assessment of the Future.- References.- 7. Recent Developments in Digital Pattern Recognition..- 7.1 A General Viewpoint of Pattern Recognition.- 7.2 Tree Grammars for Syntactic Pattern Recognition.- 7.3 Syntactic Pattern Recognition Using Stochastic Languages.- 7.4 Error-Correcting Parsing.- 7.5 Clustering Analysis for Syntactic Patterns.- 7.5.1 Sentence-to-Sentence Clustering Algorithms.- A Nearest Neighbor Classification Rule.- The Cluster Center Techniques.- 7.5.2 A Proposed Nearest Neighbor Syntactic Recognition Rule.- 7.6 Picture Recognition.- 7.6.1 Properties of Regions.- 7.6.2 Detection of Objects.- Template Matching.- Edge Detection.- 7.6.3 Object Extraction.- Thresholding.- Region Growing.- 7.6.4 Representation of Objects and Pictures.- Borders.- Skeletons.- 7.7 Speech Recognition and Understanding.- References.