A local start search algorithm to compute exact Hausdorff Distance for arbitrary point sets. (July 2017)

• Record Type: Journal Article
• Authors: Chen, Yilin; He, Fazhi; Wu, Yiqi; Hou, Neng
• Is Part Of: Pattern recognition. Volume 67(2017:Jul.)
• Page Start: 139
• Page End: 148
• Publication Date: 2017-07
• Subjects: Hausdorff Distance -- Pattern Recognition -- Shape Matching -- Similarity measurement -- Point sets; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2017.02.013
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: This paper discovers the spatial locality feature of point sets and proposes a novel search algorithm called local start search (LSS) to compute the exact Hausdorff Distance. The LSS algorithm can greatly reduce the running time when dealing with large scale of point set, in which the spatial continuity and distance continuity are very common. LSS maintains high performance in both overlap and non-overlap situations of a pair of regular point sets, while EARLYBREAK experiences degraded performance in overlap situations. Furthermore, for general point sets in overlap situations, the preprocess of excluding the intersection in EARLYBREAK will fail. However, LSS can still process the general point sets with different point sizes after ordering the sets. Our algorithm outperforms the state-of-the-art algorithm. Experiments demonstrate the efficiency and accuracy of the proposed method. Abstract: 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.