JP2004288158A - 最短サイクルによる画像分割 - Google Patents

Abstract

【課題】より効果的な、画像を分割するための方法および装置であって、特に、更なる処理ステップで簡単に使用できる分割画像の単純な記述を与える方法および装置を提供する。
【解決手段】ピクセルから成る画像を複数のフィールドに分割する方法が記載されている。この方法は、画像のバックグラウンド、特に新聞の一面の白領域を使用して、フィールドセパレータを見つける。画像内の領域に基づいて、垂直方向および水平方向の白領域が交差する場所に、白領域に対応する辺と頂点とを有するグラフが構成される。分割は、加重、特に頂点間のユークリッド距離を示す加重を辺に割り当てることにより開始される。その後、グラフの辺および頂点により、最短サイクルのリストが構成される。リストの最短サイクルの頂点および辺によってフィールドが規定される。
【選択図】 図１２ａ

Description

本発明は、ピクセルから成る合成画像を、画像のレイアウト要素に対応する複数のフィールドに分割する方法であって、前記ピクセルが、画素の強度および／または色を示す値を有する方法に関する。

また、本発明は、前記方法を実施するための装置であって、画像を入力するための入力ユニットと処理ユニットとを備えた装置に関する。

レイアウト要素に対応するフィールドを識別するために、テキストおよび図を含む文書等の合成画像を分割する幾つかの方法が技術的に知られている。一般的な方法は、バックグラウンドの処理に基づいている。画像は、画素の強度および／または色を示す値を有するピクセルによって表わされる。前記値は、バックグラウンド（通常、白）またはフォアグラウンド（通常、印刷スペースである黒）として分類される。ページ上の印刷領域を取り囲む白色のバックグラウンドスペースが、解析される。

ページ分割の方法は、１９９０年６月にニューヨークのアトランティックシティーで行なわれたパターン認識に関する第１０回国際会議の議事録、８２０頁から８２５頁における、Ｈ．Ｓ．Ｂａｉｒｄらによる文献、「Ｉｍａｇｅ Ｓｅｇｍｅｎｔａｔｉｏｎ ｂｙ Ｓｈａｐｅ−Ｄｉｒｅｃｔｅｄ Ｃｏｖｅｒｓ（形状指向カバーによる画像分割）」によって知られている。フォアグラウンドピクセルを含んでいなければ拡張することができない、バックグラウンドピクセルから成る長方形である最大長方形のセットが構成される。フィールドは、減少された最大長方形のセットで画像全体をカバーすることにより、セットに基づいて画像内で規定される。残りの「カバーされていない」領域は、フォアグラウンドとして見なされ、フィールドは、カバーされていないフォアグラウンド領域の連結成分解析によって見つけられる。この方法の問題は、コンピュータによる効率的な更なる処理ができないピクセルドメイン内の領域として、フィールドが規定されるという点である。

ページ分割のための更なる方法は、１９９４年１０月９日から１２日にイスラエルのエルサレムで行なわれた、パターン認識に関する第１２回国際会議の議事録、ＩＥＥＥ−ＣＳプレス、第２刊、３３９頁から３４４頁における、Ａ．ＡｎｔｏｎａｃｏｐｏｕｌｏｓおよびＲ．Ｔ．Ｒｉｔｃｈｉｎｇｓによる文献、「Ｆｌｅｘｉｂｌｅ ｐａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ｕｓｉｎｇ ｔｈｅ ｂａｃｋｇｒｏｕｎｄ（バックグラウンドを使用したフレキシブルなページ分割）」によって知られている。バックグラウンド白色スペースは、タイル、すなわちバックグラウンドピクセルの重なり合わない領域によって覆われる。

画像内のフォアグラウンドフィールドの外形は、それを取り囲む白色タイルに沿ってトレースすることにより識別され、これにより、タイルの内側の境界が、更なる解析のためのフィールドの境界を構成する。この方法の問題は、効率的な更なる解析を妨げる複雑な記述によって、フィールドの境界が表わされているという点である。

米国特許第５，８５６，８７７号明細書 Ｈ．Ｓ．Ｂａｉｒｄ他、「Ｉｍａｇｅ Ｓｅｇｍｅｎｔａｔｉｏｎ ｂｙ Ｓｈａｐｅ−Ｄｉｒｅｃｔｅｄ Ｃｏｖｅｒｓ（形状指向カバーによる画像分割）」、パターン認識に関する第１０回国際会議の議事録、１９９０年６月、ニューヨーク、アトランチィックシティー、ｐ８２０−８２５ Ａ．ＡｎｔｏｎａｃｏｐｏｕｌｏｓおよびＲ．Ｔ．Ｒｉｔｃｈｉｎｇｓ、「Ｆｌｅｘｉｂｌｅ ｐａｇｅ ｓｅｇｍｅｎｔａｔｉｏｎ ｕｓｉｎｇ ｔｈｅ ｂａｃｋｇｒｏｕｎｄ（バックグラウンドを使用したフレキシブルなページ分割）」、パターン認識に関する第１２回国際会議の議事録、ＩＥＥＥ−ＣＳプレス、１９９４年１０月９日−１２日、イスラエル、エルサレム、第２刊、ｐ３３９−３４４ Ｋ．Ｙ．Ｗｏｎｇ、Ｒ．Ｇ．Ｃａｓｅｙ、およびＦ．Ｍ．Ｗａｈｌ、「Ｄｏｃｕｍｅｎｔ ａｎａｌｙｓｉｓ ｓｙｓｔｅｍ（文書解析システム）」、ＩＢＭ Ｊ．Ｒｅｓ．、Ｄｅｖ ２６（１９８２）、ｐ６４７−６５６ Ｎ．Ｃｈｒｉｓｔｏｆｉｄｅｓ、「Ｇｒａｐｈ ｔｈｅｏｒｙ； ａｎ ａｌｇｏｒｉｔｈｍｉｃ ａｐｐｒｏａｃｈ（グラフ理論：アルゴリズムアプローチ）」、アカデミックプレス社、ニューヨーク、１９７５年

本発明の目的は、より効果的な、画像を分割するための方法および装置であって、特に、更なる処理ステップで簡単に使用できる分割画像の単純な記述を与える方法および装置を提供することである。

本発明の第１の態様によれば、前記目的は、以下の方法を提供することによって達成され、該方法は、
画像内のバックグラウンド領域に基づいて、頂点と頂点同士を接続する辺とを有するグラフを構成するステップを含み、前記グラフの辺は、画像のフィールドの輪郭を協働して描くフィールドセパレータに対応し、該方法はさらに、
画像の少なくとも一部を協働して完全に網羅する連続する最短サイクルのリストを構成するステップを含み、最短サイクルは、１つの頂点からグラフの辺を介してその同じ頂点に戻る閉じられた経路であって、且つ前記頂点から前記頂点に戻る考えられる全ての閉じられた経路のうち辺の加重総和が最も小さい経路として規定され、該方法はさらに、
前記リストの最短サイクルを画像のフィールドとして規定するステップを含む。

本発明の第２の態様によれば、前記目的は、ピクセルから成る画像を、画像のレイアウト要素に対応する複数のフィールドに分割する装置であって、前記ピクセルが、画素の強度および／または色を示す値を有し、該分割する装置が、画像を入力するための入力ユニットと、処理ユニットとを備え、該処理ユニットが、
画像内のバックグラウンド領域に基づいて、頂点と頂点同士を接続する辺とを有するグラフを構成するグラフ構成装置を含み、前記グラフの辺が、画像の領域の輪郭を協働して描くフィールドセパレータに対応し、該処理ユニットがさらに、
１つの頂点からグラフの辺を介してその同じ頂点に戻る閉じられた経路を、グラフ内で決定する経路検出モジュールを含み、該経路が、前記頂点から前記頂点に戻る考えられる全ての閉じられた経路のうち辺の加重総和が最も小さい経路であり、該処理ユニットがさらに、
画像の少なくとも一部を協働して完全に網羅する連続する最短サイクルのリストを構成するリストモジュールと、
前記リストの最短サイクルを画像のフィールドとして規定するフィールド規定装置とを含む、装置を用いて達成される。

本発明の第３の態様において、前記目的は、前記方法を実施するためのコンピュータプログラム製品を用いて達成される。

グラフの構造は、辺が、フィールドの境界部を簡潔に且つ効率的に表示するという利点を有する。また、グラフに基づくフィールドの解析は、コンピュータを利用すると効率的である。しかしながら、画像のグラフ表示からフィールドへのステップは、自明ではない。これは、フィールドを示す辺および頂点の固有の順序付けを、グラフが有していないためである。

