This paper describes an application of a distance measure between attributed relational graphs to the classification of muscle tissue patterns. The goal is to classify these patterns according to an increasing degree of abnormality. These degrees of abnormality are from 1 to 5 with 1 for completely normal muscles and 5 for completely abnormal muscles. The muscle tissue patterns are described as graphs with the nodes of the graphs representing groups of fibers, and the branches, the fibers which separate the nodes. The distance measure defined in this paper computes the number of modifications required to transform an input muscle tissue pattern to the reference one. For the application of the proposed distance measure a reference or ideal graph representing a normal muscle tissue pattern is created. Then the distance is calculated between the input pattern and the reference, and the numerical value of this distance is used for classification. Zero distance implies that the input pattern is normal and a distance greater than zero indicates the degree of abnormality.

This paper uses the concepts and technologies of the expert systems to the robot planning. Some examples of these planning systems have been presented. Finally, the planning performances of these systems have been compared with the existing planning systems.

Comparing the hand-written symbol with the set of training symbols (called reference symbols), we can recognize the input hand-written symbol by computing the distances among the input symbol and the reference symbols in the training set. In this paper we propose a VLSI architecture based on the space-time domain expansion which can compute the symbol distance and also give the index-pairs which correspond to the warp function. The time complexity is O(max(m, n)) by using m × n processing elements array, where m is the length of the input symbol and n is the length of the reference symbol. With a uniprocessor the matching process will have the time complexity O(m × n). If there are p reference symbols, using the proposed architecture the recognition problem can be solved in time O(max(m,n,p)). With a uniprocessor the time complexity will be O(m × n × p). The algorithm partition problems are discussed. Verification of the proposed VLSI architecture is also given.

A parallel algorithm for syntactic image segmentation is introduced. Stochastic tree grammar is used as a context-generating model. It is shown that when this context-generating process is in the equilibrium state, a matched filter can be designed and applied in parallel to the image. This process can be used for image segmentation in a syntactic pattern recognition system to enhance the performance of the succeeding recognition process.

This paper presents a powerful image understanding system that utilizes a semantic-syntactic (or attributed-synibolic) representation scheme in the form of attributed relational graphs (ARG's) for comprehending the global information contents of images. Nodes in the ARG represent the global image features, while the relations between those features are represented by attributed branches between their corresponding nodes. The extraction of ARG representation from images is achieved by a multilayer graph transducer scheme. This scheme is basically a rule-based system that uses a combination of model-driven and data-driven concepts in performing a hierarchical symbolic mapping of the image information content from the spatial-domain representation into a global representation. Further analysis and inter-pretation of the imagery data is performed on the extracted ARG representation. A distance measure between images is defined in terms of the distance between their respective ARG representations. The distance between two ARG's and the inexact matching of their respective components are calculated by an efficient dynamic programming technique. The system handles noise, distortion, and ambiguity in real-world images by two means, namely, through modeling and embedding them into the transducer's mapping rules, as well as through the appropriate cost of error-transformation for the inexact matching of the ARG image representation. Two illustrative experiments are presented to demonstrate some capabilities of the proposed system. Experiment I deals with locating objects in multiobject scenes, while Experiment II is concerned with target detection in SAR images.

The basic concept of learning control is introduced. The following five learning schemes are briefly reviewed: 1) trainable controllers using pattern classifiers, 2) reinforcement learning control systems, 3) Bayesian estimation, 4) stochastic approximation, and 5) stochastic automata models. Potential applications and problems for further research in learning control are outlined.

The problem of pattern recognition is discussed in terms of single-entity representation versus multiple-entity representation. A combined syntactic-semantic approach based on attributed grammars is suggested. Syntax-semantics tradeoff in pattern representation is demonstrated. This approach is intended to be an initial step toward unification of syntactic and statistical approaches to pattern recognition.

Inference of high-dimensional grammars is discussed. Specifically, techniques for inferring tree grammars are briefly presented. The problem of inferring a stochastic grammar to model the behavior of an information source is also introduced and techniques for carrying out the inference process are presented for a class of stochastic finite-state and context-free grammars. The possible practical application of these methods is illustrated by examples.

Inference of high-dimensional grammars is discussed. Specifically, techniques for inferring tree grammars are briefly presented. The problem of inferring a stochastic grammar to model the behavior of an information source is also introduced and techniques for carrying out the inference process are presented for a class of stochastic finite-state and context-free grammars. The possible practical application of these methods is illustrated by examples.

This paper presents the dynamic programming approach to the design of optimal pattern recognition systems when the costs of feature measurements describing the pattern samples are of considerable importance. A multistage or sequential pattern classifier which requires, on the average, a substantially smaller number of feature measurements than that required by an equally reliable nonsequential classifier is defined and constructed through the method of recursive optimization. Two methods of reducing the dimensionality in computation are presented for the cases where the observed feature measurements are 1) statistically independent, and 2) Markov dependent. Both models, in general, provide a ready solution to the optimal sequential classification problem. A generalization in the design of optimal classifiers capable of selecting a best sequence of feature measurements is also discussed. Computer simulated experiments in character recognition are shown to illustrate the feasibility of this approach.

The purpose of this paper is to demonstrate how a syntactic approach and, in particular, a tree system may be used to represent and classify fingerprint patterns. The fingerprint impressions are subdivided into sampling squares which are preprocessed and postprocessed for feature extraction. A set of regular tree languages is used to describe the fingerprint patterns and a set of tree automata is used to recognize the coded patterns. In order to infer the structural configuration of the encoded fingerprints, a grammatical inference system is developed. This sytem utilizes a simple procedure to infer the numerous substructures and relies on a reachability matrix and a man-machine interactive technique for the inference of complex structures. The 92 fingerprint impressions were used to test the proposed approach. A set of 193 tree grammars was inferred from each sampling square of the 4 × 4 sampling matrix which is capable of generating about 2 × 1034 classes for the fingerprint patterns.

