圖像正交變換

圖像正交變換2023/7/22第1頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月第4章圖像變換(Image

Transform)4.1

傅立葉變換簡(jiǎn)介4.2

傅里葉變換理論4.3

快速傅里葉變換4.4

傅里葉變換的性質(zhì)4.5

圖像傅里葉變換實(shí)例4.6

其他離散變換第2頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

線性系統(tǒng)理論通常用于描述電路和光學(xué)系統(tǒng)的行為，為采樣、濾波等提供堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)。一、定義系統(tǒng)：對(duì)信號(hào)施以的一種變換?？梢允请娐废到y(tǒng)、光學(xué)系統(tǒng)甚至其他一切對(duì)信號(hào)影響的實(shí)體。線性移不變系統(tǒng)：具有線性和移不變特性的系統(tǒng)。二、研究線性系統(tǒng)的兩種方法1、任何一個(gè)系統(tǒng)都有一個(gè)傳遞函數(shù)，它與調(diào)諧輸入相乖得到對(duì)應(yīng)的調(diào)諧輸出。2、任何一個(gè)系統(tǒng)都有一個(gè)實(shí)值的沖激響應(yīng)，它與輸入信號(hào)的卷積給出對(duì)應(yīng)的輸出。第3頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月簡(jiǎn)介

1、背景

1768年出生于法國(guó)。

傅立葉的思想：1807年，向法國(guó)科學(xué)院提交報(bào)告：任何周期函數(shù)都可以用一系列正弦波來(lái)表示。第4頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月信號(hào)的分解第5頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月一、

圖象變換的引入1.

方法：對(duì)圖象信息進(jìn)行變換，使能量保持但重新分配。2.

目的：有利于加工、處理[濾除不必要信息(如噪聲)，加強(qiáng)/提取感興趣的部分或特征]。二、

方法分類(lèi)

可分離、正交變換:

2D-DFT

,

2D-DCT

,1．提取圖象特征（如）：（1）直流分量：f(x,y)的平均值=F(0,0)；（2）目標(biāo)物邊緣：F（u,v）高頻分量。2．圖像壓縮：正交變換能量集中，對(duì)集中（小）部分進(jìn)行編碼。3．圖象增強(qiáng)：低通濾波，平滑噪聲；高通濾波，銳化邊緣。三、

用途2D-DHT,

2D-DWT

。傅立葉變換作用第6頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月連續(xù)周期函數(shù)的傅立葉級(jí)數(shù)及非周期信號(hào)的傅立葉變換第7頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月ancos(n)bnsin(n)

g()cos(n)d

g()sin(n)d

一、連續(xù)周期函數(shù)的傅立葉級(jí)數(shù)

周期為2π

周期為2π的函數(shù)g(θ)，若在一個(gè)周期內(nèi)只有有限個(gè)極值點(diǎn)和不連續(xù)點(diǎn)，并且在一個(gè)周期內(nèi)絕對(duì)可積，則它可以展成傅里葉三角級(jí)數(shù)：其中：

n1a0

2g()

an

bn

1

1

第8頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月2

2

2

ancosna0xbnsinnTxT

x02xdx

周期為T(mén)

周期為T(mén)的函數(shù)將它展開(kāi)成傅立葉三角級(jí)數(shù)時(shí)展開(kāi)式，只是要根據(jù)對(duì)應(yīng)關(guān)系將θ換算成x，它們之間的換算關(guān)系是，

x

所以有

g(x)

2

n1

T

T其中：bn

g(x)sinn

T2

x0T第9頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月1md

x

md

0xd0d2d

2、舉例有一縫寬和縫距相等的矩形光柵，振幅透過(guò)率為：其中，m為整數(shù)，將它展開(kāi)成傅立葉三角級(jí)數(shù)。函數(shù)圖形如下所示：

g(x)其它d2

g(x)

第10頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月2sin(2k

1)x、sin2πx、sin6πx、sin10πx、取前項(xiàng)：繪圖如下：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)第11頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月第12頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月Cnex

3、指數(shù)形式通過(guò)歐拉公式，把正弦函數(shù)、余弦函數(shù)和指數(shù)函數(shù)聯(lián)系起來(lái)，不難證明傅里葉三角級(jí)數(shù)可以寫(xiě)成指數(shù)級(jí)數(shù)的形式。

