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

图像的频域变换

⑵1图像的频域变换

⑵1把图像信号从空域变换到频域，从频域来分析图像信号的特性。数字图像的频域处理主要应用：①利用某些频域变换可从图像中提取图像的特征；②利用图像频域处理可实现图像高效压缩编码；③减小计算维数，使算术运算次数大大减少，从而提高图像处理的速度。频域变换的理论基础是“任何波形都可以用单纯的正弦波的和来表示”。2把图像信号从空域变换到频域，从频域来分析图像信号的特性。2离散傅立叶变换DFT3离散傅立叶变换DFT3一维DFT和IDFTu=0,1,2,…,N-1x=0,1,2,…,N-14一维DFT和IDFTu=0,1,2,…,N-14二维DFT和IDFT5二维DFT和IDFT5二维离散傅立叶变换的性质6二维离散傅立叶变换的性质677二维傅立叶变换特性:可分离性二维DFT可分离为两次一维DFTf(x,y)F(x,v)F(u,v)按列进行一维DFT按行进行一维DFT8二维傅立叶变换特性:可分离性二维DFT可分离为两次一维DFT可分离性先对行做变换：然后对列进行变换：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可分离性先对行做变换：然后对列进行变换：f(x,y)（0,0可分离性先行后列先列后行10可分离性先行后列先列后行10二维傅立叶变换特性:平移性将图像的频谱原点(0,0)移动到图像中心（M/2,N/2)处11二维傅立叶变换特性:平移性将图像的频谱原点(0,0)移动到图二维傅立叶变换特性:平移性原图无平移的傅立叶频谱平移后的傅立叶频谱12二维傅立叶变换特性:平移性原图无平移的傅立叶频谱平移后的傅立二维傅立叶变换特性:旋转不变性在时域中离散函数旋转0角度，则在变换域内离散傅立叶函数也将旋转同样的角度。13二维傅立叶变换特性:旋转不变性在时域中离散函数旋转0角度，二维傅立叶变换特性:旋转不变性14二维傅立叶变换特性:旋转不变性14快速傅立叶变换(FFT)

FastFourierTransforming15快速傅立叶变换(FFT)

