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