一种基于树型空间的三维树木模型匹配方法

摘要

本发明涉及一种基于树型空间的三维树木模型匹配方法，包括以下步骤：S1：构建树木模型数据集，并获取树木手绘轮廓；S2：构建树型空间，并将树木手绘轮廓的点数据和树木模型数据集中三维树木模型的点数据统一映射到树型空间中；S3：计算树木手绘轮廓和树木模型数据集中三维树木模型的凸包；S4：基于扫描算子的网格化编码进行降维操作；S5：对树木手绘轮廓和树木模型数据集中的三维树木模型进行相似性计算，完成三维树木模型的匹配。与现有技术相比，本发明具有准确率高、有效提高三维树木模型大规模检索重用效率等优点。

说明书

技术领域

本发明涉及三维模型匹配领域，尤其是涉及一种基于树型空间的三维树木模型匹配方法。

背景技术

在图形图像领域，三维模型具有内容丰富真实，展现能力强的优势，其拥有更全面的信息，更能与生活实际相结合，是3D领域中良好的媒介，被大量使用于出行、建筑等多个领域。在检索领域如何实现三维模型的快速检索也渐渐成为重大的研究课题，对于三维模型的检索能够大大提高相应模型的复用率，因为有许多三维模型建模完成之后也许就只是堆砌在数据集中并没有发挥任何作用，因此三维模型的快速检索可以加速三维模型重用事件的发生。但是目前在三维模型快速检索领域的相关工作中，大多数的方法仅仅只是聚集在对于常用的通用三维模型检索上，很多特定领域的三维模型在目前的检索方法中并没有获得较好的结果。

早期的模型检索方法主要是通过输入模型的自身模型间的相似性差异来达到检索三维模型的目的，主要有如下几类方法，基于数学方向的统计模型检索、基于模型骨架的检索、基于低维代入的检索和基于模型变换的检索。

研究员Tor在霍夫变换的基础上，提出使用数学方法保留输入模型的几何特征，根据保留的特征去检索三维模型。基于多视图多描述方法主要是通过对输入的三维模型进行投影，从而获取其相应的二维视图，然后计算二维视图和三维模型之间的相似性来获取与三维模型匹配的模型。刘在文章中提出，可以针对不同的复杂三维模型科学地选择三维模型的二维投影的最佳视角。还讨论了在不丢失模型输入的有效信息的情况下，完成与输入的手绘轮廓配对。通过数学统计来实现三维模型的检索在检索领域是比较常见的方法，由于数学统计中涉及到公式表达以及参数定义等比较贴近学习中所见识到的，而且直接通过数学统计也能较快获得相应的匹配结果，如果在输入过程中辅助高端输入设备也能够实现模型的精确配对。

虽然通过数学统计多视图的检索方式可以在检索过程中获得很好的配对效果，但是此过程中的难处在于在获取结果之前并不清楚到底是需要获取哪些视图，以及如何通过统一标准去度量模型间的相似。在历史的研究方法中，很多度量都可以达到上述的目的，比如傅里叶和zernike矩能够完成对于模型间相似性的度量，guan提出在树型空间生成完成的基础上通过欧式度量和测地线来衡量三维大规模模型间的相似性。

虽然目前的检索算法对于通用三维模型姑且能够获得良好的搜索效果，然而对于许多细分领域比如树木、出行等的三维模型，并没有获取较好的效果。Fan方法通过获取三维模型的局部视图然后再对输入的树木三维模型采用递进检索去完成检索的流程，然而这种方法对于系统的整体输入过于限制，使得用户只能按照其所描述的部分图示来进行操作，而并不能绘制任何自己期望的树木种类，极大限制了整个系统的创造性。

上面提到的部分检索方法大多都是聚集在通用种类的模型检索上，在一些常见的细分模型领域上述方法并不能取得良好的检索效果，且检索性能方向上均具有结果不正确、语义不符合等问题，极大影响三维模型的大规模检索和重用效率。

发明内容

本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种准确率高、有效提高三维树木模型大规模检索重用效率的基于树型空间的三维树木模型匹配方法。

本发明的目的可以通过以下技术方案来实现：

