基于RANSAC算法的三角网格特征曲面提取_图文

1、2009年1月第37卷第1期机床与液压MACH I N E T OOL &HY DRAUL I CSJan 12009Vol 137No 11收稿日期:2007-12-10基金项目:总装备部预先研究项目资助(41318111117;航空科学基金资助项目(2008Z B55001作者简介:刘元朋(1976,男,博士,讲师,主要研究方向为反求工程、CAD /CA M 和工业I CT 成像。电话:135*,E -mail:drag on_ly psina 1co m 1cn 。基于RANS AC 算法的三角网格特征曲面提取刘元朋,陈良骥,赵辉(郑州航空工业管理学院机电工程系,河南郑州4500

2、15摘要:针对三角网格模型中的二次曲面提取问题,利用随机抽样一致性算法(Random Samp ling Consensus,RANS AC 提出了一种球面、圆柱面和圆锥面等二次特征曲面的提取算法。该算法首先计算每个顶点的法向量,然后用带顶点法向量的三角面片统一表示每类二次曲面的最小子集,最后利用RANS AC 算法进行二次曲面提取。实验结果分析表明该算法具有良好的稳定性和运算效率等特点。关键词:随机抽样一致性算法;三角网格;二次曲面提取中图分类号:TP391172文献标识码:A 文章编号:1001-3881(20091-014-3Extracti n g Fea ture Surface f

3、ro m Tr i a ngul ar M eshes Ba sed on RANSAC A lgor ith mL I U Yuanpeng,CHEN L iangji,ZHAO Hui(Depart m ent of Mechanical and Electrical Engineering,ZhengzhouI nstitute of Aer onautical I ndustry Manage ment,Zhengzhou Henan 450015,China Abstract:An aut omatic algorith m was p resented t o detect qua

4、dric fr om triangular mesh .The method is based on random sa m 2p ling consensus algorith m and iteratively detects p lanes,s pheres,cylinders and cones .I n order t o reduce the nu mber of requiredpoints t o define a unique instance of each quadric,the algorith m computes an app r oxi m ate surface

5、 nor mal f or each point firstly,then the m ini m al subset is defined as a triangle with l ocal orientati on t o i m p r ove the r obust of the algorith m.Experi m ental results de mon 2strate that the algorith m is capable t o extract a variety of different types of quadric,while retaining such fa

6、vorable p r operties as high r obustness,effectiveness and generality .Keywords:Random sa mp ling consensus algorith m;Triangular mesh;Quadric surface extracti on0前言随着激光测距扫描等三维数据采样技术的进步和硬件设备性能的提高,三角网格曲面正在逐渐成为计算机图形学和几何设计领域的新宠。三角网格模型作为一种对原始模型的线性逼近,被广泛应用于快速原型制造、医用图像、地理地形绘制、计算机游戏等许多应用领域。但是,这种模型只有一阶连续,精度

7、不高,使用三角网格模型表示机械零件会损失零件模型的几何信息和拓扑信息,使得设计者难以对零件模型进行精确快速的分析。A l ons o 全面分析了产品反求建模的方法,并指出产品形面直接用低次参数曲面片(圆锥面、圆柱面、球面、比用传统三角网格模型建模精确更高、计算更有效1。Nourse 指出85%的机械零件都可以用平面、圆锥面、球面和圆柱面来描述2。因此可靠地提取三角网格模型中的二次曲面是体现零件原始设计意图反求建模的关键环节。常见的二次曲面提取方法主要有三类:Hough 变换法3、随机抽样一致性(Random Samp le Consen 2sus,RANS AC 算法4和优化算法5。由于Hou

8、gh 变换法的空间需求是其参数空间的维数的指数函数,这意味着该方法在空间上很浪费,很难用到有两个以上参数的几何形状提取,事实上,Hough 变换法主要用于直线等平面二次曲线的提取。Rabbani 等6利用圆柱面的高斯图特性,将圆柱面的参数转化为平面二次曲线参数的组合,进而利用两个Hough 变换进行圆柱面参数提取。RANS A 方法的主要优点是数学上形式化和较低的空间要求,后者同点的数量呈线性关系,而不是与参数数目成指数关系,这是对Hough 变换方法的显著改善,使得多个自由参数的几何元素提取变得容易一些。Thomas 等提出了利用RANS A 法进行圆柱面提取7。W ahl 等利用RANS

9、A 法从点云数据中提取平面8。RANS AC 的困难之处在于它的计算效率较低,RANS AC 算法的速度主要取决于两个因素:要选择的样本数,而样本数和数据的错误率、置信概率有关。所以,要提高RANS AC 算法速度的主要办法是尽量减少样本数。优化算法是将二次曲面提取问题等同于寻找具有多个局部极小值的代价函数的最优解,然后利用遗传算法9、禁忌搜索10等方法进行优化求解。优化算法的复杂度高,其运算效率比RANS A 法更低。本文作者利用RANS AC 算法提出一种从三角网格模型中提取二次曲面的新方法。1算法基础111相关定义在算法描述前,先给出几个与算法相关的定义。三角网格模型M:M是由三维空间中

10、的三角面片通过边和顶点连接而成的分片线性曲面,用顶点集合V=v1,v2,v m和三角面片集合T=T1,T2,Tn组成的二元组M=(V,T来表示。T(v=T1,T2,Tk表示所有与顶点v相连三角面片的集合。最小子集I:能唯一确定一个几何元素所需要的最小点数的集合,表示为I=v1,v2,v R,R为最小子集中点的数量。对于直线而言,两点即可唯一确定一条直线,所以I=v1,v2。残差:残差i 为顶点vi距待评估几何元素的距离。最小子集I的代价函数g(I:3个顶点残差都在一预定范围内的三角面片的个数。112RANS AC算法RANS AC算法的基本思想4:从随机抽取的N组样本中找出最优的抽样,并根据最

11、优抽样来选择参与最后计算的原始数据。具体作法是:迭代地在输入数据中采样所谓的最小点集。并利用每次采样所得到的最小点集估计出所要确定的参数,同时根据一定的判断准则来判别输入数据中哪些是与该参数相一致的,即内点,哪些是不一致的,即外点。如此迭代一定次数后,将对应输入数据中内点比例最高的所估计参数值以及所筛选出来的内点作为RANS AC最后解。将此解作为其它方法的初始值进一步优化计算,从而得到最后的估计参数值。抽样次数N的计算公式如下:N=ln(1-sln(1-(1-R其中,为预期的原始数据错误率,s代表至少有一个最小子集包含所有内点的概率。采用随机抽样方法时,使用尽可能少的数据来确定一组解是非常重

12、要的。因为使用较少的数据可以减少错误数据被抽中的概率,同时,所需要的抽样次数即计算量随所使用的数据量的增加成指数比例增长。因而达到相同的估计精度,使用数据量越少算法就越快。2算法描述传统确定一个二次曲面至少需要9个点10。为了较少抽样次数N,引入点的法向量信息将最小子集的参数R统一为3。为了提高抽取的最小子集样品质量,利用三角面片抽样来取代散乱点的抽样,利用这种方法同时也提高了随机抽取的效率。211顶点法向量计算本文中,对法向量估计采用文献11中的公式进行计算,其形式如下:nv=jT(vjAjn jTjT(vjAj其中,j、Aj和n jT分别表示T(v中第j个三角面片在顶点v处的顶角、面积和单

13、位法向量。212二次曲面识别本算法中的最小子集I为3个带顶点法向量信息的顶点v1,v2,v3,其坐标及法向量分别为p1,p2, p3和n1,n2,n3。通过坐标和法向量信息可以估计每个最小子集所对应的二次曲面类型。其中任一顶点vi与I所确定的二次曲面之间的残差为i,其法向量ni与顶点pi在I所确定的二次曲面上的向量夹角为i。平面:平面的法向量n可以通过3个点的坐标来确定12,其坐标原点到平面的垂直距离参数取为d= -n Tp,其中p为3个坐标点的平均值。最后通过3个i是否小于预定参数来判定(p,d是否可以作为一平面样品数据。球面:任取两个点(p1,n1和(p2,n2。取两条直线p1+t n1=

14、0和p2+t n2=0间最短线的中点作为球心c,取球半径为r=p1-c+p2-c2。最后通过3个i是否小于参数和3个i是否小于预定参数来判定(c,r是否可以作为一球面样品数据。圆柱面:任取两个点(p1,n1和(p2,n2。利用n1和n2确定轴线法向量=n1×n2,然后将两条参数化曲线p1+t n1=0和p2+t n2=0分别投影到平面ax=0上,取两条投影直线的交点作为轴线一点q0。取p1在平面ax=0上投影点与q的距离作为半径r。最后通过3个i是否小于参数和3个i是否小于预定参数来判定(,q,r是否可以作为一圆柱面样品数据。圆锥面:任取3个点(p1,n1、(p2,n2和(p3,n3

15、。利用3个点及其法向量确定3个平面,取3个平面交点作为顶点坐标c。轴线法向量n通过3个点来确定c+pi-cpi-c3i=1,顶角取为=3i=1arccos(pi-cT/3。最后通过3个i是否小于参数和3个i是否小于预定参数来判定(c,n,是否可以作为一圆锥面样品数据。在进行二次曲面识别时,通过圆锥面、圆柱面、球面和平面的顺序依次进行判断,从而决定最小子集所属的二次曲面类型。213内点计算在三角网格模型中,相同类型的三角面片在物理上是连通的,可以形成一个块。因此本文作者采用文献13中所述的边界扩展生长法来计算g(I。其51第1期刘元朋等:基于RANS AC算法的三角网格特征曲面提取主要思想为:以

16、最小子集抽取的三角面片为生长点,以三角面片顶点与二次曲面间的残差为判断标准,进行区域扩张;待区域扩张完毕,然后计算区域内三角形的个数,取其为g (I 。214算法流程整个算法的具体步骤如下:步骤1:设置参数的初始值N ,和T m in 。步骤2:计算V 中每个顶点的法向量。步骤3:随机从三角面片集合T 抽取N 组样本,确定每组样本的曲面类型,并计算每个样本I 所对应的代价函数g (I 。步骤4:获得最优样本I 对应的内点区域S,对S中顶点利用最小二乘法14进行拟合获得相应特征曲面参数,且从T 中删除S 中的三角面片。步骤5:如果T 中三角面片的数量大于预定阈值T m in ,转步骤3。步骤6:

17、结束。3验证实例本文作者提出的算法通过V isual C +和VTK 实现。为了验证算法的有效性,在Pentium 4210G,内存256MB 的计算机上,分别对机械零件(40k 个三角面片,见图1(a ,Fandisk (13k 个三角面片,见图2(a 模型进行了二次曲面特征提取。对于机械零件模型,其初始参数:N =25,=0101mm,=20°,T m in =100,本算法运行时间为317s,结果见图1(b ,每一种曲面类型用一种颜色表。Fandisk 模型的参数:N =25,=0101mm,=10°,T m in =50,本算法运行时间为0147s,结果见图2(b

18、所示 。4结论从三角网格模型中提取二次曲面是曲面重建中的重要问题,是解决其它问题的先决条件,例如模式识别。本文作者使用基于RANS AC 算法提取二次曲面,通过实例证明该技术是提取二次曲面的有效方法。该算法具有如下优势:算法原理简单;抗噪声能力强;可以提取多个二次曲面;算法运行效率高。参考文献【1】L A l ons o,F Cuny,S Petitjean,et al .The virtualmesh:a geometric abstracti on for efficiently computing radi osity J .AC M Trans .Graphics,2001,20(3:

19、169-20.【2】B Nourse,D Hakala,R H illyard,et al .Natural quad 2rics in mechanical design J .I n Pr oc .of Aut ofact W est,Anahei m ,1980(1:363-378.【3】V F Leavers .Survey W hich Hough Transf or m J .C V 2GI P:I m age Understanding,1993,58(2:250-264.【4】M A Fischler,R C Bolles .Random sa mp le consensus:

20、aparadig m f or model fitting with app licati ons t o i m age analy 2sis and aut omated cart ography J .AC M Commun,1981,24(6:381-395.【5】R Gerhard,D L M artin .Geometric Pri m itive Extracti onusing a Genetic A lgorith m J .I EEE Transacti ons on Pattern Analysis and Machine I ntelligence,1994,16(9:

21、901-905.【6】T Rabbani .Aut omatic reconstructi on of industrial installa 2ti ons D .Delft University of Technol ogy,2006.【7】C Thomas,G Francois .Extracting Cylinders in Full 3DData using a Random Sa mp ling Method and the Gaussian I m age C .I n:V isi on,Modelling and V isualizati ong,Stuttgart,2001:

22、21-23.【8】R W ahl,M Guthe,R Klein .I dentifying p lanes in point 2cl ouds for efficient hybrid rendering C .I n:The 13thPacific Conference on Computer Graphics and App lica 2ti ons,Macao,2005:12-14.【9】Chen Y H,L iu C Y .Quadric Surface Extracti on usingGenetic A lgorith m s J .Computer A ided Design,

23、1999,(31:101-110.【10】曲学军,席平.使用Tabu 搜索技术提取二次曲面J .中国机械工程,2004,15(15:1350-1354.【11】神会存,周来水.基于离散曲率计算的三角网格模型优化调整J .航空学报,2006,27(2:318-324.【12】D Faugeras .Three di m ensi onal computer visi on:a geo 2metric viewpoint M .M I T Press,1993.【13】刘胜兰,周儒荣,安鲁陵.三角网格模型的数据分块算法J .南京航空航天大学学报,2003,35(6:653-658.(下转第8页根据

24、本文作者所提出的启发式算法对各项制造任务进行分析,得出满足资源约束的各项任务的开始时间,如表2所示。表2工作开始时间T 挑选出的工作T =04、2、7T =43T =84T =106T =111根据各任务开始时间情况,对该中外翼A 墙的制造、装配过程进行搭接网络计划制定,得出搭接关系、搭接时距、相关时间参数。从而绘制出如图5所示的单代号网络计划。 图5A 墙制造的单代号网络计划4结束语本文作者针对国内外在搭接网络计划中搭接关系和搭接时距处理上的不足,提出了基于优先规则的启发式网络计划制定方法,在最早开始时间的计算中动态处理搭接关系,解决了资源约束下的制造项目网络计划制定问题,很好地满足了实际需

25、求,为今后制造项目的计划编制提供了有效的参考。参考文献【1】杨冰.搭接网络计划模型分析J .北方交通大学学报,2002,26(5:84-88.【2】M 1G 1S peranz,C 1Vercellis .H ierarchicalmodels for multi 2p r oject p lanning and scheduling J .Eur opean Journal of Operati onal Research,1993,64:312-325.【3】J 1Moder,C 1Philli p s,Davis,et al .Pr ojectM anage mentwith CP M

26、,PERT and Precedence D iagra mm ing,3rded M .B litz,1995.【4】刘永淞,黄明娜.矩阵法计算搭接施工网络计划J .基建优化,2001,22(4:28-29.【5】杨冰.网络计划计算模型的统一J .系统工程理论与实践,2002(3:51-55.【6】宇德明.计算搭接施工计划时间参数新模型J .铁道科学与工程学报,2005,2(4:77-81.【7】卢向南.项目计划与控制M .北京:机械工业出版社,2004.(上接第22页律,提出了利用在磨削区内磨削冷却液的体积分数的分布规律判断磨削区冷却液冷却效果好坏的一种理论方法。由于冷却液射流参数之间的综

27、合作用决定流场的特性,所以有关内容还需进一步的实验研究。总之,砂轮转速、冷却液的射流速度、射流角度及射流位置对冷却液的冷却效果都有一定影响。冷却效果的好坏是由这些因素综合作用决定。应用气液两相流理论研究磨削冷却液的体积分数的分布规律,在此基础上提出了利用在磨削区内磨削冷却液体积分数的分布规律来判断磨削液的冷却效果好坏的一种理论方法,该方法不仅为准干式磨削研究中在保证冷却效果条件下寻找使用最少量的磨削液,提供理论依据,而且可用于高速磨削智能化研究,对高速磨削过程磨削液冷却效果的预测及高速磨削过程自适应控制都具有一定的应用价值。参考文献【1】蔡光起,赵恒华,高兴军.高速高效磨削加工及其关键技术J .制造技术与机床,2004(11:42-45.【2】葛培琪,程建辉,栾芝云.磨削液磨削加工特性的研究J .润滑与密封,200