Viewer centered representations for polyhedral objects: computing the exact perspective projection aspect graph of an object bounded by planar faces
John H. Stewman · 1992
The aspect graph concept has received considerable attention in computer vision in recent years. There are two principal reasons why this representation is considered to be important for computer vision: (1) aspect graphs describe objects in terms of their 2-D image appearance, and (2) aspects differ from each other in significant, qualitative ways, so the aspect graph captures some measure of the inherent visual complexity of the object. A number of researchers have investigated algorithms for automatically constructing aspect graphs of objects in different classes. Some approaches are approximate and others are exact. Many assume a 2-D space of viewing directions rather than a 3-D space of viewpoints, and often the imaging process is approximated by orthographic rather than perspective projection. The principal focus of this dissertation is the development of an algorithm for automated construction of aspect graphs of polyhedral Euler objects. It is assumed that (1) a polyhedral boundary representation of the object is available as input, (2) the imaging process is described by perspective projection, (3) the viewpoint space is all 3-D space not occupied by the object, and (4) the aspect graph is based on an explicit representation of the parcellation of the viewpoint space. The algorithm presented is the first to solve the problem under these conditions. The algorithm has three basic steps: (1) identify all visual event surfaces separating aspects, (2) determine the parcellation of viewpoint space resulting from the arrangement of visual event surfaces, and (3) construct the aspect graph, creating a node for every cell in the parcellation and an arc for every 2-D connection between cells. This algorithm has been implemented in C. It creates the aspect graph, saves it to disk, and permits reconstruction of the description from disk and access to (display of) the various aspects of the object. The main contributions of this research are (1) an algorithm which automatically creates the aspect graph of a polyhedral Euler object based on an exact parcellation of the complete 3-D viewpoint space, (2) an implementation of the algorithm and a summary of aspect graph details for a representative set of objects, (3) a detailed analysis of the maximum numbers of visual event surfaces involved and the maximum sizes of the aspect graphs produced for various subclasses of the polyhedral object domain, and (4) an explanation of the occurrence of nonconvex cells of viewpoint space. In addition, a set of equivalence relations, based on aspect characteristics and cell geometry, and a ranking measure, based on cell size and frequency of aspect appearance, are proposed for use in arranging and accessing a database of object aspects.