Quasi-set theory: Difference between revisions

Revision as of 22:48, 29 December 2012

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 $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 $2 K$ 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 = \iint [{(\frac{\partial^{2} f}{\partial x_{1}^{2}})}^{2} + 2 {(\frac{\partial^{2} f}{\partial x_{1} \partial x_{2}})}^{2} + {(\frac{\partial^{2} f}{\partial x_{2}^{2}})}^{2}] d x_{1} d x_{2}

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:

E_{t p s} (f) = \sum_{i = 1}^{K} ‖ y_{i} - f (x_{i}) ‖^{2} + λ \iint [{(\frac{\partial^{2} f}{\partial x_{1}^{2}})}^{2} + 2 {(\frac{\partial^{2} f}{\partial x_{1} \partial x_{2}})}^{2} + {(\frac{\partial^{2} f}{\partial x_{2}^{2}})}^{2}] d x_{1} 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

Mining Engineer (Excluding Oil ) Truman from Alma, loves to spend time knotting, largest property developers in singapore developers in singapore and stamp collecting. Recently had a family visit to Urnes Stave Church.

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, \dots, 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} φ (‖ x - w_{i} ‖)

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

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:

The interpolation is smooth with derivatives of any order.
The model has 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

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

@@ Line 1: / Line 1: @@
-The author is called Wilber Pegues. One of the extremely best psychics ([http://1.234.36.240/fxac/m001_2/7330 try this site]) issues in the world for him is doing ballet and he'll be starting some thing else along with it. Invoicing is what I do for a residing but I've usually needed my own business. I've usually loved residing in Kentucky but now I'm considering other options.
+{{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 <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]].
+==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 <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:
+:<math>
+	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>
+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:
+:<math>
+	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>
+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>
+	f(x) = \sum_{i = 1}^K c_{i}\varphi(\left\| x - w_{i}\right\|)
+</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. 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===
+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>
+	f_{tps}(z, \alpha) = f_{tps}(z, d, c) = z\cdot d + \sum_{i = 1}^K \phi(\| z - x_i\|)\cdot c_i
+</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.
+If one substitutes the solution for <math>f</math>, <math>E_{tps}</math> becomes:
+:<math>
+	E_{tps}(d,c) = \|Y - Xd - \Phi c\|^2 + \lambda \textrm{Tr}(c^T\Phi c)
+</math>
+where <math>Y</math> and <math>X</math> are just concatenated versions of the point coordinates <math>y_i</math> and <math>x_i</math>, and <math>\Phi</math> is a <math>(K\times K)</math> matrix formed from the <math>\phi (\|x_i - x_j\|)</math>. Each row of each newly formed matrix comes from one of the original vectors. The matrix <math>\Phi</math> 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 <math>c</math>, 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).
+:<math>
+	X = [Q_1 | Q_2] \left(
+	\begin{array}{cc}
+	R \\
+	\end{array}
+	\right)
+</math>
+where Q1 and Q2 are <math>K \times (D+1)</math> and <math>K \times (K-D-1)</math> orthonormal matrices, respectively. The matrix <math>R</math> is upper triangular.
+With the QR decomposition in place, we have
+:<math>
+	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>
+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
+:<math>
+	\hat{c} = Q_2(Q_2^T\Phi Q_2 + \lambda I_{(k-D-1)})^{-1}Q_2^T Y
+</math>
+:<math>
+	\hat{d} = R^{-1}Q_1^T (Y - \Phi \hat{c})
+</math>
+The minimum value of the TPS energy function obtained at the optimum <math>(\hat{c},\hat{d})</math> is
+:<math>
+	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>
+-->
+==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:
+#The interpolation is smooth with derivatives of any order.
+#The model has 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.
+==See also==
+*[[Inverse distance weighting]]
+*[[Radial basis function]]
+*[[Subdivision surface]] (emerging alternative to spline-based surfaces)
+*[[Elastic map]] (a discrete version of the thin plate approximation for [[manifold learning]])
+*[[Spline (mathematics)|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==
+*[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://launchpad.net/templatedtps TPS in templated C++]
+[[Category:Splines]]
+[[Category:Multivariate interpolation]]

Quasi-set theory: Difference between revisions

Revision as of 22:48, 29 December 2012

Contents

Physical analogy

Smoothness measure

Radial basis function

Application

See also

References

External links

Navigation menu

Quasi-set theory: Difference between revisions

Revision as of 22:48, 29 December 2012

Physical analogy

Smoothness measure

Radial basis function

Application

See also

References

External links

Navigation menu

Search