|
Vol: 56(70) No: 2 / June 2011 Reconstructing a Model of Implicit Shapes from an Unorganized Point Set Levente Hunyadi Department of Automation and Applied Informatics, Budapest University of Technology and Economics, 1111 Budapest, Goldmann György tér 3., Hungary, phone: +36 1 463-2870, e-mail: hunyadi@aut.bme.hu, web: www.aut.bme.hu/portal/hunyadi István Vajk Department of Automation and Applied Informatics, Budapest University of Technology and Economics, 1111 Budapest, Goldmann György tér 3., Hungary Keywords: model reconstruction, alternating optimization, total least squares, self-organizing method. Abstract Reverse engineering whereby we seek to capture a relationship or represent a physical object with a compact computer model comprising of a set of simple objects such as straight lines and quadratic curves for 2D, or planes and quadratic surfaces for 3D is a frequent engineering problem. Unorganized coordinate data acquired from the variables of the relationship or from the physical object with a measuring device, however, are polluted with noise due to the impact of the environment, surface attributes of the object or uncertainty of the measuring device. In order to construct a computer model such that the misfit between the model and the true relationship or object is minimized, we present an approach that alloys clustering and generalized total least squares regression. An optimization scheme is presented where two steps, data regrouping and implicit shape parameter estimation are alternated, which converges to a model captured by a set of primitive shapes. References [1] S. Van Aelsta, X. Wangb, R. H. Zamarc, and R. Zhud, “Linear grouping using orthogonal regression. Computational Statistics and Data Analysis”, vol. 50, no. 5, pp. 1287–1312, March 2006. [2] M. Aigner and B. Jüttler, “Robust fitting of implicitly defined surfaces using gauss–newton-type techniques”, The Visual Computer: International Journal of Computer Graphics, vol. 25, no. 8, pp. 731–741, 2009. [3] M. Ester, H. Kriegel, J. Sander, and X. Xu, „A density-based algorithm for discovering clusters in large spatial databases with noise”, in Proc. 2nd International Conference on Knowledge Discovery and Data Mining, Portland, OR, USA, 1996, pp. 226. [4] G. Guennebaud and M. Gross, “Algebraic point set surfaces”, in Proc. SIGGRAPH ’07: ACM SIGGRAPH 2007 papers, New York, NY, USA, pp. 23. [5] L. Hunyadi and I. Vajk, “An approach to identifying linearizable dynamic errors-in-variables systems”, in Proc. 10th International PhD Workshop on Systems and Control, Hluboka nad Vltavou, Czech Republic, 2009, paper 102. [6] L. Hunyadi and I. Vajk, “Implicit model fitting to an unorganized set of points”, in Proc. IEEE International Joint Conferences on Computational Cybernetics and Technical Informatics (ICCC-CONTI 2010), Timisoara, Romania, 2010, pp. 487–491. [7] W. Lia, S. Xua, G. Zhaob, and L. P. Goha, “Adaptive knot placement in B-spline curve approximation”, Computer-Aided Design Special Issue: Modelling and Geometry Representations for CAD, vol. 37, no. 8, pp. 791–797, July 2005. [8] Y. Ohtake, A. Belyaev, M. Alexa, G. Turk, and H.-P. Seidel, “Multi-level partition of unity implicits”, ACM Trans. Graph., vol. 22, no. 3, pp. 463–470, 2003. [9] I. Vajk and J. Hetthéssy., “Identification of nonlinear errors-in-variables models”, Automatica, vol. 39, pp.:2099–2107, 2003. [10] W. Wang, H. Pottmann, and Y. Liu, “Fitting B-spline curves to point clouds by curvature-based squared distance minimization”, ACM Transactions on Graphics, vol. 25, no. 2, pp. 214–238, April 2006. [11] Z. Yang, J. Deng, and F. Chen, “Fitting unorganized point clouds with active implicit b-spline curves”, The Visual Computer, vol. 21, no. 8, pp. 831–839, 2005. [12] C.-G. Zhu and R.-H. Wang, „Least squares fitting of piecewise algebraic curves”, Mathematical Problems in Engineering, 2007. |