教学材料《数字图像》-第3章

3.1概述在实际图像处理中，为了有效、快速地对图像进行处理和分析，常常需要将图像从空间域转换到另一种域（变换域），并利用这种域的特性对图像进行各种快速、方便的处理和分析，将图像的特征在变换域中表现出来，特别是那些空间法无法完成的一些特殊处理，将空间域的处理转换为变换域的处理，不仅可减少计算量，而且可获得更有效的处理，最后再变换回图像空间域以得到所需的效果。这种转换过程称为图像变换。图像变换是许多图像处理和分析技术的基础。本章将介绍几种常用的图像变换方法，包括傅里叶变换、余弦变换、沃尔什变换、哈达码变换、霍特林变换、哈尔变换等。返回3.2傅里叶变换和性质3.2.1一维离散傅里叶变换对一个连续函数

等间隔采样，设共采了N个样本，则可得到1个有限长离散序列。若令x为离散实变量，u为离散频率变量，则可将一维离散傅里叶变换的定义如下。正变换（3.1）逆变换

（3.2）其中，

，称为变换核。

下一页返回3.2傅里叶变换和性质由式（3.1）和式（3.2）可见，给定序列

f(x)，可以求出其傅里叶谱F(x)，反之由傅里叶谱

也可以求出f(x)。离散傅里叶变换对可以简记为

（3.3）离散傅里叶变换的矩阵形式如下。正变换

（3.4）

上一页下一页返回3.2傅里叶变换和性质逆变换

（3.5）一般认为f(x)为实函数，但

是复函数F(u)，可以写成

（3.6）其中，R(u)和I(u)分别F(u)为

的实部和虚部。上式也常写成指数形式

（3.7）

上一页下一页返回3.2傅里叶变换和性质例3.1求图3.1（a）所示序列的离散傅里叶变换。解：由图已知

，则其傅里叶频谱如图3.1（b）所示。

上一页下一页返回3.2傅里叶变换和性质3.2.2一维离散傅里叶变换的性质一维离散傅里叶变换具有如下主要性质。1）线性如果

，

，则

（3.8）2）对称性如果

，则

（3.9）

上一页下一页返回3.2傅里叶变换和性质3）时移性如果

，则

（3.10）4）频移性如果

，则

（3.11）5）卷积定理如果

，

，则

（3.12）

上一页下一页返回3.2傅里叶变换和性质证：由卷积定义，有

（3.13）对

取离散傅里叶变换

上一页下一页返回3.2傅里叶变换和性质

上一页下一页返回3.2傅里叶变换和性质

上一页返回3.3一维快速傅里叶变换3.3.1一维快速傅里叶变换的算法原理由于在数据点n较大时，直接计算傅里叶变换所需的运算次数非常大，实际图像处理中，为了减少计算量，引入快速傅里叶变换法（FFT）。其与原始变换算法的计算量之比是N/log2N，当N很大时，计算量的节省是相当可观的。本节介绍一种“逐次倍乘法”的快速傅里叶变换算法。将一维傅里叶变换式（3.1）改写为

（3.22）

下一页返回3.3一维快速傅里叶变换其中

（3.23）设N为2的正整数次幂，即

（3.24）若令M为正整数，且

（3.25）

上一页下一页返回3.3一维快速傅里叶变换将式（3.25）代入式（3.22），则有

（3.26）若令

（3.27）

（3.28）

上一页下一页返回3.3一维快速傅里叶变换即有

（分成奇数项和偶数项之和）

（3.29）同理，则有

（3.30）即有

上一页下一页返回3.3一维快速傅里叶变换3.3.2一维快速傅里叶变换设计思想和算法实现1）FFT的设计思想由上述FFT算法原理可知，FFT的设计思想是：首先，将原函数分为奇数项和偶数项，通过不断地进行一个奇数和一个偶数的相加（减），最终得到需要的结果。也是说FFT是将复杂的运算变成两个数相加（减）的简单运算的重复。例3.2设对一个函数进行快速傅里叶变换，函数为：

，分成偶数、奇数为

上一页下一页返回3.3一维快速傅里叶变换2）FFT的算法实现要实现上面介绍的FFT快速算法，需要经过两个步骤：计算奇数项和偶数项，将原输入序列按要求重新排序；计算逐次加倍N点FFT变换。

对输入数据的排序可以根据一个简单的位对换规则进行。如用x表示f(x)的1个自变量值，那么它排序后对应的值可通过把x表示成二进制数并左右对换各位得到。注意这里是从左到右的对换而不是求补。例如：N=23=8

上一页下一页返回3.3一维快速傅里叶变换原地址

