Two fundamental issues in sensor fusion are (1) the definition of model spaces for representing objects of interest and (2) the definition of estimation procedures for instantiating repre-sentations, with descriptions of uncertainty, from noisy observa-tions. In 3-D perception, model spaces frequently are defined by contour and surface descriptions, such as line segments and planar patches. These models impose strong geometric limitations on the class of scenes that can be modelled and involve segmentation decisions that make model updating difficult. In this paper, we show that random field models provide attractive, alternative representations for the problem of creating spatial descriptions from stereo and sonar range measurements. For stereo ranging, we model the depth at every pixel in the image as a random variable. Maximum likelihood or Bayesian formulations of the matching problem allow us to express the uncertainty in depth at each pixel that results from matching in noisy images. For sonar ranging, we describe a tesselated spatial representation that encodes spatial occupancy probability at each cell. We derive a probabilistic scheme for updating estimates of spatial occupancy from a model of uncertainty in sonar range measurements. These representations can be used in conjunction to build occupancy maps from both sonar and stereo range measurements. We show preliminary results from sonar and single-scanline stereo that illustrate the potential of this ap-proach. We conclude with a discussion of the advantages of the representations and estimation procedures used in this paper over approaches based on contour and surface models.

In this paper, we introduce a new algorithm for modeling the structure of 3-D objects from multiple viewing directions using an integration of active and passive sensing. Construction of the structural description of a 3-D object is composed of two stages: (i) The surface orientation and partial structure are first inferred from a set of single views, and (ii) the visible surface structures inferred from different viewpoints are integrated to complete the description of the 3-D object. In the first stage, an active stripe coding technique is used for recovering visible surface orientation and partial structure. In the second stage, an iterative construction/refinement scheme is used which exploits both passive and active sensing for representing the object surfaces. The active sensing technique projects spatially modulated light patterns to encode the object surfaces for analysis. The visible surface orientation is inferred using a constraint satisfaction process based upon the observed orientation of the projected patterns. The visible surface structure is recovered by integrating a dense orientation map. For multiple view integration, the bounding volume description of the imaged object is first constructed using multiple occluding contours which are acquired through passive sensing. The bounding volume description is then refined using the partial surface structures inferred from active sensing. The final surface structure is recorded in a data structure where the surface contours in a set of parallel planar cross sections are stored. The system construction is inexpensive and the algorithms introduced are adaptive, versatile and suitable for applications in dynamic environments. We expect this approach to be widely applicable in the field of robotics, geometric modeling and factory automation.

This paper describes the software architecture used to construct a multi-sensor knowledge-based Autonomous Target Recognizer (ATR). An Intermediate Symbolic Representation (ISR) of processed data is employed to provide a very powerful method of associative access over data events and their features, thereby supporting data fusion algorithms at the symbolic level. This architecture supports data fusion from multiple sensors, and its operation is described here using MMW range and IR intensity data.

The vacuum of space presents special problems for optical image sensors. Metallic objects in this environment can produce intense specular reflections and deep shadows. By combining the polarized RCS with an incomplete camera image, we have been able to better determine the shape of some simple 3D objects. The radar data is used in an iterative procedure that generates successive approxima-tions to the target shape by minimizing the error between computed scattering cross-sections and the observed radar returns. Favorable results have been obtained for simulations and experiments recon-structing plates, ellipsoids and arbitrary surfaces.

The objective of this paper is to present some geometric techniques for fusion of gray scale intensity images with structured lighting images for scene analysis. Certain 3-D information, such as surface orientation, is obtained by numerical methods of optimization techniques with boundary conditions of structured lighting grid curves and occluding curves.

A procedure is described by which a model can be generated automatically from multiple range and intensity images of an object. The procedure extracts feature points from a series of images, determines corresponding points in various views, and transforms (rotates and translates) all extracted points to a single frame of reference. Use of points allows both efficient solution for transformations and compact coding of many types of features. However, once the transformations between views have been determined, all original data can be brought into a single frame of reference as desired to generate many different models. An implementation which constructed models of several relatively simple objects is described in detail. Although both random and systematic errors are present in range and intensity data, the procedure and algorithms are sufficiently robust to overcome these deficiencies. Uncertainty in final models was on the order of 1mm (1% of object size), approximately the same as the average deviation of the range data. Limitations are discussed, as well as applications in object recognition, CAD/CAM, and computer graphics.

In this paper we review recent work in representing generic, or basic level, objects. Our representatation is frame-based and includes spatial information in the form of a set of aspects. The representation will be used for recognition of range-imaged objects. The paper describes the structured-lighting system and the vision algorithms used to process the data and presents some preliminary results.

