《数字图像处理 第7章_傅立叶变换(2)》由会员分享，可在线阅读，更多相关《数字图像处理 第7章_傅立叶变换(2)（34页珍藏版）》请在金锄头文库上搜索。
1、第七章 频域处理 快速离散傅立叶变换第七章 频域处理 7.2.6 快速离散傅立叶变换（Fast Fourier Transform， FFT） 离散傅立叶变换计算量非常大，运算时间长。可以证明其运算次数正比于N2，特别是当N较大时，其运算时间将迅速增长。为此，研究离散傅立叶变换的快速算法是非常有必要的。第七章 频域处理 4点序列2，3，3，2 DFT的计算复杂度复数加法 N(N-1)复数乘法 N 2如何提高DFT的运算效率?第七章 频域处理 以一维离散傅立叶变换为例，说明其快速算法的推导。令W=e-j2N ，称为旋转因子，则： 第七章 频域处理 旋转因子 的性质1)周期性2) 对称性3)可约性
2、第七章 频域处理 例如，对于N=4， W阵为 第七章 频域处理 由W的周期性得：W4W0，W6W2，W9W1；再由W的对称性可得： W3W1，W2W0。于是上式可变为 ：第七章 频域处理 例如，对于N=8， W阵为 第七章 频域处理 由W的周期性和W的对称性可将上式变为 ：第七章 频域处理 设N为2的正整数次幂， 即 如令M为正整数，且 N=2M 第七章 频域处理 离散傅立叶变换可改写成如下形式： 由旋转因子W的定义可知， 因此上式变为 现定义 第七章 频域处理 于是进一步考虑W的对称性和周期性可知 和， 于是 由此，可将一个N点的离散傅立叶变换分解成两个N2短序列的离散傅立叶变换，即分解为偶
3、数和奇数序列的离散傅立叶变换Fe(u)和Fo(u) 。 第七章 频域处理 以计算N=8的DFT为例，此时n=3，M=4。可得 ：第七章 频域处理 蝶形运算单元 第七章 频域处理 由于Fe(u)和Fo(u)都是4点的DFT，因此，如果对它们再按照奇偶进行分组， 则有 第七章 频域处理 4点DFT分解为2点DFT的蝶形流程图 第七章 频域处理 8点DFT的蝶形流程图 第七章 频域处理 8点DFT逐级分解框图 第七章 频域处理 上述FFT是将f(x)序列按x的奇偶进行分组计算的，称之为时间抽选FFT。如果将频域序列的F(u)按u的奇偶进行分组计算， 也可实现快速傅立叶计算， 这称为频率抽选FFT。第
4、七章 频域处理 分析这些表达式得到如下一些有趣的特性：（1）一个N个点的变换，能够通过将原始表达式分成两个部分来计算；（2）通过计算两个（N/2）个点的变换。得到Feven(u)和 Fodd(u)；（3）奇部与偶部之和得到F(u)的前(N/2)个值；（4）奇部与偶部之差得到F(u)的后(N/2)个值，且不需要额外的变换计算。第七章 频域处理 归纳快速傅立叶变换的思想：（1）通过计算两个单点的DFT，来计算两个点的DFT；（2）通过计算两个双点的DFT，来计算四个点的DFT，以此类推；（3）对于任何N=2m的DFT的计算，通过计算两个N/2点的DFT，来计算N个点的DFT。第七章 频域处理 第七
5、章 频域处理 蝶形运算同址(原位)计算 蝶形计算的优点是可以进行所谓同址或原位计算。每一个蝶形运算都需要两个输入数据，计算结果也是两个数据，与其它结点的数据无关，其它蝶形运算也与这两结点的数据无关、因此，一个蝶形运算一旦计算完毕，原输入数据便失效了。这就意味着输出数据可以立即使用原输 人数据结点所占用的内存。原来的数据也就消失了。输出、输人数据利用同一内存单元的这种蝶形计算称为同位(址)计算。 第七章 频域处理 蝶形运算变址计算 同址计算要求输入x(n)是“混序”排列的。但实际上它是有规律的。如果输入x(n)的序号用二进制码来 表示，就可以发现输入的顺序恰 好是正序输入的“码位倒置”。 第七章
6、 频域处理 在实际运算中，按码位倒置顺序输入数据x(n)，特别当N较大时，是很不方便的。因此，数据总是按自然顺序输入存储，然后通过“变址”运算将自然顺序转换成码位倒置顺序存储。实现这种转换的程序用下图来说明。第七章 频域处理 倒序k0k1k2xk2 k1k0x000x100x0100101112 xk k0xk2 k101x110x001x101x011x11101010101第七章 频域处理 FFT算法举例设：有函数f(x)，其 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
7、(3), F(4), F(5), F(6),F(7) 第七章 频域处理 首先分成奇偶两组：有： 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) 第七章 频域处理 f(0), f(4) f(2), f(6) f(1), f(5) f(3), f(7) F2(0),F2(4) F2(2),F2(6) F2(1),F2(5) F2(3),F2(7)F4(0), F4(4), F4(2), F4(6) F4(1), F4(5),
8、 F4(3),F4(7)F8(0), F8(1), F8(2), F8(3), F8(4), F8(5), F8(6), F8(7) 第七章 频域处理 基2频率抽取FFT算法第七章 频域处理 3 NW -12 NW -11 NW -10 NW -1x0x4x1x5x2x6x3x74点 DFTX0X6X2X44点 DFTX1X3X5X7第七章 频域处理 X0X6X4X2X1X5X3X70 NW1 NW2 NW3 NW -1-1-1-1x0x3x1x2x4x5x6x70 NW2 NW2点 DFT-1-12 NW0 NW -1-12点 DFT2点 DFT2点 DFT第七章 频域处理 0 NW1 NW2 NW3 NW -1-1-1-1x0x3x1x2x4x5x6x70 NW2 NW2 NW0 NWX0X6X4X2X1X5X3X70 NW0 NW0 NW0 NW-1-1-1-1-1-1-1-1第七章 频域处理 本 次 授 课 结 束谢 谢 ！
