数字图像处理课件FFT文字稿.doc

《数字图像处理课件FFT文字稿.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、三、离散傅里叶变换的快速算法从一维离散傅里叶变换（DFT）的定义可以看出，对中每一个值，计算过程都要做与的N次复数乘法和对这些乘积的（N－1）次复数加法。共有N个取值的可能，所以总的计算过程需要有N2次复数乘法，以及N（N－1）次复数加法操作。例如当N＝8时，有64次复数乘法，56次复数加法。随着N的数值增加，复乘和复加次数将与N2成正比地增加，计算量非常大，这就限制了DFT的使用。将上式简化写作其中通常，N选为，为正整数。可以看出，具有周期性和对称性，即其中，……。例如，N＝8＝23时，正好如右图等分单位圆的各个向量。这里有，，……，，，。以下推导快速算法计算过程，当时，计算，省略书写过程

2、中的系数,则有计算每计算一个变换结果都需要8次复乘和7次复加。利用的对称性，重写上式有这样只需做4次复乘和7次复加。注意到的性质，而且，，上式可改写为可以看出，上式将原先序列分成奇偶两个子序列（两个大括号），然后分别对这两个子序列继续分解成两个更小的奇偶子序列，直至最后每个子序列只要一个样本为止。上式加法仍然为7次，乘法只有3次。以下将所有式子列出来，并把表达式相近项调整在一起：其中，上列式中有许多重复运算，如：可以进一步简化，例如在计算时，分别计算和。则有。再有由于，则计算和时有其余依此类推。总之，离散傅里叶变换可以先分成两个子序列进行计算其中，。这里的和分别是将分解成偶数项子序列和奇数项

3、子序列的傅里叶变换，即偶数项子序列奇数项子序列其中。（具体证明和继续分解过程见参考书）DFT按上述方法递归分解子序列，直到子序列只有两个样本为止。这种算法过程称之为快速傅里叶变换（FFT），计算量由原先与N2成正比，变成与Nlog2N成正比。当N很大时，FFT优势更明显。附件：1、矩阵表示法例、的原信号序列的傅氏变换展开：把上面的e指数项可写成矩阵形式，引入了DFT的矩阵表（N＝4）：记为,其W为变换核矩阵。由此，傅里叶变换就表示为向量、矩阵的简式。为了方便矩阵计算，重写离散傅立叶变换表式为也就是说，上述矩阵中的每一个矩阵元表示成。对前述N＝4情况，。图像变换矩阵描述成Y=AX，逆变换为X=

4、A-1Y。当A为正交矩阵时，逆变换为X=AtY。当A为正交对称矩阵时，逆变换为X=AY。.2、二维FFT结果显示二维FFT运算结果是一个复数矩阵，结果显示是用频谱作为亮度显示在屏幕上。将幅度值用8bit（0－255）进行量化，一个问题是：由于图像的高频幅度衰减很快，将会导致高频部分图像十分黯淡。解决的办法是：用对数调整其坐标比例。设显示信号为，就可改进只用时显示不清楚的问题。而且，当＝0时，＝0，保证了非负值。这时各峰具有相似的幅度，即相似的亮度。使用公式还用K系数调节显示的图像：其中K=1~10,调节显示最大值与最小值之间的比例。