帶法向約束的隱式T樣條曲線重構(gòu)

任浩杰，壽華好，莫佳慧，張航

浙江工業(yè)大學(xué)理學(xué)院，杭州 310023

0 引 言

在計(jì)算機(jī)輔助幾何設(shè)計(jì)和計(jì)算機(jī)圖形學(xué)中，采用光滑曲線擬合點(diǎn)云是一個(gè)廣泛研究的問(wèn)題(Vrady等，1997)。通過(guò)激光掃描、X射線斷層成像等先進(jìn)采樣設(shè)備獲取測(cè)量數(shù)據(jù)，并對(duì)其進(jìn)行數(shù)據(jù)擬合，可以實(shí)現(xiàn)對(duì)原模型進(jìn)行大致的重建及功能恢復(fù)。但有些情況下，獲取的數(shù)據(jù)點(diǎn)不僅是散亂的坐標(biāo)信息，還包含一些約束形狀的條件，如光學(xué)工程領(lǐng)域?qū)в蟹ㄏ蚣s束的數(shù)據(jù)點(diǎn)的處理(胡巧莉和壽華好，2014；胡良臣和壽華好，2016)。

與參數(shù)曲線相比，隱式曲線不需要對(duì)散亂數(shù)據(jù)點(diǎn)進(jìn)行參數(shù)化就可以描述具有復(fù)雜集合形狀的對(duì)象。傳統(tǒng)的基于B樣條的隱式曲線重構(gòu)已有了一系列高效、快速和穩(wěn)定的算法(Yang等，2005；Liu等，2017；Hamza等，2020)。Yang等人(2005)提出了一種基于B樣條的隱式曲線重構(gòu)模型，能夠處理具有復(fù)雜拓?fù)浣Y(jié)構(gòu)的點(diǎn)云。Hamza等人(2020)將漸進(jìn)迭代逼近法應(yīng)用于隱式B樣條曲線和曲面重建，提高了重建結(jié)果的質(zhì)量，但是由于隱式B樣條曲線的控制網(wǎng)格的控制頂點(diǎn)需要整行整列地規(guī)則排列，使得在局部細(xì)分方面存在一定的局限性，會(huì)造成控制點(diǎn)冗余現(xiàn)象。Sederberg等人(2003，2004)提出了T樣條方法，允許出現(xiàn)T節(jié)點(diǎn)，在繼承B 樣條曲面優(yōu)點(diǎn)的基礎(chǔ)上，又增加了控制點(diǎn)較少、局部細(xì)分等優(yōu)勢(shì)，是一項(xiàng)很有前途的技術(shù)，在逆向工程等領(lǐng)域得到了廣泛研究。在T樣條擬合方面，Zheng等人(2005)首先提出了在z-map條件下的T樣條曲面重構(gòu)。Wang和Zheng(2007，2013)將三角網(wǎng)格轉(zhuǎn)化為T(mén)樣條曲面，并提出了曲率引導(dǎo)下的T樣條擬合方法。童偉華等人(2006)提出了隱式T樣條曲面，將T網(wǎng)格從2維推廣至3維，實(shí)現(xiàn)了曲面重構(gòu)。唐月紅等人(2011)提出一種新的隱式T樣條曲面重建算法。近年來(lái)，一些快速擬合T樣條的方法相繼提出。Lin(2012)、Lin和Zhang(2013)將漸進(jìn)T樣條數(shù)據(jù)擬合算法用于擬合大數(shù)據(jù)集，迭代速度穩(wěn)定，且不受未知T網(wǎng)格頂點(diǎn)數(shù)量增加的影響。Lu等人(2020)提出了基于區(qū)域分割的T樣條擬合方法。

基于上述有關(guān)T樣條的研究，本文將T樣條函數(shù)應(yīng)用于曲線重構(gòu)問(wèn)題，提出了一種帶法向約束的隱式T樣條曲線重構(gòu)算法。通過(guò)結(jié)合曲率自適應(yīng)地調(diào)整了采樣點(diǎn)的疏密程度，利用加入曲線偏移點(diǎn)和光滑項(xiàng)消除額外零水平集，同時(shí)加入法向項(xiàng)約束曲線的法向方向，初步得到一條隱式T樣條曲線。同時(shí)，優(yōu)化了局部細(xì)分的算法，對(duì)曲線進(jìn)行局部修正，在降低曲線誤差的前提下，減少了插入控制系數(shù)的數(shù)量，最終得到一條滿足數(shù)據(jù)點(diǎn)和法向約束的隱式T樣條曲線。

