K-L变换( Karhunen-Loeve Transform)是建立在统计特性基础上的一种变换,有的文献也称为霍特林(Hotelling)变换,因他在1933年最先给出将离散信号变换成一串不相关系数的方法。K-L变换的突出优点是相关性好,是均方误差(MSE,Mean Square Error)意义下的最佳变换,它在数据压缩技术中占有重要地位。 假定一幅N x N的数字图像通过某一信号通道传输M次,由于受随机噪音干扰和环境条件影响,接收到的图像实际上是一个受干扰的数字图像集合 对第i次获得的图像 fi(x,y) ,可用一个含 N2 个元素的向量 Xi 表示,即 该向量的第一组分量(N个元素)由图像fi(x,y) 的第一行像素组成,向量的第二组分量由图像 f i(x,y) 的第二行像素组成,依此类推。也可以按列的方式形成这种向量,方法类似。 X向量的协方差矩阵定义为: m f定义为: C f 和 m f 的表达式中,“ E ”是求期望。 对于M幅数字图像,平均值向量 m f 和协方差矩阵 C f可由下述方法近似求得: 可以看出, m f 是 N2 个元素的向量, C f 是 N2 x N2 的方阵。 根据线性代数理论,可以求出协方差矩阵的 N2 个特征向量和对应的特征值。假定 是按递减顺序排列的特征值,对应的特征向量 ei = 。 则K-L变换矩阵A定义为: 从而可得K-L变换的变换表达式为: 该变换式可理解为,由中心化图像向量 X - mx 与变换矩阵A相乘即得到变换后的图像向量Y。Y的组成方式与向量X相同。 K-L变换虽然具有MSE意义下的最佳性能,但需要先知道信源的协方差矩阵并求出特征值。求特征值与特征向量并不是一件容易的事,维数较高时甚至求不出来。即使能借助计算机求解,也很难满足实时处理的要求,而且从编码应用看还需要将这些信息传输给接收端。这些因素造成了K-L变换在工程实践中不能广泛使用。人们一方面继续寻求解特征值与特征向量的快速算法,另一方面则寻找一些虽不是“最佳”、但也有较好的去相关与能量集中的性能且容易实现的一些变换方法。而K-L变换就常常作为对这些变换性能的评价标准。 KL变换 Karhunen-Loeve 用子波域中部分KL变换来抑制噪声的方法 提高S/N 比是地震数据处理的主要任务。有时野外环境非常坏,例如,沙漠、沼泽地和黄土地区,以致记录器受到很严重的干扰,而接收不到反射波。为了获得高质量剖面,介绍了一种崭新的滤波法:WKL 法。该法是根据噪声(例如,地面波)的传播特点,利用子波的优点及部分KL变换。该法的依据是反射波和噪声的传播原则及其频率范围之差。合成数据和实际数据处理结果证明,该法要优于其它的方法,而且它能明显地增强S/N 比及能合理地消除噪声。1.K-L变换的定义 以矢量信号X的协方差矩阵Ф的归一化正交特征矢量q所构成的正交矩阵Q,来对该矢量信号X做正交变换Y=QX,则称此变换为K-L变换(K-LT或KLT),K-LT是Karhuner-Loeve变换的简称,有的文献资料也写作KLT。可见,要实现KLT,首先要从信号求出其协方差矩阵Ф,再由Ф求出正交矩阵Q。Ф的求法与自相关矩阵求法类似。2.K-L变换的特性 (1)去相关特性。 K-L变换是变换后的矢量信号Y的分量互不相关。 (2)能量集中性。 所谓能量集中性,是指对N维矢量信号进行K-L变换后,最大的方差见集中在前M个低次分量之中(M<N)。 (3)最佳特性。 K-L变换是在均方误差测度下,失真最小的一种变换,其失真为被略去的各分量之和。由于这一特性,K-L变换被称为最佳变换。许多其他变换都将K-L变换作为性能上比较的参考标准。 (4)无快速算法,且变换矩阵随不同的信号样值集合而不同。 这是K-L变换的一个缺点,是K-L变换实际应用中的一个很大障碍。 §4.6 基于Karhunen-Loeve变换的特征提取 K-L变换又称主分量分析,是一种正交变换,学过数学信号处理或数字图象处理的同学可能已经学过这种变换,K-L变换常用来作为数据压缩,这里我们用它作降维,学习这一节主要要掌握以下几个问题: 1.什么是正交变换,这是在数字信号处理或其它课学习过的内容,很重要。 2.K-L变换是一种最佳的正交变换,要弄清是什么意义的最佳,也就是说它最佳的定义。 3.K-L变换的性质。 4.K-L变换的重要应用。 4.6.1 Karhunen-Loeve变换 正交变换概念 变换是一种工具,它的用途归根结底是用来描述事物,特别是描述信号用的。例如我们看到一个复杂的时序信号,我们希望能够对它进行描述,特别是希望用一些经济有效的方式进行描述。描述事物的基本方法之一是将复杂的事物化成简单事物的组合, 或对其进行分解,分析其组成的成分。
4.6.1 Karhunen-Loeve变换 正交变换概念 变换是一种工具,它的用途归根结底是用来描述事物,特别是描述信号用的。例如我们看到一个复杂的时序信号,我们希望能够对它进行描述,特别是希望用一些经济有效的方式进行描述。描述事物的基本方法之一是将复杂的事物化成简单事物的组合, 或对其进行分解,分析其组成的成分。例如看一波形,我们希望知道它是快速变化的(高频),还是缓慢变化的(低频),或是一成不变的(常量)。如它既有快正变化的成分,又有缓慢变化的成分,又有常量部分,那么我们往往希望将它的成分析取出来。这时候我们就要用到变换。变换的实质是一套度量用的工具,例如用大尺子度量大的东西,用小尺子度量小的东西,在信号处理中用高频,低频或常量来衡量一个信号中的各种不同成分。对某一套完整的工具就称为某种变换,如富里叶变换就是用一套随时间正弦、余弦信号作为度量工具,这些正弦,余弦信号的频率是各不相同的,才能度量出信号中相应的不同频率成分。例如,补图4-1中的信号只有一个单一频率的简谐信号,而补图4-2(a)中信号就不是一个简谐波号所描述的,它起码可以分解成补图4-2中的两个成分,一是基波,另一是三次谐波。 | 补图 4-1
补图 4-2(a)
补图 4-2(b) | 由此可以看出,对事物可以有不同的描述方法,如补图4-2(a)是对信号的一种描述,而补图4-2(b)则利用成分分解,得到该事物的另一种描述。当将一事物从一种描述转换成另一种描述时,就要用不同的工具,因而每一套工具称为一种变换。 为了对复杂事物进行经济有效的描述,我们希望将其分解成相互独立的成分,譬如我们分析其快速变化的成分时,就希望它只不再混杂其它成分。用富里叶变换为例,希望它分析出某种频率的成分,就不要包含其它任何频率的成分。这就要求,作为变换的工具中的每个成分是相互独立的,用其中某一个工具就只能从信号中分析出一种成分,而分析不出其它成分。 用变换对信号进行分析,所使用的数学工具是点积。点积的实质就是两个信号中相同成分之间乘积之总和,补图4-3中列举了一些点积运算的例补图4-3(a)中是两个随时间连续变化的信号,它们之间的点积运算定义为
| 补图 4-3 (a)
补图 4-3 (b) | 在这里同一成分是指同一时刻t两个信号的值F(t)与G(t)。积分就是在整个时间域上求和。而补图4-3(b)中的向量A与B在一个二维空间定义,它们两者分别含有成分为(a1,a2)与(b1,b2),a1与b1是两者的同一种成分,a2与b2则是另一种成分。故它们的点积定义为a1b1+a2b2,在这种条件下就不需要积分,而只是简单求和。 点积运算的结果是一个数值,或大于零,小于零或等于零,等于零的情况在补图4-3(b)中出现在A与B之间夹角为90°的情况,这表明B中没有A的成分,A中也没有B的成分,因此又称相互正交。由此我们知道作为一种变换,如果这种变换中的每一种成分与其它成分都正交时,它们之间的关系就相互独立了,每一种成分的作用是其它成分所不能代替的。拿富里叶变换来说,频率为f的成分只能靠变换频率为f的成分去析取。另一方面也说明了这套变换必须是完备的,也就是它必须包含一切必要的成分,例如必须有基波的任何一次整数信频率的谐波,否则就会对信号分析不全面。 综合以上分析,我们可以将对这种变换的定义归为: 如果将这种变换中的每一成分,同一个向量ui表示,i是其下标,原理上可以到∞,则我们要求的正交变换可表示成: 这里ui与uj的点积采用了矩阵乘积的形式,此时其中一个向量要表示成转置形式,上式中要求uiTuj=1,是考虑到ui是作为度量事物的单位应用的,它本身的模应该为1,ui又称为某一个基。而被分解后的任何事物(在此指信号)可等成各种成分之和。故任一信号X可等成 (被4-1)其中ci是相应基ui的相应成分。 |
|
前面讨论了利用各种距离判据进行特征提取的方法,,这一节要讨论另一种特征提取方法,即基于Karhunen-Loeve变换原理的方法。这种方法也是以样本特征向量在特征空间分布为原始数据,通过实行Karhunen-Loeve变换,找到维数较少的组合特征,达到降维的目的。由于样本的描述都是离散的向量,因此我们只讨论Karhunen-Loeve变换(以后称K-L变换)的离散情况。 现在我们讨论第二个问题,即K-L变换的最佳是指什么含义,在这里我们讨论的是特征空间的降维,因此这个最佳是与降维联系起来的。对我们降维来说,原特征空间是D维的,现希望降至d维d<D。不失一般性,可以认为D为无限大的情况,并设原信号可用一组正交为换基ui表示,见(4-59)。现要求降维至d维,也就是说将d+1维以上的成分略去,显然原信号会因此受到一些损失,我们将其表示成(4-60)形式,而每个信号的损失则表示成X与之差。现在的问题是对我们讨论的问题,即给定一个训练样本集条件下要找一个好的正交变换,能使这种误差从总体上来说是最小。注意这里讲的是总体,这是因为降维以后,训练样本集中的每个样本数据都受到损失,要衡量的是总体效果。在这种情况下最常用的指标是均方误差最小,或称均方误差的期望值最小,这就是(4-61)式。这就是说要找的正交变换能使一组样本集的截均方误差的期望值为最小。 K-L变换是一种正交变换,即将一个向量X,在某一种坐标系统中的描述,转换成用另一种基向量组成的坐标系表示。这组基向量是正交的,其中每个坐标基向量用ui表示,j=1,…,∞,因此,一个向量X可表示成 (4-59) 对一向量或一向量空间进行正交变换,可采用多种不同的正交坐标系,关键在于使用正交变换要达到的目的,不同的要求使用不同的正交变换。这里要讨论的是,如果我们将由(4-59)表示的无限多维基向量坐标系统改成有限维坐标系近似,即 (4-60) 表示X的近似值或估计量,我们希望在同样维数条件下,使向量X的估计量误差最小。确切地说是使所引起的均方误差 (4-61) 为最小。K-L变换可以实现这个目的。 要找满足(4-61)式为最小是一个求极值的问题,求最佳的是正交变换的基ui,i=1,…∞。因此还要满足变换是正交归一这个条件,因此这是一个求条件极值的问题,一般方法是利用拉格朗日乘子法将条件数值转换成一个求无条件极值的问题,观察从(4-61)到(4-69)的过程而(4-62)则是对拉格朗日函数g(ui)求偏导而得出的结果。 至于对某一个数据X的相应cj值,可以通过X与每一个基uj的点积来计算。由于不同的基之间是相互正交的,这个点积值就是cj的值,即cj=ujTx(补4-2)如不明白可看讲义中的(4-65)与(4-66)如果我们要求一组系数cj,并将其表示成一个向量形式C=(c1,c2,……)T,则我们可以从(补4-2)得: (补4-3) 则U就是一个变换矩阵,其中每一行是某一个正交基向量的转置。由X计算C称为对X的分解。反过来,如果我们希望用C重构信号X,则根据(被4-1),它是各个成分之和。如果我们将对应于每个基ui的成分表示成xi,则重构的信号又可表示成一个向量形式。 则 (补4-4) 显然,与原向量X是有差别的,是原向量的一个近似,要使与X的差异越小,则要用更多维数的正交基。 如果将 代入(4-61)可得到
由于uj,j=1,…,∞是正交归一坐标系,有 (4-63)所以有 (4-64) 系数cj可以利用正交坐标系的特性得到。如令某一基向量uj与向量X作点积,则有 (4-65) 利用(4-63)有 (4-66) 代入(4-64)得 (4-67) 如令,则有 欲使该均方误差ε为最小,就变成在确保正交变换的条件下,使ε达最小的问题,这可用拉格朗日乘子法求解。为此设一函数 并令其对uj求导数,得 (4-68) 可见向量应是矩阵的特征值的特征向量,而此时截断误差为。如将按其大小顺序排列,即 则取前d项特征值对应的特征向量组成的坐标系,可使向量的均方误差为最小。 满足上述条件的变换就是K-L变换。 在结束4.6.1节的学习时,我们还要强调K-L变换的特殊性。K-L变换是一种独特的正交变换,它与一些常用的正交变换不同。最常见的正交谈换如富里叶变换,哈达玛变换离散余弦变换等都是一种通用的正交变换,它们各自有固定的形式,如富里叶变换的基是以频率为参数的e的括数函数族组成。它主要用来对数据作频谱分析。滤波等。而K-L变换的基并没有固定的形式,它是从对给定数据等{x}进行计算产生的。换句话说,给定的数据集不同,得到的K-L变换基函数也因此而不同。正是因为它对给定数据集{x}存在依赖关系,它能在降低维数时仍能较好地描述数据,因此是模式识别中降低特征空间维数的有效方法。但是由于它的正交基函数族是从训练样本集中计算出来的,因此并不存在一种对任何数据都适用的K-L变换基,一般的作法是先用一组训练数据计算出K-L变换基,然没用这组基来重构或分析其它数据。面举一个在人脸表情分析的例子,使我们增加对K-L变换的感性认识。 例: 为了实现对人脸表情进行分析,或生成对不同表情的人脸,可以使用K-L变换。具体做法是,先获取一组带不同表情的人脸图象作为训练样本集,例如补图4-1是其中的一个日本女孩子做六种不同典型表情时的图象。如果我们将训练样本集表示成{x},则图4-1中的每一幅图就是一个数据x,利用这些数据计算出相应的协方差矩阵4。然后对这个矩阵进行特征值分解,求得相应的特征向量。我们把特征值按其数值进行降序排列,并选出前项用来重构人脸不同的表情图象,为了说明。
从下面“用KL变换作人脸合成”的例子中可以看出,每个分量都承担着各自不同的作用,也就是说各个分量之间的关系是不怎么关联的。为了说明这点我们有必要进一步了解K-L变换的性质,这就是1,训练集样本的不同系数ci与cj之间是不相关的。以及2,训练是样本集在使用K-L变换的正交基描述后,它的协方差矩阵成为对角矩阵。它们的数学证明见讲义。并注意图4-2用一个二维空间分布的数据说明K-L变换的性质。 K-L变换具有一些很重要的性质,因而在特征提取中很有用。 (1) 样本的K-L变换系数ci与cj是无关的,这可从样本集中任两个系数的乘积的期望值看出 (4-69) 其中为Kronecker符号,即 。 (4-69)式表明不同系数是无关的,同时还表明相同系数的方差就是ψ矩阵的相应特征值。特征值大,则表明样本沿该坐标轴uj分量的方差大,分布分散。 (2) K-L变换后的协方差矩阵为对角矩阵。 如我们令在K-L变换后的D维坐标系统中样本向量为X',则 而 将(4-69)代入得 (4-71) ∧为一对角矩阵,或写成 ,其中U为由(u1,...uD)组成的向量矩阵。这表明经过K-L变换后,原向量各分量之间存在的相关性已被消除。图4.2表示了一个二维空间中椭圆分布的样本集,在用K-L变换后新的坐标系中各分量的相关性消除。而在原坐标中x1,x2两个分量之间存在很明显的相关性。图4.2还反映了样本的u1分量比较分散,因而对分类可能起较大作用,而u2则对分类无太大作用,可以去掉。
| 图 4.2 | K-L变换的一些典型应用
上面我们从数学的角度分析了K-L变换的性质。归结起来,它消除了各分量之间的相关性,因而用它来描述事物时,可以减少描述量的冗余性,做到用最经济有效的方法描述事物。下面结合一些应用实例来说明如何运用K-L变换的这一性质。 1.降维与压缩 以人脸图象这个例子看,K-L变换的降维效果是十分明显的。对一幅人脸图象,如果它由M行与N到象素组成,则原始的特征空间维数就应为M×N。而如果在K-L变换以及只用到30个基,那么维数就降至30,由此可见降维的效果是极其明显的。另一方面降维与数据压缩又是紧密联系在一起的。譬如原训练样本集的数量为V,而现采用30个基,每个基实质上是一幅图象,再加上每幅图象的描述参数(式(补4-3)中的C),数据量是大大降低,尤其是图象数很大时,压缩量是十分明显的。 2.构造参数模型 使用K-L变换不仅仅起到降维与压缩数据的作用,更重要的是每个描述量都有明确的意义,因而改变某一个参数就可让图象按所需要的方向变化。在没有使用K-L变换的原数据集中对图象的描述量是每个象素的灰度值,而弧立地改变某个象素的灰度值是没有意义的。而在使用K-L变换后,每个描述量都有其各自的作用。因此通过改变这些参数的值就可实现对模型的有效描述,这在图象生成中是很有用的。因此利用K-L变换构造出可控制的,连续可调的参数模型在人脸识别与人脸图象重构采方面的应用是十分有效的。 3.人脸识别 利用K-L变换进行人脸图象识别是一个著名的方法。其原理十分简单,首先搜集要识别的人的人脸图象,建立人脸图象库,然后利用K-L变换确定相应的人脸基图象,再反过来用这些基图象对人脸图象库中的有人脸图象进行K-L变换,从而得到每幅图象的参数向量(试问用哪个公式?)并将每幅图的参数向量存起来。在识别时,先对一张所输入的脸图象进行必要的规范化,再进行K-L变换分析,得到其参数向量。将这个参数向量与库中每幅图的参数向量进行比较,找到最相似的参数向量,也就等于找到最相似的人脸,从而认为所输入的人脸图象就是库内该人的一张人脸, 完成了识别过程。 (试问:这种识别方法属于哪一种方法?) 4.人脸图象合成 用K-L变换构造参数模型的另一种典型用途是人脸图象合成。从下面的例子中可以看出,有目的的控制各个分量的比例,也就是通过调整参数向量。可以将一幅不带表情图象改变成带各种表情的图象,称为人脸表情图象合成。下图为生成各种表情图象的示例。 | | 图中从上到下分别对应KL变换后第一至第四个主分量,这四个主分量代表了人在不同表情下面部图像的主要变化。使用这四个分量,就可以描述面部表情的大部分变化,与变换以前的描述方法对比,原来要用几万个分量(图像中的各个象素)来描述这种情感图像的变化。 从左到右是对每个分量赋以不同的值,而得到的合成图像,其中中间一列是取均值时的对应结果,最左一列是取到(均值减三倍标准方差)时的合成图像,同样的,按照图像上边一行标出的意义,可以合成其它几列表情图像。 |
本章前述部分着重讨论了基于各种原理与判据的特征提取方法。从其工作原理来看可以分成两大类。一类基于对样本在特征空间分布的距离度量。其基本思想是通过原有特征向量线性组合而成新的特征向量,做到既降维,又能尽可能体现类间分离,类内聚集的原则。在欧氏距离度量的条件下所提出的几种判据都是从这一点出发的,如 ,,等。其中描述类内离散度与类间离散度的矩阵与是两个主要描述样本分布的数据。利用K-L变换进行特征提取的几个方法也是出于同样的原理。它是在原特征空间进行的一种特殊的正交变换,在其产生矩阵确定的范围内消除了特征各分量间的相关性,并从中选择有关的特征子空间。这一类方法由于直接从样本之间在特征空间中的距离度量出发,具有直观与计算简便等优点。但由于没有从概率分布考虑,与计算错误率没有直接的关系,当不同类别的样本存在交迭区时,所采用的特征提取结果无法保证有较小的错误率。 另一大类则是从概率分布的差异出发,制订出反映概率分布差异的判据,以此确定特征如何提取。这类判据由于与错误率之间可能存在单调或上界关系等,因此从错误率角度考虑有一定的合理性。但是使用这种方法需要有概率分布的知识,并且只是在概率分布具有简单形式时,计算才比较简便。熵概念的运用是描述概率分布另一种有用的形式,使用时也可仿造本章中所举例子,将一些量折算成概率形式,利用熵原理构造的判据,进行特征提取。 特征提取各个方法中都有一个共同的特点,即判别函数的极值往往演变为找有关距阵的特征值与特征向量,由相应的特征向量组成坐标系统的基向量。计算有关矩阵的特征值矩阵与特征向量,选择前d个大特征值,以它们相应的特征向量构成坐标系统,这是大部特征提取方法的基本做法。这一点与下面讨论的特征选择方法是不相同的。 在特征提取方法中所使用的各种判据原理不尽相同。从以上讨论可以看出,一般希望判据能满足以下几点要求: (1) 与错误概率或其上界或下界有单调关系,如能做到这一点,当判据达到其最大值时,一般说来其错误概率较小。前面提到的基于概率分布的判据,如Bhattacharyya距离和Chernoff界限符合这个条件,而基于特征空间分布欧氏距离度量的一些判据与错误概率没有直接关系。 (2) 判据在特征独立时有可加性,即 这里用 表示第i与j类之间的可分性准则函数, 表示相应的k分量的可分性准则函数。 (3) 可分性判别应满足 即有可分性,及对称性。 (4) 单调性,是指维数增多时,判据值不应减少。 第6章 特征生成Ⅰ:线性变换 6.1 引言 6.2 基本向量和图像 6.3 Karhunen-loeve变换 6.4 奇异值分解 6.5 独立成分分析 6.6 离散傅里叶变换(DFT)
|