Volume-based three-dimensional metamorphosis using sphere-guided region correspondence

surface metamorphosis extends this paradigm by interpolating between discrete volume representations of the surfaces. The insensitivity of the established techniques to the surface topology enables morphing between completely different surfaces: however it can also lead to intermediate surfaces which have different topology from the originals. We present a method which improves on this situation by ensuring that no part of each surface remains disconnected during the morph. The morph is guided by region correspondence, derived automatically from a sphere representation of each surface: this can be combined with manual correspondence to retain user control over the morph. What emerges is a fast and flexible method for morphing surfaces, as demonstrated on several examples. Published online: 19 July 2001     

Automatic high-resolution optoelectronic photogrammetric 3D surface geometry acquisition system

A fast, high-resolution, automatic, non-contact 3D surface geometry measuring system using a photogrammetric optoelectronic technique based on lateral-photoeffect diode detectors has been developed. Designed for the acquisition of surface geometries such as machined surfaces, biological surfaces, and deformed parts, the system can be used in design, manufacturing, inspection, and range finding. A laser beam is focused and scanned onto the surface of the object to be measured. Two cameras in stereo positions capture the reflected light from the surface at 10 kHz. Photogrammetric triangulation quickly transforms the pair of 2D signals created by the camera detectors into 3D coordinates of the light spot. Because only one small spot on the object is illuminated at a time, the stereo correspondence problem is solved in real time. The resolution is determined by a 12-bit A/D converter and can be improved up to 25 60025 600 by oversampling. The irregular 3D data can be regularized for use with image-based algorithms. Received: 8 October 1996 / Accepted: 3 February 1997     

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 stereo-vision system for support of planetary surface exploration

Abstract. In this paper, we present a system that was developed for the European Space Agency (ESA) for the support of planetary exploration. The system that is sent to the planetary surface consists of a rover and a lander. The lander contains a stereo head equipped with a pan-tilt mechanism. This vision system is used both for modeling the terrain and for localization of the rover. Both tasks are necessary for the navigation of the rover. Due to the stress that occurs during the flight, a recalibration of the stereo-vision system is required once it is deployed on the planet. Practical limitations make it unfeasible to use a known calibration pattern for this purpose; therefore, a new calibration procedure had to be developed that could work on images of the planetary environment. This automatic procedure recovers the relative orientation of the cameras and the pan and tilt axes, as well as the exterior orientation for all the images. The same images are subsequently used to reconstruct the 3-D structure of the terrain. For this purpose, a dense stereo-matching algorithm is used that (after rectification) computes a disparity map. Finally, all the disparity maps are merged into a single digital terrain model. In this paper, a simple and elegant procedure is proposed that achieves that goal. The fact that the same images can be used for both calibration and 3-D reconstruction is important, since, in general, the communication bandwidth is very limited. In addition to navigation and path planning, the 3-D model of the terrain is also used for virtual-reality simulations of the mission, wherein the model is texture mapped with the original images. The system has been implemented, and the first tests on the ESA planetary terrain testbed were successful.     

Machine tool condition monitoring using workpiece surface texture analysis

Tool wear affects the surface roughness dramatically. There is a very close correspondence between the geometrical features imposed on the tool by wear and micro-fracture and the geometry imparted by the tool on to the workpiece surface. Since a machined surface is the negative replica of the shape of the cutting tool, and reflects the volumetric changes in cutting-edge shape, it is more suitable to analyze the machined surface than look at a certain portion of the cutting tool. This paper discusses our work that analyzes images of workpiece surfaces that have been subjected to machining operations and investigates the correlation between tool wear and quantities characterizing machined surfaces. Our results clearly indicate that tool condition monitoring (the distinction between a sharp, semi-dull, or a dull tool) can be successfully accomplished by analyzing surface image data. Received: 9 June 1998 / Accepted: 6 October 1999     

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     

Impact of video scheduling on bandwidth allocation for multiplexed MPEG streams

We present efficient schemes for scheduling the delivery of variable-bit-rate MPEG-compressed video with stringent quality-of-service (QoS) requirements. Video scheduling is being used to improve bandwidth allocation at a video server that uses statistical multiplexing to aggregate video streams prior to transporting them over a network. A video stream is modeled using a traffic envelope that provides a deterministic time-varying bound on the bit rate. Because of the periodicity in which frame types in an MPEG stream are typically generated, a simple traffic envelope can be constructed using only five parameters. Using the traffic-envelope model, we show that video sources can be statistically multiplexed with an effective bandwidth that is often less than the source peak rate. Bandwidth gain is achieved without sacrificing the stringency of the requested QoS. The effective bandwidth depends on the arrangement of the multiplexed streams, which is a measure of the lag between the GOP periods of various streams. For homogeneous streams, we give an optimal scheduling scheme for video sources at a video-on-demand server that results in the minimum effective bandwidth. For heterogeneous sources, a sub-optimal scheduling scheme is given, which achieves acceptable bandwidth gain. Numerical examples based on traces of MPEG-coded movies are used to demonstrate the effectiveness of our schemes.     

