BleamCard: the first augmented reality card. Get your own on Indiegogo!

Parametric Models of Function

As it will be seen in the rest of this document, the vast majority of the problems treated in this thesis may be cast into parameter estimation problems. The fundamental concepts underlying such problems will be detailed in chapter 3. For now, let us just say that parameter estimation problems consists in finding the parameters of a parametric model so that the resulting function is `close to' a given set of data points. In a nutshell, a parametric model of function is a function whose exact behaviour is controlled by a set of parameters. For instance, a polynomial can be considered as a parametric model of function with the polynomial coefficients as parameters. A more precise definition of the parametric model of function will be given in section 3.1.1.1. In this section, we detail some particular but generic parametric models of function which are the ones mostly used in this document. Although we do not pretend to be fully exhaustive, we spend time in explaining the basics on splines and B-splines. The interested reader can deepen this topic with this readings (61,57,118,67). We also present other useful parametric models such as rational splines and radial basis functions.

Splines

The word spline is a generic term that designates a parametric model of function. This word has been used in many contexts (computer aided geometric design, approximation theory, computer vision) with a meaning that slightly varies from one domain to the other. In this section, we first fix the meaning of the word spline as we understand it in this document. We then give the basic mathematical definition of a mono-dimensional spline. We also give the fundamental properties of such objects.

Historical note.

The term spline originally designated a physical object used to draw smooth curves. It was widely used by engineers and architects to craft blue prints. It was made of a flexible strip that was fixed at some points. An illustration of such splines is given in figure 2.10. Of course, in this document we will be more interested in the mathematical form of the splines than in their physical counterparts.

Figure 2.10: An historical spline (credits: Pearson Scott Foresman).

General definition.

In its most general definition, a spline is a piecewise polynomial function. Note that this definition is independent of any particular form. For instance, the B-splines (see section 2.3.2) are just a particular representation of a spline. Note also that this basic definition does not make any assumption on the continuity of the function. In particular, the polynomial pieces of a spline may or may not satisfy continuity conditions at their junction. Examples of splines are given in figure 2.11.

Figure 2.11: Examples of spline functions. A spline is a piecewise polynomial function. The width of each piece is not necessarily the same. In the most general definition of a spline, there may (top) or may not (bottom) be continuity conditions between the polynomial pieces. Top: a spline made of 6 polynomial pieces of degree 2 with $\mathcal{C}^1$ continuity over the whole domain $[k_0,k_6]$. Bottom: a spline made of 5 polynomials of various degrees with various continuity conditions at the knots.

Mathematical definition.

Mathematically speaking, several elements are required to define a spline: a degree, a set of contiguous intervals, and, of course, polynomials on each of this intervals. The degree of a spline, denoted $d$ in this section, is the maximal degree of the polynomial pieces. Equivalently, one may talk about the order of the spline, which is $d+1$ for a spline of degree $d$. The intervals are defined using a knot sequence $k_0 < \ldots < k_n$ which is a strictly increasing sequence of $n+1$ real numbers. The values $k_0 , \ldots , k_n$ are called the knots. These knots defines $n$ knot intervals $[k_i,k_{i+1}]$ for $i \in \llbracket 0,n-1 \rrbracket$. On each knot interval, a spline of degree $d$ is defined by a polynomial of degree at most $d$. The natural definition domain of a spline is the interval $[k_0,k_n]$. For instance, a spline $s : [k_0,k_n] \rightarrow \mathbb{R}$ may be defined as:

$$s(x) = \sum_{i=0}^d p_{ij} (x - k_j)^i \qquad \begin{cases} \t... ... \llbracket 0,n-2 \rrbracket \textrm{if } x \in [k_{n-1},k_n] \end{cases}$$ (2.70)

where the values $p_{ij}$ for $i \in \llbracket 0,d \rrbracket$ are the coefficients of the $j$-th polynomial piece ( $j \in \llbracket 0,n-1 \rrbracket$). Note that equation (2.70) is just a particular way of expressing a spline. It is the most basic form for expressing the fact that $s$ is a piecewise polynomial function. Other more interesting representations will be given later in this chapter.

In addition to these basic elements, the polynomial pieces may be stitched to each other using continuity conditions. These conditions are written:

$$\lim_{\substack{k \rightarrow k_i k < k_i}} \frac{\partial^{l}... ...quad i \in \llbracket 1,n-1 \rrbracket , l \in \llbracket 0, c_i-1 \rrbracket ,$$ (2.71)

where $c_i \in \llbracket 0,d-1 \rrbracket$ is the required class of continuity at the knot $k_i$ and where the convention $\frac{\partial^0 s}{\partial x^0} = s$ is used. A common choice is $c_1 = \ldots = c_{n-1} = d-1$. We name this choice the full continuity constraints. In this case, the spline $s$ belongs to $\mathcal{C}^{d-1}([k_0,k_n])$, which is the maximal continuity class for a piecewise polynomial function.

Number of degrees of freedom.

Let us note $\mathcal{S}_d(k_0,\ldots,k_n)$ the vector space of the splines of degree $d$ with knots $k_0 , \ldots , k_n$. Let $s$ be a spline of $\mathcal{S}_d(k_0,\ldots,k_n)$. The number of degrees of freedom of the spline $s$ is the dimension of the vector space $\mathcal{S}_d(k_0,\ldots,k_n)$. It is the total number of polynomial coefficients minus the number of continuity conditions. In the full continuity case, the number of degrees of freedom of a spline is $n(d+1) - (n-1)d = n+d$.

Truncated power functions.

A particular way to expressing the splines relies on the truncated power functions. A truncated power function is denoted with the symbol $+$. It is defined as:

$$(x-c)^k_+ = \begin{cases} (x-c)^k & \textrm{if } x \geq c 0 & \textrm{otherwise.} \end{cases}$$ (2.72)

It can be proved (61) that any spline $s$ of $\mathcal{S}_d(k_0,\ldots,k_n)$ can be uniquely written as a linear combination of the canonical monomial $x^i$ and of the truncated power functions of degree $d$:

$$s(x) = \sum_{i=0}^d \alpha_i x^i + \sum_{i=1}^{n-1} \beta_j (x - k_i)_+^d,$$ (2.73)

where $\{ \alpha_i \}_{i=0}^d$ and $\{ \beta_i \}_{i=1}^{n-1}$ are $n+d$ real values. The $n+d$ polynomials $1, x, \ldots, x^d, (x - k_1)_+^d, \ldots, (x - k_{n-1})_+^d$ form a basis of the vector space $\mathcal{S}_d(k_0,\ldots,k_n)$. However, this family of functions constitutes an ill-conditioned basis which makes the expression of equation (2.73) numerically unstable. Therefore, equation (2.73) is not suited for computations. In the next section, we explore another representation of splines, the so-called B-splines, which is more convenient for practical use.

The B-spline Representation

In this section, we give the definitions and the properties of the parametric model mostly used in this thesis: the splines expressed as a linear combination of B-splines. The B-splines are a set of piecewise polynomial functions that defines a suitable basis for the vector space of the splines (the B in B-spline stands for Basis). As remarked by (56), they were first introduced in (169,53). We start this section with the construction and the definitions of the basic building block, i.e. the B-spline functions. We then give the details on the general representation of splines with the B-splines basis functions. We end this section with a special case of particular interest: the uniform cubic B-splines.

The B-Splines Functions

The B-spline $N_{i,d+1}$ of degree $d$ (order $d+1$) with knots $k_i < \ldots < k_{i+d+1}$ is defined recursively with the following relation:

$$N_{i,d+1}(x) = \frac{x - k_i}{k_{i+d} - k_i} N_{i,d}(x) + \frac{k_{i+d+1} - x}{k_{i+d+1} - k_{i+1}} N_{i+1,d}(x),$$ (2.74)

$$N_{i,1}(x) = \begin{align*}\begin{cases} 1 & \textrm{if } x \in [k_i,k_{i+1}[ 0 & \textrm{otherwise.} \end{cases}\end{align*}$$ (2.75)

These formula are only one way of defining the B-splines. They are called the Cox de Boor recursion formula. One may remark from equation (2.74) and equation (2.75) that B-splines are themselves splines.

Properties.

Here comes a list of the most basic properties of the B-spline functions. These properties were extensively studied in (57,170).

Positivity.

The B-splines are everywhere positive or null:

$$N_{i,d+1}(x) \geq 0 \qquad \forall x \in \mathbb{R}.$$ (2.76)

Local support.

The support of the B-splines is bounded, i.e. they are non-zero only over a their natural definition domain:

$$N_{i,d+1}(x) = 0 \textrm{ if } x \not\in [k_i,k_{i+d+1}]$$ (2.77)

Boundary values.

$$N_{i,d+1}(k_i) = N_{i,d+1}(k_{i+d+1}) = 0$$ (2.78)

Continuity.

For a given degree $d$, the B-splines belongs to the highest possible class of continuity for a piecewise polynomial function:

$$N_{i,d+1} \in \mathcal{C}^{d-1}([k_i,k_{i+d+1}])$$ (2.79)

Derivatives of a B-spline.

The derivative of a B-spline of degree $d$ is a linear combination of B-splines of degree $d-1$:

$$N'_{i,d+1}(x) = d \left ( \frac{N_{i,d}(x)}{k_{i+d} - k_i} - \frac{N_{i+1,d}(x)}{k_{i+d+1} - k_{i+1}} \right )$$ (2.80)

Coincident knots.

So far, we made the assumptions that the knots were all different. The definition of the B-splines may be extended to coincident knots. This allows one to weaken the continuity conditions at the position of these coincident knots. Let $r$ knots in the set $\{k_i, \ldots, k_{i+d+1}\}$ be coincident at the point $c$ (with $2 \leq r \leq d+1$). The B-spline have continuous derivatives up to order $d-r$ at $c$ and is discontinuous at $c$ if $r = d+1$. Figure 2.12 illustrates the influence of coincident knots on the B-spline basis functions.

Figure 2.12: Influence of coincident knots on a B-spline basis function. Here we consider a B-spline of degree $d=3$. The knots $k_0, \ldots, k_4$ form a strictly increasing sequence in the sub-figures (a) to (e). In sub-figure (f), $k_1$, $k_2$, and $k_3$ are coincident. In (a-e), the B-spline belongs to $\mathcal{C}^3$. In (f), it is only $\mathcal{C}^{d-3} = \mathcal{C}^{0}$ at the position of the knot $k_1 = k_2 = k_3$.

(a)	(b)
(c)	(d)
(e)	(f)

Multiple knots, breaks.

Let $k_0 \leq \ldots \leq k_n$ be a knot sequence with coincidence allowed. The break sequence $b_0 < \ldots < b_m$ (with $m \leq n$) is the strictly increasing sequence of real numbers build by removing the redundancies from the knot sequence:

$$b_0 = k_0 < \ldots < b_i = k_{i_1} = \ldots = k_{i_1+r_1} < \ldots < b_j = k_{i_2} = \ldots = k_{i_2+r_2} < \ldots < b_m = k_n.$$ (2.81)

The multiplicity of the breaks $b_i$ is the number of knots that corresponds to the break $b_i$. It is denoted with the operator $\mathrm{mult}$. For instance, in equation (2.81), we have that $\mathrm{mult}(b_j) = r_2 + 1$.

Splines as Linear Combinations of B-Splines

Splines can be written as a linear combination of B-splines basis functions. Such splines are often referred to as B-splines. This may be a bit confusing but it is shorter than `splines as a linear combination of B-splines'. We will use this language shortcut in the rest of this document. The expression `B-spline basis function' will be utilised to distinguish between the splines and the basis functions. Let us take back the knot sequence we used when we introduced the spline functions (see section 2.3.1): $\mathbf{k} = k_0 \leq \ldots \leq k_n$^2.3. Since a single B-spline of degree $d$ spans $d+1$ knot intervals, $n-d$ independent B-splines can be defined using $\mathbf{k}$. The vector space $\mathcal{S}_d(k_0,\ldots,k_n)$ has $n+d$ dimensions. Therefore, we need $2d$ supplemental B-splines to form a basis of $\mathcal{S}_d(k_0,\ldots,k_n)$. These B-splines may be defined by adding $2d$ extra knots to the initial knot sequence satisfying the following conditions:

$$\begin{split} & k_{-d} \leq \ldots \leq k_{-1} \leq k_0, ... ...d } & k_{n} \leq k_{n+1} \leq \ldots \leq k_{n+d}. \end{split}$$ (2.82)

These additional knots are named the boundary knots. They must satisfy the conditions of equation (2.82) but may be otherwise arbitrary. There exists some common choice for defining these boundary knots, later reviewed in this document.

A B-spline $s$ is uniquely written as a linear combination of the $n+d$ basis functions $N_{i,d+1}$ for $i \in \llbracket -d,n-1 \rrbracket$:

$$s(x) = \sum_{i=-d}^{n-1} w_i N_{i,d+1}(x),$$ (2.83)

where the real values $w_i$ ( $i \in \llbracket -d,n-1 \rrbracket$) are named the weights (or the coefficients) of the B-spline. For vector-valued splines (see after), the entities that corresponds to the weights will be called the control points. Note that equation (2.83) will often be written in vector notation:

$$s(x) = \mathbf{n}_x^\mathsf{T}\mathbf{w} = \mathbf{w}^\mathsf{T}\mathbf{n}_x,$$ (2.84)

where $\mathbf{w}^\mathsf{T}= \begin{pmatrix}w_{-d} & \ldots & w_{n-1} \end{pmatrix}$ and $\mathbf{n}_x^\mathsf{T}= \begin{pmatrix}N_{-d,d+1}(x) & \ldots & N_{n-1,d+1}(x) \end{pmatrix}$.

