This paper introduces a new hybrid functional-neural approach for surface reconstruction. Our approach is based on the combination of two powerful artificial intelligence paradigms: on one hand, we apply the popular Kohonen neural network to address the data parameterization problem. On the other hand, we introduce a new functional network, called NURBS functional network, whose topology is aimed at reproducing faithfully the functional structure of the NURBS surfaces. These neural and functional networks are applied in an iterative fashion for further surface refinement. The hybridization of these two networks provides us with a powerful computational approach to obtain a NURBS fitting surface to a set of irregularly sampled noisy data points within a prescribed error threshold. The method has been applied to two illustrative examples. The experimental results confirm the good performance of our approach. 1. Introduction Manufacturing industries are constantly evolving in response to the new challenges of the globalization and the growing competition in this global market. Product design is playing a central role in this process, as current customers are increasingly demanding a mass customization of the products. As a result, the geometric and aesthetic properties of the manufactured goods (shape, color, and dimensions) have to be modified frequently in order to meet the new market demands. A major step in this process is the generation of real prototypes with different materials to explore and analyze their geometric properties and the feedback of potential customers when exposed to different variations of the final product. Prototype generation and customization can be dramatically improved by using digital technologies, in which the physical model is digitized, stored, and manipulated by computer, a process called reverse engineering [1, 2]. Typically, this process begins with data sampling by using 3D laser scanning and other digitizing devices. This technology is intensively used for the construction of car bodies, ship hulls, airplane fuselage, and other free-form objects [2–7]. The resulting data points are then fitted to mathematical entities such as curves and surfaces, usually in parametric form. The output is a very accurate digital version of the real product, which is also simpler and easier to store, analyze, and manipulate. It also simplifies the transfer and communication processes among designers, manufacturers, and providers, making the model available in just a few seconds all over the world, a key aspect in our ubiquitously
References
[1]
T. Várady, R. R. Martin, and J. Cox, “Reverse engineering of geometric models—an introduction,” CAD Computer Aided Design, vol. 29, no. 4, pp. 255–268, 1997.
[2]
T. Varady and R. Martin, “Reverse engineering,” in Handbook of Computer Aided Geometric Design, G. Farin, J. Hoschek, and M. Kim, Eds., pp. 651–681, Elsevier Science, 2002.
[3]
R. E. Barnhill, Geometric Processing for Design and Manufacturing, SIAM, Philadelphia, Pa, USA, 1992.
[4]
A. Iglesias, G. Echevarría, and A. Gálvez, “Functional networks for B-spline surface reconstruction,” Future Generation Computer Systems, vol. 20, no. 8, pp. 1337–1353, 2004.
[5]
A. Iglesias and A. Gálvez, “A new artificial intelligence paradigm for computer aided geometric design,” in Artificial Intelligence and Symbolic Computation, vol. 1930 of Lectures Notes in Artificial Intelligence, pp. 200–213, 2001.
[6]
N. M. Patrikalakis and T. Maekawa, Shape Interrogation for Computer Aided Design and Manufacturing, Springer, Heidelberg, Germany, 2002.
[7]
H. Pottmann, S. Leopoldseder, M. Hofer, T. Steiner, and W. Wang, “Industrial geometry: recent advances and applications in CAD,” CAD Computer Aided Design, vol. 37, no. 7, pp. 751–766, 2005.
[8]
A. Gálvez, A. Iglesias, A. Cobo, J. Puig-Pey, and J. Espinola, “Bézier curve and surface fitting of 3D point clouds through genetic algorithms, functional networks and least-squares approximation,” in Computational Science and Its Applications—ICCSA 2007, vol. 4706 of Lectures Notes in Computer Science, pp. 680–693, 2007.
[9]
G. E. Farin, Curves and Surfaces for Computer-Aided Geometric Design, Morgan Kaufmann, San Francisco, Calif, USA, 5th edition, 2001.
[10]
A. Gálvez and A. Iglesias, “Efficient particle swarm optimization approach for data fitting with free knot B-splines,” CAD Computer Aided Design, vol. 43, no. 12, pp. 1683–1692, 2011.
[11]
J. Hoschek and D. Lasser, Fundamentals of Computer Aided Geometric Design, A. K. Peters, 1993.
[12]
J. Ling and S. Li, “Fitting B-spline curves by least squares support vector machines,” in Proceedings of the International Conference on Neural Networks & Brain Proceedings (ICNNB '05), pp. 905–909, IEEE Press, Beijing, China, October 2005.
[13]
T. C. M. Lee, “On algorithms for ordinary least squares regression spline fitting: a comparative study,” Journal of Statistical Computation and Simulation, vol. 72, no. 8, pp. 647–663, 2002.
[14]
W. Y. Ma and J. P. Kruth, “Parameterization of randomly measured points for least squares fitting of B-spline curves and surfaces,” Computer-Aided Design, vol. 27, no. 9, pp. 663–675, 1995.
[15]
W. P. 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, 2006.
[16]
H. P. Yang, W. P. Wang, and J. G. Sun, “Control point adjustment for B-spline curve approximation,” CAD Computer Aided Design, vol. 36, no. 7, pp. 639–652, 2004.
[17]
P. Dierckx, Curve and Surface Fitting with Splines, Oxford University Press, Oxford, UK, 1993.
[18]
H. Park and J.-H. Lee, “B-spline curve fitting based on adaptive curve refinement using dominant points,” CAD Computer Aided Design, vol. 39, no. 6, pp. 439–451, 2007.
[19]
L. A. Piegl and W. Tiller, “Least-squares B-spline curve approximation with arbitrary end derivatives,” Engineering with Computers, vol. 16, no. 2, pp. 109–116, 2000.
[20]
D. L. B. Jupp, “Approximation to data by splines with free knots,” SIAM Journal on Numerical Analysis, vol. 15, no. 2, pp. 328–343, 1978.
[21]
J. R. Rice, The Approximation of Functions, vol. 2, Addison-Wesley, Reading, Mass, USA, 1969.
[22]
J. Hertz, A. Krogh, and R. G. Palmer, Introduction to the Theory of Neural Computation, Addison-Wesley, Reading, Mass, USA, 1991.
[23]
M. G. Cox, “Algorithms for spline curves and surfaces,” in Fundamental Developments of Computer-Aided Geometric Design, L. Piegl, Ed., pp. 51–76, Academic Press, London, UK, 1993.
[24]
R. H. Franke and L. L. Schumaker :, “A bibliography of multivariate approximation,” in Topics in Multivariate Approximation, C. K. Chui, L. L. Schumaker, and F. I. Utreras, Eds., Academic Press, New York, NY, USA, 1986.
[25]
N. R. Draper and H. Smith, Applied Regression Analysis, Wiley-Interscience, 3rd edition, 1998.
[26]
D. R. Forsey and R. H. Bartels, “Surface fitting with hierarchical splines,” ACM Transactions on Graphics, vol. 14, pp. 134–161, 1995.
[27]
H. Pottmann, S. Leopoldseder, and M. Hofer, “Approximation with active bspline curves and surfaces,” in Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, pp. 8–25, IEEE Computer Society Press, 2002.
[28]
M. Eck and H. Hoppe, “Automatic reconstruction of B-spline surfaces of arbitrary topological type,” in Proceedings of the Computer Graphics Conference (SIGGRAPH '96), pp. 325–334, August 1996.
[29]
L. Piegl and W. Tiller, The NURBS Book, Springer, Berlin, Germany, 1997.
[30]
M. Prasad, A. Zisserman, and A. Fitzgibbon, “Single view reconstruction of curved surfaces,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '06), vol. 2, pp. 1345–1354, IEEE Computer Society Press, Los Alamitos, Calif, USA, June 2006.
[31]
M. Levoy, K. Pulli, B. Curless, et al., “The digital Michelangelo project: 3D scanning of large statues,” in Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '00), pp. 131–144, New Orleans, La, USA, July 2000.
[32]
M. C. Leu, X. Peng, and W. Zhang, “Surface reconstruction for interactive modeling of freeform solids by virtual sculpting,” CIRP Annals—Manufacturing Technology, vol. 54, no. 1, pp. 131–134, 2005.
[33]
C. V. Alvino and A. J. Yezzi Jr., “Tomographic reconstruction of piecewise smooth images,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '04), vol. 1, pp. I576–I581, Los Alamitos, Calif, USA, July 2004.
[34]
J. Rossignac and B. Borrel, “Multi-resolution 3D approximations for rendering complex scenes,” in Geometric Modeling in Computer Graphics, pp. 455–465, Springer, 1993.
[35]
C. L. Bajaj, F. Bernardini, and G. Xu, “Automatic reconstruction of surfaces and scalar fields from 3D scans,” in Proceedings of the 22nd Annual ACM Conference on Computer Graphics and Interactive Techniques, pp. 109–118, August 1995.
[36]
C. L. Bajaj, E. J. Coyle, and K.-N. Lin, “Arbitrary topology shape reconstruction from planar cross sections,” Graphical Models and Image Processing, vol. 58, no. 6, pp. 524–543, 1996.
[37]
M. Jones and M. Chen, “A new approach to the construction of surfaces from contour data,” Computer Graphics Forum, vol. 13, no. 3, pp. 75–84, 1994.
[38]
D. Meyers, S. Skinnwer, and K. Sloan, “Surfaces from contours,” ACM Transactions on Graphics, vol. 11, no. 3, pp. 228–258, 1992.
[39]
H. Park and K. Kim, “Smooth surface approximation to serial cross-sections,” CAD Computer Aided Design, vol. 28, no. 12, pp. 995–1005, 1996.
[40]
W. J. Gordon, “Spline-blended surface interpolation through curve networks,” Journal of Mathematics and Mechanics, vol. 18, no. 10, pp. 931–952, 1969.
[41]
H. Fuchs, Z. M. Kedem, and S. P. Uselton, “Optimal surface reconstruction from planar contours,” Communications of the ACM, vol. 20, no. 10, pp. 693–702, 1977.
[42]
T. Maekawa and K. H. Ko, “Surface construction by fitting unorganized curves,” Graphical Models, vol. 64, no. 5, pp. 316–332, 2002.
[43]
V. Savchenko, A. Pasko, O. Okunev, and T. Kunii, “Function representation of solids reconstructed from scattered surface points and contours,” Computer Graphics Forum, vol. 14, no. 4, pp. 181–188, 1995.
[44]
G. Echevarría, A. Iglesias, and A. Gálvez, “Extending neural networks for B-spline surface reconstruction,” in Computational Science—ICCS, vol. 2330 of Lectures Notes in Computer Science, pp. 305–314, 2002.
[45]
P. Gu and X. Yan, “Neural network approach to the reconstruction of freeform surfaces for reverse engineering,” Computer-Aided Design, vol. 27, no. 1, pp. 59–64, 1995.
[46]
B. Guo, “Surface reconstruction: from points to splines,” CAD Computer Aided Design, vol. 29, no. 4, pp. 269–277, 1997.
[47]
H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle, “Surface reconstruction from unorganized points,” Computer Graphics (ACM), vol. 26, no. 2, pp. 71–78, 1992.
[48]
C. T. Lim, G. M. Turkiyyah, M. A. Ganter, and D. W. Storti, “Implicit reconstruction of solids from cloud point sets,” in Proceedings of the 3rd Symposium on Solid Modeling and Applications, pp. 393–402, May 1995.
[49]
Y. Yu, “Surface reconstruction from unorganized points using self-organizing neural networks,” in Proceedings of IEEE Visualization '99, pp. 61–64, 1999.
[50]
M. S. Floater, “Parametrization and smooth approximation of surface triangulations,” Computer Aided Geometric Design, vol. 14, no. 3, pp. 231–250, 1997.
[51]
？. Oblon？ek and N. Guid, “A fast surface-based procedure for object reconstruction from 3D scattered points,” Computer Vision and Image Understanding, vol. 69, no. 2, pp. 185–195, 1998.
[52]
R. M. Bolle and B. C. Vemuri, “On three-dimensional surface reconstruction methods,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 1, pp. 1–13, 1991.
[53]
F. J. M. Schmitt, B. A. Barsky, and W.-H. Du, “An adaptive subdivision method for surface fitting from sampled data,” Computer Graphics (ACM), vol. 20, no. 4, pp. 179–188, 1986.
[54]
T. A. Foley, “Interpolation of scattered data on a spherical domain,” in Algorithms for Approximation II, J. C. Mason and M. G. Cox, Eds., pp. 303–310, Chapman and Hall, London, UK, 1990.
[55]
S. Sclaroff and A. Pentland, “Generalized implicit functions for computer graphics,” ACM Siggraph Computer Graphics, vol. 25, no. 4, pp. 247–250, 1991.
[56]
V. Pratt, “Direct least-squares fitting of algebraic surfaces,” Computer Graphics (ACM), vol. 21, no. 4, pp. 145–152, 1987.
[57]
A. Gálvez, A. Cobo, J. Puig-Pey, and A. Iglesias, “Particle swarm optimization for Bézier surface reconstruction,” in Computational Science—ICCS 2008, vol. 5102 of Lectures Notes in Computer Science, pp. 116–125, 2008.
[58]
A. Gálvez and A. Iglesias, “Particle swarm optimization for non-uniform rational B-spline surface reconstruction from clouds of 3D data points,” Information Sciences, vol. 192, pp. 174–192, 2012.
[59]
A. Gálvez, A. Iglesias, and J. Puig-Pey, “Iterative two-step genetic-algorithm-based method for efficient polynomial B-spline surface reconstruction,” Information Sciences, vol. 182, no. 1, pp. 56–76, 2012.
[60]
M. Sarfraz and S. A. Raza, “Capturing outline of fonts using genetic algorithms and splines,” in Proceedings of the 5th International Conference on Information Visualization (IV' 01), pp. 738–743, IEEE Computer Society Press, 2001.
[61]
F. Yoshimoto, M. Moriyama, and T. Harada, “Automatic knot adjustment by a genetic algorithm for data fitting with a spline,” in Proceedings of the International Conference on Shape Modeling, pp. 162–169, IEEE Computer Society Press, 1999.
[62]
F. Yoshimoto, T. Harada, and Y. Yoshimoto, “Data fitting with a spline using a real-coded genetic algorithm,” CAD Computer Aided Design, vol. 35, no. 8, pp. 751–760, 2003.
[63]
A. Gálvez, A. Iglesias, and A. Andreina, “Discrete Bézier curve fitting with artificial immune systems,” in Intelligent Computer Graphics 2012, vol. 441 of Studies in Computational Intelligence, pp. 59–75, 2013.
[64]
E. ülker and A. Arslan, “Automatic knot adjustment using an artificial immune system for B-spline curve approximation,” Information Sciences, vol. 179, no. 10, pp. 1483–1494, 2009.
[65]
X. Zhao, C. Zhang, B. Yang, and P. Li, “Adaptive knot placement using a GMM-based continuous optimization algorithm in B-spline curve approximation,” CAD Computer Aided Design, vol. 43, no. 6, pp. 598–604, 2011.
[66]
A. Gálvez and A. Iglesias, “Firey algorithm for polynomial Bézier surface parameterization,” Journal of Applied Mathematics, vol. 2013, Article ID 237984, 9 pages, 2013.
[67]
A. Gálvez and A. Iglesias, “Firey algorithm for explicit B-spline curve fitting to data points,” Mathematical Problems in Engineering, vol. 2013, Article ID 528215, 12 pages, 2013.
[68]
A. Gálvez and A. Iglesias, “A new iterative mutually-coupled hybrid GA-PSO approach for curve fitting in manufacturing,” Applied Soft Computing, vol. 13, no. 3, pp. 1491–1504, 2013.
[69]
A. Gálvez and A. Iglesias, “From nonlinear optimization to convex optimization through firey algorithm and indirect approach with applications to CAD/CAM,” The Scientific World Journal, vol. 2013, Article ID 283919, 10 pages, 2013.
[70]
M. Hoffmann and L. Várady, “Free-form surfaces for scattered data by neural networks,” Journal for Geometry and Graphics, vol. 2, no. 1, pp. 1–6, 1998.
[71]
J. Barhak and A. Fischer, “Parameterization and reconstruction from 3D scattered points based on neural network and PDE techniques,” IEEE Transactions on Visualization and Computer Graphics, vol. 7, no. 1, pp. 1–16, 2001.
[72]
E. Castillo, “Functional networks,” Neural Processing Letters, vol. 7, no. 3, pp. 151–159, 1998.
[73]
E. Castillo, A. Iglesias, and R. Ruiz-Cobo, Functional Equations in Applied Sciences, Elsevier Science, Amsterdam, The Netherlands, 2005.
[74]
E. Castillo and A. Iglesias, “Some characterizations of families of surfaces using functional equations,” ACM Transactions on Graphics, vol. 16, no. 3, pp. 296–318, 1997.
[75]
T. Kohonen, Self-Organization and Associative Memory, vol. 8 of Springer Series in Information Sciences, Springer, New York, NY, USA, 3rd edition, 1989.
[76]
T. Kohonen, Self-Organizing Maps, vol. 30 of Springer Series in Information Sciences, Springer, Berlin, Germany, 3rd edition, 2001.
[77]
M. Hoffmann, “Modified Kohonen neural network for surface reconstruction,” Publicationes Mathematicae, vol. 54, pp. 857–864, 1999.
[78]
W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling, Numerical Recipes, Cambridge University Press, Cambridge, UK, 2nd edition, 1986.
[79]
J. Puig-Pey, A. Gálvez, A. Iglesias, J. Rodríguez, P. Corcuera, and F. Gutiérrez, “Some applications of scalar and vector fields to geometric processing of surfaces,” Computers & Graphics, vol. 29, no. 5, pp. 723–729, 2005.
