第8章图像变换快速傅立叶变换课件.ppt

1、1图像的频域变换图像的频域变换2 把图像信号从空域变换到频域，从频域来分析图把图像信号从空域变换到频域，从频域来分析图像信号的特性。像信号的特性。数字图像的频域处理主要应用：数字图像的频域处理主要应用：利用某些频域变换可从图像中提取图像的特征；利用某些频域变换可从图像中提取图像的特征；利用图像频域处理可实现图像高效压缩编码；利用图像频域处理可实现图像高效压缩编码；减小计算维数，使算术运算次数大大减少，从减小计算维数，使算术运算次数大大减少，从而提高图像处理的速度。而提高图像处理的速度。频域变换的理论基础是频域变换的理论基础是“任何波形都可以用单纯任何波形都可以用单纯的正弦波的和来表示的正弦波的

2、和来表示”。34一维一维DFTDFT和和IDFTIDFT 1021021NuuNxjNxxNuje)u(FNxfexfuFNjNeWLet2u=0,1,2,N-1x=0,1,2,N-1 10101NuuxNNxuxNW)u(FNWxf5二维二维DFTDFT和和IDFTIDFT1210121011010210102N,.,y,vM,.,x,ue)v,u(FMN)y,x(fe)y,x(f)v,u(FMuNn)NvyMux(jNxNy)NvyMux(j6二维离散傅立叶变换的性质二维离散傅立叶变换的性质 78二维傅立叶变换特性二维傅立叶变换特性:可分离性可分离性 二维二维DFT可分离为两次一维可分离为

3、两次一维DFTf(x,y)F(x,v)F(u,v)按列进行按列进行一维一维DFT按行进行按行进行一维一维DFT9可分离性可分离性 先对行做变换：先对行做变换：然后对列进行变换然后对列进行变换：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）uv10)y,x(fFFee)y,x(f)y,x(fFFee)y,x(fe)y,x(f)v,u(FxyNvyjNyNxMuxjyxMuxjNxNyNvyjNxNy)NvyMux(j 21010221010210102可分离性可分离性先行

4、后列先行后列先列后行先列后行11二维傅立叶变换特性二维傅立叶变换特性:平移性平移性)Nv,Mu(F)(y,x(fNvandMuif)vv,uu(Fe)y,x(fe)v,u(F)yy,xx(f)v,u(F)y,x(fyx)NyvMxu(j)NyvMxu(j22122000022000000将图像的频谱原点将图像的频谱原点(0,0)移动到图像中心（移动到图像中心（M/2,N/2)处处12二维傅立叶变换特性二维傅立叶变换特性:平移性平移性原图原图无平移的傅立叶频谱无平移的傅立叶频谱平移后的傅立叶频谱平移后的傅立叶频谱13二维傅立叶变换特性二维傅立叶变换特性:旋转不变性旋转不变性 在时域中离散函数旋转

5、在时域中离散函数旋转 0角度，则在变换域内角度，则在变换域内离散傅立叶函数也将旋转同样的角度。离散傅立叶函数也将旋转同样的角度。),(F),r(f),(F),r(f0014二维傅立叶变换特性二维傅立叶变换特性:旋转不变性旋转不变性15快速傅立叶变换快速傅立叶变换(FFT)Fast Fourier Transforming16 有限长序列通过离散傅立叶变换有限长序列通过离散傅立叶变换(DFT)将其频域离散将其频域离散化成有限长序列化成有限长序列.但其计算量太大但其计算量太大(与与N2成正比）成正比）,很难很难实时地处理问题实时地处理问题,因此引出了快速傅立叶变换因此引出了快速傅立叶变换(FFT)

6、.FFT并不是一种新的变换形式并不是一种新的变换形式,它只是它只是DFT的一种快速的一种快速算法算法.并且根据对序列分解与选取方法的不同而产生并且根据对序列分解与选取方法的不同而产生了了FFT的多种算法的多种算法.FFT在离散傅立叶反变换、线性卷积和线性相关等方在离散傅立叶反变换、线性卷积和线性相关等方面也有重要应用面也有重要应用.17FFT产生故事产生故事当时当时Garwin在自已的研究中极需要一个计算傅立在自已的研究中极需要一个计算傅立叶变换的快速方法。他注意到叶变换的快速方法。他注意到Turkey正在写有关傅立正在写有关傅立叶变换的文章，因此详细询问了叶变换的文章，因此详细询问了Turk

7、ey关于计算傅立关于计算傅立叶变换的技术知识。叶变换的技术知识。Turkey概括地对概括地对Garwin介绍了一介绍了一种方法，它实质上就是后来的著名的种方法，它实质上就是后来的著名的Cooley-Turkey算法。在算法。在Garwin的迫切要求下，的迫切要求下，Cooley很快设计出一很快设计出一个计算机程序。个计算机程序。1965年年Cooley-Turkey在在Mathematic of Computation上发表了著名的上发表了著名的“机器机器计算傅立级数的一种算法计算傅立级数的一种算法”，提出一种快速计算，提出一种快速计算DFT的方法和计算机程序的方法和计算机程序-揭开了揭开了F

8、FT发展史上的第一页，发展史上的第一页，促使促使FFT算法产生原因还有算法产生原因还有1967年至年至1968年间年间FFT的的数字硬件制成，电子数字计算机的条件，使数字硬件制成，电子数字计算机的条件，使DFT的运算的运算大大简化了。大大简化了。18 110110111110111110010100NfffWWWWWWWWWNFFFN)N()N()N(NN N/jNxuxNxxNujeWWxfexfuF210102旋转因子矩阵形式的一维矩阵形式的一维DFT:W系数矩阵系数矩阵FFT的推导的推导19xuNxuNxuNNjNxuNxuNNjNWWWWeWWWeW22222211系数系数W是以是以N

9、为周期的，所以为周期的，所以W阵中很多系数是相同的，阵中很多系数是相同的，不必进行多次重复计算，又由于不必进行多次重复计算，又由于W的对称性，可以进一步的对称性，可以进一步减少计算工作量。减少计算工作量。FFT的推导的推导W4=W6=W9=W3=W2=W0W2W1-W1-W0假设假设N4，u,x=0,1,2,320W阵的变换如下：阵的变换如下：FFT的推导的推导1010000010100000WWWWWWWWWWWWWWWW9630642032100000WWWWWWWWWWWWWWWW21FFT的基本思想的基本思想把一个把一个N点的点的DFT分解成两个分解成两个N/2短序列的短序列的DFT，

10、即，即分解成偶数和奇数序列的分解成偶数和奇数序列的DFT Fe(u)和和Fo(u)，并充，并充分利用旋转因子分利用旋转因子W的周期性和对称性来计算的周期性和对称性来计算DFT，简化运算过程。简化运算过程。10101201212021221222MxuxMuNMxuxMNx)x(uNNx)x(uNWxfWWxfWxfW)x(fuFMNuxMuNNxujNujNuxj)x(uNj)x(uNuxMMuxiNuxj)x(uNjWWeee)e(WWee)e(222221221222222u(2x)NW22 )WW,WW(uFWuF)Mu(FuFWuFuFWxfuFWxfuFuMMuMuMMuMouMeo

11、uMeMxuxMoMxuxMe22221010122对前对前M个个DFT对后对后M个个DFTFFT的推导的推导23uMxjuMMxMjMujMuMjMuMWeWeeeW222222222)(uMxjuMMxMjMujMuMjMuMWeWeeeW2222)(W5=-w1N=8,M=4,W=W8，u=0,1,27W7=-w3FFT的推导的推导24F(1)F(5)Fe(1)Fo(5)W1W1)(FW)(F)(F)(FW)(FFoeoe51551111蝶形运算单元蝶形运算单元FFT的蝶形算法的蝶形算法计算量计算量?25f(2)f(1)f(5)f(3)f(7)f(0)f(4)f(6)F(0)F(1)F(

12、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)F2(0)F2(1)F2(2)F2(3)F2(4)F2(5)F2(6)F2(7)W0W2W4W6W0W2W4W6W0W1W2W3W4W5W6W78点的点的FFT的完整蝶形计算图和逐级分解图。的完整蝶形计算图和逐级分解图。37261504WW,WW,WW,WW奇奇偶偶分分组，组，输输入入倒倒序序第一级第一级第二级第二级第三级第三级输输出出顺顺序序FFT的蝶形算法的蝶形算法26)()()()()()()()()()()()()()()()()(

13、)()()()()(7531624073518240642040000000001010101202fffffffffWfWfWfWFWfWfWfFWFWFWFFWFFFFT的蝶形算法的蝶形算法27)()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(7531624075316240735162406420404400040001014101242ffffffffffffWfffffWfWfWfWfWfWfWfFWFWFWFFWFFFFT的蝶形算法的蝶形算法28输入码位倒置，输出顺序输入码位倒置，输出顺序自然顺序自然顺序二进制表

14、示二进制表示码位倒置码位倒置码位倒置顺序码位倒置顺序000000001001100420100102301111064100001151011013611001157111111729时间抽取时间抽取FFTFFT（将（将f(x)f(x)序列按序列按x x的奇偶进行分组计算）的奇偶进行分组计算）对对点的信号，需次递推，每次递推有点的信号，需次递推，每次递推有个蝶形，共有个蝶形，共有(2)M2)M(2 2）loglog2 2个蝶个蝶形，每个蝶形包括次乘法和两次加法。总计算量形，每个蝶形包括次乘法和两次加法。总计算量(1/2)Nlog(1/2)Nlog2 2N N次次乘法和乘法和NlogNlog2

15、2N N次次加法。加法。对点对点DFTDFT总计算量为：总计算量为：次乘法和次乘法和N(N-1)N(N-1)次加法。次加法。算法复杂性算法复杂性30FFT与DFT的比较NN(DFT)log2N(FFT)N/(log2N)2422.0864242.71024104857610240102.440961677721649152341.331 FourierFourier变换变换高频反映细节、低频反映景物概貌的特性高频反映细节、低频反映景物概貌的特性 高频滤波高频滤波 低频滤波低频滤波 图像压缩图像压缩，将高频系数置为将高频系数置为0 0 将卷积运算转换为点乘运算，由此简化运算，提高将卷积运算转换为

16、点乘运算，由此简化运算，提高计算速度。计算速度。二维二维FourierFourier变换的应用变换的应用32 )(SG),(jif),(jifgfgfg),(),(),(FGFg)(1ggFFFTf33离散余弦变换离散余弦变换DCT34 FourierFourier变换的一个最大的问题是：它的参变换的一个最大的问题是：它的参数都是复数，在数据的描述上相当于实数的数都是复数，在数据的描述上相当于实数的两倍。两倍。为此，我们希望有一种能够达到相同功能但为此，我们希望有一种能够达到相同功能但数据量又不大的变换。在此期望下，产生了数据量又不大的变换。在此期望下，产生了DCTDCT变换。变换。问题的提出

17、问题的提出35离散余弦变换（离散余弦变换（Discrete Cosine TransformDiscrete Cosine Transform）的）的变换核为余弦函数。变换核为余弦函数。DCTDCT除了具有一般的正交变换除了具有一般的正交变换性质外，性质外，它的变换阵的基向量能很好地描述人类它的变换阵的基向量能很好地描述人类语音信号和图像信号的相关特征。因此，在对语音语音信号和图像信号的相关特征。因此，在对语音信号、图像信号的变换中，信号、图像信号的变换中，DCTDCT变换被认为是一种变换被认为是一种准最佳变换。近年颁布的一系列视频压缩编码的国准最佳变换。近年颁布的一系列视频压缩编码的国际标准

18、建议中，都把际标准建议中，都把DCTDCT作为其中的一个基本处理作为其中的一个基本处理模块。除此之外，模块。除此之外，DCTDCT还是一种可分离的变换。还是一种可分离的变换。36 把一幅图像划分成一系列的图像块，每个图像块把一幅图像划分成一系列的图像块，每个图像块包含包含88个像素。如果原始图像有个像素。如果原始图像有640480个个像素，则图片将包含像素，则图片将包含80列列60行的方块。如果图像行的方块。如果图像只包含灰度，那么每个像素用一个只包含灰度，那么每个像素用一个8比特的数字比特的数字表示。因此可以把每个图像块表示成一个表示。因此可以把每个图像块表示成一个8行行8列列的二维数组。数

19、组的元素是的二维数组。数组的元素是0255的的8比特整数。比特整数。离散余弦变换就是作用在这个数组上。离散余弦变换就是作用在这个数组上。37 如果图像是彩色的，那么每个像素可以用如果图像是彩色的，那么每个像素可以用24比特、比特、相当于三个相当于三个8位比特的组合来表示（用位比特的组合来表示（用RGB或或YIQ表示，在这里没有影响）。因此，可以用三个表示，在这里没有影响）。因此，可以用三个8行行8列的二维数组表示这个列的二维数组表示这个88的像素方块。每一个数的像素方块。每一个数组表示其中一个八位比特组合的像素值。离散余弦组表示其中一个八位比特组合的像素值。离散余弦变换作用于每个数组。变换作用

20、于每个数组。38 简单的说，是用一个简单的说，是用一个8行行8列的二维数组产生另一个同样列的二维数组产生另一个同样包含包含8行行8列二维数组的函数，也就是说，把一个数组通列二维数组的函数，也就是说，把一个数组通过一个变换，变成另一个数组。过一个变换，变成另一个数组。如图下图所示，对每个图像块做离散余弦变换。通过如图下图所示，对每个图像块做离散余弦变换。通过DCTDCT变换可以把能量集中在矩阵左上角少数几个系数上。变换可以把能量集中在矩阵左上角少数几个系数上。f(i,j)经DCT变换之后得到F(u,v)，其中F(0,0)是直流系数，称为DC系数，其他为交流系数，称为AC系数。39离散余弦变换的数

21、组离散余弦变换的数组f(i,j)经DCT变换之后得到F(u,v)，其中F(0,0)是直流系数，称为DC系数，其他为交流系数，称为AC系数。40离散余弦变换（离散余弦变换（DCTDCT）逆变换：10102221212MxNyNMMN)y(cosu)x(cos)(C)u(C)y,x(f),u(F10102221212MuNNMMN)y(cosu)x(cos),u(F)(C)u(C)y,x(f1)(21xc0 x1,.,2,1Nx设设f(x,y)为为MN的数字图像矩阵的数字图像矩阵正变换：41)y(cosu)x(cos)(C)u(CMNNM1212222DCT变换的基函数变换的基函数(变换核变换核)

22、424344余弦变换实际上是利用了余弦变换实际上是利用了FourierFourier变换的实数变换的实数部分构成的变换。部分构成的变换。余弦变换主要用于图像的压缩，如目前的余弦变换主要用于图像的压缩，如目前的国际压缩标准的国际压缩标准的JPEGJPEG格式中就用到了格式中就用到了DCTDCT变变换。换。具体的做法与具体的做法与DFTDFT相似。即高频部分压缩多相似。即高频部分压缩多一些，低频部分压缩少一些。一些，低频部分压缩少一些。DCTDCT的应用的应用45作 业（共1题）1.1.已知图像为已知图像为8070605040302010f求求2 2维维FFTFFT变换变换 F(u,v)F(u,v)46Fourier变换的频率特性 中间部分为低频部分，中间部分为低频部分，越靠外边频率越高越靠外边频率越高47Fourier变换的低通滤波48Fourier变换的高通滤波49基于Fourier变换的压缩另一幅图像效果另一幅图像效果压缩率为：1.7：1压缩率为：2.24：1压缩率为：3.3：150基于Fourier变换的压缩压缩率为：8.1：1压缩率为：10.77：1压缩率为：16.1：151