若g(x)的周期為T(mén)，在一個(gè)周期內(nèi)只有有限個(gè)極值點(diǎn)和不連續(xù)點(diǎn)，并且在一個(gè)周期內(nèi)絕對(duì)可積。則g(x)可以展開(kāi)成傅立葉指數(shù)級(jí)數(shù)：其中：

nxjn2

Tg(x)xjndxCn

x0

T

0g(x)e

1T2

T第13頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月T

x0g(x)dx

0T

x0

xg(x)cos(nx)dx

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

證明如下：取n為任一正整數(shù)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第14頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

Ce

22C0

Cne

T

Cne2ancos

nx

bnsin

nx

jnxn2

T

ng(x)

jn

x

jn

x

Tn1

cosnxjsinnx

n1

2TT即：得證。n1Ta0

2

2

T第15頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月傅立葉級(jí)數(shù)第16頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

事實(shí)上周期函數(shù)只是數(shù)學(xué)上的描述，對(duì)于一切物理過(guò)程嚴(yán)格來(lái)說(shuō)都是非周期的。有些物理過(guò)程可以用周期函數(shù)來(lái)近似描述，象前面介紹的矩形光柵的例子，只有當(dāng)光柵常數(shù)ｄ比光柵總寬度小得多的時(shí)，也就是總縫數(shù)很大時(shí)才可以用周期函數(shù)來(lái)描寫(xiě)這種光柵，當(dāng)然這種描寫(xiě)仍是近似的。還有相當(dāng)多的物理現(xiàn)象，只發(fā)生在有限的空間范圍和時(shí)間間隔內(nèi)，這樣的現(xiàn)象對(duì)于空間和時(shí)間來(lái)說(shuō)是非周期的。對(duì)于大量非周期函數(shù)的展開(kāi)，首先可以以它有非零值的范圍（空間范圍或時(shí)間間隔）為周期，將它延拓成為周期函數(shù)。右圖中g(shù)(x)為非周期函數(shù)：T

2T2第17頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月當(dāng)xT,T時(shí)，有：Ce因?yàn)橛校篊n

12T

ge

gTx將g(x)延拓后，為gT(x)函數(shù)：

T

T

22將延拓后的周期函數(shù)展開(kāi)，得到的傅立葉級(jí)數(shù)，該函數(shù)在所取周期，與原函數(shù)完全相同。即

nxjnn2

T

2

2

TT

2

gxgTx

2

jn

d

T

T

2

2

Tn第18頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月1

n

則有：

g(x)limd]e

T1

nQ(f)df

limf

Q(fn)lim

n

TTTn顯然，當(dāng)T趨近無(wú)窮大時(shí)，對(duì)g(x)在任何x點(diǎn)都是成立的，假設(shè)有一函數(shù)Q(f)，其對(duì)整個(gè)坐標(biāo)軸的積分可以表示如下：因?yàn)橛校核裕簒jn

jn22

T2

TTT[

T

g()e

21f

1Tf

1Tf1Tf

0f1f2f3fnf

Qf

見(jiàn)下圖。

nT,...,fn

nf

2T

1T,f2

2ff0

0,f1

fQ()f

0第19頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月1

n

[2T

g()eTTd]e

TTQ(f)df

lim二、傅立葉變換

兩個(gè)公式放在一起對(duì)比一下：則：

上兩式叫做傅立葉變換對(duì)。由g(x)得到G(f)的公式叫做傅立葉變換，

G(f)稱(chēng)為原函數(shù)g(x)的頻譜函數(shù)。記作

F(f)=F{g(x)}。求原函數(shù)的公式叫做傅立葉逆變換，記作

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

第20頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

數(shù)字圖像為二維函數(shù)，下面給出二維傅立葉變換公式：正變換：F(u,v)

f(x,y)exp[

j2(uxvy)]dxdy

逆變換：f(x,y)

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

第21頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

一個(gè)周期函數(shù)，必須在一個(gè)周期內(nèi)只有有限個(gè)極值點(diǎn)和間斷點(diǎn)，并且要求在一個(gè)周期內(nèi)絕對(duì)可積，才能展成傅立葉級(jí)數(shù)。

對(duì)于非周期函數(shù)，我們將它延拓為周期是無(wú)窮的周期函數(shù)而得到傅立葉積分。顯然非周期函數(shù)能進(jìn)行傅立葉變換必須滿(mǎn)足：在整個(gè)xy平面內(nèi)函數(shù)只有有限個(gè)極值點(diǎn)和間斷點(diǎn)，對(duì)整個(gè)xy平面絕對(duì)可積。

但是，不少有用的函數(shù)是不滿(mǎn)足以上條件的。為此必須把以上傅里葉變換定義推廣。在推廣定義以后不少不滿(mǎn)足上述條件的函數(shù)可以求出其變換式。廣義傅立葉變換第22頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

若有一個(gè)函數(shù)序列fn(x,y)存在傅里葉變換，對(duì)應(yīng)的譜函數(shù)為函數(shù)序列Fn(u,v)。函數(shù)f(x,y)不存在傅立葉變換，但f(x,y)是fn(x,y)當(dāng)n→∞時(shí)的極限，則定義當(dāng)n→∞時(shí)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)

