A local start search algorithm to compute exact Hausdorff Distance for arbitrary point sets
作者：
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.
摘要
•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.
论文关键词：Hausdorff Distance,Pattern Recognition,Shape Matching,Similarity measurement,Point sets
论文评审过程：Received 11 June 2016, Revised 3 January 2017, Accepted 5 February 2017, Available online 6 February 2017, Version of Record 14 February 2017.
论文官网地址：https://doi.org/10.1016/j.patcog.2017.02.013
