This paper presents a solution to the problem of recognition and location estimation of complex three dimensional objects in a robotic workspace. We initially assume 3-D data is available in the form of a range image measured by an active triangulation system. The system was designed to meet three criteria: hardware implementation, optimality and real-time execution speed. The assumptions are that a scene contains several objects which may be at any position and orientation and may be arbitrarily overlapping. Each object consists of planar and slowly curving surfaces. The design criteria lead to an approach distinguished by the use of windows. One system using this approach was designed to meet the optimality criterion. Then simplifying approximations were made to improve speed, while maintaining similar performance. The basic approach to segmentation is to divide the range image into windows, classify each window as a particular surface primitive, and group like windows into surface regions. Segmented surface regions are matched with surfaces in an object model using a simple search constrained by a geometric similarity measure. Finally, we describe another system which uses a similar approach with visible light images of the same type of scene.

We first discuss criteria that allow one to distinguish between the many different types of object representations that are currently used for visual recognition tasks. We then apply these criteria to describe the versatile planar form representation used by FOVEA, a recently developed invariant visual recognition system. Current efforts to extend FOVEA to handle non-planar (3-D) objects are described.

A simple criterion is proposed for the selection of contour points from a hierarchy of filter responses. The operators are the first derivatives of 2-dimensional Gaussians with different widths whose positive and negative parts are separately normalized to +1 and -1, respectively. The responses of the convolution of this 2-dimensional gradient operator with a gray value picture are vectors whose magnitudes and phases give useful information about differences of mean gray values across contours, and about the exact direction of the maximal intensity changes. Closed chains of contour points define regions whose gray values can be reconstructed approximately from the attributes of contour points. The regions of the segmented pictures are appropriate features which facilitate the matching process with scene models.

A new approach to dynamic edge detection uses the order of passage over a triad of equidistant detectors to compute the direction and velocity of a translating edge. The paper examines a parallel architecture for extracting low and intermediate level intrinsic images from moving objects starting with this low complexity operator. The approach is entirely parallel and based on non-quantitative logic processing.

A common industrial problem is to load and unload process machinery. A feasible solution to a large subset of this problem has been demonstrated using sensor-equipped robot systems. These systems combine both remotely and locally sensed data with heuristic analysis algorithms. These algorithms can successfully direct a robot to acquire a part from a jumbled heap. This paper presents a heuristic vision analysis algorithms which are based on neighborhood operators. The algorithms combine global characteristics and local matches to graspable inside or outside edge pairs, the pattern of a holdsite. The properties inherent to neighborhood operators permit smoothed local edge information to be extracted from images of the target class of parts.

Color textures are modelled by a set of second order spatial averages pΔ(C1,C2) where C1 and C2 are the color codes of two pixels distant of Δ on the texture field. The parameters of this model may be computed from a color texture field using a dynamical clustering algorithm which replaces the (R,G,B) coordinates of each pixel by a simple code.

Decision processing on colours demands something more than the exact colour science which has largely dominated the design of colour inspection systems until the present. The work to be described challenges the traditional view by the introduction of the concept of fuzziness to broaden the decision aspects in determining colour by artificial means. Here colours are regarded as fuzzy sets described by so called 'fuzzy membership functions', which are subsets to a universe of discourse (in this case a chromaticity space). Members of these subsets are neither wholly inclusive nor exclusive to the set itself, hence giving rise to fuzziness in the definition of a colour. In a typical application, fuzzy connectives are used to perform operations of union and intersection between membership functions so as to produce a resultant fuzzy set which is characteristic of several colours as described by a simple mathematical equation.

We present a new segmentation algorithm based upon a region growing technique. An initial segmentation is obtained using a MERGE procedure described by Pavlidis. We then build an adjacency graph of regions pairs.

