Box spline

Last updated

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.

Contents

Definition

A box spline is a multivariate function defined for a set of vectors, usually gathered in a matrix

When the number of vectors is the same as the dimension of the domain (i.e., ) then the box spline is simply the (normalized) indicator function of the parallelepiped formed by the vectors in :

Adding a new direction, to or generally when the box spline is defined recursively: [1]

Examples of bivariate box splines corresponding to 1, 2, 3 and 4 vectors in 2-D. Box Splines Square Grid Annotated Dark.png
Examples of bivariate box splines corresponding to 1, 2, 3 and 4 vectors in 2-D.

The box spline can be interpreted as the shadow of the indicator function of the unit hypercube in when projected down into In this view, the vectors are the geometric projection of the standard basis in (i.e., the edges of the hypercube) to

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

Properties

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. [3] Also, box splines can be used to compute the volume of polytopes. [4]

In the context of multidimensional signal processing, box splines can provide multivariate interpolation kernels (reconstruction filters) tailored to non-Cartesian sampling lattices, [5] and crystallographic lattices (root lattices) that include many information-theoretically optimal sampling lattices. [6] Generally, optimal sphere packing and sphere covering lattices [7] are useful for sampling multivariate functions in 2-D, 3-D and higher dimensions. [8] In the 2-D setting the three-direction box spline [9] is used for interpolation of hexagonally sampled images. In the 3-D setting, four-direction [10] and six-direction [11] box splines are used for interpolation of data sampled on the (optimal) body-centered cubic and face-centered cubic lattices respectively. [5] The seven-direction box spline [12] has been used for modelling surfaces and can be used for interpolation of data on the Cartesian lattice [13] as well as the body centered cubic lattice. [14] Generalization of the four- [10] and six-direction [11] box splines to higher dimensions [15] can be used to build splines on root lattices. [16] Box splines are key ingredients of hex-splines [17] and Voronoi splines [18] that, however, are not refinable.

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

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. [21] [22] 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. [21]

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

Related Research Articles

<span class="mw-page-title-main">Discrete Fourier transform</span> Type of Fourier transform in discrete mathematics

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. An inverse DFT (IDFT) is a Fourier series, using the DTFT samples as coefficients of complex sinusoids at the corresponding DTFT frequencies. It has the same sample-values as the original input sequence. The DFT is therefore said to be a frequency domain representation of the original input sequence. If the original sequence spans all the non-zero values of a function, its DTFT is continuous, and the DFT provides discrete samples of one cycle. If the original sequence is one cycle of a periodic function, the DFT provides all the non-zero values of one DTFT cycle.

<span class="mw-page-title-main">Multivariate normal distribution</span> Generalization of the one-dimensional normal distribution to higher dimensions

In probability theory and statistics, the multivariate normal distribution, multivariate Gaussian distribution, or joint normal distribution is a generalization of the one-dimensional (univariate) normal distribution to higher dimensions. One definition is that a random vector is said to be k-variate normally distributed if every linear combination of its k components has a univariate normal distribution. Its importance derives mainly from the multivariate central limit theorem. The multivariate normal distribution is often used to describe, at least approximately, any set of (possibly) correlated real-valued random variables each of which clusters around a mean value.

In probability theory and statistics, a Gaussian process is a stochastic process, such that every finite collection of those random variables has a multivariate normal distribution. The distribution of a Gaussian process is the joint distribution of all those random variables, and as such, it is a distribution over functions with a continuous domain, e.g. time or space.

<span class="mw-page-title-main">Radon transform</span> Integral transform

In mathematics, the Radon transform is the integral transform which takes a function f defined on the plane to a function Rf defined on the (two-dimensional) space of lines in the plane, whose value at a particular line is equal to the line integral of the function over that line. The transform was introduced in 1917 by Johann Radon, who also provided a formula for the inverse transform. Radon further included formulas for the transform in three dimensions, in which the integral is taken over planes. It was later generalized to higher-dimensional Euclidean spaces and more broadly in the context of integral geometry. The complex analogue of the Radon transform is known as the Penrose transform. The Radon transform is widely applicable to tomography, the creation of an image from the projection data associated with cross-sectional scans of an object.

<span class="mw-page-title-main">Sinc function</span> Special mathematical function defined as sin(x)/x

In mathematics, physics and engineering, the sinc function, denoted by sinc(x), has two forms, normalized and unnormalized.

Observability is a measure of how well internal states of a system can be inferred from knowledge of its external outputs.

<span class="mw-page-title-main">Filter bank</span> Tool for Digital Signal Processing

