(57)【要約】【課題】距離が近いベクトルを一定数探索するために、対象ベクトルについてベクトル間距離を反映した比較が可能なコードに符号化するベクトル符号化装置等を提供する。【解決手段】多数の訓練ベクトルをクラスタリングし、クラスタ番号毎に、当該クラスタに属する訓練ベクトルの代表ベクトルを対応付けた量子化コードブックを作成する量子化コードブック作成手段と、量子化コードブック記憶手段を用いて、入力された対象ベクトルに対応するクラスタ番号を出力する量子化手段と、クラスタ番号毎に、異なる２つの訓練ベクトルの近さ順序を保持するよう「コード」を対応付けた符号化コードブックを作成する符号化コードブック作成手段と、符号化コードブック記憶手段を参照し、量子化手段から出力されたクラスタ番号に対応する「コード」を出力する符号化手段とを有する。【選択図】図１
2015080181.tif 000002
【特許請求の範囲】
【請求項１】
対象ベクトルについてベクトル間距離を反映した比較が可能なコードに符号化するベクトル符号化装置であって、
多数の訓練ベクトルをクラスタリングし、クラスタ番号毎に、当該クラスタに属する訓練ベクトルの代表ベクトルを対応付けた量子化コードブックを作成する量子化コードブック作成手段と、
前記量子化コードブックを記憶する量子化コードブック記憶手段と、
前記量子化コードブック記憶手段を用いて、入力された前記対象ベクトルに対応するクラスタ番号を出力する量子化手段と、
クラスタ番号毎に、異なる２つの訓練ベクトルの近さ順序を保持するよう「コード」を対応付けた符号化コードブックを作成する符号化コードブック作成手段と、
前記符号化コードブックを記憶する符号化コードブック記憶手段と、
前記符号化コードブック記憶手段を参照し、前記量子化手段から出力された前記クラスタ番号に対応する「コード」を出力する符号化手段と
を有することを特徴とするベクトル符号化装置。
【請求項２】
前記コードは、{0,1}列からなるバイナリコードであり、
前記符号化コードブック作成手段は、
全ての訓練ベクトルの組について、
第１の訓練ベクトルに属するクラスタのバイナリコードと、第２の訓練ベクトルに属するクラスタのバイナリコードとの間の理想的なハミング距離を算出し、実際に割り当てられたコードに基づくハミング距離と理想的なハミング距離との誤差が最小となるように各クラスタにバイナリコードを割り当てる
ことを特徴とする請求項１に記載のベクトル符号化装置。
【請求項３】
前記符号化コードブック作成手段は、前記理想的なハミング距離を算出するために、
第１の訓練ベクトルからみた、他の全ての訓練ベクトルの中で第２の訓練ベクトルの近さ順序（ランク）から、第１の訓練ベクトルが属するクラスタと第２の訓練ベクトルが属するクラスタとの間の理想的なハミング距離を算出する
ことを特徴とする請求項２に記載のベクトル符号化装置。
【請求項４】
前記符号化コードブック作成手段は、遺伝的アルゴリズムを用いて、割り当てられたコードに基づくハミング距離と理想的なハミング距離の誤差が最小となるような各クラスタへのバイナリコードの割り当てを求める
ことを特徴とする請求項１に記載のベクトル符号化装置。
【請求項５】
前記符号化コードブック作成手段は、ランダムな割り当てからスタートし、割り当てられたコードに基づくハミング距離と理想的なハミング距離の誤差が小さくなるようランダムな割り当てを最適化する
ことを特徴とする請求項１に記載のベクトル符号化装置。
【請求項６】
前記量子化コードブック作成手段は、各クラスタに属する訓練ベクトルの数が同一の出現頻度となるようにクラスタリングする
ことを特徴とする請求項１から５のいずれか１項に記載のベクトル符号化装置。
【請求項７】
前記対象ベクトル及び前記訓練ベクトルを、部分ベクトルに分割するベクトル分割手段を更に有し、
分割されたベクトル毎に、前記量子化コードブック作成手段と、前記量子化コードブック記憶手段と、前記量子化手段と、前記符号化コードブック作成手段と、前記符号化コードブック記憶手段と、前記符号化手段とが機能する
ことを特徴とする請求項１から６のいずれか１項に記載のベクトル符号化装置。
【請求項８】
前記ベクトル分割手段は、
前記訓練ベクトルから、前記量子化手段における量子化誤差が小さくなるような回転行列Ｒを算出し、
前記対象ベクトルを、前記回転行列Ｒで回転させてから分割する
ことを特徴とする請求項７に記載のベクトル符号化装置。
【請求項９】
対象ベクトルについてベクトル間距離を反映した比較が可能なコードに符号化するように、装置に搭載されたコンピュータを機能させるプログラムにおいて、
多数の訓練ベクトルをクラスタリングし、クラスタ番号毎に、当該クラスタに属する訓練ベクトルの代表ベクトルを対応付けた量子化コードブックを作成する量子化コードブック作成手段と、
前記量子化コードブックを記憶する量子化コードブック記憶手段と、
前記量子化コードブック記憶手段を用いて、入力された前記対象ベクトルに対応するクラスタ番号を出力する量子化手段と、
クラスタ番号毎に、異なる２つの訓練ベクトルの近さ順序を保持するよう「コード」を対応付けた符号化コードブックを作成する符号化コードブック作成手段と、
前記符号化コードブックを記憶する符号化コードブック記憶手段と、
前記符号化コードブック記憶手段を参照し、前記量子化手段から出力された前記クラスタ番号に対応する「コード」を出力する符号化手段と
してコンピュータを機能させることを特徴とするベクトル符号化プログラム。
【請求項１０】
対象ベクトルについてベクトル間距離を反映した比較が可能なコードに符号化するように、装置を実行させるベクトル符号化方法において、
多数の訓練ベクトルをクラスタリングし、クラスタ番号毎に、当該クラスタに属する訓練ベクトルの代表ベクトルを対応付けた量子化コードブックを作成し、該量子化コードブックを記憶する第１のステップと、
クラスタ番号毎に、異なる２つの訓練ベクトルの近さ順序を保持するよう「コード」を対応付けた符号化コードブックを作成し、該符号化コードブックを記憶する第２のステップと
を有すると共に、
前記量子化コードブックを用いて、入力された対象ベクトルに対応するクラスタ番号を出力する第３のステップと、
前記符号化コードブックを参照し、前記量子化手段から出力された前記クラスタ番号に対応する「コード」を出力する第４のステップと
を有することを特徴とするベクトル符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多次元ベクトルをコンパクトなバイナリコードに符号化する技術に関する。
【背景技術】
【０００２】
近年、局所特徴点に基づいた画像認識や検索技術が注目されている。物体認識に用いる特徴ベクトルの抽出アルゴリズムとしては、回転やスケールの変化にロバストな、例えばＳＩＦＴ(Scale-Invariant Feature Transform)（例えば非特許文献１参照）やＳＵＲＦ(Speeded Up Robust Features)が用いられる。例えば、ＳＩＦＴの場合、１枚の画像からは１２８次元の特徴ベクトルの集合が抽出される。ＳＩＦＴとは、スケールスペースを用いて特徴的な局所領域を解析し、そのスケール変化及び回転に不変となる特徴ベクトルを記述する技術である。一方で、ＳＵＲＦは、積分画像を利用することによって処理を高速化しており、ＳＩＦＴよりも高速処理が可能であって、１枚の画像から６４次元の特徴ベクトルの集合が抽出される。
【０００３】
スマートフォンやタブレット端末のようなモバイル端末が普及する中で、コンテンツ検索処理に対して、省メモリ化及び高速マッチング化が要求されてきている。特に、拡張現実感（Augmented Reality, AR）の用途における画像認識の技術分野によれば、リアルタイムに処理するべく、ＳＩＦＴやＳＵＲＦの特徴ベクトルを省メモリで高速にマッチングすることが要求される。
【０００４】
この問題を解決すべく、ＳＩＦＴやＳＵＲＦのような特徴ベクトルを、｛0,1｝列で表現されるバイナリコードに符号化する技術がある。バイナリコードに変換する利点としては、以下の２つの点がある。
（１）オリジナルの特徴ベクトルよりもコンパクトなバイナリコードに変換することによって、メモリ使用量を削減することができる。
（２）２つのバイナリコード間の類似度を求める際に、高速に計算可能なハミング距離を用いることができる。
尚、「ハミング距離」とは、等しいビット数を持つ２つのバイナリコードの中で、対応する位置にある異なったビットの個数である。即ち、一方のバイナリコードから他方のバイナリコードへ変形する際に必要な置換回数を計測したものである。
【０００５】
また、大量の訓練特徴ベクトルに対して主成分分析を行い、各固有ベクトルで射影した次元毎に固有値に応じたビットを割り当てる関数を学習し、その関数によって入力ベクトルをバイナリ化する技術がある（例えば非特許文献２参照）。
【０００６】
更に、射影行列によって入力ベクトルを射影し、射影後の各次元の値の正負によってバイナリ化する技術もある（例えば特許文献１参照）。この技術によれば、以下の２つの特徴がある。
（１）バイナリコード間の距離が、元のベクトル間の距離を反映するように射影行列を学習する。これによって、検索精度を担保することができる。
（２）射影行列の要素がほとんど０であるような疎な行列となるようにする。これによって、高速にバイナリコードを生成できる。
【０００７】
更に、入力ベクトルをベクトル量子化し、割り当てられた代表ベクトル（クラスタ）に紐付けられたバイナリコードに符号化する技術もある（例えば非特許文献３参照）。この技術によれば、ベクトルのクラスタリングと、各クラスタに対するバイナリコードの紐付けを最適化するアルゴリズムとが提案されている。特に、この技術によれば、他の従来技術が超平面で｛0,1｝のビットを切り分けるのに対し、（量子化誤差の観点から最適な）ベクトル量子化により定義されるボロノイ図の境界で｛0,1｝のビットを切り分けるため、より適切なバイナリコードを生成することができる。「ボロノイ図(Voronoi diagram)」とは、ある距離空間上の任意の位置に配置された複数個の点（母点）に対して、同一距離空間上の他の点がどの母点に近いかによって領域分けされた図をいう。２次元ユークリッド平面の場合、領域の境界線は、各々の母点の２等分線の一部になる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特許第５２５８９１５号
【非特許文献】
【０００９】
【非特許文献１】D. G. Lowe, "Distinctive Image Features from Scale-InvariantKeypoints," International Journal of Computer Vision, vol. 60, no. 2, pp.91-110, 2004.
【非特許文献２】Y. Weiss, A. Torralba, and R. Fergus, "Spectral hashing,"in Proc. of NIPS, 2008.
【非特許文献３】K. He, F. Wen, and J. Sun, "K-means Hashing: anAffinity-Preserving Quantization Method for Learning Binary CompactCodes," in Proc. of CVPR, 2013.
【非特許文献４】T. Ge, K. He, Q. Ke, and J. Sun, "Optimized ProductQuantization for Approximate Nearest Neighbor Search," in Proc. of CVPR,2013.
【非特許文献５】「Orthogonal Procrustes problem」、[online]、［平成２５年９月３０日検索］、インターネット＜URL: http://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem＞
【発明の概要】
【発明が解決しようとする課題】
【００１０】
非特許文献３に記載の技術によれば、ベクトル量子化をバイナリコード化に結び付けることによって、符号化効率の高いバイナリコードを生成している。ベクトルのクラスタングと各クラスタに対するバイナリコードとの紐付けは、「バイナリコード間の距離が、ベクトル間の距離をうまく近似できること」を評価関数として最適化している。これは、距離が一定以下のベクトルを探索するという目的では有益である。
【００１１】
しかしながら、本願の発明者らは、距離が近いベクトルを一定数探索するといった目的であれば、正確に距離を近似する必要はないのではないか？と考えた。例えば、ベクトルの密度が高い領域では、正確に距離を近似する必要がある一方で、ベクトルの密度が低い領域では、ベクトル間の距離の順序さえ保てれば距離を正確に近似する必要はない。
【００１２】
そこで、本発明によれば、距離が近いベクトルを一定数探索するために、対象ベクトルについてベクトル間距離を反映した比較が可能なコードに符号化するベクトル符号化装置、プログラム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明によれば、対象ベクトルについてベクトル間距離を反映した比較が可能なコードに符号化するベクトル符号化装置であって、
多数の訓練ベクトルをクラスタリングし、クラスタ番号毎に、当該クラスタに属する訓練ベクトルの代表ベクトルを対応付けた量子化コードブックを作成する量子化コードブック作成手段と、
量子化コードブックを記憶する量子化コードブック記憶手段と、
量子化コードブック記憶手段を用いて、入力された対象ベクトルに対応するクラスタ番号を出力する量子化手段と、
クラスタ番号毎に、異なる２つの訓練ベクトルの近さ順序を保持するよう「コード」を対応付けた符号化コードブックを作成する符号化コードブック作成手段と、
符号化コードブックを記憶する符号化コードブック記憶手段と、
符号化コードブック記憶手段を参照し、量子化手段から出力されたクラスタ番号に対応する「コード」を出力する符号化手段と
を有することを特徴とする。
【００１４】
本発明のベクトル符号化装置における他の実施形態によれば、
コードは、{0,1}列からなるバイナリコードであり、
符号化コードブック作成手段は、
全ての訓練ベクトルの組について、
第１の訓練ベクトルに属するクラスタのバイナリコードと、第２の訓練ベクトルに属するクラスタのバイナリコードとの間の理想的なハミング距離を算出し、実際に割り当てられたコードに基づくハミング距離と理想的なハミング距離との誤差が最小となるように各クラスタにバイナリコードを割り当てることも好ましい。
【００１５】
本発明のベクトル符号化装置における他の実施形態によれば、
符号化コードブック作成手段は、理想的なハミング距離を算出するために、
第１の訓練ベクトルからみた、他の全ての訓練ベクトルの中で第２の訓練ベクトルの近さ順序（ランク）から、第１の訓練ベクトルが属するクラスタと第２の訓練ベクトルが属するクラスタとの間の理想的なハミング距離を算出することも好ましい。
【００１６】
本発明のベクトル符号化装置における他の実施形態によれば、
符号化コードブック作成手段は、遺伝的アルゴリズムを用いて、割り当てられたコードに基づくハミング距離と理想的なハミング距離の誤差が最小となるような各クラスタへのバイナリコードの割り当てを求めることも好ましい。
【００１７】
本発明のベクトル符号化装置における他の実施形態によれば、
符号化コードブック作成手段は、ランダムな割り当てからスタートし、割り当てられたコードに基づくハミング距離と理想的なハミング距離の誤差が小さくなるようランダムな割り当てを最適化することも好ましい。
【００１８】
本発明のベクトル符号化装置における他の実施形態によれば、
量子化コードブック作成手段は、各クラスタに属する訓練ベクトルの数が同一の出現頻度となるようにクラスタリングすることも好ましい。
【００１９】
本発明のベクトル符号化装置における他の実施形態によれば、
対象ベクトル及び訓練ベクトルを、部分ベクトルに分割するベクトル分割手段を更に有し、
分割されたベクトル毎に、量子化コードブック作成手段と、量子化コードブック記憶手段と、量子化手段と、符号化コードブック作成手段と、符号化コードブック記憶手段と、符号化手段とが機能する
ことも好ましい。
【００２０】
本発明のベクトル符号化装置における他の実施形態によれば、
ベクトル分割手段は、
訓練ベクトルから、量子化手段における量子化誤差が小さくなるような回転行列Ｒを算出し、
対象ベクトルを、回転行列Ｒで回転させてから分割する
ことも好ましい。
【００２１】
本発明によれば、対象ベクトルについてベクトル間距離を反映した比較が可能なコードに符号化するように、装置に搭載されたコンピュータを機能させるプログラムにおいて、
多数の訓練ベクトルをクラスタリングし、クラスタ番号毎に、当該クラスタに属する訓練ベクトルの代表ベクトルを対応付けた量子化コードブックを作成する量子化コードブック作成手段と、
量子化コードブックを記憶する量子化コードブック記憶手段と、
量子化コードブック記憶手段を用いて、入力された対象ベクトルに対応するクラスタ番号を出力する量子化手段と、
クラスタ番号毎に、異なる２つの訓練ベクトルの近さ順序を保持するよう「コード」を対応付けた符号化コードブックを作成する符号化コードブック作成手段と、
符号化コードブックを記憶する符号化コードブック記憶手段と、
符号化コードブック記憶手段を参照し、量子化手段から出力されたクラスタ番号に対応する「コード」を出力する符号化手段と
してコンピュータを機能させることを特徴とする。
【００２２】
本発明によれば、対象ベクトルについてベクトル間距離を反映した比較が可能なコードに符号化するように、装置を実行させるベクトル符号化方法において、
多数の訓練ベクトルをクラスタリングし、クラスタ番号毎に、当該クラスタに属する訓練ベクトルの代表ベクトルを対応付けた量子化コードブックを作成し、該量子化コードブックを記憶する第１のステップと、
クラスタ番号毎に、異なる２つの訓練ベクトルの近さ順序を保持するよう「コード」を対応付けた符号化コードブックを作成し、該符号化コードブックを記憶する第２のステップと
を有すると共に、
量子化コードブックを用いて、入力された対象ベクトルに対応するクラスタ番号を出力する第３のステップと、
符号化コードブックを参照し、量子化手段から出力されたクラスタ番号に対応する「コード」を出力する第４のステップと
を有することを特徴とする。
【発明の効果】
【００２３】
本発明のベクトル符号化装置、プログラム及び方法によれば、距離が近いベクトルを一定数探索するために、対象ベクトルについてベクトル間距離を反映した比較が可能なコードに符号化することができる。
【図面の簡単な説明】
【００２４】
【図１】本発明におけるベクトル符号化装置の機能構成図である。
【図２】Ｂ＝２における理想的なベクトル間距離を用いたランクを表す説明図である。
【図３】Ｂ＝３における理想的なベクトル間距離を用いたランクを表す説明図である。
【図４】本発明における前段のフローチャートである。
【図５】図４に続く後段のフローチャートである。
【図６】本発明について遺伝的アルゴリズムを用いたフローチャートである。
【図７】本発明について回転行列Ｒを導出するための行列式である。
【図８】回転行列Ｒに基づく訓練ベクトルの回転を表す説明図である。
【発明を実施するための形態】
【００２５】
以下、本発明の実施の形態について、図面を用いて詳細に説明する。
【００２６】
図１は、本発明におけるベクトル符号化装置の機能構成図である。
【００２７】
図１によれば、ベクトル符号化装置１は、量子化コードブック記憶部１１０と、量子化部１１１と、量子化コードブック作成部１１２と、符号化コードブック記憶部１２０と、符号化部１２１と、符号化コードブック作成部１２２とを有する。これら機能構成部は、装置に搭載されたコンピュータを機能させるベクトル符号化用プログラムを実行することによって実現される。また、これら機能構成部の処理の流れは、装置を用いたベクトル符号化方法としても理解できる。尚、ベクトル符号化装置１は、入力された対象ベクトルを、Ｂビットに符号化することとする。
【００２８】
［量子化コードブック作成部１１２］
量子化コードブック作成部１１２は、入力された多数の訓練ベクトルをクラスタリングする。ここでは、例えばk-meansのようなクラスタリングアルゴリズムを用いる。クラスタリングをした後、クラスタ番号毎に、当該クラスタに属する訓練ベクトルの代表（平均）ベクトルを算出する。そして、クラス番号毎に、代表ベクトルを対応付けたテーブルを、量子化コードブックとする。
【００２９】
k-meansアルゴリズムを用いた場合、訓練ベクトルの分布によっては、各クラスタに割り当てられる訓練ベクトルの出現頻度が大きく異なる場合がある。この出現頻度は、符号化部から出力される各バイナリコードの出現頻度となる。そのために、情報量の観点からは、各バイナリコードが同一頻度で出現することが好ましい。このことから、各クラスタに割り当てられる訓練ベクトルの頻度が同一になるよう、後処理によってクラスタリングの結果を変えてもよい。即ち、量子化コードブック作成部１１２は、各クラスタに属する訓練ベクトルの数が同一の出現頻度となるようにクラスタリングする。これは、訓練ベクトルを各クラスタに割り当てる際に、訓練ベクトルからクラスタの代表ベクトルまでの距離に、ペナルティ距離を加算することによって処理する。
【００３０】
具体的には、i番目の代表ベクトルに対するペナルティ距離ｄiについて、初期値を1として、ペナルティ距離の更新と、各クラスタへの訓練ベクトルの割り当てとを、繰り返し処理により最適化する。ペナルティ距離は、以下の式によって更新する。
ｄi＝ｄi＊（ｎi／ｎ）α
ｎ＝Ｎ／Ｋ
ｎi：i番目のクラスタに属する訓練ベクトルの数
ｎ：平均訓練ベクトル数
Ｎ：訓練ベクトル数
Ｋ（＝２Ｂ）：クラスタ数
α：収束速度を調整するパラメータ
【００３１】
ｎi＞nの場合、クラスタまでの距離が大きくなり、割り当てられる訓練ベクトルの数が減少する。この場合、ペナルティ距離の最適化によって、各クラスタに割り当てられる訓練ベクトルの数を、ほぼ同一とすることができる。
【００３２】
［量子化コードブック記憶部１１０］
量子化コードブック記憶部は、量子化コードブック作成部１１２によって作成された量子化コードブックを記憶する。具体的には、訓練ベクトルと同次元の代表ベクトルを、クラスタ数Ｋ個分、記憶する。
【００３３】
また、前述のペナルティ距離を利用してクラスタに割り当てられた訓練ベクトルの数を調整している場合には、ペナルティ距離も記憶する。ペナルティ距離（スカラー値）を、クラスタ数Ｋ個分、更に記憶する。
【００３４】
［量子化部１１１］
量子化部１１１は、量子化コードブック記憶部１１０を用いて、入力された対象ベクトルに、量子化コードブック中で最も近い代表ベクトルを参照し、それに対応するクラスタ番号を出力する。
【００３５】
また、前述のペナルティ距離を利用してクラスタに割り当てられた訓練ベクトルの数を調整している場合には、ペナルティ距離を考慮して割り当てる。具体的には、入力されたベクトルに関して、各クラスタの代表ベクトルまでの距離と、対応するクラスタのペナルティ距離の和を算出し、その和が最も小さくなるクラスタの番号を出力する。
【００３６】
［符号化コードブック作成部１２２］
符号化コードブック作成部１２２は、クラスタ番号毎に、異なる２つの訓練ベクトルの近さ順序を保持するよう「コード」を対応付けた符号化コードブックを作成する。コードは、{0,1}列からなるバイナリコードである。そして、全ての訓練ベクトルの組について、第１の訓練ベクトルに属するクラスタのバイナリコードと、第２の訓練ベクトルに属するクラスタのバイナリコードとの間の「理想的なハミング距離」を算出する。実際に割り当てられた「コードに基づくハミング距離」と「理想的なハミング距離」との誤差が最小となるように、各クラスタにバイナリコードを割り当てる。
【００３７】
また、符号化コードブック作成部１２２は、理想的なハミング距離を算出するために、第１の訓練ベクトルからみた、他の全ての訓練ベクトルの中で第２の訓練ベクトルの近さ順序（ランク）から、第１の訓練ベクトルが属するクラスタと第２の訓練ベクトルが属するクラスタとの間の理想的なハミング距離を算出する。
【００３８】
各ハミング距離の出現頻度は、２項分布から算出される。ここでは、Ｎ個のＢビットのバイナリコードを考える。
Ｂ：ビット数
Ｎ：訓練ベクトル数
Ｋ（＝２Ｂ）：クラスタ数
このとき、全てのバイナリコードが、同一確率（１／２Ｂ）で出現すると仮定した場合、あるバイナリコードとのハミング距離がｄとなるバイナリコードの出現頻度の期待値は、以下のようになる。
ＢＣｄ・Ｎ／２Ｂ
ＢＣｄ：Ｂビットの中でｄビットを選択する組み合わせ
ハミング距離がｄということは、Ｂビットのうちｄビットが異なっており、その位置の選び方の組み合わせが、ＢＣｄ個あることを意味する。
【００３９】
各訓練ベクトルｖについて、全ての訓練ベクトルが当該ベクトルｖからの距離に関して昇順にソートされる。ここでは、各訓練ベクトルが何番目に位置しているかの近さ順序（ランク）が既に分かっているものとする。理想的には、以下のように変換される。
先頭からＢＣ０・Ｎ／２Ｂ個のベクトルは、ベクトルｖのバイナリコードから、ハミング距離０のバイナリコードに変換される。
その後、ＢＣ１・Ｎ／２Ｂ個のベクトルは、ベクトルｖのバイナリコードからハミング距離１のバイナリコードに変換される。
・・・・・・
最後に、ＢＣＢ・Ｎ／２Ｂ個のベクトルは、ベクトルｖのバイナリコードからハミング距離Ｂのバイナリコードに変換される。
【００４０】
図２は、Ｂ＝２における理想的なベクトル間距離を用いたランクを表す説明図である。
【００４１】
図２によれば、以下のように定義されている。
訓練ベクトル数：Ｎ＝１２個
ビット数：Ｂ＝２ビット
クラスタ数：Ｋ＝２２＝４
その上で、各訓練ベクトルｖについて、全ての訓練ベクトルが当該ベクトルｖからの距離に関して昇順にソートされる。そして、例えばベクトルｖがバイナリコード「００」に割り当てされた場合の例を表す。以下のように、ハミング距離に応じた理想的なベクトル間距離が算出される。
（コード間のハミング距離）：（出現頻度）：（バイナリコード）
０            ：２Ｃ０・Ｎ／２２：      ００
１            ：２Ｃ１・Ｎ／２２：  ０１、１０
２            ：２Ｃ２・Ｎ／２２：      １１
【００４２】
図３は、Ｂ＝３における理想的なベクトル間距離を用いたランクを表す説明図である。
【００４３】
図３によれば、以下のように定義されている。
訓練ベクトル数：Ｎ＝１２個
ビット数：Ｂ＝３ビット
クラスタ数：Ｋ＝２３＝８
その上で、各訓練ベクトルｖについて、全ての訓練ベクトルが当該ベクトルｖからの距離に関して昇順にソートされる。そして、例えばベクトルｖがバイナリコード「０１０」に割り当てられた場合の例を表す。以下のように、ハミング距離に応じた理想的なベクトル間距離が算出される。
（コード間のハミング距離）：（出現頻度）：（バイナリコード）
０            ：３Ｃ０・Ｎ／２３：    ０１０
１            ：３Ｃ１・Ｎ／２３：１１０、０００、０１１
２            ：３Ｃ２・Ｎ／２３：１００、１１１、００１
３            ：３Ｃ３・Ｎ／２３：    １０１
【００４４】
ｘ番目のベクトルからｙ番目のベクトルに対するランクから、その間の理想的なハミング距離が算出される。このことを利用して、各クラスタに対してバイナリコードを割り当てる際に、この理想的なハミング距離からの実際のバイナリコード間の距離の誤差を、全てのｘ，ｙの組み合わせに関して総和した誤差を最小にするように割り当てる。
【００４５】
図４及び図５は、本発明におけるフローチャートである。
【００４６】
以下では、前述のプログラムの各処理を詳細に説明する。
（Ｓ１１）  C[N][N][B+1]← 0
//C[i][j][d]は、クラスタ番号iのコードと、クラスタ番号jのコードと
の間の距離が、d（0〜B）であるときのコストを表す
（Ｓ１２）  I[N]の算出
//I[x]は、x番目の訓練ベクトルが属するクラスタ番号を表す
（Ｓ１３）  R[N][N]の算出
//R[x][y]は、x番目の訓練ベクトルからみて、y番目の訓練ベクトルまで
近さ順序（ランク）を表す
（Ｓ２１）  for x = 1 to N
for y = 1 to N
（Ｓ２２）      r = ceil(R[x][y]*N/K)
//rは、x番目の訓練ベクトルが属するクラスタからみた、y番目の
訓練ベクトルが属するクラスタまでのの近さ順序（ランク）を表す
（Ｓ２３）      d’← r ≦ BＣ0 + BＣ1 + ・・・ + BＣdを満たす最小のd(d'＝0〜B)
//BＣhは、２項係数を表す。
//d'は、x番目のベクトルからみたy番目のベクトルのランクに基づ
く、バイナリコード間の理想的なハミング距離を表す。
（Ｓ２４）      for d = 0 to B
C[I[x]][I[y]][d] += (d'- d)2
end
//I[x]番目のクラスタと、I[y]番目のクラスタのバイナリコード間の
距離がdであるときのコストを、理想的なハミング距離からの２乗
誤差で更新する
（Ｓ２５）    end
end
【００４７】
（Ｓ３１）  for each BC[K]∈各クラスタに対するバイナリコードの全ての組合せ
//BC[k]: k番目のクラスタのバイナリコード
//K＝２Ｂ個のクラスタに対するK個のバイナリコードの割り当て
K！通り
（Ｓ３２）    C← 0
//現在のバイナリコードの割り当てのコスト
（Ｓ３３）    for i = 1 to K
for j = 1 to K
（Ｓ３４）        C += C[i][j][ham(BC[i],BC[j])]
//ham(BC1,BC2)：バイナリコードBC1,BC2間のハミング距離
（Ｓ３５）      end
end
（Ｓ３６）  end
【００４８】
これによって、対象ベクトルに近い訓練ベクトルを検索する際にに、元ベクトルの検索結果のランキングと、バイナリコードの検索結果のランキングとが、できる限り近くなるようコスト関数を設計する。このコスト関数に基づいて、各クラスタに対するバイナリコードの紐付けを最適化する。
【００４９】
［符号化コードブック記憶部１２０］
符号化コードブック記憶部１２０は、符号化コードブック作成部１２２で作成された符号化コードブックを記憶する。
【００５０】
［符号化部１２１］
符号化部１２１は、符号化コードブック記憶部１２０を参照し、量子化部１１１から出力されたクラスタ番号に対応する「コード」を出力する。
【００５１】
前述した実施形態によれば、コストCを最小にするバイナリコードの割り当てBC[K]を採用している。これによって、全てのクラスタについてクラスタ番号と対応するバイナリコードの組み合わせを、符号化コードブックとして出力することができる。しかしながら、コストCを最適にするバイナリコードの割り当てBC[K]は、K!（＝２Ｂ！）通りの候補が考えられる。そのために、ビット数Ｂが大きい場合（例えば５以上である場合）、全探索によって最適解を算出することは不可能となる。そこで、以下の２つの方法を採用することもできる。
（１）［遺伝的アルゴリズムの採用］
（２）［ベクトル分割部の採用]
【００５２】
（１）［遺伝的アルゴリズムの採用］
図６は、本発明について遺伝的アルゴリズムを用いたフローチャートである。
【００５３】
遺伝的アルゴリズム(Genetic Algorithm)は、近似解を探索するメタヒューリスティックアルゴリズムである。この技術によれば、データ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉（組み換え）・突然変異などの操作を繰り返しながら解を探索する。バイナリコードの割り当てBC[K]を遺伝子とみなし、遺伝的アルゴリズムによって近似解を効率的に算出することができる。
【００５４】
符号化コードブック作成部１２２は、遺伝的アルゴリズムを用いて、割り当てられたコードに基づくハミング距離と理想的なハミング距離の誤差が最小となるような各クラスタへのバイナリコードの割り当てを求める。このとき、ランダムな割り当てからスタートし、その割り当てを最適化することも好ましい。
【００５５】
（Ｓ６０）Ｓ６７との間の処理を所定回数、繰り返す。
（Ｓ６１）ランダムな順列BC[K]（バイナリコードの全ての組み合わせ）を生成する。
（Ｓ６２）現在の順列BC[K]について、コストCを算出する。
（Ｓ６３）現在の順列BC[K]の任意の２点を交換（BC[i]<->BC[j]）する。
（Ｓ６４）順列BC[K]（ＫＣ２通り）全てのコストCを計算する。
（Ｓ６５）最もコストが低いコストC'を算出する。
（Ｓ６６）現コストCが最小コストC'よりも大きい場合、Ｓ６２へ戻って繰り返す。
（Ｓ６７）現コストCが最小コストC'以上である場合、Ｓ６０との間で所定回数を繰り返す。その中で、最もコストCが低い順列BC[K]を採用する。
【００５６】
（２）［ベクトル分割部の採用]
図１によれば、対象ベクトル及び訓練ベクトルそれぞれを、部分ベクトルに分割するベクトル分割部１３を有する。ここでは、各部分ベクトルについて独立に、バイナリコードに符号化することによって、ビット数Ｂを小さくすることができる。また、入力された対象ベクトル及び訓練ベクトルについて、量子化誤差を最小化するように、回転させて補正することも好ましい（例えば非特許文献４参照）。
【００５７】
具体的には、分割した部分ベクトル毎に、量子化コードブック及び符号化コードブックを作成する。即ち、訓練ベクトルの割り当てについて、量子化誤差を最小化する回転行列Ｒを算出する。
【００５８】
図７は、本発明について回転行列Ｒを導出するための行列式である。
図８は、回転行列Ｒに基づく訓練ベクトルの回転を表す説明図である。
【００５９】
量子化誤差を最小化する回転行列Ｒは、以下の式を最小化するＲである（図７参照）。
||ＲＸ−Ｙ||F2
Ｘ：各訓練ベクトルを並べた行列（訓練ベクトルの数：Ｎ個）
Ｙ：Ｘの各訓練ベクトルが割り当てられた代表ベクトルを並べた行列
この式は、直交プロクラステス問題として知られており、特異値分解によって算出することができる（例えば非特許文献５参照）。図８によれば、訓練ベクトル全体を回転させることによって、訓練ベクトルと代表ベクトルとの間の量子化誤差を最小する回転位置が導出されている。
【００６０】
最適な回転行列Ｒを導出した後、再度、訓練ベクトルから代表ベクトルへの割り当てを実行し、コードブックを更新する。これら処理を収束するまで繰り返すことで、回転行列Ｒ及びコードブックを得る。
【００６１】
その後、対象ベクトルを、回転行列Ｒで回転させてから分割する。分割されたベクトル毎に、量子化コードブック作成部１１２と、量子化コードブック記憶部１１０と、量子化部１１１と、符号化コードブック作成部１２２と、符号化コードブック記憶部１２０と、符号化部１２１とが機能する。
【００６２】
以上、詳細に説明したように、本発明のベクトル符号化装置、プログラム及び方法によれば、距離が近いベクトルを一定数探索するために、対象ベクトルについてベクトル間距離を反映した比較が可能なコードに符号化することができる。
【００６３】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００６４】
１  ベクトル符号化装置
１１０  量子化コードブック記憶部
１１１  量子化部
１１２  量子化コードブック作成部
１２０  符号化コードブック記憶部
１２１  符号化部
１２２  符号化コードブック作成部
１３  ベクトル分解部
【図１】
2015080181.tif 000003
【図２】
2015080181.tif 000004
【図３】
2015080181.tif 000005
【図４】
2015080181.tif 000006
【図５】
2015080181.tif 000007
【図６】
2015080181.tif 000008
【図７】
2015080181.tif 000009
【図８】
2015080181.tif 000010