Search

This paper presents a formalization of the concept of cluster analysis. It begins with an intuitive description of clustering, and discusses the separation of the measurement problem from the clustering problem. It develops the nature of the elements to be clustered, the nature of the possible clusters, and the nature of the clustering results. Particularly significant is the introduction of the attribute of mass of an element. The paper defines a class of functions, called clustering functions, having a certain domain and range and satisfying a certain set of properties, called axioms. It discusses some properties which are inadequate to serve as axioms. Finally, it presents a function which is in the class of clustering functions.

This paper presents some novel results concerning the recognition of single-font printed Chinese characters via the transformation algorithms of Fourier, Hadamard, and Rapid. The new design philosophy of a three-stage structure is believed to offer at least a suboptimal search strategy for recognizing printed Chinese characters with a dictionary of 7000–8000 characters. The transformation algorithms discussed in this paper will be used in the last two stages. Extensive experiments and simulations concerning feature extraction and noisy or abnormal pattern recognition have been carried out (the simulations have been restricted to a 63-character subset called “Radicals”). Comparison has been made of all three transforms according to their ability to recognize characters.

This paper presents the results of research into the development of a semantic-based picture recognition technique. The need for such a technique is reflected in the limitations of syntactic picture recognition techniques, which are discussed in detail. The motivation for developing a semantic-based technique arises from a few intuitive notions described in the paper. A paradigm for semantic picture recognition is realized in the development of a general procedure which makes explicit use of contextual information and bases recognition on intensional class descriptions.

Pavlidis in his “analysis of set patterns” proposed three size-oriented similarity measures. In this paper, shape-oriented similarity and dissimilarity measures of triangles and polygons are proposed and investigated. There are three advantages of shape-oriented similarity measures. First, two polygons may have the same shape but differ in area and dimensions and still be similar. Second, shape-oriented similarity and dissimilarity measures can be normalized between zero and one. Third, shape-oriented similarity measures are invariant with respect to rotation, translation, or expansion or contraction in size. The “rubber-mask” technique proposed by Widrow utilized length and width parameters in the classification of chromosomes. In this paper, chromosome images are classified through the use of angular and dimensional proximity measures which are in terms of angle and length parameters. The results obtained in this paper may contribute to processing a picture from the polygonal approximation stage to the final filtering stage in order to recognize or classify a picture.

A general description of an optical character recognition system is given. Major problems encountered by each of the system units are described, and some common solutions are given. No new work is described or proposed. This paper presents a general review of character recognition techniques and problems for people not intimately acquainted with this field. It will give perspective to more detailed papers on character recognition, as well as to the more general field of pattern recognition.

In this paper, some problems related to the recognition of plane, two-tone pictures (e.g. handprinted characters) are considered. It is assumed that suitable algorithms (already described) have been applied to the original picture, in order to obtain linearwise, two-tone figures. A problem that arises at this point is classifying these results in a suitable way; to this purpose, it is necessary to define and perform a set of measurements such that the results obtained by applying them to figures of the same class be the same, the possible ambiguity be minimal and the loss of information be as reduced as possible. In this paper, some algorithms are described that transform the figure into another one of the least possible dimensions, but retaining a set of basic topological and quasi-topological characteristics of the original picture. While implicitly defining a set of measurements to be performed, the “reduction” of the figure is implemented so that several figures having the same basic characteristics give the same “reduced” figure as final result. The considerable reduction of the figure's dimensions may furthermore make the recognition simpler. Several algorithms are described, and the results are compared; all are of parallel type, and therefore particularly suited for hardware implementation.

Within the descriptive approach to pattern analysis and recognition, this paper argues for the need to distinguish between syntax-controlled and syntax-aided recognition schemes. The fundamental importance of recognition schemes based on syntax-aided learning is discussed. The main part of the paper describes some exploratory work undertaken to study operationally viable structures for syntax-aided learning in the context of handprinted letter recognition. The results of two experiments in recognition performed, using a syntax-aided (nonlearning) scheme. are given. Specific studies in learning suggested by this recognition scheme are discussed.

