2

I am working on my final year M.Tech. project. It involves using Hausdorff Distance to compare images. In the process of understanding it, I stumbled upon this website which states that Hausdorff Distance is sensitive to position. I have refered several papers and articles but unable to understand how this is possible. Can someone please explain it to me or atleast point me towards a link that will help me to understand this.

Thank you

Asaf Karagila
  • 393,674
Yash
  • 281
  • 1
    Note that the first definition given for Hausdorff distance is not actually even a distance; the real Hausdorff distance is the "generalized" version. Could you explain more in detail what you mean by the expression: sensitive to position? – T. Eskin Mar 12 '13 at 08:23
  • @Thomas E, "Sensitive to position" is exactly what I am not understanding. According to the link in my question, it says that Hausdorff Distance is sensitive to position and they show it by drawing circles enclosing the polygons with radius equal to the Hausdorff distance between the polygons. They show two figures where in the dimension of the polygons remain same but their positions are changed and the radius of the enclosing circles are different in the figures. This, they suggest is the proof for Hausdorff distance being sensitive to position, which i am unable to understand. – Yash Mar 13 '13 at 12:46

1 Answers1

2

Compare figures 1 and 2. They depict two triangles such that the shortest distance between them is the same. However, qualitatively, the two triangles in figure 2 appear closer than the two triangles in figure 1. This is what the website calls the insensitivity of the shortest distance metric to position (the way the shapes are posed in the ambient space).

Now look at figures 4 and 5. Figure 4 depicts the same triangles as in figure 1, and figure 5 depicts the same triangles as in figure 2. Now, what is computed is the Hausdorff distance instead of the shortest distance. It is now seen that the Hausdorff distance between the triangles in figure 4 is larger than for those in figure 5. Thus, it is seen that the Hausdorff distance captures the initial intuition that the triangles in figure 5 are indeed closer.

This property, that the Hausdorff distance considers the position (again, the way the shapes are posed in the ambience), is what the website calls the sensitivity of the Hausdorff distance to position.

I'm not sure this terminology is very illuminating. I would say something along the lines of "the Hausdorff distance is sensitive to the global positioning of the two sets, and not just to the local distances".

A more straightforward example would be in $\mathbb R$. Consider $A=[0,1]$ and $B=[2,3]$. The shortest distance metric between $A$ and $B$ is $1$. The Hausdorff distance between $A$ and $B$ is 2. Now, consider $B'=[2,100]$. The shortest distance between $A$ and $B'$ did not change, it's still $1$. But the Hausdorff distance is between $A$ and $B'$ is now $99$. The shortest distance metric is blind to the global relative positioning of the two shapes, but the Hausdorff distance picks it up.

Ittay Weiss
  • 79,840
  • 7
  • 141
  • 236
  • 1
    A small note to the second sentence in the last paragraph: the shortest distance is not actually a metric. It fails to satisfy e.g. the condition $d(A,B)=0\Leftrightarrow A=B$. – T. Eskin Mar 13 '13 at 12:55
  • that depends on the definition of metric space. More and more texts drop the demand that $d(x,y)=0$ implies $x=y$, calling metric spaces that do satisfy this property separated. There are plenty of reasons to do that, one is the enhance the analogy with topological spaces. Separated metric spaces correspond to Hausdorff spaces. – Ittay Weiss Mar 13 '13 at 21:11
  • I only mentioned that condition in order to avoid writing concrete counter-examples. However, the shortest distance also fails to satisfy the triangle-inequality. Take $A=[0,1]$, $B=[2,3]$, and $C=[4,5]$ as a simple example. By shortest distance, $d(A,C)>d(A,B)+d(B,C)$, since $3>2$. I don't think the triangle inequality is negotiable when defining metric spaces. What is there left, the symmetry? – T. Eskin Mar 13 '13 at 21:18
  • of course, no letting go of the triangle inequality in metric spaces. I thought you were referring to the Hausdorff distance limited to closed subsets in order to force separability. As you say, due to failure of the triangle inequality, the shortest distance does not make the set of subsets (closed or not) of a metric space into a metric space. – Ittay Weiss Mar 13 '13 at 21:24