A focal-plane-array chip designed for real-time, general-purpose, image preprocessing is reported. A 48 X 48 pixel detector array and a 24 X 24 processing element processor array are monolithically integrated on the chip. The analog, charge-coupled device-based VLSI chip operates in the charge domain and has sensing, storing, and computing capabilities. It captures the image data and performs local neighborhood operations. The processor array is digitally programmable and uses a single-instruction, multiple-data parallel architecture. Various image preprocessing tasks such as level shifting, gain adjustment, thresholding, smoothing, sharpening, and edge detection can be implemented and A/D conversion can be performed prior to output. Frame-to-frame operations such as motion detection and tracking can be implemented as well. The chip was fabricated with a double-poly, double-metal process in a commercial CCD foundry. The prediction of the performance is based on numerical analysis and experimental results of testing a prototype charge-coupled computer. Operating at a modest clock frequency of 25 MHz, the chip is projected to achieve an internal throughput as high as 576 Mops with a 54 dB dynamic range (9-bit equivalent accuracy). The simulation of an edge detection algorithm implemented by the chip is presented. The power dissipation is estimated to be 20 mW and the total size of the 59-pad chip is 9.4 X 9.4 mm2.

In order to provide a framework for the evaluation of, and need for, sensor information appropriate to real time manufacturing control, a workcell based on a 5-axis machining center was developed. This workcell defines a problem space within which automated inspection is to be applied. Primarily, we are interested in evaluating the use of machine vision and Coordinate Measuring Machines (CMM's) as means to provide information to an automated workcell controller. This controller will use these sensing technologies in a hierarchical fashion exploiting the speed vs. accuracy tradeoff's characteristic of tactile and non-tactile coordinate acquisition. We have implemented an Octree solid modeling system which has the capabilities of model generation from the information provided by the vision system. In addition, the Octree method lends itself to simulating the actual manufacturing process. Our system reads the machine tool G-Codes generated by our CAD system and simulates the material removal operation by successively removing intersections between the tool and workpiece. This machined model is then used for automatic inspection sequence generation. This paper will describe the framework and architecture of our automated inspection system, as well as specifics relating to the Octree modeling system.

The increase in the development of techniques and equipments for image processing purposes has allowed the study of new applications for automatic vision. In many cases, the need of real time image processing functions leads to a heavy and high cost equipment, which reduces the number of industrial applications. This paper presents a new concept of image processing hardware to be used in real time operations at low cost. The system hardware named HARVIS is based on only one board which is able to execute one function over all the images in one video frame. The function is hardware selectable among several available configurations. The paralell or sequencial association of the necessary boards allows some complex functions to be performed at video frame speed. In this paper the application of this modular architecture to automatic surveillance executed by vision cameras in an open space environment is described.

The paper presents a design concept which eliminates two major weaknesses of existing visual inspection systems: (1) narrow application field and (2) inability to process images with poor contrast or noise distortion. Our system combines two basic inspection principles: (1) Feature Extraction and Comparison and (2) Verification of Design Rules. Inspection algorithms are based on gray scale morphology. Our short time goal is a real-time system which can cope with changing inspection objects and does well with complex, low-contrast images. The long-time goal is a rule-based system, able to translate design specifications of an object into an inspection algorithm.

This paper reports the research performed on using computer vision for the control of the chip-bonding process in the manufacture of micro-electronic IC devices. The ultimate purpose is to develop an automated system to identify and classify the defects during the process of bonding the IC chip to its carrier. Vision algorithms have been developed for identifying defects, such as missing chip, misregistration of the chip, scratches, edge cracks, surface contamination, misorientation, poor eutectic flow, carrier damage. Dark-field as well as bright-field illumination are used separately to create images accentuating the defects. We comment on the limitations of the algorithms regarding their capability and robustness. A prototype production system which implemented the optics, illumination and the algorithms for identification and reporting of the defects for process control is briefly described.

This paper deals with an important problem encountered in automating VLSI wafer probing. In this automation, vision is used for accurately guiding and lowering a probe to make contact with the wafer. In this paper, we discuss various algorithms used in measurement of the distance of the micro-manipulator from the wafer surface. In particular, we describe algorithms for alignment of consecutive frames of the wafer, separation of probe and wafer regions, and getting a clean image of the probe by eliminating traces of the background patterns. We also describe a three-level procedure for obtaining the proximity of the probe from the wafer. These algorithms are verified with the experimental data.

Automatic visual wafer inspection will increase productivity and improve product quality of integrated circuit (IC) chips on wafers. Recently, research on such inspection has been focused on problems for classification of defects on wafers to rectify wafer fabrication errors by comparing them with predefined specification standards. This paper describes the development of a knowledge-based system which classifies defects in the recti-linear type wafer images for VLSI chips. A consultation system shell called CESM (Classification Expert System Maker) has been used to develop the classification system. CESM supports integration of low level processing, feature extraction, and final decision stages.

Machine vision systems and other automated visual inspection (AVI) systems have been proving their usefulness in factories for more than a decade. In spite of this, the number of installed systems is far below the number that could profitably be employed. In the opinion of the authors, the primary reason for this is the high cost of customizing vision systems to meet applications requirements. A three-part approach to this problem has proven to be useful: 1. A multi-phase paradigm for customer interaction, system specification, system development, and system installation; 2. A powerful and easy-to-use system development environment, including a a flexible laboratory lighting setup, plus software-based tools to assist in the design of image acquisition systems, b. an image processing environment with a very large repertoire of image processing and feature extraction operations and an easy-to-use command interpreter having macro capabilities, and c. an image analysis environment with high-level constructs, a flexible and powerful syntax, and a "seamless" interface to the image processing level; and 3. A moderately-priced high-speed "target" system fully compatible with the development environment, so that algorithms developed thereon can be transferred directly to the factory environment without further development costs or reprogramming. Items 1 and 2 are covered in other papers1,23,4,5 and are touched on here only briefly. Item 3 is the main subject of this paper. Our major motivation in presenting this paper is to offer suggestions to vendors developing commercial boards and systems, in hopes that the special needs of industrial inspection can be met.

The basic mathematical formulation of a general solution to the extraction of three-dimensional information from images and camera calibration is presented. Standard photogrammetric algorithms for the least squares estimation of relevant parameters are outlined together with terms and principal aspects of calibration and quality assessment. A second generation prototype system for "Real-Time Photogrammetry" developed as part of the "Digital Photogrammetric Station" of the Institute of Geodesy and Photogrammetry of ETH-Zurich is described. Two calibration tests with three-dimensional testfields and independently determined reference coordinates for quality assessment are presented. In a laboratory calibration with off the shelf equipment an accuracy of 1120th and 1150th of the pixel spacing in row and column direction respectively has been achieved. Problems of the hardware used in the test are outlined. The calibration of a vision system of a ping-pong playing high-speed robot led to an improvement of the accuracy of object coordinates by a factor of over 8. The vision system is tracking table-tennis balls with a 50 Hz rate.

The human visual system has evolved towards a close integration of visual information processing and visual data acquisition. Fast, peripheral, pre-attentive vision uses low resolution input to direct the fixation of the fovea to features of importance in an efficient visual search pattern. Here we describe a system which emulates the multi-resolution aspect of human visual processing to provide computational efficiency in data analysis. The visual task used is the location of specific features in human faces for use in videotelephony. The feature location technique uses a Kohonen-based neural network architecture to permit learning by example. Input data is in the form of a resolution pyramid to emulate the differing modes of human vision. The system is implemented on a RISC-based microcomputer workstation with purpose-built real-time image acquisition hardware. It performs well with both familiar and unseen image data and, with refinement, could form the basis of a useable system.

Traditional neural networks for pattern classification use linear decisions to partition a multivalued high dimensional pattern space. This paper shows that the properties of binary space ({0, 1}N space) make it well suited for these tasks and a simple training algorithm is given. A simple measure of network ordering is used to allow a variable number of clusters and continuous learning.

A three-dimensional object identification methodology based on rigid geometrical constraints and cross-correlation is discussed, and experimental results are given. Comparable results from a nearest-neighbor classifier using simple feature vectors extracted from the object and model projections are also given. Comments concerning advantages of model-driven recognition methodologies are then made.

Object recognition is a major theme in computer vision. In this paper, we present a method of recognizing planar objects in 3-D space from a single image. Objects in a scene may be occluded, and the orientation of the objects is arbitrary. We represent each object by its dominant points, and pose the recognition problem as a dominant-point matching problem. We introduce a measure, known as sphericity, derived from an affine transform to indicate the quality of match among dominant points. A clustering algorithm, probe-and-block, is used to guide the matching. We use a least squares fit among dominant points to estimate object location in the scene. A heuristic measure is finally computed to verify the match.

Least-squares template matching and correlation have long been used for detecting, locating, and quantifying features in images. More recently, binary and grey-level morphology have been used to accomplish similar functions. Least squares techniques involve fitting a function to the image in such a way as to minimize the norm of the error in,L2(Hilbert) space, and result in errors being distributed approximately equally on both sides (+ and -) of the fitted function. Morphological techniques involve fitting a function (i.e., a structuring element) to the image in L_space, and result in all the errors being distributed on the same side of the fitted function. Thus, the final result is completely determined by the worst case error, without regard for the other errors. As a result, morphological techniques are very sensitive to noise. There is a need for a technique falling between these two extremes of "full penetration" (12 space) and "no penetration" (L2 space). Banach spaces (Lp-spaces) provide the basis for such a technique. The Banach-space norm for discretized images has the form II f IIp = [(1/N)ΣIfjIP](1/p)where the summation is taken over all of the N pixels in the structuring element. By an appropriate choice of p, the degree of penetration appropriate to a given type of problem and image noise level can be achieved. This paper presents the mathematical basis for Banach morphology, gives some simple examples, describes possible implementations on existing hardware, and suggests an architecture suited to high-speed implementation.

This paper surveys hierarchical algorithms used in the analysis of image data under hexagonal planar decomposition. Part of the motivation for these algorithms is that practical parallel image processing devices have been based on hexagonal decomposition. The advantages of the hexagonal covering are based on the 'uniform adjacency property: each element is adjacent to exactly six others, shares with each exactly one-sixth of its boundary, and has identical distance between its centroid and those of its neighbors. We describe the septree: a seven-descendant hierarchical data structure based on decomposing a roughly-hexagonal planar region into a central hexagon and its six neighbors. Septree algorithms used for low-level image pre-processing, image segmentation, and feature extraction are surveyed. The results presented here for static two-dimensional scenes can be extended to three-dimensional analogies. These can be used in computer vision models and in time-sequences of images for robots.

This paper presents a method for finding image correspondence by partial shape invariance. The shape invariant features are defined as: the number of keypoints; a set of relative distance between the keypoints and the centroid of an object; a set of edge length between the sequential keypoints in different viewpoints. Shape invariant features within certain viewing range is assumed. Shape features are extracted from edge images,and those edges are converted into polylines or polygons in order to represent shapes in linear features. Multiview models are built based on partial shape invariance. Corresponding points are obtained by comparing input image data with multiview model data.

Many of the programming techniques used in solving two-dimensional problems can be extended to three-dimensions. Here a method is proposed for converting the three-dimensional array representation of an object into its linear octtree description. The method contains two algorithms: (1) conversion of three-dimensional array into set of 0-octants and (2) translation--merging of 0-octants encoded an object. For the three--dimensional array A = { a(i, j, k) I 0<i,j,k<2n-1} ,algorithm(1) requires 0(2 3n) time and algorithm (2) can be executed in linear time with respect to the total number of 0-octants.

We have developed a prototype for a traffic flow measuring system using image processing. The system measures traffic flow parameters such as vehicles' average speed and their spatial occupancy directly from road images. Its features are summarized as follows: (1) The system can stably extract the vehicles using the subtraction-spatial differentiation method and the background updating method, which considers the change ratio of the road brightness under changing surrounding conditions. (2) The system can track vehicles moving as fast as 150 km/h employing real-time gray scale image processing and parallel image features extraction of the HITACHI-IP/200 image processor. (3) In experimental applications to an expressway, the system had good accuracy in the traffic flow measurements, with errors within 10%, even under bad conditions at dusk.

An acousto-optic correlator is considered to verify that the correct text is present on a product and that the text is not skewed or blurred or mispositioned beyond allowed tolerances. For the case study considered, 20 possible labels exist and the presence of the correct one is to be verified. We need not determine which wrong label is present, although this is possible with modifications. We address the resolution and quantization requirements and the capacity of the system. Initial simulation results and real-time laboratory test results are provided. A space and frequency-multiplexed acousto-optic processor is used and described.

Texture analysis has been an area of active research for the last two decades. This paper presents results on the application of two techniques for the analysis of textured images. Specifically, we look at the two problems of identifying and classifying sandpaper samples based on the textural properties created by varying the sizing coat, and detecting and classifying wrinkles within the sandpaper sample. The techniques used for identifying the samples are based on mathematical morphology and the computation of neighboring grey level dependence matrices. The features generated by applying a four grey-level morphological operations to images with a 5 X 5 kernel are used to classify the different textures. The size and shape of the structuring elements, as well as the sequence of operations can be optimized to provide the best discrimination for a particular product. Next, we show that the techniques used for the solution of sizing coat problems have a natural extension to the wrinkle detection problem. The wrinkle detection problem may be thought of as detecting a time-varying signal in a noisy background when processing in the spectral domain. The method that we use is the modified Hough transform. The parameters obtained from this transform, the length, angle, and orientation of the wrinkle, are the parameters of interest to the manufacturer. This paper presents a description of the image processing system used, the algorithms employed for both the sizing coat height measurements and for wrinkle detection, and results obtained for actual data. With over 100 sandpaper samples, the algorithms have proven to be entirely successful, and the system is currently being implemented online in the sponsor's manufacturing facility.

Custom VLSI devices are making possible two dimensional geometric analysis of video images as fast as the data can be acquired by the camera. The APA512 cardset is the first commercial implementation of Video Rate Geometric Analysis. The American Iron and Steel Institute (AISI) has sponsored a study where the APA512 was applied to continuous strip steel production. This paper describes the system implemented and the results that the system provided.

Quartz devices play an important role in the field of radio communication and are also well known for their popular use in electronic clocks and watches. Detection of scratches and cracks on the crystals is the key quality control in their production. Difficulties encountered in these inspections are due to the fact that such defects are so thin and short that they are almost indiscernible from the blurred textural background of the crystal unless a special illumination and torsional viewing mechanism are provided. In this paper, image processing and pattern recognition techniques are introduced for the automatic detection and delineation of these indiscernible imperfections so that high quality in crystal production can be assured.

A general purpose algorithm for visually guiding a robot to automatically follow a seam is presented. The algorithm was designed for automated welding applications but may be used for other seam tracking problems such as the inspection of machined part edges. The algorithm is particularly useful in its ability to work on low contrast seam images and is robust enough to ignore higher contrast scratches and markings near the seam, allowing for the use of conventional illumination techniques. The seam tracker works by continuously measuring an offset from a nominal position. The offset can be stored to modify a coarsely pretaught robot path or can be used as an input to a real time trajectory control loop. The seam position is computed using a matched edge filter and a majority voting scheme based on features measured from the current image frame as well as from past image frames. The success of this algorithm is based on several generally valid assumptions and rules. One such assumption is that the seam is nearly vertical in the image or can be made vertical by rotating the image data by an angle based on a pretaught robot path or by using results from previous image frames. By assuming that the seam width and position is smoothly varying, these parameters can be fed back from previous image frames to maintain tracking. An implementation of this algorithm for a real time weld seam tracking application is discussed.

In this paper we discuss methods currently being implemented for the visual inspection of defects found on ground metal components. These are then identified and located for the purpose of removal/regrinding using a robotic manipulator. The visual sensing system and 3 dimensional vision algorithms are described.

The need for low-cost, real-time, image processing for automated inspection and other industrial applications has led to considerable effort being directed at many novel computer architectures. Two main avenues of work have become apparent: the use of powerful parallel architectures and the use of pipelined processors. The former while offering great flexibility, have, to date, been associated with high cost. The latter, being essentially simpler processors can produce considerable cost savings but have generally been inflexible and provided a limited number of functions. Pipeline processors have generally found application as pre-processors for use with parallel machines or in image enhancement for human operators where relatively simple processing is required. The paper describes the development of an adaptive pipeline processor which offers the potential cost efficiency of large scale integration together with the flexibility of an adaptive system. The processor concerned accepts digitised video information from any standard video source and performs real-time processing on it. Each identical processor element (PE) can be programmed by a separate controller over a high speed communications channel, and can perform a range of operations including filtering, averaging, edge-detection, line-thinning, thresholding, scaling and inversion. Synchronisation information is also processed by the PE allowing any number of elements to be cascaded without the need for a frame store. A typical image processing arrangement would consist of a series of identical PEs connected in series and a separate control computer which is responsible for configuring the system. The absence of frame buffering within the system greatly reduces its cost and provides true real-time operation. Since each PE may be reconfigured in real-time the parameters and functions of each element can be modified to suit the image. This permits the processing to be adapted to cater for changing lighting conditions or a change of scene. Since each PE will be implemented as a single, identical, VLSI circuit, the arrangement is potentially very cost effective.

Kiwivision II is a hybrid vision architecture under development at the Department of Scientific and Industrial Research (DSIR) in Auckland, New Zealand. It consists of a reconfigurable network of transputers interfaced to a commercially available family of pipeline processing modules. Images can be loaded directly from the pipeline processor bus into image/data stores which are memory-mapped into the transputer network. The array topology is variable, can be dynamically reconfigured and can be expanded with the addition of extra transputer processing modules. This paper describes the parallel implementation of several useful vision algorithms on Kiwivision II, and demonstrates the usefulness of its hybrid structure.

Parallel computers are playing an increasingly important role in areas such as fluid dynamics, particle physics, simulation, and computer vision. In particular, regular data structures and the complexity of computation of most computer vision algorithms make them ideally suited for implementation in parallel computers. In the past, most parallel algorithms have been developed for a given target architecture. Recently, generalized approaches to parallel program design, where architectural issues are postponed to the last step of the design process, have been gaining momentum in the research community. A formal approach for the design of parallel programs is to iteratively refine the specifications. In this paper, we demonstrate the use of this approach to split and merge method of segmentation. The starting point for the design is the general specifications of the divide-and-conquer paradigm, and the end result is the design of a program for the split and merge segmentation on a hypercube architecture. The performance is evaluated in terms of speed-up and efficiency of the processors.

In this paper we discuss applications of the Connection Machine to various robot vision problems. In particular we investigate backpropagation used for terrain typing and as part of a model-based computer vision system. Mapping the backpropagation algorithm onto the fine grain architecture of the CM-2 is sketched. We discuss the interplay between data-level and control-level parallelism in model-based vision systems.

Though they boast many attractive features, major problems exist in using an artificial neural network to represent knowledge. In particular, network training is usually a considerable task. Moreover, the network connections in the trained network bear no obviously derivable relationship to the component structures or concepts existing in the knowledge which has been learned. Research described here attempts to tackle both these issues in the context of edge interpretation in machine vision. The basis for a novel artificial neural network architecture is proposed which supports the direct representation of domain knowledge, in this case, the relationship between simple edge patterns and objects represented by the edge patterns. This means that the time-consuming training cycle can be avoided because network weights are directly calculated as functions of the edge structures which make up each object so that connection weights have a natural interpretation in terms of concepts comprising an object. The notions of arc and arc relation space have been developed as the cornerstones of this architecture. Their analysis in this limited domain indicates that such spaces may have a significant part to play in the general context of object recognition based on edge structures in machine vision.

This paper developes a new method for the pixel classification of an intensity image. A neural networks of non-linear analog neurons have been shown extremely effective. This problem is considered as an optimally classification of an image based on their original activation. Optimization is defined in terms of energy which is a function of neurons the output values which vary continuously. The neurons are modelled as amplifiers which have sigmoid monotonic input-output relations. A synapse between two neurons is defined by a conductance which connects the output of neuron to the input of another neuron. The net input current to any neuron is the sum of the currents flowing through the set of resistors connecting its input to the outputs of the other neurons. We have formulate the problems in terms of desired optima, subject to certain constraints.

In the work presented in this paper, graphical representations showing the typical evolution of the mapping function of the various neurons in a three-layered feed-forward network, are used to help gaining the necessary insight to error backpropagation training. The study of the learning behaviour of a simple object classifier is presented, and commented.

For high-speed vision systems it is necessary to find appropriate trade-offs between hard- and software structures. Concurrent processing depends on the networking facilities, the communication between different processing units and system modules. This paper deals with new results obtained at IPA while comparing different possibilities in the hardware and software domain of network topologies and strategies. By way of examples useful features as well as restrictions will be described.