なにしたの？

GitHub Pages で動く数独ソルバーを作ってみました。

• Sudoku Solver (PC で数独をカメラに映してライブで解くバージョン）
• Sudoku Solver (画像を選択するバージョン、携帯はこちらがおススメ）

ソース：GitHub: Sudoku Solver via Wasm

👁 image_0.png

ここでは以下の ３ 点について簡単に紹介します。

• そもそもの動機
• 画像が処理される過程の解説
• CNN での予測を安定化させるための工夫

なんでいまさらこんなことを・・

数独を解く例題はたくさんあるが、、何かソフトを立ち上げないと遊べないのはつまらない！ということで誰でも遊べるようにしたかったんです。手軽に公開出来て・手軽にアクセスできるように GitHub Pages に上げました。

数独をプログラムで解かせる例は MATLAB だと

• Solving Sudoku with MATLAB By Cleve Moler, MathWorks
• 整数計画法により数独パズルを解く: ソルバーベース

や、File Exchange で "Sudoku" で検索すると 63 件（2021/12/11 時点）もヒットします。中には画像から数独を認識させて解く例もあります。例えばこの 2 つ。前者はセミナーのつかみによく使ってました（笑）

• Video Sudoku Solver by Teja Muppirala
• Deep Sudoku Solver by Justin Pinkney

後者はセマンティックセグメンテーションを使って Sudoku を画像から見つけて・・とかなり気合の入った力作です。2018 年に MATLAB Expo UK で ”Computer Vision and Image processing with MATLAB” として講演されました。英語ですが結構丁寧に解説されているので興味のある方は是非こちらチェックしてみてください。（動画、ブログ）

具体的にどうやったのか

手順は以下の通り

1. Teja さんのコードをベースに C コード生成できるように書き換え
2. 数字認識部分は CNN を使うように変更
3. WebAssembly 化して JavaScript で呼び出し

ポイント１：できるだけ軽く・・

Deep Sudoku Solver by Justin Pinkney のように CNN にいろいろお任せするのも 1 案ではありますが、今回はブラウザで動かすことを考えてできるだけ重い処理は避けたい。なので Deep Learning を使う部分は数字の認識だけにとどめて、更に軽いネットワークでも動くように、数値を取り出すところまでを画像処理で何とかすることにします。画像処理関係の関数は多くが C コード生成に対応しているので WebAssembly への変換も大丈夫です。数字認識（CNN での予測）も手軽に精度が安定するようにちょこっと工夫しました。

ポイント２：WebAssembly 化

MATLAB Coder で C コード化して WebAssembly 化する部分は GenerateJavaScriptUsingMATLABCoder, Geoff McVittie (2021) を使います。このツールは以前も Qiita で紹介しています。

• MATLAB のニューラルネットをブラウザで動かす: MATLAB > C++ > WebAssembly の自動変換
• MATLAB -> C++ -> WebAssembly の自動変換を使った非線形最適化 on JavaScript

C コード生成に対応している処理であれば MATLAB の処理がそのまま Javascript に統合できるので便利。これは MathWorks 製品に含まれてはいませんが、MathWorks の社員が業務外で作って公開してくれたものです。

実際に変換する際に wasm-ld: error: initial memory too small に遭遇しましたが、これは Emscripten からのメッセージで

-s INITIAL_MEMORY=205914112

というフラグを付けることで回避。背景は @goccy さんの「1年間本番環境で WebAssembly ( by Emscripten )を使ってきた中で生じた問題とその解決策」が参考になります。

主要な関数の概要

必要なソースコードは GitHub: Sudoku Solver via Wasm に置いてありますが、肝になる関数・スクリプトは以下の通りです。

• solveSudokuImage_codegen.m：今回コード生成するエントリー関数
• solveSudokuImage_codegen_script.m：上の関数を WebAssembly 化するスクリプト
• testrun1_Image.m：静止画像に対しての処理を確認するスクリプト
• testrun2_Webcam.m：ウェブカメラ画像に対しての処理を確認するスクリプト
• digitPredictFcn_CNN.m：CNN を使用した数字認識用関数
• trainCNNtoClassifyDigits.md：数字認識する CNN の学習ステップ解説
• generataDigitsImage2Train.m：↑ の学習に使用する数字の画像作成スクリプト

エントリー関数である solveSudokuImage_codegen.m は数独の画像（実装時は 750 x 750 で固定）を入力として受けて、解を上書きした画像を返します。

使用した Toolbox

• MATLAB R2021b
• MATLAB Coder
• Image Processing Toolbox
• Deep Learning Toolbox

画像処理ステップ

Deep Sudoku Solver by Justin Pinkney のようにセマンティックセグメンテーションを使って数独を認識させるのも1案ではありますが、今回はブラウザで動かすことを考えてできるだけ重い処理は避けたい。Deep Learning を使う部分は数字の認識だけにとどめ、数値を取り出すところは数独を大きく撮るという撮影方法と＋画像処理で何とかすることにします。

ここでは入力画像がどのように処理されていくかの流れを紹介します。

入力画像の 2 値化 + ノイズ除去

まず携帯で撮影した画像を読み込んで 2 値化します。RGB イメージからバイナリ イメージを生成するには、まず rgb2gray でグレースケールに変換して imbinarize で。rgb2gray も imbinarize も C コード生成対応関数ですね。

撮影状況も様々だろうと想定し、サンプルにある適応しきい値処理を使います。

Icam = imread('photoEx5.jpg');
figure
imshow(Icam)

Igray = rgb2gray(Icam);
Ibw = ~imbinarize(Igray,'adaptive', ...
 'ForegroundPolarity','dark', ...
 'Sensitivity',0.4); % codegen ok
tmp = Ibw; % 比較表示用

枠内に小さいゴミが見られるので画像全体の 0.01 % （サイズで 1%）より小さいものは bwareaopen を使って取り除きます。

thNoise = numel(Ibw)*0.0001; % 0.01%
Ibw = bwareaopen(Ibw,floor(thNoise)); % code gen ok

さらに今回はあまり気になりませんが、imclearborder で外とつながっているピクセルを除去しておきます。しっかり画像に写っているものだけを気にします。画像を並べて比較するには montage ですね。

Ibw = imclearborder(Ibw); % code gen ok
figure
montage({tmp,Ibw},BackgroundColor='white',BorderSize=[10,10])

👁 figure_1.png

数独の認識

regionprops を使って一番大きな物体（ピクセルの集まり）を探します。数独の他に大きな物体が写り込んでいると上手くいかないので要注意。この辺は画像の撮り方で対処することにします。

R = regionprops(Ibw,'Area','BoundingBox','PixelList') % code gen ok

結果は構造体ベクトルとして出てきますので、C コード生成対応している範囲で、一番 Area (面積) が大きい物体を探します。

areaMax = 0;
kmax = 0;
for ii=1:length(R)
 if areaMax < R(ii).Area
 areaMax = R(ii).Area;
 kmax = ii;
 end
end

% C コード生成しないならこんな書き方も。。
% [~,kmax] = max(vertcat(R.Area));
% tR = struct2table(R);
% [~,kmax] = max(tR.Area);

一番大きな物体の四隅のピクセル位置を探して、プロット。

tmpR = R(kmax);
tmp = tmpR.PixelList;
DIAG1 = sum(tmp,2);
DIAG2 = diff(tmp,[],2);

[~,dUL] = min(DIAG1); [~,dDR] = max(DIAG1);
[~,dDL] = min(DIAG2); [~,dUR] = max(DIAG2);

pts = tmpR.PixelList([dUL dDL dDR dUR dUL],:);

figure
imshow(Ibw)
hold on 
plot(pts(:,1),pts(:,2),'m','linewidth',3);

幾何学変換

大枠が捉えられたのでここから枠内の数字を抽出します。ただ、今回の画像は数独が斜めに写っていますので、まずは数独を正面に捉えた画像に幾何学的変換。fitgeotrans を使います。その後は 9x9 の升に等分してその中身を数字のピクセルして取り出します。

fixedPoints = [1 1; 9 1; 9 9; 1 9]/10.*size(Ibw); % 変換後の数独の四隅の位置（正方形）
movingPoints = pts(1:4,:); % 変換前の数独の四隅

とその前に、数独がうまく捉えられていない場合は入力をそのまま返すようにエラー処理を入れておきます。数独として捉えただろう枠の面積が全体の 10 % に満たない場合はエラーとしておきます。もう少し大きく映してね。

boxarea = polyarea(movingPoints(:,1),movingPoints(:,2));

if boxarea/(1e6) < 0.1
 tmp = cat(3,Icam,zeros(N,N,1,'uint8'));
 tmp = permute(tmp,[3,2,1]);
 Imask = tmp(:);
 return
else
 transformationType = "projective";
 tform = fitgeotrans(movingPoints,fixedPoints, ...
 transformationType); % code gen ok % error occurs here for bad images
end
Ibw_warp = imwarp(Ibw,tform); % code gen ok
Icam_warp = imwarp(Icam,tform); % code gen ok

figure
montage({Ibw,Ibw_warp},BackgroundColor='white',BorderSize=[10,10])

👁 figure_3.png

再度大きい枠（数独）の探索＋中の数字を抽出

変換後の画像内の四隅のピクセル位置を同じ処理で見つけ、今度はその枠を 9x9 に等分します。

👁 image_1.png