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     

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     

A hybrid approach for stereo disparity computation

An alternative, hybrid approach for disparity estimation, based on the phase difference technique, is presented. The proposed technique combines the robustness of the matching method with the sub-pixel accuracy of the phase difference approach. A matching between the phases of the left and right signals is introduced in order to allow the phase difference method to work in a reduced disparity range. In this framework, a new criterion to detect signal singularities is proposed. The presented test cases show that the performance of the proposed technique in terms of accuracy and density of the disparity estimates has greatly improved. Received: 24 June 1997 / Accepted: 15 September 1998     

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 comparative study of the robustness of two pose estimation techniques

The paper presents an analysis of the stability of pose estimation. Stability is defined as sensitivity of the pose parameters towards noise in image features used for estimating pose. The specific emphasis of the analysis is on determining {how the stability varies with viewpoint} relative to an object and to understand the relationships between object geometry, viewpoint, and pose stability. Two pose estimation techniques are investigated. One uses a numerical scheme for finding pose parameters; the other is based on closed form solutions. Both are “pose from trihedral vertices” techniques, which provide the rotation part of object pose based on orientations of three edge segments. The analysis is based on generalized sensitivity analysis propagating the uncertainty in edge segment orientations to the resulting effect on the pose parameters. It is shown that there is a precomputable, generic relationship between viewpoint and pose stability, and that there is a drastic difference in stability over the range of viewpoints. This viewpoint variation is shared by the two investigated techniques. Additionally, the paper offers an explicit way to determine the most robust viewpoints directly for any given vertex model. Experiments on real images show that the results of the work can be used to compute the variance in pose parameters for any given pose. For the predicted {instable} viewpoints the variance in pose parameters is on the order of 20 (degrees squared), whereas the variance for robust viewpoints is on the order of 0.05 (degrees squared), i.e., two orders of magnitude difference.     

A reconfigurable architecture for autonomous visual-navigation

Abstract. This paper describes the design of a reconfigurable architecture for implementing image processing algorithms. This architecture is a pipeline of small identical processing elements that contain a programmable logic device (FPGA) and double port memories. This processing system has been adapted to accelerate the computation of differential algorithms. The log-polar vision selectively reduces the amount of data to be processed and simplifies several vision algorithms, making possible their implementation using few hardware resources. The reconfigurable architecture design has been devoted to implementation, and has been employed in an autonomous platform, which has power consumption, size and weight restrictions. Two different vision algorithms have been implemented in the reconfigurable pipeline, for which some experimental results are shown. Received: 30 March 2001 / Accepted: 11 February 2002 RID="*" ID="*" This work has been supported by the Ministerio de Ciencia y Tecnología and FEDER under project TIC2001-3546 Correspondence to: J.A. Boluda     

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     

Evaluation of statistical and multiple-hypothesis tracking for video traffic surveillance

Abstract. Conventional tracking methods encounter difficulties as the number of objects, clutter, and sensors increase, because of the requirement for data association. Statistical tracking, based on the concept of network tomography, is an alternative that avoids data association. It estimates the number of trips made from one region to another in a scene based on interregion boundary traffic counts accumulated over time. It is not necessary to track an object through a scene to determine when an object crosses a boundary. This paper describes statistical tracing and presents an evaluation based on the estimation of pedestrian and vehicular traffic intensities at an intersection over a period of 1 month. We compare the results with those from a multiple-hypothesis tracker and manually counted ground-truth estimates. Received: 30 August 2001 / Accepted: 28 May 2002 Correspondence to: J.E. Boyd     

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     

Direct linear sub-pixel correlation by incorporation of neighbor pixels' information and robust estimation of window transformation

Standard methods for sub-pixel matching are iterative and nonlinear; they are also sensitive to false initialization and window deformation. In this paper, we present a linear method that incorporates information from neighboring pixels. Two algorithms are presented: one ‘fast’ and one ‘robust’. They both start from an initial rough estimate of the matching. The fast one is suitable for pairs of images requiring negligible window deformation. The robust method is slower but more general and more precise. It eliminates false matches in the initialization by using robust estimation of the local affine deformation. The first algorithm attains an accuracy of 0.05 pixels for interest points and 0.06 for random points in the translational case. For the general case, if the deformation is small, the second method gives an accuracy of 0.05 pixels; while for large deformation, it gives an accuracy of about 0.06 pixels for points of interest and 0.10 pixels for random points. They are very few false matches in all cases, even if there are many in the initialization. Received: 24 July 1997 / Accepted: 4 December 1997     

Fast template matching using bounded partial correlation

This paper describes a novel, fast template-matching technique, referred to as bounded partial correlation (BPC), based on the normalised cross-correlation (NCC) function. The technique consists in checking at each search position a suitable elimination condition relying on the evaluation of an upper-bound for the NCC function. The check allows for rapidly skipping the positions that cannot provide a better degree of match with respect to the current best-matching one. The upper-bounding function incorporates partial information from the actual cross-correlation function and can be calculated very efficiently using a recursive scheme. We show also a simple improvement to the basic BPC formulation that provides additional computational benefits and renders the technique more robust with respect to the parameters choice. Received: 2 November 2000 / Accepted: 25 July 2001 Correspondence to: L. Di Stefano     

Robust real-time ground plane motion compensation from a moving vehicle