A 3-day Symposium on Automatic Photointerpretation was held in Washington, D.C., U.S.A. in the summer of 1967. Thirty technical papers were presented at the meeting. Although the research has been done independently in widely diverse disciplines, the basic methods used in pictorial pattern recognition are similar. Based on this unified point of view, the contents of the papers are abstracted and summarized in six sections: Picture Digitization; Picture Preprocessing; Feature Extraction; Data Editing; Pattern Recognition; and Picture Data Measurement.

This paper describes an interactive graphics system which is being used in the solution of both pattern recognition and pattern analysis problems. The paper concentrates on a pattern analysis subsystem of the larger On-Line Pattern Analysis and Recognition System (OLPARS), although its relationship to the larger system is discussed. The basic algorithm underlying the subsystem is a non-linear mapping of high dimensional data to a two- or three-dimensional space. Several graphic interactive options are explained along with example applications in the design of a system for the classification of hand printed characters.

This paper briefly summarizes much of the work in pattern recognition to date, and relates the rubber mask technique to previous work. A scheme for incorporating flexible-mask methods into a proposed pattern recognition and memory system is presented. A discussion based on some facts and on some conjecture of the human eye/brain system and how it recognizes patterns, possibly by flexible matching, is also presented.

The advent of new stains for chromosomes has increased the possibility of implementing useful automated chromosome analysis. The case with which chromosomes can now be recognized makes it possible to perform detailed statistical analysis of the chromosomes of an individual. This paper describes methods for assembling chromosome information from several cells in such a way that accidental variations due to preparation, etc. can be eliminated and an undistorted set of characteristics of the chromosome complement can be established. This set of characteristics can then be compared with various references, and statements can be made concerning the relationships between variations in the chromosome complement and genetic traits. These same methods can be employed in multiple-cell karyotyping to circumvent the classical problem of touching and overlapping chromosomes. The methods also allow one to achieve very reliable descriptions of the chromosome complement. The importance of appropriate descriptors of the chromosomes is illustrated.

For use in hand-printed character recognition, this paper introduces a method of binarization that can cope with quite large and abrupt changes of the grey levels of black and white. The binarizing threshold is a piece-wise linear function of a local maximum white level, and this function is conveniently implemented by means of associative addressing.

During production, storage and shipment, a crop of feed grain is often contaminated with admixtures of other grains or foreign material. Failure to meet the contractural limits of purity can result in monetary penalties or may prevent completion of the sales transaction. Presently, purity is established by human inspectors. They subject a carefully selected sample to 100 per cent visual inspection. This paper describes part of the development of a high speed, automatic sorting and grading procedure. A recursive learning pattern classification scheme is described which yields an overall accuracy of about 98 per cent.

The sample mean and sample covariance matrix are unbiased and consistent estimates of population mean and covariance matrix only if the samples are independent. In practical applications of Bayes' procedure these estimates are used in place of population means and covariance matrices on the assumption of independence among the training samples. This practice has often given, especially in remote sensing data analysis, misclassification probabilities much higher than that can be accounted for theoretically. The reason may be that the assumption of independence may not be valid. In reality, the samples are rarely independent, they are rather dependent, at best equicorrelated. This paper investigates how such intraclass correlation among the training samples affects the misclassification probabilities of the Bayes' procedure.

The purpose of the glossary is to state in the simplest possible way the general meaning or word usage for many of the terms in image pattern recognition. There is no intent to provide definitive statements for terms such as “resolution” but rather only statements about the general nature of what resolution is. There is no intent to provide mathematical formulas involving integrals or derivatives in any of the statements. Those who need the mathematics can get it from technical papers or texts. The glossary is designed to be read by those generally unfamiliar with the area and provide for them an overall perspective. The organization approaches that of programmed learning material and can be smoothly (I hope) read from beginning to end. Those needing to look up a specific term can do so via the index. There is some overlap of terms in this glossary with those glossaries or definitions in radiometry and aerial photography. There is no intent that the way the terms are described here replace the way they are described in those glossaries and definitions. The overlap is provided here so that the reader can get a perspective of a cluster of terms frequently used in our field. The perspective is intended to start from what the image concept is through the recording of an image by some sensor, the possible conversion of image format and the simple analog or more complex digital processing which must be done on the imagery. In short, the perspective is one of image pattern recognition.

