手書きフォームでの定期的なジャミングの問題

こんにちは、Habr）

この記事では、光学認識技術（OCR、ICR）およびCognitive Technologiesが開発したドキュメントの理解に関する一連の出版物を開始しています。 これらの決定の多くは、10年以上にわたってさまざまな組織で成功裏に実施されており、年金基金のフォーム、パスポートのアンケート、ロシア連邦のズベルバンクの支払い命令、ガスプロムの株主による投票の結果、その他多数の文書の処理を最適化するのに役立ちます。
今日、ビジネス文書を認識するときに解決しなければならない最も複雑で科学的に興味深い問題の1つに関する私たちの話は、干渉を除去するか、「ゴミ」から有用な情報を分離しています。

まず、既知の形式に従って作成された手書き入力のドキュメントについて話していることを確認する必要があります。


セルグリッド

単一細胞

セリフ文字列
図1.親しみやすさの格子の種類

a）

b）
図2.セリフがある場合（a）、通常の干渉を除去した後（b）の塗りつぶしフィールドの例

このような場合、ドキュメント内のデータ入力フィールドの場所は事前に知られており、
ドキュメントのモデル。静的要素（行、行、フィールド見出し）の説明、要素の構成、それらの相対位置、サイズ、およびその他の特性が含まれます。 手書き入力を含む空白の形式のドキュメントの場合、入力フィールドは特別なタイプのグリッドとして作成され、各文字に個別のセルが割り当てられます（親しみやすさ）。
使い慣れたグリッドにはさまざまな種類があります。 実際には、主に3つのタイプの格子が使用されます。セルのグリッドの形、個々のセル、およびセリフのある行の形です（図1）。 それらはすべて、特徴的な長方形構造を持っています（水平線と垂直線で構成されています）。
図2aは、「セリフの列」などの格子を備えた完成した手書きフィールドの例を示しています。 認識システムの観点から見ると、親しみやすさの格子は、本質的にテキストデータに重畳された構造化ノイズであり、多数の認識エラーを生成します。 特に、無相関のソルト/ペッパーノイズとは異なり、重ね合わせたグレーティングにより、トポロジカル文字認識方法が完全に不適切になります。 したがって、これらの「人工」干渉を除去しようとすると、認識の品質が大幅に向上する可能性があります。
サポート要素の正確な位置を知ることで、ほとんどテキストを歪めることなく、サポート要素を抑制することができます。 理論的にはこの情報は既知である（ドキュメントモデルに埋め込まれている）にもかかわらず、実際には多くの場合不完全または不正確です。 フォームの印刷、充填、およびその後のデジタル化のプロセスでは、さまざまな種類の変形（シフト、傾斜、プリンターおよび/またはスキャナーのブローチに関連するわずかな伸縮）およびノイズ信号（スポット、折り紙からの影など）が導入されます。 そのため、グリッドの参照記述は実装に対応していないことがよくあります。長方形の形状プロパティが失われ、セリフ間の周波数などが侵害されます（図3）。


周期性の違反


真直度の歪み
図3.なじみのある格子の変形の例

上記から、サポート要素の正確なローカライズに関連して次の問題が発生します。

• •ラインの直線性の歪み。
• •格子の周期性の違反はよく知られています。
• •入力フィールドに近接した無関係な静的要素の存在（図4）。
• •線分に形態学的に類似した充填要素の存在。

最初の2つの問題は、動的プログラミング手法を使用した典型的な例であるDynamic Time Warping（DTW）アルゴリズムを適用することで解消できます。 おなじみの格子の構造に関する追加の知識、水平および垂直の接続線の接合部の存在の助けを借りて、描画線を注意から除外することが可能です。 このような構造的特徴は、ヒットまたはミスのモルフォロジーフィルターを使用して簡単に検出されます。
これらの2つのツールのアプリケーション上に構築されたサポートラティスローカリゼーションアルゴリズムについて詳しく見ていきましょう。
文書を予備的に識別する方法により、入力フィールドのおおよその領域と、文書全体の角度を決定できます。 残念ながら、画像の変形により、これは個々のフィールドの正確な方向を保証しません。 さらに、アンケートにはいわゆる「オーバープリント」があります。これは、プリンターで適用されるアンケートの可変部分です。 明らかな理由により、オーバープリントフィールドの傾斜は、ドキュメントのグローバルな傾斜と異なる場合があります。 提案された定位アルゴリズムは、「入力で」直接指向の画像を想定しているため、最初のステップはフィールド画像を回転させてその傾斜角を決定することです。 このために、高速ハフ変換に基づくアルゴリズムが使用されます。 さらに、格子の垂直成分を持つ関節の数とタイプに関する知識に基づいて、水平基準線の位置が決定されます。 次のステップは、垂直支持要素の位置です。 結論として、動的計画法を使用して、各セルの水平線の配置が調整されます。
画像の向きを決定するタスクと正確に見つかったラティスを削除するタスクは別のタスクであり、この記事では考慮されていないことに注意してください。
ここで、ラインとジョイントの検索と調整のアルゴリズムをより詳細に検討してみましょう。

