Structural information about a document is essential for structured query processing, indexing, and retrieval. A document page can be partitioned into a hierarchy of homogeneous regions such as columns, paragraphs, etc.; these regions are called physical components, and define the physical layout of the page. In this paper we develop a class of models for the physical layouts of technical paper title pages. We model physical layout using hidden semiMarkov models for directional projections of page regions, and a stochastic attributed K-d tree grammar model for the 2D hierarchical structure of these regions. We use the models to generate sets of synthetic title page images of three distinctive styles, which we use in controlled experiments on page structure analysis.

An accurate optical flow estimation algorithm is proposed in this paper. By combining the three-dimensional (3D) structure tensor with a parametric flow model, the optical flow estimation problem is converted to a generalized eigenvalue problem. The optical flow can be accurately estimated from the generalized eigenvectors. The confidence measure derived from the generalized eigenvalues is used to adaptively adjust the coherent motion region to further improve the accuracy. Experiments using both synthetic sequences with ground truth and real sequences illustrate our method. Comparisons with classical and recently published methods are also given to demonstrate the accuracy of our algorithm.

A multi-scale algorithm using wavelet decomposition is proposed to estimate dense optical flow using only two frames. Hierarchical image representation by wavelet decomposition is used to exploit the assumption of local rigid motion in a new multi-scale framework. It is shown that if a wavelet basis with one vanishing moment is carefully selected, we can get hierarchical images, edges, and comers from the wavelet decomposition. Based on this result, all the components of the wavelet decomposition are used to estimate relatively accurate optical flow even under the inadequate image sampling condition, and overcome the “flattening-out” problem in traditional pyramid methods, which produce high errors when low-texture regions become flat at coarse levels due to blurring. Local affine transforms are also used to speed up flow estimation. Experiments on different types of image sequences together with quantitative and qualitative comparisons with several other optical flow methods are given to demonstrate the effectiveness and robustness of our algorithm.

This paper describes technology and tools for intelligent human-computer interaction (IHCI) in which human cognitive, perceptual, motor and affective factors are modeled and used to adapt the H-C interface. IHCI emphasizes that human behavior encompasses both apparent human behavior and the hidden mental state behind behavioral performance. IHCI expands on the interpretation of human activities, known as W4 (what, where, when, who). While W4 only addresses the apparent perceptual aspect of human behavior the W5+ technology for IHCI described in this paper addresses also the why and how questions, whose solution requires recognizing specific cognitive states. IHCI integrates parsing and interpretation of nonverbal information with a computational cognitive model of the user which, in turn, feeds into processes that adapt the interface to enhance operator performance and provide for rational decision-making. The technology proposed is based on a general four-stage interactive framework, which moves from parsing the raw sensory-motor input, to interpreting the user's motions and emotions, to building an understanding of the user's current cognitive state. It then diagnoses various problems in the situation and adapts the interface appropriately. The interactive component of the system improves processing at each stage. Examples of perceptual, behavioral, and cognitive tools are described throughout the paper Adaptive and intelligent HCI are important for novel applications of computing, including ubiquitous and human-centered computing.

We propose an approach to accurately detecting two-dimensional (2-D) shapes. The cross section of the shape boundary is modeled as a step function. We first derive a one-dimensional (1-D) optimal step edge operator, which minimizes both the noise power and the mean squared error between the input and the filter output. This operator is found to be the derivative of the double exponential (DODE) function, originally derived by Ben-Arie and Rao. We define an operator for shape detection by extending the DODE filter along the shape's boundary contour. The responses are accumulated at the centroid of the operator to estimate the likelihood of the presence of the given shape. This method of detecting a shape is in fact a natural extension of the task of edge detection at the pixel level to the problem of global contour detection. This simple filtering scheme also provides a tool for a systematic analysis of edge-based shape detection. We investigate how the error is propagated by the shape geometry. We have found that, under general assumptions, the operator is locally linear at the peak of the response. We compute the expected shape of the response and derive some of its statistical properties. This enables us to predict both its localization and detection performance and adjust its parameters according to imaging conditions and given performance specifications. Applications to the problem of vehicle detection in aerial images, human facial feature detection, and contour tracking in video are presented.

We present a comprehensive treatment of 3D object tracking by posing it as a nonlinear state estimation problem. The measurements are derived using the outputs of shape-encoded filters. The nonlinear state estimation is performed by solving the Zakai equation, and we use the branching particle propagation method for computing the solution. The unnormalized conditional density for the solution to the Zakai equation is realized by the weight of the particle. We first sample a set of particles approximating the initial distribution of the state vector conditioned on the observations, where each particle encodes the set of geometric parameters of the object. The weight of the particle represents geometric and temporal fit, which is computed bottom-up from the raw image using a shape-encoded filter. The particles branch so that the mean number of offspring is proportional to the weight. Time update is handled by employing a second-order motion model, combined with local stochastic search to minimize the prediction error. The prediction adjustment suggested by system identification theory is empirically verified to contribute to global stability. The amount of diffusion is effectively adjusted using a Kalman updating of the covariance matrix. WE have successfully applied this method to human head tracking, where we estimate head motion and compute structure using simple head and facial feature models.

We present an approach to tracking human activities in a monocular video. We model the human body by decomposing it into torso and limbs and use simple 3D shapes to approximate them. The limb motions are parametrized by the relative joint angles. The problems of motion tracking and estimation are posed as nonlinear state estimation problems. The measurements are computed using the outputs of 3D shape-encoded filters which extract the boundary gradient information of the body image. The uncertainties of body pose are propagated by a branching particle system. We first sample a set of particles approximating the initial distribution of the state vector conditioned on observations, where each particle encodes the body pose. The posterior density is realized by the weight of the particle, where the weight represents geometric and temporal fit, and computed bottom-up from the raw image using a shape-encoded filter. The particles branch so that the mean number of offspring is proportional to the weight. Applications to both synthetic and real video sequences show the effectiveness of this approach.

Signatures may be stylish or unconventional and have many personal characteristics that are challenging to reproduce by anyone other than the original author. For this reason, signatures are used and accepted as proof of authorship or consent on personal checks, credit purchases and legal documents. Currently signatures are verified only informally in many environments, but the rapid development of computer technology has stimulated great interest in research on automated signature verification and forgery detection. In this paper, we focus on forgery detection of offline signatures. Although a great deal of work has been done on offline signature verification over the past two decades, the field is not as mature as online verification. Temporal information used in online verification is not available offline and the subtle details necessary for offline verification are embedded at the stroke level and are hard to recover robustly. We approach the offline problem by establishing a local correspondence between a model and a questioned signature. The questioned signature is segmented into consecutive stroke segments that are matched to the stroke segments of the model. The cost of the match is determined by comparing a set of geometric properties of the corresponding substrokes and computing a weighted sum of the property value differences. The least invariant features of the least invariant substrokes are given the biggest weights, thus emphasizing features that are highly writer-dependent. Random forgeries are detected when a good correspondence cannot be found, i.e. the process of making the correspondence yields a high cost. Many simple forgeries can also be identified in this way. The threshold for making these decisions is determined by a Gaussian statistical model. Using the local correspondence between the model and a questioned signature, we perform skilled forgery detection by examining the writer-dependent information embedded at the substroke level and try to capture unballistic motion and tremor information in each stroke segment, rather than as global statistics. Experiments on random, simple and skilled forgery detection are presented.

