图像正交变换

图像正交变换2023/6/9第一页，共一百一十九页，编辑于2023年，星期二第4章图像变换(Image

Transform)4.1

傅立叶变换简介4.2

傅里叶变换理论4.3

快速傅里叶变换4.4

傅里叶变换的性质4.5

图像傅里叶变换实例4.6

其他离散变换第二页，共一百一十九页，编辑于2023年，星期二

线性系统理论通常用于描述电路和光学系统的行为，为采样、滤波等提供坚实的数学基础。一、定义系统：对信号施以的一种变换。可以是电路系统、光学系统甚至其他一切对信号影响的实体。线性移不变系统：具有线性和移不变特性的系统。二、研究线性系统的两种方法1、任何一个系统都有一个传递函数，它与调谐输入相乖得到对应的调谐输出。2、任何一个系统都有一个实值的冲激响应，它与输入信号的卷积给出对应的输出。第三页，共一百一十九页，编辑于2023年，星期二简介

1、背景

1768年出生于法国。

傅立叶的思想：1807年，向法国科学院提交报告：任何周期函数都可以用一系列正弦波来表示。第四页，共一百一十九页，编辑于2023年，星期二信号的分解第五页，共一百一十九页，编辑于2023年，星期二一、

图象变换的引入1.

方法：对图象信息进行变换，使能量保持但重新分配。2.

目的：有利于加工、处理[滤除不必要信息(如噪声)，加强/提取感兴趣的部分或特征]。二、

方法分类

可分离、正交变换:

2D-DFT

,

2D-DCT

,1．提取图象特征（如）：（1）直流分量：f(x,y)的平均值=F(0,0)；（2）目标物边缘：F（u,v）高频分量。2．图像压缩：正交变换能量集中，对集中（小）部分进行编码。3．图象增强：低通滤波，平滑噪声；高通滤波，锐化边缘。三、

用途2D-DHT,

2D-DWT

。傅立叶变换作用第六页，共一百一十九页，编辑于2023年，星期二连续周期函数的傅立叶级数及非周期信号的傅立叶变换第七页，共一百一十九页，编辑于2023年，星期二ancos(n)bnsin(n)

g()cos(n)d

g()sin(n)d

一、连续周期函数的傅立叶级数

周期为2π

周期为2π的函数g(θ)，若在一个周期内只有有限个极值点和不连续点，并且在一个周期内绝对可积，则它可以展成傅里叶三角级数：其中：

n1a0

2g()

an

bn

1

1

第八页，共一百一十九页，编辑于2023年，星期二2

2

2

ancosna0xbnsinnTxT

x02xdx

周期为T

周期为T的函数将它展开成傅立叶三角级数时展开式，只是要根据对应关系将θ换算成x，它们之间的换算关系是，

x

所以有

g(x)

2

n1

T

T其中：bn

g(x)sinn

T2

x0T第九页，共一百一十九页，编辑于2023年，星期二1md

x

md

0xd0d2d

2、举例有一缝宽和缝距相等的矩形光栅，振幅透过率为：其中，m为整数，将它展开成傅立叶三角级数。函数图形如下所示：

g(x)其它d2

g(x)

第十页，共一百一十九页，编辑于2023年，星期二2sin(2k

1)x、sin2πx、sin6πx、sin10πx、取前项：绘图如下：sin14πx

27π

25π1222π3π解：

g(x)

xbnsinn

x

2

n1

d

d

2

d

2

1n

0

g(x)cosn

d

g(x)sinn

xdx

sinn

xdx

d

d

d

d

1

n

2,4,6,...2k其中k=0,1,2,…。于是：12g(x)2

d

k0(2k

1)第十一页，共一百一十九页，编辑于2023年，星期二第十二页，共一百一十九页，编辑于2023年，星期二Cnex

3、指数形式通过欧拉公式，把正弦函数、余弦函数和指数函数联系起来，不难证明傅里叶三角级数可以写成指数级数的形式。

若g(x)的周期为T，在一个周期内只有有限个极值点和不连续点，并且在一个周期内绝对可积。则g(x)可以展开成傅立叶指数级数：其中：

nxjn2

Tg(x)xjndxCn

x0

T

