一种基于立方体小栅格的K邻域快速搜索算法

赵俭辉; 龙成江; 丁乙华; 袁志勇

美国《工程索引》（EI）核心期刊
美国《剑桥科学文摘》（CSA）收录期刊
荷兰斯高帕斯数据库（Scopus）收录期刊
英国INSPEC数据库（SA）收录期刊

留言板

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

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

一种基于立方体小栅格的K邻域快速搜索算法

赵俭辉, 龙成江, 丁乙华, 袁志勇

文章导航 > 武汉大学学报 ● 信息科学版 > 2009 > 34(5): 615-618

赵俭辉, 龙成江, 丁乙华, 袁志勇. 一种基于立方体小栅格的K邻域快速搜索算法[J]. 武汉大学学报 ● 信息科学版, 2009, 34(5): 615-618.

引用本文:

赵俭辉, 龙成江, 丁乙华, 袁志勇. 一种基于立方体小栅格的K邻域快速搜索算法[J]. 武汉大学学报 ● 信息科学版, 2009, 34(5): 615-618.

ZHAO Jianhui, LONG Chengjiang, DING Yihua, YUAN Zhiyong. 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.

Citation:

ZHAO Jianhui, LONG Chengjiang, DING Yihua, YUAN Zhiyong. 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邻域快速搜索算法

¹武汉大学计算机学院,武汉市珞喻路129号430079

基金项目: 国家自然科学基金资助项目(60603079)

A New K-Nearest Neighbors Search Algorithm Based on 3D Cell Grids

¹School of Computer,Wuhan University,129 Luoyu Road,Wuhan 430079,China

Funds: 国家自然科学基金资助项目(60603079)

摘要: 提出了一种新的基于立方体小栅格的K邻域搜索算法。首先,采用二次划分的方法将点云划分到相应的立方体小栅格中;然后,为采样点所在的立方体小栅格确定最终子空间、内子空间和外子空间,结合采样点的球空间,就能很快确定该采样点的K邻域的搜索范围。与已有方法相比,该算法具有更高的搜索效率。
- K邻域 /
- 三维点云 /
- 立方体小栅格 /
- 搜索算法
Abstract: Based on 3D cell grids,we proposed a new K-nearest neighbors search algorithm.The point cloud was divided twice and distributed to 3D cell grids,then ultimate space,internal space,external space were decided for each grid.With the help of each point's sphere space,K-nearest neighbors of the point can be found quickly.Compared with the existed methods,the proposed algorithm has more efficient performance.
- K-nearest neighbors /
- point cloud /
- 3D cell grids /
- search algorithm

[1]	王玮琦, 游雄, 杨剑, 李钦. 一种改进匹配点对选取策略的ElasticFusion室内三维重建算法 . 武汉大学学报 ● 信息科学版, 2020, 45(9): 1469-1477. doi: 10.13203/j.whugis20180278
[2]	李健, 曹垚, 王宗敏, 王广印. 融合k-means聚类和Hausdorff距离的散乱点云精简算法 . 武汉大学学报 ● 信息科学版, 2020, 45(2): 250-257. doi: 10.13203/j.whugis20180204
[3]	杨军, 林岩龙, 张瑞峰, 王小鹏. 一种大规模点云k邻域快速搜索算法 . 武汉大学学报 ● 信息科学版, 2016, 41(5): 656-664. doi: 10.13203/j.whugis20140191
[4]	龚健雅, 崔婷婷, 单杰, 季顺平, 黄玉春. 利用车载移动测量数据的建筑物立面建模方法 . 武汉大学学报 ● 信息科学版, 2015, 40(9): 1137-1143. doi: 10.13203/j .whu g is20150173
[5]	张正鹏, 江万寿, 张靖. 车载立方体全景影像匹配点的粗差检测方法 . 武汉大学学报 ● 信息科学版, 2014, 39(10): 1208-1213.
[6]	康志忠, 王薇薇, 李珍. 多源数据融合的三维点云特征面分割和拟合一体化方法 . 武汉大学学报 ● 信息科学版, 2013, 38(11): 1317-1321.
[7]	杨惠珍, 赵文光, 张萍, 张瑞芳. 云闪空间定位的三维网格搜索算法研究 . 武汉大学学报 ● 信息科学版, 2013, 38(3): 370-373.
[8]	. 云闪空间定位的三维网格搜索算法研究 . 武汉大学学报 ● 信息科学版, 2013, 38(3): 370-.
[9]	孙殿柱, 刘健, 李延瑞, 孙永伟. 三维散乱点云的Voronoi拓扑近邻点集查询算法 . 武汉大学学报 ● 信息科学版, 2011, 36(1): 86-91.
[10]	马娟, 方源敏, 赵文亮, 冯瑜瑾. 利用空间微分块与动态球策略的k近邻搜索算法研究 . 武汉大学学报 ● 信息科学版, 2011, 36(3): 358-362.
[11]	孙殿柱, 刘健, 李延瑞, 李心成. 三维散乱点集Voronoi图快速生成算法研究 . 武汉大学学报 ● 信息科学版, 2010, 35(8): 909-912.
[12]	赵学胜, 崔马军, 李昂, 张美娟. 球面退化四叉树格网单元的邻近搜索算法 . 武汉大学学报 ● 信息科学版, 2009, 34(4): 479-482.
[13]	高松, 陆锋, 段滢滢. 一种基于双向搜索的K则最优路径算法 . 武汉大学学报 ● 信息科学版, 2008, 33(4): 418-421.
[14]	孙文彬, 赵学胜. 基于Quaternary编码的球面三角格网邻近搜索算法 . 武汉大学学报 ● 信息科学版, 2007, 32(4): 350-352.
[15]	朱庆, 李逢春, 张叶廷. 一种改进的三维点集表面重建的区域生长算法 . 武汉大学学报 ● 信息科学版, 2006, 31(8): 667-670.
[16]	郑春燕, 郭庆胜, 刘小利. 基于禁忌搜索算法的点状要素注记的自动配置 . 武汉大学学报 ● 信息科学版, 2006, 31(5): 428-431.
[17]	郑顺义, 苏国中, 张祖勋. 三维点集的自动表面重构算法 . 武汉大学学报 ● 信息科学版, 2005, 30(2): 154-157.
[18]	邹逸江, 李德仁, 王任享. 空间数据立方体分析操作原理 . 武汉大学学报 ● 信息科学版, 2004, 29(9): 822-826.
[19]	边馥苓, 傅仲良, 胡自锋. 面向目标的栅格矢量一体化三维数据模型 . 武汉大学学报 ● 信息科学版, 2000, 25(4): 294-298.
[20]	张卉冉, 董震, 杨必胜, 黄荣刚, 徐大展. 点云压缩研究进展与趋势 . 武汉大学学报 ● 信息科学版, 0, 0(0): 0-0. doi: 10.13203/j.whugis20210103