基于頂點(diǎn)局部特征度的網(wǎng)格模型分割算法

賈流洋+莊澤民

摘 要：網(wǎng)格模型的簡(jiǎn)化要兼顧保持細(xì)節(jié)特征和快速這兩個(gè)基本原則，而對(duì)網(wǎng)格模型進(jìn)行分割可以有效提高模型簡(jiǎn)化效率。提出了一種基于頂點(diǎn)局部特征度的網(wǎng)格模型分割算法。分割時(shí)，網(wǎng)格模型要求分割成大小適中、密度差異相對(duì)明顯的連續(xù)區(qū)域，區(qū)域邊緣平滑，且所有三角形均屬于某個(gè)區(qū)域。通過引入頂點(diǎn)局部特征度的概念對(duì)區(qū)域生長(zhǎng)算法進(jìn)行了改進(jìn)。

關(guān)鍵詞關(guān)鍵詞：網(wǎng)格模型；頂點(diǎn)局部特征度；區(qū)域分割；區(qū)域生長(zhǎng)

DOIDOI：10.11907/rjdk.161477

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A ：1672-7800（2016）008-0021-02

0 引言

所謂網(wǎng)格模型區(qū)域分割，就是對(duì)網(wǎng)格模型按照拓?fù)涮卣骰蛘邘缀翁卣鬟M(jìn)行分割，獲得一組有一定外觀意義、若干相互連通的子網(wǎng)格的操作，包括區(qū)域生長(zhǎng)法、層次聚類法和迭代聚類法等。

區(qū)域生長(zhǎng)法可以生成滿足網(wǎng)格某一特征的區(qū)域，實(shí)現(xiàn)模型簡(jiǎn)化的目的。本文研究了一種改進(jìn)的區(qū)域生長(zhǎng)算法，首先提出了頂點(diǎn)的局部特征度概念，采用一種簡(jiǎn)單的計(jì)算方法近似估值頂點(diǎn)曲率，設(shè)定頂點(diǎn)局部特征度的閾值作為生長(zhǎng)條件對(duì)不平滑區(qū)域進(jìn)行平滑處理。

1 頂點(diǎn)局部特征度

對(duì)于大多數(shù)三維網(wǎng)格模型來說，不同細(xì)節(jié)部位具有不同的分辨率，因而其復(fù)雜程度也是不同的。例如，模型中的棱邊、凹痕、尖端、褶皺等關(guān)鍵區(qū)域的曲率較大，其它區(qū)域的曲率相對(duì)較小。常見的三維網(wǎng)格模型是由點(diǎn)、邊、面分段組合而成的線性曲面，無(wú)法用傳統(tǒng)的二次求導(dǎo)方法來計(jì)算其曲率，只能人為定義求取某點(diǎn)處曲率的近似估值。本文采用相對(duì)簡(jiǎn)便的方法計(jì)算頂點(diǎn)的局部特征度，作為該點(diǎn)曲率的近似估值來反映網(wǎng)格模型某點(diǎn)位置的不平整程度。在不增加計(jì)算復(fù)雜度的前提下，本文將頂點(diǎn)的局部特征度定義如下：

2 區(qū)域預(yù)分割

網(wǎng)格模型的區(qū)域分割要服務(wù)于三角形網(wǎng)格模型簡(jiǎn)化需要：首先分割區(qū)域比較大（也不宜過大）， 太小的區(qū)域很難控制簡(jiǎn)化過程，太大的區(qū)域使得分割意義大打折扣；分割區(qū)域的邊緣不平滑也給模型的簡(jiǎn)化處理帶來麻煩， 所以三角形網(wǎng)模型的區(qū)域分割遵從以下原則[5]：①將網(wǎng)格模型盡可能分割成大小適中且連續(xù)的區(qū)域；②各個(gè)區(qū)域的三角形網(wǎng)格稠密程度區(qū)分明顯；③分割區(qū)域的邊緣平滑；④不存在任何三角形不屬于任何區(qū)域問題。

