Thin plate spline

Thin plate spline

This is a brief derivation for the closed form solutions for "smoothing Thin Plate Spline". Details about these splines can be found in (Wahba, 1990).

Thin plate splines (TPS) were introduced to geometric design by Duchon (Duchon, 1976). The name "thin plate spline" refers to a physical analogy involving the bending of a thin sheet of metal. 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.

"Smoothing TPS" is a regularized TPS. The model has a parameter lambda to control how non-rigid is allowed for the deformation. When lambda ightarrow infty, TPS is equal to an affine transformation, as the roughest model for non-rigid deformation.

Radial basis function

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}phi(left| x - w_{i} ight|)where left|cdot ight| denotes the usual Euclidean norm and {c_{i}} is a set of mapping coefficients. One possible choice for the kernel function phi is the thin plate spline phi(r) = r^2 log r. It has a more global nature than the Gaussian kernel phi(r) = exp(-r^2/sigma^2), which is another common function -- a small perturbation of one of the control points always affects the coefficients corresponding to all the other points as well.

Thin plate spline

moothness measure

One of the simplest smoothness measures is the space integral of the square of the second order derivatives of the mapping function. This leads us to the thin plate spline (TPS). The TPS fits a mapping function f(x) between corresponding point-sets {y_i} and {x_i} by minimizing the following energy function: : E = iintleft [left(frac{partial^2 f}{partial x^2} ight)^2 + 2left(frac{partial^2 f}{partial xy} ight)^2 + left(frac{partial^2 f}{partial y^2} ight)^2 ight] extrm{d} x , extrm{d}yAnd for a smoothing TPS, it is: E_{tps} = sum_{i=1}^K |y_i - f(x_i) | + lambda iintleft [left(frac{partial^2 f}{partial x^2} ight)^2 + 2left(frac{partial^2 f}{partial xy} ight)^2 + left(frac{partial^2 f}{partial y^2} ight)^2 ight] extrm{d} x , extrm{d}yThen smoothing TPS is defined as: f_{tps} = argmin_f E_{tps}For this variational problem, it can be shown that there exists a unique minimizer f (Wahba,1990) with a fixed weight parameter lambda which is presented in next section.

pline

Suppose the points are in 2D (D = 2). We use "homogeneous coordinates" for the point-set where a point y_{i} 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) = zcdot d + sum_{i = 1}^K phi(| z - x_i|)cdot c_i where d is a (D+1) imes(D+1) matrix representing the affine transformation and c is a K imes(D+1) warping coefficient matrix representing the non-affine deformation. The kernel function phi(|z- x_i|) is a 1 imes K vector for each point z, where each entry phi_i(z) = |z - x_i|^2 log |z - x_i| for 2 dimensions. For the 3 dimension case, phi_i(z) = |z - x_i|^3 . 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 we substitute the solution for f, E_{tps} becomes:: E_{tps}(d,c) = |Y - Xd - Phi c|^2 + lambda extrm{trace}(c^TPhi c)where Y and X are just concatenated versions of the point coordinates y_i and x_i, and Phi is a (K imes 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.

olution

The separation of the affine and non-affine warping space is done through a QR decomposition (Wahba,1990). : X = [Q_1 | Q_2] left( egin{array}{cc} R \ 0 end{array} ight)where Q1 and Q2 are K imes (D+1) and K imes (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^TPhi Q_2 gamma|^2 + |Q_1^T Y -Rd - Q_1^TPhi Q_2 gamma|^2 + lambda gamma^T Q_2^T Phi Q_2 gammawhere gamma is a (K-D-1) imes (D+1) matrix. Setting c=Q_2gamma (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^TPhi 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, extrm{trace} [Q_2(Q_2^TPhi 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 imagealignment and shape matching.

The popularity of TPS comes from a number of advantages: (1) the interpolation is smooth with derivatives of any order; (2) the model has no free parameters that need manual tuning; (3) it has closed-form solutions for both warping and parameter estimation; and (4) there is a physical explanation for its energy function.

References

*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.
*J. Duchon, 1976, Splines minimizing rotation invariant seminorms in sobolev spaces, constructive theory of functions of several variables. vol 1, pp 85-100

ee also

*Radial basis function
*Subdivision surface (emerging alternative to spline-based surfaces)
*Spline
*Polyharmonic spline (the thin-plate-spline is a special case of a polyharmonic spline)

External links

* [http://www-cse.ucsd.edu/classes/fa01/cse291/hhyu-presentation.pdf Explanation for a simplified variation problem]
* [http://mathworld.wolfram.com/ThinPlateSpline.html TPS at MathWorld]
* [http://elonen.iki.fi/code/tpsdemo/index.html TPS in C++]
* [http://ricanet.com/new/data/hw/vision/tps1.ppt TPS Powerpoint]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Polyharmonic spline — In mathematics, polyharmonic splines are used for function approximation and data interpolation.They are very useful for interpolation of scattered datain many dimensions.Polyharmonic splines are a special case of radial basis functions andare… …   Wikipedia

  • TPS — thin plate spline; time to peak shortening; topical skin protectant; treatment planning system; trypsin; tryptase; tumor polysaccharide substance …   Medical dictionary

  • TPS — • thin plate spline; • time to peak shortening; • topical skin protectant; • treatment planning system; • trypsin; • tryptase; • tumor polysaccharide substance …   Dictionary of medical acronyms & abbreviations

  • Shape context — is the term given by Serge Belongie and Jitendra Malik to the feature descriptor they first proposed in their paper Matching with Shape Contexts in 2000cite conference author = S. Belongie and J. Malik title = Matching with Shape Contexts url =… …   Wikipedia

  • Multivariate interpolation — In numerical analysis, multivariate interpolation or spatial interpolation is interpolation on functions of more than one variable. The function to be interpolated is known at given points and the interpolation problem consist of yielding values… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Radial basis function — A radial basis function (RBF) is a real valued function whose value depends only on the distance from the origin, so that phi(mathbf{x}) = phi(||mathbf{x}||); or alternatively on the distance from some other point c , called a center , so that… …   Wikipedia

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

  • Falsche Progenie — Klassifikation nach ICD 10 K07.1 Anomalien des Kiefer Schädelbasis Verhältnisses …   Deutsch Wikipedia

  • Maxilläre Retrognathie — Klassifikation nach ICD 10 K07.1 Anomalien des Kiefer Schädelbasis Verhältnisses …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”