第三章图像变换精选PPT.ppt

《第三章图像变换精选PPT.ppt》由会员分享，可在线阅读，更多相关《第三章图像变换精选PPT.ppt（96页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章图像变换第三章图像变换第1页，本讲稿共96页2023/4/202本章主要内容n n1.连续函数的傅立叶变换n n2.卷积和相关n n3.离散傅立叶变换n n4.4.二维离散傅立叶变换的基本性质n n5.5.离散卷积和离散相关n n6.快速傅立叶变换n n7.其他离散图像变换第2页，本讲稿共96页2023/4/2031.连续函数的傅立叶变换 n n傅立叶变换是最早研究与应用的酉变换n n60年代出现快速傅立叶变换n n傅立叶变换域也称为频域傅立叶变换域也称为频域第3页，本讲稿共96页2023/4/2041.连续函数的傅立叶变换 设 为一实变量x的连续、可积函数，则其傅立叶变换为：反变换为:

2、第4页，本讲稿共96页2023/4/2051.连续函数的傅立叶变换 一般是一个复函数，可以表示为：其中 、分别是 的实部和虚部。第5页，本讲稿共96页2023/4/2061.连续函数的傅立叶变换 还可以表示为指数形式：其中 、分别是 的傅立叶谱和相角。第6页，本讲稿共96页2023/4/2071.连续函数的傅立叶变换 称为 的能量谱或功率谱 称为 相位谱 称为 幅度谱则：第7页，本讲稿共96页2023/4/2081.连续函数的傅立叶变换一维傅立叶变换举例一维傅立叶变换举例方波信号：经过傅立叶变换后：第8页，本讲稿共96页2023/4/2091.连续函数的傅立叶变换 如果二维连续函数 满足可积条

3、件,则其傅立叶变换为:反变换为:第9页，本讲稿共96页2023/4/20101.连续函数的傅立叶变换对于二维方波信号傅立叶变换为：幅度：第10页，本讲稿共96页2023/4/20112.卷积和相关2.1卷积和卷积定理l卷积积分：如果函数卷积积分：如果函数 y(t)满足下列关系式满足下列关系式则称函数则称函数 y(t)为函数为函数 x(t)和和 h(t)的卷积的卷积l卷积积分的图解表示：卷积积分的图解表示：11x(t)th(t)t1/21*x(t)h(t)第11页，本讲稿共96页2023/4/20122.卷积和相关2.1卷积和卷积定理l卷积积分的图解表示（续）：卷积积分的图解表示（续）：2y(t

4、)1h(-)1/2-1折迭折迭位移位移h(t-)1/2t h(t1-)x()1111x()*相相乘乘t1t积分积分1/2第12页，本讲稿共96页2023/4/20132.卷积和相关2.1卷积和卷积定理l卷积积分的步骤：卷积积分的步骤：1 折迭：把折迭：把 h()相对纵轴作出其镜像相对纵轴作出其镜像2 位移：把位移：把 h(-)移动一个移动一个 t 值值3 相乘：将位移后的函数相乘：将位移后的函数 h(t-)乘以乘以 x()4 积分：积分：h(t-)和和 x()乘积曲线下的面积即为乘积曲线下的面积即为 t 时刻的卷积值时刻的卷积值l卷积积分的另一种形式：卷积积分的另一种形式：第13页，本讲稿共9

5、6页2023/4/20142.卷积和相关2.1卷积和卷积定理l包含脉冲函数的卷积：即包含脉冲函数的卷积：即 x(t)或或 h(t)中有一个为脉冲函数，则它中有一个为脉冲函数，则它们的卷积是一种最简单的卷积们的卷积是一种最简单的卷积x(t)h(t)*x(t)atA-T0T0h(t)tA-T0T0t第14页，本讲稿共96页2023/4/20152.卷积和相关2.1卷积和卷积定理l卷积定理：如果卷积定理：如果 x(t)和和 h(t)的富里叶变换分别为的富里叶变换分别为 X(f)和和 H(f),则则x(t)*h(t)的富里叶变换为的富里叶变换为 X(f)H(f)。即即l卷积定理的简单推导：卷积定理的简

