Fitting of Analytic Surfaces to Noisy Point Clouds
- 1 Laboratory of CAD/CAM/CAE, Medellin, Colombia
- 2 Laboratory of CAD/CAM/CAE, Medellin, Colombia
- 3 Design and Development of Processes (DDP) Group, Universidad EAFIT, Medellin, Colombia
Abstract
Fitting C 2 -continuous or superior surfaces to a set S of points sampled on a 2-manifold is central to reverse engineering, computer aided geometric modeling, entertaining, modeling of art heritage, etc. This article addresses the fitting of analytic (ellipsoid, cones, cylinders) surfaces in general position in . Currently, the state of the art presents limitations in 1 ) automatically finding an initial guess for the analytic surface F sought, and 2 ) economically estimating the geometric distance between a point of S and the analytic surface F . These issues are central in estimating an analytic surface which minimizes its accumulated distances to the point set. In response to this situation, this article presents and tests novel user-independent strategies for addressing aspects 1 ) and 2 ) above, for cylinders, cones and ellipsoids. A conjecture for the calculation of the distance point-ellipsoid is also proposed. Our strategies produce good initial guesses for F and fast fitting error estimation for F , leading to an agile and robust optimization algorithm. Ongoing work addresses the fitting of free-form parametric surfaces to S .
- H. Nyquist, “Certain Topics in Telegraph Transmission Theory,” Transactions of the American Institute of Electrical Engineers, Vol. 47, No. 2, 1928, pp. 617-644. doi:10.1109/T-AIEE.1928.5055024
- C. E. Shannon, “Communication in the Presence of Noise,” Proceedings of the IRE, Vol. 37, No. 1, 1949, pp. 10-21. doi:10.1109/JRPROC.1949.232969
- K. Levenberg, “A Method for the Solution of Certain Non-Linear Problems in Least Squares,” Quarterly Journal of Applied Mathmatics, Vol. II, No. 2, 1944, pp. 164-168.
- D. W. Marquardt, “An Algorithm for Least-Squares Estimation of Nonlinear Parameters,” Journal of the Society for Industrial and Applied Mathematics, Vol. 11, No. 2, 1963, pp. 431-441. doi:10.1137/0111030
- E. K. P. Chong and S. H. Zak, “An Introduction to Optimization,” 2nd Edition, Wiley India Pvt. Ltd., New Delhi, 2010.
- J. Wang and Z. Yu, “Quadratic Curve and Surface Fitting Via Squared Distance Minimization,” Computers and Graphics, Vol. 35, No. 6, 2011, pp. 1035-1050. doi:10.1016/j.cag.2011.09.001
- A. D. Sappa and M. Rouhani, “Efficient Distance Estimation for Fitting Implicit Quadric Surfaces,” 16th IEEE International Conference on Image Processing ICIP, Cairo, 7-12 November 2009, pp. 3521-3524.
- D. M. Yan, Y. Liu and W. Wang, “Quadric Surface Extraction by Variational Shape Approximation,” Geometric Modeling and Processing—GMP, Pittsburgh, 26-28 July 2006, pp. 73-86.
- X. Jiang and D. C. Cheng, “A Novel Parameter Decomposition Approach to Faithful Fitting of Quadric Surfaces,” Pattern Recognition, Vol. 3663, 2005, pp. 168-175. doi:10.1007/11550518_21
- X. Ying, L. Yang and H. Zha, “A Fast Algorithm for Multidimensional Ellipsoid-Specific Fitting by Minimizing a New Defined Vector Norm of Residuals Using Semidefinite Programming,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.:1856-1863, 2012. doi:10.1109/TPAMI.2012.109
- Q. Li and J. G. Griffiths, “Least Squares Ellipsoid Specific Fitting,” Proceedings of Geometric Modeling and Processing, 2004, pp. 335-340. doi:10.1109/GMAP.2004.1290055
- S. W. Kwon, F. Bosche, C. Kim, C. T. Haas and K. A. Liapi, “Fitting Range Data to Primitives for Rapid Local 3D Modeling Using Sparse Range Point Clouds,” Automation in Construction, Vol. 13, No. 1, 2004, pp. 67-81. doi:10.1016/j.autcon.2003.08.007
- O. Ruiz and C. Vanegas, “Statistical Assessment of Global and Local Cylinder Wear,” 5th IEEE International Conference on Industrial Informatics, Vienna, 23-26 July 2007, pp. 387-392.