結合Nystr?m 方法的三維網格模型分割方法

朱天曉

（上海工程技術大學電子電氣工程學院， 上海 201620）

0 引 言

隨著計算機視覺、三維掃描等技術的發展，三維網格模型被廣泛應用于虛擬現實、影視動畫等領域。三維網格模型分割是計算機圖形學的重要研究點，也是互聯網上模型檢索、模型生成等技術的基礎。三維模型精度越來越高，數據量不斷增長，大大增加了分割難度。

三維網格模型分割（簡稱網格分割）是根據一定分割規則，將連通的網格模型分解為一組數目有限的面片集的過程。 網格分割按照不同的標準有不同的分類。 按照分割結果的不同，Rodrigues 等［1］將網格分割方法分為面片分割和部件分割，前者將網格分割成若干幾何屬性一致的面片集，后者將網格分割為符合人類視覺劃分效果的若干部件。 按照分割方式的不同，龔思潔等［2］將現今主流的分割方法分為3 類：第一類是根據模型幾何特征將模型表面具有相關性的面片合并為一類，如聚類分析法；第二類是基于最小值原則，在模型表面構建分割線，將模型拆分為多個部分；第三類是深度學習方法，通過構建深度學習網絡，進行有監督學習。 深度學習方法通常對機器性能有很高的要求，此外獲取優質數據集也是一個難題，因此很多研究集中在前兩種方法上，計算量相對較小。 龔思潔等［2］提出能量和區分度兩種模型特征用于尋找分割點，并使用腐蝕算法、最小能量原則構造分割線，得到了精度較高的分割結果，但算法耗時較長；趙云成等［3］提出了結合曲率約束的網格模型快速分割方法，根據高斯曲率和平均曲率篩選出模型的凹區域，依據最小負曲率閾值原則構造出閉合分割線，實現對網格模型的分割；這兩種方法都屬于基于最小值原則、構建分割線的分割方法。 對于基于聚類分析的網格分割方法，梁楚萍等［4］根據聚類過程中簇劃分方式的區別，將其劃分為5 類：區域生長算法、多源區域生長算法、層次聚類算法、迭代聚類算法和譜聚類算法，前4 種算法都以網格屬性直接作為分類依據，而譜聚類算法核心在于對網格模型生成的親和力矩陣的劃分，該算法可以得到較高準確率。

Liu 等［5］將譜聚類引入到網格分割問題中，使用基于測地線距離和余弦距離構造的核函數計算親和力矩陣，可以有效利用模型的幾何特征進行分割，但是構建親和力矩陣耗時較長；Jiao 等［6］在譜聚類算法框架下，使用網格顯著指數和網格離散曲率構建親和力矩陣并完成網格分割，沒有解決構建親和力矩陣時間、空間開銷大的問題；萬燕［7］等使用譜聚類算法將模型過分割為弱凸區域，對弱凸區域按照可見度進行排序，根據相互可見性和形狀直徑函數進行區域合并，最終得到分割結果，但沒有解決譜聚類算法耗時長、內存消耗大的問題；Tong 等［8］對親和力矩陣計算費德勒（Fiedler）向量，通過分析費德勒向量，將網格分割問題轉化為梯度極小化問題；Li 等［9］通過分析費德勒向量、計算費德勒殘差，對模型進行遞歸分割。僅使用費德勒向量降低了后續的計算成本，但是構建親和力矩陣的時間、空間開銷沒有降低。

針對譜聚類構建親和力矩陣耗時長、內存消耗大、難以分割面片數較多的模型的問題，本文提出了一種結合Nystr?m 方法的三維網格模型分割方法，能夠避免構建親和力矩陣的巨大內存開銷，有效降低譜聚類算法進行網格分割所需的時間，可以獲得符合人類視覺劃分效果的分割結果。

1 相關技術背景

1.1 Nystr?m 方法

Nystr?m 方法是一種用于大規模數據聚類的有效方法，其最初目的是為了求解積分方程。 Williams等［10］將其引入核方法，用于加速矩陣特征分解，而準確率并沒有明顯下降。 近年來隨著研究的深入，Nystr?m 方法也被用于圖片分割、點云分割。

Nystr?m 方法適用于對稱矩陣，其基本思想是通過采樣獲得少量樣本點，使用樣本點與非樣本點之間的相似性來估計目標矩陣或其特征向量，采樣方法有隨機采樣、基于K-Means 算法采樣、基于最遠策略采樣等。

1.2 譜聚類算法

