基于蚁狮优化的极限学习机的网格分割方法 
下载： 1148次
1 引言
得益于硬件传感器和重建技术的迅速发展,各式各样的数字多媒体数据不断增长[1]。针对三维数据进行分析与处理,已成为计算机图形学研究的热点。其中,网格模型的分割是计算机图形学的基础性研究课题,对于三维物体的语义理解至关重要[2]。网格模型的分割就是按照模型的几何或拓扑特征对其进行分解,将其变成一定数目且彼此连通的区域,每个区域都具有简单形状意义的子网格[3]。国内外研究人员针对网格模型的分割提出了很多算法。根据是否将模型的标签作为输入信息,可将这些算法分为基于无监督的网格分割[4-5]和基于有监督的网格分割[6-8]两大类。在基于无监督的网格分割方面,2018年,赵天宇等[4]提出了一种基于多特征融合的三维形状分割方法,将提取得到的几何特征输入到无监督的深层神经网络中,再利用高斯混合模型得到聚类中心,最后采用图割的方法得到了最终的分割结果;虽然该方法取得了较好的一致性分割结果,但操作比较繁琐;同年,张耀楠等[5]提出了一种基于蚁群优化的网格分割方法,通过蚁群优化算法对每个网格的标签进行迭代更新,再进行区域合并,最终完成网格分割;采用该方法对3例网格模型进行实验,均取得了比图割更好的分割结果,但该方法不适合用于大规模的数据集。在基于有监督的网格分割方面,人工干预少且分割精确度更高。近些年,研究人员相继提出了一些基于有监督的网格分割方法:2014年,Xie等[6]提出了一种快速的三维形状分割与标记方法,首次采用极限学习机(ELM)[9]进行分割与标记,在普林斯顿19类模型数据集[10]上的平均分割精确度可达91.93%,训练时间大幅减少;2015年,Guo等[7]提出了一种有效且鲁棒的形状表示方法,通过深度神经网络学习数据,进一步提高了分割和标注性能,但训练过程非常耗时;2017年,李红岩[8]在文献[ 6]方法的基础上,分别针对标记数据的面片信息和边界信息训练分割分类器,并通过多标签图割优化方法,获得了最终的平滑分割结果。倘若极限学习机的权重设置不当,就会在一定程度上对分割结果造成影响。粒子群优化算法(PSO)[11]、蚁群优化算法(ACO)[12]、灰狼优化算法(GWO)[13]和蚁狮优化算法(ALO)[14]等群体智能优化算法(SI)简单灵活,并且可以有效避免局部最优的特点,在求解优化问题上得到了广泛应用。鉴于此,本文提出了一种基于蚁狮优化的极限学习机的网格分割方法,该方法将群体智能的思想应用到网格分割研究中,采用蚁狮优化算法的基于种群的全局优化搜索能力,得到极限学习机最优的输入权值矩阵与隐层偏置,利用本文改进的极限学习机方法训练分割分类器,采用该分割分类器对三维模型进行测试。与前人的工作相比,本文算法的分割精确度更高。
2 本文方法概述
本文提出的基于蚁狮优化的极限学习机的网格分割方法总体步骤如
本文所提分割方法总体步骤可以分为三步:第一步,提取每类网格模型的特征描述子,并进行归一化处理,组成输入特征向量。本文提取了文献[ 4-8]中证实有效的特征描述子,包含面片曲率特征、主成分分析(PCA)特征、形状上下文特征[15]、平均测地距离特征[16]、形状直径函数特征[17]等。第二步,采用蚁狮优化算法优化的极限学习机(ALO-ELM)针对输入的特征向量进行训练,得到分割分类器,ALO-ELM网格分割方法将在第4节中详细介绍;第三步,采用训练好的分割分类器对同类别未分割的网格模型进行测试,最终得到分割标注结果。
3 基本原理
3.1 极限学习机
极限学习机(ELM)是黄广斌教授[9]提出的一种高效率的单隐层前馈神经网络机器学习算法,该算法解决了反向传播算法(BP)神经网络学习效率低与参数设定繁琐的问题,在分类分割[6]、行业预测[13]、防灾减灾[18]和光谱分析[19]等领域具有广泛应用。
任意选择M个样本构成样本集,表达式为{(xj,tj),j=1,2,…,M},其中xj=
式中:wi=
假设ELM的实际输出结果与期望输出结果tj一致,可以表示为
将(2)式转换成
其中:H=
ELM算法采用最小二乘法计算得到最小的输出权重
式中:H-为H的广义逆
3.2 蚁狮优化算法
蚁狮优化算法是2015年Mirjalili等[14]提出的一种新的群体智能优化算法,模拟自然界中幼虫蚁狮捕食蚂蚁的行为活动。蚂蚁的行为活动会受到蚁狮陷阱的影响,围绕蚁狮随机游走从而探索搜索空间,以此来确保种群的多样性与算法的寻优性能。蚂蚁觅食时随机游走的公式为
其中:cs表示计算累积和;n为最大迭代次数;r(t)表示随机函数。
受蚁狮陷阱影响的蚂蚁进行随机游走时,会在选定的蚁狮周围的超球内运动,用数学模型表示为
式中:ct为第t次迭代中所有变量的最小值;
随着迭代次数增加,c与d的值会自适应减小,这样就能有效地提高收敛速度,寻求得到最优解,数学公式为
式中:I为比率。
在ALO算法的迭代过程中,每一次迭代得到的最佳蚁狮被视为精英蚁狮。精英蚁狮会影响所有蚂蚁的行为活动。为了降低算法陷入局部极值的可能性,ALO算法通过轮盘赌策略和精英蚁狮的影响共同确定蚂蚁的位置,表达式为
式中:
在第t次迭代时,如果蚂蚁在精英蚁狮与轮盘赌策略的双重作用下,得到了比蚁狮更好的位置,则蚂蚁将被蚁狮吃掉,此时,蚁狮更新到被吃蚂蚁的位置,表达式为
4 ALO-ELM网格分割方法
由于极限学习机随机生成输入权值矩阵和隐层偏置,因此训练所得到的分割分类器模型不是最优的,唯有增设更多的隐层节点,才能保证训练的精确度;然而增加隐层节点不仅加剧了时间的消耗,而且不能保证训练精确度有效提升。要得到分割精确度更高的ELM模型,蚁狮优化算法需要对(1)式中的输入权值矩阵wi=
式中:w为输入权值矩阵;wi,j为矩阵内的元素;b为隐层偏置。
基于蚁狮优化的极限学习机网格模型分割方法的实验流程详细描述如下:
1) 提取普林斯顿数据集中的每类网格模型的特征描述子,进行归一化处理,然后将它们组成输入特征向量{(xj,tj),j=1,2,…,M};
2) 将每类网格模型数据按比例划分为训练数据集与测试数据集,其中训练数据集用来训练分割分类器,测试数据集则用来对训练好的分割分类器进行检验;
3) 设置ALO-ELM模型的参数(隐层神经元数为L、最大迭代次数为Imax,蚁狮和蚂蚁的种群规模均为N);
4) 根据(12)式中的限制条件,随机初始化蚂蚁与蚁狮种群,蚁狮优化算法中每只蚂蚁与蚁狮的位置均表示极限学习机待优化的参数组合f(w,b);
5) 计算ALO模型中每只蚁狮的适应度值,这里的适应度值表示普林斯顿某一类别的模型测试数据集分割的精确度,将最优的视为精英蚁狮;
6) 按照(10)式更新蚂蚁的位置,并将蚂蚁与蚁狮合并,按照适应度值从大到小排序,将排在前N个的个体赋值给蚁狮种群,实现N个蚁狮个体的并行搜索;
7) 更新精英蚁狮,蚂蚁比蚁狮具有更好的适应度值,按(11)式将蚁狮更新到所捕获蚂蚁的位置,否则,蚁狮保持不变,继而蚁狮比精英蚁狮的适应度值更好,即蚁狮种群的最优个体的适应度值优于精英蚁狮的适应度值,用该蚁狮替换精英蚁狮,反之,则精英蚁狮保持不变;
8) 判断蚁狮优化算法是否达到最大迭代次数Imax,如果达到,就输出精英蚁狮对应的最优适应度值(测试数据的分割精确度)和位置(极限学习机待优化的参数组合f(w,b)),进行下一步,否则迭代次数加1,返回步骤6)继续执行,直到达到算法的最大迭代次数Imax;
9) 得到精英蚁狮对应的最优适应度值(测试数据的分割精确度),生成与之对应的三维网格模型分割结果(.seg文件),并在普林斯顿标准测试程序上运行得到可视化结果。
5 分析与讨论
5.1 实验数据集以及实验环境
采用普林斯顿模型数据集[10]中的Airplane、Ant、Chair、Octopus、Teddy和Fish模型进行实验,实验在处理器为Intel(R) Xeon(R) CUP E5-1603 v3 @2.8 GHz、内存为16 GB和显卡为NVIDIA Quadro K620的计算机上完成。
5.2 参数设置
ALO-ELM网格模型分割方法中主要涉及三个参数:蚁狮和蚂蚁的种群大小均为N、最大迭代次数为Imax、隐层神经元个数为L。文献[
6,8]在采用面片信息训练分割分类器时,将隐层神经元大小L均设置为500。参考文献[
6]中的
图 2. Airplane模型在不同种群规模下的收敛性
Fig. 2. Convergence of Airplane model at different population sizes
图 3. Octopus模型在不同种群规模下的收敛性
Fig. 3. Convergence of Octopus model at different population sizes
ALO-ELM网格模型分割方法的运行时间会随着种群规模的增大而加倍增加。综合考虑算法的运行时间与分割精确度,当种群规模N设置为20时,可在运行时间和分割精确度上取得良好的平衡。
由
5.3 实验结果的分析与比较
采用留一交叉验证法进行分割测试验证,每个类别数据集共20个模型,选用其中的19个模型作为训练数据集,1个模型作为测试数据集。最后将测试得到的分割结果与普林斯顿模型的实际分割结果进行比较。为了评价本文方法的优劣,将本文方法的分割结果与文献[
6-8]中的结果统计在
表 1. 文献[ 6-8]方法与本文方法在平均分割精确度上的比较
Table 1. Comparison of average segmentation accuracy obtained with the methods in references [6-8] and our method
| |||||||||||||||||||||||||||||||||||||||
本文方法对Airplane、Ant、Chair、Octopus、Teddy和Fish模型的分割结果如
为了便于观察比较,根据
表 2. 本文方法在训练面片数为200000~300000的模型时的时间消耗
Table 2. Time consumption of our method during training the model with 200000-300000 patches
|
从
图 5. 文献[ 6-8]方法与本文方法平均分割精确度的柱状图
Fig. 5. Bar chart showing average segmentation accuracy obtained with the methods in references[6-8] and our method
6 结论
本文提出了一种基于蚁狮优化的极限学习机的网格分割方法。在蚁狮优化算法中,蚂蚁受精英蚁狮与轮盘赌策略的影响随机游走,不断迭代更新,并将蚁狮种群与蚂蚁种群的最优解赋值给精英蚁狮,以此得到极限学习机最优的输入权值矩阵以及隐层偏置。本文采用此改进的极限学习机训练所得的分割分类器,相比于未经优化的极限学习机作为模型训练得到的分割分类器,能够对未分割的网格模型进行更高精确度的预测,有效避免了深度神经网络训练时间过长的问题。但本文方法仍有不足之处,存在一些工作有待研究:错分的面片聚集在一起构成连通区域会影响视觉效果,需要提取更有效的特征描述子训练分割分类器,以进一步提高网格分割的精确度。
[1] 夏清, 李帅, 郝爱民, 等. 基于深度学习的数字几何处理与分析技术研究进展[J]. 计算机研究与发展, 2019, 56(1): 155-182.
Xia Q, Li S, Hao A M, et al. Deep learning for digital geometry processing and analysis: a review[J]. Journal of Computer Research and Development, 2019, 56(1): 155-182.
[2] 安喆, 徐熙平, 杨进华, 等. 结合图像语义分割的增强现实型平视显示系统设计与研究[J]. 光学学报, 2018, 38(7): 0710004.
[3] 董孙俊. 基于机器学习的三维模型分割算法研究[D]. 昆明: 云南大学, 2014.
Dong SJ. The research of 3D model segmentation algorithm based on machine learning[D]. Kunming: Yunnan University, 2014.
[4] 赵天宇, 李海生, 吴晓群, 等. 基于多特征融合的三维形状分割方法[J]. 计算机辅助设计与图形学学报, 2018, 30(11): 2011-2017.
Zhao T Y, Li H S, Wu X Q, et al. A 3D shape segmentation method based on multi-feature fusion[J]. Journal of Computer-Aided Design & Computer Graphics, 2018, 30(11): 2011-2017.
[5] 张耀楠, 周升, 牛乐川, 等. 一种基于蚁群优化的网格分割方法[J]. 计算机工程, 2018, 44(2): 277-281.
Zhang Y N, Zhou S, Niu L C, et al. A mesh segmentation method based on ant colony optimization[J]. Computer Engineering, 2018, 44(2): 277-281.
[7] Guo K, Zou D Q, Chen X W. 3D mesh labeling via deep convolutional neural networks[J]. ACM Transactions on Graphics, 2015, 35(1): 3.
[8] 李红岩. 三维形状分割和标注的快速学习方法[J]. 计算机工程与应用, 2017, 53(11): 211-216.
Li H Y. Fast learning method for 3D shape segmentation and labeling[J]. Computer Engineering and Applications, 2017, 53(11): 211-216.
[9] Huang GB, Zhu QY, Siew CK. Extreme learning machine: a new learning scheme of feedforward neural networks[C]∥Proceedings of the International Joint Conference on Neural Networks, July 25-29, 2004, Budapest, Hungary. New York: IEEE, 2004: 25- 29.
[10] Chen X B, Golovinskiy A, Funkhouser T. A benchmark for 3D mesh segmentation[J]. ACM Transactions on Graphics, 2009, 28(3): 73.
[11] 王泽兵, 杨卫, 秦丽. 基于粒子群算法的动态热释电目标跟踪[J]. 光学学报, 2014, 34(10): 1004001.
[12] 惠晓威, 常正英, 林森, 等. 结合Predator-Prey-AACO的图像边缘检测算法[J]. 激光与光电子学进展, 2015, 52(5): 051001.
[13] Wang M J, Chen H L, Li H Z, et al. Grey wolf optimization evolving kernel extreme learning machine: application to bankruptcy prediction[J]. Engineering Applications of Artificial Intelligence, 2017, 63: 54-68.
[14] Mirjalili S. The ant lion optimizer[J]. Advances in Engineering Software, 2015, 83: 80-98.
[15] Belongie S, Malik J, Puzicha J. Shape matching and object recognition using shape contexts[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2002, 24(4): 509-522.
[16] HilagaM, ShinagawaY, KohmuraT, et al. Topology matching for fully automatic similarity estimation of 3D shapes[C]∥Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, August 12-17, 2001, Los Angeles, California, USA. New York: ACM, 2001: 203- 212.
[17] Shapira L, Shalom S, Shamir A, et al. Contextual part analogies in 3D objects[J]. International Journal of Computer Vision, 2010, 89(2/3): 309-326.
[18] 王亚, 周孟然, 陈瑞云, 等. 基于多层正则极限学习机的煤矿突水光谱判别方法[J]. 光学学报, 2018, 38(7): 0730002.
[19] 吕晓翠, 李国林, 李晗, 等. 基于特征提取的极限学习机算法在可调谐二极管激光吸收光谱学中的应用[J]. 中国激光, 2018, 45(9): 0911013.
Article Outline
杨晓文, 尹洪红, 韩燮, 刘佳鸣. 基于蚁狮优化的极限学习机的网格分割方法[J]. 激光与光电子学进展, 2020, 57(4): 041014. Xiaowen Yang, Honghong Yin, Xie Han, Jiaming Liu. Mesh Segmentation Based on Optimizing Extreme Learning Machine with Ant Lion Optimization[J]. Laser & Optoelectronics Progress, 2020, 57(4): 041014.
PDF全文
