|
|
- 2016
一种大规模点云k邻域快速搜索算法
|
Abstract:
针对大规模点云数据k邻域搜索效率低和分块不均匀的问题,提出了一种新的k邻域快速搜索算法。首先,根据设定的子空间内点云数目上限对点云空间在坐标轴方向自适应分块;然后,以待搜索点到所对应子空间6个面的最小距离作为边长生成初始自身小立方体,根据小立方体内采样点数目的控制阈值动态控制小立方体大小,缩小k邻域的搜索范围;最后,以搜索不成功的点到子空间边界的最小距离所对应的面的外法向量方向作为此面的扩展方向,并以所有搜索不成功点到该面距离的最大值作为该方向的扩展步长对子空间定量扩充。实验结果表明,该算法不仅具有较强的稳定性,而且自动化程度较高,能更快地完成k邻域搜索
| [1] | Zhou Rurong, Zhang Liyan, Su Xu, et al. Algorithmic Research on Surface Reconstruction from Dense Scattered Points[J]. <em>Journal of Software</em>, 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]. <em>Acta Geodaetica et Cartographica Sinica</em>, 2012, 41(6):831-837(程效军, 何桂珍. 适用于多值曲面修复的空洞边界提取方法及应用[J]. 测绘学报, 2012, 41(6):831-837) |
| [3] | Xiao Hui, Yang Bisheng. An Improved KNN Search Algorithm Based on Road Network Distance[J]. <em>Geomatics and Information Science of Wuhan University</em>, 2008, 33(4):437-439(肖晖, 杨必胜. 一种改进的基于道路网络距离的<em>K</em>近邻查询算法[J]. 武汉大学学报\5信息科学版, 2008, 33(4):437-439) |
| [4] | Dickerson M T, Drysdale R, Sack J R. Simple Algorithms for Enumerating Interpoint Distance and Finding <em>k</em> Nearest Neighbors[J]. <em>International Journal of Computational Geometry and Applications</em>, 1992, 2(3):221-239 |
| [5] | Goodsell G. On Finding <em>p</em>-th Nearest Neighbors of Scattered Points in Two Dimensions for Small <em>p</em>[J]. <em>Computer Aided Geometric Design</em>, 2000, 17(4):387-392 |
| [6] | Ma Liming, Xu Yi, Li Zexiang. Fast <em>k</em>-nearest Neighbors Searching Algorithm for Scattered Points Based on Dynamic Grid Decomposition[J]. <em>Computer Engineering</em>, 2008, 34(8):10-11(马骊溟, 徐毅, 李泽湘. 基于动态网格划分的散乱点<em>k</em>邻域快速搜索算法[J]. 计算机工程, 2008, 34(8):10-11) |
| [7] | Sankaranarayanan J, Samet H, Varshney A. A Fast All Nearest Neighbor Algorithm for Applications Involving Large Point-Clouds[J]. <em>Computers & Graph</em>, 2007, 31(2):157-174 |
| [8] | Xiong Bangshu, He Mingyi, Yu Huajing. Algorithm for Finding <em>k</em>-nearest Neighbors of Scattered Points in Three Dimensions[J]. <em>Journal of Computer-Aided Design and Computer Graphics</em>, 2004, 16(7):909-912(熊邦书, 何明一, 余华璟. 三维散乱数据的<em>k</em>个最近邻域快速搜索算法[J]. 计算机辅助设计与图形图像学报, 2004, 16(7):909-912) |
| [9] | Ma Juan, Fang Yuanming, Zhao Wenliang, et al. Algorithm for Finding <em>k</em>-nearest Neighbors Based on Spatial Sub-cubes and Dynamic Sphere[J]. <em>Geomatics and Information Science of Wuhan University</em>, 2011, 36(3):358-362(马娟, 方源敏, 赵文亮, 等. 利用空间微分块与动态球策略的<em>k</em>邻域搜索算法研究[J]. 武汉大学学报\5信息科学版, 2011, 36(3):358-362) |
| [10] | Liu Yuehua, Liao Wenhe, Liu Hao. Research of <em>k</em>-nearest Neighbors Search Algorithm in Reverse Engineering[J]. <em>Machinery Design and Manufacture</em>, 2012, 1(3):256-258(刘越华, 廖文和, 刘浩. 逆向工程中散乱点云的<em>k</em>邻域搜索算法研究[J]. 机械设计与制造, 2012, 1(3):256-258) |
| [11] | Sarkar M, Leong T Y. Application of <em>k</em>-nearest Neighbors Algorithm on Breast Cancer Diagnosis Problem[C]. The 2000 AMIA Annual Symposium, Los Angeles, CA, 2000 |
| [12] | Piegl L A, Tiller W. Algorithm for Finding All <em>k</em> Nearest Neighbors[J]. <em>Computer-Aided Design</em>, 2002, 34(2):167-172 |
| [13] | Connor M, Kumar P. Fast Construction of <em>k</em>-nearest Neighbor Graphs for Point Clouds[J]. <em>IEEE Transactions on Visualization & Computer Graphics</em>, 2010, 16(4):599-608 |
| [14] | Yang Jun, Lin Yanlong, Wang Yangping, et al. Fast Algorithm for Finding The <em>k</em>-nearest Neighbors of A Large-Scale Scattered Point Cloud[J]. <em>Journal of Image and Graphics</em>, 2013, 18(4):399-406(杨军, 林岩龙, 王阳萍, 等. 大规模散乱点的<em>k</em>邻域快速搜索算法[J]. 中国图象图形学报, 2013, 18(4):399-406) |
| [15] | Zhao Jianhui, Long Chengjiang, Ding Yihua, et al. A New <em>k</em>-nearest Neighbors Search Algorithm Based on 3D Cell Grids[J]. <em>Geomatics and Information Science of Wuhan University</em>, 2009, 34(5):615-618(赵俭辉, 龙成江, 丁乙华, 等. 一种基于立方体小栅格的<em>k</em>邻域快速搜索算法[J]. 武汉大学学报\5信息科学版, 2009, 34(5):615-618) |
| [16] | 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 |
