Syntactic Pattern Recognition, Applications

The many different mathematical techniques used to solve pattem recognition problems may be grouped into two general approaches: the decision-theoretic (or discriminant) approach and the syntactic (or structural) approach. In the decision-theoretic approach, aset of characteristic measurements, called features, are extracted from the pattems. Each pattem is represented by a feature vector, and the recognition of each pattem is usually made by partitioning the feature space. Applications of decision-theoretic approach indude character recognition, medical diagnosis, remote sensing, reliability and socio-economics. A relatively new approach is the syntactic approach. In the syntactic approach, ea ch pattem is expressed in terms of a composition of its components. The recognition of a pattem is usually made by analyzing the pattem structure according to a given set of rules. Earlier applications of the syntactic approach indude chromosome dassification, English character recognition and identification of bubble and spark chamber events. The purpose of this monograph is to provide a summary of the major reeent applications of syntactic pattem recognition. After a brief introduction of syntactic pattem recognition in Chapter 1, the nin e mai n chapters (Chapters 2-10) can be divided into three parts. The first three chapters concem with the analysis of waveforms using syntactic methods. Specific application examples indude peak detection and interpretation of electro­ cardiograms and the recognition of speech pattems. The next five chapters deal with the syntactic recognition of two-dimensional pictorial pattems.

1. Introduction to Syntactic Pattern Recognition..- 1.1 Syntactic (Structural) Approach to Pattern Recognition.- 1.2 Syntactic Pattern Recognition System.- 1.3 Selection of Pattern Primitives.- 1.3.1 Primitive Selection Emphasizing Boundaries or Skeletons.- 1.3.2 Pattern Primitives in Terms of Regions.- 1.4 Pattern Grammar.- 1.5 High-Dimensional Pattern Grammars.- 1.6 Syntax Analysis as Recognition Procedure.- 1.6.1 Recognition of Finite-State Languages.- 1.6.2 Syntax Analysis of Context-Free Languages.- 1.7 Concluding Remarks.- References.- 2. Peak Recognition in Waveforms..- 2.1 What is a Peak?.- 2.1.1 Mathematical Definition.- 2.1.2 Syntactical Definition.- 2.2 Practical Peak Recognition.- 2.2.1 Signal and Noise.- 2.2.2 Piecewise Linear Approximation Preprocessor.- 2.2.3 Peak Recognition Algorithms.- 2.3 Application to Electrocardiography.- 2.4 Concluding Remarks.- References.- 3. Electrocardiogram Interpretation Using a Stochastic Finite State Model..- 3.1 The Interpretation Problem.- 3.2 A Solution to the Interpretation Problem.- 3.2.1 The Tree Structure.- 3.2.2 The Yield of a Node.- 3.2.3 The Probability of a Node.- 3.2.4 The Tree Search.- 3.3 A Simple Example.- 3.4 Application to Analog Signal Processing.- 3.5 An Example Application.- 3.5.1 The Clock Model.- 3.5.2 The Clock Pulse Detector.- 3.5.3 The Total System.- 3.6 The Solution to the Clock Signal Interpretation Problem.- 3.6.1 The Search Tree.- 3.6.2 The Abbreviated Tree Structure.- 3.6.3 The Probability of a Node.- 3.6.4 Summary of the Tree Structure.- 3.7 A Sample Clock Signal Search Tree.- 3.8 Conclusion.- References.- 4. Syntactic Recognition of Speech Patterns..- 4.1 Background.- 4.2 Preprocessing and Feature Extraction.- 4.2.1 Signal Processing.- 4.2.2 Trajectories of Speech Parameters.- 4.2.3 Distinctive Features.- 4.3 Syntax-Controlled Segmentation of Continuous Speech.- 4.4 Syntactic Recognition of Syllables and Words.- 4.5 Linguistic Interpretation of Speech Patterns.- 4.5.1 Evaluation of Hypotheses.- 4.5.2 Preselection Rules.- 4.5.3 Verification of Hypotheses.- 4.6 Automatic Learning of Speech Patterns.- 4.7 Conclusions.- References.- 5. Chinese Character Recognition..- 5.1 Historical.- 5.1.1 An Approach to Pattern Recognition.- 5.1.2 A Chinese Reading Machine.- 5.1.3 Chinese Characters.- 5.1.4 Preview.- 5.2 The Morphology of Chinese Characters.- 5.2.1 Models.- 5.2.2 Some Applications.- 5.3 Recognition of Chinese Characters.- 5.3.1 The Model.- 5.3.2 Input.- 5.3.3 Analysis of Components.- 5.3.4 Analysis of Characters.- 5.3.5 Encoding of Components.- 5.3.6 Encoding of Characters.- 5.3.7 Results.- 5.3.8 Conclusions.- 5.3.9 Other Approaches.- References.- 6. Shape Discrimination..- 6.1 Basic Considerations.- 6.2 Description of Contours in Terms of Polygons.- 6.3 Description of the Shape of Polygons.- 6.4 Fundamentals of Decomposition.- 6.5 Further Decomposition and Shape Description.- 6.6 Decomposition of Polygons with Holes.- 6.7 Implementation of the Decomposition Algorithm.- 6.8 Discussion of the Methodology.- References.- 7. Two-Dimensional Mathematical Notation..- 7.1 Mathematics Notation.- 7.2 Coordinate Grammars.- 7.3 A Syntax-Directed Recognition Algorithm.- 7.3.1 Characters.- 7.3.2 Syntactic Units.- 7.3.3 Coordinate Grammar Rules for Two-Dimensional Character Configurations.- 7.4 Scope of Recognition Capability.- 7.5 Implementation and Efficiency.- 7.6 Summary.- Appendix 7.A.- Appendix 7.B.- References.- 8. Fingerprint Classification..- 8.1 Historical Background.- 8.1.1 Fingerprint Pattern.- 8.1.2 Automatic Fingerprint Identification.- 8.2 Syntactic Approach.- 8.2.1 Digitizer.- 8.2.2 Preprocessing.- 8.2.3 Feature Extractor.- 8.2.4 Fingerprint Classifier.- 8.3 Tree Grammar Approach to Fingerprint Pattern Recognition.- 8.3.1 Tree Classifier.- 8.3.2 Tree Grammar.- 8.3.3 Grammatical Inference.- 8.3.4 Computer Simulation.- 8.4 Summary.- References.- 9. Modeling of Earth Resources Satellite Data..- 9.1 The Satellite Data.- 9.2 The Model.- 9.3 Details of the Analysis.- 9.3.1 Clouds and Shadows.- 9.3.2 The Downtown Area.- 9.4 Inferring a Grammar for the Highways.- 9.5 Summary.- References.- 10. Industrial Objects and Machine Parts Recognition..- 10.1 A Short Review of Leading Ideas.- 10.2 Levels of Knowledge.- 10.3 Hardware.- 10.3.1 Input.- 10.3.2 Output.- 10.4 Software.- 10.4.1 The Dictionary.- 10.4.2 Software Tools.- 10.5 Pattern Recognition.- 10.5.1 Preprocessing.- 10.5.2 Feature Extraction.- 10.5.3 The Grammar.- 10.5.4 The Organization of the Grammar.- 10.5.5 Some Heuristics.- 10.6 Conclusions.- References.