第3章图象变换复习课程课件

第3章图象变换什么是图像变换将图像看成是线性叠加系统图像在空域上相关性很强图像变换是将图像从空域变换到其它域如频域的数学变换常用的变换：傅立叶变换、离散余弦变换、Walsh变换、Hadamard变换、小波变换、离散K-L变换连续函数集合的正交性正交函数集合当C=1时，称集合为归一化正交函数集合 正交函数集合的完备性若f(x)是定义在t0和t0+T区间的实值信号，平方可积。可以表示为：对任意小的0，存在充分大的N，其中，则称函数U集合是完备的。离散情况n个正交向量当C=1时，称归一化正交 满足：一维正交变换对于一向量f，用上述正交矩阵进行运算：g=Af若要恢复f，则以上过程称为正交变换。酉变换若A为复数矩阵，正交的条件为：其中A*为A的复数共轭矩阵，满足这个条件的矩阵为酉矩阵酉矩阵。对于任意向量f的运算称为酉变换酉变换：酉变换、正交变换与信号分析正交变换是酉变换的特例它们都可以用于信号分析用于信号分析的基函数集合和正交矩阵都应满足正交性和完备性二维酉变换 NN二维函数可以类似于一维用正交序列展开和恢复正变换核反变换核变换核的可分离性其中au(x),u=0,1,N-1,bv(y),v=0,1,N-1为一维完备正交基向量的集合。用矩阵表示：A=a(u,x)，B=b(v,y)通常选择A=B。二维酉变换A=B时，二维酉变换正变换表示为用矩阵表示：F=AfAT类似的，对于MN的二维函数f(x,y)基图像反变换看成是基图像F(u,v)权因子图像f(x,y)可以用N2个基图像的加权和来表示酉变换的性质1.酉矩阵是正交阵2.AA*T=A*TA=INN3.2.A为酉阵，则A-1和AT都是酉阵4.3.酉变换是能量保持的变换5.对于一维酉变换F=Af,有|F|=|f|6.二维情况下，则有：酉变换的性质(2)设f(x,y)的均值和协方差为f和f4.均值和方差则F(u,v)的均值为：则F(u,v)的协方差为：酉变换的性质(3)5.其他性质：(1)A为酉阵，则其行列式值|A|=1(2)若a为向量，则作酉变换后向量模保持不变：b=Aa，则|b|=|a|。傅里叶变换及性质傅里叶变换及性质快速傅里叶变换快速傅里叶变换沃尔什变换沃尔什变换(Walsh)(Walsh)哈达玛变换哈达玛变换(Hadamard)(Hadamard)离散余弦变换离散余弦变换(Discrete Cosine(Discrete Cosine Transform)Transform)哈尔变换哈尔变换(Harr)(Harr)斜变换斜变换(Slant)(Slant)霍特林霍特林(Hotelling)(Hotelling)变换变换主要内容：主要内容：3.1 傅里叶变换傅里叶变换及性质及性质3.1.1 3.1.1 背景背景 法国数学家傅里叶生于法国数学家傅里叶生于17681768年，他被世年，他被世人铭记的最大贡献记载在人铭记的最大贡献记载在18701870年的传记中和年的传记中和后来出版于后来出版于18221822年的年的“La Thorie“La Thorie Analitique”Analitique”（热分析理论）一书中。此（热分析理论）一书中。此书由书由FreemanFreeman（参见（参见Freeman1878Freeman1878）在）在5555年年后翻译为英文。后翻译为英文。我们现在认为理所应当，但在它第一次我们现在认为理所应当，但在它第一次出现的时候，这个革命性的概念被全世界的出现的时候，这个革命性的概念被全世界的数学家数学家“纠正纠正”了一个世纪。了一个世纪。傅里叶在这个特殊领域的贡献是他指出傅里叶在这个特殊领域的贡献是他指出任何周期函数都可以表示为不同频率的正弦任何周期函数都可以表示为不同频率的正弦和和/或余弦和的形式，每个正弦和或余弦和的形式，每个正弦和/或余弦和或余弦和乘以不同的系数（现在称为傅里叶级数）。乘以不同的系数（现在称为傅里叶级数）。无论函数有多么复杂，只要它是周期的，并无论函数有多么复杂，只要它是周期的，并且满足某些软的数学条件，都可以用这样的且满足某些软的数学条件，都可以用这样的和来表示。和来表示。在那时，在数学思想中函数的规律性是占在那时，在数学思想中函数的规律性是占主导的。基于这样的传统思想，复杂函数主导的。基于这样的传统思想，复杂函数可以由简单的正弦和余弦之和来表示的概可以由简单的正弦和余弦之和来表示的概念根本不直观念根本不直观(如图如图3.13.1所示所示)，所以傅里，所以傅里叶的想法遭到怀疑是不足为奇的。叶的想法遭到怀疑是不足为奇的。甚至非周期的函数（但是这些领域是在曲甚至非周期的函数（但是这些领域是在曲线是有限的情况下）也可以用正弦和线是有限的情况下）也可以用正弦和/或余弦乘或余弦乘以加权函数的积分来表示。在这种情况下的公以加权函数的积分来表示。在这种情况下的公式就是傅里叶变换，它的应用在大多数实际应式就是傅里叶变换，它的应用在大多数实际应用中比傅里叶级数更广泛。用中比傅里叶级数更广泛。用傅里叶级数或变换表示的函数特征可用傅里叶级数或变换表示的函数特征可以完全通过傅里叶反过程来重建，不丢失任何以完全通过傅里叶反过程来重建，不丢失任何信息。这是这些表示法的最重要特征之一，因信息。这是这些表示法的最重要特征之一，因为它可以使我们工作于为它可以使我们工作于“频率域频率域”，而且在转，而且在转换回函数的原始域时不丢失任何信息。换回函数的原始域时不丢失任何信息。总之总之,傅里叶级数和变换是解决实际问题傅里叶级数和变换是解决实际问题的工具，它被广泛地使用并作为基础工具学习。的工具，它被广泛地使用并作为基础工具学习。傅里叶最初想法的应用是在热扩散领域，人们傅里叶最初想法的应用是在热扩散领域，人们考虑用微分方程的公式表示热流动，用这种方考虑用微分方程的公式表示热流动，用这种方法第一次获得了结论。法第一次获得了结论。在过去的一个世纪里，尤其是后在过去的一个世纪里，尤其是后5050年，年，傅里叶的思想使整个工业和学术界都空前繁傅里叶的思想使整个工业和学术界都空前繁荣。在荣。在2020世纪世纪5050年代后期，数字计算的出现年代后期，数字计算的出现和快速傅里叶变换算法的和快速傅里叶变换算法的 发明发明 在信号处理在信号处理领域产生了巨大变革。这两个核心技术第一领域产生了巨大变革。这两个核心技术第一次允许对人类本身的特殊信号和工业的重要次允许对人类本身的特殊信号和工业的重要信号（从医学监视器和扫描仪到现代电子通信号（从医学监视器和扫描仪到现代电子通信），进行实际处理和有意义的解释。信），进行实际处理和有意义的解释。这里仅处理有限域内的函数（图像），这里仅处理有限域内的函数（图像），所以傅里叶变换是我们感兴趣的工具。在所以傅里叶变换是我们感兴趣的工具。在以下各节的内容中将介绍傅里叶变换和频以下各节的内容中将介绍傅里叶变换和频率域。它显示出傅里叶技术提供了一个有率域。它显示出傅里叶技术提供了一个有意义的和实际的研究及实现图像增强的主意义的和实际的研究及实现图像增强的主要途径。要途径。3.1.2 一维连续傅立叶变换一维连续傅立叶变换1、变换、变换例例3-1：为下图所示的简单函数：为下图所示的简单函数f(x)，求其傅立，求其傅立叶变换叶变换F(u)。xfXA例例3-2：对高斯函数：对高斯函数G(t)，求其傅立叶变换，求其傅立叶变换F(u)。解：解：高斯函数的傅立叶变换同样是高斯函数。高斯函数的傅立叶变换同样是高斯函数。请课后练习!2、加快运算、加快运算3、傅立叶变换性质、傅立叶变换性质1）加法定理）加法定理时域或空域内的相加对应于频域内的相加。时域或空域内的相加对应于频域内的相加。2）位移定理）位移定理函数位移不改变傅立叶变换的幅值。函数位移不改变傅立叶变换的幅值。3）卷积定理）卷积定理时域（或空域）中的卷积等价于频域的乘积时域（或空域）中的卷积等价于频域的乘积两个函数的卷积定义为：两个函数的卷积定义为：4）相似性定理）相似性定理描述函数自变量尺度变化对其傅立叶变换的作用。描述函数自变量尺度变化对其傅立叶变换的作用。3.1.3 二维连续傅立叶变换二维连续傅立叶变换功率谱、频谱密度例例3-3：为下图所示的二维函数：为下图所示的二维函数f(x,y)，求其傅立叶变换，求其傅立叶变换F(u,v)。xyzA3.1.4 一维离散傅立叶变换一维离散傅立叶变换1、一维离散傅立叶变换对、一维离散傅立叶变换对注意注意:1/N:1/N并没有固定位置并没有固定位置.2、一维、一维DFT的矩阵表示法的矩阵表示法N=8时时W各元素各元素3、常用一维、常用一维DFT的几个性质的几个性质3.1.5 3.1.5 二维离散傅立叶变换二维离散傅立叶变换1、二维离散傅立叶变换的性质二维离散傅立叶变换的性质（1 1）分离性）分离性二维离散傅立叶变换二维离散傅立叶变换DFT可分离性的基本可分离性的基本思想是：思想是：二维二维DFT可分离为两次一维可分离为两次一维DFT应用：应用：二维快速傅立叶算法二维快速傅立叶算法FFT，是通过计，是通过计算两次一维算两次一维FFT实现的实现的先进行列变换，然后进行行变换傅立叶变换分离傅立叶变换分离分离过程先对列做变换先对列做变换再对行做变换再对行做变换 平移性特性表明：平移性特性表明：输入信号与一个指数项相乘相当于把变换输入信号与一个指数项相乘相当于把变换后的频域中心平移到新的位置；类似频率函数后的频域中心平移到新的位置；类似频率函数F(u,v)与一个指数项相乘相当于把其反变换的与一个指数项相乘相当于把其反变换的空域中心平移到新的位置空域中心平移到新的位置（2 2）平移性特性平移性特性（3 3）周期性和共轭对称性周期性和共轭对称性周期性周期性（共轭对称性共轭对称性)（4）旋转不变性）旋转不变性 如果如果f(x,y)f(x,y)旋转了一个角度旋转了一个角度 ，那么，那么f(x,y)f(x,y)旋转后的图象的傅立叶变换也旋转了相旋转后的图象的傅立叶变换也旋转了相同的角度同的角度 。线性的描述：傅立叶变换是线性系统、函数和线性的描述：傅立叶变换是线性系统、函数和的傅立叶变换是可分离的的傅立叶变换是可分离的设：设：f(x,y)f(x,y)的傅立叶变换为的傅立叶变换为Ff(x,y)Ff(x,y)g(x,y)g(x,y)的傅立叶变换为的傅立叶变换为Fg(x,y)Fg(x,y)有：有：Ff(x,y)+g(x,y)=Ff(x,y)+Fg(x,y)Ff(x,y)+g(x,y)=Ff(x,y)+Fg(x,y)（5）线性特性）线性特性（6）相似性（尺度变换）相似性（尺度变换）（7）微分性质）微分性质（8）平均值）平均值函数的傅立叶变换在（函数的傅立叶变换在（0 0，0 0）处的值为）处的值为因此有：因此有：离散函数的均值与该函数傅立叶变换在离散函数的均值与该函数傅立叶变换在(0,0)(0,0)点的值之关系点的值之关系（9）卷积）卷积两个两个2-D2-D函数的卷积定义为：函数的卷积定义为：（10）相关相关2个个1-D连续函数的相关定义为：连续函数的相关定义为：定义定义1-D离散相关为：离散相关为：2-D连续和离散的相关分别定义为：连续和离散的相关分别定义为：相关定理相关定理3.1.6 3.1.6 由采样重建图像由采样重建图像问题：对一幅连续图像采多少个样本才能由问题：对一幅连续图像采多少个样本才能由这些采样完全重建这幅图像？这些采样完全重建这幅图像？3.2 3.2 快速快速FourierFourier变换变换问题的提出解决问题的思路与方法 基2时间抽取FFT算法基2时间抽取FFT算法的计算复杂度基2时间抽取FFT算法流图规律基2频率抽取FFT算法问题的提出问题的提出4点序列点序列2，3，3，2 DFT的计算复杂度的计算复杂度复数加法复数加法N(N-1)复数乘法复数乘法如如何何提提高高DFT的的运运算算效效率率?N 2解决问题的思路解决问题的思路1.将长序列DFT分解为短序列的DFT2.利用旋转因子 的周期性周期性、对称性对称性、可约性可约性。1)周期性周期性2)对称性对称性3)可约性可约性快速快速FourierFourier变换算法原理变换算法原理DFT的定义如下：的定义如下：上式可写成：上式可写成：设设N为为2的正整数次幂，即的正整数次幂，即令令M为正整数，且为正整数，且（可约性）（可约性）同理，由同理，由可得可得(1)(2)(1)和和(2)表明，表明，1个个N点的变换可通过将原始表点的变换可通过将原始表达式分成两半来计算。达式分成两半来计算。(1)式计算前一半点的变换，式计算前一半点的变换，(2)式计算后一半点的变换。式计算后一半点的变换。解决问题的方法解决问题的方法将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。基基2时间抽取时间抽取(Decimation in time)FFT算法算法基基2频率抽取频率抽取(Decimation in frequency)FFT算算法法基2时间抽取FFT算法流图N=24点基2时间抽取FFT算法流图2点DFT2点DFT-1-1-1-14点基2时间抽取FFT算法流图-1-1-1-18点基点基2时间抽取时间抽取FFT算法流图算法流图4点DFT4点DFTf0f2f4f6f1f3f5f7X10X11X12X13X20X21X22X23F 0F 1F 2F 3F 4F 5F 6F 7-1-1-1-14点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18点基2时间抽取FFT算法流图基基2 2时间抽取时间抽取FFTFFT算法算法第一级第一级第二级第二级第三级第三级算法的计算复杂度算法的计算复杂度复乘次数复乘次数NN 2用计算机实现快速用计算机实现快速FourierFourier变换变换需要解决如下需要解决如下4个问题：个问题：1、迭代次数、迭代次数r的确定的确定2、对偶节点的计算、对偶节点的计算3、加权系数、加权系数 的计算的计算4、重新排序问题、重新排序问题1、迭代次数、迭代次数r的确定的确定N是变换序列的长度。是变换序列的长度。2、对偶节点的计算、对偶节点的计算3、加权系数、加权系数 的计算的计算3)把这个右移后的二进制数进行比特倒转，并转成十把这个右移后的二进制数进行比特倒转，并转成十进制数，就得到进制数，就得到p的值。的值。4、重新排序、重新排序1）将最后一次迭代结果）将最后一次迭代结果 中的序号数中的序号数 写成二进写成二进制数，即制数，即2)将将r位的二进制数比特倒转，即位的二进制数比特倒转，即也就是也就是3)求出二进制数的十进制表示，就可得到求出二进制数的十进制表示，就可得到m。基基2频率抽取频率抽取FFT算法算法3NW-1-12NW-1-11NW-1-10NW-1-1x0 x4x1x5x2x6x3x74点点DFTX0X6X2X44点点DFTX1X3X5X7X0X6X4X2X1X5X3X70NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2点点DFT-1-1-1-12NW0NW-1-1-1-12点点DFT2点点DFT2点点DFT0NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2NW0NWX0X6X4X2X1X5X3X70NW0NW0NW0NW-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1上机实习题上机实习题1、编写二维数字图象的离散傅立叶变换程序。、编写二维数字图象的离散傅立叶变换程序。2、编写、编写 二维数字图象的快速傅立叶变换程二维数字图象的快速傅立叶变换程序。序。3、采用上题编写的程序，任选一幅数字图象，显示其、采用上题编写的程序，任选一幅数字图象，显示其频谱图。频谱图。3.3 3.3 可分离变换可分离变换1D1D可分离变换的一般形式可表示为：可分离变换的一般形式可表示为：的变换的变换正向变换核正向变换核反变换可表示为：反变换可表示为：反向变换核反向变换核对于对于2D2D情况，正变换与反变换分别表示为情况，正变换与反变换分别表示为其中其中 与与 分别称为正向变分别称为正向变换核与反向变换核。它们与换核与反向变换核。它们与 和和 无关，只依无关，只依赖于赖于如果下式成立如果下式成立,则称正向变换核是可分离的。则称正向变换核是可分离的。如果下式成立，则变换核是对称的。如果下式成立，则变换核是对称的。变换的矩阵表示变换的矩阵表示 对于具有可分离特性变换核的对于具有可分离特性变换核的2D变换可分变换可分解成两个解成两个1D变换。变换。列变换列变换行变换行变换 当变换核是可分离和对称时，正向变换可表为当变换核是可分离和对称时，正向变换可表为矩阵形式矩阵形式其中，其中，F F为为NxNNxN图像矩阵，图像矩阵，A A为为NxNNxN的对称变换矩阵，的对称变换矩阵，其元素为其元素为 ，T T为为NxNNxN的变换结果的变换结果。反变换反变换设设B为反变换矩阵，为反变换矩阵，如果如果 ，则，则图像完全可由其变换恢复。如果图像完全可由其变换恢复。如果 ，可得到可得到F的一个近似，的一个近似，如果变换矩阵是正交的，则称为图像的正交如果变换矩阵是正交的，则称为图像的正交变换。变换。一、一、Walsh变换变换当当N N2 2n n时，取如下变换核时时，取如下变换核时函数函数f(x)f(x)的离散的离散WalshWalsh变换变换W(u)W(u)为为WalshWalsh变换核元素的取值为变换核元素的取值为+1,-1+1,-1，变换矩阵，变换矩阵为对称的正交变换矩阵。为对称的正交变换矩阵。WalshWalsh函数是美国数学家函数是美国数学家WalshWalsh在在19231923年提出的，年提出的，与与FourierFourier变换相比，变换相比，Walsh Walsh变换的主要优点在变换的主要优点在于存储空间少和运算速度高。于存储空间少和运算速度高。沃尔什反变换沃尔什反变换N8时，沃尔什变换核为时，沃尔什变换核为1D Walsh正变换正变换和反变换只差一和反变换只差一个常数项个常数项2D沃尔什正变换核与反变换核相同沃尔什正变换核与反变换核相同2D沃尔什正变换与反变换沃尔什正变换与反变换2D沃尔什正变换与反变换核都是可分离的和沃尔什正变换与反变换核都是可分离的和对称的，有类似对称的，有类似FFT的快速算法。的快速算法。N4，沃尔什变换的基函数，沃尔什变换的基函数uvxy二、二、Hadamard变换变换1D哈达玛变换的变换核哈达玛变换的变换核1D哈达玛变换哈达玛变换2D哈达玛变换核哈达玛变换核2D哈达玛正变换与反变换核可分离的和对称的，哈达玛正变换与反变换核可分离的和对称的，也有快速算法也有快速算法 Hadamard变换的核矩阵中只有+1和-1元素。它要求图象的大小是 ，。对于 的大小，核矩阵为：类推有：例如：N=8时，有：每一行的符号的变化次数称作这个行的列率。HadamardHadamard变换与变换与WalshWalsh变换每个元素的取值都变换每个元素的取值都是是+1+1或或-1-1，其行与列的排列次序不同。，其行与列的排列次序不同。WalshWalsh变换对任何正整数都成立，变换对任何正整数都成立，Hadamard Hadamard变换对变换对于于2 2整次幂与小于整次幂与小于200200的正整数成立。的正整数成立。uvyxN=4N=4时经过排序时经过排序的的HadamardHadamard变变换基函数图换基函数图三、离散余弦变换（DCT）傅立叶变换的一个最大的问题是：它的参数都是复数，在数据的描述上相当于实数的两倍。为此，我们希望有一种能够达到相同功能的变换。在此期望下，产生了DCT变换。余弦变换当f(x)或f(x,y)为偶函数时，变换的计算公式只有余弦项。一个任意函数采样从0,1,2,N-1，若向负方向折叠形成2N采样的偶函数，就可以进行2N的偶函数傅立叶变换。余弦变换是简化傅立叶变换的一种方法离散余弦变换（DCT）1D离散余弦变换离散余弦变换反变换反变换矩阵表示矩阵表示1D余弦变换的矩阵表示，N4余弦变换矩阵为正交矩阵AAI2D离散余弦变换离散余弦变换反变换反变换DCT变换的应用：余弦变换实际上是傅立叶变换的实数部分。余弦变换主要用于图象的压缩，如目前的国际压缩标准的JPEG格式中就用到了DCT变换。具体的做法与DFT相似。给高频系数大间隔量化，低频部分小间隔量化。四、四、Harr变换变换五、斜变换五、斜变换3.4 K-L变换变换设 是一幅 的图像。做一个向量为：是 的均值，是其协方差。A是由 的特征向量构成的正交矩阵。K-L正变换：K-L反变换：K-L变换的压缩原理：由于A是按照特征值的大小顺序排列的特征向量构成的变换阵，特征值小的部分对图像的影响不大。取最大的K个特征值所对应的特征向量构成的矩阵为变换阵 。有：K-L变换在遥感多光谱图像中的应用：实质上是利用了K-L变换的降维能力来进行压缩的。例如，一幅1000*1000的24通道的多光谱图象可以被看成106个24维随机向量集合。由于一幅多光谱图象的不同谱带间通常存在很大的相关性，所以24个特征值中有许多的值非常小。这就意味着一组24幅单色图可以仅用少量主分量图来表示。3.5 （奇异值分解）SVD变换设 的图像为给出一个酉变换的话：正变换：反变换：不妨假设 ，的秩为r。为的对称阵，为的对称阵。所以我们可以找到r 个非零特征值对应的特征向量ui和vi，满足下式：ui是M维向量，vi是N维向量。设ui是 的特征向量（M维），按下式得到N维向量vi。则vi是 的特征向量。所以就有：即：1。如果F存在一些为零（或很小的）特征值，对应的元素中较小的值，忽略它们可以用来实现“有损”压缩。精品课件精品课件！精品课件精品课件！2。由于至多只有r个非零元素，这样至少可以获得大于N倍的无损压缩，这一点是因为，对每一幅图象来说，U,和V是唯一的，对于一组类似的图象来说，也可以只（近似地）使用同一对U,V阵。（如：对于动态图象的相近时刻的图象组）此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