Hexagonal fast Fourier transform explained

The fast Fourier transform (FFT) is an important tool in the fields of image and signal processing. The hexagonal fast Fourier transform (HFFT) uses existing FFT routines to compute the discrete Fourier transform (DFT) of images that have been captured with hexagonal sampling.^[1] The hexagonal grid serves as the optimal sampling lattice for isotropically band-limited two-dimensional signals and has a sampling efficiency which is 13.4% greater than the sampling efficiency obtained from rectangular sampling.^{[2] [3]} Several other advantages of hexagonal sampling include consistent connectivity, higher symmetry, greater angular resolution, and equidistant neighbouring pixels.^{[4] [5]} Sometimes, more than one of these advantages compound together, thereby increasing the efficiency by 50% in terms of computation and storage when compared to rectangular sampling. Despite all of these advantages of hexagonal sampling over rectangular sampling, its application has been limited because of the lack of an efficient coordinate system.^[6] However that limitation has been removed with the recent development of the hexagonal efficient coordinate system (HECS, formerly known as array set addressing or ASA) which includes the benefit of a separable Fourier kernel. The existence of a separable Fourier kernel for a hexagonally sampled image allows the use of existing FFT routines to efficiently compute the DFT of such an image.

Preliminaries

Hexagonal Efficient Coordinate System (HECS)

See main article: Hexagonal Efficient Coordinate System (HECS). The hexagonal efficient coordinate system (formerly known as array set addressing (ASA)) was developed based on the fact that a hexagonal grid can be represented as a combination of two interleaved rectangular arrays.^[7] It is easy to address each individual array using familiar integer-valued row and column indices and the individual arrays are distinguished by a single binary coordinate. Therefore, a full address for any point in the hexagonal grid can be uniquely represented by three coordinates.

(a,r,c) \in \{ 0 , 1 \} x Z x Z where the coordinates a, r and c represent the array, row and column respectively. The figure shows how the hexagonal grid is represented by two interleaved rectangular arrays in HECS coordinates.

Hexagonal discrete Fourier transform

The hexagonal discrete Fourier transform (HDFT) has been developed by Mersereau and it has been converted to an HECS representation by Rummelt. Let

x(a, r, c) be a two-dimensional hexagonally sampled signal and let both arrays be of size n x m . Let, X(b, s, d) be the Fourier transform of x. The HDFT equation for the forward transform as shown in is given by X(b, s, d) = \sum _{a} \sum _{r} \sum _{c} x(a, r, c)E( ⋅ ) where E( ⋅ ) = \exp\left[ - j\pi\left( ((a +2 c)(b +2 d))/(2 m) + ((a +2 r)(b +2 s))/(n) \right)\right] Note that the above equation is separable and hence can be expressed as X(b, s, d) = f _{0(b,} s, d) + W( ⋅ ) f _{1(b,} s, d) where W( ⋅ ) = \exp\left[ - j\pi\left( (b +2 d)/(2 m) + (b +2 s)/(n) \right)\right] andg _{a(b,} r, d) = \sum _{c} x(a, r, c) \exp\left( - j 2 \pi ((c)(b +2 d))/(2 m) \right) f _{a(b,} s, d) = \sum _{r} g _{a(b,} r, d) \exp\left( - j 2 \pi ((r)(b +2 s))/(n) \right)

Hexagonal fast Fourier transform (HFFT)

The linear transforms

g _{a} and f _{a} are similar to the rectangular Fourier kernel where a linear transform is applied along each dimension of the 2-D rectangular data. Note that each of these equations, discussed above, is a combination of four rectangular arrays that serve as precursors to the HDFT. Two, out of those four rectangular g _{a} terms contribute to the sub-array of HFFT. Now, by switching the binary coordinate, we have four different forms of equations. In, the three out of those four expressions have been evaluated using what the author called "non-standard transforms (NSTs)" (shown below) while one expression is computed using any correct and applicable FFT algorithm.g _{a(0,} r, d) = \sum _{c} x(a, r, c) \exp\left( - j 2 \pi ((c)(d))/(m) \right) g _{a(1,} r, d) = \sum _{c} x(a, r, c) \exp\left( - j 2 \pi ((c)( 2 d +1 ))/(2 m) \right) f _{a(0,} s, d) = \sum _{r} g _{a} (a, r, d) \exp\left( - j 2 \pi ((r)( 2 s))/(n) \right) f _{a(1,} s, d) = \sum _{r} g _{a} (a, r, d) \exp\left( - j 2 \pi ((r)( 2 s +1 ))/(n) \right)

