将棋盤を画像認識する

Analytics チームで転職会議のレコメンドを開発している @na_o_ys です。今回は業務のことは忘れて、趣味の将棋の話をしたいと思います。

この数年で将棋の学習環境はずいぶんリッチになりました。通勤電車では将棋アプリのネット対局をして、自宅ではオープンソースの強豪 AI を使って棋譜検討し、日々将棋を楽しんでいます。
一方で、顔を突き合わせて盤と駒を使って指す対局が一番楽しいのは変わりがありません。 リアルの対局を AI で検討するために、盤面を手軽にコンピュータに入力したい というのが今回のテーマの発端です。

TL;DR

盤上の駒を高い精度で推定することができました。

処理は大きく 2 つのステップからなります。

1. 盤面の正規化
   • 盤面の四隅の座標を特定し、元画像から正規化画像への射影変換を得る
2. マス目毎の内容を推定する
   • マス目毎に画像を切り出し、駒の有無・種類を推定する

ちなみに上記画像は私と同僚の将棋で、現局面は後手番です。後手玉は詰めろ飛車取りですが次の一手を考えてみてください。

ステップ 1. 盤面の正規化

正規化画像への射影変換を得るには、盤面の四隅の座標を特定できれば十分です。画像処理の要素技術としてエッヂ検出、輪郭検出、線分検出など多様な特徴抽出手法があります。今回は、 輪郭検出 + 線分検出 + 焼きなまし法 を組み合わせることで、高い精度で四隅の座標を特定することができました。

輪郭検出

将棋盤の大まかな位置を特定するために 輪郭検出 を利用します。

大まかな位置は特定できますが、マス目とぴったり一致しません。輪郭検出では罫線だけでなく将棋盤の端や机の角も検出してしまうためです。ここで特定した大まかな座標を出発点として、次に紹介する焼きなまし法でイテラティブに精度を高めていきます。

なお輪郭検出の結果は多角形ではなく曲線のため、直接四隅の座標は得られません。四角形の頂点座標を得るために以下の処理を行っています。

1. 輪郭検出
2. 凸包で近似
3. 凸包の頂点から四隅の座標候補 (最も正方形に近いもの) を選択

線分検出 + 焼きなまし法

焼きなまし法 はパラメータ (ここでは四隅の座標) を振動させながら、目的関数が最小となる値を探索する手法です。

以下の要件を満たす目的関数を設計する必要があります。

目的関数 f:
    f(四隅の座標候補) = 真の座標にどれだけ近いか

まず 線分検出 により将棋盤の罫線を大雑把に抽出します。これを 罫線画像 と呼ぶことにします。

目的関数の中で、与えられた四隅の座標をもとに マスク画像 を生成します。マスク画像は四隅の座標から仮定される罫線の位置に近ければ近いほど明るく、罫線から遠いと暗くなるようにします。

このマスク画像を罫線画像に重ねると、罫線の重なり具合が大きければ多くの罫線が透過されるのに対して、重なり具合が小さければ一部しか透過されないことが想像できます。 すなわち マスク画像と罫線画像の内積 が目的関数として利用できるということです。

この目的関数を利用して焼きなまし法を行うことで、輪郭検出結果からぴったりした座標が得られます。

四隅の座標が得られればマス目毎の画像を得るのは簡単です。

ステップ 2. マス目の内容推定

ディープラーニングします。

学習データ

学習データはインターネットで集めた約 400 枚の駒画像 (手作業でひと駒ずつトリミングしたのですが、この作業が一番大変でした) と、iPhone のカメラで撮影した盤面 10 枚です。盤面はテレビ画面やネット対局のキャプチャを含みます。

ステップ 1 で作成した盤面正規化プログラムを利用して事前にマス目毎の画像に分割し、手動で駒の有無・種類をラベリングしました。

ネットワーク

入力は単一のマスの画像で、画素数は 64 * 64 です。出力はマスの内容で、空 or 駒の種類 (先手後手それぞれ 15 種類) を判別する 31 のラベルです。ネットワークは畳み込み & プーリング層が 3 層と全結合層 3 層の構成です。

