JP5577372B2 - 画像検索装置、画像検索方法、プログラムおよびコンピュータ読取り可能な記憶媒体 - Google Patents

Description

本発明は画像検索装置、画像検索方法、プログラムおよびコンピュータ読取り可能な記憶媒体に関する。

ネットワーク技術等の発達によって、膨大な量の画像ファイルが管理されるようになっている。その大量の画像の中から、クエリとなる画像（クエリ画像）に類似する画像を選び出す画像検索技術がある。画像検索技術の１つとして画像の局所的な特徴を示す局所特徴量を用いるものがあり、また、大量の画像から短いレスポンス時間で類似画像を検索するため、一般的な手法ではクエリ画像との類似の度合いを示すスコアを簡略的に計算している。

上述の手法の１つが、ＢｏＦ（Bag of Features）法と呼ばれるものである。この手法は、ＢｏＷ(Bag of Words)法と呼ばれる文書検索の手法を応用したものである。ＢｏＦ法では、検索対象となる画像から抽出される局所特徴量（以下では「画像特徴量」と記す）のそれぞれをＢｏＷ法における単語に相当するＶｉｓｕａｌ Ｗｏｒｄに対応させて記憶しておく。そして、検索をする際にクエリとなる画像から複数の局所特徴量（以下では「クエリ特徴量」と記す）を抽出し、その局所特徴量のそれぞれに対応するＶｉｓｕａｌ Ｗｏｒｄを取得する。そして、そのＶｉｓｕａｌ Ｗｏｒｄの出現頻度を統計的に処理することで、クエリ画像と検索対象となる画像との類似の度合いを示すスコアを生成し、類似の画像を検索する。

特許文献１には、Ｖｉｓｕａｌ Ｗｏｒｄを用いて画像を検索する手法の概要および、画像から抽出される画像特徴量ベクトルとその画像に関連づけられた文章から抽出されるメディア特徴量ベクトルとを結合させて画像を検索する技術が開示されている。

特許文献２には、クエリ画像に類似する街並画像を決定する技術が記載されている。その技術では、クエリ画像と街並画像のいずれかとの間で、幾何拘束の条件に基づいて局所特徴量の対応関係を取得する。その対応関係に基づいて、検索結果となる画像を決定している。

特開２０１１−１０３０８２号公報 特開２０１１−１１３１９７号公報

ＢｏＦ法では、一般的には、クエリ特徴量に近い画像特徴量の出現頻度をＴＦ／ＩＤＦにより統計処理することで類似の画像を検索している。すると、検索対象となる画像においてあるクエリ特徴量に近い特徴量の出現頻度（ＴＦ）が高く、かつその出現頻度がＩＤＦの項が十分に機能しない程度である場合に、その画像の類似の尺度となるスコアが高くなってしまう。例えば、星マークを１つ含むトルコ国旗に類似する画像を検索すると、トルコ国旗を含む画像ではなく、星マークを大量に含むアメリカ星条旗の画像が検索結果として出力されることがある。

本発明は上記課題を鑑みてなされたものであって、その目的は、クエリ画像から抽出される局所特徴量の数とその局所特徴量に近い検索対象となる画像の局所特徴量の数とが異なる場合に、このような画像が類似の画像として検索されてしまう現象を抑え、検索の精度を向上させる技術を提供することである。

上記課題を解決するために、本発明にかかる画像検索装置は、クエリとなる画像の局所的な特徴をそれぞれ示す複数のクエリ特徴量を取得するクエリ特徴量取得手段と、検索対象となる複数の画像のそれぞれの局所的な特徴を示す画像特徴量から、前記複数のクエリ特徴量のうち１つに対して前記検索対象となる画像につき１つの画像特徴量が選択されるように、前記複数のクエリ特徴量のそれぞれに対応する画像特徴量を選択する画像特徴量選択手段と、前記複数のクエリ特徴量に対応して選択された画像特徴量に基づいて、前記検索対象となる複数の画像のいずれか１つが前記クエリとなる画像に類似する度合いを示すスコアを生成するスコア生成手段と、前記画像について生成されたスコアに基づいて、前記検索対象となる複数の画像から少なくとも１つの画像を選択する画像選択手段と、を含むことを特徴とする。

また、本発明にかかるプログラムは、クエリとなる画像の局所的な特徴をそれぞれ示す複数のクエリ特徴量を取得するクエリ特徴量取得手段、検索対象となる複数の画像のそれぞれの局所的な特徴を示す画像特徴量から、前記複数のクエリ特徴量のうち１つに対して前記検索対象となる画像につき１つの画像特徴量が選択されるように、前記複数のクエリ特徴量のそれぞれに対応する画像特徴量を選択する画像特徴量選択手段、前記複数のクエリ特徴量に対応して選択された画像特徴量に基づいて、前記検索対象となる複数の画像のいずれか１つが前記クエリとなる画像に類似する度合いを示すスコアを生成するスコア生成手段、および、前記画像について生成されたスコアに基づいて、前記検索対象となる複数の画像から少なくとも１つの画像を選択する画像選択手段、としてコンピュータを機能させる。

また、本発明にかかる画像検索方法は、ククエリとなる画像の局所的な特徴をそれぞれ示す複数のクエリ特徴量を取得するステップと、検索対象となる複数の画像のそれぞれの局所的な特徴を示す画像特徴量から、前記複数のクエリ特徴量のうち１つに対して前記検索対象となる画像につき１つの画像特徴量が選択されるように、前記複数のクエリ特徴量のそれぞれに対応する画像特徴量を選択するステップと、前記複数のクエリ特徴量に対応して選択された画像特徴量に基づいて、前記検索対象となる複数の画像のいずれか１つが前記クエリとなる画像に類似する度合いを示すスコアを生成するステップと、前記画像について生成されたスコアに基づいて、前記検索対象となる複数の画像から少なくとも１つの画像を選択するステップと、を含むことを特徴とする。

また、本発明にかかるコンピュータ読み取り可能な記憶媒体は、クエリとなる画像の局所的な特徴をそれぞれ示す複数のクエリ特徴量を取得するクエリ特徴量取得手段、検索対象となる複数の画像のそれぞれの局所的な特徴を示す画像特徴量から、前記複数のクエリ特徴量のうち１つに対して前記検索対象となる画像につき１つの画像特徴量が選択されるように、前記複数のクエリ特徴量のそれぞれに対応する画像特徴量を選択する画像特徴量選択手段、前記複数のクエリ特徴量に対応して選択された画像特徴量に基づいて、前記検索対象となる複数の画像のいずれか１つが前記クエリとなる画像に類似する度合いを示すスコアを生成するスコア生成手段、および、前記画像について生成されたスコアに基づいて、前記検索対象となる複数の画像から少なくとも１つの画像を選択する画像選択手段、としてコンピュータを機能させるためのプログラムを格納する。

本発明によれば、クエリ画像から抽出される局所特徴量に対し、その局所特徴量に近い検索対象となる画像の局所特徴量が多い場合に、この検索対象となる画像が類似の画像として検索されてしまう現象を抑えることができる。

本発明の一態様では、画像検索装置は、前記検索対象となる複数の画像の特徴を示す複数の画像特徴量が分類される複数のクラスタのうちから、前記複数のクエリ特徴量のそれぞれに対応するクラスタを選択するクラスタ選択手段、をさらに含み、前記画像特徴量選択手段は、前記複数のクエリ特徴量のそれぞれに対応するクラスタに分類された複数の画像特徴量から、当該クエリ特徴量に対応する画像特徴量を選択してもよい。

本態様によれば、画像の検索速度を向上させることができる。

本発明の一態様では、前記クラスタ選択手段は、前記複数のクラスタをそれぞれ代表する複数の代表特徴量と前記クエリ特徴量との距離に基づいて前記クエリ特徴量に対応するクラスタを選択し、前記画像特徴量選択手段は、前記複数のクエリ特徴量と、前記クエリ特徴量に対応するクラスタに属する画像特徴量との距離に基づいて、前記選択されるクラスタに分類された複数の画像特徴量から、前記複数のクエリ特徴量のそれぞれに対応する画像特徴量を選択してもよい。

本発明の一態様では、前記画像特徴量選択手段は、前記複数のクエリ特徴量のいずれか１つに対して選択される画像特徴量が、他のクエリ特徴量に対して選択される画像特徴量と重複しないように、前記複数のクエリ特徴量のそれぞれに対応する画像特徴量を選択してもよい。

本態様によれば、検索対象となる画像の局所特徴量に対し、その局所特徴量に近いクエリ画像の局所特徴量が多い場合に、この検索対象となる画像が類似の画像として検索されてしまう現象が抑えられる。

本発明の一態様では、前記画像特徴量選択手段は、前記クエリ特徴量のそれぞれに対応するクラスタに属する複数の画像特徴量から、選択される画像特徴量の数が前記検索対象となる画像につき１つとなり、かつ、前記複数のクエリ特徴量のいずれか１つに対して選択される画像特徴量が、他のクエリ特徴量に対して選択される画像特徴量と重複しない条件を満たす画像特徴量の全てを当該クエリ特徴量に対応する画像特徴量として選択してもよい。

