A fast and exact Euclidean distance transformation using decomposed grayscale morphological operators is presented. Applied on a binary image, a distance transformation assigns each object pixel a value that corresponds to the shortest distance between the object pixel and the background pixels. It is shown that the large structuring element required for the Euclidean distance transformation can be easily decomposed into 3/spl times/3 windows. This is possible because the square of the Euclidean distance matrix changes uniformly both in the vertical and horizontal directions. A simple extension for a 3D Euclidean distance transformation is discussed. A fast distance transform for serial computers is also presented. Acting like thinning algorithms, the version for serial computers focuses operations only on the potential changing pixels and propagates from the boundary of objects, significantly reducing execution time. Nonsquare pixels can also be used in this algorithm. An example application, shape filtering using arbitrary sized circular dilation and erosion, is discussed. Rotation-invariant basic morphological operations can be done using this example application.>

A distance transformation technique for a binary digital image using a gray-scale mathematical morphology approach is presented. Applying well-developed decomposition properties of mathematical morphology, one can significantly reduce the tremendous cost of global operations to that of small neighborhood operations suitable for parallel pipelined computers. First, the distance transformation using mathematical morphology is developed. Then several approximations of the Euclidean distance are discussed. The decomposition of the Euclidean distance structuring element is presented. The decomposition technique employs a set of 3 by 3 gray scale morphological erosions with suitable weighted structuring elements and combines the outputs using the minimum operator. Real-valued distance transformations are considered during the processes and the result is approximated to the closest integer in the final output image.

A fast and exact Euclidean distance transformation using grayscale mathematical morphology is presented. The large structuring element required for this operation is decomposed into iterative applications of simple 3*3 windows. This is possible because the square of the Euclidean distance matrix is easily decomposable. Non-square pixels can also be used in this application.>

The general solution to the moment-preserving (MP) quantizer problem is presented. It is shown that the moment preserving quantizer is related to the Gauss-Jacobi mechanical quadrature, the output levels of the N-level MP quantizer are the N zeros of an Nth degree orthogonal polynomial associated with the input probability distribution function, and the N-1 thresholds of the MP quantizer are related to the Christoffel numbers through the Chebyshev-Markov-Stieltjes separation theorem. The statistical convergence of the MP quantizer is investigated. MP quantizer tables are presented for the uniform, Gaussian, and Laplacian density functions. The moment-preserving quantizer is shown to be related to block truncation coding.>

The authors develop methodologies for the automatic selection of image features to be used to visually control the relative position and orientation (pose) between the end-effector of an eye-in-hand robot and a workpiece. A resolved motion rate control scheme is used to update the robot's pose based on the position of three features in the camera's image. The selection of these three features depends on a blend of image recognition and control criteria. The image recognition criteria include feature robustness, completeness, cost of feature extraction, and feature uniqueness. The control criteria include system observability, controllability, and sensitivity. A weighted criteria function is used to select the combination of image features that provides the best control of the end-effector of a general six-degrees-of-freedom manipulator. Both computer simulations and laboratory experiments on a PUMA robot arm were conducted to verify the performance of the feature-selection criteria.>

The authors investigate the selection of image features to be used to control visually the position and orientation (pose) of the end-effector of an eye-in-hand robot relative to a workpiece. A resolved-motion-rate control scheme is used to update the robot's pose on the basis of the position of three features in the camera's image. The selection of these three features depends on the condition and sensitivity of the differential relationship between the image features and the control parameters. Both computer simulations and laboratory experiments on a PUMA robot arm were conducted to verify the performance of the feature selection criteria. Experimentally, the PUMA robot arm, with a CCD (charged-coupled device) camera mounted on its end effector, was able to track a randomly moving carburetor gasket with a visual feedback cycle time of 70 ms.>

