The Fool In The Valleyの雑記帳

-- 好奇心いっぱいのおじいちゃんが綴るよしなし事 --

数独でPythonを 10

Javaで書いたプログラムをPythonに移植するという作業を通してPythonに慣れよう、ということでスタートしたプロジェクトですが、「数独Pythonを 1~9」で書いてきたように、処理を①静止画から数独の問題を抽出する、②抽出した問題を解く、という二つのモジュールに分けて考えました。そしてそれらを個別に開発して検証したら、できた気になって少し飽きてしまい、全体をつないで一つのアプリケーションとして完成させるという最後の詰めの作業をさぼっていました。悪い癖です。以前ならそのままにして別のプロジェクトに移ってしまったかもしれませんが、このブログを書き始めたおかげで、一応きちんと最後まで完成させてまとめようという気になりました。

メイン・プログラムは次のようになります。GetProblemが問題を抽出するモジュール、SolveItが問題を解くモジュール、cv2はOpenCVのライブラリです。

# -*- coding: utf-8 -*-
import cv2, GetProblem, SolveIt

def main():
    frame = GetProblem.GetPhotoFromCamera() 
    sudokuProb = GetProblem.GetProblemFromPicture(frame)
    SolveIt.SudokuSolver(sudokuProb)
    
if __name__ == '__main__':
    main()

まずGetProblem の GetPhotoFromCamera() でカメラからの画像を (640, 480, 3)でframeとして取りだします。
そのframeをGetProblemFromPicture(frame) で処理して、数独の問題を9×9のndarrayのsudokuProb として抽出します。それをSolveIt の SudokuSolver(sudokuProb) に渡して解くという流れです。
下は、その処理の経過を示したビデオです。流れが分かるように処理の様子を分割したウィンドウで表示しています。

youtu.be

まず、①Webカメラを使って数独の問題を含む画像を取り込みます。位置を決めて静止画像をキャプチャするとそれを白黒二値変換し、反転、膨張処理して、問題の枠を強調します②。次にそれから画像のなかの問題の枠の傾き、回転を得るために輪郭とコーナーを抽出します③。コーナーの場所が検出できたら透視変換して問題の形を正対した正方形に変換し、数独の各マス目の画像を切り出します④。②から④の画像処理は瞬時に終わります。次に、切り出した画像に対して文字認識を行い、問題のなかの数字を検出し、9×9のndarrayのsudokuProbに問題として格納していきます⑤。この文字認識では、「数独Pythonを 5」で書いたようにTesseractを使っています。数独のマス81個のイメージに対して一つずつ文字認識を行っているので、ここは10数秒ほど時間がかかってしまいます。
数独の問題を9×9のndarrayに変換できたので、それを数独の問題を解くモジュールにsudokuSolver(sudokuProb)として渡し、⑥で問題を解いています。このデモで使った問題は、「数独Pythonを 9」で例として使ったものと同じです。Web上で難問として挙げられていたもので、単純には解けません。そのために途中で候補を仮定し、テストしてみてダメな場合は別な候補を仮定し直すという探索をしています。その様子をグラフィカルに確認できるように、処理の区切りで500msecの休止をいれているので、時間がかかっているように見えますが、実際には、こういう難問でも瞬時に解が得られます。

以上で、数独を解くプログラムをPythonで作るという目標を達することができたので、これで区切りをつけることにします。
ある程度の量のコードを書いたことによって、目的どおりPythonにかなり馴染むことができ、今後メインで使っていこうという気持ちになってきました。

f:id:tfitv:20201126215257p:plain