Measurement of the Gaussian and principal curvatures at points on smooth object surfaces is important to robotic vision applications for determining surface regions which are convex, concave or planar. Accurate measurement of the directions of principal curvature can determine the orientation of objects such as cylinders and cones. Unfortunately the accurate measurement of Gaussian and principal curvature and directions of principal curvature is very difficult in the presence of noise, using conventional methods which determine depth and local surface orientation at points. Determination of the Gaussian and principal curvatures of a smooth surface, parametrized by image coordinates and height above the image plane, requires the measurement of the second order variations of height with respect to image coordinates. Noise inherent to depth measurements obtained from a laser range finder will be extremely compounded when computing second order derivatives. Surface normals (i.e. first order variations) obtained from photometric stereo techniques are not determined accurately enough for a low error measurement of their rate of change. This paper expounds upon an idea first presented in [Woodham 1978] of using a reflectance map to determine the viewer-centered curvature matrix. Accurate measurement of this matrix, which consists of the second order variations of object height with respect to image coordinates, enables accurate measurement of Gaussian curvature and the principal directions of curvature. The method presented by Woodham to obtain the viewer-centered curvature matrix yields an underconstrained solution and requires auxiliary assumptions about the curvature of the object surface for a unique determination. Presented here is a technique using multiple light sources which not only uniquely determines the viewer-centered curvature matrix in the absence of auxiliary constraints, but overconstrains the solution for accurate measurement in the presence of noise. Other insights are given into obtaining more accuracy using directional derivatives of an image function, and positioning the light sources so as to generate a more static reflectance gradient vector field.

A unified approach to instantiating model and camera parameters in the verification process is presented. Recognition implies the generation of a hypothesis, a map between projected model data and image data. An important issue remaining is the instantiation of model and camera parameters to verify the hypothesis. This "camera pose determination" is formulated as a nonlinear least squares problem, with functions minimizing distance between the projected model and image data. This approach treats camera and model parameters the same, simplifying the camera calibration problem. An original data structure Coordinate Trees with Null Com-ponents models the objects in the image. With this calculation of analytical first and second partial derivatives (with respect to parameters of model and camera) are now made possible. The application of various numeric techniques are compared, with tables displaying convergence results for various models and parameters. Minimal information is required, including the absence of depth data. This makes the algorithms robust in noisy images as well. Extensions to vision applications with general models is outlined.

This paper presents an algorithm for identifying and locating an object from a set of objects. The algorithm is designed and implemented in two parts. The first part identifies the object using an automatically generated set of constraints, while the second part determines the displacement and orientation of the object. The novelty of this algorithm is in its use of three-dimensional data which are obtained from projection of parallel laser light planes. The knowledge that laser light planes are parallel to each other allows automatic discovery of various constraints from the three-dimensional data. One constraint is based on collinearity among various points and another constraint on coplanarity among various segments of the three-dimensional data. These automatically derived constraints, then, are used in a tree search algorithm for object identification. After the identification routine, a set of interpretations are generated. An interpretation is the assignment of each sensed (three dimmentional) data point to a specific edge of the object. An interpretation, however, does not define the exact position of the data point on the specific edge. Given a set of these interpretations, the fitting algorithm recovers the rotation and translation transformation parameters of the object with respect to a known origin. It is shown that a minimum of six interpreted data points are required. The selection of these six points is guided by three constraints, based on whether these points are collinear, coplanar, and spanning the space. Alternatively, a least-squared method is given which uses all, the available interpretations and thus no selection of points is required. Sample applications to various objects are presented. It is also shown that this algorithm is robust with respect to noisy data.

A spherical model for fusion of multisensory data into 3-D spatial information is presented. It is the combination of existing models in visual, thermal, radar and other sensing systems. This unified approach is efficient in managing and processing different kinds of sensory data. Not only the mathematical overhead is eliminated, but also we get a more transparent picture of various techniques in multisensor fusion.

We consider the problem of aggregating the information provided by sensors such as range finders and its applications to scene modelling. This information consists of collections of three-dimensional points which form a discrete subspace of the objects-to-free-space boundaries within the world to be modelled. The ultimate goal is to obtain a valid surface model which can in turn be transformed into an efficient volumetric representation for solid interference detection algorithms. We first relate our work to that of other researchers, and we then show that surface connectivity is a non-trivial but essential element of a valid representation. To that end, we introduce a formal definition for model validity which we use to guide the process of aggregating the different views and we provide a proof of its correctness under stated assumptions. We eventually suggest heuristic methods for extending our approach when the strict validity conditions do not suffice to construct a perceptually consistent model. Finally, we quickly introduce the topological problems posed by objects non-homeomorphic to spheres, such as multi-holed tori. The methods we develop do not depend on the physical nature of the sensing technique. For example, our results can also be used from data obtained by stereo analysis and to some extent by haptic sensing.

The set theoretic structure of mathematical morphology supports real-time fusion of image information from multiple sources. We demonstrate this morphological approach by detecting terrain features such as road and region boundaries in dual-mode radar imagery. Our scheme uses morphological processing to extract and combine features of interest from two millimeter wave data sources.

Solid modeling plays an important role in CAD, automated assembly and recently has found applications in robotics. Constructive Solid Geometry (CSG) is one of the most popular methods used for representing solids. It preserves the 3-D structure of the object; also it provides a hierarchical representation which is useful in representing complex objects. Yet the representation is only syntactic. Many applications using solid modelers need additional information such as physical, behavioral and functional properties of the objects. This paper incorporates these properties on CSG representation of solids and provides semantic constraints for manipulating these properties. Selection of the set of properties and the appropriate constraints depends on specific application. Three applications - finite element analysis, model-based robot vision and automated assembly are chosen in this paper for illustration. The goal is to embed this approach in a geometric reasoning system.

