2.4 經典變換

2.4.1 快速傅里葉變換

快速傅里葉變換（Fast Fourier Transform，FFT）是利用計算機計算離散傅里葉變換（Discrete Fourier Transform，DFT）的高效、快速計算方法的統稱，簡稱FFT，在1965年由Cooley和Tukey提出。FFT的本質就是DFT，可以將信號從時域變換到頻域，而且時域和頻域都是離散的。也就是說，FFT可以求出一個信號是由哪些正弦波疊加而成的，求出的結果就是這些正弦波的幅度和相位。例如，音樂播放器上面顯示的就是音樂信號經過FFT之后的不同頻率正弦波的幅度。在分析和合成語音信號時，在通信系統中實現全數字化的時分制與頻分制（TDM/FDM）的復用轉換時，在頻域對信號濾波及相關分析時，我們都可以利用對雷達、聲吶、振動信號的頻譜分析的方法來提高對目標的搜索精度和跟蹤的分辨率等。這些技術的應用都需要利用FFT。FFT具有計算量小的優點，能夠廣泛地應用在信號處理技術領域，再結合高速的硬件系統就可以實時處理信號。

首先來簡單了解一下DFT的基本原理。

1.連續信號的傅里葉變換

設x(t)表示非周期連續的時間信號，可以利用傅里葉變換求出該信號的頻譜信號。

式中，ω=2πf，f表示頻率；X(ω)為非周期信號，并且具有連續的頻率響應。

如果已知頻譜信號X(ω)，可以利用式（2.19）的反傅里葉變換公式計算其時域響應。

2.一維離散傅里葉變換

為了在計算機上實現傅里葉變換計算，必須把連續函數離散化。離散函數的傅里葉變換稱為離散傅里葉變換。

連續信號離散化過程如下。

（1）建立連續時間信號x(t)。

（2）設定采樣間隔Δt。

（3）對連續信號做時域等間隔采樣，得到離散序列x(kΔt)，k=0,1,2,N-1。

（4）得到具有N個元素的離散函數序列x(n)，x(n)可以利用式（2.20）計算求得。

式中，Ts表示采樣周期，且Ts=1/Fs，Fs為采樣頻率。

因此，一維離散傅里葉變換（DFT）和一維離散傅里葉反變換（Inverse DFT）可表示為：

式中，ω'=ω/Fs，代表歸一化后的頻率弧長。

3.二維離散傅里葉變換

對于一個具有M×N尺度的二維離散函數f(x,y)，(x=0,1,2,M-1;y=0,1,2,N-1)，其離散傅里葉變換可以表示為：

對于一個具有M×N尺度的二維離散函數F(u,v),(u=0,1,2,M-1;v=0,1,2,N-1)，其離散反傅里葉變換可以表示為：

在運用計算機進行二維離散傅里葉變換時，可先對每一行或者每一列進行一維的離散傅里葉變換，然后對上一步的計算結果再進行列或者行的一維離散傅里葉變換，具體步驟不再贅述。通過觀察不難發現，二維離散傅里葉變換具有許多非常實用的性質，主要包括可分離性、平移性、線性特性、比例特性、周期性和共軛對稱性、微分特性、旋轉特性等，因此，在數字圖像處理領域同樣發揮著重要的作用。

FFT是根據DFT的奇、偶、虛、實等特性，對DFT的算法進行改進獲得的。FFT的基礎原理是把已知的N點序列，按順序分解成一系列的短序列，再利用DFT計算式中指數因子所具有的對稱性質和周期性質，求出這些短序列相應的DFT并進行適當組合，實現重復計算，降低乘法運算次數進而簡化結構。當N是素數時，可以將DFT計算轉化為求循環卷積，從而進一步減少乘法次數，提高速度。FFT在傅里葉變換的理論中并沒有發現創新點，但是能夠將離散傅里葉變換應用在計算機系統，或者說，在數字系統中已經進了一大步。FFT的結果具有對稱性，通常只需要利用前半部分的結果即可，即小于采樣頻率一半的結果。

2.4.2 圖像變換

