59重・合体ナンプレの画像
きっかけ
合体ナンプレを解くアルゴリズムを開発したが、数字を毎回入力するのが面倒くさくなってきたので自動化することにした。
59重ナンプレになると、9x9グリッドが7x5の35個あり、セルの数は２０００個ほどになってしまう。
(これを解いてしまう人は天才だと思う)
OCRは難しい
OCRは"Optical Character Recognition"ということで画像から文字を認識してデータ化するシステムやアルゴリズムのこと。
入力値はデジタルデータだが、きちんと正規化されていないために、正確なOCRを作ることは難しい。
特に手書きの場合は、困難を極める。
この画像は１にも２にも７にも読めてしまう。
OCRに限界を感じる人もいる。
名刺を管理する株式会社SanSanは、OCRの限界を感じ、人海戦術で文字を解読している。
https://jp.sansan.com/knowledge/ocr/
今回の画像の制約
・写真に対応（スキャナやキャプチャももちろんOK)
・基本まっすぐに撮影してもらうが、少しの傾きはOK
・明るさは統一されてなくてもいい。
・紙が多少よれていてもいい。
・周りに関係ない画像があってもいい。
・１セル45pxは確保してもらう。
・手書きには対応しない。
使用したツール
・Ruby
・RMagick(ImageMagick)
処理の流れ
処理は大きく分けて３つになる。
①セルを認識する
②セルの中の数字を認識する
③セルの位置関係から、9x9グリッドの重なりを計算
①セルを認識する
最初に考えたのがセルを囲む直線を認識する方法だが、紙のよれや傾きがあり、セル数が多くなると直線でなくなるので、正しく認識できない。
そこで、１つ１つのセルを地道に認識する方法を選んだ。
セルの４つの頂点を認識し、１つのセルを認識したら上下左右にセルがないかを探索するようにした。
頂点の認識はパターンマッチングによって行った。
②数字を認識する
最初にtesseractを使おうとしたが、思いのほか識字率が悪く、使えない。
認識する必要があるのは０～９までの数字だけなので、自前で用意することにした。
図書館で借りた本を参考にした。
１．２極値化
２．数字を識別するたの閾値を５０種類以上用意した。
閾値の例、２極値化した画像のx方向、y方向の重心がどこにあるかというような値になる。
０の場合のx方向、y方向の重心はほぼ真ん中になり、極端に外れる場合は0でないと認識する。
３．５０種類以上の閾値をクリアしたものが残った数字となる。
数字が残らなかったり、複数ある場合はエラーとなる。
(セルと数字を認識後)
③セルの位置関係から、9x9グリッドの重なりを計算
セルが認識されているので、そこから、35個の9x9グリッドがどのように重なっているか計算し、正規化されたデータとする。
横幅=81、高さ=57をインプットとして、自動で正規化されたデータにしている。
(正規化されたデータの一部)
OCRを実装してみての所感
・この値がこうだからこの画像は3だみたいな決め方をすると失敗する。
・閾値を用意する場合はかなり余裕をもった値にする。
・コントラストが小さいとエッジを抽出できないので失敗する可能性が高くなる。
・画像によれ・たわみがあるとセルの大きさが大きく変わってしまうので正しく認識できなくなる。
・今回は２極値化(モノクロ)を採用したが、元データ(グレースケールのまま)を使用した方が精度は高まるだろう。
・写真でなく、スキャナを利用すればかなり精度は高くなるはず。
・純粋な計算アルゴリズムはRubyだと遅くなるが、今回のコードをC言語で書いたら大変なことになっただろう。
・茶色っぽい紙と薄い字の組み合わせは最悪。
・数字だけでも大変だから、日本語全体で特定の閾値を用意するのには無理だ。
・５９重合体ナンプレは実物のサイズが大きいので、１つ１つのオブジェクトの画像が荒くなる。
・ パズルを解く時間（数秒) <<<<<< OCRの時間(数百秒)
・成功のポイントは折り目やしわをなくし、明るさを均衡にして、なるべくまっすぐに撮影する！！
参考にした本
たまたま図書館にあった。
