9

2D 配列 (点の数、座標の数) として定義された曲線のセットがあります。ハウスドルフ距離を使用して、それらの距離行列を計算しています。私の現在のコードは次のとおりです。残念ながら、それぞれが 50 ～ 100 の 3D ポイントを持つ 500 ～ 600 のカーブでは遅すぎます。そのためのより速い方法はありますか？

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

あなたの質問もこれに関連している可能性があります

これはちょっと難しい問題です。考えられる方法は、ユークリッド距離を自分で実装し、完全に放棄してpypyの JIT コンパイラscipyを利用することです。しかし、ほとんどの場合、これにより多くの利益が得られることはありません。

個人的には、ルーチンを C で書くことをお勧めします。

問題は実装ではなく、この問題へのアプローチ方法です。メトリック空間サブセットの可能な各ペア内のポイントの個別のペアごとにユークリッド距離を計算することによって、力ずくのアプローチを選択しました。これは計算量が多いです:

  • 500 個の曲線があり、それぞれに 75 個の点があるとします。力ずくのアプローチでは、ユークリッド距離を 500 * 499 * 75 * 75 = 1 403 437 500 回計算することになります。このアプローチの実行に永遠にかかることは、さらに驚くべきことではありません。

私はこれの専門家ではありませんが、ハウスドルフ距離が画像処理で広く使用されていることは知っています。速度が最適化されたアルゴリズムについては、文献を参照することをお勧めします。出発点は、この、またはこの論文かもしれません。また、ハウスドルフ距離と組み合わせてよく言及されるのは、ボロニ図です。

これらのリンクがこの問題の解決に役立つことを願っています。

于 2012-12-04T10:05:48.093 に答える
0

あなたが試すことができるいくつかの方法があります：

  1. numpy の代わりに Intel の高性能数学カーネル ライブラリを利用する numpy-MKL を使用します。
  2. 配列関数に Bootleneck を使用する。
  3. 計算には Cpython を使用します。
于 2012-12-04T01:53:08.803 に答える