1 隱式T樣條曲線重建算法描述

1.1 隱式T樣條曲線方程

若隱式曲線通過(guò)隱函數(shù)f:Ω?R2→R，則稱S=f-1(0)={p∈Ω:f(p)=0}為隱式曲線。若函數(shù)f為T(mén)樣條函數(shù)，則隱式曲線S稱為隱式T樣條曲線。

定義在2維T網(wǎng)格上的隱式T樣條曲線方程為

(1)

式中，ci是控制系數(shù)。控制系數(shù)ci對(duì)應(yīng)的T樣條基函數(shù)Bi(x,y)為

Bi(x,y)=N[si](x)N[ti](y)

(2)

式中，N[si](x)和N[ti](y)是三次B樣條基函數(shù)，相應(yīng)的節(jié)點(diǎn)向量為si=[si0,si1,…,si4]和ti=[ti0,ti1,…,ti4]。此時(shí)，N[si](x)可表示為

式中，

由式(1)確定的二元函數(shù)f(x,y)稱為隱式T樣條函數(shù)，由f-1(0)定義的曲線稱為隱式T樣條曲線。

1.2 曲線重建算法

f(xl,yl)=dl,l=n+1,n+2,…,N

(3)

令vi表示曲線在pi處的單位切向量，顯然

vi·ni=0,i=1,2,…,n

由此可以得到n個(gè)單位切向量vi的值。于是問(wèn)題轉(zhuǎn)化為要求函數(shù)f滿足

(4)

隱式T樣條曲線重構(gòu)算法步驟如下：

輸入：散亂數(shù)據(jù)點(diǎn)集pi和對(duì)應(yīng)的單位法向量ni,i=1,2,…,n。

輸出：T網(wǎng)格和網(wǎng)格點(diǎn)對(duì)應(yīng)的控制系數(shù)。

1)對(duì)輸入的數(shù)據(jù)進(jìn)行預(yù)處理，通過(guò)曲率自適應(yīng)調(diào)整采樣點(diǎn)的疏密程度，利用單位法向量加入偏移點(diǎn)作為輔助點(diǎn)，同時(shí)求出每個(gè)數(shù)據(jù)點(diǎn)的單位切向量。

2)利用二叉樹(shù)對(duì)數(shù)據(jù)點(diǎn)進(jìn)行細(xì)分，自動(dòng)生成合理的2維T網(wǎng)格。給T網(wǎng)格的每條邊賦予一個(gè)節(jié)點(diǎn)區(qū)間值，同時(shí)給T網(wǎng)格的邊界加入相應(yīng)的虛邊,并給虛邊賦予一個(gè)非負(fù)值。

3)利用T網(wǎng)格獲取網(wǎng)格上每個(gè)點(diǎn)的局部坐標(biāo)系，從而得到每個(gè)控制系數(shù)對(duì)應(yīng)的節(jié)點(diǎn)向量，進(jìn)而得到T樣條基函數(shù)。

4)建立合適的優(yōu)化模型，并用最小二乘法求得T樣條的控制系數(shù)，獲得隱式T樣條曲線。

5)對(duì)得到的隱式T樣條曲線與給定的數(shù)據(jù)點(diǎn)集和單位法向量進(jìn)行分析，判斷是否達(dá)到精度要求。在誤差較大的區(qū)域插入新的控制系數(shù)進(jìn)行修正，然后更新節(jié)點(diǎn)向量，轉(zhuǎn)步驟4)，直到滿足精度要求。

2 構(gòu)造2維T網(wǎng)格

將隱式T樣條應(yīng)用到曲線重建的關(guān)鍵問(wèn)題是構(gòu)造合理的2維T網(wǎng)格，使其控制系數(shù)滿足一定的拓?fù)潢P(guān)系。

T樣條是允許出現(xiàn)T節(jié)點(diǎn)的矩形網(wǎng)格，控制網(wǎng)格的頂點(diǎn)不要求整行整列的排列，因此構(gòu)造T網(wǎng)格可以在數(shù)據(jù)點(diǎn)密集的地方多插入控制系數(shù)，在數(shù)據(jù)點(diǎn)稀疏的地方少插入控制系數(shù)，使T網(wǎng)格的網(wǎng)格點(diǎn)的數(shù)量相比B樣條的控制網(wǎng)格大幅減少，在保證類(lèi)似精度的前提下提高了重建曲線的效率。在2維平面上利用二叉樹(shù)方法進(jìn)行細(xì)分的步驟如下：

