第七章频域处理
7.4.2二维离散余弦变换?
考虑到两个变量，很容易将一维DCT的定义推广到二维
DCT。其正变换核为
g(x,y,u,v)?2(2x?1)u?(2y?1)v?C(u)C(v)coscos2M2NMN(7-53)
式中，C(u)和C(v)的定义同式（7-48）；x,u=0,1,2,…,M－1；y,v=0,1,2,…,N－1。?
二维DCT定义如下：设f(x, y)为M×N的数字图像矩阵，则
F(u,v)?2MNM?1N?1x?0y?0??(2x?1)u?(2y?1)v?f(x,y)C(u)C(v)coscos2M2N(7-54)
第七章频域处理
式中：x, u=0, 1, 2, …, M－1；y, v=0, 1, 2, …, N－1。?
二维DCT逆变换定义如下：
f(x,y)?2MNM?1N?1u?0v?0??(2x?1)u?(2y?1)v?C(u)C(v)F(u,v)coscos2M2N(7-55)
式中：x,u=0,1,2,…,M－1；y,v=0,1,2,…,N－1。?
类似一维矩阵形式的DCT，可以写出二维DCT的矩阵形式
如下：?
F=GfGT (7-56)?
第七章频域处理
同时，由式(7-55)和式(7-54)可知二维DCT的逆变换核与正变换核相同，且是可分离的，即
g(x,y,u,v)?g1(x,u)g2(y,v)2(2x?1)u?2(2y?1)v??C(u)cos?C(v)cos2M2NMN(7-57)
式中：C(u)和C(v)的定义同式（7-48）；x, u=0, 1, 2, …, M－1；y, v=0, 1, 2, …, N－1。
第七章频域处理
通常根据可分离性，二维DCT可用两次一维DCT来完成，其算法流程与DFT类似，即
f(x,y)?F行[f(x,y)]?F(x,v)转置?F(x,v)?F列[F(x,v)]?F(u,v)?F(u,v)TTT(7-58)
转置第七章频域处理
7.4.3快速离散余弦变换?
离散余弦变换的计算量相当大，在实用中非常不方便，也需要研究相应的快速算法。目前已有多种快速DCT（FCT），在此介绍一种由FFT的思路发展起来的FCT。??
首先，将f(x)延拓为
f(x)??fe(x)????0x=0, 1, 2, …, N-1x=N，N+1, …, 2N-1
(7-59)
按照一维DCT的定义，fe(x)的DCT为?
1F(0)?N?f(x)ex?0N?1(7-60)
第七章频域处理
第七章频域处理
7.1 频域世界与频域变换7.2 傅立叶变换
7.3 频域变换的一般表达式7.4 离散余弦变换
7.5 离散沃尔什哈达玛变换
7.6 用Matrix
第七章频域处理
7.1 频域世界与频域变换
(a)(b)(c)(d)图7-1 任意波形可分解为正弦波的加权和第七章频域处理
振幅AAO基本 正弦波(A＝1, ?＝0)角频率初相位?图7-2 正弦波的振幅A和相位φ
第七章频域处理
A?O(a)fO(b)f图7-3 图7-1（a）波形的频域表示?
(a) 幅频特性；(b) 相频特性
第七章频域处理
时域和频域之间的变换可用数学公式表示如下：
f(f)?A(f),?(f)逆变换正变换(7-1)
为能同时表示信号的振幅和相位，通常采用复数表示法，因此式（7-1）可用复数表示为
f(f)?F(f)逆变换正变换(7-2)
完成这种变换，一般采用的方法是线性正交变换。
第七章频域处理
对二维离散傅立叶变换，则有
P(x,u)?g1(x,u)?e?j2?ux/M(7-45) (7-46)
P(y,v)?g2(x,v)?e?j2?vy/N实践中，除了DFT变换之外，还采用许多其他的正交变换。例如：离散余弦变换、沃尔什-哈达玛变换、K-L变换等，下面将对常用的变换作一简要介绍。
第七章频域处理
7.4 离散余弦变换（DCT）
离散余弦变换（DiscreteCosineTransform，DCT）的变换核
为余弦函数。DCT除了具有一般的正交变换性质外，它的变换阵的基向量能很好地描述人类语音信号和图像信号的相关特征。因此，在对语音信号、图像信号的变换中，DCT变换被认为是一种准最佳变换。近年颁布的一系列视频压缩编码的国际标准建议中，都把DCT作为其中的一个基本处理模块。除此之外，DCT还是一种可分离的变换。?
第七章频域处理7.4.1 一维离散余弦变换?
一维DCT的变换核定义为
2(2x?1)u?g(x,u)?C(u)cosN2N式中，x, u=0, 1, 2, …, N－1；
(7-47)
?1u?0?C(u)??2?其他?1(7-48)
一维DCT定义如下：设{f(x)|x=0, 1, …, N-1}为离散的信号列。
2(2x?1)u?F(u)?C(u)f(x)cos?Nx?02NN?1(7-49)
式中，u, x=0, 1, 2, …, N－1。?
第七章频域处理
将变换式展开整理后，可以写成矩阵的形式，即
F=Gf
其中
（7-50）
?1/N?11?1???2/N?cos(?/2N)cos(3?/2N)?cos((2N?1)?/2N)????G??2/Ncos(?/2N)cos(6?/2N)?cos((2N?1)?/2N)?????????2/Ncos((N?1)?/2N)cos((N?1)(3?/2N)?cos((N?1)(2N?1)?/2N)???????????(7-51)
第七章频域处理一维DCT的逆变换IDCT定义为
f(x)?2(2x?1)u?C(u)F(u)cos?Nu?02NN?1(7-52)
式中，x, u=0, 1, 2, …, N－1。可见一维DCT的逆变换核
与正变换核是相同的。
第七章频域处理
由于Fe(u)和Fo(u)都是4点的DFT，因此，如果对它们再按照
0奇偶进行分组，则有??Fe(0)?Fee(0)?W8Feo(0)??Fe(1)?Fee(1)?W82Feo(1)??0?Fe(2)?Fee(0)?W8Feo(0)?2??Fe(3)?Fee(1)?W8Feo(1)?Fo(0)?Foe(0)?W80Foo(0)??Fo(1)?Foe(1)?W82Foo(1)??0?Fo(2)?Foe(0)?W8Foo(0)?2??Fo(3)?Foe(1)?W8Foo(1)（7-35a）
（7-35b）
第七章频域处理
Fee(0)Fee(1)Feo(0)Feo(1)W802W8Fe(0)Fe(1)Fe(2)Fe(3)Foe(0)Foe(1)Foo(0)Foo(1)W802W8Fo(0)Fo(1)Fo(2)Fo(3)－W－W08－W－W082828图7-8 4点DFT分解为2点DFT的蝶形流程图
第七章频域处理
f (0)W08Fee(0)Fee(1)Feo(0)Feo(1)Foe(0)Foe(1)Foo(0)Foo(1)W08Fe(0)Fe(1)Fe(2)Fe(3)Fo(0)Fo(1)Fo(2)Fo(3)W08F(0)f (4)0－W8W82－W08W81W28F(1)f (2)W08F(2)f (6)f (1)0－W8082－W808W83－W08F(3)F(4)WWf (5)0W－8W820－W81W－8F(5)f (3)W80－W082－W8F(6)f (7)－W28－W38F(7)图7-9 8点DFT的蝶形流程图
第七章频域处理
第一级f (0)f (4)f (2)f (6)N / 4点DF TN / 4点DF T第二级第三级F(0)N / 2点DF TF(1)F(2)F(3)N 点DFTf (1)f (5)f (3)f (7)N / 4点DF TN / 4点DF TF (4)N / 2点DF TF(5)F(6)F (7)图7-10 8点DFT逐级分解框图
第七章频域处理
表7-2 自然顺序与码位倒序（N=8）
第七章频域处理
上述FFT是将f(x)序列按x的奇偶进行分组计算的，称之为时间抽选FFT。如果将频域序列的F(u)按u的奇偶进行分组计算，
也可实现快速傅立叶计算，这称为频率抽选FFT。??
至此，读者应该对傅立叶变换的理论基础及其实现方式有
所了解。对于计算机专业的学生而言，每个人都应该尝试编写快速傅立叶变换的程序。当然，有关傅立叶变换的算法还有很多，网上的FFT算法源代码也非常多，但不建议大家拿来就用。当你得到类似的代码后，一定要认真分析其实现过程和思路，只有这样才能不断地提高编程水平。
第七章频域处理
7.3 频域变换的一般表达式
7.3.1 可分离变换?
二维傅立叶变换可用通用的关系式来表示：
M?1N?1F(u,v)???f(x,y)g(x,y,u,v)x?0y?0M?1N?1u?0v?0(7-36)
f(x,y)???F(u,v)h(x,y,u,v)(7-37)
式中：x,u=0,1,2,…,M－1；y,v=0,1,2,…,N－1；g(x,y,u,v)和h(x,y,u,v)分别称为正向变换核和反向变换核。
第七章频域处理
如果
g(x, y, u, v)=g1(x, u)g2（y, v）?
h(x, y, u, v)=h1(x, u)h2(y, v)
(7-38)(7-39)
则称正、反变换核是可分离的。进一步，如果g1和g2，h1和h2在函数形式上一样，则称该变换核是对称的。?
二维傅立叶变换对是式（7-36）和式（7-37）的一个特殊情况，它们的核为
?uxvy??j2?????MN??uxvy?j2?????MN?g(x,y,u,v)?e?eux?j2?M?evy?j2?Nvyj2?N1h(x,y,u,v)?eMN1?eMuxj2?M1?eN第七章频域处理
可见，它们都是可分离的和对称的。?
如前所述，二维傅立叶变换可以利用变换核的可分离性，用两次一维变换来实现，即可先对f(x,y)的每一行进行一维变换得到F(x,v)，再沿F(x,v)每一列取一维变换得到变换结果F(u,v)。对于其他的图像变换，只要其变换核是可分离的，同样也可用两次一维变换来实现。?
如果先对f(x,y)的每一列进行一维变换得到F(y,u)，再沿F(y,u)每一行取一维变换得到F(u,v)，其最终结果是一样的。该结论对反变换核也适用。
第七章频域处理7.3.2图像变换的矩阵表示?
数字图像都是实数矩阵，设f(x,y)为M×N的图像灰度矩阵，通常为了分析、推导方便，可将可分离变换写成矩阵的形式：
(7-42) (7-43)
F=PfQF=P-1FQ-1
其中，F、f是二维M×N的矩阵；P是M×M矩阵；Q是N×N矩阵。
F(u,v)??x?0M?1N?1y?0?P(x,u)f(x,y)Q(y,v)(7-44)
式中，u=0, 1, 2, …, M－1，v=0, 1, 2, …, N－1。?