最短サイクルのリストを構成するステップは、画像内でフィールドを決定する特に有利な方法である。これは、最短サイクルが、画像内の関連する多角形フィールドにほぼ対応する形状を既に有しているからである。そのようなフィールドは、通常、少なくともマンハッタンタイプのレイアウトで、すなわち、主に新聞で使用されるレイアウトで、垂直方向および水平方向のラインにより境界付けられるが、複雑な形状を有していても良い。

このように、最短サイクルのリストを構成すると、リストからフィールドを簡単に特定することができる。

本発明の一実施形態においては、辺の頂点間のユークリッド距離等の加重が、１つの辺に対して割り当てられる。この加重は、最短サイクルを決定する際に使用される。この実施形態において、最短サイクルは、実際に、ユークリッド用語で「最短の」サイクルである。また、加重の他の形式としては、例えば距離の階段関数も考えられる。

本発明の一実施形態において、前記最短サイクルのリストを構成するステップは、多くても１つの最短サイクルの一部となり得る１つの辺を選択し、前記辺の代わりに、前記辺の頂点同士を接続する最短経路を決定し、前記辺と前記最短経路とを組み合わせることを含む。このようにすれば、最短サイクルが効率的に見つけられる。

更なる実施形態において、前記最短サイクルのリストを構成するステップが、反復処理であり、最短サイクルを見つけた後、グラフは、最短サイクルの一部であり、且つ更なる最短サイクルの一部と成り得ない任意の辺を除去することにより減少され、その後、次の最短サイクルが決定される。この場合の利点は、最短サイクルのリストを構成する処理中にグラフが確実に減少し、これにより、計算労力を低減できるという点である。多くても１つの最短サイクルの一部となり得るそのような１つの辺は、例えば、グラフの外側の境界にある辺である。

実際に、画像のフィールドは、より大きなフィールド内に完全に含まれていても良い。その結果、これらのフィールドに対応する最短サイクルもこの特性を有する。しかし、分割後の更なる判定ステップで、これらのフィールドを別個に処理する必要がある。したがって、更なる実施形態において、フィールドを規定するステップは、第１の領域を囲む第１の最短サイクルが、第１の領域よりも小さい第２の領域を囲む第２の最短サイクルを完全に含んでいるか否かをチェックし、完全に囲んでいる場合には、囲まれた前記第１の領域から、囲まれた前記第２の領域を差し引くことから成る。

あるいは、最短サイクルのリストは、最短サイクルの前記囲まれた領域のサイズに基づいて区分けされ、区分けされたリストの順番で、最短サイクルに対応するフィールドに関し、任意の更なる画像処理が連続的に行なわれる。したがって、最も小さいフィールドが最初に処理される場合、これらのフィールドは、それが含まれるより大きなフィールドの処理から自動的に除外される。そのような更なる処理は、例えば読む順番の決定である。

本発明に係る装置の更に好ましい実施形態が、別の請求項に記載されている。

本発明のこれらの態様および他の態様は、以下の説明に一例として記載された実施形態および添付図面を更に参照することにより、明らかとなり、さらに解明される。

図面は、概略図であり、一定の縮尺で描かれたものではない。図面において、既に説明した要素に対応する要素が、同じ参照符号で示されている。

図１は、知られている分割システムによる３つの基本的なステップを有する典型的な分割方法の概略を示している。入力画像１１は、連結成分解析を使用して画像のピクセルを解析するＣＣＡ（Ｃｏｎｎｅｃｔｅｄ Ｃｏｍｐｏｎｅｎｔ Ａｎａｌｙｓｉｓ）モジュール１４で処理される。最初に、白黒文書、グレースケール文書、またはカラー文書、例えば新聞の一面であっても良いオリジナル画像が、好ましくはグレースケールで走査される。このグレースケール走査された画像は、フォアグラウンド値（例えば黒）またはバックグラウンド値（例えば白）を各ピクセルに割り当てるため、ハーフトーン化される。ＣＣＡモジュール１４は、同様の特性を有する隣り合うピクセルの連結成分（Ｃｏｎｎｅｃｔｅｄ Ｃｏｍｐｏｎｅｎｔ、ＣＣ）を検出することにより、画像中のフォアグラウンド要素を見つける。分割処理におけるこの第１のステップの例は、例えばＵＳ５，８５６，８７７に記載されている。ＣＣＡモジュールは、連結されたフォアグラウンドピクセルの連結成分であるＣＣオブジェクト１２を出力として形成する。ＬＡ（Ｌａｙｏｕｔ Ａｎａｌｙｓｉｓ）モジュール１５は、ＣＣオブジェクト１２を入力として受け、レイアウトオブジェクト１３を形成する。この場合、ＣＣオブジェクトを統合してグループ化することにより、テキストラインおよびテキストブロック等の大きなレイアウトオブジェクトが形成される。この段階中においては、ヒューリスティックス（経験則）を使用して、レイアウト要素をグループ化し、大きなレイアウト要素を形成する。これは、通常のボトムアップ処理における論理的なステップである。ＡＦ（Ａｒｔｉｃｌｅ Ｆｏｒｍａｔｉｏｎ）モジュール１６は、レイアウトオブジェクト１３を入力として受けて、記事形成（ａｒｔｉｃｌｅ ｆｏｒｍａｔｉｏｎ）により出力として記事１７を形成する。このモジュールにおいては、大きなエンティティを構成する幾つかのレイアウトオブジェクトが、一緒になってグループ化される。大きなエンティティは、オリジナル画像に適用されるレイアウトルールを使用してアセンブルされる。例えば、新聞の一面において、ＡＦモジュールは、その特定の新聞様式のレイアウトルールにしたがって、テキストブロックおよび画像のようなグラフィック要素をグループ化し、個々の記事を形成する。例えば西洋タイプの雑誌のレイアウト、科学のテキストのレイアウト、または日本の記事のレイアウトといった画像のレイアウトタイプの知識は、ルールに基づいた記事形成方法において使用でき、これにより、テキストブロックのグループ化を向上させることができる。

本発明によれば、以下に説明するように、分割に対して複数の更なるステップが加えられる。これらのステップは、画像を複数のフィールドに分割した後、１つのフィールド内で要素を検出すること、すなわち、更に小さい相互に関連する別個の項目によって構成される、レイアウトオブジェクトを形成することに関するものである。図２は、サンプルとしての日本の新聞を示している。このような新聞は、水平方向読み方向２２および垂直方向読み方向２１の両方を有するテキストラインを含む、特定のレイアウトを有している。検出された連結成分の従来のボトムアップグループ化処理における問題点は、グループ化をどの方向で進めるべきかが分からないという点である。そのため、バックグラウンドを処理してその頁（一面）のフィールドを検出する別個のステップにより、分割が増大される。その後、文字のグループ化を行なう前に、日本の新聞の各フィールドにおける読み方向が検出される。

この方法の一実施形態においては、例えば個々のコラムにおける黒ライン２３といったセパレータ要素が検出されて、複数のバックグラウンド要素に変換される。このような選択肢を用いれば、実際に連結される垂直および水平ラインを含む黒ライン２３の大きな要素を、様々なセパレータ要素に分離することができる。日本の新聞において、ラインは、レイアウトにおいてフィールドを分割するための非常に重要なオブジェクトである。これらのオブジェクトが、分離方向に沿うラインとして認識されることが求められる。この選択肢が無いと、これらのオブジェクトはグラフィックスとして分類される。この選択肢を使用すると、ラインを、様々な方向のセパレータ要素として、各分離方向毎に個別に扱うことができる。

図３は、オブジェクトを１つの方向に統合する基本的な方法を示している。この図は、知られている方向に向けられたレイアウトオブジェクト、例えば読む順番が分かっている状況におけるテキストブロックを見つけるためのＬＡモジュール１５の基本的な機能を示している。連結成分１２は、統計的な解析により最初の解析ステップ３１で処理され、これにより、算定閾値３２が得られる。２番目の分類ステップ３３においては、ＣＣ分類が補正され、これにより、補正された連結成分３４が得られる。この補正された連結成分が、３番目の統合ステップ３５で処理されることにより、文字がテキストラインに加えられ、その結果、テキストラインおよび他のオブジェクト３６が得られる。４番目のテキスト統合ステップ３７においては、テキストラインが、テキストブロック３８（および、可能であれば他のグラフィックオブジェクト）に加えられる。日本の新聞に関する要求事項に基づいて、従来のオブジェクトの統合は、少なくとも２つの読み方向に沿っていなければならず、そのため、前述した基本的な方法を改良しなければならない。