定義存在第23頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月sgn(x)

例如，對(duì)于符號(hào)函數(shù)：顯然對(duì)整個(gè)坐標(biāo)軸不可積。對(duì)于函數(shù)序列：1x

01x

0n

nxfn(x)

e

x

enx

0

0x

0

n

?

0

xx

nn

0

2

2

n

n所以：

?1

2

2

n第24頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月F

,

若則：

相似定理說(shuō)明原面數(shù)空域坐標(biāo)(x,y)“伸展”，其頻譜函數(shù)在頻率域中是“收縮”，并且高度也有相應(yīng)變化。而當(dāng)原函數(shù)在空域坐標(biāo)中“收縮”時(shí)，則其頻譜函數(shù)在頻率城中變寬。uva

bFfax,by

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

傅立葉變換的性質(zhì)

線性定理

a、b為任意復(fù)常數(shù)，g(x,y)、h(x,y)存在傅立葉變換，則：

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

相似性定理第25頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

位移定理若則：

F{f(xa,y

b)}

F(u,v)exp

j2(aubv)

即原函數(shù)在空域中平移，頻譜函數(shù)在頻率域中有相應(yīng)的相移，相移大小與u、v呈線性關(guān)系。顯然不論原函數(shù)在空域中如何平移，零頻分量總是一樣的，因?yàn)榇藭r(shí)u、v=0。

同樣原函數(shù)在空域中的相移，引起的是頻譜函數(shù)在頻率域中的平移，即

F

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

F(u,v)第26頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月f(x,y)dxdy

帕色伏定理若則：這個(gè)結(jié)果可以理解為能量守恒的表達(dá)式。

卷積定理

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)

卷積定理表明，兩個(gè)函數(shù)在空域內(nèi)的卷積，得到新函數(shù)的頻譜等于原來(lái)兩個(gè)函數(shù)各自的乘積。這樣就把空域中卷積轉(zhuǎn)化為頻域中乘積。第27頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月)

,

(

)]

,

(

)]

,

(

[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??

?第28頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

可分離變量性

若則：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)}第29頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月原函數(shù)譜函數(shù)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)]第30頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月xe

j2fxdx

1e

j的

f

0變換2cos2xf

f0dx

lim2cos2xf

f0dx

δ函數(shù)的變換

δ函數(shù)的傅立葉變換為：

2x可以通過(guò)位移定律間接導(dǎo)出，也可以由定理直接推出。

00Fj2f0x

lim2

sinc2ff0ff0sin2f

f0

2ff0

lim2

?

Fx同理可得：

?FA0xA0由位移定律可得：

?Fxx0ej2x0f?e舉例第31頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月?

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

舉例第32頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月combxx

n,n為整數(shù)Cn

1dx1e

j2nx?

Fcombx?

Fe

?

F

e

f

n

combf

comb(x)的變換

comb(x)函數(shù)稱(chēng)梳狀函數(shù)，定義為：換稱(chēng)傅立葉指數(shù)級(jí)數(shù)：

