I want to compute the Hausdorff distance between two (very large) binary images X and Y, which is:
$$H(X,Y) = \max\left\{\,h(X,Y), h(Y,X)\right\}\!$$
with
$$h(X,Y) = \sup_{x \in X} \inf_{y \in Y} d(x,y)$$
$d$ being the euclidean distance (or any kind of distance, as it doesn't matter).
The naive algorithm for $h$, comparing each pixel of $X$ to each pixel of $Y$, leading to a complexity of $O(X*Y)$, is way too slow.
I have read many papers saying it is possible to compute the Hausdorff distance in $O(X+Y)$ by first calculating the distance map (distance transform) of $X$ and $Y$.
I can easily compute these distance maps, but I don't see how they can lead to the Hausdorff distance, and I did not manage to find the algorithm in any of these papers.
So the question is, does anyone know how to compute the Hausdorff distance of two images according to their distance map ?