3D网格之间的豪斯多夫距离

Question

我有多个网格（numpy数组[Nk，Ny，Nx]），想要使用Hausdorff距离作为这些网格相似性的度量标准。scipy中有几个模块（scipy.spatial.distance.cdist、scipy.spatial.distance.pdist）可以计算2D数组之间的欧几里德距离。现在，为了比较网格，我必须选择一些横截面（例如grid1 [0,:]和grid2 [0,:]），并将它们彼此比较。是否可能直接计算3D网格之间的Hausdorff距离？

- Vitali Molchan

---

这个问题 (https://dev59.com/42vXa4cB1Zd3GeqPLKFI) 可能是相关的。结论似乎是没有 scipy/numpy 算法，如果速度很关键，最好用 c 写主算法 (这是针对 2D 的情况)。 - Ed Smith

Farhawa，非常感谢！ - Vitali Molchan

Answer 1

我是新手，但面临着相同的挑战，尝试在三维层面直接解决它。

以下是我编写的函数：

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)

输入需要是numpy.array，但其余部分可以直接使用。

我有8000个对比5000个三维点，这需要几分钟时间，但最终会得到你寻找的距离。

然而，这只检查两点之间的距离，而不一定是两条曲线的距离（也不是网格）。 编辑（于2015年11月26日）： 最近完成了该代码的精细调整版本。现在它被分成两部分。

第一部分负责抓取给定点周围的一个盒子并获取所有半径。我认为这是减少所需检查点数量的聪明方式。

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

还有用于距离计算的另一段代码：

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)

- Akos Gulyban

Answer 2

如果有人多年后仍在寻找此问题的答案……自2016年起，scipy现在包含一个用于计算三维Hausdorff距离的函数：

scipy.spatial.distance.directed_hausdorff

- craq

---

此函数仅支持2D。 - Guillaume Mougeot

有趣的是...文档说它只支持2D，但在我的测试中它可以在3D中工作。查看代码，似乎根本没有任何数组维度限制。你同意吗？如果是这样，我可能会向scipy提出一个工单，让他们更新他们的文档。 - craq

你似乎是对的！是的，也许可以向Scipy提出一个工单。 - Guillaume Mougeot

不需要门票。函数返回“两个二维坐标数组之间的距离”，其中2D表示二维数组。您可能有两个N维点列表。 - Dom

Answer 3

有一个名为point_cloud_utils的软件包，它提供了一些3D度量，例如Hausdorff距离。使用pip install point_cloud_utils安装它，然后按照以下方式使用：

import point_cloud_utils as pcu
import numpy as np

# Generate two random point sets
a = np.random.rand(1000, 3)
b = np.random.rand(500, 3)

# Compute one-sided squared Hausdorff distances
hausdorff_a_to_b = pcu.one_sided_hausdorff_distance(a, b)
hausdorff_b_to_a = pcu.one_sided_hausdorff_distance(b, a)

# Take a max of the one sided squared  distances to get the two sided Hausdorff distance
hausdorff_dist = pcu.hausdorff_distance(a, b)

- Philipp