An algorithm for constructing the aspect graph
William Harry Plantinga, Charles R. Dyer · Annual Symposium on Foundations of Computer Science · 1986
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.
Cited by 61 works. doi:10.1109/sfcs.1986.4
Authors
References
- The internal representation of solid shape with respect to vision
- Characteristic Views As A Basis For Three-Dimensional Object Recognition
- 3-D multiview object representations for model-based object recognition
- From solid model to robot vision
- Solid Modeling, Aspect Graphs, and Robot Vision
- The visual potential: One convex polygon
- Correspondence in line drawings of multiple views of objects