| 两种空间分块策略K近邻搜索算法的比较研究 |
| |
| 引用本文： | 马娟,朵云峰,赵文亮.两种空间分块策略K近邻搜索算法的比较研究[J].中国图象图形学报,2011,16(9):1676-1680. |
| |
| 作者姓名： | 马娟 朵云峰 赵文亮 |
| |
| 作者单位： | 西南交通大学土木工程学院测量工程系，成都 610031；昆明冶金高等专科学校计算机信息学院，昆明 650033,昆明冶金高等专科学校计算机信息学院，昆明 650033,昆明冶金高等专科学校测绘学院，昆明 650033 |
| |
| 基金项目： | 云南省应用基础研究面上项目（2009CD102）。 |
| |
| 摘 要： | 空间分块策略是K近邻搜索算法研究中的有效方法，然而现有算法进行空间划分时给出的子立方体大小主要取决于K值的大小，K值变化时需重新进行空间划分，影响了时间效率和稳定性。利用空间分块策略的优点，提出一种以建立离散数据空间索引为空间划分目标的K近邻搜索新算法。该算法预先对空间包围盒进行微分块，形成的子立方体结构仅与离散数据和预设参数相关，同一点云数据只需进行一次空间分配。搜索过程中，以计算点为球心建立空间动态球，判定符合条件的子立方体，进行K近邻搜索。测试结果表明，新算法较现有算法点云分配和遍历时间效率、随机点搜索时间稳定性及对不同K值的适应性等方面更具有优势。
|
| 关 键 词： | 空间分块 K近邻 动态球 算法比较 |
| 收稿时间： | 5/30/2010 3:02:44 PM |
| 修稿时间： | 5/30/2011 9:45:29 PM |
Comparison of two algorithms for finding K-nearest neighbors based on spatial sub-cubes |
| |
| Ma Juan,Duo Yunfeng and Zhao Wenliang.Comparison of two algorithms for finding K-nearest neighbors based on spatial sub-cubes[J].Journal of Image and Graphics,2011,16(9):1676-1680. |
| |
| Authors: | Ma Juan Duo Yunfeng and Zhao Wenliang |
| |
| Affiliation: | Ma Juan~(1),2)),Duo Yunfeng~(3)),Zhao Wenliang~(2)) 1)(Department of Surveying Engineering,Southwest Jiaotong University,Chengdu 610031 China) 2)(Department of Surveying,Kunming Metallurgy College,Kunming 650033 China) 3)(Department of Computer,Kunming 650033 China) |
| |
| Abstract: | Space block strategy is the effective method in finding K-nearest neighbors.However,during dividing the min-max box of the dataset,the size of sub-cubes mainly is decided by the K value,and the min-max box is needed to divide again along with the change of K value in existing algorithms,it has affected time efficiency and stability of algorithm.Using the advantages of space block strategy,a new algorithm for finding K-nearest neighbors is presented with establishing the space index of scattered points as th... |
| |
| Keywords: | spatial sub-cubes K-nearest neighbors dynamic sphere comparison of algorithms |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《中国图象图形学报》浏览原始摘要信息 |
|
点击此处可从《中国图象图形学报》下载免费的PDF全文 |
