留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种大规模点云k邻域快速搜索算法

杨军,  林岩龙,  张瑞峰,  王小鹏

downloadPDF
文章导航 > 武汉大学学报 ● 信息科学版  > 2016 >  41(5): 656-664
杨军, 林岩龙, 张瑞峰, 王小鹏. 一种大规模点云k邻域快速搜索算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(5): 656-664. doi: 10.13203/j.whugis20140191
引用本文: 杨军, 林岩龙, 张瑞峰, 王小鹏. 一种大规模点云k邻域快速搜索算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(5): 656-664. doi: 10.13203/j.whugis20140191
shu
YANG Jun, LIN Yanlong, ZHANG Ruifeng, WANG Xiaopeng. A Fast Algorithm for Finding k-nearest Neighbors of Large-Scale Scattered Point Cloud[J]. Geomatics and Information Science of Wuhan University, 2016, 41(5): 656-664. doi: 10.13203/j.whugis20140191
Citation: YANG Jun, LIN Yanlong, ZHANG Ruifeng, WANG Xiaopeng. A Fast Algorithm for Finding k-nearest Neighbors of Large-Scale Scattered Point Cloud[J]. Geomatics and Information Science of Wuhan University, 2016, 41(5): 656-664. doi: 10.13203/j.whugis20140191
shu

一种大规模点云k邻域快速搜索算法

doi: 10.13203/j.whugis20140191
基金项目: 国家自然科学基金(61462059);中国博士后科学基金面上项目(2013M542396);人社部留学人员科技活动项目择优资助(2013277);甘肃省财政厅基本科研业务费(214142)。
详细信息
    作者简介:

    杨军,博士,教授,主要从事三维几何模型的对应关系和分割问题研究。yangj@mail.lzjtu.cn

  • 中图分类号: P208;TP391.4

A Fast Algorithm for Finding k-nearest Neighbors of Large-Scale Scattered Point Cloud

