【誤訳訂正書】
【提出日】平成21年1月29日(2009.1.29)
【誤訳訂正１】
【訂正対象書類名】特許請求の範囲
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【特許請求の範囲】
【請求項１】
ピクセルから成る複合画像を、画像のレイアウト要素に対応する複数のフィールドに分割する方法であって、前記ピクセルが、画素の強度および／または色を示す値を有し、
画像の隣り合うピクセルの領域に対応し且つ画像のバックグラウンドを示す所定の特性を有するフィールドセパレータを見出すステップを含み、前記分割する方法がさらに、
少なくとも１つの分離方向に沿って画像の外側の境界まで前記フィールドセパレータを延長するステップと、
前記延長されたフィールドセパレータに対応するラインのテセレーショングリッドを構成するステップと、
前記テセレーショングリッドのラインによって囲まれる領域である基本長方形のセットを構成するステップと、
互いに隣り合い且つ１つのフィールドセパレータによって分離されない基本長方形同士を連結することによりフィールドを構成するステップとを含むことを特徴とする方法。
【請求項２】
基本長方形のセットを構成する前記ステップが、要素の２次元配列によって前記テセレーショングリッドを表わすマトリクスマップを構成することを含み、各要素は、テセレーショングリッドの基本長方形またはラインセグメントのいずれかを表わし、１つの要素が、フィールドセパレータに対応するラインを表わすための所定の第１の値、または基本長方形あるいは延長されたフィールドセパレータに対応するラインを表わすための更なる異なる値を有している、請求項１に記載の方法。
【請求項３】
フィールドを構成する前記ステップが、前記更なる異なる値を有するマトリクスマップ内の要素同士を連結することを含む、請求項２に記載の方法。
【請求項４】
前記フィールドセパレータが連結する点でノードが規定され、フィールドを構成する前記ステップが、前記テセレーショングリッドに対応し且つ前記テセレーショングリッド内のノードを示す要素を含むノードマトリクスを構成することを含む、請求項１から３のいずれか一項に記載の方法。
【請求項５】
フィールドを構成する前記ステップが、マトリクスマップ内の連結された要素の各領域毎に外形を構成し、該外形を前記ノードマトリクス上に描出することによりフィールドを規定するノードを見出すことを含む、請求項４に記載の方法。
【請求項６】
前記外形が、前記領域を拡張して、拡張された領域の領域を取り去ることにより構成される、請求項５に記載の方法。
【請求項７】
分割が、画像のバックグラウンドを示す所定の特性を有する隣り合う領域に対応する辺と、辺が接続する頂点とを有するグラフを構成するとともに、前記フィールドセパレータを前記グラフの辺に関連付け、かつ
前記フィールドセパレータを画像の外側の境界まで延長することにより、前記テセレーショングリッドを形成することを含む、請求項１から６のいずれか一項に記載の方法。
【請求項８】
グラフを構成するステップが、２つ未満の辺に連結される頂点を除去することにより、かつ／または２つ未満の辺に連結される頂点に連結する任意の辺を除去することにより、前記グラフをクリーニングすることを含む、請求項７に記載の方法。
【請求項９】
前記テセレーショングリッド内のラインを２つの直交する分離方向でのズレを無くす、すなわちスナッピングすることを含む、請求項１から８のいずれか一項に記載の方法。
【請求項１０】
ピクセルから成る画像を複数のフィールドに分割するためのコンピュータプログラム製品であって、請求項１から９のいずれか一項に記載の方法をプロセッサに実行させるようにプログラムが動作する、コンピュータプログラム製品。
【請求項１１】
ピクセルから成る複合画像を、画像のレイアウト要素に対応する複数のフィールドに分割する装置であって、前記ピクセルが、画素の強度および／または色を示す値を有し、前記分割する装置が、
画像を入力するための入力ユニット（９１）と、
隣り合うピクセルの領域に対応し且つ画像のバックグラウンドを示す所定の特性を有するフィールドセパレータを見出す処理ユニット（９４）とを備え、
前記処理ユニット（９４）が、
少なくとも１つの分離方向に沿って画像の外側の境界まで前記フィールドセパレータを延長し、
前記延長されたフィールドセパレータに対応するラインのテセレーショングリッドを構成し、
前記テセレーショングリッドのラインによって囲まれる領域である基本長方形のセットを構成し、
互いに隣り合い且つ１つのフィールドセパレータによって分離されない基本長方形同士を連結することによりフィールドを構成するように、構成されていることを特徴とする装置。
【請求項１２】
前記処理ユニット（９４）が、
要素の２次元配列によって前記テセレーショングリッドを表わすマトリクスマップを構成し、各要素が、テセレーショングリッドの基本長方形またはラインセグメントのいずれかを表わし、１つの要素が、フィールドセパレータに対応するラインを表わすための所定の第１の値、または基本長方形あるいは延長されたフィールドセパレータに対応するラインを表わすための更なる異なる値を有するように構成されている、請求項１１に記載の装置。
【請求項１３】
前記処理ユニット（９４）が、
前記テセレーショングリッドに対応し且つ前記テセレーショングリッド内のノードを示す要素を含むノードマトリクスを構成するように構成されている、請求項１１または１２に記載の装置。
【請求項１４】
分割後に画像のフィールドを表示するディスプレイユニット（９３）を備えている、請求項１１から１３のいずれか一項に記載の装置。
【誤訳訂正２】
【訂正対象書類名】明細書
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【発明の詳細な説明】
【発明の名称】最小領域による合成画像の分割
【技術分野】
【０００１】
本発明は、ピクセルから成る複合画像を、画像のレイアウト要素に対応する複数のフィールドに分割する方法に関し、前記ピクセルが、画素の強度および／または色を示す値を有し、この方法は、画像の隣り合うピクセルの領域に対応し且つ画像のバックグラウンドを示す所定の特性を有するフィールドセパレータを見出すステップを含む。
【０００２】
また、本発明は、ピクセルから成る複合画像を、画像のレイアウト要素に対応する複数のフィールドに分割する装置に関し、前記ピクセルが、画素の強度および／または色を示す値を有し、この装置は、画像を入力するための入力ユニットと、隣り合うピクセルの領域に対応し且つ画像のバックグラウンドを示す所定の特性を有するフィールドセパレータを見出す処理ユニットとを備える。
【０００３】
更に、本発明はコンピュータプログラム製品に関する。
【背景技術】
【０００４】
ページ分割方法は、１９９４年１０月９日から１２日にイスラエルのエルサレムで行なわれたパターン認識に関する第１２回国際会議の議事録、ＩＥＥＥ−ＣＳプレス、第２刊、３３９頁から３４４頁における、Ａ．ＡｎｔｏｎａｃｏｐｏｕｌｏｓおよびＲ．Ｔ．Ｒｉｔｃｈｉｎｇｓによる文献、「Ｆｌｅｘｉｂｌｅ  ｐａｇｅ  ｓｅｇｍｅｎｔａｔｉｏｎ  ｕｓｉｎｇ  ｔｈｅ  ｂａｃｋｇｒｏｕｎｄ（バックグラウンドを使用するフレキシブルなページ分割）」によって知られている。画像は、画素の強度および／または色を示す値を有するピクセルによって表わされる。この値は、バックグラウンド（通常、白）またはフォアグラウンド（通常、印刷スペースである黒）として分類される。ページ上の印刷領域を取り囲む白色のバックグラウンドスペースが、解析される。バックグラウンド白色スペースは、タイル、すなわちバックグラウンドピクセルの重なり合わない領域によって覆われる。
【０００５】
画像内のフォアグラウンドフィールドの外形は、それを取り囲む白色タイルに沿ってトレースすることにより識別され、これにより、タイルの内側の境界が、更なる解析のためのフィールドの境界を構成する。この方法の問題は、効率的な更なる解析を妨げる複雑な記述によってフィールドの境界が表わされているという点にある。
【０００６】
【特許文献１】米国特許第５，８５６，８７７号明細書
【非特許文献１】Ａ．ＡｎｔｏｎａｃｏｐｏｕｌｏｓおよびＲ．Ｔ．Ｒｉｔｃｈｉｎｇｓ、「Ｆｌｅｘｉｂｌｅ  ｐａｇｅ  ｓｅｇｍｅｎｔａｔｉｏｎ  ｕｓｉｎｇ  ｔｈｅ  ｂａｃｋｇｒｏｕｎｄ（バックグラウンドを使用するフレキシブルなページ分割」、パターン認識に関する第１２回国際会議の議事録、ＩＥＥＥ−ＣＳプレス、１９９４年１０月９日−１２日、イスラエル、エルサレム、第２刊、ｐ３３９−３４４
【非特許文献２】Ｋ．Ｙ．Ｗｏｎｇ、Ｒ．Ｇ．Ｃａｓｅｙ、およびＦ．Ｍ．Ｗａｈｌ、「Ｄｏｃｕｍｅｎｔ  ａｎａｌｙｓｉｓ  ｓｙｓｔｅｍ（文書解析システム）」、ＩＢＭ  Ｊ．Ｒｅｓ．、Ｄｅｖ  ２６、（１９８２）、ｐ６４７−６５６
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の目的は、信頼性が高く複雑でない画像分割方法および装置を提供することである。
【課題を解決するための手段】
【０００８】
本発明の第１の態様によれば、前記目的は、冒頭の段落に規定された方法であって、少なくとも１つの分離方向に沿って画像の外側の境界までフィールドセパレータを延長するステップと、延長されたフィールドセパレータに対応するラインのテセレーショングリッドを構成するステップと、テセレーショングリッドのラインによって囲まれる領域である基本長方形のセットを構成するステップと、互いに隣り合い且つ１つのフィールドセパレータによって分離されない基本長方形同士を連結することによりフィールドを構成するステップとをさらに備えていることを特徴とする方法によって達成される。
【０００９】
本発明の第２の態様によれば、前記目的は、冒頭の段落に規定された装置であって、少なくとも１つの分離方向に沿って画像の外側の境界までフィールドセパレータを延長し、延長されたフィールドセパレータに対応するラインのテセレーショングリッドを構成し、テセレーショングリッドのラインによって囲まれる領域である基本長方形のセットを構成し、互いに隣り合い且つ１つのフィールドセパレータによって分離されない基本長方形同士を連結することによりフィールドを構成するように、処理ユニットが構成されていることを特徴とする装置によって達成される。
【００１０】
本発明の第３の態様によれば、前記目的は、前記方法を実行するためのコンピュータプログラム製品を用いて達成される。
【００１１】
通常、画像は、フィールドセパレータを含む、このフィールドセパレータは、少なくとも２つの分離方向、一般には水平方向および垂直方向のうちの１つを有し、且つテキストフィールド等のレイアウト要素を連結しかつ／または横断しともに取り囲む。本方法の結果、外側の境界へのフィールドセパレータの延長に基づくラインにより、テセレーショングリッド（ｔｅｓｓｅｌｌａｔｉｏｎ  ｇｒｉｄ）が形成される。グリッドによって囲まれるが小分割されない全ての領域が、基本長方形と称され、これらの基本長方形に関して更なる解析が行なわれる。基本長方形のセットの利点は、基本長方形を連結することによりフィールドを簡単に構成することができるという点である。なお、基本長方形のレベルに関する演算は、コンピュータで行なうと、個々のピクセル同士または小さなピクセルを基本とするオブジェクト同士を連結する場合よりも、実質的に効率的である。
【００１２】
本発明は、以下の認識に基づいている。分割は、関連する階層レベルで画像内のオブジェクトを識別する処理である。例えば、新聞の一面において、階層レベルが最も低いものはピクセルであり、その次にレベルが低いものは、連結されたピクセルから成るオブジェクト（例えば、文字またはセパレータ）であり、その次がテキストラインであり、その次がテキストフィールドであり、その次がコラムであり、最後が記事である。発明者らは、構造化された画像内でフィールドを見出す場合には、フィールドセパレータの低いレベルからビルディングブロックレベルへの変換により、フィールドの所要レベルを下回るビルディングブロックを構成できることが分かった。基本長方形は、テセレーショングリッドによって効率的に構成することができるビルディングブロックである。基本長方形を１つの領域に連結するステップは、ビルディングブロックレベルで行なわれる。最後に、ビルディングブロックレベルからフィールドレベルへの変換は、画像のノードまたはフィールドセパレータの当初の連結点に基づいて、複数の基本長方形をフィールドに統合することにより行なわれる。したがって、基本長方形の構成は、主に多角形のフィールドを有するデジタル画像を分割する最中に、フィールドのビルディングブロックを決定するという便利な方法を与える。
【００１３】
この方法の一実施形態において、基本長方形のセットを構成するステップは、要素の２次元配列によってテセレーショングリッドを表わすマトリクスマップを構成することを含み、各要素は、テセレーショングリッドの基本長方形またはラインセグメントのいずれかを表わし、１つの要素は、フィールドセパレータに対応するラインを表わすための所定の第１の値、または、基本長方形あるいは延長されたフィールドセパレータに対応するラインを表わすための更なる異なる値を有している。利点は、マトリクスマップが、基本長方形と基本長方形同士の間の境界とを含んでいるという点である。マトリクスマップは、簡単に処理することができる。これは、そうでなければ、演算を複雑にしかねない幾何学的な内容を伴うことなく、マトリクスマップが、フィールドのビルディングブロックのレベルで画像を表わしているためである。
【００１４】
この方法の一実施形態において、ノードは、フィールドセパレータが連結する位置、およびテセレーショングリッド内の対応する位置にあるオリジナル画像の点で規定される。また、フィールドを構成するステップは、テセレーショングリッドに対応し且つテセレーショングリッド内のノードを示す要素を含むノードマトリクスを構成することを含む。
【００１５】
利点は、ノードマトリクスが、幾何学的な表示でノードへの参照を含んでいるという点である。ノードマトリクスにより、フィールドのビルディングブロックすなわち基本長方形のレベルを、ノードによってフィールドの表示へと簡単に変換することができる。
【００１６】
本発明に係る装置の更に好ましい実施形態が、別の請求項に記載されている。
【００１７】
本発明のこれらの態様および他の態様は、以下の説明に一例として記載された実施形態および添付図面を更に参照することにより、明らかとなり、解明される。
【００１８】
図面は、概略図であり、一定の縮尺で描かれたものではない。図面において、既に説明した要素に対応する要素が、同じ参照符号で示されている。
【発明を実施するための最良の形態】
【００１９】
図１は、知られている分割システムによる３つの基本的なステップを有する典型的な分割方法の概略を示している。入力画像１１は、連結成分解析を使用して画像のピクセルを解析するＣＣＡ（Ｃｏｎｎｅｃｔｅｄ  Ｃｏｍｐｏｎｅｎｔ  Ａｎａｌｙｓｉｓ）モジュール１４で処理される。最初に、白黒文書、グレースケール文書、またはカラー文書、例えば新聞の一面であっても良いオリジナル画像が、好ましくはグレースケールで走査される。このグレースケール走査された画像は、フォアグラウンド値（例えば黒）またはバックグラウンド値（例えば白）を各ピクセルに割り当てるため、ハーフトーン化される。ＣＣＡモジュール１４は、同様の特性を有する隣り合うピクセルの連結成分（Ｃｏｎｎｅｃｔｅｄ  Ｃｏｍｐｏｎｅｎｔ、ＣＣ）を検出することにより、画像中のフォアグラウンド要素を見つける。分割処理におけるこの第１のステップの例は、例えばＵＳ５，８５６，８７７に記載されている。ＣＣＡモジュールは、連結されたフォアグラウンドピクセルの連結成分であるＣＣオブジェクト１２を出力として形成する。ＬＡ（Ｌａｙｏｕｔ  Ａｎａｌｙｓｉｓ）モジュール１５は、ＣＣオブジェクト１２を入力として受け、レイアウトオブジェクト１３を形成する。この場合、ＣＣオブジェクトを統合してグループ化することにより、テキストラインおよびテキストブロック等の大きなレイアウトオブジェクトが形成される。この段階中においては、ヒューリスティックス（経験則）を使用して、レイアウト要素をグループ化し、大きなレイアウト要素を形成する。これは、通常のボトムアップ処理における論理ステップである。ＡＦ（Ａｒｔｉｃｌｅ  Ｆｏｒｍａｔｉｏｎ）モジュール１６は、レイアウトオブジェクト１３を入力として受けて、記事形成（ａｒｔｉｃｌｅ  ｆｏｒｍａｔｉｏｎ）により出力として記事１７を形成する。このモジュールにおいては、大きなエンティティを構成する幾つかのレイアウトオブジェクトが、一緒になってグループ化される。大きなエンティティは、オリジナル画像に適用されるレイアウトルールを使用してアセンブルされる。例えば、新聞の一面において、ＡＦモジュールは、その特定の新聞様式のレイアウトルールにしたがって、テキストブロックおよび画像のようなグラフィック要素をグループ化し、個々の記事を形成する。例えば西洋タイプの雑誌のレイアウト、科学のテキストのレイアウト、または日本の記事のレイアウトといった画像のレイアウトタイプの知識は、ルールに基づいた記事形成方法において使用でき、これにより、テキストブロックのグループ化を向上させることができる。
【００２０】
本発明によれば、以下に説明するように、分割に対して複数の更なるステップが加えられる。これらのステップは、画像を複数のフィールドに分割した後、１つのフィールド内で要素を検出すること、すなわち、更に小さい相互に関連する別個の項目によって構成される、レイアウトオブジェクトを形成することに関するものである。図２は、サンプルとしての日本の新聞を示している。このような新聞は、水平方向読み方向２２および垂直方向読み方向２１の両方を有するテキストラインを含む、特定のレイアウトを有している。検出された連結成分の従来のボトムアップグループ化処理における問題点は、グループ化をどの方向で進めるべきかが分からないという点である。そのため、バックグラウンドを処理してその頁（一面）のフィールドを検出する別個のステップにより、分割が増大される。その後、文字のグループ化を行なう前に、日本の新聞の各フィールドにおける読み方向が検出される。
【００２１】
この方法の一実施形態においては、例えば個々のコラムにおける黒ライン２３といったセパレータ要素が検出されて、複数のバックグラウンド要素に変換される。このような選択肢を用いれば、実際に連結される垂直および水平ラインを含む黒ライン２３の大きな要素を、様々なセパレータ要素に分離することができる。日本の新聞において、ラインは、レイアウトにおいてフィールドを分割するための非常に重要なオブジェクトである。これらのオブジェクトが、分離方向に沿うラインとして認識されることが求められる。この選択肢が無いと、これらのオブジェクトはグラフィックスとして分類される。この選択肢を使用すると、ラインを、様々な方向のセパレータ要素として、各分離方向毎に個別に扱うことができる。
【００２２】
図３は、オブジェクトを１つの方向に統合する基本的な方法を示している。この図は、知られている方向に向けられたレイアウトオブジェクト、例えば読む順番が分かっている状況におけるテキストブロックを見つけるためのＬＡモジュール１５の基本的な機能を示している。連結成分１２は、統計的な解析により最初の解析ステップ３１で処理され、これにより、算定閾値３２が得られる。２番目の分類ステップ３３においては、ＣＣ分類が補正され、これにより、補正された連結成分３４が得られる。この補正された連結成分が、３番目の統合ステップ３５で処理されることにより、文字がテキストラインに加えられ、その結果、テキストラインおよび他のオブジェクト３６が得られる。４番目のテキスト統合ステップ３７においては、テキストラインが、テキストブロック３８（および、可能であれば他のグラフィックオブジェクト）に加えられる。日本の新聞に関する要求事項に基づいて、従来のオブジェクトの統合は、少なくとも２つの読み方向に沿っていなければならず、そのため、前述した基本的な方法を改良しなければならない。
【００２３】
図４は、オブジェクトの分割および２方向統合を示している。図３の１方向処理に対して、新たな別個のステップが加えられている。最初の（前）処理ステップにおいては、画像のグラフ４１が構成される。フィールドセパレータを見つけることによりグラフを構成することについて以下に述べる。グラフにおいて、フィールドは、フィールド検出ステップ４２で、グラフの辺によって囲まれる領域を見出すことにより検出される。当該領域は、テキストブロック４７を含むフィールドとして分類される。テキストブロック４７において（テキストブロック領域内にある補正されたみ連結成分３４または連結成分４３を使用して）、ステップ４４で、読む順番４５が決定される。読み方向検出は、文書スペクトルに基づいている。テキストブロック４７のフィールド、含まれている連結成分４３、および読む順番４５を入力として使用して、ライン形成ステップ４６は、必要に応じて、見出された方向に沿って文字をラインに加える。
【００２４】
ここで、グラフ４１の構成について説明する。文書のグラフ表示は、走査のバックグラウンドを使用して形成される。走査におけるピクセルは、バックグラウンドとして（通常、白）或はフォアグラウンド（通常、黒）として分類される。白の大きな領域だけが、フィールドに関する情報を与えるため、例えば画像をダウンサンプリングすることにより、小さなノイズオブジェクトが除去される。１つのフォアグラウンド（黒）ピクセルを除去するため、更に、ダウンサンプリングされた画像から斑点が除去されても良い。
【００２５】
次の作業は、重要な白領域を抽出することである。最初のステップは、隣り合うバックグラウンドピクセルの１ピクセル高領域、所謂ホワイトランを検出することである。所定の最小長よりも短いホワイトランは、処理から除外される。
【００２６】
図５は、一例として、垂直方向で隣り合う白ピクセルの４つの水平方向のホワイトラン５１を示している。フォアグラウンド領域５３は、ホワイトラン５１を直接に取り囲むフォアグラウンドピクセルを有していると仮定される。「最大白長方形」は、隣り合うホワイトラン５１によって構成することができる最も大きな長方形領域、したがって、黒（フォアグラウンド）ピクセルを含んでいると延長することができない長方形白領域として規定される。最大白長方形５２は、垂直方向の破線によって示される長さ、及び４ピクセル分の幅を有する４つのホワイトラン５１に基づいて示されている。白長方形は、これを延長することができない場合に、いわゆる最大分離力を有する。そのような長方形は、より重要な白領域の更に小さい部分ではない。したがって、長方形５２は、４ピクセル分の幅を有する考えられる唯一の最大長方形である。３ピクセル分または２ピクセル分の幅を持つ更なる長方形を構成することができる。更なる例が図６に示されている。
【００２７】
白長方形の構成は、例えば水平方向および垂直方向の白長方形といったように、異なる分離方向で別個に行なわれる。垂直方向の白長方形は、画像を回転させ、且つ回転された画像における水平方向のホワイトランを検出することにより検出される。なお、画像のタイプまたは用途に応じて、斜め方向等の他の分離方向が選択されても良いこと留意されたい。
【００２８】
最大白長方形を構成するためのアルゴリズムは、以下の通りである。アルゴリズムの入力は、所定の画像から検出された全ての水平方向の１ピクセル高ホワイトラン（Ｗｈｉｔｅ  Ｒｕｎ、ＷＲ）から成る。各ホワイトランは、一組の座標（（ｘ１，ｙ１），（ｘ２，ｙ２））によって特徴付けられる長方形として表わされる。ここで、ｘ１およびｙ１は、その左上角部の座標であり、ｘ２およびｙ２は右下角部の座標である。順序付けられたアクティブなオブジェクトＩＮＰＵＴ  ＬＩＳＴに存在する各ホワイトランは、延長の可能性に関して検査される。延長の可能性は、ｐのラベルが付された所定のＷＲが、最大白長方形（Ｍａｘｉｍａｌ  Ｗｈｉｔｅ  Ｒｅｃｔａｎｇｌｅ、ＭＷＲ）を形成できるか否かといった態様で表わされる。延長の可能性が偽である場合には、ｐが既に最大のものであり、ｐは、アクティブＩＮＰＵＴ  ＬＩＳＴから削除されるとともに、アクティブＲＥＳＵＬＴ  ＬＩＳＴに書き込まれる。延長の可能性が真である場合には、ｐで始まる全てのＭＷＲが構成されるまで、延長のための検査が繰り返される。その後、ｐがＩＮＰＵＴ  ＬＩＳＴから削除され、ｐから得られる全てのＭＷＲが、アクティブＲＥＳＵＬＴ  ＬＩＳＴに書き込まれる。ＩＮＰＵＴ  ＬＩＳＴからの全ての白長方形が処理されると、ＲＥＳＵＬＴ  ＬＩＳＴに全てのＭＷＲが含まれるようになる。アルゴリズムの効率を高めるため、ＩＮＰＵＴ  ＬＩＳＴにおいてｙの値がソートされる。まず最初に、水平方向のＷＲ、すなわち高さよりも幅が大きいホワイトランに関してアルゴリズムが適用される。そして、画像を９０°回転させた後、垂直方向のＷＲに対してアルゴリズムを適用することができる。
【００２９】
一実施形態において、最大長方形を構成するためのアルゴリズムは、以下の通りである。まず、長方形データがリンクリストとして記憶される。この場合、長方形データには、少なくとも長方形の頂点の座標が含まれている。ＩＮＰＵＴ  ＬＩＳＴおよびＲＥＳＵＬＴ  ＬＩＳＴも、リンクリストとして記憶される。このリンクリストには、少なくとも３つの要素、すなわち、白長方形の数、リンクリスト内の最初および最後の要素のポインタが含まれている。次に、以下のステップが実行される。すなわち、ＩＮＰＵＴ  ＬＩＳＴをアクティブにして、ＲＥＳＵＬＴ  ＬＩＳＴを開始し、選択された長方形の一次的な座標のためのＢＵＦＦＥＲを開始する。順序付けられたアクティブなＩＮＰＵＴ  ＬＩＳＴにあるもののうち、ｐ１のラベルが付された最初の白長方形から始める。リスト中の次の白長方形にｐ２のラベルが付される。ＩＮＰＵＴ  ＬＩＳＴ中の各白長方形毎に、ｐ１が延長の可能性を有しているか否かを検討する。アクティブな白長方形ｐ１に関し、順序付けられたアクティブなＩＮＰＵＴ  ＬＩＳＴ中で、以下の条件を満たすｐｎｊ，ｊ＝１，．．．．，ｌのラベルが付された最初のものを見つける。
【数１】
2004282701.tif 000001
【数２】
2004282701.tif 000002
【数３】
2004282701.tif 000003
【００３０】
この検索により、｛ｐｎ１，ｐｎ２，．．．．ｐｎｌ｝のセットが得られる。このセット｛ｐｎ１，ｐｎ２，．．．．ｐｎｌ｝が空でない場合にだけ、ｐ１が延長の可能性を有していると言われる。
【００３１】
ｐ１が延長の可能性を有していない場合には、ｐ１が最大白長方形である。ｐ１をＲＥＳＵＬＴ  ＬＩＳＴに書き込んで、ｐ１をＩＮＰＵＴ  ＬＩＳＴから削除し、ｐ２に関して処理を進める。
【００３２】
ｐ１が延長の可能性を有している場合には、延長処理をｐ１に適用する。ｐ２に関して処理を進める。なお、ｐ１がそれ自体最大であっても延長の可能性を有し得る。延長処理は以下の通りである。まず、ｐ１が延長の可能性を有していると仮定すると、セット｛ｐｎ１，ｐｎ２，．．．．ｐｎｌ｝が存在する。延長処理は、｛ｐｎ１，ｐｎ２，．．．．ｐｎｌ｝の各要素に対して一貫して適用される。長方形ｐｎｊ，ｊ＝１，．．．．，ｌを用いて延長可能な白長方形ｐ１に関して、以下の座標を有する新たな長方形ｐ１，ｎｊを構成する。
【数４】
2004282701.tif 000004
【数５】
2004282701.tif 000005
【数６】
2004282701.tif 000006
【数７】
2004282701.tif 000007
【００３３】
ｐ１，ｎｊ，ｊ＝１，．．．．，ｌの座標を「座標」バッファに書き込む。ここで、ｐ１，ｎｊに関して延長可能性の検査を繰り返す。検査が真である場合には、ｐ１，ｎｊが最大である。ｐ１，ｎｊをＲＥＳＵＬＴ  ＬＩＳＴに書き込み、さもなければ、ｐ１，ｎｊを延長する。
【００３４】
延長処理をｐ１，ｎｊに適用する前に、吸収作用に関してｐ１およびｐｎｊをチェックする。ｐ１，ｎｊを用いた吸収作用に関するｐ１およびｐｎｊの検査は、以下の通りである。吸収作用とは、ｐ１（ｐｎｊ）又はこれらの両方が、ｐ１，ｎｊに完全に含まれている状態を意味する。座標において、このことは、以下の状態を意味する。
【数８】
2004282701.tif 000008
【数９】
2004282701.tif 000009
ここで、ｋ＝１，ｎｊ，ｊ＝１，．．．，ｌである。
【００３５】
状態がｐ１に関して真である場合には、ｐ１はｐ１，ｎｊによって吸収される。ｐ１をＩＮＰＵＴ  ＬＩＳＴから除去する。状態がｐｎｊに関して真である場合には、ｐｎｊはｐ１，ｎｊによって吸収される。ｐｎｊをＩＮＰＵＴ  ＬＩＳＴから除去する。
【００３６】
アルゴリズムでは、長方形の幅が高さよりも大きく、したがって、長方形が、主として水平方向であると仮定される。垂直方向のＭＷＲを構成するため、オリジナルの２値画像が９０°時計周りに回転される。回転された画像に関して前述したアルゴリズムが繰り返される。その結果、オリジナル画像において全ての垂直方向のＭＷＲが構成される。
【００３７】
図６は、最大白長方形の構成を示している。水平方向のｘ軸および垂直方向のｙ軸に沿って、ピクセル座標が表わされている。４つのホワイトラン６１が、図の左側に示されている。ホワイトラン（ＷＲ）は、その上角部および下角部の座標が、以下の座標に対応する長方形として描かれている。
【数１０】
2004282701.tif 000010
【数１１】
2004282701.tif 000011
【数１２】
2004282701.tif 000012
【数１３】
2004282701.tif 000013
【００３８】
これらのホワイトランによって全ての最大白長方形が構成される。図の右側部分には、結果として得られる５つの最大白長方形（ＭＷＲ）が、６２、６３、６４、６５、および６６で示されている。図示された５つのＭＷＲは、図の左側部分に示されたＷＲにおけるＭＷＲの完全なセットである。構成アルゴリズムは以下の通りである。
【００３９】
ＩＮＰＵＴ  ＬＩＳＴに４つのホワイトラン６１を含ませる。ＩＮＰＵＴ  ＬＩＳＴからの最初の要素は、ＷＲ１（（１０，１），（５０，２））である。ＷＲ１にｐ１のラベルを付ける。前述したように、延長の可能性に関してｐ１を検査する。延長における第１の候補は、ＷＲ２（（１０，２），（５０，３））である。ＷＲ２にｐｎ１のラベルを付ける。前述した延長に関する方式にしたがってｐｎ１を用いてｐ１を延長する。これにより、座標（（１０，１），（５０，３））を有する新たな長方形ｐ１，ｎ１が与えられる。ｐ１，ｎ１を用いた吸収作用に関してｐ１およびｐｎ１を検査する。以下の通り、吸収検査により、ｐ１およびｐｎ１の両方が、ｐ１，ｎ１によって吸収される。したがって、ｐ１およびｐｎ１をＩＮＰＵＴ  ＬＩＳＴから削除する。ｐ１，ｎ１に関して処理を進める。延長の可能性に関してｐ１，ｎ１を検査する。これにより、第１の候補ＷＲ３（（５，３），（３０，４））が与えられる。ＷＲ３にｐｔ１のラベルを付ける。延長に関する方式にしたがってｐｔ１を用いてｐ１，ｎ１を延長する。その結果、座標（（１０，１），（３０，４））を有する新たな長方形ｐ（１，ｎ１），ｔ１が得られる。ｐ（１，ｎ１），ｔ１を用いた吸収作用に関してｐｔ１を有するｐ１，ｎ１を検査する。検査は失敗する。
【００４０】
ｐ（１，ｎ１），ｔ１に関して延長の可能性の検査を繰り返す。検査は失敗する。すなわち、ｐ（１，ｎ１），ｔ１は延長の可能性を有していない。このことは、ｐ（１，ｎ１），ｔ１が最大であることを意味する。座標（（１０，１），（３０，４））を有するｐ（１，ｎ１），ｔ１をＲＥＳＵＬＴ  ＬＩＳＴに書き込む。
【００４１】
ｐ１，ｎ１に関して再び処理を進め、延長の可能性に関してｐ１，ｎ１を検査する。第２の候補ＷＲ４（（４０，３），（６０，４））が見出される。ＷＲ４にｐｔ２のラベルを付ける。延長に関する方式にしたがってｐｔ２を用いてｐ１，ｎ１を延長する。その結果、座標（（４０，１），（５０，４））を有する新たな長方形ｐ（１，ｎ１），ｔ２が得られる。
【００４２】
ｐ（１，ｎ１），ｔ２を用いた吸収作用に関してｐｔ２を有するｐ１，ｎ１を検査する。検査は失敗する。すなわち、吸収がない。ｐ（１，ｎ１），ｔ２に関して延長の可能性の検査を繰り返す。検査は失敗する。すなわち、ｐ（１，ｎ１），ｔ２は延長の可能性を有していない。このことは、ｐ（１，ｎ１），ｔ２が最大であることを意味する。座標（（４０，１），（５０，４））を有するｐ（１，ｎ１），ｔ２をＲＥＳＵＬＴ  ＬＩＳＴに書き込む。
【００４３】
延長の可能性に関してｐ１，ｎ１を再び検査する。検査は失敗し、ｐ１，ｎ１が最大である。座標（（１０，１），（５０，３））を有するｐ１，ｎ１をＲＥＳＵＬＴ  ＬＩＳＴに書き込む。
【００４４】
ＩＮＰＵＴ  ＬＩＳＴに戻る。この段階におけるＩＮＰＵＴ  ＬＩＳＴは、２つのホワイトラン、すなわち、ＷＲ３：（（５，３），（３０，４）），ＷＲ４：（（４０，３），（６０，４））を含んでいる。ＷＲ３から開始して、これにｐ２のラベルを付ける。ｐ２に関して延長の可能性の検査を繰り返す。検査は失敗し、ｐ２が最大である。座標（（５，３），（３０，４））を有するｐ２を、ＲＥＳＵＬＴ  ＬＩＳＴに書き込む。ＩＮＰＵＴ  ＬＩＳＴからｐ２を除去する。ＷＲ４に関して処理を進め、これにｐ３のラベルを付ける。ｐ３に関して延長の可能性の検査を行なうことにより、ｐ３が最大であることが分かる。座標（（４０，３），（６０，４））を有するｐ３をＲＥＳＵＬＴ  ＬＩＳＴに書き込む。ＩＮＰＵＴ  ＬＩＳＴからｐ３を除去する。最終的に、ＲＥＳＵＬＴ  ＬＩＳＴは、５つの最大白長方形、すなわち、図６に６４で示されるＭＷＲ１：（（１０，１），（５０，３））と、６２で示されるＭＷＲ２：（（１０，１），（３０，４））と、６３で示されるＭＷＲ３：（（４０，１），（５０，４））と、６５で示されるＭＷＲ４：（（５，３），（３０，４））と、６６で示されるＭＷＲ５：（（４０，３），（６０，４））とを含んでいる。
【００４５】
図７は、本発明にかかる方法における次のステップ、すなわち、最大白長方形をオーバーラップさせるクリーニングステップを示している。このクリーニングステップにおいて、オーバーラップする複数の最大白長方形は、後で詳述するように、オリジナルの最大白長方形の最も関連する特性を組み合わせる、１つの所謂「情報提供最大長方形」（Ｉｎｆｏｒｍａｔｉｖｅ  Ｍａｘｉｍａｌ  Ｒｅｃｔａｎｇｌｅ、ＩＷＲ）に統合される。
【００４６】
クリーニングは、サイズおよび空間的な関係をチェックする等のステップを更に含んでいる。図７の上側の部分は、一例として、２つの最大白長方形ＭＷＲ１およびＭＷＲ２を示している。これらの対は、図の下側の部分に示されるように、クリーニングステップにおいて、１つの情報提供白長方形ＩＷＲに統合される。オーバーラップを検知する処理および統合する処理は、関連する対をもはや形成することができなくなるまで繰り返される。対を形成する基準は、オーバーラップ領域のサイズであっても良い。
【００４７】
また、クリーニングステップは、薄い或は短い長方形、すなわち、アスペクト比が所定の値を下回る長方形を除去することを含んでいても良い。除去する基準は、画像のタイプに基づいていても良い。例えば、所定のピクセル数を下回る幅は、テキストラインのセパレータを示し、フィールドの分離に関係しない。特定の値を下回る長さは、フィールドの期待されるサイズに関連しない。
【００４８】
クリーニングステップのためのアルゴリズムは、以下の通りである。クリーニング処理の開始は、図５および図６に関して前述したように構成されるＭＷＲのセット全体である。クリーニング処理は、情報を提供しないＭＷＲを廃棄するべく適用される。このため、情報を提供しないことに関する尺度が規定される。例えば、長いＭＷＲは、短いものよりも多くの情報を与える。低いアスペクト比は、情報提供量が少ない正方形を多かれ少なかれ示す。また、例えば２つのテキストラインを分離する極めて薄い長方形は、除外しなければならない。最初に、全てのＭＷＲは、その高さと幅との間の比が計算されることにより、水平方向、垂直方向、あるいは正方形であるとして分類される。正方形のＭＷＲは、その情報提供性が無いことにより、削除される。残りの水平方向および垂直方向のＭＷＲに関しては、以下の３つのステップから成るクリーニング技術が適用される。
【００４９】
長さまたは幅が所定の値を下回る各ＭＷＲが削除される。
【００５０】
長い辺の長さを短い辺の長さで割った比として規定されるアスペクト比（ＡＲ）が、所定の値を下回る各ＭＷＲが削除される。
【００５１】
互いにオーバーラップする水平方向（または垂直方向）のＭＷＲ１（（ｘ１，ｙ１），（ｘ２，ｙ２））および水平方向（または垂直方向）のＭＷＲ２（（ａ１，ｂ１），（ａ２，ｂ２））から成る各対毎に、以下の座標を用いて、情報提供白長方形ＩＷＲが構成される。
（ａ）水平方向のオーバーラップ
【数１４】
2004282701.tif 000014
【数１５】
2004282701.tif 000015
【数１６】
2004282701.tif 000016
【数１７】
2004282701.tif 000017
（ｂ）垂直方向のオーバーラップ
【数１８】
2004282701.tif 000018
【数１９】
2004282701.tif 000019
【数２０】
2004282701.tif 000020
【数２１】
2004282701.tif 000021
【００５２】
この処理は、オーバーラップするＭＷＲから成る全ての対に関して繰り返される。ここで、ＭＷＲのセットは、情報提供白長方形ＩＷＲを含んでいる。これらのＩＷＲは、レイアウト要素に対応する複数のフィールドに、画像を分割するアルゴリズムのための開始点を形成する。ＩＷＲは、有力なフィールドセパレータであり、そのため、「分離要素」と呼ばれる。アルゴリズムは、ＩＷＲを使用して、画像の地理的記述へと更に処理するためにグラフを構成する。
【００５３】
図８は、新聞の一面におけるそのようなグラフを示している。画像は、ダウンサンプリングされた新聞の一面のデジタル画像８０を示している。オリジナルテキストは、図２に対応するダウンサンプリングされたバージョンにおいて黒で見ることができる。分離要素を構成する情報提供長方形ＩＷＲが、灰色で示されている。グラフの構成のため、水平方向および垂直方向の白ＩＷＲによって構成される分離要素の交差部が決定される。２つのＩＷＲの交点は、頂点すなわちグラフの頂点８１を示す小さな黒色正方形で表わされている。一面内でフィールドを分離するラインを示す辺８２は、頂点８１から成る対を「フィールドセパレータ」によって接続することにより構成される。グラフの辺８２が白で示されている。辺の２つの頂点間の距離、すなわち長さは、更なる処理のために加重として辺に対して割り当てられる。他の実施形態においては、異なるパラメータが使用され、例えばピクセルの色等の加重が割り当てられる。グラフを構成するためのアルゴリズムは、以下の通りである。
【００５４】
初めに、ＩＷＲに関して以下の表記法および定義が与えられる。Ｒ＝｛ｒ１，．．．，ｒｍ｝が空でなく、また全てのＩＷＲの有限のセットが所定の画像ｌから得られると仮定する。ここで、各ＩＷＲは、それぞれ、その左上角部および右下角部のｘ座標およびｙ座標（（ｘ１（τ），ｙ１（τ）），（ｘ２（τ），ｙ２（τ））），τ＝１，２，．．．，ｍによってによって特定される。各長方形ｒτは、その高さと幅との比に基づいて、水平方向、垂直方向、あるいは正方形として分類される。Ｈ＝｛ｈ１，．．．ｈｌ｝，Ｖ＝｛ｖ１，．．．，ｖｋ｝，Ｓ＝｛ｓｉ，．．．，ｓｄ｝は、以下の関係を成すように、水平方向、垂直方向、および正方形のＩＷＲのサブセットを示す。
【数２２】
2004282701.tif 000022
【数２３】
2004282701.tif 000023
ここで、以下が仮定される。
【数２４】
2004282701.tif 000024
【００５５】
また、Ｓの内容は無視され、ＨおよびＶのサブセットだけが使用される。これは、多くの場合、テキストブロックまたは非テキストブロックの境界を形成する白空間が、細長い垂直方向または水平方向領域であるといった考えに基づいている。ｈが座標（（ｘ１，ｙ１），（ｘ２，ｙ２））を有するＨの一部であるとし、また、ｖが座標（（ａ１，ｂ１），（ａ２，ｂ２））を有するＶの一部であるとする。この時、以下の条件の下、ｈおよびｖはオーバーラップを有する。
【数２５】
2004282701.tif 000025
【００５６】
オーバーラップの場合のｈおよびｖの交点により、以下の座標によって規定される唯一の点Ｐが得られる。
【数２６】
2004282701.tif 000026
【００５７】
ＩＷＲにおいては、考えられる全てのタイプのオーバーラップから、２つのオーバーラップだけが生じる。すなわち、長方形となるオーバーラップと、点となるオーバーラップだけが生じる。ラインのオーバーラップは生じない。これは、ラインのオーバーラップがＭＷＲの概念と矛盾するからである。
【００５８】
図９は、最大長方形の２つのタイプの交差部を示している。グラフを構成するため、垂直方向および水平方向の情報提供最大長方形の交点が決定され、これにより、グラフの頂点の位置が見出される。すなわち、頂点の正確な座標が決定される。図の左側部分は、垂直方向のＩＷＲであるｖと、水平方向のＩＷＲであるｈとの交差部の第１のタイプを示している。このタイプの交差では、交差部の中心が点Ｐである長方形領域８８が形成される。図の右側部分は、垂直方向のＩＷＲであるｖと水平方向のＩＷＲであるｈとの交差部の第２のタイプを示している。このタイプの交差では、交差部の中心がＰ’である１つの交点８９が生じる。
【００５９】
交点に基づいてグラフを構成するアルゴリズムは、以下の通りである。
【００６０】
Ｐ＝｛ｐ１，．．．，ｐＮ｝は、垂直方向のＩＷＲおよび水平方向のＩＷＲの全ての交点のセットを示している。この場合、Ｐの中の各ｐは、そのｘ座標およびｙ座標（ｘｐ，ｙｐ）によって特定される。ここで、ｐ＝１，．．．．Ｎである。セットＰが見出され、Ｇ＝（Ｘ，Ａ）がＰに対応する方向性が無いグラフであるとする。グラフＧ＝（Ｘ，Ａ）は、交点に対して直接に関係する有限の数の頂点Ｘと、交点間の関係を描く有限の数の辺Ａとから成る。これは、数学的には、以下のように表わされる。
【数２７】
2004282701.tif 000027
ここで、
【数２８】
2004282701.tif 000028
【数２９】
2004282701.tif 000029
ここで、ｄｉｊは、点ｉと点ｊとの間のユークリッド距離を示している。また、４連鎖接続（４−ｃｈａｉｎ  ｃｏｎｎｅｃｔｅｄ）は、４つの可能な移動方向で長方形ブロックの頂点が接続されることを意味している。前述した２つの点ｉ，ｊは、ｍｉｎｄｉｊを有する４つの接続連鎖コードによって１方向に動き回ることにより、これらの点に達し得る場合には、４連鎖接続である。
【００６１】
ここで、構成されたグラフを更に処理して、グラフの内部の領域をテキストブロックとして分類し、あるいは、画像のタイプに応じて同様の分類を行なっても良い。一実施形態において、グラフは、解析において、例えば黒ラインまたは破線／点線等のパターン化されたラインといったフォアグラウンドセパレータを含めることにより増大される。また、検出される写真またはグラフィックオブジェクトのエッジを、解析に含めることもできる。
【００６２】
また、この分割方法は、フォアグラウンドセパレータを除去するステップを含んでいても良い。まず最初に、フォアグラウンドセパレータが認識されて、１つのオブジェクトとして再構成される。パターン化されたラインを構成する成分は、要素ヒューリスティックス、空間的関係ヒューリスティックス、およびラインヒューリスティックスを解析することにより、すなわち、１方向で組み合わされた要素を構築し且つそれがラインとして分類するか否かを検出することにより接続される。パターン化されたラインから実線を再構成するための更なる方法は、ダウンサンプリングおよび／または「Ｄｏｃｕｍｅｎｔ  ａｎａｌｙｓｉｓ  ｓｙｓｔｅｍ（文書解析システム）」ＩＢＭ  Ｊ．Ｒｅｓ．Ｄｅｖ  ２６（１９８２）６４７−６５６において、Ｋ．Ｙ．Ｗｏｎｇ，Ｒ．Ｇ．Ｃａｓｅｙ，Ｆ．Ｍ．Ｗａｈｌにより説明されている、ラン・レングス・スムージング・アルゴリズム（ＲＬＳＡ）使用することである。フォアグラウンドセパレータの検出後、フォアグラウンドセパレータは、バックグラウンドピクセルに取って代えられる。その結果、より大きな最大白長方形を構成することができ、あるいは、バックグラウンドピクセル特性を使用して、バックグラウンドセパレータを見出す任意の他の適した方法をサポートすることができる。
【００６３】
図１１は、フィールドセパレータに基づいてフィールドを規定する方法に関する図を示している。
【００６４】
基本的に、この方法のタスクは、画像内でフィールドを規定することである。この場合、フィールドは、新聞画像内のテキストブロック等といった、相互に関連するフォアグラウンド要素を含む領域として規定される。画像内のフィールドは、所定の方向を有し且つ厚さが０である幾何学的なラインであると理解されるフィールドセパレータによって分離される。フィールドセパレータは、分離方向、一般には水平または垂直方向で、長方形状を有する連結されたバックグラウンドピクセルの領域に対応している。フィールドセパレータの交差点は、ノードと呼ばれている。本方法においては、最初に、画像内のフィールドセパレータが検出され、その後、フィールドセパレータの解析に基づいて、フィールドが決定される。
【００６５】
ＳＥＰＡＲステップ９５においては、画像が解析されることにより、フィールドセパレータが得られる。フィールドセパレータは、前述した最大白長方形を使用する解析に基づいていることが好ましい。最大白長方形を使用する解析では、辺と辺が接続する頂点とを有するグラフが得られる。本発明の方法において、フィールドセパレータおよびノードは、グラフの辺および頂点にそれぞれ対応している。また、フィールドセパレータを決定するために、他の適した方法を使用しても良い。なお、セパレータを得るための処理は、先立って既に終了してしまっていても良い。すなわち、画像は、既にセパレータを示す更に高いレベルでの構造の表示である。
【００６６】
このようにして見つけられたフィールドセパレータは、例えば走査のアライメントミス等により、基本的な水平方向および垂直方向から僅かに外れるかもしれず、更なる処理ステップにおいてエラーを招く可能性がある。したがって、この時点で、フィールドセパレータのｘ座標またはｙ座標の小さなズレを０にする、「スナップ・トゥ・グリッド（ｓｎａｐ  ｔｏ  ｇｒｉｄ）」ステップが処理に加えられても良い。
【００６７】
ＴＥＳＳステップ９６においては、ビルディングブロックレベルへの変換が行なわれる。このステップにおいては、フィールドセパレータが画像の外側の境界に達するまでフィールドセパレータを延長することにより、画像内のフィールドのビルディングブロックを形成する基本的な複数の長方形に画像が分割される。このようにして、所謂テセレーショングリッドが形成され、（延長された）フィールドセパレータによって囲まれた領域が、基本長方形として規定される。
【００６８】
テセレーショングリッドの形成については、図１２および図１３を参照しながら詳細に後述する。
【００６９】
基本的に、ここで、方法は、フィールドセパレータによって分離されない基本長方形をフィールドに連結する。この処理を行なうための特に有効な方法は、以下のステップを含んでいる。
【００７０】
ＭＡＴＲＩＸステップ９７においては、テセレーション画像の新たな表示が、マトリクスマップの形態で形成される。マトリクスマップにおいて、基本長方形およびテセレーショングリッド要素は、マトリクス要素によって表わされる。このステップについては、図１４を参照しながら更に後述する。
【００７１】
ＣＯＮＮステップ９８においては、基本長方形が連結され、これにより、連結基本長方形の領域が形成される。基本長方形は、これらがラインの延長部分によって分離される場合に、連結されていると見なされ、フィールドセパレータに関連付けられたライン部分によって分離される場合に、連結されていないと見なされる。連結成分アルゴリズムは、図１４に関して後述するように、このステップで使用される。
【００７２】
このステップでこの時に決定される連結基本長方形のセットは、オリジナル画像のフィールドに対応している。
【００７３】
ＮＯＤＥステップ９９においては、オリジナル画像内においてフィールドの位置を規定するために、ＣＯＮＮステップで見出されたフィールドを境界付けるオリジナルノードが検索される。
【００７４】
最後に、ＦＩＥＬＤステップ１００において、先のステップで検索されたオリジナルノードは、連結基本長方形の各領域毎にフィールドを規定するデータ構造に組み合わされる。これにより、マトリクス表示が変換されてピクセルドメインに戻される。このステップについては、図１５から図１７を参照しながら更に後述する。
【００７５】
ここで、アルゴリズムのＴＥＳＳステップについて更に詳しく説明する。
【００７６】
図１２は、画像の表示を示している。画像は、フィールド１０９を囲むフィールドセパレータ１１０に関連付けられたラインによって表わされている。フィールドセパレータ１１０は、バックグラウンド、通常は新聞の白を表わしており、黒ラインとして示される。例えばこの例ではフィールド１０９であるフィールドセパレータ間のフォアグラウンド領域は、フィールドとして規定される。実行されるタスクは、画像内のフィールドを識別することである。
【００７７】
図１３は、図１２の入力画像に基づく画像上のテセレーショングリッドを示している。テセレーショングリッドを形成するため、全てのフィールドセパレータ（図１３の連続ライン１１０）が画像の境界まで延長された。その結果、画像は、４つのＸセグメントΔＸ１からΔＸ４の垂直ライン、および６つのＹセグメントΔＹ１からΔＹ６の水平ラインによって小分割される。フィールドセパレータ１１０の延長が、破線１１１によって示されている。例えば、ノード２、６はフィールドセパレータの実際のノードであり、延長により、ノード２とノード６との間に仮想ノード１１６が形成される。ノード２とノード６との間のラインの直ぐ右側の領域には、２つの基本長方形が形成される。フィールドセパレータの延長に基づくラインによって形成されるテセレーショングリッド内の全ての長方形は、所謂基本長方形である。例えば、基本長方形１１３は、影が付けられた領域によって示される連結領域の一部である。前記連結領域は、フィールドセパレータによって基本長方形１１３から分離されない全ての基本長方形によって構成される。連結基本長方形の領域は、図１４に関して後述するように、簡単に構成することができる。
【００７８】
なお、このような方法は、実質的に長方形構造ではない領域にも拡大して適用することができることに留意されたい。平面グラフの区分的線形化および／または弾力的変形は、「湾曲した境界付けられた」領域を含む画像を処理するために適用できる。
【００７９】
基本的なアルゴリズムのＭＡＴＲＩＸステップにおいて、図１３に示されるテセレーション画像は、マトリクス表示に変換される。このマトリクス表示においては、全ての基本長方形および全てのラインセグメントが、マトリクス要素に関連付けられる。テセレーション画像は、水平方向で横切る場合には、４つの基本長方形とフィールドセパレータに関連付けられた５つの垂直ラインとにまたがる。したがって、マトリクス表示は９個の縦列を有する。テセレーション画像は、垂直方向で横切る場合には、６つの基本長方形と７つの水平ラインとにまたがる。したがって、マトリクス表示は１３個の横列を有する。
【００８０】
最初に、全てのマトリクス要素に値１が与えられる。その後、全てのマトリクス要素は、オリジナル画像のフィールドセパレータに関連付けられているか否かが体系的にチェックされる。関連付けられている場合には、マトリクス要素の値１が値０に変更される。したがって、フォアグラウンド要素が１で表わされ、バックグラウンド要素が０で表わされる。
【００８１】
また、フィールドセパレータのリストをチェックすることにより、マトリクス要素が０に変更されても良い。フィールドセパレータのリストをチェックすることは、通常、演算を殆ど必要としない。
【００８２】
図１４は、結果として得られる図１３の画像のマトリクスマップ１２０を示している。例えば、基本長方形１１３は、ここでは、マトリクスの１つの要素１２３に換算され、また、延長されたラインセグメント１１１は、ここでは、マトリクスの要素１２１となる。ノード２、６は、要素１２４、１２５で表わされている。また、仮想ノード１１６に対応するマトリクス要素も示されている。この要素は値１を有している。なぜなら、この要素は、フィールドセパレータの一部だからである。なお、地理的形状は保たれていないことに留意されたい。これは、ノード間のラインの長さが考慮されていないためである。画像およびテセレーショングリッドの表示におけるオリジナルノード間の関係は、図１７を参照して後述するように個別に記憶される。
【００８３】
領域１０９（図１２）は、全て１となる要素から成る影付き領域１２２として図１４に示されている。
【００８４】
アルゴリズムのＣＯＮＮステップにおいて、形成されたマトリクスマップには、その後、１の値を有する連結要素のセットをマトリクス内で見つけるための連結成分処理が施される。連結成分アルゴリズムは、文献で広く知られているため、本明細書では、これ以上説明しない。
【００８５】
以下、アルゴリズムのＮＯＤＥステップについて更に詳細に説明する。一例として、図１５は、図１４のマトリクス内の１つの連結領域１３０を示している。図示のマトリクスは、前述したテセレーショングリッドに基づいているが、連結成分処理によって検出される連結領域１３０だけが、影付き領域で示されている。連結領域の構成要素は、値１を有するとともに、０の値を有する要素によって囲まれている。以下のステップにおいて、フィールドは、連結領域の周囲の外形に基づいて規定される。
【００８６】
図１６は、連結領域の外形１４０を示している。この外形は、連結領域１３０に対応する値０を有する領域が、値１を有する影付き領域によって取り囲まれることにより示される。外形を見出すため、最初に、領域１３０が１ピクセル分だけ拡張される。その後、オリジナル領域が取り去られる。
【００８７】
図１７はノードマトリクスを示している。このマトリクスは、マトリクスマップと同じ大きさを有している。要素の値は、ノード番号（０から１９）または空のいずれかである。ノード番号は、図１２に示されるオリジナル画像のノードを参照する。先に得られた連結領域１３０の外形１４０は、ノードマトリクス上に描出され、影付き領域１４１で示されている。
【００８８】
ノードマトリクスは、以下のように構成される。最初に、要素の値が「空」に設定される。その後、例えばグラフの頂点リストに基づいて、フィールドセパレータの実際のノードがマトリクスに入力される。
【００８９】
タスクは、領域１３０の外形１４０に属する全てのノードを抽出することである。外形内に存在するノードは、外形をトレースしてその中のノードを表示することにより検索される。
【００９０】
外形をトレースした後、ノードは、アルゴリズムのＦＩＥＬＤステップにおいて、オリジナル画像表示に組み合わせられる。必要に応じて、「スナップ・トゥ・グリッド（ｓｎａｐ−ｔｏ−ｇｒｉｄ）」処理の逆が適用され、ノード番号が、再びノードのオリジナルセットと一体になる。最後に、必要に応じて、ノードおよび／またはフィールドの辺が、例えば時計周り方向で順序付けられる。この順序付けは、領域演算または表示のために必要とされても良い。
【００９１】
無論、ノード抽出およびフィールド決定は、画像内の全てのフィールドに関して行なわれなければならない。
【００９２】
なお、領域が互いに取り囲むことにより、分離した多角形、例えばテキスト包囲体を形成しても良いことに留意されたい。複数の分離した多角形によって境界付けられる領域に関して演算できるように、これらの多角形を連結する知られている技術が使用される。多角形の２つの外形は、所謂「０領域ブリッジ」により、実際には２つのラインセグメントにより連結される。ラインセグメントの一方は内側の外形に入り、ラインセグメントの他方は内側の外形から出る。
【００９３】
図１０は、画像を分割するための本発明に係る方法が実施される装置を示している。この装置は、デジタル画像を入力するための入力ユニット９１を有している。入力ユニットは、紙からの画像を走査する電子光学スキャナ等の走査ユニット、またはインターネット等のネットワークからの画像を受けるデジタル通信ユニット、または光ディスクドライブ等の記録キャリアからデジタル情報を検索する再生ユニットを備えていても良い。入力ユニット９１は、記憶ユニット９２と協働する処理ユニット９４に接続されている。処理ユニットは、汎用コンピュータ中央処理ユニット（ＣＰＵ）および支援回路を備えていても良く、前述した分割を行なうためのソフトウェアを使用して動作する。特に、ソフトウェアは、テセレーショングリッドを構成するためのモジュール（図面には単独で示されていない）を有している。このモジュールは、フィールドセパレータを画像の外側の境界まで延長して基本長方形を構成し、フィールドセパレータによって分離されない隣り合う基本長方形同士を連結することによりフィールドを構成することによって、テセレーショングリッドを構成する。また、ソフトウェアは、テセレーショングリッドを表示するマトリクスマップを構成し、且つテセレーショングリッド内のノードに関連するノードマトリクスを構成するモジュールを有している。
【００９４】
処理ユニットは、キーボード、マウス装置、またはオペレータボタン等の制御手段を備えたユーザインタフェース９５を更に有していても良い。処理ユニットの出力部は、ディスプレイユニット９３に接続されている。一実施形態において、ディスプレイユニットは、処理された画像を紙上に出力するための印刷ユニット、または磁気テープや光ディスク等の記録キャリア上に分割された画像を記憶する記録ユニットである。
【００９５】
分割されるデジタル画像として、新聞の一面の実施形態によって本発明を主に説明してきたが、本発明は、例えばＩＣ設計のためのレイアウト画像における電気回路や、シティーマップ上の通りや建物など、バックグラウンド上にフィールドを備える任意のデジタル表示にも適している。また、最短のサイクルによって分割を実行するための開始点としてのグラフは、ＭＷＲシステムに基づく前述したグラフとは異なる方法で構成されても良い。例えば、グラフは、前述したＡｎｔｏｎａｃｏｐｏｕｌｏｓによる論文に記載されたタイルを使用して構成されても良い。また、グラフの辺に割り当てられる加重は、必ずしも距離でなくても良い。加重は、最短サイクルに寄与するように対応して選択されなければならない。例えば、加重は、タイルの表面であっても良い。なお、この明細書において、動詞「備える」、「含む」、「有する」及びその活用の用法は、記載された要素以外の他の要素またはステップの存在を排除しない。また、要素に先立つ単語「１つの」は、そのような要素が複数存在することを除外せず、任意の参照符号は、特許請求の範囲を限定しない。また、本発明、および全てのユニット、または前述した手段は、適当なハードウェアおよび／またはソフトウェアによって実施することができ、幾つかの「手段」または「ユニット」は、同じ要素によって表わすことができる。また、本発明の範囲は実施形態に限定されず、本発明は、前述した個々の新規な特徴、全ての新規な特徴、または特徴の組み合わせにある。
【図面の簡単な説明】
【００９６】
【図１】典型的な分割方法の概略を示している。
【図２】サンプルとしての日本の新聞の一部を示している。
【図３】１方向に沿うオブジェクトの統合を示している。
【図４】オブジェクトの分割および２方向統合を示している。
【図５】ホワイトランからの最大長方形の構成を示している。
【図６】最大白長方形の構成を示している。
【図７】最大白長方形をオーバーラップさせるクリーニングを示している。
【図８】新聞の一面上のグラフを示している。
【図９】最大長方形の２つのタイプの交差部を示している。
【図１０】画像を分割するための装置を示している。
【図１１】フィールドセパレータに基づいてフィールドを規定するための方法に関する図を示している。
【図１２】画像の表示を示している。
【図１３】画像のテセレーショングリッドを示している。
【図１４】テセレーショングリッドのマトリクスマップを示している。
【図１５】マトリクス内の１つの連結領域を示している。
【図１６】連結領域の外形を示している。
【図１７】ノードマトリクスを示している。
【符号の説明】
【００９７】
１１  入力画像
１２  ＣＣオブジェクト
１３  レイアウトオブジェクト
１４  ＣＣＡモジュール
１５  ＬＡモジュール
１６  ＡＦモジュール
１７  記事
２１  垂直方向読み方向
２２  水平方法読み方向
２３  黒ライン
３１  最初の解析ステップ
３２  算定閾値
３３  分類ステップ
３４  補正された連結成分
３５  統合ステップ
３６  オブジェクト
３７  テキスト統合ステップ
３８  テキストブロック
４１  画像のグラフ
４２  フィールド検出ステップ
４３  連結成分
４４  ステップ
４５  読む順番
４６  ライン形成ステップ
４７  テキストブロック
５１  ホワイトラン
５２  最大白長方形
５３  フォアグラウンド領域
６１  ホワイトラン
６２、６３、６４、６５、６６  最大白長方形
８０  デジタル画像
８１  グラフの頂点
８２  辺
８８  長方形領域
８９  交点
９１  入力ユニット
９２  記憶ユニット
９３  ディスプレイユニット
９４  処理ユニット
９５  ユーザインタフェース
９６  ＴＥＳＳステップ
９７  ＭＡＴＲＩＸステップ
９８  ＣＯＮＮステップ
９９  ＮＯＤＥステップ
１００  ＦＩＥＬＤステップ
１０９  フィールド
１１０  フィールドセパレータ
１１１  ラインセグメント
１１３  基本長方形
１１６  仮想ノード
１２０  マトリクスマップ
１２１、１２３、１２４、１２５  要素
１２２、１４１  影付き領域
１３０  連結領域
１４０  外形