1)定義一個(gè)細(xì)分的最大次數(shù)和一個(gè)閾值，其中，閾值表示每個(gè)矩形塊中允許包含的最大點(diǎn)數(shù)。

2)計(jì)算每個(gè)矩形塊中包含的數(shù)據(jù)點(diǎn)數(shù)量，若某個(gè)矩形塊包含的數(shù)據(jù)點(diǎn)個(gè)數(shù)大于給定的閾值，則對(duì)其進(jìn)行細(xì)分。具體來(lái)說(shuō)，假定該矩形塊的左下角坐標(biāo)為(smin,tmin)，右上角坐標(biāo)為(smax,tmax)，T網(wǎng)格s方向的長(zhǎng)度為sm，t方向的長(zhǎng)度為tm。如果(smax-smin)/sm≥(tmax-tmin)/tm，那么在矩形塊s=[(smax+smin)/2]處將矩形塊分成兩塊；否則，在t=[(tmax+tmin)/2]處細(xì)分矩形塊。

3)重復(fù)步驟2)，直到每個(gè)矩形塊包含的點(diǎn)數(shù)小于閾值或者達(dá)到最大的細(xì)分次數(shù)。

4)輸出細(xì)分后得到的T網(wǎng)格。

通過(guò)細(xì)分得到的T網(wǎng)格，不僅要保存T網(wǎng)格每個(gè)頂點(diǎn)的坐標(biāo)，還需要通過(guò)節(jié)點(diǎn)區(qū)間值得到每個(gè)頂點(diǎn)對(duì)應(yīng)的局部坐標(biāo)系。

圖1是由一條封閉曲線構(gòu)造的T網(wǎng)格。其中圖1(a)是曲線的初始采樣點(diǎn)，包含466個(gè)數(shù)據(jù)點(diǎn)，圖1(b)是通過(guò)平面二叉樹(shù)細(xì)分生成的2維T網(wǎng)格，包含131個(gè)網(wǎng)格點(diǎn)。

圖1 2維T網(wǎng)格構(gòu)造Fig.1 The construction of two dimensional T-meshes((a)the initial sampling points；(b)two dimensional T-meshes)

構(gòu)造2維T網(wǎng)格后，因?yàn)槊總€(gè)控制系數(shù)ci都對(duì)應(yīng)T網(wǎng)格上的各個(gè)網(wǎng)格頂點(diǎn)，因此可以得到控制系數(shù)ci的數(shù)量。然后通過(guò)T網(wǎng)格獲得每個(gè)控制系數(shù)對(duì)應(yīng)的節(jié)點(diǎn)向量si和ti，從而確定控制系數(shù)的基函數(shù)。本文在構(gòu)造T網(wǎng)格后，保存了網(wǎng)格頂點(diǎn)、邊、節(jié)點(diǎn)區(qū)間值以及每個(gè)小矩形塊的信息，以便對(duì)T網(wǎng)格進(jìn)行局部修正。

3 模型擬合

通過(guò)T網(wǎng)格構(gòu)造，得到每個(gè)控制系數(shù)對(duì)應(yīng)的基函數(shù)后，尚需找到合適的隱式T樣條函數(shù)f滿足式(4)中的條件。顯然，待求的未知數(shù)即控制系數(shù)的數(shù)量遠(yuǎn)少于條件中給出的方程的個(gè)數(shù)，因此需要建立合適的優(yōu)化模型，從而找到在某種意義下的最優(yōu)解。此時(shí)，隱式曲線重構(gòu)問(wèn)題轉(zhuǎn)化為最小值優(yōu)化問(wèn)題，得到的目標(biāo)方程為

Efit(c)=Ep(c)+ω1EN(c)+ω2EG(c)

(5)

式中，c=[c1,c2,…,cm]T為T(mén)網(wǎng)格中待求的控制系數(shù)，Ep(c)表示擬合誤差平方和；EN(c)表示法向項(xiàng)，ω1為法向項(xiàng)權(quán)值；EG(c)表示光滑項(xiàng)，ω2為光滑項(xiàng)系數(shù)。這里，Ep(c)可以表示為

EN(c)可以表示為

EG(c)可以表示為