原顺序

新地址

新顺序000 f(0) 000 f(0)001 f(1) 100 f(4)010 f(2) 010 f(2)011 f(3) 110 f(6)100 f(4) 001 f(1)101 f(5) 101 f(5)110 f(6) 011 f(3)111 f(7) 111 f(7)

上一页下一页返回3.3一维快速傅里叶变换例3.3要计算1个8点的快速傅里叶变换，即N=23=8，已知{f(0)，f(1)，f(2)，f(3)，f(4)，f(5)，f(6)，f(7)}，要求计算：{F(0)，F(1)，F(2)，F(3)，F(4)，F(5)，F(6)，F(7)}。解：利用FFT算法实现如下计算。首先分成奇偶两组：有

{f(0)，f(2)，f(4)，f(6)}；{f(1)，f(3)，f(5)，f(7)}。为了利用递推特性排序，再分成两组：

有

{f(0)，f(4)}，{f(2)，f(6)}；{f(1)，f(5)}，{f(3)，f(7)}。如图3.2所示，这样在第一层先计算4个2点变换，在第2层用以上4个结果计算2个4点变换，在第3层再用以上2个结果计算1个8点变换。图3.3为其具体的计算步骤与公式。

上一页下一页返回3.3一维快速傅里叶变换FFT的总计算量为：乘法次数为

，加法次数为

，而直接计算DFT需要的计算量为：乘法次数为

，加法次数为N(N-1)。当N=2

048时，DFT需要4

194

304次乘法运算，而FFT只需要11

264次乘法运算，二者之比为

。可见，当N较大时，FFT算法节省的运算时间是相当惊人的。

上一页下一页返回3.3一维快速傅里叶变换3.3.3一维快速傅里叶反变换对比一维DFT（离散傅里叶变换）与一维IDFT（离散傅里叶逆变换）的定义式，只要将上述FFT算法中W因子用其共轭代替，并将最后结果乘以1/N，就是计算IDFT的快速算法。即先对式（3.2）求复共轭两边同除以N得到

（3.31）然后再求

复共轭并两边同乘以N得到所需的反变换f(x)。

上一页返回3.4二维离散傅里叶变换3.4.1二维离散傅里叶变换对一个连续函数f(x,y)

等间隔采样可得到1个离散矩阵序列，设以M×N长方形网格采样，共采了M×N个样本，则这个离散矩阵可表示为

也即可得到一幅M×N数字图像

下一页返回3.4二维离散傅里叶变换其二维离散傅里叶变换定义为

（3.32）其逆变换定义为

（3.33）式（3.32）与式（3.33）构成二维离散傅里叶变换对，记为

（3.34）

上一页下一页返回3.4二维离散傅里叶变换

上一页下一页返回3.4二维离散傅里叶变换

上一页下一页返回3.4二维离散傅里叶变换3.4.2二维离散傅里叶变换的性质二维离散傅里叶变换的主要性质有以下几点。1）平移性若

（3.42）则

（3.43）

（3.44）式（3.43）表明将f(x,y)

与一个指数函数相乘就相当于把其变换后的频域中心移动到新的位置；式（3.44）表明将F(u,v)

与一个指数函数相乘就相当于把其反变换后的空域中心移动到新的位置。同时，对f(x,y)

的平移不影响其傅里叶变换的幅值。

上一页下一页返回3.4二维离散傅里叶变换2）周期性和对称性（1）周期性质。若

且周期为N，则有

（3.45）同理，反变换也具有周期性质。

（3.46）此性质表明，F(u,v)的周期长度为N，只需根据在任一周期里的N个值的变换就可将F(u,v)在频域里完全确定。同样结论也对f(x,y)

在空域成立。

上一页下一页返回3.4二维离散傅里叶变换（2）共轭对称性。若f(x,y)为实函数，且

则其傅里叶变换具有共轭对称性，即

（3.47）

（3.48）其中，

为

的复共轭。

上一页下一页返回3.4二维离散傅里叶变换（3）中心对称性（平均值）。对于一个二维离散时间信号，其平均值可以用下式表示。

（3.49）由傅变定义得到

时的变换值为

（3.50）故有

（3.51）

上一页下一页返回3.4二维离散傅里叶变换3）线性若有

则

（3.52）但通常

（3.53）即傅里叶变换对加法具有线性分配性，但对乘法不具有。此结论对傅里叶反变换同样成立。

上一页下一页返回3.4二维离散傅里叶变换4）比例尺度变换性质对比例因子a和b，若有

（3.54）则

（3.55）5）旋转性质若有

（3.56）则

