|
三、傅立叶交换 （一）傅立叶的定义 傅立叶变换在数学中的定义非常严格，它的定义如下。 http://www.paper51.com 设f(x)为x的函数，如果f(x)满足下面的狄里赫莱条件： copyright paper51.com （１）具有有限个间断点； 内容来自www.paper51.com
（２）具有有限个极值点； 内容来自www.paper51.com （３）绝对可积。 http://www.paper51.com
则定义f(x)的傅立叶变换公式为： 内容来自论文无忧网 www.paper51.com (4-13) http://www.paper51.com 它的逆变换为： (4-14) http://www.paper51.com 可以把傅立叶推广到二维情况。如果f（x,y）满足狄里赫莱条件，那么将可以导出下面的二维傅立叶变换： copyright paper51.com
(4-15) paper51.com
二维傅立叶的逆变换为： paper51.com
(4-16) 内容来自www.paper51.com （二）快速傅立叶变换的实现 paper51.com 现在，离散傅立叶已成为数字信号处理的重要工具，但是它的计算量比较大，运算时间长，在某种程度上限制了它的使用。为了解决这一矛盾，引用了快速傅立叶变换的思想。快速傅立叶变换并不是一种新的变换方式，它是离散傅立叶变换的一种算法，这种方法是建立在分析离散傅立叶里叶变换中的多余运算的基础上，进而消除这些重复工作的思想指导下得到的，从而在运算中节省了大量的计算时间，达到快速运算的目的。 内容来自www.paper51.com 快速傅立叶算法设计思想是: http://www.paper51.com 首先，将原函数分为奇数项和偶数项，通过不断的一个奇数一个偶数的相加（减），最终得到需要的结果。也就是说快速傅立叶算法是将复杂的运算变成两个数相加（减）的简单运算的重复 内容来自论文无忧网 www.paper51.com 。令： 内容来自www.paper51.com
(4-17) 内容来自www.paper51.com
一维离散傅立叶变换公式变为： copyright paper51.com
内容来自论文无忧网 www.paper51.com 内容来自www.paper51.com (4-18) paper51.com (分成奇数项和偶数项之和) 内容来自www.paper51.com 其中 http://www.paper51.com
copyright paper51.com (4-19) copyright paper51.com (4-20) 内容来自论文无忧网 www.paper51.com 所以，由式(4-17)(4-18)(4-19)(4-20)可得： paper51.com (4-21) 内容来自www.paper51.com 例如，设对一个函数进行快速Fourier变换，函数为： copyright paper51.com paper51.com 分成偶数、奇数为： 内容来自论文无忧网 www.paper51.com
copyright paper51.com 图4-3 内容来自www.paper51.com
从上可见F（0）和F（4）仅仅在运算符上不同，同理可以推出F（2）与F（6），F（2）与F（6），F（3）和F（7）在运算符上不同。为了快速实现傅立叶变换，要对F（x）进行“逆序”重排。 内容来自www.paper51.com 有了“逆序”的概念，就可以着手讨论快速傅立叶变换的实现。计算时，先将原始数组按宗量值“逆序”顺序，重新排列，然后自左向右，每两个相邻元素为一组，共4组，具体是：F（0），F（4）；F（2），F（6）；F（2），F（6）；F（3），F（7）。在每一组中，第一元素作为偶元素，第二元素作为奇元素（注意对所有组都一样）。在此基础上完成4个“两点变换”。下一步是利用“两点变换”结果形成两个“四点变换”，最后是建立在“四点变换”基础上的一个“八点变换”。具体见图4-7及图4-8。 内容来自论文无忧网 www.paper51.com 内容来自论文无忧网 www.paper51.com 图4-4 paper51.com
copyright paper51.com 图4-5 copyright paper51.com 以上快速傅立叶变换流程简称为逐次加倍法，因为“两点变换”由两个“一点变换”算出，“四点变换”由两个“两点变换”算出，“八点变换”由两个“四点变换”算出，依此类推。通过这种计算方法快速傅立叶变换比二维离散傅立叶变换的计算量大量减少，效率大大提高，增加了算法的实用性，使傅立叶变换在数字图像处理中得到更为广泛的应用。 内容来自www.paper51.com （三）二维离散傅立叶变换 http://www.paper51.com
二维离散傅立叶变换变换有两个好处： 内容来自论文无忧网 www.paper51.com （1）可以得出信号在各个频率点上的强度。 http://www.paper51.com （2）可以将卷积运算化为乘积运算。 内容来自www.paper51.com 二维离散函数f（x,y）的傅立叶变换为： 内容来自www.paper51.com
http://www.paper51.com
（4-22） copyright paper51.com 傅立叶反变换为： http://www.paper51.com
http://www.paper51.com
(4-23) paper51.com 其中：x=0,1,2,…，M-1; y=0,1,2…，N-1； 内容来自www.paper51.com
在数字图像处理中，图像取样一般是方阵，即:M=N,则二维离散傅立叶变换公式为： copyright paper51.com 内容来自www.paper51.com (4-24) 内容来自论文无忧网 www.paper51.com
内容来自www.paper51.com (4-25) copyright paper51.com 实现步骤 内容来自www.paper51.com
为了能在数字图像处理中应用傅立叶变换进行频谱分析处理，必须引入二维傅立叶变换的概念。二维傅立叶变换可以很容易地在一维傅立叶变换的基础上推导得出。可以将一个二维傅立叶变换通过在X方向、Y方向上的两次一维傅立叶变换来进行。将二维傅立叶变换的运算分解为水平和垂直两个方向上的一维离散傅立叶变换运算，由于在分解后的运算是靠一维离散傅立叶变换来完成的，而在前面已给出了对一维离散傅立叶变换的快速算法的实现过程，因此经分解后的二维离散快速傅立叶变换可以借助一维快速傅立叶变换来实现其快速算法。傅立叶变换在程序中的实现步骤： 内容来自论文无忧网 www.paper51.com (1) 开始； 内容来自www.paper51.com (2) 是否读入图像(否则转到(13))； 内容来自论文无忧网 www.paper51.com (3) 是否灰度图像(否则转到(13))； copyright paper51.com (4) 获得窗口数据； 内容来自论文无忧网 www.paper51.com
(5) 定义输出图象数据指针； 内容来自www.paper51.com (6) 分配内存； 内容来自论文无忧网 www.paper51.com
(7) 进行FFT变换 http://www.paper51.com (8) 滤波处理 copyright paper51.com (9) 逆傅立叶变换处理； 内容来自www.paper51.com (10)表示滤波后图象； 内容来自论文无忧网 www.paper51.com (11)更新画图； http://www.paper51.com (12)释放内存； paper51.com
(13)结束； 内容来自论文无忧网 www.paper51.com
|