Better Ways for Fitting Algebraic Curves

Note you must have java installed to run the online fitting program included in this article. 

This on-line fitting program fits planar algebraic curves (i.e., implicit polynomial curves) of user-specified degree to

user-drawn curve data. Detailed description of the Gradient 1 fitting algorithm and software is given in [1]. The Gradient 1 [1] and 3L  [2] fitting algorithms are the most stable algorithms known to date for fitting algebraic curves to somewhat noisy data. The Gradient 1 fitting algorithm minimizes the sum of the weighted algebraic distances from the data points to the fitted algebraic curve subjected to the constraint that the normals to the input curve data are close to the normals to the fitted algebraic curve at corresponding points. This latter constraint is a regularization of the curve fitting and results in far better fits than if the algebraic distance alone is used. The fitting algorithm is an explicit solution since it is the minimization of a quadratic form.

To operate this demo, click on the black screen and draw a curve with your cursor. Though the algorithm will fit curves for which the input curve intersects itself, the algorithm is designed for and works best for input curves that are open or closed but do not intersect themselves. In the line of boxes below the back screen, the second box from the left shows the number 1. Reset that number to the desired degree for the curve to be fitted. In the 3rd box, click on Weighted Gradient 1 and then click on the 4th box which says Fit Dataset. The graph of the fitted curve will then appear.

Other fits are available by selecting other choices in the 3rd box including Least Squares, a miminum mean squared algebraic error fit, and Gradient 1, the fit to the data where the regularization term is weighted equally with the sketch points. As indicated above, best results are obtained when the normals are weighted less than the sketched points. The Weighted Gradient 1 fit is the algebraic curve fit that results when the sketched point data is weighted 100 times more heavily than the estimated normals of the sketched data. Normals estimated for the sketched data may be visualized by right-clicking on the background of the fitting window and selecting the "Show Normals" check box.

If a good fit to the data can be had with an algebraic curve of low degree, e.g., of degree 2 or degree 4, the algorithm will produce a good fit. If a higher degree is needed, e.g., 6 or 8, the algorithm usually produces a good fit but there are also often annoying branches that lie away from the data. The amount of regularization used has some effect on the extent of these annoying branches, but the best way to get rid of them is simply to remove branches of the algebraic curve that do not lie near the input curve data.

For what purposes are algebraic curves effective? The computational cost for fitting them to curve data is small – real time for fitting curves of degree 8 or less. They work best for fitting free-form fairly smooth curves, but can also represent curves having curvature discontinuities, e.g., triangles, squares, etc. They are also very effective for quickly computing whether points in a set lie close to a stored curve. These curves have been extremely useful in estimating the axis/profile-curve pair for the dense-data laser scans of a pot sherd for a pot made on a wheel. (See algorithm from [3])

[1] Tasdizen and J.P. Tarel and D.B. Cooper, Improving the stability of algebraic curves for applications, IEEE Transactions on Image Processing, Vol 9:3, 405-416, March 2000.

[2] M. M. Blane, Z. Lei, H. Civi and D. B. Cooper, The 3L Algorithm for Fitting Implicit Polynomial Curves and Surfaces to Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000.

[3] Willis, A. and Cooper, D. et. al., Accurately Estimating Sherd 3D Surface Geometry with Application to Pot Reconstruction, Conference on Computer Vision and Pattern Recognition (CVPR) Workshop, 2003.