Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-26T16:37:35.342Z Has data issue: false hasContentIssue false
  • English
  • Français

A symbolic approach to polyhedral scene analysis by parametric calotte propagation*

Published online by Cambridge University Press:  01 July 2008

Hongbo Li ,
Lina Zhao  and
Ying Chen
Hongbo Li*
Affiliation:
Mathematics Mechanization Research Center, AMSS, Chinese Academy of Sciences, Beijing 100080, P. R. China
Lina Zhao
Affiliation:
Department of Mathematics and Computer Science, School of Science, Beijing University of Chemical Technology, Beijing 100080, P. R. China
Ying Chen
Affiliation:
Department of Basic Sciences, Beijing Electronic Science and Technology Institute, Beijing 100080, P. R. China
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

Polyhedral scene analysis studies whether a 2D line drawing of a 3D polyhedron is realizable in space, and if so, it gives the results of parameterizing the space of all possible realizations. For generic 2D data, symbolic computation with Grassmann–Cayley algebra is needed in the analysis. In this paper, we propose a method called parametric calotte propagation to solve the realization and parameterization problems for general polyhedral scenes at the same time. In algebraic manipulation, parametric propagation is more efficient than elimination. In applications, it can lead to linear construction sequences for nonspherical polyhedra whose resolvable sequences do not exist.

Keywords

Structure geometryPolyhedral scene analysisGrassmann–Cayley algebraBracket algebraConstraint satisfaction
Type
Article
Information
Robotica , Volume 26 , Special Issue 4: Geometry in Robotics: Sensing , July 2008 , pp. 483 - 501
Copyright
Copyright © Cambridge University Press 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

Supported partially by NSFC 10471143 and NKBRSF 2004CB318001.

References

1.Buchberger, B. “Application of Gröbner basis in non-linear computational geometry,” In: Scientific Software (Rice, J., ed.) (Springer, New York, 1988).Google Scholar
2.Bokowski, J. and Sturmfels, B., Computational Synthetic Geometry, LNM 1355 (Springer, Berlin, 1989).Google Scholar
3.Crapo, H. and Whiteley, W., “Stresses on frameworks and motions of panel structures: A projective geometric introduction,” Struct. Topol. 6, 42–82 (1982).Google Scholar
4.Crapo, H. and Ryan, J., “Spatial realizations of linear scenes,” Struct. Topol. 13, 33–68 (1986).Google Scholar
5.Crapo, H., “Invariant-theoretic methods in scene analysis and structural mechanics,” J. Symbolic Comput. 11, 523–548 (1991).Google Scholar
6.Crapo, H. and Whiteley, W., Plane self stresses and projected polyhedra I: The basic pattern,” Struct. Topol. 20, 55–78 (1993).Google Scholar
7.Doubilet, P., Rota, G. C. and Stein, J., On the foundations of combinatorial theory IX: Combinatorial methods in invariant theory, Stud. Appl. Math. 57, 185–216 (1974).Google Scholar
8.Hestenes, D. and Ziegler, R., Projective geometry with Clifford algebra, Acta Appli. Math. 23, 25–63 (1991).Google Scholar
9.Huffman, D., Realizable configurations of lines in pictures of polyhedra, Mach. Intell. 8, 493–509 (1977).Google Scholar
10.Li, H., Vectorial equation-solving for mechanical geometry theorem proving. J. Autom. Reasoning 25, 83–121 (2000).Google Scholar
11.Li, H. and Wu, Y., Automated short proof generation for projective geometric theorems with Cayley and Bracket algebras, I. Incidence geometry. J. Symbolic Comput. 36 (5), 717–762 (2003).Google Scholar
12.Li, H., Zhao, L. and Chen, Y., “Polyhedral scene analysis combining parametric propagation with calotte analysis,” In: Computer Algebra and Geometric Algebra with Applications, LNCS 3519 (Springer Berlin, 2005) pp. 383–402.Google Scholar
13.Li, H., “nD polyhedral scene reconstruction from single 2D line drawing by local propagation,” In: Automated Deduction in Geometry, LNAI 3763 (Springer, Berlin 2006) pp. 169–197, 2006.Google Scholar
14.Mackworth, A., Interpreting pictures of polyhedral scenes, Artif. Intelligence 4, 121–137 (1973).Google Scholar
15.Richter-Gebert, J., Realization Spaces of Polytopes. LNM 1643 (Springer, Berlin, 1996).Google Scholar
16.Ros, L. and Thomas, F., “Analysing Spatial Realizability of Line Drawings Through Edge-Concurrence Tests,” Proceedings of the IEEE International Conference on Robotics and Automation, vol IV (May 1998) pp. 3559–3566.Google Scholar
17.Ros, L., “A kinematic-geometric approach to spatial interpretation of line drawings,” PhD Thesis (Polytechnic University of Catalonia, May 2000).Google Scholar
18.Ros, L. and Thomas, F., Overcoming superstrictness in line drawing interpretation. IEEE Trans. PAMI 24 (4), 456–466 (2002).Google Scholar
19.Sturmfels, B. and Whiteley, W., On the synthetic factorization of projectively invariant polynomials. J. Symbolic Comput. 11, 439–453 (1991).CrossRefGoogle Scholar
20.Sturmfels, B., Algorithms in Invariant Theory (Springer, Wien, 1993).CrossRefGoogle Scholar
21.Sugihara, K., Mathematical structures of line drawings of polyhedrons—Towards man–machine communication by means of line drawings. IEEE Trans. PAMI 4, 458–469 (1982).CrossRefGoogle ScholarPubMed
22.Sugihara, K., An algebraic and combinatorial approach to the analysis of line drawings of polyhedra. Discrete Appl. Math. 9, 77–104 (1984).Google Scholar
23.Sugihara, K., An algebraic approach to shape-from-image problems, Artif. Intell. 23, 59–95 (1984).CrossRefGoogle Scholar
24.Sugihara, K., Machine Interpretation of Line Drawings (MIT Press, Cambridge, MA, 1986).Google Scholar
25.Sugihara, K., Resolvable representation of polyhedra, Discrete Comput. Geom. 21 (2), 243–255 (1999).Google Scholar
26.White, N., The bracket ring of combinatorial geometry I. Trans. Am. Math. Soc. 202, 79–103 (1975).Google Scholar
27.White, N. and Whiteley, W., The algebraic geometry of stresses in frameworks, SIAM J. Alg. Discrete Math. 4, 481–511 (1983).Google Scholar
28.White, N., Multilinear cayley factorization. J. Symbolic Comput. 11, 421–438 (1991).Google Scholar
29.Whiteley, W., From a line drawing to a polyhedron. J. Math. Psych. 31, 441–448 (1987).Google Scholar
30.Whiteley, W., A matroid on hypergraphs with applications in scene analysis and geometry. Discrete Computational Geometry 4, 75–95 (1989).Google Scholar
31.Whiteley, W., Weavings, sections and projections of spherical polyhedra. Discrete Appl. Math. 32, 275–294 (1991).Google Scholar
32.Whiteley, W., “Matroids and rigid structures,” In: Matroid Applications (White, N., ed.) Encyclopedia of Mathematics and Its Applications 40 (Cambridge University Press, Cambridge, 1992) pp. 1–53.Google Scholar
33.Wu, W.-T., Basic Principles of Mechanical Theorem Proving in Geometries, Volume 1: Part of Elementary Geometries. Science Press, Beijing, 1984; Springer, Wien, 1994.Google Scholar