本発明の一態様では、画像検索装置は、前記検索対象となる画像のそれぞれから画像特徴量を抽出する画像特徴量抽出手段と、前記抽出された画像特徴量の少なくとも一部が分類される前記複数のクラスタを生成するクラスタ生成手段と、をさらに含み、前記クラスタ生成手段は、あるクラスタに属する画像特徴量のうち前記検索対象となる複数の画像のいずれか１つに対応する画像特徴量の数が所定の値を超えないように前記複数のクラスタを生成してもよい。

本態様によれば、画像の検索をより高速に行うことができる。

第１の実施形態にかかる画像検索システムの構成の一例を示す図である。 第１の実施形態にかかる画像検索装置の構成の一例を示す図である。 並列計算装置の構成の一例を示す図である。 第１の実施形態にかかる画像検索装置の機能を示す機能ブロック図である。 第１の実施形態にかかるインデックス生成部の機能構成を示す機能ブロック図である。 検索対象となる画像の一例を示す図である。 画像から抽出される画像特徴ベクトルの概念を示す図である。 代表ベクトルの木構造の一例を示す図である。 第１の実施形態にかかる画像検索部の機能構成を示す機能ブロック図である。 第１の実施形態にかかる画像検索部の処理の概略的な処理フローの一例を示す図である。 装置内メモリでのデータ配置の一例を示す図である。 装置内メモリでの代表ベクトルの配置の一例を示す図である。 クエリとなる画像を入力する画面の一例を示す図である。 距離計算の処理フローの一例を示す図である。 クエリ画像から抽出されるクエリ特徴ベクトルと、検索対象となる複数の画像から抽出される画像特徴ベクトルとの対応の一例を示す図である。 画像特徴ベクトル選択部の処理フローの一例を示す図である。 クエリ特徴ベクトルに対して画像特徴ベクトルを選択する場合の例を示す図である。 クエリ画像における局所的特徴と、検索対象となる画像における局所的な特徴との対応の一例を示す図である。 クエリ画像における局所的特徴と、検索対象となる画像における局所的な特徴との対応の比較例を示す図である。 クエリ特徴ベクトルと画像特徴ベクトルの距離のばらつきの一例を示す図である。 クエリ特徴ベクトルに対応する画像を統計処理した結果の一例を示す図である。 クラスタ画像特徴量格納部に格納されるデータの一例を示す図である。 第２の実施形態にかかる画像検索部の機能構成を示す機能ブロック図である。 第２の実施形態にかかる画像検索部の処理の概要を示す処理フローの一例を示す図である。 ３番目の画像特徴クラスタにおける画像特徴ベクトルの分布とクエリ特徴ベクトルによる選択とを説明する図である。 画像スコアを生成するために用いられる転置行列の一例を示す図である。 第３の実施形態にかかる画像検索部の処理の概要を示す処理フローの一例を示す図である。

以下では、本発明の実施形態について図面に基づいて説明する。出現する構成要素のうち同一機能を有するものには同じ符号を付し、その説明を省略する。

［第１の実施形態］
図１は、本発明の第１の実施形態にかかる画像検索システムの構成の一例を示す図である。画像検索システムは、画像検索装置１と、ウェブサーバ２と、クライアント装置３とを含む。ウェブサーバ２は、例えばウェブサーバプログラムが動作するサーバハードウェアであり、クライアント装置３は、例えばウェブブラウザのプログラムが動作するパーソナルコンピュータや、スマートフォンである。画像検索システムは画像検索を行う動作の概要は以下の通りである。はじめに、ウェブサーバ２は、インターネット等のネットワークを介してクライアント装置３から画像検索に用いるクエリとなる画像（以下、「クエリ画像」と記述する）を取得し、そのクエリ画像を画像検索装置１に入力させる。次に画像検索装置１は、入力された画像に類似する１または複数の画像を検索し、ウェブサーバ２に出力する。ウェブサーバ２は、画像検索装置１が検索した画像をクライアント装置３に表示させるデータを出力する。

図２は、第１の実施形態にかかる画像検索装置１の構成の一例を示す図である。画像検索装置１は、ＣＰＵ１１、記憶部１２、通信部１３、並列計算装置１４およびバス１５を含む。

ＣＰＵ１１は、記憶部１２に格納されているプログラムに従って動作する。またＣＰＵ１１は通信部１３や並列計算装置１４を制御する。なお、上記プログラムは、インターネット等のネットワークを介して提供されるものであってもよいし、ＤＶＤ−ＲＯＭやＵＳＢメモリ等のコンピュータで読み取り可能な情報記憶媒体に格納されて提供されるものであってもよい。

記憶部１２は、ＲＡＭやＲＯＭ等のメモリ素子やハードディスクドライブ等によって構成されている。記憶部１２は、上記プログラムを格納する。また、記憶部１２は、各部から入力される情報や演算結果を格納する。

通信部１３は、ウェブサーバ２等の他の装置と通信する機能を実現するものであり、例えばネットワークカードのような通信手段で構成されている。ネットワークカードは、通信用の集積回路や通信端子を含んでいる。通信部１３は、ＣＰＵ１１の制御に基づいて、他の装置から受信した情報をＣＰＵ１１や記憶部１２に入力し、他の装置に情報を送信する。

バス１５は、ＣＰＵ１１、記憶部１２、通信部１３および並列計算装置１４との間でデータをやりとりする経路を構成する。例えば、ＣＰＵ１１や記憶部１２と並列計算装置１４とはバス１５の中の拡張バスを介して接続される。

並列計算装置１４は、並列計算によって同種の計算を大量に行うことを得意とするハードウェアである。並列計算装置１４は、例えばＧＰＵ（Graphics Processing Unit）である。図３は、並列計算装置１４の構成の一例を示す図である。並列計算装置１４は、複数の並列実行部４０と、装置内メモリ４５とを含む。また各並列実行部４０は、複数のプロセッサ４１と、命令ユニット４２と、高速メモリ４３とを含む。

複数のプロセッサ４１のそれぞれは、浮動小数点計算や、装置内メモリ４５や高速メモリ４３との間でのデータの読込みや書込み等の処理を行う。命令ユニット４２は、装置内メモリ４５等に格納されるプログラムに基づいて、その命令ユニット４２を含む並列実行部４０に含まれる複数のプロセッサ４１に処理をさせる。ある並列実行部４０に含まれる複数のプロセッサ４１は、その並列実行部４０に含まれる一つの命令ユニット４２からの指示によって、同一の命令を処理する。こうすると、複数のプロセッサ４１を１つの命令ユニット４２で制御できるため、命令ユニット４２の回路の規模の増加を抑えることができる。並列計算装置１４に含まれるプロセッサ４１の数をＣＰＵ１１に比べて増やすことが可能になり、特定の計算処理では、複数の独立性の高いプロセッサを用いる場合より高速化が容易になる。

装置内メモリ４５は、ＤＲＡＭからなり、そのＤＲＡＭは記憶部１２に用いられるＲＡＭより高速にアクセス可能なものである。装置内メモリ４５は、バス１５を介して、ＣＰＵ１１や記憶部１２と接続されている。なお、並列計算装置１４は、ＤＭＡ転送により装置内メモリ４５と記憶部１２との間でデータを転送する回路も有する。高速メモリ４３は、装置内メモリ４５より高速にアクセス可能なＳＲＡＭ等からなる。プロセッサ４１が高速メモリ４３にアクセスする際のレイテンシは、プロセッサ４１がその内部レジスタにアクセスする際のレイテンシとほとんど変わらない。ここで、装置内メモリ４５も高速メモリ４３も複数のプロセッサ４１から共通にアクセスできる共通メモリである。

図４は、第１の実施形態にかかる画像検索装置１の機能を示す機能ブロック図である。画像検索装置１は、機能的に、インデックス生成部５１、および画像検索部５２を含む。これらの機能は、ＣＰＵ１１が記憶部１２に格納されたプログラムを実行し、通信部１３や並列計算装置１４を制御し、また、並列計算装置１４がその並列計算装置１４向けのプログラムを実行することで実現される。

［インデックスの生成］
以下では、画像特徴ベクトル２２をクラスタに分類し、インデックスを生成する処理について説明する。

インデックス生成部５１は、検索対象となる複数の画像から、画像検索の際に用いる画像特徴ベクトル２２や、その画像特徴ベクトル２２の選択を容易にするインデックスを生成する。画像検索部５２は、インデックスや画像特徴ベクトル２２を用いて、クエリ画像に類似する画像を検索する。

図５は、インデックス生成部５１の機能構成を示す機能ブロック図である。インデックス生成部５１は、機能的に、画像特徴ベクトル抽出部６１と、クラスタ生成部６２とを含む。クラスタ生成部６２は、クラスタのインデックスとなる代表ベクトルの木構造を生成し、木構造代表ベクトル格納部７２にインデックスに関連する情報を格納する。また、クラスタベクトル格納部７１は、その木構造の葉となるクラスタ（代表ベクトルが代表するクラスタ）に属する画像特徴ベクトル２２の情報を格納する。クラスタベクトル格納部７１、木構造代表ベクトル格納部７２は、具体的には記憶部１２により構成される。

画像特徴ベクトル抽出部６１は、主にＣＰＵ１１、記憶部１２および並列計算装置１４により実現される。画像特徴ベクトル抽出部６１は、記憶部１２に格納されている複数の画像であって検索対象となる複数の画像のそれぞれから、１または複数の画像特徴ベクトル２２を抽出する。また、画像特徴ベクトル抽出部６１は、抽出された画像特徴ベクトル２２を、その画像特徴ベクトル２２が抽出された画像と関連付けて記憶部１２に記憶させる。

