三角網(wǎng)格分割中種子點的優(yōu)化采樣算法

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

(1.合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院,安徽 合肥 230601; 2.工業(yè)安全與應(yīng)急技術(shù)安徽省重點實驗室,安徽 合肥 230601)

0 引 言

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

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

1 相關(guān)工作

1.1 研究現(xiàn)狀

原始采集到的三角網(wǎng)格模型往往缺少結(jié)構(gòu)特征和語義信息,使計算機(jī)難以對其進(jìn)行更高級的識別處理工作,由此引申出大量關(guān)于三角網(wǎng)格模型處理的工作。

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

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

當(dāng)分割的對象是較精細(xì)的模型或者分割以網(wǎng)格重建為目的時,不能忽略模型細(xì)節(jié)。文獻(xiàn)[10]將網(wǎng)格數(shù)據(jù)劃分為多個相同的單元,依據(jù)其密度分布進(jìn)行劃分,只有當(dāng)密度不小于設(shè)定閾值才進(jìn)行擴(kuò)展；依據(jù)密度閾值的設(shè)定,可以控制劃分粒度、展示模型細(xì)節(jié)。

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

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

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

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

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

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

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

(1)

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

2 網(wǎng)格分割

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

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

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

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

本文基于三角網(wǎng)格模型,以VSA的算法思想為基礎(chǔ),提出一種種子點的優(yōu)化采樣算法,可以提取網(wǎng)格模型中近似合理的種子點個數(shù)及位置。

2.2 網(wǎng)格劃分誤差分析

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

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

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

圖2 過度分割現(xiàn)象

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

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

圖3 稀疏分割現(xiàn)象和單獨提取的稀疏分割部分

稀疏分割現(xiàn)象會導(dǎo)致提取的輪廓線無法包含模型所有的輪廓線,從而導(dǎo)致根據(jù)輪廓線進(jìn)行模型重建的結(jié)果出現(xiàn)錯誤。

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

圖4 邊界誤差現(xiàn)象

邊界誤差現(xiàn)象會導(dǎo)致最終劃分結(jié)果出現(xiàn)錯誤,提取的輪廓線不夠平滑。

3 算法流程

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

圖5 處理流程

3.1 類間合并

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

圖6 類間合并處理效果

3.2 類內(nèi)再聚類

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

圖7 類內(nèi)再聚類處理效果

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

3.3 邊界再劃分

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

圖8 邊界再劃分處理效果

3.4 更新種子點

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

3.5 模型重建

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

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

圖9 不同種子點對應(yīng)重建效果對比

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

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

4 實 驗

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

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

4.1 模型重建工具

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

4.2 重建模型對比

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

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

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

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

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

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

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

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

5 結(jié) 論

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

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