6、单推导：第15页，本讲稿共96页2023/4/20162.卷积和相关2.2相关和相关定理l频率卷积定理：如果频率卷积定理：如果 x(t)和和 h(t)的傅立叶变换分别为的傅立叶变换分别为 X(f)和和 H(f),则则 x(t)h(t)的傅立叶变换为的傅立叶变换为 X(f)*H(f)。即即l相关：如果函数相关：如果函数 z(t)满足下列关系式满足下列关系式则称函数则称函数 z(t)为函数为函数 x(t)和和 h(t)的相关函数的相关函数第16页，本讲稿共96页2023/4/20172.卷积和相关2.2相关和相关定理 l相关积分的计算步骤：相关积分的计算步骤：1 位移：把位移：把 h()移动一个移

7、动一个 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)的复共轭的复共轭第17页，本讲稿共96页2023/4/20183.离散傅立叶变换3.1一维离散傅立叶变换 一维离散傅立叶变换公式为：逆变换为：第18页，本讲稿共96页2023/4

8、/20193.离散傅立叶变换3.2二维离散傅立叶变换 对于二维傅立叶变换，其离散形式为：逆变换为：幅谱(频谱)、相谱：第19页，本讲稿共96页2023/4/20203.离散傅立叶变换3.2二维离散傅立叶变换 l l离散傅立叶变换的显示离散傅立叶变换的显示第20页，本讲稿共96页2023/4/20213.离散傅立叶变换3.2二维离散傅立叶变换 l l离散傅立叶变换的显示变换中心移动到原点第21页，本讲稿共96页2023/4/20223.离散傅立叶变换3.2二维离散傅立叶变换 图像傅立叶变换示例:注意低频(背景)和高频(细节、边缘)信息的分布第22页，本讲稿共96页2023/4/20233.离散傅

9、立叶变换3.2二维离散傅立叶变换 第23页，本讲稿共96页2023/4/20243.离散傅立叶变换3.2二维离散傅立叶变换 第24页，本讲稿共96页2023/4/20254.二维离散傅立叶变换的基本性质4.1可分离性 由可分离性可知，一个二维傅立叶变换可分解为两步进 行，其中每一步都是一个一维傅立叶变换。先对f(x,y)按行进行傅立叶变换得到F(x,v)，再对F(x,v)按列进行傅立叶变换，便可得到f(x,y)的傅立叶变换结果，如下图所示。显然对f(x,y)先按列进行离散傅立叶变换，再按行进行离散傅立叶变换也是可行的。第25页，本讲稿共96页2023/4/20264.二维离散傅立叶变换的基本性

10、质4.1可分离性 正变换:反变换:第26页，本讲稿共96页2023/4/20274.二维离散傅立叶变换的基本性质4.2平移性 平移性质表明，只要将f(x,y)乘以因子 (1)x+y，再进行离散傅立叶变换，即可将图像的频谱原点（0，0）移动到图像中心（M2,N2）处。下图是简单方块图像平移的结果。第27页，本讲稿共96页2023/4/20284.二维离散傅立叶变换的基本性质4.2平移性 (a)原图像；（b）无平移的傅立叶频谱；（c）平移后的傅立叶频谱(a)(b)(c)第28页，本讲稿共96页2023/4/20294.二维离散傅立叶变换的基本性质4.3 线性特性这一性质可使节约我们求傅立叶变换的时

11、间第29页，本讲稿共96页2023/4/20304.二维离散傅立叶变换的基本性质4.4 比例尺性质当a=b=-1:第30页，本讲稿共96页2023/4/20314.二维离散傅立叶变换的基本性质4.5 周期性和共轭对称性 周期性：第31页，本讲稿共96页2023/4/20324.二维离散傅立叶变换的基本性质4.5 周期性和共轭对称性 共轭对称性：第32页，本讲稿共96页2023/4/20334.二维离散傅立叶变换的基本性质4.5 周期性和共轭对称性 应用:1.图形的频谱分析和显示2.图像中心化第33页，本讲稿共96页2023/4/20344.二维离散傅立叶变换的基本性质4.6 旋转性质 空间域坐