図６は、検索対象となる画像の一例を示す図である。図７は、画像から抽出される画像特徴ベクトル２２の概念を示す図である。画像から抽出される画像特徴ベクトル２２のそれぞれは、その画像の局所的な特徴を示す局所特徴量である。画像特徴ベクトル２２のそれぞれは、例えば１２８の要素（次元）をもつベクトルである。画像から画像特徴ベクトル２２を抽出するために、ＳＩＦＴ（Scale-Invariant Feature transform）、ＳＵＲＦ（Speeded Up Robust Features）などの公知の手法を用いてよい。画像特徴ベクトル２２のそれぞれが有する要素の数は、画像からの抽出の手法などに応じて変化させてよい。また１つの画像から抽出される画像特徴ベクトル２２の数は、予め定められた数（例えば３００）としてよいが、単純な画像から抽出される画像特徴ベクトル２２の数はその予め定められた数より少なくなってもよい。

クラスタ生成部６２は、主にＣＰＵ１１、記憶部１２および並列計算装置１４により実現される。クラスタ生成部６２は、クラスタリングにより、画像特徴ベクトル抽出部６１により抽出された複数の画像特徴ベクトル２２の少なくとも一部を複数のクラスタに分類する。言い換えれば、抽出された画像特徴ベクトル２２の少なくとも一部が分類される複数のクラスタを生成する。また、それらのクラスタのそれぞれを代表する代表ベクトルを生成する。画像特徴ベクトル２２が分類されるクラスタは多段階であってよい。それに対応し、クラスタに分類する処理は１段階の処理とは限らず、多段階の処理であってよい。以下では、その多段階の処理を再帰的に呼び出すことにより実現する処理の例について説明する。なお、具体的な例では、２段階の処理を行っており、１段目で画像特徴ベクトル抽出部６１により抽出された複数の画像特徴ベクトル２２を１０２４個のクラスタに分類し、さらに２段目でその１０２４個のクラスタのそれぞれを５１２個のクラスタに分類する。

クラスタ生成部６２の各段の処理では、クラスタリングにより、与えられた複数の画像特徴ベクトル２２を与えられた個数のクラスタに分類し、複数のクラスタを生成し、さらにその生成されたクラスタの代表ベクトルを生成し、生成された代表ベクトルをその段の代表ベクトルとして木構造代表ベクトル格納部７２に格納する。処理中の段が最下段でない場合は、クラスタ生成部６２は処理中の段で生成されたクラスタのそれぞれに属する複数の画像特徴ベクトル２２を入力情報として、次の段の処理を再帰的に呼び出す。代表ベクトルは、例えばその分類されたクラスタに属する画像特徴ベクトル２２の重心であり、そのクラスタを代表するベクトルである。またクラスタ生成部６２は、最下段の処理で生成されたクラスタごとに、そのクラスタに属する画像特徴ベクトル２２をクラスタベクトル格納部７１に格納する。

上述の例の場合、１段目の処理では、クラスタ生成部６２は、与えられた画像特徴ベクトル２２を１０２４個のクラスタに分類し、その分類された１段目の各クラスタの代表ベクトルを生成し、生成された１段目の代表ベクトルを木構造代表ベクトル格納部７２に格納する。２段目の処理では、クラスタ生成部６２は、１段目に生成された１０２４個のクラスタのそれぞれに属する複数の画像特徴ベクトル２２を入力情報として、更に５１２個のクラスタに分類し、その分類された２段目の各クラスタの代表ベクトルを生成し、生成された下位の段の代表ベクトルを木構造代表ベクトル格納部７２に格納する。２段目のクラスタを全て生成するとその２段目のクラスタの総数は（１０２４×５１２）個となる。さらにクラスタ生成部６２は、２段目に生成されたクラスタごとに、そのクラスタに属する画像特徴ベクトル２２をクラスタベクトル格納部７１に格納する。以下では、説明の容易のため、１段目のクラスタを代表する代表ベクトルを上位代表ベクトルと記し、最下段（上述の例では２段目）のクラスタを代表する代表ベクトルを代表特徴ベクトルと記す。また最終的に生成されたクラスタ（上述の例では２段目のクラスタ）を画像特徴クラスタとも記す。

画像特徴ベクトル２２をクラスタに分類する際には、ｋ−ｍｅａｎｓ法等の公知のクラスタリング手法を用いればよい。クラスタの数は、後述の画像検索部５２の処理との関係で、２のべき乗が好適であるが、２のべき乗でなくてもよい。また全ての画像に含まれる画像特徴ベクトル２２を分類すると、それぞれの画像特徴クラスタには、複数の画像特徴ベクトル２２が属する。クラスタ生成部６２の再帰処理を２段階行う事で、木構造代表ベクトル格納部７２に、２階層の情報を格納する事ができる。なお、画像特徴ベクトル抽出部６１やクラスタ生成部６２の計算は、並列計算装置１４を用いずに行ってもよい。ただしこれらの計算は並列計算装置１４を用いる方が望ましい。比較実験によれば、並列計算装置１４を用いる場合の計算速度が、用いない場合の２０から２００倍になるからである。

図８は、代表ベクトルの木構造の一例を示す図である。クラスタ生成部６２が上述の２段階の処理を行う場合、２段階のクラスタに対応する２段階の代表ベクトルが木構造を構成する。上位代表ベクトルの数は１０２４個であり、上位代表ベクトルのそれぞれは、５１２個の代表特徴ベクトルの親となっている。このように多段のクラスタによる木構造を用いる場合には、画像検索部５２はその木構造に応じた代表ベクトルに親子関係があることを利用して検索を行うことができる。

［画像を検索する処理］
図９は、画像検索部５２の機能構成を示す機能ブロック図である。画像検索部５２は、機能的に、代表ベクトル転送部８１、クエリ特徴ベクトル取得部８２、上位代表ベクトル距離計算部８３、代表クラスタ選択部８４、代表特徴ベクトル距離計算部８５、画像特徴クラスタ選択部８６、画像特徴ベクトル転送部８７、画像特徴ベクトル距離計算部８８、画像特徴ベクトル選択部８９、画像スコア生成部９０および検索結果画像選択部９１を含む。

図１０は、第１の実施形態にかかる画像検索部５２の処理の概要を示す図である。以下では、図１０が示す処理フローに従い、画像検索部５２に含まれる各機能について説明する。

［並列計算装置の初期化］
代表ベクトル転送部８１は、主に並列計算装置１４と、記憶部１２とにより実現される。代表ベクトル転送部８１は、並列計算装置１４を初期化する処理（ステップＳ１０１）として、木構造代表ベクトル格納部７２に格納された、複数の上位代表ベクトルおよび複数の代表特徴ベクトルを、複数のプロセッサ４１から共通にアクセスできる装置内メモリ４５に転送する。

代表ベクトル転送部８１が上記データを記憶部１２から装置内メモリ４５に転送する際には、並列計算装置１４やバス１５のＤＭＡ（Direct Memory Access）機能を用いる。

図１１は、装置内メモリ４５でのデータ配置の一例を示す図である。装置内メモリ４５には、代表特徴ベクトルを格納する領域と、上位代表ベクトルを格納する領域と、１つの画像特徴クラスタに含まれる画像特徴ベクトル２２を格納する領域とが設けられる。代表ベクトル転送部８１は、記憶部１２に記憶される複数の代表ベクトルの情報を、予め割り当てられた装置内メモリ４５のメモリ領域に格納する。画像特徴クラスタを格納する領域へのデータの格納については後述する。

ここで、代表特徴ベクトルの要素数が１２８次元、代表特徴ベクトルの数は画像特徴クラスタの数と同じ（１０２４×５１２）個、各要素が１バイトの整数型とすると、その複数の代表特徴ベクトルの全てのデータ量は、（１０２４×５１２×１２８）バイト（Ｂ）、つまり６４ＭＢとなる。また、この場合、複数の上位代表ベクトルの数は１０２４であるので、同様に複数の上位代表ベクトルのデータ量は（１０２４×１２８）バイト、つまり１２８ＫＢとなる。例えば現行のＧＰＵに搭載される装置内メモリ４５のメモリ容量は１ＧＢ程度であり、装置内メモリ４５の容量も１ＧＢであるとすると、複数の代表ベクトルのデータ量は装置内メモリ４５の容量より小さい。

一方、画像の数が１００万、１つの画像から抽出される画像特徴ベクトル２２の数が３００とすると、複数の画像特徴クラスタに含まれる画像特徴ベクトル２２のデータ量は、（１００万×３００×１２８）バイト、つまり約３６ＧＢになり、装置内メモリ４５には格納できない。一方、１つの画像特徴クラスタあたりの平均的な画像特徴ベクトル２２の数は、（１００万×３００÷（１０２４×５１２））、つまり約６００であるので、データ量は７５ＫＢ程度である。クラスタリングにより画像特徴クラスタに含まれる画像特徴ベクトル２２の数が多少変動したとしても、複数の代表特徴ベクトルのデータ量と、複数の上位代表ベクトルのデータ量と、１つの画像特徴クラスタに含まれる画像特徴ベクトル２２のデータ量との和は、装置内メモリ４５の容量より小さくなる。

