三角網格分割中種子點的優化采樣算法

徐源廷, 曹 力,2, 賈 偉,2

(1.合肥工業大學 計算機與信息學院,安徽 合肥 230601; 2.工業安全與應急技術安徽省重點實驗室,安徽 合肥 230601)

0 引 言

近年來,隨著3D打印、三維掃描、基于圖像建模等技術的發展,許多三維數據采集設備應運而生,隨之產生大量三維幾何數據,將這些數據進行去噪、三角化、簡化處理后才可以得到供使用的模型。將采集到的模型進行必要的三角網格分割,可以使用戶更容易對這些模型進行曲面壓縮、紋理映射、模型檢索、網格重構、參數化等操作。對三維幾何模型的網格劃分,是提取模型輪廓線的一個常用辦法。將三角網格模型分割為多個面片,其面片的邊界線可作為模型的輪廓線。以VSA(variational shape approximation)[1]為代表的三角網格模型聚類分割算法是一種基于k-means的網格分割方式,常被用于面片劃分、輪廓線提取等工作，但由于它采取隨機的方式生成種子點,從而導致劃分結果存在誤差,提取的輪廓線不夠精細。

本文提出一種三角網格分割中種子點的優化采樣算法,可以通過類內再聚類、類間合并以及邊界再劃分的步驟優化三角網格分塊結果,給出建議的初始種子點個數及位置。根據對多個模型進行試驗表明,利用本文方法給出的種子點可以提取優質的輪廓線,該輪廓線重建模型效果更好。

1 相關工作

1.1 研究現狀

原始采集到的三角網格模型往往缺少結構特征和語義信息,使計算機難以對其進行更高級的識別處理工作,由此引申出大量關于三角網格模型處理的工作。

三角網格分割[2]可以解決諸如紋理映射、模型重建、網格動畫、參數化等問題[3],一直以來，很多學者提出不同研究方法[4-5]，文獻[6-7]總結了一些網格分割算法,并提出改進途徑。

針對分割目的或對象的不同,分割算法的側重點也有所差別。當分割的對象是尺度較大的模型或者分割目的是為了紋理映射時,網格分割算法更加側重整體分割,即分割為若干大的區域,細節的展示由紋理完成,因此分割過程中可以一定程度上忽略部分細節；例如基于分水嶺的三角網格劃分方法[8],這類方法首先根據幾何信息確定盆地和分水嶺,然后采用浸水方式或降水方式將模型分割為以分水嶺為邊界的集水盆地區域。文獻[9]提出一種基于特征檢測和核心提取的網格分割算法,該算法首先獲取到網格的特征信息,如特征邊、特征點,然后根據這些特征信息對網格進行劃分。該類方法適用于一些較大的區域或部件,且略去了部分模型細節。

當分割的對象是較精細的模型或者分割以網格重建為目的時,不能忽略模型細節。文獻[10]將網格數據劃分為多個相同的單元,依據其密度分布進行劃分,只有當密度不小于設定閾值才進行擴展；依據密度閾值的設定,可以控制劃分粒度、展示模型細節。

另外基于可變網格,文獻[11]提出一種動態增量的聚類算法,即當新的數據到來時,判斷是否屬于現有劃分區域；若是，則加入,否則新建一個類。該方法避免了k-means算法需初始設定聚類數的問題,但無法在一開始提供推薦種子點個數或位置。還有一些網格聚類分割工作[12-14],針對應用場景不同、采用策略不同均提出自己的優化算法。

除采用聚類分割以外,文獻[15]采用模型表面張量投票的方法,可以更加快速地對網格進行分割。文獻[16]提出一種三角網格分割算法，應用在CAD方面;另外還有一些自適應算法[17-18]和約束關系[19]的網格模型分割。對于網格分割得到的區域邊界,可以作為網格模型的輪廓線。