12、标变换为：空间频率域坐标变换为：则:第34页，本讲稿共96页2023/4/20354.二维离散傅立叶变换的基本性质4.6 旋转性质 傅立叶变换的旋转性第35页，本讲稿共96页2023/4/20364.二维离散傅立叶变换的基本性质4.7 微分性质 若:则:第36页，本讲稿共96页2023/4/20374.二维离散傅立叶变换的基本性质4.8 平均值性质 二维离散函数 的平均值定义为：第37页，本讲稿共96页2023/4/20384.二维离散傅立叶变换的基本性质4.8 平均值性质 二维离散函数 的傅立叶变换的平均值定义为：可知：第38页，本讲稿共96页2023/4/20395.离散卷积和离散相关5.

13、1 离散卷积和离散卷积定理 l离散卷积的定义离散卷积的定义:由下面的求和公式给出由下面的求和公式给出这里，这里，x(kT)和和 h(kT)都是周期为都是周期为 T 的周期函数。的周期函数。l离散卷积的表示离散卷积的表示:和连续函数的卷积一样，离散卷积通常写作和连续函数的卷积一样，离散卷积通常写作:第39页，本讲稿共96页2023/4/20405.离散卷积和离散相关5.1 离散卷积和离散卷积定理 l离散卷积的计算步骤离散卷积的计算步骤:和连续函数的卷积的计算步骤类似，离散卷积也和连续函数的卷积的计算步骤类似，离散卷积也可以用下面几步来计算：可以用下面几步来计算：1 折迭：把折迭：把 h(iT)相

14、对纵轴作出其镜像相对纵轴作出其镜像2 位移：把位移：把 h(-iT)移动一个移动一个 kT 值值3 相乘：将位移后的函数相乘：将位移后的函数 h(kT-iT)乘以乘以 x(iT)4 积分：积分：h(kT-iT)和和 x(iT)在各个离散点的乘积的和即为在各个离散点的乘积的和即为 k 时刻时刻的卷积值的卷积值l离散卷积的另一种形式：离散卷积的另一种形式：第40页，本讲稿共96页2023/4/20415.离散卷积和离散相关5.1 离散卷积和离散卷积定理 离散卷积和连续卷积的关系 l有限长波形的离散卷积：仍考虑前面的两个连续函数有限长波形的离散卷积：仍考虑前面的两个连续函数h(t)1/21/22 t

15、y(t)P=6N=92y(t)N=91/2th(t)Q=6N=9x(t)t1第41页，本讲稿共96页2023/4/20425.离散卷积和离散相关5.1 离散卷积和离散卷积定理 离散卷积和连续卷积的关系 l有限长波形的离散卷积：有限长波形的离散卷积：N=111/2th(t)Q=6N=11ty(t)N=11P=6x(t)tN=11第42页，本讲稿共96页2023/4/20435.离散卷积和离散相关5.1 离散卷积和离散卷积定理 离散卷积和连续卷积的关系 l有限长波形的离散卷积：从上面我们可以看到，周期的选择对离散卷有限长波形的离散卷积：从上面我们可以看到，周期的选择对离散卷积的影响。如果周期选择的

16、太小，则离散卷积对连续卷积的近似是很差积的影响。如果周期选择的太小，则离散卷积对连续卷积的近似是很差的。原因是周期太小，则两个函数的输出会发生重迭。的。原因是周期太小，则两个函数的输出会发生重迭。l离散卷积的周期选择公式：要使离散卷积近似于连续卷积，则周期必离散卷积的周期选择公式：要使离散卷积近似于连续卷积，则周期必须满足下面的公式：须满足下面的公式：其中，其中，P 是函数是函数 x(t)的周期，的周期，Q 为函数为函数 h(t)的周期。的周期。l比例系数：离散卷积和连续卷积之间相差一个比例系数比例系数：离散卷积和连续卷积之间相差一个比例系数 T。第43页，本讲稿共96页2023/4/2044