図１２は、装置内メモリ４５での代表ベクトルの配置の一例を示す図である。装置内メモリ４５に格納される代表ベクトルの各要素のサイズは４バイトであり、要素の順に並んでいる。また、ある代表ベクトルのデータの先頭アドレスは、装置内メモリ４５から一括して読み出すことのできるデータのバイト数（例えば３２や６４）の倍数となっている。このデータ構造は、後述する距離計算の処理において、装置内メモリ４５に格納されるデータを複数のプロセッサ４１に一括して読込ませるためのものである。代表ベクトル転送部８１は、代表ベクトルの各要素のサイズが１バイトであっても、一括して読込むために、各要素のサイズを４バイトに変換したデータを装置内メモリ４５に転送している。なお、上位代表ベクトルや、１つの画像特徴クラスタ内の画像特徴ベクトル２２も、同様のデータ構造によって装置内メモリ４５に格納される。装置内メモリ４５内での複数の代表特徴ベクトル、複数の上位代表ベクトル、および１つの画像特徴クラスタに含まれる画像特徴ベクトル２２のデータ量は４倍になるが、この例ではそれらのデータ量の和が装置内メモリ４５の容量より小さい点は変わりない。本実施形態においては、少なくとも装置内メモリ４５内での複数の代表特徴ベクトル、および複数の上位代表ベクトルのデータ量の和が装置内メモリ４５の容量に収まるように、画像特徴クラスタや代表ベクトルの数を調整すればよい。

［クエリ特徴ベクトルの取得］
クエリ特徴ベクトル取得部８２は、主にＣＰＵ１１、記憶部１２、および並列計算装置１４によって実現される。クエリ特徴ベクトル取得部８２は、並列計算装置１４の初期化の後に、クエリ画像から１または複数のクエリ特徴ベクトルを取得する（ステップＳ１０２）。また、クエリ特徴ベクトル取得部８２は、クエリ画像から抽出される１または複数のクエリ特徴ベクトルを共通メモリである装置内メモリ４５に格納する。

クエリ特徴ベクトル取得部８２は、はじめに、クエリ画像を、クライアント装置３からウェブサーバ２を介して取得する。図１３は、クエリ画像を入力する画面の一例を示す図である。クライアント装置３は、ウェブサーバ２が生成したデータにより本画面を表示する。クエリ画像は、ユーザがクライアント装置３内の画像ファイルをアップロードすることで取得されてもよいし、なんらかのウェブページに表示される画像のＵＲＬを送ることで取得されてもよいし、写真共有サービス等に格納される画像からクエリ画像を選択することで取得されてもよい。次に、クエリ特徴ベクトル取得部８２は、ウェブサーバ２から、取得したクエリ画像を取得し、そのクエリ画像から１または複数のクエリ特徴ベクトルを抽出し取得する。クエリ特徴ベクトルは、画像特徴ベクトル抽出部６１が画像特徴ベクトル２２を抽出する手法と同じ手法を用いて生成される。次にクエリ特徴ベクトル取得部８２はクエリ特徴ベクトルを装置内メモリ４５に格納する。ここで、ＣＰＵ１１がクエリ特徴ベクトルを抽出し、並列計算装置１４がクエリ特徴ベクトルを装置内メモリ４５にロードしてもよいし、クエリ画像を並列計算装置１４にロードし、並列計算装置１４がクエリ特徴ベクトルを抽出して装置内メモリ４５に格納してもよい。

［画像特徴クラスタの選択］
次に、画像検索部５２は、複数のクエリ特徴ベクトルのそれぞれに対応する画像特徴クラスタを選択する（ステップＳ１０３）。この処理は、上位代表ベクトル距離計算部８３、代表クラスタ選択部８４、代表特徴ベクトル距離計算部８５、および画像特徴クラスタ選択部８６が行う。

上位代表ベクトル距離計算部８３は、並列計算装置１４を中心として実現される。上位代表ベクトル距離計算部８３は、複数の上位代表ベクトルのそれぞれと、クエリ特徴ベクトルとの距離とを、複数の並列のプロセッサ４１を用いて計算する。以下では上位代表ベクトル距離計算部８３での距離計算の詳細について説明する。なお、上位代表ベクトル距離計算部８３、代表クラスタ選択部８４、代表特徴ベクトル距離計算部８５、画像特徴クラスタ選択部８６、画像特徴ベクトル距離計算部８８および画像特徴ベクトル選択部８９の処理は、クエリ画像から抽出されたクエリ特徴ベクトルのそれぞれについて行う。

図１４は距離計算の処理フローの一例を示す図である。はじめに、上位代表ベクトル距離計算部８３は、クエリ特徴ベクトルを装置内メモリ４５から距離計算を行う並列実行部４０の高速メモリ４３にロードする（ステップＳ２０１）。次に、計算対象となるベクトル（ここでは上位代表ベクトル）の各要素を装置内メモリ４５からその要素の計算を行うプロセッサ４１のレジスタにロードする（ステップＳ２０２）。この際、複数のプロセッサ４１は、装置内メモリ４５から計算対象ベクトルのデータを一括で読込む。それは、計算対象となるベクトルのデータが代表ベクトル転送部８１等によって予めその一括の読込ができるよう装置内メモリ４５に記憶されているからである。次に、上位代表ベクトル距離計算部８３は、レジスタに格納された計算対象となるベクトルの要素と、その要素に対応するクエリ特徴ベクトルの要素とを減算し、さらにその減算結果を２乗する（ステップＳ２０３）。距離計算においては、減算結果を２乗するかわりに減算結果の絶対値を用いるなど他の距離関数を用いてよい。距離関数で用いる距離は、ステップＳ２０３のようなユークリッド距離（Ｌ２）に限らず、コサイン、マンハッタン距離（Ｌ１）等であってもよい。

次に、計算対象となるベクトルの各要素についてのステップＳ１０３の計算結果を合計する（ステップＳ２０４）。そして、上位代表ベクトル距離計算部８３は、合計結果を装置内メモリ４５に格納する（ステップＳ２０５）。なお、ある並列実行部４０に含まれる、同一の命令を実行するプロセッサ４１の数がクエリ特徴ベクトルや計算対象となるベクトルの要素の数より少なければ、ステップＳ２０２からステップＳ２０４の処理は、プロセッサ４１の数にあわせて分割され、複数回実行される。また、並列実行部４０が複数ある場合、別の並列実行部４０に、上位代表ベクトル距離計算部８３は、別の計算対象となるベクトルについてステップＳ２０１からＳ２０５の処理を実行させる。また、クエリ画像から抽出された他のクエリ特徴ベクトルについても並列に計算してもよい。こうすることで、クエリ特徴ベクトルと他の複数の計算対象のベクトルとの距離計算はＧＰＵのような並列計算装置１４の並列計算能力にあわせて並列に計算される。この距離計算の処理内容からわかるように、装置内メモリ４５に適切に配置された複数のベクトルと、クエリ特徴ベクトルとの距離計算はＧＰＵのようなハードウェアと親和性が高く、非常に高速に処理される。

代表クラスタ選択部８４は、並列計算装置１４を中心として実現される。代表クラスタ選択部８４は、上位代表ベクトル距離計算部８３で計算されたクエリ特徴ベクトルと複数の上位代表ベクトルのそれぞれとの距離に基づいて、複数の代表特徴ベクトルの集合から１つの集合を選択する。より詳細には、例えば、クエリ特徴ベクトルとの距離が最も短い上位代表ベクトルの子となる複数の代表特徴ベクトルの集合を選択する。この代表特徴ベクトルの集合のそれぞれは１段目のクラスタ（代表クラスタ）に対応する。代表特徴ベクトルの集合の選択は、それに対応する代表クラスタの選択にも相当する。なお、上位代表ベクトルのそれぞれは、複数の代表特徴ベクトルを代表しているとみることもできる。代表クラスタ選択部８４は、より具体的には、その代表ベクトルの集合を格納するメモリ内の領域の先頭アドレスを計算することによってその集合を選択する。例えば、ある上位代表ベクトルの子となる代表特徴ベクトルの数が上位代表ベクトルにかかわらず一定であれば、距離が最も短い上位代表ベクトルが何番目かわかれば、かけ算等の単純な計算で先頭アドレスを求めることが可能となる。そうすれば、分岐や追加のメモリアクセスを必要とするような演算を用いずに済むため、ＧＰＵのようなハードウェアの性能をより活かした処理ができる。

代表特徴ベクトル距離計算部８５は、並列計算装置１４を中心として実現される。代表特徴ベクトル距離計算部８５は、複数の代表特徴ベクトルの少なくとも一部のそれぞれと、クエリ特徴ベクトルとの距離とを、複数の並列のプロセッサ４１を用いて計算する。ここで計算対象となる代表特徴ベクトルは、代表クラスタ選択部８４で選択された集合に属する代表特徴ベクトルである。代表特徴ベクトル距離計算部８５は、上位代表ベクトル距離計算部８３が距離を計算するものと同様に、図１４のフローに従い距離を計算する。ただし、計算対象ベクトルは上述の代表特徴ベクトルである。上位代表ベクトル距離計算部８３と同様に、この処理内容はＧＰＵのようなハードウェアと親和性が高く、非常に高速に処理される。

