Mobile robot navigation and scene modeling using stereo fish-eye lens system

We present an autonomous mobile robot navigation system using stereo fish-eye lenses for navigation in an indoor structured environment and for generating a model of the imaged scene. The system estimates the three-dimensional (3D) position of significant features in the scene, and by estimating its relative position to the features, navigates through narrow passages and makes turns at corridor ends. Fish-eye lenses are used to provide a large field of view, which images objects close to the robot and helps in making smooth transitions in the direction of motion. Calibration is performed for the lens-camera setup and the distortion is corrected to obtain accurate quantitative measurements. A vision-based algorithm that uses the vanishing points of extracted segments from a scene in a few 3D orientations provides an accurate estimate of the robot orientation. This is used, in addition to 3D recovery via stereo correspondence, to maintain the robot motion in a purely translational path, as well as to remove the effects of any drifts from this path from each acquired image. Horizontal segments are used as a qualitative estimate of change in the motion direction and correspondence of vertical segment provides precise 3D information about objects close to the robot. Assuming detected linear edges in the scene as boundaries of planar surfaces, the 3D model of the scene is generated. The robot system is implemented and tested in a structured environment at our research center. Results from the robot navigation in real environments are presented and discussed. Received: 25 September 1996 / Accepted: 20 October 1996     

A complete system for the intelligent interpretation of engineering drawings

Converting paper-based engineering drawings into CAD model files is a tedious process. Therefore, automating the conversion of such drawings represents tremendous time and labor savings. We present a complete system which interprets such 2D paper-based engineering drawings, and outputs 3D models that can be displayed as wireframes. The system performs the detection of dimension sets, the extraction of object lines, and the assembly of 3D objects from the extracted object lines. A knowledge-based method is used to remove dimension sets and text from ANSI engineering drawings, a graphics recognition procedure is used to extract complete object lines, and an evidential rule-based method is utilized to identify view relationships. While these methods are the subject of several of our previous papers, this paper focuses on the 3D interpretation of the object. This is accomplished using a technique based on evidential reasoning and a wide range of rules and heuristics. The system is limited to the interpretation of objects composed of planar, spherical, and cylindrical surfaces. Experimental results are presented. Received December 2, 1998 / Revised June 18, 1999     

Utilization of stereo disparity and optical flow information for the computer analysis of human interactions

We propose a system that simultaneously utilizes the stereo disparity and optical flow information of real-time stereo grayscale multiresolution images for the recognition of objects and gestures in human interactions. For real-time calculation of the disparity and optical flow information of a stereo image, the system first creates pyramid images using a Gaussian filter. The system then determines the disparity and optical flow of a low-density image and extracts attention regions in a high-density image. The three foremost regions are recognized using higher-order local autocorrelation features and linear discriminant analysis. As the recognition method is view based, the system can process the face and hand recognitions simultaneously in real time. The recognition features are independent of parallel translations, so the system can use unstable extractions from stereo depth information. We demonstrate that the system can discriminate the users, monitor the basic movements of the user, smoothly learn an object presented by users, and can communicate with users by hand signs learned in advance. Received: 31 January 2000 / Accepted: 1 May 2001 Correspondence to: I. Yoda (e-mail: yoda@ieee.org, Tel.: +81-298-615941, Fax: +81-298-613313)     

Head tracking using stereo

Head tracking is an important primitive for smart environments and perceptual user interfaces where the poses and movements of body parts need to be determined. Most previous solutions to this problem are based on intensity images and, as a result, suffer from a host of problems including sensitivity to background clutter and lighting variations. Our approach avoids these pitfalls by using stereo depth data together with a simple human-torso model to create a head-tracking system that is both fast and robust. We use stereo data (Commercial equipment and materials are identified in order to adequately specify certain procedures. In no case does such identification imply recommendation or endorsement by the National Institute of Standards and Technology, nor does it imply that the materials or equipment identified are necessarily the best available for the purpose.) to derive a depth model of the background that is then employed to provide accurate foreground segmentation. We then use directed local edge detectors on the foreground to find occluding edges that are used as features to fit to a torso model. Once we have the model parameters, the location and orientation of the head can be easily estimated. A useful side effect from using stereo data is the ability to track head movement through a room in three dimensions. Experimental results on real image sequences are given. Accepted: 13 August 2001     