在計算機視覺領域，所謂的圖像變換技術，就是為了更加快速有效地處理和分析圖像。首先，需要通過某種形式將原定義在圖像空間的圖像轉化到另外的空間，然后利用空間的特性對圖像進行一定的加工，最后再轉換回圖像空間得到所需的效果。許多圖像處理和分析技術都是以圖像變換技術為背景的，上文提到的傅里葉變換是應用最廣泛和重要的圖像變換手段之一。為了提高運算速度，計算機中多采用快速傅里葉變換算法。

對于數字圖像而言，圖像變換的作用對象為一個個獨立的像素點，每一個像素點的值由多個通道的數值組合表示，而圖像變換就是針對這些具體的像素值來操作的。在后面的實驗章節，我們將結合Python語言及工具庫，對幾種比較簡單的圖像變換方法進行實驗驗證。

教材配套演示實驗中包含了計算機視覺中經常使用的兩個圖像變換實例。為方便理解，現對這兩個變換的基本原理進行簡單的講解。

1.Gamma變換

Gamma變換是對輸入圖像灰度值進行的非線性操作，使輸出圖像灰度值與輸入圖像灰度值呈指數關系，這個指數即Gamma。變換公式如下：

其中，Vin的取值范圍為0～1，因此，在程序中需要先進行歸一化處理，然后再進行指數運算。

人眼對外界光源的感光值與輸入光強二者之間滿足指數型關系。換句話說，就是在低照度下，人眼更容易分辨出亮度的變化，但光照強度的逐漸增加使得人眼不易分辨出亮度的變化，但是攝像機感光與輸入光強二者之間滿足線性關系。Gamma變換主要用于圖像增強，可以提升圖像黑暗部分細節的亮度。簡單來說，就是通過非線性變換，讓圖像從曝光強度的線性響應變得更接近人眼感受的響應，即對過曝或曝光不足的圖片進行矯正。

輸入值經過Gamma變換后輸出的圖像灰度值關系如圖2-1所示：橫坐標表示輸入灰度值，縱坐標表示輸出灰度值，上方曲線表示的是gamma值小于1時的輸入輸出關系，下方曲線表示的是gamma值大于1時的輸入輸出關系。從圖2-1可以看出，當gamma值小于1時，圖像的整體亮度值得到提升，同時低灰度處的對比度得到增加，因而更利于分辨低灰度值時的圖像細節。

Gamma變換規律可以總結如下：

gamma>1，較亮的區域灰度被拉伸，較暗的區域灰度被壓縮得更暗，圖像整體變暗；

gamma<1，較亮的區域灰度被壓縮，較暗的區域灰度被拉伸得較亮，圖像整體變亮。

2.卷積

卷積，有時也叫算子。用一個模板去和另一個圖片對比，進行卷積運算，目的是使目標與目標之間的差距變得更大。卷積在數字圖像處理中常見的應用為銳化和邊緣提取。例如邊緣提取，假如目標像素點和它周邊的值有較大差異，就可以通過這個算子對原圖矩陣中的這個位置進行卷積運算，得出的值和該像素點原來的灰度值會有顯著的差異。當這種前后差異超過我們預設的范圍后，就將這個像素點標記為0（白色），其余點標記為255（黑色），這樣就得到了一幅以黑色為背景，白色線條作為邊緣或形狀的邊緣提取效果圖。

幾個常用術語如下。

模板。模板就是一個矩陣（其實就是下面說的卷積核），也就是處理圖像這個過程對應的函數，它對應卷積運算。

卷積運算。它可以看作加權求和的過程，為了增強圖像和減少噪聲，用該像素點的鄰域像素點進行加權，處理完之后得到這個點的像素點。

卷積核。上面說的卷積運算，需要確定點的鄰域和哪個矩陣進行加權，以及鄰域內像素點所占的權重是多少。這些權重構成的矩陣就叫卷積核，卷積核的行數和列數都是奇數。

舉例來說，對于數字圖像來說，已知矩陣R和G，如果要對R5這個像素點進行卷積運算，有式（2.26）成立，這個卷積核的數組直接決定卷積的結果。

使用卷積核的時候會出現一個問題——邊界問題：當處理圖像邊界像素時，如果卷積核不能匹配于圖像使用區域，卷積核的中心與邊界像素點對應，卷積運算會出現問題。一般可以選擇如下兩種處理方法：

（1）忽略邊界像素，即處理后的圖像將丟掉這些像素；

（2）保留原邊界像素，即復制邊界像素到處理后的圖像。