ABSTRACT

In this paper, we propose an efficient curve reconstruction method based on the classical least-square fitting scheme. Specifically, given planar sample points equipped with normals, we reconstruct the objective curve as the zero set of a hierarchical implicit ZP(Zwart-Powell)-spline that can recover large holes of dataset without loosing the fine details. As regularizers, we adopted two: a Tikhonov regularizer to reduce the singularity of the linear system and a discrete Laplacian operator to smooth out the isocurves. Benchmark tests with quantitative measurements are done and our method shows much better quality than polynomial methods. Compared with the hierarchical bi-quadratic spline for datasets with holes, our method results in compatible quality but with less than 90% computational overhead.

KEYWORD

Curve reconstruction, Least-square fitting, Hierarchical spline, ZP-splines, Regularization

REFERENCES(18)open

  1. [jounal] G. Taubin / 1991 / Estimation of planar curves, surfaces, and nonplanar space curves defined by implicit equations with applications to edge and range image segmentation / Pattern Analysis and Machine Intelligence, IEEE Transactions 13 (11) : 1115 ~ 1138

  2. [confproc] Z. Lei / 1996 / 3l fitting of higher degree implicit polynomials / Applications of Computer Vision, 1996. WACV ’96., Proceedings 3rd IEEE Workshop : 148 ~ 153

  3. [jounal] M. Blane / 2000 / The 3l algorithm for fitting implicit polynomial curves and surfaces to data / IEEE Transactions on Pattern Analysis and Machine Intelligence 22 (3) : 298 ~ 313

  4. [jounal] T. Tasdizen / 2000 / Improving the stability of algebraic curves for applications / Image Processing, IEEE Transactions 9 (3) : 405 ~ 416

  5. [book] B. Jüttler / 2000 / The Mathematics of Surfaces IX / Springer : 263 ~ 280

  6. [jounal] C.-G. Zhu / 2007 / Least squares fitting of piecewise algebraic curves / Mathematical Problems in Engineering 2007

  7. [jounal] M. Rouhani / 2015 / Implicit b-spline surface reconstruction / Image Processing, IEEE Transactions 24 (1) : 22 ~ 32

  8. [book] J. Duchon / 1977 / Constructive Theory of Functions of Several Variables, ser. Lecture Notes in Mathematics vol. 571 / Springer Berlin Heidelberg : 85 ~ 100

  9. [jounal] C. Giannelli / 2012 / THB-splines:The truncated basis for hierarchical splines / Computer Aided Geometric Design 29 (7) : 485 ~ 498

  10. [jounal] U. Zore / 2014 / Adaptively refined multilevel spline spaces from generating systems / Computer Aided Geometric Design 31 (7–8) : 545 ~ 566

  11. [jounal] F. Calakli / 2011 / SSD: Smooth signed distance surface reconstruction / Computer Graphics Forum 30 (7) : 1993 ~ 2002

  12. [jounal] P. B. Zwart / 1973 / Multivariate splines with nondegenerate partitions / SIAM Journal on Numerical Analysis 10 (4) : 665 ~ 673

  13. [book] M. J. D. Powell / 1974 / Software for Numerical Mathematics / Academic Press : 253 ~ 271

  14. [book] C. de Boor / 1993 / Box splines / Springer-Verlag New York, Inc

  15. [book] G. H. Golub / 2012 / Matrix Computations / Johns Hopkins University Press

  16. [jounal] R. Mehra / 2010 / Visibility of noisy point cloud data / 34 (3) : 219 ~ 230

  17. [web] D.-J. Kroon / 2D Line Curvature and Normals

  18. [confproc] E. Grinspun / 2006 / Introduction to discrete differential geometry: The geometry of plane curves / ACM SIGGRAPH 2006 Courses, ser. SIGGRAPH ’06 : 1 ~ 4