2019/01/31

Excelで書類の発行元をロゴ画像認識により判定する実験

書類自動仕分けプログラム

当社には、いろいろな書類が数多く届き、それを逐一スキャンして整理しているのだが、書類の数量が多すぎて仕分けが大変であるために、自然言語による仕分けソフトを過去に作った。

この書類仕分けソフトは、TFIDF×コサイン類似度というアルゴリズムで動いており、簡単にいえば自然言語解析をベースにしたものである。

最近は、この記事からさらなる改良を重ね、当社に届く業務書類であれば8-9割以上は正しく仕分けができるようになっている。
改良の内容とは、主には、教師データの見直しである。

画像も見ながら仕分けできないか

しかし、この仕分けソフト、その設計上、OCRした後の文字列のみを頼りに仕分けをしている。画像は一切見ていない。そうすると、銀行の振込伝票のように

・文字量が極端に少なく文字だけでは何の書類だか判別できない
・銀行名の印字もない(もしくは帳票がドロップアウト印刷のためOCRで正しく文字が読み取れていない)
・だが、銀行のロゴは出ているので人間が見れば一目瞭然

というような帳票はエラーになってしまい、がっかりする。

なので、今回は、ロゴが出ているならばそれを頼りに「銀行関連の書類」であると書類カテゴリを推定し、また、発行した銀行名を当ててみよう。という試みである。

OpenCVを試したらいまいち

では、どのようなロジックで認識するか。これが問題である。

Convolutional Neural Networkのような画像認識のロジックを作るどころか理解するのも困難であるため、ここは素直にOpenCVに依存しようと考え、
python+OpenCVでAKAZEなる認識を試したものの、思ったように精度が出なかった。


右にお手本となる某財閥系大企業のロゴがあり、書類上のロゴと結ばれるはずだったのだが、誤認識している。おそらくこれは認識ロジックがロゴに適していなかったのかな。という気もする。

それを差し引いても、OpenCVを操る面倒さと、思ったよりも期待した精度は簡単には出ないことを知っている人ならば、人工知能で人間の仕事がなくなるのは、もうしばらく先であることを理解できるだろう。

OpenCVでの物体認識は認識は引き続き研究するとして、違う方法をあたることにした。

総当たり&差の絶対値での画像検出を試す

Convolutional Neural Networkを研究してみたところ、ピクセルを畳み込んで抽象化して、中間オブジェクトみたいなものを作って、それとお手本の類似度を判定するのかな。みたいな感じに読めた。

だが、ロゴは抽象化して、犬と猫のどちらに似ているか。みたいなことをする必要はない気がして、Exact Matchに近い感じでいけるのではと思った。そのため、総当たりで差の絶対値を計算してみることにした。

とりあえず、総当たりでやってみて精度をチェックしてみよう。結論的には、試したサンプル(といっても5個くらいだけど)のすべてにおいて、適正な検出&誤検出ゼロを達成。
現在、いろいろ研究されている検出アルゴリズムよりも精度が良いわけだ。これはどうしたことだろう。

おそらく、OpenCVも、ロゴの検出に特化するならば総当たり&差の絶対値の精度が良いことは分かっているが、
それをやってしまうと変形に弱い、また、計算量が膨大で遅いので、違うモデルを考えたということなのではないか。

コピー機でスキャンされたロゴの検出が総当たりと相性が良いのは下記の特殊性も関係している。ロゴの性質上
・上に別のオブジェクトが重なることはない
・一部分だけしか見えないことがない
・周囲にほどよく空白があり、ロゴの隙間を縫って違うデザインが施されていることはあり得ない
・基本的に背景は白(または反転)
・多少、傾いていることはあるが基本的には水平
・拡大縮小率は50-200%くらいで見ておけば十分
という限られた変化しかない。Exact Matchではないが、結構それに近い。なので、一工夫を施せば総当たりが最も精度が良いのだ。

検出の手順

単純明快に次のようなロジックを自作した。

・お手本ロゴと入力書類をモノクロBMP化する
・BMPから輝度の値(黒0~255白)を抜き出してExcel上に展開する
・色が全体的に薄い書類は、その書類の中で最も濃い色を真っ黒と見なして正規化する。それでも薄い場合は薄い部分のレベルを下げる(グレースケールではあるものの若干の黒つぶれ状態を作る)
・書類はA4サイズ*300dpiを等倍で縮小。1024×724=741,376の輝度の羅列とする。それをExcel上に展開する。ロゴも同様に輝度をExcel上に展開する。
・あとはロゴを1ピクセルずつ、縦と横に計約74万回スライド(スキャン)させていき差の絶対値を取得する
→差の絶対値の総和がゼロであれば、お手本ロゴとスキャンした範囲はぴったり同じである。なので、総和が小さい方がお手本との一致度が高い。
→二枚の紙を太陽に向けて透かして差分を目視するのと同じ原理。


モノクロ書類画像の輝度をExcel上に並べると書類を間近で見たのと同じ模様が浮かび上がる。銀行!


おもしろい。

高速化のためにやってみたこと

