三维网格的Mean Shift并行分割算法

孙晓鹏，荣 丹

（1.辽宁师范大学 计算机与信息技术学院，辽宁 大连116029；2.大连大学 辽宁省先进设计与智能计算省部共建教育部重点实验室，辽宁 大连116622）

0 引 言

近年来，随着三维激光扫描建模技术的成熟，三维网格模型分割的研究已经广泛应用到数字几何处理的许多领域中，如动画变形、纹理合成、参数化、局部特征提取等，并已成为数字几何处理研究领域的热点问题。现有的三维网格分割算法多数源自图像分割算法，如分水岭算法、k均值聚类算法、层次聚类算法、谱系聚类算法、Mean Shift算法等，在三维几何空间的分割问题上均有很好的推广应用。

Mean Shift算法是一种无参的核密度梯度估计方法，算法简单无需预处理、实时性好，处理目标变形等问题较为健壮，在视频跟踪、视频信号分析、图像分割等应用中有较好表现。2005年，彭宁嵩等［1］提出一种核函数窗宽自动选取的算法，根据后向跟踪、目标形心配准的思想对目标进行配准，在此基础上提取特征点并对其进行回归计算。该工作克服了固定核窗宽的局限性，保证了回归精度，可以有效地跟踪不断增大尺寸的刚性目标，但是没有实现对低分辨率图像的准确定位。2009年，云廷进等［2］基于粒子滤波的思想对人体进行红外跟踪。该方法基于Mean shift算法对各粒子进行收敛性分析，并根据状态粒子的坐标对其进行聚类，使用少数粒子即可实现对红外人体的准确跟踪，计算复杂度较低，但无法解决多目标的跟踪问题。汤杨等［3］提出了层次分级的 Mean shift算法，该方法在初次迭代求解聚类中心时采用不同带宽的核函数进行聚类，从而得到不同层级的聚类中心集，最后根据叶节点和根节点归属关系的分类情况实现图像分割。该算法很好地保留了图像的局部信息，实用性好，但对于一些细条状区域的分割效果并不理想。2011年，依玉峰等［4］针对图像分割问题提出一种改进的随机游走算法，该工作首先应用Mean shift算法对图像进行预分割，然后结合高斯函数和欧氏距离，计算相邻区域间的相似性，根据节点间的概率分布对预分割结果进行分类。与传统随机游走算法相比，该工作很好地处理了自然纹理背景的干扰，计算效率和分割精度都有很大的提高。另外，Mean Shift算法在信息融合［5］、 模式识别与聚类分析［6－7］等领域中也有广泛应用。

随着三维网格模型数据规模的增大以及高阶数字几何计算日趋复杂，数字几何处理研究对算法的实时性要求也与日俱增。GPU的出现大大提高了相关工作的计算效率，并降低了显卡对CPU的依赖，大部分图形处理工作从CPU中转移到GPU；同时GPU的高性能并行计算、高精度计算也为数字几何处理工作提供了有力的支持。2010年，葛军等［8］以人机交互的形式，基于GPU的多个通道通用计算功能实现了体数据绘制与切割，提高了体数据的绘制效率，该工作通过人机交互实时地改变切割体的位置和形状，克服了传统方法对切割体形状和数量的限制，降低了对显示存储空间的需求，但该方法对复杂结构的体数据切割效果不是很好。陈加等［9］提出了一种快速的Mean shift算法，使用K－means算法对图像进行预分类，然后在预分类后得到的数据集上进行Mean shift聚类。该方法利用GPU来加速数据读取和最小化GPU与CPU之间的数据传输，对K－means和 Mean shift分别进行并行处理，克服了传统mean shift算法运行速度慢的缺点，有效提高了图像的识别率和算法的运行速度，满足了实时性要求。

本文提出了一种改进的Mean Shift并行分割网格模型的算法。首先提取三维网格模型的多显著特征点；然后利用GPU的高性能并行计算能力，实现了基于Mean Shift算法的并行分割。与同类工作相比，本算法得到了更有意义的分割，并提高计算运行效率。

1 三维网格的Mean Shift串行分割

对于Rd空间n个样本X＝｛xi｜i＝1，2，…，n｝，设Sh（x）＝｛y｜（y－x）T（y－x）≤h2｝，即半径为h的高维球区域，x、y是空间中的点，则记（xix）／k，其中Mh（x）为落入Sh区域的k个样本点对n个样本点xi的均值偏移向量（Mean Shift向量），它指向样本集概率密度的梯度方向，其中k表示在n个样本点xi中落入Sh区域的个数。Mh（x）计算步骤包括选定初始区域、确定分类中心、移动区域到一个新的中心位置、迭代直至收敛等4个步骤。该算法的本质是自适应的梯度上升搜索极值，通过反复迭代搜索样本空间中的最密集区域，并计算收敛值，最后根据收敛值对样本点进行分类［10］。

