綜合曲率約束的在線網格模型分割方法研究

趙云成，王 琳 ，盛步云，趙飛宇

1.武漢理工大學 機電工程學院，武漢 430070

2.湖北省數字制造重點實驗室，武漢 430070

1 引言

近年來，隨著Web 技術的發展，計算機輔助設計與數字幾何處理均有向Web環境發展的趨勢?！叭S掃描+在線重構”的逆向建模方式，憑借低門檻和便捷性，逐漸成為在線三維建模軟件的主要建模方式。將三維掃描儀掃描重構的三角網格模型轉化為可參數化設計的實體模型，需要對無法編輯的三角網格模型進行分割處理，并分別將每塊分割區域重構為可參數化驅動的基本實體特征[1]。從完整的三角網格模型中劃分和識別特征區域的研究，有助于實現基于三維掃描的逆向實體建模，提升產品逆向設計效率，對大眾參與的計算機輔助設計領域發展具有重要意義[2]。在Web環境下實現網格分割，不僅要求保證三角網格模型分割的準確性，而且須確保分割算法具備較低的計算復雜度以適應在線高并發環境，從而滿足Web 環境對數字幾何處理高效性、實時性的要求。

國內外學者對應用于不同幾何處理領域的三維模型分割做了大量的研究，并提出了一系列網格模型分割方法。根據分割方式的不同，模型分割大致可分為三類：聚類分析法[3-4]、區域增長法[5]和邊界檢測法[6]。基于聚類的分割方法主要通過聚類算法，對網格模型中具有相同幾何信號的點和面片進行迭代聚類，常用于模型塊分割。文獻[7]將三角網格模型向譜空間映射，進而通過K-means聚類實現分割。文獻[8]基于最小主曲率以及特征向量對掃描后自由曲面模型進行塊分割，并用于牙齒掃描模型的語義分割。文獻[9]在GPU上基于高斯曲率和平均曲率對面片進行頂點聚類，實現了GPU 環境下網格模型的分割。這類算法基于全局信號的迭代聚類，分割效率較低，且分割結果難以預測，不滿足Web環境下幾何處理應具備較低計算復雜度的要求?；趨^域生長的模型分割方法主要將局部幾何信號作為分割驅動信號，通過選取種子點和相應的生長規則將滿足條件點和面片合并在同一區域中。文獻[10]通過計算測地距離選取種子點，基于凹凸信號合并相似區域，實現對三角網格模型的面分割。這類算法雖然具有較高的分割效率，但是區域增長易受到驅動信號的影響，且容易存在過分割等現象。另一類算法則是基于邊界的方法，通過在模型上構造符合分割特點的分割線，并以分割線為邊界，將模型分割為多個獨立的特征面。文獻[11]提出了基于分割邊界學習的分割線提取算法，該方法通過大量的網格模型人工分割結果來訓練分類器，進而獲取網格模型的分割邊界。該類方法雖然能夠獲得較好的分割結果，但是在前期訓練需要繁瑣的數據采集，因而算法總體效率不高，不適用于Web環境下高效分割網格模型。

根據以上分析，本文提出一種基于凹特征區域分割線提取的在線三角網格模型分割方法。首先采用微分幾何方法對模型各頂點的離散曲率進行計算，然后根據模型的曲率特性設定閾值來計算判斷模型的凹特征區域，在此凹特征區域提取出分割線并進行閉合和光順處理，最后基于分割線將模型分割成不同的區域。實驗表明，本文方法能夠實現Web環境下高效快速準確的分割三維模型，且分割的結果具有可預測性，適用于工程實踐，便于后期參數化重建研究。

2 三角網格模型分割流程

傳統的基于曲率的網格分割方法往往依據單個曲率特征來實現網格模型的分割[12]?；蚧谇市盘柕垲悾蚋鶕式Y合特征信號進行輪廓特征提取。同樣是基于曲率分割，不同的方法運用不同的曲率特征，文獻[13]算法利用主曲率，文獻[14]算法利用高斯曲率與平均曲率，有的方法基于最小值準則分割模型，有的則基于平坦性原則利用二次曲面（如可展曲面）控制分割過程，還有的算法利用語義或人的視覺原理指導網格分割。

