Difference between revisions of "Thin plate spline"

From formulasearchengine
Jump to navigation Jump to search
 
Line 1: Line 1:
{{Confusing|date=December 2006}}
+
{{expert-subject}}
  
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)''' are an [[interpolation]] and [[smoothing]] technique, the generalisation of [[splines]] so that they may be used with two or more dimensions. They were introduced to [[geometric design]] by Duchon (Duchon, 1976).
  
'''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 <math>z</math> 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 <math>x</math> or <math>y</math> coordinates within the plane. In 2D cases, given a set of <math>K</math> corresponding points, the TPS warp is described by <math>2(K+3)</math> parameters which include 6 global affine motion parameters and <math>2K</math> coefficients for correspondences of the control points. These parameters are computed by solving a linear system, in other words, TPS has [[closed-form solution]].
+
==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 <math>z</math> 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 <math>x</math> or <math>y</math> coordinates within the plane. In 2D cases, given a set of <math>K</math> corresponding points, the TPS warp is described by <math>2(K+3)</math> parameters which include 6 global affine motion parameters and <math>2K</math> 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 <math>\lambda</math> to control how non-rigid is allowed for the deformation.
+
==Smoothness measure==
  
==Radial basis function==
+
The TPS arises from consideration of the integral of the square of the second derivative -- this forms its smoothness measure. In the case where <math>x</math> is two dimensional, for interpolation, the TPS fits a mapping function <math>f(x)</math> between corresponding point-sets <math>\{y_i\}</math> and <math>\{x_i\}</math> that minimises the following energy function:
{{Main|Radial basis function}}
 
 
 
Given a set of control points <math>\{w_{i}, i = 1,2, \ldots,K\}</math>, a radial basis function basically defines a spatial mapping which maps any location <math>x</math> in space to a new location <math>f(x)</math>, represented by,
 
 
:<math>
 
:<math>
f(x) = \sum_{i = 1}^K c_{i}\varphi(\left\| x - w_{i}\right\|)
+
E = \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
 
</math>
 
</math>
where <math>\left\|\cdot\right\|</math> denotes the usual [[Norm (mathematics)|Euclidean norm]] and <math>\{c_{i}\}</math> is a set of mapping coefficients.
 
One possible choice for the kernel function <math>\varphi</math> is the thin plate spline <math>\varphi(r) = r^2 \log r</math>. It has a more global nature than the Gaussian kernel <math>\varphi(r) = \exp(-r^2/\sigma^2)</math>, 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. Note that a thin plate spline is generally understood as a function minimizing the integral of the squared second derivative, typically in two dimensions.  This corresponds to the radial basis kernel <math>\varphi(r) = r^2 \log r</math>.  Other choices of radial basis kernel produce interpolation that would not normally be described as a thin plate spline.  For example the Gaussian kernel corresponds to minimization of an infinite sum of derivative terms.
 
  
==Thin plate spline==
+
The smoothing variant, correspondingly, uses a tuning parameter <math>\lambda</math> to control how non-rigid is allowed for the deformation, balancing the aforementioned criterion with the measure of goodness of fit, thus minimising:
===Smoothness 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 <math>f(x)</math> between corresponding point-sets <math>\{y_i\}</math> and <math>\{x_i\}</math> by minimizing the following energy function:  
 
 
:<math>
 