This paper presents a mathematical model of a nonsupervised two-category classifier with a nonparametric learning method by using the first principal component. On the assumptions that the patterns of each category are clustered and that the mean point of all patterns used lies between the two clusters, the separating hyperplane contains the mean pattern point and is perpendicular to the line governed by the first principal component. The learning algorithm for obtaining the mean pattern vector and the first principal component is described, and also some experimental results on random patterns are presented.

In this paper, we shall show the following experimental results: (1) the one-dimensional clustering algorithm advocated by Slagle and Lee (1) can be generalized to the n -dimensional case, n > 1: (2) if a set of points in some n -space ( n > 1) are linearly ordered through the short spanning path algorithm, then this set of points can be considered as occupying a one-dimensional space and the original n -dimensional clustering problem can now be viewed as a one-dimensional clustering problem; (3) a short spanning path usually contains as much information as a minimal spanning tree; (4) the one-dimensional clustering algorithm can be used to find the long links in a short spanning path or a minimal spanning tree. These long links have to be broken to obtain clusters.

After surveying existing feature selection procedures based upon the Karhunen-Loeve (K-L) expansion, the paper describes a new K-L technique that overcomes some of the limitations of the earlier procedures. The new method takes into account information on both the class variances and means, but lays particular emphasis on the classification potential of the latter. The results of a series of experiments concerned with the classification of real vector-electrocardiogram and artificially generated data demonstrate the advantages of the new method. They suggest that it is particularly useful for pattern recognition when combined with classification procedures based upon discriminant functions obtained by recursive least squares analysis.

Algorithms which are operationally efficient and which give a good partition of a finite set, produce solutions that are not necessarily optimum. The main aim of this paper is a synthetical study of properties of optimality in spaces formed by partitions of a finite set. We formalize and take for a model of that study a family of particularly efficient technics of “clusters centers” type. The proposed algorithm operates on groups of points or “kernels” these kernels adapt and evolve into interesting clusters. After having developed the notion of “strong” and “weak” patterns, and the computer aspects, we illustrate the different results by an artificial example and by two applications: one in mineral geology, the other in medicine to determine biological profiles.

“Linguistic” techniques have been developed for well-formed linear strings. This paper describes several extensions of standard linguistic recognizers, to give flexibility in handling loosely connected, noisy, messy patterns.

This paper describes a picture-processing system that was first developed to locate ridge-endings in a fingerprint, but has since been expanded to solve a number of other picture-processing problems. The system extracts from a picture contour a set of features or nodes which are then tied together in a bidirectional list structure. Having the information in this form simplifies elimination of noise. The method used for establishing the list structures provides a convenient means for the performance of summing operations such as accumulation of area or calculation of moments of the picture surface.

The FIDAC is a high-speed flying-spot scanner for on-line input of digitized pictorial data into a computer's core memory. This paper describes the design of the FIDAC instrument, from original basic requirements to ultimate physical realization. The essential basic circuitry and the mechanical and optical systems of the FIDAC MOD I are described. The problems of achieving dynamic focus, light uniformity, and positional accuracy are discussed, and the methods used to solve these problems are given. The modifications incorporated into a later model, the FIDAC MOD II with a selective scan under computer control, are then described.

Figures of arbitrary shape (not necessarily “thin line”) can be approximated by polygons which are represented as unions of some of their convex subsets. Such representations can be considered as graphs whose nodes correspond to convex subsets and whose branches connect nodes corresponding to intersecting subsets. The nodes of such graphs are labeled with information related to the structure of the convex set they represent. The paper discusses various properties of such graphs including grammars which may generate them. It is also shown that their analysis can provide information about topological properties of the figure and its shape in general.

