数字图像处理学：第3章 图像处理中的正交变换（第3－4讲）.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数字图像处理学,第,3,章,图像处理中的正交变换,（第四讲）,3.4,哈尔函数及哈尔变换,在图像编码及数字滤波方面得到应用的另一种归一化正交函数是哈尔,(,Haar,),函数。它的一个重要特点是收敛均匀而迅速。,3.,4.1,哈尔函数的定义,哈尔函数是完备的、归一化的正交函数。在,0,1,区间内，,har,(,0,t,),为,1,，,har,(,1,t,),在左半个区间内取值为,1,，在右半个区间内取值为,-1,。它的其他函数取,0,值和,1,乘以 的幂，即取,，,2,，,4,等。具体定义如下。,一般情况,3173),前八个哈尔函数的波形图示于图,316,。,图,316,哈尔函数波形图,t,Har(0,t),1,0,Har(1,t),1,0,-1,t,Har(2,t),0,t,Har(3,t),t,Har(4,t),2,0,-2,t,Har(5,t),2,0,-2,Har(6,t),2,0,-2,Har(7,t),2,0,-2,t,t,t,图,316,哈尔函数波形图,上述哈尔函数是定义在区间,0,1),内的，但是，我们可以以,1,为周期，将它延拓至整个时间轴上。,3.4.2,哈尔函数的性质,（）归一化正交性,从图,316,我们可以看出哈尔函数的正交性。例如，哈尔函数,har,(,4,t,),har,(,5,t,),har,(,6,t,),har,(,7,t,),在时间上是互不重迭的，因此，它们必然是正交的。,另外，阶数不相同的两个哈尔函数，或者互不重迭（例如,har,(,3,t,),和,har,(,4,t,),；或者一个哈尔函数处于另一个哈尔函数的半周之内（例如,har,(,4,t,),和,har,(,2,t,),，这两种情况都是正交的。,(3174),总的来说，哈尔函数的正交性可用下式来表示,（）哈尔级数,周期为的连续函数,f,(,t,),可以展开成哈尔级数，即,(3175),(3176),其中,哈尔级数的收敛性比沃尔什函数要好。,图,317,指数函数展开成有限哈尔函数,图,317,是用有限项哈尔级数去逼近指数函数的情况。从图中可见，逼近曲线是步长相等的阶梯波。步长为 ，阶梯数目为 ，哈尔函数的最高阶为,P,，由这个,P,确定了步长。,从图可见，项数越多，逼近越好，这种增加项数的效果是很明显的。而在傅里叶级数和沃尔什级数中就没有这样直观、简单。,（）帕斯维尔定理,因为哈尔函数是完备的正交函数，因此，帕斯维尔定理是成立的，即,(3,177),（）全域函数和区域函数,我们观察哈尔函数会发现，前两个哈尔函数,har,(,0,t,),及,har,(,1,t,),在整个正交区间内都有值，因此把它们称为,全域函数,。而其余的函数,har,(,2,t,),har,(,3,t,),har,(,4,t,),等只在部分区间有值，因此，把它们称为,区域函数,。,按上述定义来看，三角函数，沃尔什函数都是全域函数。从式,(3176),可以看出，全域函数,har,(,0,t,),和,har,(,1,t,),的系数,C(0),和,C(1),在整个正交区间内受,f,(,t,),的影响；,区域函数的系数,c(2),c(3),等只受,f,(,t,),部分值的影响。这样，如果用哈尔函数去逼近,f,(,t,),，则全域函数在整个正交区间内起作用，而区域函数则在部分区域起作用。在工程应用中，如果我们希望将一个函数,f,(,t,),的某一部分逼近得更好的话，那么，哈尔函数有独到之处。,3.,4.3,哈尔变换及快速算法,把离散的哈尔函数写成矩阵形式就可得到哈尔矩阵。前八个哈尔函数组成的矩阵如式,(3178),所示。,(3178),哈尔正变换由下式来定义,(3179),式中 是变换系数阵列，是时间序列，是 阶哈尔矩阵，,p,为正整数。,其逆变换如式,(3180),所示,(3180),式中 是 的逆矩阵。由于哈尔矩阵不是对称矩阵，因此 不等于 ，所以哈尔正变换与逆变换是不相同的。,仿照沃尔什变换，利用矩阵因子分解之方法也可以得到快速哈尔变换。一般说来，快速哈尔变换的流程图并不是蝶形的，但是，我们可以用重新排序的方法构成哈尔变换的蝶式运算流程图。具体作法如下：,设原时间序列为,运算之前首先重新排序。令,为排序后的新序列。具体排序方法如下：,（）将 中元素的序号写成自然,二进码；,（）将此二进码比特倒置；,（）把倒置后的二进码翻成十进制数字，这个数字就是新序列的序号。,例如：,f(2),的序号是,2,，则：,2,十进,=010,二进,，,倒置后仍是,010,二进,，,所以,f,(2),f,(2),又例如：,f,(4),序号为,4,，则：,4,十进,100,二进,倒置后是 001,二进,1,十进,，,所以,f,(1),f,(4),。,以此类推可求出,f,(0),f(0),f,(1),f(4),f,(2),f(2),，,f,(3),f(6),，,f,(4),f(1),，,f,(5),f(5),，,f,(6),f(3),，,f,(7),f(7),。,这样排序后，第一步运算就构成蝶式运算的方式了。以后，为使后续运算也是蝶式的形式，第二，第三步等也要重新排序。其流程图如图,318,所示。,图,3,18,哈尔变换蝶式运算流程图,一般说来，用蝶式快速算法需要,log,2,N,次比特倒置，,2(N-1),加减法及,N,次乘法。,采用蝶式流程算法的目的是使哈尔变换也能用,FFT,处理机来运算。,二维哈尔变换与二维沃尔什哈达玛变换完全相似。其中只要把哈达玛矩阵换成哈尔矩阵就可以了。它的定义可用下式表示,(3181),式中,是空间域数据矩阵，,是变换系数矩阵，,和,为离散哈尔函数。,(3182)其反变换式为,矩阵式定义如下二式所示,（,3,183,）,(3,184),二维哈尔变换的计算也可按一维方法进行。需要指出的一点是，由于哈尔矩阵不是对称矩阵，因此，二维哈尔正变换与逆变换也是不同的。,3.5,斜矩阵与斜变换,在图像处理中要用到的另一种正交变换是斜变换（,Slant Transform,）。,斜向量和斜变换的概念是由伊诺莫托,(,Enomoto,),和夏伊巴塔,(Shibata),于,1971,年提出来的。,后来关于斜变换的一般定义又由普拉特,(Pratt),，,W.K,韦尔克,(Welch),和,W.H.,陈,(Chen),进一步推导出来。已经证明，斜向量非常适合于表示灰度逐渐改变的图像信号。目前，斜变换已成功地应用于图像编码。,3.,5.1,斜矩阵的构成,3.,5.2,斜 变 换,3.5.1,斜矩阵的构成,斜向量是一个在其范围内呈均匀阶梯下降的离散锯齿波形。,N=4,，,阶梯高度为,2,的斜向量如图,3,19,所示。,3,2,1,0,-1,-2,-3,图,3,19 N=4,阶梯为,2,的斜向量,如果用,S(n),来表示,N,N,斜矩阵，设,N=2,n,n,为正整数，则,(3,185),(3,186),对于,N=2,2,的斜矩阵可以写成下式,式中的,a,、,b,应满足下列两个条件：,第一，阶梯高度必须均匀；,第二，,S(2),必须是正交的。,由上述两个条件，我们可以求出,a,、,b,的值。首先，由阶梯高度必须均匀的条件，可有下式成立,即,由此，,S(2),可写成如下形式,其次，利用正交条件可求出,b,值。,(3187),因为,，所以,(3188),这样便求得斜矩阵如下,显然，,S(2),也具有列率性质。,S(2),的列率为,0,，,1,，,1,，,2,。,S(2),也可以用,S(1),来表示,因为,(3189),其中,所以,类似地有,S(3),用,S(2),来表示的式子如下,(3190),其中,是常数。由上式可见，,S(3),中的斜向量是通过对,S(2),乘以一个比例因子而得到的。其余项是为了满足列率性及正交性而设置的。,由上面二式可把它们推广为,N/2阶斜矩阵生成,N,阶斜矩阵的公式,式中,为,(2,2),单位矩阵；,(3192),例如：,n,=2,时，可得,显然，这样推出的结果与式,(3188),一致。,3.5.2,斜 变 换,用斜矩阵可定义变换的矩阵式如下,(3193),式中,S,(,n,),是,N,N,斜矩阵，并且,N=,2,n,D,(,n,),是变换系数矩阵，,f,(,x,),是数据矩阵。,反变换可由下式来表示,(3194),式中,是,的逆矩阵。,斜变换也可以用快速算法来计算，下面以,N,4,的情况来说明斜变换的快速算法。,可以把,S(2),做如下分解,由上面的分解，可得到下面的运算流程图。,图,320,斜变换快速算法流程图,二维斜变换的矩阵式如下,(3,195),(3,196),式中 是变换系数矩阵，是空间数据矩阵，是斜矩阵，是 的逆矩阵。,其计算方法也是采用一维计算方法。,以上介绍的是图像处理中应用的几种主要变换法，在某种意义上可以说，这些是比较经典的方法。目前，就变换来说，针对特殊的用途及目的还有更多的变换方法用于图像处理。如数论变换、霍夫变换等。,