散乱点云数据K_邻域快速搜索算法的研究.kdh.pdf

《散乱点云数据K_邻域快速搜索算法的研究.kdh.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2008年第2期农业装备与车辆工程No.22008(总第199期)AGRICULTURALEQUIPMENT&VEHICLEENGINEERING(2T0o0ta8ll年y1299月)散乱点云数据K-邻域快速搜索算法的研究杨科彪,李旭,张学义,王臣涛(山东理工大学交通与车辆工程学院,山东淄博255049)摘要:K-近邻搜索是海量数据曲面重构中构建合理拓扑关系的关键步骤,其效率直接影响到曲面重构的效率。本文主要研究了一种面向逆向工程的k邻域的快速搜索算法,并通过VisualC++6.0编程实现,最

2、后结合UG二次开发对车身数据点进行了检验。结果表明该算法稳定可靠,效率较高。关键词:点云;曲面重构;k-近邻中图分类号:TP391文献标识码:A文章编号:1673-3142(2008)02-0017-03ResearchonAlgorithmforFindingk-NearestNeighborsofScatteredPointsCloudYANGKe-biao,LIXu,ZHANGXue-yi,WANGChen-tao(SchoolofTransportandVehicleEngineerin

3、g,ShandongUniversityofTechnology,Zibo255049,China)Abstract:Findingk-nearestneighborsisoneofthekeystepsconstructinglogicaltopologyinsurfacereconstructionofscatteredpointclouds,andtheefficiencyofsurfacereconstructionisdirectlyaffectedbyitsefficiency.In

4、thispaper,analgorithmoffindingk-nearestneighborsforreverseengineeringisimplementedbyusingVisualC++6.0,andtestedwiththedatapointsofanautomobilebody,whichiscombinedwithUGfurtherdevelopment.Theresultsshowthatthealgorithmhashighstabilityandefficiency.Key

5、Words:pointscloud;surfacereconstruction;k-nearestneighbors引言许多学者都对快速搜索算法进行了一定的研究,与Goodsell与Dickerson等都是利用点集Voronoi图来k-邻域广泛应用于海量数据点的曲面重建,计进行k个最近点的搜索,但点集的Voroni图计算量算机几何学,图像识别以及地理信息系统等领域。仍然是相当巨大的。PieglL以及周儒荣等都是利用空由于高精度的激光扫描设备的出现,而采用激光扫间分块策略进行k邻域搜索,但Pieg

6、lL只研究了针描法采集的数据点往往十分密集,数据量一般都在对平面点集的k邻域搜索问题,周儒荣等将散乱数数兆字节,甚至达数十兆字节,其所能体现的曲面形据点集看成一个大的数据包围盒,根据一定的准则状信息越来越精细和复杂。因此基于海量数据的曲将其划分为若干个小立方体,这样数据点集中的每面重构技术成为研究的热点,其中三角剖分的建立个点都位于相应的子立方体中,在搜索某一点的k必须要在海量数据点中搜索顶点,其时间及空间复邻域时,需要在测点所在的子立方体及其相邻的上杂度可想而知,所以必须在数据点中建立一定的邻

7、下、左右、前后共27个小立方体中查找k个最近点。近关系以加快搜索速度。本文也是一种基于空间分块策略的k个最近邻设数据点集X={xi,i=1,2,⋯n}是某未知曲面上域的快速搜索算法,但是综合考虑了海量点云数据的空间取样点,对于!x∈X,待求的k个数据点的的大小、点的总数以及最近点个数k,可以给出接近点集Q

8、据点即称为x的邻近点。邻域的搜索速度。最简单的k-邻域方法是求出测点与其余n-1个点的直线距离,并按从小到大的顺序排列,前面的2K-邻域快速搜索算法的实现k个点即为测点的k个邻近点,这种方法很简单,但本文算法首先根据计算出来的子立方体的边是真实数据的n往往很大,用它来计算数据集的k长,把空间分割成许多个大小相等的立方体子空间,个最近邻域必然会很耗时,且很难满足工程要求。并记录子空间内包含的数据点的信息,最后利用子空间内点的信息对每个数据点进行k邻域的搜索。收稿日期:2007-09-06作者简介: