第3章 图像处理中的正交变换（第3-2讲）

数字图像处理基础第3章图像处理中的正交变换（第二讲）3. 2 离散余弦变换

图像处理中常用的正交变换除了傅里叶变换外，还有其他一些有用的正交变换。其中离散余弦就是一种。离散余弦变换表示为DCT。

3.2.1 离散余弦变换的定义

一维离散余弦变换的定义由下式表示

F(0)?1NN?1?f(x)x?0N?1(3—74)

22(x?1)u?F(u)?f(x)cos?Nx?02N(3—75)

式中F(u)是第u个余弦变换系数，u是广义频率变量，u?1,2,3,??,N?1；f(x)是时域N点序列，

x?0,1,??,N?1一维离散余弦反变换由下式表示

f(x)?12N?1(2x?1)u?F(0)?F(u)cos?NNu?02N(3—76)

显然，式(3—74)式(3—75)和式(3—76)构成了一维离散余弦变换对。

二维离散余弦变换的定义由下式表示

1F(0,0)???f(x,y)Nx?0y?02(2y?1)v?F(0,v)?f(x,y)?cos??Nx?0y?02NN?1N?1N?1N?12F(u,0)??Nx?0N?1N?1?y?0(2x?1)u?f(x,y)cos2N2(2x?1)u?(2y?1)v?F(u,v)???f(x,y)cos?cos(3—77) Nx?0y?02N2NN?1N?1

式(3—77)是正变换公式。其中f(x,y)是空间域二维向量之元素。x,y?0,1,2,....N?1,，F(u,v)是变换系数阵列之元素。式中表示的阵列为N ×N

二维离散余弦反变换由下式表示

12(2y?1)v?f(x,y)?F(0,0)?F(0,v)cos?NNv?12NN?12(2x?1)u??F(u,0)cos?Nu?12NN?12?N??u?1v?1N?1N?1(2x?1)u?(2y?1)v?F(u,v)cos?cos2N2N(3—78)

式中的符号意义同正变换式一样。式(3—77)和式

(3—78)是离散余弦变换的解析式定义。更为简洁的定义方法是采用矩阵式定义。如果令N＝4，那

么由一维解析式定义可得如下展开式

?F(0)?0.500f(0)?0.500f(1)?0.500f(2)?0.500f(3)?F(1)?0.653f(0)?0.271f(1)?0.271f(2)?0.653f(3)???F(2)?0.500f(0)?0.500f(1)?0.500f(2)?0.500f(3)??F(3)?0.271f(0)?0.653f(1)?0.653f(2)?0.271f(3)(3—79)

写成矩阵式

?F(0)??0.5000.500?F(1)??0.6530.271?????F(2)??0.500?0.500????F(3)??0.271?0.6530.500??f(0)?????0.271?0.653??f(1)???0.5000.500??f(2)????0.653?0.271??f(3)?0.500(3—80)

[f(x,y)][F(u)]为变换系数矩阵，若定义[A]为变换矩阵，

为时域数据矩阵，则一维离散余弦变换的矩阵定义

式可写成如下形式

[F(u)]?[A] [f(x)](3—81)

同理，可得到反变换展开式

?f(0)?0.500F(0)?0.653F(1)?0.500F(2)?0.271F(3)?f(1)?0.500F(0)?0.271F(1)?0.500F(2)?0.653F(3)???f(2)?0.500F(0)?0.271F(1)?0.500F(2)?0.653F(3)??f(3)?0.500F(0)?0.653F(1)?0.500F(2)?0.271F(3)(3—82)

写成矩阵式

0.271??F(0)??f(0)??0.5000.6530.500?f(1)??0.5000.271?0.500?0.653??F(1)??????????f(2)??0.500?0.271?0.5000.653??F(2)????????f(3)??0.500?0.6530.500?0.271??F(3)?

即

[f(x)]?[A]' [F(u)](3—84)

当然，二维离散余弦变换也可以写成矩阵式

[F(u,v)]?[A] [f(x,y)][A]? [f(x,y)]?[A]? [F(u,v)][A](3—85)

[F(u,v)]是变换系式中[f(x,y)]是空间数据阵列，

[A]是变换矩阵，[A]?是[A]的转置。数阵列，

3.2.2 离散余弦变换的正交性

由一维DCT的定义可知

N?11F(0)?f(x)?Nx?0F(u)?2NN?1(2x?1)u??f(x)cos2Nx?0它的基向量是

???1, N2(2x?1)u??cos?N2N?(3—86)

在高等数学中，切比雪夫多项式的定义为

T0(p)?Tu(zx)?1N2cos?uarccos(zx)?N(3—87)

式中Tu(zx)是u和多项式为

TN(zx)?zx的多项式。它的第N个

2cosNarccos(zx)N如果那么将此式代入

TN(zx)?0(2x?1)?zx?cos2NTN(zx)则

