少し前（ああ、もう1年です！）文書ページの画像を分割するための最新の方法のレビューに誰かが興味を持っているかどうかという質問に対して、私は肯定的な回答を受け取りました（ massimusから）。 そして今日、ついにこのレビューを行うことにしました。



しかし、スタート-小さな余談。 当社製品のテキスト認識システムは非常に簡単に説明できます。 テキストを含むページがあり、それをテキストブロックに解析してから、ブロックを個別の行、行を単語に、単語を文字に、認識した文字に解析し、さらにチェーンに沿ってすべてを収集してページのテキストに戻します。 セグメンテーションのタスクは次のように設定されています。ページがあり、それをテキスト要素と非テキスト要素に分解する必要があります。



さらに、タスクを洗練して洗練することができます（ ここで、問題の正しい定式化はすでにその解決策の半分のステップであるという説明にうんざりしています。安心できます、同僚と上司のためにこれをさらに強くしました ）。 引用された方法の著者であるさまざまな国の科学者は、学問ではなく科学を行いたいため、タスクをより簡単に定式化します。



ページにはテキストと写真があります。 テキストをブロックに分割し、画像を選択する必要があります。



私のインスピレーションの源は、 F。Shafait、D。Keysers、Thの記事でした。 ブリューエル。 ページセグメンテーション用の6つのアルゴリズムのパフォーマンス比較 （以降、著者の名前の最初の文字に従ってSKBと呼びます）。これにより、上記のセグメンテーション手法のほとんどすべての比較評価が得られます。 したがって、すぐに主要なソースを掘り下げたい場合は、それを取得してリンクをたどることをお勧めします。 アルゴリズム自体の説明、詳細、および議論はこちらです。



したがって、テキストをブロックに分割し、写真を選択する必要があります。 ご覧のとおり、表、図、その他の飾りの問題はありません。 さらに、写真はコントラストが高く、2値化されていると想定されることがよくあります。つまり、原則として、モノクロ画像のみで作業することで境界を見つけることができます。



また、研究では「マンハッタン」および「非マンハッタン」レイアウトの概念をよく使用します。 「マンハッタン」は、すべてのブロックの境界が直線であるものです（各ブロックは長方形であるか、いくつかの頂点と辺の一部が共通の複数の長方形で構成されます）。「マンハッタン以外」はそのような制限を満たしません。



まず、マンハッタンのドキュメントで動作するように設計されたいくつかのアルゴリズムを分析します。

スミアリング

これは最も古いアルゴリズムです。おそらく、セグメンテーションのタスクに直面したときに頭に浮かぶのはおそらく最初のことです。 1982年にKY Wong、RG Casey、FM Wahlの記事で最初に説明されました。 文書分析システム。



簡単に言うと、次のように機能します。単語を少し垂直および水平に広げてみましょう。結果として、接続された領域は完成したブロックになります。



もう少し説明すると、次のようになります。

1. RLE表現でページの画像を取得します
2. lT_horzより短い白いRLEストローク（=白いピクセルのシーケンス）を削除します。 画像Image_1を取得します
3. 元の画像を90度回転し、回転した画像のlT_vertより短い長さの白いRLEストロークを削除します。 画像を元に戻し、画像Image_2を取得します
4. ANDイメージImage_1およびImage_2の作成
   
   
5. 結果の画像で、T_Finalより短い白いストロークを削除します
   
   

結果の画像の関連領域は、事前に作成されたブロックです。 テキストと非テキストに分割する必要があります。 1982年には、機械学習ツールのような兵器庫はまだありませんでしたが、それらがなければ困難でした-決定木は手動で描かれました。



これが中間画像と最終ブロックの外観です：







元の記事では、著者は240 dpiの解像度の画像で作業し、値T_horz = 300 T_vert = 500およびT_final = 30を選択しました。やや予期せず、値が非常に大きくなりました（T_vertフック付き2インチ）、明らかにこれは何が行われているためですそして。



アルゴリズムの利点は理解できます-それは単純で、RLEイメージとそれだけで動作するため、高速です。 入力ドキュメントが「マンハッタン」であるという事実にアルゴリズムが明示的に依存している場所はありません。 ただし、考えてみると、アルゴリズムはマンハッタン以外では機能しません。以下の例では、テキストは画像に固定されます。







本当に悪いニュースは、「マンハッタン」ドキュメントでは、テキストと「非テキスト」の接着も非常に頻繁に行われるということです。これはSKBで通知されます。

