Python3 隣接する特徴量座標の中心点を求めたい

Question

前提・実現したいこと

現在、OpenCVでの画像処理の学習を行っています。画像中の特徴量抽出することができました。隣接している特徴量座標の中心点を求めたいのですが、Numpy配列の操作でよい方法が思い浮かびません。ご指導ご鞭撻のほどよろしくお願いいたします。

以下のような配列を想定していいます。

X:596.0 Y:29.0
X:242.0 Y:32.0
X:242.0 Y:33.0
X:243.0 Y:33.0
X:288.0 Y:36.0
X:288.0 Y:37.0
X:289.0 Y:37.0
X:111.0 Y:50.0
X:112.0 Y:51.0

該当のソースコード

以下の通りで出力しています。

for i in range(len(index[0])):
        print("X:{} Y:{}".format(index[1][i],index[0][i]))

補足情報（FW/ツールのバージョンなど）

python3.6,OpenCV3.4.1

Answer 1

numpy を使うやり方

numpy の関数のみを使うのであれば、以下のやり方でできます。

1. ある点と他のすべての点との距離を計算し、距離行列を作成する。
2. 距離が最も近い点を隣接した点とする。(距離が同じなら複数ある可能性もある。)

サンプルコード

import matplotlib.pyplot as plt
import numpy as np
import seaborn as sn  # 無ければ、pip install seaborn

# 2次元の点を10個生成する。
points = np.random.randint(0, 10, (10, 2))

print('points.shape', points.shape)  # points.shape (10, 2)
print('points[:, np.newaxis].shape', points[:, np.newaxis].shape)  # points[:, np.newaxis].shape (10, 1, 2)
dist_matrix = np.linalg.norm(points[:, np.newaxis] - points, axis=-1)

# 距離行列を描画する。
plt.figure(figsize=(6, 6))
ax = sn.heatmap(dist_matrix, annot=True, cmap='Reds')
plt.show()

np.fill_diagonal(dist_matrix, np.inf)  # 一番近い点は自身の点なので、対角成分を Inf で埋める。

for i, dists in enumerate(dist_matrix):
    indices = np.where(dists == dists.min())[0]
    print('点 {} の最も近い点一覧: {}'.format(i, indices))

点 0 の最も近い点一覧: [8]
点 1 の最も近い点一覧: [5]
点 2 の最も近い点一覧: [4]
点 3 の最も近い点一覧: [8]
点 4 の最も近い点一覧: [7]
点 5 の最も近い点一覧: [1]
点 6 の最も近い点一覧: [9]
点 7 の最も近い点一覧: [4]
点 8 の最も近い点一覧: [3]
点 9 の最も近い点一覧: [6]

まず points[:, np.newaxis] - points で2点間の差を計算します。
10点あるとすると、points は (10, 2) の numpy 配列、points[:, np.newaxis] は (10, 1, 2) の numpy 配列なので、
points は (10, 2) -> (10, 10, 2)
points[:, np.newaxis] は (10, 1, 2) -> (10, 10, 2)
とブロードキャストが行われたあとに減算が行わるのて、これで任意の2点間の距離が計算できます。

次に np.linalg.norm() で2ノルム (ユークリッド距離) が計算できます。

以上の計算でできた dist_matrix は第 (i, j) 成分に点 i と 点 j の距離が入っています。
これを距離行列 (distance matrix) といいます。
対角成分 (i, i) は自身の点同士の距離なので、0になっています。

可視化してみるとわかりやすいでしょう。

あとは、点1に一番近い点を探したければ、この距離行列の1行目で値が一番小さい列を探せば、最も近い点を見つけたことになります。
(ただし、自身の点同士は距離が0で最も近いとなってしまうことを避けるために、np.fill_diagonal() で対角成分に INFINITY を入れています。)

提示された例の場合

import matplotlib.pyplot as plt
import numpy as np
import seaborn as sn  # 無ければ、pip install seaborn

# 2次元の点を10個生成する。
points = np.array([[596.0, 29.0],
                   [242.0, 32.0],
                   [242.0, 33.0],
                   [243.0, 33.0],
                   [288.0, 36.0],
                   [288.0, 37.0],
                   [289.0, 37.0],
                   [111.0, 50.0],
                   [112.0, 51.0]])

dist_matrix = np.linalg.norm(points[:, np.newaxis] - points, axis=-1)
np.fill_diagonal(dist_matrix, np.inf)  # 一番近い点は自身の点なので、対角成分を Inf で埋める。
for i, dists in enumerate(dist_matrix):
    # argmin() だと最小値が2つあっても一方のインデックスしか取得できないので、
    # np.where() を使う。
    indices = np.where(dists == dists.min())[0]
    print('点 {} の最も近い点一覧: {}'.format(i, indices))

点 0 の最も近い点一覧: [6]
点 1 の最も近い点一覧: [2]
点 2 の最も近い点一覧: [1 3]
点 3 の最も近い点一覧: [2]
点 4 の最も近い点一覧: [5]
点 5 の最も近い点一覧: [4 6]
点 6 の最も近い点一覧: [5]
点 7 の最も近い点一覧: [8]
点 8 の最も近い点一覧: [7]

Comments

[selva604]

とてもわかりやすい回答ありがとうございます。ユークリッド計算で求めた距離を行列にすることで近い点を見つける。。。勉強になりました。ありがとうございました。