python中曲线的距离矩阵

Question

我有一组定义为2D数组的曲线（点数，坐标）。我正在用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

Answer 1

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

我希望这有帮助，我在两两比较中遇到了25 x 25.000点（总共25 x 25 x 25.000点），代码运行时间从1分钟到3-4小时（取决于点数）。在数学上我看不出有多少方法可以提高速度。在

替代方案可以使用不同的编程语言（C/C++）或将此计算引入GPU（CUDA）。我现在正在玩CUDA方法。在

编辑日期：2015年12月3日：

我可以通过执行基于CPU的并行计算来加速这个比较。那是最快的办法。我使用了pp包（parallel python）的好例子，并在三种不同的计算机和phython组合上运行。 不幸的是，对于python2.732位，我一直有内存错误，所以我安装了64位的winpython2.764位软件包和一些实验性的numpy64位软件包。在

所以对我来说，这个效果是很有帮助的，对我来说它没有库达复杂。。。。祝你好运

Answer 2

您的问题也可能与this one有关

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

就我个人而言，我建议你用C写这个程序

问题不在于实现，而在于解决问题的方式。通过计算度量空间子集中每对不同点的欧几里得距离，您选择了一种强力方法。这需要计算：

• 假设你有500条曲线，每个曲线有75个点。用蛮力法计算欧几里德距离500*499*75*75=1403437500次。这种方法要花很长时间才能运行也就不足为奇了。在

我不是这方面的专家，但我知道Hausdorff距离广泛用于图像处理。我建议你浏览一下有关速度优化算法的文献。起点可以是this，或者this纸张。另外，经常与Hausdorff距离结合使用的是Voroni diagram。在

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

Answer 3

有几种方法可以尝试：

1. 使用numpy MKL，它使用英特尔的高性能数学内核库而不是numpy
2. 对数组函数使用Bootleneck
3. 使用Cpython进行计算。在