An intelligent robotic system for multi-sensor based tracking and interception of moving objects which travel at unknown velocities is presented. The capability for multi-sensor assisted object tracking has been achieved through the development of techniques to track in multiple dimensions for both the static and dynamic cases. These methods are realized via the fusion of the best attributes of visual and acoustic sensing into an effective configuration that is ideal for real time tracking purposes. The kinematic information for a moving object is extracted via end effector mounted vision and ultrasonic sensors. A hybrid position/force servo-controlled gripper developed at NCSU has been used for the system implementation. One parallel actuation gripper finger houses a fiber optics based Eye-in-Hand vision sensor, while the other accommodates an ultrasonic range sensor. The primary intent of this work is to develop approaches for performing the tasks of: generalized visual/ultrasonic tracking of known rectangular entities; 3-D tracking of arbitrary pseudo-planar objects that can change orientation about the optical axis; and a real time paradigm for the tracking of motion in 3-D with variable orientation about the optical axis. This discussion includes both a description of the underlying principles and the initial experimental results.

We present recent advancements in our passive trinocular stereo system. These include a technique for calibrating and rectifying in a very efficient and simple manner the triplets of images taken for trinocular stereovision systems. After the rectification of images, epipolar lines are parallel to the axes of the image coordinate frames. Therefore, potential matches between the three images satisfy simpler relations, allowing for a less complicated and more efficient matching algorithm. We also describe a more robust and general control strategy now employed in our trinocular stereo system. We have also developed an innovative method for the recon-struction of 3-D segments which provides better results and a new validation technique based on the observation that neighbors in the image should be neighbors in space. Experiments are presented demonstrating these advancements.

Accuracy of geometric measurement of object environments for robotic vision tasks is of increasing importance as these tasks become more sophisticated. The precision of the measurement of the position and orientation of objects in space is highly dependent upon the accurate calibration of a number of physical parameters for imaging cameras. Some recent articles have shown that for two camera stereo triangulation methods to work in practical situations that severe mechanical positioning constraints must be placed on the pair of cameras. The current practice for most stereo based methods is to build up descriptions of how objects occupy space from point data whose absolute positions in space have been measured. In particular, errors in orientation measurement of surfaces can be badly compounded by errors in absolute mesurement of multiple points that lie on the surface. This paper analyzes a stereo method which determines lines in space from the intersection of projected planar sheets. Object descriptions are built up from information about linear features instead of by points. It is shown that there are major advantages to accurately determining the orientation of object lines and surfaces using this stereo method. In the absence of errors apart from baseline translation error the measurement of the orientation of lines and surfaces from this stereo method is translation invariant in the sense that the orientation measurement is completely independent of knowledge of the baseline. Computer simulations of realistic imaging configurations show that even in the presence of errors from other camera parameters that this stereo method is nearly translation invariant and can far outperform stereo methods for the measurement of orientation based upon the absolute correspondence of points. Another advantage of determining the orientation of lines and surfaces from stereo using intersecting planes is that orientation errors do not grow rapidly as the object distance from the baseline increases. This is true for orientation measurement from stereo using the absolute correspondence of points.

This paper is a description of a framework for reasoning about textured scenes where low level structural information is used as evidence for texture primitives instead of a particular texture. Although low level texture edge features are not robust enough to determine exactly the texture in the scene, they can be used to reason about the scene since they provide evidence about the type of texture present. The structural evidence is combined to determine a measure of belief in the type of texture in the scene. Our overall goal is to use texture as a cue to separate surfaces in a scene. Segmenting textures into homogeneous regions must be based on properties of the texture that are not affected by an oblique projection. Our earlier results using project invariants showed that invariants of low level features cannot reliably discriminate textures. This lead us to an approach to first identify the type of texture element, and then the tesselation of the texture elements. Projective invariants based on the tesselation can then be used to segment the scene. In this paper, the reasoning framework and low level features will be described, along with the results of some experiments using Brodatz textures.

In this paper, a new analytic method for the fusion of range, r = r(x,y), and intensity, i = i(x,y), edge maps is presented. This method focuses on the integration of registered information in order to increase one's confidence about the presence/absence of edges in a depicted scene. The algorithm is based on the in-teraction between the following two constraints: the principle of existence, which tends to maximize the value of the output edge map at a given location if one input edge map features an edge, and the principle of confirmability, which adjusts this value according to the edge content in the other input edge map at the same location, by maximizing the similarity between them. These two principles are combined by maximizing a linear positive combinations of those two constraints related by a fusion function, a = a(x, y). The latter maximization is achieved us-ing the Euler-Language Calculus of Variations equations. This method was tested with synthetic and real data. The resulting edge maps combining both range and intensity data satisfies both principles of existence and confirmability. It has been applied also to other type of registered real data (multispectral) with the same integration success.

Integration of outputs from multiple sensors has been the subject of much of the recent research in the machine vision field. This process is useful in a variety of applications, such as three dimensional interpretation of scenes imaged by multiple cameras, integration of visible and range data, and the fusion of multiple types of sensors. The use of multiple types of sensors for machine vision poses the problem of how to integrate the information from these sensors. This paper presents a neural network model for the fusion of visible and thermal infrared sensor outputs. Since there is no human biological system that can be used as a model for integration of these sensor outputs, alternate biological systems for sensory fusions can serve as starting points. In this paper, a model is developed based upon six types of bimodal neurons found in the optic tectum of the rattlesnake. These neurons integrate visible and thermal infrared sensory inputs. The neural network model has a series of layers which include a layer for unsupervised clustering in the form of self-organizing feature maps, followed by a layer which has multiple filters that are generated by training a neural net with experimental rattlesnake response data. The final layer performs another unsupervised clustering for integration of the output from the filter layer. The results of a number of experiments are also presented.

