(57)【特許請求の範囲】
【請求項１】
デジタル画像またはマルチメディアアイコンなどの検索可能な項目を配置して表示するシステムであって、
レイアウト空間内に項目を配置するための費用関数であって、前記項目の１つまたは複数の所定の特性に適用される費用関数を最小にし、
各項目が前記レイアウト空間内に空間分布を有するとみなすことによって混合分布を構築し、
各項目が前記レイアウト空間内で別個の位置を占める範囲を最大にするために、前記混合分布のエントロピーを制御する、オプティマイザモジュールと、
上記の通り生成されたレイアウトを表示装置にレンダリングするレンダラモジュールと
を備える、システム。
【請求項２】
前記費用関数が、低エントロピー混合分布にはペナルティを科し、前記レイアウト空間内の項目間の距離が、前記項目の内容類似度に依存しているレイアウトには報酬を与える、請求項１に記載のシステム。
【請求項３】
前記レイアウト空間が、項目が含まれる１つまたは複数のレイアウト領域を備える、請求項１又は２に記載のシステム。
【請求項４】
レイアウト空間内の各項目の前記空間分布が、ガウス分布である、請求項１から３のいずれか一項に記載のシステム。
【請求項５】
前記空間分布が、ガウス混合分布である、請求項４に記載のシステム。
【請求項６】
前記混合分布が、各ガウス要素について同等の重みを有する、請求項５に記載のシステム。
【請求項７】
前記項目が、内容類似度に基づいてレイアウトされる、請求項１から６のいずれか一項に記載のシステム。
【請求項８】
前記所定の特性が、色、テクスチャ、および／または形状などの様相を表す特徴である、請求項１から７のいずれか一項に記載のシステム。
【請求項９】
各項目のサムネイルまたはアイコンの寸法および形状情報を、前記費用関数に埋め込むことができる、請求項１から８のいずれか一項に記載のシステム。
【請求項１０】
前記エントロピーが、２次レニーエントロピーである、請求項１から９のいずれか一項に記載のシステム。
【請求項１１】
前記レニーエントロピーの２個１組の公式が使用される、請求項１０に記載のシステム。
【請求項１２】
前記項目を処理するステップが、
前記項目がデータ多様体で分布していると仮定するステップと、
前記データ多様体の前記構造を求めるステップと、
前記項目の前記内容構造をほぼ保存するように、多様体学習法を適用して、項目を低次元レイアウト空間にマッピングするステップと
を含む、請求項１から１１のいずれか一項に記載のシステム。
【請求項１３】
前記費用関数が、前記レイアウト空間内の前記項目の前記エントロピーと、前記内容構造保存とをトレードオフするようにさらに適合される、請求項１から１２のいずれか一項に記載のシステム。
【請求項１４】
前記トレードオフを制御するパラメータが、ユーザ定義のものである、請求項１３に記載のシステム。
【請求項１５】
前記項目が、前記表示装置上で２次元に配置される、請求項１から１４のいずれか一項に記載のシステム。
【請求項１６】
前記項目が、２次元表示装置上で３次元構成に見えるように配置される、請求項１から１４のいずれか一項に記載のシステム。
【請求項１７】
前記項目が、３次元表示装置上で３次元に配置される、請求項１から１４のいずれか一項に記載のシステム。
【請求項１８】
前記表示装置が、表示装置の一部とすることができる表示空間を備え、したがって前記項目が前記表示空間内に広がることになる、請求項１から１７のいずれか一項に記載のシステム。
【請求項１９】
前記項目が、画像または前記画像のサムネイルである、請求項１から１８のいずれか一項に記載のシステム。
【請求項２０】
前記項目が、オーディオまたはビデオクリップなどのマルチメディア項目用のアイコンである、請求項１から１８のいずれか一項に記載のシステム。
【請求項２１】
前記オプティマイザモジュールが、いくつかのサブモジュールを備える、請求項１から２０のいずれか一項に記載のシステム。
【請求項２２】
前記オプティマイザモジュールが、前記項目の初期レイアウトを生成するイニシャライザモジュールを備える、請求項１から２１のいずれか一項に記載のシステム。
【請求項２３】
前記オプティマイザモジュールが、前記費用関数に基づいて最適レイアウトを検索する検索エンジンを備える、請求項１から２２のいずれか一項に記載のシステム。
【請求項２４】
前記費用関数が、マルチメディア内容モジュール、レイアウト分散モジュール、およびレイアウト範囲モジュールによって計算されたレイアウト品質スコアの組合せとして計算される、請求項１から２３のいずれか一項に記載のシステム。
【請求項２５】
前記マルチメディア内容サブモジュールが、前記レイアウトによって内容構造が保存される範囲を測定するスコアを計算する、請求項２４に記載のシステム。
【請求項２６】
前記レイアウト分散サブモジュールが、前記レイアウトの前記エントロピーを測定するスコアを計算する、請求項２４に記載のシステム。
【請求項２７】
前記レイアウト範囲サブモジュールが、前記項目が１つの前記レイアウト領域または複数の前記レイアウト領域内に配置される制約が満たされる範囲を測定するスコアを計算する、請求項２４に記載のシステム。
【請求項２８】
前記オプティマイザモジュールが、前記スコアを、前記検索エンジンが前記レイアウト用の費用関数値として使用する全体スコアに組み合わせるコンバイナモジュールをさらに備える、請求項２３に記載のシステム。
【請求項２９】
前記検索エンジンが、最適化法を適用して、スコアすべきレイアウトを提案する、請求項２８に記載のシステム。
【請求項３０】
前記検索エンジンが、レイアウトの提案およびスコアを数回反復した後、最適化レイアウトを出力する、請求項２８または請求項２９に記載のシステム。
【請求項３１】
表示装置を備えたユーザインタフェースと、
デジタル画像またはマルチメディアアイコンなどの検索可能な項目を表示画面上に配置するコンピュータソフトウェアを実行するように適合されたコンピューティング手段であって、前記コンピュータソフトウェアが、
請求項１から３０のいずれかに記載のオプティマイザモジュールと、
上記の通り生成されたレイアウトを前記表示装置にレンダリングするレンダラモジュールとを備えるコンピューティング手段と
を備える、ブラウザ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、項目(items)を配置して表示するシステムおよび方法に関し、特に、それだけに限られるものではないが、画像閲覧システムを使用する際にグラフィック的に表示することができる画像の見せ方に関する。本発明はまた、表示装置上にグラフィック的に表示することが可能な他のデジタル資産を配置するために使用することもできる。
【背景技術】
【０００２】
人間は、膨大な量の視覚的情報、およびマルチメディア情報を処理することができる。しかし、かかる情報を正確に定義し、説明するのは人間にとってしばしば困難である。例えば、脳は、色について約１０，０００ものニュアンスを識別することができると推定されているが、人はほんの少数の色名（約１２）しか挙げることができない。その結果、データベースを検索する際に、典型的にはメタデータを使用するテキストベースの検索を用いて画像にアクセスすることは困難となり得る。
【０００３】
この問題は、内容ベースの索引作成および検索方法によって、部分的には解決することができる。多くの内容ベース検索システムでは、照会項目に対する類似度の概念に基づいて、関連する項目を自動検索する点に重点が置かれている。例えば、内容ベース画像検索（ＣＢＩＲ）では、選択した絵画、写真、印刷、図面、または他の対象物の画像の特徴を用いて、視覚的に類似した画像を見つけ、それらの画像が、元の画像とはメタデータを共有していなくとも、コレクション内でマッチングを探し出すことができる。
【０００４】
閲覧は、探索的検索の有効な手段となり、また、ユーザがテキスト形式または画像形式の照会を公式化する従来の内容ベース検索に代わる有用な代替手段となる。さらに、画像および／またはマルチメディアコレクションを探索する際、ユーザの意図が非常に漠然としていることもあり得る。ユーザは、ナビゲーションを指南する様々な手がかりや選択肢が得られるシステムを期待している。
【０００５】
画像および／またはマルチメディア閲覧システムでは、項目（またはそれらのサムネイルもしくはアイコン）のコレクションを適切にレイアウトして表示することによって、ユーザがそれらのコレクションを映像化できるようにする必要がある。多くのシステムでは、諸項目が異なるクラスに分類され、それらの項目は、各クラスの１次元リストとして２次元表示装置上に単にレイアウトされるだけである（Ｋａｎｇ，Ｈ．およびＳｈｎｅｉｄｅｒｍａｎ，Ｂ．（２０００）、「Ｖｉｓｕａｌｉｚａｔｉｏｎ  ｍｅｔｈｏｄｓ  ｆｏｒ  ｐｅｒｓｏｎａｌ  ｐｈｏｔｏ  ｃｏｌｌｅｃｔｉｏｎｓ  ｂｒｏｗｓｉｎｇ  ａｎｄ  ｓｅａｒｃｈｉｎｇ  ｉｎ  ｔｈｅ  ｐｈｏｔｏｆｉｎｄｅｒ」、ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍｕｌｔｉｍｅｄｉａ  ａｎｄ  Ｅｘｐｏ、１５３９〜１５４２頁）。かかる１次元リストでは、項目間の相互関係がうまく描写されない。
【０００６】
あるいは、２次元マップに基づいた映像化（例えば、Ｎｇｕｙｅｎ，Ｇ．およびＷｏｒｒｉｎｇ，Ｍ．（２００６）、「Ｉｎｔｅｒａｃｔｉｖｅ  ａｃｃｅｓｓ  ｔｏ  ｌａｒｇｅ  ｉｍａｇｅ  ｃｏｌｌｅｃｔｉｏｎｓ  ｕｓｉｎｇ  ｓｉｍｉｌａｒｉｔｙ−ｂａｓｅｄ  ｖｉｓｕａｌｉｚａｔｉｏｎ」、Ｊｏｕｒｎａｌ  ｏｆ  Ｖｉｓｕａｌ  Ｌａｎｇｕａｇｅｓ  ａｎｄ  Ｃｏｍｐｕｔｉｎｇ，１９（２）：２０３〜２２４）では、類似した項目が２次元表示装置上で互いに近接して表示され、非常に異なる画像は離れるように項目がレイアウトされる。２次元マップに基づいた技術は、項目から高次元の特徴ベクトルを抽出し、２個１組の項目の類似度を測定し、次元削減を高次元空間から２次元表示空間へと実施して、項目の分布をマッピングする点において異なる（Ｒｏｄｄｅｎ，Ｋ．（２００２）、「Ｅｖａｌｕａｔｉｎｇ  ｓｉｍｉｌａｒｉｔｙ−ｂａｓｅｄ  ｖｉｓｕａｌｉｓａｔｉｏｎｓ  ａｓ  ｉｎｔｅｒｆａｃｅｓ  ｆｏｒ  ｉｍａｇｅ  ｂｒｏｗｓｉｎｇ」、ＰｈＤ論文、Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｃａｍｂｒｉｄｇｅ）。
【０００７】
例えば、Ｒｕｂｎｅｒ他（Ｒｕｂｎｅｒ，Ｙ．、Ｔｏｍａｓｉ，Ｃ．、およびＧｕｉｂａｓ，Ｌ．（１９９８）、「Ａ  ｍｅｔｒｉｃ  ｆｏｒ  ｄｉｓｔｒｉｂｕｔｉｏｎｓ  ｗｉｔｈ  ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  ｉｍａｇｅ  ｄａｔａｂａｓｅｓ」、ＩＣＣＶ、５９〜６６頁、Ｂｏｍｂａｙ、Ｉｎｄｉａ）は、Ｅａｒｔｈ  Ｍｏｖｅｒ’ｓ  Ｄｉｓｔａｎｃｅを用いて２個１組の非類似度を測定し、多次元スケーリング（ＭＤＳ）を実施して、画像カラーおよびテクスチャ特徴を２次元空間に変換した。
【０００８】
多数の項目を表示装置上で閲覧用に映像化すると、項目同士が重なり、この重なりの度合いは、項目数に伴って増大する傾向がある。さらに、表示空間領域が空白となることもしばしば生じる。次元削減法では、表示位置をマッピングする際に、項目を表すために使用する画像（例えば、画像サムネイルまたはアイコン）の寸法が考慮されないため、こうした問題は悪化する。２つの非常に類似した項目は、おそらく非常に近接した位置に投影されることになり、したがって一方が他方と大幅に重なることになる。重なりを低減させるために、次元削減によって２次元表示装置上に画像位置を得た後、勾配降下法を用いて、重なり合った画像を空いている２次元表示領域に移動させることが行われてきている。Ｂａｓａｌａｊ（Ｂａｓａｌａｊ、２０００）およびＬｉｕ他（Ｌｉｕ他、２００４）は、ＭＤＳの類似型を分散ドメインに用いて、グリッドの単一セル内で各画像を表示した。これらの手法は、画像の重なりを低減させる一助となり得るが、こうした手法では、主に少数（約２０〜２００）の画像しか取り扱われない。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、表示装置上で項目をレイアウトまたは配置する方式を改善することである。
【課題を解決するための手段】
【００１０】
本発明の第１の態様によれば、デジタル画像またはマルチメディアアイコンなどの検索可能な項目を配置して表示するシステムであって、
レイアウト空間内に項目を配置するための費用関数であって、項目の１つまたは複数の所定の特性に適用される費用関数を最小にし、
各項目がレイアウト空間内に空間分布を有するとみなすことによって混合分布を構築し、
各項目がレイアウト空間内で別個の位置を占める範囲を最大にするために、混合分布のエントロピーを制御する、オプティマイザモジュールと、
上記の通り生成されたレイアウトを表示装置にレンダリングするレンダラモジュールと
を備える、システムが提供される。
【００１１】
好ましくは、費用関数は、低エントロピー混合分布にはペナルティを科し(penalise)、レイアウト空間内の項目間の距離が、それら項目の内容類似度に依存しているレイアウトには報酬を与える(reward)。
【００１２】
好ましくは、レイアウト空間は、項目が含まれる１つまたは複数のレイアウト領域を備える。
【００１３】
好ましくは、レイアウト空間内の各項目の空間分布は、ガウス分布である。
【００１４】
好ましくは、ガウス分布は、ガウス混合分布である。
【００１５】
好ましくは、混合分布は、各ガウス要素について同等の重みを有する。
【００１６】
好ましくは、項目は、内容類似度に基づいてレイアウトされる。
【００１７】
好ましくは、所定の特性とは、色、テクスチャ、および／または形状などの様相を表す特徴である。
【００１８】
好ましくは、各項目のサムネイルまたはアイコンの寸法および形状情報は、費用関数に組み込むことができる。
【００１９】
好ましくは、エントロピーは、２次レニーエントロピーである。
【００２０】
好ましくは、項目を処理するステップは、
項目がデータ多様体で分布していると仮定するステップと、
データ多様体の構造を求めるステップと、
項目の内容構造がほぼ保存されるように、多様体学習法を適用して、項目を低次元レイアウト空間にマッピングするステップと
を含む。
【００２１】
好ましくは、費用関数は、レイアウト空間内の項目のエントロピーと、内容構造保存とをトレードオフするようにさらに適合される。
【００２２】
好ましくは、このトレードオフを制御するパラメータは、ユーザ定義のものである。有利には、このパラメータによって、ユーザが、内容構造保存と、レイアウトエントロピーとのトレードオフを行うことが可能となる。
【００２３】
好ましくは、項目は、表示装置上で２次元に配置される。
【００２４】
あるいは、項目は、２次元表示装置上で３次元構成に見えるように配置される。
【００２５】
あるいは、項目は、３次元表示装置上で３次元に配置される。
【００２６】
好ましくは、表示装置は、表示装置の一部とすることができる表示空間を備え、したがって項目がその表示空間内に広がることになる。
【００２７】
好ましくは、項目は、画像または画像のサムネイルである。
【００２８】
あるいは、項目は、オーディオまたはビデオクリップなどのマルチメディア項目用のアイコンである。
【００２９】
好ましくは、オプティマイザモジュールは、いくつかのサブモジュールを備える。
【００３０】
好ましくは、オプティマイザモジュールは、項目の初期レイアウトを生成するイニシャライザモジュールを備える。
【００３１】
好ましくは、オプティマイザモジュールは、費用関数に基づいて最適レイアウトを検索する検索エンジンを備える。
【００３２】
好ましくは、費用関数は、マルチメディア内容モジュール、レイアウト分散モジュール、およびレイアウト範囲モジュールによって計算されたレイアウト品質スコアの組合せとして計算される。
【００３３】
好ましくは、マルチメディア内容サブモジュールは、レイアウトによって内容構造が保存される範囲を測定するスコアを計算する。
【００３４】
好ましくは、レイアウト分散サブモジュールは、レイアウトのエントロピーを測定するスコアを計算する。
【００３５】
好ましくは、レイアウト範囲サブモジュールは、項目が１つのレイアウト領域または複数のレイアウト領域内に配置される制約が満たされる範囲を測定するスコアを計算する。
【００３６】
好ましくは、オプティマイザモジュールは、これらのスコアを、検索エンジンがレイアウト用の費用関数値として使用する全体スコアに組み合わせるコンバイナモジュールをさらに備える。
【００３７】
好ましくは、検索エンジンは、最適化法を適用して、スコアすべきレイアウトを提案する。
【００３８】
好ましくは、検索エンジンは、レイアウトの提案およびスコアを数回反復した後、最適化レイアウトを出力する。
【００３９】
本発明の第２の態様によれば、デジタル画像またはマルチメディアアイコンなどの検索可能な項目を配置して表示する方法であって、
各項目がレイアウト空間内に空間分布を有するとみなすことによって混合分布を構築するステップと、
レイアウト空間内に項目を配置する費用関数であって、項目の１つまたは複数の所定の特性に適用される費用関数を最小にするステップと、
各項目がレイアウト空間内で別個の位置を占める範囲を最大にするために、混合分布のエントロピーを制御するステップと、
上記の通り生成されたレイアウトを表示装置にレンダリングするステップと
を含む、方法が提供される。
【００４０】
好ましくは、費用関数は、低エントロピー混合分布にはペナルティを科し、レイアウトの項目間の距離が、それら項目の内容類似度に依存しているレイアウトには報酬を与える。
【００４１】
好ましくは、レイアウト空間は、項目が含まれる１つまたは複数のレイアウト領域を備える。
【００４２】
好ましくは、レイアウト空間内の各項目の空間分布は、ガウス分布である。
【００４３】
好ましくは、混合分布は、ガウス混合分布である。
【００４４】
好ましくは、混合分布は、各ガウス要素について同等の重みを有する。
【００４５】
好ましくは、項目は、内容類似度に基づいてレイアウトされる。
【００４６】
好ましくは、項目の所定の特性とは、色、テクスチャ、および／または形状などの様相を表す特徴である。
【００４７】
好ましくは、各項目のサムネイルまたはアイコンの形状情報は、費用関数に埋め込むことができる。
【００４８】
好ましくは、エントロピーは、２次レニーエントロピーである。
【００４９】
好ましくは、項目を処理するステップは、
項目がデータ多様体で分布していると仮定するステップと、
データ多様体の構造を求めるステップと、
内容構造をほぼ保存するように、多様体学習法を適用して、項目を低次元レイアウト空間にマッピングするステップと
を含む。
【００５０】
好ましくは、費用関数は、レイアウト空間内の項目のエントロピーと、内容構造保存とをトレードオフするようにさらに適合される。
【００５１】
好ましくは、このトレードオフを制御するパラメータは、ユーザ定義のものである。有利には、このパラメータによって、ユーザが、内容構造保存と、レイアウトエントロピーとのトレードオフを行うことが可能となる。
【００５２】
好ましくは、項目は、表示装置上で２次元に配置される。
【００５３】
あるいは、項目は、２次元表示装置上で３次元構成に見えるように配置される。
【００５４】
あるいは、項目は、３次元表示装置上で３次元に配置される。
【００５５】
好ましくは、表示装置は、表示装置の一部とすることができる表示空間を備え、項目がその表示空間内に広がるようにされる。
【００５６】
好ましくは、項目は、画像または画像のサムネイルである。
【００５７】
あるいは、項目は、オーディオまたはビデオクリップなどのマルチメディア項目用のアイコンである。
【００５８】
本発明の第３の態様によれば、
表示装置を備えたユーザインタフェースと、
デジタル画像またはマルチメディアアイコンなどの検索可能な項目を表示画面上に配置するコンピュータソフトウェアを実行するように適合されたコンピューティング手段であって、該コンピュータソフトウェアが、
レイアウト空間に項目を配置するための費用関数であって、項目の１つまたは複数の所定の特性に適用される費用関数を最小にし、
各項目がレイアウト空間内に空間分布を有するとみなすことによって混合分布を構築し、
各項目がレイアウト空間で別個の位置を占める範囲を最大にするために、混合分布のエントロピーを制御する、オプティマイザモジュールと、
上記の通り生成されたレイアウトを表示装置にレンダリングするレンダラモジュールと
を備えるコンピューティング手段と
を備える、ブラウザが提供される。
【００５９】
好ましくは、費用関数は、低エントロピー混合分布にはペナルティを科し、レイアウトの項目間の距離が、それら項目の内容の類似度に依存しているレイアウトには報酬を与える。
【００６０】
好ましくは、レイアウト空間は、項目が含まれる１つまたは複数のレイアウト領域を備える。
【００６１】
好ましくは、レイアウト空間内の各項目の空間分布は、ガウス分布である。
【００６２】
好ましくは、混合分布は、ガウス混合分布である。
【００６３】
好ましくは、混合分布は、各ガウス要素について同等の重みを有する。
【００６４】
好ましくは、項目は、内容類似度に基づいてレイアウトされる。
【００６５】
好ましくは、項目の所定の特性とは、色、テクスチャ、および／または形状などの様相を表す特徴である。
【００６６】
好ましくは、各項目のサムネイルまたはアイコンの形状情報は、費用関数に埋め込むことができる。
【００６７】
好ましくは、エントロピーは、２次レニーエントロピーである。
【００６８】
好ましくは、項目を処理するステップは、
項目がデータ多様体で分布していると仮定するステップと、
データ多様体の構造を求めるステップと、
内容構造をほぼ保存するように、多様体学習法を適用して、項目を低次元レイアウト空間にマッピングするステップと
を含む。
【００６９】
好ましくは、費用関数は、レイアウト空間内のレイアウトのエントロピーと、内容構造保存とをトレードオフするようにさらに適合される。
【００７０】
好ましくは、このトレードオフを制御するパラメータは、ユーザ定義のものである。有利には、このパラメータによって、ユーザが、内容構造保存と、レイアウトエントロピーとのトレードオフを行うことが可能となる。
【００７１】
好ましくは、項目は、表示装置上で２次元に配置される。
【００７２】
あるいは、項目は、２次元表示装置上で３次元構成に見えるように配置される。
【００７３】
あるいは、項目は、３次元表示装置上で３次元に配置される。
【００７４】
好ましくは、オプティマイザモジュールは、いくつかのサブモジュールを備える。
【００７５】
好ましくは、オプティマイザモジュールは、項目の初期レイアウトを生成するイニシャライザモジュールを備える。
【００７６】
好ましくは、オプティマイザモジュールは、費用関数に基づいて最適レイアウトを検索する検索エンジンを備える。
【００７７】
好ましくは、費用関数は、マルチメディア内容モジュール、レイアウト分散モジュール、およびレイアウト範囲モジュールによって計算されたレイアウト品質スコアの組合せとして計算される。
【００７８】
好ましくは、マルチメディア内容サブモジュールは、レイアウトによって内容構造が保存される範囲を測定するスコアを計算する。
【００７９】
好ましくは、レイアウト分散サブモジュールは、レイアウトのエントロピーを測定するスコアを計算する。
【００８０】
好ましくは、レイアウト範囲サブモジュールは、項目が１つのレイアウト領域または複数のレイアウト領域内に配置される制約が満たされる範囲を測定するスコアを計算する。
【００８１】
好ましくは、オプティマイザモジュールは、これらのスコアを、検索エンジンがレイアウト用の費用関数値として使用する全体スコアに組み合わせるコンバイナモジュールをさらに備える。
【００８２】
好ましくは、検索エンジンは、最適化法を適用して、スコアすべきレイアウトを提案する。
【００８３】
好ましくは、検索エンジンは、レイアウトの提案およびスコアを数回反復した後、最適化レイアウトを出力する。
【００８４】
次に、添付の図面を参照しながら、本発明を単なる例によって説明する。
【図面の簡単な説明】
【００８５】
【図１】本発明によるシステムの例を用いた項目データの収束を示し、特に、図１（ａ）は反復回数に対する費用関数値を示し、図１（ｂ）及び１（ｃ）は、初期の画像位置に基づいた画像コレクションの映像及び収束後の位置に基づいた画像コレクションの映像を示す図である。
【図２】本発明の方法、ならびに従来技術による代替法、すなわちＭｏｇｈａｄｄａｍ法およびＮｇｕｙｅｎ法を用いた、内容構造誤差と、画像重なりとの関係を示すグラフである
【図３】図３ａから３ｄは、各々、ｉｓｏｍａｐ、Ｍｏｇｈａｄｄａｍ法、Ｎｇｕｙｅｎ法、及び本発明の方法の例を用いた１００個の画像の映像を示す図である。
【図４−１】図４ａ〜４ｉは１０００個のアート画像の映像を示す図であり、図ａ〜ｃは、初期の画像位置、構造保存と画像重なりとのトレードオフによる位置、画像重なりの低減だけに焦点を当てた位置の分布を示す。
【図４−２】図４ａ〜４ｉは１０００個のアート画像の映像を示す図であり、図４ｄ、４ｆ及び４ｈは、図４ａ、４ｂ、４ｃの位置に対応する画像コレクションの映像を示し、図４ｅ、４ｇ及び４ｉは、レイアウト空間中央の画像周辺の画像位置をスケーリングした後の画像コレクションの一部の映像を示す。
【図５−１】図５ａ〜５ｉは１０００個のアート画像の映像を示す図であり、図ａ〜ｃは、初期の画像位置、構造保存と画像重なりとのトレードオフによる位置、画像重なりの低減だけに焦点を当てた位置の分布を示す。
【図５−２】図５ａ〜４ｉは１０００個のアート画像の映像を示す図であり、図５ｄ、５ｆ及び５ｈは、図５ａ、５ｂ、５ｃの位置に対応する画像コレクションの映像を示し、図５ｅ、５ｇ及び５ｉは、レイアウト空間中央の画像周辺の画像位置をスケーリングした後の画像コレクションの一部の映像を示す。
【図６】全ての画像位置が矩形レイアウト領域内に位置するように拘束された、アート画像の画像位置、および対応する画像映像を示す図である。
【図７】画像位置に基づいてテキスタイルサンプルを映像化した別の例を示す図である。
【図８】図８ａ及び８ｂは、各々、５００個の画像のレイアウトを最適化する際の反復当たりの時間及び得られた画像近似の精度のプロットを示す図である。図８ｃは、レイアウト内の画像数の関数としての平均計算時間のプロットを示す図であり、スケーリングの改善を示す図である。図８ｄは、本発明の近似法を用いて得られた１００個の画像のレイアウトを示す図である。
【図９】ステップサイズに閾値τを与えなかった場合（第１の列）、および閾値τ＝０．０５とした場合の、数回の反復後の画像位置の変化を示す図である。
【図１０】利用可能なレイアウト領域に対して画像数が多い場合の画像を広げる能力を、本発明と、２つの従来技術による技術とで比較した３つの図の組である。
【図１１】図１０に関して説明した技術の性能の差を簡略的に説明する図である。
【図１２】本発明、および従来技術によるＩｓｏｍａｐ技術を用い、カラーヒストグラムに基づいた１０００個の画像の映像を示す図である。
【図１３】本発明の実施形態のブロック図である。
【図１４】本発明によるオプティマイザモジュールの例を示すより詳細なブロック図である。
【発明を実施するための形態】
【００８６】
本発明は、項目をそれらの内容類似度に基づいて配置して表示することを可能とするシステム、方法、およびブラウザを提供する。本発明を用いて、画像などの項目を、それらの内容の特徴（形状、色、テクスチャ、およびパターンなど）に従って配置することができる。また、表示装置上での項目間の距離を、上記特徴に関して、それらの項目間の類似度に関連付けるように配置することができる。
【００８７】
この工程の第１の段階は、レイアウト空間内で項目のレイアウトを計算することである。レイアウトを計算した後は、そのレイアウトを用いて項目のレンダリングを生成して、コンピュータ画面などの装置に表示することができる。全てのレイアウト空間を、常に表示装置にマッピングする必要があるわけではない。例えば、ユーザは、レイアウトの小さい部分を詳細に見たい場合があるかもしれず、その場合には、レイアウトのその小さい部分に位置する項目だけが、表示空間／ウィンドウ上に実際にレンダリングされることになる。
【００８８】
用語「レイアウト」、「レイアウト領域」、および「レイアウト空間」は、データを目に見える表示画像にレンダリングする前の、項目に関連した処理済みデータを指すことを理解されたい。
【００８９】
本発明の少なくとも１つの例では、
利用可能なレイアウト領域を有効に使用できるように、項目をほぼ一様にレイアウトすること、
利用可能なレイアウト領域（例えば円形、矩形、または環状の場合がある）の範囲内で項目を保持すること、および
項目をそれらの内容に応じて、典型的には、類似した項目同士が互いに近接するようにレイアウトすること（本明細書では「内容構造保存」と呼ぶ）によって、レイアウト空間を「良好に」使用することを目的とする。
【００９０】
本発明は、費用関数を最適化し、各項目を混合モデルの要素と関連付けることによって、レイアウト空間内に形成された混合モデルを使用する。この混合モデルのエントロピーを最大にすることによって、レイアウト空間内で画像を広げて所定のレイアウト領域を占める効果が得られる。特に、各項目は、項目の空間範囲によって決まる共分散行列を用いたガウス分布、および効率的に計算され、最適化される２次レニーエントロピーに関連付けることができる。
【００９１】
理論に縛られたくはないが、本発明の少なくとも以下の実施形態が動作する数学的記述について以下で説明する。
【００９２】
一組の項目｛Ｉｉ｝，ｉ＝１，．．．，Ｎ，について、抽出された高次元特徴ベクトル｛Ｘｉ｝、および画像（またはサムネイルもしくはアイコン）寸法を｛Ｓｉ｝とすると、ここで取り扱う課題は、以下の２つの要件、すなわち（１）レイアウト空間内の項目間の距離は、それら項目の内容類似度に依存しなければならない、（２）レイアウト領域を良好に使用するように項目を広げなければならない、という２つの要件をトレードオフすることによって、レイアウト空間の所定の１つの領域、または複数の領域に項目をレイアウトすることである。
【００９３】
第１の要件は、多様体学習によって実現することができる。項目は、高次元空間に埋め込まれた低次元非線形多様体で分布していると仮定すると、多様体学習法を適用して、データ多様体の構造を検出し、発見し、その多様体をベクトル空間に展開することができる。元の高次元データ点を低次元ベクトル空間に忠実に埋め込むことができると、データベース内の画像の相対近接性は、低次元（例えば２次元または３次元）空間でもほぼ保存されることになる。これは、「内容構造保存（ｃｏｎｔｅｎｔ  ｓｔｒｕｃｔｕｒｅ  ｐｒｅｓｅｒｖａｔｉｏｎ）」と呼ばれる。
【００９４】
多数の高次元項目のコレクションを、２次元または３次元空間で映像化して、閲覧、調査、および組織化することができる。多様体構造、および構造保存に使用される基準によれば、多種多様な多様体学習法が提唱されてきており、例えば、Ｉｓｏｍａｐ（Ｔｅｎｅｎｂａｕｍ他、２０００）、Ｌａｐｌａｃｉａｎ固有マップ（ＢｅｌｋｉｎおよびＮｉｙｏｇｉ、２００２）、拡散マップ（Ｎａｄｌｅｒ他、２００５）および最大分散展開（Ｗｅｉｎｂｅｒｇｅｒ他、２００５）がある。原則として、いかなる多様体学習法も使用することができる。本明細書では、一例としてＩｓｏｍａｐを使用する。Ｉｓｏｍａｐは、まず｛Ｘｉ｝に基づいて低密度グラフを構築し、このグラフでは、項目と、グラフの頂点間で１対１の対応がある。
【００９５】
Ｋ近傍（ＫＮＮ）法によって、類似した項目間でエッジを構築する。各エッジには、重みＷｉｊが割り当てられ、この重みは、隣接する２つの項目間の非類似度である。次いで、任意の２つの項目間の測地距離に対する近似値Ｄｉｊを、それらの対応するグラフ上の頂点間の最短経路として得る。一般性を失わず、｛Ｄｉｊ｝は、最大Ｄｉｊがレイアウト領域寸法に制限されるように正規化される。Ｉｓｏｍａｐは、以下のＥｓを最小にすることによって、低次元（例えば、２次元または３次元）ベクトル空間内の画像位置｛ｙｉ｝を求めることができる。
【００９６】
【数１】
0005552495.tif 000002
式中、ｄｉｊは、ｙｉとｙｊ間のユークリッド距離である。    
【００９７】
２つの項目ＩｉとＩｊの内容が類似している場合、それらの項目間の距離Ｄｉｊは小さくなり、したがってこれら２つの項目は、低次元空間でおそらく互いに近接して表示されることになることに留意されたい。
【００９８】
第２の要件に関して、本発明者らは、レイアウト領域内に広がった項目の品質をエントロピーに関して測定する方法を提案する。低次元レイアウト領域内の画像位置をｙｉとすると、ガウス分布Ｇ（ｙｉ，Σｉ）を用いて空間内のこの画像の空間分布を近似させ、上記Σｉは項目寸法および形状、画像数、ならびにレイアウト領域の寸法によって求められる。次いで、レイアウト領域内に配置すべき全ての項目のガウス分布を組み合わせて、各ガウス要素について同等に重み付けられたガウス混合、すなわち、
【００９９】
【数２】
0005552495.tif 000003
を得ることができる。
【０１００】
レイアウト領域Ｒに項目を広げるために、レイアウト空間内のガウス混合のエントロピーを最大にすることができる。本明細書では、従来のシャノンエントロピーの代わりに、レニーの２次エントロピー測度法の使用を提案する。ガウス混合の２次レニーエントロピーＨは、ガウス要素間の２個１組の測定値の総計として、効率良く推定することができ（Ｔｏｒｋｋｏｌａ、２００３）、すなわち、
【０１０１】
【数３】
0005552495.tif 000004
によって得られる。
【０１０２】
Ｈを最大化する（または−Ｈを最小にする）ことによって、領域Ｒを良好に使用することができる。これには、空白の空間量を小さく維持し、かつ項目間の重なりを小さく維持するように項目を配置する効果があり、したがって、項目がその領域にわたってより一様に広がることになる。２つの要件は、トレードオフさせなければならない。これはすなわち、課題はＥλを最小にすることを意味する。
【０１０３】
【数４】
0005552495.tif 000005
上記は、各項目が領域Ｒの範囲内に存在しなければならないという制約を条件とし、λ∈［０，１］はトレードオフパラメータである。λは、アプリケーションに依存した形で決定しなければならない。λが０に近い場合、多様体構造の保存に重点が置かれる。λが１に近い場合、エントロピーの最大化に重点が置かれる。
【０１０４】
この最適化問題は、任意の数の周知の最適化法を用いて解決することができる。本明細書では、ペナルティ関数法を用いて、Ｒの外側に位置する項目にペナルティを科す。直観的に、項目位置ｙｉからレイアウト領域Ｒまでのユークリッド距離が大きくなるほど、項目の配置は悪くなり、したがってペナルティがより高くなる。全ての画像位置の平均ペナルティ費用は、Ｅｂによって示され、すなわち、
【０１０５】
【数５】
0005552495.tif 000006
となり、式中、ｆ（ｙｉ）は、ｙｉからレイアウト領域Ｒまでのユークリッド距離の単調増加非負関数（すなわち、ｍｉｎｙ∈Ｒ‖ｙ−ｙｉ‖）である。最後に、課題はＥを最小にすることに置き換えることができる。
【０１０６】
【数６】
0005552495.tif 000007
式中、γはＥλとＥｂとを平衡にする定数である。
【０１０７】
勾配ベース最適化を用いてＥの（局所）最小値を求めることができる。式（４）から、
【０１０８】
【数７】
0005552495.tif 000008
【０１０９】
Ｅｓのｙｊに関する勾配は、Ｋｒｕｓｋａｌ（ＣｏｘおよびＣｏｘ、２００１）によって以下で導かれている。
【０１１０】
【数８】
0005552495.tif 000009
【０１１１】
式（３）から、Ｈのｙｊに関する勾配を以下で導くことができる。
【０１１２】
【数９】
0005552495.tif 000010
【０１１３】
一般に、レイアウト領域の形状は自由であるため、関数ｆ（ｙｊ）をパラメータ的に表すのは困難であるので、Ｅｂのｙｊに関する勾配を求めるには、離散近似法を採用する。この近似法では、Ｅｂのｙｉに関する勾配のｋ番目の要素を
【０１１４】
【数１０】
0005552495.tif 000011
によって計算する。式中、δは離散ユニットスケールであり、ｕｋはレイアウト領域のｋ次元の基本ベクトルである。
【０１１５】
最適化のために、Ｉｓｏｍａｐアルゴリズムを用いてＥｓを最小にすることによって、良好な初期の項目位置｛ｙｉ｝を容易に得ることができる。
【０１１６】
この方法は、レイアウト領域の次元によっても、項目の形状によっても制約されない。しかし、本方法を実験的に評価するために、以下では、２次元レイアウト領域について考慮し、各画像Ｉｊを、高さｈｉおよび幅ｗｉの矩形と仮定する。この場合、共分散行列Σｉは、対角行列、すなわち
【０１１７】
【数１１】
0005552495.tif 000012
である。                            
【０１１８】
σｉ１およびσｉ２は、非常に小さくても、非常に大きくてもいけないものであり、その理由は、どちらの場合も、Ｈ（式３）が定数関数に収束することになり、したがって画像レイアウトを有効に広げることができなくなるからである点に留意されたい。本明細書では、画像寸法、レイアウト領域寸法、および広げるべき画像数によって、σｉ１およびσｉ２が自動的に決まる方法、すなわち
【０１１９】
【数１２】
0005552495.tif 000013
を提案する。式中、｜Ｒ｜はレイアウト領域の面積であり、
【０１２０】
【数１３】
0005552495.tif 000014
および
【０１２１】
【数１４】
0005552495.tif 000015
は、広げるべき全ての画像の平均幅および平均高さである。
【０１２２】
【数１５】
0005552495.tif 000016
は、各項目のグローバルスケール（ｇｌｏｂａｌ  ｓｃａｌｅ）であり、したがって、全ての項目の空間分布の組合せｐ（ｙ）（式２）によって、項目を広げるレイアウト領域をほぼ均一な分布で効果的にカバーすることができる。レイアウト領域Ｒが固定されている場合、項目数が増え、かつ平均項目寸法が大きくなるほど、グローバルスケールは小さくなる。項目の組が固定されている場合、レイアウト領域が広くなるほど、グローバルスケールも大きくなる。あらゆる対（σｉ１，σｉ２）が、対応する項目寸法、およびグローバルスケールに線形に関連付けられている。
【０１２３】
次に、本発明の性能について、２つの画像データベース、すなわち第１のデータベースは、商用アーカイブからのテキスタイルデザイン画像を１０００個有し、第２のデータベースは、公共の美術館コレクションからのアート画像を１０００個含む、２つの画像データベースを含めて、いくつかの画像データベースにおける本発明の使用する場合を参照しながら説明する。２種類の特徴を用いて、画像を表示した。ＨＳＶ色空間の色相を３２値、彩度を１６値に規則正しく量子化することによって、５１２ビンのカラーヒストグラムを抽出した。テクスチャ特徴は、多重解像度ガボール変換を実施し、次いで、画像分解能の各レベルで、この変換の係数の平均および分散を計算することによって抽出し、１０８個のテクスチャ特徴を得た。
【０１２４】
両種の特徴について、ユークリッド距離を用いて、多様体構造を構築する最近傍画像を求めた。この試験では、デフォルトレイアウト領域寸法を
【０１２５】
【数１６】
0005552495.tif 000017
とし、各画像Ｉｉを、その高さおよび幅の最大値がｓｍａｘ＝０．０８に予め設定されるように寸法変更した。さらに、本明細書で提案するアルゴリズムを量的かつ質的に２つの既存のアルゴリズムと比較するために、式４でγ＝０とし、その理由は、Ｅｂは、既存のアルゴリズムでは使用されていなかったためである。この場合、各Σｉについて、グローバルスケーリングなしで、σｉ１＝Ｗｉ／２、およびσｉ２＝ｈｉ／２とした。
【０１２６】
評価において、構造保存の性能を、以下の構造誤差ｅｓによって測定した。
【０１２７】
【数１７】
0005552495.tif 000018
式中、最小値ｅｓの正規化要因βは以下によって分析的に計算することができた。
【０１２８】
【数１８】
0005552495.tif 000019
画像分布の構造は、直観的に、全てのｄｉｊが同じ量だけスケーリングされる場合、同じでなければならないので、βはｅｓを計算するのに必要となる。
【０１２９】
評価のための第２の測定値は、全体的な画像重なりを表すｅｏであり、これは、表示空間内の２個１組全ての画像重なり
【０１３０】
【数１９】
0005552495.tif 000020
の総計であり、すなわち
【０１３１】
【数２０】
0005552495.tif 000021
式中、重なり領域の面積Ｚｉｊは、画像位置ｙｉおよびｙｊ、ならびに画像寸法（ｗｉ，ｈｉ）および（ｗｊ，ｈｊ）から直接計算することができる。画像重なりｅｏを計算する前に、全ての画像がデフォルト表示空間σｄ＝１内に位置するように、全てのｙｉ’およびｙｊ’を正規化しておかなければならないことに留意されたい。
【０１３２】
添付の図を参照すると、１００個の画像を備える第１の例を、図１ａおよび１ｂに示すように、ファブリック画像の組から一様にサンプリングした。各画像をガボール特徴によって表し、λを０．５に設定した。
【０１３３】
図１ａは、反復回数に対する費用関数の値を示すグラフ１である。このグラフは、約７０回の反復後に、費用値が安定値まで低減したことを示している。
【０１３４】
図１ｂおよび１ｃは、初期の画像位置、および収束後の位置に基づいた、１００個の画像全てを映像化した図である。これらの画像は、灰色背景上のファブリックのパターン片の画像である。図１ｂおよび１ｃはどちらも、同数のファブリック画像を含む。図１ｂは、画像がレイアウト空間３の中央に集まっている様子を示し、一方、図１ｃの画像は、明らかにレイアウト空間５全体にわたってより広がっている。これは、図１ｂと図１ｃのレイアウト空間の視覚的な比較から分かり、図１ｃではレイアウト空間のより広い面積が画像によって覆われている点に留意されたい。言い換えれば、これらの映像は、画像の位置分布は全く同様のまま、画像の重なりが幾分低減したことを示している。例えば、図１ｂおよび１ｃからの画像７および９は、同じ位置のままであり、参照番号１１および１３で示す、左側の表示装置境界付近の数個の画像間の重なりは、それらの画像がなおも互いに近接しながらも、大幅に低減していた。
【０１３５】
画像重なりと、構造保存との平衡化に関して、本発明のシステムおよび方法の実施形態を、２つの既存のアルゴリズム、すなわちＭｏｇｈａｄｄａｍのアルゴリズム（Ｍｏｇｈａｄｄａｍ他、２００４）およびＮｇｕｙｅｎのアルゴリズム（ＮｇｕｙｅｎおよびＷｏｒｒｉｎｇ、２００６）と量的かつ質的に比較した。公正に比較するために、構造保存に関して、３つの方法それぞれの費用関数に同じＥｓを使用した。Ｍｏｇｈａｄｄａｍ法、およびＮｇｕｙｅｎ法のどちらにおいても、各画像を半径ｓｍａｘ／２の円形画像によって近似させた。上述と同じ１００個の画像およびガボール特徴を使用した。トレードオフパラメータλを、０から１に徐々に変動させた。λ値ごとに、各アルゴリズムの収束結果に基づいて、構造誤差ｅｓ、および重なりｅｏを測定した。
【０１３６】
図２に示す構造保存と重なりとの関係から、任意の所与の構造誤差について、本発明のこの方法では、画像重なりが常に他の２つのアルゴリズムと同等またはそれよりも少なくなることが分かる。さらに、本発明の方法によって得られる最小の画像重なり（すなわち約２）は、他の２つの方法によって得られる最小の画像重なり（すなわち、それぞれ約４．５および約４）よりも遙かに少ない。このことは、画像コレクションの対応する映像（図３）から、知覚的に検証することができる。図３ａに示すＩｓｏｍａｐによって得られた初期の映像に比べて、Ｍｏｇｈａｄｄａｍ法およびＮｇｕｙｅｎ法（図３（ｂ）および（ｃ））によって得られた映像の方が、画像重なりが遙かに少なかった。しかし、画像重なりが最も小さくなるのは、図３（ｄ）に示す本発明の方法によって得られた映像である。図３（ｄ）では、ほぼ全ての画像が、他の画像との重なりが非常に小さい状態ではっきりと映像化されていることが分かる。本発明の方法のこの実施形態は、おそらく以下の２つの理由でより優れた性能を示していると思われる。
【０１３７】
まず、各画像の幅および高さのどちらもが費用関数に埋め込まれ、そのため２個１組の画像重なりをより効果的に近似させることができる。従来の２つの方法では、各画像を円形画像によって近似させていた。第２に、本明細書で提案する費用関数（式５）では、費用項−Ｈが滑らかであり、２個１組の距離に対してより広い領域で効果を有する。それに比べて、従来の両方法における画像重なりの費用項は、２つの画像間に画像重なりがない場合に２個１組の距離に対して効果のない区分的に滑らかな関数（ｐｉｅｃｅｗｉｓｅ  ｓｍｏｏｔｈ  ｆｕｎｃｔｉｏｎ）であり、したがって良好な最小値を見つけることが困難となっている。
【０１３８】
１０００個の画像を２組用いて、多大な画像コレクションについて、このアルゴリズムの性能を試験した。ガボール特徴を用いてファブリック画像を表し、カラーヒストグラムを用いてアート画像を表した。
【０１３９】
図４ａ〜ｉは、アート画像組について、２次元表示での画像位置、および対応する画像映像を示す。図４ａに示すＩｓｏｍａｐによって得られた初期の画像分布では、大部分の画像が表示装置中央付近に集まり、境界では、数個の画像が不規則に分布している。構造保存と画像重なりとをトレードオフすることによって、図４ｂに示すように、画像は、極端に集まることなく、より一様に分布している。画像重なりの低減に重点を置く場合（すなわちλ＝１）、図４ｃに示すように、諸画像は、近傍画像から最も一様に分散している。
【０１４０】
図４ｄ、４ｆ、および４ｈに示す、対応する画像映像は、構造保存要件を緩和させた場合も、類似した画像同士がなおも互いに近接して位置していることを示す。この白黒画像では、異なる色エリアを参照番号２１ａ〜ｃ、２３ａ〜ｃ、２５ａ〜ｃ、および２７ａ〜ｃによって表している。
【０１４１】
画像重なり低減における本発明の方法の効果を示すために、３つの分布について、表示装置中央付近の１つの画像周辺で拡大し、対応する映像を図４ｅ、４ｇ、および４ｉに示す。拡大動作によって画像位置がスケーリングされているが、画像自体はスケーリングされていない点に留意されたい。図４（ｅ）、（ｇ）、および（ｉ）は、本発明の方法によって、画像重なりを有効に低減させることができることを明白に示している。
【０１４２】
画像の閲覧において、本発明は、ユーザが多大な画像コレクション上で拡大して、画像重なりがより少ない状態で画像を詳細に見ることができる有効な策となることができる。
【０１４３】
図５は、テキスタイル画像の画像位置、および対応する画像映像、ならびに選択した画像周辺の画像位置の座標をスケーリングすることによって得られた、表示装置中央付近の画像周囲の拡大映像を示す。アート画像に関して上述した観察と同様の観察が得られる。ここでは、画像は、色特徴ではなく、テクスチャ特徴によって分布している。図５ｄ、５ｆ、および５ｈから、参照番号３１ａ〜ｃ、３３ａ〜ｃ、および３５ａ〜ｃで示されるエリアでは、画像テクスチャの粗度が、表示空間の上部から下部へと滑らかに変化していることが分かる。テクスチャの滑らかな変化は、ユーザが多大な画像コレクションを閲覧し、特定のテクスチャ情報を備えた当該画像を見つける一助となり得る。図５ｅ、ｇ、およびｉは、本発明の方法によって、画像重なりを有効に低減させることができることを明白に示している。
【０１４４】
上記実験結果は全て、γ＝０の場合に得られた。図６は、γ＝１０に設定した、アート画像の画像位置、および対応する画像映像を示し、この設定は、レイアウト領域内全ての画像位置を拘束するのに十分である。図４ｈおよび５ｈに比べて、図６は、画像レイアウトがレイアウト空間全体にわたってより広がり、したがって画像重なりが低減していることを示す。
【０１４５】
図７は、１０個のテキスタイルサンプルを画像位置に基づいて映像化した別の例である。図７ａは、本発明を用いた映像であり、図７ｂは、Ｉｓｏｍａｐを用いた映像であり、図７ｃは、Ｍｏｇｈａｄｄａｍ他の技術を使用し、図７ｄは、Ｎｇｕｙｅｎ他の技術を使用している。本発明を用いて得られた映像は、図７ｂ、７ｃ、および７ｄに示す、従来技術を用いて生成した映像に比べて、画像重なりがほとんどないことを示している。
【０１４６】
本明細書に記載の高エントロピーレイアウト（ＨＥＬＤ）法は、利用可能なレイアウト領域に合った項目レイアウトを生成し、高次元データ分布を近似させ、その結果、項目が一様に分布した表示をレンダリングする。低次元のレイアウト空間内で分布が形成されるように項目を取る。低エントロピー分布は、過剰密度のレイアウトを生じ、他の領域がまばらに占められるか、または空白となるレイアウトを生じるため、ペナルティが科される。
【０１４７】
一態様では、本発明は、既存の多様体ベースの学習法と、レニーエントロピーとの組合せに基づいて、計算的により効率の良い形で画像を配置するシステムおよび方法を構築し、かつ、グラフィカルユーザインタフェースに表示される画像をより良く分散させ、組織化して、ユーザが、画面上に表示された画像から、１つまたは複数の項目を選択する一助となるシステムおよび方法を構築する、内容ベースの画像コレクション映像化のための公式について記載する。さらに、小規模の近傍画像にわたって２個１組の測定を行うエントロピー近似化を用いて、このシステムおよび方法の効率を向上させることができる。
【０１４８】
この場合、以下の式は、総和が各画像の近傍画像のみにわたる場合の特例を表す。画像ｉの近傍画像の組をＦ（ｉ）によって示す。
【０１４９】
【数２１】
0005552495.tif 000022
【０１５０】
近似化によって、計算費用の削減と、精度維持との間で良き妥協が得られる。共分散行列に含むべき最近傍組は、具体的には、各画像中央の３σｉ以内のものである。
【０１５１】
【数２２】
0005552495.tif 000023
式中、ａは画像のアスペクト比である。前述のように、レニーの２次エントロピーを最大にすることによって、レイアウト領域内の空白空間の出現が最小限に抑えられ、画像重なりも最小限に抑えられることになる。
【０１５２】
図８は、計算時間および精度に対する近似化の効果を調べている。５００個のテキスタイル画像の組を、近似化あり、および近似化なしで配置し、それらの結果を比較した。図８ａおよび８ｂは、５００個の画像のレイアウトを最適化する際の反復当たりの時間のプロット、および得られた画像近似値の精度をそれぞれ示す。図８ｃは、レイアウト中の画像数の関数としての平均計算時間のプロットを示し、スケーリングの改善を示している。図８ｄは、本発明の近似化を用いて得られた１００個の画像のレイアウトを示す。この近似化によって、レイアウトはおそらく僅かに劣るものの、既存の既知の競合製品によって得られるレイアウトよりは優れ、また、使用する計算電力はより少なくなる。
【０１５３】
最適化中の、ステップサイズαの効果を調べるために、本発明の方法を、λ＝１．０、およびγ＝１．０で１０００個のアート画像に適用した。各画像をカラーヒストグラムで表し、式５の関数ｆ（ｙｉ）は、ｙｉからレイアウト領域Ｒまでのユークリッド距離の２乗関数とした。
【０１５４】
図９は、ステップサイズに閾値τを与えなかった場合（１列目）、およびτ＝０．０５とした場合（２列目）の、数回の反復後の画像位置の変化を示す。閾値を使用しなかった場合、多数の画像位置が、第１回目の反復で急激に変化し、その結果、画像同士が互いに「飛び越え（ｊｕｍｐｉｎｇ  ｏｖｅｒ）」、構造が大幅に損なわれた。それに比べて、τ＝０．０５とした場合、画像位置の変化は最初に制限され、最も大きい移動は、右側に見られる中心から離れた画像の移動であった。その後、レイアウトの密度の高い中央部分は、発散された。両ケースとも、結果として得られた位置分布は、図９ｃに示すように同様であった。ステップサイズを制御することによって、構造を損なうことなく共役勾配降下を使用することが可能となる。このステップサイズ制御を行わないと、得られた映像は劣っていたので、この制御は本方法の重要な側面である。
【０１５５】
さらに、閾値τを使用することによって、広い範囲のγ（例えば０．１〜１００）に影響されず、かつ異なる種類の関数ｆ（ｙｉ）（すなわち、ｙｉからＲまでのユークリッド距離の線形関数、および二乗関数）に影響されずに最適化を行うことができる。
【０１５６】
利用可能なレイアウト領域に対して画像数が多い場合の、画像を広げる能力を比較するために、さらなる実験を実施した。
【０１５７】
１０００個の画像の組を、カラーヒストグラムに自動的に配置した。Ｉｓｏｍａｐを用いた初期化後、画像をレイアウト領域にできるだけ広げるために、λを１に設定した。図１０は、結果として得られた１０００個の画像の配置を示す。本発明によるシステム（図１０ａ）では、最も均等な画像分布が得られ、画像密度はレイアウト領域にわたって実質的に一定であった。Ｍｏｇｈａｄｄａｍ他に基づく結果は、緊密な集まり（図１０ｂ）を示し、図１０ｃのＮｇｕｙｅｎ他の結果は、より均等な広がりを示したものの、画像密度に顕著なばらつきが見られた。
【０１５８】
図１１ａ〜１１ｄは、図１０に関して説明した諸技術の性能における差の簡略的な説明を示す。この例では、幅ｗ＝１．０の４つの正方形画像を、幅２．０、および高さ１．０の矩形領域に配置した。画像の位置のうち２つを固定し、したがってそれら２つの画像が共にその領域を占めることになる。原点は、レイアウト領域の底部左側隅であり、したがって画像は０．５および１．５の水平座標を有する。他の２つの画像を、一方がｕ（０．５≦ｕ≦１．５）にあるとき、他方が２．０にあるように、２つの固定画像間で反対称に動かす。図１１ａは、３つのｕ値についてこの実験の概略を示す。図１１ｂ〜１１ｄは、重なりの費用項の値を示す。本発明を用いた重なり費用は、４つの画像が、任意の画像と、その最近傍画像との距離がほぼ同じとなるように配置される場合、最小限に抑えられる。図１１ｂ、図１１ｃは、Ｍｏｇｈａｄｄａｍ他の方法での重なり費用が、２つの可動画像が２つの固定画像の真上に位置した場合に、最小限に抑えられることを示す。図１１ｄは、Ｎｇｕｙｅｎ他の方法での重なり費用が、可動画像が互いに僅かにだけ重なり合う場合に最小限に抑えられることを示す。
【０１５９】
図１２は、本発明、および従来技術によるＩｓｏｍａｐ技術を用いた、カラーヒストグラムに基づく１０００個の画像の映像を示す。パラメータγを１０に設定し、この方法では、（近傍近似せずに）反復当たり約１０秒かかった。Ｉｓｏｍａｐによる初期分布では（図１２ａ）、ほとんどの画像がレイアウトの中央付近に集まり、少しの画像が境界付近で不規則に分布していた。エントロピーに重点を置いた場合（λ＝１）、画像密度は、ほぼ一定になった（図１２ｂ）。ポイントをよりよく示すために、映像を、レイアウト中央付近の１つの画像周辺で拡大した。結果として得られた映像を図１２ｃおよび１２ｄに示す。拡大動作によって画像位置がスケーリング変更されているが、画像自体はスケーリング変更されていない。
【０１６０】
図１３は、本発明の実施形態を示すブロック図である。この例では、本発明は、コンピュータに搭載された一連のソフトウェアモジュールを備える。システム１０１は、マルチメディアデータ１０３を処理してレイアウト空間のレイアウト領域に最適化レイアウトを生成するオプティマイザ１０５を備え、また、このオプティマイザ１０５を用いて、ユーザの制御下で、表示装置上にレンダリングを生成することができる。
【０１６１】
ユーザは、項目内容を比較する際に使用する非類似度の概念（すなわち、マルチメディアデータを組織するために使用するコンセプト）に対して制御を有し、また、データの内容構造保存を、利用可能なレイアウト領域を使用すべき要件に対してトレードオフすべき範囲に対しても制御を有する。ユーザはまた、使用すべきレイアウト領域の寸法および形状を指定することができる。
【０１６２】
図１４は、本発明の実施形態のオプティマイザモジュールをより詳細に示す。オプティマイザモジュール１１０は、いくつかのサブモジュールを備える。イニシャライザモジュール１１９は、例えばＩｓｏｍａｐアルゴリズムを適用することによって、マルチメディアデータまたは項目１１１の初期レイアウトを生成する。検索エンジン１２３は、マルチメディア内容サブモジュール１１３、レイアウト分散サブモジュール１１５、およびレイアウト範囲サブモジュール１１７の３つによって計算されたレイアウト品質スコアを組み合わせた費用関数に基づいて最適レイアウトを検索する。マルチメディア内容サブモジュール１１３は、レイアウトによって内容構造が保存される範囲を測定するスコアを計算する。レイアウト分散サブモジュール１１５は、レイアウトのエントロピーを測定するスコアを計算する。レイアウト範囲サブモジュール１１７は、項目を１つのレイアウト領域または複数のレイアウト領域内に配置する制約が満たされる範囲を測定するスコアを計算する。コンバイナモジュール１２１は、これらのスコアを全体スコアに組み合わせ、検索エンジン１２３は、この全体スコアをレイアウト用の費用関数値として使用する。検索エンジン１２３は、最適化法を適用して、スコアすべきレイアウトを提案する。この検索エンジンは、レイアウトの提案およびスコアを数回反復した後、最適化レイアウト１２５を出力する。
【０１６３】
本発明の実施形態は、例えば、デジタル画像またはマルチメディアアイコンなどの検索可能な項目を表示装置上に配置する方法として存在することができ、その場合、本方法は、コンピューティング手段に搭載されたコンピュータプログラムの形を取ることができる。本発明はまた、本発明に従ってデジタル画像またはマルチメディアアイコンなどの検索可能な項目を表示装置上に配置するシステムを含むことができ、ハードウェアおよびソフトウェアの組合せを含むことができる。本発明のシステムおよび方法は、既存の画像閲覧ソフトウェアおよびハードウェアに組み込む、またはそれらと共に用いて、上述の形でそれらの性能を改善することができることが予期される。
【０１６４】
さらに、ブラウザは、ユーザがデータベースから項目を選択するタスクを実施することを可能とする装置となるであろう。本発明の装置またはシステムは、閲覧を含むことができ、ブラウザは、調査結果が示されることになる物理的な表示領域を指定することができる。
【０１６５】
使用に際しては、ブラウザは、最も近いマッチングを見つけるよう求められる、テキスト照会またはスケッチ照会による照会項目に基づいて、項目のデータベースの検索を開始することができるものである。
【０１６６】
さらに、検索は、データ組を代表し、したがってデータ組の概要を示す表示装置上の項目の組を用いて開始することができる。ユーザが閲覧し始める際、ユーザは捜しているものについての考えがほとんど、または全くない場合があり得る。ユーザは、インスピレーションを模索している場合もあろう。ユーザは、様々な基準に従ってレイアウトされた表示を介して閲覧するにつれて、関心のある項目に出会い、検索がより方向付けられることもあり得る。この場合、ユーザが項目空間を閲覧して、関心のある項目を効率良く見つけることに重点が置かれる。上記およびその他の場合において、項目が表示されるユーザインタフェースは、リアルタイムで応答し、ユーザとシステムとの間で閉ループの相互作用を形成しなければならない。
【０１６７】
本発明の範囲から逸脱せずに、本明細書に改善形態および改変形態を組み込むことができる。
【図１】
0005552495.tif 000024
【図２】
0005552495.tif 000025
【図３】
0005552495.tif 000026
【図４−１】
0005552495.tif 000027
【図４−２】
0005552495.tif 000028
【図５−１】
0005552495.tif 000029
【図５−２】
0005552495.tif 000030
【図６】
0005552495.tif 000031
【図７】
0005552495.tif 000032
【図８】
0005552495.tif 000033
【図９】
0005552495.tif 000034
【図１０】
0005552495.tif 000035
【図１１】
0005552495.tif 000036
【図１２】
0005552495.tif 000037
【図１３】
0005552495.tif 000038
【図１４】
0005552495.tif 000039