本文采用區(qū)域生長(zhǎng)法進(jìn)行區(qū)域擴(kuò)展以便分割出連續(xù)區(qū)域。采用區(qū)域生長(zhǎng)法進(jìn)行分割要處理好3個(gè)問題：①如何選取種子；②如何設(shè)定生長(zhǎng)準(zhǔn)則；③如何設(shè)定終止條件。這3個(gè)問題處理不好會(huì)直接影響到區(qū)域生長(zhǎng)效果，進(jìn)而影響模型簡(jiǎn)化質(zhì)量。

如何選擇種子是區(qū)域生長(zhǎng)的關(guān)鍵。三角網(wǎng)格模型可以采用頂點(diǎn)、邊或三角形作為種子生長(zhǎng)，本文著重研究頂點(diǎn)作為種子的情況。如圖1（a）所示，頂點(diǎn)P1是區(qū)域中正在生長(zhǎng)的種子頂點(diǎn)，那么凡是以P1為頂點(diǎn)的三角形都是生長(zhǎng)區(qū)域的一部分。然后判斷任意一個(gè)與該頂點(diǎn)P1相鄰的頂點(diǎn)Pi是否滿足生長(zhǎng)準(zhǔn)則條件。若頂點(diǎn)Pi 滿足生長(zhǎng)準(zhǔn)則條件， 則將以Pi為頂點(diǎn)的生長(zhǎng)區(qū)域擴(kuò)展為區(qū)域生長(zhǎng)的一部分， 如圖1（b）所示。

初始種子的選擇決定區(qū)域生長(zhǎng)的形狀，本文采用的方法是：重復(fù)選取沒有被分割區(qū)域具有頂點(diǎn)的局部特征度極大值的頂點(diǎn)作為初始種子。這樣可將所有棱邊、凹痕、尖端、褶皺等區(qū)域都按照頂點(diǎn)的局部特征度大小先后進(jìn)入擴(kuò)展區(qū)域，以減少這些區(qū)域出現(xiàn)在分割邊緣。

生長(zhǎng)準(zhǔn)則的選擇會(huì)影響區(qū)域生長(zhǎng)趨勢(shì)，為了對(duì)網(wǎng)格模型的三角形疏密程度進(jìn)行區(qū)域劃分，本文采用頂點(diǎn)局部特征度作為區(qū)域生長(zhǎng)的判定條件，對(duì)于滿足判定條件的進(jìn)行區(qū)域生長(zhǎng)，不滿足則終止生長(zhǎng)。若頂點(diǎn)P1和頂點(diǎn) Pi的局部特征度滿足生長(zhǎng)某個(gè)閾值， 便可將Pi 的相鄰三角形擴(kuò)展到區(qū)域中。生長(zhǎng)準(zhǔn)則規(guī)定為：

其中， Ri、 R1分別表示頂點(diǎn)Ri和R1的局部特征度， RVthod是生長(zhǎng)閾值， 它的大小選擇根據(jù)實(shí)際情況而定。對(duì)于平滑區(qū)域，RVthod可選擇較小值；對(duì)于局部特征度較大的區(qū)域，RVthod可適度增大。

3 區(qū)域平滑處理

經(jīng)過預(yù)分割后的區(qū)域存在不連通及區(qū)域邊緣不平滑，會(huì)給后續(xù)簡(jiǎn)化帶來很大麻煩，所以在預(yù)分割后，需要進(jìn)行平滑處理，本文采用區(qū)域填充法處理。邊緣不平滑區(qū)域包含的頂點(diǎn)所在三角形數(shù)目和該頂點(diǎn)所在三角形數(shù)目的比大于1/2，我們將該頂點(diǎn)所在三角形全部填充到這個(gè)邊緣不平滑區(qū)域，處理步驟如下：

首先，統(tǒng)計(jì)頂點(diǎn)vi所在三角形數(shù)目N，統(tǒng)計(jì)這些三角形中屬于區(qū)域As的數(shù)目Ns；然后判斷：如果頂點(diǎn)vi滿足NsN>1/2，就將vi所在的N個(gè)三角形全部填充到區(qū)域As中。最后判斷區(qū)域As是否連通，如果不連通就重新執(zhí)行該操作；如果連通，則操作結(jié)束。

4 基于頂點(diǎn)的局部特征度網(wǎng)格分割算法過程

（1）將所有頂點(diǎn)加入頂點(diǎn)數(shù)組Q，并計(jì)算網(wǎng)格模型每個(gè)頂點(diǎn)的局部特征度值。

