Article

Free access

Extended Gaussian images, mixed volumes, shape reconstruction

Author:

James J. LittleAuthors Info & Claims

SCG '85: Proceedings of the first annual symposium on Computational geometry

Pages 15 - 23

https://doi.org/10.1145/323233.323236

Published: 01 June 1985 Publication History

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]

{5} W.E.L. Grimson, "From Images to Surfaces: A Computational Study of the Human Early-Visual System", MIT Press, Cambridge, Mass, 1981.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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]

{15} C.H. Papadimitriou and K. Steiglitz, "Combinatorial Optimization: Algorithms and Complexity", Prentice Hall, Englewood Cliffs, NJ, 1982.

Digital Library

[16]

{16} F. P. Preparata and S.J. Hong, "Convex Hulls of Finite Sets of Points in Two and Three Dimensions", CACM, vol. 20, pp. 87-93, 1977.

Digital Library

[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.

Cited By

Adjigble MTamadazte Bde Farias CStolkin RMarturi N(2023)3D Spectral Domain Registration-Based Visual Servoing2023 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA48891.2023.10160430(769-775)Online publication date: 29-May-2023
https://doi.org/10.1109/ICRA48891.2023.10160430
Friedman AFrueh C(2022)Observability of Light Curve Inversion for Shape and Feature Determination Exemplified by a Case AnalysisThe Journal of the Astronautical Sciences10.1007/s40295-021-00293-w69:2(537-569)Online publication date: 24-Feb-2022
https://doi.org/10.1007/s40295-021-00293-w
Adjigble Mde Farias CStolkin RMarturi N(2021)SpectGRASP: Robotic Grasping by Spectral Correlation2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS51168.2021.9636235(3987-3994)Online publication date: 27-Sep-2021
https://doi.org/10.1109/IROS51168.2021.9636235
Show More Cited By

Index Terms

Extended Gaussian images, mixed volumes, shape reconstruction

Recommendations

An iterative method for reconstructing convex polyhedra from extended gaussian images
AAAI'83: Proceedings of the Third AAAI Conference on Artificial Intelligence

In computing a scene description from an image, a useful intermediate representation of a scene object is given by the orientation and area of the constituent surface facets, termed the Extended Gaussian Image (EGI) of the object. The EGI of a convex ...
Recovering Shape \& Determining Attitude from Extended Gaussian Images
Recovering shape and determining attitude from extended gaussian images

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '85: Proceedings of the first annual symposium on Computational geometry

June 1985

322 pages

ISBN:0897911636

DOI:10.1145/323233

Chairman:
Joseph O'Rourke
Johns Hopkins Univ., Baltimore, MD

Copyright © 1985 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1985

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCG85

Sponsor:

SCG85: The 1st Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry 1985

June 5 - 7, 1985

Maryland, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
575
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)7

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Adjigble MTamadazte Bde Farias CStolkin RMarturi N(2023)3D Spectral Domain Registration-Based Visual Servoing2023 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA48891.2023.10160430(769-775)Online publication date: 29-May-2023
https://doi.org/10.1109/ICRA48891.2023.10160430
Friedman AFrueh C(2022)Observability of Light Curve Inversion for Shape and Feature Determination Exemplified by a Case AnalysisThe Journal of the Astronautical Sciences10.1007/s40295-021-00293-w69:2(537-569)Online publication date: 24-Feb-2022
https://doi.org/10.1007/s40295-021-00293-w
Adjigble Mde Farias CStolkin RMarturi N(2021)SpectGRASP: Robotic Grasping by Spectral Correlation2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS51168.2021.9636235(3987-3994)Online publication date: 27-Sep-2021
https://doi.org/10.1109/IROS51168.2021.9636235
Fan SFrueh C(2019)A Direct Light Curve Inversion Scheme in the Presence of Measurement NoiseThe Journal of the Astronautical Sciences10.1007/s40295-019-00190-3Online publication date: 29-Aug-2019
https://doi.org/10.1007/s40295-019-00190-3
Abdallah HMérigot Q(2015)On the Reconstruction of Convex Sets from Random Normal MeasurementsDiscrete & Computational Geometry10.1007/s00454-015-9673-253:3(569-586)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s00454-015-9673-2
Abdallah HMérigot QCheng SDevillers O(2014)On the reconstruction of convex sets from random normal measurementsProceedings of the thirtieth annual symposium on Computational geometry10.1145/2582112.2582130(300-307)Online publication date: 8-Jun-2014
https://dl.acm.org/doi/10.1145/2582112.2582130
Li ZZhang YHou KLi H(2005)3D polar-radius invariant moments and structure moment invariantsProceedings of the First international conference on Advances in Natural Computation - Volume Part II10.1007/11539117_70(483-492)Online publication date: 27-Aug-2005
https://dl.acm.org/doi/10.1007/11539117_70
Alboul LEcheverria G(2005)Polyhedral gauss maps and curvature characterisation of triangle meshesProceedings of the 11th IMA international conference on Mathematics of Surfaces10.1007/11537908_2(14-33)Online publication date: 5-Sep-2005
https://dl.acm.org/doi/10.1007/11537908_2
Zouaki H(2003)Convex set symmetry measurement using Blaschke additionPattern Recognition10.1016/S0031-3203(02)00090-036:3(753-763)Online publication date: Mar-2003
https://doi.org/10.1016/S0031-3203(02)00090-0
Lamberg LKaasalainen M(2001)Numerical solution of the Minkowski problemJournal of Computational and Applied Mathematics10.1016/S0377-0427(01)00360-0137:2(213-227)Online publication date: Dec-2001
https://doi.org/10.1016/S0377-0427(01)00360-0
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents