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

1、2. .1 離散卷積與離散相關離散卷積與離散相關2. .2 二維離散傅里葉變換（二維離散傅里葉變換（2D-DFT）2. .3 離散沃爾什變換（離散沃爾什變換（DWT）2.1.1 二維離散卷積二維離散卷積 2.1.2 二維離散卷積定理二維離散卷積定理 2.1.3 二維離散相關二維離散相關 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ù)點的奇數(shù)點的CosineCosine變換變換2.

2、 .4 離散哈達瑪變換（離散哈達瑪變換（DHT）2. .5 離散卡離散卡- -洛變換（洛變換（DKLT） 2.4.1 哈達瑪矩陣哈達瑪矩陣 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ù)點的偶數(shù)點的CosineCosine變換變換 2.6.3 DCT的性能的性能 2.1.1 二維離散卷積二維離散卷積 2.1.2 離散卷積定理離散卷積定理v 定義定義v 對卷積矩陣對卷積矩陣Te的討論的討論v 小結小結 2

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

4、10,0),(),(NyDDyMxCCxyxgyxge上頁上頁即即： 和和 的周期為的周期為：),(yxfe),(yxge定義所給出的定義所給出的 階函數(shù)陣列階函數(shù)陣列，是二維離散卷積的一個周期是二維離散卷積的一個周期。NM 110; 1; 10,0),(),(NyBByMxAAxyxfyxfe110; 1; 10,0),(),(NyBByMxAAxyxfyxfe 例題例題 求兩個求兩個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) 按一維離散卷積方法計算卷積按一維離散卷積方法計算卷積： 上頁上頁826835211000043021110220000011022000001102200000110220000011022200001102220000110022000011102200001eeefTy(4) 卷積結果卷積結果( (矩陣形式矩陣形式) )：8268

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

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

8、0003eg本例本例：其中各子矢量為其中各子矢量為：返回返回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上頁上頁定義二維離散相關定義二維離散相關：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 定義定義 對兩個二維離散實函數(shù)對兩個二維離散實函數(shù)： 上頁上頁則則),(),(),(),(vuGvuFyxgyxfee),(),(),(),(vuGvuFyxgyxfee,),(),(vuFyxfe),(),(vuGyxgev 二維相關定理二維

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

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

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

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

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

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

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

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

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

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

21、jnymxjvyuxNjynNvxmNuNjeeee根據(jù)根據(jù)DFT定義和復指數(shù)函數(shù)的周期性定義和復指數(shù)函數(shù)的周期性：同理，反變換同理，反變換v 周期性周期性上頁上頁與一維與一維DFT類似，在求類似，在求 f (x, y)二維二維DFT時，意味著在空間域和頻時，意味著在空間域和頻率域兩方面都周期化了率域兩方面都周期化了。f (x, y)和和F (u, v)的的 NN 個樣本，均表個樣本，均表示二維周期函數(shù)的一個周期。因此，欲了解示二維周期函數(shù)的一個周期。因此，欲了解F (u, v)的全貌，只需的全貌，只需一個完整的周期即可。一個完整的周期即可。二維二維DFT也具有也具有“循環(huán)循環(huán)”特性，如循環(huán)空特性，如循環(huán)空間位移，循環(huán)卷積等。間位移，循環(huán)卷積等。 結論結論 上頁上頁 由周期性由周期性：1010)(2),(1),(),(NxNyvyuxNjeyxfNvuFnNvmNuF作變量代換作變量代換 u u， v v，并取，并取共軛共軛： 可得可得：),(),(vuFnNvmNuF),(nNvmNuF 等式左邊等式左邊：)(2)(2vyuxNjvyuxNjee 等式右邊（觀察指