We present a new approach for accurate detection of two-dimensional shapes. We first derive an optimal smoothing filter, which minimizes both the noise power and the mean squared error between the input and the filter output. This operator is found to be a derivative of the double exponential (DODE) function. We define an operator for shape detection by extending the DODE filter along the shape's boundary contour. We find that this filtering scheme is equivalent to integrating gradients along the hypothetical shape boundary, but our method turns out to be more robust than conventional edge detection followed by edge grouping. This approach also provides a tool for a systematic analysis of edge-based shape detection. We investigate how the error is propagated by the shape geometry. This enables us to predict both its localization and detection performance. Application to vehicle detection in aerial images and human facial feature detection are provided.

If we histogram the normal flow vectors in images of a scene viewed by a moving observer, we can use the time-varying histogram to derive qualitative information about the observer's motion-for example, whether it is (primarily) translational or rotational, and whether the direction of translation or axis of rotation is (roughly) parallel or perpendicular to the camera axis. This is illustrated using flow histogram obtained from a variety of real image sequences.

Research has been active in the field of forgery detection, but relatively little work has been done on the detection of skilled forgeries. We present an algorithm for detecting skilled forgeries based on a local correspondence between a questioned signature and a model obtained a priori. Writer-dependent properties are measured at the substroke level and a cost function is trained for each writer. When a candidate signature is presented, the same features are extracted and matched against the model. We present a description of the features and experimental results.

A new method of finding people in video images is presented. The detection is based on a novel background modeling and subtraction approach which uses both color and edge information. We introduce confidence maps gray-scale images whose intensity is a function of confidence that a pixel has changed - to fuse intermediate results and represent the results of background subtraction. The latter is used to delineate a person's body by guiding contour collection to segment the person from the background. The method is tolerant to scene clutter, slow illumination changes, and camera noise, and runs in near real time on a standard platform.

Classical digital geometry deals with sets of cubical voxels (or square pixels) that can share faces, edges, or vertices, but basic parts of digital geometry can be generalized to sets S of convex voxels (or pixels) that can have arbitrary intersections. In particular, it can be shown that if each voxel P of S has only finitely many neighbors (voxels of S that intersect P), and if any nonempty intersection of neighbors of P intersects P, then the neighborhood N(P) of every voxel P is simply connected and without cavities, and if the topology of N(P) does not change when P is deleted (i.e., P is a “simple” voxel), then deletion of P does not change the topology of S.

Laplacian operators used in the literature for digital image processing are not rotationally invariant. We examine the anisotropy of 3 x 3 Laplacian operators for images quantized in square pixels, and find the operator which has the minimum overall anisotropy.

Many types of common objects, such as tools and vehicles, usually move in simple ways when they are wielded or driven. The natural axes of the object tend to remain aligned with the local trihedron defined by the object's trajectory. Based on this observation we use a model called Frenet-Serret motion which corresponds to the motion of a moving trihedron along a space curve. Knowing how the Frenet-Serret frame is changing relative to the observer gives us essential information for understanding the object's motion. This is illustrated here for four examples, involving tools (a wrench and a saw) and vehicles (an accelerating van, a turning taxi).

A set P of nondegenerate convex polygons P in R 2 , or polyhedra P in R 3 , will be called normal if the intersection of any two of the P s of P is a face (in the case of polyhedra), an edge, a vertex or empty. P is called strongly normal (SN) if it is normal and, for all P , P 1 , …, P n , if each P i intersects P and I = P 1 ∩⋯∩ P n is nonempty, then I intersects P . The union of the P i ∈ P that intersect P ∈ P is called the neighborhood of P in P , and is denoted by N P ( P ). We prove that P is SN iff for any P ′ ⊆ P and P ∈ P ′, N P ′ ( P ) is simply connected. Thus SN characterizes sets P of polyhedra (or polygons) in which the neighborhood of any polyhedron, relative to any subset P ′ of P , is simply connected. Tessellations of R 2 or R 3 into convex polygons or polyhedra are normal, but they may not be SN; for example, the square and hexagonal regular tessellations of R 2 are SN, but the triangular regular tessellation is not.

Most previous theoretical work on motion planning for a group of robots has addressed the problem of path planning for the individual robots sequentially, in geometrically simple regions of Euclidean space (e.g. a planar region containing polygonal obstacles). In this paper, we define a version of the motion-planning problem in which the robots move simultaneously. We establish conditions under which a team of robots having a particular configuration can move from any start location to any goal destination in a graph-structured space. We show that, for a group of robots that maintain a fixed formation, we can find the "shortest" path in polynomial time, and we give faster algorithms for special kinds of environments.

The purpose of a document is to facilitate the transfer of information from its author to its readers. It is the author's job to design the document so that the information it contains can be interpreted accurately and efficiently. To do this, the author can make use of a set of stylistic tools. In this paper, we introduce the concept of document functionality, which attempts to describe the roles of documents and their components in the process of transferring information. A functional description of a document provides insight into the type of the document, into its intended uses, and into strategies for automatic document interpretation and retrieval. To demonstrate these ideas, we define a taxonomy of functional document components and show how functional descriptions can be used to reverse-engineer the intentions of the author, to navigate in document space, and to provide important contextual information to aid in interpretation.

Progress on the problem of signature verification has advanced more rapidly in online applications than offline applications, in part because information which can easily be recorded in online environments, such as pen position and velocity, is lost in static offline data. In offline applications, valuable information which can be used to discriminate between genuine and forged signatures is embedded at the stroke level. We present an approach to segmenting strokes into stylistically meaningful segments and establish a local correspondence between a questioned signature and a reference signature to enable the analysis and comparison of stroke features. Questioned signatures which do not conform to the reference signature are identified as random forgeries. Most simple forgeries can also be identified, as they do not conform to the reference signature's invariant properties such as connections between letters. Since we have access to both local and global information, our approach also shows promise for extension to the identification of skilled forgeries.

Spatially quantized approximations of the Laplacian used in digital image processing are not rotationally invariant. We examine the anisotropy of 3/spl times/3 Laplacian operators for images quantized in square pixels, and derive, from optimizing criteria, the operator which has the minimum overall anisotropy.

Automatic target recognition (ATR) generally refers to the autonomous or aided target detection and recognition by computer processing of data from a variety of sensors such as forward looking infrared (FLIR), synthetic aperture radar(SAR), inverse synthetic aperture radar (ISAR), laser radar (LADAR), millimeter wave (MMW) radar, multispectral/hyperspectral sensors, low-light television (LLTV), video, ete. It is an extremely important capability for targeting and surveillance missions of defense weapon systems operating from a variety of platforms.

Work has recently begun on a joint project between the Universities of Maryland and Oulu on the development of a system for Intelligent Document Image Retrieval (IDIR). The IDIR system will provide close connections with and utilization of document analysis and image processing techniques, advanced computing and networking, and modern approaches to database management. The system design consists of aggressively modularized components to enhance the development of individual parts which are used in the complete solution, including: Interface specifications, multipurpose feature extraction, an integrated efficient query language, physical retrieval from an object-oriented database, and delivery of retrieved objects. In this paper, we introduce the general framework, feature extraction modules, query capabilities, a graphical query interface, and the application interface. We demonstrate each component of the system and how the query mechanisms can be used to handle both content and struc...

