"粗量子化及び直積量子化を用いて符号化された高次元の登録ベクトルの集合からクエリベクトルに類似したベクトルを検索する検索装置であって、粗量子化における代表識別値n=1~Nに割り当てられた学習ベクトルfと、それに対応する代表ベクトルfnとの間の残差ベクトルfr=f-fnを、T個の残差部分ベクトルに分割し、t番目の残差部分ベクトルの集合Rntをクラスタリングし、各クラスタから直積量子化のためのコードブックを作成する残差コードブック生成手段を有することを特徴とする検索装置。前記残差コードブック生成手段は、残差コードブック及び残差コードブック識別子テーブルTntを生成するものであり、代表ベクトルfnと、当該代表ベクトルfnに属する学習ベクトルfとの間の残差ベクトルfr=f-fnを導出することによってN個の残差クラスタを作成する第1の機能と、前記残差ベクトルfrをT個の残差部分ベクトルに分割し、残差部分ベクトル集合Rnt1≦n≦N,1≦t≦Tを生成する第2の機能と、前記残差部分ベクトル集合Rntそれぞれについて、前記残差コードブック識別子テーブルTntに、いずれかのラベル値mm=12Mを割り当てる第3の機能と、前記ラベル値mそれぞれについて、当該ラベル値mが割り当てられた全ての残差部分ベクトル集合Rntを用いて、当該m番目の残差コードブックを生成する第4の機能と、前記残差部分ベクトル集合Rntそれぞれについて、M個の残差コードブックそれぞれで量子化した際の量子化誤差が最も小さくなるm番目の残差コードブックを用いて残差コードブック識別子テーブルTntを更新する第5の機能とを有し、第4及び第5の機能を繰り返し実行することを特徴とする請求項1に記載の検索装置。コードブックを生成するコードブック生成手段を更に有し、前記コードブック生成手段は、前記学習ベクトルの集合を、N個のクラスタにクラスタリングする第1の機能と、前記クラスタ毎に、代表ベクトルを導出する第2の機能と、各代表ベクトルに、一意の代表識別値n=1~Nを割り当てたコードブックを生成する第3の機能とを実行することを特徴とする請求項2に記載の検索装置。前記登録ベクトルfを量子化するために、代表識別値n=1~Nと代表ベクトルfnとを対応付けたコードブックを記憶するコードブック記憶手段と、前記登録ベクトルfを、前記コードブックを用いて、代表識別値nに量子化するベクトル量子化手段と、前記登録ベクトルfから代表ベクトルfnを引いた残差ベクトルfrを導出する残差ベクトル導出手段と、前記残差ベクトルをT個の残差部分ベクトルfr1fr2frTに分割する残差ベクトル分割手段と、各残差部分ベクトルfrtを更に量子化するために、残差識別値l=1~Lと残差部分代表ベクトルflとを対応付けた残差コードブックをM個記憶すると共に、前記代表識別値nに対応付けられた登録ベクトルfの残差部分ベクトルfrtが、前記M個の残差コードブックのどれで量子化すべきかを示す残差コードブック識別子テーブルTntを記憶する残差コードブック記憶手段と、前記残差部分ベクトルfrtを、Tnt番目の前記残差コードブックで量子化する残差部分ベクトル量子化手段と、前記登録ベクトルfの代表識別値n毎に、複数の残差部分ベクトルfrtの残差識別値lt1≦t≦Tの集合と、登録ベクトルfに関する付加情報とを、各登録ベクトルfの登録情報として登録した転置インデックスを生成する転置インデックス生成手段と、前記転置インデックスを、登録ベクトルの集合として記憶する転置インデックス記憶手段とを有することを特徴とする請求項3に記載の検索装置。前記残差コードブック生成手段における第3の機能について、前記残差コードブック識別子テーブルTntに、ランダムに、いずれかのラベル値mm=12Mを割り当てることを特徴とする請求項3又は4に記載の検索装置。前記残差コードブック生成手段における第3の機能について、前記残差部分ベクトル集合Rntの中から、ランダムにいずれか1つの残差部分ベクトル集合Rntを選択する第31の機能と、選択された当該残差部分ベクトル集合Rnt内の残差部分ベクトルをクラスタリングし、1つの残差コードブックを生成する第32の機能と、前記残差部分ベクトル集合Rntそれぞれについて、既に作成された全ての残差コードブックそれぞれで量子化した際に、量子化誤差の総和が最小となる残差コードブック及び量子化誤差Dntを求める第33の機能と、全ての残差部分ベクトル集合Rnt1≦n≦N,1≦t≦Tの中から前記Dntに比例する確率で1つの残差部分ベクトル集合を選択し、その残差部分ベクトル集合内の残差部分ベクトルをクラスタリングすることで、1つの残差コードブックを生成する第34の機能と、M個の残差コードブックが生成されるまで、第33及び第34の機能を繰り返す第35の機能と、前記残差部分ベクトル集合Rntそれぞれについて、M個の残差コードブックそれぞれで量子化した際に、量子化誤差が最小となる当該残差コードブックのラベル値mを、当該残差部分ベクトル集合Rntに割り当てる第36の機能とを有することを特徴とする請求項3又は4に記載の検索装置。前記転置インデックス記憶手段を用いて、クエリベクトルに類似したベクトルを検索するために、前記ベクトル量子化手段は、前記クエリベクトルfを、前記コードブックを用いて、代表識別値nに量子化し、前記残差ベクトル導出手段は、前記クエリベクトルfから代表ベクトルfnを引いたクエリ残差ベクトルfrを導出し、前記残差ベクトル分割手段は、前記クエリ残差ベクトルをT個のクエリ残差部分ベクトルに分割すると共に、前記クエリ残差部分ベクトルfrtと、前記残差コードブック識別子テーブルTntにより指定される残差コードブックの各残差代表ベクトルft,l1≦l≦LとのLp距離を算出し参照テーブルDtlに保持する残差ベクトル距離算出手段と、前記登録ベクトルの登録情報である残差識別値lt1≦t≦Tを基に、前記テーブルDtlを参照することで、クエリベクトルと登録ベクトルのLp距離の推定値を、参照テーブルの重み付き和d=Σt1TwtDtltとして算出する登録ベクトル距離算出手段と、前記距離の重み付き和dが、所定閾値以下となる登録ベクトルを、又は、距離の重み付き和dが小さいものから順に所定個数となる登録ベクトルを、検索結果として出力する検索判定手段とを有することを特徴とする請求項2から6のいずれか1項に記載の検索装置。前記登録ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであり、前記登録ベクトルの付加情報は、画像識別子、局所特徴領域のスケール、局所特徴領域の角度のいずれか1つを含むことを特徴とする請求項1から7のいずれか1項に記載の検索装置。粗量子化及び直積量子化を用いて符号化された高次元の登録ベクトルの集合からクエリベクトルに類似したベクトルを検索する装置に搭載されたコンピュータを機能させるプログラムであって、粗量子化における代表識別値n=1~Nに割り当てられた学習ベクトルfと、それに対応する代表ベクトルfnとの間の残差ベクトルfr=f-fnを、T個の残差部分ベクトルに分割し、t番目の残差部分ベクトルの集合Rntをクラスタリングし、各クラスタから直積量子化のためのコードブックを作成する残差コードブック生成手段としてコンピュータを機能させることを特徴とする検索プログラム。前記残差コードブック生成手段は、残差コードブック及び残差コードブック識別子テーブルTntを生成するものであり、代表ベクトルfnと、当該代表ベクトルfnに属する学習ベクトルfとの間の残差ベクトルfr=f-fnを導出することによってN個の残差クラスタを作成する第1の機能と、前記残差ベクトルfrをT個の残差部分ベクトルに分割し、残差部分ベクトル集合Rnt1≦n≦N,1≦t≦Tを生成する第2の機能と、前記残差部分ベクトル集合Rntそれぞれについて、前記残差コードブック識別子テーブルTntに、いずれかのラベル値mm=12Mを割り当てる第3の機能と、前記ラベル値mそれぞれについて、当該ラベル値mが割り当てられた全ての残差部分ベクトル集合Rntを用いて、当該m番目の残差コードブックを生成する第4の機能と、前記残差部分ベクトル集合Rntそれぞれについて、M個の残差コードブックそれぞれで量子化した際の量子化誤差が最も小さくなるm番目の残差コードブックを用いて残差コードブック識別子テーブルTntを更新する第5の機能とを有し、第4及び第5の機能を繰り返し実行するようにコンピュータを機能させることを特徴とする請求項9に記載の検索プログラム。コードブックを生成するコードブック生成手段を更に有し、前記コードブック生成手段は、前記学習ベクトルの集合を、N個のクラスタにクラスタリングする第1の機能と、前記クラスタ毎に、代表ベクトルを導出する第2の機能と、各代表ベクトルに、一意の代表識別値n=1~Nを割り当てたコードブックを生成する第3の機能とを実行するようにコンピュータを機能させることを特徴とする請求項10に記載の検索プログラム。前記登録ベクトルfを量子化するために、代表識別値n=1~Nと代表ベクトルfnとを対応付けたコードブックを記憶するコードブック記憶手段と、前記登録ベクトルfを、前記コードブックを用いて、代表識別値nに量子化するベクトル量子化手段と、前記登録ベクトルfから代表ベクトルfnを引いた残差ベクトルfrを導出する残差ベクトル導出手段と、前記残差ベクトルをT個の残差部分ベクトルfr1fr2frTに分割する残差ベクトル分割手段と、各残差部分ベクトルfrtを更に量子化するために、残差識別値l=1~Lと残差部分代表ベクトルflとを対応付けた残差コードブックをM個記憶すると共に、前記代表識別値nに対応付けられた登録ベクトルfの残差部分ベクトルfrtが、前記M個の残差コードブックのどれで量子化すべきかを示す残差コードブック識別子テーブルTntを記憶する残差コードブック記憶手段と、前記残差部分ベクトルfrtを、Tnt番目の前記残差コードブックで量子化する残差部分ベクトル量子化手段と、前記登録ベクトルfの代表識別値n毎に、複数の残差部分ベクトルfrtの残差識別値lt1≦t≦Tの集合と、登録ベクトルfに関する付加情報とを、各登録ベクトルfの登録情報として登録した転置インデックスを生成する転置インデックス生成手段と、前記転置インデックスを、登録ベクトルの集合として記憶する転置インデックス記憶手段としてコンピュータを更に機能させることを特徴とする請求項11に記載の検索プログラム。前記残差コードブック生成手段における第3の機能について、前記残差コードブック識別子テーブルTntに、ランダムに、いずれかのラベル値mm=12Mを割り当てるようにコンピュータを機能させることを特徴とする請求項11又は12に記載の検索プログラム。前記残差コードブック生成手段における第3の機能について、前記残差部分ベクトル集合Rntの中から、ランダムにいずれか1つの残差部分ベクトル集合Rntを選択する第31の機能と、選択された当該残差部分ベクトル集合Rnt内の残差部分ベクトルをクラスタリングし、1つの残差コードブックを生成する第32の機能と、前記残差部分ベクトル集合Rntそれぞれについて、既に作成された全ての残差コードブックそれぞれで量子化した際に、量子化誤差の総和が最小となる残差コードブック及び量子化誤差Dntを求める第33の機能と、全ての残差部分ベクトル集合Rnt1≦n≦N,1≦t≦Tの中から前記Dntに比例する確率で1つの残差部分ベクトル集合を選択し、その残差部分ベクトル集合内の残差部分ベクトルをクラスタリングすることで、1つの残差コードブックを生成する第34の機能と、M個の残差コードブックが生成されるまで、第33及び第34の機能を繰り返す第35の機能と、前記残差部分ベクトル集合Rntそれぞれについて、M個の残差コードブックそれぞれで量子化した際に、量子化誤差が最小となる当該残差コードブックのラベル値mを、当該残差部分ベクトル集合Rntに割り当てる第36の機能としてコンピュータを更に機能させることを特徴とする請求項11又は12に記載の検索プログラム。前記転置インデックス記憶手段を用いて、クエリベクトルに類似したベクトルを検索するために、前記ベクトル量子化手段は、前記クエリベクトルfを、前記コードブックを用いて、代表識別値nに量子化し、前記残差ベクトル導出手段は、前記クエリベクトルfから代表ベクトルfnを引いたクエリ残差ベクトルfrを導出し、前記残差ベクトル分割手段は、前記クエリ残差ベクトルをT個のクエリ残差部分ベクトルに分割すると共に、前記クエリ残差部分ベクトルfrtと、前記残差コードブック識別子テーブルTntにより指定される残差コードブックの各残差代表ベクトルft,l1≦l≦LとのLp距離を算出し参照テーブルDtlに保持する残差ベクトル距離算出手段と、前記登録ベクトルの登録情報である残差識別値lt1≦t≦Tを基に、前記テーブルDtlを参照することで、クエリベクトルと登録ベクトルのLp距離の推定値を、参照テーブルの重み付き和d=Σt1TwtDtltとして算出する登録ベクトル距離算出手段と、前記距離の重み付き和dが、所定閾値以下となる登録ベクトルを、又は、距離の重み付き和dが小さいものから順に所定個数となる登録ベクトルを、検索結果として出力する検索判定手段としてコンピュータを更に機能させることを特徴とする請求項9から14のいずれか1項に記載の検索プログラム。前記登録ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであり、前記登録ベクトルの付加情報は、画像識別子、局所特徴領域のスケール、局所特徴領域の角度のいずれか1つを含むようにコンピュータを機能させることを特徴とする請求項9から15のいずれか1項に記載の検索プログラム。しかしながら、非特許文献2に記載された技術によれば、残差ベクトルを単一のコードブックで量子化しているために、近似最近傍検索の精度が悪くなるという問題があった。これは、最初に荒く量子化した際に、残差ベクトルの分布が、クラスタ毎に大きく異なるためである。一方で、この残差ベクトルのコードブックを、クラスタ毎に生成してしまうと、コードブックの情報量メモリ量が非常に膨大となってしまう。そこで、本発明は、検索精度とメモリ量とのトレードオフを考慮して、少ないコードブックの情報量によって、高次元の特徴ベクトルの集合からクエリ特徴ベクトルに類似した特徴ベクトルを検索することができる検索装置及びプログラムを提供することを目的とする。本発明によれば、粗量子化及び直積量子化を用いて符号化された高次元の登録ベクトルの集合からクエリベクトルに類似したベクトルを検索する検索装置であって、粗量子化における代表識別値n=1~Nに割り当てられた学習ベクトルfと、それに対応する代表ベクトルfnとの間の残差ベクトルfr=f-fnを、T個の残差部分ベクトルに分割し、t番目の残差部分ベクトルの集合Rntをクラスタリングし、各クラスタから直積量子化のためのコードブックを作成する残差コードブック生成手段を有することを特徴とする。本発明の検索装置における他の実施形態によれば、残差コードブック生成手段は、残差コードブック及び残差コードブック識別子テーブルTntを生成するものであり、代表ベクトルfnと、当該代表ベクトルfnに属する学習ベクトルfとの間の残差ベクトルfr=f-fnを導出することによってN個の残差クラスタを作成する第1の機能と、残差ベクトルfrをT個の残差部分ベクトルに分割し、残差部分ベクトル集合Rnt1≦n≦N,1≦t≦Tを生成する第2の機能と、残差部分ベクトル集合Rntそれぞれについて、残差コードブック識別子テーブルTntに、いずれかのラベル値mm=12Mを割り当てる第3の機能と、ラベル値mそれぞれについて、当該ラベル値mが割り当てられた全ての残差部分ベクトル集合Rntを用いて、当該m番目の残差コードブックを生成する第4の機能と、残差部分ベクトル集合Rntそれぞれについて、M個の残差コードブックそれぞれで量子化した際の量子化誤差が最も小さくなるm番目の残差コードブックを用いて残差コードブック識別子テーブルTntを更新する第5の機能とを有し、第4及び第5の機能を繰り返し実行することも好ましい。本発明の検索装置における他の実施形態によれば、コードブックを生成するコードブック生成手段を更に有し、コードブック生成手段は、学習ベクトルの集合を、N個のクラスタにクラスタリングする第1の機能と、クラスタ毎に、代表ベクトルを導出する第2の機能と、各代表ベクトルに、一意の代表識別値n=1~Nを割り当てたコードブックを生成する第3の機能とを実行することも好ましい。本発明の検索装置における他の実施形態によれば、登録ベクトルfを量子化するために、代表識別値n=1~Nと代表ベクトルfnとを対応付けたコードブックを記憶するコードブック記憶手段と、登録ベクトルfを、コードブックを用いて、代表識別値nに量子化するベクトル量子化手段と、登録ベクトルfから代表ベクトルfnを引いた残差ベクトルfrを導出する残差ベクトル導出手段と、残差ベクトルをT個の残差部分ベクトルfr1fr2frTに分割する残差ベクトル分割手段と、各残差部分ベクトルfrtを更に量子化するために、残差識別値l=1~Lと残差部分代表ベクトルflとを対応付けた残差コードブックをM個記憶すると共に、代表識別値nに対応付けられた登録ベクトルfの残差部分ベクトルfrtが、M個の残差コードブックのどれで量子化すべきかを示す残差コードブック識別子テーブルTntを記憶する残差コードブック記憶手段と、残差部分ベクトルfrtを、Tnt番目の残差コードブックで量子化する残差部分ベクトル量子化手段と、登録ベクトルfの代表識別値n毎に、複数の残差部分ベクトルfrtの残差識別値lt1≦t≦Tの集合と、登録ベクトルfに関する付加情報とを、各登録ベクトルfの登録情報として登録した転置インデックスを生成する転置インデックス生成手段と、転置インデックスを、登録ベクトルの集合として記憶する転置インデックス記憶手段とを有することも好ましい。本発明の検索装置における他の実施形態によれば、残差コードブック生成手段における第3の機能について、残差コードブック識別子テーブルTntに、ランダムに、いずれかのラベル値mm=12Mを割り当てることも好ましい。本発明の検索装置における他の実施形態によれば、残差コードブック生成手段における第3の機能について、残差部分ベクトル集合Rntの中から、ランダムにいずれか1つの残差部分ベクトル集合Rntを選択する第31の機能と、選択された当該残差部分ベクトル集合Rnt内の残差部分ベクトルをクラスタリングし、1つの残差コードブックを生成する第32の機能と、残差部分ベクトル集合Rntそれぞれについて、既に作成された全ての残差コードブックそれぞれで量子化した際に、量子化誤差の総和が最小となる残差コードブック及び量子化誤差Dntを求める第33の機能と、全ての残差部分ベクトル集合Rnt1≦n≦N,1≦t≦Tの中からDntに比例する確率で1つの残差部分ベクトル集合を選択し、その残差部分ベクトル集合内の残差部分ベクトルをクラスタリングすることで、1つの残差コードブックを生成する第34の機能と、M個の残差コードブックが生成されるまで、第33及び第34の機能を繰り返す第35の機能と、残差部分ベクトル集合Rntそれぞれについて、M個の残差コードブックそれぞれで量子化した際に、量子化誤差が最小となる当該残差コードブックのラベル値mを、当該残差部分ベクトル集合Rntに割り当てる第36の機能とを有することも好ましい。本発明の検索装置における他の実施形態によれば、転置インデックス記憶手段を用いて、クエリベクトルに類似したベクトルを検索するために、ベクトル量子化手段は、クエリベクトルfを、コードブックを用いて、代表識別値nに量子化し、残差ベクトル導出手段は、クエリベクトルfから代表ベクトルfnを引いたクエリ残差ベクトルfrを導出し、残差ベクトル分割手段は、クエリ残差ベクトルをT個のクエリ残差部分ベクトルに分割すると共に、クエリ残差部分ベクトルfrtと、残差コードブック識別子テーブルTntにより指定される残差コードブックの各残差代表ベクトルft,l1≦l≦LとのLp距離を算出し参照テーブルDtlに保持する残差ベクトル距離算出手段と、登録ベクトルの登録情報である残差識別値lt1≦t≦Tを基に、テーブルDtlを参照することで、クエリベクトルと登録ベクトルのLp距離の推定値を、参照テーブルの重み付き和d=Σt1TwtDtltとして算出する登録ベクトル距離算出手段と、距離の重み付き和dが、所定閾値以下となる登録ベクトルを、又は、距離の重み付き和dが小さいものから順に所定個数となる登録ベクトルを、検索結果として出力する検索判定手段とを有することも好ましい。本発明の検索装置における他の実施形態によれば、登録ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであり、登録ベクトルの付加情報は、画像識別子、局所特徴領域のスケール、局所特徴領域の角度のいずれか1つを含むことも好ましい。本発明によれば、粗量子化及び直積量子化を用いて符号化された高次元の登録ベクトルの集合からクエリベクトルに類似したベクトルを検索する装置に搭載されたコンピュータを機能させるプログラムであって、粗量子化における代表識別値n=1~Nに割り当てられた学習ベクトルfと、それに対応する代表ベクトルfnとの間の残差ベクトルfr=f-fnを、T個の残差部分ベクトルに分割し、t番目の残差部分ベクトルの集合Rntをクラスタリングし、各クラスタから直積量子化のためのコードブックを作成する残差コードブック生成手段としてコンピュータを機能させることを特徴とする。本発明の検索プログラムにおける他の実施形態によれば、残差コードブック生成手段は、残差コードブック及び残差コードブック識別子テーブルTntを生成するものであり、代表ベクトルfnと、当該代表ベクトルfnに属する学習ベクトルfとの間の残差ベクトルfr=f-fnを導出することによってN個の残差クラスタを作成する第1の機能と、残差ベクトルfrをT個の残差部分ベクトルに分割し、残差部分ベクトル集合Rnt1≦n≦N,1≦t≦Tを生成する第2の機能と、残差部分ベクトル集合Rntそれぞれについて、残差コードブック識別子テーブルTntに、いずれかのラベル値mm=12Mを割り当てる第3の機能と、ラベル値mそれぞれについて、当該ラベル値mが割り当てられた全ての残差部分ベクトル集合Rntを用いて、当該m番目の残差コードブックを生成する第4の機能と、残差部分ベクトル集合Rntそれぞれについて、M個の残差コードブックそれぞれで量子化した際の量子化誤差が最も小さくなるm番目の残差コードブックを用いて残差コードブック識別子テーブルTntを更新する第5の機能とを有し、第4及び第5の機能を繰り返し実行するようにコンピュータを機能させることも好ましい。本発明の検索プログラムにおける他の実施形態によれば、コードブックを生成するコードブック生成手段を更に有し、コードブック生成手段は、学習ベクトルの集合を、N個のクラスタにクラスタリングする第1の機能と、クラスタ毎に、代表ベクトルを導出する第2の機能と、各代表ベクトルに、一意の代表識別値n=1~Nを割り当てたコードブックを生成する第3の機能とを実行するようにコンピュータを機能させることも好ましい。本発明の検索プログラムにおける他の実施形態によれば、登録ベクトルfを量子化するために、代表識別値n=1~Nと代表ベクトルfnとを対応付けたコードブックを記憶するコードブック記憶手段と、登録ベクトルfを、コードブックを用いて、代表識別値nに量子化するベクトル量子化手段と、登録ベクトルfから代表ベクトルfnを引いた残差ベクトルfrを導出する残差ベクトル導出手段と、残差ベクトルをT個の残差部分ベクトルfr1fr2frTに分割する残差ベクトル分割手段と、各残差部分ベクトルfrtを更に量子化するために、残差識別値l=1~Lと残差部分代表ベクトルflとを対応付けた残差コードブックをM個記憶すると共に、代表識別値nに対応付けられた登録ベクトルfの残差部分ベクトルfrtが、M個の残差コードブックのどれで量子化すべきかを示す残差コードブック識別子テーブルTntを記憶する残差コードブック記憶手段と、残差部分ベクトルfrtを、Tnt番目の残差コードブックで量子化する残差部分ベクトル量子化手段と、登録ベクトルfの代表識別値n毎に、複数の残差部分ベクトルfrtの残差識別値lt1≦t≦Tの集合と、登録ベクトルfに関する付加情報とを、各登録ベクトルfの登録情報として登録した転置インデックスを生成する転置インデックス生成手段と、転置インデックスを、登録ベクトルの集合として記憶する転置インデックス記憶手段としてコンピュータを更に機能させることも好ましい。本発明の検索プログラムにおける他の実施形態によれば、残差コードブック生成手段における第3の機能について、残差コードブック識別子テーブルTntに、ランダムに、いずれかのラベル値mm=12Mを割り当てるようにコンピュータを機能させることも好ましい。本発明の検索プログラムにおける他の実施形態によれば、残差コードブック生成手段における第3の機能について、残差部分ベクトル集合Rntの中から、ランダムにいずれか1つの残差部分ベクトル集合Rntを選択する第31の機能と、選択された当該残差部分ベクトル集合Rnt内の残差部分ベクトルをクラスタリングし、1つの残差コードブックを生成する第32の機能と、残差部分ベクトル集合Rntそれぞれについて、既に作成された全ての残差コードブックそれぞれで量子化した際に、量子化誤差の総和が最小となる残差コードブック及び量子化誤差Dntを求める第33の機能と、全ての残差部分ベクトル集合Rnt1≦n≦N,1≦t≦Tの中からDntに比例する確率で1つの残差部分ベクトル集合を選択し、その残差部分ベクトル集合内の残差部分ベクトルをクラスタリングすることで、1つの残差コードブックを生成する第34の機能と、M個の残差コードブックが生成されるまで、第33及び第34の機能を繰り返す第35の機能と、残差部分ベクトル集合Rntそれぞれについて、M個の残差コードブックそれぞれで量子化した際に、量子化誤差が最小となる当該残差コードブックのラベル値mを、当該残差部分ベクトル集合Rntに割り当てる第36の機能としてコンピュータを更に機能させることも好ましい。本発明の検索プログラムにおける他の実施形態によれば、転置インデックス記憶手段を用いて、クエリベクトルに類似したベクトルを検索するために、ベクトル量子化手段は、クエリベクトルfを、コードブックを用いて、代表識別値nに量子化し、残差ベクトル導出手段は、クエリベクトルfから代表ベクトルfnを引いたクエリ残差ベクトルfrを導出し、残差ベクトル分割手段は、クエリ残差ベクトルをT個のクエリ残差部分ベクトルに分割すると共に、クエリ残差部分ベクトルfrtと、残差コードブック識別子テーブルTntにより指定される残差コードブックの各残差代表ベクトルft,l1≦l≦LとのLp距離を算出し参照テーブルDtlに保持する残差ベクトル距離算出手段と、登録ベクトルの登録情報である残差識別値lt1≦t≦Tを基に、テーブルDtlを参照することで、クエリベクトルと登録ベクトルのLp距離の推定値を、参照テーブルの重み付き和d=Σt1TwtDtltとして算出する登録ベクトル距離算出手段と、距離の重み付き和dが、所定閾値以下となる登録ベクトルを、又は、距離の重み付き和dが小さいものから順に所定個数となる登録ベクトルを、検索結果として出力する検索判定手段としてコンピュータを更に機能させることも好ましい。本発明の検索プログラムにおける他の実施形態によれば、登録ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであり、登録ベクトルの付加情報は、画像識別子、局所特徴領域のスケール、局所特徴領域の角度のいずれか1つを含むようにコンピュータを機能させることも好ましい。本発明の検索装置及びプログラムによれば、検索精度とメモリ量とのトレードオフを考慮して、少ないコードブックの情報量によって、高次元の特徴ベクトルの集合からクエリ特徴ベクトルに類似した特徴ベクトルを検索することができる。以下、本発明の実施の形態について、図面を用いて詳細に説明する。図1は、検索装置の機能構成図である。本発明が対象とする検索装置1は、粗量子化及び直積量子化を用いて符号化された高次元の登録ベクトルの集合からクエリベクトルに類似したベクトルを検索する。検索装置1は、コードブック記憶部101と、残差コードブック記憶部102と、転置インデックス記憶部103と、登録部11と、検索部12とを有する。これら機能構成部は、装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。以下では、[登録部][検索部]の順に説明すると共に、その中で記憶部101~103について説明する。[登録部]図2は、登録部における処理内容の説明図である。以下では、図2を参照しつつ、図1の登録部11の各機能が説明される。また、図3は、クラスタFに含まれるベクトルを代表ベクトルfnに対応付けた説明図である。登録部11は、ベクトル量子化部111と、残差ベクトル導出部112と、残差ベクトル分割部113と、残差部分ベクトル量子化部114と、転置インデックス生成部115とを有する。コードブック記憶部101は、登録ベクトルfを量子化するために、代表識別値n=1~Nと代表ベクトルfnとを対応付けたコードブックを記憶する図2のコードブック記憶部101参照。代表識別値n:代表ベクトルfn1:f1=f11,f12,,f1D2:f2=f21,f22,,f2D3:f3=f31,f32,,f3DN:fN=fN1,fN2,,fNDベクトル量子化部111は、登録ベクトルfを入力する。ここで、ベクトルは、高次元の特徴ベクトルであって、例えば128次元D=128で表されるものであってもよい。登録ベクトルf:f=f1,f2,,fDそして、ベクトル量子化部111は、登録ベクトルfを、コードブック記憶部101に記憶されたコードブックを用いて、代表識別値n=1~N、n:整数値に量子化する図2のベクトル量子化部111参照。n=qf=argminnf-fn2登録ベクトルfの量子化関数qfは、f-fn2が最小となるnを導出するq:RDN量子化を意味するfn:代表ベクトル残差ベクトル導出部112は、登録ベクトルfから代表ベクトルfnを引いた残差ベクトルfrを導出する図2の残差ベクトル導出部112参照。尚、図3aによれば、クラスタF毎に、多数のベクトルfに対する代表ベクトルfnが表されている。また、fとfnとの差分となる残差ベクトルもfrも表されている。fr=f-fn=qf:残差ベクトル残差ベクトル分割部113は、残差ベクトルをT個の残差部分ベクトルfr1fr2frTに分割する図2の残差ベクトル分割部113参照。ここで、例えば1つの残差部分ベクトルを、16次元にしたとする。この場合、残差ベクトルは、8個T=D/D=128/16の残差部分ベクトルに分割される。fr1=fr1,1,fr1,2,,fr1,Dfr2=fr2,D1,fr2,D2,,fr2,DDfrT=frT,D1,frT,D2,,frT,DD残差コードブック記憶部102は、各残差部分ベクトルfrtを更に量子化するために、残差識別値l=1~Lと残差部分代表ベクトルflとを対応付けた残差コードブックをM個記憶する図2の残差コードブック記憶部102及び図3b参照。ここで、本発明における最も特徴的な部分は、残差コードブックを、N×T個ではなく、M個しか記憶する必要が無いことにある。また、残差コードブック記憶部102は、代表識別値nに対応付けられた登録ベクトルfの残差部分ベクトルfrtが、M個の残差コードブックのどれで量子化すべきかを示す残差コードブック識別子テーブルTntも記憶する図2の残差コードブック識別子テーブル参照。ここで、Mは、1<<M<<N×Tの関係にある。M=1にすると、残差ベクトルの分布が、クラスタ毎に大きく異なるために、残差ベクトルを量子化する際の量子化誤差が増加し、結果的に近似最近傍検索の精度が悪くなる。一方で、M=N×Tにすると、コードブックの情報量メモリ量が非常に膨大となってしまう。そこで、本発明は、1<<M<<N×Tの関係にすることが重要となる。残差部分ベクトル量子化部114は、代表識別値n=qfとすると、残差部分ベクトルfrtをTnt番目の残差コードブックで量子化する。残差コードブック識別子テーブルTntには、Mが対応付けられている。量子化結果は、以下のように表される。lt=qrTntfrt転置インデックス生成部115は、登録ベクトルfの代表識別値n毎に、複数の残差部分ベクトルfrtの残差識別値lt1≦t≦Tの集合と、登録ベクトルfに関する付加情報メタデータとを、各登録ベクトルfの登録情報として登録した転置インデックスを生成する。転置インデックスとは、ベクトルを、識別値に置き換えたものである。これは、代表識別値n=1~N毎に作成された登録ベクトルのリストである。登録ベクトルのメタデータには、何が割り当てられてもよい。例えば、登録ベクトルが画像検索における画像特徴量である場合、登録ベクトルが所属する画像識別値を割り当てる。例えば画像の局所特徴領域から抽出された局所特徴ベクトルである場合、メタデータ登録ベクトルの付加情報は、画像識別子、局所特徴領域のスケール、局所特徴領域の角度のいずれか1つを含むことも好ましい。また、高精度に検索する場合、登録ベクトルそのものをメタデータに追加的に登録するものであってもよい。転置インデックス記憶部103は、転置インデックスを、登録ベクトルの集合として記憶する。[検索部]検索部12は、登録部11と同様に、ベクトル量子化部111と、残差ベクトル導出部112と、残差ベクトル分割部113とを有し、更に、残差ベクトル距離算出部124と、登録ベクトル距離算出部125と、検索判定部126とを有する。図4は、検索部における処理内容の説明図である。以下では、図4を参照しつつ、図1の検索部12の各機能が説明される。検索部12は、クエリベクトルfを入力する。クエリベクトルfは、登録ベクトルと同じ次元のベクトルである。そして、ベクトル量子化部111は、クエリベクトルfを、コードブック記憶部101に記憶されたコードブックを用いて、代表識別値n=1~N、n:整数値に量子化する。残差ベクトル導出部112は、クエリベクトルfから代表ベクトルfnを引いたクエリ残差ベクトルfrを導出する。残差ベクトル分割部113は、クエリ残差ベクトルをT個のクエリ残差部分ベクトルに分割する。残差ベクトル距離算出部124は、クエリ残差部分ベクトルfrtと、残差コードブック識別子テーブルTntにより指定される残差コードブックの各残差代表ベクトルft,l1≦l≦LとのLp距離を算出し、テーブルDtlに保持する図4の残差ベクトル距離算出部124参照。Lp距離とは、高次元空間におけるベクトル距離を算出するために、ミンコフスキー距離として知られたものである。Lp距離は、以下のように定義される。多次元空間の点XIを以下のように表す。XI=Ti=123nこのとき、多次元空間上の2点XIとXKとのLp距離は、次元数D及びパラメータpを用いて、以下のように表す。Lp=Σj1Dxij-xkjp1p登録ベクトル距離算出部125は、登録ベクトルの登録情報である残差識別値lt1≦t≦Tを基に、テーブルDtlを参照することで、クエリベクトルと登録ベクトルの近似距離を、距離の重み付き和d=Σt1TwtDtltとして算出する図4の登録ベクトル距離算出部125参照。検索判定部126は、距離の重み付き和dが、所定閾値以下となる登録ベクトルを、検索結果として出力する図4の検索判定部126参照。この検索結果として、複数の登録ベクトルが導出されてもよい。既存技術によれば、特徴ベクトルを量子化し、その量子化ベクトルの残差ベクトルに識別値を割り当てている。しかしながら、残差符号化のための残差コードブックが、特徴ベクトルで同一であったために、検索精度が低くなってしまう。これに対し、図1~4で前述した検索装置によれば、クラスタ毎にコードブックを変更することによって、高次元ベクトルを高精度に検索することができる。即ち、クラスタ毎の残差ベクトルの分布に基づいてM個のコードブックを最適化することによって、全てのクラスタの残差コードブックを生成することなくM=N×T、単一の残差コードブックを用いるよりもM=1、高精度に検索することができる。前述したような検索装置1に対する登録部11及び検索部12に対して、本発明によれば、最適なM個の残差コードブックのみを生成する学習部13に特徴がある。以下では、学習部13について詳細に説明する。[学習部]図5は、本発明における学習部を含む検索装置の機能構成図である。図5によれば、学習部13は、学習ベクトルを入力する。学習部13は、コードブック生成部131と、残差コードブック生成部132とを有する。コードブック生成部131は、学習ベクトルの集合を用いて、コードブック記憶部101に記憶すべきコードブックを生成する。図6は、コードブック生成部の処理ステップを表すフローチャートである。S61学習ベクトルの集合Fを、N個のクラスタにクラスタリングする。FF1,F2,,FN例えばkmeans又はkmeansのようなクラスタリングアルゴリズムが用いられる。S62クラスタ毎に、代表ベクトルfnを導出する。f1,f2,,fNS63各代表ベクトルに、一意の代表識別値n=1~Nを割り当てたコードブックを生成する。が得られる。残差ベクトル集合:Frn={f-fnf∈Fn}残差コードブック生成部132は、残差コードブック記憶部102に記憶すべき残差コードブック及び残差コードブック識別子テーブルTntを生成する。本発明の特徴は、残差コードブック生成部132にあって、粗量子化における代表識別値n=1~Nに割り当てられた学習ベクトルfと、それに対応する代表ベクトルfnとの間の残差ベクトルfr=f-fnを、T個の残差部分ベクトルに分割し、t番目の残差部分ベクトルの集合Rntをクラスタリングし、各クラスタから直積量子化のためのコードブックを作成する。図7は、本発明における残差コードブック生成部の処理ステップを表すフローチャートである。図8は、残差コードブック生成部における処理内容の第1の説明図である。図9は、残差コードブック生成部における処理内容の第2の説明図である。以下では、図8及び9を参照しつつ、図7のフローチャートの処理内容が説明される。S71代表ベクトルfnと、当該代表ベクトルfnに属する学習ベクトルfとの間の残差ベクトルfr=f-fnを導出する図8のS71参照。これによって、N個の残差クラスタを作成する。S72残差ベクトルfrを、T個の残差部分ベクトルfrtに分割する図8のS72参照。これによって、残差部分ベクトル集合Rnt1≦n≦N,1≦t≦Tを生成する。図8のS72によれば、N×T個の残差部分ベクトル集合Rntが表されている。S73残差部分ベクトル集合Rntそれぞれについて、残差コードブック識別子テーブルTntに、いずれかのラベル値mm=12Mを割り当てる。ここでは、ラベル値mを割り当てるために、以下の2つの方法がある。[第1のラベル値割当方法]残差コードブック識別子テーブルTntに、ランダムに、いずれかのラベル値mを割り当てる。[第2のラベル値割当方法]残差コードブック識別子テーブルTntに、残差コードブックによって導出したラベル値mを割り当てる。この方法については、図10及び図11を用いて後述する。図9のS73によれば、以下のようにランダムに、ラベル値mが割り当てられている。R11:m2R12:m7R13:m1S74ラベル値mそれぞれについて、当該ラベル値mが割り当てられた全ての残差部分ベクトル集合Rntを用いて、当該m番目の残差コードブックを生成する。図8のS74によれば、ラベル値m1が割り当てられた全ての残差部分ベクトル集合Rntを用いて、当該1番目の残差コードブックが生成されている。S75残差部分ベクトル集合Rntそれぞれについて、M個の残差コードブックそれぞれで量子化した際の量子化誤差が最も小さくなるm番目の残差コードブックを用いて残差コードブック識別子テーブルTntを更新する。図9のS75によれば、残差部分ベクトル集合Rnt毎に、残差コードブックの割り当てが更新されている。そして、残差部分ベクトルfrtそれぞれについて、S74及びS75の処理を、所定回数、繰り返す。これによって、M個の残差コードブックと、残差コードブックの割り当てとの両方が更新される。最後に、S73における[第2のラベル値割当方法]について説明する。図10は、本発明における第2のラベル値割当方法の処理ステップを表すフローチャートである。図11は、第2のラベル値割当方法の処理内容の説明図である。S731残差部分ベクトル集合Rntの中から、任意にいずれか1つの残差部分ベクトル集合Rntを選択する。図11のS731によれば、任意に1つの残差部分ベクトル集合Rntが選択されている。S732選択された当該残差部分ベクトル集合Rnt内の残差部分ベクトルをクラスタリングし、1つの残差コードブックを生成する。図11のS732によれば、1つの残差部分ベクトル集合Rntから、1つの残差コードブックが生成されている。S733残差部分ベクトル集合Rntそれぞれについて、既に作成された全ての残差コードブックそれぞれで量子化した際に、量子化誤差の総和が最小となる残差コードブック及び量子化誤差Dntを求める。S734全ての残差部分ベクトル集合Rnt1≦n≦N,1≦t≦Tの中からDntに比例する確率で1つの残差部分ベクトル集合を選択する。ここで、比例する確率とは、正規化確率を意味し、全ての残差部分ベクトル集合Rntにおける最小の量子化誤差Dntの総和ΣDntに対する、当該残差部分ベクトル集合Rntの最小の量子化誤差Dntの割合である。残差部分ベクトル集合毎:Dnt/ΣDnt即ち、確率Dnt/ΣDntで、残差部分ベクトル集合Rntが選択される。そして、選択された残差部分ベクトル集合Rnt内の残差部分ベクトルをクラスタリングすることで、1つの残差コードブックを生成する。S735M個の残差コードブックが生成されるまで、S733及びS734を繰り返す。S736残差部分ベクトル集合Rntそれぞれについて、M個の残差コードブックそれぞれで量子化した際に、量子化誤差が最小となる当該残差コードブックのラベル値mを、当該残差部分ベクトル集合Rntに割り当てる。図10及び図11で前述したように、各残差部分ベクトル集合Rntに、当該残差コードブックのラベル値mが割り当てられる。その後、図7及び図9で前述したS74及びS75の処理が繰り返し実行される。以上、詳細に説明したように、本発明の検索装置及びプログラムによれば、検索精度とメモリ量とのトレードオフを考慮して、少ないコードブックの情報量によって、高次元の特徴ベクトルの集合からクエリ特徴ベクトルに類似した特徴ベクトルを検索することができる。前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。"