A randomized knot insertion algorithm for outline capture of planar images using cubic spline

ABSTRACT

The proposed work, in this paper, is concerned with an efficient technique of curve fitting using cubic splines. The technique has various phases including extracting outlines of images, detecting corner points from the detected outline, addition of extra knot points if needed. The last phase makes a significant contribution by making the technique automated. It uses the idea of knot insertion in a randomized manner. The proposed algorithm is an iterative one. The algorithm proposed is computationally efficient as compared to least square approach.

REFERENCES

• 1: Chetrikov, D. and Zsabo, S., A Simple and Efficient Algorithm for Detection of High Curvature Points in Planar Curves, In Proceedings of the 23rd Workshop of the Australian Pattern Recognition Group, 1999, 1751-2184.
• 2: Wang, W., Pottmann, H., and Liu, Y., Fitting B-Spline Curves to Point Clouds by Squared Distance Minimization, HKU CS Tech Report TR-2004-11, 2004.
• 3: A. Ardeshir Goshtasby, Grouping and parameterizing irregularly spaced points for curve fitting, ACM Transactions on Graphics (TOG), v.19 n.3, p.185-203, July 2000 [doi>10.1145/353981.353992]
• 4: M. Sarfraz , M. A. Khan, An automatic algorithm for approximating boundary of bitmap characters, Future Generation Computer Systems, v.20 n.8, p.1327-1336, November 2004 [doi>10.1016/j.future.2004.05.024]
• 5: Sarfraz, M., Some Algorithms for Curve Design and Automatic Outline Capturing of Images, International Journal of Image and Graphics, 2004, 301--324.
• 6: Hou, Z. J. and Wei, G. W., A New Approach to Edge Detection, Pattern Recognition, 2002, 1559--1570.
• 7: Reche, P., Urdiales, C., Bandera, A., Trazegnies, C. and Sandoval, F., Corner Detection by Means of Contour Local Vectors, Electronic Letters, 2002, 38(14).
• 8: Marji, M. and Siv, P., A New Algorithm for Dominant Points Detection and Polygonization of Digital Curves, Pattern Recognition, 2003, 2239--2251.
• 9: Curve Designing Using a Rational Cubic Spline with Point and Interval Shape Control, Proceedings of the International Conference on Information Visualisation, p.63, July 19-21, 2000
• 10: Wu-Chih Hu, Multiprimitive Segmentation Based on Meaningful Breakpoints for Fitting Digital Planar Curves with Line Segments and Conic Arcs, Image and Vision Computing, 2005, 783--789.
• 11: Kano, H., Nakata, H. and Martin, C. F., Optimal Curve Fitting and Smoothing using Normalized Uniform B-Splines: A Tool for Studying Complex Systems, Applied Mathematics and Computation, 2005, 96--128.
• 12: Yang, Z., Deng, J., and Chen, F., Fitting Unorganized Point Clouds with Active Implicit B-Spline Curves, Visual Computer, 2005, 831--839.
• 13: Lavoue, G., Dupont, F. and Baskurt, A., A New Subdivision Based Approach for Piecewise Smooth Approximation of 3D Polygonal Curves, Pattern Recognition, 2005, 1139--1151.
• 14: Yang, H., Wang, W., and Sun, J., Control Point Adjustment for B-Spline Curve Approximation, Computer Aided Design, 2004, 639--652.
• 15: Yang, X., Curve Fitting and Fairing using Conic Spines, Computer Aided Design, 2004, 461--472.
• 16: M. Sarfraz , M. R. Asim , A. Masood, Piecewise Polygonal Approximation of Digital Curves, Proceedings of the Information Visualisation, Eighth International Conference on (IV'04), p.991-996, July 14-16, 2004 [doi>10.1109/IV.2004.111]
• 17: Ji-Hwei Horng, An adaptive smoothing approach for fitting digital planar curves with line segments and circular arcs, Pattern Recognition Letters, v.24 n.1-3, p.565-577, January 2003 [doi>10.1016/S0167-8655(02)00277-5]
• 18: Biswajit Sarkar , Lokendra K. Singh , Debranjan Sarkar, Approximation of digital curves with line segments and circular arcs using genetic algorithms, Pattern Recognition Letters, v.24 n.15, p.2585-2595, November 2003 [doi>10.1016/S0167-8655(03)00103-X]
• 19: J. C. Carr , R. K. Beatson , J. B. Cherrie , T. J. Mitchell , W. R. Fright , B. C. McCallum , T. R. Evans, Reconstruction and representation of 3D objects with radial basis functions, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.67-76, August 2001 [doi>10.1145/383259.383266]
• 20: Juttler, B., and Felis, A., A Least Square Fitting of Algebraic Spline Surfaces, Advance Computer Mathematics, 2002, 135--152.
• 21: Bryan S. Morse , Terry S. Yoo , David T. Chen , Penny Rheingans , K. R. Subramanian, Interpolating Implicit Surfaces from Scattered Surface Data Using Compactly Supported Radial Basis Functions, Proceedings of the International Conference on Shape Modeling & Applications, p.89, May 07-11, 2001
• 22: Yang, X. N. and Wang G. Z., Planar Point Set Fairing and Fitting by Arc Splines, Computer Aided Design, 2001, 35--43.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Spline and piecewise polynomial interpolation

General Terms:
Algorithms, Experimentation, Theory

Keywords:
cubic spline, curve fitting, knot insertion, outline, planar image