図４は、オブジェクトの分割および２方向統合を示している。図３の１方向処理に対して、新たな別個のステップが加えられている。最初の（前）処理ステップにおいては、画像のグラフ４１が構成される。フィールドセパレータを見つけることによりグラフを構成することについて以下に述べる。グラフにおいて、フィールドは、フィールド検出ステップ４２で、グラフの辺によって囲まれる領域を見出すことにより検出される。当該領域は、テキストブロック４７を含むフィールドとして分類される。テキストブロック４７においては（テキストブロック領域内にある補正された連結成分３４または連結成分４３を使用して）、ステップ４４で、読む順番４５が決定される。読み方向検出は、文書スペクトルに基づいている。テキストブロック４７のフィールド、含まれている連結成分、および読む順番４５を入力として使用して、ライン形成ステップ４６は、必要に応じて、見出された方向に沿って文字をラインに加える。

ここで、グラフ４１の構成について説明する。文書のグラフ表示は、走査のバックグラウンドを使用して形成される。走査におけるピクセルは、バックグラウンドとして（通常、白）或はフォアグラウンド（通常、黒）として分類される。白の大きな領域だけが、フィールドに関する情報を与えるため、例えば画像をダウンサンプリングすることにより、小さなノイズオブジェクトが除去される。１つのフォアグラウンド（黒）ピクセルを除去するため、更に、ダウンサンプリングされた画像から斑点が除去されても良い。

次の作業は、重要な白領域を抽出することである。最初のステップは、隣り合うバックグラウンドピクセルの１ピクセル高領域、所謂ホワイトランを検出することである。所定の最小長よりも短いホワイトランは、処理から除外される。

図５は、一例として、垂直方向で隣り合う白ピクセルの４つの水平方向のホワイトラン５１を示している。フォアグラウンド領域５３は、ホワイトラン５１を直接に取り囲むフォアグラウンドピクセルを有していると仮定する。「最大白長方形」は、隣り合うホワイトラン５１によって構成することができる最も大きな長方形領域、したがって、黒（フォアグラウンド）ピクセルを含んでいると延長することができない長方形白領域として規定される。最大白長方形５２は、垂直方向の破線によって示される長さ、及び４ピクセル分の幅を有する４つのホワイトラン５１に基づいて示されている。白長方形は、これを延長することができない場合に、いわゆる最大分離力を有する。そのような長方形は、より重要な白領域の更に小さい部分ではない。したがって、長方形５２は、４ピクセル分の幅を有する考えられる唯一の最大長方形である。３ピクセル分または２ピクセル分の幅を持つ更なる長方形を構成することができる。更なる例が図６に示されている。

白長方形の構成は、例えば水平方向および垂直方向の白長方形といったように、異なる分離方向で別個に行なわれる。垂直方向の白長方形は、画像を回転させ、且つ回転された画像における水平なホワイトランを検出することにより検出される。なお、画像のタイプまたは用途に応じて、斜め方向等の他の分離方向が選択されても良いことに留意されたい。

最大白長方形を構成するためのアルゴリズムは、以下の通りである。アルゴリズムの入力は、所定の画像から検出された全ての水平な１ピクセル高ホワイトラン（Ｗｈｉｔｅ Ｒｕｎ、ＷＲ）から成る。各ホワイトランは、一組の座標（（ｘ_１，ｙ_１），（ｘ_２，ｙ_２））によって特徴付けられる長方形として表わされる。ここで、ｘ_１およびｙ_１は、その左上角部の座標であり、ｘ_２およびｙ_２は右下角部の座標である。順序付けられたアクティブなオブジェクトＩＮＰＵＴ ＬＩＳＴに存在する各ホワイトランは、延長の可能性に関して検査される。延長の可能性は、ｐのラベルが付された所定のＷＲが、最大白長方形（Ｍａｘｉｍａｌ Ｗｈｉｔｅ Ｒｅｃｔａｎｇｌｅ、ＭＷＲ）を形成できるか否かといった態様で表わされる。延長の可能性が偽である場合には、ｐが既に最大のものであり、ｐは、アクティブＩＮＰＵＴ ＬＩＳＴから削除されるとともに、アクティブＲＥＳＵＬＴ ＬＩＳＴに書き込まれる。延長の可能性が真である場合には、ｐで始まる全てのＭＷＲが構成されるまで、延長のための検査が繰り返される。その後、ｐがＩＮＰＵＴ ＬＩＳＴから削除され、ｐから得られる全てのＭＷＲが、アクティブＲＥＳＵＬＴ ＬＩＳＴに書き込まれる。ＩＮＰＵＴ ＬＩＳＴからの全ての白長方形が処理されると、ＲＥＳＵＬＴ ＬＩＳＴに全てのＭＷＲが含まれるようになる。アルゴリズムの効率を高めるため、ＩＮＰＵＴ ＬＩＳＴにおいてｙの値がソートされる。まず最初に、水平方向のＷＲ、すなわち、高さよりも幅が大きいホワイトランに関してアルゴリズムが適用される。そして、画像を９０°回転させた後、垂直方向のＷＲに対してアルゴリズムを適用することができる。

一実施形態において、最大長方形を構成するためのアルゴリズムは、以下の通りである。まず、長方形データがリンクリストとして記憶される。この場合、長方形データには、少なくとも長方形の頂点の座標が含まれている。ＩＮＰＵＴ ＬＩＳＴおよびＲＥＳＵＬＴ ＬＩＳＴも、リンクリストとして記憶される。このリンクリストには、少なくとも３つの要素、すなわち、白長方形の数、リンクリスト内の最初および最後の要素のポインタが含まれている。次に、複数のステップが実行される。すなわち、ＩＮＰＵＴ ＬＩＳＴをアクティブにして、ＲＥＳＵＬＴ ＬＩＳＴを開始し、選択された長方形の一次的な座標のためのＢＵＦＦＥＲを開始する。順序付けられたアクティブなＩＮＰＵＴ ＬＩＳＴにあるもののうち、ｐ_１のラベルが付された最初の白長方形から始める。リスト中の次の白長方形にｐ_２のラベルが付される。ＩＮＰＵＴ ＬＩＳＴ中の各白長方形毎に、ｐ_１が延長の可能性を有しているか否かを検討する。アクティブな白長方形ｐ_１に関し、順序付けられたアクティブなＩＮＰＵＴ ＬＩＳＴ中で以下の条件を満たすｐ_ｎｊ，ｊ＝１，．．．．，ｌのラベルが付された最初のものを見つける。

この検索により、｛ｐ_ｎ１，ｐ_ｎ２，．．．．ｐ_ｎｌ｝のセットが得られる。このセット｛ｐ_ｎ１，ｐ_ｎ２，．．．．ｐ_ｎｌ｝が空でない場合にだけ、ｐ_１が延長の可能性を有していると言われる。

ｐ_１が延長の可能性を有していない場合には、ｐ_１が最大白長方形である。ｐ_１をＲＥＳＵＬＴ ＬＩＳＴに書き込んで、ｐ_１をＩＮＰＵＴ ＬＩＳＴから削除し、ｐ_２に関して処理を進める。

ｐ_１が延長の可能性を有している場合には、延長処理をｐ_１に適用する。ｐ_２に関して処理を進める。なお、ｐ_１がそれ自体最大であっても延長の可能性を有し得る。延長処理は以下の通りである。まず、ｐ_１が延長の可能性を有していると仮定すると、セット｛ｐ_ｎ１，ｐ_ｎ２，．．．．ｐ_ｎｌ｝が存在する。延長処理は、｛ｐ_ｎ１，ｐ_ｎ２，．．．．ｐ_ｎｌ｝の各要素に対して一貫して適用される。長方形ｐ_ｎｊ，ｊ＝１，．．．．，ｌを用いて延長可能な白長方形ｐ_１に関して、以下の座標を有する新たな長方形ｐ_１，ｎｊを構成する。

ｐ_１，ｎｊ，ｊ＝１，．．．．，ｌの座標を「座標」バッファに書き込む。ここで、ｐ_１，ｎｊに関して延長可能性の検査を繰り返す。検査が真である場合には、ｐ_１，ｎｊが最大である。ｐ_１，ｎｊをＲＥＳＵＬＴ ＬＩＳＴに書き込み、さもなければ、ｐ_１，ｎｊを延長する。