画像特徴クラスタ選択部８６は、並列計算装置１４を中心として実現される。画像特徴クラスタ選択部８６は、代表特徴ベクトル距離計算部８５で計算されたクエリ特徴ベクトルと複数の代表特徴ベクトルのそれぞれとの距離に基づいて、複数の画像特徴クラスタから画像特徴クラスタを選択する。より詳細には、例えば、クエリ特徴ベクトルとの距離が最も短い代表特徴ベクトルが代表する画像特徴クラスタを選択する。

なお、本実施形態では上位代表ベクトルと代表特徴ベクトルのように代表ベクトルが２段階の木構造の構成になっているが、上位代表ベクトルを設けない１段の構成にしてもよい。その場合、上位代表ベクトル距離計算部８３および代表クラスタ選択部８４の処理は不要であり、代表特徴ベクトル距離計算部８５は全ての代表特徴ベクトルについて距離計算を行う。また、３段以上の構成にしてもよい。

［画像特徴ベクトルの選択］
画像特徴クラスタが選択された後には、画像検索部５２は、複数のクエリ特徴ベクトルのそれぞれと、選択された画像特徴クラスタに属する画像特徴ベクトル２２との距離とを計算し、その距離に基づいてそのクエリ特徴ベクトルに対応する１または複数の画像特徴ベクトル２２を選択する（ステップＳ１０４）。この処理は、画像特徴ベクトル転送部８７、画像特徴ベクトル距離計算部８８、および画像特徴ベクトル選択部８９が行う。

画像特徴ベクトル転送部８７は、記憶部１２および並列計算装置１４を中心として実現される。画像特徴ベクトル転送部８７は画像特徴クラスタ選択部８６で選択された画像特徴クラスタに属する複数の画像特徴ベクトル２２を、クラスタベクトル格納部７１から、複数のプロセッサ４１から共通にアクセスできる装置内メモリ４５に転送する。画像特徴ベクトル転送部８７は、代表ベクトル転送部８１が代表特徴ベクトル等を転送するのと同じように、装置内メモリ４５に格納されるデータを複数のプロセッサ４１に一括して読込ませるように画像特徴ベクトル２２のデータを配置する。

画像特徴ベクトル距離計算部８８は、並列計算装置１４を中心として実現される。画像特徴ベクトル距離計算部８８は、複数の画像特徴ベクトル２２のそれぞれと、クエリ特徴ベクトルとの距離とを、複数の並列のプロセッサ４１を用いて計算する。ここで計算に用いる画像特徴ベクトル２２は、画像特徴クラスタ選択部８６で選択された画像特徴クラスタに属する画像特徴ベクトル２２である。そのデータは画像特徴ベクトル転送部８７により装置内メモリ４５に転送されている。画像特徴ベクトル距離計算部８８は、上位代表ベクトル距離計算部８３が距離を計算するものと同様に、クエリ特徴ベクトルのそれぞれについて、図１４のフローに従い距離を計算する。ただし、計算対象ベクトルは画像特徴ベクトル２２である。上位代表ベクトル距離計算部８３と同様に、この処理内容はＧＰＵのようなハードウェアと親和性が高く、非常に高速に処理される。

画像特徴ベクトル選択部８９は、並列計算装置１４を中心として実現される。画像特徴ベクトル選択部８９は、複数のクエリ特徴ベクトルと、選択された画像特徴クラスタに属する複数の画像特徴ベクトル２２と、の近さに基づいて、複数のクエリ特徴ベクトルのそれぞれに対応する複数の画像特徴ベクトル２２を選択する。近さとして、この例では距離を用いている。ここで、画像特徴ベクトル選択部８９は、以下の条件を満たす複数の画像特徴ベクトル２２を選択する。その条件は、あるクエリ特徴量に対して、検索対象となる複数の画像のそれぞれにつき１つの画像特徴ベクトル２２が選択されることである。この条件により、１つのクエリ特徴ベクトルに対して、ある１つの画像から抽出された複数の画像特徴ベクトル２２が対応することを防ぐ。

図１５は、クエリ画像から抽出されるクエリ特徴ベクトルと、検索対象となる複数の画像から抽出される画像特徴ベクトル２２との対応の一例を示す図である。図１５の左側にある１つの矩形がクエリ画像を示し、その中にある×印はそのクエリ画像から抽出されたクエリ特徴ベクトルを示す。図１５の右側に上下方向に並ぶ矩形のそれぞれは検索対象となる画像を示し、その矩形のそれぞれの中にある×印はその画像から抽出される画像特徴ベクトル２２を示す。図１５に示すように、あるクエリ画像と、検索対象となる画像うち１つとの間では１つのクエリ特徴ベクトルは、１つの画像特徴ベクトル２２にしか対応しない。一方、そのクエリ特徴ベクトルに対して、検索対象となる他の画像から抽出される画像特徴ベクトル２２が存在しうる。もちろん、そのクエリ特徴ベクトルに対応する画像特徴ベクトル２２を含まない画像があってもよいので、あるクエリ特徴ベクトルに対応しある１つの画像から抽出される画像特徴ベクトル２２の数は１または０となる。

図１６は、画像特徴ベクトル選択部８９の処理フローの一例を示す図である。画像特徴ベクトル選択部８９は、クエリ特徴ベクトルごとに図１６に示す処理を行う。また、後述する選択済特徴リストはあるクエリ画像に対する全てのクエリ特徴ベクトルの間で共通して用い、選択済特徴リストは１番目のクエリ特徴ベクトルに対し処理を始める前に初期化される。以下ではあるクエリ特徴ベクトルについての処理について説明する。

はじめに、画像特徴ベクトル選択部８９は、選択されたクラスタに属する画像特徴ベクトル２２から、クエリ特徴ベクトルとの距離があらかじめ定められた閾値より小さいものを取得し、それらを距離によりソートする（ステップＳ３０１）。

図１７は、クエリ特徴ベクトルに対して画像特徴ベクトル２２を選択する場合の例を示す図である。本図の実線の円は選択されたクラスタを示し、その円の中心にある黒丸はそのクラスタの代表ベクトル２４１（正確にはベクトルの座標）を示し、白丸はそのクラスタに含まれる画像特徴ベクトル２２を示している。プラス記号はクエリ特徴ベクトルを示している。図１７の例では、クエリ特徴ベクトル３２１からの距離が閾値の範囲となる、クエリ特徴ベクトル３２１の白丸を中心とする破線内にある画像特徴ベクトル２２１，２２３がクエリ特徴ベクトル３２１に対応して取得されソートされる。またクエリ特徴ベクトル３２２に対しては、画像特徴ベクトル２２２，２２３が取得されソートされる。ここで、閾値を変化させることで、検索精度をコントロールすることが可能となる。具体的には、閾値が小さいほど、少数の画像特徴ベクトル２２を検索結果として出力可能となり、閾値が大きいほど、広範囲の画像特徴ベクトル２２を検索結果として出力可能となる。なお、閾値を最大とした場合には、クラスタに含まれる画像特徴ベクトル全てを選択することになる。なお、距離が範囲内になるか否かではなく、距離が近い順にあらかじめ定められた数のクエリ特徴ベクトルを取得するようにしてもよい。なお、図１７では、分かりやすさのために、クラスタの代表ベクトル、そのクラスタに含まれる画像特徴ベクトル、およびクエリ特徴ベクトルを２次元の図面を用いて図示しているが、実際は、これらのベクトルは２次元ではなく１２８次元である。

次に画像特徴ベクトル選択部８９は、選択済画像リストに属する画像をクリアし初期化する（ステップＳ３０２）。次に、ソートされた画像特徴ベクトル２２のうち１番目の画像特徴ベクトル２２を処理対象として取得する（ステップＳ３０３）。そして、その処理対象の画像特徴ベクトル２２が、選択済画像リストにある画像から抽出されておらず（ステップＳ３０４のＮ）、かつ、選択済特徴リストに存在しない（ステップＳ３０５のＮ）場合には、処理対象となる画像特徴ベクトル２２を、このクエリ特徴ベクトルに対応するものとして選択する（ステップＳ３０６）。そして、選択された画像特徴ベクトル２２を選択済特徴リストに追加し（ステップＳ３０７）、また選択された画像特徴ベクトル２２が抽出された画像を選択済画像リストに追加する（ステップＳ３０８）。処理対象の画像特徴ベクトル２２が、選択済画像リストにある画像から抽出されている（ステップＳ３０４のＹ）、または、選択済特徴リストに存在する（ステップＳ３０５のＹ）場合には、ステップＳ３０６からステップＳ３０８の処理をスキップする。

そして、処理対象となる画像特徴ベクトル２２が最後の画像特徴ベクトル２２であれば（ステップＳ３０９のＹ）、このクエリ特徴ベクトルに対する処理は終了し、処理対象となる画像特徴ベクトル２２が最後の画像特徴ベクトル２２でなければ（ステップＳ３０９のＮ）、次の画像特徴ベクトル２２を処理対象として取得し（ステップＳ３１０）、ステップＳ３０４から繰り返す。

ステップＳ３０４等の処理により、あるクエリ特徴ベクトルに対し１つの画像から抽出された複数の画像特徴ベクトル２２が選択される現象が抑えられる。ステップＳ３０５等の処理により、例えば図１７における画像特徴ベクトル２２３が複数のクエリ特徴ベクトルによって複数回選択される現象が抑えられる。言い換えれば、あるクエリ特徴ベクトルに対して選択される画像特徴ベクトル２２が、他のクエリ特徴ベクトルに対して選択される画像特徴ベクトル２２と重複しない。その結果、クエリ画像から抽出されるクエリ特徴ベクトルと、検索対象となる画像のいずれか１つから抽出された画像特徴ベクトル２２のうち選択されるものとが１対１で対応する。

