はじめに
今年オセロAdvent Calendarなるものが企画されて誘っていただいたので、記事を書いてみることにしました。実は1日目にも別記事を書いているのですが、勝手がわかっておらず唐突に記事に入ってしまったため、今回はちょっとだけ自己紹介です。
私は棋譜BoxというiOS用のアプリを開発しています。その機能の1つとしてオセロ盤をカメラで写して、盤上に評価値をARで重畳表示するという機能を組み込みました。次の画像をクリックすると紹介動画が出ます。
また、盤を撮影して(または撮影した写真を選択して)盤面の石の配置を認識するという機能もあります。これも紹介動画があります。
今回の記事では、これらの機能でどのようにオセロ盤の盤面を認識しているかについて説明したいと思います。以下の左側の画像を入力したときに、右側の画像のように黒石・白石の位置と、空きマスの状況を認識するのが目標です。
前提環境
- Python3.7.1
- OpenCV 4.1.0
実際のアプリではiOSなのでObjective C + OpenCVで実装したのですが、本記事ではPython版で説明します。実行している内容自体はアプリ版とほぼ同等です。
なお、Python版のソースコード全体は以下においてありますのでご参照ください。
https://github.com/lavox/reversi_recognition
方針
画像の認識をするに当たって、大きく以下の2つのアプローチがあります。
- 機械学習を使用する方法
- 自力でアルゴリズムを作成する方法
前者については学習用の教師画像を大量に集めるのが難しそうなことと、うまくいかなかった時のチューニングが難しそうだったので、後者の方法を採用することにしました。
以下のステップで画像認識を行います。
- 盤の範囲を特定する
- 正方形に変換する
- 石の位置を特定する
- 石の色を判定する
カメラで写真を撮って盤面を取り込む機能では1を行なった後に範囲の確認画面を表示してから2〜4を行なっていますが、AR機能では1〜4を一気に実行しています。
準備
import cv2
image = cv2.imread("./sample.jpg")
image = cv2.blur(image,(3,3))
画像を読み込み、3×3のサイズで平滑化(ぼかし)を行っています。画像解析をする際は予め平滑化するのが定説のようなのでそうしておきました。
なお、Pythonの場合は読み込んだ画像は、各ピクセルごとに3要素のNumPyの配列になりますが、3要素の順序はRGBではなくBGRになるので注意してください。matplotlib等を使って表示する際は、形式(色の順序)を変更しないと色合いがおかしくなります。
rgbImage = cv2.cvtColor(image, cv2.COLOR_BGR2RGB)
Step1. 盤面の範囲の特定
オセロ盤の盤面は緑色なので、緑色の領域を抽出する方向で進めることにしました。BGR形式だと色の範囲が抽出しにくいので、HSV形式に変換します。
hsv = cv2.cvtColor(image, cv2.COLOR_BGR2HSV)
HSV形式になったので、Hで色の領域を範囲指定し、SとVは値がある一定以上の領域を緑とみなすことにしました。
本当は曲線的にしたかったのですが、処理が面倒になるので2つの領域の右上側を合わせた領域を「緑」とします。境界の値は実際に画像を見ながら試行錯誤的に決めました。
lower = np.array([45,89,30])
upper = np.array([90,255,255])
green1 = cv2.inRange(hsv,lower,upper)
lower = np.array([45,64,89])
upper = np.array([90,255,255])
green2 = cv2.inRange(hsv,lower,upper)
green = cv2.bitwise_or(green1,green2)
OpenCVではinRangeで範囲を指定することができます。bitwise_orは文字通り領域同士のORになります。
緑色の領域が抽出できました。ここから盤の四隅の頂点の座標を求めたいのですが、この二値化された画像からどうやって求めるのか、という話になります。盤が複数写っているのも気になるところです。いろいろ探してみたところ、輪郭を検出するfindContoursという関数を見つけたので使ってみます。
※この関数はV3時代は3つ戻り値を返していましたが、V4から2つになったようなので注意してください。
contours, hierarchy = cv2.findContours(green, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
これを実行してみた結果、何と2000個以上の輪郭が抽出されてしまいました。何が起きたのでしょうか？大きめの輪郭をいくつか描画してみました。
マス目の黒い線や石で区切られていました。もっと細かい輪郭を見ると、1ピクセルの画素だけで輪郭となっていたりしていて、このfindContoursというのはかなりシビアに輪郭を判定しているということがわかりました。こういった黒い線などの障害物を除去するテクニックをネットで検索してみたところ、モルフォロジー変換というのを見つけました。領域を一度膨張(dilate)して大きくした後、収縮(erode)することで、細かい線やゴミを消せるというやり方です。
ではどれくらい膨張・収縮すれば良いでしょうか？画像いっぱいに盤が写っているケースで試算してみたところ、線の太さは長辺の0.6〜0.7%くらいのようだったので、これを両サイドから膨張して消すために長辺の0.35%にすることにしました。
kernelSize = max(1, int(0.0035 * max(width, height))) * 2 + 1
kernel = np.ones((kernelSize, kernelSize), dtype=np.int)
green = cv2.dilate(green, kernel) # 膨張
green = cv2.erode(green, kernel) # 収縮
若干意味のよくわからない*2+1というのがありますが、膨張収縮のサイズは奇数でないといけないようなので、奇数にするための補正です。
線を消すことに成功しました。ただ、石が増えてきたときに石で分断されそうでちょっと危うい感じです。仕方がないので、思い切って緑だけでなく白い部分も盤の一部だとみなすことにしました。（黒い部分はさすがに盤の枠が黒なので広がりすぎるためやめました）
lower = np.array([0, 0, 128])
upper = np.array(([180, 50, 255])
white = cv2.inRange(hsv, lower, upper)
greenWhite = cv2.bitwise_or(green, white)
テーブルも白いのでちょっと気にはなりますが、分断リスクはだいぶ下がりましたし、盤の範囲もはっきりしているのでこれで進めることにしました。これで輪郭を再抽出してみます。
contours, hierarchy = cv2.findContours(greenWhite, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
辺のあたりにある石で凹みはありますが、分断はされなくなりました。あと何とかしたいのは、
- 凹みが何とかならないか
- たくさん輪郭が抽出された中で、注目している盤の輪郭をどうやって選択するか
といったところです。１つ目の凹みについて何とかならないか探してみたところ、凸包という方法がありました。
凸にできれば、抽出した輪郭の中で画像の中心点を含むもの（盤面を認識するのに撮影しているはずなので、中央に写っていることを仮定しました）、とすれば２つ目の課題であったどの輪郭を選択するかというのもクリアできそうです。
for i, c in enumerate(contours):
hull = cv2.convexHull(c) # 凸包
if cv2.pointPolygonTest(hull,(width / 2 , height / 2), False) > 0: # 中心を含むか判定
mask = np.zeros((height, width),dtype=np.uint8)
cv2.fillPoly(mask, pts=[hull], color=(255)) # 輪郭範囲内を塗りつぶした画像
break
一応これで盤の領域が得られました。ただ、先ほど分断対策のために白部分を加えてしまったため、余計な領域を巻き込んでいないか若干心配です。なので、この領域に入っている緑部分を抽出して、その輪郭を取って全部つなげるということをしてみました。
green = cv2.bitwise_and(green, green, mask=mask)
contours, hierarchy = cv2.findContours(green, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
greenContours = functools.reduce(lambda x, y: np.append(x, y,axis=0),contours)
hull = cv2.convexHull(greenContours)
これで無事輪郭が抽出できた、と思ったのですが、値を表示してみたところ何と26角形でした。
> print(hull.shape)
(26, 1, 2)
ほとんど直線に見えているところも実は間に頂点が入ってしまっているようです。このような状況の対策手段もOpenCVにはありました。approxPolyDPという多角形を近似する関数です。
epsilon = 0.004 * cv2.arcLength(hull, True)
approx = cv2.approxPolyDP(hull, epsilon, True)
試行錯誤の結果、周の長さの0.4%を誤差とすることで、大体の場合いい感じで四角形になるようです。
> print(approx)
[[[2723 2702]]
[[ 675 2669]]
[[1045 1639]]
[[2418 1613]]]
これで盤の４頂点を求めることができたのですが、ここに書ききれなかった細かい点について少し触れておきます。
- 隅に近いところに石があった場合や、隅付近が画像から見切れている場合に、隅が欠けて五角形や六角形になってしまうことがある
- このような場合も辺は合っているはずなので、抽出された多角形から長い順に4辺を選び、その交点を頂点とみなすことにしました。これはOpenCVというよりは数学の問題なので、興味のある方はソースコードの371行目～396行目あたりと、99行目～107行目あたりを見てください。
- 盤ではない領域を選択してしまうことがある
- これ自体は仕方ないことですが、明らかに元が正方形ではないものを選択していると判断した時は失敗とみなすようにしました。これも数学の問題なので、興味のある方はソースコードの438行目～485行目あたりと、125行目～197行目あたりを参照してください。この副産物として、盤とカメラの相対的な位置関係が求まりますが、後ほど使っています。
- 盤の向きの補正
- 画像の左上から順に時計回りになるように頂点を取り直しています
- 盤面が大きく見切れていないかのチェック
- オセロ盤の枠線は外周が若干太めのためその補正
- 画像サイズが大きすぎると処理に時間がかかるため、最初にリサイズ
Step2. 盤面部分を正方形に変換する
Step1で求めた盤を正方形に変換するのですが、後の処理の都合上、周囲にマージン（青枠）を持たせることにします。マージンの目的は以下の通りです。
- あとで石の色を調べるときに、チェック範囲が画像からはみ出さないようにする
- 盤の隅が見切れている画像の場合に、見切れた部分と同じ扱いにできるようにする
margin = 13 # マージンの幅
cell_size = 42 # 1マスのサイズ
size = cell_size * 8 + margin * 2 # 変換後の辺の長さ
outer = (254, 0, 0) # マージン部分の色
正方形への変換は実は簡単で、移動元と移動先の頂点がわかっていれば射影変換で一発です。
# 移動元の4頂点
src = np.array([[1045,1639], [2418,1613], [2723,2702], [ 675,2669]], dtype=np.float32)
# 移動先の4頂点
dst = np.array([
[margin, margin],
[size - 1 - margin, margin],
[size - 1 - margin, size - 1 - margin],
[margin, size - 1 - margin]
], dtype=np.float32)
# 変換行列
trans = cv2.getPerspectiveTransform(src, dst)
# 射影変換
board = cv2.warpPerspective(image, trans, (int(size), int(size)), flags=cv2.INTER_LINEAR, borderMode=cv2.BORDER_CONSTANT, borderValue=outer)
注意事項として、上記の射影変換のouterは、4頂点が画像からはみ出していた場合などに、はみ出していた部分を補うための色です。マージンを塗りつぶしているわけではありません。ということで、マージン部分も塗っておきます。
cv2.rectangle(board, (0, 0), (size - 1, margin), outer, -1)
cv2.rectangle(board, (0, 0), (margin, size - 1), outer, -1)
cv2.rectangle(board, (size - margin, 0), (size - 1, size - 1), outer, -1)
cv2.rectangle(board, (0, size - margin), (size - 1, size - 1), outer, -1)
これで盤を正方形にすることができました。
Step3. 石の位置の特定
石の位置を特定するにあたって、石はマスの中心にあることを仮定するかどうかという悩みがありました。実際の盤なので、中心からずれたところに石が置かれるケースもありますし、斜めから撮った画像だと正方形に変換した後の画像では石の厚みの関係で中心がずれるケースもありそうです。なので、石がマスの中心にあることは仮定せずに進めることにしました。
で、どうやって石の位置を特定するかですが、石は円形なので円を検出するハフ変換というものを使えば良いだろうと最初は思っていました。が、実際に試してみると人の目には見えない謎の円を大量検出し、パラメータも多いので調整は挫折しました。なお、ScoreNowというアプリでは、開発者の方に聞いたところハフ変換を使用して石を検出しているとのことでしたので、うまく調整すればできるのだと思います。
途方に暮れていろいろ検索していたところ、物体セグメンテーションアルゴリズム"watershed"を詳しくという記事にたどり着き、このやり方を試してみることにしました。今回の場合は石の輪郭を正確に求めるというよりは、石の中心を求めるということなので、リンク先の記事の一部のみを実行していることになります。
まず、盤と石を分別するため、Step1と同様に緑色の部分で盤の部分を抽出します。
hsv = cv2.cvtColor(board, cv2.COLOR_BGR2HSV)
lower = np.array([45,89,30])
upper = np.array([90,255,255])
green1 = cv2.inRange(hsv,lower,upper)
lower = np.array([45,64,89])
upper = np.array([90,255,255])
green2 = cv2.inRange(hsv,lower,upper)
green = cv2.bitwise_or(green1,green2)
マージンの青い部分も加えてから反転すると、石の部分が抽出できます。
outer = cv2.inRange(board, (254, 0, 0), (254, 0, 0))
green = cv2.bitwise_or(green, outer)
disc = cv2.bitwise_not(green)
マスの線が残っていますが、この後の処理には特に影響しないので、今回はこのままにしておきます。
また、実際には人の手とかが写り込んでいる可能性を考慮して、緑でも白でも黒でもない部分を「不明」なマスとして扱うような処理もありますが、長くなるので省略します。
さて、先ほどのQiitaの記事に従って、石の外から各点までの距離を求めます。
dist = cv2.distanceTransform(disc, cv2.DIST_L2, 5)
各島(?)の最大値の点が石の中心になりそうです。ただし、今は島が一部連結してしまっているので、ある程度の値以上の点を抽出して分離します。「ある程度の値」は大きすぎると認識できない石が発生してしまう可能性がある一方、小さすぎると連結を切り離せない可能性があり、試行錯誤の結果13.0を閾値としました。
_, distThr = cv2.threshold(dist, 13.0, 255.0, cv2.THRESH_BINARY)
この各連結領域の最大の点が石の中心のはずですので、それを求めます。
distThr = np.uint8(distThr) # 型変換が必要
# 連結成分を取得
labelnum, labelimg, data, center = cv2.connectedComponentsWithStats(distThr)
for i in range(1, labelnum): # i = 0 は背景なので除外
x, y, w, h, s = data[i]
distComponent = dist[y:y+h, x:x+w]
maxCoord = np.unravel_index(distComponent.argmax(), distComponent.shape) + np.array([y, x])
なお、うまく島が分離しきれておらず双峰的になってしまった場合のため、実際のソースでは最大値付近を消し込みながらループするというちょっと複雑なことをしていますが、ここでは単純化しています。
まずまずの精度で石の中心を求めることができました。
懸念として、斜めから撮った写真を無理やり正方形にしているので、石は円ではなくドラム缶的な形になっており、できれば石の色は天面の中心付近で、石の位置は底面の中心で判断したいところです。これを何とかするために、盤面抽出時に求めたカメラ位置を元に、石の中心をカメラから遠い方と近い方にずらして天面と底面の中心とみなすということをしていますが、長くなるので（既に十分長いですが・・・）今回は説明を省略します。
Step4. 石の色の判定
さていよいよ石の色の判定です。基本的には石の中心付近の色の明るさで判断すれば良さそうですが、実際にやってみるといくつか課題が出てきました。
- 中心点の精度が完全ではないので、判定する範囲を広げると隣の石や、石の側面の色を拾って誤検知の元になる
- 明るい環境にある黒石と、薄暗い環境にある白石は、HSVのV(明るさ)だけでは判断がつきにくい。
- 黒石が光の反射で白石っぽく見えることがある。これは本当の白石並みに白い。
2点目について、当初は周囲との明るさの比較で条件を作っていましたが、その後OpenCVを使ってもっと簡単に判定する方法を発見しました。それがadaptive thresholdという周囲の状況を踏まえて二値化する処理です。これを使うと、周りの明るさに影響されず白い石は白くなります。
grayBoard = cv2.cvtColor(board, cv2.COLOR_BGR2GRAY)
binBoardWide = cv2.adaptiveThreshold(grayBoard, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY, 127, -20)
グレースケール化した後、adaptive thresholdを実行しています。
これで白い石はかなり白くなりましたが、黒石でまだ白っぽいのがあるのでもう少し工夫しておきたいところです。完全に反射している石は判定が難しいですが、画像をよく見ていると多少反射しているくらいの黒石であれば少しは「色ムラ」があるということがわかってきました。adaptive thresholdの処理で「周囲」とみなす範囲を狭くするとこの色ムラが拾えることがわかりました。blockというのが「周囲」とみなす範囲です。
binBoardWide = cv2.adaptiveThreshold(grayBoard, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY, 127, -20)
binBoardNarrow = cv2.adaptiveThreshold(grayBoard, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY, 7, 2)
# 試行錯誤の結果、ぼかしを入れた後、閾値で二値化した
binBoardNarrow = cv2.blur(binBoardNarrow, (3, 3))
_, binBoardNarrow = cv2.threshold(binBoardNarrow, 168, 255, cv2.THRESH_BINARY)
block=127と広めだと、そこそこ広い範囲が白くなってしまうのに対して、block=7のように狭めに取ると、色ムラが浮き出てきます。しかも白石は白いままというのが良いところです。
そこでStep3で求めた石の中心点(天面)から半径10の領域内に、黒いピクセルがいくつあるかで以下のように石の色を決めることにしました。
- 「広め」で10以上 or 「狭め」で26以上 → 黒石
- それ以外 → 白石
この閾値も、実際の画像から黒いピクセル数を黒石と白石でプロットしてみて、その分布の傾向から決めました。
完成！ ...精度は？
これでオセロの盤面を認識できるようになりましたが、精度はどの程度のものでしょうか？手元にあった76枚の画像を認識してみたところ、以下のような結果でした。
- 67枚：全石を正しく判定
- 1枚：盤の範囲検知に失敗(盤が中央に写っていなかった)
- 8枚：計14個の石で色の誤判定
ただ、認識ロジックを開発する際の試行錯誤に使用した画像も多数含まれているため、実際的な精度としてはもう少し低いものと思います。
うまく認識できなかったケースをいくつか挙げておきます。
a5を空きマス、h3を白石と判定してしまいましたが、正解は両方とも黒石です。ピンボケ気味の写真の場合はうまく認識できないようです。
e3の石を黒判定してしまいましたが、正解は見た通り白石です。盤の材質によっては盤自体が反射するケースがありますが、盤を緑色で判断しているせいか盤の反射に弱いようです。
e7,e8,f8の石を白石と判定してしまいましたが、これらは全て反射した黒石が正解です。反射が強烈なので人の目でも判断に迷うところですが、今回のアルゴリズムでは正しく判定できませんでした。
また認識の性能としては、長辺を1024pxにリサイズしてから認識することでそこそこの性能が出ていて、iPhone8で実行している限りでは秒間数回程度の認識ができるようです。
今回説明できなかった話
実際のオセロ盤を認識する話は以上ですが、アプリでオセロの盤面を認識する機能を実装すると、
- 他のアプリの盤面のスクリーンショットを認識する機能も欲しくなる
- 白黒印刷の書籍の盤面を認識する機能を欲しくなる
ということになります。スクリーンショットについてはある程度は実際の盤と同じアルゴリズムでいけるのですが、固有の考慮をしないとうまく認識できないケースがありました。
白黒印刷の書籍に至っては、緑色で盤面を判定する作戦が根本的に使えないので、そこから見直さないと使い物になりません。
これらについてはまた別の方法で実装しているのですが、いい加減記事が長くなってきていますので、ここまでにしておきます。ソースコードにはスクリーンショットや書籍も含めて実装していますので、興味のある方はそちらをご覧ください。