一种基于树型空间的三维树木模型匹配方法，包括以下步骤：

S1：构建树木模型数据集，并获取树木手绘轮廓；

S2：构建树型空间，并将树木手绘轮廓的点数据和树木模型数据集中三维树木模型的点数据统一映射到树型空间中；

S3：计算树木手绘轮廓和树木模型数据集中三维树木模型的凸包；

S4：基于扫描算子的网格化编码进行降维操作；

S5：对树木手绘轮廓和树木模型数据集中的三维树木模型进行相似性计算，完成三维树木模型的匹配。

进一步地，所述的树木模型数据集包括通用数据集和共享数据集，所述的通用数据集为现有图像数据集，所述的共享数据集由通过网络爬虫共享获取的树木模型构成，所述的树木模型数据集中，将所有的三维树木模型分为乔木、灌木和草本植物三类。由于通用数据集中的模型种类和数量并不能充分满足本发明模型匹配的要求，因此本发明还通过另一个方向即网络共享的方式来对通用数据集中的模型进行增补。

进一步地，所述的步骤S2具体包括：

S21：通过PCA主成分分析方法分别对树木手绘轮廓和三维树木模型进行预处理；

S22：计算树木手绘轮廓和三维树木模型相应的骨架表示，找到分支对应，并对分支对应进行颜色编码；

S23：通过树图表示每个植物树，并用二叉树对树图进行扩充、二值化和参数化；

S24：将各植物树以点的形式表示，构建树型空间；

S25：将树木手绘轮廓的点数据和树木模型数据集中三维树木模型的点数据统一映射到树型空间中。树型空间中的测地线对应于树木手绘轮廓和三维树木模型之间的平滑几何和结构混合。

进一步地，所述的步骤S3中，计算树木手绘轮廓的凸包具体包括：

S31：获取树木手绘轮廓点数据的坐标点(U,V,W)；

S32：获取所有坐标点中纵坐标y轴的最小的点y

S33：将所有坐标点移动至以Z

S34：计算各坐标点相对于起始点的仰角α，并将计算结果依照从小到大进行顺序排序；

S35：在起始点与仰角α最小的坐标点之间作直线M；

S36：比较当前计算的坐标点位于直线M的左边或右边，若当前计算的坐标点位于直线M的左边则进行入栈操作，否则进行出栈操作；

S37：判断是否到达结束坐标点，若否，则将当前选取的计算坐标点作为起始点，并返回执行步骤S34，否则结束流程，输出标识凸包结果；

所述的树木模型数据集中三维树木模型凸包的计算与树木手绘轮廓的凸包计算相同，树木模型数据集中三维树木模型点数据的坐标为(U

优选地，所述的步骤S4使用神经网络中的卷积实现运算量的降低，因为卷积核可以通过滤波器的操作把输入过程中的高维数据降维成保留主要特征的低维数据，也能够缓解后续匹配过程中存在的过匹配。

进一步地，所述的步骤S5具体包括：

S51：对树木手绘轮廓和树木模型数据集中三维树木模型进行相似性计算，输出初步匹配的三维树木模型；

S52：计算树木手绘轮廓和输出的初步匹配三维树木模型测地线距离，并依据距离表现导出排序结果；

S53：按照排序结果依次输出每个距离对应的三维树木模型，完成三维模型匹配。

进一步优选地，所述的相似性计算使用欧式距离进行计算，由于树木模型数据集中的三维树木模型在输入过程中已经通过了中心处理，其对应的输出模型并不会存在空间方向的差异，在后续的差异计算中仅仅只需要计算坐标上的差异值，因此本文未选取夹角余弦这一度量。而且由于前述构建的树型空间选取的欧式度量和测地线距离的契合程度更高，在后续的计算过程中更加灵活，对于未来的多视角或者多浏览器融合能够提供更高的接洽程度，并且欧式度量对于高维数据的度量程度更加精确，能够精准表达相应高维向量之间的最大化差异程度，因此本文选取欧式度量和测地线距离来对手绘轮廓和输出模型之间的差异进行计算。

所述的步骤S52中，计算测地线距离具体包括以下步骤：

S251：在树型空间上，对树木手绘轮廓点数据和树木模型数据集中三维树木模型点数据进行配对，获取配对成功的数据点；

S252：将配对成功的数据点中部分坐标点进行参数化，并生成起始搜索路径；

S253：在搜索过程中将对应的坐标点生成测地线的过渡中间坐标点序列；

S354：将起始搜索路径理顺，得到一条矫直的搜索路径；

S355：把矫直的搜索路径最小化为相对应的度量单位，并将对应的坐标点序列保持在同一子空间。

更进一步地，所述的步骤S34的排序过程中，若两个坐标点的仰角α相同，则把与初始点差距小的点排在前。

更进一步地，所述的步骤S3中，计算凸包前，首先将树木手绘轮廓点数据和树木模型数据集中三维树木模型点数据以向量矩阵的形式保存，然后选取设定数量的点数据进行采样，再进行凸包计算。

与现有技术相比，本发明具有以下优点：

1)本发明通过构建三维模型的树型空间，把三维模型和手绘轮廓的点数据直接映射到相关的树型空间中，利用构建好的树型空间简化后面的模型匹配操作，把模型数据集中的数据坐标点与手绘轮廓中的坐标点数据量有效缩减，能够大幅提高树木模型匹配的准确率；

