Box spline

{{Short description|Generalization of basis splines (B-splines) to multiple variables}}

In the mathematical fields of numerical analysis and approximation theory, box splines are piecewise polynomial functions of several variables.{{Cite book | doi = 10.1007/978-1-4757-2244-4| title = Box Splines| volume = 98| series = Applied Mathematical Sciences| year = 1993| last1 = Boor | first1 = C. | last2 = Höllig | first2 = K. | last3 = Riemenschneider | first3 = S. | isbn = 978-1-4419-2834-4}} 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.{{Cite book | last1 = Prautzsch | first1 = H. | last2 = Boehm | first2 = W. | last3 = Paluszny | first3 = M. | doi = 10.1007/978-3-662-04919-8_17 | chapter = Box splines | title = Bézier and B-Spline Techniques | series = Mathematics and Visualization | pages = 239–258 | year = 2002 | isbn = 978-3-642-07842-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} &\text{if } \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:

: $M_{\mathbf{\Xi} \cup \xi}(\mathbf{x}) = \int_0^1 M_{\mathbf{\Xi}}(\mathbf{x}- t \xi) \, {\rm d}t.$

File:Box Splines Square Grid Annotated Dark.png

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} \ast \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)$ .
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 \operatorname{sinc}(\xi_n\cdot\omega).$

Applications

For applications, linear combinations of shifts of one or more box splines on a lattice are used. Such splines are efficient, more so than linear combinations of simplex splines, because they are refinable and, by definition, shift invariant. They therefore form the starting point for many subdivision surface constructions.

