On combining range and intensity data

This paper addresses the problem of combining range and intensity data for scene analysis. Although both sources of information describe the same scene, they are very dissimilar. To place both sources of information in the same form, the edge maps of the range image and of the intensity image are derived. An initial step in examining the edge maps is to observe which edges they have in common. Two procedures for extracting the edges common to the range image and the intensity image are presented.     

Recent progress in object recognition from range data

Within the last half decade active devices have been able to provide three-dimensional data directly to vision systems. This paper examines some of the progress that has been made with this data in the field of 3D computer vision. Aspects of this field from acquisition to recognition are discussed and some major research results are reviewed.     

Invariant surface and motion estimation from sparse range data

In this paper, we present a system for the estimation of the surface structure and the motion parameters of a free-flying object in a tele-robotics experiment. The system consists of two main components: (i) a vision-based invariant-surface and motion estimator and (ii) a Kalman filter state estimator. We present a new algorithm for motion estimation from sparse multi-sensor range data. The motion estimates from the vision-based estimator are input to a Kalman filter state estimator for continuously tracking a free-flying object in space under zero-gravity conditions. The predicted position and orientation parameters are then fed back to the vision module of the system and serve as an initial guess in the search for optimal motion parameters. The task of the vision module is two-fold: (i) estimating a piecewise-smooth surface from a single frame of multi-sensor data and (ii) determining the most likely (in the Bayesian sense) object motion that makes data in subsequent time frames to have been sampled from the same piecewise-smooth surface. With each incoming data frame, the piecewise-smooth surface is incrementally refined. The problem is formulated as an energy minimization and solved numerically resulting in a surface estimate invariant to 3D rigid motion and the vector of motion parameters. Performance of the system is depicted on simulated and real range data.     

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     

Robust real-time 3D head pose estimation from range data

In this paper a real-time 3D pose estimation algorithm using range data is described. The system relies on a novel 3D sensor that generates a dense range image of the scene. By not relying on brightness information, the proposed system guarantees robustness under a variety of illumination conditions, and scene contents. Efficient face detection using global features and exploitation of prior knowledge along with novel feature localization and tracking techniques are described. Experimental results demonstrate accurate estimation of the six degrees of freedom of the head and robustness under occlusions, facial expressions, and head shape variability.     

Robust deformation capture from temporal range data for surface rendering

Imagine an object such as a paper sheet being waved in front of some sensor. Reconstructing the time‐varying 3D shape of the object finds direct applications in computer animation. The goal of this paper is to provide such a deformation capture system for surfaces. It uses temporal range data obtained by sensors such as those based on structured light or stereo. So as to deal with many different kinds of material, we do not make the usual assumption that the object surface has textural information. This rules out those techniques based on detecting and matching keypoints or directly minimizing color discrepancy. The proposed method is based on a planar mesh that is deformed so as to fit each of the range images. We show how to achieve this by minimizing a compound cost function combining several data and regularization terms, needed to make the overall system robust so that it can deal with low quality datasets. Carefully examining the parameter to residual relationship shows that this cost function can be minimized very efficiently by coupling nonlinear least squares methods with sparse matrix operators. Experimental results for challenging datasets coming from different kinds of range sensors are reported. The algorithm is reasonably fast and is shown to be robust to missing and erroneous data points. Copyright © 2008 John Wiley & Sons, Ltd.     

On optimally combining pieces of information, with application to estimating 3-d complex-object position from range data

New asymptotic methods are introduced that permit computationally simple Bayesian recognition and parameter estimation for many large data sets described by a combination of algebraic, geometric, and probabilistic models. The techniques introduced permit controlled decomposition of a large problem into small problems for separate parallel processing where maximum likelihood estimation or Bayesian estimation or recognition can be realized locally. These results can be combined to arrive at globally optimum estimation or recognition. The approach is applied to the maximum likelihood estimation of 3-D complex-object position. To this end, the surface of an object is modeled as a collection of patches of primitive quadrics, i.e., planar, cylindrical, and spherical patches, possibly augmented by boundary segments. The primitive surface-patch models are specified by geometric parameters, reflecting location, orientation, and dimension information. The object-position estimation is based on sets of range data points, each set associated with an object primitive. Probability density functions are introduced that model the generation of range measurement points. This entails the formulation of a noise mechanism in three-space accounting for inaccuracies in the 3-D measurements and possibly for inaccuracies in the 3-D modeling. We develop the necessary techniques for optimal local parameter estimation and primitive boundary or surface type recognition for each small patch of data, and then optimal combining of these inaccurate locally derived parameter estimates in order to arrive at roughly globally optimum object-position estimation.     

