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. Hexagonal sampling's application is limited due to the lack of an efficient coordinate system. 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)
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. 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:
( a , r , c ) ∈ { 0 , 1 } × Z × 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.
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 ) {\displaystyle x(a,r,c)} be a two-dimensional hexagonally sampled signal and let both arrays be of size n × m {\displaystyle n\times m} . Let, 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 is given by
X ( b , s , d ) = ∑ a ∑ r ∑ c x ( a , r , c ) E ( ⋅ ) {\displaystyle X(b,s,d)=\sum _{a}\sum _{r}\sum _{c}x(a,r,c)E(\cdot )}
where
E ( ⋅ ) = exp [ − j π ( ( a + 2 c ) ( b + 2 d ) 2 m + ( a + 2 r ) ( b + 2 s ) n ) ] {\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
X ( b , s , d ) = f 0 ( b , s , d ) + W ( ⋅ ) f 1 ( b , s , d ) {\displaystyle X(b,s,d)=f_{0}(b,s,d)+W(\cdot )f_{1}(b,s,d)}
where
W ( ⋅ ) = exp [ − j π ( b + 2 d 2 m + b + 2 s n ) ] {\displaystyle W(\cdot )=\exp \left[-j\pi \left({\frac {b+2d}{2m}}+{\frac {b+2s}{n}}\right)\right]}
and
… excerpt ends here. Continue reading the full article.