Box splines have been useful in characterization of hyperplane arrangements.{{Cite book | doi = 10.1007/978-0-387-78963-7| title = Topics in Hyperplane Arrangements, Polytopes and Box-Splines| year = 2010| last1 = De Concini | first1 = C. | last2 = Procesi | first2 = C. | isbn = 978-0-387-78962-0| url = http://swbplus.bsz-bw.de/bsz333462971inh.htm}} Also, box splines can be

used to compute the volume of polytopes.{{Cite journal | doi = 10.1016/j.jat.2010.10.005| title = Multivariate splines and polytopes| journal = Journal of Approximation Theory| volume = 163| issue = 3| pages = 377–387| year = 2011| last1 = Xu | first1 = Z. | arxiv = 0806.1127| s2cid = 10063913}}

In the context of multidimensional signal processing, box splines can provide multivariate interpolation kernels (reconstruction filters) tailored to non-Cartesian sampling lattices,Entezari, Alireza. Optimal sampling lattices and trivariate box splines. [Vancouver, BC.]: Simon Fraser University, 2007. . and crystallographic lattices (root lattices) that include many information-theoretically optimal sampling lattices.{{Cite journal | last1 = Kunsch | first1 = H. R. | last2 = Agrell | first2 = E. | last3 = Hamprecht | first3 = F. A. | doi = 10.1109/TIT.2004.840864 | title = Optimal Lattices for Sampling | journal = IEEE Transactions on Information Theory | volume = 51 | issue = 2 | pages = 634 | year = 2005 | s2cid = 16942177 | url = https://research.chalmers.se/en/publication/11977 }} Generally, optimal sphere packing and sphere covering latticesJ. H. Conway, N. J. A. Sloane. Sphere packings, lattices and groups. Springer, 1999. are useful for sampling multivariate functions in 2-D, 3-D and higher dimensions.{{Cite journal | doi = 10.1016/S0019-9958(62)90633-2| title = Sampling and reconstruction of wave-number-limited functions in N-dimensional euclidean spaces| journal = Information and Control| volume = 5| issue = 4| pages = 279| year = 1962| last1 = Petersen | first1 = D. P. | last2 = Middleton | first2 = D. | doi-access = free}}

In the 2-D setting the three-direction box spline{{Cite journal | last1 = Condat | first1 = L. | last2 = Van De Ville | first2 = D. | doi = 10.1109/LSP.2006.871852 | title = Three-directional box-splines: Characterization and efficient evaluation | journal = IEEE Signal Processing Letters | volume = 13 | issue = 7 | pages = 417 | year = 2006 | bibcode = 2006ISPL...13..417C | s2cid = 9023102 | url = http://infoscience.epfl.ch/record/130318/files/condat0601.pdf }} is used for interpolation of hexagonally sampled images. In the 3-D setting, four-direction{{Cite journal | last1 = Entezari | first1 = A. | last2 = Van De Ville | first2 = D. | last3 = Moller | first3 = T. | doi = 10.1109/TVCG.2007.70429 | title = Practical Box Splines for Reconstruction on the Body Centered Cubic Lattice | journal = IEEE Transactions on Visualization and Computer Graphics | volume = 14 | issue = 2 | pages = 313–328 | year = 2008 | pmid = 18192712| s2cid = 6395127 | url = http://infoscience.epfl.ch/record/130345/files/entezari0801.pdf }} and six-direction{{Cite journal | last1 = Minho Kim | first1 = M. | last2 = Entezari | first2 = A. | last3 = Peters | first3 = Jorg | doi = 10.1109/TVCG.2008.115 | title = Box Spline Reconstruction on the Face-Centered Cubic Lattice | journal = IEEE Transactions on Visualization and Computer Graphics | volume = 14 | issue = 6 | pages = 1523–1530 | year = 2008 | pmid = 18989005| s2cid = 194024 | citeseerx = 10.1.1.216.408 }} box splines are used for interpolation of data sampled on the (optimal) body-centered cubic and face-centered cubic lattices respectively. The seven-direction box spline{{Cite book| doi = 10.1145/267734.267783| chapter = Box-spline based CSG blends| title = Proceedings of the fourth ACM symposium on Solid modeling and applications - SMA '97| pages = [https://archive.org/details/proceedings0000symp_g3s1/page/195 195]| year = 1997| last1 = Peters| first1 = Jorg| last2 = Wittman| first2 = M.| isbn = 0897919467| s2cid = 10064302| chapter-url = https://archive.org/details/proceedings0000symp_g3s1/page/195}} has been used for modelling surfaces and can be used for interpolation of data on the Cartesian lattice{{Cite journal | last1 = Entezari | first1 = A. | last2 = Moller | first2 = T. | doi = 10.1109/TVCG.2006.141 | title = Extensions of the Zwart-Powell Box Spline for Volumetric Data Reconstruction on the Cartesian Lattice | journal = IEEE Transactions on Visualization and Computer Graphics | volume = 12 | issue = 5 | pages = 1337–1344 | year = 2006 | pmid = 17080870| s2cid = 232110 }} as well as the body centered cubic lattice.{{Cite journal | last1 = Minho Kim | doi = 10.1109/TVCG.2012.130 | title = Quartic Box-Spline Reconstruction on the BCC Lattice | journal = IEEE Transactions on Visualization and Computer Graphics | volume = 19 | issue = 2 | pages = 319–330 | year = 2013 | pmid = 22614329| s2cid = 7338997 }} Generalization of the four- and six-direction box splines to higher dimensionsKim, Minho. Symmetric Box-Splines on Root Lattices. [Gainesville, Fla.]: University of Florida, 2008. . can be used to build splines on root lattices.{{Cite journal | doi = 10.1016/j.cam.2010.11.027| title = Symmetric box-splines on root lattices| journal = Journal of Computational and Applied Mathematics| volume = 235| issue = 14| pages = 3972| year = 2011| last1 = Kim | first1 = M. | last2 = Peters | first2 = Jorg | doi-access = free}} Box splines are key ingredients of hex-splines{{Cite journal | last1 = Van De Ville | first1 = D. | last2 = Blu | first2 = T. | last3 = Unser | first3 = M. | last4 = Philips | first4 = W. | last5 = Lemahieu | first5 = I. | last6 = Van De Walle | first6 = R. | doi = 10.1109/TIP.2004.827231 | title = Hex-Splines: A Novel Spline Family for Hexagonal Lattices | journal = IEEE Transactions on Image Processing | volume = 13 | issue = 6 | pages = 758–772 | year = 2004 | pmid = 15648867| bibcode = 2004ITIP...13..758V | s2cid = 9832708 | url = http://miplab.unige.ch/pub/vandeville0402.pdf }} and Voronoi splines{{Cite journal | last1 = Mirzargar | first1 = M. | last2 = Entezari | first2 = A. | doi = 10.1109/TSP.2010.2051808 | title = Voronoi Splines | journal = IEEE Transactions on Signal Processing | volume = 58 | issue = 9 | pages = 4572 | year = 2010 | bibcode = 2010ITSP...58.4572M | s2cid = 9712416 }} that, however, are not refinable.

Box splines have found applications in high-dimensional filtering, specifically for fast bilateral filtering and non-local means algorithms.{{Cite journal | last1 = Baek | first1 = J. | last2 = Adams | first2 = A. | last3 = Dolson | first3 = J. | doi = 10.1007/s10851-012-0379-2 | title = Lattice-Based High-Dimensional Gaussian Filtering and the Permutohedral Lattice | journal = Journal of Mathematical Imaging and Vision | volume = 46 | issue = 2 | pages = 211 | year = 2012 | hdl = 1721.1/105344 | s2cid = 16576761 | hdl-access = free }} Moreover, box splines are used for designing efficient space-variant (i.e., non-convolutional) filters.{{Cite journal | last1 = Chaudhury | first1 = K. N. | last2 = MuñOz-Barrutia | first2 = A.|author2-link=Arrate Muñoz Barrutia | last3 = Unser | first3 = M. | doi = 10.1109/TIP.2010.2046953 | title = Fast Space-Variant Elliptical Filtering Using Box Splines | journal = IEEE Transactions on Image Processing | volume = 19 | issue = 9 | pages = 2290–2306 | year = 2010 | pmid = 20350851| arxiv = 1003.2022 | bibcode = 2010ITIP...19.2290C | s2cid = 16383503 }}

Box splines are useful basis functions for image representation in the context of tomographic reconstruction problems as the spline spaces generated by box splines spaces are closed under X-ray and Radon transforms.{{Cite journal | last1 = Entezari | first1 = A. | last2 = Nilchian | first2 = M. | last3 = Unser | first3 = M. | doi = 10.1109/TMI.2012.2191417 | title = A Box Spline Calculus for the Discretization of Computed Tomography Reconstruction Problems | journal = IEEE Transactions on Medical Imaging | volume = 31 | issue = 8 | pages = 1532–1541 | year = 2012 | pmid = 22453611| s2cid = 3787118 | url = http://bigwww.epfl.ch/publications/entezari1201.pdf }}{{Cite book | last1 = Entezari | first1 = A. | last2 = Unser | first2 = M. | doi = 10.1109/ISBI.2010.5490105 | chapter = A box spline calculus for computed tomography | title = 2010 IEEE International Symposium on Biomedical Imaging: From Nano to Macro | pages = 600 | year = 2010 | isbn = 978-1-4244-4125-9 | s2cid = 17368057 | url = http://infoscience.epfl.ch/record/211450 }} In this application while the signal is represented in shift-invariant spaces, the projections are obtained, in closed-form, by non-uniform translates of box splines.

In the context of image processing, box spline frames have been shown to be effective in edge detection.{{Cite journal | doi = 10.1137/120881348| title = Box Spline Wavelet Frames for Image Edge Analysis| journal = SIAM Journal on Imaging Sciences| volume = 6| issue = 3| pages = 1553| year = 2013| last1 = Guo | first1 = W. | last2 = Lai | first2 = M. J. | s2cid = 2708993| url = https://zenodo.org/record/894468}}

References

Category:Splines (mathematics)