本文將平坦性規則與最小值準則結合起來，在滿足Web環境下計算復雜度較低的要求的情況下，綜合高斯曲率、平均曲率以及最小主曲率，通過二次提取特征點方法來提取網格模型特征區域，避免了多次全局信號計算。進而在凹特征區域中獲取優化分割邊界線，實現Web環境下網格模型的高效準確分割。

如圖1 所示，本文方法的分割大致流程為：首先根據離散曲率公式計算網格模型各頂點的離散曲率特性；其次根據平坦性規則，利用高斯曲率與平均曲率提取模型中凹區域，在凹區域中利用最小曲率閾值提取凹特征區域，并由此特征區域提取和優化形成閉合分割線，實現對網格模型的塊分割。

2.1 網格模型離散曲率估計

在逆向工程中，包含凹形狀的特征區域是基于特征建模等操作的重要考慮部分，而高斯曲率KG和平均曲率KH是判斷網格模型頂點凸凹特性的重要指標。對PSB中人工分割結果分析可知，分割邊界的頂點一般在負的最小主曲率處。因此在通過高斯曲率KG和平均曲率KH確定模型凹區域之后，定義最小曲率閾值KT。將低于最小曲率閾值KT的邊界點視為特征點，提取模型凹特征點集，作為網格劃分邊界線的基礎。

目前離散曲率估計方法有很多。其中文獻[15]提出的Voronoi圖方法比較靈活和準確地估算了任意三角網格模型頂點的曲率?？紤]Web 環境下計算低復雜度的要求，在滿足曲率估算盡量準確的情況下，本文采用頂點的一環鄰域進行計算，得到三角網格模型頂點vi的平均曲率計算公式：

式中，φk、ψk分別為邊的對角，如圖2（a）所示。Amix表示頂點vi鄰域內三角面片對應的區域面積，其公式為：

圖1 網格模型分割方法總體流程圖

其中，Svi表示頂點vi鄰域Voronoi圖劃分區域（灰色部分）的面積[15]，由于vi鄰域三角形夾角θk大小不同，面積取值規則不同，如圖2（b）、（c），定義三角面片T的三個頂點vi、vj、vj+1，定義邊的夾角為φ，i邊的夾角為ψ。不同角度取值規則如下：i

根據微分幾何中GaussBonnet 定理[16]，可以通過下列公式得到高斯曲率：

圖2 網格頂點離散曲率估計示意圖

式中，KG(vi)為頂點vi的高斯曲率，θk表示頂點vi與其鄰域第k個三角面片的夾角，Amix表示頂點vi鄰域內三角面片對應的區域面積。

頂點vi處的主曲率可由離散曲率和平均曲率計算得到：

式中，K1(vi)和K2(vi)分別為最大、最小主曲率。

2.2 三維模型凹特征區域提取

頂點的高斯曲率和平均曲率反映了頂點的凹凸性，由于模型可能存在噪點，僅僅根據離散頂點本身的曲率特性無法判斷區域的凹凸性。本文通過微分幾何特性綜合各頂點鄰域的高斯曲率與平均曲率來判斷模型凹區域，并根據歸一化最小主曲率閾值在優化后的凹區域中提取出模型的凹特征區域點集。首先根據頂點鄰域的高斯曲率和平均曲率篩選出凹點集區域，在凹區域劃分中，噪點存在可能導致出現細碎劃分，影響凹特征點集提取。噪點存在處往往區域較小且連通性較差，因而本文根據鄰域面積和曲率分布狀況優化和刪除頂點數量過少凹點集，在此凹區域中基于最小主曲率篩選出凹特征點集。不同模型的最小主曲率范圍不同，考慮分割邊界盡量在最小主曲率處，本文采用提取凹區域中頂點主曲率較小點集作為凹特征點集。具體步驟如下：