再帰的XYカット

数年後の1984年に、再帰XYカットと呼ばれるより高度なページセグメンテーション方法が説明されました。 G. NagyとS. Sethで説明されています。 「光学的にスキャンされたドキュメントの階層表現」であり、90年代に積極的に開発されました。



この方法は、マンハッタンのドキュメントにのみ適していると既に明示されています。 この方法の本質は、ページをブロックに交互に分割し、ブロックを垂直または水平に分割することです。 つまり、アルゴリズムは次のようなものです。

• ページの準備、小さな破片からのクリーニング
• 接続エリアを選択します。 突然誰かがそのような関連付けを安全に構築する方法を知っていれば、それらを少し組み合わせて言葉のようなものを得ることができます。 しかし、この投稿のフレームワークでは、それらを「接続エリア」と呼びます。
• アルゴリズムのグローバルパラメータ、たとえばシンボルの中央の高さと幅を計算します。

次に、ページ全体から始めて、アルゴリズムを再帰的に実行します。

• ブロックを垂直または水平セクションで分割する方法を探しています。
• 可能であれば、各部分の分割を繰り返し、分割を開始します。
• できなかったら、やめてください。

ブロックの分割方法に関する段落について。 2つの方法が提案されています-ホワイトクリアランス（それぞれ、水平軸または垂直軸へのブロックの投影で見つけることができます）または長くてかなり絶縁された黒い直線のいずれかです。



これらすべての分割の結果として、図の右下のように、木の構造が得られます。







元の記事の著者は、このツリービューを主なメリットと考えているようです。 彼らは、マンハッタンのドキュメントであっても、このアルゴリズムが目標を達成できない可能性があることに気付きました。たとえば、ブロックがこのように配置されている場合







率直に言って、最も一般的な構成ではなく、新聞でも、雑誌やオフィス文書は言うまでもありません。 しかし、確かに新聞に載っています。



それにもかかわらず、アルゴリズムのより深刻な問題は、しきい値への提出です。 そのような断片について、タイトルを壊さずにテキストからタイトルを分離することは難しいとしましょう：







そして、ここでは、距離によるしきい値のみに依存して、画像をテキストから分離することは非常に困難です：







もちろん、この投稿で示されているすべてのアルゴリズムに共通する問題も関連しています-番号付きリストから番号付けを引き裂かないようにする方法と、冒頭で示した制限（テキストとコントラストの高い画像のみがある）を取り除く方法

最大の白い長方形を使用したセグメンテーション

次に、最大の白い長方形を使用してページをセグメント化するアイデアについて説明します。 「最大の白い長方形」とは何ですか？ 白は、黒のドットが含まれていないことを意味します（最初に画像を小さな破片から廃棄する必要があることは明らかです）。 最大-左、右、上、下のいずれにも増やせないため、白のままになりません。 次に、黒い点の代わりに、接続領域を検討します。 再帰セクションのように、それらを何らかの方法でグループ化できますが、ここでも停止しません。 スキャンされるほぼすべてのページに、このような白い長方形が数万個あることは明らかです。 ただし、セグメンテーションの目的では、最大のもののみが必要になる場合があります。 彼らの検索のアルゴリズムは、Thomas M. Breuelの記事で提案されました。 レイアウト分析のための2つの幾何学的アルゴリズム







最大の白い長方形を見つけるタスクに戻りましょう。 長方形の「品質」の概念を紹介できます。



r1⊆r2 Q（r1）<= Q（r2）が満たされている場合、つまり、ある長方形が別の長方形の内側にある場合、内部の品質は外部の品質より大きくなることはできません。 単調な性質には多くのものがあります。 面積は良いです。 周囲は良好です。 高さの正方形と幅の正方形が適切です。 一般に、十分なファンタジーがあります。



品質が単調な場合、次のアルゴリズムを適用して、品質の高い順に最大の白い長方形を検索します。

• 長方形の優先順位でキューを開始します。 優先度は品質と同等です。
• ページ全体の長方形をキューに入れます。 彼は間違いなく最初です。

さらにループ内：

• キューから長方形を取得します。 空の場合、これは別の最大の白い長方形です。
• そうでない場合は、調査対象の四角形内の接続された領域から、1つの「サポート」領域を選択します（QSortの中央値と同様）。 チャンスに頼るのではなく、より中心的なものを意識的に選択する方が良いでしょう。
• 最大の白い長方形は、この領域の完全に上、または完全に下、またはその右側または左側（下図の緑色の長方形）のいずれかになります。
• 緑の長方形をキューに追加します。