A scalable storage supporting multistream real-time data retrieval

This paper presents a new data placement scheme for continuous-media playback via a scalable storage system. Multimedia contents are segmented into data blocks for the purpose of being stored, retrieved, and manipulated. If these data blocks belong to some continuous media, then they must be handled in a timely manner, for example, being retrieved before some deadline. One of the main challenges in implementing the above system is the simultaneous retrieval of a great number of different media streams from a very large storage system. The proposed scheme efficiently reduces the seeking delay by a very simple placement method and a retrieval scheduler. Thus, both the storage capacity and the number of concurrent accesses to the storage are scalable. The performance of the proposed scheme is evaluated through a simple analytical model and a practical prototype implementation.     

Protocol synthesis and re-synthesis with optimal allocation of resources based on extended Petri nets

Protocol synthesis is used to derive a protocol specification, that is, the specification of a set of application components running in a distributed system of networked computers, from a specification of services (called the service specification) to be provided by the distributed application to its users. Protocol synthesis reduces design costs and errors by specifying the message exchanges between the application components, as defined by the protocol specification. In general, maintaining such a distributed application involves applying frequent minor modifications to the service specification due to changes in the user requirements. Deriving the protocol specification after each modification using the existing synthesis methods is considered expensive and time consuming. Moreover, we cannot identify what changes we should make to the protocol specification in correspondence to the changes in the service specification. In this paper, we present a new synthesis method to re-synthesize only those parts of the protocol specification that must be modified in order to satisfy the changes in the service specification. The method consists of a set of simple rules that are applied to the protocol specification written in an extended Petri net model. An application example is given along with some experimental results. Received: July 2001 / Accepted: July 2002 RID="*" ID="*" Supported by International Communications Foundation (ICF), Japan RID="**" ID="**" Supported by Communications and Information Technology Ontario (CITO) and Natural Sciences and Engineering Research Council (NSERC), Canada RID="*" ID="*" Supported by International Communications Foundation (ICF), Japan     

Robust and efficient surface reconstruction from contours

We propose a new approach for surface recovery from planar sectional contours. The surface is reconstructed based on the so-called “equal importance criterion,” which suggests that every point in the region contributes equally to the reconstruction process. The problem is then formulated in terms of a partial differential equation, and the solution is efficiently calculated from distance transformation. To make the algorithm valid for different application purposes, both the isosurface and the primitive representations of the object surface are derived. The isosurface is constructed by means of a partial differential equation, which can be solved iteratively. The traditional distance interpolating method, which was used by several researchers for surface reconstruction, is an approximate solution of the equation. The primitive representations are approximated by Voronoi diagram transformation of the surface space. Isosurfaces have the advantage that subsequent geometric analysis of the object can be easily carried out while primitive representation is easy to visualize. The proposed technique allows for surface recovery at any desired resolution, thus avoiding the inherent problems of correspondence, tiling, and branching.     

Evaluation of correspondence errors for stereo

The computation of a scalar correspondence error is the fundamental step in most stereo correspondence algorithms. The quality of the results obtained by the reconstruction algorithm directly depends on the characteristics of such error. We have developed a procedure to evaluate different methods proposed for the computation of the correspondence error. The evaluation is based on exploring the shape of the error surface generated and testing it for uniqueness, isolation and compatibility. The scheme presented makes it possible to recognise the known characteristics of the tested methods for the computation of a correspondence error from the results of the evaluations. Our results show that, for the tested scenes, the evaluation scheme allows us to identify the most appropriate method to compute the correspondence error.     

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     

Accuracy bounds and optimal computation of robot localization

We present an optimal method for estimating the current location of a mobile robot by matching an image of the scene taken by the robot with a model of the known environment. We first derive a theoretical accuracy bound and then give a computational scheme that can attain that bound, which can be viewed as describing the probability distribution of the current location. Using real images, we demonstrate that our method is superior to the naive least-squares method. We also confirm the theoretical predictions of our theory by applying the bootstrap procedure. Received: 17 March 1998 / Accepted: 7 April 2001     

An automatic assessment scheme for steel quality inspection

This paper presents an automatic system for steel quality assessment, by measuring textural properties of carbide distributions. In current steel inspection, specially etched and polished steel specimen surfaces are classified manually under a light microscope, by comparisons with a standard chart. This procedure is basically two-dimensional, reflecting the size of the carbide agglomerations and their directional distribution. To capture these textural properties in terms of image fea tures, we first apply a rich set of image-processing operations, including mathematical morphology, multi-channel Gabor filtering, and the computation of texture measures with automatic scale selection in linear scale-space. Then, a feature selector is applied to a 40-dimensional feature space, and a classification scheme is defined, which on a sample set of more than 400 images has classification performance values comparable to those of human metallographers. Finally, a fully automatic inspection system is designed, which actively selects the most salient carbide structure on the specimen surface for subsequent classification. The feasibility of the overall approach for future use in the production process is demonstrated by a prototype system. It is also shown how the presented classification scheme allows for the definition of a new reference chart in terms of quantitative measures. Received: 16 February 1999 / Accepted: 29 March 2000     