基于上述的基本思想，本文记三角网格模型S上的面片集合为F＝｛Fj｜j＝1，2，…，m｝，m为三角网格上的面片数目。定义三角网格顶点上的离散曲率为α＊H＋（1－α）＊K（其中α为权值），即为该顶点的平均曲率H和高斯曲率K的加权和，则记三角面片fj的曲率Cj为该面片上3个顶点曲率的平均。本文定义S的面片集合F上的Mean Shift分割过程如下：

步骤1 交互指定面片m1，以该三角面片的中心为初始球心、以给定h为半径定义初始球（如图1（b））；令δ为误差阈值，比较落在球内三角面片fj的曲率Cj与球心面片m1的曲率Cm1，若满足｜Cj－Cm1｜＜δ，则将面片fj与球心面片m1归为一类，将标志位数组与面片fj对应的标志位记为sign（j）＝1。记本次迭代添加三角面片中心点的平均值为下一球心（如图1（c）所示），迭代求解，直至达到指定的分类数目，或者面片分类情况不再发生变化（如图1（d）所示）。

图1 Mean Shift对面片的串行分类过程

步骤2 在面片集合为F求与初始球心m1测地距离最远的面片m2，以其面片中心为球心，以h为半径定义球（如图1（e））；比较落在球内三角面片fj的曲率Cj与球心面片m2的曲率Cm2，若满足｜Cj－Cm2｜＜δ，则将面片fj与球心面片m2归为一类，将标志位数组与面片fj对应的标志位记为sign（j）＝2。

依此类推，直到遍历所有面片。对于没有进行分类的面片，按照就近原则进行分类（如图1（f）所示）。

2 并行的Mean Shift

Mean Shift算法每一次新的迭代都需要将与已有分类球心测地距离最远的面片中心作为新的分类球心，并使用同样的方法对新分类球心的周围面片进行分类，该算法具有高度的可并行性。本文在提取显著性特征点的基础上，采用并行计算的方法，从多个特征点开始并发地执行Mean Shift算法，充分利用GPU硬件，提高计算效率。该工作包括提取显著性特征点作为分类球心的初始位置和并发执行Mean Shift算法两部分内容。

2.1 提取显著性特征点

设S的顶点集合为V＝｛vi｜i＝1，2，…，n｝，对于V中的任意顶点v，设Nv是其k－ring邻接顶点集合，g（v，p）表示顶点v和顶点p之间的离散测地距离。

对于S表面任意一个顶点v，其与S上其他所有顶点p之间的测地距离之和定义为［11］

如果对于任意的vi∈Nv，都有pf（v）＞pf（vi），则称顶点v为S上的显著特征点。记显著特征点的集合为｛svi｜i＝1，2，…，NS｝，其中NS为模型S上显著特征点的数目，则有特征点间的测地距离平均值为［11］

合并测地距离小于TS的显著特征点对，得到显著特征点集合C＝｛svi∈S：svj∈C，g（svi，svj）＜TS｝［11］。

2.2 基于GPU的并行Mean Shift

记S上显著特征点集合C中特征显著点的数目为NPCs，显著特征点的坐标存放在CPU数组SPC中；S上面片的标志位存放在CPU数组sign中；函数gsingle将CPU数组SPC和sign分别转换为GPU类型的矩阵gSPC和gsign。GPU的并行循环gfor执行mean Shift算法，将模型S上的面片分类到各显著特征顶点的集合中，从而完成分类。算法伪代码描述如下：

如图2所示，本节首先计算模型显著特征点的位置和数目（如图2（b）），然后分别从各个显著特征点并发执行Mean Shift，实现分类（如图2（c））。与串行的 Mean Shift算法（图1）不同，本节分类过程中，初始球心即为多显著特征点，多个球分别从各自所在的显著特征点并发执行分类。

图2 Mean Shift对面片的并行分类过程

上述对三角网格上的面片集合F分类的过程较为粗糙，两类面片集合之间的分割边界往往有明显的锯齿，分割边界也缺乏明确的几何意义。本文基于文献［12］的后处理方法对分类边界进行后处理，得到了有意义的分割结果。

3 实验结果与分析

本文实验环境为Intel（R）Celeron（R）CPU 2.66GHZ，1.5GB内存空间，显示处理器为拥有128个流处理器Geforce GTS250，编程环境为C＋＋和Matlab。本文实验数据来自Princeton大学的三维分割Benchmark数据库，该数据库共提供了19类380个三维网格模型的手工分割结果、以及其他各种算法完成的自动分割结果［13］。

图3是本文实验结果与其他相关算法的比较［13］，在分割份数相同的前提下，本文工作的分割边界和整体分割效果比较理想。与Norm Cuts算法相比，对于Benchmark数据库的模型30、165、208，本文工作的实验结果较好，模型22、379的分割效果相近，模型101、128中Norm Cuts算法的分割效果比本文实验结果好。与Rand Cuts算法比较，对于Benchmark数据库的模型101、208、221、379，本文分割效果较好。表1为本文算法在CPU上串行实现与在GPU上并行实现所需时间的对比，由表1中的加速比可以看出，本文基于GPU算法的实验速度明显得到提高，而且与模型的数据规模、分割份数有关，分割份数越多，实验速度越快。