ループを終了する条件は、見つかった十分な数の長方形か、キューから取り出された現在の長方形の品質のいずれかです。十分な空想があります。



さて、最大の白い長方形が見つかりました。 それらでさらに何ができるかを見てみましょう。



同じ記事で、Thomas M. Breuelは実際にこのトピックを気にせず、分析全体が4つのステップで行われると書いています。

1. すべての高い最大の白い長方形を見つけ、列間セパレーターの候補として評価します
2. 見つかった列構造に従って、行を見つけます
3. 見つかった行を見て、段落、見出し構造、フッターを見つけます
4. 幾何学的情報と言語情報の両方を使用して読み取り順序を復元する

このホワイトペーパーの後半では、白い長方形を分類する方法について、いくつかの合理的な考慮事項について説明します。 評価関数にはそれほど多くの欠点がないことを認めます-ここでは、評価の不正確さよりもメソッドの制限に直面します。



ヘンリー・ベアードは、作品イメージの背景構造で、少し異なるアプローチを説明しています。 この作業では非常に興味深いアルゴリズムについて説明しますが、一部の関数の実装により、特定の実験に基づいて特別に「微調整」されるという感覚が残ります。 そのため、見つかったすべての最大の白い長方形を優先キューに入れることが提案されています。 私は特定の優先機能を与えません、あなたは作品を見ることができます。 直観的には、長方形の面積が大きく、長方形が高いほど、優先度が高くなります。



次に、特別なリストLにそれらのいくつかを配置するために、このキューから長方形を削除します。削除された各長方形にトリミングルールを適用します。この長方形がリストLのいくつかの要素と交差する場合、すでに処理されて残っているものから減算し、キューに戻します。 それ以外の場合は、リストLに追加します。サイクルを終了するための条件は、ややトリッキーです（優先順位のしきい値を示すだけですが、作成者はより困難です）。



リストLのすべての長方形をページから切り取り、画像内の残りの接続領域を既製のテキストまたは画像ブロックとして宣言します。



最大の白い長方形の簡単な要約として、最大の白い長方形は非常に重要な概念であり、ページのセグメンテーションの問題を解決するのに非常に役立つと言えます。 SKBの実験によると、ここで紹介するアルゴリズムは両方とも、再帰セクションとスミアリングの両方でより適切に機能します。 与えられたアルゴリズムでは、より複雑な概念は言うまでもなく、写真でさえ「隠されている」ことは別の問題です

非マンハッタンレイアウト

マンハッタン文書のいくつかのアルゴリズムを分析しました。 しかし、この種の文書に出会ったらどうなるでしょう：







まあ、具体的にはこれに対する答えは非常に単純です-それはドキュメントではなく、トイレの壁紙に過ぎないので、ドキュメント処理プログラムがこの写真をどう処理するかはそれほど重要ではありません。



真剣に言えば、「非マンハッタン」レイアウトはそれほどエキゾチックなものではなく、新聞や雑誌、場合によっては本にも見られます。 典型的な新聞の例を次に示します。







以下では、「非マンハッタン」ドキュメントに対処できる2つのアルゴリズムを分析します。

Docstrum

Docstrumという語は、Portmanteau語のキャロル生産モデルによって形成されます-DocumentとSpectrum（このモデルが大好きです）という言葉を結び付け、「非マンハッタン」文書のセグメンテーションのアルゴリズムを示します。 O'Gormanは、1993年の記事「ページレイアウト分析のドキュメントスペクトル」で説明しました。 この方法自体は、スキャナー上で完全に位置合わせされているのではなく、わずかな角度でページ用に考案されました。 このアルゴリズムの仕組みを説明します。



開始するには、小さなゴミと明らかにテキストではない大きなオブジェクトを削除してページを準備します（まあ、またはページに写真がないことを装います-初めてですか？）。 ページに残っているのは文字だけだと信じています。 これらの文字のサイズをクラスタリングします（著者は正確に2つのクラスターを提案しましたが、この方法を使用した人は3つ、4つ、またはそれ以上を試しました）。 同じ文字列からの最近傍の各文字からk（通常は4または5に等しいkを取る）までの距離を見てみましょう。 距離をヒストグラムに記録します。 ヒストグラムの最初の3つのピークを見てみましょう。 最小のピークは単語内の文字間の距離、2番目は行間、3番目はスペースであると主張されています。 この仮定を使用すると、バイアスを修正できます。



