《信号处理原理》实验指导书.doc

《信号处理原理》实验指导 【实验数据】 实验数据为一图像数据文件，文件格式是纯文本格式。文件正文的第一行的值表示矩阵的大小，即N值。后面的N行是点阵图像，每行有N个数据。N最大为256。在图像点阵中，‘.’代表0（即没有点）， ‘o’代表1（即有点）。 具体内容见附件[Data.txt]，这是一个“国”字的点阵文件。 【实验要求】 对输入图象文件内容进行2D－FFT变换，再对所得频谱数据进行2D－IFFT，将结果重新转换成字符文件保存起来。 对输入图象文件内容进行2D－FFT变换，再将频谱的大小压缩为（N/2）*（N/2），然后对所得频谱数据进行2D－IFFT，将结果重新转换成字符，保存成（N/2）*（N/2）的汉字图像。 对输入图象文件内容进行2D－FFT变换，再将频谱的大小压缩为（N/2）*（N/2），然后对频谱补入一些零，再对频谱进行2D－IFFT，将结果重新转换成字符，保存成（N/2）*（N/2）的汉字图像。 【实验原理】 一幅二维数字图像可以用矩阵[g(m,n)]来表示，g(m,n)是图像在坐标(m,n)处的灰度级（或彩色RGB值）。也可以把g(m,n)视为一个二元函数，它的自变量为m和n，则可以用它来表示数字图像在平面上的亮度分布。矩阵可以写成下面的形式： 在上面的基础上，我们可以定义下面的二维DFT： 定义1：二维矩阵向量[g(m,n)]的2D-DFT , 从上面的定义我们可以看出：2D-DFT可以用两次1D-DFT来实现。一次是对g(m,n)的各行（即m相同而n不同）进行1D-DFT---如上式中的红色部分所示；再对变换后的结果，再按列进行1D-DFT---如上式中的蓝色部分所示。 上面这个公式是我们实现2D-DFT的算法基础。 定义2：二维矩阵谱向量[G(p,q)]的2D-IDFT , 根据相同的想法，上面的2D-IDFT公式也可以用两次1D-IDFT来实现。 【2D-FFT算法实现】 二维FFT相当于对行和列分别进行一维FFT运算。具体的实现办法如下： 先对各行逐一进行一维FFT，然后再对变换后的新矩阵的各列逐一进行一维FFT。相应的伪代码如下所示： for (int i=0; iM; i++) FFT_1D(ROW[i]，N); for (int j=0; jN; j++) FFT_1D(COL[j]，M); 其中，ROW[i]表示矩阵的第i行。注意这只是一个简单的记法，并不能完全照抄。还需要通过一些语句来生成各行的数据。同理，COL[i]是对矩阵的第i列的一种简单表示方法。 所以，关键是一维FFT算法的实现。下面讨论一维FFT的算法原理。 【1D-FFT的算法实现】 设序列h(n)长度为N，将其按下标的奇偶性分成两组，即he和ho序列，它们的长度都是N/2。这样，可以将h(n)的FFT计算公式改写如下 ： ………………… (A) 由于 所以，(A)式可以改写成下面的形式： 按照FFT的定义，上面的式子实际上是： 其中，k的取值范围是 0~N-1。 我们注意到He(k)和Ho(k)是N/2点的DFT，其周期是N/2。因此，H(k)DFT的前N/2点和后N/2点都可以用He(k)和Ho(k)来表示 而且 于是，N点H(k)用N/2点的He(k)和Ho(k)来计算的公式为： ( 【1D-FFT的算法流程】 根据上面推导的公式，我们可以用递归程序来实现1D-FFT。下面是一个示例： void FFT_1D (Comp in[ ], Comp out[ ], int N) { Comp he[256], ho[256]; Comp He[256], Ho[256]; // 如果DFT点数为1，则根据DFT公式，可以直接返回原值 // 这是递归的退出条件 if (N==1) { out[0] = in[0]; } else { // 如果N不是1，则… // 按下标将数据分成两组 for (int i=0; iN/2; i++) { he[i] = in[2*i]; // 偶数下标分组 ho[i] = in[2*i+1]; // 奇数下标分组 } // 计算偶数下标部分的N/2点DFT FFT_1D(he, He, N/2); // 计算奇数下标部分的N/2点DFT FFT_1D(ho, Ho, N/2); // 计算当前所有数据的N点DFT for (int k=0; kN/2; k++) { // 下面计算式中的W[k]是旋转因子，可以事先计算好。 // 当前数据的前一半，N/2点 out[k] = He[k] + W[k]*Ho[k];