Box spline

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In the mathematical fields of numerical analysis and approximation theory, box splines are piecewise polynomial functions of several variables.[1] Box splines are considered as a multivariate generalization of basis splines (B-splines) and are generally used for multivariate approximation/interpolation. Geometrically, a box spline is the shadow (X-ray) of a hypercube projected down to a lower-dimensional space.[2] Box splines and simplex splines are well studied special cases of polyhedral splines which are defined as shadows of general polytopes.

Definition[edit]

A box spline is a multivariate function (\mathbb{R}^d \to \mathbb{R} ) defined for a set of vectors, \xi \in \mathbb{R}^d, usually gathered in a matrix \mathbf{\Xi} := \left[\xi_1 \dots \xi_N\right] .

When the number of vectors is the same as the dimension of the domain (i.e.,  N = d ) then the box spline is simply the (normalized) indicator function of the parallelepiped formed by the vectors in \mathbf{\Xi}:

 M_{\mathbf{\Xi}}(\mathbf{x}) := \frac{1}{\mid{\det{\Xi}}\mid}\chi_{\mathbf{\Xi}}(\mathbf{x}) = \begin{cases} \frac{1}{\mid{\det{\Xi}}\mid} & \mathbf{x} = \sum_{n=1}^d{t_n \xi_n} \text{ for some } 0 \le t_n < 1 \\ 0 & \text{otherwise}\end{cases}.

Adding a new direction, \xi, to \mathbf{\Xi}, or generally when N > d, the box spline is defined recursively:[1]

 M_{\mathbf{\Xi} \cup \xi}(\mathbf{x}) = \int_0^1{M_{\mathbf{\Xi}}(\mathbf{x}- t \xi) \,  {\rm d}t}.
Examples of bivariate box splines corresponding to 1, 2, 3 and 4 vectors in 2-D.

The box spline M_{\mathbf{\Xi}} can be interpreted as the shadow of the indicator function of the unit hypercube in \mathbb{R}^N when projected down into \mathbb{R}^d. In this view, the vectors \xi \in \mathbf{\Xi} are the geometric projection of the standard basis in \mathbb{R}^N (i.e., the edges of the hypercube) to \mathbb{R}^d.

Considering tempered distributions a box spline associated with a single direction vector is a Dirac-like generalized function supported on t\xi for 0 \le t < 1. Then the general box spline is defined as the convolution of distributions associated the single-vector box splines:

M_{\mathbf{\Xi}} = M_{\xi_1} \ast M_{\xi_2} \dots \ast M_{\xi_N}.

Properties[edit]

  • Let \kappa be the minimum number of directions whose removal from \Xi makes the remaining directions not span \mathbb{R}^d. Then the box spline has \kappa-2 degrees of continuity: M_{\mathbf{\Xi}} \in C^{\kappa-2}(\mathbb{R}^d).[1]
  • When N\ge d (and vectors in \Xi span \mathbb{R}^d) the box spline is a compactly supported function whose support is a zonotope in \mathbb{R}^d formed by the Minkowski sum of the direction vectors {\xi} \in \mathbf{\Xi}.
  • Since zonotopes are centrally symmetric, the support of the box spline is symmetric with respect to its center: \mathbf{c}_\Xi := \frac{1}{2}\sum_{n=1}^N \xi_n .
\hat{M}_{\Xi}(\omega) = \exp{(-j\mathbf{c}_{\Xi}\cdot\omega)}\prod_{n=1}^N{{\rm sinc}(\xi_n\cdot\omega)}.

Applications[edit]

Box splines have been useful in characterization of hyperplane arrangements.[3] Also, box splines can be used to compute the volume of polytopes.[4]

In the context of multidimensional signal processing, box splines provide a flexible framework for designing (non-separable) basis functions acting as multivariate interpolation kernels (reconstruction filters) geometrically tailored to non-Cartesian sampling lattices. This flexibility makes box splines suitable for designing (non-separble) interpolation filters for crystallographic lattices which are optimal[5] from the information-theoretic aspects for sampling multidimensional functions. Optimal sampling lattices have been studied in higher dimensions.[5] Generally, optimal sphere packing and sphere covering lattices[6] are useful for sampling multivariate functions in 2-D, 3-D and higher dimensions.[7]

For example, in the 2-D setting the three-direction box spline[8] is used for interpolation of hexagonally sampled images. In the 3-D setting, four-direction[9] and six-direction[10] box splines are used for interpolation of data sampled on the (optimal) body centered cubic and face centered cubic lattices respectively.[11] The seven-direction box spline can be used for interpolation of data on the Cartesian lattice[12] as well as the body centered cubic lattice.[13] Generalization of the four-[9] and six-direction[10] box splines to higher dimensions[14] can be used to build splines on root lattices. Box splines are key ingredients of hex-splines[15] and Voronoi splines.[16]

They have found applications in high-dimensional filtering, specifically for fast bilateral filtering and non-local means algorithms.[17] Moreover, box splines are used for designing efficient space-variant (i.e., non-convolutional) filters.[18]

Box splines are useful basis functions for image representation in the context of tomographic reconstruction problems as the box spline (function) spaces are closed under X-ray and Radon transforms.[19][20]

In the context of image processing, box spline frames have been shown to be effective in edge detection.[21]

