(40分钟/ 8000) 80002 (N
/ 2) log 2 N2
N
0.18天
4.33小时
[假设运算效率主要由乘法效率决定]
Cooley（库利）和Tukey（图基）在1965年提出FFT算法
例 3609×5455，PIV 2.0G, 256M, Matlab 2006,语句
t=cputime;f=fft2(double(a(:,:,1)));tt=cputime; 内存不够；463×687，0.4844s
➢一维连续傅立叶变换
引理1：若一维实空间上的函数f(x)绝对可积，则函数
F (u) f (x) exp( j2xu)dx
存在，若F(u)绝对可积，则
f (x) F (u) exp( j2ux)du
其中 j 1 （下同）
定义：通常称F(u)为f(x)的Fourier变换，f(x)为F(u) 的Fourier反变换。记
MN x0 y0
MN
u 0,1, M 1; v 0,1, N 1
f (x, y) M 1N 1 F (u, v) exp(2 j ( ux vy))
u0 v0
MN
傅 立 叶
x 0,1, M 1; y 0,1, N 1
变
换
或者：
的
数
F (u, v) 1 M 1N 1 f (x, y) exp(2 j ( ux vy))
R(u, v) F (u, v)称为f (x, y)的振幅谱（频谱, Fourier谱(变换）)
(u, v)称为f (x, y)的相位谱，E(u, v) | F (u, v) |2 称为
f (x, y)的能量谱。
通常，我们将Fourier变换前的变量域，即(x, y)的变化 范围称为空间域，而将变换后的变量域，即变量(u, v)的 变化范围称为频率域或变换域。
N 1
F (u) f (x) exp(2ux / N ), u 0,1, , N 1 （3.1） x0
f (x)
1
N 1
F (u) exp(2ux / N ), x 0,1,
, N 1
N x0
（3.2）
令
j 2
W e N
则以上两式可写为：
10/106
N 1
F (u) f (x)W xu , u 0,1, , N 1 x0
MN x0 y0
MN
学 表 达
u 0,1, M 1; v 0,1, N 1
形
f (x, y) 1 M 1N 1 F (u, v) exp(2 j ( ux vy))
MN u0 v0
MN
式 问 题
x 0,1, M 1; y 0,1, N 1
当M N时，傅立叶变换对可以写为
F (u, v) 1 N1 N1 f (x, y) exp(2 j ux vu)
方法
6 沃什变换和哈达 玛变换
7 低通滤波 8 高通滤波
N 1
F (u)
f ( x) exp(2ux / N )
x0
N
2 4 16 64 512 1024
N2(DFT) 乘法N2 加法N(N-1)
Nlog2N(FFT) 乘法(N/2)log2N
加法Nlog2N
N2/Nlog2N
4
2
2.0
16
8
2.0
W
( N 1)( N 1)
f
(N
1)
例1 f(x)=1,x=0,1,2,…,N-1有限长常数序列的离散傅立叶变换： 1 u 0
F (u) 0 其他
12/106
3 一维快速傅立叶变换
1.概述 2.一维傅立叶变换 3.一维快速傅立叶
变换
4.二维傅立叶变换 5.余弦变换 5’.数字图像处理
(u)称为f (x)的相位谱，E(u) | F (u) |2 称为f (x)的能量谱。
通常，我们将Fourier变换前的变量域，即x的变化范围称为 空间域，而将变换后的变量域，即变量u的变化范围称为 频率域或变换域。
9/106
➢一维离散傅立叶变换
对有限长序列f(x),x=0,1,2,…,N-1,可定义一维离散傅 立叶变换对如下：
5 10 15 20 25 30 35 40 45 50
6/106
ttt=10;
tt=0.01;
N=ttt/tt;
TT=2;
t=0:tt:ttt;
y=sin(2*pi*t)+sin(4*2*pi*t)+sin(8*2*pi*t);
yy=fft(y);
subplot(4,1,1);plot(t,y);
f (x)
1
N 1
F (u)W ux , x 0,1,
, N 1
N x0
傅立叶变换对也可以简记为： f (x) F(u)
注意到（3.1)和（3.2)的结构，傅立叶变换也可以写成矩 阵形式：
11/106
f (0) W 0
W0
W0
W0
F (0)
f
f (1)
(N
1)
W 0
W 0
N x0 y0
N
u 0,1, N 1;v 0,1, N 1
f (x, y)
1
N 1 N 1
F (u, v) exp(2 j
ux vu)
N u0 v0
N
x 0,1, N 1; y 0,1, N 1
一般来讲，数字图像是空间域中的连续图像的一种 满足人为满意尺度的近似，对图像进行频谱分析， 对应地，对数字图像也可以进行频谱分析，有关的 分析数据都有相同的物理解释。
subplot(4,1,3);plot(t,real(z));
yyy=yy(1:u);
subplot(4,1,4);plot(i,abs(yyy));
7/106
2.一维Fourier变换
1.概述 2.一维傅立叶变换 3.一维快速傅立叶
变换 4.二维傅立叶变换 5.余弦变换 6 沃什变换和哈达
玛变换 7 低通滤波 8 高通滤波
T / 2
称1/T为基频。令T趋向于无穷大，可导出傅立叶变 换的概念。Cn是频率为n/T的谐波信号所占的“比 将信号重f”(t)。分解成一系列基本信号的叠加具有理论和工程意义。 “分解－综合”是解决复杂问题的常用思路。
t=0:0.1:8; y=sin(2*pi*t)+sin(4*2*pi*t)+sin(8*2*pi*t)+sin(12*2*pi*t); yy=fft(y); subplot(2,1,1);plot(t,y); subplot(2,1,2);plot(2.5*t,abs(yy));
W 11
W ( N 1)1
W 21
W ( N 1)2
W (N 1)1 F (1)
W
(
N
1)(
N
1)
F
(
N
1)
F (0) W 0
F
F (1) (N
1)
W 0
W 0
W0 W 11
W 1(N 1)
W0 W 21
W 2(N 1)
W0 W（N 1)1
f (0) f (1)
19/106
例2 图像的傅立叶谱
a=imread('fft1.jpg'); b=uint8(a(:,:,1)); subplot(1,2,1); imshow(b); f=fft2(double(a(:,:,1))); subplot(1,2,2); imshow(log(1+abs(f)),[ 0 10],'notruesize');
为了记号简略起见，若f的Fourier变换为F,则记
f (x, y) F(u, v)
15/106
将F (u, v)写成F (u, v) R(u, v) jI (u, v) | F (u, v) | e j (u,v)
其中| F (u, v) | R(u, v)2 I (u, v)2 , (u, v) arctg I (u, v)
设f(t)是定义在[-T/2,T/2]上的函数(信号),0<T<∞.
将信号f(t)分解成一系列基本信号的叠加具有 理论和工程意义。“分解－综合”是解决复 杂问题的常用思路。
泰勒展式
f
(t)
N 1 n0
f
(n) (t0 ) n!
(t
t0
)n
f
(N ) (
N!
)
(t
t0
)N
2/106
傅立叶级数
f
(t)
20/106
21/106
22/106
23/106
24/106
例3 灰度图像的傅立叶谱
25/106
256
64
4.0
4096
394
10.7
262144
4608
56.9
1048576 10240
102.4
N>8000, IBM7094(1962.9), 耗时40分钟
设t N 为N个数据的傅立叶变换所用总时间, 则 tN / N为得到每个傅立叶变换系数所用的平均时间. (40分钟/ 8000) 80002 0.609年 5334.84小时
F(u) F ( f (x)), f (x) F -1(F(u))
将F (u)写成F (u) R(u) jI (u) | F (u) | e j (u)
其中| F (u) | R(u)2 I (u)2 , (u) arctg I (u)
R(u) F (u)称为f (x)的振幅谱（频谱, Fourier谱)
f (x, y) 1 M 1N1 F (u, v) exp(2 j ( ux vy))