(57)【特許請求の範囲】
【請求項１】
粗量子化及び直積量子化を用いて符号化された高次元の登録ベクトルの集合からクエリベクトルに類似したベクトルを検索する検索装置であって、
残差コードブック及び残差コードブック識別子テーブルＴ[n][t]を生成するものであり、
粗量子化における代表識別値ｎ（＝１〜Ｎ）に割り当てられた学習ベクトルｆと、それに対応する代表ベクトルｆｎとの間の残差ベクトルｆｒ（＝ｆ−ｆｎ）を導出することによってＮ個の残差クラスタを作成する第１の機能と、
前記残差ベクトルｆｒをＴ個の残差部分ベクトルに分割し、ｔ番目の残差部分ベクトル集合Ｒn,t（１≦ｎ≦Ｎ，１≦ｔ≦Ｔ）を生成する第２の機能と、
前記残差部分ベクトル集合Ｒn,tそれぞれについて、前記残差コードブック識別子テーブルＴ[n][t]に、いずれかのラベル値ｍ（ｍ＝1,2,..,M）を割り当てる第３の機能と、
前記ラベル値ｍそれぞれについて、当該ラベル値ｍが割り当てられた全ての残差部分ベクトル集合Ｒn,tを用いて、当該ｍ番目の残差コードブックを生成する第４の機能と、
前記残差部分ベクトル集合Ｒn,tそれぞれについて、Ｍ個の残差コードブックそれぞれで量子化した際の量子化誤差が最も小さくなるｍ'番目の残差コードブックを用いて残差コードブック識別子テーブルＴ[n][t]を更新する第５の機能と
を有し、第４及び第５の機能を繰り返し実行する
残差コードブック生成手段を有することを特徴とする検索装置。
【請求項２】
コードブックを生成するコードブック生成手段を更に有し、
前記コードブック生成手段は、
前記学習ベクトルの集合を、Ｎ個のクラスタにクラスタリングする第１の機能と、
前記クラスタ毎に、代表ベクトルを導出する第２の機能と、
各代表ベクトルに、一意の代表識別値ｎ（＝１〜Ｎ）を割り当てたコードブックを生成する第３の機能とを実行する
ことを特徴とする請求項１に記載の検索装置。
【請求項３】
前記登録ベクトルｆを量子化するために、代表識別値ｎ（＝１〜Ｎ）と代表ベクトルｆｎとを対応付けたコードブックを記憶するコードブック記憶手段と、
前記登録ベクトルｆを、前記コードブックを用いて、代表識別値ｎに量子化するベクトル量子化手段と、
前記登録ベクトルｆから代表ベクトルｆｎを引いた残差ベクトルｆｒを導出する残差ベクトル導出手段と、
前記残差ベクトルをＴ個の残差部分ベクトルｆｒ1, ｆｒ2, ..., ｆｒTに分割する残差ベクトル分割手段と、
各残差部分ベクトルｆｒｔを更に量子化するために、残差識別値ｌ（＝１〜Ｌ）と残差部分代表ベクトルｆｌとを対応付けた残差コードブックをＭ個記憶すると共に、前記代表識別値ｎに対応付けられた登録ベクトルｆの残差部分ベクトルｆｒｔが、前記Ｍ個の残差コードブックのどれで量子化すべきかを示す残差コードブック識別子テーブルＴ[n][t]を記憶する残差コードブック記憶手段と、
前記残差部分ベクトルｆｒｔを、Ｔ[n][t]番目の前記残差コードブックで量子化する残差部分ベクトル量子化手段と、
前記登録ベクトルｆの代表識別値ｎ毎に、複数の残差部分ベクトルｆｒｔの残差識別値ｌｔ（１≦ｔ≦Ｔ）の集合と、登録ベクトルｆに関する付加情報とを、各登録ベクトルｆの登録情報として登録した転置インデックスを生成する転置インデックス生成手段と、
前記転置インデックスを、登録ベクトルの集合として記憶する転置インデックス記憶手段と
を有することを特徴とする請求項２に記載の検索装置。
【請求項４】
前記残差コードブック生成手段における第３の機能について、前記残差コードブック識別子テーブルＴ[n][t]に、ランダムに、いずれかのラベル値ｍ（ｍ＝1,2,..,M）を割り当てることを特徴とする請求項２又は３に記載の検索装置。
【請求項５】
前記残差コードブック生成手段における第３の機能について、
前記残差部分ベクトル集合Ｒn,tの中から、ランダムにいずれか１つの残差部分ベクトル集合Ｒn,tを選択する第３１の機能と、
選択された当該残差部分ベクトル集合Ｒn,t内の残差部分ベクトルをクラスタリングし、１つの残差コードブックを生成する第３２の機能と、
前記残差部分ベクトル集合Ｒn,tそれぞれについて、既に作成された全ての残差コードブックそれぞれで量子化した際に、量子化誤差の総和が最小となる残差コードブック及び量子化誤差Ｄn,tを求める第３３の機能と、
全ての残差部分ベクトル集合Ｒn,t（１≦ｎ≦Ｎ，１≦ｔ≦Ｔ）の中から前記Ｄn,tに比例する確率で１つの残差部分ベクトル集合を選択し、その残差部分ベクトル集合内の残差部分ベクトルをクラスタリングすることで、１つの残差コードブックを生成する第３４の機能と、
Ｍ個の残差コードブックが生成されるまで、第３３及び第３４の機能を繰り返す第３５の機能と、
前記残差部分ベクトル集合Ｒn,tそれぞれについて、Ｍ個の残差コードブックそれぞれで量子化した際に、量子化誤差が最小となる当該残差コードブックのラベル値ｍを、当該残差部分ベクトル集合Ｒn,tに割り当てる第３６の機能と
を有することを特徴とする請求項２又は３に記載の検索装置。
【請求項６】
前記転置インデックス記憶手段を用いて、クエリベクトルに類似したベクトルを検索するために、
前記ベクトル量子化手段は、前記クエリベクトルｆを、前記コードブックを用いて、代表識別値ｎに量子化し、
前記残差ベクトル導出手段は、前記クエリベクトルｆから代表ベクトルｆｎを引いたクエリ残差ベクトルｆｒを導出し、
前記残差ベクトル分割手段は、前記クエリ残差ベクトルをＴ個のクエリ残差部分ベクトルに分割する
と共に、
前記クエリ残差部分ベクトルｆｒｔと、前記残差コードブック識別子テーブルＴ[n][t]により指定される残差コードブックの各残差代表ベクトルｆｔ，ｌ（１≦ｌ≦Ｌ）とのＬｐ距離を算出し参照テーブルＤ[t][l]に保持する残差ベクトル距離算出手段と、
前記登録ベクトルの登録情報である残差識別値ｌｔ（１≦ｔ≦Ｔ）を基に、前記テーブルＤ[t][l]を参照することで、クエリベクトルと登録ベクトルのＬｐ距離の推定値を、参照テーブルの重み付き和ｄ（＝Σt=1Tｗt・Ｄ[t][lｔ]）として算出する登録ベクトル距離算出手段と、
前記距離の重み付き和ｄが、所定閾値以下となる登録ベクトルを、又は、距離の重み付き和ｄが小さいものから順に所定個数となる登録ベクトルを、検索結果として出力する検索判定手段と
を有することを特徴とする請求項１から５のいずれか１項に記載の検索装置。
【請求項７】
前記登録ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであり、
前記登録ベクトルの付加情報は、画像識別子(IDentifier)、局所特徴領域のスケール、局所特徴領域の角度のいずれか１つを含むことを特徴とする請求項１から６のいずれか１項に記載の検索装置。
【請求項８】
粗量子化及び直積量子化を用いて符号化された高次元の登録ベクトルの集合からクエリベクトルに類似したベクトルを検索する装置に搭載されたコンピュータを機能させるプログラムであって、
残差コードブック及び残差コードブック識別子テーブルＴ[n][t]を生成するものであり、
粗量子化における代表識別値ｎ（＝１〜Ｎ）に割り当てられた学習ベクトルｆと、それに対応する代表ベクトルｆｎとの間の残差ベクトルｆｒ（＝ｆ−ｆｎ）を導出することによってＮ個の残差クラスタを作成する第１の機能と、
前記残差ベクトルｆｒをＴ個の残差部分ベクトルに分割し、ｔ番目の残差部分ベクトル集合Ｒn,t（１≦ｎ≦Ｎ，１≦ｔ≦Ｔ）を生成する第２の機能と、
前記残差部分ベクトル集合Ｒn,tそれぞれについて、前記残差コードブック識別子テーブルＴ[n][t]に、いずれかのラベル値ｍ（ｍ＝1,2,..,M）を割り当てる第３の機能と、
前記ラベル値ｍそれぞれについて、当該ラベル値ｍが割り当てられた全ての残差部分ベクトル集合Ｒn,tを用いて、当該ｍ番目の残差コードブックを生成する第４の機能と、
前記残差部分ベクトル集合Ｒn,tそれぞれについて、Ｍ個の残差コードブックそれぞれで量子化した際の量子化誤差が最も小さくなるｍ'番目の残差コードブックを用いて残差コードブック識別子テーブルＴ[n][t]を更新する第５の機能と
を有し、第４及び第５の機能を繰り返し実行する
残差コードブック生成手段としてコンピュータを機能させることを特徴とする検索プログラム。
【請求項９】
コードブックを生成するコードブック生成手段を更に有し、
前記コードブック生成手段は、
前記学習ベクトルの集合を、Ｎ個のクラスタにクラスタリングする第１の機能と、
前記クラスタ毎に、代表ベクトルを導出する第２の機能と、
各代表ベクトルに、一意の代表識別値ｎ（＝１〜Ｎ）を割り当てたコードブックを生成する第３の機能とを実行する
ようにコンピュータを機能させることを特徴とする請求項８に記載の検索プログラム。
【請求項１０】
前記登録ベクトルｆを量子化するために、代表識別値ｎ（＝１〜Ｎ）と代表ベクトルｆｎとを対応付けたコードブックを記憶するコードブック記憶手段と、
前記登録ベクトルｆを、前記コードブックを用いて、代表識別値ｎに量子化するベクトル量子化手段と、
前記登録ベクトルｆから代表ベクトルｆｎを引いた残差ベクトルｆｒを導出する残差ベクトル導出手段と、
前記残差ベクトルをＴ個の残差部分ベクトルｆｒ1, ｆｒ2, ..., ｆｒTに分割する残差ベクトル分割手段と、
各残差部分ベクトルｆｒｔを更に量子化するために、残差識別値ｌ（＝１〜Ｌ）と残差部分代表ベクトルｆｌとを対応付けた残差コードブックをＭ個記憶すると共に、前記代表識別値ｎに対応付けられた登録ベクトルｆの残差部分ベクトルｆｒｔが、前記Ｍ個の残差コードブックのどれで量子化すべきかを示す残差コードブック識別子テーブルＴ[n][t]を記憶する残差コードブック記憶手段と、
前記残差部分ベクトルｆｒｔを、Ｔ[n][t]番目の前記残差コードブックで量子化する残差部分ベクトル量子化手段と、
前記登録ベクトルｆの代表識別値ｎ毎に、複数の残差部分ベクトルｆｒｔの残差識別値ｌｔ（１≦ｔ≦Ｔ）の集合と、登録ベクトルｆに関する付加情報とを、各登録ベクトルｆの登録情報として登録した転置インデックスを生成する転置インデックス生成手段と、
前記転置インデックスを、登録ベクトルの集合として記憶する転置インデックス記憶手段と
してコンピュータを更に機能させることを特徴とする請求項９に記載の検索プログラム。
【請求項１１】
前記残差コードブック生成手段における第３の機能について、前記残差コードブック識別子テーブルＴ[n][t]に、ランダムに、いずれかのラベル値ｍ（ｍ＝1,2,..,M）を割り当てるようにコンピュータを機能させることを特徴とする請求項９又は１０に記載の検索プログラム。
【請求項１２】
前記残差コードブック生成手段における第３の機能について、
前記残差部分ベクトル集合Ｒn,tの中から、ランダムにいずれか１つの残差部分ベクトル集合Ｒn,tを選択する第３１の機能と、
選択された当該残差部分ベクトル集合Ｒn,t内の残差部分ベクトルをクラスタリングし、１つの残差コードブックを生成する第３２の機能と、
前記残差部分ベクトル集合Ｒn,tそれぞれについて、既に作成された全ての残差コードブックそれぞれで量子化した際に、量子化誤差の総和が最小となる残差コードブック及び量子化誤差Ｄn,tを求める第３３の機能と、
全ての残差部分ベクトル集合Ｒn,t（１≦ｎ≦Ｎ，１≦ｔ≦Ｔ）の中から前記Ｄn,tに比例する確率で１つの残差部分ベクトル集合を選択し、その残差部分ベクトル集合内の残差部分ベクトルをクラスタリングすることで、１つの残差コードブックを生成する第３４の機能と、
Ｍ個の残差コードブックが生成されるまで、第３３及び第３４の機能を繰り返す第３５の機能と、
前記残差部分ベクトル集合Ｒn,tそれぞれについて、Ｍ個の残差コードブックそれぞれで量子化した際に、量子化誤差が最小となる当該残差コードブックのラベル値ｍを、当該残差部分ベクトル集合Ｒn,tに割り当てる第３６の機能と
してコンピュータを更に機能させることを特徴とする請求項９又は１０に記載の検索プログラム。
【請求項１３】
前記転置インデックス記憶手段を用いて、クエリベクトルに類似したベクトルを検索するために、
前記ベクトル量子化手段は、前記クエリベクトルｆを、前記コードブックを用いて、代表識別値ｎに量子化し、
前記残差ベクトル導出手段は、前記クエリベクトルｆから代表ベクトルｆｎを引いたクエリ残差ベクトルｆｒを導出し、
前記残差ベクトル分割手段は、前記クエリ残差ベクトルをＴ個のクエリ残差部分ベクトルに分割する
と共に、
前記クエリ残差部分ベクトルｆｒｔと、前記残差コードブック識別子テーブルＴ[n][t]により指定される残差コードブックの各残差代表ベクトルｆｔ，ｌ（１≦ｌ≦Ｌ）とのＬｐ距離を算出し参照テーブルＤ[t][l]に保持する残差ベクトル距離算出手段と、
前記登録ベクトルの登録情報である残差識別値ｌｔ（１≦ｔ≦Ｔ）を基に、前記テーブルＤ[t][l]を参照することで、クエリベクトルと登録ベクトルのＬｐ距離の推定値を、参照テーブルの重み付き和ｄ（＝Σt=1Tｗt・Ｄ[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 and David G. Lowe、「FastApproximate Nearest Neighbors with Automatic Algorithm Configuration」、IEEE International Conference on Computer Vision、Theory and Applications (VISAPP'09)、2009.
【非特許文献２】Herve Jegou, Matthijs Douze, Cordelia Schmid、「Product Quantization for Nearest Neighbor Search」、IEEE Transactions on Pattern Analysis and Machine Intelligence、25 Feb. 2010.
【非特許文献３】D. G. Lowe, 「Distinctive Image Features fromScale-Invariant Keypoints」、International Journal ofComputer Vision、vol. 60, no. 2, pp. 91-110, 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、非特許文献２に記載された技術によれば、残差ベクトルを単一のコードブックで量子化しているために、近似最近傍検索の精度が悪くなるという問題があった。これは、最初に荒く量子化した際に、残差ベクトルの分布が、クラスタ毎に大きく異なるためである。一方で、この残差ベクトルのコードブックを、クラスタ毎に生成してしまうと、コードブックの情報量（メモリ量）が非常に膨大となってしまう。
【００１０】
そこで、本発明は、検索精度とメモリ量とのトレードオフを考慮して、少ないコードブックの情報量によって、高次元の特徴ベクトルの集合からクエリ特徴ベクトルに類似した特徴ベクトルを検索することができる検索装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明によれば、粗量子化及び直積量子化を用いて符号化された高次元の登録ベクトルの集合からクエリベクトルに類似したベクトルを検索する検索装置であって、
残差コードブック及び残差コードブック識別子テーブルＴ[n][t]を生成するものであり、
粗量子化における代表識別値ｎ（＝１〜Ｎ）に割り当てられた学習ベクトルｆと、それに対応する代表ベクトルｆｎとの間の残差ベクトルｆｒ（＝ｆ−ｆｎ）を導出することによってＮ個の残差クラスタを作成する第１の機能と、
残差ベクトルｆｒをＴ個の残差部分ベクトルに分割し、ｔ番目の残差部分ベクトル集合Ｒn,t（１≦ｎ≦Ｎ，１≦ｔ≦Ｔ）を生成する第２の機能と、
残差部分ベクトル集合Ｒn,tそれぞれについて、残差コードブック識別子テーブルＴ[n][t]に、いずれかのラベル値ｍ（ｍ＝1,2,..,M）を割り当てる第３の機能と、
ラベル値ｍそれぞれについて、当該ラベル値ｍが割り当てられた全ての残差部分ベクトル集合Ｒn,tを用いて、当該ｍ番目の残差コードブックを生成する第４の機能と、
残差部分ベクトル集合Ｒn,tそれぞれについて、Ｍ個の残差コードブックそれぞれで量子化した際の量子化誤差が最も小さくなるｍ'番目の残差コードブックを用いて残差コードブック識別子テーブルＴ[n][t]を更新する第５の機能と
を有し、第４及び第５の機能を繰り返し実行する
残差コードブック生成手段を有することを特徴とする。
【００１３】
本発明の検索装置における他の実施形態によれば、
コードブックを生成するコードブック生成手段を更に有し、
コードブック生成手段は、
学習ベクトルの集合を、Ｎ個のクラスタにクラスタリングする第１の機能と、
クラスタ毎に、代表ベクトルを導出する第２の機能と、
各代表ベクトルに、一意の代表識別値ｎ（＝１〜Ｎ）を割り当てたコードブックを生成する第３の機能とを実行することも好ましい。
【００１４】
本発明の検索装置における他の実施形態によれば、
登録ベクトルｆを量子化するために、代表識別値ｎ（＝１〜Ｎ）と代表ベクトルｆｎとを対応付けたコードブックを記憶するコードブック記憶手段と、
登録ベクトルｆを、コードブックを用いて、代表識別値ｎに量子化するベクトル量子化手段と、
登録ベクトルｆから代表ベクトルｆｎを引いた残差ベクトルｆｒを導出する残差ベクトル導出手段と、
残差ベクトルをＴ個の残差部分ベクトルｆｒ1, ｆｒ2, ..., ｆｒTに分割する残差ベクトル分割手段と、
各残差部分ベクトルｆｒｔを更に量子化するために、残差識別値ｌ（＝１〜Ｌ）と残差部分代表ベクトルｆｌとを対応付けた残差コードブックをＭ個記憶すると共に、代表識別値ｎに対応付けられた登録ベクトルｆの残差部分ベクトルｆｒｔが、Ｍ個の残差コードブックのどれで量子化すべきかを示す残差コードブック識別子テーブルＴ[n][t]を記憶する残差コードブック記憶手段と、
残差部分ベクトルｆｒｔを、Ｔ[n][t]番目の残差コードブックで量子化する残差部分ベクトル量子化手段と、
登録ベクトルｆの代表識別値ｎ毎に、複数の残差部分ベクトルｆｒｔの残差識別値ｌｔ（１≦ｔ≦Ｔ）の集合と、登録ベクトルｆに関する付加情報とを、各登録ベクトルｆの登録情報として登録した転置インデックスを生成する転置インデックス生成手段と、
転置インデックスを、登録ベクトルの集合として記憶する転置インデックス記憶手段と
を有することも好ましい。
【００１５】
本発明の検索装置における他の実施形態によれば、
残差コードブック生成手段における第３の機能について、残差コードブック識別子テーブルＴ[n][t]に、ランダムに、いずれかのラベル値ｍ（ｍ＝1,2,..,M）を割り当てることも好ましい。
【００１６】
本発明の検索装置における他の実施形態によれば、
残差コードブック生成手段における第３の機能について、
残差部分ベクトル集合Ｒn,tの中から、ランダムにいずれか１つの残差部分ベクトル集合Ｒn,tを選択する第３１の機能と、
選択された当該残差部分ベクトル集合Ｒn,t内の残差部分ベクトルをクラスタリングし、１つの残差コードブックを生成する第３２の機能と、
残差部分ベクトル集合Ｒn,tそれぞれについて、既に作成された全ての残差コードブックそれぞれで量子化した際に、量子化誤差の総和が最小となる残差コードブック及び量子化誤差Ｄn,tを求める第３３の機能と、
全ての残差部分ベクトル集合Ｒn,t（１≦ｎ≦Ｎ，１≦ｔ≦Ｔ）の中からＤn,tに比例する確率で１つの残差部分ベクトル集合を選択し、その残差部分ベクトル集合内の残差部分ベクトルをクラスタリングすることで、１つの残差コードブックを生成する第３４の機能と、
Ｍ個の残差コードブックが生成されるまで、第３３及び第３４の機能を繰り返す第３５の機能と、
残差部分ベクトル集合Ｒn,tそれぞれについて、Ｍ個の残差コードブックそれぞれで量子化した際に、量子化誤差が最小となる当該残差コードブックのラベル値ｍを、当該残差部分ベクトル集合Ｒn,tに割り当てる第３６の機能と
を有することも好ましい。
【００１７】
本発明の検索装置における他の実施形態によれば、
転置インデックス記憶手段を用いて、クエリベクトルに類似したベクトルを検索するために、
ベクトル量子化手段は、クエリベクトルｆを、コードブックを用いて、代表識別値ｎに量子化し、
残差ベクトル導出手段は、クエリベクトルｆから代表ベクトルｆｎを引いたクエリ残差ベクトルｆｒを導出し、
残差ベクトル分割手段は、クエリ残差ベクトルをＴ個のクエリ残差部分ベクトルに分割する
と共に、
クエリ残差部分ベクトルｆｒｔと、残差コードブック識別子テーブルＴ[n][t]により指定される残差コードブックの各残差代表ベクトルｆｔ，ｌ（１≦ｌ≦Ｌ）とのＬｐ距離を算出し参照テーブルＤ[t][l]に保持する残差ベクトル距離算出手段と、
登録ベクトルの登録情報である残差識別値ｌｔ（１≦ｔ≦Ｔ）を基に、テーブルＤ[t][l]を参照することで、クエリベクトルと登録ベクトルのＬｐ距離の推定値を、参照テーブルの重み付き和ｄ（＝Σt=1Tｗt・Ｄ[t][lｔ]）として算出する登録ベクトル距離算出手段と、
距離の重み付き和ｄが、所定閾値以下となる登録ベクトルを、又は、距離の重み付き和ｄが小さいものから順に所定個数となる登録ベクトルを、検索結果として出力する検索判定手段と
を有することも好ましい。
【００１８】
本発明の検索装置における他の実施形態によれば、
登録ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであり、
登録ベクトルの付加情報は、画像識別子(IDentifier)、局所特徴領域のスケール、局所特徴領域の角度のいずれか１つを含むことも好ましい。
【００１９】
本発明によれば、粗量子化及び直積量子化を用いて符号化された高次元の登録ベクトルの集合からクエリベクトルに類似したベクトルを検索する装置に搭載されたコンピュータを機能させるプログラムであって、
残差コードブック及び残差コードブック識別子テーブルＴ[n][t]を生成するものであり、
粗量子化における代表識別値ｎ（＝１〜Ｎ）に割り当てられた学習ベクトルｆと、それに対応する代表ベクトルｆｎとの間の残差ベクトルｆｒ（＝ｆ−ｆｎ）を導出することによってＮ個の残差クラスタを作成する第１の機能と、
残差ベクトルｆｒをＴ個の残差部分ベクトルに分割し、ｔ番目の残差部分ベクトル集合Ｒn,t（１≦ｎ≦Ｎ，１≦ｔ≦Ｔ）を生成する第２の機能と、
残差部分ベクトル集合Ｒn,tそれぞれについて、残差コードブック識別子テーブルＴ[n][t]に、いずれかのラベル値ｍ（ｍ＝1,2,..,M）を割り当てる第３の機能と、
ラベル値ｍそれぞれについて、当該ラベル値ｍが割り当てられた全ての残差部分ベクトル集合Ｒn,tを用いて、当該ｍ番目の残差コードブックを生成する第４の機能と、
残差部分ベクトル集合Ｒn,tそれぞれについて、Ｍ個の残差コードブックそれぞれで量子化した際の量子化誤差が最も小さくなるｍ'番目の残差コードブックを用いて残差コードブック識別子テーブルＴ[n][t]を更新する第５の機能と
を有し、第４及び第５の機能を繰り返し実行する
残差コードブック生成手段としてコンピュータを機能させることを特徴とする。
【００２１】
本発明の検索プログラムにおける他の実施形態によれば、
コードブックを生成するコードブック生成手段を更に有し、
コードブック生成手段は、
学習ベクトルの集合を、Ｎ個のクラスタにクラスタリングする第１の機能と、
クラスタ毎に、代表ベクトルを導出する第２の機能と、
各代表ベクトルに、一意の代表識別値ｎ（＝１〜Ｎ）を割り当てたコードブックを生成する第３の機能とを実行する
ようにコンピュータを機能させることも好ましい。
【００２２】
本発明の検索プログラムにおける他の実施形態によれば、
登録ベクトルｆを量子化するために、代表識別値ｎ（＝１〜Ｎ）と代表ベクトルｆｎとを対応付けたコードブックを記憶するコードブック記憶手段と、
登録ベクトルｆを、コードブックを用いて、代表識別値ｎに量子化するベクトル量子化手段と、
登録ベクトルｆから代表ベクトルｆｎを引いた残差ベクトルｆｒを導出する残差ベクトル導出手段と、
残差ベクトルをＴ個の残差部分ベクトルｆｒ1, ｆｒ2, ..., ｆｒTに分割する残差ベクトル分割手段と、
各残差部分ベクトルｆｒｔを更に量子化するために、残差識別値ｌ（＝１〜Ｌ）と残差部分代表ベクトルｆｌとを対応付けた残差コードブックをＭ個記憶すると共に、代表識別値ｎに対応付けられた登録ベクトルｆの残差部分ベクトルｆｒｔが、Ｍ個の残差コードブックのどれで量子化すべきかを示す残差コードブック識別子テーブルＴ[n][t]を記憶する残差コードブック記憶手段と、
残差部分ベクトルｆｒｔを、Ｔ[n][t]番目の残差コードブックで量子化する残差部分ベクトル量子化手段と、
登録ベクトルｆの代表識別値ｎ毎に、複数の残差部分ベクトルｆｒｔの残差識別値ｌｔ（１≦ｔ≦Ｔ）の集合と、登録ベクトルｆに関する付加情報とを、各登録ベクトルｆの登録情報として登録した転置インデックスを生成する転置インデックス生成手段と、
転置インデックスを、登録ベクトルの集合として記憶する転置インデックス記憶手段と
してコンピュータを更に機能させることも好ましい。
【００２３】
本発明の検索プログラムにおける他の実施形態によれば、
残差コードブック生成手段における第３の機能について、残差コードブック識別子テーブルＴ[n][t]に、ランダムに、いずれかのラベル値ｍ（ｍ＝1,2,..,M）を割り当てるようにコンピュータを機能させることも好ましい。
【００２４】
本発明の検索プログラムにおける他の実施形態によれば、
残差コードブック生成手段における第３の機能について、
残差部分ベクトル集合Ｒn,tの中から、ランダムにいずれか１つの残差部分ベクトル集合Ｒn,tを選択する第３１の機能と、
選択された当該残差部分ベクトル集合Ｒn,t内の残差部分ベクトルをクラスタリングし、１つの残差コードブックを生成する第３２の機能と、
残差部分ベクトル集合Ｒn,tそれぞれについて、既に作成された全ての残差コードブックそれぞれで量子化した際に、量子化誤差の総和が最小となる残差コードブック及び量子化誤差Ｄn,tを求める第３３の機能と、
全ての残差部分ベクトル集合Ｒn,t（１≦ｎ≦Ｎ，１≦ｔ≦Ｔ）の中からＤn,tに比例する確率で１つの残差部分ベクトル集合を選択し、その残差部分ベクトル集合内の残差部分ベクトルをクラスタリングすることで、１つの残差コードブックを生成する第３４の機能と、
Ｍ個の残差コードブックが生成されるまで、第３３及び第３４の機能を繰り返す第３５の機能と、
残差部分ベクトル集合Ｒn,tそれぞれについて、Ｍ個の残差コードブックそれぞれで量子化した際に、量子化誤差が最小となる当該残差コードブックのラベル値ｍを、当該残差部分ベクトル集合Ｒn,tに割り当てる第３６の機能と
してコンピュータを更に機能させることも好ましい。
【００２５】
本発明の検索プログラムにおける他の実施形態によれば、
転置インデックス記憶手段を用いて、クエリベクトルに類似したベクトルを検索するために、
ベクトル量子化手段は、クエリベクトルｆを、コードブックを用いて、代表識別値ｎに量子化し、
残差ベクトル導出手段は、クエリベクトルｆから代表ベクトルｆｎを引いたクエリ残差ベクトルｆｒを導出し、
残差ベクトル分割手段は、クエリ残差ベクトルをＴ個のクエリ残差部分ベクトルに分割する
と共に、
クエリ残差部分ベクトルｆｒｔと、残差コードブック識別子テーブルＴ[n][t]により指定される残差コードブックの各残差代表ベクトルｆｔ，ｌ（１≦ｌ≦Ｌ）とのＬｐ距離を算出し参照テーブルＤ[t][l]に保持する残差ベクトル距離算出手段と、
登録ベクトルの登録情報である残差識別値ｌｔ（１≦ｔ≦Ｔ）を基に、テーブルＤ[t][l]を参照することで、クエリベクトルと登録ベクトルのＬｐ距離の推定値を、参照テーブルの重み付き和ｄ（＝Σt=1Tｗt・Ｄ[t][lｔ]）として算出する登録ベクトル距離算出手段と、
距離の重み付き和ｄが、所定閾値以下となる登録ベクトルを、又は、距離の重み付き和ｄが小さいものから順に所定個数となる登録ベクトルを、検索結果として出力する検索判定手段と
してコンピュータを更に機能させることも好ましい。
【００２６】
本発明の検索プログラムにおける他の実施形態によれば、
登録ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであり、
登録ベクトルの付加情報は、画像識別子(IDentifier)、局所特徴領域のスケール、局所特徴領域の角度のいずれか１つを含むようにコンピュータを機能させることも好ましい。
【発明の効果】
【００２７】
本発明の検索装置及びプログラムによれば、検索精度とメモリ量とのトレードオフを考慮して、少ないコードブックの情報量によって、高次元の特徴ベクトルの集合からクエリ特徴ベクトルに類似した特徴ベクトルを検索することができる。
【図面の簡単な説明】
【００２８】
【図１】検索装置の機能構成図である。
【図２】登録部における処理内容の説明図である。
【図３】クラスタＦに含まれるベクトルを代表ベクトルｆｎに対応付けた説明図である。
【図４】検索部における処理内容の説明図である。
【図５】本発明における学習部を含む検索装置の機能構成図である。
【図６】コードブック生成部の処理ステップを表すフローチャートである。
【図７】本発明における残差コードブック生成部の処理ステップを表すフローチャートである。
【図８】残差コードブック生成部における処理内容の第１の説明図である。
【図９】残差コードブック生成部における処理内容の第２の説明図である。
【図１０】本発明における第２のラベル値割当方法の処理ステップを表すフローチャートである。
【図１１】第２のラベル値割当方法の処理内容の説明図である。
【発明を実施するための形態】
【００２９】
以下、本発明の実施の形態について、図面を用いて詳細に説明する。
【００３０】
図１は、検索装置の機能構成図である。
【００３１】
本発明が対象とする検索装置１は、粗量子化及び直積量子化を用いて符号化された高次元の登録ベクトルの集合からクエリベクトルに類似したベクトルを検索する。検索装置１は、コードブック記憶部１０１と、残差コードブック記憶部１０２と、転置インデックス記憶部１０３と、登録部１１と、検索部１２とを有する。これら機能構成部は、装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。以下では、［登録部］［検索部］の順に説明すると共に、その中で記憶部１０１〜１０３について説明する。
【００３２】
［登録部］
図２は、登録部における処理内容の説明図である。以下では、図２を参照しつつ、図１の登録部１１の各機能が説明される。また、図３は、クラスタＦに含まれるベクトルを代表ベクトルｆｎに対応付けた説明図である。
【００３３】
登録部１１は、ベクトル量子化部１１１と、残差ベクトル導出部１１２と、残差ベクトル分割部１１３と、残差部分ベクトル量子化部１１４と、転置インデックス生成部１１５とを有する。
【００３４】
コードブック記憶部１０１は、登録ベクトルｆを量子化するために、代表識別値ｎ（＝１〜Ｎ）と代表ベクトルｆｎとを対応付けたコードブックを記憶する（図２のコードブック記憶部１０１参照）。
代表識別値ｎ：  代表ベクトルｆｎ
１：  ｆ１＝（ｆ１１，ｆ１２，・・・，ｆ１Ｄ）
２：  ｆ２＝（ｆ２１，ｆ２２，・・・，ｆ２Ｄ）
３：  ｆ３＝（ｆ３１，ｆ３２，・・・，ｆ３Ｄ）
・・・
Ｎ：  ｆＮ＝（ｆＮ１，ｆＮ２，・・・，ｆＮＤ）
【００３５】
ベクトル量子化部１１１は、登録ベクトルｆを入力する。ここで、ベクトルは、高次元の特徴ベクトルであって、例えば１２８次元（Ｄ＝１２８）で表されるものであってもよい。
登録ベクトルｆ：  ｆ＝（ｆ１，ｆ２，・・・，ｆＤ）
そして、ベクトル量子化部１１１は、登録ベクトルｆを、コードブック記憶部１０１に記憶されたコードブックを用いて、代表識別値ｎ（＝１〜Ｎ、ｎ：整数値）に量子化する（図２のベクトル量子化部１１１参照）。
ｎ＝ｑ（ｆ）＝ａｒｇｍｉｎｎ||ｆ−ｆｎ||２
（登録ベクトルｆの量子化関数ｑ（ｆ）は、||ｆ−ｆｎ||２が最小となるｎを導出
する）
ｑ：ＲＤ->Ｎ（量子化を意味する）
ｆｎ：代表ベクトル
【００３６】
残差ベクトル導出部１１２は、登録ベクトルｆから代表ベクトルｆｎを引いた残差ベクトルｆｒを導出する（図２の残差ベクトル導出部１１２参照）。尚、図３（ａ）によれば、クラスタＦ毎に、多数のベクトルｆに対する代表ベクトルｆｎが表されている。また、ｆとｆｎとの差分となる残差ベクトルもｆｒも表されている。
ｆｒ＝ｆ−ｆｎ（＝ｑ（ｆ））：残差ベクトル
【００３７】
残差ベクトル分割部１１３は、残差ベクトルをＴ個の残差部分ベクトルｆｒ1, ｆｒ2, ..., ｆｒTに分割する（図２の残差ベクトル分割部１１３参照）。ここで、例えば１つの残差部分ベクトルを、１６次元にしたとする。この場合、残差ベクトルは、８個（Ｔ＝Ｄ／Ｄ'＝１２８／１６）の残差部分ベクトルに分割される。
ｆｒ１＝（ｆｒ１，１          ，ｆｒ１，２    ，・・・，ｆｒ１，Ｄ'）
ｆｒ２＝（ｆｒ２，Ｄ'+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]に保持する（図４の残差ベクトル距離算出部１２４参照）。Ｌｐ距離とは、高次元空間におけるベクトル距離を算出するために、ミンコフスキー距離として知られたものである。Ｌｐ距離は、以下のように定義される。多次元空間の点ＸIを以下のように表す。
ＸI＝(xi1, xi2, ・・・, xiD)T    i＝1,2,3,・・・,n
このとき、多次元空間上の２点ＸIとＸKとのＬｐ距離は、次元数D及びパラメータpを用いて、以下のように表す。
Ｌｐ(I,K)＝（Σj=1D|ｘij−ｘkj|p）1/p
【００４９】
登録ベクトル距離算出部１２５は、登録ベクトルの登録情報である残差識別値ｌｔ（１≦ｔ≦Ｔ）を基に、テーブルＤ[t][l]を参照することで、クエリベクトルと登録ベクトルの近似距離を、距離の重み付き和ｄ（＝Σt=1Tｗt・Ｄ[t][lｔ]）として算出する（図４の登録ベクトル距離算出部１２５参照）。
【００５０】
検索判定部１２６は、距離の重み付き和ｄが、所定閾値以下となる登録ベクトルを、検索結果として出力する（図４の検索判定部１２６参照）。この検索結果として、複数の登録ベクトルが導出されてもよい。
【００５１】
既存技術によれば、特徴ベクトルを量子化し、その量子化ベクトルの残差ベクトルに識別値を割り当てている。しかしながら、残差符号化のための残差コードブックが、特徴ベクトルで同一であったために、検索精度が低くなってしまう。これに対し、図１〜４で前述した検索装置によれば、クラスタ毎にコードブックを変更することによって、高次元ベクトルを高精度に検索することができる。即ち、クラスタ毎の残差ベクトルの分布に基づいてＭ個のコードブックを最適化することによって、全てのクラスタの残差コードブックを生成することなく（Ｍ＝Ｎ×Ｔ）、単一の残差コードブックを用いるよりも（Ｍ＝１）、高精度に検索することができる。
【００５２】
前述したような検索装置１に対する登録部１１及び検索部１２に対して、本発明によれば、最適なＭ個の残差コードブックのみを生成する学習部１３に特徴がある。以下では、学習部１３について詳細に説明する。
【００５３】
［学習部］
図５は、本発明における学習部を含む検索装置の機能構成図である。
【００５４】
図５によれば、学習部１３は、学習ベクトルを入力する。学習部１３は、コードブック生成部１３１と、残差コードブック生成部１３２とを有する。
【００５５】
コードブック生成部１３１は、学習ベクトルの集合を用いて、コードブック記憶部１０１に記憶すべきコードブックを生成する。
【００５６】
図６は、コードブック生成部の処理ステップを表すフローチャートである。
【００５７】
（Ｓ６１）学習ベクトルの集合Ｆを、Ｎ個のクラスタにクラスタリングする。
Ｆ
-> Ｆ１，Ｆ２，・・・，ＦＮ
例えばk-means又はk-means++のようなクラスタリングアルゴリズムが用いられる。
（Ｓ６２）クラスタ毎に、代表ベクトルｆｎを導出する。
ｆ１，ｆ２，・・・，ｆＮ
（Ｓ６３）各代表ベクトルに、一意の代表識別値ｎ（＝１〜Ｎ）を割り当てたコードブックを生成する。が得られる。
残差ベクトル集合：Ｆｒｎ＝｛ｆ−ｆｎ|ｆ∈Ｆｎ｝
【００５８】
残差コードブック生成部１３２は、残差コードブック記憶部１０２に記憶すべき残差コードブック及び残差コードブック識別子テーブルＴ[n][t]を生成する。
【００５９】
本発明の特徴は、残差コードブック生成部１３２にあって、粗量子化における代表識別値ｎ（＝１〜Ｎ）に割り当てられた学習ベクトルｆと、それに対応する代表ベクトルｆｎとの間の残差ベクトルｆｒ（＝ｆ−ｆｎ）を、Ｔ個の残差部分ベクトルに分割し、ｔ番目の残差部分ベクトルの集合Ｒn,tをクラスタリングし、各クラスタから直積量子化のためのコードブックを作成する。
【００６０】
図７は、本発明における残差コードブック生成部の処理ステップを表すフローチャートである。図８は、残差コードブック生成部における処理内容の第１の説明図である。図９は、残差コードブック生成部における処理内容の第２の説明図である。以下では、図８及び９を参照しつつ、図７のフローチャートの処理内容が説明される。
【００６１】
（Ｓ７１）代表ベクトルｆｎと、当該代表ベクトルｆｎに属する学習ベクトルｆとの間の残差ベクトルｆｒ（＝ｆ−ｆｎ）を導出する（図８のＳ７１参照）。これによって、Ｎ個の残差クラスタを作成する。
【００６２】
（Ｓ７２）残差ベクトルｆｒを、Ｔ個の残差部分ベクトルｆｒｔに分割する（図８のＳ７２参照）。これによって、残差部分ベクトル集合Ｒn,t（１≦ｎ≦Ｎ，１≦ｔ≦Ｔ）を生成する。図８のＳ７２によれば、Ｎ×Ｔ個の残差部分ベクトル集合Ｒn,tが表されている。
【００６３】
（Ｓ７３）残差部分ベクトル集合Ｒn,tそれぞれについて、残差コードブック識別子テーブルＴ[n][t]に、いずれかのラベル値ｍ（ｍ＝1,2,..,M）を割り当てる。ここでは、ラベル値ｍを割り当てるために、以下の２つの方法がある。
［第１のラベル値割当方法］
残差コードブック識別子テーブルＴ[n][t]に、ランダムに、いずれかのラベル値ｍを割り当てる。
［第２のラベル値割当方法］
残差コードブック識別子テーブルＴ[n][t]に、残差コードブックによって導出したラベル値ｍを割り当てる。この方法については、図１０及び図１１を用いて後述する。
【００６４】
図９のＳ７３によれば、以下のようにランダムに、ラベル値ｍが割り当てられている。
Ｒ1,1：m=2
Ｒ1,2：m=7
Ｒ1,3：m=1
・・・
【００６５】
（Ｓ７４）ラベル値ｍそれぞれについて、当該ラベル値ｍが割り当てられた全ての残差部分ベクトル集合Ｒn,tを用いて、当該ｍ番目の残差コードブックを生成する。図８のＳ７４によれば、ラベル値m=1が割り当てられた全ての残差部分ベクトル集合Ｒn,tを用いて、当該1番目の残差コードブックが生成されている。
【００６６】
（Ｓ７５）残差部分ベクトル集合Ｒn,tそれぞれについて、Ｍ個の残差コードブックそれぞれで量子化した際の量子化誤差が最も小さくなるｍ'番目の残差コードブックを用いて残差コードブック識別子テーブルＴ[n][t]を更新する。図９のＳ７５によれば、残差部分ベクトル集合Ｒn,t毎に、残差コードブックの割り当てが更新されている。
【００６７】
そして、残差部分ベクトルｆｒｔそれぞれについて、Ｓ７４及びＳ７５の処理を、所定回数、繰り返す。これによって、Ｍ個の残差コードブックと、残差コードブックの割り当てとの両方が更新される。
【００６８】
最後に、Ｓ７３における［第２のラベル値割当方法］について説明する。
図１０は、本発明における第２のラベル値割当方法の処理ステップを表すフローチャートである。
図１１は、第２のラベル値割当方法の処理内容の説明図である。
【００６９】
（Ｓ７３１）残差部分ベクトル集合Ｒn,tの中から、任意にいずれか１つの残差部分ベクトル集合Ｒn,tを選択する。図１１のＳ７３１によれば、任意に１つの残差部分ベクトル集合Ｒn,tが選択されている。
【００７０】
（Ｓ７３２）選択された当該残差部分ベクトル集合Ｒn,t内の残差部分ベクトルをクラスタリングし、１つの残差コードブックを生成する。図１１のＳ７３２によれば、１つの残差部分ベクトル集合Ｒn,tから、１つの残差コードブックが生成されている。
【００７１】
（Ｓ７３３）残差部分ベクトル集合Ｒn,tそれぞれについて、既に作成された全ての残差コードブックそれぞれで量子化した際に、量子化誤差の総和が最小となる残差コードブック及び量子化誤差Ｄn,tを求める。
【００７２】
（Ｓ７３４）全ての残差部分ベクトル集合Ｒn,t（１≦ｎ≦Ｎ，１≦ｔ≦Ｔ）の中からＤn,tに比例する確率で１つの残差部分ベクトル集合を選択する。ここで、「比例する確率」とは、正規化確率を意味し、全ての残差部分ベクトル集合Ｒn,tにおける最小の量子化誤差Ｄn,tの総和ΣＤn,tに対する、当該残差部分ベクトル集合Ｒn,tの最小の量子化誤差Ｄn,tの割合である。
残差部分ベクトル集合毎：Ｄn,t／ΣＤn,t
即ち、確率Ｄn,t／ΣＤn,tで、残差部分ベクトル集合Ｒn,tが選択される。
【００７３】
そして、選択された残差部分ベクトル集合Ｒn,t内の残差部分ベクトルをクラスタリングすることで、１つの残差コードブックを生成する。
【００７４】
（Ｓ７３５）Ｍ個の残差コードブックが生成されるまで、Ｓ７３３及びＳ７３４を繰り返す。
【００７５】
（Ｓ７３６）残差部分ベクトル集合Ｒn,tそれぞれについて、Ｍ個の残差コードブックそれぞれで量子化した際に、量子化誤差が最小となる当該残差コードブックのラベル値ｍを、当該残差部分ベクトル集合Ｒn,tに割り当てる。
【００７６】
図１０及び図１１で前述したように、各残差部分ベクトル集合Ｒn,tに、当該残差コードブックのラベル値ｍが割り当てられる。その後、図７及び図９で前述したＳ７４及びＳ７５の処理が繰り返し実行される。
【００７７】
以上、詳細に説明したように、本発明の検索装置及びプログラムによれば、検索精度とメモリ量とのトレードオフを考慮して、少ないコードブックの情報量によって、高次元の特徴ベクトルの集合からクエリ特徴ベクトルに類似した特徴ベクトルを検索することができる。
【００７８】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００７９】
１  検索装置
１０１  コードブック記憶部
１０２  残差コードブック記憶部
１０３  転置インデックス記憶部
１１  登録部
１１１  ベクトル量子化部
１１２  残差ベクトル導出部
１１３  残差ベクトル分割部
１１４  残差部分ベクトル量子化部
１１５  転置インデックス生成部
１２  検索部
１２４  残差ベクトル距離算出部
１２５  登録ベクトル距離算出部
１２６  検索判定部
【図１】
0005637939.tif 000002
【図２】
0005637939.tif 000003
【図３】
0005637939.tif 000004
【図４】
0005637939.tif 000005
【図５】
0005637939.tif 000006
【図６】
0005637939.tif 000007
【図７】
0005637939.tif 000008
【図８】
0005637939.tif 000009
【図９】
0005637939.tif 000010
【図１０】
0005637939.tif 000011
【図１１】
0005637939.tif 000012