资源描述：
《第8章图像变换快速傅立叶变换ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图像的频域变换 ⑵1把图像信号从空域变换到频域，从频域来分析图像信号的特性。数字图像的频域处理主要应用：①利用某些频域变换可从图像中提取图像的特征；②利用图像频域处理可实现图像高效压缩编码；③减小计算维数，使算术运算次数大大减少，从而提高图像处理的速度。频域变换的理论基础是“任何波形都可以用单纯的正弦波的和来表示”。2离散傅立叶变换DFT3一维DFT和IDFTu=0,1,2,…,N-1x=0,1,2,…,N-14二维DFT和IDFT5二维离散傅立叶变换的性质67二维傅立叶变换特性:可分离性二维DFT可分离为两次一维DFTf(x
2、,y)F(x,v)F(u,v)按列进行一维DFT按行进行一维DFT8可分离性先对行做变换：然后对列进行变换：f(x,y)（0,0）（N-1，M-1）xyF(x,v)（0,0）（N-1，M-1）xvF(x,v)（0,0）（N-1，M-1）xvF(u,v)（0,0）（N-1，M-1）uv9可分离性先行后列先列后行10二维傅立叶变换特性:平移性将图像的频谱原点(0,0)移动到图像中心（M/2,N/2)处11二维傅立叶变换特性:平移性原图无平移的傅立叶频谱平移后的傅立叶频谱12二维傅立叶变换特性:旋转不变性在时域中离散函数旋转0角度
3、，则在变换域内离散傅立叶函数也将旋转同样的角度。13二维傅立叶变换特性:旋转不变性14快速傅立叶变换(FFT) FastFourierTransforming15有限长序列通过离散傅立叶变换(DFT)将其频域离散化成有限长序列.但其计算量太大(与N2成正比）,很难实时地处理问题,因此引出了快速傅立叶变换(FFT).FFT并不是一种新的变换形式,它只是DFT的一种快速算法.并且根据对序列分解与选取方法的不同而产生了FFT的多种算法.FFT在离散傅立叶反变换、线性卷积和线性相关等方面也有重要应用.16FFT产生故事当时Garwin
4、在自已的研究中极需要一个计算傅立叶变换的快速方法。他注意到Turkey正在写有关傅立叶变换的文章，因此详细询问了Turkey关于计算傅立叶变换的技术知识。Turkey概括地对Garwin介绍了一种方法，它实质上就是后来的著名的Cooley--Turkey算法。在Garwin的迫切要求下，Cooley很快设计出一个计算机程序。1965年Cooley--Turkey在MathematicofComputation上发表了著名的“机器计算傅立级数的一种算法”，提出一种快速计算DFT的方法和计算机程序--揭开了FFT发展史上的第一页，
5、促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成，电子数字计算机的条件，使DFT的运算大大简化了。17矩阵形式的一维DFT:W系数矩阵FFT的推导18系数W是以N为周期的，所以W阵中很多系数是相同的，不必进行多次重复计算，又由于W的对称性，可以进一步减少计算工作量。FFT的推导W4=W6=W9=W3=W2=W0W2W1W1-W0假设N＝4，u,x=0,1,2,319W阵的变换如下：FFT的推导20FFT的基本思想把一个N点的DFT分解成两个N/2短序列的DFT，即分解成偶数和奇数序列的DFTFe(u)和F
6、o(u)，并充分利用旋转因子W的周期性和对称性来计算DFT，简化运算过程。21对前M个DFT对后M个DFTFFT的推导22W5=-w1N=8,M=4,W=W8，u=0,1,2…7W7=-w3FFT的推导23F(1)F(5)Fe(1)Fo(5)W1－W1蝶形运算单元FFT的蝶形算法计算量?24f(2)f(1)f(5)f(3)f(7)f(0)f(4)f(6)F(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)W0W4W4W4W4W0W0W0F1(0)F1(1)F1(2)F1(3)F1(4)F1(5)F1(6)F1(7)
7、F2(0)F2(1)F2(2)F2(3)F2(4)F2(5)F2(6)F2(7)W0W2W4W6W0W2W4W6W0W1W2W3W4W5W6W78点的FFT的完整蝶形计算图和逐级分解图。奇偶分组，输入倒序第一级第二级第三级输出顺序FFT的蝶形算法25FFT的蝶形算法26FFT的蝶形算法27输入码位倒置，输出顺序自然顺序二进制表示码位倒置码位倒置顺序000000001001100420100102301111064100001151011013611001157111111728时间抽取FFT（将f(x)序列按x的奇偶进行分组计
8、算）对Ｎ＝２Ｍ点的信号，需Ｍ次递推，每次递推有Ｎ／２个蝶形，共有(Ｎ／2)M＝(Ｎ／2）log2Ｎ个蝶形，每个蝶形包括１次乘法和两次加法。总计算量(1/2)Nlog2N次乘法和Nlog2N次加法。对Ｎ点DFT总计算量为：Ｎ２次乘法和N(N-1)次加法。算法复杂性29FFT与D
