基于中軸表達(dá)的三維模型輪廓提取方法

曹 力，吳 垚，徐宜科

基于中軸表達(dá)的三維模型輪廓提取方法

曹 力1,2，吳 垚1，徐宜科1

(1. 合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院(人工智能學(xué)院)，安徽 合肥 230601；2. 安全關(guān)鍵工業(yè)測(cè)控技術(shù)教育部工程研究中心，安徽 合肥 230601)

三維網(wǎng)格模型的輪廓信息在網(wǎng)格檢索、網(wǎng)格簡(jiǎn)化、網(wǎng)格重建中有著廣泛應(yīng)用?，F(xiàn)有的輪廓提取方法較為復(fù)雜，需要分析和過濾網(wǎng)格模型的幾何特征，計(jì)算量大且有時(shí)無法生成完整的輪廓信息。近年來，三維模型的中軸表達(dá)研究趨于成熟，在表達(dá)模型幾何拓?fù)潢P(guān)系上有獨(dú)特的優(yōu)勢(shì)。因此，提出了一種基于中軸表達(dá)的三維模型輪廓提取方法：首先提取三維模型的中軸表達(dá)信息，將中軸角點(diǎn)投影到三維模型表面；然后根據(jù)每個(gè)區(qū)域的拓?fù)潢P(guān)系選擇適合的角點(diǎn)連接關(guān)系，將投影點(diǎn)連接形成模型區(qū)域輪廓；再針對(duì)投影過程中產(chǎn)生的誤差進(jìn)行分析和糾正；最后合并區(qū)域輪廓得到三維模型的完整輪廓。通過對(duì)多個(gè)模型數(shù)據(jù)庫(kù)中代表性的三維網(wǎng)格模型進(jìn)行實(shí)驗(yàn)和重建誤差比較，該方法的平均重建質(zhì)量較現(xiàn)有方法約有10%的提升，在重建質(zhì)量和輪廓信息完整度方面優(yōu)于現(xiàn)有方法。

網(wǎng)格模型處理；輪廓線提?。恢休S表達(dá)；特征提取；幾何分割

隨著三維圖形技術(shù)的愈發(fā)成熟，三維模型在輔助設(shè)計(jì)、電子游戲、影視特效制作等領(lǐng)域中被廣泛應(yīng)用。三維模型的輪廓信息是模型幾何形狀簡(jiǎn)潔且有效地表達(dá)，可以在模型檢索[1]、模型簡(jiǎn)化[2]、網(wǎng)格重建[3]等操作中提供關(guān)于模型幾何特征的有效信息。但輪廓信息在提取時(shí)存在計(jì)算復(fù)雜、冗余信息難以過濾、易受模型細(xì)小特征干擾等難題。因此，如何從三維模型中獲得高質(zhì)量的輪廓信息顯得尤為重要。

針對(duì)不同的應(yīng)用需求，三維模型輪廓在模型編輯和檢索方面有著廣泛應(yīng)用，產(chǎn)生了許多輪廓提取方法，如通過樣條曲線逼近三維曲線法[4]、點(diǎn)云插值法[5]、通過特征曲線的過濾得到完整輪廓法[6]等。2015年，CAO等[7]提出了一種檢測(cè)模型表面特征線并實(shí)現(xiàn)封閉回路的混合框架，可以組合特征線過濾、擴(kuò)展，分塊細(xì)分和邊界平滑，通過凹面特征方法計(jì)算模型輪廓。2019年，LU等[8]在文獻(xiàn)[7]的基礎(chǔ)上利用三維模型提取完整特征曲線網(wǎng)絡(luò)并生成高質(zhì)量的分片布局，可從復(fù)雜的三維模型輸入中提取出完整的特征曲線網(wǎng)絡(luò)，并獲得高質(zhì)量的模型輪廓。ZHUANG等[9]通過一種相關(guān)聚類的方法獲得特征曲線。Torrente等[10]將霍夫變換擴(kuò)展到三維形狀領(lǐng)域，用代數(shù)方法識(shí)別三維網(wǎng)格上的小特征。LAI等[11]引入特征敏感度量識(shí)別特征，并使用數(shù)學(xué)形態(tài)學(xué)的思想對(duì)特征進(jìn)一步分類。BENJAMIN等[12]引入了熱擴(kuò)散以提供更好地分割結(jié)果。除此之外，一些研究中還引入了二面角[13]、法向投票張量[14]、最小二乘逼近[15]，SULTANA等[16]探索了二維空間中中軸與輪廓之間的關(guān)系，但局限于一種類型的模型。這些方法避免了估計(jì)曲率張量或曲率導(dǎo)數(shù)時(shí)巨大的計(jì)算量，但大多數(shù)是基于模型表面網(wǎng)格曲面分析。

