Retrieval of Shape from Silhouette

Andrea Bottino; Aldo Laurentini    Dipartimento di Automatica e Informatica, Politecnico di Torino, 10129, Torino, Italy

I INTRODUCTION

A Reconstructing Three-Dimensional Shapes: General Techniques

The reconstruction of three-dimensional (3D) shapes is a fundamental research field in computer vision. A large number of techniques have been discussed and implemented, depending first on the type of sensors used. Active 3D scanning is currently a leading technology. Most active 3D scanners use ranging techniques (time of flight, phase comparison) or triangulation with laser beams. Their main feature is producing depth maps that are close to the final 3D shape (Figure 1).

However, 3D scanners are expensive and are affected by several limitations. They are rather invasive, different equipments are required for scanning objects of different sizes, scanning outdoor large scenes presents several problems, and scanning times are not adequate for real time applications, such as capturing the shape of objects in motion.

For these reasons, in several practical situations traditional image-based computer vision approaches are more effective. For instance, an important emerging area usually requiring image-based approaches is the analysis of human body movements (Figure 2).

Several passive approaches, based on 2D images captured by inexpensive cameras, have been proposed, usually referred to as shape from X, where X stands for some image feature that can be used as a 3D shape cue (Aloimonos, 1988). Among them are stereo (disparity), texture, motion, focus, shading, and silhouettes. An advantage of image-based approaches is that they can easily supply 3D textured reconstructed objects. Actually, most of these approaches require textured objects, or lines called image contours.

Some of these approaches, such as shape from shading (Zhang et al., 1999), require a number of hypotheses and conditions that seldom take place in practice. The most effective approaches are shape from stereo and shape from contours. Shape from stereo requires images from (at least) two cameras and matching algorithms for determining corresponding points in the two images (Trucco and Verri, 1998). From the different positions in the images of the corresponding points (stereo disparity), and camera geometry, it is easy to find the 3D position of a point. Shape from motion in principle is an extension of shape from stereo, since it considers multiple images of the same objects taken with the same camera from different relative positions, and also requires finding correspondences in the various images. The purpose of this work is to discuss the theory and practice of shape from silhouettes.

B Shape from Silhouettes

Many algorithms for reconstructing 3D objects from two-dimensional (2D) image features are based on particular lines called image contours. Actually, these lines can be also used for recognizing 3D objects. This approach mimics to some extent the human vision, since we are often able to understand the solid shape of an object from a few image lines laid out on a plane (Gibson, 1951; Koenderink and van Doorn, 1979).

In general, from an image of a 3D object we can extract various kinds of lines, separating areas of different intensities or colors. Some of them are not directly related to the 3D shape, and correspond to different surface properties, or to abrupt changes of the incident light. Other lines are directly related to the surface of the object. They are usually called edges and occluding contours (see Figure 3).

The edges are the projections of the creases of the object (surface normal discontinuities), and are not present in images of smooth surface objects. The lines called occluding contours (apparent contours, limbs) are the projection onto the image plane of the contour generators of the objects. A contour generator is a locus of points of the object surface where there is a depth discontinuity along the line of sight.

The lines related to the 3D shape (occluding contours and edges) produce line drawings that can be organized into the aspect graph, a user-centered representation of 3D objects first proposed by Koenderink and van Doorn (1979).

With the word silhouette we indicate the area of the image bounded by the contours that occlude the background. Sometimes the word silhouette is used for the boundary of this area. The idea of using silhouettes to reconstruct 3D shapes was first introduced in the pioneering work of Baumgart (1974). Since then, several variations of the shape from silhouettes methods have been proposed. For example, Martin and Aggarwal (1983) and Kim and Aggarwal (1986) used volumetric descriptions to represent the reconstructed shape. Potemesil (1987), Noborio et al. (1988), and Ahuja and Veenstra (1989) used octree data structure to accelerate the reconstruction process. Shape from silhouettes has also been used by Szeliski (1993) to build a noninvasive 3D digitizer using a turntable and a single camera. Other recent techniques (Kutulakos and Seitz, 2000; Matusik et al., 2001; Slabaugh et al., 2003) stem from this idea.

In principle, reconstruction from silhouette requires backprojecting the silhouettes from the corresponding viewpoints to obtain solid cones. They are bounded by the circumscribed cones formed by the half-lines tangent to the object. Since the object must lie inside each cone, it must also lie inside their intersection R, which summarizes the information provided by all silhouettes and viewpoints (Figure 4). This reconstruction technique is called volume intersection (VI).

Silhouette-based techniques are popular because silhouettes are usually easy to extract from images. This operation is particularly fast and robust with controlled background, or for objects in motion with respect to the background. Another important feature of the silhouette-based techniques is that they are convenient for real time applications.

However, one drawback of this approach is that, depending on the object, the information provided by its silhouettes could be insufficient to fully understand a 3D concave shape. The problem, qualitatively perceived by several researchers in the field, received a full quantitative solution in Laurentini (1994).

This chapter is organized as follows. First we discuss the theoretical problems raised by silhouette-based image understanding. In particular, we present and develop the concept of the visual hull of an object, which allows questions such as whether the 3D shape of an object be fully understood from its silhouettes to be answered. We will see that this geometric entity allows this and other basic questions related to the silhouettes approach to be answered. It will be shown that the visual hull and the aspect graph of an object are strictly related. The computation of the visual hull will be discussed for polyhedra, object of revolution, and smooth surface objects. In general, VI supplies an object that is not coincident with the object to reconstruct: the problem of inferring the real shape from the object reconstructed will be also discussed, introducing the concepts of hard and soft points. Based on these concepts, we will show how an interactive reconstruction approach can be outlined. Finally we will deal with the problem of reconstructing an object when we have its silhouettes, but no information about the relative positioning of the corresponding viewplanes.

The last part of the chapter is devoted to survey practical shape from silhouettes algorithms.

II THE VISUAL HULL

Reconstructing as well as recognizing 3D objects using silhouettes requires facing some problems inherent to the approach. An intuitive analysis of some examples will help focus the problems raised by this technique. Let us consider the concave objects O1 and O2 in Figure 5. The difference between them consists of a small cube inside the concavity. It is not difficult to intuitively realize that this cube does not affect any of the silhouettes of the object, provided that the corresponding viewpoint is not “too close” to the object (a precise formulation of this statement will be given later). The example shows that we might not be able to distinguish different concave objects using their silhouettes.

Let us consider now the reconstruction from silhouettes of O1 and O2. Since the silhouettes relative to not “too close” viewpoints are equal for the two objects, we cannot exactly reconstruct either O1 or O2. On the contrary,...