This paper studies M-way automata as a method of defining patterns in a multidimensional discrete space. It is shown that the membership question is recursively solvable for large classes of automata while the emptiness question is r, unsolvable even for the class of M-way finite automata. Efficient recognition algorithms are given for the pattern sets defined by M-way pushdown automata and certain error operators designed to make a set of patterns insensitive to noise are also presented and studied.

The paper includes theoretical foundation of the design of a learning multiclass pattern classifier based on adaptive threshold gates. The conclusions and applicability of such a classifier are illustrated with a small adjustable multiclass classifier called AMOS.

Chemical data can be automatically classified into useful chemical categories by computerized learning machines using adaptive pattern dichotomizers. Previous investigations have employed negative, error correction feedback procedures to train the two-class pattern categorizers. This paper reports a new method based on an iterative least squares procedure developed for obtaining the discriminant functions used by the pattern dichotomizers. The iterative least squares method is discussed in detail, and its application to the training of decision makers to classify low resolution mass spectra is demonstrated. It is shown that pattern dichotomizers trained with the method can obtain predictive abilities of 98% in classifying unknown low resolution mass spectra into useful chemical categories.

Sensing, feature extraction, optimum decision, parameter estimation, adaptation and learning are the major problems in the design of pattern recognition systems. This paper discusses the selection of mathematical features on the basis of entropy minimization and introduces the concept of extracting statistical features by the method of kernel approximation.

The paper discusses an adaptive pattern recognition program that learns to recognize coded line drawings, and to describe the structure of the pattern by giving the hierarchical organization of its subparts, and the spatial relationships between them. Emphasis is on mechanisms that allow learning (directed by feedback from a human trainer), and on the methods of abstracting, storing, and retrieving chunks of graphic information for use in subsequent pattern recognition and description. Some similarities to the perceptual process in humans are noted.

This paper describes methods for extracting pattern-synthesizing features. A set of patterns is expressed as a Boolean matrix, allowing the problem of feature extraction to be viewed as one of factoring this matrix. Feature extraction methods based on matrix factorization and pattern intersection are presented. Attribute inclusion is defined to be the implication of the presence of one attribute by that of another, and an algorithm for obtaining features correlated by inclusion is discussed.

One way to compare clustering techniques is in terms of the part done by the computer and the part controlled by the user. This paper presents a mathematical formulation of the clustering problem in which no parameters to be controlled by the user are included, thus no outside interference is required. The model was applied to clustering data points defined in a multi-dimentional space. The experiments demonstrate that the partition depends mainly upon the structure inherent in the data set. This approach is particularly useful in the case where no preliminary information, as to the number of categories or their distribution, is available.

A statistical measure of similarity distinct from a measure of association is introduced. By this measure two things are highly similar, if and only if their respective associations with all other things are the same. In this paper, measures of association and similarity are combined to perform a cluster analysis of variables concerned with behavioral problems of deaf children. The four major clusters which emerge are identified as characteristics of anxiety, hot temperedness, inattentiveness, and social withdrawal. The clusters obtained by the combined measures are compared with the clusters obtained by each measure alone.

This paper considers unsupervised learning, structure and parameter adaptive binary pattern recognition when a nongaussian pattern is observed in gaussian noise. Different schemes, none of which require growing or infinite memory, are suggested. To facilitate feasible solutions, certain judicious approximations are made use of. Two examples are presented to demonstrate the learning capability of the proposed algorithms.

This paper introduces an algorithm for the automatic inspection of X-ray photographs. This algorithm is applicable to nonautomatic welding, and it does not require any treatment for taking X-ray photographs. The algorithm consists of two steps. Step A extracts parameters of welding and is required only once for each kind of welding. In step B, the boundaries of the welding part are at first determined, then each raster point is classified into a normal or an abnormal point, using the Q value of the point. The results of experiments with an X-ray photograph of the butt weld of a boiler on the HITAC 5020E is satisfactory.

