# Box spline

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

• 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 .$
• 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.[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

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.