劉世凡, 梁晉, 董波

(西安交通大學(xué)機(jī)械制造系統(tǒng)工程國家重點(diǎn)實(shí)驗(yàn)室, 710049, 西安)

近年來,3D反求技術(shù)發(fā)展迅速,快速三維人體掃描廣泛應(yīng)用于醫(yī)療外科、服裝、個(gè)性化定制等行業(yè),因此快速獲取完整的人體三維模型數(shù)據(jù)具有重要的意義[1]。但是,人體掃描結(jié)果幾乎不可避免地會出現(xiàn)局部信息缺失,從而產(chǎn)生模型孔洞,對人體模型的整體外觀和后續(xù)處理產(chǎn)生巨大的不良影響[2],其中尤以大面積信息缺失所致的孔洞影響最深[3]。因此,在保證模型特征的情況下快速修復(fù)大面積復(fù)雜孔洞是三維模型后處理過程中的重要工作。

Davis等在孔洞附近設(shè)置符號距離函數(shù),通過擴(kuò)散來重建整體模型,該方法修復(fù)精度較高但效率低[4]。Van等通過將三維點(diǎn)映射到二維平面并進(jìn)行德洛內(nèi)三角化來修補(bǔ)孔洞,但難以修補(bǔ)空間形狀復(fù)雜的孔洞[5]。Centin等通過泊松驅(qū)動來封閉孔洞,但是需要依賴精確的頂點(diǎn)法線[6]。Brunton等利用最小能量方程獲取投影平面并插入新點(diǎn),但邊界點(diǎn)數(shù)較多時(shí),效率大大下降[7]。Altantsetseg等通過邊界邊輪廓線獲取均勻插入點(diǎn),同樣存在效率問題[8]。Brunet等利用B樣條曲線獲取插入點(diǎn)信息,該方法體素化過程較為耗時(shí)[9]。張立國等采用徑向基函數(shù)擬合孔洞的隱式曲面,并將新增點(diǎn)投影上去,該方法對單一簡單孔洞修補(bǔ)較為理想,但對大面積孔洞擬合隱式曲面效率很低且可能擬合失敗[10]。Xia等通過特征線將孔洞分割后再修補(bǔ),該方法依賴恰當(dāng)?shù)拈撝礫11]。劉震等通過動態(tài)規(guī)劃構(gòu)建曲面并利用帶特征線約束的雙拉普拉斯系統(tǒng)修補(bǔ)孔洞,方法保持了較好的細(xì)節(jié)但孔洞面積大時(shí)效率較低[12]。Wang等通過粒子群優(yōu)化算法在三次曲面上獲取新增點(diǎn)信息,該方法依賴優(yōu)良的參數(shù)[13]。Wei等通過積分法產(chǎn)生最小三角面片來修補(bǔ)孔洞,但效率較低[14]。Hu等在細(xì)分三角面片后利用雙邊濾波重建缺失的特征,但生成的網(wǎng)格與原網(wǎng)格有較大差別[15]。高旋輝等先對孔洞進(jìn)行異常值消除,再利用改進(jìn)的多邊形三角化法進(jìn)行修補(bǔ)[16]。以上算法在孔洞修復(fù)精度方面有較大改進(jìn),但多應(yīng)用于單一孔洞,而人體掃描模型中存在大量大面積且空間形狀復(fù)雜的孔洞,這些方法難以快速甚至無法完成修補(bǔ)。

本文提出了一種利用邊界點(diǎn)周圍矢量信息建立權(quán)函數(shù)的孔洞修復(fù)算法,實(shí)現(xiàn)了對大面積復(fù)雜孔洞的快速、保持特征的均勻網(wǎng)格修補(bǔ)。該方法基于波前法,結(jié)合邊界點(diǎn)法向量、邊界點(diǎn)曲率和周邊局部邊界點(diǎn)聚攏方向建立權(quán)函數(shù),通過最小化權(quán)函數(shù)確定新增點(diǎn)的空間坐標(biāo)以產(chǎn)生新增面片,多次向孔洞內(nèi)部推進(jìn)直至孔洞修復(fù)完成。

1 傳統(tǒng)波前法