An algorithm is proposed for the design of ``on-line'' learning controllers to control a discrete stochastic plant. The subjective probabilities of applying control actions from a finite set of allowable actions using random strategy, after any plant-environment situation (called an ``event'') is observed, are modified through the algorithm. The subjective probability for the optimal action is proved to approach one with probability one for any observed event. The optimized performance index is the conditional expectation of the instantaneous performance evaluations with respect to the observed events and the allowable actions. The algorithm is described through two transformations, T1, and T2. After the ``ordering transformation'' T1 is applied on the estimates of the performance indexes of the allowable actions, the ``learning transformation'' T2 modifies the subjective probabilities. The cases of discrete and continuous features are considered. In the latter, the Potential Function Method is employed. The algorithm is compared with a linear reinforcement schenme and computer simulation results are presented.

Description or discrimination of boundary curves (shapes) is an important problem in picture processing and pattern recognition Fourier descriptors (FD's) have interesting properties in this respect. First, a critical review is given of two kinds of FD's. Some properties of the FD's are given and a distance measure is proposed, in terms of FD's, that measures the difference between two boundarv curves. It is shown how FD's can be used for obtaining skeletons fobjects. Finally, experimental results are given in character recognition and machine parts recognition.

A methodology for three-dimensional collision-free path planning by which planning is done in the three-dimensional orthogonal two-dimensional projections of a three-dimensional environment is presented, Collision checking is done in each of the three orthogonal two-dimensional subspaces using primitive path segments. A hierarchical-path search method is used to speed up the search process. This approach forms basis for spatial planning in environments where no a priori knowledge is assumed. The three orthogonal two-dimensional projections can be readily obtained from three orthogonal cameras in simple environments.

A syntactic approach to three-dimensional object recognition from a single viewpoint is proposed. The system consists of two major parts: analysis and recognition. The analysis part consists of selecting primitive surface patches and modeling grammar construction. The recognition part consists of preprocessing, image segmentation, visible primitive surfaces identification, camera model estimation, and structural analysis. Attention is given primarily to the analysis and the structural analyzer of this system.

The space-time domain expansion method has recently been used to transform a computational task with a recursive formula into a VLSI architecture. In addition to its simplicity and completeness, an important advantage of this method is that it can easily solve the problem of partitioning an algorithm to fit a fixed size VLSI architecture. We propose a computational model and a partition rule which can be easily used to partition any recursive computation problem suited to the space-time domain expansion method so it can be solved on fixed-size VLSI architectures. Several examples, such as partitioned vector inner product, partitioned comparators in relational database management, partitioned matrix multiplications, and partitioned transitive closure computation, parallel recognition of general context-free languages, string matching and dynamic time-warp pattern-matching are used to illustrate the proposed method.

Syntactic pattern recognition is applied to the seismogram for the detection of bright spots. The calculation between error probability and Levenshtein distance is proposed. Three kinds of string distance computation are proposed to test the continuity of a bright spot pattern. The experiment on relative-amplitude real stacked seismograms is presented. The classification results are quite good and the proposed method can be used to improve seismic interpretation.

We present a methodology for 3-D collision-free path planning in which planning is done in the 3-orthogonal 2-D projections of a 3-D environment. Suboptimal path searching is done in each of the 3 orthogonal 2-D subspaces using primitive path segments. A hierarchical path searching method is introduced to speed up the search process. This approach lends applications to spatial planning in environments where no a priori knowledge is assumed. The three orthogonal 2-D projections can be readily obtained from 3 orthogonal cameras in simple environments.

Knowledge organization is a very important step in building an expert system. The problem is how to organize knowledge into a conceptual structure and thus make it complete, concise, and consistent. In this paper, concepts used in knowledge description are divided into tangible ones and intermediate ones depending on whether or not they appear in the input or the output of the system. Intermediate concepts and their relationships with tangible concepts are subjected to changes. A distance measure for rules and an algorithm for conceptual clustering are described. New intermediate concepts are generated using this algorithm. A few new concepts may replace a large number of old relationships and also generate new rules for the system. An experiment on traditional Chinese medicine shows that the proposed method produces results similar to those generated by experts.

VLSI technology has recently received increasing attention due to its high performance and high reliability. Designing a VLSI structure systematically for a given task becomes a very important problem to many computer engineers. In this paper, we present a method to transform a recursive computation task into a VLSI structure systematically. The main advantages of this approach are its simplicity and completeness. Several examples, such as vector inner product, matrix multiplication, convolution, comparison operations in relational database and fast Fourier transformation (FFT), are given to demonstrate the transformation procedure. Finally, we apply the proposed method to hierarchical scene matching. Scene matching refers to the process of locating or matching a region of an image with a corresponding region of another view of the same image taken from a different viewing angle or at a different time. We first present a constant threshold estimation for hierarchical scene matching. The VLSI implementation of the hierarchical scene matching is then described in detail.

A coherence problem may occur in a multicache system as soon as data inconsistency exists in the private caches and the main memory. Without an effective solution to the coherence problem, the effectiveness of a multicache system will be inherently limited. The problem is closely examined in this paper and previous solutions, both centralized approaches and distributed approaches, are analyzed based on the notion of semicritical sections. A state model is then presented which clarifies various coherence mechanisms as well as introduces a new state to enable the multicache system to more efficiently handle the processor writes. Software guidance, for performance and not for integrity, is advocated in a new proposal which in a practical multicache environment explores the benefit of the new state with little cost.

A low-cost geometry-preserving image database system is proposed in this paper. This scheme adapts, but not suppresses, the unique characteristics of images. In addition, an image data storage scheme which requires only linear order space-complexity is described to provide the benefits of not only saving storage space but also preserving geometrical features of images. The proposed database system provides more functions and easier and faster in image manipulations.

Earley's algorithm has been commonly used for the parsing of general context-free languages and the error-correcting parsing in syntactic pattern recognition. The time complexity for parsing is 0(n3). This paper presents a parallel Earley's recognition algorithm in terms of an ``X*'' operator. By restricting the input context-free grammar to be ¿-free, the parallel algorithm can be executed on a triangular-shape VLSI array. This array system has an efficient way of moving data to the right place at the right time. Simulation results show that this system can recognize a string with length n in 2n + 1 system time. We also present a parallel parse-extraction algorithm, a complete parsing algorithm, and an error-correcting recognition algorithm. The parallel complete parsing algorithm has been simulated on a processor array which is similar to the triangular VLSI array. For an input string of length n the processor array will give the correct right-parse at system time 2n + 1 if the string is accepted. The error-correcting recognition algorithm has also been simulated on a triangular VLSI array. This array recognizes an erroneous string of length n in time 2n + 1 and gives the correct error count. These parallel algorithms are especially useful for syntactic pattern recognition.

A 3-D object representation scheme which uses surfaces as primitives and grammatical production rules as structural relationship descriptors is proposed. Possible selections of surface primitives are discussed. Examples are given to illustrate the object description method.

The feasibility of applying image processing techniques to metal surface inspection is demonstrated. Two methods for metal surface inspection are described. In the first method, the metal surface reflective power and the metal surface normal are related by a random surface scattering model. The metal surface profile can then be computed from the metal surface normal. The second method applies pattern recognition techniques to classify metal surfaces into classes of different roughness. Methods of feature extraction and classification have been tested experimentally and the performances of different types of classifier have been compared. A two-level tree classifier using nonparametric linear classifiers at each node gives better than 90% correct classification on the testing set.

Attributed relational graphs (ARGs) have shown superior qualities when used for image representation and analysis in computer vision systems. A new, efficient approach for calculating a global distance measure between attributed relational graphs is proposed, and its applications in computer vision are discussed. The distance measure is calculated by a global optimization algorithm that is shown to be very efficient for this problem. The approach shows good results for practical size ARGs. The technique is also suitable for parallel processing implementation.

A general approach to the inference of context-free programmed grammars (CFPG) is proposed on the basis of inferability analysis. The method is applicable to a sufficiently large class of languages to be used for string pattern description in syntactic pattern recognition. Languages with basic recursive structure whose recursive parameter can be represented by polynomial functions with finite terms are always suitable for the suggested method. Five major problems are discussed: sample set generalization, string segmentation, CFPG trunk grammar inference, CFPG subgrammar inference, and derivation program unification.

A computer vision system is proposed, in which the recogni-tion of an object involves two interacting processes: model retrieval and model verification. The goal of the model retrieval process is to generate a proper structural description of the object in the input image, and use the description to retrieve candidate object models from the associative memory of the vision system. The present study explores one way of deriving such an object shape description from a single image. Regularity constraints and a preference rule are used to restrict the solutions to a preferred interpretation of geometric contours. Local interpretation is then propagated to neighboring regions. Through a proper control on the interaction between constraints and consistency checking, a rough object description in terms of visible surface orientations can be gener-ated. A computer vision system using this approach has been imple-mented and it is described in some details.

In this paper, we suggest a class of (attributed) expansive graph grammars which generate languages contained in a graph family ¿. It turns out that by means of node renumbering using a very effi-cient algorithm, any graph in ¿ can be converted into a standard form, which enables the use of related string representation for that graph to facilitate the syntax analysis. As a consequence, the syntax analysis of (attributed) expansive graph language is very efficient and almost like the parsing of tree languages. Furthermore, a syntax-directed transla-tion can be established for mapping one (attributed) expansive graph language to another. Finally, since many relational graphs for scene analysis can be considered as belonging to these graph languages, the proposed graph grammar model appears to be quite attractive from the application point of view.

A method to determine a distance measure between two nonhierarchical attributed relational graphs is presented. In order to apply this distance measure, the graphs are characterised by descriptive graph grammars (DGG). The proposed distance measure is based on the computation of the minimum number of modifications required to transform an input graph into the reference one. Specifically, the distance measure is defined as the cost of recognition of nodes plus the number of transformations which include node insertion, node deletion, branch insertion, branch deletion, node label substitution and branch label substitution. The major difference between the proposed distance measure and the other ones is the consideration of the cost of recognition of nodes in the distance computation. In order to do this, the principal features of the nodes are described by one or several cost functions which are used to compute the similarity between the input nodes and the reference ones. Finally, an application of this distance measure to the recognition of lower case handwritten English characters is presented.

The structure-preserved error-correcting graph isomorphism proposed by Tsai and Fu (1979) for matching patterns represented by attributed relational graphs is extended to the case of subgraphs. The resulting subgraph error-correcting isomorphism, which includes the structure-preserved error-correcting graph isomorphism as a special case, is useful for recognizing partially viewed or structurally distorted patterns. After formulating a subgraph error-correcting isomorphism as a state-space tree-search problem, heuristic information useful for speeding up the search is suggested and an ordered-search algorithm is proposed for finding an optimal subgraph error-correcting isomorphism.

This paper presents two VLSI architectures for the recognition of context-free languages and finite-state languages. The architecture for context-free languages consists of n(n+1)/2 identical cells and it is capable of recognizing an input string of length n in 2n time units. The architecture for finite-state languages consists of n cells and it can recognize a string of length n in constant time. Since both architectures have characteristics such as modular layout, simple constrol and dataflow pattern, high degree of multiprocessing and/or pipelining, etc., they are very suitable for VLSI implementation.

The nearest-neighbor decision rule for syntactic patterns is applied to seismic pattern classification. Each pattern is represented by a string. The string-to-string distance is used as a similarity measure. Another method using finite-state grammars inferred from the training samples and error-correcting parsers is also implemented. Both methods show equal recognition accuracy; however, the nearest-neighbor rule is much faster in computation speed. The classification results of real earthquake/explosion data are presented.

The PUMPS architecture consists of P task processing units (TPU) which share a pool of special peripheral processors, VLSI functional units, and a common two-dimensional shared memory (SM) via a block transfer oriented interconnection network. A shared cache is provided between the TPU's and SM for efficient MIMD interprocessor communication. The SM is also connected via a backend database management network (BDMN) with distributed control to the file memories, which are disk-based database storage devices.

In our earlier paper1 we proposed an algorithm S for error-correcting parsing of formal languages. It is found recently that two additional CS conditions and a routine for detecting infinite loop are required for the algorithm S.

In a previous a]er [1] we proposed a syntactic method for the analysis of time-varying image problems. A language translation schema (syntax-directed translation) is employed to characterize the time-varying process of an image sequence. The formulation of string translation is extended to trees using a generalized syntax-directed translation schema. The generalized model is then compared with the conventional top-down and bottom-up tree translation models. A parsing algorithm for this generalized tree translation schema is presented. A traffic monitoring system is designed using the tree translation schema to model vehicle motion patterns.

