数字图像处理第十章　图像的频域变换.pptVIP

FFT算法步骤 对得到的偶数数据项，进行第三层计算有： 两个数一组 FFT算法步骤 对得到的奇数数据项，进行第三层计算有： 两个数一组 FFT算法步骤 最后，将获得的所有数据项进行合并： FFT算法图示 FFT计算例 设对一个函数进行快速Fourier变换，函数在采样点上的值设为： 偶数项部分： 下标值分别为：000，010，100，110 排序为： 000, 100, 010, 110 奇数项部分： 下标值分别为：001，011，101，111 排序为： 001, 101, 011, 111 分成偶数、奇数为（偶数在左，奇数在右）： 按照前面叙述的FFT方法,第1层(4组2个点的运算)： 偶数项部分 奇数项部分 第2层偶数部分： 第2层奇数部分： 第3层（1组8个点的运算）： 对函数： 按照定义，可得其Fourier变换为： 下面，我们以F3为例验证结果是否正确： 人类视觉所感受到的是在空间域和时间域的信号。 但是，往往许多问题在频域中讨论时，有其非常方便分析的一面。例如，空间位置上的变化不改变信号的频域特性。　　　 问题的提出 首先，提出的变换必须是有好处的，换句话说，可以解决时域中解决不了的问题。　 其次，变换必须是可逆的，可以通过逆变换还原回原时域中。　　 图像变换的前提条件 二维离散傅立叶变换 快速傅立叶变换 二维离散傅立叶变换的应用 离散余弦变换　　　 本章讨论的内容 因为数字图像信号是二维的数字信号，所以必须采用二维傅立叶变换才能够实现对图像的频域变换。　　　 二维离散傅立叶变换 二维离散Fourier变换 —— 正变换 设图像大小为M*N，原图为f(x,y)，其频谱为F(u,v)，则： 二维Fourier变换可以转化为两次一维Fourier变换。 二维离散Fourier变换 —— 反变换 注：逆变换的系数不为1。 二维离散Fourier变换  —— 变换公式系数说明 因为Fourier变换是一种正交变换，所以其正、反变换的系数可以有几种表示形式。 按照严格意义上的正交变换，正、反变换的系数相等，为： 按照计算方便的角度，正、反变换的系数可以按照前面的方式给出，并且正、反变换的系数可以互换。 二维离散Fourier变换 —— 作用 1）可以得出信号在各个频率点上的强度。 2）可以将卷积运算化为乘积运算。 快速Fourier变换（FFT） 快速Fourier变换的提出，是为了减少计算量。 基本思想是，找出Fourier变换中的数据变化规 律，按照其规律整理出 适合计算机运算 的逻辑 结构。 FFT的推导 因为二维傅立叶变换可以转换成两次的一维傅立叶变换，所以，在这里我们只对一维快速傅立叶变换进行推导。 FFT的推导 （分成奇数项和偶数项之和） FFT的推导 （又可分成奇数项和偶数项之和） 单看偶数项: FFT的推导 = = = = = …… …… FFT的数据变换规律之一是： 1)可以不断分成奇数项与偶数项之加权和。 2)奇数项、偶数项可分层分类。 FFT的推导 至此，计算量可减少近一半。 FFT的算法原理 首先，将原函数分为奇数项和偶数项，通过不断的一个奇数一个偶数的相加（减），最终得到需要的结果。 也就是说FFT是将复杂的运算变成两个数相加（减）的简单运算的重复。这恰好符合计算机计算所擅长的计算规律。 FFT的算法步骤 1. 先将数据进行奇、偶分组。 例： 下标为2x 下标为2x+1 FFT算法步骤 分析偶数部分的数据项： 0000，0010，0100，0110，1000，1010，1100，1110 如果下标用二进制数表示为： 末尾一位是0。 FFT算法步骤 分析奇数部分的数据项： 0001，0011，0101，0111，1001，1011，1101，1111 如果下标用二进制数表示为： 末尾一位是1。 FFT算法步骤 二进制数为：0000，0010，0100，0110，1000，1010，1100，1110 第一层下标为： 0 2 4 6 8 10 12 14 2. 对偶数部分进行分层分组排序 因为奇数部分的数据项排列规律为2x+1，所以只需要给出偶数项部分，奇数项部分则可以类推。 FFT算法步骤 二进制数为：0000，0010，0100，0110，1000，1010，1100，1110 0 2 4 6 1 3 5 7 /2 *2 第一层下标分组为：