《数字图像总复习第3章》由会员分享，可在线阅读，更多相关《数字图像总复习第3章（150页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章 图象变换图象变换3.1 概述和分类概述和分类3.2 傅里叶变换傅里叶变换3.3 快速傅里叶变换快速傅里叶变换3.4 其它可分离图象变换其它可分离图象变换3.5 霍特林变换霍特林变换第第三三章章 图图象象变变换换1第一节第一节 概述和分类概述和分类为为了了有有效效地地和和快快速速地地对对图图象象进进行行处处理理和和分分析析常常常常需需要要将将原原定定义义在在图图象象空空间间的的图图象象以以某某种种形形式式转转换换到到另另外外一一些些空空间间，并并利利用用在在这这些些空空间间的的特特有有性性质质方方便便地地进进行行一一定定的的加加工工, ,最最后后再再转转换换回回图象空间以得到所需的
2、效果。图象空间以得到所需的效果。这这些些转转换换方方法法就就是是本本章章要要着着重重介介绍绍和和讨讨论论的的图图象变换技术。象变换技术。第第三三章章 图图象象变变换换2图象为什么要变换图象为什么要变换利用变换的某些性质，可以大大简化或加速图象处理过利用变换的某些性质，可以大大简化或加速图象处理过程程空域图象经过变换后形成空域图象经过变换后形成 “ “对应域图象对应域图象”，从中会看到，从中会看到在空域图象中不易看到的某些在空域图象中不易看到的某些“东西东西”。变换后形成变换后形成 “ “对应域图象对应域图象”，会呈现某些性态，利用这，会呈现某些性态，利用这些性态可完成图象处理中某个应用领域的应
3、用。些性态可完成图象处理中某个应用领域的应用。 应选择什么样的变换才能满足各种要求是下面要讨论应选择什么样的变换才能满足各种要求是下面要讨论的主要问题之一。的主要问题之一。3变换选择的原则变换选择的原则1)1)变换必须是可逆的。变换必须是可逆的。2)2)变换不能损失信息。变换不能损失信息。3)3)变换必须是有好处的。变换必须是有好处的。4)4)变换算法必须是不复杂的。变换算法必须是不复杂的。 4第一节第一节 概述和分类概述和分类图象变换是许多图象处理和分析技术的基础，图象变换是许多图象处理和分析技术的基础，本章的主要目的是建立起图象变换及其性质的本章的主要目的是建立起图象变换及其性质的理论基础
4、。把傅里叶变换放在主要地位反映了理论基础。把傅里叶变换放在主要地位反映了它在图象处理问题中应用的广泛性。它在图象处理问题中应用的广泛性。对图象进行变换的目的：对图象进行变换的目的：为为了了便便于于对对图图象象进进行行分分析析，如如对对图图象象进进行行特特征征提提取取、匹配、识别；匹配、识别；为为了了便便于于对对图图象象进进行行处处理理，如如简简化化处处理理操操作作、提提高高运算效率；运算效率；为了便于对图象数据进行压缩，提高传输效率等为了便于对图象数据进行压缩，提高传输效率等第第三三章章 图图象象变变换换5第一节第一节 概述和分类概述和分类图像变换的一种分类方法：图像变换的一种分类方法：可分离
5、变换：可分离变换： 傅里叶变换及性质傅里叶变换及性质 快速傅里叶变换快速傅里叶变换 其它可分离变换其它可分离变换统计变换：统计变换： 霍特林变换霍特林变换另一种分类方法：另一种分类方法：正弦型变换：正弦型变换： 傅里叶变换、傅里叶变换、DCTDCT方波型变换：方波型变换： Walsh Walsh变换、变换、HadamardHadamard变换、变换、 Haar Haar变换、变换、 Slant Slant变换变换 基于特征向量的变换：基于特征向量的变换： 霍特林变换霍特林变换第第三三章章 图图象象变变换换6第二节第二节 傅里叶变换傅里叶变换1-D傅里叶变换傅里叶变换 设长度为设长度为N的离散序
6、列为的离散序列为f(0), f(1), f(2), ，f(N-l)。 则其离散傅里叶变换对定义为：则其离散傅里叶变换对定义为：第第三三章章 图图象象变变换换7第二节第二节 傅里叶变换：一维傅里叶变换：一维 在在图图象象处处理理中中f(x)总总是是实实函函数数，但但一一般般F(u)是是复复函数，可以写成：函数，可以写成： F(u)=R(u)+j I(u) 其中其中R(u)和和I(u)分别为分别为F(u)的实部和虚部。的实部和虚部。 上式也常写成指数形式：上式也常写成指数形式： F(u)=| F(u)| exp j (u)第第三三章章 图图象象变变换换8第二节第二节 傅里叶变换：一维傅里叶变换：一
7、维幅度函数幅度函数 |F(u)|和相位函数和相位函数 (u)为：为： | F(u)| = R2(u)+ I2(u) 1/2 (u) =arctan I(u)/R(u) |F(u)| 又又称称为为f(x)的的傅傅里里叶叶频频谱谱， (u)称称为为相相位位角。角。频频谱谱的的平平方方称称为为f(x)的的功功率率谱谱或或频频谱谱密密度度，记记为为P(u)： P(u) = | F(u)| 2= R2(u)+I2(u)第第三三章章 图图象象变变换换9第二节第二节 傅里叶变换：一维傅里叶变换：一维指数项可借助欧拉公式写为：指数项可借助欧拉公式写为： exp -j2 u x= cos（2 u x）- j s
8、in（2 u x） 由于每个由于每个u值都确定所对应的正弦和余弦对的值都确定所对应的正弦和余弦对的频率，所以称为频率变量。频率，所以称为频率变量。第第三三章章 图图象象变变换换10第二节第二节 傅里叶变换：二维傅里叶变换：二维2-D傅里叶变换傅里叶变换 图象图象f(x, y)的的2-D傅里叶变换对是傅里叶变换对是1-D傅里叶变换对的推傅里叶变换对的推广：广：第第三三章章 图图象象变变换换11第二节第二节 傅里叶变换：二维傅里叶变换：二维2-D2-D傅里叶变换的频谱、相位角和功率谱如下：傅里叶变换的频谱、相位角和功率谱如下：频谱：频谱：|F(u, v)| = R|F(u, v)| = R2 2(
9、u, v) + I(u, v) + I2 2(u, v) (u, v) 1/21/2 相位角：相位角： (u, v) = arctan I(u, v) / R(u, v) (u, v) = arctan I(u, v) / R(u, v) 功率谱：功率谱：P(u, v) = |F(u, v)| P(u, v) = |F(u, v)| 2 2 = R = R2 2(u, v)+ I(u, v)+ I2 2(u, v)(u, v)第第三三章章 图图象象变变换换12第二节第二节 傅里叶变换：二维傅里叶变换：二维第第三三章章 图图象象变变换换13第二节第二节 傅里叶变换：二维傅里叶变换：二维第第三三章
10、章 图图象象变变换换14傅氏变换傅氏变换离散变换离散变换线性系统线性系统第二节第二节 傅里叶变换：二维傅里叶变换：二维一幅集成电路的扫描电子显一幅集成电路的扫描电子显微镜图象微镜图象,放大将近放大将近2500倍倍15第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性二维傅立叶变换特性二维傅立叶变换特性可分离性可分离性周期与共轭对称周期与共轭对称平移性平移性旋转特性旋转特性 线性与相似性线性与相似性 均值性均值性 拉普拉斯拉普拉斯 卷积与相关卷积与相关第第三三章章 图图象象变变换换16第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性可分离性可分离性二维离散傅立叶变换二维
11、离散傅立叶变换DFTDFT可分离性的基本思可分离性的基本思想是：想是： 二维二维DFTDFT可分离为两次一维可分离为两次一维DFTDFT应用：应用： 二维快速傅立叶算法二维快速傅立叶算法FFT FFT ，是通过计算两，是通过计算两次一维次一维FFTFFT实现的实现的第第三三章章 图图象象变变换换17第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性可分离性的定义可分离性的定义第第三三章章 图图象象变变换换18第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性可分离性成立的推导可分离性成立的推导先对列（先对列（y y变量）做变换：变量）做变换： N-1N-1F(x,F(x
12、,v v)=1/N )=1/N f(x,f(x,y y)exp(-j2)exp(-j2 v vy y/N)/N) y=0 y=0然后对行（然后对行（x x变量）进行变换：变量）进行变换： M-1 M-1F(u,v)=1/N F(u,v)=1/N F(x,F(x,v v)exp(-j2)exp(-j2 ux/N)ux/N) x=0 x=0第第三三章章 图图象象变变换换19第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性第第三三章章 图图象象变变换换行行列列20第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性平移性质平移性质f(xf(x，y) expj2y) expj2
13、 (u(u0 0x+vx+v0 0y)y)N N F(u- uF(u- u0 0,v- v,v- v0 0) ) f(x-xf(x-x0 0，y-yy-y0 0) ) F(u, F(u, v) v) exp exp -j2-j2 (u(u0 0x+vx+v0 0y)y)N N 将将f(x, f(x, y)y)与与一一个个指指数数项项相相乘乘就就相相当当于于把把其其变变换换后后的频域中心移动到新的位置。的频域中心移动到新的位置。将将F(u, F(u, v)v)与与一一个个指指数数项项相相乘乘就就相相当当于于把把其其反反变变换换后后的的空空域域中中心心移移动动到到新新的的位位置置。同同时时可可知知
14、，对对f(xf(x，y)y)的平移不影响其傅里叶变换的幅值。的平移不影响其傅里叶变换的幅值。该两式的证明可直接从傅里叶变换的定义式获得。该两式的证明可直接从傅里叶变换的定义式获得。第第三三章章 图图象象变变换换21平移性（不影响幅值，由级数展开可得出对应关系平移性（不影响幅值，由级数展开可得出对应关系 ） 表明原表明原f f（x,yx,y）用）用f f（x,yx,y ）exp-2jexp-2j （u u0 0x+vx+v0 0y y）/N/N替换替换后进行傅里叶变换，则变换后的频域中心平移到了新位后进行傅里叶变换，则变换后的频域中心平移到了新位置。置。 与上述频域平移与上述频域平移类似类似，
15、f f（x,yx,y） F F（u-uu-u0 0,v-v,v-v0 0）表明表明F F（u,vu,v）与一个指数项相乘）与一个指数项相乘后再进行傅里叶反变换，后再进行傅里叶反变换，则变换后的空域中心平移到了新位置。空域平移。则变换后的空域中心平移到了新位置。空域平移。 即即 f f（x-xx-x0 0,y-y,y-y0 0） F F（u,vu,v）。）。22举例：举例：当当 时有：时有：可以简单的用可以简单的用 乘以乘以 将将 的傅里的傅里叶变换的原点移动到相应频率方阵的中心。叶变换的原点移动到相应频率方阵的中心。图像的图像的离散离散傅里叶变换举例：傅里叶变换举例：2324 平移性质平移性质
16、 平移性质表明，只要将f(x, y)乘以因子(1)x+y，再进行离散傅立叶变换，即可将图像的频谱原点（0，0）移动到图像中心（M2, N2）处。图7-5是简单方块图像平移的结果。 图7-5 傅立叶频谱平移示意图(a) 原图像；（b）无平移的傅立叶频谱；（c）平移后的傅立叶频谱 (a) (b) (c) 25第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性周期性和共扼对称性周期性和共扼对称性 傅里叶变换和反变换均以傅里叶变换和反变换均以N为周期，即：为周期，即： F(u，v) = F(u+N，v) = F(u, v+N) = F(u+N, v+N) 上式可通过将右边几项分别代入傅里叶
17、变换的定义式上式可通过将右边几项分别代入傅里叶变换的定义式来验证。来验证。第第三三章章 图图象象变变换换26第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性 证明：证明： 所以上式成立。所以上式成立。第第三三章章 图图象象变变换换27第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性周周期期性性表表明明，尽尽管管F(u, v)对对无无穷穷多多个个u和和v的的值值重重复复出出现现，但但只只需需根根据据在在任任一一个个周周期期里里的的N个个值值就就可可以以从从F(u, v)得到得到f(x，y)。同样的结论对。同样的结论对f(x，y)在空域也成立。在空域也成立。如果如果f(
18、x, y)是实函数，则有共扼对称性是实函数，则有共扼对称性： F(u，v) = F* (-u,-v) | F(u，v)| = | F (-u,-v)| 第第三三章章 图图象象变变换换28第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性 证明：证明： 因为因为f(x, y)是实函数，所以是实函数，所以f(x, y)= f * (x, y)， 证毕。证毕。第第三三章章 图图象象变变换换29第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性旋转性质旋转性质 f(r, + 0) F(w， + 0)上上式式表表明明，对对f(x, y)旋旋转转 0对对应应于于将将其其傅傅里里叶叶
19、变变换换F（u, v)也旋转也旋转 0。 类类似似地地，对对F(u, v)旋旋转转 0也也对对应应于于将将其其傅傅里里叶叶反反变变换换f(x, y)旋转旋转 0。证证明明可可首首先先进进行行极极坐坐标标变变换换 x = rcos ，y = rsin ， u = wcos ，v = wsin ，将将f(x, y)和和F(u, v)转转换换为为f(r, )和和F(w, )，直直接接将将它它们们代代入入傅里叶变换对即可得到。傅里叶变换对即可得到。第第三三章章 图图象象变变换换30 旋转不变性旋转不变性 由旋转不变性可知，如果时域中离散函数旋转0角度，则在变换域中该离散傅立叶变换函数也将旋转同样的角度
20、。离散傅立叶变换的旋转不变性如图7-6所示。 图7-6 离散傅立叶变换的旋转不变性（a） 原始图像； （b） 原始图像的傅立叶频谱； （c） 旋转45后的图像； （d） 图像旋转后的傅立叶频谱 (a)(b)(d)(c)31第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性分配律分配律 根据傅里叶变换对的定义可直接得到：根据傅里叶变换对的定义可直接得到： Ff1(x, y)+f2(x, y) = F f1(x, y) + F f2(x, y)傅傅里里叶叶变变换换和和反反变变换换对对加加法法满满足足分分配配律律，但但对对乘法则不满足，即一般有：乘法则不满足，即一般有： Ff1(x, y
21、)f2(x, y) F f1(x, y) F f2(x, y) 第第三三章章 图图象象变变换换32第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性尺度变换尺度变换( (缩放缩放) ) 给给 定定 二二 个个 标标 量量 a a和和 b b， 则则 对对 傅傅 氏氏 变变 换换 有有 以以 下下 2 2式式 成成 立立 ： a f(x, y) a f(x, y) a F(u, v) a F(u, v) f(ax, by) f(ax, by) （1/|ab|1/|ab|）F(u/a, v/b) F(u/a, v/b) 证证明明：f(ax, f(ax, by)by)的的傅傅里里叶叶变变
22、换换为为：（令令x x1 1= = axax，y y1 1= = byby） 证毕。证毕。第第三三章章 图图象象变变换换33第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性平均值平均值 对一个对一个2-D2-D离散函数离散函数f(x, y), f(x, y), 其平均值为：其平均值为： 因为，对一个因为，对一个2-D2-D离散函数离散函数f(x, y)f(x, y)：第第三三章章 图图象象变变换换34第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性 如如将将u=v=0u=v=0代代入入傅傅里里叶叶变变换换定定义义式式，可可以以得到：得到： 比比较较以以上上两两式式可
23、可得得f(x, f(x, y)y)的的平平均均值值与与傅里叶变换的关系。傅里叶变换的关系。第第三三章章 图图象象变变换换35第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性卷积定理卷积定理对对1-D1-D连续情况，两个函数的卷积定义为：连续情况，两个函数的卷积定义为：卷卷积积定定理理：如如果果f(x)f(x)的的傅傅里里叶叶变变换换是是F(u)F(u)，g(x)g(x)的的傅里叶变换是傅里叶变换是 G(u) G(u)，那么：，那么： f(x) * g(x) f(x) * g(x) F(u)G(u) F(u)G(u) f(x)g(x) f(x)g(x) F(u) * G(u) F(
24、u) * G(u) 第第三三章章 图图象象变变换换36第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性离散卷积定理离散卷积定理 根据傅里叶变换和反变换的周期性，根据傅里叶变换和反变换的周期性，假设假设f(x)和和g(x)具有周期具有周期M，则卷积结果具有相同的，则卷积结果具有相同的周期。周期。只有当只有当M A+B-1时，卷积的周期才不会重迭，否时，卷积的周期才不会重迭，否则卷积结果就会产生重迭则卷积结果就会产生重迭(wrap-around)误差。误差。若给上述二个序列加一些零以得到其长度为若给上述二个序列加一些零以得到其长度为M的扩的扩展序列：展序列：第第三三章章 图图象象变变
25、换换37第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性它们的离散卷积可如下定义：它们的离散卷积可如下定义： 用用fe(x)和和g e(x)就可以避免重迭误差，卷积定理对离就可以避免重迭误差，卷积定理对离散序列仍可成立。散序列仍可成立。第第三三章章 图图象象变变换换38第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性例例 1 函数卷积示例函数卷积示例第第三三章章 图图象象变变换换39第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性例例 2 连续卷积和离散卷积的比较连续卷积和离散卷积的比较第第三三章章 图图象象变变换换40第二节第二节 傅里叶变换：二维变
26、换特性傅里叶变换：二维变换特性两个两个2-D2-D函数的卷积定义为：函数的卷积定义为： 2-D2-D卷积定理：卷积定理：f(x, y) * g(x, y) f(x, y) * g(x, y) F(u, v)G(u, v) F(u, v)G(u, v)f(x, y)g(x, y) f(x, y)g(x, y) F(u, v)*G(u, v) F(u, v)*G(u, v)第第三三章章 图图象象变变换换41 卷积与傅里叶变换的关系卷积与傅里叶变换的关系 两个函数卷积的傅里叶变换对应于两个函数傅两个函数卷积的傅里叶变换对应于两个函数傅里叶变换的乘积；里叶变换的乘积； 许多图像变换是卷积运算许多图像变
27、换是卷积运算 在频域的乘积运算比在空域的卷积运算快，在频域的乘积运算比在空域的卷积运算快，特别是有了快速傅立叶变换以后，效果更加明显。特别是有了快速傅立叶变换以后，效果更加明显。 两个函数乘积的傅里叶变换对应于两个函数傅两个函数乘积的傅里叶变换对应于两个函数傅里叶变换的卷积；里叶变换的卷积；42第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性为为求求得得2-D2-D的的离离散散卷卷积积，可可让让f(x, f(x, y)y)和和g(x, g(x, y)y)分分别别用用尺尺寸寸为为ABAB和和CDCD，周周期期为为M M和和N N的的离离散散数数组组表表示。示。这这里里需需要要选选择
28、择M M A+C-lA+C-l和和N N B+D-1B+D-1以以避避免免重重迭迭误误差。差。周期性扩展序列构造如下：周期性扩展序列构造如下：第第三三章章 图图象象变变换换43第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性它们的离散卷积可如下定义：它们的离散卷积可如下定义：与与一一维维情情况况同同样样，只只要要我我们们利利用用f fe e(x,y)(x,y)和和g g e e(x,y)(x,y)就就可可以以避避免免重重迭迭误误差差，卷卷积积定定理理对对2-D2-D离离散散情情况况仍仍成立。成立。第第三三章章 图图象象变变换换44第二节第二节 傅里叶变换：二维变换特性傅里叶变换：
29、二维变换特性相关定理相关定理对对l-Dl-D连续情况，二个函数的相关定义为：连续情况，二个函数的相关定义为： 如果如果f(x)和和g(x)是同一个函数，上式算得的结果常称是同一个函数，上式算得的结果常称为自相关。而如果为自相关。而如果f(x)和和g(x)不是同一个函数，则算不是同一个函数，则算得的结果常称为互相关。得的结果常称为互相关。第第三三章章 图图象象变变换换45第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性例例 一维函数相关示例：一维函数相关示例：第第三三章章 图图象象变变换换46第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性定义定义1-D1-D离散相关
30、：离散相关：进一步可对进一步可对2-D2-D连续和离散相关分别定义如下：连续和离散相关分别定义如下：第第三三章章 图图象象变变换换47 相关与傅里叶变换的关系相关与傅里叶变换的关系 相关主要应用于模板和原型匹配相关主要应用于模板和原型匹配给定一个未知图像和已知图像集之间求最紧给定一个未知图像和已知图像集之间求最紧密的匹配。其基本途径是求相关，然后取相密的匹配。其基本途径是求相关，然后取相关函数最大值。关函数最大值。48第二节第二节 傅里叶变换：二维变换特性傅里叶变换：二维变换特性对对卷卷积积和和相相关关，要要求求f(x, f(x, y)y)和和g(x, g(x, y) y) 是是周周期期为为M
31、 M和和N N的的离离散散数数组组。这这里里需需要要选选择择M M A+C- A+C- l l和和N N B+D-1B+D-1以避免重迭误差。以避免重迭误差。周期性序列周期性序列f fe e(x,y)(x,y)和和g ge e (x,y)(x,y)为：为：第第三三章章 图图象象变变换换49由采样重建图象由采样重建图象问题的提出：问题的提出： 连续时间信号先要在时间和幅度上进行离散连续时间信号先要在时间和幅度上进行离散化后才能被计算机处理化后才能被计算机处理 。同理，连续图象信。同理，连续图象信号也首先要在时间和幅度上进行离散化后才能号也首先要在时间和幅度上进行离散化后才能被计算机处理被计算机处
32、理 。 为了达到对原来连续时间信号或连续图像信为了达到对原来连续时间信号或连续图像信号较好的近似，或者说要使经采样后得到的离号较好的近似，或者说要使经采样后得到的离散数字信号或数字图象不失真，需要多大的采散数字信号或数字图象不失真，需要多大的采样率？是不是越高越好？最低不能低于多少？样率？是不是越高越好？最低不能低于多少？ 501 1、抽样定理抽样定理如果函数 f(x) 在 x=T 处连续，则函数 f(x) 在时间 T 的一个样本表示为：函数的抽样波形：如果函数f(t) 在 x=nT =nx，n0，1，2 处连续，则称为 f(x) 函数的抽样波形。函数的抽样波形是一个等间隔的无限脉冲序列，每一
33、个脉冲的幅度就等于函数f(x) 在脉冲出现时刻的值。定义： 为采样函数。51函数的抽样波形实际上就是连续函数 f(x) 和脉冲序列 s(x)的乘积。相乘s(x)xf(x)s(x)xf(x)x52函数的抽样后的频域波形应用频率的卷积定理，连续函数 f(x) 和脉冲序列的乘积就等于频域中两个函数的傅立叶变换的卷积的傅立叶逆变换。卷积逆变换-fcfcS(u)F(u)F(u) S(u)-1/xuuu1/x53混迭效应如果时域的抽样间隔时间太大，则等距脉冲序列 f 的间隔太小，它们与频率函数 F(u) 的卷积就产生了波形的相互重迭，抽样后函数的傅立叶变换的这种畸变称为混迭效应。卷积逆变换-fcfcF(u
34、)F(u) S(u)S(u)uuu54截止频率函数 f(x) 的傅立叶变换(即F(u)的最高频率称为截止频率。如下面 (a) 图所示，其中的 fc 即为截止频率。避免混迭效应：如果抽样间隔 T 等于截止频率倒数的一半，混迭效应就不会出现。此时，脉冲序列 S(u) 的间隔为 2fc ，如上面 (b) 图所示。-fcfcF(u)(a)-2fc2fcS(u)(b)uu55结论抽样定理的两个条件1)、要保证信号信息不丢失对于比 fc 高的频率，f(x) 的傅立叶变换必须为零(带限)。2)、抽样间隔选择为 T=1/2fc。这是使抽样定理成立的最小抽样间隔。2fc 称为奈奎斯特采样频率。-fcfcF(u)
35、u56函数的恢复从频域恢复F(u) S(u)相乘-fcfcF(u)逆逆变变换换xf(x)uuH(u)-fc-fcu572、有限区间函数的采样与恢复结论：在频域中处理经截断后的信号，不可能完全恢复原信号状态；但是能够恢复截断部分的采样信号。h(x)x1XH(u)*F(u)*S(u)u混迭效应f(x)s(x)xKH(u)u58设图像f (x, y)是一连续二维信号，其空间频谱F(fx, fy)在x方向具有截止频率Wu，在y方向具有截止频率Wv。所谓采样是对f (x, y)乘以空间采样函数：式中x和y为x、y两个方向的采样间隔，上式为脉冲函数(x, y)沿x、y两个方向的展开。 3、二维连续图像信号
36、的采样59第二节第二节 傅里叶变换：由采样重建图象傅里叶变换：由采样重建图象第第三三章章 图图象象变变换换60对一个带限函数对一个带限函数f(x,y)(即它的傅立叶变换在某个即它的傅立叶变换在某个有限区间有限区间R外为零外为零),如果选择如下频域里的函数如果选择如下频域里的函数(见上图见上图b)与与f(x,y)和和s(x,y)的乘积的傅立叶变换相的乘积的傅立叶变换相乘乘,就有可能完全恢复就有可能完全恢复f(x,y)如果设如果设2 Wu和和2Wv分别为能完全包含分别为能完全包含R的最小长方的最小长方形在形在U和和V方向的长度方向的长度,并通过选择采样间隔使之满并通过选择采样间隔使之满足下式足下式
37、,就能由采样完全重建就能由采样完全重建f(x,y)61练练 习习 题题（P70）3538第第三三章章 图图象象变变换换62第三节第三节 快速傅里叶变换快速傅里叶变换快速傅里叶变换算法原理快速傅里叶变换算法原理我我们们只只考考虑虑1-D的的情情况况，因因为为2-D傅傅里里叶叶变变换换可可由由连连续两次续两次1-D傅里叶变换得到。傅里叶变换得到。已知已知1-D傅里叶变换：傅里叶变换：第第三三章章 图图象象变变换换63第三节第三节 快速傅里叶变换快速傅里叶变换为计算全部的傅里叶系数，需要：为计算全部的傅里叶系数，需要： 复数乘法（复数乘法（N2）和加法（）和加法（N （N-1） 它们的次数都正比于它
38、们的次数都正比于N2。 注意到注意到 exp-j2 ux/N可只计算一次然后存放在一可只计算一次然后存放在一个表中以备查用，所以正确地分解上式可将复数乘个表中以备查用，所以正确地分解上式可将复数乘法和加法的次数减少为正比于法和加法的次数减少为正比于Nlog2N。 这个分解过程称为快速傅里叶变换这个分解过程称为快速傅里叶变换(FFT)算法。算法。 FFT算法与原始变换算法的计算量之比是算法与原始变换算法的计算量之比是log2N/N，当当 N比较大时，计算量的节省是相当可观的。比较大时，计算量的节省是相当可观的。第第三三章章 图图象象变变换换64第三节第三节 快速傅里叶变换快速傅里叶变换FFTFF
39、T算法算法基本思想基本思想 FFT FFT算法基于一个叫做算法基于一个叫做递推加倍递推加倍的方法。为方便起的方法。为方便起见我们用下式表达离散傅立叶变换公式见我们用下式表达离散傅立叶变换公式 N-1N-1F(u)=1/Nf(x)F(u)=1/Nf(x)(W(WN N) )uxux x=0 x=0 这里这里 W WN N = exp(-j2= exp(-j2 /N)/N) 是一个常数是一个常数第第三三章章 图图象象变变换换65第三节第三节 快速傅里叶变换快速傅里叶变换假设假设N N为：为： N = 2N = 2n n 其中其中n n是一个正整数，因此是一个正整数，因此N N可表示为：可表示为：N
40、 = 2MN = 2M 这这里里M M仍仍然然是是一一个个正正整整数数。将将N N = = 2M2M代代入入上上式式，得得到到： 2M-1 2M-1 F(u)=1/(2M)f(x)(W F(u)=1/(2M)f(x)(W2M2M) )uxux x=0 x=0 M-1M-1 M-1M-1 =1/2 =1/2 1/Mf(2x)W1/Mf(2x)W2M2Mu(2x)u(2x)+ +1/Mf(2x+1)W1/Mf(2x+1)W2M2Mu(2x+1)u(2x+1) x=0 x=0 x=0x=0第第三三章章 图图象象变变换换66第三节第三节 快速傅里叶变换快速傅里叶变换由于：由于： W WN N = ex
41、p(-j2= exp(-j2 /N)/N) W W2M2M2ux2ux = exp-j2= exp-j2 2ux2ux/ /2 2M M = exp-j2 = exp-j2 uxux/M = W/M = WM Muxux 所以：所以： W W2M2M2xu2xu = W= Wm mxuxu 代入上式有：代入上式有： M-1 M-1 M-1 M-1 1/21/Mf(2x) 1/21/Mf(2x)W Wm mux ux + 1/Mf(2x+1)+ 1/Mf(2x+1)W WM Muxux W W2M2Mu u x=0 x=0 x=0 x=0第第三三章章 图图象象变变换换67第三节第三节 快速傅里叶
42、变换快速傅里叶变换定义两个符号：定义两个符号： M-1 M-1 F Feveneven(u) = 1/Mf(2x)W(u) = 1/Mf(2x)Wm mux ux 偶数部分偶数部分 x=0x=0u = 0,1,2,M-1u = 0,1,2,M-1 M-1 M-1 F Fodd odd (u) = 1/Mf(2x(u) = 1/Mf(2x+1+1)W)Wm mux ux 奇数部分奇数部分 x=0 x=0 u = 0,1,2,M-1u = 0,1,2,M-1第第三三章章 图图象象变变换换68第三节第三节 快速傅里叶变换快速傅里叶变换得出得出FFT FFT 的第一个递推公式：的第一个递推公式： F(
43、u)=1/2 ( FF(u)=1/2 ( Feveneven(u)+F(u)+Foddodd(u)W(u)W2M2Mu u ) )该公式说明该公式说明F(u)F(u)可以通过奇部和偶部之和来计算可以通过奇部和偶部之和来计算第第三三章章 图图象象变变换换69第三节第三节 快速傅里叶变换快速傅里叶变换另有：另有：W WM Mu+M u+M = = expexp-2j-2j (u+M)/M(u+M)/M = exp-2j = exp-2j u/Mexp-2ju/Mexp-2j = = W WM Mu ue ej j (-2) (-2) = = W WM Mu u(-1)(-1)(-2) (-2) =
44、 = W Wm mu u且：且：W W2M2Mu+M u+M = = expexp-2j-2j (u+M)/2M(u+M)/2M = = exp-2jexp-2j u/2M u/2M e ej j (-1)(-1) = = W W2M2Mu u (-1)(-1)(-1) (-1) = -= -W W2M2Mu u最后有：最后有：W WM Mu+M u+M = = W Wm mu u ； W W2M2Mu+M u+M = = - -W W2M2Mu u第第三三章章 图图象象变变换换70第三节第三节 快速傅里叶变换快速傅里叶变换因为：因为：W WM Mu+M u+M = = W Wm mu u ；
45、 W W2M2Mu+M u+M = = - -W W2M2Mu u得出得出u+Mu+M 的的DFTDFT为：为： M-1 M-1F(u+M) F(u+M) = = 1/2 1/Mf(2x) 1/2 1/Mf(2x)W WM M(u+M)x (u+M)x + + x=0 x=0 M-1 M-1 1/Mf(2x 1/Mf(2x+1+1) )W WM M(u+M)x(u+M)x W W2M2Mu+Mu+M x=0x=0 = 1/2 ( F = 1/2 ( Feveneven(u)- F(u)- Foddodd(u)W(u)W2M2Mu u ) ) 第第三三章章 图图象象变变换换71第三节第三节 快速
46、傅里叶变换快速傅里叶变换得出得出FFTFFT的第二个递推公式：的第二个递推公式： F(u+M)= 1/2(F F(u+M)= 1/2(Feveneven(u)(u)- -F Foddodd(u)W(u)W2M2Mu u) ) 该该公公式式说说明明F(u+M)F(u+M)可可以以通通过过F(u)F(u)偶偶部部和和奇奇部部之之差差来来计计算算第第三三章章 图图象象变变换换72第三节第三节 快速傅里叶变换快速傅里叶变换分析这些表达式得到如下一些有趣的特性：分析这些表达式得到如下一些有趣的特性：（1 1）一个）一个N N个点的变换，能够通过将原始个点的变换，能够通过将原始 表达表达 式分成两个部分来
47、计算式分成两个部分来计算（2 2）通过计算两个（）通过计算两个（N/2N/2）个点的变换。得到）个点的变换。得到 F Feveneven(u)(u)和和 F Foddodd(u)(u)（3 3）奇部与偶部之和得到）奇部与偶部之和得到F(u)F(u)的前的前(N/2)(N/2)个值。个值。（4 4）奇部与偶部之差得到）奇部与偶部之差得到F(u)F(u)的后的后(N/2)(N/2)个值。个值。 且不需要额外的变换计算。且不需要额外的变换计算。第第三三章章 图图象象变变换换73第三节第三节 快速傅里叶变换快速傅里叶变换归纳快速傅立叶变换的思想：归纳快速傅立叶变换的思想：1 1）通过计算两个单点的）通
48、过计算两个单点的DFTDFT，来计算两个点的，来计算两个点的DFTDFT，2 2）通通过过计计算算两两个个双双点点的的DFTDFT，来来计计算算四四个个点点的的DFTDFT，以此类推以此类推3 3）对对于于任任何何N=2N=2m m的的DFTDFT的的计计算算，通通过过计计算算两两个个N/2N/2点点的的DFTDFT，来计算，来计算N N个点的个点的DFTDFT第第三三章章 图图象象变变换换74第三节第三节 快速傅里叶变换快速傅里叶变换第第三三章章 图图象象变变换换75第三节第三节 快速傅里叶变换快速傅里叶变换逆向逆向FFTFFT算法算法算法思想描述：用正向变换计算逆向变换算法思想描述：用正向
49、变换计算逆向变换 N-1N-1F(u) = 1/NF(u) = 1/N f(x)exp-j2f(x)exp-j2 ux/Nux/N x=0x=0u = 0, 1, 2, .N-1u = 0, 1, 2, .N-1 N-1N-1 f(x) = f(x) = F(u)expj2 F(u)expj2 ux/N ux/N u=0u=0x = 0, 1, 2, .N-1x = 0, 1, 2, .N-1第第三三章章 图图象象变变换换76第三节第三节 快速傅里叶变换快速傅里叶变换在离散逆向变换表达式两边同取共轭，并除在离散逆向变换表达式两边同取共轭，并除N N N-1N-11/N1/Nf f* *(x)
50、= (x) = 1/N1/N F F* *(u) exp(u) exp- -j2j2 ux/Nux/N u=0u=0u = 0, 1, 2, .N-1u = 0, 1, 2, .N-1 用正向变换算法计算，得到用正向变换算法计算，得到1/Nf*(x) 1/Nf*(x) ，取共轭并乘取共轭并乘上上N N，即得到，即得到f(x)f(x)第第三三章章 图图象象变变换换77第三节第三节 快速傅里叶变换快速傅里叶变换算法实现算法实现 实现按时间抽取实现按时间抽取FFT算法的关键是将输入数据排列成算法的关键是将输入数据排列成满足连续运用奇偶分解所需的次序。满足连续运用奇偶分解所需的次序。 对输入数据的排序
51、可根据一个简单的位对换规则进对输入数据的排序可根据一个简单的位对换规则进行（称为倒位序）。如用行（称为倒位序）。如用x表示表示f(x)的一个自变量值，的一个自变量值，那么它排序后对应的值可通过把那么它排序后对应的值可通过把x表示成二进制数并表示成二进制数并(左右左右)对换各值得到。对换各值得到。 当把输入数据进行了重新排序，则输出结果是正确当把输入数据进行了重新排序，则输出结果是正确的次序。的次序。 不把输入数据进行排序，则输出结果需要重新排序不把输入数据进行排序，则输出结果需要重新排序才能得到正确的次序。才能得到正确的次序。第第三三章章 图图象象变变换换78第三节第三节 快速傅里叶变换快速傅
52、里叶变换第第三三章章 图图象象变变换换79第三节第三节 快速傅里叶变换快速傅里叶变换例：例：N=23，f(6)排序后为排序后为f(3)，因为，因为6=1102倒位序倒位序后后0112=3。 0 1 2 3 4 5 6 7 输入输入000 001 010 011 100 101 110 111 自然序自然序000 100 010 110 001 101 011 111 倒位序倒位序 0 4 2 6 1 5 37 FFT的输入序的输入序第第三三章章 图图象象变变换换80按照前面叙述的按照前面叙述的FFTFFT方法方法, ,第第1 1层层(4(4组组2 2个点的运算个点的运算) )：同理：同理：81
53、第第2 2层（层（2 2组组4 4个点的运算）：个点的运算）：同理：同理：82第第3 3层（层（1 1组组8 8个点的运算）：个点的运算）：83算法计算量比较算法计算量比较 N FT FFT N FT FFT 倍数倍数 8 64 24 2.7 8 64 24 2.7 128 16384 896 18.3128 16384 896 18.3256 65535 2048 32 256 65535 2048 32 1024 1024*1024 22528 102.41024 1024*1024 22528 102.42048 2048*2048 22528 186.22048 2048*2048 2
54、2528 186.284练练 习习 题题（P71）310、 312、 第第三三章章 图图象象变变换换85傅立叶变换的优点与主要问题优点：1)、傅立叶变换的系数恰好表现的是被变换信号各个频率点上的幅值。可以根据要求精确地设计滤波器滤除不需要的频率成分。对图象而言，高频部分代表细节；低频部分表示背景或大面积的灰度变化不剧烈的部分。2)、利用卷积定理可以方便地对图象进行滤波处理。缺点： 傅立叶变换的参数都是复数，在数据的描述上相当于实数的两倍。 86第四节第四节 其它可分离图象变换其它可分离图象变换可分离变换可分离变换1-D变换的一般形式可用下式表示：变换的一般形式可用下式表示： 其中其中T(u)为
55、为f(x)的变换，的变换，g(x, u)称为正向变换核。称为正向变换核。 反变换可表示为：反变换可表示为： 其中其中h(x, u)称为反向变换核。称为反向变换核。第第三三章章 图图象象变变换换87第四节第四节 其它可分离图象变换其它可分离图象变换对对2-D的情况，正变换和反变换可分别表示为：的情况，正变换和反变换可分别表示为：第第三三章章 图图象象变变换换88第四节第四节 其它可分离图象变换其它可分离图象变换 如果：如果： g(x, y, u, v)=g1 (x, u)g2 (y, v)成立成立 则称正向变换核是可分离的。则称正向变换核是可分离的。 如果如果g1与与g2的函数形式一样，则称正向
56、变换核是对称的函数形式一样，则称正向变换核是对称 的。即：的。即： g(x, y, u, v)=g1 (x, u)g1 (y, v) 第第三三章章 图图象象变变换换89第四节第四节 其它可分离图象变换其它可分离图象变换 前面讨论的傅里叶变换是可分离变换中的一个特例。前面讨论的傅里叶变换是可分离变换中的一个特例。 例：傅里叶变换的正向变换核：例：傅里叶变换的正向变换核： g(x, y, u, v ) = exp-j2 (ux+vy)/N/N 它是可分离的和对称的，因为：它是可分离的和对称的，因为： g(x, y, u, v)=g1 (x, u)g1 (y, v)第第三三章章 图图象象变变换换90
57、第四节第四节 其它可分离图象变换其它可分离图象变换 只有可分离变换核的只有可分离变换核的2-D变换可分成两个步骤计算，每变换可分成两个步骤计算，每个步骤用一个个步骤用一个 l-D变换：先沿变换：先沿f(x, y)的每一行进行的每一行进行 l-D变变换，换， x,v = 0，l，N-l 然后沿然后沿T(x, v)的每一列进行的每一列进行1-D变换得到：变换得到： u,v = 0，l，N-l 第第三三章章 图图象象变变换换91第四节第四节 其它可分离图象变换其它可分离图象变换当当g(x, y, u, v)是是可可分分离离的的和和对对称称的的，图图象象变变换换的的矩矩阵阵形式：形式： T=AFA F
58、是是NN图图象象矩矩阵阵，A是是NN对对称称变变换换矩矩阵阵，T是是输输出出的的NN变换结果。变换结果。 从反变换式，有从反变换式，有： F= BTB 将将T=AFA代入上式，则：代入上式，则： F=BAFAB 如果如果B=A-1，这表明图象，这表明图象 F可完全由其变换恢复。可完全由其变换恢复。第第三三章章 图图象象变变换换92第四节第四节 其它可分离图象变换其它可分离图象变换 如果如果B不等于不等于A-1，则得，则得F的一个近似：的一个近似： 利用矩阵形式的一个优点是，所得到的变换矩阵可分利用矩阵形式的一个优点是，所得到的变换矩阵可分解成若干个具有较少非零元素的矩阵的乘积，这样可解成若干个
59、具有较少非零元素的矩阵的乘积，这样可减少冗余并减少操作次数。减少冗余并减少操作次数。第第三三章章 图图象象变变换换93第四节第四节 其它可分离图象变换其它可分离图象变换沃尔什变换沃尔什变换 沃沃尔尔什什变变换换其其变变换换核核是是由由+1和和-1组组成成的的，因因此此在在变变换换过过程程中中只只有有加加法法和和减减法法，计计算算速速度度快快而而且且易易于于用用硬硬件件实现。实现。 当当 N=2n 时，沃尔什变换核为：时，沃尔什变换核为：第第三三章章 图图象象变变换换94第四节第四节 其它可分离图象变换其它可分离图象变换 函数函数 f(x)的离散沃尔什的离散沃尔什(Walsh)正变换正变换W(u
60、)为：为： 由沃尔什变换核组成的矩阵是一个对称矩阵并且其行由沃尔什变换核组成的矩阵是一个对称矩阵并且其行和列正交。和列正交。第第三三章章 图图象象变变换换95 由美国数学家由美国数学家WalshWalsh提出而得名；提出而得名；沃尔什变换（沃尔什变换（WTWT）的变换核及其变换（设）的变换核及其变换（设N=2N=2n n） 一维正变换核：一维正变换核： 沃尔什正变换：沃尔什正变换： 式中式中 是是z z的二进制表达中的第的二进制表达中的第k k位（取位（取0 0或或1 1值）；值）； 例如例如n=3n=3时，若时，若z=6=110z=6=1102 2， 则则b b2 2（z z）=1=1， b
61、 b1 1（z z）=1=1， b b0 0（z z）=0 =0 。96 举例，举例，WalshWalsh变换核的值求解过程：变换核的值求解过程： 设设N=8N=8（n=3n=3），则），则 求求g g（0,00,0），即），即x=0=000x=0=0002 2； u=0=000 u=0=0002 2， 显然，显然，b b2 2（0 0）=0=0， b b1 1（0 0）=0=0， b b0 0（0 0）=0 =0 ， 所以，所以， g g（0,00,0） = = （1/81/8）(-1)(-1)0*00*0(-1)(-1)0*0 0*0 (-1)(-1)0*00*0 = = （1/81/8）
62、 。97第四节第四节 其它可分离图象变换其它可分离图象变换 N=8时时1-D的沃尔什变换核的值的沃尔什变换核的值(常数常数 l/N略去）。略去）。 例例如如x=6(110)，u=1(001)，则则 bi(x)bn-1-i(u)=1+0+0=1，所以系数为所以系数为-1。第第三三章章 图图象象变变换换98第四节第四节 其它可分离图象变换其它可分离图象变换 离散沃尔什反变换核为：离散沃尔什反变换核为： 所以离散沃尔什反变换为：所以离散沃尔什反变换为： 沃尔什正变换和反变换只差一个常数项沃尔什正变换和反变换只差一个常数项 l/N，所以用，所以用于正变换的算法也可用于反变换。于正变换的算法也可用于反变
63、换。第第三三章章 图图象象变变换换99第四节第四节 其它可分离图象变换其它可分离图象变换 2-D沃尔什正变换和反变换：沃尔什正变换和反变换： 沃尔什正变换核和反变换核都是可分离的和对称的，沃尔什正变换核和反变换核都是可分离的和对称的， g(x, y, u, v) = g1 (x, u)g1 (y, v) = h1 (x, u)h1 (y, v) 2-D的沃尔什正反变换都可分成两个步骤计算，每个的沃尔什正反变换都可分成两个步骤计算，每个 步骤用一个步骤用一个1-D变换实现。变换实现。第第三三章章 图图象象变变换换100第四节第四节 其它可分离图象变换其它可分离图象变换 沃尔什变换可用类似于沃尔什
64、变换可用类似于FFT算法快速地计算，算法快速地计算，只需将那里的指数项设为只需将那里的指数项设为 “l”即可。即可。 快速沃尔什变换为（快速沃尔什变换为（FWT）：）： W(u)=Weven(u)+Wodd(u)/2 W(u+M)=Weven(u)-Wodd(u)/2第第三三章章 图图象象变变换换101第四节第四节 其它可分离图象变换其它可分离图象变换 图象变换可以通过对核进行恰当的级数展开来得到图象变换可以通过对核进行恰当的级数展开来得到 由由于于正正向向变变换换核核和和反反向向变变换换核核只只依依赖赖于于x，y，u, v而而与与f(x, y)或或F(u, v)的的值值无无关关。这这些些核核
65、可可看看作作一一组组基基本本函函数数，一旦图象尺寸确定这些函数也完全确定。一旦图象尺寸确定这些函数也完全确定。 例如对沃尔什变换例如对沃尔什变换： W=UFV = (uo t uN-1 t ) F ui t vj即为基本函数。即为基本函数。第第三三章章 图图象象变变换换102第四节第四节 其它可分离图象变换其它可分离图象变换 例如对例如对N=4， l-D沃尔什变换核的值：沃尔什变换核的值：第第三三章章 图图象象变变换换103第四节第四节 其它可分离图象变换其它可分离图象变换则则 ：uo = (1 1 1 1), vo = (1 1 1 1), u1 = (1 1 1 1 ), v1 = (1
66、1 1 1 ), u2 = (1 1 1 1 ), v2 = (1 1 1 1 ), u3 = (1 1 1 1)， v3 = (1 1 1 1)第第三三章章 图图象象变变换换104第四节第四节 其它可分离图象变换其它可分离图象变换第第三三章章 图图象象变变换换105二维沃尔什变换对的定义例：用44沃尔什变换阵G对给定图像f1(x,y)和f2(x,y)进行变换，求其变换后的“图像”W1(u,v)和W2(u,v)。106能量集中在边角！且图像越平滑能量越集中。107第四节第四节 其它可分离图象变换其它可分离图象变换哈达玛变换哈达玛变换(Hadamard) 正向哈达玛变换核定义如下：正向哈达玛变换
67、核定义如下： l-D的离散哈达玛变换的离散哈达玛变换H(u)为：为： 第第三三章章 图图象象变变换换108第四节第四节 其它可分离图象变换其它可分离图象变换 N=8时时1-D哈达玛变换核的值哈达玛变换核的值 与沃尔什变换类似，由哈达玛变换核组成的矩阵是与沃尔什变换类似，由哈达玛变换核组成的矩阵是个个对称矩阵并且其行和列正交。对称矩阵并且其行和列正交。第第三三章章 图图象象变变换换109第四节第四节 其它可分离图象变换其它可分离图象变换 同样反变换核与正变换核只差一个常数同样反变换核与正变换核只差一个常数 l/N，即：，即： 离散哈达玛反变换为：离散哈达玛反变换为：第第三三章章 图图象象变变换换
68、110第四节第四节 其它可分离图象变换其它可分离图象变换1-D的哈达玛正变换和反变换只差一个常数项的哈达玛正变换和反变换只差一个常数项1/N，所以用于正变换的算法也可用于反变换。所以用于正变换的算法也可用于反变换。2-D的哈达玛正变换和反变换：的哈达玛正变换和反变换：第第三三章章 图图象象变变换换111第四节第四节 其它可分离图象变换其它可分离图象变换 同样，哈达玛正变换核和反变换核都是可分离的和同样，哈达玛正变换核和反变换核都是可分离的和对称的，所以对称的，所以2-D的哈达玛正变换和反变换都可分成两的哈达玛正变换和反变换都可分成两个步骤计算，每个步骤用一个个步骤计算，每个步骤用一个1-D变换
69、实现。变换实现。 在在绝绝大大多多数数图图象象变变换换应应用用中中有有N=2 n成成立立，所所以以沃沃尔尔什什变变换换和和哈哈达达玛玛变变换换常常混混合合使使用用。沃沃尔尔什什-哈哈达达玛玛变变换换常用来指两者中的任一个。常用来指两者中的任一个。第第三三章章 图图象象变变换换112第四节第四节 其它可分离图象变换其它可分离图象变换 在选择采用哪个变换时有两个因素需要考虑：在选择采用哪个变换时有两个因素需要考虑： （1） FWT可可直直接接写写成成逐逐次次加加倍倍的的形形式式，所所以以可可以以靠靠修修改改FFT算算法法得得到到。而而为为了了计计算算快快速速哈哈达达玛玛变变换换（FHT)，需需要要
70、进进一一步步考考虑虑数数据据的的排排序序。当当然然也也可可以以先先用用FWT然后再将结果排序以得到哈达玛变换。然后再将结果排序以得到哈达玛变换。（2）尽尽管管哈哈达达码码变变换换的的排排序序问问题题使使得得它它不不易易直直接接用用逐逐次次加加倍倍的的方方式式实实现现，但但哈哈达达码码变变换换具具有有的的简简单单迭迭代代性性质质可以方便地产生实现运算所必需的变换矩阵。可以方便地产生实现运算所必需的变换矩阵。第第三三章章 图图象象变变换换113第四节第四节 其它可分离图象变换其它可分离图象变换快速哈达玛变换（快速哈达玛变换（FHT） ： 最小阶最小阶(N=2)的哈达玛矩阵是：的哈达玛矩阵是： 如如
71、果果用用 HN代代表表N阶阶哈哈达达玛玛变变换换矩矩阵阵，则则HN满满足足迭迭代代关关系：系：第第三三章章 图图象象变变换换114例如：例如：N=8N=8时，有时，有哈达玛变换阵哈达玛变换阵每一行的符号的变化次数称作这个行的列率。哈达玛变换的正反变换核是一样的。变换核生成有一哈达玛变换的正反变换核是一样的。变换核生成有一规律，使其生成非常方便规律，使其生成非常方便(如果图像是如果图像是NNNN，N=2N=2n n )。115第四节第四节 其它可分离图象变换其它可分离图象变换 沿沿哈哈达达玛玛矩矩阵阵某某一一列列的的符符号号变变换换次次数数常常称称为为该该列列的的阶阶或或序序。前前述述N=8哈哈
72、达达玛玛矩矩阵阵的的序序依依次次为为0,7,3,4,1,6,2和和5。 我们可以定义随我们可以定义随u增加而序也增加的哈达玛变换核。增加而序也增加的哈达玛变换核。 以下两式给出满足该条件的以下两式给出满足该条件的1-D哈达玛变换对哈达玛变换对 ：第第三三章章 图图象象变变换换116第四节第四节 其它可分离图象变换其它可分离图象变换其中：其中：第第三三章章 图图象象变变换换117第四节第四节 其它可分离图象变换其它可分离图象变换N=8时经过排序的时经过排序的1-D哈达玛变换核的值：哈达玛变换核的值：经过排序的经过排序的2-D哈达玛变换核同样是可分离并且对称的。哈达玛变换核同样是可分离并且对称的。
73、第第三三章章 图图象象变变换换118第四节第四节 其它可分离图象变换其它可分离图象变换第第三三章章 图图象象变变换换119第四节第四节 其它可分离图象变换其它可分离图象变换离散余弦变换离散余弦变换1-D离散余弦变换离散余弦变换(DCT) 和其反变换由以下和其反变换由以下2式定义：式定义：其中其中a(u)由下式定义：由下式定义：第第三三章章 图图象象变变换换120第四节第四节 其它可分离图象变换其它可分离图象变换其矩阵形式为：其矩阵形式为：第第三三章章 图图象象变变换换121第四节第四节 其它可分离图象变换其它可分离图象变换2-D的的 DCT对由下面两式定义：对由下面两式定义：经经DCT变换后信
74、号的能量将向左上角集中，变换后信号的能量将向左上角集中，因而有利于图象数据的压缩。因而有利于图象数据的压缩。第第三三章章 图图象象变变换换122第四节第四节 其它可分离图象变换其它可分离图象变换N=4时经过排序的DCT基本函数的图示第第三三章章 图图象象变变换换123第四节第四节 其它可分离图象变换其它可分离图象变换哈尔变换哈尔变换 哈哈尔尔(Haar)变变换换基基于于定定义义在在连连续续闭闭区区间间0,1上上的的哈哈尔尔函数函数hk(z)，其中，其中k=0,1,2,N-1，要求，要求N=2n。 哈尔函数：哈尔函数：第第三三章章 图图象象变变换换124第四节第四节 其它可分离图象变换其它可分离
75、图象变换 其其中中：整整数数k可可被被唯唯一一地地分分解解（即即对对于于任任意意的的k 0，总存在总存在2的最大幂的最大幂2 p和余数和余数q-1）：）：k=2 p +q-1 k=2 p +q-1 （k=0,1,2,N-1，要求，要求N=2n） 其中其中 0 p n-1， 当当p=0时，时，q=0 或或q=1， 当当p=1时，时，q=1、2， 当当p=2时，时，q=1、2、3、4， 即当即当p 0时，时，1 q 2 p 。 例例如如对对N=4，当当k=0时时有有p=0和和q=0，而而当当k=1时时有有p=0和和q =1。 在这里在这里p规定了尺度，规定了尺度，q规定了平移量。规定了平移量。第第
76、三三章章 图图象象变变换换125第四节第四节 其它可分离图象变换其它可分离图象变换 根据哈尔函数可得出哈尔矩阵。根据哈尔函数可得出哈尔矩阵。 对对1个个NN矩矩阵阵，其其第第i行行是是由由z =0/N，1/N，(N-1)N的的h i(z)的元素构成。的元素构成。 哈尔矩阵哈尔矩阵A为：为：第第三三章章 图图象象变变换换126第四节第四节 其它可分离图象变换其它可分离图象变换 例如例如N=2时，哈尔矩阵为：时，哈尔矩阵为： 第第三三章章 图图象象变变换换127第四节第四节 其它可分离图象变换其它可分离图象变换 例如例如N=8时，哈尔矩阵为：时，哈尔矩阵为： 哈尔矩阵是正交矩阵，它具有实现快速变换
77、所需的性质。由于哈哈尔矩阵是正交矩阵，它具有实现快速变换所需的性质。由于哈尔矩阵中有许多常数和尔矩阵中有许多常数和“0”，所以哈尔变换可以很快地计算出来。，所以哈尔变换可以很快地计算出来。第第三三章章 图图象象变变换换128第四节第四节 其它可分离图象变换其它可分离图象变换N=8时哈尔变换的基函数第第三三章章 图图象象变变换换129第四节第四节 其它可分离图象变换其它可分离图象变换斜变换斜变换 斜斜(slant) 变换也称斯拉特变换。设变换也称斯拉特变换。设N为偶数，一个为偶数，一个 NN阶的斯拉特矩阵由下列迭代关系定义：阶的斯拉特矩阵由下列迭代关系定义：第第三三章章 图图象象变变换换130第
78、四节第四节 其它可分离图象变换其它可分离图象变换第第三三章章 图图象象变变换换131第四节第四节 其它可分离图象变换其它可分离图象变换例例 斯拉特矩阵示例斯拉特矩阵示例 N=4时的斯拉特矩阵为：时的斯拉特矩阵为：第第三三章章 图图象象变变换换132第四节第四节 其它可分离图象变换其它可分离图象变换N=8时的斯拉特矩阵系数图示第第三三章章 图图象象变变换换133练练 习习 题题（P71）316317 318 第第三三章章 图图象象变变换换134第五节第五节 霍特林变换霍特林变换霍霍特特林林(Hotelling)变变换换是是基基于于图图象象统统计计特特性性的的变变换换，霍霍特特林林变变换换也也常常
79、称称为为特特征征值值变变换换、主主分分量变换或离散量变换或离散K-L变换。变换。 霍特林变换的突出优点是去相关性好，主要用霍特林变换的突出优点是去相关性好，主要用于数据压缩和图象旋转上。于数据压缩和图象旋转上。第第三三章章 图图象象变变换换135第五节第五节 霍特林变换霍特林变换设给定一组设给定一组M个随机矢量（即个随机矢量（即x有有M个样本）：个样本）： k=1,2,M 这组随机矢量的均值矢量为：这组随机矢量的均值矢量为： m x =Ex 这组随机矢量的协方差矩阵为：这组随机矢量的协方差矩阵为： C x = E（x - m x ）（）（x - m x ）T 第第三三章章 图图象象变变换换13
80、6第五节第五节 霍特林变换霍特林变换 若若是是从从同同一一个个随随机机母母体体得得到到了了M个个矢矢量量采采样样，则则其其均值矢量和协方差矩阵可分别用以下两式来近似：均值矢量和协方差矩阵可分别用以下两式来近似：第第三三章章 图图象象变变换换137第五节第五节 霍特林变换霍特林变换 例例 协方差矩阵计算示例协方差矩阵计算示例 设有设有4个矢量个矢量 x1=0 0 0T，x2=1 0 0T，x3=1 1 0T，x4=1 0 1T， 则可得均值矢量为：则可得均值矢量为： m x =1/4 3 1 1 T第第三三章章 图图象象变变换换138第五节第五节 霍特林变换霍特林变换第第三三章章 图图象象变变换
81、换139第五节第五节 霍特林变换霍特林变换 因因为为矩矩阵阵C x是是一一个个实实对对称称矩矩阵阵，所所以以总总可可以以找找到到它它的一组的一组N个正交特征值。个正交特征值。 令令ei和和 i (i=1,2,N-1)分分别别为为C x的的特特征征矢矢量量和和对对应应的的特特征征值值，再再令令A为为由由C x的的特特征征矢矢量量组组成成的的矩矩阵阵，则则霍霍特特林变换定义为：林变换定义为： y = A(x-mx )第第三三章章 图图象象变变换换140第五节第五节 霍特林变换霍特林变换 由由这这个个变变换换得得到到的的y 矢矢量量其其均均值值为为零零，协协方方差差矩矩阵阵为为对角矩阵，即：对角矩阵
82、，即： my =0 C y =A C x AT 第第三三章章 图图象象变变换换141第五节第五节 霍特林变换霍特林变换证明：证明： 因为因为my = EY = EA（X - m x ） = AEX - A m x = 0 所以所以 my =0 而而 y矢量的协方差矩阵可由矢量的协方差矩阵可由A和和C x得到：得到： 因为因为C y = E（Y- m y）（）（Y - m y ）T = EY YT = E（AX - Am x）（）（AX - Am x）T = EA（X - m x）（）（X - m x）TAT = A E（X - m x）（）（X - m x）TAT = A C x AT (该变
83、换即是对该变换即是对C x的对角化变换的对角化变换) 所以所以 C y = A C x AT = C y是一个对角矩阵，它的主对角线上的元素正是是一个对角矩阵，它的主对角线上的元素正是C x的特征值。的特征值。第第三三章章 图图象象变变换换142第五节第五节 霍特林变换霍特林变换霍特林变换的性质：霍特林变换的性质：变换后的图象向量变换后的图象向量Y的均值向量的均值向量my为为0向量；向量；Y向量的协方差矩阵向量的协方差矩阵C y =A C x AT； 协协方方差差矩矩阵阵C y为为对对角角矩矩阵阵，其其对对角角线线上上的的元元素素等等于于C x的特征值，这说明向量的特征值，这说明向量Y的元素是
84、不相关的。的元素是不相关的。 霍霍特特林林变变换换的的突突出出优优点点是是去去相相关关性性好好，主主要要用用于于数数据据压压缩缩和和图图象象旋旋转转上上，另另外外也也作作为为评评价价图象变换性能优劣的标准。图象变换性能优劣的标准。 第第三三章章 图图象象变变换换143第五节第五节 霍特林变换霍特林变换 霍特林变换应用的例子：霍特林变换应用的例子：第第三三章章 图图象象变变换换144第五节第五节 霍特林变换霍特林变换（1）原始数据的分布指明了特征向量的方向；）原始数据的分布指明了特征向量的方向；（2）利用变换）利用变换y = A(x-mx )作数据旋转和中心化。作数据旋转和中心化。第第三三章章
85、图图象象变变换换145第五节第五节 霍特林变换霍特林变换 用用霍霍特特林林变变换换将将x映映射射到到y实实际际上上是是建建立立了了一一个个新新的的坐标系，其坐标轴在坐标系，其坐标轴在C x的特征矢量方向上。的特征矢量方向上。 借借助助这这个个坐坐标标系系可可看看出出，霍霍特特林林变变换换是是一一个个将将物物体体沿沿特特征征矢矢量量对对齐齐的的旋旋转转变变换换，这这个个变变换换将将数数据据解解除除了了相关。相关。 另另外外，特特征征值值是是沿沿C y的的主主对对角角线线的的，所所以以 i是是沿沿特特征矢量征矢量ei的的yi分量的方差。分量的方差。第第三三章章 图图象象变变换换146第五节第五节
86、霍特林变换霍特林变换第第三三章章 图图象象变变换换147第五节第五节 霍特林变换霍特林变换 从从 y重建重建x： A的的各各行行都都是是正正交交归归一一化化矢矢量量，从从而而A-1= AT，所所以以任一个矢量任一个矢量x都可由都可由y 恢复：恢复： x=AT y+m x 当当用用对对应应C x 中中K个个最最大大特特征征值值的的K个个特特征征矢矢量量构构造造变变换换矩矩阵阵Ak，这这样样得得到到的的y矢矢量量是是K阶阶的的，因因而而重重建建的的 x就只是一个近似而不再精确了。就只是一个近似而不再精确了。 用用Ak 重建的矢量为：重建的矢量为：第第三三章章 图图象象变变换换148第五节第五节 霍
87、特林变换霍特林变换 可以证明可以证明x和和 x 之间的均方误差是：之间的均方误差是： 上上式式表表明明，如如果果K=N（即即如如果果在在变变换换中中利利用用所所有有特特征征矢矢量量)则则误误差差为为零零。因因为为 i是是单单调调减减小小的的，所所以以上上式式也也表表明明，通通过过选选择择对对应应最最大大特特征征值值的的K个个特特征征矢矢量量可可以以使得使得x和之间的均方误差最小。和之间的均方误差最小。 这这说说明明在在最最小小化化矢矢量量x和和它它的的近近似似x之之间间在在均均方方误误差差的意义上，霍特林变换是最优的。的意义上，霍特林变换是最优的。第第三三章章 图图象象变变换换149练练 习习 题题（P71）320 321第第三三章章 图图象象变变换换150
