一种基于蚁群优化的网格分割方法

张耀楠,周 升,牛乐川,王元一

(1.西安思源学院 电子信息工程学院,西安 710038; 2.东北大学 中荷生物医学与信息工程学院,沈阳 110169)

0 概述

近年来,由于数码照相机、数码摄像机、医学成像、遥感成像、工程成像等技术的快速发展和普遍应用,产生了大量的三维图像和影像数据。通过图像处理和分析会形成大量的自然物体和人体器官的三维网格数据。一般而言,这些三维网格数据还需要做进一步的处理才能被特定的应用使用。 网格分割是其中重要的一步,它将三维网格数据按照一定的标准分离成部件或曲面片,为以后的压缩、识别、检索、分类等提供基础。

图像分割领域现已存在较多方法,但网格分割研究相对文献较少。文献[1]从分割类型及策略、算法复杂度及范围等方面对典型的网格分割算法进行了比较。文献[2]提出一种基于高斯映射的法向聚类CAD网格分割方法。文献[3]通过热核函数来描述曲面的属性。文献[4]通过近似矩阵来比较2块曲面,然后通过聚类进行分割。文献[5]对形状比较的度量方法进行了综述。文献[6]中方法是完全无监督的,并可表示为一个整数二次规划的联合分割问题。文献[7]中引入一组无监督的协同层次分析,目的在于发现分层结构和揭示形状部件之间的关系。文献[8]以过分割结果作为起点,然后通过统计聚类来描述集群,同时采用多标签优化改善共分割。文献[9]提出使用深度学习分割3D形状。文献[10]使用Student-t混合模型与变分贝叶斯近似,提出了一个网格聚类算法。文献[11]则将先验知识与基于几何相似性的内容驱动分析相结合。

本文使用蚁群优化(Ant Colony Optimization,ACO)[12]算法进行网格分割。ACO算法模拟蚂蚁在自然界中觅食的行为:在地上行走时遗留激素而被其他蚂蚁探测,进而用来寻找巢穴和食物来源之间的最有效路线。ACO最初被成功地应用于旅行商问题,后被用于许多工程问题如网络路径优化、图像处理等[13]。笔者在早期的工作中已成功地将蚁群优化应用到图像序列的移动矢量估计上[14],在本文中则将蚁群优化应用到三维网格的分割中。

1 网格分割模型与方法

1.1 基于蚁群优化的网格分割模型

网格分割的目的是将每个网格赋予一个标签,并且使属于同一标签的相邻网格满足分割条件。将待分割网格的每个网格视为一个蚂蚁,每个蚂蚁可以选择Γ个标签,通过蚁群优化机制对每个网格的标签不断更新。在迭代过程中,每个蚂蚁最佳的标签由式(1)决定。

(1)

其中:p(u)是一个候选标签u的转移概率。

转移概率按式(2)计算。

(2)

其中:τ(u)被称为残留信息浓度,在迭代过程中,每个蚂蚁都保留在所有标签下的残留信息;η(u)为启发值,它反映了蚂蚁对于某个标签的趋向;α和β是控制τ(u)和η(u)相对平衡的2个因子系数。

η(u)的计算公式如式(3)所示。

(3)

其中:ε(u)是本蚂蚁对应于u标签的特征值,其计算方法将在下文描述。

1.2 残留信息浓度的更新

在迭代过程中,每个蚂蚁的每个标签的残留信息浓度都要更新。设τ(u)第一次迭代前的初始值为τ0,并在每次迭代结束时被更新,如式(4)所示。

τ(u)←ρ·τ(u)+γ·Δτ(u)

(4)

其中:ρ为遗传系数,它代表蚂蚁当前残留信息浓度对下次迭代的影响程度;Δτ(u)为残留信息浓度增量的空间约束分量,它由计算相邻蚂蚁的平均残留信息浓度而得。

相邻蚂蚁的平均残留信息按式(5)计算。

(5)

其中:假设当前的蚂蚁为b,b′为邻域中符合分割条件的蚂蚁之一;NS为邻域大小。

1.3 蚂蚁的特征值

对于网格,可以计算网格的一些属性,如曲率、形状直径函数(Shape Diameter Function,SDF)[15]等。本文选用SDF。形状直径函数是一个定义在网格表面上的标量函数,它表示在网格表面每一点附近的物体体积的直径。

在式(3)中,ε(u)是本蚂蚁对应于u标签的特征值,这是驱动网格分割的主要标准。本文计算特征值的办法是计算某个蚂蚁邻域内网格点SDF的标准差。

1.4 网格标签初始化与种子点产生

图1显示了网格初始化的过程。所有的网格先赋予一个背景标签(如Γ+1)。然后对于每一个种子点(每一个种子点对应一个唯一的标签),其周围的网格点赋予和种子点一样的标签。产生种子点可以采取随机的方法产生。随着蚁群优化的迭代,种子点的标签向外扩散,直到迭代标准满足。图1中V1和V2是2个种子点,而V3是背景标签。

