二維傅里葉變換是怎麼進行的？

12-15

最近看了一些二維傅里葉變換的東西，不太明白，特來請教。
問題如下：
二維傅里葉變化是如何進行的？為什麼圖中水平和豎直的分隔得到的頻率域差別很大？為什麼對角分隔的圖形對應的頻率域有個十字？
第二個問題，我注意到二維傅里葉轉換之後，頻率域的坐標有沒有變換？如果沒有，那頻率是如何在頻率域體現的？如果變換了，那原圖中點陣的坐標信息又是如何保留的？

圖片來源：http://www.math.ucla.edu/~wittman/PCMI/fourier_pcmi6.pdf

1，2D Fourier Transform (FT)
$F(u,v) =int_{-infty}^{+infty}int_{-infty}^{+infty}f(x,y)e^{-j2pi(ux+vy)}dxdy$
上式為連續情形下的傅立葉變換，具體的積分區間取決於函數 $f(x,y)$ 的定義域。 $x$ ， $y$ 的積分順序可交換，因此，對 $f(x,y)$ 做2D FT實際上相當於對兩個方向分別作1D FT。此外，FT的一大特點就是它是線性變換，即信號 $f_1$ , $f_2$ 線性組合的FT等於它們各自FT的線性組合。
2，2D Discrete Fourier Transform (DTF)
頻域分析是信號處理中的經典方法，但是計算機是離散的，處理的信號也不可能是無限長的，因此信號分析中用到的是離散傅立葉變換DFT，2D正變換公式如下
$F(k,l) = sum_{m=0}^{M-1}sum_{n=0}^{N-1}f(m,n)e^{-j2pi(km/M+ln/N)} \ = sum_{m=0}^{M-1}e^{-j2pifrac{km}{M}}sum_{n=0}^{N-1}f(m,n)e^{-j2pifrac{ln}{N}}$
同FT，2D DFT同樣分兩個方向獨立進行，且是線性的。有一點要注意，在進行DFT時，實際上默認信號時周期的，然而實際上並非如此。
此外，快速傅立葉變換演算法FFT的提出極大促進了信號處理等領域的發展，這也是它能成為20世紀十大演算法之一的原因。
3，題主所看的slide中的圖是"錯誤"的，正確的圖應該如下（slide中的圖片應該是MATLAB畫的）

錯誤1，信號 $f_1$ 和 $f_2$ 的DFT只存在方向上的區別，幅度值是一樣的。上圖於slides中的圖不同是因為作者在畫圖時用了fftshift命令，至於原因，錯誤2中詳述。此外，這兩個信號實際是1D階越信號的二維延拓，對應1D如下

錯誤2，首先要明確的就是MATLAB中矩陣與作圖時坐標原點問題。
MATLAB中，矩陣的坐標原點是左上角，因此，用fft函數做傅立葉變換，所得到的變換結果，左上角是原點，當我們在畫圖的時候，習慣了原點在中心，因此slides中的圖是用了fftshift後得到的，即將原點一到了我們習慣的位置（在圖中坐標(26,26)是為原點）。之所以可以這麼作，是因為我們已經假設信號的周期的了，因此，若將 $F_1, F_2, F_3$ 周期化後，即可得到slide中的效果。
回到信號 $f_3$ ，從函數角度看，實際上是要將它按頂邊旋轉180度來看的，即它的間斷處是第一象限的角平分線。因此到了頻域在幅值上會有相應的直線，比如下圖就是，但是沒有角平分線明顯

4，對應關係
對於DFT，時域，頻域是對應的，這種對應是指，時域有多少點，頻域即有多少點。或者說，在進行DFT是，時域和頻域的離散化網格大小是一致的，解析度都是 $frac{1}{N}$ ， $N$ 對應著信號在每個維度上的長度。

謝邀，覺得有點意思，特地嘗試了一下。
使用fftshift把零頻移到了圖像中間，和題主給的結果是一樣的。

1. 因為fft會把圖像周期延拓，fig3的fft2結果fig6就不難理解了，45度方向的頻率對應原圖中135度的階躍，水平和垂直方向的頻率分量來源於周期延拓（可以嘗試把圖像上方重複到下方來，那麼就有水平的階躍了，垂直方向同理）

2. fig1 的fft2 結果fig4 和 fig2的fft2結果 fig5 為何會長的不一樣呢? 這兩圖原理上只是旋轉了90度而已啊，因為fft2是線性運算，二者頻譜似乎也應該只是一個旋轉90度的關係才對。
經驗證，fig4和fig5確實只是一個旋轉90度的關係。二者顯示差別是由於colorbar不一致導致。（二者相對差為 1.3466e-016）