Recent results in precision measurements using computer vision are presented. An edge operator based on two-dimensional spatial moments is given. The operator can be implemented for virtually any size of window and has been shown to locate edges in digitized images to a twentieth of a pixel. This accuracy is unaffected by additive or multiplicative changes to the data values. The precision is achieved by correcting for many of the deterministic errors caused by nonideal edge profiles using a lookup table to correct the original estimates of edge orientation and location. This table is generated using a synthesized edge which is located at various subpixel locations and various orientations. The operator is extended to accommodate nonideal edge profiles and rectangularly sampled pixels. The technique is applied to the measurement of imaged machined metal parts. Theoretical and experimental noise analyses show that the operator has relatively small bias in the presence of noise.>

Recently, a superposition property called threshold decomposition and another property called stacking were introduced and shown to apply successfully to gray-scale morphological operations. This property allows gray-scale signals to be decomposed into multiple binary signals. The signals are processed in parallel, and the results are combined to produce the desired gray-scale result. The authors present the threshold decomposition architecture and the stacking property that allows the implementation of this architecture. Gray-scale operations are decomposed into binary operations. This decomposition allows gray-scale morphological operations to be implemented using only logic gates in VLSI architectures that can significantly improve speed as well as give theoretical insight into the operations.>

The authors present a vision module which is able to guide an eye-in-hand robot through general servoing and tracking problems using off-the-shelf image-processing equipment. The vision module uses the location of binary image features from a camera on the robot's end-effector to control the position and one degree of orientation of the robot manipulator. A unique feature-based trajectory generator provides smooth motion between the actual image features and the desired image features even with asynchronous and discontinuous vision updates. By performing the trajectory generation in image feature space, image-processing constraints such as the feature extraction time can be accounted for when determining the appropriate segmentation and acceleration times of the trajectory. Experimental results of a PUMA robot tracking objects with vision feedback are discussed.>

The authors have created an interface between computer vision processes and CAD (computer-aided design) databases as part of the development of an automated visual inspection system. A recognition planning system uses rules to select the important vision features from the given CAD database and generates feature-recognition procedures. An inspection planning system provides overall inspection procedures given the CAD database. This system provides such information as a list of features to be measured, techniques to use, and the range of values allowed. Thus, after the design cycle, parts can be thoroughly inspected with no technical decisions or programming required.>

Morphological operations are used for segmentation, feature generation and location extraction. A recursive adaptive thresholding algorithm transforms a gray-level image into a set of multiple level regions of objects. A distance transformation algorithm then is used to transform a binary image into the minimum distance from each object point to the object's boundary. This algorithm uses a morphological erosion with a large structuring element which may correspond to Euclidean, city-block, or chessboard distance measures. A shape library database with hierarchical features is automatically generated. The features extracted are the shape number and the skeletal local-maximum points radii and coordinates. Object recognition is achieved by comparing the shape number and the hierarchical radii. Object location is detected by a hierarchical morphological bandpass filter.>

Application algorithms for industrial parts and tool recognition and inspection by image morphology techniques are discussed. A recursive adaptive thresholding algorithm transforms a gray-level image into a set of multiple-level regions of objects. This algorithm uses a morphological erosion with a large symmetrical concave structuring element. A distance-transformation algorithm transforms these binary image regions into the minimum distance from each object point to the boundary of the object. This algorithm also uses a morphological erosion. From the distance transform, it is possible to compute a shape number and extract the skeleton, which is useful for generic pattern recognition and feature extraction. Corner angles and the radii of circular holes can be located, identified, and estimated by using morphological openings and erosions. The algorithms allow robust tool and part recognition and inspection.>

A partial-shape-recognition technique utilizing local features described by Fourier descriptors is introduced. A dynamic programming formulation for shape matching is developed, and a method for comparison of match quality is discussed. This technique is shown to recognize unknown contours that may be occluded or that may overlap other objects. Precise scale information is not required, and the unknown objects may appear at any orientation with respect to the camera. The segment-matching dynamic programming method is contrasted with other sequence-comparison techniques that utilize dynamic programming. Experimental results are discussed that indicate that partial contours can be recognized with reasonable accuracy.>