n函數(shù)圖形如右圖所示，周期T為1。可以將此函數(shù)首先轉(zhuǎn)combx0123321xcombx

Cnej2nxn12

212

2comb(x)ej2nx(x)ej2nxdx1

n所以：combxj2nx

nn

nj2nx舉例第33頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

:

fx

4.2

離散傅里葉變換（Discrete

Fourier

Transform）

函數(shù)fx的一維離散傅里葉變換由下式定義：

N

1

:

F

x0義為：

u

0,1,2,...,

N

1

Fu1N

1u0

1NFue

j2ux/

N第34頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月相位:能量譜傅里葉頻譜：

Fu

R2u

I

2uu

arctanIu/

Ru22u

I

2u

RPu

Fu4.2

離散傅里葉變換（Discrete

Fourier

Transform）第35頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

4.2

離散傅里葉變換（Discrete

Fourier

Transform）

同連續(xù)函數(shù)的傅里葉變換一樣，離散函數(shù)的傅里葉變換也可推廣到二維的情形，其二維離散傅里葉變換定義為：

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第36頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月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是頻率變量。與一維的情況一樣，二維函數(shù)的離散傅里葉譜、能量和相位譜為:Fu,v

R2u,v

I

2u,v

Iu,vRu,vu,v

arctan2第37頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月示例

1、編寫(xiě)程序，計(jì)算二維離散傅立葉級(jí)數(shù)

2、討論算法執(zhí)行的時(shí)間第38頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

快速傅里葉變換(FFT)并不是一種新的變換，它是離散傅里葉變換(DFT)的一種算法。這種方法是在分析離散傅里葉變換(DFT)中的多余運(yùn)算的基礎(chǔ)上，進(jìn)而消除這些重復(fù)工作的思想指導(dǎo)下得到的，所以在運(yùn)算中大大節(jié)省了工作量，達(dá)到了快速的目的。4.3

快速傅里葉變換(Fast

FourierTransform)第39頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月§4.3.1

引言

FFT:

Fast

Fourier

Transform

1965年，Cooley-Turky

發(fā)表文章《機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法》，提出FFT算法，解決DFT運(yùn)算量太大，在實(shí)際使用中受限制的問(wèn)題。

FFT的應(yīng)用。頻譜分析、濾波器實(shí)現(xiàn)、實(shí)時(shí)信號(hào)處理等。

DSP芯片實(shí)現(xiàn)。TI公司的TMS

320c30，10MHz時(shí)鐘，基2-FFT1024點(diǎn)FFT時(shí)間15ms。第40頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

IFFTy(n)x(n)

FFTh(n)

FFT

典型應(yīng)用：信號(hào)頻譜計(jì)算、系統(tǒng)分析等頻譜分析與功率譜計(jì)算

DFT系統(tǒng)分析

x(n)

h(n)y(n)第41頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

k0X(k)WN

1N1

knNx(n)

直接計(jì)算DFT的問(wèn)題及改進(jìn)途徑1、

DFT與IDFT

N點(diǎn)有限長(zhǎng)序列x(n)

N1

kn

N

n0第42頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月實(shí)數(shù)乘法實(shí)數(shù)加法一次復(fù)乘42一次復(fù)加2一個(gè)X(k)4N2N+2(N–1)=2(2N–1)N個(gè)X(k)(N點(diǎn)DFT)24N2N(2N–1)IDFT運(yùn)算量與DFT復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)X(k)NN–1N個(gè)X(k)(N點(diǎn)DFT)2NN(N–1)()x

n

W

DFT與IDFT運(yùn)算特點(diǎn)nkNN1n0a

jbc

jd

acbd

jad

cb相同。第43頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月(WN

)WN

nkWNNn)kWN

(Nk)WWWN

NWN

Nnk

*對(duì)稱(chēng)性

nkNW

(Nn)kN

n(Nk)NWW周期性降低DFT運(yùn)算量的考慮

j

nk

nk

NNknk

nNnk

nk

mnk

nk

nk

/mN

mN

N

N

/m

j

j

mnk

N

2

mN

0第44頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月FFT算法分類(lèi):

時(shí)間抽選法

DIT:

Decimation-In-Time

頻率抽選法

DIF:

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