Multisensor fusion for object recognition, particularly when multiple sensor platforms and phenomenologies are considered, stresses the state of the art in model-based Image Understanding. The discrimination power of the algorithms depends on accumulation of evidence from diverse sources and on properly applying known model constraints to sensor data. In this paper we describe a model-based multiple-hypothesis Bayesian approach to recognition that has roots in detection and estimation theory. We also describe an approach to object modeling that utilizes an object-based representation that allows multiple geometric representations and multiple, alternative decompositions of the object model. Initial implementations of these ideas have been incorporated into a model-based vision testbed and are currently undergoing testing and evaluation.

We are interested in designing autonomous mobile robots for industrial applications. Building useful robots for real-world tasks will require developing efficient methods for representing and reasoning about space. Pervasive among spatial representation schemes suggested to date is the assumption that the robot has some built-in mechanism that allows it to uniquely identify different locations in the world. This paper extends one such rep-resentation, developed by Smith and Cheeseman [8], to account for uncertainty in the identification of locations. We will begin with a brief account of Smith and Cheeseman's model.

Parallel relaxation computations such as those of connectionist networks offer a useful model for constraint integration and intrinsic image combination in developing a general-purpose stereo matching algorithm. This paper describes such a stereo algorithm that incorporates hierarchical, surface structure and edge appearance constraints that are redefined and are integrated at the level of individual candidate matches. The algorithm produced a high percentage of correct decisions on a wide-variety of stereo pairs. Its few errors arose when the correlation measures defined by the constraints were either weakened, or ambiguous, as in the case of periodic patterns in the images. Two additional mechanisms are discussed for overcoming the remaining errors. First, an independent estimate of disparity, obtained through a depth-from-focus algorithm, can resolve the ambiguity in periodic regions. Second, a third image, taken from a position above the left image, is incorporated into matching. This is accomplished by defining matches between the new image and the left image, and relating the new and old matches through new constraints. Both of the new approaches are easily easily incorporated into the connectionist network computations of the original algorithm.

Current techniques for dealing with uncertainty in expert systems do not adequately handle dependency information. In fact, most schemes make routine independence assumptions. These assumptions lead to serious questions as to the validity of the conclusions reached by systems which employ such schemes. This paper introduces a technique for reasoning with dependency information in expert systems that acquire probabilistic evidence. This technique relies on a modified version of Dempster-Shafer Theory. In particular, a new support function and updating scheme are used. Examples of several different types of situations are given to show that this modified technique deals with dependency in both an intuitive and reasonable way.

There are a number of methods for the combination of multiple sensor outputs for the interpretation of a scene. Among these are Bayesian, Dempster-Shafer, fuzzy and modified Dempster-Shafer methods. This paper presents a comparison of various techniques for the combination of the information from multiple sensors under uncertain conditions. Oftentimes, sensor independence is an underlying assumption for the sensor fusion process. The experimen-tal studies presented in this paper indicate that interpretation of sensor fusion results as far as the use of thresholds is further complicated due to this assumption. The different systems that are compared have results that numerically differ by as much as 20%, which indicates the need for further studies along these lines.

The machine vision community needs a simple, easy to use, fast, accurate, and low cost way of calibrating the robot eye, eye-to-hand and hand for 3D machine vision applications. This paper overviews a trio exactly for this purpose. The trio is real time, and uses common motion, cal-ibration plate, setup, coordinate systems, matrices, vectors, symbols and operations throughout. It is easier and faster than any of the existing techniques, and is among the most accurate calibration techniques using vision (while several orders of magnitude faster than those techniques that have comparable accuracy). The robot makes a series of automatically planned movements with a camera rigidly mounted at the gripper. At the end of each move, it takes a total of 90 milliseconds to grab an image, extract image feature coordinates and perform camera extrinsic calibration. After the robot finishes all the movements, it takes only a few milliseconds to do the eye-to-hand and hand calibration, and takes less than 25 milliseconds to do the eye calibration (can be reduced several fold if only a minimal number of calibration points are used). In this paper, we first introduce what a trio is. Then a list of main advantages of the proposed trio is given. Next, each element of the trio is defined. The common setup used throughout the trio is then described. Next, we briefly overview how the trio works globally. Then, each element of the trio is presented in more detail. The trio has been fully implemented and is operational; with the eye a Javelin CID camera, and the hand an IBM Clean Room Robot. This paper only overviews the approaches. The complete details of the theory, algorithm, and implementation results can be found in the references.

Using single sensor for reasoning is not adequate for operations in a complicate and dynamic environment and is not suitable for detecting features inferred from multiple modality sensor information. In order to reduce uncertainty about the target and achieve fault tolerant ability, using multiple sensors to provide more information is desired. Since each sensor offers unique scene attribute and contextual information, data gathered from different sensor sources may have different spatial resolutions and various relative orientations between the target and the sensor. In addition, the dimension of the sensor data may vary from one dimension to N dimensions. In order to correlate data from multiple sensor sources, registration between the sensor data and the world coordinate system is required for both voxel-based sensor fusion and feature-based information fusion. It is obviously that the success of the voxel based sensor fusion is heavily relied on the registration accuracy. On the other hand, geometric information is required to be associated with the extracted features either from a single sensor source or from multiple sensor sources for accurate global description in feature-based information fusion.