本文提出一種基于中軸表達(dá)的三維模型輪廓提取方法。中軸表達(dá)是一種形狀的描述方式，一般指的是二維或三維模型的最大內(nèi)切圓(球)的圓心(球心)的集合[17]。中軸表達(dá)在許多工程領(lǐng)域上有著重要的用途，如有限元分析[18]、形狀分析[19]、實(shí)體建模[20]等。

基于三維模型中軸表達(dá)信息，本文總結(jié)了一系列基本幾何體中軸端點(diǎn)的連接關(guān)系，將輸入模型的不同區(qū)域匹配適合的中軸角點(diǎn)連接關(guān)系，進(jìn)而生成區(qū)域模型輪廓。再按照拓?fù)潢P(guān)系將區(qū)域輪廓合并形成完整的模型輪廓信息。在評(píng)估輪廓線質(zhì)量時(shí)，通過重建模型計(jì)算Hausdorff距離來評(píng)判模型輪廓信息的質(zhì)量。根據(jù)對(duì)各類模型的實(shí)驗(yàn)和重建誤差比較，結(jié)果表明本文方法提取的模型輪廓線更準(zhǔn)確、重建效果更好。

1 相關(guān)工作

1.1 三維中軸表達(dá)

如圖1所示，三維中軸表達(dá)比二維中軸表達(dá)結(jié)構(gòu)更加復(fù)雜，保留的拓?fù)湫畔⒏唷?/p>

圖1 2種中軸表達(dá)((a)二維中軸表達(dá)；(b)三維中軸表達(dá))

1.2 模型輪廓提取方法

依據(jù)從點(diǎn)云或三角網(wǎng)格中提取模型輪廓線的方法，如文獻(xiàn)[9]和最小二乘逼近[15]方法，大部分是通過計(jì)算點(diǎn)或邊的法向信息，采用聚類或擬合網(wǎng)格點(diǎn)的方法。預(yù)先設(shè)定一個(gè)閾值，將法向在閾值內(nèi)的點(diǎn)聚為一類，最終將整個(gè)點(diǎn)云或三角網(wǎng)格分成不相交的幾類，類與類之間的連接處形成邊界。擬合邊界曲線并按照幾何拓?fù)湫畔⑦B接以實(shí)現(xiàn)輪廓線的提取。

由于聚類算法依賴于閾值的設(shè)定，在計(jì)算模型輪廓時(shí)經(jīng)常出現(xiàn)因?yàn)殚撝翟O(shè)計(jì)不合理導(dǎo)致生成輪廓變形的問題。如圖2所示，在聚類時(shí)容易形成鋸齒邊緣，導(dǎo)致出現(xiàn)特征線1和2的錯(cuò)誤特征線，最終生成錯(cuò)誤輪廓。

圖2 種子點(diǎn)出錯(cuò)得到錯(cuò)誤輪廓

1.3 中軸表達(dá)與輪廓提取

MAT作為一種成熟的幾何處理技術(shù)，能夠從復(fù)雜的點(diǎn)云或三角網(wǎng)格數(shù)據(jù)中生成保留拓?fù)湫畔⒌狞c(diǎn)。其最大優(yōu)勢(shì)是生成簡(jiǎn)潔的MAT信息，提供的幾何拓?fù)潢P(guān)系可以為圖像處理提供在幾何形狀上的幫助。

在二維圖形中，利用MAT端點(diǎn)的法向變化性質(zhì)，可以將邊界點(diǎn)篩選出來后與MAT端點(diǎn)連接形成圖形輪廓。在建筑和醫(yī)療影像方面有廣泛地應(yīng)用[21]。

在三維模型中，提取MAT的方法趨于成熟，可以高效準(zhǔn)確地提取出中軸[17]。但是由于三維模型中端點(diǎn)連接關(guān)系的不確定性，缺乏從MAT到模型輪廓直觀的映射關(guān)系，如圖3所示，很難直接從中軸信息中生成正確的模型輪廓。

圖3 中軸表達(dá)生成錯(cuò)誤的輪廓((a)中軸表達(dá)；(b)錯(cuò)誤輪廓1；(c)錯(cuò)誤輪廓2)

2 算法流程

2.1 算法流程

本文算法的輸入是三維網(wǎng)格模型，經(jīng)過中軸提取、區(qū)域分割、輪廓分析等處理步驟后，輸出三維模型的輪廓信息。圖4為輪廓信息的生成流程。

首先通過中軸提取，得到輸入模型的MAT和區(qū)域劃分。對(duì)于每個(gè)區(qū)域，通過MAT的中間網(wǎng)格和對(duì)應(yīng)的端點(diǎn)提取方法得到區(qū)域的MAT端點(diǎn)并映射到原模型三角網(wǎng)格點(diǎn)。

然后根據(jù)本文所定義的基本幾何體中軸端點(diǎn)連接關(guān)系，對(duì)每個(gè)區(qū)域使用最接近的基本幾何體連接關(guān)系來連接端點(diǎn)，形成局部區(qū)域輪廓。

圖4 本文算法具體流程

將得到的區(qū)域輪廓按照原模型的幾何拓?fù)潢P(guān)系連接。連接時(shí)根據(jù)本文所定義的區(qū)域輪廓合并規(guī)則進(jìn)行合并，得到完整的模型輪廓信息。

模型完整輪廓表達(dá)的生成步驟如下：

步驟1.對(duì)輸入模型中軸轉(zhuǎn)換并劃分區(qū)域；

步驟2.提取每個(gè)區(qū)域的中軸角點(diǎn)并映射到原模型三角網(wǎng)格，生成模型輪廓端點(diǎn)；

步驟3.根據(jù)區(qū)域拓?fù)潢P(guān)系匹配不同的連接關(guān)系，連接步驟2得到的輪廓端點(diǎn)，生成區(qū)域輪廓；

步驟4.合并步驟3得到的區(qū)域輪廓；

步驟5.檢查區(qū)域輪廓之間的完整性，擴(kuò)展得到封閉輪廓線；

步驟6.輸出模型完整輪廓。

2.2 模型中軸轉(zhuǎn)換

如圖5所示，通過三維中軸變換可以將Bird模型轉(zhuǎn)換為中軸表達(dá)模型。

2.3 模型區(qū)域劃分

基于SEG-MAT方法[19]，識(shí)別三維模型不同部分之間的連接，將模型劃分為具有幾何意義的區(qū)域。

圖5 Bird模型轉(zhuǎn)換為中軸表達(dá)

獲取三維模型和結(jié)構(gòu)化的MAT圖，計(jì)算輸入三維模型的MAT，將其作為基本圖，并進(jìn)行簡(jiǎn)化，將結(jié)構(gòu)扁平部分的MAT圖簡(jiǎn)化為片，將其余部分簡(jiǎn)化為線，得到結(jié)構(gòu)化MAT圖用來提供三維模型的結(jié)構(gòu)化信息。

本文使用的區(qū)域分割方法為，首先利用結(jié)構(gòu)化MAT圖的連接關(guān)系，計(jì)算中軸網(wǎng)格的球體半徑變化，以檢測(cè)模型的急劇彎曲和厚度變化。將發(fā)生急劇彎曲和厚度變化的部分分割成不同的區(qū)域。通過檢測(cè)中軸的方向變化來確定區(qū)域的連接邊界，相鄰的區(qū)域中軸方向的角度較小。

在得到每個(gè)部分的連接關(guān)系后，執(zhí)行區(qū)域生長(zhǎng)，在計(jì)算時(shí)，每次選擇半徑最大的區(qū)域作為生長(zhǎng)種子點(diǎn)。從粗略分割中獲得精細(xì)分割。

如圖6所示，將分割結(jié)果映射到三維模型表面，得到最終的分割結(jié)果。

圖6 Bird模型區(qū)域劃分

2.4 提取區(qū)域輪廓端點(diǎn)

模型劃分后，需要提取每個(gè)區(qū)域的輪廓，三維模型輪廓由端點(diǎn)和端點(diǎn)間的連接關(guān)系組成。首先要確定區(qū)域輪廓的端點(diǎn)。

由中軸表達(dá)的定義可知，通過內(nèi)接球的方式生成的中軸網(wǎng)格中，最接近模型表面的點(diǎn)保留了模型的邊界信息，可將這一部分點(diǎn)稱為角點(diǎn)。因此提取模型輪廓端點(diǎn)則分為2步：①提取區(qū)域中軸表達(dá)的中軸角點(diǎn)；②將角點(diǎn)映射到模型表面得到輪廓端點(diǎn)。

由于角點(diǎn)均位于最接近模型表面的區(qū)域，因此角點(diǎn)的半徑在所有中軸點(diǎn)中最小。在遍歷模型中軸網(wǎng)格時(shí)，根據(jù)此性質(zhì)，將半徑最小的中軸點(diǎn)提取作為角點(diǎn)集合。以Vase模型為例，將半徑為0.35的中軸點(diǎn)作為模型角點(diǎn)。

因?yàn)橹休S點(diǎn)位于模型內(nèi)部，直接作為模型輪廓端點(diǎn)會(huì)存在誤差。因此在得到中軸角點(diǎn)后，需要將角點(diǎn)映射到原模型距離最近的三角網(wǎng)格點(diǎn)，作為輪廓端點(diǎn)。

輪廓端點(diǎn)可作為模型輪廓的起點(diǎn)與終點(diǎn)，在得到輪廓端點(diǎn)后進(jìn)入確定輪廓端點(diǎn)之間的連接關(guān)系，并得到區(qū)域輪廓。

2.5 生成區(qū)域輪廓

本文以錐體、圓柱、圓環(huán)3種基本幾何體連接方法為例。通過對(duì)基本幾何體連接方法的總結(jié)與拓展，得到3種輪廓端點(diǎn)間連接關(guān)系。每種連接方法分為2步：①連接輪廓端點(diǎn)形成輪廓面；②從輪廓端點(diǎn)中篩選出母線端點(diǎn)，與其余輪廓面連接生成區(qū)域輪廓。

2.5.1 錐體端點(diǎn)連接關(guān)系

將錐體分為圓錐和多棱錐進(jìn)行分別處理。兩者的區(qū)別在于底部端點(diǎn)中母線點(diǎn)的選取區(qū)別。

圓錐體可以看作圓柱體的一個(gè)變形，其中一個(gè)頂面半徑為0。而圓錐體輪廓由底部圓和側(cè)面母線組成，其中母線為頂點(diǎn)與底部圓邊界上端點(diǎn)的連接線。

在提取端點(diǎn)后，可以得到圓錐體的端點(diǎn)集合，由于錐體的幾何性質(zhì)可知：頂點(diǎn)到其余端點(diǎn)的距離相等。將距離方差計(jì)算出的最小端點(diǎn)作為圓錐的頂點(diǎn)。

得到頂點(diǎn)后，其余的端點(diǎn)通過計(jì)算端點(diǎn)間的歐式距離，即將每個(gè)端點(diǎn)與距離最近的其他2個(gè)端點(diǎn)進(jìn)行連接，得到圓錐體底部圓輪廓。

在得到頂點(diǎn)和底部圓邊界點(diǎn)后，連接頂點(diǎn)和底部圓邊界點(diǎn)得到錐體的母線。按照頂點(diǎn)到底部圓邊界點(diǎn)的關(guān)系確定母線的2個(gè)端點(diǎn)，連接母線，從一個(gè)端點(diǎn)出發(fā)，在原模型三角網(wǎng)格中按照?qǐng)D深度優(yōu)先的方法連接到另一個(gè)端點(diǎn)形成母線。母線與底部圓邊界點(diǎn)連接后，形成完整的錐體輪廓。如圖7所示，紅色點(diǎn)為母線點(diǎn)，藍(lán)色點(diǎn)為頂點(diǎn)。

經(jīng)過測(cè)試，從底部圓端點(diǎn)中提取出8個(gè)母線點(diǎn)與頂點(diǎn)進(jìn)行連接時(shí)，重建效果較好且重建誤差趨于收斂。

如圖8所示，在底部圓選取8個(gè)母線點(diǎn)時(shí)誤差已經(jīng)接近收斂。因此對(duì)于圓錐體，選取8個(gè)母線點(diǎn)是較優(yōu)選擇。

圖7 圓錐體和四棱錐輪廓((a)圓錐體輪廓；(b)四棱錐輪廓)

圖8 圓錐體輪廓母線點(diǎn)數(shù)量與重建質(zhì)量關(guān)系

多棱錐與圓錐體不同在于頂部母線點(diǎn)的選取，多棱錐的底部為凸多邊形，因此多棱錐的母線點(diǎn)為底部凸多邊形的頂點(diǎn)。通過向量夾角公式計(jì)算底部輪廓中每個(gè)端點(diǎn)和與其相連的點(diǎn)向量夾角，將與自身最近的2個(gè)端點(diǎn)不在同一直線上的端點(diǎn)作為底部輪廓母線點(diǎn)。

將頂點(diǎn)與頂部母線點(diǎn)連接形成多棱錐輪廓，以圖7四棱錐為例，將頂點(diǎn)與底部四邊形4個(gè)頂點(diǎn)在原模型三角網(wǎng)格上按照?qǐng)D深度遍歷方法連接生成四棱錐輪廓。

2.5.2 圓柱連接關(guān)系

圓柱的頂點(diǎn)連接關(guān)系需要確定頂部和底部輪廓，因與錐體連接關(guān)系不同，圓柱立方體頂部端點(diǎn)到底部端點(diǎn)也需要確定連接關(guān)系。

