基于Z曲线和八叉树的高效Hausdorff距离计算方法  

Efficient Hausdorff Distance Calculation Algorithm Based on Z-Order and Octree

作　　者：张德军 何发智[2] 田龙 谢朱洋 邹露 Zhang Dejun;He Fazhi;Tian Long;Xie Zhuyang;Zou Lu(College of Information and Engineering,Sichuan Agricultural University,Yaan 625014;School of Computer Science,Wuhan University,Wuhan 430072)

机构地区：[1]四川农业大学信息工程学院,雅安625014 [2]武汉大学计算机学院,武汉430072

出　　处：《计算机辅助设计与图形学学报》2018年第10期1794-1800,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(61702350;61472289);湖北省自然科学基金(2015CFB254)

摘　　要：为提高计算点云模型之间Hausdorff距离(HD距离)的效率,提出基于Z曲线和八叉树的Hausdorff距离计算方法.首先利用Z曲线和八叉树实现点云模型预处理;然后在八叉树结构中定义了2类邻居(邻居点和邻居节点),并提出基于八叉树的局部搜索,以某一个叶子节点作为搜索的起点,递归地搜索其邻居直到根节点;最后结合模型预处理和局部搜索,给出了算法的实现细节.针对三维高斯随机数据和点云模型进行大量实验,并与经典方法进行对比,结果验证了文中方法的高效性.In order to improve the efficiency of calculating the Hausdorff distance(HD distance)between point clouds,this paper presents an efficient Hausdorff distance calculation algorithm based on Z-Order and octree.First,the point sets are preprocessed in a structured format by Z-Order and octree partition.Then,two kinds of neighbor information are defined as neighborhood and neighbor-node.With a leaf node recorded as the start position,the algorithm searches its neighbors recursively until the root node.Combined with the idea of data preprocessing and local search,the implementation details of the algorithm are given.A set of experiments have been conducted against classical algorithms on 3D stochastic Gaussian data and the point clouds.The results demonstrate the presented algorithm is high-efficiency.

关 键 词：HAUSDORFF距离 Z曲线 八叉树 相似度度量 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]