The problem of performing multiple attribute clustering in a dynamic database is studied. The extended K-d tree method is presented. In an extended K-d tree organization, the basic k-d tree structure after modification is used as the structure of the directory which organizes the data records in the secondary storage. The discriminator value of each level of the directory determines the partitioning direction of the corresponding attribute subspace. When the record insertion causes the data page to overload, the attribute space will be further partitioned along the direction specified by the corresponding discriminator.

In this study, a technique of performing multiple attribute clustering in dynamic databases has been investigated. We have transformed the problem of performing multiple attribute clustering into a problem of dynamically partitioning the attribute space. The optimal number of partitioning of the attribute space in a dynamic database environment has been analyzed, the partitioning direction is controlled by a discriminator sequence. The design of the discriminator sequence to obtain the optimal partitioning is presented. The selection of the directory attributes has also been discussed. Using the extended K-d tree to direct the partitioning, we have presented the extended K-d tree method. Empirical results have justified the improvement of the performance using the extended K-d tree method, when compared with that using the single attribute clustering or using inverted file method without any clustering index.

Extensive research and development has taken place over the last twenty years in the areas of pattern recognition. Areas to which these disciplines have been applied include business (e.g., character recognition), medicine (diagnosis, abnormality detection), automation (robot vision and automatic inspection), military intelligence, communications (data compression, speech recognition), and many others. This paper presents a very brief survey of recent developments in basic pattern recognition techniques.