延長処理をｐ_１，ｎｊに適用する前に、吸収作用に関してｐ_１およびｐ_ｎｊをチェックする。ｐ_１，ｎｊを用いた吸収作用に関するｐ_１およびｐ_ｎｊの検査は、以下の通りである。吸収作用とは、ｐ_１（ｐ_ｎｊ）又はこれらの両方が、ｐ_１，ｎｊに完全に含まれている状態を意味する。座標において、このことは、以下の状態を意味する。

ここで、ｋ＝１，ｎ_ｊ，ｊ＝１，．．．，ｌである。

状態がｐ_１に関して真である場合には、ｐ_１はｐ_１，ｎｊによって吸収される。ｐ_１をＩＮＰＵＴ ＬＩＳＴから除去する。状態がｐ_ｎｊに関して真である場合には、ｐ_ｎｊはｐ_１，ｎｊによって吸収される。ｐ_ｎｊをＩＮＰＵＴ ＬＩＳＴから除去する。

アルゴリズムでは、長方形の幅が高さよりも大きく、したがって、長方形が、主として水平方向であると仮定される。垂直方向のＭＷＲを構成するため、オリジナルの２値画像が９０°時計周りに回転される。回転された画像に関して前述したアルゴリズムが繰り返される。その結果、オリジナル画像において全ての垂直方向のＭＷＲが構成される。

図６は、最大白長方形の構成を示している。水平方向のｘ軸および垂直方向のｙ軸に沿って、ピクセル座標が表わされている。４つのホワイトラン６１が、図の左側に示されている。ホワイトラン（ＷＲ）は、その上角部および下角部の座標が、以下の座標に対応する長方形として描かれている。

これらのホワイトランによって全ての最大白長方形が構成される。図の右側部分には、結果として得られる５つの最大白長方形（ＭＷＲ）が、６２、６３、６４、６５、および６６で示されている。図示された５つのＭＷＲは、図の左側部分に示されたＷＲにおけるＭＷＲの完全なセットである。構成アルゴリズムは以下の通りである。

ＩＮＰＵＴ ＬＩＳＴに４つのホワイトラン６１を含ませる。ＩＮＰＵＴ ＬＩＳＴからの最初の要素は、ＷＲ_１（（１０，１），（５０，２））である。ＷＲ_１にｐ_１のラベルを付ける。前述したように、延長の可能性に関してｐ_１を検査する。延長における第１の候補は、ＷＲ_２（（１０，２），（５０，３））である。ＷＲ_２にｐ_１のラベルを付ける。前述した延長に関する方式にしたがってｐ_ｎ１を用いてｐ_１を延長する。これにより、座標（（１０，１），（５０，３））を有する新たな長方形ｐ_１，ｎ１が与えられる。ｐ_１，ｎ１を用いた吸収作用に関してｐ_１およびｐ_ｎ１を検査する。以下の通り、吸収検査により、ｐ_１およびｐ_ｎ１の両方が、ｐ_１，ｎ１によって吸収される。したがって、ｐ_１およびｐ_ｎ１をＩＮＰＵＴ ＬＩＳＴから削除する。ｐ_１，ｎ１に関して処理を進める。延長の可能性に関してｐ_１，ｎ１を検査する。これにより、第１の候補ＷＲ_３（（５，３），（３０，４））が与えられる。ＷＲ_３にｐ_ｔ１のラベルを付ける。延長に関する方式にしたがってｐ_ｔ１を用いてｐ_１，ｎ１を延長する。その結果、座標（（１０，１），（３０，４））を有する新たな長方形ｐ_{（１，ｎ１），ｔ１}が得られる。ｐ_{（１，ｎ１），ｔ１}を用いた吸収作用に関してｐ_ｔ１を有するｐ_１，ｎ１を検査する。検査は失敗する。

ｐ_{（１，ｎ１），ｔ１}に関して延長の可能性の検査を繰り返す。検査は失敗する。すなわち、ｐ_{（１，ｎ１），ｔ１}は延長の可能性を有していない。このことは、ｐ_{（１，ｎ１），ｔ１}が最大であることを意味する。座標（（１０，１），（３０，４））を有するｐ_{（１，ｎ１），ｔ１}をＲＥＳＵＬＴ ＬＩＳＴに書き込む。

ｐ_１，ｎ１に関して再び処理を進め、延長の可能性に関してｐ_１，ｎ１を検査する。第２の候補ＷＲ_４（（４０，３），（６０，４））が見出される。ＷＲ_４にｐ_ｔ２のラベルを付ける。延長に関する方式にしたがってｐ_ｔ２を用いてｐ_１，ｎ１を延長する。その結果、座標（（４０，１），（５０，４））を有する新たな長方形ｐ_{（１，ｎ１），ｔ２}が得られる。

ｐ_{（１，ｎ１），ｔ２}を用いた吸収作用に関してｐ_ｔ２を有するｐ_１，ｎ１を検査する。検査は失敗する。すなわち、吸収がない。ｐ_{（１，ｎ１），ｔ２}に関して延長の可能性の検査を繰り返す。検査は失敗する。すなわち、ｐ_{（１，ｎ１），ｔ２}は延長の可能性を有していない。このことは、ｐ_{（１，ｎ１），ｔ２}が最大であることを意味する。座標（（４０，１），（５０，４））を有するｐ_{（１，ｎ１），ｔ２}をＲＥＳＵＬＴ ＬＩＳＴに書き込む。

延長の可能性に関してｐ_１，ｎ１を再び検査する。検査は失敗し、ｐ_１，ｎ１が最大である。座標（（１０，１），（５０，３））を有するｐ_１，ｎ１をＲＥＳＵＬＴ ＬＩＳＴに書き込む。

ＩＮＰＵＴ ＬＩＳＴに戻る。この段階におけるＩＮＰＵＴ ＬＩＳＴは、２つのホワイトラン、すなわち、ＷＲ_３：（（５，３），（３０，４）），ＷＲ_４：（（４０，３），（６０，４））を含んでいる。ＷＲ_３から開始して、これにｐ_２のラベルを付ける。ｐ_２に関して延長の可能性の検査を繰り返す。検査は失敗し、ｐ_２が最大である。座標（（５，３），（３０，４））を有するｐ_２を、ＲＥＳＵＬＴ ＬＩＳＴに書き込む。ＩＮＰＵＴ ＬＩＳＴからｐ_２を除去する。ＷＲ_４に関して処理を進め、これにｐ_３のラベルを付ける。ｐ_３に関して延長の可能性の検査を行なうことにより、ｐ_３が最大であることが分かる。座標（（４０，３），（６０，４））を有するｐ_３をＲＥＳＵＬＴ ＬＩＳＴに書き込む。ＩＮＰＵＴ ＬＩＳＴからｐ_３を除去する。最終的に、ＲＥＳＵＬＴ ＬＩＳＴは、５つの最大白長方形、すなわち、図６に６４で示されるＭＷＲ_１：（（１０，１），（５０，３））と、６２で示されるＭＷＲ_２：（（１０，１），（３０，４））と、６３で示されるＭＷＲ_３：（（４０，１），（５０，４））と、６５で示されるＭＷＲ_４：（（５，３），（３０，４））と、６６で示されるＭＷＲ_５：（（４０，３），（６０，４））とを含んでいる。

図７は、本発明にかかる方法における次のステップ、すなわち、最大白長方形をオーバーラップさせるクリーニングステップを示している。このクリーニングステップにおいて、オーバーラップする複数の最大白長方形は、後で詳述するように、オリジナルの最大白長方形の最も関連する特性を組み合わせる、１つの所謂「情報提供最大長方形」（Ｉｎｆｏｒｍａｔｉｖｅ Ｍａｘｉｍａｌ Ｒｅｃｔａｎｇｌｅ、ＩＷＲ）に統合される。

クリーニングは、サイズおよび空間的な関係をチェックする等のステップを更に含んでいる。図７の上側の部分は、一例として、２つの最大白長方形ＭＷＲ１およびＭＷＲ２を示している。これらの対は、図の下側の部分に示されるように、クリーニングステップにおいて、１つの情報提供白長方形ＩＷＲに統合される。オーバーラップを検知する処理および統合する処理は、関連する対をもはや形成することができなくなるまで繰り返される。対を形成する基準は、オーバーラップ領域のサイズであっても良い。