既知のジョイントパターンを持つ水平線を検索する

したがって、外部のコントラスト線の背景に対して格子の基準水平線を強調するために、基準線と格子の垂直要素との共役に関する情報に依存することが提案されます。 目的のオブジェクトを最も単純な正規表現-セマンティックシンボルと可能な繰り返しシンボル（「*」）を含む文字列で記述します。 この説明をラインパターンと呼びます。
セマンティック文字として、ジャンクション（たとえば、 '└'、 '┴'、 '┘'）などの文字を使用します。また、ジョイントのない線の存在（ '─'）および線の不在（ '○'）の記号も使用します。 たとえば、図に示されているすべてのフィールドの下の基準線 4、パターン「└─*┴─*┘」で記述され、「単一セル」タイプの格子を持つフィールドは「└─*┘○*└─*┘○*└─*┘...」です。
ここで、ラインジャンクションの中心ピクセルとして画像ピクセルを推定する方法を考えてみましょう。 実際、中央のピクセルの暗さ、およびラインの存在が予想される方向にあるピクセルを評価する必要があります。 さらに、残りの方向ではピクセルが十分に明るいことを確認する必要があります（そうでない場合、すべての検出器は十字形のジョイントに応答します）。さらに、対角線が明るいはずです（そうでない場合、検出器は黒い長方形の角に応答します）。 予想される線の太さに見合ったステップLの規則的な格子のノードにある9ピクセルのパターンを検討します。 図 図5は、ジャンクション「┴」の予想される構成を示しています。 計算が行われるピクセルは、指定されたスキームの中心に対応します。



ここで、検討中の構成に対応するモルフォロジーフィルターを構築します。 ダイアグラム上で白でマークされたピクセルについては、最小値を探し、黒は最大値を探します。 次に、取得した値の差を見つけ、0より小さい場合はゼロを見つけます。Wの結果の値は、このピクセルの目的のジョイントの品質の推定値と見なされます。



他のすべてのタイプのジョイントの検出器も同様に構成され、ジョイントのない直線検出器も同様です。 ライン検出器がないため、構築方法はわずかに異なります。


ここで、Wbgは、パターンのピクセルのいずれかに汚染物質が存在する可能性がある場合に、背景の明るさを評価するという意味があります。

そのため、フィールドの画像に適切なモルフォロジーフィルターを適用すると、各ピクセルに、このピクセルがジョイント、ライン、またはスペースの中心ピクセルにどれだけ見えるかを示す評価のセットが得られます（図5）。

ここで、フィールドの画像の各行について、それが目的のパターンにどれだけ対応しているかを判断し、すべての行の中から最適なものを選択します。 単一行を評価するタスクが動的プログラミングのタスクであることは明らかです。 実際、テーブルを作成します。各列はテンプレートのセマンティックシンボルまたはアスタリスクが後に続くシンボルに対応し、各行は画像行のピクセルに対応します。 列で指定されたジョイントに対応する行で指定されたピクセルを評価することにより、テーブルの各要素を埋めます（表1）。 私たちのタスクは、テーブル内で左端から右端までの重みが最大のパスを見つけることです。ただし、アスタリスクのない列では、対角線上のセルを右下に1つだけ移動でき、アスタリスクのある列では-同じ方法または1つのセル下に移動できます この場合、パスが通過するセルの値の合計がパスの重みと見なされます。 （表1では、最適なパスが青色で強調表示されています。）
画像の各行についてこの問題を順番に解決すると、下部および（このタイプのラティスタイプの場合）上部ラティス基準線の座標が見つかります。


表1.動的プログラミングを使用したパターンの適合性評価の検索の例。

縦線を検索する

格子の垂直線は、水平投影の周波数分析を使用して検索できます。 しかし、プリンターの不完全な紙送りシステムと格子内のブローチスキャナーにより、セリフ間の周波数はしばしば違反されます（図6）。

a） b）

c） d）

図6.フィールド（a）の画像でのジョイント '└'、 '┴'および '─'（b、c、d）の検出結果。

