• Introduction
• Demo
  
  

1. Introduction

Reconstructing 3-D shapes from 2-D images is a basic research area in computer vision. Many algorithms are based on occluding contours or silhouettes. In the latter case, only the contours which occlude the background are considered. Reconstruction from silhouettes is as reconstruction from shadows cast from the object with point light sources located at the viewpoints.

The information provided by set of silhouettes and viewpoints is summarized by the volume R shared by the solid regions of space C_i within which each silhouette S_i constrains the unknown object O to lie (Fig.1). R approximates O more or less closely, depending on the viewpoints and the shape of O itself. Finding this volume is a popular reconstruction called volume intersection (VI).



The Volume Intersection approach.

Figure 1

Silhouette-based reconstruction algorithms must face an important problem. If no a priori information about the 3-D shape is available, we have no idea of the accuracy of the reconstruction obtained, and consequently we do not know whether halting or not the reconstruction process. It is also clear that, for a given object, each new VI operation can refine the reconstruction to different degrees, depending on the viewpoint chosen. So another problem is where to locate new viewpoints. If we were given the shape of the object, in principle we could construct some object specific algorithm for finding the next best viewpoint, but the shape is the very information we are looking for. So in general we are reduced to a simple "the more silhouettes the better" strategy.

The purpose of this work is to demonstrate a quantitative approach able to solve, at least in part, this apparently under-constrained problem. This approach is based on a necessary condition for the reconstruction obtained to be optimal. This condition can be verified considering the reconstructed object R only, without any a priori knowledge about O. We will also show that, when this necessary condition is not satisfied, we can compute a measure of the current reconstruction accuracy, and derive suggestions for locating a new viewpoint.

Here we will demonstrate our active approach for polyhedral objects in a virtual environment.

2. Visual hull, hard and soft points

The visual hull VH(O,V) of an object O relative to a viewing region V is the closest approximation of O which can be obtained by VI with viewpoints belonging to V. It is also the largest object that produces the same silhouettes as O from viewpoints belonging to V. All the visual hulls relative to viewing regions which:

1. completely enclose O;
2. do not share any point with the convex hull of O;

are equal. This is called the external visual hull of O, or simply the visual hull VH(O).

Three objects and their visual hulls are shown in Fig.2. In the figure, P is a curved ruled patch due to lines tangent at the edges E_1, E₂, E₃. An intuitive physical construction of the visual hull is shown for the third object. Suppose filling the concavity with soft material. The visual hull can be obtained by scraping off the excess material with a ruler grazing the hard surface of the object in all possible ways.

Some objects and their visual hulls

Figure 2

The points of the surface of R can be divided into: hard points, which belong to any possible object originating R; soft points, which could belong or not to O. In other words, hard points are guaranteed to belong to (the surface of) O.

The problem of computing the hard points can be considered in two reconstruction cases.

Case 1 - In this case we assume that the optimal reconstruction has been performed, i.e. the visual hull of O has been obtained. This is the inverse problem of computing the visual hull of a given object. Let a hard point of a visual hull be a VH-hard point. A necessary and sufficient condition for a point to be VH-hard is the following:

Prop. 1. A point P is VH-hard iff there exists one straight line sharing only P with VH(O) .

This is a point condition, which requires further work for finding the hard parts of general surfaces. For the case of polyhedral visual hulls however an algorithm has been presented [Laure95], which allows to find in polynomial time the hard edges of the object (the internal points of planar faces are always soft).

Examples of VH-hard points are shown in Fig.3. The four leftmost objects of each row have the same visual hull (the first object of the row), and share its hard edges, marked thick in the rightmost objects.

Examples of VH-hard edges.

Figure 3

Case 2 - Let us assume that we do not know whether the reconstruction is optimal or not. Obviously, this is the situation to face usually. Let call R-hard a hard point in this case.

A necessary and sufficient condition exists for a point to be R-hard. Let the strip ST(O,V_i) relative to the viewpoint V_i and the object O be the part of surface (let it be a visual cone) of the solid cone C_i starting at V which bounds R, or, in other words the part of the visual cone which is left after the VI operations due to the other silhouettes. Also let the width of a strip ST(O,V_i) at a point P be the length of the segment of the half-line starting at V_i and passing through P which lies on the strip. The following statement holds:

