开曲面点云边界提取

1、12月刘章明等:一种非封闭H由曲面的点云边界提取算法249文章编：100l -9081 2009)S2 -0247 -03一种非封闭自由曲面的点云边界提取算法刘章明I，董救颖'，王金涛2S沈阳理工大学信息科学与工程学院沈阳100168 ：2沈阳新松机器人自动化般份有限公可沈阳110168)(liuzhangmingl88& 163. com)摘要:点公边界不仅作为衣达曲向的蛍要的儿何特征、而4作为求解曲面的泄义域，対电建曲向模吃的品质和 耕度起着页耍的作用以激光线性均匀扌1描的点云数据为例论述了 种改进的空间非封闭1*1山曲而点云的边界提収 方法，在脈算法基础匕增设阈值，变同定

2、K值为变屋K值。实验证明该算法不仅町以较快地提収边界，而II表达曲面 边界特征比校耕确关键词:点云；边界提収；哈希两数；曲而雨建中图分类号：TP391.41文献标志码:ABoundary extraction algorithm of point clouds onnon-closed freeform surfaceI JU Zhang-ining1, DENG Ihii-ing', WANG Jin-tao2(1 College Inifornalion Siience and EHgineering, Shen)un；Unitvrsily, Shen)un Im i uni ng

3、 110168. China;2 SheHyung SIASUN Robot and AuU)mution Company UmUek Shenyang lauonin 110168, China)Abstract: Ilie lM)un(lan of |x)int clouds is mA only the iin|M)rtant gromrtn feature of surface, but also the drGnition domain to x)lve the surface. It plays an iin|x>rtant rule in the reconstructio

4、n of surface In this pa|x-r, taking the |M)ii)t clouds obtained from laser scanning as an example, an improved algorithm was |)n>|x)sr(l to extract ihr IxHindan of |M)inl clouds Details of improvemrnt include adding a threshold and transforming constant K into variable K . Experiment results show

5、 that the algorithm has higher computing efficiency, and expressed the boundary fralurv of surface more precisely.Key words: point cloud; boundary extraction; hash function: surface reconstruction12月刘章明等:一种非封闭H由曲面的点云边界提取算法24912月刘章明等:一种非封闭H由曲面的点云边界提取算法249收稿日期：2009-0420$修订日期：2009 -07 -03作者简介：刘饭明 佃74-)

6、小湖南氏沙人，硕士瞬究生,£耍研究方向：卯别、数字图像处理：笙急颖<1962 - )女辽宁沈阳人教 授博士主要研究方向:模式识别:王金涛Q980 -男山东人高级工程师博士.主要研究方向：模式识别机器视觉.0引言随着当前数了化测呈技术的快速发贋，反求工程在图像 处理、计算机视觉、儿何造世和数字化制造等领域得到了广泛 应用,而曲何重建圧反求工程的关键技术Z O点公边界不 仅作为表达曲面的東要的几何特征，而且作为求解曲而的定 义域，对重建曲面模也的品质和精度起着重嬰的作用越.文 献D-3分别通过建立点云的三角网格和球面参数网格模 型提収点公边界特征，该算法边界特征提取准晚，但耗费人虽

7、 的系统资源虫彳連度慢,浙江人7的乍江雄提出把散乱点云 网格化，得到边界网几和IE边网孔，但是此算法只适介测虽点 比较密集的数据对于疏散的散乱测駅数据不适用.本文改 进的算法采用三维链衣数纽的数据结构与哈希两数相结合匱 观形彖的组织散乱数据点云的拓扑关系拟介毎点的K- Nrarrsl Points的徹切平曲,以K-Nrarrsl Points在微切平闻上 投影点的几何分布提取边界特征，该算法可适用丁空间非封 闭自山曲向数据点云，运行速度校快,边界特征提取准确。1边界点的提取方法1.1建立点云数据的拓扑关系由于在边界提取过程中会涉及到每点的复杂邻域搜索 为减少授索的时间消耗，在进行边界提取前，首

8、先对点云建立 包国盒，从而利用包帼盒的空间层次分割技术将英划分为多 个小的单元，使得在其邻域捜索过程中不必每次都遍历整个 实体空间包帀盒建立的JI体步骤如下所示.1) 考虑到点云中点的数呈的未知性，此处将数据读入一 个vector < PoinBD > in_poinBd容器中，同时获得点集的x,y, z朋标的绘小值与最大值分别X*, , Yllun, , Z.MI.乙”“， 然后将包川盒向外扩人相当丁重点谋羞的距离TOL,以避免 在计算包閑盒边缘数据点时产生的谋差。PointsD的数据结构为：SlnictPoin(3D(doiiblr x；double y:double z;:X

9、=X,m. - TOLXi = X 叫 + TOL心=»_ TOL=A + TOL= Z“. - TOL= ZII1-M + TOL从而形成-个9坐标轴平行的K方体包用盒包屈所冇 的点集。2) 设定小立方体边氏为CelUize眦值可以调整)，当询 点的三维坐标值为:匕，化七，并沿着坐标轴的方向将长方 体包围盒划分为m x n x/个小立方体总元，小芷方体单元在 三个方向的个数为：m = (nt) W" - X" )/ce_$ize：n = int)-乙一)/ce_$ize：I = <nl) “心-乙心3) 建立毎个数据点与小立方体单元的对应关系在毎点的邻域搜

