0

以下のように座標が格納されたリストがあり、そこからaとbお互いの最も近い座標同士を一対一で対応させたいのですが

import numpy as np

a = np.array([[38,139], [60,150], [188, 71], [41, 138]])
b = np.array([[23,188], [70, 172], [52, 196]])

for i in a:
    min = np.linalg.norm(i - b[0])
    for j in b:
        c = np.linalg.norm(i - j)
        if min > c:
            min = c
            #index_a = np.where(a[:] == i)
            #index_b = np.where(b[:] == j)
            result = np.array([min, i, j])
        else:
            pass
    print(result)
【出力結果】
[45.967379738244816 array([ 38, 139]) array([ 70, 172])]
[24.166091947189145 array([ 60, 150]) array([ 70, 172])]
[155.32224567009067 array([188,  71]) array([ 70, 172])]
[44.68780594300866 array([ 41, 138]) array([ 70, 172])]

というように全てのaの座標が同じbの座標を最近点としてしまいます。この場合、採用するのは

[24.166091947189145 array([ 60, 150]) array([ 70, 172])]

の座標のペアで、次はこの座標を除いてそれぞれを比較し、どちらかのリストの要素がなくなるまでそれを繰り返したいのですがどうしたら良いでしょうか?

コメントからの転記

2画像間の物体の移動距離を調べることなのですが、独立した2枚の画像だと例えば、1枚目で移動前の人間を3人検出して、2枚目で移動後の3人の人間を検出したとき、2枚目の3人の人間は1枚目の画像のどこの場所にいた人間だったのかが分からないので、それぞれの物体の移動前の中心座標(x,y)をaに、移動後のそれぞれの物体中心座標(x,y)をbに入れて、「移動前の座標から一番近い移動後の座標を同じ物体の移動前と移動後の座標とする」という仮定のもと、aとbのそれぞれの座標の距離を調べて一番近いものを探すということをしていたので、aとbには移動前と移動後という順序があります。

3
  • 試行錯誤の後だったので関係ない文が残ってしまっていました。申し訳ありませんでした。
    – Awax2
    2019年11月3日 13:00
  • ちなみに、除く座標というのは具体的に何で、それを選択するためにはどう判断するのでしょう?
    – kunif
    2019年11月3日 14:42
  • 出力結果の複数のリストの中から0番目の数字が一番小さいものを選択。今回は [24.166091947189145 array([ 60, 150]) array([ 70, 172])] を採用。そして、array([ 60, 150])をリストaから、array([ 70, 172])をリストbから除いて、 a = [[38,139], [188, 71], [41, 138]] b = [[23,188], [52, 196]] の状態にしたいです。
    – Awax2
    2019年11月3日 15:47

2 件の回答 2

0

質問に記載されたデータだけの動作ですが、
以下の様な感じで numpy の array から削除しつつ処理出来ます。

関数にして、削除した後の配列と、検出した結果の配列を返すようにしてみました。

line_profilerで計って 約 761 マイクロ秒になりました。
numpyのデータでなくても良いのでは?と思ったところを素のPythonのデータにしています。

import numpy as np

def nearest(a, b):
    d = []  # 最短結果通知用に初期化 numpy でなくても良い?

    # どちらも空でない間だけループ実行
    while (len(a) > 0) and (len(b) > 0):

        # あり得ない値で初期化
        out_min = 9999999999.9
        out_res = []

        for i in a:
            min = np.linalg.norm(i - b[0])
            result = [min, i, b[0]]  # result も min に対応した初期値を入れておく
            for j in b:
                c = np.linalg.norm(i - j)
                if min > c:
                    min = c
                    result = [min, i, j]  # index取得のコメントは外に移動して有効化
                else:
                    pass

            # 外側のループで最小値を更新する
            if out_min > min:
                out_min = min
                out_res = result

        # 最小値の要素の index を取得して、元のデータから削除
        a = np.delete(a, np.where(a[:] == out_res[1])[0], 0)
        b = np.delete(b, np.where(b[:] == out_res[2])[0], 0)
        d.append(out_res)  # 最短結果通知用に格納

    return a, b, d