また、クリーニングステップは、薄い或は短い長方形、すなわち、アスペクト比が所定の値を下回る長方形を除去することを含んでいても良い。除去する基準は、画像のタイプに基づいていても良い。例えば、所定のピクセル数を下回る幅は、テキストラインのセパレータを示し、フィールドの分離に関係しない。特定の値を下回る長さは、フィールドの期待されるサイズに関連しない。

クリーニングステップのためのアルゴリズムは、以下の通りである。クリーニング処理の開始は、図５および図６に関して前述したように構成されるＭＷＲのセット全体である。クリーニング処理は、情報を提供しないＭＷＲを廃棄するべく適用される。このため、情報を提供しないことに関する尺度が規定される。例えば、長いＭＷＲは、短いものよりも多くの情報を与える。低いアスペクト比は、情報提供量が少ない正方形を多かれ少なかれ示す。また、例えば２つのテキストラインを分離する極めて薄い長方形は、除外しなければならない。最初に、全てのＭＷＲは、その高さと幅との間の比が計算されることにより、水平方向、垂直方向、あるいは正方形であるとして分類される。正方形のＭＷＲは、その情報提供性が無いことにより、削除される。残りの水平方向および垂直方向のＭＷＲに関しては、以下の３つのステップから成るクリーニング技術が適用される。

長さまたは幅が所定の値を下回る各ＭＷＲが削除される。

長い辺の長さを短い辺の長さで割った比として規定されるアスペクト比（ＡＲ）が、所定の値を下回る各ＭＷＲが削除される。

互いにオーバーラップする水平方向（または垂直方向）のＭＷＲ_１（（ｘ_１，ｙ_１），（ｘ_２，ｙ_２））および水平方向（または垂直方向）のＭＷＲ_２（（ａ_１，ｂ_１），（ａ_２，ｂ_２））から成る各対毎に、以下の座標を用いて、情報提供白長方形ＩＷＲが構成される。
（ａ）水平方向のオーバーラップ

（ｂ）垂直方向のオーバーラップ

この処理は、オーバーラップするＭＷＲから成る全ての対に関して繰り返される。ここで、ＭＷＲのセットは、情報提供白長方形ＩＷＲを含んでいる。これらのＩＷＲは、レイアウト要素に対応する複数のフィールドに、画像を分割するアルゴリズムのための開始点を形成する。ＩＷＲは、有力なフィールドセパレータであり、そのため、「分離要素」と呼ばれる。アルゴリズムは、ＩＷＲを使用して、画像の地理的記述へと更に処理するためにグラフを構成する。

図８は、新聞の一面におけるそのようなグラフを示している。画像は、ダウンサンプリングされた新聞の一面のデジタル画像８０を示している。オリジナルテキストは、図２に対応するダウンサンプリングされたバージョンにおいて黒で見ることができる。分離要素を構成する情報提供長方形ＩＷＲが、灰色で示されている。グラフの構成のため、水平方向および垂直方向の白ＩＷＲによって構成される分離要素の交差部が測定される。２つのＩＷＲの交点は、頂点すなわちグラフの頂点８１を示す小さな黒色正方形で表わされている。一面内でフィールドを分離するラインを示す辺８２は、頂点８１から成る対を「フィールドセパレータ」によって接続することにより構成される。グラフの辺８２が白で示されている。辺の２つの頂点間の距離、すなわち長さは、更なる処理のために加重として辺に対して割り当てられる。他の実施形態においては、異なるパラメータが使用され、例えばピクセルの色等の加重が割り当てられる。グラフを構成するためのアルゴリズムは、以下の通りである。

初めに、ＩＷＲに関して以下の表記法および定義が与えられる。Ｒ＝｛ｒ_１，．．．，ｒ_ｍ｝が空でなく、また全てのＩＷＲの有限のセットが所定の画像ｌから得られると仮定する。ここで、各ＩＷＲは、それぞれ、その左上角部および右下角部のｘ座標およびｙ座標（（ｘ_１ ^（τ），ｙ_１ ^（τ）），（ｘ_２ ^（τ），ｙ_２ ^（τ））），τ＝１，２，．．．，ｍによって特定される。各長方形ｒ_τは、その高さと幅との比に基づいて、水平方向、垂直方向、あるいは正方形として分類される。Ｈ＝｛ｈ_１，．．．ｈ_ｌ｝，Ｖ＝｛ｖ_１，．．．，ｖ_ｋ｝，Ｓ＝｛ｓ_ｉ，．．．，ｓ_ｄ｝は、以下の関係を成すように、水平方向、垂直方向、および正方形のＩＷＲのサブセットを示す。

ここで、以下が仮定される。

また、Ｓの内容は無視され、ＨおよびＶのサブセットだけが使用される。これは、多くの場合、テキストブロックまたは非テキストブロックの境界を形成する白空間が、細長い垂直方向または水平方向領域であるといった考えに基づいている。ｈが座標（（ｘ_１，ｙ_１），（ｘ_２，ｙ_２））を有するＨの一部であるとし、また、ｖが座標（（ａ_１，ｂ_１），（ａ_２，ｂ_２））を有するＶの一部であるとする。この時、以下の条件の下、ｈおよびｖはオーバーラップを有する。

オーバーラップの場合のｈおよびｖの交点により、以下の座標によって規定される唯一の点Ｐが得られる。

ＩＷＲにおいては、考えられる全てのタイプのオーバーラップから、２つのオーバーラップだけが生じる。すなわち、長方形となるオーバーラップと、点となるオーバーラップだけが生じる。ラインのオーバーラップは生じない。これは、ラインのオーバーラップがＭＷＲの概念と矛盾するからである。

図９は、最大長方形の２つのタイプの交差部を示している。グラフを構成するため、垂直方向および水平方向の情報提供最大長方形の交点が決定され、これにより、グラフの頂点の位置が見出される。すなわち、頂点の正確な座標が決定される。図の左側部分は、垂直方向のＩＷＲであるｖと、水平方向のＩＷＲであるｈとの交差部の第１のタイプを示している。このタイプの交差では、交差部の中心が点Ｐである長方形領域８８が形成される。図の右側部分は、垂直方向のＩＷＲであるｖと水平方向のＩＷＲであるｈとの交差部の第２のタイプを示している。このタイプの交差では、交差部の中心がＰ’である１つの交点８９が生じる。

交点に基づいてグラフを構成するアルゴリズムは、以下の通りである。

Ｐ＝｛ｐ_１，．．．，ｐ_Ｎ｝は、垂直方向のＩＷＲおよび水平方向のＩＷＲの全ての交点のセットを示している。この場合、Ｐの中の各ｐは、そのｘ座標およびｙ座標（ｘ_ｐ，ｙ_ｐ）によって特定される。ここで、ｐ＝１，．．．．Ｎである。セットＰが見出され、Ｇ＝（Ｘ，Ａ）がＰに対応する方向性が無いグラフであるとする。グラフＧ＝（Ｘ，Ａ）は、交点に対して直接に関係する有限の数の頂点Ｘと、交点間の関係を描く有限の数の辺Ａとから成る。これは、数学的には、以下のように表わされる。

ここで、

ここで、ｄ_ｉｊは、点ｉと点ｊとの間のユークリッド距離を示している。また、４連鎖接続（４−ｃｈａｉｎ ｃｏｎｎｅｃｔｅｄ）は、４つの可能な移動方向で長方形ブロックの頂点が接続されることを意味している。前述した２つの点ｉ，ｊは、ｍｉｎｄ_ｉｊを有する４つの接続連鎖コードによって１方向に動き回ることにより、これらの点に達し得る場合には、４連鎖接続である。

ここで、構成されたグラフを更に処理して、グラフの内部の領域をテキストブロックとして分類し、あるいは、画像のタイプに応じて同様の分類を行なっても良い。一実施形態において、グラフは、解析において、例えば黒ラインまたは破線／点線等のパターン化されたラインといったフォアグラウンドセパレータを含めることにより増大される。また、検出される写真またはグラフィックオブジェクトのエッジを、解析に含めることもできる。