In recent years a number of methods have been suggested which attempt to solve the Pattern Recognition Problem using a so-called linguistic approach. A given image is represented though primitives (or signs) and the classifications are decided on the basis of the occurrence of certain primitives and their interrelation. This paper deals with the development of such a method. In the present study we consider halfplanes as primitives. Their intersections form convex polygons and the unions of the latter are arbitrary polygons. These can be then considered as approximations for arbitrary plane figures, like letters of the alphabet, drawings, etc. In the application of the method the image is prefiltered and then approximated by a polygon with sides parallel to specific directions. This determines the primitives which are present and then through a well-defined procedure the “syntax” of the figure is determined, i.e. which are the (unique) convex polygons whose union forms the figure. From that representation one can proceed in a number of different directions by using various classification techniques.

This paper discusses a recognition processing between patterns represented by N points in R 2 . As the processing is founded on the comparison of “ordonnances” obtained by ordering the Euclidian distances between the N points, it does not depend on either translation, rotation or homothety and also allows up to 10 per cent distortion. Experimental results are presented.

The paper discusses the idea of iterating the conversion of a continuous-tone picture from binary to Gray code representation. A simple recursive function is defined by means of which the value of the ith bit representing a picture point's grey level after the mth iteration is determined. The resulting rearrangement of grey levels as well as that of the bits throughout the planes is discussed next. The iteration is shown to repeat after 2″ steps, where n is the number of bit planes representing the picture. A data compression scheme is developed on the basis that prior to exact repetition, approximate repetitions take place during the iterations, and the resulting picture is almost the same as the original.

In this paper a few of the techniques that can be used to produce spatial filters for coherent or incoherent optical data-processing systems are discussed. Some experimental results of using a coherent optical system and spatial filters generated with a digital computer are given.

The key elements in coherent optical processors are the spatial filters. To realize the full potential of coherent processors much work should be devoted to the synthesis of and the production techniques for them. In this paper, some recent work on filters synthesis will be summarized, and the implications in optical computation, image processing (enhancement), image restoration (deblurring) and image detection examined. In addition, some advances on the production techniques for the spatial filters will be briefly reviewed. This would include the extension of Vander Lugt's filters to the multiply-exposed filters, the binary filters, the phase only filters, and the introduction of nonlinear filters.

Color is one of the important properties of objects. This paper introduces an algorithm to perceive color and demonstrates its application to visual perception. Input data are the light intensities of three images of a single scene through red, green and blue filters. From this information, the color ( r. g. b ) of each point is determined and regions which have uniform color are extracted. As final results, the number of objects in the scene and the color, shape, size and position of each object are obtained.

This paper is concerned with the synthesis of networks of threshold elements to separate patterns into two classes. There exist many algorithms which determine the parameters of a classifier, when the two classes are linearly separable. But a large number of problems do not fulfill this requirement. In such cases it is necessary to generate nonlinear decision boundaries to separate the patterns.

The theme of this paper is a linguistic approach to the problem of pictorial pattern recognition. Instead of the vocabulary of primitives and grammar being selected by the designer, this new pattern-recognition system is able to make a new description, give the vocabulary, and construct the grammar. The vocabulary consists in two kinds of words, “forms” of characteristic fragments of pictorial patterns (images) and “locations” of these fragments. The enumeration of the forms and locations describes a pattern. The general scheme of the process of forming the language, the ways of extracting the characteristic fragments, the vectors (sentences) connecting “forms” and “location”, and the algorithms for constructing and comparing the image descriptions are described. Simulation of forming a description language and analysis of various forms are presented.

In some cases it is possible to radically modify the character of an optical system to make it highly compatible with image processing. One such case is discussed in this paper. A large-aperture optical system may be operated as a multi-element interferometer such that a posteriori image processing can yield images that are free from the usual distortions of atmospheric “seeing”. Most significantly, the image corrections can be accomplished without any knowledge of the point-spread function of the atmosphere.