An algorithm to determine the three-space position and orientation of a robot camera relative to a rectangular shaped mark of known size has been developed. In contrast to similar research, this algorithm does not require that a priori constraints be placed on the original position or orientation of the camera relative to the mark. Given the image plane positions of at least three vertices of the mark, the two projected diagonals of the mark are isolated and processed in turn to find the 2d position of the camera in the plane that contains the diagonal and the line connecting the centroid of the mark and the focal point of the camera. The 2d results are then combined using heuristics to determine the unique three-space position and orientation of the camera relative to the rectangle. If fewer than three vertices are visible, camera repositioning parameters are computed such that relational determination can be achieved from a subsequent image. Results of camera position determination and an analysis of associated errors are provided.

The purpose of this report is to show results of automatic target classification and sensor fusion for forward looking infrared (FLIR) and Laser Radar sensors. The sensor fusion data base was acquired from the Naval Weapon Center and it consists of coregistered Laser RaDAR (range and reflectance image), FLIR (raw and preprocessed image) and TV. Using this data base we have developed techniques to extract relevant object edges from the FLIR and LADAR which are correlated to wireframe models. The resulting correlation coefficients from both the LADAR and FLIR are fused using either the Bayesian or the Dempster-Shafer combination method so as to provide a higher confidence target classifica-tion level output. Finally, to minimize the correlation process the wireframe models are modified to reflect target range (size of target) and target orientation which is extracted from the LADAR reflectance image.

Prediction of target signatures using complex computer models of targets and sensor characteristics permits the development of robust target discrimination algorithms in the absence of large data collections. This paper describes the methodology of employing model-derived data in multisensor target discrimination activities. The signature predictions not only provide reference data for algorithms but also aid in the design optimization of multisensor collection configurations. Due to their ability to process more information, multisensor target recognition algorithms are expected to outperform single sensor designs. Development of multisensor algorithms is hampered by extensive requirements for registered training and reference data. By relying heavily on predicted signatures for sensor parameter selection and algorithm development, the required quantity of sensed data collection is greatly reduced. The usefulness of the collected data is focused and enhanced by examination of modeling and validation requirements. Final expansion of algo-rithm designs from straightforward pattern recognition approaches to more highly-evolved model-based recognition concepts is more easily bridged when model-derived data plays a significant role at each developmental stage.

We consider the problem of distributed detection based on a system of two sensors that transmit raw data to a central processor (fusion center) responsible for making the final decision when the region jointly covered by the two sensors contains sub-regions that are blind spots to each of the sensors. Preliminary assumptions include a known geometry of the visible and blind spots, symmetric coverage of the region by the two sensors and uniform distribution of a target in the coverage region. We formulate and compare three detection schemes. In the first scheme, the a-priori information on the coverage factor along with the data from both sensors are used directly to detect the presence of the target with no attempt to estimate its position first. In the second scheme, a preliminary estimate of the target position is used to deternime whether the target is visible by both sensors, one only, or none. Once a decision is taken on which sensor data to use, a likelihood ratio test is implemented for target detection. This scheme therefore estimates the probable target location and then proceeds to detect it. In the third scheme, estimates of the most likely position of the target, if the target were present, are incorporated in the detection model, and the presence of the target is detected by using a likelihood ratio test. Numerical results for the three schemes are presented for the Gaussian channel.

Presented in this paper are the system and measurement models, and the recursive filter equations, for an extended Kalman filter (EKF) to be used in tracking video point targets. The filter is designed to maintain estimates of a target's position, velocity, and acceleration in three dimensions (3D) based on two-dimensional (2D) measurements of the target's bearings as observed by several cameras. The geometric mapping from object points in 3D world coordinates to image points in 2D image coordinates is modeled by the central projection for pinhole cameras. The recursive equations of the EKF incorporate the Jacobian of this nonlinear camera transformation.

In many autonomous target recognition (ATR) investigations it is necessary (or at least desirable) to develop target detection algorithms which function on partially occluded targets as well as open targets. This task may prove difficult if the developers must provide an algorithm based on parameters which are invariant under open and partially occluded conditions. A simpler approach is to detect the possibility of partial occlusion and apply separate detection thresholds or algorithms in such areas. In a typical battlefield outside densely populated areas, only trees have the ability to obscure vehicles from view. The problem of discriminating tree clutter from other types of clutter in the scene environment as viewed from various sensors is addressed in an effort to signal the conditions under which a partially occluded target detection algorithm should be applied. The discussion that follows defines the desirable characteristics of the tree finder, outlines the problem assumptions and examines various strategies for tree clutter discrimination that will be considered.

