le 
IS 
je 
th 
1e 
d 
al 
1S 
ro 
of 
I, 
nt 
(S 
ASPECT GRAPHS: STATE-OF-THE-ART AND APPLICATIONS 
IN DIGITAL PHOTOGRAMMETRY* 
David W. Eggert and Kevin W. Bowyer 
Department of Computer Science and Engineering 
University of South Florida 
Tampa, Florida 33620 USA 
eggertd or kwb@csee.usf.edu 
ISPRS Commission V 
Charles R. Dyer 
Department of Computer Science 
University of Wisconsin 
Madison, Wisconsin 53706 USA 
dyer@cs.wisc.edu 
ISPRS Commission V 
The study of the viewer-centered object representation known as the aspect graph has recently been an active area of research 
in computer vision. The aspect graph is desirable because it provides a complete enumeration of all possible distinct views of 
an object, given a particular model for viewpoint space and a definition of “distinct”. This paper presents a history of the 
evolution of the aspect graph, culminating with the current state of the art in algorithms and implementations for automatically 
constructing an aspect graph. The use of the aspect graph in possible applications in computer vision and computer graphics 
is described. Finally, current limitations of the representation are discussed and a potential solution involving the scale space 
concept is presented. 
Key Words: Computer Vision, Computer Graphics, Viewer-centered Representation, Aspect Graph, Survey, Scale Space. 
1. INTRODUCTION 
The origin of the aspect graph concept"" has several inde- 
pendent roots. It is most often credited to Koenderink and 
van Doorn (Koenderink and Van Doorn, 1976, 1979) who 
initially referred to it as the visual potential of an object. 
Somewhat earlier, Minsky described a concept very similar 
to the aspect graph (Minsky, 1975), sketching an example 
in terms of a frame system that depicted the different visual 
possibilities for a cube. Somewhat later, Chakravarty and 
Freeman (Chakravarty and Freeman, 1982) employed a sim- 
ilar concept, under the term characteristic views, in a study 
involving recognition of polyhedra. Since then, several other 
viewer-centered representations similar to the aspect graph 
have also been proposed. 
Each of these authors recognized the potential value of a 
representation that summarizes all of the possible distinct 
views of an object. Also, researchers in the fields of computer 
vision (Rosenfeld, 1987) and psychophysics (Palmer, Rosch 
and Chase, 1981; Perrett, et al., 1989) have been gathering 
evidence that humans may use a set of “important” aspects 
to achieve fast recognition of unknown objects, although it 
is unclear whether a human’s definition of “aspect” and “im- 
portant” coincide with what will be described here. 
Unfortunately, none of the first researchers was able to de- 
scribe an algorithm to automatically compute such a repre- 
sentation for any specific class of objects. As stated by Koen- 
derink and van Doorn, “A general decomposition of F3 — B 
  
* This work was supported at the University of South Florida by Air 
Force Office of Scientific Research grant AFOSR-89-0036, National Sci- 
ence Foundation grant IRI-8817776 and a grant from the Florida High 
Technology and Industry Council, and at the University of Wisconsin 
by National Science Foundation grant IRI-8802436 and the University 
of Wisconsin Graduate School. 
** In this paper, the term aspect graph will refer generally to rep- 
resentations that have also been called characteristic views, principal 
views, stable views, viewing data, view classes and other similar terms. 
(B refers to the space occupied by a solid object) into cells 
that provide a stable global aspect of 6B is by no means triv- 
ial to carry out.” (Koenderink and van Doorn, 1976, page 
57). This simple fact delayed research on aspect graphs for 
several years. However, now due to intensive research in re- 
cent years there exist a number of different algorithms and 
even implementations to produce this representation. 
The remainder of this paper is organized as follows. Sec- 
tion 2 presents a more rigorous and detailed definition of 
the aspect graph. Section 3 describes the approach used in 
computing an approximate aspect graph. Sections 4 and 5 
outline the considerations involved and subsequent results 
in computing the exact aspect graph of polyhedral objects 
and curved objects, respectively. Section 6 discusses a gen- 
eralization of the aspect graph concept for objects having 
articulated connections between rigid parts. Section 7 de- 
scribes some of the possible applications for aspect graphs 
in both computer vision and computer graphics. In Section 
8 some possible deficiencies in the current conception of the 
aspect graph representation are mentioned, and a potential 
solution, the scale space aspect graph, is presented. Finally, 
Section 9 briefly presents some topics of continuing research. 
2. DEFINING THE ASPECT GRAPH 
The commonly agreed upon elements of the definition of an 
aspect graph representation are generally that: 
e there is a node for each general view of the object as 
seen from some maximal connected cell of viewpoint 
space, and 
e there is an arc for each possible transition, called a 
visual event, between two neighboring general views. 
The not so commonly agreed upon elements, needed to com- 
plete this definition, are the model of viewpoint space, and 
what is meant by a general view. These and other factors 
discussed in the next sections can be used to classify the 
various algorithms developed to date, as shown in Figure 1.