We present an algorithm for determining the position and orientation (pose) of an unoccluded three-dimensional object given a digitized grey-scale image. A model data base of characteristic views is generated prior to run-time by merging perspective views containing the same feature points, such as points of sharp curvature in an edge map, into common characteristic views. The run-time algorithm consists of (1) extracting an edge map from the image; (2) locating feature points in the edge map; (3) using intrinsic properties of the feature points in the image, such as signs of curvature, to rank the characteristic views for the object according to their likelihood of correspondence to the image; (4) for each characteristic view in the ranking, matching properties of the image feature points and object feature points in order to generate potential correspondences; and (5) verifying the most likely correspondences by examining a least-squares fit in each correspondence. The fit yields a rotation matrix that defines the pose of the object.

The Adaptive Least Squares Correlation is a general and flexible technique for many different image matching problems. It allows for simultaneous local geometrical image shaping and radiometric corrections, whereby the system parameters are automatically assessed, corrected and thus optimized with respect to the specific signal during the least squares iterations. Precision and reliability measures can be developed to assess the quality of the match. A stabilization and improvement of the correlation procedure can be achieved through the simultaneous consideration of object point intersection conditions from conjugate rays and other sensor and object constraints. These geometrical constraints limit the search area size, reduce the number of alternatives, increase the precision and reliability of matching and provide simultaneously 3D-point positioning information. The method can be applied to correlation, object detection and measurement, and image tracking, while the 3D-information provided can be readily utilized for tasks requiring inspection, manipulation, object tracking and navigation. As an exciting new prospect the method can be applied to more than two images at a time. This paper outlines the basic concept of the technique.

This paper is concerned with the problem of recognizing complex objects rapidly and flexibly. The strategy is based on three main concepts: the use of a generalised local feature detector, an extended learning algorithm, and unique object structure. Most of the paper is devoted to a discussion of the strategy and the architecture that was developed to tackle this problem and the extent of its generality. Implementation and algorithmic considerations are given only briefly as they have already been described in detail elsewhere. A summary of test results is also given.

This paper presents a maximum likelihood approach to 3-D complex-object position estimation. To this end a simple 3-D modeling scheme for complex objects is proposed. The surface of an object is modeled as a collection of patches of primitive quadrics, i.e., planar, cylindrical, and spherical patches, possibly augmented by boundaries. The primitive surface-patch models are specified by geometric parameters, reflecting location, orientation, and dimension information of the 3-D primitives. The object-position estimation is based on sets of range data points, each set associated with a model primitive. The range data may be obtained by laser range finders or by passive or active stereo vision. Probability density functions are introduced that model the generation of range measurement of points on the 3-D primitives. This entails the formulation of a noise mechanism in three-space accounting for inaccuracies in the 3-D measurements and possibly for inaccuracies in the 3-D modeling. A formal probabilistic mechanism is derived to combine the various pieces of 3-D information obtained from the different data patches. In this way special attention is directed at appropriately weighting the estimated local geometric parameters of the object primitives to arrive at an optimal overall object-position estimation. In this paper the problem of matching object features to measurement features is not addressed. The work reported here appears to be the first to treat object positioning within a formal statistical estimation framework. The techniques used are based on asymptotic analysis, and are not restricted to range data but can be applied to any type of data. They permit controlled decomposition of a large problem into small problems where maximum likelihood estimation or Bayesian estimation or recognition can be realized locally, and these results can be combined to arrive at globally optimum estimation or recognition.

A method is proposed for the determination of a progressive polyhedral approximation of 3-D digitized surfaces whose points are located on a regular lattice. It relies on an iterative and adaptative splitting of the triangular faces of an initial polyhedral surface. Assuming a bijection between the digitized surface and its approximation, a partition of the data base is operated. The algorithm allows for the measurement of the local quality of the approximation and avoids the generation of ill-defined triangles with sharp corners. Its low computational complexity permits the approximation of very large sets of points (hundreds of thousands).

An adaptive algorithm which has the capability of simultaneously identifying several shapes is introduced and derived. The identification of the irregular objects (shapes) can be accomplished over a wide range of scale factors, and independent of rotation and translation. It is demonstrated that excellent identification performance is obtained under the most adverse conditions. Specifically, it is demonstrated that the algorithm performs well in the presence of both noise and occlusion. Additionally, the matching process produces estimates of rotation, scaling, and translation for the various irregular objects. The algorithm is robust in the sense that adjustments can be made to accomodate both extreme noise and memory restrictions. It is demonstrated that the computational requirements for the procedure are not excessive.

