图像处理分析-FFT

快速傅里叶变换FFT的C语言实现及应用

快速傅里叶变换（Fast Fourier Transform, FFT）是一种快速计算离散傅里叶变换（Discrete Fourier Transform, DFT）的算法。它能够在较短时间内计算出巨大数据集的傅里叶变换，广泛应用于信号处理、图像处理、通信等领域。

C语言是一种广泛应用于嵌入式系统和科学计算的编程语言，拥有高效、灵活和可移植等特点。下面将介绍FFT的C语言实现及应用。

首先，我们需要了解离散傅里叶变换的定义。离散傅里叶变换将一组离散的时域信号转换成一组对应的频域信号，可以表示为以下公式：

X(k) = Σ[ x(n) * W^(kn) ]

其中，X(k)是频域信号，x(n)是时域信号，W是单位复数旋转因子，其计算公式为W=e^(-j*2π/N)，其中j是虚数单位，N是信号的长度。

实现FFT算法的关键在于计算旋转因子的值，一种常用的计算方法是采用蝶形算法（butterfly algorithm）。蝶形算法将DFT分解成多个子问题的求解，通过递归调用可以快速计算出结果。以下是一种基于蝶形算法的FFT实现的示例代码：

```c

#include

#include

typedef struct

float real; float imag;

if (N <= 1)

return;

}

for (int i = 0; i < N/2; i++)

even[i] = signal[2*i];

odd[i] = signal[2*i + 1];

}

fft(even, N/2);

fft(odd, N/2);

for (int k = 0; k < N/2; k++)

signal[k].real = even[k].real + temp.real;

signal[k].imag = even[k].imag + temp.imag;

signal[k + N/2].real = even[k].real - temp.real;

N=4时FFT流程图数字图像处理

在以上讨论FFT算法中，均假定序列x(l)为复的，但实际问题中e68a843231313335323631343130323136353331333433616238的序列大多为实的。当然，我们可以把实序列处理成虚部为零的重复序列。因此，就要引进许多零参加运算。这样一来，在机器运算时间和存储单元方面都将造成很大的浪费。在本段中，我们介绍对实序列x(l)应用FFT算法的一个有效方法。

1、同时计算两个实序列的FFT算法

设有N=4的两个实序列x1(l)与x2(l)。为了求得它们的谱X1(m)与X2(m)，我们用此二实序列构造成如下复序列

物探数字信号分析与处理技术

利用上一段的方法，可以求得复序列x(l)的谱X(m)。根据（7-3-1）得到

物探数字信号分析与处理技术

上式中的m用N-m代替，则得

物探数字信号分析与处理技术

将上式两端取共轭，根据对称性有

物探数字信号分析与处理技术 根据DFT的复共轭性质，对于实序列x1(l)与x2(l)，有

物探数字信号分析与处理技术

于是从（7-3-4）得到

物探数字信号分析与处理技术

联立求解（7-3-2）和（7-3-6）便得到

物探数字信号分析与处理技术

例如设有两个N=4点的实序列，

物探数字信号分析与处理技术

我们用它们构造一个N=4点的重复序列

物探数字信号分析与处理技术

利用FFT算法求X(m)，m=0，1，2，3，

于是得到

物探数字信号分析与处理技术

因此从式（7-3-7）得到

物探数字信号分析与处理技术

物探数字信号分析与处理技术

2、实序列的FFT算法

设有N点的实序列x(l)，l=0，1，2，…，N-1。按照点的奇偶编号，将它们分成N/2个点的两个子序列 物探数字信号分析与处理技术

设x1(l)的谱与x2(l)的谱分别为X1(m)与X2(m)

物探数字信号分析与处理技术

其中

于是可以将实序列x(l)的谱X(m)，用两个子序列x1(l)，x2(l)的谱X1(m)，X2(m)来表示

一、实验目的

（1）在理论学习的基础上，通过本实验，加深对FFT的理解，熟悉FFT子程序。

（2）熟悉应用FFT对典型信号进行频谱分析的方法。

（3）了解应用FFT进行信号频谱分析过程中可能出现的问题，以便在实际中正确应用FFT。

（4）熟悉应用FFT实现两个序列的线性卷积的方法。

（5） 初步了解用周期图法做随机信号谱分析的方法。

二、实验原理

1、对有限长序列，可以用离散傅里叶变换DFT。不但可以很好的反映序列的频谱特性，而且易于用快速算法在计算机上实现，当序列x(n)的长度为N时，它的DFT定义为

NjNNnknNeWWnxk210,)(X）（

逆变换为：

10)(1)(NkknNWkXNnx

有限长序列的DFT使其z变换在单位圆上的等距采样。因此可用于序列的谱分析。

2、用FFT计算线性卷积

用FFT可以实现两个序列的圆周卷积。在一定的条件下，可以使圆周卷积等于线性卷积，一般情况，设两个序列的长度分别为N1和N2，要使圆周卷积等于线性卷积的充要条件是FFT的长度N大于等于N1加N2.对于长度不足N的序列，分别用FFT对它们补零延长到N。

三、实验内容

1、已知有限长序列x(n)=[1,0.5,0,0.5,1,1,0.5,0],要求：

①用FFT求该序列的DFT、IDFT图形

②假设采样频率F=20Hz,序列长度N分别取8、32和64，用FFT计算其幅度频谱和相位频谱。

①程序

实验截图：

DFT、IDFT图形

实验截图：

幅度频谱和相位频谱。

2、用FFT计算下面连续信号的频谱，并观察不同的采样周期T和序列长度N值对频谱特性的影响。

程序：

实验截图：

3、已知序列x(n)=sin(0.4n),1

２００８，４４（２）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用１引言现代数字图像处理包括很多技术，从简单的图像模糊、锐化，雾化到复杂的高动态范围（ＨＤＲ）图像的色调映射，基本上都使用了一种或者多种图像滤波器的组合。因此可以说图像滤波器是现代计算机图形学中的关键要素之一。图像滤波中，又分为两种不同的基本方式：在空间域中的滤波和在频域中的滤波。在空间域中的滤波很简单，只需要将待滤波的图像和滤波器核进行卷积运算；而在频域的滤波则需要先将图像通过傅立叶变换转换到频域上，然后乘以适当的滤波器，最后，通过傅立叶反变换转换到空间域中。这两种方式在不同的情况下有着各自的缺点和优点，而且在ＣＰＵ上的实现已经是成熟通用的方法广为人们熟知。然而由于这两种方法都存在计算量巨大的特点，当待处理的图像比较大的时候，ＣＰＵ的结构特点决定了其的性能往往不能满足图像滤波的实时性要求。图形处理器（ＧＰＵ）为ＳＩＭＤ架构，决定了它非常适合处理大量数据诸如图像、音频的这类任务。早期的ＧＰＵ由于是固定管线结构，自由度非常小，人们难以利用其进行３Ｄ图形运算之外的工作。自从Ｍｉｃｒｏｓｏｆｔ推出ＤｉｒｅｃｔＸ８以后，ＧＰＵ工作管线中加入了可编程单元，使得人们可以使用ＧＰＵ进行一些通用的计算，同样，也给使用ＧＰＵ进行图像滤波处理提供了可能。关于在ＧＰＵ上实现ＦＦＴ算法，Ｍｏｒｅｌａｎｄ和Ａｎｇｅｌ［１］可能是首先进行尝试的，但由于当时条件限制（他们使用的是ＮＶ５０００系列的ＧＰＵ），许多工作还无法在ＧＰＵ上实现；Ｓｕｍａｍａｗｅｅｒａ和Ｌｉｕ［２］在医疗图像处理上做了很有效地尝试，他们使用时间抽取算法实现ＦＦＴ并把计算量在顶点着色器和像素着色器中做了分摊，但是这种分摊并没有收到很明显的效果，因为老架构的ＧＰＵ顶点运算单元和像素运算单元存在运算能力的不均衡。本文采用了频率抽取算法在ＧＰＵ上实现了ＦＦＴ算法，在实时图像处理方面将ＦＦＴ和卷积算法就性能和ＧＰＵ实现的适应性方面进行了比较。简单起见，本文的图像都为灰度图像。２数学原理２．１离散傅立叶变换有着Ｎ个采样点的一维离散信号ｘ（ｎ）的离散傅立叶变换可以表示为：Ｘ（ｋ）＝Ｎ－１ｎ＝０!ｘ（ｎ）ＷｋｎＮ，０≤ｋ≤Ｎ－１（１）其中：ＷｋｎＮ＝ｅ－ｉ２!ｋｎＮ（２）由于讨论的数字图像都是二维信号，故需一维傅立叶变换扩展到二维：ＧＰＵ图像处理的ＦＦＴ和卷积算法及性能分析冯煌ＦＥＮＧＨｕａｎｇ上海西门子移动通信有限公司，上海２００１２６ＳｉｅｍｅｎｓＳｈａｎｇｈａｉＭｏｂｉｌｅＣｏｍｍｕｎｉｃａｔｉｏｎｓＬｔｄ，Ｓｈａｎｇｈａｉ２００１２６，ＣｈｉｎａＥ－ｍａｉｌ：ｈｕａｎｇ．ｆｅｎｇ＠ｓｉｅｍｅｎｓ．ｃｏｍＦＥＮＧＨｕａｎｇ．ＩｍｐｌｅｍｅｎｔａｔｉｏｎａｎｄｐｅｒｆｏｒｍａｎｃｅｏｆＦＦＴａｎｄｃｏｎｖｏｌｕｔｉｏｎｉｎｉｍａｇｅｆｉｌｔｅｒｉｎｇｏｎＧＰＵ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００８，４４（２）：１２０－１２２．Ａｂｓｔｒａｃｔ：Ｉｍａｇｅｆｉｌｔｅｒｉｎｇａｐｐｒｏａｃｈｅｓａｒｅｉｍｐｏｒｔａｎｔｐａｒｔｏｆｍａｎｙｃｏｎｔｅｍｐｏｒａｒｙｉｍａｇｅ－ｐｒｏｃｅｓｓｉｎｇｔｏｏｌｓ．Ｓｉｎｃｅｉｍａｇｅ－ｆｉｌｔｅｒｉｎｇａｐ－ｐｒｏａｃｈｅｓａｒｅｖｅｒｙｃｏｍｐｕｔａｔｉｏｎａｌｌｙｄｅｍａｎｄｉｎｇ，ｔｏｐｒｅｓｅｒｖｅｉｎｔｅｒａｃｔｉｖｉｔｙｏｆｔｈｏｓｅｔｏｏｌ，ｕｓｉｎｇＧｒａｐｈｉｃｓ－Ｐｒｏｃｅｓｓ－Ｕｎｉｔ（ＧＰＵ）ｔｏａｃｃｅｌｅｒ－ａｔｅｔｈｅｉｍａｇｅｆｉｌｔｅｒｉｎｇｍａｙｂｅａｇｏｏｄｗａｙｏｕｔ．ＩｎｔｈｉｓａｒｔｉｃｌｅｔｈｅａｕｔｈｏｒｇｉｖｅｓｔｈｅＧＰＵｉｍｐｌｅｍｅｎｔａｔｉｏｎｏｆｔｗｏｂａｓｉｃａｐｐｒｏａｃｈｅｓｔｏｉｍａｇｅｆｉｌｔｅｒｉｎｇＦａｓｔＦｏｕｒｉｅｒＴｒａｎｓｆｏｒｍ（ｆｒｅｑｕｅｎｃｙｄｏｍａｉｎ）ａｎｄｃｏｎｖｏｌｕｔｉｏｎ（ｓｐａｔｉａｌｄｏｍａｉｎ），ａｎｄｅｖａｌｕａｔｅｔｈｅｓｅｍｅｔｈｏｄｓｉｎｔｅｒｍｓｏｆｔｈｅｐｅｒｆｏｒｍａｎｃｅａｎｄｓｕｉｔａｂｉｌｉｔｙｆｏｒＧＰＵｉｍｐｌｅｍｅｎｔａｔｉｏｎ．Ｃｏｎｖｏｌｕｔｉｏｎｙｉｅｌｄｓｂｅｔｔｅｒｐｅｒｆｏｒｍａｎｃｅｉｎｍａｎｙｃａｓｅｓ，ａｎｄｔｈｅａｕｔｈｏｒａｌｓｏｉｄｅｎｔｉｆｉｅｓｃｏｎｄｉｔｉｏｎｓｕｎｄｅｒｗｈｉｃｈｔｈｅＦＦＴｇｉｖｅｒｓｂｅｔｔｅｒｐｅｒｆｏｒｍａｎｃｅ．Ｋｅｙｗｏｒｄｓ：ＦａｓｔＦｏｕｒｉｅｒＴｒａｎｓｆｏｒｍａｔｉｏｎ（ＦＦＴ）；ｃｏｎｖｏｌｕｔｉｏｎ；ＧｒａｐｈｉｃｓＰｒｏｃｅｓｓｉｏｎＵｎｉｔ（ＧＰＵ）；ｉｍａｇｅｆｉｌｔｅｒｉｎｇ摘要：图像滤波器是当前绝大多数图像处理软件中的重要组成部分；然而，图像滤波对于计算量的要求是巨大的，为了加强图像处理软件的人机交互性能，使用ＧＰＵ（可编程图形处理器）来加速图像滤波，是一个很好的选择。讨论了在ＧＰＵ上两种图像处理工具的实现：频域上的快速傅立叶变换和空间域上的卷积运算，并评估了这两种工具在ＧＰＵ上的性能表现。卷积运算在一般情况下表现出来比ＦＦＴ更好的性能；并同时讨论了在ＦＦＴ运算有更佳性能的情况。关键词：快速傅立叶变换；卷积；可编程图形处理器；图像滤波文章编号：１００２－８３３１（２００８）０２－０１２０－０３文献标识码：Ａ中图分类号：ＴＰ３９１１２０２００８，４４（２）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用Ｆ（ｕ，ｖ）＝１Ｎ２Ｎ－１ｘ＝０!Ｎ－１ｙ＝０!ｆ（ｘ，ｙ）ＷｕｘＮＷｖｙＮ，０≤ｕ，ｖ≤Ｎ－１（３）其中ｆ（ｘ，ｙ）为一Ｎ×Ｎ的二维离散信号。根据二维离散傅立叶变换的可分离性，二维傅立叶变换可以分解为两步，其中每一步都是一个一维傅立叶变换：首先，对于每一个ｘ值，ｆ（ｘ，ｙ）先沿每一行进行一次一维ＦＴ，得到Ｆ（ｘ，ｖ），然后将其沿每一列在进行一次一维ＦＴ，就可得到二维傅立叶变换Ｆ（ｕ，ｖ）：Ｆ（ｘ，ｖ）＝１ＮＮ－１ｙ＝０!ｆ（ｘ，ｙ）ＷｕｙＮ，Ｆ（ｕ，ｖ）＝１ＮＮ－１ｙ＝０!Ｆ（ｘ，ｙ）ＷｖｘＮ（４）朴素的离散傅立叶变换的时间复杂度为Ｏ（Ｎ２），而快速傅立叶变换可以将这个复杂度降为Ｏ（ＮｌｏｇＮ）。采取频率抽取（ＤＩＴ）基２算法，其模型可以用蝶形网络图１，图２来表示。由图可见，由于ＤＩＴ算法的输出值和正常顺序有一个码位倒置的关系，所以需要将其做一次转换然后作为最终输出。２．２空间域卷积两个大小为Ｎ×Ｎ的二维离散信号ｆ（ｘ，ｙ）和ｈ（ｘ，ｙ）的卷积可以定义为：ｙ（ｘ，ｙ）＝１Ｎ２Ｎ－１ｍ＝０!Ｎ－１ｎ＝０!ｆ（ｘ－ｍ，ｙ－ｎ）ｈ（ｍ，ｎ）（５）在图像处理领域里面，若一个信号代表输入图像，则另一个为滤波器的核。３在ＧＰＵ上的实现３．１ＦＦＴ在ＧＰＵ上的实现正如之前所说，２Ｄ图像的傅氏变换可以转化为两步一维傅氏变换，而所有的一维傅氏变换又可以转换为步ｌｂＮ的运算，前一步计算的输出就是后一步计算的输入；结合ＧＰＵ编程接口的特殊性，设计了一个双缓存系统：将初始输入图像传输到其中一个缓存内作为ｔｅｘｔｕｒｅ输入，而另一个缓存作为Ｒｅｎ－ｄｅｒ－Ｔａｒｇｅｔ输出，每一次ＧＰＵ管线的渲染动作就是一步ＦＦＴ的运算，渲染一次后将两个缓存的角色对调，上次的输入缓存作为这次的输出缓存，上次的输出缓存作为这次的输入缓存，由于二维ＦＦＴ需要进行两步，所以共计进行２×ｌｂＮ＋２次的渲染（包括两次输出的转置运算），就可以得到输入图像的ＦＦＴ变换结果。下面讨论每一步的ＦＦＴ计算。由图１可以看出，在每一步计算中，输出ｐｉｘｅｌ的值都是由在输入ｔｅｘｔｕｒｅ上与它位置相同的ｔｅｘｅｌ加上另一个不同位置的ｔｅｘｅｌ乘以因子±ＷｋＮ得到的。与它位置相同的ｔｅｘｅｌ的纹理坐标可以从像素着色器的纹理坐标输入中取得，而另一个ｔｅｘｅｌ的纹理坐标，可以预先离线计算求得，而计算因子ＷｋＮ可以分解为：ＷｋＮ＝ｃｏｓ（２!ｋＮ）－ｉｓｉｎ（２!ｋＮ）（６）因为一共只有离散的Ｎ个正弦值和余弦值，所以它们也可以很快的预先计算好并通过ｔｅｘｔｕｒｅ来输入。在ＤＩＦ的最后的转置计算中，通过预先计算的码位转置的纹理坐标，也能够很容易的在一次渲染中将输出次序重排。基于以上讨论，设计了这样的一个计算因子ｔｅｘｔｕｒｅ，其数据的结构如图３所示，在前ｌｏｇ（Ｎ）个ｔｅｘｔｕｒｅ中，每个ｔｅｘｅｌ的Ｒ通道存放了第二输入的符号信息，Ｇ通道存放了第二输入的纹理坐标，而Ｂ通道和Ａ通道则存放了相应的正余弦值。值得注意的是由于所有的采样都在相同行（列）中进行，所以第二输入的纹理坐标只需要占用一个通道。在ＤＩＦ的最后一步，并不需要正余弦信息，所以Ｂ通道存放了经过码倒置的纹理坐标。通过这样的ＦＦＴ在ＧＰＵ上实现，做到了使用最简的着色器代码，在代码中没有用到跳转和循环等控制流语句，这样即使在较老一些的ＧＰＵ上也能够运行并获得较高的效率。３．２空间域卷积的实现在ＧＰＵ上实现空间卷积算法原理十分简单，在每个像素上通过其自身的纹理坐标输入获得邻接点的纹理坐标值，采样得到邻接点的像素值，然后和滤波器核进行卷积运算操作。通过一个循环很容易实现。但是随着滤波核的增大，每个像素处理需要执行的指令条数会迅速增多。而ＳＭ（ＳｈａｄｅｒＭｏｄｅ）２．０的ａｓｍ指令条数限制在了９６条以内，这就使滤波核的规模限制在了很小的范围内。到了ＳＭ３．０，每个着色器可以使用最多３２７６８条指令，这就给与了更多的自由度，允许使用更大的滤波核。在即将到来的ＳＭ４．０，着色器指令条数可以没有限制，这将意味着滤波核的大小也可以不受限制。但在当前，尤其是一些较老的ＧＰＵ上，滤波核还无法做到很大。滤波核的可分离性会严重影响到卷积运算的性能，因为可分离的二维卷积可以分解为两个一维的卷积，这样计算的复杂度就由原来的二次方关系降为线性关系，可以节省很多指令冯煌：ＧＰＵ图像处理的ＦＦＴ和卷积算法及性能分析１２１２００８，４４（２）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用条数。更优化的卷积实现方式是将所有采样点的纹理坐标与滤波核的数据预先计算好放到ｔｅｘｔｕｒｅ内，在计算卷积时读取。这样Ｓｈａｄｅｒ代码中就不会出现流控制指令，但是代码长度同样无法得到控制，依然受到软硬件环境的影响。４实验结果比较和讨论本文的实验平台环境为ＡＭＤＡｔｈｌｏｎ６４３５００＋，１ＧＢ内存，ＧＰＵ为Ｎｖｉｄｉａ７６００ＧＳ，２５６ＭＢ显存，ＣＰＵ和ＧＰＵ在２００６年都是主流的民用配置。无庸置疑，ＧＰＵ的ＳＩＭＤ架构决定了它在处理大量数据方面的优势，无论是ＦＦＴ还是卷积运算，在ＧＰＵ上的性能表现都大大超出了其在ＣＰＵ上的版本。图４显示在用卷积运算处理２５６×２５６和５１２×５１２大小的图像时，ＧＰＵ的处理速度平均是ＣＰＵ的３倍，若将ＧＰＵ的处理精度由３２ｂｉｔ减少到１６ｂｉｔ，其性能还会有大幅度的提高，而ＣＰＵ的３２位架构使得其不会从精度的损失上取得性能的提升。在ＧＰＵ上对一个２５６×２５６的图像作ＦＦＴ约耗时５．２ｍｓ，而在ＣＰＵ上则大约要用１８ｍｓ，性能提升的比例约为３．４，在这里ＦＦＴ的ＣＰＵ版本是Ｍ．Ｆｒｉｇｏ和Ｓ．Ｇ．Ｊｏｈｎｓｏｎ的ＦＦＴＷｌｉ－ｂｒａｒｉｅｓ［３］，这是一个高度优化的算法，使用了许多现代ＣＰＵ的特性。而将经过ＦＦＴ变换的图像乘以滤波器在ＣＰＵ上还要花去大约１０ｍｓ而在ＧＰＵ上只需要额外的０．１ｍｓ，这似乎和总线中的数据传输速度有关，并不完全是ＣＰＵ性能所致。接下来将比较同样在ＧＰＵ上的ＦＦＴ和卷积的性能差异。在采用单个高斯低通滤波器的情况下，测试了ＦＦＴ和卷积在处理２５６×２５６，５１２×５１２和１０２４×１０２４大小的图像时表现出来的性能，图５显示了ＦＦＴ和不同滤波核大小的可分离或不可分离的卷积运算的帧率。从图中可以看出随着图像的变大，ＦＦＴ和卷积运算的性能下降比例是不一样的，这可以用两者的基本运算单元次数来解释。对一个Ｎ×Ｎ大小的图像进行可分离卷积滤波的复杂度为Ｏ（２ｋ・Ｎ２），其中ｋ为滤波核的大小：因为对每一个像素都要在ｘ，ｙ坐标上进行卷积运算；而ＦＦＴ的复杂度则为Ｏ（４Ｎ２・ｌｂ（Ｎ）），因为单次一维ＦＦＴ需要ｌｂ（Ｎ）步计算，而每个像素都需要经过两个坐标轴和正逆共４次这样的变换。当滤波核较小的时候，使用可分离的卷积滤波会比ＦＦＴ快很多；如果在某个滤波核上卷积和ＦＦＴ取得了同样的性能，那么可以称之为临界核，基于上面的复杂度讨论，临界核的大小会随着图像的增大而随之增加，图５中的结果也显示了这一点。如果卷积滤波核是不可分离的，那么它的计算复杂度将是Ｏ（ｋ２・Ｎ２），这是相当慢的，同时也会受到ｐｉｘｅｌｓｈａｄｅｒ指令条数限制的严重制约。在ＳＭ３．０下，可以实现的最大滤波核是９×９的（仅允许１１２次的采样指令）。在现实中很多的应用，象ＨＤＲ图像的色调映射，会对输入图形叠加多次滤波，所以也对卷积和ＦＦＴ的多重滤波性能表现进行了比较。可以想象，对于卷积滤波，每引入一个滤波器，就需要重复一次卷积操作；而对于ＦＦＴ，无论引入多少滤波器，只需要做一次傅立叶正逆变换，叠加一个滤波器仅仅是多加一次乘法，因此当滤波器数量很多时，ＦＦＴ有着更好的效率。从图６中可以看出当滤波器个数变多时，ＦＦＴ逐渐表现出更好的性能，当仅有一个滤波器时，ＦＦＴ和３３像素的滤波核性能相当，而当滤波器个数变为８个时，ＦＦＴ的性能可以达到２１像素的滤波核的水平。表１对ＦＦＴ滤波和卷积滤波的优缺点进行了比较。５结论本文提出了两种基本的图像滤波算法：卷积和ＦＦＴ在表１ＦＦＴ滤波和卷积滤波的优缺点比较ＦＦＴ＋对于任何滤波器性能不受影响＋基本不受硬件条件限制＋可以实现所有频域上的滤波＋多个滤波器的叠加并不影响性能－傅立叶正反变换非常耗时－由于计算步骤过多，对计算精度很敏感，即使是非高动态范围的应用也要有１６ｂｉｔ的精度－仅能使用在大小为２的幂的图像，否则需要扩展图像的大小卷积－复杂度受滤波核影响，大的或不可分离的滤波核性能较低－滤波核的大小受到软硬件环境限制－不是所有滤波器都有合适的滤波核－滤波器的叠加会明显的影响性能＋滤波核小的情况下性能出色＋对计算精度要求不高，８ｂｉｔ的精度足以满足非高动态范围的应用＋对图像大小没有限制（下转１２９页）１２２