采用移動(dòng)最小二乘的平面散亂點(diǎn)集曲線重構(gòu)

劉斌,林俊義,黃常標(biāo),江開勇

(華僑大學(xué)機(jī)電及自動(dòng)化學(xué)院,福建泉州362021)

采用移動(dòng)最小二乘的平面散亂點(diǎn)集曲線重構(gòu)

劉斌,林俊義,黃常標(biāo),江開勇

(華僑大學(xué)機(jī)電及自動(dòng)化學(xué)院,福建泉州362021)

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

曲線重構(gòu);散亂點(diǎn)集;移動(dòng)最小二乘;細(xì)化點(diǎn)云;B樣條

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

1 點(diǎn)云細(xì)化

1.1 K-鄰近構(gòu)建

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

1.2 局部最小二乘回歸

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

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

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

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

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

1.2.2 基于MLS的投影點(diǎn)計(jì)算 進(jìn)行平移和旋轉(zhuǎn)變換,構(gòu)建以P＊為原點(diǎn),以平行于直線L的方向?yàn)閤軸的局部坐標(biāo)系.其平移和旋轉(zhuǎn)矩陣分別為

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

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

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

對(duì)點(diǎn)集S中的每一點(diǎn)進(jìn)行同樣的變換,得到一系列新的MLS點(diǎn),把S中的每一點(diǎn)移動(dòng)到對(duì)應(yīng)的MLS點(diǎn),就可使帶狀分布的無序點(diǎn)集得到細(xì)化,如圖1所示.

圖1 基于MLS的點(diǎn)云細(xì)化Fig.1 Thinning a point cloud using moving lease square

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

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

2 排序與重構(gòu)

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

2.1 點(diǎn)集排序與稀疏

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

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

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

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

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

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

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

2.2 點(diǎn)集的B樣條曲線重構(gòu)

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

圖2 點(diǎn)云細(xì)化與曲線重構(gòu)過程Fig.2 Processof thinning point cloud and curve reconstruction

3 應(yīng)用實(shí)例

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

4 結(jié)束語

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

[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] 鐘綱,楊勛年,汪國(guó)昭.平面無序點(diǎn)集曲線重建的跟蹤算法[J].軟件學(xué)報(bào),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] 顧步云,周來水,劉勝蘭,等.基于平面散亂點(diǎn)集的曲線重建算法[J].機(jī)械科學(xué)與技術(shù),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] 施法中.計(jì)算機(jī)輔助幾何設(shè)與非均勻有理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

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

1000-5013(2010)06-0611-04

2009-09-23

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

福建省科技計(jì)劃重點(diǎn)項(xiàng)目(2009H0032,2008H0085);福建省自然科學(xué)基金資助項(xiàng)目(E0810040);國(guó)務(wù)院僑辦科研基金資助項(xiàng)目(08QZR01)