On the Approximation Power of Splines: Orthogonal Versus Hexagonal Lattices

Dimitri Van De Ville, T. Blu, Michaël UnserInfoscience 2003

Abstract

Recently, we have proposed a novel family of bivariate, non-separable splines. These splines, called "hex-splines," have been designed to deal with hexagonally sampled data. Incorporating the shape of the Voronoi cell of a hexagonal lattice, they preserve the twelve-fold symmetry of the hexagon tiling cell. Similar to B-splines, we can use them to provide a link between the discrete and the continuous domain, which is required for many fundamental operations such as interpolation and resampling. The question we answer in this paper is "How well do the hex-splines approximate a given function in the continuous domain?" and more specifically "How do they compare to separable B-splines deployed on a lattice with the same sampling density?"

Introduction

In digital signal and image processing, the ability to transition accurately between discrete samples and continuous functions is paramount. While the majority of current systems rely on orthogonal (square) grids, hexagonal lattices have long been recognized for their superior sampling efficiency and higher symmetry. To bridge the gap between hexagonal sampling and continuous representation, the authors previously introduced hex-splines: a family of bivariate, non-separable splines specifically engineered for hexagonal geometries.

This paper provides a formal mathematical evaluation of these hex-splines, specifically focusing on their approximation power. By quantifying how quickly the approximation error vanishes as the sampling density increases, we can determine if hex-splines offer a functional advantage over the industry-standard separable B-splines used on square grids.

Methodology

The research utilizes a framework from approximation theory to conduct a comparative analysis across three distinct scenarios:

  1. Hex-splines on a hexagonal lattice.
  2. "Slanted" B-splines on the same hexagonal lattice (B-splines shifted to fit a rhomboid support).
  3. Separable B-splines on a standard orthogonal (square) lattice.

To ensure a fair comparison, the sampling density—the number of samples per unit area—is normalized across all lattice types. The analysis is conducted in the frequency domain using Fourier error kernels $E(\omega)$ to quantify the approximation error. The study assumes the use of an optimal "dual filter" for orthogonal projection, representing the best possible projection of a function into the spline space. The core of the proof rests on asymptotic analysis, calculating numerical "asymptotic constants" that represent the magnitude of error as the sampling step $h$ tends toward zero.

The Significance of Hexagonal Symmetry

A primary insight of this work is that the geometric symmetry of the spline is intrinsically linked to its functional performance. Unlike "slanted" B-splines, which utilize a rhomboid support that breaks the natural symmetry of the grid, hex-splines are inspired by the Voronoi cell of the hexagonal lattice. By preserving the twelve-fold symmetry of the hexagon, hex-splines achieve a more isotropic and efficient representation of the underlying signal.

Key Findings

The mathematical derivations yield several critical results regarding the efficiency of hexagonal sampling:

  • Superior Error Constants: The asymptotic constants for hex-splines are consistently smaller than those for slanted B-splines on the same lattice, proving that the hex-spline shape is better suited for hexagonal data than shifted versions of traditional splines.
  • Density Parity Advantage: When holding the sampling density constant, hex-splines on a hexagonal lattice provide a more accurate approximation of a continuous function than separable B-splines on an orthogonal lattice.
  • Asymptotic Dominance: For any given order of approximation $L$, hex-splines converge to the original signal with a lower constant factor of error than their orthogonal counterparts.

Conclusion and Future Directions

This research mathematically demonstrates that hex-splines are asymptotically a superior representation for continuous-domain functions in bivariate settings. By leveraging the geometric properties of the hexagonal lattice, hex-splines provide higher fidelity for a given number of samples compared to standard square-grid approaches.

While this paper establishes the theoretical foundation for hex-spline superiority, it focuses on asymptotic behavior. Future work will involve the explicit computation of these constants for various spline orders and an investigation into the computational trade-offs involved in implementing non-separable hex-spline convolutions compared to highly optimized separable filters.

Summary updated

Abstract

Recently, we have proposed a novel family of bivariate, non-separable splines. These splines, called "hexsplines" have been designed to deal with hexagonally sampled data. Incorporating the shape of the Voronoi cell of a hexagonal lattice, they preserve the twelve-fold symmetry of the hexagon tiling cell. Similar to B-splines, we can use them to provide a link between the discrete and the continuous domain, which is required for many fundamental operations such as interpolation and resampling. The question we answer in this paper is "How well do the hex-splines approximate a given function in the continuous domain?" and more specifically "How do they compare to separable B-splines deployed on a lattice with the same sampling density?"
BibTeX
@inproceedings{ville2003approximation,
  author = {Dimitri Van De Ville and T. Blu and Michaël Unser},
  title = {{On the Approximation Power of Splines: Orthogonal Versus Hexagonal Lattices}},
  booktitle = {Infoscience},
  year = {2003},
}
Figure