One method to detect obstacles from a vehicle moving on a planar road surface is the analysis of motion-compensated difference images. In this contribution, a motion compensation algorithm is presented, which computes the required image-warping parameters from an estimate of the relative motion between camera and ground plane. The proposed algorithm estimates the warping parameters from displacements at image corners and image edges. It exploits the estimated confidence of the displacements to cope robustly with outliers. Knowledge about camera calibration, measuremts from odometry, and the previous estimate are used for motion prediction and to stabilize the estimation process when there is not enough information available in the measured image displacements. The motion compensation algorithm has been integrated with modules for obstacle detection and lane tracking. This system has been integrated in experimental vehicles and runs in real time with an overall cycle of 12.5 Hz on low-cost standard hardware. Received: 23 April 1998 / Accepted: 25 August 1999     

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     

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     

Subgrid stabilization of Galerkin approximations of linear contraction semi-groups of class C0

This paper presents a stabilized Galerkin technique for approximating linear contraction semi-groups of class C⁰ in a Hilbert space. The main result of this paper is that this technique yields optimal error estimates in the graph norm. The key idea is twofold, first it consists in introducing an approximation space that is broken up into resolved scales and subgrid scales so that the generator of the semi-group satisfies a uniform inf-sup condition with respect to this decomposition. Second, the Galerkin approximation is slightly modified by introducing an artificial diffusion acting only on the subgrid scales. Received: 30 April 1999 / Revised version: 17 June 1999     

A projectively invariant intersection test for polyhedra

Although intersection relations are projectively invariant, most existing intersection detection tests for arbitrary polyhedra can give different results before and after a nonsingular arbitrary projective transformation of the polyhedra under test. This paper presents a projectively invariant intersection test for general polyhedra whose only numerical part is the computation of 4×4 determinants of homogeneous vertex coordinates. Degeneracies are resolved using a technique of symbolic infinitesimals which also reduces to the computation of 4×4 determinants. This greatly simplifies the implementation of the test in hardware. Moreover, its projective invariance permits applying it at any point in the graphics pipeline. Since no auxiliary geometric entities need to be computed, the presented test can be concisely expressed as a Boolean formula, instead of a procedure. Published online: 15 March 2002 Correspondence to: F. Thomas     

Adaptive image-smoothing using a coplanar matrix and its application to document image binarization

Abstract. For document images corrupted by various kinds of noise, direct binarization images may be severely blurred and degraded. A common treatment for this problem is to pre-smooth input images using noise-suppressing filters. This article proposes an image-smoothing method used for prefiltering the document image binarization. Conceptually, we propose that the influence range of each pixel affecting its neighbors should depend on local image statistics. Technically, we suggest using coplanar matrices to capture the structural and textural distribution of similar pixels at each site. This property adapts the smoothing process to the contrast, orientation, and spatial size of local image structures. Experimental results demonstrate the effectiveness of the proposed method, which compares favorably with existing methods in reducing noise and preserving image features. In addition, due to the adaptive nature of the similar pixel definition, the proposed filter output is more robust regarding different noise levels than existing methods. Received: October 31, 2001 / October 09, 2002 Correspondence to:L. Fan (e-mail: fanlixin@ieee.org)     

Optic flow estimation by a Hopfield neural network using geometrical constraints

Sparse optic flow maps are general enough to obtain useful information about camera motion. Usually, correspondences among features over an image sequence are estimated by radiometric similarity. When the camera moves under known conditions, global geometrical constraints can be introduced in order to obtain a more robust estimation of the optic flow. In this paper, a method is proposed for the computation of a robust sparse optic flow (OF) which integrates the geometrical constraints induced by camera motion to verify the correspondences obtained by radiometric-similarity-based techniques. A raw OF map is estimated by matching features by correlation. The verification of the resulting correspondences is formulated as an optimization problem that is implemented on a Hopfield neural network (HNN). Additional constraints imposed in the energy function permit us to achieve a subpixel accuracy in the image locations of matched features. Convergence of the HNN is reached in a small enough number of iterations to make the proposed method suitable for real-time processing. It is shown that the proposed method is also suitable for identifying independently moving objects in front of a moving vehicle. Received: 26 December 1995 / Accepted: 20 February 1997     

A vision system based on a laser range-finder applied to robotic fruit harvesting

This paper describes a laser-based computer vision system used for automatic fruit recognition. It is based on an infrared laser range-finder sensor that provides range and reflectance images and is designed to detect spherical objects in non-structured environments. Image analysis algorithms integrate both range and reflectance information to generate four characteristic primitives which give evidence of the existence of spherical objects. The output of this vision system includes 3D position, radius and surface reflectivity of each spherical object. It has been applied to the AGRIBOT orange harvesting robot, where it has obtained good fruit detection rates and unlikely false detections.     

Self-stabilization with r-operators

This paper describes a parameterized distributed algorithm applicable to any directed graph topology. The function parameter of our algorithm is instantiated to produce distributed algorithms for both fundamental and high level applications, such as shortest path calculus and depth-first-search tree construction. Due to fault resilience properties of our algorithm, the resulting protocols are self-stabilizing at no additional cost. Self-stabilizing protocols can resist transient failures and guarantee system recovery in a finite time. Since the condition on the function parameter (being a strictly idempotent r-operator) permits a broad range of applications to be implemented, the solution presented in our paper can be useful for a large class of distributed systems. Received: August 1999 / Accepted: January 2001