Hausdorff distance between two binary images according to distance maps
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)