This paper describes a segmented-region based stereo reconstruction of planar-surface objects. Since there are a great number of matching-points in edge based stereo while there are a much smaller number of matching-regions in segmented-region based stereo, matching can be achieved much easilier in segmented-region based stereo than in edge based stereo. Images are first segmented on reduced images. Boundaries of segmented regions are refined on the original images. Similarity of two regions in both images determines match of regions. A set of points is selected from both matched regions to obtain an equation of a plane in 3-D space. The projected region on the plane is a surface of an object in 3-D space. A demonstration is achieved on images of our laboratory indoor scene.

A composite surface model is a data structure in which a stream of surface information from different sources and different viewing positions is integrated. A composite surface model may be used for learning about objects, planning actions and monitoring the execution of actions. This paper describes a representation for a composite surface model based on small planar patches. The primitive symbol of this representation, the generalized surface patch, embodies mutual constraints between uncertainties in position, spatial extent and orientation. Techniques for integrating surface information from different sources, and for dynamically updating a composite surface model are described.

The robot working space protection system presented is based on visual perception. In this system any intrussion in the working area are detected by their movement. The evaluation of the collision risk is based on the analysis of the information given by the vision system and that corresponding to the position of the robot which is acquired by its own sensors The vision system differentiates among the movements of the robot itself, those of the tools and those of the usual scene components from those of unexpected events in order to detect them. Then the system studies the possible intersection of the bounding rectangles containing the mobile elements seen during the trainning phase and the detected objects. The tracking of the robot trajectory allows to foresee in advance their future movements and thus to foresee the collision risk. This allows the system to generate the stopping order with time enough in case the invaded zone has to be occtpiedsoon by the robot. The robot won't be sttoped if its trajectory is not in conflict with the detected obstacle. The system might be useful either in the coordination of several robots in a working cell doing not syncronised tasks, or in the protection of a robot working in a machine tool environment.

In this paper we present two classes of algorithms for real-time tracking of target moving on natural background. The first solution is based on linear features matching by Hough shape transform with a simple velocities based discrimination. The second one is a real-time image segmentation algorithm based on adaptative statistical clustering and on efficient texture measures.

This paper describes initial progess toward the development of a holarchical robot vision system. The holarchical concept is an organisational philosophy which is borrowed from system sciences and is concerned with the organisation of interacting complex systems. The major levels of this holarchy correspond to the peripheral, attentional, and cognitive visual processes. The approach is exemplified by describing the development of a contour-following boundary-based object recognition vision system. The extension of the holarchy to incorporate further visual cues is considered.

This paper is concerned with an original procedure which has been designed to determine moving edges. An image sequence is considered as a 3D-space (x,y,t) and a moving local 2D-edge is modeled as a small planar patch in this 3D-space. A maximum likelihood procedure enables to simultaneously detect such planar patches and estimate their orientation (i.e., spatial direction of the corresponding 2D-edge element and perpendicular component of its displacement). The computational aspect of this method merely consists of convolution operations by considering appropriate local 3D-neighborhoods. This early processing is part of a robot vision algorithm for an obstacle avoidance task, currently developed at the laboratory.

In this paper, the DRF (Difference of Recursive Filters) method is proposed for stereo vision. One obtains the BLI's (Binary Laplacian Image) of the stereopair images by DRF method and the disparities are found by the correlation between the BLI's. Some experimental results are presented also.

This paper describes the construction of 3D binairy images using one camera and a rotating object or a moving camera on a robotarm. Two methods are combined. First polygonal convex hulls of object cross-sections are found with the volumetric approach. Then a stereovision method is applied to get hold of the non-convex part of the cross-sections. The binairy 3D image is represented by a stack of polygons. An example is given.

