# Hybrid Functional-Neural Approach for Surface Reconstruction

Authors: Andrés Iglesias; Akemi Gálvez
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

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.


---

## Body

## 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 connected information society era.In this paper, we are interested in one of the most critical steps of this process, namely, the construction of surfaces of the real objects from sets of digitized data points, a field usually calledsurface reconstruction. The preferred mathematical models for design and manufacturing are the free-form parametric surfaces [3, 8–16], because they are very flexible and can be readily modified by changing a small set of parameters. In this paper, we use NURBS surfaces, the most powerful (and most difficult to deal with) free-form parametric surfaces, which have become the standard for CAD/CAM data representation in industrial settings and in many other fields, from digital effects for movies in computer animation and advertisements to the design of characters in computer graphics and video games. In reverse engineering applications, data points are usually acquired through laser scanning and other digitizing devices and are, therefore, subjected to measurement noise, irregular sampling, and other artifacts [6, 7]. Consequently, a good fitting of data should be generally based on approximation schemes rather than interpolation [1, 13, 14, 17–19]. Because this is the typical case in many real-world industrial problems, in this paper we focus on the approximation scheme to a given set of noisy, irregularly sampled data points.Obtaining the best approximating surface in such cases is much more troublesome than it may seem at first sight. The main reasons are as follows.(i)
The NURBS surfaces depend on many different parameters (data parameters, knots, control points, and weights) that are strongly interconnected with each other, leading to a strongly nonlinear continuous optimization problem.
(ii)
It is also multivariate, as it typically involves a large number of unknown variables for a large number of data points, a case that happens very often in real-world examples.
(iii)
In addition, it is also overdetermined, because we expect to obtain the approximating surface with many fewer parameters than the number of data points.
(iv)
Finally, the problem is known to be multimodal; that is, the least-squares objective function can exhibit many local optima [20, 21], meaning that the problem might have several (global and/or local) good solutions.In conclusion, we have to solve a very difficult multimodal, multivariate, high-dimensional continuous nonlinear optimization problem. A number of methods have been proposed to solve this problem (see Section2 for details). Among them, those based on artificial intelligence techniques have received increasing attention during the last few years. Most of such methods rely on the artificial neural networks (ANN) formalism [22]. Since ANN methodology is actually inspired by the behavior of the human brain, it is able to reproduce some of its most typical features, such as the ability to learn from data. This explains why they have been so widely applied to data fitting problems.Although they are very popular, the ANN are however limited in many aspects. A major drawback is their inability to reproduce mathematically the functional structure of a given problem. This limitation can be overcome with the use of a new paradigm in artificial intelligence, the so-calledfunctional networks (FN) (see Section 4 for details). In short, functional networks are a generalization of the standard neural networks in which the scalar weights are replaced by neural functions. These neural functions can exhibit, in general, a multivariate character. Furthermore, different neurons can be associated with neural functions from different families of functions. These FN features allow us to reproduce exactly the functional structure of the problem by a careful choice of the functions involved, which can hereby be associated with one or several neurons of the network. This procedure yields a functional structure that is typically a replica of the underlying structure of the given problem.


### 1.1. Aims and Structure of the Paper

In this paper, we propose a hybrid artificial intelligence approach to solve the surface reconstruction problem. 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 take advantage of the remarkable properties mentioned in previous paragraph by introducing a new functional network, called NURBS functional network, whose topology is specially targeted to reproduce the functional structure of the NURBS surfaces. These neural and functional networks are then applied iteratively for further surface refinement. As it will be shown later on, the hybridization of these two networks provides us with a powerful computational approach to solve the surface reconstruction problem. To check the performance of our approach, it has been applied to two illustrative examples. Our experimental results show that the method performs very well, being able to reconstruct the approximating surface of the given set of data points with a high degree of accuracy.The structure of this paper is as follows: in Section2, previous work regarding the surface reconstruction problem is reported. Then, some basic concepts about NURBS surfaces and the optimization problem to be solved are given in Section 3. Section 4 describes the fundamentals of the functional networks along with their main components and the differences between neural and functional networks. The proposed hybrid functional-neural method for surface reconstruction with NURBS surfaces is described in detail in Section 5. Then, some illustrative examples of its application are reported in Section 6. A comparison of our approach with other ANN alternative methods is analyzed in detail in Section 7. The paper closes with the main conclusions of this contribution and our plans for future work in the field.


## 1.1. Aims and Structure of the Paper

In this paper, we propose a hybrid artificial intelligence approach to solve the surface reconstruction problem. 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 take advantage of the remarkable properties mentioned in previous paragraph by introducing a new functional network, called NURBS functional network, whose topology is specially targeted to reproduce the functional structure of the NURBS surfaces. These neural and functional networks are then applied iteratively for further surface refinement. As it will be shown later on, the hybridization of these two networks provides us with a powerful computational approach to solve the surface reconstruction problem. To check the performance of our approach, it has been applied to two illustrative examples. Our experimental results show that the method performs very well, being able to reconstruct the approximating surface of the given set of data points with a high degree of accuracy.The structure of this paper is as follows: in Section2, previous work regarding the surface reconstruction problem is reported. Then, some basic concepts about NURBS surfaces and the optimization problem to be solved are given in Section 3. Section 4 describes the fundamentals of the functional networks along with their main components and the differences between neural and functional networks. The proposed hybrid functional-neural method for surface reconstruction with NURBS surfaces is described in detail in Section 5. Then, some illustrative examples of its application are reported in Section 6. A comparison of our approach with other ANN alternative methods is analyzed in detail in Section 7. The paper closes with the main conclusions of this contribution and our plans for future work in the field.


## 2. Previous Work