Query-by-Pictorial-Example is a relational query language introduced for manipulating queries regarding pictorial relations as well as conventional relations. In addition to the manipulating capabilities of the conventional query languages, queries can also be expressed in terms of pictorial examples through a display tenninal. Example queries are used to illustrate the language facilities.

Attributed grammars are defned from the pattern recognidon point of view and shown to be useful for descriptions of syntactic stuctures as well as semantic attributes in primitives, subpatterns, and patterns. A pattern analysis system using attributed grammars Is proposed for pattern classification and description. This system extracts primitives and their attributes after preprocessing, performs syntax analysis of the resulting pattern representations, computes and extracts subpattern attributes for syntactically accepted patterns, and finally makes decisions according to the Bayes decision rule. Such a system uses a combination of syntactic and statistical pattern recognition techniques, as is demonstrated by illustrative examples and experimental results.

The problem of performing multiple attribute clustering in a dynamic database is studied. The extended K-d tree method is presented. in an extended K-d tree organization, the basic k-d tree structure after modification is used as the struc ture of the directory which organizes the data records in the secondary storage. The discrimina tor value of each level of the directory determines the partitioning direction of the corresponding attribute subspace. When the record insertion causes the data page to overload, the attribute space will be further partitioned along the direction specified by the corresponding discriminator. For a given query, the number of disk accesses involved is estimated. The design of the discriminator function are then described.

Query-by-Pictoriat-Exampe is a relational query language introduced for manipulating queries regarding pictorial relations as well as conventional relations. In addition to the manipulating capabilities of the conventional query languages, queries can also be expressed in terms of pictorial examples through a display terminal. Example queries are used to illuustrate the language facilities.

A pattern deformational model is proposed in this paper. Pattern deformations are categorized into two types: local deformation and structural deformation. A structure-preserving local deformation can be decomposed into a syntactic deformation followed by a semantic deformation, the former being induced on primitive structures and the latter on primitive properties. Bayes error-correcting parsing algorithms are proposed accordingly which not only can perform normal syntax analysis but also can make statistical decisions. An optimum Bayes error-correcting recognition system is then formulated for pattern classification. The system can be considered as a hybrid pattern classifier which uses both syntactic and statistical pattern recognition techniques.