步驟1 計算網格模型各點離散曲率。計算網格模型中各頂點vi的高斯曲率KG和平均曲率KH。

步驟2 凹點集初提取。遍歷每個頂點vi，獲取頂點vi以及頂點vi的一階鄰域各點的離散曲率特性。判斷該點一環鄰域中所有點的高斯曲率KG和平均曲率KH是否滿足KG＜0&&KH＜0，將滿足條件的點加入凹點集中。

步驟3 凹點集區域擴展。計算步驟2 中獲得每個頂點vi一階鄰域頂點在凹點集區域中所形成的凹三角形面積Sconcave與頂點vi一鄰域所有頂點形成面積Sall的比值M，若M＞threshold1，將頂點vi鄰接點加入凹點集區域。

步驟4 凹點集區域刪除。計算步驟3 得到凹點集區域中所有連通分支頂點數量N以及平均高斯曲率KH,將滿足N＜threshold2&&KH＞0 的連通分支刪除，得到最終的凹點集區域。

步驟5 凹特征區域提取。計算凹區域點集中點的最小主曲率K2，通過設定歸一化閾值KT，將凹點集中主曲率較小部分點加入凹特征區域。

如圖3 所示，在凹特征區域的提取過程中，凹點集區域擴展中面積比值M過小易造成點集擴展過多，對區域優化效果不好，在凹點集區域刪除過程中對擴展后頂點數量較少以及高斯曲率較大的凸區域(KH＞0)進行刪除。本文結合實驗測試結果，最終確定threshold1取值0.8，threshold2取值6，凹區域特征提取效果較優。由于初提取的區域最小主曲率分布往往不太一致，因而本文采用歸一化閾值。在設定KT過程中，本文通過對PSB 模型人工分割數據集中眾多相同或相似輪廓進行閾值估計，并結合實驗結果最終設定歸一化閾值KT為0.5，取得較好的區域提取結果。

2.3 分割線獲取和優化方法

2.3.1 初始分割線生成

如圖3Teddy 模型凹特征區域提取所示，特征點在網格邊界附近呈區域分布，不能作為最終的分割邊界，為了獲取精確的分割線，需要在特征點集中區域提取出分割線來。在滿足Web環境低計算復雜度要求條件下，考慮分割線生成盡可能平滑。對于三維空間的凹特征點集，本文提出一種基于球面半徑搜索方法來連接特征點生成初始分割線，在確定初始種子點后，以最大特征邊長為半徑，搜索鄰域內與連接邊夾角最大的特征點，形成分割線。具體步驟如下：

步驟1 移除G中離群點。計算每個特征點vi到其余特征點的平均歐氏距離假定平均歐式距離服從高斯分布，求得的均值μ與方差σ。將分布在±3σ之外的特征點視為離群點并移除。如圖4（a）、（b）所示，紅色離群點被移除。

步驟2 設定初始種子點。選定凹特征點集中兩鄰邊夾角大于135°的點作為初始種子點，加入到組點序列中。如圖4（c）所示，選定vp作為特征線起點。

步驟3 確定搜索半徑R。遍歷凹特征區域中所有的邊，找到長度最大的邊，將最大長度記為Rmax，以vp為球心，以Rmax為半徑確定搜索區域。

步驟4 尋找分割線的連續點。獲取搜索區域的特征點集合，計算球心點vp與特征點組成線和球心點與前一點組成邊的夾角ω，選取夾角最大的點加入到組點序列。如圖4（c）所示，夾角最大，選取v b加入組點序列。

步驟5 獲取所有特征點。球心點移動到下一特征點，重復步驟4，直到遍歷完所有特征點。

步驟6 生成初始分割線。將搜索得到的組點序列進行連接得到初步的分割線。如圖4（d）所示。

圖4 初始分割線生成方法圖

