Advanced Applications in Pattern Recognition – serie

It is with great pleasure that I present this fourth vol­ ume in the series "Advanced Applications in Pattern Recognition." It would be difficult to find two authors better versed in the design and application of parallel image processing systems, due to both their own many years of pioneering in the field and their encyclopedic knowledge of what is going on in uni­ versity and industrial laboratories around the world. The monograph is unique in its parallel presentation of orthogonal and hexagonal dissections, and the wealth of graphic illustration of algorithmic procedures for processing and analyz­ ing images in the various known implementations of parallel im­ age-processing architectures. This volume should find a place on the bookshelf of every practitioner of pattern recognition, image processing, and compu­ ter graphics. Morton Nadler General Editor vii PREFACE This book endeavors to introduce the reader to the subject of cellular logic and cellular automata and is devoted particu­ larly to those parts dealing with the manipulation of pictorial data. The study of cellular automata owes much to the pioneer­ ing work of John von Neumann during the 1950s. Von Neumann was interested in general problems in the behavior of computing structures and was immensely impressed by the complexity and performance of the human brain, which he felt must point to­ wards successful designs for automatic computing machines.

It is with great pleasure that I present this third volume of the series "Advanced Applications in Pattern Recognition." It represents the summary of many man- (and woman-) years of effort in the field of speech recognition by tne author's former team at the University of Turin. It combines the best results in fuzzy-set theory and artificial intelligence to point the way to definitive solutions to the speech-recognition problem. It is my hope that it will become a classic work in this field. I take this opportunity to extend my thanks and appreciation to Sy Marchand, Plenum's Senior Editor responsible for overseeing this series, and to Susan Lee and Jo Winton, who had the monumental task of preparing the camera-ready master sheets for publication. Morton Nadler General Editor vii PREFACE Si parva licet componere magnis Virgil, Georgics, 4,176 (37-30 B.C.) The work reported in this book results from years of research oriented toward the goal of making an experimental model capable of understanding spoken sentences of a natural language. This is, of course, a modest attempt compared to the complexity of the functions performed by the human brain. A method is introduced for conce1v1ng modules performing perceptual tasks and for combining them in a speech understanding system.

It is most appropriate that the first volume to appear in the series "Advanced Applications in Pattern Recognition" should be this monograph by Nagao and Matsuyama. The work described here is a deep unification and synthesis of the two fundamental approaches to pat­ tern recognition: numerical (also known as "statistical") and struc­ tural ("linguistic," "syntactic"). The power and unity of the meth­ odology flow from the apparently effortless and natural use of the knowledge-base framework illuminated by the best results of artificial intelligence research. An integral part of the work is the algorithmic solution of many hitherto incompletely or clumsily treated problems. It was on the occasion of a laboratory visit in connection with the 4th IJCPR (of ~hich Professor Nagao was the very able Program Chairman) that I saw in operation the system described here. On the spot I expressed the desire to see the work described for the inter­ national technical audience in this series and the authors were kind enough to agree to contribute to a new and unknown series. With the publication of this monograph on the eve of the 5th ICPR my wish is fu1fi11~d. I want to thank here the authors and Plenum Publishing Corporation for making this volume and the series a reality.

The fuzzy set was conceived as a result of an attempt to come to grips with the problem of pattern recognition in the context of imprecisely defined categories. In such cases, the belonging of an object to a class is a matter of degree, as is the question of whether or not a group of objects form a cluster. A pioneering application of the theory of fuzzy sets to cluster analysis was made in 1969 by Ruspini. It was not until 1973, however, when the appearance of the work by Dunn and Bezdek on the Fuzzy ISODATA (or fuzzy c-means) algorithms became a landmark in the theory of cluster analysis, that the relevance of the theory of fuzzy sets to cluster analysis and pattern recognition became clearly established. Since then, the theory of fuzzy clustering has developed rapidly and fruitfully, with the author of the present monograph contributing a major share of what we know today. In their seminal work, Bezdek and Dunn have introduced the basic idea of determining the fuzzy clusters by minimizing an appropriately defined functional, and have derived iterative algorithms for computing the membership functions for the clusters in question. The important issue of convergence of such algorithms has become much better understood as a result of recent work which is described in the monograph.