Digital Pattern Recognition

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.