第三章图像变换

2023/1/111第三章图像变换2023/1/112本章主要内容1.连续函数的傅立叶变换2.卷积和相关3.离散傅立叶变换4.二维离散傅立叶变换的基本性质5.离散卷积和离散相关6.快速傅立叶变换7.其他离散图像变换2023/1/1131.连续函数的傅立叶变换傅立叶变换是最早研究与应用的酉变换60年代出现快速傅立叶变换傅立叶变换域也称为频域2023/1/1141.连续函数的傅立叶变换

设为一实变量x的连续、可积函数，则其傅立叶变换为：反变换为:2023/1/1151.连续函数的傅立叶变换

一般是一个复函数，可以表示为：其中、分别是的实部和虚部。2023/1/1161.连续函数的傅立叶变换还可以表示为指数形式：其中、分别是的傅立叶谱和相角。2023/1/1171.连续函数的傅立叶变换称为的能量谱或功率谱称为相位谱称为幅度谱则：2023/1/1181.连续函数的傅立叶变换一维傅立叶变换举例方波信号：经过傅立叶变换后：2023/1/1191.连续函数的傅立叶变换如果二维连续函数满足可积条件,则其傅立叶变换为:反变换为:2023/1/11101.连续函数的傅立叶变换对于二维方波信号傅立叶变换为：幅度：2023/1/11112.卷积和相关2.1卷积和卷积定理卷积积分：如果函数y(t)满足下列关系式则称函数y(t)为函数x(t)

和h(t)

的卷积卷积积分的图解表示：11x(t)th(t)t1/21*x(t)h(t)2023/1/11122.卷积和相关2.1卷积和卷积定理卷积积分的图解表示（续）：2y(t)1h(-)1/2-1折迭位移h(t-)1/2th(t1-)x()1111x()*相乘t1t积分1/22023/1/11132.卷积和相关2.1卷积和卷积定理卷积积分的步骤：1折迭：把h()相对纵轴作出其镜像2位移：把h(-)移动一个t

值3相乘：将位移后的函数h(t-)乘以

x()4积分：h(t-)和

x()乘积曲线下的面积即为

t时刻的卷积值卷积积分的另一种形式：2023/1/11142.卷积和相关2.1卷积和卷积定理包含脉冲函数的卷积：即x(t)或h(t)中有一个为脉冲函数，则它们的卷积是一种最简单的卷积x(t)h(t)*x(t)atA-T0T0h(t)tA-T0T0t2023/1/11152.卷积和相关2.1卷积和卷积定理卷积定理：如果x(t)

和h(t)

的富里叶变换分别为X(f)

和H(f),则x(t)*h(t)的富里叶变换为X(f)H(f)。即卷积定理的简单推导：2023/1/11162.卷积和相关2.2相关和相关定理频率卷积定理：如果x(t)

和h(t)

的傅立叶变换分别为X(f)

和H(f),则x(t)h(t)的傅立叶变换为X(f)*H(f)。即相关：如果函数z(t)满足下列关系式则称函数z(t)为函数x(t)

和h(t)

的相关函数2023/1/11172.卷积和相关2.2相关和相关定理

相关积分的计算步骤：1位移：把h()移动一个t

值2相乘：将位移后的函数h(t+)乘以

x()3积分：h(t+)和

x()乘积曲线下的面积即为

t时刻的相关值相关定理：如果x(t)

和h(t)

的富里叶变换分别为X(f)

和H(f),则x(t)

和h(t)的相关积分为X(f)H*(f)。即其中，X*(f)为X(f)的复共轭2023/1/11183.离散傅立叶变换3.1一维离散傅立叶变换

一维离散傅立叶变换公式为：逆变换为：2023/1/11193.离散傅立叶变换3.2二维离散傅立叶变换

对于二维傅立叶变换，其离散形式为：逆变换为：幅谱(频谱)、相谱：2023/1/11203.离散傅立叶变换3.2二维离散傅立叶变换

离散傅立叶变换的显示2023/1/11213.离散傅立叶变换3.2二维离散傅立叶变换

离散傅立叶变换的显示变换中心移动到原点2023/1/11223.离散傅立叶变换3.2二维离散傅立叶变换

图像傅立叶变换示例:注意低频(背景)和高频(细节、边缘)信息的分布2023/1/11233.离散傅立叶变换3.2二维离散傅立叶变换

2023/1/11243.离散傅立叶变换3.2二维离散傅立叶变换

2023/1/11254.二维离散傅立叶变换的基本性质4.1可分离性