Optimization processes based on "active models" play central roles in many areas of computational vision as well as computational geometry. However, current models usually require highly complex and sophisticated mathematical machinery and at the same time they also suffer from a number of limitations which impose restrictions on their applicability. In this paper a simple class of discrete active models, called migration processes, is presented. The processes are based on iterated averaging over neighborhoods defined by constant geodesic distance. It is demonstrated that the migration process model combines a number of advantages of different active models. The processes can be applied to derive natural solutions to a variety of optimization problems which include: defining (minimal) surface patches given their boundary curves; finding shortest paths joining set of points; and decomposing objects into "primitive" parts.

This paper treats the problem of detecting straight or circular pieces of road in noisy aerial images. It first uses a local nonlinear operator to detect pixels whose neighborhoods are line-like, and then applies (robust) estimation techniques to find sets of such pixels that lie on, or near straight or circular loci. An (unbiased) ordinary least squares estimator cannot handle outlying data; on the other hand, conventional robust techniques for fitting circular arcs are severely affected by digitization effects and the fact that road circular segments are typically short and shallow. We therefore introduce an estimator that is both robust and statistically efficient.

A robotic agent operating in an unknown and complex environment may employ a search strategy of some kind to perform a navigational task such as reaching a given goal. In the process of performing the task, the agent can attempt to discover characteristics of its environment that enable it to choose a more efficient search strategy for that environment. If the agent is able to do this, we can say that it has "learned to navigate" — i.e., to improve its navigational performance. This paper describes how an agent can learn to improve its goal-finding performance in a class of discrete spaces, represented by graphs embedded in the plane. We compare several basic search strategies on two different classes of "random" graphs and show how information collected during the traversal of a graph can be used to classify the graph, thus allowing the agent to choose the search strategy best suited for that graph.

We present an approach to function-based object recognition that reasons about the functionality of an object's initiative parts. We extend the popular "recognition by parts" shape recognition framework to support "recognition, by functional parts", by combining a set of functional primitives and their relations with a set of abstract volumetric shape primitives and their relations. Previous approaches have relied on more global object features, often ignoring the problem of object segmentation, and thereby restricting themselves to range images of unoccluded scenes. We show how these shape primitives and relations can be easily recovered from superquadric ellipsoids which, in turn, can be recovered from either range or intensity images of occluded scenes. Furthermore, the proposed framework supports both unexpected (bottom-up) object recognition and expected (top-down) object recognition. We demonstrate the approach on, a simple domain by recognizing a restricted class of hand-tools from 2-D images.>

An algorithm for fusing monocular and stereo cues to get robust estimates of both motion and structure is presented. The authors' algorithm assumes the motion to be along a smooth trajectory and the sequence of images to be dense. The algorithm starts by calculating the instantaneous FOE (focus of expansion). Knowing the FOE, a MAP estimate of the displacement at each pixel and an associated confidence measure are calculated. Using the displacement estimates, a relative depth map is calculated from one of the two frame sequences. By calculating the disparities at some feature points and using information about their relative depths, the instantaneous component of velocity in the direction perpendicular to the image plane (the Z direction) is computed. Using this information, a depth map is calculated; this depth map is then used to derive a prior probability distribution for disparity that is used in matching the two frames of the stereo pairs. This method is used to estimate the disparity of each pixel independently. Experimental results on a real image sequence are given.>

A new model, Frenet-Serret motion, is proposed for the motion of an observer in a stationary environment. This model relates the motion parameters of the observer to the curvature and torsion of the path along which the observer moves. Screw-motion equations for Frenet-Serret motion are derived and employed for geometrical analysis of the motion. Normal flow is used to derive constraints on the rotational and translational velocity of the observer and to compute egomotion by intersecting these constraints in the manner proposed by Z. Duric/spl acute/ and Y. Aloimonos (1989). The accuracy of egomotion estimation is analyzed for different combinations of observer motion and feature distance. The authors explain the advantages of controlling feature distance to analyze egomotion and derive the constraints on depth which make either rotation or translation dominant in the perceived normal flow field. The results of experiments on real image sequences are presented.>

An overview of an approach to the generic modeling and processing of known forms is presented. The system provides a methodology by which models are generated from regions in the document based on their usage. Automatic extraction of an optimal set of features to be used for registration is proposed, and it is shown how specialized detectors can be designed for each feature based on their position, orientation and width properties. Registration of the form with the model is accomplished using probing to establish correspondence. Form components which are corrupted by markings are detected and isolated, the intersections are interpreted and the properties of the non-form markings are used to reconstruct the strokes through the intersections. The feasibility of these ideas is demonstrated through an implementation of key components of the system.>

A taxonomy of local, regional, and global temporal clues that, along with a detailed examination of the document, allow temporal properties to be recovered from the image is provided. It is shown that this system will benefit from obtaining a comprehensive understanding of the handwriting signal and that it requires a detailed analysis of stroke and sub-stroke properties. It is suggested that this task requires breaking away from traditional thresholding and thinning techniques, and a framework for such analysis is presented. It is shown how the temporal clues can reliably be extracted from this framework and how many of the seemingly ambiguous situations can be resolved by the derived clues and knowledge of the writing process.>

The robust least-median-of-squares (LMedS) estimator, which can recover a model representing only half the data points, was recently introduced in computer vision. Image data, however, is usually also corrupted by a zero-mean random process (noise) accounting for the measurement uncertainties. It is shown that in the presence of significant noise, LMedS loses its high breakdown point property. A different, two-stage approach in which the uncertainty due to noise is reduced before applying the simplest LMedS procedure is proposed. The superior performance of the technique is proved by comparative graphs.>

Handwritten character recognition is typically classified as online or offline depending on the nature of the input data. Online data consists of a temporal sequence of instrument positions while offline data is in the form of a 2D image of the writing sample. Online recognition techniques have been relatively successful but have the disadvantage of requiring the data to be gathered during the writing process. This paper presents work on the extraction of temporal information from static images of handwriting and its implications for character recognition.>

Studies the problem of object recognition by considering it in the context of an agent operating in an environment, where the agent's intentions translate into a set of behaviors. In this context, an object can fulfil a function; if the agent recognizes this, it has in effect recognized the object. To perform this type of recognition one needs on one hand a definition of the desired function, and on the other the means of determining whether the object can fulfil that function. To illustrate this approach the authors describe the visual recognition abilities that might be needed by an autonomous cleaning robot.>

An approach to the recovery of 3-D volumetric primitives from a single 2-D image is presented. The approach first takes a set of 3-D volumetric modeling primitives and generates a hierarchical aspect representation based on the projected surfaces of the primitives; conditional probabilities capture the ambiguity of mappings between levels of the hierarchy. From a region segmentation of the input image, the authors present a formulation of the recovery problem based on the grouping of the regions into aspects. No domain-independent heuristics are used; only the probabilities inherent in the aspect hierarchy are exploited. Once the aspects are recovered, the aspect hierarchy is used to infer a set of volumetric primitives and their connectivity. As a front end to an object recognition system, the approach provides the indexing power of complex 3-D object-centered primitives while exploiting the convenience of 2-D viewer-centered aspect matching; aspects are used to represent a finite vocabulary of 3-D parts from which objects can be constructed.>

Describes a method of recognizing objects whose contours can be represented in smoothly varying polar coordinate form. Both low- and high-level information about the object (contour smoothness and edge sharpness at the low level and contour shape at the high level) are incorporated into a single energy function that defines a 1D, cyclic, Markov random field (1DCMRF). This 1DCMRF is based on a polar coordinate object representation whose center can be initialized at any location within the object. The recognition process is based on energy function minimization, which is implemented by simulated annealing.>