図１８は、クエリ画像における局所的特徴（クエリ特徴ベクトルに対応）と、検索対象となる画像における局所的な特徴（画像特徴ベクトル２２に対応）との対応の一例を示す図である。図１８のうち上側の矩形がクエリ画像を、下側の矩形が検索対象となる画像を示す。これらの画像に含まれる複数の三角形は、互いに類似する局所的特徴を示す。このように、クエリ画像における局所的特徴と、検索対象となる画像における局所的な特徴とが１対１に対応する。

図１９は、クエリ画像における局所的特徴と、検索対象となる画像における局所的な特徴との対応の比較例を示す図である。本図はステップＳ３０４およびＳ３０５の処理を行わない場合の例である。この場合、多対多の対応関係となり、選択される画像特徴ベクトル２２の数が飛躍的に増大してしまう。

図１８と図１９とを比較してもわかるように、上述の処理により、クエリ画像と、検索対象となる画像の１つとで、局所的な特徴量の数が異なるものが同じものより多くの画像特徴ベクトル２２が抽出されることを防ぐことが可能となる。これにより、後述のスコア生成処理を通じて、検索対象となる画像が有する局所的特徴の数と、クエリ画像が有する局所的特徴の数とが大きく異なる画像が検索結果として選択される可能性を抑えることができる。

［画像ごとのスコアの生成］
画像特徴ベクトル２２が選択されると、画像検索部５２に含まれる画像スコア生成部９０は、検索対象となる画像ごとにスコアを生成する（ステップＳ１０５）。画像スコア生成部９０は並列計算装置１４を中心として実現される。画像スコア生成部９０は、複数の画像のそれぞれについて、当該画像の特徴を示しかつ選択された複数の画像特徴ベクトル２２と、その選択された画像特徴ベクトル２２に対応するクエリ特徴ベクトルとの近さに基づいてスコア要素を計算し、さらにそのスコア要素の合計に基づいて、当該画像の画像スコアを生成する。

画像スコア生成部９０は、以下の式を用いて選択された画像特徴ベクトル２２のそれぞれについて、スコア要素ｓｅを計算する。

ここで、ｄｉｓｔは画像特徴ベクトル２２と、その画像特徴ベクトル２２に対応するクエリ特徴ベクトルとの距離であり、ｌｎは自然対数をｅは自然対数の底を示す。これにより、対応するクエリ特徴ベクトルを有する画像特徴ベクトル２２のスコア要素ｓｅが距離に応じて変化するようになる。次に、画像スコア生成部９０は、画像のそれぞれについて、その画像から抽出されかつ画像特徴ベクトル選択部８９が選択した画像特徴ベクトル２２のスコア要素ｓの合計を用いて、以下の式のように画像スコアｓｉを計算する。

ここで、ｋｎは、その画像から抽出された画像特徴ベクトル２２の数である。これらの式で生成される画像スコアｓｉは、画像のそれぞれについて画像特徴ベクトル２２が選択された頻度だけではなく、クエリ特徴ベクトルのそれぞれと対応する画像特徴ベクトル２２との近さも考慮に入れたスコアとなるため、検索精度をさらに向上させることができる。

図２０は、クエリ特徴ベクトルと画像特徴ベクトル２２との距離のばらつきの一例を示す図である。例えば、本図のように、クエリ特徴ベクトル３２４と、対応して選択される画像特徴ベクトル２２４とが近いものと、クエリ特徴ベクトル３２５と、対応して選択される画像特徴ベクトル２２５とが近いものとがある場合、従来は、同じ重みでスコアを計算していたが、上述の処理により、このような違いを反映したスコアを計算し、局所的な特徴の類似性をより反映した検索を行うことが可能となる。

［画像の選択］
画像スコアが生成されると、画像検索部５２に含まれる検索結果画像選択部９１は、検索結果となる画像を選択する（ステップＳ１０６）。検索結果画像選択部９１は、並列計算装置１４を中心として実現される。検索結果画像選択部９１は、画像スコア生成部９０が計算した画像スコアに基づいて、検索対象となる複数の画像のうち少なくとも１つを検索結果として選択する。具体的には、画像スコアをその値により降順にソートし、その画像スコアが高い画像からいくつかを選択したり、所定の値より画像スコアが高い画像を選択する。

図２１は、画像スコアのソート結果の一例を示す図である。本図に示すように、星マークを１つ含むトルコ国旗をクエリ画像とする場合に、星マークを大量に含むアメリカ星条旗の画像に対する画像スコアが上昇してしまう現象が抑えられている。検索結果画像選択部９１は、画像を選択すると、ウェブサーバ２に選択した画像の情報を出力する。ウェブサーバ２は、クライアント装置３に検索結果の画像を表示させる情報を出力する。

なお、上位代表ベクトル距離計算部８３から画像特徴ベクトル距離計算部８８までの処理はＧＰＵなどの並列計算を行うハードウェアとの親和性が高く、ＧＰＵの並列計算能力をフルに活かすことができる。またそれ以降の処理も、ある程度並列処理が可能であり、ＣＰＵ１１も用いるより高速に処理を行うことができる。よって、ＧＰＵによる処理時間の短縮効果を十分に享受することができる。また、これらの処理のうち一部をＣＰＵ１１に実行させてもよい。

［第２の実施形態］
本発明の第２の実施形態にかかる画像検索システムは、第１の実施形態と異なり、画像特徴クラスタを選択した後に画像特徴ベクトル２２とクエリ特徴ベクトルとの距離を判断しない。この手法はＢｏＦ法に一部類似する検索手法である。以下では、第１の実施形態との相違点を中心に説明する。なお、図１に示す画像検索システムを構成する機器の構成や、画像検索装置１がインデックス生成部５１および画像検索部５２を有する点は第１の実施形態と同様である。

［インデックスの生成］
第１の実施形態と同様に、インデックス生成部５１は、画像特徴ベクトル抽出部６１と、クラスタ生成部６２とを含む。画像特徴ベクトル抽出部６１は、検索対象となる複数の画像のそれぞれから複数の画像特徴ベクトル２２を抽出する。クラスタ生成部６２は、その抽出された画像特徴ベクトル２２を複数の画像特徴クラスタに分類する。また、クラスタ生成部６２は、それらの画像特徴クラスタの代表ベクトルを代表ベクトル格納部１７２に格納し、画像特徴クラスタに属する画像特徴ベクトル２２に関する情報をクラスタ画像特徴量格納部１７１に格納する。画像特徴クラスタへの分類は、第１の実施形態と同様の手法を用いればよい。ただし、クラスタ生成部６２は、クラスタ画像特徴量格納部１７１には、画像特徴ベクトル２２の各要素の代わりに、その画像特徴ベクトル２２のインデックスに相当する情報、より具体的にはその画像特徴ベクトルが抽出された画像の識別情報を格納する。クラスタ画像特徴量格納部１７１、代表ベクトル格納部１７２は、具体的には記憶部１２により構成される。

図２２は、クラスタ画像特徴量格納部１７１に格納されるデータの一例を示す図である。クラスタ画像特徴量格納部１７１には、画像特徴クラスタの識別情報であるクラスタ番号と画像の識別情報である画像番号とを要素とする複数のレコードが格納されている。ここで、１つのレコードは、１つの画像特徴ベクトル２２に対応する。ある画像から抽出された複数の画像特徴ベクトルが同じ画像特徴クラスタに存在する場合、同じクラスタ番号と画像番号とを有するレコードの数はその画像特徴ベクトル２２の数となる。

［画像を検索する処理］
図２３は、第２の実施形態にかかる画像検索部５２の機能構成を示す機能ブロック図である。画像検索部５２は、機能的に、クエリ特徴ベクトル取得部１８１、画像特徴クラスタ選択部１８２、画像特徴ベクトル選択部１８３、画像スコア生成部１８４、および検索結果画像選択部１８５を含む。

図２４は、第２の実施形態にかかる画像検索部５２の処理の概要を示す図である。以下では、図２４が示す処理フローに従い、画像検索部５２に含まれる各機能について説明する。

［クエリ特徴ベクトルの取得］
クエリ特徴ベクトル取得部１８１は、主にＣＰＵ１１、記憶部１２、および並列計算装置１４によって実現される。はじめに、クエリ特徴ベクトル取得部１８１は、クエリ画像から１または複数のクエリ特徴ベクトルを取得する（ステップＳ１１０１）。この処理は、第１の実施形態におけるクエリ特徴ベクトル取得部８２と同様の処理である。

［画像特徴クラスタの選択］
画像特徴クラスタ選択部１８２は、主にＣＰＵ１１、記憶部１２、および並列計算装置１４により実現される。クエリ特徴ベクトルが取得されると、画像特徴クラスタ選択部１８２は、複数のクエリ特徴ベクトルにそれぞれ対応する複数の画像特徴クラスタを選択する（ステップＳ１１０２）。より具体的には、クエリ特徴ベクトルのそれぞれについて、当該クエリ特徴ベクトルに最も近い代表ベクトルを有する画像特徴クラスタを選択する。より詳細な計算方法としては、ＣＰＵ１１を用いて距離計算を行ってもよいし、第１の実施形態に示すように、並列計算装置１４と代表ベクトルの木構造とを用いて画像特徴クラスタを選択してもよい。なお、選択された画像特徴クラスタは、ＢｏＦ法におけるＶｉｓｕａｌ Ｗｏｒｄに相当すると考えてよい。

