一种基于边收缩的3维表面模型数据压缩算法

随着数据采集尤其是3维激光扫描技术的发展,对地物目标建立的表面模型越来越精细,由于其不仅导致数据存储量急剧增大,也降低了图形实时交互显示的速度,因此必须对表面模型数据进行压缩处理。为了对原始扫描构模表面模型进行合理、有效的压缩处理,在Garland提出的表面模型压缩算法的基础上,提出了一种新的基于边收缩的表面模型数据压缩算法。该算法首先依据二次误差度量准则计算边收缩的代价,同时确定各边收缩的顺序,然后利用半空间测试方法判断边收缩的合法性,以实现表面模型的边界区域与内部区域的同步压缩。实践表明,该算法不仅在高压缩比的情况下仍能保留原始模型的几何特征,而且能有效地保证压缩模型的质量。

基于边收缩方法的网络化信息系统链路重要性评估

链路重要性对于确定链路维修顺序、链路防护级别以及网络拓扑优化具有重要意义。从链路正常工作的角度出发,提出基于图论的边收缩方法,认为网络化信息系统网络拓扑模型的某条边收缩后,得到的图对应的生成树数目越多,则该边对应的链路对于网络化信息系统的重要程度越高。运用该方法评价了某网络化信息系统(局部)各链路的重要性,评价结果与实际吻合,证明了该方法的可行性。

基于边收缩的渐进网格模型生成算法

为了实现3D模型的渐进式网格模型表示,改进基于边收缩方式模型简化的收缩代价计算方法。本算法首先从SMF数据文件中读取模型数据信息,然后在内存中快速建立起3D模型,重新设计Garland算法中QEM的权值计算方法。以顶点相邻三角平面法向量最大偏差的平方作为顶点的重要程度并将其加入到误差测度公式中,通过简化最终生成渐进式网格模型。实验结果表明,本算法简练,网格模型生成速度快,模型轮廓信息保持完整。

基于边收缩的快速网格简化算法

根据Garland的QEM算法提出了一种快速的网格模型简化算法。算法使用顶点权值来表示顶点的重要程度,顶点权值可以将收缩的边所影响的范围控制在较小的区域内;顶点的权值被存储在一个优先权队列中并且利用优先权队列来控制边收缩的顺序,顶点的优先权队列所存储的元素比较少并且易于维护。该算法实现容易、执行速度快。

κ连通图中的非边收缩

图的非边收缩指将图中两个不相邻的顶点粘合在一起．对 κ连通无三角形图， Ｋｒｉｅｓｅｌｌ证明了如果图 Ｇ 的阶大于 κ２＋ １，则除了一类特殊图外， Ｇ 中总包含两个不相邻顶点，使其收缩之后的图仍是κ连通的．本文考虑另一些图类，并得到类似的结果．

递归收缩算法中支点的处理策略研究

为了确保生成无向图割集的递归收缩算法的正确性和稳定性,对算法中种子顶点是支点的情形进行了分析,并采取了新的处理策略。分析了支点具有一个非可吸簇的情形,引进附加吸入的概念,修正了种子顶点的BFSO值取值规则,解决了现有算法可能遗漏割集的问题。针对支点没有非可吸簇的情形,给出了一个新的处理策略,解决了现有算法在某些特殊输入条件下效率不高的问题,在理论上分析了新处理策略的有效性,并做了相应的实验比较,理论分析和实验比较均表明:新的处理策略采用提高了递归收缩算法的稳定性。

边收缩池化的网格变分自编码器

目的3D形状分析是计算机视觉和图形学的一个重要研究课题。虽然现有方法使用基于图的卷积将基于图像的深度学习推广到3维网格,但缺乏有效的池化操作限制了其网络的学习能力。针对具有相同连通性,但几何形状不同的网格模型数据集,本文利用网格简化的边收缩操作建立网格层次结构,提出了一种新的网格池化操作。方法本文改进了传统的网格简化方法,以避免生成高度不规则的三角形,利用改进的网格简化方法定义了新的网格池化操作。网格简化的边收缩操作建立的网格层次结构之间存在对应关系,有利于网格池化的定义。新定义的池化操作有效地编码了层次结构中较粗糙和较稠密网格之间的对应关系。最后提出了一种带有边收缩池化和图卷积的变分自编码器(variational auto-encoder,VAE)结构,以探索3D形状的隐空间并用于3D形状的生成。结果由于引入了新定义的池化操作和图卷积操作,提出的网络结构比原始MeshVAE需要的参数更少,因此可以处理更稠密的网格模型。结论实验表明提出的方法具有更好的泛化能力,并且在各种应用中更可靠,包括形状生成、形状插值和形状嵌入。

通信网中链路重要性的评价方法

本文提出了一种通信网链路重要性的评价方法 ,该方法可以评价全网范围内的链路重要性 .最重要的链路是将其进行边收缩操作后 ,得到的图的生成树数目最多 .通过比较生成树的数目 ,我们可以判断通信网中任意两条链路的相对重要性 .基于生成树数目的边收缩方法反映了某条链路处于正常工作时 ,对整个通信网的贡献大小 .

基于曲线曲率的网格简化方法

网格简化是科学可视化和虚拟现实领域中的一个重要研究方面。细节是模型的重要组成部分,而顶点的法向量是描述模型细节的一个重要参数,在网格简化中,为了在保持模型的全局特征的同时也能较好地保持模型的细节,提出了一种采用曲率加权的二次误差作为简化代价的方法,该方法基于二次误差(QEM)简化方法,在代价函数中引入了顶点法向量的变化率,即顶点的离散曲线曲率,从而使得网格简化后模型的细节能够较好地保留。此外,为了在网格绘制上获得良好的视觉效果,采用了三角形平均法向量作为顶点法向量来进行处理和显示。实验结果表明,与单纯采用二次误差(QEM)作为代价函数的简化方法相比较,新方法能够在同等的简化率下更好地保持原有模型的固有特征,并具有良好的视觉效果。

多边形简化算法及比较

用多边形简化提高工程分析效率,利用图形学中三维模型简化的相关思想,从顶点删除和边收缩2个角度,提出3种多边形简化算法,并对其简化效果进行比较。实验结果表明,该算法在对多边形进行简化的同时能够有效保持多边形的形状,已应用于地质高程分析软件中。

渐进网格简化模型的改进算法

渐进网格模型可以用于层次细节的实现、三维网格的简化及重建等。改进并实现了一种渐进网格生成算法,针对渐进网格在简化和重建过程中各边权值计算中出现的误差,给出一种改进的权值公式,以便更精确地确定各边的优先级。同时针对简化过程中,各个块之间会出现裂缝,提出裂缝消除的方法。实验结果表明,该方法可以有效的简化模型,以满足用户的需求并提高效率。

基于顶点度的模型简化算法

针对基于二次误差度量的边收缩算法在计算大度顶点误差度量时计算量大,且收缩该类顶点关联边时易使关键点发生偏移而引起模型变动过大、简化不够准确的问题,提出了基于顶点度的模型简化算法。该算法不但提高了模型的简化质量,而且加快了模型的简化速度。

基于三角形折叠的多细节层次模型

提出了一种新的三角形折叠误差计算方法,针对网格简化程度的不同引入阈值控制折叠误差,生成满足不同需要三维模型的多个细节层次;提出通过建立不同细节层次模型间顶点的对应关系,在对应点之间进行线性插值,以此实现了绘制过程中不同细节层次模型间的平滑过渡。

Catalan数的一个递归关系

将非结合代数中n元X1 ,X2 ,… ,Xn 按给定次序的加括号乘法 (结合法 )转化为长为n- 1的路X1 X2 …Xn 的边收缩问题 ,用容斥原理 。

网络可靠性分析中自顶向下的二叉决策图构造研究

采用边界分区标识网络的思想,实现基于边界分区的自顶向下K端可靠度二叉决策图(BDD)构建算法。针对BDD构建过程中存在的节点冗余问题,提出无效边冗余消除和K点非连通冗余消除2种处理技术。在规则网络和实际工程中的实验结果表明,利用无效边冗余消除和K点非连通消除技术后的BDD改进算法,在不影响算法时间性能的情况下,可大幅缩减BDD尺度,提升K端网络可靠度分析算法性能,适用于大规模的网络可靠度分析。

基于三角形折叠的LOD算法研究与实现

对三角形折叠误差计算方法进行了改进,针对网格简化程度的不同引入阈值控制折叠误差,然后按要求的折叠误差确定折叠新顶点,从而生成满足不同需要三维模型的多个细节层次;建立了不同细节层次模型间顶点的对应关系,然后在对应点之间进行线性插值,实现了绘制过程中不同细节层次模型间的平滑过渡。

基于顶点度的多分辨率表示

针对边收缩算法在计算大曲率面距离公差时计算量大 ,且收缩大曲率面所含的线段时易使关键点发生偏移而引起模型变动过大、简化不够准确的问题 ,本文在边收缩算法基础上提出了加入顶点度控制的算法 ,以减少大曲率面距离公差的冗余计算 ,并提高模型简化质量。实验表明该算法能提高模型简化质量 ,并加快图形收缩的生成速度。

极图参数研究

研究了不含n-圈(n≤6)的极图的围长和1度顶点数2个参数。通过图的边收缩操作,得出不含n-圈(n≤6)的极图的围长是7,并进一步得出了极图中1度顶点数的上界。

基于曲率和面积的二次误差测度网格简化算法

在经典的二次误差测度(QEM)简化算法基础上,将离散曲率和面积引入到边收缩代价计算中,提出了一种基于离散曲率和面积的二次误差测度网格简化改进算法.该算法既考虑了离散曲面在各顶点附近的弯曲程度,又考虑了曲面的几何形状特征.为保留模型的原始边界特征,规定不对其边界进行简化.试验结果表明,改进算法在网格简化过程中保持了原有算法运行速度快的优点,且简化模型能合理地分配网格,并更好地保持了原始模型的重要特征.

探索Euler图的等价命题

从研究Euler图的等价命题入手,尝试挖掘Euler图的拓扑结构,力图从多个角度刻画Euler图的本征,得到4个新的Euler图等价命题,并利用图的"浓缩"和"稀释"运算给出刻画Euler图的技术,且此技术能够转化为可行的算法.