17、5.离散卷积和离散相关5.1 离散卷积和离散卷积定理 离散卷积定理:l离散卷积定理：类似于连续富里叶变换，卷积公式的离散富里叶变换离散卷积定理：类似于连续富里叶变换，卷积公式的离散富里叶变换产生了离散卷积定理。定理的表示如下：产生了离散卷积定理。定理的表示如下：也就是说，两个周期为也就是说，两个周期为 N 的抽样函数，它们的卷积的离散富里叶的抽样函数，它们的卷积的离散富里叶变换等于它们的离散富里叶变换的乘积。变换等于它们的离散富里叶变换的乘积。l离散卷积定理的意义：有了离散卷积定理，我们就可以使用后面将要离散卷积定理的意义：有了离散卷积定理，我们就可以使用后面将要介绍的快速富里叶算法来计算离散

18、卷积。介绍的快速富里叶算法来计算离散卷积。第44页，本讲稿共96页2023/4/20455.离散卷积和离散相关5.2 离散相关和离散相关定理 l离散相关的定义：离散相关可以用下面的求和公式来表示离散相关的定义：离散相关可以用下面的求和公式来表示 这里，这里，x(kT)、h(kT)、z(kT)都是周期函数。和连续的情况一样，都是周期函数。和连续的情况一样，离散相关和离散卷积的差别就在于不需要折迭运算。离散相关和离散卷积的差别就在于不需要折迭运算。l离散相关定理：离散相关定理：第45页，本讲稿共96页2023/4/20466.快速傅立叶变换l矩阵方程：考虑离散傅立叶变换矩阵方程：考虑离散傅立叶变换

19、 上面的式子代表了上面的式子代表了 N 个方程的计算个方程的计算，为方便表示，我们引入下面，为方便表示，我们引入下面一个记号。一个记号。如果如果 N=4，则方程可写为：，则方程可写为：第46页，本讲稿共96页2023/4/20476.快速傅立叶变换l矩阵表示：矩阵表示：或者表示成：或者表示成：l矩阵的计算次数：要完成矩阵的运算，需要做矩阵的计算次数：要完成矩阵的运算，需要做 N*N 次复数的乘法和次复数的乘法和 N(N-1)次复数加法。次复数加法。第47页，本讲稿共96页2023/4/20486.快速傅立叶变换l 改写矩阵：改写矩阵：这是因为：这是因为：例如：例如：N=4，n=2，k=3,则则

20、第48页，本讲稿共96页2023/4/20496.快速傅立叶变换l矩阵分解因子：矩阵分解因子：注：上面的列矢量注：上面的列矢量 x(n)的行顺序发生了改变。的行顺序发生了改变。l乱序后的列矢量：用下面的符号标记乱序后的列矢量乱序后的列矢量：用下面的符号标记乱序后的列矢量第49页，本讲稿共96页2023/4/20506.快速傅立叶变换l计算次数：将矩阵分解因子后，计算需要分两步来进行。计算次数：将矩阵分解因子后，计算需要分两步来进行。第一步：第一步：其中其中:一次乘法和一次加法一次乘法和一次加法一次乘法和一次加法一次乘法和一次加法一次加法一次加法一次加法一次加法第50页，本讲稿共96页2023/

21、4/20516.快速傅立叶变换l计算次数：计算次数：(第二步第二步)其中其中:一次乘法和一次加法一次乘法和一次加法一次乘法和一次加法一次乘法和一次加法一次加法一次加法一次加法一次加法而而:第51页，本讲稿共96页2023/4/20526.快速傅立叶变换l计算次数计算次数：经过矩阵分解后，计算方程总共需要四次复数乘法和八次：经过矩阵分解后，计算方程总共需要四次复数乘法和八次复数加法。而未经分解的矩阵计算，总共需要十六次复数乘法和十二次复数加法。而未经分解的矩阵计算，总共需要十六次复数乘法和十二次复数加法。复数加法。l效率效率：因为计算时间主要取决于复数乘法的计算次数，所以减少复数：因为计算时间主

