Hausdorff distance between three-dimensional grids

Question

I have several grids (numpy [Nk, Ny, Nx] arrays) and would like to use the Hausdorff distance as a similarity metric for these grids. There are several modules in scipy (scipy.spatial.distance.cdist, scipy.spatial.distance.pdist) that allow you to calculate the Euclidean distance between 2D arrays. Now, to compare the grids, I have to select some kind of cross section (for example, grid1 [0 ,:] and grid2 [0 ,:]) and compare it with each other. Is it possible to directly calculate the Hausdorff distance between three-dimensional grids?

Answer 1

I am new here, but ran into the same challenge and tried to attack him directly at the three-dimensional level.

So here is what I did:

def Hausdorff_dist(vol_a,vol_b): dist_lst = [] for idx in range(len(vol_a)): dist_min = 1000.0 for idx2 in range(len(vol_b)): dist= np.linalg.norm(vol_a[idx]-vol_b[idx2]) if dist_min > dist: dist_min = dist dist_lst.append(dist_min) return np.max(dist_lst) 

The input should be numpy.array, but the rest works directly.

I have 8000 vs 5000 3D glasses, and this lasts a few minutes, but in the end it comes close to the distance you are looking for.

This, however, is a check of the distance between two points, not necessarily the distance of two curves. (no mesh).

Edit (11/26/2015):

Recenty has completed a finely tuned version of this code. Now it is divided into two parts.

First you need to take care of capturing a box around a given point and taking the entire radius. I think this is a reasonable way to reduce the number of points required for verification.

 def bbox(array, point, radius): a = array[np.where(np.logical_and(array[:, 0] >= point[0] - radius, array[:, 0] <= point[0] + radius))] b = a[np.where(np.logical_and(a[:, 1] >= point[1] - radius, a[:, 1] <= point[1] + radius))] c = b[np.where(np.logical_and(b[:, 2] >= point[2] - radius, b[:, 2] <= point[2] + radius))] return c 

And another code to calculate the distance:

 def hausdorff(surface_a, surface_b): # Taking two arrays as input file, the function is searching for the Hausdorff distane of "surface_a" to "surface_b" dists = [] l = len(surface_a) for i in xrange(l): # walking through all the points of surface_a dist_min = 1000.0 radius = 0 b_mod = np.empty(shape=(0, 0, 0)) # increasing the cube size around the point until the cube contains at least 1 point while b_mod.shape[0] == 0: b_mod = bbox(surface_b, surface_a[i], radius) radius += 1 # to avoid getting false result (point is close to the edge, but along an axis another one is closer), # increasing the size of the cube b_mod = bbox(surface_b, surface_a[i], radius * math.sqrt(3)) for j in range(len(b_mod)): # walking through the small number of points to find the minimum distance dist = np.linalg.norm(surface_a[i] - b_mod[j]) if dist_min > dist: dist_min = dist dists.append(dist_min) return np.max(dists)