# Thin plate spline

Jump to: navigation, search

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 $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 $x$ or $y$ coordinates within the plane. In 2D cases, given a set of $K$ corresponding points, the TPS warp is described by $2(K+3)$ parameters which include 6 global affine motion parameters and $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 $x$ is two dimensional, for interpolation, the TPS fits a mapping function $f(x)$ between corresponding point-sets $\{y_i\}$ and $\{x_i\}$ that minimises the following energy function:

$E_{tps}(f) = \sum_{i=1}^K \|y_i - f(x_i) \|^2$

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

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

## Radial basis function

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 $\{w_{i}, i = 1,2, \ldots,K\}$, a radial basis function basically defines a spatial mapping which maps any location $x$ in space to a new location $f(x)$, represented by,

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

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

### Spline

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

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

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

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

where $Y$ and $X$ are just concatenated versions of the point coordinates $y_i$ and $x_i$, and $\Phi$ is a $(K\times K)$ matrix formed from the $\phi (\|x_i - x_j\|)$. Each row of each newly formed matrix comes from one of the original vectors. The matrix $\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 $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).

$X = [Q_1 | Q_2] \left( \begin{array}{cc} R \\ 0 \end{array} \right)$

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

$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 $\gamma$ is a $(K-D-1)\times (D+1)$ matrix. Setting $c=Q_2\gamma$ (which in turn implies that $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 $\gamma$ and then w.r.t. $d$. By applying Tikhonov regularization we have

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

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

$E_{bending} = \lambda\,\textrm{trace}[Q_2(Q_2^T\Phi Q_2 + \lambda I_{(k-D-1)})^{-1}Q_2^T Y Y^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.

## References

1. ^ J. Duchon, 1976, Splines minimizing rotation invariant semi-norms in Sobolev spaces. pp 85–100, In: Constructive Theory of Functions of Several Variables, Oberwolfach 1976, W. Schempp and K. Zeller, eds., Lecture Notes in Math., Vol. 571, Springer, Berlin, 1977
• Haili Chui: Non-Rigid Point Matching: Algorithms, Extensions and Applications. PhD Thesis, Yale University, May 2001.
• G. Wahba, 1990, Spline models for observational data. Philadelphia: Society for Industrial and Applied Mathematics.