（3.57）

上一页下一页返回3.4二维离散傅里叶变换6）可分离性二维傅里叶变换定义式可用可分离的形式表示如下。

（3.58）

（3.59）

上一页下一页返回3.4二维离散傅里叶变换其中，

F(x,

v)为对y的一维傅里叶变换，即是先沿着f(x,

y)

的每一列进行的傅里叶变换，然后再对中间结果F(x,v)

的每一行作傅里叶变换即可得到F(u,

v)，颠倒次序后（先行后列）结论同样成立。即一个二维离散傅里叶变换可以运用连续2次一维离散傅里叶变换来实现。同理。对于二维傅里叶反变换同样具有可分离性。先沿着F(u,

v)

的每一列进行的傅里叶反变换，然后再对中间结果的每一行作傅里叶反变换即可得到f(x,

y)。

可分离性可用图形表示如图3.4所示。

上一页下一页返回3.4二维离散傅里叶变换7）卷积2个二维函数的连续卷积定义为

（3.60）2个二维函数的离散卷积定义为

（3.61）若有

，则卷积定理为

（3.62）

（3.63）

上一页下一页返回3.4二维离散傅里叶变换8）相关2个二维函数的连续相关定义为

（3.64）2个二维函数的离散相关定义为

（3.65）若有

，则相关定理为

（3.66）

（3.67）

上一页下一页返回3.4二维离散傅里叶变换9）空间重采样二维采样定理：若设2Wu和2Wv分别为能完全包含R的最小长方形在u和v方向上的长度，并通过选择采样间隔使之满足

；

，就能由采样完全重建f(x,

y)。同时，空间域和频域抽样点之间的关系为

（3.68）保证了在空域和频域中都可以由M×N个均匀分布的采样来重建完整的二维周期。

上一页下一页返回3.4二维离散傅里叶变换3.4.3二维快速离散傅里叶变换基于二维离散傅里叶变换的分离性，二维离散FFT算法可以用两个一维FFT算法来实现。为此令

（3.69）则有

（3.70）对于每个x值，式（3.70）就是一个针对变量y的一维离散傅里叶变换，而式（3.69）则是一个针对变量x的一维离散傅里叶变换。因此，利用式（3.69）和式（3.70）以及前面介绍的一维FFT可以方便地实现二维FFT，其过程如图3.5所示。

上一页下一页返回3.4二维离散傅里叶变换需要指出的是，式（3.70）的另一种分离方式为

（3.71）令

（3.72）则式（3.71）成为

（3.73）因而得到另一种实现二维FFT的方法，如图3.6所示。例3.4灰度图像及其傅里叶变换谱，如图3.7所示。

上一页下一页返回3.4二维离散傅里叶变换3.4.4可分离图像变换以上讨论的二维离散傅里叶变换实际上是一类更广泛的变换——可分离变换中的一个特例。一般情况下，二维正变换和逆变换可分别表示为

（3.74）

（3.75）其中，g(x,y,u,v)和h(x,y,u,v)分别称为正变换核和逆变换核，它们只依赖于x,y,u,v，而f(x,y)与

F(u,v)值无关。如果

（3.76）

上一页下一页返回3.4二维离散傅里叶变换则称正变换核是可分离的。如果g1(x,u)与

g2(y,v)函数形式一样，则称正变换核是对称的。此时式（3.76）可写成

（3.77）前面介绍的二维离散傅里叶变换是可分离变换的一个特例。例如傅里叶变换的正变换核

（3.78）就是可分离的和对称的。上述关于正变换核的讨论同样适用于逆变换核，这里不再赘述。具有可分离变换核的二维变换的重要特点就是可以分成两个步骤计算，每个步骤用一个一维变换来实现。以下将要介绍的离散余弦变换、沃尔什变换和哈达玛变换都是可分离变换。

上一页返回3.5离散余弦变换3.5.1一维离散余弦变换傅里叶变换的一个最大的问题是：它的参数都是复数，在数据的描述上相当于实数的两倍，不易计算。因此，希望有一种能够达到相同功能但数据量又不大的变换，于是产生了DCT变换。一维离散余弦变换（DCT）及其逆变换（IDCT）由以下公式定义。

（3.79）其中

（3.80）一维DCT变换实际上就是将信号

分解成直流分量

、基波分量

和各次谐波分量（u＞1），使信号的分析从空域转移到频域。

