問題
一連の候補位置 ( と の値) を使用して 2D グリッドを構築する必要がありXますY。ただし、フィルターで除外する必要がある偽陽性の候補や、偽陰性 (周囲の位置の値を考慮して予想される位置に対して位置を作成する必要がある場合) が存在する場合があります。グリッドの行と列は直線であると予想され、回転が小さい場合は回転します。
さらに、(0, 0) グリッドの位置に関する信頼できる情報はありません。しかし、私は知っています：
grid_size = (4, 4)
expected_distance = 105
(除外距離は、グリッド ポイント間の間隔の大まかな推定値にすぎず、10% の範囲で変動することが許容されます)。
サンプルデータ
これは、偽陽性も偽陰性もない理想的なデータです。アルゴリズムは、いくつかのデータポイントの削除と偽のデータポイントの追加にも対処できる必要があります。
X = np.array([61.43283582, 61.56626506, 62.5026738, 65.4028777, 167.03030303, 167.93965517, 170.82191781, 171.37974684, 272.02884615, 272.91089109, 274.1031746, 274.22891566, 378.81553398, 379.39534884, 380.68181818, 382.67164179])
Y = np.array([55.14427861, 160.30120482, 368.80213904, 263.12230216, 55.1030303, 263.64655172, 162.67123288, 371.36708861, 55.59615385, 264.64356436, 368.20634921, 158.37349398, 54.33980583, 160.55813953, 371.72727273, 266.68656716])
コード
次の関数は候補を評価し、2 つの辞書を返します。
キーと値は、隣接する位置の右と下の 2 つの長さのタプルであるため、最初のものは (2 つの長さのタプルとして) 各候補位置を持ちます (画像の表示方法のロジックを使用)。これらの隣接要素自体は、長さ 2 のタプル座標またはNone.
2 番目のディクショナリは最初のディクショナリの逆ルックアップであり、各候補 (位置) にはそれをサポートする他の候補の位置のリストがあります。
import numpy as np
from collections import defaultdict
def get_neighbour_grid(X, Y, expect_dist=(105, 105)):
t1 = (expect_dist[0] + expect_dist[1]) / 2.0 * 0.9
t2 = t1 * 1.222
def neighbours(x, y):
nRight = None
ideal = x + expect_dist[0]
D = np.sqrt((X - ideal)**2 + (Y - y)**2)
candidate = (X[D.argmin()], Y[D.argmin()])
if candidate != (x, y) and x + t2 > candidate[0] > x + t1:
nRight = candidate
nBelow = None
ideal = y + expect_dist[0]
D = np.sqrt((X - x)**2 + (Y - ideal)**2)
candidate = (X[D.argmin()], Y[D.argmin()])
if candidate != (x, y) and y + t2 > candidate[1] > y + t1:
nBelow = candidate
return nRight, nBelow
right_below_neighbours = dict()
def _default_val(*args):
return list()
reverse_lookup = defaultdict(_default_val)
for pos in np.arange(X.size):
pos_tuple = (X[pos], Y[pos])
n = neighbours(*pos_tuple)
right_below_neighbours[pos_tuple] = n
reverse_lookup[n[0]].append(pos_tuple)
reverse_lookup[n[1]].append(pos_tuple)
return right_below_neighbours, reverse_lookup
これが私が立ち往生する場所です：
これらの辞書をどのように使用して、および/またはX最もYサポートされているグリッドを構築するのですか?
私は、2 つの隣人によってサポートされている右下の候補から開始し、reverse_lookup辞書を使用してグリッドを繰り返し作成するというアイデアを思いつきました。しかし、その設計にはいくつかの欠陥があります。最も明白なのは、最下位の右端の候補とそのサポートする隣接候補の両方を検出できたことを当てにできないことです。
そのためのコードですが、問題があることに気付いたときに放棄したため、実行されません ( pre_grid = right_below_neighbours):
def build_grid(pre_grid, reverse_lookup, grid_shape=(4, 4)):
def _default_val(*args):
return 0
grid_pos_support = defaultdict(_default_val)
unsupported = 0
for l, b in pre_grid.values():
if l is not None:
grid_pos_support[l] += 1
else:
unsupported += 1
if b is not None:
grid_pos_support[b] += 1
else:
unsupported += 1
well_supported = list()
for pos in grid_pos_support:
if grid_pos_support[pos] >= 2:
well_supported.append(pos)
well_A = np.asarray(well_supported)
ur_pos = well_A[well_A.sum(axis=1).argmax()]
grid = np.zeros(grid_shape + (2,), dtype=np.float)
grid[-1,-1,:] = ur_pos
def _iter_build_grid(pos, ref_pos=None):
isX = pre_grid[tuple(pos)][0] == ref_pos
if ref_pos is not None:
oldCoord = map(lambda x: x[0], np.where(grid == ref_pos)[:-1])
myCoord = (oldCoord[0] - int(isX), oldCoord[1] - int(not isiX))
for p in reverse_lookup[tuple(pos)]:
_iter_build_grid(p, pos)
_iter_build_grid(ur_pos)
return grid
ただし、最初の部分は、各ポジションのサポートを要約しているため、役立つ場合があります。また、最終出力として必要なものも示しています ( grid):
最初の 2 つの次元がグリッドの形状で、3 つ目の次元が長さ 2 (各位置の x 座標と y 座標) の 3D 配列。
要約
だから私は自分の試みがいかに役に立たなかったかを理解していますが、すべての候補をグローバルに評価し、候補の x 値と y 値を使用して最もサポートされているグリッドをどこにでも配置する方法について途方に暮れています。これは非常に複雑な質問だと思いますが、誰かが完全な解決策を提供するとは本当に期待していません (それは素晴らしいことですが) が、どのタイプのアルゴリズムまたは numpy/scipy 関数を使用できるかについてのヒントは感謝します。
最後に、これはやや長い質問で申し訳ありません。
編集
私がしたいことの描画：
星/ドットは でXありY、2 つの変更を加えてプロットされています。最初の位置を削除し、偽の位置を追加して、これを求めるアルゴリズムの完全な例にしました。
つまり、赤丸で囲まれた位置の新しい座標値 (横に書かれている値) をマッピングして、新しい座標から古い座標を取得できるようにすることです (例: (1, 1) -> (170.82191781, 162.67123288))。また、真の点が表す理想的なグリッドに近似しない点を破棄し (示されているように)、最終的に空の理想的なグリッド位置 (青い円) を理想的なグリッド パラメータ (およそ(0, 0) -> (55, 55)) を使用して「塗りつぶす」必要があります。
解決
@skymandr が提供するコードを使用して理想的なパラメーターを取得し、次のことを行いました (最も美しいコードではありませんが、機能します)。つまり、私はget_neighbour_gridもう -functionを使用していません.:
def build_grid(X, Y, x_offset, y_offset, dx, dy, grid_shape=(16,24),
square_distance_threshold=None):
if square_distance_threshold is None:
square_distance_threshold = ((dx + dy) / 2.0 * 0.05) ** 2
grid = np.zeros(grid_shape + (2,), dtype=np.float)
D = np.zeros(grid_shape)
for i in range(grid_shape[0]):
for j in range(grid_shape[1]):
D[i,j] = i * (1 + 1.0 / (grid_shape[0] + 1)) + j
rD = D.ravel().copy()
rD.sort()
def find_valid(x, y):
d = (X - x) ** 2 + (Y - y) ** 2
valid = d < square_distance_threshold
if valid.any():
pos = d == d[valid].min()
if pos.sum() == 1:
return X[pos], Y[pos]
return x, y
x = x_offset
y = y_offset
first_loop = True
for v in rD:
#get new position
coord = np.where(D == v)
#generate a reference position already passed
if coord[0][0] > 0:
old_coord = (coord[0] - 1, coord[1])
elif coord[1][0] > 0:
old_coord = (coord[0], coord[1] - 1)
if not first_loop:
#calculate ideal step
x, y = grid[old_coord].ravel()
x += (coord[0] - old_coord[0]) * dx
y += (coord[1] - old_coord[1]) * dy
#modify with observed point close to ideal if exists
x, y = find_valid(x, y)
#put in grid
#print coord, grid[coord].shape
grid[coord] = np.array((x, y)).reshape(grid[coord].shape)
first_loop = False
return grid
それは別の問題を提起します.2D配列の対角線に沿ってうまく反復する方法ですが、それはそれ自体の質問に値すると思います.2D配列の「直交」対角線を反復するより派手な方法
編集
すべての位置の理想的な座標の参照として既に渡された隣接するグリッド位置を使用するように、より大きなグリッド サイズをより適切に処理するようにソリューション コードを更新しました。リンクされた質問からグリッドを反復処理するより良い方法を実装する方法を見つける必要があります。