輪廓線提取對于三角網格模型的處理是至關重要的。文獻[20]提出首先提取模型中角點,再依據角點間的某種拓撲關系,提取模型輪廓線;文獻[21-22]提出一種網格頂點法向投票張量理論,進一步將頂點分類為角點、面點、尖銳邊點;文獻[23]在特征線的基礎上,另外提取曲率方向一致、更加規整緊湊的曲線網格,得到的輪廓線有更好的重建效果。

關于模型重建的工作,文獻[24]通過輸入給定曲線或曲面上的采樣點,通過直線或三角形連接這些樣本得到多邊形網格,以此重建三維模型;文獻[25]將模型輪廓線信息作為輸入,在輪廓線間穿插特定曲率曲線,使其平滑過渡輪廓線間曲率差距,自動補全網格信息,重建三維網格模型;文獻[26]用基于L0范數定義法向量場的優化目標函數,使用變分逼近的方式對模型進行分割,擬合區域的B樣條曲面進行合并覆蓋,得到重建后模型的似可展曲面,最后再對可展曲面進行擬合優化得到最終的重建結果，該方法對帶有噪聲的模型也能有較好的重建效果。

1.2 變分形狀逼近(VSA)算法介紹

變分形狀逼近算法是最具代表性的網格模型聚類分割算法[1]是一種基于k-means的迭代聚類的三角網格模型分割算法,并廣泛應用于輪廓線或特征提取的工作中。該方法通過形狀代理代表帶擴展區域,通過計算帶擴展區域邊界三角形到對應形狀代理的距離,進行區域擴展,并通過不斷迭代直到收斂,最終得到劃分結果。文獻[27-29]在其工作基礎上進行改進,分別采用不同的形狀代理進行擬合,以達到更好的逼近效果。

其中計算三角形與代理之間的距離度量采用L2,1距離,定義為:

(1)

其中:Ri為待擴展區域;Pi為區域代理;n(x)為待擴展區域法向;ni為區域代理法向。以此來刻畫區域代理與區域邊界三角形間的誤差。

2 網格分割

2.1 變分形狀逼近(VSA)不足

變分形狀逼近作為一種基于k-means的迭代聚類算法,種子點的選取尤為重要，種子點的數量直接決定了最終分割的塊數。假設一個模型被劃分為n個區域為最佳,而當種子點選取個數小于n時,會使得原模型中理應被多個區域的部位被劃分為一個區域;當種子點數大于n時,則會出現理應被分為一個區域的部位被分為多個區域。當種子點的位置選取不適當時,可能會陷入局部最優,很難迭代出正確的劃分結果,這種情況下只能重新選取一組新的種子點。不同種子點對VSA分割效果的對比如圖1所示。圖1a、圖1b均為使用VSA方法對Fandisk模型選取不同種子點進行網格分割的效果,可以明顯看出，圖1a的黑色方框中所示部分出現一些分割錯誤,分割效果不如圖1b。

圖1 不同種子點對VSA分割效果對比

由此可見，種子點的選取個數以及位置對于三角網格模型的處理是非常重要的。

本文基于三角網格模型,以VSA的算法思想為基礎,提出一種種子點的優化采樣算法,可以提取網格模型中近似合理的種子點個數及位置。

2.2 網格劃分誤差分析

現有三角網格劃分算法因其自身局限性,難以適用于全部模型,其劃分結果往往存在一定誤差,本文以VSA方法為例,將此類問題產生的誤差分為如下3種。

(1) 過度分割。當在三角網格模型M上選取n個種子進行VSA聚類分割時,因其種子點選取的隨機性,會對劃分結果造成不可預計的錯誤。當2個種子點同處一個平面上時,其采用加權平均法得到代理面法向信息,此時得出的2個代理法向完全相同，導致在迭代完成后將一個平面錯誤分為2個分塊,此時便出現過度劃分的情況如圖2所示。

圖2中黑色方框處即錯誤地將一個平面分為2個區域。

圖2 過度分割現象

過度分割的情況會使輪廓線的數量增多,而這些額外的輪廓線并不包含模型的輪廓特征,從而造成了后續模型重建過程中時間上的浪費。