Silhouette-based occluded object recognition through curvature scale space

A complete and practical system for occluded object recognition has been developed which is very robust with respect to noise and local deformations of shape (due to weak perspective distortion, segmentation errors and non-rigid material) as well as scale, position and orientation changes of the objects. The system has been tested on a wide variety of free-form 3D objects. An industrial application is envisaged where a fixed camera and a light-box are utilized to obtain images. Within the constraints of the system, every rigid 3D object can be modeled by a limited number of classes of 2D contours corresponding to the object's resting positions on the light-box. The contours in each class are related to each other by a 2D similarity transformation. The Curvature Scale Space technique [26, 28] is then used to obtain a novel multi-scale segmentation of the image and the model contours. Object indexing [16, 32, 36] is used to narrow down the search space. An efficient local matching algorithm is utilized to select the best matching models. Received: 5 August 1996 / Accepted: 19 March 1997     

Machine vision system for curved surface inspection

This application-oriented paper discusses a non-contact 3D range data measurement system to improve the performance of the existing 2D herring roe grading system. The existing system uses a single CCD camera with unstructured halogen lighting to acquire and analyze the shape of the 2D shape of the herring roe for size and deformity grading. Our system will act as an additional system module, which can be integrated into the existing 2D grading system, providing the additional third dimension to detect deformities in the herring roe, which were not detected in the 2D analysis. Furthermore, the additional surface depth data will increase the accuracy of the weight information used in the existing grading system. In the proposed system, multiple laser light stripes are projected into the herring roe and the single B/W CCD camera records the image of the scene. The distortion in the projected line pattern is due to the surface curvature and orientation. Utilizing the linear relation between the projected line distortion and surface depth, the range data was recovered from a single camera image. The measurement technique is described and the depth information is obtained through four steps: (1) image capture, (2) stripe extraction, (3) stripe coding, (4) triangulation, and system calibration. Then, this depth information can be converted into the curvature and orientation of the shape for deformity inspection, and also used for the weight estimation. Preliminary results are included to show the feasibility and performance of our measurement technique. The accuracy and reliability of the computerized herring roe grading system can be greatly improved by integrating this system into existing system in the future.     

A database model for object dynamics

To effectively model complex applications in which constantly changing situations can be represented, a database system must be able to support the runtime specification of structural and behavioral nuances for objects on an individual or group basis. This paper introduces the role mechanism as an extension of object-oriented databases to support unanticipated behavioral oscillations for objects that may attain many types and share a single object identity. A role refers to the ability to represent object dynamics by seamlessly integrating idiosyncratic behavior, possibly in response to external events, with pre-existing object behavior specified at instance creation time. In this manner, the same object can simultaneously be an instance of different classes which symbolize the different roles that this object assumes. The role concept and its underlying linguistic scheme simplify the design requirements of complex applications that need to create and manipulate dynamic objects. Edited by D. McLeod / Received March 1994 / Accepted January 1996     

Multipass hierarchical stereo matching for generation of digital terrain models from aerial images

This paper presents a new multi-pass hierarchical stereo-matching approach for generation of digital terrain models (DTMs) from two overlapping aerial images. Our method consists of multiple passes which compute stereo matches with a coarse-to-fine and sparse-to-dense paradigm. An image pyramid is generated and used in the hierarchical stereo matching. Within each pass, the DTM is refined by using the image pyramid from the coarse to the fine level. At the coarsest level of the first pass, a global stereo-matching technique, the intra-/inter-scanline matching method, is used to generate a good initial DTM for the subsequent stereo matching. Thereafter, hierarchical block matching is applied to image locations where features are detected to refine the DTM incrementally. In the first pass, only the feature points near salient edge segments are considered in block matching. In the second pass, all the feature points are considered, and the DTM obtained from the first pass is used as the initial condition for local searching. For the passes after the second pass, 3D interactive manual editing can be incorporated into the automatic DTM refinement process whenever necessary. Experimental results have shown that our method can successfully provide accurate DTM from aerial images. The success of our approach and system has also been demonstrated with a flight simulation software. Received: 4 November 1996 / Accepted: 20 October 1997     

A new phase extraction algorithm for phase profilometry