2.3.2 分割線閉合及光順

在初始分割線生成之后，往往存在模型分割線不閉合特征，多為一側具有明顯凹特征，另一側較為平坦或凸起，大致為L 形狀。如圖3 中圈出區域所示Teddy 模型腿部與后臀部連接處較為平整，而軀干與腿部處存在凹特征區域，導致生成的分割線無法確保分割區域的封閉性。本文提出基于射線的邊界線閉合方法，通過捕獲射線與面片的交點獲得分割線形狀，通過修正交點獲取閉合分割線。

步驟1 構造射線。為確保射線由模型內部發出，選擇構成邊界線的質心點vg為射線起點，通過連接vg與端點va、vb構建單位向量es、ee，求得兩向量夾角Φ=arccos(es·ee)，之后構造n條單位夾角為φ的射線 (0＜φ ＜Φ)，分別與模型面片交于{P1,P2,…,Pn}。

步驟2 計算交點Pi。通過建立空間Octree搜索結構，并通過矢量分解判斷射線l與三角面片是否相交。構造射線參數方程，計算射線與三角面片交點Pi。

步驟3 修正交點。鑒于Pi位于三角面片T的內部，為避免網格細分而增加計算復雜度，須對Pi進行修正。如圖5（b）所示，即計算Pi與T三個頂點vi、vj、vk的歐氏距離，選取距離最小的頂點作為修正后的交點vc，表示為：

步驟4 邊界閉合。運用Dijsktra最短路徑算法[17]求得從va到vb并經過所有修正后交點的最短路徑，形成閉合邊界線Lb。

步驟5 分割線光順。采用主動輪廓模型（Snakes）[18]，定義邊界線上頂點的內部能量Eint與外部能量Eext，借助貪心算法[19]，使曲線上的頂點迭代地向局部范圍中能量最小位置偏移，獲得光順分割線。

以圖5為例，通過連接vg與v1、v7確定夾角，發出7條射線分別與不同三角面片交于Pa、Pb、Pc、Pd、Pe、Pf、Pg。計算出交點坐標，Pa、Pb、Pc、Pd、Pf、Pe、Pg經過修正得到va、vb、vc、ve、vf、vg、vh。之后運用Dijsktra 最短路徑算法形成閉合線如圖5（c），光順處理后得到分割線如圖5（d）。

圖5 邊界線閉合及光順圖

如圖6所示，最終得到Teddy模型的分割效果。

圖6 Teddy模型最終分割效果圖

3 實驗與結果分析

為了驗證算法的有效性，本文依托開源數字幾何處理軟件MeshLabJS，通過開發網格分割Filter插件實現，并部署于Apache 服務器，運用WebGL 的幾何處理及圖形渲染功能，實現完全在瀏覽器中的在線網格分割與網格渲染。在軟、硬件方面，采用Windows 7 Ultimate x64操作系統以及WebStorm 2016.3.1開發環境，服務器PC采用Intel Xeon-E5 2620V4 2.1 GHz CPU 與32 GB RAM，客戶端PC采用Intel?i5-7200U 2.5 GHz CPU與8 GB RAM。

目前，評價三維模型分割的優劣主要是以下幾方面：

（1）視覺效果

視覺效果主要是指模型在分割之后，基于人類視覺效果最小值準則，能否將模型分割成具有意義的各個分塊，分割結果是否存在過分割。

（2）分割一致性

目前普林斯頓大學提供了一套完整的模型分割評判標準[20]。其中蘭德指數（Rand Index）衡量各類算法與人工分割數據的一致性。本文采用評價指標蘭德指數，對普林斯頓數據集進行測試，將本文方法與文獻[21]中提供的9種算法進行比較。

（3）算法的運行速度

一個良好的網格模型分割算法除了需要在模型分割的視覺效果和結果精確度兩方面找到最佳平衡外，還需要有較高的處理速度。本文采用相同模型分割處理消耗時間，將本文方法與蘭德指數平均值較低的3種算法進行時效性對比。