Artificially generated test sequences are of major importance in the field of image processing. A new procedure is described, which represents an economic and powerful generation process and allows a great variety of objects, motion and illumination. The internal description of the 3-D objects is based on the representation of their surface elements. This permits the generation of arbitrarily formed and textured objects.

A design of computer software for machine vision of roving robots is presented. We have identified the basic requirements for the guidance and navigation of roving robots as directional guidance, obstacle avoidance, orientation determination, range finding, and object identification. To meet these requirements, we developed techniqes for safety path planning for roving robots, proposed methods for shadow identification and object discrimination, and introduced the concept of scene layout footprint and 3-D maps for landmarks. Analytical study is supported by experimental results.

Guidance of autonomons transport systems used in flexible manufacturing systems is usually performed by using either photoelectric cells or leading wires. This work refer to the system developped to track painted strips on the floor by means of a TV camera. The system designed is able to recognize and identify a pattern on the floor in a factory environment and to deal with the guidance of a transport system according to the commands received from the control unit which establishes its itinerary.

In this paper a heuristic approach to the navigation problem is presented, in which the task complexity is distributed among different components whose global performance is guaranteed by a run time correction mechanism. It is shown i) how information about free space is coded in a symbolic data base, ii) how some motion capabilities of the actor can be represented and iii) that the selected path can be covered in different ways on the basis of different strategies.

In this paper, a fast and accurate range-finding vision system is described. On request, it measures the three-dimensional coordinates (x,y,z) of a single point or of a series of points on the surface of the scene. The scanning order is not fixed, but can be chosen freely. In fact, the scene-scanning process is driven in close interaction with the segmentation algorithms. The sensor is composed of a laser, a two-degrees-of-freedom deflection unit, pointing the laser-beam on the scene, 3 linear high resolution CCD photodiode arrays, observing the laser-spot through special optics. The system has been designed as an intelligent peripheral to a hostcomputer and is implemented in a 16-bit microprocessor environment. The hardware is roughly described. Two implemented segmentation algorithms, reducing 3-D coordinates to a description of the scene with planes are explained and evaluated.

Object recognition is a difficult task for single sensor systems (e.g. machine vision) in unconstrained environments. A useful approach is to combine sensory data from more than one source to overcome these problems. However, using multiple sensors poses new problems with respect to coordination of the sensors, strategies for their use and integration of their data. In this paper, these problems are explored and solutions posed for the task of object recognition using passive stereo vision and active tactile sensing.

Robots experience a three-dimensional binary world. Robot vision should therefore consider 3-d binary images. Rather than the acquisition, the processing of such images is the topic of this paper. 3-d images tend to contain at least two orders of magnitude more data than 2-d images. This means that the urge for speed is correspondingly stronger. Moreover, the state space of robot coordinates may be of still higher dimension and often a fast reaction to changes in the robot environment is wanted. Speeding up image processing for robot vision is likely to be a permanent need in the years to come. This paper describes some techniques to make 3-d binary image processing more efficient. Starting out from the typical needs and methods in robot vision the operations and corresponding optimal data representations are discussed. Cellular logic operations and of these skeletonization in particular are found to play a key role. Extensive use is made of the concept of region of interest, which permits to skip background when operating. The use of look-up tables, so effective in 2-d processing, is hampered by memory restrictions but still proves valuable when handled with care. A table-driven method for 3-d skeletonization is given as an example.

A system for automatic adaptation of an image understanding system to new objects and changes in industrial scenes is presented. The representation of different types of knowledge and their utilization during the adaptation process will be discussed and demonstrated on a practical example.

This paper deals with the extraction of multiple features and with iconic segmentation of images, with the purpose of providing a description of image entities like, for example, closed contours. In particular we will show how multiple sources of information can be integrated in a Iconic Data-Base, and how this data-base can be suitably organized for symbolic manipulation. Finally, the heuristics used to segment images of a simplified real world (a low scale model of an office-like environment whose objects are composed of planar surfaces) will be described, together with their actions on a Symbolic Data-Base.

