# Difference between revisions of "Thin plate spline"

Thin plate splines (TPS) are a spline-based technique for data interpolation and smoothing. They were introduced to geometric design by Duchon. [1]

## Physical analogy

The name thin plate spline refers to a physical analogy involving the bending of a thin sheet of metal. Just as the metal has rigidity, the TPS fit resists bending also, implying a penalty involving the smoothness of the fitted surface. In the physical setting, the deflection is in the ${\displaystyle z}$ direction, orthogonal to the plane. In order to apply this idea to the problem of coordinate transformation, one interprets the lifting of the plate as a displacement of the ${\displaystyle x}$ or ${\displaystyle y}$ coordinates within the plane. In 2D cases, given a set of ${\displaystyle K}$ corresponding points, the TPS warp is described by ${\displaystyle 2(K+3)}$ parameters which include 6 global affine motion parameters and ${\displaystyle 2K}$ coefficients for correspondences of the control points. These parameters are computed by solving a linear system, in other words, TPS has closed-form solution.

## Smoothness measure

The TPS arises from consideration of the integral of the square of the second derivative -- this forms its smoothness measure. In the case where ${\displaystyle x}$ is two dimensional, for interpolation, the TPS fits a mapping function ${\displaystyle f(x)}$ between corresponding point-sets ${\displaystyle \{y_{i}\}}$ and ${\displaystyle \{x_{i}\}}$ that minimises the following energy function:

${\displaystyle E_{tps}(f)=\sum _{i=1}^{K}\|y_{i}-f(x_{i})\|^{2}}$

The smoothing variant, correspondingly, uses a tuning parameter ${\displaystyle \lambda }$ to control how non-rigid is allowed for the deformation, balancing the aforementioned criterion with the measure of goodness of fit, thus minimising:

${\displaystyle E_{tps,smooth}(f)=\sum _{i=1}^{K}\|y_{i}-f(x_{i})\|^{2}+\lambda \iint \left[\left({\frac {\partial ^{2}f}{\partial x_{1}^{2}}}\right)^{2}+2\left({\frac {\partial ^{2}f}{\partial x_{1}\partial x_{2}}}\right)^{2}+\left({\frac {\partial ^{2}f}{\partial x_{2}^{2}}}\right)^{2}\right]{\textrm {d}}x_{1}\,{\textrm {d}}x_{2}}$

For this variational problem, it can be shown that there exists a unique minimizer ${\displaystyle f}$ (Wahba,1990).The finite element discretization of this variational problem, the method of elastic maps, is used for data mining and nonlinear dimensionality reduction.

