图像处理实践电子课件教案-第4章 图像变换.ppt

2019/12/6,第4章图像变换,4.1连续傅里叶变换4.2离散余弦变换4.3K-L变换4.4小波变换,2019/12/6,第4章图像变换,为了有效和快速地对图像进行处理和分析，常常需要将原定义在图像空间的图像以某种形式转换到其他空间，并且利用图像在这个空间的特有性质进行处理，然后通过逆变换操作转换到图像空间。本章讨论图像变换重点介绍图像处理中常用的正交变换，如傅里叶变换、离散余弦变换和小波变换等。,2019/12/6,1.一维连续傅里叶变换设f(x)为x的函数，如果f(x)满足下面的狄里赫莱条件：(1)具有有限个间断点；(2)具有有限个极值点；(3)绝对可积。则定义f(x)的傅里叶变换为：,4.1连续傅里叶变换,2019/12/6,式中x为空域变量，u为频域变量，j为虚数单位。从F(u)恢复f(x)称为傅里叶反变换，定义为：,上述二式形成傅里叶变换对，记做：,函数f(x)的傅里叶变换一般是一个复数，它可以由下式表示：F(u)=R(u)+jI(u)R(u),I(u)分别为F(u)的实部和虚部。,写成指数形式：,4.1连续傅里叶变换,2019/12/6,F(u)为复平面上的向量，它有幅度和相角：,幅度：,相角：,幅度函数|F(u)|称为f(x)的傅里叶谱或频率谱，(u)称为相位谱。,称为f(x)的能量谱或称为功率谱。,4.1连续傅里叶变换,2019/12/6,2.二维连续傅里叶变换傅里叶变换可以推广到两个变量连续可积的函数f(x,y)若f(x,y)满足狄里赫莱条件，则存在如下傅里叶变化对：,二维函数的傅里叶谱、相位和能量谱分别表示为：,2019/12/6,1.一维离散傅里叶变换对一个连续函数f(x)等间隔采样可得到一个离散序列。设共采了N个点，则这个离散序列可表示为f(0),f(1),f(N-1)。借助这种表达，并令x为离散空域变量，u为离散频率变量，可将离散傅里叶变换定义为：,4.1.2离散傅里叶变换,2019/12/6,傅里叶反变换定义由表示：,可以证明离散傅里叶变换对总是存在的。其傅里叶谱、相位和能量谱如下：,4.1.2离散傅里叶变换,2019/12/6,2.离散傅里叶变换（DFT）的矩阵表示法由DFT的定义，若考虑1/N系数，N4的原信号序列f(x)=f(0),f(1),f(2),f(3)的傅里叶变换F(u)展开为：,4.1.2离散傅里叶变换,2019/12/6,将e指数项化简可写成矩阵形式（计算机处理通常可忽略1/N）：,记作：,式中W称作变换核矩阵，简称核矩阵。矩阵计算需把指数表示为a+jb。可用复平面的单位圆来求W的各元素。如图4-1所示。当N=4时，参看图4.1(a)。把单位圆分为N=4份，则正变换矩阵第u行每次移动u份得到该行系数。这样N=4时W阵如下：,4.1.2离散傅里叶变换,2019/12/6,(a),(b),图4.1复平面单位圆(a)N4(b)N8,4.1.2离散傅里叶变换,2019/12/6,同理N=8见图4-1(b)的单位圆。N=8的W阵应把单位圆分为8份，顺时顺次转0份,1份、,7份，可得W阵为:,4.1.2离散傅里叶变换,2019/12/6,4.1.2离散傅里叶变换,2019/12/6,用以上表示方法可把傅里叶正变换式写为：,式中,显然，具有周期性，即：,另外，还具有对称性：,4.1.2离散傅里叶变换,2019/12/6,3.快速傅里叶变换(FFT)这里介绍一种称为逐次加倍法的快速傅里叶变换算法。设N为2的整数次幂，即N=2n。如果N不是2的整数次幂，则它的FFT算法比较复杂，这里不做介绍，有兴趣的可以查阅有关信号处理的书籍。设：fe(x)=f(2x)x=0,1,2,N/2-1fo(x)=f(2x+1)x=0,1,2,N/2-1由此，离散傅里叶变换可写成下面的形式：,4.1.2离散傅里叶变换,2019/12/6,4.1.2离散傅里叶变换,2019/12/6,上式中,这样，就将一个求N点的离散傅里叶变换转换成求两个N/2点的离散傅里叶变换。设N=8，根据上式可以求得：,4.1.2离散傅里叶变换,2019/12/6,根据傅里叶变换的周期性和W的对称性，同时注意这里的Fe(u)和Fo(u)都是4点DFT，因而周期是4，即：,4.1.2离散傅里叶变换,2019/12/6,从而上式可以简化为：,4.1.2离散傅里叶变换,2019/12/6,现在已经大大地简化了DFT的计算，但是还可以继续简化。事实上，Fe(u)和Fo(u)都是4个点的DFT。按照上面的思路，Fe(u)和Fo(u)都还可以简化为2个点的DFT。设：,则：,4.1.2离散傅里叶变换,2019/12/6,将上式展开并进一步简化为：,这样，A(u),B(u),C(u),D(u)都已经是2点的DFT，他们可以根据一维离散傅里叶变换的公式由原始数据f(x)直接求得。计算方法如下：,4.1.2离散傅里叶变换,2019/12/6,上面就是8个点的快速傅里叶变换算法(FFT),对于更多的点的FFT,可以依次类推。为了便于理解，下面给出FFT的更加直观的蝶形流图。如图4.2所示为FFT蝶形运算流程图的一个运算单元。,4.1.2离散傅里叶变换,2019/12/6,图4.2FFT的蝶形运算单元,其中BA+mC，D=C+nA，则8点FFT的完整蝶形计算流图如图4.3所示。,4.1.2离散傅里叶变换,2019/12/6,图4.38点FFT蝶形流图,4.1.2离散傅里叶变换,2019/12/6,图4.48点DFT逐级分解框图,4.1.2离散傅里叶变换,2019/12/6,图4.58点FFT蝶形流图,4.1.2离散傅里叶变换,2019/12/6,4.用计算机实现快速傅里叶变换要解决的问题利用FFT蝶式流程图算法在计算机上实现快速傅里叶变换必须解决如下问题：迭代次数r的确定；对偶节点的计算；加权系数的计算；重新排序问题。1、迭代次数r的确定由蝶式流程图可见，迭代次数与N有关。r值可由下式确定：,式中N是变换序列的长度。,4.1.2离散傅里叶变换,2019/12/6,2、对偶节点的计算在流程图中把标有的点称为节点。其中下标l为列数，也就是第几次迭代，k代表流程图中的行数，也就是序列的序号数。其中每一节点的值均是用前一节点对计算得来的。例如，x1(0)和x1(4)均是x(0)和x(4)计算得来的。在蝶式流程图中，把具有相同来源的一对节点叫做对偶节点。对偶节点的计算也就是求出在每次迭代中对偶节点的间隔或者节距。由流程图可见，第一次选代的节距为N/2，第二次迭代的节距为N/4，第三次迭代的节距为N/23等等。由以上分析可得到如下对偶节点的计算方法。如果某一节点为，那么，它的对偶节点为:,4.1.2离散傅里叶变换,2019/12/6,式中l是第几次迭代的数字，k是序列的序号数，N是序列长度。例如果序列长度N=8，求x2(1)的对偶节点。利用上式计算，可得：,4.1.2离散傅里叶变换,2019/12/6,3、加权系数的计算的计算主要是确定p值。p值可用下述方法求得：把k值写成r位的二进制数(k是序列的序号数，r是迭代次数)；把这个二进制数右移r-l位，并把左边的空位补0（结果仍为r位）；把这个右移后的二进制数进行比特倒转；把这比特倒转后的二进制数变成十进制数就得到p值。,4.1.2离散傅里叶变换,2019/12/6,例：求x2(2)的加权系数。由x2(2)和可知k=2，l=2，N=8，则r=log2N=log28=31）因为k=2，所以写成二进制数为010；2）r-l=3-2=1，把010右移一位得到001；3）把001做位序颠倒，即做比特倒转，得到100；4）把100译成十进制数，得到4，所以p=4，x2(2)的加权值为。,4.1.2离散傅里叶变换,2019/12/6,结合对偶节点的计算，可以看出具有下述规律：如果某一节点上的加权系数为，则其对偶节点的加权系数必然是，而且，所以一对对偶节点可用下式计算：,4.1.2离散傅里叶变换,2019/12/6,4、重新排序由蝶式流程图可见，如果输入序列x(n)是按顺序排列的，经过蝶式运算后，其变换序列是非顺序排列的，即乱序的；反之，如果x(n)是乱序的，那么，X(m)就是顺序的。因此，为了便于输出使用，应加入重新排序程序，以便保证x(n)与它的变换系数X(m)的对应关系。具体排序方法如下：1）将最后一次迭代结果xl(k)中的序号数k写成二进制数；2）将r位的二进制数比特倒转；3）求出倒置后的二进制数代表的十进制数，就可以得到与x(k)相对应的X(m)的序号数。,4.1.2离散傅里叶变换,2019/12/6,5.傅里叶反变换傅里叶反变换可以利用正变换来进行计算。只须对正变换的输入作一点修改就可用于反变换。傅里叶反变换如下：,取上式的复共轭并两边同除以N得到：,4.1.2离散傅里叶变换,2019/12/6,上式右边对应一个正变换，即F*(u)的傅里叶正变换。因此，求傅里叶反变换可以先求傅里叶变换F(u)的复共轭F*(u)，然后求F*(u)的傅里叶变换得到f*(x)/N，对此再求复共轭并乘以N就得到所需的反变换f(x)。,4.1.2离散傅里叶变换,2019/12/6,6.二维离散傅里叶变换一幅静止的数字图像可看做是二维数据阵列。因此，数字图像处理主要是二维数据处理。如果一幅二维离散图像f(x,y)的大小为M*N，则二维傅里叶变换可用下面二式表示。,4.1.2离散傅里叶变换,2019/12/6,在图像处理中，一般总是选择方形阵列，所以通常情况下总是M=N。因此，二维离散傅里叶变换多采用下面两式形式：,4.1.2离散傅里叶变换,2019/12/6,7.二维离散傅里叶变换的性质二维离散傅里叶变换有一些重要的性质，这些性质为使用提供了极大的方便。1）分离性二维离散傅里叶变换具有分离性,4.1.2离散傅里叶变换,2019/12/6,其中：,分离性质的主要优点是可借助一系列一维傅里叶变换分两步求得F(u,v)。第1步，沿着f(x,y)的每一行取变换，将其结果乘以1/N,取得二维函数F(x,v);第2步，沿着F(x,v)的每一列取变换，再将结果乘以1/N,就得到了F(u,v)。这种方法是先行后列。如果采用先列后行的顺序，其结果相同。如图4.6所示。,4.1.2离散傅里叶变换,2019/12/6,行变换,列变换,图4.6把二维傅里叶变换作为一系列一维的计算方法,4.1.2离散傅里叶变换,2019/12/6,对逆变换f(x,y)也可以类似地分两步进行。,4.1.2离散傅里叶变换,2019/12/6,2）平移性傅里叶变换和逆变换对的位移性质是指：,由f(x,y)乘以指数项并取其乘积的傅立叶变换，使频率平面的原点位移至(u0,v0)。同样地，以指数项乘以F(u,v)并取其反变换，将空间域平面的原点位移至(x0,y0)。当u0=v0=N/2时，指数项为：,4.1.2离散傅里叶变换,2019/12/6,即为：,这样，用（-l）(x+y)乘以f(x,y)就可以将f(x,y)的傅里叶变换原点移动到N*N频率方阵的中心，这样才能看到整个谱图。另外，对f(x,y)的平移不影响其傅里叶变换的幅值。此外，与连续二维傅里叶变换一样，二维离散傅里叶变换也具有周期性、共轭对称性、线性、旋转性、相关定理、卷积定理、比例性等性质。这些性质在分析及处理图像时有重要意义。,4.1.2离散傅里叶变换,2019/12/6,8.DFT应用中的问题1）频谱的图像显示DFT在计算机图像处理中计算的中间过程和结果要图像化。对DFT来讲不但f(x,y)是图像,F(u,v)也要用图像来显示其结果。谱图像就是把|F(u,v)|作为亮度显示在屏幕上。但在傅里叶变换中F(u,v)随u,v的衰减太快，其高频项只看到一两个峰，其余皆不清楚。由于人的视觉可分辨灰度有限，为了得到清晰的显示效果，即为了显示这个频谱，可用下式处理，设显示信号为D(u,v),4.1.2离散傅里叶变换,2019/12/6,即用显示D(u,v)来代替只显示|F(u,v)|不够清楚的补救方法。谱的显示加深了对图像的视觉理解。如一幅遥感图像受正弦网纹的干扰，从频谱图上立即可指出干扰的空间频率并可方便地从频域去除。如图4.7为图像的傅里叶频谱图像,4.1.2离散傅里叶变换,2019/12/6,图4.7图像的傅里叶频谱图像，原始图像，(b)频谱直接显示，(c)频谱经过变换后的结果,(b),(c),4.1.2离散傅里叶变换,a.,a.,2019/12/6,2.频谱图像的移中显示常用的傅里叶正反变换公式都是以零点为中心的公式，其结果中心最亮点却在频谱图像的左上角，作为周期性函数其中心最亮点将分布在四角，为了观察方便，将频谱图像的零点移到显示的中心。当周期为N时，应在频域移动N/2。利用DFT的平移性质，先把原图像f(x,y)乘以(-1)(x+y)然后再进行傅里叶变换，其结果谱就是移N/2的F(u,v)。图4-8所示。应当注意，显示是为了观看，而实际F(u,v)数据仍保留为原来的值。,4.1.2离散傅里叶变换,2019/12/6,图4.8频谱图像的移中显示(a)未移至中心的频谱图像，(b)移至中心后的频谱图像,(a),(b),4.1.2离散傅里叶变换,2019/12/6,3.旋转性应用中，对两幅图像进行傅里叶变换后，为求两幅图像的相似性，常须对频域图进行旋转寻找匹配。此时FT公式常用极坐标表示为傅里叶变换对。设f(x,y)为原图中任一点的坐标，为(x,y)点与x轴的夹角，则傅里叶变换对为：,若空域,频域,4.1.2离散傅里叶变换,2019/12/6,则旋转不变性质为：,上式表明，在空域中对图像f(x,y)旋转0对应于将其傅里叶变换F(u,v)也旋转0，类似的，对F(u,v)旋转0也对应于将其傅里叶反变换f(x,y)旋转0。,4.1.2离散傅里叶变换,2019/12/6,(a),(b),图4.9傅里叶变换的旋转性，对比图4.8,4.1.2离散傅里叶变换,2019/12/6,9.数字图像傅里叶变换的频谱分布和统计特性1)数字图像傅里叶变换的频谱分布数字图像的二维离散傅里叶变换所得结果的频率成分如图4.10所示，左上角为直流成分，变换结果的四个角的周围对应于低频成分，中央部位对应于高频部分。为了便于观察谱的分布，使直流成分出现在窗口的中央，可采用图示的换位方法，根据傅里叶频率位移的性质，只需要用f(x，y)乘上因子进行傅里叶变换即可实现，变换后的坐标原点移动到了窗口中心，围绕坐标中心的是低频，向外是高频。,4.1.2离散傅里叶变换,2019/12/6,图4.10二维傅里叶变换的频谱分布,4.1.2离散傅里叶变换,2019/12/6,图4.11频率位移示例,4.1.2离散傅里叶变换,2019/12/6,图4.11为二维离散傅里叶变换的频率位移特性。围绕坐标中心的是低频，向外是高频，频谱由中心向周边放射，而且各行各列的谱对中心点是共轭对称的，利用这个特性，在数据存储和传输时，仅存储和传输它们中的一部分，进行逆变换恢复原图像前，按照对称性补充另一部分数据，就可达到数据压缩的目的。,2）图像傅里叶变换的统计分布（1）傅里叶变换后的零频分量F（0，0），也称作直流分量，根据傅里叶变换公式有：,它反映了原始图像的平均亮度。,4.1.2离散傅里叶变换,2019/12/6,（2）对大多数无明显颗粒噪音的图像来说，低频区集中了85的能量，这一点成为对图像变换压缩编码的理论根据，如变换后仅传送低频分量的幅值，对高频分量不传送，反变换前再将它们恢复为零值，就可以达到压缩的目的。（3）图像灰度变化缓慢的区域，对应它变换后的低频分量部分；图像灰度呈阶跃变化的区域，对应变换后的高频分量部分。除颗粒噪音外，图像细节的边缘、轮廓处都是灰度变化突变区域，它们都具有变换后的高频分量特征。,4.1.2离散傅里叶变换,2019/12/6,4.2离散余弦变换,数字图像处理中的正交变换，除了傅里叶变换以外，还经常用到离散余弦变换（DiscreteCosineTransform，DCT)。DCT是与傅里叶变换相关的一种变换，它类似于离散傅里叶变换(DiscreteFourierTransform,DFT)，但是只使用实数。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换，这个离散傅里叶变换是对一个实偶函数进行的(因为一个实偶函数的傅里叶变换仍然是一个实偶函数)。,2019/12/6,4.2离散余弦变换,离散余弦变换经常在信号处理和图像处理使用，用于对信号和图像(包括静止图像和运动图像)进行有损数据压缩。离散余弦变换具有很强的“能量集中”特性。大多数的自然信号(包括声音和图像)的能量都集中在离散余弦变换后的低频部分。在后面讲述的静止图像编码标准JPEG中、运动图像编码标准MPEG和H.26x的各个标准中都使用了二维离散余弦变换。在这些标准中，首先对输入图像进行离散余弦变换，然后将DCT变换系数进行量化之后进行熵编码。在对输入图像进行DCT前，需要将图像分成子块，对每个块的每行进行DCT变换，然后每列进行变换。得到的是一个的变换系数矩阵。其中，(0,0)位置的元素就是直流分量，矩阵中的其他元素根据其位置，表示不同频率的交流分量。,2019/12/6,4.2.1一维离散余弦变换,2019/12/6,式中是第u个余弦变换系数，u是广义频率变量，；是时域N点序列，；两式构成了一维离散余弦变换对。,4.2.1一维离散余弦变换,2019/12/6,4.2.2二维离散余弦变换,2019/12/6,4.2.2二维离散余弦变换,2019/12/6,4.2.3离散余弦变换的矩阵表示,二维离散余弦变换具有系数为实数，正变换与逆变换的核相同的特点。离散余弦变换是一种正交变换。为了分析计算方便，还可以用矩阵的形式来表示。设f为一个N点的离散信号序列，可以用一个的列向量表示，F为频域中一个的列向量。的矩阵C为离散余弦变换矩阵，一维离散余弦变换表示为,2019/12/6,二维离散余弦变换为正变换,2019/12/6,4.2.3离散余弦变换的矩阵表示,2019/12/6,4.2.3离散余弦变换的矩阵表示,2019/12/6,4.2.3离散余弦变换的矩阵表示,2019/12/6,结果分析：离散余弦变换具有信息强度集中的特点。图像进行DCT变换后，在频域中矩阵左上角低频的幅值大而右下角高频幅值小，经过量化处理后产生大量的零值系数，在编码时可以压缩数据，因此DCT被广泛用于视频编码图像压缩。,4.2.3离散余弦变换的矩阵表示,2019/12/6,4.3K-L变换,卡-洛（K-L）变换是一种主成分分析的变换方法。当变量之间存在一定的相关关系时，可以通过原始变量的线性组合，构成为数较少的新变量代替原始变量。这种处理方法叫做主成分分析，其中的新变量叫做原始变量的主成分。,2019/12/6,4.3K-L变换,2019/12/6,4.3K-L变换,2019/12/6,4.3K-L变换,令和是的特征向量和对应的特征值，特征值按减序排列。变换矩阵的行是的特征值，则变换矩阵为,2019/12/6,4.3K-L变换,KL变换的定义为其中，K为新的图像向量，为原始向量减去均值向量，称为中心化的图像向量。,2019/12/6,4.3K-L变换,K-L变换的步骤如下。（1）求协方差矩阵；（2）求协方差矩阵的特征值；（3）求特征向量；（4）构成特征矩阵，按式计算。,2019/12/6,4.4小波变换,小波分析是当前应用数学和工程学科中一个迅速发展的领域。与傅里叶变换相比，小波变换是空间（时间）和频率的局部变换，因而能有效地从信号中提取信息。它通过伸缩和平移运算对信号进行多尺度细化，最终达到在高频处时间细分，低频处频率细分，能够自动适应时频信号分析的要求，从而聚焦到信号的任意细节。小波编码是近年来随着小波变换而提出的一种在图像和视频压缩领域具有很好发展的编码技术。由于小波变换具有良好的时域或空域局部特征，以及适应人类视觉系统的特性，所以它非常有利于图像视频信号的压缩编码。,2019/12/6,4.4.1连续小波变换,设函数f(t)具有有限能量，即（平方可积函数空间），给定基本小波函数，信号f(t)的连续小波变换定义为,2019/12/6,4.4.1连续小波变换,式中a为尺度参数，b为定位参数，函数称为小波。若则函数具有伸展作用，若则函数具有收缩作用。对于所有的，连续小波逆变换为,2019/12/6,4.4.1连续小波变换,2一维连续小波变换的性质1）线性小波变换是线性变换，它把一维信号分解成不同尺度的分量。设为的小波变换，如果,2019/12/6,4.4.1连续小波变换,2019/12/6,4.4.1连续小波变换,3)小波变换的时-频局部化小波变换实现时-频局部化分析的特点与信号频率高低密切相关。因此，了解小波变换在频域中的特性是很重要的。小波变换的时-频局部化表示为,2019/