遥感图像快速傅立叶变换新算法的研究与实现
|
摘要
图像的快速傅立叶变换是众多数字图像处理算法的关键步骤，也是各种频率域分析算法的第一步。现有的图像FFT算法存在处理速度缓慢的缺点，这严重制约了其各种应用的整体运算效率。
本文在分析传统算法的速度瓶颈基础上，从两方面着手采取了一系列优化措施，一是提升FFT运算本身的速度，另一方面是在做行列转置过程中，优化读写磁盘操作的效率。这些优化措施主要包括：
1) 将国际上先进的FFTW算法引入到图像的二维FFT计算中。
2) 提出了以分块的方式存储二维FFT运算的中间结果，大幅提升行列转置时文件读写的效率。
3) 研究了文件缓存对存取文件数据速度的影响，对此进行了优化。
4) 采用并行处理方式，在进行FFT运算的同时进行中间数据的读写操作，解决了CPU长时间空闲的问题。
这些改进大幅提升了图像的FFT运算速度，实验表明，本算法的处理速度是ERDAS遥感软件的4—5倍。
另外，本算法程序还有使用简单，便于扩展的优点，可以很方便地推广到诸如小波变换、离散余弦变换等领域。
Fast Fourier Transforms (FFTs) are efficient algorithms for calculating the discrete fourier transform(DFT), it's the most important approach to many Digital Image Processing algorithms. Traditional algorithms for FFT of huge images are inefficient and the speed is slow, which limit its application.
On the basis of analyzing the bottle neck of traditional algorithms, this paper develops a series of approach to improve the efficience in two aspects: one is to speed up the FFT algorithm which is use to compute the FFT of each row and column; another is to improve the speed of file I/O while interconverting the result of FFTs between row and column. The most work is followed:
1) A FFTW algorithm is introduced to be used as FFT of image.
2) The intermediate result of FFTs is saved to disk in blocks, which optimizes the interconverting of row and column.
3) The using of intermediate buffering of file I/O is optimized, which increases the performance of reading and writing large amount of file data.
4) A parallel processing is used to enable performing FFT calculating synchronously while file I/O is running.
Experiment shows that our algorithm is competitive to many popular image processing software such as PCI and ERDAS.
本文在分析传统算法的速度瓶颈基础上，从两方面着手采取了一系列优化措施，一是提升FFT运算本身的速度，另一方面是在做行列转置过程中，优化读写磁盘操作的效率。这些优化措施主要包括：
1) 将国际上先进的FFTW算法引入到图像的二维FFT计算中。
2) 提出了以分块的方式存储二维FFT运算的中间结果，大幅提升行列转置时文件读写的效率。
3) 研究了文件缓存对存取文件数据速度的影响，对此进行了优化。
4) 采用并行处理方式，在进行FFT运算的同时进行中间数据的读写操作，解决了CPU长时间空闲的问题。
这些改进大幅提升了图像的FFT运算速度，实验表明，本算法的处理速度是ERDAS遥感软件的4—5倍。
另外，本算法程序还有使用简单，便于扩展的优点，可以很方便地推广到诸如小波变换、离散余弦变换等领域。
Fast Fourier Transforms (FFTs) are efficient algorithms for calculating the discrete fourier transform(DFT), it's the most important approach to many Digital Image Processing algorithms. Traditional algorithms for FFT of huge images are inefficient and the speed is slow, which limit its application.
On the basis of analyzing the bottle neck of traditional algorithms, this paper develops a series of approach to improve the efficience in two aspects: one is to speed up the FFT algorithm which is use to compute the FFT of each row and column; another is to improve the speed of file I/O while interconverting the result of FFTs between row and column. The most work is followed:
1) A FFTW algorithm is introduced to be used as FFT of image.
2) The intermediate result of FFTs is saved to disk in blocks, which optimizes the interconverting of row and column.
3) The using of intermediate buffering of file I/O is optimized, which increases the performance of reading and writing large amount of file data.
4) A parallel processing is used to enable performing FFT calculating synchronously while file I/O is running.
Experiment shows that our algorithm is competitive to many popular image processing software such as PCI and ERDAS.
引文
[1] 赵忠明，朱重光．遥感图像中薄云的去除方法，环境遥感．Vol．11， No．2，1996．8
[2] 赵荣椿，赵忠明，崔甦生．数字图像处理导论．西北工业大学出版社，1995
[3] M. Frigo and S. G. Johnson.FFTW: An Adaptive Software Architecture for the FFT. 1998 ICASSP conference proceedings (vol. 3, pp. 1381-1384)
[4] M. Frigo and S. G. Johnson.The Fastest Fourier Transform in the West. MIT-LCS-TR-728 (September 1997)
[5] Matteo Frigo. A Fast Fourier Transform Compiler. 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'99)
[6] M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-Oblivious Algorithms.(FOCS'99).
[7] Jim Beveridge&Robert Wiener著，候捷 译，The Complete Guide to Threads，(中文)win32多线程程序设计．华中科技大学出版社
[8] 尤晋元，史美林等。Windows操作系统原理。机械工业出版社
[9] (美)Uwe Meyer-Baese，译者：刘凌 胡永生。数字信号处理的FPGA实现，Digital Signal Processing with Field Programmable Gate Arrays。清华大学出版社，2003
[10] (美)Maurice J．Bach著，陈葆钰 王旭 柳纯录 冯雪山译。UNIX操作系统设计。机械工业出版社，2000
[11] (美)Jeffrey Richter著，王建华 张焕生 候丽坤译。Windows核心编程。机械工业出版社，2000．5
[12] X. Leroy, The Caml Light system release 0.71. Institut National de Recherche en In-formatique at Automatique (INRIA), Mar. 1996.
[13] J. W. Cooley and J. W. Tukey, "An algorithm for the machine computation of the com-plex Fourier series," Mathematics of Computation, vol.19, pp. 297-301, Apr. 1965.
[14] 李象霖。数字图像处理。中科院研究生院数字图像处理课程讲义。
[15] 宁书年，吕松棠，杨小勤等．遥感图像处理与应用．地震出版社，1995
[16] 王恒进．基于小波的遥感图像薄云去除的研究与实现[西北工业大学硕士学位论文]．2002
[2] 赵荣椿，赵忠明，崔甦生．数字图像处理导论．西北工业大学出版社，1995
[3] M. Frigo and S. G. Johnson.FFTW: An Adaptive Software Architecture for the FFT. 1998 ICASSP conference proceedings (vol. 3, pp. 1381-1384)
[4] M. Frigo and S. G. Johnson.The Fastest Fourier Transform in the West. MIT-LCS-TR-728 (September 1997)
[5] Matteo Frigo. A Fast Fourier Transform Compiler. 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'99)
[6] M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-Oblivious Algorithms.(FOCS'99).
[7] Jim Beveridge&Robert Wiener著，候捷 译，The Complete Guide to Threads，(中文)win32多线程程序设计．华中科技大学出版社
[8] 尤晋元，史美林等。Windows操作系统原理。机械工业出版社
[9] (美)Uwe Meyer-Baese，译者：刘凌 胡永生。数字信号处理的FPGA实现，Digital Signal Processing with Field Programmable Gate Arrays。清华大学出版社，2003
[10] (美)Maurice J．Bach著，陈葆钰 王旭 柳纯录 冯雪山译。UNIX操作系统设计。机械工业出版社，2000
[11] (美)Jeffrey Richter著，王建华 张焕生 候丽坤译。Windows核心编程。机械工业出版社，2000．5
[12] X. Leroy, The Caml Light system release 0.71. Institut National de Recherche en In-formatique at Automatique (INRIA), Mar. 1996.
[13] J. W. Cooley and J. W. Tukey, "An algorithm for the machine computation of the com-plex Fourier series," Mathematics of Computation, vol.19, pp. 297-301, Apr. 1965.
[14] 李象霖。数字图像处理。中科院研究生院数字图像处理课程讲义。
[15] 宁书年，吕松棠，杨小勤等．遥感图像处理与应用．地震出版社，1995
[16] 王恒进．基于小波的遥感图像薄云去除的研究与实现[西北工业大学硕士学位论文]．2002