(57)【特許請求の範囲】
【請求項１】
１つまたは複数の画像に対するクエリに応答する方法であって、
カメラで画像を取り込み、プロセッサを使用し、索引付け戦略を適用して画像を、個別の単一の画像ではなく小さなグループであるグループレットとして処理することと、
各々が画像層内の１つまたは複数の画像に関連付けられている、グループ層を有する２層索引付け構造を生成することと、
前記画像を２つ以上のグループに相互参照索引付けすることと、
相互参照索引付けされた画像および前記グループレットを用いて、ある画像と他の画像との略重複した画像を検索することとを含む方法。
【請求項２】
２層索引付け構造を生成することは、３つの異なる種類の情報を使用してグループを構築すること含む請求項１に記載の方法。
【請求項３】
情報の前記種類は、局所的特徴類似性、領域類似性、および大域的高水準特徴類似性を含む請求項２に記載の方法。
【請求項４】
前記クエリの中で前記クエリの画像から局所的特徴を抽出することを含む請求項１に記載の方法。
【請求項５】
各ディスクリプタを使用し、ディスクリプタグループ索引付けを介して対応するグループを検索することを含む請求項４に記載の方法。
【請求項６】
前記画像をグループに索引付けたものによって１つまたは複数の画像を見つけることを含む請求項５に記載の方法。
【請求項７】
データベース内の画像のスコアを生成することと、前記画像が複数のディスクリプタによって検索される場合に前記検索される画像のスコアを集計することとを含む請求項１に記載の方法。
【請求項８】
複数のグループ内の各画像を、グループマッピングに対する相互接続された画像として決定することを含む請求項１に記載の方法。
【請求項９】
画像が１つ以下のグループに属している場合に、グループ内のすべての画像は、全く同じ検索スコアを有する請求項８に記載の方法。
【請求項１０】
複数のグループが１つの画像に対するスコアを投票することを可能にすることと、２つの画像に対する異なる検索スコアを、それらの画像が同じグループ内にあるとしても生成することとを含む請求項１に記載の方法。
【請求項１１】
逆索引を使用した高速なグループ検索にグループ層索引を適用することを含む請求項１に記載の方法。
【請求項１２】
語彙ツリー構造を使用してディスクリプタとグループＩＤとを対応付けた第１の層ディスクリプタ索引付けを実行することを含む請求項１に記載の方法。
【請求項１３】
探索されたグループから画像を検索することを可能にする第２の画像層索引を生成することを含む請求項１に記載の方法。
【請求項１４】
グループ構築処理において画像層索引を取得することを含む請求項１に記載の方法。
【請求項１５】
画像ディスクリプタおよびグループ識別対応関係を符号化するグループ層索引を生成することを含む請求項１に記載の方法。
【請求項１６】
画像およびグループ対応関係を符号化する画像層索引付けを生成することを含む請求項１に記載の方法。
【請求項１７】
局所的特徴類似性は、画像間の局所的コンテンツ類似性をモデル化する請求項１に記載の方法。
【請求項１８】
２つの画像の間の意味論的意味類似性を測定する意味類似性を生成することを含む請求項１に記載の方法。
【請求項１９】
ＳＩＦＴディスクリプタを抽出し視覚的単語に量子化し、
【数１】
0006279771.tif 000031
を使用してＴＦ−ＩＤＦ類似性を計算し、
ここで、ＩＤＦ（ｖ）は、視覚的単語ｖの文献出現頻度の逆数であり、ＴＦｄ＿ｉ（ｖ）は、ディスクリプタｉの語出現頻度であり、ＴＦＧａは、グループレットの語出現頻度であり、ｓｉｍ（ｄｉ，Ｇａ）＄は、ｄｉとＧａとの間の類似性である、ことと、
類似の局所ディスクリプタを前記クエリと共有するグループレットを取得することと、
画像索引に記録されている前記グループレットの画像関係に従って、グループレットを単一の画像のリストにアンパックし、ここにおいて、クエリｑとデータベース画像ｄｉとの間の類似性はｑ、およびｄｉを含むグループレットの類似性を投票することによって決定される、こととを含む請求項１に記載の方法。
【請求項２０】
冗長なグループレットを取り除き、逆ファイル索引付けを実行してグループレット索引を構築することと、
視覚的単語の語彙ツリーにより局所ディスクリプタを抽出し、局所ディスクリプタを視覚的単語に符号化し、次いで、グループレットのＴＦ（語出現頻度）ベクトルを計算することと、
ただ１つの画像を含むグループレットについては、Ｌ−１正規化視覚的単語ヒストグラムを前記ＴＦベクトルとして決定することと、
複数の画像含むグループレットについて、各画像のＴＦベクトルを決定し、次いで、グループレット
【数２】
0006279771.tif 000032
について、Ｇ内の視覚的単語ｖのＴＦ値が
【数３】
0006279771.tif 000033
として計算される最大プーリング戦略を適用し、
ここで、ＴＦｉは、データベース画像ｄｉのＬ−１正規化ＴＦベクトルを表している、こととを含む請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願情報
本出願は、参照により本明細書に組み込まれている、２０１４年３月６日に出願した仮特許出願第６１９４８９０３号および２０１４年７月３０日に出願した仮出願第６２０３０６７７号の優先権を主張するものである。
【背景技術】
【０００２】
画像検索は、３つの重要な手順、すなわち、特徴抽出、オフライン索引付け、およびオンライン検索を含む。３つの手順のうち、オフライン索引付けは、関連する画像を一緒に組織化して冗長性を排除し、オンライン検索時に画像をアクセスすることをしやすくする。したがって、索引付け戦略は、検索の精度、時間、およびメモリコストに大きく影響する。現今では、適切な画像特徴を抽出すること、および精度の高いオンライン検索アルゴリズムを設計することに焦点を当てた研究が大量に公開されているが、適切な索引付け戦略に対する取り組みは、比較的限られている。
【０００３】
他の研究では、逆索引を使用してデータベース内の画像ＩＤに索引を付ける。索引付けは、画像毎に行われる。他の研究は、データベース画像内の相関を広範に調査することもしていない。これらの方法では、局所不変画像特徴が抽出され、それにより、局所変形に対してロバストな局所低水準コンテンツを取り込む。画像は、典型的には、約１０００個の特徴点を生成する。データベース画像は、これらの局所的な特徴を使用して索引付けされる。
【０００４】
局所ディスクリプタベースの画像検索におけるこれらのアプローチが大成功しているにもかかわらず、既存の研究の大部分は、１層の「ディスクリプタから画像へ」の索引付け構造に従っている。非常に効果的ではあるけれども、いくつかの明白な欠点がある。第１に、画像データベースは、通常、類似のオブジェクトまたはシーン、特に、何百万枚もの画像を有するオブジェクトまたはシーンの複数のコピーを記憶する。局所ディスクリプタのグループは、また、複数の画像中に頻繁に出現し得る。頻繁に出現するディスクリプタは、文献出現頻度の逆数を使用して少なめに重み付けされるけれども、「ディスクリプタから画像へ」の索引付けは、メモリを節約するためにいくつもの画像にわたってそのような冗長性を排除する戦略を有しない。言い換えれば、現在の索引付け方式は、必要以上にメモリコストを高くしている可能性がある。第２に、大規模画像分類および突出物解析における近年の進歩は、画像間のロバストな類似性解析を実施するうえで役立ち得る。現在の索引付けは、各画像について個別に実行されるので、オンライン検索のために複雑なデータベース画像関係を現在のフレームワークに埋め込むことは容易でない。
【０００５】
画像検索のための現在の画像索引付けシステムの大部分は、データベースを個別の画像の集合と見なしている。したがって、高度な交差画像解析（ｃｒｏｓｓ  ｉｍａｇｅ  ａｎａｌｙｓｉｓ）を実施する検索フレームワークの柔軟性が制限され、その結果、メモリ消費量が増大し、検索精度が次善最適なものとなっている。
【発明の概要】
【０００６】
一態様において、プロセッサを使用することと、個別の単一の画像ではなくグループレットとして画像を処理する索引付け戦略を適用することと、グループ層により２層索引付け構造（ｔｗｏ  ｌａｙｅｒ  ｉｎｄｅｘｉｎｇ  ｓｔｒｕｃｔｕｒｅ）を生成し、各々が画像層内の１つまたは複数の画像に関連付けられていることと、画像を２つ以上のグループに対して相互参照索引付けすることと、相互参照索引付けされた画像およびグループレットで近い重複画像を検索することとによって１つまたは複数の画像に対するクエリに応答するシステムおよび方法が開示されている。
【０００７】
別の態様において、システムは、２つの手順、１）グループレット生成、および２）グループレットベースの索引付けおよび検索を含む。各グループレット内の画像は、１つのユニットとして索引付けされ、検索されるので、検索精度を保証するために画像は互いに高い関連性を有している必要がある。大規模画像データベース内でそのようなグループレットを発見するために、われわれは、頂点が画像であり、リンクが異なる方法で計算された相互ｋ−最近傍（ｋＮＮ）関係を表す疎グラフを構築する。次いで、そのようなグラフにおいて、われわれは、最大クリークをグループレットとして求める。各最大クリークは、２つの頂点がリンクされているサブグラフであり、したがって、サブグラフの中の画像は、互いに高い関連性を有するであろう。異なる種類のグループレットを生成した後、われわれは、古典的なＢｏＷｓ（Ｂａｇ−ｏｆ−ｖｉｓｕａｌＷｏｒｄｓ）索引付け手順に従って、グループレットに索引付けする、すなわち、局所ディスクリプタを抽出し、プーリング戦略でＴＦ（語出現頻度）ベクトルを計算し、逆ファイル索引を構築する。オンライン検索段階において、われわれは、また、ＢｏＷｓ検索手順に従い、クエリから特殊ディスクリプタを抽出して関連性のあるグループレットを検索することのみを行い、次いで、グループレットをアンパックし、個別の画像をランク付けする。
【０００８】
このシステムの利点は、以下の１つまたは複数を含んでいてよい。われわれの方法では、データベース画像を合併集合として取り扱っている。各グループは、局所的類似性または大域的意味的類似性のいずれかに基づいた高い相関ベースを有する画像の集合からなる。各個別の画像を索引付けする大部分の以前の研究とは対照的に、われわれは、各グループに対して索引付けを適用する。グループは、特定のグループ内の画像が何らかの点で類似しているという形で構成されているので、グループ内の局所ディスクリプタは高い冗長性を有している。冗長なディスクリプタは、１回だけ索引付けされればよく、したがってメモリ使用量が著しく低減される。グループ構築の処理において、ロバストな索引付けをサポートするために大域的な高水準特徴、さらには局所的な特徴が考慮される。
【０００９】
われわれのアプローチは、より優れている精度、効率、およびメモリコスト、すなわち、３つの種類のグループレットおよび１つの種類のグループレットが考察される場合にそれぞれベースラインＢｏＷｓの約１３０％および５０％のメモリコストを示している。したがって、われわれは、われわれのアプローチが精度、効率、およびメモリコストの面で既存の索引付けアプローチよりも優秀であると結論している。システムは、さまざまなコンテンツ解析技術を継ぎ目なく統合している。われわれのアプローチは、特徴抽出およびオンライン検索に取り組んでいる多くの近年の検索アプローチと大きく異なる。これらのアプローチは、われわれの索引付け戦略と統合されることでより優れたパフォーマンスを発揮できる。われわれのオンライン検索は、局所ディスクリプタを抽出することのみ行うが、複数の画像類似性を考慮し、統合することができる。このアプローチは、オンライン検索時に異なる特徴または複数の検索結果を融合することによって余分な計算およびメモリコストを持ち込む、多くの検索融合アプローチに勝っている。
【図面の簡単な説明】
【００１０】
【図１】例示的なデータベース索引付け処理を示している。
【図２】例示的な索引付け構造を示している。
【図３】例示的なグループ生成モジュールを示している。
【図４】画像をグループマッピングに相互接続する例示的なモジュールを示している。
【図５】図１〜４のシステムを実行する例示的なコンピュータを示している。
【発明を実施するための形態】
【００１１】
次に、図を参照すると、図１には、画像を索引付けすることとは対照的に、グループを索引付けする索引付けエンジン１００が記載されている。図２〜４のブロック１０１、１０２、および１０３において詳細が説明されている。図１〜４のシステムは、局所ディスクリプタベースの画像検索に対して、コンパクト性、弁別性、および柔軟性の高い索引付け戦略を実現するものである。「ディスクリプタから画像へ」の単一層索引付けとは対照的に、われわれは、２層構造、すなわち、「ディスクリプタからグループレットへ」および「グループレットから画像へ」の構造を使用してデータベース画像を索引付けしている。中間のグループレット層は、高度な交差画像関係をモデル化し、画像間の冗長性を排除する。われわれがグループレットと名付けたのは、多数の小さいグループを使用して強い画像相関を実行するからである。索引付けフレームワークは、複数の画像にわたって相互情報を同時に符号化し、そこで、われわれは、その操作を、相互参照索引付けと称し、個別の画像の索引付けと区別している。図１に示されているように、グループレットの数は画像の数よりも著しく少ない可能性があるので、個別の画像ではなくグループレットを索引付けすることでよりコンパクトな索引ファイルを作成できる。より重要なのは、グループレットアプローチにより、オフライン相互参照索引付けにおいて異なる画像特徴および画像コンテンツ解析技術を継ぎ目なく統合することができる。
【００１２】
相互参照索引付けは、２つの主要なステップ、１）グループレット生成および２）グループレット索引付けからなる。われわれは、グループレット生成を、頂点が画像であり、リンクがカスタマイズされた類似性測定とともに計算されたｋ−最近傍（ｋＮＮ）関係を表す、疎グラフ内のすべての最大クリークを求めることと定式化している。図１に示されているように、われわれは、様々な類似性測定、すなわち、局所的類似性、領域的類似性、および大域的類似性、を介してグループレットを生成することを提案している。その結果得られるグループレットは、逆ファイル索引で一緒に索引付けされる。このようにして、類似の局所ディスクリプタ、類似のオブジェクト領域、または類似の意味を有する画像は、統一的フレームワーク内で一緒に組織化される。この方法で、索引ファイルの弁別能力が著しく改善され、したがってロバストな検索結果が生み出される。
【００１３】
われわれのオンライン検索は、ＢｏＷｓ（Ｂａｇ−ｏｆ−ｖｉｓｕａｌ  Ｗｏｒｄｓ）検索手順に従い、最初に、クエリから局所ディスクリプタを抽出し、関連するグループレットを検索する。次いで、画像は、グループレット構築時に得られるグループレット画像対応関係を使用してグループレットから検索される。局所ディスクリプタのみが、オンラインクエリに使用されるけれども、中間グループレット層が高度な画像関係をモデル化するので、類似する局所ディスクリプタ、類似するオブジェクト領域、および類似する意味を共有する画像を検索することも可能である。われわれは、自分たちのアプローチをいくつかの画像検索ベンチマークデータセットでテストしている。近年の画像検索アルゴリズムと比較すると、われわれのアプローチは、より低いメモリコスト、より高い効率、および競争力のある精度を示している。大規模データセット上の検索は、そのような利点をさらに明らかにしている。
【００１４】
図１は、例示的なデータベース索引付け処理を示している。図１は、データベース画像を索引付けする一般的索引付けフレームワークを示している。入力画像が特徴抽出エンジンに供給される。図１のシステムは、最初に、データベース画像から特徴を抽出する。次いで、これらの特徴は、画像ＩＤに従って、図２で形成された索引付け構造に対して索引付けされる。すべてのグループを取得した後に、われわれは、簡単のため局所的特徴のみを使用し、図２の１０１で説明されている方法を使用して各グループを索引付けする。データベース画像は、２層索引付け構造、すなわち、グループ層索引と画像層索引とで索引付けされる。図２の１０１において、データベース画像を索引付けする２層索引付け構造は、グループ層と画像層とに作用する。グループ層索引付けは、画像ディスクリプタとグループｉｄとの対応関係を符号化する。画像層索引付けは、画像とグループとの対応関係を符号化する。
【００１５】
われわれは、画像データベース内で、多くの画像が互いに強い関連性を共有することを観察している。われわれは、これらの画像を個別に索引付けするのではなく、これらの画像を、索引付けおよび検索を行えるように１つの基本ユニットにパッケージすることを提案している。われわれは、高い関連性を有する画像を含むそのような基本ユニットをグループレットと呼んでいる。
【００１６】
画像ｉｄを使用して局所的特徴ディスクリプタを索引付けする従来の方法とは対照的に、われわれは、グループｉｄを使用して局所的特徴ディスクリプタを索引付けする。グループ層索引は、逆索引を使用して高速なグループ探索を可能にする。以前の研究と同様に、われわれは、語彙ツリー構造を使用して、第１の層ディスクリプタ索引付けタスクを実行する。第２の画像層索引は、探索されたグループから画像を検索することを可能にする。画像層索引は、当然のことながら、グループ構築処理において得られる。
【００１７】
図３は、２層索引付け構造とともに例示的な索引付け構造をより詳しく示している。第１に、われわれは、１０２に示されているような３つの異なる種類の情報、すなわち、１）局所的特徴類似性、２）領域類似性、３）大域的高水準特徴類似性を使用してグループを構築している。たとえば、画像グループは、グループ内のすべての画像が類似する局所的特徴を有する場合に構築され得る。類似のグループ構築処理は、２）および３）に適用され得る。各個別の画像を取り出して独立した索引付けを適用する、既存の方法と異なり、われわれは、構築した画像グループに対するデータベース画像に索引付けを適用する。
【００１８】
図３のモジュール１０２は、３つの異なる画像類似性測定、すなわち、局所的特徴類似性、意味的類似性、および部分領域類似性を使用する例示的なグループ構築を示している。局所的特徴類似性は、画像間の局所的コンテンツ類似性をモデル化する。意味的類似性は、２つの画像の間の類似性の意味を測定する。図３に示されているように、グループレットの数は単一の画像の数よりも著しく少ないので、単一の画像ではなくグループレットを索引付けすることでコンパクトな索引ファイルを作成できる。より重要なのは、グループレットを索引付けすることで、オフライン索引付けにおいて異なる画像特徴および画像コンテンツ解析技術を継ぎ目なく統合することができる。図３において、われわれは、異なるレベルの類似性、すなわち、局所的類似性、領域的類似性、および大域的類似性を有するグループレットを生成し、これらのグループを逆索引で一緒に索引付けする。したがって、最終的な索引において、類似の意味、類似の局所ディスクリプタ、または類似のオブジェクト領域のいずれかを有する画像は、一緒に組織化されることも可能である。この組織化は、索引ファイルの弁別能力およびコンパクト性を著しく改善し、したがって、既存のハッシュ法、転置ファイル、および検索融合戦略よりも優れている。
【００１９】
図４は、画像を複数のグループ内に出現させることができる例示的な相互参照索引付けモジュール１０３を示している。１つの画像が１つのグループ内にのみ入るようにできる場合、データセット全体が互いに素な集合に分割される。検索結果は、グループ構築結果に対して非常に敏感であろう。われわれの相互参照索引付けフレームワークは、グループ構築結果に対してロバストである。
【００２０】
クエリにおいて、われわれは、最初に、クエリ画像から局所的特徴を抽出する。各ディスクリプタを通じて、われわれは、ディスクリプタグループ索引付けを介して対応するグループを検索する。次いで、われわれは、画像グループ索引付けを通じて画像を見つける。データベース内の画像の検索スコアは、画像が複数のディスクリプタによって検索される場合に集計される。われわれは、グループマッピングに対する相互接続された画像と称する複数のグループ内に各画像を入れることができる。画像が１つ以下のグループに属している場合、グループ内のすべての画像は、全く同じ検索スコアを有する。このスコアで、同じグループ内の画像を区別することができない。われわれのフレームワークは、複数のグループが１つの画像に対してスコアを投票することを可能にする。したがって、２つの画像に対する検索スコアは、同じグループ内にあるとして異なるものとすることが可能である。
【００２１】
一実施形態において、画像データセットＤ＝｛ｄ１，ｄ２，．．．，ｄＭ｝が用意されている。相互参照索引付けにおいて、われわれは、データベースをグループレットの集合体、すなわち、Ｄ上で生成された
【００２２】
【数１】
0006279771.tif 000002
として表している。われわれは、グループレットＧａを画像の集合体として定義する、すなわち、
【００２３】
【数２】
0006279771.tif 000003
であり、ここで、｜・｜はＧの濃度である、すなわち、グループレット内の画像の数である。索引付けするグループレットが多いほど、結果として、メモリコストが大きくなるので、グループレットの数を制御するために各グループレットが他の部分集合でないことが必要である。われわれは、画像ｄｉを含むグループレットの集合体を
【００２４】
【数３】
0006279771.tif 000004
として表す。ｄｉは複数のグループレットに属している可能性があるので、
【００２５】
【数４】
0006279771.tif 000005
となる。
【００２６】
相互参照索引付けにおけるそのようなグループレット表現に基づき、オンライン検索時に、クエリｑとデータベース画像ｄｉとの間の類似性は、
【００２７】
【数５】
0006279771.tif 000006
として定式化することが可能であり、ここで、われわれは、グループレットとクエリとの間の類似性、すなわち、ｓｉｍ（・）を使用して、クエリとデータベース画像との間の類似性に投票する。したがって、式（２）は、ＴＦ−ＩＤＦ（語出現頻度−文献出現頻度の逆数）類似性と、クエリとデータベース画像との間の類似性を直接計算する逆ファイル索引付けの点で異なる。
【００２８】
式（２）によれば、同じグループレット内の画像は、異なるグループレット内の画像に比べてより整合している、クエリとの類似性を示すであろう。したがって、生成されたグループレットの品質は、相互参照索引付けの後の画像検索における類似性計算に大きな影響を及ぼすであろう。画像検索を有効にするために、グループレットは、画像間に弁別関係を埋め込んで、緊密な関係を有する画像がクエリとより整合している類似性を共有することを保証すべきである。このようにすることで、われわれのグループレット生成の式、すなわち、
【００２９】
【数６】
0006279771.tif 000007
が誘導され、ここで、Ｄは、意味論的意味、または局所的視覚的類似性のようなカスタマイズされた測定によって計算され得る与えられた距離行列を表し、
【００３０】
【数７】
0006279771.tif 000008
は、相互参照索引付けの後のクエリｑとｄｉとの間の距離である。式（２）と同様に、この式は、ｑと
【００３１】
【数８】
0006279771.tif 000009
内のグループレットとを比較することによって計算される。
【００３２】
【数９】
0006279771.tif 000010
は、生成されたグループレットの数を制御する正則化項である。距離関係により、われわれは、上記の式を
【００３３】
【数１０】
0006279771.tif 000011
として簡略化することが可能であり、ここで、ＤＩＳ（・）は、グループレットの２つの集合体の間の距離を表す。ＤＩＳ（・）およびＤを式
【００３４】
【数１１】
0006279771.tif 000012
で置き換えることによって、われわれは、式（４）を
【００３５】
【数１２】
0006279771.tif 000013
として十分簡単にすることが可能であり、ここにおいて、ＳＩＭ（・）は、グループレットの２つの集合体の間の類似性を表し、行列Ｓは、データベース画像間のカスタマイズされた関係を表す無向グラフとみなすことができる。グループレット生成は、したがって、このグラフを、１）同じ部分グラフ内の画像が互いに高い関連性を有するべきであり、無関係の画像は異なる部分グラフ内に出現すべきであるという条件、および２）部分グラフの数は、メモリを節約できるくらいに小さい数であるべきであるという条件を満たす部分グラフに分割することと同等である。
【００３６】
グラフ理論によれば、無向グラフ内のクリークは、１つおきの頂点が接続されている、頂点の部分集合として定義される。最大クリークは、１つまたは複数の隣接する頂点を含めることによって延ばすことができないクリークである。したがって、式（６）を最適化することは、無向グラフ内のすべての最大クリークを見つけることと同等である、すなわち、最大クリーク内の画像が互いに接続され、最小数のクリークが生成され得る。したがって、グループレット生成は、Ｓによって定義されたグラフ内のすべての最大クリークを求めることによって妥当に解決されることが可能であろう。
【００３７】
一実施形態において、相互ｋＮＮグラフは、画像間の関連性関係を明らかにし、次いで、そのグラフ内のすべての最大クリックをグループレットとして求めるために使用される。ｄｉ、ｄｊが、互いの相互ｋＮＮｓであると仮定すると、ｄｉ、ｄｊは
【００３８】
【数１３】
0006279771.tif 000014
を満たすべきであり、ここで、ｋＮＮ（・）は、画像のｋ最近傍を表す。
【００３９】
辺は、相互ｋＮＮ関係を表している。相互ｋＮＮは、画像間の信頼できる関連性を明らかにしていることは明白である。相互ｋＮＮ関係に基づき、われわれは、疎グラフＨ＝（Ｖ，Ｓ）を構築することが可能であり、ここで、Ｖは、頂点集合、すなわち、データベース画像であり、Ｓは、頂点と頂点との間の辺を記憶する、すなわち、ｄｉおよびｄｊが互いの相互ｋＮＮｓである場合に、Ｓ（ｉ，ｊ）＝１である。
【００４０】
グラフ内のすべての最大クリークを見つけることは、ＮＰ完全問題である。この問題は難しいけれども、多くの効率的なアルゴリズムが研究されている。Ｍａｋｉｎｏらは、疎グラフから毎秒約１００，０００個の最大クリークを見つける、高速な行列乗算に基づき出力に敏感なアルゴリズムを提案している。この論文において、われわれは、最大クリークを見つける方法を採用している。適切に選択されたパラメータｋで疎グラフを構築することによって、最大クリークは、効率的に識別され得る。
【００４１】
強い関連性を共有する画像は、１つのグループレットとして識別されることが可能であることが観察され得る。他の画像との類似性を有しない孤立した画像は、その画像自体を含むグループレットを構成する。この構成により、必ず、各グループレット内の画像間の高い関連性が保証される。前述のように、パラメータｋは、行列Ｓの疎性を決定し、したがって、生成されたグループレットの数および品質を十分に決定する。相互参照索引付けにおいて、中間グループレット層は、相互ｋＮＮ関係をカスタマイズすることを通じて異なる画像コンテンツ解析技術の継ぎ目のない統合を可能にする。われわれは、３つの相補的手がかりを使用して、最終的なグループレット集合体、すなわち、
【００４２】
【数１４】
0006279771.tif 000015
を生成する。
【００４３】
【数１５】
0006279771.tif 000016
は、局所ディスクリプタとともに生成されたグループレットを表している。われわれは、語彙ツリーを採用して、ＢｏＷｓモデルを計算し、データベース画像に対する逆索引を構築し、最終的に、ＴＦ−ＩＤＦ類似性を計算して相互ｋＮＮグラフを構築することが可能である。局所ディスクリプタベースの画像探索［？，？］および画像関係計算［？，？，？，？］に関する近年の研究も、
【００４４】
【数１６】
0006279771.tif 000017
の品質を改善するために使用することができる。局所ディスクリプタおよび語彙ツリーは、もっぱら、部分的重複画像探索において使用されるので、
【００４５】
【数１７】
0006279771.tif 000018
は、部分的重複画像を同じグループレットに一緒に効果的に組織化する。
【００４６】
【数１８】
0006279771.tif 000019
は、領域特徴とともに生成されたグループレットを表している。われわれは、最初、オーバーセグメンテーションを通じて画像上の初期領域を密に生成する。サイズが大きすぎるか、または小さすぎる領域を除去した後、われわれは、残っている領域間の重なり率を記憶する行列を計算している。したがって、アフィニティ伝搬がこの行列上で適用され、これらの領域をクラスタ化する。われわれは、最終的に、５個以下のクラスタを保持し、それらのクラスタ内の最大の領域を選択して、この画像を表す。２つの画像ｄｉおよびｄｊの領域集合体が
【００４７】
【数１９】
0006279771.tif 000020
および
【００４８】
【数２０】
0006279771.tif 000021
であるとそれぞれ仮定して、われわれは、領域画像類似性を
【００４９】
【数２１】
0006279771.tif 000022
として定義し、ここで、｜・｜は、集合の濃度、すなわち、それぞれ、ｄｉまたはｄｊ内の領域の数であり、ｓ（・）は、２つの画像領域の特徴ベクトルの間の類似性を返す。したがって、われわれは、定義された領域類似性Ｓｒ（・）を使用してグラフを構築することが可能である。領域は、オブジェクトレベルの手掛かりを取り込む傾向があり、また背景クラッタの負の効果を排除し得るので、
【００５０】
【数２２】
0006279771.tif 000023
は、類似のオブジェクトを有する画像を同じグループレットに組織化することが期待される。
【００５１】
【数２３】
0006279771.tif 000024
は、大域的類似性とともに生成されたグループレットを表している。われわれは、単純に、大域的特徴とともに計算された類似性を使用して、
【００５２】
【数２４】
0006279771.tif 000025
の生成に対する相互ｋＮＮグラフを構築している。したがって、
【００５３】
【数２５】
0006279771.tif 000026
は、類似の大域的外観を有する画像を同じグループレットに組織化する傾向がある。
【００５４】
相互参照索引付けにおいて、われわれは、異なる種類のグループレットを一緒に混合し、次いで、２層索引付け構造でグループレットを索引付けすることを続ける。関連性のある画像は、複数の面で、たとえば、局所的外観および大域的外観の面で多く類似性があるので、冗長なグループレットが存在し得る。そのような冗長性を取り除き、メモリコストを節約するために、われわれは、２つのグループレットの類似性を、
【００５５】
【数２６】
0006279771.tif 000027
として定義し、ここで、｜・｜は、Ｇの濃度、すなわち、グループレット内の画像の数である。式（９）により、われわれは、２つのグループレットの類似性がαを超える場合により小さいグループレットを無視する。この論文で、われわれは、実験的に、α＝０．８に設定した。
【００５６】
重複するグループレットを取り除いた後、われわれは、逆ファイル索引付け例に従って、グループレット索引を構築している。われわれは、最初に、数百万もの視覚的単語を含む語彙ツリーにより局所ディスクリプタを抽出し、局所ディスクリプタを視覚的単語に符号化し、次いで、グループレットのＴＦ（語出現頻度）ベクトルを計算している。ただ１つの画像を含むグループレットについては、われわれは、Ｌ−１正規化視覚的単語ヒストグラムをＴＦベクトルとして直接計算している。複数の画像を含むグループレットについては、われわれは、最初に、画像のＴＦベクトルを計算し、次いで、説明されているように疎ＴＦベクトルに適している、最大プーリング戦略を採用している。グループレット
【００５７】
【数２７】
0006279771.tif 000028
については、Ｇの中の視覚的単語ｖのＴＦ値は、
【００５８】
【数２８】
0006279771.tif 000029
として計算され、ここで、ＴＦｉは、データベース画像ｄｉのＬ−１正規化ＴＦベクトルを表している。
【００５９】
すべてのグループレットのＴＦベクトルに基づき、われわれは、グループレット索引でグループレットを索引付けし、ここで、索引中の各セルは、視覚的単語のＴＦ値およびグループレットのＩＤを記録する。われわれは、第２の層索引をさらに構築してグループレット画像関係を記録している。グループレット画像関係は、グループレット生成処理において取得される。
【００６０】
２層索引付け構造であるので、われわれのオンライン検索手順は、２つのステップからなる。第１のステップは、ＢｏＷｓベースの画像検索とほとんど同一である、すなわち、ＳＩＦＴディスクリプタを抽出して、視覚的単語に量子化し、ＴＦ−ＩＤＦ類似性、すなわち、
【００６１】
【数２９】
0006279771.tif 000030
を計算する。
【００６２】
この処理は、類似の局所ディスクリプタをクエリと共有するグループレットを返す。
【００６３】
次いで、画像索引に記録されたグループレット画像関係に従って、われわれは、これらのグループレットを単一の画像のリストにアンパックしている。式（２）に示されているように、クエリｑとデータベース画像ｄｉとの間の類似性は、ｑ、およびｄｉを含むグループレットの類似性を投票することによって計算される。
【００６４】
われわれは、類似性の異なる面を持つグループレットを生成するので、複数の面でクエリと整合している画像が最初に返されるであろう。これは、クエリの部分的重複画像を検索することに焦点をもっぱら当てる、既存の局所ディスクリプタベースの画像検索システムの大部分よりも優れている。それに加えて、われわれの検索戦略は、クエリに対する局所ディスクリプタのみを抽出し、したがって、オンライン検索時に複数の特徴または複数の結果のいずれかを融合させる必要がある、検索融合戦略の大部分よりも優れている。
【００６５】
一実施態様は、グループレットによる相互参照索引付けを使用して、データベース画像を各々が高い関連性を有する画像のグループとして定義されているグループレットの集合とみなす。グループレットの数は、画像の数よりも少なく、したがって、メモリコストが下がるのは当然である。さらに、グループレットの定義は、カスタマイズされた関係に基づくことが可能であり、オフライン索引付けにおける高度なデータマイニング技術の継ぎ目のない統合が可能になる。グループレットによる相互参照索引付けでは、データベース画像をグループレットの集合とみなし、２層索引付け構造を構築して、効率的な画像検索を実現する。われわれは、各グループレットを関連性の高い画像の集合として定義し冗長性を排除する。さらに、グループレットの定義は、カスタマイズされた関係に基づくことが可能であり、オフライン索引付けにおける高度なデータマイニング技術の継ぎ目のない統合が可能になる。われわれのフレームワークは、局所的類似性、領域関係、および大域的知覚的特徴によってそれぞれ定義される相互ｋＮＮグラフの最大クリークを求めることによって３つの異なる種類のグループレットにより具体的に説明されている。システムを妥当なものとするために、われわれは、局所的類似性、領域関係、および大域的視覚的モデリングにそれぞれ基づく３つの異なる種類のグループレットを構築している。公開ベンチマークデータセットでの広範な実験により、われわれのアプローチの効率および優秀なパフォーマンスが実証されている。
【００６６】
システムは、ハードウェア、ファームウェアもしくはソフトウェア、またはこれら３つの組合せで実装されてよい。図５は、上述されたシステムを実行する例示的なコンピュータを示している。
【００６７】
好ましくは、本発明は、プロセッサ、データ記憶装置システム、揮発性および不揮発性メモリおよび／または記憶装置要素、少なくとも１つの入力デバイス、および少なくとも１つの出力デバイスを有するプログラム可能なコンピュータ上で実行されるコンピュータプログラムで実装される。
【００６８】
たとえば、このシステムをサポートするコンピュータのブロック図を次に説明する。コンピュータは、好ましくは、プロセッサ、ランダムアクセスメモリ（ＲＡＭ）、プログラムメモリ（好ましくは、フラッシュＲＯＭなどの書き込み可能なリードオンリーメモリ（ＲＯＭ））、およびＣＰＵバスによって結合された入出力（Ｉ／Ｏ）コントローラを備えている。コンピュータは、適宜、ハードディスクおよびＣＰＵバスに結合されているハードドライブコントローラを備えてよい。ハードディスクは、本発明などのアプリケーションプログラム、およびデータを記憶するために使用され得る。代替的に、アプリケーションプログラムは、ＲＡＭまたはＲＯＭに記憶されてよい。Ｉ／Ｏコントローラは、Ｉ／Ｏバスを用いてＩ／Ｏインターフェースに結合される。Ｉ／Ｏインターフェースは、シリアルリンク、ローカルエリアネットワーク、ワイヤレスリンク、およびパラレルリンクなどの通信リンク上でアナログまたはデジタル形式のデータを送受信する。適宜、ディスプレイ、キーボード、およびポインティングデバイス（マウス）も、Ｉ／Ｏバスに接続されてよい。代替的に、別個の接続（別個のバス）が、Ｉ／Ｏインターフェース、ディスプレイ、キーボード、およびポインティングデバイスに使用されてよい。プログラム可能な処理システムは、事前プログラムされ得るか、またはプログラムを別のソース（たとえば、フロッピィディスク、ＣＤ−ＲＯＭ、別のコンピュータ）からダウンロードすることによってプログラムされ（および再プログラムされ）てよい。
【００６９】
各コンピュータプログラムは、記憶媒体またはデバイスがコンピュータによって読み出され、本明細書で説明されている手順を実行するときにコンピュータのオペレーションを構成し、制御するために、汎用または専用プログラム可能コンピュータによって読み取り可能な機械可読記憶媒体またはデバイス（たとえば、プログラムメモリまたは磁気ディスク）に有形に記憶されている。本発明のシステムは、コンピュータプログラムを伴って構成された、コンピュータ可読記憶媒体に具現化されるように企図されてもよく、ここで、そのように構成された記憶媒体により、コンピュータは特定の、事前定義された方式で動作し、本明細書で説明されている機能を実行する。
【００７０】
本発明は、特許法を遵守するために、また新規性のある原理を応用し、必要に応じてそのような専用の構成要素を構築し使用するのに必要な情報を当業者に提供するために、かなり詳細に説明されている。しかしながら、本発明は、特に異なる機器およびデバイスによって実施されうること、および本発明自体の範囲から逸脱することなく、機器の詳細および動作手順の両方に関する、さまざまな修正を実施することができることは理解されるであろう。
【図１】
0006279771.tif 000034
【図２】
0006279771.tif 000035
【図３】
0006279771.tif 000036
【図４】
0006279771.tif 000037
【図５】
0006279771.tif 000038