基础知识
复数表示
C = R + jI
极坐标: C = |C|(cosθ + jsinθ)
欧拉公式: C = |C|ejθ
有关更多的时域与复频域的知识可以学习复变函数与积分变换, 本篇文章只给出 DFT 公式, 性质, 以及实现方法
二维离散傅里叶变换(DFT)
其中 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");
- }
傅里叶谱
相角
功率谱
傅里叶变换频谱图
对于上面得两幅图案, 在区间 [0, M-1] 中, 变换数据由两个在点 M/2 处碰面的背靠背的半个周期组成
针对显示和滤波的目的, 在该区间中有一个完整的变换周期更加方便, 因为完整周期中数据是连续的
我们希望得到上图所示的图案
傅里叶变换的平移性质
因此对每个 f(x, y)项乘以(-1)x+y 可达目的
代码示例
- void fre_spectrum(short **in_array, short **out_array, long height, long width)
- {
- double re, im, temp;
- int move;
- 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;
- move = (x + y) % 2 == 0 ? 1 : -1;
- re += in_array[x][y] * cos(-2 * pi * temp) * move;
- im += in_array[x][y] * sin(-2 * pi * temp) * move;
- }
- }
- out_array[i][j] = (short)(sqrt(re*re + im*im) / 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;
- 27 }
- }
- }
执行结果
旋转性质
即 f(x, y)旋转一个角度, F(u, v)旋转相同的角度
二维离散傅里叶反变换
代码示例
- 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), 等以后有时间再对这段代码进行优化.
来源: https://www.cnblogs.com/GoldBeetle/p/9807399.html