Proposes a statistical model for the perception of motion transparency and coherence which is given by a two stage process for the extraction of the optical flow and the velocity histogram. In the first stage, a sequence of images is divided into regions; in each region, an optical flow or a normal component of the optical flow is computed. In the second stage, in each of the regions mentioned above, a local velocity histogram is computed and the local histogram is summarised into a global histogram. As for experiment, the authors describe the perception of motion coherence and transparency for synthetic images, such as line patterns and filled regions. They then extend the model for real scenes and apply it to the analysis of the motion of pedestrians.>

A scheme is developed to register range images in an environment where distinctive features are scarce. Another issue addressed here is conflicting situations that may arise from pair-wise registration of multiple overlapping range images whether or not they contain distinctive features. There can be two causes for this: (a) error in individual registrations or (b) compression or bending in range images. The authors develop a scheme for resolving such conflicts for the case where range images share a common reference surface, i.e. when the transformation matrix between two overlapping images involves only three components: two translations and one rotation. The authors implemented this scheme to map the floor of the ocean, where the range data is obtained by a multibeam echo-sounder system installed aboard a sailing ship producing multiple overlapping range images. The system developed is the first automated system for correctly registered mapping of the ocean floor; it is efficient and robust.>

A novel multiresolution image analysis technique based on hierarchies of irregular tessellations generated in parallel by independent stochastic processes is presented. Like traditional image pyramids these hierarchies are constructed in a number of steps on the order of log(image-size) steps. However, the structure of a hierarchy is adapted to the image content and artifacts of rigid resolution reduction are avoided. Two applications of these techniques are presented: connected component analysis of labeled images and segmentation of gray level images. In labeled images, every connected component is reduced to a separate root, with the adjacency relations among the components also extracted. In gray level images the output is a segmentation of the image into a small number of classes as well as the adjacency graph of the classes.>

An approach is presented to 3-D primitive reconstruction that is independent of the selection of volumetric primitives used to model objects. The approach first takes an arbitrary set of 3-D volumetric primitives and generates a hierarchical aspect representation based on the projected surfaces of the primitives; conditional probabilities capture the ambiguity of mappings between levels of the hierarchy. The integration of object-centered and viewer-centered representations provides the indexing power of 3-D volumetric primitives, while supporting a 2-D matching paradigm for primitive reconstruction. Formulation of the problem based on grouping the image regions according to aspect is presented. No domain dependent heuristics are used; the authors exploit only the probabilities inherent in the aspect hierarchy. For a given selection of primitives, the success of the heuristic depends on the likelihood of the various aspects; best results are achieved when certain aspects are more likely, and fewer primitives project to a given aspect.>

A blind noise variance algorithm that recovers the variance of noise in two steps is proposed. The sample variances are computed for square cells tessellating the noise image. Several tessellations are applied with the size of the cells increasing fourfold for consecutive tessellations. The four smallest sample variance values are retained for each tessellation and combined through an outlier analysis into one estimate. The different tessellations thus yield a variance estimate sequence. The value of the noise variance is determined from this variance estimate sequence. The blind noise variance algorithm is applied to 500 noisy 256*256 images. In 98% of the cases, the relative estimation error was less than 0.2 with an average error of 0.06. Application of the algorithm to differently sized images is also discussed.>

A novel hierarchical approach toward fast parallel processing of chain-codable contours is presented. The environment, called the chain pyramid, is similar to a regular nonoverlapping image pyramid structure. The artifacts of contour processing on pyramids are eliminated by a probabilistic allocation algorithm. Building of the chain pyramid is modular, and for different applications new algorithms can be incorporated. Two applications are described: smoothing of multiscale curves and gap bridging in fragmented data. The latter is also employed for the treatment of branch points in the input contours. A preprocessing module allowing the application of the chain pyramid to raw edge data is also described. The chain pyramid makes possible fast, O(log(image/sub -/size)), computation of contour representation in discrete scale-space.>

A scheme is developed to match range images in an environment where distinctive features are scarce. When each image overlaps with several other images, the match must also be performed at the global level. This is particularly challenging, because of the possibility of bending and compression in range images. The primitives used for local matching contours of constant range which are extracted from data are represented by means of a modified chain-code method. All best matches of pairs of contours are considered tentative until their geometrical implications are evaluated and a consistent majority has emerged. To do global matching a cost function is constructed and minimized. Terms contributing to the cost include violation of local matches as well as compression and bending in range images. The present global scheme is valid for any set of multiple overlapping range images, whether they contain distinctive features or not. This scheme has been used to map the floor of the ocean, where the range data are obtained by a multibeam echo-sounder system.>

A method for parallel processing of chain-codable contours is described. The proposed hierarchical environment, called the chain pyramid, is similar to a regular nonoverlapping image pyramid structure. The chain pyramid makes possible the fast computation of contours. The artifacts of contour processing on pyramids are eliminated by a probabilistic allocation algorithm. Processing modules are developed for smoothing of curves, gap bridging in fragmented data, and treatment of branch points. Raw edge data are preprocessed before being input into the chain pyramid. Typical results are presented and briefly characterized.>

In a "coordinate grammar", the rewriting rules replace sets of symbols having been given coordinates by sets of symbols whose coordinates are given functions of the coordinates of the original symbols. It was shown in 1972 that coordinate grammars are "too powerful"; even if the rules are all of finite-state types and the functions are all computable by finite transducers, the grammar has the power of a Turing machine. This paper shows that if we require the functions to be shift-invariant and the rules to be of bounded diameter, then such grammars do have a useful hierarchy of types; in fact, when we require that their sentential forms always remain connected, they turn out to be equivalent to "isometric grammars".

A benchmark is presented that was designed to evaluate the merits of various parallel architectures as applied to image understanding (IU). This benchmark exercise addresses the issue of system performance on an integrated set of tasks, where the task interactions that are typical of complex vision application are present. The goal of this exercise is to gain a better understanding of vision architecture requirements, which can be used to guide the development of the next generation of vision architectures.>

The author provides a general introduction to computer vision. He discusses basic techniques and computer implementations, and also indicates areas in which further research is needed. He focuses on two-dimensional object recognition, i.e. recognition of an object whose spatial orientation, relative to the viewing direction is known.>

Humans can recognize familiar, but unexpected objects, belonging to highly variable object classes, in a fraction of a second — a few hundred cycles of the neural visual "hardware". This position paper suggests computational techniques that could serve as a basis for this type of object recognition if implemented on appropriate parallel hardware.

Construction of image pyramids is described as a two-di-mensional decimation process. Frequently employed generating kernels are compared to the optimal kernel that assures minimal information loss after the resolution reduction, i.e., the one corresponding to an ideal low pass filter. Physically realizable, optimal generating kernels are presented. The amount of computation required for generation of the image pyramid can be reduced significantly by employing half-band filters as components of the optimal kernel. Image pyramids generated by the optimal kernel show a better command of details than the ones generated by a simple 4 × 4 averaging, or a computationally equivalent kernel.

A method is presented which corrects the geometric distortion of pictures with sub-pixel precision. Correction is performed in two passes. The first pass, called calibration, creates correction tables which represent the deviation value of each pixel of the input picture. The second pass, called decalibration, corrects a distorted picture by gray level interpolation using the correction tables. The deviation value is computed with sub-pixel accuracy.