Coincident knots.

The dimension of the vector  $\mathcal{S}_d(k_0,\ldots,k_n)$ is reduced with coincident knots. Indeed, it corresponds to the number $m$ ($m \leq n$) of break intervals multiplied by the number of polynomial coefficients on each break interval ($d+1$) minus the number of continuity conditions. This is consistent with the fact that the order of continuity of a spline is reduced at the location of coincident knots. Indeed, for a break $b_i$ with multiplicity $r_i$, we have $d-r_i$ continuity constraints instead of $d$:

$$\frac{\partial^{l} s}{\partial x^{l}}(k_i^-) = \frac{\partial^{l} s}{\partial x^{l}}(k_i^+) \qquad l \in \llbracket 0, d-r_i \rrbracket .$$ (2.85)

Properties.

We now list some basic properties of the B-splines.

Definition domain.

From equation (2.82) and equation (2.83), we see that a B-spline can take non-zero values over the interval $]k_{-d}, k_{n+d}[$. Therefore, the interval $[k_{-d}, k_{n+d}]$, named the full definition domain, seems to be a good candidate for the definition domain of the spline. This is not always a good choice. Indeed, if there are no coincident knots, the boundary values of the splines will always be zero. Besides, for arbitrary knots, some interesting properties of the B-splines will not be satisfied on $[k_{-d},k_0[$ and $]k_{n},k_{n+d}]$. For instance, it is the case for the property of the partition of unity (see below). Besides, on the interval $[k_0,k_n]$, a B-spline is always the combination of exactly $d+1$ non-zero basis functions (except maybe at the knot position or if some weights are zero). This is not true on $[k_{-d},k_0[$ and $]k_{n},k_{n+d}]$. Consequently, the definition domain $[k_0,k_n]$ is often a more natural choice than $[k_{-d}, k_{n+d}]$. We name this interval the natural definition domain. Besides, it is more consistent with the general definition of a spline, as explained in section 2.3.1.

Partition of unity.

The B-spline basis functions have the interesting property of forming a partition of unity. This means that we have:

$$\sum_{i=-d}^{n-1} N_{i,d+1} (x) = 1 \qquad \forall x \in [k_0,k_n].$$ (2.86)

This property is the reason why the B-spline basis functions are often qualified of normalized. Figure 2.13 illustrates the partition of unity property.

Figure 2.13: Some interesting properties of the B-splines. On the natural definition domain of the B-spline ($[k_0,k_4]$ on this figure), the B-spline basis functions sum up to one (partition of unity). In this example, we use B-splines of degree 2. The horizontal segment below the abscissa axis represents the domain of influence of the B-splines basis function, i.e. the interval on which they are not null. At a given point, there are at most $d+1$ non-zero B-spline basis functions (compact support).

Limited influence of the weights.

Another interesting property of the B-splines is the fact that the influence of the weights is spatially limited. This comes from the fact that the B-spline basis functions have a limited support. Consequently, for a given point $x$, the value $s(x)$ is always the linear combination of at most $d+1$ non-zero basis functions. This is illustrated on figure 2.13. For reasons that will become clear later in this document, this property allows one to design efficient procedures for parameter estimation with splines. For now, let us just say that it is obviously faster to compute the sum of $d+1$ numbers than the sum of $d+n$ numbers (especially when $n$ is much more bigger than $d$, which is often the case in practice).

Representational power.

By definition, it is clear that a B-spline is a spline. Reciprocally, it can also be shown that any spline of $\mathcal{S}_d(k_0,\ldots,k_n)$ can be represented by a B-spline. This property is sometimes considered as the fundamental theorem of the B-splines (57).

Position of the weights.

At this point, the reader who has a minimal background on splines and B-splines might wonder where are the `control points' of the B-spline. This is generally a confusing point. As we mentioned earlier, the term `control point' is more conveniently used for vector-valued splines (for instance, a parametric curve embedded in a 2D or 3D space). In this case, talking about the position of the control points has a meaning (and, besides, some interesting properties can be linked to these positions). In the mono-dimensional case, and more generally in the scalar-valued case, speaking about the position of the weights does not make much sense. Indeed, the weight $w_i$ is just a scalar that multiplies the $i$-th basis function. It is thus linked to the whole interval on which the basis function $N_{i,d+1}$ is non null ( $[k_i,k_{i+d}]$). In other words, the weight $w_i$ may be seen as an ordinate without an abscissa. If one really wants to associate a spatial information to the weight $w_i$, it might be an horizontal segment of line ranging from $k_i$ to $k_{i+d}$ for the abscissa and of ordinate $w_i$. This is illustrated in figure 2.14.

Figure 2.14: A possible graphical representation of the weights of a mono-dimensional B-spline. In this illustration, we take the same knots and the same degree than in figure 2.13 (in other words, the same B-spline basis functions). The horizontal segments represents the weights applied to each one of the basis functions (the heights are equal to the weights). The dashed curves are the weighted basis functions, i.e. the basis functions multiplied by their corresponding weight. The solid line is the sum of the weighted basis functions, i.e. the final B-spline.

Linearity.

Although the expression $s(x)$ is not linear with respect to the abscissa $x$, it is linear with respect to the weights. This is of particular interest in parameter estimation since in such problems we are interested in estimating the weights, not the abscissa. A linear relation generally leads to easier computations.

Derivatives.

Let us temporarily write explicitly the dependency of $s$ in the weights  $\mathbf{w}^\mathsf{T}= \begin{pmatrix}w_{-d} & \ldots & w_{n-1} \end{pmatrix}$, i.e. $s(x) = s(x ; \mathbf{w})$. The derivatives of the B-spline $s$ with respect to $x$ is easily computed:

$$\frac{\partial s}{\partial x}(x ; \mathbf{w}) = \sum_{i=-d}^{n-1} w_i \frac{\partial N_{i,d+1}}{\partial x}(x).$$ (2.87)

Since the derivative of a B-spline basis function of degree $d$ is a linear combination of B-spline basis functions of degree $d-1$ (see equation (2.80)), the derivative of a B-spline is a B-spline with one less degree than the original.

The `derivative', or more precisely the gradient, of $s$ with respect to the weights  $\mathbf{w}$ is given by:

$$\boldsymbol{\nabla}^\mathsf{T}s(x ; \mathbf{w}) = \begin{pmatrix} N_{-d,d+1}(x) & \ldots & N_{n-1,d+1}(x) \end{pmatrix}.$$ (2.88)

The gradient of a spline with respect to the parameters  $\mathbf{w}$ plays an important role in parameter estimation since it is used by optimization algorithms.

Coincident boundary knots.

The coincident boundary knots are a common choice for the supplemental boundary knots $k_{-d}, \ldots, k_{-1}$ and $k_{n+1}, \ldots, k_{n+d}$. It is defined by:

$$\begin{split} & k_{-d} = \ldots = k_{0}, \textrm{and } & k_{n} = \ldots = k_{n+d}. \end{split}$$ (2.89)

In this case, the full definition domain of the B-spline $[k_{-d}, k_{n+d}]$ coincides with the natural definition domain $[k_0,k_n]$. The boundary values of the splines on the full definition domain are not 0 anymore but 1. Therefore, the partition of unity property is satisfied over the entire definition domain. This particular choice of boundary knots is illustrated in figure 2.15. Note that there exists other choices for the boundary knots. For instance, one may use arbitrary knots at his convenience or periodic boundary knots (61). This later choice is particularly well suited for approximating periodic functions with B-splines. We do not detail this choice here because we do not use it in this document.

Figure 2.15: B-spline with coincident boundary knots. In this case, the partition of unity property is satisfied over all the full definition domain which is the same as the natural definition domain.

Uniform Cubic B-Splines

The Uniform Cubic B-Splines (UCBS) are a special case of B-splines which are particularly interesting for their simplicity and efficiency. As the name indicates, they are B-splines of degree 3. This degree is a good compromise between flexibility and simplicity of the induced computations. The word uniform means that all the knots are equally spaced. In this case, the B-splines basis functions are just shifted copies of each others:

$$N_{j,d+1}(x) = N_{i,d+1}\left ( x - (j + i) s \right ) \qquad \forall (i,j) \in \llbracket -d, n-1 \rrbracket ^2,$$ (2.90)

where $s$ is the width of a knot interval (i.e. $s = k_{i+1}-k_i$ for all $i \in \llbracket -d, n-2 \rrbracket$). Figure 2.16 shows a set of B-spline basis functions in the UCBS case. For the sake of simplicity, we drop the index that indicates the order in the notation of the B-spline basis functions, i.e. $N_i(x) = N_{i,4}(x)$.

Figure 2.16: The B-spline basis functions for UCBS are shifted copies of each others. On the natural definition domain ($[k_0,k_3]$ on this figure), there are always 4 non-zero basis functions.

Notation, definitions

Normalized abscissa.

When dealing with UCBS, it is often more convenient to work with normalized abscissa than with original abscissa. The normalized abscissa consists in scaling and translating the abscissa so that the knot $k_0$ coincides with 0 and so that the width of the knot intervals equals 1. Let $\mathbf{k} = \{k_{-3}, \ldots, k_0, \ldots, k_n, \ldots k_{n+3}\}$ be the knot sequence. The normalized abscissa of the point $x$, denoted $\nu(x)$, is defined by:

$$\nu(x) = \frac{x-k_0}{s},$$ (2.91)

where $s$ is the original width of a knot interval, i.e. $s = k_{i+1}-k_i$ ( $i \in \llbracket -3, n+2 \rrbracket$).

Knot interval.

The knot interval in which a point $x$ lies is denoted $\iota(x)$. $\iota$ is a function from $[k_{-3}, k_{n+3}]$ to $\llbracket -3, n+2 \rrbracket$ defined as follows:

$$\iota(x) = \begin{cases} \lfloor \nu(x) \rfloor & \textrm{if } x \in [k_{-3}, k_{n+3}[ n+2 & \textrm{if } x = k_{n+3}. \end{cases}$$ (2.92)

Normalized 0-based abscissa.

The normalized 0-based abscissa of $x$ is the number $o(x)$ such that:

$$o(x) = \nu(x) - \iota(x).$$ (2.93)

It corresponds to the abscissa of the point $x$ in a local coordinate frame so that the lower bound of the knot interval in which the point $x$ lies coincides with 0 and of width 1.

UCBS basis functions.

A closed form expression of the UCBS basis functions can be computed by unrolling the Cox-de Boor recursive relations that defines the B-spline basis functions (equation (2.74)). Without loss of generality, we consider that the knot sequence is normalized and 0-based. If it was not the case, one would just have to replace $x$ by $o(x)$ in the right-hand side of the following equations. The $i$-th basis function of the UCBS is expressed as:

$$N_i(x) = \begin{cases} b_3(x) = \frac{1}{6} x^3 & \textrm{if }... ...\textrm{if } x \in [k_{i+3},k_{i+4} [ 0 & \textrm{otherwise.} \end{cases}$$ (2.94)

Figure 2.17 gives an illustration of the B-spline basis function for the UCBS. The evaluation of a B-spline at a point $x$ is then equivalent to a blending of the four weights closest to the point $x$. The blending functions are the four polynomials  $b_0, \ldots, b_3$ of degree 3 that constitutes the B-spline basis function. In other words, we have that:

$$s(x) = \sum_{i=0}^3 w_{\iota(x)+i} b_i(o(x))$$ (2.95)

Figure 2.17: Anatomy of a B-spline basis function of UCBS. (a) A B-spline basis function of a UCBS is made of four pieces, each one of which being a polynomial of degree 3. (b) On a given knot interval, the value of a B-spline can be viewed as the blending of the four adjacent coefficients of the B-spline with weights given by the basis functions.

(a)		(b)

Vector notation.

As any B-spline, a UCBS can be written in vector notation:

$$s(x) = \mathbf{n}_x^\mathsf{T}\mathbf{w},$$ (2.96)

$$\textrm{with } \mathbf{n}_x = \begin{pmatrix} \mathbf{0}_{\iota(... ... \mathbf{w} = \begin{pmatrix} w_{-d} \vdots w_{n-1} \end{pmatrix}.$$ (2.97)

Remark that the vector  $\mathbf{n}_x$ has at most 4 non-zeros entries, whatever the size of the knot vector (i.e. the number of weights).

Matrix notation.

The matrix notation is another common notation for the UCBS. It explicitly reveals that, on a given knot interval, a UCBS is a polynomial function of degree 3 with coefficients obtained by blending the weights of the 4 non-zero B-spline basis functions that corresponds to this knot interval. As we will see later in this manuscript, the matrix notation can make easy some computations that would have been more difficult otherwise. It is given by:

$$s(x) = \begin{pmatrix}o(x)^3 & o(x)^2 & o(x) & 1 \end{pmatrix} \... ...{\iota(x)} w_{\iota(x)+1} w_{\iota(x)+2} w_{\iota(x)+3} \end{pmatrix},$$ (2.98)

where $M_G$ is known as the geometric matrix (118) and is defined by:

$$\mathsf{M}_G = \frac{1}{6} \begin{pmatrix} -1 & 3 & -3 & 1 3 & -6 & 3 & 0 -3 & 0 & 3 & 0 1 & 4 & 1 & 0 \end{pmatrix}.$$ (2.99)

Although we do not use them in this document, other type of splines can be written in the form of equation (2.98) just by changing the geometric matrix. For instance, this is the case for the cubic Hermite splines (67).

Natural Splines

One of the most important application of the splines is to interpolate a sparse set of data point. Let $\{x_i \leftrightarrow y_i\}_{i=1}^n$ be the data set. The natural spline is the `least bended' function that interpolates the data set. It is the solution to the following variational problem:

$$\begin{array}{rclcl} \displaystyle \min_{f \in \mathcal{C}^2... ...= y_i &\forall i \in \llbracket 1,n \rrbracket \end{array}$$ (2.100)

where $B$ is the functional that gives the bending energy of a function over its definition domain $\Omega$ (here, $$\Omega = \big[\min_i x_i, \max_i x_i \big]$$). It is defined as:

$$B[f] = \int_{\Omega} \left ( \frac{\partial^2 f}{\partial x^2}(x) \right )^2 \mathrm d x$$ (2.101)

The solution to problem (2.100) is a B-spline of degree 3 with knots identical to the abscissa of the data points (57).

B-Splines in Higher Dimensions

In this section, we extend the B-splines as presented in the previous section to higher dimensions. Note that for the sake of simplicity, we restrict our study to B-splines although most of the concept presented in this section could be applied to arbitrary splines. We first show how vector-valued B-splines can be defined. We will not spend much time on these aspects since they are barely used in the rest of this document. We then consider a case of greater importance in this thesis: the bivariate B-splines built using the tensor-product of univariate B-splines.

Vector-Valued B-Splines

Vector-valued B-splines can easily be constructed from scalar-valued B-splines by replacing the weights with control points. A vector-valued B-splines $\mathcal {S} : \mathbb{R}\rightarrow \mathbb{R}^m$ is thus defined by:

$$\mathcal {S}(\mathbf{x}) = \sum_{i=-d}^{n-1} \mathbf{p}_i N_{i, k+1}(x),$$ (2.102)

where the $\mathbf{p}_i$ are the control points of the B-splines. They are vector of $\mathbb{R}^m$. With $m=2$, equation (2.102) is the equation of a parametric curve embedded in a plane. With $m=3$, equation (2.102) describes a parametric curve embedded in space. An illustration of vector-valued (with $m=2$) is given in Figure 2.18.

Figure 2.18: A vector-valued B-splines (blue thick curve) embedded in the 2D plane. We use a B-spline of degree 3 with a uniform knot sequence $\{k_{-3}, \ldots, k_{10}\}$. The blue ticks represent the position of the knots (note that we only consider the natural definition domain $[k_0,k_7]$). The black dots are the control points of the curve (from $\mathbf p_{-3}$ to $\mathbf p_6$). The solid grey line is the polygon of control. The dashed grey line is the convex hull of the control points.

Contrarily to the scalar-valued case, it makes sense to speak about the position of the control points. While a weight $w_i$ could be seen as an ordinate without an abscissa, a control point  $\mathbf{p}_i \in \mathbb{R}^m$ completely defines a point in $m$ dimensions. Besides, some properties can be attached to the position of the control points. The set of all the control points  $P = \{ \mathbf{p}_i \}_{i=-d}^{n-1}$ defines what is called the polygon of control. An interesting property is that the B-spline is always included in the convex hull of the polygon of control $P$.

Bivariate B-Splines

One of the most simple approach to extend the univariate B-splines to two variables is known as the tensor product B-spline. The use of the expression tensor product will become clear later as we will see that it is related to the tensor product of two matrices (also known as the Kronecker product). We restrict our study of the tensor product splines to the case of two variables but the same principles could be applied for higher dimensions (but with a dramatic increase in the notation burden). Let $\{ k_{-d_x}, \ldots, k_{n_x+d_x} \}$ and $\{ l_{-d_y}, \ldots, l_{n_y+d_y} \}$ be two knot sequences. The (scalar-valued bivariate) tensor product B-spline of degree $d_x$ along the $x$-direction and $d_y$ along the $y$-direction is the function $s$ from $[k_0,k_{n_x}] \times [l_0,l_{n_y}]$^2.4 to $\mathbb{R}$ defined as:

$$s(x,y) = \sum_{i=-d_x}^{n_x-1} \sum_{i=-d_y}^{n_y-1} w_{ij} N_{i,d_x+1}(x) N_{j,d_y+1}(y).$$ (2.103)

The main advantage of the tensor product approach is that most of the properties of the univariate B-splines are still true in the bivariate case. This is true, for instance, for the partition of unity property, or for the local support of the basis functions.

The definition of equation (2.103) can be interpreted in different ways. We give two of these interpretations in the next two paragraphs.

Linear combination of bivariate basis functions.

One can consider the tensor product B-splines as a linear combination of the bivariate basis functions $B_{i,j}$ (for $i \in \llbracket -d_x,n_x-1 \rrbracket$ and $j \in \llbracket -d_y,n_y-1\rrbracket$) which are bivariate polynomials of degree $d_x$ in $x$ and $d_y$ in $y$ defined as:

$$B_{i,j}(x,y) = N_{i,d_x+1}(x) N_{j,d_y+1}(y).$$ (2.104)

Given the properties of the univariate B-spline basis functions, the basis function $B_{i,j}$ is non-zero only over the interval $[k_i,k_{i+d_x+1}] \times [l_j,l_{j+d_y+1}]$. The construction of the tensor product B-spline basis functions is illustrated in figure 2.19.

Figure 2.19: Construction of a bivariate B-spline basis function (mesh grid) as the tensor product of two univariate B-spline basis functions (blue and red curves). In this illustration, we took $d_x=d_y=3$ and uniformly spaced knots. The value of the tensor product B-spline basis function $B_{i,j}$ at the point $(x,y)$ is the product of the univariate basis function $N_{i,d_x}$ and $N_{j,d_y}$ evaluated at the points $x$ and $y$ respectively.

Relation to the tensor product of matrices.

On a sub-domain $[k_i,k_{i+1}]$, a univariate spline $s$ of degree $d$ is a single polynomial of degree $d$. This can be written in vector form as follows:

$$s(x) = \mathbf{a}^\mathsf{T}\mathbf{x} = \begin{pmatrix} a_d & \... ...\end{pmatrix} \begin{pmatrix} x^d & \ldots & x & 1 \end{pmatrix}^\mathsf{T},$$ (2.105)

where the values $\{a_i\}_{i=0}^d$ are the coefficients of the polynomial. On a sub-rectangle  $[k_i,k_{i+1}] \times [l_j,l_{j+1}]$, a tensor product spline $s$ is given by the tensor (or Kronecker) product of a polynomial of degree $d_x$ in $x$ and $d_y$ in $y$. Let $p_x$ and $p_y$ be those two polynomials:

$$p_x(x) = \mathbf{a}^\mathsf{T}\mathbf{x} = \begin{pmatrix} a_{d_x} & \l... ...{pmatrix} \begin{pmatrix} x^{d_x} & \ldots & x & 1 \end{pmatrix}^\mathsf{T},$$ (2.106)

$$\textrm{and } p_y(y) = \mathbf{b}^\mathsf{T}\mathbf{y} = \begin{pmatrix} b_{d_y} & \l... ...{pmatrix} \begin{pmatrix} y^{d_y} & \ldots & y & 1 \end{pmatrix}^\mathsf{T}.$$ (2.107)

The fact that a tensor product spline is the tensor product of two univariate polynomial can be seen from the following identity:

$$(\mathbf{a}^\mathsf{T}\mathbf{x}) \otimes (\mathbf{b}^\mathsf{T}\... ...bf{a}^\mathsf{T}\otimes \mathbf{b}^\mathsf{T}) (\mathbf{x} \otimes \mathbf{y}).$$ (2.108)

Univariate B-splines with varying weights.

Another common way of interpreting the basic definition of equation (2.103) of the tensor product B-spline is to see that each `slice' parallel to the $y$-axis of the surface is a univariate spline with weights that are themselves defined by B-splines. It can be seen by rearranging equation (2.103) as follows:

$$s(x,y) = \sum_{j=-d_y}^{n_y-1} v_j N_j(y) \qquad \textrm{with } v_j = \sum_{i=-d_x}^{n_x-1} w_{ij} N_i(x).$$ (2.109)

This point of view is illustrated in figure 2.20.

Figure 2.20: The slices of a tensor product B-spline are univariate B-splines with weights on orthogonal B-splines. (a) A tensor product B-splines with its $6 \times 5$ weights. (b) The 6 weights in the slice of equation $y=-1$ define a B-spline. (c) All the same way, the 6 weights in the slice of equation $y=0$ define another B-spline. (d) Applying the same principle again and again, we obtain 5 B-splines. (e) The intersection of this 5 B-splines with the plane of equation $x=\alpha$ gives 5 values. (f) Those values can be used as the weights of a B-spline which is exactly the profile of the surface for $x=\alpha$ (in the example, $\alpha = 2.1$).

(a)	(b)	(c)
(d)	(e)	(f)

Vector-valued bivariate B-splines.

The extensions of the B-splines to the vector-valued bivariate case can be combined. In particular, this allows one to define parametric surfaces embedded in a 3D space, which is a function from $\mathbb{R}^2$ to $\mathbb{R}^3$. An example of such surface is presented in figure 2.21. We will make use of this type of surface model for the NURBS-Warps and for the monocular reconstruction of inextensible surfaces.

Figure 2.21: Example of a parametric surface described with a 3-vector-valued tensor-product B-spline.

Uniform cubic tensor product B-splines.

As in the univariate case, bivariate tensor-product B-splines of degree 3 defined with the help of uniformly distributed knot sequences are of particular interest. Indeed, such B-splines involves only polynomials of degree 3 which make the computations more stable. Besides, these computations are simplified in the sense that the bivariate basis functions are shifted copies of each other, as illustrated in figure 2.22. This type of tensor product B-spline is also abbreviated UCBS.

Figure 2.22: The bivariate tensor product B-spline basis functions for UCBS are shifted copies of each others. Here the full definition domain is represented, i.e. $[k_{-3}, k_{10}] \times [l_{-3},l_{7}]$.

Non Uniform Rational B-Splines (NURBS)

The rational splines are another parametric model of function that will be used in this document. As the name may indicate, this model is defined as the ratio of two splines. Rational splines are particularly interesting in computer vision since they may be seen as the perspective projection of standard splines. Although any type of spline could be used, we focus on a particular type of rational splines that relies on B-splines: the Non-Uniform Rational B-Splines (NURBS).

Basics on NURBS

Definition.

We first give the definition of a univariate scalar-valued NURBS. Let $\mathbf{k} = \{k_{-d} \leq \ldots \leq k_{d+n}\}$ be a knot sequence, with $d$ the degree of the NURBS. A NURBS is a function model parametrized by $d+n$ points $p_i$ ( $i \in \llbracket -d,n-1 \rrbracket$)), each one of those associated to a strictly positive^2.5 weight $w_i$. Let $r : [k_0,k_n] \rightarrow \mathbb{R}$ be the NURBS. Its expression is given by (42,67):

$$r(x) = \frac{\displaystyle \sum_{i=-d}^{n-1} w_i p_i N_{i,d+1}(x)}{\displaystyle \sum_{i=-d}^{n-1} w_i N_{i,d+1}(x)}.$$ (2.110)

The weight $w_i$ controls the influence of the point $p_i$. In particular, the bigger $w_i$ the closer to $p_i$ the NURBS. This property is illustrated on figure 2.23 for 2-vector-valued NURBS. Another common writing of the NURBS consists in expressing them as a combination of basis functions with the control points as the coefficients:

$$r(x) = \sum_{i=-d}^{n-1} p_i R_{i,d+1}(x),$$ (2.111)

where $R_{i,d+1}$ is the $i$-th rational basis function of degree $d$ (order $d+1$):

$$R_{i,d+1}(x) = \frac{\displaystyle w_i N_{i,d+1}(x)}{\displaystyle \sum_{i=-d}^{n-1} w_i N_{i,d+1}(x)}.$$ (2.112)

Although the writing of equation (2.111) seems similar to the definition of the B-splines, it is in fact quite different. Indeed, the B-spline basis functions were functions independent of the parameters of the B-spline. On the contrary, the rational basis functions depend on the weights of the NURBS. Consequently, the NURBS are not linear with respect to the parameters. Even if the concepts behind the rational basis functions and the B-spline basis functions are different, they still share some properties. This will be reviewed and illustrated in the paragraph dedicated to the properties of the NURBS.

Higher dimensions.

As for the B-splines, the NURBS can be generalized to higher dimensions. An $m$-vector-valued NURBS is obtained from equation (2.110) by replacing the scalars $p_i$ by vectors  $\mathbf{p}_i \in \mathbb{R}^m$. The weights remain unchanged and they still control the influence of the control points  $\mathbf{p}_i$. Multi-variate NURBS are derived from equation (2.110) using tensor product B-splines for both the numerator and the denominator. For instance, given two knot sequences $\{ k_{-d_x}, \ldots, k_{n_x+d_x} \}$ and $\{ l_{-d_y}, \ldots, l_{n_y+d_y} \}$, a 3-vector-valued bivariate NURBS (i.e. a parametric surface embedded in a 3D space) is the function $\mathcal {R}$ from $[k_0,k_{n_x}] \times [l_0,l_{n_y}]$ to $\mathbb{R}^3$ defined by:

$$r(x) = \frac{\displaystyle \sum_{i=-d_x}^{n_x-1} \sum_{j=-d_y}^{n... ...m_{i=-d_x}^{n_x-1} \sum_{j=-d_y}^{n_y-1} w_{ij} N_{i,d_x+1}(x) N_{j,d_y+1}(y)},$$ (2.113)

with $w_{ij} \in \mathbb{R}_+^*$ and $\mathbf{p}_{ij} \in \mathbb{R}^3$ for all $(i,j) \in \llbracket -d_x, n_x-1 \rrbracket \times \llbracket -d_y, n_y-1 \rrbracket$.

Figure 2.23: Influence of the weights associated to the control points of a 2-vector-valued NURBS.

Perspective projection.

Let  $\mathcal {R}$ be an $m$-vector-valued univariate NURBS. One may notice that the vector $\mathcal {R}(t)$ are the Cartesian coordinates of the following point expressed in homogeneous coordinates:

$$\sum_{i=-d}^{n-1} \begin{bmatrix} w_i \mathbf{p}_i w_i \end{bmatrix} N_{i,d+1}(x).$$ (2.114)

Equation (2.114) is the exact definition of an $(m+1)$-vector-valued B-spline. In other words, an $m$-vector-valued NURBS is the perspective projection of an $(m+1)$-vector-valued B-spline. This fact is illustrated in figure 2.24.

Figure 2.24: An $m$-vector-valued NURBS is the perspective projection of an $(m+1)$-vector-valued B-spline. In this illustration, we considered that $m=2$. (a) A 3-vector valued B-spline and its perspective projection into the plane of equation $z=1$. (b) Same as (a) but viewed from the top. (c) The resulting NURBS.

(a)	(b)	(c)

Properties

The NURBS share many properties with the B-splines. In addition, they have supplemental interesting properties. We now give a brief overview of these properties.

Partition of unity.

As for the B-splines, the rational basis functions form a partition of unity, i.e. :

$$\sum_{i=-d}^{n-1} R_{i,d+1}(x) = 1 \qquad \forall x \in [k_{-d}, k_{n+d}].$$ (2.115)

Note that this property hold true for any set of weights. Figure 2.25 illustrates this property. Note also that for B-splines this property was satisfied only over the natural definition domain. For NURBS, it is satisfied over all the full definition domain. This comes from the fact that the rational basis function are normalized and, therefore, the rightmost (and the leftmost) basis functions does not vanish to zero.

Figure 2.25: The rational basis functions form a partition of unity. In this illustration, we use a NURBS from $\mathbb{R}$ to $\mathbb{R}$ of degree 3 (order 4). The full definition domain $[k_{-3}, k_{10}]$ is shown. Note that contrarily to the B-splines, the rational basis functions still form a partition of unity outside of the natural definition domain $[k_0,k_7]$. This comes from the fact that the rational basis functions are normalized. In this example, the knots and the weights were randomly chosen. For the same reasons than for the control points of the univariate B-splines, the weights of the NURBS are represented using segments (shown in dashed lines) that span the interval of the corresponding rational spline function.

Compact support.

The rational basis functions have a compact support:

$$R_{i,d+1}(x) = 0 \qquad \forall x \not\in [k_i,k_{i+d+1}].$$ (2.116)

In other word, the $i$-th control point and the $i$-th weight influences the shape of the resulting NURBS only over the $d+1$ knot intervals $[k_i,k_{i+d+1}]$.

Continuity.

NURBS have continuous derivatives up to order $d$. In other words, we have that:

$$r \in \mathcal{C}^d([k_{-d}, k_{d+n}]).$$ (2.117)

As with the B-splines, it is possible to diminish these continuity conditions at the position of the knots by using multiple knots. This is illustrated in figure 2.26.

Figure 2.26: Diminishing the continuity conditions by using multiple knots with a NURBS of degree 3. A the position of the knot $k_1$, the NURBS is $\mathcal{C}^3$ in (a), $\mathcal{C}^2$ in (b), $\mathcal{C}^1$ in (c), $\mathcal{C}^0$ in (d), and not even continuous in (e).

(a)	(b)	(c)
(d)	(e)

Derivatives.

Several `types' of derivatives are useful for parameter estimation: with respect to the free variable $x$, to the control points  $\mathbf{p} = \begin{pmatrix}p_{-d} & \ldots & p_{d+n} \end{pmatrix}^\mathsf{T}$, and to the weights $\mathbf{w} = \begin{pmatrix}w_{-d} & \ldots & w_{d+n} \end{pmatrix}^\mathsf{T}$. In this paragraph, we will write explicitly the dependency of $r$ in all its parameters, i.e. $r(x ; \mathbf{p}, \mathbf{w}) = r(x)$. For the sake of simplicity, let us note $n$ and $m$ the numerator and the denominator of $r$:

$$n(x ; \mathbf{p}, \mathbf{w}) = \sum_{i=-d}^{n-1} p_i w_i N_{i,d+1}(x),$$ (2.118)

$$m(x ; \mathbf{w}) = \sum_{i=-d}^{n-1} w_i N_{i,d+1}(x).$$ (2.119)

We just give the formula of the different derivatives. More detailed computations can be found in (42).

Derivatives with respect to $x$.

$$\frac{\partial r}{\partial x}(x ; \mathbf{p}, \mathbf{w}) = \frac... ...'(x ; \mathbf{w})r(x ; \mathbf{p}, \mathbf{w})}{m(x ; \mathbf{p}, \mathbf{w})},$$ (2.120)

where $n'$ and $m'$ denote the derivatives of $n$ and $m$ with respect to $x$.

Derivatives with respect to $\mathbf p$.

The gradient of $r$ with respect to  $\mathbf{p}$ is given by:

$$\boldsymbol{\nabla}_{\mathbf{p}}^\mathsf{T}r(x ; \mathbf{p}, \mat... ...mathbf{w}) & \ldots & R_{n-1, d+1}(x ; \mathbf{p} , \mathbf{w}) \end{pmatrix},$$ (2.121)

where the functions $R_{i,d+1}$ ( $i \in \llbracket -d,n-1 \rrbracket$) are the rational basis functions defined in equation (2.112).

Derivatives with respect to $\mathbf w$.

The gradient of $r$ with respect to $\mathbf{w}$ is given by:

$$\boldsymbol{\nabla}_{\mathbf{w}}^\mathsf{T}r(x ; \mathbf{p}, \mat... ...\dfrac{\partial r}{\partial w_{n-1}}(x ; \mathbf{p},\mathbf{w}) \end{pmatrix},$$ (2.122)

with

$$\frac{\partial r}{\partial w_i}(x ; \mathbf{p} , \mathbf{w}) = \... ..._{i,d+1}(x) n(x ; \mathbf{p} , \mathbf{w})}{\left (m(x ; \mathbf{w})\right )^2}$$ (2.123)

Representation of conics.

Although we will not need this property in this document, it is still worth noticing that conic sections can be represented with NURBS. It is an ability that standard splines, in particular B-splines, do not have. Splines can only approximate conic sections. We will not give the details underlying the representation of conics with NURBS (which can be found in, for instance, (118)). We just give a classic example in figure 2.27: the representation of a circle.

Figure 2.27: Exact representation of a circle with a NURBS of degree 2. Standard splines such as B-splines can only approximate a conic, not represent them exactly.

Radial Basis Functions

Generalities

Definition.

Radial Basis Functions (RBF) are another model of parametric functions. Let $f : \mathbb{R}^n \rightarrow \mathbb{R}$ be an RBF. The function $f$ is of the following form:

$$f(\mathbf{x}) = \sum_{i=1}^p w_i \rho(\Vert \mathbf{x} - \mathbf{c}_i \Vert) + \sum_{i=p+1}^{p+n+1} w_i \phi_{i-p}(\mathbf{x}),$$ (2.124)

The real values $w_i$ ( $i \in \llbracket 1,n+1 \rrbracket$) are the weights of the RBF. They can be vectors of $\mathbb{R}^m$ in which case the RBF $f$ is a function from $\mathbb{R}^n$ to $\mathbb{R}^m$. The second term in equation (2.124) is the affine part where the functions $\phi_i$ ( $i \in \llbracket 1, q-p \rrbracket$) are monomials of order up to 1 (156). The vectors $\mathbf{c}_i \in \mathbb{R}^n$ ( $i \in \llbracket 1,p \rrbracket$) are called the centres of the RBF. They are generally fixed values, i.e. they are not part of the parameters to be estimated in a parameter estimation problem. Broadly speaking, the centres define the number of degrees of freedom of the RBF. Finally, $\rho$ is a function from $\mathbb{R}_+$ to $\mathbb{R}$. It is the basis function of the RBF. The norm $\Vert \textrm{\raisebox{1pt}{\tiny $\bullet$}}\Vert$ in equation (2.124) is not necessarily the Euclidean norm ; it can be any norm. Common basis functions will be given in section 2.3.4.2. Contrarily to the spline model, the RBF are naturally designed as multi-variate functions. This can be an advantage compared to the splines because the tensor-product approach used with splines to handle multi-variate functions has some limitations.

Note that under some assumptions, the affine part in equation (2.124) can be dropped. The RBF thus becomes:

$$f(\mathbf{x}) = \sum_{i=1}^p w_i \rho(\Vert \mathbf{x} - \mathbf{c}_i \Vert).$$ (2.125)

Linear model.

Since an RBF is linear with respect to its weights, it can be written in vector form:

$$f(\mathbf{x}) = \mathbf{l}_{\mathbf{x}}^\mathsf{T}\mathbf{w},$$ (2.126)

where $\mathbf{l}_{\mathbf{x}}$ and $\mathbf{w}$ are two vectors of $\mathbb{R}^{p+n+1}$ that are defined in the following way:

$$\mathbf{l}_{\mathbf{x}}^\mathsf{T} = \begin{pmatrix}\rho(\Vert \mathbf{x} - \mathbf{c}_1 \Vert) & \l... ...Vert \mathbf{x} - \mathbf{c}_p \Vert) & \mathbf{x}^\mathsf{T}& 1 \end{pmatrix},$$ (2.127)

$$\mathbf{w}^\mathsf{T} = \begin{pmatrix}w_1 & \ldots & w_{p+n+1} \end{pmatrix}.$$ (2.128)

Note that the vector  $\mathbf{l}_{\mathbf{x}}$ may depend on  $\mathbf{x}$ in a nonlinear fashion. However, this does not change the fact that an RBF is linear with respect to the weights  $\mathbf{w}$. Note also that RBF are very similar to splines in the sense that they are both a linear combination of basis functions. The differences are the form of the basis functions and their locations.

The Gram matrix.

For reasons that will become clear later in this document, the Gram matrix (54) plays an important role in parameter estimation problems with RBF. Let $\{ \mathbf{x}_1, \ldots, \mathbf{x}_p \}$ be a set of vectors, the number of which being identical to the number of centres of the RBF. The Gram matrix is the matrix  $\mathsf{G} \in \mathbb{R}^{p \times p}$ defined as follows:

$$\mathsf{G} = \begin{pmatrix} \rho(\Vert \mathbf{x}_1 - \mathbf{c... ...t) & \ldots & \rho(\Vert \mathbf{x}_p - \mathbf{c}_p \Vert) \end{pmatrix}.$$ (2.129)

For now, let us just say that parameter estimation problems with RBF involves the inversion of the matrix  $\mathsf{G}$. Therefore, the definiteness of the Gram matrix is an important property. The definiteness of the Gram matrix depends on the basis function $\rho$.

Basis Functions

In this section, we give details on classical basis functions for RBF (152). Table 2.2 gives the expression and some basic properties of common basis functions for RBF. These basis functions are illustrated in figure 2.28 in the univariate and the bivariate cases.

Table 2.2: Some common basis functions (s.: singular, p.d.: positive definite, p.s.d.: positive semidefinite).

Name	$\rho(r)$	Gram matrix
Gaussian	$\exp(-\sigma r^2), r \geq 0, \sigma > 0$	p.d.
Truncated Gaussian	$\left\{\begin{array}{ll} \exp(-\sigma r^2) & \textrm{if }r \leq \alpha \\ 0 & \textrm{otherwise} \end{array}\right.$	s.
Inverse multiquadric	$(r^2+c^2)^{-\frac{1}{2}}, r \geq 0, c > 0$	p.d.
Multiquadric	$(r^2+c^2)^{\frac{1}{2}}, r \geq 0, c > 0$	p.s.d.
Thin-plate spline	$\left\{\begin{array}{ll} \frac{r^2}{\sigma^2} \log \frac{r}{\sigma} & \textrm{if } r > 0 \\ 0 & \textrm{otherwise} \end{array}\right., \sigma > 0$	p.s.d.
Wendland's function	$\left\{\begin{array}{ll} \left(1-\frac{r}{\sigma}\right)^4\left(4\frac{r}{\si... ... \leq r \leq \sigma \\ 0 & \textrm{otherwise} \end{array}\right., \sigma > 0$	p.d.

Among the basis functions described in table 2.2, two are of particular interest in computer vision: the Thin-Plate Spline (TPS) basis functions and the Wendland's basis functions.

TPS.

The TPS are sometimes considered as the natural extension to the bivariate case of the cubic B-splines (193). This comes from the fact that these two models are the functions that minimizes the following variational minimization problem:

$$\min_{f : \mathbb{R}^n \rightarrow \mathbb{R}} B[f],$$ (2.130)

with $n=1$ in the cubic B-spline case and $n\geq 2$ in the TPS case. The functional $B$ is the bending energy. If $n=2$, it is defined as:

$$B[f] = \iint_{\mathbb{R}^2} \left ( \frac{\partial^2 f}{\partial ... ... + \left ( \frac{\partial^2 f}{\partial y^2} \right )^2 \mathrm d x \mathrm d y$$ (2.131)

TPS have been widely used in computer vision (11,62,24,18).

Wendland's basis functions.

The Wendland's basis functions are another type of basis functions that are particularly interesting for several reasons (73). First, they are expressed as polynomials of relatively low order, which makes them easier to compute than basis functions relying on `exotic' functions such as the logarithm or the exponential. Second, the Wendland's basis function have a bounded support. It means that the influence of a weight is spatially limited. This is not the case with, for instance, the TPS.

Figure 2.28: Graphical representation of RBF basis functions. Left-most column: univariate case. Right-most column: bivariate case.

Gaussian
Multiquadric
Inverse multiquadric
TPS
Wendland