為了求解優(yōu)化問(wèn)題，將式(5)的目標(biāo)函數(shù)對(duì)控制系數(shù)c的每個(gè)分量求偏導(dǎo)，并使其等于零，即

(6)

此時(shí)，問(wèn)題轉(zhuǎn)化為求解

(7)

解該線性方程組即可得到T網(wǎng)格中控制系數(shù)的值，從而得到隱式T樣條曲線。

4 T網(wǎng)格局部細(xì)分

1)給定一個(gè)容許誤差σ>0，細(xì)分比率α和一個(gè)閾值z(mì)，這里的閾值小于上面構(gòu)造T網(wǎng)格時(shí)給定的閾值。

2)計(jì)算每個(gè)采樣點(diǎn)pi對(duì)應(yīng)的誤差Δi，若所有采樣點(diǎn)的誤差均小于容許誤差σ，則此時(shí)的隱式T樣條曲線即為最終的曲線，循環(huán)終止；否則，找到誤差不滿足的采樣點(diǎn)處于哪些矩陣塊后，執(zhí)行步驟3)。

3)計(jì)算需要細(xì)分的矩形塊中包含的數(shù)據(jù)點(diǎn)的數(shù)量，若某矩形塊的數(shù)據(jù)點(diǎn)數(shù)量小于給定閾值z(mì)，則將該矩形塊排除需要細(xì)分的序列。

4)統(tǒng)計(jì)需要細(xì)分的矩形塊的總數(shù)量，與細(xì)分比率α相乘，得到的值μ即為實(shí)際細(xì)分的數(shù)量。根據(jù)矩形塊包含數(shù)據(jù)點(diǎn)的最大誤差對(duì)矩形塊從大到小進(jìn)行排序，此時(shí)，對(duì)前μ個(gè)矩形塊細(xì)分。

5)更新T樣條基函數(shù)，重新反求控制系數(shù)，得到新的隱式T樣條曲線。

6)重復(fù)步驟2)—5)，直到循環(huán)結(jié)束，輸出T網(wǎng)格和相應(yīng)的控制系數(shù)。

5 實(shí)驗(yàn)與比較

選取3個(gè)封閉曲線實(shí)例對(duì)隱式T樣條曲線重建算法的性能進(jìn)行驗(yàn)證。首先結(jié)合曲率自適應(yīng)地調(diào)整采樣點(diǎn)的疏密程度，然后進(jìn)行曲線重構(gòu)。現(xiàn)有的T樣條重構(gòu)的方法大多集中在曲面上，實(shí)驗(yàn)時(shí)，選取童偉華等人(2006)和唐月紅等人(2011)的隱式T樣條曲面重構(gòu)方法用于隱式T樣條曲線重建，分別作為方案1和方案2，其中，方案1通過(guò)添加隱函數(shù)對(duì)x,y求偏導(dǎo)分別等于法向分量的方程避免奇異解，重構(gòu)隱式T樣條函數(shù)；方案2通過(guò)添加偏移點(diǎn)構(gòu)造隱式函數(shù)。然后將兩種方案與本文算法進(jìn)行比較，以驗(yàn)證本文方法的性能。圖2展示了方案1和本文方法對(duì)3條曲線的重建，其中，圖2(a)是初始采樣點(diǎn)顯示的曲線，圖2(b)是構(gòu)造的2維T網(wǎng)格，圖2(c)和圖2(d)分別為方案1和本文方法重構(gòu)的曲線。可以看出，雖然本文方法和方案1都重構(gòu)出了隱式T樣條曲線，但是方案1的方法會(huì)產(chǎn)生一些額外的零水平集，破壞了重構(gòu)效果。

圖2 方案1和本文方法對(duì)3條曲線的重建Fig.2 The reconstruction of three curves using the method 1 and the proposed method((a)the initial sampling points；(b)two dimensional T-meshes；(c)method 1；(d)ours)

本文方法與方案1和方案2的定量比較結(jié)果如表1所示。可以看出，3種方法在數(shù)據(jù)點(diǎn)處的誤差相差不大，但是本文方法在法向誤差處無(wú)論是平均誤差還是最大誤差都是最小的。方案1雖然也能約束法向，但是誤差沒(méi)有本文方法小，同時(shí)會(huì)產(chǎn)生零水平集。方案2重構(gòu)曲率變化較小的曲線時(shí)，法向誤差與方案1差不多，但在實(shí)現(xiàn)曲率變化較大的曲線，如曲線3的手型曲線時(shí)不能有效地約束法向，法向誤差較大。本文對(duì)輸入的數(shù)據(jù)點(diǎn)要求采樣密集，當(dāng)數(shù)據(jù)點(diǎn)比較稀疏時(shí)，對(duì)曲線1這種比較簡(jiǎn)單的曲線影響不大，但對(duì)比較復(fù)雜的曲線在曲率變化較大的位置無(wú)法較好地約束法向誤差。

