"ベクトル量子化符号化またはベクトル量子化復号における,規則的な量子化代表ベクトルの並びに基づくエントロピ拘束型ベクトル量子化方法であって,量子化代表ベクトル群の原点からの距離を示すN個の半径ci0≦i≦N-1,c0<c1<...<cN1となる実数とN個の分割数Ki2Kiは1以上の整数を入力するステップと,量子化すべきベクトルvを入力するステップと,前記ベクトルvの全要素の絶対値の最大値がci1以上ci未満となるような整数iを求めるステップと,間隔qi1=ci1/Ki1を得るステップと,ベクトルの全要素の絶対値の最大値がci1でベクトル要素の値が-ci1kqi1kは整数,0≦k≦2Ki1となるようなベクトルのうち,前記ベクトルvと最もユークリッド距離が近いベクトルv′i1を求めるステップと,間隔qi=ci/Kiを得るステップと,ベクトルの全要素の絶対値の最大値がciでベクトル要素の値が-cikqikは整数,0≦k≦2Kiとなるようなベクトルのうち,前記ベクトルvと最もユークリッド距離が近いベクトルv′iを求めるステップと,前記ベクトルvを,前記ベクトルv′i1または前記ベクトルv′iのいずれにベクトル量子化した場合のラグランジュコストが小さいかを判定するステップと,より小さいラグランジュコストを与える前記ベクトルv′i1または前記ベクトルv′iを,前記ベクトルvのベクトル量子化結果として出力するステップとを有することを特徴とするベクトル量子化方法。ベクトル量子化符号化またはベクトル量子化復号における,規則的な量子化代表ベクトルの並びに基づくエントロピ拘束型ベクトル量子化方法であって,量子化代表ベクトル群の原点からの距離を示すN個の半径ci0≦i≦N-1,c0<c1<...<cN1となる実数とN個の分割数KiKiは1以上の整数を入力するステップと,量子化すべきベクトルvを入力するステップと,前記ベクトルvの全要素の絶対値和がci1以上ci未満となるような整数iを求めるステップと,間隔qi1=ci1/Ki1を得るステップと,ベクトルの全要素の絶対値和がci1でベクトル要素の値が-ci1kqi1kは整数,0≦k≦2Ki1となるようなベクトルのうち,前記ベクトルvと最もユークリッド距離が近いベクトルv′i1を求めるステップと,間隔qi=ci/Kiを得るステップと,ベクトルの全要素の絶対値和がciでベクトル要素の値が-cikqikは整数,0≦k≦2Kiとなるようなベクトルのうち,前記ベクトルvと最もユークリッド距離が近いベクトルv′iを求めるステップと,前記ベクトルvを,前記ベクトルv′i1または前記ベクトルv′iのいずれにベクトル量子化した場合のラグランジュコストが小さいかを判定するステップと,より小さいラグランジュコストを与える前記ベクトルv′i1または前記ベクトルv′iを,前記ベクトルvのベクトル量子化結果として出力するステップとを有することを特徴とするベクトル量子化方法。ベクトル量子化符号化またはベクトル量子化復号における,規則的な量子化代表ベクトルの並びに基づくエントロピ拘束型ベクトル量子化装置であって,量子化代表ベクトル群の原点からの距離を示すN個の半径ci0≦i≦N-1,c0<c1<...<cN1となる実数とN個の分割数Ki2Kiは1以上の整数を入力する手段と,量子化すべきベクトルvを入力する手段と,前記ベクトルvの全要素の絶対値の最大値がci1以上ci未満となるような整数iを求める手段と,間隔qi1=ci1/Ki1を得る手段と,ベクトルの全要素の絶対値の最大値がci1でベクトル要素の値が-ci1kqi1kは整数,0≦k≦2Ki1となるようなベクトルのうち,前記ベクトルvと最もユークリッド距離が近いベクトルv′i1を求める手段と,間隔qi=ci/Kiを得る手段と,ベクトルの全要素の絶対値の最大値がciでベクトル要素の値が-cikqikは整数,0≦k≦2Kiとなるようなベクトルのうち,前記ベクトルvと最もユークリッド距離が近いベクトルv′iを求める手段と,前記ベクトルvを,前記ベクトルv′i1または前記ベクトルv′iのいずれにベクトル量子化した場合のラグランジュコストが小さいかを判定する手段と,より小さいラグランジュコストを与える前記ベクトルv′i1または前記ベクトルv′iを,前記ベクトルvのベクトル量子化結果として出力する手段とを備えることを特徴とするベクトル量子化装置。ベクトル量子化符号化またはベクトル量子化復号における,規則的な量子化代表ベクトルの並びに基づくエントロピ拘束型ベクトル量子化装置であって,量子化代表ベクトル群の原点からの距離を示すN個の半径ci0≦i≦N-1,c0<c1<...<cN1となる実数とN個の分割数KiKiは1以上の整数を入力する手段と,量子化すべきベクトルvを入力する手段と,前記ベクトルvの全要素の絶対値和がci1以上ci未満となるような整数iを求める手段と,間隔qi1=ci1/Ki1を得る手段と,ベクトルの全要素の絶対値和がci1でベクトル要素の値が-ci1kqi1kは整数,0≦k≦2Ki1となるようなベクトルのうち,前記ベクトルvと最もユークリッド距離が近いベクトルv′i1を求める手段と,間隔qi=ci/Kiを得る手段と,ベクトルの全要素の絶対値和がciでベクトル要素の値が-cikqikは整数,0≦k≦2Kiとなるようなベクトルのうち,前記ベクトルvと最もユークリッド距離が近いベクトルv′iを求める手段と,前記ベクトルvを,前記ベクトルv′i1または前記ベクトルv′iのいずれにベクトル量子化した場合のラグランジュコストが小さいかを判定する手段と,より小さいラグランジュコストを与える前記ベクトルv′i1または前記ベクトルv′iを,前記ベクトルvのベクトル量子化結果として出力する手段とを備えることを特徴とするベクトル量子化装置。請求項1または請求項2に記載のベクトル量子化方法を,コンピュータに実行させるためのベクトル量子化プログラム。請求項1または請求項2に記載のベクトル量子化方法を,コンピュータに実行させるためのベクトル量子化プログラムを記録したコンピュータ読み取り可能な記録媒体。ベクトル量子化では,量子化代表ベクトルの配置を任意とした場合が最も自由度が高く,理想的なラグランジュコストが小さくなるベクトル量子化となる。しかし,ベクトルの配置設計や量子化符号化といった処理は,量子化代表ベクトルの個数に応じて増加するため,量子化代表ベクトルの個数は数千が限度である。例えば16次元で1[bit/sample]でベクトル量子化符号化する場合,およそ2161=65536個の代表ベクトルが必要であり,処理量が膨大になってしまう。そこで,ピラミッドベクトル量子化のように格子点を基本としたベクトル量子化において,実用的に処理可能な範囲内で,より高い自由度でベクトル量子化を最適化する技術が望まれる。本発明は上記問題点の解決を図り,高い符号化効率を実現でき,かつ処理が簡易であるベクトル量子化の技術を提供することを目的とする。本発明は上記課題を解決し,ピラミッドベクトル量子化のように格子点を基本としたベクトル量子化において,エントロピ拘束型ベクトル量子化を,より高い自由度で最適化するため,代表ベクトルの配置設計における自由度として,代表ベクトル群の原点からの距離と,各距離に対して一対一に対応する分割数整数値との2自由度を有することを,もっとも主要な特徴とする。本発明において,上記代表ベクトル群の原点からの距離の尺度として,ベクトルの全要素の絶対値和を用いることができる。これは,L∞ノルムを距離尺度として用いることに相当する。また,本発明は,原点からの距離の尺度として,ベクトルの全要素の絶対値の最大値を用いることもできる。これは,L1ノルムを距離尺度として用いることに相当する。本発明の特徴は,次のように捉えることもできる。すなわち,本発明は,エントロピ拘束型ベクトル量子化において,零ベクトルを量子化代表ベクトルの一つとして保持する手段と,量子化代表ベクトル群の原点からの距離を示すN個の半径ci0≦i≦N-1,c0<c1<...<cN1となる実数とN個の分割数Ki2Kiは1以上の整数を入力する手段と,あるi0≦i≦N-1において,間隔q=ci/Kiを得る手段と,ベクトルvの要素の絶対値のうち最大値がciであり,ベクトルvの要素の値が-cikqkは整数,0≦k≦2Kiとなっているベクトルvを量子化代表ベクトルとする手段と,前記量子化代表ベクトルに基づきベクトル量子化または逆量子化を行う手段とを備えることを特徴とする。また,本発明は,エントロピ拘束型ベクトル量子化において,零ベクトルを量子化代表ベクトルの一つとして保持する手段と,量子化代表ベクトル群の原点からの距離を示すN個の半径ci0≦i≦N-1,c0<c1<...<cN1となる実数とN個の分割数KiKiは1以上の整数を入力する手段と,あるi0≦i≦N-1において,間隔q=ci/Kiを得る手段と,ベクトルvの要素の絶対値の和がciであり,ベクトルvの要素の絶対値がkqkは整数,0≦k≦Kiとなっているベクトルvを量子化代表ベクトルとする手段と,前記量子化代表ベクトルに基づきベクトル量子化または逆量子化を行う手段とを備えることを特徴とする。本発明によれば,規則的計算容易ながら従来よりもより柔軟な量子化代表ベクトルの配置を実現することができ,結果として,より低いラグランジュコスト,すなわち,より高い符号化効率を実現することができるようになる。まず,本発明の実施形態についての考え方の概要を簡単に説明する。本発明では,量子化代表ベクトルの位置を,原点を中心とする多次元の立方体超立方体の表面に存在する格子点に限定する図1,図2参照。ただし,超立方体は複数存在し,その一辺の長さ2ciを可変とする図8のフローチャートのステップ102。また,格子点の間隔も,一辺の長さの整数2K1分の1とし,これを可変とする図8のフローチャートのステップ106。このように量子化代表ベクトルの配置を規則的としながら,従来よりも自由度の高い配置をとること図2,図7参照により,量子化符号化において,これら自由度の最適化を施すことで図8のフローチャート全体,従来よりも低いラグランジュコストを実現する。量子化代表ベクトル多次元の立方体超立方体の表面に存在する格子点配置が規則的なため,量子化逆量子化が簡易である。量子化自体は通常の四捨五入でできるほか,そのインデクスの列挙符号化も,符号化方法においては,例えば図11のフローチャートのステップ401,403,404,405,406の5ステップに分割して高速に行うことができる。また,復号方法においても,図12のフローチャートのステップ501,504,505,506,507の5ステップに分割して高速に行える。処理が簡易なため,例えば,画像映像符号化への適用においては,一旦設計した量子化代表ベクトルを画像映像全体に使うのではなく,符号化単位毎に最適ベクトルの設計を繰り返し,適応設計することも可能で,さらに効率を高めることができる。この最適ベクトルの設計は,1次元最適化を繰り返すようになっているため,多次元探索よりも処理量のオーダーが小さい。例えば図8のフローチャートのステップ102,ステップ103,ステップ104,ステップ105,ステップ106は全て1変数を最適化しているのみで,処理が簡易である。以下,本発明を実現するための基本的な仕組みについて詳細に説明する。[1]距離尺度がL∞ノルムの場合まず,距離尺度が最も単純なL∞ノルムの場合を例に説明する。この場合,格子代表ベクトルに対応するの分布は,図1のようになる。[2]その一般化本発明ではこれをより一般化し,図2に示すように,原点からの等確率面の距離cnと分割数Knを自由に選択できるようにする。0=c0<c1<c2<<ck5K0=1,2Ki≧1i>06とする。ci,Kiから代表ベクトルが一意に定まることに注意されたい。また,本モデルでは,Kiの値として,整数だけでなく小数部分が0.5のいわゆる半整数も扱える。以降,扱う空間をL次元とする。図2は2次元の例であるが,一般性は失われていない。この一般化モデルにおいて,先ほどの図1は,L=2,ci=i,Ki=i7という特殊なケースに相当する。また,従来のECLVQは,格子点を単純に拡大したci=αi,Ki=i8という,特殊なケースに相当する。ここでαは格子の拡大率である。また同様の量子化に基づき若干自由度の増した方式非特許文献2参照も,部分的に半分またその半分にした図3に示すようなケースに相当する。ci=2aia,Ki=2biba,bは整数,ia,ibは自然数9いずれも本モデルよりも自由度が著しく低い。[3]代表ベクトルの設計ここで,学習データとしてInを用いる。これは,原点からの距離nに対応するデータの個数を表すものとする。nは適宜離散化されており,ここでは0以上の整数であるとしておく。ここで,量子化境界tiを考える。原点からの距離nがti1≦n<tiを満たす点は,ciの面内に分布する間隔ci/Kiの離散点のうち最も近い点に量子化されると仮定し,確率pi,二乗誤差diを次のように見積もる。ただし,Iは全学習データ点数=ΣnInである。i番目の等確率面に量子化される学習データの平均二乗誤差を次のように近似する。ここでci/Ki2L/12の項は,L次元空間内において,間隔ci/Kiで各次元均等量子化した際の二乗誤差の期待値である。ci,ti,piの空間的説明を図4に示す。[4]ベクトル量子化量子化境界を表すtiは,厳密には,後に定義する符号量riや歪みdiを見積もるための目安であり,実際には,ベクトルv=v1,v2,,vLが与えられたときのベクトル量子化は,次のように行う:1.ci1≦∥v∥∞<ciを満たす整数iを求める∞は右下添字,2.ci1の等確率面内でvに最も近い代表ベクトルv′i1を求める,3.ciの等確率面内でvに最も近い代表ベクトルv′iを求める,4.∥v-v′i1∥2λri1≦∥v-v′i∥2λriならば,v′i1を結果として出力;∥v-v′i1∥2λri1>∥v-v′i∥2λriならば,v′iを結果として出力する。この模式図を図5に示す。上記でciの等確率面内でvに最も近い代表ベクトルv′iを求める処理は,具体的に次のようになる:ただし,fxはスカラーxを四捨五入し,xがベクトルの場合はxの全要素を四捨五入する関数である。i番目の等確率面に対応する代表ベクトルの平均符号量より算出される,学習データの符号量は次のように見積もることができる。ここでNL,Kiはciの面に存在する格子点一辺につき2Ki1個の総数を求める関数であり,Nとして次のN0を用いることとする。これは,N0L,K=2K1L-2K-1L16で与えられる。以上述べたエントロピ拘束型ベクトル量子化方法は,すなわち,量子化代表ベクトル群の原点からの距離を示すN個の半径ci0≦i≦N-1,c0<c1<...<cN1となる実数とN個の分割数Ki2Kiは1以上の整数を入力するステップと,量子化すべきベクトルvを入力するステップと,前記ベクトルvの全要素の絶対値の最大値L∞ノルムがci1以上ci未満となるような整数iを求めるステップと,間隔qi1=ci1/Ki1を得るステップと,L∞ノルムがci1でベクトル要素の値が-ci1kqi1kは整数,0≦k≦2Ki1となるようなベクトルのうち,前記ベクトルvと最もユークリッド距離が近いベクトルv′i1を求めるステップと,間隔qi=ci/Kiを得るステップと,L∞ノルムがciでベクトル要素の値が-cikqikは整数,0≦k≦2Kiとなるようなベクトルのうち,前記ベクトルvと最もユークリッド距離が近いベクトルv′iを求めるステップと,前記ベクトルvを,前記ベクトルv′i1または前記ベクトルv′iのいずれにベクトル量子化した場合のラグランジュコストが小さいかを判定するステップと,より小さいラグランジュコストを与える前記ベクトルv′i1または前記ベクトルv′iを,前記ベクトルvのベクトル量子化結果として出力するステップとを有する。本モデルにおけるエントロピ拘束型ベクトル量子化器の設計は,未定乗数λにより定まるラグランジュコストを最小化するci,Kiを求めることに相当する。例えば,次のような手順でこの最適化を行う。[5]最適化アルゴリズム1.外部よりラグランジュ未定乗数λを入力する。2.Ki,tiを適切に初期化する。C′を十分大きな値とする。3.ciを区間ti1,tiの重心として求める。4.piを第10式に従って求める。5.tiを,∥ci-ti∥22λri=∥ci1-ti∥22λri1を満たすよう修正する。6.現状のci,pi,tiよりラグランジュコストCを求める。7.各iについて,KiをKi1と見倣した場合のコスト,KiをKi-1と見倣した場合のコスト,および上記Cを比べ,最も小さなコスト値を与える値にKiをセットする。その最小コストを新たにCとする。8.前回の値C′からの変化が十分少なければ例えば|C-C′|/C<0.005,収束したと判断し終了する。そうでなければC′:=Cとして3に戻る。[6]距離尺度がL1ノルムの場合と一般化次に,L1ノルムの場合を例に説明する。この場合,格子代表ベクトルに対応するの分布は,図6のようになる。より一般化されたモデルは,図7のようになる。ここでNとしては,次のように漸化的に求められるN1を用いる。K=1の場合:N1L,K=2LL=1の場合:N1L,K=2それ以外:N1L,K=N1L,K-1N1L-1,K-1N1L-1,Kその他の諸量の計算は,L∞ノルムの場合と同様である。[7]ベクトル量子化量子化は,次のようになる:1.ci1≦∥v∥1<ciを満たす整数iを求める,2.ci1の等確率面内でvに最も近い代表ベクトルv′i1を求める,3.ciの等確率面内でvに最も近い代表ベクトルv′iを求める,4.∥v-v′i1∥2λri1≦∥v-v′i∥2λriならば,v′i1を結果として出力;∥v-v′i1∥2λri1>∥v-v′i∥2λriならば,v′iを結果として出力。上記でciの等確率面内でvに最も近い代表ベクトルv′iを求める処理は,具体的には次のようになる。vの各要素をci/Kiで割ったベクトルをv0とする。ベクトルの各要素を四捨五入し整数化する作用素をfとする。∥fv0∥1=Kiであれば終了。そうでなければ,vからsgnv方向へk>0だけ移動しながら∥fv0ksgnv∥1=Kiとなるようなkを探す。ここで関数sgnxは,スカラーxの符号を返し,xがベクトルの場合には,xの全要素の符号を要素とするベクトルを返す関数である。x<0の場合:sgnx=-1x=0の場合:sgnx=0x>0の場合:sgnx=119関数sgnも同様に,スカラー,ベクトルいずれにも作用する関数とする。具体的には,∥fv0∥1<Kiであれば,v0の各要素の絶対値|v0i|の小数部分giのうち,gi<0.5を満たすうちで値の大きい上位∥fV0∥1-Ki個に入る要素番号について,fv0の該当要素をsgnvjだけ増加させる。∥fv0∥1>Kiであれば,v0の各要素の絶対値|v0i|の小数部分giのうち,gi≧0.5を満たすうちで値の小さい上位∥Ki-fv0∥1個に入る要素番号について,fv0の該当要素をsgnvjだけ減少させる。以上述べたエントロピ拘束型ベクトル量子化方法は,すなわち,量子化代表ベクトル群の原点からの距離を示すN個の半径ci0≦i≦N-1,c0<c1<...<cN1となる実数とN個の分割数Ki2Kiは1以上の整数を入力するステップと,量子化すべきベクトルvを入力するステップと,前記ベクトルvの全要素の絶対値和L1ノルムがci1以上ci未満となるような整数iを求めるステップと,間隔qi1=ci1/Ki1を得るステップと,L1ノルムがci1でベクトル要素の値が-ci1kqi1kは整数,0≦k≦2Ki1となるようなベクトルのうち,前記ベクトルvと最もユークリッド距離が近いベクトルv′i1を求めるステップと,間隔qi=ci/Kiを得るステップと,L1ノルムがciでベクトル要素の値が-cikqikは整数,0≦k≦2Kiとなるようなベクトルのうち,前記ベクトルvと最もユークリッド距離が近いベクトルv′iを求めるステップと,前記ベクトルvを,前記ベクトルv′i1または前記ベクトルv′iのいずれにベクトル量子化した場合のラグランジュコストが小さいかを判定するステップと,より小さいラグランジュコストを与える前記ベクトルv′i1または前記ベクトルv′iを,前記ベクトルvのベクトル量子化結果として出力するステップとを有する。図8に,本発明の一実施形態を示す。基本的には先に述べた最適化アルゴリズムの処理を実施する。まず,外部よりラグランジュ未定乗数λを入力し,メモリ100に記憶する。次に,初期化ステップ101において,C′,Ki,tiを初期化する。次に,c設定ステップ102において,ciを区間ti1,tiの重心として求める。次に,p設定ステップ103において,piを第10式に従って求める。次に,t修正ステップ104において,tiを次式を満たすように修正する。∥ci-ti∥22λr1=∥ci1-ti∥22λri1次に,C算出ステップ105において,現状のci,pi,tiよりラグランジュコストCを求める。次に,K微修正C算出ステップ106において,各iについて,KiをKi1と見倣した場合のコスト,KiをKi-1と見倣した場合のコスト,および上記Cを比べ,最も小さなコスト値を与える値にKiをセットする。その最小コストを新たにCとする。次に,収束判定ステップ107において,前回の値C′からの変化が十分少なければ|C-C′|/C<0.005,収束したと判断し終了する。そうでなければ,ステップ108においてC′:=Cとしてc設定ステップ102に戻る。図9に,本発明の一実施形態のブロック図を示す。初期化器302は,信号端子301よりラグランジュ未定乗数λを入力し,これをメモリ303に蓄積すると同時に,C′,Ki,tiを初期化する。次に,設定修正器304にて,ciおよびpiの設定,またメモリ303のλ値を参照しながらtiの修正を行う。次に,コスト算出器305にて,ci,pi,tiよりラグランジュコストCを求める。次に,微修正器306にて,Kを±1しつつコスト算出器305にて求まるコストCが小さくなるKの値を採用する。次に,変化量算出器307において,|C-C′|/Cの値を算出する。次に,比較器308において,これが0.005より小さいかを判断し,小さければ出力端子309にci,ti,Kiを出力し,終了する。そうでなければ,設定修正器304へ戻る。[距離尺度がL∞ノルムの場合の格子点列挙方法]次に,本実施形態におけるベクトル量子化による符号化および復号処理について,詳細に説明する。一辺の長さがJ-1のL次元の超直方体表面の間隔1の格子点の列挙方法は,以下のとおりである。この超直方体の表面には,L-1次元,L-2次元,,2次元平面,1次元辺,0次元頂点と,様々な次元の超平面が存在する。それぞれのL-i次元i=1Lの超平面の個数は,2iLCi,として与えられる非特許文献6参照。ただし,nCmはn個からm個を選ぶ取り出し方の総数であり,nCm=n/n-mmとして与えられる。そして,各超平面中の,端を除く格子点の数はJ-216i個である。L=16,J=5の場合のこれらの数を図10に一覧として示す。ちなみに,図10の右端の数は次元毎の超平面内の格子点の個数であり,その和は,となっている。この値は,別の形式である式16を用いて求まる格子点の数,NL,K=516-316=152544843904ただしJ=2K1に一致する。つまりこのように次元毎に分類することで,漏れなく超立方体表面の格子点が列挙できる。ここでiは,与えられた代表ベクトルの座標値全L個のうち,絶対値がcnに等しいものの個数に一致する残りのL-i個の座標値は絶対値がcnより小さい。ここで,n番目の超立方体平面に着目しているとする。[距離尺度がL∞ノルムの場合の符号化アルゴリズムの一例]既にベクトル量子化は別述の手続きにより済んでいるとする。すなわち,符号化対象のデータが属する量子化代表ベクトルが確定しているものとする。量子化インデックスと量子化代表ベクトルとの対応情報が格納されたコードブックを利用して量子化インデックスを特定し,それを符号化することも考えられるが,次元数が多い場合に事前にコードブックを作成するのは膨大な量となるため現実的ではない。ここでの符号化対象データが対応する一つの量子化代表ベクトルの符号化アルゴリズムは次のようになる:手順1まず,量子化代表ベクトルがどの超立方体表面に属するかという情報を,何番目かを示す番号nの生起確率p0,p1,を用いて符号化する。内側からn番目だとすると,この符号量は-log2pn[bit]となる。手順2もし,n=0であれば符号化処理を終了する。手順3次に,超平面の次元数L-iを特定するための整数値iを表す情報を確率区間p=2iLCiJ-2Li/NL,Kを用いて符号化する。この符号量は-log2p[bit]となる。手順4L個の次元のうち,どのi個の次元の絶対値が最大値c=cnに等しいのかを特定する情報を符号化する。全部でLCi通りあるので,log2LCi[bit]となる。手順5絶対値がcであるi個の座標値がそれぞれ正cか負-cのどちらかを特定する情報を各1[bit]を使い符号化する。例えば0なら正側,1なら負側とする。長さiの二進列なのでi[bit]となる。手順6残るL-i個の座標値は,-ccをJ等分し両端-cとcを除いた値のどれかに量子化されている。これはJ-2通りの値を取り得る。小さい方から順に0,1,2,...,J-3と番号を付け,生起確率が一様として,log2J-2[bit]を用いて符号化する。これを残る軸の数L-iだけ繰り返す。符号量はL-ilog2J-2[bit]となる。なお,生起確率を予め定められた不均等分布とみなし,算術符号等で非等長符号化をしてもよい。[距離尺度がL∞ノルムの場合の復号アルゴリズムの一例]復号アルゴリズムは,次のようになる:手順1生起確率p0,p1,を用いて,整数値nを復号する。この情報から量子化代表ベクトルが内側からn番目の超立方体表面に属することがわかる。こうして復号代表ベクトル要素の絶対値最大値がc=cnであり,分割数がJ=2Kn1とわかる。手順2もしn=0であれば,代表ベクトルとして原点を出力し,復号処理を終了する。手順3次に,生起確率分布NL,K/2iLCiJ-2Liを用いて,整数値iを復号する。これは超平面の次元数L-iを特定する情報となる。手順4log2LCi[bit]を復号し,L個の次元のうちどのi個の次元の絶対値がcに等しいのかを特定する情報を復号する。手順5i[bit]を読み込み,そのi個の座標値の符号正か負かを決定する。例えばビットが0なら正c,1なら負-cと確定する作業をi回繰り返す。手順6残るL-i個の座標値を各軸log2J-2[bit]を用いて確定する。具体的には0以上の整数値xを復号し,座標値を2cx-J-2/2/Jとして復号する。これを軸の数L-iだけ繰り返す。符号量はL-ilog2J-2[bit]となる。なお生起確率を予め定められた不均等分布とみなし,算術符号等で符号化をしてもよい。この手続きにより,符号化された量子化代表ベクトルのL個の座標値が全て復元される。[符号化フローチャート]図11は,本実施形態によるベクトル量子化符号化方法の一例を示すフローチャートである。まず,401の超立方体表面番号n符号化ステップにて,量子化代表ベクトルが内側から何番目の超立方体表面に属するかという情報を,番号nの生起確率p0,p1,を用いて符号化する。条件判断ステップ402でn=0か判定し,真であれば符号化処理を終了する。次に,403の境界座標個数i符号化ステップにて,超平面の次元数L-iを特定するための整数値iを表す情報を,確率区間p=2iLCiJ-2Li/NL,Kを用いて符号化する。次に,404の境界座標特定情報符号化ステップにて,被符号化代表ベクトルのL個の座標のうち,どのi個の次元の絶対値が最大値c=cnに等しいのかを特定する情報を符号化する。次に,405の境界座標符号情報符号化ステップにて,絶対値がcであるi個の座標値がそれぞれ正cか負-cのどちらかを特定する情報を各1[bit]を使い符号化する。例えば0なら正側,1なら負側とする。次に,406の残り座標値符号化ステップにて,残るL-i個の座標値が,-ccをJ等分し両端-cとcを除いた値のどれかに量子化されているかを符号化する作業を残る軸の数L-iだけ繰り返す。[復号フローチャート]図12は,本実施形態によるベクトル量子化復号方法の一例を示すフローチャートである。まず,501の超立方体表面番号n復号ステップにおいて,生起確率p0,p1,...を用いて,整数値nを復号する。この情報から量子化代表ベクトルが内側からn番目の超立方体表面に属することがわかる。こうして復号代表ベクトル要素の絶対値の最大値がc=cnであり,分割数がJ=2Kn1とわかる。次に,条件判断ステップ502でn=0か判定し,真であれば,503の0ベクトル出力ステップにて代表ベクトルとして原点を出力し,復号処理を終了する。次に,504の境界座標個数i復号ステップにおいて,生起確率分布NL,K/2iLCiJ-2Liを用いて,整数値iを復号する。これは超平面の次元数L-iを特定する情報となる。次に,505の境界座標特定情報復号ステップにおいて,L個の次元のうちどのi個の次元の絶対値がcに等しいのかを特定する情報を復号する。次に,506の境界座標符号情報復号ステップにおいて,そのi個の座標値の符号正か負かを決定する。例えば読み込んだビットが0なら正c,1なら負-cと確定する。これをj回繰り返す。次に,507の残り座標値復号ステップにおいて,残るL-i個の座標値を確定する。具体的には0以上の整数値xを復号し,座標値を2cx-J-2/2/Jとして復号する。これを軸の数L-iだけ繰り返す。最後に,508のベクトル出力ステップにおいて,ここまでの作業で確定したL個の座標値をベクトルとして出力する。以上,距離尺度がL∞ノルムの場合の符号化および復号処理の例を説明したが,距離尺度がL1ノルムの場合にも,上記説明から同様に実施できることは明らかである。以上のベクトル量子化の処理は,コンピュータとソフトウェアプログラムとによっても実現することができ,そのプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することも,ネットワークを通して提供することも可能である。"