画像処理で図形画像をグリッドに落とし込む

はじめに

就活の適性検査で、こんな問題が出ました。
「1つの図形を2つの合同な図形に分割できるものを選びなさい」

これを見て、プログラムを作れば一瞬で解けるんじゃないか？と思ったのが、今回の動機です。

プログラムで扱うには、まずは図形をマス目（グリッド）で表現しないといけないです。選択肢の図形は5つあり、適性検査の限られた時間で図形を手入力でグリッドに変換したくないです。

そこで、画像処理で図形をグリッドに変換するプログラムを作りました。最終的には「マスのあるところが1、ないところが0」の2次元配列に変換されます。
例えば、この画像が

こうなります。

[[0 1 1 0]
 [1 1 1 0]
 [0 0 1 1]
 [0 0 0 1]]

この記事では、このグリッド変換プログラムの実装と仕組みを解説します。

実装

使用ライブラリ

OpenCVを使って画像処理を行います。

pip install opencv-python

全体のコード

以下がグリッド変換プログラムの全体です。

import cv2
import numpy as np

def preprocess_image(image, binary_thresh=120):
    gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
    _, binary_inv = cv2.threshold(gray, binary_thresh, 255, cv2.THRESH_BINARY_INV)
    return binary_inv


def extract_rectangles(binary_inv):
    """画像から外枠と内枠の四角形を抽出"""
    contours, _ = cv2.findContours(binary_inv, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
    outer_contour = contours[0]
    outer_box = cv2.boundingRect(outer_contour)

    inner_rectangles = []
    for inner_contour in contours[1:]:
        rect = cv2.boundingRect(inner_contour)
        inner_rectangles.append(rect)

    return outer_box, inner_rectangles

def estimate_grid_size(outer_box, inner_rectangles):
    """マスの中央値から行数と列数を推定"""
    widths = [w for _, _, w, _ in inner_rectangles]
    heights = [h for _, _, _, h in inner_rectangles]
    median_width = int(np.median(widths))
    median_height = int(np.median(heights))

    _, _, w, h = outer_box
    num_cols = round(w / median_width)
    num_rows = round(h / median_height)

    return num_rows, num_cols


def compute_cell_centers(outer_box, num_rows, num_cols):
    """グリッドの各セルの中心点を計算"""
    x, y, w, h = outer_box
    cell_width = w / num_cols
    cell_height = h / num_rows

    centers = []
    for i in range(num_rows):
        for j in range(num_cols):
            cx = int(x + (j + 0.5) * cell_width)
            cy = int(y + (i + 0.5) * cell_height)
            centers.append((cx, cy))

    return centers


def is_point_in_rectangle(point, rect):
    x, y, w, h = rect
    return x <= point[0] <= x + w and y <= point[1] <= y + h
    

def convert_image_to_grid(image, binary_thresh=120):
    binary_inv = preprocess_image(image, binary_thresh)
    outer_box, inner_rectangles = extract_rectangles(binary_inv)
    num_rows, num_cols = estimate_grid_size(outer_box, inner_rectangles)

    grid = np.zeros((num_rows, num_cols), dtype=int)

    # セルの中心点がマス(内側の四角形)に含まれていたら1をセット
    centers = compute_cell_centers(outer_box, num_rows, num_cols)
    for i, center in enumerate(centers):
        for rect in inner_rectangles:
            if is_point_in_rectangle(center, rect):
                row = i // num_cols
                col = i % num_cols
                grid[row, col] = 1
                break

    return grid

実際に使ってみる

この画像(shape.png)をグリッドに変換してみます。

import cv2
import matplotlib.pyplot as plt

# 画像を読み込む
image = cv2.imread('shape.png')
# 画像をグリッドに変換
grid = convert_image_to_grid(image, binary_thresh=120)
print(grid)

# グリッドを画像で表示
plt.imshow(grid, cmap='gray')
plt.axis('off')
plt.show()

出力例

[[0 1 1 0]
 [1 1 1 0]
 [0 0 1 1]
 [0 0 0 1]]

図形がきちんとグリッドで表現されているのがわかります。

解説

ここからは、それぞれの関数が何をしているか説明していきます。

画像の前処理

画像を二値化します。binary_threshはしきい値で、これを調整して黒い線だけ残るようにします。

def preprocess_image(image, binary_thresh=120):
    gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
    _, binary_inv = cv2.threshold(gray, binary_thresh, 255, cv2.THRESH_BINARY_INV)
    return binary_inv

出力のbinary_invを可視化するとこうなります。

画像の明るさは、黒が0、白が255です。しきい値より小さい部分（暗い部分）を白として残します。つまり、黒い線だけを白として残し、それ以外は黒にするという変換です。

binary_threshを小さくすると、本当に黒い線だけが残りますが、線が薄いところは消えてしまうかもしれません。
逆に、binary_threshを大きくすると、線がより確実に残りますが、ノイズが大きくなります。

外枠と内枠の四角形を抽出

二値化された画像から、外枠と内枠のマス（小さな四角形）を検出します。輪郭を抽出して、それぞれの輪郭を囲む四角形を求めています。

def extract_rectangles(binary_inv):
    """画像から外枠と内枠の四角形を抽出"""
    contours, _ = cv2.findContours(binary_inv, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
    outer_contour = contours[0]
    outer_box = cv2.boundingRect(outer_contour)

    inner_rectangles = []
    for inner_contour in contours[1:]:
        rect = cv2.boundingRect(inner_contour)
        inner_rectangles.append(rect)

    return outer_box, inner_rectangles

抽出結果はを可視化しました。左が外枠、右が内枠の四角形です。

グリッドの大きさを求める

グリッドの大きさ、つまり行数と列数を求めます。

まず行数を求めるには、「外枠の四角形の高さ」に対して「1マスの高さ」が何個入るかを考えればいいので、「外枠の高さ ÷ 1マスの高さ」で求められます。列数も同様です。

ただし、マスの大きさには多少のばらつきがあるため、個々のマスの幅や高さを使うと誤差が出やすくなります。そこで、異常値の影響を抑えるために、中央値を使っています。

def estimate_grid_size(outer_box, inner_rectangles):
    """マスの中央値から行数と列数を推定"""
    widths = [w for _, _, w, _ in inner_rectangles]
    heights = [h for _, _, _, h in inner_rectangles]
    median_width = int(np.median(widths))
    median_height = int(np.median(heights))

    _, _, w, h = outer_box
    num_cols = round(w / median_width)
    num_rows = round(h / median_height)

    return num_rows, num_cols

グリッドを作成

行数と列数を求めたので、グリッドは作成できます。後はマスのあるところを1にすればいいです。

grid = np.zeros((num_rows, num_cols), dtype=int)

外枠を行数×列数のグリッドに等分し、それぞれのマスの中心点を求めます。

def compute_cell_centers(outer_box, num_rows, num_cols):
    """グリッドの各セルの中心点を計算"""
    x, y, w, h = outer_box
    cell_width = w / num_cols
    cell_height = h / num_rows

    centers = []
    for i in range(num_rows):
        for j in range(num_cols):
            cx = int(x + (j + 0.5) * cell_width)
            cy = int(y + (i + 0.5) * cell_height)
            centers.append((cx, cy))

    return centers

中心点の可視化です。

その後、中心点がマスのどれかに含まれていれば、中心点に対応するセルを1にします。

centers = compute_cell_centers(outer_box, num_rows, num_cols)
    for i, center in enumerate(centers):
        for rect in inner_rectangles:
            if is_point_in_rectangle(center, rect):
                row = i // num_cols
                col = i % num_cols
                grid[row, col] = 1
                break

これで画像の図形をグリッドに変換できます。

おわりに

適性検査の「ひとつの図形を2つの合同な図形に分割できるものを選べ」という問題を解くためにこのプログラムを書きました。なので、次は図形を2つの合同な図形に分割できるか判定しようとしましたが、プログラムを作成している途中でその必要がないことに気づきました。

実はこの問題、選択肢の図形のうちマスの数が偶数のものがひとつしかないです。奇数だと2つの合同な図形に分けられないので、消去法でそのひとつの図形が正解になります。

つまり、マスの数を数えるだけでいいです。このようにグリッドの1の数を数えるとマスの数が求まります。

import numpy as np

total_ones = np.sum(grid)
print(f"マスの数: {total_ones}")