王利娟

(太原科技大學 華科學院，山西 太原 030024)

在三維數(shù)字掃描儀幾何獲取能力持續(xù)增強的過程中，通過掃描方式數(shù)字化，使現(xiàn)實世界中的復(fù)雜物體轉(zhuǎn)變?yōu)槿S數(shù)字幾何模型.使用大量的點云促進了三維模型獲取、傳輸和存儲的研究.點云微分幾何量對于三維形狀理解與感知尤為重要，以此實現(xiàn)后續(xù)幾何造型與編輯.各采樣點處的曲率、法向等尤為重要，法向指的是計算機圖形學基本幾何量，比如模型簡化、曲面重建、光線跟蹤等，都和法向估計具有密切關(guān)系[1].以此，對點云模型微分幾何量的研究具有重要意義.

1 三階局部擬合曲面

利用最小二乘法與鄰域構(gòu)造代數(shù)曲面的方法實現(xiàn)離散網(wǎng)格模型頂點微分幾何屬性的估算，目前，Razdan等人提出了將雙二次Bezire參數(shù)曲面作為基礎(chǔ)的擬合局部區(qū)域估算微分幾何屬性的方法，此方法簡化了參數(shù)曲面的構(gòu)造，并且設(shè)置了具備噪聲的網(wǎng)格模型，方法中的權(quán)因子與調(diào)節(jié)矩陣能夠提高擬合曲面.曲率和二階導(dǎo)數(shù)具有密切關(guān)系，而且具有大量局部幾何形狀.因此，本文利用加權(quán)雙三次Bezier曲面擬合網(wǎng)格頂點和鄰域.

雙三次Bezier曲面公式為：

公式中的Bi，3(u)，Bj，3(v)指的是Bernstein基函數(shù)，bij指的是Bezier曲面控制頂點.

本文利用雙三次Bezier曲面對給定頂點pi與周圍2-鄰域網(wǎng)格頂點進行擬合，利用次擬合頂點對擬合曲面控制頂點bij進行擬合.假設(shè)參數(shù)曲面中擬合點所對應(yīng)(ui，vi)參數(shù)，就要對此參數(shù)進行計算[2].

假設(shè)頂點pi鄰域中的頂點有n個，所以就要對此頂點法向量實現(xiàn)算術(shù)平均，從而得出pi點公共法向量N.之后，創(chuàng)建將pi作為原點并且垂直此法向量的切平面.在此平面中創(chuàng)建笛卡兒坐標系，假設(shè)此平面中鄰域點的投影點到原點方向為x-軸，垂直方向為y-軸.此平面中全部鄰域頂點的投影點處于同一個矩形區(qū)域中，此矩形利用參數(shù)到標準[0，1]2區(qū)域中轉(zhuǎn)變.此投影點坐標值也就是參數(shù)曲面擬合點參數(shù)，在投影擬合點處于此切平面的時候，假如投影點重合或者相交，使切平面原點改變，從而解決此問題.

得出頂點pi與擬合點參數(shù)(ui，vi)之后，就能夠得出線性方程組Ax=B：

針對方程組Ax=B，能夠得到x中全部控制頂點bij，以此得出局部擬合曲面.但是在利用最小二乘法對此方程組求解的時候，得出局部擬合曲面無效[3].為了提高局部擬合曲面精準率，可以設(shè)置調(diào)節(jié)矩陣和權(quán)因子：

為了提高局部擬合曲面的光滑度，要均勻分布雙三次Bezier曲面控制頂點.通過實驗結(jié)果分析，以下矩陣S為良好選擇：

權(quán)因子α能夠在[0，1]以模型噪聲密度調(diào)節(jié)，在具有大量噪聲的時候，α設(shè)置低值；相反，α設(shè)置高值.在缺省逼近下，使其設(shè)置為0.8.針對以上方程組，利用最小二乘法求出控制頂點，以此能夠得出雙三次局部擬合曲面.這個時候頂點p1就是局部擬合曲面中點B(u1，v1)，從而對頂點p1的微分幾何屬性進行估算[4].

2 曲面擬合與法向擬合

2.1 法向擬合

通過理算數(shù)據(jù)重新創(chuàng)建連續(xù)曲面，對參數(shù)曲面尋找，以此實現(xiàn)采樣點到曲面距離最小優(yōu)化與平方.通過離散曲面對曲率等二階微分量估計，并不是局部曲面擬合.充分考慮點位置為曲面零階微分量，法向指的是一階微分量.利用分析可以看出來，曲面擬合方法指的是在零階微分量中最小化采樣點與曲面的差別.針對將法向誤差作為主要目標函數(shù)得到最優(yōu)曲面問題，也就是法向擬合.曲面二階微分量和一階微分量具有密切關(guān)系，因為微分計算針對噪聲較為敏感，所以針對帶噪聲離散數(shù)據(jù)二階微分量估計，將法向作為基礎(chǔ)的擬合方法針對點位置來說，具有良好的性能，以下就對此方法進行說明[5].

