第五章图象正交变换.ppt

第五章图象正交变换
第一页，本课件共有129页
什么是图象变换
将图象看成是线性叠加系统
图象在空域上相关性很强
图象变换是将图象从空域变换到其它域如频域的数学变换
常用的变换：傅立叶变换、离散余弦变换、沃尔什变换、离散K-L 快速傅立叶变换（FFT）
第二十四页，本课件共有129页
傅立叶变换
时间抽取基2 FFT算法
对于u>N/2-1的点，有以下规则给出：
N=8
4点
DFT
4点
DFT
第二十五页，本课件共有129页
傅立叶变换
时间抽取基2 FFT算法
蝶形运算(u=0,1,…,N/2-1)
第二十六页，本课件共有129页
傅立叶变换
时间抽取基2 FFT算法
用两个2点DFT代替4点DFT：
第二十七页，本课件共有129页
傅立叶变换
时间抽取基2 FFT算法
2点
DFT
2点
DFT
2点
DFT
2点
DFT
输入倒序排列
第二十八页，本课件共有129页
傅立叶变换
时间抽取基2 FFT算法
输入倒序排列
第二十九页，本课件共有129页
傅立叶变换
标号
二进制表示
按位倒序的二进制表示
倒序后标号
0
1
2
3
4
5
6
7
000
001
010
011
100
101
110
111
000
100
010
110
001
101
011
111
0
4
2
6
1
5
3
7
时间抽取基2 FFT算法
第三十页，本课件共有129页
傅立叶变换

利用FFT蝶形流程图算法在计算机上实现快速付里叶变换必须解决如下问题：迭代次数r的确定、对偶节点的计算、加权系数 的计算、重新排序问题。
(1)迭代次数r的确定
由蝶形流程图可见，迭代次数与N有关。r值可由下式确定：
式中N是变换序列的长度，对于基2的蝶形程图，N是2的整数次幂。例如，序列长度为8则要三次迭代，序列长度为16时就要4次迭代。
第三十一页，本课件共有129页
傅立叶变换

(2)对偶节点的计算
在流程图中把标有xi(k)的点称为节点。其中下标i为列数，也就是第几次迭代，例如，x1(k)则说明它是第一次迭代的结果。k代表流程图中的行数，也就是序列的序号数。其中每节点的值均是用前一 节点对计算得来的。例如，x1(0)和x1(4)均是x(0)和x(4)计算得来的。在蝶形流程图中，把具有相同来源的一对节点叫做对偶节点。如： x1(0)和x1(4)就是一对对偶节点，因为它们均来源于x(0)和x(4) 。对偶节点的计算也就是求出在每次迭代小对偶节点的间隔。由流程图可见，第一次迭代的间距为计N／2，第二次迭代的节距为N／4，第三次迭代的节距为人N／23等等。由以上分析可得到对偶节点的计算方法。如果某一节点为xi(k)，那么它的对偶节点为
第三十二页，本课件共有129页
傅立叶变换

(3)加权系数 的计算
的计算主要是确定p值。p值可用下述方法求得：
把k值写成r位的二进制数(k序列的序号数，r是迭代次数)；
把这个二进制数右移r-1位，并把左边的空位补零(结果仍为r位)
把这个右移后的二进制数倒序
把倒序后的二进制数转换维十进制数就得到p值。
第三十三页，本课件共有129页
傅立叶变换

(4)重新排序
由蝶形流程图可见，如果序列x(n)是按顺序排列的，经过蝶式运算后，其变换序列是倒序排列的；反之，如果x(n)是倒序排列的，那么输出就是顺序排列的。因此，为了便于输出
使用，最好加入倒序程序以保证x(n)与它的变换系数X(m)的对应关系。
第三十四页，本课件共有129页
傅立叶变换
5. 如何提高FFT的速度？
（1）减少乘法次数；（2）基4、基8算法；（3）实数FFT；
（4）硬件实现（DSP芯片，FFT集成块）
第三十五页，本课件共有129页
傅立叶变换
6. FFT举例
w2
w1
w3
-1
-1
-1
-1
F（u）
-1
-1
-1
-1
w2
w2
-1
-1
-1
-1
1
0
0
1