0g(x)e

1T2

T第十三页，共一百一十九页，编辑于2023年，星期二T

x0g(x)dx

0T

x0

xg(x)cos(nx)dx

1x0Tx0g(x)edxxg(x)cos(nx)dx

证明如下：取n为任一正整数a

21

x0TC0

xjndxCn

g(x)e1x0T2

T

1Tan

jbn

2x)

j

sin(nx0

T

02

T2

TT

2jnx

TCn

1Tan

jbn

2x)jsin(nx0

T

02

T2

T第十四页，共一百一十九页，编辑于2023年，星期二

Ce

22C0

Cne

T

Cne2ancos

nx

bnsin

nx

jnxn2

T

ng(x)

jn

x

jn

x

Tn1

cosnxjsinnx

n1

2TT即：得证。n1Ta0

2

2

T第十五页，共一百一十九页，编辑于2023年，星期二傅立叶级数第十六页，共一百一十九页，编辑于2023年，星期二

事实上周期函数只是数学上的描述，对于一切物理过程严格来说都是非周期的。有些物理过程可以用周期函数来近似描述，象前面介绍的矩形光栅的例子，只有当光栅常数ｄ比光栅总宽度小得多的时，也就是总缝数很大时才可以用周期函数来描写这种光栅，当然这种描写仍是近似的。还有相当多的物理现象，只发生在有限的空间范围和时间间隔内，这样的现象对于空间和时间来说是非周期的。对于大量非周期函数的展开，首先可以以它有非零值的范围（空间范围或时间间隔）为周期，将它延拓成为周期函数。右图中g(x)为非周期函数：T

2T2第十七页，共一百一十九页，编辑于2023年，星期二当xT,T时，有：Ce因为有：Cn

12T

ge

gTx将g(x)延拓后，为gT(x)函数：

T

T

22将延拓后的周期函数展开，得到的傅立叶级数，该函数在所取周期，与原函数完全相同。即

nxjnn2

T

2

2

TT

2

gxgTx

2

jn

d

T

T

2

2

Tn第十八页，共一百一十九页，编辑于2023年，星期二1

n

则有：

g(x)limd]e

T1

nQ(f)df

limf

Q(fn)lim

n

TTTn显然，当T趋近无穷大时，对g(x)在任何x点都是成立的，假设有一函数Q(f)，其对整个坐标轴的积分可以表示如下：因为有：所以：xjn

jn22

T2