This correspondence describes a method of image segmentation based on a ``pyramid'' of reduced-resolution versions of the image. It defines link strengths between pixels at adjacent levels of the pyramid, based on proximity and similarity, and iteratively recomputes the pixel values and adjusts the link strengths. After a few iterations, the strengths stabilize, and the links that remain strong define subtrees of the pyramid; the leaves of each tree are the pixels belonging to a compact (piece of a) homogeneous region in the image.

Pictures containing lines and curves are often perceived by humans as being composed of a smaller number of more global figures. For example, a broken set of collinear line segments is perceived as a single straight line, even in the presence of other overlapping line segments. A method of extracting such figures from images automatically in a highly parallel manner is presented in this work. A pyramid of successively lower-resolution images is used to transform the problem from one of global search to one of local good continuation. Using the pyramid, figures that are both sparse and obscured can successfully be extracted and the background clutter can be suppressed.

It is shown that the `pyramid linking' method of image segmentation can be regarded as a special case of the ISODATA clustering algorithm and hence is guaranteed to converge.

Multispectral images can be effectively smoothed by using the global distribution of pixel values to guide a local selective averaging process. After several iterations of this process, a typical image is virtually segmented into regions of constant value while significant edges in the image are preserved.

Conflict-free communication in large networks of processors with particular application to image processing is discussed. A general network model and a general class of communication tasks are defined, and algorithms are given for carrying out such tasks on an arbitrary network. Specific types of communication tasks (e.g., one-to-many, many-to-one, and one-to-one) are then considered; these tasks are found to be sufficient for implementing the standard image processing operations. Next, various specific networks topologies are treated, including hypercubes, rings, arrays, and trees. Finally, these results are applied to defining algorithms for performing basic types of image processing operations on both general and specific types of networks.

Laws has introduced a class of texture features based on average degrees of match of the pixel neighbourhoods with a set of standard masks. These features yield better texture classification than standard features based on pairs of pixels. Simplifications of these features are investigated. Their performance is not greatly affected by their exact form and also appears to remain the same if only local match maxima are used. An alternative definition of such features is also presented, based on sums and differences of Gaussian convolutions.

A well-known heuristic for segmenting an image into gray level subpopulations is to select thresholds at the bottoms of valleys on the image's histogram. When the subpopulations overlap, valleys may not exist, but it is often still possible to define good thresholds at the `shoulders' of histogram peaks. Both valleys and shoulders correspond to concavities on the histogram, and this suggests that it should be possible to find good candidate thresholds by analyzing the histogram's concavity structure. Histogram concavity analysis as an approach to threshold selection is investigated and its performance on a set of histograms of infrared images of tanks is illustrated.

Results of a study are summarized in which quadtrees were used to encode the regions in three map overlays representing a small area in northern California. Programs were then written to perform various analysis and manipulation tasks on the quadtree-encoded regions. Data is provided on the compactness of the encodings and the efficiency of the programs.

An image can be segmented by classifying its pixels using local properties as features. Two intuitively useful properties are the gray level of the pixel and the ``busyness,'' or gray level fluctuation, measured in its neighborhood. Busyness values tend to be highly vari-able in busy regions; but great improvements in classification accuracy can be obtained by smoothing these values prior to classifying. An alternative possibility is to classify probabilistically and use relaxation to adjust the probabilities.

It is shown that a digital region is convex if and only if every pair of points in the region is connected by a digital straight line segment contained in the region. The midpoint property is shown to be a necessary but not a sufficient condition for the convexity of digital regions. However, it is shown that a digital region is convex if and only if it has the median-point property.

A definition of convexity of digital solids is introduced. Then it is proved that a digital solid is convex if and only if it has the chordal triangle property. Other geometric properties which characterize convex digital regions are shown to be only necessary, but not sufficient, conditions for a digital solid to be convex. An efficient algorithm that determines whether or not a digital solid is convex is presented.

A method of pairing antiparallel straight lines is presented and discussed. The pairing is based on the distance between the lines, the amount by which they overlap, and on whether or not other lines are interposed. Examples are shown of applying the method to high resolution aerial photographs. Results indicate that cultural features such as roads and buildings can be extracted and that a significant reduction in the complexity of the image description can be obtained.

Blum's medial axis transformation (MAT) for binary pictures yields medial axis points that lie midway between opposite borders of a region or along angle bisectors. This note discusses a generalization of the MAT in which a score is computed for each point P of a grayscale picture based on the gradient magnitudes at pairs of points that have P as their midpoint. These scores are high at points that lie midway between pairs of antiparallel edges or along angle bisectors, so that they define a MAT-like ``skeleton,'' which we may call the GRADMAT. However, this skeleton is rather sensitive to the presence of noise edges or to irregularities in the region edges, and it also is subject to artifacts created by pairs of edges belonging to different objects.

A simple class of piecewise constant approximations to an image is constructed as follows: start with the entire image, subdivide it into quadrants if its gray level standard deviation is high, and repeat the process for each quadrant. This yields a decomposition of the image into blocks, each having low standard deviation, so that each of them can be approximated by a constant value, namely, its mean. The histogram of this approximated image tends to have sharper peaks than that of the original image since the block averaging reduces the variability of the gray levels within homogeneous regions. A possible way of further improving the histogram is based on the fact that small blocks tend to occur near region borders; thus, suppressing these blocks should tend to deepen the valleys on the histogram, making threshold selection (to separate regions of different types) easier. Conversely, the histogram of the small blocks only represents a population of pixels near region borders, and if there are only two types of regions (e.g., objects and background), the mean of this histogram should be a useful threshold for separating them; but in practice, this method is not very reliable since background fluctuations also give rise to border pixels.

ZMOB is a multimicroprocessor system consisting of 256 Z80A microprocessors that communicate via a fast cyclic shift-register bus. This paper discusses the efficient use of ZMOB for various types of image processing operations, including point and local operations, discrete transforms, geometric operations, and computation of image statistics.

A recently developed method of image smoothing and segmentation makes use of a "pyramid" of images at successively lower resolutions. It establishes links between pixels at successive levels of the pyramid; the subtrees of the pyramid defined by these links yield a segmentation of the image into regions over which the smoothing takes place. This paper investigates several variations on the basic linking process with regard to such factors as initialization, criteria for linking, and iteration scheme used. It also studies generalizations in which the links are weighted rather than forced, and in which interactions among the pixels at a given level are also allowed. Finally, it extends the approach to links based on more than one feature of a pixel, e.g., on color components or local property values.

We define straightness and convexity of regions in a digital picture. Then it is shown that a few important properties satisfied by convex (Euclidean) regions are also satisfied by convex digital regions. We extend the definition of digital convexity of regions to digital solids. Efficient algorithms are presented that determine whether or not a digital region is convex, a digital arc is a digital straight line segment and a digital solid is convex.

This paper deals with a class of image models based on random geometric processes. Theoretical and empirical results on properties of patterns generated using these models are summarized. These properties can be used as aids in fitting the models to images.

A blob is a compact region lighter (or darker) than its background surrounded by a smoothly curved edge. Blobs can be detected using cooperating relaxation processes to enhance their interior and edge probabilities. A discussion of the processes working independently and together is given. The use of a pyramidal relaxation structure, the use of the closedness of contours as an additional information source, and the extension of cooperating relaxation processes to a time sequence of images are also discussed.

