Structural Pattern Analysis

The following sections are included:

• PREFACE

• CONTENTS

Multivalued strings and an extension of Earley's parsing algorithm are introduced. The resulting method is suitable for recognition of patterns in distorted input data. Applications in waveform and image analysis are discussed.

There are interesting Pattern Recognition problems which do not admit a proper formulation in terms of classification, and which could adequately be stated under the more general framework of “interpretation”. Without loss of generality, an interpretation of a given representation of an object can be considered in terms of a “semantic message”; i.e., a sentence from a certain semantic language in which the actions to be carried out as a response to the interpretation of the given object can be specified. This interpretation task can be conveniently formalized through the concept of transduction. In this paper, we propose a methodology for the inductive inference of finite state transducers from samples of known translations corresponding to the interpretation task that is considered. The proposed methodology is applied to two different Pattern Recognition tasks involving unidimensional objects including speech signals. The results show both the convenience of the transducer inference framework and the capability of the methods that are proposed here to achieve this inference.

The paper describes a speech coding system based on an ear model followed by a set of Multi-Layer Networks (MLN). MLNs are trained to learn how to recognize articulatory features like the place and manner of articulation. Experiments are performed on 10 English vowels showing a recognition rate higher than 95% for new speakers. When features are used for recognition, comparable results are obtained for vowels and diphthongs not used for training and pronounced by new speakers. This suggests that MLNs suitably fed by the data computed by an ear model have good generalization capabilities over new speakers and new sounds.

This paper introduces the concept of a pattern complex for the purpose of object recognition and identification. A pattern complex is a set of measurements, one measurement coming from each unit or entity being measured. Some of the measurements in the pattern complex come from entities which may be a part of one of the objects of interest. Other measurements may be the result of uninteresting environmental clutter or noise. Recognition with the pattern complex constitutes the structural problem of simultaneously selecting which units and measurements are associated with an object of interest and then making an identification based on the selected measurements. Classical statistical pattern recognition is the simplest, most special case of recognition with the pattern complex. Likewise, relational matching is a special case of the pattern complex problem.

In this work, we present a new representation of complex structures mainly suitable for representing objects and scenes, which is oriented to reduce complex matching and reasoning operations to a simple ones. The cyclic-tree representation is a structure which allows to describe an object by means of a tree which branches and nodes are cyclic. Indeed the cyclic-tree is not a tree, is a graph which is structured as a tree in order to allow doing partial operations in the same way that are done in a tree. In this work, we introduce the cyclic-tree, we show some of the matching operations and the application of this representation for identifying 3D objects in a scene.

This paper describes an industrial vision system which not only recognizes parts but also is capable of performing and controlling a sequence of actions. The system has to control a cell in an assembly system by analyzing images of its environment. It has to recognize parts, evaluate their quality, inspect the environment, and control the placement of the part. This requires the representation of rich task-specific knowledge that can be decomposed into quite different levels of abstraction. The approach to knowledge acquisition is based on a semantic network structure. This paper briefly shows the framework for a homogeneous knowledge representation. After a description of the main features of the knowledge representation language and the analysis process a more detailed discussion of the knowledge acquisition component will follow. At last powerful methods for image processing are presented. The whole system is realized in C under the UNIX operating system.

High amount of data on digital images require data structures which allow the access to different resolutions of one image. Image pyramids meet this requirement. The geometry of two corresponding pyramids containing grey levels on the one hand and curves on the other hand is defined. The generation of curve information from a grey level image is described. The grey level pyramid is built using numeric reduction functions, in the curve pyramid a syntactic reduction function is used. The interaction between the grey level pyramid and symbolic information contained in the corresponding curve pyramid is described. A comparison between standard pyramid schemes and our method leads to better results on noise reduction and edge preserving using the methods described in this paper.

A system for the recognition of 3-D solid objects from single graylevel images is described. Models of the objects to be recognized are generated using a commercial CAD-System. Vertices and edges are extracted from the graylevel image by edge finding, curve segmentation and junction labeling. Model and object representation are based on attributed graphs.

Object recognition is achieved by a two stage procedure. First, hypotheses are generated based on a subgraph isomorphism detection. Next, hypothesis verification through geometric projection is carried out. It will be shown that the algorithms of both stages together have a time complexity of O(n²) for objects which can be represented by connected graphs. This result will be experimentally verified with generated graphs of prismatic solids, and compared with graphs of real images.

This paper illustrates how feature grouping can improve matching. Obviously feature groups convey more information and therefore are less ambiguous. But still remains the problem of the choice of these groups, how to build them automatically and how to use them in different problems. Partial answers taken from our work and from some others are given here.