Using a dextrous hand involves understanding the relation-ships between the three kinds of sensor outputs available: joint space positions, tendon forces, and tactile contacts. Dextrous manipulation then is a fusion of these three sensing modalities. This paper is an exploration of using a dextrous, multi-fingered hand (Utah/MIT hand) for high-level object recognition tasks. The paradigm is model-based recognition in which the objects are modeled and recovered as superquadrics, which are shown to have a number of important attributes that make them well suited for such a task. Experiments have been performed to recover the shape of objects using sparse contact point data from the hand kinematics and forces with promising results. We also present our approach to using tactile data in conjunction with the dextrous hand to build a library of grasping and exploration primitives that can be used in recognizing and grasping more complex multi-part objects.

In the paper an intelligent optically powered robot gripper equipped with optical fiber sensors is proposed. The gripper's sensor system includes single sensor modules C an optical fiber slip sensor and an optical fiber colour sensor ) and systems of sensors (a 3-D optical fiber proximity sensing system, an optical fiber tactile matrix for tactile imaging and a vision system with an optical fiber illuminator, a coherent optical fiber bundle for transmitting an image from the gripper, and a CCD image sensor placed out of the gripper). In the described robot gripper many different sensors have been placed because of the complexity of the analized problems of sensing. In many situations the application of all sensors is unnecessary. The paper gives the procedure of defining the design of a sensor system for an intelligent robot gripper. The procedure determines the number of particular types of sensors for the system and the manner of integrating the sensors with the gripper.

The advantage in using several similar sensors has been demonstrated in the context of remote sensing and dynamic scene analysis. There have been few studies dealing with the use of several dissimilar sensors although the advantage is clear : different sensors are sensitive to different properties of the environment, each one of which can contribute significantly in interpreting this environment. One of the main problems, however, is to integrate in a meaningful fashion, the (possibly dissimilar) data collected by the various sensors. This paper examines the problem and suggests the use of decision networks.

We consider imaging spectrometer data as a large class problem (for which we offer a decision net solution involving a new hierachical classifier and set of multiple directed graphs) and as a mixture problem (for which a neural net solution is advanced).

In this paper we describe an approach to high-level multisensor integration in the context of an autonomous mobile robot. Previous papers have described the development of the INRIA mobile robot subsystems: 1. sensor and actuator systems 2. distance and range analysis 3. feature extraction and segmentation 4. motion detection 5. uncertainty management, and 6. 3-D environment descriptions. We describe here an approach to: the semantic analysis of the 3-D environment descriptions. This analysis is organized in terms of robot goals and behaviors. This is accomplished by the use of logical behaviors. Such an approach allows for active control of the sensors in acquiring information.

A Common Lisp software system to support integrated image and symbolic processing applications is described. The system, termed Omega is implemented on a Symbolics Lisp Machine and is organized into modules to facilitate the development of user applications and for software transportability. An object-oriented programming language similar to Symbolics Zetalisp/Flavors is implemented in Common Lisp and is used for creating symbolic objects known as tokens. Tokens are used to represent images, significant areas in images, and regions that define the spatial extent of the significant areas. The extent of point, line, and areal features is represented by polygons, label maps, boundary points, row- and column-oriented run-length encoded rasters, and bounding rectangles. Macros provide a common means for image processing functions and spatial operators to access spatial representations. The implementation of image processing, segmentation, and symbolic processing functions within Omega are described.

The development of sensor systems generally includes significant algorithm and software design and implementation. In this paper we describe the development of requirements for and contruction of an algorithm and software development environment which handles all of the critical development elements from algorithm prototyping through real time implementation.

A mobile robot that maintains a dynamic cognitive map will often find that the information in the map is contradicted by his perceptions, and is therefore incorrect. Such errors may be the result of an earlier misperception, an erroneous matching, an erroneous default inference, computational errors, a change in the world over time, or an erroneous previous error correction. Due to the complexity of inference in forming cognitive maps, domain-independent strategies for error correction, such as data-dependencies or conditional probabilities, are not sufficient by themselves to give a robust error correction scheme. Rather, domain-specific techniques and heuristics must be applied. We dis-cuss some of the basic issues involved in detecting, diagnosing and correcting errors in the cognitive map. We also discuss how a robot may decide whether to take actions in order to gather relevant information.

In processing ultrasonic and visual sensor data acquired by mobile robots systematic errors can occur. The sonar errors include distortions in size and surface orientation due to the beam resolution, and false echoes. The vision errors include, among others, ambiguities in discriminating depth discontinuities from intensity gradients generated by variations in surface brightness. In this paper we present a methodology for the removal of systematic errors using data fror the sonar sensor domain to guide the processing of information in the vision domain, and vice versa. During the sonar data processing some errors are removed from 2D navigation maps through pattern analyses and consistent-labelling conditions, using spatial reasoning about the sonar beam and object characteristics. Others are removed using visual information. In the vision data processing vertical edge segments are extracted using a Canny-like algorithm, and are labelled. Object edge features are then constructed from the segments using statistical and spatial analyses. A least-squares method is used during the statistical analysis, and sonar range data are used in the spatial analysis.

Many of the current approaches toward the creation of an intelligent robotic system involve the creation and maintenance of an explicit world model. One such world model decomposes space into a hierarchical grid, representing spatial features of interest in high detail and those of lesser interest in lower detail. These models provide an effective interface for sensory information as well as an efficient mechanism for performing spatial inferences. Although hierarchical decompositions provide efficient representations of space, paths generated by planning systems operating within such representations tend to suffer from stair-stepping effects. Stair-stepping effects are a result of the loss of spatial continuity resulting from the decomposition of space into a grid. This paper presents a path planning algorithm which eliminates stair-stepping effects induced by the grid-based spatial representation. The algorithm exploits a hierarchical spatial model to efficiently plan paths for a mobile robot operating in dynamic domains. The spatial model and path planning algorithm map to a parallel machine, allowing the system to effectively operate incrementally, thereby accounting for unexpected events in the operating space.

