同じ行要素のグループ化

OCRの開発している背景

レシートローラーでは、紙レシート削減を目指して事業を進めていますが、
明日紙レシートがなくなるわけではなく、紙レシートをなくしていく工程をサポートすることが、
実際に紙レシートゼロになると信じています。
ですので、OCRという技術を使い紙レシートの電子化も進めている手前です。

OCR(Optical Character Recognition)とは

OCRとは光学文字認識の略語です。画像や紙の文書などの文字データを、
コンピュータが理解できるテキストデータに変換する技術です。この用途は多岐にわたり、
文書のデジタル化や自動データ入力、電子書籍の作成、テキスト検索などの場面で役立ちます。

簡単な自己紹介

ここで突然ではありますが自己紹介をさせていただきます。私は岡田と申します。
23歳の大学院生で、アルバイトとして開発業務に携わらせていただいてます。
まだ経験の浅い身ではありますが、試行錯誤を通して開発に貢献していきたいと思っています。
よろしくお願いします。

開発環境

レシートローラーでは、ASP.NET Core X C# X Azureというスタックで開発をしています、
本日のブログでも、こちらのスタックを前提に書かれています。（開発メンバー募集中です）

与えられたタスクと解決したい課題

一般的なOCRライブラリーを用いて文字認識を行うと、横書きに連続して
印字されている文字に対し、グループ化されて出力されます。
これは「卵　　200円」のように私たちが目で見ると、
同じ行にあると認識できますが、出力されるデータでは「卵」と「200円」のように、
別の要素として認識されます。レシート上には、別の要素も多く存在しており、
どの要素同士が意味のある組み合わせなのかを判別したい、つまり、「卵　200円」のほかに
「キャベツ　150円」があったとすると、出力は「卵」「200円」「キャベツ」「150円」
となります。そうすると卵が200円なのか、キャベツが200円なのかは、
得られたデータからは判別できません。レシートは行によって、
要素同士に関係を持たせているため、同じ行の要素をグループ化することが、
私に回ってきたタスクと課題になります。

理想的な画像における行のグループ化

まずは、理想的なグループ化を定義したいと思います。
今回進めたアプローチは、Y(縦)座標に注目してグループを振り分ける方法です。

図のように、各要素の4頂点の座標(x,y)が与えられるので、
それぞれの左側頂点のy座標の中間値leftYMid、
中間値と左側の頂点のy座標との差thresholdを計算します。
AのleftYMidとBのleftYMidの差が、threshold未満なら同じ行にあると判別します。

そんな簡単ではない、レシートの傾き補正

レシートの画像を撮影するときに、まっすぐ正確に撮影するのは難しく、
少なからず斜めになってしまいます。このように傾きがあると同じ行にあるにも関わらず
、y座標が大幅に異なることがあります。この問題を解決するために、
要素の座標をすべての要素の傾きの平均を利用して回転させることで、
ある程度の補正を行います。　
左の中間座標$ (x_1,y_1) $、右の中間座標$ (x_2,y_2) $を利用して次の式で要素の傾きを導出できました。

$$ \frac{y_2 - y_1}{x_2 - x_1} $$

次にこれを実現するコードを示します。BoundingBoxは要素の座標の四頂点のx,y座標を、
左上から時計回りに保存した配列です。

CalcBias.cs

static double CalcBias(Line line)
    { 
         return (double)((((line.BoundingBox[3] + line.BoundingBox[5]) / 2.0) - 
    ((line.BoundingBox[7] + line.BoundingBox[1]) / 2.0)) / (((line.BoundingBox[2] + 
    line.BoundingBox[4]) / 2.0) - ((line.BoundingBox[6] + line.BoundingBox[0]) / 2.0))); 

     }

座標の回転を行うにはすべての要素の傾きの平均をとり、全体を回転します。
傾きの平均をAvgAngleとし三角関数を用います。その式は次のようになります。

