课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 常用性质常用性质 2.3.1 离散沃尔什函数离散沃尔什函数 2.3.2 一维一维DWT2.3.3 二维二维DWT 2.6.1 奇数点的奇数点的CosineCosine变换变换2.

2、 .4 离散哈达玛变换（离散哈达玛变换（DHT）2. .5 离散卡离散卡- -洛变换（洛变换（DKLT） 2.4.1 哈达玛矩阵哈达玛矩阵 2.4.2 一维一维DHT 2.4.3 二维二维DHT 2.5.1 一维连续一维连续K-L展开展开 2.5.2 一维离散一维离散KLT 2.5.3 一维离散一维离散KLT T2. .6 离散余弦变换（离散余弦变换（DCT） 2.6.1 偶数点的偶数点的CosineCosine变换变换 2.6.3 DCT的性能的性能 2.1.1 二维离散卷积二维离散卷积 2.1.2 离散卷积定理离散卷积定理v 定义定义v 对卷积矩阵对卷积矩阵Te的讨论的讨论v 小结小结 2

3、.1.3 二维离散相关二维离散相关v 定义定义v 二维离散相关定理与性质二维离散相关定理与性质返回返回v 定义定义定义二维离散卷积定义二维离散卷积：10; 10),(ByAxyxf10; 10),(DyCxyxg( ( 个样本值个样本值) )BA( ( 个样本值个样本值) )DC),(),(),(),(1010nymxgnmfyxgyxfeMmNneee) 1, 2 , 1 , 0; 1, 2 , 1 , 0(NyMx设两个二维离散函数设两个二维离散函数：式中式中， 与与 分别是分别是 、 的周期化函数的周期化函数。),(yxfe),(yxge),(yxf),(yxg上页上页110; 1; 1

4、0,0),(),(NyDDyMxCCxyxgyxge上页上页即即： 和和 的周期为的周期为：),(yxfe),(yxge定义所给出的定义所给出的 阶函数阵列阶函数阵列，是二维离散卷积的一个周期是二维离散卷积的一个周期。NM 110; 1; 10,0),(),(NyBByMxAAxyxfyxfe110; 1; 10,0),(),(NyBByMxAAxyxfyxfe 例题例题 求两个求两个22 阶二维离散函数的卷积阶二维离散函数的卷积：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) 卷积结果卷积结果( (矩阵形式矩阵形式) )：82683

6、5211eYl Te为为 阶方阵阶方阵；22MM l 有有 个分块子阵每个子阵为个分块子阵每个子阵为 阶阶；MM MM 上页上页l 共有共有 M 组相同的子阵组相同的子阵。22110220000011022000001102200000110220000011022200001102220000110022000011102200001MMeT 其中其中卷积矩阵卷积矩阵：110220000011022000001102200000110220000011022200001102220000110022000011102200001eT其中，分块子阵其中，分块子阵：1100111011eT220