图3 本文工作与其他分割算法对比

表1 GPU／CPU计算效率对比

4 结束语

本文基于Mean Shift算法的基本理论，实现了基于三维网格模型多个显著特征点的并行快速分割算法，得到了较为有意义的分割结果，并分析对比了CPU／GPU的计算效率，与基于CPU的串行Mean Shift分割相比，基于GPU的并行分割效率有所提高，与同类工作相比，本文算法的分割效果较好。不足之处在于，本文算法仅适用于分支形状特征不紧凑的模型，在处理分支紧凑的三维模型时分割效果不理想；另外本文对GPU与CPU间数据交换的效率没有展开研究，后续工作将考虑改进本文算法，提高在分支特征紧凑模型的分割效果，并在改善GPU和CPU之间的数据交换效率上，以期进一步提高减速比。

［1］PENG Ningsong，YANG Jie，LIU Zhi，et al.Automatic selection of kernel－bandwidth for Mean－Shift object tracking［J］.Journal of Software，2005，16（9）：1542－1550（in Chinese）.［彭宁嵩，杨杰，刘志，等.Mean－Shift跟踪算法中核函数窗宽的自动选取［J］.软件学报，2005，16（9）：1542－1550.］

［2］YUN Tingjin，GUO Yongcai，GAO Chao.Human tracking in infrared images based on particles Mean－Shift migration algorithm［J］.Chinese Journal of Computers，2009，32（6）：1222－1228（in Chinese）.［云廷进，郭永彩，高潮.基于粒子Mean Shift迁移的红外人体目标跟踪算法［J］.计算机学报，2009，32（6）：1222－1228.］

［3］TANG Yang，PAN Zhigeng，TANG Min，et al.Image segmentation with hierarchical mean shift［J］.Journal of Computer Research and Development，2009，46（9）：1424－1431（in Chinese）.［汤杨，潘志庚，汤敏，等.基于分级mean shift的图像分割算法［J］.计算机研究与发展，2009，46（9）：1424－1431.］

［4］YI Yufeng，GAO Liqun，GUO Li.Mean shift based rand walker interactive image segmentation algorithm［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2011，23（11）：1875－1881（in Chinese）.［依玉峰，高立群，郭丽.基于Mean shift随机游走图像分割算法［J］.计算机辅助设计与图形学学报，2011，23（11）：1875－1881.］

［5］Comaniciu D.Nonparametric information fusion for motion estimation［C］／／Madison：Proc of the IEEE Int’l Conf on Computer Vision and Pattern Recognition，2003：59－66.

［6］Comaniciu D，Ramesh V，Bue AD.Multivariate saddle point detection for statistical clustering［C］／／Copenhagen：Proc of the European Conf on Computer Vision，2002：561－576.

［7］Georgescu B，Shimshoni I，Meer P.Mean shift based clustering in high dimensions：A texture classification example［C］／／Beijing：Proc of the ICCV，2003：456－463.

［8］GE Jun，JIANG Xiaoming，SHU Huazhong.GPU－Based interactive volume cutting［J］.Journal of Computer－Aided Design ＆ Computer Graphics，2010，22（3）：298－233（in Chinese）.［葛军，姜小明，舒华忠.基于GPU的交互式体数据切割［J］.计算机辅助设计与图形学学报，2010，22（3）：298－233.］

［9］CHEN Jia，WU Xiaojun，CAI Rong.Parallel processing for accelerated mean shift algorithm with GPU［J］.Journal of Computer Aided Design ＆ Computer Graphics，2010，22（3）：463－464（in Chinese）.［陈加，吴晓军，蔡荣.GPU并行加速的均值偏移算法［J］.计算机辅助设计与图形学报，2010，22（3）：463－464.］

［10］WEN Zhiqiang，CAI Zixing.Convergence analysis of mean shift algorithm［J］.Journal of Software，2007，18（2）：205－212（in Chinese）.［文志强，蔡自兴.Mean shift算法的收敛性分析［J］.软件学报，2007，18（2）：205－212.］

［11］Agathos A，Pratikakis I，Perantonis S，et al.Protrusionoriented 3dmesh segmentation［J］.The Visual Computer，2010，26（1）：63－81.

［12］Katz Sagi，Tal Ayellet.Hierarchical mesh decomposition using fuzzy clustering and cuts［J］.ACM Transactions on Graphics，2003，22（3）：954－961.

［13］Chen Xiaobai，Aleksey Golovinskiy，Thomas Funkhouser.A benchmark for 3Dmesh segmentation［J］.ACM Transactions on Graphics，2009，28（3）：1－12.