References[edit]

  1. ^ a b c Boor, C.; Höllig, K.; Riemenschneider, S. (1993). Box Splines. Applied Mathematical Sciences 98. doi:10.1007/978-1-4757-2244-4. ISBN 978-1-4419-2834-4. 
  2. ^ Prautzsch, H.; Boehm, W.; Paluszny, M. (2002). "Box splines". Bézier and B-Spline Techniques. Mathematics and Visualization. p. 239. doi:10.1007/978-3-662-04919-8_17. ISBN 978-3-642-07842-2. 
  3. ^ De Concini, C.; Procesi, C. (2010). Topics in Hyperplane Arrangements, Polytopes and Box-Splines. doi:10.1007/978-0-387-78963-7. ISBN 978-0-387-78962-0. 
  4. ^ Xu, Z. (2011). "Multivariate splines and polytopes". Journal of Approximation Theory 163 (3): 377. doi:10.1016/j.jat.2010.10.005. 
  5. ^ a b Kunsch, H. R.; Agrell, E.; Hamprecht, F. A. (2005). "Optimal Lattices for Sampling". IEEE Transactions on Information Theory 51 (2): 634. doi:10.1109/TIT.2004.840864. 
  6. ^ J. H. Conway, N. J. A. Sloane. Sphere packings, lattices and groups. Springer, 1999.
  7. ^ Petersen, D. P.; Middleton, D. (1962). "Sampling and reconstruction of wave-number-limited functions in N-dimensional euclidean spaces". Information and Control 5 (4): 279. doi:10.1016/S0019-9958(62)90633-2. 
  8. ^ Condat, L.; Van De Ville, D. (2006). "Three-directional box-splines: Characterization and efficient evaluation". IEEE Signal Processing Letters 13 (7): 417. doi:10.1109/LSP.2006.871852. 
  9. ^ a b Entezari, A.; Van De Ville, D.; Moller, T. (2008). "Practical Box Splines for Reconstruction on the Body Centered Cubic Lattice". IEEE Transactions on Visualization and Computer Graphics 14 (2): 313–328. doi:10.1109/TVCG.2007.70429. PMID 18192712. 
  10. ^ a b Minho Kim, M.; Entezari, A.; Peters, J. (2008). "Box Spline Reconstruction on the Face-Centered Cubic Lattice". IEEE Transactions on Visualization and Computer Graphics 14 (6): 1523–1530. doi:10.1109/TVCG.2008.115. PMID 18989005. 
  11. ^ Entezari, Alireza. Optimal sampling lattices and trivariate box splines. [Vancouver, BC.]: Simon Fraser University, 2007. <http://summit.sfu.ca/item/8178>.
  12. ^ Entezari, A.; Moller, T. (2006). "Extensions of the Zwart-Powell Box Spline for Volumetric Data Reconstruction on the Cartesian Lattice". IEEE Transactions on Visualization and Computer Graphics 12 (5): 1337–1344. doi:10.1109/TVCG.2006.141. PMID 17080870. 
  13. ^ Minho Kim (2013). "Quartic Box-Spline Reconstruction on the BCC Lattice". IEEE Transactions on Visualization and Computer Graphics 19 (2): 319–330. doi:10.1109/TVCG.2012.130. 
  14. ^ Kim, Minho. Symmetric Box-Splines on Root Lattices. [Gainesville, Fla.]: University of Florida, 2008. <http://uf.catalog.fcla.edu/permalink.jsp?20UF021643670>.
  15. ^ Van De Ville, D.; Blu, T.; Unser, M.; Philips, W.; Lemahieu, I.; Van De Walle, R. (2004). "Hex-Splines: A Novel Spline Family for Hexagonal Lattices". IEEE Transactions on Image Processing 13 (6): 758–772. doi:10.1109/TIP.2004.827231. PMID 15648867. 
  16. ^ Mirzargar, M.; Entezari, A. (2010). "Voronoi Splines". IEEE Transactions on Signal Processing 58 (9): 4572. doi:10.1109/TSP.2010.2051808. 
  17. ^ Baek, J.; Adams, A.; Dolson, J. (2012). "Lattice-Based High-Dimensional Gaussian Filtering and the Permutohedral Lattice". Journal of Mathematical Imaging and Vision 46 (2): 211. doi:10.1007/s10851-012-0379-2. 
  18. ^ Chaudhury, K. N.; MuñOz-Barrutia, A.; Unser, M. (2010). "Fast Space-Variant Elliptical Filtering Using Box Splines". IEEE Transactions on Image Processing 19 (9): 2290–2306. doi:10.1109/TIP.2010.2046953. PMID 20350851. 
  19. ^ Entezari, A.; Nilchian, M.; Unser, M. (2012). "A Box Spline Calculus for the Discretization of Computed Tomography Reconstruction Problems". IEEE Transactions on Medical Imaging 31 (8): 1532–1541. doi:10.1109/TMI.2012.2191417. PMID 22453611. 
  20. ^ Entezari, A.; Unser, M. (2010). "A box spline calculus for computed tomography". 2010 IEEE International Symposium on Biomedical Imaging: From Nano to Macro. p. 600. doi:10.1109/ISBI.2010.5490105. ISBN 978-1-4244-4125-9. 
  21. ^ Guo, W.; Lai, M. J. (2013). "Box Spline Wavelet Frames for Image Edge Analysis". SIAM Journal on Imaging Sciences 6 (3): 1553. doi:10.1137/120881348.