如何擴展一維FFT代碼來計算Python中圖像（2D）的FFT？

Question

我想擴展fft代碼，適用於圖像的python中的一維數組。其實我知道問題是在邏輯上延伸。我不太瞭解FFT，我必須提交圖像處理作業。我會感謝任何提示或解決方案

這裏是代碼，實際上，我正在嘗試在python中創建一個用於FFT的模塊，並且它已經可以很好地用於一維，從羅塞塔代碼網站獲得幫助。

from cmath import exp, pi 
from math import log, ceil 

def fft(f): 
    N = len(f) 
    if N <= 1: return f 
    even = fft(f[0::2]) 
    odd = fft(f[1::2]) 
    return [even[k] + exp(-2j*pi*k/N)*odd[k] for k in xrange(N/2)] + \ 
      [even[k] - exp(-2j*pi*k/N)*odd[k] for k in xrange(N/2)] 

def pad(f): 
    n = len(f) 
    N = 2 ** int(ceil(log(n, 2))) 
    F = f + [0] * (N - n) 
    return F, n 

def unpad(F, n): 
    return F[0 : n] 

def pad2(f): 
    m, n = len(f), len(f[0]) 
    M, N = 2 ** int(ceil(log(m, 2))), 2 ** int(ceil(log(n, 2))) 
    F = [ [0]*N for _ in xrange(M) ] 
    for i in range(0, m): 
     for j in range(0, n): 
      F[i][j] = f[i][j] 
    return F, m, n 

def fft1D(f): 
    Fu, n = pad(f) 
    return fft(Fu), n 

def fft2D(f): 
    F, m, n = pad2(f) 
    M, N = len(F), len(F[0]) 
    Fuv = [ [0]*N for _ in xrange(M) ] 
    for i in range(0, M): 
     Fxv = fft(F[i]) 
     for j in range(0, N): 
      Fuv[i][j] = (fft(Fxv))[j] 
    return Fuv, [m, n] 

我稱這個模塊TIS代碼：

from FFT import * 
f= [0, 2, 3, 4] 
F = fft1D(f) 
print f, F 
X, s = fft2D([[1,2,1,1],[2,1,2,2],[0,1,1,0], [0,1,1,1]]) 
for i in range(0, len(X)): 
    print X[i] 

它的輸出是：

[0, 2, 3, 4] ([(9+0j), (-3+2j), (-3+0j), (-3-2j)], 4) 
[(4+0j), (4-2.4492935982947064e-16j), (4+0j), (8+2.4492935982947064e-16j)] 
[(8+0j), (8+2.4492935982947064e-16j), (8+0j), (4-2.4492935982947064e-16j)] 
[0j, -2.33486982377251e-16j, (4+0j), (4+2.33486982377251e-16j)] 
[0j, (4+0j), (4+0j), (4+0j)] 

第一個一維是好的，因爲我與Matlab的輸出，但對於第二個驗證的結果一個Matlab的輸出是：

>> fft([1,2,1,1;2,1,2,2;0,1,1,0;0,1,1,1]) 

ans = 

    3.0000    5.0000    5.0000    4.0000   
    1.0000 - 2.0000i 1.0000     0 - 1.0000i 1.0000 - 1.0000i 
    -1.0000    1.0000   -1.0000   -2.0000   
    1.0000 + 2.0000i 1.0000     0 + 1.0000i 1.0000 + 1.0000i 

輸出是不同的，這意味着我在代碼的邏輯中做了錯誤的事情。請不要麻煩，因爲我到現在還沒有正式研究過FFT，所以我無法完全理解數學，也許在我學習之後，我可能會解決這個問題。

Answer 1

你的代碼有點難以遵循，但它看起來像你沿着相同的方向同時進行FFT。查看FT的積分，你會發現x和y的積分是獨立的。這是（抱歉，這個符號是可怕的，'表示傅立葉空間中的功能）

FT(f(x, y), x) -> f'(k, y) 
FT(f'(k, y), y) -> f''(k, w) 

所以，你想要做的是採取每個行的FFT（比做ñ維FFT）和推結果導入一個新的數組（從f(x, y) -> f'(k, y)開始）。然後拿這個結果陣列（做中號維FFT）的每個列的FFT搡這些結果到另一個新的數組（這需要你從f'(k, y) -> f''(k, w)。

Answer 2

我isedev，你應該使用numpy的同意，這已經有一個偉大的FFT軟件包，可以在n維做變換。

http://docs.scipy.org/doc/numpy/reference/routines.fft.html

http://docs.scipy.org/doc/numpy-1.4.x/reference/generated/numpy.fft.fft.html