TTT[

T

g()e

21f

1Tf

1Tf1Tf

0f1f2f3fnf

Qf

见下图。

nT,...,fn

nf

2T

1T,f2

2ff0

0,f1

fQ()f

0第十九页，共一百一十九页，编辑于2023年，星期二1

n

[2T

g()eTTd]e

TTQ(f)df

lim二、傅立叶变换

两个公式放在一起对比一下：则：

上两式叫做傅立叶变换对。由g(x)得到G(f)的公式叫做傅立叶变换，

G(f)称为原函数g(x)的频谱函数。记作

F(f)=F{g(x)}。求原函数的公式叫做傅立叶逆变换，记作

g(x)=

-1{F(f)}。xjn

jn22

TT

2g(x)limQ(

)

1

nTTn

即：

dx

j2fx

如果令：G(f)

g(x)e

g(x)

G(f)ej2fxdf

第二十页，共一百一十九页，编辑于2023年，星期二

数字图像为二维函数，下面给出二维傅立叶变换公式：正变换：F(u,v)

f(x,y)exp[

j2(uxvy)]dxdy

逆变换：f(x,y)

F(u,v)exp[j2(uxvy)]dudv

第二十一页，共一百一十九页，编辑于2023年，星期二

一个周期函数，必须在一个周期内只有有限个极值点和间断点，并且要求在一个周期内绝对可积，才能展成傅立叶级数。

对于非周期函数，我们将它延拓为周期是无穷的周期函数而得到傅立叶积分。显然非周期函数能进行傅立叶变换必须满足：在整个xy平面内函数只有有限个极值点和间断点，对整个xy平面绝对可积。

但是，不少有用的函数是不满足以上条件的。为此必须把以上傅里叶变换定义推广。在推广定义以后不少不满足上述条件的函数可以求出其变换式。广义傅立叶变换第二十二页，共一百一十九页，编辑于2023年，星期二

若有一个函数序列fn(x,y)存在傅里叶变换，对应的谱函数为函数序列Fn(u,v)。函数f(x,y)不存在傅立叶变换，但f(x,y)是fn(x,y)当n→∞时的极限，则定义当n→∞时Fn(u,v)的极限F(u,v)为f(x,y)的广义傅立叶变换。F1(u,v)F2(u,v)Fn(u,v)F(u,v)f1(x,y)

存

在

f

2(x,y)存在

f

n(x,y)存在存在f(x,y)

定义存在第二十三页，共一百一十九页，编辑于2023年，星期二sgn(x)

例如，对于符号函数：显然对整个坐标轴不可积。对于函数序列：1x

01x

0n

nxfn(x)

e

x

enx

0

0x

0

n

ℱ

0

xx

nn

0

2

2

n

n所以：

ℱ1

2

2

n第二十四页，共一百一十九页，编辑于2023年，星期二F

,

若则：

相似定理说明原面数空域坐标(x,y)“伸展”，其频谱函数在频率域中是“收缩”，并且高度也有相应变化。而当原函数在空域坐标中“收缩”时，则其频谱函数在频率城中变宽。uva

bFfax,by

1abF{f(x,y)}F(u,v)

傅立叶变换的性质

线性定理

a、b为任意复常数，g(x,y)、h(x,y)存在傅立叶变换，则：

F{ag(x,y)bh(x,y)}aF{g(x,y)}bF{h(x,y)}

相似性定理第二十五页，共一百一十九页，编辑于2023年，星期二

位移定理若则：

F{f(xa,y

b)}

F(u,v)exp

j2(aubv)

即原函数在空域中平移，频谱函数在频率域中有相应的相移，相移大小与u、v呈线性关系。显然不论原函数在空域中如何平移，零频分量总是一样的，因为此时u、v=0。

同样原函数在空域中的相移，引起的是频谱函数在频率域中的平移，即

F

1{F(ua,vb)}f(x,y)exp(j2(axby)F{f(x,y)}

F(u,v)第二十六页，共一百一十九页，编辑于2023年，星期二f(x,y)dxdy

帕色伏定理若则：这个结果可以理解为能量守恒的表达式。

卷积定理

2

2F(u,v)dudvF{f(x,y)}

F(u,v)F{f(x,y)}F(u,v)F{h(x,y)}

H(u,v)

则：F{f(x,y)*h(x,y)}F(u,v)H(u,v)

卷积定理表明，两个函数在空域内的卷积，得到新函数的频谱等于原来两个函数各自的乘积。这样就把空域中卷积转化为频域中乘积。第二十七页，共一百一十九页，编辑于2023年，星期二)

,

(

)]

,

(

)]

,