利用DFT系數(shù)的特性，合并DFT運(yùn)算中的某些項(xiàng)，把長(zhǎng)序列DFT

短序列DFT，從而減少其運(yùn)算量。第45頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月)2()(1

r

x

r

x按時(shí)間抽?。―IT）的FFT算法12...，r

0，，，N/21x2(r)

x(2r

1)（Decimation

In

Time）1、算法原理設(shè)序列點(diǎn)數(shù)

N

=

2L，L

為整數(shù)。若不滿(mǎn)足，則補(bǔ)零N為2的整數(shù)冪的FFT算法稱(chēng)基-2FFT算法。將序列x(n)按n的奇偶分成兩組：第46頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

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點(diǎn)DFT定義式分解為兩個(gè)長(zhǎng)度為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第47頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月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第48頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月X(k

2)

X1(k)WN

X2(k)將上式表達(dá)的運(yùn)算用一個(gè)專(zhuān)用“蝶形”信流圖表示。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.

乘法運(yùn)算的支路標(biāo)箭頭和系數(shù)。第49頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月N

82用“蝶形結(jié)”表示上面運(yùn)算的分解：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點(diǎn)

DFT

N

2點(diǎn)

DFT第50頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)N/2點(diǎn)DFT2(N/2)N/2(N/2–1)兩個(gè)N/2點(diǎn)DFT2N/2N(N/2–1)一個(gè)蝶形12N/2個(gè)蝶形N/2N總計(jì)2N/2N/22N/2NN/21N2N/2分解后的運(yùn)算量：運(yùn)算量減少了近一半第51頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月(2l1)

xX1

3(k)WNk/2

4(k)(k)

XX

進(jìn)一步分解

M

N

2DFT又可同樣進(jìn)一步分解為4個(gè)

點(diǎn)的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第52頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月點(diǎn)點(diǎn)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)第53頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月點(diǎn)點(diǎn)點(diǎn)W點(diǎn)....N點(diǎn)DFT分解為四個(gè)N/4點(diǎn)的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)第54頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

類(lèi)似進(jìn)一步分解

類(lèi)似的分解一直繼續(xù)下去，直到分解為最

后的兩類(lèi)蝶形運(yùn)算為止(2點(diǎn)DFT).

如上述N=8=23，N/4=2點(diǎn)中：1點(diǎn)DFTx(0)1點(diǎn)DFTx(4)X3(0)X3(1)

02W第55頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月x(0)WN/4x(4)x(0)WNx(4)x(0)WN/4x(4)x(0)WNx(4)進(jìn)一步簡(jiǎn)化為蝶形流圖：

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

0

01X3(0)

X3(1)因此8點(diǎn)FFT時(shí)間抽取方法的信流圖如下——第56頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月WWWW................

..........

..

..............第三級(jí)x(2)x(6)x(0)

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

0N

0N

0NWN0WN2WN0WN2

第一級(jí)第二級(jí)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)第57頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月FFT運(yùn)算量與運(yùn)算特點(diǎn)1．

N=2L時(shí)，共有L=log2N級(jí)運(yùn)算；每一級(jí)有N/2個(gè)蝶形結(jié)。2．每一級(jí)有N個(gè)數(shù)據(jù)中間數(shù)據(jù)），且每級(jí)只用到本級(jí)的轉(zhuǎn)入中間數(shù)據(jù)，適合于迭代運(yùn)算。3．計(jì)算量：每級(jí)N/2次復(fù)乘法，N次復(fù)加。（每蝶形只乘一次，加減各一次）。共有L*N/2=N/2log2N

次復(fù)乘法；復(fù)加法L*N=Nlog2N

次。與直接DFT定義式運(yùn)算量相比(倍數(shù))

N2/(Nlog2N)

。當(dāng)

N大時(shí)，此倍數(shù)很大。第58頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月()

F

m

DFTN2N2()log

F

m

FFT

N22Nlog2

N

比較DFT可以直觀看出，當(dāng)點(diǎn)數(shù)N越大時(shí)，F(xiàn)FT的優(yōu)點(diǎn)更突出。第59頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月按時(shí)間抽取FFT蝶形運(yùn)算特點(diǎn)1、關(guān)于FFT運(yùn)算的混序與順序處理（位倒序處理）由于輸入序列按時(shí)間序位的奇偶抽取，故輸入序列是混序的，為此需要先進(jìn)行混序處理。混序規(guī)律：

