Comments on “Efficiently computing and representing aspectgraphs of polyhedral objects”

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     

The visual hull concept for silhouette-based image understanding

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     

Tables for Butterworth-digital-filter design

A method for constructing tables for digital-filter design is described. Filters whose transfer functions are similar to those of Butterworth analogue filters are considered.     

The visual hull of smooth curved objects

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.     

A nearly optimal sensor placement algorithm for boundary coverage

Locating visual sensors in 2D can be often modeled 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”. For other tasks, such as inspection and image based rendering, observing the boundaries of the environment is sufficient. As Interior Covering (IC), also Edge Covering (EC) is NP-hard, and no finite algorithm is known for its exact solution. Approximate EC solutions are provided by many heuristic algorithms, but their performances with respect to optimality (minimum number of sensors) is unknown. In this paper, we propose a new EC sensors location technique. The algorithm is incremental, and converges toward the optimal solution. It refines an initial approximation provided by an integer covering algorithm (IEC) 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 at each step for evaluating the quality of the current solution, and a set of rules are provided for performing a local refinement to reduce the computational burden. The algorithm has been implemented, and tests over hundreds of random polygons show that it supplies solutions very close to and often coincident with the lower bound, and then suboptimal or optimal. In addition, the approximate starting solutions provided by the IEC algorithms are, on the average, close to optimum. The tight lower bound can also be used for testing other EC sensor location algorithms. Running times allow dealing with polygons with up to a few hundreds of edges, which appears adequate for many practical cases. An enhanced version of the algorithm, also taking into account range and incidence constraints, has also been implemented and tested.     

On the number of zones in which the hyperspace is divided byN hyperplanes

In this note an upper bound is given to the number of zones in which ad dimensional hyperspace is divided byN hyperplanes.     

Counterexample to a conjecture in multiprocessor scheduling

A counterexample to a conjecture on an upper bound to the execution time of a graph of tasks by the longest-path scheduling algorithm is presented.     

A nearly optimal algorithm for covering the interior of an Art Gallery

The problem of locating visual sensors can be often modelled as 2D Art Gallery problems. In particular, tasks such as surveillance require observing the interior of a polygonal environment (interior covering, IC), while for inspection or image based rendering observing the boundary (edge covering, EC) is sufficient. Both problems are NP-hard, and no technique is known for transforming one problem into the other. Recently, an incremental algorithm for EC has been proposed, and its near-optimality has been demonstrated experimentally. In this paper we show that, with some modification, the algorithm is nearly optimal also for IC. The algorithm has been implemented and tested over several hundreds of random polygons with and without holes. The cardinality of the solutions provided is very near to, or coincident with, a polygon specific lower bound, and then suboptimal or optimal. In addition, our algorithm has been compared, for all the test polygons, with recent heuristic sensor location algorithms. In all cases, the cardinality of the set of guards provided by our algorithm was less than or equal to that of the set computed by the other algorithms. An enhanced version of the algorithm, also taking into account range and incidence constraints, has also been implemented.     

Introducing a new problem: shape-from-silhouette when the relative positions of the viewpoints is unknown

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.     

What's NEXT? An interactive next best view approach

Shape-from-silhouettes algorithms use either a surface or a volumetric approach. A problem with the volumetric approach is that in general we know neither the accuracy of the reconstruction, nor where to locate new viewpoints for improving the accuracy. In this paper we present a general approach to interactive, object-specific volumetric algorithms, based on a necessary condition for the best possible reconstruction to have been performed. The outlined approach can be applied to any class of objects. As an example of this approach, an interactive algorithm has been implemented for convex polyhedra.