V字のような図形を三分割する方法について

こちらで解決済みにした質問に関する追加の質問です。
https://teratail.com/questions/176153
上のURLでの質問ではVの字の三分割ということで質問をしたのですが以下のようなV字のように配置されたランダムな図形の集まり(以下V図形と呼びます)に関して質問させてください。
以下のような入力画像を三分割にする方法はありますでしょうか？
【条件】(説明しづらいので伝わらなかったら追記での質問をお願いします。)
・入力画像はオレンジと白の2色だけで構成されます。
・出力画像の長方形はそれぞれV図形の白い部分を囲む最小の大きさの長方形です。
・V図形の輪郭のうちy座標が最も小さい二点(黒い点)をつないだ直線(緑線)と図形の輪郭内側(黒い部分)をくぼみ図形と呼びます。

・青い点はくぼみ図形の中で一番y座標が最も大きい点として定義します。
※y座標が最も大きい点が複数ある場合は複数の点の真ん中のx座標を持つV図形の輪郭上の点とします。
・3の長方形は画像の青い点を通ります。(1,2は通らなくてもよい。)

入力画像

出力画像(目視で書いたものなので実際この画像になる必要はありません。条件を満たした四角形の枠の表示をしたいです。)

tiitoi

2019/02/25 10:34

この形状が輪郭で表されている (点 (x, y) のリスト) としたとき、「くぼみの部分の先」とはどのように定義されるものなのでしょうか？「くぼみの部分」というものを具体的に定義できないとプログラムはかけないです。

退会済みユーザー

2019/02/25 11:22

毎回お世話になっております。具体的な点に関して修正いたしました。

行動規範の内容に同意します

回答2件

ベストアンサー

くぼみの点を求めるというところが一番むずかしい部分かと思います。
今回はまず局所的な凹凸は無視するため、輪郭を大雑把に近似してから、凸包と比べることでくぼみの点を見つけました。

この部分は凸集合の解析方法等でもう少し賢いやり方がありそうな気がしますが、思いつきませんでした。
以下サンプルコードです。

サンプルコード

python
1import cv2
2import numpy as np
3from IPython.display import Image, display
4
5
6def imshow(img):
7    ret, img = cv2.imencode('.png', img)
8    display(Image(img))

1 . 画像読み込み
2 . BGR -> グレースケール
3 . 2値化

# 画像読み込み
img = cv2.imread('test.png')
assert img is not None, 'Failed to load image'
# bgr -> grayscale
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
# 2値化
ret, binary = cv2.threshold(gray, 200, 255, cv2.THRESH_BINARY)

4 . 輪郭を求める
5 . 輪郭を近似する。
6 . 凸包を求める。

python
1def get_contour(binary):
2    # 輪郭抽出
3    contours = cv2.findContours(
4        binary, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)[0]
5    cnt = contours[0]  # 1つだけ見つかる前提
6    cnt = cnt.squeeze(axis=1)  # (N, 1, 2) -> (N, 2)
7    return cnt
8
9# 輪郭を求める。
10cnt = get_contour(binary)
11# 近似
12arclen = cv2.arcLength(cnt, closed=True)
13approx = cv2.approxPolyDP(cnt, epsilon=0.03 * arclen,
14                          closed=True).squeeze(axis=1)
15# 凸包を求める。
16hull = cv2.convexHull(approx).squeeze(axis=1)
17
18
19# 「近似した輪郭の点一覧 - 凸包を構成する点一覧」の差が凹み部分の点 (集合演算)
20diff_points = set(map(tuple, approx)) - set(map(tuple, hull))
21cx, cy = list(diff_points)[0]

輪郭

近似

凸包

python
1# 対象領域以外をマスクする。
2block1 = np.zeros_like(binary)
3block1[:cy, :cx] = binary[:cy, :cx]
4
5block2 = np.zeros_like(binary)
6block2[:cy, cx:] = binary[:cy, cx:]
7
8block3 = np.zeros_like(binary)
9block3[cy:] = binary[cy:]
10
11def get_bounding_rect(binary):
12    cnt = get_contour(binary)
13    x, y, w, h = cv2.boundingRect(cnt)
14    return (x, y), (x + w, y + h)
15
16# 各領域を輪郭抽出し、外接矩形を取得する。
17rect1 = get_bounding_rect(block1)
18rect2 = get_bounding_rect(block2)
19rect3 = get_bounding_rect(block3)

block1

block2

block3

結果を描画

python
1cv2.rectangle(img, rect1[0], rect1[1], color=(255, 255, 0), thickness=2)
2cv2.rectangle(img, rect2[0], rect2[1], color=(0, 255, 255), thickness=2)
3cv2.rectangle(img, rect3[0], rect3[1], color=(255, 0, 255), thickness=2)
4imshow(img)