以下のような感じでしょうか?
- y 座標を見て、各矩形をクラスタリングする。
- 同じクラスの矩形は外接する矩形に置き換える。
追記
コメント欄の矩形をプロットしたら以下のようになったのですが、グループ分けする基準はなんでしょうか?
追記
y 座標を見て Mean-Shift でクラスタリングする方法では、以下のようにあまりうまくいかなかったので、隣接する矩形を調べて、find-union アルゴリズム でグループ分けする方法を試してみました。
1. データ読み込み
test.txt に (N行、8列) でスペース区切りの矩形の座標値が入っているものとする。
python
1import numpy as np
2import matplotlib.pyplot as plt
3from matplotlib.patches import Rectangle
4
5# 矩形のデータを読み込む。
6data = np.loadtxt('test.txt')
7
8# 矩形の表現方法を4点の座標値から (xmin, ymin, xmax, ymax) という形式に直す。
9xs, ys = data[:, ::2], data[:, 1::2]
10rects = np.c_[xs.min(axis=1), ys.min(axis=1), xs.max(axis=1), ys.max(axis=1)]
2. Find-Union
python
1class UnionFind:
2 def __init__(self, size):
3 self.parent = np.arange(size) # 各ノードのルートノード一覧
4 self.rank = np.full(size, 1) # 木の高さ一覧
5
6 def find(self, x):
7 if self.parent[x] == x:
8 return x
9 self.parent[x] = self.find(self.parent[x]) # ルートに繋ぎ直す。
10 return self.parent[x]
11
12 def union(self, x, y):
13 rx = self.find(x)
14 ry = self.find(y)
15 if rx == ry:
16 return # ルートが同じ場合
17 self.parent[rx] = self.parent[ry] # x のルートを y のルートに繋ぐ。
18
19 def are_same(self, x, y):
20 return self.find(x) == self.find(y)
3. 2つの矩形が近いかどうかを判断する関数
- 2つの矩形をそれぞれ少し大きくする。
- 大きくした矩形が共通部分をとるかどうか判断する。
2つの矩形が共通部分を持たないのは以下の場合なので、それ以外の場合は交わると判断する。
python
1def are_close(rect1, rect2, margin_x, margin_y):
2 # マージンだけ大きくした矩形を考え、それが共通部分を持つなら
3 # 2つの長方形は近いと判断する。
4 xmin1, ymin1, xmax1, ymax1 = \
5 rect1 + np.array([-margin_x, -margin_y, margin_x, margin_y])
6 xmin2, ymin2, xmax2, ymax2 = \
7 rect2 + np.array([-margin_x, -margin_y, margin_x, margin_y])
8
9 return not (xmin1 > xmax2 or xmax1 < xmin2 or
10 ymin1 > ymax2 or ymax1 < ymin2)
4. find-union で近い矩形同士をグループ分けする。
python
1# find-union アルゴリズムで近い矩形同士をグループ分けする。
2find_union = UnionFind(len(rects))
3for i, rect1 in enumerate(rects):
4 for j, rect2 in enumerate(rects):
5 if are_close(rect1, rect2, margin_x=15, margin_y=0):
6 # rect1 が rect2 に隣接するなら、rect1 は rect2 と同じグループと判断する。
7 find_union.union(i, j)
8 break
9
10classes = find_union.parent
11print(find_union.parent)
5. グループごとの外接矩形を求める。
python
1# 各クラスの外接矩形を求める。
2bounding_rects = []
3for label in np.unique(classes):
4 # 同じグループ内のすべての矩形を含む外接矩形を計算する。
5 xmin, ymin, xmax, ymax = np.split(rects[classes == label], 4, axis=-1)
6 bounding_rect = [xmin.min(), ymin.min(), xmax.max(), ymax.max()]
7 bounding_rects.append(bounding_rect)
6. 結果を描画する。
python
1# 描画する。
2fig, ax = plt.subplots(figsize=(8, 8))
3ax.set_xlim(xs.min() - 20, xs.max() + 20)
4ax.set_ylim(ys.min() - 20, ys.max() + 20)
5# 元の矩形を描画する。
6colors = np.random.rand(len(classes), 3)
7for (xmin, ymin, xmax, ymax), class_, color in zip(rects, classes, colors):
8 w, h = xmax - xmin, ymax - ymin
9 ax.add_patch(Rectangle(xy=(xmin, ymin), width=w, height=h,
10 color=colors[class_], fill=False, lw=2))
11# 外接する矩形を描画する。
12for xmin, ymin, xmax, ymax in bounding_rects:
13 w, h = xmax - xmin, ymax - ymin
14 ax.add_patch(Rectangle(xy=(xmin, ymin), width=w,
15 height=h, lw=2, alpha=0.5, fill=False))
16
17plt.show()
結果
右側の細長い矩形が他のと同じグループになっているのは、矩形同士が隣接しているかどうかを見ているからです。
望むグループ分けができるように、同じグループと判断する条件を増やしたりして、調整してみてください。(are_close()
関数の中身)
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/12/10 06:40
2018/12/10 06:42
2018/12/10 07:31
2018/12/10 07:49
2018/12/10 09:49
2018/12/10 09:51
2018/12/10 09:55