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

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

2、的和来表示的正弦波的和来表示”。 3 4 一维一维DFTDFT和和IDFTIDFT 1 0 2 1 0 2 1 N u u N x j N x x N u j e )u(F N xf exfuF N j N eWLet 2 u=0,1,2,N-1 x=0,1,2,N-1 1 0 1 0 1 N u ux N N x ux N W)u(F N Wxf 5 二维二维DFTDFT和和IDFTIDFT 1210 1210 1 1 0 1 0 2 1 0 1 0 2 N,., ,y, v M,., ,x ,u e )v ,u(F MN )y, x(f e )y, x(f)v ,u(F M u N n )

3、 N vy M ux (j N x N y ) N vy M ux (j 6 二维离散傅立叶变换的性质二维离散傅立叶变换的性质 7 8 二维傅立叶变换特性二维傅立叶变换特性:可分离性可分离性 二维二维DFT可分离为两次一维可分离为两次一维DFT f(x,y)F(x,v)F(u,v) 按列进行按列进行 一维一维DFT 按行进行按行进行 一维一维DFT 9 可分离性可分离性 先对行做变换：先对行做变换： 然后对列进行变换然后对列进行变换： f(x,y) （0,0） （N-1，M-1） x y F(x,v) （0,0） （N-1，M-1） x v F(x,v) （0,0） （N-1，M-1） x v

4、 F(u,v) （0,0） （N-1，M-1） u v 10 )y, x( fFF ee )y, x( f )y, x( fFF ee )y, x( f e )y, x( f)v ,u(F xy N vy j N y N x M ux j yx M ux j N x N y N vy j N x N y ) N vy M ux (j 2 1 0 1 0 2 2 1 0 1 0 2 1 0 1 0 2 可分离性可分离性 先行后列先行后列 先列后行先列后行 11 二维傅立叶变换特性二维傅立叶变换特性:平移性平移性 ) N v , M u(F)(y, x(f N vand M uif )vv ,uu

5、(Fe )y, x(f e )v ,u(F)yy,xx(f )v ,u(F)y, x(f yx ) N yv M xu (j ) N yv M xu (j 22 1 22 00 00 2 2 00 00 00 将图像的频谱原点将图像的频谱原点(0,0)移动到图像中心（移动到图像中心（M/2,N/2)处处 12 二维傅立叶变换特性二维傅立叶变换特性:平移性平移性 原图原图 无平移的傅立叶频谱无平移的傅立叶频谱 平移后的傅立叶频谱平移后的傅立叶频谱 13 二维傅立叶变换特性二维傅立叶变换特性:旋转不变性旋转不变性 在时域中离散函数旋转在时域中离散函数旋转 0角度，则在变换域内角度，则在变换域内 离

6、散傅立叶函数也将旋转同样的角度。离散傅立叶函数也将旋转同样的角度。 ),(F), r(f ),(F), r(f 00 14 二维傅立叶变换特性二维傅立叶变换特性:旋转不变性旋转不变性 15 快速傅立叶变换快速傅立叶变换(FFT) Fast Fourier Transforming 16 有限长序列通过离散傅立叶变换有限长序列通过离散傅立叶变换(DFT)将其频域离散将其频域离散 化成有限长序列化成有限长序列.但其计算量太大但其计算量太大(与与N2成正比）成正比）,很难很难 实时地处理问题实时地处理问题,因此引出了快速傅立叶变换因此引出了快速傅立叶变换(FFT). FFT并不是一种新的变换形式并不

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

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

9、揭开了FFT发展史上的第一页，促使发展史上的第一页，促使 FFT算法产生原因还有算法产生原因还有1967年至年至1968年间年间FFT的数字的数字 硬件制成，电子数字计算机的条件，使硬件制成，电子数字计算机的条件，使DFT的运算大大的运算大大 简化了。简化了。 18 1 1 0 1 1 0 111110 111110 010100 Nf f f WWW WWW WWW NF F F N)N()N()N( N N N/j N x ux N x x N u j eW WxfexfuF 2 1 0 1 0 2 旋转因子 矩阵形式的一维矩阵形式的一维DFT: W系数矩阵系数矩阵 FFT的推导的推导 1

10、9 xu N xu N xu N N j N xuNxu N N j N WWWW eW WW eW 22 2 2 2 2 1 1 系数系数W是以是以N为周期的，所以为周期的，所以W阵中很多系数是相同的，阵中很多系数是相同的， 不必进行多次重复计算，又由于不必进行多次重复计算，又由于W的对称性，可以进一步的对称性，可以进一步 减少计算工作量。减少计算工作量。 FFT的推导的推导 W4= W6= W9= W3= W2= W0 W2 W1 -W1 - W0 假设假设N4，u,x=0,1,2,3 20 W阵的变换如下：阵的变换如下： FFT的推导的推导 1010 0000 1010 0000 WWW

11、W WWWW WWWW WWWW 9630 6420 3210 0000 WWWW WWWW WWWW WWWW 21 FFT的基本思想的基本思想 把一个把一个N点的点的DFT分解成两个分解成两个N/2短序列的短序列的DFT，即，即 分解成偶数和奇数序列的分解成偶数和奇数序列的DFT Fe(u)和和Fo(u)，并充，并充 分利用旋转因子分利用旋转因子W的周期性和对称性来计算的周期性和对称性来计算DFT， 简化运算过程。简化运算过程。 1 0 1 0 1 2 0 12 1 2 0 2 122 122 2 M x ux M u N M x ux M N x )x(u N N x )x(u N Wx

12、fWWxf WxfW)x(fuF MN ux M u N N xu j N u j N ux j )x(u N j )x(u N ux M M ux i N ux j )x(u N j WWeee)e(W Wee)e( 2 22 2 2 12 2 12 2 2 2 2 2 u(2x) N W 22 )WW,WW( uFWuF)Mu(F uFWuFuF WxfuF WxfuF u M Mu M u M Mu M o u Me o u Me M x ux Mo M x ux Me 22 2 2 1 0 1 0 12 2 对前对前M个个DFT 对后对后M个个DFT FFT的推导的推导 23 u M

13、xju M M xM j M u j Mu M j Mu M WeWeeeW 22 2 2 2 2 2 2 2 )( u M xju M M xM j M u j Mu M j Mu M WeWeeeW 2 22 2 )( W5= - w1 N=8, M=4, W=W8，u=0,1,27 W7= - w3 FFT的推导的推导 24 F(1) F(5) Fe(1) Fo(5) W1 W1 )(FW)(F)(F )(FW)(FF oe oe 515 511 1 1 蝶形运算单元蝶形运算单元 FFT的蝶形算法的蝶形算法 计算量计算量? ? 25 f(2) f(1) f(5) f(3) f(7) f(

14、0) f(4) f(6) F(0) F(1) F(2) F(3) F(4) F(5) F(6) F(7) W0 W4 W4 W4 W4 W0 W0 W0 F1(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) W0 W2 W4 W6 W0 W2 W4 W6 W0 W1 W2 W3 W4 W5 W6 W7 8点的点的FFT的完整蝶形计算图和逐级分解图。的完整蝶形计算图和逐级分解图。 37261504 WW,WW,WW,WW 奇奇 偶偶 分分 组，组， 输输 入入

15、 倒倒 序序 第一级第一级第二级第二级第三级第三级 输输 出出 顺顺 序序 FFT的蝶形算法的蝶形算法 26 )()()()( )()()()( )()()()( )()()()( )()()()( )()( 7531 6240 7351 8240 6420 400 0000 000 1 0 1 0 1 0 1 2 0 2 ffff ffff fWfWfWfW FWfWfWf FWFWFWF FWFF FFT的蝶形算法的蝶形算法 27 )()()()( )()()()( )()()()( )()()()( )()()()( )()()()( )()()()( )()( 7531 6240 75

16、31 6240 7351 6240 6420 404 4 0004 000 1 0 1 4 1 0 1 2 4 2 ffff ffff ffffW ffff fWfWfWfW fWfWfWf FWFWFWF FWFF FFT的蝶形算法的蝶形算法 28 输入码位倒置，输出顺序输入码位倒置，输出顺序 自然顺序自然顺序二进制表示二进制表示码位倒置码位倒置码位倒置顺序码位倒置顺序 00000000 10011004 20100102 30111106 41000011 51011013 61100115 71111117 29 时间抽取时间抽取FFTFFT（将（将f(x)f(x)序列按序列按x x的奇

17、偶进行分组计算）的奇偶进行分组计算） 对对 点的信号，需次递推，每次递推有 点的信号，需次递推，每次递推有 个蝶形，共有个蝶形，共有( (2)M2)M( (2 2）loglog2 2个蝶个蝶 形，每个蝶形包括次乘法和两次加法。总计算量形，每个蝶形包括次乘法和两次加法。总计算量 (1/2)Nlog(1/2)Nlog2 2N N次次乘法和乘法和NlogNlog2 2N N次次加法。加法。 对点对点DFTDFT总计算量为：总计算量为： 次乘法和 次乘法和N(N-1)N(N-1)次加法。次加法。 算法复杂性算法复杂性 30 FFT与DFT的比较 NN (DFT) log2N (FFT) N/(log2

18、N) 2422.0 864242.7 1024104857610240102.4 40961677721649152341.3 31 FourierFourier变换变换 高频反映细节、低频反映景物概貌的特性高频反映细节、低频反映景物概貌的特性 高频滤波高频滤波 低频滤波低频滤波 图像压缩图像压缩，将高频系数置为将高频系数置为0 0 将卷积运算转换为点乘运算，由此简化运算，提高将卷积运算转换为点乘运算，由此简化运算，提高 计算速度。计算速度。 二维二维FourierFourier变换的应用变换的应用 32 )(SG ),(jif ),(jif g fgf g ),(),(),(FGFg )(

19、1 gg FFFTf 33 离散余弦变换离散余弦变换 DCT 34 FourierFourier变换的一个最大的问题是：它的参变换的一个最大的问题是：它的参 数都是复数，在数据的描述上相当于实数的数都是复数，在数据的描述上相当于实数的 两倍。两倍。 为此，我们希望有一种能够达到相同功能但为此，我们希望有一种能够达到相同功能但 数据量又不大的变换。在此期望下，产生了数据量又不大的变换。在此期望下，产生了 DCTDCT变换。变换。 问题的提出问题的提出 35 离散余弦变换（离散余弦变换（Discrete Cosine TransformDiscrete Cosine Transform）的）的 变

20、换核为余弦函数。变换核为余弦函数。DCTDCT除了具有一般的正交变换除了具有一般的正交变换 性质外，性质外， 它的变换阵的基向量能很好地描述人类它的变换阵的基向量能很好地描述人类 语音信号和图像信号的相关特征。因此，在对语音语音信号和图像信号的相关特征。因此，在对语音 信号、图像信号的变换中，信号、图像信号的变换中，DCTDCT变换被认为是一种变换被认为是一种 准最佳变换。近年颁布的一系列视频压缩编码的国准最佳变换。近年颁布的一系列视频压缩编码的国 际标准建议中，都把际标准建议中，都把DCTDCT作为其中的一个基本处理作为其中的一个基本处理 模块。除此之外，模块。除此之外， DCTDCT还是一

21、种可分离的变换。还是一种可分离的变换。 36 把一幅图像划分成一系列的图像块，每个图像块把一幅图像划分成一系列的图像块，每个图像块 包含包含88个像素。如果原始图像有个像素。如果原始图像有640480个个 像素，则图片将包含像素，则图片将包含80列列60行的方块。如果图像行的方块。如果图像 只包含灰度，那么每个像素用一个只包含灰度，那么每个像素用一个8比特的数字比特的数字 表示。因此可以把每个图像块表示成一个表示。因此可以把每个图像块表示成一个8行行8列列 的二维数组。数组的元素是的二维数组。数组的元素是0255的的8比特整数。比特整数。 离散余弦变换就是作用在这个数组上。离散余弦变换就是作用

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

23、个同样 包含包含8行行8列二维数组的函数，也就是说，把一个数组通列二维数组的函数，也就是说，把一个数组通 过一个变换，变成另一个数组。过一个变换，变成另一个数组。 如图下图所示，对每个图像块做离散余弦变换。通过如图下图所示，对每个图像块做离散余弦变换。通过 DCTDCT变换可以把能量集中在矩阵左上角少数几个系数上。变换可以把能量集中在矩阵左上角少数几个系数上。 wf(i,j)经DCT变换之后得到F(u,v)，其中F(0,0)是直流系数， 称为DC系数，其他为交流系数，称为AC系数。 39 离散余弦变换的数组离散余弦变换的数组 wf(i,j)经DCT变换之后得到F(u,v)，其中F(0,0)是直流系数， 称为DC系数，其他为交流系数，称为AC系数。 40 离散余弦变换（离散余弦变换（DCTDCT） 逆变换： 1 0 1 0 22 2 1212 M x