劉斌,林俊義,黃常標,江開勇

(華僑大學機電及自動化學院,福建泉州362021)

采用移動最小二乘的平面散亂點集曲線重構

劉斌,林俊義,黃常標,江開勇

(華僑大學機電及自動化學院,福建泉州362021)

針對帶狀分布的無序散亂點集的曲線重構問題,采用移動最小二乘法對其進行二次局部加權回歸和細化點云;在迭代過程中,采用逐步減小K-鄰域頂點數(shù)的策略,以兼顧計算效率和精度.對細化后的點云進行重新排序和稀疏,把無序點集有序化;然后,利用現(xiàn)有的B樣條曲線重構技術,對點云進行重構.最后,實例驗證算法的有效性.

曲線重構;散亂點集;移動最小二乘;細化點云;B樣條

曲線擬合在逼近論和幾何造型中都是一個重要的研究課題.從有序散亂點重建曲線,已經有了許多成熟的方法[1-3].近年來,無序數(shù)據(jù)點的曲線重建已逐步受到人們的重視.如Pottmann等[4]將原始的數(shù)據(jù)點集投影到平面網(wǎng)格上,生成二值圖像;Goshtasby[5]先由離散點構造勢函數(shù)并生成灰度圖像,最后利用圖像細化算法來得到重建曲線.但是,文[5]的方法所獲得的重建曲線并不能很好地反映點云端點的形狀,并且重建曲線的準確性、正確性受到網(wǎng)格分辨率的影響.Fang等[6],Taubin等[7]分別利用彈力模型與隱式曲線模型,把已知數(shù)據(jù)點作為約束條件,直接求解曲線參數(shù)并得到重建曲線.文[6-7]的方法常需要優(yōu)化或迭代求解,對于噪音過多的數(shù)據(jù)點集則不夠理想.鐘綱等[8]提出了平面無序點集曲線重建的跟蹤算法.本文利用移動最小二乘(Moving Least-Squares,MLS)方法細化點云,重新對點云排序并進行稀疏,在獲得稀疏的有序點列后,利用B樣條插值技術,獲得點云重構的B樣條曲線.

1 點云細化

1.1 K-鄰近構建

由于點云數(shù)據(jù)只包含點的坐標信息,沒有任何的拓撲結構信息,所以每一點的微分幾何信息如曲率、法矢等,都只能由其最臨近的一些點來決定.搜索點云中任一點的K個最臨近點的方法,一般有柵格法、八叉樹法、近似最近鄰庫(App roximate Nearest Neighbo r,ANN)方法,以及K-d樹方法等.文中采用K-d樹方法來快速構建點云中每一點的K-鄰近.

1.2 局部最小二乘回歸

對于二維空間R2內的點集S={Pi=(xi,yi)|i=1,…,N},采用K-d樹方法建立點集內每一頂點的K-鄰近信息,在局部鄰域內進行加權回歸;利用移動最小二乘方法,使頂點移動到新的位置[9-12].

1.2.1 局部直線擬合 對于點集S內的任一點P＊,由其局部鄰域點集可以擬合一條直線(L:y=ax+ b),系數(shù)a,b的計算式為

式(1)中:K為點P＊的K-鄰近頂點個數(shù)(包括點P＊本身);wi為鄰域內各頂點的權值.權值的選取采用常用的指數(shù)表示函數(shù),即

式(2)中:r=‖Pi-P＊‖2;H為鄰域半徑,選取P＊的K-鄰域中距離P＊最遠的點到P＊的距離作為H值.為了求a和b的值,按照最小二乘法,由式(1)分別對a,b求偏導數(shù),并令其為零,可得到求解a,b的法方程組,其矩陣形式為

解此線性方程組,可求得P＊的K-鄰域最小二乘擬合直線(L:y=ax+b).

1.2.2 基于MLS的投影點計算 進行平移和旋轉變換,構建以P＊為原點,以平行于直線L的方向為x軸的局部坐標系.其平移和旋轉矩陣分別為

式(4)中:θ為局部擬合直線與x軸正向的夾角,逆時針為正,順時針為負.由此,整體的變換矩陣M為

把P＊的K-鄰域內的點集V變換到新的局部坐標系下,得到新的點集～P =V M,即～P ={～pj=(xj, yj)|j=1,…,K};然后,用一個二次曲線(Q～y=a～x2+b～x+c)來逼近該點集.該曲線的計算式為

