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

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

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

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

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

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

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

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