Multidimensional signal processing
Hexagonal fast Fourier transform
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. 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. Several other advantages of hexagonal sampling include consistent connectivity, higher symmetry, greater angular resolution, and equidistant neighbouring pixels. 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. 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. (Wikipedia).