Looking at the second expression,

g _{a} ( 1 ,r,d) , we see that it is nothing more than a standard discrete Fourier transform (DFT) with a constant offset along the rows of rectangular sub-arrays of a hexagonally-sampled image x(a, r, c) . This expression is nothing more than a circular rotation of the DFT. Note that the shift must happen in the integer number of samples for the property to hold. This way, the function g _{a} can be computed using the standard DFT, in same number of operations, without introducing an NST.

If we have a look at 0-array

f _{a} , the expression will always be symmetric about half its spatial period. Because of this, it is enough to compute only half of it. We find that this expression is the standard DFT of the columns of g _{a} , which is decimated by a factor of 2 and then is duplicated to span the space of r for the identical second period of the complex exponential. Mathematically,\begin{align} X _{even[k]} & = \sum ^{N -1} _{n =0} x[n]e ^{-\tfrac{2j\pi} {N} 2 kn} \\[ 5 pt] & = \sum ^{\tfrac{N} _{n =0} { 2 } -1 } x[n]e ^{-\tfrac{2j\pi} {N/ 2 }kn} + \sum _{n=\tfrac{N} { 2 }} ^{N-1} x[n]e ^{-\tfrac{2j\pi} {N/ 2 }kn} \\[ 5 pt] & = \sum ^{\tfrac{N} _{n =0} { 2 } -1 } x[n]e ^{-\tfrac{2j\pi} {N/ 2 }kn} + \sum ^{\tfrac{N} _{n =0} { 2 } -1 } x\left[n + \tfrac{N}{ 2 }\right]e ^{-\tfrac{2j\pi} {N/ 2 }kn} \\[ 5 pt] & = \sum ^{\tfrac{N} _{n =0} { 2 } -1 } \left(x[n] + x\left[n + \tfrac{N}{ 2 }\right]\right)e ^{-\tfrac{2j\pi} {N/ 2 }kn} \end{align}

The expression for the 1-array

f _{a} is equivalent to the 0-array expression with a shift of one sample. Hence, the 1-array expression can be expressed as columns of the DFT of g _{a} decimated by a factor of two, starting with second sample providing a constant offset needed by 1-array, and then doubled in space to span the range of s. Thus, the method developed by James B. Birdsong and Nicholas I. Rummelt in is able to successfully compute the HFFT using the standard FFT routines unlike the previous work in.

Notes and References

1. James B. Birdsong, Nicholas I. Rummelt, "The Hexagonal Fast Fourier Transform", 2016 IEEE International Conference on Image Processing (ICIP), pp. 1809–1812,
2. D. P. Petersen and D. Middleton, Dec. 1962, "Sampling and reconstruction of wave-number-limited functions in n-dimensional Euclidean spaces", Inf. Control, vol. 5, no. 4, pp. 279–323
3. R. M. Mersereau, June 1979, "The Processing of Hexagonally Sampled Two-Dimensional Signals", Proceedings of the IEEE, vol. 67, no. 6, pp. 930–949
4. X. He and W. Jia, 2005, "Hexagonal structure for intelligent vision", in Proc. 1st Int. Conf. Information and Communication Technologies, pp. 52–64
5. W. E. Snyder, 1999, H. Qi, and W. Sander, "A coordinate system for hexagonal pixels", in Proc. SPIE Medical Imaging: Image Processing, vol. 3661, pp. 716–727
6. Nicholas I. Rummelt and Joseph N. Wilson "Array set addressing: enabling technology for the efficient processing of hexagonally sampled imagery," Journal of Electronic Imaging 20(2), 023012 (1 April 2011). https://doi.org/10.1117/1.3589306
7. Nicholas I. Rummelt, 2010, Array Set Addressing: Enabling Efficient Hexagonally Sampled Image Processing, Ph.D. thesis, University of Florida