Coarse-to-fine surface reconstruction from silhouettes and range data using mesh deformation

We present a coarse-to-fine surface reconstruction method based on mesh deformation to build watertight surface models of complex objects from their silhouettes and range data. The deformable mesh, which initially represents the object visual hull, is iteratively displaced towards the triangulated range surface using the line-of-sight information. Each iteration of the deformation algorithm involves smoothing and restructuring operations to regularize the surface evolution process. We define a non-shrinking and easy-to-compute smoothing operator that fairs the surface separately along its tangential and normal directions. The mesh restructuring operator, which is based on edge split, collapse and flip operations, enables the deformable mesh to adapt its shape to the object geometry without suffering from any geometrical distortions. By imposing appropriate minimum and maximum edge length constraints, the deformable mesh, hence the object surface, can be represented at increasing levels of detail. This coarse-to-fine strategy, that allows high resolution reconstructions even with deficient and irregularly sampled range data, not only provides robustness, but also significantly improves the computational efficiency of the deformation process. We demonstrate the performance of the proposed method on several real objects.     

Face recognition based on 3D ridge images obtained from range data

In this paper, we present an approach for 3D face recognition from frontal range data based on the ridge lines on the surface of the face. We use the principal curvature, k_max, to represent the face image as a 3D binary image called ridge image. The ridge image shows the locations of the ridge points around the important facial regions on the face (i.e., the eyes, the nose, and the mouth). We utilized the robust Hausdorff distance and the iterative closest points (ICP) for matching the ridge image of a given probe image to the ridge images of the facial images in the gallery. To evaluate the performance of our approach for 3D face recognition, we performed experiments on GavabDB face database (a small size database) and Face Recognition Grand Challenge V2.0 (a large size database). The results of the experiments show that the ridge lines have great capability for 3D face recognition. In addition, we found that as long as the size of the database is small, the performance of the ICP-based matching and the robust Hausdorff matching are comparable. But, when the size of the database increases, ICP-based matching outperforms the robust Hausdorff matching technique.     

Geometric probing of dense range data

A new method is presented for the efficient and reliable pose determination of 3D objects in dense range image data. The method is based upon a minimalistic Geometric Probing strategy that hypothesizes the intersection of the object with some selected image point, and searches for additional surface data at locations relative to that point. The strategy is implemented in the discrete domain as a binary decision tree classifier. The tree leaf nodes represent individual voxel templates of the model, with one template per distinct model pose. The internal nodes represent the union of the templates of their descendant leaf nodes. The union of all leaf node templates is the complete template set of the model over its discrete pose space. Each internal node also encodes a single voxel which is the most common element of its child node templates. Traversing the free is equivalent to efficiently matching the large set of templates at a selected image seed location. The method was implemented and extensive experiments were conducted for a variety of combinations of tree designs and traversals under isolated, cluttered, and occluded scene conditions. The results demonstrated a tradeoff between efficiency and reliability. It was concluded that there exist combinations of tree design and traversal which are both highly efficient and reliable     

Robust segmentation of primitives from range data in the presenceof geometric degeneracy

This paper addresses a common problem in the segmentation of range images. We present methods for the least-squares fitting of spheres, cylinders, cones, and tori to 3D point data, and their application within a segmentation framework. Least-squares fitting of surfaces other than planes, even of simple geometric type, has rarely been studied. Our main application areas of this research are reverse engineering of solid models from depth-maps and automated 3D inspection where reliable extraction of these surfaces is essential. Our fitting method has the particular advantage of being robust in the presence of geometric degeneracy, i.e., as the principal curvatures of the surfaces being fitted decrease, the results returned naturally become closer and closer to those surfaces of “simpler type”, i.e., planes, cylinders, cones, or spheres, which best describe the data. Many other methods diverge because, in such cases, various parameters or their combination become infinite     