This is a constructive condition. The R-hard points can be obtained as a by-product of the VI algorithm. In practice, we can find R-hard points or, at most, R-hard lines ( R-hard surface would require an infinite number of silhouettes). The idea of R-hard points is demonstrated in Fig.4. Two ideal viewing directions, V₁ and V₂, shown together with the corresponding strips, are insufficient to produce hard points, since both strips have everywhere non-zero width. One additional co-planar viewing direction V₃ supplies a couple of R-hard segments.

Examples of R-hard edges.

Figure 4

1. The interactive reconstruction approach

In this Section we state a necessary condition for the reconstruction to be optimal, and show that from this condition we can derive:

1. a measure of reconstruction accuracy
2. hints for selecting new viewpoints when the accuracy is not satisfactory

Suppose that we are given a set of viewpoints and silhouettes of an unknown object O, which produce the object R. Let VH(R) be the set of VH-hard points, and R(R) be the set of R-hard points.

In general it is VH(R)>R(R) (see for instance Fig.3 and Fig.4). In fact, by adding new silhouettes we cannot delete old hard points, but only add new hard points, and the visual hull is the reconstruction made with all possible silhouettes. If the best possible reconstruction has been obtained, that is R=VH(O), no more hard points can be found. It follows that:

Prop 3. A necessary condition for the reconstruction to be optimal is: VH(R)= R(R)

Let us define compatible a reconstruction which satisfies this condition, that is, such that all the points of R which could be hard have been found to be actually hard.

The condition is not sufficient for the reconstruction to be optimal, and in some cases small details of the object could remain undetected. However, the necessary condition stated is fruitful. In fact, not only it can tell us when to halt the VI process, but it also allows, if not satisfied, to understand how far we are from a compatible reconstruction. In addition, if we are not satisfied with the accuracy already obtained, it suggests the location of the next viewpoint.

Let us outline a general interactive reconstruction approach, which holds for any kind of object. First, let us introduce some figure of merit f(HPS,R) depending on a set HPS of hard points and the surface of R. This figure should be defined in relation with the category of objects considered. For instance, for smooth-surface object, where only hard points, and not hard lines, can be found, f could be the number of hard points per square inch, possibly corrected according to the local curvature.

For polyhedra, where both hard points and hard lines can be found, f could be defined as the total length of the hard lines, plus the number of hard points multiplied by some constant weight. Let the relative reconstruction accuracy RA be defined as:

RA = f ( R(R),R)/ f ( VH(R),R)

Clearly RA is one iff the reconstruction is compatible. An interactive reconstruction algorithm can be constructed as follows:

1. compute R, VH(R), R(R) and RA
2. if (1-RA) £e , where e is some predefined error , stop;
3. otherwise, refine the reconstruction by testing if the potentially hard points VH(R)-R(R) are actually hard or not. This can be done for a subset of the potentially hard points by selecting a viewpoint such that this subset is projected on the boundary of the silhouette of R.

Although this approach is quite general, to implement a general algorithm is not trivial. One reason is that it requires algorithms for computing VH(R) for any kind of object. Since one algorithm is available for polyhedra, we have implemented the interactive algorithm for these solids.

1. An interactive algorithm for polyhedra

In many cases, the visual hull of a polyhedron is a polyhedron in his turn. Obviously, this happens when the object is exactly reconstructable (O=VH(O)). Also if this is not the case, the surface of VH(O) could consist of planar patches only. In all these cases, we state as goal of the interactive algorithm to find a compatible reconstruction, where VH(R)=R(R) so that the reconstruction accuracy is one.

In some cases however, the surface of VH(O) includes curved ruled patches, as shown in Fig. 2. For simplicity, we will not deal with this cases. The algorithm, implemented for virtual polyhedra, consists of four parts:

1. ALGVI, which performs the volume intersection;
2. ALGVH, the algorithm for computing the hard points VH(R);
3. ALGR, the algorithm for computing the hard points R(R);
4. NEXT, which compares VH(R) and R(R) and, if the sets are not equal, computes the next viewpoint;

In the following we will present NEXT, which uses two different sets of rules for convex and non convex polyhedra, and the experimental results obtained.

In this case running ALGVH is not necessary, since any reconstructed object R is convex, and thus all the edges are VH-hard. Therefore, NEXT computes new viewpoints until all the edges of R are R-hard.

Strategy. Start with three random viewpoints. Until there are candidate edges, chose a new viewpoint such that at least one candidate edge E is on the boundary of the silhouette of the current R. According to the type of the faces F₁ and F₂ of R converging into E, it could be necessary for the viewpoint to satisfy some further condition.

