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] They are an important special case of a polyharmonic spline.

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.

Main article: Radial basis function

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 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.

Application

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

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.