孫曉鵬，榮 丹

（1.遼寧師范大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，遼寧 大連116029；2.大連大學(xué) 遼寧省先進(jìn)設(shè)計(jì)與智能計(jì)算省部共建教育部重點(diǎn)實(shí)驗(yàn)室，遼寧 大連116622）

0 引 言

近年來，隨著三維激光掃描建模技術(shù)的成熟，三維網(wǎng)格模型分割的研究已經(jīng)廣泛應(yīng)用到數(shù)字幾何處理的許多領(lǐng)域中，如動(dòng)畫變形、紋理合成、參數(shù)化、局部特征提取等，并已成為數(shù)字幾何處理研究領(lǐng)域的熱點(diǎn)問題。現(xiàn)有的三維網(wǎng)格分割算法多數(shù)源自圖像分割算法，如分水嶺算法、k均值聚類算法、層次聚類算法、譜系聚類算法、Mean Shift算法等，在三維幾何空間的分割問題上均有很好的推廣應(yīng)用。

Mean Shift算法是一種無參的核密度梯度估計(jì)方法，算法簡(jiǎn)單無需預(yù)處理、實(shí)時(shí)性好，處理目標(biāo)變形等問題較為健壯，在視頻跟蹤、視頻信號(hào)分析、圖像分割等應(yīng)用中有較好表現(xiàn)。2005年，彭寧嵩等［1］提出一種核函數(shù)窗寬自動(dòng)選取的算法，根據(jù)后向跟蹤、目標(biāo)形心配準(zhǔn)的思想對(duì)目標(biāo)進(jìn)行配準(zhǔn)，在此基礎(chǔ)上提取特征點(diǎn)并對(duì)其進(jìn)行回歸計(jì)算。該工作克服了固定核窗寬的局限性，保證了回歸精度，可以有效地跟蹤不斷增大尺寸的剛性目標(biāo)，但是沒有實(shí)現(xiàn)對(duì)低分辨率圖像的準(zhǔn)確定位。2009年，云廷進(jìn)等［2］基于粒子濾波的思想對(duì)人體進(jìn)行紅外跟蹤。該方法基于Mean shift算法對(duì)各粒子進(jìn)行收斂性分析，并根據(jù)狀態(tài)粒子的坐標(biāo)對(duì)其進(jìn)行聚類，使用少數(shù)粒子即可實(shí)現(xiàn)對(duì)紅外人體的準(zhǔn)確跟蹤，計(jì)算復(fù)雜度較低，但無法解決多目標(biāo)的跟蹤問題。湯楊等［3］提出了層次分級(jí)的 Mean shift算法，該方法在初次迭代求解聚類中心時(shí)采用不同帶寬的核函數(shù)進(jìn)行聚類，從而得到不同層級(jí)的聚類中心集，最后根據(jù)葉節(jié)點(diǎn)和根節(jié)點(diǎn)歸屬關(guān)系的分類情況實(shí)現(xiàn)圖像分割。該算法很好地保留了圖像的局部信息，實(shí)用性好，但對(duì)于一些細(xì)條狀區(qū)域的分割效果并不理想。2011年，依玉峰等［4］針對(duì)圖像分割問題提出一種改進(jìn)的隨機(jī)游走算法，該工作首先應(yīng)用Mean shift算法對(duì)圖像進(jìn)行預(yù)分割，然后結(jié)合高斯函數(shù)和歐氏距離，計(jì)算相鄰區(qū)域間的相似性，根據(jù)節(jié)點(diǎn)間的概率分布對(duì)預(yù)分割結(jié)果進(jìn)行分類。與傳統(tǒng)隨機(jī)游走算法相比，該工作很好地處理了自然紋理背景的干擾，計(jì)算效率和分割精度都有很大的提高。另外，Mean Shift算法在信息融合［5］、 模式識(shí)別與聚類分析［6－7］等領(lǐng)域中也有廣泛應(yīng)用。