また、この分割方法は、フォアグラウンドセパレータを除去するステップを含んでいても良い。まず最初に、フォアグラウンドセパレータが認識されて、１つのオブジェクトとして再構成される。パターン化されたラインを構成する成分は、要素ヒューリスティックス、空間的関係ヒューリスティックス、およびラインヒューリスティックスを解析することにより、すなわち、１方向で組み合わされた要素を構築し且つそれがラインとして分類するか否かを検出することにより接続される。パターン化されたラインから実線を再構成するための更なる方法は、ダウンサンプリングおよび／または「Ｄｏｃｕｍｅｎｔ ａｎａｌｙｓｉｓ ｓｙｓｔｅｍ（文書解析システム）」ＩＢＭ Ｊ．Ｒｅｓ．Ｄｅｖ ２６（１９８２）６４７−６５６において、Ｋ．Ｙ．Ｗｏｎｇ，Ｒ．Ｇ．Ｃａｓｅｙ，Ｆ．Ｍ．Ｗａｈｌにより説明されている、ラン・レングス・スムージング・アルゴリズム（ＲＬＳＡ）を使用することである。フォアグラウンドセパレータの検出後、フォアグラウンドセパレータは、バックグラウンドピクセルに取って代えられる。その結果、より大きな最大白長方形を構成することができ、あるいは、バックグラウンドピクセル特性を使用して、バックグラウンドセパレータを見出す任意の他の適した方法をサポートすることができる。 図１１は、画像のグラフ表示における最短サイクルのリストを形成に基づき、ピクセル画像内でフィールドを規定するための本発明に係る方法のフローチャートを示している。基本的に、この方法は、最初に、頂点と頂点同士を接続する辺とを有するグラフの形態を成すピクセル画像の数学的な記述を構成する。その後、前記グラフは、考えられる最も短い周長を有する複数の連続する領域、すなわち、グラフの辺によって形成される考えられる最も短いサイクル（最短サイクル）により輪郭が描かれる複数の領域に分割される。最後に、（数学的に規定された）最短サイクルに対応して、オリジナル画像のピクセルドメイン内にフィールドが規定される。考えられる最短サイクルをグラフ内で探すこのような方法は、対応する計算が簡単であり且つ速いという利点を有している。しかし、第１の最短サイクルが、更に小さい第２の最短サイクルを完全に含んでいる場合には、結果が常に完全に正しいとは限らない。これについては、例えば、最短サイクル１０４ａが、更に小さい２つの最短サイクル（略長方形１０３ａ、１０３ｂ）を完全に含んでいる図１２ｂを参照のこと。以下、この作用によって問題が生じないことを明らかにする。

ＧＲＡＰＨステップＳ１においては、画像内でフィールドを分割するバックグラウンド領域に対応する辺を有するグラフが構成される。グラフの頂点は、画像内のフィールドの角の点に対応している。画像内のフィールドは、例えば新聞の一面のテキストブロックである。基本的に、フィールドは、垂直方向および水平方向の境界を主に有する多角形領域であるが、必ずしも長方形ではない。例えば、特定の状況においては、Ｌ字形状のテキストブロックが頻繁に現われる。

以上、図８および図９を参照しながら、グラフを構成する一例について説明してきた。オリジナル画像内のフィールドの実際の境界に対応する辺をグラフが有している場合には、グラフを構成してフィールドを有する画像を表わす任意の他の方法が適している。なお、グラフ内でフィールドを見つける作業は、そのフィールドを境界付けている辺および／または頂点を特定することから成ることに留意されたい。これは、例えばフィールドを示す辺および頂点の固有の順序付けをグラフが有していないため、グラフからはっきりと分からない。また、以下のステップが行なわれる。

ＷＥＩＧＨＴステップＳ２においては、各辺に対して加重が割り当てられる。分割されるレイアウトタイプ画像のグラフにおける辺の加重は、頂点間のユークリッド距離、すなわち、オリジナル画像におけるその長さであっても良い。画像が、マップ等の異なる構造を表わす異なるタイプの用途における実施形態において、加重に適した指標は、移動時間またはコスト等の異なるパラメータであっても良い。加重割り当てステップにおいて、各辺における加重は、計算されるとともに、グラフデータ構造に加えられる。

次のステップにおいては、最短サイクルが決定される。最短サイクルは、頂点を接続する辺によって閉じられたグラフ内の経路として規定される。この経路は、関連する辺の加重を加えることによって累積された加重総和が最も小さい。ＩＮＩＴステップＳ３においては、初期的に中身が空の最短サイクルのリストが形成され、最初の開始点、頂点、または辺がグラフ内で決定される。例えばこの目的のため、グラフが区分され、最初の開始点が、グラフの左上角部の頂点となるように設定される。この時、処理は、ステップＳ４、Ｓ５、Ｓ６、およびＳ７から成るループに入る。このループにおいては、予め選択された開始点を発端として最短サイクルが構成される。ループの最後において、ＮＥＸＴステップＳ７は、次の最短サイクルを見つけるための新たな開始点を選択する。候補開始点として依然として利用できるためのグラフの頂点または辺の状態は維持される。候補開始点が残っていない場合には、ステップＳ７は、ループを終了させ、次のステップＳ８に進む。

ループ内において、ＣＹＣＬＥステップＳ４は、選択された開始点のための最短サイクルを決定する。最短サイクルアルゴリズムは、考えられる全てのサイクルを構成するとともに、セットから最短サイクルを選択しても良い。見つけられた最短サイクルは、ＮＥＷステップＳ５において、既に見つけられた最短サイクルのリストに対して新しいか否かが判断される。最短サイクルが新しい場合、最短サイクルのリストに最新の最短サイクルを加えるために、ＡＤＤステップＳ６が行なわれる。以下、最短サイクルを構成し、開始点を選択して維持し、新たな最短サイクルのリストを構成するのに適したアルゴリズムについて説明する。

更なる候補開始点が利用できないことをＮＥＸＴステップＳ７が検出する時点で、リストは、グラフに形成できる最短サイクルを含んでいる。また、ＮＥＸＴステップＳ７は、グラフの所要の特定部分が、完全に処理されているか否かを検出するために設けられても良い。そのような所要の部分は、グラフの特定部分に含まれるフィールドだけを構成する必要があることが用途から分かっている場合に、規定することができる。その時、最短サイクルのリストは、グラフのその部分だけに最短サイクルを含んでいる。

ＦＩＥＬＤステップＳ８においては、最短サイクルのリストに基づいてフィールドが規定される。フィールドは、フィールドを囲む最短サイクルの頂点および辺によって表わされる多角形である。また、ステップＳ８は、他の更に小さい最短サイクルを含む最短サイクルを検出し、且つその場合における最初の結果を補正する追加のステップを含んでいても良い。

処理は、ＥＮＤステップＳ９で終了する。

一実施形態において、ＦＩＥＬＤステップＳ８は、フィールドを規定するための追加のステップを含んでいる。最初に、大きな領域を囲む最短サイクルが、第２の最短サイクルによってそれ自体が囲まれる更に小さな領域を更に含んでいるか否かが決定される。対応するより大きなフィールドは、囲まれたより大きな領域から、囲まれたより小さな領域を差し引くことにより補正される。あるいは、第２の最短サイクルに対応するフィールドは、第１の最短サイクルに対応するフィールドを処理する前に処理される。後者を処理する場合、第１の領域が省かれる。以下、図１２ｂを参照しながら、追加のステップについて更に説明する。

図１２ａおよび図１２ｂは、グラフおよびグラフ中のサイクルを示している。グラフは、辺１００および頂点１０１によって構成されている。辺１００によって囲まれる各領域は、グラフによって表わされるオリジナル画像のフィールドに対応している。図１２ａは、テキスト領域１０５の周りの最短サイクル１０２を示している。図１２ｂは、長方形の最短サイクル１０４ａによって囲まれた更なるテキスト領域１０４を有する、更なるグラフを示している。領域１０４は、更により小さいテキスト領域１０３ａおよび第２のより小さい領域１０３ｂを更に囲んでいる。また、これらのより小さい領域も、最短サイクルによって囲まれている。この状況は、他の２つの方法のうちの一方によって処理されても良い。

第１の方法においては、読み方向などのフィールドの更なる特性を決定する前に、領域が、その囲まれる領域の大きさに基づいて区分される。特に、より小さいテキストブロックの読む順番が、最初に決定される。より大きな最短サイクルの処理中、より小さなサイクルの領域は、その領域の文字が、より大きな領域の読み方向の決定に影響を与えないように省かれる。