Surface reconstruction has been a topic of increasing attention from the scientific community during the last 20 years, with outstanding applications in both theoretical and applied domains. Regarding the theoretical side, it is a remarkable subject in approximation theory [23, 24], statistics [25], numerical analysis [26, 27], geometric modeling [2, 8, 28], and computer-aided geometric design (CAGD) [5, 29]. In addition, there is a bulk of applications in several fields, such as computer-aided manufacturing (CAM) [6, 7], data visualization [30], cultural heritage preservation [31], virtual reality [32], medical imaging [33], and computer animation [34], to mention just a few.In general, surface reconstruction methods are classified in terms of the available input (2D slices, isoparametric curves, clouds of points, mixed information, etc.). For instance, authors in [35–39] address the problem of obtaining a surface model from a set of given cross-sections, a classical problem in medical science, biomedical engineering, and CAD/CAM. Other classical input data include isoparametric curves on the surface [40] and even mixed information, such as scattered points and contours [41–43] or isoparametric curves and data points [4, 5, 44].In most cases, however, the available information about the surface is typically a dense set of (usually unorganized) 3D data points obtained by using some sort of digitizing devices (see, e.g., [14, 45–48]). In that case, the reconstructed surface can be described using three different representations providing different levels of accuracy. The simplest one is given by the polygonal meshes, where the data points are used as vertices connected by lines (edges) that work together to create a 3D model, comprised of vertices, edges, and faces. Although it is the coarsest representation, it is also the most popular because of its simplicity, flexibility, and excellent performance with current graphical cards. Surface reconstruction methods with polygonal meshes can be found, for instance, in [30, 31, 47, 49–51] and references therein. The next level is given by the constructive solid geometry (CSG) models, where elementary geometries (such as spheres, boxes, cylinders, or cones) are combined in order to produce more elaborated shapes by applying some simple (Boolean) operators: union, intersection, and difference. This methodology works well but presents a low level of flexibility, being severely limited to very simple shapes. The most sophisticated and most accurate level consists of obtaining the real mathematical surface fitting the data points. This issue has been analyzed from several points of view, such as parametric methods [52], subdivision surfaces [53], function reconstruction [54, 55], implicit surfaces [48], and algebraic surfaces [56]. Other approaches are based on the application of metaheuristic techniques, which have been intensively applied to solve difficult optimization problems that cannot be tackled through traditional optimization algorithms. Recent schemes in this area involve particle swarm optimization [10, 57, 58], genetic algorithms [59–62], artificial immune systems [63, 64], estimation of distribution algorithms [65], firefly algorithm [66, 67], and hybrid techniques [68, 69].Artificial neural networks have also been applied to this problem [45, 70], mostly for arranging the input data in case of unorganized points. After this preprocessing step, any other classical surface reconstruction method operating on organized points is subsequently applied. A work using a combination of neural networks and partial differential equation (PDE) techniques for the parameterization and reconstruction of surfaces from 3D scattered points can be found in [71]. Two previous papers by the authors have also addressed this problem by using functional networks [4, 8], a powerful generalization of neural networks based on functional equations [72, 73]. Both works show, however, that the single application of functional networks is still unable to solve the general case. The work in [4] addresses the particular case of B-spline surface reconstruction when some additional information (isoparametric curves) is available in addition to the data points. The fitting surfaces are a generalization of the Gordon surfaces [40]. The work in [8] combines functional networks with genetic algorithms in order to solve the (much simpler) polynomial Bézier case. The approach presented here solves the general NURBS surface reconstruction problem based exclusively on neural and functional networks. To the best of our knowledge, no previous method is reported in the literature providing all these features.


## 3. Basic Concepts and Definitions

### 3.1. NURBS Surfaces

