The asp: a continuous, viewer-centered object representation for computer vision

摘要

In this thesis a new continuous, viewer-centered representation for polyhedral objects or scenes is introduced, called the aspect representation or asp. The asp is viewer-centered in the sense that it represents the appearance of a polyhedron to a viewer as a two-dimensional line drawing, rather than the volume of space that it fills. It is continuous in the sense that it represents appearance for all viewpoints rather than for a discrete set of viewpoints. In effect, it is a representation of appearance as a function of viewpoint. Analyses of the size of asps and algorithms for their construction are given under orthographic and perspective viewing models, for convex and non-convex polyhedra. The worst-case size of an asp is Θ(n) in the convex case and Θ(n4) in the non-convex case. The asp is the first representation of appearance as a function of viewpoint. As such it is useful for problems that depend on knowing the appearance of an object from many viewpoints, finding ranges of viewpoints with particular characteristics of appearance, and determining viewpoints at which particular visual events happen. Many problems in computer vision and graphics fall into one of these categories. In general, the asp is useful for problems that make repeated use of appearance characteristics, justifying the representation of all visual events. In this thesis the asp is applied to three problems, in each case yielding improvements or advantages over previous results. The first problem is the construction of the aspect graph, a graph defined to have a vertex for each topologically-distinct view of a polyhedron and edges connecting adjacent views. Using the asp, we present the first algorithm for constructing the aspect graph for general polyhedra. The second application is object recognition. In this application we show how to use the asp to represent and use occlusion information in recognizing three-dimensional objects from an arbitrary viewpoint. The third application is animating rotation, or showing views of a polyhedral scene from many closely-spaced viewpoints fast enough to give the appearance of the scene as the viewer moves around it. Chapter 1: Representation and Appearance 1-1. Representation for Problem Solving Any system that seeks to solve a problem must represent the problem to be solved; representation of some aspect of the world is one of the most basic requirements of a problem-solving system. Reasoning systems require a representation of knowledge and beliefs; natural language understanding systems require a representation of language and meaning; robot motion planning systems require a representation of location and shape of objects in the world. A particular representation may be more or less helpful in the solution of a problem. Choosing an advantageous representation is often a key to finding an efficient solution because an advantageous representation makes explicit the information pertinent to the solution. For example, given two equivalent knowledge databases, one may yield a proof of a theorem much more quickly than the other if it includes key lemmas. Problems in computer vision, computer graphics, CAD/CAM, robotics, and many other areas require a representation of objects in the world. Thus, it is not surprising that there are many different object representations in use with different advantages and disadvantages. Major existing three-dimensional (3-D) object representations can be divided into three main categories: volumetric, boundary, and swept-volume representations. Volumetric representations, such as octrees [Jackins & Tanimoto, 1980], space occupancy arrays [March & Steadman, 1974], [Srihari, 1981], and constructive solid geometry [Requicha, 1978], represent the volume of space that an object occupies by constructing the volume as a combination of simpler volumes. Boundary representations such as winged-edge polyhedra [Baumgart, 1972] represent the boundary of the volume. Swept-volume representations r