图象变换1正交变换傅立叶变换.pptx

第三章 图像变换12024年4月19日什么是图像变换什么是图像变换?n图像变换是将图像从空间域变换到其它域（如频域）图像变换是将图像从空间域变换到其它域（如频域）的数学变换。的数学变换。n简单的图像变换通常就是一种简单的图像变换通常就是一种二维的正交变换二维的正交变换，但，但要求这种正交变换必须是要求这种正交变换必须是可逆的可逆的，并且正变换和反，并且正变换和反变换的算法不能太复杂。变换的算法不能太复杂。n常用的变换：傅立叶变换、离散余弦变换、沃尔什常用的变换：傅立叶变换、离散余弦变换、沃尔什变换和哈达玛变换、霍特林变换、拉东变换、小波变换和哈达玛变换、霍特林变换、拉东变换、小波变换等等。变换等等。第三章 图像变换22024年4月19日一、正交变换一、正交变换第三章 图像变换32024年4月19日连续函数集合的连续函数集合的正交性正交性n正交函数集合正交函数集合当当C C=1=1时，称集合为归一化正交函数集合时，称集合为归一化正交函数集合第三章 图像变换42024年4月19日正交函数集合的正交函数集合的完备性完备性若若f(x)是定义在是定义在t0和和t0+T区间的实值信号区间的实值信号，平方，平方可积。可以表示为：可积。可以表示为：对任意小的对任意小的0，存在充分大的，存在充分大的N，其中其中，则称函数则称函数U集合是完备的集合是完备的。意味着意味着f(x)可以由无可以由无穷级数来表示穷级数来表示第三章 图像变换52024年4月19日离散情况离散情况nn个正交向量个正交向量 当当C=1时，时，称归一化正交。即每一个相量为单位相称归一化正交。即每一个相量为单位相量量。第三章 图像变换62024年4月19日满足上式的基相量组成矩阵：满足上式的基相量组成矩阵：则一定满足：则一定满足：第三章 图像变换72024年4月19日一维正交变换一维正交变换对于一向量对于一向量f，用上述正交矩阵进行运算：，用上述正交矩阵进行运算：g=Af若要恢复若要恢复f，则，则:以上过程称为以上过程称为正交变换。正交变换。我们把原为我们把原为A-1可以用可以用AT来代替的来代替的A阵称为阵称为正正交矩阵。交矩阵。第三章 图像变换82024年4月19日二维正交变换二维正交变换 nNN二维函数可以类似于一维二维函数可以类似于一维正变换核反变换核l显然，这两个变换核应该满足显然，这两个变换核应该满足正交性和完正交性和完备性备性。第三章 图像变换92024年4月19日二、傅立叶变换二、傅立叶变换第三章 图像变换102024年4月19日傅立叶变换傅立叶变换n傅立叶变换域傅立叶变换域也称为也称为频域变换频域变换，它把图像，它把图像从图像从图像空间变换到频率空间空间变换到频率空间。n将原定义在图像空间的图像以某种形式转换（正将原定义在图像空间的图像以某种形式转换（正变换）到另外一些空间，并利用在这些空间的特变换）到另外一些空间，并利用在这些空间的特有性质方便地进行一定的加工，最后再转换回图有性质方便地进行一定的加工，最后再转换回图像空间（反变换或逆变换）以得到所需要的效果。像空间（反变换或逆变换）以得到所需要的效果。第三章 图像变换112024年4月19日1.连续函数的傅立叶变换连续函数的傅立叶变换 若若把把一一个个一一维维输输入入信信号号作作一一维维傅傅立立叶叶变变换换，该该信信号号就就被被变变换换到到频频域域上上的的一一个个信信号号，即即得得到到了了构构成成该该输输入入信信号的频谱，号的频谱，频谱反映了该输入信号由哪些频率构成频谱反映了该输入信号由哪些频率构成。当一个一维信号当一个一维信号f(x)满足狄里赫莱条件，即满足狄里赫莱条件，即f(x)（1）具有有限个间断点；具有有限个间断点；（2）具有有限个极值点；具有有限个极值点；（3）绝对可积。绝对可积。则其傅立叶变换对（正变换和逆变换）一定存在。则其傅立叶变换对（正变换和逆变换）一定存在。第三章 图像变换122024年4月19日一维傅立叶变换的定义一维傅立叶变换的定义f(x)为连续可积函数，其傅立叶变换定义为：为连续可积函数，其傅立叶变换定义为：其反变换为：其反变换为：式中式中：，x称为称为时域变量，时域变量，u为为频域变量。频域变量。通常傅立叶变换为复数形式通常傅立叶变换为复数形式F(u)=R(u)+jI(u)幅度谱：幅度谱：相位谱：相位谱：第三章 图像变换132024年4月19日变换分析的直观说明变换分析的直观说明 把一个信号的波形分解为许把一个信号的波形分解为许多不同频率正弦波之和。多不同频率正弦波之和。第三章 图像变换142024年4月19日一维傅立叶变换举例一维傅立叶变换举例方波信号：方波信号：经过傅立叶变经过傅立叶变换后：换后：第三章 图像变换152024年4月19日一维离散傅立叶变换一维离散傅立叶变换(DFT)一维离散傅立叶变换公式为：一维离散傅立叶变换公式为：逆变换为：逆变换为：数学上建立傅立叶变换的数学上建立傅立叶变换的f(x)是连续的是连续的模拟信号模拟信号，而计算机，而计算机处理的是离散的处理的是离散的数字信号数字信号，同时数学上用无穷大概念，而计算，同时数学上用无穷大概念，而计算机只能进行机只能进行有限次计算有限次计算。通常就将这种受限的傅立叶变换称为。通常就将这种受限的傅立叶变换称为离散傅立叶变换（离散傅立叶变换（DFT）。第三章 图像变换162024年4月19日由欧拉公式可知由欧拉公式可知可得可得 可见，离散序列的傅立叶变换仍然是一个离散的可见，离散序列的傅立叶变换仍然是一个离散的序列，序列，每一个每一个u对应的傅立叶变换结果是所有输对应的傅立叶变换结果是所有输入序列入序列f(x)的加权和。的加权和。每个每个f(x)都乘以不同频率的正弦和余弦值。都乘以不同频率的正弦和余弦值。第三章 图像变换172024年4月19日二维离散傅立叶变换二维离散傅立叶变换对于二维傅立叶变换，由一维推广而来，其离散对于二维傅立叶变换，由一维推广而来，其离散形式为：形式为：逆变换为：逆变换为：幅谱幅谱(频谱频谱)、相谱：、相谱：第三章 图像变换182024年4月19日二维傅立叶变换举例二维傅立叶变换举例对于二维方波信号对于二维方波信号傅立叶变换为：傅立叶变换为：幅度：幅度：第三章 图像变换192024年4月19日例：函数在以原点为中心的一个正方形内为正值常例：函数在以原点为中心的一个正方形内为正值常数，而在其它地方为零。傅立叶频谱幅度的灰度图数，而在其它地方为零。傅立叶频谱幅度的灰度图显示。显示。第三章 图像变换202024年4月19日二维傅立叶变换的性质二维傅立叶变换的性质 1.分离性分离性 二维二维傅立叶变换可由连续两次运用一维傅立叶变换来实现。傅立叶变换可由连续两次运用一维傅立叶变换来实现。第三章 图像变换212024年4月19日 由由可可分分离离性性可可知知，一一个个二二维维傅傅立立叶叶变变换换可可分分解解为为两两步步进进行行，其其中中每每一一步步都都是是一一个个一一维维傅傅立立叶叶变变换换。先先对对f(x,y)按按列列进进行行傅傅立立叶叶变变换换得得到到F(x,v)，再再对对F(x,v)按按行行进进行行傅傅立叶变换，便可得到立叶变换，便可得到f(x,y)的傅立叶变换结果，的傅立叶变换结果，如图所示。如图所示。显显然然对对f(x,y)先先按按行行进进行行离离散散傅傅立立叶叶变变换换，再再按按列列进进行行离离散散傅立叶变换也是可行的。傅立叶变换也是可行的。第三章 图像变换222024年4月19日2.平移性平移性 将将f(x,y)f(x,y)与一个指数项相乘就相当于把其变换后与一个指数项相乘就相当于把其变换后的频域中心移动到新的位置。的频域中心移动到新的位置。F(u,v)F(u,v)与一个指数项相乘就相当于把其反变换后与一个指数项相乘就相当于把其反变换后的空域中心移动到新的位置。的空域中心移动到新的位置。对对f(x,y)f(x,y)的平移不影响其傅立叶变换的幅值的平移不影响其傅立叶变换的幅值。第三章 图像变换232024年4月19日3.周期性和共扼对称性周期性和共扼对称性 如果如果f(x,y)f(x,y)是实函数，则它的傅立叶变换具有共扼是实函数，则它的傅立叶变换具有共扼对称性：对称性：F F*(u,v)(u,v)为为F(u,v)F(u,v)的复共扼。的复共扼。假定傅立叶变换和反变换均以假定傅立叶变换和反变换均以N为周期。为周期。第三章 图像变换242024年4月19日 由由旋旋转转不不变变性性可可知知，如如果果时时域域中中离离散散函函数数旋旋转转0角角度度，则则在在变变换换域域中中该该离离散散傅傅立立叶叶变变换换函函数数也也将将旋旋转转同同样样的的角角度度0。离离散散傅傅立立叶叶变变换换的的旋旋转转不不变变性如图性如图3-3所示。所示。图图3-3 离散傅立叶变换的旋转不变性离散傅立叶变换的旋转不变性（a）原始图像；原始图像；（b）原图像的傅立叶频谱；原图像的傅立叶频谱；（c）旋转旋转45后的图像；后的图像；（d）图像旋转后的傅立叶频谱图像旋转后的傅立叶频谱(a)(b)(d)(c)4.旋转性质旋转性质 借助极坐标变换借助极坐标变换 x=rcosx=rcos，y=rsiny=rsin，u=w cosu=w cos，v=w v=w sinsin，将，将f(x,y)f(x,y)和和F(u,v)F(u,v)转换为转换为f(r,)f(r,)和和F(w,)F(w,)。第三章 图像变换252024年4月19日傅立叶变换和反变换对加法满足分配律，但对乘法则不满足。傅立叶变换和反变换对加法满足分配律，但对乘法则不满足。5.分配律分配律 6.尺度变换尺度变换(缩放缩放)比例性质比例性质第三章 图像变换262024年4月19日将将u=v=0u=v=0代入正变换式，可以得到：代入正变换式，可以得到：7 7.平均值平均值 2 2个函数的卷积定义为：个函数的卷积定义为：8.卷积卷积平均值计算平均值计算计算步骤计算步骤:折叠折叠位移位移相乘相乘积分（求和）积分（求和）图像变换图像变换(二二)快速傅立叶变换、离散余弦变换快速傅立叶变换、离散余弦变换第三章 图像变换282024年4月19日普通傅立叶变换：普通傅立叶变换：完成全部完成全部DFT运算的计算量与运算的计算量与N2成正比。特别是当成正比。特别是当N较大较大时，其运算时间将迅速增长，时，其运算时间将迅速增长，以至于无法容忍。以至于无法容忍。为此，研究离散傅立叶变换的快速算法（为此，研究离散傅立叶变换的快速算法（Fast Fourier Transform，FFT）非常必要。）非常必要。研究快速傅立叶变换的必要性研究快速傅立叶变换的必要性 快速离散傅立叶变换快速离散傅立叶变换一一种种称称为为逐逐次次加加倍倍法法的的快快速速傅傅立立叶叶变变换换算算法法（FFT），它它是是1965年年Cooley和和Tukey首首先先提提出出的的。算算法法时时间间复复杂杂度度为为Nlog2N。当当N很大时计算量可以大大减少。很大时计算量可以大大减少。第三章 图像变换302024年4月19日记记称为旋转因子。则有称为旋转因子。则有：单位圆表示：单位圆表示：快速傅立叶变换快速傅立叶变换(3-1)第三章 图像变换312024年4月19日式中，由式中，由Wux构成的矩阵称为构成的矩阵称为W阵或系数矩阵。阵或系数矩阵。一维离散傅立叶变换（一维离散傅立叶变换（DFT）用矩阵的形式表示为：）用矩阵的形式表示为：第三章 图像变换322024年4月19日 W的定义表达式的定义表达式W=e-j2N，由，由欧拉公式欧拉公式知系数知系数W是以是以N为周为周期的。这样，期的。这样，W阵中很多系数就是相同的，阵中很多系数就是相同的，且由于且由于W的对称性，的对称性，即即 因此可进一步减少计算工作量。因此可进一步减少计算工作量。例如，对于例如，对于N=4，W阵为阵为 W4W0，W6W2，W9W1；W3W1，W2W0第三章 图像变换332024年4月19日 可可见见N=4的的W阵阵中中只只需需计计算算W0和和W1两两个个系系数数即即可可。说说明明W阵阵的的系系数数有有许许多多计计算算工工作作是是重重复复的的，如如果果把把一一个个离离散散序序列列分分解解成成若若干干短短序序列列，并并充充分分利利用用旋旋转转因因子子W的的周周期期性性和和对对称称性性来来计计算算离散傅立叶变换，便可以简化运算过程，离散傅立叶变换，便可以简化运算过程，这就是这就是FFT的基本思想。的基本思想。设设N为为2的正整数次幂，的正整数次幂，即即 如令如令M为正整数，且为正整数，且 N=2M 第三章 图像变换342024年4月19日将式将式N=2M代入式（代入式（3-1），离散傅立叶变换可改写成如下形式：），离散傅立叶变换可改写成如下形式：由旋转因子由旋转因子W的定义可知的定义可知，因此式因此式(3-2)变为变为 现定义现定义(3-2)(3-3)(3-4)(3-5)第三章 图像变换352024年4月19日于是式于是式(3-3)变为变为(3-6)进一步考虑进一步考虑W的对称性和周期性可知的对称性和周期性可知 和和，于是于是(3-7)由由此此，可可将将一一个个N点点的的离离散散傅傅立立叶叶变变换换分分解解成成两两个个N2短短序序列列的的离离散散傅傅立立叶叶变变换换，即即分分解解为为偶偶数数和和奇奇数数序序列列的的离离散散傅立叶变换傅立叶变换Fe(u)和和Fo(u)。第三章 图像变换362024年4月19日 在此，以计算在此，以计算N=8的的DFT为例，此时为例，此时n=3，M=4。由式。由式(3-6)和式和式(3-7)可得可得(3-8)第三章 图像变换372024年4月19日 式式（3-8）中中，u取取07时时的的F(u)、Fe(u)和和Fo(u)的的关关系系可可用用图图3.1描描述述。左左方方的的两两个个节节点点为为输输入入节节点点，代代表表输输入入数数值值；右右方方两两个个节节点点为为输输出出节节点点，表表示示输输入入数数值值的的叠叠加加，运运算算由由左左向向右右进进行行。线线旁旁的的W18和和W18为为加加权权系系数数，定定义义由由F(1)、F(5)、Fe(1)和和Fo(1)所构成的结构为蝶形运算单元所构成的结构为蝶形运算单元,其表示的运算为其表示的运算为(3-9)图图3.1 蝶形运算单元蝶形运算单元第三章 图像变换382024年4月19日 由于由于Fe(u)和和Fo(u)都是都是4点的点的DFT，因此，如果对它们再按照，因此，如果对它们再按照奇偶进行分组，奇偶进行分组，则有则有第三章 图像变换392024年4月19日图图3.2 4点点DFT分解为分解为2点点DFT的蝶形流程图的蝶形流程图 第三章 图像变换402024年4月19日二维快速傅立叶变换的Matlab实现简单图像及其傅立叶变换简单图像及其傅立叶变换Eg3.4nd=zeros(32,32);nd(13:20,13:20)=1;nfigure(1);nimshow(d,notruesize);nD=fft2(d);nfigure(2);nimshow(abs(D),-1 5,notruesize);第三章 图像变换412024年4月19日第三章 图像变换422024年4月19日二维快速傅立叶变换的Matlab实现eg3.3nfigure(1);nload imdemos saturn2;nimshow(saturn2);nfigure(2);nS=fftshift(fft2(saturn2);nimshow(log(abs(S),);第三章 图像变换432024年4月19日频域变换的一般表达式频域变换的一般表达式 1、可分离变换、可分离变换 二维傅立叶变换可用通用的关系式来表示二维傅立叶变换可用通用的关系式来表示：(3-10)(3-11)式式中中：x,u=0,1,2,M1；y,v=0,1,2,N1；g(x,y,u,v)和和h(x,y,u,v)分别称为正向变换核和反向变换核分别称为正向变换核和反向变换核。第三章 图像变换442024年4月19日如果如果 g(x,y,u,v)=g1(x,u)g2（y,v）(3-12)h(x,y,u,v)=h1(x,u)h2(y,v)(3-13)则则称称正正、反反变变换换核核是是可可分分离离的的。如如果果g1和和g2，h1和和h2在在函函数数形式上一样，则形式上一样，则称该变换核是对称的称该变换核是对称的。二维傅立叶变换对是一个特殊情况，二维傅立叶变换对是一个特殊情况，它们的核为它们的核为 可分离可分离对称对称第三章 图像变换452024年4月19日 对对于于图图像像变变换换，只只要要其其变变换换核核是是可可分分离离的的，就就可可用用两次一维变换来实现。两次一维变换来实现。如果先对f(x,y)的每一列进行一维变换得到F(y,u)，再沿F(y,u)每一行取一维变换得到F(u,v)，和先对f(x,y)的每一行进行一维变换得到F(x,v)，再沿F(x,v)每一列取一维变换得到F(u,v)其最终结果是一样的。该结论对反变换核也适用。该结论对反变换核也适用。第三章 图像变换462024年4月19日3.4 离散余弦变换第三章 图像变换472024年4月19日3.4.1 一维离散余弦变换一维离散余弦变换 一维一维DCT的变换核定义为的变换核定义为 式中，式中，x,u=0,1,2,N1；(3-47)(3-48)一维一维DCT定义如下：定义如下：设设f(x)|x=0,1,N-1为离散的信号列。为离散的信号列。(3-49)式中，式中，u,x=0,1,2,N1。第三章 图像变换482024年4月19日将变换式展开整理后，将变换式展开整理后，可以写成矩阵的形式，可以写成矩阵的形式，即即 F=Gf（3-50）其中(3-51)第三章 图像变换492024年4月19日 一维一维DCT的逆变换的逆变换IDCT定义为定义为(3-52)式中，式中，x,u=0,1,2,N1。可见一维。可见一维DCT的逆变换核的逆变换核与正变换核是相同的。与正变换核是相同的。第三章 图像变换502024年4月19日3.4.2 二维离散余弦变换二维离散余弦变换将一维将一维DCT的定义推广到二维的定义推广到二维DCT。其正变换核为。其正变换核为 (3-53)式式中中，C(u)和和C(v)的的定定义义同同式式（3-48）；x,u=0,1,2,M1；y,v=0,1,2,N1。第三章 图像变换512024年4月19日3.4.2 二维离散余弦变换二维离散余弦变换二维二维DCT定义如下：设定义如下：设f(x,y)为为MN的数字图像矩阵，则的数字图像矩阵，则(3-54)式中：式中：x,u=0,1,2,M1；y,v=0,1,2,N1。第三章 图像变换522024年4月19日 二维二维DCT逆变换定义如下：逆变换定义如下：(3-55)式中：式中：x,u=0,1,2,M1；y,v=0,1,2,N1。类类似似一一维维矩矩阵阵形形式式的的DCT，可可以以写写出出二二维维DCT的的矩矩阵阵形形式式如下：如下：F=GfGT (3-56)第三章 图像变换532024年4月19日 同时，由式同时，由式(3-55)和式和式(3-54)可知可知二维二维DCT的逆变换核与正的逆变换核与正变换核相同，且是可分离的变换核相同，且是可分离的，即，即(3-57)式中：式中：C(u)和和C(v)的定义同式（的定义同式（3-48）；）；x,u=0,1,2,M1；y,v=0,1,2,N1。第三章 图像变换542024年4月19日 通常根据可分离性，通常根据可分离性，二维二维DCT可用两次一维可用两次一维DCT来完成，来完成，其算法流程与其算法流程与DFT类似，类似，即即 第三章 图像变换552024年4月19日3.4.3 快速离散余弦变换快速离散余弦变换 离离散散余余弦弦变变换换的的计计算算量量相相当当大大，在在实实用用中中非非常常不不方方便便，也也需需要要研研究究相相应应的的快快速速算算法法。目目前前已已有有多多种种快快速速DCT（FCT），在此介绍一种由在此介绍一种由FFT的思路发展起来的的思路发展起来的FCT。首先，将首先，将f(x)延拓为延拓为 x=0,1,2,N-1x=N，N+1,2N-1(3-59)按照一维按照一维DCT的定义，的定义，fe(x)的的DCT为为(3-60)第三章 图像变换562024年4月19日式中，式中，Re表示取复数的表示取复数的实部。实部。第三章 图像变换572024年4月19日 由于由于 为为fe(x)的的2N点点DFT。因因此此，在在作作DCT时时，可可把把长长度度为为N的的f(x)的的长长度度延延拓拓为为2N点点的的序序列列fe(x)，然然后后对对fe(x)作作DFT，最后取，最后取DFT的实部便可得到的实部便可得到DCT的结果。的结果。同理对于离散余弦逆变换同理对于离散余弦逆变换IDCT，可首先将，可首先将F(u)延拓为延拓为u=0,1,2,N-1u=N,N+1,2N-1(3-62)第三章 图像变换582024年4月19日由式(3-52)可得，DCT的IDCT为（3-63）由式（由式（3-63）可见，）可见，IDCT可由可由 的的2N点的点的IDFT来实现。来实现。