［画像特徴ベクトルの選択］
画像特徴ベクトル選択部１８３は、ＣＰＵ１１および記憶部１２を中心として実現される。画像特徴ベクトル選択部１８３は、クエリ特徴ベクトルのそれぞれに対して選択された画像特徴クラスタに属する画像特徴ベクトル２２から、当該クエリ特徴ベクトルに対応する画像特徴ベクトル２２を選択する（ステップＳ１１０３）。ここで、画像特徴ベクトル選択部８９は、以下の条件を満たす複数の画像特徴ベクトル２２を選択する。１つの条件は、検索対象となる複数の画像のそれぞれについて、その画像から抽出された複数の画像特徴ベクトル２２のうち、ある１つのクエリ特徴ベクトルに対応して選択された画像特徴ベクトル２２の数が１となることである。もう１つの条件は、いずれかのクエリ特徴ベクトルに対し選択される画像特徴ベクトル２２と、他のクエリ特徴ベクトルに対し選択される画像特徴ベクトル２２とが重複しないことである。画像特徴ベクトル選択部１８３は、クエリ特徴ベクトルのそれぞれについて、上述の条件を満たす全ての画像特徴ベクトル２２をそのクエリ特徴ベクトルに対応する画像特徴ベクトル２２として選択する。

具体的な処理方法としては、例えば、第１の実施形態において図１６で説明した処理のうち、ステップＳ３０１の処理を、クエリ特徴ベクトルに対応して選択された画像特徴クラスタに含まれる全ての画像特徴ベクトル２２を取得するように変更すればよい。なお、本実施形態ではクラスタ画像特徴量格納部１７１には画像特徴ベクトル２２そのものは格納されておらず、距離計算や距離によるソートは行わない。

図２５は、３番目の画像特徴クラスタにおける画像特徴ベクトル２２の分布とクエリ特徴ベクトルによる選択とを説明する図である。図２５は、ある画像特徴クラスタ（ここではクラスタ番号が３である画像特徴クラスタ）における画像ごとの画像特徴ベクトル２２の数を示している。図２５において横軸は画像番号であり、縦軸は画像特徴ベクトル２２の数である。あるクエリ特徴ベクトルにより１度目にクラスタ番号３である画像特徴クラスタが選択された場合、画像番号３，４，５，７，１６の画像から抽出された画像特徴ベクトル２２がそれぞれ１つずつ選択される。また、他のクエリ特徴ベクトルにより２度目にクラスタ番号３の画像特徴クラスタが選択された場合、残っている画像特徴ベクトル２２のうち、画像番号４，１６の画像から抽出された画像特徴ベクトル２２がそれぞれ１つずつ選択される。

［画像ごとのスコアの生成］
画像スコア生成部１８４は、ＣＰＵ１１および記憶部１２を中心として実現される。画像スコア生成部１８４は、複数の画像の少なくとも一部のそれぞれについて、その画像における選択された画像特徴ベクトル２２の出現頻度に基づいて当該画像の画像スコアを生成する（ステップＳ１１０４）。例えば、画像スコア生成部１８４は、画像ごとに、その画像から抽出され、クエリ特徴ベクトルに対応して選択された画像特徴ベクトル２２の数をカウントして画像スコアを生成する。

［画像の選択］
検索結果画像選択部１８５は、ＣＰＵ１１および記憶部１２を中心として実現される。検索結果画像選択部１８５は、検索結果となる画像を選択する（ステップＳ１１０５）。具体的には、検索結果画像選択部１８５は第１の実施形態における検索結果画像選択部９１と同様に画像スコアに基づいて検索対象となる複数の画像のうち少なくとも１つを検索結果として選択する。

上述のように、画像特徴クラスタを選択した後に画像特徴ベクトル２２とクエリ特徴ベクトルとの距離を計算しなくても、クエリ画像から抽出されるクエリ特徴ベクトルと、検索対象となる画像のいずれか１つから抽出された画像特徴ベクトル２２のうち、選択された画像特徴ベクトル２２とを１対１に対応させ、検索対象となる画像が有する局所的特徴の数と、クエリ画像が有する局所的特徴の数とが大きく異なる画像が検索結果として選択される可能性を抑えるという効果を生ずる。

［第３の実施形態］
本発明の第２の実施形態にかかる画像検索システムは、第２の実施形態と同様に、画像特徴クラスタを選択した後に画像特徴ベクトル２２とクエリ特徴ベクトルとの距離を判断しない。本実施形態ではＢｏＦ法で用いられるような既存の全文検索エンジンを用いつつ第２の実施形態と同様の効果を得るようにしたものである。以下では、第２の実施形態との相違点を中心に説明する。なお、図１に示す画像検索システムを構成する機器の構成や、図２や図２３に示す機能構成は第２の実施形態と同様である。

［インデックスの生成］
第３の実施形態では、クラスタ生成部６２は、ＢｏＦ法で一般的に用いられる転置行列をクラスタ画像特徴量格納部１７１に格納する。ＢｏＦ法における転置行列は、画像に対応する列と、Ｖｉｓｕａｌ Ｗｏｒｄに対応する行とからなる行列である。本実施形態では、行列の行を特定する文字列をビジュアルワード識別子と呼ぶ。ここで、ビジュアルワード識別子は、Ｖｉｓｕａｌ Ｗｏｒｄに相当する画像特徴クラスタの識別番号に、その画像特徴クラスタについてある画像に対応する画像特徴ベクトル２２が抽出された順位を示す情報を付加したものである。

図２６は、画像スコアを生成するために用いられる転置行列の一例を示す図である。ハイフンのないビジュアルワード識別子は、画像特徴クラスタのクラスタ番号と同じである。そのビジュアルワードの行とある画像番号の列とによる定まるセルに「１」がある場合には、その画像番号が示す画像から抽出され、その画像特徴クラスタに属する１番目の画像特徴ベクトル２２が存在することを示す。また、ハイフンのあるビジュアルワード識別子については、ハイフンの前の番号は画像特徴クラスタのクラスタ番号を、ハイフンの後の番号は画像における画像特徴ベクトル２２のシーケンシャル番号を示す。例えば、ビジュアルワード識別子が「３−２」の行と、画像番号「４」の列とにより定まるセルに「１」がある場合には、３番目の画像特徴クラスタに、４番目の画像について２番目の画像特徴ベクトル２２が存在していることを示す。この「１」が存在するセルは、画像特徴ベクトル２２に相当する。もちろん、ビジュアルワード識別子の表現にハイフンを用いなくてもよい。ビジュアルワード識別子は、同じクラスタに属しかつ同じ画像から抽出される画像特徴ベクトル２２が識別できればどのような表現でもよい。

また、ビジュアルワード識別子「３−ｍａｎｙ」の「ｍａｎｙ」は、あらかじめ定められたクラスタ内閾値（ここでは３）以降のシーケンシャル番号を示す。ビジュアルワード識別子が「３−ｍａｎｙ」の行と、画像番号「４」の列とにより定まるセルに「１」がある場合には、３番目の画像特徴クラスタに、所定の順位（３番目）以降の画像特徴ベクトル２２が存在することを示す。本実施形態では「３−４」以降のビジュアルワードは存在させない。これは、４番目以降の画像特徴ベクトル２２についての情報を削除することを示す。さらにいえば、ある画像特徴クラスタに属する画像特徴ベクトル２２のうち検索対象となる複数の画像のいずれか１つに対応する画像特徴量の数がそのクラスタ内閾値を超えないことと等価である。クラスタ生成部６２は、ある画像特徴クラスタに属し、かつ検索対象となる複数の画像のいずれか１つに対応する画像特徴ベクトル２２のうちクラスタ内閾値を超えるものを画像特徴クラスタから削除し、その結果をクラスタ画像特徴量格納部１７１に格納している。

［画像を検索する処理］
図２７は、第３の実施形態にかかる画像検索部５２の処理の概要を示す図である。以下では、図２７が示す処理フローに従い、主に第２の実施形態との相違点について説明する。

はじめに、クエリ特徴ベクトル取得部１８１は、クエリ画像から１または複数のクエリ特徴ベクトルを取得する（ステップＳ２１０１）。次に、画像特徴クラスタ選択部１８２は、複数のクエリ特徴ベクトルにそれぞれ対応する複数の画像特徴クラスタを選択する（ステップＳ２１０２）。これらの処理は第２の実施形態と同様であるので説明を省略する。

次に、画像特徴ベクトル選択部１８３は、選択された画像特徴クラスタのクラスタ番号とその画像特徴クラスタが選択された順位とに基づいて、ビジュアルワード識別子を生成する（ステップＳ２１０３）。この作成ルールは、転置行列におけるビジュアルワード識別子の生成ルールと同様である。具体的には、画像特徴クラスタが選択された順位が１である場合には画像特徴クラスタのクラスタ番号をビジュアルワード識別子にし、その順位が２から（特徴閾値−１）までは、クラスタ番号にハイフンと順位を付加したものをビジュアルワード識別子にし、その順位が特徴閾値である場合には、クラスタ番号に「−ｍａｎｙ」を付加したものをビジュアルワード識別子とする。

