(57)【要約】【課題】  特定の表示に適した視覚化（例えば、アイコン）を生成する方法及び装置を開示する。【解決手段】  一実施例では、方法は、特定の表示上の視覚化に適した同様なレイアウト特徴を有する文書画像群を複数の文書画像から、複数の文書画像に相当するレイアウト解析情報に基づいて選択する工程と、複数の視覚化を作成して、文書画像群についての文書レイアウト情報を、1つ又は複数の表示装置特性と、文書群のコンテンツとに基づいて視覚化する工程とを備える。【選択図】      図９
2006179002.tif 000002
【特許請求の範囲】
【請求項１】
方法であって、
特定の表示上の視覚化に適した同様なレイアウト特徴を有する文書画像群を複数の文書画像から、該複数の文書画像に相当するレイアウト解析情報に基づいて選択する工程と、
複数の視覚化を作成して、文書画像群についての文書レイアウト情報を、1つ又は複数の表示装置特性と、文書群のコンテンツとに基づいて視覚化する工程とを備えることを特徴とする方法。
【請求項２】
請求項1記載の方法であって、
視覚化可能な文書レイアウト特徴を前記複数の文書画像から抽出する工程と、
該複数の文書画像からの文書画像を前記文書画像群に前記視覚化可能な文書レイアウト特徴に基づいてグループ化する工程とを更に備えることを特徴とする方法。
【請求項３】
請求項2記載の方法であって、
前記文書レイアウト特徴を分類に分割する工程を更に備え、
文書画像のグループ化が前記分類に基づくものであることを特徴とする方法。
【請求項４】
請求項1記載の方法であって、
同様なレイアウト特徴を有する文書画像群を選択する工程が、特徴的な、視覚化可能な特徴によって文書画像をクラスタ化する工程を備えることを特徴とする方法。
【請求項５】
請求項4記載の方法であって、前記複数の視覚化を作成する工程が、
文書レイアウトのアイコン表現をアイコン視覚要素の収集物として作成する工程と、
1つ又は複数の葉ノード・クラスタを表示及びレイアウトの制約に基づいて縮小する工程とを備えることを特徴とする方法。
【請求項６】
請求項4記載の方法であって、特徴的な視覚化可能な特徴によって文書画像をクラスタ化する工程が、
特徴空間を部分空間に視覚化特性によって分割する工程と、
特徴ベクトルを前記特徴空間の特徴部分空間上に投影する工程と、
文書画像を前記特徴部分空間の各々においてクラスタ化する工程と、
１つのクラスタ分割をクラスタ分割から前記特徴部分空間毎に選択する工程とを備えることを特徴とする方法。
【請求項７】
請求項6記載の方法であって、１つのクラスタ分割を前記クラスタ分割から前記特徴部分空間毎に選択する工程が、
クラスタ木を、葉から、関連した根まで、前記クラスタ木の、葉ノード全てが表示領域に収まるまで縮小する工程を備えることを特徴とする方法。
【請求項８】
1つ又は複数の記録可能媒体を有する製造物品であって、前記1つ又は複数の記録可能媒体は、システムによって実行されると該システムに方法を行わせる命令を前記1つ又は複数の記録可能媒体上に記憶しており、前記方法が、
特定の表示上の視覚化に適した同様なレイアウト特徴を有する文書画像群を複数の文書画像から、該複数の文書画像に相当するレイアウト解析情報に基づいて選択する工程と、
複数の視覚化を作成して、文書画像群についての文書レイアウト情報を、1つ又は複数の表示装置特性と、文書群のコンテンツとに基づいて視覚化する工程とを備えることを特徴とする製造物品。
【請求項９】
請求項8記載の製造物品であって、前記方法が、
視覚化可能な文書レイアウト特徴を前記複数の文書画像から抽出する工程と、
該複数の文書画像からの文書画像を前記文書画像群に、前記視覚化可能な文書レイアウト特徴に基づいてグループ化する工程とを更に備えることを特徴とする製造物品。
【請求項１０】
請求項9記載の製造物品であって、前記方法が、
前記文書レイアウト特徴を分類に分割する工程を更に備え、
文書画像のグループ化が前記分類に基づいていることを特徴とする製造物品。
【請求項１１】
請求項8記載の製造物品であって、同様なレイアウト特徴を有する文書画像群を選択する工程が、
文書画像を特徴的な視覚化可能な特徴によってクラスタ化する工程を備えることを特徴とする製造物品。
【請求項１２】
請求項11記載の製造物品であって、前記複数の視覚化を作成する工程が、
文書レイアウトのアイコン表現をアイコン視覚要素の収集物として作成する工程と、
1つ又は複数の葉ノード・クラスタを表示及びレイアウトの制約に基づいて縮小する工程とを備えることを特徴とする製造物品。
【請求項１３】
装置であって、
特定の表示上の視覚化に適した同様なレイアウト特徴を有する文書画像群を複数の文書画像から、該複数の文書画像に相当するレイアウト解析情報に基づいて選択する手段を備えることを特徴とする装置。
【請求項１４】
装置であって、
複数の視覚化を作成して、文書画像群についての文書レイアウト情報を、1つ又は複数の表示装置特性と、文書群のコンテンツとに基づいて視覚化する手段を備えることを特徴とする装置。
【請求項１５】
方法であって、
文書画像を、特徴的な視覚化可能な特徴によってクラスタ化する工程と、
文書レイアウトの特徴的な視覚化可能な特徴のアイコン表現をアイコン視覚要素の収集物として作成する工程と、
1つ又は複数のクラスタを表示の制約に基づいて縮小する工程とを備えることを特徴とする方法。
【請求項１６】
請求項15記載の方法であって、
1つ又は複数のクラスタを縮小する工程が、クラスタ分割品質に基づいていることを特徴とする方法。
【請求項１７】
請求項16記載の方法であって、
前記文書画像を表す、Mcut値が最大である親ノードをクラスタ木において見つける工程と、
前記親ノードの子であるクラスタ全てを取り除く工程とを更に備えることを特徴とする方法。
【請求項１８】
1つ又は複数の記録可能媒体を有する製造物品であって、前記1つ又は複数の記録可能媒体は、システムによって実行されると該システムに方法を行わせる命令を前記1つ又は複数の記録可能媒体上に記憶しており、前記方法が、
文書画像を、特徴的な視覚化可能な特徴によってクラスタ化する工程と、
文書レイアウトの特徴的な視覚化可能な特徴のアイコン表現をアイコン視覚要素の収集物として作成する工程と、
1つ又は複数のクラスタを表示の制約に基づいて縮小する工程とを備えることを特徴とする製造物品。
【請求項１９】
装置であって、
文書画像を、特徴的な視覚化可能な特徴によってクラスタ化する手段と、
文書レイアウトの特徴的な視覚化可能な特徴のアイコン表現をアイコン視覚要素の収集物として作成する手段と、
1つ又は複数のクラスタを表示の制約に基づいて縮小する手段とを備えることを特徴とする装置。
【請求項２０】
特徴的な視覚可能な特徴によって文書画像をクラスタ化する方法であって、
特徴空間を部分空間に視覚化特性によって分割する工程と、
特徴ベクトルを前記特徴空間の特徴部分空間上に投影する工程と、
文書画像を前記特徴部分空間の各々においてクラスタ化する工程と、
１つのクラスタ分割をクラスタ分割から前記特徴部分空間毎に選択する工程とを備えることを特徴とする方法。
【請求項２１】
装置であって、
特徴的な視覚可能な特徴によって文書画像をクラスタ化する木クラスタ化装置と、
文書レイアウトの特徴的な視覚可能な特徴のアイコン表現をアイコン視覚要素の収集物として作成するアイコン作成装置と、
枝刈りされた木の、葉ノードでのアイコンを表示するうえでの表示の制約に基づいて1つ又は複数のクラスタを縮小する木枝刈り装置とを備えることを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般的に文書処理の分野に関し、特に、個々の文書及び文書収集物に対するアイコンの作成に関する。
【背景技術】
【０００２】
ディジタル文書の量の一層の増加によって、検索アルゴリズムについての課題が増えてきており、効果的な解決策が一層重要になってきている。文書検索の分野は、文書におけるテキストの抽出及び評価を主たる焦点として広く研究されている。
【０００３】
文書検索手法は、テキストベースの検索手法と画像ベースの検索手法とに分類することができる。用いる手法に応じて、結果が、テキストや画像を用いてユーザに適宜、提示される。例えば、コンテンツベースの画像検索（CBIR）アプリケーションでは、サーチ結果は画像として表示し得るが、それは利用可能なものとして存在するテキスト情報が何らないからである。一方、文書検索結果はテキスト形式のみで表されることが多いが、それは、テキスト解析（例えば、OCR）が文書画像に対して行われた唯一の解析であったからである。
【０００４】
サムネールをテキストに加えて、検索結果を表すのに用いてきた。検索に用いるサーチ・アルゴリズムはテキスト特徴のみに基づいている一方、サムネール画像は、テキスト結果への直接のリンクが、それらが同じ文書を表すということを除けば何らなしで、「特定の追加情報」として表示されるに過ぎない。
【０００５】
ゼロックス社の拡張サムネールは、HTMLページに存在するキーワードを、サムネールにおける相当する場所にペーストして作成される。
【０００６】
検索テキスト結果のリストを表示する以外に、テキストベースの検索手法は、文書データベースから導き出される基礎特徴空間の全て又は一部の構造も表示し得る。結果として表示される画像は、高次元データの視覚化、すなわち、特徴空間における点、である。画像として表示し得る低次元（２次元）データ・プロットに高次元データを変換する手法がいくつか存在する。手法例としては、デンドログラム手法や多次元スケーリング手法がある。デンドログラムを用いて文書クラスタを視覚化することは公知である。例えば、van  Liere,  R.,deLeeuw,  W.,Waas,F.による「Interactive  Visualization  of  Multidimensional  Feature  Spaces」  Proc.  of  Workshop  on  New  Paradigms  for  Information  Visualization,  Washington  DC,  November  2000を参照。多次元スケーリング（MDS）も従来技術において用いられてきた。例えば、Leouski,  A,  Allan  J.による「Visual  Interactions  with  a  Multidimensional  Ranked  List」  Proc.  of  the  21st  Annual  International  ACM  SIGIR  Conference  on  Research  and  Development  in  Information  Retrieval,  pp.  353-354,  1998参照。データ・マウンテン(Data  Mountain)手法と呼ばれる手法によって、ユーザが自らの空間的サムネール配置を、シミュレーション3次元環境において規定することが可能になる。更なる情報については、Robertson,  G.,  Czerwinski,  M.,  Larson  K.,  Robbins,  D.,  Thiel,  D.  及びvan  Dantzich,  M.による「Data  Mountain:  Using  spatial  memory  for  document  management」  Proceedings  of  UIST  ’98,  11th  Annual  Symposium  on  User  Interface  Software  and  Technology,  pp.  153-162,  1998を参照。
【０００７】
テキストベースの検索結果のテキストのみの視覚化は、コンベラ社(http://www.convera.com/Products/rw_categorization.asp)のソフトウェア「RetrievalWare」によって行われる。テキストベースの検索結果のリストを前提にすれば、コンベラ社は、分類の、特徴的な語又は句を含むラベルを備えている限られた数のフォルダの形式で表示される、検索結果を自動的に分類したものをユーザに備える。コンベラ社はこのアルゴリズム的手法を動的な分類と呼んでいる。分類の結果は、テキスト・ラベルを付したフォルダ画像として視覚化される。
【０００８】
文書検索、文書サーチ及び文書ブラウジングにおいてテキスト特徴を用いることは広く行われている一方、視覚特徴は一般的に用いられている訳でない。単純なテキスト結果リストに加え、従来技術において公表されている、検索結果の視覚化は、伝統的な文書サムネールと、例えば、デンドログラム手法や多次元スケーリング手法（van  Liere,  R,  deLeeuw,  W、Waas,  F..による「Interactive  Visualization  of  Multidimensional  Feature  Space」  Proc.  of  Workshop  on  New  Paradigms  for  Information  Visualization,  Washington  DC  November  2000参照。）を施した、高次元特徴空間の視覚化との何れかから成る。
【０００９】
サムネール視覚化の場合、サムネール作成に用いるアルゴリズムは通常、個々の画像をダウンサンプリングするに過ぎない。ユーザが個々のサムネールにおいて認識する特徴、喪失される情報や、サムネール収集物によって伝達される情報に対しては明示的な制御が何ら存在しない。例外としては、判読可能なテキスト部分と認識可能な画像部分とを示すことに焦点を当ててサムネールに似た画像を作成する「SmartNail」手法がある。「SmartNail」手法によって、サムネール視覚化は、単一の画像のみの情報から得られ、何れの特定の問い合わせ駆動型検索結果にもリンクされていない。しかし、現行の「Smart  Nail」手法は、文書収集物についてではなく、個々の画像について画像表現を、問い合わせ情報に関する知識なしで計算する。「SmartNail」に関する更なる情報については、西暦2003年5月9日付で出願され、西暦2004年7月29日付で公開（公開第20040145593号）された「Resolution  Sensitive  Layout  of  Document  Regions」と題する米国特許出願第10/435,300号を参照。
【００１０】
高次元データ視覚化の場合、ユーザは、位置的な特徴の、文書画像との関連付けが何らされていない抽象表現に直面する。MDS及びデンドログラムの視覚化は、文書画像に関する情報は伝達せず、抽出される特徴の配置のみを伝達する。データ・マウンテン手法は、ユーザによって個人的な選好に従って配置される従来のサムネールを用いる。別のユーザにとっては、この構造は意味がない。
【００１１】
画面領域は非常に限られていることが多いので、個々の文書毎の視覚化を画面上で示すのは可能でない。よって、いきおい、同様な特徴を有する文書をグループ化し、各グループをラベルと関連付ける。このグループ化すなわちクラスタ化は、検索アプリケーションにおいては通常の手法である。検索を有することなくデータ集合全体をクラスタ化することとは異なる、検索結果のクラスタ化は、本明細書及び特許請求の範囲では、検索後クラスタ化として表す。Park,  G.,  Baek,  Y.,  Lee,  H.-K.による「Re-ranking  algorithm  using  post-retrieval  clustering  for  content-based  image  retrieval」  Information  Processing  and  Management,  vol.  41,  no.  2,  pp.  177-194,  2005参照。クラスタは通常、テキスト特徴に関して作成される。クラスタ・ラベルは通常、共通のクラスタ・コンテンツのテキスト記述である。
【００１２】
クラスタ化は、他の方法で行い得る。１つの例示的な文書システムでは、テクチャを文書の分類及びクラスタ化に用いて例による検索をサポートする。文書レイアウトを記述するテクスチャは、ユーザによる検索入力である。一実施例では、システムはクラスタ化アルゴリズムを用いて、ユーザ記述文書レイアウトに一致する文書を戻すことによって応答する。クラスタ化アルゴリズム（例えば、Kミーンズや誤差平方和）は、文書の通常の特徴に関して文書をグループ化するのに使用し得る。このアルゴリズムは、アイコンとして視覚化された、クラスタ・プロトタイプ集合を戻す場合があり、そのうちの１つを用いて更なる検索を行い得る。更なる情報については、西暦1999年8月3日付発行の「Image  Database  Browsing  and  Query  Using  Texture  Analysis」と題する米国特許第5,933,823号参照。
【００１３】
一般的に、クラスタ化手法は、ボトムアップ手法とトップダウン手法とに分けることができる。ボトムアップ手法すなわち集塊性手法は、各データ点をそれ自体のクラスタとして扱い、次に、上に上がる途上でクラスタの併合を行うことによって始まる。トップダウン手法すなわち分析的手法は、データ全てが１つのクラスタであり、次に、このクラスタをより小さなクラスタに徐々に分割することによって始まる。分析的手法に関する更なる情報については、Duda,  R.O.,  Hart,  P.E.による「Pattern  Classification  and  Scene  Analysis」  Wiley,  New  York  1973参照。
【００１４】
クラスタ化手法の別の特徴付けとしては、一元的手法と多元的手法がある。一元的手法では、クラスタ・メンバシップは、単一の特徴の有無に基づいている。多元的手法は、2つ以上の特徴を用いる。「A  Hierarchical  Monothetic  Document  Clustering  Algorithm  for  Summarization  and  Browsing  Search  Results」  Proceedings  of  the  13th  international  conference  on  World  Wide  Web,  New  York,  NY,  USA,  pp.  658-665,  2004.
【発明の開示】
【発明が解決しようとする課題】
【００１５】
本明細書及び特許請求の範囲では、特定の表示に適した視覚化（例えば、アイコン）を生成する方法及び装置を開示している。
【課題を解決するための手段】
【００１６】
一実施例では、方法は、特定の表示上での視覚化に適した同様なレイアウト特徴を有する文書画像群を複数の文書画像から、複数の文書画像に相当するレイアウト解析情報に基づいて選択する工程と、複数の視覚化を作成して、文書画像群についての文書レイアウト情報を1つ又は複数の表示装置特性と文書群のコンテンツに基づいて視覚化する工程とを備える。
【発明を実施するための最良の形態】
【００１７】
本発明は、本発明の種々の実施例の、以下記載の詳細説明と、添付図面とから更に十分に分かるものであるが、それらは、特定の実施例に本発明を限定するものとして解するべきでなく、説明及び理解のみを目的としている。
【００１８】
文書検索結果の視覚化を行う方法及び装置を説明する。結果は、動的な文書アイコンによって表示される。一実施例では、このアイコンは、文書収集物に含まれる幾何情報及び論理情報を反映し、表示特性、文書コンテンツ及び/又はユーザ入力の変化に適合する。一実施例では、各視覚化は、表示特性及びユーザ入力を考慮して文書についてアルゴリズム的に判定される情報を知覚される情報にマッピングする。
【００１９】
一実施例では、個々の文書及び文書収集物の視覚化は、一般的なレイアウト情報（例えば、幾何情報及び論理情報）の伝達を強調する。一実施例では、従来技術の欠点の一部を解決するために、視覚形式で表す、文書の論理的な特徴及び幾何学的な特徴についての情報を含むアイコン画像が生成される。一実施例では、アイコン表現は、文書収集物を通して幾何学的なレイアウト情報及び論理的なレイアウト情報を表すが、テキストの読みやすさは犠牲にする。
【００２０】
文書画像のレイアウト情報の選択は、ユーザが文書を認識するのに視覚化に含まれる情報が有用であるようにするよう、改善させ、場合によっては最適化させ得る。例えば、従来のサムネール表示において、画面ページ上に示す結果全てのサムネールが（ダウンサンプリング処理において喪失される高解像度特徴が唯一の特徴的な特徴であったので）同じように見える場合、画面ページ上の文書全てを一体化させる視覚化としての役割を果たす、それらのサムネールのうちの１つのみを示すことによって情報を伝え得る。これによって、別のテキスト結果により多くの空間を有することが可能になる。一実施例では、一体化させるサムネール視覚化は、概要レベルの文書情報（例えば  列レイアウト情報）のみを含んでいる可能性が高い。そのような列レイアウトの視覚化は、当初のサムネール・サイズよりもなお小さいアイコン表現によって可能である。列と背景とのコントラストが十分大きいとみなせば、ユーザは列レイアウトをなお認識し得る。
【００２１】
以下の記載では、数多くの詳細を表して本発明の更に徹底的な説明を備えている。しかし、本発明をこれらの特定の詳細なしで実施し得るということは当業者に明らかなものである。他の場合には、周知の構造及び装置を、詳細にではなく構成図形式で表して、本発明を分かりにくくしないようにしている。
【００２２】
以下の詳細説明の一部は、コンピュータ・メモリ内部のデータ・ビットに対する演算のアルゴリズム及び記号表現によって示す。これらのアルゴリズムの記述と表現は、当該データ処理技術分野における当業者が別の当業者に自分達の作業内容の本質を最も効果的に伝えるのに用いられる手段である。アルゴリズムは本明細書及び特許請求の範囲において、更に一般的には、所望の結果につながる首尾一貫した一連の工程であるように着想されている。当該工程は、物理的数量を物理的に操作することを必要とするものである。これらの数量は、記憶、転送、合成、比較やその他の方法による操作ができる電気信号又は磁気信号の形式を通常は呈するものであるが、必ずしもそうでなくてもよい。主に慣用的な理由で、これらの信号をビット、値、要素、記号、文字、項、数字などとして表すことが場合によっては有用であることが証明されている。
【００２３】
これらの語及び同様な語は全て、適切な物理的数量と関連付けられるべきであり、この数量に付される有用なラベルに過ぎないことを、しかし、念頭に入れるべきである。以下の記載から明らかであるように、別途明記しない限り、本明細書及び特許請求の範囲を通して、「処理」、「計算」、「算出」、「判定」や「表示」などの語を用いた記載は、コンピュータ・システムのレジスタ内とメモリ内とで物理的（電子的）数量として表すデータを操作し、該データを、コンピュータ・システムのメモリ内若しくはレジスタ内やその他のそのような情報記憶デバイス内、情報伝送デバイス内又は情報表示デバイス内で物理的数量として同様に表す別のデータに変換するコンピュータ・システムや同様な電子計算機装置の動作及び処理を表す。
【００２４】
本発明は、本明細書及び特許請求の範囲記載の手順を行う装置にも関する。この装置は、要求される目的用に特別に構築されてもよく、コンピュータに記憶されているコンピュータ・プログラムによって選択的に起動されるか再構成される汎用コンピュータを備えてもよい。そのようなコンピュータ・プログラムは、電子命令を記憶させるのに適した、フロッピー（登録商標）・ディスク、光ディスク、CD-ROM及び光磁気ディスクを含む何れかの種類のディスク、読み取り専用メモリ(ROM)、ランダム・アクセス・メモリ(RAM)、EPROM、EEPROM、磁気カード若しくは光カードなどであるがそれらには限定されないコンピュータ判読可能記憶媒体、又は何れかの種類の媒体で、各々がコンピュータ・システム・バスに結合されているものに記憶させ得る。
【００２５】
本明細書及び特許請求の範囲に示すアルゴリズム及び表示は、何れかの特定のコンピュータやその他の装置に固有に関連する訳でない。種々の汎用システムを本明細書及び特許請求の範囲記載の教示によるプログラムとともに用いてもよく、更に特化した装置を構築して要求方法工程を行うことが有用であることが明らかになる場合もある。これらの各種システムに要求される構造は以下の記載から明らかとなる。更に本発明は、何れかの特定のプログラミング言語を参照しながら記載されている訳でない。各種プログラミング言語を用いて本明細書及び特許請求の範囲記載の本発明の教示を実施し得ることが分かる。
【００２６】
マシン判読可能媒体は、マシン（例えば、コンピュータ）によって判読可能な形式での情報を記憶又は伝送する何れかの機構を含む。例えば、マシン判読可能媒体は読み取り専用メモリ（「ROM」）；ランダム・アクセス・メモリ（「RAM」）；磁気ディスク記憶媒体；光記憶媒体；フラッシュ・メモリ・デバイス；及び、電気的形式、光学的形式、音響的形式やその他の形式の伝搬信号（例えば、搬送波、赤外線信号、ディジタル信号等）；などを含む。
【実施例】
【００２７】
（概要）
動的な文書アイコンは、文書及び文書収集物の一般的なレイアウト情報（例えば、幾何情報や論理情報）を伝達する。そのような情報は、文書から導き出される特徴によって記述される。一実施例では、特徴空間は、文書特有の特徴の視覚化に焦点を当てて、テキスト記述によって表すよりも容易に視覚化可能な情報をユーザに備える文書特徴に限定される。視覚的に容易に認識可能であるがテキストによって説明するのはずっと難しい一般的な特徴としては、形状、テクスチャ、位置及び色がある。一実施例では、これらの一般的な特徴は、文書特有の特徴に以下のように関連付けられる。
【００２８】
●  形状  →  文書ゾーンや列の矩形形状
●  テクスチャ  →  テキスト（太字及び標準）、グラフィック、画像
●  位置  →  ゾーン位置、読み取り順序
●  色  →  スポットカラー、色画像及び色グラフィックス
図1は、新たなアイコン標準を用いた、画像による視覚文書レイアウト特徴の記述例を示す。ユーザに伝える必要がある情報が列レイアウト、題名及び画像位置である場合、アイコン視覚化は、通常の寸法のサムネールや、テキストのみのバージョンと比べて縮小された寸法でその情報を表す。
【００２９】
前述の多くの特徴が、文書レイアウト解析の結果として、利用可能なものとして存在する。これらは、文書ゾーンのバウンディング・ボックス、列へのグループ化や、読み取り順序を含むが、それらに限定されない。これらは、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などの周知の方法で取得し得る。更に、一実施例では、ゾーンはそのコンテンツによって分類される。一実施例では、３つのクラス、すなわち、テキスト・コンテンツ、グラフィック・コンテンツ及び画像コンテンツが考察され、テキスト・ゾーンは題名ヘッディングやセクション・ヘディングに更に分類される。
【００３０】
一実施例では、2つの分類、すなわち、幾何学的な特徴及び論理的な特徴への特徴の分割が行われる。幾何学的な特徴は例えば、列レイアウトと、ゾーンの位置とを含む一方、論理的な特徴は例えば、ゾーン・コンテンツとテキスト特徴とを含む。
【００３１】
一実施例では、幾何学的な特徴及び論理的な特徴への分割の他に、階層構造を施し得る。列は文書ゾーンから作成される。ゾーンのコンテンツは、題名を含むテキストでも、テキスト・キャプションを含む画像でもよい。
【００３２】
図2は、幾何学的な特徴と論理的な特徴とに分けられている、レイアウト解析特徴の階層構造の一実施例を示す。文書特徴空間は、論理的な特徴の空間Lと幾何学的な特徴の空間Gとに分けられている。一実施例では、Lにおける特徴LiとGにおける特徴Giは、階層的に配列され、L0＞l1＞…＞Lnと、G0＞G1＞…＞Gmとによって表される。
【００３３】
（例示的な動的文書アイコン生成システム）
一実施例では、動的な文書アイコン生成システムは、文書画像クラスタの視覚化を生成する。各視覚化は、文書レイアウト特徴を含む。一実施例では、テキストは視覚化においては抑制される。よって、元のレイアウト特徴が視覚化され、テキストの読みやすさは無視される。従来技術と比べて、視覚化は文書コンテンツのみによって変わってくるのみならず、表示装置によって課される制約によっても変わってくる。この制約の例として、コントラスト比、装置解像度（絶対画素数と相対dpi）及び、モノクロ/カラーがある。
【００３４】
一実施例では、システムは、3つの装置、すなわち、木クラスタ化装置、アイコン作成装置及び木枝刈り装置、を備える。これらの装置の各々は、動的な文書アイコンを表示する対象の表示装置の表示特性に基づいて動作し得る。図3は、表示に適応した視覚化システムの文書レイアウト特徴についての概略を表す。図3を参照すれば、木クラスタ化装置301は、収集物310における文書画像を木にクラスタ化する。一実施例では、木クラスタ化装置301は表示装置特性320に基づいて動作し得る。アイコン作成装置302は、木クラスタ化装置301が文書収集物310を木にクラスタ化することに応じて、かつ、木枝刈り装置303がクラスタ木の枝刈りを行うことに応じて、アイコンをクラスタ表現として作成する。アイコン作成装置302と木枝刈り装置303との一方又は両方は、表示装置特性320に基づいて動作し得る。システムの出力は、枝刈りされた木の、葉ノードからのアイコン表現（アイコン）330である。
【００３５】
図3のシステムは、文書群を処理する。この群は、ファイル・フォルダにおけるテキスト検索又は収集物の結果であり得る。文書のレイアウトについての構造情報は、利用可能なものとして存在しているものとみなす。
【００３６】
（文書の、木へのクラスタ化）
一実施例では、文書は、視覚化可能な特徴に関する検索後クラスタ化を用いてクラスタ化される。各クラスタ化工程では、一意の幾何学的な特徴又は論理的な特徴を選んで分割判定を駆動させる。そのようにして、論理的な特徴及び幾何学的な特徴に関するクラスタ化判定を、曖昧でなく反映した（アイコン形式での）視覚ラベルを作成することが可能になる。
【００３７】
一実施例では、クラスタ化手法は、同質の特徴、すなわち、理想的には、明らかに優位に立っている論理的な特徴又は幾何学的な特徴、を備えている集合にデータを分割する。一実施例では、広いサーチ基準から開始して、それを連続して精緻化する通常のサーチ手法が動機となって、集塊性の階層クラスタ化の代わりに分析的手法を用いる。それは、根から葉までの完全なクラスタ階層は必要でなくなるからである。
【００３８】
一実施例では、一元的な分析的な階層手法が選ばれる。多元的手法よりも一元的手法を選ぶがそれは、最終クラスタ間の特徴的な特性を曖昧でない視覚化に変えることが必要であるからである。この手法では、階層における各レベルiで、現行のデータ集合が、選ばれた特徴Lk及びGlによって個々にクラスタ化される。一実施例では、クラスタ化は、周知技術（Ding,  C.H.Q他による「A  Min-max  Cut  Algorithm  for  Graph  Partitioning  and  Data  Clustering」Proc.  Int’l  Conference  on  Data  Mining,  San  Jose,  CA,  pp.  107-114,  2001参照。)  の最小最大カット(MMC)アルゴリズムを用いて行われる。あるいは、kミーンズのアルゴリズムを用い得る。しかし、MMCのほうが優れた特性を有するものと考えられている（Leouski,  A.,Allan,  J.による「Visual  Interactions  with  a  Multidimensional  Ranked  List」Proc.  of  the  21st  Annual  International  ACM  SIGIR  Conference  on  Research  and  Development  in  Information  Retrieval,  pp.  353-354,  1998）。
【００３９】
一実施例では、木クラスタ化装置301は、一元的な（単一の特徴の）、分析的な（トップダウンの）階層クラスタ手法を文書画像に施す。各クラスタ化工程では、2元分割が行われる。３つのゾーンの特性の、（階層構造の）位置及び形状、ゾーン・テクスチャ、ゾーン色が、大局的な文書特徴空間における３つの方向を規定する。これらの、特徴空間の部分空間はF1、F2、F3によって表す。
【００４０】
各クラスタ化工程では、現行の文書集合の現行の特徴データが、特徴空間の個々の部分空間各々の上に投影される。結果として生じる特徴ベクトルは、下記の最小最大カット・アルゴリズムによって処理される。一実施例では、アルゴリズムは、特徴ベクトルの、クラスタ内の類似性を最大にし、特徴ベクトルの、２つの別々のクラスタ間での類似性を最大にしようとする。クラスタ内の類似性が十分大きいという条件の下で、特徴部分空間毎に分割されたクラスタが評価され、最善のものが最終のクラスタ化分割として選ばれる。そのようにして、クラスタ化分割が、特徴空間の好ましい部分空間において行われる。図4は、分割手順の概要を示す。
【００４１】
（最小・最大カット・アルゴリズム）
一実施例では、木クラスタ化装置301は、最小・最大アルゴリズムをクラスタ化処理の一部として用いる。一実施例では、用いるクラスタ化手法は、Ding,  C.H.Q他による「A  Min-max  Cut  Algorithm  for  Graph  Partitioning  and  Data  Clustering」  Proc.  Int’l  Conference  on  Data  Mining,  San  Jose,  CA,  pp.  107-114,  2001に記載されているものである。
【００４２】
n個の構成要素から成るデータ集合Dと、n×n個の結合行列（重み行列）Wとを前提とすれば、目標は、クラスタ間の類似性を最小にし、クラスタ内の類似性を最大にする最小・最大の原理を満たす、部分集合A及びBへのDの分割を見つけるというものである。2つのデータ構成要素u及びvの類似性すなわち結合は、行列要素wuvによって表す。部分集合Aと部分集合Bとの類似性は、
cut(A,B)＝W(A,B)                                                          (1)
のカットサイズであり、そのとき、
【００４３】
【数１】
2006179002.tif 000003
であり、W(A):=W(A,A)である。
【００４４】
次の目標は、cut(A,B)の最小化を、W(A)及びW(B)の最大化と同時に行うということである。一実施例では、このことは、
Mcut(A,B)=(cut(A,B)/W(A))+(cut(A,B)/W(B))                                  (2)
の目標関数によって達成される。行列Wを
【００４５】
【数２】
2006179002.tif 000004
の標準形で表すと仮定すれば、Wのフィードラ(Fiedler)・ベクトルを判定しなければならない。フィードラ・ベクトルは、2番目に大きな固有値（最大の固有値は１である。）に相当するWの2番目の固有ベクトルである。フィードラ・ベクトルをソートすることによって、有用な線形サーチ順序がもたらされる。
【００４６】
ソートされたフィードラ・ベクトルが表す順序に従って、式(2)のMcut関数を計算する。一実施例では、最低のMcut値は、最適なカット点に相当する。
【００４７】
このカット点の精緻化は、例えば、Ding,  C.H.Q他による「A  Min-max  Cut  Algorithm  for  Graph  Partitioning  and  Data  Clustering」Proc.  Int’l  Conference  on  Data  Mining,  San  Jose,  CA,  pp.  107-114,  2001に記載されている精緻化手法などのリンケージ・ベースの精緻化手法によって行い得る。この手法は、カットを局所的に改善し得るよう、計算されたカット点に近い点を検査するものである。
【００４８】
一実施例では、MMCアルゴリズムが階層的に文書収集物に、幾何学的な特徴及び論理的な特徴を用いて施される。一実施例では、階層クラスタ化アルゴリズムにおける各工程で、クラスタ内部での類似性が最も小さいクラスタが識別される。そのクラスタは更に、２つの新たなクラスタに、1度は幾何学的な特徴を用い、1度は論理的な特徴を用いて、2度分割される。分割は評価され、より「好適な」分割、すなわち、類似性が最も大きな新たなクラスタを生成する分割、が選ばれる。クラスタ化アルゴリズムにおいて測定される類似性は、別々の特徴集合からの類似性測定が比較できるように、正規化特徴について測定される。そのような正規化を行う1つの方法は、特徴空間の部分空間上に投影されるデータが、確率密度分布を備えている確率変数の実現形態である、すなわち、当該データが経験確率密度関数(pdf)として解釈するというものである、確率変数Xは、周知の公式
(X−E(X)/STD(X)によって正規化できる。そのような正規化を行った後、特徴空間Fdir
の特定の部分空間に関する最善の分離が、
【００４９】
【数３】
2006179002.tif 000005
の2つの集合によって表す最適なカット点で式(2)の関数Mcutによって測定される。
【００５０】
特徴空間の部分空間全てから得る、分割クラスタの選択は、
【００５１】
【数４】
2006179002.tif 000006
として計算できる。
【００５２】
以下の擬似コードは、階層的な幾何・論理クラスタ化の一実施例の詳細を含んでいる。
【００５３】
【数５】
2006179002.tif 000007
（アイコン木-クラスタ表現としてのアイコン）
クラスタ化によって、概要レベルの文書情報を表す卓越した視覚化可能な特徴によってラベリングできるグループに文書収集物を分割した後、その特徴を次に、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は、テキストの部分分類として題名を表す。当該集合例の特徴空間は、以下の表１に示す。
【００６１】
【表１】
2006179002.tif 000008
最後のクラスタ階層は深度が最大4レベルまであり、2列・テキストのみ・題名付きの文書、2列・テキストのみ・題名なしの文書、2列・混合コンテンツの文書、３列・テキストのみの文書、3列・混合コンテンツ及び2列でも3列でもない文書を含む部分収集物に文書収集物を分割する。
【００６２】
（表示サイズ制約に合わせるための、アイコン木の枝刈り）
アイコン木の、葉ノードは、文書群の視覚化として用いる。特定の利用可能な表示領域を前提にすれば、葉ノードのアイコン全てをそれらの元のサイズで表示することが可能でない場合がある。アイコン木を下部から上部まで枝刈りすることによって、葉ノードの数は減少するものであり、アイコン・サイズは減少し得る。一実施例では、アイコン木は、葉ノード・アイコン集合が、利用可能な表示領域に収まるまで枝刈りされる。表示領域が大きい場合、表示領域が小さい場合と比べて、行う枝狩りは少なくなければならない。図７（Ａ）乃至図７（Ｅ）は、葉ノードと、木の枝刈りを行った後の残りの葉ノードとを、３つの別々の表示領域について示す。図７（Ａ）は、葉ノード付きクラスタ木の例である。
【００６３】
クラスタ数、表示画面のサイズ、及び文書収集物のコンテンツは、視覚化に影響を及ぼす。表示サイズが変わると、視覚化も変わるはずである。同じことが、文書収集物コンテンツに対する変更の場合もあてはまる。これらの依存関係によって、入力条件における変化は各々、アイコン視覚化を変え得る。したがって、アイコン視覚化は、動的なもの、すなわち、動的な文書アイコンである。
【００６４】
図10は、図７（Ａ）において作成される葉クラスタに対する動的な文書アイコンと、個々のページのレイアウトの情報を表す動的な文書アイコンの例とを示す。図７（Ｂ）は、木のノード毎にアイコン表現を備えている、図７（Ａ）のクラスタ木を示す。
【００６５】
図７（Ｃ）は、モニタ表示上で表示可能な、図７（Ｂ）のクラスタ木の一部分を（太字で）示す。図７（Ｄ）は、PDA表示上で表示可能な、図７（Ｂ）のクラスタ木の一部分を（太字で）示す。図７（Ｅ）は、携帯電話表示上で表示可能な、図７（Ｂ）のクラスタ木の一部分を（太字で）示す。一実施例では、クラスタ木は木データ構造表現を用いて実施される。
【００６６】
（例示的な木の枝刈り）
木の枝刈りは、種々の方法で行い得る。以下に、3つの方法を詳細に説明する。実施形態において選ぶ枝刈り手法は、アプリケーションやユーザ選好によって変わってくる場合がある。
【００６７】
vkはアイコン木におけるノード全てを表すものとする。ノード
【００６８】
【数６】
2006179002.tif 000009
で、
【００６９】
【数７】
2006179002.tif 000010
が葉ノードであり、かつ、
【００７０】
【数８】
2006179002.tif 000011
の親の子全ても葉ノードであるようなもの全てを見つけることとする。この集合は、葉ノード集合と呼ばれ、
【００７１】
【数９】
2006179002.tif 000012
によって表す。葉ノード集合の親ノードの集合は、
【００７２】
【数１０】
2006179002.tif 000013
によって表す。
【００７３】
枝刈りは、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=葉ノード集合）であると仮定すれば、システムは、アイコンが表示領域に収まるか否かを、単純な線形的な水平パッキング順序
【００８１】
【数１１】
2006179002.tif 000014
に従って検査し、そのとき、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に進む。
【００９４】
図14は、クラスタ化と枝刈りとの組み合わせを含む処理の一実施例の流れ図である。当該処理は、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータ上や専用マシン上で実行されるものなどの）ソフトウェア、又は両方の組み合わせを備え得る処理ロジックによって行われることが好ましい。図14を参照すれば、処理ロジックは、文書を木にクラスタ化し、レイアウト機能を用いてアイコンを利用可能な表示空間に収めるということの利用可能性を検査することによって閉葉ノードを識別する（処理ブロック1401）。このことは、文書収集物や、表示の制約（例えば、表示コントラストや表示領域サイズ）を受け取ることに応じて行われる。次に、処理ロジックは、枝刈りされた木の、葉ノードでのアイコンを表示する（処理ブロック1402）。
【００９５】
図8は、アイコンをクラスタ表現として自動的に作成する処理の一実施例の流れ図である。処理は、ハードウェア（例えば、回路、専用ロジックなど）、（汎用コンピュータ上や専用マシン上で実行されるものなどの）ソフトウェア、又は両方の組み合わせを備え得る処理ロジックによって行われる。
【００９６】
図8を参照すれば、当該処理は、処理ロジックがクラスタ分割の方向を余儀なくした特徴を受信することによって開始する（処理ブロック801）。それに対する応答として、処理ロジックは、特徴対幾何変換を行う（処理ブロック802）。変換の結果は、1つ又は複数の幾何学的な命令803である。例えば、幾何学的な命令は、システムに、矩形（形状、位置）を描写し、特定のベタ塗りの灰色の値によって矩形を塗りつぶし、画像をクロッピングし、画像を矩形に収めることを命じ得る。
【００９７】
処理ロジックは更に、幾何学的な命令の実行の画像出力の最小サイズ（805）（例えば、塗りつぶされている矩形は特定の最小寸法を有する。）を判定するために最小サイズの判定（処理ブロック804）を行う。
【００９８】
画像出力805の最小サイズを用いて、処理ロジックは、親ノードの命令リストに、幾何学的な命令と、関連した最小サイズとを追加し（処理ブロック806）、更新命令リスト(808)を生成するうえでの、画像出力の最小サイズを満たすよう、リストにおける幾何学的な命令を修正（例えば、スケーリング）する（処理ブロック807）。処理ロジックは、アイコン作成器を用いて動的な文書アイコン810を作成して、更新命令リスト808における命令を実行する（処理ブロック809）。
【００９９】
よって、一実施例では、システムは、表示特性がアイコン作成と木枝刈りに影響を及ぼす、クラスタ化ツール、アイコン作成ツール及び木枝刈りツールを備える。そのようなシステムの概略を図9に示す。
【０１００】
（例示的なアプリケーション）
動的な文書アイコンの用法として考えられるものの１つとして、動的な文書アイコンをテキスト結果に加えて、個々のページのレイアウトの情報の視覚化及び/又は、動的な文書アイコンの、クラスタ・ラベル又は「フォルダ記号」としての表示を行うというものである。図11は、左にある動的な文書アイコン1101と上にある動的な文書アイコン1102とを以下のように用いてPDAに似た表示上に表示される、そのような検索結果例を示す。
【０１０１】
まず、フォルダ記号としての動的な文書アイコンの場合、考えられる利用シナリオとしては、選ばれた動的な文書アイコン・クラスタに含まれる、文書の検索結果を示す新たな表示が、その文書アイコン上をクリックすることによって作成されるようにフォルダ記号にリンケージ構造を追加するというものである。この用法は、図６（Ａ）の2列・テキストのみ文書と図６（Ｂ）の3列・混合コンテンツとについて表す。なお、図６（Ａ）のシナリオでは、論理的な特徴の階層レベルがもう１つ、テキスト及び題名を含む文書と、テキストのみを含み、題名を含まない文書とに対する動的な文書アイコンを示すことによって追加されている。図６（Ｂ）のシナリオでは、テキスト結果は、文書で利用可能なものとして存在していないが、それは、英語ではなく、ドイツ語及びフィンランド語で書かれているからである。文書が画像ゾーンを含む場合、動的な文書アイコンは、アイコン中の適切な場所に元の画像コンテンツの低解像度のバージョンを示す。
【０１０２】
他の、動的な文書アイコンのアプリケーションとしては、サーチ及びブラウジングがある。サーチは、題名などの、ある特定の情報を前提とすれば、特定の文書について狭く定義される。一方、ブラウジングは、十分に定義された目標はないが、文書収集物について更に知る必要性を満たす。これらの定義を用いれば、動的な文書アイコンは一般的に、サーチ作業よりもブラウジング作業を好適にサポートし得る。
【０１０３】
（アルゴリズム的に制御される知覚可能な情報）
本明細書及び特許請求の範囲記載の視覚化手法は、文書収集物のコンテンツと、視覚化の幾何学的な特性とを組み入れ、ユーザが結果を知覚する可能性と、表示装置が施す制約とをこれらの要素にリンクする。この概念は以下に更に詳細に説明する。従来技術では、画像領域などの一方向表示特性は、最初のページ上の検索結果に対して固定の数を設定することによって考慮される。例えば、グーグルは、最初のウェブページ上に10個の結果を示す。ブラウザ・ウィンドウのサイズによって、ユーザは、10個の結果の全ての情報を認識しない場合がある一方、10個の結果全ての情報を受けるのにスクロールすることを要し得る。
【０１０４】
入力パラメータと、出力媒体としての画像とを前提とすれば、検索視覚化アルゴリズムの目標は、検索データを計算し、視覚化し、そのデータに含まれる情報をユーザが認識し得るようにするというものでなければならない。この目標を達成するよう、情報が種々の方法で判定又は測定される。一方で、情報は、サーチ、クラスタ化、レイアウト作成などの作業に用いるアルゴリズム内で測定する必要がある。この情報は、アルゴリズム的に測定される検索情報と呼ばれる。他方で、最終的な視覚化画像を通じてユーザが認識する情報を判定しなければならない。この情報は、知覚可能な情報と呼ばれる（例としては、読みやすさ、認識可能性、区別可能性を含み得る。）。アルゴリズム的に測定される検索情報を知覚可能な情報にマッピングするために、スマートネールなどの視覚化ツール（「Resolution  Sensitive  Layout  of  Document  Regions」と題する（西暦2003年5月9日付出願、西暦2004年7月29日付公開（公開番号第2004/0145593号）の米国特許出願第10/435,000号参照。）と、動的な文書アイコンが用いられる。これらは、視覚化ツールと呼ばれる。アルゴリズム的に測定される検索情報と知覚可能な情報とのマッピングを含む、入力、出力及び検索のアルゴリズムと、視覚化ツールとに分割することの概略を図12に示す。
【０１０５】
技術的なレベルでは、アルゴリズム的に測定される検索情報と、知覚可能な情報とに分割することは、文書検索結果の視覚化における知覚可能な情報を判定し、測定する方法という中心的な問題につながる（特に難しいのは、文書収集物についての情報を測定するという例である。）。この情報についての測定があると、知覚可能な情報とアルゴリズム的に抽出される検索情報との間のマッピングを定義しなければならない。これによって、知覚可能な情報のアルゴリズム的な制御が可能になる。よって、図12に示す概念は、アルゴリズム的に制御される知覚可能な情報と呼ばれる。
【０１０６】
伝統的なサムネールやデンドログラムなどの伝統的な視覚化は、検索情報と知覚可能な情報との間のマッピングが設定も制御もされておらず、表示特性が入力として欠落している場合としてこの概念に適合する。
【０１０７】
（例示的なコンピュータ・システム）
図13は、本明細書及び特許請求の範囲記載の1つ又は複数の手順を行い得る例示的なコンピュータ・システムの構成図である。図13を参照すれば、コンピュータ・システム1300は、例示的なクライアント・サーバ・コンピュータ・システムを備え得る。コンピュータ・システム1300は、情報を伝達する通信機構すなわちバス1311と、バス1311に結合されて情報を処理するプロセッサ1312とを備える。プロセッサ1312は、例えば、ペンティウム（商標）、パワーＰＣ（商標）、アルファ（商標）などのマイクロプロセッサを含むが、それらなどのマイクロプロセッサに限定されるものでない。
【０１０８】
システム1300は、バス1311に結合されて、情報及び、プロセッサ1312が実行する対象の命令を記憶するランダム・アクセス・メモリ（ＲＡＭ）や他の（主メモリとして呼ばれる）動的な記憶装置1304を更に備える。主メモリ1304は、プロセッサ1312が命令を実行する間に一時変数や他の中間的情報を記憶するのにも用い得る。
【０１０９】
コンピュータ・システム1300は更に、バス1311に結合されて、静的情報とプロセッサ1312用命令とを記憶する読み取り専用メモリ（ＲＯＭ）及び/又は他の静的な記憶装置1306と、磁気ディスク又は光ディスク、及び対応ディスク・ドライブなどのデータ記憶装置1307とを備える。データ記憶装置1307は、バス1311に結合されて、情報及び命令を記憶する。
【０１１０】
コンピュータ・システム1300は、バス1311に結合されて、情報をコンピュータ・ユーザに向けて表示する、陰極線管（ＣＲＴ）表示又は液晶表示（ＬＣＤ）などの表示装置1321に更に結合されてもよい。英数字キーや他のキーを含む英数字入力装置1322も、バス1311に結合されて、情報及びコマンドの選択をプロセッサ1312に伝達し得る。別のユーザ入力装置としては、バス1311に結合されて、方向情報及びコマンド選択をプロセッサ1312に伝達し、表示1321上のカーソルの動きを制御する、マウス、トラックボール、トラックパッド、スタイラスや、カーソル方向キーなどのカーソル制御部1323がある。
【０１１１】
バス1311に結合し得る別の装置としては、紙、フィルムや他の同様な種類の媒体などの媒体に命令、データや他の情報を印刷するのに用い得るハードコピー装置1324がある。更に、スピーカ及び/又はマイクロフォンなどの音響記憶及び再生装置を任意的に、バス1311に結合して、コンピュータ・システム1300とのオーディオ・インタフェースを行い得る。バス1311に結合し得る別の装置としては、電話機やハンドヘルド型パーム機器に通信する無線/有線通信機構1325がある。
【０１１２】
なお、システム1300と、関連したハードウェアとの何れか又は全部の構成部分を本発明において用い得る。しかし、他のコンピュータ・システム構成が当該装置の一部又は全部を含み得るということは分かり得るものである。
【０１１３】
本発明の多くの改変及び修正は、当業者が上記記載を検討した後に明らかになることは疑いないものである一方、例証の目的で示し、説明した特定の実施例は何れも、限定的なものとみなすことを意図しているものでは何らないこととする。したがって、種々の実施例の詳細への言及は、本発明に必須とみなされる特徴のみをそれ自体が列挙するその本願請求項の範囲を限定することを意図するものでない。
【図面の簡単な説明】
【０１１４】
【図１】新たなアイコン視覚化を用いた、画像の視覚文書レイアウト特徴の記述例を示す図である。
【図２】幾何学的な特徴と論理的な特徴とに分けたレイアウト解析特徴の階層構造の一実施例を示す図である。
【図３】表示に適応した視覚化システムを、文書レイアウト特徴について表す概略図である。
【図４】分割手順の一実施例の概要を示す図である。
【図５】（Ａ）はアイコン表現の例を示す図、（Ｂ）はアイコン表現の例を示す別の図、（Ｃ）〜（Ｈ）はアイコン表現の例を示す更に別の図である。
【図６】（Ａ）は2列の、テキストのみの文書の用法を説明する図で、（Ｂ）は3列の混合文書の用法を説明する図である。
【図７】（Ａ）は葉ノードを備えているクラスタ木の例を示す図、（Ｂ）は木のノード毎にアイコン表現を備えている、（Ａ）のクラスタ木を示す図、（Ｃ）はモニタ表示上に表示可能な、（Ｂ）のクラスタ木の一部分を示す図、（Ｄ）はPDA表示上に表示可能な、（Ｂ）のクラスタ木の一部分を示す図、（Ｅ）は携帯電話表示上に表示可能な、（Ｂ）のクラスタ木の一部分を示す図である。
【図８】アイコンをクラスタ表現として自動的に作成する手順の一実施例を示す流れ図である。
【図９】そのようなシステムの概略を示す図である。
【図１０】図７（Ａ）の、作成された葉クラスタに対する文書アイコンと、個々のページのレイアウトの情報を表すダイドコン(dydocons)の例とを示す図である。
【図１１】PDAに似た表示上に表示される検索結果のそのような例を示す図である。
【図１２】アルゴリズム的に測定される検索情報と、知覚可能な情報とのマッピングを含めた、入力、出力、検索アルゴリズム及び視覚化ツールへの分離の概略を示す図である。
【図１３】本明細書及び特許請求の範囲記載の１つ又は複数の処理を行い得る例示的なコンピュータ・システムの構成図である。
【図１４】クラスタ化と枝刈りとの組み合わせを表す流れ図である。
【符号の説明】
【０１１５】
301  クラスタ化
302  アイコン作成
303  木枝刈り
310  文書収集物
320  表示装置特性
330  アイコン
1101  動的な文書アイコン 
1102  動的な文書アイコン
1300  コンピュータ・システム
1304  主メモリ
1306  静的なメモリ
1307  大容量メモリ
1311  バス
1312  プロセッサ
1321  表示
1322  キーボード
1323  カーソル制御装置
1324  ハードコピー装置
1325  無線/電話インタフェース
【図１】
2006179002.tif 000015
【図２】
2006179002.tif 000016
【図３】
2006179002.tif 000017
【図４】
2006179002.tif 000018
【図５】
2006179002.tif 000019
【図６】
2006179002.tif 000020
【図７】
2006179002.tif 000021
【図８】
2006179002.tif 000022
【図９】
2006179002.tif 000023
【図１０】
2006179002.tif 000024
【図１１】
2006179002.tif 000025
【図１２】
2006179002.tif 000026
【図１３】
2006179002.tif 000027
【図１４】
2006179002.tif 000028