图1 网格初始化

1.5 分割条件

下面以SDF为网格属性为例说明分割条件。对于一个待更新蚂蚁b,其目前的最佳标签为M,假设其邻域含有若干个非背景标签。对于其中一个候选标签u,其分割条件如式(6)所示。

(6)

并且:

|mean(SDF[Ω(b,M)])-

(7)

图2 网格邻域示意图

2 基于蚁群优化的网格分割算法

基于蚁群优化的网格分割算法描述如下:

输入标签个数Γ、迭代次数、待处理三维网格数据

计算网格属性如SDF

数据预处理:准备每个蚂蚁的数据结构、计算每个蚂蚁的邻域、将属性归一化

产生种子点

初始化网格标签(背景标签和种子点邻域标签)

Loop/*蚁群优化迭代*/

Loop/*对每个蚂蚁,挑选最佳标签*/

IF检查这个蚂蚁是否需要被更新,如果是,执行以下步骤(参见下文注1)

Loop/*对每个候选标签u,计算其转移概率*/

计算候选标签u的特征值

计算转移概率p(u)(式(2))

End/*完成所有候选标签的计算*/

根据式(1)选取最佳标签并记录

End

End

Loop/*对每个蚂蚁,更新其残留信息浓度*/

IF检查这个蚂蚁是否需要被更新,如果是,执行以下步骤

Loop/*对每个候选标签u进行更新*/

根据式(4)和式(5),更新τ(u)

End

End

End

End/*最大迭代次数达到或迭代标准完成*/

区域合并(参见下文注2)

输出分割结果

注1:在蚂蚁更新过程中,有一个判断标准。这一步有以下目的;1)保证背景标签不做不必要的更新;2)种子点及其邻域只有在满足分割条件的情况下才能扩散。一个蚂蚁只有在下面情况下才能更新:1)邻域含有足够的非背景标签;2)至少有一个候选标签满足分割条件。

注2:蚁群迭代完成后,相邻的区域在满足分割条件的情况下进行合并。

3 实验与结果分析