The pattern deformational model proposed by Tsai and Fu [11] is extended so that numerical attributes and probability or density distributions can be introduced into primitives and relations in a nonhierarchical relational graph. Conventional graph isomorphisms are then generalized to include error-correcting capability for matching deformed patterns represented by such attributed relational graphs. An ordered-search algorithm is proposed for determining error-correcting isomorphisms. Finally, a pattern classification approach using graph isomorphisms is described, which can be considered as a combination of structural and statistical techniques.

The syntactic method is used to describe the structure of a two-dimensional shape by grammatical rules and the local details by primitives. Four attributes are proposed to describe an open curve segment, and the angle between two consecutive curve segments is used to describe the connection. The properties of the attributes and the recognition capability are studied. Two algorithms are implemented to perform the primitive extraction and syntax analysis at the same step by using both semantic and syntactic information, namely, the attributes and production rules. Also, an automatic inference procedure for the shape grammar is presented. This approach attempts to develop a general method for shape recognition.

The syntax errors on trees are defined in terms of five types of error transformations, namely, substitution, stretch, split, branch, and deletion. The distance between two trees is the least cost sequence of error transformations needed to transform one to the other. Based on this definition, a class of error-correcting tree automata (ECTA) is proposed. The operation of ECTA is illustrated by a character recognition example.

This paper describes error-correcting parsers for context-free and context-sensitive languages with substitution, insertion and deletion errors. Furthermore, it is shown that the ability of the proposed parsers can be expressed in terms of the weighted Levenshtein metric.

Cluster analysis for patterns represented by sentences is investigated. The similarity between patterns is expressed in terms of the distance between their corresponding sentences. A weighted distance between two strings is defined and its probabilistic interpretation given. The class membership of an input pattern (sentence) is determined according to the nearest neighbor or k-nearest neighbor rule. A clustering procedure on a sentence-to-sentence basis is proposed. A set of English characters is used to illustrate the proposed metric and clustering procedure.

In this paper, a probabilistic model for error-correcting parsing with substitution, insertion, and deletion errors is introduced. The formulation of maximum-likelihood error-correcting parser (MLECP) by incorporating the noise model into stochastic grammars is also presented. The use of stochastic error-correcting parsers for recognition of noisy and/or distorted patterns results in a process of high accuracy, but with low efficiency. In order to make the syntax analysis more practically feasible, it is proposed to use a sequential classification method for noisy strings processing. Computation results based on the classification experiments of noisy patterns for both nonsequential and sequential error-correcting parsers are presented.

The performance of a pattern classification system is often evaluated based on the risk committed by the classification procedure. The minimum attainable risk is the Bayes risk. Therefore, the Bayes risk can be used as a measure of the intrinsic complexity of the system, and it also serves as a reference of the optimality measure of a classification procedure. There are many practical situations in which the nonparametric methods may have to be called upon to estimate the Bayes risk. One of the nonparametric methods is via the probability density estimation technique. The convergence properties of this estimation technique are studied under fairly general assumptions. In the computer experiments reported, the estimate of the Bayes risk is taken as the sample mean of the density estimate by making use of the leave-one-out method. The probability density estimate used is the one proposed by Loftsgaarden and Quesenberry. This estimate is shown to be, in general, superior to the risk associated with a Bayes-like decision rule based on the error-counting scheme. This estimate is also compared experimentally with the risk estimate associated with the nearest neighbor rule.

A distance between two syntactic patterns is defined in terms of error transformations. This definition is extended to the case of distance measures between one syntactic pattern and a group of syntactic patterns. A nearest neighbor recognition rule for syntactic patterns using the proposed distance is then given. Using the proposed distance as a similarity measure, a clustering procedure for syntactic patterns is described. A character recognition experiment is given as an illustrative example.

