第三章图像变换精选文档.ppt

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

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

2、3/1/951.连续函数的傅立叶变换 一般是一个复函数，可以表示为：其中 、分别是 的实部和虚部。本讲稿第五页，共九十六页2023/1/961.连续函数的傅立叶变换 还可以表示为指数形式：其中 、分别是 的傅立叶谱和相角。本讲稿第六页，共九十六页2023/1/971.连续函数的傅立叶变换 称为 的能量谱或功率谱 称为 相位谱 称为 幅度谱则：本讲稿第七页，共九十六页2023/1/981.连续函数的傅立叶变换一维傅立叶变换举例一维傅立叶变换举例方波信号：经过傅立叶变换后：本讲稿第八页，共九十六页2023/1/991.连续函数的傅立叶变换 如果二维连续函数 满足可积条件,则其傅立叶变换为:反变换为

3、:本讲稿第九页，共九十六页2023/1/9101.连续函数的傅立叶变换对于二维方波信号傅立叶变换为：幅度：本讲稿第十页，共九十六页2023/1/9112.卷积和相关2.1卷积和卷积定理l卷积积分：如果函数卷积积分：如果函数 y(t)满足下列关系式满足下列关系式则称函数则称函数 y(t)为函数为函数 x(t)和和 h(t)的卷积的卷积l卷积积分的图解表示：卷积积分的图解表示：11x(t)th(t)t1/21*x(t)h(t)本讲稿第十一页，共九十六页2023/1/9122.卷积和相关2.1卷积和卷积定理l卷积积分的图解表示（续）：卷积积分的图解表示（续）：2y(t)1h(-)1/2-1折迭折迭位

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

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

6、页2023/1/9162.卷积和相关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)的相关函数的相关函数本讲稿第十六页，共九十六页2023/1/9172.卷积和相关2.2相关和相关定理 l相关积分的计算步骤：相关积分的计算步骤：1 位移：把位移：把 h()移动一个移动一个 t 值值2 相乘：将位移

7、后的函数相乘：将位移后的函数 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/9183.离散傅立叶变换3.1一维离散傅立叶变换 一维离散傅立叶变换公式为：逆变换为：本讲稿第十八页，共九十六页2023/1/9193.离散傅立叶变换3.

8、2二维离散傅立叶变换 对于二维傅立叶变换，其离散形式为：逆变换为：幅谱(频谱)、相谱：本讲稿第十九页，共九十六页2023/1/9203.离散傅立叶变换3.2二维离散傅立叶变换 l l离散傅立叶变换的显示本讲稿第二十页，共九十六页2023/1/9213.离散傅立叶变换3.2二维离散傅立叶变换 l l离散傅立叶变换的显示变换中心移动到原点本讲稿第二十一页，共九十六页2023/1/9223.离散傅立叶变换3.2二维离散傅立叶变换 图像傅立叶变换示例:注意低频(背景)和高频(细节、边缘)信息的分布本讲稿第二十二页，共九十六页2023/1/9233.离散傅立叶变换3.2二维离散傅立叶变换 本讲稿第二十三

9、页，共九十六页2023/1/9243.离散傅立叶变换3.2二维离散傅立叶变换 本讲稿第二十四页，共九十六页2023/1/9254.二维离散傅立叶变换的基本性质4.1可分离性 由可分离性可知，一个二维傅立叶变换可分解为两步进 行，其中每一步都是一个一维傅立叶变换。先对f(x,y)按行进行傅立叶变换得到F(x,v)，再对F(x,v)按列进行傅立叶变换，便可得到f(x,y)的傅立叶变换结果，如下图所示。显然对f(x,y)先按列进行离散傅立叶变换，再按行进行离散傅立叶变换也是可行的。本讲稿第二十五页，共九十六页2023/1/9264.二维离散傅立叶变换的基本性质4.1可分离性 正变换:反变换:本讲稿第

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

11、3/1/9304.二维离散傅立叶变换的基本性质4.4 比例尺性质当a=b=-1:本讲稿第三十页，共九十六页2023/1/9314.二维离散傅立叶变换的基本性质4.5 周期性和共轭对称性 周期性：本讲稿第三十一页，共九十六页2023/1/9324.二维离散傅立叶变换的基本性质4.5 周期性和共轭对称性 共轭对称性：本讲稿第三十二页，共九十六页2023/1/9334.二维离散傅立叶变换的基本性质4.5 周期性和共轭对称性 应用:1.图形的频谱分析和显示2.图像中心化本讲稿第三十三页，共九十六页2023/1/9344.二维离散傅立叶变换的基本性质4.6 旋转性质 空间域坐标变换为：空间频率域坐标变换

