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: Cooley-Tukey Type Algorithms on the 2-D Spatial Hexagonal Lattice
  submitted for publication
  

  Recently, we introduced the framework for signal processing on a 2-D 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, "z-transform," convolution, spectrum, and Fourier transform. The latter we termed discrete triangle transform (DTT). The DTT is a nonseparable 2-D 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 general-radix algorithms for the DTT, focusing on the radix-2x2 case. The derivation is based on a stepwise decomposition of the polynomial algebra underlying the DTT. The 1-D equivalent of this technique underlies a large class of 1-D transform algorithms including the Cooley-Tukey 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: 2-D Spatial Hexagonal Lattice
  to appear in IEEE Transactions on Image Processing
  

  We develop the framework for signal processing on a spatial, or undirected, 2-D hexagonal lattice for both an infinite and a finite array of signal samples. This framework includes the proper notions of z-transform, 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, bottom-up 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 transform---a 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, two-dimensional 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 two-dimensional directional quincunx lattice. The transform is non-separable, but closely related to a two-dimensional (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 non-separable transform for signal processing on a two-dimensional 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 Cooley-Tukey FFT like algorithms that enable its efficient computation.

  triangle.pdf (91 KB)

• Markus Püschel and Martin Rötteler
  Cooley-Tukey 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 non-separable transform for signal processing on a two-dimensional 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 Cooley-Tukey FFT type fast algorithm. We derive this algorithm and an upper bound for the number of complex operations it requires. Similar to most separable two-dimensional 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)