
Discrete Lattice Transforms
We have recently derived new signal transforms for signals given on finite hexagonal or quincunx lattices. The transforms are derived using the algebraic theory signal processing.



triangular or hexagonal lattice
(nonseparable) 
quincunx lattice
(nonseparable) 
rectangular lattice
(separable) 
Papers

Markus Püschel and Martin Rötteler
Algebraic Signal Processing Theory: CooleyTukey Type Algorithms on the 2D Spatial Hexagonal Lattice
submitted for publication
Recently, we introduced the framework for signal processing on a 2D
hexagonal spatial lattice. Spatial means that the lattice is
undirected in contrast to the directed lattices that were studied by
Mersereau. The framework includes the proper notions of filter and
signal space, "ztransform," convolution, spectrum, and Fourier
transform. The latter we termed discrete triangle transform (DTT).
The DTT is a nonseparable 2D transform. The derivation of the
framework uses the algebraic signal processing theory. This means
that the above concepts are obtained by constructing polynomial
algebras with suitable structure.
In this paper, we derive generalradix algorithms for the DTT,
focusing on the radix2x2 case. The derivation is based on
a stepwise decomposition of the polynomial algebra underlying the
DTT. The 1D equivalent of this technique underlies a large class
of 1D transform algorithms including the CooleyTukey FFT. The
obtained DTT algorithm has a runtime of O(n^2 log(n)). This puts
the DTT into the same complexity class as its separable
counterparts.

Markus Püschel and Martin Rötteler
Algebraic Signal Processing Theory: 2D Spatial Hexagonal Lattice
to appear in IEEE Transactions on Image Processing
We develop the framework for signal processing on a spatial, or undirected, 2D hexagonal lattice for both an infinite and a finite array of signal samples. This framework includes the proper notions of ztransform, boundary conditions, filtering or convolution, spectrum, frequency response, and Fourier transform. In the finite case, the Fourier transform is called discrete triangle transform (DTT). Like the hexagonal lattice, this transform is nonseparable. The derivation of the framework makes it a natural extension of the algebraic signal processing theory that we recently introduced. Namely, we construct the proper signal models, given by polynomial algebras, bottomup from a suitable definition of hexagonal space shifts using a procedure provided by the algebraic theory. These signal models, in turn, then provide all the basic signal processing concepts. The framework developed in this paper is related to Mersereau's early work on hexagonal lattices in the same way as the discrete cosine and sine transforms are related to the discrete Fourier transforma fact that will be made rigorous in this paper.
 Markus Püschel and Martin Rötteler
Fourier Transform for the Spatial Quincunx Lattice
Proc. ICIP 2005
We derive a new, twodimensional nonseparable signal transform for computing the spectrum of spatial signals residing on a finite quincunx lattice. The derivation uses the connection between transforms and polynomial algebras, which has long been known for the discrete Fourier transform (DFT), and was extended to other transforms in recent research. We also show that the new transform can be computed with O(n^2 log(n)) operations, which puts it in the same complexity class as its separable counterparts.
dqt.pdf (88 KB)
 Markus Püschel and Martin Rötteler
Fourier Transform for the Directed Quincunx Lattice
Proc. ICASSP 2005
We introduce a new signal transform for computing the spectrum of a signal given on a twodimensional directional quincunx lattice. The transform is nonseparable, but closely related to a twodimensional (separable) discrete Fourier transform. We derive the transform using recently discovered connections between signal transforms and polynomial algebras. These connections also yield several important properties of the new transform.
ddqt.pdf (77 KB)
 Markus Püschel and Martin Rötteler
The Discrete Triangle Transform
Proc. ICASSP 2004
We introduce the discrete triangle transform (DTT), a nonseparable transform for signal processing on a twodimensional equispaced triangular grid. The DTT is, in a strict mathematical sense, a generalization of the DCT, type III, to two dimensions, since the DTT is built from Chebyshev polynomials in two variables in the same way as the DCT, type III, is built from Chebyshev polynomials in one variable. We provide boundary conditions, signal extension, and diagonalization properties for the DTT. Finally, we give evidence that the DTT has CooleyTukey FFT like algorithms that enable its efficient computation.
triangle.pdf (91 KB)
 Markus Püschel and Martin Rötteler
CooleyTukey FFT Like Algorithm for the Discrete Triangle Transform
Proc. 11th IEEE DSP Workshop, 2004
The discrete triangle transform (DTT) was recently introduced (see above) as an example of a nonseparable transform for signal processing on a twodimensional triangular grid. The DTT is built from Chebyshev polynomials in two variables in the same way as the DCT, type III, is built from Chebyshev polynomials in one variable. We show that, as a consequence, the DTT has, as the DCT, type III, a CooleyTukey FFT type fast algorithm. We derive this algorithm and an upper bound for the number of complex operations it requires. Similar to most separable twodimensional transforms, the operations count of this algorithm is O(n^2 log(n)) for an input of size n x n.
trianglealgo.pdf (91 KB)
