(57)【特許請求の範囲】
【請求項１】
高次元の登録ベクトルの集合から、クエリベクトルに類似したベクトルを検索する検索装置であって、
前記登録ベクトルｆを量子化するために、代表識別値ｎ（＝１〜Ｎ）と代表ベクトルｆｎとを対応付けたコードブックを記憶するコードブック記憶手段と、
前記登録ベクトルｆを、前記コードブックを用いて、代表識別値ｎに量子化するベクトル量子化手段と、
前記登録ベクトルｆから代表ベクトルｆｎを引いた残差ベクトルｆｒを導出する残差ベクトル導出手段と、
前記残差ベクトルをＴ個の残差部分ベクトルに分割する残差ベクトル分割手段と、
各残差部分ベクトルｆｒｔを更に量子化するために、残差識別値ｌ（＝１〜Ｌ）と残差部分代表ベクトルｆｌとを対応付けた残差コードブックをＭ×Ｔ個記憶すると共に、前記代表識別値ｎに対応付けられた登録ベクトルｆの残差部分ベクトルｆｒｔが、前記Ｍ×Ｔ個の残差コードブックのどれで量子化すべきかを示す残差テーブルＴ[n][t]を記憶する残差コードブック記憶手段と、
前記残差部分ベクトルｆｒｔを、Ｔ[n][t]番目の前記残差コードブックで量子化する残差部分ベクトル量子化手段と、
前記登録ベクトルｆの代表識別値ｎ毎に、複数の残差部分ベクトルｆｒｔの残差識別値ｌｔ（１≦ｔ≦Ｔ）の集合と、登録ベクトルｆに関する付加情報とを、各登録ベクトルｆの登録情報として登録した転置インデックスを生成する転置インデックス生成手段と、
前記転置インデックスを、登録ベクトルの集合として記憶する転置インデックス記憶手段と
を有することを特徴とする検索装置。
【請求項２】
前記転置インデックス記憶手段を用いて、クエリベクトルに類似したベクトルを検索するために、
前記ベクトル量子化手段は、前記クエリベクトルｆを、前記コードブックを用いて、代表識別値ｎに量子化し、
前記残差ベクトル導出手段は、前記クエリベクトルｆから代表ベクトルｆｎを引いたクエリ残差ベクトルｆｒを導出し、
前記残差ベクトル分割手段は、前記クエリ残差ベクトルをＴ個のクエリ残差部分ベクトルに分割する
と共に、
前記クエリ残差部分ベクトルｆｒｔと、前記残差テーブルＴ[n][t]により指定される残差コードブックの各残差代表ベクトルｆｔ，ｌ（１≦ｌ≦Ｌ）との距離を算出しテーブルＤ[t][l]に保持する残差ベクトル距離算出手段と、
前記登録ベクトルの登録情報である残差識別値ｌｔ（１≦ｔ≦Ｔ）を基に、前記テーブルＤ[t][l]を参照することで、クエリベクトルと登録ベクトルの近似距離を、距離の和ｄ（＝Σt=1TＤ[t][lｔ]）として算出する登録ベクトル距離算出手段と、
前記距離の和ｄが、所定閾値以下となる登録ベクトルを、検索結果として出力する検索判定手段と
を有することを特徴とする請求項１に記載の検索装置。
【請求項３】
学習ベクトルの集合を用いて、前記コードブック記憶手段に記憶すべきコードブックを生成するコードブック生成手段と、
前記残差コードブック記憶手段に記憶すべき残差コードブックを生成する残差コードブック生成手段と
を更に有し、
前記コードブック生成手段は、
前記学習ベクトルの集合を、Ｎ個のクラスタにクラスタリングする第１の機能と、
前記クラスタ毎に、代表ベクトルを導出する第２の機能と、
各代表ベクトルに、一意の代表識別値ｎ（＝１〜Ｎ）を割り当てたコードブックを生成する第３の機能と
を実行するものであり、
前記残差コードブック生成手段は、
代表ベクトルｆｎと、当該代表ベクトルｆｎに属する学習ベクトルｆとの間の残差ベクトルｆｒ（＝ｆ−ｆｎ）を導出することによってＮ個の残差クラスタを作成する第１の機能と、
前記残差ベクトルｆｒをＴ個の残差部分ベクトルに分割する第２の機能と、
前記残差部分ベクトル毎に、以下の第３から第８の機能をそれぞれ実行するものであって、
Ｎ個の残差クラスタから任意のＭ個の残差クラスタを選択する第３の機能と、
Ｍ個の各残差クラスタについて、各残差クラスタに所属する残差部分ベクトルを更にＬ個のクラスタにクラスタリングする第４の機能と、
Ｍ個の残差クラスタからそれぞれ作成されたＬ個のクラスタの代表ベクトル集合から、Ｌ個の要素を持つ残差コードブックをＭ個生成する第５の機能と、
Ｎ個の残差クラスタについて、各残差クラスタに属する残差部分ベクトルの全てを、Ｍ個の残差コードブック各々を用いて量子化した場合の量子化誤差の合計値を算出する第６の機能と、
前記量子化誤差の合計値が最小となる残差コードブックに、当該残差クラスタを割り当てる第７の機能と、
Ｍ個の残差コードブックについて、各残差コードブックに割り当てられた残差クラスタに含まれる全ての残差部分ベクトルを用いて、更にＬ個のクラスタにクラスタリングし、そのＬ個の新たな代表ベクトルによって残差コードブックを更新する第８の機能と
を実行することを特徴とする請求項１又は２に記載の検索装置。
【請求項４】
前記残差コードブック生成手段は、第６から第８の機能を、所定回数、又は、先の量子化誤差の合計値と後の量子化誤差の合計値との差が所定閾値以下となるまで、繰り返すことを特徴とする請求項３に記載の検索装置。
【請求項５】
前記ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであり、
前記登録ベクトルの付加情報は、画像識別子(IDentifier)、局所特徴領域のスケール、局所特徴領域の角度のいずれか１つを含むことを特徴とする請求項１から４のいずれか１項に記載の検索装置。
【請求項６】
高次元の登録ベクトルの集合から、クエリベクトルに類似したベクトルを検索する装置に搭載されたコンピュータを機能させる検索プログラムであって、
前記登録ベクトルｆを量子化するために、代表識別値ｎ（＝１〜Ｎ）と代表ベクトルｆｎとを対応付けたコードブックを記憶するコードブック記憶手段と、
前記登録ベクトルｆを、前記コードブックを用いて、代表識別値ｎに量子化するベクトル量子化手段と、
前記登録ベクトルｆから代表ベクトルｆｎを引いた残差ベクトルｆｒを導出する残差ベクトル導出手段と、
前記残差ベクトルをＴ個の残差部分ベクトルに分割する残差ベクトル分割手段と、
各残差部分ベクトルｆｒｔを更に量子化するために、残差識別値ｌ（＝１〜Ｌ）と残差部分代表ベクトルｆｌとを対応付けた残差コードブックをＭ×Ｔ個記憶すると共に、前記代表識別値ｎに対応付けられた登録ベクトルｆの残差部分ベクトルｆｒｔが、前記Ｍ×Ｔ個の残差コードブックのどれで量子化すべきかを示す残差テーブルＴ[n][t]を記憶する残差コードブック記憶手段と、
前記残差部分ベクトルｆｒｔを、Ｔ[n][t]番目の前記残差コードブックで量子化する残差部分ベクトル量子化手段と、
前記登録ベクトルｆの代表識別値ｎ毎に、複数の残差部分ベクトルｆｒｔの残差識別値ｌｔ（１≦ｔ≦Ｔ）の集合と、登録ベクトルｆに関する付加情報とを、各登録ベクトルｆの登録情報として登録した転置インデックスを生成する転置インデックス生成手段と、
前記転置インデックスを、登録ベクトルの集合として記憶する転置インデックス記憶手段と
してコンピュータを機能させることを特徴とする検索プログラム。
【請求項７】
前記転置インデックス記憶手段を用いて、クエリベクトルに類似したベクトルを検索するために、
前記ベクトル量子化手段は、前記クエリベクトルｆを、前記コードブックを用いて、代表識別値ｎに量子化し、
前記残差ベクトル導出手段は、前記クエリベクトルｆから代表ベクトルｆｎを引いたクエリ残差ベクトルｆｒを導出し、
前記残差ベクトル分割手段は、前記クエリ残差ベクトルをＴ個のクエリ残差部分ベクトルに分割する
と共に、
前記クエリ残差部分ベクトルｆｒｔと、前記残差テーブルＴ[n][t]により指定される残差コードブックの各残差代表ベクトルｆｔ，ｌ（１≦ｌ≦Ｌ）との距離を算出しテーブルＤ[t][l]に保持する残差ベクトル距離算出手段と、
前記登録ベクトルの登録情報である残差識別値ｌｔ（１≦ｔ≦Ｔ）を基に、前記テーブルＤ[t][l]を参照することで、クエリベクトルと登録ベクトルの近似距離を、距離の和ｄ（＝Σt=1TＤ[t][lｔ]）として算出する登録ベクトル距離算出手段と、
前記距離の和ｄが、所定閾値以下となる登録ベクトルを、検索結果として出力する検索判定手段と
してコンピュータを更に機能させることを特徴とする請求項６に記載の検索プログラム。
【請求項８】
学習ベクトルの集合を用いて、前記コードブック記憶手段に記憶すべきコードブックを生成するコードブック生成手段と、
前記残差コードブック記憶手段に記憶すべき残差コードブックを生成する残差コードブック生成手段と
を更に有し、
前記コードブック生成手段は、
前記学習ベクトルの集合を、Ｎ個のクラスタにクラスタリングする第１の機能と、
前記クラスタ毎に、代表ベクトルを導出する第２の機能と、
各代表ベクトルに、一意の代表識別値ｎ（＝１〜Ｎ）を割り当てたコードブックを生成する第３の機能と
を実行するものであり、
前記残差コードブック生成手段は、
代表ベクトルｆｎと、当該代表ベクトルｆｎに属する学習ベクトルｆとの間の残差ベクトルｆｒ（＝ｆ−ｆｎ）を導出することによってＮ個の残差クラスタを作成する第１の機能と、
前記残差ベクトルｆｒをＴ個の残差部分ベクトルに分割する第２の機能と、
前記残差部分ベクトル毎に、以下の第３から第８の機能をそれぞれ実行するものであって、
Ｎ個の残差クラスタから任意のＭ個の残差クラスタを選択する第３の機能と、
Ｍ個の各残差クラスタについて、各残差クラスタに所属する残差部分ベクトルを更にＬ個のクラスタにクラスタリングする第４の機能と、
Ｍ個の残差クラスタからそれぞれ作成されたＬ個のクラスタの代表ベクトル集合から、Ｌ個の要素を持つ残差コードブックをＭ個生成する第５の機能と、
Ｎ個の残差クラスタについて、各残差クラスタに属する残差部分ベクトルの全てを、Ｍ個の残差コードブック各々を用いて量子化した場合の量子化誤差の合計値を算出する第６の機能と、
前記量子化誤差の合計値が最小となる残差コードブックに、当該残差クラスタを割り当てる第７の機能と、
Ｍ個の残差コードブックについて、各残差コードブックに割り当てられた残差クラスタに含まれる全ての残差部分ベクトルを用いて、更にＬ個のクラスタにクラスタリングし、そのＬ個の新たな代表ベクトルによって残差コードブックを更新する第８の機能と
してコンピュータを更に機能させることを特徴とする請求項６又は７に記載の検索プログラム。
【請求項９】
前記残差コードブック生成手段は、第４から第６の機能を、所定回数、又は、先の量子化誤差の合計値と後の量子化誤差の合計値との差が所定閾値以下となるまで、繰り返すようにコンピュータを更に機能させることを特徴とする請求項８に記載の検索プログラム。
【請求項１０】
前記ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであり、
前記登録ベクトルの付加情報は、画像識別子(IDentifier)、局所特徴領域のスケール、局所特徴領域の角度のいずれか１つを含むようにコンピュータを機能させることを特徴とする請求項６から９のいずれか１項に記載の検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索用データベースに登録された高次元の特徴ベクトルの集合から、クエリ特徴ベクトル（検索キー）に類似した特徴ベクトルを検索する最近傍探索技術に関する。
【背景技術】
【０００２】
最近傍検索技術として、木構造を用いた、R-tree(Rectangle-tree：矩形木)やANN(Approximate Nearest Neighbor)がある。R-treeは、階層的に入れ子になった最小外接矩形により空間を分割するものであって、主に低次元データ空間に対するインデックス化に用いられる。例えば、所定範囲内に存在するベクトルを検索することに適する。また、ANNは、所要程度の検索誤りを許容（近似最近傍検索）ことによって、検索を高速化することができる。
【０００３】
更に、空間における特徴ベクトルの密度に応じてインデックスを生成する技術もある（例えば特許文献１参照）。この技術によれば、R-treeよりも高速に検索することができるが、特徴ベクトルが高次元になるほど、ほぼ全検索と同等の速度になるという問題がある（例えば「次元の呪い」と称される）。即ち、特徴ベクトルが高次元になるほど、最近傍探索の効率が重要となる。
【０００４】
これに対し、高次元の特徴ベクトルに対する検索技術として、ハッシュでデータを構造化（インデキシング）したLSH(Locality Sensitive Hashing)がある。LSHもANNと同様に検索誤りを許容した近似最近傍探索技術である。LSHによれば、類似するデータ同士のハッシュ値は一致し、非類似のデータ同士のハッシュ値は異なる可能性が高くなるように、ハッシュ値を出力するハッシュ関数が用いられる。尚、LSHについて、各バケットに登録される特徴ベクトルの数をなるべく均一にすることで、効率的に検索する技術も提案されている（例えば特許文献２参照）。
【０００５】
更に、ランダムに生成した木構造(kd-tree)のインデックスを複数利用することによって、検索の高精度化を実現する技術もある（例えば非特許文献１参照）。これは、高次元ベクトルを構成する各次元のうち分散の大きな次元を順に決定的に分割するkd-treeに対して、分割する次元や閾値に自由度を持たせたkd-treeを利用している。しかしながら、このような技術についても、特徴ベクトルそのものを登録して、クエリベクトルとの距離計算を行う必要がある。そのために、メモリ効率が悪く、登録ベクトルが高次元且つ大量にある場合には、メモリ上で動作することができないという問題がある。
【０００６】
これに対し、インデックスに、特徴ベクトルそのものを登録するのではなく、最初に、特徴ベクトルを荒く量子化し、その残差ベクトルを更に量子化し、その量子化されたコードを転置インデックスとして登録することによってメモリ使用量を削減する技術がある（例えば非特許文献２参照）。この技術によれば、検索が高速化されると共に、メモリ効率も向上する。尚、この技術は、LSHや非特許文献１に記載された技術と比較して、検索精度とメモリ使用量とのトレードオフに優れる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００２−１６３２７２号公報
【特許文献２】特開２００９−０２０７６９号公報
【非特許文献】
【０００８】
【非特許文献１】Marius Muja andDavid G. Lowe、「Fast Approximate Nearest Neighbors with Automatic AlgorithmConfiguration」、IEEE International Conference on Computer Vision、Theory andApplications (VISAPP'09)、2009.
【非特許文献２】Herve Jegou, Matthijs Douze, Cordelia Schmid、「ProductQuantization for Nearest Neighbor Search」、IEEE Transactions on Pattern Analysisand Machine Intelligence、25 Feb. 2010.
【非特許文献３】D. G. Lowe, 「Distinctive Image Features fromScale-Invariant Keypoints」、International Journal of Computer Vision、vol. 60,no. 2, pp. 91-110, 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、非特許文献２に記載された技術によれば、残差ベクトルを単一のコードブックで量子化しているために、近似最近傍検索の精度が悪くなるという問題があった。これは、最初に荒く量子化した際に、残差ベクトルの分布が、クラスタ毎に大きく異なるためである。一方で、この残差ベクトルのコードブックを、クラスタ毎に生成してしまうと、コードブックの情報量（メモリ量）が非常に膨大となってしまう。
【００１０】
そこで、本発明は、検索精度とメモリ量とのトレードオフを考慮して、高次元の特徴ベクトルの集合から、クエリ特徴ベクトルに類似した特徴ベクトルを検索することができる検索装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明によれば、高次元の登録ベクトルの集合から、クエリベクトルに類似したベクトルを検索する検索装置であって、
登録ベクトルｆを量子化するために、代表識別値ｎ（＝１〜Ｎ）と代表ベクトルｆｎとを対応付けたコードブックを記憶するコードブック記憶手段と、
登録ベクトルｆを、コードブックを用いて、代表識別値ｎに量子化するベクトル量子化手段と、
登録ベクトルｆから代表ベクトルｆｎを引いた残差ベクトルｆｒを導出する残差ベクトル導出手段と、
残差ベクトルをＴ個の残差部分ベクトルに分割する残差ベクトル分割手段と、
各残差部分ベクトルｆｒｔを更に量子化するために、残差識別値ｌ（＝１〜Ｌ）と残差部分代表ベクトルｆｌとを対応付けた残差コードブックをＭ×Ｔ個記憶すると共に、代表識別値ｎに対応付けられた登録ベクトルｆの残差部分ベクトルｆｒｔが、Ｍ×Ｔ個の残差コードブックのどれで量子化すべきかを示す残差テーブルＴ[n][t]を記憶する残差コードブック記憶手段と、
残差部分ベクトルｆｒｔを、Ｔ[n][t]番目の残差コードブックで量子化する残差部分ベクトル量子化手段と、
登録ベクトルｆの代表識別値ｎ毎に、複数の残差部分ベクトルｆｒｔの残差識別値ｌｔ（１≦ｔ≦Ｔ）の集合と、登録ベクトルｆに関する付加情報とを、各登録ベクトルｆの登録情報として登録した転置インデックスを生成する転置インデックス生成手段と、
転置インデックスを、登録ベクトルの集合として記憶する転置インデックス記憶手段と
を有することを特徴とする。
【００１２】
本発明の検索装置における他の実施形態によれば、転置インデックス記憶手段を用いて、クエリベクトルに類似したベクトルを検索するために、
ベクトル量子化手段は、クエリベクトルｆを、コードブックを用いて、代表識別値ｎに量子化し、
残差ベクトル導出手段は、クエリベクトルｆから代表ベクトルｆｎを引いたクエリ残差ベクトルｆｒを導出し、
残差ベクトル分割手段は、クエリ残差ベクトルをＴ個のクエリ残差部分ベクトルに分割する
と共に、
クエリ残差部分ベクトルｆｒｔと、残差テーブルＴ[n][t]により指定される残差コードブックの各残差代表ベクトルｆｔ，ｌ（１≦ｌ≦Ｌ）との距離を算出しテーブルＤ[t][l]に保持する残差ベクトル距離算出手段と、
登録ベクトルの登録情報である残差識別値ｌｔ（１≦ｔ≦Ｔ）を基に、テーブルＤ[t][l]を参照することで、クエリベクトルと登録ベクトルの近似距離を、距離の和ｄ（＝Σt=1TＤ[t][lｔ]）として算出する登録ベクトル距離算出手段と、
距離の和ｄが、所定閾値以下となる登録ベクトルを、検索結果として出力する検索判定手段と
を有することも好ましい。
【００１３】
本発明の検索装置における他の実施形態によれば、
学習ベクトルの集合を用いて、コードブック記憶手段に記憶すべきコードブックを生成するコードブック生成手段と、
残差コードブック記憶手段に記憶すべき残差コードブックを生成する残差コードブック生成手段と
を更に有し、
コードブック生成手段は、
学習ベクトルの集合を、Ｎ個のクラスタにクラスタリングする第１の機能と、
クラスタ毎に、代表ベクトルを導出する第２の機能と、
各代表ベクトルに、一意の代表識別値ｎ（＝１〜Ｎ）を割り当てたコードブックを生成する第３の機能と
を実行するものであり、
残差コードブック生成手段は、
代表ベクトルｆｎと、当該代表ベクトルｆｎに属する学習ベクトルｆとの間の残差ベクトルｆｒ（＝ｆ−ｆｎ）を導出することによってＮ個の残差クラスタを作成する第１の機能と、
残差ベクトルｆｒをＴ個の残差部分ベクトルに分割する第２の機能と、
残差部分ベクトル毎に、以下の第３から第８の機能をそれぞれ実行するものであって、
Ｎ個の残差クラスタから任意のＭ個の残差クラスタを選択する第３の機能と、
Ｍ個の各残差クラスタについて、各残差クラスタに所属する残差部分ベクトルを更にＬ個のクラスタにクラスタリングする第４の機能と、
Ｍ個の残差クラスタからそれぞれ作成されたＬ個のクラスタの代表ベクトル集合から、Ｌ個の要素を持つ残差コードブックをＭ個生成する第５の機能と、
Ｎ個の残差クラスタについて、各残差クラスタに属する残差部分ベクトルの全てを、Ｍ個の残差コードブック各々を用いて量子化した場合の量子化誤差の合計値を算出する第６の機能と、
量子化誤差の合計値が最小となる残差コードブックに、当該残差クラスタを割り当てる第７の機能と、
Ｍ個の残差コードブックについて、各残差コードブックに割り当てられた残差クラスタに含まれる全ての残差部分ベクトルを用いて、更にＬ個のクラスタにクラスタリングし、そのＬ個の新たな代表ベクトルによって残差コードブックを更新する第８の機能と
を実行することも好ましい。
【００１４】
本発明の検索装置における他の実施形態によれば、残差コードブック生成手段は、第６から第８の機能を、所定回数、又は、先の量子化誤差の合計値と後の量子化誤差の合計値との差が所定閾値以下となるまで、繰り返すことも好ましい。
【００１５】
本発明の検索装置における他の実施形態によれば、
ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであり、
登録ベクトルの付加情報は、画像識別子(IDentifier)、局所特徴領域のスケール、局所特徴領域の角度のいずれか１つを含むことも好ましい。
【００１６】
本発明によれば、高次元の登録ベクトルの集合から、クエリベクトルに類似したベクトルを検索する装置に搭載されたコンピュータを機能させる検索プログラムであって、
登録ベクトルｆを量子化するために、代表識別値ｎ（＝１〜Ｎ）と代表ベクトルｆｎとを対応付けたコードブックを記憶するコードブック記憶手段と、
登録ベクトルｆを、コードブックを用いて、代表識別値ｎに量子化するベクトル量子化手段と、
登録ベクトルｆから代表ベクトルｆｎを引いた残差ベクトルｆｒを導出する残差ベクトル導出手段と、
残差ベクトルをＴ個の残差部分ベクトルに分割する残差ベクトル分割手段と、
各残差部分ベクトルｆｒｔを更に量子化するために、残差識別値ｌ（＝１〜Ｌ）と残差部分代表ベクトルｆｌとを対応付けた残差コードブックをＭ×Ｔ個記憶すると共に、代表識別値ｎに対応付けられた登録ベクトルｆの残差部分ベクトルｆｒｔが、Ｍ×Ｔ個の残差コードブックのどれで量子化すべきかを示す残差テーブルＴ[n][t]を記憶する残差コードブック記憶手段と、
残差部分ベクトルｆｒｔを、Ｔ[n][t]番目の残差コードブックで量子化する残差部分ベクトル量子化手段と、
登録ベクトルｆの代表識別値ｎ毎に、複数の残差部分ベクトルｆｒｔの残差識別値ｌｔ（１≦ｔ≦Ｔ）の集合と、登録ベクトルｆに関する付加情報とを、各登録ベクトルｆの登録情報として登録した転置インデックスを生成する転置インデックス生成手段と、
転置インデックスを、登録ベクトルの集合として記憶する転置インデックス記憶手段と
してコンピュータを機能させることを特徴とする。
【００１７】
本発明の検索プログラムにおける他の実施形態によれば、転置インデックス記憶手段を用いて、クエリベクトルに類似したベクトルを検索するために、
ベクトル量子化手段は、クエリベクトルｆを、コードブックを用いて、代表識別値ｎに量子化し、
残差ベクトル導出手段は、クエリベクトルｆから代表ベクトルｆｎを引いたクエリ残差ベクトルｆｒを導出し、
残差ベクトル分割手段は、クエリ残差ベクトルをＴ個のクエリ残差部分ベクトルに分割する
と共に、
クエリ残差部分ベクトルｆｒｔと、残差テーブルＴ[n][t]により指定される残差コードブックの各残差代表ベクトルｆｔ，ｌ（１≦ｌ≦Ｌ）との距離を算出しテーブルＤ[t][l]に保持する残差ベクトル距離算出手段と、
登録ベクトルの登録情報である残差識別値ｌｔ（１≦ｔ≦Ｔ）を基に、テーブルＤ[t][l]を参照することで、クエリベクトルと登録ベクトルの近似距離を、距離の和ｄ（＝Σt=1TＤ[t][lｔ]）として算出する登録ベクトル距離算出手段と、
距離の和ｄが、所定閾値以下となる登録ベクトルを、検索結果として出力する検索判定手段と
してコンピュータを更に機能させることも好ましい。
【００１８】
本発明の検索プログラムにおける他の実施形態によれば、
学習ベクトルの集合を用いて、コードブック記憶手段に記憶すべきコードブックを生成するコードブック生成手段と、
残差コードブック記憶手段に記憶すべき残差コードブックを生成する残差コードブック生成手段と
を更に有し、
コードブック生成手段は、
学習ベクトルの集合を、Ｎ個のクラスタにクラスタリングする第１の機能と、
クラスタ毎に、代表ベクトルを導出する第２の機能と、
各代表ベクトルに、一意の代表識別値ｎ（＝１〜Ｎ）を割り当てたコードブックを生成する第３の機能と
を実行するものであり、
残差コードブック生成手段は、
代表ベクトルｆｎと、当該代表ベクトルｆｎに属する学習ベクトルｆとの間の残差ベクトルｆｒ（＝ｆ−ｆｎ）を導出することによってＮ個の残差クラスタを作成する第１の機能と、
残差ベクトルｆｒをＴ個の残差部分ベクトルに分割する第２の機能と、
残差部分ベクトル毎に、以下の第３から第８の機能をそれぞれ実行するものであって、
Ｎ個の残差クラスタから任意のＭ個の残差クラスタを選択する第３の機能と、
Ｍ個の各残差クラスタについて、各残差クラスタに所属する残差部分ベクトルを更にＬ個のクラスタにクラスタリングする第４の機能と、
Ｍ個の残差クラスタからそれぞれ作成されたＬ個のクラスタの代表ベクトル集合から、Ｌ個の要素を持つ残差コードブックをＭ個生成する第５の機能と、
Ｎ個の残差クラスタについて、各残差クラスタに属する残差部分ベクトルの全てを、Ｍ個の残差コードブック各々を用いて量子化した場合の量子化誤差の合計値を算出する第６の機能と、
量子化誤差の合計値が最小となる残差コードブックに、当該残差クラスタを割り当てる第７の機能と、
Ｍ個の残差コードブックについて、各残差コードブックに割り当てられた残差クラスタに含まれる全ての残差部分ベクトルを用いて、更にＬ個のクラスタにクラスタリングし、そのＬ個の新たな代表ベクトルによって残差コードブックを更新する第８の機能と
してコンピュータを更に機能させることも好ましい。
【００１９】
本発明の検索プログラムにおける他の実施形態によれば、残差コードブック生成手段は、第４から第６の機能を、所定回数、又は、先の量子化誤差の合計値と後の量子化誤差の合計値との差が所定閾値以下となるまで、繰り返すようにコンピュータを更に機能させることも好ましい。
【００２０】
本発明の検索プログラムにおける他の実施形態によれば、
ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであり、
登録ベクトルの付加情報は、画像識別子(IDentifier)、局所特徴領域のスケール、局所特徴領域の角度のいずれか１つを含むことも好ましい。
【発明の効果】
【００２１】
本発明の検索装置及びプログラムによれば、検索精度とメモリ量とのトレードオフを考慮して、高次元の特徴ベクトルの集合から、クエリ特徴ベクトルに類似した特徴ベクトルを検索することができる。
【図面の簡単な説明】
【００２２】
【図１】本発明における検索装置の機能構成図である。
【図２】登録部における処理内容の説明図である。
【図３】クラスタＦに含まれるベクトルを代表ベクトルｆｎに対応付けた説明図である。
【図４】検索部における処理内容の説明図である。
【図５】学習部を更に含む検索装置の機能構成図である。
【図６】コードブック生成部の処理ステップを表すフローチャートである。
【図７】残差コードブック生成部の処理ステップを表すフローチャートである。
【図８】残差コードブック生成部における処理内容の第１の説明図である。
【図９】残差コードブック生成部における処理内容の第２の説明図である。
【発明を実施するための形態】
【００２３】
以下、本発明の実施の形態について、図面を用いて詳細に説明する。
【００２４】
図１は、本発明における検索装置の機能構成図である。
【００２５】
本発明が対象とする検索装置１は、高次元の登録ベクトルの集合から、クエリベクトルに類似したベクトルを検索する。図１によれば、検索装置１は、コードブック記憶部１０１と、残差コードブック記憶部１０２と、転置インデックス記憶部１０３と、登録部１１と、検索部１２とを有する。これら機能構成部は、装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。以下では、［登録部］［検索部］の順に説明すると共に、その中で記憶部１０１〜１０３について説明する。
【００２６】
［登録部］
図２は、登録部における処理内容の説明図である。以下では、図２を参照しつつ、図１の登録部１１の各機能が説明される。また、図３は、クラスタＦに含まれるベクトルを代表ベクトルｆｎに対応付けた説明図である。
【００２７】
登録部１１は、ベクトル量子化部１１１と、残差ベクトル導出部１１２と、残差ベクトル分割部１１３と、残差部分ベクトル量子化部１１４と、転置インデックス生成部１１５とを有する。
【００２８】
コードブック記憶部１０１は、登録ベクトルｆを量子化するために、代表識別値ｎ（＝１〜Ｎ）と代表ベクトルｆｎとを対応付けたコードブックを記憶する（図２のコードブック記憶部１０１参照）。
代表識別値ｎ：  代表ベクトルｆｎ
１：  ｆ１＝（ｆ１１，ｆ１２，・・・，ｆ１Ｄ）
２：  ｆ２＝（ｆ２１，ｆ２２，・・・，ｆ２Ｄ）
３：  ｆ３＝（ｆ３１，ｆ３２，・・・，ｆ３Ｄ）
・・・
Ｎ：  ｆＮ＝（ｆＮ１，ｆＮ２，・・・，ｆＮＤ）
【００２９】
ベクトル量子化部１１１は、登録ベクトルｆを入力する。ここで、ベクトルは、高次元の特徴ベクトルであって、例えば１２８次元（Ｄ＝１２８）で表されるものであってもよい。
登録ベクトルｆ：  ｆ＝（ｆ１，ｆ２，・・・，ｆＤ）
そして、ベクトル量子化部１１１は、登録ベクトルｆを、コードブック記憶部１０１に記憶されたコードブックを用いて、代表識別値ｎ（＝１〜Ｎ、ｎ：整数値）に量子化する（図２のベクトル量子化部１１１参照）。
ｎ＝ｑ（ｆ）＝ａｒｇｍｉｎｎ||ｆ−ｆｎ||２
（登録ベクトルｆの量子化関数ｑ（ｆ）は、||ｆ−ｆｎ||２が最小となるｎを導出
する）
ｑ：ＲＤ->Ｎ（量子化を意味する）
ｆｎ：代表ベクトル
【００３０】
残差ベクトル導出部１１２は、登録ベクトルｆから代表ベクトルｆｎを引いた残差ベクトルｆｒを導出する（図２の残差ベクトル導出部１１２参照）。尚、図３（ａ）によれば、クラスタＦ毎に、多数のベクトルｆに対する代表ベクトルｆｎが表されている。また、ｆとｆｎとの差分となる残差ベクトルもｆｒも表されている。
ｆｒ＝ｆ−ｆｎ（＝ｑ（ｆ））：残差ベクトル
【００３１】
残差ベクトル分割部１１３は、残差ベクトルをＴ個の残差部分ベクトルに分割する（図２の残差ベクトル分割部１１３参照）。ここで、例えば１つの残差部分ベクトルを、１６次元にしたとする。この場合、残差ベクトルは、８個（Ｔ＝Ｄ／Ｄ'＝１２８／１６）の残差部分ベクトルに分割される。
ｆｒ１＝（ｆｒ１，１          ，ｆｒ１，２          ，・・・，ｆｒ１，Ｄ'）
ｆｒ２＝（ｆｒ２，Ｄ'+1       ，ｆｒ２，Ｄ'+2       ，・・・，ｆｒ２，Ｄ'+Ｄ'）
・・・・・
ｆｒＴ＝（ｆｒＴ，(T-1)・Ｄ'+1，ｆｒＴ，(T-1)・Ｄ'+2，・・・，ｆｒT，(T-1)・Ｄ'+Ｄ'）
【００３２】
残差コードブック記憶部１０２は、各残差部分ベクトルｆｒｔを更に量子化するために、残差識別値ｌ（＝１〜Ｌ）と残差部分代表ベクトルｆｌとを対応付けた残差コードブックをＭ×Ｔ個記憶する（図２の残差コードブック記憶部１０２及び図３（ｂ）参照）。また、代表識別値ｎに対応付けられた登録ベクトルｆの残差部分ベクトルｆｒｔが、Ｍ×Ｔ個の残差コードブックのどれで量子化すべきかを示す残差テーブルＴ[n][t]も記憶する。
【００３３】
ここで、Ｍは、１＜＜Ｍ＜＜Ｎの関係にある。Ｍ＝１にすると、残差ベクトルの分布が、クラスタ毎に大きく異なるために、残差ベクトルを量子化する際の量子化誤差が増加し、結果的に近似最近傍検索の精度が悪くなる。一方で、Ｍ＝Ｎにすると、コードブックの情報量（メモリ量）が非常に膨大となってしまう。そこで、本発明は、１＜＜Ｍ＜＜Ｎの関係にすることが重要となる。
【００３４】
残差部分ベクトル量子化部１１４は、代表識別値ｎ＝ｑ（ｆ）とすると、残差部分ベクトルｆｒｔをＴ[n][t]番目の残差コードブックで量子化する。残差テーブルＴ[n][t]には、Ｍが対応付けられている。量子化結果は、以下のように表される。
ｌｔ＝ｑｒT[n][t]（ｆｒｔ）
【００３５】
転置インデックス生成部１１５は、登録ベクトルｆの代表識別値ｎ毎に、複数の残差部分ベクトルｆｒｔの残差識別値ｌｔ（１≦ｔ≦Ｔ）の集合と、登録ベクトルｆに関する付加情報（メタデータ）とを、各登録ベクトルｆの登録情報として登録した転置インデックスを生成する。「転置インデックス」とは、ベクトルを、識別値に置き換えたものである。これは、代表識別値ｎ（＝１〜Ｎ）毎に作成された登録ベクトルのリストである。
【００３６】
登録ベクトルのメタデータには、何が割り当てられてもよい。例えば、登録ベクトルが画像検索における画像特徴量である場合、登録ベクトルが所属する画像識別値を割り当てる。例えば画像の局所特徴領域から抽出された局所特徴ベクトルである場合、メタデータ（登録ベクトルの付加情報）は、画像識別子(IDentifier)、局所特徴領域のスケール、局所特徴領域の角度のいずれか１つを含むことも好ましい。また、高精度に検索する場合、登録ベクトルそのものをメタデータに追加的に登録するものであってもよい。
【００３７】
転置インデックス記憶部１０３は、転置インデックスを、登録ベクトルの集合として記憶する。
【００３８】
［検索部］
検索部１２は、登録部１１と同様に、ベクトル量子化部１１１と、残差ベクトル導出部１１２と、残差ベクトル分割部１１３とを有し、更に、残差ベクトル距離算出部１２４と、登録ベクトル距離算出部１２５と、検索判定部１２６とを有する。
【００３９】
図４は、検索部における処理内容の説明図である。以下では、図４を参照しつつ、図１の検索部１２の各機能が説明される。
【００４０】
検索部１２は、クエリベクトルｆを入力する。クエリベクトルｆは、登録ベクトルと同じ次元のベクトルである。そして、ベクトル量子化部１１１は、クエリベクトルｆを、コードブック記憶部１０１に記憶されたコードブックを用いて、代表識別値ｎ（＝１〜Ｎ、ｎ：整数値）に量子化する。残差ベクトル導出部１１２は、クエリベクトルｆから代表ベクトルｆｎを引いたクエリ残差ベクトルｆｒを導出する。残差ベクトル分割部１１３は、クエリ残差ベクトルをＴ個のクエリ残差部分ベクトルに分割する。
【００４１】
残差ベクトル距離算出部１２４は、クエリ残差部分ベクトルｆｒｔと、残差テーブルＴ[n][t]により指定される残差コードブックの各残差代表ベクトルｆｔ，ｌ（１≦ｌ≦Ｌ）との距離を算出し、テーブルＤ[t][l]に保持する（図４の残差ベクトル距離算出部１２４参照）。
【００４２】
登録ベクトル距離算出部１２５は、登録ベクトルの登録情報である残差識別値ｌｔ（１≦ｔ≦Ｔ）を基に、テーブルＤ[t][l]を参照することで、クエリベクトルと登録ベクトルの近似距離を、距離の和ｄ（＝Σt=1TＤ[t][lｔ]）として算出する（図４の登録ベクトル距離算出部１２５参照）。
【００４３】
検索判定部１２６は、距離の和ｄが、所定閾値以下となる登録ベクトルを、検索結果として出力する（図４の検索判定部１２６参照）。この検索結果として、複数の登録ベクトルが導出されてもよい。
【００４４】
［学習部］
図５は、学習部を更に含む検索装置の機能構成図である。
【００４５】
図５によれば、図１と比較して、学習部１３を更に有する。学習部１３は、学習ベクトルを入力する。学習部１３は、コードブック生成部１３１と、残差コードブック生成部１３２とを有する。
【００４６】
コードブック生成部１３１は、学習ベクトルの集合を用いて、コードブック記憶部１０１に記憶すべきコードブックを生成する。
【００４７】
図６は、コードブック生成部の処理ステップを表すフローチャートである。
【００４８】
（Ｓ６０１）学習ベクトルの集合Ｆを、Ｎ個のクラスタにクラスタリングする。
Ｆ -> Ｆ１，Ｆ２，・・・，ＦＮ
例えばk-means又はk-means++のようなクラスタリングアルゴリズムが用いられる。
（Ｓ６０２）クラスタ毎に、代表ベクトルｆｎを導出する。
ｆ１，ｆ２，・・・，ｆＮ
（Ｓ６０３）各代表ベクトルに、一意の代表識別値ｎ（＝１〜Ｎ）を割り当てたコードブックを生成する。が得られる。
残差ベクトル集合：Ｆｒｎ＝｛ｆ−ｆｎ|ｆ∈Ｆｎ｝
【００４９】
残差コードブック生成部１３２は、残差コードブック記憶部１０２に記憶すべき残差コードブックを生成する。
【００５０】
図７は、残差コードブック生成部の処理ステップを表すフローチャートである。図８は、残差コードブック生成部における処理内容の第１の説明図である。図９は、残差コードブック生成部における処理内容の第２の説明図である。以下では、図８及び９を参照しつつ、図７のフローチャートの処理内容が説明される。
【００５１】
（Ｓ７０１）代表ベクトルｆｎと、当該代表ベクトルｆｎに属する学習ベクトルｆとの間の残差ベクトルｆｒ（＝ｆ−ｆｎ）を導出する（図８のＳ７０１参照）。これによって、Ｎ個の残差クラスタを作成する。
（Ｓ７０２）残差ベクトルｆｒを、Ｔ個の残差部分ベクトルｆｒｔに分割する（図８のＳ７０２参照）。
【００５２】
（Ｓ７０３）残差部分ベクトルｆｒｔそれぞれについて、以下のＳ７０４〜Ｓ７１１の処理を実行する。
（Ｓ７０４）Ｎ個の残差クラスタから任意のＭ個の残差クラスタを選択する（図８のＳ７０４参照）。
（Ｓ７０５）Ｍ個の各残差クラスタについて、各残差クラスタに属する残差部分ベクトルを更にＬ個のクラスタにクラスタリングする（図８のＳ７０５参照）。Ｓ６０１と同様に、例えばk-means又はk-means++のようなクラスタリングアルゴリズムが用いられる。
（Ｓ７０６）Ｍ個の残差クラスタからそれぞれ作成されたＬ個のクラスタの代表ベクトル集合から、Ｌ個の要素を持つ残差コードブックをＭ個生成する（図８のＳ７０６参照）。ここで、Ｎ個の残差クラスタは、Ｍ個の中のいずれか１つの残差コードブックに対応付けられる。
【００５３】
（Ｓ７０７）以下、Ｓ７０８〜Ｓ７１０を、所定回数、又は、先の量子化誤差の合計値と後の量子化誤差の合計値との差が所定閾値以下となるまで、繰り返す（図９参照）。
（Ｓ７０８）Ｎ個の残差クラスタについて、各残差クラスタに属する残差部分ベクトルの全てを、Ｍ個の残差コードブック各々を用いて量子化した場合の量子化誤差の合計値を算出する。
（Ｓ７０９）量子化誤差の合計値が最小となる残差コードブックに、当該残差クラスタを割り当てる。
（Ｓ７１０）Ｍ個の残差コードブックについて、各残差コードブックに割り当てられた残差クラスタに含まれる全ての残差部分ベクトルを用いて、更にＬ個のクラスタにクラスタリングする。そして、そのＬ個の新たな代表ベクトルによって残差コードブックを更新する。
【００５４】
以上、詳細に説明したように、本発明の検索装置及びプログラムによれば、検索精度とメモリ量とのトレードオフを考慮して、高次元の特徴ベクトルの集合から、クエリ特徴ベクトルに類似した特徴ベクトルを検索することができる。
【００５５】
従来技術によれば、特徴ベクトルを量子化し、その量子化ベクトルの残差ベクトルに識別値を割り当てている。しかしながら、残差符号化のための残差コードブックが、特徴ベクトルで同一であったために、検索精度が低くなってしまう。これに対し、本発明によれば、クラスタ毎にコードブックを変更することによって、高次元ベクトルを高精度に検索することができる。即ち、クラスタ毎の残差ベクトルの分布に基づいてＭ個のコードブックを最適化することによって、全てのクラスタの残差コードブックを生成することなく（Ｍ＝Ｎ）、単一の残差コードブックを用いるよりも（Ｍ＝１）、高精度に検索することができる。
【００５６】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００５７】
１  検索装置
１０１  コードブック記憶部
１０２  残差コードブック記憶部
１０３  転置インデックス記憶部
１１  登録部
１１１  ベクトル量子化部
１１２  残差ベクトル導出部
１１３  残差ベクトル分割部
１１４  残差部分ベクトル量子化部
１１５  転置インデックス生成部
１２  検索部
１２５  残差ベクトル距離算出部
１２６  登録ベクトル距離算出部
１２７  検索判定部
【図１】
0005436346.tif 000002
【図２】
0005436346.tif 000003
【図３】
0005436346.tif 000004
【図４】
0005436346.tif 000005
【図５】
0005436346.tif 000006
【図６】
0005436346.tif 000007
【図７】
0005436346.tif 000008
【図８】
0005436346.tif 000009
【図９】
0005436346.tif 000010