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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数字图像处理学,第,3,章,图像处理中的正交变换,（第二讲）,3.2,离散余弦变换,图像处理中常用的正交变换除了傅里叶变换外，还有其他一些有用的正交变换。其中离散余弦就是一种。离散余弦变换表示为,DCT,。,3.2.1,离散余弦变换的定义,一维离散余弦变换的定义由下式表示,(374),(375),式中 是第 个余弦变换系数，是广义频率变量，；是时域,N,点序列，,一维离散余弦反变换由下式表示,(376),显然，式,(374),式,(375),和式,(376),构成了一维离散余弦变换对。,二维离散余弦变换的定义由下式表示,(377),式,(377),是正变换公式。其中 是空间域二维向量之元素。，是变换系数阵列之元素。式中表示的阵列为,N N,二维离散余弦反变换由下式表示,(378),式中的符号意义同正变换式一样。式,(377),和式,(378),是离散余弦变换的解析式定义。更为简洁的定义方法是采用矩阵式定义。如果令,N,4,，那么由一维解析式定义可得如下展开式,(379),写成矩阵式,(380),若定义 为变换矩阵，为变换系数矩阵，为时域数据矩阵，则一维离散余弦变换的矩阵定义式可写成如下形式,(381),同理，可得到反变换展开式,(382),写成矩阵式,即,(384),当然，二维离散余弦变换也可以写成矩阵式,(385),式中 是空间数据阵列，是变换系数阵列，是变换矩阵，是 的转置。,3.2.2,离散余弦变换的正交性,由一维,DCT,的定义可知,它的基向量是,(386),在高等数学中，切比雪夫多项式的定义为,(387),式中 是 和 的多项式。它的第,N,个多项式为,如果,那么,将此式代入,显然，这与一维,DCT,的基向量是一致的。因为切比雪夫多项式是正交的，所以,DCT,也是正交的。另外，离散余弦变换的正交性也可以通过实例看出。如前所示，当,N,时，,(388),则,显然,这是满足正交条件的。从上述讨论可见，离散余弦变换是一类正交变换。,3.2.3,离散余弦变换的计算,与傅里叶变换一样离散余弦变换自然可以由定义式出发进行计算。但这样的计算量太大，在实际应用中很不方便。所以也要寻求一种快速算法。,首先，从定义出发，作如下推导,(389),式中 是取其实部的意思。如果把时域数据向量作下列延拓，即：,(390),则 的离散余弦变换可写成下式,(391),由式,(391),可见,是,2N,点的离散傅里叶变换。所以，在作离散余弦变换时，可以把序列长度延拓为,2N,，然后作离散傅里叶变换，产生的结果取其实部便可得到余弦变换。,同样道理，在作反变换时，首先在变换空间，把 作如下下延拓,(392),那么，反变换也可用式,(393),表示,(393),由式,(393),可见，离散余弦反变换可以从,的,2N,点反傅里叶变换实现。,3.3,沃尔什变换,离散傅里叶变换和余弦变换在快速算法中都要用到复数乘法，占用的时间仍然比较多。在某些应用领域中，需要更为便利更为有效的变换方法。沃尔什变换就是其中的一种。,沃尔什函数是在,1923,年由美国数学家沃尔什,(J.L.Walsh),提出来的。在沃尔什的原始论文中，给出了沃尔什函数的递推公式，这个公式是按照函数的序数由正交区间内过零点平均数来定义的。,这种规定函数序数的方法也被波兰数学家卡兹马兹,(,S.Kaczmarz,),采用了，所以，通常将这种规定函数序数的方法称为：,沃尔什卡兹马兹,(,Walshi-Kaczmarz,),定序法。,1931,年美国数学家佩利,(,R.E.A.C.Paley,),又给沃尔什函数提出了一个新的定义。他指出，沃尔什函数可以用有限个拉德梅克,(,Rademacher,),函数的乘积来表示。这样得到的函数的序数与沃尔什得到的函数的序数完全不同。这种定序方法是用二进制来定序的，所以称为,：,二进制序数或自然序数。,利用只包含,1,和,1,阵元的正交矩阵可以将沃尔什函数表示为矩阵形式。早在,1867,年，英国数学家希尔威斯特,(J.J.Sylvester),已经研究过这种矩阵。后来，法国数学家哈达玛,(,M.Hadamard,),在,1893,年将这种矩阵加以普遍化，建立了所谓哈达玛矩阵。,利用克罗内克乘积算子,(,Kronecker,Product Operator),不难把沃尔什函数表示为哈达玛矩阵形式。利用这种形式定义的沃尔什函数称为克罗内克序数。,这就是沃尔什函数的,第三种定序法,。,由上述历史可见，沃尔什函数及其有关函数的数学基础早已奠定了。但是，这些函数在工程中得到应用却是近几十年的事情。主要原因是由于半导体器件和计算机在近几十年得到迅速发展，它们的发展为沃尔什函数的实用解决了手段问题，因此，也使沃尔什函数得到了进一步发展。,与付里哀变换相比，沃尔什变换的主要优点在于存储空间少和运算速度高，这一点对图像处理来说是至关重要的，特别是在大量数据需要进行实时处理时，沃尔什函数就更加显示出它的优越性。,3.,3.1,拉德梅克函数,拉德梅克,(,Rademacher,),函数集是一个不完备的正交函数集，由它可以构成完备的沃尔什函数。在这里首先介绍一下拉德梅克函数。拉德梅克函数包括,n,和,t,两个自变量，用,R(n,t),来表示拉德梅克函数。它可用下式来表示,(3100),当,x=0,时，,sgn(x,),无定义。,(3101),由,sin,函数的周期性知道,R(n,t),也是周期性函数。由式,(3100),可见，,当,n=1,时，,R(n,t),的周期为,1,；,当,n=2,时,R(2,t),的周期为,1/2,；,当,n=3,时，,R(3,t),的周期为 ；,一般情况下可用下式表示,(3102),拉德梅克函数的波形如图,39,所示。,R(0,t),1,0,t,R(1,t),t,t,R(2,t),t,R(3,t),t,R(4,t),图,39,拉德梅克函数,1,0,-1,1,0,-1,1,0,-1,1,0,-1,由图,39,可见，拉德梅克函数有如下一些规律：,（）,R(n,t),的取值只有,+1,和,-1,。,（）,R(n,t),是,R(n-1,t),的二倍频。因此，如果已知最高次数,m,=,n,，则其他拉德梅克函数可由脉冲分频器来产生。,（）如果已知,n,，那么,R(n,t),有 个周期，其中,0t1；,（4）,如果在 处作取样，则可得到一数据序列,R(n,k)，,每一取样序列将与下述矩阵相对应。,这里我们取,n,=3,，,k,=0,1,2,.7,。,(3103),采用上述离散矩阵形式就可以用计算机,进行灵活处理。,3.3.,2,沃尔什函数,沃尔什函数系是完备的正交函数系，其值也是只取,1,和,1,。从排列次序来定义不外乎三种：,第一种是按沃尔什排列或称按列率排列来定义；,第二种是按佩利排列定义；(自然序数）,第三种是按哈达玛排列来定义。（第三定序法）,1.,按沃尔什排列的沃尔什函数,按沃尔什排列的沃尔什函数用 来表示。,函数波形如图,310,所示。,按沃尔什排列的沃尔什函数实际上就是按列率排列的沃尔什函数。,1,0,t,1,0,-1,t,1,1,1,0,-1,t,1,1,0,-1,t,1,1,0,-1,t,1,1,0,-1,t,1,1,0,-1,t,1,1,0,-1,t,1,图,310,按沃尔什排列的沃尔什函数,从波形上可总结出如下规律：,（1）在 中，,i,就是波形在正交区间的变号次数；,如：变号次数为0；,变号次数为1；,变号次数为2；,（2）,列率,：通常把正交区间内波形变号次数的二分之一称为列率,(,sequency,),。如果令,i,为波形在正交区间内的变号次数，那么，按照,i,为奇数或偶数，函数 的列率将分别由下式来决定,（3）按沃尔什排列的沃尔什函数可由拉德梅克函数构成，它的表达式如下,(3105),式中,R(k+1,t),是拉德梅克函数，,g,(,i,),是为,i,的格雷码，,是此格雷码的第,k,位数字，,p,为正整数。,一个正整数可以编成自然二进码，但也可以编成格雷码。格雷码也称为反射码。格雷码的特点是：两个相邻数的格雷码只有一个码位的值不同。例如：,2,的格雷码是,(0 0 1 1),，,3,的格雷码为,(0 0 1 0),。,这两个相邻的数字的格雷码只有第四个码位的值不同。,在脉冲编码技术中，常常采用这种码，以便得到较好的误差特性。一个正整数的自然二进码和格雷码之间是可以互相转换的。,从自然二进码转成格雷码的方法如下：,设一个十进制数的自然二进码为：,并设该数的格雷为：,其中 和 分别为自然二进码和格雷码内的码位数字，并且 、。它们之间的关系可用式,(3106),表示,(3106),式中 代表模加。,模2加的规律：,1,10,101,0 11,0 00,例：试求（,2,）的格雷码,，,P=4,。,解：,其中：,其格雷码,同理,，,若,则其格雷码为,在格雷码中，有如下关系存在：,(3107),例：设：,则,而,所以：,从正整数的格雷码也可以求出该十进数的自然二进码。其转换方法如下：,设正整数的格雷码为：,又设其自然二进码为：,则,(3108),例：,n,的格雷码为,1011,，求其自然二进码表示。,由给定的格雷码可知：,其中：,以上便是格雷码的定义及格雷码与自然二进码之间的转换方法。,即：自然二进码为,所以：,例：用公式,(3105),求,p=4,时的,。,解：因为,i=5,，所以,5,的自然二进码为,(0101),。由前面所述的转换规则可得到格雷码为,(0111),。因此，有下面的对应关系,(0 1 1 1),第,3,位 第,2,位 第,1,位 第,0,位,即,代入式,(3105),得,2.,按佩利排列的沃尔什函数,用 来表示按佩利排列的沃尔什函数，其波形如图,311,所示。,1,0,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,图,311,按佩利排列的沃尔什函数,t,按佩利排列的沃尔什函数也可以由拉德梅克函数产生。其定义由式,(3111),表示,(3111),式中 是拉德梅克函数，,是将函数序号写成自然二进码的,第,k,位数字，。即：,例：,p=3,时，求,因为,i,=1,，所以自然二进码为：,第,2,位 第,1,位 第,0,位,代入式,(3111),得：,例：,p=3,，求,。,因为,i=5,，所以，自然二进码为,(101),，代入式,(3111),，则,当,p=3,时的,8,个沃尔什函数经取样后可得矩阵,如式,(3112),由按佩利排列的沃尔什函数前,8,个波形可以看出有如下一些规律：,(1),、函数序号,i,与正交区间内取值符号变化次数有表,31,所列之关系。,表,3.1,按佩利排列的沃尔什函数序号与变号次数的关系,0,1,2,3,4,5,6,7,变 号 数,0,1,3,2,7,6,4,5,(2),、,i,与变号次数的关系是自然二进码与格雷码的关系。,如,i=6=(110),B,，这个自然二进制码按格雷码读出是,4,，也就是说，把十进制数编成自然二进码，然后按格雷码的规律反变回十进制数，这个数就是这个序号的沃尔什函数的变号次数。,3.,按哈达玛排列的沃尔什函数,按哈达玛排列的沃尔什函数是从 阶哈达玛矩阵得来的。阶哈达玛矩阵每一行的符号变化规律，对应某个沃尔什函数在正交区间内符号变化的规律，也就是说，阶哈达玛矩阵的每一行就对应着一个离散沃尔什函数阶哈达玛矩阵有如下形式,(3,113),(3,114),(3,115),一般情况,(3116),式,(3,116),是哈达玛矩阵的递推关系式。利用这个关系式可以产生任意 阶哈达玛矩阵。这个关系也叫做克罗内克积,(,Kronecker,Product),关系，或叫直积关系。,按哈达玛排列的沃尔什函数用 来表示。它的前八个函数波形如图,312,所示。,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,1,0,-1,1,t,图,312,按哈达玛排列,的沃尔什函数,t,(3117),按哈达玛排列的沃尔什函数也可以写成矩阵式,按哈达玛排列的沃尔什函数有如下一些特点,：,(1),、从,2,阶哈达玛矩阵可得到,2,个沃尔什函数，从,4,阶哈达玛矩阵可得到,4,个沃尔什函数，一般地说，阶哈达玛矩阵可得到 个沃尔什函数。,(2),、由不同阶数的哈达玛矩阵得到的沃尔什函数排列顺序是不同的。例如，从 得到的沃尔什函数 并不是从,得到的 ，而是从 得到的,。,(3),、由于哈达玛矩阵的简单的递推关系，使得按哈达玛排列的沃尔什函数特别容易记忆。,按哈达玛排列的沃尔什函数也可以由拉德梅克函数产生，解析式如式,(3118),所示。,(3118),式中 仍然是拉德梅克函数，,是把,i,的自然二进码反写后的第,k,位数字，并且 ，也就是,：,反写后,第,1,位第,0,位,例如：求,p=3,时，的波形。,第一种方法可用比较简单的方法是写出,阶哈达玛矩阵 ，并自上而下从,0,数起至第,6,行就是 。,第二种方法是应用数学解析式。因为,所以：,代入式,(3118),得,三种定义下的沃尔什函数，尽管它们的排列顺序各不相同，但三种排序方法得到的沃尔什函数是有一定关系的。它们之间的关系如表,32,和图,313,所示。,表,3 2,三种排列的前个沃尔什函数之间的关系表,例如 的 和 间的关系如下：,2=(010),B,，按格雷码读，即,(010),G,=3,，所以 就是 ，,(010),比特倒置后为,(010),，按二进码读仍为,2,，则 就是 。其他以次类推。以上就是沃尔什函数三种定义之间的关系。,图,3 13,三种定义的沃尔什函数序号间的关系,