隨著三維網(wǎng)格模型數(shù)據(jù)規(guī)模的增大以及高階數(shù)字幾何計(jì)算日趨復(fù)雜，數(shù)字幾何處理研究對(duì)算法的實(shí)時(shí)性要求也與日俱增。GPU的出現(xiàn)大大提高了相關(guān)工作的計(jì)算效率，并降低了顯卡對(duì)CPU的依賴，大部分圖形處理工作從CPU中轉(zhuǎn)移到GPU；同時(shí)GPU的高性能并行計(jì)算、高精度計(jì)算也為數(shù)字幾何處理工作提供了有力的支持。2010年，葛軍等［8］以人機(jī)交互的形式，基于GPU的多個(gè)通道通用計(jì)算功能實(shí)現(xiàn)了體數(shù)據(jù)繪制與切割，提高了體數(shù)據(jù)的繪制效率，該工作通過人機(jī)交互實(shí)時(shí)地改變切割體的位置和形狀，克服了傳統(tǒng)方法對(duì)切割體形狀和數(shù)量的限制，降低了對(duì)顯示存儲(chǔ)空間的需求，但該方法對(duì)復(fù)雜結(jié)構(gòu)的體數(shù)據(jù)切割效果不是很好。陳加等［9］提出了一種快速的Mean shift算法，使用K－means算法對(duì)圖像進(jìn)行預(yù)分類，然后在預(yù)分類后得到的數(shù)據(jù)集上進(jìn)行Mean shift聚類。該方法利用GPU來加速數(shù)據(jù)讀取和最小化GPU與CPU之間的數(shù)據(jù)傳輸，對(duì)K－means和 Mean shift分別進(jìn)行并行處理，克服了傳統(tǒng)mean shift算法運(yùn)行速度慢的缺點(diǎn)，有效提高了圖像的識(shí)別率和算法的運(yùn)行速度，滿足了實(shí)時(shí)性要求。

本文提出了一種改進(jìn)的Mean Shift并行分割網(wǎng)格模型的算法。首先提取三維網(wǎng)格模型的多顯著特征點(diǎn)；然后利用GPU的高性能并行計(jì)算能力，實(shí)現(xiàn)了基于Mean Shift算法的并行分割。與同類工作相比，本算法得到了更有意義的分割，并提高計(jì)算運(yùn)行效率。

1 三維網(wǎng)格的Mean Shift串行分割

對(duì)于Rd空間n個(gè)樣本X＝｛xi｜i＝1，2，…，n｝，設(shè)Sh（x）＝｛y｜（y－x）T（y－x）≤h2｝，即半徑為h的高維球區(qū)域，x、y是空間中的點(diǎn)，則記（xix）／k，其中Mh（x）為落入Sh區(qū)域的k個(gè)樣本點(diǎn)對(duì)n個(gè)樣本點(diǎn)xi的均值偏移向量（Mean Shift向量），它指向樣本集概率密度的梯度方向，其中k表示在n個(gè)樣本點(diǎn)xi中落入Sh區(qū)域的個(gè)數(shù)。Mh（x）計(jì)算步驟包括選定初始區(qū)域、確定分類中心、移動(dòng)區(qū)域到一個(gè)新的中心位置、迭代直至收斂等4個(gè)步驟。該算法的本質(zhì)是自適應(yīng)的梯度上升搜索極值，通過反復(fù)迭代搜索樣本空間中的最密集區(qū)域，并計(jì)算收斂值，最后根據(jù)收斂值對(duì)樣本點(diǎn)進(jìn)行分類［10］。

基于上述的基本思想，本文記三角網(wǎng)格模型S上的面片集合為F＝｛Fj｜j＝1，2，…，m｝，m為三角網(wǎng)格上的面片數(shù)目。定義三角網(wǎng)格頂點(diǎn)上的離散曲率為α＊H＋（1－α）＊K（其中α為權(quán)值），即為該頂點(diǎn)的平均曲率H和高斯曲率K的加權(quán)和，則記三角面片fj的曲率Cj為該面片上3個(gè)頂點(diǎn)曲率的平均。本文定義S的面片集合F上的Mean Shift分割過程如下：

