Fitting of Analytic Surfaces to Noisy Point Clouds

Oscar Ruiz, Santiago Arroyave, Diego Acosta

Design and Development of Processes (DDP) Group, Universidad EAFIT, Medellin, Colombia.
Laboratory of CAD/CAM/CAE, Medellin, Colombia.

DOI: 10.4236/ajcm.2013.31A004                

Abstract

Fitting C²-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.

Keywords

Surface Fitting; Optimization; Analytic Surfaces

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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
[2]	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
[3]	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.
[4]	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
[5]	E. K. P. Chong and S. H. Zak, “An Introduction to Optimization,” 2nd Edition, Wiley India Pvt. Ltd., New Delhi, 2010.
[6]	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
[7]	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.
[8]	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.
[9]	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
[10]	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
[11]	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
[12]	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
[13]	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.
[14]	R. A. Calvo, M. Partridge and M. Jabri, “A Comparative Study of Principal Component Analysis Techniques,” Proceedings of Ninth Australian Conference on Neural Networks, Brisbane, 11-13 February 1998, pp. 276-281.
[15]	L. Zhou and O. Salvado, “A Comparison Study of Ellipsoid Fitting for Pose Normalization of Hippocampal Shapes,” International Conference on Digital Image Computing Techniques and Applications (DICTA), Noosa, 6-8 December 2011. pp. 285-290.
[16]	P. D. Simari and K. Singh, “Extraction and Remeshing of Ellipsoidal Representations from Mesh Data,” Proceedings of Graphics Interface, 9-11 May 2005, Canadian Human-Computer Communications Society, pp. 161-168.
[17]	D. Marshall, G. Lukacs and R. Martin, “Robust Segmentation of Primitives from Range Data in the Presence of Geometric Degeneracy,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 23, No. 3, 2001, pp. 304-314. doi:10.1109/34.910883
[18]	D. A. Turner, I. J. Anderson, J. C. Mason and M. G. Cox, “An Algorithm for Fitting an Ellipsoid to Data,” National Physical Laboratory, Teddington, 1999.
[19]	J. Wallner, “On the Semiaxes of Touching Quadrics,” Resultate der Mathematik, Vol. 36, No. 3-4, 1999, pp. 373-383. doi:10.1007/BF03322124
[20]	P. Morena at Thingiverse, “Treefrog STL Model,” 2012. http://www.thingiverse.com/download:61236
[21]	E. Carlos at GrabCAD, “Fan STL Model,” 2012. http://grabcad.com/library/carcasa-de-un-ventilador-paraensayos/files/carca.stl