自底向上的三維形狀分割.pdf

1、三維形狀分割一直以來都是計算機圖形學(xué)領(lǐng)域的基礎(chǔ)性研究課題。一方面，三維形狀分割可以被應(yīng)用在參數(shù)化、紋理映射、重新網(wǎng)格化以及網(wǎng)格簡化等純幾何分析和處理方面。當前，越來越多的研究者將研究重心從純幾何分析和處理轉(zhuǎn)化到高層次的結(jié)構(gòu)化分析和處理上，而三維形狀的語義分割正是高層次形狀分析與處理的基礎(chǔ)。近些年來，多個三維形狀的協(xié)同分割已經(jīng)成為形狀分析尤其是形狀分割領(lǐng)域中的一個重要課題。這里，多個三維形狀的協(xié)同分割指的是將一組屬于同一類的三維形狀一致分

2、割成具有相互對應(yīng)關(guān)系的語義部件。相對于單個三維形狀，一組屬于同一類的三維形狀可以提供更多的信息，因而對一組三維形狀進行協(xié)同分割所得到的結(jié)果將要優(yōu)于對每個三維形狀單獨進行分割的結(jié)果。而這其中，最關(guān)鍵的問題是如何從一組三維形狀中獲取合適的信息用于協(xié)同分割。
　　另一方面，如何將一個復(fù)雜的形狀分解為一系列簡單的形狀是也一個重要的幾何問題。其中主要的原因是，相對于復(fù)雜的形狀，更容易對簡單的形狀進行計算和操作。本文要介紹的是金字塔分割問題，

3、即希望將給定形狀分割為最少的金字塔形的塊。我們說一個形狀是金字塔形的，如果它的邊界上有一個平坦的底而且剩余的邊界部分可以看成是這個底上的一個高度函數(shù)。三維形狀的金字塔分割問題的研究價值主要體現(xiàn)在其在工業(yè)界的有效應(yīng)用。對于一般的三維形狀，用熔融沉積式三維打印機打印需要額外的支持材料。而支撐材料所帶來的弊端主要是有兩個方面:首先是材料的浪費;其次是這些支撐材料將很難從打印完成的模型中去除，特別是那種有鏤空設(shè)計的三維形狀。然而，金字塔形狀是自

4、穩(wěn)定的，即在打印的時候不需要任何支撐材料，所以它是熔融沉積式三維打印機能處理的理想輸入。另外，金字塔形狀都是可以鑄模的，沿反方向?qū)⒔鹱炙螤顝哪＞咧腥〕鰧⒉粫δＰ驮斐扇魏螕p壞。
　　本文圍繞不同應(yīng)用背景下的三維形狀分割問題展開研究，主要研究成果與貢獻包括:
　　1.本文提出了一個全新的自底向上的算法，可以自動將屬于同一個類的一組模型分割成帶有語義的部件并同時建立這些部件之間的對應(yīng)關(guān)系。從對網(wǎng)格表面進行的過分割開始，我們算法

5、通過將這些過分割曲面片進行聚類得到了期望的語義分割以及對應(yīng)關(guān)系。其中，核心思想是通過在曲面片上定義多種特征使得相似曲面片以較大概率落在特征空間的同一個子空間內(nèi)，從而將曲面片的聚類問題轉(zhuǎn)化為子空間聚類問題。實驗結(jié)果顯示，本算法具有很強的靈活性，對于不同的模型集都能得到較為理想的協(xié)同分割結(jié)果。
　　2.在定義多個特征空間并對其上的信息進行融合時，傳統(tǒng)的方法是將不同特征串連合并成一個特征之后直接進行聚類。我們則是通過在優(yōu)化問題中加入一個

6、懲罰函數(shù)來保證不同特征空間內(nèi)的相似矩陣的稀疏相容性。通過求解這一優(yōu)化問題，我們既可以找到相似性較大的曲面片對，又可以確定出對這一相似性判定起決定性因素的特征。由于在進行三維形狀進行分析和處理時往往需要綜合考慮其上多種特征，所以這種對多種特征進行融合的非傳統(tǒng)方式，可應(yīng)用在除形狀分割以外的其他形狀分析與處理的工作上。
　　3.本文提出了一個全新的自底向上的算法，來解決三維形狀的近似金字塔分割問題。精確金字塔分割問題是NP-難的，這里我

7、們將這個問題轉(zhuǎn)化為一個較為被大家熟知的精確覆蓋問題。給定一個三維形狀，我們首先在其內(nèi)部采樣，然后通過對這些采樣點進行逐步聚類得到一系列不同程度的基本元，并進一步合并得到一組備選金字塔塊。最終，我們將在這一組備選金字塔塊上進行精確覆蓋問題的求解從而得到最后的分割結(jié)果。實驗結(jié)果表明，無論輸入形狀是二維的還是三維的，實心的還是中空的，我們算法都可以處理。我們在大量的數(shù)據(jù)集上對算法進行了測試與評價，證實了算法的有效性和普適性。
　　4.類