同樣地,由式(6)分別對a,b,c求偏導數(shù),并令其為零,可得到一組線性方程組.用與求解式(3)同樣的方法,求得局部擬合二次曲線Q.此時,點～P＊(0,0)在曲線Q上的對應點為^P＊(0,c).通過變換矩陣M的逆變換M-1,將^P＊變換回原坐標系,即可得到P＊點經MLS變換后的新點P′=^P＊M-1.

對點集S中的每一點進行同樣的變換,得到一系列新的MLS點,把S中的每一點移動到對應的MLS點,就可使帶狀分布的無序點集得到細化,如圖1所示.

圖1 基于MLS的點云細化Fig.1 Thinning a point cloud using moving lease square

關于K-鄰域中鄰近點個數(shù)K值的選取問題,有賴于點云本身的分布情況和經驗,一般取8～20.K值過大,一方面增加計算成本,另一方面因鄰域過大而使點云上的細節(jié)特征消失;K值過小,則對噪聲點比較敏感,特別是對于帶狀分布的點云,可能導致計算出的局部擬合直線的方向不是沿著曲線的走勢方向,而是沿曲線的橫向而導致計算錯誤.

為了兼顧計算精度與效率,在迭代的初始階段,點云比較粗的時候,采用較大的K值;而隨著迭代次數(shù)的增加,點云被細化,K值也逐漸縮小.

2 排序與重構

在通過MLS方法獲得足夠細化的點云后,將通過對無序點云排序使之有序化,并根據(jù)需要對其進行必要的稀疏化處理,減少點云頂點個數(shù).即可利用現(xiàn)有的B樣條曲線重構技術,將其擬合為非均勻B樣條曲線.

2.1 點集排序與稀疏

設點集S經過MLS細化后所得點集為S′={P′i=(x′i,y′i)|i=1,…,N},從中隨機選出一點P′j.根據(jù)需要指定一個K值,作為點的K-鄰近頂點個數(shù),以決定點云稀疏的程度.如果點云足夠細的話,點P′j及其鄰域內的點近似在一條直線上,那么,搜尋P′j的K-鄰域中距離P′j最遠的點作為下一個搜尋點.

點云排序與稀疏的算法流程有如下6個步驟.(1)從點集中隨機選出一點P′j作為初始點,計算其K-鄰域A及A內各點到P′j的距離,存入數(shù)組dj;按照從大到小的順序對dj排序,把P′j存入排序后的新的點列數(shù)組Pnew中.

(2)設A中距離P′j最遠的點為P′j+1,向量F=P′j+1-P′j表示點P′j到P′j+1的方向.把P′j+1存入排序后的新的點列數(shù)組Pnew中.

(3)計算點P′j+1的K-鄰域B及其各點到P′j+1的距離,并按照從大到小的順序排序.

(4)從已排序的B中循環(huán)找出每一點P′l,計算向量Fnew=P′l-P′j+1與向量F的內積e=Fnew· F,判斷e值的大小.如果e>0,則將P′l存入排序后的新的點列數(shù)組Pnew,以P′l作為新的P′j+1轉入步驟(3)進行迭代;如果e≤0,則繼續(xù)在B中循環(huán).遍歷B后,如果所有e≤0,說明該點是點集的端點,則結束該方向的搜索,轉入步驟(5).

(5)回到初始點P′j,遍歷其K-鄰域A,找出與方向F反側的距離P′j最遠的點作為P′j+1,重復步驟(3),(4),直至搜索到點云的另一端點.

(6)在步驟(4)中,如果點P′l位于初始點P′j的K-鄰域A中,說明點集構成了一個封閉的曲線,則迭代終止.

2.2 點集的B樣條曲線重構

對點云進行有序化稀疏后,即可利用比較成熟的有序點列曲線重構技術對其進行曲線重構.采用3次非均勻B樣條作為重構曲線類型.即采用積累弦長參數(shù)化方法對有序化的點列進行參數(shù)化,從而確定曲線的節(jié)點矢量;然后,根據(jù)節(jié)點矢量反算3次B樣條插值曲線的控制頂點,求解控制頂點時采用拋物線邊界條件.在計算出曲線的控制頂點后,用德布爾算法對其進行正算,得出曲線上的點,其具體計算細節(jié)參照文[13].

圖2 點云細化與曲線重構過程Fig.2 Processof thinning point cloud and curve reconstruction

3 應用實例