x(n)按n位置進(jìn)行碼位（二進(jìn)制）倒置規(guī)律輸入，而非自然排序，即得到混序排列。所以稱(chēng)為位倒序處理。位倒序?qū)崿F(xiàn)：（1）DSP實(shí)現(xiàn)采用位倒序?qū)ぶ罚?）通用計(jì)算機(jī)實(shí)現(xiàn)可以有兩個(gè)方法：一是嚴(yán)格按照位倒序含義進(jìn)行；二是倒進(jìn)位的加N/2。第60頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月倒位序自然序00000000100410010102201011063011001141001015510101136110111771111x(n)n

(n2nn0)2倒位序第61頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月第62頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月x(n)

nn

，

0,1,2....31計(jì)算。計(jì)算x(13)

13

169x(13)

22

484例問(wèn)倒序前寄存器的數(shù)據(jù)值？

2N

32

點(diǎn)FFT。用時(shí)間抽取輸入倒序算法，x(13)和倒序后

x(13)的數(shù)2N

3225(13)10

(01101)22解：倒序前倒序倒序?yàn)?/p>

(10110)2

(22)10倒序后第63頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月(N

2

)

DIT

FFT中最主要的蝶形運(yùn)算實(shí)現(xiàn)（1）參與蝶形運(yùn)算的兩類(lèi)結(jié)點(diǎn)（信號(hào)）間“距離

”（碼地址）與其所處的第幾級(jí)蝶形有關(guān)；第mL級(jí)的“結(jié)距離”為2m1，m1,2,...L

(即原位計(jì)算迭代）（2）每級(jí)迭形結(jié)構(gòu)為

Xm(k)

Xm1(k)Xm1(k2m1)WNr

第64頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月（3）

WN的確定：

蝶形運(yùn)算兩節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)為k值，表

示成L位二進(jìn)制數(shù)，左移L–

m位，把右邊

空出的位置補(bǔ)零，結(jié)果為r的二進(jìn)制數(shù)。Lmr

(k)2

2

r第m級(jí)的r取值：WN

k第65頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月DIT算法的其他形式流圖輸入倒位序輸出自然序輸入自然序輸出倒位序輸入輸出均自然序相同幾何形狀

–輸入倒位序輸出自然序

–輸入自然序輸出倒位序第66頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月時(shí)間抽取、

輸入自然順序、

輸出倒位序的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第67頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月例用FFT算法處理一幅N×N點(diǎn)的二維圖像，如用每秒可做10萬(wàn)次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)N=1024時(shí)，問(wèn)需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？

解

當(dāng)N=1024點(diǎn)時(shí)，F(xiàn)FT算法處理一幅二維圖像所需復(fù)數(shù)乘法約為分之一。

即原需要3000小時(shí)，現(xiàn)在只需要2

分鐘。log2

N2

107

次，僅為直接計(jì)算DFT所需時(shí)間的10萬(wàn)N2

2第68頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月e

y0

f

x,yeF(x,v)

N

x04.4.1可分離性（Separability）4.4

