Generating Octrees from Object Silhouettes in Orthographic Views

Narendra Ahuja, Jack Veenstra

Research output: Contribution to journalArticle

Abstract

Octrees are used in many 3-D representation problems because they provide a compact data structure, allow rapid access to occupancy information, and implement many geometric manipulation algorithms efficiently. The initial acquisition of the 3-D information, however, is a common problem. This paper describes an algorithm to construct the octree representation of a 3-D object from silhouette images of the object. The images must be obtained from any subset of thirteen viewing directions corresponding to the three “face” views, six “edge” views, and four “corner” views of an upright cube. These views were chosen because they provide a simple relationship between pixels in the image and the octant labels in the octree, thus replacing the computation of detecting intersections between the octree space and the objects by a table lookup operation. The average ratio of the object volume to the octree volume is found to be greater than 90 percent. The sequential use made of the chosen viewing directions results in a coarse-to-fine acquisition of occupancy information. The number and order of the viewpoints used provides a mechanism for trading accuracy of the representation against the computational effort needed to obtain the representation.

Original languageEnglish (US)
Pages (from-to)137-149
Number of pages13
JournalIEEE transactions on pattern analysis and machine intelligence
Volume11
Issue number2
DOIs
StatePublished - Feb 1989

    Fingerprint

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics

Cite this