10、索过程中，针対每个点采取遍历査找的方式，则算法 时间复杂度为o 2).效率太低，如采用平衡二叉树的査找方 法,时间复杂度为o山“)，但是平衡：叉树山F节点的插入 或删除操作可能会影响到树的平術性，必须对n进行平衡化 規转，从而便其保持量佳性的时间代价太大理想的怙况是能 血接找到需要的点记录，因此必须在记录点的存储位说和它 的关键7) Z|hJ建立一个确圧的对应关系昭希函数”h“ 0,使毎个关键字和结构中一个唯一的存储位代相对 应，即采用哈希直找算法，其址人的优点，就是把数据的心储 和査找涓耗的时间大大降低时间复杂度为。“)，篦法简单 但当某-个点的关键丫在通个对应关系 昭希函数”加0映 射存储

11、地址时可能存在冲突好的哈希函数能使地址均匀分 布在:整个哈希表中,从而减少冲突，fl I不能避免冲突。一般处理哈希冲突冇开放地址法、再呛希法、链地址法和 建立一个共公溢出区。向虽容器的使用可以随机访问其中的 元索并可在不知元聚个数的借况下动态的添加元索，同时为 自观的衣达数据点的存储结构与乞小立方体的对应，冈此本 文采用链地址法处理冲突的哈希民绍构式的向於容器:-维数 组存放各个小立方体栅格中包倉的数据点及数据点在脈 m»int3d容褊中的序号，这样在同一个小立方体内的多个点 既可以通过呛希函数映射出点的存储地址，乂町以通过向屋 容器存储解决哈希冲突立方体栅格在X,Y,Z 个方向的編

12、 号可以哈希函数直接定址。当前点巴仔巴)所在小立方体橱格的哈希函数设为: VoidHahFun Foint3D P9 Hashvalue v alue)value, i = <nl) (P. ，丫阳.value, j = fnl) (Pt - YM )/celljiize：value, k = Oil) (P: - ZIBMI )/<v/_.u；)数据结构为：StriHlIlashvaliiefini i; int j; int k:ISlrlK tkryval (int index:表示数据点在vector < Point3D > mj>oint3d容器中的序号

13、Poinl3I) poini;Typrclrf vector < keyViil>siibli>tMiblist harray|klji|;存放毎个小立方体中的点4) K-Nearest Points的计算，一个小立方体单尤中叮以存 放晏个数据点，但毎个数据点只心储在唯的芷方体也元中. 在査询点云中任意数据点P的Kearrst Points时.育先根据 点卩的坐标值及哈希函数ii rr.tp所在立方体单元的编巧一然后把编号i ± IJ ± 1和A ±1币:新组合就町以得到与该 眼元相邻的26个单元的编号，瑕后在27个单元宀为边界小 元时小于27个

14、单尤)中査找到与点P欧氏距离绘近的K个 点叭1.2 Kdmrrsl Poin怕在微切平血上的投影点集设K-Nearrsl Points逼近平而方程为：Ax + Cz + D = 0(1 )平面的单位法矢为:AT a,fi,C),K-Nearest Points内任意点P.乞z, )与切平面的距离公代4D = I 4. + By, + Czt + I) IK-Nearest Points 点集 P, (i = 1.2.3”)以它们与待 求的绘小i.乘平面的即离的平方和最小建立冃标函数：F fA.B.CJ) = V iAXt + HYt + CZ, + D)22)要便F故小.对尸求偏导使其等于零,

15、得：d =-必 + cza)INII其中：II£x、二£若八人=土若匕，乙=代入式2)得：zjy6)对式B)求偏导得：kF以 K - X.)+ S - 打)+ C 0 -叫0叫 叫叫 ml2=04)Ay aml2 一 加21 一其约束条件也屮绘终求最小.乘间题就转化为求矩阵4)最小特征值和 它对应的特征向虽问题。因为此矩阵为实对称距阵即町用雅 比法求出量小特征值和对应的特征向量即平面单位法矢 (UBQ求出切平面后再求K-Nearest Points在该平面上 的投恳坐标设点坐标为cv0,y0,z0>,投影坐标为(v,r,z) 山丁枚影点位丁过点 仏，人必)且方向欠虽为