第２の方法において、ＦＩＥＬＤステップＳ８は、そのような囲まれ状態を検出してそれを補償することを含む。第１のサブステップにおいては、より大きな最短サイクルが、より小さな最短サイクルを含んでいるか否かが決定される。最短サイクルの囲まれた領域および／または場所を比較することにより、囲まれ状態が分かる。この目的のため、共有されている辺または頂点を使用しても良い。第２のサブステップにおいては、より小さい最短サイクルの囲まれた領域が、より大きい最短サイクルの囲まれた領域から差し引かれる。

幾つかの方法で、例えば以下のアルゴリズムを使用して、最短サイクルを検出することができる。

図１３ａおよび図１３ｂは、最短サイクル検出を示している。開始辺１０８の選択に基づいて、最短サイクルを見つける方法が示されている。図１３ａには、頂点ｕと頂点ｖとの間の開始辺１０８を除去することにより、一時的に減るグラフが示されている。この時、頂点ｕから頂点ｖに向かうグラフの最短経路が構成される。図１３ｂは、辺１０９のリセットによる最短サイクルの構成を示している。このようにして、辺および頂点ｕ、ｖを含む最短サイクルが見つけられる。グラフの２つの頂点間の最短経路を構成するのに適したアルゴリズムは、１９７５年にニューヨークのアカデミックプレス社から発行された、Ｎ．Ｃｈｒｉｓｔｏｆｉｄｅｓによる「Ｇｒａｐｈ ｔｈｅｏｒｙ； ａｎ ａｌｇｏｒｉｔｈｍｉｃ ａｐｐｒｏａｃｈ（グラフ理論：アルゴリズムアプローチ）」、特にこの中で説明されているＤｉｊｋｓｔｒａのアルゴリズムで見出すことができる。その後、開始点として辺を取ることにより、グラフの全体を網羅する最短サイクルのリストが構成される。一実施形態において、最短サイクルのリストの構成は、最短サイクルが未だリスト内に含まれていない場合には、その最短サイクルをリスト上に含めることだけから成る。

所謂グラフ減少方法（ｇｒａｐｈ ｒｅｄｕｃｔｉｏｎ ｍｅｔｈｏｄ）を適用すると、計算量を大幅に抑えることができる。この方法によれば、検出される最短サイクルがグラフから除去され、減少されたグラフ内で、好ましくは除去されたサイクルの隣で、最短サイクルの検出が続けられる。このようにして、グラフは、その残りがなくなるまで、連続的に減少される。

グラフ減少方法を使用してリストを構成するのに適したアルゴリズムが、図１４に示されている。第１のステップ１１１において、各辺には、それが一部を成し得る最短サイクルの最大数を示す見込み数が割り当てられる。通常、グラフの外側の境界にある辺に関しては見込み数１が割り当てられ、グラフの境界の内側にある辺に関しては見込み数２が割り当てられる。左上領域には、検出された最短サイクル１１５が示されている。検出されると直ぐに、この最短サイクルに含まれる４つの辺の見込みサイクル数が１だけ減少される。第２のステップ１１２においては、見込み数が０である左上の辺は、グラフから除去される。サイクル１１５の領域の右に隣接する第２の領域で、第２の最短サイクル１１６が検出される。第３のステップ１１３においても再び、見込み数が減少され、更に２つの辺がグラフから除去される。左側の２番目の横列で、第３の最短サイクル１１７が検出される。

最短サイクルが検出される度に、その最短サイクルは、画像における最短サイクルのリストに加えられる。最短サイクルを検出し且つグラフを減少する処理は、辺が残らなくなるまで続けられる。なお、グラフのデッドエンドも除去されることに留意されたい。これは、グラフのデッドエンドがサイクルの一部になり得ないからである。

方法の他の実施形態において、最短サイクルの決定は、最小スパニングツリー（ｍｉｎｉｍａｌ ｓｐａｎｎｉｎｇ ｔｒｅｅ）を構成することによって行なわれる。そのような最小スパニングツリーは、根元の頂点から他の頂点へと向かう最短経路の全てを表わしている。根元の頂点ｕは、除去された辺の最初の頂点である。ツリーは、除去された辺の他の頂点ｖへの最短経路を見つけるために使用される。ポインタのデータ構造は、最小スパニングツリーを表わすために使用される。ツリーは、繰り返し毎に頂点を１つ加えることにより構成される。この頂点は、未だツリー内にない全ての頂点の根元の頂点への最短距離を有している。新たな各頂点は、既にツリー内に含まれている全ての頂点の隣をチェックするとともに、隣が未だツリー内にない場合には、根元までの距離を計算することにより見つけられる。頂点ｖがツリーに加えられると直ちに、処理が停止される。現在の繰り返しの隣を持つ別個のリストを維持できれば有益である。

また、最小スパニングツリーは、グラフを示すデータ構造の変数で表わされても良く、特にグラフの頂点要素に関連付けられても良い。各頂点要素は、ツリーを記憶するための追加の変数を有している。新たな最短サイクルを見つけるためには、変数を初期化しなければならない。一実施形態において、変数は個別に初期化されないが、最初のツリーが構成される前に、初期化される各頂点に別個の変数が加えられる。その後の各ツリー毎に、異なる値が追加の変数で記憶され、現在のツリーの一部として各頂点を特定する。グラフの変数を使用してツリーを構成することは、別個のデータ構造を、最小スパニングツリーのために維持する必要がないため有利である。

図１０は、本発明に係る方法を使用して画像を分割するための装置を示している。この装置は、デジタル画像を入力するための入力ユニット９１を有している。入力ユニットは、紙からの画像を走査する電子光学スキャナ等の走査ユニット、インターネット等のネットワークから画像を受けるデジタル通信ユニット、または光ディスクドライブ等の記録キャリアからデジタル情報を検索する再生ユニットを備えていても良い。入力ユニット９１は、記憶ユニット９２と協働する処理ユニット９４に接続されている。処理ユニット９４は、汎用コンピュータ中央処理ユニット（ＣＰＵ）および支援回路を備えていても良く、前述した分割を行なうためのソフトウェアを使用して動作する。また、処理ユニットは、画像内のバックグラウンド領域に基づいてグラフを構成するためのＧＲＡＰＨモジュールと、グラフの辺に対して加重を割り当てるためのＷＥＩＧＨＴモジュールと、グラフ内で閉じられた経路すなわちサイクルを辺によって決定し、且つそこから最短サイクルを決定するためのＰＡＴＨモジュールと、連続する最短サイクルのリストを構成するためのＬＩＳＴモジュールと、リストの最短サイクルを画像のフィールドとして規定するためのＦＩＥＬＤモジュールとを有している。これらのモジュールが、処理シュニット９４内でプログラムモジュールとして実現されても良いことは言うまでもない。このため、これらのモジュールは、図１０では破線によって示されている。また、処理ユニットは、キーボード、マウス装置、またはオペレータボタン等の制御手段を備えた、ユーザインタフェース９５を有していても良い。処理ユニットの出力部は、ディスプレイユニット９３に接続されている。一実施形態において、ディスプレイユニットは、処理された画像を紙上に出力するための印刷ユニット、または磁気テープや光ディスク等の記録キャリア上に分割された画像を記憶する記録ユニットである。

分割されるデジタル画像として日本の新聞の一面を使用する実施形態によって、本発明を主に説明してきたが、本発明は、例えばＩＣ設計のためのレイアウト画像における電気回路や、シティーマップ上のストリートや建物など、バックグラウンド上のフィールドにレイアウトを有する任意のテキストまたは画像の任意のデジタル表示にも適している。また、例えば電気チェーンで閉じられたサブ回路を検出するといった非常に異なる用途において、この方法が使用されても良い。なお、最短サイクルによって分割を実行するための開始点としてのグラフは、ＭＷＲシステムに基づいて、前述したグラフと異なるように構成されても良いことに留意されたい。例えば、グラフは、前述したＡｎｔｏｎａｃｏｐｏｕｌｏｓによる論文に記載されたタイルを使用して構成されても良いが、Ａｎｔｏｎａｃｏｐｏｕｌｏｓに開示された特定のグラフは、本発明のグラフとは異なっており、使用することができない。また、グラフの辺に割り当てられる加重は、必ずしも距離でなくても良い。加重は、最短サイクルに寄与するように対応して選択されなければならない。例えば、加重は、タイルの表面であっても良い。なお、本明細書において、動詞「備える」、「含む」、「有する」及びその活用の用法は、記載された要素以外の他の要素またはステップの存在を排除しない。また、要素に先立つ単語「１つの」は、そのような要素が複数存在することを妨げず、任意の参照符号は、特許請求の範囲を限定しない。また、本発明、および全てのユニットまたは前述した手段は、適当なハードウェアおよび／またはソフトウェアによって実施することができ、幾つかの「手段」または「ユニット」は、同じ要素によって表わすことができる。また、本発明の範囲は実施形態に限定されず、本発明は、前述した個々の新規な特徴、全ての新規な特徴、または新規な特徴の組み合わせにある。