对本文算法用MATLAB(版本2012a)进行实现,并对Princeton网格数据集(http://segeval.cs.princeton.edu/)的一些例子进行实验。所用计算机处理器为Intel i5-4590 CPU @3.30 GHz,内存4 GB,64位操作系统。

3.1 参数选择

关于式(2)中α和β的选择,根据多数数蚁群优化的文献以及笔者的相关研究,2个参数均可选1。关于式(4)中ρ和γ的选择,根据笔者多次实验,选用ρ=0.7及γ=0.2可以达到较好的结果。

图3(a)显示了蚁群优化的迭代次数和标签更新率的关系,此结果是对Princeton网格数据集第180例数据上实验得到的。标签更新率指一次迭代时标签发生更新的网格顶点数与总网格顶点数之比。从中可以看出,迭代次数在20次左右之后,标签更新率基本稳定,这种现象在测试其他例子时也是如此。图3(b)显示了蚁群优化的迭代次数和标签更新率在第130例数据的关系。

图3 蚁群优化迭代次数与标签更新率的关系

可以看出,标签更新率在开始迭代后几次达到高峰,然后迅速下降,再达到基本稳定。这一点和将蚁群优化用于移动矢量估计结果有所不同[13]。在那种情况下,在约第10帧之前,移动矢量仍然大幅度振荡,当经过一定数量的帧数之后,移动矢量才开始趋于稳定。由此可以看出,应用不同,蚁群优化的收敛结果是不同的。

3.2 实验结果

图4显示对Princeton网格数据集第91例网格数据的处理结果。 这个例子有8 640个顶点、17 276个网面。图4(a)是原始网格,图4(b)显示了种子点,共有40个,图4(c)显示了蚁群优化的结果,也是区域合并前结果,而图4(d)显示了区域合并后结果,即最后分割结果。分割结果含有11个区域,正确率100%。

图4 Princeton网格数据集第91例分割结果

图5显示对第130例网格数据的处理结果。该例有7 747个顶点、15 490个网面。分割结果包含9个区域,正确率为100%。

图5 Princeton网格数据集第130例分割结果

图6显示对第180例网格数据的处理结果。该例有9 548个顶点、19 092个网面。分割结果包含7个区域,正确率为100%。

图6 Princeton网格数据集第180例分割结果

3.3 与图割方法的比较

图割是图像分割的热门研究方向,也有将图割用于网格分割的研究[16-18]。将本文方法和图割方法进行比较。在图割方法中,首先,用高斯混合模型将k个高斯函数拟合SDF直方图,此过程通过EM(Expectation Maximization)算法完成。通过这个聚类过程可以得到三维网格每个网格点SDF值在各个高斯函数下的概率,也就是该网格点属于各个区域的概率。然后通过α-扩张图割算法取得最后分割结果。这一步优化将高斯混合模型拟合的结果和其他平滑条件结合形成一个能量函数。图7显示了利用图割方法的分割结果:图7(a)中分割出15个区域,正确率73%;图7(b)中分割出20个区域,正确率35%;图7(c)中分割出11个区域,正确率82%。通过比较可以看出本文方法的分割结果较好。

图7 图割方法分割结果

4 结束语

本文将蚁群优化算法应用到三维网格的分割上,利用MATLAB进行实现,并通过Princeton网格数据集的例子进行实验。本文方法具有简单、灵活的优点,可以根据具体问题灵活构造,本文特征值使用的是SDF值,对于其他应用,可以使用其他特征值或者多个特征值。此外,蚁群优化具有潜在的平行处理特性,可以加快处理速度,这需要进一步研究。后续工作是将本文方法用在其他应用上,如在生物医学工程领域,在医学图像分割之后,可以通过网格分割进一步划分出人体结构的许多子结构。此外,笔者也拟将本文方法与其他方法相结合,以提高分割质量。

[1] 董洪伟.三角网格分割综述[J].中国图象图形学报,2010,15(2):181-193.

[2] 易 兵,刘振宇,谭建荣.基于高斯映射的CAD网格法向聚类分割方法[J].机械工程学报,2015,51(7):115-122.

[3] FANG Y,SUN M,KIM M,et al.Heat-mapping:A Robust Approach Toward Perceptually Consistent Mesh Segmentation[C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington D.C.,USA:IEEE Press,2011:2145-2152.

[4] HU Ruizhen,FAN Lubin,LIU Ligang.Co-segmentation of 3D Shapes via Subspace Clustering[J].Computer Graphics Forum,2012,31(5):1703-1713.

[5] BIASOTTI S,CERRI A,BRONSTEIN A,et al.Recent Trends,Applications,and Perspectives in 3D Shape Similarity Assessment[J].Computer Graphics Forum,2016,35(6):87-119.

[6] HUANG Qixing,KOLTUN V,GUIBAS L.Joint Shape Segmentation with Linear Programming[J].ACM Transactions on Graphics,2011,30(6).

[7] van KAICK O,XU Kai,ZHANG Hao,et al.Co-hierarchical Analysis of Shape Structures[J].ACM Transactions on Graphics,2013,32(4).

[8] MENG Min,XIA Jiazhi,LUO Jun,et al.Unsupervised Co-segmentation for 3D Shapes Using Iterative Multi-label Optimization[J].CAD Computer Aided Design,2013,45(2):312-320.

[9] SHU Zhenyu,QI Chengwu,XIN Shiqing,et al.Unsupervised 3D Shape Segmentation and Co-segmentation via Deep Learning[J].Computer Aided Geometric Design,2016,43(3):39-52.

[10] TSUCHIE S,HOSINO T,HIGASHI M.High-quality Vertex Clustering for Surface Mesh Segmentation Using Student-t Mixture Model[J].CAD Computer Aided Design,2014,46(1):69-78.

[11] van KAICK O,TAGLIASACCHI A,SIDI O,et al.Prior Knowledge for Part Correspondence[J].Computer Graphics Forum,2011,30(2):553-562.

[12] DORIGO M,GAMBARDELLA L.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

[13] 魏 东,吴良杰,佐 丹,等.基于混合蚁群算法的网格任务调度[J].计算机工程,2010,36(3):215-217.

[14] 张耀楠,杨 乐,康 雁.蚁群优化在超声图像运动矢量估计中的应用[J].东北大学学报(自然科学版),2012,33(3):327-331.

[15] SHAPIRA L,SHAMIR A,COHEN-OR D.Consistent Mesh Partitioning and Skeletonisation Using the Shape Diameter Function[J].Visual Computer,2008,24(4):249-259.

[16] UGAIL H,LIU Lei,SHENG Yun,et al.Graph Cut Based Mesh Segmentation Using Feature Points and Geodesic Distance[C]//Proceedings of 2015 International Con-ference on Cyberworlds.Visby,Sweden:[s.n.],2015:115-120.

[17] LI Guodong,CHEN Xinjian,SHI Fei,et al.Automatic Liver Segmentation Based on Shape Constraints and Deformable Graph Cut in CT Images[J].IEEE Transactions on Image Processing,2015,24(12):5315-5329.

[18] SHI Zhenfeng,LE Dan,YU Liyang,et al.3D Mesh Segmentation Based on Markov Random Fields and Graph Cuts[J].IEICE Transactions on Information and Systems,2012,E95-D(2):703-706.