This paper describes a new phase extraction algorithm for 3D optical profilometry based on the projection of a periodic light pattern and phase measurement (phase profilometry). The algorithm uses a square wave to demodulate phase and moving averages and comb-shaped filters to extract the phase information from low frequency. The proposed algorithm is compared with the two major profilometry techniques, namely Fourier domain profilometry and signal domain profilometry based on FIR low-pass filtering. Comparison is focused on adaptiveness to changes of the pattern frequency, ability to deal with nonuniform surfaces and computational complexity. Adaptiveness analysis is carried out by means of simulations. The issue of nonuniform surfaces is discussed on the basis of experimental results obtained from application of phase profilometry to on-line 3D printed circuit board inspection. With regard to complexity, theoretical estimates are verified by means of actual computation time measurements. Received: 30 November 1996 / Accepted: 6 June 1997     

The reconstruction of dynamic 3D structure of biological objects using stereo microscope images

In this paper, we address the analysis of 3D shape and shape change in non-rigid biological objects imaged via a stereo light microscope. We propose an integrated approach for the reconstruction of 3D structure and the motion analysis for images in which only a few informative features are available. The key components of this framework are: 1) image registration using a correlation-based approach, 2) region-of-interest extraction using motion-based segmentation, and 3) stereo and motion analysis using a cooperative spatial and temporal matching process. We describe these three stages of processing and illustrate the efficacy of the proposed approach using real images of a live frog's ventricle. The reconstructed dynamic 3D structure of the ventricle is demonstrated in our experimental results, and it agrees qualitatively with the observed images of the ventricle.     

Building a color classification system for textured and hue homogeneous surfaces: system calibration and algorithm

We present a system for classifying the color aspect of textured surfaces having a nearly constant hue (such as wooden boards, textiles, wallpaper, etc.). The system is designed to compensate for small fluctuations (over time) of the light source and for inhomogeneous illumination conditions (shading correction). This is an important feature because even in industrial environments where the lighting conditions are controlled, a constant and homogeneous illumination cannot be guaranteed. Together with an appropriate camera calibration (which includes a periodic update), our approach offers a robust system which is able to “distinguish” (i.e., classify correctly) between surface classes which exhibit visually barely perceptible color variations. In particular, our approach is based on relative (not absolute) color measurements. In this paper, we outline the classification algorithm while focusing in detail on the camera calibration and a method for compensating for fluctuations of the light source. Received: 1 September 1998 / Accepted: 16 March 2000     

A bin picking system based on depth from defocus

It is generally accepted that to develop versatile bin-picking systems capable of grasping and manipulation operations, accurate 3-D information is required. To accomplish this goal, we have developed a fast and precise range sensor based on active depth from defocus (DFD). This sensor is used in conjunction with a three-component vision system, which is able to recognize and evaluate the attitude of 3-D objects. The first component performs scene segmentation using an edge-based approach. Since edges are used to detect the object boundaries, a key issue consists of improving the quality of edge detection. The second component attempts to recognize the object placed on the top of the object pile using a model-driven approach in which the segmented surfaces are compared with those stored in the model database. Finally, the attitude of the recognized object is evaluated using an eigenimage approach augmented with range data analysis. The full bin-picking system will be outlined, and a number of experimental results will be examined. Received: 2 December 2000 / Accepted: 9 September 2001 Correspondence to: O. Ghita     

A stereovision system for a planetary rover: calibration, correlation, registration, and fusion

This paper describes a complete stereovision system, which was originally developed for planetary applications, but can be used for other applications such as object modeling. A new effective on-site calibration technique has been developed, which can make use of the information from the surrounding environment as well as the information from the calibration apparatus. A correlation-based stereo algorithm is used, which can produce sufficient dense range maps with an algorithmic structure for fast implementations. A technique based on iterative closest-point matching has been developed for registration of successive depth maps and computation of the displacements between successive positions. A statistical method based on the distance distribution is integrated into this registration technique, which allows us to deal with such important problems as outliers, occlusion, appearance, and disappearance. Finally, the registered maps are expressed in the same coordinate system and are fused, erroneous data are eliminated through consistency checking, and a global digital elevation map is built incrementally.     

A volume-preserving approach for modeling and animating water flows generated by metaballs

