60231


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

[code]

    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)
    
[/code]

[code]

    【出力結果】
    [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])]
    
[/code]

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

[code]

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

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

**コメントからの転記**

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


CC BY-SA 4.0
2019-11-03T12:32:54.943
60220
2019-11-05T06:33:17.650
2019-11-03T16:40:53.390
31836
question
python numpy
最も近い座標同士を一対一で対応させたいです


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

[code]

    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))
    
[/code]

**実行結果**

[code]

    [24.166091947189145, array([ 60, 150]), array([ 70, 172])]
    [51.24451190127583, array([ 38, 139]), array([ 23, 188])]
    [59.033888572581766, array([ 41, 138]), array([ 52, 196])]
    
[/code]


CC BY-SA 4.0
2019-11-03T14:55:22.067
60224
2019-11-03T17:15:49.987
2019-11-03T17:15:49.987
60220
answer


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

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

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

[code]

    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)
    
[/code]

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

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

[code]

    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)
    
[/code]

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


CC BY-SA 4.0
2019-11-03T17:05:46.040
60231
2019-11-05T06:33:17.650
2019-11-05T06:33:17.650
26370
26370
60220
answer