2015优博公示指导教师戴教授

StructuredPerceptionandandLowQualityVisualDissertationSubmittedTsinghuaforthedegreeofDoctorofControlScienceandDissertationSupervisor ProfessorQionghaiApril,关于使用的说本人完全了解有关保留、使用的规定，即：拥有在著作权定范围内的使用权，其中包：（1）已获的必须按学校规定提交，学校可以教学和科研目的，学校可以将公开的作为资料在馆、资料室等场所供校内师生阅读，或在校园网上供校内师生浏览部分内；（3）根据《中民条例暂行实施办法》，向国家图书馆报送可以公开的。（ 摘摘随着物理世界的，设备所能感知到视觉信息的维度越来越高。但同时受到环境及理论极限诸多约束，高维视觉信息的质量却存在着低质的特点,的结构化感知与理解框架。本的工作成果及创新点如下：化到了统一的数学框架下。揭示了在这个统一的感知框架下，log-sum函数是非凸p范数近0范数的极限并提出了对数和启发式感知算法。并在凸优化的框架下融合中的应用均表明，log-sum极限近算法可以从更大的噪声干扰下更为精准的提出随机特征抽取算法和图拉斯修复算法。在生物特征识别这一经典视觉觉理解上，利用判别性结构可以将计算机对合成孔径成像图（SAR）理解的精度该算法有效地针对语义中的缺失和错误，利用互信息为衡量标准，精准地发掘出数据的本身语义及内在结构。在人工给定语义标记错误的情况下，鲁棒信息量投影算法可以将现有主流投影算法的识别率提升10%以上。受此工作启发，本文进一步提出了最小信息量损失的视觉信息编码算法，显著提升了计算机对航拍图像理解的能力。Withtheevolutionsofmoderncameras,itispossibletoacquireimageswithex-tremelyhighresolutionsfromdiverses.However,duetosomephysicalcomparablelowinsomecases.Suchlowqualitypropertiesincluderedundancy, dimensionalandlowqualitydata,inthisdissertation,weproposeacomputationalframe-dissertationarefour-fold:Thisdissertationrevisitsthetypicalcompressivesensingframeworkbyintroduc-andnoisyobservations.thatinformationuniformlyprorogateonagraph,werespectivelyproposearandomworkbasedmethodforfeatureextractionandaGraphLacemethodfordamagedimagecompletion.Thesetwomodelsareappliedtobiometricsrecognition.isintroducedtoautomaticallyidentifythecommoncharactersandthedifferencesamongMoreover,thehighunderstandingaccuracyisobtainedwithverylowcomputationalcost-Tohandlevisualinformationunderstandingtasksthatinvolvenoisesand pletenessinthesupervisedlabels,thisworkproposesarobustinformationtheoreticem-beddingmethodintheframeworkofinformationtheory.By izingthemutualmodelimprovestheclassificationaccuracyashighastenpercentswhenthereexistslabelperceptionandunderstanding;目第1章绪 研究意 研究背 数据稀疏结构学 数据简约及降 数据的判别性表 本文组织及贡 引 压缩感知理论的重新审 低秩与稀疏的数学统 非凸p范数的数学极 非凸启发式恢 理论证 问题与背 融合矩阵的建立及特性分 点云融 三维重 本章小 第3章图结构下的视觉信息感 引 随机模型下的特征提取算 随机交互时 交互时间保持策 基于随机模型的生物特征识 信息机制下的缺损视觉信息生 图算 缺损视觉信息修复及理 本章小 第4章判别性结构下的视觉信息理 引 判别性结构下视觉信息解 判别性解 实验验 判别性结构下的视觉信息编 视觉信息的判别性编 局部线性化的优化求 实验验 本章小 第5章信息熵结构下的视觉信息理 引 最大互信息下的判别式投 算法概 信息论下的判别式数据嵌 实验验 最小信息量损失的视觉信息编 算法概 最小信息损失的图指 实验验 本章小 第6章结 本文工作总 未来工作展 参考文 致 声 附录 子序列收敛性证 附录 个人简历、在学期间的学 与研究成 双向梯度下降法(AlternativeDirectionMinimization) 特征包图像编码算法(BagofFeature,BoF) 判别核指派(DiscriminativeKernelAssignment) 最小信息损失图指派(GraphAssignmentviaMinimalMutualInfor-mationLoss) 对数和形式的启发式恢复（Log-sumHeuristicRecovery） 低秩表示，(LowRankRepresentation) 低秩结构学习（LowRankStructureLearning） 多视角立体（MultiviewStereo） 合成孔径(SyntheticApertureRadar，SAR)1章今时今日，信息获取的能力以及方式都在发生着日新月异的改变，不断刷新创造着新的历史。Ntre和Science，分别于 年以及 年以封面文章的形式告示了大数据时代的来临。在这样一个信息的时代，如何对大规模数据行“有效感知”是人类社会在科学技术各领域探索新发现的关键，这其中涉及众值得深入探究的科学问题。结合笔者的研究背景，在视觉信息处理领域，人类一直追求着对物理世界本质特性更度、尺度与分辨率的观测能力，这也谱写了年物理学奖的发展历程：可见光极限至衍射极限的突破（显微观测，色散棱镜至电子、激光光谱仪的发明（光谱观测，射电望远镜（天文观测）等辟了新的尺度、维度空间。进一步，电荷耦合组件的发明实现了光信号的数字化，计算引入视觉信息的感知过程。结合大数据时代的来临，视觉信息处理的时代或许已经来临，并已经开推动众多传统科学问题寻求新的突破。在计算成像领域，Due大学的科学家最近在Nature上撰文，宣称已经成功研制了具有亿万像素的装置。这一突破性地着视觉信息处理大数据时代的真正来临1]。2008年，伯克利大学科学家在Cell上撰文，通过对于大规模信息的感知，突破了静态观测环境的约束，重构并揭示了果蝇细胞进化的动态过程[]。在航天科学领域，美国ASA的科学家通过对光谱，可见光成像设备以及遥感设备等多源信息的融合，对月球的生态环境进行了有效的重构与感知。在物理领域，T的科学家在Ntre上撰文揭示了光学成像的非线性特质。其研究通过数据感知的，放松了波粒二相性的物理先验，揭示了光子成像的非线性特点[]。在显微观测领域，哈佛大学科学家在Ntre上了一种随机光照显微镜，实现了生物上细胞虽然物理世界的可以让我们获取到更度的视觉信息，然而视觉是匀速直线运动。在一个成像周期内，无人机发射接收电磁波并将数据积累，随条件是不满足的，这也就造成了实际情况与数学模型之间的偏差。所以，在因为受到物的遮挡，从而在成像数据上造成了残缺。另外一个值得考虑的情就是数据的冗余，由于无人机成像过程会对地表信息进行时空协同的采样，因此不可避免造成空间分辨度上的冗余。最后，在对无人机视觉信息的理解上，我们同样，生物显微领域获取视觉信息的低质量特性也是不可忽视的。如哈佛大学著名的OM显微成像装置，它以随机光照的形式对生物试体进行多次采样，不同的细胞结构会对不同波长的入射光产生响应。因此，在一次成像过程中，只可获得残缺的视觉信息。另一方面，多次采样，也会造成视觉信息获取的冗余。同时，由于显微成像物理设备和衍射极限等客观条件的限制，成像结果中不可避免地引入了大量的噪声。和无人机视觉系统相同的，需要对生物样本成像数据进行理解，也就势必需要对生物过程赋予语义。但是，在微观世界下对语义的解读以及对自然规律透彻的理解本身就是一个极具的科学问题。视觉数据的冗余：获取的多样性带来了视觉数据的冗余。空间或时间上几何信息可以被多个机同时捕捉到，这就带来了视角的冗余。同时，时间的递进也会带来数据的冗余。一段连续拍摄的中，不同帧之间也就存在着大量的信息冗余。另一方面，数据的维度间也存在着冗余，对于这视觉信息的缺损：物理成像设备信息会因环境的约束在最终的上产客观原因。另一方面，获样本的行为也可能造成视觉信息的残缺。在生物特征识别上，人脸会因为眼镜，围巾等造成遮挡。在生物样造成了成像信息的缺损。语义信息的获取往往来自于的标记。这种标记的方式造成了语义信样本都进行完美的标记。这就无疑地就造成了样本上语义的缺失。另那么，如何有效的处理视觉信息与视觉信息低质之间的，这是本所要探寻的重要问题。综前文所述，信息与视觉已非常紧密的结合在了一起，那么，是否可以利用数据之间的特定关系，通过计算的去感知视觉信息的本在规律的计算模型？3、如何理解视觉信息所蕴含的自然规律？年来的发展历程，我们不难发现，数据处理研究已渗入于计算机领域的每一次。20世纪中叶数值计算（RichardHamming，1969，线性代数（James勃发展（EdwardFeigenbaum，1994。2011年因对概率论以及机器学习领域的突出贡献，JudeaPearl成为了的得主，也为大数据时代下智能信息处理的发展指明了方向。在这样一个时代背景下，视觉信息感知与大数据的不期而遇势必带来领域的交叉和碰撞，从而促进传统科学的长足发展。这些基础计算理论，在数据处理中起着不可或缺的作用，也是本博士 所讨论内容的理论基石。探索了百年的溯求，在这个计算能力卓越提升的年代，似乎又有着更为新鲜着潜在的流形结构[5][6]。这也开辟了流形学习的先河，奠定了近十年来流形学习在计算视觉领域如火如荼的发展。2006年，工程院Donohol在信息论顶级期IEEETIT首先提出了压缩感知的概念[7]。这篇迄今为止已被了6000余次的（schorlar）,详实的阐述了数据维度之间的稀疏结构及其重构理论。该对于数据稀疏结构的揭示，奠定了压缩感知理论在信息感知，信息简约以及信息理解领域的理论基础。2006年Science上深度神经网络的发表[8]，带来了研究数据判别性结构的新热潮。利用判别性结构进行特征学习，带来了机器学习领域新一轮的蓬勃发展，也在工业界了大数据时代真正的来年以及2007年院（PNAS）上的两篇文章[9][10]，揭示了大数据分布的信息熵结构，利用信息的熵结构，研究者揭示了大数据间的网络拓扑结构以及前人对于信息本质的解读似乎都引入到了一个关键问题上，即数据的结构系列基础理论，以探寻大量视觉信息中最有价值的“信息”。广义地讲，有完成对于视觉信息的有效简约,建模以及理解。具体说来，本文考虑了视觉的涵盖矩阵计算，优化，概率推理及信息论。应用层面涉及传统生物特征识别，高精度三维建模，时间序列分析，理解以及无人机视觉（遥感图像本文提出利用数据的结构化信息，通过计算去弥补方面的“先天不足”，以解析真实的海量信息中潜在的语义结构，高效地完成视觉信息献，并在回顾前人工作的同时本的意义及贡献。了广泛的认可]。受到压缩感知理论的启发，稀疏计算已经越来越多地被引入到计算机视觉的范畴。稀疏计算从两个维度上大大提升了数据表达的性能。首先，通过稀疏计算，人们可以挖掘出大量冗余数据的本质表达。另外，数据间也存在着大量的污损噪声。与传统噪声不同的是，污损噪声往往具有较大的量值且仅仅分布在数据维度的某些尺度上，如在本文的第3.3节中，对于有遮挡的人脸识别这一问题的处理中，遮挡部分即可视为大噪声。因此，可以在优化中利用稀疏特性对这类噪声进行惩罚。展开了讨论：信号的稀疏与矩阵的低秩。在2.2节中，通过统一的视角去审xℓ0=argmin∥x s.t.Ax= (1-∥∥ℓ0表示ℓ0范数，其意义在于列举出了向量中的非零元素的个数。A是一组基，在压缩感知中，对于ℓ0最小化问题的求解，可以通过其凸包络，即ℓ1来求解。因xℓ1=argmin∥x∥ℓ1s.t.Ax=y (1-间学习方法来进行人脸识别[14]。除了广泛应用的基于ℓ1范数的稀疏学习，一些来也取得了长足的进步，从而了研究低秩矩阵结构学习（LowRankStructureLearning,LRSL）问题的热潮[16][17]。利用矩阵分析理论学习数据的内在结构已经在许多领域取得了一系列有的成果，例如神经网络[18]、机器学习[19][20]、控制理论[21]、计算机视觉[22]、模式识别[23]24]等。在矩阵秩的分析方面，主成分化[25]已经被引入矩阵秩的分析中来。核范数在数学上定义了矩阵奇异值之和。声的干扰下学习得到数据的低秩结构[16,17]。此类问题可以表示为P=f(Ag(E)，PAE分别是低秩矩阵和稀疏大噪声；f(·)g(·)函数均为线性的。从一个等式中恢复出两个变量(AE)本身是一个问题。但是这种的问题，却仍可以通过优化的方法进行求解。我们考虑下(P0)

rank(A)+λ

(1- P=f(Ag(E)在(P0)中，rank(A)A的秩结构，∥E∥ℓ0ℓ0ℓ0范数分别是衡化它的最小凸包，即把矩阵的秩替换为核范数，同时稀疏噪声通过ℓ1范数进行惩罚。核范数和ℓ1范数分别是rank(·)∥·∥ℓ0的最小凸包。在实际的应用中，通过1的LRL方法可以十分有效地解决许多和低秩结构、稀疏大噪声相关的信号重构问题。然而，当所处理的矩阵变得复杂时，比如在秩相对较高或者受污染的噪声比例较大的情况下，1的R可能无法得到理想的结果。为了增强LR在处理问题时的学习能力，本文考虑利用非凸函数来加强信号的稀疏度。在本 的2.2节中我们提出了og-sum近，并在理论上揭示了在低秩矩阵结构学习问题上og-sum是传统非凸p-范数对于范数近的右极限。结合稀疏计算和og-sum近，本文将该模型应用去解决数据聚类，运动分析以及三维信息融合等这一系列实际的计算机视觉问题。 据降维。数据降维可以有效的处理数据维度之间的冗余并消除数据维度上噪声降维方法是在某些特定的统计意义下，将数据变换到另一空间，在新空间中，义之间的联系，而是直接利用数据间的潜在结构完成数据简约。而判别式降维的方式，是一种有利于数据理解的降维方法。在判别式降维的方式中，任务在于强调简约后数据的可分性。分类是众多数据理解任务的基础，因此充分利用数据及其语义间的结构信息，能够大大提升数据的可解释性。经典的结构化降维方式，势必要追溯到流形学习。流形是一种局部线性的，但是全局非线性的数学抽象。流形学习是刻画数据间非线性关系的有效，它对于外界刺激的编码方式是通过一个网络结构去完成的6]。因此，图学习也就成找到强而有效的数学支撑。最短路径降维[5]、局部保持映射[6]和映射[27]。然而，大多数现有的流形算法不能处理测试样本[28]。它们只是将训练样本投影到子空间，但不能泛化学识别算法。为了泛化流形算法的学习能力，局部保持投影[28]作为特征映射[27]的一个扩展们提出。该算法通过一个线性变换去保持图上的局部连接关如上所述，流形学习着如下两方面的：（1）如何泛化图上的学习结果到训练样本之外的测试样本;以及（2）如何找到一个鲁棒的测度来揭示图上两两节点间的拓扑关系，无论这两节点是否直接相连。为了解决这两个问transformation,CTG）。在我们的CTG模型中，采用随机的交互时间(CommuteTime,CT)[29]作为一个鲁棒的指标，对图表上的所有节点对之间的相似性来进行评价。CT是一个概率的距离，该距离记录了一个随机者往返于图上的一对节点所需的平均时间。在数学上，这是一种概率论下的期望距离，因此其对噪声非常鲁棒。用CT代感。受LLP的框架[28]和图嵌入(GraphEmbedding,GE)[30]的启发，我们提出一套优化框架，来隐式地在一个低维子空间中保持流形上的交互时间。CTG算法应用于解决两类计算机视觉中的常见问题。首先，因为CT的鲁棒特性，CTG算法应用于人脸识别领域（节，在国际通行数据库中的表明，基于CTG变换的投影算法可以有效的在人脸上抽取特征，在5.3节中，CTG变换与信息熵巧妙的联系在一起去考虑样本及其语义的信息结构，提出最小信息量损失下的视觉信息编码算法，并将其用于图像理解。统计学习的方法，例如线性判别分析31][]和典型相关分析[33][34]都是一些关于数据表示的早期想法。但即使在它们被提出几十年后，这些算法的有效性和鲁棒性也未曾受到质疑。线性判别分析是判别式模型，它采用著名的isher作为嵌入的依据。典型相关分析是一种分析多源数据的方法，它将不同的数据映射到同一个隐空间，在这个隐空间中不同源数据有着最大的关联性。文献]给出了典型相关分析处理判别性数据降维的基本流程。总的来说，CCA的目的在于找到一个投影将数据变换到隐空间中去，从而在这个新的变换空间里揭示数据及其语义之间最大的关联性。流形学习中也可嵌入判别性的特质，例如图嵌入算法[28,30]以及其变形的算法[24,36]，都是在寻找一个投射矩阵，能够在低维隐空间中尽量保持空间中的来说，这些方法通过构建图拓扑得到正则项以约束相似的特征拥有相似前文所探讨的两类结构化计算模型，是对数据本身的低质特性的有效处理，更近一步，本文也将考虑数据语义的低质特性，即如何建立有效的计算模型去刻画数据及其语义之间的内在结构去完成视觉信息理解的任务。本文主要借鉴判别式在概率框架下，本文将通过多元逻辑回归（Multinomiallogisticregression，L)0]来刻画信息和语义之间的概率关系。L通过最小化联合损失去优化出最优的回归参数来描述样本的可分性。在本第4.2L的组成部分被嵌入到一个产生式的概率表达中。在概率框架下，L可以成功的揭示不同图像间差异，从而发现哪些图像信息有助于人类认知，哪些图像信息代在优化框架下，费希尔准则（ishercriteria）是一种经典的判别性目标。ishe准则通过最大化类间距离并最小化类内距离的方式建立优化目标。本文第4.3节将利用isher准则从一个新的角度定义基于核码本的视觉信息编码方法。在典型的核指派中]，字典里的所字享有同样的权重。我们的方法轻微地修改了这种设定使得不同的码字能够有不同的权重。为了学习得到这组差异性的权重，本文提出最优化训练数据的ishe判别准则。尽管这种想法本身清楚易懂，但对其优化求解确是非常的。其学习过程依赖于一个高度非凸和非线性的优化目标。在优化方法上，本文提出局部线性化非线性部分的算法，从而来学习具有判别特性的权重。除了上述的两类判别式思想，本文同样从信息论的角度去揭示图像及其语义之间的结构信息。曾有研究者提出互信息是描述数据可分性的一个重要准则。在本文第5.2节中，结合逻辑回归，将提出了一个鲁棒的信息论嵌入算法（RstnformatinThereticmbeddin,IT。该算法通过最大化隐空间中数据与标记的互信息，在学习数据嵌入模型的同时得到性能良好的分类器。由于联合优化的特点，我们的模型在数据标记部分缺失情况下能够灵活地扩展到半监督的模式。更为重要的是，由于概率框架的灵活性，T学习过程中并不会导致分类器的过学习问题，同时还可以在优化中自动减轻标记噪声的影响。来揭示大量局部描述符之间的非线性关系。同时，在隐空间中优化语义和特征的互信息结构来增加指派后图像特征的可分性。与RIT模型不同的是，在这项工作的是通过非参数估计的方法去建模隐空间中的概率密度，从而完成信息量的估计。针对视觉信息低质的特点，本文主要从以下四个方面展开讨论。前两方感知理论，提出了一套以log-sum近为的压缩感知算法，在大量冗余，污损考虑视觉信息数据维度之间的冗余及噪声，结合物理学中的场论将数据间的作用描述为场扩散的过程，并在图的抽象结构下提出视觉信息简约及缺损视判别性图像编码算法在一个优化的框架下对图像信息进行有效的简约，大大提升了计算机对于视觉信息的理解能力。第五章考虑到一个更有的问题，人工赋予的语义信息本身也不完美。针对此，在视觉语义缺损及错误的情况下，本文考在视觉信息的稀疏结构研究领域，本文提出了视觉信息的“有效感知”理论。在理论研究方面，本文重新审视了经典的压缩感知理论，提出了一套以log-sum函数为的近算法，并在数学上将信号稀疏与矩阵低秩泛化到了统一的数学框架下。在低秩矩阵结构学习的框架下，本文进一步揭示了log-sum函数是传统ℓp范数对于ℓ0范数近的极限。从算法角度，本文在凸优化的框架下寻求到log-sum近的最优解，并在理论上证明其收敛性。该算法息生成以及视觉信息降维等领域。以及“判别性编码”方法。在的“判别性解析”方面，本提出了一个分层的模型，通过概率推理的有效的解析出不同所具有的上，通过判别结构挖掘，本文所判别性编码算法，提升了已有算法识在追溯视觉数据的信息本源方面，本文研究了数据及其语义间的信息熵结构。在信息论的框架下，引入互信息作为揭示判别性结构的优化目标。通过概率论，信息论及优化的，本文在联合优化的框架下提出了“鲁棒信投影”算法，可以有效处理视觉信息语义中存在的噪声及残缺。数据背后或许存在着本质的稀疏结构。在本章中，通过低秩特性和稀疏特性两类结构先验去有效感知冗余数据背后的稀疏本质。本节内容于[42]。为低秩污损矩阵恢复问题考虑从稀疏大噪声的干扰下分解获得一个低秩矩阵，可表示为P=A+EA是一个低秩矩阵，E是稀疏噪声，P是从现实世界设备（比如相机、传感器等）中观察得到的实际数据。在大多数情况下由于E的干扰，P并不具有低秩特性，那么如何从具有大噪声干扰的数据中恢复出低秩的矩16]和ght等人提出了主成分追踪PrincieCoponentPit,PCP)1范数和矩阵核范数的共同约束下完成这一问题。低秩表示[20](LowRankRepresentation,LRR)是解决子空间聚类[43]的鲁棒工具。常用的LRR模型可以表示为P=PA+E，其中P是原始的混合数据，A是表示不同组数据相关性的仿射矩阵，E是这种表示方法的噪声（也称表示残差。在LRR中[20]，矩阵A被认为是低秩的，表示残差E被看作稀疏噪声。不失一般性地，上述两类问题都可以泛化成（1-3）所表示的低秩矩阵结入低秩结构学习框架中，并讨论两种被广泛应用的非凸项，即ℓp(0<p<1)以及对数和项(log-sum)。相应地，后文将提出两种非凸模型―ℓp范数启发式恢复模型(p-normHeuristicRecovery,pHR)和对数和启发式恢复模型(Log-sumHeuristicRecovery,LHR)用于解决污损矩阵学习的问题。理论上将分析揭示这两类模型的关系，并证明LHRp0+pHR模型的极限近。因此，LHRpHR模型具(rniii,算法来求解上述非凸启发式模型。MM算法采用一种迭代的形式，首先将目标函数中的非凸项替换为其对应的凸上界，然后最小化所建立的新的目标函数。通过这种变化，非凸问题就转化为一系列重问题。后文将证明通过MM算法，上述非凸优化将会最终收敛于稳定的驻点。在应用层面上，LHR将被用来解决数据分析和计算机视觉领域的多种问题，如光照分离、运动分析和聚类。存在大噪声的情况下，矩阵融合算法大大提高了已有MVS算法下点云融合的精度。这里首先将式(1-3)表示为一个半正定问题(SemidefiniteProgramming,SDP)。可以明显地看到，典型的LRSL问题的本质其实是一种普通的ℓ1启发式优化。如前所述，基本的优化问题(1-3)是非凸的，并且由于其离散特性，对此问题的直接优化求解是NP难的。为了使(1-3)可解，已有方法往往通过其凸松弛，在凸优化的框ℓ1范数替换ℓ0范数。通过凸松弛，(1-3)中的问题可以被s.t.P=f(Ag(E)

(2-

σi(A)

A矩阵的核范数，具体为

∈(Y,Z,X)∥X∥∗

≽

(2- 其中YRm×mZ∈Rn×ntr(· ≽(Y,Z,A,E) ≽

(2- P=f(Ag(E)2.1，可知YZ均是对称半正定的。因此，YZ的迹可以表示为ℓ1范数的特定形式，即tr(Y)=∥diag(Y)∥ℓ1diag(Y)Y对角线上1 (∥diag(Y)∥ℓ+∥diag(Z)∥ℓ)+λ∥E∥ℓ ˆ={(Y,Z,A,E) ≽0,(A,E)∈ (2- (AEC根据引理2.1，在(2-1)中具有两种范数的凸问题已经被成功地转化为只有ℓ1范数的优化问题，因此这可以被称为ℓ1启发式优化。ℓ1范数是ℓ0范数的最小凸包，但是之前许多的研究工作[45][46]已经表明利用ℓ1范数近ℓ0的稀疏度具有较大的凸的ℓ1泛数更接近ℓ0范数的非凸函数。然而，如果使用非凸启发式项，不可避免1)2)如何有效地求解非凸不失一般性地，本文介绍两个非凸项来加强(2-4)中模型的稀疏度。第一个被引入的非凸项是非凸的ℓp范数（0<p<1）。直观地，它处于ℓ0范数和ℓ1之间。因此，它比凸的ℓ1范数具有更好的稀疏表示能力。我们定义非凸ℓp范数的p次方为fp(X)=∑ij|Xij|p0<p<1并将其代入(2-4)，得到如下ℓp范数启发式恢(pHR)Hp(ˆ)=min1[fp(diag(Y))+fp(diag(Z))]+λfp(E) (2-从以上的pHR(2-4)的差别。pHR模型使用了非凸的ℓp范数去替换(2-4)中的ℓ1范数。根据pHR，可以得到另一种具有更强稀疏惩罚性能的非凸启发式模型。显然，∀p>0，最小化pHR等价于：minF(ˆ)=1[Hp(ˆ)−(1m+1n+ (2- +1∑m|Y 1 |Z + (2-6)中的优化问题与(2-7)中的是相同的，因为相乘的系数参量1是一个正的常p数，而且1m1nλmn’Hˆspital规则，可以得到limxp−1，其中∂f(p))代表f(p)，其中∂f(p))代表f(p)p的偏导。通过limF(X)

对数和启发式恢复(LHR)模型HL(ˆ：(LHR)HL(ˆ)=min1[fL(diag(Y))+fL(diag(Z))]+λfL(E) (2-i对于任意的矩阵X∈Rm×n，对数和项被定义为fL(X)=∑log(|Xij|δ)，其中δi根据(2-6)与(2-8)，可知LHR是pHR在p取极限0+时的特殊情况。当0<p1p越接近0，ℓp优化的稀疏性能也就越被加强。同时，不难发现当p等于0时，pHR就变为(1-3)中的不可解离散问题。值得讨论的是，当p0与p0时，pHR对应了两种不同的目标函数。这样的发现并不违背上述推导，因为当p=0或者p<0时，从(2-6)(2-7)式中的等价性就不再满足。这也正是为什么需要在极限p→0+中的0上方增添一个正号的原因。由于LHR更强大的稀疏化能力，后文的讨尽管前文引入了强有力的log-sum来加强稀疏度，但同时也在目标函数中引入了非凸项。因为对数函数在R++=(δ∞)区间是凹的，所以LHR模型就是非凸的。在大多数情况下，非凸问题是十分难解的。幸运的是，fL(·)的凸上界很容易通过其一阶泰勒展开来定义。因此，本节将引入最大值最小化（MM）算法来求(MM算法将上述难题转化为一系列简单的问题进行依次求解。最大化步骤中，MM算法计算非凸目标函数的凸上界；在最小化步骤中，MM算法最小化上述放缩后得到的上界。2-8)中各项的一阶泰勒展开式均已定义在附录A.1中。类似的矩阵的推导也可在47]中给出。因此，可以构造LHR的上界并转化为以下优化问题：|ˆ (2-iλ∑ij(ΓEδ)−1Eiji(2-9)中Xˆ{YZAE包含所有需要被优化的变量，数集ˆ{ΓYΓZΓE}}在之前的一些关于MM算法的工作中[45,48]，第t次迭代中所需参数Γˆ由上一次迭代中Xˆ的最优值决定。, i

(WE)ijEi WY(Z)=(ΓY(Z)+δIm(n))−1/2(WE)ij=(Eij+δ)−1∀ij。请注意tr(W2Y (2- 2 WYYWY WYAWZ ≽0 (WYAWZ)T P=f(Ag(E)s.tP=f(Ag(E)

(2-在(2-13)中，噪声项中的运算符⊙表示两个变量的对应元素积，即对于WE与E：(WE⊙E)ij=(WE)ijEij[44]，可知Y和Z的最优值为Y∗=UΣUT，Z∗=VΣVT。其中U和V可以对A进行特征值分解后得到，即A∗=UΣVT。因此，权重矩阵可定义如下：WY=(UΣUT+δIm)−1/2，WZ=(VΣVT+δIn)−1/2。需要指出的是式(2-13)同样适用于求解pHR问题，仅仅需要使用不同的权重矩阵WYdiag((UΣUTδIm))(p−1)/2,WZdiag((VΣVTδIn))(p−1)/2WE[(Eijδ)(p−1)] 题。同时，(2-13)中的凸目标函数由一个核范数与一个ℓ1相加得到，并可通过凸(2-8中的目标函数被定义为H(ˆ；(2-9)中的替换函数被定义为TXˆ|ˆ)。Xˆ是所有H(ˆt+1)≤H(ˆt)

Xˆt,MM算法可使非凸目标函数H(ˆ){ˆ0ˆ1...ˆt}引理2.3的证明包含两步。首先，我们需要证明在MM算法的迭代过程产生ˆtkˆA.32.3。2.1通过MM优化算法，LHR这一节已经证明了通过MM算法，LHR模型可以收敛于一稳定点。然而，由于LHR果给定一个较好的初始点，我们算法总可以通过迭代寻找到理想的优化结果。一种值得推荐的初始化方式是将1启发式模型的最优结果作为LHR的初始值。在这一章，LHR将被用于污损数据的低秩结构恢复，然后将其恢复结果与主成分追踪算法PrincieComponentPit,PCP)进行对比。在不同的场合，PCP也被称为鲁棒主成分分析（RostPrincipeComponent ysis,A。s.t.P=AE

(2-由于在核范数中引入矩阵，因此A的更新无法直接利用核范数的闭式解。受[20]的启发，可以在(2-14)中引入另一个辅助变量J，并求解如下优化：s.t.h1=P−A−E=h2JWYAWZ0

(2-使用增广日（AugmentedLagrangianMultiplier，ALM）算法[49]，可以 L=∥J∥∗+λ∥WE⊙E∥ℓ1+<C1,h1>+<C2,h2>+(∥h1∥+∥h2∥ 其中<,>是内积运算符，C1和C2是日对偶变量，其可通过对偶变量递增的方式更新。(2-16)包含三个变量，即J,EA。通过ALM，上述联合优化问题可以通过E最小化,J最小化,A最小化和对偶递增这四步进行求解。详细的推导过程类似于[22,49]中的步骤，故而在本中不展开讨论，只将求解的迭代步骤在算法2.1中给出，其中sα(·)dα(·)分别被定义为向量阈值化操作和矩阵阈值化操模拟实验来检验它的有效性，并与PCP方法进行比较。为了对比的公平，我们采[16m×n秩为rA∗。不是一般性地，这里的仿真仅考虑方阵的情况，即mn。稀疏E在矩阵元素上均匀产生，污损的量值从区间[-100,100]损数据矩阵通过以下方式产生：P=AE∗，其中A∗E∗方便，我们定义秩比率为η=

；污损率为ξ

文献[16]表明PCP方法在η+ξ<0.3511t:=1E0:=1∀ijW(1)Im(n)i2 Z C00;µ00;ρ1;k1;A0E0 while5Ek=iλµ(WE)i16Jk=d1k−1W(t)+µ−1Ck)Z27Ak=Ak−1+(t)(hk+ (t)+(hk+µ−1Ck)]12218Ck=Ck−1+µkhk 19Ck=Ck−1+µkhk 2 k:=k+1,µk+1=t:=t+until收敛输 :(A(t),E(t))低秩矩阵。为了证明LHR模型的有效性，这里的实验直接考虑更为的任务，设置η+ξ=0.5。为了比较，本文将PCP(p=1)模型与pHR(p=1/3，p=2/3)和LHRp→0+) 表示恢复精确度 表示恢复矩阵从结果中可以明显地看到，与PCP相比，LHR模型可以从具有更高秩和更大噪声的污损数据中精确地恢复出低秩矩阵。R模型在大部分情况下也可以正确地恢复出低秩矩阵，但是其恢复精确度稍低于LHR。表2.1中同时也记录了算法的运行时间。这些实验均是在配有2.3GHZ的CPUB的内存的台式机上运行的。个变量来测试PCP、pHRLHR的可行域。实验是在均匀分布于[−100100]疏噪声干扰下的400×400确度大于1%即

>0.01)时，就认为算法恢复失败。ηξ两个参数分别从 rank(A∗)=0.4m||E∗||ℓ0= rank(A∗)=0.1m||E∗||ℓ0=m m

8.7e- 本文得出了和[16]PCP的可行域边界大概符合ηPCP+ξPCP=0.35的曲线；LHR的可行域边界大概符合ηLHRξLHR=0.575的曲线。尽管pHR的求解LHR，但它仍远远好于PCP的求解能力。当p=1/3p=2/3时，边界等式就分别变为ηpHRρpHR=0.52ηpHRρpHR=0.48。从这个实验可以明显地看到所LHR算法具有最大的可行域，表明LR可以求解PCP所无法解决的更为的问题。进一步，LHR算法将用来处理真实世界的视觉信息，并证其优越性。在LHR的第一个应用中，本文将考虑人脸去阴影和光照这一问题。根据[16]中的方法，可以将不同光照条件下的相同人脸数据置于矩阵P中的不同列中。本实验是在Yale-B扩展数据集中进行的，在此数据集里每张人脸的分辨率为192168。本文分别使用PCP和LHR求解污损矩阵P。在恢复之后，阴影、高光以及其它的反射光都被去除在噪声矩阵(E)中，低秩矩阵(A)中即为计算得到的纯 实验结果如图2.2所示，其中从左到右每一个子图分别是e中的原始人脸、PC恢复出的人脸、pR(p=1/3)⃝1恢复出的人脸以及中，当人脸图像中存在较强的阴影时，LHR性能明显优越于PCP。然而，在图2.2(a的结果中，两个非凸模型之间并不存在着显著的差异。但是图2.2(b)显验证了LHR比其它方法的优越性。A，前景被去除在噪声矩阵E中。实验使用[50]中的真实值进行数值评估 这里只给出p1/3时的求解结果，因为在之前的数学模拟中pHRp1/3)比pHR(p2/3)具有更高的Lab(886帧Seam(459帧 为了计算的精确，每张图像的分辨率都被归一化到120×160的分辨率，并且所有的帧都被转化为灰度级。这里使用的标准包含了太多帧，会导致矩阵过大。虽然从理论角度分析，上述两种方法均可以求解任意大的矩阵恢复问题。但不幸的是，对于实际应用，过大的矩阵常常会超过的内存限制。因此，对于每个，原始的大矩阵被分割成列数小于的子矩阵并将这些矩阵分别恢复。被分离出的前景以及其真值如图2.3所示。从这些结果可知LHR较之PCP可以从污损数据矩阵中去除更大的噪声。图2.3中的三个序列也证明了这样的结论：LHR从中恢复出了更为完整的物体。此外，从图2.3(c)也可明显地看光照变化。PCP对于这些小的变化十分敏感，会景中分离出的小噪声。尽管在点。因此，本文仅仅使用混合(MixtureofGaussian,MoG)[51]作为对比基准。在MoG中，5个项被用于图像中每个像素的建模。进一步地，实验通过计算III错误。FNR代表某种方法对前景恢复的精确程度，FPR表示某种实验结果显示，PCP和LHR的求解表现远远强于oG算法。同时，LHR具有PCPpRNR，表明LHR比它们能够更好地检测前景物体。然而，在high和seam两段中,LHR的FPR比PCP和pH稍高。一个可能的原因是这两个中含有太多的移动阴影，因此物体和阴影都被当做噪声分离了出去。在帧中，这些阴影被当做了背景。综上，LHR可以从一个低秩矩阵中分离出的噪声，因此会得到一个较低的FNR值。前文讨论了LHR算法用于低秩矩阵恢复，在这一节里LHR将被应用于另一问LR)[20]中，LHP=A+射矩阵A是低秩的，噪声E是稀疏的。本节将首先介绍如何使用联合优化方法来求解非凸启发下的LRR问题。然后，LHR启发下的LRR模型将被应用到运动分割及聚类两个实际问题中。 PPAE

(2-s.t.b1=P−PA−E=0b2JWYAWZ0。

(2-通过增广日的方法，(2-18)中的优化问题将可被求解。LRR的求解与LHR非常类似，只是对于每个变量的更新法则稍有不同。算法2.2中给出公11Ek=i(WE)i 12Jk=d−1µW Y(t)+µ–1Ck23Ak=Ak−1+γ[W(t)(bk+µ−1Ck)W(t)+PT(bk+ 21//4Ck=Ck−1+µkbk 15Ck=Ck−1+µkbk 2则在这一小节中，LHR应用于Hopkins155数据集[43]中的运动分割任务。Hopkins155156段要任务是将每种运动分类到其对应的子空间中，这样每段都对应于一个单独实验将LHR及LRR与其他的一些用于子空间聚类的算法进行对比。这些算法包括随机抽样一致算法(ANdomSeConsesSC)]、广义主成分分(eneraizedPCA，GPCA)53](lbaeAn-it，LSA)[43](LaicayLrdCluin，)5]以及稀疏子空间聚类(SparseSsaceClusterinC)]。ANC是一种通过迭代区分正常值和离群值来进行数据聚类的统计学方法。GPCA是一种利用数据点法向量来对混合数据进行聚类的代数方法。LSALLMC算法，它们假设某一点及其相邻点分布在一个子空间内，并通过谱图的方式来进行聚类。SC假设数据间的仿射矩阵是稀疏的，其通过归一化切割的方式对数据进行归类[56]20中推荐的程序和默认参数设置来进行实验。对于LHRλ=.。为了得到更好的聚类精确度，在20中，Li等人对学习得到的低秩矩阵结构进行一些后期处理。例如，在得到表示矩阵A后，对该矩阵进行了额外的PCP处理以加强矩阵的低秩性。这样的后期处理无疑会增加子空间聚类的精确度。然而，本文的主要贡献在于将LHR模型用于低秩结构学LR模型不进行任何的后期处理操作，以强调算法本身的性能表现。Hopkins155数据集在一个序列中包含两空间情形，即两种运动类型和三种运动类型。表2.3给出了两类样本分类错误率TO)、三类样本分割错误率(THREE)以及所有样本分割错率(ALL)。从结果中可以看到，对于运动分割，基于稀疏理论的方法通常会优于其它算法。在三种稀疏方法中，LHR具有最好的聚类精确度。然而，其精确度仅仅比LRR有了非常小的改善。如20]所述，运动数据仅仅包含小的噪声，LRR90%的理想结果。借助于一些后期处理操作，精确度还可以被进一步改善。因此，为了突出LHR数据的低秩表示问题方面的有效性，下文将考虑一种更为复杂的问题。 在现实生活中，一种最难分析的数据结构是价格，其会受到公司动态、流言和全球经济氛围的剧烈影响。因此，对经济数据的数据挖掘是十分的。这里将讨论如何把非凸的LRR模型应用于聚类任务中（基于它们的行业分类M和.an分别被分类为计算机系统类别和银行类别。通常认为相同类别的会具有相似的市场表现。这个观点被许多广泛地用于统计。我们认为相业类型的分布在一个子空间上，因此聚类或者说 分类的目的就是根据一支 的历史价格来确定它的行业类型。本实验数据分别来自于位于纽约和的两个全球中心。在每个中心，我们挑选具有最大市值的10种行业。纽约中心的价格来自于雅虎金融，中心的价格来自于金融。然而，在雅虎金融上并没有给出所有的历史价格。因此，在纽约中心中选取了76支并将它们分为10类，每类包含7到9支；在中心选取了96支如前所述，价格可能会存在或者暴涨的现象，并由此产生原始数据中的离群值。同时，不同的价格也是多种多样的，并不能在同一个数量级上来进行计算求解。为了方便分析，在实验中使用文献[57]介绍的归一化方法对股˜(t)=p(t)−µα(t) (2-其中p(t)是某只在时间t时的价格，µα(t)和σα(t)分别是价格在[t−α,t]时间段内的平均值和标准差。三类的归一化后的价格在图2.4中给出。在每个行业中，不同颜色的线代表不同的。在归一化之后，为了提升计算效率，可以通过PCA将价格进行从R200降维到R5。 使用不同的子空间聚类方法对这两个中心数据的聚类错误率列于疏方法中，LHR将LRR的准确率提升了8%左右。尽管LHR在所有的方法中表现最好，但其对纽约和中心聚类的精确度却只有63%和61%。这 市场 57.3的聚类精确度并不是特别高。这可能是由于真实数据与真值包含了许多不确定性。例如我们可以观察图2.4最下面的无线通信行业的子图，在同一行业中，绿色曲线所描述的指数与其他的表现很不同。但是本实验结果足够验证LHR方法对类行业子空间聚类的有效性。如果没有智能的处理，那么求解的精确度可能只有10%。尽管真实数据如此复杂，但我们LHR算法在非监督的情况下依然可以得到高达62%的聚类精确度。及机器学习中的几类应用。利用低秩结构学习的两大优势在于：1)降低数据冗余性和2)有效地处理数据中的噪声。这两大优势直接启发我们去处理一个更为实用低秩结构学习这一有效的数学工具去有效地融合三维点云信息。本节内容注的热点问题之一。MVS考虑的是如何利用2D信息，通过相机模型去恢复出行导航以及产业。现今科学研究发展而言，一种被广泛认可的MVS方法是基于深度图的立体重建。深度图，又名点云是利用一堆离散的“点的集合”去近物体的深度信息。因此，形象化地，可以将这些离散点的集合称为“点云”。为点云（深度）的估计，往往需要一对或者多对相机。利用成计算机算法，严格意义上应该是对于机的标定。但是为了描述简洁，这里姑且将之称为标为在VS系统中，为了获取完整的物体信息，往往需要在物体周围利用环形机阵列密集地对物体采样。因此，不可避免的是，同一个世界坐标下的信息，可个捕同信将度复出来。同时，利用计算机视觉算法需要多个步骤，包括机标定、特征匹配及深优化。任何一个步骤中的误差都可能对最终深度的估计造成影响。可见的信息，未知元素为该视角不可见的信息。各视角得到的深度向量进都是通过这种方法求取的。考虑两幅视图:I(TAR)及参考视图I(REF)们定义视差向量

来表示从目标视图上的像素xxΓ定义了图上的目标区域所在的位置所以WΓ=,∀x∈Γx场,包括了Γ受到前人光流工作的启发[61WΓ可以通过最小化如下函数得到E(WΓ)=ED(WΓ)+αES (2-ED(WΓ)ES(WΓ))∫E(W)

(|ITAR− |2+γ|∇ITAR− (2-

(xω其中ITAR代表了目标视图上像素位置x的亮度， 是参考xω (x+→xω二项,即一阶梯度信息,保证了算法对光照的鲁棒性。由于多种不确定因素，比如])∫ES(WΓ) ΨS(∇ωx)dx (2-Γ[61]ΨS(·通过总体差异（total式子(2-20)的优化可以转变为一个欧拉-日方程求解的问题。关于这一点的详细说明可参见[60,61]。在得到了两个视角的视差之后,在机参数已知度图。这一点在[60]中有详细说明。通过前文算法估计出的深度具有很多的噪声。在矩阵融合之前,将首先利用NCC[60,62]中的建议首先根据NCC度量的值去选择那些好的深不连续点。如果一个深度点周围数的邻居,那么这个点将被视作为不连续点，并且将被滤除掉。如果一个点少于0.5n的邻居，那么这个点将被移除。n是所有点的邻居数量的平均值。不精确解。如果一个点的法向(利用其邻域信息估计)和机中心连线的夹的估计并确，更为准确的深度或以在其他视角下估计得出。在介绍如何建立融合矩阵之前，这里将首先定义一些常用的数学字符。在后文中,Ck来表示第k个相机，I(k)代表了这 机所拍摄 。其中 代表了I(k)中的x位置。像素I(k)所对应的三维信息为dk。离散点的集合定义为 x{dk∀xΓk。在实验中dkI(k)I(k+1)x(a)可见性分析 图2.5拍摄系统由于遮挡和机摆放位置的不同，每个机的可见性非常有限。对于视对于C2,其可见蓝域及黄域(AC)。黄域是两个机同时可看见的重合区域⃝1。Ck可以看见物体的全部,那么可以定义被这个视角所得到的所有点的信PkBD,为Pk这个向量中的已知元素。不能被这个相机所看到的元素,即DB(反时针方向)则被定义为未知元ˆ=[P1,P2,P3,...Pn] (2-在不完整矩阵ˆ中,每一列代表了一个机所能描述的点的信息。而每一行表示了物体上相同的深度信息。值得说明的是每个深度信息都是通过三维坐标:x,y和z来描述的。因此,将得到三个不完整的融合矩阵分别定义为ˆxˆy,ˆz。但是,

如图2.5(b)所示,我们定义I(k)所对应的深度为dkdk pI(tIt⃝2。由于噪声和估计误差的存在，所找到的对应不一定是一种严格意义下精确的配准位置。所以,我们在投影点的R-邻域位置内继p续搜索最优的匹配信息，即图2.5(b)中的粉红位置 p 如果投影的像素不是一个整数像素位置，我们就依照最近的邻域信息找到整数位置p xxdk,t=argmin

–

(2-x

x xdk,tδ,即可认为这两两点间阈值过大,所对应的矩阵第t列中该元素位置就被认为是未知。xx对于图像I(k)中每个元素x及其所对应的三维信息dk,我们在所有剩余I(t),t,k上遍历dk,t。如果仅仅相机kx−1kk+1k+4可以检测到该点信息,x那些不能看见此信息的相机,(q∗表示)。对于那些已经被检测到并填充到矩阵里的深度信息其在图像上所对应的二维像素信息It将被定义为已检测点。q前文的描述了所建立的融合矩阵是不完整的。本节将融合矩阵的另(a)噪声 (b)偏移噪声 图2.6MVS工作中点云的噪声及误差观测矩阵里的第一种噪声就是噪声，这种噪声表示在图2.6(a)中。被恢复出的点(蓝色点)都分别在真实信息周围的某一邻域中(将误差距离在图2.6(a)中标记为r)。数学上，噪声NG可以通过一个零均值的正态分布去表征，即NG∼N(0,σ2)。第二类噪声可以定义为偏移噪声（biasnoise）。偏移噪声主要由于标定误差所引起。在图2.6(b)中,PG,通过一个蓝色三角形去表征。然而,由于标定误差，它被错误的标定在了PC的位置上。在图中用一个红色的三角表云(如图中红色虚线表示)都距离真实位置存在一个r-偏移。在图中通过蓝线来表征物体的真实位置。对于偏移噪声，可以通过一个r-均值的正态分布去描述，即NB∼N(r,σ2)。2.6(c)所示,绿色的散点代表了这些野值。他们距特定的分布，所以可以通过一个均匀分布去描述，即NO∼U[a,b]U代表了均匀分布并且a,b是这一均匀分布的上下界。本第2.3.1节的推导。具体形式也可参见笔者之前的[22]。

此说明的是参数是δ(见(2-24)及其后描述)。它控制了建立矩阵过程中一行元素的噪声容限值。它与最终建立矩阵的行数以及矩阵中未知元素的比例直接相关。根据经验，我们控制δ以保证最终建立的融合矩阵中有5055的已知元另一个需要的问题就是用矩阵恢复的算法处理大规模的深度点云信息的计算复杂度。理论上说，本文所框架可以处理任意大规模的矩阵。但是，从实际操作上讲，大规模矩阵的恢复需要极大的运行内存。因此，在实际应用中需要将一个大的矩阵拆分成若干小的矩阵去运行。它们的恢复可以调 用的分布式模块去计算为了验证PC算法可以有效的恢复一个融合矩阵，我们首先在低秩矩阵上直接加上噪声，以观察恢复算法的效果。这里所用到的真实模型是PL的ontin-P11，该真实模型通过三维扫描仪获取。因为真实的喷泉模型过大，实验仅仅选择该模型的中间部分运用在实验中。喷泉两边的墙面过于平坦，但是中间部分却15个离散点。这些散点的集合被定义为Π，并且其中任一个点定义为i,πi∈Π。对于融合矩阵，假设在喷泉模型周围有1⃝1。进一步地，我们假设Ππ可以被nn是一个从到1假如一个随机数t被随机产生了，当前点πk就被认为可以被第t个相机看见，并且矩阵中的第tk个元素将被指派上一个值πk+ε代表了被加在真实深度上的噪声。根据前文的讨论,声可以被分为如下三类：、偏移噪声及野值。因为先前假设了一个点只能被n个相机所见，所以在第k行中只有n个元素被定义为已知，其他均为未知。cc对于所建立矩阵中的已知元素，计算其均值µc及标准差σc。在实验中，所的从N,σ2/100的分布并且噪声被加在所有的观测元素上。偏移噪声由于相机的标定参数所引起，所以它仅仅被加在融合矩阵的一些列上。在实验中，列被随机选取出来作为被偏移噪声所污染的相机。偏移噪声服从分N±µc/1σ2/100)。其中，±控制了偏移的方向。对于野值，其服从均匀分布[−0.4µc.4µc]并被加在20%的观测元素上。cc对于融合矩阵，本实验通过三种方式去恢复它。首先,利用PC并且将融合结果提供在图2.7(a)中。为了对比，再利用1恢复算法以及平均恢复算法去恢复融合矩阵。ℓ1恢复算法是指直接采用ℓ1范数作为优化的目标，而不考虑使用非凸近来增加惩罚的稀疏性。对于平均法，每行的均值将被填充在该行的未知元素中。相应的实验结果提供在图2.7(b)和图2.7c)中。因为该融合矩阵是仿真产生的，所以可以知道每个元素上的真实值。三种恢复算法的精度同样提供在图2.7中。从视觉效果对比和精度对比上，都可以看出LPC算法获得了最好的恢复效果及融合效果。在这一部分中，噪声直接被加在了融合矩阵上。但是，所矩阵融合算法却包含了两个方面，分别是融合矩阵建立及PC恢复。这部分的实验探讨只验证了第二部分，即PC算法的有效性。在下一节中，噪声将被直接加在深度图上，去验证整个矩阵融合框架的有效性。 在EPFL的喷泉数据集上，提供者就提供了11个视角的二维。因此，在这里的仿真，我们也假设(a)LPC(5.4e− x维模型根据机参数反投影到11个视角，并据此产生了11张深度。对于第t张深度。在本实验中，真实模型下采样后可以得到总共1.17×106个散点。x根据前文所述，三种噪声将被加在产生的深度图上。在加在噪声之前，先要计算所有点的均值µall及标准差σall。首先，这三种噪声将被分别加在深度图上，即一次实验中只产生一类噪声。对于所加的噪声，其服从正态分 布N(0,σ2/100)N(±µall/40,σ2/100))。方向±被随机的赋在一张其分布服从[−µall/20µall/ 2.5中。在该表中,δ是建立融合矩2.5噪声类型 维扫描仪获得的真实数据，可以量化地评测融合结果。精度评测结果在表2.6中离（单位为米 元素的平均值。从实验结果表明，该算法可以有效地处理噪声。却无法传统矩阵恢复（TMC）:TMC代表了传统矩阵恢复算法。本文利用[58]中公布的FPC(FixedPointContinuation算法去恢复这一矩阵。FPC算法的噪声容限非常有限，它并不能处理观测项上含有噪声的情况。实验表明，FPC算法噪声的融合矩阵上无法得到融合结果，表格中相应位置被标记为NA。与平均方法相比，TMC可以更好地处理噪声及偏移噪声。野值。其在偏移噪声及噪声的处理上，也具有不错的表现。但是融合精LPC:LPC在除了噪声的情况下都取得了最好的结果。当三种噪声都存在时,LPC可以显著提高其它所有算法的融合精度。前文中的实验分析都是在人工加噪的深度图上进行的。本节将在由计算机视觉算法产生的真实深度图上验证我们的融合算法。EPFL数据库中提供的二维具有非高的分辨率，为了降低计算复杂度，本文首先将下采样到1536×1024的分辨率。这些拍自喷泉模型的11个视角。在这个实验里,深度图由2.4.2节中介绍的算法产生。噪声首先通过物理滤波进行处理，物理滤波方法包含了几何约束及对极线约束。由计算机视觉方法产生的点云信息提供在图2.8(a)中。该模型的一些数量化特性提供在表2.7中。 k=δ=δ=δ=数量与矩阵融合后的点云数量类似。在矩阵融合的算法框架下平均融合算法，传统矩阵恢复(TMC),ℓ1-LPC将被分别去恢复融合矩阵。不幸的是,TMC并的参数及相应的融合精度提供在表2.7中。 (d)LPC融 的融合精度。从视觉效果对比可以看出，矩阵融合算法有着更为优越的表现。在图2.8c和图2.8(d)中,两个结果是在同一个非完整矩阵上获得的。但是，它们却通过不同的矩阵恢复算法所完成。PC的融合结果在表面上有着更少的噪声及野PC33%。这里的实验结果表明，即使是在同样的不完整融合矩阵上，PC恢复算法都可以大大提高平均融合算法的效果。Middlebury⃝1上评测实验结果，这也是国际上最为通行的立体重建效果评测公开数据库。为了构成闭合曲面，在得到融合结果的散点上利用“泊松重建”[65]的方式完成点云到面片的转换。 矩阵恢复融合将与其它标准的三维重建算法进行比较。评估结果在表2.8给出,其中在每个子图下面,NA代表了该类方法并未给出实验值。从实验结果表明，Frukawa[6]征点匹配的重建算法取得了最好的实验效果，但同时也是耗时最多的算法。在 ”基于深度的方法中，Bradley取得了最好的融合精度但是完整度却不高。为了突出视觉效果上的比较,真实数据和我们的重建结果都提供在图2.9中。在该图中，从左到右依次是：真值、我们的重建结果和Bradely的重建结果。视觉效果上，Bradley的方法在重建表面上有一系列的，我们的算法却给出了更完整的重建本文提出了一种对数和启发式恢复算法从污损数据中学习得到的低秩结构。我们引入M算法并通过重方法将非凸目标函数转化为一系列凸优化，而且证明了这样的方法可以收敛至一个稳定点。此模型被应用于低秩矩阵结构恢复和子空间聚类两个实际应用。对于普通的噪声矩阵恢复问题，LHR将可行域边界扩展至η+ξ=.。对于子空间聚类问题，LHR在运动分割问题中比其它方法得到了更好的求解结果。在包含许多异常值与不确定性的聚类问题中也得到了令人满意的结果。本文进一步地将LHR模型应用于一个实际的计算机视觉问题―三维重建。据我们所知，这是国际上首次提出基于矩阵恢复的三维重建算法。在这个应用中，LHR作为有效的数字滤波器通过低秩约束和稀疏惩罚从大量有噪且残缺的点云信息中精确恢复三维模型。与已有算法不同的是，该应用不强调深度图的获取，而是在获取深度之后利用数学的方法改进深度图的质量。因此该方法可以无缝地拼接到多种三维重建算法中去，进一步提升已有三维重建算法的重建精度。3章越丰富，数据量的增长也是与日俱增。经典流形学习理论，当数据量大到一线性度量与物理学中的场论以及信息机制有着千丝万缕的联系。场和信息扩这一问题，利用信息扩散的机制，本章将提出两种基于信息的流形学习本章首先提出了随机交互时间指导下的特征抽取算法。这部分内容于[24]。在数学本质上，这一算法是对数据的降维。在衡量流形上样本间相似度时，本文提出利用图上的随机交互时间作为依托去引导数据的降维学习。随机交互时间，是一种在场论下定义的概率距离，它用随机场的概念刻画了物理网络中电子的机制。在数学意义下，它是一种统计意义下的期望距样本间的结构信息。基于此，本文提出了基于随机交互时间（CommuteTimeGuided,CTG)的特征提取算法。这种场论观点下的流形测度，可以更好地处理样对此问题的探讨于[23]。视觉信息在获取过程中会因遮挡而造成缺失。如在人脸识别问题中，人脸会因镜，浓密的胡子，佩戴围巾等客观因素造成了信息在各像素间的过程。基于此，本文提出谱图上的算法去刻画本节将首先介绍基于随机交互时间的特征提取算法（CommuteTimeCTG，度间的冗余。在介绍CTG模型之前，本文先给出交互时间（CommuteTime，CT）文采用的是基于马尔科夫描述的计算方法。我们定义了一个有权无向图G，在图上，Wij的值表示任意两个节点i,j之间的相似度。一个随机者从节点i随机游pij

∑Wij,t∈ (3-W W明显地看出：一条边的连接权重越大，随机者越有可能通过这条路径。由于随机行为的概率性，这里不可避免出现一个问题：一个随机者，可以按照不同的路径在节点间。基于路径的不同，相应的时间花销也是不同的。幸运的是，交互时间是一个固定的统计期望。它代表一个随机者周游一对节点的平均时间。交互时间与整的拓扑结构相关，而并不仅仅取决于一条单一的路径[70]。本文主要遵循[71]中的结果去计算节点i和j之间的随机模型交互时间ctij： j ictij=volG×(l++l+−2l j i [ivolGi

ijWi

l+=

L+中，L i L=D− (3-Dii

jWi (3-布[72]。这些良好的特性自然使得CT成为一种理想的流形学习度量。虽然CT有如上这些良好的特性，但大多数现有的CT嵌入算法只考虑了训练数据的处理72]，这也限制了CT只能处理数据聚类的实际问题。但诸多计算机视觉课题要求泛化学习能力到训练样本之外的测试数据。针对这一，本节将提出一种可以处理测试样本的CT嵌入算法，称为交互时间引导（CTG）变换。ctijyiRm×1mM。在子空间数据yiyj之间的欧氏距离为dij=∥yi−yj∥。i mini

=min (3-ijcti i (3-5)ctijctijdij也应该足够小，以尽量减少整个目标结果。一个小ctij以及一个大的dij会导致目标函数值变大，这极大地影响了全局的最小化。相反地，如果ctij大，在被映射的空间中则相应地允间引导变换(CommuteTimeGuided，CTG)的最主要的原因。此外，为了泛化CTG的学习能力到测试样本，我们引入一个投影矩阵Ω∈RM×m来建立隐空间中的点与流形上点之间的线性关系。数学上，ΩT将节点Ni∈RMyi∈Rm，即yi=ΩTNi。由此，可得到CTG模型的优(CTGObj.)

∑ij∥ΩNi−ΩNj∥ ∑∥ΩNi−ΩNi =i 1tr[(ΩTNi−ΩTNj)(ΩTNi−ΩTNj)T=ii[]=tr[]

(ΩTNi−ΩTNj)(ΩTNi−ΩTNij

(3-ΩTNiNT ΩTNiNT=2tr

i

ctj[ iN[N1N2...