さらに、フォームの開発段階でフィールドセルの数が緊急に増加すると（「Gediminayte-Berzhanskayt-Klausutayt」という名前を突然知ったとき）、追加されたセルのサイズが標準外になります。 問題は、完全なラティスジオメトリの場合でも、顕著な垂直ストロークを持つシンボルのために、多くの誤ったピークが投影に表示されるという事実によって悪化します。
ただし、最後の問題は部分的に軽減することができます。格子の検出のこの段階では水平線の位置がすでにわかっているため、水平軸上の画像全体の投影ではなく、格子の最下線より上であるが最上線より下の部分のみの投影を考慮することができます対応するタイプのグレーティングの場合のセリフの高さ。 これにより、大文字によって形成されるピークが、格子の要素によって形成されるピークを超えないことが保証されます。 さらに、真のピークを強化するために、ヒストグラムに「┴」および「┬」ジョイントの重みを追加するのが妥当です。
推定期間と垂直支持要素間の距離の可能な誤差を知ることで、特定のセクション内のそのような要素の位置について考えられるすべてのオプションをすばやく計算し、最適なオプションを選択できます。 この問題は、動的プログラミングの方法によって十分に解決されます。この場合、テーブルを解決する必要はありません。
ヒストグラムに沿って左から右に移動します。 各ステップで、ヒストグラムのセグメントを考慮します。ここで、xは現在の位置、pは予想期間、Δは最大偏差です。 指定されたセグメントのヒストグラム値から最大値を見つけて現在のセルに追加し、最大インデックスを並列配列に格納します。 次に、取得したヒストグラムのグローバルな最大値は、最後の垂直線の位置に対応し、対応するインデックスは、見つかった行のリストの前の要素を示します。 リストを調べた後、すべての垂直支持要素の位置を復元します。

水平線の位置を修正する

垂直線と水平線を見つけた後、おなじみの格子が形成されたと見なされます。 ただし、グリッド除去アルゴリズムにはピクセル精度が必要であり、印刷およびスキャン段階で用紙を描画する場合、画像にファンの歪みが生じる可能性があります（パスに沿ってシートが回転する場合）。 さらに、フィールド画像の角度を決定するためのアルゴリズムも小さな誤差を引き起こす可能性があります。 次のように問題を提起します：セルからセルへの水平ライン要素の垂直オフセットのシーケンスを見つける必要があります（図3）。ただし、個々のオフセットはkピクセル（通常はk = 1）より大きくすることはできません。
この問題は、動的プログラミングの方法によっても解決されます。
格子の各セルについて、フィールドの高さに等しいサイズ（格子のサイズを超える）の垂直ヒストグラムを収集し、これらのヒストグラムをセルの数に等しい幅のテーブルで埋めます。 テーブルの左から右の境界までのパスを最大化し、右にシフトしたときに、k要素以下だけ上下にシフトできるようにします。 見つかった最大パスは、水平参照線の要素の位置に従います。
これらの2つのツールを使用して、使い慣れた格子の正確なローカライズの問題が解決されました。 比較問題を解決するために開発されたアプローチは、プログラムによって実装され、現在、CTP保険プロファイル、ローン申請、ネットワークマーケティングプロファイルのストリーミング入力に産業的に使用されています。
アルゴリズムの品質は、12,245個のフィールドを含む395個のCTPポリシーで評価されました（表2）。 このセットでは、すべてのフィールドの正しい値が手動で入力され、認識システムが3つのモードで起動されました：ラティス削除サブシステムをオフにし、ナイーブアルゴリズムを有効にし（ヒストグラムの分析のみに依存）、提案したアルゴリズムを使用します。 認識品質は、正しく（単一エラーなしで）認識されたフィールドの割合として測定されました。 システムの2倍の速度低下を犠牲にして、認識の品質を30％から80％に上げることができました。 認識品質が70％未満の文書認識システムは通常、採算が取れないことに注意してください。オペレーターがすべてのフィールドに入力すると、エラーを修正するよりも速くなります。

処理された画像の詳細ビューで示されるように、提案されたアルゴリズムは以下を提供します。

• レイアウトの余分な対照的な線をキャプチャするフィールドの正しい動作。
• 可変セル幅のフィールドの正しい処理。
• 格子の正しい処理は、破損したジオメトリ（ファンの歪みを含む）に慣れています。

表2

このトピックの詳細については、A.Vの記事をご覧ください。 クロプテフ、D.P。 ニコラエフ、V.V。 ポストニコフ。 ロシア科学アカデミーのシステム分析研究所（ISA RAS）の論文集、2013年、V。63、No。3、p。