An algorithm for constructing the aspect graph
- 1 October 1986
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 123-131
- https://doi.org/10.1109/sfcs.1986.4
Abstract
In this paper we present tight bounds on the maximum size of aspect graphs and give worstcase optimal algorithms for their construction, first in the convex case and then in the general case. In particular, we give upper and lower bounds on the maximum size (including vertex labels) of Θ(n3) and Θ(n5) and algorithms for constructing the aspect graph which run in time O(n3) and O(n5) for the convex and general cases respectively. The algorithm for the general case makes use of a new 3D object representation called the aspect representation or asp. We also show a different way to label the aspect graph in order to save a factor of n in the asymptotic size (at the expense of label retrieval time) in both the convex and general cases, and we suggest alternatives to the aspect graph which require less space and store more information.Keywords
This publication has 4 references indexed in Scilit:
- From solid model to robot visionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- 3-D multiview object representations for model-based object recognitionPattern Recognition, 1986
- Characteristic Views As A Basis For Three-Dimensional Object RecognitionPublished by SPIE-Intl Soc Optical Eng ,1982
- The internal representation of solid shape with respect to visionBiological Cybernetics, 1979