譜聚類是一種基于譜圖理論的聚類算法，能在任意簇形的樣本空間上達到良好的聚類效果。 該算法核心在于構建親和力矩陣，其形式類似于圖鄰接矩陣。

Ng 等［11］提出了一種二維數據譜聚類算法，使用徑向基函數核（Radial Basis Function kernel， RBF kernel）計算二維數據中每兩點的歐氏距離，用于構建親和力矩陣，并對親和力矩陣的特征向量進行KMeans 聚類，實現對原始數據的聚類；Liu 等［5］在其工作基礎上提出了一種譜聚類三維網格模型分割算法，將測地線距離和余弦距離引入RBF 核函數來構造親和力矩陣，該算法在網格分割方面得到了較高的準確率。

2 本文算法流程

傳統的譜聚類算法使用核函數構建親和力矩陣，時間、空間復雜度一般為O（n2）。 對于面片數較多的模型，往往難以使用譜聚類算法對模型進行分割。

本文將Nystr?m 方法與譜聚類算法結合，提出了一種有效降低構建親和力矩陣時間、空間開銷的網格模型分割方法。 首先，使用K-Means＋＋算法對模型面心進行聚類，將距離聚類中心最近的面心作為采樣點；其次，使用基于測地線距離和余弦距離的核函數計算采樣點和所有面心的親和力數值，并使用Nystr?m 方法估計親和力矩陣的主特征向量；將主特征向量拼接為矩陣，對矩陣每行元素使用KMeans 算法聚類，實現對模型的分割；最后，使用自適應鄰域濾波算法對分割結果進行處理，得到優化后的模型分割結果。 本文方法流程如圖1 所示。

圖1 本文方法流程圖Fig. 1 Flow chart of the proposed method

2.1 特征向量估計

使用譜聚類算法分割模型時，若模型的面片數為N，則需要計算大小為N×N的親和力矩陣，計算量較大、耗時較長。 因此，可以使用Nystr?m 方法對矩陣或其特征向量進行估計近似，提升譜聚類算法運行速度。

Oglic 等［12］證明了K -Means ＋＋算法作為Nystr?m 方法中的采樣方法具有可行性，并且誤差較小。 K-Means＋＋算法是K-Means 算法的改進，其初始聚類中心點的選擇是基于最遠策略的，即選擇相互間距離盡可能遠的初始聚類中心點。 本文將聚類數目設置為采樣點數，對模型面片的面心進行KMeans＋＋聚類，并選擇距離聚類中心點最近的面心作為采樣點。

設模型的面片數為N，從中使用K-Means＋＋采樣獲得m個面心作為樣本點（m?N），則非樣本點數目為n＝N-m。

親和力矩陣W可以表示為式（1）：

其中，A∈，B∈，C∈，矩陣A表示采樣的m個樣本點之間的親和力矩陣；矩陣B表示采樣的m個樣本點和剩余n個非樣本點之間的親和力矩陣；因為m?N，所以矩陣C的大小幾乎和矩陣W相同。

本文使用Nystr?m 方法對矩陣W的主特征向量進行估計，方法流程如圖2 所示。

圖2 Nystr?m 方法流程圖Fig. 2 Flow chart of the Nystr?m method

首先，將矩陣Α特征分解，即?。経Λ UT；Λ為對角矩陣，其中非零元素為矩陣A的特征值。 親和力矩陣W的近似特征向量為式（2）：

由式（1）、式（2）有親和力矩陣W可近似為式（3）：

由式（3）可知，矩陣C的近似值為BTA-1B。

其次，對A、B進行標準化。 因為在譜聚類算法中，使用標準化的親和力矩陣。 對估計矩陣求行和，式（4）：

其中，ar、br∈，分別表示矩陣A、B的行和；bc∈表示矩陣B的列和；1 表示元素均為1 的列向量。

使用式（4）對矩陣A和B進行歸一化，式（5）和式（6）：

最后，求解矩陣的主特征向量。

若矩陣A正定，令A1／2表示A的正定平方根。定義S＝A＋A-1／2B BTA-1／2，并將其特征分解為S＝US ΛS。 可一步估算出矩陣的正交主特征向量式（7）：

若矩陣A非正定，矩陣的估計特征向量為定義有Z ZT，對ZTZ特征分解，有ZTZ＝FΣ FT。 最后估算出矩陣的正交主特征向量，式（8）：