(2) 稀疏分割。在使用VSA方法進行網格分割過程中,若模型最佳分塊數為n,而種子的初始選取個數小于n,則在劃分的結果中,會出現將本應劃分為多個部分的區域錯誤劃分為一個部分,這種情況稱為稀疏分割現象,如圖3所示。圖3a黑色方框橘色分區部分包含模型多處輪廓線,卻錯誤地將其劃分為一個部分,應進行進一步劃分。

圖3 稀疏分割現象和單獨提取的稀疏分割部分

稀疏分割現象會導致提取的輪廓線無法包含模型所有的輪廓線,從而導致根據輪廓線進行模型重建的結果出現錯誤。

(3) 邊界誤差。因各種網格劃分算法的局限性,對于邊界三角形,對其歸屬分塊的判斷出現錯誤,造成邊界誤差。對于邊界三角形所屬分塊劃分錯誤，如圖4所示。

圖4 邊界誤差現象

邊界誤差現象會導致最終劃分結果出現錯誤,提取的輪廓線不夠平滑。

3 算法流程

本文在VSA方法思想的基礎上,針對以上具體問題,做出一種改進。對以上中提到的過度劃分、稀疏劃分和邊界誤差的現象,分別采用類間合并、類內再聚類以及邊界再劃分的方法進行處理。處理流程圖如圖5所示。

圖5 處理流程

3.1 類間合并

采用VSA方法一步劃分完成后,首先處理由于種子點選取過密而引起的過度劃分現象,對于每個區域分塊,計算其與相鄰區域代理間的L2,1距離,若小于設定閾值(本文為0.02),則說明2個區域十分相似,視為2塊區域出現過度分割現象。將三角面較少的分塊合并到較多的分塊中,并刪除該分塊。類間合并處理后的效果如圖6所示,由于圖2中底部2個分塊代理的L2,1距離趨近于0,將2個部分合并為一個分塊，從而消除過度分割現象。

圖6 類間合并處理效果

3.2 類內再聚類

對于劃分后的每個區域,單獨提取,計算其分塊內所有三角形的單位法向方差；若需要其方差大于設定閾值,則該區域出現稀疏分割現象,需要對該區域進行進一步劃分。類內再聚類處理效果如圖7所示,將圖3b中稀疏分割部分單獨提取并進一步劃分,直至任一區域的三角形法向方差均小于設定閾值。

圖7 類內再聚類處理效果

這里之所以先進行類間合并再進行類內再聚類,主要是因為如果先進行類內再聚類再進行類間合并,那么最后的類間合并可能會導致誤差堆疊,使得一個區域內的單位法向方差重新大于原設定閾值。因此這里先進行類間合并再進行類內再劃分。

3.3 邊界再劃分

為保證最終劃分結果邊界平滑無誤差,對于區域邊界三角形,判斷其與所屬劃分區域代理面的L2,1距離,當大于設定值時,視為出現邊界誤差。對該三角面進行邊界再劃分處理,計算其與相鄰區域代理的差值,將其劃分到差值最小的區域中去。邊界再劃分處理效果如圖8所示,將圖4中黑色方框中三角形再劃分,得到較好效果。

圖8 邊界再劃分處理效果

3.4 更新種子點

將最終劃分結果,對每個區域計算其平均法向及平均重心作為區域代理,找出與每個區域代理距離最為相近的三角形,作為新的種子點。

3.5 模型重建

利用上一步提取的種子點個數y及位置,重新進行三角網格劃分,提取模型輪廓線并進行模型重建,對比重建模型與原模型間的差距。本文采用模型間Hausdorff距離[30]來表示模型間的差距,同時對比選取不同種子點個數時重建出的模型與原模型的Hausdorff距離。

選取不同種子點時,重建模型之間的效果對比如圖9所示。利用本文算法推薦種子點個數為18。不難看出當種子點個數小于18時,可以明顯觀察到重建誤差；當種子點個數大于18時,對重建模型的質量影響不大。

