The main goal of this research is the automatic construction of a computer model of 3D solid objects from a single range image. This research has many real world applications, including robotic environments and the inspection of industry parts. The most common methods for 3D-object extraction are based on stereo reconstruction and structured light analysis. The first approach encounters the difficulty of finding a correspondence of points between two images for the same scene, which involves intensive computations. The latter, on the other hand, has limitations and difficulties in object extraction, namely, inferring information about 3D objects from a 2D image. In addition, research in 3D-object extraction up to this point has lacked a thorough treatment of overlapped (occluded) objects.

This research has resulted in a system that can extract multiple polyhedral objects from a single range image. The system consists of several parts: edge detection, segmentation, initial vertex extraction, occlusion detection, grouping faces into objects, and object representation. The problem is difficult especially when occluded objects are present. The system that has been developed separates occluded objects by combining evidence of several types.

In the edge detection algorithm, noise reduction for range images is treated first by implementing a statistically robust technique based on the least median of squares. Three approaches to edge detection are presented. One that detects change in gradient orientation is a novel approach, which is implemented in the algorithm due to its superior performance, and the other two are extensions of work by other researchers. In general, the performance of these edge detection methods is considerably better than many others in the domain of range image segmentation.

A hybrid approach (region-edge based) is introduced to achieve a robust solution for a single range image segmentation. The segmentation process depends on collaborating edge and region techniques where they give complementary information about the scene. Region boundaries are improved using iterative refinement.

A novel approach for initial vertex extraction is presented to find the vertices of the polyhedral objects. The 3D vertex locations for the objects are obtained through an analysis of two-dimensional (2D) region shape and corner proximity, and the vertices of the polyhedra are extracted from the individual faces.

There are two major approaches for dealing with occlusion. The first is an automatic identification of layers of 3D solid objects within a single range image. In this novel approach, a histogram of the distance values from a given range image is clustered into separate modes. Ideally, each mode of the histogram will be associated with one or more surfaces having approximately the same distance from the sensor. This approach works well when the objects are lying at different distances from the sensor, but when two or more objects are overlapped and lying at the same distance from the sensor, this approach has difficulty in detecting occlusion.

The second approach for occlusion detection is considered the major contribution of this work. It detects occlusion of 3D solid objects from a single range image using multiple sources of evidence. This technique is based on detecting occlusion that may be present between each pair of adjacent faces associated with the estimated vertices of the 3D objects. This approach is not based on vertex and line labeling as other approaches are; it utilizes the topology and geometrical information of the 3D objects.

After occlusion detection, faces are grouped into objects according to their adjacency relations and the absence or presence of occlusion between them. The initial vertex estimates are improved significantly through a global optimization procedure. Finally, models of the 3D objects are represented using the boundary representation technique that makes use of the region adjacency graph (RAG) paradigm.

The experimental results of this research were obtained using real range images obtained from the CESAR lab at Oak Ridge National Laboratory. These images were obtained using a Perceptron laser range finder. These images contain single and multiple polyhedral objects, and they have a size of 512x512 pixels and a quantization of 12 bits per pixel.

A quantitative evaluation of the construction algorithms is given. Part of this evaluation depends on the comparison between the results of the proposed segmentation technique and the ground truth database for these range images. The other part is to compare the results of the implemented algorithms with the results of other researchers, and it is found that the system developed here exhibits better performance in terms of the accuracy of the boundaries for the regions of the segmented images. A subjective comparison of the new edge detection methods with some traditional approaches is also provided for the set of range images. An evaluation of the new approach to occlusion detection is also presented.

A recommendation for future work is to extend this system to involve images contain objects with curved surfaces. With some modifications to the multiple evidence-based approach of occlusion detection, the curved objects could be addressed. In addition, the model could be updated to include representation of the hidden surfaces for the 3D objects. This could be achieved by using multiple views for the same scene, or through assumptions such as symmetry to infer the shape of the hidden portion of the objects.