圓柱的頂面和底面的輪廓生成與圓錐底面生成類似，首先通過方差公式將中軸端點(diǎn)分成2個(gè)點(diǎn)集和，每個(gè)點(diǎn)集內(nèi)通過距離公式進(jìn)行連接形成頂面和底面輪廓。之后從頂面輪廓中選取母線點(diǎn)，如圖9所示圓柱體在選取8個(gè)母線點(diǎn)時(shí)重建效果較好，且誤差趨于收斂。

每個(gè)母線點(diǎn)與另一個(gè)點(diǎn)集中距離最近的點(diǎn)一一對(duì)應(yīng)，作為母線的起點(diǎn)與終點(diǎn)。使用圖深度遍歷在三角網(wǎng)格上將起點(diǎn)與終點(diǎn)連接生成圓柱體的母線，圓柱體輪廓如圖10所示。

圖9 圓柱體輪廓母線數(shù)量與重建結(jié)果之間的關(guān)系

圖10 圓柱體和圓環(huán)輪廓((a)圓柱體輪廓；(b)圓環(huán)輪廓)

2.5.3 圓環(huán)連接關(guān)系

圓環(huán)的頂點(diǎn)連接關(guān)系確定與圓柱類似，需要確定每個(gè)部分的頂部和底部輪廓。與圓柱不同的是，圓環(huán)的中軸表達(dá)為一條穿過圓環(huán)中軸的圓形曲線，其中軸點(diǎn)的半徑大小基本一致，因此無法通過方差公式來確定每一塊的頂部和底部輪廓。

在圓環(huán)的頂點(diǎn)連接關(guān)系中，需要將完整圓環(huán)與殘缺圓環(huán)分開討論。首先隨機(jī)選擇一個(gè)中軸點(diǎn)，以點(diǎn)為起點(diǎn)計(jì)算圓環(huán)中軸表達(dá)的周長(zhǎng)，計(jì)算出間距相同的5個(gè)點(diǎn)。并將圓環(huán)分成5個(gè)部分，再將每個(gè)點(diǎn)映射到模型表面形成母線點(diǎn)，將其進(jìn)行連接得到完整輪廓。如圖11所示，圓環(huán)在選取8個(gè)母線點(diǎn)時(shí)重建效果較好，且誤差趨于收斂。

圖11 圓環(huán)輪廓母線數(shù)量與重建結(jié)果之間的關(guān)系

5個(gè)部分中每2個(gè)部分中的母線點(diǎn)按照最近距離對(duì)應(yīng)，作為母線的起點(diǎn)與終點(diǎn)。使用圖深度遍歷在三角網(wǎng)格上將起點(diǎn)與終點(diǎn)連接生成圓環(huán)的母線，圓環(huán)輪廓如圖10所示。其他的一些基本幾何體的面和母線點(diǎn)見表1。

表1 一些基本幾何體的面與母線點(diǎn)

2.6 區(qū)域合并

在得到各個(gè)區(qū)域的區(qū)域輪廓后，根據(jù)區(qū)域劃分時(shí)三角網(wǎng)格點(diǎn)的聚類信息，按照相鄰區(qū)域進(jìn)行合并。合并策略為：將待合并的2個(gè)區(qū)域設(shè)為和；分別選取和的母線端點(diǎn)，與另一個(gè)區(qū)域(或)的輪廓上最近的點(diǎn)相連。連接按照?qǐng)D深度遍歷的方法，2個(gè)區(qū)域中2個(gè)點(diǎn)之間只產(chǎn)生一次連接關(guān)系。

在合并時(shí)，可能會(huì)出現(xiàn)因幾何性質(zhì)導(dǎo)致端點(diǎn)未連接的問題，本文采用端點(diǎn)生長(zhǎng)的方法。在區(qū)域合并輪廓時(shí)，計(jì)算端點(diǎn)與其周圍端點(diǎn)的距離，當(dāng)該端點(diǎn)與周圍較遠(yuǎn)端點(diǎn)有連接關(guān)系但與較近端點(diǎn)沒有連接關(guān)系時(shí)，將該端點(diǎn)與較近端點(diǎn)進(jìn)行連接，將輪廓線進(jìn)行延伸。如圖12所示，將輪廓線進(jìn)行延伸得到完整的區(qū)域輪廓。

圖12 區(qū)域輪廓合并過程

當(dāng)2個(gè)區(qū)域的幾何性質(zhì)較為接近時(shí)，則合并2個(gè)區(qū)域的端點(diǎn)。首先計(jì)算2個(gè)區(qū)域合并處的端點(diǎn)，并將其進(jìn)行合并。之后對(duì)齊2個(gè)區(qū)域的輪廓線，消除過于接近的輪廓端點(diǎn)產(chǎn)生的突起以減少其對(duì)輪廓的影響。