圖7 展示了本文算法在PSB 數據集中部分具有代表性的三維模型分割效果。圖8 展示了本文算法在COSEG形狀數據集中部分具有代表性三維模型的分割效果，將不同分割區域中的三角面片標記為不同顏色。從分割視覺效果上看，絕大多數三維分割的視覺效果符合人的認知要求。

圖7 本文方法對普林斯頓數據集部分模型分割效果圖

圖8 本文方法對COSEG數據集部分模型分割效果圖

表1 Rand Index評價表

在分割一致性上，分別采用本文算法與文獻[20]中提供的9 種算法進行比較。利用蘭德指數作為評價指標，對普林斯頓數據集中19種模型進行測試。表1展示了本文選擇19種模型在不同評估算法下的Rand Index評價結果。蘭德指數越小說明在當前分割下效果越好。從表1中可以看出，對于具有明顯分支結構的模型，如Airplane、Chair、Table、Mech、Bearing 等模型，本文算法具有較優的分割效果，分割蘭德指數優于大多數算法。

然而在對Human、Glass、Armadillo 等模型分割時，本文算法雖然能分割出模型大致語義，但是由于模型存在太多模糊細節特征，因而分割效果不夠理想。從圖9平均蘭德指數圖可以看出，本文方法在分割一致性上優于大部分算法，但是不如深度學習和WCSeg[22]的分割方法。其中深度學習方法的分割一致性最高，本文在蘭德指數平均值上接近WCSeg方法。

圖9 測試模型Rand Index平均值

在算法運行速度方面，表2展示了本文算法與蘭德指數較低的3種算法在分割6種模型時的時效性。由表2可以看出，本文算法由于沒有費時的迭代聚類過程，也沒有復雜度較高的計算，相較于WCSeg 算法在分割效率上要高，另外相較于機器學習方法，不需要考慮數據集采集以及人工訓練時間。

表2 算法時效性分析 s

為了綜合評價性能較優的4種網格分割算法，采用熵值法，分別從分割時間、分割差異（CD）、漢明距離（HD）、基于缺失率的漢明距離（HD-Rm）、基于誤報率的漢明距離（HD-Rf）、蘭德指數（RI）、全局一致性誤差（GCE）和局部一致性誤差（LCE）共8個指標進行綜合評價。熵值法充分考慮指標對評價結果的決定性作用，削弱了主觀因素對評價結果的影響，有助于獲取更為客觀、真實的評價結果。將4 種網格分割方法的8 項指標值分別統計于表3。

表3 不同網格分割算法指標值

在對所有指標進行負向歸一化處理后，考慮到在線網格分割要求算法具備較低的時間復雜度，因此分割時間的主觀權值均取0.15，其余指標主觀權值取0.10，求得各指標熵權值，并統計于表4。最終，根據相對權重向量與歸一化后的指標矩陣，求得6 種方案的綜合評分，見表5。由綜合評分結果可知，在以網格分割快速性為主要導向的前提下，本文方法在算法執行效率、快速性方面具備明顯優勢的同時，能夠兼顧分割可視化效果與分割快速性，適宜在Web環境下執行。

表4 各指標的熵權值

表5 4種方案綜合評分

4 結束語

本文提出了一種面向Web的快速網格分割方法，其目的是為解決Web 環境下網格的在線快速分割。首先綜合離散曲率特性提取出模型的凹特征區域，利用特征區域點集提取出模型的閉合分割線，最終實現在具有較好分割效果情況下對網格模型的快速分割，并通過模型數據集對分割結果進行分析，驗證了本研究對在Web環境下實現網格的數字幾何處理具有一定的意義。

由于本文方法應用于Web 環境下掃描得到網格模型實體建模的區域分割，因而分割高效準確性要求較高，未來研究應側重于兩方面：（1）對網格分割算法進行優化研究；（2）考慮研究基于在線機器學習的網格分割方法。