2.2 擬合算法

分析二階微分量，要實現(xiàn)兩階或者以上的多項式曲面階次的擬合，也是使用二階多項式曲面.本文對利用二次、三次多項式曲面實驗進行擬合，將法向擬合算法QN、基于二次多項式曲面擬合算法QP、三次多項式曲面的曲面加法項擬合算法CPN、基于三次多項式曲面法向擬合算法CN等算法實現(xiàn)對比.對針對二次多項式曲面擬合，QP擬合曲面方程公式為：

算法QN的擬合曲面方程為：

公式中的(x，y，z)指的是擬合點在局部坐標系中的三維坐標方程，(nx，ny，nz)指的是對應(yīng)點法向量，a，b，c為單估計二次多項式曲面系數(shù)約束方程表示為：

公式中的a，b，c，d，e，f，g指的是需要估計的三次多項式曲面系數(shù)[6].

2.3 實驗結(jié)果

本文設(shè)計對比試驗對以下情況研究，不同擬合差別為：

其一，離散數(shù)據(jù)點沒有噪聲，已知各個采樣點處的曲面準確法向；

其二，離散數(shù)據(jù)點沒有噪聲，但是各個采樣點中的曲面準確法向未知；

其三，離散數(shù)據(jù)點噪聲明顯，并且采樣點曲面未知精準法向.

在圓環(huán)(R=2，r=1)與測試曲面中隨機采樣5 000點能夠得出無噪聲點云模型，也就是曲面參數(shù)方程，計算曲面中法向、曲率與主方向中精準信息，以此對不同條件下算法估計誤差進行對比.為了實現(xiàn)不同微分量估計算法的魯棒性，在數(shù)據(jù)合成過程中以各點法線方向中添加不同幅度Gauss噪聲，噪聲方差和點云數(shù)據(jù)的距離中值為0.1，0.2，…，0.9，1.圖1為模型中估計平均絕對誤差[7].

圖1 模型中估計平均絕對誤差

通過分析表示：

其一，QP算法性能最差，CN和QN性能基本相同；

其二，CPN與CN算法的性能曲線基本重合，以此表示在法向擬合過程中，新添加的點位置約束無法提高二階微分量的估計性能.

通過此情況表示，在對點云曲面二階微分量進行估計的過程中，法向擬合性優(yōu)于點位置曲面擬合性能，數(shù)據(jù)點的噪聲比較大，此表現(xiàn)更加明顯.以此可以看出，由于法向擬合使用鄰域中全部數(shù)據(jù)點法向信息，即便是法向信息并不是完全可靠.曲面擬合利用一點處的法向信息，都具有大量有效信息，可得出更加精準的結(jié)果[8].

3 點云曲率估計

以魯棒統(tǒng)計學理論，離群點會對曲率估計結(jié)果造成影響.使用向前搜索算法，在進行搜索的過程中使用最小二乘中位數(shù)創(chuàng)建沒有離群點的初始子集，兩者結(jié)合在有離群點點云模型中使用.

3.1 最小二乘中位數(shù)法

本文通過LMS方法對問題求解，將其應(yīng)用到曲率估計問題中.最小二乘中位數(shù)是指魯棒回歸方法，利用最小化殘差絕對值中位數(shù)，對估計模型從參數(shù)魯棒性進行估計，最小二乘和函數(shù)為中位數(shù)，使斷點要求得到滿足，斷點使估計成為任意大非正常值需要離群點最小比例.轉(zhuǎn)變成以下的目標函數(shù)[9]：

(1)

為了充分考慮點pl和點pj的距離影響，對(1)式進行改進，使用相應(yīng)權(quán)值函數(shù)，那么(1)式就是：

(2)

將(2)式作為加權(quán)LMS最優(yōu)化問題，第j個點殘差絕對值為加權(quán)形式.

3.2 向前搜索算法和向后方法

最初DP算法為向后方法，在點云數(shù)據(jù)集合中實現(xiàn)任意三維點的投影計算，在之后算法迭代時，逐漸移除數(shù)據(jù)集中小權(quán)值數(shù)據(jù)點，降低參與計算點數(shù)量，使算法計算精度得到提高.但是，向后方法問題無法對點云數(shù)據(jù)中的離群點問題解決，具有比較大的離散點權(quán)值，向后無法使數(shù)據(jù)點移除，從而導(dǎo)致出現(xiàn)錯誤的投影計算結(jié)果.向前搜索算法的思想為：對樣本集合進行選擇，此子集沒有離群點，作為算法開始，在迭代過程中，在計算中添加估計量樣本，在達到閾值時將算法迭代結(jié)束.以此表示，算法每次迭代都沒有離群點的時候?qū)崿F(xiàn)模型參數(shù)估計，有效保證算法的魯棒性，使估計結(jié)果的正確性得到提高.

3.3 向前搜索算法的過程

3.3.1 確定工作子集