傳統(tǒng)波前法以遞歸的方式修補(bǔ)網(wǎng)格孔洞。首先用當(dāng)前邊界點(diǎn)集初始化波前,而后計(jì)算相鄰邊界邊形成的內(nèi)角,從最小內(nèi)角開始遞歸推進(jìn),每次遞歸后都以新邊界點(diǎn)集對波前進(jìn)行初始化,直至孔洞被新增三角面片完全填充。對最小內(nèi)角θ進(jìn)行推進(jìn)時(shí),通常根據(jù)最小內(nèi)角的大小采取不同的推進(jìn)策略[17],當(dāng)最小角θ<75°,直接連接邊界點(diǎn);當(dāng)75°≤θ≤135°,新增點(diǎn)Vadd在θ角平分線上;當(dāng)135°<θ≤180°,新增點(diǎn)Vadd1和Vadd2在θ角三等分線上,新增邊長度取Vi點(diǎn)鄰邊的平均長度,如圖1所示。

(a)0°≤θ<75° (b)75°≤θ≤135° (c)135°<θ≤180°圖1 最小角推進(jìn)原則

波前法可以快速地修復(fù)趨于收攏的簡單孔洞,但無法保持孔洞特征,且當(dāng)孔洞趨于發(fā)散時(shí),孔洞修補(bǔ)會失敗。這是因?yàn)椴ㄇ胺ǖ耐七M(jìn)方向僅由最小內(nèi)角決定,當(dāng)推進(jìn)方向不朝向孔洞中心時(shí),新增的三角面片不能聚攏并封閉孔洞。圖2a、2b分別表示了趨于聚攏和趨于發(fā)散的孔洞在波前法迭代一次時(shí)的推進(jìn)方向。

(a)趨于聚攏的孔洞 (b)趨于發(fā)散的孔洞圖2 兩種孔洞的波前法推進(jìn)方向

本文采用了波前法的最小角迭代推進(jìn)原則,但在推進(jìn)策略上先通過邊界點(diǎn)周邊的聚攏矢量對大面積孔洞邊界點(diǎn)法向量進(jìn)行修正,再通過修正后的頂點(diǎn)法向量與邊界點(diǎn)的兩個(gè)鄰點(diǎn)計(jì)算平均曲率,最后結(jié)合原插入向量建立加權(quán)函數(shù),通過求解最小化的加權(quán)函數(shù),得出新增點(diǎn)的空間坐標(biāo),使新增面片在孔洞趨于發(fā)散的情況下能夠快速向孔洞中心聚攏。

2 網(wǎng)格孔洞修補(bǔ)

首先,通過孔洞邊界點(diǎn)個(gè)數(shù)識別大面積的孔洞,對此類孔洞通過周邊邊界點(diǎn)的平均聚攏特征向量修正最小角頂點(diǎn)的法向量;然后,結(jié)合邊界頂點(diǎn)局部曲率和原插入向量,建立并求解最小化加權(quán)函數(shù),以獲取新增點(diǎn)空間坐標(biāo),迭代推進(jìn)直至網(wǎng)格封閉。本文算法適用的網(wǎng)格模型為流形網(wǎng)格模型。

對于任意孔洞,現(xiàn)定義邊界點(diǎn)按逆時(shí)針順序編號形成的集合為{Vi|i=0,1,…,nhole-1},其中nhole是孔洞邊界點(diǎn)總個(gè)數(shù);定義vij為邊界點(diǎn)Vi指向邊界點(diǎn)Vj的向量,vij的單位向量為eij。現(xiàn)以最小內(nèi)角∠Vi-1ViVi+1=θ,75°≤θ<135°為例,此時(shí)應(yīng)新增1個(gè)點(diǎn)Vx。

2.1 頂點(diǎn)法向量修正

本文以邊界點(diǎn)個(gè)數(shù)大于50的孔洞為大面積孔洞。對于大面積孔洞,為避免新增面片不能聚合收攏,利用頂點(diǎn)Vi的局部聚攏方向?qū)ζ浞ㄏ蛄窟M(jìn)行修正。以頂點(diǎn)Vi在邊界點(diǎn)鏈表中指向前n個(gè)邊界點(diǎn)和后n個(gè)邊界點(diǎn)的單位向量的平均向量為局部聚攏方向,即計(jì)算單位向量

