An application of stochastic languages to fingerprint pattern recognition

The purpose of this paper is to present a stochastic syntactic approach for representation and classification of fingerprint patterns.The fingerprint impressions are subdivided into sampling squares which are preprocessed for feature extraction. First, a brief summary of application of a class of context-free languages for recognition of fingerprints is presented. Next, using the same set of features, a class of stochastic context-free languages was used to further classify the fingerprint impressions. The recognizers using the class of context-free and stochastic context-free languages are named the first-level and second-level classifiers, respectively. Experimental results in terms of real data fingerprints are presented.     

Efficient regular grammatical inference for pattern recognition

A new and simple method for the inference of regular grammars or finite automata is presented. It is based on the analysis of the successive appearances of the terminal symbols in the learning strings. It is shown that for syntactic pattern recognition applications, this method is more efficient than other algorithms already proposed.     

A syntactic approach to twig-query matching on XML streams

Query matching on XML streams is challenging work for querying efficiency when the amount of queried stream data is huge and the data can be streamed in continuously. In this paper, the method Syntactic Twig-Query Matching (STQM) is proposed to process queries on an XML stream and return the query results continuously and immediately. STQM matches twig queries on the XML stream in a syntactic manner by using a lexical analyzer and a parser, both of which are built from our lexical-rules and grammar-rules generators according to the user's queries and document schema, respectively. For query matching, the lexical analyzer scans the incoming XML stream and the parser recognizes XML structures for retrieving every twig-query result from the XML stream. Moreover, STQM obtains query results without a post-phase for excluding false positives, which are common in many streaming query methods. Through the experimental results, we found that STQM matches the twig query efficiently and also has good scalability both in the queried data size and the branch degree of the twig query. The proposed method takes less execution time than that of a sequence-based approach, which is widely accepted as a proper solution to the XML stream query.     

A syntactic method for image segmentation and object recognition

In this paper, image segmentation and object recognition using syntactic methods are investigated. The segmentation process is embedded in the parsing algorithm. The approach can be described by a syntax-directed relaxation process. Previous error-correcting parsing algorithms, however, have not tackled the segmentation problem satisfactorily. Experimental results using Synthetic Aperture Radar (SAR) images are given.     

A syntactic approach to seismic pattern recognition

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 artificial intelligence approach to pattern recognition—a perspective and an overview

The present paper reviews the techniques for automated extraction of information from signals. The techniques may be classified broadly into two categories—the conventional pattern recognition approach and the artificial intelligence (AI) based approach. The conventional approach comprises two methodologies—statistical and structural. The paper reviews salient issues in the application of conventional techniques for extraction of information. The systems that use the artificial intelligence approach are characterized with respect to three key properties. The basic differences between the approaches and the computational aspects are reviewed. Current trends in the use of the AI approach are indicated. Some key ideas in current literature are reviewed.     

Software support for the construction of syntactic pattern recognisers by a research engineer

Syntactic pattern recognition is introduced and it is suggested that a research engineer will probably be less familiar with the language theory underlying syntactic pattern recognition than with the statistical ideas connected with decision theoretic methods. For this reason application of syntactic pattern recognition will only develop if software support is provided. The steps of grammatical inference, recogniser construction and recogniser optimisation are outlined. They are included in a scheme by which, working interactively and iteratively, a syntactic pattern recogniser can be produced. Some comments on an implementation are given.     

Breadth-first search strategies for trie-based syntactic pattern recognition

Dictionary-based syntactic pattern recognition of strings attempts to recognize a transmitted string X ^*, by processing its noisy version, Y, without sequentially comparing Y with every element X in the finite, (but possibly, large) dictionary, H. The best estimate X ⁺ of X ^*, is defined as that element of H which minimizes the generalized Levenshtein distance (GLD) D(X, Y) between X and Y, for all X ∈H. The non-sequential PR computation of X ⁺ involves a compact trie-based representation of H. In this paper, we show how we can optimize this computation by incorporating breadth first search schemes on the underlying graph structure. This heuristic emerges from the trie-based dynamic programming recursive equations, which can be effectively implemented using a new data structure called the linked list of prefixes that can be built separately or “on top of” the trie representation of H. The new scheme does not restrict the number of errors in Y to be merely a small constant, as is done in most of the available methods. The main contribution is that our new approach can be used for generalized GLDs and not merely for 0/1 costs. It is also applicable when all possible correct candidates need to be known, and not just the best match. These constitute the cases when the “cutoffs” cannot be used in the DFS trie-based technique (Shang and Merrettal in IEEE Trans Knowl Data Eng 8(4):540–547, 1996). The new technique is compared with the DFS trie-based technique (Risvik in United Patent 6377945 B1, 23 April 2002; Shang and Merrettal in IEEE Trans Knowl Data Eng 8(4):540–547, 1996) using three large and small benchmark dictionaries with different errors. In each case, we demonstrate marked improvements with regard to the operations needed up to 21%, while at the same time maintaining the same accuracy. Additionally, some further improvements can be obtained by introducing the knowledge of the maximum number or percentage of errors in Y.

Syntactic recognition of ECG signals by attributed finite automata