為了降低算法處理的計算時間，使估計精度提高，針對大規(guī)模點云模型通過點云數(shù)據(jù)集合中數(shù)量小的子集，也就是工作子集，使算法效率得到提高.假設(shè)點云數(shù)據(jù)集合為CN，某采樣點工作子集為cn，以權(quán)值大小選擇cn中元素.對于方向投影，給出創(chuàng)建cn的方法[10].首先對CN中所有點權(quán)值集合{aj}計算，之后對局部變量aumic進行定義：

公式中的ktol指的是常數(shù)，amax與amean指的是權(quán)值集合最大值與平均值.對于ktol不容易控制的問題，針對權(quán)值集合{aj}實現(xiàn)降序排序，之后選擇第n個權(quán)值作為aumic.針對n的大小，簡單選擇300或者在大點云規(guī)模的時候使n=N/100.本文對工作子集考慮，對采樣點鄰域大小確定，實現(xiàn)空間歐式距離考慮，實現(xiàn)aj的計算，所以本文也利用創(chuàng)建的k-d樹的方法創(chuàng)建工作子集.

3.3.2 LMS的過程

向前搜索算法首先創(chuàng)建初始子集，通過最小二乘中位數(shù)法進行.k為初始子集的大小，如果選擇小的k，就無法計算有效點.在k增加中，算法要大量迭代次數(shù).假如k比較大，那么算法對于離群點比較敏感，一般使用k=p，p就是模型參數(shù)個數(shù)，p值為3.

為了避免LMS的過程中出現(xiàn)子集離散點，就要通過隨機采樣實現(xiàn).首先，通過工作子集選擇k點，對半徑t計算，對點殘差絕對值對中位數(shù)計算，重復(fù)以上過程T次，實現(xiàn)T個候選解生成，計算結(jié)果為最小中位數(shù)的解.根據(jù)統(tǒng)計學理論，LMS具有獨立樣本點，假設(shè)g指的是通過cn中隨機采樣得出的點為非離群點概率，在T次重復(fù)k個點隨機選擇之后，實現(xiàn)初始子集的選擇，概率設(shè)置為P=1-(1-gk)T.為了提高P值，使用大的T值.針對每次選擇k個點之后，LMS過程中使N-k個點殘差進行排序，以此利用大量空間與時間.所以，創(chuàng)建工作子集，使內(nèi)存空間與計算時間得到降低[11].

本文使用LMS方法創(chuàng)建初始子集Q，利用T次隨機篩選，保證Q中沒有離群點，在Q中將球擬合方法作為基礎(chǔ)，計算P點曲率大小，在迭代時在Q點添加ck-Q的最小殘差點，在曲率計算與上次計算達到設(shè)置閾值時終止算法[12].完整算法為：

圖2 球的點云模型

1)給定云數(shù)據(jù)集與采樣點，實現(xiàn)k-d樹的創(chuàng)建，對pi點鄰域查詢，創(chuàng)建工作子集，對最大迭代次數(shù)、臨時子集進行初始化[13].

2)以最小二乘中位數(shù)創(chuàng)建出示自己，對曲率進行計算.

3)在迭代處比MAXITER小的時候，使臨時子集=Q，cramain=cn*Q，對cramain中全部點殘差計算，在臨時子集中設(shè)置最小殘差，基于球擬合方法對曲率大小進行計算，設(shè)為rnew.

4)對|rnew-r|>rt進行判斷.

IF：|rnew-r|

ELSE:令r=rnew，Q=ctemp，轉(zhuǎn)3.

5)輸出pi點曲率[14].

4 算法仿真

針對理想情況，通過球模型計算仿真.

本文使用傳統(tǒng)方法與本文方法的實驗結(jié)果詳見表1.

表1 不同方法的曲率估計

本文計算點云模型采樣點有3 125個，選擇最大鄰域為30，通過表1表示，使用傳統(tǒng)方法所計算曲率最大值和最小值的誤差為0.066 396，使用本文方法的誤差為0.010 68，所以本文方法存在一定收斂性與穩(wěn)定性[15].但是，在計算時間方面，本文方法要比傳統(tǒng)方法慢，所以在實現(xiàn)采樣點估計曲率的過程中，算法實現(xiàn)過程中要創(chuàng)建工作集，通過LMS方法創(chuàng)建初始子集，離散點缺少，在估計LMS算法時占據(jù)時間比較大.另外，在后續(xù)迭代的時候，在計算中添加工作集最小殘差點，所以消耗時間比較大[16].本文分析方法的穩(wěn)定性較高，但是算法時間比較長，所以今后就要研究計算時間和穩(wěn)定性之間的平衡點.

5 結(jié)束語

基于點云模型曲率估計的問題，并且存在離群點的情況.本文通過魯棒統(tǒng)計學向前搜索實現(xiàn)全新曲率魯棒估計方法的設(shè)計，通過仿真結(jié)果表示，本文分析方法魯棒性比較強，使離群點的問題得到解決.