22、要取决于复数乘法的计算次数，所以减少复数乘法的次数就是乘法的次数就是 FFT 算法效率高的原因。算法效率高的原因。l基基2的的 FFT 算法的原理算法的原理：对于：对于 的的 FFT 算法，就是要把一个算法，就是要把一个 N*N 的矩阵，分解为的矩阵，分解为 (其中每个都是其中每个都是 N*N)个矩阵。使被分解后的每一个个矩阵。使被分解后的每一个矩阵具有复数乘法和复数加法最少的特性。矩阵具有复数乘法和复数加法最少的特性。第52页，本讲稿共96页2023/4/20536.快速傅立叶变换l基基2的的 FFT 算法的效率：对于算法的效率：对于 的的 FFT 算法，所需的计算次数为：算法，所需的计算次

23、数为：乘法次数：乘法次数：加法次数：加法次数：l普通算法的效率：所需的计算次数为：普通算法的效率：所需的计算次数为：乘法次数：乘法次数：加法次数：加法次数：l两种算法的效率之比：两种算法的效率之比：第53页，本讲稿共96页2023/4/20546.快速傅立叶变换l乱序重排：经过矩阵分解后，计算所得到的是一个乱序的列矢量，这乱序重排：经过矩阵分解后，计算所得到的是一个乱序的列矢量，这种乱序是分解过程中固有的，需要经过重新排列。种乱序是分解过程中固有的，需要经过重新排列。1、二进制表示：将列矢量的自变量表示成二进制。、二进制表示：将列矢量的自变量表示成二进制。2、位序颠倒：将列矢量的自变量二进制码

24、的位序颠倒。、位序颠倒：将列矢量的自变量二进制码的位序颠倒。第54页，本讲稿共96页2023/4/20556.快速傅立叶变换l信号流程图：前面矩阵分解计算的过程可以用下面的信号流程图表示信号流程图：前面矩阵分解计算的过程可以用下面的信号流程图表示出来：出来：数据数组数据数组数组数组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)w0w0w2w2w0w2w1w3第55页，本讲稿共96页2023/4/20566.快速傅立叶变换l对信号流程图的几点说明：对信号流程图的几点说明：1、传输路

25、径：进入计算数组的每个节点有两条实线，它们表示从、传输路径：进入计算数组的每个节点有两条实线，它们表示从上一列节点来的两条传输路径。上一列节点来的两条传输路径。2、传输路径的权值：每条传输路径都带有相应的权值。如果在某、传输路径的权值：每条传输路径都带有相应的权值。如果在某条传输路径上没有标记权值，则缺省权值为条传输路径上没有标记权值，则缺省权值为1。3、数组的计算：从两条传输路径进到一个节点的两结果要相加起、数组的计算：从两条传输路径进到一个节点的两结果要相加起来。来。第56页，本讲稿共96页2023/4/2057数据数组数据数组x0(0)x0(3)x0(2)x0(1)x0(4)x0(7)x

26、0(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

27、)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)对偶对偶节点对节点对对偶对偶节点对节点对对偶对偶节点对节点对对偶对偶节点对节点对第57页，本讲稿共96页2023/4/20586.快速傅立叶变换l对偶节点：在前面的图中的每一纵列中，总可以找到这样的两个点，它对偶节点：在前面的图中的每一纵列中，总可以找到这样的两个点，它们的传输路径来自前一列中的同一对节点，而且这两个节点不会用来计们的传输路径来自前一列中的同一对节点，而且这两个节点不会用来计算其它的

28、任何节点。我们把这样的两个点称为算其它的任何节点。我们把这样的两个点称为对偶节点对偶节点对偶节点对偶节点。例如，例如，x1(0)和和 x1(8)，它们都用，它们都用 x0(0)和和 x0(8)来计算。可以用来计算。可以用 x0(0)和和 x0(8)同时计算出同时计算出 x1(0)和和 x1(8)。l对偶节点的间隔：用对偶节点的间隔：用 l 表示数组的下标，在表示数组的下标，在 l=1的列中，对偶节点（例如的列中，对偶节点（例如x1(0)和和 x1(8)）之间的距离为）之间的距离为 K=8=N/2l，在在 l=2的列中，对偶节点（例如的列中，对偶节点（例如 x2(8)和和 x2(12)）之间的距