Nystr?m 方法中數據量最大的是式（3）的親和力矩陣，但是不必真正計算該矩陣，譜聚類算法需要的是親和力矩陣的主特征向量。 因為是由矩陣A、B計算拼接出的，而在式（4）進行標準化時，可以直接使用矩陣A、B標準化，而無需計算。

可見，最大的矩陣為，相比與傳統譜聚類算法需要計算，本文使用Nystr?m 方法對親和力矩陣主特征向量進行估計近似，大大降低了時間、空間開銷。

2.2 網格模型分割

本文計算面片i到相鄰面片j的測地線距離，式（9）：

其中，li、lj分別為面片i、j的交線中點pl到對應面片質心pi、pj的歐式距離。

本文定義面片i到相鄰面片j的余弦距離為式（10）：

其中，ni為面片i的法向量，nj為面片j的法向量。

使用式（9）、式（10）構造的加權距離公式為式（11）：

其中，n為面片數；δ為衡量測地線距離與余弦距離重要性的參數；η為調整余弦距離的參數。

本文設置δ＝0.03，η＝0.15。

使用式（11）構造的親和力數值計算式（12）：

本文提出的結合Nystr?m 方法的譜聚類算法流程如下：

（1）對面片集M＝｛m1，…，mn｝，使用K-Means＋＋算法確定m個采樣點；

（2）使用式（12）計算m個采樣點與自身以及與剩余n個非樣本點之間的親和力矩陣；

（3）使用Nystr?m 方法估計親和力矩陣W＾的m個主特征向量， 并按列排放， 組成矩陣V＝[e1，e2，…，em] ；

（4）對矩陣V每行元素進行單位化，得到矩陣V′；

（5）將矩陣V′ 中每行元素視為映射到m維空間的特征點，并對其進行K-Means 聚類，聚類數目為m。

最后，如果矩陣V′的i行分配給簇j時，將原始面片mi分配給簇j。

2.3 分割誤差優化

Nystr?m 方法獲得的親和力矩陣特征向量是近似計算得出的，因此在分割時會出現一定的誤差，分割模型誤差俯視圖如圖3 所示。

圖3 分割模型誤差俯視圖Fig. 3 Top view of segmentation error

可見，分割誤差類似于二維圖像中的椒鹽噪聲，椒鹽噪聲的消除方式一般是使用中值濾波方法。

二維圖像中使用像素鄰域濾波，在三維網格中可以使用面片鄰域進行濾波。 面片i的一階鄰域、二階鄰域如圖4 所示。

圖4 面片i 鄰域示意圖Fig. 4 Diagram of the neighborhood of surface i

參考目前去噪效果較好的自適應中值濾波算法，本文使用面片鄰域作為濾波算子對分割模型進行優化，提出了一種網格模型自適應鄰域濾波算法。該算法遍歷模型面片進行優化，其核心是對誤差的判斷。

若面片i的一階鄰域中均為同一種顏色C且與面片i顏色不同，則將面片i視為誤差，并將其顏色設置為顏色C。

若面片i一階鄰域中存在兩種（或以上）顏色Ca、Cb，并且數量最多的顏色Cm占比超過80%，同時面片i顏色不為Cm，則將面片i視為誤差，將其顏色設置為顏色Cm。

若一階頂點鄰域中數量最多的顏色Cm占比不超過80%，同時面片i顏色不為Cm， 則將鄰域擴大為二階鄰域進行判斷，將面片i顏色設置為二階鄰域中數量最多的顏色。

使用自適應鄰域濾波算法對分割結果進行優化，得到優化后的模型俯視圖如圖5 所示，基本上消除了因矩陣估計引起的分割誤差。

圖5 分割模型優化結果俯視圖Fig. 5 Top view of optimization results of segmentation

3 實 驗

本文使用Python 編程實現方法，在CPU 為Intel Core i5-6300HQ（2.30 GHz）、內存為16 GB、系統為Windows 10 的PC 上進行實驗。 由于普林斯頓數據集中模型面片數較少，本文從中選擇了8 類，每類2 個，共計16 個網格模型進行Loop 細分，并進行人工二分割，作為實驗數據集。

使用Nystr?m 方法時，需要確定對模型的采樣數m。 圖6 為幾何模型A 的分割誤差俯視圖（未進行誤差優化），其中m為采樣數，可見采樣數從2 增加到10，分割誤差基本相同。

圖6 幾何A 模型不同采樣數的分割誤差俯視圖Fig. 6 Top view of segmentation error of geometry A with different sampling numbers