A volumetric fusion technique for surface reconstruction from silhouettes and range data

Optical triangulation, an active reconstruction technique, is known to be an accurate method but has several shortcomings due to occlusion and laser reflectance properties of the object surface, that often lead to holes and inaccuracies on the recovered surface. Shape from silhouette, on the other hand, as a passive reconstruction technique, yields robust, hole-free reconstruction of the visual hull of the object. In this paper, a hybrid surface reconstruction method that fuses geometrical information acquired from silhouette images and optical triangulation is presented. Our motivation is to recover the geometry from silhouettes on those parts of the surface which the range data fail to capture. A volumetric octree representation is first obtained from the silhouette images and then carved by range points to amend the missing cavity information. An isolevel value on each surface cube of the carved octree structure is accumulated using local surface triangulations obtained separately from range data and silhouettes. The marching cubes algorithm is then applied for triangulation of the volumetric representation. The performance of the proposed technique is demonstrated on several real objects.     

Categorization of indoor places by combining local binary pattern histograms of range and reflectance data from laser range finders

This paper presents an approach to categorize typical places in indoor environments using 3D scans provided by a laser range finder. Examples of such places are offices, laboratories, or kitchens. In our method, we combine the range and reflectance data from the laser scan for the final categorization of places. Range and reflectance images are transformed into histograms of local binary patterns and combined into a single feature vector. This vector is later classified using support vector machines. The results of the presented experiments demonstrate the capability of our technique to categorize indoor places with high accuracy. We also show that the combination of range and reflectance information improves the final categorization results in comparison with a single modality.     

On the problem of correspondence in range data and some inelasticuses for elastic nets

In this work, the authors propose a novel method to obtain correspondence between range data across image frames using neural like mechanisms. The method is computationally efficient and tolerant of noise and missing points. Elastic nets, which evolved out of research into mechanisms to establish ordered neural projections between structures of similar geometry, are used to cast correspondence as an optimization problem. This formulation is then used to obtain approximations to the motion parameters under the assumption of rigidity (inelasticity). These parameter scan be used to recover correspondence. Experimental results are presented to establish the veracity of the scheme and the method is compared to earlier attempts in this direction.     

Efficient data structures for model-based 3-D object recognitionand localization from range images

An effective method of surface characterization of 3D objects using surface curvature properties and an efficient approach to recognizing and localizing multiple 3D free-form objects (free-form object recognition and localization) are presented. The approach is surface based and is therefore not sensitive to noise and occlusion, forms hypothesis by local analysis of surface shapes, does not depend on the visibility of complete objects, and uses information from a CAD database in recognition and localization. A knowledge representation scheme for describing free-form surfaces is described. The data structure and procedures are well designed, so that the knowledge leads the system to intelligent behavior. Knowledge about surface shapes is abstracted from CAD models to direct the search in verification of vision hypotheses. The knowledge representation used eases processes of knowledge acquisition, information retrieval, modification of knowledge base, and reasoning for solution     

The role of model-based segmentation in the recovery of volumetricparts from range data

We present a method for segmenting and estimating the shape of 3D objects from range data. The technique uses model views, or aspects, to constrain the fitting of deformable models to range data. Based on an initial region segmentation of a range image, regions are grouped into aspects corresponding to the volumetric parts that make up an object. The qualitative segmentation of the range image into a set of volumetric parts not only captures the coarse shape of the parts, but qualitatively encodes the orientation of each part through its aspect. Knowledge of a part's coarse shape, its orientation, as well as the mapping between the faces in its aspect and the surfaces on the part provides strong constraints on the fitting of a deformable model (supporting both global and local deformations) to the data. Unlike previous work in physics-based deformable model recovery from range data, the technique does not require presegmented data. Furthermore, occlusion is handled at segmentation time and does not complicate the fitting process, as only 3D points known to belong to a part participate in the fitting of a model to the part. We present the approach in detail and apply it to the recovery of objects from range data