(57)【要約】【課題】  画像符号化におけるレート・歪み勾配が簡単な処理で効率良く求め、目標符号量の圧縮符号化した画像データを得る。【解決手段】  画像データ入力部２００で入力した画像データは、周知の手順でウェーブレット変換、量子化を経て、各コードブロックの全パスにおける符号データ列を生成し符号列格納部２０５に格納すると共に、各コードブロックの各パス位置における符号データの増加量と歪みとの関係を示す情報をコードブロック情報格納部２０７に格納する。ビット探索処理部２０９は、コードブロック情報格納部２０７に格納された情報に基づき、目標レート・歪み勾配情報を、その上位のビットから下位に向かって１ビットずつ決定していく。符号列形成部２０５はビット探索処理部２０９で求められたレート・歪み勾配情報に従って、符号列格納部２０６より該当するパス位置までの符号データ列を読出し、最終的な符号化データを生成する。【選択図】  図１
2005150845.tif 000002
【特許請求の範囲】
【請求項１】
画像データを周波数変換し、変換後のデータを所定サイズの複数のブロックに分割し、分割したブロック内の各係数値のビット情報を上位から下位に向かうパス順に符号化データを生成し、各ブロックの上位から下位に向かうどのパス位置までの符号化データを用いて圧縮符号化データにするかを、目標符号量Ｒmaxと各パス位置における符号データ量の増加量と画像の歪みで表わされるレート・歪み勾配λに基づき決定する画像データ符号化装置であって、
周波数変換したデータの各ブロックについて、各パス段階での符号データを記憶する第１の記憶手段と、
前記各ブロックにおける各パス段階における増加する符号量と歪み量、及び、増加する符号量に対する歪み量に関する情報を記憶する第２の記憶手段と、
有意ビット長ｎを有し、ｉ＝ｎ−１とする最上位ビットｉを“１”とする仮レート・歪み勾配情報を設定する設定手段と、
該設定手段で設定された仮レート・歪み勾配情報以上のレート・歪み勾配情報となる符号データの総符号量Ｒを、前記第２の記憶手段を参照することで算出する算出手段と、
該算出手段で算出した総符号量Ｒと前記目標符号量Ｒmaxとを比較する比較手段と、
該比較手段の比較結果に応じて、Ｒ＞Ｒｍａｘである場合には前記ｉを“１”だけ減じ、前記仮レート・歪み勾配情報のビットｉを“１”に更新し、前記Ｒ＜Ｒｍａｘである場合には前記ビットｉを“０”に修正し、前記ｉを“１”だけ減じ、前記仮レート・歪み勾配情報のビットｉを“１”に更新する更新手段と、
前記比較手段でＲ＝Ｒｍａｘとなる、或いは、前記仮レート・歪み勾配情報の全ビット情報が確定するまで、或いは、前記仮レート・歪み勾配情報までの符号を集めた符号量と目標符号量Ｒｍａｘの差が予め設定された誤差以内となるまで、仮レート・歪み勾配情報のビット情報の探索処理を行うべく、前記算出手段及び判断手段の処理を繰り返すビット探索手段とを備え、
前記ビット探索手段によって得られた最終の仮レート・歪み勾配情報を目標レート・歪み勾配情報λとし、当該レート・歪み勾配λに基づいて、前記第１の記憶手段に記憶された該当するパス段階での符号化データを読出し、圧縮符号化データとして出力することを特徴とする画像データ符号化装置。
【請求項２】
前記符号化はＪＰＥＧ２０００による符号化であることを特徴とする請求項１に記載の画像データ符号化装置。
【請求項３】
更に、符号化データを生成する際に各コードブロックの各パス段階でのレート・歪み勾配情報のうち、最大となるレート・歪み勾配情報を記憶保持する記憶保持手段と、
該記憶保持手段で記憶保持された、最大となるレート・歪み勾配情報の有意ビット数を求める有意ビット数算出手段とを備え、
前記仮レート・歪み勾配情報のビット数ｎは、前記有意ビット数算出手段で算出したビット数とすることを特徴とする請求項１に記載の画像データ符号化装置。
【請求項４】
更に、前記第２の記憶手段を検索することで、最大となるレート・歪み勾配情報を求める検索手段と、
該検索手段で検索した、最大となるレート・歪み勾配情報の有意ビット数を求める有意ビット数算出手段とを備え、
前記仮レート・歪み勾配情報のビット数ｎは、前記有意ビット数算出手段で算出したビット数とすることを特徴とする請求項１に記載の画像データ符号化装置。
【請求項５】
画像データを周波数変換し、変換後のデータを所定サイズの複数のブロックに分割し、分割したブロック内の各係数値のビット情報を上位から下位に向かうパス順に符号化データを生成し、各ブロックの上位から下位に向かうどのパス位置までの符号化データを用いて圧縮符号化データにするかを、目標符号量Ｒmaxと各パス位置における符号データ量の増加量と画像の歪みで表わされるレート・歪み勾配λに基づき決定する画像データ符号化方法であって、
周波数変換したデータの各ブロックについて、各パス段階での符号データを記憶する第１の記憶工程と、
前記各ブロックにおける各パス段階における増加する符号量と歪み量、及び、増加する符号量に対する歪み量に関する情報を記憶する第２の記憶工程と、
有意ビット長ｎを有し、ｉ＝ｎ−１とする最上位ビットｉを“１”とする仮レート・歪み勾配情報を設定する設定工程と、
該設定工程で設定された仮レート・歪み勾配情報以上のレート・歪み勾配情報となる符号データの総符号量Ｒを、前記第２の記憶手段を参照することで算出する算出工程と、
該算出工程で算出した総符号量Ｒと前記目標符号量Ｒmaxとを比較する比較工程と、
該比較工程の比較結果がＲ＞Ｒｍａｘである場合には前記ｉを“１”だけ減じ、前記仮レート・歪み勾配情報のビットｉを“１”に更新し、前記Ｒ＜Ｒｍａｘである場合には前記ビットｉを“０”に修正し、前記ｉを“１”だけ減じ、前記仮レート・歪み勾配情報のビットｉを“１”に更新する更新工程と、
前記比較工程でＲ＝Ｒｍａｘとなる、或いは、前記仮レート・歪み勾配情報の全ビット情報が確定するまで、或いは、前記仮レート・歪み勾配情報までの符号を集めた符号量と前記Ｒｍａｘとの差が所定値以内となるまで、仮レート・歪み勾配情報のビット情報の探索処理を行うべく、前記算出工程及び判断工程の処理を繰り返すビット探索工程とを備え、
前記ビット探索工程によって得られた最終の仮レート・歪み勾配情報を目標レート・歪み勾配情報λとし、当該レート・歪み勾配λに基づいて、前記第１の記憶工程に記憶された該当するパス段階での符号化データを読出し、圧縮符号化データとして出力することを特徴とする画像データ符号化方法。
【請求項６】
画像データを周波数変換し、変換後のデータを所定サイズの複数のブロックに分割し、分割したブロック内の各係数値のビット情報を上位から下位に向かうパス順に符号化データを生成し、各ブロックの上位から下位に向かうどのパス位置までの符号化データを用いて圧縮符号化データにするかを、目標符号量Ｒmaxと各パス位置における符号データ量の増加量と画像の歪みで表わされるレート・歪み勾配λに基づき決定する画像データ符号化装置として機能するコンピュータプログラムであって、
周波数変換したデータの各ブロックについて、各パス段階での符号データを記憶する第１の記憶手段と、
前記各ブロックにおける各パス段階における増加する符号量と歪み量、及び、増加する符号量に対する歪み量に関する情報を記憶する第２の記憶手段と、
有意ビット長ｎを有し、ｉ＝ｎ−１とする最上位ビットｉを“１”とする仮レート・歪み勾配情報を設定する設定手段と、
該設定手段で設定された仮レート・歪み勾配情報以上のレート・歪み勾配情報となる符号データの総符号量Ｒを、前記第２の記憶手段を参照することで算出する算出手段と、
該算出手段で算出した総符号量Ｒと前記目標符号量Ｒmaxとを比較する比較手段と、
該比較手段の比較結果に応じて、Ｒ＞Ｒｍａｘである場合には前記ｉを“１”だけ減じ、前記仮レート・歪み勾配情報のビットｉを“１”に更新し、前記Ｒ＜Ｒｍａｘである場合には前記ビットｉを“０”に修正し、前記ｉを“１”だけ減じ、前記仮レート・歪み勾配情報のビットｉを“１”に更新する更新手段と、
前記比較手段でＲ＝Ｒｍａｘとなる、或いは、前記仮レート・歪み勾配情報の全ビット情報が確定するまで、或いは、前記仮レート・歪み勾配情報までの符号を集めた符号量と前記Ｒｍａｘの差が所定値以内となるまで、仮レート・歪み勾配情報のビット情報の探索処理を行うべく、前記算出手段及び判断手段の処理を繰り返すビット探索手段とを備え、
前記ビット探索手段によって得られた最終の仮レート・歪み勾配情報を目標レート・歪み勾配情報λとし、当該レート・歪み勾配λに基づいて、前記第１の記憶手段に記憶された該当するパス段階での符号化データを読出し、圧縮符号化データとして出力する
として機能することを特徴とするコンピュータプログラム。
【請求項７】
請求項６に記載のコンピュータプログラムを格納することを特徴とするコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、静止画像または動画像のフレームデータを符号化する画像符号化技術に関するものである。
【背景技術】
【０００２】
画像符号化の効率を向上させる手法の一つとしてレート・歪み最適化手法がある。レート・歪み最適化手法は符号化データを構成する複数の区分ごとに発生符号量と画像の歪みに関する指標値を求め、総符号量が目標値以下という条件の基で総歪み指標値の最小化を図るものである。
【０００３】
ＩＳＯ／ＩＥＣ  ＪＴＣ１／ＳＣ２９／ＷＧ１での標準化作業により制定された静止画像符号化の国際標準である通称ＪＰＥＧ２０００（ＩＳＯ／ＩＥＣ  １５４４４）では、ウェーブレット変換により得られる各サブバンドの係数をコードブロックと呼ばれる矩形領域に分割してそれぞれ独立に符号化するという構成となっている。そして、各コードブロックを何回かに分けて（何回かのパスに分けて）符号化しており、パスを単位として発生符号量と画像の歪み指標値を求めてレート・歪み最適化手法を適用することが考慮されている。ＪＰＥＧ２０００標準を実施する上での上記レート・歪み最適化手法の一適用方法がある（非特許文献１）。
【０００４】
コードブロックBiの符号打ち切り可能点をniとし、niで符号を打ち切った場合のコードブロックBiの符号量をRi(ni)、歪みの指標値をDi(ni)とするとき、画像全体での歪み指標値Ｄ、および総符号量Ｒは、
Ｄ＝ΣＤi(ni)
Ｒ＝ΣＲi(ni)
で表わされる（ここでΣは、「ｉ=1,2,…,コードブロック総数」を変数とする合算関数）。歪みの指標値としては、平均二乗誤差や視覚的に重み付けされた平均二乗誤差など、画質の劣化の度合を表わす様々な値を用いることができる。
【０００５】
レート・歪み最適化の目標は、目標となる総符号量Rmax以下という条件、即ち、Ｒ≦Ｒmaxという条件で、Ｄを最小化する打ち切り点niの集合を求めることである。この最適化問題は、一般化ラグランジェ乗数法（非特許文献２）によって解決することができ、あるλの値について、
Σ（Ｄi(ni)＋λ×Ｒi(ni)）
を最小化する問題に帰着する。λの値は総符号量RがRmax以下となるように調整される。
【０００６】
この式の最小化は、各コードブロックの個々の最小化問題となる。以下、コードブロックBiについてＤi(ni)＋λ・Ｒi(ni)が最小となる符号打ち切り点niを求める単純なアルゴリズムについて説明する。
【０００７】
図４は有効符号化パスの数がki_maxであるコードブロックBiについて符号打ち切り点niを決定する処理の流れを示すものである。図４に示すように、まず、符号打ち切り点niを0に初期化しておく（ステップＳ４０１）。次に、着目する符号打ち切り可能点を示す変数kを１に設定する（ステップＳ４０２）。続いて、着目する符号打ち切り可能点ｋについて、このコードブロックBiの符号打ち切り点をniからkに移動させた場合の符号量増加分ΔRi(k)と歪み指標値減少分ΔDi(k)を求める（ステップＳ４０３）。符号打ち切り点niから着目する符号打ち切り可能点kの間にある符号の符号量対歪み指標値としてΔDi(k)/ΔRi(k)を算出してλと比較し（ステップＳ４０４）、大きければniの値をkに更新する（ステップＳ４０５）。次いで、kに１を加えて着目する符号打ち切り点を一つ下げ（ステップＳ４０６）、更新されたkの値をこのコードブロックの符号化パスの数ki_maxと比較し（ステップＳ４０７）、k≦ki_maxであれば更新されたkについてステップＳ４０３から繰り返して処理を行う。こうして、k＞ki_maxであれば処理を終了し、与えられたλでの着目コードブロックBiの符号打ち切り点は終了時点のniを決定する。
【０００８】
このアルゴリズムは種々のλの値について実施されることを考慮すると、あらかじめコードブロックの符号打ち切り点の候補を定めておく方が効率が良い。
【０００９】
コードブロックの符号打ち切りは符号化パス単位に行われるので基本的には全ての符号化パス境界で符号打ち切りが可能であるが、上述の符号打ち切り点ni決定アルゴリズムを適用する場合、符号打ち切り候補点間のレート・歪みの勾配を表す値Si(k)=ΔDi(k)/ΔRi(k)がkに伴って単調減少となるように打ち切り候補点が決定され、条件を満たさない符号化パス境界は符号打ち切り点の候補から除外する。
【００１０】
例えば図１０のように、４つの符号化パスにより符号化されたコードブロックを考える。４つのパスの境界（同図中、打ち切り可能点０から４）で符号を打ち切ることが可能であるが、打ち切り可能点２ではレート・歪みの勾配が単調減少となっておらず、コードブロックの符号を打ち切るのは効率的でないため、上述のアルゴリズムで符号打ち切り点として選択されることはないようにする。
【００１１】
なお、ここで言う、レート・歪みの勾配が減少するとは、その勾配が水平に近くなることを意味する。すなわち、「レート・歪みの勾配」の算術的な傾きの正負の符号は除外していることに注意されたい。
【００１２】
以下、全符号化パスの境界から符号打ち切り点の候補を決定するアルゴリズムについて説明する。
【００１３】
図５は符号打ち切り点の候補を選択する処理の流れを示す図である。ここでは符号打ち切り点の候補の集合をNiとする。まず、符号打ち切り点の候補の集合Niの初期状態として着目するコードブロックの全符号化パスの境界の集まりをセットする（ステップＳ５０１）。すなわち、コードブロックBiの符号化パスの数をki_maxとするとNi={1,2,3,・・・,ki_max}とする。
【００１４】
次に候補判定の対象となる符号打ち切り点pを0に設定する(ステップＳ５０２)。候補判定の対象となる符号打ち切り点の次の打ち切り点としてkを“１”に設定する(ステップＳ５０３)。kが集合Niに属しているか否かを判定し（ステップＳ５０３）、Niに属しているならば符号打ち切り点をpからkに移動させた場合の符号量増加分ΔRi(k),歪み指標値減少分ΔDi(k)を求め、更にこの区間のレート・歪み勾配Si(k)を求める(ステップＳ５０５)。Niに属さないならば後述するステップＳ５０８へと処理を移す。p≠0の場合、Si(k)とSi(p)を比較して(ステップＳ５０６)、Si(k)＞Si(p)ならばpを集合Niから除き（ステップＳ５１０）、ステップＳ５０２へと戻る。それ以外の場合にはpにkを設定し(ステップＳ５０７)、kの値に１を加えて更新し(ステップＳ５０８)、kとki_maxを比較してk≦ki_maxならば更新されたkについてステップＳ５０４から処理を行い、k＞ki_maxならば処理を終了して、この時点での集合Niに残った数字が符号打ち切り点（パス）の候補の集合となる。
【００１５】
上記処理を行うと、先に例に挙げた図１０のようなコードブロックの場合には、採集的に残った注目コードブロックＢｉの打ち切り点の候補集合Niは{1,3,4}となり、これらの打ち切り候補点については図１１に示すようにレート・歪み勾配がkに伴って単調減少となることが約束されることになる。
【００１６】
以上により得られた符号打ち切り点候補集合Niに属するｋについてSi(k),Ri(k)の値を保持しておき、Si(k)＞λとなる最大のkを選択する。λの値が小さい場合には符号打ち切り点は下がって切り捨てられる符号は少なくなり、逆にλの値が大きい場合には符号打ち切り点は上がって切り捨てられる符号は多くなるため、乗数λは画質のパラメータと見なすことができる。大きいλの値から小さい値へと変化させながら総符号量R=Rmax、あるいはR≒Rmaxとなるλを探して、そのλに基づいて各コードブロックの符号打ち切り点を決定することでレート・歪みの最適化を図ることができる。
【００１７】
以下、レート・歪み最適化手法をＪＰＥＧ２０００に適用する一形態について説明する。但し、ＪＰＥＧ２０００による符号化の具体的方法については勧告書に詳細に説明されているので、ここでは簡単な例についてその大まかな処理の流れのみを説明する。
【００１８】
説明簡略化のため、符号化対象画像は、各画素が８ビット（０〜２５５の２５６階調）で表現された５１２×５１２画素のモノクロ画像とし、符号化対象画像の各画素の水平方向の画素位置（座標）をｘ、垂直方向の画素位置をｙとして、画素位置（ｘ，ｙ）の画素値をＰ（ｘ，ｙ）で表す。また、ＪＰＥＧ２０００の符号化の条件として、タイル分割なし（５１２×５１２画素＝１タイル）、離散ウェーブレット変換２回、９×７非可逆フィルタ(9-7 Irreversible Filter)使用、コードブロックサイズは６４×６４、１レイヤでの符号列形成として説明する。その他にも、エントロピ符号化のオプションなど、様々な条件設定が必要であるが、ここでは特に言及しない。
【００１９】
図２はＪＰＥＧ２０００の符号化処理の流れを示す図である。同図において２００は画像入力部、２０１は離散ウェーブレット変換部、２０２は係数量子化部、２０３はコードブロック分割部、２０４はコードブロック符号化部、２０５は符号列形成部、２０６は符号列格納部、２０７はコードブロック情報格納部、２０８は符号出力部である。
【００２０】
まず、画像データ入力部２００から符号化対象の画像データを構成する各画素値Ｐ（ｘ，ｙ）が順に入力される。画像データ入力部２００では入力される各画素値Ｐ（ｘ，ｙ）から中間値１２８を引くことで０から２５５の入力データのＤＣレベルシフトを行い、−１２８から１２７までのデータＰ'（ｘ，ｙ）に変換して、離散ウェーブレット変換部２０１へと出力する。離散ウェーブレット変換部２０１ではＤＣレベルシフト後の入力データＰ'（ｘ、ｙ）を不図示の内部バッファに適宜格納し、２次元離散ウェーブレット変換を実施する。２次元離散ウェーブレット変換は、１次元の離散ウェーブレット変換を水平及び垂直方向それぞれに適用することにより行われる。離散ウェーブレット変換部２０１では１次元離散ウェーブレット変換として先に述べたように、９×７タップの非可逆フィルタを使用することとする。図３は、２次元離散ウェーブレット変換によって処理される符号化対象画像のサブバンドを説明するための図である。
【００２１】
すなわち、図３（ａ）に示されるような符号化対象画像に対して、まず垂直方向に１次元離散ウェーブレット変換を適用し、図３（ｂ）に示されるように低周波サブバンドＬと高周波サブバンドＨとに分解する。次に、それぞれのサブバンドに対して水平方向の１次元離散ウェーブレット変換を適用することにより、図３（ｃ）に示されるようなＬＬ、ＨＬ、ＬＨ、ＨＨの４つのサブバンドに分解し、１回目のウェーブレット変換を完了する。
【００２２】
離散ウェーブレット変換部２０１では、上述した２次元離散ウェーブレット変換により得られたサブバンドＬＬに対して、さらに繰り返して２次元離散ウェーブレット変換（２回目のウェーブレット変換）を適用する。これによって、符号化対象画像をＬＬ、ＨＬ１、ＬＨ１、ＨＨ１、ＨＬ２、ＬＨ２、ＨＨ２の７つのサブバンドに分解することができる。
【００２３】
図６は、２回目の２次元離散ウェーブレット変換によって得られる７つのサブバンドを示している。復号側ではＬＬサブバンドの係数を復号することにより水平・垂直方向ともに原画像の１／４の大きさ（水平・垂直方向画素数が１／４）で画像を再生することができ、さらにＨＬ１，ＬＨ１，ＨＨ１の係数を復号することにより水平・垂直とも１／２の大きさの画像を、ＨＬ２，ＬＨ２，ＨＨ２まで復号することにより元の画像と同じ大きさの画像を再生することができる。換言すれば、この順に画像の解像度が高くなることを意味するので、ＬＬサブバンドに基づいて生成される画像は解像度０、解像度０の画像及びＬＨ１，ＨＬ１，ＨＨ１のサブバンドで生成される画像は解像度レベル１、解像度１の画像及びＬＨ２，ＨＬ２，ＨＨ２のサブバンドで生成される画像は像度レベル２を有すると言い換えることができる。
【００２４】
さて、ここで、各サブバンド内の係数をＣ（Ｓｂ，ｘ，ｙ）と表す。ここで、Ｓｂはサブバンドの種類を表し、ＬＬ、ＬＨ１、ＨＬ１、ＨＨ１、ＬＨ２、ＨＬ２、ＨＨ２のいずれかである。また、（ｘ，ｙ）は各サブバンド内の左上隅の係数位置を（０，０）としたときの水平方向及び垂直方向の係数位置（座標）を表す。
【００２５】
係数量子化部２０２では、離散ウェーブレット変換部２０１で生成された各サブバンドの係数Ｃ（Ｓ，ｘ，ｙ）を、各サブバンド毎に定めた量子化ステップｄｅｌｔａ（Ｓ）を用いて量子化する。ここで、量子化された係数値をＱ（Ｓ，ｘ，ｙ）と表すとすると、係数量子化部２０３で行われる量子化処理は次式により表すことができる。
Ｑ（Ｓ，ｘ，ｙ）＝ｓｉｇｎ｛Ｃ（Ｓ，ｘ，ｙ）｝
×ｆｌｏｏｒ｛｜Ｃ（Ｓ，ｘ，ｙ）｜／ｄｅｌｔａ（Ｓ）｝
ここで、ｓｉｇｎ｛Ｉ｝は整数Ｉの正負符号を表す関数であり、Ｉが正の場合は１を、負の場合は−１を返す。また、ｆｌｏｏｒ｛Ｒ｝は実数Ｒを超えない最大の整数値を表す。
【００２６】
コードブロック分割部２０３は係数量子化部２０２で量子化されたサブバンドの係数Ｃ（Ｓ，ｘ，ｙ）を不図示の内部バッファに適宜格納してコードブロックとよばれる所定の大きさの矩形に分割して切り出す。コードブロック分割はサブバンドの左上隅を基準として例えば６４×６４のブロックに分割することで行われる。
【００２７】
したがって、２回ウェーブレット変換の場合、これによりＬＬ，ＨＬ１，ＬＨ１，ＨＨ１の各サブバンドは１２８×１２８のサイズであるから、それぞれ２×２＝４つのコードブロックを内包し、ＨＬ２，ＬＨ２，ＨＨ２の各サブバンドは４×４＝１６個のコードブロックを内包することになる。各コードブロックには順番に重複しない識別番号ｉ(＝０〜６３)を割り振り、B0,B1,B2,…,B63のようにBiという形でコードブロックを特定する。識別番号ｉは、先に説明したように解像度レベル順に割り振り、同一解像度レベル内においてはＨＬ，ＬＨ，ＨＨサブバンドの順、同一サブバンド内においてはラスタースキャン順に番号付けるものとする。
【００２８】
図７はコードブロック分割部２０３におけるコードブロック分割と番号の割振りの様子を示している。同図において実線はサブバンドの境界を表し、点線はコードブロックの境界を示しており、点線または実線で区切られる矩形がコードブロックである。
【００２９】
コードブロック符号化部２０４はコードブロック分割部２０３により切り出されたコードブロックBi内の量子化された係数値Ｑ（Ｓ，ｘ，ｙ）（以降、単に「係数値」と称す）の絶対値を自然２進数で表現して、上位の桁から下位の桁へとビットプレーン方向を優先して二値算術符号化し、コードブロックの符号化データを符号列格納部２０６に格納する。
【００３０】
このとき、各ビットプレーンは最上位のビットプレーンを除いて３つのパスに分けて符号化する。最上位のビットプレーンを複数パスに分割しないのは、最上位ビットプレーンに存在する各係数値のビットがその係数値に対して支配的であり、重要度が高いからである。
【００３１】
上記を分かりやすく示したのが図１２である。上記では１つのコードブロックは６４×６４サイズとしているが、同図では簡単のため４×５サイズで示している。最上位ビットプレーンについては、先に述べたように、該当するコードブロックの最上位ビットプレーンであるので、全ビットが符号化対象として扱われる。そして、最上位ビットプレーンよりも下位のビットプレーンは、図示の如く３つのグループに分けられ、それぞれの符号化対象ビット位置は図示のように排他的な位置に設定される（全部をまとめると１つのビットプレーンとなる、という意味）。これまで説明した符号化を打ち切るパスが仮にｎパス目としたとき、上位からｎパス目までの符号化データを利用し、それ以降のパスの符号化データを切り捨てることを意味する。
【００３２】
最上位ビットプレーンを除く、各ビットプレーンのパスへの分割、各パスでの具体的な符号化方法については勧告書に従う。各パスの符号化毎に着目するパスの符号量増加分ΔRi(k)と歪み指標値減少分ΔDi(k)を求め、図８に示すテーブルを構築して不図示の内部バッファに格納する。歪み指標値には平均二乗誤差や、サブバンド毎に重みをつけて導出される重み付き平均二乗誤差などが用いられる。３種類のパスそれぞれについて、各係数の歪み指標値減少分を導出する一方式は勧告書の附属書Ｊ等に記されている。着目するコードブロックBiについて全パスの符号化が終了し、図８のようなテーブルが完成されると、先に述べた符号打ち切り点の候補を選択するアルゴリズム（図５）を実行し、全符号化パス境界の集合からSi(k)が単調減少となる符号打ち切り点候補集合Niを求める。図９のように候補集合Niの要素の数NPと各打ち切り候補点でのパス番号k、レート・歪み勾配Si(k)、符号量Ri(k)をコードブロック情報格納部２０７に格納する。
【００３３】
符号列形成部２０５はコードブロック符号化部２０４により全てのコードブロックの符号化が終了すると、コードブロック情報格納部２０５に格納される各コードブロックの打ち切り候補点の情報を参照しながら、総符号量R=Rmax、あるいはR≒Rmaxとなるλを探して、Si(k)＞λとなる部分の符号を集めて最終符号列を形成し、出力する。
【００３４】
符号列形成部２０５におけるλ決定の処理の流れを図１３に示し、以下に説明する。尚、以下の説明において、閾値を表す変数としてSを導入し、処理終了時点での変数Sの値がλとなることに注意されたい。
【００３５】
まず、コードブロック情報格納部２０７に格納される全コードブロックの打ち切り候補点の情報を参照して、Si(k)の最小値Sminと最大値Smaxを求める（ステップＳ１４０１）。次に、閾値を表す変数SにステップＳ１４０１で求めたSmaxを設定する（ステップＳ１４０２）。続いて、変数Sからあらかじめ定めた閾値変更幅ΔSを減じ、変数Sの値を少しだけ下げる（ステップＳ１４０３）。コードブロック番号を表す変数iに0を設定し、累積符号量Rを0に初期化する（ステップＳ１４０４）。再び、コードブロック情報格納部２０５に格納されるコードブロックBiの打ち切り候補点情報を参照してSi(k)＞Sを満たす最大のkを求め、コードブロックBiの打ち切り点niとする（ステップＳ１４０５）。Si(k)の値はコードブロックBiの打ち切り候補点順に単調減少化されているのでSi(k)を候補点の順番に比較していくことでniを求めることができる。ステップＳ１４０５で求めた打ち切り点niでのコードブロックBiの符号量Ri(ni)を累積符号量Rに加える（ステップＳ１４０６）。次いで、変数iに１を加えて更新する（ステップＳ１４０７）。そして、変数iを64と比較し、i=64ならばステップＳ１４０９へ、そうでない場合にはステップＳ１４０５に処理を移して、次のコードブロックについて符号量加算を行う（ステップＳ１４０８）。
【００３６】
変数ｉの値が64に到達した場合、即ち、閾値Sについて全コードブロックからの累積符号量の算出が終了した場合、累積符号量Rを目標符号量Rmaxと比較し、R＜RmaxならばステップＳ１４１０へ、そうでなければステップＳ１４１１へと処理を移す（ステップＳ１４０９）。ステップＳ１４１１へと処理が移された場合には、現在の閾値Sでは目標符号量を超えるため、ΔSを加えてひとつ前の閾値Sに戻して処理を終了する（ステップＳ１４１１）。また、ステップＳ１４１０では閾値SをステップＳ１４０１で求めた最小値Sminと比較し、S＞SminであればステップＳ１４０３へと戻りSの値をまた少し小さくしてから再びステップＳ１４０９までの処理を行い、S≦Sminであれば処理を終了する。処理終了時点でのSが閾値λとして選択される。
【００３７】
上述の処理により求められた閾値λに対し、各コードブロックからSi(k)＞λとなる部分の符号を符号列格納部２０６から読み出して、ＪＰＥＧ２０００符号列のフォーマットに従って情報（メインヘッダ、タイルヘッダ、パケットヘッダなど）を付加してＪＰＥＧ２０００の符号列を形成し、符号出力部２０８へと出力する。
【００３８】
符号出力部２０８は符号列形成部２０５により生成されたＪＰＥＧ２０００符号化データを装置外部に出力する。符号出力部２０８は例えばハードディスク、光磁気ディスク、メモリなどの記憶媒体、または、ネットワークへのインターフェースなどである。
【非特許文献１】標準勧告書（ＩＳＯ／ＩＥＣ  １５４４４−１）の附属書Ｊ
【非特許文献２】“Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources”, Operation Research, vol.11, pp.399-417, 1963
【発明の開示】
【発明が解決しようとする課題】
【００３９】
しかしながら、上述の方法によりR≒Rmaxとなる最大のλを見つけるためには、様々なλで総符号量Rを求めて目標符号量Rmaxと比較するという処理を繰り返す必要があり、符号打ち切り点候補の情報Si(k),Ri(k)を格納するメモリへの多数回のアクセスや、Si(k)とλの比較など、総符号量Rを求めるために必要な演算コストなどから多くの処理時間を必要とするなどの問題がある。
【００４０】
また、前述のしきい値変更幅ΔＳを小さくすればする程、RをRmaxに近づけることができるが、変更幅に反比例して上記演算量は増加する。しかも、演算量を増やしたからと言って、Rmaxに最も近いRを得ることが保証されるものでもない、という問題点がある。
【００４１】
本発明は、このような事情を考慮してなされたものであり、より単純な処理で、目標符号量となる最適なレート・歪み勾配を決定し、圧縮符号化画像データを生成する技術を提供しようとするものである。
【課題を解決するための手段】
【００４２】
この課題を解決するため、例えば本発明の画像データ符号化装置は以下の構成を備える。すなわち、
画像データを周波数変換し、変換後のデータを所定サイズの複数のブロックに分割し、分割したブロック内の各係数値のビット情報を上位から下位に向かうパス順に符号化データを生成し、各ブロックの上位から下位に向かうどのパス位置までの符号化データを用いて圧縮符号化データにするかを、目標符号量Ｒmaxと各パス位置における符号データ量の増加量と画像の歪みで表わされるレート・歪み勾配λに基づき決定する画像データ符号化装置であって、
周波数変換したデータの各ブロックについて、各パス段階での符号データを記憶する第１の記憶手段と、
前記各ブロックにおける各パス段階における増加する符号量と歪み量、及び、増加する符号量に対する歪み量に関する情報を記憶する第２の記憶手段と、
有意ビット長ｎを有し、ｉ＝ｎ−１とする最上位ビットｉを“１”とする仮レート・歪み勾配情報を設定する設定手段と、
該設定手段で設定された仮レート・歪み勾配情報以上のレート・歪み勾配情報となる符号データの総符号量Ｒを、前記第２の記憶手段を参照することで算出する算出手段と、
該算出手段で算出した総符号量Ｒと前記目標符号量Ｒmaxとを比較する比較手段と、
該比較手段の比較結果に応じて、Ｒ＞Ｒｍａｘである場合には前記ｉを“１”だけ減じ、前記仮レート・歪み勾配情報のビットｉを“１”に更新し、前記Ｒ＜Ｒｍａｘである場合には前記ビットｉを“０”に修正し、前記ｉを“１”だけ減じ、前記仮レート・歪み勾配情報のビットｉを“１”に更新する更新手段と、
前記比較手段でＲ＝Ｒｍａｘとなる、或いは、前記仮レート・歪み勾配情報の全ビット情報が確定するまで、或いは、前記仮レート・歪み勾配情報までの符号を集めた符号量と前記Ｒｍａｘとの差が所定値以内となるまで、仮レート・歪み勾配情報のビット情報の探索処理を行うべく、前記算出手段及び判断手段の処理を繰り返すビット探索手段とを備え、
前記ビット探索手段によって得られた最終の仮レート・歪み勾配情報を目標レート・歪み勾配情報λとし、当該レート・歪み勾配λに基づいて、前記第１の記憶手段に記憶された該当するパス段階での符号化データを読出し、圧縮符号化データとして出力することを特徴とする。
【発明の効果】
【００４３】
本発明によれば、目標となるレート・歪み勾配情報がｎビットで表わされるとした場合、最大でもｎ回の符号量算出と比較処理で全ビットの情報を確定でき、レート・歪み勾配を効率良く求めることが可能となり、目標符号量の符号化データを効率良く生成することが可能になる。
【発明を実施するための最良の形態】
【００４４】
以下、添付図面に従って本発明にかかる実施形態を詳細に説明する。
【００４５】
図１は実施形態における画像符号化処理装置のブロック構成図である。
【００４６】
図２と異なる点は、コードブロック情報格納部２０７をアクセスするビット探索処理部２０９を設け、このビット探索処理部２０９が目標となるレート・歪み勾配情報の各ビットを順に確定する点である。符号列格納部２０５は、このビット探索処理部２０９で求めた処理結果（レート・歪み勾配情報）に基づいて符号列格納部２０５より該当する各コードブロックのパス位置における符号列を読出し、出力符号化データを生成することになる。それ以外は先に説明した内容と同様であるものとし、以下では、本実施形態の特徴部分について説明する。
【００４７】
なお、詳細は後述するが、実施形態におけるコードブロック符号化部２０４は、１つの画像データを符号化する際、各コードブロックの各パス段階での符号データ列を生成する際、レート・歪み勾配を求め、求めたレート・歪み勾配と従前のレート歪み勾配とを比較し、大きい方を記憶保持する手段（レジスタ等）を備える。１つの画像全体の符号データ列の生成が完了したとき、その画像全体における最大レート・歪み勾配情報を初期処理で利用するためである。
【００４８】
図１に示した装置全体の処理は、図１４に示す手順に従って処理される。
【００４９】
同図において、先ず、ステップＳ１００にて画像データを入力する。この画像データの入力は例えばイメージスキャナであるが、画像データを記憶した記憶媒体から画像データを読取る構成でも勿論構わないし、ネットワークインタフェースを介して画像データを入力しても勿論構わない。
【００５０】
次いで、ステップＳ１０１にて入力した画像データに対して離散ウェーブレット変換処理を行い、ステップＳ１０２にて変換結果の各係数の量子化処理を行う。そして、量子化結果を今度はコードブロックに分割し（ステップＳ１０３）、各コードブロック符号化処理を行う。このとき、各コードブロックをビットプレーンに分割し、なおかつ、最上位ビットプレーンを除くビットプレーンについては３つのパスに分け、最上位のパスから順に符号データ列を生成する（ステップＳ１０４）。次に、ステップＳ１０５において、各パス毎の符号化データを所定の記憶手段に格納すると共に、ステップＳ１０６において各コードブロック毎に、各パスにおける符号増加量と歪み量とを関連付けてコードブロック情報（図８参照）として所定の記憶手段に格納する。
【００５１】
次に、本実施形態における特徴部分である、ビット探索処理を行い、目標レート・歪み勾配λを求める（ステップＳ１０７）。この結果、各コードブロック毎のパス打ち切り位置が求められるので、ステップＳ１０９にて、先に格納した各コードブロック中の該当するパス位置までの符号化データ列を取り出し、最終的な画像全体の符号化データ列を生成し、ステップＳ１１０にて生成された符号化コード列を出力する。
【００５２】
上記処理中、本実施形態における特徴的な処理はステップＳ１０７、すなわち、図１におけるビット探索処理部２０９にある。そこで、以下では、かかる点を中心に説明することとする。
【００５３】
先ず、説明を簡単にするため、本実施形態の画像符号化装置で符号化対象とする画像符号化データは、前述の従来例と同じく、５１２×５１２の各画素８ビットのモノクロ画像データとする。また、タイル分割の無（１タイル＝５１２×５１２）、コードブロックのサイズは６４×６４、９×７タップフィルタを用いた２回ウェーブレット変換を行うものとする。すなわち、先に説明した従来例と同じとする。
【００５４】
また、符号列格納部２０６には、各コードブロックの、各パス段階での符号データ列が既に格納され、コードブロック情報格納部２０７は各コードブロック毎の図８に示すテーブルが既に作成されているものとする。また、レート・歪み勾配情報は８ビットで表現されるものとする。
【００５５】
実施形態におけるビット探索処理部２０９は、コードブロック情報格納部２０７に格納された情報に基づき、目標符号量もしくはそれに近似する符号量を得るための、目標レート・歪み勾配情報λthを上位ビットから下位ビットに向かう方向に１ビットずつ決定するものである。以下、その原理を説明する。
【００５６】
先ず、初期段階において、ビット探索処理部２０９は、コードブロック符号化部２０４が記憶保持していた最大レート・歪み勾配情報λmaxを入力する。最大レート・歪み勾配情報λmaxは、コードブロック情報格納部２０７を検索することでも得られるが、上記のようにするとその検索に要する処理が省かれ、都合が良い。
【００５７】
目標レート・歪み勾配情報λthは、０以上で、且つ、最大レート・歪み勾配情報λmax以下であることが約束されている。換言すれば、最大レート・歪み勾配情報λmaxの最上位ビットから下位に向かうｍ個のビットが“０”となっていた場合、目標レート・歪み勾配情報λthの最上位から下位に向かう、少なくともｍビットもまた“０”であることが約束されていることになる。従って、最大レート・歪み勾配情報λmaxを取得することは、目標レート・歪み勾配情報λthの最上位ビットから０に設定できるビット数を求めることを等価のものとなる。
【００５８】
従って、目標レート・歪み勾配情報λthは、下位ｎ（＝８−ｍ）ビット（実施形態では、レート・歪み勾配情報は８ビットとしていることに注意）が如何なる状態であるかを求めれば良いことになる。
【００５９】
今、ここでコードブロック符号化部２０４より入力した全コードブロック中の最大レート・歪み勾配情報λmaxが、仮に、“１１”（２進数８ビットで示すと“００００１０１１”）であったとする。この場合、目標レート・歪み勾配情報λthの少なくとも上位４ビットは０であり、下位４ビットが不定であることになる。すなわち、目標レート・歪み勾配情報λthは２進数表記で示すと“００００ｘｘｘｘ”（ｘは０、１のいずれか）となる。
【００６０】
つまり、目標レート・歪み勾配情報λthは、二進数で示すと“００００１１１１”（以下、λvmaxという）と、“００００００００”（以下、λvminという）の間に存在すると言い換えることができる。なお、上記の場合、λvmax＞λmaxとなってしまうので、厳密に言えば、λvmaxをλmaxとすべきであるが、本実施形態ではビット毎にλhを決定していくので、λvmaxをλmaxが有する有意なビット群のうち最上位のビット位置でもって決定する。
【００６１】
さて、λvmaxとλvminが決定されると、そのほぼ中間値を仮のレート歪み勾配閾値λm＝００００１０００を求める。すなわちλmは、λthの未定のビット群（上記では下位４ビット）中の最上位ビットを“１”と仮定し、それより下位のビットを０とする。
【００６２】
図１５の符号１５０１乃至１５０４は符号量と歪みを示してる。横軸は符号量であるが、パス段階と見ることもできる点に注意されたい。
【００６３】
図１５における符号１５０１は、λvmax,λm,λvminそれぞれにおける符号量と歪みＤを示しているが、閾値λm以上の累積符号量Ｒ（レート・歪み勾配をλmとした場合の符号データ量をコードブロック情報格納部２０７を調べ、累積加算することで得られる）と目標符号量Ｒmaxとを比較したとき、その取り得る関係は、
Ｒ＞Ｒmax  or
Ｒ＜Ｒmax  or
Ｒ＝Ｒmax
のいずれかになる。
【００６４】
ここで、「Ｒ＞Ｒmax」という関係がある場合には、図示の符号１５０２の如く、求めるλthは現時点でのλmの左側に存在することになる。従って、この場合には、λvminをその時点でのλmで更新し、λvmaxと更新後のλvminとの中間位置、すなわち、値“００００１１００”を新たなλmとする。換言すれば、λthの不定となっていた４ビット中の最上位のビットは“１”として確定し、その下位のビットを“１”と仮定する。
【００６５】
一方、「Ｒ＜Ｒmax」という関係になった場合には、図示の符号１５０４で示すように、求めるλthは現時点でのλmの右側に存在することを示す。従って、この場合には、λvmaxを現時点でのλmで更新し、λminと更新後のλvmaxの中間位置である値“０００００１００”を新たなλmとする。換言すれば、λthの不定となっていた４ビット中の最上位のビットは“０”として確定し、その下位のビットを“１”と仮定する。
【００６６】
そして、「Ｒ＝Ｒmax」であるという関係にある場合には、その時点でのλmが求めるλthであると判定し、本処理を終える。
【００６７】
ここで、「Ｒ＞Ｒmax」又は「Ｒ＜Ｒmax」のいずれかの場合には、上記処理を繰り返すことで、当初のλthの未定となっていた４ビットを、その上位ビット位置から順に確定していく。
【００６８】
図１７は、全コードブロックの最大レート・歪み勾配λmaxが十進数表記で“１１”（二進表記で“００００１０１１”）の場合の場合を示している。λmaxはその上位から調べていってビット３で始めて“１”になるから、仮のλｍはその上位４ビットを“０”にし、未定のビットは下位の４ビットであることになる。従って、その未定のビット群中の最大位置にあるビット３を開始ビット位置とし、以下、ビット２、ビット１、ビット０の順にそのビット位置を確定していくことを示している。
【００６９】
要するに、当初のλthの、未定ビットがｎビットである場合、最大でもｎ回の総符号量Ｒを求める処理、及び比較処理を行えば、Ｒ≦Ｒmaxとなる最終的なλthを求めることができることを意味する。実施形態では、レート・歪み勾配情報が８ビットで表現される場合について述べているので、最大でも８回の演算で済むことも意味するものとも言える。
【００７０】
以上であるが、実施形態におけるビット探索処理部２０９の具体的な構成を図１６に示し、以下、その構成をその動作処理内容に従って説明する。
【００７１】
最大有意ビット位置検出部１００は、コードブロック符号化部２０４が１つの画像データの符号化処理が完了した後、コードブロック符号化部２０４が記憶保持している全コードブロック中の最大レート・歪み勾配情報λmaxを入力し、その最上位ビットＭＳＢから下位に向かうビットを調べ、最初に“１”となったビット位置を示す情報Ｓを閾値生成部１０１、及び、判定部１０６に出力する。例えば、最大レート・歪み勾配情報λmaxの値が先に説明したように十進数で“１１”である場合、二進数で示すと“００００１０１１”となるから、ビット７からビット４までは“０”、ビット３になって始めて“１”となるから、「３」を出力する。
【００７２】
閾値生成部１０１は、初回時には、最大有意ビット位置検出部１００からの情報Ｓを入力し、その有意ビット位置を“１”とした仮の閾値λｍ（初期λｍ）を発生し、それを符号量Ｒ決定部１０３に出力する。例えば、最大有意ビット位置が「３」であれば、λｍ＝“００００１０００”となる。
【００７３】
符号量Ｒ決定部１０３は、入力したレート・歪み勾配情報λｍ以上のレート・勾配情報となる総符号データ量Ｒを、コードブロック情報格納部２０７を検索し、該当する符号量を累積加算することで取得し、その結果を比較部１０４に出力する。
【００７４】
比較部１０４は、予め設定された目標符号量Ｒmaxと、符号量Ｒ決定部１０３からの符号量Ｒとを比較し、その比較結果、すなわち、Ｒ＜Ｒmax、Ｒ＞Ｒmax、Ｒ＝Ｒmaxのいずれであるのかを示す情報を判定部１０６に出力する。
【００７５】
符号量Ｒ決定部１０３は、以下に示す３つの判定処理のいずれか１つを行う。ただし、最大有意ビット位置検出部１００から出力された値Ｓを初期値とし、３つの処理のいずれを行った場合にも１だけ減じるカウンタを有する。カウンタが保持された値をＣＴとしたとき、初回ではＣＴ＝Ｓとなる。
【００７６】
＜判定処理１＞
比較部１０４から比較結果の情報が「Ｒ＝Ｒmax」を示す情報であるとき、現時点でのλｍを目標レート・歪み勾配情報λthであるとして符号列形成部２０５に出力する。このとき、カウンタの値ＣＴが０以外であっても、本処理を終了する。
【００７７】
＜判定処理２＞
比較部１０４からの比較結果の情報が「Ｒ＞Ｒmax」を示す情報であるとき、カウンタＣＴの値で示されるビットＣＴのビット情報は“１”で正しいものとして確定する（ＣＴ＝Ｓ＝３の場合、λｍのビット３は“１”で正しいとする）。そして、ＣＴを１だけ減じる。更に、減じたＣＴで示されるビット位置（ビットＣＴ）を仮に“１”とするため、λｍを更新するよう閾値生成部１０１に要求する。
【００７８】
例えば、Ｓ＝ＣＴ＝３のときλｍは“００００１０００”であったが、ＣＴ＝ＣＴ−１＝２とすることで、現在のλｍのビット２を“１”とする新たなλｍ＝“００００１１００”を発生するよう要求する。
【００７９】
なお、更新後のＣＴ＜０になった場合、有意ビットと判定された全ビットの状態が確定したことになるので、最後の符号量Ｒを求めたλｍを目標レート・歪み勾配情報λthとして符号列形成部２０５に出力し、この処理を終える。
【００８０】
＜判定処理３＞
比較部１０４からの比較結果の情報が「Ｒ＜Ｒmax」を示すとき、カウンタＣＴの値で示されるビットＣＴのビット情報は誤りであり、“０”であるとして確定する（ＣＴ＝Ｓ＝３の場合、λｍのビット３を“０”とする）。そして、ＣＴを１だけ減じる。更に、減じたＣＴで示されるビット位置を仮に“１”とするため、λｍを更新するよう閾値生成部１０１に要求する。
【００８１】
例えば、Ｓ＝ＣＴ＝３のときλｍは“００００１０００”であったが、このビット３の値は“０”が正しいことが判明したわけであるから、ＣＴ＝ＣＴ−１＝２とすることで、現在のλｍのビット２を“１”とする新たなλｍ＝“０００００１００”を発生するよう要求する。なお、更新後のＣＴ＜０になった場合、有意ビットと判定された全ビットの状態が確定したことになるが、このときの符号量Ｒを求めたλｍの最下位ビットは０にし、その結果をλｍの目標レート・歪み勾配情報λthとして符号列形成部２０５に出力し、この処理を終える。
【００８２】
以上のようにして、目標レート・歪み勾配情報λthが求められるが、符号列形成部２０５は、与えられた目標レート・歪み勾配情報λthを最大レート・歪み勾配情報とし、コードブロック情報格納部２０７の該当するパス位置を各コードブロック毎に決定し、その決定したパス位置までの符号データ列を符号列格納部２０６より読出し、所定のフォーマットにデータを構成し、符号出力部２０８に出力することになる。
【００８３】
以上説明したように本実施形態によれば、レート・歪み勾配情報がｎビットで表現される場合には、最大でもｎ回の符号量Ｒを求める処理と目標符号量Ｒｍａｘとの比較処理を行うことで目標レート・歪み勾配情報を求めることができるようになる。従って、これまでのように初期値λにΔλを順次加算して求めていく処理と比べ、格段に演算処理量及びコードブロック情報格納部へのアクセス回数が減り、処理速度を大幅に向上させることが可能となる。
【００８４】
また、符号化処理を行う際に得られた全コードブロックのレート・歪み勾配情報の最大値を示す有意ビット数を求め、その有意ビット数中の最大ビット位置から下位方向に沿って目標レート・歪み勾配情報λthの各ビット状態を確定していくので、有意ビット以外のビット状態の判定処理は不要になる分、処理を簡略化させることが可能となる。更に、全コードブロックのレート・歪み勾配情報の最大値は、コードブロック符号化部２０４に最大値を保持させることで、コードブロック情報格納部２０７を検索する処理が１回減り、処理量を更に減らすことが可能になる。
【００８５】
なお、実施形態における目標レート・歪み勾配情報λthを求めるための処理を、例えばパーソナルコンピュータ等の汎用情報処理装置で実現する場合の構成を示すと図１９のようになる。
【００８６】
図中、１は装置全体の制御を司るＣＰＵ、２はブートプログラム及びＢＩＯＳ等を記憶するＲＯＭ、３はＣＰＵ１のワークエリアとして使用されるＲＡＭである。４はハードディスク装置等の外部記憶装置であって、ここには図２０に示すようにＯＳ、画像圧縮処理に係るアプリケーションプログラム（ＪＰＥＧ２０００アプリケーション）が格納されている。また、最終的に目標符号量ＲmaxもしくはＲｍａｘ未満でＲmaxに近似する符号量をネットワーク上に配信するための通信プログラム等も格納されている。５は画像入力部であって、例えばイメージスキャナ等であるが、画像データが記憶媒体に記憶されている場合にはその記憶媒体をアクセスする手段、画像データがネットワーク上のサーバに存在する場合にはネットワークインタフェースと見ることもできる。６はキーボード（ＫＢ）やポインティングデバイス（ＰＤ）であり、７はビデオＲＡＭを搭載すると共にそのビデオＲＡＭへの描画処理及びビデオＲＡＭからデータを読出しビデオ信号として出力する表示制御部である。８は表示制御部７よりのビデオ信号に基づき表示する表示装置である。
【００８７】
上記構成において、電源を投入すると、ＣＰＵ１はＲＯＭ２に格納されたブートプログラムに従って外部記憶装置よりＯＳをＲＡＭ３にロードし、しかる後、画像圧縮プログラムをロードすることで、画像入力部５より入力した画像データを、予め設定された目標符号量Rmax、もしくは、それを越えないで近似する符号量の圧縮符号化データを生成し、外部記憶装置に格納することになる。なお、最終的に生成された圧縮符号化画像データの出力先は外部記憶装置ではなく、ネットワークを介して出力しても構わないし、その出力先は問わない。
【００８８】
ここで、上記画像データの圧縮符号化処理プログラムは、先に説明したように、図１４の処理手順にて行われるが、ステップＳ１０６までで生成されたコードブロック格納部、符号列格納部としてのデータは、図１９に示すように、外部記憶装置４に一時的に格納されることになる。なお、ＲＡＭ上に確保できるのであれば、ＲＡＭ上でも構わない。
【００８９】
そして、本実施形態におけるステップＳ１０７におけるビット探索処理は、図１８に示す処理を実行すれば良い。以下、図１８に従ってソフトウェアで実現する例を説明する。
【００９０】
先ず、ステップＳ１８０１では、外部記憶装置４に格納されたコードブロック情報格納部を参照して、入力した画像の全コードブロックの最大レート・歪み勾配情報λmaxを求める。コードブロック情報格納部には、１つのコードブロックについて図８のような形式のデータが生成されているから、増加する符号量と歪み指標値との比を算出することを行い、全コードブロック中の最大値となるものを算出すればよい。なお、コードブロックの符号化データ列を生成する際に、最大値を記憶保持するようにし、それを利用すれば更にλmaxは容易に求めることもできる。
【００９１】
次いで、ステップＳ１８０２に進み、λmax中の有意なビット群中の最大ビット位置を求め、それを変数ｎに格納する。ステップＳ１８０３では、目標レート・歪み勾配を求めるための変数λｍ（但し、ｎビット以上）をゼロクリアし、ステップＳ１８０４にて、そのビットｎを“１”にセットする。
【００９２】
ステップＳ１８０５では、コードブロック情報格納部を参照し、λｍ以上のレート・歪み勾配を有する各コードブロックの符号量を累積加算し、λｍ以上の総符号量Ｒを求める。そして、ステップＳ１８０５にて、求めた総符号量Ｒと目標符号量Ｒmax（ユーザがキーボード等で指定してもよいし、原稿画像のサイズに基づいて決定するようにしても良い）とを比較する。
【００９３】
Ｒ＜Ｒmaxであると判断した場合、λｍのビットｎは“１”でなく、“０”であることになるから、ステップＳ１８０７にてλｍのビットｎを“０”に修正する。
【００９４】
ステップＳ１８０６にてＲ＞Ｒmaxと判断された場合、或いは、ステップＳ１８０７の処理が行われると、ステップＳ１８０８に進み、変数ｎが“０”であるか否か、すなわちＬＳＢの判定が完了したか否かを判断する。否（ｎ＞０）の場合には、ステップＳ１８０９にて変数ｎを“１”だけ減じ、ステップＳ１８１０にてλｍのビットｎを“１”に設定し、ステップＳ１８０５に戻り、上記処理を繰り返す。
【００９５】
ここで、ステップＳ１８０６にてＲ＝Ｒｍａｘ、もしくは、ステップＳ１８０８にてｎ＝０であると判断した場合、その時点でのλｍを、目標レート・歪み勾配λthとして決定（ステップＳ１８１１）、本処理をコールした処理に戻る。この後は、図１４に示す処理ステップＳ１０９、Ｓ１１０を行えば良い。
【００９６】
以上、本発明に係る実施形態を説明したが、本発明はＪＰＥＧ２０００での実施に好適であるものの、符号化データを小区分に分けて符号量、歪み指標値を得られるその他の符号化方式においても適用することが可能である。
【００９７】
また、上述の実施の形態では、５１２×５１２の各画素８ビットのモノクロ画像データを符号化対象画像として説明したが、その他のサイズ、ビット深度の画像、各画素が複数の色成分で表されたカラー画像など、その他の画像データに適用しても構わない。さらに、動画像の各フレーム、フィールドなどに対して適用しても構わない。
【００９８】
さらにまた、実施形態における処理は、先に説明したようにパーソナルコンピュータ等の汎用情報処理装置で実行するコンピュータプログラムにも適用できる。また、コンピュータプログラムは、通常、ＣＤＲＯＭ等のコンピュータ可読記憶媒体をそのコンピュータにセットし、システムにコピー若しくはインストールを行うことで実行可能となるわけであるから、本発明はかかるコンピュータ可読記憶媒体をも含むのは明らかである。
【図面の簡単な説明】
【００９９】
【図１】実施形態における画像符号化装置のブロック構成図である。
【図２】画像符号化装置の従来例の構成を示すブロック構成図である。
【図３】２次元離散ウェーブレット変換によって処理される符号化対象画像のサブバンドを説明するための図である。
【図４】コードブロックBiの符号打ち切り点niを決定する処理の流れを示すフローチャートである。
【図５】コードブロックBiのパスの統合による単調減少化の処理の流れを示すフローチャートである。
【図６】２回の２次元離散ウェーブレット変換によって得られる７つのサブバンドを説明するための図である。
【図７】コードブロック分割部２０３におけるコードブロック分割の様子を示す図である。
【図８】コードブロック符号化部２０４の内部に構築されるコードブロックBiの情報の例を示す図である。
【図９】コードブロック情報格納部２０７に格納される符号打ち切り候補点の情報を表す図である。
【図１０】コードブロックの各パスのレートと歪みの関係の一例を示す図である。
【図１１】単調減少化処理により、パスが統合される様子を示す図である。
【図１２】コードブロックの各ビットプレーンと、符号化のパスとの関係を示す図である。
【図１３】従来の符号列形成部２０５におけるλ決定の処理の流れを示すフローチャートである。
【図１４】実施形態における画データ圧縮処理の処理手順を示すフローチャートである。
【図１５】図１におけるビット探索処理部の原理を説明するための図である。
【図１６】図１におけるビット探索処理部の構成の一例を示す図である。
【図１７】図１におけるビット探索処理部の処理内容を説明するための図である。
【図１８】ビット探索処理をソフトウェアで実現するための処理手順を示すフローチャートである。
【図１９】実施形態における画像圧縮処理をコンピュータプログラムにより実現する際の装置の構成例を示す図である。
【図２０】外部記憶装置に格納、確保されるプログラムや作業領域を示す図である。
【図１】
2005150845.tif 000003
【図２】
2005150845.tif 000004
【図３】
2005150845.tif 000005
【図４】
2005150845.tif 000006
【図５】
2005150845.tif 000007
【図６】
2005150845.tif 000008
【図７】
2005150845.tif 000009
【図８】
2005150845.tif 000010
【図９】
2005150845.tif 000011
【図１０】
2005150845.tif 000012
【図１１】
2005150845.tif 000013
【図１２】
2005150845.tif 000014
【図１３】
2005150845.tif 000015
【図１４】
2005150845.tif 000016
【図１５】
2005150845.tif 000017
【図１６】
2005150845.tif 000018
【図１７】
2005150845.tif 000019
【図１８】
2005150845.tif 000020
【図１９】
2005150845.tif 000021
【図２０】
2005150845.tif 000022