数字图像处理：第3章 图像处理中的正交变换第一讲.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数字图像处理,第,2,章,图像处理中的正交变换,（,第一讲）,第,2,章 图像处理中的正交变换,数字图像处理的方法主要分为两大类：,一个是空间域处理法,(,或称空域法,),，,一个是频域法,(,或称变换域法,),。,在频域法处理中最为关键的预处理便是变换处理。,这种变换一般是线性变换，其基本线性运算式是严格可逆的，并且满足一定的正交条件，因此，也将其称作酉变换。目前，在图像处理技术中正交变换被广泛地运用于图像特征提取、图像增强、图像复原、图像识别以及图像编码等处理中。,1,傅里叶变换,傅里叶变换是大家所熟知的正交变换。在一维信号处理中得到了广泛应用。把这种处理方法推广到图像处理中是很自然的事。这里将对傅里叶变换的基本概念及算法作一些简单的复习。,1,1,傅里叶变换的定义及基本概念,傅里叶变换在数学中的定义是严格的。设,f,(,x,),为,x,的函数，如果满足下面的狄里赫莱条件：,（）具有有限个间断点；,（）具有有限个极值点；,（）绝对可积。,则有下列二式成立,(3,1),(3,2),式中,x,是,时域变量，,u,为频率变量。,如令 ，则有,(3,3),(3,4),通常把以上公式称为傅里叶变换对。,函数,f,(,x,),的傅里叶变换一般是一个复量，它可以由式（,35,）表示,(3,5),或写成指数形式,(3,6),(3,7),(3,8),把 叫做 的傅里叶谱，而 叫相位谱。,傅里叶变换广泛用于频谱分析。,例：求图,31,所示波形,f,(,x,),的频谱。,f(x),A,X,31,函数,的波形,则,的幅度谱及相位谱如图,3,2,所示。,图32,的幅度谱及相位谱,例：求周期函数的傅里叶谱。,一个周期为,T,的信号 可用傅里叶级数来表示，即,因此，傅里叶变换可写成下式,:,式中,图,33,周期函数的傅里叶谱,由上面的例子可以建立起下面几个概念：,（）只要满足狄里赫莱条件，连续函数就可以进行傅里叶变换，实际上这个条件在工程运用中总是可以满足的。,（）连续非周期函数的傅里叶谱是连续的非周期函数，连续的周期函数的傅里叶谱是离散的非周期函数。,傅里叶变换可推广到二维函数。如果二维函数,满足狄里赫莱条件，那么将有下面二维付里哀变换对存在：,(3,9),(3,10),与一维傅里叶变换类似，二维傅里叶变换的幅度谱和相位谱如下式,式中：是幅度谱；是相位谱；是能量谱。,(3,13),(3,11),(3,1,2,),1,2,傅里叶变换的性质,（）具有可分性,这个性质说明一个二维傅里叶变换可用二次一维傅里叶变换来实现。,（）线性,傅里叶变换是线性算子，即,（）共轭对称性,如果 是 的傅里叶变换，,是 傅里叶变换的共轭函数，那么,（）旋转性,如果空间域函数旋转的角度为 ，那么在变换域中此函数的傅里叶变换也旋转同样的角度，即,（）比例变换特性,如果 是 的傅里叶变换。,a,和,b,分别为两个标量，那么,（）帕斯维尔（,Parseval,）定理,这个性质也可称为能量保持定理。如果 是,的傅里叶变换，那么有下式成立,这个性质说明变换前后并不损失能量,（）相关定理,如果，,f,(,x,),g,(,x,),为两个一维时域函数；,f,(,x,y,),和,g,(,x,y,),为两个二维空域函数，那么，定义下二式为相关函数,由以上定义可引出傅里叶变换的一个重要性质。这就是相关定理，即,式中 是 的傅里叶变换，是,的傅里叶变换，是 的共轭，是 的共轭。,（）卷积定理,如果,f,(,x,),和,g,(,x,),是一维时域函数，,f,(,x,y,),和,g,(,x,y,),是二维空域函数，那么，定义以下二式为卷积函数，即,式中 和 分别是,f,(,x,),和,g,(,x,),的傅里叶变换。,由此，可得到傅里叶变换的卷积定理如下,1,3,离散傅里叶变换,连续函数的傅里叶变换是波形分析的有力工具，这在理论分析中无疑具有很大价值。离散傅里叶变换使得数学方法与计算机技术建立了联系，这就为傅里叶变换这样一个数学工具在实用中开辟了一条宽阔的道路。因此，它不仅仅有理论价值，而且在某种意义上说它也有了更重要的实用价值。,1,3,1,离散傅里叶变换的定义,如果,x,(,n,),为一数字序列，则其离散傅里叶正变换定义由下式来表示,(3,29),傅里叶反变换定义由下式来表示,(3,30),由,(329),和,(330),式可见，离散傅里叶变换是直接处理离散时间信号的傅里叶变换。如果要对一个连续信号进行计算机数字处理，那么就必须经过离散化处理。这样，对连续信号进行的傅里叶变换的积分过程就会自然地蜕变为求和过程。,1,3,2,离散傅里叶变换的性质,（）线性,如果时间序列,x,(,n,),与,y,(,n,),各有傅里叶变换,X,(,m,),和,Y,(,m,),，则,（）对称性,如果,则,（）时间移位,如果序列向右（或向左）移动,k,位，则,:,（）频率移位,如果,则,(3,40),（）周期性,如果,则,（）偶函数,如果,则,（）奇函数,如果,则,（）卷积定理,如果,则,反之,也成立。,（）相关定理,如果,则,（,10,）帕斯维尔定理,如果,则,1,4,快速傅里叶变换,(,FFT),随着计算机技术和数字电路的迅速发展，在信号处理中使用计算机和数字电路的趋势愈加明显。离散傅里叶变换已成为数字信号处理的重要工具。,然而，它的计算量较大，运算时间长，在某种程度上却限制了它的使用范围。快速算法大大提高了运算速度，在某些应用场合已可能作到实时处理，并且开始应用于控制系统。,快速傅里叶变换并不是一种新的变换，它是离散傅里叶变换的一种算法。,这种方法是在分析离散傅里叶变换中的多余运算的基础上，进而消除这些重复工作的思想指导下得到的，所以在运算中大大节省了工作量，达到了快速运算的目的。,对于一个有限长序列 ，,它的傅里叶变换由下式表示,(347),令,将正变换式（,348,）展开可得到如下算式,因此，傅里叶变换对可写成下式,(349,）,(348),(350),上面的方程式（,350,）可以用矩阵来表示,(351),从上面的运算显然可以看出，要得到每一个频率分量，需进行,N,次乘法和,N,-1,次加法运算。要完成整个变换需要 次乘法和,N,(,N,-1),次加法运算。当序列较长时，必然要花费大量的时间。,观察上述系数矩阵，发现 是以为,N,周期的，即,(352),例如，当,N,=8,时，其周期性如图,36,所示由于,所以，当,N,=8,时，可得：,图,36,N=8,时,的周期性和对称性,可见，离散傅里叶变换中的乘法运算有许多重复内容。,1965,年库利图基提出把原始的,N,点序列依次分解成一系列短序列，然后，求出这些短序列的离散傅里叶变换，以此来减少乘法运算。,快速傅里叶变换简称,FFT,。算法根据分解的特点一般有两类，一类是按时间分解，一类是按频率分解。下面介绍一下的基本形式及运算蝶式流程图。,1,4,基数按时间分解的算法,把,x(n,),分成偶数点和奇数点,即,:,这种算法的流程图如图,37,所示：图,(,a),输入为顺序的，运算结果是乱序的；图,(,b),输入为乱序的，运算结果是顺序的。,蝶式运算流程图,(,按时间分解,),蝶式运算流程图,(,按时间分解,),1,4,基数,2,按频率分解的算法,这种分解方法是直接把序列分为前 点和后 点两个序列，即,(355),1,5,用计算机实现快速付傅里叶变换,利用,FFT,蝶式流程图算法在计算机上实现快速傅里叶变换必须解决如下问题：,1,）、迭代次数,r,的确定；,2,）、对偶节点的计算；,3,）、加权系数 的计算；,4,）、重新排序问题。,(1),迭代次数,r,的确定,由蝶式流程图可见，迭代次数,r,与,N,有关。值可由下式确定,(359),式中,N,是变换序列的长度。对于前述基数,2,的蝶式流程图是,2,的整数次幂。例如，序列长度为,8则要三次迭代，序列长度为,16,时就要,4,次迭代等等。,(2),对偶节点的计算,在流程图中把标有 的点称为节点。其中下标,l,为列数，也就是第几次迭代，例如，则说明它是第一次迭代的结果。代表流程图中的行数，也就是序列的序号数。其中每一节点的值均是用前一节点对计算得来的。,例如，和 均是,x,(0),和,x,(4),计算得来的。,在蝶式流程图中，,把具有相同来源的一对节点叫做对偶节点。,如,:,和 就是一对对偶节点，因为它们均来源于,x,(0),和,x,(4),。对偶节点的计算也就是求出在每次迭代中对偶节点的间隔或者节距。由流程图可见，,由流程图可见，第一次迭代的节距为 ，第二次迭代的节距为 ，第三次迭代的节距为,等等。由以上分析可得到如下对偶节点的计算方法。,如果某一节点为 ，那么，它的对偶节点为,式中,l,是表明第几次迭代的数字，,k,是序列的序号数，,N,是序列长度。,(360),例：如果序列长度,N,=8,，求 的对偶节点,。,可利用式（,360,）计算，得,则,其正确性不难由流程图来验证。,（,3,）加权系数 的计算,的计算主要是确定,P,值。,P,值可用下述方法求得,。,（）把,k,值写成,r,位的二进制数（,k,是序列的序号数，,r,是迭代次数）；,（）把这个二进制数右移,r-l,位，并把左边的空位补零（结果仍为,r,位）；,（）把这个右移后的二进制数进行比特倒转；把这比特倒转后的二进制数翻成十进制数就得到,p,值。,例：求 的加 权系数 。,由 和 可知,k,=2,，,l,=2,，,n,=8,，,则,（）因为,k,=2,，所以写成二进制数为,010,；,（）,r,-,l,=3-2=1,，把,010,右移一位得到,001,；,（）把,001,做位序颠倒，即做比特倒转，得到,100,；,（）把,100,译成十进制数，得到,4,，所以,P,=4,，的加权值为 。,结合对偶节点的计算，可以看出 具有下述规律：如果某一节点上的加权系数为 ，则其对偶节点的加权系数必然是 ，而且,所以一对对偶节点可用下式计算,(361),(362),（,4,）重新排序,由蝶式流程图可见，如果序列,x(n,),是按顺序排列的，经过蝶式运算后，其变换序列,X(m,),是非顺序排列的，即乱序的；反之，如果,x(n,),是乱序的，那么，,X(m,),就是顺序的。因此，为了便于输出使用，最好加入重新排序程序，以便保证,x(n,),与它的变换系数,X(m,),的对应关系。具体排序方法如下：,（）将,r,位的二进制数比特倒转，即：,也就是,（）将最后一次迭代结果 中的序号数,k,写成二进制数，即,（）求出倒置后的二进制数代表的十进制数，就可以得到与,x,(,k,),相对应的,X,(,m,),的序号数。,例如：,N=8,的最后迭代结果：,x,3,(0)000,倒置,000,十进制0,）,x,3,(1)001,倒置,100,十进制（,4,）,x,3,(2)010,倒置,010,十进制（,2,）,x,3,(3)011,倒置,110,十进制（,6,）,x,3,(4)100,倒置,001,十进制（,1,）,x,3,(5)101,倒置,101,十进制（,5,）,x,3,(6)110,倒置,011,十进制（,3,）,x,3,(7)111,倒置,111,十进制（,7,）,1,6,二维离散傅里叶变换,一幅静止的数字图像可看做是二维数据阵列。因此，数字图像处理主要是二维数据处理。二维离散傅里叶变换的定义可用下面二式表示。正变换式为：,(363),反变换式为：,(364),在图像处理中，一般总是选择方形阵列，所以通常情况下总是 。因此，二维离散傅里叶变换多采用下面两式形式。,(365),式中符号 可称为空间频率。,(366),二维离散傅里叶变换的可分离性是显而易见。,(367),(368),这个性质可以使二维变换用两次一维变换实现,图,39,二维傅里叶变换的处理结果,