c語言數字影象處理（六）：二維離散傅立葉變換
摘要：
基礎知識
複數表示
C = R + jI
極座標：C = |C|(cosθ + jsinθ)
尤拉公式：C = |C|e jθ
有關更多的時域與複頻域的知識可以學習複變函式與積分變換，本篇文章只給出DFT公式，性質，以及實現方法
二維離散傅立葉變換(DFT)
...
基礎知識
複數表示
C = R + jI
極座標：C = |C|(cosθ + jsinθ)
尤拉公式：C = |C|e jθ
有關更多的時域與複頻域的知識可以學習複變函式與積分變換，本篇文章只給出DFT公式，性質，以及實現方法
二維離散傅立葉變換(DFT)
其中f(x,y)為原影象，F(u,v)為傅立葉變換以後的結果，根據尤拉公式可得，每個F(u,v)值都為複數，由實部和虛部組成
程式碼示例
1 void dft(short** in_array, double** re_array, double** im_array, long height, long width)
2 {
3double re, im, temp;
4
5for (int i = 0; i < height; i++){
6for (int j = 0; j < width; j++){
7re = 0;
8im = 0;
9
10for (int x = 0; x < height; x++){
11for (int y = 0; y < width; y++){
12temp = (double)i * x / (double)height +
13(double)j * y / (double)width;
14re += in_array[x][y] * cos(-2 * pi * temp);
15im += in_array[x][y] * sin(-2 * pi * temp);
16}
17}
18
19re_array[i][j] = re;
20im_array[i][j] = im;
21}
22}
23printf("dft done\n");
24 }
傅立葉譜
相角
功率譜
傅立葉變換頻譜圖
對於上面得兩幅圖案，在區間[0, M-1]中，變換資料由兩個在點M/2處碰面的背靠背的半個週期組成
針對顯示和濾波的目的，在該區間中有一個完整的變換週期更加方便，因為完整週期中資料是連續的
我們希望得到上圖所示的圖案
傅立葉變換的平移性質
因此對每個f(x, y)項乘以(-1) x+y 可達目的
程式碼示例
1 void fre_spectrum(short **in_array, short **out_array, long height, long width)
2 {
3double re, im, temp;
4int move;
5
6for (int i = 0; i < height; i++){
7for (int j = 0; j < width; j++){
8re = 0;
9im = 0;
10
11for (int x = 0; x < height; x++){
12for (int y = 0; y < width; y++){
13temp = (double)i * x / (double)height +
14(double)j * y / (double)width;
15move = (x + y) % 2 == 0 ? 1 : -1;
16re += in_array[x][y] * cos(-2 * pi * temp) * move;
17im += in_array[x][y] * sin(-2 * pi * temp) * move;
18}
19}
20
21out_array[i][j] = (short)(sqrt(re*re + im*im) / sqrt(width*height));
22if (out_array[i][j] > 0xff)
23out_array[i][j] = 0xff;
24else if (out_array[i][j] < 0)
25out_array[i][j] = 0;
2627}
28}
29 }
執行結果
旋轉性質
即f(x, y)旋轉一個角度，F(u, v)旋轉相同的角度
二維離散傅立葉反變換
程式碼示例
1 void idft(double** re_array, double** im_array, short** out_array, long height, long width)
2 {
3double real, temp;
4
5for (int i = 0; i < height; i++){
6for (int j = 0; j < width; j++){
7real = 0;
8
9for (int x = 0; x < height; x++){
10for (int y = 0; y < width; y++){
11temp = (double)i * x / (double)height +
12(double)j * y / (double)width;
13
14real += re_array[x][y] * cos(2 * pi * temp) -
15im_array[x][y] * sin(2 * pi * temp);
16}
17}
18
19out_array[i][j] = (short)(real / sqrt(width*height));
20if (out_array[i][j] > 0xff)
21out_array[i][j] = 0xff;
22else if (out_array[i][j] < 0)
23out_array[i][j] = 0;
24}
25}
26printf("idft done\n");
27 }
經驗證，影象經傅立葉變換，然後再反變換以後可恢復原圖
改進
本篇文章只是按照二維離散傅立葉變換公式進行了實現，在測試的過程中發現，執行速度真的是非常慢，演算法時間複雜度O(n 4 )，等以後有時間再對這段程式碼進行優化。