Hausdorff distance between two binary images according to distance maps

Question

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 ?

Answer 1

So I finally managed to do it, here's the answer for future reference.

The idea is not to compute the distance map of the image, but of its complement.

Here's a example to better understand :

You have these binary images, where our objects are in black :

Object $X$

Object $Y$

To compute $h(Y, X)$, you need to compute the distance map $dX$ of the complement of $X$ (here using 4-adjacency, but work the same with any distance):

The distance is 0 on the object.

You now only need to find the $max(dX[i,j])$ such as $Y[i, j]$ is in the object.

Here's our example with $Y[i, j]$ in the object in orange, and the $max(dX[i,j])$ in red :

So $h(Y, X) = 3$.

$h(X, Y)$ is computed in a similar fashion, using $dY$ and $X$.

Now that you have $h(X,Y)$ and $h(Y,X)$, you can easily compute the Hausdorff distance $H(X,Y) = \max\left\{\,h(X,Y), h(Y,X)\right\}\!$.

If you already have your distance map, the complexity of the Hausdorf distance is obviously $O(X + Y)$ with this algorithm since you only need to iterate one time over each image.

Note that computing the distance matrix is also done in linear time, so its always better to go with this method instead of the naive one.

Here some sources:

• A Linear Time Algorithm of Computing Hausdorff Distance for Content-based Image Analysis (M. Julius Hossain, M. Ali Akber Dewan, Kiok Ahn and Oksam Chae)
• An image algorithm for computing the Hausdorff distance efficiently in linear time (R. Shonkwiler)