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