Description or discrimination of boundary curves (shapes) is an important problem in picture processing and pattern recognition. Fourier descriptors (FD's) have interesting properties in this respect. First, a critical review is given of two kinds of FD's. Some properties of the FD's are given and a distance measure is proposed, in terms of FD's, that measures the difference between two boundary curves. It is shown how FD's can be used for obtaining skeletons of objects. Finally, experimental results are given in character recognition and machine parts recognition.

Extensive research and development has taken place over the last 20 years in the areas of pattern recognition and image processing. Areas to which these disciplines have been applied include business (e. g., character recognition), medicine (diagnosis, abnormality detection), automation (robot vision), military intelligence, communications (data compression, speech recognition), and many others. This paper presents a very brief survey of recent developments in basic pattern recognition and image processing techniques.

The purpose of this paper is to demonstrate how a syntactic approach and, in particular, a tree system may be used to represent and classify fingerprint patterns. The fingerprint impressions are subdivided into sampling squares which are preprocessed and postprocessed for feature extraction. A set of regular tree languages is used to describe the fingerprint patterns and a set of tree automata is used to recognize the coded patterns. In order to infer the structural configuration of the encoded fingerprints, a grammatical inference system is developed. This system utilizes a simple procedure to infer the numerous substructures and relies on a reachability matrix and a man-machine interactive technique for the inference of complex structures. The 92 fingerprint impressions were used to test the proposed approach. A set of 193 tree grammars was inferred from each sampling square of the 4 × 4 sampling matrix which is capable of generating about 2 × 1034classes for the fingerprint patterns.

TheL^{ \alpha}-distance between posterior density functions (PDF's) is proposed as a separability measure to replace the probability of error as a criterion for feature extraction in pattern recognition. Upper and lower bounds on Bayes error are derived for\alpha > 0. If\alpha = 1, the lower and upper bounds coincide; an increase (or decrease) in\alphaloosens these bounds. For\alpha = 2, the upper bound equals the best commonly used bound and is equal to the asymptotic probability of error of the first nearest neighbor classifier. The case when\alpha = 1is used for estimation of the probability of error in different problem situations, and a comparison is made with other methods. It is shown how unclassified samples may also be used to improve the variance of the estimated error. For the family of exponential probability density functions (pdf's), the relation between the distance of a sample from the decision boundary and its contribution to the error is derived. In the nonparametric case, a consistent estimator is discussed which is computationally more efficient than estimators based on Parzen's estimation. A set of computer simulation experiments are reported to demonstrate the statistical advantages of the separability measure with\alpha = 1when used in an error estimation scheme.

Feature extraction for parametric problems is carried out via the direct minimization of the probability of error estimated by the F-method. The proposed methods for feature ordering and feature extraction are applied to the medical diagnosis of two cancer diseases (cancer of the pancreas and primary cancer of the liver) with encouraging results.

A model of noise deformation of the substitution type is adopted for linguistic patterns generated by formal grammars. The maximum-likelihood criterion and the minimum-distance criterion are proposed for the classification of noisy strings described by context-free grammars. Classification algorithms based on a modified Cocke-Younger-Kasami parsing scheme are presented.

A model of a linguistic information source is proposed as a grammar that generates a language over some finite alphabet. It is pointed out that grammatical sentences generated by the source grammar contain intrinsic "redundancy" that can be exploited for error-corrections. Symbols occurring in the sentences are composed according to some syntactic rules determined by the source grammar, and hence are different in nature from the lexicographical source symbols assumed in information theory and algebraic coding theory. Almost all programming languages and some simple natural languages can be described by the linguistic source model proposed in this paper. In order to combat excessive errors for very noisy channels, a conventional encoding-decoding scheme that does not utilize the source structure is introduced into the communication system. Decoded strings coming out of the lexicographical decoder may not be grammatical, which indicates that some uncorrected errors still remain in the individual sentences and will be reprocessed by a syntactic decoder that converts ungrammatical strings into legal sentences of the source language by the maximum-likelihood criterion. Thus more errors in the strings coming out of the noisy channel can be corrected by the syntactic decoder using syntactic analysis than the !exicographical decoder is capable of correcting or even of detecting. To design the syntactic decoder we use parsing techniques from the study of compilers and formal languages.

The problem of grammatical inference is introduced, and its potential engineering applications are demonstrated. Inference algorithms for finite-state and context-free grammars are presented. The application of some of the algorithms to the inference of pattern grammars in syntactic pattern recognition is illustrated by examples.

Inference of high-dimensional grammars is discussed. Specifically, techniques for inferring tree grammars are briefly presented. The problem of inferring a stochastic grammar to model the behavior of an information source is also introduced and techniques for carrying out the inference process are presented for a class of stochastic finite-state and context-free grammars. The possible practical application of these methods is illustrated by examples.

One important area in engineering cybernetics is that of learning systems—the analysis and synthesis of engineering systems which exhibit learning behavior. During the past decade there has been a considerable growth of research interest in problems of learning systems. Many different approaches have been proposed for the design of systems with learning capabilities. Engineering applications include pattern recognition, communication and antenna systems, and control and diagnostic problems. Recent progress has indicated that the research in learning systems has just gone through a transient period from discussions of general philosophy, concepts and formulations of the problem to studies of a possible unified theory. This progress is significant in the sense that, once a unified approach is successful, further research efforts can then be concentrated toward the depth of the theory and its applications. One of the major contributors in this direction is Prof. Tsypkin, the author of this book. Under a general approach of probabilistic iterative algorithms or stochastic approximation procedures, this book treats systematically a broad class of problems in learning systems. Many existing learning algorithms can be put under this same general formulation, and these are compared.

It is generally a problem to select the appropriate preprocessing and feature-extraction technique in most pictorial pattern recognition applications so that an accurate classification is possible. In this paper a class of pictures of medical importance, namely, chest X-ray pictures, is used to test the proposed preprocessing and feature-extraction technique. The technique presented in this paper is applied only to chest X-ray images; however, the same technique could also be applied to a fairly broad class of picture patterns with only some minor modifications. The proposed preprocessing technique, which utilizes the local and global information of the picture patterns, is to extract the lung boundary. The lung field is then enclosed by a polygon which is the piecewise linear approximation of the lung boundary. The set of texture features, which are the average of some local property measures, is has then extracted in this approximated lung area. The proposed technique been tested on two sets of X-ray picture classes-one with abnormalities caused by a known disease and the others with abnormalities caused by some unkown effects in the lung region. The classification results presented in this paper show the feasibility of the proposed pictorial pattern recognition system in effectively screening out the abnormal pictures without human intervention.

An approach of representing patterns by trees rather than by strings is described. A review of tree systems that include tree grammars, transformations, and mappings on trees and tree automata is briefly presented. The tree system is then applied to the problem of syntactic pattern recognition. Tree grammars are used for pattern description, and tree automata are used for classification. Illustrative examples include the application of the tree system to the classification of bubble chamber events and some English characters.

This research is directed toward the development of a scheduling algorithm for large digital computer systems. To meet this goal methods of adaptive control and pattern recognition are applied. As jobs are received by the computer, a pattern recognition scheme is applied to the job in an attempt to classify its characteristics, such as a CPU-bound job, an I/O job, a large memory job, etc. Simultaneously, another subsystem, using a linear programming model, evaluates the overall system performance, and from this information an optimized (or desired) job stream is determined. When the processor requests a new job, it is chosen from the various classifications in an attempt to meet the optimal (or desired) job stream. After the jobs are completely processed, their characteristics are compared to the projected classification produced by the pattern discriminant function. The results are then returned to the discriminant function to update the decision mechanism, a minimum-distance discriminant function. From a systems point of view, this results in an adaptive or self-organizing control system. The overall effect is a dynamic scheduling algorithm. Simulation studies indicated that the scheduler was able to adapt to changing work loads, and it improved the turnaround times significantly. These simulation studies were based on a multiprocessor-uniprogram environment.

A procedure is described for stochastic syntax analysis of context-free languages. The parsing algorithm utilizes a bottom-up technique used in precedence languages. All decisions encountered in the algorithm ate determined statistically. The stochastic choice is computed from the a priori probability distribution of the language. Also developed is a stochastic context-free language for use in pattern classification of chromosome images. Classification is based on statistical decision theory with the probability of occurrence of each pattern computed from the stochastic context-free grammar.

A two dimensional adaptive model of a human operator in a visual-manual compensatory tracking task is proposed. The model is adaptive to changes in gain and/or form of the plant dynamics on each axis, accommodating plant transfer functions of the form (k/s) or (k/s2). Pattern recognition is used to sense changes in the control system requiring a change in the model operating mode. The form of the model is derived from consideration of the physiological processes evident in a human controller. It contains separate sections dealing with perception of the control system variables, action taken by the central nervous system (CNS) as a result of the sensory inputs, and the conversion of CNS commands into motions of the controller. The model reflects the influence of the dominant type 2 control strategy on the type 1 strategy when tracking is performed with heterogeneous plant axis dynamics. Tests of the gain adaptive algorithm simulating time invariant human operator performance are described, and the test results presented for types 1 and 2 control situations. Results of pattern recognition tests conducted with model-generated data are also presented.

The authors wish to thank G. W. Beakley and F. B. Tuteur for their identification of a source of difficulty in the analysis of the non- parametric procedure as originally proposed. We shall reexamine our analysis in the light of this new development and will report on any modifications at a later date.

A nonparametric procedure is developed for determining a structure for multivariate, multiclass pattern classification. The resultant classifier is in the form of a layered machine which is composed of multithreshold elements. The basic algorithm determines partitions which are parallel hyperplanes orthogonal to the feature coordinate dimensions. Inherent in the procedure is the concept of a transgenerator unit used to establish new feature dimensions such that effective partitioning can be obtained. While the choice of which classes of transgeneration units to consider is ultimately up to the user, a number of such units are suggested herein. The algorithm gives an indication as to the effectiveness of various transgeneration units and hence can also be used in an interactive manner if so desired for the actual design of a classification structure.

The paper deals with the problem of "compound" and "cascade threshold" element "synthesis" of an arbitrary Boolean function from the "multithreshold weight threshold vector" (MTWTV). The above synthesis procedure is presented to reveal a unique feature of the multithreshold weight threshold vector, from which several realizations of threshold element nets can be obtained from one of the multithreshold weight threshold vectors.

Abstract—In this note, three suboptimal solutions are obtained for the joint sequential feature selection and pattern classification problem. These solutions allow the comparison of two distinctly different approximations to the optimal procedure. One approximation involves simplifying assumptions on the underlying distribution of features for each pattern class, while the second involves an approximation in the implementation of the optimal procedure.

An algorithm for the realization of k-threshold threshold realizable functions is presented. Instead of solving the set of linear inequalities, where the unknowns are the weights corresponding to the input variables, incremental weights are sought. The procedure reduces to that of resolving contradicting pairs of vertices by the incremental weights. The minimum number of thresholds are sought for each complementation and permutation of input variables. A definition of an optimal multithreshold weight threshold vector is derived from the reliability viewpoint. The desired solution is obtained through a search of all possible obtainable realization vectors of the function. For single-threshold realizable functions, permutation and complementation of input variables need not be considered if the input variables of the function are ordered and positivized. The procedure is systematic and has been programmed in FORTRAN IV. As a comparison with Haring and Ohori's tabulation on the 221 equivalence classes of four variable Boolean functions under the NPN1operation, it can be seen that 42 of the 221 equivalence classes need fewer numbers of thresholds for their realization. For the same number of thresholds, 58 equivalence classes have less absolute sum of weights. Finally, with the number of thresholds and absolute sum of weights being equal, 36 equivalence classes have lower threshold values.

This paper deals with input tolerance considerations of a multithreshold threshold element. The concept of a multilevel minus-plus-one model[9]of a threshold element is introduced. It is shown that the multilevel minus-plus-one model is equivalent to the zero-one model[9]of a multithreshold element. The equivalence is established through a set of defining equations similar to that of a single threshold threshold element. For a nonlinearly separable Boolean function, more than one multithreshold weight threshold vector may exist for its realization, even though the number of thresholds and the sum of the absolute magnitude of all the input weights are the same; i.e., Σni=1|wi|. From reliability considerations, the optimal synthesis of the multithreshold threshold elements is shown to depend on the magnitudes of max (|T1|, |Tk|) in addition to the minimum number of thresholds needed to realize the Boolean function and the min Σni=1|wi|. An example is given for illustrative purposes of choosing an optimal realization. For a given margin of operation with the error model assumed, it is shown that one need only work from the normalized set of inequalities. The solution with margins specified is obtained from the optimal solutions of the normalized system of inequalities.

Properties of self-dual and self-complementary dual functions are discussed. Necessary and sufficient conditions of self-dual and self-complementary dual functions are obtained in terms of the multithreshold weight threshold vector. In particular, self-dual and self-complementary dual functions are shown to be realizable only by an odd and even number of effective thresholds, respectively. A threshold Tjis effective if Eminjmax. It is shown that n+1 variable self-dual and self-complementary dual functions can always be generated from 1- and 2-effective-threshold weight threshold vectors of n-variable Boolean functions, respectively. If the number of effective thresholds exceeds 2, constraints on the thresholds must be met in order to generate n+1 variable self-dual and self-complementary dual functions. Such generations of self-dual and self-complementary dual functions are shown to correspond to the functional forms of self-dualization and self-complementary dualization of an n-variable Boolean function. Moreover, they are realized by the same threshold vector T. Furthermore, it is shown that if an n-variable Boolean function Fn(X) is self-dual or self-complementary dual with weight threshold vector [Wn; T], then an n+m variable self-dual or self-complementary dual Boolean function Fn+m(X), where m is any positive integer, can be realized by a weight threshold vector [Wn+m; T]. The above cited weight vectors Wnand Wn+mare constrained by If Σni=1Wi= Σn+mi=1Wi. Σni=1|Wi| = &3x003A3;n+mi=1|Wi|, then optimal realization vectors seem to be obtained.

Abstract—A more general adaptive procedure for determining linear or piecewise linear discriminant functions for multiclass pattern classification is proposed. The adaptive procedure is a many-pattern or group-pattern adaptation. The training sequence consists of groups of vectors in matrix form instead of single vectors. The convergence proof shows that this procedure terminates in a finite number of adaptions if the solution exists. A necessary and suffcient condition is developed for testing the linear separability of each subset of (d + 1) samples. Furthermore, the proposed procedure can be implemented with the addition of only a little complexity to existing systems. Computer simulations indecate satisfactory results.

This paper presents the dynamic programming approach to the design of optimal pattern recognition systems when the costs of feature measurements describing the pattern samples are of considerable importance. A multistage or sequential pattern classifier which requires, on the average, a substantially smaller number of feature measurements than that required by an equally reliable nonsequential classifier is defined and constructed through the method of recursive optimization. Two methods of reducing the dimensionality in computation are presented for the cases where the observed feature measurements are 1) statistically independent, and 2) Markov dependent. Both models, in general, provide a ready solution to the optimal sequential classification problem. A generalization in the design of optimal classifiers capable of selecting a best sequence of feature measurements is also discussed. Computer simulated experiments in character recognition are shown to illustrate the feasibility of this approach.

