画像検索装置およびプログラム
【課題】ＧＰＵのように同種の処理を大量に行う能力の高いハードウェアを用いて、画像検索処理を高速化すること。
【解決手段】画像検索装置１は、共通メモリと、同一の命令を実行する複数の並列のプロセッサを含む。画像検索装置１は、記憶手段から、複数の画像特徴ベクトルを含む複数のクラスタをそれぞれ代表する複数の代表特徴ベクトルを転送し、クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを前記共通メモリに格納し、前記転送された複数の代表特徴ベクトルと前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算し、前記第１の距離計算手段による計算結果により選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離に基づいて、複数の画像のうちいずれかを選択する。
【解決手段】画像検索装置１は、共通メモリと、同一の命令を実行する複数の並列のプロセッサを含む。画像検索装置１は、記憶手段から、複数の画像特徴ベクトルを含む複数のクラスタをそれぞれ代表する複数の代表特徴ベクトルを転送し、クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを前記共通メモリに格納し、前記転送された複数の代表特徴ベクトルと前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算し、前記第１の距離計算手段による計算結果により選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離に基づいて、複数の画像のうちいずれかを選択する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像検索装置およびプログラムに関する。
【背景技術】
【０００２】
ネットワーク技術等の発達によって、膨大な量の画像ファイルが管理されるようになっている。その大量の画像の中から、クエリとなる画像に類似する画像を選び出す画像検索技術がある。大量の画像の中から高速に画像を選択するために、ＢｏＦ（Bag of Features）法と呼ばれる検索手法の開発が進んでいる。この手法は、ＢｏＷ(Bag of Words)法と呼ばれる文書検索の手法を応用したものである。ＢｏＦ法では、検索対象となる画像から抽出される特徴ベクトルのそれぞれをＢｏＷ法における単語に相当するＶｉｓｕａｌ Ｗｏｒｄに対応させ、このＶｉｓｕａｌ Ｗｏｒｄの出現頻度を用いて類似する画像を検索する。
【０００３】
特許文献１には、クエリとなる画像から抽出される複数の画像特徴量ベクトルを、クラスタリングを用いてより少ないベクトルに変換し、その変換されたベクトルをクエリとして画像の検索を行う技術が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１１−１０７７９５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、画像データは文字データに比較してそのデータ量が膨大であるため、通常のＣＰＵを用いて文字と同様な高速検索を行うには、処理量を削減することが必要になる。このため、検索インデックスの生成時にその画像データの特徴を的確に表せないＶｉｓｕａｌ Ｗｏｒｄを用いなければなければならないなど、充分な検索精度を得ることが難しくなっていた。
【０００６】
そこで、例えば所謂ＧＰＵ（Graphic Processing Unit）のような、複数のプロセッサおよび共通メモリを含み、複数のプロセッサはそれぞれ共通メモリから効率的にデータを取込み、また共通のプログラムを実行して演算処理を行うことができる、ＣＰＵよりも計算能力の高いハードウェアを用いることが考えられる。演算処理が高速に行われるのであれば、精度を確保しつつ高速検索することが可能となるからである。
【０００７】
しかしながら、上記したようなＢｏＦ法などはＣＰＵに最適化された手順であり、疎行列等を扱うためにリンクドリストのデータ構造や分岐処理を多用する。それらは、上述のような特徴を有するＧＰＵのアーキテクチャとの親和性が低いため、ＧＰＵをそのまま用いてもその能力を充分に活かすことができなかった。
【０００８】
本発明は上記課題を鑑みてなされたものであって、その目的は、ＧＰＵのように同種の処理を大量に行う能力の高いハードウェアを用いて、画像検索処理を高速化することにある。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明にかかる画像検索装置は、共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含み、さらに、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段と、クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを取得し、前記共通メモリに格納するクエリ特徴ベクトル取得手段と、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算手段と、前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算手段と、前記第２の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択する手段と、を含むことを特徴とする。
【００１０】
また、本発明にかかるプログラムは、共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータを、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段、クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定手段、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算手段、前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算手段、および、前記第２の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択する手段、として機能させることを特徴とする。
【００１１】
また、本発明にかかる画像検索方法は、共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータに画像を検索させる画像検索方法であって、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送ステップと、クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定ステップと、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算ステップと、前記第１の距離計算ステップによる計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算ステップと、前記第２の距離計算ステップによる計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択するステップと、を含むことを特徴とする。
【００１２】
また、本発明にかかるコンピュータ読み取り可能な記憶媒体は、共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータを、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段、クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定手段、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算手段、前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算手段、および、前記第２の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択する手段、として機能させるためのプログラムを記憶することを特徴とする。
【００１３】
本発明によれば、ＧＰＵのように同種の処理を大量に行う能力の高いハードウェアを用いて、画像検索処理を高速化することができる。代表ベクトルを用いることで距離計算の対象となる特徴ベクトルの数が減り、かつ距離計算が主体となるためＧＰＵのように同種の処理を大量に行えるハードウェアとの親和性が高いからである。
【００１４】
本発明の一態様では、前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルを前記記憶手段から前記共通メモリに転送する画像特徴ベクトル転送手段をさらに含み、前記第２の距離計算手段は、前記転送された画像特徴ベクトルと前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算しもよい。
【００１５】
本発明の一態様では、前記複数の代表特徴ベクトルのデータ量は、前記共通メモリの容量より小さくてもよい。
【００１６】
本発明の一態様では、前記複数のクラスタのうち１つに属する画像特徴ベクトルのデータ量は、前記共通メモリの容量より小さく、前記複数のクラスタに属する画像特徴ベクトルのデータ量は、前記共通メモリの容量より大きくてもよい。
【００１７】
本発明の一態様では、前記複数のクラスタのうち１つに属する画像特徴ベクトルと前記複数の代表ベクトルとのデータ量は、前記共通メモリの容量より小さく、前記画像特徴ベクトル転送手段は、前記選択されたクラスタに属する画像特徴ベクトルを、共通メモリに記憶されている他の画像特徴ベクトルと置き換えてもよい。
【００１８】
本発明の一態様では、追加される検索対象となる画像から複数の画像特徴ベクトルを抽出する追加画像特徴ベクトル抽出手段と、前記追加画像特徴ベクトル抽出手段により抽出された画像特徴ベクトルを前記画像特徴クラスタのうちいずれかに追加する画像特徴ベクトル追加手段と、をさらに含んでもよい。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施形態にかかる画像検索システムの構成の一例を示す図である。
【図２】本発明の実施形態にかかる画像検索装置の構成の一例を示す図である。
【図３】並列計算装置の構成の一例を示す図である。
【図４】本発明の実施形態にかかる画像検索装置の機能を示す機能ブロック図である。
【図５】インデックス生成部の機能構成を示す機能ブロック図である。
【図６】検索対象となる画像の一例を示す図である。
【図７】画像から抽出される画像特徴ベクトルの概念を示す図である。
【図８】代表ベクトルの木構造の一例を示す図である。
【図９】画像検索部の機能構成を示す機能ブロック図である。
【図１０】装置内メモリでのデータ配置の一例を示す図である。
【図１１】装置内メモリでの代表ベクトルの配置の一例を示す図である。
【図１２】クエリとなる画像を入力する画面の一例を示す図である。
【図１３】距離計算の処理フローの一例を示す図である。
【図１４】クエリ特徴ベクトルに対応する画像を統計処理した結果の一例を示す図である。
【図１５】インデックス追加部の機能構成を示す機能ブロック図である。
【発明を実施するための形態】
【００２０】
以下では、本発明の実施形態について図面に基づいて説明する。出現する構成要素のうち同一機能を有するものには同じ符号を付し、その説明を省略する。
【００２１】
図１は、本発明の実施形態にかかる画像検索システムの構成の一例を示す図である。画像検索システムは、画像検索装置１と、ウェブサーバ２と、クライアント装置３とを含む。ウェブサーバ２は、例えばウェブサーバプログラムが動作するサーバハードウェアであり、クライアント装置３は、例えばウェブブラウザのプログラムが動作するパーソナルコンピュータや、スマートフォンである。画像検索システムは画像検索を行う動作の概要は以下の通りである。はじめに、ウェブサーバ２は、インターネット等のネットワークを介してクライアント装置３から画像検索に用いるクエリとなる画像（以下、「クエリ画像」と記述する）を取得し、そのクエリ画像を画像検索装置１に入力させる。次に画像検索装置１は、入力された画像に類似する１または複数の画像を検索し、ウェブサーバ２に出力する。ウェブサーバ２は、画像検索装置１が検索した画像をクライアント装置３に表示させるデータを出力する。
【００２２】
図２は、本発明の実施形態にかかる画像検索装置１の構成の一例を示す図である。画像検索装置１は、ＣＰＵ１１、記憶部１２、通信部１３、並列計算装置１４およびバス１５を含む。
【００２３】
ＣＰＵ１１は、記憶部１２に格納されているプログラムに従って動作する。またＣＰＵ１１は通信部１３や並列計算装置１４を制御する。なお、上記プログラムは、インターネット等のネットワークを介して提供されるものであってもよいし、ＤＶＤ−ＲＯＭやＵＳＢメモリ等のコンピュータで読み取り可能な情報記録媒体に格納されて提供されるものであってもよい。
【００２４】
記憶部１２は、ＲＡＭやＲＯＭ等のメモリ素子やハードディスクドライブ等によって構成されている。記憶部１２は、上記プログラムを格納する。また、記憶部１２は、各部から入力される情報や演算結果を格納する。
【００２５】
通信部１３は、ウェブサーバ２等の他の装置と通信接続するためにネットワークカードなどが設けられる通信手段等で構成されている。通信部１３は、ＣＰＵ１１の制御に基づいて、他の装置から受信した情報をＣＰＵ１１や記憶部１２に入力し、他の装置に情報を送信する。
【００２６】
バス１５は、ＣＰＵ１１、記憶部１２、通信部１３および並列計算装置１４との間でデータをやりとりするためのものである。例えば、ＣＰＵ１１や記憶部１２と並列計算装置１４とはバス１５の中の拡張バスを介して接続される。
【００２７】
並列計算装置１４は、並列計算によって同種の計算を大量に行うことを得意とするハードウェアである。並列計算装置１４は、例えばＧＰＵである。図３は、並列計算装置１４の構成の一例を示す図である。並列計算装置１４は、複数の並列実行部４０と、装置内メモリ４５とを含む。また各並列実行部４０は、複数のプロセッサ４１と、命令ユニット４２と、高速メモリ４３とを含む。
【００２８】
複数のプロセッサ４１のそれぞれは、浮動小数点計算や、装置内メモリ４５や高速メモリ４３との間でのデータの読込みや書込み等の処理を行う。命令ユニット４２は、装置内メモリ４５等に格納されるプログラムに基づいて、その命令ユニット４２を含む並列実行部４０に含まれる複数のプロセッサ４１に処理をさせる。ある並列実行部４０に含まれる複数のプロセッサ４１は、その並列実行部４０に含まれる一つの命令ユニット４２からの指示によって、同一の命令を処理する。こうすると、複数のプロセッサ４１を１つの命令ユニット４２で制御できるため、命令ユニット４２の回路の規模の増加を抑えることができるため、並列計算装置１４に含まれるプロセッサ４１の数をＣＰＵ１１に比べて増やすことが可能になる。
【００２９】
装置内メモリ４５は、記憶部１２に用いられるＲＡＭより高速にアクセス可能なＤＲＡＭからなる。装置内メモリ４５は、バス１５を介して、ＣＰＵ１１や記憶部１２と接続されている。なお、並列計算装置１４は、ＤＭＡ転送により装置内メモリ４５と記憶部１２との間でデータを転送する回路も有する。高速メモリ４３は、装置内メモリ４５より高速にアクセス可能なＳＲＡＭ等からなる。プロセッサ４１が高速メモリ４３にアクセスする際のレイテンシは、プロセッサ４１がその内部レジスタにアクセスする際のレイテンシとほとんど変わらない。ここで、装置内メモリ４５も高速メモリ４３も複数のプロセッサ４１から共通にアクセスできる共通メモリである。
【００３０】
図４は、本発明の実施形態にかかる画像検索装置１の機能を示す機能ブロック図である。画像検索装置１は、機能的に、インデックス生成部５１、画像検索部５２、およびインデックス追加部５３を含む。これらの機能は、ＣＰＵ１１が記憶部１２に格納されたプログラムを実行し、通信部１３や並列計算装置１４を制御し、また、並列計算装置１４がその並列計算装置１４向けのプログラムを実行することで実現される。
【００３１】
インデックス生成部５１は、検索対象となる複数の画像から、画像検索の際に用いる画像特徴ベクトル２０や、その画像特徴ベクトル２０の選択を容易にするインデックスを生成する。画像検索部５２は、インデックスや画像特徴ベクトル２０を用いて、クエリ画像に類似する画像を検索する。インデックス追加部５３は、追加の画像から画像特徴ベクトル２０を生成し、またその追加の画像を選択できるようインデックスを変更する。
【００３２】
図５は、インデックス生成部５１の機能構成を示す機能ブロック図である。インデックス生成部５１は、機能的に、画像特徴ベクトル抽出部６１と、クラスタ生成部６２とを含む。クラスタ生成部６２は、クラスタのインデックスとなる代表ベクトルの木構造を生成し、木構造代表ベクトル格納部７２にインデックスに関連する情報を格納する。また、クラスタベクトル格納部７１は、その木構造の葉となる代表ベクトルが代表するクラスタに属する画像特徴ベクトル２０の情報を格納する。クラスタベクトル格納部７１、木構造代表ベクトル格納部７２は、具体的には記憶部１２により構成される。
【００３３】
画像特徴ベクトル抽出部６１は、主にＣＰＵ１１および記憶部１２により実現される。画像特徴ベクトル抽出部６１は、記憶部１２に格納されている複数の画像であって検索対象となる複数の画像から、複数の画像特徴ベクトル２０を抽出する。より具体的には、画像特徴ベクトル抽出部６１は、その複数の画像のそれぞれから、１または複数の画像特徴ベクトル２０を抽出し、抽出された画像特徴ベクトル２０を、その画像特徴ベクトル２０が抽出された画像と関連付けて記憶部１２に記憶させる。
【００３４】
図６は、検索対象となる画像の一例を示す図である。図７は、画像から抽出される画像特徴ベクトル２０の概念を示す図である。画像から抽出される画像特徴ベクトル２０のそれぞれは、その画像の局所的な特徴を示す局所特徴量である。画像特徴ベクトル２０のそれぞれは、例えば１２８の要素（次元）をもつベクトルである。画像特徴ベクトル２０を抽出するためには、ＳＩＦＴ（Scale-Invariant Feature transform）、ＳＵＲＦ（Speeded Up Robust Features）などの公知の手法を用いてよい。画像特徴ベクトル２０のそれぞれが有する要素の数は、画像からの抽出の手法などに応じて変化させてよい。また１つの画像から抽出される画像特徴ベクトル２０の数は、予め定められた数（例えば３００）としてよいが、単純な画像から抽出される画像特徴ベクトル２０の数はその予め定められた数より少なくなってもよい。
【００３５】
クラスタ生成部６２は、主にＣＰＵ１１および記憶部１２により実現される。クラスタ生成部６２は、クラスタリングにより、画像特徴ベクトル抽出部６１により抽出された複数の画像特徴ベクトル２０のそれぞれを、複数のクラスタのいずれかに分類する。画像特徴ベクトル２０をクラスタに分類する処理は１段階の処理とは限らず、多段階の処理であってよい。また、その多段階の処理は、以下の処理を再帰的に呼び出すことにより実現してもよい。以下では、２段階の処理を行い、かつ１段目で画像特徴ベクトル抽出部６１により抽出された複数の画像特徴ベクトル２０を１０２４個のクラスタに分類し、さらに２段目でその１０２４個のクラスタのそれぞれを５１２個のクラスタに分類する場合の例について説明する。
【００３６】
クラスタ生成部６２の各段の処理では、クラスタリングにより、与えられた複数の画像特徴ベクトル２０を与えられた個数のクラスタに分類し、複数のクラスタを生成し、さらにその生成されたクラスタの代表ベクトルを生成し、生成された代表ベクトルをその段の代表ベクトルとして木構造代表ベクトル格納部７２に格納する。処理中の段が最下段でない場合は、クラスタ生成部６２は処理中の段で生成されたクラスタのそれぞれに属する複数の画像特徴ベクトル２０を入力情報として、次の段の処理を再帰的に呼び出す。代表ベクトルは、例えばその分類されたクラスタに属する画像特徴ベクトル２０の重心であり、そのクラスタを代表するベクトルである。またクラスタ生成部６２は、最下段の処理で生成されたクラスタごとに、そのクラスタに属する画像特徴ベクトル２０をクラスタベクトル格納部７１に格納する。
【００３７】
上述の例の場合、１段目の処理では、クラスタ生成部６２は、与えられた画像特徴ベクトル２０を１０２４個のクラスタに分類し、その分類された１段目の各クラスタの代表ベクトルを生成し、生成された１段目の代表ベクトルを木構造代表ベクトル格納部７２に格納する。２段目の処理では、クラスタ生成部６２は、１段目に生成された１０２４個のクラスタのそれぞれに属する複数の画像特徴ベクトル２０を入力情報として、更に５１２個のクラスタに分類し、その分類された２段目の各クラスタの代表ベクトルを生成し、生成された下位の段の代表ベクトルを木構造代表ベクトル格納部７２に格納する。２段目のクラスタを全て生成するとその２段目のクラスタの総数は（１０２４×５１２）個となる。さらにクラスタ生成部６２は、２段目に生成されたクラスタごとに、そのクラスタに属する画像特徴ベクトル２０をクラスタベクトル格納部７１に格納する。以下では、説明の容易のため、１段目のクラスタを代表する代表ベクトルを上位代表ベクトルと記し、最下段（上述の例では２段目）のクラスタを代表する代表ベクトルを代表特徴ベクトルと記す。また最終的に生成されたクラスタ（上述の例では２段目のクラスタ）を画像特徴クラスタとも記す。
【００３８】
画像特徴ベクトル２０をクラスタに分類する際には、ｋ−ｍｅａｎｓ法等の公知のクラスタリング手法を用いればよい。クラスタの数は、後述の画像検索部５２の処理との関係で、２のべき乗が好適であるが、２のべき乗でなくてもよい。また全ての画像に含まれる画像特徴ベクトル２０を分類すると、それぞれの画像特徴クラスタには、複数の画像特徴ベクトル２０が属する。クラスタ生成部６２の再帰処理を２段階行う事で、木構造代表ベクトル格納部７２に、２階層の情報を格納する事ができる。クラスタ生成部６２の計算は、並列計算装置１４を用いて行ってもよい。
【００３９】
図８は、代表ベクトルの木構造の一例を示す図である。クラスタ生成部６２が上述の２段階の処理を行う場合、２段階のクラスタに対応する２段階の代表ベクトルが木構造を構成する。上位代表ベクトルの数は１０２４個であり、上位代表ベクトルのそれぞれは、５１２個の代表特徴ベクトルの親となっている。画像検索部５２は、代表ベクトルが木構造を構成するように親子関係があることを利用して検索を行う。
【００４０】
図９は、画像検索部５２の機能構成を示す機能ブロック図である。画像検索部５２は、機能的に、代表ベクトル転送部８１、クエリ特徴ベクトル取得部８２、上位代表ベクトル距離計算部８３、代表クラスタ選択部８４、代表特徴ベクトル距離計算部８５、画像特徴クラスタ選択部８６、画像特徴ベクトル転送部８７、画像特徴ベクトル距離計算部８８、および検索結果画像選択部８９を含む。
【００４１】
代表ベクトル転送部８１は、主に並列計算装置１４と、記憶部１２とにより実現される。代表ベクトル転送部８１は、木構造代表ベクトル格納部７２に格納され、上位代表ベクトルおよびそれぞれ画像特徴クラスタを代表する複数の代表特徴ベクトルを、複数のプロセッサ４１から共通にアクセスできる装置内メモリ４５に転送する。代表ベクトル転送部８１は、具体的には並列計算装置１４やバス１５のＤＭＡ（Direct Memory Access）機能を用いて記憶部１２から装置内メモリ４５に上記データを転送する。
【００４２】
図１０は、装置内メモリ４５でのデータ配置の一例を示す図である。装置内メモリ４５には、代表特徴ベクトルを格納する領域と、上位代表ベクトルを格納する領域と、１つの画像特徴クラスタを格納する領域とが設けられる。代表ベクトル転送部８１は、記憶部１２に記憶される複数の代表ベクトルの情報を、予め割り当てられた装置内メモリ４５のメモリ領域に格納する。画像特徴クラスタを格納する領域へのデータの格納については後述する。
【００４３】
ここで、代表特徴ベクトルの要素数が１２８次元、代表特徴ベクトルの数は画像特徴クラスタの数と同じ（１０２４×５１２）個、各要素が１バイトの整数型とすると、その複数の代表特徴ベクトルの全てのデータ量は、（１０２４×５１２×１２８）バイト（Ｂ）、つまり６４ＭＢとなる。また、この場合、複数の上位代表ベクトルの数は１０２４であるので、同様に複数の上位代表ベクトルのデータ量は（１０２４×１２８）バイト、つまり１２８ＫＢとなる。例えば現行のＧＰＵに搭載される装置内メモリ４５のメモリ容量は１ＧＢ程度であり、装置内メモリ４５の容量も１ＧＢであるとすると、複数の代表ベクトルのデータ量は装置内メモリ４５の容量より小さい。
【００４４】
一方、画像の数が１００万、１つの画像から抽出される画像特徴ベクトル２０の数が３００とすると、複数の画像特徴クラスタに含まれる画像特徴ベクトル２０のデータ量は、（１００万×３００×１２８）バイト、つまり約３６ＧＢになり、装置内メモリ４５には格納できない。一方、１つの画像特徴クラスタあたりの平均的な画像特徴ベクトル２０の数は、（１００万×３００÷（１０２４×５１２））、つまり約６００であるので、データ量は７５ＫＢ程度である。クラスタリングにより画像特徴クラスタに含まれる画像特徴ベクトル２０の数が多少変動したとしても、複数の代表特徴ベクトルのデータ量と、複数の上位代表ベクトルのデータ量と、１つの画像特徴クラスタに含まれる画像特徴ベクトル２０のデータ量との和は、装置内メモリ４５の容量より小さくなる。
【００４５】
図１１は、装置内メモリ４５での代表ベクトルの配置の一例を示す図である。装置内メモリ４５に格納される代表ベクトルの各要素のサイズは４バイトであり、要素の順に並んでいる。また、ある代表ベクトルのデータの先頭アドレスは、装置内メモリ４５から一括して読み出すことのできるデータのバイト数（例えば３２や６４）の倍数となっている。このデータ構造は、後述する距離計算の処理において、装置内メモリ４５に格納されるデータを複数のプロセッサ４１に一括して読込ませるためのものである。代表ベクトル転送部８１は、代表ベクトルの各要素のサイズが１バイトであっても、一括して読込むために、各要素のサイズを４バイトに変換したデータを装置内メモリ４５に転送している。なお、上位代表ベクトルや、１つの画像特徴クラスタ内の画像特徴ベクトル２０も、同様のデータ構造によって装置内メモリ４５に格納される。装置内メモリ４５内での複数の代表特徴ベクトル、複数の上位代表ベクトル、および１つの画像特徴クラスタに含まれる画像特徴ベクトル２０のデータ量は４倍になるが、この例ではそれらのデータ量の和が装置内メモリ４５の容量より小さい点は変わりない。本実施形態においては、少なくとも装置内メモリ４５内での複数の代表特徴ベクトル、および複数の上位代表ベクトルのデータ量の和が装置内メモリ４５の容量に収まるように、画像特徴クラスタや代表ベクトルの数を調整すればよい。
【００４６】
クエリ特徴ベクトル取得部８２は、主にＣＰＵ１１、記憶部１２、および並列計算装置１４によって実現される。クエリ特徴ベクトル取得部８２は、クエリ画像から抽出される１または複数のクエリ特徴ベクトルを取得し、共通メモリである装置内メモリ４５に格納する。
【００４７】
クエリ特徴ベクトル取得部８２は、はじめに、クエリ画像を、クライアント装置３からウェブサーバ２を介して取得する。図１２は、クエリ画像を入力する画面の一例を示す図である。クライアント装置３は、ウェブサーバ２が生成したデータにより本画面を表示する。クエリ画像は、ユーザがクライアント装置３内の画像ファイルをアップロードすることで取得されてもよいし、なんらかのウェブページに表示される画像のＵＲＬを送ることで取得されてもよいし、写真共有サービス等に格納される画像からクエリ画像を選択することで取得されてもよい。次に、クエリ特徴ベクトル取得部８２は、ウェブサーバ２から、取得したクエリ画像を取得し、そのクエリ画像から１または複数のクエリ特徴ベクトルを抽出し取得する。クエリ特徴ベクトルは、画像特徴ベクトル抽出部６１が画像特徴ベクトル２０を抽出する手法と同じ手法を用いて生成される。次にクエリ特徴ベクトル取得部８２はクエリ特徴ベクトルを装置内メモリ４５に格納する。ここで、ＣＰＵ１１がクエリ特徴ベクトルを抽出し、並列計算装置１４がクエリ特徴ベクトルを装置内メモリ４５にロードしてもよいし、クエリ画像を並列計算装置１４にロードし、並列計算装置１４がクエリ特徴ベクトルを抽出して装置内メモリ４５に格納してもよい。
【００４８】
上位代表ベクトル距離計算部８３は、並列計算装置１４を中心として実現される。上位代表ベクトル距離計算部８３は、複数の上位代表ベクトルのそれぞれと、クエリ特徴ベクトルとの距離とを、複数の並列のプロセッサ４１を用いて計算する。以下では上位代表ベクトル距離計算部８３での距離計算の詳細について説明する。なお、上位代表ベクトル距離計算部８３、代表クラスタ選択部８４、代表特徴ベクトル距離計算部８５、画像特徴クラスタ選択部８６および画像特徴ベクトル距離計算部８８の処理は、クエリ画像から抽出されたクエリ特徴ベクトルのそれぞれについて行う。
【００４９】
図１３は距離計算の処理フローの一例を示す図である。はじめに、上位代表ベクトル距離計算部８３は、クエリ特徴ベクトルを装置内メモリ４５から距離計算を行う並列実行部４０の高速メモリ４３にロードする（ステップＳ１０１）。次に、計算対象となるベクトル（ここでは上位代表ベクトル）の各要素を装置内メモリ４５からその要素の計算を行うプロセッサ４１のレジスタにロードする（ステップＳ１０２）。この際、複数のプロセッサ４１は、装置内メモリ４５から計算対象ベクトルのデータを一括で読込む。それは、計算対象となるベクトルのデータが代表ベクトル転送部８１等によって予めその一括の読込ができるよう装置内メモリ４５に記憶されているからである。次に、上位代表ベクトル距離計算部８３は、レジスタに格納された計算対象となるベクトルの要素と、その要素に対応するクエリ特徴ベクトルの要素とを減算し、さらにその減算結果を２乗する（ステップＳ１０３）。次に、計算対象となるベクトルの各要素についてのステップＳ１０３の計算結果を合計する（ステップＳ１０４）。そして、上位代表ベクトル距離計算部８３は、合計結果を装置内メモリ４５に格納する（ステップＳ１０５）。なお、ある並列実行部４０に含まれる、同一の命令を実行するプロセッサ４１の数がクエリ特徴ベクトルや計算対象となるベクトルの要素の数より少なければ、ステップＳ１０２からステップＳ１０４の処理は、プロセッサ４１の数にあわせて分割され、複数回実行される。また、並列実行部４０が複数ある場合、別の並列実行部４０に、上位代表ベクトル距離計算部８３は、別の計算対象となるベクトルについてステップＳ１０１からＳ１０５の処理を実行させる。また、クエリ画像から抽出された他のクエリ特徴ベクトルについても並列に計算してもよい。こうすることで、クエリ特徴ベクトルと他の複数の計算対象のベクトルとの距離計算はＧＰＵのような並列計算装置１４の並列計算能力にあわせて並列に計算される。この距離計算の処理内容からわかるように、装置内メモリ４５に適切に配置された複数のベクトルと、クエリ特徴ベクトルとの距離計算はＧＰＵのようなハードウェアと親和性が高く、非常に高速に処理される。
【００５０】
代表クラスタ選択部８４は、並列計算装置１４を中心として実現される。代表クラスタ選択部８４は、上位代表ベクトル距離計算部８３で計算されたクエリ特徴ベクトルと複数の上位代表ベクトルのそれぞれとの距離に基づいて、複数の代表特徴ベクトルの集合から１つの集合を選択する。より詳細には、例えば、クエリ特徴ベクトルとの距離が最も短い上位代表ベクトルの子となる複数の代表特徴ベクトルの集合を選択する。この代表特徴ベクトルの集合のそれぞれは１段目のクラスタ（代表クラスタ）に対応する。代表特徴ベクトルの集合の選択は、それに対応する代表クラスタの選択にも相当する。なお、上位代表ベクトルのそれぞれは、複数の代表特徴ベクトルを代表しているとみることもできる。代表クラスタ選択部８４は、より具体的には、その代表ベクトルの集合を格納するメモリ内の領域の先頭アドレスを計算することによってその集合を選択する。例えば、ある上位代表ベクトルの子となる代表特徴ベクトルの数を上位代表ベクトルにかかわらず一定とすれば、距離が最も短い上位代表ベクトルが何番目かわかれば、かけ算等の単純な計算で先頭アドレスを求めることが可能となる。そうすれば、分岐や追加のメモリアクセスを必要とするような演算を用いずに済むため、ＧＰＵのようなハードウェアの性能をより活かした処理ができる。
【００５１】
代表特徴ベクトル距離計算部８５は、並列計算装置１４を中心として実現される。代表特徴ベクトル距離計算部８５は、複数の代表特徴ベクトルの少なくとも一部のそれぞれと、クエリ特徴ベクトルとの距離とを、複数の並列のプロセッサ４１を用いて計算する。ここで計算対象となる代表特徴ベクトルは、代表クラスタ選択部８４で選択された集合に属する代表特徴ベクトルである。代表特徴ベクトル距離計算部８５は、上位代表ベクトル距離計算部８３が距離を計算するものと同様に、図１３のフローに従い距離を計算する。ただし、計算対象ベクトルは上述の代表特徴ベクトルである。上位代表ベクトル距離計算部８３と同様に、この処理内容はＧＰＵのようなハードウェアと親和性が高く、非常に高速に処理される。
【００５２】
画像特徴クラスタ選択部８６は、並列計算装置１４を中心として実現される。画像特徴クラスタ選択部８６は、代表特徴ベクトル距離計算部８５で計算されたクエリ特徴ベクトルと複数の代表特徴ベクトルのそれぞれとの距離に基づいて、複数の画像特徴クラスタから画像特徴クラスタを選択する。より詳細には、例えば、クエリ特徴ベクトルとの距離が最も短い代表特徴ベクトルが代表する画像特徴クラスタを選択する。
【００５３】
画像特徴ベクトル転送部８７は、記憶部１２および並列計算装置１４を中心として実現される。画像特徴ベクトル転送部８７は画像特徴クラスタ選択部８６で選択された画像特徴クラスタに属する複数の画像特徴ベクトル２０を、クラスタベクトル格納部７１から、複数のプロセッサ４１から共通にアクセスできる装置内メモリ４５に転送する。画像特徴ベクトル転送部８７は、並列計算装置１４やバス１５のＤＭＡ機能を用いて記憶部１２から装置内メモリ４５に上記データを転送する。画像特徴ベクトル転送部８７は、図１１において代表ベクトル転送部８１が代表特徴ベクトル等を転送するのと同じように、装置内メモリ４５に格納されるデータを複数のプロセッサ４１に一括して読込ませるように画像特徴ベクトル２０のデータを配置する。
【００５４】
画像特徴ベクトル距離計算部８８は、並列計算装置１４を中心として実現される。画像特徴ベクトル距離計算部８８は、複数の画像特徴ベクトル２０のそれぞれと、クエリ特徴ベクトルとの距離とを、複数の並列のプロセッサ４１を用いて計算する。ここで計算に用いる画像特徴ベクトル２０は、画像特徴クラスタ選択部８６で選択された画像特徴クラスタに属する画像特徴ベクトル２０である。そのデータは画像特徴ベクトル転送部８７により装置内メモリ４５に転送されている。画像特徴ベクトル距離計算部８８は、上位代表ベクトル距離計算部８３が距離を計算するものと同様に、クエリ特徴ベクトルのそれぞれについて、図１３のフローに従い距離を計算する。ただし、計算対象ベクトルは画像特徴ベクトル２０である。上位代表ベクトル距離計算部８３と同様に、この処理内容はＧＰＵのようなハードウェアと親和性が高く、非常に高速に処理される。
【００５５】
検索結果画像選択部８９は、並列計算装置１４を中心として実現される。検索結果画像選択部８９は、画像特徴ベクトル距離計算部８８の計算結果に基づいて、検索対象となる複数の画像のうちいずれかを検索結果として選択する。まず、検索結果画像選択部８９は、画像特徴ベクトル距離計算部８８で計算された、クエリ特徴ベクトルと複数の画像特徴ベクトル２０のそれぞれとの距離に基づいて、その距離計算に用いたクエリ特徴ベクトルに対応する画像を取得する。より詳細には、例えば、クエリ特徴ベクトルごとに、そのクエリ特徴ベクトルとの距離が最も短い画像特徴ベクトル２０が抽出された画像特徴ベクトル２０を選択し、その画像特徴ベクトル２０が抽出された画像を取得する。その取得された画像の画像ＩＤは、装置内メモリ４５に格納する。
【００５６】
次に、検索結果画像選択部８９は、それぞれクエリ特徴ベクトルのいずれかに対応する複数の取得された画像を統計処理し、クエリとなる画像に対して類似している１または複数の画像を選択する。図１４は、クエリ特徴ベクトルに対応する画像を統計処理した結果の一例を示す図である。図１４の例では、検索結果画像選択部８９は、選択された画像ごとに、その画像に対応するクエリ特徴ベクトルの数（検索された回数）をカウントして画像ごとにスコアリングしている。そのスコアリングされた数値の大きい方から降順にソートする統計処理を行っている。クエリ画像から抽出される複数のクエリ特徴ベクトル画像のそれぞれについて画像が選択されるので、それを統計処理することで距離計算によって選択された画像からどの画像がクエリ画像に類似するかを評価することができる。この統計結果から、検索結果画像選択部８９は１または複数の画像を検索結果の画像として選択し、ウェブサーバ２に選択した画像の情報を出力する。選択される画像は、例えば検索された回数が最も多い画像でもよいし、その回数の多い順で上位いくつかであってもよい。ウェブサーバ２は、クライアント装置３に検索結果の画像を表示させる情報を出力する。
【００５７】
これまでの説明からわかるように、上位代表ベクトル距離計算部８３から画像特徴ベクトル距離計算部８８までの処理はＧＰＵなどの並列計算を行うハードウェアとの親和性が高く、その並列計算能力をフルに活かすことができる。また検索結果画像選択部８９の処理も、ある程度並列処理が可能であり、ＣＰＵ１１も用いるより高速に処理を行うことができる。また検索結果画像選択部８９の処理量は上位代表ベクトル距離計算部８３から画像特徴ベクトル距離計算部８８までの処理に比べれば小さいため、全体の処理時間に対する本処理の処理時間の割合は十分に小さい。これらにより、ＧＰＵによる処理時間の短縮効果を十分に享受することができる。
【００５８】
上述の説明では、画像特徴ベクトル距離計算部８８および検索結果画像選択部８９の処理は並列計算装置１４を中心にして行っているが、ＣＰＵ１１を中心として行ってもよい。その他の処理をＧＰＵに実行させるだけでも高速化の効果が得られるからである。また画像特徴ベクトル距離計算部８８および検索結果画像選択部８９の処理をＣＰＵ１１で行えば、画像特徴ベクトル転送部８７の処理を省略できるので、代表特徴ベクトルの距離計算などに比べれば、ＣＰＵ１１で処理を行うことによる計算時間の増加は抑えられる。
【００５９】
なお、本実施形態では上位代表ベクトルと代表特徴ベクトルのように代表ベクトルが２段階の木構造の構成になっているが、上位代表ベクトルを設けない１段の構成にしてもよい。その場合、上位代表ベクトル距離計算部８３および代表クラスタ選択部８４の処理は不要であり、代表特徴ベクトル距離計算部８５は全ての代表特徴ベクトルについて距離計算を行う。また、上位代表ベクトルの親となる親代表ベクトルを設け、３段以上の構成にしてもよい。３段以上の構成とする場合、上位代表ベクトル距離計算部８３の前にその親代表ベクトルとの距離計算をする処理と、その中から上位代表ベクトルの集合を選択する処理とが行われ、上位代表ベクトル距離計算部８３は、その選択された上位代表ベクトルの集合（一部の上位代表ベクトル）について距離計算を行う。
【００６０】
図１５は、インデックス追加部５３の機能構成を示す機能ブロック図である。インデックス追加部５３は、機能的に、追加特徴ベクトル抽出部９１と、追加特徴ベクトル距離計算部９２と、追加クラスタ選択部９３と、画像特徴ベクトル追加部９４とを含む。
【００６１】
追加特徴ベクトル抽出部９１は、主にＣＰＵ１１および記憶部１２により実現される。追加特徴ベクトル抽出部９１は、記憶部１２に格納されている検索対象として追加される画像から、複数の画像特徴ベクトル２０を抽出する。この抽出の手法は、画像特徴ベクトル抽出部６１と同じ手法でよい。以下、この画像特徴ベクトル２０を、追加特徴ベクトルと記す。
【００６２】
追加特徴ベクトル距離計算部９２は、並列計算装置１４を中心として実現される。追加特徴ベクトル距離計算部９２は、追加特徴ベクトルと、木構造代表ベクトル格納部７２に格納される代表特徴ベクトルのそれぞれとの距離を計算する。その距離は、図１３に示す処理方法におけるクエリ特徴ベクトルと計算対象となるベクトルとを、それぞれ追加特徴ベクトルと全ての代表クラスタに含まれる代表特徴ベクトルとに替えたフローに基づいて計算される。
【００６３】
追加クラスタ選択部９３は、並列計算装置１４を中心として計算される。追加クラスタ選択部９３は、追加特徴ベクトル距離計算部９２の計算結果に基づいて、追加特徴ベクトルの属する画像特徴クラスタを選択する。例えば、追加特徴ベクトルのそれぞれについて、その追加特徴ベクトルとの距離が最も短い代表特徴ベクトルが代表する画像特徴クラスタをその追加特徴ベクトルに対応する画像特徴クラスタとして選択する。
【００６４】
画像特徴ベクトル追加部９４は、ＣＰＵ１１および記憶部１２を中心として実現される。画像特徴ベクトル追加部９４は、追加クラスタ選択部９３により選択された画像特徴クラスタにそれに対応する追加特徴ベクトルを追加し、その画像特徴クラスタのデータをクラスタベクトル格納部７１に格納する。こうすることで、検索対象となる画像を追加する場合にも、再度クラスタリングすることなく追加される画像を検索対象に加えることができ、その追加に伴う処理時間を節約することができる。
【符号の説明】
【００６５】
１ 画像検索装置、２ ウェブサーバ、３ クライアント装置、１１ ＣＰＵ、１２ 記憶部、１３ 通信部、１４ 並列計算装置、１５ バス、２０ 画像特徴ベクトル、４０ 並列実行部、４１ プロセッサ、４２ 命令ユニット、４３ 高速メモリ、４５ 装置内メモリ、５１ インデックス生成部、５２ 画像検索部、５３ インデックス追加部、６１ 画像特徴ベクトル抽出部、６２ クラスタ生成部、７１ クラスタベクトル格納部、７２ 木構造代表ベクトル格納部、８１ 代表ベクトル転送部、８２ クエリ特徴ベクトル取得部、８３ 上位代表ベクトル距離計算部、８４ 代表クラスタ選択部、８５ 代表特徴ベクトル距離計算部、８６ 画像特徴クラスタ選択部、８７ 画像特徴ベクトル転送部、８８ 画像特徴ベクトル距離計算部、８９ 検索結果画像選択部、９１ 追加特徴ベクトル抽出部、９２ 追加特徴ベクトル距離計算部、９３ 追加クラスタ選択部、９４ 画像特徴ベクトル追加部。
【技術分野】
【０００１】
本発明は画像検索装置およびプログラムに関する。
【背景技術】
【０００２】
ネットワーク技術等の発達によって、膨大な量の画像ファイルが管理されるようになっている。その大量の画像の中から、クエリとなる画像に類似する画像を選び出す画像検索技術がある。大量の画像の中から高速に画像を選択するために、ＢｏＦ（Bag of Features）法と呼ばれる検索手法の開発が進んでいる。この手法は、ＢｏＷ(Bag of Words)法と呼ばれる文書検索の手法を応用したものである。ＢｏＦ法では、検索対象となる画像から抽出される特徴ベクトルのそれぞれをＢｏＷ法における単語に相当するＶｉｓｕａｌ Ｗｏｒｄに対応させ、このＶｉｓｕａｌ Ｗｏｒｄの出現頻度を用いて類似する画像を検索する。
【０００３】
特許文献１には、クエリとなる画像から抽出される複数の画像特徴量ベクトルを、クラスタリングを用いてより少ないベクトルに変換し、その変換されたベクトルをクエリとして画像の検索を行う技術が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１１−１０７７９５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、画像データは文字データに比較してそのデータ量が膨大であるため、通常のＣＰＵを用いて文字と同様な高速検索を行うには、処理量を削減することが必要になる。このため、検索インデックスの生成時にその画像データの特徴を的確に表せないＶｉｓｕａｌ Ｗｏｒｄを用いなければなければならないなど、充分な検索精度を得ることが難しくなっていた。
【０００６】
そこで、例えば所謂ＧＰＵ（Graphic Processing Unit）のような、複数のプロセッサおよび共通メモリを含み、複数のプロセッサはそれぞれ共通メモリから効率的にデータを取込み、また共通のプログラムを実行して演算処理を行うことができる、ＣＰＵよりも計算能力の高いハードウェアを用いることが考えられる。演算処理が高速に行われるのであれば、精度を確保しつつ高速検索することが可能となるからである。
【０００７】
しかしながら、上記したようなＢｏＦ法などはＣＰＵに最適化された手順であり、疎行列等を扱うためにリンクドリストのデータ構造や分岐処理を多用する。それらは、上述のような特徴を有するＧＰＵのアーキテクチャとの親和性が低いため、ＧＰＵをそのまま用いてもその能力を充分に活かすことができなかった。
【０００８】
本発明は上記課題を鑑みてなされたものであって、その目的は、ＧＰＵのように同種の処理を大量に行う能力の高いハードウェアを用いて、画像検索処理を高速化することにある。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明にかかる画像検索装置は、共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含み、さらに、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段と、クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを取得し、前記共通メモリに格納するクエリ特徴ベクトル取得手段と、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算手段と、前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算手段と、前記第２の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択する手段と、を含むことを特徴とする。
【００１０】
また、本発明にかかるプログラムは、共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータを、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段、クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定手段、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算手段、前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算手段、および、前記第２の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択する手段、として機能させることを特徴とする。
【００１１】
また、本発明にかかる画像検索方法は、共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータに画像を検索させる画像検索方法であって、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送ステップと、クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定ステップと、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算ステップと、前記第１の距離計算ステップによる計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算ステップと、前記第２の距離計算ステップによる計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択するステップと、を含むことを特徴とする。
【００１２】
また、本発明にかかるコンピュータ読み取り可能な記憶媒体は、共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータを、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段、クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定手段、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算手段、前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算手段、および、前記第２の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択する手段、として機能させるためのプログラムを記憶することを特徴とする。
【００１３】
本発明によれば、ＧＰＵのように同種の処理を大量に行う能力の高いハードウェアを用いて、画像検索処理を高速化することができる。代表ベクトルを用いることで距離計算の対象となる特徴ベクトルの数が減り、かつ距離計算が主体となるためＧＰＵのように同種の処理を大量に行えるハードウェアとの親和性が高いからである。
【００１４】
本発明の一態様では、前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルを前記記憶手段から前記共通メモリに転送する画像特徴ベクトル転送手段をさらに含み、前記第２の距離計算手段は、前記転送された画像特徴ベクトルと前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算しもよい。
【００１５】
本発明の一態様では、前記複数の代表特徴ベクトルのデータ量は、前記共通メモリの容量より小さくてもよい。
【００１６】
本発明の一態様では、前記複数のクラスタのうち１つに属する画像特徴ベクトルのデータ量は、前記共通メモリの容量より小さく、前記複数のクラスタに属する画像特徴ベクトルのデータ量は、前記共通メモリの容量より大きくてもよい。
【００１７】
本発明の一態様では、前記複数のクラスタのうち１つに属する画像特徴ベクトルと前記複数の代表ベクトルとのデータ量は、前記共通メモリの容量より小さく、前記画像特徴ベクトル転送手段は、前記選択されたクラスタに属する画像特徴ベクトルを、共通メモリに記憶されている他の画像特徴ベクトルと置き換えてもよい。
【００１８】
本発明の一態様では、追加される検索対象となる画像から複数の画像特徴ベクトルを抽出する追加画像特徴ベクトル抽出手段と、前記追加画像特徴ベクトル抽出手段により抽出された画像特徴ベクトルを前記画像特徴クラスタのうちいずれかに追加する画像特徴ベクトル追加手段と、をさらに含んでもよい。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施形態にかかる画像検索システムの構成の一例を示す図である。
【図２】本発明の実施形態にかかる画像検索装置の構成の一例を示す図である。
【図３】並列計算装置の構成の一例を示す図である。
【図４】本発明の実施形態にかかる画像検索装置の機能を示す機能ブロック図である。
【図５】インデックス生成部の機能構成を示す機能ブロック図である。
【図６】検索対象となる画像の一例を示す図である。
【図７】画像から抽出される画像特徴ベクトルの概念を示す図である。
【図８】代表ベクトルの木構造の一例を示す図である。
【図９】画像検索部の機能構成を示す機能ブロック図である。
【図１０】装置内メモリでのデータ配置の一例を示す図である。
【図１１】装置内メモリでの代表ベクトルの配置の一例を示す図である。
【図１２】クエリとなる画像を入力する画面の一例を示す図である。
【図１３】距離計算の処理フローの一例を示す図である。
【図１４】クエリ特徴ベクトルに対応する画像を統計処理した結果の一例を示す図である。
【図１５】インデックス追加部の機能構成を示す機能ブロック図である。
【発明を実施するための形態】
【００２０】
以下では、本発明の実施形態について図面に基づいて説明する。出現する構成要素のうち同一機能を有するものには同じ符号を付し、その説明を省略する。
【００２１】
図１は、本発明の実施形態にかかる画像検索システムの構成の一例を示す図である。画像検索システムは、画像検索装置１と、ウェブサーバ２と、クライアント装置３とを含む。ウェブサーバ２は、例えばウェブサーバプログラムが動作するサーバハードウェアであり、クライアント装置３は、例えばウェブブラウザのプログラムが動作するパーソナルコンピュータや、スマートフォンである。画像検索システムは画像検索を行う動作の概要は以下の通りである。はじめに、ウェブサーバ２は、インターネット等のネットワークを介してクライアント装置３から画像検索に用いるクエリとなる画像（以下、「クエリ画像」と記述する）を取得し、そのクエリ画像を画像検索装置１に入力させる。次に画像検索装置１は、入力された画像に類似する１または複数の画像を検索し、ウェブサーバ２に出力する。ウェブサーバ２は、画像検索装置１が検索した画像をクライアント装置３に表示させるデータを出力する。
【００２２】
図２は、本発明の実施形態にかかる画像検索装置１の構成の一例を示す図である。画像検索装置１は、ＣＰＵ１１、記憶部１２、通信部１３、並列計算装置１４およびバス１５を含む。
【００２３】
ＣＰＵ１１は、記憶部１２に格納されているプログラムに従って動作する。またＣＰＵ１１は通信部１３や並列計算装置１４を制御する。なお、上記プログラムは、インターネット等のネットワークを介して提供されるものであってもよいし、ＤＶＤ−ＲＯＭやＵＳＢメモリ等のコンピュータで読み取り可能な情報記録媒体に格納されて提供されるものであってもよい。
【００２４】
記憶部１２は、ＲＡＭやＲＯＭ等のメモリ素子やハードディスクドライブ等によって構成されている。記憶部１２は、上記プログラムを格納する。また、記憶部１２は、各部から入力される情報や演算結果を格納する。
【００２５】
通信部１３は、ウェブサーバ２等の他の装置と通信接続するためにネットワークカードなどが設けられる通信手段等で構成されている。通信部１３は、ＣＰＵ１１の制御に基づいて、他の装置から受信した情報をＣＰＵ１１や記憶部１２に入力し、他の装置に情報を送信する。
【００２６】
バス１５は、ＣＰＵ１１、記憶部１２、通信部１３および並列計算装置１４との間でデータをやりとりするためのものである。例えば、ＣＰＵ１１や記憶部１２と並列計算装置１４とはバス１５の中の拡張バスを介して接続される。
【００２７】
並列計算装置１４は、並列計算によって同種の計算を大量に行うことを得意とするハードウェアである。並列計算装置１４は、例えばＧＰＵである。図３は、並列計算装置１４の構成の一例を示す図である。並列計算装置１４は、複数の並列実行部４０と、装置内メモリ４５とを含む。また各並列実行部４０は、複数のプロセッサ４１と、命令ユニット４２と、高速メモリ４３とを含む。
【００２８】
複数のプロセッサ４１のそれぞれは、浮動小数点計算や、装置内メモリ４５や高速メモリ４３との間でのデータの読込みや書込み等の処理を行う。命令ユニット４２は、装置内メモリ４５等に格納されるプログラムに基づいて、その命令ユニット４２を含む並列実行部４０に含まれる複数のプロセッサ４１に処理をさせる。ある並列実行部４０に含まれる複数のプロセッサ４１は、その並列実行部４０に含まれる一つの命令ユニット４２からの指示によって、同一の命令を処理する。こうすると、複数のプロセッサ４１を１つの命令ユニット４２で制御できるため、命令ユニット４２の回路の規模の増加を抑えることができるため、並列計算装置１４に含まれるプロセッサ４１の数をＣＰＵ１１に比べて増やすことが可能になる。
【００２９】
装置内メモリ４５は、記憶部１２に用いられるＲＡＭより高速にアクセス可能なＤＲＡＭからなる。装置内メモリ４５は、バス１５を介して、ＣＰＵ１１や記憶部１２と接続されている。なお、並列計算装置１４は、ＤＭＡ転送により装置内メモリ４５と記憶部１２との間でデータを転送する回路も有する。高速メモリ４３は、装置内メモリ４５より高速にアクセス可能なＳＲＡＭ等からなる。プロセッサ４１が高速メモリ４３にアクセスする際のレイテンシは、プロセッサ４１がその内部レジスタにアクセスする際のレイテンシとほとんど変わらない。ここで、装置内メモリ４５も高速メモリ４３も複数のプロセッサ４１から共通にアクセスできる共通メモリである。
【００３０】
図４は、本発明の実施形態にかかる画像検索装置１の機能を示す機能ブロック図である。画像検索装置１は、機能的に、インデックス生成部５１、画像検索部５２、およびインデックス追加部５３を含む。これらの機能は、ＣＰＵ１１が記憶部１２に格納されたプログラムを実行し、通信部１３や並列計算装置１４を制御し、また、並列計算装置１４がその並列計算装置１４向けのプログラムを実行することで実現される。
【００３１】
インデックス生成部５１は、検索対象となる複数の画像から、画像検索の際に用いる画像特徴ベクトル２０や、その画像特徴ベクトル２０の選択を容易にするインデックスを生成する。画像検索部５２は、インデックスや画像特徴ベクトル２０を用いて、クエリ画像に類似する画像を検索する。インデックス追加部５３は、追加の画像から画像特徴ベクトル２０を生成し、またその追加の画像を選択できるようインデックスを変更する。
【００３２】
図５は、インデックス生成部５１の機能構成を示す機能ブロック図である。インデックス生成部５１は、機能的に、画像特徴ベクトル抽出部６１と、クラスタ生成部６２とを含む。クラスタ生成部６２は、クラスタのインデックスとなる代表ベクトルの木構造を生成し、木構造代表ベクトル格納部７２にインデックスに関連する情報を格納する。また、クラスタベクトル格納部７１は、その木構造の葉となる代表ベクトルが代表するクラスタに属する画像特徴ベクトル２０の情報を格納する。クラスタベクトル格納部７１、木構造代表ベクトル格納部７２は、具体的には記憶部１２により構成される。
【００３３】
画像特徴ベクトル抽出部６１は、主にＣＰＵ１１および記憶部１２により実現される。画像特徴ベクトル抽出部６１は、記憶部１２に格納されている複数の画像であって検索対象となる複数の画像から、複数の画像特徴ベクトル２０を抽出する。より具体的には、画像特徴ベクトル抽出部６１は、その複数の画像のそれぞれから、１または複数の画像特徴ベクトル２０を抽出し、抽出された画像特徴ベクトル２０を、その画像特徴ベクトル２０が抽出された画像と関連付けて記憶部１２に記憶させる。
【００３４】
図６は、検索対象となる画像の一例を示す図である。図７は、画像から抽出される画像特徴ベクトル２０の概念を示す図である。画像から抽出される画像特徴ベクトル２０のそれぞれは、その画像の局所的な特徴を示す局所特徴量である。画像特徴ベクトル２０のそれぞれは、例えば１２８の要素（次元）をもつベクトルである。画像特徴ベクトル２０を抽出するためには、ＳＩＦＴ（Scale-Invariant Feature transform）、ＳＵＲＦ（Speeded Up Robust Features）などの公知の手法を用いてよい。画像特徴ベクトル２０のそれぞれが有する要素の数は、画像からの抽出の手法などに応じて変化させてよい。また１つの画像から抽出される画像特徴ベクトル２０の数は、予め定められた数（例えば３００）としてよいが、単純な画像から抽出される画像特徴ベクトル２０の数はその予め定められた数より少なくなってもよい。
【００３５】
クラスタ生成部６２は、主にＣＰＵ１１および記憶部１２により実現される。クラスタ生成部６２は、クラスタリングにより、画像特徴ベクトル抽出部６１により抽出された複数の画像特徴ベクトル２０のそれぞれを、複数のクラスタのいずれかに分類する。画像特徴ベクトル２０をクラスタに分類する処理は１段階の処理とは限らず、多段階の処理であってよい。また、その多段階の処理は、以下の処理を再帰的に呼び出すことにより実現してもよい。以下では、２段階の処理を行い、かつ１段目で画像特徴ベクトル抽出部６１により抽出された複数の画像特徴ベクトル２０を１０２４個のクラスタに分類し、さらに２段目でその１０２４個のクラスタのそれぞれを５１２個のクラスタに分類する場合の例について説明する。
【００３６】
クラスタ生成部６２の各段の処理では、クラスタリングにより、与えられた複数の画像特徴ベクトル２０を与えられた個数のクラスタに分類し、複数のクラスタを生成し、さらにその生成されたクラスタの代表ベクトルを生成し、生成された代表ベクトルをその段の代表ベクトルとして木構造代表ベクトル格納部７２に格納する。処理中の段が最下段でない場合は、クラスタ生成部６２は処理中の段で生成されたクラスタのそれぞれに属する複数の画像特徴ベクトル２０を入力情報として、次の段の処理を再帰的に呼び出す。代表ベクトルは、例えばその分類されたクラスタに属する画像特徴ベクトル２０の重心であり、そのクラスタを代表するベクトルである。またクラスタ生成部６２は、最下段の処理で生成されたクラスタごとに、そのクラスタに属する画像特徴ベクトル２０をクラスタベクトル格納部７１に格納する。
【００３７】
上述の例の場合、１段目の処理では、クラスタ生成部６２は、与えられた画像特徴ベクトル２０を１０２４個のクラスタに分類し、その分類された１段目の各クラスタの代表ベクトルを生成し、生成された１段目の代表ベクトルを木構造代表ベクトル格納部７２に格納する。２段目の処理では、クラスタ生成部６２は、１段目に生成された１０２４個のクラスタのそれぞれに属する複数の画像特徴ベクトル２０を入力情報として、更に５１２個のクラスタに分類し、その分類された２段目の各クラスタの代表ベクトルを生成し、生成された下位の段の代表ベクトルを木構造代表ベクトル格納部７２に格納する。２段目のクラスタを全て生成するとその２段目のクラスタの総数は（１０２４×５１２）個となる。さらにクラスタ生成部６２は、２段目に生成されたクラスタごとに、そのクラスタに属する画像特徴ベクトル２０をクラスタベクトル格納部７１に格納する。以下では、説明の容易のため、１段目のクラスタを代表する代表ベクトルを上位代表ベクトルと記し、最下段（上述の例では２段目）のクラスタを代表する代表ベクトルを代表特徴ベクトルと記す。また最終的に生成されたクラスタ（上述の例では２段目のクラスタ）を画像特徴クラスタとも記す。
【００３８】
画像特徴ベクトル２０をクラスタに分類する際には、ｋ−ｍｅａｎｓ法等の公知のクラスタリング手法を用いればよい。クラスタの数は、後述の画像検索部５２の処理との関係で、２のべき乗が好適であるが、２のべき乗でなくてもよい。また全ての画像に含まれる画像特徴ベクトル２０を分類すると、それぞれの画像特徴クラスタには、複数の画像特徴ベクトル２０が属する。クラスタ生成部６２の再帰処理を２段階行う事で、木構造代表ベクトル格納部７２に、２階層の情報を格納する事ができる。クラスタ生成部６２の計算は、並列計算装置１４を用いて行ってもよい。
【００３９】
図８は、代表ベクトルの木構造の一例を示す図である。クラスタ生成部６２が上述の２段階の処理を行う場合、２段階のクラスタに対応する２段階の代表ベクトルが木構造を構成する。上位代表ベクトルの数は１０２４個であり、上位代表ベクトルのそれぞれは、５１２個の代表特徴ベクトルの親となっている。画像検索部５２は、代表ベクトルが木構造を構成するように親子関係があることを利用して検索を行う。
【００４０】
図９は、画像検索部５２の機能構成を示す機能ブロック図である。画像検索部５２は、機能的に、代表ベクトル転送部８１、クエリ特徴ベクトル取得部８２、上位代表ベクトル距離計算部８３、代表クラスタ選択部８４、代表特徴ベクトル距離計算部８５、画像特徴クラスタ選択部８６、画像特徴ベクトル転送部８７、画像特徴ベクトル距離計算部８８、および検索結果画像選択部８９を含む。
【００４１】
代表ベクトル転送部８１は、主に並列計算装置１４と、記憶部１２とにより実現される。代表ベクトル転送部８１は、木構造代表ベクトル格納部７２に格納され、上位代表ベクトルおよびそれぞれ画像特徴クラスタを代表する複数の代表特徴ベクトルを、複数のプロセッサ４１から共通にアクセスできる装置内メモリ４５に転送する。代表ベクトル転送部８１は、具体的には並列計算装置１４やバス１５のＤＭＡ（Direct Memory Access）機能を用いて記憶部１２から装置内メモリ４５に上記データを転送する。
【００４２】
図１０は、装置内メモリ４５でのデータ配置の一例を示す図である。装置内メモリ４５には、代表特徴ベクトルを格納する領域と、上位代表ベクトルを格納する領域と、１つの画像特徴クラスタを格納する領域とが設けられる。代表ベクトル転送部８１は、記憶部１２に記憶される複数の代表ベクトルの情報を、予め割り当てられた装置内メモリ４５のメモリ領域に格納する。画像特徴クラスタを格納する領域へのデータの格納については後述する。
【００４３】
ここで、代表特徴ベクトルの要素数が１２８次元、代表特徴ベクトルの数は画像特徴クラスタの数と同じ（１０２４×５１２）個、各要素が１バイトの整数型とすると、その複数の代表特徴ベクトルの全てのデータ量は、（１０２４×５１２×１２８）バイト（Ｂ）、つまり６４ＭＢとなる。また、この場合、複数の上位代表ベクトルの数は１０２４であるので、同様に複数の上位代表ベクトルのデータ量は（１０２４×１２８）バイト、つまり１２８ＫＢとなる。例えば現行のＧＰＵに搭載される装置内メモリ４５のメモリ容量は１ＧＢ程度であり、装置内メモリ４５の容量も１ＧＢであるとすると、複数の代表ベクトルのデータ量は装置内メモリ４５の容量より小さい。
【００４４】
一方、画像の数が１００万、１つの画像から抽出される画像特徴ベクトル２０の数が３００とすると、複数の画像特徴クラスタに含まれる画像特徴ベクトル２０のデータ量は、（１００万×３００×１２８）バイト、つまり約３６ＧＢになり、装置内メモリ４５には格納できない。一方、１つの画像特徴クラスタあたりの平均的な画像特徴ベクトル２０の数は、（１００万×３００÷（１０２４×５１２））、つまり約６００であるので、データ量は７５ＫＢ程度である。クラスタリングにより画像特徴クラスタに含まれる画像特徴ベクトル２０の数が多少変動したとしても、複数の代表特徴ベクトルのデータ量と、複数の上位代表ベクトルのデータ量と、１つの画像特徴クラスタに含まれる画像特徴ベクトル２０のデータ量との和は、装置内メモリ４５の容量より小さくなる。
【００４５】
図１１は、装置内メモリ４５での代表ベクトルの配置の一例を示す図である。装置内メモリ４５に格納される代表ベクトルの各要素のサイズは４バイトであり、要素の順に並んでいる。また、ある代表ベクトルのデータの先頭アドレスは、装置内メモリ４５から一括して読み出すことのできるデータのバイト数（例えば３２や６４）の倍数となっている。このデータ構造は、後述する距離計算の処理において、装置内メモリ４５に格納されるデータを複数のプロセッサ４１に一括して読込ませるためのものである。代表ベクトル転送部８１は、代表ベクトルの各要素のサイズが１バイトであっても、一括して読込むために、各要素のサイズを４バイトに変換したデータを装置内メモリ４５に転送している。なお、上位代表ベクトルや、１つの画像特徴クラスタ内の画像特徴ベクトル２０も、同様のデータ構造によって装置内メモリ４５に格納される。装置内メモリ４５内での複数の代表特徴ベクトル、複数の上位代表ベクトル、および１つの画像特徴クラスタに含まれる画像特徴ベクトル２０のデータ量は４倍になるが、この例ではそれらのデータ量の和が装置内メモリ４５の容量より小さい点は変わりない。本実施形態においては、少なくとも装置内メモリ４５内での複数の代表特徴ベクトル、および複数の上位代表ベクトルのデータ量の和が装置内メモリ４５の容量に収まるように、画像特徴クラスタや代表ベクトルの数を調整すればよい。
【００４６】
クエリ特徴ベクトル取得部８２は、主にＣＰＵ１１、記憶部１２、および並列計算装置１４によって実現される。クエリ特徴ベクトル取得部８２は、クエリ画像から抽出される１または複数のクエリ特徴ベクトルを取得し、共通メモリである装置内メモリ４５に格納する。
【００４７】
クエリ特徴ベクトル取得部８２は、はじめに、クエリ画像を、クライアント装置３からウェブサーバ２を介して取得する。図１２は、クエリ画像を入力する画面の一例を示す図である。クライアント装置３は、ウェブサーバ２が生成したデータにより本画面を表示する。クエリ画像は、ユーザがクライアント装置３内の画像ファイルをアップロードすることで取得されてもよいし、なんらかのウェブページに表示される画像のＵＲＬを送ることで取得されてもよいし、写真共有サービス等に格納される画像からクエリ画像を選択することで取得されてもよい。次に、クエリ特徴ベクトル取得部８２は、ウェブサーバ２から、取得したクエリ画像を取得し、そのクエリ画像から１または複数のクエリ特徴ベクトルを抽出し取得する。クエリ特徴ベクトルは、画像特徴ベクトル抽出部６１が画像特徴ベクトル２０を抽出する手法と同じ手法を用いて生成される。次にクエリ特徴ベクトル取得部８２はクエリ特徴ベクトルを装置内メモリ４５に格納する。ここで、ＣＰＵ１１がクエリ特徴ベクトルを抽出し、並列計算装置１４がクエリ特徴ベクトルを装置内メモリ４５にロードしてもよいし、クエリ画像を並列計算装置１４にロードし、並列計算装置１４がクエリ特徴ベクトルを抽出して装置内メモリ４５に格納してもよい。
【００４８】
上位代表ベクトル距離計算部８３は、並列計算装置１４を中心として実現される。上位代表ベクトル距離計算部８３は、複数の上位代表ベクトルのそれぞれと、クエリ特徴ベクトルとの距離とを、複数の並列のプロセッサ４１を用いて計算する。以下では上位代表ベクトル距離計算部８３での距離計算の詳細について説明する。なお、上位代表ベクトル距離計算部８３、代表クラスタ選択部８４、代表特徴ベクトル距離計算部８５、画像特徴クラスタ選択部８６および画像特徴ベクトル距離計算部８８の処理は、クエリ画像から抽出されたクエリ特徴ベクトルのそれぞれについて行う。
【００４９】
図１３は距離計算の処理フローの一例を示す図である。はじめに、上位代表ベクトル距離計算部８３は、クエリ特徴ベクトルを装置内メモリ４５から距離計算を行う並列実行部４０の高速メモリ４３にロードする（ステップＳ１０１）。次に、計算対象となるベクトル（ここでは上位代表ベクトル）の各要素を装置内メモリ４５からその要素の計算を行うプロセッサ４１のレジスタにロードする（ステップＳ１０２）。この際、複数のプロセッサ４１は、装置内メモリ４５から計算対象ベクトルのデータを一括で読込む。それは、計算対象となるベクトルのデータが代表ベクトル転送部８１等によって予めその一括の読込ができるよう装置内メモリ４５に記憶されているからである。次に、上位代表ベクトル距離計算部８３は、レジスタに格納された計算対象となるベクトルの要素と、その要素に対応するクエリ特徴ベクトルの要素とを減算し、さらにその減算結果を２乗する（ステップＳ１０３）。次に、計算対象となるベクトルの各要素についてのステップＳ１０３の計算結果を合計する（ステップＳ１０４）。そして、上位代表ベクトル距離計算部８３は、合計結果を装置内メモリ４５に格納する（ステップＳ１０５）。なお、ある並列実行部４０に含まれる、同一の命令を実行するプロセッサ４１の数がクエリ特徴ベクトルや計算対象となるベクトルの要素の数より少なければ、ステップＳ１０２からステップＳ１０４の処理は、プロセッサ４１の数にあわせて分割され、複数回実行される。また、並列実行部４０が複数ある場合、別の並列実行部４０に、上位代表ベクトル距離計算部８３は、別の計算対象となるベクトルについてステップＳ１０１からＳ１０５の処理を実行させる。また、クエリ画像から抽出された他のクエリ特徴ベクトルについても並列に計算してもよい。こうすることで、クエリ特徴ベクトルと他の複数の計算対象のベクトルとの距離計算はＧＰＵのような並列計算装置１４の並列計算能力にあわせて並列に計算される。この距離計算の処理内容からわかるように、装置内メモリ４５に適切に配置された複数のベクトルと、クエリ特徴ベクトルとの距離計算はＧＰＵのようなハードウェアと親和性が高く、非常に高速に処理される。
【００５０】
代表クラスタ選択部８４は、並列計算装置１４を中心として実現される。代表クラスタ選択部８４は、上位代表ベクトル距離計算部８３で計算されたクエリ特徴ベクトルと複数の上位代表ベクトルのそれぞれとの距離に基づいて、複数の代表特徴ベクトルの集合から１つの集合を選択する。より詳細には、例えば、クエリ特徴ベクトルとの距離が最も短い上位代表ベクトルの子となる複数の代表特徴ベクトルの集合を選択する。この代表特徴ベクトルの集合のそれぞれは１段目のクラスタ（代表クラスタ）に対応する。代表特徴ベクトルの集合の選択は、それに対応する代表クラスタの選択にも相当する。なお、上位代表ベクトルのそれぞれは、複数の代表特徴ベクトルを代表しているとみることもできる。代表クラスタ選択部８４は、より具体的には、その代表ベクトルの集合を格納するメモリ内の領域の先頭アドレスを計算することによってその集合を選択する。例えば、ある上位代表ベクトルの子となる代表特徴ベクトルの数を上位代表ベクトルにかかわらず一定とすれば、距離が最も短い上位代表ベクトルが何番目かわかれば、かけ算等の単純な計算で先頭アドレスを求めることが可能となる。そうすれば、分岐や追加のメモリアクセスを必要とするような演算を用いずに済むため、ＧＰＵのようなハードウェアの性能をより活かした処理ができる。
【００５１】
代表特徴ベクトル距離計算部８５は、並列計算装置１４を中心として実現される。代表特徴ベクトル距離計算部８５は、複数の代表特徴ベクトルの少なくとも一部のそれぞれと、クエリ特徴ベクトルとの距離とを、複数の並列のプロセッサ４１を用いて計算する。ここで計算対象となる代表特徴ベクトルは、代表クラスタ選択部８４で選択された集合に属する代表特徴ベクトルである。代表特徴ベクトル距離計算部８５は、上位代表ベクトル距離計算部８３が距離を計算するものと同様に、図１３のフローに従い距離を計算する。ただし、計算対象ベクトルは上述の代表特徴ベクトルである。上位代表ベクトル距離計算部８３と同様に、この処理内容はＧＰＵのようなハードウェアと親和性が高く、非常に高速に処理される。
【００５２】
画像特徴クラスタ選択部８６は、並列計算装置１４を中心として実現される。画像特徴クラスタ選択部８６は、代表特徴ベクトル距離計算部８５で計算されたクエリ特徴ベクトルと複数の代表特徴ベクトルのそれぞれとの距離に基づいて、複数の画像特徴クラスタから画像特徴クラスタを選択する。より詳細には、例えば、クエリ特徴ベクトルとの距離が最も短い代表特徴ベクトルが代表する画像特徴クラスタを選択する。
【００５３】
画像特徴ベクトル転送部８７は、記憶部１２および並列計算装置１４を中心として実現される。画像特徴ベクトル転送部８７は画像特徴クラスタ選択部８６で選択された画像特徴クラスタに属する複数の画像特徴ベクトル２０を、クラスタベクトル格納部７１から、複数のプロセッサ４１から共通にアクセスできる装置内メモリ４５に転送する。画像特徴ベクトル転送部８７は、並列計算装置１４やバス１５のＤＭＡ機能を用いて記憶部１２から装置内メモリ４５に上記データを転送する。画像特徴ベクトル転送部８７は、図１１において代表ベクトル転送部８１が代表特徴ベクトル等を転送するのと同じように、装置内メモリ４５に格納されるデータを複数のプロセッサ４１に一括して読込ませるように画像特徴ベクトル２０のデータを配置する。
【００５４】
画像特徴ベクトル距離計算部８８は、並列計算装置１４を中心として実現される。画像特徴ベクトル距離計算部８８は、複数の画像特徴ベクトル２０のそれぞれと、クエリ特徴ベクトルとの距離とを、複数の並列のプロセッサ４１を用いて計算する。ここで計算に用いる画像特徴ベクトル２０は、画像特徴クラスタ選択部８６で選択された画像特徴クラスタに属する画像特徴ベクトル２０である。そのデータは画像特徴ベクトル転送部８７により装置内メモリ４５に転送されている。画像特徴ベクトル距離計算部８８は、上位代表ベクトル距離計算部８３が距離を計算するものと同様に、クエリ特徴ベクトルのそれぞれについて、図１３のフローに従い距離を計算する。ただし、計算対象ベクトルは画像特徴ベクトル２０である。上位代表ベクトル距離計算部８３と同様に、この処理内容はＧＰＵのようなハードウェアと親和性が高く、非常に高速に処理される。
【００５５】
検索結果画像選択部８９は、並列計算装置１４を中心として実現される。検索結果画像選択部８９は、画像特徴ベクトル距離計算部８８の計算結果に基づいて、検索対象となる複数の画像のうちいずれかを検索結果として選択する。まず、検索結果画像選択部８９は、画像特徴ベクトル距離計算部８８で計算された、クエリ特徴ベクトルと複数の画像特徴ベクトル２０のそれぞれとの距離に基づいて、その距離計算に用いたクエリ特徴ベクトルに対応する画像を取得する。より詳細には、例えば、クエリ特徴ベクトルごとに、そのクエリ特徴ベクトルとの距離が最も短い画像特徴ベクトル２０が抽出された画像特徴ベクトル２０を選択し、その画像特徴ベクトル２０が抽出された画像を取得する。その取得された画像の画像ＩＤは、装置内メモリ４５に格納する。
【００５６】
次に、検索結果画像選択部８９は、それぞれクエリ特徴ベクトルのいずれかに対応する複数の取得された画像を統計処理し、クエリとなる画像に対して類似している１または複数の画像を選択する。図１４は、クエリ特徴ベクトルに対応する画像を統計処理した結果の一例を示す図である。図１４の例では、検索結果画像選択部８９は、選択された画像ごとに、その画像に対応するクエリ特徴ベクトルの数（検索された回数）をカウントして画像ごとにスコアリングしている。そのスコアリングされた数値の大きい方から降順にソートする統計処理を行っている。クエリ画像から抽出される複数のクエリ特徴ベクトル画像のそれぞれについて画像が選択されるので、それを統計処理することで距離計算によって選択された画像からどの画像がクエリ画像に類似するかを評価することができる。この統計結果から、検索結果画像選択部８９は１または複数の画像を検索結果の画像として選択し、ウェブサーバ２に選択した画像の情報を出力する。選択される画像は、例えば検索された回数が最も多い画像でもよいし、その回数の多い順で上位いくつかであってもよい。ウェブサーバ２は、クライアント装置３に検索結果の画像を表示させる情報を出力する。
【００５７】
これまでの説明からわかるように、上位代表ベクトル距離計算部８３から画像特徴ベクトル距離計算部８８までの処理はＧＰＵなどの並列計算を行うハードウェアとの親和性が高く、その並列計算能力をフルに活かすことができる。また検索結果画像選択部８９の処理も、ある程度並列処理が可能であり、ＣＰＵ１１も用いるより高速に処理を行うことができる。また検索結果画像選択部８９の処理量は上位代表ベクトル距離計算部８３から画像特徴ベクトル距離計算部８８までの処理に比べれば小さいため、全体の処理時間に対する本処理の処理時間の割合は十分に小さい。これらにより、ＧＰＵによる処理時間の短縮効果を十分に享受することができる。
【００５８】
上述の説明では、画像特徴ベクトル距離計算部８８および検索結果画像選択部８９の処理は並列計算装置１４を中心にして行っているが、ＣＰＵ１１を中心として行ってもよい。その他の処理をＧＰＵに実行させるだけでも高速化の効果が得られるからである。また画像特徴ベクトル距離計算部８８および検索結果画像選択部８９の処理をＣＰＵ１１で行えば、画像特徴ベクトル転送部８７の処理を省略できるので、代表特徴ベクトルの距離計算などに比べれば、ＣＰＵ１１で処理を行うことによる計算時間の増加は抑えられる。
【００５９】
なお、本実施形態では上位代表ベクトルと代表特徴ベクトルのように代表ベクトルが２段階の木構造の構成になっているが、上位代表ベクトルを設けない１段の構成にしてもよい。その場合、上位代表ベクトル距離計算部８３および代表クラスタ選択部８４の処理は不要であり、代表特徴ベクトル距離計算部８５は全ての代表特徴ベクトルについて距離計算を行う。また、上位代表ベクトルの親となる親代表ベクトルを設け、３段以上の構成にしてもよい。３段以上の構成とする場合、上位代表ベクトル距離計算部８３の前にその親代表ベクトルとの距離計算をする処理と、その中から上位代表ベクトルの集合を選択する処理とが行われ、上位代表ベクトル距離計算部８３は、その選択された上位代表ベクトルの集合（一部の上位代表ベクトル）について距離計算を行う。
【００６０】
図１５は、インデックス追加部５３の機能構成を示す機能ブロック図である。インデックス追加部５３は、機能的に、追加特徴ベクトル抽出部９１と、追加特徴ベクトル距離計算部９２と、追加クラスタ選択部９３と、画像特徴ベクトル追加部９４とを含む。
【００６１】
追加特徴ベクトル抽出部９１は、主にＣＰＵ１１および記憶部１２により実現される。追加特徴ベクトル抽出部９１は、記憶部１２に格納されている検索対象として追加される画像から、複数の画像特徴ベクトル２０を抽出する。この抽出の手法は、画像特徴ベクトル抽出部６１と同じ手法でよい。以下、この画像特徴ベクトル２０を、追加特徴ベクトルと記す。
【００６２】
追加特徴ベクトル距離計算部９２は、並列計算装置１４を中心として実現される。追加特徴ベクトル距離計算部９２は、追加特徴ベクトルと、木構造代表ベクトル格納部７２に格納される代表特徴ベクトルのそれぞれとの距離を計算する。その距離は、図１３に示す処理方法におけるクエリ特徴ベクトルと計算対象となるベクトルとを、それぞれ追加特徴ベクトルと全ての代表クラスタに含まれる代表特徴ベクトルとに替えたフローに基づいて計算される。
【００６３】
追加クラスタ選択部９３は、並列計算装置１４を中心として計算される。追加クラスタ選択部９３は、追加特徴ベクトル距離計算部９２の計算結果に基づいて、追加特徴ベクトルの属する画像特徴クラスタを選択する。例えば、追加特徴ベクトルのそれぞれについて、その追加特徴ベクトルとの距離が最も短い代表特徴ベクトルが代表する画像特徴クラスタをその追加特徴ベクトルに対応する画像特徴クラスタとして選択する。
【００６４】
画像特徴ベクトル追加部９４は、ＣＰＵ１１および記憶部１２を中心として実現される。画像特徴ベクトル追加部９４は、追加クラスタ選択部９３により選択された画像特徴クラスタにそれに対応する追加特徴ベクトルを追加し、その画像特徴クラスタのデータをクラスタベクトル格納部７１に格納する。こうすることで、検索対象となる画像を追加する場合にも、再度クラスタリングすることなく追加される画像を検索対象に加えることができ、その追加に伴う処理時間を節約することができる。
【符号の説明】
【００６５】
１ 画像検索装置、２ ウェブサーバ、３ クライアント装置、１１ ＣＰＵ、１２ 記憶部、１３ 通信部、１４ 並列計算装置、１５ バス、２０ 画像特徴ベクトル、４０ 並列実行部、４１ プロセッサ、４２ 命令ユニット、４３ 高速メモリ、４５ 装置内メモリ、５１ インデックス生成部、５２ 画像検索部、５３ インデックス追加部、６１ 画像特徴ベクトル抽出部、６２ クラスタ生成部、７１ クラスタベクトル格納部、７２ 木構造代表ベクトル格納部、８１ 代表ベクトル転送部、８２ クエリ特徴ベクトル取得部、８３ 上位代表ベクトル距離計算部、８４ 代表クラスタ選択部、８５ 代表特徴ベクトル距離計算部、８６ 画像特徴クラスタ選択部、８７ 画像特徴ベクトル転送部、８８ 画像特徴ベクトル距離計算部、８９ 検索結果画像選択部、９１ 追加特徴ベクトル抽出部、９２ 追加特徴ベクトル距離計算部、９３ 追加クラスタ選択部、９４ 画像特徴ベクトル追加部。
【特許請求の範囲】
【請求項１】
共通メモリと、
同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、
を含む画像検索装置であって、
検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段と、
クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを取得し、前記共通メモリに格納するクエリ特徴ベクトル取得手段と、
前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算手段と、
前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算手段と、
前記第２の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択する手段と、
を含むことを特徴とする画像検索装置。
【請求項２】
前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルを前記記憶手段から前記共通メモリに転送する画像特徴ベクトル転送手段をさらに含み、
前記第２の距離計算手段は、前記転送された画像特徴ベクトルと前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する、
ことを特徴とする請求項１に記載の画像検索装置。
【請求項３】
前記複数の代表特徴ベクトルのデータ量は、前記共通メモリの容量より小さい、
ことを特徴とする請求項１または２に記載の画像検索装置。
【請求項４】
前記複数のクラスタのうち１つに属する画像特徴ベクトルのデータ量は、前記共通メモリの容量より小さく、
前記複数のクラスタに属する画像特徴ベクトルのデータ量は、前記共通メモリの容量より大きい、
ことを特徴とする請求項３に記載の画像検索装置。
【請求項５】
前記複数のクラスタのうち１つに属する画像特徴ベクトルと前記複数の代表ベクトルとのデータ量は、前記共通メモリの容量より小さく、
前記画像特徴ベクトル転送手段は、前記選択されたクラスタに属する画像特徴ベクトルを、共通メモリに記憶されている他の画像特徴ベクトルと置き換える、
ことを特徴とする請求項２に記載の画像検索装置。
【請求項６】
追加される検索対象となる画像から複数の画像特徴ベクトルを抽出する追加画像特徴ベクトル抽出手段と、
前記追加画像特徴ベクトル抽出手段により抽出された画像特徴ベクトルを前記クラスタのうちいずれかに追加する画像特徴ベクトル追加手段と、
をさらに含むことを特徴とする請求項１から５のいずれかに記載の画像検索装置。
【請求項７】
共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータを、
検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段、
クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定手段、
前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算手段、
前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算手段、および
前記第２の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択する手段、
として機能させるためのプログラム。
【請求項８】
共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータに画像を検索させる画像検索方法であって、
検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送ステップと、
クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定ステップと、
前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算ステップと、
前記第１の距離計算ステップによる計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算ステップと、
前記第２の距離計算ステップによる計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択するステップと、
を含むことを特徴とする画像検索方法。
【請求項９】
共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータを、
検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段、
クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定手段、
前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算手段、
前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算手段、および
前記第２の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択する手段、
として機能させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【請求項１】
共通メモリと、
同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、
を含む画像検索装置であって、
検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段と、
クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを取得し、前記共通メモリに格納するクエリ特徴ベクトル取得手段と、
前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算手段と、
前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算手段と、
前記第２の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択する手段と、
を含むことを特徴とする画像検索装置。
【請求項２】
前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルを前記記憶手段から前記共通メモリに転送する画像特徴ベクトル転送手段をさらに含み、
前記第２の距離計算手段は、前記転送された画像特徴ベクトルと前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する、
ことを特徴とする請求項１に記載の画像検索装置。
【請求項３】
前記複数の代表特徴ベクトルのデータ量は、前記共通メモリの容量より小さい、
ことを特徴とする請求項１または２に記載の画像検索装置。
【請求項４】
前記複数のクラスタのうち１つに属する画像特徴ベクトルのデータ量は、前記共通メモリの容量より小さく、
前記複数のクラスタに属する画像特徴ベクトルのデータ量は、前記共通メモリの容量より大きい、
ことを特徴とする請求項３に記載の画像検索装置。
【請求項５】
前記複数のクラスタのうち１つに属する画像特徴ベクトルと前記複数の代表ベクトルとのデータ量は、前記共通メモリの容量より小さく、
前記画像特徴ベクトル転送手段は、前記選択されたクラスタに属する画像特徴ベクトルを、共通メモリに記憶されている他の画像特徴ベクトルと置き換える、
ことを特徴とする請求項２に記載の画像検索装置。
【請求項６】
追加される検索対象となる画像から複数の画像特徴ベクトルを抽出する追加画像特徴ベクトル抽出手段と、
前記追加画像特徴ベクトル抽出手段により抽出された画像特徴ベクトルを前記クラスタのうちいずれかに追加する画像特徴ベクトル追加手段と、
をさらに含むことを特徴とする請求項１から５のいずれかに記載の画像検索装置。
【請求項７】
共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータを、
検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段、
クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定手段、
前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算手段、
前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算手段、および
前記第２の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択する手段、
として機能させるためのプログラム。
【請求項８】
共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータに画像を検索させる画像検索方法であって、
検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送ステップと、
クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定ステップと、
前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算ステップと、
前記第１の距離計算ステップによる計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算ステップと、
前記第２の距離計算ステップによる計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択するステップと、
を含むことを特徴とする画像検索方法。
【請求項９】
共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータを、
検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段、
クエリとなる画像から抽出される１または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定手段、
前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第１の距離計算手段、
前記第１の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第２の距離計算手段、および
前記第２の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも１つを選択する手段、
として機能させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２０１３−６５１４６（Ｐ２０１３−６５１４６Ａ）
【公開日】平成２５年４月１１日（２０１３．４．１１）
【国際特許分類】
【出願番号】特願２０１１−２０２７１３（Ｐ２０１１−２０２７１３）
【出願日】平成２３年９月１６日（２０１１．９．１６）
【特許番号】特許第４９７６５７８号（Ｐ４９７６５７８）
【特許公報発行日】平成２４年７月１８日（２０１２．７．１８）
【出願人】（３９９０３７４０５）楽天株式会社 (416)
【Ｆターム（参考）】
【公開日】平成２５年４月１１日（２０１３．４．１１）
【国際特許分類】
【出願日】平成２３年９月１６日（２０１１．９．１６）
【特許番号】特許第４９７６５７８号（Ｐ４９７６５７８）
【特許公報発行日】平成２４年７月１８日（２０１２．７．１８）
【出願人】（３９９０３７４０５）楽天株式会社 (416)
【Ｆターム（参考）】
[ Back to top ]