4
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ What is the domain of $x,y$? Is $x$ an integer in $\{0,1,\dots,255\}$? A real number? A 3-vector? Something else? $\endgroup$ – D.W. Dec 3 '19 at 6:08
  • $\begingroup$ Since you are using the word pixels, I assume you are using a discrete grid. However, you are using supremum and infimum. So … are you also interested in "the values between integer coordinates"? $\endgroup$ – Albjenow Dec 3 '19 at 7:08
  • $\begingroup$ @D.W.♦ $x$, $y$ are pixels on an image, so a 2-vector. $\endgroup$ – FPSedin Dec 3 '19 at 17:06
  • $\begingroup$ @Albjenow Yes it is on a discrete grid. I used $sup$ and $inf$ as it is how the Hausdorff distance is defined on the Wikipedia page. I guess $max$ and $min$ should be more appropriate in my case $\endgroup$ – FPSedin Dec 3 '19 at 17:08
4
$\begingroup$

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$

enter image description here

Object $Y$

enter image description here

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):

enter image description here

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 :

enter image description here

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:

$\endgroup$
  • 1
    $\begingroup$ Awesome! I've seen this concept in math but never saw an algorithm for it. One comment is that in your OP you say you are using $d=$ Euclidean distance but in this answer you are using Manhattan distance (which seems to make more sense given the grid setup). $\endgroup$ – Matthew C Dec 3 '19 at 18:13
  • $\begingroup$ @user111398 In my application, I needed the euclidean distance, but for the sake of example (and easier time making the images :) ), I used d4. It works exactly the same with any distance anyway, just compute the distance matrix with the one you need. $\endgroup$ – FPSedin Dec 3 '19 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.