SUGR – Statistically Uncertain Geometric Reasoning

Overview

Recently, projective geometry was extensively used in areas sugr_teasersuch as Computer Vision and Computer Graphics to handle geometrical structures and relations in images and 3D space. Using the so-called Grassmann-Cayley algebra, one can find nice algebraic bilinear expressions for geometric tasks such as the intersection of a line and a plane in 3D, tests of geometric relations or camera projection of 3D points and lines.

However it is not clear how to include notions of uncertainty into the algebraic expressions for projective geometry tasks. SUGR attempts to model uncertainty by the second moments of the homogeneous parameter vectors. Usually we expect the user to know the covariance vector of a point in 3D or 2D or maybe the covariance vector of a line in 2D. For all subsequent constructions from these entities we can do error propagation which is sufficently accurate for practical cases.

With the proposed uncertainty model, one can do direct construction, construction by minimizationq and statistical tests with reasonable results as long as the errors are small as in most real-world applications.

.

Implementations

  • Java
    There exists an implementation in Java developed and maintained at our department. It is free with source code. You can download it from here
  • Perl
    There is also an implementation in Perl available here, which was written by Stephan Heuel as a preview version.  This version been tested on Linux systems, see the README file for details. It may also run on Windows systems, but this hasn’t been tested. This software will not be maintained  or developed any further.
.

Literature

  • S. Heuel. Points, lines and planes and their optimal estimation. In Pattern Recognition, 23rd DAGM Symposium, number 2191 in LNCS, pages 92-99. Springer, September 2001. (pdf)
  • S. Heuel and W. Förstner. Matching, reconstructing and grouping 3d lines from multiple views using uncertain projective geometry. In CVPR ’01. IEEE, 2001. accepted for publication. (pdf)
  • S. Heuel and W. Förstner. Topological and geometrical models for building extraction from multiple images. In Automatic Extraction of Man-Made Objects from Aerial and Space Images (III). Balkema Publishers, 2001.
  • W. Förstner, A. Brunn, and S. Heuel. Statistically testing uncertain geometric relations. In G. Sommer, N. Krüger, and Ch. Perwass, editors, Mustererkennung 2000, pages 17-26. DAGM, Springer, September 2000. (pdf)
  • Förstner, Wolfgang: Uncertainty and Projective Geometry. In: Bayro Corrochano, Eduardo (Hg.): Handbook of Geometric Computing. 2005, S. 493-535. (pdf)
  • Meidow, Jochen / Beder, Christian / Förstner, Wolfgang:Reasoning with uncertain points, straight lines, and straight line segments in 2D. In: ISPRS Journal of Photogrammetry and Remote Sensing, 64. Jg. 2009, Heft 2, S. 125-139. (pdf)
  • Meidow, Jochen / Förstner, Wolfgang / Beder, Christian:Optimal Parameter Estimation with Homogeneous Entities and Arbitrary Constraints. In: 31th Annual Symposium of the German Association for Pattern Recognition (DAGM). Jena, Germany 2009 (pdf)