(57)【特許請求の範囲】
【請求項１】
入力された画像データを一連のサブセットとして圧縮するデータ圧縮装置において、
上記画像データが、以前に圧縮／伸長サイクルを経験したことがないソース画像データか、又は以前に上記圧縮／伸長サイクルを経験したことがある非ソース画像データかを検出するソース検出部と、
上記ソース検出部に応答して、上記画像データを圧縮するために、該画像データがソース画像データである場合、第１の所望の出力データ量を表す第１の値を該ソース画像データに設定し、該画像データが非ソース画像データである場合、上記第１の所望の出力データ量よりも大きい第２の所望の出力データ量を表す第２の値を該非ソース画像データに設定するデータ量発生器と、
全体として上記各所望の出力データ量となる個々のターゲットデータ量を、上記データ量発生器によって設定された上記各所望の出力データ量に基づいて、上記画像データの各サブセットに割り当てるターゲット割当器と、
上記画像データの各サブセットについて少なくとも１つの量子化の程度を試して、該量子化の程度を用いて発生するデータ量を試験する１つ以上の試し量子化器と、上記試し量子化器の結果に基づいて、各サブセットについての上記ターゲットデータ量を超えないように、上記画像データの圧縮に用いる量子化の程度を選択する選択器と、上記画像データの各サブセットを、上記選択されたそれぞれの量子化の程度に基づいて量子化する量子化器とを有し、上記画像データの各サブセットを上記個々のターゲットデータ量に基づいて圧縮するデータ圧縮部と、
上記ターゲットデータ量を超えない最も粗さの小さな試し量子化の程度及び１つ以上のより粗い量子化の程度において、上記画像データの各サブセットを量子化する少なくとも１つの逆戻り量子化器を有する逆戻り探索部と、
上記逆戻り量子化器によって実行される上記各量子化の程度での量子化により発生する量子化誤差を算出する少なくとも１つの誤差算出器とを備え、
上記データ圧縮部の上記選択器は、上記画像データのサブセットの圧縮に使用する量子化の程度として、上記逆戻り量子化器による量子化で発生する量子化誤差が最小となる上記誤差算出器が決定した量子化の程度を選択することを特徴とするデータ圧縮装置。
【請求項２】
上記誤差算出器は、複数の離散コサイン変換係数に対する残差誤差を累算して、上記量子化誤差を算出することを特徴とする請求項１記載のデータ圧縮装置。
【請求項３】
上記誤差算出器は、
上記逆戻り探索量子化器によって量子化されたデータを逆量子化する少なくとも１つの逆量子化器と、
上記逆量子化したデータを対応する量子化前のデータと比較して、上記量子化誤差を検出する比較器とを備えることを特徴とする請求項１記載のデータ圧縮装置。
【請求項４】
上記第１の所望の出力データ量に対応する上記第１の値は、上記第２の所望の出力データ量に対応する上記第２の値より約５％少ないことを特徴とする請求項１乃至３のいずれか１項記載のデータ圧縮装置。
【請求項５】
入力された画像データを一連のサブセットとして圧縮するデータ圧縮方法において、
上記画像データが、以前に圧縮／伸長サイクルを経験したことがないソース画像データか、又は以前に圧縮／伸長サイクルを経験したことがある非ソース画像データかを検出するステップと、
上記画像データを圧縮するために、該画像データがソース画像データの場合、第１の所望の出力データ量を表す第１の値を該ソース画像データに設定し、該画像データが非ソース画像データの場合、上記第１の所望の出力データ量よりも大きい第２の所望の出力データ量を表す第２の値を該非ソース画像データに設定するステップと、
全体として上記各所望の出力データ量となる個々のターゲットデータ量を、上記データ量発生器によって設定された上記各所望の出力データ量に基づいて、上記画像データの各サブセットに割り当てるステップと、
上記画像データの各サブセットについて少なくとも１つの量子化の程度を試して、該量子化の程度を用いて発生するデータ量を試験するステップと、
上記ターゲットデータ量を超えない最も粗さの小さな試し量子化の程度及び１つ以上のより粗い量子化の程度において、上記画像データの各サブセットを量子化する逆戻り量子化を実行するステップと、
上記逆戻り量子化において実行される上記各量子化の程度での量子化により発生する量子化誤差を算出するステップと、
上記逆戻り量子化において発生する量子化誤差が最小となる量子化の程度を、上記画像データのサブセットの圧縮に使用する量子化の程度として選択するステップと、
上記選択されたそれぞれの量子化の程度に基づいて上記画像データの各サブセットを量子化することにより、上記画像データの各サブセットを上記個々のターゲットデータ量に基づいて圧縮するステップとを有するデータ圧縮方法。
【請求項６】
コンピュータに、請求項５記載のデータ圧縮方法における各ステップを実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデータ圧縮に関する。
【０００２】
【従来の技術】
データ圧縮技術は、制限された帯域幅内で動的に変化する通信チャンネルによってサポートされているビットレートでデータ通信を行うために、データ通信分野で広く採用されている。代表的には、画像データは、伝送又は適当な記憶媒体に蓄積する前に圧縮され、画像の再生に先立ち伸長される。
【０００３】
データ圧縮技術は、静止画像の場合は空間的な冗長度を利用し、動画像の場合は空間及び時間の双方の冗長度を利用する。時間的冗長度は、動画像において時系列における連続した画像、特に同一シーンに属する画像が非常に類似している場合に発生する。モーションピクチャーエキスパーツグループ（Motion Picture Experts group：以下、ＭＰＥＧという。）は、娯楽及び放送の用途におけるビデオ圧縮符号化の国際的標準を規定している。本発明は、低いデータ圧縮率を用いて非常に高いデータレート（１Ｇｂｉｔ／ｓまで）で動作するハイエンドのビデオハードウェアに対するＭＰＥＧ４「スタジオプロファイル」規格の実現に関する（なお、本発明は、これに限定されるものではない）。
【０００４】
離散コサイン変換（Discreet Cosine Transform：以下、ＤＣＴという）の量子化は、ビデオデータの符号化技術で広く用いられている。ＤＣＴの量子化は、データの伝送又は蓄積に先立ち、入力画像データを表すのに必要なデータのワード長を低減する画像圧縮において使用される。ＤＣＴの量子化処理において、画像は、規則的なサイズの画素値のブロックに分割され、殆どの場合、各ブロックは、横８画素、縦８画素（８Ｈ×８Ｖ）で構成される。従来のデータフォーマットにおいて、ビデオデータは、通常、カラー画像における赤、緑、青（ＲＧＢ）成分、あるいは輝度成分Ｙと２つの色差成分Ｃb、Ｃrに対応する３つの成分を有する。全ての３つのＲＧＢ又はＹＣbＣr信号成分に対応する画素ブロックのグループはマクロブロック（ＭＢ）と呼ばれる。
【０００５】
ＤＣＴは、画像の空間領域から空間周波数領域への変換を表し、画素値のブロックを同一次元を有する変換係数のブロックに有効に変換する。ＤＣＴ係数は、画像ブロックの空間周波数成分を表す。各係数は、適当な基底関数に適用される重みとみなすことができ、基底関数の重み付け和が入力画像を完全に表現している。ＤＣＴ係数の各８Ｈ×８Ｖブロックは、ゼロ空間周波数を表す１個の「ＤＣ」成分と６３個の「ＡＣ」成分からなる。ＤＣＴ係数の最大値は、殆どの場合、低い空間周波数のＤＣＴ係数に対応している。画像にＤＣＴを施すだけでは、必ずしも圧縮することはできず、単に画像データを空間領域から空間周波数領域に変換するだけである。圧縮を達成するためには、各ＤＣＴ係数は量子化除数（quantisation divisor）と呼ばれる正の整数で除算され、商は一番近い整数に切り上げ又は切り捨てすることにより丸められる。量子化除数を大きくすることにより、データをより圧縮することができるが、その代償として量子化が粗くなる。量子化を粗くするほど、再生画像の画質がより劣化する。ＤＣＴ係数の切上げ又は切捨てによる丸めの結果として、量子化によるアーティファクトが再生画像に発生する。圧縮画像の再生の際には、各ＤＣＴ係数は量子化ステップによる、当初の商ではなく、（最も近い整数に丸められた整数である）量子化係数を乗算することにより再生されるが、このことはＤＣＴ係数の当初の精度が確保されないことを意味する。したがって、量子化は「有ひずみ（lossy）」符号化技術である。
【０００６】
画像データ圧縮システムでは、殆どの場合、所定の出力ビットレートを達成する最適の量子化除数を決定するために、一連の試し（trial）圧縮を行っている。試し量子化は、例えば、可能な量子化除数の全範囲に亘って分散した２０個の可能な量子化除数で実行される。ターゲットビットレートの直ぐ上と直ぐ下に位置する予測出力ビットレートを与える２つの隣接した試し量子化除数を見つけ、この２つの値間で更に細かな探索を実行する。典型的には、画像圧縮を実行するために選ばれる量子化除数は、ターゲットビットレートを達成しつつ粗さが最小の量子化を与える量子化除数である。
【０００７】
粗さが最小の量子化除数を選択すると、過去に１回以上の圧縮／伸長サイクルを経験したことがない「ソース（source）」画像データに対して、再生の際に最良の画質（すなわちノイズが最少の画像）が得られるが、このことは、「非ソース（non-source）」画像データに対しては必ずしも成立しないことが判明している。圧縮と伸長が１回行われた画像は第１世代の画像と呼ばれ、過去に２回圧縮／伸長サイクルが行れた画像は第２世代と呼ばれ、以下同様に高い世代となる。
【０００８】
第２世代の再生画像では、殆どの場合、第１世代の再生画像の対応する量子化除数でのノイズと比較して、画像ノイズが量子化除数の全範囲で体系的に高くなる。このことは、量子化の各処理（each stage）で生じるＤＣＴ係数の丸め誤差の問題として理解される。しかしながら、第２世代の量子化除数を第１世代の量子化除数と略等しく選んだ場合、第２世代の再生画像のノイズレベルは、第１世代の再生画像のノイズレベルと略等しくなることが知られている。したがって、非ソース入力画像データに対しては、所要のデータレートを満たし、可能な限り最小の大きさを有する量子化除数は、必ずしも再生画像の最良の画質をもたらさない。代わりに、前の圧縮／伸長サイクルで用いられた量子化除数に略等しい量子化除数により、再生画像の最良の画質が得られる可能性が高い。なお、量子化除数の選択は、特定の通信チャンネルの世代毎に変わる可能性があるターゲットビットレートによって制限される。
【０００９】
「最良」の量子化ステップが、所謂多世代（multi-generation）画像に亘って選択されるように保証するために、上述した試し量子化によって見い出された量子化値から開始し、その後はより粗い量子化（大きな値の量子化）除数を用いて更なる検証を行う逆戻り探索（backsearch）を実施する。これらの逆戻り探索における量子化ステップの各々を用いて、データを量子化した後、逆量子化する。代替として、逆量子化の代わりに、量子化器の剰余（residual）から誤差（error）が算出される。逆量子化データと入力画像データを遅延したもの（量子化していないもの）とを比較し、この比較において最も誤差が小さくなる量子化ステップを逆戻り探索して、この量子化ステップを量子化の最終出力処理のために選択する。
【００１０】
【発明が解決しようとする課題】
逆戻り探索処理において、第２世代の画像におけるマクロブロックのターゲットビット数（target bit count）が対応する第１世代画像におけるマクロブロックのターゲットビット数よりも少ない場合に問題が生じる。ターゲットビット数が不一致する結果として、第２世代の画像データは、第１世代の画像データよりも粗く（より大きな量子化除数を用いて）量子化される。図１は、この問題を模式的に説明するための図である。逆戻り探索処理は、量子化除数Q_SCALE＝Q_ALLOCから始まり、ここで、量子化除数Q_ALLOCは、マクロブロックのターゲットビット数に基づきビット割当／２分探索処理（bit allocation/binary search process）により選択されたものである。また、逆戻り探索は、量子化除数Q_ALLOCに対応した量子化よりも粗い一連の、例えば１２個の量子化除数ＱＢ１〜ＱＢ１２を試験する。（これらの試験した中で）再生画像のノイズが最も少なかった量子化除数を、Q_FINALとして決定する。したがって、第１世代の圧縮に対応した量子化除数Ｑ１は、量子化除数Q_ALLOCよりも粗くなく（より小さな量子化除数であり）、再生された第２世代の画像に対して最良の画質を与えるそうな値であるにもかかわらず、後戻り探索では検出されない。
【００１１】
原理上、この問題は、第２世代の逆戻り探索の開始点を、量子化除数Q_ALLOCよりも小さな量子化除数に対応させ、したがって逆戻り探索が量子化除数Ｑ１を確実に含むように調節することにより、解決することができるが、このようにすると、より小さな量子化除数が選択されてしまうことになる。これは、通信システムが処理できないような高いビットレートになりやすい。符号化ビットレートが所定の最大符号化ビットレートを超えると、許容できないデータ消失が起こる可能性がある。
【００１２】
【課題を解決するための手段】
本発明は、データ圧縮装置を提供する。このデータ圧縮装置は、入力データが前に圧縮／伸長サイクルを経験したことがないソースデータか否かを検出するソース検出部と、ソース検出部に応答して、ソース入力データに対しては第１の値であり、非ソース入力データに対してはこの第１の値よりも大きな第２の値である所望の出力データ量を圧縮データに設定するデータ量発生器と、全体として所望の出力データ量となる個々のターゲットデータ量を所望の出力データ量に基づいて、力データの各サブセットに割り当てるターゲット割当器と、入力データの各サブセットを個々のターゲットデータ量に基づいて圧縮するデータ圧縮部とを備える。
【００１３】
本発明は、前に圧縮及び伸長されたことがないデータに対しては所望のデータ量をより低いレベルのデータ量に設定することにより、上述した問題を解決する。データ量の違いは十分に小さく（例えば５％）することができ、それ自体は顕著ではないが、後の世代の圧縮処理において、第１世代で用いたのと同程度の量子化を達成する余裕（headroom）が得られる。これにより、後の世代のエラーレートを低減することができる。
【００１４】
【発明の実施の形態】
図２は、データ圧縮システムの構成を模式的に示す図である。このデータ圧縮システムは、符号化装置（encoder）１０と、データ処理装置（data processing module）２０と、復号装置（decoder）３０とを備える。入力の高品位（high difinition）ビデオ信号５は、符号化装置１０に供給される。符号化装置１０は、冗長度を除去し、その統計的性質を利用するためにビデオ画像データをモデル化し、入力画像データ５の情報を圧縮フォーマットで表現する出力データシンボルを生成する。符号化装置１０は、圧縮データ信号１５Ａを出力し、この圧縮データ信号１５Ａはデータ処理装置２０に供給され、そこで、通信チャンネルを介して伝送されるか、又は記録媒体に格納される。記録媒体から読み出された、又は通信チャンネルを介して受信された圧縮データ信号１５Ｂは、復号装置３０に供給され、復号装置３０は、圧縮データ信号１５Ｂを復号して高品位の出力画像信号３５を形成する。
【００１５】
図３は、図２のビットレートを低減する符号化装置１０の具体的な構成を示すブロック図である。高品位ビデオのフレームにおける入力ＲＧＢチャンネルに対応するデータ信号Ｄ１、Ｄ２、Ｄ３は、シャッフル部（shuffle unit）１００に供給される。他の具体例として、データは、ＹＣbＣrフォーマットで供給することもできる。更に、画像は、プログレッシブフレームモードとインタレースフィールドモードのいずれでも処理することができる。シャッフル部１００は、入力データをマクロブロックユニット（Macro-Block Unit：以下、ＭＢＵという）に分割する。この具体例では、１フレームは４０個のＭＢＵからなり、各ＭＢＵは２０４個のＭＢからなる。各入力フレームの画像サンプルは、外部ＳＤＲＡＭ２００に一時的に書き込まれる。このシャッフル書込処理中に、後続の符号化処理で必要とされる２つの量子化除数パラメータQ_START、DCT_PRECISIONの値が算出される。画素ブロックが外部ＳＤＲＡＭ２００から、入力画像フレーム内の隣接した画素ブロックがシャッフル順序では隣接した位置で読み出されないように画像データをインタリーブする所定のシャッフル順序に従って、読み出される。
【００１６】
シャッフル処理により、復号装置３０によって再生される画像におけるデータ消失の影響が軽減される。入力ビデオフレームにおいて隣接した画素ブロックは、シャッフルされたビットストリームでは、離れている。短時間のデータ消失により、ビットストリームの連続した一部が損なわれ、幾つかのデータブロックが影響を受けるが、これらのブロックは、再生画像内では連続していない。この場合、データ隠蔽（concealment）を適切に用いて、消失したブロックを再構成することができる。更に、シャッフル処理は、入力ビデオデータをＭＢＵに疑似ランダム的に分配することによって画像フレームの各ＭＢＵに選択された量子化パラメータの変化の度合い（variation）を低減することができ、可変速再生（suttle playback）時の画質が改善される。
【００１７】
現画像フレームは、外部ＳＤＲＡＭ２００から前フレームをシャッフルされたフォーマットで読み出している間に、外部ＳＤＲＡＭ２００に書き込まれる。シャッフル部１００は、２対の出力信号を生成し、第１の信号対は、信号S_OP_D1と信号S_OP_D2からなり、第２の信号対は、同じＭＢＵデータを含むが、第１の信号対に対して約１ＭＢＵ遅延された信号S_OP_DD1と信号S_OP_DD2からなる。この遅延は、Ｑ割当部（Q allocation unit）３００に内蔵されているビット割当器（bit allocation module）４００の処理による遅延を補償するためのものである。Q割当部３００は、第１の信号対S_OP_D1、S_OP_D2を用いて、適切な符号化モードと、ＭＢＵの各ＭＢに対するQ_SCALEパラメータと呼ばれる量子化除数を測定する（determine）。
【００１８】
シャッフル部１００から出力される信号は、Q割当部３００に供給され、このQ割当部３００は、ビット割当器４００と、ターゲット挿入器５００と、ＤＣＴ変換器６００と、２分探索（binary search module）器７００とを備える。シャッフル部１００から出力される第１の信号対S_OP_D1、S_OP_D2は、ビット割当器４００に入力される。これらの入力信号は、ラスタ走査された１２ビットビデオサンプルの８Ｈ×８Ｖ縦ブロックからなる。
【００１９】
ビット割当器４００は、無ひずみ（lossless）の差分パルス符号変調（differential pulse code modulation：以下、ＤＰＣＭという）符号化とＤＣＴ量子化符号化を比較する。
【００２０】
ＤＰＣＭは、画像内の空間的に近い画素は相関が高いことを利用した簡単な画像圧縮技術である。ＤＰＣＭでは、画素値自体は伝送されない。代わりに、符号化装置により、前に送信した画素値に基づいた画素の期待値が予測される。１回のＤＰＣＭ符号化処理（single DPCM encoding stage）は、ＤＰＣＭリフォーマットと、ＤＰＣＭ変換と、エントロピー符号化計算を含む。
【００２１】
これに対し、ＤＣＴ量子化符号化の処理は、１回のＤＣＴ変換と、一連の量子化除数を用いた複数回の量子化処理を含み、各量子化処理の後にハフマン（Huffman）エントロピー符号化計算が行われる。この具体例では、６個の試し（trial）量子化除数がビット割当器４００により試験される。ハフマン符号化は、既知の無ひずみ圧縮技術であり、出現頻度の高い値は短い符号で、出現頻度の低い値は長い符号で表現される。ＤＣＴ試し符号化処理は、オプションとして、画像領域の「アクティビティ（activity）」に依存した量子化を含む。アクティビティは、画像ブロックの適切に正規化された画素の分散（variance）から算出される尺度（measure）である。高いアクティビティを有する画像ブロックでは、量子化をより粗くしても、見る人には知覚されにくいことが知られているので、各ブロックの量子化ステップを、アクティビティのレベルに応じて適切に調整することができる。アクティビティを考慮することにより、再生画像の知覚的な画質を維持したまま、圧縮率をより高めることができる。
【００２２】
ＤＰＣＭ及びＤＣＴ量子化の試し符号処理により、所要の符号化ビットレートに基づいた所定のフレームのターゲットビット数によって制限されるＭＢのターゲットビット数を計算する。各ＭＢに対して最少の符号化ビットが得られるモード（ＤＣＴかＤＰＣＭ）が選択される。ビット割当器４００は、信号４０５をターゲット挿入器５００に出力する。この信号４０５は、各マクロブロックに対して選択された符号化モードと、２分探索器７００で使用される量子化除数Q_SCALEの値Q_BASEと、各マクロブロックに対するターゲットビット数（bit count traget）とに関する情報を含んでいる。信号４０５に含まれる情報は、ターゲット挿入器５００によって、対応する遅延された画像データのビットストリームに付加される。ターゲット挿入器５００は、２つの信号５０５Ａ、５０５Ｂを出力し、これらの信号はＤＣＴ変換器６００に入力として供給される。
【００２３】
ＤＣＴ変換器６００で再びＤＣＴ係数を計算するが、今回は画像データの遅延バージョンに基づき計算を行う。ＤＣＴ変換器６００は、データを２分探索器７００に出力する。２分探索器７００は、ＤＣＴ量子化符号化すべき各ＭＢに対して２回目の（second stage）Ｑ割当を実行するとともに、２分探索法を用いて、各マクロブロックに対して適切な量子化除数を測定する。２分探索器７００は、ビット割当器４００で使用された分解能より高い分解能で（使用可能な量子化除数の範囲内で）量子化除数を測定する。実際には、５回の２分探索における開始点を定めるためにQ_BASEを用いて、ＤＣＴモードの各マクロブロックに対してより高い分解能の量子化ステップQ_ALLOCが選択されるようにする。ＤＰＣＭモードのマクロブロックは、バイパス機能によって２分探索器７００を通過するので、その出力においてデータは変更されてない。
【００２４】
２分探索器７００からの出力は、ＤＣＴモードの各マクロブロックに対する量子化ステップの値Q_ALLOCを含み、逆戻り探索（backsearch）器８００に供給される。逆戻り探索器８００は、各ＭＢに対して選択された値Q_ALLOCが符号化のための「最良」の量子化スケールであることを検査（check）する。上述したように、前に１回以上の符号化／復号化サイクルを経験したことがある画像データについては、所定のターゲットビット数（target bit count）を達成できる最も粗さが小さい量子化が必ずしもそのマクロブロックに対して可能な限り小さい量子化誤差をもたらさない。代わりに、最小の量子化誤差は、前回の符号化／復号化サイクルで使用された量子化除数に略等しい量子化除数を用いることによって達成される可能性が高い。したがって、逆戻り探索器８００は、値Q_ALLOCから始まり、より粗い量子化となる様々な量子化除数に対する量子化誤差を評価する。逆戻り探索器８００は、可能な限り最も小さい量子化誤差を実際に発生する量子化ステップQ_FINALを決定する（determine）。試し量子化はＤＣＴモードのマクロブロックに対してのみ行われ、ＤＰＣＭモードのマクロブロックに対してはバイパス機能が適用される。
【００２５】
逆戻り探索器８００から出力される、選択された量子化ステップQ_FINALと、ＤＣＴ符号化器６００で生成されたＤＣＴブロックは、量子化器９００に供給され、ここで、最終的な量子化が実行される。量子化処理は、以下のようにして行われる。
【００２６】
ＤＣＴモードの符号化では、各８Ｈ×８Ｖブロックの１つのＤＣ係数は、次式に従って量子化される。
【００２７】
Ｑ(DC)＝ＤＣ／(DC_QUANT＊DCT_SCALER)
ここで、ＤＣは量子化前の係数であり、DC_QUANTは、方式（system）によって設定されている量子化ファクタ（quantisation facter）であり、全てのＭＢを量子化するのに用いられる。DC_QUANTは、下記表に示すように、DC_PRECISIONから決定される。
【００２８】
【表１】
0004263517.tif 000002
【００２９】
DC_PRECISIONは、各フレームに対して固定値、好ましくは００に設定されているる。
【００３０】
DCT_SCALERは、量子化除数パラメータDCT_PRECISIONを指数とすることによって決定される量子化ファクタであり、DCT_SCALER＝２ＤＣＴ＿ＰＲＥＣＩＳＩＯＮである。この具体例では、規格（conventin）が用いられ、量子化除数パラメータDCT_PRECISIONは４つの可能な値０、１、２、３を取り、３は最も粗い量子化に対応している。なお、ＭＰＥＧスタジオプロファイル標準規格では、これとは異なり、DCT_PRECISION＝０が最も粗い量子化に対応し、DCT_PRECISION＝３が最小粗さの量子化に対応している。
【００３１】
同様に、ブロックの６３個のＡＣ係数は、次式に従って量子化される。
【００３２】
Ｑ(AC)＝(ＡＣ＊１６)／(Q_MATRIX＊AC_QUANTISE＊DCT_SCALER)
ここで、ＡＣは量子化前の係数であり、Q_MATRIXは、ＤＣＴブロックの各要素に１つ１つが対応した６４個の重みの配列である。AC_QUANTISEは、量子化除数Q_SCALEとNORM_ACTの積である。量子化除数Q_SCALEは、Q_SCALE_TYPEによって定まる線形量子化スケール又は非線形量子化スケールに対応したファクタである。各Q_SCALE_TYPEは、Q_SCALE_CODE(1)〜Q_SCALE_CODE(31)で示される３１個の可能な値からなる。図４の表は、全３１個のQ_SCALE_CODEに対する各Q_SCALE_TYPEに対応した量子化除数Q_SCALEの値を示したものである。上記式において、NORM_ACTは、正規化されたアクティビティファクタであり、「アクティビティオン（activity on）」の場合に０．５〜２．０の範囲にあるが、「アクティビティオフ（activity off）」の場合は１に等しくなる。
【００３３】
AC_QUANTISE＝NORM_ACT＊Q_SCALEとし、除数の一部として組み込まれる前に、最も近い量子化除数Q_SCALE（すなわち、図４の表におけるQ_SCALE_CODEに対応するQ_SCALE）に丸められる。
【００３４】
量子化の結果Ｑ(DC)、Ｑ(AC)は、正規無限丸め（normal infinity rounding）と呼ばれる方法で丸められる。この方法は、０．５より小さい正数を（ゼロに）切り捨て、０．５以上の整数を正の無限大に切り上げ、−０．５より大きな負数をゼロに切り上げ、−０．５以下の負数を負の無限大に切り捨てることにより丸める。
【００３５】
ビット割当器４００、２分探索器７００及び逆戻り探索器８００のそれぞれは、量子化器９００によって実行される量子化処理と同じように、量子化処理を実行する。しかしながら、２分探索器７００及び逆戻り探索器８００では、ファクタNORM_ACTは、常に１に設定される。ビット割当器４００によって実行されるビット割当処理の間のみ、ファクタNORM_ACTは１以外の値を取る。ビット割当中に生成されるＭＢターゲットは、アクティビティを考慮しているので、後段でこれを考慮する必要はない。
【００３６】
量子化器９００から出力される量子化データは、エントロピー符号器１０００に供給され、ここで、無ひずみデータ圧縮が、エントロピー符号化の標準原理に基づき適用される。この具体例では、ハフマン符号化を使用しており、出現頻度の高い値は短い符号で、出現頻度の低い値は長い符号で表現される。
【００３７】
エントロピー符号器１０００の出力は、シャッフル部１００内のパッキング器１５０に供給される。パッキング器１５０は、外部ＳＤＲＡＭ２００と協働して、エントロピー符号化器１０００によって生成された可変長符号化データを固定長の同期ブロック（sync-block）にパックする。同期ブロックは、画像再生の際、独立して再生される最小のデータブロックである。
【００３８】
パッキング機能は、ＳＤＲＡＭ２００の読出及び書込アドレスを操作することによって実現される。各ＭＢＵをＳＤＲＡＭ内の固定パッキング領域（fixed packing space）に割り当て、更にそれを、各ＭＢ用の名目パッキング領域（nominal packing space）に分割する。個々のワード長から算出される又はエントロピー符号化器１０００から直接パッキング器１５０に供給される各ＭＢの全体の長さも記憶する必要がある。符号化装置１０からの出力は、同期ブロック１のデータ出力ＳＢ１、同期ブロック２のデータ出力ＳＢ２からなる。符号化処理で使用した量子化除数の情報も復号装置３０に送られる。
【００３９】
図５は、図２の復号装置の構成を示すブロック図である。復号装置３０は、符号化処理の逆処理を行うものであり、アンシャッフル部２０１０と、アンパック部２０２０と、外部ＳＤＲＡＭ２１００と、エントロピー復号器２２００と、逆量子化器２３００と、逆ＤＣＴ変換器２４００とを備える。同期ブロックのデータ信号ＳＢ１、ＳＢ２は、記録媒体から読み出され、あるいはデータ伝送ネットワークを介して受信されて、アンパック部２０２０に供給され、アンパック部２０２０は、外部ＳＤＲＡＭ２１００の読出及び書込により、アンパッキング機能を実行する。アンパックデータはエントロピー復号器２２００に供給され、エントロピー復号器２２００は、ハフマン符号化の逆処理を実行して量子化係数を再生し、逆量子化器２３００に供給する。逆量子化器２３００は、符号化装置１０から供給された量子化除数に関する情報を用いて、量子化係数に適切な量子化除数を乗算して元のＤＣＴ係数の近似値を得る。この逆量子化処理は、ＤＣＴ係数の元の精度を回復するものではなく、量子化は「有ひずみ（lossy）」圧縮技術である。逆量子化器２３００の出力は、逆ＤＣＴ変換器２４００に供給され、逆ＤＣＴ変換器２４００は、離散コサイン逆変換を用い、周波数領域のＤＣＴ係数の各ブロックを処理して空間領域の画像ブロック情報を再生する。逆ＤＣＴ変換器２４００の出力は、量子化の結果には情報消失があるため、符号化前の画素ブロックと等しくない。最後に、逆ＤＣＴ変換器２４００の出力はアンシャッフル部２０１０に供給され、ここで、データはアンシャッフルされ、符号化前の画像ブロックの順序が再現される。アンシャッフル部２０１０の出力は、３つの色成分ビデオ信号ＲＧＢからなり、これから画像を再生することができる。
【００４０】
図６は、シャッフル部１００内に設けられたDCT_PRECISION検出器（図示せず）によって実行される計算を説明するための図である。DCT_PRECISION検出器は、入力ビデオデータがソースデータか非ソースデータか判定し、非ソースデータの場合、前の符号化／復号化サイクルで使用したDCT_PRECISIONインデックスを検出する。量子化除数パラメータDCT_PRECISIONの値は、ＤＣ係数とＡＣ係数の両方に対する量子化に影響を与える。DC_QUANTの値が既知であるとすると（この具体例では各フレームに対してDC_PRECISIONを固定値００に設定しているので、DC_QUANT＝８である）、ＤＣ丸めの影響を解析することにより、前世代で使用された量子化除数パラメータDCT_PRECISIONの値を検出することができる。DCT_PRECISION検出器は、入力ビデオデータが供給され、このビデオデータのＤＣ量子化の解析を行う。画像フィールド又はフレームの各ＤＣＴブロックについて、６４画素からなるブロックの各画素について６つの最下位ビット（ＬＳＢ）の値の和を求め、各ブロックに対する６ビットの値ＤＣ［５：０］を生成する。特定のＤＣ［５：０］の出現頻度は以下のアルゴリズムに従って求められる。
【００４１】
Ｓ０＝ＤＣ［５：０］の出現回数＝00 0000
Ｓ１＝ＤＣ［５：０］の出現回数＝10 0000
Ｓ２＝ＤＣ［５：０］の出現回数＝x1 0000
Ｓ３＝ＤＣ［５：０］の出現回数＝xx 1000
Ｓ４＝ＤＣ［５：０］の出現回数＝xx x100
ここで、ｘは０か１を表す。実質上、ＤＣ［５：０］のインスタンスの数は、６４で割り切れれば和Ｓ０に対応し、（６４でなく）３２で割り切れれば和Ｓ１に対応し、（３２でなく）１６で割り切れれば和Ｓ２に対応し、（１６でなく）８で割り切れれば和Ｓ３に対応し、（８でなく）４で割り切れればＳ４に対応する。図７は、特定のＤＣ［５：０］値の出現頻度の計算を模式的に示している。
【００４２】
この具体例において、５つの和Ｓ０〜Ｓ４は、全てのビデオ成分からの全ＤＣＴブロックを含んでいる。しかしながら、他の具体例として、和Ｓ０〜Ｓ４を各成分（ＲＧＢ又はＹＣbＣr）について別々に計算して、最終的な量子化除数パラメータDCT_PRECISIONの決定を、例えば多数決を用いて合成してもよい。
【００４３】
和Ｓ０〜Ｓ４を一旦算出したら、４つの所定の閾値ｔｈ１〜ｔｈ４を用いて、前世代で使用した量子化除数パラメータDCT_PRECISIONを検出し、予測値DCT_PREC_DETECTEDを生成する。以下の疑似コードは使用したアルゴリズムを表している。
【００４４】
if(Ｓ０＞ｔｈ１＊Ｓ１)                          DCT_PREC_DETECTED＝３
else if(Ｓ０＋Ｓ１＞ｔｈ２*Ｓ２)                DCT_PREC_DETECTED＝２
else if(Ｓ０＋Ｓ１＋Ｓ２＞ｔｈ３*Ｓ３)          DCT_PREC_DETECTED＝１
else if(Ｓ０＋Ｓ１＋Ｓ２＋Ｓ３＞ｔｈ４＊Ｓ４)   DCT_PREC_DETECTED＝０
else                                            ソースデータ
上述のアルゴリズムは、前世代と現世代の両方においてDC_QUANT＝８（DCT_PRECISION＝００）を想定している。Ｑ(DC)＝ＤＣ／DC_QUANT＊２ＤＣＴ＿ＰＲＥＣ且つDC_QUANT＝８であるので、ＤＣデータについて除数、例えば８を検出したときは、更なる量子化はなく、上述のアルゴリズムにおいてDCT_PREC_DETECTED＝０であることが導かれる。なお、このアルゴリズムは前世代と現世代の双方でDC_QUANTを考慮するように適合化される。
【００４５】
和Ｓ０が閾値ｔｈ１と和Ｓ１の積より大きいときは、ＤＣデータの検出された除数は６４＝８＊２３であり、アルゴリズムは、最も粗い量子化除数パラメータDCT_PRECISIONでの量子化に対応したDCT_PREC_DETECTED＝３と設定する。(Ｓ０＋Ｓ１)の値が閾値ｔｈ２と和Ｓ２の積より大きいときは、ＤＣデータの検出された除数は３２＝８＊２２であり、アルゴリズムはDCT_PREC_DETECTED＝２と設定する。(Ｓ０＋Ｓ１＋Ｓ２)の値が閾値ｔｈ３と和Ｓ３の値の積より大きいときは、ＤＣデータの検出された除数は１６＝８＊２であり、アルゴリズムはDCT_PREC_DETECTED＝１と設定する。最後に、(Ｓ０＋Ｓ１＋Ｓ２＋Ｓ３)の値が閾値ｔｈ４と和Ｓ４の値の積より大きいときは、ＤＣデータの検出除数は８であり、アルゴリズムは、粗さが最小の量子化除数パラメータDCT_PRECISIONでの量子化に対応したDCT_PREC_DETECTED＝０と設定する。この特定の具体例において、閾値はｔｈ１＝ｔｈ２＝ｔｈ３＝１６であり、ｔｈ４＝２である。閾値は試験画像シーケンスに対する計算を実行することにより経験的に求められる。このアルゴリズムは、量子化除数パラメータDCT_PRECISIONの前の値を検出するために、画素値に対する丸め効果の重大性を本質的に定量化している。
【００４６】
DCT_PRECISION検出器は、前に１回以上の符号化／復号化サイクルを経験したことがあるか否かを表す「ソース」／「非ソース」信号を出力し、この信号は、図３のビット割当器４００に入力として供給され、ターゲットビット数の算出に用いられる。
【００４７】
図７は、図２のビット割当器４００の具体的な構成を示すブロック図である。このビット割当器４００は、３つの主要な機能を有し、第１の機能では、各マクロブロック毎に無ひずみＤＣＰＭと有ひずみＤＣＴ符号化という２つの利用可能な選択肢の中から符号化モードを選択し、第２の機能では、システムの所要のターゲットビットレートから算出される対応したマクロブロックユニットに関する同様のターゲットに基づいて、各マクロブロックに対するターゲットビット数MB_TARGETを算出し、第３の機能では、２分探索器７００で実行される２分探索における量子化除数Q_SCALEの開始目盛り（starting scale）となるように定義される値Q_BASEを算出する。２分探索器７００は、量子化除数Q_SCALEの値Q_ALLOCを測定し、これは、開始点の値Q_BASEを得るのに使用したよりも高い分解能で量子化除数Q_SCALEを探索することによって得られる。
【００４８】
シャッフル部１００から出力されるシャッフルされた画像データ信号S_OP_D1、S_OP_D2は、ビット割当器４００に入力として供給される。これらの入力信号は、ラスタ走査された１２ビットのビデオサンプルの８Ｈ×８ＶＤＣＴブロックからなる。パラメータ予測回路により生成される最終的な量子化除数パラメータDCT_PRECISION、Q_STARTの値もビット割当器４００に入力として供給される。ビット割当器４００は、ＤＰＣＭリフォーマット器４１０と、ＤＰＣＭ器４２０と、ゴーロン（Golomb）長器４３０と、ＤＣＴ変換器４４０と、量子化器４５２及びハフマン長器４５４からなる有ひずみ符号化器４５０と、アクティビティ器４６０と、決定論理ユニット４７０とを備える。決定論理ユニット４７０は、ターゲット挿入器５００に入力を供給する。
【００４９】
ビット割当器４００は、この具体例においては、２０４個のＭＢからなるマクロユニットの試し符号化に基づき符号化の決定を行う。無ひずみＤＰＣＭと有ひずみＤＣＴを選択肢とする符号化モードの決定は、１回のＤＰＣＭ符号化処理（ＤＰＣＭリフォーマット器４１０、ＤＰＣＭ器４２０及びゴーロン長器４３０と協調して実行される）に基づき、更に、ＤＣＴ変換器４４０における１回の離散コサイン変換とそれに続く有ひずみ符号化ユニット４５０を介した６サイクルとを含む６回のＤＣＴ試し符号化処理に基づいて、行われる。アクティビティ器４６０は、量子化器４５２がデータに適用する量子化除数を調整する。アクティビティ器４６０で実行される演算について、以下に詳述する。
【００５０】
決定論理器４７０には、ＤＰＣＭ符号化のエントロピー符号化処理を行うゴーロン長器４３０の出力が供給されるとともに、ＤＣＴ符号化のエントロピー符号処理を行うハフマン長器４５４の出力が供給される。決定論理ユニット４７０は、ＤＰＣＭ試し符号化とＤＣＴ試し符号化との結果を比較する。無ひずみＤＰＣＭは、マクロブロックに対して全体のビット数がより少ない場合のみ、選択される。また、決定論理ユニット４７０は、マクロブロックユニットとマクロブロックの双方についてターゲットビット数を算出する。
【００５１】
アクティビティ器４６０は、ＤＣＴモードの符号化回路の一部を構成し、画像ブロックの画素の分散に基づきアクティビティの尺度を算出する。より高いアクティビティレベルを有する画像ブロックでは、量子化をより粗くしても、見る人には知覚されにくいことが知られている。各ブロックに対する量子化ステップは、ビット割当器４００の量子化器４５２で使用される量子化除数Q_SCALEを、高いアクティビティレベルのブロックが粗く量子化されるように、適切に調整することによりオフセット（offset）することができる。後述するように、ビット割当処理のために使用されるQ_SCALE_CODEは、「アクティビティオン」か「アクティビティオフ」の状態に依存する。更に、アクティビティファクタNORM_ACTは、上述のＤＣＴのＡＣ係数Ｑ(AC)の量子化の式の分母に現れている。
【００５２】
アクティビティは、各マクロブロックに対して１回ずつだけ計算される。パラメータIntraMADの値は、マクロブロック内の各８Ｈ×８ＶＤＣＴブロックに対して、ＹＣbＣrモードでは輝度（Ｙ)ＤＣＴブロックのみ、ＲＧＢモードではＲ、Ｇ、Ｂのブロックが計算される。パラメータIntraMADは次のように定義される。
【００５３】
【数１】
0004263517.tif 000003
【００５４】
ここで、dct[i,j]は、ｊ番目のＤＣＴブロックのｉ番目の画素の画素値である。パラメータdct_dc[j]は、８Ｈ×８ＶＤＣＴブロックについての（且つ所定の信号成分についての）dct[i,j]の平均値であり、次式で与えられる。
【００５５】
【数２】
0004263517.tif 000004
【００５６】
マクロブロック内の全てのＹ又はＲＧＢのＤＣＴブロックに対するパラメータIntraMADの最小値は、次式で与えられる。
【００５７】
【数３】
0004263517.tif 000005
【００５８】
アクティビティACTは、
ACT＝１＋MinMAD
で与えられる。アクティビティACTの値は１から数千に及ぶので、アクティビティACTを正規化して所定の範囲内に収まるようにする。この具体例では、アクティビティACTを前回のマクロブロックユニットのデータによって正規化し、０．５〜２の範囲に収まるNORM_ACTを得ている。
【００５９】
NORM_ACT＝(２＊ACT＋AVG_ACT)／(ACT＋２＊AVG_ACT)
ここで、AVG_ACT＝前ＭＢＵからのアクティビティACTの平均である。
【００６０】
画像シーケンスの開始時、あるいはシーンの変化を（標準的方法により）検出したときには、量子化除数パラメータQ_START、DCT_PRECISIONに依存したデフォルト値DEFAULT_AVG_ACTをAVG_ACTの代わりに使用する。任意のフレーム（シーケンスの最初のフレームは除く）内の最初のＭＢＵに対しては、前フレーム内の全てのＭＢＵに対するアクティビティACTの平均を表す値FRM_AVG_ACTをAVG_ACTの代わりに使用する。この具体例では、アクティビティACTを０．５〜２の範囲に収まるように正規化しているが、代わりに次式を用いることにより、ｐ／ｑ〜ｑ／ｐである任意の範囲に正規化することができる。
【００６１】
NORM_ACT＝(ｑ＊ACT＋ｐ＊AVG_ACT)／(ｐ＊ACT＋ｑ＊AVG_ACT)
したがって、NORM_ACTの範囲を０．５〜２となるように選択する場合、パラメータｐ、ｑは、それぞれ値１、２である。
【００６２】
符号化の多数世代に亘る反復性を良くするために、NORM_ACTは固定数のレベルに制限される。０．５〜２．０の範囲に対して、NORM_ACTは８個のレベル（４／８、５／８、６／８、７／８、１，４／３、５／３、２）に制限される。
【００６３】
図８は、各ＭＢＵに対し、本発明の具体例に基づくビット割当器４００によって実行されるアルゴリズムを表すフローチャートである。ステップ１は、ＤＰＣＭリフォーマット器４１０、ＤＰＣＭ器４２０及びゴーロン長器４３０の協調動作で実行される。ステップ２Ａ〜２Ｄは、量子化器４５２により実行され、ステップ３〜５は、決定論理器４７０により実行される。
【００６４】
ステップ１において、ＭＢＵ内の全ＭＢに対して１回の無ひずみＤＰＣＭ試し符号化を実行し、各ＭＢについてＤＰＣＭ符号化によって生成されるビット数MB_DPCM_BITを測定する。
【００６５】
ステップ２Ａにおいて、ＭＢＵ内の全ＭＢに対して６回の有ひずみＤＣＴ符号化を実行して、各ブロック及び６個の試し量子化除数Q_SCALE(1)〜(6)の各々について、ＭＢの有ひずみＤＣＴ符号化によって生成されるビット数MB_DCT_BITS（Q_SCALE）を測定する。量子化除数Q_SCALEの各値は、３１個のQ_SCALE_CODEのいずれか１つと線形又は非線形であるQ_SCALE_TYPEとの組合せにより定まる。３１個の使用可能なQ_SCALE_CODEに関する量子化除数Q_SCALEの全範囲を完全に走査する代わりに、Q_SCALE_CODEのサブセット（subset：以下、ＳＳという)を選択する。ＳＳは、量子化除数パラメータDCT_PRECISIONの値とアクティビティがオンかオフの両方を考慮して定められる。例えば、DCT_PRECISION＝１でアクティビティがオフの場合、サブセットは、
ＳＳ＝[２，３，５，７，１０，１５，２２，３１]
となる。一方、アクティビティがオンの場合（この場合、NORM_ACTは０．５〜２の範囲にある）、サブセットは、
ＳＳ＝[２，３，５，７，１０，１５]
で与えられる。
【００６６】
下記表２は、「アクティビティオン」と「アクティビティオフ」の両方に対する量子化除数パラメータDCT_PRECISIONの各値について、本発明の具体例で用いられたビット割当用サブセットを示したものである。
【００６７】
【表２】
0004263517.tif 000006
【００６８】
試し量子化で使用する６個の量子化除数Q_SCALE(1)〜(6)は、該当するＳＳから取り出した６個のQ_SCALE_CODEに関する量子化除数に対応している。なお、各ＳＳは、殆どの場合、６より多い数のQ_SCALE_CODEを含んでいる。量子化除数パラメータQ_STARTの値を用いて、サブセットの中から試し量子化で使用する６個のQ_SCALE_CODEを選択する。
【００６９】
サブセット内で使用可能な最小のQ_SCALE_CODEは、下記式の量子化ファクタMINIMUM_Qを表すコードであり、
MINIMUM_Q＝２（ＤＣＴ＿ＰＲＥＣＩＳＩＯＮ）
あるいは、このコードが存在しないときは、使用可能な最小のQ_SCALE_CODEは、量子化ファクタMINIMUM_Qよりも大きな数の中で最も小さなQ_SCALE_CODEである。
【００７０】
ステップ２Ｂにおいて、量子化除数パラメータDCT_PRECISIONの値に関係する量子化除数パラメータQ_STARTの誤差を算出し、この誤差は、
Q_START_ERROR＝２４／（３−２ＤＣＴ＿ＰＲＥＣＩＳＩＯＮ）
で与えられるので、量子化の粗さが小さくなる量子化除数パラメータDCT_PRECISIONの値に対して、Q_STARTの誤差は大きくなる。
【００７１】
ステップ２Ｃにおいて、量子化除数パラメータQ_STARTから誤差Q_START_ERRORを減算することによってQ_SCALE_MINを算出するとともに、図４のルックアップテーブルからQ_SCALE_MINに関するQ_SCALE_CODE及びQ_SCALE_CODE_MINを求める。サブセットの中のQ_SCALE_CODE_MIN以下の、一番近いQ_SCALE_CODEを識別し、このQ_SCALE_CODEに対応した量子化除数を、６個の試し量子化パラメータの中の１番目、すなわち試し量子化除数Q_SCALE(1)として定める。なお、サブセット中にQ_SCALE_CODE_MIN以下のQ_SCALE_CODEがない場合は、試し量子化除数Q_SCALE(1)を、サブセット中の最も小さなQ_SCALE_CODEに対応した量子化ファクタに設定する。
【００７２】
ステップ２Ｄにおいて、残る５個の試し量子化除数Q_SCALE(2)〜(6)を、サブセット中の試し量子化除数Q_SCALE(1)よりも順に大きな５個Q_SCALE_CODEに割り当てる。サブセット中にこれを満足する十分な数のQ_SCALE_CODEがないときは、試し量子化除数Q_SCALE(6)を、サブセット中の最大のQ_SCALE_CODEに設定するとともに、試し量子化除数Q_SCALE(1)〜(5)を、サブセット中の試し量子化除数Q_SCALE(6)よりも順に小さな５個のQ_SCALE_CODEに設定する。
【００７３】
ステップ３において、６回の試しＤＣＴ量子化を行い、マクロブロックユニット内の全てのマクロブロックに亘るMB_DCT_BITS(Q_SCALE)の値の総和を求めて、６個の試し量子化除数Q_SCALE(1)〜(6)の各々に対する値MBU_DCT_BITS(Q_SCALE)を生成する。ＭＢＵ毎のターゲットビット数は、各画像フレーム（又はフィールド）毎に定めた所定のFRAME_TARGETから、
MBU_TARGET＝FRAME_TARGET／４０
により算出される。
【００７４】
既知の方式においては、FRAME_TARGETは、所要の符号化ビットレートにより完全に決まっている。しかしながら、本発明の具体例では、FRAME_TARGETを、所要の符号化ビットレートからだけではなく、ビデオデータが「ソース」か「非ソース」かにも依存して割り当てる。入力データを「ソース」データであると判定した場合、所要のビットレートを、僅かに減らすように調整することによって意図的に落とし、「ソース」データに対するFRAME_TARGETも有効に下げるように調整する。この具体例において、下げる調整は２．５％である。「ソース」入力データに対するFRAME_TARGETを特に低減した結果として、そのソースデータに対してビット割当器４００によって算出されるマクロブロックのターゲットビット数は減少し、第１世代のQ_ALLOC_GEN1に対する（２分探索器７００によって算出される）Q_ALLOCは増加し、FRAME_TARGETを低減しなかった場合に比べて僅かながら粗い、最終的な量子化Q_FINAL_GEN1を第１世代の再生画像に対して適用することになる。しかしながら、第１世代画像の画質の若干の低下は、FRAME_TARGETを低減した画像データを更に圧縮／伸長する際に得られる利点によって相殺される。このデータの第２世代及びそれ以降の世代における符号化では、FRAME_TARGETを調整しない。第２世代の調整された値Q_ALLOC_GEN2_ADJUSTEDは、Q_FINAL_GEN1よりも小さくなる傾向が、調整しなかった値Q_ALLOC_GEN2よりも遙かに強い。これを図９を参照して説明する。図９に示すように、従来の逆戻り探索の開始点がQ_FINAL_GEN1を見失っているのに対し、調整された逆戻り探索、すなわち第１世代のFRAME_TARGETの調整に基づく２分探索は、その試し量子化除数Q_SCALEの範囲内にQ_FINAL_GEN1を含んでいる。したがって、調整された逆戻り探索処理は、第２（及びそれ以降の）世代について可能な最良の画質を与えるQ_FINAL_GEN2＝Q_FINAL_GEN1を発見する可能性が高い。なお、第２世代の入力データの符号化際に、第１世代の符号化の所要レートは必ずしも分かっていない。
【００７５】
MBU_DCT_BITS(Q_SCALE）の６個の値からなるセットをターゲットビット数MBU_TARGETと比較し、ターゲットビット数MBU_TARGETの直ぐ上と直ぐ下にある、MBU_DCT_BITS(Q_SCALE)の２つの値B_UＭＢＵ、B_LＭＢＵをそれぞれ次のように定義する。
【００７６】
B_UＭＢＵ≡MBU_DCT_BITS(Q_SCALE(n))＞MBU_TARGET
B_LＭＢＵ≡MBU_DCT_BITS(Q_SCALE(n+1))≦MBU_TARGET
図１０は、量子化除数Q_SCALEに対するMBU_DCT_BITSを示すグラフであり、量子化除数Q_SCALEのコードQ_SCALE(n)、Q_SCALE(n+1)にそれぞれ対応した２つのビット数の値B_LＭＢＵ、B_UＭＢＵを示している。小さい方の量子化除数Q_SCALE(n)は、大きい方の量子化除数Q_SCALE(n+1)に比べて、ビット数が多くなっている。マクロユニットに関する「ビット対Q_SCALE」のグラフの性質を利用して、ＭＢＵに属する各ＭＢに対するターゲットビット数MBU_TARGETを導き出す。特に、図１０に示す量Ｘ、Ｙ、Ｚは次のように定義される。
【００７７】
Ｘ≡MBU_TARGET−B_UＭＢＵ
Ｙ≡B_LＭＢＵ−MBU_TARGET
Ｚ≡B_UＭＢＵ−B_LＭＢＵ＝Ｘ＋Ｙ
したがって、
MBU_TARGET＝（B_UＭＢＵＸ＋B_LＭＢＵＹ）／Ｚ
したがって、図８のステップ４において、ターゲットビット数MB_TARGETは、次のようにして算出される。
【００７８】
MB_TARGET＝Ｘ＊MB_DCT_BITS(Q_SCALE(n))／Ｚ
＋Ｙ＊MB_DCT_BITS(Q_SCALE(n+1))／Ｚ
そして、もしＺ＝０ならば、ゼロの除算を避けるために、MBU_TARGET＝MBU_DCT_BITS(Q_SCALE（n))と設定する。
【００７９】
ステップ５において、ＭＢＵ内の各ＭＢ毎に無ひずみＤＰＣＭ符号化と有ひずみＤＣＴ符号化との間で選択を行うために、MB_DPCM_BITをターゲットビット数MB_TARGETと比較する。MB_DPCM_BITがターゲットビット数MB_TARGETより大きいときは、そのマクロブロックに対して有ひずみＤＣＴ符号化を選択する。逆に、MB_DPCM_BITがターゲットビット数MB_TARGET以下ときは、そのマクロブロックに対して無ひずみＤＰＣＭ符号化モードを選択する。無ひずみＤＰＣＭ符号化モードがＭＢに対して選択される毎に、ターゲットビット数MBU_TARGETを再計算して、MBU_TARGET＝MBU_TARGET−MB_DPCM_BITとする。また、MBU_DCT_BITS(Q_SCALE(n))及びMBU_DCT_BITS(Q_SCALE(n+1))を次のように再計算する。
【００８０】
MBU_DCT_BITS(Q_SCALE(n))＝MBU_DCT_BITS(Q_SCALE(n))
−MB_DCT_BITS(Q_SCALE(n))
MBU_DCT_BITS(Q_SCALE(n+1))＝MBU_DCT_BITS(Q_SCALE(n+1))
−MB_DCT_BITS(Q_SCALE(n+1))
ターゲットビット数MBU_TARGETをステップ５において再計算しているので、ターゲットビット数MB_TARGETについても、有ひずみＤＣＴモード符号化に現在割り当てらているＭＢの個数を考慮して、再計算する必要がある。ステップ６において、ＤＰＣＭ符号化モードに切り替わるＭＢが無くなるまで、全ての有ひずみＤＣＴモードのＭＢに対してステップ４、５を繰り返す。これを達成するのに、代表的には５、６回の反復で十分である。
【００８１】
量子化除数Q_SCALEに関する不正確な予測によって、適切な量子化除数Q_SCALEがビット割当探索範囲（６個の量子化除数Q_SCALEからなる）外に位置するような状況を検討する必要がある。このような場合、ターゲットビット数MB_TARGETを計算するために、上述のステップ３、４の方法に対する代わりの方法が必要となる。２つの可能な方法が考えられる。
【００８２】
先ず、ステップ３において、MBU_DCT_BITS(Q_SCALE(n))が、ｎが６個の全ての値についてターゲットビット数MBU_TARGET以下であり、量子化が６個の試し値の全てについて粗すぎるときは、ステップ４におけるターゲットビット数MB_TARGETを次のように計算する。
【００８３】
【数４】
0004263517.tif 000007
【００８４】
この第１の方法を図１１に示す。
【００８５】
第２に、ステップ３において、MBU_DCT_BITS(Q_SCALE(n))が、ｎが６個の全ての値についてターゲットビット数MBU_TARGETより大きく、量子化が６個の試し値のいずれについても粗すぎないときは、試し量子化除数Q_SCALE(5)、Q_SCALE(6)をステップ３におけるQ_SCALE(n)、Q_SCALE(n+1)として選択する。この場合、ステップ４は変更されないが、今度はターゲットビット数MB_TARGETの外挿（extrapolating）効果が生じる。この第２の方法を図１２に示す。
【００８６】
ターゲットビット数MB_TARGETの計算に加え、ビット割当器４００は、２分探索における量子化除数Q_SCALEの開始点の値Q_BASEを設定する。量子化除数Q_SCALEの開始点の値Q_BASEは、適切なMBU_DCT_BITS対Q_SCALE曲線を用いて、ターゲットビット数MB_TARGETから求められる。この具体例のように５回の２分探索を行う場合、開始点の値Q_BASEは、単にQ_SCALE_CODE＝１６で与えられる量子化除数Q_SCALE（すなわち量子化表の中点）である。したがって、２分探索は、この開始点の値Q_BASEから開始することにより、量子化除数Q_SCALEの全範囲をカバーすることができる。しかしながら、２分探索の回数を少なくした具体例では、開始点の値Q_BASEを、各マクロブロック対してQ_SCALE(n)とQ_SCALE(n+1)の中間に設定する。有ひずみＤＣＴモード符号化に割り当てられたマクロブロックに対してのみ、決定論理ユニット４７０から開始点の値Q_BASE及びターゲットビット数MB_TARGETを出力し、ターゲット挿入器５００によって１ＭＢＵだけ遅延された画像データIP_DD1、IP_DD2からなるビットストリームに付加する。ターゲットビット数MB_TARGET及び開始点の値Q_BASEを２分探索器７００に供給し、２分探索器７００は、これらを最終的な量子化除数Q_SCALEを決定するのに使用する。
【００８７】
図１３は、２分探索器７００の内部構成を示すブロック図である。２分探索器７００は、５つの部分からなり、各部分は２分探索の各段に対応している。各部分は、ＭＢ遅延器７１０と、量子化器７２０と、ハフマン長算出器７３０と、Q_SCALE選択器７４０とを備える。
【００８８】
２分探索器７００には、離散コサイン変換されたマクロブロックデータからなる２つの入力信号BIN_IP_D1、BIN_IP_D2が、ビット割当器４００で算出されたターゲットビット数MB_TARGET及び開始点の値Q_BASEと共に供給される。入力信号BIN_IP_D1、BIN_IP_D2はＭＢ遅延器７１０に供給され、ＭＢ遅延器７１０は、この入力信号BIN_IP_D1、BIN_IP_D2を、５段の２分探索処理間でそれぞれ１マクロブロック異なるように遅延する。また、信号BIN_IP_D1、BIN_IP_D2は量子化器７２０にも供給され、量子化器７２０は、ハフマンエントロピー符号化を行うハフマン長算出器７３０にデータを出力する。２分探索アルゴリズムの各段は、量子化器７２０とハフマン長算出器７３０とを介したサイクルを実行する。ハフマン長算出器７３０は、ＤＣＴ変換され、量子化されたマクロブロックを符号化するのに必要なビット長を算出する。５つの部分のそれぞれの量子化器７２０及びハフマン長算出器７３０には、入力信号IP_PGMが供給されており、この信号IP_PGMは、８Ｈ×８ＶのＤＣＴブロック内のサンプル位置に基づいて各サンプルの量子化を変えるために使用する量子化重み付けマトリクス（Quantiser Weighting Matirices）のデータと、各テーブル／グループの組合せ毎にビット長を与えるＡＣ係数が可変長のハフマン長符号化テーブル（Huffman length AC vairiable length coding table）とからなる。この具合例では、５回の２分探索処理で使用する全ての量子化重み付けマトリクスを１つのＲＡＭに記憶するようにすることによって、ハードウェア要求を軽減することができる。なお、各処理段でランダムにアクセスすることが要求されるＶＬＣデータテーブルを用いた場合は、ハードウェアとしてＶＬＣデータテーブル毎に独立したＲＡＭが必要である。
【００８９】
ＭＢ遅延器７１０からの遅延された入力データと、ハフマン長算出器７３０の出力はQ_SCALE選択器７４０に入力として供給され、Q_SCALE選択器７４０は、マクロブロックを試験するために次のQ_SCALE値を選択し、選択したQ_SCALE値を次段の２分探索に供給する。最終的なQ_SCALE値は、５段目の２分探索部のQ_SCALE選択器７４０によって選択され、これをQ_ALLOCで示す。Q_ALLOCは、マクロブロックに対してターゲットビット数MB_TARGETを超えない最小のQ_SCALE値である。Q_ALLOC値は、最終的な出力信号BIN_OP_D1、BIN_OP_D2と共に、更なる処理のために逆戻り探索器８００に供給される。ここで、出力信号BIN_OP_D1、BIN_OP_D2は、入力信号BIN_IP_D1、BIN_IP_D2に対して合計で５マクロブロック分遅延している。
【００９０】
図１４は、５段の２分探索処理を説明するための図である。
【００９１】
第１段目の２分探索は、ビット割当器４００によって算出された開始点の値Q_BASEを用いて、入力データを量子化し、Q_BASE_CODEで示す２分探索の開始点Q_SCALE_CODEを決定する。この具体例では、２分探索は、量子化除数Q_SCALEの全範囲を探索する５段からなる。したがって、開始点の値Q_BASEは、常に、値が１６のQ_SCALE_CODEに対応するこの範囲の中心に設定される。そして、量子化データは、ハフマン長算出器７３０に供給される。ハフマン長算出器７３０で算出された第１段目におけるデータ長がターゲットビット数MB_TARGETより大きいときは、次段の２分探索のために、Q_SCALE値をQ_SCALE_CODEの８ステップ分増加し、そうでないときは、Q_SCALE値をQ_SCALE_CODEの８ステップ分減少する。この具体例では、Q_SCALE値は第２段目においてQ_SCALE_CODEの８ステップ分増加している。入力データは、次段に合わせるために、１マクロブロック分遅延される。
【００９２】
第２段目において、データを値Q_SCALE_CODE＝(Q_BASE_CODE＋８)を用いて量子化し、第２段目におけるデータ長を算出する。第２段目のデータ長をターゲットビット数MB_TARGETと比較して、第３段目のために、Q_SCALE値をQ_SCALE_CODEの４ステップ分増加又は減少する。この具体例では、Q_SCALE値は第３段目においてQ_SCALE_CODEの４ステップ分減少している。入力データを第３段目に合わせるために、２回目のＭＢ遅延を行う。
【００９３】
第３段目において、データを値Q_SCALE_CODE＝(Q_BASE_CODE＋８−４)を用いて量子化し、第３段目におけるデータ長を算出する。第３段目のデータ長をターゲットビット数MB_TARGETと比較して、第４段目のために、Q_SCALE値をQ_SCALE_CODEの２ステップ分増加又は減少する。この具体例では、Q_SCALE値は第４段目においてQ_SCALE_CODEの２ステップ分増加している。入力データを第４段目に合わせるために、３回目のＭＢ遅延を行う。
【００９４】
第４段目において、データを値Q_SCALE_CODE＝(Q_BASE_CODE＋８−４＋２)を用いて量子化し、第４段目におけるデータ長を算出する。第４段目のデータ長をターゲットビット数MB_TARGETと比較し、第５段目のために、Q_SCALE値をQ_SCALE_CODEの１ステップ分増加又は減少する。この具体例では、Q_SCALE値は第５段目においてQ_SCALE_CODEの１ステップ分増加している。入力データを第５段目に合わせるために、４回目のＭＢ遅延を行う。
【００９５】
第５段目において、データを値Q_SCALE_CODE＝(Q_BASE_CODE＋８−４＋２＋１)を用いて量子化し、第５段目におけるデータ長を算出する。第５段のデータ長をターゲットビット数MB_TARGETと比較する。第５段のデータ長がターゲットビット数MB_TARGETより大きいときは、Q_SCALE値をQ_SCALE_CODEの１ステップ分増加する。そうでないときは、Q_SCALE値は変更しない。この具体例では、Q_SCALE値は変更されていない。このようにして、２分探索アルゴリズムでは、マクロブロックに対してターゲットビット数MB_TARGETを超えない最小のQ_SCALE値を選択する。このQ_SCALE値はQ_ALLOCと呼ばれる。
【００９６】
２分探索の各段において、Q_SCALE値を減少する決定は、量子化ファクタMINIMUM_Qの条件に制約される。使用可能な最小のQ_SCALE_CODEは、量子化ファクタMINIMUM_Qを表すQ_SCALE_CODEであり（又はこれが存在しなければ、量子化ファクタMINIMUM_Qより大きな数を表す最初のQ_SCALE_CODEである）、ここで、
MINIMUM_Q＝２＾(３−DCT_PRECISION)
である。Q_SCALE値を減少させることにより、Q_SCALE値が使用可能な最小のQ_SCALE_CODEより小さくなったときは、次段の２分探索の前に、Q_SCALE値を使用可能な最小のQ_SCALE_CODEと等しくなるように設定する。
【００９７】
図１５は、２分探索器７００の各２分探索段における入力及び出力マクロブロックのタイミングを示す図である。
【００９８】
２分探索器７００は、無ひずみモード（ＤＰＣＭ）で符号化したマクロブロックに対しては、BYPASSモードで動作する。BYPASSモードでは、各２分探索処理の終了時に通常実行されるQ_SCALEの切換は行われない。これにより、２分探索器７００の出力データは、入力データと等しい。
【００９９】
図１６は、逆戻り探索器８００の内部構成を示すブロック図である。この逆戻り探索器８００は、Q_SCALE抽出回路８１０と、Q_SCALEスケール増分器（incrementer）８２０と、前処理器（pre-processor）８３０と、量子化器８４２及び誤差算出器８４４をそれぞれ有する６個の量子化部８４０と、マクロブロック遅延器８５０と、Q_SCALE選択器８６０とを備える。
【０１００】
逆戻り探索器８００の入力は、２分探索器７００の出力信号BIN_OP_D1、BIN_OP_D2である。この入力データには、各ＭＢの値Q_ALLOCが含まれている。Q_SCALE抽出回路８１０は、入力ビットストリームから量子化除数Q_SCALEの値Q_ALLOCを抽出し、この値は、逆戻り探索処理で試験する最初の量子化スケールとして用いられる。各量子化部８４０は、２つの量子化スケールを試験する。Q_SCALE抽出回路８１０は、値Q_ALLOCをQ_SCALEスケール増分器８２０に出力し、ここで、これらの値は、Q_SCALE_CODEの１ステップ分だけ増加されて、量子化部８４０で試験される第２の量子化スケールとなり、この第２の値は量子化部８４０の量子化器８４２に入力として供給される。Q_SCALE抽出回路８１０から出力されるＭＢデータは、ＭＢ遅延器８５０に供給され、ここで１ＭＢ分遅延された後、Q_SCALE選択器８６０に入力として供給される。Q_SCALE抽出回路８１０からのＭＢデータは前処理器８３０にも供給されており、ここで、ＤＣＴ係数の６３個のＡＣ係数のうちの第１の３１個を繰り返して、各ＤＣＴブロックで２度発生するようにする。前処理器８３０からの出力は、６個の量子化部８４０のそれぞれに供給される。各量子化部８４０は、異なる２つの量子化レベルにおける量子化誤差を評価する。この１個の量子化部８４０当たり２つの量子化レベルの計算は、誤差計算にＤＣＴの３１個のＡＣ係数のみを用いているので可能である。この具体例では、ＤＣＴの第１の３１個のＡＣ係数を用いて誤差を計算しているが、代わりに、ＤＣＴの第２の３１個のＡＣ係数を用いてもよい。量子化器８４２は、第１の量子化除数を用いてＤＣＴの第１の３１個のＡＣ係数を量子化し、第２の量子化除数を用いてＤＣＴの第２の３１個ののＡＣ係数を量子化する。
【０１０１】
量子化除数の範囲を６個の量子化部８４０で試験する際、Q_SCALE＝Q_ALLOCから始め、量子化除数Q_SCALEをQ_SCALE_CODEの１ステップ分同時に増加して、全部で１２個までの量子化スケールを試験する。各量子化器８４２は、入力信号IP_PGMが供給されており、この信号IP_PGMは、８Ｈ×８Ｖのブロック内のサンプル位置に基づいて各サンプルの量子化を変える量子化重み付けマトリクスからなる。量子化器８４２は、量子化データを誤差算出器８４４に出力し、誤差算出器８４４は、実行された量子化に関する残差誤差（residual error）を算出する。
【０１０２】
量子化処理の結果として、量子化された各ＤＣＴ係数は、関連する残差誤差を含んでおり、この残差誤差は、除算後の剰余（remainder）、量子化で使用したトータルの除数（total divisor）、及びその結果に適用した丸め方（rounding）に依存する。任意のＤＣＴ係数をＣとすると、Ｃはトータルの除数ｑ、剰余ｒ、整数ｎの組合せとして次のように表すことができる。
【０１０３】
Ｃ＝ｎ＊ｑ＋ｒ
量子化後、係数は切捨ての丸めにより「ｎ」に、あるいは切上げの丸めにより「ｎ＋１」になる。したがって、逆量子化後の絶対誤差は、ｎが切捨てなら「ｒ」、ｎが切上げなら「ｑ−ｒ」と予想される。
【０１０４】
誤差算出器８４４は、量子化器８４２から丸め前の結果Ｃ／ｑを取り出し、「ｑ」を既知であり、マクロブロック全体について一定であるとして、この誤差算出器８４４は、各ＤＣＴ係数に対する残差誤差「ｒ」又は「ｑ−ｒ」を評価することができる。残差誤差を各ＤＣＴブロックの第１の（又は第２の）３１個のＡＣ係数について累算して、マクロブロック全体についてトータルの誤差を求める。
【０１０５】
６個の誤差算出器８４４の各々の出力は、Q_SCALE選択器８６０に供給され、Q_SCALE選択器８６０は、各マクロブロックに対して、最小の残差誤差を発生する、Q_FINALで示される量子化除数Q_SCALEを選択する。ＭＢ遅延器８５０は、残差誤差の計算にかかる時間を補償するために設けられている。Q_FINAL値を遅延された入力データのビットストリームに挿入して、逆戻り探索器８００の出力信号BKS_OP_D1、BKS_OP_D2を形成する。逆戻り探索器８００の出力は、最終的な量子化器９００に入力として供給され、ここで、値Q_FINALによりデータは量子化され、その後、エントロピー符号化器１０００でハフマン符号化される。
【図面の簡単な説明】
【図１】既知の逆戻り探索法の問題を模式的に説明するための図である。
【図２】データ記録／再生装置又はデータ送信／受信システムと共に使用される、圧縮符号化装置及び対応する復号装置の模式図である。
【図３】図２のビットレート圧縮符号化装置を模式的に説明するための図である。
【図４】図２の符号化装置のビットレート圧縮処理で使用するパラメータの表である。
【図５】図２の復号装置を模式的に示した図である。
【図６】図３のシャッフル部におけるDCT_PRECISION検出回路により行われる計算を模式的に示した図である。
【図７】図３の符号化装置のビット割当器を模式的に説明するための図である。
【図８】図７のビット割当器により行われる計算を示すフローチャートである。
【図９】本発明の具体例に基づいた、調整逆戻り探索の利点を模式的に説明するための図である。
【図１０】  Q_SCALEに対するMBU_DCT_BITSを説明するグラフである。
【図１１】全部で６個の試し量子化値について量子化が粗すぎる場合における、Q_SCALEに対するMBU_DCT_BITSのグラフである。
【図１２】６個の試し量子化値のいずれに対しても量子化が粗くない場合における、Q_SCALEに対するMBU_DCT_BITSのグラフである。
【図１３】図３に示す符号化装置の２分探索器の内部構成を模式的に示した図である。
【図１４】図１３の装置が行う５段構成の２分探索の説明するための図である。
【図１５】図１４の２分探索の各段におけるマクロブロック遅延を模式的に説明するための図である。
【図１６】図３に示す符号化装置の２分探索器を模式的に説明するための図である。
【図１】
0004263517.tif 000008
【図２】
0004263517.tif 000009
【図３】
0004263517.tif 000010
【図４】
0004263517.tif 000011
【図５】
0004263517.tif 000012
【図６】
0004263517.tif 000013
【図７】
0004263517.tif 000014
【図８】
0004263517.tif 000015
【図９】
0004263517.tif 000016
【図１０】
0004263517.tif 000017
【図１１】
0004263517.tif 000018
【図１２】
0004263517.tif 000019
【図１３】
0004263517.tif 000020
【図１４】
0004263517.tif 000021
【図１５】
0004263517.tif 000022
【図１６】
0004263517.tif 000023