Two new methods integrating region growing and edge detection are presented to extract buildings in aerial images. In the domain we are considering, buildings shadows play an important role in enhancing the detection accuracy and reliability. In the first method we start with edge detection then combine the results with region growing in subsequent phases; while in the second method we use segmentation obtained from region growing first then apply the edge detection to enhance the result. The first method can be divided into three phases (1) We use edge detection to locate shadows and thus to confirm the presence of a building since they provide very reliable features with high S/N ratios. (2) In the low-contrast areas where boundary features can not be reliably obtained by edge detection, we use a region growing operator to delineate the boundaries. The “leaking” problem that occurs with applying region growing between two low-contrast regions is effectively solved by using morphological operations with a directional operator related to the light orientation. (3) A beautification phase is used to enhance the delineated contours. The second method can also be divided into three phases. (1) we follow the paradigm of hypothesis then testing on each region of the segmentation. Two features, shadow and contour shape, are used to verify the hypotheses. (2) To enhance the contours of the detected buildings, we use the shape and edge information to remove artifacts and to modify the contours. (3) The artifacts which can not be improved by local edge information are beautified by a beautification process similar to the one in the first method. Since we combine the best parts of the features obtained by edge detection and region growing to find the shape description of each building, the results turn out to be accurate and reliable.

The analysis of page layouts is an essential part of fully-automatic machine interpretation of images of printed documents. Two control strategies, top-down and bottom-up, have been emphasized in the literature. We describe a global-to-local strategy, in which a sequence of model-refinement steps is executed in an order which is constrained by dependencies among model parameters and which maximizes the statistical support available at each step for inference of the parameters. This promises to be more robust than bottom-up merging methods and more efficient than backtracking top-down methods, while requiring relatively little a priori information. The strategy has been applied to the analysis of isolated columns of printed text whose line spacing and text size vary over a wide range. Columns are partitioned into lines by skew-correction followed by analysis of the horizontal projection profile. Text size and baseline are inferred following a preliminary classification of characters by shape. Performance trials of an experimental implementation are described.

A document image is a bit-map produced by raster-digitizing (scanning) a printed page. It can contain fields of text, equations, tables and figures. This article describes a method to identify the spatial structure of a document image and label various components without using optical character recognition. The segmentation and labeling is done simultaneously using publication specific information. This domain-dependent knowledge is in the form of a page-grammar and is used to describe the relationship between various entity classes or blocks. Lexical and syntax analysis tools such as Lex and Yacc are used to label the segments. A simulated document title page is used to illustrate this approach.

The Hottel- Whillier-Bliss (HWB) equation has been the standard tool for the evaluation of collector thermal performance for four decades. This paper presents a technique that applies the criteria of ASHRAE Standard 93–77 to the determination of the HWB equation coefficients from field-derived data. Results of the analysis of a sample collector array illustrate the technique. Actual dynamic performances of various collector arrays in the field are compared to those predicted by the steady-state efficiency models for the individual panels. In certain cases, the HWB model produces deviations of over 100% from measured hourly performances and 35% from measured monthly performances when compared with the single-panel laboratory-derived model. However, when the field-derived HWB model is used as the basis of comparison the performance deviations were typically less than 5%.

We describe a methodology and associated system for the interpretation of images of engineering drawings based on the exploitation of the Unix tool Yacc. The system is extensible and clearly relates a hypothesis/prediction/verification strategy to a hierarchical model description and the deployment of low level techniques. Examples are given of the interpretation of real mechanical engineering drawings.

The following sections are included:

• Introduction

• From pixels to primitives

• A priori knowledge
  • Dimensions of technical drawings
  • Representation standards
  • Views of a solid object
  • Consistency rules

• Symbol recognition

• Recognition strategies
  • Strategy for one document type
  • Strategy parameterized by the model

• Conclusion

• References

Traditionally, the methods applied in pattern recognition are categorized into statistical (or decision theoretic), structural, and artificial intelligence based approaches. Decision theoretic methods are applied primarily for the purpose of classification. The task in pattern classification is to assign an unknown input pattern to a class out of M classes. An individual pattern is represented by a N-dimensional vector of features. Depending on the way the classes are represented, we distinguish between nonparametric and parametric statistical classification. The most important subclasses of nonparametric and parametric statistical classification are nearest neighbor, or NN, classification, and Bayes-classification, respectively…

The following sections are included:

• Members of the working group

• Introduction

• Line graphics

• Text

• Concluding remarks

The following sections are included:

• Members of the working group

• Introduction

• Inductive versus deductive model construction

• The role of primitives

• Concluding remarks