{{#invoke:main|main}}

The Thin Plate Spline has a natural representation in terms of radial basis functions. Given a set of control points ${\displaystyle \{w_{i},i=1,2,\ldots ,K\}}$, a radial basis function basically defines a spatial mapping which maps any location ${\displaystyle x}$ in space to a new location ${\displaystyle f(x)}$, represented by,

${\displaystyle f(x)=\sum _{i=1}^{K}c_{i}\varphi (\left\|x-w_{i}\right\|)}$

where ${\displaystyle \left\|\cdot \right\|}$ denotes the usual Euclidean norm and ${\displaystyle \{c_{i}\}}$ is a set of mapping coefficients. The TPS corresponds to the radial basis kernel ${\displaystyle \varphi (r)=r^{2}\log r}$.

### Spline

Suppose the points are in 2 dimensions (${\displaystyle D=2}$). One can use homogeneous coordinates for the point-set where a point ${\displaystyle y_{i}}$ is represented as a vector ${\displaystyle (1,y_{ix},y_{iy})}$. The unique minimizer ${\displaystyle f}$ is parameterized by ${\displaystyle \alpha }$ which comprises two matrices ${\displaystyle d}$ and ${\displaystyle c}$ (${\displaystyle \alpha =\{d,c\}}$).

${\displaystyle f_{tps}(z,\alpha )=f_{tps}(z,d,c)=z\cdot d+\sum _{i=1}^{K}\phi (\|z-x_{i}\|)\cdot c_{i}}$

where d is a ${\displaystyle (D+1)\times (D+1)}$ matrix representing the affine transformation (hence ${\displaystyle z}$ is a ${\displaystyle 1\times (D+1)}$ vector) and c is a ${\displaystyle K\times (D+1)}$ warping coefficient matrix representing the non-affine deformation. The kernel function ${\displaystyle \phi (z)}$ is a ${\displaystyle 1\times K}$ vector for each point ${\displaystyle z}$, where each entry ${\displaystyle \phi _{i}(z)=\|z-x_{i}\|^{2}\log \|z-x_{i}\|}$ for each (${\displaystyle D}$) dimensions. Note that for TPS, the control points ${\displaystyle \{w_{i}\}}$ are chosen to be the same as the set of points to be warped ${\displaystyle \{x_{i}\}}$, so we already use ${\displaystyle \{x_{i}\}}$ in the place of the control points.

If one substitutes the solution for ${\displaystyle f}$, ${\displaystyle E_{tps}}$ becomes:

${\displaystyle E_{tps}(d,c)=\|Y-Xd-\Phi c\|^{2}+\lambda {\textrm {Tr}}(c^{T}\Phi c)}$

where ${\displaystyle Y}$ and ${\displaystyle X}$ are just concatenated versions of the point coordinates ${\displaystyle y_{i}}$ and ${\displaystyle x_{i}}$, and ${\displaystyle \Phi }$ is a ${\displaystyle (K\times K)}$ matrix formed from the ${\displaystyle \phi (\|x_{i}-x_{j}\|)}$. Each row of each newly formed matrix comes from one of the original vectors. The matrix ${\displaystyle \Phi }$ represents the TPS kernel. Loosely speaking, the TPS kernel contains the information about the point-set's internal structural relationships. When it is combined with the warping coefficients ${\displaystyle c}$, a non-rigid warping is generated.

A nice property of the TPS is that it can always be decomposed into a global affine and a local non-affine component. Consequently, the TPS smoothness term is solely dependent on the non-affine components. This is a desirable property, especially when compared to other splines, since the global pose parameters included in the affine transformation are not penalized.

### Solution

The separation of the affine and non-affine warping space is done through a QR decomposition (Wahba,1990).

${\displaystyle X=[Q_{1}|Q_{2}]\left({\begin{array}{cc}R\\0\end{array}}\right)}$

where Q1 and Q2 are ${\displaystyle K\times (D+1)}$ and ${\displaystyle K\times (K-D-1)}$ orthonormal matrices, respectively. The matrix ${\displaystyle R}$ is upper triangular. With the QR decomposition in place, we have

${\displaystyle E_{tps}(\gamma ,d)=\|Q_{2}^{T}Y-Q_{2}^{T}\Phi Q_{2}\gamma \|^{2}+\|Q_{1}^{T}Y-Rd-Q_{1}^{T}\Phi Q_{2}\gamma \|^{2}+\lambda {\textrm {trace}}(\gamma ^{T}Q_{2}^{T}\Phi Q_{2}\gamma )}$

where ${\displaystyle \gamma }$ is a ${\displaystyle (K-D-1)\times (D+1)}$ matrix. Setting ${\displaystyle c=Q_{2}\gamma }$ (which in turn implies that ${\displaystyle X^{T}c=0}$) enables us to cleanly separate the first term in last third equation into a non-affine term and an affine term (first and second terms last equation respectively).

The least-squares energy function in the last equation can be first minimized w.r.t ${\displaystyle \gamma }$ and then w.r.t. ${\displaystyle d}$. By applying Tikhonov regularization we have

${\displaystyle {\hat {c}}=Q_{2}(Q_{2}^{T}\Phi Q_{2}+\lambda I_{(k-D-1)})^{-1}Q_{2}^{T}Y}$
${\displaystyle {\hat {d}}=R^{-1}Q_{1}^{T}(Y-\Phi {\hat {c}})}$

The minimum value of the TPS energy function obtained at the optimum ${\displaystyle ({\hat {c}},{\hat {d}})}$ is

${\displaystyle E_{bending}=\lambda \,{\textrm {trace}}[Q_{2}(Q_{2}^{T}\Phi Q_{2}+\lambda I_{(k-D-1)})^{-1}Q_{2}^{T}YY^{T}]}$

## Application

TPS has been widely used as the non-rigid transformation model in image alignment and shape matching.

The Thin-plate-spline has a number of properties which have contributed to its popularity:

1. It produces smooth surfaces, which are infinitely differentiable.
2. There are no free parameters that need manual tuning.
3. It has closed-form solutions for both warping and parameter estimation.
4. There is a physical explanation for its energy function.