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

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:

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

References

↑ 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
↑ Bookstein, F. L. (June 1989). "Principal warps: thin-plate splines and the decomposition of deformations". IEEE Transactions on Pattern Analysis and Machine Intelligence 11 (6): 567–585. doi:10.1109/34.24792.

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.

External links

This article is issued from Wikipedia - version of the Sunday, February 07, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.