Given a binary image stored in a cellular array, a local reconfiguration process can be used to reconnect some of the cells into a quadtree network representing the image. This quadtree can also be ``roped,'' i.e., nodes representing adjacent image blocks of the same size can be joined. Using the roped quadtree network as a parallel (cellular) computer, image properties such as perimeter and genus, as well as the quadtree distance transform, can be computed in O(tree height) = O(log image diameter) time. The area and centroid of the image can be computed in O(height) time without the need for roping.

This paper introduces a generalization of cellular automata in which each celi is a tape-bounded Turing machine rather than a finite-state machine. Fast algorithms are given for performing various basic image processing tasks by such automata. It is suggested that this model of parallel computation is a very suitable one for studying the advantages of parallelism in this domain.

A new method for smoothing images by local weighted averaging is presented. The weights are computed as strengths of links between neighbors. These link strengths are averages of the variations in gray level over paths of length 2. It is shown that the method preserves edges, thin lines, and average gray levels. Moreover, it transforms the images into slowly varying regions with sharp borders, having histograms that tend to be composed of sharp peaks.

Probabilistic relaxation labeling processes are iterative parallel schemes that use contextual information to reduce local ambiguities. The behavior of these processes can be described by examining the rates of change and entropies of the probability vectors at each iteration. Examples are given comparing three relaxation processes as applied to several basic image analysis tasks.

One way to define operators for detecting edges in digital images is to fit a surface (plane, quadric,...) to a neighborhood of each image point and take the magnitude of the gradient of the surface as an estimate of the rate of change of gray level in the image at that point. This approach is extended to define edge detectors applicable to multidimensional arrays of data-e.g., three-dimensional arrays obtained by reconstruction from projections-by locally fitting hypersurfaces to the data. The resulting operators, for hypersurfaces of degree 1 or 2, are closely analogous to those in the two-dimensional case. Examples comparing some of these three-dimensional operators with their twodimensional counterparts are given.

Blum's medial axis transformation (MAT) of the set S of 1's in a binary picture can be defined by an iterative shrinking and reexpanding process which detects ``corners'' on the contours of constant distance from S¿, and thereby yields a ``skeleton'' of S. For unsegmented (gray level) pictures, one can use an analogous definition, in which local MIN and MAX operations play the roles of shrinking and expanding, to compute a ``MMMAT value'' at each point of the picture. The set of points having high values defines a good ``skeleton'' for the set of high-gray level points in the given picture.

Hueckel's edge detector finds the best-fitting ideal step edge to a given picture neighborhood by expanding the neighborhood and step edge in terms of a set of nine basis functions. A very simple case of this approach uses a 2 × 2 neighborhood and three basis functions. This case is solved explicitly using elementary methods. The magnitude of the best-fitting step edge for the neighborhood AB CD turns out to be the Roberts operator max (|A - D|, |B - C|).

If a picture contains dark objects on a light background (or vice versa), the objects can be extracted by thresholding, i.e., by classifying the pixels into ``light'' and ``dark'' classes. If the picture is noisy, so that the object and background gray level populations overlap, there will be errors in the thresholded output. A relaxation process can be used to reduce these errors; we classify the pixels probabilistically, and then adjust the probabilities for each pixel, based on its neighbors' probabilities, with light reinforcing light and dark dark. When this adjustment process is iterated, the dark probabilities become very high for pixels that belong to dark regions, and vice versa, so that thresholding becomes trivial.

Relaxation is applied to the segmentation of closed boundary curves of shapes. The ambiguous segmentation of the boundary is represented by a directed graph structure whose nodes represent segments, where two nodes are joined by an arc if the segments are consecutive along the boundary. A probability vector is associated with each node; each component of this vector provides an estimate of the probability that the corresponding segment is a particular part of the object. Relaxation is used to eliminate impossible sequences of parts, or reduce the probabilities of unlikely ones. In experiments involving airplane shapes, this almost always results in a drastic simplification of the graph with only good interpretations surviving. The approach is also extended to include curve linking and gap filling. A chain coded input image is broken into segments based on a measure of local curvature. Gap completions linking pairs of segments are then proposed and represented in a graph structure. A second graph, whose nodes consist of paths in the above graph, is constructed, and the nodes of the second graph are probabilistically classified as various object parts. Relaxation is then applied to increase the probability of mutually supporting classifications, and decrease the probability of unsupported decisions. A modified relaxation process using information about the size, spatial position, and orientation of the object parts yielded a high degree of disambiguation.

Several types of gray-weighted ``medial axes'' have been defined. This paper shows that one of them, the min-max medial axis, can be used to reconstruct good approximations to the original image based on a relatively small amount of information.

Some contour properties can be derived in parallel by a string or cycle of automata in linear time, faster than can be done with a single processor. In particular, the intersection points of two contours, the straightness of a line, the union or intersection of two contours, and polygonal approximations of a contour are computed in linear time.

A formal model for processor networks, the cellular d-graph automaton, is described, and its equivalence to Siegel's formal model for SIMD machines is discussed.

The task of segmenting an image and that of estimating properties of image regions may be highly interdependent. The goal of segmentation is to partition the image into regions with more or less homogeneous properties; but the processes which estimate these properties should be confined within individual regions. A cooperative, iterative approach to segmentation and property estimation is defined; the results of each process at a given iteration are used to adjust the other process at the next iteration. A linked pyramid structure provides a framework for this process iteration. This hierarchical structure ensures rapid convergence even with strictly local communication between pyramid nodes.

A method of evaluating edge detector output is proposed, based on the local good form of the detected edges. It combines two desirable qualities of well-formed edges-good continuation and thinness. It yields results generally similar to those obtained with measures based on discrepancy of the detected edges from their known ideal positions, but it has the advantage of not requiring ideal positions to be known. It can be used as an aid to threshold selection in edge detection (pick the threshold that maximizes the measure), as a basis for comparing the performances of different detectors, and as a measure of the effectiveness of various types of preprocessing operations facilitating edge detection.

Three simple methods of extracting texture primitives are compared. It appears that the simplest of these, thresholding at a fixed percentile, yields primitives that are quite effective in texture discrimination, using a set of simple properties of the primitives. Second-order statistics of these properties were also computed for pairs of neighboring primitives, using several definitions of "neighboring." In some cases, textures not discriminable using first-order statistics can be discriminated using statistics of the second order.