This paper presents a volume-preserving approach for animating liquid flows modeled by metaballs. A volume of liquid can be adjusted to a previous volume by using the influence radius and the maximum density of metaballs as volume-controlling parameters. Recursive subdivision is used to efficiently calculate the volume of implicit surfaces. The criterion for subdivision is obtained by using the concept of interval analysis and the common property of metaball density functions. Providing a sequence of parameters, the volume-compensation region can be controlled according to the substance making up the object, resulting in local preservation of the volume. Set partition is used for determining isolated surfaces in order to apply local-volume preservation. Published online: 23 July 2002 Correspondence to: K. Kaneda     

Model-based interpretation of stereo imagery of textured surfaces

We present a scheme for reliable and accurate surface reconstruction from stereoscopic images containing only fine texture and no stable high-level features. Partial shape information is used to improve surface computation: first by fitting an approximate, global, parametric model, and then by refining this model via local correspondence processes. This scheme eliminates the window size selection problem in existing area-based stereo correspondence schemes. These ideas are integrated in a practical vision system that is being used by environmental scientists to study wind erosion of bulk material such as coal ore being transported in open rail cars. Received: 14 August 1995 / Accepted: 27 May 1997     

The normalform of a space curve and its application to surface design

x )=0 with ∥▿h∥=1. The normalform function h is (unlike the latter cases) not differentiable at curve points. Despite of this disadvantage the normalform is a suitable tool for designing surfaces which can be treated as common implicit surfaces. Many examples (bisector surfaces, constant distance sum/product surfaces, metamorphoses, blending surfaces, smooth approximation surfaces) demonstrate applications of the normalform to surface design. Published online: 25 July 2001     

d-Dimensional parametric models for dynamic animation of deformable objects

This paper introduces an accurate, efficient, and unified engine dedicated to dynamic animation of d-dimensional deformable objects. The objects are modelled as d-dimensional manifolds defined as functional combinations of a mesh of 3D control points, weighted by parametric blending functions. This model ensures that, at each time step, the object shape conforms to its manifold definitions. The object motion is deduced from the control points dynamic animation. In fact, control points should be viewed as the degrees of freedom of the continuous object. The chosen dynamic equations (Lagrangian formalism) reflect this generic modelling scheme and yield an exact and computationally efficient linear system.     

Geometric fusion for a hand-held 3D sensor

Abstract. This article presents a geometric fusion algorithm developed for the reconstruction of 3D surface models from hand-held sensor data. Hand-held systems allow full 3D movement of the sensor to capture the shape of complex objects. Techniques previously developed for reconstruction from conventional 2.5D range image data cannot be applied to hand-held sensor data. A geometric fusion algorithm is introduced to integrate the measured 3D points from a hand-held sensor into a single continuous surface. The new geometric fusion algorithm is based on the normal-volume representation of a triangle, which enables incremental transformation of an arbitrary mesh into an implicit volumetric field function. This system is demonstrated for reconstruction of surface models from both hand-held sensor data and conventional 2.5D range images. Received: 30 August 1999 / Accepted: 21 January 2000     

Active shape from stereo for highway inspection

Abstract. This paper describes an unsupervised algorithm for estimating the 3D profile of potholes in the highway surface, using structured illumination. Structured light is used to accelerate computation and to simplify the estimation of range. A low-resolution edge map is generated so that further processing may be focused on relevant regions of interest. Edge points in each region of interest are used to initialise open, active contour models, which are propagated and refined, via a pyramid, to a higher resolution. At each resolution, internal and external constraints are applied to a snake; the internal constraint is a smoothness function and the external one is a maximum-likelihood estimate of the grey-level response at the edge of each light stripe. Results of a provisional evaluation study indicate that this automated procedure provides estimates of pothole dimension suitable for use in a first, screening, assessment of highway condition. Received: 9 October 1998 / Accepted: 22 February 2000     

THRED: a two-handed design system

This paper describes a computer-aided design system for sketching free-form polygonal surfaces such as terrains and other natural objects. The user manipulates two 3D position and orientation trackers with three buttons, one for each hand. Each hand has a distinct role to play, with the dominant hand being responsible for picking and manipulation, and the less dominant hand being responsible for context setting of various kinds. The less dominant hand holds the workpiece, sets which refinement level that can be picked by the dominant hand, sets the constraint mode and the reshape operator, and generally acts as a counterpoint to the dominant hand. In this paper, the architecture of the system is outlined, the interaction techniques are presented, and a simple surface is shown.