文档介绍：第十三讲图像变换(三)
【目录】
一、快速傅立叶变换 1
1、推导 1
2、举例 2
3、分析 5
二、余弦变换 6
1、定义 6
2、命令 6
3、基础函数 8
4、应用 9
【正文】
一、快速傅立叶变换
1、推导
二维的傅立叶变换可以用一维的傅立叶变换来实现。所以下面所说的快速傅立叶变换(FFT)是指一维的快速傅立叶变换。
一维的离散傅立叶变换(DFT)表达式为:
令,则:
假定,则:
对于,用来表示时,有:
所以有:
因为有:
所以:
定义:
第一项:
第二项:
则:
,其中:
另外:
要求个数的傅立叶变换,只要先求出其中个偶数项的傅立叶变换值和个奇数项的傅立叶变换值,用上述两个公式就能得到整个的变换值。
2、举例
下面以为例,分解:
令:
则:
其中。因为有:
所以我们只要计算就可以得到8个傅立叶变化值了。
如下图所示。
Fe(0)
Fe(1)
Fe(2)
Fe(3)
F0(0)
F0(1)
F0(2)
F0(3)
F(0)
F(1)
F(2)
F(3)
F(5)
F(6)
F(7)
F(4)
其中每一组表示一个蝶形运算。Fe(U)、Fo(U)可进一步分成两部分。直至分到两个数的傅立叶变换。
f0(0)
f0(4)
f0(2)
f0(6)
f0(1)
f0(5)
f0(3)
f0(7)
f1(0)
f1(4)
f1(2)
f1(6)
f1(1)
f1(5)
f1(3)
f1(7)
f2(0)
f2(2)
f2(4)
f2(6)
f2(1)
f2(3)
f2(5)
f2(7)
F(0)
F(1)
F(2)
F(3)
F(4)
F(5)
F(6)
F(7)
对于两个数的傅立叶变换,可直接由变换公式得:
【例】
f0=[14 24 98 45 56 66 23 56];f1=zeros(1,8);f2=f1;F=f1;
W4=exp(-j*2*pi/4);W8=exp(-j*2*pi/8);
% N=2
f1(1)=f0(1)+f0(5);f1(5)=f0(1)-f0(5);
f1(3)=f0(3)+f0(7);f1(7)=f0(3)-f0(7);
f1(2)=f0(2)+f0(6);f1(6)=f0(2)-f0(6);
f1(4)=f0(4)+f0(8);f1(8)=f0(4)-f0(8);
% N=4
f2(1)=f1(1)+W4^0*f1(3);f2(5)=f1(1)-W4^0*f1(3);
f2(3)=f1(5)+W4^1*f1(7);f2(7)=f1(5)-W4^1*f1(7);
f2(2)=f1(2)+W4^0*f1(4);f2(6)=f1(2)-W4^0*f1(4);
f2(4)=f1(6)+W4^1*f1(8);f2(8)=f1(6)-W4^1*f1(8);
% N=8
F(1)=f2(1)+W8^0*f2(2);F(5)=f2(1)-W8^0*f2(2);
F(2)=f2(3)+W8^1*f2(4);F(6)=f2(3)-W8^1*f2(4);
F(3)=f2(5)+W8^2*f2(6);F(7)=f2(5)-W8^2*f2(6)