Hexagonal fast Fourier transform

The hexagonal fast Fourier transform (HFFT) is a tool in image and signal processing which uses fast Fourier transform (FFT) routines to compute the discrete Fourier transform (DFT) of images captured with hexagonal sampling.^[1] Hexagonal sampling's application is limited due to the lack of an efficient coordinate system ^[2] . 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.

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.^[3] One can address each individual array by using integer-valued row and column indices, and the individual arrays can be distinguished by a single binary coordinate. Therefore, a full address for any point in the hexagonal grid can be uniquely represented by three coordinates:

${\displaystyle (a,r,c)\in \{0,1\}\times \mathbb {Z} \times \mathbb {Z} }${\displaystyle (a,r,c)\in \{0,1\}\times \mathbb {Z} \times \mathbb {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.

The hexagonal discrete Fourier transform (HDFT) has been developed by Mersereau^[4] and it has been converted to an HECS representation by Rummelt.^[3] Let ${\displaystyle x(a,r,c)}${\displaystyle x(a,r,c)} be a two-dimensional hexagonally sampled signal and let both arrays be of size ${\displaystyle n\times m}${\displaystyle n\times m}. Let, ${\displaystyle X(b,s,d)}${\displaystyle X(b,s,d)} be the Fourier transform of x. The HDFT equation for the forward transform as shown in ^[3] is given by

${\displaystyle X(b,s,d)=\sum _{a}\sum _{r}\sum _{c}x(a,r,c)E(\cdot )}${\displaystyle X(b,s,d)=\sum _{a}\sum _{r}\sum _{c}x(a,r,c)E(\cdot )}

where

${\displaystyle E(\cdot )=\exp \left[-j\pi \left({\frac {(a+2c)(b+2d)}{2m}}+{\frac {(a+2r)(b+2s)}{n}}\right)\right]}${\displaystyle E(\cdot )=\exp \left[-j\pi \left({\frac {(a+2c)(b+2d)}{2m}}+{\frac {(a+2r)(b+2s)}{n}}\right)\right]}

Note that the above equation is separable and hence can be expressed as

${\displaystyle X(b,s,d)=f_{0}(b,s,d)+W(\cdot )f_{1}(b,s,d)}${\displaystyle X(b,s,d)=f_{0}(b,s,d)+W(\cdot )f_{1}(b,s,d)}

where

${\displaystyle W(\cdot )=\exp \left[-j\pi \left({\frac {b+2d}{2m}}+{\frac {b+2s}{n}}\right)\right]}${\displaystyle W(\cdot )=\exp \left[-j\pi \left({\frac {b+2d}{2m}}+{\frac {b+2s}{n}}\right)\right]}

and

${\displaystyle g_{a}(b,r,d)=\sum _{c}x(a,r,c)\exp \left(-j2\pi {\frac {(c)(b+2d)}{2m}}\right)}${\displaystyle g_{a}(b,r,d)=\sum _{c}x(a,r,c)\exp \left(-j2\pi {\frac {(c)(b+2d)}{2m}}\right)}

${\displaystyle f_{a}(b,s,d)=\sum _{r}g_{a}(b,r,d)\exp \left(-j2\pi {\frac {(r)(b+2s)}{n}}\right)}${\displaystyle f_{a}(b,s,d)=\sum _{r}g_{a}(b,r,d)\exp \left(-j2\pi {\frac {(r)(b+2s)}{n}}\right)}

The linear transforms ${\displaystyle g_{a}}${\displaystyle g_{a}} and ${\displaystyle f_{a}}${\displaystyle f_{a}} are similar to the rectangular Fourier kernel where a linear transform is applied along each dimension of the 2-D rectangular data.^[5] 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 ${\displaystyle g_{a}}${\displaystyle g_{a}} terms contribute to the sub-array of HFFT. By switching the binary coordinate, we have four different forms of equations. Three out of those four expressions have been evaluated using "non-standard transforms (NSTs)" (shown below) while one expression is computed using any correct and applicable FFT algorithm.^[3]

${\displaystyle g_{a}(0,r,d)=\sum _{c}x(a,r,c)\exp \left(-j2\pi {\frac {(c)(d)}{m}}\right)}${\displaystyle g_{a}(0,r,d)=\sum _{c}x(a,r,c)\exp \left(-j2\pi {\frac {(c)(d)}{m}}\right)}

${\displaystyle g_{a}(1,r,d)=\sum _{c}x(a,r,c)\exp \left(-j2\pi {\frac {(c)(2d+1)}{2m}}\right)}${\displaystyle g_{a}(1,r,d)=\sum _{c}x(a,r,c)\exp \left(-j2\pi {\frac {(c)(2d+1)}{2m}}\right)}

${\displaystyle f_{a}(0,s,d)=\sum _{r}g_{a}(a,r,d)\exp \left(-j2\pi {\frac {(r)(2s)}{n}}\right)}${\displaystyle f_{a}(0,s,d)=\sum _{r}g_{a}(a,r,d)\exp \left(-j2\pi {\frac {(r)(2s)}{n}}\right)}

${\displaystyle f_{a}(1,s,d)=\sum _{r}g_{a}(a,r,d)\exp \left(-j2\pi {\frac {(r)(2s+1)}{n}}\right)}${\displaystyle f_{a}(1,s,d)=\sum _{r}g_{a}(a,r,d)\exp \left(-j2\pi {\frac {(r)(2s+1)}{n}}\right)}

The second expression, ${\displaystyle g_{a}(1,r,d)}${\displaystyle g_{a}(1,r,d)}, is a standard discrete Fourier transform (DFT) with a constant offset along the rows of rectangular sub-arrays of a hexagonally-sampled image ${\displaystyle x(a,r,c)}${\displaystyle x(a,r,c)}.^[5] 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 ${\displaystyle g_{a}}${\displaystyle g_{a}} can be computed using the standard DFT, in same number of operations, without introducing an NST.

Since 0-array ${\displaystyle f_{a}}${\displaystyle f_{a}} will always be symmetric about half its spatial period, it is enough to compute only half of it. This expression is the standard DFT of the columns of ${\displaystyle g_{a}}${\displaystyle 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.^[5] Mathematically,

${\displaystyle {\begin{aligned}X_{\text{even}}[k]&=\sum _{n=0}^{N-1}x[n]e^{-{\tfrac {2j\pi }{N}}2kn}\\[5pt]&=\sum _{n=0}^{{\tfrac {N}{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}\\[5pt]&=\sum _{n=0}^{{\tfrac {N}{2}}-1}x[n]e^{-{\tfrac {2j\pi }{N/2}}kn}+\sum _{n=0}^{{\tfrac {N}{2}}-1}x\left[n+{\tfrac {N}{2}}\right]e^{-{\tfrac {2j\pi }{N/2}}kn}\\[5pt]&=\sum _{n=0}^{{\tfrac {N}{2}}-1}\left(x[n]+x\left[n+{\tfrac {N}{2}}\right]\right)e^{-{\tfrac {2j\pi }{N/2}}kn}\end{aligned}}}${\displaystyle {\begin{aligned}X_{\text{even}}[k]&=\sum _{n=0}^{N-1}x[n]e^{-{\tfrac {2j\pi }{N}}2kn}\\[5pt]&=\sum _{n=0}^{{\tfrac {N}{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}\\[5pt]&=\sum _{n=0}^{{\tfrac {N}{2}}-1}x[n]e^{-{\tfrac {2j\pi }{N/2}}kn}+\sum _{n=0}^{{\tfrac {N}{2}}-1}x\left[n+{\tfrac {N}{2}}\right]e^{-{\tfrac {2j\pi }{N/2}}kn}\\[5pt]&=\sum _{n=0}^{{\tfrac {N}{2}}-1}\left(x[n]+x\left[n+{\tfrac {N}{2}}\right]\right)e^{-{\tfrac {2j\pi }{N/2}}kn}\end{aligned}}}

The expression for the 1-array ${\displaystyle f_{a}}${\displaystyle 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 ${\displaystyle g_{a}}${\displaystyle 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^[5] is able to successfully compute the HFFT using the standard FFT routines.

• Multidimensional signal processing

• Wikipedia articles with possible conflicts of interest from October 2025