算法已通過VC 6.0編程在微機平臺上實現(xiàn).圖2是點云重構的一個例子.圖2(a)是測量鞋楦曲面時所獲得的一條帶狀點云,其頂點個數(shù)為1 141.初始K值取25,經過7次的MLS迭代后,其細化點云如圖2(b)所示.經有序化并稀疏后,點云頂點數(shù)為137.

4 結束語

針對逆向工程中呈帶狀分布的平面散亂點云曲線重構問題,基于K-d樹方法,快速構建點云的鄰接信息.然后,利用移動最小二乘方法細化點云,重新對點云排序并進行稀疏,在獲得稀疏的有序點列后,利用B樣條插值技術,獲得點云重構的B樣條曲線.算法目前還只適用于平面點集,下一步的工作是把其擴展到三維,并進一步提高其計算效率.而在細化帶狀點云的同時,保持其尖角特征也是未來要解決的問題.

[1] KORSTERSM.Curvature-dependent parameterization of curves and surfaces[J].Computer Aided Design,1991,23 (8):569-578.

[2] SARKAR B,M ENQ C H.Parameter op timization in app roximating curves and surfaces to measurement data[J]. Computer Aided Geometric Design,1991,8(4):267-290.

[3] YANG Xun-nian,WANG Guo-zhao.Planar point set fairing and fitting by arc sp lines[J].Computer Aided Design, 2001,33(1):35-43.

[4] POTTMANN H,RANDRUP T.Rotational and helical surface app roximation fo r reverse engineering[J].Computing,1998,60(4):307-322.

[5] GOSHTASBY A A.Grouping and parameterizing irregularly spaced points for curve fitting[J].ACM Transaction on Graphics,2000,19(3):185-203.

[6] FANG L,GOSSARD D C.M ultidimensional curve fitting to uno rganized data points by nonlinear minimization[J]. Computer Aided Design,1995,27(1):48-58.

[7] TAUB IN G,RONDFARD R.Imp licit simp licialmodels fo r adap tive curve reconstruction[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1996,18(3):321-325.

[8] 鐘綱,楊勛年,汪國昭.平面無序點集曲線重建的跟蹤算法[J].軟件學報,2002,13(11):2188-2193.

[9] LEV IN D.The app roximation power of moving least-squares[J].Mathematicsof Computation,1998,67(224):1517-1531.

[10] LEE I K.Curve reconstruction from unorganized points[J].Computer Aided Geometric Design,2000,17(2):161-177.

[11] 顧步云,周來水,劉勝蘭,等.基于平面散亂點集的曲線重建算法[J].機械科學與技術,2007,26(4):455-458.

[12] DAN IELSJⅡ,HA L K,OCHOTTA T,et al.Robust smooth feature extraction from point clouds[C]∥Proc of the 2007 IEEE International Conferenceon Shape Modeling and App lications.Washington D C:IEEEComputer Society,2007:123-136.

[13] 施法中.計算機輔助幾何設與非均勻有理B樣條[M].北京:高等教育出版社,2001.

Planar Curve Reconstruction from a Set of Unorgan ized Points Based on M oving Least Square

L IU Bin,L IN Jun-yi, HUANG Chang-biao,JIANG Kai-yong
(College of Mechanical Engineering and Automation,Huaqiao University,Quanzhou 362021,China)

In allusion to curve reconstruction p roblem from a set of unorganized points w ith a zonal distribution,moving least square(MLS)is used to conduct second locally weighted regression and to thin point cloud,in the iteration p rocess of w hich the strategy of reducing K-neighborhood vertices gradually is adop ted in order that both computation efficiency and accuracy could be taken into account.The point cloud being thinned is reco rded and resparsed to make uno rganized point set o rderly,the the existing B-sp line curve reconstruction technique is used to reconstruct the point cloud.Finally, the validity of the algo rithm is p roven by the case study.

curve reconstruction;unorganized points;moving least square;thinning point cloud;B-sp line

TP 391

A

(責任編輯:陳志賢 英文審校:鄭亞青)

1000-5013(2010)06-0611-04

2009-09-23

劉斌(1972-),男,副教授,博士,主要從事三維反求建模與數(shù)字化設計、模具CAD/CAE/CAM及其集成技術的研究.E-mail:mold_bin@hqu.edu.cn.

福建省科技計劃重點項目(2009H0032,2008H0085);福建省自然科學基金資助項目(E0810040);國務院僑辦科研基金資助項目(08QZR01)