圖9 不同種子點對應重建效果對比

為客觀展示重建差距,不同種子點重建模型與原模型Hausdorff距離對比如圖10所示。從圖10可以看出，當種子點個數不斷增加時,重建模型與原模型之間的Hausdorff距離呈下降趨勢；而當種子個數為18時,重建模型與原模型之間的Hausdorff距離已基本收斂,不再變化。

圖10 不同種子點重建模型與原模型Hausdorff距離對比

4 實 驗

本文借鑒VSA方法思想,將網格模型分割結果進一步進行類間合并、類內再聚類以及邊界再劃分,優化三角網格模型的聚類劃分結果,從而提取出推薦模型種子點。利用該種子點可以提取優質模型輪廓線,從而重建出的模型更加貼近原模型。

所有對比實驗均在配置為Intel 1.90 GHz(2處理器)、8 GB內存、GTX 1060 3 GB顯卡的圖形工作站上完成。

4.1 模型重建工具

對于最終劃分計算得到的模型輪廓信息,本文模型重建采用文獻[13]的方法。該方法通過輸入模型輪廓線信息,可以在所給出輪廓線之間平滑地插入特定曲率曲線,使得模型表面曲率變化與給出的輪廓線自動對齊,最小化不好的曲率變化。自動構建模型表面三角網格,使模型曲面上的主曲率方向與輪廓線所表示的光滑流場一致性保持最大，最終輸出off格式的模型文件。經過對比,該方法具有較好的模型重建效果。

4.2 重建模型對比

本文分別采用raised、joint、bird以及gear 4個模型,選取不同種子點數目進行重建模型對比實驗，結果如圖11～圖14所示,其中每幅圖中的圖b為采用本文方法計算出的種子點數目進行模型重建所得效果；圖a為種子點數目小于計算值時的重建效果,圖c為種子點數目大于計算值時的重建效果。

可以看出,當種子點數小于計算值時,raised模型和joint模型均發生了一定程度的扭曲變形,bird模型和gear模型則出現了明顯的重建錯誤,bird模型的左側翅膀部分下截面凸出到上截面上,gear模型的中間齒輪部分出現空洞。而當種子點數大于計算值時,可以看出與中間結果相差不大,只是增加了部分可有可無的輪廓線而已,而這些多出的輪廓線,對模型描述的作用并不大,反而會帶來不必要的資源消耗。

圖11 raised模型種子點不同時重建效果

圖12 joint模型種子點不同時重建效果

圖13 bird模型種子點不同時重建效果

圖14 gear模型種子點不同時重建效果

選取種子點數目見表1所列。由表1中對比重建模型與對應重建模型的具體誤差數據可以進一步佐證本文觀點。其中SN(seed number)代表種子點數目,HD(Hausdorff distance)代表對比原模型的Hausdorff距離。數據列(1)、(2)、(3)分別代表種子點數目小于、等于、大于計算值時,對比原模型的重建誤差。可以看出,由列(1)到列(2)誤差降低明顯,由列(2)到列(3)誤差降低不大。

表1 不同種子點數目與原模型誤差對比

5 結 論

本文針對三角網格分割中常見的過度劃分、稀疏分割、邊界誤差三類問題,進行檢測,并分別采用類間合并、類內再聚類、邊界再劃分的方式逐一進行處理,最小化區域內三角形法向方差。從優化后的劃分區域中以加權平均的方式選取推薦種子點。

通過實驗表明,在種子點選取個數遞增的情況下,采用提取輪廓線并進行模型重建的方式,其結果與原模型之間的Hausdorff距離呈下降趨勢,逐漸趨于曲線收斂。采用本文方法提取的種子點個數可以接近收斂處的種子點個數。進行輪廓提取模型重建時,可以保證在種子點個數盡可能少的情況下,保證重建模型質量,使其與原模型之間差距更小,結果更為精確。