Three approaches to reducing errors in multispectral pixel classification were compared: 1) postprocessing (iterated reclassification based on comparison with the neighbors' classes); 2) preprocessing (iterated smoothing, by averaging with selected neighbors, prior to classification); and 3) relaxation (probabilistic classification followed by iterative probability adjustment). In experiments using a color image of a house, the relaxation approach gave markedly superior performance; relaxation eliminated 4-8 times as many errors as the other methods did.

Experimental results are presented on some properties of random mosaic models for textures. These observations are compared with the theoretically predicted values. The predictions are also compared with observations on a real Image.

Elongated black objects in black-and-white pictures can be ``thinned'' to arcs and curves, without changing their connectedness, by (repeatedly) deleting black border points whose deletion does not locally disconnect the black points in their neighborhoods. This technique generalizes to gray-scale pictures if we use a weighted definition of connectedness: two points are ``connected'' if there is a path joining them on which no point is lighter than either of them. We can then ``thin'' dark objects by changing each point's gray level to the minimum of its neighbors' gray levels, provided this does not disconnect any pair of points in its neighborhood. Examples illustrating the performance of this technique are given.

Complex waveforms may contain peaks and valleys at many different scales, ranging from very local to very global. This correspondence describes an approach to detecting these peaks and valleys by applying simple difference operators at each point to neighborhoods having a wide range of sizes, and making simple comparisons of the outputs of these operators for various sizes and positions.

Ehrich and Foith have proposed an approach to the hierarchical representation of waveforms based on peak dominance relations. This correspondence proposes an alternative approach, derived from concepts of fuzzy connectedness. It also discusses the possibility of extending this approach to the description of curves and of images.

In order to apply relaxation-like methods to waveforms with ambiguous segmentations one has to consider all possible segmentations separately. An extension of the discrete relaxation operator is proposed which can be applied to such waveforms using just one relaxation network. Examples of the application of the method are also given.

Abstract : A standard approach to threshold selection for image segmentation is based on locating valleys in the image's gray level histogram. Several methods have been proposed that produce a transformed histogram in which the valley is deeper, or is converted into a peak, and is thus easier to detect. The transformed histograms used in these methods can all be obtained by creating (gray level, edge value) scatter plots, and computing various weighted projections of these plots on the gray level axis. Using this unified approach makes it easier to understand how the methods work and to predict when a particular method is likely to be effective. The methods are applied to a set of examples involving both real and synthetic images, and the characteristics of the resulting transformed histograms are discussed. (Author)

Suppose that we are given a picture having approximately piecewise constant gray leveL Each point P has a largest neighborhood N(P) that is entirely contained in one of the constant regions, and the set of maximal N(P)'s (i.e., N(P)'s not contained in other N(P)'s) constitutes an economical description of the picture, generalizing the Blum "skeleton" or medial axis transformation. This description can be used to construct approximations to the picture (e.g., by discarding small N(P)'s). The picture can be smoothed, without excessive blurring, by averaging over each N(P). By taking differences between pairs of touching maximal N(P)'s, the edges between the regions can be detected; since this edge detection scheme is not based on symmetrical detection operators, it is not handicapped when two adjacent regions differ greatly in size.

Image segmentation can be treated as a pixel classification problem. This classification may be done by measuring a set of features at each point and defining a decision surface in the feature space. This method is commonly used in multispectral images, but there is no obvious choice for the feature set in the case of monochromatic images. Ihis paper makes use of a two-dimensional feature set consisting of gray level and edge value. Ihe structure of this feature space is analyzed, and several plausible decision surfaces are suggested. These are compared experimentally on a set of FLIR test images.

Cloud-type classification is an important component of meteorological and hydrological programs which require estimates of parameters such as solar radiation, rainfall, moisture, and sea-surface temperature. The accuracy of automatic cloud-type classification systems has been limited by ambiguities in multispectral cloud type signatures. Attempts to resolve these ambiguities by the addition of textural features to brightness and temperature features have not produced a significant reduction in misclassification errors. The algorithm described presents a cloud-type classification system which resolves ambiguities in infrared cloud-type signatures by a comparison of textural measures on known and unknown cloud-type segments. The algorithm consists of two parts: 1) the segmentation procedure and 2) the classification procedure. The segmentation part of the algorithm provides a generalized method for partitioning a window of image data into objects characterized by nonoverlapping intervals of gray-level values. The classification part of the algorithm is problem specific, i.e., selection of window and segment features and decision rules will vary with the application. Application of the algorithm to the problem of classifying 107 windows of SMS-1 infrared satellite data resulted in a classification accuracy of approximately 95 percent.

Threshold selection techniques have been used as a basic tool in image segmentation, but little work has been done on the problem of evaluating a threshold of an image. The problem of threshold evaluation is addressed, and two methods are proposed for measuring the "goodness" of a thresholded image, one based on a busyness criterion and the other based on a discrepancy or error criterion. These evaluation techniques are applied to a set of infrared images and are shown to be useful in facilitating threshold selection. In fact, both methods usually result in similar or identical thresholds which yield good segmentations of the images.

A method of detecting natural ``plateaus'' (equals maximal intervals of approximately constant value) in a one-dimensional pattern is described. The method is based on examining neighborhoods of each point having a range of sizes; rejecting neighborhoods of each size for which the standard deviation (of pattern values over the neighborhood) is not a local minimum; and further rejecting any neighborhood N whose subintervals of conparable size do not have mean pattern values approximately equal to that of N.

This correspondence discusses parallel iterative methods of segmenting the border of a shape into "angles" and "sides." Initially, smoothed "slope" and "curvature" values of the border are measured at every point, and the curvature value determines the point's initial probabilities of being an angle or a side. The values are then iteratively adjusted, and the probabilities are reinforced or weakened, in a manner dependent on the values and probabilities at neighboring points. For example, a point p's probability of being on a side is reinforced if p and its neighbors have similar slopes, and our estimate of p's slope can be improved by (say) averaging with these slopes. Similarly, p's probability of being an angle is reinforced if appropriate slope or curvature differences exist between p and its neighbors, and our estimate of p's curvature can be improved by taking the neighbors' slopes into account. A set of such reinforcement and adjustment rules is formulated, and examples are given of their effects on various types of shapes.

This paper deals with the detection of freehand forgeries of signatures on bank checks. The detection process makes use of size ratio and slant features derived from Eden's kinematic stroke model for handwriting, which was modified to make it applicable to prewritten material. The features are measured for a real signature by a process involving automatic thresholding, to extract the signature from the background; analysis of projections, to segment the signature into vertical zones; detection of tall letters, to segment it into horizontal zones; and identification of the tall letters with respect to the (assumed known) spelling of the signature. Statistical assumptions are made regarding the expected variation in feature values among different writers and for a single writer. Tests on a small data base led to verification of these assumptions and to successful forgery detection.

The computational cost of template matching can be reduced by using only a subtemplate, and applying the rest of the template only when the subtemplate's degree of match exceeds a threshold. A probabilistic analysis of this approach is given, with emphasis on the choice of subtemplate size to minimize the expected computational cost.

A relaxation process is described and is applied to the detection of smooth lines and curves in noisy, real world images. There are nine labels associated with each image point, eight labels indicating line segments at various orientations and one indicating the no-line case. Attached to each label is a probability. In the relaxation process, interaction takes place among the probabilities at neighboring points. This permits line segments in compatible orientations to strengthen one another, and incompatible segments to weaken one another. Similarly, no-line labels are reinforced by neighboring no-line labels and weakened by appropriately oriented line labels. This process converges, in only a few iterations, to a condition in which points lying on long curves have achieved high line probabilities, while other points have high no-line probabilities, There is some tendency, under this process, for curves to thicken; however, a thinning procedure can be incorporated to counteract this. The process is effective even for curves of low contrast, and even when many curves lie close to one another.

Two methods are introduced for reducing additive noise in approximately piecewise constant images. In the first method, the correct gray level of a point P is estimated by a weighted average of the gray levels of P's immediate neighbors. To assign these weights for a given P so that the local averaging operation does not blur the image, the presence of any edges or lines passing through P's neighborhood must be determined. For example, when an edge is present, only those points on P's side of the edge should be used. In general, the distribution of gray levels in P's neighborhood will suggest many possible line and edge configurations which can be used to compute the weight distribution for the averaging operation. The averaging is performed in parallel over the entire image and is iterated for additional smoothing. The second method is a relaxation labeling formulation which can be psed in cases of more severe noise. Each point is now assigned a vector of probabilities over its allowable gray level set. These probabilities are updated as weighted averages of the gray level probabilities at neighboring points. Once again the presence of lines and edges determines how the contribution from each neighboring point is weighted. Examples demonstrating both methods are given.

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.

