数字图像处理 第三章 图像变换课件.ppt

Slide 1,第3章 图像变换,Slide 2,内容提要,主要介绍图像处理中常用的二维离散变换的定义、性质、实现方法及应用。经典变换离散傅里叶变换（DFT）离散余弦变换（DCT）离散沃尔什-哈达玛变换（DWT）K-L变换（KLT）离散小波变换（DWT）及其应用,Slide 3,知识要点,余弦型变换：傅里叶变换和余弦变换。方波型变换：沃尔什-哈达玛变换。基于特征向量的变换：K-L变换。从哈尔变换、短时傅里叶变换到小波变换。各种变换的定义和有关快速算法及实现方法。,Slide 4,3.1 二维离散傅里叶变换（DFT）,3.1.1 二维连续傅里叶变换定义：设 f(x,y)是独立变量x和y 的函数，且在 上绝对可积，则定义积分 为二维连续函数 f(x,y)的傅里叶变换，并定义 为F(u,v)的反变换。f(x,y)和F(u,v)为傅里叶变换对。,Slide 5,【例3.1】求图3.1所示函数的傅里叶变换。,解：,图3.1 二维信号f(x,y),其幅度谱为,Slide 6,二维信号的频谱图,（a）信号的频谱图（b）图（a）的灰度图图3.2 信号的频谱图,Slide 7,3.1.2 二维离散傅里叶变换,尺寸为MN的离散图像函数的DFT,反变换可以通过对F(u,v)求IDFT获得,Slide 8,F(u,v)即为f(x,y)的频谱，通常是复数：,幅度谱,相位谱,Slide 9,DFT幅度谱的特点,频谱的直流成分说明在频谱原点的傅里叶变换F(0,0)等于图像的平均灰度级。幅度谱|F(u,v)|关于原点对称。图像f(x,y)平移后，幅度谱不发生变化，仅有相位发生变化。,Slide 10,3.1.3 二维离散傅里叶变换的性质,1变换可分离性二维DFT可以用两个可分离的一维DFT之积表示：,式中，,结论：（1）二维变换可以通过先进行行变换再进行列变换的两次一维变换来实现。（2）也可以通过先求列变换再求行变换得到二维傅里叶变换。,Slide 11,图3.3 用两次一维DFT计算二维DFT,Slide 12,2周期性、共轭对称性及频谱中心化,周期性和共轭对称性来了许多方便。首先来看一维的情况。设有一矩形函数,求出它的傅里叶变换：,Slide 13,在进行DFT之前用输入信号乘以（-1）x，便可以在一个周期的变换中求得一个完整的频谱。,（a）幅度谱（b）原点平移后的幅度谱 图3.4 频谱图,Slide 14,用(-1)x+y 乘以输入的图像函数，则有：,原点F(0,0)被设置在 u=M/2和v=N/2上。,如果是一幅图像，在原点的傅里叶变换F(0,0)等于图像的平均灰度级，也称作频率谱的直流成分。,Slide 15,3离散卷积定理,设f(x,y)和g(x,y)是大小分别为AB和CD的两个数组，则它们的离散卷积定义为,卷积定理,Slide 16,【例3.2】用MATLAB实现图像的傅里叶变换。,为了增强显示效果，用对数对频谱的幅度进行压缩，然后将频谱幅度的对数值用在010之间的值进行显示。【解】MATLAB程序如下：I=imread(pout.tif);%读入图像imshow(I);%显示图像F1=fft2(I);%计算二维傅里叶变换figure,imshow(log(abs(F1)+1),0 10);%显示对数变换后的频谱图F2=fftshift(F1);%将直流分量移到频谱图的中心figure,imshow(log(abs(F2)+1),0 10);%显示对数变换后中心化的频谱图,Slide 17,（a）原始图像(b)中心化前的频谱图(c)中心化后的频谱,图3.6 图像频谱的中心化,Slide 18,（a）原始图像（b）图像的频谱图（c）中心化的频谱图图3.7 傅里叶变换,Slide 19,1.4 快速傅里叶变换(FFT),随着计算机技术和数字电路的迅速发展，在信号处理中使用计算机和数字电路的趋势愈加明显。离散傅里叶变换已成为数字信号处理的重要工具。,Slide 20,快速傅里叶变换并不是一种新的变换，它是离散傅里叶变换的一种算法。这种方法是在分析离散傅里叶变换中的多余运算的基础上，进而消除这些重复工作的思想指导下得到的，所以在运算中大大节省了工作量，达到了快速运算的目的。,Slide 21,对于一个有限长序列，它的傅里叶变换由下式表示,(347),令,Slide 22,将正变换式（348）展开可得到如下算式,因此，傅里叶变换对可写成下式,(349）,(348),Slide 23,(350),Slide 24,上面的方程式（350）可以用矩阵来表示,(351),Slide 25,从上面的运算显然可以看出，要得到每一个频率分量，需进行N次乘法和N-1次加法运算。要完成整个变换需要 次乘法和N(N-1)次加法运算。当序列较长时，必然要花费大量的时间。,观察上述系数矩阵，发现 是以为N周期的，即,(352),Slide 26,例如，当N=8时，其周期性如图36所示。由于 所以，当N=8时，可得：,Slide 27,图 36 N=8 时 的周期性和对称性,Slide 28,可见，离散傅里叶变换中的乘法运算有许多重复内容。1965年库利图基提出把原始的N点序列依次分解成一系列短序列，然后，求出这些短序列的离散傅里叶变换，以此来减少乘法运算。,Slide 29,快速傅里叶变换简称FFT。算法根据分解的特点一般有两类，一类是按时间分解，一类是按频率分解。下面介绍一下的基本形式及运算蝶式流程图。,Slide 30,1.4.基数按时间分解的算法把 x(n)分成偶数点和奇数点,即:,这种算法的流程图如图37所示：图(a)输入为顺序的，运算结果是乱序的；图(b)输入为乱序的，运算结果是顺序的。,Slide 31,蝶式运算流程图(按时间分解),Slide 32,蝶式运算流程图(按时间分解),Slide 33,Slide 34,1.4.基数2按频率分解的算法,这种分解方法是直接把序列分为前 点和后 点两个序列，即,(355),Slide 35,Slide 36,1.5 用计算机实现快速付傅里叶变换,利用 FFT 蝶式流程图算法在计算机上实现快速傅里叶变换必须解决如下问题：1）、迭代次数 r 的确定；2）、对偶节点的计算；3）、加权系数 的计算；4）、重新排序问题。,Slide 37,(1)迭代次数r的确定,由蝶式流程图可见，迭代次数 r 与 N 有关。值可由下式确定,(359),式中 N 是变换序列的长度。对于前述基数2的蝶式流程图是2的整数次幂。例如，序列长度为8则要三次迭代，序列长度为16时就要4次迭代等等。,Slide 38,(2)对偶节点的计算,在流程图中把标有 的点称为节点。其中下标 l为列数，也就是第几次迭代，例如，则说明它是第一次迭代的结果。代表流程图中的行数，也就是序列的序号数。其中每一节点的值均是用前一节点对计算得来的。,Slide 39,在蝶式流程图中，把具有相同来源的一对节点叫做对偶节点。如:和 就是一对对偶节点，因为它们均来源于 x(0)和 x(4)。对偶节点的计算也就是求出在每次迭代中对偶节点的间隔或者节距。,Slide 40,由流程图可见，第一次迭代的节距为，第二次迭代的节距为，第三次迭代的节距为 等等。由以上分析可得到如下对偶节点的计算方法。,Slide 41,如果某一节点为，那么，它的对偶节点为,式中 l 是表明第几次迭代的数字，k 是序列的序号数，N 是序列长度。,(360),Slide 42,例：如果序列长度N=8，求 的对偶节点。,可利用式（360）计算，得,则,其正确性不难由流程图来验证。,Slide 43,（3）加权系数 的计算,的计算主要是确定 P值。P 值可用下述方法求得。,(1)把k值写成r位的二进制数（k 是序列的序号数，r 是迭代次数）；,Slide 44,（）把这个二进制数右移 r-l 位，并把左边的空位补零（结果仍为 r 位）；（）把这个右移后的二进制数进行比特倒转；（）把这比特倒转后的二进制数翻成十进制数就得到p值。,Slide 45,例：求 的加 权系数。,由 和 可知:k=2，l=2，n=8，则,（）因为k=2，所以写成二进制数为010；（）r-l=3-2=1，把010右移一位得到001；,Slide 46,（）把001做位序颠倒，即做比特倒转，得到100；（）把100译成十进制数，得到4，所以 P=4，的加权值为。,Slide 47,结合对偶节点的计算，可以看出 具有下述规律：如果某一节点上的加权系数为，则其对偶节点的加权系数必然是，而且,Slide 48,所以一对对偶节点可用下式计算,(361),(362),Slide 49,（4）重新排序,由蝶式流程图可见，如果序列 x(n)是按顺序排列的，经过蝶式运算后，其变换序列 X(m)是非顺序排列的，即乱序的；反之，如果 x(n)是乱序的，那么，X(m)就是顺序的。因此，为了便于输出使用，最好加入重新排序程序，以便保证 x(n)与它的变换系数 X(m)的对应关系。具体排序方法如下：,Slide 50,（）将r位的二进制数比特倒转，即：,也就是,（）将最后一次迭代结果 中的序号数k写成二进制数，即,Slide 51,（）求出倒置后的二进制数代表的十进制数，就可以得到与 x(k)相对应的 X(m)的序号数。,Slide 52,例如：N=8 的最后迭代结果：x3(0)000倒置000十进制（0）x3(1)001倒置100十进制（4）x3(2)010倒置010十进制（2）x3(3)011倒置110十进制（6）x3(4)100倒置001十进制（1）x3(5)101倒置101十进制（5）x3(6)110倒置011十进制（3）x3(7)111倒置111十进制（7）,Slide 53,53,Matlab实现,fft函数 一维DFT fft2函数 二维DFT fftn函数 N维DFT ifft函数 一维IDFT ifft2函数 二维IDFT ifftn函数 N维IDFT,快速傅里叶变换函数,Slide 54,54,Matlab实现,例,简单图像,傅里叶变换谱,对数傅里叶变换谱,傅里叶变换中心谱,Slide 55,55,Matlab实现,例,风景图像,傅里叶变换中心谱,Slide 56,3.2 二维离散余弦变换（DCT）,任何实对称函数的傅里叶变换中只含余弦项，余弦变换是傅里叶变换的特例，余弦变换是简化DFT的重要方法。3.2.1 一维离散余弦变换将一个信号通过对折延拓成实偶函数，然后进行傅里叶变换，我们就可用2N点的DFT来产生N点的DCT。1以x=-1/2为对称轴折叠原来的实序列f(n)得：,Slide 57,图3.8 延拓示意图,2以2N为周期将其周期延拓，其中f（0）f（1），f（N1）f（N）,fc(2N n 1)=fc(n),Slide 58,3对0到2N1的2N个点的离散周期序列 作DFT，得,令i2Nm1，则上式为,Slide 59,保证变换基的规范正交性，引入常量，定义：,F(k)C(k),C(k)=,其中,DCT逆变换为,Slide 60,3.2.2 二维离散余弦变换,正变换：逆变换：,Slide 61,3.2.3 二维DCT的应用,典型应用是对静止图像和运动图像进行性能优良的有损数据压缩。在静止图像编码标准JPEG、运动图像编码标准MJPEG和MPEG等标准中都使用了88块的离散余弦变换，并将结果进行量化之后进行熵编码。DCT具有很强的能量集中在频谱的低频部分的特性，而且当信号具有接近马尔可夫过程的统计特性时，DCT的去相关性接近于具有最优去相关性的K-L变换的性能。,Slide 62,【例3.3】应用MATLAB实现图像的DCT变换。,【解】MATLAB程序如下：I=imread(saturn.tif);subplot(1,2,1),imshow(I);%显示原图像C1=dct2(I);%对图像做DCT变换C2=fftshift(F1);%将直流分量移到频谱图的中心subplot(1,2,2),imshow(log(abs(C2)+1,0 10);%显示DCT变换结果,Slide 63,图3.10 离散余弦变换,（a）原始图像（b）DCT系数,Slide 64,3.3 二维离散沃尔什-哈达玛变换（DHT）,前面的变换是余弦型变换，基底函数选用的是余弦型。图像处理中有些变换常常选用方波信号或者它的变形。沃尔什（Walsh）变换。沃尔什函数是一组矩形波，其取值为1和-1，便于计算机运算。函数有三种排列或编号方式，以哈达玛排列最便于快速计算。采用哈达玛排列的沃尔什函数进行的变换称为沃尔什-哈达玛变换，简称WHT或直称哈达玛变换。,Slide 65,3.3.1 沃尔什变换,沃尔什函数系函数值仅取+1和1两值的非正弦型的标准正交完备函数系。由于二值正交函数与数字逻辑中的两个状态相对应，所以非常便于计算机和数字信号处理器运算。,Slide 66,图3.11 沃尔什函数系的前10个函数,Slide 67,沃尔什函数有三种排列或编号方式,列率排列、佩利（Paley）排列和哈达玛（Hadamard）排列。沃尔什变换的排列方式为列率排列。与正弦波频率相对应，非正弦波形可用列率描述。列率表示某种函数在单位区间上函数值为零的零点个数之半。,Slide 68,一维沃尔什变换核g(x,u),设N=2n，变换核为,bk(z)代表z的二进制表示的第k位值。核是一个对称阵列，其行和列是正交的。,Slide 69,一维沃尔什变换,正变换：逆变换：,Slide 70,二维沃尔什变换,正变换：逆变换：,Slide 71,【例3.5】求图像 f 的DWT，并反求 f。,【解】W=G f G，采用MATLAB程序求解W。f=2 5 5 2;3 3 3 3;3 3 3 3;2 5 5 1;G=1 1 1 1;1 1-1-1;1-1-1 1;1-1 1-1;W=(1/16)*G*f*G,Slide 72,运行结果为W=3.18750.0625-0.8125 0.0625 0.0625-0.0625 0.0625-0.0625 0.18750.0625-0.8125 0.0625 0.0625-0.0625 0.0625-0.0625,Slide 73,反求 f 的程序如下：W=3.1875 0.0625-0.8125 0.0625;0.0625-0.0625 0.0625-0.0625;0.1875 0.0625-0.8125 0.0625;0.0625-0.0625 0.0625-0.0625G=1 1 1 1;1 1-1-1;1-1-1 1;1-1 1-1;f=G*W*G,Slide 74,运行结果为f=2 5 5 2 3 3 3 3 3 3 3 3 2 5 5 1,Slide 75,3.3.2 哈达玛变换,哈达玛矩阵：元素仅由1和1组成的正交方阵。正交方阵：指它的任意两行（或两列）都彼此正交，或者说它们对应元素之和为零。哈达玛变换要求图像的大小为N2n。一维哈达玛变换核为 其中，bk(z)代表z的二进制表示的第k位值。,Slide 76,二维哈达玛正、逆变换具有相同形式,正反变换都可通过两个一维变换实现。高阶哈达玛矩阵可以通过如下方法求得：N8的哈达玛矩阵为,Slide 77,一维、二维哈达玛正、逆变换,一维哈达玛正变换 一维哈达玛逆变换二维哈达玛正变换二维哈达玛逆变换,Slide 78,3.4 卡胡南-列夫变换（K-L变换）,Kahunen-Loeve变换是在均方意义下的最佳变换。优点：能够完全去除原信号中的相关性，因而具有非常重要的理论意义。缺点：基函数取决于待变换图像的协方差矩阵，因而基函数的形式是不定的，且计算量很大。,Slide 79,设原图像为X，采用KLT恢复的图像，则和原图像X具有最小的均方误差，即,对第i次获得的图像fi(x,y)可以用N2维向量Xi表示：,Slide 80,Cx是一个N2N2的实对称矩阵。令i和ai（i=1,2,N2）分别为Cx的第i个特征值和特征向量，其特征向量构成的矩阵是一个正交矩阵,Slide 81,ATCxA=A1CxA=（3.51）为Cx的特征值构成的对角线矩阵。K-L变换选取一个上述的正交变换A，使得变换后的图像Y满足 Y=A(X mx)（3.52）优点：能够完全去除原信号中的相关性，因而具有重要的理论意义。缺点：计算量很大。,Slide 82,3.5 二维离散小波变换,小波分析是20世纪80年代开始逐渐发展成熟的应用数学的一个分支。主要特点：对时间（二维信号为空间）-频率的双重分析和多分辨率分析能力。被誉为“数学显微镜”，在信号和图像处理等领域具有重要的应用价值。,Slide 83,3.5.1 小波分析的思想来源,哈尔提出了一种正交归一化函数系，以其作为正交规范基的哈尔变换收敛均匀而迅速，在图像信息压缩和特征编码等方面获得应用。哈尔变换特点：（1）具有尺度和位移两个特性；（2）变换范围窄；（3）变换特性与图像边界的特性十分接近。,Slide 84,图3.12 Haar函数系的前几个函数波形,Slide 85,窗口傅里叶变换（WFT）,信号f(x)的窗口傅里叶变换定义为,WFT的重构公式为,常见的窗函数具有相对短的时间窗宽，例如可选为高斯函数，所以WFT也称为短时傅里叶变换（STFT）。,Slide 86,WFT的不足,窗口傅里叶变换是一种大小及形状均固定的时频化分析。实际信号进行时间和频率分析时，分辨率往往是相对的，即反映信号高频成分需要较高的时间分辨率，因此窗函数宽度应该窄一些，而反映低频成分则需要较高的频率分辨率，窗函数宽度应该宽一些。窗口傅里叶变换不能满足上述要求。,Slide 87,3.5.2 连续小波变换,小波变换的窗口具有大小（面积）固定但形状可改变的特点，能满足上述时-频局部化分析的要求。按如下方式生成的函数族为连续小波（分析小波）：,(x)称为基本小波或母波a称为伸缩因子，b为平移因子。母波可由平移与尺度变换构造小波基函数。,Slide 88,图3.13 小波函数的平移与扩展,Slide 89,信号的连续小波变换,正变换：反变换：,Slide 90,3.5.3 一维离散小波变换,把连续小波变换离散化更有利于实际应用。对a和b按如下规律取样：其中；，得离散小波：,离散小波变换和逆变换为,Slide 91,3.5.4 二维离散小波变换,信号f(x,y)的连续小波变换Wf(a,bx,by)为,由Wf(a,bx,by)重构f(x,y)的小波逆变换为,定义二维离散小波变换逼近，并采用Mallat二维快速算法求解。与DFT类似，可分离二维小波变换最终可转化为两次一维小波变换。,Slide 92,图3.14 可分离二维小波变换的频率域分解,（a）1层分解（b）2层分解（c）3层分解,Slide 93,重构算法按相反的步骤进行,这样就构成了2D DWT的金字塔结构。由于小波变换的理论和算法比较复杂，从应用的角度看，读者可以将注意力集中在用MATLAB对图像进行小波变换和重构的实现过程中。,Slide 94,【例3.6】对图像实现小波变换,bior3.7是双正交样条小波对应的滤波器。图像：wbarb.mat。【解】MATLAB程序如下：load wbarb;%从磁盘调入磁盘文件wbarb.matimage(X);%将矩阵X显示为图像.colormap(map);%配合函数image()画出连续的灰度图cA1,cH1,cV1,cD1=dwt2(X,bior3.7);%对X进行DWT，bior3.7是双正交样条小波对应的滤波器A1=upcoef2(a,cA1,bior3.7,1);H1=upcoef2(h,cV1,bior3.7,1);V1=upcoef2(v,cV1,bior3.7,1);D1=upcoef2(d,cD1,bior3.7,1);,Slide 95,figure;colormap(map);subplot(2,2,1);image(wcodemat(A1,180);title(Approximation A1)subplot(2,2,2);image(wcodemat(H1,255);title(Horizontal Detail H1)subplot(2,2,3);image(wcodemat(V1,255);title(Vertical Detail V1)subplot(2,2,4);image(wcodemat(D1,255);title(Diagonal Detail D1)Y=2.0*IDWT2(A1,H1,V1,D1,bior3.7);Y=imresize(Y,0.5);figure;image(Y);colormap(map);,Slide 96,图3.15 一层小波变换,（a）原图像（b）逆变换后的图像,Slide 97,图3.15 一层小波变换,（c）一层小波变换的4个分量,Slide 98,本章小结,图像处理可以直接在空间域进行，也可以通过变换的手段达到更好的效果。图像变换是图像处理中常用的有效手段，对实现某些图像处理和后期的图像分析起着十分重要的作用。,Slide 99,为了达到图像处理、分析、识别、传输和存储等目的，图像变换一般为正交变换。正交变换可以显著地减少图像数据的相关性，可以实现用较少的数据量表示原始图像及其特征。,Slide 100,针对图像处理中常用的变换进行了详细的介绍，特别分析了小波变换的思想和实现方法。重点是傅里叶变换、离散余弦变换，难点是小波变换。,