(57)【特許請求の範囲】
【請求項１】
有限個の成分を持つ多次元行列成分の値の符号化に際して，ビットレートを低減する方法であって，
多次元行列の各成分の値を，予め定められた順序で読み出す過程と，
読み出した値が，予め決められた基準値以上の値かどうかを判定し，基準値以上の値の場合には有効な成分とする過程と，
符号化処理対象となっている現在の有効な成分の１つ前に有効な成分と判定された成分の多次元位置情報を蓄積する過程と，
前記蓄積した多次元位置情報と，前記現在の有効な成分の多次元位置情報の差を計算し，前記蓄積した多次元位置情報が示す位置に基づいて，予め定められた複数の座標系の中から１つの座標系を選択し，その選択した１つの座標系における，前記多次元位置情報の差に対応する多次元ベクトルを求める過程と，
前記求めた多次元ベクトルの各成分と前記現在の有効な成分の値とを含む複数の値の組み合わせに対して，１つの可変長符号を割り当てる過程とを有する
ことを特徴とする符号化方法。
【請求項２】
有限個の成分を持つ多次元行列成分の値の符号化に際して，ビットレートを低減する方法であって，
多次元行列の各成分の値を，予め定められた順序で読み出す過程と，
読み出した値が，予め決められた基準値以上の値かどうかを判定し，基準値以上の値の場合には有効な成分とする過程と，
符号化処理対象となっている現在の有効な成分の１つ前に有効な成分と判定された成分の多次元位置情報を蓄積する過程と，
前記蓄積した多次元位置情報と，前記現在の有効な成分の多次元位置情報の差を計算し，多次元ベクトルを求める過程と，
前記求めた多次元ベクトルの成分を量子化する過程と，
前記量子化された多次元ベクトルの各成分と前記現在の有効な成分の値とを含む複数の値の組み合わせに対して，１つの可変長符号を割り当てる過程とを有する
ことを特徴とする符号化方法。
【請求項３】
有限個の成分を持つ多次元行列成分の値の符号化に際して，ビットレートを低減する方法であって，
多次元行列の各成分の値を，予め定められた順序で読み出す過程と，
読み出した値が，予め決められた基準値以上の値かどうかを判定し，基準値以上の値の場合には有効な成分とする過程と，
符号化処理対象となっている現在の有効な成分の１つ前に有効な成分と判定された成分の多次元位置情報を蓄積する過程と，
前記蓄積した多次元位置情報と，前記現在の有効な成分の多次元位置情報の差を計算し，前記蓄積した多次元位置情報が示す位置に基づいて，予め定められた複数の座標系の中から１つの座標系を選択し，その選択した１つの座標系における，前記多次元位置情報の差に対応する多次元ベクトルを求める過程と，
前記求めた多次元ベクトルの成分を量子化する過程と，
前記量子化された多次元ベクトルの各成分と前記現在の有効な成分の値とを含む複数の値の組み合わせに対して，１つの可変長符号を割り当てる過程とを有する
ことを特徴とする符号化方法。
【請求項４】
請求項１，請求項２または請求項３に記載の符号化方法において，
前記１つの可変長符号を割り当てる対象となる複数の値の組み合わせの中に，前記現在の有効な成分が，多次元行列内最後の有効な成分かどうかを示すラスト情報の値を含む
ことを特徴とする符号化方法。
【請求項５】
請求項１から請求項４までのいずれかに記載の符号化方法で作られた可変長符号の復号方法において，
前記可変長符号を入力し，少なくとも多次元ベクトルの各成分と有効な成分の値とを含む値を可変長復号する過程と，
前記可変長復号によって得られた多次元ベクトルの成分を用いて多次元行列内の位置情報を計算することにより，多次元行列成分の値を復号する過程とを有する
ことを特徴とする復号方法。
【請求項６】
有限個の成分を持つ多次元行列成分の値の符号化装置において，
多次元行列の各成分の値を，予め定められた順序で読み出す多次元行列読み出し部と，
読み出した値が，予め決められた基準値以上の値かどうかを判定し，基準値以上の値の場合には有効な成分とする有効成分判定部と，
符号化処理対象となっている現在の有効な成分の１つ前に有効な成分と判定された成分の多次元位置情報を蓄積する前成分座標蓄積部と，
前記前成分座標蓄積部に蓄積した多次元位置情報と，前記有効成分判定部で得られた有効な成分の多次元位置情報の差を計算し，前記前成分座標蓄積部に蓄積した多次元位置情報が示す位置に基づいて，予め定められた複数の座標系の中から１つの座標系を選択し，その選択した１つの座標系における，前記多次元位置情報の差に対応する多次元ベクトルを求めるベクトル計算部と，
前記ベクトル計算部で求めた多次元ベクトルの各成分と前記有効成分判定部で得られた有効な成分の値とを含む複数の値の組み合わせに対して，１つの可変長符号を割り当てるベクトル値符号化部とを備える
ことを特徴とする符号化装置。
【請求項７】
有限個の成分を持つ多次元行列成分の値の符号化装置において，
多次元行列の各成分の値を，予め定められた順序で読み出す多次元行列読み出し部と，
読み出した値が，予め決められた基準値以上の値かどうかを判定し，基準値以上の値の場合には有効な成分とする有効成分判定部と，
符号化処理対象となっている現在の有効な成分の１つ前に有効な成分と判定された成分の多次元位置情報を蓄積する前成分座標蓄積部と，
前記前成分座標蓄積部に蓄積した多次元位置情報と，前記有効成分判定部で得られた有効な成分の多次元位置情報の差を計算し，多次元ベクトルを求めるベクトル計算部と，
前記ベクトル計算部で求めた多次元ベクトルの成分を量子化するベクトル成分量子化部と，
前記量子化された多次元ベクトルの各成分と前記有効成分判定部で得られた有効な成分の値とを含む値の組み合わせに対して，１つの可変長符号を割り当てるベクトル値符号化部とを備える
ことを特徴とする符号化装置。
【請求項８】
有限個の成分を持つ多次元行列成分の値の符号化装置において，
多次元行列の各成分の値を，予め定められた順序で読み出す多次元行列読み出し部と，
読み出した値が，予め決められた基準値以上の値かどうかを判定し，基準値以上の値の場合には有効な成分とする有効成分判定部と，
符号化処理対象となっている現在の有効な成分の１つ前に有効な成分と判定された成分の多次元位置情報を蓄積する前成分座標蓄積部と，
前記前成分座標蓄積部に蓄積した多次元位置情報と，前記有効成分判定部で得られた有効な成分の多次元位置情報の差を計算し，前記前成分座標蓄積部に蓄積した多次元位置情報が示す位置に基づいて，予め定められた複数の座標系の中から１つの座標系を選択し，その選択した１つの座標系における，前記多次元位置情報の差に対応する多次元ベクトルを求めるベクトル計算部と，
前記ベクトル計算部で求めた多次元ベクトルの成分を量子化するベクトル成分量子化部と，
前記量子化された多次元ベクトルの各成分と，前記有効成分判定部で得られた有効な成分の値の組み合わせに対して，１つの可変長符号を割り当てるベクトル値符号化部とを備える
ことを特徴とする符号化装置。
【請求項９】
請求項６，請求項７または請求項８に記載の符号化装置において，
前記有効成分判定部で得られた有効な成分が，多次元行列内最後の有効な成分かどうかを判断し，これをラスト情報として出力するラスト判定部を備え，
前記１つの可変長符号を割り当てる対象となる複数の値の組み合わせの中に，前記ラスト判定部が出力するラスト情報の値を含む
ことを特徴とする符号化装置。
【請求項１０】
請求項６から請求項９までのいずれかに記載の符号化装置で作られた可変長符号の復号装置において，
前記可変長符号を入力し，少なくとも多次元ベクトルの各成分と有効な成分の値とを含む値を可変長復号するベクトル値復号部と，
前記可変長復号によって得られた多次元ベクトルの成分を用いて多次元行列内の位置情報を計算する位置情報計算部と，
前記位置情報計算部によって計算された多次元行列内の位置情報に従って前記可変長復号によって得れた有効な成分の値を，多次元行列内に代入する値代入部とを備える
ことを特徴とする復号装置。
【請求項１１】
請求項１から請求項４までのいずれかに記載の符号化方法を，コンピュータに実行させるための符号化プログラム。
【請求項１２】
請求項５に記載の復号方法を，コンピュータに実行させるための復号プログラム。
【請求項１３】
請求項１から請求項４までのいずれかに記載の符号化方法を，コンピュータに実行させるためのプログラムを記録した
ことを特徴とする符号化プログラムのコンピュータ読み取り可能な記録媒体。
【請求項１４】
請求項５に記載の復号方法を，コンピュータに実行させるためのプログラムを記録した
ことを特徴とする復号プログラムのコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，情報源符号化における可変長符号化と可変長復号に関するものである。
【０００２】
【従来の技術】
多次元行列の各成分が，多数の同じ値（Ａ）と，それと異なる値（Ｂ1 ，Ｂ2 ，... ，Ｂn ）とで構成されている場合，この行列の成分を符号化する手法に，ランレングス符号化を応用する方法がある。まず，多次元行列中の成分を，ある定められた順序でスキャンして，１次元配列にする。この１次元配列中では，同じ値（Ａ）が多数を占めているため，値（Ａ）が連続して並ぶ場合が多い。そこで値（Ａ）の並んだ成分の数をランレングス符号化する。あるいは，値（Ａ）の並ぶ数（ＬA ）と，値（Ａ）の前後にある値（Ｂi ；ｉ＝１，... ，ｎ）との間に相関がある場合には，（ＬA ）と（Ｂi ）の組み合わせに対して，１つの可変長符号を割り当てる２次元可変長符号化を行う方法もある。ここで一般的に，（ＬA ）をラン，（Ｂi ）をレベルと呼ぶ。
【０００３】
例えば，２次元画像の符号化では一般に，画素を離散コサイン変換（ＤＣＴ）した後の係数を２次元可変長符号化する。まず，各画素を縦横８画素のブロックに分割し，ブロック毎に２次元ＤＣＴする。２次元ＤＣＴでは，低周波数部分には０以外の値が集中し，逆に高周波数部分には値０が多くなる性質がある。このＤＣＴ係数を８×８の２次元行列とみなす。
【０００４】
図１３は，８×８ＤＣＴ係数上のジグザグスキャンの例を示す図である。低周波数部分から高周波数部分へジグザグスキャンして１次元配列にする。値が０の係数の連続する数をランとし，その後の係数の値をレベルとして，２次元可変長符号化する。予めランとレベルの各組み合わせに対して，１つの符号を対応させたルックアップテーブルを作っておき，このルックアップテーブルを利用して２次元可変長符号化する。ルックアップテーブルにない組み合わせの場合には，エスケープ符号を使った固定長符号化を行う。あるいは，２次元可変長符号化を行う方法として，ルックアップテーブルを利用しない，算術符号化を用いることも可能である。
【０００５】
特に画像符号化方式ＭＰＥＧ−１では，２次元ＤＣＴに，大きな値の係数の周囲には小さい値の係数が存在する性質があることを利用して，２次元可変長符号化のルックアップテーブルを構成している。例えば，値の大きいランに対しては，値の小さいレベルとの組み合わせに符号長の短い符号を用意しておく。
【０００６】
また，多次元行列中の値（Ｂi ）と，値（Ａ）の長さ（ＬA ）の２次元可変長符号化を行う前に，値（Ｂi ）を量子化する方法がある。量子化によって，値（Ｂi ）が，より小さい値（ＢＱi ）に変換されるとすると，値（ＢＱi ）と（ＬA ）の組み合わせを２次元可変長符号化する。一般的に，２次元可変長符号化では，値（Ｂi ）が小さいほど，より短い符号長の符号を割り当てるため，量子化により符号量の削減が可能となる。
【０００７】
また，値（Ｂi ）と（ＬA ）を可変長符号化する際に，値（Ｂi ）が，多次元行列中で最後の，値（Ａ）以外の成分かどうかを示すラスト情報を含めて符号化する３次元可変長符号化方法がある。
【０００８】
例えば画像符号化方式ＭＰＥＧ−４では，２次元ＤＣＴした係数のうち，値が０以外の係数を符号化する際に，最後の０以外の係数でない場合にはラスト情報を０に，最後の０以外の係数である場合にはラスト情報を１に設定し，ランとレベルとラスト情報の３次元可変長符号化を行う。各ランとレベルとラストに対して符号を対応させたルックアップテーブルを予め作っておき，それを参照しながら３次元可変長符号化を行う。
【０００９】
逆に画像符号化方式ＭＰＥＧ−１では，２次元ＤＣＴの最後の係数を符号化した後に，ＥＯＢという特有なビットパターンをした固定長符号を出力する。このＥＯＢは，復号側でビット配列から２次元ＤＣＴの係数を可変長復号する際に，復号するべき係数が終わったことを知ることに利用される。このＥＯＢ符号は一般的に符号長が長いため，２次元ＤＣＴ内の符号化する係数が少ない場合には，符号化効率が低下する。
【００１０】
３次元可変長符号化は，ラスト情報の符号化を可変長符号化で行うことにより，ＥＯＢの出力を避けることができる。すなわち，２次元ＤＣＴの符号化する係数が少ない場合に，符号化効率の低下を避けることができる。
【００１１】
また，３次元画像符号化で３次元ＤＣＴを使う方法もある。この場合には，３次元ＤＣＴ係数をジグザグスキャンして１次元配列にする。その後，２次元画像符号化と同様に，１次元配列に対して，２次元可変長符号化あるいは３次元可変長符号化を行う。
【００１２】
【発明が解決しようとする課題】
多次元行列中で，値の大きな成分の周囲に値の小さな成分がある場合には，符号化すべき成分がかたまって存在する。例えば，２次元画像符号化における２次元ＤＣＴでは，値の大きい係数の周囲に，値の小さい係数が存在する。このような成分間の相関がある場合には，多次元行列の各成分を，一旦１次元配列にする方法であると，成分間の相関を損なってしまう。
【００１３】
図１４は，８×８ＤＣＴ係数位置の例を示す図である。例えば，図１４に示すような２次元ＤＣＴにおいて，係数Ａ〜Ｇの値が０以外であり，係数Ｄを中心に他の成分が配置されている場合を考える。ジグザグスキャンして１次元配列にするので，係数Ａから係数Ｂは連続しており，短い符号長の符号を割り当てることができる。しかし，係数Ｂから係数Ｃまでの間には多くの値０の係数が存在するため，割り当てられる可変長符号の符号長が長くなるか，あるいはエスケープ符号を使った固定長となる。すなわち，隣り合う係数の符号化に関して，スキャン方向に隣り合う場合には短い符号長の符号を割り当てられるが，スキャン方向ではない場合には短い符号長を割り当てられない。
【００１４】
このように，多次元行列を１次元配列に変換して符号化する方法では，変換に用いるスキャンの方向以外の方向に関する相関性を損なう。このため，従来の方法では，符号化効率の低下を引き起こすことがある。
【００１５】
【課題を解決するための手段】
上記の課題を解決するため，本発明は，多次元で表される位置の差分ベクトルの成分とレベルの組み合わせに対して，可変長符号語を割り当て，かつ可変長符号化する２成分間の位置の差分情報を，上記多次元の座標系とは異なる座標系で求めることを，最も主要な特徴とする。また，位置の差分ベクトルの成分を量子化することを特徴とする。
【００１６】
具体的には，本発明は第１に，有限個の成分を持つ多次元行列成分の値の符号化に際して，ビットレートを低減する方法であって，少なくとも１つの可変長符号語の形成において，２成分間の位置の差分情報を，そのうちの片方の成分の値と共に使うことを特徴とする。
【００１７】
この第１の特徴では，多次元行列中の符号化データとして必要な成分の位置情報の符号化に，成分間の位置の差分を使う。Ｎ次元行列の場合，成分Ｐの位置は，次の式（１）で表現される。
【００１８】
Ｐ（ｐ1 ，ｐ2 ，... ，ｐn ）                                  （１）
成分Ｐに対する成分Ｑの位置の差分は，Ｎ次元ベクトルとなり，このベクトルＶ（Ｐ，Ｑ）は，式（２）で示される。
【００１９】
Ｖ（Ｐ，Ｑ）＝（ｑ1 −ｐ1 ，ｑ2 −ｐ2 ，... ，ｑn −ｐn ）    （２）
そして，多次元行列中の，符号化データとして必要な成分の値レベルと，位置の差分ベクトルの成分の組み合わせに対して，１つの可変長符号を割り当てる。
【００２０】
ここで，ベクトルＶ（Ｐ，Ｑ）のノルムの大きさの小さい順に符号長の短い符号を割り当てると，隣接する成分はノルムが小さい値となるため，短い符号長で符号化することができる。これにより，１次元配列に変換する方法において失われた，スキャン方向以外の方向に関する相関性を失うことなく，効率よく符号化することが可能となる。
【００２１】
さらに，差分ベクトルのノルムの大きな場合には，値の小さいレベルが多くなる相関性がある。そのため，差分ベクトルの成分とレベルの組み合わせに対して１つの可変長符号を割り当てる。このように，差分ベクトルの成分とレベルの組み合わせに対する可変長符号化を行うことにより，差分ベクトルの成分とレベルを個別に符号化するよりも，より効率良く可変長符号化することができる。
【００２２】
図１は，８×８ＤＣＴ係数上の２次元ベクトル符号化の一例（例１）を示す。例えば，２次元ＤＣＴの場合，図１に示すようなＸ軸（Ｖx ）とＹ軸（Ｖy ）を持つ２次元座標を設定すると，係数Ｂから係数Ｃはベクトルとして（１，０）と表現できる。このようにノルムの小さいベクトルに対して，符号長の短い符号を割り当てれば，符号化効率を向上することができる。
【００２３】
本発明において，上記１つの可変長符号を割り当てる対象となる複数の値の組み合わせの中に，現在の有効な成分が，多次元行列内最後の有効な成分かどうかを示すラスト情報の値を含ませることもできる。
【００２４】
このようにすれば，上記の差分ベクトルの成分と，符号化する成分の値と，多次元行列内で符号化する成分が，その成分で最後であるかどうかを示すラスト情報の組み合わせに対して，１つの可変長符号を割り当てることができる。これにより，多次元行列内の，符号化する成分の数が少ない場合に発生する符号化効率の低下を避けることができる。
【００２５】
また，本発明の実施においては，上記符号化方法で作られる可変長符号語を，予めルックアップテーブルに記録しておき，ルックアップテーブルを使って可変長符号化するようにしてもよい。
【００２６】
上記可変長符号語を予め作ってルックアップテーブルに記録しておくことにより，多次元行列の符号化において，ルックアップテーブルを参照しながら可変長符号化することが可能となる。
【００２７】
本発明は第２に，上記の符号化方法において，可変長符号化する２成分間の位置の差分情報を，多次元行列とは異なる座標系で求めることを特徴とする。この多次元行列とは異なる座標系は，差分を計算する原点の成分の位置毎に変更することができる。
【００２８】
この第２の特徴によれば，多次元行列の符号化において，差分ベクトルを多次元行列とは異なる座標系に変換して求めることができる。図２は，８×８ＤＣＴ係数上の２次元ベクトル符号化の一例（例２）を示している。例えば，２次元ＤＣＴにおいて，係数Ａに対しては図１に示すような座標系を適用するのではなく，図２に示すようなＸ軸（Ｖx ）とＹ軸（Ｖy ）とからなる座標系を使うことができる。これにより係数Ａから係数Ｂの差分ベクトルは（１，０）と表現でき，より符号長の短い符号を割り当てることができる。
【００２９】
さらに，本発明において差分ベクトルを多次元行列とは異なる座標系に変換する際に，差分ベクトルの原点の位置毎に座標系を変更することができる。例えば，２次元ＤＣＴにおいて，係数Ａに対しては図２に示す座標系を用い，係数Ｂに対しては図１に示すような座標系を適用することが可能となる。
【００３０】
別の本発明は，上記第１の特徴を有する符号化方法において，可変長符号化する２成分間の位置の差分情報を量子化してから，可変長符号化を行うことを特徴とする。
【００３１】
この発明によれば，多次元行列の符号化において，差分ベクトルの成分の値を量子化した後で，可変長符号化することができる。これにより，差分ベクトルのノルムが小さい程，符号長の短い符号を割り当てるような可変長符号化を行う場合には，より符号化効率を向上することができる。
さらに，上記１つの可変長符号を割り当てる対象となる複数の値の組み合わせの中に，現在の有効な成分が，多次元行列内最後の有効な成分かどうかを示すラスト情報の値を含ませることもできる。
【００３２】
また，本発明は，有限個の成分を持つ多次元行列成分の値の復号において，上記の符号化方法で作られた可変長符号から，少なくとも多次元ベクトルの各成分と有効な成分の値とを含む値を可変長復号し，多次元ベクトルの成分を用いて多次元行列内の位置情報を計算することにより，多次元行列成分の値を復号することを特徴とする。ここでは，上記の符号化方法で作られた可変長符号語を，予めルックアップテーブルに記録しておき，ルックアップテーブルを使って可変長復号することができる。
【００３３】
この発明によれば，多次元行列の復号において，上記発明による符号化方法によって出力されるビット配列を，ルックアップテーブル等を使って復号することができる。
【００３４】
また，上記符号化方法を実施する符号化装置を構成することができ，上記復号方法を実施する復号装置を構成することもできる。符号化装置では，多次元行列の各成分の値が予め決められた基準を満たす値かどうかを判定し，満たす場合には有効な成分とする有効成分判定部を設けることにより，多次元行列中から有効な成分を判定して，有効な成分のみを符号化することが可能である。有効成分であるかどうかを判定する基準としては，例えば次のものが挙げられる。
（ａ）基準値Ｔ以上の値の場合を有効とする。Ｔが１の場合には，０以外の場合に有効な成分とみなすことができる。
【００３５】
以上の符号化方法および復号方法は，回路化されたハードウェアによって実現することができるだけでなく，コンピュータと，そのコンピュータにインストールされ実行されるソフトウェアプログラムによって実現することができ，そのプログラムは，コンピュータが読み取り可能な可搬媒体メモリ，半導体メモリ，ハードディスク等の適当な記録媒体に格納することができる。
【００３６】
【発明の実施の形態】
以下，本発明の実施の形態を図面を参照しながら説明する。例として，２次元の縦横８画素の画像を２次元ＤＣＴし，ＤＣＴ係数を可変長符号化する画像符号化装置と画像復号装置の構成と動作例を示す。この実施の形態では，ＤＣＴ係数の係数の値と，位置の差分ベクトルを量子化してから可変長符号化するものとする。また，可変長符号化では，係数の値と，差分ベクトルの成分と，ラスト情報を使うものとする。
【００３７】
図３は，本実施の形態における画像符号化装置の構成例を示す図である。画像符号化装置１は，ＤＣＴ係数の値を量子化する値量子化部１０１と，ＤＣＴ係数の値を図１３に示した順序で読み出す多次元行列読み出し部１０２と，読み出した値が０かどうかを判定して０以外の場合には有効な成分とする有効成分判定部１０３と，有効な成分の値を蓄積する値蓄積部１０４と，有効な成分の２次元位置情報を蓄積する前成分座標蓄積部１０５と，前成分座標蓄積部１０５に蓄積した２次元位置情報と，有効成分判定部１０３で得られた有効な成分の２次元位置情報の差を計算し，２次元ベクトルを求めるベクトル計算部１０６と，２次元ベクトルの成分を量子化するベクトル成分量子化部１０７と，量子化した２次元ベクトルの成分を逆量子化して２次元位置情報を計算し，それをもとに前成分の位置情報を求めて前成分座標蓄積部１０５に蓄積するベクトル成分逆量子化部１０９と，ベクトル計算部１０６で求めたベクトルの成分を蓄積するベクトル蓄積部１０８と，有効成分判定部１０３で有効な成分がＤＣＴ係数内の最後まで得られない場合にはラスト情報として１を，得られた場合にはラスト情報として０を出力するラスト判定部１１０と，ベクトル成分量子化部１０７で求めた２次元ベクトルの各成分と，有効成分判定部１０３で得られた有効な成分の値と，ラスト判定部１１０で得られるラスト情報の組み合わせに対して，１つの可変長符号を割り当てるベクトル値ラスト符号化部１１１と，多次元ベクトルの成分と有効な成分の値とラスト情報に対して，１つの可変長符号を割り当てたルックアップテーブルを蓄積するベクトル値ラストテーブル部１１２とを備える。
【００３８】
図４は，２次元ベクトル座標の例を示す図である。ベクトル計算部１０６で使用するベクトルの座標系は，前成分座標蓄積部１０５に蓄積した位置情報に従って，図４に示す３種類を変更するものとする。行列成分（ｘ，ｙ）（ｘ，ｙ＝０，... ，７）に対して，ｘが偶数または０でｙが０の場合には図４（ａ）の座標系を適用し，それ以外で，ｘ＋ｙが偶数の場合には図４（ｂ）の座標系を適用し，ｘ＋ｙが奇数の場合には図４（ｃ）の座標系を適用するものとする。
【００３９】
ベクトル値ラストテーブル部１１２には，図５に示すルックアップテーブルが蓄積されているものとする。なお，このルックアップテーブルは，ベクトルＶx 成分，ベクトルＶy 成分，量子化されたＤＣＴ係数の値，ラスト情報の組み合わせによって，符号語が参照される構成になっている。
【００４０】
値量子化部１０１は，式（３）に従って全ての係数の値を量子化するものとする。Ｉは入力値を示し，Ｏは出力値を示す。
【００４１】
Ｏ＝Ｉ／２                                                    （３）
ベクトル成分量子化部１０７は，位置の差分ベクトル（Ｉ1 ，Ｉ2 ）を入力ベクトルとして出力ベクトル（Ｏ1 ，Ｏ2 ）を求めるものであり，２次元ベクトルの成分を式（４）に従って量子化するものとする。ただし，ｘ，ｙはそれぞれ前成分座標蓄積部１０５に蓄積した位置を示すものとする。なお，前成分座標蓄積部１０５には，初期値として（０，０）が予め蓄積されているものとする。
【００４２】
Ｏi ＝（Ｉi ＋１）／（（ｘ＋ｙ＋７）／７）                    （４）
ベクトル成分逆量子化部１０９は式（５）に従って逆量子化するものとする。
【００４３】
Ｏi ＝Ｉi ＊（（ｘ＋ｙ＋７）／７）−１                        （５）
図６は，本実施の形態における入力ＤＣＴ係数の例を示す図である。上記のような前提の下で，すでに２次元ＤＣＴが施された図６に示す２次元ＤＣＴ係数が得られた場合に，画像符号化装置１は次のように動作する。まず，値量子化部１０１は，ＤＣＴ係数の値を式（３）に従って量子化する。図７は，量子化されたＤＣＴ係数の例を示す図である。図６のＤＣＴ係数が量子化されると，図７のようになる。多次元行列読み出し部１０２は，図１３に示した順序で量子化した値を読み出す。
【００４４】
多次元行列読み出し部１０２で読み出した順序で係数を符号化する手順を示す。行列成分位置（ｘ，ｙ）の値をＡ（ｘ，ｙ）と記すことにする。有効成分判定部１０３は，Ａ（１，０）が０以外であるので有効な成分と判定する。Ａ（１，０）を値蓄積部１０４に蓄積する。
【００４５】
ベクトル計算部１０６は，前成分座標蓄積部１０５に蓄積した位置（０，０）と現成分の座標位置（１，０）の差分を求める。このとき，ベクトルの座標系は図４（ａ）を用いる。差分ベクトルは（１，０）と求めることができる。
【００４６】
ベクトル成分量子化部１０７は，式（４）を使って量子化して（１，０）を得る。これをベクトル蓄積部１０８に蓄積する。ベクトル成分逆量子化部１０９は，式（５）を使って逆量子化し（１，０）を得る。そして，ベクトル座標系は図４（ｃ）であるため，このベクトル成分を行列成分に座標変換して（１，０）を得て，前成分座標蓄積部１０５に（０，０）＋（１，０）＝（１，０）を蓄積する。
【００４７】
ラスト判定部１１０は，有効成分判定部１０３で有効な値が得られたので，ラスト情報として０を出力する。ベクトル値ラスト符号化部１１１は，ラスト情報のみ得られたときには何も動作しない。
【００４８】
続いて，有効成分判定部１０３は，Ａ（０，１）が０以外であるので有効な成分と判定する。Ａ（０，１）を値蓄積部１０４に蓄積する。ベクトル計算部１０６は，前成分座標蓄積部１０５に蓄積した位置（１，０）と（０，１）の差分を求める。このとき，ベクトルの座標系は図４（ｃ）を用いる。差分ベクトルは（１，０）と求めることができる。ベクトル成分量子化部１０７は，式（４）を使って量子化して（１，０）を得る。これをベクトル蓄積部１０８に蓄積する。ベクトル成分逆量子化部１０９は，式（５）を使って逆量子化し（１，０）を得る。そして，このベクトル成分を行列成分に座標変換して（−１，１）を得て，前成分座標蓄積部１０５に（１，０）＋（−１，１）＝（０，１）を蓄積する。
【００４９】
ラスト判定部１１０は，有効成分判定部１０３で有効な値が得られたので，ラスト情報として０を出力する。ベクトル値ラスト符号化部１１１は値蓄積部１０８に蓄積されていた値Ａ（０，１）と，ベクトル蓄積部１０８に蓄積されていた（１，０）と，ラスト情報０を，ベクトル値ラストテーブル部１１２に記録されたルックアップテーブルを使って可変長符号化する。
【００５０】
このような処理を繰り返して，図８に示す順序でＤＣＴ係数を可変長符号化する。図８は，符号化されるＤＣＴ係数の順序の例を示している。最後の係数Ａ（３，５）を符号化した後で，有効成分判定部１０３は，ＤＣＴ係数内に有効な成分を得られない。この場合には，ラスト判定部１１０は，ラスト情報として１を出力する。ベクトル値ラスト符号化部１１１は，値蓄積部１０４に蓄積されていた値Ａ（２，６）と，ベクトル蓄積部１０８に蓄積されていた（１，０）と，ラスト情報の１を，ベクトル値ラストテーブル部１１２に記録されたルックアップテーブルを使って可変長符号化する。
【００５１】
このような処理の繰り返しによって得られる値Ａ（ｘ，ｙ）とベクトル成分とラスト情報の一覧は，図９に示すようになる。図９は，ベクトル値ラスト符号化部１１１で符号化する組み合わせの例を示している。図１０は，ベクトル値ラスト符号化部１１１で出力される符号語の例を示しており，図９のそれぞれの組み合わせごとに，ベクトル値ラストテーブル部１１２のルックアップテーブル（図７）を参照して，符号語が決定され，図１０のような可変長符号化のビット列が出力される。
【００５２】
図１１は，本実施の形態における画像復号装置の構成例を示す図である。画像復号装置２は，ベクトル値ラストテーブル部２０１と，１つの可変長符号を検出して，多次元ベクトルの各成分と有効な成分の値とラスト情報を復号するベクトル値ラスト復号部２０２と，ベクトル値ラスト復号部２０２で得られる多次元ベクトルの成分を逆量子化するベクトル成分逆量子化部２０３と，多次元行列の成分の位置情報を蓄積する前成分座標蓄積部２０４と，ベクトル成分逆量子化部２０３で得られる多次元ベクトルの成分と，前成分座標蓄積部２０４に蓄積した位置情報から，多次元行列内の位置情報を計算する位置情報計算部２０５と，ベクトル値ラスト復号部２０２で得られる有効な成分の値を逆量子化する値逆量子化部２０６と，値逆量子化部２０６で得られる有効な成分の値を位置情報計算部２０５で得られた位置のＤＣＴ係数に代入する値代入部２０７と，ベクトル値ラスト復号部２０２で得られるラスト情報が１であった場合に，値が得られていない係数の値を０にする非有効成分値設定部２０８とを備える。
【００５３】
前成分座標蓄積部２０４には，位置（０，０）が予め蓄積されているものとする。位置情報計算部２０５では，前成分座標蓄積部２０４に蓄積した位置情報に従って，ベクトル成分逆量子化部２０３で得られたベクトルの座標系を変換し，位置情報を計算するものとする。ベクトルの座標系は，図４に示す３種類を変更するものとする。行列成分（ｘ，ｙ）（ｘ，ｙ＝０，... ，７）に対して，ｘが偶数または０でｙが０の場合には図４（ａ）の座標系を適用し，それ以外で，ｘ＋ｙが偶数の場合には図４（ｂ）の座標系を適用し，ｘ＋ｙが奇数の場合には図４（ｃ）の座標系を適用するものとする。
【００５４】
ベクトル値ラストテーブル部２０１には，図５に示すルックアップテーブルが蓄積されているものとする。値逆量子化部２０６は式（６）に従って全ての係数の値を量子化するものとする。Ｉは入力値を示し，Ｏは出力値を示す。
【００５５】
Ｏ＝Ｉ＊２                                                    （６）
ベクトル成分逆量子化部２０３は式（５）に従って逆量子化するものとする。
【００５６】
このような前提の下で，まずベクトル値ラスト復号部２０２は，ビット列から図１０の順に可変長符号語を検出し，個々の可変長符号語毎に，ベクトル値ラストテーブル部２０１に記録してあるルックアップテーブルを参照して，ベクトル成分と有効な値とラスト情報を復号する。
【００５７】
最初の可変長符号語に対して，ベクトル（１，０）と値５とラスト情報０を得る。ベクトル成分逆量子化部２０３は式（５）に従ってベクトルを逆量子化し（１，０）を得る。位置情報計算部２０５は，前成分座標蓄積部２０４に（０，０）が蓄積されていることから，図４（ａ）の座標系を使ってベクトル（１，０）を（１，０）に変換し，前成分座標蓄積部２０４に蓄積されている（０，０）に加算する。これによって，（０，０）＋（１，０）＝（１，０）と位置情報が求まる。この位置情報は，前成分座標蓄積部２０４に蓄積する。次に値逆量子化部２０６は，値５を式（６）に従って逆量子化して値１０を得る。値代入部２０７はＤＣＴ係数位置（１，０）に値１０を代入する。
【００５８】
続いて，ベクトル値ラスト復号部２０２は，次の可変長符号語に対して，ベクトル（１，０）と値５とラスト情報０を得る。ベクトル成分逆量子化部２０３は式（５）に従ってベクトルを逆量子化し（１，０）を得る。位置情報計算部２０５は，前成分座標蓄積部２０４に（１，０）が蓄積されていることから，図４（ｃ）の座標系を使ってベクトル（１，０）を（−１，１）に変換し，前成分座標蓄積部２０４に蓄積されている（１，０）に加算する。これによって，（１，０）＋（−１，１）＝（０，１）と位置情報が求まる。この位置情報は，前成分座標蓄積部２０４に蓄積する。次に値逆量子化部２０６は，値５を式（６）に従って逆量子化して値１０を得る。値代入部２０７はＤＣＴ係数位置（０，１）に値１０を代入する。
【００５９】
このような処理を繰り返して，ビット列を最後まで可変長復号する。最後の可変長符号語をベクトル値ラスト復号部２０２が復号したときに，ラスト情報として１を得る。非有効成分値設定部２０８は値が得られていない係数に値０を代入する。
【００６０】
図１２は，画像復号装置２で得られるＤＣＴ係数の例である。図１２のように，本実施の形態では，有効な成分間のベクトルを量子化するため，ＤＣＴの位相がずれる係数もあるが，式（４）（５）のように高周波でのみずれる可能性があるように設定することができる。すなわち，一般的に高周波の歪みは視覚的な劣化が少ないため，位相のずれによる画質劣化は少なくすることができる。
【００６１】
また，本実施の形態では，予めルックアップテーブルを記録しておき，それを参照することによって可変長符号化と復号を行った。このテーブルを利用せずに，算術符号化を使って可変長符号化と復号をすることも可能である。この場合には，画像符号化装置１に，ベクトル値ラスト符号化部１１１とベクトル値ラストテーブル部１１２の代わりに，ベクトル値ラスト算術符号化部（図示省略）を備える。また画像復号装置２に，ベクトル値ラスト復号部２０２とベクトル値ラストテーブル部２０１の代わりに，ベクトル値ラスト算術復号部（図示省略）を備える。
【００６２】
また，本実施の形態では有効な成分の値を量子化したが量子化しない方法も可能である。この場合には，画像符号化装置１に値量子化部１０１を備えない。また画像復号装置２に値逆量子化部２０６を備えない。
【００６３】
また，本実施の形態では有効な成分間の位置情報を量子化したが量子化しない方法も可能である。この場合には，画像符号化装置１にベクトル成分量子化部１０７とベクトル成分逆量子化部１０９を備えない。また画像復号装置２にベクトル成分逆量子化部２０３を備えない。
【００６４】
また，本実施の形態ではラスト情報を含めて可変長符号化を行ったが，含めない方法も可能である。この場合には，画像符号化装置１にラスト判定部１１０と値蓄積部１０４とベクトル蓄積部１０８を備えない。また画像復号装置２に非有効成分値設定部２０８を備えない。
【００６５】
また，本実施の形態では有効な成分間の位置情報を２次元ベクトルとし，その座標系を変換したが変換しない方法も可能である。
【００６６】
この実施の形態のように本発明による画像符号化装置１と画像復号装置２では，有効な成分間のベクトルのノルムが小さいほど，符号長の短い可変長符号を割り当てることが可能となる。
【００６７】
本発明は，画像符号化に限らず，有限個の成分を持つ多次元行列成分の値の符号化であれば適用することができ，同様にビットレートを低減することが可能である。
【００６８】
【発明の効果】
以上の発明によれば，多次元で表される位置の差分ベクトルの成分とレベルの組み合わせに対して，可変長符号語を割り当てる。したがって，多次元で表される位置の各成分の相関を損なわずに可変長符号化することができる。特に，多次元行列内の，２成分間の位置の差分が小さいほど，符号長の短い可変長符号を割り当てることができ，ビットレートを低減することが可能となる。
【図面の簡単な説明】
【図１】８×８ＤＣＴ係数上の２次元ベクトル符号化の一例を示す図である。
【図２】８×８ＤＣＴ係数上の２次元ベクトル符号化の他の一例を示す図である。
【図３】本実施の形態における画像符号化装置の構成例を示す図である。
【図４】２次元ベクトル座標の例を示す図である。
【図５】ベクトル値ラストテーブル部に蓄積したルックアップテーブルの例を示す図である。
【図６】本実施の形態における入力ＤＣＴ係数の例を示す図である。
【図７】量子化されたＤＣＴ係数の例を示す図である。
【図８】符号化されるＤＣＴ係数の順序の例を示す図である。
【図９】ベクトル値ラスト符号化部で符号化する組み合わせの例を示す図である。
【図１０】ベクトル値ラスト符号化部で出力される符号語の例を示す図である。
【図１１】本実施の形態における画像復号装置の構成例を示す図である。
【図１２】画像復号装置で得られるＤＣＴ係数の例を示す図である。
【図１３】８×８ＤＣＴ係数上のジグザグスキャンの例を示す図である。
【図１４】８×８ＤＣＴ係数位置の例を示す図である。
【符号の説明】
１      画像符号化装置
１０１  値量子化部
１０２  多次元行列読み出し部
１０３  有効成分判定部
１０４  値蓄積部
１０５  前成分座標蓄積部
１０６  べクトル計算部
１０７  べクトル成分量子化部
１０８  ベクトル蓄積部
１０９  ベクトル成分逆量子化部
１１０  ラスト判定部
１１１  ベクトル値ラスト符号化部
１１２  ベクトル値ラストテーブル部
２      画像復号装置
２０１  ベクトル値ラストテーブル部
２０２  ベクトル値ラスト復号部
２０３  ベクトル成分逆量子化部
２０４  前成分座標蓄積部
２０５  位置情報計算部
２０６  値逆量子化部
２０７  値代入部
２０８  非有効成分値設定部
【図１】
0003866539.tif 000002
【図２】
0003866539.tif 000003
【図３】
0003866539.tif 000004
【図４】
0003866539.tif 000005
【図５】
0003866539.tif 000006
【図６】
0003866539.tif 000007
【図７】
0003866539.tif 000008
【図８】
0003866539.tif 000009
【図９】
0003866539.tif 000010
【図１０】
0003866539.tif 000011
【図１１】
0003866539.tif 000012
【図１２】
0003866539.tif 000013
【図１３】
0003866539.tif 000014
【図１４】
0003866539.tif 000015