2個(gè)區(qū)域全部頂點(diǎn)連接完成后即得到2個(gè)區(qū)域合并后的輪廓。將該輪廓與原始2個(gè)區(qū)域的三角網(wǎng)格計(jì)算Hausdorff距離，選取Hausdorff距離較小的連接關(guān)系作為2個(gè)區(qū)域輪廓合并的結(jié)果。最后將所有區(qū)域合并以得到模型完整輪廓。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 對(duì)比實(shí)驗(yàn)

為了評(píng)估輪廓信息的有效性，本文與現(xiàn)有VSA[22]，DFN[7]和FCNE[8]3種方法進(jìn)行了比較，其中VSA方法是一種基于法線域度量標(biāo)準(zhǔn)的形狀近似算法；DFN方法通過分析曲面片的谷線、脊線等特征線來形成光滑曲面邊界和生成模型輪廓；FCNE方法使用二次曲面擬合技術(shù)過濾噪聲特征曲線，通過特征擴(kuò)展來形成閉合的曲線。通過上述3種方法和本文方法在選取的各類不同模型中提取模型輪廓信息，并重建模型，對(duì)比重建的結(jié)果(Hausdorff距離)以評(píng)價(jià)輪廓信息的優(yōu)劣。Hausdorff距離描述了重建后的模型與原始模型的最大誤差，誤差越小代表重建效果越好。

重建使用的是基于曲率的曲面建模算法，根據(jù)2條輪廓線之間的曲率變化，對(duì)曲率進(jìn)行平滑插值得到平滑曲面[23]。

使用本文方法重建出圖13所示的模型分塊，并得到模型重建結(jié)果。

圖13 模型實(shí)驗(yàn)效果

表2中本文方法在處理由基本幾何體組成的模型時(shí)，相比于VSA方法效果約有13%的提升，在處理Bird模型時(shí)可以減少19%的重建誤差；相比于DFN方法有7%到17%的提升，在處理由多個(gè)圓環(huán)、圓柱和圓錐組成的模型時(shí)，效果提升明顯；相比于FCNE方法平均有10%的提升。

由表3和表4可見，本文方法得到的輪廓線進(jìn)行重建后的模型面數(shù)和RMS值較VSA，F(xiàn)CNE和DFN方法更少，為后續(xù)模型處理過程中提供了便利。表5由于使用了中軸信息來減少計(jì)算復(fù)雜度，在處理大部分模型時(shí)耗時(shí)較FCNE方法和DFN方法更少。

表2 不同方法的重建結(jié)果的Hausdorff距離

表3 模型輪廓重建分塊數(shù)

表4 不同方法的重建結(jié)果RMS值

表5 不同方法的運(yùn)行耗時(shí)(ms)

表2～5中缺失的數(shù)據(jù)是由于FCNE和DFN方法在處理Teapot和Telescope模型時(shí)生成的輪廓線互相獨(dú)立且不閉合導(dǎo)致模型重建有誤，因此無法與原模型進(jìn)行比較并得到相關(guān)數(shù)據(jù)。

由圖13可以看出，由于本文方法通過中軸表達(dá)來獲取模型的拓?fù)潢P(guān)系，避免計(jì)算復(fù)雜的三角網(wǎng)格頂點(diǎn)法向信息。針對(duì)聚類算法處理不佳的把手、圓錐圓柱等區(qū)域提取效果較好，重建質(zhì)量較佳。從圖14輪廓對(duì)比和圖15重建結(jié)果對(duì)比可以看出，本文方法提取的輪廓信息整體質(zhì)量?jī)?yōu)于其他3種方法。

圖14 輪廓對(duì)比

圖15 重建結(jié)果對(duì)比

3.2 本文方法的局限性

雖然本文方法使用中軸表達(dá)信息提供模型幾何拓?fù)潢P(guān)系進(jìn)行輪廓提取避免了對(duì)三角網(wǎng)格的復(fù)雜計(jì)算，但依然存在以下2點(diǎn)局限性：

(1) 由于中軸表達(dá)對(duì)于噪聲較為敏感，在處理帶噪聲的模型時(shí)容易出現(xiàn)中軸表達(dá)的端點(diǎn)無法有效地保留該模型的幾何拓?fù)湫畔?。如圖16所示，當(dāng)原模型加上中等強(qiáng)度的高斯噪聲(0.3，是三角網(wǎng)格的平均邊長(zhǎng))后，中軸表達(dá)無法很好地保留原始模型的幾何拓?fù)潢P(guān)系。

圖16 帶噪聲模型的中軸表達(dá)

