What is an Implicit Polynomial Curve?

Implicit Polynomial (IP) curves and surfaces are mathematical models for the representation of 2D curves and 3D surfaces, respectively.  IP curves and surfaces provide a powerful mathematical framework for

Drawbacks of IP curves and surfaces has been the lack of stability in the fitted IP representations and their parameters under noise and shape perturbations.

Example: Intersection of the polynomial z=x2+4y2-1 with the plane z=0, yields the IP curve x2+4y2-1=0 which describes an ellipse in the x-y plane. This is illustrated in the following figure.

The implicit polynomial curve (IP curve) is the set of points in the x-y plane where the associated polynomial takes on the value 0.
More generally, a second degree IP curve is given by: a2,0x2+a1,1xy+a0,2y2+a1,0x+a0,1y+a0,0=0.
Second degree IP curves are described by 6 coefficients: a2,0, a1,1, a0,2, a1,0, a0,1, a0,0.
An IP curve of degree d is described by (d+1)(d+2)/2 coefficients: ad,0 , ad-1,1 , ... , a0,d , ad-1,0 , ... , a0,0.

f(x,y) is a polynomial in 2 variables and the IP curve is the set of points {(x,y) : f(x,y)=0}. The equation f(x,y)=0 defining the IP curve is sometimes referred to as the IP curve.
Vector notation provides a more compact representation. Let the coefficient vector be

and let the vector of monomials be
.
Then the IP curve equation is simply found as  where the superscipt t denotes the vector transpose.


Comparison of IP curves with other shape representations
Chain codes, polygonal approximations, signature curves, skeletons, B-splines and Fourier Descriptors are other shape boundary representation models. IP curves are often compared with Fourier Shape Descriptors and B-splines in terms of shape representation and object recognition power. Fourier Descriptors(FDs) are very useful in computer vision in certain circumstances and not in others which are better handled within the IP framework. Two main types of FDs: IP curves do not suffer from these drawbacks. B-splines are very efficient for curve representation due to their boundedness, continuity, local controllability; however, their usefulness for shape recognition is hindered by the non-uniquesness of their parameters.

Fitting IP curves to point data sets
Given a discrete set of points in 2D space , and a degree d, choose the coefficient vector a such that the IP curve ``best'' represents the data set. "Best" representation translates to the coefficient vector that minimizes some error function. Examples of IP curve fits of degree 4, 6 and 8 to two data sets are shown below. The red points represent the points in the data set and the black curves represent the IP curves fitted to these data sets. These IP curve fits were obtained by the gradient-1/ridge regression algorithm which was an important part of my PhD research. By introducing a new error function that incorporates derivatives as well as data point locations we were able to significantly improve the quality of the shape representations and the robustness of the implicit polynomial coefficients to noise and perturbations over previous methods. Moreover, by introducing the statistical technique of ridge regression in to implicit polynomial curve fitting, we are able to obtain coefficient vectors robust enough to perform shape recognition and/or pose estimation based only on the implicit polynomial coefficients. This is a very fast and powerful way of doing object recognition. Details of this work can be found in

Degree 4 IP Curve Degree 6 IP curve Degree 8 IP curve

Notice that as the degree of the IP curve is increased so does its shape representation potential: while lower degree IP curves are good at obtaining a coarse representation, higher degree IP curves follow the data curve closer.


Gradient-1/Ridge Regression (g1/rr) Fitting of IP Curves

Fit IP curves to your data with the g1/rr algorithm

As mentioned earlier, the fitting of IP curves to data refers to the estimation of model parameters (IP coefficients in this case) from the data by optimization of a fitting function (equivalently minimization of an error function). Classical least squares fitting of IP curves is the most straightforward approach to this problem: the error function is the sum of squared values of the polynomial at the points in the data set. Here is an example:

The circles in the above figure are the points in a data set, the curve representing the silhoutte of a boot. The black curve is the IP curve fitted to this data set with classical least squares fitting. The IP curve is not an adequate representation for the data because it has several pieces and does not respect the continuity of the data curve it is fitted to. A look at the polynomial surface (recall that the IP curve is the set of points in the x-y plane where the polynomial takes on the value 0) is revealing about the causes of this problem:

Confused? Take another look at this
Observe that the polynomial surface seen in the above figure is saddle shaped. Consequently, the IP curve (shown on top of the surface with the black curve) is broken into several pieces as the gradient of the polynomial along the data set switches back and forth between pointing towards the outside of the data curve and the inside. Classical fitting also has no robustness to noise and data perturbations; very different representations and polynomial coefficients are obtained with small changes to the data. Better results are obtained with other methods such as approximate Euclidean distance error minimization. However, these methods either still have problems with robustness and the quality of shape representations and/or involve non-linear minimizations which are time consuming. Gradient-1fitting provides a way of obtaining better IP curve fits while remaining in a linear least squres minimization framework. The idea is to use differential geometry information from the data curve to include error terms on the derivatives of the polynomial as well as the value of the polynomial at the data points. Specifically, we force the polynomial gradient vector to be in the direction that is perpendicular to the data curve tangent and to have length 1. Hence, the name gradient-1 fitting. It can be seen below that the IP curve obtained with this method is a much better representation of the data then the one obtained with classical least squares method. The computational cost of the gradient-one algorithm is not higher than the classical least squares algorithm; it involves a matrix inversion which has dimensions equal to the number of terms in the polynomial. This number is 15 for a 4'th degree polynomial or more generally (d+1)(d+2)/2 for a d'th degree polynomial.

Incorporating the polynomial gradient into the error function in the manner described above introduces forces the IP curve to behave more regularly around the vicinity of the data curve. In other words, the polynomial gradient consistently points towards the inside (or the outside) of the data curve; consequently, the IP curve has a single piece that represents the data. This can be seen more clearly in the figure below. So where are the other 2 pieces of the IP curve that are irrelevant to the data in the image above coming from? The answer is simple: 2D polynomials and thus implicit polynomial curves are global objects defined over the entire x-y plane and data sets which have finite spatial extent may not provide sufficient forces in the error function to control the behaivour of the polynomial in locations other than their immediate vicinity.

This statement is supported by an interesting observation: If one pertubs the data a little, we observe the following:

The interested reader is referred to To remedy the remaining instability problems in implicit polynomial curve fitting, we incorporated the method of ridge regression in the fitting. Gradient-1 fitting, like other linear least squares estimation methods, involves the inversion of a square matrix which has number of dimensions equal to the number of parameters being estimated. Ridge regression weighs each dimension in the solution such that stable dimensions are emphasized and non-stable ones are diminished as much as possible. Ridge regression is very similar to Principal Component Analysis (PCA); however, unlike in PCA dimensions are not either discarded or kept but weighted. This property of ridge regression allows properties such as rotation invariance of gradient-one fitting to be preserved.
Ridge regression involves a parameter, k, which controls the amount of weighting. We tested ridge regression with respect to object recognition in the following setup: 27 objects were used and implicit polynomial curves were fit to them. Invariants of theses IP curves were then used for recognition under noise, shape perturbations and missing data. Using ridge regression in the fitting stage of the experiment significantly improved recognition rates, especially when 6'th degree IP curves were used. Moreover, k=0.001 seemed to be the optimal value fo the ridge regression parameter in this experiment. These results can be seen in the graph below.


DEMO: INTERACTIVE IMPLICIT POLYNOMIAL CURVE FITTING

contact: tt@lems.brown.edu