6

この質問は、私が使用した最終的な解決策を表示するための回答の後に編集されました

例のように、さまざまなソースからの非構造化 2D データセットが あります。これらの データセットは 3 numpy.ndarray (X、Y 座標、Z 値) です。データ例1：3D計測 サンプルデータ 2: 2D メッシュノード

私の最終的な目的は、これらのデータをグリッド上で補間して、画像/マトリックスに変換することです。したがって、これらのデータを補間するための「最適なグリッド」を見つける必要があります。そして、そのためには、そのグリッドのピクセル間の最適な X と Y のステップを見つける必要があります。

ポイント間のユークリッド距離に基づいてステップを決定する：

各点とその最も近い点の間のユークリッド距離の平均を使用します。

  • X,Y データの構築ツリーには scipy.spacial のKDTree/を使用します。cKDTree
  • queryメソッドを使用しk=2て距離を取得します ( の場合k=1、各ポイントのクエリがそれ自体を検出したため、距離はゼロになります)。


    # Generate KD Tree
    xy = np.c_[x, y]  # X,Y data converted for use with KDTree
    tree = scipy.spacial.cKDTree(xy)  # Create KDtree for X,Y coordinates.

    # Calculate step
    distances, points = tree.query(xy, k=2)  # Query distances for X,Y points
    distances = distances[:, 1:]  # Remove k=1 zero distances
    step = numpy.mean(distances)  # Result

パフォーマンスの調整:

  • scipy.spatial.cKDTreeand notを使用すると、scipy.spatial.KDTree実際に高速になるためです。
  • balanced_tree=False組み合わせて使用scipy.spatial.cKDTree​​: 私の場合は大幅に高速化されますが、すべてのデータに当てはまるとは限りません。
  • マルチスレッドを使用するn_jobs=-1には withを使用します。cKDTree.query
  • ユークリッド距離 ( ) の代わりにマンハッタン距離を使用p=1するために使用: 高速ですが、精度が低くなる場合があります。cKDTree.queryp=2
  • ポイントのランダムなサブサンプルのみの距離をクエリします。大規模なデータセットでは速度が大幅に向上しますが、精度と再現性が低下する可能性があります。

グリッド上の点を補間する:

計算されたステップを使用して、グリッド上のデータセット ポイントを補間します。



    # Generate grid
    def interval(axe):
        '''Return numpy.linspace Interval for specified axe'''
        cent = axe.min() + axe.ptp() / 2  # Interval center
        nbs = np.ceil(axe.ptp() / step)  # Number of step in interval
        hwid = nbs * step / 2  # Half interval width 
        return np.linspace(cent - hwid, cent + hwid, nbs)  # linspace

    xg, yg = np.meshgrid(interval(x), interval(y))  # Generate grid

    # Interpolate X,Y,Z datas on grid
    zg = scipy.interpolate.griddata((x, y), z, (xg, yg))

ピクセルがイニシャル ポイントから遠すぎる場合は NaN を設定します。

初期 X、Y、Z データのポイントから遠すぎる (距離 > ステップ) グリッドのピクセルに NaN を設定します。以前に生成された KDTree が使用されます。



    # Calculate pixel to X,Y,Z data distances
    dist, _ = tree.query(np.c_[xg.ravel(), yg.ravel()])
    dist = dist.reshape(xg.shape)

    # Set NaN value for too far pixels
    zg[dist > step] = np.nan
4

2 に答える 2

2

解決したい問題は、「全最近傍問題」と呼ばれます。たとえば、この記事を参照してください: http://link.springer.com/article/10.1007/BF02187718

これに対する解決策は O(N log N) であり、KDTree.query と同じ順序ですが、実際には、個別のクエリの束よりもはるかに高速です。申し訳ありませんが、これの Python 実装については知りません。

于 2016-01-16T03:54:19.353 に答える
1

と一緒に行くことをお勧めしますKDTree.query。

ビニングをスケーリングするために特徴的な距離を検索しています。ポイントのランダムなサブセットのみを取得し、マンハッタン距離KDTree.queryを使用することをお勧めします。

これが私のコードです：

# CreateTree
tree=scipy.spatial.KDTree(numpy.array(points)) # better give it a copy?
# Create random subsample of points
n_repr=1000
shuffled_points=numpy.array(points)
numpy.random.shuffle(shuffled_points)
shuffled_points=shuffled_points[:n_repr]
# Query the tree
(dists,points)=tree.query(shuffled_points,k=2,p=1)
# Get _extimate_ of average distance:
avg_dists=numpy.average(dists)
print('average distance Manhattan with nearest neighbour is:',avg_dists)

マンハッタン距離 ( https://en.wikipedia.org/wiki/Taxicab_geometry ) を使用することをお勧めします。これは、ユークリッド距離よりも計算が高速であるためです。また、平均距離の推定量だけが必要なので、それで十分です。

于 2016-01-15T15:10:12.387 に答える