(57)【要約】      （修正有）【課題】入力ベクトルを符号化する代表ベクトルをより高速に選択するベクトル量子化装置を提供する。【解決手段】ｋ次元を基準としてソートされた代表ベクトルからなるコードブックを記憶したコードブックメモリ１３０と、入力ベクトルにおけるｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとしてコードブックから探索する初期代表ベクトル探索装置１７０と、入力ベクトルに対する代表ベクトルのひずみを計算してコードブックから次に探索する代表ベクトルのアドレスを計算する演算装置１４０と、演算装置１４０により計算された２つのひずみを比較して、入力ベクトルが符号化される代表ベクトルの候補を決める判定装置１５０と、演算装置１４０による演算処理と判定装置１５０による判定処理とを繰り返し行うように制御する制御装置１６０とを備える。【選択図】  図１
2009021873.tif 000002
【特許請求の範囲】
【請求項１】
ｋ次元（ｋは自然数。）を基準としてソートされた代表ベクトルからなるコードブックを記憶した記憶手段と、
入力ベクトルにおける上記ｋ次元の値の近傍に位置する上記代表ベクトルを、初期の代表ベクトルとして上記記憶手段に記憶されたコードブックから探索する探索手段と、
上記入力ベクトルに対する上記代表ベクトルのひずみを計算して、上記記憶手段に記憶されたコードブックから次に探索する上記代表ベクトルのアドレスを計算する演算手段と、
上記演算手段により計算された２つのひずみを比較して、上記入力ベクトルが符号化される上記代表ベクトルの候補を決める判定手段と、
上記演算手段による演算処理と、上記判定手段による判定処理とを繰り返し行うように制御する制御手段とを備えるベクトル量子化装置。
【請求項２】
上記コードブックの代表ベクトルを上記ｋ次元を基準として並び替えるソーティング手段を更に備えることを特徴とする請求項１記載のベクトル量子化装置。
【請求項３】
上記演算手段は、上記入力ベクトルに対する上記代表ベクトルのひずみを各次元毎に算出した値の積算値であるひずみの部分和を計算して、上記記憶手段に記憶されたコードブックから次に検索する上記代表ベクトルのアドレスを計算し、
上記判定手段は、上記演算手段により以前に算出された値が最小であるひずみと、上記演算手段により算出されたひずみの部分和とを比較して、上記入力ベクトルが符号化される上記代表ベクトルの候補を決めることを特徴とする請求項１又は２記載のベクトル量子化装置。
【請求項４】
上記探索手段は、上記入力ベクトルのｋ次元における上位ビットの値と上記初期の代表ベクトルの探索を開始するアドレスとを対応付けたテーブルを参照して、上記入力ベクトルに対して上記初期の代表ベクトルを探索することを特徴とする請求項１乃至３のいずれか１項記載のベクトル量子化装置。
【請求項５】
ｋ次元（ｋは自然数。）を基準として代表ベクトルがソートされたコードブックを記憶した記憶手段と、
入力ベクトルにおける上記ｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとして上記記憶手段に記憶されたコードブックから探索する探索手段と、
上記入力ベクトルに対する複数の上記代表ベクトルとのひずみを並列に計算して、上記記憶手段に記憶されたコードブックから次に探索する上記代表ベクトルのアドレスを計算する演算手段と、
上記演算手段により計算された複数のひずみを比較して、上記入力ベクトルが符号化される上記代表ベクトルの候補を決める判定手段と、
上記演算手段による演算処理と、上記判定手段による判定処理とを繰り返し行うように制御する制御手段とを備えるベクトル量子化装置。
【請求項６】
上記コードブックの代表ベクトルを上記ｋ次元を基準として並べ替えるソーティング手段を更に備えることを特徴とする請求項５記載のベクトル量子化装置。
【請求項７】
上記探索手段は、上記入力ベクトルのｋ次元における上位ビットの値と上記初期の代表ベクトルの探索を開始するアドレスとを対応付けたテーブルを参照して、上記入力ベクトルに対して上記初期の代表ベクトルを探索することを特徴とする請求項５又は６記載のベクトル量子化装置。
【請求項８】
ｋ次元（ｋは自然数。）を基準としてソートされた代表ベクトルからなるコードブックを記憶した第１の記憶手段と、
上記コードブックの代表ベクトルを上記ｋ次元を基準として並べ替えるソーティング手段と、
上記ソーティング手段により並べ替えられた上記コードブックの代表ベクトルの並び順が記された第２の記憶手段と、
入力ベクトルにおける上記ｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとして上記記憶手段に記憶されたコードブックから探索する探索手段と、
上記入力ベクトルに対する上記代表ベクトルのひずみを計算して、上記第２の記憶手段に記憶されたコードブックの代表ベクトルの並び順から次に探索する上記代表ベクトルのアドレスを計算する演算手段と、
上記演算手段により計算される２つのひずみを比較して、上記入力ベクトルが符号化される上記代表ベクトルの候補を決める判定手段と、
上記演算手段による演算処理と、上記判定手段による判定処理とを繰り返し行うように制御する制御手段とを備えるベクトル量子化装置。
【請求項９】
上記演算手段は、上記入力ベクトルに対する上記代表ベクトルのひずみを各次元毎に算出した値の積算値であるひずみの部分和を計算し、
上記判定手段は、上記演算手段により計算されたひずみの部分和と、該演算手段により以前に算出された値が最小であるひずみとを比較して、上記入力ベクトルが符号化される代表ベクトルの候補を決めることを特徴とする請求項８記載のベクトル量子化装置。
【請求項１０】
上記探索手段は、上記入力ベクトルのｋ次元における上位ビットの値と上記初期の代表ベクトルの探索を開始するアドレスとを対応付けたテーブルを参照して、上記入力ベクトルに対して上記初期の代表ベクトルを探索することを特徴とする請求項８又は９記載のベクトル量子化装置。
【請求項１１】
ｋ次元（ｋは自然数。）を基準として代表ベクトルがソートされたコードブックを記憶する記憶手段と、
上記コードブックの代表ベクトルを上記ｋ次元を基準として並び替えるソーティング手段と、
入力ベクトルにおける上記ｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとして上記記憶手段に記憶されたコードブックから探索する探索手段と、
上記入力ベクトルに対する複数の上記代表ベクトルとのひずみを並列に計算し、上記記憶手段に記憶されたコードブックから次に探索する上記代表ベクトルのアドレスを計算する演算手段と、
上記演算手段により計算された複数のひずみを比較して、上記入力ベクトルが符号化される代表ベクトルの候補を決める判定手段と、
上記演算手段による演算処理と、上記判定手段による判定処理とを繰り返し行うように制御する制御手段とを備えるベクトル量子化装置。
【請求項１２】
上記探索手段は、上記入力ベクトルのｋ次元における上位ビットの値と上記初期の代表ベクトルの探索を開始するアドレスとを対応付けたテーブルを参照して、上記入力ベクトルに対して上記初期の代表ベクトルを探索することを特徴とする請求項１１記載のベクトル量子化装置。
【請求項１３】
所定の記憶手段に記憶されたｋ次元（ｋは自然数。）を基準としてソートされた代表ベクトルからなるコードブックから、入力ベクトルにおける上記ｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとして探索する探索ステップと、
上記入力ベクトルと上記代表ベクトルのひずみを計算し、上記記憶手段に記憶されたコードブックから次に探索する上記代表ベクトルのアドレスを計算する演算ステップと、
上記演算ステップにより計算された２つのひずみを比較して符号化される代表ベクトルの候補を決める判定ステップとからなり、
上記演算ステップ及び上記判定ステップを繰り返し行うベクトル量子化方法。
【請求項１４】
所定の記憶手段に記憶されたｋ次元（ｋは自然数。）を基準としてソートされた代表ベクトルからなるコードブックから、入力ベクトルにおける上記ｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとして探索する探索ステップと、
上記入力ベクトルと複数の上記代表ベクトルとのひずみを並列に計算し、上記記憶手段に記憶されたコードブックから次に探索する上記代表ベクトルのアドレスを計算する演算ステップと、
上記演算ステップにより計算された複数のひずみを比較して符号化される上記代表ベクトルの候補を決める判定ステップとからなり、
上記演算ステップ及び上記判定ステップを繰り返し行うベクトル量子化方法。
【請求項１５】
所定の記憶手段に記憶された複数の代表ベクトルからなるコードブックをｋ次元（ｋは自然数。）を基準として並べ替えるソーティングステップと、
上記入力ベクトルにおける上記ｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとして上記記憶手段に記憶されたコードブックから探索する探索ステップと、
上記入力ベクトルと上記代表ベクトルのひずみを計算し、上記記憶手段に記憶されたコードブックから次に探索する上記代表ベクトルのアドレスを計算する演算ステップと、
上記演算ステップにより計算された２つのひずみを比較して、上記入力ベクトルが符号化される上記代表ベクトルの候補を決める判定ステップとからなり、
上記演算ステップ及び上記判定ステップを繰り返し行うベクトル量子化方法。
【請求項１６】
所定の記憶手段に記憶された複数の代表ベクトルからなるコードブックをｋ次元（ｋは自然数。）を基準として並べ替えるソーティングステップと、
上記入力ベクトルにおける上記ｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとして上記記憶手段に記憶されたコードブックから探索する探索ステップと、
上記入力ベクトルと複数の上記代表ベクトルとのひずみを並列に計算し、上記記憶手段に記憶されたコードブックから次に探索する上記代表ベクトルのアドレスを計算する演算ステップと、
上記演算ステップにより計算された複数のひずみを比較して、上記入力ベクトルが符号化される上記代表ベクトルの候補を決める判定ステップとからなり、
上記演算ステップ及び上記判定ステップを繰り返し行うベクトル量子化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ベクトル量子化技術に関わり、特にパターン認識、画像信号、及び、音声信号におけるベクトル量子化の符号化を行うベクトル量子化装置及びベクトル量子化方法に関するものである。
【背景技術】
【０００２】
ベクトル量子化は、入力空間を有限個の代表ベクトルで符号化する手法である。ベクトル量子化の応用例として、パターン認識の特徴抽出、計算幾何学の最近点問題、情報の圧縮、画像や音声などの量子化などが挙げられる。特に音声圧縮の規格であるＭＰＥＧ４ＣＥＬＰでは、音声の量子化にベクトル量子化技術が使用されている。
【０００３】
図１３にベクトル量子化の概念図を示す。ベクトル量子化は、入力ベクトルの符号化処理と、コードブックの生成処理との２つ処理に分けられる。
【０００４】
ベクトル量子化の入力ベクトルの符号化処理では、Ｋ次元の入力ベクトルｘ（１０５０）に対してあらかじめ与えられているＮ個のＫ次元の代表ベクトル（コードベクトルとも呼ばれる。）からなるコードブックＷ＝｛ｗｉ∈ＲＫ：ｉ＝１，・・・，Ｎ｝（１０４０）の中から最も近い代表ベクトルＷｍｉｎを選び出し（１０６０）、その代表ベクトルの番号ｍｉｎ、又は、その代表ベクトルの値を出力する（１０７０）。
【０００５】
その際、最も近い代表ベクトルを選ぶときの測度として、非負のひずみ測度ｄ（ｘ，ｗi）を利用する。すなわち、代表ベクトルの番号を出力したときの式は次の（１）式にて表すことができる。
【０００６】
【数１】
2009021873.tif 000003
【０００７】
また、代表ベクトルの値を出力したときの式は、次の（２）式にて表すことができる。
【０００８】
【数２】
2009021873.tif 000004
【０００９】
また、ベクトル量子化のコードブックの生成処理では、初期コードブック（１０１０）を設定し、コードブック生成用の入力ベクトル集合（１０３０）を与えて、入力ベクトル集合に合うように代表ベクトルの値を修正することを繰り返して最適化し（１０２０）、最終的に最適なコードブック（１０４０）を得る。コードブック生成用の入力ベクトルは、上述した入力ベクトルの符号化処理で入力される入力ベクトルと異なっていてもかまわない。
【００１０】
上記入力ベクトルの符号化処理は、１つの入力ベクトルに対して、全ての代表ベクトルとのひずみを計算し、最も近い代表ベクトルを選択する全探索処理が基本であるため、符号化に時間が非常にかかるという問題がある。
【００１１】
この問題を解決する手法の一つとして、特許文献１には、一部分の代表ベクトルを探索するだけで全探索と同じ代表ベクトルを高速に選択することができるベクトル量子化装置が記載されている。
【００１２】
このベクトル量子化装置５００は、図１４に示すように、入力部５１０、ソーティング装置５２０、コードブックメモリ５３０、演算装置５４０、判定装置５５０、及び、制御装置５６０から構成される。
【００１３】
このベクトル量子化装置５００において、入力部５１０は、入力端子５０１より新しいコードブックを受け取る。そして、この入力部５１０は、コードブックを記憶するコードブックメモリ５３０に、コードブックを書き込むアドレスと新しいコードブックを与える。
【００１４】
ソーティング装置５２０は、制御装置５６０からのソートの指示とどの次元を基準としてソートするかの指示を受け、コードブックメモリ５３０からコードブックを読み出し、指定されたｋ次元（ｋは自然数。）を基準としてコードブックをソートする。また、ソーティング装置５２０は、ソートしたコードブックをコードブックメモリ５３０の指定したアドレスに書き込む。
【００１５】
コードブックメモリ５３０は、入力部５１０から書き込むアドレスと新しいコードブックを受け取り、そのコードブックを指定されたアドレスに格納する。また、コードブックメモリ５３０は、コードブックをソーティング装置５２０に渡す。また、コードブックメモリ５３０は、ソーティング装置５２０によりソートされたコードブックと書き込むアドレスを受け取り、指定されたアドレスにコードブックを格納する。さらに、コードブックメモリ５３０は、ひずみ計算・アドレス計算を行う演算装置５４０から、アドレスを受け取り、代表ベクトルのデータ（代表ベクトルの値ｗｉ，番号ｉなど）を渡す。
【００１６】
演算装置５４０は、制御装置５６０からひずみ・アドレスの計算の指示を受け、コードブックメモリ５３０に読み込みたい代表ベクトルのアドレス（初期の代表ベクトルは制御装置５６０から指示される）を指定して、対応するデータ（代表ベクトルの番号と値）を読み込む。また、演算装置５４０は、入力端子５０２から入力ベクトルｘを受け取り、入力ベクトルと代表ベクトルとのひずみｄ（ｘ，ｗｉ）を計算する。そして、演算装置５４０は、ひずみｄ（ｘ，ｗｉ）とデータ（代表ベクトルの番号と値）を判定装置５５０に渡す。また、演算装置５４０は、制御装置５６０からソートの基準となったｋ次元の指示を受け、ｋ次元だけのひずみｄ（ｘｋ，ｗｉ ｋ）も判定装置５５０に渡す。さらに、演算装置５４０は、判定装置５５０から、判定結果により探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を受け、次の探索する代表ベクトルのアドレスを計算する。なお、演算装置５４０は、探索終了を示す情報ｆｉｎｉｓｈを受けた場合は、代表ベクトルの探索を終了する。
【００１７】
判定装置５５０は、現在の最小のひずみｄｃｕｒｍｉｎとその代表ベクトルの番号ｍｉｎを保持しており、現在の最小のひずみｄｃｕｒｍｉｎをもつｍｉｎ番の代表ベクトルと演算装置５４０により計算されたｉ番の代表ベクトルについてひずみｄ（ｘ，ｗｉ）を比較し、ひずみが小さい方を新しいｍｉｎ番、現在の最小のひずみｄｃｕｒｍｉｎとする。また、判定装置５５０は、制御装置５６０からの指示により、現在の最小のひずみを持つ代表ベクトルの番号ｍｉｎ（インデックス）、又は代表ベクトルの値を出力端子５０３に出力する。また、判定装置５５０は、制御装置５６０から判定の指示を受け、ｋ次元だけのひずみｄ（ｘｋ，ｗｉ ｋ）と現在の最小のひずみｄｃｕｒｍｉｎを比較し、ｄ（ｘｋ，ｗｉ ｋ）の方が大きければ、次に探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を変更し、また、ｕｐ／ｄｏｗｎ両方向とも調べ終わった場合には探索終了を示す情報ｆｉｎｉｓｈを演算装置５４０に渡し、ｄ（ｘｋ，ｗｉ ｋ）の方が小さければ、同方向の次の代表ベクトルを調べる情報を演算装置５４０に渡す。
【００１８】
制御装置５６０は、ソーティング装置５２０、演算装置５４０、及び、判定装置５５０の処理フローを制御する。また、制御装置５６０は、ソーティング装置５２０にソートの基準となる次元を指定する。また、制御装置５６０は、演算装置５４０に初期の代表ベクトルのアドレス（又は番号）を指定し、また、ソートの基準となった次元を指示する。さらに、制御装置５６０は、判定装置５５０に出力端子５０３に出力するのが代表ベクトルの番号なのか、代表ベクトルの値なのかを指示する。
【００１９】
このような構成のベクトル量子化装置５００では、図１５のフローチャートに示す符号化アルゴリズムに従ってソートされた代表ベクトルを用いた高速ベクトル量子化（Vector Quantizationby Searching in Sirted Codebook：ＶＱ−ＳＳＣ）を行う。
【００２０】
すなわち、このベクトル量子化装置５００では、先ず、ステップＦ５０１において代表ベクトルをソートするための基準のｋ次元を指定する。
【００２１】
次のステップＦ５０２では、ｋ次元の代表ベクトルの値に基づいて代表ベクトルを、例えば次の２つの方法によりソートする。
【００２２】
第１の方法は、直接代表ベクトルの順番を入れ替える方法である。代表ベクトルの番号を変更したくないときは、代表ベクトルの番号の情報を持つ構造体にして入れ替える。
【００２３】
直接並べ替えているので、現在の代表ベクトルの番号より下位の代表ベクトルの番号ｌｏｗｅｒは、現在の配列の番号から１を減じた配列の番号となり、現在の代表ベクトルの番号より上位の代表ベクトルの番号ｕｐｐｅｒは、現在の配列の番号に１を加えた配列の番号となる。
【００２４】
第２の方法としては、ソートしたときの順番を示す配列を用意するものである。この方法において、各代表ベクトルが保持すべき情報は、現在の代表ベクトルの番号より下位の代表ベクトルの番号ｌｏｗｅｒと、現在の代表ベクトルの番号より上位の代表ベクトルの番号ｕｐｐｅｒである。
【００２５】
次のステップＦ５０３では、次の（３）式及び（４）式から、入力ベクトルｘと初期の代表ベクトルｗｉとのひずみの計算を行い、このひずみｄ（ｘ，ｗｉ）を現在の最小のひずみｄｃｕｒｍｉｎとし、番号ｉを符号化の候補として保存しておく。
ｄｃｕｒｍｉｎ＝ｄ（ｘ，ｗｉ）  ・・・（３）
ｍｉｎ＝ｉ  ・・・（４）
【００２６】
次のステップＦ５０４では、初期の代表ベクトルｗｉの両隣の代表ベクトルの番号を以下のように保存する。
ｌｏｗｅｒ＝下位方向の隣の代表ベクトルの番号
ｕｐｐｅｒ＝上位方向の隣の代表ベクトルの番号
【００２７】
次のステップＦ５０５では、入力ベクトルｘとｌｏｗｅｒ番の代表ベクトルｗｌｏｗｅｒとのひずみｄ（ｘ，ｗｌｏｗｅｒ）の計算を行い、計算途中のｄ（ｘｋ，ｗｌｏｗｅｒｋ）を保存しておく。
【００２８】
次のステップＦ５０６では、ステップＦ５０５で計算したひずみｄ（ｘ，ｗｌｏｗｅｒ）が現在の最小のひずみｄｃｕｒｍｉｎより小さいか否か、すなわち、次の（５）式が成り立つか否かを判定する。
ｄ（ｘ，ｗｌｏｗｅｒ）＜ｄｃｕｒｍｉｎ（５）
もし、この（５）式が成り立つならば、次のステップＦ５０７へ進み、さもなければ、ステップＦ５０８へ移る。
【００２９】
ステップＦ５０７は、代表ベクトルの番号ｌｏｗｅｒの更新ステップであり、現在のｌｏｗｅｒ番の代表ベクトルの下位方向の隣の代表ベクトルの番号を新しいｌｏｗｅｒとして、ステップＦ５０５へ戻る。
【００３０】
ステップＦ５０８では、入力ベクトルｘとｕｐｐｅｒ番の代表ベクトルｗｕｐｐｅｒとのひずみｄ（ｘ，ｗｕｐｐｅｒ）の計算を行い、計算途中のｄ（ｘｋ，ｗｕｐｐｅｒｋ）を保存しておく。そして、計算したひずみｄ（ｘ，ｗｕｐｐｅｒ）が現在の最小のひずみｄｃｕｒｍｉｎより小さいか否か、すなわち、
ｄ（ｘ，ｗｕｐｐｅｒ）＜ｄｃｕｒｍｉｎ  ・・・（６）
が成り立つか否かを判定する。もし、この（６）式が成り立つならば、（７）式及び（８）式のように下記の値を設定する。
ｄｃｕｒｍｉｎ＝ｄ（ｘ，ｗｕｐｐｅｒ）  ・・・（７）
ｍｉｎ＝ｕｐｐｅｒ  ・・・（８）
【００３１】
次のステップＦ５０９では、上位方向の探索を続けるかどうか判断する。もし、次の（９）式を満足するなら、上位方向の探索は終了で、ステップＦ５１１へ移り、さもなければ、次のステップＦ５１０へ進む。
ｄ（ｘｋ，ｗｕｐｐｅｒｋ）＞ｄｃｕｒｍｉｎ  ・・・（９）
【００３２】
ステップＦ５１０は、代表ベクトル番号ｕｐｐｅｒの更新ステップであり、現在のｕｐｐｅｒ番の代表ベクトルの上位方向の隣の代表ベクトルの番号を新しいｕｐｐｅｒとして、ステップＦ５０８へ戻る。
【００３３】
次のステップＦ５１１は、入力ベクトルｘを代表ベクトルｗｍｉｎに符号化する。このステップＦ５１１において、入力ベクトルｘは、最小のひずみｄｃｕｒｍｉｎを持つ番号ｍｉｎの代表ベクトルｗｍｉｎに符号化される。
【００３４】
このベクトル量子化装置５００では、入力ベクトルが符号化される代表ベクトルを、入力ベクトルに対する代表ベクトルのひずみを判断指標として、任意のｋ次元を基準として代表ベクトルがソートされたコードブックから検索するので、一部分の代表ベクトルを検索するだけで全検索と同じ代表ベクトルを高速に選択することができる。
【００３５】
しかしながら、このベクトル量子化装置５００では、次の具体例のように、初期の代表ベクトルの番号をどのようにして選択するのかによって探索回数が大きく異なるため、探索処理の高速化が実現できない場合がある。
【００３６】
以下に示す具体例において、ベクトル量子化装置５００は、図１６に示すようなコードブックを参照して、入力ベクトルが符号化される代表ベクトルを探索する。
【００３７】
この具体例において、コードブックは、ｋ＝１の次元を基準として、ベクトル空間次元の値が３からなる代表ベクトルをソートしたものである。また、この具体例では、ひずみ測度として、以下の（１０）式のような二乗誤差ひずみ測度を用いている。
【００３８】
【数３】
2009021873.tif 000005
【００３９】
以上のような条件に基づいて、ベクトル量子化装置５００では、空間次元の値が３の入力ベクトルｘ＝（１２，１６，１３）に対して、次のような異なる２つの初期の代表ベクトルを設定して、コードブックを参照した代表ベクトルの探索処理を開始する。
【００４０】
まず、ベクトル量子化装置５００は、ｉ＝７の番号の代表ベクトルを初期の代表ベクトルとして選択して、上述した図１５に示したフローチャートに従った探索処理を開始すると、合計７個の代表ベクトルを探索することで、入力ベクトルに対して最もひずみの小さい代表ベクトルを得ることとなる。また、ベクトル量子化装置５００は、ｉ＝４の番号の代表ベクトルを初期の代表ベクトルとして選択して、上述した図１５のフローチャートに従った探索処理を開始すると、合計１０個の代表ベクトルを探索することで、入力ベクトルに対して最もひずみの小さい代表ベクトルが得られる。
【００４１】
以上のように、ベクトル量子化装置５００では、初期の代表ベクトルの番号に応じて、代表ベクトルを探索する合計回数が大きく異なってしまう。
【００４２】
特に、ベクトル量子化装置５００では、従来次のようにして初期の代表ベクトルの番号を設定しているため、探索回数が多くなってしまうことがあった。
【００４３】
従来のベクトル量子化装置５００では、直前のベクトル量子化処理において入力ベクトルが符号化された代表ベクトルを初期の代表ベクトルとして設定している。
【００４４】
このように初期の代表ベクトルを設定する理由としては、対象となるベクトルが静止画の画素データのとき、隣接する画素同士が同色である可能性が高く、また、対象となるベクトルが動画像の画素データのとき、時間的に前後するフレーム間の絵柄が似ている傾向があるからである。
【００４５】
しかしながら、上述した処理によって初期の代表ベクトルの設定した場合には、隣接する入力データ間の相関が小さいと、より探索回数が増大してしまう。これは、量子化対象のベクトルが静止画の画素データのとき、エッジ部分などでは画素データ間の相関が非常に小さいからであり、量子化対象のベクトルが動画像の画素データのとき、シーンチェンジなどではフレーム画像で前後のフレーム間で絵柄が全く異なるからである。また、量子化対象のベクトルが音声データの場合には、時間的に前後する入力データの相関が非常に小さい傾向にあるため、より探索回数が増大してしまう。
【００４６】
【特許文献１】特開２００２―２３２２９５号公報
【発明の開示】
【発明が解決しようとする課題】
【００４７】
本発明は、このような実情に鑑みて提案されたものであり、入力ベクトルを符号化する代表ベクトルをより高速に選択するベクトル量子化装置、及び、ベクトル量子化方法を提供することを目的とする。
【課題を解決するための手段】
【００４８】
上述した課題を解決するための手段として、本発明に係るベクトル量子化装置は、ｋ次元（ｋは自然数。）を基準としてソートされた代表ベクトルからなるコードブックを記憶した記憶手段と、入力ベクトルにおける上記ｋ次元の値の近傍に位置する上記代表ベクトルを、初期の代表ベクトルとして上記記憶手段に記憶されたコードブックから探索する探索手段と、上記入力ベクトルに対する上記代表ベクトルのひずみを計算して、上記記憶手段に記憶されたコードブックから次に探索する上記代表ベクトルのアドレスを計算する演算手段と、上記演算手段により計算された２つのひずみを比較して、上記入力ベクトルが符号化される上記代表ベクトルの候補を決める判定手段と、上記演算手段による演算処理と、上記判定手段による判定処理とを繰り返し行うように制御する制御手段とを備える。
【００４９】
また、本発明に係るベクトル量子化装置は、ｋ次元（ｋは自然数。）を基準として代表ベクトルがソートされたコードブックを記憶した記憶手段と、入力ベクトルにおける上記ｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとして上記記憶手段に記憶されたコードブックから探索する探索手段と、上記入力ベクトルに対する複数の上記代表ベクトルとのひずみを並列に計算して、上記記憶手段に記憶されたコードブックから次に探索する上記代表ベクトルのアドレスを計算する演算手段と、上記演算手段により計算された複数のひずみを比較して、上記入力ベクトルが符号化される上記代表ベクトルの候補を決める判定手段と、上記演算手段による演算処理と、上記判定手段による判定処理とを繰り返し行うように制御する制御手段とを備える。
【００５０】
また、本発明に係るベクトル量子化装置は、ｋ次元（ｋは自然数。）を基準としてソートされた代表ベクトルからなるコードブックを記憶した第１の記憶手段と、上記コードブックの代表ベクトルを上記ｋ次元を基準として並べ替えるソーティング手段と、上記ソーティング手段により並べ替えられた上記コードブックの代表ベクトルの並び順が記された第２の記憶手段と、入力ベクトルにおける上記ｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとして上記記憶手段に記憶されたコードブックから探索する探索手段と、上記入力ベクトルに対する上記代表ベクトルのひずみを計算して、上記第２の記憶手段に記憶されたコードブックの代表ベクトルの並び順から次に探索する上記代表ベクトルのアドレスを計算する演算手段と、上記演算手段により計算される２つのひずみを比較して、上記入力ベクトルが符号化される上記代表ベクトルの候補を決める判定手段と、上記演算手段による演算処理と、上記判定手段による判定処理とを繰り返し行うように制御する制御手段とを備える。
【００５１】
また、本発明に係るベクトル量子化装置は、ｋ次元（ｋは自然数。）を基準として代表ベクトルがソートされたコードブックを記憶する記憶手段と、上記コードブックの代表ベクトルを上記ｋ次元を基準として並び替えるソーティング手段と、入力ベクトルにおける上記ｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとして上記記憶手段に記憶されたコードブックから探索する探索手段と、上記入力ベクトルに対する複数の上記代表ベクトルとのひずみを並列に計算し、上記記憶手段に記憶されたコードブックから次に探索する上記代表ベクトルのアドレスを計算する演算手段と、上記演算手段により計算された複数のひずみを比較して、上記入力ベクトルが符号化される代表ベクトルの候補を決める判定手段と、上記演算手段による演算処理と、上記判定手段による判定処理とを繰り返し行うように制御する制御手段とを備える。
【００５２】
また、本発明に係るベクトル量子化方法は、所定の記憶手段に記憶されたｋ次元（ｋは自然数。）を基準としてソートされた代表ベクトルからなるコードブックから、入力ベクトルにおける上記ｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとして探索する探索ステップと、上記入力ベクトルと上記代表ベクトルのひずみを計算し、上記記憶手段に記憶されたコードブックから次に探索する上記代表ベクトルのアドレスを計算する演算ステップと、上記演算ステップにより計算された２つのひずみを比較して符号化される代表ベクトルの候補を決める判定ステップとからなり、上記演算ステップ及び上記判定ステップを繰り返し行う方法である。
【００５３】
また、本発明に係るベクトル量子化方法は、所定の記憶手段に記憶されたｋ次元（ｋは自然数。）を基準としてソートされた代表ベクトルからなるコードブックから、入力ベクトルにおける上記ｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとして探索する探索ステップと、上記入力ベクトルと複数の上記代表ベクトルとのひずみを並列に計算し、上記記憶手段に記憶されたコードブックから次に探索する上記代表ベクトルのアドレスを計算する演算ステップと、上記演算ステップにより計算された複数のひずみを比較して符号化される上記代表ベクトルの候補を決める判定ステップとからなり、上記演算ステップ及び上記判定ステップを繰り返し行う方法である。
【００５４】
また、本発明に係るベクトル量子化方法は、所定の記憶手段に記憶された複数の代表ベクトルからなるコードブックをｋ次元（ｋは自然数。）を基準として並べ替えるソーティングステップと、上記入力ベクトルにおける上記ｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとして上記記憶手段に記憶されたコードブックから探索する探索ステップと、上記入力ベクトルと上記代表ベクトルのひずみを計算し、上記記憶手段に記憶されたコードブックから次に探索する上記代表ベクトルのアドレスを計算する演算ステップと、上記演算ステップにより計算された２つのひずみを比較して、上記入力ベクトルが符号化される上記代表ベクトルの候補を決める判定ステップとからなり、上記演算ステップ及び上記判定ステップを繰り返し行う方法である。
【００５５】
また、本発明に係るベクトル量子化方法は、所定の記憶手段に記憶された複数の代表ベクトルからなるコードブックをｋ次元（ｋは自然数。）を基準として並べ替えるソーティングステップと、上記入力ベクトルにおける上記ｋ次元の値の近傍に位置するベクトルを、初期の代表ベクトルとして上記記憶手段に記憶されたコードブックから探索する探索ステップと、上記入力ベクトルと複数の上記代表ベクトルとのひずみを並列に計算し、上記記憶手段に記憶されたコードブックから次に探索する上記代表ベクトルのアドレスを計算する演算ステップと、上記演算ステップにより計算された複数のひずみを比較して、上記入力ベクトルが符号化される上記代表ベクトルの候補を決める判定ステップとからなり、上記演算ステップ及び上記判定ステップを繰り返し行う方法である。
【発明の効果】
【００５６】
本発明は、ｋ次元（ｋは自然数。）を基準としてソートされた代表ベクトルからなるコードブックから、入力ベクトルにおけるｋ次元の値の近傍に位置するベクトルを初期の代表ベクトルとして探索して、入力ベクトルに対する上記代表ベクトルのひずみを計算してコードブックから次に探索する代表ベクトルのアドレスを計算し、計算された２つのひずみを比較して入力ベクトルが符号化される代表ベクトルの候補を決めるので、コードブックを参照して代表ベクトルを探索する回数を低減することができ、入力ベクトルを符号化する代表ベクトルをより高速に選択することができる。
【発明を実施するための最良の形態】
【００５７】
以下、本発明を実施するための最良の形態について、図面を参照しながら詳細に説明する。
【００５８】
本発明は、例えば図１に示すような構成のベクトル量子化装置１００に適用される。
【００５９】
このベクトル量子化装置１００は、入力部１１０、ソーティング装置１２０、コードブックメモリ１３０、演算装置１４０、判定装置１５０、制御装置１６０、及び、初期代表ベクトル探索装置１７０から構成される。
【００６０】
このベクトル量子化装置１００において、入力部１１０は、入力端子１０１より新しいコードブックを受け取る。そして、この入力部１１０は、コードブックを記憶するコードブックメモリ１３０に、コードブックを書き込むアドレスと新しいコードブックを与える。
【００６１】
ソーティング装置１２０は、制御装置１６０からのソートの指示とどの次元を基準としてソートするかの指示を受け、コードブックメモリ１３０からコードブックを読み出し、指定された次元を基準としてコードブックをソートする。また、ソーティング装置１２０は、ソートしたコードブックをコードブックメモリ１３０の指定したアドレスに書き込む。
【００６２】
コードブックメモリ１３０は、入力部１１０から書き込むアドレスと新しいコードブックを受け取り、そのコードブックを指定されたアドレスに格納する。また、コードブックメモリ１３０は、コードブックをソーティング装置１２０に渡す。また、コードブックメモリ１３０は、ソーティング装置１２０によりソートされたコードブックと書き込むアドレスを受け取り、指定されたアドレスにコードブックを格納する。さらに、コードブックメモリ１３０は、ひずみ計算・アドレス計算を行う演算装置１４０から、アドレスを受け取り、代表ベクトルのデータ（代表ベクトルの値ｗｉ，番号ｉなど）を渡す。
【００６３】
演算装置１４０は、制御装置１６０からひずみ・アドレスの計算の指示を受け、コードブックメモリ１３０に読み込みたい代表ベクトルのアドレス（初期の代表ベクトルは制御装置１６０から指示される）を指定して、対応するデータ（代表ベクトルの番号と値）を読み込む。また、演算装置１４０は、後述する初期代表ベクトル探索装置１７０から入力ベクトルｘと初期の代表ベクトルｗｉとを受け取り、入力ベクトルと代表ベクトルとのひずみｄ（ｘ，ｗｉ）を計算する。そして、演算装置１４０は、ひずみｄ（ｘ，ｗｉ）とデータ（代表ベクトルの番号と値）を判定装置１５０に渡す。また、演算装置１４０は、制御装置１６０からソートの基準となったｋ次元の指示を受け、ｋ次元だけのひずみｄ（ｘｋ，ｗｉ ｋ）も判定装置１５０に渡す。さらに、演算装置１４０は、判定装置１５０から、判定結果により探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を受け、次の探索する代表ベクトルのアドレスを計算する。なお、演算装置１４０は、探索終了を示す情報ｆｉｎｉｓｈを受けた場合は、代表ベクトルの探索を終了する。
【００６４】
判定装置１５０は、現在の最小のひずみｄｃｕｒｍｉｎとその代表ベクトルの番号ｍｉｎを保持しており、現在の最小のひずみｄｃｕｒｍｉｎをもつｍｉｎ番の代表ベクトルと演算装置１４０により計算されたｉ番の代表ベクトルについてひずみｄ（ｘ，ｗｉ）を比較し、ひずみが小さい方を新しいｍｉｎ番、現在の最小のひずみｄｃｕｒｍｉｎとする。また、判定装置１５０は、制御装置１６０からの指示により、現在の最小のひずみを持つ代表ベクトルの番号ｍｉｎ（インデックス）、又は代表ベクトルの値を出力端子１０３に出力する。また、判定装置１５０は、制御装置１６０から判定の指示を受け、ｋ次元だけのひずみｄ（ｘｋ，ｗｉ ｋ）と現在の最小のひずみｄｃｕｒｍｉｎを比較し、ｄ（ｘｋ，ｗｉ ｋ）の方が大きければ、次に探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を変更し、また、ｕｐ／ｄｏｗｎ両方向とも調べ終わった場合には探索終了を示す情報ｆｉｎｉｓｈを演算装置１４０に渡し、ｄ（ｘｋ，ｗｉ ｋ）の方が小さければ、同方向の次の代表ベクトルを調べる情報を演算装置１４０に渡す。
【００６５】
制御装置１６０は、ソーティング装置１２０、演算装置１４０、及び、判定装置１５０の処理フローを制御する。また、制御装置１６０は、ソーティング装置１２０にソートの基準となる次元を指定する。また、制御装置１６０は、演算装置１４０に初期代表ベクトルのアドレス（又は番号）を指定し、また、ソートの基準となった次元を指示する。さらに、制御装置１６０は、判定装置１５０に出力端子１０３に出力するのが代表ベクトルの番号なのか、代表ベクトルの値なのかを指示する。
【００６６】
初期代表ベクトル探索装置１７０は、制御装置１６０から初期の体表ベクトルの探索の指示を受け、コードブックメモリ１３０に読み込みたい代表ベクトルの番号を指定して、対応するデータ（代表ベクトルの番号と値）を読み込む。初期代表ベクトル探索装置１７０は、入力端子１０２から入力ベクトルｘを受け取り、入力ベクトルに対してｋ次元の値が略最も近いベクトル、すなわち、入力ベクトルにおけるｋ次元の値の近傍に位置するベクトルを探索するため、例えば、入力ベクトルのｋ次元の値ｘｋと代表ベクトルのｋ次元の値ｗｉ ｋが次の（１１）式となる代表ベクトルｗｉを探索する。
ｗｉ ｋ≦ｘｋ＜ｗｉ＋１ ｋ  ・・・（１１）
【００６７】
そして、初期代表ベクトル探索装置１７０は、入力ベクトルｘと（１１）式により探索して求まった代表ベクトルｗｉを初期の代表ベクトルとして、演算装置１４０に供給する。
【００６８】
このような構成のベクトル量子化装置１００では、図２のフローチャートに示す符号化アルゴリズムに従ってソートされた代表ベクトルを用いた高速ベクトル量子化（Vector Quantizationby Searching in Sirted Codebook：ＶＱ−ＳＳＣ）を行う。
【００６９】
すなわち、このベクトル量子化装置１００では、先ず、ステップＦ１０１において代表ベクトルをソートするための基準のｋ次元を指定する。
【００７０】
次のステップＦ１０２では、ｋ次元の代表ベクトルの値に基づいて代表ベクトルを、例えば次の２つの方法によりソートする。
【００７１】
第１の方法は、直接代表ベクトルの順番を入れ替える方法である。代表ベクトルの番号を変更したくないときは、代表ベクトルの番号の情報を持つ構造体にして入れ替える。
【００７２】
直接並べ替えているので、現在の代表ベクトルの番号より下位の代表ベクトルの番号ｌｏｗｅｒは、現在の配列の番号から１を減じた配列の番号となり、現在の代表ベクトルの番号より上位の代表ベクトルの番号ｕｐｐｅｒは、現在の配列の番号に１を加えた配列の番号となる。
【００７３】
第２の方法としては、ソートしたときの順番を示す配列を用意するものである。この方法において、各代表ベクトルが保持すべき情報は、現在の代表ベクトルの番号より下位の代表ベクトルの番号ｌｏｗｅｒと、現在の代表ベクトルの番号より上位の代表ベクトルの番号ｕｐｐｅｒである。
【００７４】
次のステップＦ１０３−１では、入力ベクトルｘのｋ次元の値ｘｋと代表ベクトルのｋ次元の値ｗｉ ｋが下記の（１２）式となるようなｗｉを探索する。
ｗｉ ｋ≦ｘｋ＜ｗｉ＋１ ｋ  ・・・（１２）
【００７５】
具体的な探索方法としては、例えば、以下の２通りの方法がある。
【００７６】
第１の方法は、まずｉの値を０に設定して、ｉの値を順次ｉ＋１に更新して（１２）式の条件を満たすようなｗｉを探索するという方法である。
【００７７】
第２の方法は、入力ベクトルのｋ次元における上位ビットの値と初期の代表ベクトルの探索を開始するアドレスとを対応付けたテーブルを参照して、ｗｉを探索するという方法である。例えば、画像に関するデータをベクトル量子化するとき、８ビットのデータサイズからなる画素データの上位３ビットの値と、初期の代表ベクトルの探索を開始するアドレスとを対応付けたテーブルとして、例えば下記の表で示されるテーブルを、予め初期代表ベクトル探索装置１７０の内部メモリに記憶しておく。
【００７８】
【表１】
2009021873.tif 000006
【００７９】
そして、初期代表ベクトル探索装置１７０は、このテーブルを参照して、入力ベクトルのｋ次元における上位３ビットの値に対応する探索開始番号を探索して、その後、探索開始番号をｉに設定して、その後はｉの値を順次ｉ＋１に更新して（１２）式の条件を満たすｗｉを探索する。また、音声信号に関するデータをベクトル量子化するときは、−１≦ｘｋ≦１のような範囲をとるので、表のように８個のテーブルを作るときは下記の（１３）式で算出される値の整数部と、初期の代表ベクトルの探索を開始するアドレスとを対応付けたテーブルを用いるようにすればよい。
【００８０】
【数４】
2009021873.tif 000007
【００８１】
次のステップＦ１０３−２では、入力ベクトルｘと初期の代表ベクトルｗｉとのひずみの計算を行い、このひずみｄ（ｘ，ｗｉ）を現在の最小のひずみｄｃｕｒｍｉｎとし、番号ｉを符号化の候補として次の式（１４）、及び、式（１５）となるように各値を保存しておく。
ｄｃｕｒｍｉｎ＝ｄ（ｘ，ｗｉ）  ・・・（１４）
ｍｉｎ＝ｉ  ・・・（１５）
【００８２】
次のステップＦ１０４では、初期の代表ベクトルｗｉの両隣の代表ベクトルの番号を以下のように保存する。
ｌｏｗｅｒ＝下位方向の隣の代表ベクトルの番号
ｕｐｐｅｒ＝上位方向の隣の代表ベクトルの番号
【００８３】
次のステップＦ１０５では、入力ベクトルｘとｌｏｗｅｒ番の代表ベクトルｗｌｏｗｅｒとのひずみｄ（ｘ，ｗｌｏｗｅｒ）の計算を行い、計算途中のｄ（ｘｋ，ｗｌｏｗｅｒｋ）を保存しておく。
【００８４】
次のステップＦ１０６では、ステップＦ１０５で計算したひずみｄ（ｘ，ｗｌｏｗｅｒ）が現在の最小のひずみｄｃｕｒｍｉｎより小さいか否か、すなわち次の（１６）式が成り立つか否かを判定する。
ｄ（ｘ，ｗｌｏｗｅｒ）＜ｄｃｕｒｍｉｎ  ・・・（１６）
もし、この（１６）式が成り立つならば、次のステップＦ１０７へ進み、さもなければ、ステップＦ１０８へ移る。
【００８５】
ステップＦ１０７は、代表ベクトルの番号ｌｏｗｅｒの更新ステップであり、現在のｌｏｗｅｒ番の代表ベクトルの下位方向の隣の代表ベクトルの番号を新しいｌｏｗｅｒとして、ステップＦ１０５へ戻る。
【００８６】
ステップＦ１０８では、入力ベクトルｘとｕｐｐｅｒ番の代表ベクトルｗｕｐｐｅｒとのひずみｄ（ｘ，ｗｕｐｐｅｒ）の計算を行い、計算途中のｄ（ｘｋ，ｗｕｐｐｅｒｋ）を保存しておく。そして、計算したひずみｄ（ｘ，ｗｕｐｐｅｒ）が現在の最小のひずみｄｃｕｒｍｉｎより小さいか否か、すなわち、次の（１７）式が成り立つか否かを判定する。
ｄ（ｘ，ｗｕｐｐｅｒ）＜ｄｃｕｒｍｉｎ  ・・・（１７）
もし、この（１７）式が成り立つならば、次の（１８）式及び（１９）式のように各値を設定する。
ｄｃｕｒｍｉｎ＝ｄ（ｘ，ｗｕｐｐｅｒ）  ・・・（１８）
ｍｉｎ＝ｕｐｐｅｒ  ・・・（１９）
【００８７】
次のステップＦ１０９では、上位方向の探索を続けるかどうか判断する。もし、次の（２０）式を満足するなら、上位方向の探索は終了で、ステップＦ１１１へ移り、さもなければ、次のステップＦ１１０へ進む。
ｄ（ｘｋ，ｗｕｐｐｅｒｋ）＞ｄｃｕｒｍｉｎ  ・・・（２０）
【００８８】
ステップＦ１１０は、代表ベクトル番号ｕｐｐｅｒの更新ステップであり、現在のｕｐｐｅｒ番の代表ベクトルの上位方向の隣の代表ベクトルの番号を新しいｕｐｐｅｒとして、ステップＦ１０８へ戻る。
【００８９】
次のステップＦ１１１では、入力ベクトルｘを代表ベクトルｗｍｉｎに符号化する。このステップＦ１１１において、入力ベクトルｘは、最小のひずみｄｃｕｒｍｉｎを持つ番号ｍｉｎの代表ベクトルｗｍｉｎに符号化される。
【００９０】
ここで、このベクトル量子化装置１００におけるベクトル量子化の符号化アルゴリズム（ＶＱ−ＳＳＣ）の動作について以下の具体例を用いて説明する。なお、この具体例では、ひずみ測度として次の（２１）式による二乗誤差ひずみ測度を用いている。
【００９１】
【数５】
2009021873.tif 000008
【００９２】
当然、このほかのひずみ測度を用いた場合も、本発明は有効である。また、次元ごとに違うひずみ測度を用いたときも、本発明は有効である。
【００９３】
３次元の入力ベクトルｘ＝（１２，１６，１３）に対して、この具体例では、図３に示すような、最小ひずみ８を持つ９番の代表ベクトルｗ９＝（１４，１８，３）に符号化される処理を行う。
【００９４】
ベクトル量子化の符号化アルゴリズム（ＶＱ−ＳＳＣ）では、ｋ＝１に対して代表ベクトルをソートしてある。わかりやすいようにソートした順に代表ベクトルの番号をつけた状態にしてある。実際は、わざわざ代表ベクトルの番号をつけ直す必要ななく、自身の代表ベクトルの両隣（上位方向・下位方向）の代表ベクトルの番号を保存するようにプログラムすればよい。
【００９５】
ここで、もし、符号化される代表ベクトルが事前にわかっているならば、最小ひずみが８なので、√８以下の最大の整数、すなわち、２以下の範囲を探索すればよい。図３から、１次元で１２±２となる代表ベクトルは、７番目、８番目、及び、９番目の合計３個の代表ベクトルだけを調べればよい。
【００９６】
しかし、事前に符号化される代表ベクトルがわかるはずがないので、次のようなアルゴリズム（探索０〜探索６）を用いて探索をすることになる。
【００９７】
すなわち、探索０では、入力ベクトルｘの１次元の値が１２なので、図４に示すように、初期の代表ベクトルを７番目の代表ベクトルに設定して、ひずみｄ（ｘ，ｗ７）を計算して、次のような計算結果を得る。
ｄ（ｘ，ｗ７）＝１７
ｌｏｗｅｒ＝６
ｕｐｐｅｒ＝８
そして、最小のひずみｄｃｕｒｍｉｎ＝１７とその代表ベクトルの番号ｍｉｎ＝７を保存する。
【００９８】
探索１では、図５に示すように、ｌｏｗｅｒの値を参照して６番目の代表ベクトルのひずみｄ（ｘ，ｗｌｏｗｅｒ）を計算して、次のような計算結果を得る。
ｄ（ｘ１，ｗｌｏｗｅｒ１）＝９
ｄ（ｘ，ｗｌｏｗｅｒ）＝１８９
そして、ｄ（ｘ，ｗｌｏｗｅｒ）と現在の最小のひずみｄｃｕｒｍｉｎとを比較すると、ｄ（ｘ，ｗｌｏｗｅｒ）はｄｃｕｒｍｉｎよりも大きいので、最小のひずみｄｃｕｒｍｉｎは、次のようにそのままの値を保持する。
ｄｃｕｒｍｉｎ＝１７
ｍｉｎ＝７
また、ｄ（ｘ１，ｗｌｏｗｅｒ１）は現在の最小のひずみｄｃｕｒｍｉｎよりも小さいので、次のｌｏｗｅｒ＝５の探索２に移る。
【００９９】
次の探索２では、図６に示すように、ｌｏｗｅｒの値を参照して５番目の代表ベクトルのひずみｄ（ｘ，ｗｌｏｗｅｒ）を計算して、次のような計算結果を得る。
ｄ（ｘ１，ｗｌｏｗｅｒ１）＝９
ｄ（ｘ，ｗｌｏｗｅｒ）＝１４
そして、ｄ（ｘ，ｗｌｏｗｅｒ）と現在の最小のひずみｄｃｕｒｍｉｎとを比較すると、ｄ（ｘ，ｗｌｏｗｅｒ）はｄｃｕｒｍｉｎよりも小さいので、最小のひずみｄｃｕｒｍｉｎを更新して、各値を次のようにする。
ｄｃｕｒｍｉｎ＝１４
ｍｉｎ＝５
また、ｄ（ｘ１，ｗｌｏｗｅｒ１）はｄｃｕｒｍｉｎ＝１４よりも小さいので、次のｌｏｗｅｒ＝４の探索３に移る。
【０１００】
探索３では、図７に示すように、ｌｏｗｅｒの値を参照して４番目の代表ベクトルのひずみを計算を行う。
ｄ（ｘ１，ｗｌｏｗｅｒ１）＝１６
ｄ（ｘ，ｗｌｏｗｅｒ）＝１８６
そして、ｄ（ｘ，ｗｌｏｗｅｒ）と現在の最小のひずみｄｃｕｒｍｉｎとを比較すると、ｄ（ｘ，ｗｌｏｗｅｒ）はｄｃｕｒｍｉｎよりも大きいので、最小のひずみｄｃｕｒｍｉｎは、次のようにそのままの値を保持する。
ｄｃｕｒｍｉｎ＝１４
ｍｉｎ＝５
また、ｄ（ｘ１，ｗｌｏｗｅｒ１）はｄｃｕｒｍｉｎ＝１４よりも大きいので、下位方向の探索は終了し、次にｕｐｐｅｒ＝８の上位方向の探索４に移る。
【０１０１】
探索４では、図８に示すように、ｕｐｐｅｒの値を参照して８番目の代表ベクトルのひずみを計算して、次のような計算結果を得る。
ｄ（ｘ１，ｗｕｐｐｅｒ１）＝１
ｄ（ｘ，ｗｕｐｐｅｒ）＝４６
そして、ｄ（ｘ，ｗｕｐｐｅｒ）と現在の最小のひずみｄｃｕｒｍｉｎとを比較すると、ｄ（ｘ，ｗｌｏｗｅｒ）はｄｃｕｒｍｉｎよりも大きいので、最小のひずみｄｃｕｒｍｉｎは、次のようにそのままの値を保持する。
ｄｃｕｒｍｉｎ＝１４
ｍｉｎ＝５
また、ｄ（ｘ１，ｗｕｐｐｅｒ１）はｄｃｕｒｍｉｎ＝１４よりも小さいので、次のｕｐｐｅｒ＝９の探索５に移る。
【０１０２】
探索５では、図９に示すように、ｕｐｐｅｒの値を参照して９番目の代表ベクトルのひずみを計算する。
ｄ（ｘ１，ｗｕｐｐｅｒ１）＝４
ｄ（ｘ，ｗｕｐｐｅｒ）＝８
そして、ｄ（ｘ，ｗｕｐｐｅｒ）と現在の最小のひずみｄｃｕｒｍｉｎとを比較すると、ｄ（ｘ，ｗｌｏｗｅｒ）はｄｃｕｒｍｉｎよりも小さいので、最小のひずみｄｃｕｒｍｉｎを更新して、各値を次のようにする。
ｄｃｕｒｍｉｎ＝８
ｍｉｎ＝９
また、ｄ（ｘ１，ｗｕｐｐｅｒ１）はｄｃｕｒｍｉｎ＝９よりも小さいので、次のｕｐｐｅｒ＝１０の探索６に移る。
【０１０３】
探索６では、図１０に示すように、ｕｐｐｅｒの値を参照して１０番目の代表ベクトルのひずみを計算して、次のような計算結果を得る。
ｄ（ｘ１，ｗｕｐｐｅｒ１）＝９
ｄ（ｘ，ｗｕｐｐｅｒ）＝４１
そして、ｄ（ｘ，ｗｕｐｐｅｒ）と現在の最小のひずみｄｃｕｒｍｉｎとを比較すると、ｄ（ｘ，ｗｌｏｗｅｒ）はｄｃｕｒｍｉｎよりも大きいので、最小のひずみｄｃｕｒｍｉｎは、次のようにそのままの値を保持する。
ｄｃｕｒｍｉｎ＝８
ｍｉｎ＝９
また、（ｘ１，ｗｕｐｐｅｒ１）はｄｃｕｒｍｉｎ＝９よりも大きいので、上位方向の探索を終了する。
【０１０４】
このようにして下位方向、上位方向、両方とも探索を終了し、最終的に得られた最小のひずみｄｃｕｒｍｉｎ＝８をもつｍｉｎ＝９番の代表ベクトルが入力ベクトルｘ＝（１２，１６，１３）に対する符号化される代表ベクトルである。
【０１０５】
ここで、図１１に示すように、あらかじめ符号化される代表ベクトルがわかっている場合は３個の代表ベクトルを探索すれば十分であるが、一般には無理なので初期代表ベクトルを決めて探索する必要がある。今回の場合、最小ひずみを更新しながら探索したので、７個の代表ベクトルを探索することで最小のひずみを持つ代表ベクトルを得ることができた。これが階調変換では、代表ベクトルの数が２５６個あるので、探索範囲を大幅に制限することが期待できる。
【０１０６】
以上、このベクトル量子化装置１００におけるベクトル量子化の符号化アルゴリズム（ＶＱ−ＳＳＣ）の動作についての具体例を説明したが、次に、上記ベクトル量子化装置１００による音声データの符号化のシミュレーション結果について説明する。
【０１０７】
ベクトル量子化装置１００による音声データのベクトル量子化の具体例として、ＭＰＥＧ４ＣＥＬＰ方式による符号化処理を取り上げる。
【０１０８】
前提として、ＭＰＥＧ４ＣＥＬＰ方式では、音声データである５次元の入力ベクトルに対してベクトル量子化が行われている。また、代表ベクトルは、合計６４個である。
【０１０９】
本具体例では、以下に示す従来手法と、上述したベクトル量子化装置１００で行われる手法との比較を行った結果を以下の表に示す。
【０１１０】
【表２】
2009021873.tif 000009
【０１１１】
ここで、従来手法とは、上述した図２に示すフローチャートに従った処理工程のうち、ステップＦ１０３−１に係る初期の代表ベクトルの探索工程を行う代わりに、直前のベクトル量子化処理において入力ベクトルが符号化された代表ベクトルを初期の代表ベクトルとして設定する処理を行う手法である。
【０１１２】
以上の表２に示すように、従来手法では、平均探索回数が５０．３８回であり、全探索手法での探索回数である６４回に対する割合が７８．７１％であるため、全探索手法に比べてより高速に入力ベクトルが符号化される代表ベクトルを探索することができる。これに対して、ベクトル量子化装置１００による本実施形態に係る探索手法では、上述した従来手法よりも平均探索回数が３８．９６回であり、全探索手法での探索回数に対する割合が６０．８８％と従来手法に対して約１８％の削減が実現できている。
【０１１３】
また、本実施形態に係る探索手法は、上述した従来手法に比べて、初期の代表ベクトルを探索する処理工程に係る処理量が増えるが、入力ベクトルを入力してから符号化された代表ベクトルを探索するまでの全処理工程に係るサイクル数が従来手法の３３．０Ｍｃから２２．６Ｍｃに減少している。したがって、従来手法に比べて、初期の代表ベクトルを探索する処理工程に係る処理量が増えているが、これによって、探索処理量が大きく増大するような影響はない。
【０１１４】
以上のようなシミュレーション結果により、本実施形態に係るベクトル量子化装置１００では、従来手法と比較して入力ベクトルが符号化される代表ベクトルを探索するまでの平均的な探索回数を低減することができる。また、ベクトル量子化装置１００では、初期の代表ベクトルを探索する操作によって、ベクトル量子化処理全体での処理量が大きく増大するという影響がない。
【０１１５】
したがって、本実施形態に係るベクトル量子化装置１００では、ベクトル量子化処理に係るサイクル数を削減することができ、これによって、より高速に入力ベクトルが符号化される代表ベクトルをコードブックから探索することができる。
【０１１６】
また、ベクトル量子化装置１００では、入力ベクトルに対する上記代表ベクトルのひずみを各次元毎に算出した値の積算値であるひずみの部分和を用いた高速化手法を組み合わせるとより一層の効果がある。具体的に、ひずみの部分和を用いた高速化手法は、上述したステップＦ１０６及び、Ｆ１０９において、（２２）式で示されるひずみの部分和が現在の最小のひずみｄｃｕｒｍｉｎと比較して大きいときは、次の代表ベクトルを探索するという手法である。
【０１１７】
【数６】
2009021873.tif 000010
【０１１８】
すなわち、ひずみを最後まで求めるのではなく、計算途中のひずみと現在の最小のひずみを比較することで探索の効率をあげる手法である。このひずみの部分和を用いた高速化手法は、文献［Bei C-D. & Gray,R. M..“An improvement of minimum distortion encoding algorithm for vector quantization.” IEEE Transactions on Communications, COM-33, pp.1132-1133,1985.］に詳述されている。
【０１１９】
次に、上述の図１に示したベクトル量子化装置１００の変形例として、図１２を参照して、図１に示したベクトル量子化装置１００と異なる部分についてのみを説明する。
【０１２０】
コードブックメモリ１３０は、コードブックとアドレスをソーティング装置１２０に渡す。
【０１２１】
ソーティング装置１２０は、制御装置１６０からのソートの指示とどの次元を基準としてソートするかの指示を受け、コードブックメモリ１３０からコードブックのアドレスとコードブックを読み出し、指定された次元を基準としてコードブックをソートする。そして、そのソートされた代表ベクトルの順番通りに、各代表ベクトルのアドレスを並び替え、ソート順に並んだアドレスをコードブックソート表１８０に書き込む。
【０１２２】
演算装置１４０は、判定装置１５０から、判定結果により探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を受け、次の探索する代表ベクトルのアドレスをコードブックソート表１８０に参照して、アドレスを受け取る。そして、コードブックメモリ１３０に、そのアドレスを指定して、対応するデータ（代表ベクトルの番号と値）を読み込む。
【０１２３】
そして、コードブックソート表１８０は、ソーティング装置１２０から受け取ったアドレスを格納する。また、コードブックソート表１８０は、演算装置１４０からの次の探索する代表ベクトルの参照の指示に従って、その代表ベクトルのアドレスを演算装置１４０に渡す。
【０１２４】
以上のように、ベクトル量子化装置１００では、一部分の代表ベクトルを探索するだけで全探索と同じ代表ベクトルを高速に選択することができる。さらに、ベクトル量子化装置１００では、上述した従来方法と比較して、ｋ次元（ｋは自然数。）を基準としてソートされた代表ベクトルからなるコードブックから、入力ベクトルにおけるｋ次元の値の近傍に位置するベクトルを初期の代表ベクトルとして探索して、入力ベクトルに対する代表ベクトルのひずみを計算してコードブックから次に探索する代表ベクトルのアドレスを計算し、計算された２つのひずみを比較して入力ベクトルが符号化される代表ベクトルの候補を決めるので、コードブックを参照して代表ベクトルを探索する回数をできるだけ低減するように初期の代表ベクトルを設定することができ、入力ベクトルを符号化する代表ベクトルをより高速に選択することができる。
【０１２５】
なお、本発明は、以上の実施形態のみに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変更が可能であることは勿論である。
【図面の簡単な説明】
【０１２６】
【図１】本発明を適用したベクトル量子化装置の構成を示すブロック図である。
【図２】ベクトル量子化装置におけるベクトル量子化の符号化アルゴリズム（ＶＱ−ＳＳＣ）を示すフローチャートである。
【図３】全探索による代表ベクトルの探索の例を示す図である。
【図４】符号化アルゴリズム（ＶＱ−ＳＳＣ）による代表ベクトルの探索例（探索０）を示す図である。
【図５】代表ベクトルの探索例（探索１）を示す図である。
【図６】代表ベクトルの探索例（探索２）を示す図である。
【図７】代表ベクトルの探索例（探索３）を示す図である。
【図８】代表ベクトルの探索例（探索４）を示す図である。
【図９】代表ベクトルの探索例（探索５）を示す図である。
【図１０】代表ベクトルの探索例（探索６）を示す図である。
【図１１】符号化アルゴリズム（ＶＱ−ＳＳＣ）の探索範囲を示す図である。
【図１２】本発明を適用したベクトル量子化装置の構成を示す図である。
【図１３】ベクトル量子化の概念図である。
【図１４】従来のベクトル量子化装置の構成を示すブロック図である。
【図１５】従来のベクトル量子化装置におけるベクトル量子化の符号化アルゴリズム（ＶＱ−ＳＳＣ）を示すフローチャートである。
【図１６】初期の代表ベクトルとして設定した番号に応じて変化する探索回数を示す図である。
【符号の説明】
【０１２７】
１００、５００  ベクトル量子化装置、１０１、１０２、５０１、５０２  入力端子、１０３、５０３  出力端子、１１０、５１０  入力部、１２０、５２０  ソーティング装置、１３０、５３０  コードブックメモリ、１４０、５４０  演算装置、１５０、５５０  判定装置、１６０、５６０  制御装置、１７０  初期代表ベクトル探索装置、１８０  コードブックソート表
【図１】
2009021873.tif 000011
【図２】
2009021873.tif 000012
【図３】
2009021873.tif 000013
【図４】
2009021873.tif 000014
【図５】
2009021873.tif 000015
【図６】
2009021873.tif 000016
【図７】
2009021873.tif 000017
【図８】
2009021873.tif 000018
【図９】
2009021873.tif 000019
【図１０】
2009021873.tif 000020
【図１１】
2009021873.tif 000021
【図１２】
2009021873.tif 000022
【図１３】
2009021873.tif 000023
【図１４】
2009021873.tif 000024
【図１５】
2009021873.tif 000025
【図１６】
2009021873.tif 000026