In this paper, we explore some basic issues concerning the impact of uncertainty on the complexity of map learning: assimilating sensor data to support spatial queries. The primary computational task involves consolidating a set of measurements to support queries concerning the relative position of identifiable locations. We are concerned with the complexity of providing the best possible answers to such queries. We provide a partial categorization of map learning problems according to the sorts of sensors available and the probability distributions that govern their accuracy. The objective of this exercise is to precisely define a set of computational problems and investigate the properties of algorithms that provide solutions to these problems. We show that hard problems involving uncertain measurements arise even in a single-dimensional setting. We also show that there are interesting two-dimensional map learning problems that can be solved in polynomial time. By considering basic time/space tradeoffs, we provide some insight into exactly what makes map learning hard, and how various sensors might be employed to circumvent combinatorial problems.

In traditional approaches to spatial learning, mobile robots in unstructured unknown environments try to build metrically accurate maps in an absolute coordinate system, and therefore have to cope with device errors. We use a qualitative method which can be robust in the face of various possible errors in the real world. Our method uses a multi-layered map which consists of procedural knowledge for movement, topological model for the structure of the environment, and metrical information for geometrical accuracy. The topological model consists of distinctive places and local travel edges linking nearby distinctive places. A distinctive place is defined as the local maximum of some measure of distinctiveness appropriate to its immediate neighborhood, and is found by a hill-climbing search. Local travel edges are defined in terms of local control strategies required for travel. The identification of distinctive places and travel edges and the use of local control strategies make it possible to largely eliminate cumulative error, resulting in an accurate topological map even in the face of sensory or motor errors. How to find distinctive places and follow edges is the procedural knowledge in the map, and the distinctive places and the travel edges have metrical descriptions for local geometry on the top of the topological map. The metrical descriptions are integrated gradually for global geometry by using local coordinate frames and a best-fit method to connect them. With a working simulation in which a robot, NX, with range sensors explores a variety of 2-D environments, we show its successful results in the face of random and simple systematic device errors.

Many scenes contain significant textual information that can be extremely helpful for understanding and/or navigation. For example, text-based information can frequently be the primary cure used for navigating inside buildings. One might first read a marquee, then look for an appropriate hallway and walk along reading door signs and nameplates until the destination is found. Optical character recognition has been studied extensively in recent years, but has been applied almost exclusively to printed documents. As these techniques improve it becomes reasonable to ask whether they can be applied to an arbitrary scene in an attempt to extract text-based information. Before an automated system can be expected to navigate by reading signs, however, the text must first be segmented from the rest of the scene. This paper discusses the feasibility of extracting text from an arbitrary scene and using that information to guide the navigation of a mobile robot. We consider some simple techniques for first locating text components and then tracking the individual characters to form words and phrases. Results for some sample images are also presented.

Operator performance with telerobotic systems may be improved by use of video displays that simulate direct vision through a window. This "virtual window" concept provides intuitive head-coupled aiming of the camera system field-of-view as the observer shifts left /right or up /down. It also provides correct motion parallax cues, thus eliminating the strange distortions seen in conventional stereoscopic video when the observer moves laterally in front of the display screen. Unlike other head-coupled approaches, this permits the use of fixed rack-mounted video displays (typically more comfortable for prolonged work sessions) that are relatively low-cost and readily available with color, high-resolution, and good image contrast (difficult to achieve in a helmet-mounted display). While this "virtual window" concept is relatively easy to implement for computer-generated imagery, real-world imaging requires special camera system geometry to make the display concept work. This paper reviews "virtual window" camera/display geometry and reports on initial performance testing with a simple prototype.

The Knowledge Based Vision Project1,2 is concerned with developing terrain recognition and modeling capabilities for an au land vehicle. For functioning in realistic outdoor environments, we are assuming a vehicle with a laser range finder, controllable cameras, and limited inertial sensing. The range finder is used for mapping and navigating through the immediate environment. The cameras are used for object recognition and recognizing distant landmarks beyond the access of the range sensor. We are assuming the vehicle has realistically limited perceptual and object recognition capabilities. In particular, it will see things that it won't be familiar with and can't recognize, but which can be described as stable visual perceptions. The vehicle will not always be able to recognize the same object as being identical from very different points of view. It will have limited, inexact, and undetailed a prior terrain information generally in the form of labeled grid data. One of the basic functions of the vehicle is to elaborate this terrain map of the environment. Another is to successfully navigate through the environment using landmarks.

