IEEE Trans Pattern Anal Mach Intell. 2015 Nov;37(11):2153-63. doi: 10.1109/TPAMI.2015.2408351.
The Hausdorff distance (HD) between two point sets is a commonly used dissimilarity measure for comparing point sets and image segmentations. Especially when very large point sets are compared using the HD, for example when evaluating magnetic resonance volume segmentations, or when the underlying applications are based on time critical tasks, like motion detection, then the computational complexity of HD algorithms becomes an important issue. In this paper we propose a novel efficient algorithm for computing the exact Hausdorff distance. In a runtime analysis, the proposed algorithm is demonstrated to have nearly-linear complexity. Furthermore, it has efficient performance for large point set sizes as well as for large grid size; performs equally for sparse and dense point sets; and finally it is general without restrictions on the characteristics of the point set. The proposed algorithm is tested against the HD algorithm of the widely used national library of medicine insight segmentation and registration toolkit (ITK) using magnetic resonance volumes with extremely large size. The proposed algorithm outperforms the ITK HD algorithm both in speed and memory required. In an experiment using trajectories from a road network, the proposed algorithm significantly outperforms an HD algorithm based on R-Trees.
豪斯多夫距离（HD）是一种常用的用于比较点集和图像分割的相似度度量方法。特别是在使用 HD 比较非常大的点集时，例如在评估磁共振体积分割时，或者在底层应用基于时间关键任务（如运动检测）时，HD 算法的计算复杂度就成为一个重要问题。在本文中，我们提出了一种计算精确豪斯多夫距离的新的有效算法。在运行时分析中，所提出的算法被证明具有近线性的复杂度。此外，它对于大的点集大小和大的网格大小都具有高效的性能；对于稀疏和密集的点集都具有相同的性能；最后，它是通用的，对点集的特征没有限制。所提出的算法与广泛使用的医学影像处理与分析工具包（ITK）中的豪斯多夫距离算法进行了比较，使用了具有极大尺寸的磁共振体积。所提出的算法在速度和所需的内存方面都优于 ITK HD 算法。在使用道路网络轨迹的实验中，所提出的算法明显优于基于 R-Trees 的 HD 算法。
