基于谱方法的网格数据的压缩毕业论文.pdf 32页

'本科毕业论文(科研训练、毕业设计)题目：基于谱方法的网格数据的压缩姓名：曾安学院：数学科学学院系：数学与应用数学专业：数学与应用数学年级：2011学号：20520112201410指导教师（校内）：曾吉文职称：教授指导教师（校外）：刘利刚职称：教授年月日 厦门大学本科毕业论文（设计）II 厦门大学本科毕业论文（设计）基于谱方法的网格数据的压缩摘要三维模型在建筑、医学、电影、游戏等很多领域有着广泛的应用，然而由于表示三维模型的三角网格的大数据量与图形引擎处理能力以及网络带宽限制之间的矛盾，因而三维网格数据压缩编码的技术就非常有必要。本文就谱方法压缩三角网格数据从实验到理论进行了深入探讨。首先介绍了网格数据压缩方法研究的重要意义和现阶段研究状况；然后对谱方法压缩三维网格数据的具体算法实现进行深入分析并用程序实现；之后讨论了一下关于谱方法压缩网格数据的改进优化之处；最后对三角网格数据谱压缩方法的最优性进行了一些理论上的分析。关键词：网格压缩谱方法Laplace坐标固定基主成分分析最优基III 厦门大学本科毕业论文（设计）MeshcompressionbasedonspectralmethodAbstract3Dmodelhasbeenappliedinmanyareassuchasarchitecture,video,gameandsoon.Butbecauseofthecontradictionbetweenbigdataofmeshesandthefinitebandwidthandfinitecomputingpower,themeshesmustbecompressed.Thisarticlestudiedthespectralcompressionofmeshdata.Firstwestudiedthemeshcompressionmethodsanditscurrenttendency.Thenwediscussedtheapproachestoimprovethespectralmethod.Finallywegivesometheoreticalproofabouttheoptimalityofspectralcompressionofmeshdata.KeyWords:MeshcompressionSpectralmethodLaplacecoordinateFixedbasesOptimalbasesPrincipalcomponentanalysisIV 厦门大学本科毕业论文（设计）目录第一章引言………………………………………………………………………………………1第二章基于谱方法的三角网格数据的压缩…………………………………………………32.1.从一个小例子谈起……………………………………………………………………32.1.1、拉普拉斯光顺…………………………………………………………………32.1.2、网格几何信息的谱……………………………………………………………42.1.3、网格的谱压缩与重建…………………………………………………………52.2.基于网格顶点绝对坐标的压缩………………………………………………………62.2.1、想法来源………………………………………………………………………62.2.2、算法介绍………………………………………………………………………62.2.3、实验结果………………………………………………………………………92.3.基于网格顶点Laplace坐标的压缩…………………………………………………102.3.1、算法介绍……………………………………………………………………102.3.2、实验结果……………………………………………………………………122.4.两种方式的比较、讨论分析…………………………………………………………12第三章对谱方法的优化………………………………………………………………………143.1.网格划分…………………………………………………………………143.2.使用固定的谱基向量……………………………………………………14第四章网格数据频谱压缩的最优性理论探讨………………………………………………174.1.一些术语定义与说明…………………………………………………………………174.2.1D情形………………………………………………………………………………184.2.1、构建模型………………………………………………………………………184.2.2、几何分布………………………………………………………………………184.2.3、最优基证明……………………………………………………………………194.3.2D情形………………………………………………………………………………214.3.1、构建模型………………………………………………………………………21V 厦门大学本科毕业论文（设计）4.3.2、几何分布………………………………………………………………………214.3.3、最优基证明……………………………………………………………………224.43D情形…………………………………………………………………………………23总结………………………………………………………………………………………………24致谢语……………………………………………………………………………………………25参考文献…………………………………………………………………………………………26VI 厦门大学本科毕业论文（设计）第一章引言三维图形数据在各方面得到了越来越广泛的应用，包括三维游戏，视频特效，建筑模拟，虚拟现实，考古遗址重现，科学可视化，医学图像，工业应用等领域。随着三维建模以及三维扫描技术的快速发展，人们对三维模型的局部细节以及精度都提出了更高的要求，三维模型的大小和细节方面的数据的复杂度急剧增长，对存储空间、计算能力、网络带宽等资源的要求越来越高。在这些资源中，网络带宽极大地限制了那些在网络上需要实时交互的图形学应用的实现。因而大量的三维模型数据需要通过压缩的方法来实现相应的实时的数据传输。在各种表示三维模型的数据中，三角网格是表示三维模型的一种行之有效的方法。三角网格一般表示空间的几何曲面，由很多多边形网格拼接而成。通常一个多边形网格包含三个部分的信息：拓扑信息、几何信息、属性信息，拓扑信息指多边形网格顶点之间的连接关系；几何信息是指顶点的位置坐标；属性信息是指网格顶点的法向量、颜色、纹理坐标、材质和其他属性信息。对于三角网格的压缩一般分为两个方面：拓扑信息的压缩和几何信息的压缩。对于拓扑信息的压缩，主要是对网格顶点之间的连接关系进行压缩从而占据更小的内存空间，例如通过哈弗曼编码就可以很好的压缩拓扑信息；对于几何信息的压缩，主要是对顶点的几何坐标进行压缩。在以前的研究中很多都是集中在拓扑编码压缩方面，后来一方面由于拓扑压缩的压缩比已经接近理论上的极限，另一方面由于几何信息的数据量比拓扑信息大得多（15bits/vertexvs.3bits/vertex）,因而最近十几年以来，越来越多的研究都集中在减少几何信息的编码上。对于数据的压缩，传统媒体使用了各种各样的压缩技术，例如图像压缩过程中就有一种采用谱方法的压缩技术实现了很好的压缩比，我们熟知的JEPG图像压缩格式就是基于离散余弦变换的。它是将一组数据表示成为一组正交基函数的线性组合，这些基函数就被称为频率。一个潜在的假设就是一个相对比较好的数据估计可以通过一小部分低频基函数的线性组合来得到。JEPG图像压缩方第1页 厦门大学本科毕业论文（设计）法得到的数据存储量是于是RGB数据量的大约二十分之一左右。由于我们已经假设低频系数对于网格数据的贡献比高频数据更大，接下来将阐述的基于谱方法的网格数据压缩编码可以被看做是一种渐进传输的编码模式：模型的重建可以利用一小部分谱系数得到，渐进传输的过程可以通过增减谱系数的个数来得到。同时，谱方法在那些对于精度要求不是太高的应用中非常有用，例如快速预览和电子商务中的产品可视化。第2页 厦门大学本科毕业论文（设计）第二章基于谱方法的三维网格数据的压缩2.1、网格几何信息的谱——从一个小例子谈起下图中是一个海马模型的平面轮廓图，它由平面上的2D点集构成的闭网格，现在我们需要通过一种操作，使得其左边粗糙的轮廓变得向右边那样光滑。图1.海马模型。上图来源于[5]。2.1.1、拉普拉斯光顺为了实现海马轮廓的平滑处理，可以采用拉普拉斯光顺算法：将每个点移到它邻接的两个顶点的终点处。设第i1,i,i1三个点分别表示为vi1xi1,yi1,vixi,yi,vi1xi1,yi1则经过两步光滑处理之后有~1111111vivvvvvvv,（2.1）i1iii1i1ii12222424如下图所示图2.拉普拉斯光顺，点的坐标变化。上图来源于[5]。其中定义一维拉普拉斯算子为第3页 厦门大学本科毕业论文（设计）1vvvv.（2.2）ii1i1i2定义2.1.1：网格顶点为一个坐标向量集V,其中V是n2的矩阵，n为网格顶点个数，x为顶点v的x轴分量的坐标。ii为了便于分析，我们只考虑x轴分量的向量X，对于y轴分量以同样的方式讨论。由式子（2.2），一维拉普拉斯算子，可以用矩阵的形式表示为11100221110022(X)LXX,(2.3)00111221100122由式子（2.1），可以得到经过两步变换后的所有点的新的坐标为11100xˆ2441111x1xˆ002424x2XˆSX.(2.4)111xˆn100xn1424xˆn111xn00442至此可以得到光滑算子S1SIL.(2.5)2为了分析光顺模型，需要弄清楚当光滑性步骤不断增大最终会出现什么结果，需要依赖拉普拉斯算子L，即考虑它的特征向量构成的基向量，这就引出了网格几何信息的谱分析。2.1.2、网格几何信息的谱定义2.1.2：设网格的拉普拉斯算子L,e1,e2,...,en为矩阵L的经过标准化之后得到的特征基向量，相对应的特征值为1,2,...,n，E为由e1,e2,...,en作为第4页 厦门大学本科毕业论文（设计）列向量构成的矩阵。对于任意网格顶点坐标分向量X，将其表示为E的列向量的线性组合~EEEEx1111111n1~n~E~E~EE~Xx21x...21x212nx2EX,(2.6)eii1ni1~En1En1En1Ennxn由于E的正交性，所以~TXEX,(2.7)对每一个i~TxieiX.(2.8)~~~~其中x1,x2,...,xn即为谱系数（网格几何信息的谱），xi由信号X投射在特征基向量ei上面得到。2.1.3、网格的谱压缩与重建定义2.1.3：设X为网格坐标向量x轴的分量，同时称它为x轴方向的一个信号。在公式（2.6）中我们知道，信号X可以通过特征基向量的线性组合来得到，也就是相当于将一个信号通过傅里叶变换分解成各种不同频率的信号（e1,e2,...,en）的线性组合，特征基向量相对应的特征值反映了相应信号的频~~~率的大小，相应的谱系数x1,x2,...,xn是对不同频率能量的大小的度量。如下图所示：图3.谱系数与特征值之间的关系。左边是由401点构成的海马的网格轮廓，信号X与特征值（经过重新排序，递增顺序）之间的对应关系，右图是将前面一部分特征值与信号X的关系放大后得到的。上图来源于[5]。由上图我们可以看出，信号X经过谱变换后，能量都集中在低频部分，高第5页 厦门大学本科毕业论文（设计）频部分基本可以忽略，基于这一点我们想到是否可以通过低频部分的信号来对初始信号X做一个渐进的线性估计？答案是肯定的。可以通过一部分特征基向量的线性组合来重建信号X。首先我们需要做一些假设：假设特征基向量e1,e2,...,en所对应的特征值是递增的，即12......n，则信号X的一个渐进估计为k~(k)Xxiei（2.9）i1这样我们就不需要传递所有的谱系数，只需要传递一部分就可以达到信号重建的目的，同时也实现了几何信息的很高的压缩比。2.2、基于网格顶点绝对坐标的谱压缩2.2.1、想法来源通过上一节的海马的例子，我们结合信号处理中傅里叶变换的的相关知识，对网格的谱压缩有了一个初步的认识，可是它只是基于平面上的一个简单网格轮廓而言，现在我们需要将其扩展到更一般的情形中来说明，在此我们还是通过一个小例子引出相关思路。在图像处理中，图像压缩是一个重要的话题，而JPEG图像压缩方法采用的就是将2D信号表示成图拉普拉斯矩阵的特征向量的线性组合，其中它对应的拉普拉斯矩阵如下方式得到：首先得到图像的像素点之间的关联矩阵1i,j相邻Aij（2.10）0其它然后可以得到它的拉普拉斯矩阵为1LIA（2.11）4由于2D网格的规则结构，在数字图像处理领域，可以知道矩阵L的特征基向量刚好就是JEPG图像压缩中的余弦基函数[1]。2.2.2、算法介绍第6页 厦门大学本科毕业论文（设计）通过上述例子，很自然的可以想到：古典的谱理论是否也能够非常自然的扩展到一般的拓扑图结构中呢？特别的，可以扩展到任意的三维网格结构（拓扑图的一种特例）中？为了回答这个问题，首先做一些定义准备。定义2.2.1：设M为一个空间三角网格，可表示为MK,G,其中K表示的是空间网格顶点之间的连接关系，G表示的是网格顶点的坐标信息。定义2.2.2：类似于公式（2.10），在3D网格中，由顶点之间的连接关系K我们同样可以得到该网格的一个关联矩阵A1顶点i,j为相邻点Aij0其它定义对角矩阵D：D1d为第i个顶点的度ijdii定义相应的Laplace矩阵L为：1ijLIDALij1dii,j为相邻点。0其它下面我们求得矩阵L的特征值和特征向量，对L进行特征值分解-1LUU,（2.12）在此我们需要假定U中列向量所对应的特征值是以递增顺序排列的，即U中信号是由低频到高频递增的，令Uu1,u2,...,un。例如，对下图中的拓扑网格图4.一个网个例子。上图来源于[1]。第7页 厦门大学本科毕业论文（设计）011111.000.250.250.250.25101110.251.000.250.250.25110110.250.251.000.250.25111000.330.330.331.000111000.330.330.3301.00关联矩阵A相对应的Laplace矩阵L.04470.0000.8170.0000.366.04470.0000.4080.0000.366.04470.0000.4080.7070.366011.251.251.5.04470.7070.0000.7070.548.04470.7070.0000.0000.548矩阵L对应的特征向量L特征向量所对应的特征值对于网格的几何坐标X,Y,Z我们分开来考虑他们，只需要对分量X讨论即可，其他两个分量类似。对于分量X想要重建它可以现将其表示成为特征基向量组U的线性组合，将X通过类似于傅里叶变换的形式得到谱系数，即将信号从而频域变到时域来分析，从初始几何定义域便到了谱定义域~TXx,x,...,xXUX~~~~12nXx1,x2,...,xn几何定义域变换谱定义域由之前所分析的可以知道，信号X的能量一般都集中在低频部分，因而高频部分可以忽略，在几何信息的谱压缩过程中，首先通过选定前k个基向量对X进行编码，然后只需要传递相应的k个谱系数到接收端，接收端可以通过谱系数进行解码，重建原来的信号X,其中原来信号X的重建质量与传递的谱系数个数息息相关，谱系数传递的越多，那么重建的网格与原来的网格越接近，越来越逼真，基于这一点，网格几何信息的谱压缩也是一种渐进传输的模式，这一特点有利于在网络上进行实时传输。以下流程图是整个网格几何信息谱压缩的编码和解码过程：第8页 厦门大学本科毕业论文（设计）拓扑信息K坐标信息G蕴含提取x分量初始信号X关联矩阵AXx,x,...,x12n对角矩阵D导~T编出xieiX码~TXUXLaplace矩阵：LIDA~谱系数X特征值分解~~~~Xx1,x2,...,xnTLUU传递一部分谱Ue,e,...,e系数用于解解12n码，实现很高码的压缩比重建误差：（L2范数意义下）重建后的信号n~n~2(k)k~XXeixixi(k)xXeiiik1ik1i12.2.3、实验结果通过上述流程图，我们可以对谱方法压缩网格的几何信息有一个大体的轮廓上的理解，接下来我们将通过给出实验结果来验证我们的理论：第9页 厦门大学本科毕业论文（设计）原始模型k=10k=30k=50k=100图5.选取的谱系数的个数相对应的重建结果。K:取定的前K个谱系数，重建图像是他们的线性组合。为了便于对比两种方法效果，相应的误差图将在2.3中给出。2.3、基于网个顶点Laplace坐标的压缩三维网格呈现的本质上就是很多小的多边形块面构成的曲面，在压缩网格时我们一般希望尽可能的不失真，也就是希望尽可能的保持原始曲面网格的局部细节。在计算机图形学中我们知道，顶点的微分坐标（即Laplace坐标）它能够很好地表示曲面的局部细节，所以我们希望做进一步的工作，考虑的是对网格顶点的Laplace坐标使用谱方法压缩，看一下效果是否会更好呢？2.3.1、算法介绍借用前面部分的定义，我们以同样的方法可以得到关联矩阵A，对角矩阵D，以及相应的拉普拉斯矩阵LIDA，对Laplace矩阵L进行特征值分解（即谱分解）：LUU-1,（2.13）其中为特征值构成的对角阵，U为相对应的特征向量。定义2.3.1：定义网格顶点的拉普拉斯坐标为：1n每个顶点的拉普拉斯坐标：1ivivj.（2.14）dijN(i)则有第10页 厦门大学本科毕业论文（设计）T1,2,...,nLV对Laplace坐标进行谱压缩编码便得到：TcU(k)U(k),（2.15）其中U(k)为前矩阵L对应的前k个特征矢量、c为被压缩后的新的Laplace坐标。"接下来我们需要进行网格重建，目标就是求得顶点的新的绝对坐标：V,具体求解方法如下：由于矩阵L所有列都加到最后一列后，最右一列全为0，可知L是奇异阵，所以无法直接对它求逆来得到顶点的压缩后的绝对坐标，需要另想其它办法：同时利用线性代数的知识我们可以证明：rank(L)n1,（2.16）所以可以通过固定一个点来反解出所有顶点的新的坐标，不妨固定最后一个顶点。当最后一个顶点被固定之后，拉普拉斯矩阵就会发生变化，设Lnew为原来拉普拉斯矩阵L去掉最后一行后所得到的新的矩阵，则Lnew为n(n1)矩阵；设V为新的将求出的前n-1个顶点的坐标，则有newcLnewVnew,（2.17）该方程组是一个超定方程组，通过最小二乘解的方式求解，左右两边同时乘以TLnew便得到方程组TTLnewcLnewLnewVnew，求解方程组：TTAXb,其中A,b,（2.18）LnewLnewLnewc就得到了前n-1个顶点的坐标，然后对最后一个顶点的坐标，取它为它邻接点的几何平均第11页 厦门大学本科毕业论文（设计）1XnXj.（2.19）dnjN(n)"至此，我们已经求得了所有顶点的新的坐标V，最后进行坐标迭代更新即可程序实现。2.3.2、实验结果原始模型k=10k=30k=50k=100图6.选取的谱系数的个数相对应的重建结果。K:取定的前K个谱系数，重建图像是他们的线性组合。我们可以发现：随着所传递的谱系数越多，重建的模型越接近原始模型。2.4、两种方式的比较、讨论分析通过比较两种方式的压缩结果，可以发现，粗略看起来效果是差不多的，但是为了更直观的比较两种方法之间的差异，我们通过一定的方式给出他们的误差图，试验中每个顶点误差度量的方式是~vivivi,（2.20）然后将这种误差通过一定的算法（程序中的PsudoColorRGB算法）将其转换成顶点的颜色，然后作出它的误差图，两种方式对比如下：基于绝对坐标压缩的误差图：ColorbarK=10K=30K=50K=100图7.原图与重建的网格之间的误差图。其中左侧的颜色条显示的是误差程度，纯蓝色代表与原始图的误差为零，颜色越偏红说明误差越大。第12页 厦门大学本科毕业论文（设计）基于Laplace坐标压缩的误差图：ColorbarK=10K=30K=50K=100图8.原图与重建的网格之间的误差图。其中左侧的颜色条显示的是误差程度，纯蓝色代表与原始图的误差为零，颜色越偏红说明误差越大。通过比较两种方式的误差图结果，可以发现随着传递的谱系数数量的增加，相对于原图误差越来越小，另一方面，传递同样个数的谱系数，基于绝对坐标的压缩重建效果比基于Laplace坐标压缩的效果要好很多。这与我们的期望有一定的差距，可以发现经验有时候也不一定是准确的。第13页 厦门大学本科毕业论文（设计）第三章对谱方法的优化在谱方法的实现过程中，有一部关键的地方就是要计算拉普拉斯矩阵的特征向量，一般的，对于一个nn的矩阵，计算它的特征向量的时间复杂度达到了O(n3)，尽管由于网格对应的拉普拉斯矩阵是稀疏矩阵，计算时间复杂度可以缩减到On，但随着网格数据量不断增大，这样计算的效率会很低，所以我们必须想办法优化谱方法，对它对一些改进从而更实用，以下将介绍两种改进的途径。3.1、网格划分一般的，当网格数据量非常大时，很多压缩方式都会采取的一个办法就是将网格进行划分，然后对每一个分片的网格单独对待，对其进行网格压缩编码，这样当网格数据量很大时就会极大地提高压缩效率。在应用中，网格划分的方式各种各样，可以根据不同的需求采取不同的划分方式。3.2、使用固定的谱基向量在上一步，我们已经知道要将网格进行划分成不同的片，但是这样做的效率依然很低，因为每一个分片网格自身的网格顶尖之间的连接关系都是不一样的，所有对每一个网格都要对它相应的拉普拉斯矩阵进行特征值分解，从而求的特征基向量，这样会降低效率，那么是否可以对不同的网格利用同样的基函数呢？首先来建立对应关系：对于一个很大的网格M，先将其分成不同的网格片的组合，即M{Mi}。在划分过程中，一般都会使得最后划分的网格片之间的顶点的数目相差不多。对每一个单独的分片网格，我们希望将其与一个规则的网格（6-正则网格）之间建立一个一一对应。第14页 厦门大学本科毕业论文（设计）定义3.2.1：定义M（n个顶点）为一个备选网格片，相应的连接图为G(M)，相应的6-正则的三角主网格片为H，并且两者的内点个数和边界点个数相等，即IMIH，BMBH，IMBMn。定义3.2.2、（图的Tutte嵌入法）将图的边界点固定在一个凸边界上，其他内部点的坐标是它的1-领域点的坐标的几何平均。为了建立备选网格片与主网格片之间的一个一一对应，首先将M和H都嵌22入到单位圆盘上面，eH:V(H)R，eM:V(M)R，其中V(M)是网格M的顶点集，接下来接下来找一个映射m:V(M)V(H)，满足所有映射点的欧氏距离之和最短margmineM(v)eH(m(v)).（3.1）vV(M)接下来使用中位切算法来划分e(V(M))和(V(H))，见[3]。实验结果如MeM下图9.此图来源于[2]。其中（a）为初始备选网格片映射到单位圆盘后的结果，（b）为6-正则主网格片映射到单位圆盘后的结果，（c）为备选网格片和主网格片两者在单位圆盘内映射的点混合后利用中位切算法进行匹配后的结果，（d）为备选网格片与主网格片匹配之后利用6-正则单位圆盘的连接关系形成的网格片，也就是将网格片M利用H的连接关系嵌入到H中。当M嵌入到H中之后，由H的连接关系构成的Laplace矩阵以及M顶点的几何坐标利用谱方法进行网格压缩。一般情形各个子网格片的顶点个数保持相等或相差不多，对于相等的情形就采用以上的方式即可，对于顶点个数不等的情形，如IMIH,BMBH。我们就必须增加边界点和内部点的个数来描述网格片的几何信息和连接关系，由于要保持内部顶点的度为6，所以选取内部顶点中都比较小的那一些点构成的三第15页 厦门大学本科毕业论文（设计）角形，在其中添加一个点，添加的顶点几何坐标为相应三角形三个顶点坐标的几何平均，一般不选取边界三角形。对于边界点也同样采取相同的添加，直至最后满足与固定的单位圆盘网格（主网格片H）内部定点个数和边界定点个数均相等即可。在添加完顶点之后，就按照之前相类似的方式将备选网格片嵌入到主网格片之中。如下图所示：图10.此图来源于[2]。其中（a）为具有任意连接关系的备选网格片M（内部顶点个数和边界点个数均小于主网格片），（b）为主网格片H，（c）为在M中顶点的都比较小的三角形之中添加了顶点（边界点也同样操作）之后，所得到的与主网格片内部顶点和边界顶点个数相等的结果，（d）为利用中位切算法进行匹配，再利用主网格片H的连接关系之后所形成的网格片。当我们将备选网格片M嵌入到主网格片H中之后，就得到了（d）中所示的网格片，再利用谱方法进行压缩编码，在之后的解码过程中将添加的顶点去掉就可以得到重建后的结果。按照这样的操作进行下去之后，我们就可以高效地利用谱方法进行压缩编码。可是这样同时会产生一些形变，需要做的是在选取固定基和形变之间保持两者之间的一个平衡。关于方法的进一步改进可以参见[9]。第16页 厦门大学本科毕业论文（设计）第四章网格数据频谱压缩的最优性理论探讨三角网格的谱压缩在实际应用中已经实现了很好的结果，但是对于这种方法的最优性很少有理论上的说明。接下来我们将通过构建模型，说明对某些种类的网格在它们的分布满足一定的概率分布的条件下，这些网格在均方误差意义下，基于谱方法的压缩方式是最优的。证明中主要是对一维和二维进行说明，由于三维情形在数学计算和表达上很复杂，在此不做证明。4.1、一些术语定义及说明n定义4.1.1：（向量分解）对于一个向量Xn1在R中一组正交基UU,U,...,U下的分解nn12nnX，（4.1）ciUii1n其中C{}为分解系数，由于U的正交性，那么Parseval等式便满足cii1CX.（4.2）一个分解被称为是有效的如果它的一小部分分解系数包含很大比例的能量（即相应的范数值），在向量重建过程中，X的重建可以通过使用前k个系数得到：kTX(U,k)ciUiX.（4.3）i1如果这个分解是有效的话，那么重建的向量与原来的向量之间的欧氏距离就非常小，在网格压缩中这种特性非常有用。一般的，对于某一个确定的向量X，它的最优分解基总是X,0,0,......,0，因为这样的话它的能量就集中在第一个系数上面。那么一个有意义的问题就产生了，对于一组向量，它们的分解的最优基是什么呢？为了回答这个问题，首先需要知道如何衡量最优性。第17页 厦门大学本科毕业论文（设计）对于一个网格，连接关系为E，几何信息可以利用适当的概率分布D来表示。n定义4.1.2：（最优基）给定R上的一个概率分布D，在这种概率分布下，我们称一组基U是最优的，如果对于任意其它的一组基W，对于1kn22Exp((XX))Exp((XX)),（4.4）(U,k)(W,k)其中Exp(X)表示在概率分布D下的期望，那么就称这组基U在均方误差（MSE）意义下是最优的。定义4.1.3：（主成分分析）假定在概率分布D意义下取定一个随机向量nXR,向量均值为0，协方差矩阵为C.i|i1,...,n为矩阵C的特征向量组，相应的特征值为i|i1,...,n,且满足12...n那么矩阵就称为随机向量X的主成分分析（PCA）。在数理统计中我们知道，主成分分析（列向量组）在均方误差（定义4.1.2）意义下是最优的。接下来我们将利用主成分分析这一工具来证明我们的主命题：网格的Laplace矩阵在乘以一个系数的意义下与网格概率分布所对应的协方差矩阵是相等的。4.2、1D情形：一维情形网格就是在直线上有序排列相连的一个点集，除了两个边界点，其他点都有两个邻域点，例如下图所示，n5情形：图11.5个顶点（内部点）的一维链式网格。此图来源于[3]。4.2.1、构建模型对于一个向量XX1,X2,...,Xn被称作有效的几何定点如果它满足：b0X1X2...Xnb1，其中b0,b1为固定的边界点，即以它们为定点的网格不相互折叠。4.2.2、几何分布第18页 厦门大学本科毕业论文（设计）设U1,U2,...,Un为一列随机变量，Ui~U(b0,b1),i1,2,...,n，U(1),U(2),...,U(n)被称为均匀次序统计量，如果满足b0U(1)...U(n)b1，均匀次序统计量。假设有效的网格几何坐标在(,)上的分布与上述均匀次序统计量一样，b0b1因为每一个有效网格，也就是相应的次序统计量，都可以通过初始变量不超过n!次置换得到。4.2.3、最优基证明定理1：对一维网格分解的最优基就是网格连接关系所对应的实对称Laplace矩阵的特征向量组i|i1...n，相对应的特征值满足u1...un。在4.1中我们知道，一维网格分解的最优基就是主成分分析，也就是网格几何分布的协方差矩阵所对应的特征向量组。为了证明定理1，我们首先需要做的事情就是求得网格几何分布对对应的协方差矩阵C。令XX1,...,Xn为一个随机有效的网格几何分布，两个边界点固定为b0,b1，C是它的协方差矩阵，由协方差的定义CijExp(XiXj)Exp(Xi)Exp(Xj).（4.5）为了计算出Cij，先要做一些准备。定义4.2.1：X0b0,Xn1b1,YiXiXi1,i1,...,n1。其中Yi被称为均匀间距，在[Pyke1965]中可以知道Yi之间是可以相互交换的随机变量，也就是说，它们是同分布的，并且相应的方差和协方差满足：Var(Yi)Var(Y1)v(n)i1,2,...,n1,（4.6）Cov(Y,Y)Cov(Y,Y)c(n)i,j1,...,n1,ij,（4.7）ij12其中v(n),c(n)是决定于顶点个数n和边界点b0,b1。引理4.2.1：如果X是一个有效的一维顶点坐标列，C是它的协方差矩阵，并且ji，则有Cjv(n)(ijj)c(n)。ij第19页 厦门大学本科毕业论文（设计）引理4.2.2：如果c(n),v(n)是定义4.2.1中所定义的均匀间距随机变量Yi（其1中i1,...,n1）的方差和协方差，则有c(n)v(n)n上述引理的证明可以参见[3]，在此不详细阐述。有了引理4.2.1和4.2.2我们便得到v(n)Cijj(ni1)1jinn从而便得到了有效几何网格的协方差阵为v(n)j(ni1)1jinCijn,（4.8）C1ijnji由观察计算发现，求矩阵乘积LC是一个不错的选择。由于一维有效网格顶点的度是2，每个顶点有两个邻接点，相应的Laplace矩阵为2100121L001210012nn其中n是内部顶点的个数。由计算可以得到k(n)ijLCij，（4.9）0ij其中k(n)决定于顶点个数n，且v(n)(n1)k(n).（4.10）n所以我们最终就得到了LCk(n)I因而就有1Lk(n)C.（4.11）由主成分分析的最优性可知，协方差矩阵C的特征向量组|i1,...,ni1（相对应的特征值12...n）就是最优基，由于C的特征向量与C第20页 厦门大学本科毕业论文（设计）1相同，而特征值却为u。所以我们就发现一维网格分解的最优基就是ii相对应的网格的Laplace矩阵的特征向量组，相应的特征值满足u1u2...un，至此，一维情形结果证明完毕。4.3、2D情形4.3.1、模型构建在二维情形，相应的几何网格M(G,R)，G(V,E)，R(X,Y)，网格M被称为是有效的如果相应的图的边都不相交。假设M有一个固定的边界，相应的边界点为(Xb,Xb,...,Xb)(xb,xb,...,xb)12k12k(Y,Y,...,Y)(y,y,...,y)b1b2bkb1b2bk所有的边界点形成一个凸边界，以下分布均是建立在此模型下。4.3.2、几何分布为了证明在二维情形由和一维情形同样的结果，我们同样需要对二维有效的网格提出一个自然概率分布，但是在二维情形这并不简单。目前，我们的证明中需要对有效几何网格顶点的坐标特性做出几点假设：(1)、Xi|Xjixj是满足正态分布的，即当其他点都给定时剩下的一个点的条件分布满足正态分布；1(2)、ExpXi|XjixjjN(i)xj，即（1）中的条件分布的期望是相应顶di点领域坐标的平均；(3)、Cov(Xi,Xj|Xkxk,ki,j,(i,j)E)0，即在其他店给定的前提下，每两个点所对应的随机变量的协方差为0[注：关于上述四个引理的证明请参见文献[3]]。从现在起，我们只对随机向量X做考虑，对于Y的结果类似可得。第21页 厦门大学本科毕业论文（设计）4.3.3、最优基证明定理4.3.1：2D网格M，其图结构为G(V,E)，相对应的实对称Laplace矩阵为L，如果它的几何分布满足上述4.3.2种的三个假设条件，那么对这个网格进行分解的最优基是L的特征向量组|i1...n，相应的特征值...。iu1un为了证明上述定理，首先我们先来介绍几个引理：引理4.3.1：XX1,X2,...,Xn为一个随机向量，如果（1）Xi|Xjixj对每个i是正态分布的（2）Exp(Xi|Xjxj)对于每个i关于xj是线性的并且非常数则X的分布是一个多元正态分布。引理4.3.2：C是有效网格M(G,R)的几何坐标R(X,Y)的分量X的协方1差矩阵。令KC，那么对于每个(i,j)，ij，(i,j)E，有Ki,j0。1引理4.3.3：X是一个多元正太分布的随机变量：X~N(,)。令K,则2（1）、Cov(,|)()KijXiXjXki,jxkKiiKjjKijKjj（2）、Exp(Xi|Xjixj)Exp(Xi)jiij(xjExp(Xj)),ij。Kii引理4.3.4：C是有效网格M(G,R)的几何坐标R(X,Y)的分量X的协方1差矩阵。令KC，则存在常数满足：（1）、对于每对(i,j)E,Kii（2）、对于每个iV,Kiidi（其中G(V,E)）[注：关于上述四个引理的证明请参见文献[3]]。有以上四个引理的铺垫，可以得到如下结论：对于有效网格MG,R，G(V,E)，R(X,Y)。C是X分量随机向量（在1相应的概率分布的意义下）的协方差矩阵，令KC，那么有第22页 厦门大学本科毕业论文（设计）(i,j)EKijdiij.（4.12）0其它回到实对称Laplace矩阵的定义，就可以得到1CKL，是依赖于n的常数.（4.13）至此，我们就完成了定理4.3.1的证明。4.4、3D情形对于3D情形，我们同样需要构建不重叠的网格模型，并且还需要给出满足一定假设的自然分布，首先想到的是能否直接使用2D情形的模型，当沿着这个思路进行下去之后，发现效果并不好，并且关于3D模型的几何分布的构造和相应定理的证明在数学上也很复杂，在此不做过多说明，具体可以参看[3].第23页 厦门大学本科毕业论文（设计）总结文章首先通过一个小例子引入谱方法，然后详细介绍了基于谱方法的网格数据的压缩的具体原理，之后又分析讨论了一下该方法的一些可以进一步改进的地方，最后通过理论分析证明在均方误差意义下，基于谱方法的网格压缩是最优的，从实验到理论全面的分析了基于谱方法的网格数据压缩，从而对其认识有一个明确而清晰的轮廓。从编写程序过程中的各种小错误的痛苦到后来程序调试成功的喜悦；从对英文文献的懵懵懂懂到真正深入其中，理解其要义；从对网格压缩相关知识的一无所知到最终通过各种求助（老师，同学，谷歌，百度...）而弄清原理：整个过程中，在不断地发现问题和解决问题，一步一步的前进，感觉收获良多。第24页 厦门大学本科毕业论文（设计）致谢语时光荏苒，岁月如梭，转眼间，四年的大学生活就要结束了，毕业在即，回想大学四年的生活，心中充满了浓浓的不舍与留恋。在这四年中，看着学校和我们一起成长，一起成熟，学校越来越美，而我却要离开校园了。当论文的最后一个字敲完，随即而来的不是应有的成就感，而是难以言喻的失落。论文的完稿，代表我美好的大学时光将要离我而去。感谢我的父母，不计回报的养育我，感谢我的母校，给我提供了良好的学习环境，感谢我的老师，给予我丰富的知识，感谢我的同学，陪伴我度过最美好的四年。刘利刚老师是我毕业论文的指导老师，他治学严谨，学识渊博，耐心负责。在本毕业论文的撰写过程中，他教会我全新的思考方式，教会我通用的研究方法，教会我树立明确的学术目标。正是由于刘利刚老师的帮助和宝贵意见，才让本文得以成型，才让我撰写论文更加顺利。在此特向刘利刚老师致以衷心的谢意！感谢您在百忙之中审阅全文，感谢您的悉心指导！最后我要感谢曾吉文老师的关心和建议，衷心的感谢您的悉心指导，使我得以妥善的完成大学之中的最后一项考核，谢谢您！第25页 厦门大学本科毕业论文（设计）参考文献[1]Z.KarniandC.Gotsman.Spectralcompressionofmeshgeometry[J].InProcedingsofSIGGRAPH2000,pp.279-286,ACM,2000.[2]Z.KarniandC.Gotsman.3DMeshcompressionusingfixedspectralbases[J].ProceedingsofGraphicsInterface,Ottawa,June2001.[3]M.Ben-ChenandC.Gotsman.Ontheoptimalityofspectralcompressionofmeshdata[J].ACMTransactionsonGraphics,24(1):60-80,2005.111233[4]O.Sorkine,D.Cohen-Or,Y.Lipman,M.Alexa,C.RösslandH.-P.Seidel.LaplacianSurfaceEditing[J].EurographicsSymposiumonGeometryProcessing2004.[5]B.LevyandH.Zhang.SpectralMeshProcessing[J].SIGGRAPH2010course.[6]蔡苏,赵沁平.三维网格压缩方法综述[J].计算机科学,第33卷第5期,2006年.[7]王金龙.三维网格压缩算法研究[D].西安电子科技大学,2007.[8]金永乐.三维网格压缩算法研究[D].中南大学,2010.[9]徐涛,张艳宁.基于固定正交基频谱分析的三维网格模型盲水印算法[J].光电工程,第34卷第11期,2007年.第26页'