二維傅立葉變換

**傅立葉轉換**（英语：**Fourier transform**）是一種幫助我們分析訊號頻域成分的積分變換，詳細內容詳見傅立葉轉換一文。一般教科書所教的通常是一維的傅立葉轉換，但我們也可以將傅立葉轉換推廣到多維的空間。而二維傅立葉轉換即是由一維傅立葉轉換推廣而來，近幾十年來常被運用在影像處理上。其他相關的數學工具，例如二維餘弦轉換、二維濾波器……等等，均是建立在二維傅立葉轉換的概念上而得到的。

## 二維傅立葉級數

考慮一個信號二維的信號，s(t_1,t_2)，其中t_1,t_2為兩個獨立變數，且s(t_1,t_2)滿足下列方程式:

s(t_1,t_2) = s(t_1+kT_1,t_2+lT_2), for all t_1,t_2, 其中k,l為整數

也就是說s(t_1,t_2)在t_1-t_2平面為週期函數，在t_1方向的週期為T_1，在t_2方向的週期為T_2，而信號的傅立葉級數為

s(t_1,t_2) = \sum_{n=-\infty}^{\infty}\sum_{m=-\infty}^{\infty}a_{mn}e^{j(m\omega_1t_1+n\omega_2t_2)},\ \omega_1 = 2\pi/T_1, \omega2 = 2\pi/T_2 

而a_{mn}可藉由積分求得

a_{mn} = \frac{1}{T_1T_2}\int_{0}^{T_2}\int_{0}^{T_1}s(t_1,t_2)e^{-jm\omega_1t_1}e^{-jn\omega_2t_2}\,dt_1\,dt_2

## 二維連續傅立葉變換

對於平面上的連續週期信號，我們可以使用二維傅立葉級數來分析，但對於平面上的連續非週期信號s(t_1,t_2)，我們則需使用二維連續傅立葉變換。

二維連續傅立葉變換定義為

S(j\omega_1,j\omega_2) = \int_{-\infty}^{\infty}\int_{-\infty}^{\infty}s(t_1,t_2)e^{-j(\omega_1t_1+\omega_2t_2)}\,dt_1\,dt_2

二維連續傅立葉逆變換定義為

s(t_1,t_2) =\frac{1}{4\pi^{2}} \int_{-\infty}^{\infty}\int_{-\infty}^{\infty}S(j\omega_1,j\omega_2)e^{j(\omega_1t_1+\omega_2t_2)}\,d\omega_1\,d\omega_2

為了方便，我們會將一些變數以向量的形式表示

\overrightarrow{t} = (t_1,t_2)^t, \overrightarrow{\omega} = (\omega_1,\omega_2)^t, \overrightarrow{\omega}^t\overrightarrow{t} = \omega_1t_1+\omega_2t_2

則上述兩式則可表示為

S(j\overrightarrow{\omega}) = \int_{-\infty}^{\infty}\int_{-\infty}^{\infty}s(\overrightarrow{t})e^{j\overrightarrow{\omega}^t\overrightarrow{t}}\,d\overrightarrow{t},\ \     
s(\overrightarrow{t}) =\frac{1}{4\pi^{2}} \int_{-\infty}^{\infty}\int_{-\infty}^{\infty}S(j\overrightarrow{\omega})e^{j\overrightarrow{\omega}^t\overrightarrow{t}}\,d\overrightarrow{\omega}

## 二維離散傅立葉變換
一般在作影像處理的影像大多不是連續信號，而對於平面上的不連續信號，我們則需使用二維離散傅立葉變換。

假設輸入的影像s[n,m]水平方向長度是N，垂直方向長度是M  

二維離散傅立葉變換定義為

S(j\omega_1,j\omega_2) = \sum_{m=-\infty}^{\infty}\sum_{n=-\infty}^{\infty}s[n,m]e^{-j(\omega_1n+\omega_2m)}

二維離散傅立葉逆變換定義為

s[n,m] = \frac{1}{4\pi^2}\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}S(j\omega_1,j\omega_2)e^{j(\omega_1n+\omega_2m)}\,d\omega_1\,d\omega_2
 
同樣為了方便，我們可將上述兩式改為向量形式

S(j\overrightarrow{\omega}) = \int_{-\infty}^{\infty}\int_{-\infty}^{\infty}s(\overrightarrow{n})e^{j\overrightarrow{\omega}^t\overrightarrow{n}}\,d\overrightarrow{n},\ \     
s(\overrightarrow{n}) =\frac{1}{4\pi^{2}} \int_{-\infty}^{\infty}\int_{-\infty}^{\infty}S(j\overrightarrow{\omega})e^{j\overrightarrow{\omega}^t\overrightarrow{n}}\,d\overrightarrow{\omega}

其中,\overrightarrow{n} = (n,m)^t 。

## 基本性質

下列為二維連續傅立葉變換的性質，大致與一維傅立葉變換的性質相似
### 分離性(Separability)
假如s(t_1,t_2)可分解為f(t_1)g(t_2)，因為自然指數部分也可分解，則

S(j\omega_1,j\omega_2) = \int_{-\infty}^{\infty}\int_{-\infty}^{\infty}s(t_1,t_2)e^{j(\omega_1t_1+\omega_2t_2)}\,dt_1\,dt_2
                             = \int_{-\infty}^{\infty}f(t_1)e^{j\omega_1t_1}\,dt_1\int_{-\infty}^{\infty}g(t_2)e^{j\omega_2t_2}\,dt_2 
                             = F(j\omega_1)G(j\omega_2)
                             = \mathcal{F}\{f(t_1)\}\mathcal{F}\{g(t_2)\} 

