Extended Gaussian images, mixed volumes, shape reconstruction

ABSTRACT

The Extended Gaussian Image (EGI) of an object records the variation of surface area with surface orientation. The EGI is a unique representation for convex objects. For a polyhedron, each face is represented by its normal and its area. The inversion problem (from an EGI to a description in terms of vertices and faces) is solved for convex polyhedra, by providing an algorithm giving an iterative solution by a minimization[Little,1983]. The algorithm employs a geometric construction, the mixed volume, which was used in Minkowski's proof [1897] of the existence and uniqueness of an inverse. The mixed volume measures similarity of shape for convex objects.

REFERENCES

• 1: [1] H.H. Baker and T.O. Binford, "Depth From Edge and Intensity Based Stereo," Proceedings of the Seventh IJCAI, pp. 631-636, Vancouver, 1981.
• 2: [2] P. Brou, "Finding Objects in Depth Maps", Robotics Research, Winter 1984.
• 3: [3] K.Q. Brown, "Fast Intersection of Half Spaces", CMU Technical Report CMU-CS-78-129, 1978.
• 4: [4] P. E. Gill, W. Murray, and M.H. Wright, "Practical Optimization", Academic Press, New York, New York, 1981.
• 5: Eric L. W. Grimson, From Images to Surfaces: A Computational Study of the Human Early Visual System, MIT Press, Cambridge, MA, 1981
• 6: [6] B. Grünbaum, "Convex Polytopes", John Wiley and Sons, Ltd. London and New York, 1967.
• 7: [7] L. Guibas, L. Ramshaw, and J. Stolfi, "A Kinetic Framework for Computational Geometry", Proc. of the 24th Annual IEEE Symposium on Foundations of Computer Science, 1983.
• 8: [8] B. K. P. Horn, "Extended Gaussian Images", Proceedings of the IEEE, pp. 1671-1686, December, 1984.
• 9: [9] K. I. Ikeuchi, "Recognition of 3-D Objects Using the Extended Gaussian Image", Proceedings of the Seventh IJCAI, pp. 595-600, 1981.
• 10: [10] K.I. Ikeuchi, B. K. P. Horn, S. Nagata, T. Callahan, and O. Feingold, "Picking up an object from a pile of objects", AI Memo 726, 1983.
• 11: [11] J.J. Little, "An Iterative Method for Reconstructing Convex Polyhedra from Extended Gaussian Image", Proceedings of AAAI-83, pp. 247-250, 1983.
• 12: [12] J.J. Little, "Determining Object Attitude from Extended Gaussian Images", submitted to IJCAI-85.
• 13: [13] L. A. Lyusternik, "Convex Figures and Polydedra", Dover Publications, New York, 1963.
• 14: [14] Herman Minkowski, "Allgemeine Lehrsatze uber die konvexe Polyeder," Nachr. Ges. Wiss. Gottingen, pp. 198-219, 1897.
• 15: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 16: F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
• 17: [17] R. Seidel, "A Method for Proving Lower Bounds for Certain Geometric Problems", TR 84-592, Feb. 1984.
• 18: [18] D. A. Smith, "Using Enhanced Spherical Imagea", MIT AI Memo 530, May, 1979.
• 19: [19] E. Steinitz, "Polyeder und Raumein teilungen", Enzykl. Math. Wiss. Vol. 3, (Geometrie) Part 3AB12, pp. 1-139, 1922.
• 20: [20] W. T. Tutte, "A Census of Planar Triangulations", Canadian Journal of Math., vol. 14, pp. 21-38, 1962.
• 21: [21] R.J. Woodham, "Photometric Method for Determining Surface Orientation from Multiple Images", Optical Engineering, vol. 19, pp. 139-144, 1980.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Shape
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Shape

General Terms:
Design, Measurement, Theory