另一個問題是頻率坐標：
本質上，數字圖像沒有採樣率信息，是無法得知確切頻率坐標的。但可以假想一個水平採樣率fy，和垂直採樣率fx，最終對M*N的數字圖像 fft2得到 M*N的頻譜圖。則坐標點（i, j )對應的頻率為（fx/M*i, fy/N*j )，簡單理解就是0對應零頻，N對應fy，線性增長（x方向同理）。考慮到頻域水平和垂直方向分別以fx， fy為周期，所以可以把坐標軸平移到原點，頻域範圍為 [-fx/2, fx/2] ∩ [-fy/2, fy/2] . 空間採樣率的含義就是單位長度採樣幾個像素。

matlab code
% test 2d fft for special images
clear, close all; clc;
X = zeros(50,50);
X1 = X;
for i=1:50
for j=1:50
if j&>25
X1(i,j) = 1;
end
end
end

X2 = X;
for i=1:50
for j=1:50
if i&>25
X2(i,j) = 1;
end
end
end

X3 = X;
for i=1:50
for j=1:50
if j&>i
X3(i,j) = 1;
end
end
end

XX1 = fft2(X1); XX1 = fftshift(XX1);
XX2 = fft2(X2); XX2 = fftshift(XX2);
XX3 = fft2(X3); XX3 = fftshift(XX3);

figure;
subplot(2,3,1); imagesc(X1);
subplot(2,3,2); imagesc(X2);
subplot(2,3,3); imagesc(X3);
subplot(2,3,4); imagesc(log(abs(XX1)));
subplot(2,3,5); imagesc(log(abs(XX2)));
subplot(2,3,6); imagesc(log(abs(XX3)));

figure;
imagesc(log(abs(XX1))); colorbar; caxis([-30, 10]);
figure;
imagesc(log(abs(XX2))); colorbar; caxis([-30, 10]);

diff = norm(conj(XX1") - XX2)/sqrt(norm(XX1)*norm(XX2));

$(mathbb{R}^2,+)$ 是個locally compact abelian group，它的Pontryagin dual是自身。這就是傳統意義下的Fourier變換。
若考慮compact abelian group $mathbb{T}^2congmathbb{R}^2/mathbb{Z}^2$ ，則它的Pontryagin dual是discrete group $mathbb{Z}^2$ 。一般來說，容易證明compact group的Pontryagin dual總是discrete group。這就是二維情形的Fourier級數，本質仍是Fourier變換。
本質上，要了解abelian group只需要知道它的character，這就是Fourier變換。

各種資料講解都差不多，我個人開始最迷茫的就是經過傅里葉變換之後的矩陣，每個點是個什麼東西。
直到在csdn上隨便下了個ppt看到一張圖，似乎明白了。。
右邊每個方格對應x和y方向不同頻率的波，這些波疊加（帶上另一個相位譜）得到原圖，而每個方格也對應頻率圖對應坐標的像素，頻率圖每個像素的亮度表示每個方格描述的波的振幅。
（要是我理解錯了趕緊告訴我T_T）

最近有一些私信來問這個PPT網址，我不記得了……

不清楚作者，如果有版權神馬的，請在這裡回復留言~~~

mark一下，回去答。
分割線-----
要去健身房前想起來還有個題挖坑沒填，前面諸位大神珠玉在前，我就稍微聊點自己的想法。。
在奧本海姆的《信號與系統》第二版的第六章信號與系統的時域和頻域特性中是這樣描述的：「這幅圖像的的傅立葉變換代表了亮度分布函數在兩個坐標方向上每一個方向上，以不同的頻率所產生的空間變化」
相位是復頻域中正負組成部分的所佔的比例，相位存在的意義在於「調製」了最終進行疊加的時候的幅度大小。所以只有在圖像邊緣和高對比度的部分，才是信息量比較大的地方，因為只有同相位的高峰或者低谷進行疊加，才會產生這樣的結果。課後題的3.70大概能了解到這個意義：頻域上的每一個點，是每一個對應倍頻的點的模長。
mark一下，明天去上班的時候續寫下具體求法，因為實在懶得編輯，暫時還不知道怎麼弄，如果等不及就直接參考章大神翻譯的那本圖像處理基礎就好，裡面有一章專門講怎麼手算圖像的傅里葉變化，題主的所有問題在看到那個計算過程之後直接迎刃而解。。如果我犯懶了，就不寫了。。畢竟手打復頻域相關的矩陣計算是一件折磨人的事兒。。。嗯，因為我們辦公室不能上網，所以最好還是找到那本書詳細看下比較好，盡量不要等我。。。
還是建議入門圖像處理的好好認真刷下信號與系統，圖像處理基礎，矩陣計算與應用這三本書。。。。。要不然概念糊糊塗塗的最後只能淪為調參機器，至少看了這幾本書，能夠變成會吹nb的調參機器。。。
---我是分割線答主來填坑了。。。。
機智如我，直接把這兩頁拍下來了，版權和榮耀屬於皮特魯和章神，我只是做了一點微不足道的搬運工作

按照我的理解，好像是x軸和y軸的分別傅立葉變換，再疊加的，這個圖像應該可以看出點東西