(2) 當(dāng)模型的組成過于復(fù)雜，不能抽象為基本幾何體時(shí)，中軸表達(dá)的端點(diǎn)與輪廓端點(diǎn)之間的拓?fù)潢P(guān)系會(huì)非常復(fù)雜，無法抽象出統(tǒng)一的對(duì)應(yīng)連接關(guān)系。這時(shí)提取出的輪廓端點(diǎn)無法保留原模型的幾何拓?fù)潢P(guān)系，也就失去了輪廓信息的意義。

在后續(xù)的工作中，將進(jìn)一步擴(kuò)大在已有連接關(guān)系基礎(chǔ)上的應(yīng)用，在保持輪廓信息有效的同時(shí)，簡(jiǎn)化連接關(guān)系的表達(dá)。將中軸表達(dá)應(yīng)用到更廣泛的模型中。

4 結(jié)束語(yǔ)

模型的中軸表達(dá)能夠從復(fù)雜的點(diǎn)云或三角網(wǎng)格數(shù)據(jù)中篩選出保留模型幾何拓?fù)湫畔⒌狞c(diǎn)集，再根據(jù)對(duì)模型進(jìn)行區(qū)域劃分，將模型的各個(gè)區(qū)域抽象為基本幾何體。按照本文設(shè)定的基本幾何體端點(diǎn)連接關(guān)系以模型輪廓的端點(diǎn)生成得到模型完整輪廓信息。由于在處理模型時(shí)通過中軸進(jìn)行篩選，使得最終要計(jì)算的數(shù)據(jù)量大大下降，提升了提取模型輪廓信息的效率，避免因?yàn)榈惴ㄈ菀紫萑刖植孔顑?yōu)解的問題。在處理由近似基本幾何體組成的模型，如CAD模型，較傳統(tǒng)迭代算法效率更高、準(zhǔn)確度更好，從而在重建過程中快速得到具有重建誤差更小的模型輪廓信息。

模型的輪廓信息可應(yīng)用在模型的編輯、檢索、重新網(wǎng)格化等各個(gè)方面。本文提出的基于中軸表達(dá)的模型輪廓信息生成方法可以為這些高級(jí)應(yīng)用提供有效的模型輪廓信息，從而方便之后的模型處理工作。

[1] LI Y H, LEI H P, LIN S J, et al. A new sketch-based 3D model retrieval method by using composite features[J]. Multimedia Tools and Applications, 2018, 77(2): 2921-2944.

[2] LI M L, NAN L L, SMITH N, et al. Reconstructing building mass models from UAV images[J]. Computers & Graphics, 2016, 54: 84-93.

[3] LUN Z L, GADELHA M, KALOGERAKIS E, et al. 3D shape reconstruction from sketches via multi-view convolutional networks[C]//2017 International Conference on 3D Vision. New York: IEEE Press, 2017: 67-77.