A major requirement for an autonomous robot is the capability to diagnose faults during plan execution in an uncertain environment. Many diagnostic researches concentrate only on hardware failures within an autonomous robot. Taking a different approach, this paper describes the implementation of a Telerobot Diagnostic System that addresses, in addition to hardware failures, failures caused by unexpected event changes in the environment or failures due to plan errors. One unique feature of the system is the utilization of task-plan knowledge and context information to deduce fault symptoms. This forward deduction provides valuable information on past activities and the current expectations of a robotic event, both of which can guide the plan-execution inference process. The inference process adopts a model-based technique to recreate the plan-execution process and to confirm fault-source hypotheses. This tech-nique allows the system to diagnose multiple faults due to either unexpected plan failures or hardware errors. This research initiates a major effort to investigate relationships between hardware faults and plan errors, relationships that have not been addressed in the past. The results of this research will provide a clear understanding of how to generate a better task planner for an autonomous robot and how to recover the robot from faults in a critical environment.

Multisensor data fusion is applied to the problem of detecting and identifying obstacles in a static (or slowly-changing) known scene. Automatic detection of unexpected objects is of crucial importance in reducing the need for personnel in surveillance stations: possible applications to the area of rail transportation systems are currently being explored, and results for a level crossing monitoring situation are presented. This paper defines a framework that allows the exploitation of multiple sensors or multiple operation modes of a single sensor: as an example, it describes a way of merging the data coming from two channels (the RG bands of a color video camera), each providing two intensity images (the actual scene and the "normal" background). Moreover, the system can profit by the introduction of additional sensors, like a Laser Range Finder to aid in locating obstacles in 3D space. The proposed system architecture is based on a blackboard organization for both inference and control: particular care has been exercised in optimizing the data flow through system modules by means of a heterarchical control structure. Object-oriented programming is extensively used to isolate the system's basic units in order to allow a future parallel implementation.

Over the past ten years a significant number of noncommunication uses for optical fibers have arisen. These applications involve the use of optical fibers in sensors. Special fiber optic sensors have also been developed for robotics. The aim of the paper is to present main directions of research on the development of optical fiber sensors for robotics and to show some of their applications. So far various types of optical fiber sensors of proximity, tactile, pressure, slip and colour have been developed. Some of the most interesting solutions are briefly described. Examples of other applications of fiber optics in the sensor system of robots are also given e.g. the use of a noncoherent optical fiber bundle for illumination of a scene, the use of coherent optical fiber bundles in vision systems for transmitting images from a robot gripper to a CCD image sensor placed out of the gripper. The presented review has been done on the basis of proceedings of many international conferences and symposia on robotics, optoelectronics and fiber optics and international journals.

As part of the Multiple Autonomous Underwater Vehicle (MAUV) project at the National Bureau of Standards, a spatial mapping system has been developed to provide a model of the underwater environment suitable for autonomous navigation. The system is composed of multi-resolution depth maps designed to integrate sensor data with an a priori model, an object/attribute database for storing information about detected objects, and a set of flags to monitor abnormal or emergency conditions in the environment. This paper describes the struc-ture of the mapping system and the algorithms used to map terrain and obstacles detected by acoustic sonar.

Autonomous navigation of airborne platforms requires the integration of diverse sources of sensor data and contextual information. In this paper we describe a system that utilizes polarimetric radar cross-section and range data to generate position estimates based on four kinds of information: area segmentation, ground contours, landmarks and road networks. Ground truth in the form of terrain feature maps is correlated with each type of data stream. Finally, an arbitrator integrates these inputs with contextual knowledge about the preplanned flight path to resolve conflicts and arrive at a final estimate of current position.

The Region Based Route Planner performs intermediate-level and high-level processing on vision data to organize the image into more meaningful higher-level topological representations. A variety of representations are employed at appropriate stages in the route plan-ning process. A variety of abstractions are used for the purposes of problem reduction and application of multiple criteria at different phases during the navigation planning process. The Region Based Route Planner operates in terrain scenarios where some or most of the terrain is occluded. The Region Based Route Planner operates without any priori maps. The route planner uses two dimensional representations and utilizes gradient and roughness information. The implementation described here is being tested on the JPL Robotic Vehicle. The Region Based Route Planner operates in two phases. In the first phase, the terrain map is segmented to derive global information about various features in it. The next phase is the actual route planning phase. The route is planned with increasing amounts of detail by successive refinement. This phase has three abstrac-tions. In the first abstraction, the planner analyses high level information and so a coarse, region-to-region plan is produced. The second abstraction produces a list of pairs of entry and exit waypoints for only these selected regions. In the last abstraction, for every pair of these waypoints, a local route planner is invoked. This planner finds a detailed point-to-point path by searching only within the boundaries of these relatively small regions.

In this paper a method intended for reducing the complexity of 3D path planning tasks, where such planning is restricted to terrain-going vehicles is described. Two classes of problems are addressed. Both classes share the property that different regions of terrain impose different costs during path traversal. The first problem class concerns traversal costs within a single region which are independent of the direction of motion. In the second problem class, however, costs within a single region vary depending upon the direction in which the vehicle is travelling. Hence, 3D terrain maps can be transformed into what here are called "cost precursor maps", which provides an abstraction of the 3D terrain information into a 2D reference frame.

In order to plan paths within a physical working space, effective data structures must be used for spatial representation. A free space graph is a data structure derived from a systematic decomposition of the unobstructed portions of the working space. For the two-dimensional case, this work describes an heuristic method for traversal and search of one particular type of free space graph. The focus herein regards the "dialogue" between an A* search process and an inference engine whose rules employ spatial operators for classification of local topologies within the free space graph. This knowledge-based technique is used to generate plans which describe admissible sequences of movement between selected start and goal configurations.