29、离为）之间的距离为 K=4=N/22，同样，同样，在在 l=3的列中，对偶节的列中，对偶节点点之间的距离为之间的距离为 K=2=N/23，在在 l=4 的列中，对偶节点的列中，对偶节点之间的距离为之间的距离为 K=1=N/24。所以，。所以，对偶节点的间隔为：对偶节点的间隔为：第58页，本讲稿共96页2023/4/20596.快速傅立叶变换l 对偶节点对的计算次数：一个对偶节点对的计算只需要一次复数乘法对偶节点对的计算次数：一个对偶节点对的计算只需要一次复数乘法。一般地讲，如果在某一节点上的加权系数为一般地讲，如果在某一节点上的加权系数为 Wp，则在其对偶节，则在其对偶节点上的加权系数就是点上

30、的加权系数就是 Wp+N/2，因为，因为 Wp=-Wp+N/2，所以计算对偶节点，所以计算对偶节点对，只需一次复数乘法。对，只需一次复数乘法。l 对偶节点对的计算公式：任何一个对偶节点对的计算，都可以用下面的对偶节点对的计算公式：任何一个对偶节点对的计算，都可以用下面的一对公式来给定一对公式来给定第59页，本讲稿共96页2023/4/20606.快速傅立叶变换l Wp 的确定：每个节点的加权系数可以通过下面的方法得到的确定：每个节点的加权系数可以通过下面的方法得到1、把指数、把指数 k 写成写成 位的二进制数；位的二进制数；2、把这个、把这个二进制数右移二进制数右移 -l 位，并把左边空出的位

31、置补为零位，并把左边空出的位置补为零；3、将右移后的、将右移后的 位二进制数的位序颠倒，其结果就是位二进制数的位序颠倒，其结果就是 P 值；值；例如，前面图中的节点例如，前面图中的节点 x3(8)，由于，由于 =4，k=8，l=3，于是，于是 k写成写成 位的二进制数就是位的二进制数就是 1000，将这个二进制数右移，将这个二进制数右移 -l=4-3=1 位，并将左位，并将左边空出的位置上补零，结果是边空出的位置上补零，结果是 0100，然后把位序颠倒。得到，然后把位序颠倒。得到 0010，这，这就是十进制的整数就是十进制的整数 2，所以，所以 p 值等于值等于 2。第60页，本讲稿共96页2

32、023/4/2061 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(100

33、0)x(1001)x(1010)x(1011)x(1100)x(1101)x(1110)x(1111)0123456789101112131415x(0000)第61页，本讲稿共96页2023/4/20626.快速傅立叶变换FFT 的计算流程图：的计算流程图：输入数据 x(k)N=2,NU=预置l=1 N2=N/2NU1=-1 k=0第62页，本讲稿共96页2023/4/2063流程图：流程图：M=k/2NU1的整数P=IBR(M)T1=Wpx(k+N2)x(k+N2)=x(k)-T1 x(k)=x(k)+T1K=k+1否I=I+1l?否是K=k+N2K=N-1是否l=l+1,N2=N2/2N

34、U1=NU1-1,k=0I=N2?I=1是第63页，本讲稿共96页2023/4/20646.快速傅立叶变换流程图：流程图：是否I=kT3=x(k)x(k)=x(i)x(i)=T3K=N-1?是结束k=k+1I=IBR(k)否第64页，本讲稿共96页2023/4/20656.快速傅立叶变换另一个推导（1）：记则有：单位园表示：W40 W41 W42 W43 N=4时W的值 W80 W82 W83 N=8时W的值 W81 W84 W85 W86 W87 第65页，本讲稿共96页2023/4/20666.快速傅立叶变换WNux的性质：(1)对称性：(2)周期性：(3)可分性：第66页，本讲稿共96页

35、2023/4/20676.快速傅立叶变换另一个推导（2）：傅立叶变换：需要N次复数乘法，N-1次复数加法。因此总共需要N2次复数乘法，N(N-1)次复数加法。1965年，Cooley和Tukey提出快速算法，算法时间复杂度为Nlog2N。第67页，本讲稿共96页2023/4/20686.快速傅立叶变换设N=2m，f(x)的定义域分为偶数部分和奇数部分，即f(2x)和f(2x+1)记为：u=0,1,2,N/2-1第68页，本讲稿共96页2023/4/2069对于N=N/2,N/2,N-1由Fe(u)和Fo(u)的原式，它们以N/2为周期：而由W的性质：所以：第69页，本讲稿共96页2023/4/

