An Efficient Algorithm for Calculating the Exact Hausdorff Distance

Authors: 
Abdel Aziz Taha
Allan Hanbury
Type: 
Journal article
Proceedings: 
Publisher: 
IEEE Transactions on Pattern Analysis and Machine Intelligence, 37-11
Pages: 
2153 - 2163
ISBN: 
Year: 
2015
Abstract: 
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.
TU Focus: 
Computational Science and Engineering
Reference: 

A. Taha, A. Hanbury:
"An Efficient Algorithm for Calculating the Exact Hausdorff Distance";
IEEE Transactions on Pattern Analysis and Machine Intelligence, 37 (2015), 11; S. 2153 - 2163.

Zusätzliche Informationen

Last changed: 
19.01.2016 15:00:52
TU Id: 
247739
Accepted: 
Accepted
Invited: 
Department Focus: 
Business Informatics
Abstract German: 
Author List: 
A. Taha, A. Hanbury