《教学课件第3章 图像处理中的正交变换（第3－2讲）（研究生学位课）.ppt》由会员分享，可在线阅读，更多相关《教学课件第3章 图像处理中的正交变换（第3－2讲）（研究生学位课）.ppt（99页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、教学课件第3章图像处理中的正交变换（第32讲）（研究生学位课）数字图像处理学数字图像处理学第第3章章 图图像像处处理中的正交理中的正交变换变换（第二讲）（第二讲）阮秋琦教授阮秋琦教授3.2 离散余弦变换离散余弦变换 图像处理中常用的正交变换除了傅里叶变换外，图像处理中常用的正交变换除了傅里叶变换外，还有其他一些有用的正交变换。其中离散余弦就还有其他一些有用的正交变换。其中离散余弦就是一种。离散余弦变换表示为是一种。离散余弦变换表示为DCT。3.2.1 离散余弦变换的定义离散余弦变换的定义 一维离散余弦变换的定义由下式表示一维离散余弦变换的定义由下式表示(3-74)(375)式中式中 F(u)是
2、第是第 u 个余弦变换系数，个余弦变换系数，u 是广义频是广义频率变量，率变量，u=1,2,N-1 ；f(x)是时域是时域N点序列，点序列，x=1,2,N-1 一维离散余弦反变换由下式表示一维离散余弦反变换由下式表示(3-76)显然，式显然，式(3-74)(3-74)式式(3-75)(3-75)和式和式(3-76)(3-76)构成了一维构成了一维离散余弦变换对。离散余弦变换对。二维离散余弦变换的定义由下式表示二维离散余弦变换的定义由下式表示(3-77)式式(3-77)是正变换公式。其中是正变换公式。其中 f(x,y)是空间域二维是空间域二维向量之元素。向量之元素。x,y=0,1,2,N-1，F
3、(u,v)是变换系数阵列之元素。式中表示的阵列是变换系数阵列之元素。式中表示的阵列为为N N 二维离散余弦反变换由下式表示二维离散余弦反变换由下式表示(3-78)(3-78)式中的符号意义同正变换式一样。式式中的符号意义同正变换式一样。式(3-77)(3-77)和式和式(3-78)(3-78)是离散余弦变换的解析式定义。更为简洁是离散余弦变换的解析式定义。更为简洁的定义方法是采用矩阵式定义。如果令的定义方法是采用矩阵式定义。如果令N4 4，那，那么由一维解析式定义可得如下展开式么由一维解析式定义可得如下展开式(3-79)写成矩阵式写成矩阵式(3-80)若定义若定义A 为变换矩阵，为变换矩阵，F
4、(u)为变换系数矩阵，为变换系数矩阵，f(x)为时域数据矩阵，则一维离散余弦变换的矩阵为时域数据矩阵，则一维离散余弦变换的矩阵定义式可写成如下形式定义式可写成如下形式(3-81)同理，可得到反变换展开式同理，可得到反变换展开式(3-82)写成矩阵式写成矩阵式(3-83)(3-84)3.2.2 离散余弦变换的正交性离散余弦变换的正交性 由一维由一维DCT的定义可知的定义可知 它的基向量是它的基向量是(3-86)在高等数学中，切比雪夫多项式的定义为在高等数学中，切比雪夫多项式的定义为(3-87)比较一下余弦变换的基向量比较一下余弦变换的基向量(3-88)显然，这与一维显然，这与一维DCT的基向量是
5、一致的。因为的基向量是一致的。因为切比雪夫多项式是正交的，所以切比雪夫多项式是正交的，所以DCT也是正交也是正交的。另外，离散余弦变换的正交性也可以通过的。另外，离散余弦变换的正交性也可以通过实例看出。如前所示，当实例看出。如前所示，当N时，时，显然显然 这是满足正交条件的。从上述讨论可见，离散余这是满足正交条件的。从上述讨论可见，离散余弦变换是一类正交变换。弦变换是一类正交变换。3.2.3 离散余弦变换的计算离散余弦变换的计算与傅里叶变换一样，离散余弦变换自然可以由定义与傅里叶变换一样，离散余弦变换自然可以由定义式出发进行计算。但这样的计算量太大，在实际应式出发进行计算。但这样的计算量太大，
6、在实际应用中很不方便。所以也要寻求一种快速算法。用中很不方便。所以也要寻求一种快速算法。首先，从定义出发，作如下推导首先，从定义出发，作如下推导(3-89)(3-91)由式由式(3-91)可见可见是是2N点的离散傅里叶变换。点的离散傅里叶变换。所以，在作离散余弦变换时，可以把序列长度延所以，在作离散余弦变换时，可以把序列长度延拓为拓为2N，然后作离散傅里叶变换，产生的结果取，然后作离散傅里叶变换，产生的结果取其实部便可得到余弦变换。其实部便可得到余弦变换。同样道理，在作反变换时，首先在变换空间，同样道理，在作反变换时，首先在变换空间，把把 F(u)作如下延拓作如下延拓(3-92)那么，反变换也
7、可用式那么，反变换也可用式(3-93)表示表示(3-93)由式由式(3-93)可见，离散余弦反变换可以从可见，离散余弦反变换可以从 的的2N点反傅里叶变换实现。点反傅里叶变换实现。离散余弦变换的快速算法：离散余弦变换的快速算法：利用利用 FFT 解决离散余弦变换的快速运算解决离散余弦变换的快速运算 问题问题。离散傅里叶变换和余弦变换在快速算法中都要用离散傅里叶变换和余弦变换在快速算法中都要用到复数乘法，占用的时间仍然比较多。在某些应到复数乘法，占用的时间仍然比较多。在某些应用领域中，需要更为便利更为有效的变换方法。用领域中，需要更为便利更为有效的变换方法。沃尔什变换就是其中的一种。沃尔什变换就
8、是其中的一种。3.3 沃尔什变换沃尔什变换沃尔什函数是在沃尔什函数是在1923年由美国数学家年由美国数学家沃尔什沃尔什(J.L.Walsh)提出来的。在沃尔什的原始论文中，提出来的。在沃尔什的原始论文中，给出了沃尔什函数的递推公式，这个公式是按照给出了沃尔什函数的递推公式，这个公式是按照函数的序数由正交区间内过零点平均数来定义的。函数的序数由正交区间内过零点平均数来定义的。不久以后，这种规定函数序数的方法也被波兰数不久以后，这种规定函数序数的方法也被波兰数学家卡兹马兹学家卡兹马兹(S.Kaczmarz)采用了，所以，通常采用了，所以，通常将这种规定函数序数的方法称为将这种规定函数序数的方法称为
9、 沃尔什卡兹马兹沃尔什卡兹马兹(Walshi-Kaczmarz)定序法。定序法。1931年美国数学家年美国数学家佩利佩利(R.E.A.C.Paley)又给沃又给沃尔什函数提出了一个新的定义。他指出，沃尔尔什函数提出了一个新的定义。他指出，沃尔什函数可以用有限个拉德梅克什函数可以用有限个拉德梅克(Rademacher)函函数的乘积来表示。数的乘积来表示。这样得到的函数的序数与沃尔什得到的函数的序这样得到的函数的序数与沃尔什得到的函数的序数完全不同。这种定序方法是用二进制来定序的，数完全不同。这种定序方法是用二进制来定序的，所以称为所以称为 二进制序数或自然序数。二进制序数或自然序数。利用只包含利
10、用只包含1和和1阵元的正交矩阵可以将沃尔什阵元的正交矩阵可以将沃尔什函数表示为矩阵形式。早在函数表示为矩阵形式。早在1867年，英国数学家希年，英国数学家希尔威斯特尔威斯特(J.J.Sylvester)已经研究过这种矩阵。后来，已经研究过这种矩阵。后来，法国数学家法国数学家哈达玛哈达玛(M.Hadamard)在在1893年将这种矩年将这种矩阵加以普遍化，建立了所谓哈达玛矩阵。阵加以普遍化，建立了所谓哈达玛矩阵。利用克罗内克乘积算子利用克罗内克乘积算子(Kronecker Product Operator)不难把沃尔什函数表示为哈达玛矩阵不难把沃尔什函数表示为哈达玛矩阵形式。利用这种形式定义的沃
11、尔什函数称为克形式。利用这种形式定义的沃尔什函数称为克罗内克序数。这就是沃尔什函数的罗内克序数。这就是沃尔什函数的第三种定序第三种定序法法。由上述历史可见，沃尔什函数及其有关函数的数由上述历史可见，沃尔什函数及其有关函数的数学基础早已奠定了。但是，这些函数在工程中得学基础早已奠定了。但是，这些函数在工程中得到应用却是近几十年的事情。主要原因是由于半到应用却是近几十年的事情。主要原因是由于半导体器件和计算机在近几十年得到迅速发展，它导体器件和计算机在近几十年得到迅速发展，它们的发展为沃尔什函数的实用解决了手段问题，们的发展为沃尔什函数的实用解决了手段问题，因此，也使沃尔什函数得到了进一步发展。因
12、此，也使沃尔什函数得到了进一步发展。与傅里叶变换相比，沃尔什变换的主要优点在与傅里叶变换相比，沃尔什变换的主要优点在于存储空间少和运算速度高，这一点对图像处于存储空间少和运算速度高，这一点对图像处理来说是至关重要的，特别是在大量数据需要理来说是至关重要的，特别是在大量数据需要进行实时处理时，沃尔什函数就更加显示出它进行实时处理时，沃尔什函数就更加显示出它的优越性。的优越性。3.3.2 拉德梅克函数拉德梅克函数拉德梅克拉德梅克(Rademacher)函数集是一个不完备的正交函数集是一个不完备的正交函数集，由它可以构成完备的沃尔什函数。在这里函数集，由它可以构成完备的沃尔什函数。在这里首先介绍一下
13、拉德梅克函数。拉德梅克函数包括首先介绍一下拉德梅克函数。拉德梅克函数包括n和和t两个自变量，用两个自变量，用R(n,t)来表示拉德梅克函数。它可用来表示拉德梅克函数。它可用下式来表示下式来表示(3-100)当当x=0时，时，sgn(x)无定义。无定义。(3-101)由由sin函数的周期性知道函数的周期性知道R(n,t)也是周期性函数。也是周期性函数。由式由式(3100)可见，可见，当当 n=1时，时，R(1,t)的周期为的周期为1；当当 n=2时时R(2,t)的周期为的周期为1/2；当当 n=3时，时，R(3,t)的周期为的周期为 ；一般情况下可用下式表示一般情况下可用下式表示(3-102)拉
14、德梅克函数的波形如图拉德梅克函数的波形如图3-10所示。所示。R(0,t)1 0 t R(1,t)t tR(2,t)t R(3,t)t R(4,t)图图 3-10 拉德梅克函数拉德梅克函数 10-110-110-110-1 由图由图3-10可见，拉德梅克函数有如下一些规律：可见，拉德梅克函数有如下一些规律：（）（）R(n,t)的取值只有的取值只有+1和和-1。（）（）R(n,t)是是R(n-1,t)的二倍频。因此，如果已知最的二倍频。因此，如果已知最高次数高次数m=n，则其他拉德梅克函数可由脉冲分频器来，则其他拉德梅克函数可由脉冲分频器来产生。产生。(3-103)采用上述离散矩阵形式就可以用计
15、算机采用上述离散矩阵形式就可以用计算机进行灵活处理。进行灵活处理。3.3.3 沃尔什函数沃尔什函数 沃尔什函数系是完备的正交函数系，其值也是只取沃尔什函数系是完备的正交函数系，其值也是只取1和和1。从排列次序来定义不外乎三种：。从排列次序来定义不外乎三种：第一种是按沃尔什排列或称按列率排列来定义；第一种是按沃尔什排列或称按列率排列来定义；第二种是按佩利排列定义；第二种是按佩利排列定义；(自然序数）自然序数）第三种是按哈达玛排列来定义。（第三定序法）第三种是按哈达玛排列来定义。（第三定序法）还可用其它方式来定义，但沃尔什函数的定还可用其它方式来定义，但沃尔什函数的定义至今尚未统一，下面分别讨论上
16、述三种排义至今尚未统一，下面分别讨论上述三种排列方法定义的沃尔什函数。列方法定义的沃尔什函数。10t10-1t1110-1t110-1t110-1t110-1t110-1t110-1t1 图图 3-11 按沃尔什排列的按沃尔什排列的沃尔什函数沃尔什函数 10t10-1t1110-1t110-1t110-1t110-1t110-1t110-1t1 图图 3-11 按沃尔什排列的按沃尔什排列的沃尔什函数沃尔什函数（2）列率列率：通常把正交区间内波形变号次通常把正交区间内波形变号次数的二分之一称为列率数的二分之一称为列率(sequency)。如果令。如果令 i为为波形在正交区间内的变号次数，那么，按
17、照波形在正交区间内的变号次数，那么，按照i为为奇数或偶数，函数奇数或偶数，函数 的列率将分别由下式来决定的列率将分别由下式来决定(3-104)（3）按沃尔什排列的沃尔什函数可由拉德梅克函数构成，它的表达式如下(3-105)式中R(k+1,t)是拉德梅克函数，g(i)是为i的格雷码，g(i)k是此格雷码的第k位数字，p为正整数。一个正整数可以编成自然二进码，但也可以编成格雷码。格雷码也称为反射码。格雷码的特点是：两个相邻数的格雷码只有一个码位的值不同。例如：2的格雷码是 (0 0 1 1)，3的格雷码为 (0 0 1 0)。这两个相邻的数字的格雷码只有第四个码位的值不同。在脉冲编码技术中，常常采
18、用这种码，以便得到较好的误差特性。一个正整数的自然二进码和格雷码之间是可以互相转换的。从自然二进码转成格雷码的方法如下：(3-106)模2加的规律：110 101 0 11 0 00 (3-107)从正整数的格雷码也可以求出该十进数的自然二进码。其转换方法如下：设正整数的格雷码为：又设其自然二进码为：(3-108)1图 3-12 按佩利排列的沃尔什函数(3-112)由按佩利排列的沃尔什函数前8个波形的规律：(1)、函数序号i与正交区间内取值符号变化次数有表3-1所列之关系。表3-1 按佩利排列的沃尔什函数序号与变号次数的关系 i0 01 12 23 34 45 56 67 7变变号号 数数0
19、01 13 32 27 76 64 45 5 (2)、i与变号次数的关系是自然二进码与格雷码的关系。如i=6=(110)B，这个自然二进制码按格雷码读出是4，也就是说，把十进制数变成自然二进码，然后按格雷码的规律反变回十进制数，这个数就是这个序号的沃尔什函数的变号次数。3 按哈达玛排列的沃尔什函数按哈达玛排列的沃尔什函数 按哈达玛排列的沃尔什函数是从 2n 阶哈达玛矩阵得来的。2n 阶哈达玛矩阵每一行的符号变化规律，对应某个沃尔什函数在正交区间内符号变化的规律，也就是说，2n 阶哈达玛矩阵的每一行就对应着一个离散沃尔什函数。2n 阶哈达玛矩阵有如下形式 (3-114)(3-115)(3-113
20、)一般情况一般情况(3-116)式式(3-116)(3-116)是哈达玛矩阵的递推关系式。利用这个关是哈达玛矩阵的递推关系式。利用这个关系式可以产生任意系式可以产生任意 2 2n 阶哈达玛矩阵。这个关系也阶哈达玛矩阵。这个关系也叫做克罗内克积叫做克罗内克积(Kronecker Product)(Kronecker Product)关系，或叫直关系，或叫直积关系。积关系。按哈达玛排列的沃尔什函数用 walh(i,t)来表示。它的前八个函数波形如图3-13所示。按哈达玛排列的沃尔什函数也可以写成矩阵式 图图 3-13 按哈达玛排列按哈达玛排列的沃尔什函数的沃尔什函数 (3-117)按哈达玛排列的沃
21、尔什函数有如下一些特点：(1)、从2阶哈达玛矩阵可得到2个沃尔什函数，从4阶哈达玛矩阵可得到4个沃尔什函数，一般地说，2n 阶哈达玛矩阵可得到 2n 个沃尔什函数。(2)、由不同阶数的哈达玛矩阵得到的沃尔什函数排列顺序是不同的。例如，从 Hh(4)得到的沃尔什函数 walh(2,t)并不是从 Hh(8)得到的 walh(2,t)，而是从 Hh(8)得到的 walh(4,t)。(3)、由于哈达玛矩阵的简单的递推关系，使得按哈达玛排列的沃尔什函数特别容易记忆。(4)、按哈达玛排列的沃尔什函数也可以由拉德梅克 函数产生，解析式如式(3-118)所示。(3-118)式中 仍然是拉德梅克函数，是把i的自然二进码反写后的第k位数字，并且 ，也就是反写后 第1位第0位 三种定义下的沃尔什函数，尽管它们的排列顺序各不相同，但三种排序方法得到的沃尔什函数是有一定关系的。它们之间的关系如表3-2和图3-14所示。代入式(3118)得例如 Walp(2,t)的 walw(i,t)和 walH(i,t)间的关系如下：2=(010)B，按格雷码读，即(010)G=3，所以 就是 walw(3,t)，(010)比特倒置后为(010)，按二进码读仍为2，则 walp(2,t)就是 walH(2,t)。其他以次类推。以上就是沃尔什函数三种定义之间的关系。图 3-14 三种定义的沃尔什函数序号间的关系