次に、画像特徴ベクトル選択部１８３は、転置行列を用いて、ビジュアルワード識別子に対応する画像特徴ベクトル２２を選択する（ステップＳ２１０４）。画像特徴ベクトル２２の選択は、具体的には、「１」のあるセルと、そのセルの画像番号とを取得することにより行われる。また、画像特徴ベクトル選択部１８３は、選択された画像番号およびセルの数値を用いて、画像のスコアを生成する（ステップＳ２１０５）。そして、そのスコアに基づいて、検索結果となる画像を選択する（ステップＳ２１０６）。

ステップＳ２１０４からステップＳ２１０６の処理は、公知の全文検索エンジンにより処理してよい。この処理エンジンの例としては、「Ｓｏｌｒ」がある。上述の転置行列の作成により、あるクエリ特徴ベクトルに対しある画像から選択されるセルの値が１に限定される。これにより、クエリ画像から抽出されるクエリ特徴ベクトルと、ある画像について選択される画像特徴ベクトル２２とを１対１に対応させることができる。よって、検索対象となる画像が有する局所的特徴の数と、クエリ画像が有する局所的特徴の数とが大きく異なる画像が検索結果として選択される可能性を抑えるという効果を生ずる。

１ 画像検索装置、２ ウェブサーバ、３ クライアント装置、１１ ＣＰＵ、１２ 記憶部、１３ 通信部、１４ 並列計算装置、１５ バス、２２，２２１，２２２，２２３，２２４，２２５ 画像特徴ベクトル、４０ 並列実行部、４１ プロセッサ、４２ 命令ユニット、４３ 高速メモリ、４５ 装置内メモリ、５１ インデックス生成部、５２ 画像検索部、６１ 画像特徴ベクトル抽出部、６２ クラスタ生成部、７１ クラスタベクトル格納部、７２ 木構造代表ベクトル格納部、８１ 代表ベクトル転送部、８２，１８１ クエリ特徴ベクトル取得部、８３ 上位代表ベクトル距離計算部、８４ 代表クラスタ選択部、８５ 代表特徴ベクトル距離計算部、８６，１８２ 画像特徴クラスタ選択部、８７ 画像特徴ベクトル転送部、８８ 画像特徴ベクトル距離計算部、８９，１８３ 画像特徴ベクトル選択部、９０，１８４ 画像スコア生成部、９１，１８５ 検索結果画像選択部、１７１ クラスタ画像特徴量格納部、１７２ 代表ベクトル格納部、２４１ 代表ベクトル、３２１，３２２，３２４，３２５ クエリ特徴ベクトル。

Claims (9)

1. クエリとなる画像の局所的な特徴をそれぞれ示す複数のクエリ特徴量を取得するクエリ特徴量取得手段と、
   前記複数のクエリ特徴量のそれぞれについて、検索対象となる複数の画像毎に予め記憶手段に記憶され、各画像の局所的な特徴を示す複数の画像特徴量から画像特徴量を選択する画像特徴量選択手段と、
   前記複数のクエリ特徴量について選択された画像特徴量に基づいて、前記検索対象となる複数の画像について各々前記クエリとなる画像に類似する度合いを示すスコアを生成するスコア生成手段と、
   前記画像について生成されたスコアに基づいて、前記検索対象となる複数の画像から少なくとも１つの画像を選択する画像選択手段と、を含み、
   前記画像特徴量選択手段は、前記複数のクエリ特徴量のそれぞれについて、前記検索対象となる画像につき、当該画像の前記複数の画像特徴量のうち当該クエリ特徴量と異なるクエリ特徴量について選択されていない画像特徴量から多くとも１つの画像特徴量を選択する、
   ことを特徴とする画像検索装置。
2. 前記画像特徴量選択手段は、前記複数のクエリ特徴量のそれぞれについて、前記検索対象となる画像につき、当該画像の前記複数の画像特徴量のうち当該クエリ特徴量と異なるクエリ特徴量について選択されていない画像特徴量から多くとも１つの任意の画像特徴量を選択する、
   ことを特徴とする請求項１に記載の画像検索装置。
3. 前記検索対象となる複数の画像の特徴を示す複数の画像特徴量が分類される複数のクラスタのうちから、前記複数のクエリ特徴量のそれぞれに対応するクラスタを選択するクラスタ選択手段、をさらに含み、
   前記画像特徴量選択手段は、前記複数のクエリ特徴量のそれぞれについて、当該クエリ特徴量に対応するクラスタに分類された複数の画像特徴量から画像特徴量を選択する、
   ことを特徴とする請求項１または２に記載の画像検索装置。
4. 前記クラスタ選択手段は、前記複数のクラスタをそれぞれ代表する複数の代表特徴量と前記クエリ特徴量との距離に基づいて前記クエリ特徴量に対応するクラスタを選択する、
   ことを特徴とする請求項３に記載の画像検索装置。
5. 前記画像特徴量選択手段は、前記複数のクエリ特徴量のそれぞれについて、当該クエリ特徴量に対応するクラスタに属する複数の画像特徴量から、選択される画像特徴量の数が前記検索対象となる画像につき多くとも１つとなり、かつ、選択される画像特徴量が当該クエリ特徴量と異なるクエリ特徴量について選択されない条件を満たす画像特徴量の全てを選択する、
   ことを特徴とする請求項３または４に記載の画像検索装置。
6. 前記検索対象となる画像のそれぞれから画像特徴量を抽出する画像特徴量抽出手段と、
   前記抽出された画像特徴量の少なくとも一部が分類される前記複数のクラスタを生成するクラスタ生成手段と、をさらに含み、
   前記クラスタ生成手段は、あるクラスタに属する画像特徴量のうち前記検索対象となる複数の画像のいずれか１つに対応する画像特徴量の数が所定の値を超えないように前記複数のクラスタを生成する、
   ことを特徴とする請求項３から５のいずれかに記載の画像検索装置。
7. クエリとなる画像の局所的な特徴をそれぞれ示す複数のクエリ特徴量を取得するクエリ特徴量取得手段、
   前記複数のクエリ特徴量のそれぞれについて、検索対象となる複数の画像毎に予め記憶手段に記憶され、各画像の局所的な特徴を示す複数の画像特徴量から画像特徴量を選択する画像特徴量選択手段、
   前記複数のクエリ特徴量について選択された画像特徴量に基づいて、前記検索対象となる複数の画像について各々前記クエリとなる画像に類似する度合いを示すスコアを生成するスコア生成手段、および、
   前記画像について生成されたスコアに基づいて、前記検索対象となる複数の画像から少なくとも１つの画像を選択する画像選択手段、
   としてコンピュータを機能させ、
   前記画像特徴量選択手段は、前記複数のクエリ特徴量のそれぞれについて、前記検索対象となる画像につき、当該画像の前記複数の画像特徴量のうち当該クエリ特徴量と異なるクエリ特徴量について選択されていない画像特徴量から多くとも１つの画像特徴量を選択する、
   ことを特徴とするプログラム。
8. クエリ特徴量取得手段がクエリとなる画像の局所的な特徴をそれぞれ示す複数のクエリ特徴量を取得するステップと、
   画像特徴量選択手段が前記複数のクエリ特徴量のそれぞれについて、検索対象となる複数の画像毎に予め記憶手段に記憶され、各画像の局所的な特徴を示す複数の画像特徴量から画像特徴量を選択するステップと、
   スコア生成手段が前記複数のクエリ特徴量について選択された画像特徴量に基づいて、前記検索対象となる複数の画像について各々前記クエリとなる画像に類似する度合いを示すスコアを生成するステップと、
   画像選択手段が前記画像について生成されたスコアに基づいて、前記検索対象となる複数の画像から少なくとも１つの画像を選択するステップと、を含み、
   前記画像特徴量を選択するステップでは、前記複数のクエリ特徴量のそれぞれについて、前記検索対象となる画像につき、当該画像の前記複数の画像特徴量のうち当該クエリ特徴量と異なるクエリ特徴量について選択されていない画像特徴量から多くとも１つの画像特徴量を選択する、
   ことを特徴とする画像検索方法。
9. クエリとなる画像の局所的な特徴をそれぞれ示す複数のクエリ特徴量を取得するクエリ特徴量取得手段、
   前記複数のクエリ特徴量のそれぞれについて、検索対象となる複数の画像毎に予め記憶手段に記憶され、各画像の局所的な特徴を示す複数の画像特徴量から画像特徴量を選択する画像特徴量選択手段、
   前記複数のクエリ特徴量について選択された画像特徴量に基づいて、前記検索対象となる複数の画像について各々前記クエリとなる画像に類似する度合いを示すスコアを生成するスコア生成手段、および、
   前記画像について生成されたスコアに基づいて、前記検索対象となる複数の画像から少なくとも１つの画像を選択する画像選択手段、
   としてコンピュータを機能させるためのプログラムであって、
   前記画像特徴量選択手段は、前記複数のクエリ特徴量のそれぞれについて、前記検索対象となる画像につき、当該画像の前記複数の画像特徴量のうち当該クエリ特徴量と異なるクエリ特徴量について選択されていない画像特徴量から多くとも１つの画像特徴量を選択する、
   ことを特徴とするプログラムを格納するコンピュータ読取り可能な情報記憶媒体。

Images