Pythonで数独認識して解く① (矩形抽出)

##初めに

• 数独を認識して解くプログラムを作る
• 入力画像から9×9マスの数独を抽出します。

[環境]
・Python 3.7.3
・numpy 1.16.4
・opencv-python 4.2.0.34
・matplotlib 3.1.2

##方法
①入力画像をcv2.imread
②グレースケール
③大津の二値化
④cv2.findContoursで矩形抽出(引数についての解説は後程)
⑤抽出した矩形を整理
⑥最も正方形に近い矩形を出力

なんかシンプル過ぎるアルゴリズムだが，ほとんどの場合でうまくいった。
④のcv2.findContoursが優秀過ぎた。

##cv2.findContoursについて

• 日本語の解説ページ を見れば使い方はわかる。

• ただし，今のバージョンのOpenCVは戻り値が1つらしい。

• contours = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)

• 第一引数は入力画像。精度を高めるために二値化やCannyのEdge検出を行うとよい。

• 第二引数はcontour retrieval mode。これは輪郭の階層情報をどうするか決定する。

• 第三引数は輪郭の近似方法を決定する。境界上すべての点情報を保存するor四隅のみとするか。

• 戻り値のcontoursを座標に展開するには

for i in range(len(contours)):
    ret = cv2.boundingRect(contours[i])
"""
ret[0] -> 矩形の左上の点のx座標
ret[1] -> 矩形の左上の点のy座標
ret[2] -> 矩形の幅
ret[3] -> 矩形の高さ
"""

##Source Code

sudoku_detection.py

import cv2
import numpy as np

#画像へのpath
img_path = "sudoku/sudoku001.jpg"
img = cv2.imread(img_path)

"""
矩形抽出
"""
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
H,W = gray.shape

#一定面積以下の矩形を除外するため
min_H = H*0.2
min_W = W*0.2

#大津の二値化
img_otsu_th = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY_INV+cv2.THRESH_OTSU)[1]

#外接矩形を抽出
contours = cv2.findContours(img_otsu_th, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)[0]

x_min = np.empty(0,dtype=np.int) #x座標の最小値
y_min = np.empty(0,dtype=np.int) #y座標の最小値
x_max = np.empty(0,dtype=np.int) #x座標の最大値
y_max = np.empty(0,dtype=np.int) #y座標の最大値
ratio = np.empty(0) #縦横の比率(w/h)

for i in range(1, len(contours)):# i = 1 は画像全体の外枠になるのでカウントに入れない
    ret = cv2.boundingRect(contours[i]) #x,y,w,hに展開
    if ret[2]>min_W and ret[3]>min_H:
        x_min = np.append(x_min,ret[0])
        y_min = np.append(y_min,ret[1])
        x_max = np.append(x_max,ret[0]+ret[2])
        y_max = np.append(y_max,ret[1]+ret[3])
        ratio = np.append(ratio,ret[2]/ret[3])

#最も正方形に近いものを選択する
ratio = np.abs(ratio-1)
xmin_use = x_min[np.argmin(ratio)]
ymin_use = y_min[np.argmin(ratio)]
xmax_use = x_max[np.argmin(ratio)]
ymax_use = y_max[np.argmin(ratio)]

#該当箇所を矩形表示
out = img.copy()
cv2.rectangle(out, (xmin_use, ymin_use), (xmax_use, ymax_use), (0, 255, 0), 3)

#元画像から切り抜く
crop_img = img_otsu_th[ymin_use:ymax_use, xmin_use:xmax_use]
crop_img = cv2.bitwise_not(crop_img)

cv2.imwrite("sudoku_result/{}".format(img_path[7:]),crop_img)

print("Crop Done!")

##実験
入力

結果

##各マスに分割

#切り抜いた画像のH,W
H,W = crop_img.shape

#縦横分割数
N = 9
cut_H,cut_W = H//N,W//N

#分割した画像N*N枚が格納される
cut_img = np.zeros((N*N,cut_H,cut_W),dtype=np.int)
cut_img[0] = crop_img[:cut_H,:cut_W]

for y in range(N):
    for x in range(N):
        cut_img[x+y*N] = crop_img[cut_H*y:cut_H*(y+1),cut_W*x:cut_W*(x+1)]

#分割した画像に含まれる枠線を消す
sise_param = 0.09

#サイズ決定
H_min,H_max = int(cut_H*sise_param),int(cut_H*(1-sise_param))
W_min,W_max = int(cut_W*sise_param),int(cut_W*(1-sise_param))
out_img = np.zeros((N*N,H_max-H_min,W_max-W_min),dtype=np.int)

#kernelの用意
kernel = np.ones((3,3),np.uint8)

#トリミング
for i in range(N*N):
    out_img[i] = cut_img[i,H_min:H_max,W_min:W_max]

#保存
for y in range(N):
    for x in range(N):
        cv2.imwrite("split_sudoku/{}.jpg".format(x+y*N),out_img[x+y*N].astype(np.uint8))
print("Split Done!")

結果

##まとめ

• OpenCVを使って矩形抽出を行った。
• もう少し制約を強くすれば危なげないアルゴリズムになったとは思うけど案外うまくいった。
• 次は分割した画像に対して文字認識を行う。