Handbook Of Pattern Recognition And Computer Vision (5th Edition)

C H Chen

• Publisher: WSPC
• Year: 2015
• ISBN:
  9789814656542
• Edition: 5
• Topic: Biological Sciences
• Subtopic: Science General
• Index: Biological Sciences

Pattern recognition, image processing and computer vision are closely linked areas which have seen enormous progress in the last fifty years. Their applications in our daily life, commerce and industry are growing even more rapidly than theoretical advances. Hence, the need for a new handbook in pattern recognition and computer vision every five or six years as envisioned in 1990 is fully justified and valid.

The book consists of three parts: (1) Pattern recognition methods and applications; (2) Computer vision and image processing; and (3) Systems, architecture and technology. This book is intended to capture the major developments in pattern recognition and computer vision though it is impossible to cover all topics.

The chapters are written by experts from many countries, fully reflecting the strong international research interests in the areas. This fifth edition will complement the previous four editions of the book.

Pattern recognition, image processing and computer vision are closely linked areas which have seen enormous progress in the last fifty years. Their applications in our daily life, commerce and industry are growing even more rapidly than theoretical advances. Hence, the need for a new handbook in pattern recognition and computer vision every five or six years as envisioned in 1990 is fully justified and valid.

The book consists of three parts: (1) Pattern recognition methods and applications; (2) Computer vision and image processing; and (3) Systems, architecture and technology. This book is intended to capture the major developments in pattern recognition and computer vision though it is impossible to cover all topics.

The chapters are written by experts from many countries, fully reflecting the strong international research interests in the areas. This fifth edition will complement the previous four editions of the book.

Readership: Graduate students, academics, practitioners, researchers, computer scientists, electrical and medical engineers.

PART 1

PATTERN RECOGNITION METHODS AND APPLICATIONS

CHAPTER 1.1

SYNTACTIC PATTERN RECOGNITION: PARADIGM ISSUES AND OPEN PROBLEMS

Mariusz Flasiński

IT Systems Department, Jagiellonian University,
ul. prof. St. Lojasiewicza 4, Cracow 30-348, Poland,
[email protected]

Paradigm issues of syntactic pattern recognition are presented in the chapter. Main open problems are identified and methodological principles are defined with respect to three basic models of this approach. The issues of enhancement of string models’ generative power, grammatical inference for tree models, and parsing/induction for graph models are discussed.

1.Introduction

There are two main approaches in the field of pattern recognition: the decision-theoretic approach and the syntactic/structural one. Representing a pattern by a vector of features is the main idea of the first approach. Feature vectors representing patterns of a learning set are “placed” in a feature space and they are used for partitioning the space into subareas corresponding to classes/categories. Then, various methods (discriminant function-based, probabilistic, artificial neural network-based, etc.) are used for a classification of an unknown pattern, i.e. for ascribing it to one of pre-defined classes.

Already at the beginning of the development of the field it turned out that some classes of patterns can be represented better with structural features than with feature vectors. This observation ushered in the syntactic approach in the early 1960s. Representing a pattern as a structure in the form of string, tree or graph and a set of structures as a formal language is the main idea of this approach.^1–5 According to the Chomsky paradigm, such an (infinite) language of structural patterns can be defined with a generator in the form of a generative grammar.⁶ Then, a recognition of an unknown pattern represented with a structure can be performed by a formal automaton, strictly speaking, by its implementation, namely a parser.

The syntactic approach has been applied successfully for such important problems of pattern recognition as, e.g., scene analysis, texture analysis, chemical and biological structure analysis, speech recognition, medical signals analysis, optical character recognition, natural language processing, since its beginning in the early 1960s for nearly three decades. Then, however, its development slowed down, since it has faced certain open problems, such as weak descriptive power of tractable grammars, high computational complexity of parsers, grammatical inference, which are hard to solve.^5,7

Indeed, open problems mentioned above have not been solved in a satisfactory way till now. However, in the case of some pattern recognition problems the use of the syntactic approach rather than the decision-theoretic one seems to be the only correct choice from a methodological point of view. Firstly, as we have mentioned above, the syntactic approach prevails over the decision-theoretic one, if patterns cannot be characterized adequately with feature vectors, since they are of the (strong) structural nature. Secondly, sometimes we require that a recognition method not only should classify, in the sense of ascribing an unknown pattern to one of pre-defined classes, but also deliver a description/interpretation of an unknown pattern. (This situation occurs frequently in issues typical for Artificial Intelligence applications and then we talk about pattern understanding.⁸) Thirdly, the structural nature of patterns can be complex, in the sense of a structural hierarchy. Then, in the syntactic approach we can represent and analyze a pattern in a hierarchical way. That is, we can decompose a complex pattern into simpler structural subpatterns, these subpatterns can be decomposed into simpler structural subpatterns and so on. At the bottom of such a hierarchy we use pre-defined elementary patterns, called primitives.

Paradigm issues which influence further development of syntactic pattern recognition are discussed in the chapter. In the next section three key open problems in the area, namely enhancement of context-free grammars, grammatical inference of tree grammars and constructing efficient graph parsers are identified. These problems are discussed in sections 3, 4, and 5, respectively. Final methodological remarks are included in the last section.

2.Methodological Foundations and Open Problems of Syntactic Pattern Recognition

The theory of formal languages delivers formal tools for syntactic pattern recognition. For its “standard” applications in computer science such as, e.g., programming languages, compilers design formalisms of grammar and automaton are sufficient. This results from the fact that grammar is constructed on the basis of a pre-defined syntax of artefactual language.

However, for pattern languages considered in computer vision their syntax is often not given explicitly. Instead of it a learning set, i.e., a sample set of pattern structures is available. This set, however, is so big that it results in an impossibility of constructing grammar “by hand.” A definition of a grammatical inference (induction) algorithm^a is a solution to the problem. A grammatical induction module (cf. Fig. 1) devises a syntactic pattern recognition system with a self-learning mechanism. Since a generation of a grammar is made in the off-line mode, (any) polynomial complexity of this algorithm is sufficient. Let us notice that the experts in the field consider a lack of an induction algorithm a serious limitation of a syntactic pattern recognition model.^5,7,9 Taking this into account, we can formulate the following principle.

Fig. 1.The general scheme of a syntactic pattern recognition system.

I. A syntactic pattern recognition model should include the following three components: a generative grammar, a computationally efficient parsing algorithm, and a grammatical induction algorithm of the polynomial time complexity.

As we have mentioned in the first section, in syntactic pattern recognition an image is decomposed into elementary patterns, called primitives. This decomposition is the result of the image processing phase (cf. Fig. 1). Noise reduction, smoothing, boundary sharpening/accentuation, image restoration, and decomposition/segmentation into primitives are basic operations of this phase. For example, an ECG image (cf. Fig. 2(a)) is filtered (grid lines are to be removed) and smoothed (cf. Fig. 2(b)). Finally, it is decomposed into primitives.

Structural primitives are usually meaningful semantically, in the sense they have a semantic interpretation in a given application area. Therefore, they are very often pre-defined by specialists in the application area. On the other hand, the use of “standard” decomposition/segmentation algorithms that involve (pure) mathematical models may result in receiving elementary components which differ, more or less, from pre-defined primitives. If differences are sma...

Table of contents

• Cover Page
• Title
• Copyright
• Dedication
• Preface to the 5th Edition
• Contents
• Part 1: Pattern Recognition Methods and Applications
• Part 2: Computer Vision and Image Processing
• Part 3: System, Architecture, and Technology
• Index