質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

1回答

4819閲覧

python3 隣接する矩形の座標データをX方向でまとめる考え方

ebifry

総合スコア14

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2018/12/10 06:17

編集2018/12/10 07:45

お世話になります。

図のような画像の矩形座標が入ったリストがあるとします。
赤線がリストの座標で描かれた矩形です。
隣接した矩形を青い矩形のようにまとめて、その座標を得たいのですが・・・・。
考えるほど、何がなんだかわからなくなってきました。

ついては、こうした方が良いなどの考え方をご教示いただきたくご質問する次第です。
リストには、[[60, 450, 60, 408, 93, 408, 93, 450], .....]のように
左上から時計回りに[x1,y1,x2,y2,x3,y3,x4,y4]の座標が格納されています。
x:0,y:0は、左上から開始するとします。
矩形図

試してみたこと
1.リストから矩形の中心座標(x,y)を算出してnumpy配列とし、np.whereで左翼にある矩形の高さ内の要素を探して結合する。
この場合、左翼の矩形が小さいと、上手く全体を内包する矩形が描けない。

2.Python3 隣接する特徴量座標の中心点を求めたいを参考にしたが、そもそもこの考え方でX方向のみまとめることができるのか?わからなくなってきた。

といった状態です。
こうした方が良い、全然見当違いだよ等々、ご指導いただければ幸いです。

よろしくお願いいたします。

追記いたします。
ありがとうございます。ご回答いただいた図に書き込みますと、
図1
イメージ説明
隣接する矩形をひとまとめにする。その規準については、まだ定義できておりません。

図2
!イメージ説明

最低でも図2のようにまとめたいと考えておりました。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

以下のような感じでしょうか?

  1. y 座標を見て、各矩形をクラスタリングする。
  2. 同じクラスの矩形は外接する矩形に置き換える。

追記

コメント欄の矩形をプロットしたら以下のようになったのですが、グループ分けする基準はなんでしょうか?

イメージ説明

追記

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つの矩形が近いかどうかを判断する関数

  1. 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:27

編集2018/12/10 09:58
tiitoi

総合スコア21954

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

ebifry

2018/12/10 06:40

早速のご回答ありがとうございます。 実際のデータは以下のような感じです。 これでよろしいでしょうか? ありがとうございます。 [[585 446 585 200 605 200 605 446] [398 398 398 356 453 356 453 398] [ 60 450 60 408 93 408 93 450] [ 96 446 96 413 130 413 130 446] [147 446 131 446 131 413 147 413] [406 450 406 417 468 417 468 450] [606 730 586 730 586 447 606 447] [536 501 536 451 558 451 558 501] [ 60 497 60 459 91 459 91 497] [ 95 497 95 464 146 464 146 497] [408 497 408 464 468 464 468 497] [ 8 539 8 515 38 515 38 539] [ 65 531 39 525 42 512 68 518] [108 553 105 516 130 514 132 551] [157 552 157 515 252 515 252 552] [284 552 284 519 340 519 340 552] [343 556 343 519 369 519 369 556] [401 556 373 556 373 519 401 519] [423 551 423 518 487 518 487 551] [502 552 502 519 541 519 541 552] [547 552 547 519 579 519 579 552] [ 68 552 41 552 41 532 68 532] [ 99 552 73 552 73 532 99 532] [255 626 190 620 194 581 258 587] [ 34 620 6 620 6 587 34 587] [ 37 624 37 587 68 587 68 624] [286 620 259 620 259 587 286 587] [347 620 347 587 363 587 363 620] [366 620 366 587 386 587 386 620] [189 616 169 616 169 591 189 591] [389 616 389 591 403 591 403 616] [509 620 509 595 535 595 535 620] [569 624 544 624 544 595 569 595]]
ebifry

2018/12/10 06:42

すいません。 左上から時計回りに[x1,y1,x2,y2,x3,y3,x4,y4]になってないですね・・・・。 左下からから時計回り?のようです。
tiitoi

2018/12/10 07:31

データをプロットしたら回答欄に追記した画像のようになったのですが、どのような基準でグループ分けしたいのでしょうか?
ebifry

2018/12/10 07:49

失礼いたしました。そうですね。 この例ですと、追記いたしました図1のように隣接する矩形、そのどこまでを隣接する矩形とするかについては、明確な定義を現在もっておらず、試行錯誤しておった段階です。 隣接の定義が困難な場合は、図2のような感じで考えておりました。この場合は、中心点のよりある一定の幅内にある矩形中心の最大高で、内包する矩形を作成しようと考えておりました。
tiitoi

2018/12/10 09:49

x 軸方向に近い矩形同士を同じグループにする方針でグループ分けをしてみました。 グループ分けを行う条件が明確になっていないようなので、そこらへんをもう少し吟味してみるとよいかと思います。
ebifry

2018/12/10 09:51

素晴らしい!!!ご回答ありがとうございました。 ご多用のなか、丁寧に回答いただいて感激です。 今の自分には、ちょっと理解が追いつかない部分もありますので、しっかり拝見して精進いたします。 本当にありがとうございました。
tiitoi

2018/12/10 09:55

あまりコメントつけてなかったので、コード中で不明な点があれば、補足します。 方針としては、これでよいと思うのであとはグループ分けする基準ですね。 Find-Union は Web 上に資料が沢山あると思うのでそちらを参照してみてください。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問