A local start search algorithm to compute exact Hausdorff Distance for arbitrary point sets

摘要

The Hausdorff Distance (HD) is a very important similarity measurement in Pattern Recognition, Shape Matching and Artificial Intelligence. Because of its inherent computational complexity, computing the HD using the NAIVEHD (brute force) algorithm is difficult, especially for comparing the similarity between large scale point sets in the time of big data. To overcome this problem, we propose a novel, efficient and general algorithm for computing the exact HD for arbitrary point sets, which takes advantage of the spatial locality of point sets, namely, Local Start Search (LSS). Different from the state-of-the-art algorithm EARLYBREAK in PAMI 2015, our idea comes from the observation and fact that the neighbor points of a break position in the current loop have higher probability to break the next loop than other points. Therefore, in our algorithm, we add a new mechanism to record the current break position as a start position, which is initialized as search center of the next loop. Then, LSS executes the next loop by scanning the neighbor points around the center. In this way, LSS maintains high performance in both overlap and non-overlap situations. Furthermore, the LSS algorithm can process arbitrary data by adopting the Morton Curve to establish the order of scattered point sets, while the EARLYBREAK is mainly applied to regular data which require the same grid size, such as medical images or voxel data. In the non-overlapping situation when comparing pairs of arbitrary point sets, LSS achieves performance as good as EARLYBREAK algorithm. While in the overlapping situation when comparing pairs of arbitrary point sets, LSS is faster than EARLYBREAK by three orders of magnitude. Thus, as a whole, LSS outperforms EARLYBREAK. In addition, LSS compared against the increment hausdorff distance calculation algorithm (INC) and significantly outperforms it by an order of magnitude faster. Experiments demonstrate the efficiency and accuracy of the proposed method. (C) 2017 Elsevier Ltd. All rights reserved.