由可分离性可知，一个二维傅立叶变换可分解为两步进行，其中每一步都是一个一维傅立叶变换。先对f(x,y)按行进行傅立叶变换得到F(x,v)，再对F(x,v)按列进行傅立叶变换，便可得到f(x,y)的傅立叶变换结果，如下图所示。显然对f(x,y)先按列进行离散傅立叶变换，再按行进行离散傅立叶变换也是可行的。2023/1/11264.二维离散傅立叶变换的基本性质4.1可分离性

正变换:反变换:2023/1/11274.二维离散傅立叶变换的基本性质4.2平移性

平移性质表明，只要将f(x,y)乘以因子(－1)x+y，再进行离散傅立叶变换，即可将图像的频谱原点（0，0）移动到图像中心（M／2,N／2）处。下图是简单方块图像平移的结果。2023/1/11284.二维离散傅立叶变换的基本性质4.2平移性

(a)原图像；（b）无平移的傅立叶频谱；（c）平移后的傅立叶频谱(a)(b)(c)2023/1/11294.二维离散傅立叶变换的基本性质4.3线性特性这一性质可使节约我们求傅立叶变换的时间2023/1/11304.二维离散傅立叶变换的基本性质4.4比例尺性质当a=b=-1:2023/1/11314.二维离散傅立叶变换的基本性质4.5周期性和共轭对称性

周期性：2023/1/11324.二维离散傅立叶变换的基本性质4.5周期性和共轭对称性

共轭对称性：2023/1/11334.二维离散傅立叶变换的基本性质4.5周期性和共轭对称性

应用:1.图形的频谱分析和显示2.图像中心化2023/1/11344.二维离散傅立叶变换的基本性质4.6旋转性质空间域坐标变换为：空间频率域坐标变换为：则:2023/1/11354.二维离散傅立叶变换的基本性质4.6旋转性质傅立叶变换的旋转性2023/1/11364.二维离散傅立叶变换的基本性质4.7微分性质

若:

则:2023/1/11374.二维离散傅立叶变换的基本性质4.8平均值性质

二维离散函数的平均值定义为：2023/1/11384.二维离散傅立叶变换的基本性质4.8平均值性质

二维离散函数的傅立叶变换的平均值定义为：可知：2023/1/11395.离散卷积和离散相关5.1离散卷积和离散卷积定理

离散卷积的定义:由下面的求和公式给出这里，x(kT)

和h(kT)

都是周期为T

的周期函数。离散卷积的表示:和连续函数的卷积一样，离散卷积通常写作: 2023/1/11405.离散卷积和离散相关5.1离散卷积和离散卷积定理

离散卷积的计算步骤:和连续函数的卷积的计算步骤类似，离散卷积也可以用下面几步来计算：1折迭：把h(iT)相对纵轴作出其镜像2位移：把h(-iT)移动一个kT

值3相乘：将位移后的函数h(kT-iT)乘以

x(iT)4积分：h(kT-iT)和

x(iT)在各个离散点的乘积的和即为

k时刻的卷积值离散卷积的另一种形式：2023/1/11415.离散卷积和离散相关5.1离散卷积和离散卷积定理

离散卷积和连续卷积的关系有限长波形的离散卷积：仍考虑前面的两个连续函数h(t)1/21/22ty(t)P=6N=92y(t)N=91/2th(t)Q=6N=9x(t)t12023/1/11425.离散卷积和离散相关5.1离散卷积和离散卷积定理

离散卷积和连续卷积的关系有限长波形的离散卷积：N=111/2th(t)Q=6N=11ty(t)N=11P=6x(t)tN=112023/1/11435.离散卷积和离散相关5.1离散卷积和离散卷积定理

离散卷积和连续卷积的关系有限长波形的离散卷积：从上面我们可以看到，周期的选择对离散卷积的影响。如果周期选择的太小，则离散卷积对连续卷积的近似是很差的。原因是周期太小，则两个函数的输出会发生重迭。离散卷积的周期选择公式：要使离散卷积近似于连续卷积，则周期必须满足下面的公式：其中，P是函数x(t)

的周期，Q为函数h(t)

的周期。比例系数：离散卷积和连续卷积之间相差一个比例系数T。2023/1/11445.离散卷积和离散相关5.1离散卷积和离散卷积定理

离散卷积定理:离散卷积定理：类似于连续富里叶变换，卷积公式的离散富里叶变换产生了离散卷积定理。定理的表示如下：

也就是说，两个周期为N的抽样函数，它们的卷积的离散富里叶变换等于它们的离散富里叶变换的乘积。离散卷积定理的意义：有了离散卷积定理，我们就可以使用后面将要介绍的快速富里叶算法来计算离散卷积。2023/1/11455.离散卷积和离散相关5.2离散相关和离散相关定理