$$
\theta = -\tan^{-1}(AvgAngle)
$$
$$
\hat{x} = x * \cos{\theta} - y * \sin{\theta}
$$
$$
\hat{y} = x * \sin{\theta} + y * \cos{\theta}
$$

これをすべてのx座標y座標に対して行い、要素の座標を変換します。
そのコードを次に記載します。

rotation.cs

double theta = -Math.Atan(avgAngle); 

foreach(var line in ReadResult.Lines) 
    { 
        for (int i = 0; i < 8; i += 2) 
            { 
                double x = line.BoundingBox[i]; 
                double y = line.BoundingBox[i + 1]; 
                line.BoundingBox[i] = (int)(x * Math.Cos(theta) - y * Math.Sin(theta)); 
                line.BoundingBox[i + 1] = (int)(x * Math.Sin(theta) + y*Math.Cos(theta)); 
            } 	 
    }

外れ値処理

Zスコアがある範囲内にあるデータポイントのみを、利用することでデータの中で大きすぎる値や、
小さすぎる値を除外します。これを行わないと一部の大きな傾きを持つ要素が全体にも影響し、
全体を回転させすぎてしまい、行の判別に影響が出てしまいます。
そのために下記の式によるzスコアを利用しました。

$$
Z = \frac{x - \mu}{\sigma}
$$

$ Z $:zスコアの値
$ x $:傾きのデータ値
$ \mu $:データの平均値
$ \sigma $:標準偏差

このzスコアを今回-1から+1の範囲内にあるデータのみを利用し、
この範囲外は外れ値として除外しています。これを実現するコードを次に示します。

zscore.cs

double meanAngle = biases.Average(); 
double stdDev = Math.Sqrt(biases.Average(v => Math.Pow(v - meanAngle, 2))); 
var zScores = biases.Select(v => (v - meanAngle) / stdDev).ToList(); 

var filteredData = biases.Where((x, index) => zScores[index] >= -1 && zScores[index] <= 1).ToList();

最終結果

これらを利用して得られた結果を画像上に要素を四角で囲ったものが、次の画像になります。
回転前と後で画像を出力してみました。画像から、補正前では右肩上がりになっている要素が、
青い四角で書かれたものでは、平行に補正されていることがわかります。
今回画像自体を回転したわけではなく、要素の座標のみを回転させたので、
四角と文字要素がずれてしまっていますが、行の判別には差し支えありません。
今回はすべての要素を同じ回転角で補正していますが、次回以降で折れ曲がりなどを考慮した、
一定の領域ごとに異なる補正を行うことができるような方法を試していきます。

補正後に行ごとにグループ化した結果も次に表示します。
このレシート画像ではすべての行が正確にグループ化されました。

また、これらを利用したOCRは、LINEからどなたでも無料でご利用いただけますので、
ぜひ試してください！

また、OCRのでも体験がこちらのページからできます！

参考

次の記事

次回はまた別のアプローチから補正を行います。
次の記事はこちら！

JSONレシートデータ

今回の内容にかかわっている部分にのみ簡単な説明をつけておきます。

“Status”:
“CreatedDateTime”:
“LastUpdatedTime”:
“Analyzeresult”:
　┣“Version”:
　┣“ModelVersion”:
　┗“ReadResults”:
　　┣“Page”:
　　┣“Language”:
　　┣“Angle”:
　　┣“Width”:入力画像の幅
　　┣“Height”:入力画像の高さ
　　┣“Unit”:
　　┗“Lines”:要素のリスト
　　　┣“Language”:
　　　┣“BoundingBox”:要素全体の四隅の座標
　　　┣“Appearance”:
　　　┃　┣“Style”:
　　　┃　　┣“Name”:
　　　┃　　┗“Confidence”:
　　　┣“Text”:要素の文字列
　　　┗“Words”:要素内の文字のリスト
　　　　┣“BoundingBox”:一文字ごとの四隅の座標
　　　　┣“Text”:文字
　　　　┗“Confidence”: