一种基于骨架引导的三维模型内蕴对称性检测方法

本发明涉及一种基于骨架引导的三维模型内蕴对称性检测方法，属于计算机图形学和计算机视觉等领域。其步骤为：(1)生成模型的线骨架，并基于骨架对模型进行凸剖分处理；(2)基于相似的骨架肢节及其子分段检测它们相关凸剖分部分之间的外蕴对称性；(3)寻找相似的骨架结构，以此基于外蕴对称凸体的组合来检测模型中的内蕴对称体。本发明很好地降低了内蕴对称性检测的计算复杂度，并能检测到小型对称体、嵌入大对称体中的子对称体等已有方法难以找到的对称体，具有简便、高效的优点。

技术领域

本发明属于计算机图形学和计算机视觉等领域，具体涉及一种基于骨架引导的三维模型内蕴对称性检测方法。

背景技术

对称检测是找到那些将三维模型的一个部分映射到另一个部分而不改变形状的变换。关于三维模型进行对称检测的方法有很多，要全面了解这些方法，请参考Mitra等人的研究[1]。在这里，只做简短的说明，特别是主要针对内蕴对称性检测进行说明。

变换投票法是一种常用的对称检测方法。除了直接在变换空间中进行搜索的方法外，大多数方法都是先在模型表面密集采样，然后对采样点之间的对应关系进行考察，通过投票来检测可能的主导变换，这些主导变换能够反映出模型对称性。由于变换空间的复杂性，采样点之间的对应关系的计算通常是非常耗时的。此外，由于投票策略的原因，这些方法仅限于检测大尺度的对称体，对于小尺度或复杂的对称体，这些方法难以检测[2]。

特征图匹配方法[3,4]本质上是一种利用特征匹配来剔除非匹配几何体的方案，它们通过迭代最近邻点法(ICP)[10]进行对齐以得到最终的检测结果。正如[2]中所讨论的，这些方法是针对刚性对齐处理的，主要用于外蕴对称检测。此外，这类方法依赖于从模型表面提取的点/线特征，而提取的点/线特征很难恰当表示体积特征，因此，这些方法不便检测体积性特征明显的对称体。通常对齐是以穷举方式的暴力求解进行的，计算代价很大。利用特征图进行对称性检测，可优化检测计算，但特征只能近似地表示模型，可能会遗漏一些对称体，所得到的对称体质量较差。

谱聚类方法尝试使用统计方法聚类来寻找对称性。他们用一个矩阵来寻找集群的对称点[6]，如几何斑块或特性[2]。由于内蕴对称性是一种非刚性的变换，不能用矩阵表示，所以一些方法通过函数映射方法来查找对应关系。这些方法可以很好地避免噪声的干扰，提高对称性检测效果，但它们实际上是基于采样点、斑块、特征以及投票策略。因此，它们在检测效率、检测效果、检测精度等方面与其他类别的方法有着相似的缺点。例如，[6]中的方法倾向于检测大尺度和固定大小的对称体，不便识别尺度较小的对称性。而[2]中的方法难以检测大尺度对称体，因为它为了计算效率而不考虑距离太远的特征之间的关联性。虽然该方法[7]将时间复杂度降低到O(knlog(n))(其中k为使用的特征函数的数目，n为模型的顶点个数)，但计算代价仍然很高。这些方法可以看作是变换投票(不需要显式的变换处理)和特征图匹配方法的集成。因此，正如在介绍变换投票方法和特征图匹配方法所指出的那样，它们也不能保证能够生成高质量的对称体。

在对称性检测的许多实践应用中，计算的复杂度是影响应用成效的重要因素，甚至是决定性因素。因此，提出一种快速高质量的对称性检测方法，具有非常重要的实际应用价值。

[1]MITRA N.J.,PAULY M.,WAND M.,CEYLAN D.:Symmetry in 3d geometry:Extraction and applications.Computer Graphics Forum 32,6(2013),1–23.

[2]LI C.,WAND M.,WU X.,SEIDEL H.-P.:Approximate 3d partial symmetrydetection using co-occurrence analysis.In Proc.Of International Conference on3D Vision(3Dv’15)(2015),pp.425–433.

[3]M.Couprie and G.Bertrand.Asymmetric parallel 3d thinning schemeand algorithms based on isthmuses.Pattern Recognition Letters,76:22–31,2016

[4]BERNER A.,BOKELOH M.,WAND M.,SCHILLING A.,SEIDEL H.-P.:A graph-based approach to symmetry detection.In Proc.of the Fifth Eurographics/IEEEVGTC Conference on Point-Based Graphics(SPBG’08)(2008),pp.1–8.

[5]BOKELOH M.,BERNER A.,WAND M.,SEIDEL H.-P.,SCHILLING A.:Symmetrydetection using feature lines.Computer Graphics Forum 28,2(2009),697–706.

[6]LIPMAN Y.,CHEN X.,DAUBECHIES I.,FUNKHOUSER T.:Symmetry factoredembedding and distance.ACM Transactions on Graphics 29,4(2010),103:1–103:12.

[7]NAGAR R.,RAMAN S.:Fast and accurate intrinsic symmetrydetection.In Proceedings of the European Conference on Computer Vision(ECCV)(2018),pp.417–434.

[8]AU O.K.-C.,TAI C.-L.,CHU H.-K.,COHEN-OR D.,LEE T.-Y.:Skeletonextraction by mesh contraction.ACM Transactions on Graphics 27,3(Aug.2008),44:1–44:10.

[9]WANG Y.,XU K.,LI J.,ZHANG H.,SHAMIR A.,LIU L.,CHENG Z.,XIONG Y.:Symmetry hierarchy of man-made objects.In Computer graphics forum(2011),vol.30,Wiley Online Library,pp.287–296.

[10]RUSINKIEWICZ S.,LEVOY M.:Efficient variants of the icpalgorithm.In Proc.of 3th International Conference on 3-D Digital Imaging andModeling Proceedings(2001),pp.145–152.

[11]TIERNY J.,VANDEBORRE J.-P.,DAOUDI M.:3d mesh skeleton extractionusing topological and geometrical analyses.In Proc.of 14th Pacific Conferenceon Computer Graphics and Applications(PG’06)(Tapei,Taiwan,Oct.2006),pp.85–94.6

发明内容

本发明技术解决问题：克服现有技术的不足，提供一种基于骨架引导的三维模型内蕴对称性检测方法，以所生成的模型线骨架为指导，基于骨架对模型进行凸剖分处理，再基于外蕴对称凸体的组合来检测模型中的内蕴对称体，具有简便、高效的优点。

本发明的技术方案，一种基于骨架引导的三维模型内蕴对称性检测方法，包括以下步骤：

(1)生成三维模型的骨架，并基于骨架对三维模型进行凸剖分，建立骨架肢子段和骨架结点与凸剖分的凸体之间的对应关系；骨架由一些节点及连接节点之间的边组成，其中由两条以上的骨架边共享的节点称为骨架结点，从一个骨架结点开始到另一个骨架结点或者骨架的一个端点的一串边，则形成一个骨架肢，在此骨架端点指只有一条边关联的节点；

(2)根据长度相似的骨架肢子段(即骨架肢剖分后的子部分)和骨架结点，检测骨架肢子段和骨架结点对应的凸体间的外蕴对称性。两个形体如能通过刚性变换使得它们重合，则称它们之间是外蕴对称的；如果两个形体可通过非刚性变化使得它们重合，则称它们之间是内蕴对称的；

(3)在骨架中寻找相似的结构，由此检测相似结构所属的各个对应的凸体之间的外蕴对称性，再基于凸体组合的方式，寻找三维模型的内蕴对称体；

所述步骤(1)生成模型的骨架，并基于骨架对模型进行凸剖分，建立骨架肢子段和骨架结点与凸剖分的凸体之间的对应关系，具体步骤为：

(11)根据模型网格收缩的方法，生成三维模型的骨架；

(12)根据骨架肢对模型网格的对应关系信息，对三维模型进行初始化剖分，并依据骨架肢与骨架结点之间的凹信息行剖分优化，使得各个骨架结点都对应一个凸剖分体，而每个骨架肢对应一个剖分体；

(13)根据三维模型上的凹信息对初始化剖分的各个部分进行凸剖分，并将剖分时的凹处情况对应到骨架肢上，对骨架肢进行子分，形成骨架肢的子段；

(14)对于长度相当的骨架肢，将它们的子分情况进行相互迁移处理，使得长度相当的骨架肢具有类似的子分情况；

(15)根据骨架肢的子分情况，对各自关联的凸体进行进一步的子分，使得骨架肢的各个子分段都分别对应一个剖分的凸体。

所述步骤(2)中，根据相似的骨架肢子段和骨架结点，检测两者对应的凸体之间的外蕴对称性，具体步骤为：

(21)查找长度相当的骨架肢子段，检测它们各自对应的凸体之间是否是外蕴对称的；

(22)检测骨架结点对应的凸体之间是否是外蕴对称的。

所述步骤(3)中，在骨架中寻找相似的结构，由此检测它们所属的各个对应的凸体之间的外蕴对称性，再基于凸体组合的方式，寻找三维模型的内蕴对称体；，具体步骤如下：

(31)找到长度相当的骨架肢，形成一个相似的骨架结构；

(32)以各个骨架结点为根结点，逐步地关联相连接的相似骨架肢、以及其它相似的树状骨架结构来生成相似的骨架结构；

(33)基于相似的骨架结构，检测它们之间各自对应的凸体之间是否都是外蕴对称的；如果是，则这些相似骨架结构对应的模型部分就是内蕴对称的本发明与现有技术相比的优点在于：

(1)本发明很好地降低了内蕴对称性检测的计算复杂度，并能检测到小型对称体、嵌入到大对称体中的子对称体等已有方法难以找到的对称体，具有简便、高效的优点。

(2)本发明基于模型的凸剖分体之间的外蕴对称性，使用模型的相似骨架结构来组合对称的凸体，以进行内蕴对称检测。相比于已有方法，本发明很好地降低了计算复杂度，避免了基于统计方法难以找到小尺度对称体和嵌入型对称体的不足，能得到高质量的对称体。实验结果表明，本发明可以找到更多的对称体，运行速度也比现有方法快很多，甚至有几个数量级的提升。

附图说明null实施方式

下面结合附图及实施例对本发明进行详细说明。

如图1所示，本发明具体步骤如下：

(2)凸体的外蕴对称性检测：在检测剖分后的凸体之间的外蕴对称性时，首先找到骨架上相似的骨架肢子段和骨架结点，然后检查它们对应的凸体是否对称。在此，如果两个骨架肢子段的长度相似，则认为它们是相似的；然后对它们关联的凸体进行外蕴对称性检测。如果两个骨架结点对应的凸体的体积相似，则认为它们是相似的。

(3)多尺度局部内蕴对称性检测：在得到剖分凸体之间的外蕴对称性之后，通过相似骨架结构的引导，基于组合的方式，寻找模型的内蕴对称体。对于相似的两个骨架结构，如果它们所属凸体均是各自对应地外蕴对称的，则它们对应的部分就是内蕴对称的。相似的骨架结构，是由小至大逐步增长来寻找的，所以，可进行多尺度的内蕴对称性检测。

在下面对本发明的各个步骤分别介绍。

1.曲线骨架生成并基于骨架对模型进行凸剖分

(1)骨架生成。考虑到实现的方便性，采用了[8]中的方法进行初始化曲线骨架生成，然后对骨架进行改进，使之很好地满足我们的需求。由于模型的细节影响，初始化的骨架可能具有冗余的骨架结点，如图2中的(b)所示，右手掌有两个连接结点。这会导致骨架对模型的拓扑结构表达不准确。为此，设计了一个简单的方法，用于快速查找冗余结点并进行归并处理以消除冗余结点。该方式主要考虑了两个重要因素，即结点之间的距离和结点对应部分的大小。其处理是依据两个结点之间的欧几里德距离(Ed)，以及与模型中这两个结点相对应的内接球体半径的和(Sr)。如果Ed<σ*Sr，则认为它们是多余的，并把这两个连接结点合并为一个连接结点，如图2(c)所示。σ一般设置为1.5就能得到高质量的结果。

(2)基于凸信息的剖分优化。利用骨架肢和骨架结点与模型之间的对应关系对模型进行初始化剖分，然后用两个步骤来优化模型的初始化剖分。第一个步骤是利用相邻骨架肢和骨架结点对应的剖分部分上的凹信息来进行优化，第二个步骤是利用骨架肢对应部分上的凹信息进行优化。

基于高斯曲率，通过下式计算圈线1的凹度C(l)：