下一页返回3.5离散余弦变换3.5.2一维快速离散余弦变换算法与傅里叶变换一样，离散余弦变换既可以由定义直接计算，也可以采用快速离散余弦变换（FDCT）算法来实现。FDCT有两种算法：一种是利用FFT的快速算法，另一种是基于代数分解的快速算法。下面分别予以介绍。1）利用FFT的快速算法比较傅里叶变换核与余弦变换核，可发现，余弦变换核实际上就是傅里叶变换核的实部。而变换计算中的乘法运算就是f(x)

与变换核的乘法运算。因此，一种DCT算法就是先对f(x)

执行FFT，然后对其取实部就可以了。由一维离散余弦变换的定义式，有

（3.81）

上一页下一页返回3.5离散余弦变换于是离散余弦变换就可以利用FFT算法计算式（3.81）中的和式了。同理，由逆变换定义，有

（3.83）其中

（3.84）同样可以利用FFT算法计算式（3.83）中的和式。

上一页下一页返回3.5离散余弦变换2）基于代数分解的快速算法利用FFT的FDCT算法的缺点是：FFT中与DCT毫不相干的复数运算是多余的，因而可以想象去掉这些运算的算法一定比利用FFT的更快。与FFT类似，利用代数分解的FDCT就是利用余弦函数的周期性以及正弦函数与余弦函数之间的关系，同时合理安排计算次序来实现的。代数分解方法如下。（1）蝶形图用小圆圈表示操作数，用连接圆圈的直线表示操作数的流动，用直线上方或下方的函数表达式表示操作数在流向前方时需乘的加权因子。根据FFT的蝶形图规定，它是2的幂，且蝶形图的级数是2log2N。

上一页下一页返回3.5离散余弦变换

上一页下一页返回3.5离散余弦变换（5）余下的操作数流向用加权因子确定具体的代数分解来做。下面以N

=

4和N

=

8为例来说明。N

=

4（a0，a1不计）时，DCT计算式如下：

（3.85）

（3.86）

上一页下一页返回3.5离散余弦变换

（3.87）

（3.88）上述计算式可以用图3.8所示的蝶形图表示出来，其中

上一页下一页返回3.5离散余弦变换同理可得N=8的FDCT的流程图，如图3.9所示，其中3.5.3二维离散余弦变换二维离散余弦正变换及其逆变换定义如下。正变换

（3.89）

上一页下一页返回3.5离散余弦变换逆变换

（3.90）其中

（3.91）

（3.92）由于二维离散余弦变换的可分离性，二维DCT可以用连续2次一维DCT来实现。

上一页下一页返回3.5离散余弦变换例3.5灰度图像及其离散余弦变换频谱。图3.10（a）为一幅原始图像，图3.10（b）为该图像的离散余弦变换频谱。在图3.10（b）中可以看到图像的低频能量都集中在左上角区域，而高频能量集中在右下角区域。与例3.4的离散傅里叶频谱图比较，可以发现高低频的能量集中在不同的区域，这主要是因为离散傅里叶变换的变换是复数，而离散余弦变换的变换核实际上是取其实部。

上一页下一页返回3.5离散余弦变换3.5.4离散余弦变换的应用余弦变换主要用于图像的压缩，如目前的国际压缩标准的JPEG格式中就用到了DCT变换。其具体的做法与DFT相似，给高频系数大间隔量化，低频部分小间隔量化。它比傅里叶变换有更强的信息集中能力，可以提高编码效率。具体在JPEG图像压缩算法中，首先将输入图像划分为8×8的方块，然后对每一个方块执行二维离散余弦变换，最后将变换得到量化的DCT系数进行编码和传送，形成压缩后的图像格式。在接收端，将量化的DCT系数进行解码，并对每个8×8方块进行二维IDCT，最后将操作完成后的块组合成一幅完整的图像。

上一页下一页返回3.5离散余弦变换8×8的方块经正交变换后得到的DCT矩阵

的左上角代表图像的低频分量，右下角代表图像的高频分量，F(0,

0)

为直流分量（DC）。DCT改变了信号能量的分布方式，使信号能量的分布范围主要集中于低频区。换言之，DCT矩阵F中大多数的DCT系数的值非常接近于零，如果舍弃这些接近于零的DCT系数值，就可以节约大量的存储空间，而在重构图像时又不会使画面质量显著下降。例3.6DCT在图像压缩中的应用。图3.11（a）是未经压缩的原始图像，图3.11（b）是采用JPEG方式压缩存储的图像，可以看出图3.11（b）基本保留了原图的内容信息，看不出有什么损失。但是图3.11（b）的文件大小只是图3.11（a）的1/6，可见离散余弦变换在图像压缩上发挥了很大的作用。