16、n s,c) 的血线上所以得到式6),山式a)和6)联立用全选高斯 消元法求解可以得到投影点坐标(VAZ)。13边界特征点提取对于同一平面上的点云数据，可以宜观的认为(如图1人 数据点P的Kearrsl Points的分布如果偏向侧，则可以认 为点P为边界特征点:反之,如果数据点川绕P均匀分布，则 可以认为“是内部点7】山于在实际应用中点云采样点并 非具育均匀性数据点P在27个单元中包育点的个数不I亦 特别足边界点的邻域点远比内部点的邻域点小用至小二乘 法拟合半血绘佳人'值是16 26,为了使边界点的邻域点人达 到最任仏则包丽盒加要相对人,这时内部点的邻域点 值就会相当大，一般达50

17、70,如果采用固定的K值17叭这 时必雄在其小捜索距离点Id近的K个点这在点公的处理 过程中将耗费大虽:时间，难以达到实时处理要求.在均匀性 比较好的点云数据处理中本文算法则依据邻域包国盒单元 中边界点H有的Kearrsl Points远比内部点典有的K- Nearcs! Point>少这-特点，增设邻域点阈值，此阈值与包田盒 cell_size的大小、点云中点的分布疏密有关，包【1：|盒越大，点的 分布越密,K值就越大，具体的设置应该根抑:实际悄况进行调 整，一般设代为30-45的某个值，当人 > 阈值则判为内部点， K W阈值初步判为边界点再辺行处理。这样町以快速剔除人 磧明显

18、的内部点减少数据运気吊，提高处理效率其余点则 按如下方法判断边界点：収P点的K-Nearest Points中绘近的 点Q作冇向线段PQ,.以PQ.为阜准计算英余点PQt 1j PQ,的 夹角“如图1)得到一个角度序列S =匕，“2"3,5宀，“”) 放入一容veclor<douHe> angle中.然后对容器用sort 0按 照升丿时*序，址后求角度垦学列及左序列的标准空改进的边 界提収流程如图2所示.图I点云边界夹角提取并法定义角度差序列乙：f ul4l - ut 91 W i V £ if 差序列标准屋E = J旗中门 +孚.设置个标准羞闽值G此阈值与包囤

19、盒cell_size的大 小、点阈值K的大小有关，当包国盒"ize及K值设定越大 时标准差阖值G就越小，山丁实际物体边界的复杂程度不 同,这个值应该根据实际惜况进行调拾当点"求得的角度罡 E > G时可以判析为边界点，把所冇的边界点放入-个容器 vector<Point3D> boundapoint 中便于 VC + + 6.0,结合 OpenGL 库显示边界点图形。2边界提取算法的时间复杂度木文算法浮先计算点的Klearesl Points,然后通过设定 点阖值初步判断该点是否为町能的边界点，如果为町能的边 界点，则将该点的K-Neaiest Point

20、s用ft小二乘法拟存平面求 投影坐标，进-步计算夹角标准差，提収边界点，冈此算法的 标准时间复杂度为O仙"),皿为点的Krarvst Points个数，“ 为点云中初步判断为可能的边界点的数目。3实验验证本文算法在PC机配置为:Priiiimn R) 4 CPU 3.06 GHz, 内存512 MB.Visual C + + 6.0调用()|>rngl图形M的坏境卜编 程完成，对25 355点数据进彳亍边界提取处理，其中X址大 733.503277, X堆小值-63.587144, 丫最大值 1511.245597. V 蚁小值-58. 789 304, Z 兹大值 1 306

21、. 687 909, Z 址小 786.407219,其曲面外形如图3 <a).实验中cdl_size设为 15.5,冗见为0.1,邻域点阈值21,标准差角E为2&0,全过程 时间为0.6 s.提収边界点670个，如图3 b),原算法&®标准 差角E为39.0,全过程时间为40 s,提取边界点688个，如图3 的：变换观察视角看脈图3 6)曲面外形如图3 (1), celLsize 设为21. 0,7丫九设为0. I,邻域点阈值39,标准差角应设为 29.38.全过程时间为1 $,提取边界点397个如图3 原算 法°：标准差角E为29.38,全过程时间为32 s,提取边界点 4加个.如图3 Q.从实验的数据及捉収的结果可以舀出.木 文提出的改进算法比脈算法不但处理速度快而H.桔度耍崗, 能很好地滴足实时性變求。/点上数危/图2木文改进的边界捉取览仏流程(a)原始曲面点云1 (b)改进算諾提取的边界1 (c)原算法提取的边界I(d)原始曲面点云2 (c)改进覓法雄取的边界2 (0原算法捉取的边界2图3实验结果4结语从上述实例可以看出本文提出的改进的空间自曲曲面点 止数拡边界的捉取方法，尽管方法待别适川J：均匀分布的点 云数据,但也同样适