c语言数字图像处理（六）：二维离散傅里叶变换

骑猪看日落 2023-01-20 09:43 13阅读 0赞

## 基础知识 ##

### 复数表示 ###

C = R + jI

极坐标：C = |C|(cosθ + jsinθ)

欧拉公式：C = |C|ejθ

有关更多的时域与复频域的知识可以学习复变函数与积分变换，本篇文章只给出DFT公式，性质，以及实现方法

## 二维离散傅里叶变换(DFT) ##

![81dec1bf1e86f14c7b6b680f004b91a9.png][]

其中f(x,y)为原图像，F(u,v)为傅里叶变换以后的结果，根据欧拉公式可得，每个F(u,v)值都为复数，由实部和虚部组成

### 代码示例 ###

void dft(short** in_array, double** re_array, double** im_array, long height, long width)
    {
        double re, im, temp;
    
        for (int i = 0; i < height; i++){
            for (int j = 0; j < width; j++){
                re = 0;
                im = 0;
    
                for (int x = 0; x < height; x++){
                    for (int y = 0; y < width; y++){
                        temp = (double)i * x / (double)height +
                               (double)j * y / (double)width;
                        re += in_array[x][y] * cos(-2 * pi * temp);
                        im += in_array[x][y] * sin(-2 * pi * temp);
                    }
                }
    
                re_array[i][j] = re;
                im_array[i][j] = im;
            }
        }
        printf("dft done\n");
    }

## 傅里叶谱 ##

![8c27b970e9285bfe555e35247022784e.png][]

## 相角 ##

![2ecff7ff8fce19efe3dd37ceb730c4a3.png][]

## 功率谱 ##

![e22b39f01a48f622e1e6f9a0852da839.png][]

### 傅里叶变换频谱图 ###

![9426a6f8ce50f3321c38b7f8dc98154d.png][]

![6a55da81a4865cefad80e4dc237901e7.png][]

对于上面得两幅图案，在区间\[0, M-1\]中，变换数据由两个在点M/2处碰面的背靠背的半个周期组成

![1abe7295e5c3da5d45e3e6bf12088f7a.png][]

针对显示和滤波的目的，在该区间中有一个完整的变换周期更加方便，因为完整周期中数据是连续的

![39182dd0b9006bf46e91089fae8a747e.png][]

我们希望得到上图所示的图案

## 傅里叶变换的平移性质 ##

![6ab177e48cacad920648852a14940dea.png][]

因此对每个f(x, y)项乘以(-1)x+y可达目的

### 代码示例 ###

1 void fre_spectrum(short **in_array, short **out_array, long height, long width)
     2 {
     3     double re, im, temp;
     4     int move;
     5 
     6     for (int i = 0; i < height; i++){
     7         for (int j = 0; j < width; j++){
     8             re = 0;
     9             im = 0;
    10 
    11             for (int x = 0; x < height; x++){
    12                 for (int y = 0; y < width; y++){
    13                     temp = (double)i * x / (double)height + 
    14                            (double)j * y / (double)width;
    15                     move = (x + y) % 2 == 0 ? 1 : -1;
    16                     re += in_array[x][y] * cos(-2 * pi * temp) * move;
    17                     im += in_array[x][y] * sin(-2 * pi * temp) * move;
    18                 }
    19             }
    20             
    21             out_array[i][j] = (short)(sqrt(re*re + im*im) / sqrt(width*height));
    22             if (out_array[i][j] > 0xff)
    23                 out_array[i][j] = 0xff;
    24             else if (out_array[i][j] < 0)
    25                 out_array[i][j] = 0;
    26  27         }
    28     }
    29 }

### 执行结果 ###

![51618cb976ed5d5708cb359a50b1f054.png][]

## ![7611dde5d83048f396a41d23fefe4305.png][] ##

## 旋转性质 ##

![20b6d54b033843dfb50c45f8798a38b2.png][]

![782d35e8fb7ba13fba9971dd623ff526.png][]

即f(x, y)旋转一个角度，F(u, v)旋转相同的角度

![b8e110fd3897c940be2cf1eacfdfdbee.png][]

## 二维离散傅里叶反变换 ##

![1471d18298532b9d858e1967d7c0374e.png][]

### 代码示例 ###

void idft(double** re_array, double** im_array, short** out_array, long height, long width)
    {
        double real, temp;
    
        for (int i = 0; i < height; i++){
            for (int j = 0; j < width; j++){
                real = 0;
    
                for (int x = 0; x < height; x++){
                    for (int y = 0; y < width; y++){
                        temp = (double)i * x / (double)height +
                               (double)j * y / (double)width;
    
                        real += re_array[x][y] * cos(2 * pi * temp) -
                                im_array[x][y] * sin(2 * pi * temp);
                    }
                }
    
                out_array[i][j] = (short)(real / sqrt(width*height));
                if (out_array[i][j] > 0xff)
                    out_array[i][j] = 0xff;
                else if (out_array[i][j] < 0)
                    out_array[i][j] = 0;
            }
        }
        printf("idft done\n");
    }

经验证，图像经傅里叶变换，然后再反变换以后可恢复原图

## 改进 ##

本篇文章只是按照二维离散傅里叶变换公式进行了实现，在测试的过程中发现，执行速度真的是非常慢，算法时间复杂度O(n4)，等以后有时间再对这段代码进行优化。

[81dec1bf1e86f14c7b6b680f004b91a9.png]: /images/20221021/09067cb2dc634c0ab46e9c19965b26f4.png
[8c27b970e9285bfe555e35247022784e.png]: /images/20221021/ae6076ca31b344fba72ff069dd874621.png
[2ecff7ff8fce19efe3dd37ceb730c4a3.png]: /images/20221021/a70ff2be08bb42838fdd48380646b036.png
[e22b39f01a48f622e1e6f9a0852da839.png]: /images/20221021/59e7b85ba57a4d67b1d6fdd145e1422a.png
[9426a6f8ce50f3321c38b7f8dc98154d.png]: /images/20221021/3e5699131ed7453aba417bf08b16bc2d.png
[6a55da81a4865cefad80e4dc237901e7.png]: /images/20221021/de13c01877a64bbf88cf8af1a50e72ae.png
[1abe7295e5c3da5d45e3e6bf12088f7a.png]: /images/20221021/d949bcdcf11d42f892de46c689c6aef6.png
[39182dd0b9006bf46e91089fae8a747e.png]: /images/20221021/23c97e9154794e98a8978c2bc08db8a8.png
[6ab177e48cacad920648852a14940dea.png]: /images/20221021/fbc7fc06ec674523b9e3b3de4b9fcc4a.png
[51618cb976ed5d5708cb359a50b1f054.png]: /images/20221021/a77bed74346140148165a43733c425e8.png
[7611dde5d83048f396a41d23fefe4305.png]: /images/20221021/c2fcb419847c446d9daf1fb1f8701edd.png
[20b6d54b033843dfb50c45f8798a38b2.png]: /images/20221021/16b971d86a6047b9b0dd7d30292a521e.png
[782d35e8fb7ba13fba9971dd623ff526.png]: /images/20221021/6d9e3fc7f82b48979dc45aac82ce6f23.png
[b8e110fd3897c940be2cf1eacfdfdbee.png]: /images/20221021/bea7b7000d8048999eb6aeb245c71138.png
[1471d18298532b9d858e1967d7c0374e.png]: /images/20221021/fc62b37376d04d56916ccdcb96841560.png