步驟1 交互指定面片m1，以該三角面片的中心為初始球心、以給定h為半徑定義初始球（如圖1（b））；令δ為誤差閾值，比較落在球內(nèi)三角面片fj的曲率Cj與球心面片m1的曲率Cm1，若滿足｜Cj－Cm1｜＜δ，則將面片fj與球心面片m1歸為一類，將標(biāo)志位數(shù)組與面片fj對(duì)應(yīng)的標(biāo)志位記為sign（j）＝1。記本次迭代添加三角面片中心點(diǎn)的平均值為下一球心（如圖1（c）所示），迭代求解，直至達(dá)到指定的分類數(shù)目，或者面片分類情況不再發(fā)生變化（如圖1（d）所示）。

圖1 Mean Shift對(duì)面片的串行分類過程

步驟2 在面片集合為F求與初始球心m1測(cè)地距離最遠(yuǎn)的面片m2，以其面片中心為球心，以h為半徑定義球（如圖1（e））；比較落在球內(nèi)三角面片fj的曲率Cj與球心面片m2的曲率Cm2，若滿足｜Cj－Cm2｜＜δ，則將面片fj與球心面片m2歸為一類，將標(biāo)志位數(shù)組與面片fj對(duì)應(yīng)的標(biāo)志位記為sign（j）＝2。

依此類推，直到遍歷所有面片。對(duì)于沒有進(jìn)行分類的面片，按照就近原則進(jìn)行分類（如圖1（f）所示）。

2 并行的Mean Shift

Mean Shift算法每一次新的迭代都需要將與已有分類球心測(cè)地距離最遠(yuǎn)的面片中心作為新的分類球心，并使用同樣的方法對(duì)新分類球心的周圍面片進(jìn)行分類，該算法具有高度的可并行性。本文在提取顯著性特征點(diǎn)的基礎(chǔ)上，采用并行計(jì)算的方法，從多個(gè)特征點(diǎn)開始并發(fā)地執(zhí)行Mean Shift算法，充分利用GPU硬件，提高計(jì)算效率。該工作包括提取顯著性特征點(diǎn)作為分類球心的初始位置和并發(fā)執(zhí)行Mean Shift算法兩部分內(nèi)容。

2.1 提取顯著性特征點(diǎn)

設(shè)S的頂點(diǎn)集合為V＝｛vi｜i＝1，2，…，n｝，對(duì)于V中的任意頂點(diǎn)v，設(shè)Nv是其k－ring鄰接頂點(diǎn)集合，g（v，p）表示頂點(diǎn)v和頂點(diǎn)p之間的離散測(cè)地距離。

對(duì)于S表面任意一個(gè)頂點(diǎn)v，其與S上其他所有頂點(diǎn)p之間的測(cè)地距離之和定義為［11］

如果對(duì)于任意的vi∈Nv，都有pf（v）＞pf（vi），則稱頂點(diǎn)v為S上的顯著特征點(diǎn)。記顯著特征點(diǎn)的集合為｛svi｜i＝1，2，…，NS｝，其中NS為模型S上顯著特征點(diǎn)的數(shù)目，則有特征點(diǎn)間的測(cè)地距離平均值為［11］

合并測(cè)地距離小于TS的顯著特征點(diǎn)對(duì)，得到顯著特征點(diǎn)集合C＝｛svi∈S：svj∈C，g（svi，svj）＜TS｝［11］。

2.2 基于GPU的并行Mean Shift

記S上顯著特征點(diǎn)集合C中特征顯著點(diǎn)的數(shù)目為NPCs，顯著特征點(diǎn)的坐標(biāo)存放在CPU數(shù)組SPC中；S上面片的標(biāo)志位存放在CPU數(shù)組sign中；函數(shù)gsingle將CPU數(shù)組SPC和sign分別轉(zhuǎn)換為GPU類型的矩陣gSPC和gsign。GPU的并行循環(huán)gfor執(zhí)行mean Shift算法，將模型S上的面片分類到各顯著特征頂點(diǎn)的集合中，從而完成分類。算法偽代碼描述如下：

如圖2所示，本節(jié)首先計(jì)算模型顯著特征點(diǎn)的位置和數(shù)目（如圖2（b）），然后分別從各個(gè)顯著特征點(diǎn)并發(fā)執(zhí)行Mean Shift，實(shí)現(xiàn)分類（如圖2（c））。與串行的 Mean Shift算法（圖1）不同，本節(jié)分類過程中，初始球心即為多顯著特征點(diǎn)，多個(gè)球分別從各自所在的顯著特征點(diǎn)并發(fā)執(zhí)行分類。

