Efficient and Accurate Hausdorff Distance Computation Based on Diffusion Search

Abstract

The Hausdorff distance (HD) between two point sets is widely used in similarity measures, but the high computational cost of HD algorithms restrict their practical use. In this paper, we analyze the time complexity to compute an accurate Hausdorff distance and find that reducing the iterations of the inner loop significantly contributes in reducing the average time cost. Based on the observation that the nearest neighbor (NN) of the breakpoint in the current inner loop suggests a higher probability to break the next inner loop, we present a novel and efficient approach for computing the accurate Hausdorff distance based on a diffusion search. The current breakpoint is recorded as the diffusion center of the next inner loop so that the efficiency of the HD computation can be significantly improved without scanning every point. According to the type of 3-D model (sparse and dense point sets), a novel HD computation framework consisting of two specific diffusion search methods is proposed. First, a Z-order-based HD algorithm (ZHD) for a sparse point sets is proposed. Second, to avoid the low efficiency of a diffusion search when computing the Hausdorff distance between dense point sets with the ZHD algorithm, an octree-based HD algorithm (OHD) is proposed. Evaluation results demonstrate that the ZHD algorithm and the OHD algorithm can greatly reduce the time complexity of HD computations for sparse and dense point sets, respectively. In addition, we conduct several comparative experiments against the most famous HD computation methods. Experimental results show that the proposed approach achieves performance as good as the most efficient available algorithm and exhibits better performance in dealing with spatial data that is highly overlapping.

Keywords

• Hausdorff distance (HD)
• time complexity
• Z-order
• octree
• similarity measure