9

我有一组曲线定义为二维数组（点数，坐标数）。我正在使用 Hausdorff 距离为他们计算距离矩阵。我当前的代码如下。不幸的是，它太慢了，500-600 条曲线每条有 50-100 个 3D 点。有没有更快的方法呢？

def distanceBetweenCurves(C1, C2):
    D = scipy.spatial.distance.cdist(C1, C2, 'euclidean')

    #none symmetric Hausdorff distances
    H1 = np.max(np.min(D, axis=1))
    H2 = np.max(np.min(D, axis=0))

    return (H1 + H2) / 2.

def distanceMatrixOfCurves(Curves):
    numC = len(Curves)

    D = np.zeros((numC, numC))
    for i in range(0, numC-1):
        for j in range(i+1, numC):
            D[i, j] = D[j, i] = distanceBetweenCurves(Curves[i], Curves[j])

    return D
4

3 回答 3

6

您的问题也可能与此有关

这是一个难题。一种可能的方法是自己实现欧几里得距离，完全放弃scipy并使用pypy的 JIT 编译器。但这很可能不会让你变得太多。

就个人而言，我建议您用 C 编写例程。

问题不在于实施，而在于您解决此问题的方式。您通过计算每对可能的度量空间子集中的每对不同点的欧几里德距离来选择一种蛮力方法。这对计算要求很高：

  • 假设你有 500 条曲线，每条曲线有 75 个点。使用蛮力方法，您最终计算欧几里得距离 500 * 499 * 75 * 75 = 1 403 437 500 次。这种方法需要永远运行也就不足为奇了。

我不是这方面的专家，但我知道 Hausdorff 距离广泛用于图像处理。我建议您浏览文献以了解速度优化算法。起点可能是this或this paper。此外，经常与豪斯多夫距离一起提到的是沃罗尼图。

我希望这些链接可以帮助您解决这个问题。

于 2012-12-04T10:05:48.093 回答
3

我最近在这里回答了一个类似的问题： Hausdorff distance between 3D grids

我希望这会有所帮助，我在成对比较中遇到了 25 x 25.000 点（总共 25 x 25 x 25.000 点），并且我的代码运行时间从 1 分钟到 3-4 小时（取决于点数）。我在数学上看不到太多提高速度的选择。

替代方案可以是使用不同的编程语言 (C / C++) 或将此计算带到 GPU (CUDA)。我现在正在使用 CUDA 方法。

2015 年 3 月 12 日编辑：

通过进行基于并行 CPU 的计算，我能够加快这种比较。那是最快的方法。我使用了pp包（parallel python）的好例子，并在三台不同的计算机和 phython 组合上运行。不幸的是，我一直在使用 python 2.7 32 位时出现内存错误，所以我安装了 WinPython 2.7 64 位和一些实验性的 numpy 64 位软件包。

在此处输入图像描述

所以对我来说，这种努力非常有帮助，它对我来说并不像 CUDA 那样复杂......祝你好运

于 2015-11-26T10:13:10.317 回答
0

您可以尝试几种方法：

  1. 使用 numpy-MKL，它利用 Intel 的高性能数学内核库而不是 numpy；
  2. 使用 Bootleneck 处理数组函数；
  3. 使用 Cpython 进行计算。
于 2012-12-04T01:53:08.803 回答