TECHNICAL REPORT ARCHIVE


A Survey of Aspect Graphs

TR-CIS-2001-01
Robert D. Schiffenbauer

pdf version of this paper

Abstract:
Aspect graphs are data structures that incorporate information about the views of an object or collection of objects in a given scene. They are useful, for example, in object classification, where the identity of an unknown object is established by comparing an available subset of its views with the views of a series of known objects and ascertaining the closest match (roughly, a 'view' is the line drawing resulting from the projection of object features visible from a given viewpoint onto a two-dimensional surface). This paper surveys the recent literature on aspect graph research with emphasis on results pertaining to polyhedral scenes. The complexity of the aspect graph induced by such scenes under various circumstances is analyzed. Algorithms for computing the aspect graph in various cases are investigated and their complexities compared. The theory of arrangements of hypersurfaces in multi-dimensional spaces plays an important role in this analysis. A particularly large body of results has been established for aspect graphs induced by polyhedral terrains, drawing extensively on the theory of Davenport-Schinzel sequences and the more general theory of envelopes of graphs of multivariate functions in higher-dimensional spaces. The survey concludes with an examination of several approximations, alternatives and extensions to the aspect graph concept.

Back to previous page