Let𝒮
=
{
s
0
,
s
1
,
s
2
,
…
,
s
r
-
1
,
s
r
}
⊂
[
a
,
b
] be a nondecreasing sequence of real numbers called knots. 𝒮 is called the knot vector. Without loss of generality, we can assume that [
a
,
b
]
=
[
0,1
]. The ith B-spline basis function  N
i
,
k
(
u
)  of order  k (or equivalently, degree k
-
1) is defined by the recurrence relations:
(1)
N
i
,
1
(
u
)
=
{
1
if
s
i
≤
u
<
s
i
+
1
0
otherwise
with i
=
0
,
…
,
r
-
1 and
(2)
N
i
,
k
(
u
)
=
u
-
s
i
s
i
+
k
-
1
-
s
i
N
i
,
k
-
1
(
u
)
+
s
i
+
k
-
u
s
i
+
k
-
s
i
+
1
N
i
+
1
,
k
-
1
(
u
)
for k
>
1. Note that ith B-spline basis function of order 1, N
i
,
1
(
u
), is a piecewise constant function with value 1 on the interval [
s
i
,
s
i
+
1
), called the support of N
i
,
1
(
u
), and zero elsewhere. This support either can be an interval or reduce to a point, as knots s
i and s
i
+
1 must not necessarily be different. If necessary, the convention 0
/
0
=
0 in (2) is applied. Any basis function of order k
>
1, N
i
,
k
(
u
), is a linear combination of two consecutive functions of order k
-
1, where the coefficients are linear polynomials in u, such that its order (and hence its degree) increases by 1. Simultaneously, its support is the union of the (partially overlapping) supports of the former basis functions of order k
-
1 and, consequently, it usually enlarges.With the same notation, given a set of three-dimensional points (calledcontrol points as they roughly determine the shape of the curve) {
P
i
j
}
i
=
0
,
…
,
m
;
j
=
0
,
…
,
n in a bidirectional net and two knot vectors 𝒮
=
{
s
0
,
s
1
,
s
2
,
…
,
s
r
-
1
,
s
r
} and 𝒯
=
{
t
0
,
t
1
,
…
,
t
h
-
1
,
t
h
}, a NURBS surface  S
(
u
,
v
)  of order  (
k
,
l
) (where NURBS stands for Non-Uniform Rational B-Spline) is a rational B-spline parametric surface given by
(3)
S
(
u
,
v
)
=
∑
i
=
0
m
∑
j
=
0
n
w
i
,
j
P
i
,
j
N
i
,
k
(
u
)
N
j
,
l
(
v
)
∑
i
=
0
m
∑
j
=
0
n
w
i
,
j
N
i
,
k
(
u
)
N
j
,
l
(
v
)
,
where the {
N
i
,
k
(
u
)
}
i and {
N
j
,
l
(
v
)
}
j are the B-spline basis functions of orders k and l, respectively, defined following (1) and (2), and {
w
i
,
j
}
i
,
j are nonnegative scalar values called weights associated with the control points {
P
i
,
j
}
i
,
j. Without loss of generality, parameters u, v can be assumed to take values on the interval [
0,1
]. For a proper definition of a NURBS surface in (3), the following relationships must hold (see [29]): r
=
m
+
k, h
=
n
+
l.In general, a NURBS surface does not interpolate any of its control points; the interpolation only occurs for nonperiodic knot vectors (in that case, the NURBS surface does interpolate the corner control points) [11, 29]. Since they are the most common in computer graphics and industrial domains, in this work we will consider the case of nonperiodic knot vectors. Note, however, that our method does not depend on the kind of knot vectors used for the approximating surfaces.


### 3.2. Surface Reconstruction Problem

In clear contrast with many previous methods, in this paper we focus on thegeneral surface reconstruction problem, which assumes that no other information about the problem is available beyond the data points. In particular, our problem can be stated as follows. Given a set of (usually irregularly sampled) noisy data points Q assumed to lie on an unknown surface U, construct, to the extent possible, a full mathematical representation of a surface model S that approximates U. Because of its remarkable applications in real-world engineering problems, we also demand such a mathematical representation to be a NURBS surface.Mathematically speaking, we assume that we are provided with a set of data points{
Q
α
,
β
}
α
=
1
,
…
,
M
;
β
=
1
,
…
,
N in ℝ
3, with M
,
N
⋙
r
,
h. Our goal is to obtain the NURBS surface S
(
u
,
v
) that fits the data points better in the discrete least-squares sense. To do so, we have to compute all the parameters of the approximating surface by minimizing the least-squares error, E, defined as the sum of squares of the residuals:
(4)
E
=
∑
α
=
1
M
‍
∑
β
=
1
N
‍
(
Q
α
,
β
-
∑
i
=
0
m
∑
j
=
0
n
w
i
,
j
P
i
,
j
N
i
,
k
(
u
α
)
N
j
,
l
(
v
β
)
∑
i
=
0
m
∑
j
=
0
n
w
i
,
j
N
i
,
k
(
u
α
)
N
j
,
l
(
v
β
)
)
2
.In the case of scattered data points{
Q
μ
}
μ
=
1
,
…
,
R, our method will work in a similar way by simply replacing the previous expression (4) by
(5)
E
=
∑
μ
=
1
R
‍
(
Q
μ
-
∑
i
=
0
m
∑
j
=
0
n
w
i
,
j
P
i
,
j
N
i
,
k
(
u
μ
)
N
j
,
l
(
v
μ
)
∑
i
=
0
m
∑
j
=
0
n
w
i
,
j
N
i
,
k
(
u
μ
)
N
j
,
l
(
v
μ
)
)
2
.The minimization of either (4) or (5) leads to the system of equations:
(6)
Q
v
=
M
·
P
v
,
where the symbol (
·
)
v denotes the vectorization operator of the given matrix and M in (6) is a matrix given by M
i
,
j
(
u
α
,
v
β
)
=
[
(
(
R
j
,
l
v
(
u
α
,
v
β
)
)
T
⊗
R
i
,
k
(
u
T
,
v
β
)
)
v
]
T, with u
=
(
u
1
,
…
,
u
M
). R
i
,
j
(
u
,
v
) is given as
(7)
R
i
,
j
(
u
,
v
)
=
w
i
,
j
N
i
,
k
(
u
)
N
j
,
l
(
v
)
∑
i
=
0
m
∑
j
=
0
n
w
i
,
j
N
i
,
k
(
u
)
N
j
,
l
(
v
)
i
=
0
,
…
,
m
;
j
=
0
,
…
,
n
while ⊗ and (
·
)
T represent the outer product operator and the transpose of a vector or matrix, respectively. The indices in (4)–(7) vary in the ranges of values indicated throughout the section.It is worthwhile to mention that since the lengths ofQ
v and P
v are, respectively, M
×
N and (
m
+
1
)
×
(
n
+
1
), the system (6) is overdetermined. Premultiplication of both sides by M
T yields
(8)
M
T
·
Q
v
=
M
T
·
M
·
P
v
=
Δ
·
P
v
,
where Δ
=
M
T
·
M. Note also that the tensor-product basis functions R
i
,
j
(
u
,
v
) are generally continuous and nonlinear, so the minimization of (8) leads to the continuous nonlinear optimization problem:
(9)
min
⁡
{
P
i
,
j
}
⊂
ℝ
3
;
{
w
i
,
j
}
≥
0
;
{
(
u
α
,
v
β
)
}

⊂

Dom
⁡
(
S
)
;
{
s
υ
}
,
{
t
ν
}

⊂

[
0,1
]
∥
M
T
·
Q
v
-
Δ
·
P
v
∥
2
,
where ∥
·
∥ represents the Euclidean norm.


## 3.1. NURBS Surfaces

Let𝒮
=
{
s
0
,
s
1
,
s
2
,
…
,
s
r
-
1
,
s
r
}
⊂
[
a
,
b
] be a nondecreasing sequence of real numbers called knots. 𝒮 is called the knot vector. Without loss of generality, we can assume that [
a
,
b
]
=
[
0,1
]. The ith B-spline basis function  N
i
,
k
(
u
)  of order  k (or equivalently, degree k
-
1) is defined by the recurrence relations:
(1)
N
i
,
1
(
u
)
=
{
1
if
s
i
≤
u
<
s
i
+
1
0
otherwise
with i
=
0
,
…
,
r
-
1 and
(2)
N
i
,
k
(
u
)
=
u
-
s
i
s
i
+
k
-
1
-
s
i
N
i
,
k
-
1
(
u
)
+
s
i
+
k
-
u
s
i
+
k
-
s
i
+
1
N
i
+
1
,
k
-
1
(
u
)
for k
>
1. Note that ith B-spline basis function of order 1, N
i
,
1
(
u
), is a piecewise constant function with value 1 on the interval [
s
i
,
s
i
+
1
), called the support of N
i
,
1
(
u
), and zero elsewhere. This support either can be an interval or reduce to a point, as knots s
i and s
i
+
1 must not necessarily be different. If necessary, the convention 0
/
0
=
0 in (2) is applied. Any basis function of order k
>
1, N
i
,
k
(
u
), is a linear combination of two consecutive functions of order k
-
1, where the coefficients are linear polynomials in u, such that its order (and hence its degree) increases by 1. Simultaneously, its support is the union of the (partially overlapping) supports of the former basis functions of order k
-
1 and, consequently, it usually enlarges.With the same notation, given a set of three-dimensional points (calledcontrol points as they roughly determine the shape of the curve) {
P
i
j
}
i
=
0
,
…
,
m
;
j
=
0
,
…
,
n in a bidirectional net and two knot vectors 𝒮
=
{
s
0
,
s
1
,
s
2
,
…
,
s
r
-
1
,
s
r
} and 𝒯
=
{
t
0
,
t
1
,
…
,
t
h
-
1
,
t
h
}, a NURBS surface  S
(
u
,
v
)  of order  (
k
,
l
) (where NURBS stands for Non-Uniform Rational B-Spline) is a rational B-spline parametric surface given by
(3)
S
(
u
,
v
)
=
∑
i
=
0
m
∑
j
=
0
n
w
i
,
j
P
i
,
j
N
i
,
k
(
u
)
N
j
,
l
(
v
)
∑
i
=
0
m
∑
j
=
0
n
w
i
,
j
N
i
,
k
(
u
)
N
j
,
l
(
v
)
,
where the {
N
i
,
k
(
u
)
}
i and {
N
j
,
l
(
v
)
}
j are the B-spline basis functions of orders k and l, respectively, defined following (1) and (2), and {
w
i
,
j
}
i
,
j are nonnegative scalar values called weights associated with the control points {
P
i
,
j
}
i
,
j. Without loss of generality, parameters u, v can be assumed to take values on the interval [
0,1
]. For a proper definition of a NURBS surface in (3), the following relationships must hold (see [29]): r
=
m
+
k, h
=
n
+
l.In general, a NURBS surface does not interpolate any of its control points; the interpolation only occurs for nonperiodic knot vectors (in that case, the NURBS surface does interpolate the corner control points) [11, 29]. Since they are the most common in computer graphics and industrial domains, in this work we will consider the case of nonperiodic knot vectors. Note, however, that our method does not depend on the kind of knot vectors used for the approximating surfaces.


## 3.2. Surface Reconstruction Problem

In clear contrast with many previous methods, in this paper we focus on thegeneral surface reconstruction problem, which assumes that no other information about the problem is available beyond the data points. In particular, our problem can be stated as follows. Given a set of (usually irregularly sampled) noisy data points Q assumed to lie on an unknown surface U, construct, to the extent possible, a full mathematical representation of a surface model S that approximates U. Because of its remarkable applications in real-world engineering problems, we also demand such a mathematical representation to be a NURBS surface.Mathematically speaking, we assume that we are provided with a set of data points{
Q
α
,
β
}
α
=
1
,
…
,
M
;
β
=
1
,
…
,
N in ℝ
3, with M
,
N
⋙
r
,
h. Our goal is to obtain the NURBS surface S
(
u
,
v
) that fits the data points better in the discrete least-squares sense. To do so, we have to compute all the parameters of the approximating surface by minimizing the least-squares error, E, defined as the sum of squares of the residuals:
(4)
E
=
∑
α
=
1
M
‍
∑
β
=
1
N
‍
(
Q
α
,
β
-
∑
i
=
0
m
∑
j
=
0
n
w
i
,
j
P
i
,
j
N
i
,
k
(
u
α
)
N
j
,
l
(
v
β
)
∑
i
=
0
m
∑
j
=
0
n
w
i
,
j
N
i
,
k
(
u
α
)
N
j
,
l
(
v
β
)
)
2
.In the case of scattered data points{
Q
μ
}
μ
=
1
,
…
,
R, our method will work in a similar way by simply replacing the previous expression (4) by
(5)
E
=
∑
μ
=
1
R
‍
(
Q
μ
-
∑
i
=
0
m
∑
j
=
0
n
w
i
,
j
P
i
,
j
N
i
,
k
(
u
μ
)
N
j
,
l
(
v
μ
)
∑
i
=
0
m
∑
j
=
0
n
w
i
,
j
N
i
,
k
(
u
μ
)
N
j
,
l
(
v
μ
)
)
2
.The minimization of either (4) or (5) leads to the system of equations:
(6)
Q
v
=
M
·
P
v
,
where the symbol (
·
)
v denotes the vectorization operator of the given matrix and M in (6) is a matrix given by M
i
,
j
(
u
α
,
v
β
)
=
[
(
(
R
j
,
l
v
(
u
α
,
v
β
)
)
T
⊗
R
i
,
k
(
u
T
,
v
β
)
)
v
]
T, with u
=
(
u
1
,
…
,
u
M
). R
i
,
j
(
u
,
v
) is given as
(7)
R
i
,
j
(
u
,
v
)
=
w
i
,
j
N
i
,
k
(
u
)
N
j
,
l
(
v
)
∑
i
=
0
m
∑
j
=
0
n
w
i
,
j
N
i
,
k
(
u
)
N
j
,
l
(
v
)
i
=
0
,
…
,
m
;
j
=
0
,
…
,
n
while ⊗ and (
·
)
T represent the outer product operator and the transpose of a vector or matrix, respectively. The indices in (4)–(7) vary in the ranges of values indicated throughout the section.It is worthwhile to mention that since the lengths ofQ
v and P
v are, respectively, M
×
N and (
m
+
1
)
×
(
n
+
1
), the system (6) is overdetermined. Premultiplication of both sides by M
T yields
(8)
M
T
·
Q
v
=
M
T
·
M
·
P
v
=
Δ
·
P
v
,
where Δ
=
M
T
·
M. Note also that the tensor-product basis functions R
i
,
j
(
u
,
v
) are generally continuous and nonlinear, so the minimization of (8) leads to the continuous nonlinear optimization problem:
(9)
min
⁡
{
P
i
,
j
}
⊂
ℝ
3
;
{
w
i
,
j
}
≥
0
;
{
(
u
α
,
v
β
)
}

⊂

Dom
⁡
(
S
)
;
{
s
υ
}
,
{
t
ν
}

⊂

[
0,1
]
∥
M
T
·
Q
v
-
Δ
·
P
v
∥
2
,
where ∥
·
∥ represents the Euclidean norm.


## 4. Functional Networks

Roughly speaking, afunctional network is a generalization of the standard neural network in which the scalar weights are replaced by neural functions. Functional networks were firstly introduced in 1998 by Castillo in [72] as a way to enhance the neural networks with new capabilities. Since then, they have been successfully applied to several problems in science and engineering. The interested reader is referred to [73, Chapter 9] for in-depth explanation about functional networks along with several illustrative examples and applications. In this section we describe the main components of a functional network. Differences between neural and functional networks are also discussed in this section.


### 4.1. Components of a Functional Network

As an explanatory example, Figure1(a) shows the functional network of the associative operation F between two real numbers; that is, function F satisfies
(10)
F
(
F
(
x
,
y
)
,
z
)
=
F
(
x
,
F
(
y
,
z
)
)
.
It can be proved that the general solution of this equation is given by [73]
(11)
F
(
x
,
y
)
=
f
-
1
[
f
(
x
)
+
f
(
y
)
]
,
where f
(
x
) is an arbitrary continuous and strictly monotonic function, which can be replaced only by c
f
(
x
), where c is an arbitrary constant. Such a solution can be represented by the functional network in Figure 1(b). Note that, because of the uniqueness (except arbitrary constants) of the solution, both networks do actually represent the same problem. In other words, the functional network in Figure 1(b), is equivalent to (but arguably simpler than) that in Figure 1(a). From Figure 1(b) the main components of a functional network become clear.The associativity functional network: (a) original network; (b) simplified network.
(a)
(b)(i) Several Layers of Storing Units(a) A Layer of Input Units. This first layer contains the input information. In this figure, this input layer consists of the units x and y.(b) A Set of Intermediate Layers of Storing Units. They are not neurons but units storing intermediate information. This set is optional and allows more than one neuron output to be connected to the same unit. In Figure 1(b), there are two intermediate layers of storing units, which are represented by small circles in black.(c) A Layer of Output Units. This last layer contains the output information. In Figure 1(b), this output layer is reduced to the unit u
=
f
-
1
(
f
(
x
)
+
f
(
y
)
).(ii) One or More Layers of Neurons or Computing Units. A neuron is a computing unit which evaluates a set of input values, coming from the previous layer, of input or intermediate units, and gives a set of output values to the next layer, of intermediate or output units. Neurons are represented by circles with the name of the corresponding neural function inside. For example, in Figure 1(b), we have three layers of neurons. The first one gives outputs of functions with one variable. The second layer exhibits the sum operator of its two inputs. The last layer computes the inverse of the first layer function applied to output of the previous layer.(iii) A Set of Directed Links. They connect the input or intermediate layers to its adjacent layer of neurons and neurons of one layer to its adjacent intermediate layers or to the output layer. Connections are represented by arrows, indicating the information flow direction. We remark here that information flows in only one direction, from the input layer to the output layer.All these elements together form thenetwork architecture or topology of the functional network, which defines the functional capabilities of the network.


### 4.2. Differences between Functional and Neural Networks

In next paragraphs, we discuss the differences between functional and neural networks and the advantages of using functional networks instead of standard neural networks.(1)
In neural networks, each neuron returns an outputy
=
f
(
∑
‍
w
i
k
x
k
) that depends only on the value ∑
‍
w
i
k
x
k, where x
1
,
x
2
,
…
,
x
n are the received inputs (see Figure 2(a)). Therefore, their neural functions have only one argument. In contrast, neural functions in functional networks can have several arguments, as shown in Figure 2(b).
(2)
In neural networks, the neural functions areunivariate: neurons can show different outputs but all of them represent the same values. In functional networks, the neural functions can be multivariate.
(3)
In a given functional network, the neural functions can bedifferent (such as functions f
1, f
2, and f
3 in Figure 2(b)), while in neural networks they are identical.
(4)
In neural networks, there are weights, which must be learned. These weights do not appear in functional networks, where neural functions are learned instead.
(5)
In neural networksthe neuron outputs are different, while in functional networks neuron outputs can be coincident. This fact leads to a set of functional equations, which have to be solved [73, 74]. These functional equations impose strong constraints leading to a considerable reduction in the degrees of freedom of the neural functions. In most cases, this implies that neural functions can be reduced in dimension or expressed as functions of smaller dimensions.Differences between (a) neural networks and (b) functional networks.
(a)
(b)All these features show that the functional networks exhibit more interesting possibilities than the neural networks. This implies that some problems can be solved more efficiently by using functional networks instead of neural networks.


## 4.1. Components of a Functional Network

As an explanatory example, Figure1(a) shows the functional network of the associative operation F between two real numbers; that is, function F satisfies
(10)
F
(
F
(
x
,
y
)
,
z
)
=
F
(
x
,
F
(
y
,
z
)
)
.
It can be proved that the general solution of this equation is given by [73]
(11)
F
(
x
,
y
)
=
f
-
1
[
f
(
x
)
+
f
(
y
)
]
,
where f
(
x
) is an arbitrary continuous and strictly monotonic function, which can be replaced only by c
f
(
x
), where c is an arbitrary constant. Such a solution can be represented by the functional network in Figure 1(b). Note that, because of the uniqueness (except arbitrary constants) of the solution, both networks do actually represent the same problem. In other words, the functional network in Figure 1(b), is equivalent to (but arguably simpler than) that in Figure 1(a). From Figure 1(b) the main components of a functional network become clear.The associativity functional network: (a) original network; (b) simplified network.
(a)
(b)(i) Several Layers of Storing Units(a) A Layer of Input Units. This first layer contains the input information. In this figure, this input layer consists of the units x and y.(b) A Set of Intermediate Layers of Storing Units. They are not neurons but units storing intermediate information. This set is optional and allows more than one neuron output to be connected to the same unit. In Figure 1(b), there are two intermediate layers of storing units, which are represented by small circles in black.(c) A Layer of Output Units. This last layer contains the output information. In Figure 1(b), this output layer is reduced to the unit u
=
f
-
1
(
f
(
x
)
+
f
(
y
)
).(ii) One or More Layers of Neurons or Computing Units. A neuron is a computing unit which evaluates a set of input values, coming from the previous layer, of input or intermediate units, and gives a set of output values to the next layer, of intermediate or output units. Neurons are represented by circles with the name of the corresponding neural function inside. For example, in Figure 1(b), we have three layers of neurons. The first one gives outputs of functions with one variable. The second layer exhibits the sum operator of its two inputs. The last layer computes the inverse of the first layer function applied to output of the previous layer.(iii) A Set of Directed Links. They connect the input or intermediate layers to its adjacent layer of neurons and neurons of one layer to its adjacent intermediate layers or to the output layer. Connections are represented by arrows, indicating the information flow direction. We remark here that information flows in only one direction, from the input layer to the output layer.All these elements together form thenetwork architecture or topology of the functional network, which defines the functional capabilities of the network.


## 4.2. Differences between Functional and Neural Networks

In next paragraphs, we discuss the differences between functional and neural networks and the advantages of using functional networks instead of standard neural networks.(1)
In neural networks, each neuron returns an outputy
=
f
(
∑
‍
w
i
k
x
k
) that depends only on the value ∑
‍
w
i
k
x
k, where x
1
,
x
2
,
…
,
x
n are the received inputs (see Figure 2(a)). Therefore, their neural functions have only one argument. In contrast, neural functions in functional networks can have several arguments, as shown in Figure 2(b).
(2)
In neural networks, the neural functions areunivariate: neurons can show different outputs but all of them represent the same values. In functional networks, the neural functions can be multivariate.
(3)
In a given functional network, the neural functions can bedifferent (such as functions f
1, f
2, and f
3 in Figure 2(b)), while in neural networks they are identical.
(4)
In neural networks, there are weights, which must be learned. These weights do not appear in functional networks, where neural functions are learned instead.
(5)
In neural networksthe neuron outputs are different, while in functional networks neuron outputs can be coincident. This fact leads to a set of functional equations, which have to be solved [73, 74]. These functional equations impose strong constraints leading to a considerable reduction in the degrees of freedom of the neural functions. In most cases, this implies that neural functions can be reduced in dimension or expressed as functions of smaller dimensions.Differences between (a) neural networks and (b) functional networks.
(a)
(b)All these features show that the functional networks exhibit more interesting possibilities than the neural networks. This implies that some problems can be solved more efficiently by using functional networks instead of neural networks.


## 5. Our Method

In this section, we describe the proposed method for solving the surface reconstruction problem indicated in Section3.2. Firstly, a general overview of the method is presented. Then, each step of the method is discussed in detail.


### 5.1. Overview of the Method

The graphical workflow in Figure3 summarizes the main steps of our method. The initial input consists of a set of irregularly sampled noisy 3D data points assumed to lie on an unknown surface. The goal is to obtain the NURBS surface that approximates these data points optimally. To this purpose, we need to solve two important subproblems: data parameterization and surface approximation. To address data parameterization, we firstly perform a principal component analysis (PCA) to obtain a parametric plane that accounts for the variability of data. Then, the data points are projected onto that parametric plane. A 2D surface parameterization is subsequently obtained by applying a Kohonen neural network to the set of projected 2D data points. Then, we apply our NURBS functional network to compute all other parameters of the NURBS surface approximating the data points for this initial parameterization. We call that surface a base surface. The next step consists of computing the fitting error for the approximating surface. Finally, the data points are projected onto the new base surface in order to yield a new (more accurate) parameterization. All previous steps are repeated iteratively until a stopping criterion is reached. Usual stopping criteria are that the fitting error becomes smaller than a given threshold value or that successive iterations of this reconstruction pipeline no longer improve current solutions.Figure 3
Graphical workflow of the proposed method.


### 5.2. Data Parameterization

The parameterization step consists of establishing the relationships among the data points in the surface parametric domain. This process is essential for a good fitting of data points. Some standard procedures are given by the uniform, chord length and centripetal parameterizations. However, these methods are only suitable for data points distributed in a uniform grid and tend to fail for unorganized, irregularly sampled data. An alternative procedure is based on the idea of projecting the data points onto an additional surface, usually called base surface, reflecting the distribution of data points and then computing a parameterization by using the projected 2D points. The simplest case of this approach consists of using a parametric plane [11], usually orthogonal to the main viewing direction of the digitizing device. A better alternative is to use a suitable 3D surface for data projection [14], usually a coarse approximation of final fitting surface, which is expected to be modified by successive improvements of this initial surface.In our method, we combine these ideas to develop a refinement process in iterative fashion. At the initial stage, we project the data points onto a parametric plane reflecting the variability of data. This parametric plane is computed by using the principal component analysis (PCA), a very popular descriptive technique in data analysis and many other fields. PCA is a powerful statistical method aimed at performing dimensionality reduction by using the analysis of the correlation of data. A great advantage of this method is its nonparametric nature, meaning that it does not require any parameter tuning in order to get an output. Furthermore, the answer is unique and available regardless of the way the data has been recorded or obtained. Other main reasons for our choice are that PCA is very efficient at preserving distances between the points and each principal component has the highest variance possible under the constraint that it is uncorrelated with preceding components. In fact, the first principal component corresponds to a line passing through the multidimensional mean. It also minimizes the sum of squares of the distances to the points from that line. Because of these properties, the parametric plane obtained by PCA is very adequate for the initial 2D projection.Projected 2D points are then used for an initial surface parameterization by applying a Kohonen neural network (also called self-organizing map (SOM) neural network). This is a very popular artificial neural network for unsupervised learning. The interested reader is referred to the nice books in [75, 76] for a comprehensive overview about the Kohonen neural network, its fundamentals and mathematical basis, along with the most important variants and modifications and several interesting applications.Algorithm 1.
Kohonen neural network for 2D data parameterization.(1)
Initialize positionΨ of all neurons Φ with random values within the surface boundaries.
(2)
Initialize the weightsσ
i
,
j randomly around the centroid of the input space.
(3)
Pick a new input sampleQ
δ.
(4)
Compute(12)
d
j
=
∑
i
=
1
R
(
Ψ
i
(
δ
)
-
σ
i
,
j
(
δ
)
)
2
.
(5)
Select the active neuronγ for which d
γ
=
min
⁡
i
=
1
,
…
,
R
(
d
i
). The winner is the closest active neuron to the sample data Q
δ, with parametric coordinates (
i
~
,
j
~
).
(6)
Compute the neighborhood of neuronγ as follows. The radius ρ is given by
(13)
ρ
(
γ
)
=
R
2
e
[
∑
i
=
1
δ
(
1
/
10
+
i
/
1
0
4
)
]
.
The bubble neighborhood of the winner neuron is defined as all neurons at positions(
i
,
j
) such that
(14)
|
i
-
i
~
|
+
|
j
-
j
~
|
<
ρ
(
1
-
δ
θ
)
,
whereθ is the run length.
(7)
Update the weight of neuronγ and all neurons in its neighborhood as
(15)
σ
i
,
j
(
δ
+
1
)
=
σ
i
,
j
(
δ
)
+
η
(
δ
)
(
Ψ
i
(
δ
)
-
σ
i
,
j
(
δ
)
)
with(16)
η
(
δ
)
=
ζ
δ
1
2
π
e
-
δ
2
/
2
,
where the learning rateζ
δ is given by
(17)
ζ
δ
=
1
-
(
1
-
ζ
0
(
1
-
δ
θ
)
)
σ
δ
.
(8)
Incrementδ.
(9)
Repeat the steps(
3
)
–
(
8
) until δ reaches the limit value.A very remarkable feature of the Kohonen neural network is that it incorporates a neighborhood function to preserve the topological properties of the input space [75]. This property is very useful to generate a 2D grid for parameterization, where the neurons represent the grid nodes. The neural network is trained by using the projected 2D data so that its topology eventually reflects their shape and neighborhood relations. To this purpose, each neuron contains geometrical information about the coordinates of the associated node and the topological relations with its neighbors. It is important to remark that the connections among the neurons do not change during the training stage; instead, the changes occur on the geometrical values stored in the neurons. In other words, the network performs a topological ordering of the competitive neurons such that the neighboring neurons represent clusters in the two-dimensional space. Eventually, the weights will specify cluster centers whose distribution approximates the distribution of data points and hence a suitable 2D parameterization. Because of these good properties, the Kohonen neural network has already been used in several ways for data parameterization in some previous works [49, 70, 71, 77]. The algorithm used in this paper combines some of the best features of previous methods. It is briefly summarized in Algorithm 1.


### 5.3. Surface Fitting

A major property of functional networks is their ability to reproduce the functional structure of the underlying mathematical function of the data points. In this paper, we introduce a new functional network (depicted in Figure4) especially designed to reproduce the functional structure of NURBS surfaces: the NURBS functional network. Its workflow can be traced graphically by proceeding upwardly in Figure 4: given the surface parameter values u and v and two orders k and l, what this functional network essentially does is to compute the values of the basis functions N
i
k at u and N
j
l at v and then the bivariate tensor-product basis functions N
i
k
(
u
)
N
j
l
(
v
), (
i
=
0
,
…
,
m
;
j
=
0
,
…
,
n
). Each bivariate basis function is then multiplied twice, firstly by the scalar weight w
i
,
j and then by such a weight and its associated vector weight P
i
,
j. Summation on indices i and j is applied to both expressions to obtain the numerator and denominator of (3), to which the quotient operator is subsequently applied. Note that two different (scalar and vector) time operators are considered, to account for the multiplication by w
i
,
j and P
i
,
j, respectively. Note also that those vectors P
i
,
j play the role of weights of the neural functions as well, with the meaning that a functional network with d-dimensional vectors as weights can be understood as d parallel functional networks with scalar weights. Note finally that the first three layers of this functional network apply functions to either the same or independent arguments of the previous layer, so NURBS functional networks are well suited for partial bottom-up parallelization.Figure 4
Graphical representation of the NURBS functional network.Now, we use the surface parameterization obtained in previous steps to compute an approximating surface to the data points. This functional network is trained by supervised learning in which couples of input-output valuesD
=
{
(
I
i
,
O
i
)
∣
i
=
1
,
…
,
R
}, corresponding to the surface parameters {
(
u
μ
,
v
μ
)
}
μ and their associated data points Q
μ, are presented to the network. Unlike ANN, where the neuron functions are assumed to be fixed and known and only the weights are learned, in functional networks the functions are learned during the structural learning (which obtains the simplified network and functional structures) and estimated during the parametric learning (which consists of obtaining the optimal neuron function from a given family). In our case, the structural learning corresponds to the topology of the NURBS functional network, where the input data are the order (
k
,
l
) and the length (
r
,
h
) of the knot vectors of the approximating surface. These values determine the number of neurons in each layer of the functional network.The parametric learning concerns the estimation of the neuron functions. It is usually accomplished by considering linear combinations of given functional families and estimating the associated parameters from the available data. For our choice of B-spline basis functions during the structural learning, the parametric learning is required to determine the scalar and vector weights of our NURBS functional network. Vector weights are learned by using expression (8) where Δ is a symmetric square matrix. This system is solved by using the singular value decomposition (SVD), which provides the best numerical answer for the minimization problem in (9) in those cases in which the exact solution is not possible (see [78] for details). Finally, the scalar weights are obtained by least-squares minimization of expression (9), where all other relevant parameters of this minimization problem have already been obtained as described in previous steps.


### 5.4. Surface Refinement

Once the approximating surface is obtained, the initial parametric plane used for data parameterization is replaced by this approximating surface, which becomes the new base surface. Data points are then projected onto this base surface by computing the nearest point on the surface to each 3D data point by following the procedure indicated in [79]. A new data parameterization and surface fitting steps are computed according to Sections 5.2 and 5.3, respectively. The resulting fitting surface becomes the new base surface and so on. In general, this procedure yields a more refined (i.e., more accurate) fitting surface to data points.This process is repeated iteratively until a stopping criterion is reached. Usual stopping criteria are that the fitting error becomes smaller than a given threshold value or that successive iterations of this reconstruction pipeline no longer improve current solutions. In the former case, we assume that an error threshold value is provided as an input of the problem (as it usually happens in many industrial problems) and we compute the fitting error according to either (4) or (5). In the latter case, we compare the fitting error between successive iterations, and the process is stopped when no further improvement is achieved.


## 5.1. Overview of the Method

The graphical workflow in Figure3 summarizes the main steps of our method. The initial input consists of a set of irregularly sampled noisy 3D data points assumed to lie on an unknown surface. The goal is to obtain the NURBS surface that approximates these data points optimally. To this purpose, we need to solve two important subproblems: data parameterization and surface approximation. To address data parameterization, we firstly perform a principal component analysis (PCA) to obtain a parametric plane that accounts for the variability of data. Then, the data points are projected onto that parametric plane. A 2D surface parameterization is subsequently obtained by applying a Kohonen neural network to the set of projected 2D data points. Then, we apply our NURBS functional network to compute all other parameters of the NURBS surface approximating the data points for this initial parameterization. We call that surface a base surface. The next step consists of computing the fitting error for the approximating surface. Finally, the data points are projected onto the new base surface in order to yield a new (more accurate) parameterization. All previous steps are repeated iteratively until a stopping criterion is reached. Usual stopping criteria are that the fitting error becomes smaller than a given threshold value or that successive iterations of this reconstruction pipeline no longer improve current solutions.Figure 3
Graphical workflow of the proposed method.


## 5.2. Data Parameterization

The parameterization step consists of establishing the relationships among the data points in the surface parametric domain. This process is essential for a good fitting of data points. Some standard procedures are given by the uniform, chord length and centripetal parameterizations. However, these methods are only suitable for data points distributed in a uniform grid and tend to fail for unorganized, irregularly sampled data. An alternative procedure is based on the idea of projecting the data points onto an additional surface, usually called base surface, reflecting the distribution of data points and then computing a parameterization by using the projected 2D points. The simplest case of this approach consists of using a parametric plane [11], usually orthogonal to the main viewing direction of the digitizing device. A better alternative is to use a suitable 3D surface for data projection [14], usually a coarse approximation of final fitting surface, which is expected to be modified by successive improvements of this initial surface.In our method, we combine these ideas to develop a refinement process in iterative fashion. At the initial stage, we project the data points onto a parametric plane reflecting the variability of data. This parametric plane is computed by using the principal component analysis (PCA), a very popular descriptive technique in data analysis and many other fields. PCA is a powerful statistical method aimed at performing dimensionality reduction by using the analysis of the correlation of data. A great advantage of this method is its nonparametric nature, meaning that it does not require any parameter tuning in order to get an output. Furthermore, the answer is unique and available regardless of the way the data has been recorded or obtained. Other main reasons for our choice are that PCA is very efficient at preserving distances between the points and each principal component has the highest variance possible under the constraint that it is uncorrelated with preceding components. In fact, the first principal component corresponds to a line passing through the multidimensional mean. It also minimizes the sum of squares of the distances to the points from that line. Because of these properties, the parametric plane obtained by PCA is very adequate for the initial 2D projection.Projected 2D points are then used for an initial surface parameterization by applying a Kohonen neural network (also called self-organizing map (SOM) neural network). This is a very popular artificial neural network for unsupervised learning. The interested reader is referred to the nice books in [75, 76] for a comprehensive overview about the Kohonen neural network, its fundamentals and mathematical basis, along with the most important variants and modifications and several interesting applications.Algorithm 1.
Kohonen neural network for 2D data parameterization.(1)
Initialize positionΨ of all neurons Φ with random values within the surface boundaries.
(2)
Initialize the weightsσ
i
,
j randomly around the centroid of the input space.
(3)
Pick a new input sampleQ
δ.
(4)
Compute(12)
d
j
=
∑
i
=
1
R
(
Ψ
i
(
δ
)
-
σ
i
,
j
(
δ
)
)
2
.
(5)
Select the active neuronγ for which d
γ
=
min
⁡
i
=
1
,
…
,
R
(
d
i
). The winner is the closest active neuron to the sample data Q
δ, with parametric coordinates (
i
~
,
j
~
).
(6)
Compute the neighborhood of neuronγ as follows. The radius ρ is given by
(13)
ρ
(
γ
)
=
R
2
e
[
∑
i
=
1
δ
(
1
/
10
+
i
/
1
0
4
)
]
.
The bubble neighborhood of the winner neuron is defined as all neurons at positions(
i
,
j
) such that
(14)
|
i
-
i
~
|
+
|
j
-
j
~
|
<
ρ
(
1
-
δ
θ
)
,
whereθ is the run length.
(7)
Update the weight of neuronγ and all neurons in its neighborhood as
(15)
σ
i
,
j
(
δ
+
1
)
=
σ
i
,
j
(
δ
)
+
η
(
δ
)
(
Ψ
i
(
δ
)
-
σ
i
,
j
(
δ
)
)
with(16)
η
(
δ
)
=
ζ
δ
1
2
π
e
-
δ
2
/
2
,
where the learning rateζ
δ is given by
(17)
ζ
δ
=
1
-
(
1
-
ζ
0
(
1
-
δ
θ
)
)
σ
δ
.
(8)
Incrementδ.
(9)
Repeat the steps(
3
)
–
(
8
) until δ reaches the limit value.A very remarkable feature of the Kohonen neural network is that it incorporates a neighborhood function to preserve the topological properties of the input space [75]. This property is very useful to generate a 2D grid for parameterization, where the neurons represent the grid nodes. The neural network is trained by using the projected 2D data so that its topology eventually reflects their shape and neighborhood relations. To this purpose, each neuron contains geometrical information about the coordinates of the associated node and the topological relations with its neighbors. It is important to remark that the connections among the neurons do not change during the training stage; instead, the changes occur on the geometrical values stored in the neurons. In other words, the network performs a topological ordering of the competitive neurons such that the neighboring neurons represent clusters in the two-dimensional space. Eventually, the weights will specify cluster centers whose distribution approximates the distribution of data points and hence a suitable 2D parameterization. Because of these good properties, the Kohonen neural network has already been used in several ways for data parameterization in some previous works [49, 70, 71, 77]. The algorithm used in this paper combines some of the best features of previous methods. It is briefly summarized in Algorithm 1.


## 5.3. Surface Fitting

A major property of functional networks is their ability to reproduce the functional structure of the underlying mathematical function of the data points. In this paper, we introduce a new functional network (depicted in Figure4) especially designed to reproduce the functional structure of NURBS surfaces: the NURBS functional network. Its workflow can be traced graphically by proceeding upwardly in Figure 4: given the surface parameter values u and v and two orders k and l, what this functional network essentially does is to compute the values of the basis functions N
i
k at u and N
j
l at v and then the bivariate tensor-product basis functions N
i
k
(
u
)
N
j
l
(
v
), (
i
=
0
,
…
,
m
;
j
=
0
,
…
,
n
). Each bivariate basis function is then multiplied twice, firstly by the scalar weight w
i
,
j and then by such a weight and its associated vector weight P
i
,
j. Summation on indices i and j is applied to both expressions to obtain the numerator and denominator of (3), to which the quotient operator is subsequently applied. Note that two different (scalar and vector) time operators are considered, to account for the multiplication by w
i
,
j and P
i
,
j, respectively. Note also that those vectors P
i
,
j play the role of weights of the neural functions as well, with the meaning that a functional network with d-dimensional vectors as weights can be understood as d parallel functional networks with scalar weights. Note finally that the first three layers of this functional network apply functions to either the same or independent arguments of the previous layer, so NURBS functional networks are well suited for partial bottom-up parallelization.Figure 4
Graphical representation of the NURBS functional network.Now, we use the surface parameterization obtained in previous steps to compute an approximating surface to the data points. This functional network is trained by supervised learning in which couples of input-output valuesD
=
{
(
I
i
,
O
i
)
∣
i
=
1
,
…
,
R
}, corresponding to the surface parameters {
(
u
μ
,
v
μ
)
}
μ and their associated data points Q
μ, are presented to the network. Unlike ANN, where the neuron functions are assumed to be fixed and known and only the weights are learned, in functional networks the functions are learned during the structural learning (which obtains the simplified network and functional structures) and estimated during the parametric learning (which consists of obtaining the optimal neuron function from a given family). In our case, the structural learning corresponds to the topology of the NURBS functional network, where the input data are the order (
k
,
l
) and the length (
r
,
h
) of the knot vectors of the approximating surface. These values determine the number of neurons in each layer of the functional network.The parametric learning concerns the estimation of the neuron functions. It is usually accomplished by considering linear combinations of given functional families and estimating the associated parameters from the available data. For our choice of B-spline basis functions during the structural learning, the parametric learning is required to determine the scalar and vector weights of our NURBS functional network. Vector weights are learned by using expression (8) where Δ is a symmetric square matrix. This system is solved by using the singular value decomposition (SVD), which provides the best numerical answer for the minimization problem in (9) in those cases in which the exact solution is not possible (see [78] for details). Finally, the scalar weights are obtained by least-squares minimization of expression (9), where all other relevant parameters of this minimization problem have already been obtained as described in previous steps.


## 5.4. Surface Refinement

Once the approximating surface is obtained, the initial parametric plane used for data parameterization is replaced by this approximating surface, which becomes the new base surface. Data points are then projected onto this base surface by computing the nearest point on the surface to each 3D data point by following the procedure indicated in [79]. A new data parameterization and surface fitting steps are computed according to Sections 5.2 and 5.3, respectively. The resulting fitting surface becomes the new base surface and so on. In general, this procedure yields a more refined (i.e., more accurate) fitting surface to data points.This process is repeated iteratively until a stopping criterion is reached. Usual stopping criteria are that the fitting error becomes smaller than a given threshold value or that successive iterations of this reconstruction pipeline no longer improve current solutions. In the former case, we assume that an error threshold value is provided as an input of the problem (as it usually happens in many industrial problems) and we compute the fitting error according to either (4) or (5). In the latter case, we compare the fitting error between successive iterations, and the process is stopped when no further improvement is achieved.


## 6. Illustrative Examples

Our method has been tested with several examples of different clouds of data points. To keep the paper at manageable size, we discuss here two of them. Examples in this paper are shown in Figures5-6. For each example, two different pictures are displayed: at (a), we show the original cloud of input data points, represented as small red points; at (b), the best approximating NURBS surface, is shown as obtained with our functional-neural approach. Our input consists of sets of irregularly sampled data points (this fact can readily be seen from simple visual inspection of the point clouds at (a)), which are also affected by measurement noise of a signal-to-noise ratio of 15 : 1 in all examples. In this paper, a fitting error threshold value ϵ
=
1
0
-
3 is considered. The other relevant parameters of the approximating NURBS surfaces are reported in Table 1, where the examples are arranged in rows. For each example, the following data are arranged in columns: number of data points, order of the approximating NURBS surface, length of knot vectors, and number of iterations required to obtain the fitting surface with a fitting error below the given threshold.Table 1
Number of data points and input parameters of the approximating NURBS surfaces for the two examples discussed in this paper.
Example
Number of  data points
Order
(r
,
h)
Iterations
Mask
11830
(4, 4)
(17, 14)
2
Umbrella
8926
(3, 3)
(6, 27)
4Mask example: (a) original data points; (b) fitting surface.
(a)
(b)Umbrella example: (a) original data points; (b) fitting surface.
(a)
(b)A simple visual inspection of the figures clearly shows that our method yields a very good approximating surface to data points in all cases. The low number of iterations required to obtain the fitting surface for the given threshold also confirms the good behavior of the method. From these examples and many others not reported here for the sake of brevity, we conclude that the presented method performs very well, with remarkable capability to provide a satisfactory solution to the general reconstruction problem with NURBS surfaces.Regarding the implementation issues, all computations in this paper have been performed on a 2.9 GHz. Intel Core i7 processor with 8 GB. of RAM. The source code has been implemented by the authors in the native programming language of the popular scientific programMatlab, version 2010b.


## 7. Comparison with Other Approaches

In this section, we compare the presented method with other alternative approaches for surface reconstruction based on neural networks. A careful revision of the literature in the field gives six previous contributions in the field, the works in [4, 8, 49, 70, 71, 77]. This small number is a clear indication of the difficulty and originality of the present work.Comparative results of these methods are summarized in Table2. The different methods are arranged in rows and sorted by year of publication. For each reported method, the columns give a brief description about its main features. Columns 2, 4, and 6 give a binary answer to three different questions: whether or not the indicated method provides algorithms for the subproblems of data parameterization, surface fitting, and support for NURBS surfaces, respectively. Answer true is marked with a check (✓), otherwise with symbol (×). Wherever a positive answer is found, a short description about the specific techniques incorporated in that method for the reported subproblem is given in columns 3 and 5, respectively. Note that all methods except [4, 8] address the data parameterization subproblem with a Kohonen neural network, and all methods except [70, 77] provide a procedure to compute the approximating surface, either as a Bézier surface [8], a B-spline surface [4, 71], or a polygonal mesh [49]. The works in [70, 77] assume that any traditional surface fitting technique will be used for this particular sub-problem.Table 2
Comparison of the proposed method with other alternative methods based on neural networks for the surface reconstruction problem.
Author, year,  and  reference
Data parameterization
Method used
Surface fitting
Method used
NURBS supported?
Hoffmann and Várady  (1998) [70]
✓
Kohonen neural  network
×
×
Yu (1999) [49]
✓
Kohonen neural  network
✓
Polygonal mesh  (edge swap)
×
Hoffmann (1999) [77]
✓
Modified Kohonen neural network
×
×
Barhak and  Fischer (2001) [71]
✓
(i)  Kohonen neural  network (ii) Partial differential  equations (PDE)
✓
(i) Gradient descent algorithm (GDA)(ii) Random surface error correction (RSEC)
×
Iglesias et al.  (2004) [4]
×
✓
Tensor-product  functional network
×
Gálvez et al.  (2007) [8]
✓
Genetic algorithms
✓
Functional network
×
This method (2013)
✓
Kohonen neural network
✓
NURBS functional  network
✓The most important difference of this method with respect to alternative approaches is that previous methods do not provide support for NURBS surfaces (see column 6 in Table2). On the contrary, NURBS surfaces are fully supported in our method. In fact, the examples shown in the paper are more difficult to reconstruct through simple polynomial surfaces and require a larger number of parameters. In clear contrast, our method requires only a small number of parameters. Furthermore, the solution is reached with a small number of iterations. To the best of our knowledge, this is the first neural-based approach providing full support for all steps of the general surface reconstruction problem by using NURBS surfaces.


## 8. Conclusions and Future Work

This paper proposes a new hybrid functional-neural approach to solve the surface reconstruction problem. In our approach, we combine two powerful artificial intelligence paradigms: the popular Kohonen neural network to address the data parameterization problem and a new functional network, called NURBS functional network, to reproduce the functional structure of the NURBS surfaces. These neural and functional networks are then applied iteratively for further surface refinement. The hybridization of these two networks provides us with a powerful computational approach to solve the surface reconstruction problem. The performance of our approach has been tested by its application to two illustrative examples. Our results show that the method performs very well, being able to reconstruct the approximating surface of the given set of data points with a high degree of accuracy and a low number of iterations.The main limitation of this approach is that it requires some initial input such as the order of the approximating NURBS surface and the length of knot vectors, which are strongly dependent on the particular set of data points. Consequently, their optimal values might be difficult to choose for end users, thus preventing the method for automatic, human-independent reconstruction. This limitation opens the door for future research in the area in order to develop efficient algorithms for automatic determination of those optimal values. Another important limitation of the method occurs when the data points cannot be unambiguously projected onto the base surface. This problem can arise with closed surfaces often represented in implicit form. In those cases, the PCA method might fail to extract the real tendency of data. We are currently working on new strategies to overcome this problem. Future work also includes the extension of this approach to other kinds of approximating surfaces as well as the possible application of this methodology to some interesting industrial problems.



---

*Source: 351648-2014-01-16.xml*