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

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

0 引 言

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

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

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

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

1.1 隱式T樣條曲線方程

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

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

(1)

式中，ci是控制系數(shù)?？刂葡禂?shù)ci對應的T樣條基函數(shù)Bi(x,y)為

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

(2)

式中，N[si](x)和N[ti](y)是三次B樣條基函數(shù)，相應的節(jié)點向量為si=[si0,si1,…,si4]和ti=[ti0,ti1,…,ti4]。此時，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個單位切向量vi的值。于是問題轉(zhuǎn)化為要求函數(shù)f滿足

(4)

隱式T樣條曲線重構算法步驟如下：

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

輸出：T網(wǎng)格和網(wǎng)格點對應的控制系數(shù)。

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

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

3)利用T網(wǎng)格獲取網(wǎng)格上每個點的局部坐標系，從而得到每個控制系數(shù)對應的節(jié)點向量，進而得到T樣條基函數(shù)。

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

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

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

將隱式T樣條應用到曲線重建的關鍵問題是構造合理的2維T網(wǎng)格，使其控制系數(shù)滿足一定的拓撲關系。

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

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

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

3)重復步驟2)，直到每個矩形塊包含的點數(shù)小于閾值或者達到最大的細分次數(shù)。

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

通過細分得到的T網(wǎng)格，不僅要保存T網(wǎng)格每個頂點的坐標，還需要通過節(jié)點區(qū)間值得到每個頂點對應的局部坐標系。

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

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

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

3 模型擬合

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

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

(5)

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

EN(c)可以表示為

EG(c)可以表示為

為了求解優(yōu)化問題，將式(5)的目標函數(shù)對控制系數(shù)c的每個分量求偏導，并使其等于零，即

(6)

此時，問題轉(zhuǎn)化為求解

(7)

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

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

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

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

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

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

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

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

5 實驗與比較

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

圖2 方案1和本文方法對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ù)點處的誤差相差不大，但是本文方法在法向誤差處無論是平均誤差還是最大誤差都是最小的。方案1雖然也能約束法向，但是誤差沒有本文方法小，同時會產(chǎn)生零水平集。方案2重構曲率變化較小的曲線時，法向誤差與方案1差不多，但在實現(xiàn)曲率變化較大的曲線，如曲線3的手型曲線時不能有效地約束法向，法向誤差較大。本文對輸入的數(shù)據(jù)點要求采樣密集，當數(shù)據(jù)點比較稀疏時，對曲線1這種比較簡單的曲線影響不大，但對比較復雜的曲線在曲率變化較大的位置無法較好地約束法向誤差。

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

在網(wǎng)格頂點數(shù)量方面，隱式B樣條需要大量多余的控制點來滿足拓撲約束，而隱式T樣條曲線可以大幅減少多余的網(wǎng)格點的數(shù)量。表2給出了3條曲線關于B樣條網(wǎng)格與T網(wǎng)格頂點數(shù)的比較，其中包括每個曲線采樣的數(shù)據(jù)點數(shù)、網(wǎng)格在兩個方向上的節(jié)點數(shù)以及控制頂點數(shù)。可以看出，3條曲線的T網(wǎng)格頂點數(shù)均小于B樣條控制點數(shù)，從而大幅減少了運算量。

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

6 結(jié) 論

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

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