典型的な分割方法の概略を示している。 サンプルとしての日本の新聞の一部を示している。 １方向に沿うオブジェクトの統合を示している。 オブジェクトの分割および２方向統合を示している。 ホワイトランからの最大長方形の構成を示している。 最大白長方形の構成を示している。 最大白長方形をオーバーラップさせるクリーニングを示している。 新聞の一面上のグラフを示している。 最大長方形の２つのタイプの交差部を示している。 画像を分割するための装置を示している。 最短サイクルのリストの形成に基づいてフィールドを規定するためのフローチャートを示している。 グラフおよびグラフ内のサイクルを示している。 グラフおよびグラフ内のサイクルを示している。 最短サイクル検出を示している。 最短サイクル検出を示している。 グラフ減少方法を示している。

符号の説明

１１ 入力画像
１２ ＣＣオブジェクト
１３ レイアウトオブジェクト
１４ ＣＣＡモジュール
１５ ＬＡモジュール
１６ ＡＦモジュール
１７ 記事
２１ 垂直方向の読み方向
２２ 水平方向の読み方向
２３ 黒ライン
３１ 最初の解析ステップ
３２ 算定閾値
３３ 分類ステップ
３４ 補正された連結成分
３５ 統合ステップ
３６ オブジェクト
３７ テキスト統合ステップ
３８ テキストブロック
４０ 画像のグラフ
４１ 画像のグラフ
４２ フィールド検出ステップ
４３ 連結成分
４４ ステップ
４５ 読む順番
４６ ライン形成ステップ
４７ テキストブロック
５１ ホワイトラン
５２ 最大白長方形
５３ フォアグラウンド領域
６１ ホワイトラン
６２、６３、６４、６５、６６ 最大白長方形
８０ デジタル画像
８１ グラフの頂点
８２ 辺
８８ 長方形領域
８９ 交点
９１ 入力ユニット
９２ 記憶ユニット
９３ ディスプレイユニット
９４ 処理ユニット
９５ ユーザインタフェース
Ｓ１、Ｓ２、Ｓ３、Ｓ４、Ｓ５、Ｓ６、Ｓ７、Ｓ８、Ｓ９ ステップ
１００ 辺
１０１ 頂点
１０２ 最短サイクル
１０３ａ、１０３ｂ、１０４、１０５ テキスト領域
１０４ａ 最短サイクル
ｕ、ｖ 頂点
１０８ 開始辺
１０９ 辺
１１１ 第１のステップ
１１２ 第２のステップ
１１３ 第３のステップ
１１５、１１６、１１７ 最短サイクル
ＭＷＲ１、ＭＷＲ２ 最大白長方形
ＩＷＲ 情報提供白長方形

Claims (15)

1. ピクセルから成る画像を、画像のレイアウト要素に対応する複数のフィールドに分割する方法であって、前記ピクセルが、画素の強度および／または色を示す値を有し、該方法が、
   画像内のバックグラウンド領域に基づいて、頂点と頂点同士を接続する辺とを有するグラフを構成するステップを含み、前記グラフの辺が、画像のフィールドの輪郭を協働して描くフィールドセパレータに対応し、該方法がさらに、
   画像の少なくとも一部を協働して完全に網羅する連続する最短サイクルのリストを構成するステップを含む、最短サイクルが、１つの頂点からグラフの辺を介して同じ頂点に戻る閉じられた経路として規定され、該経路が、前記頂点から前記頂点に戻る考えられる全ての閉じられた経路のうち最も小さい辺の加重総和を有し、該方法がさらに、
   前記リストの最短サイクルを画像のフィールドとして規定するステップを含む方法。
2. 辺の頂点間のユークリッド距離等の該辺の所定の特性に基づいて、前記辺に対して加重を割り当てることをさらに含む、請求項１に記載の方法。
3. 前記最短サイクルのリストを構成するステップが、
   多くても１つの最短サイクルの一部となり得る１つの辺を選択し、
   前記辺の代わりに、前記辺の頂点同士を接続する最短経路を決定し、
   前記辺と前記最短経路とを組み合わせることを含む、請求項１に記載の方法。
4. 多くても１つの最短サイクルの一部となり得る１つの辺が、グラフの外側の境界にある１つの辺である、請求項３に記載の方法。
5. 前記最短サイクルのリストを構成するステップが、反復処理であり、最短サイクルを見つけた後、グラフが、最短サイクルの一部であり且つ更なる最短サイクルの一部と成り得ない任意の辺を除去することにより減少され、その後、次の最短サイクルが決定される、請求項１から４のいずれか一項に記載の方法。
6. 前記最短サイクルのリストを構成するステップが、グラフに残存する辺がなくなった時に終了する、請求項５に記載の方法。
7. 最短サイクルが、根元の頂点から他の頂点へと向う最短経路の全てを示す、最小スパニングツリーを構成することによって決定され、前記最小スパニングツリーが、グラフの頂点に関連付けられた変数で表わされる、請求項１から６のいずれか一項に記載の方法。
8. 前記フィールドを規定するステップが、
   第１の領域を囲む第１の最短サイクルが、第１の領域よりも小さい第２の領域を囲む第２の最短サイクルを完全に含んでいるか否かをチェックし、
   囲まれた前記第１の領域から、囲まれた前記第２の領域を差し引くことを含む、請求項１に記載の方法。
9. 前記フィールドを規定するステップが、
   リスト内の各最短サイクル毎に、囲まれた領域を決定し、
   前記囲まれた領域のサイズに基づいて、最短サイクルのリストを区分けすることを含み、
   区分けされたリストの順番で、最短サイクルに対応するフィールドに関し、任意の更なる画像処理が連続的に行なわれる、請求項１に記載の方法。
10. 最短サイクルの任意の１つに対応するフィールドにおいて読む順番が検出されるとともに、前記読む順番に対応する方向で、フィールド内のフォアグラウンド成分が、テキストラインに結び付けられるさらなる処理ステップを含む、請求項９に記載の方法。
11. ピクセルから成る画像を複数のフィールドに分割するためのコンピュータプログラム製品であって、請求項１から１０のいずれか一項に記載の方法をプロセッサに実行させるように、プログラムが動作するコンピュータプログラム製品。
12. ピクセルから成る画像を、画像のレイアウト要素に対応する複数のフィールドに分割する装置であって、前記ピクセルが、画素の強度および／または色を示す値を有し、該分割する装置が、
    画像を入力するための入力ユニット（９１）と、
    処理ユニット（９４）とを備え、該処理ユニット（９４）が、
    画像内のバックグラウンド領域に基づいて、頂点と頂点同士を接続する辺とを有するグラフを構成するグラフ構成装置を含み、前記グラフの辺が、画像の領域の輪郭を協働して描くフィールドセパレータに対応し、該処理ユニット（９４）がさらに、
    １つの頂点からグラフの辺を介して同じ頂点に戻る閉じられた経路をグラフ内で決定する経路検出モジュールを含み、該経路が、前記頂点から前記頂点に戻る考えられる全ての閉じられた経路のうち辺の加重総和が最も小さく、さらに最短サイクルと呼ばれ、該処理ユニット（９４）がさらに、
    画像の少なくとも一部を協働して完全に網羅する連続する最短サイクルのリストを構成するリストモジュールと、
    前記リストの最短サイクルを画像のフィールドとして規定するフィールド規定装置とを含む分割する装置。
13. 前記処理ユニット（９４）が、
    辺の頂点間のユークリッド距離等の該辺の所定の特性に基づいて、該辺に対して加重を割り当てる加重割り当て装置をさらに備えている、請求項１２に記載の装置。
14. 分割後に、画像のフィールドを表示するディスプレイユニット（９３）を備えている、請求項１２に記載の装置。
15. 前記リストモジュールが、
    リスト上に含まれる最短サイクルの一部であり、且つ更なる最短サイクルの一部と成り得ない任意の辺をグラフから除去することと、
    グラフに残存する辺がなくなった時にリストの構成を終了することとによって、
    最短サイクルを繰り返し見つけるように構成されている、請求項１２または１３に記載の装置。

Images