离散相关的定义：离散相关可以用下面的求和公式来表示

这里，x(kT)、h(kT)、z(kT)都是周期函数。和连续的情况一样，离散相关和离散卷积的差别就在于不需要折迭运算。离散相关定理：2023/1/11466.快速傅立叶变换矩阵方程：考虑离散傅立叶变换

上面的式子代表了N个方程的计算，为方便表示，我们引入下面一个记号。

如果

N=4，则方程可写为：2023/1/11476.快速傅立叶变换矩阵表示：或者表示成：矩阵的计算次数：要完成矩阵的运算，需要做N*N

次复数的乘法和N(N-1)次复数加法。2023/1/11486.快速傅立叶变换

改写矩阵：这是因为：例如：N=4，n=2，k=3,则2023/1/11496.快速傅立叶变换矩阵分解因子：注：上面的列矢量x(n)

的行顺序发生了改变。乱序后的列矢量：用下面的符号标记乱序后的列矢量2023/1/11506.快速傅立叶变换计算次数：将矩阵分解因子后，计算需要分两步来进行。第一步：其中:一次乘法和一次加法一次乘法和一次加法一次加法一次加法2023/1/11516.快速傅立叶变换计算次数：(第二步)其中:一次乘法和一次加法一次乘法和一次加法一次加法一次加法而:2023/1/11526.快速傅立叶变换计算次数：经过矩阵分解后，计算方程总共需要四次复数乘法和八次复数加法。而未经分解的矩阵计算，总共需要十六次复数乘法和十二次复数加法。效率：因为计算时间主要取决于复数乘法的计算次数，所以减少复数乘法的次数就是FFT算法效率高的原因。基2的FFT算法的原理：对于的FFT算法，就是要把一个N*N的矩阵，分解为(其中每个都是N*N)个矩阵。使被分解后的每一个矩阵具有复数乘法和复数加法最少的特性。2023/1/11536.快速傅立叶变换基2的FFT算法的效率：对于的FFT算法，所需的计算次数为：乘法次数：加法次数：普通算法的效率：所需的计算次数为：乘法次数：加法次数：两种算法的效率之比：2023/1/11546.快速傅立叶变换乱序重排：经过矩阵分解后，计算所得到的是一个乱序的列矢量，这种乱序是分解过程中固有的，需要经过重新排列。1、二进制表示：将列矢量的自变量表示成二进制。2、位序颠倒：将列矢量的自变量二进制码的位序颠倒。2023/1/11556.快速傅立叶变换信号流程图：前面矩阵分解计算的过程可以用下面的信号流程图表示出来：数据数组数组1数组2x0(k)x1(k)x2(k)x1(0)x1(3)x1(2)x1(1)x0(0)x0(3)x0(2)x0(1)x2(0)x2(3)x2(2)x2(1)w0w0w2w2w0w2w1w32023/1/11566.快速傅立叶变换对信号流程图的几点说明：1、传输路径：进入计算数组的每个节点有两条实线，它们表示从上一列节点来的两条传输路径。2、传输路径的权值：每条传输路径都带有相应的权值。如果在某条传输路径上没有标记权值，则缺省权值为1。3、数组的计算：从两条传输路径进到一个节点的两结果要相加起来。2023/1/1157数据数组x0(0)x0(3)x0(2)x0(1)x0(4)x0(7)x0(6)x0(5)x0(8)x0(11)x0(10)x0(9)x0(12)x0(15)x0(14)x0(13)x1(0)x1(3)x1(2)x1(1)x1(4)x1(7)x1(6)x1(5)x1(8)x1(11)x1(10)x1(9)x1(12)x1(15)x1(14)x1(13)x2(0)x2(3)x2(2)x2(1)x2(4)x2(7)x2(6)x2(5)x2(8)x2(11)x2(10)x2(9)x2(12)x2(15)x2(14)x2(13)x3(0)x3(3)x3(2)x3(1)x3(4)x3(7)x3(6)x3(5)x3(8)x3(11)x3(10)x3(9)x3(12)x3(15)x3(14)x3(13)x4(0)x4(3)x4(2)x4(1)x4(4)x4(7)x4(6)x4(5)x4(8)x4(11)x4(10)x4(9)x4(12)x4(15)x4(14)x4(13)对偶节点对对偶节点对对偶节点对对偶节点对2023/1/11586.快速傅立叶变换对偶节点：在前面的图中的每一纵列中，总可以找到这样的两个点，它们的传输路径来自前一列中的同一对节点，而且这两个节点不会用来计算其它的任何节点。我们把这样的两个点称为对偶节点。例如，x1(0)

