六角形高速フーリエ変換

六角形高速フーリエ変換( HFFT ) は、画像および信号処理におけるツールであり、高速フーリエ変換(FFT) ルーチンを使用して、六角形サンプリングで取得された画像の離散フーリエ変換(DFT)を計算します。^{[ 1 ]}六角形サンプリングの適用範囲は、効率的な座標系がないために制限されています。^{[ 2 ]}六角形サンプリングされた画像には分離可能なフーリエカーネルが存在するため、既存の FFT ルーチンを使用して、そのような画像の DFT を効率的に計算できます。

線形変換${\displaystyle g_{a}}$そして${\displaystyle f_{a}}$これらは、2次元矩形データの各次元に沿って線形変換が適用される矩形フーリエカーネルに似ています。^{[ 5 ]}上記の各方程式は、HDFTの前身となる4つの矩形配列の組み合わせです。これら4つの矩形配列のうち2つは、${\displaystyle g_{a}}$項は HFFT のサブアレイに寄与します。バイナリ座標を切り替えることで、4 つの異なる形式の方程式が得られます。これらの 4 つの式のうち 3 つは「非標準変換 (NST)」（下記参照）を使用して評価されており、1 つの式は任意の正しく適用可能な FFT アルゴリズムを使用して計算されています。^{[ 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}(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}(1,s,d)=\sum _{r}g_{a}(a,r,d)\exp \left(-j2\pi {\frac {(r)(2s+1)}{n}}\right)}$

2番目の表現、${\displaystyle g_{a}(1,r,d)}$は、六角形にサンプリングされた画像の長方形サブアレイの行に沿って一定のオフセットを持つ標準的な離散フーリエ変換（DFT）です。${\displaystyle x(a,r,c)}$^{[ 5 ]}この式は、DFT の円回転に他なりません。この性質が成り立つためには、シフトは整数個のサンプルで発生しなければならないことに注意してください。このようにして、関数は${\displaystyle g_{a}}$標準的なDFTを用いて、NSTを導入することなく、同じ演算回数で計算できる。

0配列以来${\displaystyle f_{a}}$は常にその空間周期の半分に関して対称であるため、その半分だけを計算すれば十分です。この式は、列の標準的な DFT です。${\displaystyle g_{a}}$これは係数2で間引きされ、複素指数関数の同一の第2周期にわたってrの空間を張るように複製されます。 ^{[ 5 ]}数学的には、

${\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}}}$

1配列の式${\displaystyle f_{a}}$これは、1サンプルシフトした0配列表現と同等です。したがって、1配列表現は、DFTの列として表現できます。${\displaystyle g_{a}}$1-配列に必要な定数オフセットを提供する2番目のサンプルから始めて、2分の1に間引き、次に空間的に2倍にしてsの範囲をカバーします。したがって、James B. BirdsongとNicholas I. Rummelt ^{[ 5 ]}によって開発された方法は、標準のFFTルーチンを使用してHFFTを正常に計算できます。