課06(2.1-2.2_二維卷積與DFT).

1、2. .1 離散卷積與離散相關(guān)離散卷積與離散相關(guān)2. .2 二維離散傅里葉變換（二維離散傅里葉變換（2D-DFT）2. .3 離散沃爾什變換（離散沃爾什變換（DWT）2.1.1 二維離散卷積二維離散卷積 2.1.2 二維離散卷積定理二維離散卷積定理 2.1.3 二維離散相關(guān)二維離散相關(guān) 2.2.1 定義與討論定義與討論 2.2.2 矢量矩陣表示矢量矩陣表示 2.2.3 傅里葉變換是酉變換傅里葉變換是酉變換 2.2.4 常用性質(zhì)常用性質(zhì) 2.3.1 離散沃爾什函數(shù)離散沃爾什函數(shù) 2.3.2 一維一維DWT2.3.3 二維二維DWT 2.6.1 奇數(shù)點(diǎn)的奇數(shù)點(diǎn)的CosineCosine變換變換2.

2、 .4 離散哈達(dá)瑪變換（離散哈達(dá)瑪變換（DHT）2. .5 離散卡離散卡- -洛變換（洛變換（DKLT） 2.4.1 哈達(dá)瑪矩陣哈達(dá)瑪矩陣 2.4.2 一維一維DHT 2.4.3 二維二維DHT 2.5.1 一維連續(xù)一維連續(xù)K-L展開展開 2.5.2 一維離散一維離散KLT 2.5.3 一維離散一維離散KLT T2. .6 離散余弦變換（離散余弦變換（DCT） 2.6.1 偶數(shù)點(diǎn)的偶數(shù)點(diǎn)的CosineCosine變換變換 2.6.3 DCT的性能的性能 2.1.1 二維離散卷積二維離散卷積 2.1.2 離散卷積定理離散卷積定理v 定義定義v 對卷積矩陣對卷積矩陣Te的討論的討論v 小結(jié)小結(jié) 2

3、.1.3 二維離散相關(guān)二維離散相關(guān)v 定義定義v 二維離散相關(guān)定理與性質(zhì)二維離散相關(guān)定理與性質(zhì)返回返回v 定義定義定義二維離散卷積定義二維離散卷積：10; 10),(ByAxyxf10; 10),(DyCxyxg( ( 個(gè)樣本值個(gè)樣本值) )BA( ( 個(gè)樣本值個(gè)樣本值) )DC),(),(),(),(1010nymxgnmfyxgyxfeMmNneee) 1, 2 , 1 , 0; 1, 2 , 1 , 0(NyMx設(shè)兩個(gè)二維離散函數(shù)設(shè)兩個(gè)二維離散函數(shù)：式中式中， 與與 分別是分別是 、 的周期化函數(shù)的周期化函數(shù)。),(yxfe),(yxge),(yxf),(yxg上頁上頁110; 1; 1

4、0,0),(),(NyDDyMxCCxyxgyxge上頁上頁即即： 和和 的周期為的周期為：),(yxfe),(yxge定義所給出的定義所給出的 階函數(shù)陣列階函數(shù)陣列，是二維離散卷積的一個(gè)周期是二維離散卷積的一個(gè)周期。NM 110; 1; 10,0),(),(NyBByMxAAxyxfyxfe110; 1; 10,0),(),(NyBByMxAAxyxfyxfe 例題例題 求兩個(gè)求兩個(gè)22 階二維離散函數(shù)的卷積階二維離散函數(shù)的卷積：224321F222211G 解法一（解析法）解法一（解析法）33000043021eF33000022011eG (2) 求求 F和和G 的列矢量（按行掃描的列矢

5、量（按行掃描- -堆疊方式）堆疊方式）：Te0, 0, 0, 0, 2, 2, 0, 1, 1gTe0, 0, 0, 0, 4, 3, 0, 2, 1f上頁上頁 (1) F和和G周期化周期化： 周期周期 M = N =A+B-1=3卷積矩陣卷積矩陣 eT(3) 按一維離散卷積方法計(jì)算卷積按一維離散卷積方法計(jì)算卷積： 上頁上頁826835211000043021110220000011022000001102200000110220000011022200001102220000110022000011102200001eeefTy(4) 卷積結(jié)果卷積結(jié)果( (矩陣形式矩陣形式) )：82683

6、5211eYl Te為為 階方陣階方陣；22MM l 有有 個(gè)分塊子陣每個(gè)子陣為個(gè)分塊子陣每個(gè)子陣為 階階；MM MM 上頁上頁l 共有共有 M 組相同的子陣組相同的子陣。22110220000011022000001102200000110220000011022200001102220000110022000011102200001MMeT 其中其中卷積矩陣卷積矩陣：110220000011022000001102200000110220000011022200001102220000110022000011102200001eT其中，分塊子陣其中，分塊子陣：1100111011eT220

7、0222022eT0000000003eT10 02 22 210 00 012 20,0,0,0,4,3,0,2, 1Tefv 對卷積矩陣的進(jìn)一步討論對卷積矩陣的進(jìn)一步討論上頁上頁 箭頭所指各列與 fe 的零元素相乘，因此，可改動相關(guān)元素值，使每個(gè)分塊子陣均成為循環(huán)矩陣。小結(jié)：小結(jié)：Te 為分塊循環(huán)矩陣，其中各列（行）是分塊子陣的循環(huán)移位為分塊循環(huán)矩陣，其中各列（行）是分塊子陣的循環(huán)移位； 各分塊子陣是由各分塊子陣是由 g e子矢量諸元素構(gòu)成的循環(huán)矩陣。子矢量諸元素構(gòu)成的循環(huán)矩陣。上頁上頁TeeeTe3210, 0, 0, 0, 2, 2, 0, 1, 1gggg0111eg0222eg00

8、03eg本例本例：其中各子矢量為其中各子矢量為：返回返回224321F222211G1-22-12-11-2-21-121-22-1xy0(2) 垂直垂直/ /水平折疊水平折疊1234(1) 將將F和和G表示成表示成“掩模掩?！毙问叫问?解法二（圖解法）解法二（圖解法）上頁上頁123-2142-11) 1(111y322y833y2342-211-1 (3) 水平水平/ /垂直平移折疊后的掩模，求乘積和垂直平移折疊后的掩模，求乘積和24-21-1231342-212-1112) 1(1112y422-23-111521y42-2-1213122113y上頁上頁),(),(vuFyxfe),()