Tracking the human arm using constraint fusion and multiple-cue localization

Abstract. The use of hand gestures provides an attractive means of interacting naturally with a computer-generated display. Using one or more video cameras, the hand movements can potentially be interpreted as meaningful gestures. One key problem in building such an interface without a restricted setup is the ability to localize and track the human arm robustly in video sequences. This paper proposes a multiple-cue localization scheme combined with a tracking framework to reliably track the dynamics of the human arm in unconstrained environments. The localization scheme integrates the multiple cues of motion, shape, and color for locating a set of key image features. Using constraint fusion, these features are tracked by a modified extended Kalman filter that exploits the articulated structure of the human arm. Moreover, an interaction scheme between tracking and localization is used for improving the estimation process while reducing the computational requirements. The performance of the localization/tracking framework is validated with the help of extensive experiments and simulations. These experiments include tracking with calibrated stereo camera and uncalibrated broadcast video. Received: 19 January 2001 / Accepted: 27 December 2001 Correspondence to: R. Sharma     

Synchronization and recovery in a client-server storage system

Client-server object-oriented database management systems differ significantly from traditional centralized systems in terms of their architecture and the applications they target. In this paper, we present the client-server architecture of the EOS storage manager and we describe the concurrency control and recovery mechanisms it employs. EOS offers a semi-optimistic locking scheme based on the multi-granularity two-version two-phase locking protocol. Under this scheme, multiple concurrent readers are allowed to access a data item while it is being updated by a single writer. Recovery is based on write-ahead redo-only logging. Log records are generated at the clients and they are shipped to the server during normal execution and at transaction commit. Transaction rollback is fast because there are no updates that have to be undone, and recovery from system crashes requires only one scan of the log for installing the changes made by transactions that committed before the crash. We also present a preliminary performance evaluation of the implementation of the above mechanisms. Edited by R. King. Received July 1993 / Accepted May 1996     

Range image segmentation using local approximation of scan lines with application to CAD model acquisition

Abstract. Automatic acquisition of CAD models from existing objects requires accurate extraction of geometric and topological information from the input data. This paper presents a range image segmentation method based on local approximation of scan lines. The method employs edge models that are capable of detecting noise pixels as well as position and orientation discontinuities of varying strengths. Region-based techniques are then used to achieve a complete segmentation. Finally, a geometric representation of the scene, in the form of a surface CAD model, is produced. Experimental results on a large number of real range images acquired by different range sensors demonstrate the efficiency and robustness of the method. Received: 1 August 2000 / Accepted: 23 January 2002 Correspondence to: I. Khalifa     

An evaluation of design trade-offs in a high-performance, media-on-demand server

We present a high-performance solution to the I/O retrieval problem in a distributed multimedia system. Parallelism of data retrieval is achieved by striping the data across multiple disks. We identify the components that contribute to media data-retrieval delay. The variable delays among these have a great bearing on the server throughput under varying load conditions. We present a buffering scheme to minimize these variations. We have implemented our model on the Intel Paragon parallel computer. The results of component-wise instrumentation of the server operation are presented and analyzed. Experimental results that demonstrate the efficacy of the buffering scheme are presented. Based on our experiments, a dynamic admission-control policy that takes server workloads into account is proposed.     

Robust online detection of pipeline corrosion from range data

We present the Finite-Window Robust Sequential Estimator for the detection and analysis of corrosion in range images of gas pipelines. This statistically robust, real-time technique estimates the pipeline surface range function in the presence of noise, surface deviations, and changes in the underlying model. Deviations from the robust surface fit, corresponding to statistical outliers, represent potential areas of corrosion. Because the algorithm estimates surface parameters over a finite, sliding window of data, it can track moderately high-order surfaces using lower order models. The system is consistent, objective, and non-destructive and can be used with the pipeline in service. Received: 7 September 1999 / Accepted: 2 November 2000     

A compact algorithm for rectification of stereo pairs

Abstract. We present a linear rectification algorithm for general, unconstrained stereo rigs. The algorithm takes the two perspective projection matrices of the original cameras, and computes a pair of rectifying projection matrices. It is compact (22-line MATLAB code) and easily reproducible. We report tests proving the correct behavior of our method, as well as the negligible decrease of the accuracy of 3D reconstruction performed from the rectified images directly. Received: 25 February 1999 / Accepted: 2 March 2000