さて、問題は、総当たりスキャンの計算量である。
書類のサイズ1024×724=741,376ピクセル そして、ロゴのサイズ44×38 = 1,672ピクセルをかけ算して、12億セルほどを計算しなければならない。
VBAでループなどを作ってしまうと画像1枚で数十分ほどかかってしまう。ExcelのVBAは、うまく使わないと非常に遅い。極力、使わないほうが良い。

このイメージが悪いためか、Excelは非常に遅いアプリだと思われがちだが、じつは関数による計算は並列処理可能であり、とても速いのである。
なので、ここはCPUによる並列処理が可能な関数だけで、セル範囲の差の絶対値の総和を取得したいところである。調べたところ、次のような配列を使うととても良い。


指定した矩形範囲 vs 別の矩形範囲(当然に同セル数でなければならない)の差の絶対値の総和を計算してくれる。これのすごいのは、14億セル分の計算を10秒くらいで完了(i7-8700K)できる点である。非常に速い。正直、画像が認識できたことよりも、Excelがここまで高速であることに感動した。

まだ遅いので画像をマスキングして高速化

もう少し速くならないかなということで、画像の全体を1セルずつ丹精込めて計算することを放棄したい。

・ロゴ画像の輝度値の合計値
・スキャンする範囲の輝度値の合計値

これがあまりにも違う場合、スキャン範囲にロゴがあるわけはないので、このような全然違うカ所を除外するロジックを実装してみた。
スキャン範囲の輝度合計値は、プラス方向にしか蓄積されていかないので、このような計算の手抜きが可能である。
ロゴファイルの輝度の合計値の0.7~1.3倍までをスキャンするようにしたところ、計算は7倍ほど速くなり精度は変わらなかった。これは、もう少し範囲を絞って、もっと計算量を減らしても良い(が、たまに検出漏れが出ることになる)

スキャン範囲の輝度の合計値を出すには、前に説明のSUMPRODUCT+ABSの代わりにSUMを使うだけである。

スキャン範囲の中で差の絶対値が最小の値を拾ってくる

差の絶対値が最小ということは、数万件の範囲をスキャンをした中で、ロゴと書類のスキャン範囲の差が最も少ない(最も類似している)ということである。仮にゼロならば完全一致であるので確実にそこにロゴが存在している。

この画像ではわかりにくいのだが、このセル番地(VF483)を、書類を展開したシート上で確認すると、ロゴの左上端(ぴったり)となっている。検出できた。
めでたし。のように見えるのだが、差の絶対値の最小値を単純に拾ってくるだけでは、ロゴが存在しているのか否か分からないので、閾値を設定しなければならない。

検出有無を判定するための閾値の設定

 

結果を先に貼り付けると、書類にロゴが含まれている場合と、含まれていない場合では、スキャン範囲の差の絶対値の合計値の分布がちょっと違うのである。
ロゴ検出有りのほうは正規分布が非常に尖っている。それは書類にロゴが含まれているフラグとなる。

この尖りを目印にして閾値を設定すれば、ロゴの有無を検出できる。

標準偏差の何倍以遠を検出すれば・・など試してみたのだが、尖りすぎて標準偏差を閾値にしてもいまいちであった。
原始的すぎて悲しいが、最小値が、範囲の差の絶対値合計(数万件をスキャンしたものに対してそれぞれ求める)の平均値の半分以下くらいであれば検出としてみると、高精度であった。

一応の完成

まだ実験段階ではあるが、このようにExcelでも書類上からロゴを検出するロジックは実用的に組める気がした。

完全一致のマッチングというアルゴリズムの性質上、ロバスト性はどうなのか。というのが気になるところ。
1ピクセルでもずれたらまったく一致しないかと思ったのだが、思ったよりも大丈夫そう。

どうやら入力画像の質が良いことが関係している。最近のスキャナはエッジをきれいに階調で読み込んでくれるので、真っ白の次に真っ黒が来ることはない。なんとなくグラデーションになっている。そのため、1-2ピクセルずれていても、都合良くマッチするのである。

ただ、拡大縮小に対しては耐性がゼロに近いので、100枚くらいロゴの拡大縮小を生成して準備する必要があるだろう。ImageMagick というコマンドラインアプリをExcelから呼び出せば、画像を増殖させることは簡単にできる。
現在、A4サイズの書類からロゴを検出するのが10秒程度。なので、拡大縮小で100倍の時間をかけたとして(ここも計算量を減らす工夫はできそうだが)16分。

画像数を増やすと書類1枚当たり15分程度かかってしまう(i7-8700K 12コア)が、夜間のバッチ処理であれば耐えうる速度ではある。
いや、さすがにこれは遅いだろう。と思った人たちがConvolutional Neural Networkなどを研究しているのかもしれないが、

予算の余っている投資家は素直に多コアのコンピュータを買えばよいだろう。筆者もAMDのEPYC 64LP(論理コア)を買った。128LPでも100万円くらいで買えるはずだ。買わないけど。
それらを使えば、1枚あたり3-4分でかなり高精度にロゴを検出できるのではと思う。近日、お試し予定。

この画像認識アルゴリズムは、近いうちに当社の書類仕分けシステムに実装していきたいと思っている。