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