model = Sequential()
model.add(Conv2D(32, kernel_size=(3, 3), input_shape=input_shape))
model.add(BatchNormalization())
model.add(PReLU())
model.add(MaxPooling2D(pool_size=(2, 2)))

model.add(Conv2D(64, kernel_size=(3, 3), input_shape=input_shape))
model.add(BatchNormalization())
model.add(PReLU())
model.add(MaxPooling2D(pool_size=(2, 2)))

model.add(Conv2D(128, kernel_size=(3, 3), input_shape=input_shape))
model.add(BatchNormalization())
model.add(PReLU())
model.add(MaxPooling2D(pool_size=(2, 2)))

model.add(Flatten())
model.add(Dense(1024))
model.add(BatchNormalization())
model.add(PReLU())
model.add(Dropout(0.25))
model.add(Dense(1024))
model.add(BatchNormalization())
model.add(PReLU())
model.add(Dropout(0.5))
model.add(Dense(NUM_CLASSES, activation='softmax'))

ネットワーク構成は こちら の漢字認識率 98.5 % のものを参考にさせて頂きました。

手書き漢字データによるファインチューニング

用意した学習データは駒の書体の種類が少ない (30種類程度) ため、局所特徴量の抽出を担う畳み込み層の学習に適しません。そこで、15 万文字の手書き漢字・ひらがなからなる 手書教育漢字データベース ETL8 を利用して、畳み込み層のパラメータを事前に学習しました。

学習・推定に使う将棋駒データはノイズが多い一方で、ETL8 は非常にノイズが少ないクリアな画像データです。そのため、そのまま学習してしまうと畳み込み層がノイズに対応できず将棋駒をうまく識別できませんでした。そこで、ETL8 に以下のノイズを乗せて学習を行いました。

• ガウスノイズ (強)
• ガウスノイズ (弱)
• 白黒反転
• 回転
• 拡大縮小

その後畳み込み層を固定し、将棋駒データを使って全結合層のみを学習させます。これにより、高い精度の特徴抽出器 (畳み込み層) をそのまま将棋駒の分類に利用できます。

学習結果

Epoch 120/120
loss: 0.1981 - acc: 0.9379 - val_loss: 0.3054 - val_acc: 0.9245

92 % 程度の精度で駒の分類ができました。

今後の課題

いくつか大きな課題点を挙げます。一つは盤面検出の焼きなまし法に 10 秒程度の時間がかかることです。マスク画像を用いた目的関数は微分可能でないため確率的勾配降下法が利用できません。うまく微分を計算できる目的関数を設計すれば処理時間は大きく改善されるはずです。他にも、罫線の周期性を利用してスマートに盤面検出できないかなど考えましたが、具体的な手法は思いつきませんでした。

もう一つは、成銀・成桂・成香の分類問題です。将棋の駒には様々な書体がありますが、ものによっては人間でもそれらの識別が困難な場合があります。

特長が大きかったり一度学習した書体であれば間違えませんが、未知の書体について充分な精度を保証するのはまだ難しいようです。

最後に最も大きな課題は、持ち駒の検出ができないことです。画像によって持ち駒の位置や角度が異なるため、盤上の駒の推定とは違った要素技術が必要になります。

まとめ

将棋盤の画像から、盤面の状態を 92 % 程度の精度で得ることができました。盤面の正規化には輪郭検出・線分検出・焼きなまし法を使い、駒の推定にはディープラーニングを利用しました。普段業務で画像処理やディープラーニングを扱っていないため、今回の手法には冗長な手順や簡単な見落としもあるかと思います。お気づきの点やアイデアがあれば是非コメント頂ければ幸いです。

今回のプログラムは GitHub で参照頂けます。

github.com

おまけ

Mac で動く Electron 製の棋譜検討アプリ を絶賛開発中です。2018 年初頭には公開したいなあ。