(

[yxfyxfyxf

ℱ[

ℱ

ℱ),()],()],([11

y

x

f

y

x

f

y

x

fℱ

ℱ

[

傅立叶积分定理卷积定理证明如下：{g(x,y)*h(x,y)}

[

g(,)h(x

,y

)dd]exp[

j2(uxvy)]dxdy

{g(x,y)*h(x,y)}exp[j2(uxvy)]dxdy

g(,){

h(x

,y

}exp[

j2(uxvy)]dxdy}dd

g(,)H(u,v)exp[j2(u

v)]dd

H(u,v)

g(,)exp[

j2(u

v)]ddG(u,v)H(u,v)1

1ℱ

Fℱℱ

ℱ第二十八页，共一百一十九页，编辑于2023年，星期二

可分离变量性

若则：F

f(x,y)exp[j2(uxvy)]dxdyx(x)f

y(y)exp[

j2(uxvy)]dxdy

fx

(x)exp(j2ux)dxfy(y)exp(j2vy)dy

f(x,y)

fx(x)f

y(y)ℱF{f(x,y)}ℱF{fx(x)}

ℱF{fy(y)}证明：ℱfx,y

f

ℱF{fx(x)}ℱF{fy(y)}第二十九页，共一百一十九页，编辑于2023年，星期二原函数谱函数1(u,v)(x,y)1(xx0,yy0)exp[j2(ux0vy0)]exp[j2(axby)](ua,vb)cos(2f0x)[(uf0)(uf0)]2[(xx0)(xx0)]2cos(2fx0)sin(2f0x)[(ff0)(ff0)]2j[(xx0)(xx0)]2jsin(2fx0)rect(x)rect(y)sinc(u)sinc(v)(x)(y)22sinc(u)sinc(v)comb(x)comb(y)comb(u)comb(v)22exp[(xy)]22exp[(uv)]第三十页，共一百一十九页，编辑于2023年，星期二xe

j2fxdx

1e

j的

f

0变换2cos2xf

f0dx

lim2cos2xf

f0dx

δ函数的变换

δ函数的傅立叶变换为：

2x可以通过位移定律间接导出，也可以由定理直接推出。

00Fj2f0x

lim2

sinc2ff0ff0sin2f

f0

2ff0

lim2

ℱ

Fx同理可得：

ℱFA0xA0由位移定律可得：

ℱFxx0ej2x0fℱe举例第三十一页，共一百一十九页，编辑于2023年，星期二ℱ

Fsinx

sinxee

jx

e

jx

j2fx1

e

j2

f

1

e1dx

e

f

2

f

2

sin(x)的变换dxe

dx

j2fx2j

dx

dx

e

2jj2f1j2f1

dx

j2

f

1

2

2

2j

1

1

12j

举例第三十二页，共一百一十九页，编辑于2023年，星期二combxx

n,n为整数Cn

1dx1e

j2nxℱ

Fcombxℱ

Fe

ℱ

F

e

f

n

combf

comb(x)的变换

comb(x)函数称梳状函数，定义为：换称傅立叶指数级数：

n函数图形如右图所示，周期T为1。可以将此函数首先转combx0123321xcombx

Cnej2nxn12

212

2comb(x)ej2nx(x)ej2nxdx1

n所以：combxj2nx

nn

nj2nx举例第三十三页，共一百一十九页，编辑于2023年，星期二

:

fx

4.2

离散傅里叶变换（Discrete

Fourier

Transform）

函数fx的一维离散傅里叶变换由下式定义：

N

1

:

F

x0义为：

u

0,1,2,...,

N

1

Fu1N

1u0

1NFue

j2ux/

N第三十四页，共一百一十九页，编辑于2023年，星期二相位:能量谱傅里叶频谱：

Fu

R2u

I

2uu

arctanIu/

Ru22u

I

2u

RPu

Fu4.2

离散傅里叶变换（Discrete

Fourier

Transform）第三十五页，共一百一十九页，编辑于2023年，星期二

4.2

离散傅里叶变换（Discrete

Fourier

Transform）

同连续函数的傅里叶变换一样，离散函数的傅里叶变换也可推广到二维的情形，其二维离散傅里叶变换定义为：

1Nf

x,ye

j2(uxvy)/NN1N1x0y0Fu,v

式中u

0,1,...,N

1，

v

0,1,...,N

1。二维离散傅里叶反变换定义为N

1N

1u0v0

1Nfx,yFu,ve

j2(uxvy)/N第三十六页，共一百一十九页，编辑于2023年，星期二Pu,v

Fu,v

R2u,v

I2u,v傅里叶频谱：相位：能量谱：

4.2

离散傅里叶变换（Discrete

Fourier

Transform）

式中x

0,1,...,

N

1，y

0,1,...,N

1

式中u、v是频率变量。与一维的情况一样，二维函数的离散傅里叶谱、能量和相位谱为:Fu,v

R2u,v

I

2u,v

Iu,vRu,vu,v

arctan2第三十七页，共一百一十九页，编辑于2023年，星期二示例

1、编写程序，计算二维离散傅立叶级数

2、讨论算法执行的时间第三十八页，共一百一十九页，编辑于2023年，星期二

快速傅里叶变换(FFT)并不是一种新的变换，它是离散傅里叶变换(DFT)的一种算法。这种方法是在分析离散傅里叶变换(DFT)中的多余运算的基础上，进而消除这些重复工作的思想指导下得到的，所以在运算中大大节省了工作量，达到了快速的目的。4.3

快速傅里叶变换(Fast

FourierTransform)第三十九页，共一百一十九页，编辑于2023年，星期二§4.3.1

引言

FFT:

Fast

Fourier

Transform

1965年，Cooley-Turky

发表文章《机器计算傅里叶级数的一种算法》，提出FFT算法，解决DFT运算量太大，在实际使用中受限制的问题。

FFT的应用。频谱分析、滤波器实现、实时信号处理等。

DSP芯片实现。TI公司的TMS

320c30，10MHz时钟，基2-FFT1024点FFT时间15ms。第四十页，共一百一十九页，编辑于2023年，星期二

IFFTy(n)x(n)

FFTh(n)

FFT

典型应用：信号频谱计算、系统分析等频谱分析与功率谱计算

DFT系统分析

x(n)

h(n)y(n)第四十一页，共一百一十九页，编辑于2023年，星期二

k0X(k)WN

1N1

knNx(n)

直接计算DFT的问题及改进途径1、

DFT与IDFT

N点有限长序列x(n)

N1

kn

N

n0第四十二页，共一百一十九页，编辑于2023年，星期二实数乘法实数加法一次复乘42一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)(N点DFT)24N2N(2N–1)IDFT运算量与DFT复数乘法复数加法一个X(k)NN–1N个X(k)(N点DFT)2NN(N–1)()x

n

W

DFT与IDFT运算特点nkNN1n0a

jbc

jd

acbd

jad

cb相同。第四十三页，共一百一十九页，编辑于2023年，星期二(WN

)WN

nkWNNn)kWN

(Nk)WWWN

NWN

Nnk

*对称性

nkNW

(Nn)kN

n(Nk)NWW周期性降低DFT运算量的考虑

j

nk

nk

NNknk

nNnk

nk

mnk

nk

nk

/mN

mN

N

N

/m

j

j

mnk

N

2

mN

0第四十四页，共一百一十九页，编辑于2023年，星期二FFT算法分类:

时间抽选法

DIT:

Decimation-In-Time

频率抽选法

DIF:

Decimation-In-FrequencyFFT算法的基本思想：

利用DFT系数的特性，合并DFT运算中的某些项，把长序列DFT

短序列DFT，从而减少其运算量。第四十五页，共一百一十九页，编辑于2023年，星期二)2()(1

r

x

r

x按时间抽取（DIT）的FFT算法12...，r

0，，，N/21x2(r)

x(2r

1)（Decimation

In

Time）1、算法原理设序列点数

N

=

2L，L

为整数。若不满足，则补零N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成两组：第四十六页，共一百一十九页，编辑于2023年，星期二

DFT

x(n)

x(n)WN

knx(2r)WN

N/21

(2r1)kx(2r

1)WN

r0x1(r)WN

rk/2

WN

k

x2(r)WN

rk/2将N点DFT定义式分解为两个长度为N/2的DFTN1n0X(k)2rkr0

N/21

n为奇r0

n为偶r0N/21N/21X(k)

X1(k)WNkX2(k)记：………（1）

X1(k)（这一步利用：WN2rk

WNrk/2

X2(k)）r,k

0,1,...N/21第四十七页，共一百一十九页，编辑于2023年，星期二WWX1kx1(r)WNr(

/N2

/2k)x1(r)WNrk/2X1(k)kX2(k)X2k又WN

W

W

W2X(Nk)

X(Nk)W

(N/2k)X(Nk)222再利用周期性求X(k)的后半部分N

N/2kN

N

kNN2N2N/21N/21r0r0

rkN/2

r(N/2k)N/2(2)

X(k)

X1(k)WNkX2(k)，k

0,1,2,...N/21

1N2X1(k)WN

kX2(k)，k0,1,2,...N/21第四十八页，共一百一十九页，编辑于2023年，星期二X(k

2)

X1(k)WN

X2(k)将上式表达的运算用一个专用“蝶形”信流图表示。X1(k)WN

kX2(k)

X1(k)WNkX2(k)X1(k)

X2(k)WNkkk

X(k)

X1(k)WN

X2(k)

Nk

0,1,...,N/21注：a.

上支路为加法，下支路为减法；

b.

乘法运算的支路标箭头和系数。第四十九页，共一百一十九页，编辑于2023年，星期二N

82用“蝶形结”表示上面运算的分解：3x(0)x(2)x(4)x(6)

x(1)

x(3)

x(5)x(7)X(0)X(1)

X(2)

X(3)X(4)

X(5)X(6)X(7)WN0WN1

WN2

WN3X1(0)

X1(1)

X1(2)

X1(3)X

2(0)X2(1)X2(2)

X

2(3)

N

2点

DFT

N

2点

DFT第五十页，共一百一十九页，编辑于2023年，星期二复数乘法复数加法一个N/2点DFT2(N/2)N/2(N/2–1)两个N/2点DFT2N/2N(N/2–1)一个蝶形12N/2个蝶形N/2N总计2N/2N/22N/2NN/21N2N/2分解后的运算量：运算量减少了近一半第五十一页，共一百一十九页，编辑于2023年，星期二(2l1)

xX1

3(k)WNk/2

4(k)(k)

XX

进一步分解

M

N

2DFT又可同样进一步分解为4个

点的DFT。

4x1(2l)

x3(l)x1

4(l)l

0,1,...,N/41kX1(k)

X3(k)WN/2X4(k)

N

4N

4k

0,1,...,1第五十二页，共一百一十九页，编辑于2023年，星期二点点WN0/2WN1

/2x4(l)x(2)x(6)x(0)x(4)X1(0)X1(1)X1(2)

X1(3)X3(0)X3(1)X4(0)X

4(1)

N

4DFTN

4DFT

―蝶形”信流图表示x3(l)第五十三页，共一百一十九页，编辑于2023年，星期二点点点W点....N点DFT分解为四个N/4点的DFT

N

4DFTN

4DFTN

4DFTN

4DFTx(2)x(6)x(0)x(4)

x(1)x(5)WN0WN2WN0WN2WN0

1

NWN2WN3X(0)

X(1)X(2)X(3)X(4)X(5)

X(6)

X(7)X(k)

x(3)

x(7).....x(n)第五十四页，共一百一十九页，编辑于2023年，星期二

类似进一步分解

类似的分解一直继续下去，直到分解为最

后的两类蝶形运算为止(2点DFT).

如上述N=8=23，N/4=2点中：1点DFTx(0)1点DFTx(4)X3(0)X3(1)

02W第五十五页，共一百一十九页，编辑于2023年，星期二x(0)WN/4x(4)x(0)WNx(4)x(0)WN/4x(4)x(0)WNx(4)进一步简化为蝶形流图：

0NWX3(0)X3(1)x(0)x(4)0

0

01X3(0)

X3(1)因此8点FFT时间抽取方法的信流图如下——第五十六页，共一百一十九页，编辑于2023年，星期二WWWW................

..........

..

..............第三级x(2)x(6)x(0)

x(4)x(1)x(3)x(5)x(7)WN0

0N

0N

0NWN0WN2WN0WN2

第一级第二级X0(k)m1

X1(k)m

2X

2(k)

m

3

1NWN0WN2WN3X(0)

X(1)X(2)

X(3)X(4)X(5)X(6)

X(7)X3(k)第五十七页，共一百一十九页，编辑于2023年，星期二FFT运算量与运算特点1．

N=2L时，共有L=log2N级运算；每一级有N/2个蝶形结。2．每一级有N个数据中间数据），且每级只用到本级的转入中间数据，适合于迭代运算。3．计算量：每级N/2次复乘法，N次复加。（每蝶形只乘一次，加减各一次）。共有L*N/2=N/2log2N

次复乘法；复加法L*N=Nlog2N

次。与直接DFT定义式运算量相比(倍数)

N2/(Nlog2N)

。当

N大时，此倍数很大。第五十八页，共一百一十九页，编辑于2023年，星期二()

F

m

DFTN2N2()log

F

m

FFT

N22Nlog2

N

比较DFT可以直观看出，当点数N越大时，FFT的优点更突出。第五十九页，共一百一十九页，编辑于2023年，星期二按时间抽取FFT蝶形运算特点1、关于FFT运算的混序与顺序处理（位倒序处理）由于输入序列按时间序位的奇偶抽取，故输入序列是混序的，为此需要先进行混序处理。混序规律：

x(n)按n位置进行码位（二进制）倒置规律输入，而非自然排序，即得到混序排列。所以称为位倒序处理。位倒序实现：（1）DSP实现采用位倒序寻址（2）通用计算机实现可以有两个方法：一是严格按照位倒序含义进行；二是倒进位的加N/2。第六十页，共一百一十九页，编辑于2023年，星期二倒位序自然序00000000100410010102201011063011001141001015510101136110111771111x(n)n

(n2nn0)2倒位序第六十一页，共一百一十九页，编辑于2023年，星期二第六十二页，共一百一十九页，编辑于2023年，星期二x(n)

nn

，

0,1,2....31计算。计算x(13)

13

169x(13)

22

484例问倒序前寄存器的数据值？

2N

32

点FFT。用时间抽取输入倒序算法，x(13)和倒序后

x(13)的数2N

3225(13)10

(01101)22解：倒序前倒序倒序为

(10110)2

(22)10倒序后第六十三页，共一百一十九页，编辑于2023年，星期二(N

2

)

DIT

FFT中最主要的蝶形运算实现（1）参与蝶形运算的两类结点（信号）间“距离

”（码地址）与其所处的第几级蝶形有关；第mL级的“结距离”为2m1，m1,2,...L

(即原位计算迭代）（2）每级迭形结构为

Xm(k)

Xm1(k)Xm1(k2m1)WNr

第六十四页，共一百一十九页，编辑于2023年，星期二（3）

WN的确定：

蝶形运算两节点的第一个节点为k值，表

示成L位二进制数，左移L–

m位，把右边

空出的位置补零，结果为r的二进制数。Lmr

(k)2

2

r第m级的r取值：WN

k第六十五页，共一百一十九页，编辑于2023年，星期二DIT算法的其他形式流图输入倒位序输出自然序输入自然序输出倒位序输入输出均自然序相同几何形状

–输入倒位序输出自然序

–输入自然序输出倒位序第六十六页，共一百一十九页，编辑于2023年，星期二时间抽取、

输入自然顺序、

输出倒位序的FFT流图WN0WN0WN0WN2－1－1－1WN0－1WN0WN2－1－1－1－1X(0)x(0)X(4)x(1)X(2)x(2)X(6)X(1)x(3)x(4)X(5)x(5)X(3)x(6)X(7)x(7)－1－1WN0WN0WN2WN1WN3－1－1第六十七页，共一百一十九页，编辑于2023年，星期二例用FFT算法处理一幅N×N点的二维图像，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？

解

当N=1024点时，FFT算法处理一幅二维图像所需复数乘法约为分之一。

即原需要3000小时，现在只需要2

分钟。log2

N2

107

次，仅为直接计算DFT所需时间的10万N2

2第六十八页，共一百一十九页，编辑于2023年，星期二e

y0

f

x,yeF(x,v)

N

x04.4.1可分离性（Separability）4.4

傅里叶变换的性质(Characteristics

of

Fourier

Transform)

1Nf(x,y)ej2(uxvy)/NN

1N

1x0y0F(u,v)N1x0N1y0

1NFu,vfx,yej2vy/Nj2ux/Nv

0,1,,N

1

1N1NFx,ve

j2πux/NFu,v

u,v

0,1,,N1每1列求变换再乘以N

1

N1j2vy/N

N

x,v

每1行求傅里叶变换再对F第六十九页，共一百一十九页，编辑于2023年，星期二4.4

傅里叶变换的性质(Characteristics

of

Fourier

Transform)可分离性（Divisibility）

F(x, v)

图4.5

由2步1-D变换计算2-D变换第七十页，共一百一十九页，编辑于2023年，星期二

u0

v0

F(u,v)eeFu,ve

1NN1N1j2(uxvy)/Nf(x,y)N1

u0N1

v0

1Nfx,yj2vy/Nj2ux/N4.4

傅里叶变换的性质(Characteristics

of

Fourier

Transform)第七十一页，共一百一十九页，编辑于2023年，星期二4.4

傅里叶变换的性质(Characteristics

of

Fourier

Transform)4.4.2平移性质（Translation）f(x,y)ej2ux0v0y/N

F(u

u0,v

v0)

j2ux0vy0/Nf(xx0,yy0)

F(u,v)e(1)xy

e

j(xy)1

e

jf

x,y

与一个指数相乘等于将变换后的频率域中心移到新的位置。f

x,y的平移将不改变频谱的幅值（amplitude）。第七十二页，共一百一十九页，编辑于2023年，星期二4.4

傅里叶变换的性质(Characteristics

of

Fourier

Transform)4.4.3周期性和共轭对称性（Periodicity

and

Conjugate

Symmetry）

傅里叶变换和反变换均以N为周期，即

Fu,v

Fu

N,v

Fu,v

N

Fu

N,v

N

（4.29）

上式可通过将右边几项分别代入式（4.16）来验证。它表明，尽管

Fu,v有无穷多个u和v的值重复出现，但只需根据在任一个周期里的

N个值就可以从Fu,v得到

fx,

y。第七十三页，共一百一十九页，编辑于2023年，星期二频谱的周期性F(u,v)

F(uM,vN)第七十四页，共一百一十九页，编辑于2023年，星期二第七十五页，共一百一十九页，编辑于2023年，星期二共轭对成性（4.30）（4.31）

4.4

傅里叶变换的性质(Characteristics

of

Fourier

Transform)如果

fx,y是实函数，则它的傅里叶变换具有Fu,v

F

u,v

Fu,v

F

u,v第七十六页，共一百一十九页，编辑于2023年，星期二4.4

傅里叶变换的性质(Characteristics

of

Fourier

Transform)4.4.4旋转性质（Rotation）

f(x,y)

Fu,vx

rcosy

rsinu

wcosv

wsin

f(r,

0)

F(w,

0)上式表明，对

f(x,y)

旋转一个角度

0

F(u,v)

对应于将其傅里叶变换也旋转相同的角度

0第七十七页，共一百一十九页，编辑于2023年，星期二例4.4二维离散傅立叶变换的旋转性（具体程序参见书）。（a）原始图像（b）原图像的傅（c）旋转后的图像（d）旋转后图像的傅里叶频谱4.4

傅里叶变换的性质(Characteristics

of

Fourier

Transform)

里叶频谱

上例表明，对fx,

y旋转一个角度0对应于将其傅里叶变换Fu,v也旋转相同的角度0。第七十八页，共一百一十九页，编辑于2023年，星期二分配律(Distribution

Law)

根据傅里叶变换对的定义可得到：（4.33）4.4

傅里叶变换的性质(Characteristics

of

Fourier

Transform)f1x,

y

f2x,

y

f1x,

yf2x,

y

上式表明傅里叶变换和反变换对加法满足分配律，

但需注意对乘法则不满足，一般有：f1x,

y

f2x,

y

f1x,

yf2x,

y（4.34）4.4.5分配律（Distribution

Law）第七十九页，共一百一十九页，编辑于2023年，星期二F

,

4.4

傅里叶变换的性质(Characteristics

of

Fourier

Transform)4.4.6尺度变换（Scaling）

afx,

y

aFu,v

u

v

a

b

1abfax,by第八十页，共一百一十九页，编辑于2023年，星期二

4.4

傅里叶变换的性质(Characteristics

of

Fourier

Transform)【例4.5】比例尺度展宽。（a）原始图像

（b）比例尺度展宽前的频谱（c）比例尺度a=0.1，b=1，展宽后的频谱第八十一页，共一百一十九页，编辑于2023年，星期二

fx,

y

fx,

ye

Nfx,

y对一个2-D离散函数，其平均值可用下式表示：（4.37）4.4

傅里叶变换的性质(Characteristics

of

Fourier

Transform)N

1N

1

x0

y0

1N

2f

(x,

y)

当正反变换采用相同的标度数1/

N时，傅里叶变换域原点的频谱分量为：

1NN

1N

1

x0

y0N

1N

1

x0

y0x0

y0

j

N

f

(x,

y)

1

N

2F0,02

N4.4.7平均值（Average

Value）第八十二页，共一百一十九页，编辑于2023年，星期二（4.39）

4.4

傅里叶变