任浩杰,壽華好,莫佳慧,張航
浙江工業(yè)大學(xué)理學(xué)院,杭州 310023
在計(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樣條曲線。
若隱式曲線通過(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樣條曲線。
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),直到滿足精度要求。
將隱式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)行局部修正。
通過(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樣條曲線。
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ù)。
選取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
本文針對(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)一步研究。