六边形格网的快速傅里叶变换

Fast Fourier Transform on the Hexagonal Grid

全球离散格网系统是支持多源地球空间数据融合处理的新型数据模型,傅里叶变换是联系其空域与频域的纽带,对以格网系统为框架的遥感图像的增强具有重要意义。根据三孔六边形格网剖分方案,设计了一种规则六边形格网单元组合结构,并将该结构空间域的二维离散傅里叶变换转化为可以用蝶形算法加速的标准一维变换。采用遥感影像进行实验验证,结果表明本文提出的快速傅里叶变换算法正确、高效,其复杂度为N log2N。随着数据量增大,效率以指数函数形式提高。

Discrete Global Grid System is a new data model which supports the fusion processing of multi-source spatial data.The Fourier Transform connects spatial domain and frequency domain which is significant to the enhancement of remote sensing image based on grid system.According to the subdivision scheme of aperture 3 hexagonal grid,a regular hexagonal structure is designed in this paper.The two-dimensional discrete Fourier on this structure can be transformed into one-dimensional transform which can be accelerated by Cooley-Tukey algorithm.A remote-sensing image is used to verify the proposed method.The experimental result shows the Fast Fourier Transformation investigated in this paper is correct and efficient with a complexity of N log 2N,with the increase of data,the efficiency will grow in an exponential manner.