2)本发明中相似性度量包含两个部分，其中通过欧式距离来度量手绘轮廓与数据集中模型的相似程度，使得与输入的手绘轮廓匹配的结果尽可能精确，测地线距离衡量的是手绘轮廓与输出模型之间的距离差异，描述的是手绘轮廓与输出结果之间的相似程度，通过相似性度量和测地线距离，缩小手绘轮廓与输出结果之间的差异性，最终提升三维树木模型的大规模检索重用效率。

附图说明

图1为本发明整个框架的工作流程示意图；

图2为实施例中提供的方法流程图；

图3为根绝输入手绘轮廓匹配得到的模型示意图；

图4为自我构建数据集上，本发明方法与其他方法的PR曲线图。

具体实施方式

下面结合附图和具体实施例对本发明进行详细说明。显然，所描述的实施例是本发明的一部分实施例，而不是全部实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都应属于本发明保护的范围。

实施例

如图2所示，本发明提供的基于树型空间的三维树木模型匹配方法主要包含以下五个步骤：

1)通过通用数据集和共享数据集构建三维树木模型数据集；

2)构建树型空间，并把输入的手绘轮廓点数据与三维树木模型数据集中的模型数据统一映射到树型空间中；

3)计算输入手绘轮廓和数据集中模型数据的凸包；

4)对输入的手绘轮廓进行基于扫描算子的网格化编码并完成相应的降维操作；

5)利用欧氏距离与测地线对匹配结果进行差异度量，完成三维树木模型的匹配。

如图1所示，展示了本发明的工作流程示意图。接下来，本说明书同样分成这几部分对本方法加以详细说明。

步骤1)的具体方法为：

11)确定树木模型数据集的设计内容；

12)划分树木模型数据集的组织结构；

13)通过通用数据集和共享数据集的方式完成树木模型数据集原始搜集；

14)根据乔木、灌木、草本植物将原始数据集进行分类整理以获取完整访问路径。

其中通用数据集和共享数据集主要是大规模图像数据集以及网络爬虫共享获取得到的树木模型，进而组合形成树木模型数据集。

步骤2)的具体方法为：

21)对输入的手绘轮廓进行PCA预处理；

22)通过编码和二叉树的方式生成系统的树型空间；

23)把输入的手绘轮廓点数据与三维树木模型数据集中的模型数据统一映射到上述构建完成的树型空间中。

其中依据编码和二叉树来构建相应的三维树型空间具体为：先给定源树木模型和目标树木模型，计算其相应的骨架表示，然后找到分支对应关系。在此，分支对应进行颜色编码。然后用树图表示每个植物树，该树图共同编码其几何形状和结构，用最大的二叉树对树进行扩充、二值化和参数化。最后，在具有适当度量的树形空间中，将树表示为点。树形空间中的测地线对应于源树和目标树之间的平滑几何和结构混合。

