ABSTRACT
Applications of Computer Algebra to Image Understanding,
Object Recognition, and Computer Vision
by
Dr. Peter F. Stiller
for
3rd IMACS Conference on Applications of Computer Algebra
Keywords: symbolic computation, computer algebra, image understanding,
computer vision, geometric configurations, geometric invariants,
object/image equations
The general problem of single-view recognition is central to many image
understanding and computer vision tasks; so central, that it has been
characterized as the ``holy grail'' of computer vision (see [2]). Initial work
in the 70's and 80's made use of the mathematics of geometric invariant theory
as a tool for testing geometric consistency in certain restricted situations.
Unfortunately, negative results of Burns, Weiss, and Riesman (see [1])
confirmed that there are no general-case view invariants. In other words,
there are no values computable from an image of an object (thought of as a 3-D
configuration of geometric features such as points, lines, conics, etc.) that
are constant for that object across all possible images. This fact means that
classical geometric invariant theory cannot be used directly for single-view
recognition, and that the problem of single-view recognition is considerably
more complex. Never-the-less, it is intuitively clear that a single 2-D view
carries useful geometric information about the original 3-D object. The
question of how to extract that information is the central theme of our work.
We have been able to show that much of this information can be characterized by
a correspondence in the mathematical sense of algebraic geometry.
In this paper, we continue to exploit the use of advanced mathematical
techniques from algebraic geometry, notably the theory of correspondences and a
novel "equivariant" invariant theory, to the general problem of recognizing
three dimensional geometric configurations (such as arrangements of lines,
points, and conics) from a single two dimensional view. Of necessity, the
approach is view independent. This forces us to characterize a configuration
by its 3D or 2D geometric invariants. The algebro-geometric techniques provide
the machinery to understand the relationship that exists between the 3D
geometry and its "residual" in a 2D image. This relationship is shown to be a
correspondence in the technical sense of algebraic geometry. Exploiting this,
one can attempt compute a set of fundamental equations, which generate the
ideal of the correspondence, and which completely describe the mutual 3D/2D
constraints. We have chosen to call these equations "object/image equations".
They can be exploited in a number of ways. For example, from a given 2D
configuration, we can determine a set of non-linear constraints on the
geometric invariants of 3D configurations capable of producing the given 2D
configuration, and thus arrive at a test for determining the object being
viewed. Conversely, given a 3D geometric configuration (features on an
object), we can dervive a set of equations that constrain the images of that
object.
Methods to compute a complete set of generating object/image equations
rely heavily on modern methods in symbolic computation and the use of computer
algebra systems. The computational techniques include advanced geometric
techniques like resultants, sparse resultants, and Grobner bases, as well as
the classical calculus of invariant theory. The calculations have been carried
out in a number of important cases, including point features, and the results
have been used to develop and implement algorithms for use in a variety of
image understanding applications. Two notable successes include a system for
recognition and identification of aircraft types in reconaisance photos and a
preliminary system for target identification being worked on by the U. S.
Navy.
In this paper, we focus on the computational issues and on the the
complexity of the symbolic computations, particularly in case of recognizing
configurations of lines, because it leads to a highly complex, highly
non-generic, system of equations that must be reduced using symbolic
computational tools. Most of the subtleties of our approach are illustrated
by this case - recognizing 3-D configurations of line features from a single
2-D image. A complete set of invariants for line configurations in 3-D was
only recently made available through the work of Huang in '92. Our subsequent
efforts to compute explicitly the so-called object/image equations for the
correspondence led instead to a residual system that must be attacked by
sophisticated KSY resultant, sparse resultant or Grobner basis algorithms.
Thus we have been forced to direct a portion of our research effort to the
development of fast mixed numerical/symbolic methods to handle recognition
testing in real time. These algorithms of course have a wider applicability.
Bibliography
[1] Burns, J., Richard S. Weiss and Edward M. Riseman, ``The Invariance in
Computer Vision, J.L. Mundy and Andrew Zisserman, eds., MIT Press, 1992.
[2] Weiss, Issac, ``Geometric Invariants and Object Recognition,''
International Journal of Computer Vision, 10.3, 207-231, 1993.
Biographical Sketch
Dr. Stiller is Professor of Mathematics and Computer Science at Texas A&M
Univeristy. He also currently serves as Assistant Director of the Institute
for Scientific Computation and as Director of the Center for Geometric,
Discrete, and Symbolic Computation. He is the author of over three dozen
papers and numerous technical reports in a wide variety of areas in mathematics
and computer science. His current work focuses on the use of techniques in
algebraic geometry and computational geometry to study problems in image
understanding, database indexing for content-based retrieval, and computer
vision. His work is currently funded by the National Science Foundation, the
Air Force Office of Scientific Research, the Texas Higher Education
Coordinating Board through its Advanced Technology and Advanced Research
Programs, and by private industry.