采樣數取不同數值時，對選取的16 個模型進行分割（未進行誤差優化），并對結果進行定量比較，選組評估指標為蘭德分數（Rand Score，RS）和運行時間，蘭德分數用來衡量分割方法與基準的相似性，數值越大代表分割效果越好，實驗結果如圖7 和圖8 所示。 可見采樣數從2 增加到10，蘭德分數基本持平，分割時間明顯上升。 因此，本文選取采樣數目為m＝2。

圖7 測試模型不同采樣數的蘭德分數平均值Fig. 7 Average Rand scores of the testing models with different sampling numbers

圖8 測試模型不同采樣數的運行時間平均值（／s）Fig. 8 Average running time of the testing models with different sampling numbers（unit： second）

本文方法對模型的二分割結果（每類模型中上方的命名為A，下方為B）如圖9 所示，可以看出本文方法得到的分割結果符合人眼的視覺標準。

圖9 本文方法對普林斯頓數據集部分細分模型分割結果Fig. 9 The segmentation results by the proposed method of partial Princeton dataset models after subdivision

對比指標除蘭德分數外，還有準確率分數（Accuracy Score，AS）和漢明損失（Hamming Loss，HL）。 準確率分數與蘭德分數類似，用來衡量分割方法與基準的相似性，其數值越大越好；漢明損失用來衡量分割結果中錯誤的比例，數值越小代表分割效果越好。

為進一步驗證本文方法的有效性，采用量化評估標準將本文方法與BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies， BIRCH）算法，K-Means 算法，Mini Batch K-Means 算法，Liu等［5］提出的算法和Katz 等［13］提出的算法進行二分割比較。 實驗結果如圖10、圖11 所示。 可見本文方法具有較好的分割效果，蘭德分數、準確率分數高于其他算法，漢明損失低于其他算法。 在本文實驗環境下，Liu 等［5］提出的算法和Katz 等［13］提出的算法僅可正常分割1 個模型，分割其余模型時超出16 GB內存限制，無法運行，因此無法顯示這兩種方法的指標平均值。

圖10 測試模型蘭德分數、準確率分數平均值Fig. 10 Average Rand scores，accuracy scores of the testing models

圖11 測試模型漢明損失平均值Fig. 11 Average Hamming loss of the testing models

6 種算法在本文數據集上的蘭德分數和運行時間見表1（本文方法已進行誤差優化）。 在面片數最小的模型零件A （面片數3w）上，Liu 等［5］提出的算法獲得了最高的蘭德分數0.992，運行時間為397.3 s；Katz 等［13］提出的方法獲得的次高的蘭德分數0.988，運行時間為1 256.1 s，這兩種方法在其余模型上均超出16 GB 內存限制，無法運行（數據在表1 中顯示為橫線）。 本文方法在零件A 模型上獲得的蘭德分數為0.986，高于其余3 種方法，運行時間為19.1 s；在其余模型上，蘭德分數均為最高，運行時間在幾十秒左右。

表1 測試模型蘭德分數、運行時間評價表Tab. 1 Rand score， running time evaluation table of the testing models

傳統譜聚類算法因其巨大的時間、空間開銷無法分割面片數較多的模型；K-Means、BIRCH 等算法運行時間短、消耗內存空間小，但無法有效利用模型的幾何特征，分割效果差。 本文方法相比于傳統譜聚類算法，有效減少了分割模型所需時間、空間開銷，同時也獲得了較高的蘭德分數，分割效果比KMeans、BIRCH 等算法好。

4 結束語

本文提出了一種結合Nystr?m 方法的三維網格模型分割方法。 首先，使用K-Means＋＋算法對模型面心進行聚類，將距離聚類中心最近的面心作為采樣點；其次，計算采樣點和所有面心的親和力數值，并使用Nystr?m 方法估計親和力矩陣的主特征向量；將特征向量拼接為矩陣，并對矩陣每行元素使用K-Means 方法聚類，實現對模型的分割；最后，使用自適應鄰域濾波算法對分割結果進行優化，去除估計誤差。 實驗結果表明本文方法有效避免了計算親和力矩陣的時間、空間開銷，可以獲得符合人類視覺劃分效果的分割結果。

本文使用Nystr?m 方法估計親和力矩陣，存在一定分割誤差，在二分割上取得了較好的效果，而對于多分割則會存在較大誤差。 降低Nystr?m 方法的估計誤差，更好地逼近真實的親和力矩陣是接下來的研究重點。