36、20706.快速傅立叶变换FFT变换蝶形图：第70页，本讲稿共96页2023/4/20716.快速傅立叶变换奇偶分组和比特倒序第71页，本讲稿共96页2023/4/20727.其他离散图像变换7.1离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）1.1.沃尔什函数沃尔什函数 沃尔什函数是1923年由美国数学家沃尔什提出的。沃尔什函数系是一完备正交函数系，其值只能取1和1。从排列次序上可将沃尔什函数分为三种定义方法：一种是按照沃尔什排列来定义（按列率排序）；另一种是按照佩利排列来定义（按自然排序）；第三种是按照哈达玛排列来定义。由于哈达玛排序的沃尔什函数是由2n（n=0，1，2，）阶

37、哈达玛矩阵（Hadamard Matrix）得到的，而哈达玛矩阵的最大优点在于它具有简单的递推关系，即高阶矩阵可用两个低阶矩阵的克罗内克积求得，因此在此只介绍哈达玛排列定义的沃尔什变换。第72页，本讲稿共96页2023/4/20737.其他离散图像变换7.1离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）N=2n(n=0,1,2,)阶哈达玛矩阵每一行的符号变化规律对应于某一个沃尔什函数的符号变化规律，即N=2n(n=0,1,2,)阶哈达玛矩阵的每一行对应于一个离散沃尔什函数，哈达玛矩阵与沃尔什函数系不同之处仅仅是行的次序不同。2n阶哈达玛矩阵有如下形式：第73页，本讲稿共96页20

38、23/4/20747.其他离散图像变换7.1离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）哈达玛矩阵的阶数是按N2n(n0,1,2,)规律排列的，阶数较高的哈达玛矩阵，可以利用矩阵的克罗内克积运算，由低阶哈达玛矩阵递推得到，即 第74页，本讲稿共96页2023/4/20757.其他离散图像变换7.1离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）矩阵的克罗内克积(Kronecker Product)运算用符号记作AB，其运算规律如下：设 第75页，本讲稿共96页2023/4/20767.其他离散图像变换7.1离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）

39、则 第76页，本讲稿共96页2023/4/20777.其他离散图像变换7.1离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）2.2.离散沃尔什离散沃尔什-哈达玛变换哈达玛变换 一维离散沃尔什变换定义为一维离散沃尔什逆变换定义为 式中，Walsh(u,x)为沃尔什函数。若将Walsh(u,x)用哈达玛矩阵表示，并将变换表达式写成矩阵形式，则上式分别为 第77页，本讲稿共96页2023/4/20787.其他离散图像变换7.1离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）和 式中，HN为N阶哈达玛矩阵。第78页，本讲稿共96页2023/4/20797.其他离散图像变换7.1

40、离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）由哈达玛矩阵的特点可知，沃尔什-哈达玛变换的本质上是将离散序列f(x)的各项值的符号按一定规律改变后，进行加减运算，因此，它比采用复数运算的DFT和采用余弦运算的DCT要简单得多。第79页，本讲稿共96页2023/4/20807.其他离散图像变换7.1离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）二维离散沃尔什变换二维离散沃尔什变换 很容易将一维WHT的定义推广到二维WHT。二维WHT的正变换核和逆变换核分别为和 式中：x,u=0,1,2,M1；y,v=0,1,2,N1。第80页，本讲稿共96页2023/4/20817.

41、其他离散图像变换7.1离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）二维离散沃尔什变换的矩阵形式表达式为 和 求这两个信号的二维WHT。第81页，本讲稿共96页2023/4/20827.其他离散图像变换7.1离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）二维WHT结果（a）原图像；（b）WHT结果 第82页，本讲稿共96页2023/4/20837.其他离散图像变换7.2离散余弦变换（离散余弦变换（DCTDCT）离散余弦变换（Discrete Cosine Transform，DCT）的变换核为余弦函数。DCT除了具有一般的正交变换性质外，它的变换阵的基向量能很好地描

