三角网格模型骨架提取算法

骨架图能够直观表达三维模型几何形状,很好地反映模型的拓扑特征,在工业机器人抓取、特征识别等领域有着广泛的应用。针对三角网格表达的工业零件给出一种骨架提取算法,该算法采用Reeb图对三角网格进行骨架的抽取运算。首先读取三角网格文件,并对复杂的三角网格进行简化处理,然后遍历所有的三角网格,采用Dijkstra算法抽取基本点集,根据定义的连续函数计算每个顶点的函数值,最后根据函数值得出模型的基本骨架。实验表明,该算法具有良好的计算效果和效率,提取出的骨架图较好地保存了三维模型拓扑结构和姿态,可作为后续研究三维模型搜索的特征描述符。     

一种MRG骨架树的三维模型检索方法

根据多分辨率Reeb图（MRG）原理,依据测地线函数分割模型,有效地提取反映模型拓扑结构的Reeb图骨架。进而,映射Reeb图为树结构,分析各骨架节点的拓扑属性,并提取其相应区域的离散曲率信息作为局部形状属性。最终,有效结合拓扑和几何形状特征,计算模型的相差度。该方法突出了模型的总体拓扑特征以及模型的表面细节,一系列的实验结果验证了其高效性、鲁棒性。     

融合形状特征的MRG骨架树三维检索方法

提出一种基于MRG骨架树的三维模型检索方法。根据多分辨率Reeb图(MRG)的原理,提取反映模型拓扑特征的Reeb图骨架并且映射成树形结构,分析了节点的拓扑属性。针对拓扑属性在形状特征上的表达能力不足,在节点相应区域提取离散曲率和面积比例描绘局部的形状特征。有效地结合了模型的拓扑特征和形状特征计算模型的相似度。该方法突出了模型的整体拓扑特征和形状特征,实验结果表明了该方法的高效性和鲁棒性。     

高斯曲率约束的MRG骨架提取优化算法

三维模型的骨架保持了模型的拓扑特性,并被广泛应用于模型相似性比较、计算机动画及压缩等领域.根据多分辨率Reeb图的原理,提出了一种基于离散高斯曲率约束的骨架提取优化算法.通过计算网格顶点的离散高斯曲牢判断曲面局部凸凹特性,以获取模型表面的双曲极值点作为约束点;并依据约束点及其邻域的μ函数值产生的分裂线进行区域细分,获得子连通区域、确定关节点、形成优化的骨架结构.实验结果表明,该算法有效地突出了模型的拓扑分支特征以及模型表面的细节,提高了骨架提取的精度和效率.     

关节特征约束的3维模型骨架提取算法

根据多分辨率Reeb图（MRG）的原理,提出一种基于关节特征约束的骨架优化算法。它克服了基于曲率约束提取骨架方法中逐点计算顶点的曲率约束轮廓的低效性,通过分析网格顶点的离散高斯曲率,获取模型表面上具有凹陷特性的双曲极值点作为约束点, 进行关节特征区域的有效提取。进而增加关节特性点,优化MRG骨架。实验结果表明,本方法有效地突出了模型的拓扑分支特征以及模型表面的细节,提高了骨架提取的精度和效率。     

视觉图像相似性在三维模型相似性比较中的应用

提出一种基于视觉的三维模型相似性比较算法.首先计算三维模型的带深度信息的正交平面投影图像,然后采用Zernike描述子和Reeb图比较这些正交投影图像的形状相似性,最后通过正交投影图像的形状相似性来获得三维模型的相似性.实验结果表明：该算法具有较好的三维模型检索准确性,并且对坐标系旋转变换、模型噪声、网格简化和细分具有较好的鲁棒性.     

改进的多分辨率Reeb图骨架抽取算法

针对实际应用中的模型可能包含多个连通分量的情形,改进了多分辨率Reeb图中的骨架创建算法,并对多种不连通的模型进行了实验。生成的骨架可为三维检索提供特征描述符。     

基于优化DRG的三维人体点云骨架提取方法

针对离散Reeb图（Discrete Reeb Graph,DRG）描述人体骨架时分支部位骨架线偏离中轴的问题,采用了能量函数最小化的方法对DRG曲线进行优化。将人体模型的DRG曲线作为初始骨架,定义其能量函数,在点云模型的距离场梯度的作用下,迭代地调整偏离中轴目标段的曲线位置使其逐渐逼近中轴,能量函数最小时得到优化的骨架。将该算法应用于同一模特四个不同姿势和四个不同模特同一姿势的人体点云模型,并与基于拉普拉斯算子的点云收缩的骨架提取方法进行了比较。结果表明,该算法能够很好地适应各种不同姿势和体型,模型分叉部位的特征得到更加完善的描述,得到的骨架曲线更接近模型的中轴。     

基于特征点检测的最佳视点选择方法

针对三维模型视点选择问题,提出了基于特征点检测的最佳视点选择方法。算法首先根据三维网格模型的顶点邻接区域信息计算顶点的局部高度,即顶点的显著度大小;然后基于顶点的局部高度值大小,结合非极大值抑制算法进行三维模型表面特征点检测;最后针对视点球体上的每个候选视点分析该视点下可见特征点的几何分布信息,计算视点质量,从而筛选出最佳视点。实验结果验证了基于特征点检测的三维模型视点选择方法的合理性和优越性,所选择的最佳视点能够提供三维模型较多的几何结构和视觉特征信息。     

面向三维点云模型的鲁棒零水印技术

对三维点云模型零水印技术开展研究,基于三维模型形状分析、结合数据分析理论,选择具有较高稳定性的三维模型全局几何特征作为水印构造的基础,通过计算三维模型顶点范数,以顶点范数为依据建立三维模型有序顶点集,分析顶点集中顶点数目的分布情况构造水印。实验结果表明,该方法执行速度较快,可以直接应用于三维点云数据,能够很好地抵抗平移、旋转、均匀缩放、顶点重排序、噪声、简化、量化、平滑和细分等常见攻击,对剪切攻击也有一定的鲁棒性,能够满足三维模型版权保护的要求。     

基于邻接矩阵的网络流量检测点设置算法

在研究网络流量的有效测量问题时,考虑网络节点的流守恒,把网络流量监测点问题抽象为无向图的最小弱顶点覆盖问题,这是一个NP难的问题.基于图论中邻接矩阵的概念,提出一个近似算法,通过重复删除邻接矩阵中所有行元素之和不超过1的节点对应的行和列,得到最小弱顶点覆盖集.在此基础上通过预先递归去除无向图中1度节点,满足任意节点度数都大于或等于2的最小弱顶点覆盖问题求解条件,并将递归节点作为该近似算法的入口点.仿真实验表明,与现有算法相比,新算法具有更好的性能,能够发现更小的弱顶点覆盖集.     

骨架驱动的三维模型变形方法

为发展三维网格模型的变形技术,研究了多种三维模型变形算法,通过对骨架驱动变形算法的深入研究,针对现行算法多是以单一骨架驱动变形的不足,提出了一种新的基于多骨架点驱动的交互式局部变形方法.有效结合模型的骨架图结构,确定各骨架点对应的局部区域.并将骨架点拟合为二次Bézier曲线,通过交互式拖动任意骨架点计算与之相连的多骨架点的动态变化,实现模型局部区域的自然形变.实验结果表明了该算法的有效性和直观性.     

基于压缩的大规模图的割点求解算法

割点求解是图应用中的一个重要操作.深度优先搜索树算法可以解决割点求解问题.但是该算法存在缺点,导致它不能在实际问题中得到很好的应用.这是因为当今数据的两大特点,一是数据规模庞大,对于很多图操作提出了挑战性的要求;二是数据多变,每天数据的大量更新使得传统算法必须依据更新重复计算,浪费了时间和空间.深度优先搜索树算法的时间复杂度为O(|V|+|E|),其中,|V|和|E|分别为图的顶点的数目和边的数目.它能够很好地适应第1个特点,但是对于第2个特点该算法则无能为力.提出一种基于压缩的割点求解算法来解决这个问题.该算法通过点的朴素相似来压缩图,时间复杂度为O(|E|).在得到的无损压缩图上进行割点求解,同时在压缩图上动态地维护点和边的更新,在不解压图的情况下完成图的更新,在更新后的图上进行割点求解,极大地降低了时间和空间消耗.该压缩算法得到的压缩图对其他图操作同样适用.     

Partial 3D Shape Retrieval by Reeb Pattern Unfolding

This paper presents a novel approach for fast and efficient partial shape retrieval on a collection of 3D shapes. Each shape is represented by a Reeb graph associated with geometrical signatures. Partial similarity between two shapes is evaluated by computing a variant of their maximum common sub-graph.
By investigating Reeb graph theory, we take advantage of its intrinsic properties at two levels. First, we show that the segmentation of a shape by a Reeb graph provides charts with disk or annulus topology only. This topology control enables the computation of concise and efficient sub-part geometrical signatures based on parameterisation techniques. Secondly, we introduce the notion of Reeb pattern on a Reeb graph along with its structural signature. We show this information discards Reeb graph structural distortion and still depicts the topology of the related sub-parts. The number of combinations to evaluate in the matching process is then dramatically reduced by only considering the combinations of topology equivalent Reeb patterns.
The proposed framework is invariant against rigid transformations and robust against non-rigid transformations and surface noise. It queries the collection in interactive time (from 4 to 30 seconds for the largest queries). It outperforms the competing methods of the SHREC 2007 contest in term of NDCG vector and provides, respectively, a gain of 14.1% and 40.9% on the approaches by Biasotti et al. [ BMSF06 ] and Cornea et al. [ CDS*05 ].
As an application, we present an intelligent modelling-by-example system which enables a novice user to rapidly create new 3D shapes by composing shapes of a collection having similar sub-parts.     

Reeb graph path dissimilarity for 3D object matching and retrieval

We introduce a skeletal graph for topological 3D shape representation using Morse theory. The proposed skeletonization algorithm encodes a 3D shape into a topological Reeb graph using a normalized mixture distance function. We also propose a novel graph matching algorithm by comparing the relative shortest paths between the skeleton endpoints. Experimental results demonstrate the feasibility of the proposed topological Reeb graph as a shape signature for 3D object matching and retrieval.