Role of algebraic geometry in computer vision

Abstract

In this paper we describe the geometric components of our model-based approach to 3D rigid object recognition and positioning from range data that have potential applications in Graphics, Geometric Modeling, and Computer Aided Geometric Design. As in many other object recognition systems, due to occlusion, objects are recognized and located by comparing and geometrically matching small regions of the data set with corresponding regions of known models stored in a database. In our case, a known object is represented in the database as a hierarchical collection of regions, each of them approximated by an algebraic surface. The preliminary recognition and matching is based on comparing euclidean invariant functions of the coefficients of the corresponding polynomials. The final recognition and matching is based on determining how well the data fits a stored model. Although we have not implemented a complete system yet, towards the implementation of an object recognition and position estimation system based on this structure, a number of computational problems associated with algebraic curves and surfaces have been analyzed and solved. These problems, described in this paper, are: (1) how to fit unconstrained algebraic curve and surfaces to data, (2) how to fit bounded algebraic curves and surfaces, (3) how to efficiently compute Euclidean invariants of polynomials, and (4) how to define an intrinsic coordinate system of a polynomial, generalizing the notion of center and principal axes of a nonsingular quadric curve or surface. The intrinsic coordinate system of a polynomial can be used to transform its coefficients to a normal form. The coefficients of a polynomial in normal form constitute a complete set of Euclidean invariants.