はじめに
タイトルの通り、画像から数字を読み取って数独を解くWebアプリを作ってみました。現状では、うまくいく場合もあれば、そうでない場合もあります。
完全に自己満足なので、詳しい説明はしないつもりです。
Tesseract.jsについて
この記事を参考にさせていただきました。
ざっくり説明すると、Tesseract.jsとは、画像から文字を認識するためのライブラリです。
公式ドキュメントから、CDNをとってくるのが手軽で良いと思います。（記事執筆時のバージョンは以下のとおりでした。）
<script src='https://unpkg.com/tesseract.js@v2.1.0/dist/tesseract.min.js'></script>
数独を解く
数独を解くアルゴリズムについては、この記事を読むのがいいと思います。（今回は、解ければなんでも良いので、効率よりも分かりやすさを優先しています。）
sudoku.js
// 数独のクラス
class Sudoku {
static none = '0'; // 後で説明
static zero = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
]
_problem;// 問題
get problem() { return this._problem }
set problem(value) { this._problem = value }
_solution;// 解
get solution() { return this._solution }
set solution(value) { this._solution = value }
// コンストラクタ
constructor(array) {
this.problem = Sudoku.copy(array);
this.solution = Sudoku.zero;
}
// 表示（canvasに線を引いたり数字を書いたりしている）
show(canvas) {
const ctx = canvas.getContext('2d');
const cw = canvas.width / 9;
const ch = canvas.height / 9;
ctx.font = `${Math.floor(cw * 0.8)}px sans-serif`;
ctx.textAlign = 'center';
ctx.textBaseline = 'middle';
ctx.clearRect(0, 0, canvas.width, canvas.height)
for(let i = 0; i <= 9; i++) {
ctx.strokeStyle = 'black';
if(i % 3 == 0) ctx.lineWidth = 2;
else ctx.lineWidth = 0.5;
ctx.beginPath();
ctx.moveTo(0, ch * i);
ctx.lineTo(canvas.height, ch * i);
ctx.stroke();
ctx.moveTo(cw * i, 0);
ctx.lineTo(cw * i, canvas.height);
ctx.stroke();
}
for(let i = 0; i < 9; i++) {
for(let j = 0; j < 9; j++) {
if(this.problem[i][j] != 0) {
ctx.fillStyle = 'black';
ctx.fillText(this.problem[i][j], cw * (j + 0.5), ch * (i + 0.5));
}
else if(this.solution[i][j] != 0) {
ctx.fillStyle = 'red';
ctx.fillText(this.solution[i][j], cw * (j + 0.5), ch * (i + 0.5));
}
}
}
}
// 数独を解く
solve() {
this.solve_process(this.problem, 0, 0);
}
// 配列のi行j列をみる
solve_process(array, i, j) {
if(i == 9) { // すべて埋まった
this.solution = array;
return true;
}
if(array[i][j] != 0) { // すでに数字あり
let next = Sudoku.next(i, j);
return this.solve_process(array, next[0], next[1]); // i行j列までは埋まっているので次の場所をみる
}
for(let num = 1; num <= 9; num++) { // 1~9の数字を入れて成立するか確かめる
if(Sudoku.lookRow(array, i, j, num) && Sudoku.lookColumn(array, i, j, num) && Sudoku.lookBlock(array, i, j, num)) {
// 横、縦、３×３のブロックに同じ数字がない場合
let tmp = Sudoku.copy(array);
tmp[i][j] = num; // 数字を仮置き
let next = Sudoku.next(i, j);
if(this.solve_process(tmp, next[0], next[1])) return true;
}
}
return false;
}
// 次の行と列を取得する関数
static next(i, j) {
let i2 = i, j2 = j;
j2 += 1;
if(j2 == 9) {
i2 += 1;
j2 = 0;
}
return [i2, j2];
}
// 同じ行に同じ数字がないか？
static lookRow(array, i = 0, j = 0, num = 1) {
for(let k = 0; k < 9; k++) {
if(k == j) continue;
if(array[i][k] == num) return false;
}
return true;
}
// 同じ列に同じ数字がないか？
static lookColumn(array, i = 0, j = 0, num = 1) {
for(let k = 0; k < 9; k++) {
if(k == i) continue;
if(array[k][j] == num) return false;
}
return true;
}
// 同じ３×３のブロックに同じ数字がないか？
static lookBlock(array, i = 0, j = 0, num = 1) {
const k0 = Math.floor(i / 3) * 3;
const l0 = Math.floor(j / 3) * 3;
for(let k = k0; k < k0 + 3; k++) {
for(let l = l0; l < l0 + 3; l++) {
if(k == i && l == j) continue;
if(array[k][l] == num) return false;
}
}
return true;
}
// 配列をコピー
static copy(array) {
let tmp = new Array(9);
for(let i = 0; i < 9; i++) {
tmp[i] = new Array(9);
for(let j = 0; j < 9; j++) {
tmp[i][j] = array[i][j]
}
}
return tmp;
}
}
solve_processでは、再起処理を行っています。ゴールにたどり着いたら、solutionを解となる配列に変更します。実際に数独を解きたいときは、次のように記述します。
// arrayは問題を配列化したもの（空欄は0に設定）
// canvasはHTMLのcanvas要素
var sudoku = new Sudoku(array); // インスタンス化
sudoku.solve(); // 数独を解く
sudoku.show(canvas); // canvasに表示
画像認識を行う
では、本題の画像認識について説明したいと思います。ソースコード、どーん。
index.html
<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<script src='https://unpkg.com/tesseract.js@v2.1.0/dist/tesseract.min.js'></script>
<style>
#image_zone {display: block;}
canvas {border: solid black 1px; border: black solid 1px;}
#output {line-height: 3em;}
</style>
<title>数独</title>
</head>
<body>
<input type="file" accept="image/jpeg, image/png" id="image_zone">
<div id="output"><br></div>
<table>
<tr>
<td>画像のプレビュー</td>
<td></td>
<td>読み取った数字</td>
<td></td>
<td>数独の解（複数ある場合は１つだけ）</td>
</tr>
<tr>
<td><canvas width=300 height=300 id="canvas1"></canvas></td>
<td style="vertical-align: middle"> → </td>
<td><canvas width=300 height=300 id="canvas2"></canvas></td>
<td style="vertical-align: middle"> → </td>
<td><canvas width=300 height=300 id="canvas3"></canvas></td>
</tr>
</table>
<div style="display: none;">
<p>～デバッグ用～</p>
<canvas width=400 height=400 id="myCanvas"></canvas>
</div>
<script type="text/javascript" src="sudoku.js"></script>
<script type="text/javascript" src="main.js"></script>
</body>
</html>
main.js
const imageZone = document.getElementById('image_zone') // 画像ゾーン
const out = document.getElementById('output') // メッセージ領域
const myCanvas = document.getElementById('myCanvas'); // Tesseract.jsに渡す用
const canvas1 = document.getElementById('canvas1'); // 画像のプレビュー
const canvas2 = document.getElementById('canvas2'); // 読み取った数字
const canvas3 = document.getElementById('canvas3'); // 数独の解
// arrayの初期化
var array = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
]
// ユーザがファイルを選択したら
imageZone.addEventListener('change', e => {
const file = e.target.files[0]
if (!file.type.match('image.*')) { return }
out.innerHTML = '読み込み中...';
recognize(file).then(text => {
console.log(text);
out.innerHTML = '読み込み完了！';
SetArray(text);
let sudoku = new Sudoku(array);
sudoku.show(canvas2); // 解く前の問題を表示
sudoku.solve(); // 数独を解く
sudoku.show(canvas3); // 解いた後の解を表示
})
}, false);
// myCanvasの画像から数字を読み取る
function recognize(file) {
return new Promise((resolve, reject) => {
imageToCanvas(file).then(() => {
Tesseract.recognize(
myCanvas,
'eng',
{ logger: m => console.log(m) }
).then(({ data: { text } }) => {
resolve(text)
})
}).catch(error => {
reject(error)
})
})
}
// imageをcanvasにいい感じに表示（後で説明）
function imageToCanvas(file) {
return new Promise((resolve, reject) => {
readImage(file).then(src => {
loadImage(src).then(image => {
canvas1.getContext('2d').drawImage(image, 0, 0, image.width, image.height, 0, 0, canvas1.width, canvas1.height)
const iw = image.width / 9;
const ih = image.height / 9;
const cw = myCanvas.width / 9;
const ch = myCanvas.height / 9;
const d = 0.7;
const ctx = myCanvas.getContext('2d')
ctx.fillStyle = 'blue';
ctx.font = `${Math.floor(cw * 1)}px sans-serif`;
ctx.textAlign = 'center';
ctx.textBaseline = 'middle';
for(let i = 0; i < 9; i++) {
for(let j = 0; j < 9; j++) {
ctx.drawImage(
image,
iw * (j + (1 - d)/2), ih * (i + (1 - d)/2),
iw * d, ih * d,
cw * j, ch * i,
cw, ch
)
if(!isNum(cw*j, ch*i, cw, ch)) {
ctx.fillText(Sudoku.none, cw * (j + 0.5), ch * (i + 0.5));
}
}
}
resolve()
}).catch(error => {
reject(error)
})
}).catch(error => {
reject(error)
})
})
}
// マスに数字が含まれているか？または空欄か？（マス内のピクセルの色をみる）
function isNum(sx, sy, sw, sh) {
const ctx = myCanvas.getContext('2d')
let ave = 0;
for(let x = sx; x < sx + sw; x++) {
for(let y = sy; y < sy + sh; y++) {
let imageData = ctx.getImageData(x, y, 1, 1);
let r = imageData.data[0];
let g = imageData.data[1];
let b = imageData.data[2];
ave += (255 - r + 255 - g + 255 - b);
}
}
ave /= sw * sh;
if(ave > 30) return true; // この30は適当に決めた
return false;
}
// 画像の読み込み（base64形式に変換）
function readImage(image) {
return new Promise(function (resolve, reject) {
const reader = new FileReader()
reader.onload = () => { resolve(reader.result) }
reader.onerror = (e) => { reject(e) }
reader.readAsDataURL(image)
})
}
// ファイルのロード
function loadImage(src) {
return new Promise(function (resolve, reject) {
const img = new Image()
img.onload = () => { resolve(img) }
img.onerror = (e) => { reject(e) }
img.src = src
})
}
// 文字列（recognizeから吐き出されるtext）をarrayに変換
// textが正しく吐き出されたと仮定している
function SetArray(text = '') {
text = text.replace(' ', '')
if(text.length >= 90) {
let t = 0;
for(let i = 0; i < 9; i++) {
for(let j = 0; j < 9; j++) {
if(text[t] == Sudoku.none) {
array[i][j] = 0;
}
else {
array[i][j] = text[t];
}
t++;
}
t++;
}
}
}
恥ずかしながら、今回はじめてPromiseというものを知りました。コードがすっきりかけて便利ですね。
画像の処理について
// ～画像処理を行っている場所を抜粋～
// imageの1マスの大きさ
const iw = image.width / 9;
const ih = image.height / 9;
// canvasの1マスの大きさ
const cw = myCanvas.width / 9;
const ch = myCanvas.height / 9;
const d = 0.7; // imageで数字のみを切り取るために領域を0.7倍に狭める
const ctx = myCanvas.getContext('2d')
ctx.fillStyle = 'blue';
ctx.font = `${Math.floor(cw * 1)}px sans-serif`;
ctx.textAlign = 'center';
ctx.textBaseline = 'middle';
for(let i = 0; i < 9; i++) {
for(let j = 0; j < 9; j++) {
// imageの1マスをcanvasの1マスに書き込む
ctx.drawImage(
image,
iw * (j + (1 - d)/2), ih * (i + (1 - d)/2),
iw * d, ih * d,
cw * j, ch * i,
cw, ch
)
if(!isNum(cw*j, ch*i, cw, ch)) {
// 空欄だったらSudoku.none（つまり'0'）をmyCanvasに書き込む
ctx.fillText(Sudoku.none, cw * (j + 0.5), ch * (i + 0.5));
}
}
}
最初は、ユーザが選択した画像ファイルからそのまま数字を読み取れることができるかを試しました。すると、縦線・横線の影響からか、うまく数字が読みとれないことが分かりました。
そこで、縦線・横線を除去するためにimageの各マスの一部（真ん中の部分）を切り取ることにしました。すると、今度は数字は読み取れるものの、空白の部分がうまく読み取れないことが分かりました。
そこで、空白の部分に別の文字('0')を書き込むことにしました。すると、今度はうまくいきました。（すべてのケースでうまくいくわけではない......）
画像処理がうまくいけば、上のような画像がmyCanvas上に生成されます。これをTesseract.jsに読み取ってもらいます。
感想
Tesseract.jsは素晴らしいライブラリですが、実際に使ってみると、まだまだミスは多いのかなと感じました（使い方が悪い可能性もある）。
最初の最初は、各マスをTesseract.jsに読み取ってもらっていたのですが、それでは時間がかかりすぎるということで、紹介した方法を選択しました。ですが、正確さを求めるなら、各マスを読み取ってもらったほうがよさそうかもしれないですね。
各パラメータは試行錯誤して調整したものですが、もっと良いパラメータがありそうです。
今回作ったものは実用には耐えなそうですが、これからも改善していこうと思います！
おまけ（謎の失敗）
O, oはまだ理解できるが、eはどこから出てきたんだ、、
ちなみにこのときに得た文字列は、
850000600
000020090
040000000
300508000
000000012
0oo000O0O0O
009010000
000700500
o0o006e00800
でした。同じ文字を重複して数えてしまっているのでしょうか。
追記
読み取る文字を0-9に限定したところ、数字の読み取りの精度が少し上がりました。このページを参考に、main.jsのrecognize周辺を以下のように変更しました。
main.js
const { createWorker } = Tesseract;
function recognize(file) {
return new Promise((resolve, reject) => {
imageToCanvas(file).then( async () => {
const worker = createWorker({
langPath: '...',
logger: m => console.log(m),
});
await worker.load();
await worker.loadLanguage('eng');
await worker.initialize('eng');
await worker.setParameters({
tessedit_char_whitelist: '0123456789'
});
const { data: { text } } = await worker.recognize(myCanvas);
resolve(text);
}).catch(error => {
reject(error)
})
})
}
正直なところ、チンプンカンプンですが、
await worker.setParameters({
tessedit_char_whitelist: '0123456789'
});
の部分で、読み取る文字を0-9に限定しています。ご参考までに。