ページのセグメンテーションでは、近いコンポーネントで推移的なクロージャーを作成します-行内の単語を結合し、行を閉じると、既製のブロックが得られます。



このメソッドは「非マンハッタン」ドキュメントで機能するものとして位置付けられているという事実に加えて、重要なアイデアを明示的に使用しています。 私は、決定が依存する距離のしきい値（2つの単語を1つのブロックに入れるかどうか）が単語の高さに応じて選択されるプロパティを意味します。 これは、この方法が、研究者によって繰り返し言及されている「大きなフォントの過剰なセグメント化」の問題に定期的に対処する機会があることを意味します。



一方、ここで著者は、写真やより複雑なオブジェクトをどうするかという疑問を巧みに隠しました。 また、距離のしきい値のみに依存するというアイデアの他の欠点については、既に説明しました。

ボロノイ図

ボロノイ線図は興味深いオブジェクトであり、平面上の任意の点のセット（この場合は文字の中心）で構成されます。 ボロノイ図が作成されるポイントは、ここでは参照ポイントと呼ばれます 。 これは、プレーンの領域への分割です。 各領域は1つの基準点に対応し、この基準点が他の基準点よりも近い平面内の点のセットです。 ボロノイ図と他の奇妙なオブジェクトであるDelaunay三角形分割との関係に関する詳細情報は、 Wikipediaへのリンクから読むのが最も簡単です。



それらを構築する方法については、 A.Vで読む価値があります。 Skvortsova「ドロネー三角形分割とその応用」 1998年のK. Kise、A。Sato、およびM. Iwataによる記事についてお話します。 面積ボロノイ図を使用したページ画像のセグメンテーション。 つまり、ボロノイ図がセグメンテーション問題の解決にどのように適用されたかです。 ところで、今日、この方法は「科学的標準」と見なされていますが、科学はこれよりもよく認識されるアルゴリズムを提案していません。 はい、そしてSKBで、著者はボロノイ図が白い長方形、Docstrum、および再帰セクションの品質において著しく進んでいると書いています。



したがって、通常のジェスチャーで、ゴミの画像をクリアし（すべて、この投稿の最後のときは本当に簡単だと思います）、残りの接続されたエリアの中心を参照ポイントとして宣言し、それらにボロノイ図を作成します。 次に、ダイアグラムのどのセルを結合するかをマークします。 2つのケースでセルを結合します。

1. または、基準点（接続されたコンポーネントの中心）間の距離dがしきい値T1未満です。 しきい値T1は、このルールが単語内の隣接する文字の組み合わせを処理するように選択されます。
2. または、dの場合、次の関係が成り立ちます：d / T2 + ar / Ta <1ここで、arは、より小さな接続領域の面積に対するより大きな接続領域の面積の比率（つまり、ar> = 1）であり、T2とTaはさらに2つのしきい値です。 この条件の意味は、2つの単語を1つの行に結合する価値があるということですが、これら2つの単語の高さが異なる場合は、セルをより慎重に結合する必要があります。

結合する必要のあるすべてのセルを見つけたら、それらを結合します-そして、ボロノイ図はすぐに使用できるセグメンテーションに変わります。



将来、さまざまな研究者がボロノイ図の操作を改善しようとしました。 たとえば、Voronoi ++による2009年の記事：VoronoiおよびDocstrumの機能に基づいた動的ページセグメンテーションアプローチでは、著者のM. AgrawalとD.Doermannが、Docstrumと別の奇妙なソーサリーを使用してしきい値T2をより正確かつより正確に取得する方法について説明しています。 ここでは、この「改善主義」について詳しくは述べませんが、ボロノイ図に基づいたセグメンテーションアルゴリズムの開発に関する記事の存在、さらには、David Doermannなどの著名な科学者によって書かれたものも、風が吹いている場所を示唆しています。



ボロノイ線図の欠点もまた同じです-制限はしきい値のみに依存し、写真とのあいまいさは同じです。 この方法の間違いない利点は、選択する必要がある3つのパラメーターのみが含まれているという事実にあります。これらのパラメーターは明示的に示されています。



これで、ページのセグメンテーションに関連する科学的成果についての私のレビューは終わりです。 そして、科学はまだその言葉を言うと思います:)