稱為分離性。

### 對稱性
假設s(\overrightarrow{t})為實數，則S(j\overrightarrow{\omega}) = S^*(-j\overrightarrow{\omega})

假設s(\overrightarrow{t})為實數且偶對稱，則S(j\overrightarrow{\omega})為實數且偶對稱

假設s(\overrightarrow{t})為實數且奇對稱，則jS(j\overrightarrow{\omega})為實數且奇對稱

### 平移特性
\mathcal{F}\{s(\overrightarrow{t}-\overrightarrow{t_0})\} = e^{-j\overrightarrow{\omega}^t\overrightarrow{t_0}}S(\overrightarrow{\omega})

一維傅立葉變換的平移概念是讓信號在時間軸上延遲、提前，相對的，二維傅立葉變換的平移概念是讓影像在空間域作位移，但兩者對應在頻域的概念卻是相同的，也就是將頻域作相位位移。

### 微分

\mathcal{F}\{\frac{\partial ^ns(\overrightarrow{t})}{\partial t_i^n}\} = (j\omega_i)^nS(j\overrightarrow{\omega}) 

原函數n階偏微分的傅立葉變換，為原函數的傅立葉變換乘上(j\omega_i)^n 。

### 線性特性
由於二維傅立葉變換與一維傅立葉變換同為積分運算，所以仍有線性特性。

 \mathcal{F}\{af(\overrightarrow{t})+bg(\overrightarrow{t})\} = 
\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}[af(\overrightarrow{t})+bg(\overrightarrow{t})]e^{j\overrightarrow{\omega}^t\overrightarrow{t}}\,d\overrightarrow{t}
= a\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}f(\overrightarrow{t})e^{j\overrightarrow{\omega}^t\overrightarrow{t}}\,d\overrightarrow{t}
+ b\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}g(\overrightarrow{t})e^{j\overrightarrow{\omega}^t\overrightarrow{t}}\,d\overrightarrow{t}


=a\mathcal{F}\{f(\overrightarrow{t})\}+b\mathcal{F}\{g(\overrightarrow{t})\}


### 線性比例調整

S(j\overrightarrow{\omega}) = \int_{-\infty}^{\infty}\int_{-\infty}^{\infty}s(\overrightarrow{t})e^{j\overrightarrow{\omega}^t\overrightarrow{t}}\,d\overrightarrow{t},\ \     

 \mathcal{F}\{s(a\overrightarrow{t})\} = \frac{1}S(\frac{j\overrightarrow{\omega}}{a}) 

一維傅立葉變換的線性比例調整是讓信號在時間軸上加速或減速，相對的，二維傅立葉變換的線性比例調整則是讓影像在空間域以某個點放大或縮小，但不論是在時域或空間域作線性比例調整，均也會在頻域產生線性比例調整。

### 卷積特性

\mathcal{F}\{f(\overrightarrow{t})*g(\overrightarrow{t})\} = \mathcal{F}\{f(\overrightarrow{t})\}\mathcal{F}\{g(\overrightarrow{t})\} 

卷積特性大至與一維傅立葉變換相同。

## 空間頻率
聲音是只有時間一個維度的信號，而靜態的平面影像則是具有兩個維度的信號。一維傅立葉轉換常被用來分析隨時間變化的信號，將信號變換至頻域並得到信號的頻域成分強度與相位。然而，對一張的靜態的平面影像而言，雖然沒有時間的概念在裡面，取而代之的是二維空間域的觀念。二維傅立葉變換的目的是將信號由空間域轉到頻域，除此之外，我們也引入了空間頻率這個新的概念來取代傳統一維空間中的頻率。

對傳統隨時間變化的信號而言，以聲音為例，低頻成分的物理意義即為聲音的低音，而高頻成分的物理意義則是聲音的高音。但對空間頻率而言，空間頻率中的低頻成分指的是圖片中顏色緩慢變化的部分。相對的，空間頻率中的高頻成分則是指圖片中顏色迅速變化的部分，比方說物體的邊線。

我們可以用二維的濾波器分別將圖片的低頻與高頻成分濾掉以幫助我們了解空間頻率的概念。我們可以發現，當圖片通過低通濾波器後，被濾出來的圖片是一個模糊的影像，這就是圖片的低頻成分。而當圖片通過高通濾波器後，被濾出來的圖片僅剩下邊緣，這就是圖片的高頻成分，一般而言，圖片在頻域的能量大多集中在低頻，離散傅立葉餘弦轉換變是利用這個特性來進行有損壓縮。

## 應用
二維傅立葉變換的作用是將影像由空間域變換到頻域，並對於影像不同頻段的成分進行分析與處理，所以二維傅立葉變換在影像處理領域有著舉足輕重的地位，其主要的應用為
* 影像分析
* 影像濾波
* 影像重建
* 影像壓縮

## 參考資料

*Oppenheim & Willsky, “Signals & Systems”, 2nd Ed. 1997, Prentice-Hall

*http://fourier.eng.hmc.edu/e101/lectures/image_processing/node6.html

*http://fourier.eng.hmc.edu/e101/lectures/image_processing/node7.html

*http://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm

*http://www.cs.toronto.edu/~jepson/csc320/notes/linearFilters2.pdf