(57)【要約】【課題】  画像符号化におけるレート・歪み勾配が簡単な処理で効率良く求め、目標符号量の圧縮符号化した画像データを得る。【解決手段】  画像データ入力部２００で入力した画像データは、周知の手順でウェーブレット変換、量子化を経て、各コードブロックの全パスにおける符号データ列を生成し符号列格納部２０５に格納すると共に、各コードブロックの各パス位置における符号データの増加量と歪みとの関係を示す情報をコードブロック情報格納部２０７に格納する。ノード処理部２０９は、コードブロック情報格納部２０７に格納された情報を、２分木であるトーナメント・ツリーの末端ノードに設定する。そして、各ノードにおいてレート・歪み大小関係を比較して最上位に到達する情報を更新して、再度トーナメント・ツリーを更新することで最適なレート・歪み勾配を決定する。符号列形成部２０５はこの最適レート・歪み勾配に従って、符号列格納部より該当するパス位置までの符号データ列を読出し、最終的な符号化データを生成する。【選択図】  図１
2005150843.tif 000002
【特許請求の範囲】
【請求項１】
画像データを帯域分割し、帯域分割後のデータを所定サイズの複数のブロックに分割し、分割したブロック内の各係数値のビット情報を上位から下位に向かうパス順に符号化データを生成し、各ブロックの上位から下位に向かうどのパス位置までの符号化データを用いて圧縮符号化データにするかを、目標符号量と各パス位置における符号データ量の増加量と画像の歪みで表わされるレート・歪み勾配λに基づき決定する画像データ符号化装置であって、
帯域分割したデータの各ブロックについて、各パス段階での符号データを記憶する第１の記憶手段と、
前記各ブロックにおける各パス段階におけるレート・歪み勾配情報を記憶する第２の記憶手段と、
レート・歪み勾配情報及びブロックを特定する属性情報で構成される比較要素情報を、２分木構造の各ノードに相当する位置に記憶するための複数の記憶保持手段と、
前記２分木構造の末端に位置する複数のノードの記憶保持手段に、前記第２の記憶手段に記憶された各ブロックの所定パス段階でのレート・歪み勾配情報及びブロックを特定する情報で構成される比較要素情報を設定すると共に、２つの子ノードの記憶保持手段に記憶された比較要素情報中のレート・歪み勾配情報の大小判定することで一方の子ノードの比較要素情報を２つの子ノードに共通する親ノードの記憶保持手段に記憶保持する処理を、末端に位置するノードから順に行う処理手段と、
該処理手段によって最上位のノード位置の記憶保持手段に記憶保持された比較要素情報を注目比較要素情報としたとき、当該注目比較要素情報で特定されたブロックのレート・歪み勾配情報のパス段階での符号データ量を累積加算するための所定の符号量記憶手段に累積加算すると共に、前記注目比較要素情報のレート・歪み勾配情報のパス段階を次のパス段階のレート歪み勾配情報に変更し、当該変更した注目比較要素情報の比較要素情報で、変更前の注目比較要素情報を記憶していた末端のノード位置の記憶保持手段を更新する末端ノード更新手段と、
該末端ノード更新手段で更新された記憶保持手段の、親ノードから最上位のノードに至る経路上の記憶保持手段の比較判定と更新を行う２分木更新手段と、
前記符号量記憶手段に累積される符号量が前記目標符号量に到達したか否かを判断し、未到達であると判断した場合には、前記末端ノード更新手段及び前記２分木更新手段を繰り返す判断手段と、
該判断手段で前記符号量記憶手段に累積される符号量が予め設定した目標符号量に到達したと判断した際の、最上位のノード位置の記憶保持手段に記憶保持された比較要素情報のレート・歪み勾配情報に基づいて、最終的なレート・歪み勾配情報λを求め、当該レート・歪み勾配λに基づいて、前記第１の記憶手段に記憶された該当するパス段階での符号化データを読出し、圧縮符号化データとして出力することを特徴とする画像データ符号化装置。
【請求項２】
前記処理手段における、前記２分木構造の末端に位置する複数のノードの記憶保持手段に設定する比較要素情報におけるレート・歪み勾配情報は、各ブロックの最上位のパス段階でのレート・歪み勾配情報であり、
前記符号量記憶手段には初期状態として０を設定し、
前記処理手段及び２分木更新手段では、２つの子ノードの比較要素情報中のレート・歪み勾配情報の大きい方を選択して親ノードの記憶保持手段に記憶保持する処理を行うことを特徴とする請求項１に記載の画像データ符号化装置。
【請求項３】
前記最終的なレート・歪み勾配情報λは、前記判断手段で前記符号量記憶手段に累積される符号量が予め設定した目標符号量に到達したと判断する際の直前２分木更新手段における最上位のノード位置の記憶保持手段に記憶保持された比較要素情報のレート・歪み勾配情報とすることを特徴とする請求項１又は２に記載の画像データ符号化装置。
【請求項４】
前記処理手段における、前記２分木構造の末端に位置する複数のノードの記憶保持手段に設定する比較要素情報におけるレート・歪み勾配情報は、各ブロックの最下位のパス段階でのレート・歪み勾配情報であり、
前記符号量記憶手段には初期状態として前記第１の記憶手段に記憶された総符号データ量を設定し、
前記処理手段及び２分木更新手段では、２つの子ノードの比較要素情報中のレート・歪み勾配情報の小さい方を選択して親ノードの記憶保持手段に記憶保持する処理を行い、
前記処理手段及び前記２分木更新手段では、最上位のノード位置のレート・歪み勾配情報で示されるパス段階での符号化データ量を負の値にして前記符号量記憶手段に加算することを特徴とする請求項１に記載の画像データ符号化装置。
【請求項５】
前記２分木構造は、トーナメント構造であることを特徴とする請求項１乃至４のいずれか１項に記載の画像データ符号化装置。
【請求項６】
画像データを帯域分割し、帯域分割後のデータを所定サイズの複数のブロックに分割し、分割したブロック内の各係数値のビット情報を上位から下位に向かうパス順に符号化データを生成し、各ブロックの上位から下位に向かうどのパス位置までの符号化データを用いて圧縮符号化データにするかを、目標符号量と各パス位置における符号データ量の増加量と画像の歪みで表わされるレート・歪み勾配λに基づき決定する画像データ符号化方法であって、
帯域分割したデータの各ブロックについて、各パス段階での符号データを記憶する第１の記憶工程と、
前記各ブロックにおける各パス段階におけるレート・歪み勾配情報を記憶する第２の記憶工程と、
レート・歪み勾配情報及びブロックを特定する属性情報で構成される比較要素情報を、２分木構造の各ノードに相当する位置に記憶するための複数の記憶保持手段で構成し、当該２分木構造の末端に位置する複数のノードの記憶保持手段に、前記第２の記憶工程で記憶された各ブロックの所定パス段階でのレート・歪み勾配情報及びブロックを特定する情報で構成される比較要素情報を設定すると共に、２つの子ノードの記憶保持手段に記憶された比較要素情報中のレート・歪み勾配情報の大小判定することで一方の子ノードの比較要素情報を２つの子ノードに共通する親ノードの記憶保持手段に記憶保持する処理を、末端に位置するノードから順に行う処理工程と、
該処理工程によって最上位のノード位置の記憶保持手段に記憶保持された比較要素情報を注目比較要素情報としたとき、当該注目比較要素情報で特定されたブロックのレート・歪み勾配情報のパス段階での符号データ量を累積加算するための所定の符号量記憶手段に累積加算すると共に、前記注目比較要素情報のレート・歪み勾配情報のパス段階を次のパス段階のレート歪み勾配情報に変更し、当該変更した注目比較要素情報の比較要素情報で、変更前の注目比較要素情報を記憶していた末端のノード位置の記憶保持手段を更新する末端ノード更新工程と、
該末端ノード更新工程で更新された記憶保持手段の、親ノードから最上位のノードに至る経路上の記憶保持手段の比較判定と更新を行う２分木更新工程と、
前記符号量記憶手段に累積される符号量が前記目標符号量に到達したか否かを判断し、未到達であると判断した場合には、前記末端ノード更新工程及び前記２分木更新工程を繰り返す判断工程と、
該判断工程で前記符号量記憶手段に累積される符号量が予め設定した目標符号量に到達したと判断した際の、最上位のノード位置の記憶保持手段に記憶保持された比較要素情報のレート・歪み勾配情報に基づいて、最終的なレート・歪み勾配情報λを求め、当該レート・歪み勾配λに基づいて、前記第１の記憶工程で記憶された該当するパス段階での符号化データを読出し、圧縮符号化データとして出力することを特徴とする画像データ符号化方法。
【請求項７】
画像データを帯域分割し、帯域分割後のデータを所定サイズの複数のブロックに分割し、分割したブロック内の各係数値のビット情報を上位から下位に向かうパス順に符号化データを生成し、各ブロックの上位から下位に向かうどのパス位置までの符号化データを用いて圧縮符号化データにするかを、目標符号量と各パス位置における符号データ量の増加量と画像の歪みで表わされるレート・歪み勾配λに基づき決定する画像データ符号化装置として機能するコンピュータプログラムであって、
帯域分割したデータの各ブロックについて、各パス段階での符号データを記憶する第１の記憶手段と、
前記各ブロックにおける各パス段階におけるレート・歪み勾配情報を記憶する第２の記憶手段と、
レート・歪み勾配情報及びブロックを特定する属性情報で構成される比較要素情報を、２分木構造の各ノードに相当する位置に記憶するための複数の記憶保持手段をメモリに確保する確保手段と、
前記２分木構造の末端に位置する複数のノードの記憶保持手段に、前記第２の記憶手段で記憶された各ブロックの所定パス段階でのレート・歪み勾配情報及びブロックを特定する情報で構成される比較要素情報を設定すると共に、２つの子ノードの記憶保持手段に記憶された比較要素情報中のレート・歪み勾配情報の大小判定することで一方の子ノードの比較要素情報を２つの子ノードに共通する親ノードの記憶保持手段に記憶保持する処理を、末端に位置するノードから順に行う処理手段と、
該処理手段によって最上位のノード位置の記憶保持手段に記憶保持された比較要素情報を注目比較要素情報としたとき、当該注目比較要素情報で特定されたブロックのレート・歪み勾配情報のパス段階での符号データ量を累積加算するための所定の符号量記憶手段に累積加算すると共に、前記注目比較要素情報のレート・歪み勾配情報のパス段階を次のパス段階のレート歪み勾配情報に変更し、当該変更した注目比較要素情報の比較要素情報で、変更前の注目比較要素情報を記憶していた末端のノード位置の記憶保持手段を更新する末端ノード更新手段と、
該末端ノード更新手段で更新された記憶保持手段の、親ノードから最上位のノードに至る経路上の記憶保持手段の比較判定と更新を行う２分木更新手段と、
前記符号量記憶手段に累積される符号量が前記目標符号量に到達したか否かを判断し、未到達であると判断した場合には、前記末端ノード更新工程及び前記２分木更新手段を繰り返す判断手段と、
該判断手段で前記符号量記憶手段に累積される符号量が予め設定した目標符号量に到達したと判断した際の、最上位のノード位置の記憶保持手段に記憶保持された比較要素情報のレート・歪み勾配情報に基づいて、最終的なレート・歪み勾配情報λを求め、当該レート・歪み勾配λに基づいて、前記第１の記憶手段に記憶された該当するパス段階での符号化データを読出し、圧縮符号化データとして出力する
として機能することを特徴とするコンピュータプログラム。
【請求項８】
請求項７に記載のコンピュータプログラムを格納することを特徴とするコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、静止画像または動画像のフレームデータを符号化する画像符号化装置、及び方法、及びこの方法を実現するプログラム、及びこのプログラムを記憶する記憶媒体に関するものである。
【背景技術】
【０００２】
画像符号化の効率を向上させる手法の一つとしてレート・歪み最適化手法がある。レート・歪み最適化手法は符号化データを構成する複数の区分ごとに発生符号量と画像の歪みに関する指標値を求め、総符号量が目標値以下という条件の基で総歪み指標値の最小化を図るものである。
【０００３】
ＩＳＯ／ＩＥＣ  ＪＴＣ１／ＳＣ２９／ＷＧ１での標準化作業により制定された静止画像符号化の国際標準である通称ＪＰＥＧ２０００（ＩＳＯ／ＩＥＣ  １５４４４）では、ウェーブレット変換により得られる各サブバンドの係数をコードブロックと呼ばれる矩形領域に分割してそれぞれ独立に符号化するという構成となっている。そして、各コードブロックを何回かに分けて（何回かのパスに分けて）符号化しており、パスを単位として発生符号量と画像の歪み指標値を求めてレート・歪み最適化手法を適用することが考慮されている。ＪＰＥＧ２０００標準を実施する上での上記レート・歪み最適化手法の一適用方法がある（非特許文献１）。
【０００４】
コードブロック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を得ることが保証されるものでもない、という問題点がある。
【００４１】
本発明は、このような事情を考慮してなされたものであり、より単純な演算で、目標符号量となる最適なレート・歪み勾配を決定し、圧縮符号化画像データを生成する技術を提供しようとするものである。
【課題を解決するための手段】
【００４２】
この課題を解決するため、例えば本発明の画像データ符号化装置は以下の構成を備える。すなわち、
画像データを帯域分割し、帯域分割後のデータを所定サイズの複数のブロックに分割し、分割したブロック内の各係数値のビット情報を上位から下位に向かうパス順に符号化データを生成し、各ブロックの上位から下位に向かうどのパス位置までの符号化データを用いて圧縮符号化データにするかを、目標符号量と各パス位置における符号データ量の増加量と画像の歪みで表わされるレート・歪み勾配λに基づき決定する画像データ符号化装置であって、
帯域分割したデータの各ブロックについて、各パス段階での符号データを記憶する第１の記憶手段と、
前記各ブロックにおける各パス段階におけるレート・歪み勾配情報を記憶する第２の記憶手段と、
レート・歪み勾配情報及びブロックを特定する属性情報で構成される比較要素情報を、２分木構造の各ノードに相当する位置に記憶するための複数の記憶保持手段と、
前記２分木構造の末端に位置する複数のノードの記憶保持手段に、前記第２の記憶手段に記憶された各ブロックの所定パス段階でのレート・歪み勾配情報及びブロックを特定する情報で構成される比較要素情報を設定すると共に、２つの子ノードの記憶保持手段に記憶された比較要素情報中のレート・歪み勾配情報の大小判定することで一方の子ノードの比較要素情報を該２つの子ノードに対する親ノードの記憶保持手段に記憶保持する処理を、末端に位置するノードから順に行う処理手段と、
該処理手段によって最上位のノード位置の記憶保持手段に記憶保持された比較要素情報を注目比較要素情報としたとき、当該注目比較要素情報で特定されたブロックのレート・歪み勾配情報のパス段階での符号データ量を累積加算するための所定の符号量記憶手段に累積加算すると共に、前記注目比較要素情報のレート・歪み勾配情報のパス段階を次のパス段階のレート歪み勾配情報に変更し、当該変更した注目比較要素情報の比較要素情報で、変更前の注目比較要素情報を記憶していた末端のノード位置の記憶保持手段を更新する末端ノード更新手段と、
該末端ノード更新手段で更新された記憶保持手段の、親ノードから最上位のノードに至る経路上の記憶保持手段の比較判定と更新を行う２分木更新手段と、
前記符号量記憶手段に累積される符号量が前記目標符号量に到達したか否かを判断し、未到達であると判断した場合には、前記末端ノードの更新及び前記２分木の更新を繰り返す判断手段と、
該判断手段で前記符号量記憶手段に累積される符号量が予め設定した目標符号量に到達したと判断した際の、最上位のノード位置の記憶保持手段に記憶保持された比較要素情報のレート・歪み勾配情報に基づいて、最終的なレート・歪み勾配情報λを求め、当該レート・歪み勾配λに基づいて、前記第１の記憶手段に記憶された該当するパス段階での符号化データを読出し、圧縮符号化データとして出力することを特徴とする。
【発明の効果】
【００４３】
本発明によれば、画像符号化におけるレート・歪み勾配が簡単な処理で効率良く求められ、目標符号量の圧縮符号化した画像データを得ることが可能になる。
【発明を実施するための最良の形態】
【００４４】
以下、添付図面に従って本発明にかかる実施形態を詳細に説明する。
【００４５】
＜第１の実施形態＞
図１は実施形態における画像符号化処理装置のブロック構成図である。
【００４６】
図２と異なる点は、コードブロック情報格納部２０７をアクセスし、後述するノード処理を行うノード処理部２０９を設け、符号列形成部２０５はノード処理部２０９で処理結果に基づいて符号列格納部２０５より該当する各コードブロックのパス位置における符号列を読出し、出力符号化データを生成する点にある。それ以外は先に説明した内容と同様であるものとし、本実施形態の特徴部分について説明する。
【００４７】
図１に示した装置全体の処理は、図１９に示す手順に従って処理される。
【００４８】
図１９において、ステップＳ１００にて画像データを入力する。この画像データの入力は例えばイメージスキャナであるが、画像データを記憶した記憶媒体から画像データを読取る構成でも勿論構わないし、ネットワークインタフェースを介して画像データを入力しても勿論構わない。
【００４９】
次いで、ステップＳ１０１にて入力した画像データに対して離散ウェーブレット変換処理を行い、ステップＳ１０２にて変換結果の各係数の量子化処理を行う。そして、量子化結果を今度はコードブロックに分割し（ステップＳ１０３）、各コードブロック符号化処理を行う。このとき、各コードブロックをビットプレーンに分割し、なおかつ、最上位ビットプレーンを除くビットプレーンについては３つのパスに分け、最上位のパスから順に符号データ列を生成する（ステップＳ１０４）。次に、ステップＳ１０５において、各パス毎の符号化データを所定の記憶手段に格納すると共に、ステップＳ１０６において各コードブロック毎に、各パスにおける符号増加量と歪み量とを関連付けてコードブロック情報（図８参照）として所定の記憶手段に格納する。
【００５０】
次に、本実施形態における特徴部分である、２分木であるトーナメント・ツリー生成処理を行い（ステップＳ１０７）、そのトーナメント・ツリーの更新処理を繰り返し処理する（ステップＳ１０８）。この結果、目標符号量Rmaxに対応するレート・歪み勾配λが求められるので、ステップＳ１０９にて、先に格納した各コードブロック中の該当するλまでの符号化データ列を取り出し、最終的な画像全体の符号化データ列を生成し、ステップＳ１１０にて生成された符号化コード列を出力する。
【００５１】
上記処理中、本実施形態における特徴的な処理は、ステップＳ１０７、Ｓ１０８である。そこで、以下では、かかる点を中心に説明することとする。
【００５２】
説明簡略化のため、符号化対象とする画像符号化データは、前述の従来例と同じく、５１２×５１２の各画素８ビットのモノクロ画像データとする。また、タイル分割の無（１タイル＝５１２×５１２画素）、コードブロックのサイズは６４×６４、９×７タップのウェーブレット変換フィルタを用いて２回ウェーブレット変換する場合とする。
【００５３】
本実施形態の符号化処理では、レート・歪み最適化に関する処理量が、設定符号量に対してほぼ一定の演算量となるようにする。
【００５４】
先ず、実施形態における概要を説明すると、レート・歪み勾配のコードブロック間の大小比較をトーナメント形式で行ないそれらの大小関係を保持するトーナメント・ツリー情報を生成する。そして、このトーナメント・ツリー情報を更新しながら符号列として形成される符号量を累計し、該符号量が設定符号量に達するまで、ツリー情報を更新するものである。
【００５５】
本実施形態で行なう特徴的な処理は、以下の３つである。
（１）トーナメント・ツリーの生成
（２）トーナメント・ツリーの更新
（３）符号列の形成
その他の処理は、公知の内容か従来の技術で説明した処理方法と同じである。以下、上記３つについて詳しく説明する。
【００５６】
（１）トーナメント・ツリーの生成処理
まず、２分木構造の１つである一般的なトーナメント表を図１２に示す。この例では、７人（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ）の対決者が２人づつ互いの持ち点の大小を競い合い、もっとも高い持ち点の人が頂点に立つ例を示している。各人の持ち点は順に７，４，２，９，１，８，６とする。説明するまでもなく、最高の持ち点９を有するＤが頂点にくる。
【００５７】
このグラフの関係をそのままツリー情報として持つと、図１３のようになる。長方形の左上の外側の数字はツリーのノード番号を表わし、長方形の中の数字と次のアルファベットは、持ち点と人を表わしている。持ち点は“キー情報”、人は“属性情報”と一般的に呼ばれている。キー情報はノード間のデータの比較に用いられ、該キー情報に付随する情報が属性情報である。本明細書中では、図１３のツリー情報をトーナメント・ツリーと呼ぶことにする。
【００５８】
このようなツリー構造は冗長性が高く一般的ではないが、本実施形態では非常に重要な役割を持つ。ちなみに、通常よく見られるのが、ヒープソートに用いられるヒープ・ツリーである。ヒープ・ツリーに較べると、トーナメント・ツリーは約２倍のノード数を必要とするので冗長性を有するが、それが、比較処理の回数を減らすことに繋がり、後述するツリーの更新処理を効率よく行なうことができるようになる。
【００５９】
本実施形態においては、キー情報として各コードブロックの先頭パスのレート・歪み勾配（λ）を用い、属性情報として各コードブロックを一意に識別することが可能なコードブロック番号（ＣＢＮ）を用いる。
【００６０】
最初に行なう、トーナメント・ツリーの生成は、以下のように行なう。但し、コードブロックの数をＭ個（上記の条件ではコードブロックサイズは６４×６４であり、原画像サイズが５１２×５１２であるから、Ｍ＝６４）とする。
【００６１】
工程１．
コードブロック情報から、Ｍ個のコードブロックのレート・歪み勾配（λ）とコードブロック番号（ＣＢＮ）を、ノード番号Ｍ〜２Ｍ−１に格納する。図１３ではデータ数が７つ存在する際、ノード７〜１３に割り当てたので、容易にその処理内容について理解できよう。
工程２．
ｉ＝Ｍ−１
すなわち、変数ｉに初期値として「Ｍ−１」を設定する。
工程３．
ノード番号２ｉと２ｉ＋１のλを比較して、λが大きい方のデータ（λ，ＣＢＮ）をノード番号ｉに格納する。これは、ちょうど、図１３におけるノード１２と１３とを比較して大きい方をノード６に格納する場合に相当する。
工程4．
ｉの値が「１」になるまで、ｉを１ずつ減らしながら上記工程３の処理を行なう。
【００６２】
以上の生成処理で、トーナメント・ツリーが完成しノード番号「１」には最大のλと、対応するコードブロック番号（ＣＢＮ）が格納されることになる。
【００６３】
図１４に、上記トーナメント・ツリー生成処理によって、生成したトーナメント・ツリーの簡単な例を示す。基本的には図１３と同じであるが、図１４におけるノード７乃至１３にセットされるデータは、各コードブロックの先頭パスにおけるλとそのコードブロック番号である点で異なる。なお、既に説明したように、原画像データが５１２×５１２画素で、コードブロックサイズが６４×６４サイズである場合、コードブロックの総数は６４個になる点に注意されたい。
【００６４】
また、図１４では、キー情報と属性情報の両方が数字であるため、属性情報であるコードブロック番号は１〜７の一桁の数字、キー情報であるレート・歪み勾配（λ）は２桁の数字で表現した。トーナメント・ツリー生成後には、λの最大値と対応するコードブロック番号の情報が、ノード番号１に格納される。この図の例ではλ＝４２、コードブロック番号＝４であることを示している。
【００６５】
（２）トーナメント・ツリーの更新
以上のようにして生成したトーナメント・ツリーを次に説明する処理で更新する。
工程１．
ノード番号１からコードブロック番号（ＣＢＮ）を読み出す。
工程２．
工程１で読出したコードブロック番号で示されるコードブロックの現在のパス番号に対応する符号長を総符号量Ｒに加算する。なお、総符号量Ｒは処理開始時に０クリアされている。
工程３．
総符号量Ｒが目標符号量Rmaxを超えていたら、その時点でノード番号１に格納されている歪み勾配（λ）をλｍとし、本処理を終える。また、総符号量Ｒが目標符号量Rmaxを超えない場合には、工程４に進む。
工程４．
注目コードブロック番号で示されるコードブロックのパス番号を１つ増やす（次のパスに更新する）。
工程５．
注目コードブロック番号に対応したノード番号のλを、更新したパス番号後のλに更新する。ノード番号はj＝Ｍ＋ＣＢＮ (０≦ＣＢＮ≦Ｍ−１)である。
工程６．
ノード番号jと、jを二進表現した時の最下位ビットを反転したノード番号j'のλを比較して、大きい方のデータ（λ，ＣＢＮ）をノード番号「ｉｎｔ（ｊ／２）」に格納し、j＝ｉｎｔ（ｊ／２）とする。なお、ｉｎｔ（ｘ）はｘの小数点を切り捨てする関数である。
【００６６】
これは、図１４を用いて説明すると、同図においてノード番号１に格納されたコード番号は「４」であるから、そのコードブロック４の初期λを格納していたノード番号１０に、新たなパス番号に基づくλを格納することを意味する。また、ノード番号１０に対する比較対象であるノード番号１１は、ノード番号「１０」の二進表現のＬＳＢを反転することで特定できる。ノード番号「１０」を「２」で除算すると「５」になるので、ノード番号５から再演算すれば良いことを意味する（ノード番号３、４、６、７は変化がないため、比較演算は行わなず、その分だけ演算量も減る）。
工程７．
ｊ＝１になるまで上記６．の処理を繰り返し行なう。そして、ｊ＝１になったら工程１へ戻る。
【００６７】
以上であるが、１回目の更新、２回目の更新を行なった後のトーナメント・ツリーの状態をそれぞれ、図１５、図１６に示す。
【００６８】
図１４のトーナメント・ツリー生成処理では、データ数がＭ個の場合に２Ｍ−１回の比較処理を行うことで、最大λを有するコードブロックＣＢ４が特定される。そして、その特定されたコードブロックＣＢ４のその時点でのλに対応する符号量が総符号量Ｒに加算される。そして、コードブロックＣＢ４のλ（図示ではλ＝２９）を更新し、図１５に示すように、コードブロックＣＢ４を格納していたノード番号１０の位置に更新後のλを格納する。
【００６９】
この結果、図１５におけるトーナメント・ツリーに着目すると、ノード番号１０のみが変更されたわけであるから、その上位のノード番号５に格納するための比較演算を行い、次いで、ノード番号２、ノード番号１へと必要最小限の比較演算のみを行い、トーナメント・ツリーを更新する。図１５の場合、トーナメント・ツリーの更新後のノード番号１には、コードブロック番号「３」のλが格納されるから、そのコードブロック番号「３」のその時点でのパス番号での符号データ量を総符号量Ｒに累積加算する。そして、コードブロック番号「３」のλを更新し（図示ではλ＝２２）、図１６に示すように、コードブロック番号「３」を格納していたノード番号９の位置に更新後のλを格納する。
【００７０】
図１６では、更新されたのはノード番号９であるので、比較処理は、ノード番号順に示すと、４→２→１の経路に従って処理していけばよい。この結果、ノード番号１には、コードブロック番号６のλが格納されることになる。
【００７１】
これ以降は、上記処理を繰り返し、総符号量Ｒが予め設定した目標符号量Rmaxを越えるまで行う。
【００７２】
（３）符号列の形成
上記処理で得られたレート・歪み勾配（λ）を符号列生成部２０５にセットする。符号列生成部２０５では、セットされたレート・歪み勾配（λ）で示される最大パスの符号データを、符号列格納部２０６より集め、ＪＰＥＧ２０００形式の符号列を形成し、符号出力部２０８へと出力する。
【００７３】
なお、トーナメント・ツリーの更新処理において、Ｒ＞Ｒmaxとなったと判断された場合、最後のトーナメント・ツリー更新処理でのノード番号１に格納されたλｍではなく、その１つ前のトーナメント・ツリー更新処理におけるノード番号１に格納されたλｍを解λとして決定する。これは、Ｒ≦Ｒmaxを満足させるためである。
【００７４】
ただし、ＲがＲmaxを越えても、Ｒmaxの近傍の量になれば良いという条件、すなわち、Ｒ≒Ｒmaxを条件とする場合には、最後のトーナメント・ツリー更新処理でノード番号１に格納されたλｍを最終解とすれば良い。いずれの場合であっても、トーナメント・ツリー更新処理でノード番号１に格納されたλｍに基づいて決定できることになる。
【００７５】
以上説明したように本実施形態によれば、Ｍ個のコードブロックが存在する場合、トーナメント・ツリーを生成する際は全ノード数分の比較処理が必要であるものの、更新処理時には、ｌｏｇＭ回の比較演算で良くなり、レート・歪み勾配λを効率良く算出することが可能となり、これまでと比較して演算量を格段に少なくできる。
【００７６】
上記は図１に示す構成におけるものであったが、汎用の情報処理装置（例えばパーソナルコンピュータ等）で実行する場合の、構成を示すと図２０のようになる。
【００７７】
図中、１は装置全体の制御を司るＣＰＵ、２はブートプログラム及びＢＩＯＳ等を記憶するＲＯＭ、３はＣＰＵ１のワークエリアとして使用されるＲＡＭである。４はハードディスク装置等の外部記憶装置であって、ここにはＯＳ、本実施形態で述べた画像圧縮処理に係るアプリケーションプログラムが格納されている。５は画像入力部であって、例えばイメージスキャナ等であるが、画像データが記憶媒体に記憶されている場合にはその記憶媒体をアクセスする手段、画像データがネットワーク上のサーバに存在する場合にはネットワークインタフェースと見ることもできる。６はキーボード（ＫＢ）やポインティングデバイス（ＰＤ）であり、７はビデオＲＡＭを搭載すると共にそのビデオＲＡＭへの描画処理及びビデオＲＡＭからデータを読出しビデオ信号として出力する表示制御部である。８は表示制御部７よりのビデオ信号に基づき表示する表示装置である。
【００７８】
上記構成において、電源を投入すると、ＣＰＵ１はＲＯＭ２に格納されたブートプログラムに従って外部記憶装置よりＯＳをＲＡＭ３にロードし、しかる後、画像圧縮プログラムをロードすることで、画像入力部５より入力した画像データを、予め設定された目標符号量Rmax、もしくは、それを越えないで近似する符号量の圧縮符号化データを生成し、外部記憶装置に格納することになる。なお、最終的に生成された圧縮符号化画像データの出力先は外部記憶装置に限らず、ネットワークを介して出力しても構わないし、その出力先は問わない。
【００７９】
ここで、上記画像データの圧縮符号化処理プログラムは、先に説明したように、図１９の処理手順にて行われるが、ステップＳ１０６までで生成されたコードブロック格納部、符号列格納部としてのデータは、図２０に示すように、外部記憶装置４に一時的に格納してもよいし、ＲＡＭ上に確保できるのであれば、ＲＡＭ上でも構わない。
【００８０】
そして、本実施形態におけるステップＳ１０７、Ｓ１０８における最適レート・歪み勾配λを求める処理では、コードブロックの数がＭ個存在する場合、トーナメント・ツリーを構成する各ノードに対応する配列変数Ｎ（i）（i=1,2,…,2M-1）をＲＡＭ３に確保することで行えば良い。このとき、この配列変数Ｎ（）は構造体を有し、次のメンバーを有するようにする。
cb:コードブロックの番号
λ：コードブロック番号cbで示される現在のパス位置Pにおけるレート歪み勾配
従って、例えば、N(i).cbとは、ノードｉに格納されているコードブロック番号、N(i).λはノードｉのコードブロックにおける現在のパス位置におけるレート・歪み勾配をそれぞれ示すことになる。
【００８１】
そして、上記配列がＲＡＭ３上に確保されると、トーナメント・ツリーの末端位置に相当するノード、すなわち、配列Ｎ(2M)〜Ｎ（2M-1)に、コードブロック番号１〜Ｍのデータを格納する。このとき、各コードブロックのパス０におけるレート・歪み勾配を格納すれば良い。後は、先に説明した「トーナメント・ツリーの生成フロー」、「トーナメント・ツリーの更新」で説明した「ノード」を「配列Ｎ（）」と見立てて処理すれば良い。
【００８２】
＜第２の実施形態＞
相関のある複数の画像、例えばスチルカメラで連写した画像を連続して符号化する場合、あるいは、同じカメラを用いて同じ場所で撮影した画像は、まったく異なる画像と比べて、似た特徴量になる。従って、或る画像データより求めたレート・歪み勾配λｍを次の画像の符号化に利用することができる。一番簡単な利用方法は、前のフレームのλｍを、次のフレームを符号化する際の初期値λｓとして用いる。
【００８３】
この場合、初期値λｓに対する初期符号量Ｒｓを前述の方法で求め、それから符号量を目標符号量に向けて調整することになる。初期符号量と目標符号量の大小関係により符号量を増やす場合と、逆に減らす場合の２種類の調整処理が考えられる。
【００８４】
符号量を増やす場合は、前記第１の実施形態と同様の方法で行なえばよい。このとき、トーナメント・ツリーを生成する処理では、各コードブロックにはλｓを越える最小値のレート・歪み勾配をセットすれば良い。
【００８５】
ここでは、初期符号量Ｒｓが目標符号量より多い場合、すなわち、符号量を減らす場合のトーナメント・ツリーの生成と更新方法について記述する。
【００８６】
・トーナメント・ツリーの生成
工程１．
Ｍ個のコードブロック毎に、初期値λｓ以下でλｓに最も近いλを有するパス番号を探索する。
工程２．
上記パス番号とコードブロック番号をノード番号Ｍ〜２Ｍ−１に格納する。
工程３．
ノード番号２ｉと２ｉ＋１のλを比較して、λが小さい方のデータ（λ，ＣＢＮ）をノード番号ｉに格納する。
工程４．
ｉの値が１になるまで１ずつ減らしながら上記３の処理を行なう。
【００８７】
・トーナメント・ツリーの更新
トーナメント・ツリーの更新処理は次の通りである。
工程１．
ノード番号１からコードブロック番号（ＣＢＮ）を読み出す。
工程２．
該コードブロック番号の現在のパス番号に対応する符号長を総符号量から減算する。
工程３．
総符号量Rが目標符号量Rmaxを下回っていたら、その時点でノード番号１に格納されている歪み勾配（λ）をλｍとし、本処理を終える。それ以外は、次の工程４に進む。
工程４．
該コードブロック番号のパス番号を１つ減らす。
工程５．
上記コードブロック番号に対応したノード番号のλを、更新したパス番号後のλに更新する。ノード番号はj＝Ｍ＋ＣＢＮ (０≦ＣＢＮ≦Ｍ−１)である。
工程６．
ノード番号jとjの最下位ビットを反転したノード番号j'のλを比較して、小さい方のデータ（λ，ＣＢＮ）をノード番号ｉｎｔ（ｊ／２）に格納し、j＝ｉｎｔ（ｊ／２）とする。
工程７．
ｊ＝１になるまで上記工程６．の処理を繰り返し行ない、ｊ＝１になったら工程１．へ戻る。
【００８８】
以上であるが、本第２の実施形態が第１の実施形態と異なる点は、親ノードを更新する時に、キー情報の値が小さい方の情報で更新するところである。図１３〜図１６に示したトーナメント・ツリーでは、キーの値が大きい方の情報で更新していたのと対照的であるので、図示については省略する。
【００８９】
＜その他の実施形態＞
符号量を減らす場合の一番簡単な処理方法がある。初期値λｓを無限大、またはレンジ内の最大値に設定し、符号化したプレーンのすべての符号を初期符号量Ｒｓに含めてしまい、そこから符号量を減らしていく方法である。トーナメント・ツリー生成におけるパス番号の探索が不要となり、各コードブロックの最後の符号化パス番号からスタートし、このパス番号に対応するλをノードに格納する。トーナメント・ツリーの更新はまったく同じフローでよい。
【００９０】
符号量０からスタートして符号量を増やすより、この方法が有効な場合というのは、全コードブロックの全パスの総符号量が、目標符号量に近く符号量の調整が少ない場合である。
【００９１】
従って、全コードブロックの全パスの総符号量を仮にＲ、目標符号量ＲｍａｘとしたときＲ＞Ｒmaxであって、Ｒ−Ｒmax≦所定閾値、もしくは、Ｒ／Ｒmax＜所定閾値なる関係があるときに、この処理を採用し、そうでなければ先に説明した実施形態の処理を行うようにすれば良い。
【００９２】
また、本発明は、上述した実施形態に限定されるものではない。例えば、上述した第１から第３の実施形態においては、タイル分割なし、離散ウェーブレット変換２回、９×７非可逆フィルタ(9-7 Irreversible Filter)使用、コードブロックサイズは６４×６４、１レイヤでの符号列形成として説明したが、ＪＰＥＧ２０００符号化の条件を変更した場合にも適用できる。例えば、複数のビットレートでレイヤ構成する場合、それぞれのレイヤで目標符号量Ｒｍａｘを設定することにより適用することができる。その他、離散ウェーブレット変換のフィルタ、適用回数等を変更しても構わないことは言うまでもない。
【００９３】
また、本発明はＪＰＥＧ２０００での実施に好適であるが、符号化データを小区分に分け、各小区分内で階層的に、符号量、歪み指標値を得られるその他の符号化方式においても適用することが可能であるので、上記実施形態で限定されるものではない。
【００９４】
また、上述の実施形態ではコードブロック情報格納部、カテゴリ情報格納部、符号列格納部のように目的に応じてブロックを定義しているが、単一の記憶領域を用意して使い分けるような構成としても構わない。
【００９５】
また、上述の実施の形態では、５１２×５１２の各画素８ビットのモノクロ画像データを符号化対象画像として説明したが、その他のサイズ、ビット深度の画像、各画素が複数の色成分で表されたカラー画像など、その他の画像データに適用しても構わない。さらに、動画像の各フレーム、フィールドなどに対して適用しても構わない。
【００９６】
さらにまた、実施形態における処理は、先に説明したようにパーソナルコンピュータ等の汎用情報処理装置で実行するコンピュータプログラムにも適用できる。また、コンピュータプログラムは、通常、ＣＤＲＯＭ等のコンピュータ可読記憶媒体をそのコンピュータにセットし、システムにコピー若しくはインストールを行うことで実行可能となるわけであるから、本発明はかかるコンピュータ可読記憶媒体をも含むのは明らかである。
【図面の簡単な説明】
【００９７】
【図１】実施形態における画像符号化装置のブロック構成図である。
【図２】画像符号化装置の従来例の構成を示すブロック構成図である。
【図３】２次元離散ウェーブレット変換によって処理される符号化対象画像のサブバンドを説明するための図である。
【図４】コードブロックBiの符号打ち切り点niを決定する処理の流れを示すフローチャートである。
【図５】コードブロックBiのパスの統合による単調減少化の処理の流れを示すフローチャートである。
【図６】２回の２次元離散ウェーブレット変換によって得られる７つのサブバンドを説明するための図である。
【図７】コードブロック分割部２０３におけるコードブロック分割の様子を示す図である。
【図８】コードブロック符号化部２０４の内部に構築されるコードブロックBiの情報の例を示す図である。
【図９】コードブロック情報格納部２０７に格納される符号打ち切り候補点の情報を表す図である。
【図１０】コードブロックの各パスのレートと歪みの関係の一例を示す図である。
【図１１】単調減少化処理により、パスが統合される様子を示す図である。
【図１２】トーナメント・ツリーの基になるトーナメント表を示す図である。
【図１３】図１２をトーナメント・ツリーのノードで表現した図である。
【図１４】第１の実施形態におけるトーナメント・ツリー生成直後の状態を表わした図である。
【図１５】１回目の更新を行なった後のトーナメント・ツリーの状態を表わした図である。
【図１６】２回目の更新を行なった後のトーナメント・ツリーの状態を表わした図である。
【図１７】コードブロックの各ビットプレーンと、符号化のパスとの関係を示す図である。
【図１８】従来の符号列形成部２０５におけるλ決定の処理の流れを示すフローチャートである。
【図１９】実施形態における画データ圧縮処理の処理手順を示すフローチャートである。
【図２０】実施形態における画像圧縮処理をコンピュータプログラムにより実現する際の装置の構成例を示す図である。
【図１】
2005150843.tif 000003
【図２】
2005150843.tif 000004
【図３】
2005150843.tif 000005
【図４】
2005150843.tif 000006
【図５】
2005150843.tif 000007
【図６】
2005150843.tif 000008
【図７】
2005150843.tif 000009
【図８】
2005150843.tif 000010
【図９】
2005150843.tif 000011
【図１０】
2005150843.tif 000012
【図１１】
2005150843.tif 000013
【図１２】
2005150843.tif 000014
【図１３】
2005150843.tif 000015
【図１４】
2005150843.tif 000016
【図１５】
2005150843.tif 000017
【図１６】
2005150843.tif 000018
【図１７】
2005150843.tif 000019
【図１８】
2005150843.tif 000020
【図１９】
2005150843.tif 000021
【図２０】
2005150843.tif 000022