（2）遍歷數(shù)組Q， 選擇具有局部特征度極大值的頂點(diǎn)作為初始種子，即若頂點(diǎn)v滿足：對(duì)vn∈Nv有∑vi∈S且v≠viUv>∑vi∈SUvn，則v為區(qū)域生長(zhǎng)初始種子，將頂點(diǎn)v保存起來以備后續(xù)傳輸使用。從數(shù)組Q中刪除頂點(diǎn)v，將區(qū)域a加入到區(qū)域數(shù)組A。

（3）選擇合適的頂點(diǎn)局部特征度閾值。（4）從初始種子開始，向滿足生長(zhǎng)準(zhǔn)側(cè)的區(qū)域進(jìn)行擴(kuò)張，每擴(kuò)展一個(gè)頂點(diǎn)，從數(shù)組Q中刪除該頂點(diǎn)。如果數(shù)組Q中還有頂點(diǎn)未被擴(kuò)展， 則轉(zhuǎn)步驟（2），否則繼續(xù)。（5）如果數(shù)組A為空，算法結(jié)束。否則遍歷區(qū)域數(shù)組A找到不連通區(qū)域As，從數(shù)組A中刪除As。

（6）統(tǒng)計(jì)頂點(diǎn)vi所在三角形數(shù)目N，統(tǒng)計(jì)這些三角形中屬于區(qū)域As的數(shù)目Ns。（7）如果頂點(diǎn)vi滿足：NsN>1/2（5）

則將頂點(diǎn)vi所在的所有三角形都填充到區(qū)域As之中。（8）如果區(qū)域As已經(jīng)連通， 并且邊緣已經(jīng)達(dá)到平滑程度， 則轉(zhuǎn)步驟（5），否則， 轉(zhuǎn)步驟（6）。

5 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)環(huán)境：CPU Intel（R） Core（TM） 2 Duo，內(nèi)存 2G，代碼在Windows 7系統(tǒng)VS2013和OpenGL下編寫完成。本算法部分實(shí)驗(yàn)結(jié)果如圖2、圖3所示。

從實(shí)驗(yàn)結(jié)果可以看出，模型的分割區(qū)域比較好地保留了局部細(xì)節(jié)特征，而且分割區(qū)域中不存在不連通區(qū)域，區(qū)域邊緣基本平滑，證明了本文算法的有效性。

6 結(jié)語(yǔ)

本文提出了一種基于頂點(diǎn)的局部特征度區(qū)域生長(zhǎng)算法，算法通過對(duì)頂點(diǎn)的局部特征度閾值設(shè)定，作為區(qū)域生長(zhǎng)準(zhǔn)則的判定條件，決定區(qū)域生長(zhǎng)中所需要的區(qū)域形狀，對(duì)網(wǎng)格模型進(jìn)行分割，并對(duì)預(yù)分割后產(chǎn)生的不平滑邊界采用區(qū)域填充法進(jìn)行處理。最后獲得大小適中、密度差異相對(duì)明顯的連續(xù)區(qū)域。區(qū)域邊緣平滑，且所有三角形均屬于某個(gè)區(qū)域。

參考文獻(xiàn)：

[1] 孫曉鵬，李華.三維網(wǎng)格模型的分割及應(yīng)用技術(shù)綜述[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17 （8 ）：1647-1655.

[2] MANGAN A， WHITAKER R. Partitioning 3D surface watershed segmentation[J].IEEE Transactions on Vieualization and Computer Graphics，1999，5（4）：308-321.

[3] GARLAND M.WILLMOTT A， HECKBERT P. Hierarchical face clustering on polygonal surfaces[C].Proceedings of ACM Symposium on Interactive 3D Graphics，New York，2001.

[4] LLOYD S. Least square quantization in PCM[J] .IEEE Transactions on Information Theory，1982，28（2）：129-137.

[5] 全紅艷，張?zhí)镂?，董宇?一種基于區(qū)域分割的幾何模型簡(jiǎn)化方法[J].計(jì)算機(jī)學(xué)報(bào)，2006，29（10）： 1834-1842.

（責(zé)任編輯：杜能鋼）