12、为：则:本讲稿第三十四页，共九十六页2023/1/9354.二维离散傅立叶变换的基本性质4.6 旋转性质 傅立叶变换的旋转性本讲稿第三十五页，共九十六页2023/1/9364.二维离散傅立叶变换的基本性质4.7 微分性质 若:则:本讲稿第三十六页，共九十六页2023/1/9374.二维离散傅立叶变换的基本性质4.8 平均值性质 二维离散函数 的平均值定义为：本讲稿第三十七页，共九十六页2023/1/9384.二维离散傅立叶变换的基本性质4.8 平均值性质 二维离散函数 的傅立叶变换的平均值定义为：可知：本讲稿第三十八页，共九十六页2023/1/9395.离散卷积和离散相关5.1 离散卷积和离散

13、卷积定理 l离散卷积的定义离散卷积的定义:由下面的求和公式给出由下面的求和公式给出这里，这里，x(kT)和和 h(kT)都是周期为都是周期为 T 的周期函数。的周期函数。l离散卷积的表示离散卷积的表示:和连续函数的卷积一样，离散卷积通常写作和连续函数的卷积一样，离散卷积通常写作:本讲稿第三十九页，共九十六页2023/1/9405.离散卷积和离散相关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离散卷积的另一种形式：离散卷积的另一种形式：本讲稿第四十页，共九十六页2023/1/9415.离散卷积和离散相关5.1 离散卷积和离散卷积定理 离散卷积和连续卷积的关系 l有限长波形的离散卷积：仍考虑前面的两个连续函数有限长波形的离散卷积：仍考虑前面的两个连续函数h(t)1/21/22 ty(t)P=6N

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

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

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

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

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

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

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

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

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

24、二进制码的位序颠倒。、位序颠倒：将列矢量的自变量二进制码的位序颠倒。本讲稿第五十四页，共九十六页2023/1/9556.快速傅立叶变换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本讲稿第五十五页，共九十六页2023/1/9566.快速傅立叶变换l对信号流程图的几点说明：对信号流程图的几点说明

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

26、)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(1

27、2)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/9586.快速傅立叶变换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(1

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

30、节点上的加权系数就是权系数就是 Wp+N/2，因为，因为 Wp=-Wp+N/2，所以计算对偶节点对，只需一次复，所以计算对偶节点对，只需一次复数乘法。数乘法。l 对偶节点对的计算公式：任何一个对偶节点对的计算，都可以用下面的一对对偶节点对的计算公式：任何一个对偶节点对的计算，都可以用下面的一对公式来给定公式来给定本讲稿第五十九页，共九十六页2023/1/9606.快速傅立叶变换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。本讲稿第

32、六十页，共九十六页2023/1/961 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(0

33、111)x(1000)x(1001)x(1010)x(1011)x(1100)x(1101)x(1110)x(1111)0123456789101112131415x(0000)本讲稿第六十一页，共九十六页2023/1/9626.快速傅立叶变换FFT 的计算流程图：的计算流程图：输入数据 x(k)N=2,NU=预置l=1 N2=N/2NU1=-1 k=0本讲稿第六十二页，共九十六页2023/1/963流程图：流程图：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

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

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

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

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

38、有如下形式：本讲稿第七十三页，共九十六页2023/1/9747.其他离散图像变换7.1离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）哈达玛矩阵的阶数是按N2n(n0,1,2,)规律排列的，阶数较高的哈达玛矩阵，可以利用矩阵的克罗内克积运算，由低阶哈达玛矩阵递推得到，即 本讲稿第七十四页，共九十六页2023/1/9757.其他离散图像变换7.1离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）矩阵的克罗内克积(Kronecker Product)运算用符号记作AB，其运算规律如下：设 本讲稿第七十五页，共九十六页2023/1/9767.其他离散图像变换7.1离散沃尔什离散

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

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

41、1。本讲稿第八十页，共九十六页2023/1/9817.其他离散图像变换7.1离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）二维离散沃尔什变换的矩阵形式表达式为 和 求这两个信号的二维WHT。本讲稿第八十一页，共九十六页2023/1/9827.其他离散图像变换7.1离散沃尔什离散沃尔什-哈达玛变换（哈达玛变换（WHTWHT）二维WHT结果（a）原图像；（b）WHT结果 本讲稿第八十二页，共九十六页2023/1/9837.其他离散图像变换7.2离散余弦变换（离散余弦变换（DCTDCT）离散余弦变换（Discrete Cosine Transform，DCT）的变换核为余弦函数。DCT

42、除了具有一般的正交变换性质外，它的变换阵的基向量能很好地描述人类语音信号和图像信号的相关特征。因此，在对语音信号、图像信号的变换中，DCT变换被认为是一种准最佳变换。近年颁布的一系列视频压缩编码的国际标准建议中，都把DCT作为其中的一个基本处理模块。除此之外，DCT还是一种可分离的变换。本讲稿第八十三页，共九十六页2023/1/9847.其他离散图像变换7.2离散余弦变换（离散余弦变换（DCTDCT）一维离散余弦变换一维离散余弦变换 一维DCT的变换核定义为:式中，x,u=0,1,2,N1；一维DCT定义如下：设f(x)|x=0,1,N-1为离散的信号列。式中，u,x=0,1,2,N1。本讲稿

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

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

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

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