The 3L Algorithm for Fitting Implicit Polynomial Curves and Surfaces to Data

M. M. Blane, Z. Lei, and David Cooper

Abstract

Of great importance to a wide variety of computer vision and image analysis problems is the ability to represent two- (2D) and three-dimensional (3D) data or objects. Implicit polynomial curves and surfaces are two of the most useful representations available. Their representational power is evidenced by their ability to smooth noisy data and to interpolate through sparse or missing data. Furthermore, their associated Euclidean and affine invariants are powerful discriminators, making implicit polynomials a computationally attractive technology for recognizing objects in arbitrary positions with respect to cameras or range sensors. In this paper, we introduce a completely new approach to fitting implicit polynomials to data. The algorithm represents a significant advancement of implicit polynomial technology for three important reasons. First, it is orders of magnitude faster than existing methods. Second, it has significantly better repeatability and numerical stability than current methods. Third, it can easily fit polynomials of high, such as 14th to 18th, degree. In addition, this approach provides a completely new way of thinking about and handling implicit polynomials.

Reference

@TECHREPORT{Blane:1996:T3L,
   author	= {M. M. Blane and Z. Lei and  David B. Cooper},
   title	= {The 3L Algorithm for Fitting Implicit Polynomial Curves and Surfaces to Data},
   institution  = {LEMS, Brown University, Providence, RI},
   type         = {LEMS TR-160}
   year		= {1996},
   note         = {http://www.lems.brown.edu/~jpt/lems160.html}
}

Compressed postscript file of the article (300 Kb)