（通信与信息系统专业论文）局部信息保持投影及应用.pdf

摘要 在低维空间描述高维数据是数据分析、模式识别、机器学习、计算机视觉等 领域的基础问题之一。随着传感器技术和数据采集技术的迅速发展，实际数据的 维数越来越高，如何有效地描述数据已成为目前急需要解决和非常活跃的研究方 向之一。在已有的众多方法中，最经典且部分得到成功应用的方法是主成分分析 ( p r i n c i p a lc o m p o n e n ta n a l y s i s ，p c a ) 。p c a 是基于最小均方误差的特征提取技术， 有效地保持了数据的全局欧氏距离结构，即差异信息；缺点是不能有效地保持非 线性数据的差异信息，导致性能比较差。对此，本文从p c a 入手，借助流形学习 的思想，深入研究了基于图论的差异信息保持投影，主要内容和贡献如下： 第一，针对p c a 不能有效地保持非线性数据的局部差异信息，导致性能比较 差等问题，提出了局部信息保持投影算法( l o c a li n f o m a t i o np r e s e r v i n gp r o j e c t i o n ， l i p p ) 。该算法借助流形学习的思想，在训练数据集上定义一个由顶点和相似矩阵 构成的加权邻接图，其中顶点是由训练数据构成，相似矩阵度量了顶点之间的差 异信息大小。在此基础上，建立了一个简明、含义明确的特征提取准则，该准则 通过最大化差异离散度寻找投影方向。和传统的p c a 相比，l i p p 不仅适用于线性 数据的描述和分类，而且有效地保持了非线性数据的局部差异信息，并取得了不 错的效果。实验结果证明了所提算法的有效性。 第二，针对l i p p 存在小样本和计算比较复杂等问题，提出了二维局部信息保 持投影( 铆o d 硫e n s i o n a ll o c a l i n f o 肌a t i o np r e s e r v i n gp r o j e c t i o n ，2 d l i p p ) 。该方 法借助经典的二维特征提取技术如2 d p c a ，将提出的l i p p 算法推广到二维，有 效地避免了将图像转换成向量，较好地保持了图像相邻像素之间的空间结构信息， 同时降低了计算复杂度。和2 d p c a 相比，2 d l i p p 不仅适用于线性数据的描述和 分类，而且有效地保持了非线性数据的局部差异信息，并取得了不错的效果。在 y a l e ，u m i s t ，a r 和o r l 等人脸库上的实验结果证实了所提方法的有效性。 关键词：流形学习差异离散度邻接差异信息图特征提取主成分分析 a b s t r a c t r e p r e s e n t a t i o nt h eh i g h - d i m e n s i o n a li i a t ai i lal o w d i m e n s i o n a ls u b s p a c ei so n eo f n l e 劬幽m e n t a lp r o b l e m si i ld a t aa n a l y s i s ，p a t t e mr e c o g n i t i o n ，m a c h i n el e a r l l i n g ，a n d c o m p u t e rv i s i o n w i lm er a p i dd e v e l o p m e n to fs e n s o ra n dd a t ac o l l e c t i o nt e c h n i q u e s ， t h ed i m e n s i o no fd a t ai sb e c o m i n gh i g h e ra n d1 1 i 曲e r s o ，h o wt oe 笨c i e n t l yr e p r e s e n t t h ed a t ah a sb e c o m ea i la c t i v er e s e a r c ha r e aa i l du r g e n tp r o b l e mt ob es o l v e d i i lt h e e x i s t i n gm e t h o d s ，t h em o s tc l a s s i c a lo n ei sp c a ( p r i i l c i p a lc o m p o n e n ta n a 】y s i s ) ，w “c h i sa i lu i l s u p e n ，i s e df e a t u r ee x t r a c t i o nt e c h i l i q u ei nt h es e n s eo fm i n i m i z a t i o nm e a n s q u a r e de m r i te m c i e n t l yp r e s e r v e st h eg l o b a le u c i i d e a nd i s t a n c e ，i e d i v e r s i t y i n f o n n a t i o nb e t 、v e e nd a t a ，b u tf a i l st 0t h en o n l i n e a rd a t a i nt m sd i s s e n a t i o nt h es c h e m e o fp r e s e r v i n gt h ed i v e r s i t yo fi i a t ai ss t u d i e db yu s i n gt h e 黟印hm e o 眄a n dm a n i f o l d 1 e a n l i n gt e c h n i q u e t h em a i nc o n t r i b u t i o n sa n d 、v o r ka r ea sf o l l o w s f i r s t ，an o v e lm e t h o d ，n 锄e l yl o c a li i l f o r m a t i o np r e s e r v i n gp r o j e c t i o n ( l i p p ) ， b a s e do ng r a p ht h e o 巧i sp r o p o s e d l i p pd e f i n e sa i la d j a c e n c yg r a p hw i t hav e r t e xs e t w h i c ha r ec o m p o s e do ft h et r a i n i n gd a t aa n da na m l l i 锣m a t r i xw h o s ee l e m e n t sm e a s u r e t 1 1 ed i v e r s i t ) ri n f o m l a t i o nb e t w e e nv e n e x e s ac o n c i s ef e a t i 】r ee x t r a c t i o nc r i t e r i o ni st h e n d e v e l o p e db ym a ) ( i m i z i n gt l l ed i v e r s i 够s c a 仳e rw h i c hi sd e t e n n i n e db ya d j a c e n c y 铲印h c o m p a r e dt op c a ，l i p pn o to n l ys u i t st ol i n e a rd a t ab u ta l s oe 筋c i e n t l yp r e s e r v e st h e d i v e r s i t yi n f o m a t i o no fn o n l i n e a rd a t a e x t e n s i v ee x p e r i m e n t si n d i c a t et h ee m c i e n c y o ft h ep r o i p o s e dm e t h o d s e c o n d ，t w o - d i m e n s i o n a lf 毫a t u r ee x t r a c t i o nm e t h o d ，n 锄e l yt w o d i m e n s i o n a l l o c a li n f o 珊a t i o np r e s e i i 培p r o j e c t i o n ( 2 d l i p p ) ，i sp r o p o s e d b yc o m b i n i n gt h e t 、v o - d i m e n s i o n a lf e a t u r ee x t r a c t i o nt e c h n i q u e sa n dl i p p a so p p o s e dt ol i p p ，2 d l i p p d i r e c t l yc a l c u l a t e st h ed i v e r s 时s c a n e r 舶mt h ei m a g em a t r i c e sr a t h e rt h a ni i l l a g e v e c t o r s ，s oi ta v o i d st r a n s f o 肋i 1 1 9t h ei m a g em a t r i xi n t oav e c t o r ，c a nw e l lp r e s e n ，et h e l o c a ls p a t i a li n f o n l l a t i o n 锄o n gp i x e l so ft h ei m a g e c o m p a r e dt o2 d p c a ，2 d l i p p n o t o m ys u i t st 0l i n e a rd a 瞳ab u ta l s oe m c i e n t l yp r e s e r v e st h el o c a ld i v e r s i 钾i 甜i o m a t i o no f n o n - l i n e a rd a 瞳a e x p e r i m e n t so ny a l e ，u m i s t a ra n do r lf a c ed a t a b a l s e si n d i c a t et h e e f f i c i e n c yo f2 d l i p p k e y w o r d ：m a n i f o l dl e a r n i n g d i v e r s i 锣s c a t t e r a d j a c e n c yd i v e r s i 哆g r a p h f e a t u r ee x t r a c t i o n p r i n c i p a ic o m p o n e n ta n a l y s i s 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：毖墅)日期逊：笾。鳃 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名： 导师签名： 日期2 鲥芝= 丛! i 日期五鸱手一 第一章绪论 1 1 1 课题来源 第一章绪论 1 1 选题来源与研究背景 课题选题来源于国家自然科学基金( 6 0 8 0 2 0 7 5 ) 和i s n 国家重点实验室基金 ( i s n 0 9 0 4 0 3 ) 。 1 1 2 研究背景 随着科学技术和信息技术的飞速发展，人们从各行业中所获取的数据正在以 指数形式快速增长，越来越多的大量不确定性数据和海量模糊数据体现了高维小 样本的特征i l 】。例如，在图像分析、计算机视觉、网络数据检索、基因微阵列数据 分析、生物特征识别中获取的数据都是高维的。信息技术的发展迫切需要去探索 和揭示存在于这些数据中的奥秘。但是，直接对高维数据进行分析往往收效不大 甚至失效，以致蕴含在数据中的重要信息或规律无法被探索和理解，导致数据资 源变成“数据灾难”，甚至造成后续决策失败和巨大损失。因此，如何有效地从高 维数据中获取有用的信息或分布规律己成为当今信息科学与技术所面临的核心问 题。 将现代计算机的高性能与人的高智能相结合是处理这些数据的一种理想选 择，是目前处理高维数据一种比较有效、核心的技术与途径，其中数据挖掘和机 器学习等已经被证明是行之有效的数据分析和处理方法。在许多实际应用领域， 常常需要对这些数据建立一个分类器模型和相应的学习算法，并依据所建立的分 类器模型和学习算法去挖掘存在于数据中的一些未知规律。通常，计算机对高维 数据的处理学习过程如图1 1 所示，主要包括以下四步： 旧取h 吲嚣 后续处理 ( 如分类、模 式描述、等) 图1 1 高维数据的处理过程框图 第一步，信息获取。通过传感器或者数据采集设备采集图像、语音、字符等 原始数据。 2局部信息保持投影及应用 第二步，预处理。对采集的原始高维数据进行一些必要的处理，从中获得需 要的数据。例如，在采集过程中由于外界环境( 如气候、地点等) 和人为因素等 的影响，使得采集的原始数据掺杂了很多噪声，这些噪声可能影响后续的处理。 另外，通过采集设备采集的数据中可能夹杂着一些无用的信息，如在人脸识别领 域中所获得的人脸图像可能存在于比较复杂的背景中，从这些背景中分离出人脸 图像并去除无关的背景图像是一个必要的数据预处理过程。 第三步，特征提取选择。特征提取与选择是整个过程中的一个重要环节，提 取的特征好坏直接影响到后续处理。其基本任务是研究如何从众多的特征中挖掘 出那些对分类、描述有效的特征，从而实现特征空间维数的压缩，方便后续处理。 特征提取通常是在满足某种约束条件的基础上实现目标优化，通过相应的变换将 高维数据映射到低维空间中，以获得所需的有效特征。 第四步，后续处理，例如分类、模式描述等等。处理数据的目的就是通过已 知数据的相关信息来建立一种分类或者描述模型，使得根据这种模型可以有效地 探索隐藏在数据中的本质特征，或者能较好地描述相应模式，便于人们认识和发 现新的知识。 在上述四个主要环节中，特征提取是至关重要的一步，特征提取的好坏关系 到后续处理算法的选择和性能，进而影响着整个系统的性能。在实际应用中，很 难判断出或找出模式的重要特征，或受条件限制不能对它们进行测量1 2 j ，使得特征 提取成为许多研究领域( 如人脸识别、计算机视觉、高维图像分析) 的一个研究 难点和热点瞄圳。 1 2 研究现状 无论是识别过程还是学习过程，都要对研究对象固有的、本质的重要特征或 属性进行测量并将结果数值化，或对目标进行分解产生基元并对其符号化，形成 特征矢量或符号串、关系图，从而产生描述对象的模式【5 】。通常情况下，能描述对 象的元素很多，为了节约资源，节省存储空间、降低计算复杂度，在对后续分析 如识别等影响不大的前提下，按某种准则尽量选用对后续分析有用的特征，使得 用较少的特征就能完成分类识别任务，即减少特征矢量的维数或符号字符数。这 个过程称为特征提取。特征提取的基本任务就是将得到的原始高维数据映射到一 个低维空间，得到最能反映数据本质的特征，其目的就是为了更好地学习、训练 和分类。 目前，特征提取已成为数据分析、模式识别、机器学习、计算机视觉、图像 分析和数据挖掘等领域中不可避免的关键问题之一。在众多应用领域中，生物特 征识别以其自身的优势己成为一个非常活跃的研究领域，越来越受到研究人员的 第一章绪论 关注，其中人脸识别是一个典型的代表。它可被广泛地应用于公安系统刑侦破案 的罪犯身份识别、身份证及驾照等证件验证、银行及海关的监控、司法、医疗、 金融、自动门卫系统、视频会议、机器人的智能化研究以及医学等方面【6 1 。图1 2 给出了人脸识别系统框图。 图1 2 人脸识别系统框图 在过去的几十年里，研究者们已经提出了大量地有效的特征提取方法【1 。2 ，6 刁1 1 。 由于不同的应用领域，特征提取的方法也有所不同。下面以人脸识别为例，综述 特征提取的发展过程。 人脸识别是模式识别领域一个非常活跃的研究方向，国内外许多著名的研究 结构和大学都对人脸识别进行过深入的研究，提出了许多方法，尤其是人脸特征 提取方法。这些方法大体上可分为神经网络方法、模板匹配方法、几何特征方法 和代数特征方法( 又称子空间方法) 等。 神经网络方法研究表明，神经网络也可以被直接用来提取特征子空间【7 1 。 o i a 发现可以用一个三层结构的神经网络得到p c a 子空间【8 】。他还发现自联想神 经网络( a u 幻a s s o c i a t i v en e u r a ln e 似o r k s ，a a n n ) 可以用作独立成分分析l 引，同时 可以描述非线性子空间【1 0 】。典型的方法还有k o h o n e n 【1 1 j 提出的自组织映射 ( s e l f or g j 疝z i n gm a p p i n g ，s o m ) ，l i n 【1 2 】等人提出的基于概率决策的神经网络法， l e e 等人【1 3 】提出的用于人脸识别的b p 网络算法等等。基于神经网络的方法是基于 输入信号能够由神经网络映射到低维空间，并使其在低维空间中仍然保持高维空 间点之间的近邻关系的基础上的。常规的神经网络方法在小样本情况下具有分类 性能好，速度快等特点，当样本数量超过一定范围时，其训练速度和识别的效果 都会大大降低。 模板匹配方法o s 锄u 【1 4 】等人提出的等灰度图匹配方法( 所谓等灰度图就是对 原始图像进行二值化后得到的图像) ，主要是利用灰度直方图来抽取等灰度线图， 最后利用模板匹配进行识别。该方法的优点是运算量小于通常的基于灰度图的匹 配方法；缺点是要求光照变化不大，摄像机到人脸的距离保持不变，而且当外形 ( 如一个新的发型等等) 或附属物发生变化时，需要重新配准。y u i l l e ，c o h n 和 4 局部信息保持投影及应用 h a l l i n a n 【l5 】提出用可变形模板抽取面部特征。这些模板可以平移、旋转和变形， 可以最佳地表示它们在图像中的形状。缺点是模板的起始位置对确定眼睛的准确 位置影响很大。当模板从眉毛上开始时，算法不能够区分眼睛和眉毛。另一个缺 点是计算复杂。一般而言，基于模板的方法是一个更理性的途径。问题的关键是 如何描述模板，当对图像进行分析近似时，系统应能够容忍模板和实际图像之间 的差别，但这种容忍度往往趋向于抹煞人脸之间的差别。 几何特征方法基于几何特征的方法是将研究样本用个几何特征矢量表 示，用层次聚类的思想设计分类器以达到分类识别的目的。这就要求选取的几何 特征矢量具有一定的独特性，能够反映不同样本之间的差别，同时又具有一定的 弹性，以消除时间的跨度以及一些自然环境因素的影响。几何特征矢量是以样本 的形状和几何关系为基础的特征矢量，其分量通常包括样本指定两点间的欧氏距 离、曲率、角度等。p o g g i o 和b m n e l l i 【1 6 j 用改进的积分投影法提取出用欧氏距离 表征的3 5 维人脸特征矢量，用于模式分类，取得了不错的识别率。h 啪g 和c h e n 玎分别采用动态模板与活动轮廓模型来提取眼睛、嘴巴、眉毛和下巴的轮廓。动 态模板是参数化的简单图元模型，根据先验知识定义的能量函数及相应的图像约 束条件指导其收敛过程。而活动轮廓则是能量最小化的曲线【1 & 1 9 1 ，由能量函数指 导其收敛到局部边界。这种方法对人脸具有较好的描述能力，为几何特征矢量的 生成打下了坚实的基础【2 。另外，g l o 渤c h o w 和l i 采用动态模板提取眼睛与嘴 巴轮廓，后利用自适应霍夫变换确定眼球、下巴轮廓的识别方法，取得了满意结 果【2 1 j 。n i c h o l a sr o e d e r 和“研究指出【2 2 1 ，基于几何特征识别人脸的准确率完全 依赖于脸部特征提取的准确性，而二维图像几何特征以及特征点的定位不容易， 经常由于定位不准确而导致特征点有较大偏移，这是影响基于几何特征人脸识别 方法的重要因素。基于几何特征的人脸识别方法具有如下优点四】：( 1 ) 符合人类识 别人脸的机理，易于理解；( 2 ) 对每幅图像只需要存储一个特征矢量，存储量小； ( 3 ) 对光照变化不太敏感。其缺点是：( 1 ) 从图像中抽取稳定的特征比较困难，特别 是特征受到遮挡时；( 2 ) 对强烈的表情变化和姿态变化的鲁棒性较差；( 3 ) 一般几何 特征只描述了部件的基本形状与结构关系，忽略了局部细微特征，造成部分信息 丢失，适合于粗分类。 代数特征方法代数特征的方法又称为子空间分析法，这类方法的思想是将 数据看做高维向量空间中的一个点，然后根据统计属性和视觉属性寻找一个能有 效地反映数据内在结构信息的低维子空间，己成为特征提取的主流方法之一1 2 4 2 5 】。 这类方法大体上可分为线性方法和非线性方法。 ( 1 ) 线性方法典型的线性代数特征方法包括：主成分分析( p i n c i p a l c o m p o n e n ta n a l y s i s ，p c a ) 、独立成分分析( i i l d e n p e n d e n tc o m p o n e n ta n a l y s i s ， i c a ) 、线性判别分析( l i n e a rd i s c r i n l i n a i l ta n a l y s i s ，l d a ) 等。 第一章绪论 5 p c a 是统计领域中一种常用的基于最小均方误差的线性无监督特征提取方 法，也称k l ( k a r h u i l e n 1 0 e v e ) 变换。它提取了最佳描述子空间，并有效地保存 了样本的全局欧氏距离。它的思想是找到一个投影映射，使得样本从高维空间降 到低维子空间，同时保留尽可能多的能量。利用p c a 进行人脸识别，r b y 等人 提出了经典的e i g e r 觑e s 【z 7 。2 8 】，并取得了较好的识别率。在此基础上，人们提出 许多基于k l 变换的方法【2 9 3 引，典型的技术有m o 西a d d a m 等人【2 9 】提出的基于主 成分分析的贝叶斯框架人脸识别算法，r a o k i m 等人1 3 l j 提出的基于块主成分分析 的方法，p 破等人【3 3 】提出的c a p c a 以及最近提出的稀疏子空间算法【3 8 j 等。 近来，b a r t l e t t 等人【3 9 4 0 1 提出了基于i c a 的人脸识别方法。i c a 是上个世纪九 十年代逐渐发展起来的一种算法，最初应用于解决盲信号分量( b l i n ds o u r c e s e p 删i o n ，b b s ) 问题【4 1 1 。其思想是消除或减少各分量间的相关性，使它们尽可 能的独立，适用于非高斯分布的模型。研究表明具有优于p c a 的识别效果。该方 法的缺点是不能确定模式有多少个独立的基元以及每个基元的贡献大小。 虽然，p c a 和i c a 取得了不错的效果，但是它们均没有考虑样本的类别信息， 属于无监督特征提取方法。与它们不同的是，l d a 是一种监督的特征提取技术。 它是基于f i s h e r 判别准则：类内方差最小和类间方差最大。该方法提取的是最佳 判别子空间，将原来的高维样本向判别子空间投影，一方面可以有效地降低特征 空间的维数，另一方面所提取的特征具有最佳的可分离性【4 2 郫，4 】，这类方法的关键 是如何求解最佳判别矢量。利用l d a 进行人脸识别，b e l h u m e u r 等人提出了 f i s h e r f a c e s 【删并取得了不错的结果。l d a 虽然有利于分类，但是它需要较多的计 算量，特别是遇到小样本问题时【4 5 】，类内离散度奇异，给求解带来麻烦。为此， 人们提出了多种解决方法【4 6 5 0 】。典型的代表有z h a o 等【4 6 】提出的主成分判别分析， y - u 等人【4 7 】提出的直接线性判别分析，以及c h e n 、h 啪g 和l u 等【4 8 - 5 1 1 提出的零子 空间法等等。所有这些算法有效地提高了基于f i s h e r 判别准则的分类效果，但是 求解同样比较麻烦。 不论是基于p c a 还是l d a 的方法，都需要将数据矩阵转换成一维向量，使 得估计协方差矩阵变得更为复杂，另外一个缺点是这类方法容易遇到小样本问题， 导致识别性能不是足够的好。针对这一问题，线性代数法与多线性代数理论相结 合成为一个研究热点【5 1 。5 2 1 ，如y 抽g 等人提出了2 d p c a 等。这类方法有效地降低 了计算复杂性，并取得了令人满意的效果。 上述线性方法描述的是模式的全局属性，适用于线性可分，然而，在现实应 用中许多数据并不是全局线性的，例如人脸图像位于一种隐藏在高维空间的非线 性流形结构上，因此，这类线性方法不能较好地保持数据的局部结构属性，而导 致学习识别效果降低【5 3 ，5 9 1 。 ( 2 ) 非线性方法基于研究非线性分布数据的需要，研究者们提出了大量的 6 局部信息保持投影及应用 非线性特征提取方法。这类方法可以归结为基于核学习和流形学习( 几何视觉分 析) 的特征提取算法两大类。 核学习的思想是通过核函数将数据映射到一个高维的空间，使得数据线性 可分，然后利用已有的特征提取技术实现降维，这类方法取得了不错的结果1 5 3 。5 8 l 。 例如，k e m e lp c a ，k e m e ll d a ，k e m e li c a 等。这类方法由于引进了核函数， 在提高了算法性能的同时，却在一定程度上提高了样本的维数使得计算比较复杂， 而且算法的性能与核函数的选择及参数的设定密切相关。对于不同的数据，如何 选择核函数和设定最理想的参数是迫切需要解决的问题。到目前为止，还没有发 现一种通用的准则，多数情况下核函数和参数的选取仍然需要经验指导。 流形学习通过局部线性近似有效地保持了模式的内在局部结构属性。比较 典型的技术有t e n e n b a u m 等人提出的等距映射( i s o m e t r i cm a p p i n g ，i s o m a p ) 1 5 9 1 ， r o w e i s 和s a u l 提出的局部线性嵌入( l o c a l l yl i n e a re m b e d d i n g ，l l e ) ，b e l k i n 等人提出的l 印l a c i a i le i g e r l i l l a p l 6 1j 等。 i s o m a p 法首先在几何空间中计算成对测地距离，再运用m d s 方法把数据点 从高维空间投影到低维非线性拓扑空间中，从而获得保持样本间测地距离不变的 低维流形。而l l e 是将全局非线性化为局部线性，而相互重叠的局部领域能够提 供全局结构的信息。这样对每个局部进行线性降维后再按照某种规则将结构结合 在一起，就能够得到低维的全局坐标表示。l a p l a c i a j le i g e m a p 的突出特点是与谱 图理论联系密切，它的基本思想是在高维空间中离得很近的点投影到低维空间后 也应该离得很近，最终的求解归结到拉普拉斯算子的广义特征值问题，拉普拉斯 映射与l l e 算法类似，待定参数相同，求解的是稀疏矩阵的广义特征值问题，均 可用于数据聚类。 上面三种方法在实验中取得了令人瞩目的结果，但是所提取的映射关系仅建 立在训练数据上，对如何估计测试数据的映射不清楚，导致在计算机视觉和模式 识别领域应用的比较少。对此问题，h e 等人【6 2 制】将上述非线性流形学习方法通过 线性处理，提出了l p p ( l o c a l 时p r e s e r v i n gp r o i e c t i o n ) ，n p e ( n e i 曲b o r h o o d p r e s e r v i n ge m b e d d i n g ) 以及i s o m e t r i cp r o i e c t i o n 等等。这些方法一方面有效地 保持了非线性数据的局部内在结构，另一方面对所有数据包括测试数据建立了一 个明确的映射，而且取得了不错的效果【5 9 螂】，他们已被广泛的应用到模式识别、 文档分析、图像检索、图像恢复等领域。 这些方法的缺点是需要将数据矩阵转换成一维向量，破坏了图像相邻像素之 间的空间结构信息，而且增加了计算复杂度，另外一个缺点是小样本问题。针对 这一问题，研究者借助多线性代数，实现了基于张量的子空间方法【6 9 7 4 1 ，典型的 技术有2 d l p p ，2 d n p e ，t e l l s o r - l d e ，t e n s o r - l p p 以及t e n s o r - n p e 等。这类方 法的优点是减少了小样本问题的影响，在小样本情况下，识别率提高很明显，缺 第一章绪论 7 点是还有一些基础理论和算法有待解决。 流形学习方法有效地保持了数据的内在局部结构属性【7 5 l ，较好地保存了样本 间的局部相似性，但是破坏了样本间的差异性，以致不能较好地保持数据空间的 差异信息，导致分类效果不是足够的好。针对此问题，本文将借助流形学习的思 想，从p c a 入手，深入研究了基于图论的差异信息保持投影方法。 1 3 本论文的研究内容及安排 代数特征方法作为人脸识别领域主流的特征提取方法之一，得到了广泛关注 【1 。2 ，6 - 7 ，2 4 。7 1 】。其中p c a ，l d a 和流形学习技术是典型的代表。本文针对p c a 不能 有效地保持模式的差异信息，主要研究如何借助流形学习技术思想，实现基于 p c a 的非线性模式描述和识别，并借助二维特征提取技术，实现二维模式描述， 最后以人脸识别为例，验证算法的有效性。本文主要内容及章节安排如下： 第一章，绪论。介绍本论文的研究背景与意义；从特征提取方法在人脸识别 领域的应用入手，分析特征提取的发展现状，并指出问题；最后对本文的主要内 容及章节安排进行介绍。 第二章，局部信息保持投影。首先介绍了主成分分析和局部保持投影的思想 及算法；借助流形学习的思想，通过局部邻接图提出了差异信息的概念，并建立 了局部信息保持投影准则；然后在y a l e ，u m i s t ，a r 和o r l 四个人脸数据库上 进行实验仿真，并将其识别率与p c a ，i c a 及l p p 的识别率进行比较分析，并画 出各算法的识别率随特征个数的变化曲线；最后将该算法应用于人脸描述，以y a l e 库的实验为例进行了分析。 第三章，二维局部信息保持投影。首先，介绍了二维主成分分析的思想及算 法；接着，将局部信息保持投影算法扩展至二维，提出二维局部信息保持投影算 法；然后在y - a l e ，u m i s t ，a r 和o r l 四个人脸数据库上进行实验仿真，并将其 识别率与2 d p c a ，2 d l p p ，2 d n p e 及2 d l d a 的识别率进行比较分析，并画出各 算法的识别率随投影向量个数的变化曲线；最后讲述了图像重建，将图像分别利 用p c a ，l i p p ，2 d p c a ，2 d l i p p 提取特征后重建，比较分析重建效果。 第四章，总结和展望。对整篇论文工作进行了总结分析，并对下一步的工作 进行了规划。 第二章局部信息保持投影 9 第二章局部信息保持投影 p c a 是一种经典的线性特征提取算法，其目的是降低特征空间的维数和去除 特征间的冗余，实质是卡洛南一洛伊( k 砷m l e n l o e v e ) 变换，简称k l 变换。 它适用于任意的概率分布，是在均方误差最小准则下获得数据压缩的最佳变换。 然而，在对模式的度量过程中，人们发现一些模式实际往往服从一定形式的非线 性分布规律。这些分布规律使样本点互相影响、互相制约，因此也就形成了一种 模式在不同外界环境作用下的多种形态。例如同一人脸的不同图像可以由光照、 姿态、表情配饰等关键条件决定，这些条件中的每一种发生变化时都会引起人脸 图像中的像素发生变化，而且这些条件同时变化所引起的像素的共同变化也不是 由每种条件变化所引起的像素变化的线性叠加，也就是说光照、姿态、表情和 配饰条件变化下的人脸数据是高度非线性相关的【l 】。从几何角度来看，这样的人脸 数据位于一个嵌入高维空间的低维流形上。在现实世界中，除了人脸数据外，服 从低维流形分布的数据是大量存在的。比如手写数字、植物叶片数据、步态和手 势等，这些数据常常具有低维内在流形结构( r o w e i s ，2 0 0 0 ；t e n e n b a u m ，2 0 0 0 ) 。对于 这类数据，p c a 并不能有效地探索存在于非线性数据中的内在结构。 流形学习是一种很好的解决方案，很好的保持了非线性数据的局部结构属性， 即相似信息，但破坏了对模式分类和描述有用的差异信息。在此，借助流形学习 的思想，研究如何描述非线性数据的差异信息。本章首先详细研究了基于主成分 分析的特征提取方法，接着介绍了局部保持投影算法，然后借助流形学习的思想， 提出差异信息的概念，建立了局部信息保持投影准则( l o c a li n f o m a t i o np r e s e r v i n g p r o e c t i o n ，l i p p ) ，并从理论上分析比较了p c a 和l i p p 。 2 2 1 原理6 3 2 1 主成分分析 令x = b ，恐，) r 表示对某模式的p 维随机观测向量，其均值为，协方差阵 为。令；= x 一= ( - ，乏，i ) r ，其中i = 薯一“，待l ，2 ，p ，肛，为的第f 个 分量。 考虑如下线性组合： l o 局部信息保持投影及应用 其中吩r m ，并满足： 2 q 1 一+ 吼1 恐+ + 口p l 工p2 何_ x = q 2 毛+ 口2 2 恐+ + 2 2 口；x ( 2 1 ) 2 口l ，j c l + 口2 ，恐+ + 穹口二，工 n = o 箩j 二歹 如果用m 代替x ，则希望m 尽可能多地反映x 的信息。在统计学中，通常用m 的方差来衡量姐体现x 信息量的大小，也就是说，变量乃的方差越大，则含有x 的 信息就越多。用数学描述就是在式( 2 2 ) 约束下，使下式取最大值： v a r ) = 口f 口l( 2 3 ) 则由口，确定的变量m = 口- x 就是原始变量而，吃，勤的第主成分。 令耽为原始变量赡，砭，b 的第二主成分，为了保证耽和m 互不相关，必需 满足： c o v “，y 2 ) = 口；口l = o ( 2 - 4 ) 因此，第二主成分就是在式( 2 2 ) 及( 2 4 ) 的约束下，使v a r 如) 取最大的口：所 确定的变量儿= 口；石。其它主成分依次类推。 根据上面分析可知，求解原始变量主成分的关键就是确定单位正交向量 口，o = 1 ，2 ，p ) 。由第一主成分定义知，q 可通过求解式( 2 3 ) 在式( 2 2 ) 约束 下取最大值来获得。通过引入l a g r a n g e 乘子- ，将上述有约束最大值问题转换成 下式无约束最大值问题。 歹- 。) ：v a r 抚) = 口- 口。一a g f 口，一1 ) ( 2 5 ) 令兰：o ，则可推得： d 口l = 口l ( 2 - 6 ) 第二章局部信息保持投影 可见，a l 是的特征值，口l 是对应于九l 的特征向量。给式( 2 - 6 ) 两边左乘 以口j ，然后代入式( 2 - 3 ) ，同时考虑到式( 2 - 2 ) 的约束，则有： v 缸m ) = a 。= 口f = ( 2 7 ) 由式( 2 7 ) 知，要使v a r 1 ) 最大，则口。必然是最大特征值a l 对应的单位特 征向量。 根据第二主成分的定义知，口：是在式( 2 2 ) 和( 2 4 ) 约束下，使v a r 仗) 最 大。由于口。是的单位特征向量，故式( 2 - 2 ) 和式( 2 - 4 ) 是等价的。因此，在式 ( 2 2 ) 和式( 2 - 4 ) 约束下，求解v a r 仳) 的最大值可写成： 口2 ( 2 - 8 ) 引入l a g r a n g e 乘子如及，7 ，将上述有约束最大值问题转换为求解式( 2 9 ) 的 无约束最大值问题。 ，( 口：) = v a r ：) = 口；口：一a ：q ；口：一1 ) 一叩口；口。 ( 2 9 ) 令垦当尘：o ，可推得： 。a 口 2 口2 2 九口2 一叩口l = o ( 2 - l o ) 将式( 2 一l o ) 两边左乘以口j 并结合式( 2 4 ) 整理有叩= o 。将其代入式( 2 1 0 ) 整理得： 口2 = 九口2 即如是的特征值，口：是对应于如的特征向量。 ( 2 - 1 1 ) 给方程( 2 一1 1 ) 两边同时左乘以口；，整理有口；口：= 如，则第二主成分耽的 方差为： v a r ：) = 允2 ( 2 1 2 ) 由式( 2 - 6 ) 、( 2 2 ) 及式( 2 1 1 ) 知，要使式( 2 - 1 2 ) 取最大值，必有九2 是的第 叫旬卸 j 吒q 吒口口 av 强 盯 n ，【 1 2 局部信息保持投影及应用 二个最大特征值，而口：是的对应于如的单位特征向量，且与口。正交。依次类推， 可求得其它单位特征向量口，( ，= 3 ，p ) 及对应的主成分乃。 综上所述，司以得出如f 结论： 结论，：假定和= 0 ，p ：，p p ) r 分别为随机向量x = g 。，x ：，) r 的协 方差阵和均值。令 ，九，砧( 丑o ，w f ) 及口1 ，乜2 ，口p 分别是的特征 值及相应的单位正交特征向量，则随机向量x 的第f1 5 f = 1 ，2 ，p ) 主成分为： = q ，( 一1 ) + 呸，( 而一p 2 ) + + ，( 一p ) = 口? ( x 一) ( 2 1 3 ) 由主成分的计算过程有v a r 以) ：以，f ：1 ，2 ，p 。因此九兰九描述了第，个 ， f = l 主成分提取的信息占总信息的份额，称此为第，个主成分的贡献率。则把前七个主 k|p 成分的贡献率之和九九称为m ，j ，2 ，玖的累计贡献率，它表明了前后个主 f = i ，j = l 成分m ，耽，虮综合提供原始随机向量x 信息的能力。 在实际应用中，一般是根据累计方差贡献率的大小( 8 5 ，一般由经验确定) 来确定选取的主成分个数忌 p ) ，使得用前后个主成分m ，耽，肌代替原始随机 向量x 时，不但降低了变量个数，而目也不至于丢失太多原始信息。 2 2 2 算法分析 给定训练样本集x = b 1 ，而，h 】，表示样本个数，而r 删( 待1 ，2 ，) 表示 第f 个样本，则其协方差矩阵为： g f = 专姜c o 与r ( 2 1 4 ) 其中，二= 专姜葺为样本的均值。令肜尺脒7 为利用p c a 算法获得的最优投 影方向，且形的，个列向量为协方差矩阵g f 的前z 个最大特征值对应的特征向 量。则_ 投影后的特征为： 第二章局部信息保持投影 h = 矿，f = l ，2 ， ， ( 2 一1 5 ) 从统计学角度，投影后的特征的能量可表示为： l = p 【n “j( 2 - 1 6 ) 其中，y = h ，n ，蜥l ，p 0 ) 表示矩阵的迹。 同样，原始样本的能量可表示为： l = p 旧7j( 2 - 1 7 ) 比较式( 2 - 1 6 ) 和( 2 1 7 ) ，可以发现丢失信息l 一，。是在全局欧氏距离前提下 展小化的。然而，当训练样本为非线性数据时，全局欧氏距离就不能很好的度 量样本的主要信息i 6 0 l ，此时丢失信息就比较大。解决该问题的比较好的办法是 保持局部信息，典型的技术如下面将要介绍的局部保持投影。 此外，每个样本对样本库提供的差异信息不同，也就是说每个样本的贡献 不同，而p c a 并没有考虑这些差异在估计样本协方差矩阵时，认为所有样本 的贡献相同所以度量模式的信息不是很准确。图2l 给出了一些二维数据点 的分布。从网2l 知，空心豳与其3 邻域内的实心圈之间相距比较近，对描述 模式所提供的差异信息比较小，因此贡献就比较小，在估计协方差矩阵时，应 给予比较小的权重；相反，浅色圈与其3 邻域内的实心圈之间相距较远，分布 比较稀疏，它提供的差异信息就比较大对描述模式具有重要的作用：因此 在估计协方差矩阵时，应给予比较太的权重。但是从式( 2 1 4 ) 发现p c a 认为 所有样本的贡献是相同的，因此p c a 方法并不能很好的保存数据空问的差异信 息。 o 圈2l 样本的贡献大小说明 2 2 局部保持投影 局部保持投影( l o c a l 计y p r c s e r v i n g p r o j e c t i 叩，l p