步骤3)的具体方法为：

31)将手绘轮廓和三维树木模型数据集中的模型点数据以向量矩阵的形式保存，随后在点集中采样固定数量，然后根据凸包规则开始计算相应模型的凸包，后续使用下文所述的凸包算法来计算模型凸包。设定手绘轮廓和三维树木模型数据集中的模型点数据的坐标为(U,V,W)和(U

32)在上述的所有坐标点中首先找到坐标点中纵坐标y轴对应的最小的点min，即上述坐标点中比较靠x轴的坐标点，此处的坐标点记为Z

33)把上述所有的坐标点先移动到以上述Z

34)随后对坐标点相对于起始点的仰角进行计算，此处的仰角设为α，把上述计算的仰角结果依照从小到大进行顺序排序，如果在排序的过程中，两个坐标点的仰角相同的话，则把与Z

35)然后在仰角最小点与起始点之间作一条直线，设为M，在操作过程中，去比较当前计算的坐标点到底是位于这条直线的左边或者右边；

36)如果选取的计算坐标点是在这条直线上面还是位于这条直线的左边表示当前坐标点是属于模型凸包的点，则把它入栈，保留下对应的坐标位置，随后进行下一步操作；

37)如果选取的计算坐标点位于直线的右边说明上述的计算坐标点不属于模型凸包的数据，则把它从栈里移除，作出栈，随后进行下一步操作；

38)验证当前选取的计算坐标点是否满足所述的三维模型凸包节点的结束元条件，如果确认当前坐标点是整个环节的结束坐标则直接结束整体流程，否则把当前选取的计算坐标点作为下一步操作的起始点，返回相应的操作；

39)返回并标识凸包结果。

步骤4)的具体方法为：

基于扫描算子的网格化编码及降维重点是使用神经网络中的卷积进行整个运算过程中运算量的降低，因为卷积核可以通过滤波器的操作把输入过程中的高维数据降维成保留主要特征的低维数据，也能够缓解后续匹配过程中存在的过匹配。

步骤5)的具体方法为：

51)将初始输入的手绘轮廓数据和三维树木数据集中的模型数据合并导入对应的系统输入中；

52)对手绘轮廓和数据集模型进行相似性计算；

53)计算手绘轮廓和数据集的树木模型间的测地线距离，依据距离表现导出排序结果；

54)按照排序结果依次输出每个距离对应的三维模型，完成三维模型匹配。

相似性计算使用欧氏度量进行计算，由于树木模型数据集中的三维树木模型在输入过程中已经通过了中心处理，其对应的输出模型并不会存在空间方向的差异，在后续的差异计算中仅仅只需要计算坐标上的差异值，因此本文未选取夹角余弦这一度量。而且由于前述构建的树型空间选取的欧式度量和测地线距离的契合程度更高，在后续的计算过程中更加灵活，对于未来的多视角或者多浏览器融合能够提供更高的接洽程度，并且欧式度量对于高维数据的度量程度更加精确，能够精准表达相应高维向量之间的最大化差异程度，因此本文选取欧式度量和测地线距离来对手绘轮廓和输出模型之间的差异进行计算。

假定设定手绘轮廓和三维树木模型数据集中的模型点数据的坐标为(U,V,W)和U

其中，d

测地线计算为：在上述构建完成的树型空间上，对输入的手绘轮廓与三维树木模型数据集中模型的数据点完成配对，然后拣选出符合要求的数据点，把其中的部分坐标点进行参数化，依据参数化后的坐标去生成符合要求的起始搜索路径，随后在搜索的过程中将对应的坐标点生成测地线的过渡中间坐标点序列，然后把上述提到的搜索路径进行理顺之后，即得到一条矫直的搜索路径，由于起始搜索路径提供了过渡中间坐标点序列，所以需要对路径矫直。最后把上述的搜索路径理顺，即把搜索路径去最小化相对应的度量单位，并且在这过程中需要将对应的坐标点序列保持在同一子空间。