9、,(vuGyxge 二維二維 若二維離散函數(shù)的傅里葉變換對為若二維離散函數(shù)的傅里葉變換對為則有則有)()()()(uGuFxgxfee)()()()(uGuFxgxfee則有則有),(),(),(),(vuGvuFyxgyxfee),(),(),(),(vuGvuFyxgyxfee),()(uFxfe)()(uGxge 一維一維 若離散函數(shù)若離散函數(shù) 、 的傅里葉變換分別為的傅里葉變換分別為 、 ，即即)(xf)(xg)(uF)(uG上頁上頁定義二維離散相關(guān)定義二維離散相關(guān)：1, 2 , 1 , 0; 1, 2 , 1 , 0),(ByAxyxf1, 2 , 1 , 0; 1, 2 , 1 ,

10、 0),(DyCxyxg),(),(),(),(),(1010ynxmgnmfyxgyxfyxReMmNneeefg) 1, 2 , 1 , 0; 1, 2 , 1 , 0(NyMx以及以及),(),(),(),(),(1010ynxmfnmgyxfyxgyxReMmNneeegf) 1, 2 , 1 , 0; 1, 2 , 1 , 0(NyMxv 定義定義 對兩個(gè)二維離散實(shí)函數(shù)對兩個(gè)二維離散實(shí)函數(shù)： 上頁上頁則則),(),(),(),(vuGvuFyxgyxfee),(),(),(),(vuGvuFyxgyxfee,),(),(vuFyxfe),(),(vuGyxgev 二維相關(guān)定理二維相關(guān)

11、定理若若自相關(guān)函數(shù)自相關(guān)函數(shù)：),(),(),(),(),(1010ynxmfnmfyxfyxfyxReMmNneeeff) 1, 2 , 1 , 0; 1, 2 , 1 , 0(NyMxv 自相關(guān)函數(shù)及其性質(zhì)自相關(guān)函數(shù)及其性質(zhì)上頁上頁當(dāng)當(dāng) 時(shí)時(shí)，0 x自相關(guān)函數(shù)的傅氏變換自相關(guān)函數(shù)的傅氏變換： 2.2.1 定義與討論定義與討論 2.2.2 矩陣矢量表示矩陣矢量表示 2.2.3 傅里葉變換是酉變換傅里葉變換是酉變換下頁下頁 2.2.4 常用性質(zhì)常用性質(zhì) 設(shè)二維數(shù)據(jù)陣列設(shè)二維數(shù)據(jù)陣列 f (x,y)為為 NN 方陣方陣, , 定義定義2D- -DFT： 1010)(2),(1),(NxNyvyu

12、xNjeyxfNvuF) 1, 1 , 0,(Nvu1010)(2),(1),(NuNvvyuxNjevuFNyxf) 1, 1 , 0,(Nyx 反變換：反變換：F(u, v)也是也是 NN 方陣方陣。 正變換：正變換：v 2 2D-DFTD-DFT定義定義上頁上頁上頁上頁 ),( vuF列N -1012N -112Muv行 ),(yxf列N -1012N -112Mxy行),(),(vuFyxf變換對變換對：v 討論討論 變量說明變量說明：x, y 離散圖像像素點(diǎn)在空間的行、列位置標(biāo)號；離散圖像像素點(diǎn)在空間的行、列位置標(biāo)號；u, v 表示變換域中樣點(diǎn)行、列位置標(biāo)號表示變換域中樣點(diǎn)行、列位置

13、標(biāo)號。 上頁上頁記記NjeW2 其中，正變換核其中，正變換核：)(1vyuxWN)(1vyuxWN 變換核變換核： 可分離性可分離性：行分量列分量),(),(uxAvyARC)(21),;,(vyuxNjeNvuyxA 令令，則，則DFT的變換核為的變換核為；反變換核反變換核：),(uxARuxNjeN21),(vyAC,12vyNjeN 其中其中：改寫正變換公式改寫正變換公式：兩次一維變換),(),(vxFyxfvy先作列運(yùn)算),(vyAC),(uxAR先作行運(yùn)算 xu),(yuF101010101022),(),(),(),(),(1),(1),(NxRNxNyCRNxNyvyNjuxNj

14、uxAvxFvyAyxfuxANeyxfeNvuF 一個(gè)二維一個(gè)二維DFT，可連續(xù)運(yùn)用兩次一維，可連續(xù)運(yùn)用兩次一維DFT來實(shí)現(xiàn)，因而，來實(shí)現(xiàn)，因而，可采用一維可采用一維FFT進(jìn)行快速運(yùn)算進(jìn)行快速運(yùn)算。示意如下：示意如下： 結(jié)論結(jié)論 ),( vuFux再作行運(yùn)算再作列運(yùn)算 yv返回目錄返回目錄則則 DFT的矢量形式為的矢量形式為：v DFT的矢量表示的矢量表示 正變換正變換Afq A變換矩陣變換矩陣其中其中：頻率域矩陣為頻率域矩陣為 Q ( (列列) )矢量為矢量為 q設(shè)圖像空間域矩陣為設(shè)圖像空間域矩陣為 F ( (列列) )矢量為矢量為 f對應(yīng)對應(yīng)Bqf 反變換反變換B反變換矩陣反變換矩陣其中

15、其中：1 AB上頁上頁 舉例舉例 設(shè)空域矩陣設(shè)空域矩陣F與頻域矩陣與頻域矩陣Q分別為分別為：Tffff,11100100fTqqqq,11100100q相應(yīng)的列矢量為相應(yīng)的列矢量為：2211100100ffffF2211100100qqqqQv 對變換矩陣對變換矩陣A的討論的討論 （舉例舉例 推廣）推廣），上頁上頁問題問題：A=? 為此，可根據(jù)定義式分別求相應(yīng)的變換系數(shù)為此，可根據(jù)定義式分別求相應(yīng)的變換系數(shù)。由由DFT變換式變換式fq A)(11011010001000)00(101000WfWfWfWfNWfNqyxxyxy)(11111010101000)0(101001WfWfWfWfN

16、WfNqyxxyxy)(11111110001000)0(101010WfWfWfWfNWfNqyxxyxy)(11211110101000)(101011WfWfWfWfNWfNqyxxyxy, 1, 1vu, 1, 0vu, 0, 0vu, 0, 1vu由正變換定義式可得由正變換定義式可得：式中式中：NjeW2上頁上頁變換矩陣變換矩陣AAfq111001002110110010100000111001001ffffWWWWWWWWWWWWWWWWNqqqq上頁上頁將以上方程組寫成矩陣形式將以上方程組寫成矩陣形式： 進(jìn)一步進(jìn)一步改寫變換矩陣改寫變換矩陣：) 1(0W1000110000100

17、001000011WWWWWWWWWWWWWWWWWWWWNNA即即A的的行、列是可分離的行、列是可分離的上頁上頁令令 ，10001WWWWNRCAA 推廣推廣 一般地，變換矩陣一般地，變換矩陣A的行、列分量為的行、列分量為222)1()1(210121000001NNNNNNRCWWWWWWWWWWWWNMMMMAA顯然存在關(guān)系顯然存在關(guān)系： CTCAARTRAA直積直積：則則A可表為可表為AC與與AR的的l 正變換正變換：l 反變換反變換：等式兩邊左乘等式兩邊左乘 ，右乘，右乘 1CA1RAv DFT的矩陣表示的矩陣表示2 2階階DFT的矩陣形式可表示為的矩陣形式可表示為：10001110

18、010010001110010011WWWWNffffWWWWNqqqq 得到得到：RCFAAQ 11RCQAAF返回目錄返回目錄 對于變換矩陣對于變換矩陣T，酉變換酉變換滿足以下條件：滿足以下條件：T-1 = ( T* ) T即即T的逆為的逆為T的共軛轉(zhuǎn)置，這時(shí)稱的共軛轉(zhuǎn)置，這時(shí)稱T為為“酉矩陣酉矩陣”。當(dāng)。當(dāng)T為實(shí)酉矩陣時(shí)，為實(shí)酉矩陣時(shí)，則為正交矩陣。正交矩陣中各行（列）矢量是正交歸一的，即則為正交矩陣。正交矩陣中各行（列）矢量是正交歸一的，即 T-1 T = ( T* ) T T = I TT-1 = T ( T* ) T = I上頁上頁酉變換是普遍意義上的線性正交變換，而且是可逆的。酉

19、變換是普遍意義上的線性正交變換，而且是可逆的。v 何謂酉變換？何謂酉變換？對于對于DFT，若能證明變換矩陣，若能證明變換矩陣A滿足滿足T)(1 AA 則則A是酉矩陣是酉矩陣，進(jìn)而，進(jìn)而DFT是酉變換。是酉變換。上頁上頁222)1()1(2)1(0)1(2100000111NNNNNNRCWWWWWWWWWWWWNMMMMAA其逆矩陣為其逆矩陣為222)1()1(210121000001NNNNNNRCWWWWWWWWWWWWNMMMMAA 已知已知DFT變換矩陣變換矩陣A的行、列分量為的行、列分量為TCC)(1 AATRR)(1 AA比較顯見比較顯見： 由于由于 ,所以所以RCAAAT)(1

20、AA 即即DFT正變換矩陣正變換矩陣A是酉矩陣是酉矩陣。 結(jié)論結(jié)論 傅里葉變換是酉變換（正交變換）傅里葉變換是酉變換（正交變換）。因而逆變換矩陣因而逆變換矩陣B也是酉矩陣也是酉矩陣。TTT)()()(111BAAAB根據(jù)根據(jù) 有有,1 AB故逆變換核同樣是可分離的。故逆變換核同樣是可分離的。且因且因RCRCRCBBAAA(AAB1111)1CCAB1RRAB進(jìn)一步進(jìn)一步返回目錄返回目錄上頁上頁可得可得 ),(),(vuFnNvmNuF因此，因此，F(xiàn) (u,v)和和 f (x, y)均具有周期性，周期為均具有周期性，周期為NN。),(),(yxfnNymNxf)(2)(2)(2)()(2vyux

21、NjnymxjvyuxNjynNvxmNuNjeeee根據(jù)根據(jù)DFT定義和復(fù)指數(shù)函數(shù)的周期性定義和復(fù)指數(shù)函數(shù)的周期性：同理，反變換同理，反變換v 周期性周期性上頁上頁與一維與一維DFT類似，在求類似，在求 f (x, y)二維二維DFT時(shí)，意味著在空間域和頻時(shí)，意味著在空間域和頻率域兩方面都周期化了率域兩方面都周期化了。f (x, y)和和F (u, v)的的 NN 個(gè)樣本，均表個(gè)樣本，均表示二維周期函數(shù)的一個(gè)周期。因此，欲了解示二維周期函數(shù)的一個(gè)周期。因此，欲了解F (u, v)的全貌，只需的全貌，只需一個(gè)完整的周期即可。一個(gè)完整的周期即可。二維二維DFT也具有也具有“循環(huán)循環(huán)”特性，如循環(huán)空特性，如循環(huán)空間位移，循環(huán)卷積等。間位移，循環(huán)卷積等。 結(jié)論結(jié)論 上頁上頁 由周期