:<math>
E = \iint\left[\left(\frac{\partial^2 f}{\partial x^2}\right)^2 + 2\left(\frac{\partial^2 f}{\partial xy}\right)^2 + \left(\frac{\partial^2 f}{\partial y^2}\right)^2 \right] \textrm{d} x \, \textrm{d}y
+
E_{tps}(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
 
</math>
 
</math>
And for a smoothing TPS, it is
+
 
 +
 
 +
For this variational problem, it can be shown that there exists a unique minimizer <math>f</math> (Wahba,1990).The [[finite element]] discretization of this variational problem, the method of [[elastic map]]s, is used for [[data mining]] and [[nonlinear dimensionality reduction]].
 +
 
 +
==Radial basis function==
 +
{{Main|Radial basis function}}
 +
 
 +
The Thin Plate Spline has a natural representation in terms of radial basis functions. Given a set of control points <math>\{w_{i}, i = 1,2, \ldots,K\}</math>, a radial basis function basically defines a spatial mapping which maps any location <math>x</math> in space to a new location <math>f(x)</math>, represented by,
 
:<math>
 
:<math>
E_{tps} = \sum_{i=1}^K \|y_i - f(x_i) \|^2 + \lambda \iint\left[\left(\frac{\partial^2 f}{\partial x^2}\right)^2 + 2\left(\frac{\partial^2 f}{\partial x \partial y}\right)^2 + \left(\frac{\partial^2 f}{\partial y^2}\right)^2 \right] \textrm{d} x \, \textrm{d}y
+
f(x) = \sum_{i = 1}^K c_{i}\varphi(\left\| x - w_{i}\right\|)
</math>
 
Then smoothing TPS is defined as
 
:<math>
 
f_{tps} = \arg\min_f E_{tps}
 
 
</math>
 
</math>
For this variational problem, it can be shown that there exists a unique minimizer <math>f</math> (Wahba,1990) <!--(''can someone explain this in detail? Thanks!'')--> with a fixed weight parameter <math>\lambda</math> which is presented in the next section. The [[finite element]] discretization of this variational problem, the method of [[Elastic map|elastic maps]], is used for [[data mining]] and [[nonlinear dimensionality reduction]].
+
where <math>\left\|\cdot\right\|</math> denotes the usual [[Norm (mathematics)|Euclidean norm]] and <math>\{c_{i}\}</math> is a set of mapping coefficients. The TPS corresponds to the radial basis kernel <math>\varphi(r) = r^2 \log r</math>.
  
 +
<!--Commenting out this section... I'm not sure this is correct!
 
===Spline===
 
===Spline===
Suppose the points are in 2D (D = 2). One can use ''homogeneous coordinates'' for the point-set where a point <math>y_{i}</math> is represented as a vector <math>(1, y_{ix}, y_{iy})</math>. The unique minimizer <math>f</math> is parameterized by <math>\alpha</math> which comprises two matrices <math>d</math> and <math>c</math> (<math>\alpha = \{d,c\}</math>).
+
Suppose the points are in 2 dimensions (<math>D = 2</math>). One can use ''homogeneous coordinates'' for the point-set where a point <math>y_{i}</math> is represented as a vector <math>(1, y_{ix}, y_{iy})</math>. The unique minimizer <math>f</math> is parameterized by <math>\alpha</math> which comprises two matrices <math>d</math> and <math>c</math> (<math>\alpha = \{d,c\}</math>).
 
:<math>
 
:<math>
 
f_{tps}(z, \alpha) = f_{tps}(z, d, c) = z\cdot d + \sum_{i = 1}^K \phi(\| z - x_i\|)\cdot c_i
 
f_{tps}(z, \alpha) = f_{tps}(z, d, c) = z\cdot d + \sum_{i = 1}^K \phi(\| z - x_i\|)\cdot c_i
 
</math>
 
</math>
where d is a <math>(D+1)\times(D+1)</math> matrix representing the affine transformation (hence <math>z</math> is a <math>1\times (D+1)</math> vector) and c is a <math>K\times (D+1)</math> warping coefficient matrix representing the non-affine deformation. The kernel function <math>\phi(z)</math> is a <math>1\times K</math> vector for each point <math>z</math>, where each entry <math>\phi_i(z) = \|z - x_i\|^2 \log \|z - x_i\|</math> for each (<math>D</math>) dimensions.  Note that for TPS, the control points <math>\{w_i\}</math> are chosen to be the same as the set of points to be warped <math>\{x_i\}</math>, so we already use <math>\{x_i\}</math> in the place of the control points.  
+
where d is a <math>(D+1)\times(D+1)</math> matrix representing the affine transformation (hence <math>z</math> is a <math>1\times (D+1)</math> vector) and c is a <math>K\times (D+1)</math> warping coefficient matrix representing the non-affine deformation. The kernel function <math>\phi(z)</math> is a <math>1\times K</math> vector for each point <math>z</math>, where each entry <math>\phi_i(z) = \|z - x_i\|^2 \log \|z - x_i\|</math> for each (<math>D</math>) dimensions.  Note that for TPS, the control points <math>\{w_i\}</math> are chosen to be the same as the set of points to be warped <math>\{x_i\}</math>, so we already use <math>\{x_i\}</math> in the place of the control points.
  
 
If one substitutes the solution for <math>f</math>, <math>E_{tps}</math> becomes:
 
If one substitutes the solution for <math>f</math>, <math>E_{tps}</math> becomes:
Line 63: Line 62:
 
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)
 
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)
 
