图像傅里叶变换反变换的实现

1、课程大作业实验报告图像傅里叶变幻、反变换的实现课程名称：数字图像处理 组 长： 王文雄 学号：200730590323 年级专业班级：07通信3班成员一： 庞柱坚 学号：200730590318 年级专业班级：07通信3班 成员二： 王弥光 学号：200730590322 年级专业班级： 07通信3班 成员三： 学号： 年级专业班级：07通信3班 指导教师 邓继忠报告提交日期2010年6月1日项目答辩日期2010年6月1日目 录1.项目要求32.项目开发环境33.系统分析33.1.系统的主要功能分析33.2.系统的关键问题及解决方法（或思路）54.系统设计84.1.程序流程图及说明84.2.程

2、序主要模块（或功能）介绍104.2.1.一维 FFT 和 IFFT104.2.2.二维图像 FFT 和 IFFT：115.实验结果与分析125.1.实验结果125.2.项目的创新之处135.3.存在问题及改进设想136.心得体会146.1.系统开发的体会146.2.对本门课程的改进意见或建议147.附件一151. 项目要求1.基本要求：自修教材相关内容（P52-74）或其它参考资料，在CVI下编程对尺寸为2N(N为正整数)的图像进行FFT(快速傅里叶变换)和(快速傅里叶反变换)。（不能利用CVI下的函数）2.题目拓展：编程实现任意大小图像的二维傅立叶的变换与反变换。2. 项目开发环境项目开发环

3、境主要分为软件环境和硬件环境软件：Lab Windows/CVI和IMAQ_Vision for LabWindows/CVI。Lab Windows/CVI是美国National Instrument(简称NI)公司开发的基于C语言的虚拟仪器开发平台，适用于自动测试、自动控制、测试仪器通信、测试硬件控制、信号分析及图像处理等软件的开发。经过版本的不断更新，Lab Windows/CVI已经成为测控领域应用最为广泛的软件开发工具之一。而IMAQ_Vision for LabWindows/CVI是NI公司开发的基于LabWindows/CVI的高级图像处理和分析软件包，是进行图像处理和分析的教

4、学和科研的有力工具。软件包提供了3个重要的文件：硬件：个人PC电脑（主频：2.6GHZ*2 内存：1G*2）3. 系统分析3.1. 系统的主要功能分析傅里叶变换是研究信号频域特性首要数学工具。在数字图像频域处理中，常常要对二维图像做快速傅里叶变换，由于傅里叶变换的可分离性，二维快速傅里叶变可以分解为对行、列两个方向的一维快速傅里叶变换，所以在LabWindows/CVI 集成开发环境下实现二维图像的快速傅里叶变换的关键是一维傅里叶变换的实现。在本系统设计过程中，主要分成两个部分完成：第一部分是一维快速傅里叶变换，该部分所包含的变量函数基本上不依赖于特定的软件平台，仅仅与C语言有关，这部分是为二

5、维快速傅里叶服务的。主要有内容及其作用如表格1所示。 表 1 一维快速傅里叶变换及反变换功能模块列表内容C程序（数据定义、函数声明等）功能复数数据类型定义typedef structdouble real;double img;complex;定义描述快速傅里叶变换及其反变换数据的类型。复数类型的四则运算void add(complex a, complex b, complex *c);void mul(complex a, complex b, complex *c);void sub(complex a, complex b, complex *c);void divi(complex

6、a, complex b, complex *c);这四个函数分别完成两个复数类型数据a和b的加法、减法、乘法和除法运算，运算结果存放于指针c指向的数据空间。初始化快速傅里叶变换及其反变换变换核void initW(int legnth);该函数完成的计算，在碟新运算时需要用到；参数legnth是一次快速傅里叶变换或反变换的数据长度。“倒位序”处理函数void change(int legnth, complex source);该函数完成数据的自然顺序到“倒位序”的变换处理或是“倒位序”到自然顺序的变换处理；参数legnth是一次快速傅里叶变换或反变换的数据长度，source是待变换的数据。

7、快速傅里叶变换void fft(int length, complex src);该函数完成对个复数数据的快速傅里叶变换；参数legnth是一次快速傅里叶变换的数据长度，source是待变换的数据。快速傅里叶反变换void ifft(int length, complex src);该函数完成对2的N次方个复数数据的快速傅里叶反变换；参数legnth是一次快速傅里叶反变换的数据长度，source是待变换的数据 第二部分是二维快速傅里叶变换及其反变换，该部分主要是在一维快速傅里叶变换及其反变换的基础上，完成对一幅二维图像的快速傅里叶变换及其反变换，并将结果显示出来。主要函数模块及其功能如表格2所

