Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Hexagonal fast Fourier transform
open-in-new
<p>The <a href="/facts/Fast_Fourier_transform/caT7UUCh">fast Fourier transform</a> (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 <a href="/facts/Discrete_Fourier_transform/uK9Tjsbl">discrete Fourier transform</a> (DFT) of images that have been captured with <a href="/facts/Hexagonal_sampling/yePDtdMo">hexagonal sampling</a>. The <a href="/facts/Hexagonal_grid/HwG5F0YH">hexagonal grid</a> serves as the optimal sampling <a href="/facts/Lattice_(order)/5ak6ufky">lattice</a> for isotropically <a href="/facts/Band-limited/LrYmxzlA">band-limited</a> two-dimensional signals and has a sampling efficiency which is 13.4% greater than the sampling efficiency obtained from rectangular <a href="/facts/Sampling_(signal_processing)/xxck7aLN">sampling</a>. Several other advantages of hexagonal sampling include consistent connectivity, higher <a href="/facts/Symmetry/hpu7DK8p">symmetry</a>, greater <a href="/facts/Angular_resolution/wJarPBWF">angular resolution</a>, and <a href="/facts/Equidistant/muTk20sY">equidistant</a> neighbouring <a href="/facts/Pixel/UzwBvXBV">pixels</a>. 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. </p>