Funds: The National Natural Science Foundation of China, No.61462059; China Postdoctoral Science Foundation Funded Project, No.2013M542396; the Technology Foundation for Selected Overseas Chinese Scholar, Ministry of Human Resources and Social Security, No.2013277; the Fundamental Research Funds of Department of Finance of Gansu Province, No.214142.

  • 摘要: 针对大规模点云数据k邻域搜索效率低和分块不均匀的问题,提出了一种新的k邻域快速搜索算法。首先,根据设定的子空间内点云数目上限对点云空间在坐标轴方向自适应分块;然后,以待搜索点到所对应子空间6个面的最小距离作为边长生成初始自身小立方体,根据小立方体内采样点数目的控制阈值动态控制小立方体大小,缩小k邻域的搜索范围;最后,以搜索不成功的点到子空间边界的最小距离所对应的面的外法向量方向作为此面的扩展方向,并以所有搜索不成功点到该面距离的最大值作为该方向的扩展步长对子空间定量扩充。实验结果表明,该算法不仅具有较强的稳定性,而且自动化程度较高,能更快地完成k邻域搜索。
    Abstract: To solve the problem of low efficiency and non-uniform blocking when searching nearest neighbors in large-scale scattered point clouds, a fast algorithm for finding k-nearest neighbors is presented. Firstly, a point cloud is blocked adaptively in the coordinate directions according to the point number threshold of a sub-block. Secondly, the initial small cube is created using the minimum distance from the point to the sub-block boundary, and the size of the small cube is changed dynamically based on a threshold; that is, the amount of points in a small cube to narrow down the search extent of k-neighbors. Thirdly, the expansion direction is determined by the outer normal vector of the corresponding side, which is the side nearest to a unsuccessful searching point. The maximal distance from the unsuccessful searching point to the side is taken as a step to expand the sub-block quantitatively. Experimental results show that the proposed method is not only stable, but also is more automatic with better performance.
  • [1] Zhou Rurong, Zhang Liyan, Su Xu, et al. Algorithmic Research on Surface Reconstruction from Dense Scattered Points[J]. Journal of Software, 2001, 12(2):249-255(周儒荣, 张丽艳, 苏旭, 等. 海量散乱点的曲面重建算法研究[J]. 软件学报, 2001, 12(2):249-255)
    [2] Cheng Xiaojun, He Guizhen. The Method and Application of Hole Boundary Extraction for Multi-valued Surface Repair[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(6):831-837(程效军, 何桂珍. 适用于多值曲面修复的空洞边界提取方法及应用[J]. 测绘学报, 2012, 41(6):831-837)
    [3] Xiong Bangshu, He Mingyi, Yu Huajing. Algorithm for Finding k-nearest Neighbors of Scattered Points in Three Dimensions[J]. Journal of Computer-Aided Design and Computer Graphics, 2004, 16(7):909-912(熊邦书, 何明一, 余华璟. 三维散乱数据的k个最近邻域快速搜索算法[J]. 计算机辅助设计与图形图像学报, 2004, 16(7):909-912)
    [4] Piegl L A, Tiller W. Algorithm for Finding All k Nearest Neighbors[J]. Computer-Aided Design, 2002, 34(2):167-172
    [5] Zhao Jianhui, Long Chengjiang, Ding Yihua, et al. A New k-nearest Neighbors Search Algorithm Based on 3D Cell Grids[J]. Geomatics and Information Science of Wuhan University, 2009, 34(5):615-618(赵俭辉, 龙成江, 丁乙华, 等. 一种基于立方体小栅格的k邻域快速搜索算法[J]. 武汉大学学报\5信息科学版, 2009, 34(5):615-618)
    [6] Ma Juan, Fang Yuanming, Zhao Wenliang, et al. Algorithm for Finding k-nearest Neighbors Based on Spatial Sub-cubes and Dynamic Sphere[J]. Geomatics and Information Science of Wuhan University, 2011, 36(3):358-362(马娟, 方源敏, 赵文亮, 等. 利用空间微分块与动态球策略的k邻域搜索算法研究[J]. 武汉大学学报\5信息科学版, 2011, 36(3):358-362)
    [7] Liu Yuehua, Liao Wenhe, Liu Hao. Research of k-nearest Neighbors Search Algorithm in Reverse Engineering[J]. Machinery Design and Manufacture, 2012, 1(3):256-258(刘越华, 廖文和, 刘浩. 逆向工程中散乱点云的k邻域搜索算法研究[J]. 机械设计与制造, 2012, 1(3):256-258)
    [8] Sarkar M, Leong T Y. Application of k-nearest Neighbors Algorithm on Breast Cancer Diagnosis Problem[C]. The 2000 AMIA Annual Symposium, Los Angeles, CA, 2000
    [9] Connor M, Kumar P. Fast Construction of k-nearest Neighbor Graphs for Point Clouds[J]. IEEE Transactions on Visualization & Computer Graphics, 2010, 16(4):599-608
    [10] Sankaranarayanan J, Samet H, Varshney A. A Fast All Nearest Neighbor Algorithm for Applications Involving Large Point-Clouds[J]. Computers & Graph, 2007, 31(2):157-174
    [11] Procpiuc O, Agarwal P K, Arge L, et al. Bkd-tree:A Dynamic Scalable Kd-tree[C]. International Symposium on Spatial and Temporal Databases, Berlin, Germany, 2003
    [12] Xiao Hui, Yang Bisheng. An Improved KNN Search Algorithm Based on Road Network Distance[J]. Geomatics and Information Science of Wuhan University, 2008, 33(4):437-439(肖晖, 杨必胜. 一种改进的基于道路网络距离的K近邻查询算法[J]. 武汉大学学报\5信息科学版, 2008, 33(4):437-439)
    [13] Dickerson M T, Drysdale R, Sack J R. Simple Algorithms for Enumerating Interpoint Distance and Finding k Nearest Neighbors[J]. International Journal of Computational Geometry and Applications, 1992, 2(3):221-239
    [14] Goodsell G. On Finding p-th Nearest Neighbors of Scattered Points in Two Dimensions for Small p[J]. Computer Aided Geometric Design, 2000, 17(4):387-392
    [15] Ma Liming, Xu Yi, Li Zexiang. Fast k-nearest Neighbors Searching Algorithm for Scattered Points Based on Dynamic Grid Decomposition[J]. Computer Engineering, 2008, 34(8):10-11(马骊溟, 徐毅, 李泽湘. 基于动态网格划分的散乱点k邻域快速搜索算法[J]. 计算机工程, 2008, 34(8):10-11)
    [16] Yang Jun, Lin Yanlong, Wang Yangping, et al. Fast Algorithm for Finding The k-nearest Neighbors of A Large-Scale Scattered Point Cloud[J]. Journal of Image and Graphics, 2013, 18(4):399-406(杨军, 林岩龙, 王阳萍, 等. 大规模散乱点的k邻域快速搜索算法[J]. 中国图象图形学报, 2013, 18(4):399-406)
  • [1] 杨钰琪, 陈驰, 杨必胜, 胡平波, 崔扬.  基于UAV影像密集匹配点云多层次分割的建筑物层高变化检测 . 武汉大学学报 ● 信息科学版, 2021, 46(4): 489-496. doi: 10.13203/j.whugis20190030
    [2] 米晓新, 杨必胜, 董震.  车载激光点云道路场景可视域快速计算与应用 . 武汉大学学报 ● 信息科学版, 2020, 45(2): 258-264. doi: 10.13203/j.whugis20180380
    [3] 张瑞菊, 周欣, 赵江洪, 曹闵.  一种古建筑点云数据的语义分割算法 . 武汉大学学报 ● 信息科学版, 2020, 45(5): 753-759. doi: 10.13203/j.whugis20180428
    [4] 孙文潇, 王健, 梁周雁, 马伟丽, 陈喆.  法线特征约束的激光点云精确配准 . 武汉大学学报 ● 信息科学版, 2020, 45(7): 988-995. doi: 10.13203/j.whugis20180315
    [5] 蒋腾平, 杨必胜, 周雨舟, 朱润松, 胡宗田, 董震.  道路点云场景双层卷积语义分割 . 武汉大学学报 ● 信息科学版, 2020, 45(12): 1942-1948. doi: 10.13203/j.whugis20200081
    [6] 付永健, 李宗春, 何华.  点云内在属性因子驱动的自适应滚球算法 . 武汉大学学报 ● 信息科学版, 2020, 45(3): 353-361. doi: 10.13203/j.whugis20180390
    [7] 冯林, 李斌兵.  一种基于最小广义方差估计的TLS点云抗差法向量求解方法 . 武汉大学学报 ● 信息科学版, 2018, 43(11): 1647-1653. doi: 10.13203/j.whugis20170065
    [8] 张蕊, 李广云, 王力, 李明磊, 周阳林.  车载LiDAR点云混合索引新方法 . 武汉大学学报 ● 信息科学版, 2018, 43(7): 993-999. doi: 10.13203/j.whugis20160441
    [9] 危双丰, 刘明蕾, 赵江洪, 黄帅.  利用点云检测室内导航元素的方法综述 . 武汉大学学报 ● 信息科学版, 2018, 43(12): 2003-2011. doi: 10.13203/j.whugis20180144
    [10] 李国俊, 李宗春, 孙元超, 李伟, 黄志勇.  利用Delaunay细分进行噪声点云曲面重建 . 武汉大学学报 ● 信息科学版, 2017, 42(1): 123-129. doi: 10.13203/j.whugis20140513
    [11] 肖巍峰, 邓敏, 李朝奎.  三维点云多尺度等值线模型Morphing变换方法研究 . 武汉大学学报 ● 信息科学版, 2015, 40(7): 957-963. doi: 10.13203/j.whugis20140107
    [12] 卢昊, 庞勇, 徐光彩, 李增元.  机载激光雷达全波形数据与系统点云差异的定量分析 . 武汉大学学报 ● 信息科学版, 2015, 40(5): 588-593. doi: 10.13203/j.whugis20130443
    [13] 康志忠, 王薇薇, 李珍.  多源数据融合的三维点云特征面分割和拟合一体化方法 . 武汉大学学报 ● 信息科学版, 2013, 38(11): 1317-1321.
    [14] 王永波, 杨化超, 刘燕华, 牛晓楠.  线状特征约束下基于四元数描述的LiDAR点云配准方法 . 武汉大学学报 ● 信息科学版, 2013, 38(9): 1057-1062.
    [15] 孙杰, 马洪超, 钟良.  利用LiDAR点云的真正射影像遮蔽检测 . 武汉大学学报 ● 信息科学版, 2011, 36(8): 948-951.
    [16] 张剑清, 李彩林, 郭宝云.  基于切平面投影的散乱数据点快速曲面重建算法 . 武汉大学学报 ● 信息科学版, 2011, 36(7): 757-762.
    [17] 郑莉, 张剑清, 罗跃军.  多视结构光点云的自动无缝拼接 . 武汉大学学报 ● 信息科学版, 2009, 34(2): 199-202.
    [18] 万幼川, 徐景中, 赖旭东, 张圣望.  基于多分辨率方向预测的LIDAR点云滤波方法 . 武汉大学学报 ● 信息科学版, 2007, 32(11): 1011-1015.
    [19] 黄先锋, 陶闯, 江万寿, 龚健雅.  机载激光雷达点云数据的实时渲染 . 武汉大学学报 ● 信息科学版, 2005, 30(11): 975-978.
    [20] 项学泳, 李广云, 王力, 宗文鹏, 吕志鹏, 向奉卓.  使用局部几何特征与空洞邻域的点云语义分割 . 武汉大学学报 ● 信息科学版, 0, 0(0): 0-0. doi: 10.13203/j.whugis20200567
  • 加载中
WeChat 点击查看大图
计量
  • 文章访问数:  1006
  • HTML全文浏览量:  42
  • PDF下载量:  423
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-01-31
  • 刊出日期:  2016-05-05

一种大规模点云k邻域快速搜索算法

doi: 10.13203/j.whugis20140191
    基金项目:  国家自然科学基金(61462059);中国博士后科学基金面上项目(2013M542396);人社部留学人员科技活动项目择优资助(2013277);甘肃省财政厅基本科研业务费(214142)。
    作者简介:

    杨军,博士,教授,主要从事三维几何模型的对应关系和分割问题研究。yangj@mail.lzjtu.cn

  • 收稿日期: 2015-01-31
  • 刊出日期: 2016-05-05

  • 中图分类号: P208;TP391.4

摘要: 针对大规模点云数据k邻域搜索效率低和分块不均匀的问题,提出了一种新的k邻域快速搜索算法。首先,根据设定的子空间内点云数目上限对点云空间在坐标轴方向自适应分块;然后,以待搜索点到所对应子空间6个面的最小距离作为边长生成初始自身小立方体,根据小立方体内采样点数目的控制阈值动态控制小立方体大小,缩小k邻域的搜索范围;最后,以搜索不成功的点到子空间边界的最小距离所对应的面的外法向量方向作为此面的扩展方向,并以所有搜索不成功点到该面距离的最大值作为该方向的扩展步长对子空间定量扩充。实验结果表明,该算法不仅具有较强的稳定性,而且自动化程度较高,能更快地完成k邻域搜索。

English Abstract

杨军, 林岩龙, 张瑞峰, 王小鹏. 一种大规模点云k邻域快速搜索算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(5): 656-664. doi: 10.13203/j.whugis20140191
引用本文: 杨军, 林岩龙, 张瑞峰, 王小鹏. 一种大规模点云k邻域快速搜索算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(5): 656-664. doi: 10.13203/j.whugis20140191
shu
YANG Jun, LIN Yanlong, ZHANG Ruifeng, WANG Xiaopeng. A Fast Algorithm for Finding k-nearest Neighbors of Large-Scale Scattered Point Cloud[J]. Geomatics and Information Science of Wuhan University, 2016, 41(5): 656-664. doi: 10.13203/j.whugis20140191
Citation: YANG Jun, LIN Yanlong, ZHANG Ruifeng, WANG Xiaopeng. A Fast Algorithm for Finding k-nearest Neighbors of Large-Scale Scattered Point Cloud[J]. Geomatics and Information Science of Wuhan University, 2016, 41(5): 656-664. doi: 10.13203/j.whugis20140191
shu

    全文HTML

参考文献 (16)

目录

    /

    返回文章
    返回

    我要投稿

    投稿攻略

    联系我们

    二维码

    版权所有 © 2013 《武汉大学学报·信息科学版》编辑部

    地址：武汉大学文理学部本科生院楼北5楼邮政编码：430072

    电话：027-68778465,68778045E-mail:whuxxb@vip.163.com

    本系统由 北京仁和汇智信息技术有限公司 开发    百度统计