a = np.array([[38,139], [60,150], [188, 71], [41, 138]])
b = np.array([[23,188], [70, 172], [52, 196]])
ra, rb, rd = nearest(a, b)

ちなみに @metropolis さんの処理を元に、同様の結果を得られるようにしてみました。

同じくline_profilerで計って 約 349 マイクロ秒と半分以下になっています。

import numpy as np
from itertools import product

def nearest(a, b):

    na, nb = len(a), len(b)
    ## Combinations of a and b
    comb = product(range(na), range(nb))
    ## [[distance, index number(a), index number(b)], ... ]
    l = [[np.linalg.norm(a[ia] - b[ib]), ia, ib] for ia, ib in comb]
    ## Sort with distance
    l.sort(key=lambda x: x[0])

    xa = []
    xb = []
    d = []
    for _ in range(min(na, nb)):
        m, ia, ib = l[0]
        xa.append(ia) # 元データ配列からの削除用に追加
        xb.append(ib) # 同じ
        d.append([m, a[ia], b[ib]])  # 最短結果通知用に格納
        ## Remove items with same index number
        l = list(filter(lambda x: x[1] != ia and x[2] != ib, l))

    a = np.delete(a, xa, 0) # 元データ配列からデータ削除
    b = np.delete(b, xb, 0) # 同じ

    return a, b, d

a = np.array([[38,139], [60,150], [188, 71], [41, 138]])
b = np.array([[23,188], [70, 172], [52, 196]])
ra, rb, rd = nearest(a, b)

さらにちなみに上記結果通知を行わずに関数化だけした @metropolis さんの処理は、
print文有りで 約 819 マイクロ秒、print文無しで 約 197 マイクロ秒でした。

0

予め ab の要素(座標位置)間の距離を全ての組み合わせで計算してソートしておきます。そして、最小距離の要素ペアと同じインデックス番号を持つ要素を取り除きます。これを、ab の要素数で少ない方の回数だけ実行します。

import numpy as np
from itertools import product

a = np.array([[38,139], [60,150], [188, 71], [41, 138]])
b = np.array([[23,188], [70, 172], [52, 196]])

na, nb = len(a), len(b)
## Combinations of a and b
comb = product(range(na), range(nb))
## [[distance, index number(a), index number(b)], ... ]
l = [[np.linalg.norm(a[ia] - b[ib]), ia, ib] for ia, ib in comb]
## Sort with distance
l.sort(key=lambda x: x[0])

for _ in range(min(na, nb)):
  m, ia, ib = l[0]
  print([m, a[ia], b[ib]])
  ## Remove items with same index number
  l = list(filter(lambda x: x[1] != ia and x[2] != ib, l))

実行結果

[24.166091947189145, array([ 60, 150]), array([ 70, 172])]
[51.24451190127583, array([ 38, 139]), array([ 23, 188])]
[59.033888572581766, array([ 41, 138]), array([ 52, 196])]
2
  • 完全に私の説明不足で申し訳ないのですが、本当にやりたいことは、2画像間の物体の移動距離を調べることなのですが、独立した2枚の画像だと例えば、1枚目で移動前の人間を3人検出して、2枚目で移動後の3人の人間を検出したとき、2枚目の3人の人間は1枚目の画像のどこの場所にいた人間だったのかが分からないので、それぞれの物体の移動前の中心座標(x,y)をaに、移動後のそれぞれの物体中心座標(x,y)をbに入れて、「移動前の座標から一番近い移動後の座標を同じ物体の移動前と移動後の座標とする」という仮定のもと、aとbのそれぞれの座標の距離を調べて一番近いものを探すということをしていたので、aとbには移動前と移動後という順序はあります。すみませんでした。
    – Awax2
    2019年11月3日 16:18
  • @Awax2 質問欄に転記しました。
    – user39889
    2019年11月3日 16:41

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。