(57)【要約】【課題】エントロピ拘束型ベクトル量子化において，高い符号化効率を実現でき，かつ処理が簡易であるベクトル量子化を実現する。【解決手段】量子化代表ベクトルの位置を，原点を中心とする多次元の立方体（超立方体）の表面に存在する格子点に限定し，複数存在する超立方体の一辺の長さ（２ｃi ）を可変とする。また，格子点の間隔も，一辺の長さの整数（２Ｋi ＋１）分の１とし，これを可変とする。すなわち，量子化代表ベクトル群の原点からの距離と，前記各距離に対する一つの分割数との二自由度を，量子化代表ベクトルの配置の自由度として，学習データの符号化コストが最適化されるように量子化代表ベクトルを設定し，ベクトル量子化／逆量子化を行う。【選択図】図２
2012039657.tif 000002
【特許請求の範囲】
【請求項１】
ベクトル量子化符号化またはベクトル量子化復号における，規則的な量子化代表ベクトルの並びに基づくエントロピ拘束型ベクトル量子化方法であって，
量子化代表ベクトル群の原点からの距離を示すＮ個の半径ｃi （０≦ｉ≦Ｎ−１，ｃ0 ＜ｃ1 ＜…＜ｃN-1 となる実数）とＮ個の分割数Ｋi （２Ｋi は１以上の整数）を入力するステップと，
量子化すべきベクトルｖを入力するステップと，
前記ベクトルｖの全要素の絶対値の最大値がｃi-1 以上ｃi 未満となるような整数ｉを求めるステップと，
間隔ｑi-1 ＝ｃi-1 ／Ｋi-1 を得るステップと，
ベクトルの全要素の絶対値の最大値がｃi-1 でベクトル要素の値が−ｃi-1 ＋ｋｑi-1 （ｋは整数，０≦ｋ≦２Ｋi-1 ）となるようなベクトルのうち，前記ベクトルｖと最もユークリッド距離が近いベクトルｖ′i-1 を求めるステップと，
間隔ｑi ＝ｃi ／Ｋi を得るステップと，
ベクトルの全要素の絶対値の最大値がｃi でベクトル要素の値が−ｃi ＋ｋｑi （ｋは整数，０≦ｋ≦２Ｋi ）となるようなベクトルのうち，前記ベクトルｖと最もユークリッド距離が近いベクトルｖ′i を求めるステップと，
前記ベクトルｖを，前記ベクトルｖ′i-1 または前記ベクトルｖ′i のいずれにベクトル量子化した場合のラグランジュコストが小さいかを判定するステップと，
より小さいラグランジュコストを与える前記ベクトルｖ′i-1 または前記ベクトルｖ′i を，前記ベクトルｖのベクトル量子化結果として出力するステップとを有する
ことを特徴とするベクトル量子化方法。
【請求項２】
ベクトル量子化符号化またはベクトル量子化復号における，規則的な量子化代表ベクトルの並びに基づくエントロピ拘束型ベクトル量子化方法であって，
量子化代表ベクトル群の原点からの距離を示すＮ個の半径ｃi （０≦ｉ≦Ｎ−１，ｃ0 ＜ｃ1 ＜…＜ｃN-1 となる実数）とＮ個の分割数Ｋi （Ｋi は１以上の整数）を入力するステップと，
量子化すべきベクトルｖを入力するステップと，
前記ベクトルｖの全要素の絶対値和がｃi-1 以上ｃi 未満となるような整数ｉを求めるステップと，
間隔ｑi-1 ＝ｃi-1 ／Ｋi-1 を得るステップと，
ベクトルの全要素の絶対値和がｃi-1 でベクトル要素の値が−ｃi-1 ＋ｋｑi-1 （ｋは整数，０≦ｋ≦２Ｋi-1 ）となるようなベクトルのうち，前記ベクトルｖと最もユークリッド距離が近いベクトルｖ′i-1 を求めるステップと，
間隔ｑi ＝ｃi ／Ｋi を得るステップと，
ベクトルの全要素の絶対値和がｃi でベクトル要素の値が−ｃi ＋ｋｑi （ｋは整数，０≦ｋ≦２Ｋi ）となるようなベクトルのうち，前記ベクトルｖと最もユークリッド距離が近いベクトルｖ′i を求めるステップと，
前記ベクトルｖを，前記ベクトルｖ′i-1 または前記ベクトルｖ′i のいずれにベクトル量子化した場合のラグランジュコストが小さいかを判定するステップと，
より小さいラグランジュコストを与える前記ベクトルｖ′i-1 または前記ベクトルｖ′i を，前記ベクトルｖのベクトル量子化結果として出力するステップとを有する
ことを特徴とするベクトル量子化方法。
【請求項３】
ベクトル量子化符号化またはベクトル量子化復号における，規則的な量子化代表ベクトルの並びに基づくエントロピ拘束型ベクトル量子化装置であって，
量子化代表ベクトル群の原点からの距離を示すＮ個の半径ｃi （０≦ｉ≦Ｎ−１，ｃ0 ＜ｃ1 ＜…＜ｃN-1 となる実数）とＮ個の分割数Ｋi （２Ｋi は１以上の整数）を入力する手段と，
量子化すべきベクトルｖを入力する手段と，
前記ベクトルｖの全要素の絶対値の最大値がｃi-1 以上ｃi 未満となるような整数ｉを求める手段と，
間隔ｑi-1 ＝ｃi-1 ／Ｋi-1 を得る手段と，
ベクトルの全要素の絶対値の最大値がｃi-1 でベクトル要素の値が−ｃi-1 ＋ｋｑi-1 （ｋは整数，０≦ｋ≦２Ｋi-1 ）となるようなベクトルのうち，前記ベクトルｖと最もユークリッド距離が近いベクトルｖ′i-1 を求める手段と，
間隔ｑi ＝ｃi ／Ｋi を得る手段と，
ベクトルの全要素の絶対値の最大値がｃi でベクトル要素の値が−ｃi ＋ｋｑi （ｋは整数，０≦ｋ≦２Ｋi ）となるようなベクトルのうち，前記ベクトルｖと最もユークリッド距離が近いベクトルｖ′i を求める手段と，
前記ベクトルｖを，前記ベクトルｖ′i-1 または前記ベクトルｖ′i のいずれにベクトル量子化した場合のラグランジュコストが小さいかを判定する手段と，
より小さいラグランジュコストを与える前記ベクトルｖ′i-1 または前記ベクトルｖ′i を，前記ベクトルｖのベクトル量子化結果として出力する手段とを備える
ことを特徴とするベクトル量子化装置。
【請求項４】
ベクトル量子化符号化またはベクトル量子化復号における，規則的な量子化代表ベクトルの並びに基づくエントロピ拘束型ベクトル量子化装置であって，
量子化代表ベクトル群の原点からの距離を示すＮ個の半径ｃi （０≦ｉ≦Ｎ−１，ｃ0 ＜ｃ1 ＜…＜ｃN-1 となる実数）とＮ個の分割数Ｋi （Ｋi は１以上の整数）を入力する手段と，
量子化すべきベクトルｖを入力する手段と，
前記ベクトルｖの全要素の絶対値和がｃi-1 以上ｃi 未満となるような整数ｉを求める手段と，
間隔ｑi-1 ＝ｃi-1 ／Ｋi-1 を得る手段と，
ベクトルの全要素の絶対値和がｃi-1 でベクトル要素の値が−ｃi-1 ＋ｋｑi-1 （ｋは整数，０≦ｋ≦２Ｋi-1 ）となるようなベクトルのうち，前記ベクトルｖと最もユークリッド距離が近いベクトルｖ′i-1 を求める手段と，
間隔ｑi ＝ｃi ／Ｋi を得る手段と，
ベクトルの全要素の絶対値和がｃi でベクトル要素の値が−ｃi ＋ｋｑi （ｋは整数，０≦ｋ≦２Ｋi ）となるようなベクトルのうち，前記ベクトルｖと最もユークリッド距離が近いベクトルｖ′i を求める手段と，
前記ベクトルｖを，前記ベクトルｖ′i-1 または前記ベクトルｖ′i のいずれにベクトル量子化した場合のラグランジュコストが小さいかを判定する手段と，
より小さいラグランジュコストを与える前記ベクトルｖ′i-1 または前記ベクトルｖ′i を，前記ベクトルｖのベクトル量子化結果として出力する手段とを備える
ことを特徴とするベクトル量子化装置。
【請求項５】
請求項１または請求項２に記載のベクトル量子化方法を，コンピュータに実行させるためのベクトル量子化プログラム。
【請求項６】
請求項１または請求項２に記載のベクトル量子化方法を，コンピュータに実行させるためのベクトル量子化プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，音声や画像・映像を効率よく符号化する高能率マルチメディア信号符号化のための方法および装置に関する。
【背景技術】
【０００２】
従来のベクトル符号化においては，代表ベクトルが空間内に規則的に位置するピラミッドベクトル量子化（非特許文献１参照），ラティスベクトル量子化，区分的一様ベクトル量子化（非特許文献２参照）や，代表ベクトルを学習により最適化し，結果としてそれらを空間内に不規則に配置する，良く知られたＬＢＧアルゴリズム（非特許文献３参照）に基づくベクトル量子化，エントロピ拘束ベクトル量子化（非特許文献４参照）という方式がある。
【０００３】
エントロピ拘束ベクトル量子化は，別途与えられる未定乗数（λ）を元に，ラグランジュコストと呼ばれる値Ｃ，
Ｃ＝Ｄ＋λＲ        （１）
を最小化するように，代表ベクトルを選択するものである（非特許文献４参照）。ここで，Ｄはベクトル量子化により発生する二乗誤差，Ｒは符号量（あるいはエントロピ）である。
【０００４】
【数１】
2012039657.tif 000003
【０００５】
ここで，ｑ（ｉ）はベクトル量子化の結果の学習ベクトルｘi が属する代表ベクトルの番号であり，ｖq(i)はその代表ベクトルである。ｐ（ｖi ）はベクトルｖi の発生する確率を表す。また，‖ｘ‖p は次式のようにベクトルｘのＬp ノルムを表す。次式のｘ（ｉ）はベクトルｘの第ｉ番目の座標値を表す。
【０００６】
【数２】
2012039657.tif 000004
【０００７】
これは，ｐ＝１のとき（Ｌ1 ノルム），ベクトル要素の絶対値和を示し，ｐ＝∞のとき（Ｌ∞ノルム；∞はＬの右上添字，以下同様），ベクトル要素の絶対値の最大値を示す。
【０００８】
また，それらを融合したエントロピ拘束ラティスベクトル量子化（ＥＣＬＶＱ）という方法もある（非特許文献５参照）。これは格子全体を均等に拡大あるいは縮小し，ビットレートに応じた最適な拡大率を選択するものである。
【０００９】
しかしながら，従来のＥＣＬＶＱは最適化の余地が小さく，かつ演算が簡易な方式は知られていなかった。
【００１０】
例えば，画像の予測誤差信号は原点付近に信号が集中し，原点から離れるに従って疎になる。このような場合，代表ベクトルは原点から離れるに従い疎になる方が，符号量−歪みの関係からは好ましい。しかしながら，全格子を均等に拡大あるいは縮小するＥＣＬＶＱでは，そのような機構を実現できない。
【００１１】
なお，非特許文献６には，本発明の実施形態の説明で用いているＬ次元の超直方体表面における超平面の個数に関しての記載がある。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】T.R.Fischer:“A pyramid vector quantizer”，IEEE Trans. Inform. Theory，vol.IT-32 ，pp.568-583，1986.
【非特許文献２】D.G.Jeong ，J.Gibson: “Uniform and Piecewise Uniform Lattice Vector Quantization for Memoryless. Gaussian and Laplacian Sources”，IEEE Trans. ，1993，IT-39(3)，pp.786-804．
【非特許文献３】Y.Linde ，A.Buzo and R.M.Gray:“An algorithm for vector quantizer design”，IEEE Trans. on Communications ，vol.com-28，no.1，pp.84-95，Jan. 1980 ．
【非特許文献４】P.A.Chou，T.Lookabaugh，and R.M.Gray: “Entropy-constrained vector quantization ”，IEEE Trans. Acoust. Speech Signal Processing，vol.37，pp.31-42，Jan. 1989 ．
【非特許文献５】W.H.Kim ，Y.H.Hu，T.Nguyen: “Adaptive Wavelet Packet Basis For Entropy-Constrained Lattice Vector Quantizer (ECLVQ)”，Proc. ICIP'97 ，vol.1 ，pp.656-659，Oct. 1997 ．
【非特許文献６】J.An，Y-P.Chen and Q.Xu:“Surface Spatial Index Structure of High-Dimensional Space ”，Lecture Notes in Computer Science ，Volume 3177 ，pp.272-278，Oct ，2004．
【発明の概要】
【発明が解決しようとする課題】
【００１３】
ベクトル量子化では，量子化代表ベクトルの配置を任意とした場合が最も自由度が高く，理想的な（ラグランジュコストが小さくなる）ベクトル量子化となる。しかし，ベクトルの配置（設計）や量子化・符号化といった処理は，量子化代表ベクトルの個数に応じて増加するため，量子化代表ベクトルの個数は数千が限度である。例えば１６次元で１［ｂｉｔ／ｓａｍｐｌｅ］でベクトル量子化・符号化する場合，およそ２16*1＝６５５３６個の代表ベクトルが必要であり，処理量が膨大になってしまう。
【００１４】
そこで，ピラミッドベクトル量子化のように格子点を基本としたベクトル量子化において，実用的に処理可能な範囲内で，より高い自由度でベクトル量子化を最適化する技術が望まれる。
【００１５】
本発明は上記問題点の解決を図り，高い符号化効率を実現でき，かつ処理が簡易であるベクトル量子化の技術を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明は上記課題を解決し，ピラミッドベクトル量子化のように格子点を基本としたベクトル量子化において，エントロピ拘束型ベクトル量子化を，より高い自由度で最適化するため，代表ベクトルの配置（設計）における自由度として，代表ベクトル群の原点からの距離と，各距離に対して一対一に対応する分割数（整数値）との２自由度を有することを，もっとも主要な特徴とする。
【００１７】
本発明において，上記代表ベクトル群の原点からの距離の尺度として，ベクトルの全要素の絶対値和を用いることができる。これは，Ｌ∞ノルムを距離尺度として用いることに相当する。
【００１８】
また，本発明は，原点からの距離の尺度として，ベクトルの全要素の絶対値の最大値を用いることもできる。これは，Ｌ1 ノルムを距離尺度として用いることに相当する。
【００１９】
本発明の特徴は，次のように捉えることもできる。すなわち，本発明は，エントロピ拘束型ベクトル量子化において，零ベクトルを量子化代表ベクトルの一つとして保持する手段と，量子化代表ベクトル群の原点からの距離を示すＮ個の半径ｃi （０≦ｉ≦Ｎ−１，ｃ0 ＜ｃ1 ＜…＜ｃN-1 となる実数）とＮ個の分割数Ｋi （２Ｋi は１以上の整数）を入力する手段と，あるｉ（０≦ｉ≦Ｎ−１）において，間隔ｑ＝ｃi ／Ｋi を得る手段と，ベクトルｖの要素の絶対値のうち最大値がｃi であり，ベクトルｖの要素の値が−ｃi ＋ｋｑ（ｋは整数，０≦ｋ≦２Ｋi ）となっているベクトルｖを量子化代表ベクトルとする手段と，前記量子化代表ベクトルに基づきベクトル量子化または逆量子化を行う手段とを備えることを特徴とする。
【００２０】
また，本発明は，エントロピ拘束型ベクトル量子化において，零ベクトルを量子化代表ベクトルの一つとして保持する手段と，量子化代表ベクトル群の原点からの距離を示すＮ個の半径ｃi （０≦ｉ≦Ｎ−１，ｃ0 ＜ｃ1 ＜…＜ｃN-1 となる実数）とＮ個の分割数Ｋi （Ｋi は１以上の整数）を入力する手段と，あるｉ（０≦ｉ≦Ｎ−１）において，間隔ｑ＝ｃi ／Ｋi を得る手段と，ベクトルｖの要素の絶対値の和がｃi であり，ベクトルｖの要素の絶対値がｋｑ（ｋは整数，０≦ｋ≦Ｋi ）となっているベクトルｖを量子化代表ベクトルとする手段と，前記量子化代表ベクトルに基づきベクトル量子化または逆量子化を行う手段とを備えることを特徴とする。
【発明の効果】
【００２１】
本発明によれば，規則的・計算容易ながら従来よりもより柔軟な量子化代表ベクトルの配置を実現することができ，結果として，より低いラグランジュコスト，すなわち，より高い符号化効率を実現することができるようになる。
【図面の簡単な説明】
【００２２】
【図１】Ｌ∞がノルムにおいて最も単純な場合の代表ベクトルの配置例を示す図である。
【図２】Ｌ∞ノルムにおいて一般化された場合の代表ベクトルの配置例を示す図である。
【図３】区分的に均等な量子化の例を示す図である。
【図４】補助変数ｃi ，ｔi ，ｐi の空間的な説明図である。
【図５】ベクトル量子化の手順模式図である。
【図６】Ｌ1 ノルムにおいて最も単純な場合の代表ベクトルの配置例を示す図である。
【図７】Ｌ1 ノルムにおいて一般化された場合の代表ベクトルの配置例を示す図である。
【図８】本発明の一実施形態における処理の流れを示す図である。
【図９】本発明の一実施形態のブロック図である。
【図１０】Ｌ＝１６，Ｊ＝５の場合の，次元毎の超平面の数とその中の格子点の数を示す図である。
【図１１】符号化処理の一例を示すフローチャートである。
【図１２】復号処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００２３】
まず，本発明の実施形態についての考え方の概要を簡単に説明する。
【００２４】
・本発明では，量子化代表ベクトルの位置を，原点を中心とする多次元の立方体（超立方体）の表面に存在する格子点に限定する（図１，図２参照）。
【００２５】
・ただし，超立方体は複数存在し，その一辺の長さ（２ｃi ）を可変とする（図８のフローチャートのステップ１０２）。また，格子点の間隔も，一辺の長さの整数（２Ｋ＋１）分の１とし，これを可変とする（図８のフローチャートのステップ１０６）。
【００２６】
・このように量子化代表ベクトルの配置を規則的としながら，従来よりも自由度の高い配置をとること（図２，図７参照）により，量子化・符号化において，これら自由度の最適化を施すことで（図８のフローチャート全体），従来よりも低いラグランジュコストを実現する。
【００２７】
・量子化代表ベクトル多次元の立方体（超立方体）の表面に存在する格子点配置が規則的なため，量子化・逆量子化が簡易である。量子化自体は通常の四捨五入でできるほか，そのインデクスの列挙・符号化も，符号化方法においては，例えば図１１のフローチャートのステップ４０１，４０３，４０４，４０５，４０６の５ステップに分割して高速に行うことができる。また，復号方法においても，図１２のフローチャートのステップ５０１，５０４，５０５，５０６，５０７の５ステップに分割して高速に行える。
【００２８】
・処理が簡易なため，例えば，画像・映像符号化への適用においては，一旦設計した量子化代表ベクトルを画像・映像全体に使うのではなく，符号化単位毎に最適ベクトルの設計を繰り返し，適応設計することも可能で，さらに効率を高めることができる。この最適ベクトルの設計は，１次元最適化を繰り返すようになっているため，多次元探索よりも処理量のオーダーが小さい。例えば図８のフローチャートのステップ１０２，ステップ１０３，ステップ１０４，ステップ１０５，ステップ１０６は全て１変数を最適化しているのみで，処理が簡易である。
【００２９】
以下，本発明を実現するための基本的な仕組みについて詳細に説明する。
【００３０】
［１］距離尺度がＬ∞ノルムの場合
まず，距離尺度が最も単純なＬ∞ノルムの場合を例に説明する。この場合，格子（代表ベクトルに対応する）の分布は，図１のようになる。
【００３１】
［２］その一般化
本発明ではこれをより一般化し，図２に示すように，原点からの等確率面の距離（ｃn ）と分割数（Ｋn ）を自由に選択できるようにする。
【００３２】
０＝ｃ0 ＜ｃ1 ＜ｃ2 ＜... ＜ｃk         （５）
Ｋ0 ＝１，  ２Ｋi ≧１（ｉ＞０）        （６）
とする。
【００３３】
ｃi ，Ｋi から代表ベクトルが一意に定まることに注意されたい。また，本モデルでは，Ｋi の値として，整数だけでなく小数部分が０．５のいわゆる半整数も扱える。以降，扱う空間をＬ次元とする。図２は２次元の例であるが，一般性は失われていない。
【００３４】
この一般化モデルにおいて，先ほどの図１は，
Ｌ＝２，ｃi ＝ｉ，Ｋi ＝ｉ        （７）
という特殊なケースに相当する。また，従来のＥＣＬＶＱは，格子点を単純に拡大した
ｃi ＝αｉ，Ｋi ＝ｉ              （８）
という，特殊なケースに相当する。ここでαは格子の拡大率である。また同様の量子化に基づき若干自由度の増した方式（非特許文献２参照）も，部分的に半分・またその半分にした図３に示すようなケースに相当する。
【００３５】
ｃi ＝２a ｉa ，Ｋi ＝２b ｉb   （ａ，ｂは整数，ｉa ，ｉb は自然数）（９）
いずれも本モデルよりも自由度が著しく低い。
【００３６】
［３］代表ベクトルの設計
ここで，学習データとしてＩn を用いる。これは，原点からの距離ｎに対応するデータの個数を表すものとする。ｎは適宜離散化されており，ここでは０以上の整数であるとしておく。
【００３７】
ここで，量子化境界ｔi を考える。原点からの距離ｎがｔi-1 ≦ｎ＜ｔi を満たす点は，ｃi の面内に分布する間隔ｃi ／Ｋi の離散点のうち最も近い点に量子化されると仮定し，確率ｐi ，二乗誤差ｄi を次のように見積もる。
【００３８】
【数３】
2012039657.tif 000005
【００３９】
ただし，Ｉは全学習データ点数（＝Σn Ｉn ）である。
【００４０】
ｉ番目の等確率面に量子化される学習データの平均二乗誤差を次のように近似する。
【００４１】
【数４】
2012039657.tif 000006
【００４２】
ここで〔（ｃi ／Ｋi ）2 Ｌ／１２〕の項は，Ｌ次元空間内において，間隔ｃi ／Ｋi で各次元均等量子化した際の二乗誤差の期待値である。
【００４３】
ｃi ，ｔi ，ｐi の空間的説明を図４に示す。
【００４４】
［４］ベクトル量子化
量子化境界を表すｔi は，厳密には，後に定義する符号量（ｒi ）や歪み（ｄi ）を見積もるための目安であり，実際には，ベクトルｖ＝（ｖ1 ，ｖ2 ，... ，ｖL ）が与えられたときのベクトル量子化は，次のように行う：
１．ｃi-1 ≦‖ｖ‖∞＜ｃi を満たす整数ｉを求める（∞は右下添字），
２．ｃi-1 の等確率面内でｖに最も近い代表ベクトルｖ′i-1 を求める，
３．ｃi の等確率面内でｖに最も近い代表ベクトルｖ′i を求める，
４．‖ｖ−ｖ′i-1 ‖2 ＋λｒi-1 ≦‖ｖ−ｖ′i ‖2 ＋λｒi ならば，ｖ′i-1 を結果として出力；‖ｖ−ｖ′i-1 ‖2 ＋λｒi-1 ＞‖ｖ−ｖ′i ‖2 ＋λｒi ならば，ｖ′i を結果として出力する。
【００４５】
この模式図を図５に示す。上記で「ｃi の等確率面内でｖに最も近い代表ベクトルｖ′i を求める」処理は，具体的に次のようになる：
【００４６】
【数５】
2012039657.tif 000007
【００４７】
ただし，ｆ（ｘ）はスカラーｘを四捨五入し，ｘがベクトルの場合はｘの全要素を四捨五入する関数である。
【００４８】
【数６】
2012039657.tif 000008
【００４９】
ｉ番目の等確率面に対応する代表ベクトルの平均符号量より算出される，学習データの符号量は次のように見積もることができる。
【００５０】
【数７】
2012039657.tif 000009
【００５１】
ここでＮ（Ｌ，Ｋi ）はｃi の面に存在する格子点（一辺につき（２Ｋi ＋１）個）の総数を求める関数であり，Ｎとして次のＮ0 （）を用いることとする。これは，
Ｎ0 （Ｌ，Ｋ）＝（２Ｋ＋１）L −（２Ｋ−１）L         （１６）
で与えられる。
【００５２】
以上述べたエントロピ拘束型ベクトル量子化方法は，すなわち，量子化代表ベクトル群の原点からの距離を示すＮ個の半径ｃi （０≦ｉ≦Ｎ−１，ｃ0 ＜ｃ1 ＜…＜ｃN-1 となる実数）とＮ個の分割数Ｋi （２Ｋi は１以上の整数）を入力するステップと，量子化すべきベクトルｖを入力するステップと，前記ベクトルｖの全要素の絶対値の最大値（Ｌ∞ノルム）がｃi-1 以上ｃi 未満となるような整数ｉを求めるステップと，間隔ｑi-1 ＝ｃi-1 ／Ｋi-1 を得るステップと，Ｌ∞ノルムがｃi-1 でベクトル要素の値が−ｃi-1 ＋ｋｑi-1 （ｋは整数，０≦ｋ≦２Ｋi-1 ）となるようなベクトルのうち，前記ベクトルｖと最もユークリッド距離が近いベクトルｖ′i-1 を求めるステップと，間隔ｑi ＝ｃi ／Ｋi を得るステップと，Ｌ∞ノルムがｃi でベクトル要素の値が−ｃi ＋ｋｑi （ｋは整数，０≦ｋ≦２Ｋi ）となるようなベクトルのうち，前記ベクトルｖと最もユークリッド距離が近いベクトルｖ′i を求めるステップと，前記ベクトルｖを，前記ベクトルｖ′i-1 または前記ベクトルｖ′i のいずれにベクトル量子化した場合のラグランジュコストが小さいかを判定するステップと，より小さいラグランジュコストを与える前記ベクトルｖ′i-1 または前記ベクトルｖ′i を，前記ベクトルｖのベクトル量子化結果として出力するステップとを有する。
【００５３】
本モデルにおけるエントロピ拘束型ベクトル量子化器の設計は，未定乗数λにより定まるラグランジュコスト
【００５４】
【数８】
2012039657.tif 000010
【００５５】
を最小化するｃi ，Ｋi を求めることに相当する。例えば，次のような手順でこの最適化を行う。
【００５６】
［５］最適化アルゴリズム
１．外部よりラグランジュ未定乗数λを入力する。
２．Ｋi ，ｔi を適切に初期化する。Ｃ′を十分大きな値とする。
３．ｃi を区間（ｔi-1 ，ｔi ）の重心として求める。
４．ｐi を第１０式に従って求める。
５．ｔi を，‖ｃi −ｔi ‖2 2 ＋λｒi ＝‖ｃi+1 −ｔi ‖2 2 ＋λｒi+1 を満たすよう修正する。
６．現状のｃi ，ｐi ，ｔi よりラグランジュコストＣを求める。
７．各ｉについて，Ｋi をＫi ＋１と見倣した場合のコスト，Ｋi をＫi −１と見倣した場合のコスト，および上記Ｃを比べ，最も小さなコスト値を与える値にＫi をセットする。その最小コストを新たにＣとする。
８．前回の値（Ｃ′）からの変化が十分少なければ（例えば｜Ｃ−Ｃ′｜／Ｃ＜０．００５），収束したと判断し終了する。そうでなければＣ′：＝Ｃとして３に戻る。
【００５７】
［６］距離尺度がＬ1 ノルムの場合と一般化
次に，Ｌ1 ノルムの場合を例に説明する。この場合，格子（代表ベクトルに対応する）の分布は，図６のようになる。
【００５８】
より一般化されたモデルは，図７のようになる。
【００５９】
ここでＮとしては，次のように漸化的に求められるＮ1 を用いる。
・Ｋ＝１の場合：Ｎ1 （Ｌ，Ｋ）＝２Ｌ                                            ・Ｌ＝１の場合：Ｎ1 （Ｌ，Ｋ）＝２
・それ以外    ：Ｎ1 （Ｌ，Ｋ）＝Ｎ1 （Ｌ，Ｋ−１）＋Ｎ1 （Ｌ−１，Ｋ−１）
＋Ｎ1 （Ｌ−１，Ｋ）
その他の諸量の計算は，Ｌ∞ノルムの場合と同様である。
【００６０】
［７］ベクトル量子化
量子化は，次のようになる：
１．ｃi-1 ≦‖ｖ‖1 ＜ｃi を満たす整数ｉを求める，
２．ｃi-1 の等確率面内でｖに最も近い代表ベクトルｖ′i-1 を求める，
３．ｃi の等確率面内でｖに最も近い代表ベクトルｖ′i を求める，
４．‖ｖ−ｖ′i-1 ‖2 ＋λｒi-1 ≦‖ｖ−ｖ′i ‖2 ＋λｒi ならば，ｖ′i-1 を結果として出力；‖ｖ−ｖ′i-1 ‖2 ＋λｒi-1 ＞‖ｖ−ｖ′i ‖2 ＋λｒi ならば，ｖ′i を結果として出力。
【００６１】
上記で「ｃi の等確率面内でｖに最も近い代表ベクトルｖ′i を求める」処理は，具体的には次のようになる。
・ｖの各要素をｃi ／Ｋi で割ったベクトルをｖ0 とする。ベクトルの各要素を四捨五入し整数化する作用素をｆ（）とする。‖ｆ（ｖ0 ）‖1 ＝Ｋi であれば終了。
・そうでなければ，ｖからｓｇｎ（ｖ）方向へｋ（＞０）だけ移動しながら‖ｆ（ｖ0 ＋ｋ・ｓｇｎ（ｖ））‖1 ＝Ｋi となるようなｋを探す。
【００６２】
ここで関数ｓｇｎ（ｘ）は，スカラーｘの符号を返し，ｘがベクトルの場合には，ｘの全要素の符号を要素とするベクトルを返す関数である。
・ｘ＜０の場合：ｓｇｎ（ｘ）＝−１
・ｘ＝０の場合：ｓｇｎ（ｘ）＝０
・ｘ＞０の場合：ｓｇｎ（ｘ）＝１            （１９）
関数ｓｇｎ（）も同様に，スカラー，ベクトルいずれにも作用する関数とする。
【００６３】
具体的には，‖ｆ（ｖ0 ）‖1 ＜Ｋi であれば，ｖ0 の各要素の絶対値（｜ｖ0 （ｉ）｜）の小数部分ｇi のうち，ｇi ＜０．５を満たすうちで値の大きい上位‖ｆ（Ｖ0 ）‖1 −Ｋi 個に入る要素番号について，ｆ（ｖ0 ）の該当要素をｓｇｎ（ｖj ）だけ増加させる。
【００６４】
‖ｆ（ｖ0 ）‖1 ＞Ｋi であれば，ｖ0 の各要素の絶対値（｜ｖ0 （ｉ）｜）の小数部分ｇi のうち，ｇi ≧０．５を満たすうちで値の小さい上位‖Ｋi −ｆ（ｖ0 ）‖1 個に入る要素番号について，ｆ（ｖ0 ）の該当要素をｓｇｎ（ｖj ）だけ減少させる。
【００６５】
以上述べたエントロピ拘束型ベクトル量子化方法は，すなわち，量子化代表ベクトル群の原点からの距離を示すＮ個の半径ｃi （０≦ｉ≦Ｎ−１，ｃ0 ＜ｃ1 ＜…＜ｃN-1 となる実数）とＮ個の分割数Ｋi （２Ｋi は１以上の整数）を入力するステップと，量子化すべきベクトルｖを入力するステップと，前記ベクトルｖの全要素の絶対値和（Ｌ1 ノルム）がｃi-1 以上ｃi 未満となるような整数ｉを求めるステップと，間隔ｑi-1 ＝ｃi-1 ／Ｋi-1 を得るステップと，Ｌ1 ノルムがｃi-1 でベクトル要素の値が−ｃi-1 ＋ｋｑi-1 （ｋは整数，０≦ｋ≦２Ｋi-1 ）となるようなベクトルのうち，前記ベクトルｖと最もユークリッド距離が近いベクトルｖ′i-1 を求めるステップと，間隔ｑi ＝ｃi ／Ｋi を得るステップと，Ｌ1 ノルムがｃi でベクトル要素の値が−ｃi ＋ｋｑi （ｋは整数，０≦ｋ≦２Ｋi ）となるようなベクトルのうち，前記ベクトルｖと最もユークリッド距離が近いベクトルｖ′i を求めるステップと，前記ベクトルｖを，前記ベクトルｖ′i-1 または前記ベクトルｖ′i のいずれにベクトル量子化した場合のラグランジュコストが小さいかを判定するステップと，より小さいラグランジュコストを与える前記ベクトルｖ′i-1 または前記ベクトルｖ′i を，前記ベクトルｖのベクトル量子化結果として出力するステップとを有する。
【００６６】
図８に，本発明の一実施形態を示す。基本的には先に述べた「最適化アルゴリズム」の処理を実施する。
【００６７】
まず，外部よりラグランジュ未定乗数λを入力し，メモリ１００に記憶する。次に，初期化ステップ１０１において，Ｃ′，Ｋi ，ｔi を初期化する。次に，ｃ設定ステップ１０２において，ｃi を区間（ｔi-1 ，ｔi ）の重心として求める。次に，ｐ設定ステップ１０３において，ｐi を第１０式に従って求める。次に，ｔ修正ステップ１０４において，ｔi を次式を満たすように修正する。
【００６８】
‖ｃi −ｔi ‖2 2 ＋λｒ1 ＝‖ｃi+1 −ｔi ‖2 2 ＋λｒi+1 
次に，Ｃ算出ステップ１０５において，現状のｃi ，ｐi ，ｔi よりラグランジュコストＣを求める。次に，Ｋ微修正・Ｃ算出ステップ１０６において，各ｉについて，Ｋi をＫi ＋１と見倣した場合のコスト，Ｋi をＫi −１と見倣した場合のコスト，および上記Ｃを比べ，最も小さなコスト値を与える値にＫi をセットする。その最小コストを新たにＣとする。次に，収束判定ステップ１０７において，前回の値（Ｃ′）からの変化が十分少なければ（｜Ｃ−Ｃ′｜／Ｃ＜０．００５），収束したと判断し終了する。そうでなければ，ステップ１０８においてＣ′：＝Ｃとしてｃ設定ステップ１０２に戻る。
【００６９】
図９に，本発明の一実施形態のブロック図を示す。初期化器３０２は，信号端子３０１よりラグランジュ未定乗数λを入力し，これをメモリ３０３に蓄積すると同時に，Ｃ′，Ｋi ，ｔi を初期化する。次に，設定・修正器３０４にて，ｃi およびｐi の設定，またメモリ３０３のλ値を参照しながらｔi の修正を行う。次に，コスト算出器３０５にて，ｃi ，ｐi ，ｔi よりラグランジュコストＣを求める。次に，微修正器３０６にて，Ｋを±１しつつコスト算出器３０５にて求まるコストＣが小さくなるＫの値を採用する。次に，変化量算出器３０７において，｜Ｃ−Ｃ′｜／Ｃの値を算出する。次に，比較器３０８において，これが０．００５より小さいかを判断し，小さければ出力端子３０９にｃi ，ｔi ，Ｋi を出力し，終了する。そうでなければ，設定・修正器３０４へ戻る。
【００７０】
［距離尺度がＬ∞ノルムの場合の格子点列挙方法］
次に，本実施形態におけるベクトル量子化による符号化および復号処理について，詳細に説明する。一辺の長さがＪ−１のＬ次元の超直方体表面の間隔１の格子点の列挙方法は，以下のとおりである。
【００７１】
この超直方体の表面には，Ｌ−１次元，Ｌ−２次元，... ，２次元（平面），１次元（辺），０次元（頂点）と，様々な次元の「超平面」が存在する。それぞれの（Ｌ−ｉ）次元（ｉ＝１... Ｌ）の超平面の個数は，２i  LＣi ，として与えられる（非特許文献６  参照）。ただし， nＣm はｎ個からｍ個を選ぶ取り出し方の総数であり， nＣm ＝ｎ！／（（ｎ−ｍ）！ｍ！）として与えられる。
【００７２】
そして，各超平面中の，端を除く格子点の数は（Ｊ−２）16-i個である。
【００７３】
Ｌ＝１６，Ｊ＝５の場合のこれらの数を図１０に一覧として示す。ちなみに，図１０の右端の数は次元毎の超平面内の格子点の個数であり，その和は，
【００７４】
【数９】
2012039657.tif 000011
【００７５】
となっている。この値は，別の形式である式（１６）を用いて求まる格子点の数，
Ｎ（Ｌ，Ｋ）＝５16−３16＝１５２５４４８４３９０４  （ただしＪ＝２Ｋ＋１）
に一致する。つまりこのように次元毎に分類することで，漏れなく超立方体表面の格子点が列挙できる。
【００７６】
ここでｉは，与えられた代表ベクトルの座標値（全Ｌ個）のうち，絶対値がｃn に等しいものの個数に一致する（残りのＬ−ｉ個の座標値は絶対値がｃn より小さい）。ここで，ｎ番目の超立方体平面に着目しているとする。
【００７７】
［距離尺度がＬ∞ノルムの場合の符号化アルゴリズムの一例］
既にベクトル量子化は別述の手続きにより済んでいるとする。すなわち，符号化対象のデータが属する量子化代表ベクトルが確定しているものとする。量子化インデックスと量子化代表ベクトルとの対応情報が格納されたコードブックを利用して量子化インデックスを特定し，それを符号化することも考えられるが，次元数が多い場合に事前にコードブックを作成するのは膨大な量となるため現実的ではない。ここでの符号化対象データが対応する一つの量子化代表ベクトルの符号化アルゴリズムは次のようになる：
〔手順１〕まず，量子化代表ベクトルがどの超立方体表面に属するかという情報を，何番目かを示す番号ｎの生起確率ｐ0 ，ｐ1 ，... を用いて符号化する。内側からｎ番目だとすると，この符号量は−ｌｏｇ2 ｐn ［ｂｉｔ］となる。
〔手順２〕もし，ｎ＝０であれば符号化処理を終了する。
〔手順３〕次に，超平面の次元数（Ｌ−ｉ）を特定するための整数値ｉを表す情報を確率区間ｐ＝（２i  LＣi （Ｊ−２）L-i ）／Ｎ（Ｌ，Ｋ）を用いて符号化する。この符号量は−ｌｏｇ2 ｐ［ｂｉｔ］となる。
〔手順４〕Ｌ個の次元のうち，どのｉ個の次元の絶対値が最大値ｃ＝ｃn に等しいのかを特定する情報を符号化する。全部で LＣi 通りあるので，ｌｏｇ2  LＣi ［ｂｉｔ］となる。
〔手順５〕絶対値がｃであるｉ個の座標値がそれぞれ正（ｃ）か負（−ｃ）のどちらかを特定する情報を各１［ｂｉｔ］を使い符号化する。例えば０なら正側，１なら負側とする。長さｉの二進列なのでｉ［ｂｉｔ］となる。
〔手順６〕残るＬ−ｉ個の座標値は，−ｃ..ｃをＪ等分し両端（−ｃとｃ）を除いた値のどれかに量子化されている。これはＪ−２通りの値を取り得る。小さい方から順に０，１，２，…，Ｊ−３と番号を付け，生起確率が一様として，ｌｏｇ2 （Ｊ−２）［ｂｉｔ］を用いて符号化する。これを残る軸の数（Ｌ−ｉ）だけ繰り返す。符号量は（Ｌ−ｉ）ｌｏｇ2 （Ｊ−２）［ｂｉｔ］となる。なお，生起確率を予め定められた不均等分布とみなし，算術符号等で非等長符号化をしてもよい。
【００７８】
［距離尺度がＬ∞ノルムの場合の復号アルゴリズムの一例］
復号アルゴリズムは，次のようになる：
〔手順１〕生起確率ｐ0 ，ｐ1 ，... を用いて，整数値ｎを復号する。この情報から量子化代表ベクトルが内側からｎ番目の超立方体表面に属することがわかる。こうして復号代表ベクトル要素の絶対値最大値がｃ＝ｃn であり，分割数がＪ＝２Ｋn ＋１とわかる。
〔手順２〕もしｎ＝０であれば，代表ベクトルとして原点を出力し，復号処理を終了する。
〔手順３〕次に，生起確率分布Ｎ（Ｌ，Ｋ）／（２i  LＣi （Ｊ−２）L-i ）を用いて，整数値ｉを復号する。これは超平面の次元数（Ｌ−ｉ）を特定する情報となる。
〔手順４〕ｌｏｇ2  LＣi ［ｂｉｔ］を復号し，Ｌ個の次元のうちどのｉ個の次元の絶対値がｃに等しいのかを特定する情報を復号する。
〔手順５〕ｉ［ｂｉｔ］を読み込み，そのｉ個の座標値の符号（正か負か）を決定する。例えばビットが０なら正（ｃ），１なら負（−ｃ）と確定する作業をｉ回繰り返す。
〔手順６〕残るＬ−ｉ個の座標値を各軸ｌｏｇ2 （Ｊ−２）［ｂｉｔ］を用いて確定する。具体的には０以上の整数値ｘを復号し，座標値を２ｃ（ｘ−（Ｊ−２）／２）／Ｊとして復号する。これを軸の数（Ｌ−ｉ）だけ繰り返す。符号量は（Ｌ−ｉ）ｌｏｇ2 （Ｊ−２）［ｂｉｔ］となる。なお生起確率を予め定められた不均等分布とみなし，算術符号等で符号化をしてもよい。
【００７９】
この手続きにより，符号化された量子化代表ベクトルのＬ個の座標値が全て復元される。
【００８０】
［符号化フローチャート］
図１１は，本実施形態によるベクトル量子化符号化方法の一例を示すフローチャートである。
【００８１】
まず，４０１の超立方体表面番号ｎ符号化ステップにて，量子化代表ベクトルが内側から何番目の超立方体表面に属するかという情報を，番号ｎの生起確率ｐ0 ，ｐ1 ，... を用いて符号化する。
【００８２】
条件判断ステップ４０２でｎ＝０か判定し，真であれば符号化処理を終了する。
【００８３】
次に，４０３の境界座標個数ｉ符号化ステップにて，超平面の次元数（Ｌ−ｉ）を特定するための整数値ｉを表す情報を，確率区間ｐ＝（２i  LＣi （Ｊ−２）L-i ）／Ｎ（Ｌ，Ｋ）を用いて符号化する。
【００８４】
次に，４０４の境界座標特定情報符号化ステップにて，被符号化代表ベクトルのＬ個の座標のうち，どのｉ個の次元の絶対値が最大値ｃ＝ｃn に等しいのかを特定する情報を符号化する。
【００８５】
次に，４０５の境界座標符号情報符号化ステップにて，絶対値がｃであるｉ個の座標値がそれぞれ正（ｃ）か負（−ｃ）のどちらかを特定する情報を各１［ｂｉｔ］を使い符号化する。例えば０なら正側，１なら負側とする。
【００８６】
次に，４０６の残り座標値符号化ステップにて，残るＬ−ｉ個の座標値が，−ｃ..ｃをＪ等分し両端（−ｃとｃ）を除いた値のどれかに量子化されているかを符号化する作業を残る軸の数（Ｌ−ｉ）だけ繰り返す。
【００８７】
［復号フローチャート］
図１２は，本実施形態によるベクトル量子化復号方法の一例を示すフローチャートである。
【００８８】
まず，５０１の超立方体表面番号ｎ復号ステップにおいて，生起確率ｐ0 ，ｐ1 ，…を用いて，整数値ｎを復号する。この情報から量子化代表ベクトルが内側からｎ番目の超立方体表面に属することがわかる。こうして復号代表ベクトル要素の絶対値の最大値がｃ＝ｃn であり，分割数がＪ＝２Ｋn ＋１とわかる。
【００８９】
次に，条件判断ステップ５０２でｎ＝０か判定し，真であれば，５０３の０ベクトル出力ステップにて代表ベクトルとして原点を出力し，復号処理を終了する。
【００９０】
次に，５０４の境界座標個数ｉ復号ステップにおいて，生起確率分布Ｎ（Ｌ，Ｋ）／（２i  LＣi （Ｊ−２）L-i ）を用いて，整数値ｉを復号する。これは超平面の次元数（Ｌ−ｉ）を特定する情報となる。
【００９１】
次に，５０５の境界座標特定情報復号ステップにおいて，Ｌ個の次元のうちどのｉ個の次元の絶対値がｃに等しいのかを特定する情報を復号する。
【００９２】
次に，５０６の境界座標符号情報復号ステップにおいて，そのｉ個の座標値の符号（正か負か）を決定する。例えば読み込んだビットが０なら正（ｃ），１なら負（−ｃ）と確定する。これをｊ回繰り返す。
【００９３】
次に，５０７の残り座標値復号ステップにおいて，残るＬ−ｉ個の座標値を確定する。具体的には０以上の整数値ｘを復号し，座標値を２ｃ（ｘ−（Ｊ−２）／２）／Ｊとして復号する。これを軸の数（Ｌ−ｉ）だけ繰り返す。
【００９４】
最後に，５０８のベクトル出力ステップにおいて，ここまでの作業で確定したＬ個の座標値をベクトルとして出力する。
【００９５】
以上，距離尺度がＬ∞ノルムの場合の符号化および復号処理の例を説明したが，距離尺度がＬ1 ノルムの場合にも，上記説明から同様に実施できることは明らかである。
【００９６】
以上のベクトル量子化の処理は，コンピュータとソフトウェアプログラムとによっても実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することも，ネットワークを通して提供することも可能である。
【符号の説明】
【００９７】
３０１  信号端子
３０２  初期化器
３０３  メモリ
３０４  設定・修正器
３０５  コスト算出器
３０６  微修正器
３０７  変化量算出器
３０８  比較器
３０９  出力端子
【図１】
2012039657.tif 000012
【図２】
2012039657.tif 000013
【図３】
2012039657.tif 000014
【図４】
2012039657.tif 000015
【図５】
2012039657.tif 000016
【図６】
2012039657.tif 000017
【図７】
2012039657.tif 000018
【図８】
2012039657.tif 000019
【図９】
2012039657.tif 000020
【図１０】
2012039657.tif 000021
【図１１】
2012039657.tif 000022
【図１２】
2012039657.tif 000023