(57)【要約】【課題】画像検索結果を示すための表示スペースを有効利用する。【解決手段】本発明は、（ａ）複数の画像を１つ以上の同値類へカテゴリ化し、（ｂ）１つ以上の同値類の各々について代表画像を選択し、（ｃ）第１の複数のクラスタを生成するために、１つ以上の代表画像の各々についてｋ平均アルゴリズムを適用し、（ｄ）所定の第１判定基準が満たされるまで（ｃ）を繰り返し、（ｅ）第２の複数のクラスタを生成するために、１つ以上の同値類における画像の各々についてｋ平均アルゴリズムを適用し、（ｆ）所定の第２判定基準が満たされるまで（ｄ）を繰り返す。【選択図】図１
2007128523.tif 000002
【特許請求の範囲】
【請求項１】
ランク付けされた複数の画像を表示装置に表示することができるように要約する方法であって、
（ａ）前記複数の画像を１つ以上の同値類へカテゴリ化し、
（ｂ）１つ以上の同値類の各々について代表画像を選択し、
（ｃ）第１の複数のクラスタを生成するために、１つ以上の代表画像の各々についてｋ平均アルゴリズムを適用し、
（ｄ）所定の第１判定基準が満たされるまで（ｃ）を繰り返し、
（ｅ）第２の複数のクラスタを生成するために、１つ以上の同値類における画像の各々についてｋ平均アルゴリズムを適用し、
（ｆ）所定の第２判定基準が満たされるまで（ｄ）を繰り返す、
画像要約方法。
【請求項２】
（ｂ）において、前記代表画像は、ランク付けおよび同値類の重心の少なくとも一方である判定基準にもとづいて選択される、請求項１に記載の画像要約方法。
【請求項３】
前記ｋ平均アルゴリズムを適用することはさらに、
（ｇ）複数の代表画像を複数のクラスタの１つへ割り当て、
（ｈ）複数のクラスタの各々の重心を求め、
（ｉ）複数の代表画像を最も近い重心を有するクラスタへ割り当て、
（ｊ）所定の第３判定基準が満たされるまで（ｈ）および（ｉ）を繰り返す、
ことを含む、請求項１に記載の画像要約方法。
【請求項４】
画像のｋツリーを表示することをさらに含む、請求項１に記載の画像要約方法。
【請求項５】
（ａ）において、１つ以上のメタデータのラベルを利用してクラスタにわたって画像をカテゴリ化する、請求項１に記載の画像要約方法。
【請求項６】
前記メタデータのラベルの類似性解析にもとづいて画像をカテゴリ化する、請求項５に記載の画像要約方法。
【請求項７】
言語解析にもとづいて画像をカテゴリ化する、請求項５に記載の画像要約方法。
【請求項８】
前記第１および第２の判定基準は、何れのクラスタもｋ個を超える画像を包含していないことである、請求項１に記載の画像要約方法。
【請求項９】
（ｄ）において、クラスタの重心は、該クラスタへ割り当てられた代表画像における１つ以上の低レベルの特徴にもとづいて決定され、
低レベルの特徴は、白黒であるかカラーであるか、色ヒストグラム、ファイルサイズ、画像サイズ、名前、ファイルの種類およびユニフォームリソースロケーターの少なくとも１つから選択される、請求項１に記載の画像要約方法。
【請求項１０】
代表カラー画像を包含しているクラスタの重心は、相対ユークリッド距離にもとづいており、
代表画像の色ヒストグラムは、ユークリッド距離を決定するためにユークリッド空間へ組み込まれる、
請求項９に記載の画像要約方法。
【請求項１１】
クラスタの重心は、低レベルの特徴の類似性解析にもとづいて決定される、請求項９に記載の画像要約方法。
【請求項１２】
インタラクティブに、画像にアクセスすることができる、請求項４に記載の画像要約方法。
【請求項１３】
ステンドグラスコラージュ技術を利用して画像を表示する、請求項４に記載の画像要約方法。
【請求項１４】
ステンドグラスコラージュは、ｋツリーの横幅を表示する、請求項１３に記載の画像要約方法。
【請求項１５】
同値類における２つ以上の画像の関係が、境界の種類、境界の色および境界の厚さの少なくとも１つである属性を利用して表示される、請求項１３に記載の画像要約方法。
【請求項１６】
画像のｋツリーの深度に、ステンドグラスコラージュにおける展開アイコンを通してアクセスすることができる、請求項１３に記載の画像要約方法。
【請求項１７】
前記第３判定基準は、収束条件および停止条件の少なくとも一方である、請求項３に記載の画像要約方法。
【請求項１８】
ランク付けされた複数の画像を表示する装置であって、
（ａ）前記複数の画像を１つ以上の同値類へカテゴリ化する手段と、
（ｂ）複数の同値類の各々について代表画像を選択する手段と、
（ｃ）第１の複数のクラスタを生成するために、各々の同値類の代表画像の各々にｋ平均アルゴリズムを適用する手段と、
（ｄ）所定の判定基準が満たされるまで（ｃ）を繰り返す手段と、
（ｅ）第２の複数のクラスタを生成するために、各々の同値類における画像の各々にｋ平均アルゴリズムを適用する手段と、
（ｆ）所定の判定基準が満たされるまで（ｅ）を繰り返す手段と、
（ｇ）画像のｋツリーを表示する手段と、
を備える画像表示装置。
【請求項１９】
ランク付けされた複数の画像から画像のｋツリーを表示するシステムであって、
該システムのｋツリーを表示する装置が、
（ａ）パラメータの１つ以上のセットを指定することができ、該パラメータの１つ以上のセットをソースコードへ編入することができ、該ソースコードを画像のｋツリーを表示するための一連のタスクへコンパイルすることができる、１つ以上のプロセッサと、
（ｂ）１つ以上のプロセッサによって処理されると、パラメータの１つ以上のセットを指定し、パラメータの１つ以上のセットをソースコードへ編入し、該ソースコードを画像のｋツリーを表示するための一連のタスクへコンパイルする、ことをシステムに行わせるオペレーションを記憶している機械可読媒体と、
を備える、
ｋツリー表示システム。
【請求項２０】
ランク付けされた複数の画像から画像のｋツリーを表示する処理をシステムに実行させるプログラムであって、該処理が、
（ａ）複数の画像を複数の同値類へカテゴリ化するステップと、
（ｂ）複数の同値類の各々について代表画像を選択するステップと、
（ｃ）第１の複数のクラスタを生成するために各々の同値類の代表画像の各々にｋ平均アルゴリズムを適用するステップと、
（ｄ）所定の判定基準が満たされるまでステップ（ｃ）を繰り返すステップと、
（ｅ）第２の複数クラスタを生成するために各々の同値類における画像の各々にｋ平均アルゴリズムを適用するステップと、
（ｆ）所定の判定基準が満たされるまでステップ（ｅ）を繰り返すステップと、
（ｇ）画像のｋツリーを表示するステップと、
を含む、
ｋツリー表示プログラム。
【請求項２１】
ランク付けされた複数の画像のｋツリーを表示する方法であって、
（ａ）前記複数の画像を同値類へカテゴリ化し、
（ｂ）複数の同値類の各々について代表画像を選択し、
（ｃ）第１の複数のクラスタを生成するために各々の同値類の代表画像の各々にｋ平均アルゴリズムを適用し、
（ｄ）所定の判定基準が満たされるまで（ｃ）を繰り返し、
（ｅ）第２の複数のクラスタを生成するために各々の同値類における画像の各々にｋ平均アルゴリズムを適用し、
（ｆ）所定の判定基準が満たされるまで（ｅ）を繰り返し、
（ｇ）複数の画像のｋツリーを表示する、
ｋツリー表示方法。
【請求項２２】
ランク付けされた複数の画像から画像のｋツリーを表示する処理をシステムに実行させるプログラムであって、
該処理が、
（ａ）複数の画像を複数のクラスタへカテゴリ化するステップと、
（ｂ）複数の同値類の各々について代表画像を選択するステップと、
（ｃ）第１の複数のクラスタを生成するために各々の同値類の代表画像の各々にｋ平均アルゴリズムを適用するステップと、
（ｄ）所定の判定基準が満たされるまでステップ（ｃ）を繰り返すステップと、
（ｅ）第２の複数のクラスタを生成するために各々の同値類における画像の各々にｋ平均アルゴリズムを適用するステップと、
（ｆ）所定の判定基準が満たされるまでステップ（ｅ）を繰り返すステップと、
（ｇ）複数の画像のｋツリーを表示するステップと、
を含む、
ｋツリー表示プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ｋ平均アルゴリズムの利用によって画像検索結果を小さいモバイル機器に表示する、表示スペースの有効利用を行う方法に関するものである。詳細には、本発明は、ランク付けされた複数の画像を表示装置に表示することができるように要約する方法、ランク付けされた複数の画像を表示する装置、ランク付けされた複数の画像から画像のｋツリーを表示するシステム、ランク付けされた複数の画像から画像のｋツリーを表示する処理をシステムに実行させるプログラム、および、ランク付けされた複数の画像のｋツリーを表示する方法に関する。
【背景技術】
【０００２】
データクラスタリングアルゴリズムは、階層的なものであってもよく、あるいは区分的なものであってもよい。階層的アルゴリズムは、連続的なクラスタを、先に確立されたクラスタを利用することで見出すのに対して、区分的アルゴリズムは１つの試みにおいてすべてのクラスタを決定する。階層的アルゴリズムは、集塊性（ボトムアップ形）のものであってもよく、あるいは分割性（トップダウン形）のものであってもよい。集塊性アルゴリズムは、別個のクラスタとしての各々の要素から始まり、次いでそれらをより大きいクラスタへ連続的にまとめる。分割性アルゴリズムは、全体集合から始まり、次いでそれをより小さいクラスタへ連続的に分割するように進む。
「ウェブ画像検索エンジン」
グーグル（登録商標）（Ｇｏｏｇｌｅ：グーグル画像検索、非特許文献１）、グーグル（登録商標）ＰＤＡ（Ｇｏｏｇｌｅ  ＰＤＡ：グーグル画像検索、非特許文献２）およびＭＳＮ（登録商標）（ＭＳＮ検索、非特許文献３）のようなよく知られている検索エンジンによって画像検索が支援されている。その検索結果は一連のウェブページに与えられ、各々のページには一定数のサムネイルが表形式で示される。例えば、画像検索のための非特許文献２では検索により取得された画像が１ページ毎に３つ、リスト形式で表示される。デスクトップパーソナルコンピュータ（ＰＣ）の表示装置においては広大な空きスペースは問題にはならないが、携帯情報端末（ＰＤＡ）あるいは携帯電話の小さい表示装置において広大な空きスペースがあることは効率が悪い。非特許文献３によれば、画像をカラーあるいは白黒によって、かつサイズ（小、中、大）によって、組織化することができる。
【０００３】
クラスティ（登録商標）（Ｃｌｕｓｔｙ：クラスティ画像検索、非特許文献４）によれば、シンプルな画像特性（ファイルのサイズ、名前、種類およびユニフォームリソースロケーター（ＵＲＬ））を利用することで、画像検索およびクラスタ画像が支援されている。カテゴリラベルを有するツリーウィジェットは、マイクロソフトウィンドウズ（登録商標）（Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（登録商標））ファイルエクスプローラと類似しており、ユーザはクラスタを通してナビゲートすることができる。次にツリーウィジェットへ表示されるのは、サムネイル画像を示す大きいパネルである。しかしながら、ユーザは画像に関して（例えば、より類似した画像を取得するために所望の画像あるいはそのクラスタをクリックすることによって）、直接、ナビゲートすることはできない。
「画像検索ブラウジング」
マイクロソフト（登録商標）（Ｍｉｃｒｏｓｏｆｔ）リサーチの「モビピクチャ（ＭｏｂｉＰｉｃｔｕｒｅ）」は、画像の内部において自動検出された「関心領域」（ＲＯＩ）に対して特定のサイズの矩形サムネイルに、画像セットをトリミングする。これらのサムネイルは小さい表示装置に並べられる（非特許文献５を参照）。
【０００４】
マイクロソフト（登録商標）（Ｍｉｃｒｏｓｏｆｔ）リサーチは、ウェブにおいて画像をクラスタリングするいくつかの技術を開発した。非特許文献６は、画像、テキストおよびリンク解析を用いたクラスタリング方法を提案している。この取り組みの短所は、クラスタの数がユーザインターフェイスモジュールあるいはユーザによって特定することのできるパラメータではない、ということである。さらに、このプログラムは、クラスタリングを精緻なものにするために、ルーチンの最後で、低レベルの画像特徴を用いて、クラスタの内部でクラスタリングを実行する、後処理ステップを有する。ユーザインターフェイスにおいて、このプログラムは、クラスタを第１パネルの中で４画像サムネイルとして提示し、第２パネルの中で選択されたクラスタの画像を提示する。最後に、このプログラムは、画像間で直接ナビゲートするという問題を完全には解決しない。
【０００５】
非特許文献７は、類似性測定を繰り返して補強するために、ウェブページにおける画像の周囲のテキストとリンク解析とを利用している。さらに、非特許文献８は、検索エンジンによって戻された画像が同一の意味内容を有していることを開始点として仮定し、次いで画像を複数の領域へセグメント化するように続行し、そしてクラスタリングを促進するためにコード化言語をそれらに割り当てている。実際には、検索結果の意味内容は大きく異なるかもしれない。加えて、「マルチモデルの類似性伝搬」プログラムはクラスタリングの前に画像をカテゴリ化しない。
【０００６】
「アモーレ」によれば、ユーザは、テキスト特性と画像特性とをクラスタリングすることで、ウェブベース画像検索結果をインタラクティブに組織化することができる（非特許文献９を参照）。「アモーレ」によれば、テキスト特性と画像特性（色および構成）とにもとづいたクラスタが組織化される。ユーザは基本的な形状を表わしているテンプレートによってクラスタを選択することができる。
【０００７】
パロアルト研究センタ（ＰＡＲＣ）の「マルチモーダル画像ブラウザ」によれば、ユーザは画像特性およびテキスト特性を利用して検索質問から画像をインタラクティブにクラスタリングすることができ、また、ユーザはその結果を絞り込むとともにそれらの特性にもとづいて再びクラスタリングすることができる（非特許文献１０を参照）。
「映像要約アプリケーション」
「マンガ」は、映像から抽出されたキーフレームを利用するストーリーボードとしての単一映像を示す（非特許文献１１を参照）。これらのフレームは解析されて重要度スコアを割り当てられ、より重要なキーフレームはより大きくストーリーボードに表示される。ユーザは、掘り下げるためにキーフレームを右マウスボタンでクリックすることができる。しかしながら、「マンガ」における掘り下げはただ１つのレベルに制限される。さらに、この掘り下げ機能は、映像セグメントの内部かあるいはそのすぐ近傍かのいずれかにおけるキーフレームに制限される。
「情報視覚化および情報管理のアプリケーション」
グロッカー（登録商標）（Ｇｒｏｋｋｅｒ）ソフトウェア（グロッカー、非特許文献１２）によれば、クラスタおよびカテゴリを示す入れ子円とリーフノードで文書を示す矩形とを有する情報マップが生成される。画像は円の内側で矩形サムネイルとして示されている。このソフトウェアは、空きスペースのために、有効な割り付けをすることができない。
【０００８】
「コラージュマシン」によれば、ウェブページからコラージュが生成される。サイトが開始点としてランダムに選択され、また、時間が経てばコラージュは自動的に更新される（非特許文献１３を参照）。「コラージュマシン」は画像を取得するためにリンクに沿って進む。「コラージュマシン」で表示される画像はトリミングされることがなく、また、重なることができる。
【０００９】
サムネイルトリミングは、スー（Ｓｕｈ）らおよびワン（Ｗａｎｇ）らによって開示されている（非特許文献１４および非特許文献５）。ｋツリーを生成するために利用される方法は、ウェブページにおいて要素をフォーマットするための機構であって、カスケードスタイルシートＷ３Ｃと称される機構に似ている（非特許文献１５）。関連したアプリケーションでは、ＦＸＰＡＬの「ステンドグラス」コラージュと称されている、映像からコラージュを自動的に生成する一般的なフレームワークが開示されている（米国特許出願第１０／８１５，３８９号および米国特許出願第１０／８１５，３５４号）。さらに、「ステンドグラス」コラージュ技術を利用して画像をコラージュにすることができる（米国特許出願第１０／９４８，７３０号および米国特許出願第１０／９４８，８２３号）。
【非特許文献１】[online]、[２００５年１０月１２日検索]、インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｉｍａｇｅｓ．ｇｏｏｇｌｅ．ｃｏｍ＞
【非特許文献２】[online]、[２００５年１０月１２日検索]、インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｇｏｏｇｌｅ．ｃｏｍ／ｐｄａ＞
【非特許文献３】[online]、[２００５年１０月１２日検索]、インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｓｅａｒｃｈ．ｍｓｎ．ｃｏｍ＞
【非特許文献４】[online]、[２００５年１０月１２日検索]、インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｃｌｕｓｔｙ．ｃｏｍ＞
【非特許文献５】ワンら(Wang, et al.)、「モビピクチャモバイル機器におけるピクチャブラウジング（ＭｏｂｉＰｉｃｔｕｒｅ  −  Ｂｒｏｗｓｉｎｇ  Ｐｉｃｔｕｒｅｓ  ｏｎ  Ｍｏｂｉｌｅ  Ｄｅｖｉｃｅｓ）」、ＡＣＭマルチメディア２００４年デモ（ＡＣＭ  Ｍｕｌｔｉｍｅｄｉａ  ’０４  Ｄｅｍｏ）、２００３年
【非特許文献６】カイら(Cai, et al.)、「画像、テキストおよびリンク解析を用いたＷＷＷ画像検索結果の階層的クラスタリング（Ｈｉｅｒａｒｃｈｉｃａｌ  ｃｌｕｓｔｅｒｉｎｇ  ｏｆ  ＷＷＷ  ｉｍａｇｅ  ｓｅａｒｃｈ  ｒｅｓｕｌｔｓ  ｕｓｉｎｇ  ｖｉｓｕａｌ，  ｔｅｘｔｕａｌ  ａｎｄ  ｌｉｎｋ  ａｎａｌｙｓｉｓ）」、ＡＣＭマルチメディア２００４年議事録（Ｐｒｏｃ．  ｏｆ  ＡＣＭ  Ｍｕｌｔｉｍｅｄｉａ  ’０４）、２００４年、頁９５２〜９５９
【非特許文献７】ワンら(Wang, et al.)、「ウェブ画像取得のためのマルチモデルの類似性伝搬およびそのアプリケーション（Ｍｕｌｔｉ−Ｍｏｄｅｌ  ｓｉｍｉｌａｒｉｔｙ  ｐｒｏｐａｇａｔｉｏｎ  ａｎｄ  ｉｔｓ  ａｐｐｌｉｃａｔｉｏｎ  ｆｏｒ  Ｗｅｂ  ｉｍａｇｅ  ｒｅｔｒｉｅｖａｌ）」、ＡＣＭマルチメディア２００４年議事録（Ｐｒｏｃ．  ｏｆ  ＡＣＭ  Ｍｕｌｔｉｍｅｄｉａ  ’０４）、２００４年、頁９４４〜９５１
【非特許文献８】ワンら(Wang, et al.)、「ウェブ画像検索結果のクラスタリング（Ｃｌｕｓｔｅｒｉｎｇ  Ｗｅｂ  ｉｍａｇｅ  ｓｅａｒｃｈ  ｒｅｓｕｌｔ）」、ＡＣＭマルチメディア２００４年ポスタープレゼンテーション（ＡＣＭ  Ｍｕｌｔｉｍｅｄｉａ  ’０４  Ｐｏｓｔｅｒ  ｐｒｅｓｅｎｔａｔｉｏｎ）、２００４年
【非特許文献９】ムクハージーら(Mukherjea, et al.)、「ＷＷＷ画像検索エンジンの結果を精緻なものにするためのクラスタリングおよび視覚化の利用（Using clustering and visualization for refining the results of a WWW image search engine）」、ＡＣＭプレス  情報の視覚化および操作の新しいパラダイムに関する１９９８年ワークショップ議事録（ＡＣＭ  Ｐｒｅｓｓ  Ｐｒｏｃ．  １９９８  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｎｅｗ  ｐａｒａｄｉｇｍｓ  ｉｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｖｉｓｕａｌｉｚａｔｉｏｎ  ａｎｄ  Ｍａｎｉｐｕｌａｔｉｏｎ）、１９９８年、頁２９〜３５
【非特許文献１０】チェンら(Chen, et al.)、「ウェブドキュメントにおける画像のマルチモーダルブラウジング（Ｍｕｌｔｉ−Ｍｏｄａｌ  ｂｒｏｗｓｉｎｇ  ｏｆ  ｉｍａｇｅｓ  ｉｎ  ｗｅｂ  ｄｏｃｕｍｅｎｔ）」、ＳＰＩＥ  ドキュメント認識および検索ＶＩ議事録（Ｐｒｏｃ．  ｏｆ  ＳＰＩＥ  Ｄｏｃｕｍｅｎｔ  Ｒｅｃｏｇｎｉｔｉｏｎ  ａｎｄ  Ｒｅｔｒｉｅｖａｌ  ＶＩ）、１９９９年
【非特許文献１１】ボレツキーら(Boreczky, et al.)、「映像を検討するためのインタラクティブコミックブックプレゼンテーション（Ａｎ  ｉｎｔｅｒａｃｔｉｖｅ  ｃｏｍｉｃ  ｂｏｏｋ  ｐｒｅｓｅｎｔａｔｉｏｎ  ｆｏｒ  ｅｘｐｌｏｒｉｎｇ  ｖｉｄｅｏ）」、ＡＣＭプレス  ２０００年ＣＨＩ議事録（ＡＣＭ  Ｐｒｅｓｓ  Ｐｒｏｃ．  ＣＨＩ  ’００）、２０００年、頁１８５〜１９２
【非特許文献１２】[online]、[２００５年１０月１２日検索]、インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｇｒｏｋｋｅｒ．ｃｏｍ＞
【非特許文献１３】カーン(Kerne)、「コラージュマシン：  インターフェイスエコログのモデル（ＣｏｌｌａｇｅＭａｃｈｉｎｅ  ：  Ａ  Ｍｏｄｅｌ  ｏｆ  Ｉｎｔｅｒｆａｃｅ  Ｅｃｏｌｏｇ）」、２００１年  ＮＹＵ  Ｐｈ．Ｄ．  学位論文(NYU Ph.D. Dissertation)、２００１年
【非特許文献１４】スーら(Suh, et al.)、「自動サムネイルトリミングおよびその有効性（Ａｕｔｏｍａｔｉｃ  ｔｈｕｍｂｎａｉｌ  ｃｒｏｐｐｉｎｇ  ａｎｄ  ｉｔｓ  ｅｆｆｅｃｔｉｖｅｎｅｓｓ）」、２００３年  ＵＩＳＴ議事録（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＵＩＳＴ  ’０３）、２００３年、頁９５〜１０４
【非特許文献１５】[online]、[２００５年１０月１２日検索]、インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｗ３．ｏｒｇ／Ｓｔｙｌｅ／ＣＳＳ＞
【非特許文献１６】[online]、[２００５年１０月１２日検索]、インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｗｏｒｄｎｅｔ．ｐｒｉｎｃｅｔｏｎ．ｅｄｕ＞
【非特許文献１７】イデら(Ide, et al.)、「言葉の意味の曖昧性除去についての特殊問題の紹介：技術分野の現状（Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  ｔｈｅ  ｓｐｅｃｉａｌ  ｉｓｓｕｅ  ｏｎ  ｗｏｒｄ  ｓｅｎｓｅ  ｄｉｓａｍｂｉｇｕａｔｉｏｎ：  ｔｈｅ  ｓｔａｔｅ  ｏｆ  ｔｈｅ  ａｒｔ）」、コンピュータによる言語学（Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｌｉｎｇｕｉｓｔｉｃｓ）、１９９８年、２４（１）、頁１〜４０
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上記技術に鑑みて、本発明は、画像検索結果を示すための表示スペースの有効利用を行うアルゴリズムを定義する。解決法は、概して、直感的なものであり、拡張可能なものであり、かつ、スペース効率の高いものである。
【課題を解決するための手段】
【００１１】
本発明の１つの実施形態では、各々のクラスタは、「ｋセットの画像」をそれらのＲＯＩへ凝縮して空きスペースのないコラージュを生成する「ステンドグラス」コラージュとして視覚化される。「ｋセットの画像」とは、一般的には正確にｋ個の要素を有するが例外的な場合にはｋ個の要素よりも少ない要素を有していてもよい、同一の親ノードからの子孫のセットである。本発明の１つの実施形態では、子孫のあるそれらの領域に、ユーザがｋツリーを下にたどるようにナビゲートする展開アイコンが備わっている。本発明の１つの実施形態では、検索ランク付け順序は、ｋセットの各々の内部に、および、親−子孫系統の各々によって保存され、そのランクは、各々の画像についてのトリミングの量と倍率とを制御するために利用することができる。本発明の１つの実施形態では、テキストのカテゴリ化および関連性の解析が、より良好なクラスタを生成するために利用される。
【００１２】
本発明の第１の態様は、ランク付けされた複数の画像を表示装置に表示することができるように要約する方法であって、（ａ）前記複数の画像を１つ以上の同値類(equivalence classes)へカテゴリ化し、（ｂ）１つ以上の同値類の各々について代表画像を選択し、（ｃ）第１の複数のクラスタを生成するために、１つ以上の代表画像の各々についてｋ平均アルゴリズムを適用し、（ｄ）所定の第１判定基準が満たされるまで（ｃ）を繰り返し、（ｅ）第２の複数のクラスタを生成するために、１つ以上の同値類における画像の各々についてｋ平均アルゴリズムを適用し、（ｆ）所定の第２判定基準が満たされるまで（ｄ）を繰り返す。
【００１３】
本発明の第２の態様は、第１の態様の画像要約方法であって、（ｂ）において、前記代表画像は、ランク付けおよび同値類の重心の少なくとも一方である判定基準にもとづいて選択される。
【００１４】
本発明の第３の態様は、第１の態様の画像要約方法であって、前記ｋ平均アルゴリズムを適用することはさらに、（ｇ）複数の代表画像を複数のクラスタの１つへ割り当て、（ｈ）複数のクラスタの各々の重心を求め、（ｉ）複数の代表画像を最も近い重心を有するクラスタへ割り当て、（ｊ）所定の第３判定基準が満たされるまで（ｈ）および（ｉ）を繰り返す、ことを含む。
【００１５】
本発明の第４の態様は、第１の態様の画像要約方法であって、画像のｋツリーを表示することをさらに含む。
【００１６】
本発明の第５の態様は、第１の態様の画像要約方法であって、（ａ）において、１つ以上のメタデータのラベルを利用してクラスタにわたって画像をカテゴリ化する。
【００１７】
本発明の第６の態様は、第５の態様の画像要約方法であって、前記メタデータのラベルの類似性解析にもとづいて画像をカテゴリ化する。
【００１８】
本発明の第７の態様は、第５の態様の画像要約方法であって、言語解析にもとづいて画像をカテゴリ化する。
【００１９】
本発明の第８の態様は、第１の態様の画像要約方法であって、前記第１および第２の判定基準は、何れのクラスタもｋ個を超える画像を包含していないことである。
【００２０】
本発明の第９の態様は、第１の態様の画像要約方法であって、（ｄ）において、クラスタの重心は、該クラスタへ割り当てられた代表画像における１つ以上の低レベルの特徴にもとづいて決定され、低レベルの特徴は、白黒であるかカラーであるか、色ヒストグラム、ファイルサイズ、画像サイズ、名前、ファイルの種類およびユニフォームリソースロケーターの少なくとも１つから選択される。
【００２１】
本発明の第１０の態様は、第９の態様の画像要約方法であって、代表カラー画像を包含しているクラスタの重心は、相対ユークリッド距離にもとづいており、代表画像の色ヒストグラムは、ユークリッド距離を決定するためにユークリッド空間へ組み込まれる。
【００２２】
本発明の第１１の態様は、第９の態様の画像要約方法であって、クラスタの重心は、低レベルの特徴の類似性解析にもとづいて決定される。
【００２３】
本発明の第１２の態様は、第４の態様の画像要約方法であって、インタラクティブに、画像にアクセスすることができる。
【００２４】
本発明の第１３の態様は、第４の態様の画像要約方法であって、ステンドグラスコラージュ技術を利用して画像を表示する。
【００２５】
本発明の第１４の態様は、第１３の態様の画像要約方法であって、ステンドグラスコラージュは、ｋツリーの横幅を表示する。
【００２６】
本発明の第１５の態様は、第１３の態様の画像要約方法であって、同値類における２つ以上の画像の関係が、境界の種類、境界の色および境界の厚さの少なくとも１つである属性を利用して表示される。
【００２７】
本発明の第１６の態様は、第１３の態様の画像要約方法であって、画像のｋツリーの深度に、ステンドグラスコラージュにおける展開アイコンを通してアクセスすることができる。
【００２８】
本発明の第１７の態様は、第３の態様の画像要約方法であって、前記第３判定基準は、収束条件および停止条件の少なくとも一方である。
【００２９】
本発明の第１８の態様は、ランク付けされた複数の画像を表示する装置であって、（ａ）前記複数の画像を１つ以上の同値類へカテゴリ化する手段と、（ｂ）複数の同値類の各々について代表画像を選択する手段と、（ｃ）第１の複数のクラスタを生成するために、各々の同値類の代表画像の各々にｋ平均アルゴリズムを適用する手段と、（ｄ）所定の判定基準が満たされるまで（ｃ）を繰り返す手段と、（ｅ）第２の複数のクラスタを生成するために、各々の同値類における画像の各々にｋ平均アルゴリズムを適用する手段と、（ｆ）所定の判定基準が満たされるまで（ｅ）を繰り返す手段と、（ｇ）画像のｋツリーを表示する手段と、を備える。
【００３０】
本発明の第１９の態様は、ランク付けされた複数の画像から画像のｋツリーを表示するシステムであって、該システムのｋツリーを表示する装置が、（ａ）パラメータの１つ以上のセットを指定することができ、該パラメータの１つ以上のセットをソースコードへ編入することができ、該ソースコードを画像のｋツリーを表示するための一連のタスクへコンパイルすることができる、１つ以上のプロセッサと、（ｂ）１つ以上のプロセッサによって処理されると、パラメータの１つ以上のセットを指定し、パラメータの１つ以上のセットをソースコードへ編入し、該ソースコードを画像のｋツリーを表示するための一連のタスクへコンパイルする、ことをシステムに行わせるオペレーションを記憶している機械可読媒体と、を備える。
【００３１】
本発明の第２０の態様は、ランク付けされた複数の画像から画像のｋツリーを表示する処理をシステムに実行させるプログラムであって、該処理が、（ａ）複数の画像を複数の同値類へカテゴリ化するステップと、（ｂ）複数の同値類の各々について代表画像を選択するステップと、（ｃ）第１の複数のクラスタを生成するために各々の同値類の代表画像の各々にｋ平均アルゴリズムを適用するステップと、（ｄ）所定の判定基準が満たされるまでステップ（ｃ）を繰り返すステップと、（ｅ）第２の複数クラスタを生成するために各々の同値類における画像の各々にｋ平均アルゴリズムを適用するステップと、（ｆ）所定の判定基準が満たされるまでステップ（ｅ）を繰り返すステップと、（ｇ）画像のｋツリーを表示するステップと、を含む。
【００３２】
本発明の第２１の態様は、ランク付けされた複数の画像のｋツリーを表示する方法であって、（ａ）前記複数の画像を同値類へカテゴリ化し、（ｂ）複数の同値類の各々について代表画像を選択し、（ｃ）第１の複数のクラスタを生成するために各々の同値類の代表画像の各々にｋ平均アルゴリズムを適用し、（ｄ）所定の判定基準が満たされるまで（ｃ）を繰り返し、（ｅ）第２の複数のクラスタを生成するために各々の同値類における画像の各々にｋ平均アルゴリズムを適用し、（ｆ）所定の判定基準が満たされるまで（ｅ）を繰り返し、  （ｇ）複数の画像のｋツリーを表示する。
【００３３】
本発明の第２２の態様は、ランク付けされた複数の画像から画像のｋツリーを表示する処理をシステムに実行させるプログラムであって、該処理が、（ａ）複数の画像を複数のクラスタへカテゴリ化するステップと、（ｂ）複数の同値類の各々について代表画像を選択するステップと、（ｃ）第１の複数のクラスタを生成するために各々の同値類の代表画像の各々にｋ平均アルゴリズムを適用するステップと、（ｄ）所定の判定基準が満たされるまでステップ（ｃ）を繰り返すステップと、（ｅ）第２の複数のクラスタを生成するために各々の同値類における画像の各々にｋ平均アルゴリズムを適用するステップと、（ｆ）所定の判定基準が満たされるまでステップ（ｅ）を繰り返すステップと、（ｇ）複数の画像のｋツリーを表示するステップと、を含む。
【発明の効果】
【００３４】
本発明では、（ａ）複数の画像を１つ以上の同値類へカテゴリ化し、（ｂ）１つ以上の同値類の各々について代表画像を選択し、（ｃ）第１の複数のクラスタを生成するために、１つ以上の代表画像の各々についてｋ平均アルゴリズムを適用し、（ｄ）所定の第１判定基準が満たされるまで（ｃ）を繰り返し、（ｅ）第２の複数のクラスタを生成するために、１つ以上の同値類における画像の各々についてｋ平均アルゴリズムを適用し、（ｆ）所定の第２判定基準が満たされるまで（ｄ）を繰り返す、ようにしているので、画像検索結果を示すための表示スペースを有効利用することができる。
【発明を実施するための最良の形態】
【００３５】
本発明の好ましい実施形態を図面にもとづいて詳細に説明する。
【００３６】
検討中の画像検索結果について、各々の画像は、色あるいはテクスチャのような低レベルの画像特徴と、関連したテキストメタデータとを有する。画像はランク付けすることができる。「ランク付け」とは検索エンジンアルゴリズムの出力にもとづいた画像の順序付けである。「同値類」が、テキストの言語解析あるいは高レベルの特徴にもとづいて決定される、類似する特性を備えた複数の画像から生成される。「カテゴリ化」は、どの画像が同一の同値類に属するかを、ラベルあるいはキャプションのようなテキストメタデータ特徴の類似性解析にもとづいて決定することに対して、使用される。「代表画像」とは、最高ランクの画像にもとづいて同値類の画像から選択される画像であるか、あるいは、代わりに、同値類の重心に最も近い画像である。「同値類の重心」とは、同値類におけるすべての画像の特徴の類似性解析にもとづくものである。
【００３７】
「クラスタ」は、類似特性を備える複数のオブジェクトから生成される。本発明の１つの実施形態では、クラスタのオブジェクトが画像であるときには、「クラスタ」の類似特性は低レベルの画像特徴にもとづいて決定される。クラスタの複数の画像が同値類であるときには、類似特性は同値類の代表画像における低レベルの画像特徴にもとづいて決定される。クラスタに存在するオブジェクトの数が「ｋ」よりも大きいときには、オブジェクトの数が「ｋ」以下になるように、ｋ平均アルゴリズムをクラスタへ適用することができる。「クラスタの重心」は、クラスタにおけるオブジェクトの類似特性の解析にもとづくものである。
【００３８】
「ｋツリー」とは、各々のノードにｋ以下のオブジェクトが備わったツリーである。これらのオブジェクトは、画像であってもよくあるいは同値類であってもよい。ツリーの「ルート」とは、最上位のノードである。本発明の１つの実施形態では、ｋツリーはｋ平均アルゴリズムを繰り返して適用することによって取得される。ルートノードから始まり、ノードは「親」とみなすことができ、また、ｋ平均アルゴリズムの繰り返しの各々が、次世代の「子孫」ノードを生成する。「深度」とは、ルートまでの子孫世代の数を示す。
【００３９】
本発明によれば、ユーザはいつでもどこでも、携帯型表示装置において画像を検索することができるとともに取得された画像をその装置に表示することができる。本発明は、外国を訪れる旅行者が言葉の壁に直面したときに、言葉とは無関係に画像によってコミュニケーションを行うことができるので、特に有用である。例えば、コップ一杯の搾りたてのオレンジジュースが欲しい人は、図２に示されるように、単に、彼のＰＤＡあるいは携帯電話において「オレンジジュース」を検索して、レストランでウェイターへ搾りたてのオレンジジュースを伝える画像を示すことができる。別の実際の生活での例は、説明したりあるいはパントマイムで表わしたりすることが容易ではない「ハエたたき」である。日常的な状況においてこのような多くの状況を容易に想像することができる。
【００４０】
加えて、多くの分野における特定の用途も存在している。高度先端技術製造会社に関連する１つの例は、サービスエンジニアがある機器のサービスの分野に疎く、しかも交換部品についての情報を見付ける必要があるときである。画像検索結果へアクセスすることで、そのエンジニアは、壊れているアイテムをウェブに表示されたアイテムに容易に突き合わせることができる。
【００４１】
本発明の実施形態の装置は、（ａ）複数の画像を１つ以上の同値類へカテゴリ化する手段と、（ｂ）複数の同値類の各々について代表画像を選択する手段と、（ｃ）第１の複数のクラスタを生成するために、各々の同値類の代表画像の各々にｋ平均アルゴリズムを適用する手段と、（ｄ）所定の判定基準が満たされるまで（ｃ）を繰り返す手段と、（ｅ）第２の複数のクラスタを生成するために、各々の同値類における画像の各々にｋ平均アルゴリズムを適用する手段と、（ｆ）所定の判定基準が満たされるまで（ｅ）を繰り返す手段と、（ｇ）画像のｋツリーを表示する手段と、を備え、ランク付けされた複数の画像を表示する。
【００４２】
該装置は、例えば、携帯情報端末、携帯電話など携帯型デバイスであってよく、ユーザの指示情報、通信網からのデータを入力する入力部、プロセッサ、該プロセッサによる実行の際の作業領域を形成するとともにプログラムや処理対象としてのデータを格納する記憶部、処理内容や処理結果を表示画面上に表示する、携帯型デバイスに適したサイズの表示部、及び通信網などへデータを出力する出力部などを含む。プロセッサは、プログラム（ソフトウェア）を読み出し実行することにより、処理対象のデータ等に対し当該プログラムの手順に対応した処理を行う。上記（ａ）〜（ｇ）の手段は、プロセッサであってもよく、また、プロセッサとは別個の手段であって、プロセッサによって制御されてもよい。
【００４３】
本発明の１つの実施形態における方法は、ウェブからの画像セットのような画像の一般的なセットからの検索結果を取得しかつ表示することを目的としている。その検索結果は、非特許文献１、ＭＳＮ検索、などのような任意の画像検索エンジンによってもたらされたものであってもよい。これらの画像は相異なるサイズおよび縦横比を有している異なるものである。加えて、画像とともにテキストが見出されることが多く、あるいは代わりに、メタデータ、近接テキスト(nearby text)、近接性タグ(accessibility tags)（例えばＨＴＭＬ＜ａｌｔ＞タグ）などが存在していることもある。カテゴリ化および関連解析は、「ワードネット」あるいはＰＡＲＣの「ＸＬＥ」のような言語処理装置によって、テキストに対して行うことができる。
【００４４】
本発明の様々な実施形態では、画面スペースの有効利用、検索結果の組織化、および大きいセットへの拡張可能性のような付加的な問題に取り組んでいる。本発明の１つの実施形態における取り組みは、検索結果をｋツリーに組織化するとともに構成し、次いでこれを小さい表示装置において視覚化することである。図１には、本発明の１つの実施形態にしたがって複数の画像を要約するためのイベントフローチャートのブロック図が示されている。基本的に、ツリーの深度に沿って、ノードの子孫を折り畳み、それらを展開アイコンによって表示する。ツリーのノードの幅にしたがって、それらの画像を図３（Ａ）に示されるような「ステンドグラス」コラージュに凝縮する。図３（Ｂ）は複数の画像を示す。図３（Ａ）に示されたコラージュは該複数の画像から組み合わされた。
【００４５】
図１の処理は、ステップ１００で開始し、ランク付けされた画像のセットとテキストメタデータとをサーチエンジンから本発明の装置に入力する。ステップ１１０で、テキストメタデータを言語解析し、これにより、画像を同値類に区分する（（ａ）の手段）。ステップ１２０で、同値類の各々について、単一の代表画像を割り当てる（（ｂ）の手段）。ステップ１３０で、同値類の代表画像にｋ平均アルゴリズムを適用する（（ｃ）の手段）。
【００４６】
ステップ１４０で、各々のクラスタにおける同値類の数がｋを越えるか否か判断する。ｋを越える場合には、ステップ１５０に進み、ｋを越えるクラスタについて、ｋ平均アルゴリズムを適用する。ステップ１４０の判断においてｋを越えるクラスタがない場合、あるいは、ステップ１５０の処理によりｋを越えるクラスタがなくなった場合（（ｄ）の手段）、ステップ１６０に進み、同値類の各々の画像にｋ平均アルゴリズムを適用する（（ｅ）の手段）。
【００４７】
ステップ１７０で、各々のクラスタにおける画像の数がｋを越えるか否か判断する。ｋを越える場合、ステップ１８０に進み、ｋを越えるクラスタについて、ｋ平均アルゴリズムを適用する。ステップ１７０の判断においてｋを越えるクラスタがない場合、あるいは、ステップ１８０の処理によりｋを越えるクラスタがなくなった場合（（ｆ）の手段）、ステップ１９０に進み、ｋツリーを視覚化する。
「技術詳細」
「ｋ平均アルゴリズムを用いたｋツリーの演算」
本発明の１つの実施形態では、画像をクラスタリングするためにｋ平均アルゴリズムが利用される。本発明の１つの実施形態は、テキストあるいはメタデータの類似性スコアを考慮に入れることができるときにはマルチモーダルであってもよい。
【００４８】
本発明の１つの実施形態では、予備段階において、Ｎ個の画像をＭ＋１個の同値類へカテゴリ化するためにテキストあるいはメタデータの類似性スコアを利用する。いくつかの予め決定されているカテゴリ化あるいはオントロジーを仮定することはせず、２つのテキスト列についての類似性スコアを与えることができる機能を有しているということだけを仮定する。画像がそれらの間に高い類似性スコアを有しているときだけ、それらの画像を同一の同値類へカテゴリ化する。その結果は、図５に模式的に示されるように、ランク付けされた画像の一部をＭ＋１個の同値類へ形成する多数のセットである。各々の同値類から、その最高ランク画像を採用することによって代表画像を選択する。画像がランク付けされない本発明の１つの実施形態では、代わりに、同値類の重心に最も近い画像を代表画像に採用することができる。
【００４９】
ｋ平均アルゴリズムは、オブジェクトをユークリッド空間に組み込むことができるときには、より有効である。本発明の１つの実施形態では、画像は、Ｌ個のビンの色ヒストグラムをマッピングするＬ次元のユークリッド空間へ組み込まれている。すなわち、Ｌ個のビンの値はＬ個の座標のベクトルへマッピングされ、その距離はユークリッド距離である。実際、「距離が近い」ヒストグラムを有することは画像が類似していることを示すので、これは妥当な結果をもたらす。
【００５０】
本発明の１つの実施形態では、ｋ平均アルゴリズムは３つのステップ、すなわち、（１）初期化、（２）各々のクラスタについての重心の演算、（３）重心に最も近いことによるクラスタへの各々の代表画像の割り当て、を有している。本発明の１つの実施形態では、ステップ（２）および（３）は、それが収束する（すなわち、クラスタのメンバが１回以上の繰り返しで変化しなくなる）まで、あるいは停止条件（例えば、１，０００回のような繰り返しの数における制限）が満たされるまで、繰り返される。初期化は、オブジェクトをｋ個のクラスタの中へ任意に割り当てることによって実行することができ、より良好な方法は、階層的集塊性アルゴリズムを利用してオブジェクトをｋ個のクラスタへ入れることである。
【００５１】
本発明の１つの実施形態では、あるセットをｋ個のクラスタへクラスタリングする手順は、ｋツリーを取得するクラスタの連続的世代の各々において帰納的に適用される。このｋツリーにおける各々のノードには、リーフが含まれているノードを除いて、正確にｋ個の子孫があるであろうが、リーフが含まれているノードではｋ個の子孫よりも少ない。まず、ｋ平均クラスタリングが、１つ以上の同値類について、それらの代表画像の解析によって、事前ステップから実行される。各々の同値類について、正確に１つの代表画像が割り当てられる。この手順のこの部分は図６に示されており、ここで、三角形は同値類を表わしている。
【００５２】
本発明の１つの実施形態では、そのリーフノードがすべて画像であるツリーを生成するために、図７に示されるように、すべての同値類の内部でそれらの画像をクラスタリングするために、同一のｋ平均アルゴリズムが適用される。
「ランク付けされた画像のｋツリーの視覚化」
本発明の１つの実施形態では、表示装置は、その子孫ノードへのリンクおよびそれらの代表画像への直接リンクを有するｋツリーの単一ノードからの画像セットを示す。各々のノードについて、その子孫ノードの代表画像がステンドグラスコラージュへ生成される。これにより、小さい画面における効果的表示のために、配列されている不規則形状の領域へ画像を凝縮する。ステンドグラスコラージュおよび対応するオリジナル画像の一例は図３に示されている。
【００５３】
ステンドグラスコラージュは、よりシンプルな矩形レイアウトよりもフレキシブルである。最もシンプルなレイアウトは、画像を縮小してそれらを左から右へ一列に並べることである。しかしながら、これによれば、図３（Ｂ）に示されるように、それらの画像が相異なる縦横比を有しているかもしれず、その場合には多くのスペースを無駄にする。本発明の１つの実施形態では、画像の関心領域を矩形領域の中へ嵌め込むためにより洗練されたトリミング操作を採用することができ、また、これらのトリミングサムネイルは表示装置において格子状にレイアウトすることができる。
【００５４】
矩形格子状レイアウトの短所は、正確にｋ個の等サイズの矩形が常に画面の縦横比に合致するとは限らないスペース詰めモザイクであることである。例えば、一度に１０個の画像を示すことは好ましい。「上位１０個」のアイテムを示すこと、あるいはカウントを容易にするために一度に１０個のオブジェクトを示すことは、文化的な慣習である。携帯電話において、画像にアクセスするためにキーパッドにおける１０個の番号付きボタンを使用することができるように、１０個の画像を表示することは意味がある。しかしながら、均一な矩形サムネイルによれば、スペース詰め格子（１×１０および２×５）は標準的表示装置の縦横比に適切に合致しない。これに対して、ステンドグラスコラージュは、ほとんどの任意の縦横比を有する画面に正確に１０個の（あるいは任意の数の）画像を割り付けることができる。
【００５５】
本発明の１つの実施形態では、コラージュのある画像領域をクリックすると、その全体画像が示される。図２における画面ショットに示された画像は、図３（Ａ）における第２画像（すなわち、左上画像の隣の画像）における「＋」すなわち「プラスのオペレーターシンボル」アイコンを選択することから得られる画像の例示でもある。
【００５６】
本発明の１つの実施形態では、各々の領域には展開アイコン（「＋」すなわち「プラスのオペレーターシンボル」によってラベル付けされたもの）が備わっている。このアイコンをクリックすると、その領域のノードのためのコラージュが表示される。例えば、図４には、図３（Ａ）における左上領域をクリックすることによって取得された結果としてのコラージュが図示されており、それは、その子孫の代表画像からなっている。
【００５７】
本発明の１つの実施形態では、そのランク順序は視覚化において維持される。左上から始まって、そのランクは左から右へおよび行にしたがって下がっていく。順序の付けられた画像は英語における文章のパラグラフのように割り付けられる。
【００５８】
本発明の１つの実施形態では、そのランクはユーザがツリーを下ってナビゲートするときにも維持される。たとえツリーのどのレベルが表示されていても、ノードのトップランクの画像が左上部分であるトップランクのスポットに常にあるであろうということを意味している（図３および図４を参照）。
「クラスタのコラージュのカスケード表示」
本発明の１つの実施形態の方法は、ラベルの付けられた画像のいくつかをカテゴリツリーあるいはオントロジーへ構造化することができる検索結果とともに機能するように一般化することができる。ＲＤＦのようなＸＭＬ、ＸＭＬスキーマ、およびＭＰＥＧ−７におけるメタデータを利用するこの種の構造のためのウェブ標準がある。したがって、本方法は、データがウェブにおいて構造化され、かつ、それがウェブページの作成者によって提供されるときにその構造を反映することのできる方法（例えば、ウェブページにタグを使用する）との間で高度な互換性がある。
【００５９】
本発明の１つの実施形態の方法は、ある画像が正式に定義されたいくつかのメタデータによってラベル付けされていないときには、他の画像のテキストラベルに関連しているその画像のウェブサイトにおけるテキストを見ることによって、何らかの構造を見出すことを試みる。カテゴリツリーは、その画像のウェブページについての周辺のテキスト（例えば、オレンジ−果物−植物、オレンジ−色）を解析するために、語彙データベース（例えば、ワードネット、非特許文献１６）による言語処理によって推測されることが往々にしてある。
【００６０】
本発明の１つの実施形態では、コラージュにおける画像どうしの境界の色あるいは他の視覚的属性（例えば境界の太さ）を変えることで、視覚化によって、あるセットの画像が同一のカテゴリに属するかどうかを示すことができる。例えば、カテゴリに関係がないときには、その境界は図８に示されるように黒色であってよく、カテゴリに関係があるときには、その境界は図９に示されるように灰色であってよい。
【００６１】
カスケード表示によって、２種以上の特徴をｋツリーを生成するためのクラスタリングおよびカテゴリ化の処理に利用し、この処理を連続的に行う。本発明の１つの実施形態では、この処理は最も一般的な特徴から最も特別な特徴へ向かって行われる。本発明のさらに別の実施形態では、最も一般的なレベルで、画像についてのテキストデータあるいは意味情報によることなく、画像を示す低レベルのデータによって、画像はクラスタリングされる。本発明の１つの実施形態では、これはある画像における画素のＲＧＢ値であってもよい。本発明のさらに別の実施形態では、画像の色ヒストグラムが使用される。これが実際により有効であるからである。本発明のさらに別の実施形態では、メタデータのラベルが推測されるかあるいは提供されると、それらは、カテゴリ化のために利用されるとともに、低レベルの特徴を無効にする。カテゴリツリーにおける画像のラベルが特別なものであればあるほど、その画像は一般的なものから特別なものへ移行する処理に付されることがほとんどない。したがって、これはｋツリーを生成するための直感的にわかる方法である。
【００６２】
一例が図８および図９に示されている。ここで使用された質問用語は「ジャガー」であり、また、１００個の画像のランク付けリストは非特許文献１から取得された。画像セットは手作業によってラベル付けされ、ここでは７７個の画像が、明確に識別できるカテゴリ、すなわち、自動車、猫、ＯＳ、および飛行機にカテゴリ化された。残りの画像はラベル付けされなかった。図８（Ａ）は、ラベル情報が利用されないときの最高レベルコラージュを示している。図８（Ｂ）では、コンピュータ演算により達成することができるおおまかな推定値である０．７５の確率で画像のラベルを無作為に利用することによって、一部ラベル付けされた事例をシミュレートした（非特許文献２０を参照）。図８（Ｃ）では、ラベル付けされた情報が完全に利用されている。表１には結果が要約されている。
【００６３】
【表１】
2007128523.tif 000003
これらの最高レベルコラージュを検討することで、図８（Ｃ）に示されたようにラベル付けされた情報を利用して取得されたコラージュがカテゴリの再現(recall)の点で最良であり、１００％（４／４）であることがわかる。他の２つの例では７５％（３／４）という同一の再現率であった。しかしながら、一部ラベル付けされた事例では、冗長性が少ないので、ラベル付けされていない事例よりも良好に実行される（図８（Ｂ）のコラージュにおける初めの２つ画像は相異なるカテゴリからのものであることに留意すべきである）。
【００６４】
本発明の好ましい実施形態についての上記説明は例示および説明の目的のために提供された。上記説明によって、本発明を網羅することあるいは本発明を開示された正確な形態に限定することは意図されていない。本発明の原理およびその実際的用途を最もよく表現し、それによって、他の当業者が様々な実施形態と意図された特別な利用に適している様々な修正とについて本発明を理解することができるようにするために、多くの実施形態が選択されかつ説明された。本発明の範囲を、特許請求の範囲およびそれらの均等物によって定義することが意図されている。
【００６５】
本発明の様々な実施形態は、コンピュータの分野における当業者に明らかなように、この開示の教示にしたがってプログラムされたプロセッサを利用して実施することができる。適切なソフトウェアのコード化は、ソフトウェアの分野における当業者に明らかなように、この開示の教示にもとづいた熟練プログラマーによって容易に準備することができる。本発明は、当業者に容易に明らかなように、集積回路を準備することによって、コンポーネント回路の適切なネットワークを相互接続することによって、実施することもできる。
【００６６】
様々な実施形態には、記憶された指示、情報を有していて、多目的あるいは専用の演算プロセッサ、演算装置に存在している任意の特性を実行するために、該演算プロセッサ、演算装置をプログラムするために使用される記憶媒体であってもよいコンピュータプログラム製品が含まれている。この記憶媒体には、フロッピー（登録商標）ディスク、光ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、マイクロドライブ、光磁気ディスク、ホログラフィック記憶装置、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、ＰＲＡＭ、ＶＲＡＭ、フラッシュメモリ装置、磁気カード、光カード、ナノシステム（分子メモリＩＣを含んでいる）を含んでいる任意の型の物理的媒体、紙あるいは紙を用いた媒体、指示、情報を記憶するのに適している任意の型の媒体あるいは装置の少なくとも１つを含んでいてもよい。しかしながら、本発明はこれらに限定されるものではない。様々な実施形態には、全体としてあるいは部分的に、１つ以上のパブリックネットワーク、プライベートネットワークによって送信することができ、その送信に指示、情報が含まれていて、本明細書に記載されている任意の特性を実施するために１つ以上のプロセッサによって利用することができるコンピュータプログラム製品が含まれている。様々な実施形態では、送信に複数の別個の送信が含まれていてもよい。
【００６７】
本開示には、１つ以上のコンピュータ可読媒体に記憶され、プロセッサのハードウェアを制御するため、および、コンピュータ、プロセッサが人間のユーザあるいは他の装置とインタラクションして本発明の結果を利用することを可能にするためのソフトウェアが含まれている。このようなソフトウェアは、デバイスドライバ、インターフェイスドライバ、オペレーティングシステム、実行環境、実行コンテナ、ユーザインターフェイスおよびアプリケーションを含んでいてもよいが、これらに限定されない。
【００６８】
コードの実行は直接的であっても間接的であってもよい。コードには、コンパイラ型言語、インタープリタ型言語および他の型の言語が含まれていてもよい。特許請求の範囲の記載によって制限されない限り、ある機能のためのコード、コードセグメントの実行、送信には、その機能を実施するために、他のソフトウェアあるいは装置の、ローカルあるいはリモートの呼び出しあるいはコールが含まれていてもよい。この呼び出しあるいはコールには、その機能を実施するために、ライブラリモジュール、デバイスドライバ、インターフェイスドライバおよびリモートソフトウェアへの呼び出しあるいはコールが含まれていてもよい。この呼び出しあるいはコールには、分散システムおよびクライアント・サーバーシステムにおける呼び出しあるいはコールが含まれていてもよい。
「優先権の主張」
本出願は、米国特許法第１１９条第（ｅ）項の下において、代理人整理番号がＦＸＰＬ−０１１１７ＵＳ０  ＭＣＦ／ＡＧＣであって２００５年１１月３日に出願されて引用によってこの明細書の中に組み入れられる、発明の名称が「クラスタコラージュのカスケード表示：画像検索結果の小表示装置における視覚化」（Ｃａｓｃａｄｉｎｇ  Ｃｌｕｓｔｅｒ  Ｃｏｌｌａｇｅｓ：  Ｖｉｓｕａｌｉｚａｔｉｏｎ  ｏｆ  Ｉｍａｇｅ  Ｓｅａｒｃｈ  Ｒｅｓｕｌｔｓ  ｏｎ  Ｓｍａｌｌ  Ｄｉｓｐｌａｙｓ）であるパトリック・チュー（Ｐａｔｒｉｃｋ  Ｃｈｉｕ）らによる米国仮出願第６０／７３３，４３８号の優先権を主張するものである。
「関連出願の相互参照」
この出願は以下の出願に関連している。
（１）出願番号：１０／８１５，３８９号  ２００４年３月３１日出願、発明の名称「関心のある映像領域の抽出」（Ｅｘｔｒａｃｔｉｎｇ  Ｖｉｄｅｏ  Ｒｅｇｉｏｎｓ  ｏｆ  Ｉｎｔｅｒｅｓｔ）、パトリック・チュー（Ｐａｔｒｉｃｋ  Ｃｈｉｕ）ら
（２）出願番号：１０／８１５，３５４号  ２００４年３月３１日出願、発明の名称「高度に凝縮された視覚的要約の生成」（Ｇｅｎｅｒａｔｉｎｇ  ａ  ｈｉｇｈｌｙ  Ｃｏｎｄｅｎｓｅｄ  Ｖｉｓｕａｌ  Ｓｕｍｍａｒｙ）、パトリック・チュー（Ｐａｔｒｉｃｋ  Ｃｈｉｕ）ら
（３）出願番号：１０／９４８，７３０号  ２００４年９月２３日出願、発明の名称「写真および画像における関心領域の決定」（Ｄｅｔｅｒｍｉｎｉｎｇ  Ｒｅｇｉｏｎｓ  ｏｆ  Ｉｎｔｅｒｅｓｔ  ｉｎ  Ｐｈｏｔｏｇｒａｐｈｓ  ａｎｄ  Ｉｍａｇｅｓ）、パトリック・チュー（Ｐａｔｒｉｃｋ  Ｃｈｉｕ）ら
（４）出願番号：１０／９４８，８２３号  ２００４年９月２３日出願、発明の名称「写真および画像における関心領域の決定」（Ｄｅｔｅｒｍｉｎｉｎｇ  Ｒｅｇｉｏｎｓ  ｏｆ  Ｉｎｔｅｒｅｓｔ  ｉｎ  Ｐｈｏｔｏｇｒａｐｈｓ  ａｎｄ  Ｉｍａｇｅｓ）、パトリック・チュー（Ｐａｔｒｉｃｋ  Ｃｈｉｕ）ら
【図面の簡単な説明】
【００６９】
【図１】本発明にしたがって表示するために複数の画像を要約するイベントフローチャートのブロック図を示している。
【図２】コップ一杯の搾りたてのオレンジジュースとオレンジの半分とのＰＤＡにおける画面ショットのイラストである。
【図３】（Ａ）は、画像の関心領域の「ステンドグラス」コラージュを表示する画面ショットのイラストであり、（Ｂ）は、（Ａ）におけるコラージュを生成する関心領域の対応する全体画像のイラストである。
【図４】図３（Ａ）におけるコラージュの左上隅の「＋」すなわち「プラスのオペレーターシンボル」のアイコンが選択される場合に、表示されるコラージュのイラストである。
【図５】ランク付けされた画像が同値類（１，２，３，…，Ｎ）へどのようにして区分されるかを模式的に示す。最高ランクの画像（ｓ0，ｓ1，ｓ2，…，ｓM）が代表画像（黒三角によって表わされている）として選択される。
【図６】代表画像（黒三角印によって表わされている）が同値類からどのようにして再帰的にカテゴリ化される（円の内部で黒三角印によって表わされているか、あるいは円の内部における円の内部で黒三角印によって表わされている）か、に関する初めの２回の繰り返しを示す。破線の下は各々の繰り返しに対応するｋツリー（ｋ＝５）である。
【図７】同値類ｓ0の各々がどのようにしてｋツリーへ帰納的にクラスタリングされるかを模式的に示す。
【図８】「ジャガー」の「ステンドグラス」のイラストを示す。（Ａ）は、画像のラベルが使用されていない（ｐ＝０）場合であり、（Ｂ）は画像のラベルが一部使用されている（ｐ＝０．７５）場合であり、（Ｃ）は画像のラベルが全部使用されている（ｐ＝１．０）場合である。
【図９】同一の同値類の内部における画像の間に灰色の境界が使用されている「ジャガー」の「ステンドグラス」コラージュのイラストを示す。
【図１】
2007128523.tif 000004
【図２】
2007128523.tif 000005
【図３（Ａ）】
2007128523.tif 000006
【図３（Ｂ）】
2007128523.tif 000007
【図４】
2007128523.tif 000008
【図５】
2007128523.tif 000009
【図６】
2007128523.tif 000010
【図７】
2007128523.tif 000011
【図８（Ａ）】
2007128523.tif 000012
【図８（Ｂ）】
2007128523.tif 000013
【図８（Ｃ）】
2007128523.tif 000014
【図９】
2007128523.tif 000015