8、示。表2 二维快速傅里叶变换及反变换功能模块列表 3.2. 系统的关键问题及解决方法（或思路）二维图像的快速傅里叶变换及其反变换可以分解成行、列两个方向上的一维快速傅里叶变换及其反变换，由因为快速傅里叶变换和反变换的原理是一致的，所以，在整个系统设计的过程中，最关键的问题就是如何用C语言程序描述模拟整个快速傅里叶变换的运算流程。为了解决这个问题，根据快速傅里叶变换运算流图，将整个变换过程分层描述，共分解为3个层次：“级”、“组”和“个”。一个快速傅里叶变换运算过程分为i个级，每个级包含j个组，每个组又包含k个单个蝶形运算。例如如图1所示的N=8的快速傅里叶变换的运算流图，该流图共分为3个级：第

9、一级包含4个组，每个组又1个单个蝶形运算；第二级包含2个组，每个组有2个单个蝶形运算；第三级包含1个组，每个组有4个蝶形运算。图1 N=8的快速傅里叶变换蝶形运算流图 在函数fft(int length, complex src)实现时使用3重for循环来描述，最外层for循环是对“级”的循环，第二层for循环是对每一级里“组”的循环，最内层for循环是对每一组里“个“，即单个蝶形运算的循环。程序代码如下所示：/*快速傅里叶变换*/void fft(int length, complex src)int i=0;/1次FFT蝶形运算"级数"计数器int j=0;/1级FFT

