Locating sensors in 2D can be often modelled as an Art Gallery problem. Tasks such as surveillance require observing or "covering" the interior of a polygon with a minimum number of sensors or "guards". Observing the boundaries of a polygonal environment is sufficient for tasks such as inspection and image based rendering. As interior covering, also Edge Covering (EC) is NP-hard, and no finite algorithm is known for its exact solution. A number of heuristics have been proposed for the approximate solution of this important problem, but their performances with respect to optimality is unknown. Therefore, a polygon specific tight lower bound for the number of sensors is very useful for assessing the performances of these algorithms. In this paper, we propose a new lower bound for the EC problem. It can be computed in reasonable time for environments with up to a few hundreds of edges. To evaluate its closeness to optimality, we compare it with a previously developed lower bound and with the solution provided by a recent incremental EC algorithm. Tests over hundreds of polygons with different number of edges show that the new lower bound is tight and outperforms the previous one.

Several problems in computer vision require locating multiple sensors. In some cases the problem, which is in general three-dimensional, can be reduced to 2D. This problem can be modeled as an art gallery problem, which is NP-hard and no finite algorithm, even exponential, is known for its solution. Algorithms able to closely approximate the optimal solution and computationally feasible in the worst case are unlikely to exist. In this paper we propose a new sensor locating incremental algorithm. The technique converges toward the optimal solution. It locally refines a starting approximation provided by an integer covering algorithm, where each edge is observed entirely by at least one sensor. A lower bound for the number of sensors, specific of the polygon considered, is used for halting the algorithm, and a set of rules that allow to simplify the problem are presented

The visual hull summarizes the relations between an object and its silhouettes and shadows. This paper develops the theory of the visual hull of general piecewise smooth objects, as those used in CAD applications. A complete catalogue of the nine types of ruled surfaces that are possible boundaries of the visual hull of these objects is derived. The construction of the visual hull is simplified by a detailed analysis that allows pruning and trimming many surfaces not relevant for a particular object. An algorithm for computing the visual hull is presented, together with several examples constructed with a commercial CAD package. The theory developed includes as particular cases the previous approaches to the computation of the visual hull.

The visual hull is a geometric entity that relates the shape of an object to its silhouettes or shadows. This paper develops the theory of the visual hull of generic smooth objects. We show that the visual hull can be constructed using surfaces which partition the viewpoint space of the aspect graph of the object. The surfaces are those generated by the visual events tangent crossing and triple point. An analysis based on the shape of the object at the tangency points of these surfaces allows pruning away many surfaces and patches not relevant to the construction. An algorithm for computing the visual hull is outlined.

3D shapes can be reconstructed from 2D silhouettes by back-projecting them from the corresponding viewpoints and intersecting the resulting solid cones. However, in many practical cases as observing an aircraft or an asteroid, the positions of the viewpoints with respect to the object are not known. In these cases, the relative position of the solid cones is not known and the intersection cannot be performed. The purpose of this paper is introducing and stating in a theoretical framework the problem of understanding 3D shapes from silhouettes when the relative positions of the viewpoints are unknown. The results presented provide a first insight into the problem. In particular, the case of orthographic viewing directions parallel to the same plane is thoroughly discussed, and sets of inequalities are presented which allow determining objects compatible with the silhouettes.

The visual hull is a geometric tool which relates the 3D shape of a concave object to its silhouettes or shadows. This paper deals with the computation of the visual hull of objects bounded by smooth curved surfaces. We show that the surfaces which bound the visual hull are surfaces relevant for the construction of the aspect graph of the object, and that the algorithms for computing the aspect graph of curved objects can be exploited for computing their visual hull.

This correspondence is originated by the definition of aspect given in the above paper by Gigus-Canny-Seidel (ibid., vol.13, no.6 (1991)) on the computation of aspect graphs of polyhedra. Simple examples are presented which show that the data stored according to this definition can be unsuitable for identifying an object or its attitude through a topological match. A definition is suggested which does not incur the problems pointed out.

Each 2D silhouette of a 3D unknown object O constrains O inside the volume obtained by back-projecting the silhouette from the corresponding viewpoint. A set of silhouettes specifies a boundary volume R obtained by intersecting the volumes due to each silhouette. R more or less closely approximates O, depending on the viewpoints and the object itself. This approach to the reconstruction of 3D objects is usually referred to as volume intersection. This correspondence addresses the problem of inferring the shape of the unknown object O from the reconstructed object R. For doing this, the author divides the points of the surface of R into hard points, which belong to the surface of any possible object originating R, and soft points, which may or may not belong to O. The author considers two cases: In the first case R is the closest approximation of O which can be obtained from its silhouettes, i.e., its visual hull; in the second case, R is a generic reconstructed object. In both cases the author supplies necessary and sufficient conditions for a point to be hard and gives rules for computing the hard surfaces.>

Many algorithms for both identifying and reconstructing a 3-D object are based on the 2-D silhouettes of the object. In general, identifying a nonconvex object using a silhouette-based approach implies neglecting some features of its surface as identification clues. The same features cannot be reconstructed by volume intersection techniques using multiple silhouettes of the object. This paper addresses the problem of finding which parts of a nonconvex object are relevant for silhouette-based image understanding. For this purpose, the geometric concept of visual hull of a 3-D object is introduced. This is the closest approximation of object S that can be obtained with the volume intersection approach; it is the maximal object silhouette-equivalent to S, i.e., which can be substituted for S without affecting any silhouette. Only the parts of the surface of S that also lie on the surface of the visual hull can be reconstructed or identified using silhouette-based algorithms. The visual hull depends not only on the object but also on the region allowed to the viewpoint. Two main viewing regions result in the external and internal visual hull. In the former case the viewing region is related to the convex hull of S, in the latter it is bounded by S. The internal visual hull also admits an interpretation not related to silhouettes. Algorithms for computing visual hulls are presented and their complexity analyzed. In general, the visual hull of a 3-D planar face object turns out to be bounded by planar and curved patches.>

The volume intersection approach to the reconstruction of 3-D objects consists in intersecting the volumes obtained by back-projecting a number of silhouettes of an unknown object O. The problem of inferring, as far as possible, the shape of the unknown object O from the reconstructed object R is addressed. The points of the surface of R are divided into hard points, which belong to the surface of any possible object originating R, and soft points, which may or may not belong to O. Two cases are considered: in the first case R is the closest approximation of O which can be obtained with volume intersection techniques, i.e., its visual hull; in the second case, R is a generic reconstructed object. In both cases necessary and sufficient conditions are supplied for a point to be hard. Rules are given for computing the hard surfaces.>

The visual hull of a 3-D object is a new geometric tool for dealing with concave object recognition or reconstruction using silhouettes. Two equivalent definitions of the visual hull of an object S can be given: (i) the maximal object silhouette-equivalent to S (that gives the same silhouettes as S); (ii) the closest approximation of S that can be obtained with volume intersection techniques. The paper addresses the problem of computing the visual hull of solids of revolution. An algorithm for this purpose is presented and its complexity analyzed. The algorithm operates in an axial plane of S dissected by straight lines and hyperbolae.>