TN???2(2x?1)????cos?uarccos?cos??N2N????2(2x?1)u?cosN2N(3—88)

显然，这与一维DCT的基向量是一致的。因为切比雪夫多项式是正交的，所以DCT也是正交

的。另外，离散余弦变换的正交性也可以通过实例看出。如前所示，当N＝４时，

0.5000.500?0.500?0.6530.271?0.271[A]???0.500?0.500?0.500?0.653?0.271?0.6530.6350.500?0.500?0.5000.271?0.500[A]? ???0.500?0.271?0.500?0.500?0.500?0.6530.500??0.653??0.500???0.271?0.2710???0.653?0.653???0.271?显然

[A][A]'?[I]这是满足正交条件的。从上述讨论可见，离散余弦变换是一类正交变换。

3.2.3 离散余弦变换的计算

与傅里叶变换一样，离散余弦变换自然可以由定义式出发进行计算。但这样的计算量太大，在实际应

用中很不方便。所以也要寻求一种快速算法。首先，从定义出发，作如下推导

F(u)???2N2N?x?0N?1(2x?1)u?f(x)cos2N(2x?1)u??j2N?x?0N?1?f(x)Re?e?N?1??????(3—89)

?2Re??f(x)eN?x?0(2x?1)u??j2N式中

Re是取其实部的意思。如果把时域数据向

量作下列延拓，即：

??f(x) fe?x???? 0 ?x?0,1,2,??,N?1x?N,N?1,??,2N?1(3—90)

则fe(x)的离散余弦变换可写成下式

1F(0)?NF(u)?2N2N?1x?0?f(x)ex?02N?1?(2x?1)u?fe(x)cos2N(2x?1)u??j2N2??Re??fe(x) eN?x?02N?1??????(3—91)

2??Re?eN?u??j2N??fe(x) ex?02N?12xu??j2N

由式(3—91)可见

2N?1x?02xu??j 2N?fe(x) e是2N点的离散傅里叶变换。所以，在作离散余弦变换时，可以把序列长度延拓为2N，然后作离散傅里叶变换，产生的结果取其实部便可得到余弦变换。

同样道理，在作反变换时，首先在变换空间，把

[F(u)]作如下下延拓

u?0,1,2,??,N?1u?N,N?1,??,2N?1(3—92)

??F(u) Fe?u???? 0 ?那么，反变换也可用式(3—93)表示

f(x)?112Fe(0)?NN2N?1(2x?1)u?Fe(u)cos?2Nu?1(2x?1)u?j2N2?Fe(0)?NN2N?1?Fe(u)Re?e?u?1????2xu?u?jj??122N2N?Fe(0)?F(u)Re?e??ee?Nu?1N??2N?112?Fe(0)?Re??Fe(u)?eN?u?1N2N?1u?j2N?e2xu?j2N???2N?1?12?2?????Re???Fe(0)?N?N??N?u?0u?2xu??jj??2N2N?(3—93) ??Fe(u)?e?e????由式(3—93)可见，离散余弦反变换可以从??Fe(u)?e?u?j2N?的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)来表示拉德梅克函数。它可

用下式来表示

R(n,t)?sgn(sin2?t)(3—100)

nx?0? 1sgn(x)?? x?0??1当x=0时，sgn(x) 无定义。

(3—101)

由sin函数的周期性知道R(n,t)也是周期性函数。由式(3—100)可见，

当n=1时，R(n,t)的周期为1；当n=2时R(2,t)的周期为1/2；

1当n=3时，R(3,t)的周期为22；

一般情况下可用下式表示

1??R(n,t)?R?n, t?n?1? n?1,2,??2??(3—102)

拉德梅克函数的波形如图3—9所示。

10 10-110-110-11

R(0,t)

t

R(1,t) t

R(2,t) t

R(3,t) t

0-1t

R(4,t)

图3—9 拉德梅克函数

由图3—9可见，拉德梅克函数有如下一些规律：（１）R(n,t)的取值只有+1和-1。

（２）R(n,t)是R(n-1,t)的二倍频。因此，如果已知最高次数m=n，则其他拉德梅克函数可由脉冲分频器来

产生。

（３）如果已知n，那么, R(n,t)有2n?1个周期，其中0

1k?2t?2n处作取样，则可得

n到一数据序列R(n,k)，k?0,1,2,??,2?1。每一取样序列将与下述矩阵相对应。这里我们取n=3，k=0,1,2,......7。

?1 1 1 1 1 1 1 1??R(0,k)??1 1 1 1?1?1?1?1??R(1,k)???(3—103) ?????1 1?1?1 1 1?1?1?R(2,k)??????1?1 1?1 1?1 1?1?R(3,k)??????采用上述离散矩阵形式就可以用计算机进行灵活处理。

本文来源：https://www.bwwdw.com/article/jw03.html