和x1(8)，它们都用x0(0)

和x0(8)

来计算。可以用

x0(0)

和x0(8)同时计算出x1(0)

和x1(8)。对偶节点的间隔：用l表示数组的下标，在l=1的列中，对偶节点（例如x1(0)

和x1(8)）之间的距离为K=8=N/2l，在l=2的列中，对偶节点（例如x2(8)

和x2(12)）之间的距离为K=4=N/22，同样，在l=3的列中，对偶节点之间的距离为K=2=N/23，在l=4的列中，对偶节点之间的距离为K=1=N/24。所以，对偶节点的间隔为：2023/1/11596.快速傅立叶变换

对偶节点对的计算次数：一个对偶节点对的计算只需要一次复数乘法。一般地讲，如果在某一节点上的加权系数为

Wp，则在其对偶节点上的加权系数就是Wp+N/2，因为Wp=-Wp+N/2，所以计算对偶节点对，只需一次复数乘法。

对偶节点对的计算公式：任何一个对偶节点对的计算，都可以用下面的一对公式来给定2023/1/11606.快速傅立叶变换

Wp

的确定：每个节点的加权系数可以通过下面的方法得到1、把指数k

写成位的二进制数；2、把这个二进制数右移-l

位，并把左边空出的位置补为零；3、将右移后的

位二进制数的位序颠倒，其结果就是P

值；

例如，前面图中的节点x3(8)

，由于

=4，k=8，l=3，于是k写成

位的二进制数就是1000，将这个二进制数右移-l=4-3=1位，并将左边空出的位置上补零，结果是0100，然后把位序颠倒。得到0010，这就是十进制的整数2，所以p

值等于2。2023/1/1161

FFT的整序：整序的方法在前面已经提到过，就是将最后得到的计算数组的指数n先写成二进制形式，再进行位序颠倒。x4(0000)x4(0001)x4(0010)x4(0011)x4(0100)x4(0101)x4(0110)x4(0111)x4(1000)x4(1001)x4(1010)x4(1011)x4(1100)x4(1101)x4(1110)x4(1111)x(0001)x(0010)x(0011)x(0100)x(0101)x(0110)x(0111)x(1000)x(1001)x(1010)x(1011)x(1100)x(1101)x(1110)x(1111)0123456789101112131415x(0000)2023/1/11626.快速傅立叶变换FFT的计算流程图：输入数据x(k)N=2,NU=预置l=1N2=N/2NU1=-1k=02023/1/1163流程图：M=k/2NU1的整数P=IBR(M)T1=Wpx(k+N2)x(k+N2)=x(k)-T1x(k)=x(k)+T1K=k+1否I=I+1l>?否是K=k+N2K<=N-1是否l=l+1,N2=N2/2NU1=NU1-1,k=0I=N2?①I=1是2023/1/11646.快速傅立叶变换流程图：是否①I<=kT3=x(k)x(k)=x(i)x(i)=T3K=N-1?是结束k=k+1I=IBR(k)否2023/1/11656.快速傅立叶变换另一个推导（1）：记则有：单位园表示：

W40

W41

W42

W43

N=4时W的值

W80

W82

W83

N=8时W的值

W81

W84

W85

W86

W87

2023/1/11666.快速傅立叶变换WNux的性质：(1)对称性：(2)周期性：(3)可分性：2023/1/11676.快速傅立叶变换另一个推导（2）：傅立叶变换：需要N次复数乘法，N-1次复数加法。因此总共需要N2次复数乘法，N(N-1)次复数加法。1965年，Cooley和Tukey提出快速算法，算法时间复杂度为Nlog2N。2023/1/11686.快速傅立叶变换设N=2m，f(x)的定义域分为偶数部分和奇数部分，即f(2x)和f(2x+1)记为：u=0,1,2,…,N/2-12023/1/1169对于N=N/2,N/2,…,N-1由Fe(u)和Fo(u)的原式，它们以N/2为周期：而由W的性质：所以：2023/1/11706.快速傅立叶变换FFT变换蝶形图：2023/1/11716.快速傅立叶变换奇偶分组和比特倒序2023/1/11727.其他离散图像变换7.1离散沃尔什-哈达玛变换（WHT）沃尔什函数

