(57)【特許請求の範囲】
【請求項１】
文書イメージの文書オブジェクト間の空間的関係を識別するステップと、
隣接する文書オブジェクトのペアを分離しているスペースを決定するステップと、
前記文書オブジェクトのペアを分離しているスペースで重み付けしたスケーリングファクタが、ピクセル単位で測った視覚的に認識可能な最小のスペース以上となるように、前記スケーリングファクタを決定するステップと、
を有することを特徴とする方法。
【請求項２】
グラフモデルを用いて文書オブジェクト間のスペースを表すステップをさらに有することを特徴とする、請求項１に記載の方法。
【請求項３】
前記文書イメージの前記文書オブジェクト間の空間的関係を識別するステップは、ボロノイ三角形分割図中の辺を共有する２つのオブジェクト間の幾何学的関係を決定するステップを含むことを特徴とする、請求項１に記載の方法。
【請求項４】
ドローネ三角形分割を用いて前記空間的関係を表すステップと、
前記ドローネ三角形分割の三つ組みをグラフモデルに変換するステップと、をさらに含むことを特徴とする、請求項１に記載の方法。
【請求項５】
隣接する文書オブジェクトのペアを分離している前記スペースを決定するステップは、隣接する文書オブジェクトの各ペアの中心点を通る、オブジェクト間の前記分離するスペースと交わる数値化された線分の長さであって測られた分離するスペースを表す長さを決定するステップを含むことを特徴とする、請求項１に記載の方法。
【請求項６】
隣接する文書オブジェクトのペアを分離している前記スペースを決定するステップは、隣接する文書オブジェクトの各ペアの間を通る、オブジェクト間の前記分離するスペースと交わる数値化された線分の長さであって測られた分離するスペースを表す長さを決定するステップを含むことを特徴とする、請求項１に記載の方法。
【請求項７】
前記文書オブジェクト間の前記空間的関係を表す、前記測られた分離スペースに対応する重みを含むグラフモデルを生成するステップと、
前記グラフの頂点をツリーに結合するステップと、
をさらに有することを特徴とする、請求項１に記載の方法。
【請求項８】
文書イメージをスケーリングする画像形成装置であって、
文書イメージの文書オブジェクト間の空間的関係を識別する手段と、
隣接する文書オブジェクトのペアを分離しているスペースを決定する手段と、
前記文書オブジェクトのペアを分離しているスペースで重み付けしたスケーリングファクタが、ピクセル単位で測った視覚的に認識可能な最小のスペース以上となるように、前記スケーリングファクタを決定する手段と、
を有することを特徴とする装置。
【請求項９】
文書イメージをスケーリングするためのコンピュータプログラムであって、コンピュータに
文書イメージの文書オブジェクト間の空間的関係を識別するステップと、
隣接する文書オブジェクトのペアを分離しているスペースを決定するステップと、
前記文書オブジェクトのペアを分離しているスペースで重み付けしたスケーリングファクタが、ピクセル単位で測った視覚的に認識可能な最小のスペース以上となるように、前記スケーリングファクタを決定するステップと、
を実行させることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書画像のスケーリングに関し、特に、文書画像のコンテント適応スケーリングに関する。
【背景技術】
【０００２】
サムネイルは、文書のブラウズと検索における視覚化手段として広く使用されている。サムネイルは一般的に文書イメージをスケーリングして生成される。ここで実行されるスケーリングは、従来からあるダウンサンプリングのような幾何学的なスケーリングだけである。文書イメージをスケーリングする方法は、他にも幾つかある。その１つとして、レイアウトの歪みを許容するようなスケーリングがある。例えば、スマートネイル（SmartNail）は、サイズが固定された表示ウィンドウ中に選択されたテキストを読めるように表示する技術である。スマートネイルを使用すると、テキストを読める替わりにレイアウトが犠牲にされている。２００４年１２月２２日出願の米国特許出願第１１／０２３，１４２号（発明の名称「セマンティックドキュメントスマートネイル」）を参照されたい。その他の方法は、幾何学的スケーリングとレイアウトスケーリングを組み合わせて使用している。例えば、ここで動的文書アイコンと呼ぶ方法は、レイアウトの特徴を取得するものであるが、テキスト領域の可読性は無視している。スマートネイルとは対照的に、動的文書アイコンではアイコンのサイズは固定ではなく、アイコンの形で表される内容に依存する。動的文書アイコンについてのより詳しい情報は、２００４年１２月２１日出願の米国特許出願第１１／０１９，８０２号（発明の名称「動的文書アイコン」）を参照されたい。
【０００３】
文書解析の分野において、文書のレイアウトに関する情報を取得するには、グラフモデルがよく使われている。グラフモデルにはいろいろな形態がある。グラフモデルの一例が、Aiello  M.,  Monz,  C.,  Todoran,  L.,  Worring,  M.による「Document  Understanding  for  a  Broad  Class  of  Documents」（International  Journal  on  Document  Analysis  and  Recognition(IJDAR),  vol.  5(1),  pp.  1-16,  2002）に記載されている。この文献では、テキスト領域の中心を頂点としてモデル化し、頂点を結ぶ辺（edge）は領域間の隣接関係を示す。この情報は後で読み出し順序の抽出やテキスト領域の分類等の論理分析の際に必要となる。
【０００４】
グラフモデルは、一般的に文書解析の分野ではウェブページやテーブル構造等の分析に多く使用されている。グラフの操作にはグラフマッチングがあり、異なるグラフの比較に使用される。この分野の概要は、Lopresti,  D.,  Wilfong,  G.による「A  Fast  Technique  for  Comparing  Graph  Representations  with  Applications  to  Performance  Evaluation」（IJDAR,  vol.  6,  pp.  219-229,  2004）に記載されている。
【０００５】
多くの場合、文書中の空白を用いてアイテム（テキストのコラム等）の間のスペースを識別する。文書イメージ中の空白を計算する方法はいくつかある。１つの方法が、Breuel,  T.による「An  Algorithm  for  Finding  Maximal  Whitespace  Rectangles  at  Arbitrary  Orientations  for  Document  Layout  Analysis」（Proceedings  of  ICDAR,  2003  August  3-6;  Edinburgh,  Scotland,  pp.  66-70.  2003）に記載されている。ＯＣＲシステムは、テキストの構成要素を抽出するために空白を検出する独自の方法を有している。
【０００６】
空白を拡大する方法が、１９９７年１月７日に発行された米国特許第５，５９２，５７４号（発明の名称「Method  and  Apparatus  for  Expansion  of  White  Space  in  Document  Images  on  a  Digital  Scanning  Device」、発明者Chilton,  J.K.,  Cullen,  J.,  Ejiri,  K.）に説明されている。米国特許第５，５９２，５７４号で論じられているように、文書のオブジェクトを見やすくするため、オブジェクト間の空白を大きくする。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
文書イメージをコンテント適応スケーリングする方法と装置、及びコンピュータに当該方法を実行させるコンピュータプログラムを開示する。本発明の一態様による方法は、文書イメージの文書オブジェクト間の空間的関係を識別するステップと、隣接する文書オブジェクトのペアを分離しているスペースを決定するステップと、前記文書イメージ中の前記文書オブジェクトを分離している前記スペースに基づき、かつ表示装置の特性に基づき、スケーリングファクタを決定するステップと、を有することを特徴とする方法である。
【課題を解決するための手段】
【０００８】
文書イメージに対する適当なダウンサンプリングファクタの決定を開示する。一実施形態において、ダウンサンプリングファクタは、スケーリングされて小さくなったイメージでも選択されたレイアウトの特徴が認識できるようにダウンサンプリングファクタを選択する。一実施形態において、スケーリングファクタは空白分析を用いて求める。空白分析の結果求められる適当な最小スケーリングファクタは、文書イメージの内容に応じて決まる。これは、スケーリングされた文書イメージ中のレイアウト情報を伝えるのに適当な大きさは、装置に依存することもあるということを示唆している。一実施形態において、エレメントのアイコン化は実行されない。
【０００９】
以下の開示において、適当な最小スケーリングファクタを決定するために、文書の領域を分離している空白を用いる。この文書の領域には、テキスト領域（例えば、テキストブロック）、タイトル領域、コラム、図、脚注、表題、図・見だしテーブル等が含まれる。空白が視認できる限りスケーリングは可能である。空白が視認できない場合、スケーリングのし過ぎである。テキスト領域を分離している空白はグラフまたはツリーモデルで取得（capture）する。
【００１０】
「空白」という用語の意味は文書により異なるが、白い背景に黒いテキストが記載されている文書について使用する場合に特に好適である。ここでの目的のため、「空白」という用語を一般化して、テキスト領域を除いた背景を含むものとする。背景は、白色、グレー、単一色、または連続的なトーンの画像であってもよい。
【００１１】
ここでの目的のため、ツリーは特定のグラフであり、すなわち、いずれのノードのペアの間にもパスは１つだけである。空白ツリーはルートのある、方向付けされたツリーである。すなわち、エッジが入らないノード（ルートノード）が１つだけある。グラフはデータ構造を表すゆえ、ツリーもデータ構造を表す。相互接続されていることは空白グラフの特徴である。階層的順序により、一般的なグラフがツリーになる。
【００１２】
以下、詳細に説明する。しかし、当業者には明らかなように、本発明はこれらの具体的な詳細なしでも実施することができる。場合によって、周知の構造及びデバイスは、本発明をかえって分かりづらくしないために、その詳細は示さずにブロック図として示した。
【００１３】
以下の詳細な説明の一部は、コンピュータメモリ内のデータビット上のアルゴリズム及び動作のシンボリックな表示により表した。これらのアルゴリズムによる記述と表現は、データ処理の技術分野の当業者が他の当業者に自分の仕事の本質を最も効果的に伝えるために使用する手段である。アルゴリズムは、ここで、及び一般的に、所望の結果に結びつくステップの自己矛盾のないシーケンスであると考えられる。ステップは、物理的数量の物理的操作を必要とする。通常、必要ではないが、これらの物理量は、格納、転送、結合、比較、あるいは操作可能な電気的または磁気的信号の形をとる。これらの信号は、一般的に使用されているという理由に基づき、ビット、数値、要素、シンボル、特徴、条件、数字等と呼ぶ方が便利なこともある。
【００１４】
しかし、留意すべきことは、これらの用語や同様の用語はすべて適当な物理量と関連しており、単に便利なラベルをつけているだけである。以下の説明により明らかでなければ、特に説明しなければ、言うまでもないことであるが、この説明において、「処理」、「計算」、「判断」、「表示」等の用語を用いた説明は、コンピュータシステムや同様の電子的計算デバイスの動作及びプロセスを言う。これらの動作及びプロセスは、コンピュータシステムのレジスター及びメモリ内の（電子的）物理量として表されたデータを操作し、及びコンピュータシステムのメモリもしくはレジスターまたはその他の情報記憶、伝送、表示デバイス内の物理量として同様に表された他のデータや変換する。
【００１５】
本発明は、ここに説明する動作を実行するための装置にも関係する。この装置は必要な目的に併せた特殊構成でもよく、記憶されたコンピュータプログラムにより選択的に起動または再構成された汎用コンピュータであってもよい。このようなコンピュータプログラムは、各々コンピュータシステムバスに結合した、フレキシブルディスク、光ディスク、CD-ROM、光磁気ディスク、読出専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気または光カード、その他の電子的命令を好適に記憶可能なタイプの媒体を含むいかなるタイプのディスクも含むがこれに限定されないコンピュータ読出可能記憶媒体に記憶される。
【００１６】
ここに示したアルゴリズムと表示は、特定のコンピュータその他の装置に本質的に関係しているものではない。いろいろな汎用システムを本発明の教示によるプログラムと使用してもよく、必要な方法ステップを実行する専用装置を構成することも便利である。これらのシステムに必要な構造は以下の説明から明らかであろう。また、本発明の説明においては特定のプログラミング言語を前提として説明していない。言うまでもなく、いろいろなプログラム言語を用いてここに説明する本発明の教示を実施することができる。
【００１７】
機械読出可能媒体には、機械（例えばコンピュータ）により読出可能な形式の情報を記憶または送信するいかなるメカニズムも含まれる。例えば、機械読出可能媒体には、読出専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイス、電気的、光学的、音響的その他の形式の伝搬信号（例えば、搬送波、赤外線信号、デジタル信号等）が含まれる。
【発明を実施するための最良の形態】
【００１８】
概要
文書オブジェクトがダウンサンプリング後に空白で分離して区別できるという制約の下でのダウンサンプリングファクタの決定を説明する。一実施形態において、このような方法には３つの操作を使用する。第一に、隣り合うユニットまたはオブジェクトを判断する。第二に、隣り合うオブジェクト間の空白を計算する。最後に、隣接するオブジェクト間の空白と背景色及び表示特性を測定し、最小スケーリングファクタを求める。
【００１９】
図１は、文書イメージのコンテント適応スケーリングを実行するプロセスの一実施形態を示すフロー図である。上記プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムまたは専用機上で実行される）、またはファームウェアも含めて、これらの組み合わせを有する処理ロジックにより実行される。
【００２０】
図１を参照して、文書イメージの文書オブジェクト間の空間的関係を特定する処理ロジックで始まる（処理ブロック１０１）。一実施形態において、文書オブジェクトはテクストゾーンを含む。一実施形態において、処理ロジックは、ボロノイ図の辺を共有する２つのオブジェクト間の幾何学的関係を決定することにより、文書イメージの文書オブジェクト間の空間的関係を識別する。
【００２１】
空間的関係を識別した後、隣接する文書オブジェクトのペアを分離する隙間を判断する（処理ブロック１０２）。幾何学的スペースは、文書イメージ中のテキスト行の回りにある空白または背景色の領域を含んでもよい。一実施形態において、空白はテキスト行の回りの帯の平均色として計算される。一実施形態において、処理ロジックは、隣接する文書オブジェクトのペアの中心点を通る直線の交差する長さを決定することにより、隣接する文書オブジェクトのペアを分離しているスペースを決定する。このような場合、空白を分離しているオブジェクトがある場合、交わりの長さはその測定された分離スペースを表す。文書オブジェクト間の空間的関係を表す、測定された分離スペースに対応する重みをグラフモデルに加えてもよい。重みは規格化してもよい。例えば、他の実施形態において、隣接する文書オブジェクトの各ペアの中心点間の方向付けされた隣接する文書オブジェクトのペア間の数値化された線分の長さを決定することにより、隣接する文書オブジェクトのペアを分離しているスペースを決定する。この場合、長さは測定された分離スペースを表す。中心点は、幾何学的中心または重心である。
【００２２】
グラフモデルを用いて文書イメージ中の隣接する文書オブジェクトのペアを分離するスペースを表す（処理ブロック１０３）。一実施形態において、グラフモデルにおいてグラフ関係は、文書オブジェクト間の分離されるスペースを表す重みを含む、頂点をつなぐリストペアとして、表される。グラフモデルは、コンピュータシステムでは結合行列（association  matrix）として表される。
【００２３】
一実施形態において、空間的関係をドローネ三角形分割を用いて表し、ドローネ三角形分割の三つ組み（triplet）をグラフモデルに変換する。一実施形態において、グラフモデルは複数の頂点を含み、各頂点は１つの文書オブジェクトの中心点である。
【００２４】
一実施形態において、処理ロジックは、グラフを文書オブジェクトの画像データを含むファイル（例えば、ＪＰＭファイル）にメタデータとして格納する。
【００２５】
隣接する文書オブジェクトのペアを分離するスペースを識別すると、文書イメージ中の文書オブジェクトを分離するスペースに基づき、かつディスプレイ装置の特性に基づき、少なくとも１つのスケーリングファクタを決定する（処理ブロック１０４）。一実施形態において、最小のスペースがそのディスプレイ装置の特性を有するディスプレイ装置に表示してもまだ見えるように、文書イメージのスケーリングをするスケーリングファクタを決定することにより、少なくとも１つのスケーリングファクタを決定する。
【００２６】
一実施形態において、処理ロジックは、ピクセル単位で測定した最小の視覚的に認識可能なスペース分離を反映する定数を用いてスケーリングファクタを決定することにより、文書イメージ中の一組の文書オブジェクトを分離するスペースに基づき、かつディスプレイ装置の特性に基づき、スケーリングファクタを決定する。一実施形態において、その定数は文書クラスに対して設定される。一実施形態において、その定数は装置クラスに対して設定される。一実施形態において、その定数は、文書イメージとディスプレイ装置の特性から計算される。その定数は、そのディスプレイ装置の特性を有するディスプレイ装置に依存してもよい。
【００２７】
１つ以上のスケーリングファクタを決定すると、そのスケーリングファクタを記憶する（処理ブロック１０５）。この記憶は任意的である。スケーリングファクタは、文書イメージファイルのメタデータとして記憶してもよい。例えば、スケーリングファクタを、それと関連するディスプレイ装置の特性とともに、ＪＰＭファイルフォーマットのメタデータに記憶してもよい。
一実施形態において、スケーリングファクタを用いて文書をスケーリングする（処理ブロック１０６）。このブロックも任意的である。
【００２８】
ボロノイ図とドローネ三角形分割による文書オブジェクト間の隣接関係の確立
一実施形態において、ボロノイ図において辺を共有する場合、２つのオブジェクトＯ１とＯ２間の幾何学的隣接関係を確立する。文書オブジェクトＯｉの幾何学的中心点ｚｉに対するボロノイ図を次式により計算する：
zi=1/2[Oiの左上隅+(Oiの幅,Oiの高さ)]。
【００２９】
ボロノイ図と双対関係にあるドローネ三角形分割を隣接関係の表現として使用する。ボロノイ図は、再近接ルール（nearest  neighbor  rule）に従って領域に分割した平面を表す。再近接ルールは、各点がその点に最も近い平面領域に関係づけられることを述べている。領域への分割の結果は、線分と頂点により表される。ドローネ三角形分割は、平面内の２つの点が、そのボロノイ領域が共通の辺を有する場合にのみ、その点を接続する辺を含む。ボロノイ図とドローネ三角形分割は、ボロノイ点がドローネ三角形に対応し、ボロノイ領域が点に対応し、両タイプの辺が対応するという意味で、双対的である。より詳しい情報は、Franz  Aurenhammer著「Voronoi  Diagrams-A  Survey  of  a  Fundamental  Geometric  Data  Structure」ACM  Computing  Surveys,  Vol.  23,  No.  3,  September  1991を参照。
【００３０】
ドローネ三角形分割は中心点三つ組みのシーケンスにより与えられる。各三つ組み（triplet）は、３つの中心点間の隣接関係を反映している。図２は、文書オブジェクトの一例とそのボロノイ図を示す図である。図２を参照して、文書オブジェクト２０１−２１４を示す。これらの文書オブジェクトは、文書中のテキスト領域（例えば、タイトル、テキストのパラグラフ等）である。図中の線（例えば２２０）は、２つの文書オブジェクト（線分２２０の場合、文書オブジェクト２１３と２１４）の中心点間の線分（図示せず）に垂直である。ボロノイ図とドローネ三角形分割は、計算幾何学の分野で周知である。
【００３１】
図２の文書例について、ドローネ（Delaunay）三角形分割の三つ組み（triplet）を表１に示した。一実施形態において、これらの隣接関係を、オブジェクトの各中心点がグラフの頂点であり、２つの頂点間の辺がその頂点間に隣接関係があることを表すグラフモデルに変換する。
【００３２】
【表１】
0004781924.tif 000002
隣接領域間を分離する空白の計算
一実施形態において、中心点ｚｉとｚｊを直線で結び、２つの隣接するオブジェクトＯｉとＯｊ間の空白と交わる線分の長さを測ることにより、ＯｉとＯｊ間の空白を計算する。直線を実際に描かずに、オブジェクトＯｉとＯｊ間を分離する空白Ｗｉｊを以下のように計算する。
【００３３】
中心点を通る直線を次の式で数値化する：
【００３４】
【数１】
0004781924.tif 000003
数値化を説明する例を示す。文書オブジェクトＯｉの４つの角をＡ、Ｂ、Ｃ、Ｄで表す。文書オブジェクトＯｉの境界ボックス（bounding  box）は、線分ＡＢ、ＢＣ、ＣＤ、ＤＡで与えられる。繰り返すため、境界ボックス情報は論理分析により得られる。文書オブジェクトＯｊの４つの角をＥ、Ｆ、Ｇ、Ｈで表す。中心点ｚｉとｚｊを通る直線と、ＯｉとＯｊの各境界ボックスラインとの交わりを次のように求める。
【００３５】
中心を結ぶ線の境界ボックス線分ＡＢとの交わりの場合、
【００３６】
【数２】
0004781924.tif 000004
一実施形態において、いろいろな符号の組み合わせについて、値λとμの組を求め方は次の通りである：
１.    0<λi[1]≦1,0<μi[1]≦1の場合：OjはOiより大きい（例を図３に示した）、
２.    λi[1]<0,0<μi[1]≦1の場合：OjはOiより小さい、
３.    1<μi[1]<∞の場合：OjはOiの右側にあるが、直線ｇは境界ボックス線分と平行ではない、
４.    -∞<μi[1]<0の場合：OjはOiの左側にあるが、直線ｇは境界ボックス線分と平行ではない、
５.    どの解も中心を結ぶ線が境界ボックス線分と平行であることを示していない。
【００３７】
中心を結ぶ直線のＯｉの残りの境界ボックス線分との交わりについて同じことを実行し（その結果パラメータλi[2]、λi[3]、λi[4]が得られる）、また、オブジェクトＯｊの境界ボックス要素との交わりについて同じことを実行する（その結果各境界ボックスセグメントｋについてパラメータλj[k]が得られる）。これらの例を図４に示した。各オブジェクトのペアについて、分離する空白の線分を表す値の唯一の組み合わせ（λi[m],λj[k])が存在する。すなわち、λi[m]<∞、λj[k*[m]]<∞となり、
【００３８】
【数３】
0004781924.tif 000005
を満たす組み合わせ（λi[m],λj[k*[m]）である。
一実施形態において、分離する空白は次式により図られる：
【００３９】
【数４】
0004781924.tif 000006
分離する空白を図る別の方法は、図５に示した点線により表される距離を計算することである。図５を参照して、実線の矢印５０１で示された距離を計算するのではなく、点線５０２で示された距離を計算する。この計算は、周知慣用技術の一部である。
【００４０】
空白グラフモデル
一実施形態において、オブジェクトＯｉとＯｊの間を分離する空白Ｗｉｊを測り、それをグラフモデルの重みとして付加する。これにより、隣接関係グラフがそれぞれ重みづけグラフとなる。より具体的に、一実施形態において、２つの頂点ｖｉとｖｊの間の辺ｅｉｊが与えられると、その辺と関連づけられる重みｐｉｊは次の式で与えられる：
【００４１】
【数５】
0004781924.tif 000007
式（５）を使用することの意味は、分離のしかたが大きい空白があるオブジェクト間の辺の重みは小さく、一方、分離のしかたが小さい空白があるオブジェクト間の辺の重みは大きいということである。隣接していない領域に関する情報が記憶されていない場合、規格化は必要ない。オブジェクトＯｉとＯｊが隣接領域でない場合、重みｐｉｊ＝０である。
【００４２】
辺により結ばれたすべてのペア（ｉ，ｊ）の組は、ここで隣接関係インデックスセットと呼ぶ。最終的な重みづけされたグラフは、ここで空白グラフ（White  Space  Graph(WSG)）と呼ぶ。図２の文書例に関連するグラフ例を、図６に示した隣接行列（adjacency  matrix）により与える。
【００４３】
図６を参照して、行と列は頂点を表し、要素（ｉ，ｊ）が０のとき、それに関連する頂点ｖｉとｖｊの間に辺がなく、０でないとき、辺がありその重みがｐｉｊであることを表す。別の実施形態において、グラフ関係は、重みを含めて、接続された頂点のペアのリスト（ここではリストビューと呼ぶ）を用いて表される。
【００４４】
以下は、文書イメージからＷＳＧを生成するための疑似コードである：
各領域のアンカーポイント（幾何学的中心または重心）を決める；
アンカー点からのボロノイ分割（voronoi  tesselation）を計算する；
ボロノイ図中の辺を共有する各領域について、アンカー点を各領域に関連するデータ点として、領域間分離する空白を計算する；
各アンカー点を頂点として有するグラフを生成する；
ボロノイ図で辺を共有する頂点を辺で接続する；
分離する空白線分の長さを重みとして対応する辺に加える。
【００４５】
最小空白へのスケーリング
一実施形態において、空白グラフが与えられた場合、スケーリングファクタｓ*を次式の解として計算する：
【００４６】
【数６】
0004781924.tif 000008
ここで、ｉ、ｊは隣接関係インデックスセット中のすべてのｉ、ｊであり、
【００４７】
【数７】
0004781924.tif 000009
一実施形態において、定数εは、ピクセル単位で測った視覚的に認識可能な最小の空白分離を反映している。この定数は表示装置に依存していてもよい。例えば、ディスプレイのコントラストが高いと、低い場合と比較してεは小さくできる。
【００４８】
一実施例において、閾値εは文書のクラスに応じてマニュアルで設定する。一例として、白い背景にほぼ黒いテキストが含まれた文書が、アップルのシネマディスプレイ上に表示されている場合、定数εは２ピクセルに設定される。
【００４９】
他の一実施形態において、その定数εは、文書イメージとディスプレイ装置の特性から自動的に設定される。この場合、最初に、色的外観を例えばＣＩＥＣＡＭ０２またはｉＣＡＭを用いてモデル化する。ＣＩＥＣＡＭ０２及びｉＣＡＭは当技術分野において周知である。次に、コントラスト感度関数（例えば、Ｓ−ＣＩＥＬＡＢにおけるもの）を低解像度イメージのモデルコントラストに適用することができる。一実施形態において、隣接する領域間を分離する空白を計算する場合、中心を結ぶ線の空白部分に沿って、ΔＥユニットを計算することにより、コントラストを求める。
【００５０】
階層的文書構造の空白ツリーへの組み込み
文書レイアウトは文書オブジェクトの集まりだけでは決まらず、階層構造を含み、オブジェクトがグループ化してカラムや題名部分当の大きな単位を形成する場合がある。一実施形態において、論理的及び幾何学的情報の組み合わせに基づいてこのような階層構造を組み込む。この階層構造を、以下レイアウト情報と呼ぶ。空白情報を用いて、純粋に幾何学的情報に基づいて別の階層構造を組み込むこともできる。空白グラフに階層構造を付加すると、空白ツリー（ＷＳＴ）ができる。
【００５１】
一実施形態において、ボトムアップ的に、ＷＳＴのリーフノードとして、ＷＳＧのすべての頂点ｖｉから始めてツリーを形成する。マージプロセスにおいて、リーフノードをマージする。一実施形態において、辺の重みが最大のノードを繰り返しマージすることにより、リーフノードをマージして新しい親ノードを生成する。子と新しい親ノードの間の辺の重みは、子ノード間の辺の重みである。これは、以下のコードにより実行することができる。
【００５２】
【数８】
0004781924.tif 000010
空白グラフの頂点をツリーにマージした結果を、表２にリストビュー形式で与える。グラフィックスツリー表示を図７に示す。
【００５３】
ツリーノードに対応する重みは、親ノードのすべての子孫のグループの分離する空白に関する情報を、その子孫のグループの外のノードに提供する。
【００５４】
図８は、階層的文書構造を空白ツリーに組み込むプロセスの一実施形態を示すフロー図である。上記プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムまたは専用機上で実行される）、またはファームウェアも含めて、これらの組み合わせを有する処理ロジックにより実行される。
【００５５】
図８を参照して、本プロセスは、処理ロジックがレイアウトオブジェクトを受け取るところから始まる（処理ブロック８０１）。レイアウトオブジェクトを用いて、空白ツリーを生成する（処理ブロック８０２）。空白ツリー及びアプリケーションまたはユーザに依存したレイアウトツリーのノード選択に応じて、選択された論理ツリーノードのすべての子孫を子孫として含む空白ツリー中のノードを選択する（処理ブロック８０３）。その後、論理ツリーノードに含まれるオブジェクトについて、適当なダウンサンプリングファクタを決める（処理ブロック８０４）。
【００５６】
【表２】
0004781924.tif 000011
スケーリングしても選択されたレイアウト単位（例えば、文書のカラム）間の分離が確実に見えるようにすることが重要である。レイアウト単位（文書領域）の個々の要素は、ＷＳＴのリーフノードである。レイアウト構造の階層的性質をレイアウトツリーで捉えることができる。レイアウトツリーにおいては、各リーフノードは文書領域を表し、親ノードは領域（タイトル、要約、カラム、表題付き画像等）のグループ化を表す。レイアウトツリーの例を図９に示した。
【００５７】
ＪＰＭ中のメタデータとしての空白グラフとツリー
ＷＳＧとＷＳＴの表示を、文書オブジェクトを含むファイルにメタデータとして格納することができる。一実施形態において、そのファイルはＪＰＭレイアウトオブジェクトとしてＷＳＧの頂点により表された文書オブジェクトを含むＪＰＭファイルである。具体的なアプリケーション（例えば、サムネイルの生成）について、サムネイルの大きさをそのメタデータから自動的に計算することができる。一実施形態において、１つのグラフはディスプレイ装置には依存せず、いろいろなディスプレイ装置の場合のグラフが格納される。このように、一実施形態において、復号タスクの際にスケーリングを制御するために、ＷＳＧ及びＷＳＴのいずれか一方、または両方をメタデータとしてＪＰＭに格納する。
【００５８】
図１５は、ＸＭＬボックス中のメタデータとしてＷＳＴを含むＪＰＭ圧縮された文書イメージを生成するシステムを示す図である。これにより、圧縮された画像データに添付されたメタデータとしてＷＳＴ表示にアクセスして、効率的に復号することができる。図１５を参照して、ＪＰＭコンプレッサ１５０１が文書イメージ１５００を受け取り、ＪＰＭ圧縮を実行する。ＷＳＴ生成部１５０２が、ＪＰＭ圧縮器１５０１のＪＰＭファイル出力を受け取り、ＪＰＭファイル中の画像オブジェクトのＷＳＴを計算する。ファイル添付部１５０３が画像ファイルのＸＭＬボックスにメタデータとしてＷＳＴを添付し、ＷＳＴ情報を有するＪＰＭ圧縮された文書イメージ（１５０４）を作成する。
【００５９】
図１６は、検索クエリーに応答してサムネイルイメージを生成するデータを抽出及びデコードするプロセスの一実施形態を示すフロー図である。上記プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムまたは専用機上で実行される）、またはファームウェアも含めて、これらの組み合わせを有する処理ロジックにより実行される。
【００６０】
図１６を参照して、ＷＳＴ情報を有するＪＰＭ圧縮された文書イメージ（１５０４）をデータベース１６０２に格納する。データベース１６０２が検索クエリー１６０１を受け取る。それに応答して、クエリーの発信者の目標装置に対して適当なサムネイルの大きさを計算する（処理ブロック１６０３）。次に、サムネイル画像を復号するために、適当な画像データを抽出し（処理ブロック１６０４）、それによりサムネイル画像（１６０５）を求める。
【００６１】
別の一実施形態は、上述の圧縮器を含まず、文書イメージのいかなるオブジェクトベース表示（ＰＤＦ等）を用いてもよい。このような場合、ＷＳＴをファイルに追加してもよい。
【００６２】
検索方法におけるＷＳＧとＷＳＴの使用
ＷＳＧとＷＳＴは、選択された文書レイアウト情報を捉える。一般的に、文書レイアウト情報は、先行技術において、検索タスク（レイアウトの特徴に基づく文書のクラスタリング等）または文書マッチングを実行するために使用される。これらの方法をＷＳＧとＷＳＴに適用して、検索アプリケーションにおいてＷＳＧとＷＳＴを使用できるようにしてもよい。
【００６３】
図１０は、情報検索のプロセスの一実施形態を示すフロー図である。上記プロセスは、ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（汎用コンピュータシステムまたは専用機上で実行される）、またはファームウェアも含めて、これらの組み合わせを有する処理ロジックにより実行される。
【００６４】
図１０を参照して、本プロセスは、文書オブジェクトを有する文書にマッチする１つ以上の文書を特定する要求を受け取るところから始まる（処理ブロック１００１）。次に、処理ロジックは、文書オブジェクト間の空間的関係を表すグラフモデルを生成する（処理ブロック１００２）。一実施形態において、測った分離スペースに対応する重みを含める。グラフモデルを一旦生成すると、処理ロジックは、そのグラフモデルを文書記憶装置中の文書のグラフモデルと比較し（処理ブロック１００３）、類似閾値に基づいてマッチする１つ以上の文書の表示（indication）を返す）（処理ブロック１００４）。一実施形態においては、マッチする１つ以上の文書を返す。
【００６５】
同様に、文書をクラスター化するために空白グラフと空白ツリーを使用してもよい。例えば、文書イメージを文書アーカイブに入力すると、それの対応する空白ツリーまたはグラフがその文書アーカイブにすでに格納されている他の文書の空白ツリーまたはグラフと比較され、その新しい文書イメージが属する文書イメージグループが分類される。
【００６６】
文書検索クエリーの結果に基づき、文書が返される。これらの文書のサムネイルが欲しい場合、空白グラフによりそのサムネイルの大きさをどうするかという問いに対して答えを求める。一組の文書が与えられた場合、各文書についてＷＳＧを計算し、各文書Ｄｉについて最小スケーリングファクタs*(Di)を決定する。各文書をその最小スケーリングファクタs*(Di)（図１１−１４参照）でスケーリングするか、または、表示されるサムネイルの均一性を確保するために、各文書をすべての最小スケーリングファクタのうち最大のもの、すなわち、s*=maxi(s*(Di))でスケーリングする。
【００６７】
これは、図１１−１４に例示した。図１１は、各文書Ｄｉがそれぞれの最小スケーリングファクタs*(Di)でスケーリングされている一群の文書の一組のサムネイルを示す図である。図１２は、各文書Ｄｉが１つの最小スケーリングファクタs*(Di)でスケーリングされている一群の文書の一組のサムネイルを示す図である。図１３は、各文書Ｄｉが個々の最小スケーリングファクタs*(Di)でスケーリングされている、サーチ及び検索タスクの結果を示すテキストを含む一群の文書のサムネイルを示す図である。図１４は、各文書Ｄｉが１つの最小スケーリングファクタs*(Di)でスケーリングされている、サーチ及び検索タスクの結果を示すテキストを含む一群の文書のサムネイルを示す図である。
【００６８】
論理ツリーの一組のノードを与えられた場合の、ＷＳＴの適当なノードの発見
図１７は、文書レイアウト構造の一例を示す図である。図１７を参照して、文書には（１）−（６）の数字がふられた６つの文書オブジェクトがある。図１８は、図１７の文書のレイアウトツリーの一例であり、図１９は、図１７の文書のＷＳＴである。
【００６９】
選択されたレイアウトユニットがサムネイル中で明瞭に視覚的に分離可能でなければならないと要求された場合、選択されたレイアウトユニットに対応するノードを特定しなければならない。選択されたレイアウトユニットがこの例のカラム１またはカラム２である場合、ノードn1=８及びn2=９を特定しなければならない。次に、特定された各レイアウトユニットノードｎｉについて、ｎｉがルートであるサブツリー（TL(ni)で示す）の一組のリーフノードを特定する。図１７−１９の例において、ルートがn1=８であるサブツリーの一組のリーフノードはL(TL(n1))={3,4}であり、ルートがn2=９であるサブツリーの一組のリーフノードはL(TL(n2))={5,6}である。カラム１と２がサムネイル中の区別できるレイアウトユニットとして見えることを確保するために、L(TL(n1))中のリーフノードにより表された一組の領域間の空白と、L(TL(n1))中のリーフノードにより表された一組の領域がスケーリング後も見えることを確保する。適当なスケーリングファクタを見つけるために、ＷＳＴ（Ｔｗ）をボトムアップで探す。
【００７０】
一実施形態において、ＷＳＴのリーフノードから初めて、ＷＳＴのノードｍ＊は次の条件を満たさなければならない：
（１）ｍ＊の子ｍｊ中にルートを有するすべてのサブツリー（Tw(mj)で表す）について、リーフノードセットL(TL(ni))がツリーTw(mj)のリーフノードセットに含まれる。
【００７１】
【数９】
0004781924.tif 000012
（２）すべての可能な選択肢に対して重みが最も小さいノードｍ＊がある。
【００７２】
【数１０】
0004781924.tif 000013
図１７−１９に示した例において、式（２）の解はｍ＊＝１１である。
ｍ＊を特定すると、カラムレイアウトユニットを適当にスケーリングするため、ｍ＊の重みp(m*)より大きいスケーリングファクタを選択する必要がある。すなわち、ＴＬ中のノードｎｉにより表されるユニットの適当なスケーリングファクタｓ＊は、(s*)-1>p(m*)となるｓ＊である。ここでｍ＊は式（２）で定義される。
【００７３】
図６の例において、m*=11及び(s*)-1>p(m*)=p(11)=0.1である。
【００７４】
このように、レイアウトユニットであるカラム１（ノード８）とカラム２（ノード９）が与えられた場合、そのノードのサブツリーのリーフノードが黒の実線でグループ化される。ＷＳＴにおいて、式２で決まるノードｍ＊はノード１１である（黒丸で示す）。ｍ＊の子のリーフノードは、点線のようにグループ化される。図１８のレイアウトツリーのリーフノードセットは、図１９のＷＳＴの区別可能なリーフノードセットに含まれている。
【００７５】
論理ツリー中のノードが与えられた場合にＷＳＴ中の適当なノードを見つける疑似コードの例は以下の通りである：
【００７６】
【数１１】
0004781924.tif 000014
動的文書アイコンとの組み合わせ
一実施形態において、ここに説明した方法は２００４年１２月２１に出願された米国特許出願第１１／０１９，８０２号（発明の名称「動的文書アイコン」、出願人K.  Berkner）に記載された動的文書アイコンと組み合わせて用いることができる。この米国特許出願第１１／０１９，８０２号はここに参照により援用する。検索クエリーに対する応答として文書D1,...DMが与えられたとして、すべての文書に共通のレイアウト的特徴（例えば、すべての文書が２つのカラムを有する）を判断するアルゴリズムを使用する。その文書の文書サムネイルを区別するために、レイアウトの階層がカラムオブジェクトよりも低いイメージオブジェクトが区別可能でなければならない。最初に、上述のように、この区別を可能とするために、ノードｍ＊と、２つのカラムのレイアウトユニットを分離する空白の限界スケーリングファクタとしての重みp(m*)が各文書について決定される。その結果、一組のノードm*(Di)が得られる。次に、各文書について、ＷＳＴ中のm*(Di)の子ノードmj(Di)により表されるユニットが確実に視覚的に分離可能であるように、すなわちs(Di)が次の条件を満たすように、スケーリングファクタs(Di)を決定する：
【００７７】
【数１２】
0004781924.tif 000015
一実施形態において、maxj(p(mj(Di))>minj(p(mj(Di))であれば、s(Di)を
【００７８】
【数１３】
0004781924.tif 000016
と設定できる。別の実施形態において、
【００７９】
【数１４】
0004781924.tif 000017
と設定してもよい。
【００８０】
１つのシナリオとして、返されたドキュメントコレクションに共通のレイアウト的特徴を表示ウィンドウに動的文書アイコンにより可視化してもよい。アイコンに加えて、ファクタs(Di)によりスケーリングされた個々のサムネイルを表示する。このシナリオの例を図２０−２６に示した。
【００８１】
図２０は、テキスト検索の一部として返された、領域が視覚的に分離された３つの文書D1-3のアイコン化されたサムネイルを有する２つのコラムを有するアイコンを示す図である。図２１は、文書Ｄ１の、ノードｎ１とｎ２を有するレイアウトツリーを示す図である。図２２は、上記のｍ＊に関する式で計算したノードｍ＊を有する文書Ｄ１のＷＳＴである。図２３は、文書Ｄ２の、ノードｎ１とｎ２を有するレイアウトツリーを示す図である。図２４は、上記のｍ＊に関する式で計算したノードｍ＊を有する文書Ｄ２のＷＳＴである。
【００８２】
図２５は、文書Ｄ３の、ノードｎ１とｎ２を有するレイアウトツリーを示す図である。図２６は、上記のｍ＊に関する式で計算したノードｍ＊を有する文書Ｄ３のＷＳＴである。
【００８３】
一組の共通のレイアウトユニット（例えば、レイアウトツリー中の２つのカラムレイアウト（ノードｎ１とｎ２））から初めて、スケーリングファクタがその２つのカラム間の分離空白を無くすのに十分である場合、領域間の分割が次のレベルであるファクタs(Di)>s*でスケーリングしたサムネイルを計算する。 
【００８４】
コンピュータシステムの実施例
図２７は、ここに説明した１以上の動作を実行するコンピュータシステムの実施例を示すブロック図である。図１１を参照して、コンピュータシステム２７００はクライアントまたはサーバコンピュータシステムを有する。コンピュータシステム２７００は、情報通信用の通信メカニズムすなわちバス２７１１と、バス２７１２と結合した情報処理用のプロセッサ２７１１とを有する。プロセッサ２７１２は、ペンティアム（登録商標）プロセッサ等のマイクロプロセッサを含むが、これに限定されない。
【００８５】
システム２７００は、バス２７０４に結合した、情報及びプロセッサ２７１１により実行される命令を格納するための、ランダムアクセスメモリ（ＲＡＭ）、またはその他の動的記憶装置２７１２（メインメモリと呼ぶ）をさらに有する。メインメモリ２７０４は、プロセッサ２７１２による命令の実行中に一時的変数またはその他の中間的情報を格納するためにも使用される。
【００８６】
コンピュータシステム２７００は、バス２７０６に結合した、静的情報及びプロセッサ２７１１の命令を格納するためのリードオンリメモリ（ＲＯＭ）及び／またはその他の静的記憶装置２７１２をさらに有し、また、磁気ディスクまたは光ディスク及びそれに対応するディスクドライブ等のデータ記憶装置２７０７をさらに有する。データ記憶装置２７０７は、データ記憶装置２７１１は、情報と命令を格納するためにバス８１１に結合されている。
【００８７】
コンピュータシステム２７００は、バス２７１１に結合された、情報をコンピュータユーザに表示するためのブラウン管（ＣＲＴ）または液晶ディスプレイ（ＬＣＤ）等の表示装置２７２１にさらに結合されている。英数字その他のキーを含む英数字入力装置２７２２もバス２７１１に結合され、プロセッサ２７１２にコマンド選択と情報を通信する。付加的ユーザ入力装置は、バス２７１１に結合された、例えば、マウス、トラックボール、トラックパッド、スタイラス、カーソル方向キー等のカーソル制御２７２３であり、プロセッサ２７１２に方向情報とコマンド選択を送信し、ディスプレイ２７２１上のカーソルの動きを制御する。
【００８８】
バス２７１１に結合している装置として、ハードコピー装置２７２４があり、紙、フィルム、その他同様タイプの媒体に、命令、データ、その他の情報を印刷するために使用される。さらに、コンピュータシステム２７００とのオーディオによるインターフェイスのために、スピーカ及び／またはマイクロホン等のサウンド記録再生装置が任意的にバス２７１１に結合される。バス２７１１に結合している他の装置として、電話またはハンドヘルドパームデバイスと通信するための有線／無線通信機能２７２５がある。
【００８９】
システム２７００のすべてのまたはいずれのコンポーネント及び関連するハードウェアを本発明で使用してもよい。しかし、言うまでもなく、この他の構成のコンピュータシステムには、上記装置の一部または全部が含まれてもよい。
【００９０】
動的文書アイコンの作成例
以下の擬似コードは、階層的な幾何・論理クラスタ化の一実施例の詳細を含んでいる。
【００９１】
【数１５】
0004781924.tif 000018
（アイコン木-クラスタ表現としてのアイコン）
クラスタ化によって、概要レベルの文書情報を表す卓越した視覚化可能な特徴によってラベリングできるグループに文書収集物を分割した後、その特徴を次に、1つ又は複数の条件を満たす視覚化に変えなければならない。一実施例では、視覚化は：視覚化に含める対象の情報、場合によっては最適な情報を、利用可能なものとして存在する特定の画面領域上でユーザが知覚可能なクラスタ・ラベル特徴から選択するという条件を満たす。この条件によって、クラスタ・ラベル特徴を視覚化しようとする画像を作成しないようになるが、エッジでのコントラストが小さすぎること、テキストが小さすぎること、色調が区別できないこと、などによって、特定の表示環境における情報を伝え損なってしまう。
【００９２】
クラスタは通常、クラスタ表現によってラベリングされる。クラスタに含まれる特徴ベクトルの特性を視覚化するためには、クラスタに含まれるレイアウト情報のアイコン表現がクラスタ表現として選ばれる。一実施例では、アイコンは以下のように解される。
【００９３】
アイコン要素は、個々のレイアウト特徴に対して作成される。文書ゾーンは、矩形によって表される。テクスチャは、テキスト・ゾーン又はラベルの特定の塗りつぶしによって表される。例えば、テキストは、灰色調（例えば、標準テキストの場合には淡灰色、太字テキストの場合には濃灰色）による塗りつぶしによって視覚化される。画像は画像アイコンによって視覚化され、グラフィックスはグラフィック・アイコンによって視覚化される。例を図２８（Ａ）乃至図２８（Ｈ）に示す。図２８（Ａ）乃至図２８（Ｈ）を参照すれば、例は左から右へ順番に、標準及び太字のテキスト、グラフィック、写真、色、テキスト・ラベル、グラフィック・ラベル、写真ラベル、並びに色ラベルを含む。
【００９４】
一実施例では、「空白要素」を含む各要素は、所定の固定最小サイズを有し、その最小サイズを下回るスケーリングは可能でない。最小サイズは、例えば、コントラスト比などの1つ又は複数の表示特性によって変わってくる。コントラスト比がより高い表示によって、コントラスト比がより低い表示よりも小さな最小サイズが可能である。
【００９５】
クラスタ手順における各分割によって、親クラスタに対して既に作成されたアイコンにアイコン要素のうちの１つが加わる。アイコン要素間で区別できるようにするために、親アイコンの要素全てを、スケーリングして、新たに加えられる要素をその最小サイズ未満までスケーリングしなくてよいようにしなければならない場合がある。そのようにして、完全なアイコンのサイズはクラスタ化手順によって変わってくる。2列のテキスト・レイアウト及び3列のテキスト・レイアウトについての異なるサイズのアイコンの例を以下に説明する。
【００９６】
空白要素w及びテキスト・ゾーン要素tの最小寸法をsmin〔w〕=4画素、smin〔t〕=8画素とする。アイコンにおいて2つの列を図示することは、最小寸法8の2つの矩形が、最小寸法4の空白のそばに配置され、その空白によって隔てられ、取り囲まれなければならないということを意味する。それによって、最小幅は28画素となる。元の文書のアスペクト比を確保するために、アイコンの高さは、28(heightorig/widthorig）として判定される。81/2×11インチのレターサイズの文書の場合、アイコン・サイズは28×36.4画素になる。３つの列を図示する場合、同様な計算によって、アイコン・サイズは40×52画素になる。クラスタ木における各ノードはアイコンによって表されるので、クラスタ木はアイコン木に変換される。このアイコン木のノードの視覚化は、動的な文書アイコンと呼ばれる。図２９（Ａ）及び図２９（Ｂ）は、2列のレイアウト及び3列のレイアウトを図示するアイコン作成の例を図示する。図２９（Ａ）及び図２９（Ｂ）を参照すれば、完全な2列のアイコンはサイズが28×36画素である一方、3列のアイコンは、個々の要素の最小サイズを保証するために、サイズが40×52画素である。
【００９７】
図３０（Ａ）におけるクラスタ木は、メディアチーム(MediaTeam)データベース（アーティクル(Article)・フォルダ）(メディアチーム・オウル(Oulu)文書データベースwww.mediateam.oulu.fi/MTDB/)の20個の文書の部分集合に階層的な幾何・論理クラスタ化を施すことによって生じる。このアーティクルは、テキスト、グラフィックス又は画像を含む種々の列形式でレイアウトされる。データベースには、文書毎のレイアウト解析情報が備えられる。この情報は、文書ゾーン、コンテンツの種類（テキスト、グラフィック、画像）、読み取り順序、列レイアウトなどの特徴を含む。
【００９８】
例では、最大２つの階層レベルのみ、すなわち、1レベルの幾何学的な特徴と２レベルの論理的な特徴、が特徴空間において考察されている。幾何学的な特徴G0は列数であり、論理的な特徴L0は、テキスト、グラフィックス及び画像に関する文書コンテンツの分布である。論理的な特徴の階層の第２レベルである特徴L00は、テキストの部分分類として題名を表す。当該集合例の特徴空間は、以下の表３に示す。
【００９９】
【表３】
0004781924.tif 000019
最後のクラスタ階層は深度が最大4レベルまであり、2列・テキストのみ・題名付きの文書、2列・テキストのみ・題名なしの文書、2列・混合コンテンツの文書、３列・テキストのみの文書、3列・混合コンテンツ及び2列でも3列でもない文書を含む部分収集物に文書収集物を分割する。
【０１００】
（表示サイズ制約に合わせるための、アイコン木の枝刈り）
アイコン木の、葉ノードは、文書群の視覚化として用いる。特定の利用可能な表示領域を前提にすれば、葉ノードのアイコン全てをそれらの元のサイズで表示することが可能でない場合がある。アイコン木を下部から上部まで枝刈りすることによって、葉ノードの数は減少するものであり、アイコン・サイズは減少し得る。一実施例では、アイコン木は、葉ノード・アイコン集合が、利用可能な表示領域に収まるまで枝刈りされる。表示領域が大きい場合、表示領域が小さい場合と比べて、行う枝狩りは少なくなければならない。図３０（Ａ）乃至図３０（Ｅ）は、葉ノードと、木の枝刈りを行った後の残りの葉ノードとを、３つの別々の表示領域について示す。図３０（Ａ）は、葉ノード付きクラスタ木の例である。
【０１０１】
クラスタ数、表示画面のサイズ、及び文書収集物のコンテンツは、視覚化に影響を及ぼす。表示サイズが変わると、視覚化も変わるはずである。同じことが、文書収集物コンテンツに対する変更の場合もあてはまる。これらの依存関係によって、入力条件における変化は各々、アイコン視覚化を変え得る。したがって、アイコン視覚化は、動的なもの、すなわち、動的な文書アイコンである。
【０１０２】
図３１は、図３０（Ａ）において作成される葉クラスタに対する動的な文書アイコンと、個々のページのレイアウトの情報を表す動的な文書アイコンの例とを示す。図３０（Ｂ）は、木のノード毎にアイコン表現を備えている、図３０（Ａ）のクラスタ木を示す。
【０１０３】
図３０（Ｃ）は、モニタ表示上で表示可能な、図３０（Ｂ）のクラスタ木の一部分を（太字で）示す。図３０（Ｄ）は、PDA表示上で表示可能な、図３０（Ｂ）のクラスタ木の一部分を（太字で）示す。図３０（Ｅ）は、携帯電話表示上で表示可能な、図３０（Ｂ）のクラスタ木の一部分を（太字で）示す。一実施例では、クラスタ木は木データ構造表現を用いて実施される。
【０１０４】
（例示的な木の枝刈り）
木の枝刈りは、種々の方法で行い得る。以下に、3つの方法を詳細に説明する。実施形態において選ぶ枝刈り手法は、アプリケーションやユーザ選好によって変わってくる場合がある。
【０１０５】
vkはアイコン木におけるノード全てを表すものとする。ノード
【０１０６】
【数１６】
0004781924.tif 000020
で、
【０１０７】
【数１７】
0004781924.tif 000021
が葉ノードであり、かつ、
【０１０８】
【数１８】
0004781924.tif 000022
の親の子全ても葉ノードであるようなもの全てを見つけることとする。この集合は、葉ノード集合と呼ばれ、
【０１０９】
【数１９】
0004781924.tif 000023
によって表す。葉ノード集合の親ノードの集合は、
【０１１０】
【数２０】
0004781924.tif 000024
によって表す。
【０１１１】
枝刈りは、VPにおけるノードの子全てを取り除いて、枝刈りされた木の、葉ノードのアイコンによって文書全てを表すようにすることによって行い得る。
【０１１２】
1)クラスタ分割品質に関する枝刈り：VPにおける各ノードは、ノードの子（葉）ノードにおいて表す2つの集合に施される式(2)の目標関数Mcutの値によって表す、それと関連付けられるクラスタ分割評価を有する。葉ノードの枝刈りは、Mcut値が最大の、VPにおける親ノードをまず見つけ、更に、その親ノードの子（VLの要素）全てを取り除くことによって行う。
【０１１３】
2)アイコン・サイズに関する枝刈り：VLにおける各ノードは、アイコンの寸法ix,iy
によって表す、それと関連付けされる幾何学的なサイズを有する。アイコンの幾何学的な領域は、その場合、ix●iyによって表す。葉ノードの枝刈りは、同胞であり、かつ、最大（又は最小）の幾何学的な領域を有する葉ノード対vi1,v i2をまず判定し、次に、その葉ノードvi1,v i2を取り除くことによって行う。
【０１１４】
3)クラスタ要素数に関する枝刈り：各ノードは、それと関連付けられる、ノード・カウントと呼ぶ整数を有する。ノード・カウントは、ノードによって表す、クラスタに含まれる文書の数を表す。葉ノードの枝刈りは、同胞であり、かつ、ノード・カウントの和が最小である、すなわち、
node_count(vi1)+
node_count(vi2)=最大、
である葉ノード対vi1,v i2をまず判定し、次にそれらの葉ノードvi1,v i2を取り除くことによって行う。選択基準の代替策としては、
max(node_count(vi1),node_count(vi2))=最小、又は、
min(node_count(vi1),node_count(vi2))=最小、
というものがある。
【０１１５】
4)階層レベルに関する枝刈り：各ノードvは、それに関連付けられる階層レベルh(v)を有する。このレベルは、木の根からのノードvの距離を表す。葉ノードの枝刈りは、同胞であり、かつ、最大の階層レベルh(vi11)=h(vi22)を有する葉ノード対vi1,v i2をまず判定し、次に、それらの葉ノードvi1,v i2を取り除くことによって行う。
【０１１６】
5)クラスタ内の最小類似性に関する枝刈り：各ノードvは、それと関連付けされる類似性値sim(v)を有する。この類似性値は、クラスタ内のデータの類似性（例えば、データ点対の間の平均（最大）距離）を反映している。葉ノードの枝刈りは、同胞であり、かつ、最大の合成類似性sim(vi1)+sim(vi2)又はmax(sim(vi1),sim(vi2))を有する葉ノード対vi1,v i2をまず判定し、次に、それらの葉ノードvi1,v i2を取り除くことによって行う。
【０１１７】
6)枝刈り基準の組み合わせ、例えば、同胞であり、かつ、
h(vi11)+node_count(vi11)+
node_count(vi22)=最大
であることを満たす葉ノード対vi1,v i2を取り除くこと、も考えられる。
【０１１８】
枝刈り後、枝刈りされた木のノードを表すアイコンが利用可能な表示領域に収まるか否かについての判定が行われる。表示領域の幅がWであり、高さがHであり、葉ノードVi∈VL（VL=葉ノード集合）であると仮定すれば、システムは、アイコンが表示領域に収まるか否かを、単純な線形的な水平パッキング順序
【０１１９】
【数２１】
0004781924.tif 000025
に従って検査し、そのとき、ix(vi)は、ノードviを表すアイコンの幅である。その条件が満たされる場合、アイコンは全て、表示領域に収まる。アイコンを利用可能な表示に収めることは、例えば、R.  Johari,  J.  Marks,  A.  Partovi,  及びS.  Shieberによる「Automatic  Yellow-Pages  Pagination  and  Layout」Journal  of  Heuristics,  pp.  321-342,  1997；Kusiak  A,  Heragu  SSによる「The  facility  layout  problem」Eur  J  Opl  Res  29:229-251,1987；及び、R.  Francis,  L.  McGinnis,  J.  Whiteによる、Facility  Layout  and  Location:  An  Analytical  Approach,  2nd  edition,  Prentice  Hallなどの、より複雑な文書レイアウトを可能にする他の手法を用いても得ることができる。上記手法が適合しない場合、別の枝刈り工程が続く。
【０１２０】
一実施例では、クラスタ化と木枝刈りとの2つの処理工程は、対象の表示とその制約が事前に分かっている場合には1つに組み合わせる。各クラスタ工程後、新たに生成されるアイコンが、特定のレイアウト規則や制約を前提として、利用可能な表示領域に収まるか否かについての判定を行う。アイコンが収まらない場合、生成された葉ノードのみが取り除かれ、クラスタ木のその分岐ではクラスタ化はもう何も行われない。以下の擬似コードは、この手順をより詳細に説明している。木ノードのOPENリスト及びCLOSEDリストの語は、Nils  J.  Nilssonによる「Artificial  Intelligence」Morgan  Kaufman  Publishers,  Inc.,  San  Francisco,  1998から得ている。
【０１２１】
1.  根ノードv0のみから成るサーチ木Tを作成する。v0をOPENと呼ぶ順序リスト上に載せる。
【０１２２】
2.  当初は空き状態の、CLOSEDと呼ぶリストを作成する。
【０１２３】
3.  OPENが空き状態の場合、エラーによって終了する。
【０１２４】
4.  OPEN上の最初のノードv*を選択する。V*をOPENから取り除く。
【０１２５】
5.  v*をCLOSEDに加える。
【０１２６】
6.  v*を拡張し、子ノードv*1,v*2を生成する。
【０１２７】
7.  L(vis(Vopen)∪vis（v*1）∪vis（v*2）)を計算する。そのとき、Lは、レイアウトの適合性の品質を算出する関数である。可能な適合がない場合、Lは∞の値を呈する。
【０１２８】
8.  L(vis(Vopen)∪vis（v*1）∪vis（v*2）)<∞である場合、v*1をOPENに加える。
【０１２９】
9.  vis（v*i）の領域が、vis(Vopen)∪vis（v*1）∪vis（v*2）)を載せた後の利用可能な表示空間の領域よりも小さい場合、v*1をOPENから取り除く。
【０１３０】
10.  木枝刈り基準である、クラスタ分割品質、アイコン・サイズ、クラスタ要素数、階層レベル、クラスタ内の最小類似性などのうちの１つに関するOpenを順序付けする。
【０１３１】
11.  工程4に進む。
【０１３２】
図３２は、クラスタ化と枝刈りとの組み合わせを含む処理の一実施例の流れ図である。当該処理は、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータ上や専用マシン上で実行されるものなどの）ソフトウェア、又は両方の組み合わせを備え得る処理ロジックによって行われることが好ましい。図３２を参照すれば、処理ロジックは、文書を木にクラスタ化し、レイアウト機能を用いてアイコンを利用可能な表示空間に収めるということの利用可能性を検査することによって閉葉ノードを識別する（処理ブロック1401）。このことは、文書収集物や、表示の制約（例えば、表示コントラストや表示領域サイズ）を受け取ることに応じて行われる。次に、処理ロジックは、枝刈りされた木の、葉ノードでのアイコンを表示する（処理ブロック1402）。
【０１３３】
図３３は、アイコンをクラスタ表現として自動的に作成する処理の一実施例の流れ図である。処理は、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータ上や専用マシン上で実行されるものなどの）ソフトウェア、又は両方の組み合わせを備え得る処理ロジックによって行われる。
【０１３４】
図３３を参照すれば、当該処理は、処理ロジックがクラスタ分割の方向を余儀なくした特徴を受信することによって開始する（処理ブロック801）。それに対する応答として、処理ロジックは、特徴対幾何変換を行う（処理ブロック802）。変換の結果は、1つ又は複数の幾何学的な命令803である。例えば、幾何学的な命令は、システムに、矩形（形状、位置）を描写し、特定のベタ塗りの灰色の値によって矩形を塗りつぶし、画像をクロッピングし、画像を矩形に収めることを命じ得る。
【０１３５】
処理ロジックは更に、幾何学的な命令の実行の画像出力の最小サイズ（805）（例えば、塗りつぶされている矩形は特定の最小寸法を有する。）を判定するために最小サイズの判定（処理ブロック804）を行う。
【０１３６】
画像出力805の最小サイズを用いて、処理ロジックは、親ノードの命令リストに、幾何学的な命令と、関連した最小サイズとを追加し（処理ブロック806）、更新命令リスト(808)を生成するうえでの、画像出力の最小サイズを満たすよう、リストにおける幾何学的な命令を修正（例えば、スケーリング）する（処理ブロック807）。処理ロジックは、アイコン作成器を用いて動的な文書アイコン810を作成して、更新命令リスト808における命令を実行する（処理ブロック809）。
【０１３７】
上記の説明を読めば、当業者には本発明の変更や修正が明らかであろうが、言うまでもなく、例示により図示及び説明した実施形態はいずれも本発明を限定することを目的とするものではない。それゆえ、いろいろな実施形態で詳細に触れたが、クレームの範囲を限定する目的ではなく、本発明の重要であると考えられる特徴は、クレームに記載されている。
【図面の簡単な説明】
【０１３８】
本発明は、いろいろな実施形態の詳細な説明と添付した図面を参照すれば、よりよく理解できるであろう。しかし、これらは、本発明を特定の実施形態に限定するものではなく、本発明を説明し理解してもらうためのものあると解釈しなければならない。
【図１】文書イメージのコンテント適応スケーリングを実行するプロセスの一実施形態を示すフロー図である。
【図２】文書オブジェクトの一例とそのボロノイ図を示す図である。
【図３】文書オブジェクトの中心を結ぶ線の境界ボックスセグメントとの交点の計算を示す図である。
【図４】文書オブジェクトの中心を結ぶ線の境界ボックスセグメントとの交点の計算の別法を示す図である。
【図５】波線により示された距離を計算して境界ボックスセグメントを分離している空白を測る代替手段を示す図である。
【図６】図２に示した文書例と関連したグラフの隣接行列を示す図である。
【図７】グラフィックス的に示したツリー表示を示す図である。
【図８】階層的文書構造を空白ツリーに組み込むプロセスの一実施形態を示すフロー図である。
【図９】レイアウトツリーの一例を示す図である。
【図１０】情報検索のプロセスの一実施形態を示すフロー図である。
【図１１】それぞれが最小スケーリングファクタでスケーリングされている一群の文書の一組のサムネイルを示す図である。
【図１２】それぞれが最小スケーリングファクタでスケーリングされている一群の文書の一組のサムネイルを示す図である。
【図１３】それぞれが個別の最小スケーリングファクタでスケーリングされている、検索タスクの結果を示すテキストを含む一群の文書のサムネイルを示す図である。
【図１４】それぞれが最小スケーリングファクタでスケーリングされている、検索タスクの結果を示すテキストを含む一群の文書のサムネイルを示す図である。
【図１５】ＸＭＬボックス中のメタデータとしてＷＳＴを含むＪＰＭ圧縮された文書イメージを生成するシステムを示す図である。
【図１６】検索クエリーに応答してサムネイルイメージを生成するデータを抽出及びデコードするプロセスの一実施形態を示すフロー図である。
【図１７】文書レイアウト構造の一例を示す図である。
【図１８】図１７の文書のレイアウトツリーの一例を示す図である。
【図１９】図１７の文書のＷＳＴを示す図である。
【図２０】テキスト検索の一部として返された、領域が視覚的に分離された３つの文書のアイコン化されたサムネイルを有する２つのコラムを有するアイコンを示す図である。
【図２１】文書を示すノードを有するレイアウトツリーを示す図である。
【図２２】特定されたノードを有する文書のＷＳＴを示す図である。
【図２３】文書を示すノードを有するレイアウトツリーを示す図である。
【図２４】特定されたノードを有する文書のＷＳＴを示す図である。
【図２５】文書を示すノードを有するレイアウトツリーを示す図である。
【図２６】特定されたノードを有する文書のＷＳＴを示す図である。
【図２７】ここに説明した１以上の動作を実行するコンピュータシステムの実施例を示すブロック図である。
【図２８】（Ａ）はアイコン表現の例を示す図、（Ｂ）はアイコン表現の例を示す別の図、（Ｃ）〜（Ｈ）はアイコン表現の例を示す更に別の図である。
【図２９】（Ａ）は2列の、テキストのみの文書の用法を説明する図で、（Ｂ）は3列の混合文書の用法を説明する図である。
【図３０】（Ａ）は葉ノードを備えているクラスタ木の例を示す図、（Ｂ）は木のノード毎にアイコン表現を備えている、（Ａ）のクラスタ木を示す図、（Ｃ）はモニタ表示上に表示可能な、（Ｂ）のクラスタ木の一部分を示す図、（Ｄ）はPDA表示上に表示可能な、（Ｂ）のクラスタ木の一部分を示す図、（Ｅ）は携帯電話表示上に表示可能な、（Ｂ）のクラスタ木の一部分を示す図である。
【図３１】図７（Ａ）の、作成された葉クラスタに対する文書アイコンと、個々のページのレイアウトの情報を表すダイドコン(dydocons)の例とを示す図である。
【図３２】クラスタ化と枝刈りとの組み合わせを表す流れ図である。
【図３３】アイコンをクラスタ表現として自動的に作成する手順の一実施例を示す流れ図である。
【符号の説明】
【０１３９】
２７０４  メインメモリ
２７０６  スタティックメモリ
２７０７  データ記憶装置
２７１１  バス
２７１２  プロセッサ
２７２１  ディスプレイ
２７２２  キーボード
２７２３  カーソル制御装置
２７２４  ハードコピー装置
２７２５  有線／無線通信装置
【図１】
0004781924.tif 000026
【図２】
0004781924.tif 000027
【図３】
0004781924.tif 000028
【図４】
0004781924.tif 000029
【図５】
0004781924.tif 000030
【図６】
0004781924.tif 000031
【図７】
0004781924.tif 000032
【図８】
0004781924.tif 000033
【図９】
0004781924.tif 000034
【図１０】
0004781924.tif 000035
【図１１】
0004781924.tif 000036
【図１２】
0004781924.tif 000037
【図１３】
0004781924.tif 000038
【図１４】
0004781924.tif 000039
【図１５】
0004781924.tif 000040
【図１６】
0004781924.tif 000041
【図１７】
0004781924.tif 000042
【図１８】
0004781924.tif 000043
【図１９】
0004781924.tif 000044
【図２０】
0004781924.tif 000045
【図２１】
0004781924.tif 000046
【図２２】
0004781924.tif 000047
【図２３】
0004781924.tif 000048
【図２４】
0004781924.tif 000049
【図２５】
0004781924.tif 000050
【図２６】
0004781924.tif 000051
【図２７】
0004781924.tif 000052
【図２８】
0004781924.tif 000053
【図２９】
0004781924.tif 000054
【図３０】
0004781924.tif 000055
【図３１】
0004781924.tif 000056
【図３２】
0004781924.tif 000057
【図３３】
0004781924.tif 000058