A simple formula is derived for the distance between two points on a hexagonal grid, in terms of coordinates with respect to a pair of oblique axes.

Several models for line detection in noise are discussed, based on models for the ``simple'' and ``complex'' cells that have been found in the visual cortex. The possibility of obtaining experimental evidence for deciding among the models is briefly considered.

Implementation of a simple algorithm is described for thinning digital objects down to ``skeletons.'' A method of detecting ``noisy'' branches of a skeleton, with the aid of the distance transform of the original object, is developed.

Given a set of objects in a scene whose identifications are ambiguous, it is often possible to use relationships among the objects to reduce or eliminate the ambiguity. A striking example of this approach was given by Waltz [13]. This paper formulates the ambiguity-reduction process in terms of iterated parallel operations (i.e., relaxation operations) performed on an array of (object, identification) data. Several different models of the process are developed, convergence properties of these models are established, and simple examples are given.

Three standard approaches to automatic texture classification make use of features based on the Fourier power spectrum, on second-order gray level statistics, and on first-order statistics of gray level differences, respectively. Feature sets of these types, all designed analogously, were used to classify two sets of terrain samples. It was found that the Fourier features generally performed more poorly, while the other feature sets all performned comparably.

A method of detecting step edges in noisy one-dimensional input data is described. The method involves examination of differences in average gray level over ranges of positions and sizes. Unlike previously described methods, it remains reliable when edges occur close to one another.

The rate and direction of maximum change of texture coarseness across a surface are important cues to the orientation of the surface relative to the observer. This note describes a simple method of automatically detecting these "texture gradients."

This correspondence describes an improved method of detecting "angles"—i.e., maxima of the difference between successive nonoverlapping average slopes—on a digital curve. The method is similar to, but gives better results than, a method described in an earlier paper.

This correspondence describes a method of dividing a picture into differently textured regions by thresholding the values of a suitable local picture property. The approach used is a generalization to natural textures of a technique recently proposed by Tsuji. The examples given involve textures that differ in coarseness; a method of estimating texture coarseness by analysis of local property values is also described.

Regions in a picture that differ texturally from their surroundings can often be extracted by 1) applying a local operation to every point of the picture, 2) averaging the results, and 3) thresholding. This approach will usually not work if there are too many differently textured regions present, since the average for one type of region may then be indistinguishable from the average resulting from a mixture of two other types that adjoin. The amount of averaging that should be used depends on the coarseness of the texture. An approach to choosing this amount automatically was investigated, but the results were not as good as those obtained with a fixed high degree of averaging.

A method of detecting pits, peaks, ridges, and ravines on a digital array of terrain elevation data is described. The methods used are based on algorithms designed to detect bright and dark spots or streaks in pictures.

Parallel web automata (PWA)-a generalization of cellular arrays to arbitrary graph structures-are defined. It is shown that such automata make poor acceptors (i.e., they are not good recognizers of their own graph structures). However, they can be used to perform parallel local pattern matching (with respect to patterns of bounded size) on themselves, so that they have potential usefulness as models for ''semantic memory.'' They can also be used to find greatest compatible sets of graph labelings subject to given local constraints; this problem arises, for example, in the analysis of scenes containing three-dimensional objects.

It is shown that a digital arc S is the digitization of a straight line segment if and only if it has the "chord property:" the line segment joining any two points of S lies everywhere within distance 1 of S. This result is used to derive several regularity properties of digitizations of straight line segments.

Threshold selection for picture segmentation is relatively easy when the frequency distribution of gray levels in the picture is strongly bimodal, with the two peaks comparable insize and separated by a deep valley. This report describes a method of handling cases in which the peaks are very unequal in size and the valley is broad. A Laplacian operation is applied to the picture to determine points that lie on or near the edges of objects. Threshold selection becomes easier when the frequency distribution of gray levels of these points is used.

The square of the perimeter of a figure divided by its area P2/A is a classical measure of the noncompactness of the figure. In Euclidean geometry, P2/A is always at least 4π, and takes on this minimum value only if the figure is a circle; larger values correspond to figures that are less compact than circles. In digital pictures, however, certain squares or octagons-depending on how P is measured-yield smaller values than do digitized circles. Thus for digital pictures, though P2/A may be useful as a practical measure of noncompactness, it possesses certain pathological features of which users should be aware.

Characterizations of digital “simple arcs” and “simple closed curves” are given. In particular, it is shown that the following are equivalent for sets S having more than four points: (1) S is a simple curve; (2) S is connected and each point of S has exactly two neighbors in S ; (3) S is connected, has exactly one hole, and has no deletable points. It follows that if a “shrinking” algorithm is applied to a connected S that has exactly one hole, it shrinks to a simple curve.

A simple parallel procedure for selecting significant curvature maxima and minima on a digital curve is described.

Some gray-level manipulation techniques are described, the first of which involves changing the gray-level distribution within the picture. Thereafter a method for extracting relatively noise-free objects from a noisy background is described. The purpose of these techniques is to preprocess a textural scene for subsequent analysis or classification. The present state of the art of texture analysis in general does not enable the parameters associated with the techniques to be generalized. Results for a range of parameters for both real and computer-generated pictures are therefore given.

Certain arrangements of local features in a scene tend to group together and to be seen as units. It is suggested that, in some instances, this phenomenon might be interpretable as a process of cluster detection in a graph-structured space derived from the scene. This idea is illustrated using a class of line-drawing ``scenes'' that contain only horizontal and vertical line segments.

Further work is described on simple sets of parallel operations that detect "texture edges" (abrupt discontinuities in the average values of local picture properties), as well as spots or streaks that are texturally different from their surrounds.

If a picture contains elongated objects of different thicknesses, one can make measurements on it which are thickness-invariant by first transforming it so that each object is thinned down to a "medial line" of constant thickness.Several algorithms are described which perform such a thinning transformation when applied to the picture in parallel.It is proved that these algorithms do not change the connectivity properties of the picture.

Simple sets of parallel operations are described which can be used to detect texture edges, "spots," and "streaks" in digitized pictures. It is shown that, by comparing the outputs of the operations corresponding to (e.g.,) edges of different sizes, one can construct a composite output in which edges between differently textured regions are detected, and isolated objects are also detected, but the objects composing the textures are ignored. Relationships between this class of picture processing operations and the Gestalt psychologists' laws of pictorial pattern organization are also discussed.

Natural concepts of connectedness and simple-connectedness are defined for subsets of a digital picture.It is shown that every simply-connected object (with more than one element) in such a picture has elements which can be deleted without destroying its simpleconnectedness.This makes it easy to prove that a well-known "shrinking" algorithm always works--that is, shrinks any simply-connected object down to a single element.It also becomes easy to show that the natural "edge-following" algorithm, in which one "keeps one's hand on the wall," follows completely around the edge of any simply-connected object; this result in turn can be used to show that a well-known "border-following" algorithm (in which one follows the border elements of the object rather than the "cracks" between the object and its complement) always works.Various related questions are also treated, among them, that of whether there can exist a "parallel" shrinking algorithm.