10、蝶形运算"组数"计数器int k=0;/1组FFT蝶形运算"个数"计数器int Distance=0;/1个FFT蝶形运算跨越的"距离"int Step=0;/计算一级运算当前已经走过的步长int grade=0;/FFT蝶形运算级数寄存器int group=0;/FFT蝶形运算组数寄存器int unit=0;/FFT蝶形运算个数寄存器complex up;/1个蝶形运算中间结果寄存器complex down; /1个蝶形运算中间结果寄存器complex product;/1个蝶形运算中间结果寄存器/*先对原始数据做"到位序

11、"处理*/change(length, src);/*计算1次FFT的级数总数grade*/grade=(int)(log(length)/log(2);for(i=0;i< grade ;i+) /*计算第i级运算包含组数group*/group=(int)pow(2,(double)(grade-1-i);/*计算单个蝶形运算跨越距离*/Distance=1<<i;/*一级蝶形运算*/for(j=0;j<group;j+ )/*计算一级运算当前已经走过的步长*/Step=2*Distance*j;/*计算一组蝶形运算中包含的蝶形运算个数unit*/unit

12、=(int)pow(2,(double)(i);/*一组蝶形运算*/for(k=0;k<unit;k+) /*一个蝶形运算*/mul(srcStep+k+Distance,Wlength*k/2/Distance,&product);add(srcStep+k,product,&up);sub(srcStep+k,product,&down);srcStep+k=up;srcStep+k+Distance=down;4. 系统设计4.1. 程序流程图及说明整体程序流程图如下所示：图2 整体程序流程图说明：A.当开始运行程序后，通过点击“打开一幅图像并显示”按钮，在

13、弹出的对话框中选择一幅格式符合要求的图像并确定，之后程序就会在另一个名为“源图像”的窗口中显示原始图像并在主界面中显示原始图像宽度和高度。按钮“打开一幅图像并显示”左边的指示LED灯亮，表示已经打开一幅图像，并可以开始下面的操作。 B.打开一幅图像后，点击“傅里叶变换”按钮，对原始图像进行二维FFT变换，得到变换后的数据，并在一个名为“FFT图像”的窗口中显示经过傅里叶变换后的复数图像。 C.点击“傅里叶反变换”按钮，对第二步中二维傅里叶变换变换得到的数据进行二维傅里叶反变换，恢复原始图像，并在一个名为“IFFT图像”的窗口中显示。 D.如果此时要退出程序，那么就点击“退出”按钮；如果不想退出

14、，想对另外一幅图像进行13步的操作，那么就点击“清除”按钮，程序会重新回到刚运行程序的状态。4.2. 程序主要模块（或功能）介绍4.2.1. 一维 FFT 和 IFFT 流程图：图3 一维FFT 和 IFFT流程图说明：A.FFT和IFFT的运算及其总体流程图是相同的，均是按以上流程图来实现。B.首先，先计算 。 C.对输入数据x(n)进行位倒序处理。 D.接着，根据运算流图进行三重for循环运算，最后得出结果。E.grade是指一次FFT或IFFT运算分级的总数；group是每个级分组的总数；unit是每个组包含蝶形运算的总数。F.对于得出自然顺序的结果，可以用两种方法去实验，一是输入数据经

15、过位倒序处理后再运算，输出数据为自然顺序。二是不先对输入数据做位倒序处理，运算后在做处理也可以得到自然顺序的结果数据。4.2.2. 二维图像 FFT 和 IFFT：流程图： 图4 二维FFT和IFFT流程图说明：1、二维图像FFT和IFFT的运算流程图是相同的，均是按上图所示。 2、先通过打开图像来获得width和height，并定义二维数组Bufferwidthheight。 3、width和height分别是原始图像的宽度和高度；Bufferwidthheight是用来存放原始数据、中间运算数据及最终结果的缓冲区。4、 其实，二维数组的运算就是一维数组的变换运算，对Buffer数组的第一行

16、进行FFT或IFFT运算，之后对矩阵进行倒置，再对此矩阵的第一行进行FFT或IFFT运算，再进行多一次倒置，进而得出结果。5、对于最终结果的显示是通过在CVI下用复数图像显示。5. 实验结果与分析5.1. 实验结果（应有实验结果的图片，有结果分析或说明）下面表格里是3组实验图片，从左到右分别是原始图像、经过快速傅里叶变换后的到的数据转换而来的FFT图像（complex image）以及通过对快速傅里叶变换得到的数据进行快速傅里叶反变换恢复的图像。从3组实验图片的FFT图片表示中，可以看出图像中央是直流低频成分，四角是高频成分。从3组图像的源图像与IFFT图像的比较中可知，从快速傅里叶变换结果数

17、据用反变换的来的图像与原始图像几乎是相同的，由此证明程序是正确的。序号原始图像FFT图像IFFT图像123 图5 三组实验结果5.2. 项目的创新之处 本设计其实并没有创新之处。如果要说做的比较好的地方的话，那就是使用malloc（）动态分配内存空间，包括快速傅里叶变换及其反变换的缓冲区，用于数组到图像转换的一维数组空间等。使用动态分配空间可以适应不同大小的图片（图像宽度和高度可以不同，但仍然需要满足2的N次方条件），另外就是动态分配的内存空间使用完后及时回收，节省对内存空间的资源和提高利用率。5.3. 存在问题及改进设想 对本设计中存在的问题是快速傅里叶变换及其反变换所用的时间比较长，原因可

18、能有以下两点：一是描述complex数据类型的实部虚部成员使用double类型（64位）过大；二是在快速傅里叶变换及其反变换程序实现时，在一些运算量比较大的地方，例如for循环里，不必要的重复运算过多。 针对上面问题，本组认为可以从选择合适的数据类型和优化程序代码等方面入手，较少运算时间。6. 心得体会6.1. 系统开发的体会 在本设计中，本组成员体会比较深刻的是分层和面向过程的程序设计思想。首先，对于一个比较复杂的程序可以简化思路，提高代码可读性等等，这是对程序设计的纵向优化。在本系统设计中，主要有两个地方体现了这一思想。一是对于一维快速傅里叶变换及其反变换的实现过程，结合运算流程的特点，将

19、一个运算流程分解成若干级，每个级中包含若干组，每个组中又分成若干个单个的蝶形运算，这样子分层，可以使得程序设计更为清晰，系统化，也便于理解；二是将一维快速福利叶变换及其反变换与二维的分离开。其次是面向过程程序设计。在系统设计中，把不同功能的程序封装成各个独立的函数，使得代码重用性，可读性提高，也便于以后的修改。例如把一维快速傅里叶变换或反变换封装函数供二维变换调用。6.2. 对本门课程的改进意见或建议对本门课程的改进意见或建议：其实，课程的主要目的都是在于提高学生的学习热情和创新意识，这有利于多方面开发学生智力，提高学生的综合素质等。 所以，对于这门课程更有利开展，如果条件允许的话，可以尝试整合课程教学资源，例如包括课程介绍、教学大纲、授课