4个数一组4个数一组.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * FFT的算法步骤 1. 先将数据进行奇、偶分组。 例： 下标为2x 下标为2x+1 FFT算法步骤 分析偶数部分的数据项： 0000，0010，0100，0110，1000，1010，1100，1110 如果下标用二进制数表示为： 末尾一位是0。 FFT算法步骤 分析奇数部分的数据项： 0001，0011，0101，0111，1001，1011，1101，1111 如果下标用二进制数表示为： 末尾一位是1。 FFT算法步骤 二进制数为：0000，0010，0100，0110，1000，1010，1100，1110 第一层下标为： 0 2 4 6 8 10 12 14 2. 对偶数部分进行分层分组排序 因为奇数部分的数据项排列规律为2x+1，所以只需要给出偶数项部分，奇数项部分则可以类推。 FFT算法步骤 二进制数为：0000，0010，0100，0110，1000，1010，1100，1110 0 2 4 6 1 3 5 7 /2 *2 第一层下标分组为： 0， 4，8，12； 2，6，10，14 移位：000，001，010，011，100，101，110，111 偶数组：000，010，100，110 奇数组：001，011，101，111 FFT算法步骤 二进制数为： 0000， 0100， 1000， 1100 第二层下标为： 0 4 8 12 0 2 1 3 /4 *4 第二层下标分组为： 0， 8； 4，12； 移位：00，01，10，11 偶数组：00，10 奇数组：01，11 FFT算法步骤 3. 根据每层偶数组的排序方式，获得奇数组的排序方式。 因为偶数项的系数为f(2x)，奇数项的系数为f(2x+1)，所以由第二层偶数排序： 可以得到第一层偶数排序为： 0， 8， 4，12； 0，8，4，12，2， 6，10，14； FFT算法步骤 再根据第一层的偶数排序： 获得奇数项的排序为： 1，9，5，13，3， 7，11，15 0，8，4，12，2，6，10，14； 最后，获得原始数据的排序为： FFT算法步骤 4. 进行分层的奇、偶项相加。 对排好序的数据项，进行第一层计算有： 8个数一组 8个数一组 FFT算法步骤 对得到的偶数数据项，进行第二层计算有： 4个数一组 4个数一组 FFT算法步骤 对得到的奇数数据项，进行第二层计算有： 4个数一组 4个数一组 FFT算法步骤 对得到的偶数数据项，进行第三层计算有： 两个数一组 FFT算法步骤 对得到的奇数数据项，进行第三层计算有： 两个数一组 FFT算法步骤 最后，将获得的所有数据项进行合并： FFT算法图示 二维Fourier变换的应用 前面已经提到了Fourier变换有两个好处，即：可以获得信号的频域特性；可以将卷积运算转换为乘积运算。 因此二维Fourier变换的应用也是根据这两个特点来进行的。 二维Fourier变换的应用 ——用于图像滤波 首先，我们来看Fourier变换后的图像，中间部分为低频部分，越靠外边频率越高。 因此，我们可以在Fourier变换图中，选择所需要的高频或是低频滤波。 二维Fourier变换的应用 ——用于图像压缩 变换系数刚好表现的是各个频率点上的幅值。在小波变换没有提出时，用来进行压缩编码。 考虑到高频反映细节、低频反映景物概貌的特性。往往认为可将高频系数置为0，骗过人眼。 二维Fourier变换的应用 ——用于计算卷积 从前面的图像处理算法中知道，如果抽象来看，其实都可以认为是图像信息经过了滤波器的滤波（如：平滑滤波、锐化滤波等 ）。 如果滤波器的结构比较复杂时，直接进行时域中的卷积运算是不可思议的。 Fourier变换可以卷积运算转换为点乘运算，由此简化运算，提高计算速度。 离散余弦变换（DCT）