[4] 李小艷, 陳紹平. 改進(jìn)差分進(jìn)化算法求解B樣條曲線曲面擬合問題[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2018, 35(3): 275-281, 298.

LI X Y, CHEN S P. Solving b-spline curve and surface fitting problems by improved differential evolution algorithm[J]. Computer Applications and Software, 2018, 35(3): 275-281, 298 (in Chinese).

[5] PENG Y P, WU Z B, CAO G Z, et al. Three-dimensional reconstruction of wear particles by multi-view contour fitting and dense point-cloud interpolation[J]. Measurement, 2021, 181: 109638.

[6] GEHRE A, BRONSTEIN M, KOBBELT L, et al. Interactive curve constrained functional maps[J]. Computer Graphics Forum, 2018, 37(5): 1-12.

[7] CAO Y H, YAN D M, WONKA P. Patch layout generation by detecting feature networks[J]. Computers & Graphics, 2015, 46: 275-282.

[8] LU Z D, Guo J W, Xiao J, et al. Feature curve network extrac-tion via quadric surface fitting[EB/OL]. [2021-07-13]. https://doi.org/10.2312/pg.20191338.

[9] ZHUANG Y X, DOU H, CARR N, et al. Feature-aligned segmentation using correlation clustering[J]. Computational Visual Media, 2017, 3(2): 147-160.

[10] TORRENTE M L, BIASOTTI S, FALCIDIENO B. Recognition of feature curves on 3D shapes using an algebraic approach to Hough transforms[J]. Pattern Recognition, 2018, 73: 111-130.

[11] LAI Y K, ZHOU Q Y, HU S M, et al. Robust feature classification and editing[J]. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(1): 34-45.

[12] BENJAMIN W, POLK A W, VISHWANATHAN S V N, et al. Heat walk: robust salient segmentation of non-rigid shapes[J]. Computer Graphics Forum, 2011, 30(7): 2097-2106.

[13] ARHID K, UNIVERSITY H S, ZAKANI F, et al. An efficient hierarchical 3D mesh segmentation using negative curvature and dihedral angle[J]. International Journal of Intelligent Engineering and Systems, 2017, 10(5): 143-152.

[14] KIM H S, CHOI H K, LEE K H. Feature detection of triangular meshes based on tensor voting theory[J]. Computer-Aided Design, 2009, 41(1): 47-58.

[15] GORI G, SHEFFER A, VINING N, et al. FlowRep: descriptive curve networks for free-form design shapes[J]. ACM Transactions on Graphics, 2017, 36(4): 59.

[16] SULTANA S, BLATT J E, GILLES B, et al. MRI-based medial axis extraction and boundary segmentation of cranial nerves through discrete deformable 3D contour and surface models[J]. IEEE Transactions on Medical Imaging, 2017, 36(8): 1711-1721.

[17] Li P, Wang B, Sun F, et al. Q-mat: Computing medial axis transform by quadratic error minimization[J]. ACM Transactions on Graphics, 2016,35(1): 8.1-8.16

[18] QUADROS W R. LaTracks3D: a new approach for meshing general solids using medial axis transform[J]. Computer-Aided Design, 2016, 72: 102-117.

[19] LIN C, LIU L J, LI C J, et al. SEG-MAT: 3D shape segmentation using medial axis transform[EB/OL]. [2021-01-05]. https://ieeexplore.ieee.org/document/9234096.

[20] TSOGKAS S, DICKINSON S. AMAT: medial axis transform for natural images[C]//2017 IEEE International Conference on Computer Vision. New York: IEEE Press, 2017: 2727-2736.

[21] WIDYANINGRUM E, PETERS R Y, LINDENBERGH R C. Building outline extraction from ALS point clouds using medial axis transform descriptors[J]. Pattern Recognition, 2020, 106: 107447.

[22] COHEN-STEINER D, ALLIEZ P, DESBRUN M. Variational shape approximation[C]//ACM SIGGRAPH 2004 Papers on - SIGGRAPH '04. New York: ACM Press, 2004: 905-914.

[23] PAN H, LIU Y, SHEFFER A, et al. Flow aligned surfacing of curve networks[J]. ACM Transactions on Graphics, 2015, 34(4): 1-10.

3D model wireframe extraction method based on medial axis expression

CAO Li1,2, WU Yao1, XU Yi-ke1

(1. School of Computer and Information (School of Artificial Intelligence), Hefei University of Technology, Hefei Anhui 230601, China; 2. Engineering Research Center of Safety Critical Industrial Measurement and Control Technology, Ministry of Education, Hefei Anhui 230601, China)

The wireframe of 3D models is widely employed in mesh retrieval, mesh simplification, and mesh reconstruction. The complexity of the existent wireframe generation methods makes it necessary to analyze the geometric features of the mesh model and calculate the surface mesh of the model to obtain the wireframe. This entails a large amount of calculation and sometimes failures to complete the wireframe. To address the problems, a 3D model wireframe extraction method based on axis representation was proposed. Firstly, the axis representation information of the 3D model was extracted, and the corner points of the axis were projected onto the surface of the 3D model. Then, according to the topological relationship of each region, the suitable corner connection relationship was selected, and the projection points were connected to form the wireframe of the model region. After the connection operation, the errors in the projection process were analyzed and corrected. Finally, the region wireframes were merged to obtain the complete wireframe of the 3D model. Through experiments on and comparisons of reconstruction errors of representative 3D mesh models in several model databases, the average re-construction quality of the proposed method is about 10% higher than the three methods, outperforming the existing wireframe extraction methods in reconstruction quality and wireframe information integrity.

mesh model processing; wireframe extraction; axis representation; feature extraction; geometric segmentation

TP 391

10.11996/JG.j.2095-302X.2022030461

A

2095-302X(2022)03-0461-08

2021-09-13；

2021-11-21

13 September，2021；

21 November，2021

安徽省重點(diǎn)研究與開發(fā)計(jì)劃項(xiàng)目(202104e11020006)；國(guó)家自然科學(xué)基金項(xiàng)目(61602146)

Key Research and Development Projects of Anhui Province (202104e11020006); National Natural Science Foundation of China (61602146)

曹 力(1982-)，男，副教授，博士。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、幾何分析等。E-mail：lcao@hfut.edu.cn

CAO Li (1982-), associate professor, PH.D. His main research interests cover computer graphics and geometric analysis. E-mail：lcao@hfut.edu.cn