CODEWITHSUNDEEP
algorithmdistanceeuclidean-distance
toobee
toobee

Reputation: 2752

Hausdorff Distance between Points of two meshes

I have to implement the Hausdorff distance for 2 meshes. The meshes are different segmentation results of an human organ and I have to compare them, one mesh is a gold seg. and the second one the result of a segmentation algorithm.

I shall use the Hausdorff distance, but have some problems understanding what exactly I have to do. I understood that I have to calculate the nearest point for each point in meshA in meshB and vice versa. These are my relative distances. For 2 corresponding points in the sets I take the maximal relative distance => hausdorff. (thats how far I am)

Now my problem: One mesh has ~100,000 points the other one ~2,000. Hence, it will be n:1 relationships. Which points do I take for calculating Hausdorff, how do I tackle that? Would appreciate any hint. Thx!

Upvotes: 2

Views: 4352

Answers (2)

Fedor
Fedor

Reputation: 21317

Hausdorff distance between two objects is the longest distance from a point of one of the objects to the closest point on the other object.

For triangular meshes there are two possible scenarios, where such longest distance can be found:

  1. One point is in a vertex of one mesh, and the closest point is on triangle of the other mesh.
  2. Both points are situated inside edges of the corresponding meshes. This scenario is frequently ignored for performance reasons.

But even brute force approach with considering only vertex-triangle distances is prohibitively slow for the meshes like in the question. And a typical solution is to construct a bounding volume hierarchy BVH (e.g. AABB-tree) for each mesh, and then to use BVH for acceleration of closest point location.

One of the open-source implementations of this algorithm with the usage of AABB-trees can be found in MeshLib, see the function findMaxDistanceSq, which actually returns the square of Hausdorff distance (yet another small optimization).

Upvotes: 0

Dmitry Zagorulkin
Dmitry Zagorulkin

Reputation: 8548

If x and x is a finite or countable union, then sum

If x and y are metric spaces, then the Hausdorff dimension of their product satisfies sum

upd: Brute force algorithm :

1.  h = 0 
2.  for every point ai of A,
      2.1  shortest = Inf ;
      2.2  for every point bj of B
                    dij = d (ai , bj )
                    if dij < shortest then
                              shortest = dij
      2.3  if shortest > h then 
                    h = shortest

Upvotes: 1

Related Questions