下载文档原格式
图像处理中的傅里叶变换算法研究傅里叶变换算法是图像处理中的重要算法，它被广泛应用于图像压缩、图像分析、图像识别、图像增强等方面。
本文将从傅里叶变换算法的原理、应用、优化等方面进行探讨。
一、傅里叶变换算法的原理首先，我们需要了解一下傅里叶变换的基本概念。
傅里叶变换的本质是将时间域上的信号转化为频域上的信号，将连续的信号变成了离散的频域表达。
因此，傅里叶变换算法可以被用来分析信号的频率特征和谱形特征。
在图像领域，傅里叶变换被用来将空间域的图像转化成频域上的图像，进而进行图像处理。
具体操作是，将图像分成小块，然后对每个小块进行傅里叶变换，最后得到的频域上的图像可以被用来进行处理和分析。
二、傅里叶变换算法的应用1. 图像压缩图像压缩是一种重要的应用，它可以将大型图像文件压缩成较小的文件。
用傅里叶变换算法进行压缩，可以将图像分解成许多频域上的分量，然后对这些分量进行压缩，最终得到压缩后的图像。
2. 图像增强图像增强是一种对图像进行修复和改善的方法。
傅里叶变换算法可以被用来对图像进行增强，通过对频域上的图像信息进行处理，可以改变图像的亮度、对比度、清晰度等属性。
3. 图像分析傅里叶变换算法在图像分析方面也很重要，它可以帮助分析图像的频谱分布，从而对图像进行分类和识别。
比如，在数字图像处理中，傅里叶变换可以被用来检测图像中的特定形状和模式。
三、傅里叶变换算法的优化傅里叶变换算法虽然在图像处理中被广泛应用，但是其计算量较大，因此速度较慢。
为了解决这个问题，研究者们进行了许多优化工作，包括：1. 快速傅里叶变换算法快速傅里叶变换算法可以将傅里叶变换的运算速度提升到O(n log n)，比普通的傅里叶变换算法快得多。
这个优化方法被广泛应用于图像处理和信号处理领域。
2. 傅里叶变换的并行计算并行计算是一种可以利用多个处理器一起运行程序的方法，在傅里叶变换算法中也被广泛应用。
通过并行计算，可以将傅里叶变换的速度进一步提升。
探究GPU视角下的图像处理并行算法在现代图像处理中，由于图像数据的维度特别高，所以实现图像处理算法的并行化非常重要。
尤其是在GPU（图形处理器）的视角下，GPU拥有数以千计的专用计算单元，可以快速处理高维度的数据，因此GPU在图像处理并行算法中具有得天独厚的优势。
1. 并行渐进式拉普拉斯金字塔算法。
该算法适用于图像的降采样和上采样过程中。
在该算法中，原始图像通过不断的降采样处理生成多尺度图像（金字塔结构）。
然后使用拉普拉斯滤波器进行高通滤波，得到拉普拉斯金字塔。
最后通过高通滤波和下采样重建出原始图像。
在这个过程中，每个层级都可以并行处理。
2. 并行直方图平衡化算法。
直方图平衡化是一种基于像素亮度均衡的技术，它使图像的像素值均匀分布在整个亮度范围内。
在GPU上实现直方图平衡化并行化的方法是将图像划分成许多小块，并在每个小块中分别计算其直方图。
然后将每个小块中的直方图相加，最后通过使用累积直方图重新分配像素值来平衡化整个图像。
3. 并行区域生长算法。
区域生长是一种图像分割技术，可以将相似的像素聚类在一起，形成连续的区域。
在GPU视角下，区域生长可以通过并行处理每个像素来实现。
对于每个像素，首先将其与邻域像素进行比较，并根据相似度判断是否加入区域中。
重复此过程，直到不再向该区域中添加像素。
4. 并行快速傅里叶变换算法。
傅里叶变换是一种频域处理技术，将图像从空间域转换为频域。
GPU具有高速傅里叶变换的硬件支持，因此可以进行并行加速。
快速傅里叶变换算法（FFT）是一种高效的傅里叶变换算法，GPU可以通过并行处理FFT的各个步骤来加速整个算法。
总之，GPU视角下的图像处理并行算法可以大大提高图像处理的效率和速度，从而更好地满足现代图像处理的需求。
基于GPU的多帧信号的FFT并行实现作者：张道成来源：《中国科技博览》2013年第16期摘要随着信息科学技术的发展，快速傅里叶变换已成为当今极其重要的学科和技术领域之一，得到了广泛应用，而GPU强大的浮点计算能力和数据并行处理能力，在数字信号处理等方面得到了越来越多的应用，也带来了很大的加速比。
关键词 GPU FFT 并行中图分类号 TP3 文献标识码 A0 引言快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的快速算法，现已成为数字信号处理的强有力工具。
计算机图形处理器（Graphics Processing Unit，GPU）是指一个单芯片的处理器，近年来，随着GPU可编程性的不断提高，利用GPU来完成图形渲染以外的通用计算得到了越来越多的应用。
1 GPU的发展概况计算机图形处理器（Graphics Processing Unit，GPU）是指一个单芯片的处理器，近年来，随着GPU可编程性的不断提高，利用GPU来完成图形渲染以外的通用计算得到了越来越多的应用，众多运算密集型的应用程序执行速度已经可以通过NVIDIA的GPU产品获得令人瞩目的提升。
2 快速傅里叶变换（FFT）快速傅里叶变换（FFT）是计算离散傅里叶变换（DFT）的快速算法，直接计算有限长为的序列的DFT的公式为：（1.1）其逆变换为：（1.2）其中：（1.3）（1.4）3 多帧信号的FFT在GPU的并行实现目前，NVIDIA公司生产的CUDA软件包中集成了标准的傅立叶变换库——CUFFT，为科研人员提供了方便。
使用CUFFT库的过程如下：1.建立cufftHandle类型的对象，将数据拷贝到显存；2.选择FFT使用的对象，根据自己需要确定使用哪一个函数，本文选择的复数转向复数型的多帧信号一维FFT变换，采用的是cufftExecC2C类型的函数。
3.完成变换，将变换后的数据拷贝回内存。
系统测试环境如下表1所示表1 系统测试环境4 试验结果与分析比较表2分别为不同长度的信号和不同帧的数量时，多帧信号的一维FFT的GPU并行计算结果时间和MATLAB计算结果，其中每次结果都是系统运行10次以上测量取平均值的结果。
２００８，４４（２）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用１引言现代数字图像处理包括很多技术，从简单的图像模糊、锐化，雾化到复杂的高动态范围（ＨＤＲ）图像的色调映射，基本上都使用了一种或者多种图像滤波器的组合。
因此可以说图像滤波器是现代计算机图形学中的关键要素之一。
图像滤波中，又分为两种不同的基本方式：在空间域中的滤波和在频域中的滤波。
在空间域中的滤波很简单，只需要将待滤波的图像和滤波器核进行卷积运算；而在频域的滤波则需要先将图像通过傅立叶变换转换到频域上，然后乘以适当的滤波器，最后，通过傅立叶反变换转换到空间域中。
这两种方式在不同的情况下有着各自的缺点和优点，而且在ＣＰＵ上的实现已经是成熟通用的方法广为人们熟知。
然而由于这两种方法都存在计算量巨大的特点，当待处理的图像比较大的时候，ＣＰＵ的结构特点决定了其的性能往往不能满足图像滤波的实时性要求。
图形处理器（ＧＰＵ）为ＳＩＭＤ架构，决定了它非常适合处理大量数据诸如图像、音频的这类任务。
早期的ＧＰＵ由于是固定管线结构，自由度非常小，人们难以利用其进行３Ｄ图形运算之外的工作。
自从Ｍｉｃｒｏｓｏｆｔ推出ＤｉｒｅｃｔＸ８以后，ＧＰＵ工作管线中加入了可编程单元，使得人们可以使用ＧＰＵ进行一些通用的计算，同样，也给使用ＧＰＵ进行图像滤波处理提供了可能。
关于在ＧＰＵ上实现ＦＦＴ算法，Ｍｏｒｅｌａｎｄ和Ａｎｇｅｌ［１］可能是首先进行尝试的，但由于当时条件限制（他们使用的是ＮＶ５０００系列的ＧＰＵ），许多工作还无法在ＧＰＵ上实现；Ｓｕｍａｍａｗｅｅｒａ和Ｌｉｕ［２］在医疗图像处理上做了很有效地尝试，他们使用时间抽取算法实现ＦＦＴ并把计算量在顶点着色器和像素着色器中做了分摊，但是这种分摊并没有收到很明显的效果，因为老架构的ＧＰＵ顶点运算单元和像素运算单元存在运算能力的不均衡。
本文采用了频率抽取算法在ＧＰＵ上实现了ＦＦＴ算法，在实时图像处理方面将ＦＦＴ和卷积算法就性能和ＧＰＵ实现的适应性方面进行了比较。
基于GPU并行计算的图像处理算法分析与优化图像处理是计算机图形学中的一个重要领域，它涉及到对图像进行各种操作和处理。
随着硬件技术的发展，尤其是GPU并行计算的兴起，图像处理算法可以得到很大的加速和改进。
本文将分析并优化基于GPU并行计算的图像处理算法。
首先，我们需要了解什么是GPU并行计算。
GPU即图形处理器，它由大量的小处理单元组成，可以同时进行大规模的并行计算。
与传统的CPU相比，GPU在并行计算方面具有明显的优势。
在图像处理中，我们可以利用GPU的并行计算能力来加速算法的执行。
一种常见的图像处理算法是卷积操作，它在图像处理中被广泛应用。
卷积操作可以通过利用GPU的并行计算来加快处理速度。
在优化卷积算法时，我们可以考虑以下几点：首先，我们可以通过调整卷积核的大小来优化算法。
较小的卷积核可以减少计算量，从而提高处理速度。
然而，过小的卷积核可能会导致图像的细节丢失。
因此，我们需要在速度和精度之间进行权衡。
其次，我们可以使用分块技术来优化卷积算法。
通过将图像划分为多个小块，并在GPU上并行处理这些块，可以大大加快处理速度。
同时，我们可以利用GPU的共享内存来减少数据的传输时间，进一步提高处理效率。
另外，我们可以考虑使用快速傅里叶变换（FFT）来优化卷积算法。
FFT能够将卷积操作转化为频域上的乘法操作，从而减少计算量。
在GPU上并行计算FFT可以极大地加速卷积算法的执行。
除了卷积操作，图像处理中还有许多其他的算法可以通过GPU并行计算来进行优化。
例如，图像的缩放、旋转和平移等操作都可以利用GPU的并行计算能力来提高处理速度。
此外，一些复杂的图像处理算法，如边缘检测和图像分割，也可以通过GPU并行计算得到加速。
在进行图像处理算法的优化时，我们还需要注意一些问题。
首先，算法的正确性是最重要的。
虽然GPU并行计算可以提高速度，但如果得到的结果不准确，则毫无意义。
因此，我们需要确保优化后的算法能够输出正确的结果。
2维FFT算法实现——基于GPU的基2快速⼆维傅⾥叶变换上篇讲述了⼀维FFT的GPU实现（），后来我⼜由于需要做了⼀下⼆维FFT，⼤概思路如下。
⾸先看的肯定是公式：如上⾯公式所描述的，2维FFT只需要拆分成⾏FFT，和列FFT就⾏了，其中我在下⾯的实现是假设原点在F(0,0)，由于我的代码需要原点在中⼼，所以在最后我将原点移动到了中⼼。
下⾯是原点F(0,0)的2维FFT的伪代码：//C2DFFT//被执⾏2DFFT的是⼀个N*N的矩阵，在source_2d中按⾏顺序储存//⽔平⽅向FFTfor (int i=0;i<N;i++){fft1(&source_2d[i*N],&source_2d_1[i*N],N);}//转置列成⾏for (int i=0;i<N*N;i++){int x = i%N;int y = i/N;int index = x*N+y;source_2d[index] = source_2d_1[i];}//垂直FFTfor(int i=0;i<N;i++){fft1(&source_2d[i*N],&source_2d_1[i*N],N);}//转置回来for (int i=0;i<N*N;i++){int x = i%N;int y = i/N;int index = x*N+y;source_2d[index] = source_2d_1[i];}GPU实现⽆⾮把这些东西转换到GPU上。
我基于OpenGL的fragment shader来计算fft；数据都存放在纹理或者FBO⾥⾯。
和1维fft不同的是，NXN的数据⾥⾯，只是对当前列或者当前排做⼀维FFT，所以bit反转表只需要⼀个1*N的buffer就可以了。
对应的蝴蝶图数据也只需要1*N即可。
所以我们有如下的分配：static ofFbo _fbo_bitrev_table;static ofFbo _origin_butterfly_2d;_fbo_bitrev_table.allocate(N,1,GL_RGBA32F);_origin_butterfly_2d.allocate(N,1,GL_RGBA32F);⾸先要做的是把长度为N的bit反转表求出来，这个只需要求⼀次，所以在最开始的时候就⽤CPU求出来：for(int i=0;i<N;i++){_bitrev_index_2d.setColor(i,0,ofFloatColor(bit_rev(i,N-1),0,0,0));}_bitrev_index_2d.update();//翻转后的索引_fbo_bitrev_table.begin();_bitrev_index_2d.draw(0,0,N,1);_fbo_bitrev_table.end();然后初始化最初的蝴蝶图，这个和1维FFT是⼀样的，只是长度不同⽽已：for(int i=0;i<N;i++){//初始化⼆维蝴蝶图if(i%2==0){_data_2d.setColor(i,0,ofFloatColor(0.f,2.f,0,i+1));}else{_data_2d.setColor(i,0,ofFloatColor(1.f,2.f,0,i-1));}}_data_2d.update();/////////////////2D初始化///////////////////初始化2D蝴蝶图_weight_index_2d[0].begin();_data_2d.draw(0,0,N,1);_weight_index_2d[0].end();//备份2D初始蝴蝶图,⽤于下⼀次新的计算_origin_butterfly_2d.begin();_data_2d.draw(0,0,N,1);_origin_butterfly_2d.end();辅助函数：static unsigned int bit_rev(unsigned int v, unsigned int maxv){unsigned int t = log(maxv + 1)/log(2);unsigned int ret = 0;unsigned int s = 0x80000000>>(31);for (unsigned int i = 0; i < t; ++i){unsigned int r = v&(s << i);ret |= (r << (t-i-1)) >> (i);}return ret;}static void bit_reverse_copy(RBVector2 src[], RBVector2 des[], int len){for (int i = 0; i < len;i++){des[bit_rev(i, len-1)] = src[i];}}下⾯定义计算2维IFFT的函数：void GPUFFT::ifft_2d(ofFbo& in,ofFbo& out,int size);其中in是输⼊，out是输出，size就是N，由初始化的时候传⼊了⼀次，在这⾥写是为了⽅便调试的时候临时改变尺⼨。
GPU平台二维快速傅里叶变换算法实现及应用张全;鲍华;饶长辉;彭真明【期刊名称】《光电工程》【年(卷),期】2016(000)002【摘要】NVIDIA在其GPU平台上开发的FFT库CUFFT经过几次升级，但在二维FFT实现上效率还有提升空间，而且对于特定不能与上下文的计算融合，导致多次对Global memory的访问。
本文分析合并内存访问事务大小与占用率之间的关系，优化使用GPU存储器资源，对小数据量2次幂二维复数FFT在GPU上的实现进行改进，加速比最高达到CUFFT 6.5的1.27倍。
利用实数FFT结果的共轭对称性，算法的效率比复数FFT算法运算量降低了40%。
最后将FFT的改进应用到光学传递函数(OTF)的计算中，采用Kernel 融合的方法，使得OTF的计算效率比CUFFT计算方法提高了1.5倍。
%NVIDIA as the inventor of the GPU provides a library function CUFFT for computing Fast Fourier Transform (FFT). After several generations update of CUFFT, there is still promotion space and it is not suit for kernel fusing on GPU to reduce the memory access and increase the Instruction Level Parallelism (ILP). We develop our own custom GPU FFT implementation based on the well-known Cooley-Tukey algorithm. We analyze the relationship of coalesce memory access and occupancy of GPU and get the optimal configuration of thread block. The results show that the proposed method improved the computational efficiency by 1.27 times than CUFFT 6.5 for double complex data 512×512. And then it is used to the computation of OTF with kernel fusing strategy,and it improved the efficiency of computation about 1.5 times than conventional method using CUFFT.【总页数】7页(P69-75)【作者】张全;鲍华;饶长辉;彭真明【作者单位】中国科学院自适应光学重点实验室，成都 610209; 电子科技大学光电信息学院，成都 610054; 中国科学院光电技术研究所，成都 610209; 中国科学院大学，北京 100049;中国科学院自适应光学重点实验室，成都 610209; 中国科学院光电技术研究所，成都 610209;中国科学院自适应光学重点实验室，成都610209; 中国科学院光电技术研究所，成都610209;电子科技大学光电信息学院，成都 610054【正文语种】中文【中图分类】TP391【相关文献】1.基于GPU平台的模乘算法实现 [J], 王雷;赵龙;韩文报2.基于GPU平台的二维离散余弦算法 [J], 刘峰;施展3.基于GPU的Prewitt算法实现及其在探地雷达中的应用 [J], 彭土有;董清华;;4.GPU并行蚁群算法在中小型无人机二维航迹规划中的应用研究 [J], 杨雅宁;蔺勇5.面向GPU平台的二维FFT的加速技术研究 [J], 陈博伦; 何卫锋因版权原因，仅展示原文概要，查看原文内容请购买。
基于GPU的高性能并行算法在大规模图像处理中的应用研究随着科技的不断进步，图像处理技术在越来越多的领域扮演着越来越重要的角色。
而大规模图像处理难度也越来越大，需要更高效的处理算法来解决这些难题。
GPU并行计算在图像处理中的应用已经有了很长的历史，特别是在图形渲染和图像处理中，GPU已经成为最流行的加速器之一。
本文将介绍基于GPU的高性能并行算法在大规模图像处理中的应用研究，为读者深入了解该领域提供一个全面的视角。
一、广义边缘检测算法广义边缘检测算法在图像处理领域中得到了广泛的应用。
基于GPU的高效并行算法将广义边缘检测算法提升到了一个新的水平。
Lin 等人提出的 CUDA‐based General Edge Detection (CGED)算法基于NVIDIA的CUDA平台实现，使用快速傅里叶变换（FFT）和高斯平滑的方法来改善图像降噪和边缘检测能力。
该算法实现了实时视频流中的广义边缘检测，加速了常规边缘检测方法，并且在最大化准确性的同时显着缩短了处理时间。
二、GPU加速的图像分割图像分割是图像处理中反复出现的问题，特别是在医学图像处理、工业检测、智能运输等领域。
最近的研究中，基于GPU的并行算法已成为主流。
从2005年开始，GPU-based Speed-Up Framework for Merging Region Segmentation（SURF）引入了GPU加速的图像分割。
Han 等人提出了一种GPU分布的图像分割算法：通过并行执行区域生长算法，该算法可以在GPU上快速完成图像分割。
该研究表明，基于GPU的图像分割比传统的CPU百分之五十有效。
三、GPU加速基于加权图的图像修复算法针孔摄影机模型的图像修复问题是图像处理领域中的经典问题。
其中Hardie提出的基于加权图的图像修补算法（WGRA）是当前处理在失真和缺失数据问题上最好的算法之一。
该方法利用图像的局部结构和全局相关性估计和修复图像。
GPU加速的傅里叶变换轮廓术并行计算方法
赵小敏;周波;刘春媛;陶金
【期刊名称】《机械制造与自动化》
【年(卷),期】2013(042)002
【摘要】傅里叶变换轮廓术需要在高分辨率图像上进行相位计算,其耗时较长,不能满足实时处理的要求.相位计算时其待处理的和已处理的数据都是相对独立的图像像素,且计算密度极大,适于并行计算.因此,利用图形处理器的多线程并行处理能力,在GPU上实现了相位的并行计算,解决了在CPU上相位计算速度较慢的问题.实验表明在相位计算质量相同的情况下,经过GPU加速获得了相对于CPU一到两个数量级的加速比,为将傅里叶变换轮廓术应用于实时三维测量奠定了坚实的基础.【总页数】4页(P141-144)
【作者】赵小敏;周波;刘春媛;陶金
【作者单位】黑龙江科技学院,黑龙江哈尔滨150027
【正文语种】中文
【中图分类】TP391.41
【相关文献】
1.傅里叶变换轮廓术的Matlab仿真实现 [J], 吴应山;张启灿
2.基于G PU的轮廓提取算法的并行计算方法研究 [J], 柴志雷;张圆蒲
3.基于傅里叶变换轮廓术的动态液膜测量 [J], 管文洁; 吴庆尉; 公超; 吴迎春; 吴学成
4.基于双椭圆滤波算法的傅里叶变换轮廓术 [J], 徐友洪;童根树
5.基于傅里叶变换轮廓术的高速齿科三维扫描仪实现 [J], 刘斯奇;林晓斌
因版权原因，仅展示原文概要，查看原文内容请购买。
图形处理器上的快速傅里叶变换
邓劲
【期刊名称】《现代电子技术》
【年(卷),期】2007(30)10
【摘要】随着图形处理器(GPU)性能的突飞猛进,以及GPU可编程特性的发展,人们开始将GPU应用到通用计算领域(GPGPU).目前国内在这方面的研究还相对较少.使用改进的按频率划分(DIF)算法,结合相关研究的新进展.在GPU上实现了快速傅里叶变换(FFT),讨论和分析GPU在GPGPU中的应用技巧和技术原理,比较GPU与CPU在GPGPU设计中的差异以及性能表现.对GPGPU设计具有指导作用.
【总页数】4页(P151-154)
【作者】邓劲
【作者单位】电子科技大学,电子工程学院,四川,成都,610054
【正文语种】中文
【中图分类】TP391.41
【相关文献】
1.图形处理器上免组装有限元屈曲分析 [J], 卞翔;方宗德
2.多图形处理器上Lattice-Boltzmann方法的加速 [J], 吴亮;钟诚文;郑彦奎;刘沙;卓丛山;陈效鹏
3.图形处理器上CSB＋-树索引的并行构建算法 [J], 刘勇;奚建清;黄东平;贾连印;苗德成
4.图形处理器上内存数据库索引T-树的研究 [J], 刘勇;奚建清;黄东平;贾连印;苗德
成
5.不规则任务在图形处理器集群上的调度策略 [J], 平凡;汤小春;潘彦宇;李战怀因版权原因，仅展示原文概要，查看原文内容请购买。
光谱学与光谱分析Spectroscopy and Spectral Analysis基金项目：国家自然科学基金：基于多特征关联的复杂地形高分辨率遥感图像匹配技术研究(41201349) 作者简介：杨雪，1986年生，主要从事：遥感算法和空间数据处理基于GPU 的巨幅影像分块技术快速傅里叶变换算法研究 杨雪1,2，李学友3,4，李家国2*，马骏1，余涛2，杨健21.河南大学计算机信息工程学院，河南开封 4750042.中国科学院遥感应用研究所, 北京 100101;3.北京四维空间数码科技有限公司, 北京 100039;4.中国测绘科学研究院, 北京 100830;摘 要 快速傅里叶变换(FFT)是遥感影像处理的基础方法，随着高光谱、高空间和高时间分辨率遥感影像获取能力的提升，如何利用快速傅里叶变换技术处理巨幅遥感影像是当前遥感影像处理技术中的重要环节和研究热点。
本文在分析传统快速傅里叶变换算法的基础上，提出了一种基于GPU 加速的巨幅遥感影像快速傅里叶变换（Huge Remote Fast Fourier Transform, HRFFT ）算法。
通过对CUFFT 函数库中的FFT 算法进行改进，解决了巨幅图像内存或显存溢出的问题。
并结合HJ-1A 卫星CCD 遥感影像，进行对比分析研究，证明了该方法的合理性。
该算法在遥感图像处理项目进行实际应用，取得了很好的效果。
关键词 GPU ，HRFFT ，快速傅里叶变换，遥感影像 中图分类号: TP751 文献标志码: A引 言傅里叶变换是数字图像处理和技术分析的基础，是实现图像滤波、噪声去除、图像压缩和MTF 补偿等过程的基本环节[1]。
Cooley 等1965年提出了快速傅里叶变换（FFT ）算法[2]，加快了离散傅里叶变换（DFT ）的计算速度，减少了数据的计算量，使整个图像处理技术的研究有了突破性的进展。
此后，人们不断研究一些新的算法和软件来提高海量数据的快速傅里叶变换实现算法。
1999年MIT 的MatteoFrigo 和Steven G.Johnson 共同开发的FFTW （Fastest Fourier Transform in the West ）包，是目前世界公认的执行速度最快的FFT 软件，支持一维和多维实数及复数的DFT 并包含对共享和分布式存储系统的并行变换[3]，成功应用于ENVI 和MATLAB 等商业软件。
近年来，随着可编程图像处理器（GPU ）的出现，其强大的并行运算能力、高精度的浮点运算能力以及高速的存储器带宽，将海量数据的快速傅里叶变换推向新的台阶。
研究表明，在GPU 环境下运用统一设备架构（CUDA ）的CUFFT 进行FFT 处理的速度大约是CPU 上的20倍左右[4]。
虽然GPU 处理的速度有了质的飞跃，但与CPU 受到物理内存的限制一样，GPU 在进行FFT 运算时也受到显存容量的限制，特别是随着科学技术的不断发展，遥感影像的光谱、空间和时间分辨率不断提高，单景影像的存储量已超过2GB ，合成后的影像数据甚至高达几十GB 。
如何在有限的条件下实现GB 级遥感影像的FFT 快速运算，是当前研究的热点问题之一。
本文从FFT 基本原理着手，通过将数据分块处理和GPU 加速相结合，突破FFT 运算过程中对巨幅影像大小的限制，并有效地降低了运算的时间。
1 HRFFT 算法1.1 FFT算法基础()x n （01n N ≤≤-）的离散傅里叶变换（DFT ）可以表示为[5]：10()[()]()N nk Nn X k DFT x n x n W -===∑，01k N ≤≤- （1）其中：2j k n kn NNWeπ-= （2）将一维傅里叶变换扩展到二维为：112()00(,)(,)M N ux vyj M Nx y F u v f x y eπ---+===∑∑，（01x M ≤≤-，01y N ≤≤-） （3） 根据二维傅里叶变换的可分离性，可以将一个二维傅里叶变换转化为两个一维傅里叶变换。
快速傅里叶变换（FFT）算法是运用因子的周期性和对称性，逐步分解为短序列的DFT ，再对其组合成原序列DFT ，进而减少运算量。
FFT 算法可以分为时间抽取算法（DFT)和频率抽取算法（DIT ）。
不同的N 值选择的FFT 算法基数也不同。
对于定点FFT 有许多不同的算法结构[6,7]：基-2、基-4及任意按时间抽取，基-2、基-4及任意按频率抽取等。
基-2按频率抽取算法模型蝶形图如图1所示。
N x (0)x (4)x (2)x (6)x (1)x (5)x (3)x (7)X (0)X (1)X (2)X (3)X (4)X (5)X (6)X (7)图1 8点DIT―FFT 运算流图Fig.1 8 DIT - FFT operation flow chart从图1可以看出，通过两个点FFT 蝶形算法可以求出下一个点的值，不断递归此过程，直到经过第logN 步并行计算后，才可以算出一个N 点的一维FFT 。
在计算过程中，并行节点之间需要进行数据传递，而且每一次循环都需要同步执行，才可以进行下一步运算。
由于频域抽取算法的输出结果与正常顺序存在码位倒置的关系，因此需要将其转换后才可以得到最终的输出结果。
1.2 HRFFT 算法受计算机内存容量的限制，巨幅遥感影像需要经过分块处理才能进行FFT 运算。
例如文献[8]提出了一种对影像FFT 处理的中间结果分块存储的方法。
该方法虽然能够处理巨幅影像，但由于全部处理过程由CPU 完成，执行效率比较低。
实验表明，对于一副大约1.6G 的40000×40000大小的影像，处理时间甚至超过24小时，远远不能满足实际应用的需要。
GPU 的出现为图像处理提供了新的实现方法。
Moreland 和Angel 尝试利用GPU 实现快速傅里叶变换[9]，由于受当时GPU 软硬件的限制，虽然最终的结果还不如那时的FFTW 库的效率高，但该文献却展示了运用GPU 在实现FFT 算法上的一个很好的思路和应用前景。
2007年NVIDIA 公司开发了利用GPU 实现影像FFT 运算的CUFFT 库，文献[10]对基于GPU 的CUFFT 库与FFTW 算法进行了实验对比，文献[11-16]均运用GPU 对FFT 算法进行改进，实验表明，这些改进的FFT 算法对一般容量的图像而言均具有较高的实现效率，但对于巨幅影像的处理，仍存在一些问题。
本文在上述文献的基础上，提出了基于GPU 加速的巨幅遥感影像快速傅里叶变换的HRFFT 算法。
基本处理思路是先将巨幅影像按行分块读入内存，然后利用GPU 对每一行块的多个子块进行一维傅里叶变换和渲染；所有行的块处理完毕后，再对每一列块的图像进行一维傅里叶变换；最终实现二维傅里叶变换。
该算法的关键是内存块的大小和显存子块大小的确定，以及在GPU 中处理和渲染子块时如何将中间结果暂存到磁盘的。
1.3分块处理方法巨幅影像数据每次读入内存中的块的大小和在GPU 中进行处理的子块的大小，需要从影像数据存储格式、每像素占用字节数、内存可用空间大小以及GPU 可用显存容量等多个方面综合进行考虑[17]。
具体的分块方法如图2所示。
图2 巨幅影像FFT 变换分块处理示意图 Fig.2 The huge image FFT transform block diagram1.3.1 CPU 处理分块大小的确定FFT 分块算法分为行优先分块和列优先分块两种形式。
本文采用固定列数，行优先分块的原则对FFT 进行分块处理，即先对行进行变换，再对行变换后的结果进列变换。
假设每个像素点在内存中所占的字节数为p ，则一个m ×n 的影像分块数可以用公式表示为：1m n p b a ⎡⎤=+⎢⎥⎢⎥ （4） 其中，a 为处理图像时系统的可用内存，该值可以通过函数自动获取。
此时读入内存的每一块影像的字节数为：m n ps b =（5）1.3.2 GPU 处理子块大小的确定由于显存容量较小，因此还需要将读入到内存中的块划分为更小的子块，才能利用GPU 进行高效处理。
子块的大小会影响到数据在GPU 中运算的速度和数据读写时与I/O 的交互速度。
分的子块太小，将中间结果暂存到磁盘上时，文件读写的次数就很多，增加了I/O 之间的频繁交互；分的子块太大，就会导致显存溢出。
子块大小的计算与读入到内存中的块大小计算相似，不同的是还需要考虑显存的纹理数据存储结构以及在GPU 中进行渲染时所占用的显存空间。
1.3.3 分块处理流程第1步，首先，根据遥感影像和GPU 显存的大小，判断是否对遥感影像进行分块。
如果遥感影像能够被GPU 处理，则将遥感影像全部读入GPU 显存中，利用GPU 并行计算进行遥感影像的二维傅立叶变换；如果遥感影像过大，不能被GPU 处理，则转入下步。
第2步，根据显存大小将整个图像分成若干块。
先将第一块读入内存中。
第3步，将第一块划分成多个可以在GPU 中处理的子块。
第4步，对第一子块数据进行一维傅里叶行变换，并将变换的中间结果渲染到纹理，接下来对第二子块进行一维傅里叶行变换，直到变换的结果数据与纹理大小相等时，然后将结果进行分块，写入磁盘中，记下地址。
第5步，重复第4步，将第1块的所有子块进行一维傅里叶行变换，并对每一次变换的结果进行分块，写入磁盘，追加到之前的结果块的地址后面，存入到磁盘中。
第6步，重复以上步骤，直到整幅图像的一维傅里叶行变换结束。
第7步，根据影像结果存储的位置，按照之前所分块的结果数据，读取每一列块的影像数据。
第8步，对一列块的影像数据按列进行一维傅里叶列变换，记下每次变换结果的地址，写入磁盘。
第9步，重复步骤7～8，完成所有列块的处理完，得到傅里叶正变换后的结果。
傅里叶逆变换和正变换过程相反。
1.4渲染加速与中间结果保存显存中的数据都是以纹理方式进行存储的。
由于CPU 中数据是以数据形式进行存储的，实现中间结果的存储很容易，统一的存储器模型决定它可以在程序中任何地方进行存储器的读写操作，GPU 采用的是流式编程模型，运算通常是线性的[18]，运算时需要先把数据存放到纹理中，由于数据运算存在依赖性，实现迭代操作就很困难。
因此，为了减少读写操作的次数，本文采用渲染到纹理技术对CUFFT 库进行改进。
首先构造一个高速显存的缓存区Pbuffer ，将每一次CUFFT 算法的处理结果直接输出到Pbuffer ，并绑定到纹理，作为CUFFT 逆变换的输入数据，当计算的影像数据比较大时，可以同时构造两个Pbuffer ，交替存放输出的计算结果和输入的结果。
这样就避免了将中间结果不断写入磁盘，减少了与I/O 交互的次数。
大大提高了运算的速度。