Three cases for the candidate edge E

Figure 5

Case 1 - There are no hard edges lying on F₁ and F₂. In other words, the edges of O which produce F₁ and F₂ have not yet been detected (see Fig. 5a, where the undetected edges are shown as dotted lines). In this case, any viewpoint seeing E on the boundary of the silhouette is fit. In fact, it will either verify E as a hard edge, or produce a new face of R making contact with at least one edge yet undiscovered, inside the solid angle formed by F₁ and F₂.

Case 2 - There is one R-hard edge on both F₁ and F₂(see Fig. 5b, where the hard edges are thick segments). A viewpoint lying on a line passing through one point of both the hard edges will either verify a possible undetected face, or produce one or more faces making contact with undetected edges.

Case 3 - There is one R-hard edge on one face, let it be F₁ (see Fig. 5c). Consider a line starting at V₂ ( the viewpoint which produces F₂) and lying on F₂. This line will intersect F₂ at two points. Let P by the point closer to V₂. Chose a new viewpoint on a line passing trough P and one point of the R-hard edge on F₁. It is clear from the figure that it will produce a new face making contact with one or more undetected edges (possibly E₂).

A number of rules can be applied for speeding up the algorithm. For instance, if two R-hard vertices joined by a candidate edge have been found, the edge can be classified as hard, even if it does not belongs to a strip of zero width .

It is also clear that the general strategy described allows to position the viewpoints in several different positions. To restrict the choices, some heuristics can be used.

An example of reconstruction of a convex polyhedron

Figure 6

The algorithm NEXT actually implemented for convex polyhedra uses several heuristics which we will omit for brevity. An example of the steps performed by the algorithm is shown in Fig.6, where the arrows indicate the viewpoints and the hard edges are thicker. The algorithm has been applied to fifty randomly generated convex polyhedra. Some of them are shown in Fig.7.

A subset of the fifty convex polyhedra reconstructed

Figure 7

The average numbers of vertices, edges and faces of the fifty polyhedra are 17.8, 26.7 and 10.9 respectively. We have found that the average number of silhouettes required for the reconstruction is 13.

To reconstruct the visual hull of concave polyhedra is much more difficult. We have already recalled that there are curved visual hulls, which in principle require an infinite number of polygonal silhouettes. Even polyhedra with polyhedral visual hull could require an unbounded number of silhouettes for their reconstruction [Laure97].

Both these cases could be approached with approximations which neglect small details. Anyway, to develop an algorithm working for any concave polygons is outside the scope of this work.

The algorithm we have implemented has been able to reconstruct concave polyhedra such that:

1. the hard edges lies all on the convex hull
2. the concave parts of the visual hull can be reconstructed with a bounded number of intersections.

In more details, the algorithm first reconstructs the visual hull of the convex parts and the rim (always on the convex hull) of the concavities. In a second step it attempts to reconstruct the concavities.

In Fig. 8 we show an example of reconstruction of a concavity. In this case, the complete reconstruction of the visual hull required 16 silhouettes.

The reconstruction of a concavity

Figure 8

The algorithm has been applied for reconstructing the visual hull of several other concave polyhedra. In Fig. 9 we show some polyhedra coincident with their visual hulls and thus, in principle, exactly reconstructable. Our algorithm was able to reconstruct objects (a),(b), (d) and (e) with 16, 19, 43, 19 silhouettes respectively. The concavity of object (c) requires an infinite number of silhouettes. However, its hard edges, including the rim of the concavity, have been determined with 25 volume intersections.

In Fig. 10 we show several polyhedra ((a)-(e)) not coincident with their visual hulls. In this case, the reconstruction of the visual hulls (a’), (b’), (c’), (e’) required 16, 40, 15, 15 silhouettes respectively. To reconstruct completely the visual hull (d’) requires infinite steps, but its hard edges and the faces lying on the convex hull took 15 intersections.

Concave polyhedra coincident with their visual hull

Figure 9

Polyhedra not coincident with their visual hulls

Figure 10

• Usage of the demo program (1.5M avi)

• Reconstruction of a convex object (900K avi)
• Reconstruction of a concave object (1.1M avi)

To see the avi files it is necessary to install the DivX ;-) MPEG4 Video Codec (downloadable from http://divx.ctw.cc)