傅里葉變換的性質(zhì)(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行求傅里葉變換再對(duì)F第69頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月4.4

傅里葉變換的性質(zhì)(Characteristics

of

Fourier

Transform)可分離性（Divisibility）

F(x,?v)

圖4.5

由2步1-D變換計(jì)算2-D變換第70頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

u0

v0

F(u,v)eeFu,ve

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

u0N1

v0

1Nfx,yj2vy/Nj2ux/N4.4

傅里葉變換的性質(zhì)(Characteristics

of

Fourier

Transform)第71頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月4.4

傅里葉變換的性質(zhì)(Characteristics

of

Fourier

Transform)4.4.2平移性質(zhì)（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

與一個(gè)指數(shù)相乘等于將變換后的頻率域中心移到新的位置。f

x,y的平移將不改變頻譜的幅值（amplitude）。第72頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月4.4

傅里葉變換的性質(zhì)(Characteristics

of

Fourier

Transform)4.4.3周期性和共軛對(duì)稱(chēng)性（Periodicity

and

Conjugate

Symmetry）

傅里葉變換和反變換均以N為周期，即

Fu,v

Fu

N,v

Fu,v

N

Fu

N,v

N

（4.29）

上式可通過(guò)將右邊幾項(xiàng)分別代入式（4.16）來(lái)驗(yàn)證。它表明，盡管

Fu,v有無(wú)窮多個(gè)u和v的值重復(fù)出現(xiàn)，但只需根據(jù)在任一個(gè)周期里的N個(gè)值就可以從Fu,v得到

fx,

y。第73頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月頻譜的周期性F(u,v)

F(uM,vN)第74頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月第75頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月共軛對(duì)成性（4.30）（4.31）

4.4

傅里葉變換的性質(zhì)(Characteristics

of

Fourier

Transform)如果fx,y是實(shí)函數(shù)，則它的傅里葉變換具有Fu,v

F

u,v

Fu,v

F

u,v第76頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月4.4

傅里葉變換的性質(zhì)(Characteristics

of

Fourier

Transform)4.4.4旋轉(zhuǎn)性質(zhì)（Rotation）

f(x,y)

Fu,vx

rcosy

rsinu

wcosv

wsin

f(r,

0)

F(w,

0)上式表明，對(duì)

f(x,y)

旋轉(zhuǎn)一個(gè)角度

0

F(u,v)

對(duì)應(yīng)于將其傅里葉變換也旋轉(zhuǎn)相同的角度

0第77頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月例4.4二維離散傅立葉變換的旋轉(zhuǎn)性（具體程序參見(jiàn)書(shū)）。（a）原始圖像（b）原圖像的傅（c）旋轉(zhuǎn)后的圖像（d）旋轉(zhuǎn)后圖像的傅里葉頻譜4.4

傅里葉變換的性質(zhì)(Characteristics

of

Fourier

Transform)

里葉頻譜

上例表明，對(duì)

fx,

y旋轉(zhuǎn)一個(gè)角度0對(duì)應(yīng)于將其傅里葉變換Fu,v也旋轉(zhuǎn)相同的角度0。第78頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月分配律(Distribution

Law)

根據(jù)傅里葉變換對(duì)的定義可得到：（4.33）4.4

傅里葉變換的性質(zhì)(Characteristics

of

Fourier

Transform)f1x,

y

f2x,

y

f1x,

yf2x,

y

上式表明傅里葉變換和反變換對(duì)加法滿(mǎn)足分配律，

但需注意對(duì)乘法則不滿(mǎn)足，一般有：f1x,

y

f2x,

y

f1x,

yf2x,

y（4.34）4.4.5分配律（Distribution

Law）第79頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月F

,

4.4

傅里葉變換的性質(zhì)(Characteristics

of

Fourier

Transform)4.4.6尺度變換（Scaling）

afx,

y

aFu,v

u

v

a

b

1abfax,by第80頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

4.4

傅里葉變換的性質(zhì)(Characteristics

of

Fourier

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

（b）比例尺度展寬前的頻譜（c）比例尺度a=0.1，b=1，展寬后的頻譜第81頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月

fx,

y

fx,

ye

Nfx,

y對(duì)一個(gè)2-D離散函數(shù)，其平均值可用下式表示：（4.37）4.4

傅里葉變換的性質(zhì)(Characteristics

of

Fourier

Transform)N

1N

1

x0

y0

1N

2f

(x,

y)

當(dāng)正反變換采用相同的標(biāo)度數(shù)1/

N時(shí)，傅里葉變換域原點(diǎ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）第82頁(yè)，課件共119頁(yè)，創(chuàng)作于2023年2月（4.39）

4.4

傅里葉變換的性質(zhì)(Characteristics

of

Fourier

Transform)兩式比較可得：F0,0

1Nf

(x,

y)

也就是說(shuō)，頻譜的直流成分

N倍于圖像平面的亮度平均值。在使用諸如高通濾波器的場(chǎng)合，其

F0,0值會(huì)衰減，因?yàn)閳D像的亮度在很大程度上受到影響，采用對(duì)比度拉伸的方法可以緩和這種衰減。第83頁(yè)，課件共11