FastFourierTran有限长序列通过离散傅立叶变换(DFT)将其频域离散化成有限长序列.但其计算量太大(与N2成正比）,很难实时地处理问题,因此引出了快速傅立叶变换(FFT).FFT并不是一种新的变换形式,它只是DFT的一种快速算法.并且根据对序列分解与选取方法的不同而产生了FFT的多种算法.FFT在离散傅立叶反变换、线性卷积和线性相关等方面也有重要应用.16有限长序列通过离散傅立叶变换(DFT)将其频域离散化成有限长FFT产生故事 当时Garwin在自已的研究中极需要一个计算傅立叶变换的快速方法。他注意到Turkey正在写有关傅立叶变换的文章，因此详细询问了Turkey关于计算傅立叶变换的技术知识。Turkey概括地对Garwin介绍了一种方法，它实质上就是后来的著名的Cooley--Turkey算法。在Garwin的迫切要求下，Cooley很快设计出一个计算机程序。1965年Cooley--Turkey在MathematicofComputation上发表了著名的“机器计算傅立级数的一种算法”，提出一种快速计算DFT的方法和计算机程序--揭开了FFT发展史上的第一页，促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成，电子数字计算机的条件，使DFT的运算大大简化了。1717矩阵形式的一维DFT:W系数矩阵FFT的推导18矩阵形式的一维DFT:W系数矩阵FFT的推导18系数W是以N为周期的，所以W阵中很多系数是相同的，不必进行多次重复计算，又由于W的对称性，可以进一步减少计算工作量。FFT的推导W4=W6=W9=

W3=W2=W0W2W1

W1-W0假设N＝4，u,x=0,1,2,319系数W是以N为周期的，所以W阵中很多系数是相同的，不必进行多W阵的变换如下：FFT的推导20W阵的变换如下：FFT的推导20FFT的基本思想把一个N点的DFT分解成两个N/2短序列的DFT，即分解成偶数和奇数序列的DFTFe(u)和Fo(u)，并充分利用旋转因子W的周期性和对称性来计算DFT，简化运算过程。21FFT的基本思想把一个N点的DFT分解成两个N/2短序列的D对前M个DFT对后M个DFTFFT的推导22对前M个DFT对后M个DFTFFT的推导22W5=-w1N=8,M=4,W=W8，u=0,1,2…7W7=-w3FFT的推导23W5=-w1N=8,M=4,W=W8，u=0,1,F(1)F(5)Fe(1)Fo(5)W1－W1蝶形运算单元FFT的蝶形算法计算量?24F(1)F(5)Fe(1)Fo(5)W1－W1蝶形运算单元Ff(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)F2(0)F2(1)F2(2)F2(3)F2(4)F2(5)F2(6)F2(7)W0W2W4W6W0W2W4W6W0W1W2W3W4W5W6W78点的FFT的完整蝶形计算图和逐级分解图。奇偶分组，输入倒序第一级第二级第三级输出顺序FFT的蝶形算法25f(2)f(1)f(5)f(3)f(7)f(0)f(4)f(FFT的蝶形算法26FFT的蝶形算法26FFT的蝶形算法27FFT的蝶形算法27输入码位倒置，输出顺序自然顺序二进制表示码位倒置码位倒置顺序000000001001100420100102301111064100001151011013611001157111111728输入码位倒置，输出顺序自然顺序二进制表示码位倒置码位倒置顺序时间抽取FFT（将f(x)序列按x的奇偶进行分组计算）对Ｎ＝２Ｍ点的信号，需Ｍ次递推，每次递推有Ｎ／２个蝶形，共有(Ｎ／2)M＝(Ｎ／2）log2Ｎ个蝶形，每个蝶形包括１次乘法和两次加法。总计算量(1/2)Nlog2N次乘法和Nlog2N次加法。对Ｎ点DFT总计算量为：Ｎ２次乘法和N(N-1)次加法。算法复杂性29时间抽取FFT（将f(x)序列按x的奇偶进行分组计算）算法复FFT与DFT的比较NN２(DFT)Ｎlog2N(FFT)N２/(Ｎlog2N)2422.0864242.71024104857610240102.440961677721649152341.330FFT与DFT的比较NN２Ｎlog2NN２/(Ｎlog2N)Fourier变换高频反映细节、低频反映景物概貌的特性高频滤波低频滤波图像压缩，将高频系数置为0将卷积运算转换为点乘运算，由此简化运算，提高计算速度。二维Fourier变换的应用31Fourier变换二维Fourier变换的应用31

3232离散余弦变换

DCT33离散余弦变换

DCT33Fourier变换的一个最大的问题是：它的参数都是复数，在数据的描述上相当于实数的两倍。为此，我们希望有一种能够达到相同功能但数据量又不大的变换。在此期望下，产生了DCT变换。问题的提出34问题的提出34离散余弦变换（DiscreteCosineTransform）的变换核为余弦函数。DCT除了具有一般的正交变换性质外，它的变换阵的基向量能很好地描述人类语音信号和图像信号的相关特征。因此，在对语音信号、图像信号的变换中，DCT变换被认为是一种准最佳变换。近年颁布的一系列视频压缩编码的国际标准建议中，都把DCT作为其中的一个基本处理模块。除此之外，DCT还是一种可分离的变换。35离散余弦变换（DiscreteCosineTransfo把一幅图像划分成一系列的图像块，每个图像块包含8×8个像素。如果原始图像有640×480个像素，则图片将包含80列60行的方块。如果图像只包含灰度，那么每个像素用一个8比特的数字表示。因此可以把每个图像块表示成一个8行8列的二维数组。数组的元素是0～255的8比特整数。离散余弦变换就是作用在这个数组上。

36把一幅图像划分成一系列的图像块，每个图像块包含8×8个像素。如果图像是彩色的，那么每个像素可以用24比特、相当于三个8位比特的组合来表示（用RGB或YIQ表示，在这里没有影响）。因此，可以用三个8行8列的二维数组表示这个8×8的像素方块。每一个数组表示其中一个八位比特组合的像素值。离散余弦变换作用于每个数组。

37如果图像是彩色的，那么每个像素可以用24比特、相当于三个8位简单的说，是用一个8行8列的二维数组产生另一个同样包含8行8列二维数组的函数，也就是说，把一个数组通过一个变换，变成另一个数组。如图下图所示，对每个图像块做离散余弦变换。通过DCT变换可以把能量集中在矩阵左上角少数几个系数上。

f(i,j)经DCT变换之后得到F(u,v)，其中F(0,0)是直流系数，称为DC系数，其他为交流系数，称为AC系数。38简单的说，是用一个8行8列的二维数组产生另一个同样包含8行8离散余弦变换的数组f(i,j)经DCT变换之后得到F(u,v)，其中F(0,0)是直流系数，称为DC系数，其他为交流系数，称为AC系数。39f(i,j)经DCT变换之后得到F(u,v)，其中F(0,0离散余弦变换（DCT）逆变换：设f(x,y)为M×N的数字图像矩阵正变换：40离散余弦变换（DCT）逆变换：设f(x,y)为M×N的数字图DCT变换的基函数(变换核)41DCT变换的基函数(变换核)4142424343余弦变换实际上是利用了Fourier变换的实数部分构成的变换。余弦变换主要用于图像的压缩，如目前的国际压缩标准的JPEG格式中就用到了DCT变换。具体的做法与DFT相似。即高频部分压缩多一些，低频部分压缩少一些。DCT的应用44余弦变换实际上是利用了Fourier变换的实数部分构成的变换作业（共1题）1.已知图像为求2维FFT变换F(u,v)45作业（共1题）1.已知图像为求2维FFT变换F(u,vFourier变换的频率特性中间部分为低频部分，越靠外边频率越高46Fourier变换的频率特性中间部分为低频部分，46Fourier变换的低通滤波47Fourier变换的低通滤波47Fourier变换的高通滤波48Fourier变换的高通滤波48基于Fourier变换的压缩另一幅图像效果压缩率为：1.7：1压缩率为：2.24：1压缩率为：3.3：149基于Fourier变换的压缩另一幅图像效果压缩率为：1.7：基于Fourier变换的压缩压缩率为：8.1：1压缩率为：10.77：1压缩率为：16.1：150基于Fourier变换的压缩压缩率为：8.1：1压缩率为：15151图像的频域变换

⑵52图像的频域变换

⑵1把图像信号从空域变换到频域，从频域来分析图像信号的特性。数字图像的频域处理主要应用：①利用某些频域变换可从图像中提取图像的特征；②利用图像频域处理可实现图像高效压缩编码；③减小计算维数，使算术运算次数大大减少，从而提高图像处理的速度。频域变换的理论基础是“任何波形都可以用单纯的正弦波的和来表示”。53把图像信号从空域变换到频域，从频域来分析图像信号的特性。2离散傅立叶变换DFT54离散傅立叶变换DFT3一维DFT和IDFTu=0,1,2,…,N-1x=0,1,2,…,N-155一维DFT和IDFTu=0,1,2,…,N-14二维DFT和IDFT56二维DFT和IDFT5二维离散傅立叶变换的性质57二维离散傅立叶变换的性质6587二维傅立叶变换特性:可分离性二维DFT可分离为两次一维DFTf(x,y)F(x,v)F(u,v)按列进行一维DFT按行进行一维DFT59二维傅立叶变换特性:可分离性二维DFT可分离为两次一维DFT可分离性先对行做变换：然后对列进行变换：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）uv60可分离性先对行做变换：然后对列进行变换：f(x,y)（0,0可分离性先行后列先列后行61可分离性先行后列先列后行10二维傅立叶变换特性:平移性将图像的频谱原点(0,0)移动到图像中心（M/2,N/2)处62二维傅立叶变换特性:平移性将图像的频谱原点(0,0)移动到图二维傅立叶变换特性:平移性原图无平移的傅立叶频谱平移后的傅立叶频谱63二维傅立叶变换特性:平移性原图无平移的傅立叶频谱平移后的傅立二维傅立叶变换特性:旋转不变性在时域中离散函数旋转0角度，则在变换域内离散傅立叶函数也将旋转同样的角度。64二维傅立叶变换特性:旋转不变性在时域中离散函数旋转0角度，二维傅立叶变换特性:旋转不变性65二维傅立叶变换特性:旋转不变性14快速傅立叶变换(FFT)

FastFourierTransforming66快速傅立叶变换(FFT)

FastFourierTran有限长序列通过离散傅立叶变换(DFT)将其频域离散化成有限长序列.但其计算量太大(与N2成正比）,很难实时地处理问题,因此引出了快速傅立叶变换(FFT).FFT并不是一种新的变换形式,它只是DFT的一种快速算法.并且根据对序列分解与选取方法的不同而产生了FFT的多种算法.FFT在离散傅立叶反变换、线性卷积和线性相关等方面也有重要应用.67有限长序列通过离散傅立叶变换(DFT)将其频域离散化成有限长FFT产生故事 当时Garwin在自已的研究中极需要一个计算傅立叶变换的快速方法。他注意到Turkey正在写有关傅立叶变换的文章，因此详细询问了Turkey关于计算傅立叶变换的技术知识。Turkey概括地对Garwin介绍了一种方法，它实质上就是后来的著名的Cooley--Turkey算法。在Garwin的迫切要求下，Cooley很快设计出一个计算机程序。1965年Cooley--Turkey在MathematicofComputation上发表了著名的“机器计算傅立级数的一种算法”，提出一种快速计算DFT的方法和计算机程序--揭开了FFT发展史上的第一页，促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成，电子数字计算机的条件，使DFT的运算大大简化了。6817矩阵形式的一维DFT:W系数矩阵FFT的推导69矩阵形式的一维DFT:W系数矩阵FFT的推导18系数W是以N为周期的，所以W阵中很多系数是相同的，不必进行多次重复计算，又由于W的对称性，可以进一步减少计算工作量。FFT的推导W4=W6=W9=

W3=W2=W0W2W1

W1-W0假设N＝4，u,x=0,1,2,370系数W是以N为周期的，所以W阵中很多系数是相同的，不必进行多W阵的变换如下：FFT的推导71W阵的变换如下：FFT的推导20FFT的基本思想把一个N点的DFT分解成两个N/2短序列的DFT，即分解成偶数和奇数序列的DFTFe(u)和Fo(u)，并充分利用旋转因子W的周期性和对称性来计算DFT，简化运算过程。72FFT的基本思想把一个N点的DFT分解成两个N/2短序列的D对前M个DFT对后M个DFTFFT的推导73对前M个DFT对后M个DFTFFT的推导22W5=-w1N=8,M=4,W=W8，u=0,1,2…7W7=-w3FFT的推导74W5=-w1N=8,M=4,W=W8，u=0,1,F(1)F(5)Fe(1)Fo(5)W1－W1蝶形运算单元FFT的蝶形算法计算量?75F(1)F(5)Fe(1)Fo(5)W1－W1蝶形运算单元Ff(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)F2(0)F2(1)F2(2)F2(3)F2(4)F2(5)F2(6)F2(7)W0W2W4W6W0W2W4W6W0W1W2W3W4W5W6W78点的FFT的完整蝶形计算图和逐级分解图。奇偶分组，输入倒序第一级第二级第三级输出顺序FFT的蝶形算法76f(2)f(1)f(5)f(3)f(7)f(0)f(4)f(FFT的蝶形算法77FFT的蝶形算法26FFT的蝶形算法78FFT的蝶形算法27输入码位倒置，输出顺序自然顺序二进制表示码位倒置码位倒置顺序000000001001100420100102301111064100001151011013611001157111111779输入码位倒置，输出顺序自然顺序二进制表示码位倒置码位倒置顺序时间抽取FFT（将f(x)序列按x的奇偶进行分组计算）对Ｎ＝２Ｍ点的信号，需Ｍ次递推，每次递推有Ｎ／２个蝶形，共有(Ｎ／2)M＝(Ｎ／2）log2Ｎ个蝶形，每个蝶形包括１次乘法和两次加法。总计算量(1/2)Nlog2N次乘法和Nlog2N次加法。对Ｎ点DFT总计算量为：Ｎ２次乘法和N(N-1)次加法。算法复杂性80时间抽取FFT（将f(x)序列按x的奇偶进行分组计算）算法复FFT与DFT的比较NN２(DFT)Ｎlog2N(FFT)N２/(Ｎlog2N)2422.0864242.71024104857610240102.440961677721649152341.381FFT与DFT的比较NN２Ｎlog2NN２/(Ｎlog2N)Fourier变换高频反映细节、低频反映景物概貌的特性高频滤波低频滤波图像压缩，将高频系数置为0将卷积运算转换为点乘运算，由此简化运算，提高计算速度。二维Fourier变换的应用82Fourier变换二维Fourier变换的应用31

8332离散余弦变换

DCT84离散余弦变换

DCT33Fourier变换的一个最大的问题是：它的参数都是复数，在数据的描述上相当于实数的两倍。为此，我们希望有一种能够达到相同功能但数据量又不大的变换。在此期望下，产生了DCT变换。问题的提出85问题的提出34离散余弦变换（DiscreteCosineTransform）的变换核为余弦函数。DCT除了具有一般的正交变换性质外，它的变换阵的基向量能很好地描述人类语音信号和图像信号的相关特征。因此，在对语音信号、图像信号的变换中，DCT变换被认为是一种准最佳变换。近年颁布的一系列视频压缩编码的国际标准建议中，都把DCT作为其中的一个基本处理模块。除此之外，DCT还是一种可分离的变换。86离散余弦变换（DiscreteCosineTransfo把一幅图像划分成一系列的图像块，每个图像块包含8×8个像素。如果原始图像有640×480个像素，则图片将包含80列60行的方块。如果图像只包含灰度，那么每个像素用一个8比特的数字表示。因此可以把每个图像块表示成一个8行8列的二维数组。数组的元素是0～255的8比特整数。离散余弦变换就是作用在这个数组上。

87把一幅图像划分成一系列的图像块，每个图像块包含8×8个像素。如果图像是彩色的，那么每个像素可以用24比特、相当于三个8位比特的组合来表示（用RGB或YIQ表示，在这里没有影响）。因此，可以用三个8行8列的二维数组表示这个8×8的像素方块。每一个数组表示其中一个八位比特组合的像素值。离散余弦变换作用于每个数组