共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含む画像検索装置であって、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段と、クエリとなる画像から抽出される1または複数のクエリ特徴ベクトルを取得し、前記共通メモリに格納するクエリ特徴ベクトル取得手段と、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第1の距離計算手段と、前記第1の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第2の距離計算手段と、前記第2の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも1つを選択する手段と、を含むことを特徴とする画像検索装置。前記第1の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルを前記記憶手段から前記共通メモリに転送する画像特徴ベクトル転送手段をさらに含み、前記第2の距離計算手段は、前記転送された画像特徴ベクトルと前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する、ことを特徴とする請求項1に記載の画像検索装置。前記複数の代表特徴ベクトルのデータ量は、前記共通メモリの容量より小さい、ことを特徴とする請求項1または2に記載の画像検索装置。前記複数のクラスタのうち1つに属する画像特徴ベクトルのデータ量は、前記共通メモリの容量より小さく、前記複数のクラスタに属する画像特徴ベクトルのデータ量は、前記共通メモリの容量より大きい、ことを特徴とする請求項3に記載の画像検索装置。前記複数のクラスタのうち1つに属する画像特徴ベクトルと前記複数の代表ベクトルとのデータ量は、前記共通メモリの容量より小さく、前記画像特徴ベクトル転送手段は、前記選択されたクラスタに属する画像特徴ベクトルを、共通メモリに記憶されている他の画像特徴ベクトルと置き換える、ことを特徴とする請求項2に記載の画像検索装置。追加される検索対象となる画像から複数の画像特徴ベクトルを抽出する追加画像特徴ベクトル抽出手段と、前記追加画像特徴ベクトル抽出手段により抽出された画像特徴ベクトルを前記クラスタのうちいずれかに追加する画像特徴ベクトル追加手段と、をさらに含むことを特徴とする請求項1から5のいずれかに記載の画像検索装置。共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータを、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段、クエリとなる画像から抽出される1または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定手段、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第1の距離計算手段、前記第1の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第2の距離計算手段、および前記第2の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも1つを選択する手段、として機能させるためのプログラム。共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータに画像を検索させる画像検索方法であって、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送ステップと、クエリとなる画像から抽出される1または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定ステップと、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第1の距離計算ステップと、前記第1の距離計算ステップによる計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第2の距離計算ステップと、前記第2の距離計算ステップによる計算結果に基づいて、前記複数の画像のうち少なくとも1つを選択するステップと、を含むことを特徴とする画像検索方法。共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータを、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段、クエリとなる画像から抽出される1または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定手段、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第1の距離計算手段、前記第1の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第2の距離計算手段、および前記第2の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも1つを選択する手段、として機能させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体。ところで、画像データは文字データに比較してそのデータ量が膨大であるため、通常のCPUを用いて文字と同様な高速検索を行うには、処理量を削減することが必要になる。このため、検索インデックスの生成時にその画像データの特徴を的確に表せないVisualWordを用いなければなければならないなど、充分な検索精度を得ることが難しくなっていた。そこで、例えば所謂GPUGraphicProcessingUnitのような、複数のプロセッサおよび共通メモリを含み、複数のプロセッサはそれぞれ共通メモリから効率的にデータを取込み、また共通のプログラムを実行して演算処理を行うことができる、CPUよりも計算能力の高いハードウェアを用いることが考えられる。演算処理が高速に行われるのであれば、精度を確保しつつ高速検索することが可能となるからである。しかしながら、上記したようなBoF法などはCPUに最適化された手順であり、疎行列等を扱うためにリンクドリストのデータ構造や分岐処理を多用する。それらは、上述のような特徴を有するGPUのアーキテクチャとの親和性が低いため、GPUをそのまま用いてもその能力を充分に活かすことができなかった。本発明は上記課題を鑑みてなされたものであって、その目的は、GPUのように同種の処理を大量に行う能力の高いハードウェアを用いて、画像検索処理を高速化することにある。上記課題を解決するために、本発明にかかる画像検索装置は、共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含み、さらに、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段と、クエリとなる画像から抽出される1または複数のクエリ特徴ベクトルを取得し、前記共通メモリに格納するクエリ特徴ベクトル取得手段と、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第1の距離計算手段と、前記第1の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第2の距離計算手段と、前記第2の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも1つを選択する手段と、を含むことを特徴とする。また、本発明にかかるプログラムは、共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータを、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段、クエリとなる画像から抽出される1または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定手段、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第1の距離計算手段、前記第1の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第2の距離計算手段、および、前記第2の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも1つを選択する手段、として機能させることを特徴とする。また、本発明にかかる画像検索方法は、共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータに画像を検索させる画像検索方法であって、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送ステップと、クエリとなる画像から抽出される1または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定ステップと、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第1の距離計算ステップと、前記第1の距離計算ステップによる計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第2の距離計算ステップと、前記第2の距離計算ステップによる計算結果に基づいて、前記複数の画像のうち少なくとも1つを選択するステップと、を含むことを特徴とする。また、本発明にかかるコンピュータ読み取り可能な記憶媒体は、共通メモリと、同一の命令を実行する複数の並列のプロセッサであって、それぞれ前記共通メモリに格納されるデータを一括して読込んで処理する複数の並列のプロセッサと、を含むコンピュータを、検索対象となる複数の画像から抽出される複数の画像特徴ベクトルであってそれぞれ複数のクラスタのいずれかに属する画像特徴ベクトルと、それぞれ前記複数のクラスタのいずれかを代表する複数の代表特徴ベクトルと、を記憶する記憶手段から、前記共通メモリに前記複数の代表特徴ベクトルを転送する代表ベクトル転送手段、クエリとなる画像から抽出される1または複数のクエリ特徴ベクトルを、前記共通メモリに設定するクエリ設定手段、前記転送された複数の代表特徴ベクトルの少なくとも一部と前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算する第1の距離計算手段、前記第1の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルと、前記クエリ特徴ベクトルとの距離を計算する第2の距離計算手段、および、前記第2の距離計算手段による計算結果に基づいて、前記複数の画像のうち少なくとも1つを選択する手段、として機能させるためのプログラムを記憶することを特徴とする。本発明によれば、GPUのように同種の処理を大量に行う能力の高いハードウェアを用いて、画像検索処理を高速化することができる。代表ベクトルを用いることで距離計算の対象となる特徴ベクトルの数が減り、かつ距離計算が主体となるためGPUのように同種の処理を大量に行えるハードウェアとの親和性が高いからである。本発明の一態様では、前記第1の距離計算手段による計算結果に基づいて選択されるクラスタに属する画像特徴ベクトルを前記記憶手段から前記共通メモリに転送する画像特徴ベクトル転送手段をさらに含み、前記第2の距離計算手段は、前記転送された画像特徴ベクトルと前記クエリ特徴ベクトルとの距離を前記複数の並列のプロセッサを用いて計算しもよい。本発明の一態様では、前記複数の代表特徴ベクトルのデータ量は、前記共通メモリの容量より小さくてもよい。本発明の一態様では、前記複数のクラスタのうち1つに属する画像特徴ベクトルのデータ量は、前記共通メモリの容量より小さく、前記複数のクラスタに属する画像特徴ベクトルのデータ量は、前記共通メモリの容量より大きくてもよい。本発明の一態様では、前記複数のクラスタのうち1つに属する画像特徴ベクトルと前記複数の代表ベクトルとのデータ量は、前記共通メモリの容量より小さく、前記画像特徴ベクトル転送手段は、前記選択されたクラスタに属する画像特徴ベクトルを、共通メモリに記憶されている他の画像特徴ベクトルと置き換えてもよい。本発明の一態様では、追加される検索対象となる画像から複数の画像特徴ベクトルを抽出する追加画像特徴ベクトル抽出手段と、前記追加画像特徴ベクトル抽出手段により抽出された画像特徴ベクトルを前記画像特徴クラスタのうちいずれかに追加する画像特徴ベクトル追加手段と、をさらに含んでもよい。以下では、本発明の実施形態について図面に基づいて説明する。出現する構成要素のうち同一機能を有するものには同じ符号を付し、その説明を省略する。図1は、本発明の実施形態にかかる画像検索システムの構成の一例を示す図である。画像検索システムは、画像検索装置1と、ウェブサーバ2と、クライアント装置3とを含む。ウェブサーバ2は、例えばウェブサーバプログラムが動作するサーバハードウェアであり、クライアント装置3は、例えばウェブブラウザのプログラムが動作するパーソナルコンピュータや、スマートフォンである。画像検索システムは画像検索を行う動作の概要は以下の通りである。はじめに、ウェブサーバ2は、インターネット等のネットワークを介してクライアント装置3から画像検索に用いるクエリとなる画像以下、クエリ画像と記述するを取得し、そのクエリ画像を画像検索装置1に入力させる。次に画像検索装置1は、入力された画像に類似する1または複数の画像を検索し、ウェブサーバ2に出力する。ウェブサーバ2は、画像検索装置1が検索した画像をクライアント装置3に表示させるデータを出力する。図2は、本発明の実施形態にかかる画像検索装置1の構成の一例を示す図である。画像検索装置1は、CPU11、記憶部12、通信部13、並列計算装置14およびバス15を含む。CPU11は、記憶部12に格納されているプログラムに従って動作する。またCPU11は通信部13や並列計算装置14を制御する。なお、上記プログラムは、インターネット等のネットワークを介して提供されるものであってもよいし、DVD-ROMやUSBメモリ等のコンピュータで読み取り可能な情報記録媒体に格納されて提供されるものであってもよい。記憶部12は、RAMやROM等のメモリ素子やハードディスクドライブ等によって構成されている。記憶部12は、上記プログラムを格納する。また、記憶部12は、各部から入力される情報や演算結果を格納する。通信部13は、ウェブサーバ2等の他の装置と通信接続するためにネットワークカードなどが設けられる通信手段等で構成されている。通信部13は、CPU11の制御に基づいて、他の装置から受信した情報をCPU11や記憶部12に入力し、他の装置に情報を送信する。バス15は、CPU11、記憶部12、通信部13および並列計算装置14との間でデータをやりとりするためのものである。例えば、CPU11や記憶部12と並列計算装置14とはバス15の中の拡張バスを介して接続される。並列計算装置14は、並列計算によって同種の計算を大量に行うことを得意とするハードウェアである。並列計算装置14は、例えばGPUである。図3は、並列計算装置14の構成の一例を示す図である。並列計算装置14は、複数の並列実行部40と、装置内メモリ45とを含む。また各並列実行部40は、複数のプロセッサ41と、命令ユニット42と、高速メモリ43とを含む。複数のプロセッサ41のそれぞれは、浮動小数点計算や、装置内メモリ45や高速メモリ43との間でのデータの読込みや書込み等の処理を行う。命令ユニット42は、装置内メモリ45等に格納されるプログラムに基づいて、その命令ユニット42を含む並列実行部40に含まれる複数のプロセッサ41に処理をさせる。ある並列実行部40に含まれる複数のプロセッサ41は、その並列実行部40に含まれる一つの命令ユニット42からの指示によって、同一の命令を処理する。こうすると、複数のプロセッサ41を1つの命令ユニット42で制御できるため、命令ユニット42の回路の規模の増加を抑えることができるため、並列計算装置14に含まれるプロセッサ41の数をCPU11に比べて増やすことが可能になる。装置内メモリ45は、記憶部12に用いられるRAMより高速にアクセス可能なDRAMからなる。装置内メモリ45は、バス15を介して、CPU11や記憶部12と接続されている。なお、並列計算装置14は、DMA転送により装置内メモリ45と記憶部12との間でデータを転送する回路も有する。高速メモリ43は、装置内メモリ45より高速にアクセス可能なSRAM等からなる。プロセッサ41が高速メモリ43にアクセスする際のレイテンシは、プロセッサ41がその内部レジスタにアクセスする際のレイテンシとほとんど変わらない。ここで、装置内メモリ45も高速メモリ43も複数のプロセッサ41から共通にアクセスできる共通メモリである。図4は、本発明の実施形態にかかる画像検索装置1の機能を示す機能ブロック図である。画像検索装置1は、機能的に、インデックス生成部51、画像検索部52、およびインデックス追加部53を含む。これらの機能は、CPU11が記憶部12に格納されたプログラムを実行し、通信部13や並列計算装置14を制御し、また、並列計算装置14がその並列計算装置14向けのプログラムを実行することで実現される。インデックス生成部51は、検索対象となる複数の画像から、画像検索の際に用いる画像特徴ベクトル20や、その画像特徴ベクトル20の選択を容易にするインデックスを生成する。画像検索部52は、インデックスや画像特徴ベクトル20を用いて、クエリ画像に類似する画像を検索する。インデックス追加部53は、追加の画像から画像特徴ベクトル20を生成し、またその追加の画像を選択できるようインデックスを変更する。図5は、インデックス生成部51の機能構成を示す機能ブロック図である。インデックス生成部51は、機能的に、画像特徴ベクトル抽出部61と、クラスタ生成部62とを含む。クラスタ生成部62は、クラスタのインデックスとなる代表ベクトルの木構造を生成し、木構造代表ベクトル格納部72にインデックスに関連する情報を格納する。また、クラスタベクトル格納部71は、その木構造の葉となる代表ベクトルが代表するクラスタに属する画像特徴ベクトル20の情報を格納する。クラスタベクトル格納部71、木構造代表ベクトル格納部72は、具体的には記憶部12により構成される。画像特徴ベクトル抽出部61は、主にCPU11および記憶部12により実現される。画像特徴ベクトル抽出部61は、記憶部12に格納されている複数の画像であって検索対象となる複数の画像から、複数の画像特徴ベクトル20を抽出する。より具体的には、画像特徴ベクトル抽出部61は、その複数の画像のそれぞれから、1または複数の画像特徴ベクトル20を抽出し、抽出された画像特徴ベクトル20を、その画像特徴ベクトル20が抽出された画像と関連付けて記憶部12に記憶させる。図6は、検索対象となる画像の一例を示す図である。図7は、画像から抽出される画像特徴ベクトル20の概念を示す図である。画像から抽出される画像特徴ベクトル20のそれぞれは、その画像の局所的な特徴を示す局所特徴量である。画像特徴ベクトル20のそれぞれは、例えば128の要素次元をもつベクトルである。画像特徴ベクトル20を抽出するためには、SIFTScaleInvariantFeaturetransform、SURFSpeededUpRobustFeaturesなどの公知の手法を用いてよい。画像特徴ベクトル20のそれぞれが有する要素の数は、画像からの抽出の手法などに応じて変化させてよい。また1つの画像から抽出される画像特徴ベクトル20の数は、予め定められた数例えば300としてよいが、単純な画像から抽出される画像特徴ベクトル20の数はその予め定められた数より少なくなってもよい。クラスタ生成部62は、主にCPU11および記憶部12により実現される。クラスタ生成部62は、クラスタリングにより、画像特徴ベクトル抽出部61により抽出された複数の画像特徴ベクトル20のそれぞれを、複数のクラスタのいずれかに分類する。画像特徴ベクトル20をクラスタに分類する処理は1段階の処理とは限らず、多段階の処理であってよい。また、その多段階の処理は、以下の処理を再帰的に呼び出すことにより実現してもよい。以下では、2段階の処理を行い、かつ1段目で画像特徴ベクトル抽出部61により抽出された複数の画像特徴ベクトル20を1024個のクラスタに分類し、さらに2段目でその1024個のクラスタのそれぞれを512個のクラスタに分類する場合の例について説明する。クラスタ生成部62の各段の処理では、クラスタリングにより、与えられた複数の画像特徴ベクトル20を与えられた個数のクラスタに分類し、複数のクラスタを生成し、さらにその生成されたクラスタの代表ベクトルを生成し、生成された代表ベクトルをその段の代表ベクトルとして木構造代表ベクトル格納部72に格納する。処理中の段が最下段でない場合は、クラスタ生成部62は処理中の段で生成されたクラスタのそれぞれに属する複数の画像特徴ベクトル20を入力情報として、次の段の処理を再帰的に呼び出す。代表ベクトルは、例えばその分類されたクラスタに属する画像特徴ベクトル20の重心であり、そのクラスタを代表するベクトルである。またクラスタ生成部62は、最下段の処理で生成されたクラスタごとに、そのクラスタに属する画像特徴ベクトル20をクラスタベクトル格納部71に格納する。上述の例の場合、1段目の処理では、クラスタ生成部62は、与えられた画像特徴ベクトル20を1024個のクラスタに分類し、その分類された1段目の各クラスタの代表ベクトルを生成し、生成された1段目の代表ベクトルを木構造代表ベクトル格納部72に格納する。2段目の処理では、クラスタ生成部62は、1段目に生成された1024個のクラスタのそれぞれに属する複数の画像特徴ベクトル20を入力情報として、更に512個のクラスタに分類し、その分類された2段目の各クラスタの代表ベクトルを生成し、生成された下位の段の代表ベクトルを木構造代表ベクトル格納部72に格納する。2段目のクラスタを全て生成するとその2段目のクラスタの総数は1024×512個となる。さらにクラスタ生成部62は、2段目に生成されたクラスタごとに、そのクラスタに属する画像特徴ベクトル20をクラスタベクトル格納部71に格納する。以下では、説明の容易のため、1段目のクラスタを代表する代表ベクトルを上位代表ベクトルと記し、最下段上述の例では2段目のクラスタを代表する代表ベクトルを代表特徴ベクトルと記す。また最終的に生成されたクラスタ上述の例では2段目のクラスタを画像特徴クラスタとも記す。画像特徴ベクトル20をクラスタに分類する際には、k-means法等の公知のクラスタリング手法を用いればよい。クラスタの数は、後述の画像検索部52の処理との関係で、2のべき乗が好適であるが、2のべき乗でなくてもよい。また全ての画像に含まれる画像特徴ベクトル20を分類すると、それぞれの画像特徴クラスタには、複数の画像特徴ベクトル20が属する。クラスタ生成部62の再帰処理を2段階行う事で、木構造代表ベクトル格納部72に、2階層の情報を格納する事ができる。クラスタ生成部62の計算は、並列計算装置14を用いて行ってもよい。図8は、代表ベクトルの木構造の一例を示す図である。クラスタ生成部62が上述の2段階の処理を行う場合、2段階のクラスタに対応する2段階の代表ベクトルが木構造を構成する。上位代表ベクトルの数は1024個であり、上位代表ベクトルのそれぞれは、512個の代表特徴ベクトルの親となっている。画像検索部52は、代表ベクトルが木構造を構成するように親子関係があることを利用して検索を行う。図9は、画像検索部52の機能構成を示す機能ブロック図である。画像検索部52は、機能的に、代表ベクトル転送部81、クエリ特徴ベクトル取得部82、上位代表ベクトル距離計算部83、代表クラスタ選択部84、代表特徴ベクトル距離計算部85、画像特徴クラスタ選択部86、画像特徴ベクトル転送部87、画像特徴ベクトル距離計算部88、および検索結果画像選択部89を含む。代表ベクトル転送部81は、主に並列計算装置14と、記憶部12とにより実現される。代表ベクトル転送部81は、木構造代表ベクトル格納部72に格納され、上位代表ベクトルおよびそれぞれ画像特徴クラスタを代表する複数の代表特徴ベクトルを、複数のプロセッサ41から共通にアクセスできる装置内メモリ45に転送する。代表ベクトル転送部81は、具体的には並列計算装置14やバス15のDMADirectMemoryAccess機能を用いて記憶部12から装置内メモリ45に上記データを転送する。図10は、装置内メモリ45でのデータ配置の一例を示す図である。装置内メモリ45には、代表特徴ベクトルを格納する領域と、上位代表ベクトルを格納する領域と、1つの画像特徴クラスタを格納する領域とが設けられる。代表ベクトル転送部81は、記憶部12に記憶される複数の代表ベクトルの情報を、予め割り当てられた装置内メモリ45のメモリ領域に格納する。画像特徴クラスタを格納する領域へのデータの格納については後述する。ここで、代表特徴ベクトルの要素数が128次元、代表特徴ベクトルの数は画像特徴クラスタの数と同じ1024×512個、各要素が1バイトの整数型とすると、その複数の代表特徴ベクトルの全てのデータ量は、1024×512×128バイトB、つまり64MBとなる。また、この場合、複数の上位代表ベクトルの数は1024であるので、同様に複数の上位代表ベクトルのデータ量は1024×128バイト、つまり128KBとなる。例えば現行のGPUに搭載される装置内メモリ45のメモリ容量は1GB程度であり、装置内メモリ45の容量も1GBであるとすると、複数の代表ベクトルのデータ量は装置内メモリ45の容量より小さい。一方、画像の数が100万、1つの画像から抽出される画像特徴ベクトル20の数が300とすると、複数の画像特徴クラスタに含まれる画像特徴ベクトル20のデータ量は、100万×300×128バイト、つまり約36GBになり、装置内メモリ45には格納できない。一方、1つの画像特徴クラスタあたりの平均的な画像特徴ベクトル20の数は、100万×300÷1024×512、つまり約600であるので、データ量は75KB程度である。クラスタリングにより画像特徴クラスタに含まれる画像特徴ベクトル20の数が多少変動したとしても、複数の代表特徴ベクトルのデータ量と、複数の上位代表ベクトルのデータ量と、1つの画像特徴クラスタに含まれる画像特徴ベクトル20のデータ量との和は、装置内メモリ45の容量より小さくなる。図11は、装置内メモリ45での代表ベクトルの配置の一例を示す図である。装置内メモリ45に格納される代表ベクトルの各要素のサイズは4バイトであり、要素の順に並んでいる。また、ある代表ベクトルのデータの先頭アドレスは、装置内メモリ45から一括して読み出すことのできるデータのバイト数例えば32や64の倍数となっている。このデータ構造は、後述する距離計算の処理において、装置内メモリ45に格納されるデータを複数のプロセッサ41に一括して読込ませるためのものである。代表ベクトル転送部81は、代表ベクトルの各要素のサイズが1バイトであっても、一括して読込むために、各要素のサイズを4バイトに変換したデータを装置内メモリ45に転送している。なお、上位代表ベクトルや、1つの画像特徴クラスタ内の画像特徴ベクトル20も、同様のデータ構造によって装置内メモリ45に格納される。装置内メモリ45内での複数の代表特徴ベクトル、複数の上位代表ベクトル、および1つの画像特徴クラスタに含まれる画像特徴ベクトル20のデータ量は4倍になるが、この例ではそれらのデータ量の和が装置内メモリ45の容量より小さい点は変わりない。本実施形態においては、少なくとも装置内メモリ45内での複数の代表特徴ベクトル、および複数の上位代表ベクトルのデータ量の和が装置内メモリ45の容量に収まるように、画像特徴クラスタや代表ベクトルの数を調整すればよい。クエリ特徴ベクトル取得部82は、主にCPU11、記憶部12、および並列計算装置14によって実現される。クエリ特徴ベクトル取得部82は、クエリ画像から抽出される1または複数のクエリ特徴ベクトルを取得し、共通メモリである装置内メモリ45に格納する。クエリ特徴ベクトル取得部82は、はじめに、クエリ画像を、クライアント装置3からウェブサーバ2を介して取得する。図12は、クエリ画像を入力する画面の一例を示す図である。クライアント装置3は、ウェブサーバ2が生成したデータにより本画面を表示する。クエリ画像は、ユーザがクライアント装置3内の画像ファイルをアップロードすることで取得されてもよいし、なんらかのウェブページに表示される画像のURLを送ることで取得されてもよいし、写真共有サービス等に格納される画像からクエリ画像を選択することで取得されてもよい。次に、クエリ特徴ベクトル取得部82は、ウェブサーバ2から、取得したクエリ画像を取得し、そのクエリ画像から1または複数のクエリ特徴ベクトルを抽出し取得する。クエリ特徴ベクトルは、画像特徴ベクトル抽出部61が画像特徴ベクトル20を抽出する手法と同じ手法を用いて生成される。次にクエリ特徴ベクトル取得部82はクエリ特徴ベクトルを装置内メモリ45に格納する。ここで、CPU11がクエリ特徴ベクトルを抽出し、並列計算装置14がクエリ特徴ベクトルを装置内メモリ45にロードしてもよいし、クエリ画像を並列計算装置14にロードし、並列計算装置14がクエリ特徴ベクトルを抽出して装置内メモリ45に格納してもよい。上位代表ベクトル距離計算部83は、並列計算装置14を中心として実現される。上位代表ベクトル距離計算部83は、複数の上位代表ベクトルのそれぞれと、クエリ特徴ベクトルとの距離とを、複数の並列のプロセッサ41を用いて計算する。以下では上位代表ベクトル距離計算部83での距離計算の詳細について説明する。なお、上位代表ベクトル距離計算部83、代表クラスタ選択部84、代表特徴ベクトル距離計算部85、画像特徴クラスタ選択部86および画像特徴ベクトル距離計算部88の処理は、クエリ画像から抽出されたクエリ特徴ベクトルのそれぞれについて行う。図13は距離計算の処理フローの一例を示す図である。はじめに、上位代表ベクトル距離計算部83は、クエリ特徴ベクトルを装置内メモリ45から距離計算を行う並列実行部40の高速メモリ43にロードするステップS101。次に、計算対象となるベクトルここでは上位代表ベクトルの各要素を装置内メモリ45からその要素の計算を行うプロセッサ41のレジスタにロードするステップS102。この際、複数のプロセッサ41は、装置内メモリ45から計算対象ベクトルのデータを一括で読込む。それは、計算対象となるベクトルのデータが代表ベクトル転送部81等によって予めその一括の読込ができるよう装置内メモリ45に記憶されているからである。次に、上位代表ベクトル距離計算部83は、レジスタに格納された計算対象となるベクトルの要素と、その要素に対応するクエリ特徴ベクトルの要素とを減算し、さらにその減算結果を2乗するステップS103。次に、計算対象となるベクトルの各要素についてのステップS103の計算結果を合計するステップS104。そして、上位代表ベクトル距離計算部83は、合計結果を装置内メモリ45に格納するステップS105。なお、ある並列実行部40に含まれる、同一の命令を実行するプロセッサ41の数がクエリ特徴ベクトルや計算対象となるベクトルの要素の数より少なければ、ステップS102からステップS104の処理は、プロセッサ41の数にあわせて分割され、複数回実行される。また、並列実行部40が複数ある場合、別の並列実行部40に、上位代表ベクトル距離計算部83は、別の計算対象となるベクトルについてステップS101からS105の処理を実行させる。また、クエリ画像から抽出された他のクエリ特徴ベクトルについても並列に計算してもよい。こうすることで、クエリ特徴ベクトルと他の複数の計算対象のベクトルとの距離計算はGPUのような並列計算装置14の並列計算能力にあわせて並列に計算される。この距離計算の処理内容からわかるように、装置内メモリ45に適切に配置された複数のベクトルと、クエリ特徴ベクトルとの距離計算はGPUのようなハードウェアと親和性が高く、非常に高速に処理される。代表クラスタ選択部84は、並列計算装置14を中心として実現される。代表クラスタ選択部84は、上位代表ベクトル距離計算部83で計算されたクエリ特徴ベクトルと複数の上位代表ベクトルのそれぞれとの距離に基づいて、複数の代表特徴ベクトルの集合から1つの集合を選択する。より詳細には、例えば、クエリ特徴ベクトルとの距離が最も短い上位代表ベクトルの子となる複数の代表特徴ベクトルの集合を選択する。この代表特徴ベクトルの集合のそれぞれは1段目のクラスタ代表クラスタに対応する。代表特徴ベクトルの集合の選択は、それに対応する代表クラスタの選択にも相当する。なお、上位代表ベクトルのそれぞれは、複数の代表特徴ベクトルを代表しているとみることもできる。代表クラスタ選択部84は、より具体的には、その代表ベクトルの集合を格納するメモリ内の領域の先頭アドレスを計算することによってその集合を選択する。例えば、ある上位代表ベクトルの子となる代表特徴ベクトルの数を上位代表ベクトルにかかわらず一定とすれば、距離が最も短い上位代表ベクトルが何番目かわかれば、かけ算等の単純な計算で先頭アドレスを求めることが可能となる。そうすれば、分岐や追加のメモリアクセスを必要とするような演算を用いずに済むため、GPUのようなハードウェアの性能をより活かした処理ができる。代表特徴ベクトル距離計算部85は、並列計算装置14を中心として実現される。代表特徴ベクトル距離計算部85は、複数の代表特徴ベクトルの少なくとも一部のそれぞれと、クエリ特徴ベクトルとの距離とを、複数の並列のプロセッサ41を用いて計算する。ここで計算対象となる代表特徴ベクトルは、代表クラスタ選択部84で選択された集合に属する代表特徴ベクトルである。代表特徴ベクトル距離計算部85は、上位代表ベクトル距離計算部83が距離を計算するものと同様に、図13のフローに従い距離を計算する。ただし、計算対象ベクトルは上述の代表特徴ベクトルである。上位代表ベクトル距離計算部83と同様に、この処理内容はGPUのようなハードウェアと親和性が高く、非常に高速に処理される。画像特徴クラスタ選択部86は、並列計算装置14を中心として実現される。画像特徴クラスタ選択部86は、代表特徴ベクトル距離計算部85で計算されたクエリ特徴ベクトルと複数の代表特徴ベクトルのそれぞれとの距離に基づいて、複数の画像特徴クラスタから画像特徴クラスタを選択する。より詳細には、例えば、クエリ特徴ベクトルとの距離が最も短い代表特徴ベクトルが代表する画像特徴クラスタを選択する。画像特徴ベクトル転送部87は、記憶部12および並列計算装置14を中心として実現される。画像特徴ベクトル転送部87は画像特徴クラスタ選択部86で選択された画像特徴クラスタに属する複数の画像特徴ベクトル20を、クラスタベクトル格納部71から、複数のプロセッサ41から共通にアクセスできる装置内メモリ45に転送する。画像特徴ベクトル転送部87は、並列計算装置14やバス15のDMA機能を用いて記憶部12から装置内メモリ45に上記データを転送する。画像特徴ベクトル転送部87は、図11において代表ベクトル転送部81が代表特徴ベクトル等を転送するのと同じように、装置内メモリ45に格納されるデータを複数のプロセッサ41に一括して読込ませるように画像特徴ベクトル20のデータを配置する。画像特徴ベクトル距離計算部88は、並列計算装置14を中心として実現される。画像特徴ベクトル距離計算部88は、複数の画像特徴ベクトル20のそれぞれと、クエリ特徴ベクトルとの距離とを、複数の並列のプロセッサ41を用いて計算する。ここで計算に用いる画像特徴ベクトル20は、画像特徴クラスタ選択部86で選択された画像特徴クラスタに属する画像特徴ベクトル20である。そのデータは画像特徴ベクトル転送部87により装置内メモリ45に転送されている。画像特徴ベクトル距離計算部88は、上位代表ベクトル距離計算部83が距離を計算するものと同様に、クエリ特徴ベクトルのそれぞれについて、図13のフローに従い距離を計算する。ただし、計算対象ベクトルは画像特徴ベクトル20である。上位代表ベクトル距離計算部83と同様に、この処理内容はGPUのようなハードウェアと親和性が高く、非常に高速に処理される。検索結果画像選択部89は、並列計算装置14を中心として実現される。検索結果画像選択部89は、画像特徴ベクトル距離計算部88の計算結果に基づいて、検索対象となる複数の画像のうちいずれかを検索結果として選択する。まず、検索結果画像選択部89は、画像特徴ベクトル距離計算部88で計算された、クエリ特徴ベクトルと複数の画像特徴ベクトル20のそれぞれとの距離に基づいて、その距離計算に用いたクエリ特徴ベクトルに対応する画像を取得する。より詳細には、例えば、クエリ特徴ベクトルごとに、そのクエリ特徴ベクトルとの距離が最も短い画像特徴ベクトル20が抽出された画像特徴ベクトル20を選択し、その画像特徴ベクトル20が抽出された画像を取得する。その取得された画像の画像IDは、装置内メモリ45に格納する。次に、検索結果画像選択部89は、それぞれクエリ特徴ベクトルのいずれかに対応する複数の取得された画像を統計処理し、クエリとなる画像に対して類似している1または複数の画像を選択する。図14は、クエリ特徴ベクトルに対応する画像を統計処理した結果の一例を示す図である。図14の例では、検索結果画像選択部89は、選択された画像ごとに、その画像に対応するクエリ特徴ベクトルの数検索された回数をカウントして画像ごとにスコアリングしている。そのスコアリングされた数値の大きい方から降順にソートする統計処理を行っている。クエリ画像から抽出される複数のクエリ特徴ベクトル画像のそれぞれについて画像が選択されるので、それを統計処理することで距離計算によって選択された画像からどの画像がクエリ画像に類似するかを評価することができる。この統計結果から、検索結果画像選択部89は1または複数の画像を検索結果の画像として選択し、ウェブサーバ2に選択した画像の情報を出力する。選択される画像は、例えば検索された回数が最も多い画像でもよいし、その回数の多い順で上位いくつかであってもよい。ウェブサーバ2は、クライアント装置3に検索結果の画像を表示させる情報を出力する。これまでの説明からわかるように、上位代表ベクトル距離計算部83から画像特徴ベクトル距離計算部88までの処理はGPUなどの並列計算を行うハードウェアとの親和性が高く、その並列計算能力をフルに活かすことができる。また検索結果画像選択部89の処理も、ある程度並列処理が可能であり、CPU11も用いるより高速に処理を行うことができる。また検索結果画像選択部89の処理量は上位代表ベクトル距離計算部83から画像特徴ベクトル距離計算部88までの処理に比べれば小さいため、全体の処理時間に対する本処理の処理時間の割合は十分に小さい。これらにより、GPUによる処理時間の短縮効果を十分に享受することができる。上述の説明では、画像特徴ベクトル距離計算部88および検索結果画像選択部89の処理は並列計算装置14を中心にして行っているが、CPU11を中心として行ってもよい。その他の処理をGPUに実行させるだけでも高速化の効果が得られるからである。また画像特徴ベクトル距離計算部88および検索結果画像選択部89の処理をCPU11で行えば、画像特徴ベクトル転送部87の処理を省略できるので、代表特徴ベクトルの距離計算などに比べれば、CPU11で処理を行うことによる計算時間の増加は抑えられる。なお、本実施形態では上位代表ベクトルと代表特徴ベクトルのように代表ベクトルが2段階の木構造の構成になっているが、上位代表ベクトルを設けない1段の構成にしてもよい。その場合、上位代表ベクトル距離計算部83および代表クラスタ選択部84の処理は不要であり、代表特徴ベクトル距離計算部85は全ての代表特徴ベクトルについて距離計算を行う。また、上位代表ベクトルの親となる親代表ベクトルを設け、3段以上の構成にしてもよい。3段以上の構成とする場合、上位代表ベクトル距離計算部83の前にその親代表ベクトルとの距離計算をする処理と、その中から上位代表ベクトルの集合を選択する処理とが行われ、上位代表ベクトル距離計算部83は、その選択された上位代表ベクトルの集合一部の上位代表ベクトルについて距離計算を行う。図15は、インデックス追加部53の機能構成を示す機能ブロック図である。インデックス追加部53は、機能的に、追加特徴ベクトル抽出部91と、追加特徴ベクトル距離計算部92と、追加クラスタ選択部93と、画像特徴ベクトル追加部94とを含む。追加特徴ベクトル抽出部91は、主にCPU11および記憶部12により実現される。追加特徴ベクトル抽出部91は、記憶部12に格納されている検索対象として追加される画像から、複数の画像特徴ベクトル20を抽出する。この抽出の手法は、画像特徴ベクトル抽出部61と同じ手法でよい。以下、この画像特徴ベクトル20を、追加特徴ベクトルと記す。追加特徴ベクトル距離計算部92は、並列計算装置14を中心として実現される。追加特徴ベクトル距離計算部92は、追加特徴ベクトルと、木構造代表ベクトル格納部72に格納される代表特徴ベクトルのそれぞれとの距離を計算する。その距離は、図13に示す処理方法におけるクエリ特徴ベクトルと計算対象となるベクトルとを、それぞれ追加特徴ベクトルと全ての代表クラスタに含まれる代表特徴ベクトルとに替えたフローに基づいて計算される。追加クラスタ選択部93は、並列計算装置14を中心として計算される。追加クラスタ選択部93は、追加特徴ベクトル距離計算部92の計算結果に基づいて、追加特徴ベクトルの属する画像特徴クラスタを選択する。例えば、追加特徴ベクトルのそれぞれについて、その追加特徴ベクトルとの距離が最も短い代表特徴ベクトルが代表する画像特徴クラスタをその追加特徴ベクトルに対応する画像特徴クラスタとして選択する。画像特徴ベクトル追加部94は、CPU11および記憶部12を中心として実現される。画像特徴ベクトル追加部94は、追加クラスタ選択部93により選択された画像特徴クラスタにそれに対応する追加特徴ベクトルを追加し、その画像特徴クラスタのデータをクラスタベクトル格納部71に格納する。こうすることで、検索対象となる画像を追加する場合にも、再度クラスタリングすることなく追加される画像を検索対象に加えることができ、その追加に伴う処理時間を節約することができる。