7、0222022eT0000000003eT10 02 22 210 00 012 20,0,0,0,4,3,0,2, 1Tefv 对卷积矩阵的进一步讨论对卷积矩阵的进一步讨论上页上页 箭头所指各列与 fe 的零元素相乘，因此，可改动相关元素值，使每个分块子阵均成为循环矩阵。小结：小结：Te 为分块循环矩阵，其中各列（行）是分块子阵的循环移位为分块循环矩阵，其中各列（行）是分块子阵的循环移位； 各分块子阵是由各分块子阵是由 g e子矢量诸元素构成的循环矩阵。子矢量诸元素构成的循环矩阵。上页上页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 二维二维 若二维离散函数的傅里叶变换对为若二维离散函数的傅里叶变换对为则有则有)()()()(uGuFxgxfee)()()()(uGuFxgxfee则有则有),(),(),(),(vuGvuFyxgyxfee),(),(),(),(vuGvuFyxgyxfee),()(uFxfe)()(uGxge 一维一维 若离散函数若离散函数 、 的傅里叶变换分别为的傅里叶变换分别为 、 ，即即)(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 定义定义 对两个二维离散实函数对两个二维离散实函数： 上页上页则则),(),(),(),(vuGvuFyxgyxfee),(),(),(),(vuGvuFyxgyxfee,),(),(vuFyxfe),(),(vuGyxgev 二维相关定理二维相关

11、定理若若自相关函数自相关函数：),(),(),(),(),(1010ynxmfnmfyxfyxfyxReMmNneeeff) 1, 2 , 1 , 0; 1, 2 , 1 , 0(NyMxv 自相关函数及其性质自相关函数及其性质上页上页当当 时时，0 x自相关函数的傅氏变换自相关函数的傅氏变换： 2.2.1 定义与讨论定义与讨论 2.2.2 矩阵矢量表示矩阵矢量表示 2.2.3 傅里叶变换是酉变换傅里叶变换是酉变换下页下页 2.2.4 常用性质常用性质 设二维数据阵列设二维数据阵列 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 离散图像像素点在空间的行、列位置标号；离散图像像素点在空间的行、列位置标号；u, v 表示变换域中样点行、列位置标号表示变换域中样点行、列位置

13、标号。 上页上页记记NjeW2 其中，正变换核其中，正变换核：)(1vyuxWN)(1vyuxWN 变换核变换核： 可分离性可分离性：行分量列分量),(),(uxAvyARC)(21),;,(vyuxNjeNvuyxA 令令，则，则DFT的变换核为的变换核为；反变换核反变换核：),(uxARuxNjeN21),(vyAC,12vyNjeN 其中其中：改写正变换公式改写正变换公式：两次一维变换),(),(vxFyxfvy先作列运算),(vyAC),(uxAR先作行运算 xu),(yuF101010101022),(),(),(),(),(1),(1),(NxRNxNyCRNxNyvyNjuxNj

14、uxAvxFvyAyxfuxANeyxfeNvuF 一个二维一个二维DFT，可连续运用两次一维，可连续运用两次一维DFT来实现，因而，来实现，因而，可采用一维可采用一维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=? 为此，可根据定义式分别求相应的变换系数为此，可根据定义式分别求相应的变换系数。由由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上页上页将以上方程组写成矩阵形式将以上方程组写成矩阵形式： 进一步进一步改写变换矩阵改写变换矩阵：) 1(0W1000110000100

17、001000011WWWWWWWWWWWWWWWWWWWWNNA即即A的的行、列是可分离的行、列是可分离的上页上页令令 ，10001WWWWNRCAA 推广推广 一般地，变换矩阵一般地，变换矩阵A的行、列分量为的行、列分量为222)1()1(210121000001NNNNNNRCWWWWWWWWWWWWNMMMMAA显然存在关系显然存在关系： CTCAARTRAA直积直积：则则A可表为可表为AC与与AR的的l 正变换正变换：l 反变换反变换：等式两边左乘等式两边左乘 ，右乘，右乘 1CA1RAv DFT的矩阵表示的矩阵表示2 2阶阶DFT的矩阵形式可表示为的矩阵形式可表示为：10001110

18、010010001110010011WWWWNffffWWWWNqqqq 得到得到：RCFAAQ 11RCQAAF返回目录返回目录 对于变换矩阵对于变换矩阵T，酉变换酉变换满足以下条件：满足以下条件：T-1 = ( T* ) T即即T的逆为的逆为T的共轭转置，这时称的共轭转置，这时称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

20、AA 即即DFT正变换矩阵正变换矩阵A是酉矩阵是酉矩阵。 结论结论 傅里叶变换是酉变换（正交变换）傅里叶变换是酉变换（正交变换）。因而逆变换矩阵因而逆变换矩阵B也是酉矩阵也是酉矩阵。TTT)()()(111BAAAB根据根据 有有,1 AB故逆变换核同样是可分离的。故逆变换核同样是可分离的。且因且因RCRCRCBBAAA(AAB1111)1CCAB1RRAB进一步进一步返回目录返回目录上页上页可得可得 ),(),(vuFnNvmNuF因此，因此，F (u,v)和和 f (x, y)均具有周期性，周期为均具有周期性，周期为NN。),(),(yxfnNymNxf)(2)(2)(2)()(2vyux

21、NjnymxjvyuxNjynNvxmNuNjeeee根据根据DFT定义和复指数函数的周期性定义和复指数函数的周期性：同理，反变换同理，反变换v 周期性周期性上页上页与一维与一维DFT类似，在求类似，在求 f (x, y)二维二维DFT时，意味着在空间域和频时，意味着在空间域和频率域两方面都周期化了率域两方面都周期化了。f (x, y)和和F (u, v)的的 NN 个样本，均表个样本，均表示二维周期函数的一个周期。因此，欲了解示二维周期函数的一个周期。因此，欲了解F (u, v)的全貌，只需的全貌，只需一个完整的周期即可。一个完整的周期即可。二维二维DFT也具有也具有“循环循环”特性，如循环空特性，如循环空间位移，循环卷积等。间位移，循环卷积等。 结论结论 上页上页 由周期