The success of autonomous mobile robots depends on the ability to understand continuously changing scenery. Present techniques for analysis of images are not always suitable because in sequential paradigm, computation of visual functions based on absolute values of stimuli is inefficient. Important aspects of visual information are encoded in discontinuities of intensity, hence a representation in terms of relative values seems advantageous. We present the computing architecture of a massively parallel vision module which optimizes the detection of relative intensity changes in space and time. Visual information must remain constant despite variation in ambient light level or velocity of target and robot. Constancy can be achieved by normalizing motion and lightness scales. In both cases, basic computation involves a comparison of the center pixels with the context of surrounding values. Therefore, a similar computing architecture, composed of three functionally-different and hierarchically-arranged layers of overlapping operators, can be used for two integrated parts of the module. The first part maintains high sensitivity to spatial changes by reducing noise and normalizing the lightness scale. The result is used by the second part to maintain high sensitivity to temporal discontinuities and to compute relative motion information. Simulation results show that response of the module is proportional to contrast of the stimulus and remains constant over the whole domain of intensity. It is also proportional to velocity of motion limited to any small portion of the visual field. Uniform motion throughout the visual field results in constant response, independent of velocity. Spatial and temporal intensity changes are enhanced because computationally, the module resembles the behavior of a DOG function.

Basic robot planning and control problems such as vision-based motion planning and feedback control are well suited for parallel processing by low-cost, special purpose VLSI devices. A vision-based fast planning and control unit based on commercially available systolic chips (binary array processors) is presented. A new parallel algorithm, the coordinated border-follow algorithm, for determining admissible movements in obstacle-filled environments, has been developed. Because dataflow is simple and regular and multiprocessing is used, the algorithm is well suited for VLSI implementation.

Machine vision is an emerging technology and an integral element of a factory automation concept embracing robotics, CAD/CAM, CIM, FMS and numerous related capabilities. Although still in its infancy - especially in the methodology of performing symbolic domain tasks, it surely plays a vital role in evolving manufacturing from today's fixed automation to flexible future automation. This paper describes the elements of productivity and speed improvement currently achieved with the aid of a machine vision system. The system is an integrated electro-optical system which automatically reads mark sense labels and forwards the encoded data to sort controllers. Also, through the description of this automatic sorting system design - in both software and hardware senses, it will be recognized that complex scene understanding can be carried out successfully under elaborate use of a priori knowledge about the scene to be recognized.

A simple concept for extracting relevant digital data from an image is described. It is based on a very flexible form of sub-sampling and is well suited to a low cost implementation of a smart camera. A prototype camera which has been built is described together with a few applications in metrology, motion detection and bar code reading.

The principle difficulties encountered when implementing a co-operation between a sensor device and an industrial robot are enumerated considering the practical example of an arc welding task: seam line localization and profile geometry evaluation. The required functions for both the robot and the sensor are presented. An optical sensor that uses structured light has been developed and integrated within a robot end effector. In order to be able to process the signals of the sensor adequately, an adaptable robot control unit is used. Special attention is given to the interface between sensor and robot control. The information processing within the robot control unit is described. A short outlook gives a survey of predictable further applications.

K.I. Laws proposed a texture analysis method called "Texture energy measure", yieldina good classification results. We show that this method maybe implemented optically using birefringent crystals and polarisers. This optical processor can replace the computer for the major part of the computation required in texture processing. The ontical version is particularly attractive due to its reasonable cost and its high efficiency that may be estimated in the neighbourhood of 1 G operations per second using presently available components. We present some results that show the feasability of the setup.

For scene analysis by object identification, a new method is presented which involves a structural representation of the objects the components of which are local patterns. These local patterns are detected with a hypothesis accumulation technique analogous to the generalized Hough transform but adapted to polygonal contours as pattern representations. The object identification is controlled by a prediction-verification procedure. When a first local pattern is found by hypothesis accumulation, according to the structural model of the object, a second one is predicted, i.e. its direction and the window in which it is expected are given. Its detection is then verified by hypothesis accumulation with these research parameter values. Such an identification method gathers the advantages of both the prediction-verification and the hypothesis accumulation approaches which are respectively, the ability to make very few hypotheses for object recognition, and the capability of handling variations in polygonal contour segmentation. This method has been applied to 2D-scenes of partially observed pieces and the reported results prove its efficiency.