上一页返回3.6沃尔什变换离散傅里叶变换和离散余弦变换在快速算法中要用到复数乘法及三角函数乘法，这些运算占用时间仍然较多。在某些应用领域，需要更有效、更便利的方法。沃尔什（Walsh）变换就是其中一种。下面可以看到，由于沃尔什变换核矩阵中只有+1

和-1

两种元素，因而在计算沃尔什变换过程中只有加减运算而没有乘法运算，从而大大提高了运算速度。这一点对图像处理来说是至关重要的，特别是在实时处理大量数据时，沃尔什变换更加显示出其优越性。同时+1

和-1

与数值逻辑的两个状态相对应，故更适用于计算机实现，同时占用空间少，且计算简单，在图像的正交变换中得到了广泛的应用。

下一页返回3.6沃尔什变换

上一页下一页返回3.6沃尔什变换

上一页下一页返回3.6沃尔什变换

（3.97）而n=3，N=8时的变换矩阵G8为

（3.98）

上一页下一页返回3.6沃尔什变换3.6.2二维离散沃尔什变换将一维的情况推广到二维，可以得到二维沃尔什正变换核和逆变换核分别为

（3.99）

（3.100）相应的二维离散沃尔什正变换和逆变换为

（3.101）

（3.102）

上一页下一页返回3.6沃尔什变换3.6.3快速离散沃尔什变换FWT沃尔什变换可用类似FFT算法的快速计算，只需将那里的指数项设为1即可。与式（3.29）和式（3.30）相对应，有

（3.105）

（3.106）由于二维沃尔什正变换核和逆变换核只是依赖于x,

y,

u,

v而与f(x,

y)

或F(u,

v)

的值无关。这些核可看做1组基本函数，一旦图像尺寸确定，这些核函数也完全确定。图3.12给出N=4时沃尔什基本函数的图示，其中白色表示1，黑色表示-1。每个大方块对应固定的u和v，内部小方块对应的x和y从0变到3。可借助该图来计算4×4图像的沃尔什正变换。例如要计算W(0,

0)，只需将图像与对应u

=

v

=

0的方块进行点点相乘再将结果相加，最后除以4就可以了。

上一页返回3.7哈达玛变换3.7.1一维离散哈达玛变换

一维离散哈达玛正变换核为

（3.107）其中，指数上的求和是以2为模的，bk(z)是z的二进制表示的第k位。

N=2n是哈达玛变换的阶数。则一维离散哈达玛正变换为

（3.108）

下一页返回3.7哈达玛变换同沃尔什变换类似，由哈达玛变换核组成的矩阵是一个对称矩阵并且其行和列正交，故其正变换核与逆变换核只差一个常数项1/N，所以有以下变换。一维离散哈达玛逆变换核为

（3.109）一维离散哈达玛逆变换为

（3.110）上一页下一页返回3.7哈达玛变换3.7.2二维离散哈达玛变换将一维的情况推广到二维，可以得到二维哈达玛正变换核和逆变换核为

（3.111）

（3.112）相应的二维离散哈达玛正变换和逆变换为

（3.113）上一页下一页返回3.7哈达玛变换

（3.114）由式（3.111）与式（3.112）可见

（3.115）

（3.116）可知哈达玛正变换核和逆变换核都是分离和对称的。因此，二维离散哈达玛变换可以由连续2次一维离散哈达玛变换来进行。上一页下一页返回3.7哈达玛变换3.7.3快速哈达玛变换算法FHT由于二维变换可以用两步一维变换来实现，所以这里仅讨论一维快速哈达玛变换算法。设

N=2n，由一维离散哈达玛变换式（3.108）可写成矩阵形式。

（3.117）其中

（3.118）上一页下一页返回3.7哈达玛变换

（3.119）Hn是N阶哈达玛矩阵，具有如下重要特性：

（3.120）其中，I为单位矩阵。N=2（n=1）阶哈达玛矩阵为

（3.121）上一页下一页返回3.7哈达玛变换N（N=2n）阶哈达玛矩阵为

（3.122）例如，N=4阶哈达玛矩阵为

（3.123）上一页下一页返回3.7哈达玛变换利用矩阵分块技术或矩阵因子分解技术，便可导出快速哈达玛变换（FHT）算法。下面以

N=23=8为例来进行说明。

（3.124）

（3.125）上一页下一页返回3.7哈达玛变换

（3.126）

（3.127）引入记号

（3.128）上一页下一页返回3.7哈达玛变换则式（3.126）和式（3.127）可以写成

（3.129）

（3.130）再将上述两式各一分为二，可得到如下4个关系式

（3.131）上一页下一页返回3.7哈达玛变换

（3.132）

（3.