下载文档原格式
基于网格分割的三维模型轻量化算法及构建金伟祖;潘伟龙【摘要】三维建模指通过三维制作软件构建出具有三维数据的模型.三维建模技术可以大大增加物体的真实感.传统的三维建模技术首先对真实物体进行抽象,用多边形构造物体的三维模型,往往伴随着缓慢的生成速度.为保证三维建模以及模型展现的效率,三维模型的轻量化技术必不可少.基于重复的网格分割算法通过发现重复单元来提高模型展现效率,但是该算法对于单连通模型的效果不佳,因此在引入几何描述符的基础上,提出一种基于网格分割的模型轻量化算法,该算法包括网格分割,单元匹配和网格重建三个环节,算法能够发现经过旋转,缩放,平移后的重复单元,很好的提高轻量化效率.实验表明,该分割算法在网格轻量化中可以取得较高的存储压缩率.【期刊名称】《实验室科学》【年(卷),期】2015(018)005【总页数】4页(P20-23)【关键词】三维模型;模型轻量化;重复单元;网格分割【作者】金伟祖;潘伟龙【作者单位】同济大学软件学院,上海201804;同济大学软件学院,上海201804【正文语种】中文【中图分类】TP37三维模型特有的真实感，使得三维模型在各类应用决策中正得到广泛应用。
如何保证三维建模以及模型展现的效率至关重要，核心问题就是三维模型的轻量化，减少三维模型数据的存储量是研究的焦点之一。
本文具体分析了现有的、基于轻量化的模型分割算法，并分析它们各自的优劣和适用场景，最终在这些算法的基础上提出一种针对模型轻量化的网格分割算法，并以该算法为基础，提出了三维模型的轻量化构建步骤。
1 基于重复单元的轻量化研究重复单元是指模型中相同或相似的部分，这些相似的部分可以通过一系列几何变换来完成。
重复单元的轻量化是指通过提取模型中的重复单元，只保存一份模型数据和几何变换信息代替整个模型，达到大幅度减少数据存储量的目的。
在三维模型中，常常含有很多相似或者可以通过几何变换而变得相似的部分，例如一个建筑中含有很多窗口，而这些窗口模型之间是可以通过平移来转换的，即可以通过保存一份窗口模型的数据和平移信息来实现对窗口的保存，这样就可以使用更少的数据来保存窗口模型。
图片简介:本说明书实施例提供了半监督语义分割模型训练方法、识别方法和装置，根据实施例的半监督语义分割模型训练方法，首先通过获取人工对第一图像中的待标注对象进行标注后得到的第一监督数据，进而通过第一监督数据训练得到对待标注对象的识别率相对较高的全监督语义分割模型。
利用全监督语义分割模型对未经过人工标注的第二图像中的待标注对象进行标注，得到第二监督数据。
再利用经过人工标注得到的第一监督数据和经过全监督语义分割模型标注得到的第二监督数据训练半监督语义分割模型，并利用半监督语义分割模型对第一图像、第二图像和随机扰动项进行识别，得到第三监督数据。
最后通过第一、第二和第三监督数据对半监督语义分割模型再次训练。
技术要求1.半监督语义分割模型训练方法，所述半监督语义分割模型用于对图像中的待标注对象进行标注；包括：获得每一张第一图像的第一监督数据；每一张第一图像的第一监督数据为针对该第一图像中的待标注对象进行人工标注后得到的数据；利用各第一监督数据训练全监督语义分割模型；将至少一张第二图像输入所述全监督语义分割模型；其中，每一张第二图像中包括待标注对象；由所述全监督语义分割模型对每一张第二图像中的待标注对象进行标注，获得每一张第二图像的第二监督数据；利用各第一监督数据和各第二监督数据训练所述半监督语义分割模型；生成随机扰动项；将至少一张所述第一图像、至少一张所述第二图像和所述随机扰动项输入所述半监督语义分割模型，获得每一张图像的第三监督数据；所述每一张图像的第三监督数据为由所述半监督语义分割模型对该图像中的待标注对象进行标注后得到的数据；利用各第三监督数据、各第一监督数据和各第二监督数据，对所述半监督语义分割模型进行训练。
2.根据权利要求1所述的方法，其中，所述随机扰动项的个数为至少两个；所述将至少一张所述第一图像、至少一张所述第二图像和所述随机扰动项输入所述半监督语义分割模型，获得每一张图像的第三监督数据，包括：针对每一个随机扰动项，将至少一张所述第一图像、至少一张所述第二图像和该随机扰动项输入所述半监督语义分割模型，获得在输入该随机扰动项时至少一张所述第一图像和至少一张所述第二图像中的每一张图像的第三监督数据；所述利用各第三监督数据、各第一监督数据和各第二监督数据，对所述半监督语义分割模型进行训练，包括：针对所述每一张图像，计算在输入不同随机扰动项时所获得的不同的第三监督数据之间的差异，得到该图像的第一监督损失；针对每一张第一图像，计算该第一图像的第三监督数据与该第一图像的第一监督数据之间的差异，得到该第一图像的第二监督损失；针对每一张第二图像，计算该第二图像的第三监督数据与该第二图像的第二监督数据之间的差异，得到该第二图像的第二监督损失；利用得到的各第一监督损失和各第二监督损失，对所述半监督语义分割模型进行训练。
三维网格的Mean Shift并行分割算法孙晓鹏;荣丹【期刊名称】《计算机工程与设计》【年(卷),期】2013(034)001【摘要】为克服Mean Shift算法复杂度高、速度慢的缺点,提出了一种改进的三维网格模型Mean Shift并行分割算法.该方法基于Mean Shift的基本思想和GPU 的高性能并行计算能力,基于离散测地距离的局部极值提取三维网格模型的显著特征点,自显著特征点开始并发执行Mean Shift算法,实现了有意义的分割.与同类算法相比,该算法提高计算运行效率、改善了分割效果.%In order to overcome the shortcomings of the mean shift method for its complex computational requirement, an improved 3D mesh model mean shift parallel segmentation algorithm is presented. Based on the ideas of Mean Shift and high performance parallel computing capacity of the GPU, firstly, the salient feature points are extracted on 3D mesh model using discrete geodesic distance of the local extreme point, and then the Mean Shift algorithm is parallel executed from the salient feature, so that the algorithm achieves the meaningful division. Compared with other similar algorithms, the computational efficiency and the effect of the segmentation are imropved.【总页数】5页(P230-234)【作者】孙晓鹏;荣丹【作者单位】辽宁师范大学计算机与信息技术学院,辽宁大连116029;大连大学辽宁省先进设计与智能计算省部共建教育部重点实验室,辽宁大连116622;辽宁师范大学计算机与信息技术学院,辽宁大连116029【正文语种】中文【中图分类】TP391.41【相关文献】1.基于多层k路划分的三维网格并行任务分配策略 [J], 于方;郑晓薇;孙晓鹏2.基于三维网格的最短路径并行算法研究 [J], 武亮亮;郑晓薇3.基于SMP集群的三维网格多粒度混合并行编程模型 [J], 于方;郑晓薇;孙晓鹏4.面向局部突起的三维网格分割算法研究 [J], 华顺刚;李世皓5.三维网格表面的分层分割算法 [J], 严京旗;施鹏飞因版权原因，仅展示原文概要，查看原文内容请购买。
基于半监督学习的图像分割技术研究图像分割技术是计算机视觉领域中的一项重要技术，它的主要目的是将一张图像分割成不同的区域或者对象，为图像处理和图像识别提供基础。
目前，图像分割技术已经广泛应用于医学图像处理、人体姿态识别、智能交通等领域。
然而，传统的图像分割技术仍然存在许多问题，例如模型复杂、效率低下等，因此研究基于半监督学习的图像分割技术具有重要的实际意义。
半监督学习是机器学习中的一种方法，它是有监督学习和无监督学习的结合。
在图像分割中，半监督学习可以利用未标记的图像来增加分割模型的准确性，提高图像分割的效果。
半监督学习还可以降低人工标记样本的负担，提高数据利用率。
因此，基于半监督学习的图像分割技术成为了当前研究的热点之一。
基于半监督学习的图像分割技术主要分为两种方法：基于图嵌入和基于生成对抗网络。
基于图嵌入的方法将图像分割看作是一个图中节点的分类问题，用图嵌入的方法将图像中的像素点转化为节点，并构建节点间的连接关系。
然后，利用以往的已标记数据训练基本模型，再利用未标记的数据进行训练，进一步提高模型的准确性。
基于生成对抗网络的方法则使用生成器和判别器两个神经网络对图像进行分割。
生成器负责将输入的图像分割成不同的对象，判别器则负责判断生成器分割结果的真实性。
这种方法的优点是可以避免训练数据的过拟合问题，增加模型的鲁棒性。
在基于半监督学习的图像分割技术中，常用的误差函数有像素级别的误差函数和区域级别的误差函数。
像素级别的误差函数计算每一个像素点的分类结果与标签之间的误差，因此计算精度高，但计算量大，速度较慢。
区域级别的误差函数则将图像分成若干个区域，计算每个区域的分类误差，运算速度较快。
因此，在实际应用中，可以根据需要选择不同的误差函数，以达到更好的效果。
除了误差函数外，正则化算法也可以提高基于半监督学习的图像分割技术的效果。
其中，拉普拉斯正则化是一种常用的正则化方法，它可以在未标记的数据上学习到更加平滑的模型参数，进而提高模型的泛化能力。
基于半监督学习的语义分割算法研究语义分割是计算机视觉领域中的一个重要问题。
目的是把图像中每一个像素映射成对应的类别，这对于图像分析、自动驾驶等应用非常有用。
常见的语义分割方法包括像素嵌入、卷积神经网络等。
这些方法虽然有着出色的表现，但是样本标记成本高昂，数据集不够完备，甚至是分布不平衡都会影响算法的性能。
为了克服这些问题，半监督学习成为了一种应对语义分割问题的有效手段。
半监督学习利用未标记样本和少量标记样本来构建分类器，显著降低了模型标记成本。
同时，半监督学习还可以获得更优秀的泛化性能，因为未标记样本可以提供更全面更细节的信息。
目前，基于半监督学习的语义分割算法已成为研究热点，下面将介绍一些常见的半监督学习方法在语义分割中的应用以及其中的难点。
1.基于半监督图卷积神经网络的语义分割半监督图卷积神经网络是一种可以处理图像、语音和文本等数据的全新神经网络结构。
图卷积神经网络发展到今天已经成为CNN和RNN之外的第三种深度学习技术，被广泛应用于图像分类、节点分类和图形表示等问题。
与传统卷积神经网络不同，图卷积神经网络的基础不是卷积核，而是卷积图和卷积邻接矩阵。
使用半监督图卷积神经网络进行语义分割时，每个像素点对应一个节点，相邻的节点之间在卷积邻接矩阵中连接一条边。
通过使用非监督学习训练的卷积神经网络可以预测未标记样本的标签，提高了语义分割的精度。
2.基于生成性对抗网络的语义分割生成性对抗网络是一种通用的无监督学习模型，可以训练出逼真的样本模型。
在语义分割中，生成性对抗网络可以通过两个深度神经网络来进行训练：一个生成网络（可以理解为半监督学习中的预测模型），另一个判别网络（可以理解为半监督学习中的标记模型）。
生成网络的任务是生成与输入图像类似的图像，而鉴别网络的任务是区分生成的图像与真实图像。
在语义分割中，判别器网络训练时需要使用实际标记的图像数据，而生成器网络则可以使用实际标记和未标记的图像数据训练。
基于半监督深度学习的语义分割半监督深度学习的语义分割技术是计算机视觉领域的一个重要研究方向。
语义分割旨在将图像中的每个像素分配给特定的语义类别，从而实现对图像的精细级别理解。
然而，传统的语义分割方法通常需要大量标记好的训练数据，这在实际应用中往往是昂贵且耗时的。
半监督深度学习技术通过利用有标签和无标签数据来解决这个问题，为语义分割任务提供了一种有效且经济实用的解决方案。
半监督深度学习方法基于深度神经网络模型，通过利用无标签数据来增强模型训练。
传统监督学习方法通常使用有标签数据训练模型，但这种方法在大规模图像数据集上往往需要耗费大量时间和精力来手动标注每个像素。
相比之下，半监督学习可以利用无标签数据来提供额外信息，并通过联合优化有标签和无标签样本之间的相互关系来提高模型性能。
在半监督深度学习中，一种常见且有效的方法是使用生成对抗网络（GAN）来进行语义分割。
GAN由生成器和判别器组成，通过对抗训练的方式来提高模型的性能。
生成器负责生成分割结果，判别器则负责评估生成结果的真实性。
通过训练生成器和判别器，模型可以逐渐提高对图像语义的理解能力。
此外，半监督深度学习还可以利用自监督学习来进行语义分割。
自监督学习是一种无监督学习方法，通过利用图像自身的信息来进行训练。
在语义分割任务中，可以通过将图像中的某些区域遮盖或删除，并要求模型预测被遮盖或删除区域的标签来实现自监督学习。
这种方法可以利用大量无标签数据进行训练，并且能够提高模型在真实数据上的性能。
此外，在半监督深度学习中还有一种常见方法是使用半监督聚类技术进行语义分割。
聚类是一种将相似样本归类到同一组别的技术，在半监督聚类中，使用有标签样本和无标签样本共同训练聚类模型，并将聚类结果作为图像的语义分割结果。
这种方法可以利用无标签数据进行训练，并且能够有效地利用数据分布信息进行语义分割。
总结起来，基于半监督深度学习的语义分割技术通过充分利用有标签和无标签数据来提高模型性能。
基于半监督深度学习的语义分割第一章：引言语义分割是计算机视觉领域的重要问题之一，旨在将图像中的每个像素标记为属于哪个语义类别。
该任务具有广泛的应用，包括自动驾驶、医学图像分析、图像编辑等。
然而，语义分割面临着像素级标注昂贵的问题，因为需求大量标记样本。
针对这一问题，半监督深度学习提供了一种有效的解决方法，可以利用未标记样本进行模型训练。
第二章：半监督深度学习简介2.1 深度学习概述深度学习是一种机器学习方法，通过多层神经网络模拟人脑的工作原理，具有强大的学习能力和表达能力。
2.2 监督学习与半监督学习监督学习利用有标签的数据进行模型训练，而半监督学习则既利用有标签的数据，也利用未标记的数据进行训练，提供更多的信息用于模型学习。
2.3 半监督深度学习算法半监督深度学习算法结合了深度学习和半监督学习的思想，可以通过利用未标记样本的特征信息来提高模型性能。
第三章：传统语义分割方法综述3.1 基于传统机器学习的方法传统语义分割方法通常基于手工提取的特征和分类器进行像素级别的分类，但难以捕捉到图像的高层语义信息。
3.2 基于深度学习的方法深度学习方法通过卷积神经网络（CNN）进行特征提取和像素分类，取得了显著的成果，但仍然需要大量的有标签样本。
第四章：半监督深度学习在语义分割中的应用4.1 基于半监督迁移学习的方法半监督迁移学习利用已标记样本的知识，将其迁移到未标记样本中，从而提高模型的泛化能力。
4.2 基于生成对抗网络的方法生成对抗网络（GAN）可以通过生成器和判别器的对抗过程，生成逼真的未标记样本，并利用这些样本进行模型训练。
4.3 基于自监督学习的方法自监督学习利用无监督的目标进行模型训练，例如通过图像旋转、颜色变换等方式生成伪标签，在无需人工标注的情况下进行模型训练。
第五章：实验与评估5.1 数据集与实验设置选择合适的数据集进行实验，并设置合理的实验参数，以评估半监督深度学习在语义分割中的性能。
5.2 实验结果与对比分析对比半监督深度学习方法与传统方法的性能差异，并进行结果分析，展示半监督深度学习在语义分割中的优势。
基于半监督学习的图像分类与分割方法研究进展图像分类和分割是计算机视觉领域的重要任务，在许多应用中起着至关重要的作用。
然而，由于标注数据的昂贵和耗时，仅依靠有标注的数据进行图像分类与分割是不可行的。
因此，半监督学习方法在图像分类与分割中得到了广泛的应用并取得了显著的研究进展。
本文将对基于半监督学习的图像分类与分割方法的研究进展进行综述。
一、半监督学习概述半监督学习是介于监督学习和无监督学习之间的一种学习范式。
它利用少量有标注的数据和大量无标注的数据进行学习，以提高模型的泛化能力。
在图像分类与分割任务中，利用无标注数据进行半监督学习可以充分利用数据的潜在信息，提高分类与分割的准确性。
二、基于半监督学习的图像分类方法1. 图像标签传播算法图像标签传播算法是一种基于图模型的半监督学习方法，通过将标记样本的标签信息传播到未标记的样本上，从而实现图像分类。
该方法假设空间上相邻的像素或区域具有相似的标签，利用这种相似性进行标签传播。
标签传播算法在图像分类中取得了较好的效果，但对图像中存在的噪声和纹理信息不敏感。
2. 基于图生成的方法基于图生成的方法是一种利用无标注数据生成图像标签的半监督学习方法。
该方法首先利用无标注数据构建图模型，然后通过图像生成模型来生成标签信息，并使用生成模型学习得到的标签进行分类。
这种方法在大规模无标注数据上实现了较好的效果，但对于小规模数据集表现较差。
三、基于半监督学习的图像分割方法1. 图割算法图割算法是一种经典的半监督学习方法，广泛应用于图像分割任务中。
该算法通过在图像中构建图模型，并利用图割算法进行优化，将图像分割为不同的区域。
图割算法在图像分割中获得了较好的分割效果，但对于复杂的图像场景仍存在一定的挑战。
2. 基于聚类的方法基于聚类的方法是一种常用的半监督学习方法，通过将图像像素划分为不同的聚类簇来实现图像分割。
该方法首先利用无标注数据进行聚类，然后根据聚类结果将像素分配到相应的簇中，从而实现图像分割。
《半监督深度生成模型构建方法研究》一、引言随着深度学习技术的不断发展，半监督学习在机器学习和人工智能领域得到了广泛的应用。
半监督学习结合了监督学习和无监督学习的优点，能够利用少量的标记数据和大量的未标记数据进行训练，从而提高了模型的性能。
深度生成模型是一种重要的深度学习技术，能够学习数据的内在规律和表示，用于解决各种复杂的机器学习任务。
本文将重点研究半监督深度生成模型的构建方法，旨在提高模型的泛化能力和准确性。
二、背景及意义在传统的机器学习中，模型训练通常需要大量的标记数据。
然而，在实际应用中，标记数据的获取往往需要耗费大量的人力、物力和时间。
此外，由于数据的复杂性和多样性，仅依靠少量的标记数据往往难以获得满意的模型性能。
因此，如何利用大量的未标记数据来提高模型的性能成为了研究的重要方向。
半监督深度生成模型正是为了解决这一问题而提出的。
半监督深度生成模型结合了半监督学习和深度生成模型的优点，能够利用少量的标记数据和大量的未标记数据进行训练，从而提高了模型的泛化能力和准确性。
此外，深度生成模型还能够学习数据的内在规律和表示，为解决各种复杂的机器学习任务提供了强有力的工具。
因此，研究半监督深度生成模型的构建方法具有重要的理论价值和实际应用意义。
三、相关技术及文献综述半监督学习是一种结合了监督学习和无监督学习的学习方法，能够利用少量的标记数据和大量的未标记数据进行训练。
深度生成模型是一种重要的深度学习技术，能够学习数据的内在规律和表示。
近年来，许多研究者将半监督学习和深度生成模型相结合，提出了各种半监督深度生成模型。
其中，基于生成对抗网络的半监督深度生成模型是一种重要的方法。
该方法利用生成器学习数据的内在规律和表示，利用判别器进行半监督学习。
此外，还有一些基于自编码器的半监督深度生成模型，通过引入标签信息来提高模型的性能。
这些方法在图像分类、语音识别、自然语言处理等领域都取得了很好的效果。
四、半监督深度生成模型的构建方法本文提出了一种基于生成对抗网络的半监督深度生成模型构建方法。
基于半监督学习的图像语义分割算法研究章节一：研究背景和意义图像语义分割（Image semantic segmentation）是一种将图像中的每个像素分配到其所对应的类别的图像分割技术。
这种技术已经在计算机视觉领域广泛应用，例如自动驾驶、医学图像分析和地球观测等方面。
传统的语义分割方法需要大量的手动标记数据，这限制了其在实际应用中的应用。
半监督学习（Semi-supervised learning）是一种机器学习方法，利用少量的有标记数据和大量的无标记数据来构建分类模型，可有效地解决缺少有标记数据的问题。
基于半监督学习的图像语义分割旨在利用少量有标记数据和大量无标记数据，构建出更加准确和稳定的模型。
章节二：基本原理与算法流程基于半监督学习的图像语义分割算法主要分为两个部分:有监督分割和半监督分割。
有监督分割部分使用已标记的训练数据，进行图像分类的训练，得到一个初步的分类器。
半监督分割部分，通过利用无标记数据来提高初始分类器的准确性，同时减少出错的可能性。
常用的基于半监督学习的图像语义分割算法包括以下几种：1. 超像素分割法超像素分割法将图像分解为更小的平滑区域，称为超像素。
该算法通过聚类方法对超像素进行分类，以便在分类器中建立无监督信息，从而提高有监督分类的准确性。
2. 图形卷积网络（GCN）方法图形卷积网络（GCN）是一种用于图像分类和图像语义分割的神经网络模型。
该方法使用基于标签传播的技术，从标记和未标记的图像中提取特征。
这种方法适用于具有相似特征的区域和像素，而不适用于具有独特特征的区域和像素。
3. 概率生成模型基于概率生成模型的图像语义分割算法适用于特定目标的分割。
该模型利用已标记的数据和未标记的数据中的共同特征，生成一个概率模型。
该模型可以通过使用EM算法进行参数学习，从而对未标记图像进行分类。
4. 基于协同训练的方法协同训练的方法结合两个分类器，一个专门用于训练已标记的数据，而另一个分类器则使用未标记的数据。
第１３卷㊀第９期Ｖｏｌ．１３Ｎｏ．９㊀㊀智㊀能㊀计㊀算㊀机㊀与㊀应㊀用ＩｎｔｅｌｌｉｇｅｎｔＣｏｍｐｕｔｅｒａｎｄＡｐｐｌｉｃａｔｉｏｎｓ㊀㊀２０２３年９月㊀Ｓｅｐ．２０２３㊀㊀㊀㊀㊀㊀文章编号：２０９５－２１６３（２０２３）０９－０１３４－０７中图分类号：ＴＰ３９１．４１文献标志码：Ａ结合Ｎｙｓｔｒöｍ方法的三维网格模型分割方法朱天晓（上海工程技术大学电子电气工程学院，上海２０１６２０）摘㊀要：针对谱聚类三维网格模型分割方法耗时长㊁占用内存大的问题，本文提出了一种结合Ｎｙｓｔｒöｍ方法的三维网格模型分割方法㊂首先，对模型面心进行采样，计算采样点和所有面心的亲和力数值，使用Ｎｙｓｔｒöｍ方法估计亲和力矩阵的主特征向量，避免了计算亲和力矩阵的巨大开销；其次，使用Ｋ－Ｍｅａｎｓ算法对主特征向量聚类，实现对模型的分割；最后，使用自适应邻域滤波算法对分割结果进行优化，去除估计误差㊂在细分后的普林斯顿数据集上进行实验，并同５种分割方法进行定量比较，结果表明本文方法可以有效降低谱聚类方法的时间㊁空间开销，并且兰德分数比其余方法平均高０．２１，可以得到更高精度的分割结果㊂关键词：网格模型分割；Ｎｙｓｔｒöｍ方法；谱聚类；自适应邻域滤波３ＤｍｅｓｈｓｅｇｍｅｎｔａｔｉｏｎｍｅｔｈｏｄｃｏｍｂｉｎｅｄｗｉｔｈＮｙｓｔｒöｍｍｅｔｈｏｄＺＨＵＴｉａｎｘｉａｏ（ＳｃｈｏｏｌｏｆＥｌｅｃｔｒｏｎｉｃａｎｄＥｌｅｃｔｒｉｃａｌＥｎｇｉｎｅｅｒｉｎｇ，ＳｈａｎｇｈａｉＵｎｉｖｅｒｓｉｔｙｏｆＥｎｇｉｎｅｅｒｉｎｇＳｃｉｅｎｃｅ，Ｓｈａｎｇｈａｉ２０１６２０，Ｃｈｉｎａ）ʌＡｂｓｔｒａｃｔɔＡｉｍｉｎｇａｔｔｈｅｍａｓｓｉｖｅｔｉｍｅａｎｄｓｐａｃｅｏｖｅｒｈｅａｄｏｆｔｈｅｓｐｅｃｔｒａｌｃｌｕｓｔｅｒｉｎｇｍｅｓｈｓｅｇｍｅｎｔａｔｉｏｎｍｅｔｈｏｄ，ａｍｅｓｈｓｅｇｍｅｎｔａｔｉｏｎｍｅｔｈｏｄｃｏｍｂｉｎｅｄｗｉｔｈｔｈｅＮｙｓｔｒöｍｍｅｔｈｏｄｉｓｐｒｏｐｏｓｅｄ．Ｆｉｒｓｔｌｙ，ｓａｍｐｌｅｔｈｅｍｏｄｅｌｆａｃｅｃｅｎｔｅｒｓ，ｔｈｅｎｃａｌｃｕｌａｔｅｔｈｅａｆｆｉｎｉｔｙｖａｌｕｅｓｂｅｔｗｅｅｎｔｈｅｓａｍｐｌｅｄｐｏｉｎｔｓａｎｄａｌｌｆａｃｅｃｅｎｔｅｒｓ．ＵｓｉｎｇｔｈｅＮｙｓｔｒöｍｍｅｔｈｏｄｔｏｅｓｔｉｍａｔｅｔｈｅｐｒｉｎｃｉｐａｌｅｉｇｅｎｖｅｃｔｏｒｓｏｆｔｈｅａｆｆｉｎｉｔｙｍａｔｒｉｘａｖｏｉｄｓｔｈｅｍａｓｓｉｖｅｏｖｅｒｈｅａｄｏｆｃｏｍｐｕｔｉｎｇｔｈｅａｆｆｉｎｉｔｙｍａｔｒｉｘ．Ｓｅｃｏｎｄｌｙ，ｕｓｅｔｈｅＫ－Ｍｅａｎｓａｌｇｏｒｉｔｈｍｔｏｃｌｕｓｔｅｒｔｈｅｐｒｉｎｃｉｐａｌｅｉｇｅｎｖｅｃｔｏｒｓ，ｉｍｐｌｅｍｅｎｔｉｎｇｔｈｅｓｅｇｍｅｎｔａｔｉｏｎｏｆｔｈｅｍｏｄｅｌ．Ｆｉｎａｌｌｙ，ｔｈｅｓｅｇｍｅｎｔａｔｉｏｎｒｅｓｕｌｔｓａｒｅｏｐｔｉｍｉｚｅｄｕｓｉｎｇｔｈｅａｄａｐｔｉｖｅｎｅｉｇｈｂｏｒｈｏｏｄｆｉｌｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｔｏｒｅｍｏｖｅｔｈｅｅｓｔｉｍａｔｉｏｎｅｒｒｏｒｓ．ＥｘｐｅｒｉｍｅｎｔｓｏｎｔｈｅｓｕｂｄｉｖｉｄｅｄＰｒｉｎｃｅｔｏｎｄａｔａｓｅｔａｒｅｃｏｎｄｕｃｔｅｄ，ａｎｄｆｉｖｅｇｅｎｅｒａｌｓｅｇｍｅｎｔａｔｉｏｎｍｅｔｈｏｄｓａｒｅｃｏｍｐａｒｅｄ．Ｔｈｅｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄｃａｎｅｆｆｅｃｔｉｖｅｌｙｒｅｄｕｃｅｔｈｅｔｉｍｅａｎｄｓｐａｃｅｏｖｅｒｈｅａｄｏｆｔｈｅｓｐｅｃｔｒａｌｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄ．ＴｈｅＲａｎｄｓｃｏｒｅｉｓ０．２１ｈｉｇｈｅｒｔｈａｎｔｈｅｏｔｈｅｒｍｅｔｈｏｄｓｏｎａｖｅｒａｇｅ，ｗｈｉｃｈｓｈｏｗｓｔｈａｔｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄｃａｎｇｅｔｍｏｒｅｍｅａｎｉｎｇｆｕｌｓｅｇｍｅｎｔａｔｉｏｎｒｅｓｕｌｔｓ．ʌＫｅｙｗｏｒｄｓɔｍｅｓｈｍｏｄｅｌｓｅｇｍｅｎｔａｔｉｏｎ；ｎｙｓｔｒöｍｍｅｔｈｏｄ；ｓｐｅｃｔｒａｌｃｌｕｓｔｅｒｉｎｇ；ａｄａｐｔｉｖｅｎｅｉｇｈｂｏｒｈｏｏｄｆｉｌｔｅｒｉｎｇ作者简介：朱天晓（１９９８－），男，硕士研究生，主要研究方向：计算机图形学㊂收稿日期：２０２２－０９－２７０㊀引㊀言随着计算机视觉㊁三维扫描等技术的发展，三维网格模型被广泛应用于虚拟现实㊁影视动画等领域㊂三维网格模型分割是计算机图形学的重要研究点，也是互联网上模型检索㊁模型生成等技术的基础㊂三维模型精度越来越高，数据量不断增长，大大增加了分割难度㊂三维网格模型分割（简称网格分割）是根据一定分割规则，将连通的网格模型分解为一组数目有限的面片集的过程㊂网格分割按照不同的标准有不同的分类㊂按照分割结果的不同，Ｒｏｄｒｉｇｕｅｓ等［１］将网格分割方法分为面片分割和部件分割，前者将网格分割成若干几何属性一致的面片集，后者将网格分割为符合人类视觉划分效果的若干部件㊂按照分割方式的不同，龚思洁等［２］将现今主流的分割方法分为３类：第一类是根据模型几何特征将模型表面具有相关性的面片合并为一类，如聚类分析法；第二类是基于最小值原则，在模型表面构建分割线，将模型拆分为多个部分；第三类是深度学习方法，通过构建深度学习网络，进行有监督学习㊂深度学习方法通常对机器性能有很高的要求，此外获取优质数据集也是一个难题，因此很多研究集中在前两种方法上，计算量相对较小㊂龚思洁等［２］提出能量和区分度两种模型特征用于寻找分割点，并使用腐蚀算法㊁最小能量原则构造分割线，得到了精度较高的分割结果，但算法耗时较长；赵云成等［３］提出了结合曲率约束的网格模型快速分割方法，根据高斯曲率和平均曲率筛选出模型的凹区域，依据最小负曲率阈值原则构造出闭合分割线，实现对网格模型的分割；这两种方法都属于基于最小值原则㊁构建分割线的分割方法㊂对于基于聚类分析的网格分割方法，梁楚萍等［４］根据聚类过程中簇划分方式的区别，将其划分为５类：区域生长算法㊁多源区域生长算法㊁层次聚类算法㊁迭代聚类算法和谱聚类算法，前４种算法都以网格属性直接作为分类依据，而谱聚类算法核心在于对网格模型生成的亲和力矩阵的划分，该算法可以得到较高准确率㊂Ｌｉｕ等［５］将谱聚类引入到网格分割问题中，使用基于测地线距离和余弦距离构造的核函数计算亲和力矩阵，可以有效利用模型的几何特征进行分割，但是构建亲和力矩阵耗时较长；Ｊｉａｏ等［６］在谱聚类算法框架下，使用网格显著指数和网格离散曲率构建亲和力矩阵并完成网格分割，没有解决构建亲和力矩阵时间㊁空间开销大的问题；万燕［７］等使用谱聚类算法将模型过分割为弱凸区域，对弱凸区域按照可见度进行排序，根据相互可见性和形状直径函数进行区域合并，最终得到分割结果，但没有解决谱聚类算法耗时长㊁内存消耗大的问题；Ｔｏｎｇ等［８］对亲和力矩阵计算费德勒（Ｆｉｅｄｌｅｒ）向量，通过分析费德勒向量，将网格分割问题转化为梯度极小化问题；Ｌｉ等［９］通过分析费德勒向量㊁计算费德勒残差，对模型进行递归分割㊂仅使用费德勒向量降低了后续的计算成本，但是构建亲和力矩阵的时间㊁空间开销没有降低㊂针对谱聚类构建亲和力矩阵耗时长㊁内存消耗大㊁难以分割面片数较多的模型的问题，本文提出了一种结合Ｎｙｓｔｒöｍ方法的三维网格模型分割方法，能够避免构建亲和力矩阵的巨大内存开销，有效降低谱聚类算法进行网格分割所需的时间，可以获得符合人类视觉划分效果的分割结果㊂１㊀相关技术背景１．１㊀Ｎｙｓｔｒöｍ方法Ｎｙｓｔｒöｍ方法是一种用于大规模数据聚类的有效方法，其最初目的是为了求解积分方程㊂Ｗｉｌｌｉａｍｓ等［１０］将其引入核方法，用于加速矩阵特征分解，而准确率并没有明显下降㊂近年来随着研究的深入，Ｎｙｓｔｒöｍ方法也被用于图片分割㊁点云分割㊂Ｎｙｓｔｒöｍ方法适用于对称矩阵，其基本思想是通过采样获得少量样本点，使用样本点与非样本点之间的相似性来估计目标矩阵或其特征向量，采样方法有随机采样㊁基于Ｋ－Ｍｅａｎｓ算法采样㊁基于最远策略采样等㊂１．２㊀谱聚类算法谱聚类是一种基于谱图理论的聚类算法，能在任意簇形的样本空间上达到良好的聚类效果㊂该算法核心在于构建亲和力矩阵，其形式类似于图邻接矩阵㊂Ｎｇ等［１１］提出了一种二维数据谱聚类算法，使用径向基函数核（ＲａｄｉａｌＢａｓｉｓＦｕｎｃｔｉｏｎｋｅｒｎｅｌ，ＲＢＦｋｅｒｎｅｌ）计算二维数据中每两点的欧氏距离，用于构建亲和力矩阵，并对亲和力矩阵的特征向量进行Ｋ－Ｍｅａｎｓ聚类，实现对原始数据的聚类；Ｌｉｕ等［５］在其工作基础上提出了一种谱聚类三维网格模型分割算法，将测地线距离和余弦距离引入ＲＢＦ核函数来构造亲和力矩阵，该算法在网格分割方面得到了较高的准确率㊂２㊀本文算法流程传统的谱聚类算法使用核函数构建亲和力矩阵，时间㊁空间复杂度一般为Ｏ（ｎ２）㊂对于面片数较多的模型，往往难以使用谱聚类算法对模型进行分割㊂本文将Ｎｙｓｔｒöｍ方法与谱聚类算法结合，提出了一种有效降低构建亲和力矩阵时间㊁空间开销的网格模型分割方法㊂首先，使用Ｋ－Ｍｅａｎｓ＋＋算法对模型面心进行聚类，将距离聚类中心最近的面心作为采样点；其次，使用基于测地线距离和余弦距离的核函数计算采样点和所有面心的亲和力数值，并使用Ｎｙｓｔｒöｍ方法估计亲和力矩阵的主特征向量；将主特征向量拼接为矩阵，对矩阵每行元素使用Ｋ－Ｍｅａｎｓ算法聚类，实现对模型的分割；最后，使用自适应邻域滤波算法对分割结果进行处理，得到优化后的模型分割结果㊂本文方法流程如图１所示㊂结束输出模型自适应邻域滤波算法优化分割结果K-M e a n s++算法特征向量聚类N y s t r?m方法模型采样输入模型开始K-M e a n s算法估计亲和力矩阵特征向量图１㊀本文方法流程图Ｆｉｇ．１㊀Ｆｌｏｗｃｈａｒｔｏｆｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄ５３１第９期朱天晓：结合Ｎｙｓｔｒöｍ方法的三维网格模型分割方法２．１㊀特征向量估计使用谱聚类算法分割模型时，若模型的面片数为Ｎ，则需要计算大小为ＮˑＮ的亲和力矩阵，计算量较大㊁耗时较长㊂因此，可以使用Ｎｙｓｔｒöｍ方法对矩阵或其特征向量进行估计近似，提升谱聚类算法运行速度㊂Ｏｇｌｉｃ等［１２］证明了Ｋ－Ｍｅａｎｓ＋＋算法作为Ｎｙｓｔｒöｍ方法中的采样方法具有可行性，并且误差较小㊂Ｋ－Ｍｅａｎｓ＋＋算法是Ｋ－Ｍｅａｎｓ算法的改进，其初始聚类中心点的选择是基于最远策略的，即选择相互间距离尽可能远的初始聚类中心点㊂本文将聚类数目设置为采样点数，对模型面片的面心进行Ｋ－Ｍｅａｎｓ＋＋聚类，并选择距离聚类中心点最近的面心作为采样点㊂设模型的面片数为Ｎ，从中使用Ｋ－Ｍｅａｎｓ＋＋采样获得ｍ个面心作为样本点（ｍ≪Ｎ），则非样本点数目为ｎ＝Ｎ－ｍ㊂亲和力矩阵Ｗ可以表示为式（１）：Ｗ＝ＡＢＢＴＣéëêêùûúú（１）㊀㊀其中，Ａɪℝｍˑｍ，Ｂɪℝｎˑｍ，Ｃɪℝｎˑｎ，矩阵Ａ表示采样的ｍ个样本点之间的亲和力矩阵；矩阵Ｂ表示采样的ｍ个样本点和剩余ｎ个非样本点之间的亲和力矩阵；因为ｍ≪Ｎ，所以矩阵Ｃ的大小几乎和矩阵Ｗ相同㊂本文使用Ｎｙｓｔｒöｍ方法对矩阵Ｗ的主特征向量进行估计，方法流程如图２所示㊂结束计算出亲和力矩阵特征向量V计算出亲和力矩阵特征向量V 对矩阵Z TZ 进行特征分解对矩阵S 进行特征分解计算矩阵S计算矩阵Z对估计特征向量U S ^A 是否正定是否开始获得模型采样点计算亲和力数值AB 标准化ABA BB T B T A -1B T 图２㊀Ｎｙｓｔｒöｍ方法流程图Ｆｉｇ．２㊀ＦｌｏｗｃｈａｒｔｏｆｔｈｅＮｙｓｔｒöｍｍｅｔｈｏｄ㊀㊀首先，将矩阵Α特征分解，即Α＝ＵΛＵＴ；Λ为对角矩阵，其中非零元素为矩阵Ａ的特征值㊂亲和力矩阵Ｗ的近似特征向量为式（２）：Ｕ＾＝ＵＢＴＵΛ－１éëêêùûúú（２）㊀㊀由式（１）㊁式（２）有亲和力矩阵Ｗ可近似为式（３）：㊀㊀Ｗ＾＝Ｕ＾ΛＵ＾Ｔ＝ＵΛＵＴＢＢＴＢＴＡ－１Ｂéëêêùûúú＝ＡＢＢＴＢＴＡ－１Ｂéëêêùûúú（３）由式（３）可知，矩阵Ｃ的近似值为ＢＴＡ－１Ｂ㊂其次，对Ａ㊁Ｂ进行标准化㊂因为在谱聚类算法中，使用标准化的亲和力矩阵㊂对估计矩阵Ｗ＾求行和，式（４）：㊀㊀ｄ＾＝Ｗ＾１＝Ａ１ｍ＋Ｂ１ｎＢＴ１ｎ＋ＢＴＡ－１Ｂ１ｍéëêêùûúú＝ａｒ＋ｂｒｂｃ＋ＢＴＡ－１ｂｒéëêêùûúú（４）其中，ａｒ㊁ｂｒɪℝｍˑ１，分别表示矩阵Ａ㊁Ｂ的行和；ｂｃɪℝｎˑ１表示矩阵Ｂ的列和；１表示元素均为１的列向量㊂ｄ＾ɪℝＮˑ１使用式（４）对矩阵Ａ和Ｂ进行归一化，式（５）和式（６）：Ａｉｊ＝Ａｉｊｄ＾ｉｄ＾ｊ，ｉ，ｊ＝１， ，ｎ（５）Ｂｉｊ＝Ｂｉｊｄ＾ｉｄ＾ｊ，ｉ＝１， ，ｎ，ｊ＝１， ，ｍ（６）㊀㊀最后，求解矩阵Ｗ＾的主特征向量㊂若矩阵Ａ正定，令Ａ１／２表示Ａ的正定平方根㊂定义Ｓ＝Ａ＋Ａ－１／２ＢＢＴＡ－１／２，并将其特征分解为Ｓ＝ＵＳΛＳＵＴＳ㊂可一步估算出矩阵Ｗ＾的正交主特征向量式（７）：Ｖ＝ＡＢＴéëêêùûúúＡ－１／２ＵＳΛ－１／２Ｓ（７）㊀㊀若矩阵Ａ非正定，矩阵Ｗ＾的估计特征向量为Ｕ＾ＴＳ＝ＵＴΛ－１ＵＴＢ[]㊂定义Ｚ＝Ｕ＾ＳΛ－１／２，有Ｗ＾＝ＺＺＴ，对ＺＴＺ特征分解，有ＺＴＺ＝ＦΣＦＴ㊂最后估算出矩阵Ｗ＾的正交主特征向量，式（８）：Ｖ＝ＺＦΣ－１／２（８）㊀㊀Ｎｙｓｔｒöｍ方法中数据量最大的是式（３）的亲和６３１智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１３卷㊀力矩阵Ｗ＾ɪℝＮˑＮ，但是不必真正计算该矩阵，谱聚类算法需要的是亲和力矩阵的主特征向量㊂因为Ｗ＾是由矩阵Ａ㊁Ｂ计算拼接出的，而在式（４）进行标准化时，可以直接使用矩阵Ａ㊁Ｂ标准化，而无需计算Ｗ＾㊂可见，最大的矩阵为ＶɪℝＮˑｍ，相比与传统谱聚类算法需要计算ＷɪℝＮˑＮ，本文使用Ｎｙｓｔｒöｍ方法对亲和力矩阵主特征向量进行估计近似，大大降低了时间㊁空间开销㊂２．２㊀网格模型分割本文计算面片ｉ到相邻面片ｊ的测地线距离，式（９）：ｄｉｓｔＧ（ｉ，ｊ）＝ｌｉ＋ｌｊ（９）㊀㊀其中，ｌｉ㊁ｌｊ分别为面片ｉ㊁ｊ的交线中点ｐｌ到对应面片质心ｐｉ㊁ｐｊ的欧式距离㊂本文定义面片ｉ到相邻面片ｊ的余弦距离为式（１０）：ｄｉｓｔｃ（ｉ，ｊ）＝１－ｃｏｓ（ｎｉ，ｎｊ）（１０）㊀㊀其中，ｎｉ为面片ｉ的法向量，ｎｊ为面片ｊ的法向量㊂使用式（９）㊁式（１０）构造的加权距离公式为式（１１）：ｄｉｓｔ（ｉ，ｊ）＝ｎ㊃δ㊃ｄｉｓｔＧ（ｉ，ｊ）ðｉ，ｊɪ［１，ｎ］ｄｉｓｔＧ＋ｎ㊃（１－δ）㊃η㊃ｄｉｓｔＣ（ｉ，ｊ）ðｉ，ｊɪ［１，ｎ］ｄｉｓｔＣ（１１）其中，ｎ为面片数；δ为衡量测地线距离与余弦距离重要性的参数；η为调整余弦距离的参数㊂本文设置δ＝０．０３，η＝０．１５㊂使用式（１１）构造的亲和力数值计算式（１２）：Ｗ（ｉ，ｊ）＝ｅ－ｄｉｓｔ（ｉ，ｊ）２σ２（１２）㊀㊀其中，σ＝ðｉ，ｊɪ［１，ｎ］ｄｉｓｔ（ｉ，ｊ）ｎ２，ｉʂｊ，Ｗ（ｉ，ｉ）＝０㊂本文提出的结合Ｎｙｓｔｒöｍ方法的谱聚类算法流程如下：（１）对面片集Ｍ＝｛ｍ１， ，ｍｎ｝，使用Ｋ－Ｍｅａｎｓ＋＋算法确定ｍ个采样点；（２）使用式（１２）计算ｍ个采样点与自身以及与剩余ｎ个非样本点之间的亲和力矩阵；（３）使用Ｎｙｓｔｒöｍ方法估计亲和力矩阵Ｗ＾的ｍ个主特征向量，并按列排放，组成矩阵Ｖ＝ｅ１，ｅ２， ，ｅｍ[]；（４）对矩阵Ｖ每行元素进行单位化，得到矩阵Ｖᶄ；（５）将矩阵Ｖᶄ中每行元素视为映射到ｍ维空间的特征点，并对其进行Ｋ－Ｍｅａｎｓ聚类，聚类数目为ｍ㊂最后，如果矩阵Ｖᶄ的ｉ行分配给簇ｊ时，将原始面片ｍｉ分配给簇ｊ㊂２．３㊀分割误差优化Ｎｙｓｔｒöｍ方法获得的亲和力矩阵特征向量是近似计算得出的，因此在分割时会出现一定的误差，分割模型误差俯视图如图３所示㊂（ａ）几何Ａ模型㊀㊀㊀㊀（ｂ）几何Ｂ模型图３㊀分割模型误差俯视图Ｆｉｇ．３㊀Ｔｏｐｖｉｅｗｏｆｓｅｇｍｅｎｔａｔｉｏｎｅｒｒｏｒ㊀㊀可见，分割误差类似于二维图像中的椒盐噪声，椒盐噪声的消除方式一般是使用中值滤波方法㊂二维图像中使用像素邻域滤波，在三维网格中可以使用面片邻域进行滤波㊂面片ｉ的一阶邻域㊁二阶邻域如图４所示㊂（ａ）一阶邻域㊀㊀㊀㊀㊀（ｂ）二阶邻域图４㊀面片ｉ邻域示意图Ｆｉｇ．４㊀Ｄｉａｇｒａｍｏｆｔｈｅｎｅｉｇｈｂｏｒｈｏｏｄｏｆｓｕｒｆａｃｅｉ㊀㊀参考目前去噪效果较好的自适应中值滤波算法，本文使用面片邻域作为滤波算子对分割模型进行优化，提出了一种网格模型自适应邻域滤波算法㊂该算法遍历模型面片进行优化，其核心是对误差的判断㊂若面片ｉ的一阶邻域中均为同一种颜色Ｃ且与面片ｉ颜色不同，则将面片ｉ视为误差，并将其颜色设置为颜色Ｃ㊂若面片ｉ一阶邻域中存在两种（或以上）颜色Ｃａ㊁Ｃｂ，并且数量最多的颜色Ｃｍ占比超过８０％，同时面片ｉ颜色不为Ｃｍ，则将面片ｉ视为误差，将其颜７３１第９期朱天晓：结合Ｎｙｓｔｒöｍ方法的三维网格模型分割方法色设置为颜色Ｃｍ㊂若一阶顶点邻域中数量最多的颜色Ｃｍ占比不超过８０％，同时面片ｉ颜色不为Ｃｍ，则将邻域扩大为二阶邻域进行判断，将面片ｉ颜色设置为二阶邻域中数量最多的颜色Ｃᶄｍ㊂使用自适应邻域滤波算法对分割结果进行优化，得到优化后的模型俯视图如图５所示，基本上消除了因矩阵估计引起的分割误差㊂（ａ）几何Ａ模型㊀㊀㊀㊀（ｂ）几何Ｂ模型图５㊀分割模型优化结果俯视图Ｆｉｇ．５㊀Ｔｏｐｖｉｅｗｏｆｏｐｔｉｍｉｚａｔｉｏｎｒｅｓｕｌｔｓｏｆｓｅｇｍｅｎｔａｔｉｏｎ３㊀实㊀验本文使用Ｐｙｔｈｏｎ编程实现方法，在ＣＰＵ为ＩｎｔｅｌＣｏｒｅｉ５－６３００ＨＱ（２．３０ＧＨｚ）㊁内存为１６ＧＢ㊁系统为Ｗｉｎｄｏｗｓ１０的ＰＣ上进行实验㊂由于普林斯顿数据集中模型面片数较少，本文从中选择了８类，每类２个，共计１６个网格模型进行Ｌｏｏｐ细分，并进行人工二分割，作为实验数据集㊂使用Ｎｙｓｔｒöｍ方法时，需要确定对模型的采样数ｍ㊂图６为几何模型Ａ的分割误差俯视图（未进行误差优化），其中ｍ为采样数，可见采样数从２增加到１０，分割误差基本相同㊂m =2m =4m =6m =8m =10图６㊀几何Ａ模型不同采样数的分割误差俯视图Ｆｉｇ．６㊀ＴｏｐｖｉｅｗｏｆｓｅｇｍｅｎｔａｔｉｏｎｅｒｒｏｒｏｆｇｅｏｍｅｔｒｙＡｗｉｔｈｄｉｆｆｅｒｅｎｔｓａｍｐｌｉｎｇｎｕｍｂｅｒｓ㊀㊀采样数取不同数值时，对选取的１６个模型进行分割（未进行误差优化），并对结果进行定量比较，选组评估指标为兰德分数（ＲａｎｄＳｃｏｒｅ，ＲＳ）和运行时间，兰德分数用来衡量分割方法与基准的相似性，数值越大代表分割效果越好，实验结果如图７和图８所示㊂可见采样数从２增加到１０，兰德分数基本持平，分割时间明显上升㊂因此，本文选取采样数目为ｍ＝２㊂1.00.80.60.40.20m =2m =4m =6m =8m =10采样点数平均数值R S图７㊀测试模型不同采样数的兰德分数平均值Ｆｉｇ．７㊀ＡｖｅｒａｇｅＲａｎｄｓｃｏｒｅｓｏｆｔｈｅｔｅｓｔｉｎｇｍｏｄｅｌｓｗｉｔｈｄｉｆｆｅｒｅｎｔｓａｍｐｌｉｎｇｎｕｍｂｅｒｓ120100806040200m =2m =4m =6m =8m =10采样点数平均数值T i m e图８㊀测试模型不同采样数的运行时间平均值（／ｓ）Ｆｉｇ．８㊀Ａｖｅｒａｇｅｒｕｎｎｉｎｇｔｉｍｅｏｆｔｈｅｔｅｓｔｉｎｇｍｏｄｅｌｓｗｉｔｈｄｉｆｆｅｒｅｎｔｓａｍｐｌｉｎｇｎｕｍｂｅｒｓ（ｕｎｉｔ：ｓｅｃｏｎｄ）㊀㊀本文方法对模型的二分割结果（每类模型中上方的命名为Ａ，下方为Ｂ）如图９所示，可以看出本文方法得到的分割结果符合人眼的视觉标准㊂杯子椅子八爪小熊人物几何零件花瓶图９㊀本文方法对普林斯顿数据集部分细分模型分割结果Ｆｉｇ．９㊀ＴｈｅｓｅｇｍｅｎｔａｔｉｏｎｒｅｓｕｌｔｓｂｙｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄｏｆｐａｒｔｉａｌＰｒｉｎｃｅｔｏｎｄａｔａｓｅｔｍｏｄｅｌｓａｆｔｅｒｓｕｂｄｉｖｉｓｉｏｎ㊀㊀对比指标除兰德分数外，还有准确率分数（ＡｃｃｕｒａｃｙＳｃｏｒｅ，ＡＳ）和汉明损失（ＨａｍｍｉｎｇＬｏｓｓ，ＨＬ）㊂准确率分数与兰德分数类似，用来衡量分割方法与基准的相似性，其数值越大越好；汉明损失用来衡量分割结果中错误的比例，数值越小代表分割效果越好㊂为进一步验证本文方法的有效性，采用量化评估标准将本文方法与ＢＩＲＣＨ（ＢａｌａｎｃｅｄＩｔｅｒａｔｉｖｅ８３１智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１３卷㊀ＲｅｄｕｃｉｎｇａｎｄＣｌｕｓｔｅｒｉｎｇｕｓｉｎｇＨｉｅｒａｒｃｈｉｅｓ，ＢＩＲＣＨ）算法，Ｋ－Ｍｅａｎｓ算法，ＭｉｎｉＢａｔｃｈＫ－Ｍｅａｎｓ算法，Ｌｉｕ等［５］提出的算法和Ｋａｔｚ等［１３］提出的算法进行二分割比较㊂实验结果如图１０㊁图１１所示㊂可见本文方法具有较好的分割效果，兰德分数㊁准确率分数高于其他算法，汉明损失低于其他算法㊂在本文实验环境下，Ｌｉｕ等［５］提出的算法和Ｋａｔｚ等［１３］提出的算法仅可正常分割１个模型，分割其余模型时超出１６ＧＢ内存限制，无法运行，因此无法显示这两种方法的指标平均值㊂R SA S1.00.80.60.40.2本文方法B I R C H K -M e a n M i n i L I UK a t z B a c t c h K -M e a n s平均数值图１０㊀测试模型兰德分数㊁准确率分数平均值Ｆｉｇ．１０㊀ＡｖｅｒａｇｅＲａｎｄｓｃｏｒｅｓ，ａｃｃｕｒａｃｙｓｃｏｒｅｓｏｆｔｈｅｔｅｓｔｉｎｇｍｏｄｅｌｓH L0.200.150.100.05本文方法B I R C H K -M e a n M i n i L I UK a t z B a c t c h K -M e a n s平均数值图１１㊀测试模型汉明损失平均值Ｆｉｇ．１１㊀ＡｖｅｒａｇｅＨａｍｍｉｎｇｌｏｓｓｏｆｔｈｅｔｅｓｔｉｎｇｍｏｄｅｌｓ㊀㊀６种算法在本文数据集上的兰德分数和运行时间见表１（本文方法已进行误差优化）㊂在面片数最小的模型零件Ａ（面片数３ｗ）上，Ｌｉｕ等［５］提出的算法获得了最高的兰德分数０．９９２，运行时间为３９７．３ｓ；Ｋａｔｚ等［１３］提出的方法获得的次高的兰德分数０．９８８，运行时间为１２５６．１ｓ，这两种方法在其余模型上均超出１６ＧＢ内存限制，无法运行（数据在表１中显示为横线）㊂本文方法在零件Ａ模型上获得的兰德分数为０．９８６，高于其余３种方法，运行时间为１９．１ｓ；在其余模型上，兰德分数均为最高，运行时间在几十秒左右㊂表１㊀测试模型兰德分数㊁运行时间评价表Ｔａｂ．１㊀Ｒａｎｄｓｃｏｒｅ，ｒｕｎｎｉｎｇｔｉｍｅｅｖａｌｕａｔｉｏｎｔａｂｌｅｏｆｔｈｅｔｅｓｔｉｎｇｍｏｄｅｌｓ模型信息模型名称面片数目本文方法ＲａｎｄＳｃｏｒｅＴｉｍｅ／ｓＢＩＲＣＨＲａｎｄＳｃｏｒｅＴｉｍｅ／ｓＫ－ＭｅａｎｓＲａｎｄＳｃｏｒｅＴｉｍｅ／ｓＭｉｎｉＢａｔｃｈＫ－ＭｅａｎｓＲａｎｄＳｃｏｒｅＴｉｍｅ／ｓＬｉｕＲａｎｄＳｃｏｒｅＴｉｍｅ／ｓＫａｔｚＲａｎｄＳｃｏｒｅＴｉｍｅ／ｓ杯子Ａ１２ｗ０．９９９７１．５０．９５５１６．１０．９７１１４．４０．９６５１４．０－－－－杯子Ｂ１２ｗ０．９９８７１．４０．９６６１６．５０．９６８１５．４０．９７１１４．５－－－－椅子Ａ１１ｗ０．９８７６４．５０．７５４１５．４０．９０２１２．８０．５６６１３．９－－－－椅子Ｂ１１ｗ０．９８２６２．８０．９１９１４．５０．９６２１３．９０．９７９１２．３－－－－八爪Ａ６ｗ０．９２８３７．００．６８７８．６０．８７０７．７０．８７３７．３－－－－八爪Ｂ７ｗ０．９３８４４．００．５０２１０．４０．５０２９．００．５０２１０．９－－－－小熊Ａ１１ｗ０．９９３６４．２０．５９０１３．６０．６４５１２．７０．６４２１２．２－－－－小熊Ｂ１０ｗ０．９９６５８．１０．５１０１２．５０．５５０１０．６０．５５６１１．１－－－－人物Ａ７ｗ０．９６９４３．８０．８８６１３．７０．９０５１１．５０．９１２１１．０－－－－人物Ｂ１９ｗ０．９９３１１６．２０．６５０３１．９０．６７４２７．７０．６６６２７．７－－－－几何Ａ１２ｗ０．９９５７４．８０．５１３２１．２０．５４４１７．８０．５４３１８．４－－－－几何Ｂ１２ｗ０．９９０７１．００．７５０２０．３０．５７６１８．４０．５７４１９．４－－－－零件Ａ３ｗ０．９８６１９．１０．８６７４．８０．９８５４．３０．９８４４．２０．９９２３９７．３０．９８８１２５６．１零件Ｂ８ｗ０．９８６５０．００．８７９１４．５０．８５２１２．４０．８５２１２．７－－－－花瓶Ａ１２ｗ０．９９７７０．２０．７１０１９．９０．７０５１７．７０．７０５１７．４－－－－花瓶Ｂ１１ｗ０．９９３６５．９０．９２８１４．１０．９４６１２．８０．９５６１１．６－－－－平均值１０ｗ０．９８３６１．５０．７５４１５．５０．７８５１３．７０．７６６１３．７－－－－９３１第９期朱天晓：结合Ｎｙｓｔｒöｍ方法的三维网格模型分割方法㊀㊀传统谱聚类算法因其巨大的时间㊁空间开销无法分割面片数较多的模型；Ｋ－Ｍｅａｎｓ㊁ＢＩＲＣＨ等算法运行时间短㊁消耗内存空间小，但无法有效利用模型的几何特征，分割效果差㊂本文方法相比于传统谱聚类算法，有效减少了分割模型所需时间㊁空间开销，同时也获得了较高的兰德分数，分割效果比Ｋ－Ｍｅａｎｓ㊁ＢＩＲＣＨ等算法好㊂４㊀结束语本文提出了一种结合Ｎｙｓｔｒöｍ方法的三维网格模型分割方法㊂首先，使用Ｋ－Ｍｅａｎｓ＋＋算法对模型面心进行聚类，将距离聚类中心最近的面心作为采样点；其次，计算采样点和所有面心的亲和力数值，并使用Ｎｙｓｔｒöｍ方法估计亲和力矩阵的主特征向量；将特征向量拼接为矩阵，并对矩阵每行元素使用Ｋ－Ｍｅａｎｓ方法聚类，实现对模型的分割；最后，使用自适应邻域滤波算法对分割结果进行优化，去除估计误差㊂实验结果表明本文方法有效避免了计算亲和力矩阵的时间㊁空间开销，可以获得符合人类视觉划分效果的分割结果㊂本文使用Ｎｙｓｔｒöｍ方法估计亲和力矩阵，存在一定分割误差，在二分割上取得了较好的效果，而对于多分割则会存在较大误差㊂降低Ｎｙｓｔｒöｍ方法的估计误差，更好地逼近真实的亲和力矩阵是接下来的研究重点㊂参考文献［１］ＲＯＤＲＩＧＵＥＳＲＳ，ＭＯＲＧＡＤＯＪＦ，ＧＯＭＥＳＡＪ．Ｐａｒｔ‐ｂａｓｅｄｍｅｓｈｓｅｇｍｅｎｔａｔｉｏｎ：ａｓｕｒｖｅｙ［Ｃ］／／ＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓＦｏｒｕｍ，２０１８：２３５－２７４．［２］龚思洁，贺炯臻，陈小雕．基于能量优化的三维网格模型分割方法［Ｊ］．计算机辅助设计与图形学学报，２０２１，３３（１）：１１－１８．［３］赵云成，王琳，盛步云，等．综合曲率约束的在线网格模型分割方法研究［Ｊ］．计算机工程与应用，２０２０，５６（１６）：１７６－１８２．［４］梁楚萍，印杰，伍静，等．三维网格分割中聚类分析技术综述［Ｊ］．计算机辅助设计与图形学学报，２０２０，３２（４）：６８０－６９２．［５］ＬＩＵＲ，ＺＨＡＮＧＨ．Ｓｅｇｍｅｎｔａｔｉｏｎｏｆ３Ｄｍｅｓｈｅｓｔｈｒｏｕｇｈｓｐｅｃｔｒａｌｃｌｕｓｔｅｒｉｎｇ［Ｃ］／／１２ｔｈＰａｃｉｆｉｃＣｏｎｆｅｒｅｎｃｅｏｎＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００４：２９８－３０５．［６］ＪＩＡＯＸ，ＷＵＴ，ＱＩＮＸ．Ｍｅｓｈｓｅｇｍｅｎｔａｔｉｏｎｂｙｃｏｍｂｉｎｉｎｇｍｅｓｈｓａｌｉｅｎｃｙｗｉｔｈｓｐｅｃｔｒａｌｃｌｕｓｔｅｒｉｎｇ［Ｊ］．ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔａｔｉｏｎａｌａｎｄＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，２０１８，３２９：１３４－１４６．［７］万燕，刘巧雪，姚砺．三维模型分割的研究及其在人体测量中的应用［Ｊ］．智能计算机与应用，２０２２，１２（１）：１－７，１５．［８］ＴＯＮＧＷ，ＹＡＮＧＸ，ＰＡＮＭ，ｅｔａｌ．Ｓｐｅｃｔｒａｌｍｅｓｈｓｅｇｍｅｎｔａｔｉｏｎｖｉａｇｒａｄｉｅｎｔｍｉｎｉｍｉｚａｔｉｏｎ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＶｉｓｕａｌｉｚａｔｉｏｎａｎｄＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ，２０１８，２６（４）：１８０７－１８２０．［９］ＬＩＮＧＦＥＩＬ，ＴＩＥＲＵＷ．Ａｕｔｏｍａｔｉｃｓｐｅｃｔｒａｌｍｅｔｈｏｄｏｆｍｅｓｈｓｅｇｍｅｎｔａｔｉｏｎｂａｓｅｄｏｎｆｉｅｄｌｅｒｒｅｓｉｄｕａｌ［Ｊ］．ＣｈｉｎｅｓｅＪｏｕｒｎａｌｏｆＥｌｅｃｔｒｏｎｉｃｓ，２０２１，３０（３）：４２６－４３６．［１０］ＷＩＬＬＩＡＭＳＣ，ＳＥＥＧＥＲＭ．ＵｓｉｎｇｔｈｅＮｙｓｔｒöｍｍｅｔｈｏｄｔｏｓｐｅｅｄｕｐｋｅｒｎｅｌｍａｃｈｉｎｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ１４ｔｈａｎｎｕａｌｃｏｎｆｅｒｅｎｃｅｏｎｎｅｕｒａｌｉｎｆｏｒｍａｔｉｏｎｐｒｏｃｅｓｓｉｎｇｓｙｓｔｅｍｓ，２００１：６８２－６８８．［１１］ＮＧＡＹ，ＪＯＲＤＡＮＭＩ，ＷＥＩＳＳＹ．Ｏｎｓｐｅｃｔｒａｌｃｌｕｓｔｅｒｉｎｇ：Ａｎａｌｙｓｉｓａｎｄａｎａｌｇｏｒｉｔｈｍ［Ｃ］／／Ａｄｖａｎｃｅｓｉｎｎｅｕｒａｌｉｎｆｏｒｍａｔｉｏｎｐｒｏｃｅｓｓｉｎｇｓｙｓｔｅｍｓ，２００２：８４９－８５６．［１２］ＯＧＬＩＣＤ，ＧÄＲＴＮＥＲＴ．Ｎｙｓｔｒöｍｍｅｔｈｏｄｗｉｔｈｋｅｒｎｅｌｋ－ｍｅａｎｓ＋＋ｓａｍｐｌｅｓａｓｌａｎｄｍａｒｋｓ［Ｃ］／／ＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎＭａｃｈｉｎｅＬｅａｒｎｉｎｇ，２０１７：２６５２－２６６０．［１３］ＫＡＴＺＳ，ＴＡＬＡ．Ｈｉｅｒａｒｃｈｉｃａｌｍｅｓｈｄｅｃｏｍｐｏｓｉｔｉｏｎｕｓｉｎｇｆｕｚｚｙｃｌｕｓｔｅｒｉｎｇａｎｄｃｕｔｓ［Ｊ］．ＡＣＭｔｒａｎｓａｃｔｉｏｎｓｏｎｇｒａｐｈｉｃｓ（ＴＯＧ），２００３，２２（３）：９５４－９６１．（上接第１３３页）表３㊀不同社区内的股票构成Ｔａｂ．３㊀Ｓｈａｒｅｃｏｍｐｏｓｉｔｉｏｎｉｎｄｉｆｆｅｒｅｎｔｃｏｍｍｕｎｉｔｉｅｓ社区股票名称社区１中国中治㊁中国石化㊁三一重工㊁中国铝业㊁宝钢股份㊁中国核电㊁江西铜业㊁紫金矿业㊁中国电建㊁陕西煤业㊁中国石油㊁北方稀土㊁宝丰能源社区２北京银行㊁海通证券㊁新华保险㊁浦发银行㊁民生银行㊁中国人寿㊁交通银行㊁招商银行㊁中国银行㊁建设银行㊁金地发展㊁邮储银行社区３国泰君安㊁中国银河㊁中信建投㊁国金证券㊁东方证券㊁财通证券㊁方正证券㊁招商证券㊁国投资本社区４伊利股份㊁贵州茅台㊁海尔智家㊁片仔癀㊁青岛啤酒㊁绝味食品㊁今世缘㊁口子窖社区５工业富联㊁长电科技㊁生益科技㊁中科曙光㊁汇顶科技４㊀结束语本文基于时间序列的相似性以及复杂网络理论对网络中最重要的特性 社区结构进行了相应的分析，并利用上证１８０指数成分股票的时间序列数据对其网络进行了社区结构的分析，表明利用时间序列相似性对现实经验世界中的复杂网络的社区结构进行分析和解释其内在运行机制是有效可行的㊂但本文忽略了复杂系统中每个个体之间原本存在着一定的联系，仅仅利用每个个体时间序列之间的相似性表示每个个体之间的关系，没有非常准确地描述现实场景㊂未来的工作应该考虑保留复杂系统中个体之间原本的联系，再结合时间序列之间的相似性，考虑复杂系统每个个体之间不同类型的关系的结合并分析其对复杂系统的社区结构的影响，从而能够更精准地预测和控制这些复杂系统㊂０４１智㊀能㊀计㊀算㊀机㊀与㊀应㊀用㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀㊀第１３卷㊀。
