三維網格的Mean Shift并行分割算法

孫曉鵬，榮 丹

（1.遼寧師范大學 計算機與信息技術學院，遼寧 大連116029；2.大連大學 遼寧省先進設計與智能計算省部共建教育部重點實驗室，遼寧 大連116622）

0 引 言

近年來，隨著三維激光掃描建模技術的成熟，三維網格模型分割的研究已經廣泛應用到數字幾何處理的許多領域中，如動畫變形、紋理合成、參數化、局部特征提取等，并已成為數字幾何處理研究領域的熱點問題?，F有的三維網格分割算法多數源自圖像分割算法，如分水嶺算法、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跟蹤算法中核函數窗寬的自動選?。跩］.軟件學報，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.