nr=αn0+βne

(2)

式中:n0為Vi原法向量,α+β=1,本文取α=0.85。

圖3 法向量的修正向量ne

2.2 權(quán)函數(shù)

確定新增點(diǎn)Vx的空間坐標(biāo)實(shí)質(zhì)是確定頂點(diǎn)Vi指向Vx的向量vix,該向量應(yīng)包含Vi點(diǎn)的局部曲率特征信息、收攏趨勢信息,并能使新增的三角面片更規(guī)則。因此,本文建立了一個(gè)包含以上信息的權(quán)函數(shù)并求解,以獲取新增點(diǎn)最優(yōu)的空間坐標(biāo),具體步驟如下。

(1)先通過Vi-1點(diǎn)和Vi+1點(diǎn)的平均Taubin曲率計(jì)算Vi的曲率,Vi的Taubin曲率為

式中:nr為頂點(diǎn)Vi的修正法向量,向量T為vix在頂點(diǎn)Vi切平面上的投影。

(2)計(jì)算原插入向量

vip=lave(ei(i-1)+ei(i+1))

(4)

(3)結(jié)合原插入向量和局部曲率建立加權(quán)函數(shù)

式中:ω1+ω2=1(本文取ω1=0.65)。

圖4 局部平面極坐標(biāo)

(5)最后,可得插入向量vix=laveRnr,其中R為繞nS逆時(shí)針旋轉(zhuǎn)φ角的旋轉(zhuǎn)矩陣。

當(dāng)需要新增2個(gè)點(diǎn)時(shí),算法基本過程同上,只需對新增的兩個(gè)向量分別進(jìn)行求解即可。對于非大面積孔洞,Vi的法向量無需修正。每次推進(jìn)后,都以當(dāng)前邊界點(diǎn)集更新波前,直到修補(bǔ)完成。

本文通過表征頂點(diǎn)周邊局部聚攏趨勢的向量來修正頂點(diǎn)的原法向量,使得推進(jìn)方向向孔洞的中心聚攏,從而可以快速修補(bǔ)趨于發(fā)散的大面積孔洞。結(jié)合邊界點(diǎn)鄰點(diǎn)的平均曲率和原插入向量建立加權(quán)函數(shù),利用局部平面極坐標(biāo)求解函數(shù)值最小時(shí)的新增向量與頂點(diǎn)修正法向量間的夾角,獲得最終的新增向量,因此新增向量既保持了局部曲率,又使新增三角面片均勻規(guī)則。

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

為驗(yàn)證本文算法的孔洞修補(bǔ)效果,在主頻3.3 GHz、內(nèi)存8 GB的計(jì)算機(jī)上,利用VS2013開發(fā)網(wǎng)格修補(bǔ)軟件,并對球模型和XTBodyScan快速人體掃描系統(tǒng)掃描的人體模型進(jìn)行網(wǎng)格修補(bǔ)。

圖5a存在缺失部分的球模型,圖5b、5c、5d分別為傳統(tǒng)波前法、隱式曲面法[10]和本文波前法修補(bǔ)結(jié)果。從圖中可以看出,傳統(tǒng)波前法僅僅封閉了模型,而本文算法和隱式曲面法都保持了較好的特征。

圖6a為人體掃描模型頭部截取部分,該模型的孔洞有153個(gè)邊界點(diǎn)且孔洞趨于發(fā)散,傳統(tǒng)波前法無法修補(bǔ)該孔洞。圖6b是隱式曲面法修補(bǔ)人頭模型孔洞的結(jié)果;圖6c是隱式曲面法生成的新增三角面片,修補(bǔ)結(jié)果出現(xiàn)了大量自相交的三角面片,這是因?yàn)樵摽锥蹿呌诎l(fā)散,擬合出的隱式曲面難以符合孔洞的收攏趨勢,同時(shí)也導(dǎo)致了投射到隱式曲面上新增點(diǎn)不均勻,從而產(chǎn)生不均勻的三角面片。圖6d是本文算法修補(bǔ)結(jié)果;圖6e顯示本文算法新增的三角面片大小均勻,形狀規(guī)則;圖6f是本文算法的局部細(xì)節(jié)情況,可見新增面片與原孔洞邊界面片間有良好的過渡。

