Skip to main content
SpringerLink
Log in

Computing exact aspect graphs of curved objects: Algebraic surfaces

  • Published:
International Journal of Computer Vision Aims and scope Submit manuscript

Abstract

This article presents an algorithm for computing the exact aspect graph of an opaque solid bounded by a smooth algebraic surface. Orthographic projection is assumed. The algorithm is based on a catalog of visual events available from singularity theory. It uses curve tracing, cell decomposition, homotopy continuation, and ray tracing to construct the regions of the view sphere delineated by visual-event curves. The algorithm has been fully implemented, and examples are presented.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Arnold, V.I. 1969. Singularities of smooth mappings,Russian Math. Surveys, pp. 3–44.

  • Arnold, V.I. 1983. Singularities of systems of rays,Russian Math. Surveys, 38(2): 87–176.

    Google Scholar 

  • Arnold, V.I. 1984.Catastrophe Theory. Springer-Verlag: Heidelberg.

    Google Scholar 

  • Arnon, D.S. 1983. Topologically reliable display of algebraic curves,Computer Graphics 17(3): 219–227.

    Google Scholar 

  • Arnon, D., Collins, G., and McCallum, S. 1984. Cylindrical algebraic decomposition I and II,SIAM J. Comput. 13(4): 865–889.

    Google Scholar 

  • Bajaj, C.L., Hoffman, C.M., Lynch, R.E., and Hopcroft, J.E.H. 1988. Tracing surface intersections,Comput. Aid. Geomet. Design 5:285–307.

    Google Scholar 

  • Binford, T.O. 1971. Visual perception by computer,Proc. Conf. Syst. Con., Miami.

  • Callahan, J. and Weiss, R. 1985. A model for describing surface shape,Proc. Conf. Comput. Vis. Patt. Recog., San Francisco, pp. 240–245.

  • Castore, G. 1984. Solid modeling, aspect graphs, and robot vision, In M.S., Pickett and J.W., Boyse, eds..Solid Modeling by Computer, pp. 277–292, Plenum Press: New York.

    Google Scholar 

  • Chakravarty, I. 1982. The use of characteristic views as a basis for recognition of three-dimensional objects. Image Processing Laboratory IPL-TR-034, Rensselaer Polytechnic Institute, October.

  • Chen, S. and Freeman, H. 1991. On the characteristic views of quadric-surfaced solids,Proc. IEEE Workshop on Directions in Automated CAD-Based Vision, pp. 34–43, June.

  • Collins, G.E. 1975. Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition, vol. 33,Lecture Notes in Computer Science. Springer-Verlag: New York.

    Google Scholar 

  • Demazure, M. 1989.Catastrophes et Bifurcations. Editions Ellipses.

  • do, Carmo, M.P., 1976.Differential Geometry of Curves and Surfaces. Prentice-Hall: Englewood Cliffs, N.J.

    Google Scholar 

  • Eggert, D. 1991.Aspect Graphs of Solids of Revolution. Ph.D. thesis, University of South Florida, December.

  • Eggert, D. and Bowyer, K. 1989. Computing the orthographic projection aspect graph of solids of revolution.Proc. IEEE Workshop on Interpretation of 3D Scenes, Austin, TX, November, pp. 102–108.

  • Eggert, D. and Bowyer, K. 1991. Perspective projection aspect graphs of solids of revolution: An implementation.Proc. IEEE Workshop on Directions in Automated CAD-Based Vision, June, pp. 44–53.

  • Eggert, D., Bowyer, K., Dyer, C., Christensen, H., and Goldgof, D. 1992. The scale space aspect graph.Proc. IEEE Conf. on Comp. Vision and Patt. Recog. To appear.

  • Farouki, R.T. 1986. The characterization of parametric surface sections.Comp. Vis. Graph. Image Proces. 33: 209–236.

    Google Scholar 

  • Faugeras, O.D. and Hebert, M. 1986. The representation recognition, and locating of 3-D objects,Intern. J. Robot. Res. 5(3): 27–52.

    Google Scholar 

  • Gigus, Z., Canny, J., and Seidel, R. 1991. Efficiently computing and representing aspect graphs of polyhedral objects,IEEE Trans. Patt. Anal. Mach. Intell. 13(6).

  • Gigus Z. and Malika J., Computing the aspect graph for line drawing of polyhedral objects.IEEE Trans. Patt. Mach. Intell. 12(2): 113–122.

  • Grimson, W.E.L. and Lozano-Perez, T. 1987. Localizing overlapping parts by searching the interpretation tree,IEEE Trans. Patt. Anal. Mach. Intell. 9(4): 469–482.

    Google Scholar 

  • Hebert, M. and Kanade, T., 1985. The 3D profile method for object recognition,Proc. IEEE Conf. Comput. Vis. Patt. Recog., San Francisco, June.

  • Huttenlocher, D.P. and Ullman, S. 1987. Object recognition using alignment,Proc. 1st Intern. Conf. Comput. Vis., London, June, pp. 102–111.

  • Ikeuchi, K. and Kanade, T. 1988. Automatic generation of object recognition programs.Proc. IEEE 76(8): 1016–35.

    Google Scholar 

  • Kajiya, J.T. 1982. Ray tracing parametric patches,Proc. SIGGRAPH 82, pp. 245–254, July.

  • Kergosien, Y.L. 1981. La famille des projections orthogonales d'une surface et ses singularités,C.R. Acad. Sc. Paris, 292: 929–932.

    Google Scholar 

  • Koenderink, J.J. 1984. What does the occluding contour tell us about solid state?Perception 13.

  • Koenderink, J.J. 1987. An internal representation for solid shape based on the topological properties of the apparent contour. In W., Richards and S., Ullman, eds.,Image Understanding: 1985–86, ch. 9, Ablex Publishing: Norwood, NJ, pp. 257–285.

    Google Scholar 

  • Koenderink, J.J. 1990.Solid Shape. MIT Press: Cambridge, MA.

    Google Scholar 

  • Koenderink, J.J. and Van, Doorn, A.J. 1979. The internal representation of solid shape with respect to vision,Biological Cybernetics 32: 211–216.

    Google Scholar 

  • Kriegman, D.J. and Ponce, J. 1990. Computing exact aspect graphs of curved objects: Solids of revolution,Intern. J. Comput. Vis. 5(2): 119–135.

    Google Scholar 

  • Kriegman, D.J. and Ponce, J. 1990. On recognizing and positioning curved 3D objects from image contours,IEEE Trans. Patt. Anal. Mach. Intell. 12(12): 1127–1137.

    Google Scholar 

  • Kriegman, D.J. and Ponce, J. 1991a. Geometric modelling for computer vision. InSPIE Conference on Curves and Surfaces in Computer Vision and Graphics II, Boston.

  • Kriegman, D.J. and Ponce, J. 1991b. A new curve tracing algorithm and some applications. In P.J., Laurent, A.Le, Méhauté, and L.L., Schumaker, eds.,Curves and Surfaces, Academic Press: New York, pp. 267–270.

    Google Scholar 

  • Kriegman, D., Vijayakumar, B., and Ponce, J. 1992. Constraints for recognizing and locating curved 3D objects from monocular image features,Proc. Europ. Conf. Comput. Vis.

  • Malik, J. 1987. Interpreting line drawings of curved objects,Intern. J. Comput. Vis. 1(1): 73–103.

    Google Scholar 

  • Manocha, D. and Canny, J. 1990. Algorithm for implicitizing rational parametric surfaces,IMA Conf. on Mathematics of Surfaces, Bath. (To appear inComputer Aided Geometric Design.)

  • Mather, J. 1968. Stability ofC ∞-mappings,Annals of Mathematics 87:89–104.

    Google Scholar 

  • Morgan, A. 1987.Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems. Prentice-Hall: Englewood Cliffs, NJ.

    Google Scholar 

  • Petitjean, S. 1992. Computing exact aspect graphs of curved objects bounded by smooth algebraic surfaces. Master's thesis, University of Illinois at Urbana-Champaign.

  • Plantinga, H. and Dyer, C. 1990. Visibility, occlusion, and the aspect graph,Intern. J. Comput. Vis. 5(2): 137–160.

    Google Scholar 

  • Platonova, O.A. 1981. Singularities of the mutual disposition of a surface and a line,Russian Math. Surveys 36(1):248–149.

    Google Scholar 

  • Platonova, O.A. 1984. Singularities of projections of smooth surfaces,Russian Math. Surveys 39:177–178.

    Google Scholar 

  • Ponce, J. and Kriegman, D.J. 1990. Computing exact aspect graphs of curved objects: Parametric patches, Tech. Rept. UIUCDCSR-90-1579, University of Illinois at Urbana-Champaign, April.

  • Ponce, J., Petitjean, S. and Kriegman, D. 1991. Computing exact aspect graphs of curved objects: Algebraic surfaces,Proc. Europ. Conf. Comput. Vis.

  • Rieger, J. 1987. On the classification of views of piecewise smooth objects,Image Vis. Comput. 5:91–97.

    Google Scholar 

  • Rieger, J.H. 1990. The geometry of view space of opaque objects bounded by smooth surfaces.Artificial Intelligence 44:1–40.

    Google Scholar 

  • Rieger, J.H. 1992. Global bifurcations sets and stable projections of non-singular algebraic surfaces,Intern. J. Comput. Vis. 7(3): 171–194.

    Google Scholar 

  • Seales, W.B. and Dyer, C.R. 1991. Constrained viewpoint from occluding contour,Proc. IEEE Workshop on Directions in Automated “CAD-Based” Vision, Maui, June, pp. 54–63.

  • Sederberg, T.W., Anderson, D.C., and Goldman, R.N. 1984. Implicit representation of parametric curves and surfaces,Comput. Vis. Graphics, Image Process, 28:72–84.

    Google Scholar 

  • Shafer, S.A. 1985.Shadows and Silhouettes in Computer Vision. Kluwer Academic Publishers: Norwell, MA.

    Google Scholar 

  • Sripradisvarakul, T. and Jain, R. 1989. Generating aspect graphs of curved objects,Proc. IEEE Workshop on Interpretation of 3D Scenes, Austin, TX, December, pp. 109–115.

  • Stewman, J. and Bowyer, K.W. 1987. Aspect graphs for planar-face convex objects.Proc. IEEE Workshop on Computer Vision, Miami, pp. 123–130.

  • Stewman, J. and Bowyer, K.W. 1988. Creating the perspective projection aspect graph of polyhedral objects,Proc. 2nd Intern. Conf. Comput. Vis.

  • Thom, R. 1956. Le singularités des applications différentiables,Annales Institut Fourier, 6:43–87.

    Google Scholar 

  • Wall, C.T.C. 1976. Geometric properties of generic differentiable manifolds. In A., Dold and B., Eckmann, eds.,Geometry and Topology, Springer-Verlag: Rio de Janeiro, pp. 707–774.

    Google Scholar 

  • Wang, R. and Freeman, H. 1990. Object recognition based on characteristic view classes,Proc. 10th Intern. Conf. Patt. Recog., Atlantic City, NJ.

  • Watts, N. 1987. Calculating the principal views of a polyhedron. Tech. Rept. CS Tech. Report 234, Rochester University.

  • Weatherburn, C.E. 1927.Differential Geometry. Cambridge University Press: New York.

    Google Scholar 

  • Whitney, H. 1955. On singularities of mappings of Euclidean spaces. I. Mappings of the plane into the plane,Annals of Mathematics 62(3): 374–410.

    Google Scholar 

  • Whitted, T. 1980. An improved illumination model for shaded display,Commun. ACM, 23(6): 343–349.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Beckman Institute and Department of Computer Science, University of Illinois, 61801, Urbana, IL

    Sylvain Petitjean & Jean Ponce

  2. Center for Systems Science, Department of Electrical Engineering, Yale University, 06520-1968, New Haven, CT

    David J. Kriegman

Authors
  1. Sylvain Petitjean
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jean Ponce
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. David J. Kriegman
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Petitjean, S., Ponce, J. & Kriegman, D.J. Computing exact aspect graphs of curved objects: Algebraic surfaces. Int J Comput Vision 9, 231–255 (1992). https://doi.org/10.1007/BF00133703

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00133703

Keywords

Search

Navigation