采用移动最小二乘的平面散乱点集曲线重构

刘斌,林俊义,黄常标,江开勇

(华侨大学机电及自动化学院,福建泉州362021)

采用移动最小二乘的平面散乱点集曲线重构

刘斌,林俊义,黄常标,江开勇

(华侨大学机电及自动化学院,福建泉州362021)

针对带状分布的无序散乱点集的曲线重构问题,采用移动最小二乘法对其进行二次局部加权回归和细化点云;在迭代过程中,采用逐步减小K-邻域顶点数的策略,以兼顾计算效率和精度.对细化后的点云进行重新排序和稀疏,把无序点集有序化;然后,利用现有的B样条曲线重构技术,对点云进行重构.最后,实例验证算法的有效性.

曲线重构;散乱点集;移动最小二乘;细化点云;B样条

曲线拟合在逼近论和几何造型中都是一个重要的研究课题.从有序散乱点重建曲线,已经有了许多成熟的方法[1-3].近年来,无序数据点的曲线重建已逐步受到人们的重视.如Pottmann等[4]将原始的数据点集投影到平面网格上,生成二值图像;Goshtasby[5]先由离散点构造势函数并生成灰度图像,最后利用图像细化算法来得到重建曲线.但是,文[5]的方法所获得的重建曲线并不能很好地反映点云端点的形状,并且重建曲线的准确性、正确性受到网格分辨率的影响.Fang等[6],Taubin等[7]分别利用弹力模型与隐式曲线模型,把已知数据点作为约束条件,直接求解曲线参数并得到重建曲线.文[6-7]的方法常需要优化或迭代求解,对于噪音过多的数据点集则不够理想.钟纲等[8]提出了平面无序点集曲线重建的跟踪算法.本文利用移动最小二乘(Moving Least-Squares,MLS)方法细化点云,重新对点云排序并进行稀疏,在获得稀疏的有序点列后,利用B样条插值技术,获得点云重构的B样条曲线.

1 点云细化

1.1 K-邻近构建

由于点云数据只包含点的坐标信息,没有任何的拓扑结构信息,所以每一点的微分几何信息如曲率、法矢等,都只能由其最临近的一些点来决定.搜索点云中任一点的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),系数a,b的计算式为

式(1)中:K为点P＊的K-邻近顶点个数(包括点P＊本身);wi为邻域内各顶点的权值.权值的选取采用常用的指数表示函数,即

式(2)中:r=‖Pi-P＊‖2;H为邻域半径,选取P＊的K-邻域中距离P＊最远的点到P＊的距离作为H值.为了求a和b的值,按照最小二乘法,由式(1)分别对a,b求偏导数,并令其为零,可得到求解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求偏导数,并令其为零,可得到一组线性方程组.用与求解式(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-邻域中邻近点个数K值的选取问题,有赖于点云本身的分布情况和经验,一般取8～20.K值过大,一方面增加计算成本,另一方面因邻域过大而使点云上的细节特征消失;K值过小,则对噪声点比较敏感,特别是对于带状分布的点云,可能导致计算出的局部拟合直线的方向不是沿着曲线的走势方向,而是沿曲线的横向而导致计算错误.

为了兼顾计算精度与效率,在迭代的初始阶段,点云比较粗的时候,采用较大的K值;而随着迭代次数的增加,点云被细化,K值也逐渐缩小.

2 排序与重构

在通过MLS方法获得足够细化的点云后,将通过对无序点云排序使之有序化,并根据需要对其进行必要的稀疏化处理,减少点云顶点个数.即可利用现有的B样条曲线重构技术,将其拟合为非均匀B样条曲线.

2.1 点集排序与稀疏

设点集S经过MLS细化后所得点集为S′={P′i=(x′i,y′i)|i=1,…,N},从中随机选出一点P′j.根据需要指定一个K值,作为点的K-邻近顶点个数,以决定点云稀疏的程度.如果点云足够细的话,点P′j及其邻域内的点近似在一条直线上,那么,搜寻P′j的K-邻域中距离P′j最远的点作为下一个搜寻点.

点云排序与稀疏的算法流程有如下6个步骤.(1)从点集中随机选出一点P′j作为初始点,计算其K-邻域A及A内各点到P′j的距离,存入数组dj;按照从大到小的顺序对dj排序,把P′j存入排序后的新的点列数组Pnew中.

(2)设A中距离P′j最远的点为P′j+1,向量F=P′j+1-P′j表示点P′j到P′j+1的方向.把P′j+1存入排序后的新的点列数组Pnew中.

(3)计算点P′j+1的K-邻域B及其各点到P′j+1的距离,并按照从大到小的顺序排序.

(4)从已排序的B中循环找出每一点P′l,计算向量Fnew=P′l-P′j+1与向量F的内积e=Fnew· F,判断e值的大小.如果e>0,则将P′l存入排序后的新的点列数组Pnew,以P′l作为新的P′j+1转入步骤(3)进行迭代;如果e≤0,则继续在B中循环.遍历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样条作为重构曲线类型.即采用积累弦长参数化方法对有序化的点列进行参数化,从而确定曲线的节点矢量;然后,根据节点矢量反算3次B样条插值曲线的控制顶点,求解控制顶点时采用抛物线边界条件.在计算出曲线的控制顶点后,用德布尔算法对其进行正算,得出曲线上的点,其具体计算细节参照文[13].

图2 点云细化与曲线重构过程Fig.2 Processof thinning point cloud and curve reconstruction

3 应用实例

算法已通过VC 6.0编程在微机平台上实现.图2是点云重构的一个例子.图2(a)是测量鞋楦曲面时所获得的一条带状点云,其顶点个数为1 141.初始K值取25,经过7次的MLS迭代后,其细化点云如图2(b)所示.经有序化并稀疏后,点云顶点数为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-),男,副教授,博士,主要从事三维反求建模与数字化设计、模具CAD/CAE/CAM及其集成技术的研究.E-mail:mold_bin@hqu.edu.cn.

福建省科技计划重点项目(2009H0032,2008H0085);福建省自然科学基金资助项目(E0810040);国务院侨办科研基金资助项目(08QZR01)