为了支持以及验证本发明提出的基于树型空间的三维树木模型匹配方法的性能，本文会在利用自己构建的数据集对本文方法的检索性能进行测试。本文在自身构建数据集的方向上是有两个主要来源：一个方向是对通用模型数据集中涉及到的部分符合要求的三维模型进行提取，还有一个方向是在网络web端对部分符合要求的模型通过爬虫获取其源文件，方便后续处理。对于通用模型数据集本文选择的是COCO2017，它的特征是大规模、具有标注信息等。COCO内部的模型数据采用的主要是json数据格式，一般是由名字和类构成的，coco主要包含有80类，内部的模型包含生活的方方面面，足够进行平常的科研工作。而且在COCO数据集中还存在多视角的模型特征描述，用户可以直接在特征描述文件中直接提取相应的描述信息即可。

本发明中，构建的数据集重点是提取了COCO2017中的树木大类数据。把其中的树木大类先整合成一个初步完整的数据集，然后对内部的模型进行分类，本文主要分为了三类，分别为乔木、灌木和草本植物，其中乔木模型有175个，灌木模型65个，草本植物有40个。由于COCO数据集中的模型种类和数量并不能充分满足本文的要求，因此本文还通过另一个方向即网络共享的方式来对通用数据集中的模型进行增补。

网络共享树木模型：这个数据集汇总的主要是在web浏览器中浏览到符合要求的树木三维模型，本实施例中，除了对web的模型进行下载收集外还在部分模型质量较差的情况下购买了建模质量完好的三维树木模型。web浏览器中搜集到的模型数据重点是通过Python爬虫去爬取特定URL中的三维模型数据，随后将上述模型保存在给定路径，在模型数量不足的情形下，也从商店购买或者在老师同学的帮助下搜集了部分三维树木模型。在对上述模型经过某些预处理操作，例如去除贴图、视图模糊、重复的模型，便能顺利构成三维树木模型数据集。最终的web共享数据集大体是分为乔木、灌木、草本植物3类，总共有乔木模型560，灌木模型390个，草本植物模型有200个。

本实施例在上述提到的自我构建的数据集上进行性能验证，采用查准率-查全率曲线(Precision-Recall曲线，简称PR曲线)、准确率均值(Average Precision，简称AP)、平均准确率均值(mean Average Precision，简称mAP)、操作时间等四个通用指标作为衡量标准，将本方法同其它三维树木模型检索方法进行了比较。

图4给出了自我构建数据集上，本发明的方法和其他方法的PR曲线图。图中可以看出，本文方法对于不同种的树木模型均能获得较好的匹配性能。表1给出了在自我构建数据集上，本方法关于AP、mAP指标的结果，根据结果范围得知本文匹配算法对于乔木而言有较大的匹配度。

表1自我构建树木模型数据集匹配性能结果

表2给出了本方法与fan方法的参数对比，因为本方法的预处理在后续的配对过程中实现的，所以导致本文与Fan不一致，在此过程中，并没有预处理时间这一指标的存在，从下述表2中的数据可以得知，本方法的匹配方法能够非常迅速地把手绘轮廓与相应的三维模型实现匹配，能够在较短的时间完成上述操作。

表2本文方法与fan方法对比

表3中给出了不同数据集下本方法对应的操作时间对比，由表3的数据可得，本匹配方法对于各数据集有较快速的识别程度，然而本方法对现行的一些搜索方法来讲还存在着些许的不同，仅此讨论可能的原因构成，因为整个流程中的数据集都是自己构建的，所以对于数据集的分类标准可能是与现行方法数据集的分类标准存在差异，导致最终的结果有些许不同，但是从表中可以看出，对应的匹配性能有了提升；还有对于本文方案中的输入方式而言，相对于目前现行方案都是图片输入或者是模型直接输入来说，图片输入是极其消耗时间和资源的，如果直接输入的三维模型，其中三角面片的处理更加耗费资源，处理起来对于用户体验极其不友好，而本文的输入方法可以很好地应用于web轻量化建模领域，降低数据量，来达到轻量化加载的目的。

表3操作时间对比

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的工作人员在本发明揭露的技术范围内，可轻易想到各种等效的修改或替换，这些修改或替换都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应以权利要求的保护范围为准。