沃尔什函数是1923年由美国数学家沃尔什提出的。沃尔什函数系是一完备正交函数系，其值只能取＋1和－1。从排列次序上可将沃尔什函数分为三种定义方法：一种是按照沃尔什排列来定义（按列率排序）；另一种是按照佩利排列来定义（按自然排序）；第三种是按照哈达玛排列来定义。由于哈达玛排序的沃尔什函数是由2n（n=0，1，2，…）阶哈达玛矩阵（HadamardMatrix）得到的，而哈达玛矩阵的最大优点在于它具有简单的递推关系，即高阶矩阵可用两个低阶矩阵的克罗内克积求得，因此在此只介绍哈达玛排列定义的沃尔什变换。2023/1/11737.其他离散图像变换7.1离散沃尔什-哈达玛变换（WHT）

N=2n(n=0,1,2,…)阶哈达玛矩阵每一行的符号变化规律对应于某一个沃尔什函数的符号变化规律，即N=2n(n=0,1,2,…)阶哈达玛矩阵的每一行对应于一个离散沃尔什函数，哈达玛矩阵与沃尔什函数系不同之处仅仅是行的次序不同。2n阶哈达玛矩阵有如下形式：2023/1/11747.其他离散图像变换7.1离散沃尔什-哈达玛变换（WHT）哈达玛矩阵的阶数是按N＝2n(n＝0,1,2,…)规律排列的，阶数较高的哈达玛矩阵，可以利用矩阵的克罗内克积运算，由低阶哈达玛矩阵递推得到，即2023/1/11757.其他离散图像变换7.1离散沃尔什-哈达玛变换（WHT）

矩阵的克罗内克积(KroneckerProduct)运算用符号记作A⊙B，其运算规律如下：设2023/1/11767.其他离散图像变换7.1离散沃尔什-哈达玛变换（WHT）

则

2023/1/11777.其他离散图像变换7.1离散沃尔什-哈达玛变换（WHT）2.离散沃尔什-哈达玛变换

一维离散沃尔什变换定义为一维离散沃尔什逆变换定义为

式中，Walsh(u,x)为沃尔什函数。若将Walsh(u,x)用哈达玛矩阵表示，并将变换表达式写成矩阵形式，则上式分别为2023/1/11787.其他离散图像变换7.1离散沃尔什-哈达玛变换（WHT）和式中，［HN］为N阶哈达玛矩阵。2023/1/11797.其他离散图像变换7.1离散沃尔什-哈达玛变换（WHT）

由哈达玛矩阵的特点可知，沃尔什-哈达玛变换的本质上是将离散序列f(x)的各项值的符号按一定规律改变后，进行加减运算，因此，它比采用复数运算的DFT和采用余弦运算的DCT要简单得多。

2023/1/11807.其他离散图像变换7.1离散沃尔什-哈达玛变换（WHT）二维离散沃尔什变换

很容易将一维WHT的定义推广到二维WHT。二维WHT的正变换核和逆变换核分别为和式中：x,u=0,1,2,…,M－1；

y,v=0,1,2,…,N－1。2023/1/11817.其他离散图像变换7.1离散沃尔什-哈达玛变换（WHT）二维离散沃尔什变换的矩阵形式表达式为和求这两个信号的二维WHT。2023/1/11827.其他离散图像变换7.1离散沃尔什-哈达玛变换（WHT）二维WHT结果（a）原图像；（b）WHT结果2023/1/11837.其他离散图像变换7.2离散余弦变换（DCT）

离散余弦变换（DiscreteCosineTransform，DCT）的变换核为余弦函数。DCT除了具有一般的正交变换性质外，它的变换阵的基向量能很好地描述人类语音信号和图像信号的相关特征。因此，在对语音信号、图像信号的变换中，DCT变换被认为是一种准最佳变换。近年颁布的一系列视频压缩编码的国际标准建议中，都把DCT作为其中的一个基本处理模块。除此之外，DCT还是一种可分离的变换。2023/1/11847.其他离散图像变换7.2离散余弦变换（DCT）

一维离散余弦变换一维DCT的变换核定义为:式中，x,u=0,1,2,…,N－1；

一维DCT定义如下：设{f(x)|x=0,1,…,N-1}为离散的信号列。式中，u,x=0,1,2,…,N－1。2023/1/11857.其他离散图像变换7.2离散余弦变换（DCT）

将变换式展开整理后，可以写成矩阵的形式，即F=Gf其中:2023/1/11867.其他离散图像变换7.2离散余弦变换（DCT）

一维DCT的逆变换IDCT定义为

式中，

x,u=0,1,2,…,N－1。可见一维DCT的逆变换核与正变换核是相同的。2023/1/11877.其他离散图像变换7.2离散余弦变换（DCT）

考虑到两个变量，很容易将一维DCT的定义推广到二维DCT。其正变换核为

式中，C(u)和C(v)的定义前页；x,u=0,1,2,…,M－1；y,v=0,1,2,…,