第二章数字图象处理基础第三节频域变换数字图象处理北京大学计算机研究所 陈晓鸥第二章数字图象处理基础第三节频域变换第三节 频域变换
2.3.1 傅立叶变换导言
– 理论基础、连续与离散的傅立叶变换
2.3.2 二维傅立叶变换特性
– 可分离性、周期与共轭对称、平移性、
– 旋转特性、线性与相似性,均值性、
– 拉普拉斯、卷积与相关
2.3.3 快速傅立叶变换
– FFT算法,逆向 FFT算法、算法实现第二章数字图象处理基础第三节频域变换第三节 频域变换
2.3.1 傅立叶变换导言
– 理论基础
– 连续与离散的傅立叶变换第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,理论基础
理论基础
– 线性系统
– 卷积与相关第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,理论基础
线性系统
– 系统 的定义：
接受一个输入，并产生相应输出的任何实体。
系统的输入是一个或两个变量的函数，输出是相同变量的另一个函数。
系统x(t)输入 y(t)输出第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,理论基础
线性系统
– 线性系统 的定义：
对于某特定系统，有：
x1(t) y1(t)
x2(t) y2(t)
该系统是线性的当且仅当：
x1(t) + x2(t) y1(t) +
y2(t)
从而有,a*x1(t) a*y1(t)
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,理论基础
线性系统
– 线性系统 移不变性 的定义：
对于某线性系统,有：
x(t) y(t)
当输入信号沿时间轴平移 T,有：
x(t - T) y(t - T)
则称该线性系统具有移不变性第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,理论基础
卷积
– 卷积的定义
– 离散一维卷积
– 二维卷积的定义
– 离散二维卷积
– 相关的定义第二章数字图象处理基础第三节频域变换第三节 频域变换,理论基础
– 卷积 的定义
对于一个线性系统的输入 f(t)和输出 h(t)，如果有一个一般表达式，来说明他们的关系，对线性系统的分析，将大有帮助
卷积积分就是这样的一般表达式
h(t) =? g(t -?)f(?)d? 记为,h = g *
f
-?
g(t)称为 冲激响应函数第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,理论基础
– 离散一维卷积
h(i) = f(i)*g(i) =? f(j)g(i-j)
j
– 二维卷积的定义
h(x,y) = f*g = f(u,v)g(x – u,y –
v)dudv
-?
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,理论基础
– 离散二维卷积
h(x,y) = f*g = f(m,n)g(x – m,
y – n)
m n
– 相关 的定义
h(t) =? g(t +?)f(?)d? 记为,y = g? x
-?
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
连续与离散的傅立叶变换
– 一维连续傅立叶变换
– 二维连续傅立叶变换
– 离散傅立叶变换
– 离散傅立叶变换的计算与显示第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
一维连续傅立叶变换：定义设 f(x)为实变量 x的连续函数,
f(x)的 傅立叶变换 表示为 F{f(x)},
定义为：
F{f(x)} = F(u) =? f(x)exp(-
j2?ux)dx
-?
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
一维连续傅立叶逆变换：定义如果给定 F(u),f(x)可以由 傅立叶逆变换 得到：
F{F(u)} = f(x) =?
F(u)exp(j2?ux)du
-?
其中 j2 = -1
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
一维连续傅立叶变换：几个概念假设函数 f(x)为实函数 。 但一个实函数的傅立叶变换可能为复函数：
F(u) = R(u) + jI(u)
（ 1） f(x)的傅立叶 模 记为,|F(u)|
|F(u)| = [R2(u) + I2(u)]1/2
（ 2） f(x)的傅立叶 模平方 记为,P(u)
P(u) = |F(u)|2 = R2(u) + I2(u)
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
一维连续傅立叶变换：几个概念
（ 3） f(x)的傅立叶 相位 记为,?(u)
(u) = tan-1 (I(u) / R(u))
（ 4） 傅立叶变换中的变量 u通常称为 频率变量这个名称源于尤拉公式中的指数项
exp[-j2?ux] = cos2?ux - jsin2?ux
如果把傅立叶变换的积分解释为离散项的和,
则易推出 F(u)是一组 sin和 cos函数项的无限和,其中 u
的每个值决定了其相应 cos,sin函数对的频率 。
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
二维连续傅立叶变换如果 f(x,y)连续可积,并且 F(u,v)可积,
则存在以下傅立叶变换对,其中 u,v为频率变量：
F{f(x,y)}=F(u,v)=f(x,y)exp[-j2?(ux+vy)]dxdy
-?
F{F(u,v)}=f(x,y)=F(u,v)exp[j2?(ux+vy)]dudv
-?
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
二维连续傅立叶变换二维傅立叶模,相位和模平方分别为：
模,|F(u,v)| = [R2(u,v) +
I2(u,v)]1/2
相位,? (u,v) = tan-1 (I(u,v) /
R(u,v))
模平方,P(u,v) = |F(u,v)|2 = R2(u,v) +
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换假设连续函数 f(x),通过取 N个?x单位的采样点,被离散化为一个序列：
{f(x0),f(x0+?x),
f(x0+2?x),…,f(x0+[N–1]? x)}
无论将 x作为离散的或连续的变量,在子序列中来研究都将是方便的,仅仅依赖于讨论的上下文 。 为作到此要求定义,
f(x) = f(x0+ x?x)
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换其中假设 x现在的离散值是,0,1,2,…,N-1。
{f(x0),f(x0+?x),f(x0+2?x),...,
f(x0+[N–1]?x)}
表示相对与连续函数的任意 N个统一的空间采样第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换函数 f(x0+x?x)的离散傅立叶变换对有：
N-1
F(u) = 1/N? f(x)exp[-j2?ux/N]
x=0
u = 0,1,2,...N-1
N-1
逆变换,f(x) =? F(u)exp[j2?ux/N]
u=0
x = 0,1,2,...N-1
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换,二维
M-1 N-1
F(u,v) =1/MNf(x,y)exp[-j2?(ux/M+vy/N)]
x=0 y=0
u = 0,1,2,… M-1; v = 0,1,
2,...N-1
M-1 N-1
f(x,y) = F(u,v)exp[j2?(ux/M+vy/N)]
u=0 v=0
x = 0,1,2,...N-1; y = 0,1,
2,...N-1
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换的计算与显示
– 离散傅立叶变换的计算举例
– 离散傅立叶变换的显示第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换的计算举例
x
f(x0)=f(x0+?x)
0 1 2 3
1
2
3
4
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
F(0) = 1/4Σ f(x)exp[0]
= 1/4[f(0) + f1(1) + f(2) + f(3)]
= 1/4(2 + 3 + 4 + 4)= 3.25
F(1) = 1/4Σ f(x)exp[-j2π x/4)]
= 1/4(2e0 + 3e –j2π 1/4 + 4e –j2π 2/4 + 4e –
j2π3/4)
= 1/4(-2 + j)
F(2) = -1/4(1 + j0)
F(3) = -1/4(2 + j)
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换的计算举例
– 因为，函数 f(x,y)的傅立叶变换是 f(x,y)积分的函数
– 因此，计算每一个傅立叶变换值，原函数
f(x,y)的每一个点都需要参与第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换的显示通过对 傅立叶变换模,来显示傅立叶变换图象。由于模的值域大于显示的值域，因此要进行动态值域的压缩
D(u,v) = c log(1 + |F(u,v)|)
其中,c = 255 / k;
k = max(log(1 + |F(u,v)|))
值域 [0,k]的上限 （ 最大值 ）
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换的显示第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换的显示 ——对称平移后第二章数字图象处理基础第三节频域变换第三节 频域变换,二维傅立叶变换特性
2.3.2 二维傅立叶变换特性
可分离性
周期与共轭对称
平移性
旋转特性
线性与相似性
均值性
拉普拉斯
卷积与相关第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,可分离性
可分离性
– 二维离散傅立叶变换 DFT可分离性的基本思想是：
二维 DFT可分离为两次一维 DFT
– 应用：
二维快速傅立叶算法 FFT,是通过计算两次一维 FFT实现的第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,可分离性
可分离性的定义
M-1 N-1
F(u,v)=1/MN? [?f(x,y)e(-j2?vy/N)] e(-
j2?ux/M)
x=0 y=0
u = 0,1,2,… M-1; v = 0,1,2,...N-1
M-1 N-1
f(x,y)=? [?F(u,v)e(j2?vy/N)] e(j2?ux/M)
u=0 v=0
x = 0,1,2,...N-1; y = 0,1,2,...N-1
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,可分离性
可分离性成立的推导
– 先对行 （ y变量 ） 做变换：
N-1
F(x,v)=1/N?f(x,y)exp(-j2?vy/N)]
y=0
– 然后对列 （ x变量 ） 进行变换：
M-1
F(u,v)=1/M?F(x,v)exp(-j2?ux/M)]
x=0
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,可分离性
– 先对行做变换：
然后对列进行变换,
f(x,y)
（ 0,0）
（ N-1,M-1）x
y
F(x,v)
（ 0,0）
（ N-1,M-1）x
v
F(x,v)
（ 0,0）
（ N-1,M-1）x
v
F(u,v)
（ 0,0）
（ N-1,M-1）u
v
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,平移性
平移性定理
– 平移性的描述函数自变量的位移的傅立叶变换产生一个复系数
F{f(x-a,y-b)} = exp[-j2?(au+bv)]
F(u,v)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,平移性
平移性成立的证明用一维函数为例进行证明：
设位移为 a,f(x-a)的傅立叶变换为：
F{f(x-a)} = F(u) =? f(x-a)exp(-
j2?ux)dx
-?
将积分乘以 1 = exp(-j2?au) exp(j2?au)
且设,v = x-a,dv = dx
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,平移性
平移性成立的证明
F{f(x-a)} = F(u)
=? f(x-a)exp(-j2?ux) exp(-j2?au)exp(j2?au) dx
-?
=exp(-j2?au)? f(x-a)exp(-j2?ux)exp(j2?ua)dx
-?
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,平移性
= exp(-j2?au)? f(x-a)exp[-j2?u(x-a)]dx
-?
= exp(-j2?au)? f(v)exp[-j2?uv]dv
-?
= exp(-j2?au)F(u)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,周期与共轭对称
周期与共轭对称
– 周期性的描述,离散傅立叶变换 DFT和它的逆变换是以 N为周期的对于一维傅立叶变换有：
F(u) = F(u + N)
对于二维傅立叶变换有：
F(u,v) = F(u + M,v+N)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,周期与共轭对称
周期与共轭对称
– 共轭对称性的描述,傅立叶变换结果是以原点为中心的共轭对称函数对于一维傅立叶变换有：
F(u) = F*(-u)
对于二维傅立叶变换有：
F(u,v) = F*(-u,-v)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,周期与共轭对称
共轭对称性证明以一维傅立叶变换为例证明,
F(u) =∫ f(x)exp[-j2?ux]dx
=∫ f(x)exp[j2?(-u)x]dx
=∫ f(x)exp[-j2?(-u)x]*dx（ 取共轭复数 ）
= F*(-u)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,旋转特性
旋转特性
– 旋转特性描述：如果 f(x,y)旋转了一个角度?,
那么 f(x,y)旋转后的图象的傅立叶变换也旋转了相同的角度? 。
设,a(x,y) = x cos(?) - y sin(?)
b(x,y) = x sin(?) + y cos(?)
F{f(a(x,y),b(x,y))}? F(a(u,v),b(u,v))
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,旋转特性
旋转特性
– 结论：
对图像的旋转变换和傅立叶变换的顺序是可交换的
F{R{f(x,y)}}? R{F{f(x,y)}}
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,线性与相似性
线性与相似性
– 线性的描述：傅立叶变换是线性系统、函数和的傅立叶变换是可分离的设：
f(x,y) 的傅立叶变换为 F{f(x,y)}
g(x,y)的傅立叶变换为 F{g(x,y)}
有,F{f(x,y)+g(x,y)} = F{f(x,y)}+F{g(x,y)}
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,线性与相似性
线性的证明用一维函数为例进行证明：
F{f(x)+g(x)} = F(u)
=? (f(x)+g(x))exp[-j2?ux]dx
=? (f(x)exp[-j2?ux] + g(x)exp[-j2?ux])
dx
=?f(x)exp[-j2?ux]dx +?g(x)exp[-
j2?ux]dx
= F(u) + G(u)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,线性与相似性
线性与相似性
– 相似性的描述：
a f(x,y)? a F(u,v)
且有：
f(ax,by)? 1/|ab|F(u/a,v/b)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,线性与相似性
相似性的证明用一维函数为例进行证明,f(ax)? 1/|a|F(u/a)
F{f(ax)} = F(u) =?f(ax)exp[-j2?ux]dx
将指数和积分同时乘以 1 = a/a
并设,v = ax,dv = adx
F{f(ax)} =? f(ax)exp[-j2?ux a/a] a/a dx
=1/a? f(ax)exp[-j2?u xa/a]
adx
=1/a? f(v)exp[-j2?v (u /a)]
dv
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,均值性
均值性
– 均值性的描述：
离散函数的均值等于该函数傅立叶变换在 (0,0)点的值
M-1N-1
f(x,y) = 1/MNf(x,y)e0
x=0 y=0
f(x,y) = F(0,0)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,拉普拉斯
拉普拉斯
– 拉普拉斯特性的描述：
给出二维 拉普拉斯函数 的傅立叶变换表达式：
拉普拉斯函数,?2 f(x,y) =?2f /?x2 +?2f /
y2
其傅立叶变换为：
F{?2 f(x,y)} = -4?2(u2 +v2)F(u,v)
这个定理将在图象的边界提取中用到第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,卷积与相关
卷积与相关,空域和频域之间的基本联系
– 卷积定理的描述：
空域中的卷积等价于频域中的相乘
f(x,y)*g(x,y)? F(u,v)G(u,v)
F{f(x,y)*g(x,y)} = F(u,v)G(u,v)
同时有：
f(x,y) g(x,y)? F(u,v)*G(u,v)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,卷积与相关
卷积定理成立的证明用一维函数为例进行证明：
F{f(x)*g(x)} =? f(x)*g(x) exp[-
j2?ux]dx
=? [? f(t)g(x-t)dt] exp[-j2?ux]dx
对于上面这个式子,我们可以看出是一个两个变量 t,x的二维积分 。 交换积分的顺序有：
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,卷积与相关
=? [? f(t)g(x - t) exp[-2j?ux]dx]dt
=? f(t) [? g(x - t) exp[-2j?ux]dx]dt
将 t 视为位移量,由平移定理
G{g(x - t)} =?g(x - t)exp[-2j?ux]dx
= exp[-j2?tu]G(u)
有：
=? f(t) exp[-2j?tu]G(u) dt
= G(u)?f(t) exp[-2j?tu] dt = F(u)G(u)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,卷积与相关
卷积与相关,空域和频域之间的基本联系
– 相关定理的描述：
空域中 f(x,y)与 g(x,y)的相关等价于频域中 F(u,v)的共轭与 G(u,v) 相乘
f(x,y)? g(x,y)? F*(u,v)G(u,v)
同时有：
f*(x,y) g(x,y)?
F(u,v)?G(u,v)
第二章数字图象处理基础第三节频域变换第三节 频域变换,快速傅立叶变换
2.3.3 快速傅立叶变换
– FFT算法思想
– 递推公式推导
– 逆向 FFT算法
– 算法实现第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法思想
FFT算法基本思想
FFT算法基于一个叫做 递推加倍 的方法 。 通过推导将
DFT转换成两个递推公式
N-1
F(u)=1/N ∑ f(x) exp(-j2?ux/N)
x=0
F(u) = 1/2(Feven(u)+Fodd(u)W2Mu)
F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu)
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法思想
FFT算法基本思想
F(u) = 1/2(Feven(u)+Fodd(u)W2Mu)
F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu)
其中,N = 2M
Feven(u),Fodd(u) 是 1/2N个点的傅立叶值第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法思想
FFT算法基本思想通过一个实例来体会一下 FFT算法：
设：有函数 f(x)，其 N = 23 = 8
有：
{f(0),f(1),f(2),f(3),f(4),f(5),
f(6),f(7)}
计算：
{F(0),F(1),F(2),F(3),F(4),F(5),
F(6),F(7)}
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法思想
FFT算法基本思想首先分成奇偶两组：
有,{ f(0),f(2),f(4),f(6) }
{ f(1),f(3),f(5),f(7) }
为了利用递推特性，再分成两组：
有,{ f(0),f(4) },{ f(2),f(6) }
{ f(1),f(5) },{ f(3),f(7) }
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法思想
{ f(0),f(4) } { f(2),f(6) } { f(1),
f(5) } { f(3),f(7) }
{F2(0),F2(4)} {F2(2),F2(6)} {F2(1),F2(5)}
{F2(3),F2(7)}
{F4(0),F4(4),F4(2),F4(6)} {F4(1),F4(5),
F4(3),F4(7)}
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法思想分析这些表达式得到如下一些有趣的特性：
（ 1）一个 N个点的变换，能够通过将原始 表达式分成两个部分来计算
（ 2）通过计算两个（ N/2）个点的变换。得到
Feven(u)和 Fodd(u)
（ 3）奇部与偶部之和得到 F(u)的前 (N/2)个值。
（ 4）奇部与偶部之差得到 F(u)的后 (N/2)个值。
且不需要额外的变换计算 。
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法思想归纳快速傅立叶变换的思想：
1） 通过计算两个单点的 DFT,来计算两个点的 DFT，
2） 通过计算两个双点的 DFT,来计算四个点的
DFT,…,以此类推
3） 对于任何 N=2m的 DFT的计算,通过计算两个 N/2
点的 DFT,来计算 N个点的 DFT
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导
递推公式推导
FFT算法基于一个叫做 递推加倍 的方法 。 为方便起见我们用下式表达离散傅立叶变换公式
N-1
F(u)=1/N ∑ f(x) exp(-j2?ux/N)
x=0
N-1
F(u)=1/N ∑ f(x)(WN)ux
x=0
这里 WN = exp(-j2?/N) 是一个常数第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导
递推公式推导假设 N为,N = 2n
其中 n是一个正整数,因此 N可表示为：
N = 2M
这里 M仍然是一个正整数 。 将 N = 2M代入上式,得到,
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导
递推公式推导
2M-1
F(u)=1/(2M)∑f(x)(W 2M)ux
x=0
M-1 M-1
=1/2 [1/M∑f( 2x)W2Mu(2x)+1/M∑f( 2x+1)W2Mu(2x+1)]
x=0 x=0
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导
递推公式推导由于,WN = exp(-j2?/N)
W2M2ux = exp[-j2?2ux/2M]
= exp[-j2?ux/M] = WMux
所以,W2M2xu = WMxu
代入上式有：
F(u)=
M-1 M-1
=1/2 [1/M ∑ f(2x)W2Mu(2x) + 1/M∑f( 2x+1)W2Mu(2x+1)]
x=0 x=0
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导
M-1 M-1
1/2[1/M∑f( 2x)WMux + 1/M∑f( 2x+1)WMux W2Mu]
x=0 x=0
定义两个符号：
M-1
Feven(u) = 1/M∑f( 2x)WMux 偶数部分
x=0 u = 0,1,2,… M-1
M-1
Fodd (u) = 1/M∑f( 2x+1)WMux 奇数部分
x=0 u = 0,1,2,… M-1
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导得出 FFT 的第一个递推公式：
F(u)=1/2 ( Feven(u)+Fodd(u)W2Mu )
该公式说明 F(u)可以通过奇部和偶部之和来计算第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导另有,WMu+M = exp[-2j?(u+M)/M]
= exp[-2j?u/M] exp[-2j?]
= WMuej?(-2) = WMu(-1)(-2) = WMu
且,W2Mu+M = exp[-2j?(u+M)/2M]
= exp[-2j?u/2M] ej?(-1)
= W2Mu (-1)(-1) = -W2Mu
最后有,WMu+M = WMu ； W2Mu+M = -W2Mu
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导因为,WMu+M = WMu ； W2Mu+M = -W2Mu
得出 u+M 的 DFT为：
M-1
F(u+M) = 1/2 [1/M∑f(2x) WM(u+M)x +
x=0
M-1
1/M∑f(2x +1)WM(u+M)x W2Mu+M]
x=0
= 1/2 ( Feven(u)- Fodd(u)W2Mu )
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导得出 FFT的第二个递推公式：
F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu)
该公式说明 F(u+M)可以通过 F(u)偶部和奇部之差来计算第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导得出 FFT的两个递推公式：
F(u) = 1/2(Feven(u)+Fodd(u)W2Mu)
F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu)
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,逆向 FFT算法
逆向 FFT算法
– 算法思想描述：用正向变换计算逆向变换
N-1
F(u) = 1/N? f(x)exp[-j2?ux/N]
x=0
u = 0,1,2,...N-1
N-1
f(x) =? F(u)exp[j2?ux/N]
u=0
x = 0,1,2,...N-1
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,逆向 FFT算法
逆向 FFT算法在离散逆向变换表达式两边同取共轭，并除 N
N-1
1/Nf*(x) = 1/N? F*(u) exp[-j2?ux/N]
u=0
u = 0,1,2,...N-1
用正向变换算法计算，得到 1/Nf*(x),
取共轭并乘上 N，即得到 f(x)
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法实现
FFT算法实现 ——几个关键点
1）地址的排序,——按位倒序规则例如,N = 23 = 8
原地址 原顺序 新地址新顺序
000 f(0) 000 f(0)
001 f(1) 100 f(4)
010 f(2) 010 f(2)
011 f(3) 110 f(6)
100 f(4) 001 f(1)
101 f(5) 101 f(5)
110 f(6) 011 f(3)
111 f(7) 111 f(7)
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法实现
FFT算法实现 ——几个关键点
2）计算顺序及地址增量,2n n = 0,1,2…
地址 +1 地址 +2 地址 +4
f(0) F2(0) F4(0)
f(4) F2(4) F4(4)
f(2) F2(2) F4(2)
f(6) F2(6) F4(6)
f(1) F4(1) F4(1)
f(5) F2(5) F4(5)
f(3) F2(3 ) F4(3)
f(7) F2(7) F4(7)
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法实现
FFT算法实现 ——几个关键点
3）复系数的计算,——尤拉公式
W2M = exp[-j2?/2M]
= exp[-j?/M]
= cos(?/M) + jsin(?/M)
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法实现
SUBROUTINE FFT(F,LN)
COMPLEX F(1024),U,W,T,CMPLX
PI = 3.1415926
N = 2**LN /*要计算 FFT的函数点数 */
NV2 = N/2
NM1 = N-1
J = 1
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法实现
DO 3 I = 1,NM1
IF (I,GE,J) GOTO 1
T = F(J)
F(J) = F(I)
T = F(I)
1 K = NV2
2 IF (K,GE,J) GOTO 3
K = K/2
GOTO 2
3 J = J + K /*交换输入函数 F(I)的顺序 */
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法实现
DO 5 L = 1,LN
LE = 2**L
LE1 = LE /2 /*地址增量计算
*/
U = (1.0,0.0) /*系数赋初值 */
W = CMPLX(COS(PI/LE1),-SIN(PI/LE1))
DO 5 J = 1,LE1
DO 4 I = J,N,LE
IP = I +LE1 /*计算地址 */
T= F(IP) * U /*奇部乘系数 */
F(IP) = F(I) - T /*后半部分计算第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法实现
4 F(I) = F(I) + T /*后半部分计算 */
5 U = U*W /*新递推系数计算 */
DO 6 I = 1,N
6 F(I) = F(I) / FLOAT(N)
RETURN
END
第二章数字图象处理基础第三节频域变换第二次作业 FFT算法的实现
1,将宽为 2n的正方形图象，用 FFT算法 从空域变换到频域；
2,将频域图象以中心为原点的四个象限，做水平和垂直镜像，使图象能量中心，对应到几何中心，
并用频域图象的模来进行显示。
3,将频域图象，通过 FFT逆变换到空域，并显示。
第二章数字图象处理基础第三节频域变换请提问
http://www.icst.pku.edu.cn/digitalimage
2.3.1 傅立叶变换导言
– 理论基础、连续与离散的傅立叶变换
2.3.2 二维傅立叶变换特性
– 可分离性、周期与共轭对称、平移性、
– 旋转特性、线性与相似性,均值性、
– 拉普拉斯、卷积与相关
2.3.3 快速傅立叶变换
– FFT算法,逆向 FFT算法、算法实现第二章数字图象处理基础第三节频域变换第三节 频域变换
2.3.1 傅立叶变换导言
– 理论基础
– 连续与离散的傅立叶变换第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,理论基础
理论基础
– 线性系统
– 卷积与相关第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,理论基础
线性系统
– 系统 的定义：
接受一个输入，并产生相应输出的任何实体。
系统的输入是一个或两个变量的函数，输出是相同变量的另一个函数。
系统x(t)输入 y(t)输出第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,理论基础
线性系统
– 线性系统 的定义：
对于某特定系统，有：
x1(t) y1(t)
x2(t) y2(t)
该系统是线性的当且仅当：
x1(t) + x2(t) y1(t) +
y2(t)
从而有,a*x1(t) a*y1(t)
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,理论基础
线性系统
– 线性系统 移不变性 的定义：
对于某线性系统,有：
x(t) y(t)
当输入信号沿时间轴平移 T,有：
x(t - T) y(t - T)
则称该线性系统具有移不变性第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,理论基础
卷积
– 卷积的定义
– 离散一维卷积
– 二维卷积的定义
– 离散二维卷积
– 相关的定义第二章数字图象处理基础第三节频域变换第三节 频域变换,理论基础
– 卷积 的定义
对于一个线性系统的输入 f(t)和输出 h(t)，如果有一个一般表达式，来说明他们的关系，对线性系统的分析，将大有帮助
卷积积分就是这样的一般表达式
h(t) =? g(t -?)f(?)d? 记为,h = g *
f
-?
g(t)称为 冲激响应函数第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,理论基础
– 离散一维卷积
h(i) = f(i)*g(i) =? f(j)g(i-j)
j
– 二维卷积的定义
h(x,y) = f*g = f(u,v)g(x – u,y –
v)dudv
-?
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,理论基础
– 离散二维卷积
h(x,y) = f*g = f(m,n)g(x – m,
y – n)
m n
– 相关 的定义
h(t) =? g(t +?)f(?)d? 记为,y = g? x
-?
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
连续与离散的傅立叶变换
– 一维连续傅立叶变换
– 二维连续傅立叶变换
– 离散傅立叶变换
– 离散傅立叶变换的计算与显示第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
一维连续傅立叶变换：定义设 f(x)为实变量 x的连续函数,
f(x)的 傅立叶变换 表示为 F{f(x)},
定义为：
F{f(x)} = F(u) =? f(x)exp(-
j2?ux)dx
-?
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
一维连续傅立叶逆变换：定义如果给定 F(u),f(x)可以由 傅立叶逆变换 得到：
F{F(u)} = f(x) =?
F(u)exp(j2?ux)du
-?
其中 j2 = -1
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
一维连续傅立叶变换：几个概念假设函数 f(x)为实函数 。 但一个实函数的傅立叶变换可能为复函数：
F(u) = R(u) + jI(u)
（ 1） f(x)的傅立叶 模 记为,|F(u)|
|F(u)| = [R2(u) + I2(u)]1/2
（ 2） f(x)的傅立叶 模平方 记为,P(u)
P(u) = |F(u)|2 = R2(u) + I2(u)
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
一维连续傅立叶变换：几个概念
（ 3） f(x)的傅立叶 相位 记为,?(u)
(u) = tan-1 (I(u) / R(u))
（ 4） 傅立叶变换中的变量 u通常称为 频率变量这个名称源于尤拉公式中的指数项
exp[-j2?ux] = cos2?ux - jsin2?ux
如果把傅立叶变换的积分解释为离散项的和,
则易推出 F(u)是一组 sin和 cos函数项的无限和,其中 u
的每个值决定了其相应 cos,sin函数对的频率 。
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
二维连续傅立叶变换如果 f(x,y)连续可积,并且 F(u,v)可积,
则存在以下傅立叶变换对,其中 u,v为频率变量：
F{f(x,y)}=F(u,v)=f(x,y)exp[-j2?(ux+vy)]dxdy
-?
F{F(u,v)}=f(x,y)=F(u,v)exp[j2?(ux+vy)]dudv
-?
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
二维连续傅立叶变换二维傅立叶模,相位和模平方分别为：
模,|F(u,v)| = [R2(u,v) +
I2(u,v)]1/2
相位,? (u,v) = tan-1 (I(u,v) /
R(u,v))
模平方,P(u,v) = |F(u,v)|2 = R2(u,v) +
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换假设连续函数 f(x),通过取 N个?x单位的采样点,被离散化为一个序列：
{f(x0),f(x0+?x),
f(x0+2?x),…,f(x0+[N–1]? x)}
无论将 x作为离散的或连续的变量,在子序列中来研究都将是方便的,仅仅依赖于讨论的上下文 。 为作到此要求定义,
f(x) = f(x0+ x?x)
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换其中假设 x现在的离散值是,0,1,2,…,N-1。
{f(x0),f(x0+?x),f(x0+2?x),...,
f(x0+[N–1]?x)}
表示相对与连续函数的任意 N个统一的空间采样第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换函数 f(x0+x?x)的离散傅立叶变换对有：
N-1
F(u) = 1/N? f(x)exp[-j2?ux/N]
x=0
u = 0,1,2,...N-1
N-1
逆变换,f(x) =? F(u)exp[j2?ux/N]
u=0
x = 0,1,2,...N-1
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换,二维
M-1 N-1
F(u,v) =1/MNf(x,y)exp[-j2?(ux/M+vy/N)]
x=0 y=0
u = 0,1,2,… M-1; v = 0,1,
2,...N-1
M-1 N-1
f(x,y) = F(u,v)exp[j2?(ux/M+vy/N)]
u=0 v=0
x = 0,1,2,...N-1; y = 0,1,
2,...N-1
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换的计算与显示
– 离散傅立叶变换的计算举例
– 离散傅立叶变换的显示第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换的计算举例
x
f(x0)=f(x0+?x)
0 1 2 3
1
2
3
4
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
F(0) = 1/4Σ f(x)exp[0]
= 1/4[f(0) + f1(1) + f(2) + f(3)]
= 1/4(2 + 3 + 4 + 4)= 3.25
F(1) = 1/4Σ f(x)exp[-j2π x/4)]
= 1/4(2e0 + 3e –j2π 1/4 + 4e –j2π 2/4 + 4e –
j2π3/4)
= 1/4(-2 + j)
F(2) = -1/4(1 + j0)
F(3) = -1/4(2 + j)
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换的计算举例
– 因为，函数 f(x,y)的傅立叶变换是 f(x,y)积分的函数
– 因此，计算每一个傅立叶变换值，原函数
f(x,y)的每一个点都需要参与第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换的显示通过对 傅立叶变换模,来显示傅立叶变换图象。由于模的值域大于显示的值域，因此要进行动态值域的压缩
D(u,v) = c log(1 + |F(u,v)|)
其中,c = 255 / k;
k = max(log(1 + |F(u,v)|))
值域 [0,k]的上限 （ 最大值 ）
第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换的显示第二章数字图象处理基础第三节频域变换
2.3.1 傅立叶变换导言,傅立叶变换
离散傅立叶变换的显示 ——对称平移后第二章数字图象处理基础第三节频域变换第三节 频域变换,二维傅立叶变换特性
2.3.2 二维傅立叶变换特性
可分离性
周期与共轭对称
平移性
旋转特性
线性与相似性
均值性
拉普拉斯
卷积与相关第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,可分离性
可分离性
– 二维离散傅立叶变换 DFT可分离性的基本思想是：
二维 DFT可分离为两次一维 DFT
– 应用：
二维快速傅立叶算法 FFT,是通过计算两次一维 FFT实现的第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,可分离性
可分离性的定义
M-1 N-1
F(u,v)=1/MN? [?f(x,y)e(-j2?vy/N)] e(-
j2?ux/M)
x=0 y=0
u = 0,1,2,… M-1; v = 0,1,2,...N-1
M-1 N-1
f(x,y)=? [?F(u,v)e(j2?vy/N)] e(j2?ux/M)
u=0 v=0
x = 0,1,2,...N-1; y = 0,1,2,...N-1
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,可分离性
可分离性成立的推导
– 先对行 （ y变量 ） 做变换：
N-1
F(x,v)=1/N?f(x,y)exp(-j2?vy/N)]
y=0
– 然后对列 （ x变量 ） 进行变换：
M-1
F(u,v)=1/M?F(x,v)exp(-j2?ux/M)]
x=0
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,可分离性
– 先对行做变换：
然后对列进行变换,
f(x,y)
（ 0,0）
（ N-1,M-1）x
y
F(x,v)
（ 0,0）
（ N-1,M-1）x
v
F(x,v)
（ 0,0）
（ N-1,M-1）x
v
F(u,v)
（ 0,0）
（ N-1,M-1）u
v
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,平移性
平移性定理
– 平移性的描述函数自变量的位移的傅立叶变换产生一个复系数
F{f(x-a,y-b)} = exp[-j2?(au+bv)]
F(u,v)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,平移性
平移性成立的证明用一维函数为例进行证明：
设位移为 a,f(x-a)的傅立叶变换为：
F{f(x-a)} = F(u) =? f(x-a)exp(-
j2?ux)dx
-?
将积分乘以 1 = exp(-j2?au) exp(j2?au)
且设,v = x-a,dv = dx
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,平移性
平移性成立的证明
F{f(x-a)} = F(u)
=? f(x-a)exp(-j2?ux) exp(-j2?au)exp(j2?au) dx
-?
=exp(-j2?au)? f(x-a)exp(-j2?ux)exp(j2?ua)dx
-?
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,平移性
= exp(-j2?au)? f(x-a)exp[-j2?u(x-a)]dx
-?
= exp(-j2?au)? f(v)exp[-j2?uv]dv
-?
= exp(-j2?au)F(u)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,周期与共轭对称
周期与共轭对称
– 周期性的描述,离散傅立叶变换 DFT和它的逆变换是以 N为周期的对于一维傅立叶变换有：
F(u) = F(u + N)
对于二维傅立叶变换有：
F(u,v) = F(u + M,v+N)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,周期与共轭对称
周期与共轭对称
– 共轭对称性的描述,傅立叶变换结果是以原点为中心的共轭对称函数对于一维傅立叶变换有：
F(u) = F*(-u)
对于二维傅立叶变换有：
F(u,v) = F*(-u,-v)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,周期与共轭对称
共轭对称性证明以一维傅立叶变换为例证明,
F(u) =∫ f(x)exp[-j2?ux]dx
=∫ f(x)exp[j2?(-u)x]dx
=∫ f(x)exp[-j2?(-u)x]*dx（ 取共轭复数 ）
= F*(-u)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,旋转特性
旋转特性
– 旋转特性描述：如果 f(x,y)旋转了一个角度?,
那么 f(x,y)旋转后的图象的傅立叶变换也旋转了相同的角度? 。
设,a(x,y) = x cos(?) - y sin(?)
b(x,y) = x sin(?) + y cos(?)
F{f(a(x,y),b(x,y))}? F(a(u,v),b(u,v))
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,旋转特性
旋转特性
– 结论：
对图像的旋转变换和傅立叶变换的顺序是可交换的
F{R{f(x,y)}}? R{F{f(x,y)}}
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,线性与相似性
线性与相似性
– 线性的描述：傅立叶变换是线性系统、函数和的傅立叶变换是可分离的设：
f(x,y) 的傅立叶变换为 F{f(x,y)}
g(x,y)的傅立叶变换为 F{g(x,y)}
有,F{f(x,y)+g(x,y)} = F{f(x,y)}+F{g(x,y)}
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,线性与相似性
线性的证明用一维函数为例进行证明：
F{f(x)+g(x)} = F(u)
=? (f(x)+g(x))exp[-j2?ux]dx
=? (f(x)exp[-j2?ux] + g(x)exp[-j2?ux])
dx
=?f(x)exp[-j2?ux]dx +?g(x)exp[-
j2?ux]dx
= F(u) + G(u)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,线性与相似性
线性与相似性
– 相似性的描述：
a f(x,y)? a F(u,v)
且有：
f(ax,by)? 1/|ab|F(u/a,v/b)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,线性与相似性
相似性的证明用一维函数为例进行证明,f(ax)? 1/|a|F(u/a)
F{f(ax)} = F(u) =?f(ax)exp[-j2?ux]dx
将指数和积分同时乘以 1 = a/a
并设,v = ax,dv = adx
F{f(ax)} =? f(ax)exp[-j2?ux a/a] a/a dx
=1/a? f(ax)exp[-j2?u xa/a]
adx
=1/a? f(v)exp[-j2?v (u /a)]
dv
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,均值性
均值性
– 均值性的描述：
离散函数的均值等于该函数傅立叶变换在 (0,0)点的值
M-1N-1
f(x,y) = 1/MNf(x,y)e0
x=0 y=0
f(x,y) = F(0,0)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,拉普拉斯
拉普拉斯
– 拉普拉斯特性的描述：
给出二维 拉普拉斯函数 的傅立叶变换表达式：
拉普拉斯函数,?2 f(x,y) =?2f /?x2 +?2f /
y2
其傅立叶变换为：
F{?2 f(x,y)} = -4?2(u2 +v2)F(u,v)
这个定理将在图象的边界提取中用到第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,卷积与相关
卷积与相关,空域和频域之间的基本联系
– 卷积定理的描述：
空域中的卷积等价于频域中的相乘
f(x,y)*g(x,y)? F(u,v)G(u,v)
F{f(x,y)*g(x,y)} = F(u,v)G(u,v)
同时有：
f(x,y) g(x,y)? F(u,v)*G(u,v)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,卷积与相关
卷积定理成立的证明用一维函数为例进行证明：
F{f(x)*g(x)} =? f(x)*g(x) exp[-
j2?ux]dx
=? [? f(t)g(x-t)dt] exp[-j2?ux]dx
对于上面这个式子,我们可以看出是一个两个变量 t,x的二维积分 。 交换积分的顺序有：
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,卷积与相关
=? [? f(t)g(x - t) exp[-2j?ux]dx]dt
=? f(t) [? g(x - t) exp[-2j?ux]dx]dt
将 t 视为位移量,由平移定理
G{g(x - t)} =?g(x - t)exp[-2j?ux]dx
= exp[-j2?tu]G(u)
有：
=? f(t) exp[-2j?tu]G(u) dt
= G(u)?f(t) exp[-2j?tu] dt = F(u)G(u)
第二章数字图象处理基础第三节频域变换
2.3.2 二维傅立叶变换特性,卷积与相关
卷积与相关,空域和频域之间的基本联系
– 相关定理的描述：
空域中 f(x,y)与 g(x,y)的相关等价于频域中 F(u,v)的共轭与 G(u,v) 相乘
f(x,y)? g(x,y)? F*(u,v)G(u,v)
同时有：
f*(x,y) g(x,y)?
F(u,v)?G(u,v)
第二章数字图象处理基础第三节频域变换第三节 频域变换,快速傅立叶变换
2.3.3 快速傅立叶变换
– FFT算法思想
– 递推公式推导
– 逆向 FFT算法
– 算法实现第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法思想
FFT算法基本思想
FFT算法基于一个叫做 递推加倍 的方法 。 通过推导将
DFT转换成两个递推公式
N-1
F(u)=1/N ∑ f(x) exp(-j2?ux/N)
x=0
F(u) = 1/2(Feven(u)+Fodd(u)W2Mu)
F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu)
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法思想
FFT算法基本思想
F(u) = 1/2(Feven(u)+Fodd(u)W2Mu)
F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu)
其中,N = 2M
Feven(u),Fodd(u) 是 1/2N个点的傅立叶值第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法思想
FFT算法基本思想通过一个实例来体会一下 FFT算法：
设：有函数 f(x)，其 N = 23 = 8
有：
{f(0),f(1),f(2),f(3),f(4),f(5),
f(6),f(7)}
计算：
{F(0),F(1),F(2),F(3),F(4),F(5),
F(6),F(7)}
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法思想
FFT算法基本思想首先分成奇偶两组：
有,{ f(0),f(2),f(4),f(6) }
{ f(1),f(3),f(5),f(7) }
为了利用递推特性，再分成两组：
有,{ f(0),f(4) },{ f(2),f(6) }
{ f(1),f(5) },{ f(3),f(7) }
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法思想
{ f(0),f(4) } { f(2),f(6) } { f(1),
f(5) } { f(3),f(7) }
{F2(0),F2(4)} {F2(2),F2(6)} {F2(1),F2(5)}
{F2(3),F2(7)}
{F4(0),F4(4),F4(2),F4(6)} {F4(1),F4(5),
F4(3),F4(7)}
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法思想分析这些表达式得到如下一些有趣的特性：
（ 1）一个 N个点的变换，能够通过将原始 表达式分成两个部分来计算
（ 2）通过计算两个（ N/2）个点的变换。得到
Feven(u)和 Fodd(u)
（ 3）奇部与偶部之和得到 F(u)的前 (N/2)个值。
（ 4）奇部与偶部之差得到 F(u)的后 (N/2)个值。
且不需要额外的变换计算 。
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法思想归纳快速傅立叶变换的思想：
1） 通过计算两个单点的 DFT,来计算两个点的 DFT，
2） 通过计算两个双点的 DFT,来计算四个点的
DFT,…,以此类推
3） 对于任何 N=2m的 DFT的计算,通过计算两个 N/2
点的 DFT,来计算 N个点的 DFT
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导
递推公式推导
FFT算法基于一个叫做 递推加倍 的方法 。 为方便起见我们用下式表达离散傅立叶变换公式
N-1
F(u)=1/N ∑ f(x) exp(-j2?ux/N)
x=0
N-1
F(u)=1/N ∑ f(x)(WN)ux
x=0
这里 WN = exp(-j2?/N) 是一个常数第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导
递推公式推导假设 N为,N = 2n
其中 n是一个正整数,因此 N可表示为：
N = 2M
这里 M仍然是一个正整数 。 将 N = 2M代入上式,得到,
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导
递推公式推导
2M-1
F(u)=1/(2M)∑f(x)(W 2M)ux
x=0
M-1 M-1
=1/2 [1/M∑f( 2x)W2Mu(2x)+1/M∑f( 2x+1)W2Mu(2x+1)]
x=0 x=0
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导
递推公式推导由于,WN = exp(-j2?/N)
W2M2ux = exp[-j2?2ux/2M]
= exp[-j2?ux/M] = WMux
所以,W2M2xu = WMxu
代入上式有：
F(u)=
M-1 M-1
=1/2 [1/M ∑ f(2x)W2Mu(2x) + 1/M∑f( 2x+1)W2Mu(2x+1)]
x=0 x=0
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导
M-1 M-1
1/2[1/M∑f( 2x)WMux + 1/M∑f( 2x+1)WMux W2Mu]
x=0 x=0
定义两个符号：
M-1
Feven(u) = 1/M∑f( 2x)WMux 偶数部分
x=0 u = 0,1,2,… M-1
M-1
Fodd (u) = 1/M∑f( 2x+1)WMux 奇数部分
x=0 u = 0,1,2,… M-1
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导得出 FFT 的第一个递推公式：
F(u)=1/2 ( Feven(u)+Fodd(u)W2Mu )
该公式说明 F(u)可以通过奇部和偶部之和来计算第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导另有,WMu+M = exp[-2j?(u+M)/M]
= exp[-2j?u/M] exp[-2j?]
= WMuej?(-2) = WMu(-1)(-2) = WMu
且,W2Mu+M = exp[-2j?(u+M)/2M]
= exp[-2j?u/2M] ej?(-1)
= W2Mu (-1)(-1) = -W2Mu
最后有,WMu+M = WMu ； W2Mu+M = -W2Mu
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导因为,WMu+M = WMu ； W2Mu+M = -W2Mu
得出 u+M 的 DFT为：
M-1
F(u+M) = 1/2 [1/M∑f(2x) WM(u+M)x +
x=0
M-1
1/M∑f(2x +1)WM(u+M)x W2Mu+M]
x=0
= 1/2 ( Feven(u)- Fodd(u)W2Mu )
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导得出 FFT的第二个递推公式：
F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu)
该公式说明 F(u+M)可以通过 F(u)偶部和奇部之差来计算第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,递推公式推导得出 FFT的两个递推公式：
F(u) = 1/2(Feven(u)+Fodd(u)W2Mu)
F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu)
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,逆向 FFT算法
逆向 FFT算法
– 算法思想描述：用正向变换计算逆向变换
N-1
F(u) = 1/N? f(x)exp[-j2?ux/N]
x=0
u = 0,1,2,...N-1
N-1
f(x) =? F(u)exp[j2?ux/N]
u=0
x = 0,1,2,...N-1
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,逆向 FFT算法
逆向 FFT算法在离散逆向变换表达式两边同取共轭，并除 N
N-1
1/Nf*(x) = 1/N? F*(u) exp[-j2?ux/N]
u=0
u = 0,1,2,...N-1
用正向变换算法计算，得到 1/Nf*(x),
取共轭并乘上 N，即得到 f(x)
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法实现
FFT算法实现 ——几个关键点
1）地址的排序,——按位倒序规则例如,N = 23 = 8
原地址 原顺序 新地址新顺序
000 f(0) 000 f(0)
001 f(1) 100 f(4)
010 f(2) 010 f(2)
011 f(3) 110 f(6)
100 f(4) 001 f(1)
101 f(5) 101 f(5)
110 f(6) 011 f(3)
111 f(7) 111 f(7)
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法实现
FFT算法实现 ——几个关键点
2）计算顺序及地址增量,2n n = 0,1,2…
地址 +1 地址 +2 地址 +4
f(0) F2(0) F4(0)
f(4) F2(4) F4(4)
f(2) F2(2) F4(2)
f(6) F2(6) F4(6)
f(1) F4(1) F4(1)
f(5) F2(5) F4(5)
f(3) F2(3 ) F4(3)
f(7) F2(7) F4(7)
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法实现
FFT算法实现 ——几个关键点
3）复系数的计算,——尤拉公式
W2M = exp[-j2?/2M]
= exp[-j?/M]
= cos(?/M) + jsin(?/M)
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法实现
SUBROUTINE FFT(F,LN)
COMPLEX F(1024),U,W,T,CMPLX
PI = 3.1415926
N = 2**LN /*要计算 FFT的函数点数 */
NV2 = N/2
NM1 = N-1
J = 1
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法实现
DO 3 I = 1,NM1
IF (I,GE,J) GOTO 1
T = F(J)
F(J) = F(I)
T = F(I)
1 K = NV2
2 IF (K,GE,J) GOTO 3
K = K/2
GOTO 2
3 J = J + K /*交换输入函数 F(I)的顺序 */
第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法实现
DO 5 L = 1,LN
LE = 2**L
LE1 = LE /2 /*地址增量计算
*/
U = (1.0,0.0) /*系数赋初值 */
W = CMPLX(COS(PI/LE1),-SIN(PI/LE1))
DO 5 J = 1,LE1
DO 4 I = J,N,LE
IP = I +LE1 /*计算地址 */
T= F(IP) * U /*奇部乘系数 */
F(IP) = F(I) - T /*后半部分计算第二章数字图象处理基础第三节频域变换
2.3.3 快速傅立叶变换,FFT算法实现
4 F(I) = F(I) + T /*后半部分计算 */
5 U = U*W /*新递推系数计算 */
DO 6 I = 1,N
6 F(I) = F(I) / FLOAT(N)
RETURN
END
第二章数字图象处理基础第三节频域变换第二次作业 FFT算法的实现
1,将宽为 2n的正方形图象，用 FFT算法 从空域变换到频域；
2,将频域图象以中心为原点的四个象限，做水平和垂直镜像，使图象能量中心，对应到几何中心，
并用频域图象的模来进行显示。
3,将频域图象，通过 FFT逆变换到空域，并显示。
第二章数字图象处理基础第三节频域变换请提问
http://www.icst.pku.edu.cn/digitalimage
