Box spline

From Wikipedia, the free encyclopedia

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

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\leq 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\leq t<1$ . Then the general box spline is defined as the convolution of distributions associated the single-vector box splines:^[3]

$M_{{{\mathbf {\Xi }}}}=M_{{\xi _{1}}}\ast M_{{\xi _{2}}}\dots \ast M_{{\xi _{N}}}.$

Properties

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\geq 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}.$

Fourier transform of the box spline, in $d$ dimensions, is given by

${\hat {M}}_{{\Xi }}(\omega )=\exp {(-j{\mathbf {c}}_{{\Xi }}\cdot \omega )}\prod _{{n=1}}^{N}{{{\rm {sinc}}}(\xi _{n}\cdot \omega )}.$

Applications

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

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^[6] from the information-theoretic aspects for sampling multidimensional functions. Optimal sampling lattices have been studied in higher dimensions.^[6] Generally, optimal sphere packing and sphere covering lattices^[7] are useful for sampling multivariate functions in 2-D, 3-D and higher dimensions.

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.^[3]^[19]

References

↑ 1.0 1.1 1.2 C. de Boor, K. Höllig, and S. Riemenschneider. Box Splines, volume 98 of Applied Mathematical Sciences. Springer-Verlag, New York, 1993.
↑ 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.0 3.1 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.
↑ De Concini, Corrado, and Claudio Procesi. Topics in hyperplane arrangements, polytopes and box-splines. Springer, 2011.
↑ Zhiqiang Xu, Multivariate splines and polytopes, Journal of Approximation Theory, Vol. 163, Issue 3, March 2011.
↑ 6.0 6.1 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.
↑ J. H. Conway, N. J. A. Sloane. Sphere packings, lattices and groups. Springer, 1999.
↑ 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.0 9.1 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.0 10.1 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.
↑ Entezari, Alireza. Optimal sampling lattices and trivariate box splines. [Vancouver, BC.]: Simon Fraser University, 2007. <http://summit.sfu.ca/item/8178>.
↑ 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.
↑ 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.
↑ Kim, Minho. Symmetric Box-Splines on Root Lattices. [Gainesville, Fla.]: University of Florida, 2008. <http://uf.catalog.fcla.edu/permalink.jsp?20UF021643670>.
↑ 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.
↑ Mirzargar, M.; Entezari, A. (2010). "Voronoi Splines". IEEE Transactions on Signal Processing 58 (9): 4572. doi:10.1109/TSP.2010.2051808.
↑ 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.
↑ 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.
↑ 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.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.