(57)【要約】【課題】高次元の特徴ベクトルの集合からクエリ特徴ベクトルに類似した特徴ベクトルを検索する検索装置等を提供する。【解決手段】検索装置は、第１段（ｍ＝１）の１個の量子化器から順に、第ｍ段（２≦ｍ≦Ｍ）毎のＦ個の量子化器が多段に構成されており、第ｍ段毎にいずれか１つの量子化器ｆ（１≦ｆ≦Ｆ）が選択されると共に、第ｍ段における当該量子化器に入力されたベクトルｙmと当該量子化器から出力されたベクトルｙm〜との残差ベクトルｙm+1が、次の第ｍ＋１段の量子化器へ入力されるように構成された残差量子化手段を有する。また、クエリベクトルｘについて、残差コードブックの全ての代表ベクトルｄm,f,lとの内積（ｓm,f,l＝ｘ・ｄm,f,l）を算出し、識別子ｌｍ列に基づく内積の累積和から算出した近似ベクトルｙ〜に、所定条件下で類似（距離が近い）する登録ベクトルｙを探索する探索手段を有する。【選択図】図２
2013140494.tif 000002
【特許請求の範囲】
【請求項１】
符号化された高次元の登録ベクトルｙの集合からクエリベクトルｘに類似したベクトルを検索する検索装置であって、
第１段（ｍ＝１）の１個の量子化器から順に、第ｍ段（２≦ｍ≦Ｍ）毎のＦ個の量子化器が多段に構成されており、第ｍ段毎にいずれか１つの量子化器ｆ（１≦ｆ≦Ｆ）が選択されると共に、第ｍ段における当該量子化器に入力されたベクトルｙmと当該量子化器から出力されたベクトルｙm〜との残差ベクトルｙm+1が、次の第ｍ＋１段の量子化器へ入力されるように構成された残差量子化手段と、
前記量子化器（第ｍ段の第ｆ番目）毎に、識別子ｌ（１≦ｌ≦Ｌ）毎の代表ベクトルｄm,f,lを登録した残差コードブックＤm,fと、識別子ｌ毎のラベル値ｆ（１≦ｆ≦Ｆ）を登録した残差コードブック識別子テーブルＴm,fとを記憶した残差コードブック記憶手段と、
前記登録ベクトルｙ毎に、前記残差量子化手段から出力された第ｍ段毎に出力されたＭ個の識別子ｌｍ列を登録する登録データベースと、
前記クエリベクトルｘについて、前記残差コードブックの全ての代表ベクトルｄm,f,lとの内積（ｓm,f,l＝ｘ・ｄm,f,l）を算出し、前記識別子ｌｍ列に基づく前記内積の累積和から算出した近似ベクトルｙ〜に、所定条件下で類似（距離が近い）する登録ベクトルｙを探索する探索手段と
を有し、
前記残差量子化手段について、第ｍ段で選択される量子化器ｆは、前段の第ｍ−１段で選択された量子化器で用いられた前記残差コードブックＤの代表ベクトルの識別子に対応する前記残差コードブック識別子テーブルＴの前記ラベル値に応じて切り替えられる
ことを特徴とする検索装置。
【請求項２】
前記登録データベースは、識別子ｌｍ列に加えて、識別子ｌｍ列に基づく代表ベクトルｄm,fm,lmの累積和から算出された近似ベクトルｙ〜のＬ２ノルムを量子化した識別子lM+1を更に登録することを特徴とする請求項１に記載の検索装置。
【請求項３】
前記探索手段は、以下の式によってクエリベクトルｘと登録ベクトルｙとの近似距離を算出するものであり、所定条件下で類似する登録ベクトルｙを探索する
【数１】
2013140494.tif 000005
ことを特徴とする請求項１又は２に記載の検索装置。
【請求項４】
前記所定条件とは、ベクトルｙに対して、近似距離が所定の値以下となる登録ベクトルｙ、又は、近似距離が近い上位所定数となる登録ベクトルｙであることを特徴とする請求項３に記載の検索装置。
【請求項５】
学習ベクトルの集合を入力し、前記量子化器毎に、前記残差コードブックＤ及び前記残差コードブック識別子テーブルＴを生成する残差コードブック生成手段を有し、
前記残差コードブック生成手段は、
第１段の１個の量子化器について、
入力された学習ベクトルの集合を、Ｌ個のクラスタにクラスタリングし、クラスタ毎に代表ベクトルを付与し、各代表ベクトルに一意の代表識別子ｌ（＝１〜Ｌ）を割り当てた残差コードブックＤ1を生成し、
前記学習ベクトルの集合を各代表ベクトルで量子化し、代表識別子ｌ毎の各残差ベクトルの集合Ｒ1,lを生成し、
第２段のＦ個の量子化器について、
入力された残差ベクトルの集合Ｒ1,1〜Ｒ1,LをＦ個にクラスタリングし、各クラスタに属する残差ベクトルの集合を更にＬ個にクラスタリングし、Ｌ個の代表ベクトルを持つＦ個の残差コードブックＤ2,1〜Ｄ2,Fを生成し、
残差ベクトルの集合Ｒ1,lがｆ'番目のクラスタに属している場合に、第１段の量子化器の残差コードブック識別子テーブルの識別子ｌのラベル値に、ｆ'を登録し、
前記学習ベクトルの集合を各代表ベクトルで量子化し、代表識別子f,ｌ毎の各残差ベクトルの集合Ｒ2,f,lを生成する
ことを特徴とする請求項１から４のいずれか１項に記載の検索装置。
【請求項６】
前記残差コードブック生成手段は、
第ｍ段（２＜ｍ≦Ｍ）のＦ個の量子化器について、
入力された残差ベクトルの集合Ｒm-1,1,1〜Ｒ m-1,F,LをＦ個にクラスタリングし、各クラスタに属する残差ベクトルの集合を更にＬ個にクラスタリングし、Ｌ個の代表ベクトルを持つＦ個の残差コードブックＤm,1〜Ｄm,Fを生成し、
残差ベクトルの集合Ｒm,f,lがｆ'番目のクラスタに属している場合に、第ｍ−１段の量子化器の残差コードブック識別子テーブルの識別子f,lのラベル値に、ｆ'を登録し、
クラスタ毎に代表ベクトルを付与し、各代表ベクトルに一意の代表識別子ｌ（＝１〜Ｌ）を割り当てた残差コードブックＤm,fを生成し、
前記学習ベクトルの集合を各代表ベクトルで量子化し、代表識別子f,ｌ毎の各残差ベクトルの集合Ｒm,f,lを生成する
ことを特徴とする請求項５に記載の検索装置。
【請求項７】
前記登録ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであることを特徴とする請求項１から６のいずれか１項に記載の検索装置。
【請求項８】
符号化された高次元の登録ベクトルｙの集合からクエリベクトルｘに類似したベクトルを検索するべく、装置に搭載されたコンピュータを機能させる検索プログラムであって、
第１段（ｍ＝１）の１個の量子化器から順に、第ｍ段（２≦ｍ≦Ｍ）毎のＦ個の量子化器が多段に構成されており、第ｍ段毎にいずれか１つの量子化器ｆ（１≦ｆ≦Ｆ）が選択されると共に、第ｍ段における当該量子化器に入力されたベクトルｙmと当該量子化器から出力されたベクトルｙm〜との残差ベクトルｙm+1が、次の第ｍ＋１段の量子化器へ入力されるように構成された残差量子化手段と、
前記量子化器（第ｍ段の第ｆ番目）毎に、識別子ｌ（１≦ｌ≦Ｌ）毎の代表ベクトルｄm,f,lを登録した残差コードブックＤm,fと、識別子ｌ毎のラベル値ｆ（１≦ｆ≦Ｆ）を登録した残差コードブック識別子テーブルＴm,fとを記憶した残差コードブック記憶手段と、
前記登録ベクトルｙ毎に、前記残差量子化手段から出力された第ｍ段毎に出力されたＭ個の識別子ｌｍ列を登録する登録データベースと、
前記クエリベクトルｘについて、前記残差コードブックの全ての代表ベクトルｄm,f,lとの内積（ｓm,f,l＝ｘ・ｄm,f,l）を算出し、前記識別子ｌｍ列に基づく前記内積の累積和から算出した近似ベクトルｙ〜に、所定条件下で類似（距離が近い）する登録ベクトルｙを探索する探索手段と
してコンピュータを機能させ、
前記残差量子化手段について、第ｍ段で選択される量子化器ｆは、前段の第ｍ−１段で選択された量子化器で用いられた前記残差コードブックＤの代表ベクトルの識別子に対応する前記残差コードブック識別子テーブルＴの前記ラベル値に応じて切り替えられる
ようにコンピュータを機能させることを特徴とする検索プログラム。
【請求項９】
装置を用いて、符号化された高次元の登録ベクトルｙの集合からクエリベクトルｘに類似したベクトルを検索する検索方法であって、
第１段（ｍ＝１）の１個の量子化器から順に、第ｍ段（２≦ｍ≦Ｍ）毎のＦ個の量子化器が多段に構成されており、第ｍ段毎にいずれか１つの量子化器ｆ（１≦ｆ≦Ｆ）が選択されると共に、第ｍ段における当該量子化器に入力されたベクトルｙmと当該量子化器から出力されたベクトルｙm〜との残差ベクトルｙm+1が、次の第ｍ＋１段の量子化器へ入力されるように構成された残差量子化部と、
前記量子化器（第ｍ段の第ｆ番目）毎に、識別子ｌ（１≦ｌ≦Ｌ）毎の代表ベクトルｄm,f,lを登録した残差コードブックＤm,fと、識別子ｌ毎のラベル値ｆ（１≦ｆ≦Ｆ）を登録した残差コードブック識別子テーブルＴm,fとを記憶した残差コードブック記憶部と、
前記登録ベクトルｙ毎に、前記残差量子化手段から出力された第ｍ段毎に出力されたＭ個の識別子ｌｍ列と、識別子ｌｍ列に基づく代表ベクトルｄm,fm,lmの累積和から算出された近似ベクトルｙ〜のＬ２ノルムを量子化した識別子lM+1とを登録する登録データベースと
を有し、
前記クエリベクトルｘについて、前記残差コードブックの全ての代表ベクトルｄm,f,lとの内積（ｓm,f,l＝ｘ・ｄm,f,l）を算出し、前記識別子ｌｍ列に基づく前記内積の累積和から算出した近似ベクトルｙ〜に、所定条件下で類似（距離が近い）する登録ベクトルｙを探索し、
前記残差量子化部について、第ｍ段で選択される量子化器ｆは、前段の第ｍ−１段で選択された量子化器で用いられた前記残差コードブックＤの代表ベクトルの識別子に対応する前記残差コードブック識別子テーブルＴの前記ラベル値に応じて切り替えられる
ことを特徴とする検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索用データベースに登録された高次元の特徴ベクトルの集合から、クエリ特徴ベクトル（検索キー）に類似した特徴ベクトルを検索する最近傍探索技術に関する。
【背景技術】
【０００２】
最近傍検索技術として、木構造を用いた、R-tree(Rectangle-tree：矩形木)やANN(Approximate Nearest Neighbor)がある。R-treeは、階層的に入れ子になった最小外接矩形により空間を分割するものであって、主に低次元データ空間に対するインデックス化に用いられる。例えば、所定範囲内に存在するベクトルを検索することに適する。また、ANNは、所要程度の検索誤りを許容（近似最近傍検索）ことによって、kd-tree上での検索を高速化することができる。
【０００３】
更に、空間における特徴ベクトルの密度に応じてインデックスを生成する技術もある（例えば特許文献１参照）。この技術によれば、R-treeよりも高速に検索することができるが、特徴ベクトルが高次元になるほど、ほぼ全検索と同等の速度になるという問題がある（例えば「次元の呪い」と称される）。即ち、特徴ベクトルが高次元になるほど、最近傍探索の効率が重要となる。
【０００４】
これに対し、高次元の特徴ベクトルに対する検索技術として、ハッシュでデータを構造化（インデキシング）したLSH(Locality Sensitive Hashing)がある。LSHもANNと同様に検索誤りを許容した近似最近傍探索技術である。LSHによれば、類似するデータ同士のハッシュ値は一致し、非類似のデータ同士のハッシュ値は異なる可能性が高くなるように、ハッシュ値を出力するハッシュ関数が用いられる。尚、LSHについて、各バケットに登録される特徴ベクトルの数をなるべく均一にすることで、効率的に検索する技術も提案されている（例えば特許文献２参照）。
【０００５】
更に、ランダムに生成した木構造(kd-tree)のインデックスを複数利用することによって、検索の高精度化を実現する技術もある（例えば非特許文献１参照）。これは、高次元ベクトルを構成する各次元のうち分散の大きな次元を順に決定的に分割するkd-treeに対して、分割する次元や閾値に自由度を持たせたrandomized 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.
【非特許文献２】Y. Chen, T. Guen, and C. Wang、「ApproximateNearest Neighbor Search by Residual Vector Quantization」、Sensors、vol. 10, no. 12, 11259-11273.
【非特許文献３】Y. Weiss, A. Torralba, and R. Fergus、「SpectralHashing」, in Proc. of NIPS, 2008.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
非特許文献２に記載された技術によれば、多段階で量子化をする際に、各段階で常に単一の残差コードブックで量子化している。そのために、近似最近傍検索の精度が悪くなるという問題があった。これは、各段階の量子化器における残差（誤差）ベクトルは、各量子化器における量子化結果に応じて大きく変動するにもかかわらず、それら全ての残差ベクトルを、同一の後段の量子化コードブックで量子化することで符号化効率が低下するためである。一方で、この残差ベクトルのコードブックを、クラスタ毎に生成してしまうと、コードブックの情報量（メモリ量）が指数的に増加してしまうという問題があった。
【００１１】
そこで、本発明は、検索精度とメモリ量とのトレードオフを考慮して、高次元の特徴ベクトルの集合から、クエリ特徴ベクトルに類似した特徴ベクトルを検索することができる検索装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明によれば、符号化された高次元の登録ベクトルｙの集合からクエリベクトルｘに類似したベクトルを検索する検索装置であって、
第１段（ｍ＝１）の１個の量子化器から順に、第ｍ段（２≦ｍ≦Ｍ）毎のＦ個の量子化器が多段に構成されており、第ｍ段毎にいずれか１つの量子化器ｆ（１≦ｆ≦Ｆ）が選択されると共に、第ｍ段における当該量子化器に入力されたベクトルｙmと当該量子化器から出力されたベクトルｙm〜との残差ベクトルｙm+1が、次の第ｍ＋１段の量子化器へ入力されるように構成された残差量子化手段と、
量子化器（第ｍ段の第ｆ番目）毎に、識別子ｌ（１≦ｌ≦Ｌ）毎の代表ベクトルｄm,f,lを登録した残差コードブックＤm,fと、識別子ｌ毎のラベル値ｆ（１≦ｆ≦Ｆ）を登録した残差コードブック識別子テーブルＴm,fとを記憶した残差コードブック記憶手段と、
登録ベクトルｙ毎に、残差量子化手段から出力された第ｍ段毎に出力されたＭ個の識別子ｌｍ列を登録する登録データベースと、
クエリベクトルｘについて、残差コードブックの全ての代表ベクトルｄm,f,lとの内積（ｓm,f,l＝ｘ・ｄm,f,l）を算出し、識別子ｌｍ列に基づく内積の累積和から算出した近似ベクトルｙ〜に、所定条件下で類似（距離が近い）する登録ベクトルｙを探索する探索手段と
を有し、
残差量子化手段について、第ｍ段で選択される量子化器ｆは、前段の第ｍ−１段で選択された量子化器で用いられた残差コードブックＤの代表ベクトルの識別子に対応する残差コードブック識別子テーブルＴのラベル値に応じて切り替えられる
ことを特徴とする。
【００１３】
本発明の検索装置における他の実施形態によれば、登録データベースは、識別子ｌｍ列に加えて、識別子ｌｍ列に基づく代表ベクトルｄm,fm,lmの累積和から算出された近似ベクトルｙ〜のＬ２ノルムを量子化した識別子lM+1を更に登録することも好ましい。
【００１４】
本発明の検索装置における他の実施形態によれば、探索手段は、以下の式によってクエリベクトルｘと登録ベクトルｙとの近似距離を算出するものであり、所定条件下で類似する登録ベクトルｙを探索する
【数１】
2013140494.tif 000003
ことも好ましい。
【００１５】
本発明の検索装置における他の実施形態によれば、所定条件とは、ベクトルｙに対して、近似距離が所定の値以下となる登録ベクトルｙ、又は、近似距離が近い上位所定数となる登録ベクトルｙであることも好ましい。
【００１６】
本発明の検索装置における他の実施形態によれば、
学習ベクトルの集合を入力し、量子化器毎に、残差コードブックＤ及び残差コードブック識別子テーブルＴを生成する残差コードブック生成手段を有し、
残差コードブック生成手段は、
第１段の１個の量子化器について、
入力された学習ベクトルの集合を、Ｌ個のクラスタにクラスタリングし、クラスタ毎に代表ベクトルを付与し、各代表ベクトルに一意の代表識別子ｌ（＝１〜Ｌ）を割り当てた残差コードブックＤ1を生成し、
学習ベクトルの集合を各代表ベクトルで量子化し、代表識別子ｌ毎の各残差ベクトルの集合Ｒ1,lを生成し、
第２段のＦ個の量子化器について、
入力された残差ベクトルの集合Ｒ1,1〜Ｒ1,LをＦ個にクラスタリングし、各クラスタに属する残差ベクトルの集合を更にＬ個にクラスタリングし、Ｌ個の代表ベクトルを持つＦ個の残差コードブックＤ2,1〜Ｄ2,Fを生成し、
残差ベクトルの集合Ｒ1,lがｆ'番目のクラスタに属している場合に、第１段の量子化器の残差コードブック識別子テーブルの識別子ｌのラベル値に、ｆ'を登録し、
学習ベクトルの集合を各代表ベクトルで量子化し、代表識別子f,ｌ毎の各残差ベクトルの集合Ｒ2,f,lを生成することも好ましい。
【００１７】
本発明の検索装置における他の実施形態によれば、
残差コードブック生成手段は、
第ｍ段（２＜ｍ≦Ｍ）のＦ個の量子化器について、
入力された残差ベクトルの集合Ｒm-1,1,1〜Ｒ m-1,F,LをＦ個にクラスタリングし、各クラスタに属する残差ベクトルの集合を更にＬ個にクラスタリングし、Ｌ個の代表ベクトルを持つＦ個の残差コードブックＤm,1〜Ｄm,Fを生成し、
残差ベクトルの集合Ｒm,f,lがｆ'番目のクラスタに属している場合に、第ｍ−１段の量子化器の残差コードブック識別子テーブルの識別子f,lのラベル値に、ｆ'を登録し、
クラスタ毎に代表ベクトルを付与し、各代表ベクトルに一意の代表識別子ｌ（＝１〜Ｌ）を割り当てた残差コードブックＤm,fを生成し、
学習ベクトルの集合を各代表ベクトルで量子化し、代表識別子f,ｌ毎の各残差ベクトルの集合Ｒm,f,lを生成することも好ましい。
【００１８】
本発明の検索装置における他の実施形態によれば、登録ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであることも好ましい。
【００１９】
本発明によれば、符号化された高次元の登録ベクトルｙの集合からクエリベクトルｘに類似したベクトルを検索するべく、装置に搭載されたコンピュータを機能させる検索プログラムであって、
第１段（ｍ＝１）の１個の量子化器から順に、第ｍ段（２≦ｍ≦Ｍ）毎のＦ個の量子化器が多段に構成されており、第ｍ段毎にいずれか１つの量子化器ｆ（１≦ｆ≦Ｆ）が選択されると共に、第ｍ段における当該量子化器に入力されたベクトルｙmと当該量子化器から出力されたベクトルｙm〜との残差ベクトルｙm+1が、次の第ｍ＋１段の量子化器へ入力されるように構成された残差量子化手段と、
量子化器（第ｍ段の第ｆ番目）毎に、識別子ｌ（１≦ｌ≦Ｌ）毎の代表ベクトルｄm,f,lを登録した残差コードブックＤm,fと、識別子ｌ毎のラベル値ｆ（１≦ｆ≦Ｆ）を登録した残差コードブック識別子テーブルＴm,fとを記憶した残差コードブック記憶手段と、
登録ベクトルｙ毎に、残差量子化手段から出力された第ｍ段毎に出力されたＭ個の識別子ｌｍ列を登録する登録データベースと、
クエリベクトルｘについて、残差コードブックの全ての代表ベクトルｄm,f,lとの内積（ｓm,f,l＝ｘ・ｄm,f,l）を算出し、識別子ｌｍ列に基づく内積の累積和から算出した近似ベクトルｙ〜に、所定条件下で類似（距離が近い）する登録ベクトルｙを探索する探索手段と
してコンピュータを機能させ、
残差量子化手段について、第ｍ段で選択される量子化器ｆは、前段の第ｍ−１段で選択された量子化器で用いられた残差コードブックＤの代表ベクトルの識別子に対応する残差コードブック識別子テーブルＴのラベル値に応じて切り替えられる
ようにコンピュータを機能させることを特徴とする。
【００２０】
本発明によれば、装置を用いて、符号化された高次元の登録ベクトルｙの集合からクエリベクトルｘに類似したベクトルを検索する検索方法であって、
第１段（ｍ＝１）の１個の量子化器から順に、第ｍ段（２≦ｍ≦Ｍ）毎のＦ個の量子化器が多段に構成されており、第ｍ段毎にいずれか１つの量子化器ｆ（１≦ｆ≦Ｆ）が選択されると共に、第ｍ段における当該量子化器に入力されたベクトルｙmと当該量子化器から出力されたベクトルｙm〜との残差ベクトルｙm+1が、次の第ｍ＋１段の量子化器へ入力されるように構成された残差量子化部と、
量子化器（第ｍ段の第ｆ番目）毎に、識別子ｌ（１≦ｌ≦Ｌ）毎の代表ベクトルｄm,f,lを登録した残差コードブックＤm,fと、識別子ｌ毎のラベル値ｆ（１≦ｆ≦Ｆ）を登録した残差コードブック識別子テーブルＴm,fとを記憶した残差コードブック記憶部と、
登録ベクトルｙ毎に、残差量子化手段から出力された第ｍ段毎に出力されたＭ個の識別子ｌｍ列と、識別子ｌｍ列に基づく代表ベクトルｄm,fm,lmの累積和から算出された近似ベクトルｙ〜のＬ２ノルムを量子化した識別子lM+1とを登録する登録データベースと
を有し、
クエリベクトルｘについて、残差コードブックの全ての代表ベクトルｄm,f,lとの内積（ｓm,f,l＝ｘ・ｄm,f,l）を算出し、識別子ｌｍ列に基づく内積の累積和から算出した近似ベクトルｙ〜に、所定条件下で類似（距離が近い）する登録ベクトルｙを探索し、
残差量子化部について、第ｍ段で選択される量子化器ｆは、前段の第ｍ−１段で選択された量子化器で用いられた残差コードブックＤの代表ベクトルの識別子に対応する残差コードブック識別子テーブルＴのラベル値に応じて切り替えられる
ことを特徴とする。
【発明の効果】
【００２１】
本発明の検索装置及びプログラムによれば、検索精度とメモリ量とのトレードオフを考慮して、高次元の特徴ベクトルの集合からクエリ特徴ベクトルに類似した特徴ベクトルを検索することができる。
【図面の簡単な説明】
【００２２】
【図１】本発明における検索装置の機能構成図である。
【図２】残差量子化部の論理的な内部構成図である。
【図３】残差コードブック記憶部に記憶された量子化器毎の残差コードブックＤ及び残差コードブック識別子テーブルＴを表す説明図である。
【図４】残差量子化部の中で量子化器の選択順序を具体的に表す説明図である。
【図５】各量子化器の残差コードブック毎に算出した内積を表す説明図である。
【図６】残差コードブック生成部におけるフローチャートである。
【図７】残差コードブック毎の残差ベクトル集合同士の関係を表す説明図である。
【発明を実施するための形態】
【００２３】
以下、本発明の実施の形態について、図面を用いて詳細に説明する。
【００２４】
図１は、本発明における検索装置の機能構成図である。
【００２５】
本発明が対象とする検索装置１は、高次元の登録ベクトルの集合から、クエリベクトルに類似したベクトルを検索する。ここで、ベクトルとは、例えば画像の局所特徴領域から抽出された高次元の局所特徴ベクトルであって、例えば１２８次元（Ｄ＝１２８）で表されるようなものである。
【００２６】
検索装置１は、残差コードブック記憶部１０１と、登録データベース１０２と、残差量子化部１１１と、探索部１１２と、残差コードブック生成部１２１とを有する。これら機能構成部は、装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。以下では、残差量子化部１１１（登録部）、探索部１１２（探索部）、残差コードブック生成部１２１（学習部）の順に説明すると共に、残差コードブック記憶部１０１及び登録データベース１０２については、登録部で説明する。
【００２７】
［残差量子化部１１１（登録部）］
図２は、残差量子化部の論理的な内部構成図である。
【００２８】
図２によれば、残差量子化部１１１は、第１段（ｍ＝１）の１個の量子化器から順に、第ｍ段（２≦ｍ≦Ｍ）毎のＦ個の量子化器が多段に構成されている。そして、第ｍ段毎にいずれか１つの量子化器ｆ（１≦ｆ≦Ｆ、ｆ＝０は量子化の停止を意味）が選択される。また、第ｍ段における当該量子化器に入力されたベクトルｙmと当該量子化器から出力されたベクトルｙm〜との残差ベクトルｙm+1が、次の第ｍ＋１段の量子化器へ入力される。
【００２９】
図２によれば、残差量子化部１１１は、登録ベクトルｙ1を入力し、その登録ベクトルｙ1を、第１段（ｍ＝１）の１個の量子化器１に入力する。第１段の量子化器１は、登録ベクトルｙ1を、代表ベクトルｄ（ｙ1〜）に量子化する。そして、第１段の量子化器１に入力されたベクトルｙ1と第１段の量子化器から出力された代表ベクトルｙ1〜との残差ベクトルｙ2＝ｙ1−ｙ1〜が、次の第２段の量子化器２へ入力される。
【００３０】
第２段（ｍ＝２）では、Ｆ個の量子化器が備えられており、いずれか１つの量子化器ｆ（１≦ｆ≦Ｆ）が選択される。いずれの量子化器ｆが選択されかは、前段（第１段）の量子化器によって決定されたラベル値に基づく。図２によれば、ｆ＝２の量子化器２２が選択されている。第２段の量子化器２２は、残差ベクトルｙ2を、代表ベクトルｄ（ｙ2〜）に量子化する。そして、第２段の量子化器２２に入力されたベクトルｙ2と第２段の量子化器２２から出力されたベクトルｙ2〜との残差ベクトルｙ3＝ｙ2−ｙ2〜が、次の第３段の量子化器３へ入力される。
【００３１】
第３段から第Ｍ段（ｍ＝３〜Ｍ）まで、第２段と同様にＦ個の量子化器が備えられており、いずれか１つの量子化器ｆ（１≦ｆ≦Ｆ）が選択される。同様に、いずれの量子化器ｆが選択されかは、前段の量子化器によって決定されたラベル値に基づく。当該量子化器は、入力された残差ベクトルｙmを、代表ベクトルｄ（ｙm〜）に量子化する。そして、当該量子化器に入力されたベクトルｙmと当該量子化器から出力されたベクトルｙm〜との残差ベクトルｙm+1が、次段の量子化器へ入力される。これを、最終の第Ｍ段（ｍ＝Ｍ）まで進める。
【００３２】
ここで、残差量子化器１１１に入力された１つの登録ベクトルｙ毎に、選択された各段（ｍ＝１〜Ｍ）の量子化器から、ラベル値ｌmが出力される。そして、残差量子化器１１１は、最終的に、第ｍ段毎に出力されたＭ個の識別子ｌｍ列を出力する。
【００３３】
図３は、残差コードブック記憶部に記憶された量子化器毎の残差コードブックＤ及び残差コードブック識別子テーブルＴを表す説明図である。
【００３４】
残差量子化部１１１は全体として、以下のテーブルを有する。
（Ｍ−１）×Ｆ＋１個の残差コードブックＤ
（Ｄ1，Ｄ2,1〜Ｄ2,F，・・・，ＤM,1〜ＤM,F）
（Ｍ−２）×Ｆ＋１個の残差コードブック識別子テーブルＴ
（Ｔ1，Ｔ2,1〜Ｔ2,F，・・・，Ｔ(M-1),1〜Ｔ(M-1),F）
Ｍ：残差量子化部内の量子化器の段数の最大数
Ｆ：第２段〜第Ｍ段における各段の量子化器の数
尚、第１段だけは、量子化器が１個となる。
【００３５】
残差コードブックＤm,fは、量子化器（第ｍ段の第ｆ番目）毎に、識別子ｌ（１≦ｌ≦Ｌ）毎の代表ベクトルｄm,f,lを登録する。
代表識別値ｌ：  代表ベクトルｄ
１：  ｄm,fm,1
２：  ｄm,fm,2
３：  ｄm,fm,3
Ｌ＝４：  ｄm,fm,4
【００３６】
残差コードブック識別子テーブルＴm,fは、各残差コードブックＤm,f（但し最終段のＤM,fは除く）について、識別子ｌ毎のラベル値ｔを登録する。
代表識別値ｌ：  ラベル値
１：  ｔm,f,1
２：  ｔm,f,2
３：  ｔm,f,3
Ｌ＝４：  ｔm,f,4
ここで、ラベル値ｔm,f,lは、当該量子化器の次段について選択される量子化器ｆ（１≦ｆ≦Ｆ）を表す。従って、ラベル値ｔは、１〜ｆのいずれか１つの値をとる。ラベル値ｔがいずれのｆをとるかは、図６及び図７（学習部）を用いて後述する。残差量子化部１１１について、第ｍ段で選択される量子化器ｆは、前段の第ｍ−１段で選択された量子化器で用いられた残差コードブック識別子テーブルＴのラベル値ｔに応じて切り替えられる。
【００３７】
図４は、残差量子化部の中で量子化器の選択順序を具体的に表す説明図である。
【００３８】
（Ｓ４１）第１段の量子化器１について、入力された登録ベクトルｙ1は、残差コードブックＤ1,1を用いて、代表ベクトルｄ1,1,1〜ｄ1,1,4（ｙ1〜）のいずれか１つに量子化（符号化）される。具体的には、入力ベクトルｙとの差が最小となる代表ベクトルｄが選択される。
ｌ1＝ａｒｇｍｉｎl||ｙ1−ｄ1,l,l||２
（||ｙ1−ｄ1,l,l||２が最小となるｌを導出する）
図４によれば、代表ベクトルｄ1,1,2が選択され、そのＩＤ＝２が得られる。第１の量子化器１は、ｌ1＝２（ＩＤ）を出力する。
【００３９】
次に、残差コードブック識別子テーブルＴ1,1を用いて、量子化された代表ベクトルに付与されたＩＤ＝２に対応するラベル値ｔ1,1,2を検索する。図４によれば、ラベル値ｔ1,1,2＝１（ｆ＝１）が割り当てられており、これは、第２段の量子化器２１（ｍ＝２，ｆ＝１）が選択されることを意味する。
【００４０】
そして、第１段の量子化器１に入力されたベクトルｙ1と第１段の量子化器から出力された代表ベクトルｙ1〜との残差ベクトルｙ2が、次の第２段の量子化器２１へ入力される。
ｙ2＝ｙ1−ｙ1〜＝ｙ1−ｄ1,l,2
【００４１】
（Ｓ４２）第２段の量子化器２１について、入力された残差ベクトルｙ2は、残差コードブックＤ2,1を用いて、代表ベクトルｄ2,1,1〜ｄ2,1,4（ｙ2〜）のいずれか１つに量子化（符号化）される。
ｌ2＝ａｒｇｍｉｎl||ｙ2−ｄ2,l,l||２ 
（||ｙ2−ｄ2,l,l||２が最小となるｌを導出する）
図４によれば、代表ベクトルｄ2,1,4が選択され、そのＩＤ＝４が得られる。第２の量子化器２１は、ｌ2＝４（ＩＤ）を出力する。
【００４２】
次に、残差コードブック識別子テーブルＴ2,1を用いて、量子化された代表ベクトルに付与されたＩＤ＝４に対応するラベル値ｔ2,1,4を検索する。図４によれば、ラベル値ｔ2,1,4＝２（ｆ＝２）が割り当てられており、これは、第３段の量子化器３２（ｍ＝３，ｆ＝２）が選択されることを意味する。
【００４３】
そして、第２段の量子化器２１に入力されたベクトルｙ2と第２段の量子化器から出力された代表ベクトルｙ2〜との残差ベクトルｙ3が、次の第３段の量子化器３２へ入力される。
ｙ3＝ｙ2−ｙ2〜＝ｙ2−ｄ2,l,4
【００４４】
以降、前述したと同様に、残差ベクトルを、繰り返し量子化する。
【００４５】
最終的に、第Ｍ段の量子化器ＭｆMについて、入力された残差ベクトルｙMは、残差コードブックＤM,fMを用いて、代表ベクトルｄM,fM,1〜ｄM,fM,L（ｙM〜）のいずれか１つに量子化（符号化）される。
ｌM＝ａｒｇｍｉｎl||ｙM−ｄM,fM,l||２
（||ｙM−ｄM,fM,l||２が最小となるｌを導出する）
第Ｍ段の量子化器Ｍｆは、ｌM＝識別子（ＩＤ）を出力する。
【００４６】
そして、残差量子化部１１１は、登録ベクトルｙ毎に、最終的に以下の情報を、登録データベース１０２へ登録する。
（１）第ｍ段の量子化器毎に出力されたＭ個の識別子ｌｍ列（ｍ＝１〜Ｍ）
（２）識別子ｌｍ列に基づく代表ベクトルｄm,fm,lmの累積和から算出された
近似ベクトルｙ〜のＬ２ノルムを量子化した識別子lM+1
（３）メタデータ
【００４７】
近似ベクトルｙ〜は、代表ベクトルの和によって、以下のように表される。
ｙ〜ｙ〜＝Σm=1Mｄm,fm,lm
【００４８】
尚、ｆ1，ｆ2，・・・，ｆMは、ｆ1＝１と、ｆm+1＝ｔm,fm,lmと、ｌmとから、再帰的に求めることができる。このｙ~のＬ２ノルム||ｙ||2の値もスカラ量子化し、符号ｌM+1とする。スカラ量子化時の代表ベクトルは、スカラ値を持つコードブックＤM+1として保存することとする。ノルムとは、２つの点の間の距離を表す。Ｌ２ノルムとは、２つの点の各次元の値を二乗した和を意味する。
【００４９】
登録ベクトルのメタデータには、何が割り当てられてもよい。例えば、登録ベクトルが画像検索における画像特徴量である場合、登録ベクトルが所属する画像識別値を割り当てる。例えば画像の局所特徴領域から抽出された局所特徴ベクトルである場合、メタデータ（登録ベクトルの付加情報）は、画像識別子(IDentifier)、局所特徴領域のスケール、局所特徴領域の角度のいずれか１つを含むことも好ましい。また、高精度に検索する場合、登録ベクトルそのものをメタデータに追加的に登録するものであってもよい。
【００５０】
［探索部１１２（探索部）］
探索部１１２は、クエリベクトルｘを入力する。クエリベクトルｘは、登録ベクトルと同じ次元のベクトルである。そして、探索部１１２は、登録データベース１０２を参照して、クエリベクトルｘに所定条件下で類似する登録ベクトルｙを探索する。
【００５１】
図５は、各量子化器の残差コードブック毎に算出した内積を表す説明図である。
【００５２】
図５によれば、探索部１１２は、最初に、クエリベクトルｘについて、残差コードブックの全ての代表ベクトルｄm,fm,lmとの内積（ｓm,fm,lm＝ｘ・ｄm,fm,lm）を算出する。これは、（Ｍ−１）×Ｆ＋１個全ての残差コードブックについて算出し、参照テーブルとして一時的に保存する。
内積ｓm,fm,lm＝ｘ・ｄm,fm,lm
【００５３】
そして、探索部１１２は、識別子ｌｍ列に基づく内積の累積和から算出した近似ベクトルｙ〜に、所定条件下で類似（距離が近い）する登録ベクトルｙを探索する。探索部１１２は、以下の式によってクエリベクトルｘと登録ベクトルｙとの近似距離を算出するものであり、所定条件下で類似する登録ベクトルｙを探索する。
【数２】
2013140494.tif 000004
【００５４】
ｓm,fm,lmは、クエリベクトルｘが入力された際に予め計算されるために、参照テーブルの和のみで近似距離を算出することができる。前述した式の中で、||ｘ||2は、クエリベクトルのみに依存し、登録データベース中のベクトルには依存しない。そのために、実際の探索時に、考慮する必要がない。
【００５５】
この近似距離に基づいて、所定条件とは、ベクトルｙに対して、近似距離が所定閾値th以下となる登録ベクトルｙ、又は、近似距離が近い上位ｋ件となる登録ベクトルｙであってもよい。従って、検索結果として、複数の登録ベクトルが出力されてもよい。
【００５６】
［残差コードブック生成部１２１（学習部）］
前述したような検索装置１に対する残差量子化部１１１及び探索部１１２に対して、本発明によれば、量子化器毎に最適な残差コードブック及び残差コードブック識別子テーブルを生成する必要がある。ここで、残差コードブック生成部１２１は、学習ベクトルの集合を用いて、量子化器毎に、残差コードブックＤ及び残差コードブック識別子テーブルＴを生成する。
【００５７】
図６は、残差コードブック生成部におけるフローチャートである。
図７は、残差コードブック毎の残差ベクトル集合同士の関係を表す説明図である。
【００５８】
（Ｓ６１０）第１段の１個の量子化器１について、入力された学習ベクトルの集合を、Ｌ個のクラスタにクラスタリングする。クラスタリングアルゴリズムとしては一般的な、k-meansやk-means++を用いることができる。
次に、Ｌ個の各クラスタ毎に、代表ベクトルｄ1,1,1を導出する。そして、各代表ベクトルに一意の代表識別子ｌ（＝１〜Ｌ）を割り当てた残差コードブックＤ1を生成する。
次に、学習ベクトルの集合を、残差コードブックＤ1の各代表ベクトルで量子化し、残差ベクトルを導出する。
そして、代表識別子ｌ毎の各残差ベクトルの集合Ｒ1,1,lを生成する（図７参照）。
【００５９】
（Ｓ６２１）第２段のＦ個の量子化器は、入力された残差ベクトルの集合Ｒ1,1,1〜Ｒ1,1,Lを、Ｆ個にクラスタリングする。
次に、各クラスタに属する残差ベクトルの集合を更にＬ個にクラスタリングする。
次に、Ｌ個の各クラスタ毎に、代表ベクトルｄを導出する。そして、各代表ベクトルに一意の代表識別子ｌ（＝１〜Ｌ）を割り当てた残差コードブックＤ2,fを生成する。即ち、Ｌ個の代表ベクトルを持つＦ個の残差コードブックＤ2,1〜Ｄ2,Fを生成する。
【００６０】
（Ｓ６２２）第２段の量子化器は、残差ベクトルの集合Ｒ1,lがｆ'番目のクラスタに属している場合に、第１段の量子化器の残差コードブック識別子テーブルの識別子ｌのラベル値に、ｆ'を登録する。
【００６１】
（Ｓ６２３）次に、学習ベクトルの集合を、残差コードブックＤ2,fの各代表ベクトルで量子化し、残差ベクトルを導出する。
そして、代表識別子f,ｌ毎の各残差ベクトルの集合Ｒ2,f,lを生成する（図７参照）。
【００６２】
更に、次段で、Ｓ６２１〜Ｓ６２３を更に繰り返す。
【００６３】
（Ｓ６２１）第ｍ段の（２＜ｍ≦Ｍ）のＦ個の量子化器は、入力された残差ベクトルの集合Ｒm-1,1,1〜Ｒ m-1,F,LをＦ個にクラスタリングする。
次に、各クラスタに属する残差ベクトルの集合を更にＬ個にクラスタリングする。
次に、Ｌ個の各クラスタ毎に、代表ベクトルｄを導出する。そして、各代表ベクトルに一意の代表識別子ｌ（＝１〜Ｌ）を割り当てた残差コードブックＤm,fを生成する。即ち、Ｌ個の代表ベクトルを持つＦ個の残差コードブックＤm,1〜Ｄm,Fを生成する。
【００６４】
（Ｓ６２２）次に、残差ベクトルの集合Ｒm,f,lがｆ'番目のクラスタに属している場合に、第ｍ−１段の量子化器の残差コードブック識別子テーブルの識別子f,lのラベル値に、ｆ'を登録する。
【００６５】
（Ｓ６２３）次に、学習ベクトルの集合を、残差コードブックＤm,fの各代表ベクトルで量子化し、残差ベクトルを導出する。
そして、代表識別子f,ｌ毎の各残差ベクトルの集合Ｒm,f,lを生成する
【００６６】
そして、Ｓ６２１〜Ｓ６２３を、第Ｍ段の量子化器まで繰り返す。
【００６７】
以上、詳細に説明したように、本発明の検索装置及びプログラムによれば、検索精度とメモリ量とのトレードオフを考慮して、高次元の特徴ベクトルの集合からクエリ特徴ベクトルに類似した特徴ベクトルを検索することができる。
【００６８】
尚、本発明は、マルチメディアコンテンツを検索するために、これらコンテンツから多数の特徴ベクトルを抽出し、この特徴ベクトルの集合同士の間の類似度が高いコンテンツを検索結果として出力する技術に適用するものである。
【００６９】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００７０】
１  検索装置
１０１  残差コードブック記憶部
１０２  登録データベース
１１１  残差量子化部
１１２  探索部
１２１  残差コードブック生成部
【図１】
2013140494.tif 000006
【図２】
2013140494.tif 000007
【図３】
2013140494.tif 000008
【図４】
2013140494.tif 000009
【図５】
2013140494.tif 000010
【図６】
2013140494.tif 000011
【図７】
2013140494.tif 000012