The contrast and orientation estimation accuracy of several edge operators that have been proposed in the literature is examined both for the noiseless case and in the presence of additive Gaussian noise. The test image is an ideal step edge that has been sampled with a square-aperture grid. The effects of subpixel translations and rotations of the edge on the performance of the operators are studied. It is shown that the effect of subpixel translations of an edge can generate more error than moderate noise levels. Methods with improved results are presented for Sobel angle estimates and the Nevatia-Babu operator, and theoretical noise performance evaluations are also provided. An edge operator based on two-dimensional spatial moments is presented. All methods are compared according to worst-case and RMS error in an ideal noiseless situation and RMS error under various noise levels.>

Current methods of contour tracing are based on chain code concepts which require movement from the center of a pixel to the center of a four- or eight-connected neighbor. They are basically serial processes requiring memory and decision structures based on the connectedness of the objects and the direction of the trace. A chain code method is proposed here which moves along the edge midpoints of pixels, increasing the number of contour samples. This new tracing process needs no memory, lends itself to fast table lookup implementation, uses only two tables for all connectedness rules and trace directions, and permits parallel preprocessing. The resulting chain code is nearer the true contour than any previous digital contour tracing method. Methods for conversion between the standard chain code and the new edge chain code are also presented.

This paper presents a Lisp-based robot vision system designed for research. It combines a Puma 560 robot arm, the computing power of a VAX 11/780 and a Grinnell Systems 275, the facility for artificial intelligence through Lisp, and sensing capability through a wrist-mounted camera. A description of the robot vision system includes system and software structure, the Lisp primitives for robot control, two vision algorithms, and a frame-based motion planner written in Lisp.

A new method for locating edges in digital data to subpixel values and which is invariant to additive and multiplicative changes in the data is presented. For one-dimensional edge patterns an ideal edge is fit to the data by matching moments. It is shown that the edge location is related to the so-called ``Christoffel numbers.'' Also presented is the study of the effect of additive noise on edge location. The method is extended to include two-dimensional edge patterns where a line equation is derived to locate an edge. This in turn is compared with the standard Hueckel edge operator. An application of the new edge operator as an edge detector is also provided and is compared with Sobel and Hueckel edge detectors in presence and absence of noise.

The three-dimensional shape analysis problem is a very demanding test of shape analysis algorithms. Previous approaches to the problem have employed global features such as moments and Fourier descriptors. Global features lack the capacity for solving the partial shape recognition problem, in which only part of the unknown shape is available. Previous approaches to local shape analysis have employed structural (syntactic) methods, but these methods have so far failed to solve the three-dimensional problem. This paper describes a hybrid structural/statistical local shape analysis algorithm which is applied to the three-dimensional problem.

A method is presented to automatically inspect the block boundaries of a reconstructed two-dimensional transform coded image, to locate blocks which are most likely to contain errors, to approximate the size and type of error in the block, and to eliminate this estimated error from the picture. This method uses redundancy in the source data to provide channel error correction. No additional channel error protection bits or changes to the transmitter are required. It can be used when channel errors are unexpected prior to reception.

A new technique for image compression called Block Truncation Coding (BTC) is presented and compared with transform and other techniques. The BTC algorithm uses a two-level (one-bit) nonparametric quantizer that adapts to local properties of the image. The quantizer that shows great promise is one which preserves the local sample moments. This quantizer produces good quality images that appear to be enhanced at data rates of 1.5 bits/picture element. No large data storage is required, and the computation is small. The quantizer is compared with standard (minimum mean-square error and mean absolute error) one-bit quantizers. Modifications of the basic BTC algorithm are discussed along with the performance of BTC in the presence of channel errors.

A new technique for image texture analysis is described which uses the relative frequency of local extremes in grey level as the principal measure. This method is invariant to multiplicative gain changes (such as caused by changes in illumination level or film processing) and is invariant to image resolution and sampling rate if the image is not undersampled. The algorithm described is computationally simple and can be implemented in hardware for real-time analysis. Comparisons are made between this new method and the spatial dependence method of texture analysis using 49 samples of each of eight textures. The new method seems just as accurate and considerably faster.