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

您的问题也可能与此问题有关

这是一个很难的问题.一种可能的方法是自己实现欧几里德距离,完全放弃scipy并使用pypy的JIT编译器.但最有可能的是,这不会让你感到害怕.

就个人而言,我建议你用C编写例程.

问题不在于实现,而在于您解决此问题的方式.您通过计算每个可能的度量空间子集对中每个不同点对的欧几里德距离来选择强力方法.这在计算上要求很高:

• 假设您有500条曲线,每条曲线有75个点.使用蛮力方法,您最终计算欧氏距离500*499*75*75 = 1 403 437 500次.这种方法需要永远运行,这并不令人惊讶.

我不是这方面的专家,但我知道Hausdorff距离广泛用于图像处理.我建议你浏览文献中的速度优化算法.一个出发点可能是这个,或者这个文件.此外,经常与豪斯多夫距离结合提到的是Voroni图.

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

Answer 2

您可以尝试以下几种方法：

1. 使用numpy-MKL，它利用Intel的高性能数学内核库而不是numpy；
2. 使用 Bootleneck 进行数组函数；
3. 使用Cpython进行计算。