s1083520 作業3

 1112 Digital Image Processing Assignment #3

主題: 離散傅立葉轉換 DFT 練習

題目敘述

撰寫傅利葉轉換程式(Forward Fourier Transform and Inverse Fourier Transform)將一張

圖像轉換至頻域後，將頻譜大小與相位角度各以灰階256 色圖像方式呈現出，再呈現還

原後圖像。

開發環境

OS: Windows 10
Editor: Visual Studio Code
Compiler: GCC - 12.2.0(MinGW-W64)
Language: C++
Package: OpenCV - 4.7.0

實作方法

A. 頻譜大小與相位角度 (Forward Fourier Transform)

(1) 使用FFT algorithm實作DFT以加速運算

(2) 先撰寫FFT函數提供FFT2d函數使用，以便對一張2維的圖像做DFT

      FFT只做一維的FFT運算

      運算完後得到一個原圖像轉換為複數的矩陣

(3) 將這個複數矩陣使用cv::split函數將複數分割成只有real part以及imaginary part的矩陣

      real part表示震幅 imaginary part表示的相位

(4) 使用cv::magnitude函數將頻譜大小提取出來

      為了方便觀察，通常會對其做log運算以及shift

      log運算: 將原來的值+1後做log運算， M_1 = log(1 + M)

      shift: 將原來從0~2pi的頻譜轉換為-pi~pi的頻譜，頻譜圖像左上及右下做交換，右上及左下做交換

(5) 使用cv::phase函數將相位角度提取出來

      這邊只做shift，操作同magnitude，頻譜圖像左上及右下做交換，右上及左下做交換

(6) 將magnitude及phase使用imshow將圖片顯示

B. 還原圖像 (Inverse Fourier Transform)

(1) 將A(1)中得到的複數的矩陣做Inverse Fourier Transform

(2) 由於在做 Forward Fourier Transform時矩陣會有real part以及imaginary part兩個channel

      此時必須使用cv::extractChannel函數只將real part提取出來再使用imshow將原圖像顯示

      否則imshow會報錯顯示Invalid number of channels in input image(scn is 2)

(3) 由於在一開始，我們會將圖像進行padding，因此最後需要使用Rect擷取我們padding前的圖像

FFT algorithm使用Cooley-Tukey algorithm: (以下來自wiki)

由此可以利用此思想，recursively 呼叫FFT函數，直到n為1時停止遞迴呼叫

而Forward Fourier Transform(FFT)及Inverse Fourier Transform (IFFT)主要差別只在exponential中的正負號，因此可以將FFT函數設計成含有inverse參數的函數

- 如果inverse傳入是1時，執行Forward Fourier Transform

- 如果inverse傳入是-1時，執行Inverse Fourier Transform

FFT 核心部分:

    

    if (N <= 1) {

        return;

    }

    vector<Complex_> even(N / 2), odd(N / 2);

    for (int i = 0; i < N / 2; i++) {

        even[i] = x[2 * i];

        odd[i] = x[2 * i + 1];

    }

    fft(even, inverse);

    fft(odd, inverse);

    for (int k = 0; k < N / 2; k++) {

        Complex_ w(cos(2 * CV_PI * k / N),

sin(2 * inverse * CV_PI * k / N));

        Complex_ t = w * odd[k];

        x[k] = even[k] + t;

        x[k + N / 2] = even[k] - t;

    }

呼叫FFT前的預處理

在呼叫FFT函數前，先將原來圖像填充成2^m * 2^n的圖像以利FFT的運算

(其中2^m為第一個大於或等於img.rows的2的次方數，2^n為第一個大於或等於img.cols的2的次方數)

使用cv::copyMakeBorder函數將圖像填充，填充值為0

由於圖像使用imread讀入時，此時的矩陣只有實數值，但在FFT運算時，我們需要有虛數部分，

因此可以使用Mat::zero來建立一個與填充完後大小相同的矩陣，充當虛數部分的矩陣

最後使用cv::merge函數將原來圖像的實數部分與新建立的虛數部分做merge，成為一個channel為2的矩陣傳入FFT2d進行運算

FFT2d則使用FFT進行運算，先對矩陣的每個row做運算後，再對每個col做運算

for each row in matComplex

    FFT(row, inverse)

for each col in matComplex

    FFT(col, inverse)

實作結果

頻譜大小(Magnitude)

相位角度(Phase)

還原後的圖像