表1 不同方法重構(gòu)曲線誤差比較Table 1 The comparison of the curve errors between different methods

在網(wǎng)格頂點(diǎn)數(shù)量方面，隱式B樣條需要大量多余的控制點(diǎn)來(lái)滿足拓?fù)浼s束，而隱式T樣條曲線可以大幅減少多余的網(wǎng)格點(diǎn)的數(shù)量。表2給出了3條曲線關(guān)于B樣條網(wǎng)格與T網(wǎng)格頂點(diǎn)數(shù)的比較，其中包括每個(gè)曲線采樣的數(shù)據(jù)點(diǎn)數(shù)、網(wǎng)格在兩個(gè)方向上的節(jié)點(diǎn)數(shù)以及控制頂點(diǎn)數(shù)?？梢钥闯?，3條曲線的T網(wǎng)格頂點(diǎn)數(shù)均小于B樣條控制點(diǎn)數(shù)，從而大幅減少了運(yùn)算量。

表2 B樣條控制頂點(diǎn)數(shù)與T網(wǎng)格頂點(diǎn)數(shù)的比較Table 2 The comparison of the quantities of control points between B-spline and T-spline

6 結(jié) 論

本文針對(duì)帶有法向約束的離散數(shù)據(jù)點(diǎn)集提出了一種有效的隱式T樣條曲線重建算法，較好地實(shí)現(xiàn)了3個(gè)封閉曲線實(shí)例的重建。實(shí)驗(yàn)結(jié)果表明，通過(guò)加入曲線偏移點(diǎn)作為輔助點(diǎn)和在擬合模型中加入光滑項(xiàng)，本文方法成功消除了額外零水平集，提高了重構(gòu)曲線的質(zhì)量。此外，通過(guò)在模型中加入法向項(xiàng)約束，重構(gòu)的曲線會(huì)在逼近數(shù)據(jù)點(diǎn)的同時(shí)滿足數(shù)據(jù)點(diǎn)處的法向約束。本文還優(yōu)化了局部細(xì)分的算法，引入了細(xì)分比率這一概念，減少了插入控制系數(shù)的數(shù)量，提高了運(yùn)算速度。本文將兩種隱式T樣條曲面重構(gòu)的方法應(yīng)用到曲線重構(gòu)上，然后與本文的隱式T樣條曲線重構(gòu)方法進(jìn)行比較?？梢园l(fā)現(xiàn)，在數(shù)據(jù)點(diǎn)誤差精度相差不大的情況下，本文方法在法向誤差精度上有了顯著提高，而法向誤差在光學(xué)反射曲線曲面設(shè)計(jì)等領(lǐng)域有著重要作用。本文將隱式T樣條曲線的網(wǎng)格與隱式B樣條的網(wǎng)格頂點(diǎn)數(shù)量進(jìn)行比較，在兩種控制網(wǎng)格的相同位置插入控制點(diǎn)時(shí)，由于隱式B樣條曲線的網(wǎng)格需要大量多余的控制點(diǎn)來(lái)滿足拓?fù)浼s束，實(shí)驗(yàn)結(jié)果顯示，隱式T樣條的網(wǎng)格頂點(diǎn)數(shù)只有B樣條網(wǎng)格的一半左右。

總之，實(shí)驗(yàn)數(shù)據(jù)和重建的效果圖顯示，本文方法較好地解決了帶法向約束的隱式T樣條曲線重建問(wèn)題。但本文方法仍有不足之處:1)本文方法在重建不光滑的曲線如心形線時(shí)，在尖銳點(diǎn)的附近無(wú)法對(duì)法向進(jìn)行有效約束，有較大的誤差；2)本文方法對(duì)數(shù)據(jù)點(diǎn)要求密集，若數(shù)據(jù)點(diǎn)比較稀疏，則在曲線曲率變化較大的位置將無(wú)法較好地約束法向誤差。有待進(jìn)一步研究。