Volume 41 Issue 5
May  2016
Turn off MathJax
Article Contents
Abstract
References
Related Articles
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

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.
More Information
  • Received Date: January 30, 2015
  • Published Date: May 04, 2016
    Graphical Abstract
    • 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.
    • FullText(HTML)
    • References (16)
  • [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)
    • Related Articles

  • Related Articles

    [1]ZHANG Kaishi, JIAO Wenhai, LI Jianwen. Analysis of GNSS Positioning Precision on Android Smart Devices[J]. Geomatics and Information Science of Wuhan University, 2019, 44(10): 1472-1477. DOI: 10.13203/j.whugis20180085
    [2]ZHANG Xiaohong, LIU Gen, GUO Fei, LI Xin. Model Comparison and Performance Analysis of Triple-frequency BDS Precise Point Positioning[J]. Geomatics and Information Science of Wuhan University, 2018, 43(12): 2124-2130. DOI: 10.13203/j.whugis20180078
    [3]KONG Yao, SUN Baoqi, YANG Xuhai, CAO Fen, HE Zhanke, YANG Haiyan. Precision Analysis of BeiDou Broadcast Ephemeris by Using SLR Data[J]. Geomatics and Information Science of Wuhan University, 2017, 42(6): 831-837. DOI: 10.13203/j.whugis20140856
    [4]ZHANG Xiaohong, DING Lele. Quality Analysis of the Second Generation Compass Observables and Stochastic Model Refining[J]. Geomatics and Information Science of Wuhan University, 2013, 38(7): 832-836.
    [5]ZHANG Xiaohong, GUO Fei, LI Pan, ZUO Xiang. Real-time Quality Control Procedure for GNSS Precise Point Positioning[J]. Geomatics and Information Science of Wuhan University, 2012, 37(8): 940-944.
    [6]CAI Changsheng, ZHU Jianjun, DAI Wujiao, KUANG Cuilin. Modeling and Result Analysis of Combined GPS/GLONASS Precise Point Positioning[J]. Geomatics and Information Science of Wuhan University, 2011, 36(12): 1474-1477.
    [7]HE Ning, WANG Lei. Recursion Multi-service Cross-layer Flow Control Algorithm of Broadband GEO Satellite Networks[J]. Geomatics and Information Science of Wuhan University, 2010, 35(5): 532-536.
    [8]CAI Hua, ZHAO Qile, LOU Yidong. Implementation and Precision Analysis of GPS Precise Clock Estimation System[J]. Geomatics and Information Science of Wuhan University, 2009, 34(11): 1293-1296.
    [9]DAI Wujiao, DING Xiaoli, ZHU Jianjun. Comparing GPS Stochastic Models Based on Observation Quality Indices[J]. Geomatics and Information Science of Wuhan University, 2008, 33(7): 718-722.
    [10]ZHANG Yongjun, ZHANG Yong. Analysis of Precision of Relative Orientation and Forward Intersection with High-overlap Images[J]. Geomatics and Information Science of Wuhan University, 2005, 30(2): 126-130.

  • Cited by

    Periodical cited type(28)

    1. 李岚，朱锋，刘万科，张小红. 城市分类场景的GNSS伪距随机模型构建及其定位性能分析. 武汉大学学报(信息科学版). 2025(03): 545-553 .
    2. 苑晓峥，徐爱功，高猛，祝会忠. 基于低成本终端抗差速度约束差分定位算法. 大地测量与地球动力学. 2024(01): 27-34 .
    3. 曲利红，李俊芹. 通用智能技术路线下的人机传播应用. 电视技术. 2024(03): 176-179 .
    4. 刘一，刘敏，边少锋，翟国君，周威. 北斗低成本接收机单频PPP海上定位性能分析. 海洋测绘. 2024(03): 68-72+82 .
    5. 张宝，吴泓正，邸越超，张传定. Android智能手机GNSS定位研究进展. 测绘科学. 2024(05): 1-14 .
    6. 侯雪，张献志，叶远斌. 基于GDCORS的北斗终端高精度定位算法实现及性能分析. 地理空间信息. 2024(08): 72-75 .
    7. 孙俊锋，穆宏波，于先文，廖鹏，吴焱泽. 顾及系统误差影响的智能手机GNSS观测值质量分析. 测绘工程. 2024(05): 43-49 .
    8. 孙俊锋，吴焱泽，于先文，廖鹏，叶嘉宁，曹嘉瑞. 基于北斗的智能手机内河航道高精度定位软件研发. 现代测绘. 2024(03): 13-17 .
    9. 尹昊华，雷博，连宏亮，徐邦岁，曾翔强. 基于安卓智能手机的高精度定位系统研发及测试. 国土资源导刊. 2024(03): 9-17 .
    10. 祝会忠，孙沐凡，李军. GNSS低成本智能终端抗差自适应差分定位算法. 导航定位学报. 2024(06): 10-19 .
    11. 王瑞光，王中元，胡超，王阳阳，刘冰雨. 智能手机BDS-3/GPS数据质量及SPP性能分析. 大地测量与地球动力学. 2023(02): 168-172 .
    12. 孟庆庆，郭德普，胡洁，薄伟伟. 移动GIS在黄委直管河道确权划界中的应用. 水利信息化. 2023(02): 44-49 .
    13. 徐彦田，刘巍峰，李玉星，姜鼎璇. BDS/GPS/GAL智能手机RTK动态定位算法. 无线电工程. 2023(05): 1061-1067 .
    14. 王甫红，栾梦杰，程雨欣，祝浩祈，赵广越，张万威. 城市环境下智能手机车载GNSS/MEMS IMU紧组合定位算法. 武汉大学学报(信息科学版). 2023(07): 1106-1116 .
    15. 郑东，汪梦月，杨中皇. SM3国密算法在Android内核的汇编语言快速实现. 西安邮电大学学报. 2023(03): 57-62 .
    16. 逯遥，聂志喜，王振杰，徐晓飞，张远帆，王翔. 单/双频混合数据的Android手机精密单点定位方法. 测绘科学. 2023(08): 64-71+129 .
    17. 傅鑫榕，王甫红，郭磊，栾梦杰，祝浩祈. 不同电离层模型对智能手机实时PPP精度的影响分析. 测绘地理信息. 2023(06): 26-31 .
    18. 葛在宸，王明华. 基于智能手机GNSS伪距定位的运动距离和速度确定. 江西科学. 2023(06): 1124-1130 .
    19. 邱树素，顾桢，章怿钦，叶俊华. 基于手机内置传感器的相对高程模型. 北京测绘. 2023(12): 1676-1682 .
    20. 董少敏，辛宪会，刘杰，陈文哲，卢为选. 便携式GNSS接收机集成方案及其定位精度分析. 海洋测绘. 2022(03): 56-60 .
    21. 甘露，王志斌，张少波，韩明敏，陈攀，黄威翰. Android智能手机间相对定位性能分析. 测绘工程. 2022(05): 54-60 .
    22. 李阿红. 基于混合神经网络的Android软件缺陷精准预测研究. 自动化与仪器仪表. 2022(08): 33-36+41 .
    23. 张小红，陶贤露，王颖喆，刘万科，朱锋. 城市场景智能手机GNSS/MEMS融合车载高精度定位. 武汉大学学报(信息科学版). 2022(10): 1740-1749 .
    24. 王怡欣，刘晖，钱闯，范潇云. 一种基于智能手机的实时高精度定位系统开发与车载应用测试. 测绘通报. 2022(10): 56-61 .
    25. 曾树林，匡翠林. 智能手机RTK定位软件实现及应用试验. 全球定位系统. 2022(05): 72-80 .
    26. 祝会忠，李骏鹏，李军. 智能手机GNSS多系统多频实时动态定位方法. 测绘科学. 2022(09): 8-19 .
    27. 舒宝，义琛，王利，许豪，田云青. 华为P30手机GPS/BDS/GLONASS/Galileo观测值随机模型优化及定位性能分析. 大地测量与地球动力学. 2022(12): 1222-1226 .
    28. 吴文坛，秘金钟，谷守周. 智能手机广域差分实时定位分析. 测绘科学. 2022(10): 39-44 .

    Other cited types(27)

Catalog

    Get Citation
    PDF
    XML
    Article views PDF downloads Cited by(55)
    Related

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

    Address：武汉大学文理学部本科生院楼北5楼Post Code：430072

    Tel：027-68778465,68788631E-mail:whuxxb@vip.163.com

    Submit Article

    Submission Guidelines

    e

    Contact Us

    Qrcode

    Supported by: Beijing Renhe Information Technology Co., Ltd.  Baidu Analytics

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return