In signal processing, a filter bank is an array of bandpass filters that separates the input signal into multiple components, each one carrying a single frequency sub-band of the original signal. One application of a filter bank is a graphic equalizer, which can attenuate the components differently and recombine them into a modified version of the original signal. The process of decomposition performed by the filter bank is called analysis ; the output of analysis is referred to as a subband signal with as many subbands as there are filters in the filter bank. The reconstruction process is called synthesis, meaning reconstitution of a complete signal resulting from the filtering process.

In directional statistics, the von Mises–Fisher distribution, is a probability distribution on the -sphere in . If the distribution reduces to the von Mises distribution on the circle.

In the field of mathematics known as differential geometry, a generalized complex structure is a property of a differential manifold that includes as special cases a complex structure and a symplectic structure. Generalized complex structures were introduced by Nigel Hitchin in 2002 and further developed by his students Marco Gualtieri and Gil Cavalcanti.

Characteristic modes (CM) form a set of functions which, under specific boundary conditions, diagonalizes operator relating field and induced sources. Under certain conditions, the set of the CM is unique and complete (at least theoretically) and thereby capable of describing the behavior of a studied object in full.

<span class="mw-page-title-main">Peridynamics</span>

Peridynamics is a non-local formulation of continuum mechanics that is oriented toward deformations with discontinuities, especially fractures. Originally, bond-based peridynamic has been introduced, wherein, internal interactions forces between a material point and all the other ones with which it can interact, are modeled as a central forces field. This type of forces field can be imagined as a mesh of bonds connecting each point of the body with every other interacting points within a certain distance which depends on material property, called peridynamic horizon. Later, to overcome bond-based framework limitations for the material Poisson’s ratio, state-base peridynamics, has been formulated. Its characteristic feature is that the force exchanged between a point and another one is influenced by the deformation state of all other bonds relative to its interaction zone.

Algebraic signal processing (ASP) is an emerging area of theoretical signal processing (SP). In the algebraic theory of signal processing, a set of filters is treated as an (abstract) algebra, a set of signals is treated as a module or vector space, and convolution is treated as an algebra representation. The advantage of algebraic signal processing is its generality and portability.

Coordinate descent is an optimization algorithm that successively minimizes along coordinate directions to find the minimum of a function. At each iteration, the algorithm determines a coordinate or coordinate block via a coordinate selection rule, then exactly or inexactly minimizes over the corresponding coordinate hyperplane while fixing all other coordinates or coordinate blocks. A line search along the coordinate direction can be performed at the current iterate to determine the appropriate step size. Coordinate descent is applicable in both differentiable and derivative-free contexts.

In digital signal processing, multidimensional sampling is the process of converting a function of a multidimensional variable into a discrete collection of values of the function measured on a discrete set of points. This article presents the basic result due to Petersen and Middleton on conditions for perfectly reconstructing a wavenumber-limited function from its measurements on a discrete lattice of points. This result, also known as the Petersen–Middleton theorem, is a generalization of the Nyquist–Shannon sampling theorem for sampling one-dimensional band-limited functions to higher-dimensional Euclidean spaces.

<span class="mw-page-title-main">Point-set registration</span>

In computer vision, pattern recognition, and robotics, point-set registration, also known as point-cloud registration or scan matching, is the process of finding a spatial transformation that aligns two point clouds. The purpose of finding such a transformation includes merging multiple data sets into a globally consistent model, and mapping a new measurement to a known data set to identify features or to estimate its pose. Raw 3D point cloud data are typically obtained from Lidars and RGB-D cameras. 3D point clouds can also be generated from computer vision algorithms such as triangulation, bundle adjustment, and more recently, monocular image depth estimation using deep learning. For 2D point set registration used in image processing and feature-based image registration, a point set may be 2D pixel coordinates obtained by feature extraction from an image, for example corner detection. Point cloud registration has extensive applications in autonomous driving, motion estimation and 3D reconstruction, object detection and pose estimation, robotic manipulation, simultaneous localization and mapping (SLAM), panorama stitching, virtual and augmented reality, and medical imaging.

In applied mathematical analysis, shearlets are a multiscale framework which allows efficient encoding of anisotropic features in multivariate problem classes. Originally, shearlets were introduced in 2006 for the analysis and sparse approximation of functions . They are a natural extension of wavelets, to accommodate the fact that multivariate functions are typically governed by anisotropic features such as edges in images, since wavelets, as isotropic objects, are not capable of capturing such phenomena.

This article provides a short survey of the concepts, principles and applications of Multirate Filter Banks and Multidimensional Directional Filter Banks.

<span class="mw-page-title-main">Sparse dictionary learning</span> Representation learning method

Sparse dictionary learning is a representation learning method which aims at finding a sparse representation of the input data in the form of a linear combination of basic elements as well as those basic elements themselves. These elements are called atoms and they compose a dictionary. Atoms in the dictionary are not required to be orthogonal, and they may be an over-complete spanning set. This problem setup also allows the dimensionality of the signals being represented to be higher than the one of the signals being observed. The above two properties lead to having seemingly redundant atoms that allow multiple representations of the same signal but also provide an improvement in sparsity and flexibility of the representation.

<span class="mw-page-title-main">L1-norm principal component analysis</span>

L1-norm principal component analysis (L1-PCA) is a general method for multivariate data analysis. L1-PCA is often preferred over standard L2-norm principal component analysis (PCA) when the analyzed data may contain outliers.

The Korkine–Zolotarev (KZ) lattice basis reduction algorithm or Hermite–Korkine–Zolotarev (HKZ) algorithm is a lattice reduction algorithm.

References

  1. 1 2 3 Boor, C.; Höllig, K.; Riemenschneider, S. (1993). Box Splines. Applied Mathematical Sciences. Vol. 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. pp. 239–258. 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–387. arXiv: 0806.1127 . doi:10.1016/j.jat.2010.10.005. S2CID   10063913.
  5. 1 2 Entezari, Alireza. Optimal sampling lattices and trivariate box splines. [Vancouver, BC.]: Simon Fraser University, 2007. <http://summit.sfu.ca/item/8178>.
  6. 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. S2CID   16942177.
  7. J. H. Conway, N. J. A. Sloane. Sphere packings, lattices and groups. Springer, 1999.
  8. 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 .
  9. Condat, L.; Van De Ville, D. (2006). "Three-directional box-splines: Characterization and efficient evaluation" (PDF). IEEE Signal Processing Letters. 13 (7): 417. Bibcode:2006ISPL...13..417C. doi:10.1109/LSP.2006.871852. S2CID   9023102.
  10. 1 2 Entezari, A.; Van De Ville, D.; Moller, T. (2008). "Practical Box Splines for Reconstruction on the Body Centered Cubic Lattice" (PDF). IEEE Transactions on Visualization and Computer Graphics. 14 (2): 313–328. doi:10.1109/TVCG.2007.70429. PMID   18192712. S2CID   6395127.
  11. 1 2 Minho Kim, M.; Entezari, A.; Peters, Jorg (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. S2CID   194024.
  12. Peters, Jorg; Wittman, M. (1997). "Box-spline based CSG blends". Proceedings of the fourth ACM symposium on Solid modeling and applications - SMA '97. pp.  195. doi:10.1145/267734.267783. ISBN   0897919467. S2CID   10064302.
  13. 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. S2CID   232110.
  14. 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. PMID   22614329. S2CID   7338997.
  15. Kim, Minho. Symmetric Box-Splines on Root Lattices. [Gainesville, Fla.]: University of Florida, 2008. <http://uf.catalog.fcla.edu/permalink.jsp?20UF021643670>.
  16. Kim, M.; Peters, Jorg (2011). "Symmetric box-splines on root lattices". Journal of Computational and Applied Mathematics. 235 (14): 3972. doi: 10.1016/j.cam.2010.11.027 .
  17. 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" (PDF). IEEE Transactions on Image Processing. 13 (6): 758–772. Bibcode:2004ITIP...13..758V. doi:10.1109/TIP.2004.827231. PMID   15648867. S2CID   9832708.
  18. Mirzargar, M.; Entezari, A. (2010). "Voronoi Splines". IEEE Transactions on Signal Processing. 58 (9): 4572. Bibcode:2010ITSP...58.4572M. doi:10.1109/TSP.2010.2051808. S2CID   9712416.
  19. 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. hdl: 1721.1/105344 . S2CID   16576761.
  20. 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. arXiv: 1003.2022 . Bibcode:2010ITIP...19.2290C. doi:10.1109/TIP.2010.2046953. PMID   20350851. S2CID   16383503.
  21. 1 2 Entezari, A.; Nilchian, M.; Unser, M. (2012). "A Box Spline Calculus for the Discretization of Computed Tomography Reconstruction Problems" (PDF). IEEE Transactions on Medical Imaging. 31 (8): 1532–1541. doi:10.1109/TMI.2012.2191417. PMID   22453611. S2CID   3787118.
  22. 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. S2CID   17368057.
  23. 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. S2CID   2708993.