圖2 Mean Shift對(duì)面片的并行分類過程

上述對(duì)三角網(wǎng)格上的面片集合F分類的過程較為粗糙，兩類面片集合之間的分割邊界往往有明顯的鋸齒，分割邊界也缺乏明確的幾何意義。本文基于文獻(xiàn)［12］的后處理方法對(duì)分類邊界進(jìn)行后處理，得到了有意義的分割結(jié)果。

3 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)環(huán)境為Intel（R）Celeron（R）CPU 2.66GHZ，1.5GB內(nèi)存空間，顯示處理器為擁有128個(gè)流處理器Geforce GTS250，編程環(huán)境為C＋＋和Matlab。本文實(shí)驗(yàn)數(shù)據(jù)來自Princeton大學(xué)的三維分割Benchmark數(shù)據(jù)庫(kù)，該數(shù)據(jù)庫(kù)共提供了19類380個(gè)三維網(wǎng)格模型的手工分割結(jié)果、以及其他各種算法完成的自動(dòng)分割結(jié)果［13］。

圖3是本文實(shí)驗(yàn)結(jié)果與其他相關(guān)算法的比較［13］，在分割份數(shù)相同的前提下，本文工作的分割邊界和整體分割效果比較理想。與Norm Cuts算法相比，對(duì)于Benchmark數(shù)據(jù)庫(kù)的模型30、165、208，本文工作的實(shí)驗(yàn)結(jié)果較好，模型22、379的分割效果相近，模型101、128中Norm Cuts算法的分割效果比本文實(shí)驗(yàn)結(jié)果好。與Rand Cuts算法比較，對(duì)于Benchmark數(shù)據(jù)庫(kù)的模型101、208、221、379，本文分割效果較好。表1為本文算法在CPU上串行實(shí)現(xiàn)與在GPU上并行實(shí)現(xiàn)所需時(shí)間的對(duì)比，由表1中的加速比可以看出，本文基于GPU算法的實(shí)驗(yàn)速度明顯得到提高，而且與模型的數(shù)據(jù)規(guī)模、分割份數(shù)有關(guān)，分割份數(shù)越多，實(shí)驗(yàn)速度越快。

圖3 本文工作與其他分割算法對(duì)比

表1 GPU／CPU計(jì)算效率對(duì)比

4 結(jié)束語(yǔ)

本文基于Mean Shift算法的基本理論，實(shí)現(xiàn)了基于三維網(wǎng)格模型多個(gè)顯著特征點(diǎn)的并行快速分割算法，得到了較為有意義的分割結(jié)果，并分析對(duì)比了CPU／GPU的計(jì)算效率，與基于CPU的串行Mean Shift分割相比，基于GPU的并行分割效率有所提高，與同類工作相比，本文算法的分割效果較好。不足之處在于，本文算法僅適用于分支形狀特征不緊湊的模型，在處理分支緊湊的三維模型時(shí)分割效果不理想；另外本文對(duì)GPU與CPU間數(shù)據(jù)交換的效率沒有展開研究，后續(xù)工作將考慮改進(jìn)本文算法，提高在分支特征緊湊模型的分割效果，并在改善GPU和CPU之間的數(shù)據(jù)交換效率上，以期進(jìn)一步提高減速比。

［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跟蹤算法中核函數(shù)窗寬的自動(dòng)選?。跩］.軟件學(xué)報(bào)，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）.［云廷進(jìn)，郭永彩，高潮.基于粒子Mean Shift遷移的紅外人體目標(biāo)跟蹤算法［J］.計(jì)算機(jī)學(xué)報(bào)，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）.［湯楊，潘志庚，湯敏，等.基于分級(jí)mean shift的圖像分割算法［J］.計(jì)算機(jī)研究與發(fā)展，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ī)游走圖像分割算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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的交互式體數(shù)據(jù)切割［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào)，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）.［文志強(qiáng)，蔡自興.Mean shift算法的收斂性分析［J］.軟件學(xué)報(bào)，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.