(57)【要約】【課題】画像を符号量上限値の下で符号化する際に、その画像を特定の大きさに分割し、その分割された各ブロックのビットプレーンを廃棄するビット位置を決定するときに、歪量が最小となるビット位置を少ない演算量で求める符号量制御方法、符号量制御装置及び符号量制御プログラムを提供する。【解決手段】符号量制御装置３は、コードブロック分割手段１０と、歪・符号量テーブル生成手段１１と、符号量基準値リスト生成手段１２と、作業テーブル生成手段１３と、逆探索手段１４と、ビット切り捨て手段１５と、を備え、符号量上限値を上限とする複数の符号量基準値毎に、第１番目のブロックから特定ブロックまでの歪総量を最小とするビット位置及びそのときの歪総量を作業テーブルとして生成し、その作業テーブルから全ブロックの歪総量を最小とするビット位置を逆探索することを特徴とする。【選択図】　　　図１
2004056605.tif 000002
【特許請求の範囲】
【請求項１】
符号化対象となる画像を特定の大きさのブロックに分割して、その分割されたブロックの順に可変長符号を生成する画像符号化において、与えられた符号量上限値の範囲内で前記画像を符号化するために、前記各ブロックの符号量を制御する符号量制御方法であって、
前記ブロックを量子化する複数の量子化レベルに基づいて前記ブロックを符号化したときの符号量と、前記量子化レベルに基づいて前記ブロックから廃棄される歪量とを算出し、歪・符号量テーブルとして生成する歪・符号量テーブル生成ステップと、
前記符号量上限値を最大値とする複数の符号量基準値からなる符号量基準値リストを生成する符号量基準値リスト生成ステップと、
第１番目のブロックで前記符号量基準値に最も近い符号量となる前記量子化レベル及びそのときの歪量を、前記符号量基準値と前記ブロックとを対応付けたインデックステーブル及び歪総量テーブルの初期値として設定する作業テーブル初期値設定ステップと、
前記符号量基準値毎に、前記歪総量テーブルを参照して、第１番目のブロックから特定ブロックまでの歪総量を最小とする量子化レベル及びそのときの歪総量を順次決定して、第２番目以降のブロックにおける前記インデックステーブル及び前記歪総量テーブルの値を設定する作業テーブル設定ステップと、
この作業テーブル設定ステップで設定した前記インデックステーブルから、前記全ブロックの歪総量を最小とする量子化レベルを逆探索して求める逆探索ステップと、
を含んでいることを特徴とする符号量制御方法。
【請求項２】
符号化対象となる画像を特定の大きさのブロックＢ（ｊ）（ｊ＝１，…，Ｎ）に分割して、そのブロック毎に可変長符号を生成する画像符号化において、与えられた符号量上限値Ｋの範囲内で前記画像を符号化するために、前記各ブロックの符号量を制御する符号量制御方法であって、
前記ブロックを量子化する複数の量子化レベルｔに基づいて前記ブロックＢ（ｊ）を符号化したときの符号量Ｒ（ｔ，ｊ）と、前記量子化レベルｔに基づいて前記ブロックＢ（ｊ）から廃棄される歪量Ｄ（ｔ，ｊ）とを算出し、歪・符号量テーブルとして生成する歪・符号量テーブル生成ステップと、
前記符号量上限値Ｋを最大値とするＳ（Ｋ）個の符号量基準値ｋ（ｉ）（ｉ＝１，…，Ｓ（Ｋ）＝Ｋ）からなる符号量基準値リストを生成する符号量基準値リスト生成ステップと、
前記符号量基準値ｋ（ｉ）に最も近い符号量Ｒ（ｔ，１）となる前記量子化レベルｔ及びそのときの歪量Ｄ（ｔ，１）を、前記符号量基準値ｋ（ｉ）と前記ブロックＢ（ｊ）とを対応付けたインデックステーブルＩｄｘ（ｉ，ｊ）及び歪総量テーブルＦ（ｉ，ｊ）の初期値として設定する作業テーブル初期値設定ステップと、
符号量をｒとし、そのｒに最も近い前記符号量基準値ｋ（ｉ）のインデックスｉを返す写像をψ（ｒ）として、歪総量ｆ（ｉ，ｊ；ｔ）をＤ（ｔ，ｊ）＋Ｆ（ψ（ｋ（ｉ）−Ｒ（ｔ，ｊ）），ｊ−１）と定義したときの、前記歪総量ｆ（ｉ，ｊ；ｔ）を最小とする前記量子化レベルｔ及びそのときの前記歪総量ｆ（ｉ，ｊ；ｔ）を、インデックステーブルＩｄｘ（ｉ，ｊ）及び歪総量テーブルＦ（ｉ，ｊ）に設定する作業テーブル設定ステップと、
前記符号量基準値ｋ（ｉ）のインデックスｉにＳ（Ｋ）を、前記ブロックＢ（ｊ）のインデックスｊにＮを初期値として与え、前記ブロックＢ（ｊ）に割り当てる量子化レベルｔ（ｊ）をインデックステーブルＩｄｘ（ｉ，ｊ）とし、前記写像ψ（ｋ（ｉ）−Ｒ（ｔ（ｊ）、ｊ））を計算し、その計算結果を改めてｉの値とし、ｊを順次減算することで、前記量子化レベルｔ（ｊ）のリスト（ｔ（１），…，ｔ（Ｎ））を前記インデックステーブルＩｄｘ（ｉ，ｊ）から逆探索する逆探索ステップと、
を含んでいることを特徴とする符号量制御方法。
【請求項３】
前記量子化レベルｔは、前記各ブロックＢ（ｊ）のビットプレーンの位置を示す値であり、そのビットプレーンの位置に基づいて各ブロックＢ（ｊ）を量子化することを特徴とする請求項２に記載の符号量制御方法。
【請求項４】
符号化対象となる画像を特定の大きさのブロックに分割して、その分割されたブロックの順に可変長符号を生成する画像符号化において、与えられた符号量上限値の範囲内で前記画像を符号化するために、前記各ブロックの符号量を制御する符号量制御装置であって、
前記ブロックを量子化する複数の量子化レベルに基づいて前記ブロックを符号化したときの符号量と、前記量子化レベルに基づいて前記ブロックから廃棄される歪量とを算出し、歪・符号量テーブルとして生成する歪・符号量テーブル生成手段と、
この歪・符号量テーブル生成手段によって生成された前記歪・符号量テーブルを保持する歪・符号量テーブル保持手段と、
前記符号量上限値を最大値とする複数の符号量基準値からなる符号量基準値リストを生成する符号量基準値リスト生成手段と、
この符号量基準値リスト生成手段で生成された符号量基準値リストを保持する符号量基準値リスト保持手段と、
第１番目のブロックから特定ブロックまでの符号量が、前記符号量基準値に最も近い符号量となる前記特定ブロックの量子化レベル及びそのときの歪総量を、前記符号量基準値と前記ブロックとを対応付けたインデックステーブル及び歪総量テーブルとして生成する作業テーブル生成手段と、
この作業テーブル生成手段で生成された前記インデックステーブル及び前記歪総量テーブルを保持する作業テーブル保持手段と、
この作業テーブル保持手段に保持されている前記インデックステーブルから、前記全ブロックの歪総量を最小とする量子化レベルを逆探索して求める逆探索手段と、
を備えていることを特徴とする符号量制御装置。
【請求項５】
符号化対象となる画像を特定の大きさのブロックに分割して、その分割されたブロックの順に可変長符号を生成する画像符号化において、与えられた符号量上限値の範囲内で前記画像を符号化するときの前記各ブロックの符号量を制御するために、コンピュータを、
前記ブロックを量子化する複数の量子化レベルに基づいて前記ブロックを符号化したときの符号量と、前記量子化レベルに基づいて前記ブロックから廃棄される歪量とを算出し、歪・符号量テーブルとして生成して歪・符号量テーブル保持手段に保持する歪・符号量テーブル生成手段、
前記符号量上限値を最大値とする複数の符号量基準値からなる符号量基準値リストを生成して符号量基準値リスト保持手段に保持する符号量基準値リスト生成手段、
第１番目のブロックから特定ブロックまでの符号量が、前記符号量基準値に最も近い符号量となる前記量子化レベル及びそのときの歪総量を、前記符号量基準値と前記ブロックとを対応付けたインデックステーブル及び歪総量テーブルを生成して作業テーブル保持手段に保持する作業テーブル生成手段、
前記作業テーブル保持手段で保持されている前記インデックステーブルから、前記全ブロックの歪総量を最小とする量子化レベルを逆探索して求める逆探索手段、
として機能させることを特徴とする符号量制御プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像符号化技術に関し、より詳細には、符号量を制限された条件の下で、符号化データの切り捨てを行い画像を圧縮符号化する際に、歪量を最も少なくして符号化を行うための符号量制御を行う符号量制御方法、符号量制御装置及び符号量制御プログラムに関する。
【０００２】
【従来の技術】
従来、符号量を制限された条件の下で、符号化データの切り捨てを行い画像を圧縮符号化する符号化方式としては、ウェーブレット（Ｗａｖｅｌｅｔ）変換により符号化を行うＪＰＥＧ２０００（Ｊｏｉｎｔ　Ｐｈｏｔｏｇｒａｐｈｉｃ　Ｅｘｐｅｒｔ　Ｇｒｏｕｐ　２０００）等が挙げられる。
【０００３】
このＪＰＥＧ２０００は、入力画像を、ウェーブレット変換を用いた２次元サブバンド分解によって分解し、その分解された各サブバンドの画素を複数ビット（Ｐビット）で表現し、さらに、各サブバンドを空間的に特定の大きさ（垂直ｍ画素、水平ｎ画素）のブロック（コードブロック）に分割する。そして、各ブロック毎にｍ×ｎビットのＰ個のビットプレーンが生成されることになる。ＪＰＥＧ２０００は、このビットプレーンを１単位として独立してエントロピ符号化を行うことで、圧縮符号化を行うものである。例えば、入力画像がブロック数Ｎに分解されていたとすると、Ｎ×Ｐ個のビットプレーンが生成されることになり、入力画像は、ＪＰＥＧ２０００によってＮ×Ｐ個のエントロピ符号に変換（符号化）されることになる。
【０００４】
ここで、図１１を参照して、ＪＰＥＧ２０００等で入力画像を２次元サブバンド分解によって分解し、各サブバンドをコードブロックに分割する例について説明する。図１１（ａ）は、入力画像を２次元ウェーブレット変換により、２次元空間周波数サブバンドに分解した例を示している。図１１（ｂ）は、サブバンドを特定の大きさのコードブロックに分割した例を示している。図１１（ａ）に示すように、２次元ウェーブレット変換は、入力画像に１次元のウェーブレット変換を水平及び垂直に施すものであり、１回の分解によって入力画像をＬ１Ｌ１、Ｌ１Ｈ１、Ｈ１Ｌ１、Ｈ１Ｈ１に分解する。この分解をさらにＬ１Ｌ１に対して行うことで、Ｌ１Ｌ１は、Ｌ２Ｌ２、Ｌ２Ｈ２、Ｈ２Ｌ２、Ｈ２Ｈ２に分解される。
【０００５】
このように低周波領域を繰り返して分解することで、２次元ウェーブレット変換は、入力画像の階層的なサブバンド分解を実現している。なお、サブバンド分解を行う目的は、符号化された単一の符号化コードストリームに対して、受信側でその一部分を切り出すだけで低解像の画像を再現することを可能にするためである。そして、図１１（ａ）のように分解されたサブバンドを、図１１（ｂ）に示すように特定の大きさのコードブロックに分割する。
【０００６】
このようにコードブロックに分割された入力画像は、ビットプレーン単位で符号化を行うことで、画像全体の符号化が行われる。この画像全体の符号量は、画像毎に異なるため、一定符号量以下に符号量を制限するには、画像全体として歪量が最小限になるようにビットプレーンを選択的に廃棄することが行われている。このビットプレーンを選択的に廃棄して符号化を行うことをビットプレーン符号化という。
【０００７】
ここで、図１２を参照して、ＪＰＥＧ２０００で用いられているビットプレーン（ｂｉｔｐｌａｎｅ）符号化の動作について説明する。図１２は、入力画像をコードブロックに分割し、そのコードブロック毎のビットプレーンを選択的に廃棄して全体の符号量を一定符号量以下に抑えるビットプレーン符号化を模式的に表した図である。
図１２に示すように、入力画像Ｉｍｇは、Ｎ個のコードブロックＢ（Ｂ（ｊ）（ｊ＝１，…，Ｎ））に分割される。なお、個々のコードブロックＢは、ｍ×ｎビットのＰ個のビットプレーンで構成される。
【０００８】
ここでコードブロックＢの中で着目するビット位置をｔ（ｔ＝０，…，Ｐ−１）とし、ｔより下位のビットプレーンを廃棄してコードブロックＢを符号化したときの、符号量Ｒを（１）式で定義する。
【０００９】
Ｒ（ｔ，ｊ）≡：ｒ（ｔ，ｊ）＋…＋ｒ（Ｐ−１，ｊ）　　　…（１）
【００１０】
なお、ｒ（ｔ，ｊ）は、コードブロックＢ（ｊ）（ｊ＝１，…，Ｎ）において、ビットプレーンｔをエントロピ符号化したときの符号量を示す。すなわち、符号量Ｒは、コードブロックＢのビットプレーンｔからビットプレーン（Ｐ−１）までの符号量を示す。この着目するビット位置ｔは、ビットプレーンを廃棄する基準点を指し示すので、以下ＴＰ（Ｔｒｕｎｃａｔｉｏｎ　Ｐｏｉｎｔ）と呼ぶ。
また、（１）式において廃棄された歪量Ｄを（２）式で定義する。
【００１１】
Ｄ（ｔ，ｊ）≡：ｂ（０，ｊ）＊２０＋…＋ｂ（ｔ−１，ｊ）＊２ｔ−１　　　…（２）
【００１２】
なお、ｂ（ｔ，ｊ）は、コードブロックＢ（ｊ）（ｊ＝１，…，Ｎ）において、ビットプレーンｔの非ゼロビットの総数を示す。すなわち、歪量Ｄは、コードブロックＢのビットプレーン０からビットプレーン（ｔ−１）までの歪量の和を示す。この歪量Ｄは、例えば、ｂ（ｔ，ｊ）＊２ｔ以外にも、その自乗値を用いて算出することとしてもよい。
【００１３】
一般に、サブバンド分解によって分解されたサブバンド（係数）は正負の値を取り得るので、最上位のビットプレーン（Ｐ−１）を係数の符号を示すビットプレーン（係数符号プレーン）とし、ビットプレーン０，…，Ｐ−２を係数の絶対値のビット値とする。
【００１４】
例えば、ＴＰがｔ＝０の場合、ビットプレーンを一切廃棄しないので、（２）式において、Ｄ（０，ｊ）＝０となる。また、ＴＰ＝Ｐ−１の場合、ビットプレーンを全て廃棄するので、（１）式において、Ｒ（Ｐ−１，ｊ）＝０となる。
【００１５】
ここで、コードブロックＢのビットプレーンの数を１６（Ｐ＝１６）としたときのＴＰと、符号量Ｒ（ｔ）及び歪量Ｄ（ｔ）との関係を図１３に示す。図１３では、ビットプレーンのＴＰの位置ｔ＝１５を係数符号プレーンとしている。ここでビットプレーンのＴＰをｔとしたとき、ｔより下位のビットプレーン０，…，ｔ−１のｔ個のビットプレーンが廃棄される。また、ｒ（ｓ）（０≦ｓ≦１５）は、ビットプレーンｓをエントロピ符号化したときの符号量を示し、ｄ（ｓ）（０≦ｓ≦１５）は、ビットプレーンｓを廃棄するときの歪量を表している。この歪量は、例えば（ビットプレーンｓの非ゼロビットの総数）＊２ｓ、あるいはその自乗値とする。また、Ｒ（ｔ）は、ビットプレーンのＴＰの位置をｔとしたときのコードブロックＢ（ｊ）（ｊ＝１，…，Ｎ）全体の符号量を示し、Ｄ（ｔ）は、コードブロックＢ（ｊ）全体の歪量を示している。
【００１６】
さらに、図１４にビットプレーンのＴＰの位置（大きさ）と歪量Ｄ（ｔ）及び符号量Ｒ（ｔ）との関係を、あるコードブロックＢについてモデル的に示す。図１４（ａ）はビットプレーンのＴＰの位置（大きさ）と歪量Ｄ（ｔ）との関係を、図１４（ｂ）はビットプレーンのＴＰの位置（大きさ）と符号量Ｒ（ｔ）との関係を示している。図１４に示すように、ＴＰが大きくなる（上位のビットプレーンから多くのビットプレーンが廃棄される）と、歪量Ｄ（ｔ）が増大し、符号量Ｒ（ｔ）が減少する。逆に、ＴＰが小さくなる（下位のビットプレーンで少ないビットプレーンが廃棄される）と、歪量Ｄ（ｔ）が減少し、符号量Ｒ（ｔ）が増大する。
ここで、コードブロックＢ（ｊ）（ｊ＝１，…，Ｎ）について、コードブロックのＴＰの位置を示すｔ（ｊ）のリスト（ＴＰリスト）Ｔを（３）式で定義する。
【００１７】
Ｔ≡（ｔ（１），…，ｔ（Ｎ））　　　…（３）
【００１８】
すなわち、コードブロックＢ（ｊ）のＴＰの位置をビットプレーンｔ（ｊ）とすると、Ｎ個のコードブロック全体の符号量総和Ｒ（Ｔ）は（４）式で、歪量総和Ｄ（Ｔ）は、（５）式で表すことができる。
【００１９】
Ｒ（Ｔ）＝Ｒ（ｔ（１），１）＋…＋Ｒ（ｔ（Ｎ）、Ｎ）　　　…（４）
【００２０】
Ｄ（Ｔ）＝Ｄ（ｔ（１），１）＋…＋Ｄ（ｔ（Ｎ）、Ｎ）　　　…（５）
【００２１】
これにより、ＪＰＥＧ２０００等で符号量を制限された条件の下で、符号化データの切り捨てを行い画像を圧縮符号化するには、以下の（問題Ａ）の解を求めればよいことになる。
【００２２】
（問題Ａ）
目標とする符号量上限値をＫとするとき、Ｒ（Ｔ）＝Ｋなる条件の下で、Ｄ（Ｔ）を最小化するＴＰ（Ｔｒｕｎｃａｔｉｏｎ　Ｐｏｉｎｔ）のリスト（ＴＰリスト）Ｔを決定する（Ｔ、Ｒ（Ｔ）及びＤ（Ｔ）は（３）式、（４）式及び（５）式参照）。
（問題Ａ終）
【００２３】
この（問題Ａ）の解を直接求めることは膨大な数の組合せ演算を要するため、従来、ＪＰＥＧ２０００では、（問題Ａ）の類似的な問題として以下の（問題Ｂ）の解を求め、リスト（ＴＰリスト）Ｔ（（３）式）を決定している。
【００２４】
（問題Ｂ）
目標とする符号量上限値をＫとするとき、Ｒ（Ｔ）＝Ｋなる条件の下で、（６）式で示した評価関数を最小化する組合せＴとλを求める。
【００２５】
Ｌ（Ｔ，λ）≡Ｒ（Ｔ）＋λＤ（Ｔ）　　　…（６）
【００２６】
（Ｔ、Ｒ（Ｔ）及びＤ（Ｔ）は（３）式、（４）式及び（５）式参照）
（問題Ｂ終）
【００２７】
この（問題Ｂ）の解を求めるには、一般的には評価関数Ｌ（Ｔ，λ）が連続関数の場合であれば、ラグランジュ（Ｌａｇｒａｎｇｅ）の未定乗数法を用いて解析的に解くことが可能である。しかし、評価関数Ｌ（Ｔ，λ）は離散関数であるため、予め設定した複数のλの値により、そのλの値を変化させることで、評価関数Ｌ（Ｔ，λ）をより小さくするＴＰのリストＴ（ｔ（１），…，ｔ（Ｎ））を逐次的に決定する等の近似的な手法が用いられている。
【００２８】
このように、従来では、近似的な手法により、ＴＰのリストＴを決定し、各コードブロック毎にｔ（１），…，ｔ（Ｎ）より下位のビットプレーンを廃棄し、各ビットプレーンを符号化することで、符号量を制限された条件の下で、画像の圧縮符号化を行っている。
【００２９】
【発明が解決しようとする課題】
しかし、前記従来の技術では、（問題Ａ）の解は（問題Ｂ）の解となるが、（問題Ｂ）の解は本来求めたい（問題Ａ）の解となる保証がない。すなわち、（問題Ｂ）の解は、近似的な手法によりＴＰ（Ｔｒｕｎｃａｔｉｏｎ　Ｐｏｉｎｔ）のリストＴ（ｔ（１），…，ｔ（Ｎ））を求めるため、評価関数Ｌ（Ｔ，λ）（（６）式参照）を最小にする最適解にならない場合があるという問題がある。
【００３０】
なお、（問題Ａ）の解を直接求める方法としては、全検索により解を求める方法がある。すなわち、Ｎ個のコードブロックＢ（ｊ）（ｊ＝１，…，Ｎ）において、あるＴＰのリストＴに対するＲ（Ｔ）及びＤ（Ｔ）（（４）式及び（５）式参照）を求め、逐次リストＴを変化させることで、Ｒ（Ｔ）＝Ｋ（Ｋは符号量上限値）を満たし、Ｄ（Ｔ）が最小となるリストＴを探索する方法である。
【００３１】
しかし、この方法では、例えば、水平５１２画素、垂直５１２画素で１画素８ビットの画像について、コードブロックを６４に分割して符号化を行う場合、すなわち、画像を水平６４画素、垂直６４画素の６４個のコードブロック（Ｎ＝６４）に分割し、各コードブロックのビットプレーンの数が８（Ｐ＝８）であるとすると、取り得るリストＴの数はＰＮ＝６．２＊１０５７となり、１つのリストＴの検証を１ナノ秒（ｎｓ）で行ったとしても、Ｄ（Ｔ）が最小となるリストＴを探索するには、６．２＊１０４８秒（ｓｅｃ）＝２＊１０４１年を要することになり、現実的な時間では検索することができない。
【００３２】
本発明は、以上のような問題点に鑑みてなされたものであり、符号量を制限された条件の下で、符号化データの切り捨てを行い画像を圧縮符号化する場合に、その画像を特定の大きさのブロック（コードブロック）に分割し、各ブロックのビットプレーンを廃棄するビット位置を決定する際に、歪量が最小となる最適なビット位置を全検索よりも遥かに少ない演算量で求めることを可能にする符号量制御方法、符号量制御装置及び符号量制御プログラムを提供することを目的とする。
【００３３】
【課題を解決するための手段】
本発明は、前記目的を達成するために創案されたものであり、まず、請求項１に記載の符号量制御方法は、符号化対象となる画像を特定の大きさのブロックに分割して、その分割されたブロックの順に可変長符号を生成する画像符号化において、与えられた符号量上限値の範囲内で画像を符号化するために、各ブロックの符号量を制御する符号量制御方法であって、以下のステップを含むものとした。
【００３４】
すなわち、ブロックを量子化する複数の量子化レベルに基づいてブロックを符号化したときの符号量と、そのときの量子化レベルに基づいて前記ブロックから廃棄される歪量とを算出し、歪・符号量テーブルとして生成する歪・符号量テーブル生成ステップと、符号量上限値を最大値とする複数の符号量基準値からなる符号量基準値リストを生成する符号量基準値リスト生成ステップと、第１番目のブロックで符号量基準値に最も近い符号量となる量子化レベル及びそのときの歪量を、符号量基準値とブロックとを対応付けたインデックステーブル及び歪総量テーブルの初期値として設定する作業テーブル初期値設定ステップと、符号量基準値毎に、歪総量テーブルを参照して、第１番目のブロックから特定ブロックまでの歪総量を最小とする量子化レベル及びそのときの歪総量を順次決定して、第２番目以降のブロックにおけるインデックステーブル及び歪総量テーブルの値を設定する作業テーブル設定ステップと、この作業テーブル設定ステップで設定したインデックステーブルから、全ブロックの歪総量を最小とする量子化レベルを逆探索して求める逆探索ステップと、を含むことを特徴とする。
【００３５】
この方法によれば、符号量制御方法は、歪・符号量テーブル生成ステップによって、複数の量子化レベルに基づいてブロックを符号化したときの符号量と、そのときの量子化レベルに基づいてブロックから廃棄される歪量とを算出し、歪・符号量テーブルとして生成する。この量子化レベルは、符号化を行う際の符号量を削減するためのレベルを示すものである。
【００３６】
そして、符号量制御方法は、符号量基準値リスト生成ステップによって、符号量上限値を最大値とする複数の符号量基準値からなる符号量基準値リストを生成する。この符号量基準値は、符号量上限値における最適な量子化レベルを求める問題を解くときに、小規模な問題を解決し、その結果から順次問題の規模を拡大することで求める問題を解くために、符号量上限値を小規模な問題の値になるように細分化したものである。例えば、ＨＤＴＶ（Ｈｉｇｈ　Ｄｅｆｉｎｉｔｉｏｎ　Ｔｅｌｅｖｉｓｉｏｎ）の入力画像を符号化する場合は、符号量基準値の個数を１００〜２００個程度とする。
【００３７】
さらに、符号量制御方法は、作業テーブル初期値設定ステップによって、第１番目のブロックで符号量基準値に最も近い符号量となる前記量子化レベル及びそのときの歪量を、符号量基準値とブロックとを対応付けたインデックステーブル及び歪総量テーブルの初期値として設定し、作業テーブル設定ステップによって、符号量基準値毎に、歪総量テーブルを参照して、第１番目のブロックから特定ブロックまでの歪総量を最小とする量子化レベル及びそのときの歪総量を順次決定して、第２番目以降のブロックにおけるインデックステーブル及び歪総量テーブルの値を設定する。これによって、作業テーブル初期値設定ステップで初期化したインデックステーブル及び歪総量テーブルは、作業テーブル初期値設定ステップによって、帰納的にブロックの順に値が設定される。
【００３８】
そして、符号量制御方法は、逆探索ステップによって、作業テーブル設定ステップで設定したインデックステーブルから、全ブロックの歪総量を最小とする量子化レベルを逆探索して求める。この逆探索ステップでは、すでに作業テーブル設定ステップでインデックステーブルが設定されているため、このインデックステーブルを参照することで、歪総量を最小とする量子化レベルを最終ブロックから順番に検索していき、全ブロックの量子化レベルを取得する。
【００３９】
また、請求項２に記載の符号量制御方法は、符号化対象となる画像を特定の大きさのブロックＢ（ｊ）（ｊ＝１，…，Ｎ）に分割して、そのブロック毎に可変長符号を生成する画像符号化において、与えられた符号量上限値Ｋの範囲内で画像を符号化するために、前記各ブロックの符号量を制御する符号量制御方法であって、以下のステップを含むものとした。
【００４０】
すなわち、ブロックを量子化する複数の量子化レベルｔに基づいてブロックＢ（ｊ）を符号化したときの符号量Ｒ（ｔ，ｊ）と、量子化レベルｔに基づいてブロックＢ（ｊ）から廃棄される歪量Ｄ（ｔ，ｊ）とを算出し、歪・符号量テーブルとして生成する歪・符号量テーブル生成ステップと、符号量上限値Ｋを最大値とするＳ（Ｋ）個の符号量基準値ｋ（ｉ）（ｉ＝１，…，Ｓ（Ｋ）＝Ｋ）からなる符号量基準値リストを生成する符号量基準値リスト生成ステップと、符号量基準値ｋ（ｉ）に最も近い符号量Ｒ（ｔ，１）となる量子化レベルｔ及びそのときの歪量Ｄ（ｔ，１）を、符号量基準値ｋ（ｉ）とブロックＢ（ｊ）とを対応付けたインデックステーブルＩｄｘ（ｉ，ｊ）及び歪総量テーブルＦ（ｉ，ｊ）の初期値として設定する作業テーブル初期値設定ステップと、を含む。
【００４１】
さらに、符号量をｒとし、そのｒに最も近い前記符号量基準値ｋ（ｉ）のインデックスｉを返す写像をψ（ｒ）として、歪総量ｆ（ｉ，ｊ；ｔ）をＤ（ｔ，ｊ）＋Ｆ（ψ（ｋ（ｉ）−Ｒ（ｔ，ｊ）），ｊ−１）と定義したときの、歪総量ｆ（ｉ，ｊ；ｔ）を最小とする量子化レベルｔ及びそのときの歪総量ｆ（ｉ，ｊ；ｔ）を、インデックステーブルＩｄｘ（ｉ，ｊ）及び歪総量テーブルＦ（ｉ，ｊ）に設定する作業テーブル設定ステップと、符号量基準値ｋ（ｉ）のインデックスｉにＳ（Ｋ）を、ブロックＢ（ｊ）のインデックスｊにＮを初期値として与え、ブロックＢ（ｊ）に割り当てる量子化レベルｔ（ｊ）をインデックステーブルＩｄｘ（ｉ，ｊ）とし、写像ψ（ｋ（ｉ）−Ｒ（ｔ（ｊ）、ｊ））を計算し、その計算結果を改めてｉの値とし、ｊを順次減算することで、量子化レベルｔ（ｊ）のリスト（ｔ（１），…，ｔ（Ｎ））を前記インデックステーブルＩｄｘ（ｉ，ｊ）から逆探索する逆探索ステップと、を含むことを特徴とする。
【００４２】
この方法によれば、符号量制御方法は、歪・符号量テーブル生成ステップによって、ブロックを量子化する複数の量子化レベルｔに基づいてブロックＢ（ｊ）を符号化したときの符号量Ｒ（ｔ，ｊ）と、量子化レベルｔに基づいてブロックＢ（ｊ）から廃棄される歪量Ｄ（ｔ，ｊ）とを算出し、歪・符号量テーブルとして生成する。
【００４３】
そして、符号量制御方法は、符号量基準値リスト生成ステップによって、符号量基準値リストを生成する。この符号量基準値リストは、符号量上限値Ｋを最大値とするＳ（Ｋ）個の符号量基準値ｋ（ｉ）（ｉ＝１，…，Ｓ（Ｋ）＝Ｋ）からなる。
【００４４】
さらに、符号量制御方法は、作業テーブル初期値設定ステップによって、符号量基準値ｋ（ｉ）とブロックＢ（ｊ）とを対応付けたインデックステーブルＩｄｘ（ｉ，ｊ）及び歪総量テーブルＦ（ｉ，ｊ）を初期化する。この初期化で使用する初期値は、符号量基準値ｋ（ｉ）に最も近い符号量Ｒ（ｔ，１）となる量子化レベルｔ及びそのときの歪量Ｄ（ｔ，１）とする。そして、作業テーブル設定ステップによって、インデックステーブルＩｄｘ（ｉ，ｊ）及び歪総量テーブルＦ（ｉ，ｊ）に値を設定する。このインデックステーブルＩｄｘ（ｉ，ｊ）及び歪総量テーブルＦ（ｉ，ｊ）に設定する値は、写像ψ（ｒ）を符号量ｒに最も近い符号量基準値ｋ（ｉ）のインデックスｉを返す写像とし、歪総量ｆ（ｉ，ｊ；ｔ）をＤ（ｔ，ｊ）＋Ｆ（ψ（ｋ（ｉ）−Ｒ（ｔ，ｊ）），ｊ−１）と定義したときの、歪総量ｆ（ｉ，ｊ；ｔ）を最小とする量子化レベルｔ及びそのときの歪総量ｆ（ｉ，ｊ；ｔ）とする。なお、写像ψ（ｒ）は、符号量ｒと符号量基準値ｋ（ｉ）との差分を求め、その差分量が最も小さくなるインデックスｉを返すものである。
【００４５】
そして、符号量制御方法は、逆探索ステップによって、量子化レベルｔ（ｊ）のリスト（ｔ（１），…，ｔ（Ｎ））をインデックステーブルＩｄｘ（ｉ，ｊ）から逆探索する。この逆探索は、符号量基準値ｋ（ｉ）のインデックスｉにＳ（Ｋ）を、ブロックＢ（ｊ）のインデックスｊにＮを初期値として与え、ブロックＢ（ｊ）に割り当てる量子化レベルｔ（ｊ）をインデックステーブルＩｄｘ（ｉ，ｊ）とし、写像ψ（ｋ（ｉ）−Ｒ（ｔ（ｊ）、ｊ））を計算し、その計算結果を改めてｉの値とし、ｊを順次減算することで行う。
【００４６】
さらに、請求項３に記載の符号量制御方法は、請求項２に記載の符号量制御方法であって、量子化レベルｔは、各ブロックＢ（ｊ）のビットプレーンの位置を示す値であり、そのビットプレーンの位置に基づいて各ブロックＢ（ｊ）を量子化することを特徴とする。
【００４７】
この方法によれば、符号量制御方法は、量子化レベルｔを各ブロックＢ（ｊ）のビットプレーンの位置を示す値とし、この値に基づいて、ビットプレーンの廃棄を行うことで、各ブロックＢ（ｊ）の量子化を行う。これによって、符号化における符号量を削減する。
【００４８】
また、請求項４に記載の符号量制御装置は、符号化対象となる画像を特定の大きさのブロックに分割して、その分割されたブロックの順に可変長符号を生成する画像符号化において、与えられた符号量上限値の範囲内で画像を符号化するために、各ブロックの符号量を制御する符号量制御装置であって、以下の構成にかかるものとした。
【００４９】
すなわち、ブロックを量子化する複数の量子化レベルに基づいてブロックを符号化したときの符号量と、量子化レベルに基づいてブロックから廃棄される歪量とを算出し、歪・符号量テーブルとして生成する歪・符号量テーブル生成手段と、この歪・符号量テーブル生成手段によって生成された歪・符号量テーブルを保持する歪・符号量テーブル保持手段と、符号量上限値を最大値とする複数の符号量基準値からなる符号量基準値リストを生成する符号量基準値リスト生成手段と、この符号量基準値リスト生成手段で生成された符号量基準値リストを保持する符号量基準値リスト保持手段と、第１番目のブロックから特定ブロックまでの符号量が、符号量基準値に最も近い符号量となる特定ブロックの量子化レベル及びそのときの歪総量を、符号量基準値とブロックとを対応付けたインデックステーブル及び歪総量テーブルとして生成する作業テーブル生成手段と、この作業テーブル生成手段で生成されたインデックステーブル及び歪総量テーブルを保持する作業テーブル保持手段と、この作業テーブル保持手段に保持されているインデックステーブルから、全ブロックの歪総量を最小とする量子化レベルを逆探索して求める逆探索手段と、を備える構成とした。
【００５０】
かかる構成によれば、符号量制御装置は、歪・符号量テーブル生成手段によって、複数の量子化レベルに基づいてブロックを符号化したときの符号量と、量子化レベルに基づいてブロックから廃棄される歪量とを算出し、歪・符号量テーブルとして生成し歪・符号量テーブル保持手段に保持する。この量子化レベルは、符号化を行う際の符号量を削減するためのレベルを示すものである。
【００５１】
そして、符号量制御装置は、符号量基準値リスト生成手段によって、符号量上限値を最大値とする複数の符号量基準値からなる符号量基準値リストを生成し符号量基準値リスト保持手段に保持する。この符号量基準値は、符号量上限値における最適な量子化レベルを求める問題を解くときに、小規模な問題を解決し、その結果から順次問題の規模を拡大することで求める問題を解くために、符号量上限値を小規模な問題の値とするために細分化したものである。例えば、ＨＤＴＶ（Ｈｉｇｈ　Ｄｅｆｉｎｉｔｉｏｎ　Ｔｅｌｅｖｉｓｉｏｎ）の入力画像を符号化する場合は、符号量基準値の個数を１００〜２００個程度とする。
【００５２】
さらに、符号量制御装置は、作業テーブル生成手段によって、第１番目のブロックから特定ブロックまでの符号量が、符号量基準値に最も近い符号量となる特定ブロックの量子化レベル及びそのときの歪総量を、符号量基準値とブロックとを対応付けたインデックステーブル及び歪総量テーブルとして生成し作業テーブル保持手段に保持する。
【００５３】
そして、符号量制御装置は、逆探索手段によって、作業テーブル保持手段に保持されているインデックステーブルから、全ブロックの歪総量を最小とする量子化レベルを逆探索して求める。この逆探索手段では、すでに作業テーブル生成手段によって、インデックステーブルが作業テーブル保持手段に保持されているため、このインデックステーブルを参照することで、歪総量を最小とする量子化レベルを最終ブロックから順番に検索していき、全ブロックの量子化レベルを取得する。
【００５４】
さらに、請求項５に記載の符号量制御プログラムは、符号化対象となる画像を特定の大きさのブロックに分割して、その分割されたブロックの順に可変長符号を生成する画像符号化において、与えられた符号量上限値の範囲内で画像を符号化するときの各ブロックの符号量を制御するために、コンピュータを、以下の手段によって機能させる構成とした。
【００５５】
すなわち、ブロックを量子化する複数の量子化レベルに基づいてブロックを符号化したときの符号量と、量子化レベルに基づいてブロックから廃棄される歪量とを算出し、歪・符号量テーブルとして生成して歪・符号量テーブル保持手段に保持する歪・符号量テーブル生成手段、符号量上限値を最大値とする複数の符号量基準値からなる符号量基準値リストを生成して符号量基準値リスト保持手段に保持する符号量基準値リスト生成手段、第１番目のブロックから特定ブロックまでの符号量が、符号量基準値に最も近い符号量となる前記量子化レベル及びそのときの歪総量を、符号量基準値とブロックとを対応付けたインデックステーブル及び歪総量テーブルを生成して作業テーブル保持手段に保持する作業テーブル生成手段、作業テーブル保持手段で保持されているインデックステーブルから、全ブロックの歪総量を最小とする量子化レベルを逆探索して求める逆探索手段、とした。
【００５６】
かかる構成によれば、符号量制御プログラムは、歪・符号量テーブル生成手段によって、複数の量子化レベルに基づいてブロックを符号化したときの符号量と、量子化レベルに基づいてブロックから廃棄される歪量とを算出し、歪・符号量テーブルとして生成し歪・符号量テーブル保持手段に保持する。この量子化レベルは、符号化を行う際の符号量を削減するためのレベルを示すものである。
【００５７】
そして、符号量制御プログラムは、符号量基準値リスト生成手段によって、符号量上限値を最大値とする複数の符号量基準値からなる符号量基準値リストを生成し符号量基準値リスト保持手段に保持する。この符号量基準値は、符号量上限値における最適な量子化レベルを求める問題を解くときに、小規模な問題を解決し、その結果から順次問題の規模を拡大することで求める問題を解くために、符号量上限値を小規模な問題の値とするために細分化したものである。例えば、ＨＤＴＶ（Ｈｉｇｈ　Ｄｅｆｉｎｉｔｉｏｎ　Ｔｅｌｅｖｉｓｉｏｎ）の入力画像を符号化する場合は、符号量基準値の個数を１００〜２００個程度とする。
【００５８】
さらに、符号量制御プログラムは、作業テーブル生成手段によって、第１番目のブロックから特定ブロックまでの符号量が、符号量基準値に最も近い符号量となる量子化レベル及びそのときの歪総量を、符号量基準値とブロックとを対応付けたインデックステーブル及び歪総量テーブルを生成し作業テーブル保持手段に保持する。
【００５９】
そして、符号量制御プログラムは、逆探索手段によって、作業テーブル保持手段に保持されているインデックステーブルから、全ブロックの歪総量を最小とする量子化レベルを逆探索して求める。この逆探索手段では、すでに作業テーブル生成手段によって、インデックステーブルが作業テーブル保持手段に保持されているため、このインデックステーブルを参照することで、歪総量を最小とする量子化レベルを最終ブロックから順番に検索していき、全ブロックの量子化レベルを取得する。
【００６０】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照して説明する。
図１は、本発明における符号量制御装置を含んだ符号化装置の構成を示したブロック図である。図１に示す符号化装置１は、サブバンド分解手段２と、符号量制御装置３と、エントロピ符号生成手段４とを備え、画像符号化規格ＪＰＥＧ２０００に代表されるウェーブレット変換を用いたサブバンド符号化により、入力画像を、与えられた符号量上限値内で圧縮符号化し、エントロピ符号に変換するものである。
【００６１】
サブバンド分解手段２は、入力画像を、ウェーブレット変換を用いた２次元サブバンド分解によって分解するものである。図１１（ａ）に示すように、このサブバンド分解手段２は、入力画像に１次元のウェーブレット変換を水平及び垂直に施すものであり、１回の分解によって入力画像をＬ１Ｌ１、Ｌ１Ｈ１、Ｈ１Ｌ１、Ｈ１Ｈ１に分解する。この分解をさらにＬ１Ｌ１に対して行うことで、Ｌ１Ｌ１は、Ｌ２Ｌ２、Ｌ２Ｈ２、Ｈ２Ｌ２、Ｈ２Ｈ２に分解される。このように、サブバンド分解手段２は、入力画像の低周波領域を繰り返して分解することで、入力画像を階層的なサブバンドに分解するものである。
【００６２】
符号量制御装置３は、サブバンド分解手段２で分解されたサブバンドを特定の大きさのブロック（コードブロック）に分割し、そのブロック毎に量子化のレベル（量子化レベル）を変えて量子化を行いデータの切り捨てを行う際に、符号化歪を最小にする各ブロック毎の量子化レベルを選択するものである。ここでは、量子化レベルとして、図１２で説明したビットプレーン符号化で使用するビットプレーンの位置を示すものとする。この符号量制御装置３の構成については後記する。
【００６３】
エントロピ符号生成手段４は、符号量制御装置３で各ブロックの量子化レベルによって削減されたデータを、適応的算術符号等のエントロピ符号化を行うものである。このエントロピ符号生成手段４によって、符号化データであるエントロピ符号が生成される。
【００６４】
（符号量制御装置の構成）
次に、本発明における符号量制御装置の構成について説明する。
図１に示すように、符号量制御装置３は、コードブロック分割手段１０と、歪・符号量テーブル生成手段１１と、符号量基準値リスト生成手段１２と、作業テーブル生成手段１３と、逆探索手段１４と、ビット切り捨て手段１５と、を備える構成とした。
【００６５】
コードブロック分割手段１０は、サブバンド分解手段２によってサブバンドに分解された入力画像を特定の大きさのブロック（コードブロック）に分割するものである（図１１（ｂ）参照）。ここでは、コードブロック分割手段１０は、各サブバンドの画素をＰビットで表現し、さらに各サブバンドを空間的に垂直ｍ画素、水平ｎ画素のＮ個のコードブロックＢ（ｊ）（ｊ＝１，…，Ｎ）に分割するものとする。これにより、各コードブロックはｍ×ｎビットのＰ個のビットプレーンとして生成される。このコードブロックは、歪・符号量テーブル生成手段１１と、ビット切り捨て手段１５とに出力される。
【００６６】
歪・符号量テーブル生成手段１１は、コードブロック分割手段１０で分割されたコードブロックの量子化レベルを変えてエントロピ符号化を行ったときの符号量と、その符号化によって廃棄される歪量とを、各コードブロックと量子化レベルを対応付けた歪・符号量テーブルを生成するものである。なお、このエントロピ符号化は、エントロピ符号生成手段４と同一の符号化である。ここで、量子化レベルは、図１２で説明したビットプレーン符号化におけるビットプレーンを廃棄する基準となる位置（ＴＰ：Ｔｒｕｎｃａｔｉｏｎ　Ｐｏｉｎｔ）を用いることとする。
【００６７】
この歪・符号量テーブル生成手段１１では、歪・符号量テーブルとして、コードブロックＢ（ｊ）のＴＰをｔ（ｔ＝０，…，Ｐ−１）とし、ｔより下位のビットプレーンを廃棄してコードブロックを符号化したときの符号量を（１）式で定義して、符号量テーブル（Ｒ（ｔ，ｊ））とし、（１）式において廃棄された歪量を、歪量テーブル（Ｄ（ｔ，ｊ））として生成する。すなわち、図２に示すように、歪量テーブル（図２（ａ）参照）及び符号量テーブル（図２（ｂ）参照）は、Ｐ個のビットプレーンの中でＴＰの位置を指し示すインデックスｔと、コードブロックＢ（ｊ）を指し示すインデックスｊとを引数とする２次元の配列となる。この歪量テーブル及び符号量テーブルが請求項に記載の歪・符号量テーブル保持手段に該当し、メモリ等の記憶手段に保持される。
【００６８】
符号量基準値リスト生成手段１２は、与えられた符号量上限値を最大値とする数列を符号量基準値のリスト（符号量基準値リストＫｓｅｔ）として生成するものである。この符号量基準値リスト生成手段１２は、与えられた符号量上限値をＫとしたとき、Ｋを最大値とするＳ（Ｋ）通りの符号量基準値リストＫｓｅｔを、図３に示すようにｋ（１），…，ｋ（Ｓ（Ｋ））の１次元配列データとして生成する。例えば、ＨＤＴＶ（Ｈｉｇｈ　Ｄｅｆｉｎｉｔｉｏｎ　Ｔｅｌｅｖｉｓｉｏｎ）の入力画像を符号化する場合は、符号量基準値リストＫｓｅｔの数列の個数を１００〜２００個程度とする。この符号量基準値リストＫｓｅｔが請求項に記載の符号量基準値リスト保持手段に該当し、メモリ等の記憶手段に保持される。
【００６９】
作業テーブル生成手段１３は、歪・符号量テーブル生成手段１１で生成された歪量テーブルＤ、符号量テーブルＲ及び符号量基準値リスト生成手段１２で生成された符号量基準値リストＫｓｅｔを参照して、符号量基準値ｋ（ｉ）（ｉ＝０，…，Ｓ（Ｋ））毎に、ｊ個のコードブロックＢ（１），…，Ｂ（ｊ）の歪総量が最小となる量子化レベルのリストを設定したときの歪総量を歪総量テーブルＦ（ｉ，ｊ）とし、そのときの量子化レベル（ＴＰ）を指し示すインデックスをインデックステーブルＩｄｘ（ｉ，ｊ）として生成するものである。この歪総量テーブルＦ及びインデックステーブルＩｄｘの生成手順については後記する。この歪総量テーブルＦ及びインデックステーブルＩｄｘが請求項に記載の作業テーブル保持手段に該当し、メモリ等の記憶手段に保持される。
【００７０】
逆探索手段１４は、歪・符号量テーブル生成手段１１で生成された符号量テーブルＲ、符号量基準値リスト生成手段１２で生成された符号量基準値リストＫｓｅｔ及び作業テーブル生成手段１３で生成されたインデックステーブルＩｄｘを参照して、Ｎ個のコードブロックＢ（ｊ）（ｊ＝１，…，Ｎ）毎のＴＰの位置（ｔ（１），…，ｔ（Ｎ））をＴＰリストＴとして決定するものである。
【００７１】
この逆探索手段１４は、作業テーブル生成手段１３で生成されたインデックステーブルＩｄｘですでに求められているＩｄｘ（Ｓ（Ｋ），Ｎ）の値、すなわち、コードブロック数をＮ個としたときの、コードブロックＢ（Ｎ）のＴＰの位置（ｔ（Ｎ））を初期値として、インデックステーブルＩｄｘから順次ｔ（Ｎ−１），…，ｔ（１）を逆探索して求めていくものである。この逆探索手順については後記する。
【００７２】
ビット切り捨て手段１５は、コードブロック分割手段１０で分割されたコードブロックＢ（ｊ）（ｊ＝１，…，Ｎ）から、逆探索手段１４で求められたＴＰリストＴ（ｔ（１），…，ｔ（Ｎ））に基づいて、各コードブロックＢ（ｊ）からＴＰリストＴのＴＰの位置より下位のビットプレーンを廃棄し、残ったビットプレーンをエントロピ符号生成手段４へ出力するものである。
これにより、エントロピ符号生成手段４で符号化されたエントロピ符号は、入力画像を、与えられた符号量上限値内で歪量を最小にして圧縮符号化された符号化データとなる。
【００７３】
以上、一実施形態に基づいて、符号量制御装置３の構成について説明したが、符号量制御装置３は、コンピュータにおいて各手段を各機能プログラムとして実現することも可能であり、各機能プログラムを結合して符号量制御プログラムとして動作させることも可能である。
【００７４】
（符号量制御装置の動作）
次に、符号量制御装置３の動作について説明する。
［動作概念］
まず、符号量制御装置３で行う符号量制御動作の概念について説明する。この符号量制御装置３は、Ｎ個のコードブロックＢ（ｊ）（ｊ＝１，…，Ｎ）で前記した（問題Ａ）の解を求めるにあたり、（問題Ａ）を図４に示すようにＮ通りの部分的な対象に分解し、その部分的な対象における問題を順次解くことにより、最終的に（問題Ａ）の解を得るものである。
【００７５】
図４に示したＮ通りの対象（１〜Ｎ）について、符号量基準値リスト生成手段１２で生成する符号量基準値ｋ（ｉ）（ｉ＝１，…，Ｓ（Ｋ））を符号量上限値とする、対象ｊ（ｊ＝１，…，Ｎ）の符号量の割り当てを最適化する問題を、Ａ（ｉ，ｊ）で表し、このＳ（Ｋ）×Ｎ通りの問題を以下の（サブ問題Ａ）として定式化する。
【００７６】
（サブ問題Ａ）
ｊ個のコードブロックＢ（１），Ｂ（２），…，Ｂ（ｊ）について、目標とする符号量上限値をｋ（ｉ）とするとき、Ｒ（Ｔ（ｊ））＝ｋ（ｉ）なる条件の下で、Ｄ（Ｔ（ｊ））を最小化するＴＰ（Ｔｒｕｎｃａｔｉｏｎ　Ｐｏｉｎｔ）のリスト（ＴＰリスト）Ｔ（ｊ）を決定する（Ｒ及びＤは、（４）式及び（５）式参照）。
ただし、Ｔ（ｊ）＝（（ｔ（１），…，ｔ（ｊ）））で、ｊ個のコードブロックＢ（１），Ｂ（２），…，Ｂ（ｊ）にそれぞれ割り当てられるＴＰのリストＴ（ｊ）とする。
（サブ問題Ａ終）
【００７７】
このように定式化されたＳ（Ｋ）×Ｎ個のサブ問題の中で（サブ問題Ａ）Ａ（Ｓ（Ｋ），Ｎ）が本来求めたい（問題Ａ）に該当することになる。
この符号量制御装置３では、最も小規模な（サブ問題Ａ）Ａ（１，１）から、ｉ及びｊを順次拡大しながら、すでに解かれた小規模の（サブ問題Ａ）の解を参照することで、逐次的に問題を解決していき、最終的に求めたい（サブ問題Ａ）Ａ（Ｓ（Ｋ），Ｎ）、すなわち（問題Ａ）を解くものである。
【００７８】
次に、図５を参照（適宜図１参照）して、（サブ問題Ａ）を順次解いていく符号量制御装置３の動作について説明する。図５は、符号量制御装置３の概略動作を示すフローチャートである。なお、コードブロック分割手段１０及びビット切り捨て手段１５の動作については、従来と同様の動作であるのでここでは説明を省略する。
【００７９】
［ステップＳ１：歪・符号量テーブル生成］
まず、符号量制御装置３は、ブロック分割手段１０でｍ×ｎビットのＰ個のビットプレーンとして分割された各コードブロックＢ（ｊ）（ｊ＝１，…，Ｎ）を、歪・符号量テーブル生成手段１１によって、量子化レベル（ＴＰ）の値（ｔ＝０，…，Ｐ−１）毎にエントロピ符号化を行った符号量を符号量テーブルＲ（ｔ，ｊ）として生成し、その符号化によって廃棄される歪量を歪量テーブルＤ（ｔ，ｊ）として生成する。
【００８０】
［ステップＳ２：符号量基準値リスト生成］
また、符号量制御装置３は、符号量基準値リスト生成手段１２によって、与えられた符号量上限値をＫとしたとき、Ｋを最大値とするＳ（Ｋ）通りの符号量基準値のリスト（符号量基準値リストＫｓｅｔ）を、Ｋｓｅｔ≡（ｋ（１），…，ｋ（Ｓ（Ｋ））＝Ｋ）として生成する。
【００８１】
なお、この符号量基準値リストＫｓｅｔは、ｋ（ｉ）＜ｋ（ｉ＋１）かつｋ（Ｓ（Ｋ））＝Ｋであればよい。例えば、正数εをＫ／（Ｓ（Ｋ）−１）とし、（７）式に示すようにｋ（ｉ）を直線的に増加する数列とする。
【００８２】
ｋ（ｉ）＝（ｉ−１）＊ε　　　…（７）
【００８３】
また、符号量基準値リストＫｓｅｔは、ある符号量基準値付近を細かく分割する非線型に増加する数列としてもよい。
【００８４】
［ステップＳ３：作業テーブル初期値設定］
そして、符号量制御装置３は、作業テーブル生成手段１３によって、（サブ問題Ａ）を順次、帰納的に解くための作業領域となるＳ（Ｋ）行Ｎ列のインデックステーブルＩｄｘ及び歪総量テーブルＦに初期値を設定する。
【００８５】
ここで、Ｉｄｘ（ｉ，ｊ）及びＦ（ｉ，ｊ）（ｉ＝１，…，Ｓ（Ｋ），ｊ＝１，…，Ｎ）を、インデックステーブルＩｄｘ及び歪総量テーブルＦのｉ行ｊ列の要素とすると、Ｆ（ｉ，ｊ）は、符号量基準値ｋ（ｉ）でｊ個のコードブロックＢ（１），…，Ｂ（ｊ）について最適なＴＰのリストＴ（ｊ）を設定したとき、すなわち、（サブ問題Ａ）Ａ（ｉ，ｊ）を解いたときの歪量総和Ｄ（Ｔ（ｊ））を格納する場所となる。また、Ｉｄｘ（ｉ，ｊ）は、（サブ問題Ａ）Ａ（ｉ，ｊ）を解いたときのコードブロックＢ（ｊ）のＴＰを示すｔ（ｊ）の値を格納する場所となる。
【００８６】
このステップＳ３では、コードブロックＢ（１）に着目して、最も規模の小さい（サブ問題Ａ）Ａ（ｉ，１）（ｉ＝１，…，Ｓ（Ｋ））を解き、インデックステーブルＩｄｘ及び歪総量テーブルＦの第１列の要素を決定する。この（サブ問題Ａ）Ａ（ｉ，１）（ｉ＝１，…，Ｓ（Ｋ））は、ある符号量基準値ｋ（ｉ）における１個のブロックＢ（１）に符号量を割り当てる問題であって、求めるべきＴＰのリストであるＴ（１）には１個の要素ｔ（１）しか存在しない。従って、（サブ問題Ａ）Ａ（ｉ，１）の解、すなわち、符号量基準値ｋ（ｉ）の符号量制約の下でコードブロックＢ（１）に対する最適なＴＰであるｔ（１）は、符号量総和Ｒ（Ｔ）＝ｋ（ｉ）、すなわち、Ｒ（ｔ（１），１）＝ｋ（ｉ）によって一意に決定されることになる。この場合、必ずしもＲ（ｔ（１），１）＝ｋ（ｉ）が正確に成立するｔ（１）が存在するとは限らないため、ここでは、ｋ（ｉ）に「最も近い」符号量Ｒ（ｔ，１）となるｔ、すなわちｔ（１）を決定し、このｔ（１）の値をインデックステーブルＩｄｘ（ｉ，１）に格納する。
【００８７】
そして、歪総量テーブルＦのＦ（ｉ，１）には、（サブ問題Ａ）Ａ（ｉ，１）での歪量、すなわち、インデックステーブルＩｄｘのＩｄｘ（ｉ，１）におけるコードブロックＢ（１）に発生する符号化歪量を、歪量テーブルＤから歪量Ｄ（Ｉｄｘ（ｉ，１）、１）の値を読み込んで格納する。
【００８８】
ここで「最も近い」について定義しておく。例えば符号量をｒとし、符号量基準値ｋ（ｉ）（ｉ＝１，…，Ｓ（Ｋ））としたとき、近さの尺度を｜ｋ（ｉ）−ｒ｜（ｋ（ｉ）とｒとの差分の絶対値）とすると、ｋ（ｉ）は（７）式に示したようにｉに関して単調増加（ｋ（ｉ−１）＜ｋ（ｉ））するものであり、ｋ（ｉ−１）＜ｒ＜ｋ（ｉ）であって、ｒがｋ（ｉ−１）とｋ（ｉ）とのちょうど中間に位置する場合、すなわちｒ−ｋ（ｉ−１）＝ｋ（ｉ）−ｒであるとすると、ｒに「最も近い」値はｋ（ｉ−１）とｋ（ｉ）との２個になり、ある符号量ｒに「最も近い」符号量基準値が特定できないことになる。
【００８９】
そこで、ここではｋ（ｉ）≦ｒで、かつ、ｉ´≠ｉである全てのｉ´について｜ｒ−ｋ（ｉ）｜≦｜ｒ−ｋ（ｉ´）｜とすることで、ある符号量ｒに「最も近い」符号量基準値ｋ（ｉ）のｉを特定するものとする。なお、このｉを特定する方法はこれ以外にも種々あり、例えば、ｋ（ｉ）≧ｒで、かつ、ｉ´≠ｉである全てのｉ´について｜ｒ−ｋ（ｉ）｜≦｜ｒ−ｋ（ｉ´）｜とすることも可能である。
【００９０】
以上の作業テーブル初期値設定（ステップＳ３）の動作を図６のフローチャートに示す。図６に示すように、作業テーブル初期値設定（ステップＳ３）は、まず変数ｉを１に初期化する（ステップＳ３０）。そして、符号量基準値ｋ（ｉ）に「最も近い」符号量Ｒ（ｔ，１）となるコードブロックＢ（１）に対するＴＰの値をｔとする（ステップＳ３１）。なお、このステップＳ３１において、ａｒｇｕｍｅｎｔ｛条件｜パラメータリスト｝は「パラメータリスト」から「条件」を満たすパラメータを取り出す操作を表すものとする。また、「条件」における「≒」記号は「最も近い」を表す記号とする。
【００９１】
そして、このステップＳ３１で取得したＴＰの値ｔを、インデックステーブルＩｄｘ（ｉ，１）に格納し（ステップＳ３２）、歪量Ｄ（ｔ、１）すなわちＤ（Ｉｄｘ（ｉ，１）、１）を読み込んで、歪総量テーブルＦのＦ（ｉ，１）に格納する（ステップＳ３３）。そして、変数ｉが符号量基準値の数（Ｓ（Ｋ））かどうかを判定し（ステップＳ３４）、等しい場合（Ｙｅｓ）は処理を終了し、異なる場合（Ｎｏ）は変数ｉの値を１加算して（ステップＳ３５）、ステップＳ３１へ戻って処理を続ける。
【００９２】
以上の動作によって、符号量基準値ｋ（ｉ）（ｉ＝１，…，Ｓ（Ｋ））において、インデックステーブルＩｄｘのＩｄｘ（ｉ，１）には、コードブロックＢ（１）に対して、ｋ（ｉ）に「最も近い」符号量を与えるＴＰの値が格納される。また、歪総量テーブルＦのＦ（ｉ，１）には、コードブロックＢ（１）に対して、ｋ（ｉ）に「最も近い」符号量を与えるＴＰにおけるコードブロックＢ（１）の歪量が格納される。
これにより、インデックステーブルＩｄｘ及び歪総量テーブルＦにおける第１列目のＳ（Ｋ）個の値が埋められ、（サブ問題Ａ）Ａ（ｉ，１）（ｉ＝１，…，Ｓ（Ｋ））が解かれたことになる。
【００９３】
［ステップＳ４：作業テーブル設定］
次に符号量制御装置３は、作業テーブル生成手段１３によって、ステップＳ３で解かれた（サブ問題Ａ）Ａ（ｉ，１）の結果を初期値として、コードブロックＢ（ｉ），…，Ｂ（ｊ−１）に関する（サブ問題Ａ）Ａ（ｉ，ｊ−１）を参照して、（サブ問題Ａ）Ａ（ｉ，ｊ）を解いていく。すなわち、インデックステーブルＩｄｘ及び歪総量テーブルＦですでに確定している第（ｊ−１）列のＳ（Ｋ）個の値を参照して、第ｊ列の値を帰納的に決定していく。
【００９４】
ここで作業テーブル設定（ステップＳ４）の動作を図７のフローチャートを参照して説明する。
図７に示すように、作業テーブル設定（ステップＳ４）は、まず、コードブロックＢ（ｊ）のインデックスである変数ｊを２に初期化し（ステップＳ４０）、符号量基準値ｋ（ｉ）のインデックスである変数ｉを１に初期化する（ステップＳ４１）。ここで変数ｊを２に初期化するのは、作業テーブル初期値設定（ステップＳ３）において、コードブロックＢ（１）におけるインデックステーブルＩｄｘは、すでに設定されているためである。
【００９５】
そして、（サブ問題Ａ）Ａ（ｉ，ｊ）において、ＴＰのリストであるＴ（ｊ）の最後の要素ｔ（ｊ）をｔとしたとき（コードブロックＢ（ｊ）のＴＰをｔとしたとき）のコードブロックＢ（１），…，Ｂ（ｊ）の歪総量を算出する（ステップＳ４２）。
ここでは、まず、符号量ｒから符号量基準値リストＫｓｅｔの要素のインデックスへの写像ψを（８）式で定義しておく。
【００９６】
2004056605.tif 000003
【００９７】
この（８）式において、ａｒｇｕｍｅｎｔ｛条件｜パラメータリスト｝は「パラメータリスト」から「条件」を満たすパラメータを取り出す操作を表すものとし、「条件」における「≒」記号は「最も近い」を表す記号とする。
そして、このステップＳ４２のコードブロックＢ（１），…，Ｂ（ｊ）の歪総量ｆ（ｉ，ｊ；ｔ）の算出には、（９）式を用いる。
【００９８】
2004056605.tif 000004
【００９９】
この（９）式において、（ｋ（ｉ）−Ｒ（ｔ，ｊ））は、（サブ問題Ａ）Ａ（ｉ，ｊ）に割り当てられた符号量基準値ｋ（ｉ）から、コードブロックＢ（ｊ）の符号量Ｒ（ｔ，ｊ）を引いた量で、ここでは残余符号量と呼ぶこととする。また、ψ（ｋ（ｉ）−Ｒ（ｔ，ｊ））は、（８）式に示したように、残余符号量（ｋ（ｉ）−Ｒ（ｔ，ｊ））に「最も近い」符号量基準値リストＫｓｅｔの要素のインデックスを表している。従って、歪総量テーブルＦのＦ（ψ（ｋ（ｉ）−Ｒ（ｔ，ｊ）），ｊ−１）は、（サブ問題Ａ）Ａ（ψ（ｋ（ｉ）−Ｒ（ｔ，ｊ），ｊ−１）を解いたときの歪総量となる。
【０１００】
そして、（９）式は、この（サブ問題Ａ）Ａ（ψ（ｋ（ｉ）−Ｒ（ｔ，ｊ），ｊ−１）を解いたときの歪総量に、コードブロックＢ（ｊ）の歪量Ｄ（ｔ，ｊ）を加算したもので、（サブ問題Ａ）Ａ（ｉ，ｊ）において、ＴＰのリストであるＴ（ｊ）の最後の要素ｔ（ｊ）をｔとしたときのコードブロックＢ（１），…，Ｂ（ｊ）の歪総量となる。
このように、（９）式で算出した歪総量が最小となるＴＰの値ｔを（１０）式を用いて取得する（ステップＳ４３）。
【０１０１】
2004056605.tif 000005
【０１０２】
この（１０）式は、歪総量ｆ（ｉ，ｊ；ｔ）がパラメータｔによって変化するときに最小値（ｍｉｎｉｍｉｚｅ）となるｔの値を取り出すことを表している。ここで、歪総量ｆ（ｉ，ｊ；ｔ）の要素は最大Ｐ（０，…，Ｐ−１）個あり、その中の最小値が、（サブ問題Ａ）Ａ（ｉ，ｊ）を解いたときの歪総量である。従って、その歪総量が最小値となるときのＴＰの値ｔを取得すれば、このｔの値が、（サブ問題Ａ）Ａ（ｉ，ｊ）の解であるＴＰのリストＴ（ｊ）における最後の要素ｔ（ｊ）となる。
【０１０３】
そして、ステップＳ４３で取得したＴＰの値ｔを、インデックステーブルＩｄｘ（ｉ，ｊ）に格納し（ステップＳ４４）、そのときのｔの値における歪総量ｆ（ｉ，ｊ；ｔ）を、歪総量テーブルＦのＦ（ｉ，ｊ）に格納する（ステップＳ４５）。そして、変数ｉが符号量基準値の数（Ｓ（Ｋ））かどうかを判定し（ステップＳ４６）、異なる場合（Ｎｏ）は変数ｉの値を１加算して（ステップＳ４７）、ステップＳ４２へ戻って処理を続ける。
【０１０４】
そして、変数ｉが符号量基準値の数（Ｓ（Ｋ））と等しい場合（Ｙｅｓ）は、変数ｊがコードブロックの数（Ｎ）かどうかを判定し（ステップＳ４８）、等しい場合（Ｙｅｓ）は処理を終了し、異なる場合（Ｎｏ）は変数ｊの値を１加算して（ステップＳ４９）、ステップＳ４１へ戻って処理を続ける。
【０１０５】
以上の動作によって、インデックステーブルＩｄｘ及び歪総量テーブルＦにおける第２列目以降のコードブロックＢ（ｊ）（ｊ＝２，…，Ｎ）の値がＳ（Ｋ）個づつ順に埋められ、（サブ問題Ａ）Ａ（ｉ，ｊ）を解いたときの、インデックステーブルＩｄｘの値であるＩｄｘ（ｉ，ｊ）と、歪総量テーブルＦの値であるＦ（ｉ，ｊ）が決定される。このインデックステーブルＩｄｘ及び歪総量テーブルＦの要素が逐次的に決定される順序を図９に示す。図９（ａ）には、インデックステーブルＩｄｘの決定順序を、図９（ｂ）には、歪総量テーブルＦの決定順序を模式的に示している。インデックステーブルＩｄｘ及び歪総量テーブルＦ共に、第１列目（コードブロックＢ（１））の符号量基準値ｋ（ｉ）のインデックスｉ＝１からｉ＝Ｓ（Ｋ）までが初期値として設定された後に、第２列目のコードブロックＢ（２）から順番にコードブロックＢ（Ｎ）までの値が決定される。
【０１０６】
このように、帰納的に（サブ問題Ａ）を解いていくことで、（サブ問題Ａ）Ａ（Ｓ（Ｋ），Ｎ）における歪総量テーブルＦの値であるＦ（Ｓ（Ｋ），Ｎ）と、インデックステーブルＩｄｘの値であるＩｄｘ（Ｓ（Ｋ），Ｎ）とを求めることができる。
【０１０７】
［ステップＳ５：逆探索］
次に符号量制御装置３は、作業テーブル生成手段１３によって、ステップＳ４で設定されたインデックステーブルＩｄｘのＳ（Ｋ）行Ｎ列のテーブルであるＩｄｘ（ｉ，ｊ）（ｉ＝１，…，Ｓ（Ｋ），ｊ＝１，…，Ｎ）を用いて、Ｉｄｘ（Ｓ（Ｋ），Ｎ）、すなわち、コードブロックの数がＮ個の場合のコードブロックＢ（Ｎ）におけるＴＰの値ｔ（Ｎ）を初期値として、逆探索によりｔ（Ｎ−１），…，ｔ（１）を順次決定する。
【０１０８】
ここで、逆探索（ステップＳ５）の動作を図８のフローチャートを参照して説明する。
図８に示すように、逆探索（ステップＳ５）は、まず、符号量基準値ｋ（ｉ）のインデックスである変数ｉを符号量基準値の数（Ｓ（Ｋ））に初期化し（ステップＳ５０）、コードブロックＢ（ｊ）のインデックスである変数ｊをコードブロックの数（Ｎ）に初期化する（ステップＳ５１）。
【０１０９】
そして、コードブロックＢ（ｊ）に割り当てるＴＰの値であるＩｄｘ（ｉ，ｊ）をインデックステーブルＩｄｘから取得し、ｔ（ｊ）に設定する（ステップＳ５２）。このステップＳ５２は、あるＩｄｘ（ｉ，ｊ）が定まっているとすると、符号量基準値ｋ（ｉ）をコードブロックＢ（１），…，Ｂ（ｊ）に割り当てる（サブ問題Ａ）Ａ（ｉ，ｊ）はすでに解かれており、Ｉｄｘ（ｉ，ｊ）は、最後のコードブロックＢ（ｊ）に割り当てるＴＰの値であるｔ（ｊ）となる。
【０１１０】
この結果、符号量基準値ｋ（ｉ）から、コードブロックＢ（ｊ）に割り当てる符号量Ｒ（ｔ，ｊ）を引いた量、すなわち、残余符号量ｋ（ｉ）−Ｒ（ｔ（ｊ），ｊ）がコードブロックＢ（１），…，Ｂ（ｊ−１）に割り当てるべき符号量となる。そこで、このコードブロックＢ（ｊ）の残余符号量ｋ（ｉ）−Ｒ（ｔ（ｊ），ｊ）に「最も近い」符号量基準値のインデックスをψ（ｋ（ｉ）−Ｒ（ｔ（ｊ），ｊ））で算出し、新たに変数ｉに代入する（ステップＳ５３）。
【０１１１】
そして、コードブロックＢ（ｊ）のインデックスである変数ｊから１減算し（ステップＳ５４）、変数ｊが０になったかどうかを判定する（ステップＳ５５）。ここで変数ｊが０になった場合（Ｙｅｓ）は、処理を終了し、変数ｊが０でない場合（Ｎｏ）は、ステップＳ５２へ戻って処理を続ける。
【０１１２】
以上の動作を図１０を参照してさらに説明する。図１０は、逆探索手段１４における逆探索動作を模式的に表した図である。インデックステーブルＩｄｘの値であるＩｄｘ（Ｓ（Ｋ），Ｎ）、すなわちコードブロックＢ（Ｎ）のＴＰの値（ｔ（Ｎ））は、すでにステップＳ４によって求められている（Ａ１に書き込まれている）。次に、符号量上限値Ｋから、ｔ（Ｎ）でコードブロックＢ（Ｎ）を符号化したときの符号量（Ｒ（ｔ（Ｎ）、Ｎ））を引いた残余符号量（Ｋ−Ｒ（ｔ（Ｎ）、Ｎ））に「最も近い」符号量基準値リストＫｓｅｔの要素のインデックスをｉとする。すなわち、Ｋ−Ｒ（ｔ（Ｎ）、Ｎ）≒ｋ（ｉ）となるインデックスｉを求める。そして、インデックステーブルＩｄｘで、このインデックスｉに該当する（Ａ２に書き込まれている）コードブロックＢ（Ｎ−１）の値（Ｉｄｘ（ｉ，Ｎ−１））をコードブロックＢ（Ｎ−１）のＴＰの値（ｔ（Ｎ−１））とする。
【０１１３】
さらに、符号量基準値ｋ（ｉ）から、ｔ（Ｎ−１）でコードブロックＢ（Ｎ−１）を符号化したときの符号量（Ｒ（ｔ（Ｎ−１）、Ｎ−１））を引いた残余符号量（Ｋ−Ｒ（ｔ（Ｎ−１）、Ｎ−１））に「最も近い」符号量基準値リストＫｓｅｔの要素のインデックスをｉ´とする。すなわち、Ｋ−Ｒ（ｔ（Ｎ−１）、Ｎ−１）≒ｋ（ｉ´）となるインデックスｉ´を求める。そして、インデックステーブルＩｄｘで、このインデックスｉ´に該当する（Ａ３に書き込まれている）コードブロックＢ（Ｎ−２）の値（Ｉｄｘ（ｉ´，Ｎ−２））をコードブロックＢ（Ｎ−２）のＴＰの値（ｔ（Ｎ−２））とする。このように、順次ＴＰの値をｔ（１）まで逆探索する。
【０１１４】
以上の動作によって、Ｎ個のコードブロックＢ（ｊ）のＴＰのリストＴ＝（ｔ（１），…，ｔ（Ｎ））は、すでに求まっているインデックステーブルＩｄｘを参照（逆探索）することで、ｔ（Ｎ），…，ｔ（１）の順番に決定される。
以上のステップＳ１〜Ｓ５の動作により、与えられた符号量上限値Ｋの下で歪量総和Ｄ（Ｔ）（（５）式参照）を最小化するコードブロックＢ（ｊ）（ｊ＝１，…，Ｎ）についてのＴＰ（Ｔｒｕｎｃａｔｉｏｎ　Ｐｏｉｎｔ）のリスト（ＴＰリスト）Ｔを逐次的に決定することができる。
【０１１５】
このステップＳ１〜Ｓ５の動作で明らかなように、本手法によれば（問題Ａ）は、Ｓ（Ｋ）＊Ｎ＊Ｐのオーダの演算で解くことが可能である。例えば、符号量基準値の数を１００（Ｓ（Ｋ）＝１００）、コードブロックの数を６４（Ｎ＝６４）、各コードブロックのビットプレーンの数を１６（Ｐ＝１６）とすると、５１２００回の演算ステップで動作させることが可能で、例えば、１ステップあたり１００ナノ秒（ｎｓ）の演算時間としても、１／３０秒のフレームレートで本手順を動作させることができる。これにより、ソフトウェアによる符号量制御を実現することができる。
【０１１６】
なお、本手法において、量子化レベルをビットプレーンの位置を示すＴＰ（Ｔｒｕｎｃａｔｉｏｎ　Ｐｏｉｎｔ）として説明したが、この量子化レベルは、サブバンド符号化で使用されるビットプレーン符号化に限定されるものではなく、ブロック単位で符号量と、歪量とをパラメータ制御するような符号化方式においても、そのパラメータを量子化レベルとみなすことで実現することが可能である。例えば、ＤＣＴ（Ｄｉｓｃｒｅｔｅ　Ｃｏｓｉｎｅ　Ｔｒａｎｓｆｏｒｍ：離散コサイン変換）ベースのブロック符号化においては、ブロック単位に量子化レベルを決定すればよい。
【０１１７】
また、ＪＰＥＧ２０００では、１つのビットプレーンが３種類のパスに分類されてエントロピ符号化されるが、本手法においては、パス毎に別のビットプレーンとみなすことで前記した動作と同様に扱うことが可能である。
【０１１８】
【発明の効果】
以上説明したとおり、本発明に係る符号量制御方法、符号量制御装置及び符号量制御プログラムでは、以下に示す優れた効果を奏する。
【０１１９】
請求項１、請求項２、請求項４又は請求項５に記載の発明によれば、情報量を廃棄（量子化）することで、所定の符号量上限値の範囲内で圧縮符号化を行う画像符号化において、歪量を最小化する符号をテーブル検索及び四則演算による短いステップの演算で決定することができる。
これによって、汎用のＣＰＵであっても、動画像を実時間で高画質に圧縮符号化を行うことが可能になり、低コストで符号化装置を実現することができる。
【０１２０】
請求項３に記載の発明によれば、量子化を行うレベル（量子化レベル）をビットプレーン符号化におけるビットプレーンを廃棄する基準位置とすることで、例えば、ビットプレーン符号化によって量子化を行うＪＰＥＧ２０００等で、画像をブロックに分割し、そのブロックのビットプレーンを廃棄する位置を各ブロック毎に制御することが可能になる。
【図面の簡単な説明】
【図１】本発明の実施の形態に係る符号量制御装置の全体構成を示すブロック図である。
【図２】本発明の実施の形態に係る歪量テーブル及び符号量テーブルの構造を説明するための説明図である。
【図３】本発明の実施の形態に係る符号量基準値リストの構造を説明するための説明図である。
【図４】本発明の実施の形態に係る（問題Ａ）の解を求めるためにコードブロックを複数の対象に分解する作業を説明するための説明図である。
【図５】本発明の実施の形態に係る符号量制御動作の概略を示すフローチャートである。
【図６】本発明の実施の形態に係る作業テーブル初期設定の動作を示すフローチャートである。
【図７】本発明の実施の形態に係る作業テーブル設定の動作を示すフローチャートである。
【図８】本発明の実施の形態に係る逆探索の動作を示すフローチャートである。
【図９】本発明の実施の形態に係るインデックステーブル及び歪総量テーブルを設定する順序を視覚的に表した模式図である。
【図１０】本発明の実施の形態に係る逆探索動作を模式的に表した模式図である。
【図１１】サブバンド符号化におけるサブバンド分解とコードブロック分割を説明するための説明図である。
【図１２】ビットプレーン符号化の動作の概要を説明するための説明図である。
【図１３】ビットプレーン符号化におけるＴｒｕｎｃａｔｉｏｎ　ｐｏｉｎｔと符号量及び歪量との関係を説明するための説明図である。
【図１４】ビットプレーンの位置（大きさ）と、歪量及び符号量の関係を説明するための説明図である。
【符号の説明】
１……符号化装置
２……サブバンド分解手段
３……符号量制御装置
４……エントロピ符号生成手段
１０……コードブロック分割手段
１１……歪・符号量テーブル生成手段
１２……符号量基準値リスト生成手段
１３……作業テーブル生成手段
１４……逆探索手段
１５……ビット切り捨て手段
Ｄ…………歪量テーブル（歪・符号量テーブル保持手段）
Ｒ…………符号量テーブル（歪・符号量テーブル保持手段）
Ｋｓｅｔ…符号量基準値リスト（符号量基準値リスト保持手段）
Ｉｄｘ……インデックステーブル（作業テーブル保持手段）
Ｆ…………歪総量テーブル（作業テーブル保持手段）
【図１】
2004056605.tif 000006
【図２】
2004056605.tif 000007
【図３】
2004056605.tif 000008
【図４】
2004056605.tif 000009
【図５】
2004056605.tif 000010
【図６】
2004056605.tif 000011
【図７】
2004056605.tif 000012
【図８】
2004056605.tif 000013
【図９】
2004056605.tif 000014
【図１０】
2004056605.tif 000015
【図１１】
2004056605.tif 000016
【図１２】
2004056605.tif 000017
【図１３】
2004056605.tif 000018
【図１４】
2004056605.tif 000019