A syntactic pattern recognition method of electrocardiograms (ECG) is described in which attributed automata are used to execute the analysis of ECG signals. An ECG signal is first encoded into a string of primitives and then attributed automata are used to analyse the string. We have found that we can perform fast and reliable analysis of ECG signals by attributed automata.     

A pattern recognition approach to understanding the multi-layer perception

This letter is concerned with the operation of a class of multi-layer associative networks commonly known as the multi-layer perceptron (MLP), Rumelharte network or back-propagation network. We describe the operation of the MLP as a pattern recognition device in terms of a feature-space representation. This allows an understanding of how structure in the training data is represented internally in the machine.     

Structural pattern recognition,homomorphisms, and arrangements

This paper discusses the general supervised pattern discrimination problem from a structural point of view. We show that both the problem of determining a decision rule and the problem of applying a decision rule are problems of finding homomorphisms, whether the pattern data structure is an N-tuple as in statistical pattern recognition, or a string or its generalizations as in syntactic pattern recognition. We then introduce the concept of an arrangement, which is a labeled N-ary relation, as a more complex pattern data structure and show how decision rules can be constructed and applied to arrangements using the homomorphism concept. The methodology suggested in the paper provides a structural pattern recognition generalization to phrase-structured syntactic pattern recognition.     

Conversion and parsing of tree transducers for syntactic pattern analysis

The conversion algorithms for two classes of tree transducers, i.e., simple generalized syntax-directed tree translation (SGSDTT) and generalized finite state transformation (GFST), are proposed. A top-down backtrack parsing algorithm for a GFST is presented. The minimum distance structure-preserved error-correcting tree automaton is also extended to be a parser for SGSDTT. Finally, the tree transducers are applied to modeling and analysis of human motion.This work was supported by the NSF Grant IST 79-18884.     

A multilevel approach to pattern processing

This paper presents a methodology for describing multilevel pattern processing systems. It is suggested that any pattern processor can be adequately described in terms of multiple hierarchies of two types of fundamental mechanism: (1) a process which performs the pattern recognition functions of analysis and synthesis and (2) a process which performs the syntactic functions of parsing and generation. A computer implementation of these principles is outlined which enables a range of systems to be configured. Examples of speech and non-speech pattern processing are presented.     

A syntax-directed program that performs a three-dimensional perceptual task

A syntax-directed program that performs a three-dimensional perceptual task is described. The task, in a slightly simpler form, was used originally in a psychological study of mental rotation. ⁽¹⁾ The task consists of determining whether two line drawings portray (different views of) identical objects, mirror image objects, or structurally different objects, where the objects are composed of linear strings of attached cubes. The program is syntax-directed in the sense that it uses a fixed set of syntactic rules to analyze the line drawings. This is the first use of formal syntactic techniques in the analysis of pictures (in this case, line drawings) of three-dimensional objects.     

Syntactic/semantic techniques in pattern recognition: A survey

This paper surveys some of the contemporary work in syntactic/semantic pattern recognition, with emphasis on four topics that are active research areas. These areas-grammatical inferrence, probabilistic models, syntactic errorcorrection, and grammars with attributes-present challenging questions both as to theory and as to practice.Portions of the paper are adapted from Syntactic Methods in Pattern Recognition, M. G. Thomason, to appear in theProceedings of the NATO Advanced Study Institute, Oxford University, 1981 J. Kittler, Ed. (D. Reidel Publishing Company. Dordrecht, Holland).     

The scaling problem in the pattern recognition approach to machine translation

Statistical machine translation (SMT) has proven to be an interesting pattern recognition framework for automatically building machine translations systems from available parallel corpora. In the last few years, research in SMT has been characterized by two significant advances. First, the popularization of the so called phrase-based statistical translation models, which allows to incorporate local contextual information to the translation models. Second, the availability of larger and larger parallel corpora, which are composed of millions of sentence pairs, and tens of millions of running words. Since phrase-based models basically consists in statistical dictionaries of phrase pairs, their estimation from very large corpora is a very costly task that yields a huge number of parameters which are to be stored in memory. The handling of millions of model parameters and a similar number of training samples have become a bottleneck in the field of SMT, as well as in other well-known pattern recognition tasks such as speech recognition or handwritten recognition, just to name a few. In this paper, we propose a general framework that deals with the scaling problem in SMT without introducing significant time overhead by means of the combination of different scaling techniques. This new framework is based on the use of counts instead of probabilities, and on the concept of cache memory.     

A unified approach to pattern recognition

The paper is an outline of a new approach to pattern recognition developed by the author. A fuller introduction to the approach will appear soon.⁽¹⁾ Within the proposed framework the two principal approaches to pattern recognition—vector and syntactic—are unified.     

Supervised pattern recognition by parallel feature partitioning

In the present paper the supervised pattern recognition problem is considered. For solving the problem a mathematical model based on parallel feature partitioning is proposed. The solution is obtained by partitioning the feature space to a minimal number of nonintersecting regions. This is achieved by solving an integer-valued optimization problem, which leads to the construction of minimal covering. Since the classes do not intersect it follows that the solution of the formulated problem exists. Computational complexity of the model and computational procedures are discussed. Geometrical interpretation of the solution is given.