42、述人类语音信号和图像信号的相关特征。因此，在对语音信号、图像信号的变换中，DCT变换被认为是一种准最佳变换。近年颁布的一系列视频压缩编码的国际标准建议中，都把DCT作为其中的一个基本处理模块。除此之外，DCT还是一种可分离的变换。第83页，本讲稿共96页2023/4/20847.其他离散图像变换7.2离散余弦变换（离散余弦变换（DCTDCT）一维离散余弦变换一维离散余弦变换 一维DCT的变换核定义为:式中，x,u=0,1,2,N1；一维DCT定义如下：设f(x)|x=0,1,N-1为离散的信号列。式中，u,x=0,1,2,N1。第84页，本讲稿共96页2023/4/20857.其他离散图像变换

43、7.2离散余弦变换（离散余弦变换（DCTDCT）将变换式展开整理后，可以写成矩阵的形式，即 F=Gf 其中:第85页，本讲稿共96页2023/4/20867.其他离散图像变换7.2离散余弦变换（离散余弦变换（DCTDCT）一维DCT的逆变换IDCT定义为 式中，x,u=0,1,2,N1。可见一维DCT的逆变换核与正变换核是相同的。第86页，本讲稿共96页2023/4/20877.其他离散图像变换7.2离散余弦变换（离散余弦变换（DCTDCT）考虑到两个变量，很容易将一维DCT的定义推广到二维DCT。其正变换核为 式中，C(u)和C(v)的定义前页；x,u=0,1,2,M1；y,v=0,1,2,

44、N1。第87页，本讲稿共96页2023/4/20887.其他离散图像变换7.2离散余弦变换（离散余弦变换（DCTDCT）式中：x,u=0,1,2,M1；y,v=0,1,2,N1。二维DCT定义如下：设f(x,y)为MN的数字图像矩阵，则 第88页，本讲稿共96页2023/4/20897.其他离散图像变换7.2离散余弦变换（离散余弦变换（DCTDCT）二维DCT逆变换定义如下：式中：x,u=0,1,2,M1；y,v=0,1,2,N1。类似一维矩阵形式的DCT，可以写出二维DCT的矩阵形式如下：F=GfGT第89页，本讲稿共96页2023/4/20907.其他离散图像变换7.2离散余弦变换（离散余

45、弦变换（DCTDCT）同时，可知二维DCT的逆变换核与正变换核相同，且是可分离的，即 x,u=0,1,2,M1；y,v=0,1,2,N1。第90页，本讲稿共96页2023/4/20917.其他离散图像变换7.2离散余弦变换（离散余弦变换（DCTDCT）通常根据可分离性，二维DCT可用两次一维DCT来完成，其算法流程与DFT类似，即 第91页，本讲稿共96页2023/4/20927.其他离散图像变换7.2离散余弦变换（离散余弦变换（DCT)DCT)压缩压缩DCT 其变换结果的能量将主要集中在左上角的位置，即低频部分 第92页，本讲稿共96页2023/4/20937.其他离散图像变换7.2离散余弦

46、变换（离散余弦变换（DCTDCT）去噪去噪 DENOISEDNOISED第93页，本讲稿共96页2023/4/20947.其他离散图像变换7.3 KLKL变换变换 KL变换通常也称为霍特林变换。它和前面介绍的其它变换不同，它是建立在统计特性基础上的一种变换。KL变换的突出优点是去相关性好，主要应用于数据压缩和图像的旋转上。为X的平均向量第94页，本讲稿共96页2023/4/20957.其他离散图像变换7.3 KLKL变换变换 KLKL变换的性质变换的性质 （1）变换后的图像向量Y的均值向量 =0 。（2）Y向量的协方差矩阵为 （3）协方差矩阵 是对角型矩阵，其对角线上的元素等于 的特征值。第95页，本讲稿共96页2023/4/20967.其他离散图像变换7.3 KLKL变换变换 （a）原始图像 （b）第一主成分 （c）第二主成分 （d）第三主成分第96页，本讲稿共96页