Search code examples
algorithmdistanceeuclidean-distance

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!

Solution

  • 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