圖7a為人體足部掃描模型,足底孔洞有319個(gè)邊界點(diǎn),孔洞空間形狀復(fù)雜且趨于發(fā)散。傳統(tǒng)波前法和隱式曲面法皆無法修補(bǔ)該孔洞。圖7b、7c分別為本文算法修補(bǔ)后的新增面片及局部細(xì)節(jié),修補(bǔ)后的新增面片均勻規(guī)則,且與邊界面片過渡處光滑自然。

圖8a為人體全身掃描模型,該模型中有孔洞196個(gè),其中大面積孔洞11個(gè)。圖8b為本文算法修補(bǔ)結(jié)果,圖8c為部分孔洞修補(bǔ)細(xì)節(jié),修補(bǔ)整個(gè)模型僅耗時(shí)26.8 s,且保持了孔洞的局部特征。

表1統(tǒng)計(jì)了以上6個(gè)孔洞的修補(bǔ)信息。三角形品質(zhì)因子Q為三角形最短邊與外接圓半徑比,三角形越接近正三角形,則Q越接近1.73。本文以Q大于1.39的三角面片為高品質(zhì)三角形[18],統(tǒng)計(jì)其與新增面片總數(shù)的比值。從表中可以看出,本文算法修補(bǔ)各類孔洞所產(chǎn)生的三角面片中,高品質(zhì)面片都在90%以上,且修補(bǔ)時(shí)間短,效率高。

(a)球模型 (b)傳統(tǒng)波前法 (c)隱式曲面法(d)本文算法圖5 不同方法球模型修補(bǔ)效果對比

(a)頭部模型 (b)隱式曲面法修補(bǔ)效果 (c)隱式曲面法新增面片

(d)本文算法修補(bǔ)結(jié)果(e)本文算法新增面片 (f)本文算法修補(bǔ)細(xì)節(jié)圖6 不同方法頭部模型修補(bǔ)結(jié)果對比

(a)足部模型 (b)新增面片 (c)局部細(xì)節(jié)圖7 足部掃描模型修補(bǔ)結(jié)果

(a)原始模型 (b)修補(bǔ)結(jié)果

(c)孔洞1修復(fù)細(xì)節(jié) (d)孔洞2修復(fù)細(xì)節(jié) (e)孔洞3修復(fù)細(xì)節(jié)圖8 人體全身模型

孔洞新增點(diǎn)數(shù)新增面片數(shù)修補(bǔ)時(shí)間/s高品質(zhì)面片與新增面片之比/%球孔洞521250.04794.41頭部孔洞2 1924 5391.18399.10足部孔洞4 97210 2833.16297.53孔洞19892 1750.60793.68孔洞24299900.34690.51孔洞31333160.13693.35

4 結(jié) 論

(1)本文算法對于邊界點(diǎn)數(shù)超過50的孔洞,在迭代推進(jìn)中對最小內(nèi)角的頂點(diǎn)進(jìn)行了法向量修正。利用頂點(diǎn)前后局部邊界點(diǎn)的聚攏趨勢信息獲取頂點(diǎn)法向量的修正向量,修正后的法向量包含了局部聚攏信息,快速地修補(bǔ)趨于發(fā)散的大面積孔洞。

(2)本文算法結(jié)合了原插入向量和局部Taubin曲率建立權(quán)函數(shù),通過極坐標(biāo)轉(zhuǎn)換獲取權(quán)函數(shù)值最小時(shí)的新增點(diǎn)空間坐標(biāo)。新增的面片與原始邊界面片過渡平滑,且網(wǎng)格大小均勻,形狀規(guī)則。

(3)本文在VS2013開發(fā)環(huán)境下開發(fā)了網(wǎng)格修復(fù)軟件,完成了對人體掃描模型的快速修復(fù)。算法具有較高的效率和魯棒性,無論對人為操作形成的孔洞還是掃描信息缺失形成的孔洞都有較好的修復(fù)效果。為快速修補(bǔ)掃描模型中大面積缺失以及趨于發(fā)散的孔洞提供了一種思路。對人體掃描模型修復(fù)、3D反求、個(gè)性定制等都具有重要意義。