In a recent paper Watanabe (1965) has established two useful theorems concerning the optimum properties of the Karhunen-Loeve expansion for the random functions of a stochastic process. The resulting coordinate system (Karhunen-Loeve system) was found to be optimum in the sense of i) minimizing the mean-square error committed by approximating the expansion of an infinite series by a finite number of terms, ii) minimizing the entropy function defined over the probability distribution of the coordinate coefficients for the entire ensemble. These optimum features were then effectively applied to the preprocessing of input data for the speech recognition problem. However, in the development of these properties considerations were only given to the situation where the random functions come from the same stochastic process, and consequently the coordinate coefficients in the expansion were treated to be nonrandom. The question then arises as to whether the optimum properties will hold if the random functions are realizations of more than one stochastic process as in the case of many preprocessing problems in pattern recognization and signal detection. The purpose of this correspondence is to show. that the cited optimum properties can be retained by defining a generalized Karhunen-Loeve expansion which considers the possibility of two or more stochastic processes generating the random functions. Necessary conditions are derived to assure the existence of such an expansion. Applications of these results are indicated in the ranking and selection of feature measurements for the sequential recognition (decision) problems.

In the problems of statistical pattern recognition, it has become increasingly known that there are many applications in which parametric assumptions regarding the pattern statistics are not justified. This paper treats a nonparametric design of a sequential recognition machine which uses the optimum property of Wald's sequential probability ratio test (SPRT). For the case of binary classification, a sequential ranking procedure is found useful in a two-sample problem in which we wish to test the hypothesis against the Lehmann alternatives, based on the successively ranked observations. The test procedure is then analyzed in terms of the performance criterion which in this case is the expected number of observations, with specified error probabilities. A generalization procedure of multiple classification is also given as a direct extension. Computer-simulated experiments have illustrated the effectiveness of this test procedure in the recognition of handwritten English characters, where the nonparametric method seems to be necessary and appropriate.

The problem of optimally terminating the sequential recognition procedure at a finite time prespecified by the designer is considered. The application arises, in practice, when the receptor (feature extraction) part of a sequential recognition machine has only a finite number of suitable features available to the categorizer (decision) part, or the cost of taking observation is found too high as the recognition process exceeds a certain time limit. In either case, the urgency to terminate the recognition procedure becomes greater when the available measurements are to be exhausted. The problem is studied by considering time-varying stopping boundaries for the sequential procedure such that by a preassigned length of time, the acceptance and rejection regions meet and, therefore, one of the pattern classes has to be accepted as the terminal decision. The idea of varying the stopping rules as a function of time enables us to investigate the behavior of a modified sequential test as compared to the standard Wald test with constant stopping boundaries. Computer simulation of English character recognition using the modified sequential test procedure indicates very satisfactory results.