</math>
 
</math>
where <math>\gamma </math> is a <math>(K-D-1)\times (D+1)</math> matrix. Setting <math>c=Q_2\gamma</math> (which in turn implies that <math>X^T c = 0</math>) 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).
+
where <math>\gamma </math> is a <math>(K-D-1)\times (D+1)</math> matrix. Setting <math>c=Q_2\gamma</math> (which in turn implies that <math>X^T c = 0</math>) 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 <math>\gamma</math> and then w.r.t. <math>d</math>. By applying [[Tikhonov regularization]] we have
 
The least-squares energy function in the last equation can be first minimized w.r.t <math>\gamma</math> and then w.r.t. <math>d</math>. By applying [[Tikhonov regularization]] we have
Line 76: Line 75:
 
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]
 
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]
 
</math>
 
</math>
 +
-->
  
 
==Application==
 
==Application==
 
TPS has been widely used as the non-rigid transformation model in image
 
TPS has been widely used as the non-rigid transformation model in image
alignment and shape matching.  
+
alignment and shape matching.
  
 
The popularity of TPS comes from a number of advantages:
 
The popularity of TPS comes from a number of advantages:
Line 86: Line 86:
 
#It has closed-form solutions for both warping and parameter estimation.
 
#It has closed-form solutions for both warping and parameter estimation.
 
#There is a physical explanation for its energy function.
 
#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 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
 
  
 
==See also==
 
==See also==
Line 99: Line 94:
 
*[[Spline (mathematics)|Spline]]  
 
*[[Spline (mathematics)|Spline]]  
 
*[[Polyharmonic spline]] (the thin-plate-spline is a special case of a polyharmonic spline)
 
*[[Polyharmonic spline]] (the thin-plate-spline is a special case of a polyharmonic spline)
 +
 +
==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 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
  
 
==External links==
 
==External links==
Line 105: Line 105:
 
*[http://elonen.iki.fi/code/tpsdemo/index.html TPS in C++]
 
*[http://elonen.iki.fi/code/tpsdemo/index.html TPS in C++]
 
*[http://launchpad.net/templatedtps TPS in templated C++]
 
*[http://launchpad.net/templatedtps TPS in templated C++]
*[http://ricanet.com/new/data/hw/vision/tps1.ppt TPS Powerpoint]
 
  
 
[[Category:Splines]]
 
[[Category:Splines]]
 
[[Category:Multivariate interpolation]]
 
[[Category:Multivariate interpolation]]

Revision as of 15:53, 4 November 2013

Template:Expert-subject

Thin plate splines (TPS) are an interpolation and smoothing technique, the generalisation of splines so that they may be used with two or more dimensions. They were introduced to geometric design by Duchon (Duchon, 1976).

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 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 or coordinates within the plane. In 2D cases, given a set of corresponding points, the TPS warp is described by parameters which include 6 global affine motion parameters and 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 is two dimensional, for interpolation, the TPS fits a mapping function between corresponding point-sets and that minimises the following energy function:

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


For this variational problem, it can be shown that there exists a unique minimizer (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

{{#invoke:main|main}}

The Thin Plate Spline has a natural representation in terms of radial basis functions. Given a set of control points , a radial basis function basically defines a spatial mapping which maps any location in space to a new location , represented by,

where denotes the usual Euclidean norm and is a set of mapping coefficients. The TPS corresponds to the radial basis kernel .


Application

TPS has been widely used as the non-rigid transformation model in image alignment 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.
  4. There is a physical explanation for its energy function.

See also

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

External links