It is agreed that computer vision system need to be integrated whithin advanced robotics systems (3th generation robotics). Integration of vision is made difficult because of the real time constraints and the highly specialized nature of the control and the perception modules. In this paper we present the programing of the experimental robot support of LIMSI under Unix. Three main lines of programming are discussed: object recognition with a camera, on line and off line programming of decision procedures and the control of two manipulators. A robust calibration method that does not require previous knowledge of the sensor caracteristics is used. Object recognition is carried out as follows: multilevel sampling, edges detection, clasification, features computing and search in a data base. These functions are performed by a dedicated computer, using a decentralised host processor. This computer structure helps solving the portability, cost and compatibility problems. The adopted solution to avoid the difficulties of Unix in the control of real-time processes seems to be a good compromise that allows to exploit the "universality" of Unix in the domain of robot programming. The flexible assembly cell includes two six degrees of freedom manipulators and peripheral equipment such as a conveyor belt. The programming of this cell for the robotisation of assembly sequences of an automobile shock-absorber is an experimental synthesis of the developed programs. The problem is one of the "canonical" experiments of the French National Research Project in Robotics (ARA program).

The advent of advanced computer architectures for parallel and symbolic processing has evolved to the point where the technology currently exists for the development of prototype autonomous vehicles. Control of such devices will require communication between knowledge-based subsystems in charge of the vision, planning, and conflict resolution aspects necessary to make autonomous vehicles functional in a real world environment. This paper describes a heuristic route planning system capable of forming the planning foundation of an autonomous ground vehicle.

The Differences of Gaussians (DOGs) are of fundamental importance in edge detection. They belong to the human vision system as shown by Enroth-Cugell and Robson [ENR66]. The zero-crossings of their outputs mark the loci of the intensity changes. The set of descriptions from different operator sizes forms the input for later visual processes, such as stereopsis and motion analysis. We show that DOGs uniformly converge to the Laplacian of a Gaussian (ΔG2,σ) when both the inhibitory and excitatory variables converge to σ. Spatial and spectral properties of DOGs and ΔGs are compared: width and height of their central positive regions, bandiwidths... Finally, DOGs' responses to some features such as ideal edge, right angle corner, general corner..., are presented and magnitudes of error on edge position are given.

The method generates a set of 3-D coordinates of points situated on surfaces of the observed 3-D scene. It is based on a spatial triangulation technique combined with structured lighting. Projection of a 2-D rectangular lattice allows the capture of all the available 3-D information of the observed scene in only one 2-D image. Precise alignment and positioning procedures of lightprojector and camera are avoided by an automatic calibration method. After a short comparison with Moire-techniques, the principles of the method and its mathematical formulation are described.

The sampling and reconstruction error that arises if a (not necessarily bandlimited) scene is reconstructed by a discrete convolution is estimated in the L∞ and L2 norms, including the effect of sample-scene phasing. General conditions on the underlying filter are presented which allow to control this error in both norms. Several types of reconstruction filters are constructed on base of this approach, and spline convolution of arbitrary order serves as a typical application.

The most interesting sensor-systems that can be used advantageously in flexible production, not only for quality control purposes, are image processing systems. The use of one or more electro-optical sensors, e.g. matrix or linear CCD-arrays, laser scanners etc., combined with an image processing unit and a host computer leads to sophisticated system configurations. Yet a clear understanding of these configurations, both in software- and hardware-level, is necessary to make these systems flexible and intelligent as needed. As a consequence new hardware and software concepts are required that could be integrated into image processing units for industrial applications. A time sequential, dynamically configurable image processing system is a good approximation with adapted software tools - and here especially the powerful BILDLIB of IPA - to meet industrial needs.