(57)【要約】  データ項目のグループを表す方法は、グループ内の複数のデータ項目のそれぞれについて、グループ内のデータ項目と複数の他のデータ項目のそれぞれとの類似度を求めること、及び類似度に基づいて各対にランクを割り当てることを含み、複数のデータ項目のそれぞれのランク付けされた類似度値は、グループ内のデータ項目の全体の相対類似度を反映するように関連付けられる。
2009509215.tif 000002
【特許請求の範囲】
【請求項１】
データ項目のグループを表す方法であって、
前記グループ内の複数のデータ項目のそれぞれについて、
そのグループ内で、前記データ項目と複数の他のデータ項目のそれぞれとの類似度を求めることと、
前記類似度に基づいて各対にランクを割り当てることと
を含み、
前記複数のデータ項目のそれぞれの前記ランク付けされた類似度値は、前記グループ内のデータ項目の全体の相対類似度を反映するように関連付けられる、データ項目のグループを表す方法。
【請求項２】
グループ内のデータ項目間のランク付けされた全体の相対類似度に基づいて、データ項目のグループを表す方法。
【請求項３】
データ項目と複数の他のデータ項目との類似度を求めることと、
少なくとも２つの追加のデータ項目のそれぞれと複数の他のデータ項目との類似度を求めることと、
前記類似度値をランク付けすることと、
前記少なくとも２つのデータ項目への類似度に基づいて、前記ランク付けされた全体の類似度値を使用することと
によって、前記グループ内のデータ項目のランク付けされた相対類似度を求めることを含む、請求項２に記載の方法。
【請求項４】
前記ランク付けされた類似度値は、前記グループ内のデータ項目の全体の相対類似度を反映する配列に配置される、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
行列配列を導き出すことを含み、
前記行列内のエントリはデータ項目間のランク付けされた類似度値に対応する、請求項１〜４のいずれか一項に記載の方法。
【請求項６】
前記行列のｉ番目の列及びｊ番目の行にあるエントリは、ｉ番目のデータ項目及びｊ番目のデータ項目の前記ランク付けされた類似度値に対応する、請求項５に記載の方法。
【請求項７】
行列配列を導き出すことを含み、
前記ｉ番目の列及び前記ｊ番目の行にあるエントリは、前記ｉ番目のデータ項目と前記ｊ番目のデータ項目との前記類似度に対応する、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
行内又は列内の前記類似度値をランク付けすることを含む、請求項７に記載の方法。
【請求項９】
ランク行列を対称化することを含む、請求項５、６、又は８のいずれか一項に記載の方法。
【請求項１０】
前記行列のエントリを閾値処理することを含む、請求項５〜９のいずれか一項に記載の方法。
【請求項１１】
データ項目の類似度は、データ項目の特徴に基づいて求められる、請求項１〜１０のいずれか一項に記載の方法。
【請求項１２】
データ項目の前記特徴は、
時間若しくはユーザが割り当てる値等のメタデータ、及び／又は、
色、テクスチャ等の固有の特徴
を含む、請求項１１に記載の方法。
【請求項１３】
複数の特徴のそれぞれの類似度を求めることを含む、請求項１〜１２のいずれか一項に記載の方法。
【請求項１４】
複数の特徴の類似度を結合したものを使用することを含む、請求項１３に記載の方法。
【請求項１５】
時間的特徴及び視覚的特徴を使用する、請求項１３又は１４に記載の方法。
【請求項１６】
複数の特徴についてランク行列を導き出して結合することを含む、請求項１３〜１５のいずれか一項に記載の方法。
【請求項１７】
複数の特徴について類似度行列を導き出して結合することを含む、請求項１３〜１５のいずれか一項に記載の方法。
【請求項１８】
前記データ項目を事前処理することを含み、
前記事前処理は、例えば、前記データ項目の部分集合を選択すること、前記データ項目をクラスタ化すること、又は前記データ項目をサブサンプリングすることによる、請求項１〜１７のいずれか一項に記載の方法。
【請求項１９】
データ項目を表す方法であって、
データ項目間の類似度を求めてランク付けすることを含み、
３つ以上のデータ項目の相対ランクを一緒に使用してさらに処理することを含む、データ項目を表す方法。
【請求項２０】
前記データ項目は画像を含む、請求項１〜１９のいずれか一項に記載の方法。
【請求項２１】
さらに処理することであって、データ項目の埋め込み、視覚化、クラスタ化等のさらに処理することを含む、請求項１〜２０のいずれか一項に記載の方法。
【請求項２２】
前記ランク付けされた全体の類似度値に基づいてデータ項目を空間内の点に写像することを含む、請求項２１に記載の方法。
【請求項２３】
データ項目を低次元空間、例えば、前記データ項目の表現次元よりも低い低次元空間に写像することを含む、請求項２２に記載の方法。
【請求項２４】
二次元空間に写像することを含む、請求項２３に記載の方法。
【請求項２５】
前記空間内の写像されたデータ項目間の距離は、データ項目の相対類似度に対応する、請求項２３〜２６のいずれか一項に記載の方法。
【請求項２６】
ラプラス固有写像技法を使用することを含む、請求項２２〜２５のいずれか一項に記載の方法。
【請求項２７】
データ項目に対応するシンボルを表示することを含む、請求項１〜２６のいずれか一項に記載の方法。
【請求項２８】
前記ディスプレイ内のシンボルの相対配置及び／又は位置は、データ項目のそれぞれの相対類似度に対応する、請求項２７に記載の方法。
【請求項２９】
新しいデータ項目を前記全体表現に追加又は射影することを含む、請求項１〜２８のいずれか一項に記載の方法。
【請求項３０】
時間的特徴及び視覚的特徴に基づいてデータ項目間の類似度を求めることを含む、データ項目を表す方法。
【請求項３１】
画像対間の類似度をランク付けする方法であって、
画像対間の類似度値を計算することと、
要素が対毎の類似度値を表す類似度行列を構築することと、
類似度行列値を分析することによりランク行列を計算すること
を含む、画像対間の類似度をランク付けする方法。
【請求項３２】
類似度行列値の列毎の分析により前記ランク行列を計算することをさらに含む、請求項３１に記載の方法。
【請求項３３】
前記ランク行列を対称にすることをさらに含む、請求項３１又は３２に記載の方法。
【請求項３４】
前記ランク行列を前記ランク行列の転置行列に加算すること、又は
主対角線に関して対称に配置されているランク要素間の最大値を計算すること
を含む、請求項３３に記載の方法。
【請求項３５】
前記ランク行列の低次元埋め込みにより、前記ランク行列に対して次元削減を行うことをさらに含む、請求項３１〜３４のいずれか一項に記載の方法。
【請求項３６】
ラプラス固有写像技法を使用して前記削減を行う、請求項３５に記載の方法。
【請求項３７】
請求項１〜３６のいずれか一項に記載の方法を含む、データ項目のグループ内のデータ項目同士の関係を求める方法。
【請求項３８】
請求項１〜３７のいずれか一項に記載の方法を使用することであって、例えば、埋め込み、視覚化、クラスタ化、検索、及び閲覧に使用すること。
【請求項３９】
請求項１〜３８のいずれか一項に記載の方法を実行するようにプログラムされる制御装置。
【請求項４０】
請求項１〜３８のいずれか一項に記載の方法を実行するようになっている装置。
【請求項４１】
請求項１〜３８のいずれか一項に記載の方法を実行するように構成されるプロセッサと、
表示手段と、
選択手段と、
データ項目を記憶する記憶装置と
を備える装置。
【請求項４２】
請求項１〜３８のいずれか一項に記載の方法を実行するためのコンピュータプログラム、又は、このようなコンピュータプログラムを記憶するコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ項目、特に画像コレクションの効率的な表現に関する。本発明は、特に、画像内容の数学的記述を抽出することができる画像コレクションの中でのナビゲーションに関する。その理由は、画像コレクションのようなデータベースにおいては自動アルゴリズムを使用してデータの解析、編成、検索、及び閲覧が可能であるためである。デジタル画像コレクションは、専門的な場及び消費者の場の両方でますます一般的になりつつある。技術の進歩により、デジタル画像の取り込み、格納、及び伝送がかつてないほどに安価且つ容易になった。これにより、ユーザがこのようなコレクションと効率的に対話できるようにする新しい方法に対する必要性が生まれた。
【０００２】
画像データベースを照会する方法がいくつか知られている。例えば、米国特許第６２４０４２３号明細書には、照会の結果が領域ベースの画像マッチングと境界ベースの画像マッチングとの組み合わせに基づく、１つのこのような方法が開示されている。
【０００３】
特に、初心者ユーザの場合、このような大量のデータに関連する直観的な方法を見つけることが難しい。例えば、大半の消費者は、写真プリント紙を物理的に編成してアルバムに入れることには慣れているが、その具体的な相互作用は、パーソナルコンピュータ、カメラ付き携帯電話、又はデジタルカメラのメモリ内のデジタル写真コレクションの場合ではもはや不可能である。当初、コレクションをナビゲートする電子的な方法は、この物理的で具体的な保存経験を擬似的に模倣することに重点を置いた。
【０００４】
Wang他（米国特許第６０２８６０３号明細書）は、ページ内の画像の配置を定義する情報を有する１つ又は複数のページから成る写真アルバムのようなフォーマットで画像を提示する手段を提供している。順序及び配置は、ユーザのドラッグアンドドロップ操作で変更することができる。
【０００５】
別の簡便な方法が、画像を重なったスタック表示で提示するGargi（米国特許出願公開第２００２／０１４０７４６号明細書）からもたらされる。マウスが配置された画像が表示される。ユーザにとって、これはテーブル上の山になった写真の中から写真を選ぶことに似ている。
【０００６】
ユーザが画像コレクションを手作業で編成する場合、通常、構造に何等かの意義がある。換言すれば、写真アルバムの配置にはユーザにとって何らかの「意味」がある。これは、画像に関連するイベント、人々、又は感情に関連するか、又は例えば、ストーリーを物語り得る。いくつかの電子的ナビゲーションツールは、ユーザが画像にラベルをつけるか又はグループ化できるようにすることで、この構造を模倣して利用しようとする。カテゴリ又はグループ化に対する提案を自動的に行うものさえある。
【０００７】
Mojsilovic他（米国特許出願公開第２００３／０１２３７３７号明細書）は、知覚的実験から導き出される意味的特徴に基づいてデジタル画像コレクションの閲覧、検索、照会、及び視覚化を行う方法を開示している。Mojsilovic他は、この「完全な特徴セット」に基づいて２つの画像の意味的類似性を比較する測定基準を定義すると共に、各画像に意味的カテゴリを割り当てる方法も定義している。
【０００８】
Rosenzweig他（米国特許出願公開第２００２／００７５３２２号明細書）は、画像グループがそのグループのサイズに比例するサイズを有するアイコンで表される、閲覧及び検索のためのタイムラインベースのグラフィカルユーザインタフェース（ＧＵＩ）を提案している。階層システムは、ユーザがアイコンをアクティブ化することによって動作し、アイコンのアクティブ化により、最初のレベルよりも区別の細かいさらなる階層レベルがトリガされる。システムは、例えば、ロケーション、人物、イベントを識別する、画像ファイルに記憶されている各種メタデータも復号して、（相互に排他的な）グループを導き出す。最終レベル／ビューにおいてアイコンをアクティブ化することによって、含まれている画像が表示される。
【０００９】
Stavely他（米国特許出願公開第２００３／００８６０１２号明細書）は、画像閲覧のための別のユーザインタフェースを記載している。上下入力コントロールと左右入力コントロールとの単純な組み合わせを使用して、各グループに「好ましい」画像を持たせることによりグループ内の画像又はグループ間の画像を閲覧できるようにする。
【００１０】
Anderson（米国特許第６５３８６９８号明細書）は、各種カテゴリ基準による画像のソート及びグループ化に頼って検索し閲覧するシステムを詳述している。
【００１１】
ユーザは、写真プリントでは可能な物理的な相互作用を、デジタルライブラリでは行うことができないが、デジタルライブラリは、特に、内容の自動解析に関わる有用な新機能を可能にする。複数の方法で、画像を特徴付ける「特徴」を抽出することができる。画像に存在する形状、テクスチャ、及び色（例えば）はすべて、数値特徴で記述することができ、こういった属性により画像の比較及び索引付けが可能になる。
【００１２】
上述した自動カテゴリ割り当ては、これにより可能になる種類の機能の単なる一例にすぎない。また、画像を定量的に比較できることで、データベース全体の構造を取り込んで表現する可能性も開かれる。ユーザは、写真アルバムの編成に取り掛かるときに構造を付与しようとすることが多いため、これは魅力的なアイディアである。コレクション中の画像が固有の構造を有する場合、それはおそらくユーザの開始点として有用であろう。ユーザは構造を学習して利用又は変更することができるため、検索及び閲覧もより効率的に行うことができる。
【００１３】
本発明の方法は、画像対の類似度を解析することにより画像データベースの構造を自動的に発見する。次に、この構造を、ユーザがインタラクティブにナビゲートすることができる二次元プロットで表現することを含む複数の方法で利用することができる。
【００１４】
純粋に表現のため（例えば、主成分分析（ＰＣＡ））であるか、分類のため（例えば、線形判別分析(Linear Discriminant Analysis（ＬＤＡ））であるか、それとも視覚化のため（例えば、ラプラス固有写像、多次元スケーリング（ＭＤＳ）、局所性保存射影(Locality Preserving Projection)（ＬＰＰ）、及び自己組織化写像（ＳＯＭ））であるかに関わらず、高次元空間から低次元空間へのデータの射影に関わる様々な方法が文献から知られている。本発明の文脈の中では、対毎の比較の行列を入力とするアルゴリズムが特に興味深い。多くの特徴がある場合、数値データはデカルト空間内の点として単純に解釈することはできず、通常、特定の距離測定基準を使用しての比較のみが適切である。このため、ベクトルデータに対して直接働くアルゴリズムの、本発明の目的での有用性は劣る。類似度ベースの技法は、ＭＤＳ、ＳＯＭ、及びラプラス固有写像を含む。これらはすべて、各類似度測定基準を最良に反映するデータの低次元射影を作成する（「最良」は何らかの費用関数により決められる）。
【００１５】
Rising（米国特許第６７２１７５９号明細書）は、画像の階層ＭＤＳデータベースのためのプロセスを記載している。これは、構造を照会し更新する方法と共に、特徴検出器を使用して画像集合の類似度を測定することに基づく。表現を構築するために、ＭＤＳが最上位レベルで、「制御点」と呼ばれる画像の部分集合に対して行われる。これらの点は、データ点の凸包(convex hull)を近似するように、すなわち、画像に存在するバリエーションを完全に表すように選択される。残りの点は、制御点に対する相対的な位置で初期化され、全体集合が、部分セットをそれぞれ表す複数の「ノード」に分けられる。次に、ＭＤＳが各ノードに対して実行されて、各ノード内の画像の配列を改良する。この方法は、階層ツリーの効率的な側面を利用して、反復最適化アルゴリズムであるＭＤＳ計算の計算負担を低減する。
【００１６】
Trepess及びThorpeの方法（欧州特許出願公開第１４２６８８２号明細書）は、ＳＯＭを使用して、データの写像表現を作成する。次に、階層的クラスタ化が構築されて、ナビゲーション及び表示を容易にする。クラスタは、各種の特徴付け情報（ラベル）で区別することができ、クラスタ化された構造から自動的に導き出すことができる。用途は主にテキスト文書に向けてであるが、この方法自体は汎用的である。或る意味で、この方法はRisingの研究を鏡に映したものであり、Risingの方法はデータを各レベルでクラスタ化し、それから写像を行うのに対して、Trepess及びThorpeはまず写像を計算し（大域的に）、それから写像を使用して階層を構築する。
【００１７】
Jain及びSantini（米国特許第６１２１９６９号明細書）は、画像データベースの照会結果を視覚化する方法を提示する。結果は三次元空間で表示され、三次元空間の軸はＮ次元の集合から任意に選択される。これらは、照会画像とデータベース画像との類似度の各種測定に対応する。空間を移動することによる視覚的なナビゲーションが提案され、ユーザに動力学的経験ならびに視覚的な経験を提供する。この方法は、画像コレクションの類似度構造を最適に取り込もうとするのではなく、ユーザが選んだ照会画像に対するコレクションの類似度を表すため、先の２つの例と異なる。複数の次元が発生するのは、画像の複数の相互類似度からではなく、類似度の複数の測定基準からである。
【００１８】
すぐに分かるように、本発明の背後にある主要概念の１つは、類似度構造ではなくランク構造が、画像データベースを表現して編成する際に維持されるべき重要な特性であることである。ランクを使用してクラスタ化をガイドすることは、例えば、Novak他（J. Novak, P. Raghavan、及びA. Tomkins「Anti-aliasing on the web」（Proc. International World Wide Web Conference, pages. 30-39, 2004））及びFang（F. M. Fang「An Analytical Study on Image Databases」（Master's Thesis, MIT, June 1997））により文献でちらりと触れられてきた。これらの研究はいずれも、オブジェクトｉおよびｊの相互ランクを、ｊに相対するｉのランクと、ｉに相対するｊのランクとの和として定義する。
【００１９】
しかし、この種類の測定の最大の可能性は利用されていない。特に、上述した研究はクラスタ化のみを考慮し、次に、分離した状態で各対毎での相互ランク比較を処理し、局所的で「欲張り」な様式で判断を下すだけである。新規の大域的ランクベースの測定を使用して表現をガイドすることが、構造を明らかにする強力なツールであることが分かる。
【００２０】
従来技術による各方法は、本発明により対処される以下のような欠点を有する。
【００２１】
単純な閲覧方法は、画像コレクションの構造を利用せず、構造を良好に表しもしない。
【００２２】
分類に基づく方法は、これを部分的に解決することができる。利用できる特徴情報を利用し始めるが、離散的かつ多くの場合に排他的であるクラスラベルの割り当てのため、柔軟性がない。また、信頼性の高い自動分類は実現が難しいことで悪名が高い。
【００２３】
より複雑な方法は類似度を考慮して類似度を表すことができるが、現在までのところ、絶対的な比較を取り込むにすぎない。本方法は、コレクション全体のコンテキストの中で画像間の相対的な関係を取り込む。
【００２４】
また、従来技術に欠けているのは、時間的及び視覚的両方の類似度の合同測定値(joint measure)を計算して表現に埋め込むという概念である。このようにして時間と外観を統合することにより、ユーザが結果としての配置を解釈し易くすることを含め、視覚化に有利な性質が提供される。
【００２５】
本発明の態様は特許請求の範囲に記載される。本発明は、装置を使用してデータ項目に対応する信号を処理することによりデータ項目に関係する。本発明は、主に、画像に関係する。本発明の用途についてのさらなる詳細が、同時係属中の欧州特許出願第０５２５５０３３号明細書に見られる。
【００２６】
本発明の一態様は、類似度の絶対的な測定ではなく相対的な関係が、画像コレクションの構造をコンパクトに表す際に維持されるべき重要な特性であるということである。このため、相互ランク行列を、数学的に分析できる形態でデータの構造を符号化するのに適正な方法として定義する。この行列内のエントリは、より広いコレクションのコンテキストの中での画像対の比較を表す。数学的分析は、この情報に基づく画像のグループ化（クラスタ化）又は構造の最も重要な側面を保持するコンパクト表現への情報の射影から成ることができる。
【００２７】
第２の関連する態様は、この構造が、相互ランク測定が分離されてではなく全体的に考慮される場合、すなわち、処理が相互ランクを局所的（対毎）にではなく大域的に見る場合に、最も効率的に取り込まれることである。
【００２８】
第３の態様は、時間的情報及び視覚的情報が両方とも、コレクション内の画像のコンテキストを判断するに当たって等しく有用なことである。これは、比較を測定する際に、時間が別個の、又は独立した数量として扱われないことを意味する。したがって、その結果得られるクラスタ又は視覚表現は、視覚的類似度及び時間的な近接度をまとめて表すことができる空間内に形成される。
【００２９】
本発明の実施形態について添付図面を参照して説明する。
【００３０】
画像検索タスクの文脈におけるありふれた方法の一つは、照会に対する（或る意味での）類似度で並べられた、ランク付けされた結果のリストを表す方法である。これは、照会画像に対するデータベース内の画像の関係を良好に取り込む。好ましくは、ユーザが関心のある画像をランク付きリストの最上部付近で見つけ、関係のない画像は底部に押しやられているというのがアイデアである。本発明は、データベース内の画像間の相互関係をすべて取り込んで視覚化することを目的としてこの概念を拡張する。
【００３１】
本方法の一実施形態は、画像を分析し、特徴を比較し、１組の相互ランク行列を生成し、これらを結合し、固有値問題を解くことにより写像された表現を計算するシステムである。このプロセスを図１のフローチャートに示す。
【００３２】
別の実施形態を図２に示す。図２では、第１の実施形態では相互ランク行列に対して実行された結合ステップが、ここでは特徴類似度に対して実行される。図３は、いくつかの結合が早い段階で実行され、残りが後の段階で実行される第３の実施形態を示す。様々な特徴からのデータをいつ融合させるかの選択は、本発明の概念から独立している。むしろ、それは特定の実施態様の詳細である。当業者には明らかなように、選択は、複雑性、特徴（次元）数、及び独立の程度(degree of independence)等の要因により決めることができる。この説明の残りの部分では、一般性を失うことなく、図１に示すシーケンスに的を絞る。
【００３３】
このようなシステムでの最初のステップは、画像及び任意の関連付けられたメタデータからいくつかの記述的な特徴を抽出することである。特徴は、例えば、ＭＰＥＧ−７規格ＩＳＯ／ＩＥＣ１５９３８−３「Information technology -- Multimedia content description interface -- Part 3: Visual」に述べられているように、画像の色、テクスチャ、構造特性、又は他の任意の視覚的性質を記述するＭＰＥＧ−７視覚記述子であることができる。例えば、第１の画像の色記述子は、所与の色空間での画像の平均色の位置を示し得る。次に、第２の画像の対応する色記述子を第１の画像の色記述子と比較して、所与の色空間での分離距離、ひいては第１の画像と第２の画像との類似度の数量的評価を提供することができる。
【００３４】
換言すれば、例えば、第１の平均色値（ａ１，ｂ１，ｃ１）が、単純な距離測定値すなわち類似度値Ｓを使用して第２の平均色値（ａ２，ｂ２，ｃ２）と比較される。但し、
Ｓ＝［ａ１−ａ２］＋［ｂ１−ｂ２］＋［ｃ１−ｃ２］
である。
【００３５】
時間はメタデータの中で最も重要な要素であるが、他の情報も、ユーザが供給するか、それとも自動的に生成されるかに関わらず組み込むことができる。この及び他の方法で時間的情報を視覚的情報と結合する例が、Cooper他「Temporal event clustering for digital photo collections」（Proc. 11th ACM International conference on Multimedia, pp.364-373, 2003）に見られる。
【００３６】
記述的特徴に対する唯一の制約は、画像同士を比較して類似度値を生成できるようにするということである。米国特許第６２４０４２３号明細書には、画像同士の類似度値を計算する例が開示されている。ＭＥＰＧ−７規格自体は、記述子及び関連する類似度測定値の両方を定義している。しかし、好ましくは、特徴は画像内容のいくつかの人間にとって意味のある特性も取り込む。
【００３７】
第２のステップは、記述的特徴を使用して画像のクロスマッチングを行うことである。記述的特徴及び関連付けられる類似度測定値の多くの例が周知である。例えば、欧州特許出願公開第１１７３８２７号明細書、欧州特許出願公開第１１８３６２４号明細書、英国特許出願公開第２３５１８２６号明細書、英国特許出願公開第２３５２０７５号明細書、英国特許出願公開第２３５２０７６号明細書参照。
【００３８】
同様に、記述的スカラー値又はベクトル値（すなわち、特徴ベクトル）を導き出す多くの周知の技法がある。これらの記述的スカラー値又はベクトル値は、スカラー値又はベクトル値（単純な距離測定値等）の類似度を求めるために、多くの周知の技法を使用して比較することができる。
【００３９】
これは、各特徴Ｆ毎に、対毎類似度ＳＦの行列をもたらす。各エントリＳＦ（ｉ，ｊ）は、問題となっている特徴Ｆの画像ｉと画像ｊとの類似度である。したがって、通常、この行列は対称である。行列は、例えば、非対称の類似度測定値が使用される場合には対称ではない。すべての画像がクロスマッチングに含まれてもよく、又はその部分集合が含まれてもよい。例えば、事前に画像をクラスタ化し、各クラスタから１つだけの画像を処理して、複雑性及び冗長性を低減することができる。これは、多くの従来技術によるアルゴリズム、例えば、ｋ最近傍法、凝集併合（agglomerative merging）、及び他の任意のものを使用して実現することができる。
【００４０】
第３のステップは、類似度行列ＳＦをランク行列ＲＦに変換することである。各列が独立して処理され、類似度値が或るランク順序値で置き換えられる。換言すれば、各ｉ毎に、最大類似度ＳＦ（ｉ，ｊ）が、例えば、Ｎ（ここで、Ｎは集合内の画像数である）で置き換えられ、２番目に最も大きな類似度がＮ−１で置き換えられ、３番目に最も大きな類似度がＮ−２で置き換えられ、以下同様である。このステップ後、ｊに対する画像ｉのランクはｉに対するｊのランクと同じではないため、行列はもはや対称でなくなる。このステップの副作用は、任意の画像を照会する検索結果を事前に計算していることである。これがランク順序情報を保存する唯一の方法ではないことに留意されたい。一般に、このステップは、データ依存・非線形・単調性の、類似度の変換として見ることができる。このような変換はいずれも、本発明の範囲内にあるものとして見ることができる。
【００４１】
ランク行列をさらに処理することが有利であるが、必ずしもそうする必要はない。例えば、閾値を適用して、偽性の(spurious)情報を除去することができる。多くの特徴では、或るカットオフポイントを超えるランク値は無意味になる。画像は単純に「類似せず」、減少するランク値を保持することは無駄である。しかし、時間はこれが当てはまらない一特徴である。時間差及びランクはすべての画像にわたって一貫しているため、通常、この特徴のランク行列は閾値処理されない。
【００４２】
第４のステップは、各特徴毎に、ランク行列を対称化することである。このために、ランク行列に対して作用する、任意の、線形又は非線形の、代数的又は統計的な関数を使用することができる。一実施形態では、ランク行列がその転置行列に加算され、相互ランク行列の一実施形態：
ＭＦ＝ＲＦ＋ＲＦＴ
が与えられる。
【００４３】
この行列内で、各エントリは、画像コレクションというより広いコンテキストを考えての画像ｉと画像ｊとの相対類似度を符号化する。ＭＦが対称であることに留意されたい。適当な対称化の別の例は、単純に最大：
ＭＦ（ｉ，ｊ）＝ｍａｘ｛ＲＦ（ｉ，ｊ），ＲＦ（ｊ，ｉ）｝
を選択することである。
【００４４】
第５のステップは、この複数の行列ＭＦを、相互ランクスコアの単一の大域行列Ｍに結合することである。これを実現する多くの可能な方法がある。一実施形態では、ＭＦが重み付けされて加算される。システムが重みを判断するいくつかの手段を含んでもよく、又は重みを設計で固定してもよい。特徴をシステムのより早い段階で結合すべき場合（先に考察され、図２及び図３に示される）でも、同じ広範囲の結合方法が可能である。
【００４５】
この段階で、データベースの構造についての豊富な情報源である行列Ｍを、クラスタ化及び／又は表現を行う従来技術によるいくつかのアルゴリズムで分析することができる。例えば、相互ランクが低い画像対を、凝集的クラスタ化プロセスで繰り返し併合することができる。
【００４６】
より有用なことには、行列Ｍを「大域」的に分析して、相互ランク測定値のいくつか（又はすべても可能）を同時に考慮することができる。これは、個々の測定値（行列エントリ）でのノイズに対する表現に対する敏感性を低減すると共に、データの性質の大半(bulk properties)をよりよく取り込む。文献から既知のスペクトルクラスタ化法がこの種類の処理の一例であるが、他の任意の非局所的な方法も適当であることが当業者には明らかであろう。
【００４７】
好ましい実施形態では、相互ランク行列は、ラプラス固有写像法により低次元空間に埋め込まれる。次元は、視覚化するために好ましくは２であるが、これよりも高くても低くてもよい。別法として、任意の数の次元をクラスタ化に使用することができる。埋め込みを行うのに他の方法も可能である。ラプラス固有写像法は、空間内の距離がＭ内のエントリに対応するように、画像を空間内の点として埋め込もうとする。すなわち、相互ランク値が大きい画像対ほど互いに近く、相互ランクの小さい画像対ほど離れる。
【００４８】
これを実現することで、固有値問題である以下の式：
（Ｄ−Ｍ）ｘ＝λＤｘ
がもたらされる。式中、Ｄは、Ｍの行を加算すること：
【００４９】
【数１】
2009509215.tif 000003
【００５０】
により形成される対角行列である。この式の解により、相互ランク類似度空間内の画像の座標であるＮ個の固有ベクトルｘがもたらされる。コレクションの構造を取り込むに当たっての各ベクトル（次元）の重要性は、対応する固有値により示される。これにより、視覚化、ナビゲーション、及びクラスタ化に最も重要な、数少ない次元を選択することが可能になる。
【００５１】
上記方法を使用して導き出された二次元空間内のデータ項目の集合が写像された画像の例示を図４に示す。より具体的には、図４は、シンボル（点又はドット）が、ここでは画像であるデータ項目に対応する、ディスプレイ１２０上のシンボリック表現空間を示す。
【００５２】
ディスプレイ内のシンボルの配置（すなわち、シンボルの相対的位置およびシンボル間の距離）は、データ項目の特徴（平均色等）の１つ又は複数に基づく、対応するデータ項目の類似度を反映する。
【００５３】
ユーザは、ポインティングデバイス１３０を使用して、表現空間１０全体を通してカーソル２５０を動かすことができる。カーソルの位置に応じて、１つ又は複数の画像（サムネイル）２７０が、各シンボル２６０（複数可）のカーソルへの近接度に基づいて表示される。この方法及び関連する方法のさらなる詳細が、「Method and apparatus for accessing data using a symbolic representation space」と題する同時係属中の欧州特許出願第０５２５５０３３号明細書に記載されており、これを参照により本明細書に援用する。
【００５４】
変更形態及び代替形態を以下に考察する。
【００５５】
相互ランク行列を計算する場合に画像の部分集合を選択することが可能である。これは、行列のサイズを低減すると共に、計算の負担を低減する。この場合、初期部分集合には存在しない、画像の出力空間内の位置を求めることが望まれる。これらはより大きなコレクションの残りであってもよく、又は追加された新しい画像であってもよい。上記実施形態によれば、新しい画像が存在する場合には画像の相対ランクが変化するので、追加の行及び列を相互ランク行列に追加すると共に、既存のエントリを変更する必要がある。次に、写像を完全に再計算する。しかし、出力空間内の既存の画像の位置を変更せずに、この手順を近似することが可能である。Bengio他（Y. Bengio、P. Vincent、J.-F. Paiement、O. Delalleau、M. Ouimet、及びN. Le Roux著「Spectral Clustering and Kernel PCA are Learning Eigenfunctions」（Technical Report 1239, Departement d'Informatique et Recherche Operationnelle, Centre de Recherches Mathematiques, Universite de Montreal））が、追加の点をラプラス固有写像に追加し、新しいデータを元の分解により与えられる次元に射影するこのような方法を提供している。これは、サブサンプリングされた相互ランク類似度空間の効率的な実施に役立つ。
【００５６】
第２に、数学的枠組みの構造は、追加の情報を表現に組み込むことを想像しやすいようなものである。例えば、ユーザ注釈又は他のラベル情報を使用して、異なる表現を作成することができる（例えば、ＬＤＡ又は一般判別分析(General Discriminant Analysis)（ＧＤＡ）を介して）。これらは、ラベル付けされたクラス間及びクラス内の構造及び関係をよりよく表す。また、新しい画像がデータベースに追加されるときに、新しい画像へのクラス割り当てを提案するために使用することもできる。この変更は数学的分析に対してのみであり、相互ランク行列の構造（construction）は同じままである。変更されたシステムの出力（埋め込み）は、画像同士の視覚的関係及び時間的関係についての結合された情報ならびにそれらのクラス属性を含む。
【００５７】
ユーザがナビゲートしたい可能性がある画像又は映像（ありふれた方法としては、キーフレーム又は他を介して）の任意のコレクションに対して本方法が可能である。同等に、データベースレコード／データ項目は、画像及び視覚的類似度測定値に関係しなくてもよく、オーディオクリップ及び対応する類似度測定値等の他の任意の分野に関係してもよい。例えば、ＭＰＥＧ−７規格は音声の記述子を記載している（ＩＳＯ／ＩＥＣ１５９３８−４「Information technology -- Multimedia content description interface -- Part 4: Audio」）。２つのクリップの音声メタデータを比較して、定量的な類似度測定値を提供することができる。開始点として適当な類似度測定値があれば、テキスト文書を処理することもできる。テキスト文書の類似度を測定する方法は、Novak他（上記参照）により開示される。この分野には、当分野において既知の方法である潜在的意味インデキシング（ＬＳＩ）等の専門の技法がすでにある。画像以外のデータ項目の記述値を抽出し、このような記述値を比較して類似度測定値を導き出す様々な技法が周知であり、本明細書ではこれ以上は説明しない。
【００５８】
本発明は、特定の記述値又は類似度測定値にも制限されず、従来技術又は本明細書において述べられているような任意の適した記述値又は類似度測定値（複数可）を使用することが可能である。純粋に一例として、記述的特徴は、例えば、欧州特許出願公開第１１７３８２７号明細書に記載のような色値及び対応する類似度測定値であってもよく、又は、例えば、英国特許出願公開第２３５１８２６号明細書又は英国特許出願公開第２３５２０７５号明細書に記載のようなオブジェクトの輪郭及び対応して測定される類似度であってもよい。
【００５９】
本明細書では、「画像」なる用語は、フィルタリング、解像度変更、アップサンプリング、ダウンサンプリング等の処理後を含む画像ユニットを記述するために使用されるが、この用語は、フレーム、フィールド、ピクチャ等の他の同様の用語にも適用され、また、画像やフレームのサブユニット若しくは領域等の他の同様の用語にも適用される。ピクセル及びブロック又はピクセルグループなる用語は、適当な場合には同じ意味で使用することができる。本明細書では、「画像」なる用語は、文脈から明らかな場合を除き、画像全体又は画像の或る領域を意味する。同様に、画像の或る領域は全体全体を意味し得る。画像はフレーム又はフィールドを含み、静止画像又はフィルム若しくは映像等の画像シーケンス内の画像、又は画像の関連付けられたグループに関連する。
【００６０】
画像は、グレースケール画像、カラー画像、別の種類のマルチスペクトル画像、例えば、ＩＲ、ＵＶ、又は他の電磁画像、又は音響画像等であることができる。
【００６１】
「選択手段」なる用語は、例えば、ナビゲーションボタン及び選択ボタンを含むコントローラ等の、選択のためにユーザにより制御される装置及び／又はポインタ若しくはカーソル等によるディスプレイ上のコントローラの表現を意味することができる。
【００６２】
好ましくは、本発明は、適した装置を使用して電子的な形態で表されるデータ項目を処理し、電気信号を処理することにより実施される。本発明は、例えば、適したソフトウェア及び／又はハードウェアの変更が行われたコンピュータシステムで実施することができる。例えば、本発明は、コンピュータ、又は類似のものを使用して実施することができる。このコンピュータ又は類似のものとは、プロセッサ若しくは制御装置等の制御手段若しくは処理手段、メモリ、磁気記憶装置、ＣＤ、ＤＶＤ等の画像記憶手段を含むデータ記憶手段、ディスプレイ、モニタ、若しくはプリンタ等のデータ出力手段、キーボード等のデータ入力手段、及びスキャナ等の画像入力手段、又は追加の構成要素と共にこのような構成要素の任意の組み合わせを有する。本発明の態様は、ソフトウェア形態及び／又はハードウェア形態、又は特定用途向け装置で提供してもよく、又はチップ等の特定用途向けモジュールを提供してもよい。本発明の一実施形態による装置内のシステム構成要素は、例えば、インターネットを介して他の構成要素と離れて設けられてもよい。
【図面の簡単な説明】
【００６３】
【図１】第１の実施形態の流れ図である。
【図２】第２の実施形態の流れ図である。
【図３】第３の実施形態の流れ図である。
【図４】閲覧装置を示す。
【図１】
2009509215.tif 000004
【図２】
2009509215.tif 000005
【図３】
2009509215.tif 000006
【図４】
2009509215.tif 000007
【国際調査報告】
2009509215.tif 000008
2009509215.tif 000009
2009509215.tif 000010