(57)【要約】【課題】最良画質を得るための量子化ステップの選択が保証されるデーター圧縮装置を提供する。【解決手段】データ圧縮装置は、入力データが前に圧縮／伸長サイクルを経験したことがないソースデータか否かを検出するソース検出部と、ソース検出部に応答して、ソース入力データに対しては第１の値であり、非ソース入力データに対してはこの第１の値よりも大きな第２の値である所望の出力データ量を圧縮データに設定するデータ量発生器と、全体として所望の出力データ量となる個々のターゲットデータ量を、所望の出力データ量に基づいて、入力データの各サブセットに割り当てるターゲット割当器と、入力データの各サブセットを個々のターゲットデータ量に基づいて圧縮するデータ圧縮部とを備える。【選択図】　図１
2004129204.tif 000002
【特許請求の範囲】
【請求項１】
入力データが前に圧縮／伸長サイクルを経験したことがないソースデータか否かを検出するソース検出部と、
上記ソース検出部に応答して、ソース入力データに対しては第１の値であり、非ソース入力データに対しては該第１の値よりも大きな第２の値である所望の出力データ量を圧縮データに設定するデータ量発生器と、
全体として上記所望の出力データ量となる個々のターゲットデータ量を、上記所望の出力データ量に基づいて、上記入力データの各サブセットに割り当てるターゲット割当器と、
上記入力データの各サブセットを上記個々のターゲットデータ量に基づいて圧縮するデータ圧縮部とを備えるデータ圧縮装置。
【請求項２】
上記入力データは、画像データであることを特徴とする請求項１記載のデータ圧縮装置。
【請求項３】
上記データ圧縮部は、
上記入力データの各サブセットについて少なくとも１つの量子化の程度を試して、該量子化の程度を用いて発生するデータ量を試験する１つ以上の試し量子化器と、
上記試し量子化器の結果に基づいて、上記ターゲットデータ量がそのサブセットについて超えないように、上記入力データの圧縮に用いる量子化の程度を選択する選択器と、
上記入力データのサブセットを、上記選択されたそれぞれの量子化の程度に基づいて量子化する量子化器とを備えることを特徴とする請求項１又は２記載のデータ圧縮装置。
【請求項４】
上記ターゲットデータ量を超えない最も粗さの小さな試し量子化の程度及び１つ以上のより粗い量子化の程度において、上記入力データの各サブセットを量子化する少なくとも１つの量子化器を有する逆戻り探索部と、
上記後戻り量子化器によって実行される上記各量子化の程度での量子化により発生する量子化誤差を算出する少なくとも１つの誤差算出器とを備え、
上記選択器は、上記入力データのサブセットの圧縮に使用する量子化の程度として、上記逆戻り量子化器による量子化で発生する誤差が最小となる上記誤差算出器が決定した量子化の程度を選択することを特徴とする請求項３記載のデータ圧縮装置。
【請求項５】
上記誤差算出器は、複数の離散コサイン変換係数に対する残差誤差を累算して、上記量子化誤差を算出することを特徴とする請求項４記載のデータ圧縮装置。
【請求項６】
上記誤差算出器は、
上記逆戻り探索量子化器によって量子化されたデータを逆量子化する少なくとも１つの逆量子化器と、
上記逆量子化したデータを対応する量子化前のデータと比較して、上記量子化誤差を検出する比較器とを備えることを特徴とする請求項４記載のデータ圧縮装置。
【請求項７】
上記所望のデータ量に関する上記第１の値は、該所望のデータ量に関する上記第２の値より約５％少ないことを特徴とする請求項１乃至６のいずれか１項記載のデータ圧縮装置。
【請求項８】
入力データが前に圧縮／伸長サイクルを経験したことがないソースデータか否かを検出するステップと、
圧縮データに対する所望のデータ量として、ソース入力データに対しては第１の値であり、非ソース入力データに対しては該第１の値よりも大きな第２の値である所望の出力データ量を設定するステップと、
全体として上記所望の出力データ量となる個々のターゲットデータ量を、上記所望の出力データ量に基づいて、上記入力データの各サブセットに割り当てるステップと、
上記入力データの各サブセットを上記個々のターゲットデータ量に基づいて圧縮するステップとを有するデータ圧縮方法。
【請求項９】
図面を参照して説明したデータ圧縮方法。
【請求項１０】
請求項８又は９記載のデータ圧縮方法を実施するプログラムコードを有するコンピュータソフトウェア。
【請求項１１】
請求項１０記載のコンピュータソフトウェアを提供するデータ提供媒体。
【請求項１２】
上記データ提供媒体は、伝送媒体であることを特徴とする請求項１１記載のデータ提供媒体。
【請求項１３】
上記データ提供媒体は、記憶媒体であることを特徴とする請求項１１記載のデータ提供媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデータ圧縮に関する。
【０００２】
【従来の技術】
データ圧縮技術は、制限された帯域幅内で動的に変化する通信チャンネルによってサポートされているビットレートでデータ通信を行うために、データ通信分野で広く採用されている。代表的には、画像データは、伝送又は適当な記憶媒体に蓄積する前に圧縮され、画像の再生に先立ち伸長される。
【０００３】
データ圧縮技術は、静止画像の場合は空間的な冗長度を利用し、動画像の場合は空間及び時間の双方の冗長度を利用する。時間的冗長度は、動画像において時系列における連続した画像、特に同一シーンに属する画像が非常に類似している場合に発生する。モーションピクチャーエキスパーツグループ（Ｍｏｔｉｏｎ　ＰｉｃｔｕｒｅＥｘｐｅｒｔｓ　ｇｒｏｕｐ：以下、ＭＰＥＧという。）は、娯楽及び放送の用途におけるビデオ圧縮符号化の国際的標準を規定している。本発明は、低いデータ圧縮率を用いて非常に高いデータレート（１Ｇｂｉｔ／ｓまで）で動作するハイエンドのビデオハードウェアに対するＭＰＥＧ４「スタジオプロファイル」規格の実現に関する（なお、本発明は、これに限定されるものではない）。
【０００４】
離散コサイン変換（Ｄｉｓｃｒｅｅｔ　Ｃｏｓｉｎｅ　Ｔｒａｎｓｆｏｒｍ：以下、ＤＣＴという）の量子化は、ビデオデータの符号化技術で広く用いられている。ＤＣＴの量子化は、データの伝送又は蓄積に先立ち、入力画像データを表すのに必要なデータのワード長を低減する画像圧縮において使用される。ＤＣＴの量子化処理において、画像は、規則的なサイズの画素値のブロックに分割され、殆どの場合、各ブロックは、横８画素、縦８画素（８Ｈ×８Ｖ）で構成される。従来のデータフォーマットにおいて、ビデオデータは、通常、カラー画像における赤、緑、青（ＲＧＢ）成分、あるいは輝度成分Ｙと２つの色差成分Ｃｂ、Ｃｒに対応する３つの成分を有する。全ての３つのＲＧＢ又はＹＣｂＣｒ信号成分に対応する画素ブロックのグループはマクロブロック（ＭＢ）と呼ばれる。
【０００５】
ＤＣＴは、画像の空間領域から空間周波数領域への変換を表し、画素値のブロックを同一次元を有する変換係数のブロックに有効に変換する。ＤＣＴ係数は、画像ブロックの空間周波数成分を表す。各係数は、適当な基底関数に適用される重みとみなすことができ、基底関数の重み付け和が入力画像を完全に表現している。ＤＣＴ係数の各８Ｈ×８Ｖブロックは、ゼロ空間周波数を表す１個の「ＤＣ」成分と６３個の「ＡＣ」成分からなる。ＤＣＴ係数の最大値は、殆どの場合、低い空間周波数のＤＣＴ係数に対応している。画像にＤＣＴを施すだけでは、必ずしも圧縮することはできず、単に画像データを空間領域から空間周波数領域に変換するだけである。圧縮を達成するためには、各ＤＣＴ係数は量子化除数（ｑｕａｎｔｉｓａｔｉｏｎ　ｄｉｖｉｓｏｒ）と呼ばれる正の整数で除算され、商は一番近い整数に切り上げ又は切り捨てすることにより丸められる。量子化除数を大きくすることにより、データをより圧縮することができるが、その代償として量子化が粗くなる。量子化を粗くするほど、再生画像の画質がより劣化する。ＤＣＴ係数の切上げ又は切捨てによる丸めの結果として、量子化によるアーティファクトが再生画像に発生する。圧縮画像の再生の際には、各ＤＣＴ係数は量子化ステップによる、当初の商ではなく、（最も近い整数に丸められた整数である）量子化係数を乗算することにより再生されるが、このことはＤＣＴ係数の当初の精度が確保されないことを意味する。したがって、量子化は「有ひずみ（ｌｏｓｓｙ）」符号化技術である。
【０００６】
画像データ圧縮システムでは、殆どの場合、所定の出力ビットレートを達成する最適の量子化除数を決定するために、一連の試し（ｔｒｉａｌ）圧縮を行っている。試し量子化は、例えば、可能な量子化除数の全範囲に亘って分散した２０個の可能な量子化除数で実行される。ターゲットビットレートの直ぐ上と直ぐ下に位置する予測出力ビットレートを与える２つの隣接した試し量子化除数を見つけ、この２つの値間で更に細かな探索を実行する。典型的には、画像圧縮を実行するために選ばれる量子化除数は、ターゲットビットレートを達成しつつ粗さが最小の量子化を与える量子化除数である。
【０００７】
粗さが最小の量子化除数を選択すると、過去に１回以上の圧縮／伸長サイクルを経験したことがない「ソース（ｓｏｕｒｃｅ）」画像データに対して、再生の際に最良の画質（すなわちノイズが最少の画像）が得られるが、このことは、「非ソース（ｎｏｎ−ｓｏｕｒｃｅ）」画像データに対しては必ずしも成立しないことが判明している。圧縮と伸長が１回行われた画像は第１世代の画像と呼ばれ、過去に２回圧縮／伸長サイクルが行れた画像は第２世代と呼ばれ、以下同様に高い世代となる。
【０００８】
第２世代の再生画像では、殆どの場合、第１世代の再生画像の対応する量子化除数でのノイズと比較して、画像ノイズが量子化除数の全範囲で体系的に高くなる。このことは、量子化の各処理（ｅａｃｈ　ｓｔａｇｅ）で生じるＤＣＴ係数の丸め誤差の問題として理解される。しかしながら、第２世代の量子化除数を第１世代の量子化除数と略等しく選んだ場合、第２世代の再生画像のノイズレベルは、第１世代の再生画像のノイズレベルと略等しくなることが知られている。したがって、非ソース入力画像データに対しては、所要のデータレートを満たし、可能な限り最小の大きさを有する量子化除数は、必ずしも再生画像の最良の画質をもたらさない。代わりに、前の圧縮／伸長サイクルで用いられた量子化除数に略等しい量子化除数により、再生画像の最良の画質が得られる可能性が高い。なお、量子化除数の選択は、特定の通信チャンネルの世代毎に変わる可能性があるターゲットビットレートによって制限される。
【０００９】
「最良」の量子化ステップが、所謂多世代（ｍｕｌｔｉ−ｇｅｎｅｒａｔｉｏｎ）画像に亘って選択されるように保証するために、上述した試し量子化によって見い出された量子化値から開始し、その後はより粗い量子化（大きな値の量子化）除数を用いて更なる検証を行う逆戻り探索（ｂａｃｋｓｅａｒｃｈ）を実施する。これらの逆戻り探索における量子化ステップの各々を用いて、データを量子化した後、逆量子化する。代替として、逆量子化の代わりに、量子化器の剰余（ｒｅｓｉｄｕａｌ）から誤差（ｅｒｒｏｒ）が算出される。逆量子化データと入力画像データを遅延したもの（量子化していないもの）とを比較し、この比較において最も誤差が小さくなる量子化ステップを逆戻り探索して、この量子化ステップを量子化の最終出力処理のために選択する。
【００１０】
【発明が解決しようとする課題】
逆戻り探索処理において、第２世代の画像におけるマクロブロックのターゲットビット数（ｔａｒｇｅｔ　ｂｉｔ　ｃｏｕｎｔ）が対応する第１世代画像におけるマクロブロックのターゲットビット数よりも少ない場合に問題が生じる。ターゲットビット数が不一致する結果として、第２世代の画像データは、第１世代の画像データよりも粗く（より大きな量子化除数を用いて）量子化される。図１は、この問題を模式的に説明するための図である。逆戻り探索処理は、量子化除数Ｑ＿ＳＣＡＬＥ＝Ｑ＿ＡＬＬＯＣから始まり、ここで、量子化除数Ｑ＿ＡＬＬＯＣは、マクロブロックのターゲットビット数に基づきビット割当／２分探索処理（ｂｉｔ　ａｌｌｏｃａｔｉｏｎ／ｂｉｎａｒｙ　ｓｅａｒｃｈ　ｐｒｏｃｅｓｓ）により選択されたものである。また、逆戻り探索は、量子化除数Ｑ＿ＡＬＬＯＣに対応した量子化よりも粗い一連の、例えば１２個の量子化除数ＱＢ１〜ＱＢ１２を試験する。（これらの試験した中で）再生画像のノイズが最も少なかった量子化除数を、Ｑ＿ＦＩＮＡＬとして決定する。したがって、第１世代の圧縮に対応した量子化除数Ｑ１は、量子化除数Ｑ＿ＡＬＬＯＣよりも粗くなく（より小さな量子化除数であり）、再生された第２世代の画像に対して最良の画質を与えるそうな値であるにもかかわらず、後戻り探索では検出されない。
【００１１】
原理上、この問題は、第２世代の逆戻り探索の開始点を、量子化除数Ｑ＿ＡＬＬＯＣよりも小さな量子化除数に対応させ、したがって逆戻り探索が量子化除数Ｑ１を確実に含むように調節することにより、解決することができるが、このようにすると、より小さな量子化除数が選択されてしまうことになる。これは、通信システムが処理できないような高いビットレートになりやすい。符号化ビットレートが所定の最大符号化ビットレートを超えると、許容できないデータ消失が起こる可能性がある。
【００１２】
【課題を解決するための手段】
本発明は、データ圧縮装置を提供する。このデータ圧縮装置は、入力データが前に圧縮／伸長サイクルを経験したことがないソースデータか否かを検出するソース検出部と、ソース検出部に応答して、ソース入力データに対しては第１の値であり、非ソース入力データに対してはこの第１の値よりも大きな第２の値である所望の出力データ量を圧縮データに設定するデータ量発生器と、全体として所望の出力データ量となる個々のターゲットデータ量を所望の出力データ量に基づいて、力データの各サブセットに割り当てるターゲット割当器と、入力データの各サブセットを個々のターゲットデータ量に基づいて圧縮するデータ圧縮部とを備える。
【００１３】
本発明は、前に圧縮及び伸長されたことがないデータに対しては所望のデータ量をより低いレベルのデータ量に設定することにより、上述した問題を解決する。データ量の違いは十分に小さく（例えば５％）することができ、それ自体は顕著ではないが、後の世代の圧縮処理において、第１世代で用いたのと同程度の量子化を達成する余裕（ｈｅａｄｒｏｏｍ）が得られる。これにより、後の世代のエラーレートを低減することができる。
【００１４】
【発明の実施の形態】
図２は、データ圧縮システムの構成を模式的に示す図である。このデータ圧縮システムは、符号化装置（ｅｎｃｏｄｅｒ）１０と、データ処理装置（ｄａｔａ　ｐｒｏｃｅｓｓｉｎｇｍｏｄｕｌｅ）２０と、復号装置（ｄｅｃｏｄｅｒ）３０とを備える。入力の高品位（ｈｉｇｈ　ｄｉｆｉｎｉｔｉｏｎ）ビデオ信号５は、符号化装置１０に供給される。符号化装置１０は、冗長度を除去し、その統計的性質を利用するためにビデオ画像データをモデル化し、入力画像データ５の情報を圧縮フォーマットで表現する出力データシンボルを生成する。符号化装置１０は、圧縮データ信号１５Ａを出力し、この圧縮データ信号１５Ａはデータ処理装置２０に供給され、そこで、通信チャンネルを介して伝送されるか、又は記録媒体に格納される。記録媒体から読み出された、又は通信チャンネルを介して受信された圧縮データ信号１５Ｂは、復号装置３０に供給され、復号装置３０は、圧縮データ信号１５Ｂを復号して高品位の出力画像信号３５を形成する。
【００１５】
図３は、図２のビットレートを低減する符号化装置１０の具体的な構成を示すブロック図である。高品位ビデオのフレームにおける入力ＲＧＢチャンネルに対応するデータ信号Ｄ１、Ｄ２、Ｄ３は、シャッフル部（ｓｈｕｆｆｌｅ　ｕｎｉｔ）１００に供給される。他の具体例として、データは、ＹＣｂＣｒフォーマットで供給することもできる。更に、画像は、プログレッシブフレームモードとインタレースフィールドモードのいずれでも処理することができる。シャッフル部１００は、入力データをマクロブロックユニット（Ｍａｃｒｏ−Ｂｌｏｃｋ　Ｕｎｉｔ：以下、ＭＢＵという）に分割する。この具体例では、１フレームは４０個のＭＢＵからなり、各ＭＢＵは２０４個のＭＢからなる。各入力フレームの画像サンプルは、外部ＳＤＲＡＭ２００に一時的に書き込まれる。このシャッフル書込処理中に、後続の符号化処理で必要とされる２つの量子化除数パラメータＱ＿ＳＴＡＲＴ、ＤＣＴ＿ＰＲＥＣＩＳＩＯＮの値が算出される。画素ブロックが外部ＳＤＲＡＭ２００から、入力画像フレーム内の隣接した画素ブロックがシャッフル順序では隣接した位置で読み出されないように画像データをインタリーブする所定のシャッフル順序に従って、読み出される。
【００１６】
シャッフル処理により、復号装置３０によって再生される画像におけるデータ消失の影響が軽減される。入力ビデオフレームにおいて隣接した画素ブロックは、シャッフルされたビットストリームでは、離れている。短時間のデータ消失により、ビットストリームの連続した一部が損なわれ、幾つかのデータブロックが影響を受けるが、これらのブロックは、再生画像内では連続していない。この場合、データ隠蔽（ｃｏｎｃｅａｌｍｅｎｔ）を適切に用いて、消失したブロックを再構成することができる。更に、シャッフル処理は、入力ビデオデータをＭＢＵに疑似ランダム的に分配することによって画像フレームの各ＭＢＵに選択された量子化パラメータの変化の度合い（ｖａｒｉａｔｉｏｎ）を低減することができ、可変速再生（ｓｕｔｔｌｅ　ｐｌａｙｂａｃｋ）時の画質が改善される。
【００１７】
現画像フレームは、外部ＳＤＲＡＭ２００から前フレームをシャッフルされたフォーマットで読み出している間に、外部ＳＤＲＡＭ２００に書き込まれる。シャッフル部１００は、２対の出力信号を生成し、第１の信号対は、信号Ｓ＿ＯＰ＿Ｄ１と信号Ｓ＿ＯＰ＿Ｄ２からなり、第２の信号対は、同じＭＢＵデータを含むが、第１の信号対に対して約１ＭＢＵ遅延された信号Ｓ＿ＯＰ＿ＤＤ１と信号Ｓ＿ＯＰ＿ＤＤ２からなる。この遅延は、Ｑ割当部（Ｑ　ａｌｌｏｃａｔｉｏｎ　ｕｎｉｔ）３００に内蔵されているビット割当器（ｂｉｔ　ａｌｌｏｃａｔｉｏｎ　ｍｏｄｕｌｅ）４００の処理による遅延を補償するためのものである。Ｑ割当部３００は、第１の信号対Ｓ＿ＯＰ＿Ｄ１、Ｓ＿ＯＰ＿Ｄ２を用いて、適切な符号化モードと、ＭＢＵの各ＭＢに対するＱ＿ＳＣＡＬＥパラメータと呼ばれる量子化除数を測定する（ｄｅｔｅｒｍｉｎｅ）。
【００１８】
シャッフル部１００から出力される信号は、Ｑ割当部３００に供給され、このＱ割当部３００は、ビット割当器４００と、ターゲット挿入器５００と、ＤＣＴ変換器６００と、２分探索（ｂｉｎａｒｙ　ｓｅａｒｃｈ　ｍｏｄｕｌｅ）器７００とを備える。シャッフル部１００から出力される第１の信号対Ｓ＿ＯＰ＿Ｄ１、Ｓ＿ＯＰ＿Ｄ２は、ビット割当器４００に入力される。これらの入力信号は、ラスタ走査された１２ビットビデオサンプルの８Ｈ×８Ｖ縦ブロックからなる。
【００１９】
ビット割当器４００は、無ひずみ（ｌｏｓｓｌｅｓｓ）の差分パルス符号変調（ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｕｌｓｅ　ｃｏｄｅ　ｍｏｄｕｌａｔｉｏｎ：以下、ＤＰＣＭという）符号化とＤＣＴ量子化符号化を比較する。
【００２０】
ＤＰＣＭは、画像内の空間的に近い画素は相関が高いことを利用した簡単な画像圧縮技術である。ＤＰＣＭでは、画素値自体は伝送されない。代わりに、符号化装置により、前に送信した画素値に基づいた画素の期待値が予測される。１回のＤＰＣＭ符号化処理（ｓｉｎｇｌｅ　ＤＰＣＭ　ｅｎｃｏｄｉｎｇ　ｓｔａｇｅ）は、ＤＰＣＭリフォーマットと、ＤＰＣＭ変換と、エントロピー符号化計算を含む。
【００２１】
これに対し、ＤＣＴ量子化符号化の処理は、１回のＤＣＴ変換と、一連の量子化除数を用いた複数回の量子化処理を含み、各量子化処理の後にハフマン（Ｈｕｆｆｍａｎ）エントロピー符号化計算が行われる。この具体例では、６個の試し（ｔｒｉａｌ）量子化除数がビット割当器４００により試験される。ハフマン符号化は、既知の無ひずみ圧縮技術であり、出現頻度の高い値は短い符号で、出現頻度の低い値は長い符号で表現される。ＤＣＴ試し符号化処理は、オプションとして、画像領域の「アクティビティ（ａｃｔｉｖｉｔｙ）」に依存した量子化を含む。アクティビティは、画像ブロックの適切に正規化された画素の分散（ｖａｒｉａｎｃｅ）から算出される尺度（ｍｅａｓｕｒｅ）である。高いアクティビティを有する画像ブロックでは、量子化をより粗くしても、見る人には知覚されにくいことが知られているので、各ブロックの量子化ステップを、アクティビティのレベルに応じて適切に調整することができる。アクティビティを考慮することにより、再生画像の知覚的な画質を維持したまま、圧縮率をより高めることができる。
【００２２】
ＤＰＣＭ及びＤＣＴ量子化の試し符号処理により、所要の符号化ビットレートに基づいた所定のフレームのターゲットビット数によって制限されるＭＢのターゲットビット数を計算する。各ＭＢに対して最少の符号化ビットが得られるモード（ＤＣＴかＤＰＣＭ）が選択される。ビット割当器４００は、信号４０５をターゲット挿入器５００に出力する。この信号４０５は、各マクロブロックに対して選択された符号化モードと、２分探索器７００で使用される量子化除数Ｑ＿ＳＣＡＬＥの値Ｑ＿ＢＡＳＥと、各マクロブロックに対するターゲットビット数（ｂｉｔ　ｃｏｕｎｔ　ｔｒａｇｅｔ）とに関する情報を含んでいる。信号４０５に含まれる情報は、ターゲット挿入器５００によって、対応する遅延された画像データのビットストリームに付加される。ターゲット挿入器５００は、２つの信号５０５Ａ、５０５Ｂを出力し、これらの信号はＤＣＴ変換器６００に入力として供給される。
【００２３】
ＤＣＴ変換器６００で再びＤＣＴ係数を計算するが、今回は画像データの遅延バージョンに基づき計算を行う。ＤＣＴ変換器６００は、データを２分探索器７００に出力する。２分探索器７００は、ＤＣＴ量子化符号化すべき各ＭＢに対して２回目の（ｓｅｃｏｎｄ　ｓｔａｇｅ）Ｑ割当を実行するとともに、２分探索法を用いて、各マクロブロックに対して適切な量子化除数を測定する。２分探索器７００は、ビット割当器４００で使用された分解能より高い分解能で（使用可能な量子化除数の範囲内で）量子化除数を測定する。実際には、５回の２分探索における開始点を定めるためにＱ＿ＢＡＳＥを用いて、ＤＣＴモードの各マクロブロックに対してより高い分解能の量子化ステップＱ＿ＡＬＬＯＣが選択されるようにする。ＤＰＣＭモードのマクロブロックは、バイパス機能によって２分探索器７００を通過するので、その出力においてデータは変更されてない。
【００２４】
２分探索器７００からの出力は、ＤＣＴモードの各マクロブロックに対する量子化ステップの値Ｑ＿ＡＬＬＯＣを含み、逆戻り探索（ｂａｃｋｓｅａｒｃｈ）器８００に供給される。逆戻り探索器８００は、各ＭＢに対して選択された値Ｑ＿ＡＬＬＯＣが符号化のための「最良」の量子化スケールであることを検査（ｃｈｅｃｋ）する。上述したように、前に１回以上の符号化／復号化サイクルを経験したことがある画像データについては、所定のターゲットビット数（ｔａｒｇｅｔ　ｂｉｔ　ｃｏｕｎｔ）を達成できる最も粗さが小さい量子化が必ずしもそのマクロブロックに対して可能な限り小さい量子化誤差をもたらさない。代わりに、最小の量子化誤差は、前回の符号化／復号化サイクルで使用された量子化除数に略等しい量子化除数を用いることによって達成される可能性が高い。したがって、逆戻り探索器８００は、値Ｑ＿ＡＬＬＯＣから始まり、より粗い量子化となる様々な量子化除数に対する量子化誤差を評価する。逆戻り探索器８００は、可能な限り最も小さい量子化誤差を実際に発生する量子化ステップＱ＿ＦＩＮＡＬを決定する（ｄｅｔｅｒｍｉｎｅ）。試し量子化はＤＣＴモードのマクロブロックに対してのみ行われ、ＤＰＣＭモードのマクロブロックに対してはバイパス機能が適用される。
【００２５】
逆戻り探索器８００から出力される、選択された量子化ステップＱ＿ＦＩＮＡＬと、ＤＣＴ符号化器６００で生成されたＤＣＴブロックは、量子化器９００に供給され、ここで、最終的な量子化が実行される。量子化処理は、以下のようにして行われる。
【００２６】
ＤＣＴモードの符号化では、各８Ｈ×８Ｖブロックの１つのＤＣ係数は、次式に従って量子化される。
【００２７】
Ｑ（ＤＣ）＝ＤＣ／（ＤＣ＿ＱＵＡＮＴ＊ＤＣＴ＿ＳＣＡＬＥＲ）
ここで、ＤＣは量子化前の係数であり、ＤＣ＿ＱＵＡＮＴは、方式（ｓｙｓｔｅｍ）によって設定されている量子化ファクタ（ｑｕａｎｔｉｓａｔｉｏｎ　ｆａｃｔｅｒ）であり、全てのＭＢを量子化するのに用いられる。ＤＣ＿ＱＵＡＮＴは、下記表に示すように、ＤＣ＿ＰＲＥＣＩＳＩＯＮから決定される。
【００２８】
【表１】
2004129204.tif 000003
【００２９】
ＤＣ＿ＰＲＥＣＩＳＩＯＮは、各フレームに対して固定値、好ましくは００に設定されているる。
【００３０】
ＤＣＴ＿ＳＣＡＬＥＲは、量子化除数パラメータＤＣＴ＿ＰＲＥＣＩＳＩＯＮを指数とすることによって決定される量子化ファクタであり、ＤＣＴ＿ＳＣＡＬＥＲ＝２ＤＣＴ＿ＰＲＥＣＩＳＩＯＮである。この具体例では、規格（ｃｏｎｖｅｎｔｉｎ）が用いられ、量子化除数パラメータＤＣＴ＿ＰＲＥＣＩＳＩＯＮは４つの可能な値０、１、２、３を取り、３は最も粗い量子化に対応している。なお、ＭＰＥＧスタジオプロファイル標準規格では、これとは異なり、ＤＣＴ＿ＰＲＥＣＩＳＩＯＮ＝０が最も粗い量子化に対応し、ＤＣＴ＿ＰＲＥＣＩＳＩＯＮ＝３が最小粗さの量子化に対応している。
【００３１】
同様に、ブロックの６３個のＡＣ係数は、次式に従って量子化される。
【００３２】
Ｑ（ＡＣ）＝（ＡＣ＊１６）／（Ｑ＿ＭＡＴＲＩＸ＊ＡＣ＿ＱＵＡＮＴＩＳＥ＊ＤＣＴ＿ＳＣＡＬＥＲ）
ここで、ＡＣは量子化前の係数であり、Ｑ＿ＭＡＴＲＩＸは、ＤＣＴブロックの各要素に１つ１つが対応した６４個の重みの配列である。ＡＣ＿ＱＵＡＮＴＩＳＥは、量子化除数Ｑ＿ＳＣＡＬＥとＮＯＲＭ＿ＡＣＴの積である。量子化除数Ｑ＿ＳＣＡＬＥは、Ｑ＿ＳＣＡＬＥ＿ＴＹＰＥによって定まる線形量子化スケール又は非線形量子化スケールに対応したファクタである。各Ｑ＿ＳＣＡＬＥ＿ＴＹＰＥは、Ｑ＿ＳＣＡＬＥ＿ＣＯＤＥ（１）〜Ｑ＿ＳＣＡＬＥ＿ＣＯＤＥ（３１）で示される３１個の可能な値からなる。図４の表は、全３１個のＱ＿ＳＣＡＬＥ＿ＣＯＤＥに対する各Ｑ＿ＳＣＡＬＥ＿ＴＹＰＥに対応した量子化除数Ｑ＿ＳＣＡＬＥの値を示したものである。上記式において、ＮＯＲＭ＿ＡＣＴは、正規化されたアクティビティファクタであり、「アクティビティオン（ａｃｔｉｖｉｔｙ　ｏｎ）」の場合に０．５〜２．０の範囲にあるが、「アクティビティオフ（ａｃｔｉｖｉｔｙ　ｏｆｆ）」の場合は１に等しくなる。
【００３３】
ＡＣ＿ＱＵＡＮＴＩＳＥ＝ＮＯＲＭ＿ＡＣＴ＊Ｑ＿ＳＣＡＬＥとし、除数の一部として組み込まれる前に、最も近い量子化除数Ｑ＿ＳＣＡＬＥ（すなわち、図４の表におけるＱ＿ＳＣＡＬＥ＿ＣＯＤＥに対応するＱ＿ＳＣＡＬＥ）に丸められる。
【００３４】
量子化の結果Ｑ（ＤＣ）、Ｑ（ＡＣ）は、正規無限丸め（ｎｏｒｍａｌ　ｉｎｆｉｎｉｔｙ　ｒｏｕｎｄｉｎｇ）と呼ばれる方法で丸められる。この方法は、０．５より小さい正数を（ゼロに）切り捨て、０．５以上の整数を正の無限大に切り上げ、−０．５より大きな負数をゼロに切り上げ、−０．５以下の負数を負の無限大に切り捨てることにより丸める。
【００３５】
ビット割当器４００、２分探索器７００及び逆戻り探索器８００のそれぞれは、量子化器９００によって実行される量子化処理と同じように、量子化処理を実行する。しかしながら、２分探索器７００及び逆戻り探索器８００では、ファクタＮＯＲＭ＿ＡＣＴは、常に１に設定される。ビット割当器４００によって実行されるビット割当処理の間のみ、ファクタＮＯＲＭ＿ＡＣＴは１以外の値を取る。ビット割当中に生成されるＭＢターゲットは、アクティビティを考慮しているので、後段でこれを考慮する必要はない。
【００３６】
量子化器９００から出力される量子化データは、エントロピー符号器１０００に供給され、ここで、無ひずみデータ圧縮が、エントロピー符号化の標準原理に基づき適用される。この具体例では、ハフマン符号化を使用しており、出現頻度の高い値は短い符号で、出現頻度の低い値は長い符号で表現される。
【００３７】
エントロピー符号器１０００の出力は、シャッフル部１００内のパッキング器１５０に供給される。パッキング器１５０は、外部ＳＤＲＡＭ２００と協働して、エントロピー符号化器１０００によって生成された可変長符号化データを固定長の同期ブロック（ｓｙｎｃ−ｂｌｏｃｋ）にパックする。同期ブロックは、画像再生の際、独立して再生される最小のデータブロックである。
【００３８】
パッキング機能は、ＳＤＲＡＭ２００の読出及び書込アドレスを操作することによって実現される。各ＭＢＵをＳＤＲＡＭ内の固定パッキング領域（ｆｉｘｅｄ　ｐａｃｋｉｎｇ　ｓｐａｃｅ）に割り当て、更にそれを、各ＭＢ用の名目パッキング領域（ｎｏｍｉｎａｌ　ｐａｃｋｉｎｇ　ｓｐａｃｅ）に分割する。個々のワード長から算出される又はエントロピー符号化器１０００から直接パッキング器１５０に供給される各ＭＢの全体の長さも記憶する必要がある。符号化装置１０からの出力は、同期ブロック１のデータ出力ＳＢ１、同期ブロック２のデータ出力ＳＢ２からなる。符号化処理で使用した量子化除数の情報も復号装置３０に送られる。
【００３９】
図５は、図２の復号装置の構成を示すブロック図である。復号装置３０は、符号化処理の逆処理を行うものであり、アンシャッフル部２０１０と、アンパック部２０２０と、外部ＳＤＲＡＭ２１００と、エントロピー復号器２２００と、逆量子化器２３００と、逆ＤＣＴ変換器２４００とを備える。同期ブロックのデータ信号ＳＢ１、ＳＢ２は、記録媒体から読み出され、あるいはデータ伝送ネットワークを介して受信されて、アンパック部２０２０に供給され、アンパック部２０２０は、外部ＳＤＲＡＭ２１００の読出及び書込により、アンパッキング機能を実行する。アンパックデータはエントロピー復号器２２００に供給され、エントロピー復号器２２００は、ハフマン符号化の逆処理を実行して量子化係数を再生し、逆量子化器２３００に供給する。逆量子化器２３００は、符号化装置１０から供給された量子化除数に関する情報を用いて、量子化係数に適切な量子化除数を乗算して元のＤＣＴ係数の近似値を得る。この逆量子化処理は、ＤＣＴ係数の元の精度を回復するものではなく、量子化は「有ひずみ（ｌｏｓｓｙ）」圧縮技術である。逆量子化器２３００の出力は、逆ＤＣＴ変換器２４００に供給され、逆ＤＣＴ変換器２４００は、離散コサイン逆変換を用い、周波数領域のＤＣＴ係数の各ブロックを処理して空間領域の画像ブロック情報を再生する。逆ＤＣＴ変換器２４００の出力は、量子化の結果には情報消失があるため、符号化前の画素ブロックと等しくない。最後に、逆ＤＣＴ変換器２４００の出力はアンシャッフル部２０１０に供給され、ここで、データはアンシャッフルされ、符号化前の画像ブロックの順序が再現される。アンシャッフル部２０１０の出力は、３つの色成分ビデオ信号ＲＧＢからなり、これから画像を再生することができる。
【００４０】
図６は、シャッフル部１００内に設けられたＤＣＴ＿ＰＲＥＣＩＳＩＯＮ検出器（図示せず）によって実行される計算を説明するための図である。ＤＣＴ＿ＰＲＥＣＩＳＩＯＮ検出器は、入力ビデオデータがソースデータか非ソースデータか判定し、非ソースデータの場合、前の符号化／復号化サイクルで使用したＤＣＴ＿ＰＲＥＣＩＳＩＯＮインデックスを検出する。量子化除数パラメータＤＣＴ＿ＰＲＥＣＩＳＩＯＮの値は、ＤＣ係数とＡＣ係数の両方に対する量子化に影響を与える。ＤＣ＿ＱＵＡＮＴの値が既知であるとすると（この具体例では各フレームに対してＤＣ＿ＰＲＥＣＩＳＩＯＮを固定値００に設定しているので、ＤＣ＿ＱＵＡＮＴ＝８である）、ＤＣ丸めの影響を解析することにより、前世代で使用された量子化除数パラメータＤＣＴ＿ＰＲＥＣＩＳＩＯＮの値を検出することができる。ＤＣＴ＿ＰＲＥＣＩＳＩＯＮ検出器は、入力ビデオデータが供給され、このビデオデータのＤＣ量子化の解析を行う。画像フィールド又はフレームの各ＤＣＴブロックについて、６４画素からなるブロックの各画素について６つの最下位ビット（ＬＳＢ）の値の和を求め、各ブロックに対する６ビットの値ＤＣ［５：０］を生成する。特定のＤＣ［５：０］の出現頻度は以下のアルゴリズムに従って求められる。
【００４１】
Ｓ０＝ＤＣ［５：０］の出現回数＝００　００００
Ｓ１＝ＤＣ［５：０］の出現回数＝１０　００００
Ｓ２＝ＤＣ［５：０］の出現回数＝ｘ１　００００
Ｓ３＝ＤＣ［５：０］の出現回数＝ｘｘ　１０００
Ｓ４＝ＤＣ［５：０］の出現回数＝ｘｘ　ｘ１００
ここで、ｘは０か１を表す。実質上、ＤＣ［５：０］のインスタンスの数は、６４で割り切れれば和Ｓ０に対応し、（６４でなく）３２で割り切れれば和Ｓ１に対応し、（３２でなく）１６で割り切れれば和Ｓ２に対応し、（１６でなく）８で割り切れれば和Ｓ３に対応し、（８でなく）４で割り切れればＳ４に対応する。図７は、特定のＤＣ［５：０］値の出現頻度の計算を模式的に示している。
【００４２】
この具体例において、５つの和Ｓ０〜Ｓ４は、全てのビデオ成分からの全ＤＣＴブロックを含んでいる。しかしながら、他の具体例として、和Ｓ０〜Ｓ４を各成分（ＲＧＢ又はＹＣｂＣｒ）について別々に計算して、最終的な量子化除数パラメータＤＣＴ＿ＰＲＥＣＩＳＩＯＮの決定を、例えば多数決を用いて合成してもよい。
【００４３】
和Ｓ０〜Ｓ４を一旦算出したら、４つの所定の閾値ｔｈ１〜ｔｈ４を用いて、前世代で使用した量子化除数パラメータＤＣＴ＿ＰＲＥＣＩＳＩＯＮを検出し、予測値ＤＣＴ＿ＰＲＥＣ＿ＤＥＴＥＣＴＥＤを生成する。以下の疑似コードは使用したアルゴリズムを表している。
【００４４】
2004129204.tif 000004
上述のアルゴリズムは、前世代と現世代の両方においてＤＣ＿ＱＵＡＮＴ＝８（ＤＣＴ＿ＰＲＥＣＩＳＩＯＮ＝００）を想定している。Ｑ（ＤＣ）＝ＤＣ／ＤＣ＿ＱＵＡＮＴ＊２ＤＣＴ＿ＰＲＥＣ且つＤＣ＿ＱＵＡＮＴ＝８であるので、ＤＣデータについて除数、例えば８を検出したときは、更なる量子化はなく、上述のアルゴリズムにおいてＤＣＴ＿ＰＲＥＣ＿ＤＥＴＥＣＴＥＤ＝０であることが導かれる。なお、このアルゴリズムは前世代と現世代の双方でＤＣ＿ＱＵＡＮＴを考慮するように適合化される。
【００４５】
和Ｓ０が閾値ｔｈ１と和Ｓ１の積より大きいときは、ＤＣデータの検出された除数は６４＝８＊２３であり、アルゴリズムは、最も粗い量子化除数パラメータＤＣＴ＿ＰＲＥＣＩＳＩＯＮでの量子化に対応したＤＣＴ＿ＰＲＥＣ＿ＤＥＴＥＣＴＥＤ＝３と設定する。（Ｓ０＋Ｓ１）の値が閾値ｔｈ２と和Ｓ２の積より大きいときは、ＤＣデータの検出された除数は３２＝８＊２２であり、アルゴリズムはＤＣＴ＿ＰＲＥＣ＿ＤＥＴＥＣＴＥＤ＝２と設定する。（Ｓ０＋Ｓ１＋Ｓ２）の値が閾値ｔｈ３と和Ｓ３の値の積より大きいときは、ＤＣデータの検出された除数は１６＝８＊２であり、アルゴリズムはＤＣＴ＿ＰＲＥＣ＿ＤＥＴＥＣＴＥＤ＝１と設定する。最後に、（Ｓ０＋Ｓ１＋Ｓ２＋Ｓ３）の値が閾値ｔｈ４と和Ｓ４の値の積より大きいときは、ＤＣデータの検出除数は８であり、アルゴリズムは、粗さが最小の量子化除数パラメータＤＣＴ＿ＰＲＥＣＩＳＩＯＮでの量子化に対応したＤＣＴ＿ＰＲＥＣ＿ＤＥＴＥＣＴＥＤ＝０と設定する。この特定の具体例において、閾値はｔｈ１＝ｔｈ２＝ｔｈ３＝１６であり、ｔｈ４＝２である。閾値は試験画像シーケンスに対する計算を実行することにより経験的に求められる。このアルゴリズムは、量子化除数パラメータＤＣＴ＿ＰＲＥＣＩＳＩＯＮの前の値を検出するために、画素値に対する丸め効果の重大性を本質的に定量化している。
【００４６】
ＤＣＴ＿ＰＲＥＣＩＳＩＯＮ検出器は、前に１回以上の符号化／復号化サイクルを経験したことがあるか否かを表す「ソース」／「非ソース」信号を出力し、この信号は、図３のビット割当器４００に入力として供給され、ターゲットビット数の算出に用いられる。
【００４７】
図７は、図２のビット割当器４００の具体的な構成を示すブロック図である。このビット割当器４００は、３つの主要な機能を有し、第１の機能では、各マクロブロック毎に無ひずみＤＣＰＭと有ひずみＤＣＴ符号化という２つの利用可能な選択肢の中から符号化モードを選択し、第２の機能では、システムの所要のターゲットビットレートから算出される対応したマクロブロックユニットに関する同様のターゲットに基づいて、各マクロブロックに対するターゲットビット数ＭＢ＿ＴＡＲＧＥＴを算出し、第３の機能では、２分探索器７００で実行される２分探索における量子化除数Ｑ＿ＳＣＡＬＥの開始目盛り（ｓｔａｒｔｉｎｇ　ｓｃａｌｅ）となるように定義される値Ｑ＿ＢＡＳＥを算出する。２分探索器７００は、量子化除数Ｑ＿ＳＣＡＬＥの値Ｑ＿ＡＬＬＯＣを測定し、これは、開始点の値Ｑ＿ＢＡＳＥを得るのに使用したよりも高い分解能で量子化除数Ｑ＿ＳＣＡＬＥを探索することによって得られる。
【００４８】
シャッフル部１００から出力されるシャッフルされた画像データ信号Ｓ＿ＯＰ＿Ｄ１、Ｓ＿ＯＰ＿Ｄ２は、ビット割当器４００に入力として供給される。これらの入力信号は、ラスタ走査された１２ビットのビデオサンプルの８Ｈ×８ＶＤＣＴブロックからなる。パラメータ予測回路により生成される最終的な量子化除数パラメータＤＣＴ＿ＰＲＥＣＩＳＩＯＮ、Ｑ＿ＳＴＡＲＴの値もビット割当器４００に入力として供給される。ビット割当器４００は、ＤＰＣＭリフォーマット器４１０と、ＤＰＣＭ器４２０と、ゴーロン（Ｇｏｌｏｍｂ）長器４３０と、ＤＣＴ変換器４４０と、量子化器４５２及びハフマン長器４５４からなる有ひずみ符号化器４５０と、アクティビティ器４６０と、決定論理ユニット４７０とを備える。決定論理ユニット４７０は、ターゲット挿入器５００に入力を供給する。
【００４９】
ビット割当器４００は、この具体例においては、２０４個のＭＢからなるマクロユニットの試し符号化に基づき符号化の決定を行う。無ひずみＤＰＣＭと有ひずみＤＣＴを選択肢とする符号化モードの決定は、１回のＤＰＣＭ符号化処理（ＤＰＣＭリフォーマット器４１０、ＤＰＣＭ器４２０及びゴーロン長器４３０と協調して実行される）に基づき、更に、ＤＣＴ変換器４４０における１回の離散コサイン変換とそれに続く有ひずみ符号化ユニット４５０を介した６サイクルとを含む６回のＤＣＴ試し符号化処理に基づいて、行われる。アクティビティ器４６０は、量子化器４５２がデータに適用する量子化除数を調整する。アクティビティ器４６０で実行される演算について、以下に詳述する。
【００５０】
決定論理器４７０には、ＤＰＣＭ符号化のエントロピー符号化処理を行うゴーロン長器４３０の出力が供給されるとともに、ＤＣＴ符号化のエントロピー符号処理を行うハフマン長器４５４の出力が供給される。決定論理ユニット４７０は、ＤＰＣＭ試し符号化とＤＣＴ試し符号化との結果を比較する。無ひずみＤＰＣＭは、マクロブロックに対して全体のビット数がより少ない場合のみ、選択される。また、決定論理ユニット４７０は、マクロブロックユニットとマクロブロックの双方についてターゲットビット数を算出する。
【００５１】
アクティビティ器４６０は、ＤＣＴモードの符号化回路の一部を構成し、画像ブロックの画素の分散に基づきアクティビティの尺度を算出する。より高いアクティビティレベルを有する画像ブロックでは、量子化をより粗くしても、見る人には知覚されにくいことが知られている。各ブロックに対する量子化ステップは、ビット割当器４００の量子化器４５２で使用される量子化除数Ｑ＿ＳＣＡＬＥを、高いアクティビティレベルのブロックが粗く量子化されるように、適切に調整することによりオフセット（ｏｆｆｓｅｔ）することができる。後述するように、ビット割当処理のために使用されるＱ＿ＳＣＡＬＥ＿ＣＯＤＥは、「アクティビティオン」か「アクティビティオフ」の状態に依存する。更に、アクティビティファクタＮＯＲＭ＿ＡＣＴは、上述のＤＣＴのＡＣ係数Ｑ（ＡＣ）の量子化の式の分母に現れている。
【００５２】
アクティビティは、各マクロブロックに対して１回ずつだけ計算される。パラメータＩｎｔｒａＭＡＤの値は、マクロブロック内の各８Ｈ×８ＶＤＣＴブロックに対して、ＹＣｂＣｒモードでは輝度（Ｙ）ＤＣＴブロックのみ、ＲＧＢモードではＲ、Ｇ、Ｂのブロックが計算される。パラメータＩｎｔｒａＭＡＤは次のように定義される。
【００５３】
【数１】
2004129204.tif 000005
【００５４】
ここで、ｄｃｔ［ｉ，ｊ］は、ｊ番目のＤＣＴブロックのｉ番目の画素の画素値である。パラメータｄｃｔ＿ｄｃ［ｊ］は、８Ｈ×８ＶＤＣＴブロックについての（且つ所定の信号成分についての）ｄｃｔ［ｉ，ｊ］の平均値であり、次式で与えられる。
【００５５】
【数２】
2004129204.tif 000006
【００５６】
マクロブロック内の全てのＹ又はＲＧＢのＤＣＴブロックに対するパラメータＩｎｔｒａＭＡＤの最小値は、次式で与えられる。
【００５７】
【数３】
2004129204.tif 000007
【００５８】
アクティビティＡＣＴは、
ＡＣＴ＝１＋ＭｉｎＭＡＤ
で与えられる。アクティビティＡＣＴの値は１から数千に及ぶので、アクティビティＡＣＴを正規化して所定の範囲内に収まるようにする。この具体例では、アクティビティＡＣＴを前回のマクロブロックユニットのデータによって正規化し、０．５〜２の範囲に収まるＮＯＲＭ＿ＡＣＴを得ている。
【００５９】
ＮＯＲＭ＿ＡＣＴ＝（２＊ＡＣＴ＋ＡＶＧ＿ＡＣＴ）／（ＡＣＴ＋２＊ＡＶＧ＿ＡＣＴ）
ここで、ＡＶＧ＿ＡＣＴ＝前ＭＢＵからのアクティビティＡＣＴの平均である。
【００６０】
画像シーケンスの開始時、あるいはシーンの変化を（標準的方法により）検出したときには、量子化除数パラメータＱ＿ＳＴＡＲＴ、ＤＣＴ＿ＰＲＥＣＩＳＩＯＮに依存したデフォルト値ＤＥＦＡＵＬＴ＿ＡＶＧ＿ＡＣＴをＡＶＧ＿ＡＣＴの代わりに使用する。任意のフレーム（シーケンスの最初のフレームは除く）内の最初のＭＢＵに対しては、前フレーム内の全てのＭＢＵに対するアクティビティＡＣＴの平均を表す値ＦＲＭ＿ＡＶＧ＿ＡＣＴをＡＶＧ＿ＡＣＴの代わりに使用する。この具体例では、アクティビティＡＣＴを０．５〜２の範囲に収まるように正規化しているが、代わりに次式を用いることにより、ｐ／ｑ〜ｑ／ｐである任意の範囲に正規化することができる。
【００６１】
ＮＯＲＭ＿ＡＣＴ＝（ｑ＊ＡＣＴ＋ｐ＊ＡＶＧ＿ＡＣＴ）／（ｐ＊ＡＣＴ＋ｑ＊ＡＶＧ＿ＡＣＴ）
したがって、ＮＯＲＭ＿ＡＣＴの範囲を０．５〜２となるように選択する場合、パラメータｐ、ｑは、それぞれ値１、２である。
【００６２】
符号化の多数世代に亘る反復性を良くするために、ＮＯＲＭ＿ＡＣＴは固定数のレベルに制限される。０．５〜２．０の範囲に対して、ＮＯＲＭ＿ＡＣＴは８個のレベル（４／８、５／８、６／８、７／８、１，４／３、５／３、２）に制限される。
【００６３】
図８は、各ＭＢＵに対し、本発明の具体例に基づくビット割当器４００によって実行されるアルゴリズムを表すフローチャートである。ステップ１は、ＤＰＣＭリフォーマット器４１０、ＤＰＣＭ器４２０及びゴーロン長器４３０の協調動作で実行される。ステップ２Ａ〜２Ｄは、量子化器４５２により実行され、ステップ３〜５は、決定論理器４７０により実行される。
【００６４】
ステップ１において、ＭＢＵ内の全ＭＢに対して１回の無ひずみＤＰＣＭ試し符号化を実行し、各ＭＢについてＤＰＣＭ符号化によって生成されるビット数ＭＢ＿ＤＰＣＭ＿ＢＩＴを測定する。
【００６５】
ステップ２Ａにおいて、ＭＢＵ内の全ＭＢに対して６回の有ひずみＤＣＴ符号化を実行して、各ブロック及び６個の試し量子化除数Ｑ＿ＳＣＡＬＥ（１）〜（６）の各々について、ＭＢの有ひずみＤＣＴ符号化によって生成されるビット数ＭＢ＿ＤＣＴ＿ＢＩＴＳ（Ｑ＿ＳＣＡＬＥ）を測定する。量子化除数Ｑ＿ＳＣＡＬＥの各値は、３１個のＱ＿ＳＣＡＬＥ＿ＣＯＤＥのいずれか１つと線形又は非線形であるＱ＿ＳＣＡＬＥ＿ＴＹＰＥとの組合せにより定まる。３１個の使用可能なＱ＿ＳＣＡＬＥ＿ＣＯＤＥに関する量子化除数Ｑ＿ＳＣＡＬＥの全範囲を完全に走査する代わりに、Ｑ＿ＳＣＡＬＥ＿ＣＯＤＥのサブセット（ｓｕｂｓｅｔ：以下、ＳＳという）を選択する。ＳＳは、量子化除数パラメータＤＣＴ＿ＰＲＥＣＩＳＩＯＮの値とアクティビティがオンかオフの両方を考慮して定められる。例えば、ＤＣＴ＿ＰＲＥＣＩＳＩＯＮ＝１でアクティビティがオフの場合、サブセットは、
ＳＳ＝［２，３，５，７，１０，１５，２２，３１］
となる。一方、アクティビティがオンの場合（この場合、ＮＯＲＭ＿ＡＣＴは０．５〜２の範囲にある）、サブセットは、
ＳＳ＝［２，３，５，７，１０，１５］
で与えられる。
【００６６】
下記表２は、「アクティビティオン」と「アクティビティオフ」の両方に対する量子化除数パラメータＤＣＴ＿ＰＲＥＣＩＳＩＯＮの各値について、本発明の具体例で用いられたビット割当用サブセットを示したものである。
【００６７】
【表２】
2004129204.tif 000008
【００６８】
試し量子化で使用する６個の量子化除数Ｑ＿ＳＣＡＬＥ（１）〜（６）は、該当するＳＳから取り出した６個のＱ＿ＳＣＡＬＥ＿ＣＯＤＥに関する量子化除数に対応している。なお、各ＳＳは、殆どの場合、６より多い数のＱ＿ＳＣＡＬＥ＿ＣＯＤＥを含んでいる。量子化除数パラメータＱ＿ＳＴＡＲＴの値を用いて、サブセットの中から試し量子化で使用する６個のＱ＿ＳＣＡＬＥ＿ＣＯＤＥを選択する。
【００６９】
サブセット内で使用可能な最小のＱ＿ＳＣＡＬＥ＿ＣＯＤＥは、下記式の量子化ファクタＭＩＮＩＭＵＭ＿Ｑを表すコードであり、
ＭＩＮＩＭＵＭ＿Ｑ＝２（ＤＣＴ＿ＰＲＥＣＩＳＩＯＮ）
あるいは、このコードが存在しないときは、使用可能な最小のＱ＿ＳＣＡＬＥ＿ＣＯＤＥは、量子化ファクタＭＩＮＩＭＵＭ＿Ｑよりも大きな数の中で最も小さなＱ＿ＳＣＡＬＥ＿ＣＯＤＥである。
【００７０】
ステップ２Ｂにおいて、量子化除数パラメータＤＣＴ＿ＰＲＥＣＩＳＩＯＮの値に関係する量子化除数パラメータＱ＿ＳＴＡＲＴの誤差を算出し、この誤差は、
Ｑ＿ＳＴＡＲＴ＿ＥＲＲＯＲ＝２４／（３−２ＤＣＴ＿ＰＲＥＣＩＳＩＯＮ）
で与えられるので、量子化の粗さが小さくなる量子化除数パラメータＤＣＴ＿ＰＲＥＣＩＳＩＯＮの値に対して、Ｑ＿ＳＴＡＲＴの誤差は大きくなる。
【００７１】
ステップ２Ｃにおいて、量子化除数パラメータＱ＿ＳＴＡＲＴから誤差Ｑ＿ＳＴＡＲＴ＿ＥＲＲＯＲを減算することによってＱ＿ＳＣＡＬＥ＿ＭＩＮを算出するとともに、図４のルックアップテーブルからＱ＿ＳＣＡＬＥ＿ＭＩＮに関するＱ＿ＳＣＡＬＥ＿ＣＯＤＥ及びＱ＿ＳＣＡＬＥ＿ＣＯＤＥ＿ＭＩＮを求める。サブセットの中のＱ＿ＳＣＡＬＥ＿ＣＯＤＥ＿ＭＩＮ以下の、一番近いＱ＿ＳＣＡＬＥ＿ＣＯＤＥを識別し、このＱ＿ＳＣＡＬＥ＿ＣＯＤＥに対応した量子化除数を、６個の試し量子化パラメータの中の１番目、すなわち試し量子化除数Ｑ＿ＳＣＡＬＥ（１）として定める。なお、サブセット中にＱ＿ＳＣＡＬＥ＿ＣＯＤＥ＿ＭＩＮ以下のＱ＿ＳＣＡＬＥ＿ＣＯＤＥがない場合は、試し量子化除数Ｑ＿ＳＣＡＬＥ（１）を、サブセット中の最も小さなＱ＿ＳＣＡＬＥ＿ＣＯＤＥに対応した量子化ファクタに設定する。
【００７２】
ステップ２Ｄにおいて、残る５個の試し量子化除数Ｑ＿ＳＣＡＬＥ（２）〜（６）を、サブセット中の試し量子化除数Ｑ＿ＳＣＡＬＥ（１）よりも順に大きな５個Ｑ＿ＳＣＡＬＥ＿ＣＯＤＥに割り当てる。サブセット中にこれを満足する十分な数のＱ＿ＳＣＡＬＥ＿ＣＯＤＥがないときは、試し量子化除数Ｑ＿ＳＣＡＬＥ（６）を、サブセット中の最大のＱ＿ＳＣＡＬＥ＿ＣＯＤＥに設定するとともに、試し量子化除数Ｑ＿ＳＣＡＬＥ（１）〜（５）を、サブセット中の試し量子化除数Ｑ＿ＳＣＡＬＥ（６）よりも順に小さな５個のＱ＿ＳＣＡＬＥ＿ＣＯＤＥに設定する。
【００７３】
ステップ３において、６回の試しＤＣＴ量子化を行い、マクロブロックユニット内の全てのマクロブロックに亘るＭＢ＿ＤＣＴ＿ＢＩＴＳ（Ｑ＿ＳＣＡＬＥ）の値の総和を求めて、６個の試し量子化除数Ｑ＿ＳＣＡＬＥ（１）〜（６）の各々に対する値ＭＢＵ＿ＤＣＴ＿ＢＩＴＳ（Ｑ＿ＳＣＡＬＥ）を生成する。ＭＢＵ毎のターゲットビット数は、各画像フレーム（又はフィールド）毎に定めた所定のＦＲＡＭＥ＿ＴＡＲＧＥＴから、
ＭＢＵ＿ＴＡＲＧＥＴ＝ＦＲＡＭＥ＿ＴＡＲＧＥＴ／４０
により算出される。
【００７４】
既知の方式においては、ＦＲＡＭＥ＿ＴＡＲＧＥＴは、所要の符号化ビットレートにより完全に決まっている。しかしながら、本発明の具体例では、ＦＲＡＭＥ＿ＴＡＲＧＥＴを、所要の符号化ビットレートからだけではなく、ビデオデータが「ソース」か「非ソース」かにも依存して割り当てる。入力データを「ソース」データであると判定した場合、所要のビットレートを、僅かに減らすように調整することによって意図的に落とし、「ソース」データに対するＦＲＡＭＥ＿ＴＡＲＧＥＴも有効に下げるように調整する。この具体例において、下げる調整は２．５％である。「ソース」入力データに対するＦＲＡＭＥ＿ＴＡＲＧＥＴを特に低減した結果として、そのソースデータに対してビット割当器４００によって算出されるマクロブロックのターゲットビット数は減少し、第１世代のＱ＿ＡＬＬＯＣ＿ＧＥＮ１に対する（２分探索器７００によって算出される）Ｑ＿ＡＬＬＯＣは増加し、ＦＲＡＭＥ＿ＴＡＲＧＥＴを低減しなかった場合に比べて僅かながら粗い、最終的な量子化Ｑ＿ＦＩＮＡＬ＿ＧＥＮ１を第１世代の再生画像に対して適用することになる。しかしながら、第１世代画像の画質の若干の低下は、ＦＲＡＭＥ＿ＴＡＲＧＥＴを低減した画像データを更に圧縮／伸長する際に得られる利点によって相殺される。このデータの第２世代及びそれ以降の世代における符号化では、ＦＲＡＭＥ＿ＴＡＲＧＥＴを調整しない。第２世代の調整された値Ｑ＿ＡＬＬＯＣ＿ＧＥＮ２＿ＡＤＪＵＳＴＥＤは、Ｑ＿ＦＩＮＡＬ＿ＧＥＮ１よりも小さくなる傾向が、調整しなかった値Ｑ＿ＡＬＬＯＣ＿ＧＥＮ２よりも遙かに強い。これを図９を参照して説明する。図９に示すように、従来の逆戻り探索の開始点がＱ＿ＦＩＮＡＬ＿ＧＥＮ１を見失っているのに対し、調整された逆戻り探索、すなわち第１世代のＦＲＡＭＥ＿ＴＡＲＧＥＴの調整に基づく２分探索は、その試し量子化除数Ｑ＿ＳＣＡＬＥの範囲内にＱ＿ＦＩＮＡＬ＿ＧＥＮ１を含んでいる。したがって、調整された逆戻り探索処理は、第２（及びそれ以降の）世代について可能な最良の画質を与えるＱ＿ＦＩＮＡＬ＿ＧＥＮ２＝Ｑ＿ＦＩＮＡＬ＿ＧＥＮ１を発見する可能性が高い。なお、第２世代の入力データの符号化際に、第１世代の符号化の所要レートは必ずしも分かっていない。
【００７５】
ＭＢＵ＿ＤＣＴ＿ＢＩＴＳ（Ｑ＿ＳＣＡＬＥ）の６個の値からなるセットをターゲットビット数ＭＢＵ＿ＴＡＲＧＥＴと比較し、ターゲットビット数ＭＢＵ＿ＴＡＲＧＥＴの直ぐ上と直ぐ下にある、ＭＢＵ＿ＤＣＴ＿ＢＩＴＳ（Ｑ＿ＳＣＡＬＥ）の２つの値Ｂ＿ＵＭＢＵ、Ｂ＿ＬＭＢＵをそれぞれ次のように定義する。
【００７６】
Ｂ＿ＵＭＢＵ≡ＭＢＵ＿ＤＣＴ＿ＢＩＴＳ（Ｑ＿ＳＣＡＬＥ（ｎ））＞ＭＢＵ＿ＴＡＲＧＥＴ
Ｂ＿ＬＭＢＵ≡ＭＢＵ＿ＤＣＴ＿ＢＩＴＳ（Ｑ＿ＳＣＡＬＥ（ｎ＋１））≦ＭＢＵ＿ＴＡＲＧＥＴ
図１０は、量子化除数Ｑ＿ＳＣＡＬＥに対するＭＢＵ＿ＤＣＴ＿ＢＩＴＳを示すグラフであり、量子化除数Ｑ＿ＳＣＡＬＥのコードＱ＿ＳＣＡＬＥ（ｎ）、Ｑ＿ＳＣＡＬＥ（ｎ＋１）にそれぞれ対応した２つのビット数の値Ｂ＿ＬＭＢＵ、Ｂ＿ＵＭＢＵを示している。小さい方の量子化除数Ｑ＿ＳＣＡＬＥ（ｎ）は、大きい方の量子化除数Ｑ＿ＳＣＡＬＥ（ｎ＋１）に比べて、ビット数が多くなっている。マクロユニットに関する「ビット対Ｑ＿ＳＣＡＬＥ」のグラフの性質を利用して、ＭＢＵに属する各ＭＢに対するターゲットビット数ＭＢＵ＿ＴＡＲＧＥＴを導き出す。特に、図１０に示す量Ｘ、Ｙ、Ｚは次のように定義される。
【００７７】
Ｘ≡ＭＢＵ＿ＴＡＲＧＥＴ−Ｂ＿ＵＭＢＵ
Ｙ≡Ｂ＿ＬＭＢＵ−ＭＢＵ＿ＴＡＲＧＥＴ
Ｚ≡Ｂ＿ＵＭＢＵ−Ｂ＿ＬＭＢＵ＝Ｘ＋Ｙ
したがって、
ＭＢＵ＿ＴＡＲＧＥＴ＝（Ｂ＿ＵＭＢＵＸ＋Ｂ＿ＬＭＢＵＹ）／Ｚ
したがって、図８のステップ４において、ターゲットビット数ＭＢ＿ＴＡＲＧＥＴは、次のようにして算出される。
【００７８】
ＭＢ＿ＴＡＲＧＥＴ＝Ｘ＊ＭＢ＿ＤＣＴ＿ＢＩＴＳ（Ｑ＿ＳＣＡＬＥ（ｎ））／Ｚ
＋Ｙ＊ＭＢ＿ＤＣＴ＿ＢＩＴＳ（Ｑ＿ＳＣＡＬＥ（ｎ＋１））／Ｚ
そして、もしＺ＝０ならば、ゼロの除算を避けるために、ＭＢＵ＿ＴＡＲＧＥＴ＝ＭＢＵ＿ＤＣＴ＿ＢＩＴＳ（Ｑ＿ＳＣＡＬＥ（ｎ））と設定する。
【００７９】
ステップ５において、ＭＢＵ内の各ＭＢ毎に無ひずみＤＰＣＭ符号化と有ひずみＤＣＴ符号化との間で選択を行うために、ＭＢ＿ＤＰＣＭ＿ＢＩＴをターゲットビット数ＭＢ＿ＴＡＲＧＥＴと比較する。ＭＢ＿ＤＰＣＭ＿ＢＩＴがターゲットビット数ＭＢ＿ＴＡＲＧＥＴより大きいときは、そのマクロブロックに対して有ひずみＤＣＴ符号化を選択する。逆に、ＭＢ＿ＤＰＣＭ＿ＢＩＴがターゲットビット数ＭＢ＿ＴＡＲＧＥＴ以下ときは、そのマクロブロックに対して無ひずみＤＰＣＭ符号化モードを選択する。無ひずみＤＰＣＭ符号化モードがＭＢに対して選択される毎に、ターゲットビット数ＭＢＵ＿ＴＡＲＧＥＴを再計算して、ＭＢＵ＿ＴＡＲＧＥＴ＝ＭＢＵ＿ＴＡＲＧＥＴ−ＭＢ＿ＤＰＣＭ＿ＢＩＴとする。また、ＭＢＵ＿ＤＣＴ＿ＢＩＴＳ（Ｑ＿ＳＣＡＬＥ（ｎ））及びＭＢＵ＿ＤＣＴ＿ＢＩＴＳ（Ｑ＿ＳＣＡＬＥ（ｎ＋１））を次のように再計算する。
【００８０】
2004129204.tif 000009
ターゲットビット数ＭＢＵ＿ＴＡＲＧＥＴをステップ５において再計算しているので、ターゲットビット数ＭＢ＿ＴＡＲＧＥＴについても、有ひずみＤＣＴモード符号化に現在割り当てらているＭＢの個数を考慮して、再計算する必要がある。ステップ６において、ＤＰＣＭ符号化モードに切り替わるＭＢが無くなるまで、全ての有ひずみＤＣＴモードのＭＢに対してステップ４、５を繰り返す。これを達成するのに、代表的には５、６回の反復で十分である。
【００８１】
量子化除数Ｑ＿ＳＣＡＬＥに関する不正確な予測によって、適切な量子化除数Ｑ＿ＳＣＡＬＥがビット割当探索範囲（６個の量子化除数Ｑ＿ＳＣＡＬＥからなる）外に位置するような状況を検討する必要がある。このような場合、ターゲットビット数ＭＢ＿ＴＡＲＧＥＴを計算するために、上述のステップ３、４の方法に対する代わりの方法が必要となる。２つの可能な方法が考えられる。
【００８２】
先ず、ステップ３において、ＭＢＵ＿ＤＣＴ＿ＢＩＴＳ（Ｑ＿ＳＣＡＬＥ（ｎ））が、ｎが６個の全ての値についてターゲットビット数ＭＢＵ＿ＴＡＲＧＥＴ以下であり、量子化が６個の試し値の全てについて粗すぎるときは、ステップ４におけるターゲットビット数ＭＢ＿ＴＡＲＧＥＴを次のように計算する。
【００８３】
【数４】
2004129204.tif 000010
【００８４】
この第１の方法を図１１に示す。
【００８５】
第２に、ステップ３において、ＭＢＵ＿ＤＣＴ＿ＢＩＴＳ（Ｑ＿ＳＣＡＬＥ（ｎ））が、ｎが６個の全ての値についてターゲットビット数ＭＢＵ＿ＴＡＲＧＥＴより大きく、量子化が６個の試し値のいずれについても粗すぎないときは、試し量子化除数Ｑ＿ＳＣＡＬＥ（５）、Ｑ＿ＳＣＡＬＥ（６）をステップ３におけるＱ＿ＳＣＡＬＥ（ｎ）、Ｑ＿ＳＣＡＬＥ（ｎ＋１）として選択する。この場合、ステップ４は変更されないが、今度はターゲットビット数ＭＢ＿ＴＡＲＧＥＴの外挿（ｅｘｔｒａｐｏｌａｔｉｎｇ）効果が生じる。この第２の方法を図１２に示す。
【００８６】
ターゲットビット数ＭＢ＿ＴＡＲＧＥＴの計算に加え、ビット割当器４００は、２分探索における量子化除数Ｑ＿ＳＣＡＬＥの開始点の値Ｑ＿ＢＡＳＥを設定する。量子化除数Ｑ＿ＳＣＡＬＥの開始点の値Ｑ＿ＢＡＳＥは、適切なＭＢＵ＿ＤＣＴ＿ＢＩＴＳ対Ｑ＿ＳＣＡＬＥ曲線を用いて、ターゲットビット数ＭＢ＿ＴＡＲＧＥＴから求められる。この具体例のように５回の２分探索を行う場合、開始点の値Ｑ＿ＢＡＳＥは、単にＱ＿ＳＣＡＬＥ＿ＣＯＤＥ＝１６で与えられる量子化除数Ｑ＿ＳＣＡＬＥ（すなわち量子化表の中点）である。したがって、２分探索は、この開始点の値Ｑ＿ＢＡＳＥから開始することにより、量子化除数Ｑ＿ＳＣＡＬＥの全範囲をカバーすることができる。しかしながら、２分探索の回数を少なくした具体例では、開始点の値Ｑ＿ＢＡＳＥを、各マクロブロック対してＱ＿ＳＣＡＬＥ（ｎ）とＱ＿ＳＣＡＬＥ（ｎ＋１）の中間に設定する。有ひずみＤＣＴモード符号化に割り当てられたマクロブロックに対してのみ、決定論理ユニット４７０から開始点の値Ｑ＿ＢＡＳＥ及びターゲットビット数ＭＢ＿ＴＡＲＧＥＴを出力し、ターゲット挿入器５００によって１ＭＢＵだけ遅延された画像データＩＰ＿ＤＤ１、ＩＰ＿ＤＤ２からなるビットストリームに付加する。ターゲットビット数ＭＢ＿ＴＡＲＧＥＴ及び開始点の値Ｑ＿ＢＡＳＥを２分探索器７００に供給し、２分探索器７００は、これらを最終的な量子化除数Ｑ＿ＳＣＡＬＥを決定するのに使用する。
【００８７】
図１３は、２分探索器７００の内部構成を示すブロック図である。２分探索器７００は、５つの部分からなり、各部分は２分探索の各段に対応している。各部分は、ＭＢ遅延器７１０と、量子化器７２０と、ハフマン長算出器７３０と、Ｑ＿ＳＣＡＬＥ選択器７４０とを備える。
【００８８】
２分探索器７００には、離散コサイン変換されたマクロブロックデータからなる２つの入力信号ＢＩＮ＿ＩＰ＿Ｄ１、ＢＩＮ＿ＩＰ＿Ｄ２が、ビット割当器４００で算出されたターゲットビット数ＭＢ＿ＴＡＲＧＥＴ及び開始点の値Ｑ＿ＢＡＳＥと共に供給される。入力信号ＢＩＮ＿ＩＰ＿Ｄ１、ＢＩＮ＿ＩＰ＿Ｄ２はＭＢ遅延器７１０に供給され、ＭＢ遅延器７１０は、この入力信号ＢＩＮ＿ＩＰ＿Ｄ１、ＢＩＮ＿ＩＰ＿Ｄ２を、５段の２分探索処理間でそれぞれ１マクロブロック異なるように遅延する。また、信号ＢＩＮ＿ＩＰ＿Ｄ１、ＢＩＮ＿ＩＰ＿Ｄ２は量子化器７２０にも供給され、量子化器７２０は、ハフマンエントロピー符号化を行うハフマン長算出器７３０にデータを出力する。２分探索アルゴリズムの各段は、量子化器７２０とハフマン長算出器７３０とを介したサイクルを実行する。ハフマン長算出器７３０は、ＤＣＴ変換され、量子化されたマクロブロックを符号化するのに必要なビット長を算出する。５つの部分のそれぞれの量子化器７２０及びハフマン長算出器７３０には、入力信号ＩＰ＿ＰＧＭが供給されており、この信号ＩＰ＿ＰＧＭは、８Ｈ×８ＶのＤＣＴブロック内のサンプル位置に基づいて各サンプルの量子化を変えるために使用する量子化重み付けマトリクス（Ｑｕａｎｔｉｓｅｒ　Ｗｅｉｇｈｔｉｎｇ　Ｍａｔｉｒｉｃｅｓ）のデータと、各テーブル／グループの組合せ毎にビット長を与えるＡＣ係数が可変長のハフマン長符号化テーブル（Ｈｕｆｆｍａｎ　ｌｅｎｇｔｈ　ＡＣ　ｖａｉｒｉａｂｌｅ　ｌｅｎｇｔｈ　ｃｏｄｉｎｇ　ｔａｂｌｅ）とからなる。この具合例では、５回の２分探索処理で使用する全ての量子化重み付けマトリクスを１つのＲＡＭに記憶するようにすることによって、ハードウェア要求を軽減することができる。なお、各処理段でランダムにアクセスすることが要求されるＶＬＣデータテーブルを用いた場合は、ハードウェアとしてＶＬＣデータテーブル毎に独立したＲＡＭが必要である。
【００８９】
ＭＢ遅延器７１０からの遅延された入力データと、ハフマン長算出器７３０の出力はＱ＿ＳＣＡＬＥ選択器７４０に入力として供給され、Ｑ＿ＳＣＡＬＥ選択器７４０は、マクロブロックを試験するために次のＱ＿ＳＣＡＬＥ値を選択し、選択したＱ＿ＳＣＡＬＥ値を次段の２分探索に供給する。最終的なＱ＿ＳＣＡＬＥ値は、５段目の２分探索部のＱ＿ＳＣＡＬＥ選択器７４０によって選択され、これをＱ＿ＡＬＬＯＣで示す。Ｑ＿ＡＬＬＯＣは、マクロブロックに対してターゲットビット数ＭＢ＿ＴＡＲＧＥＴを超えない最小のＱ＿ＳＣＡＬＥ値である。Ｑ＿ＡＬＬＯＣ値は、最終的な出力信号ＢＩＮ＿ＯＰ＿Ｄ１、ＢＩＮ＿ＯＰ＿Ｄ２と共に、更なる処理のために逆戻り探索器８００に供給される。ここで、出力信号ＢＩＮ＿ＯＰ＿Ｄ１、ＢＩＮ＿ＯＰ＿Ｄ２は、入力信号ＢＩＮ＿ＩＰ＿Ｄ１、ＢＩＮ＿ＩＰ＿Ｄ２に対して合計で５マクロブロック分遅延している。
【００９０】
図１４は、５段の２分探索処理を説明するための図である。
【００９１】
第１段目の２分探索は、ビット割当器４００によって算出された開始点の値Ｑ＿ＢＡＳＥを用いて、入力データを量子化し、Ｑ＿ＢＡＳＥ＿ＣＯＤＥで示す２分探索の開始点Ｑ＿ＳＣＡＬＥ＿ＣＯＤＥを決定する。この具体例では、２分探索は、量子化除数Ｑ＿ＳＣＡＬＥの全範囲を探索する５段からなる。したがって、開始点の値Ｑ＿ＢＡＳＥは、常に、値が１６のＱ＿ＳＣＡＬＥ＿ＣＯＤＥに対応するこの範囲の中心に設定される。そして、量子化データは、ハフマン長算出器７３０に供給される。ハフマン長算出器７３０で算出された第１段目におけるデータ長がターゲットビット数ＭＢ＿ＴＡＲＧＥＴより大きいときは、次段の２分探索のために、Ｑ＿ＳＣＡＬＥ値をＱ＿ＳＣＡＬＥ＿ＣＯＤＥの８ステップ分増加し、そうでないときは、Ｑ＿ＳＣＡＬＥ値をＱ＿ＳＣＡＬＥ＿ＣＯＤＥの８ステップ分減少する。この具体例では、Ｑ＿ＳＣＡＬＥ値は第２段目においてＱ＿ＳＣＡＬＥ＿ＣＯＤＥの８ステップ分増加している。入力データは、次段に合わせるために、１マクロブロック分遅延される。
【００９２】
第２段目において、データを値Ｑ＿ＳＣＡＬＥ＿ＣＯＤＥ＝（Ｑ＿ＢＡＳＥ＿ＣＯＤＥ＋８）を用いて量子化し、第２段目におけるデータ長を算出する。第２段目のデータ長をターゲットビット数ＭＢ＿ＴＡＲＧＥＴと比較して、第３段目のために、Ｑ＿ＳＣＡＬＥ値をＱ＿ＳＣＡＬＥ＿ＣＯＤＥの４ステップ分増加又は減少する。この具体例では、Ｑ＿ＳＣＡＬＥ値は第３段目においてＱ＿ＳＣＡＬＥ＿ＣＯＤＥの４ステップ分減少している。入力データを第３段目に合わせるために、２回目のＭＢ遅延を行う。
【００９３】
第３段目において、データを値Ｑ＿ＳＣＡＬＥ＿ＣＯＤＥ＝（Ｑ＿ＢＡＳＥ＿ＣＯＤＥ＋８−４）を用いて量子化し、第３段目におけるデータ長を算出する。第３段目のデータ長をターゲットビット数ＭＢ＿ＴＡＲＧＥＴと比較して、第４段目のために、Ｑ＿ＳＣＡＬＥ値をＱ＿ＳＣＡＬＥ＿ＣＯＤＥの２ステップ分増加又は減少する。この具体例では、Ｑ＿ＳＣＡＬＥ値は第４段目においてＱ＿ＳＣＡＬＥ＿ＣＯＤＥの２ステップ分増加している。入力データを第４段目に合わせるために、３回目のＭＢ遅延を行う。
【００９４】
第４段目において、データを値Ｑ＿ＳＣＡＬＥ＿ＣＯＤＥ＝（Ｑ＿ＢＡＳＥ＿ＣＯＤＥ＋８−４＋２）を用いて量子化し、第４段目におけるデータ長を算出する。第４段目のデータ長をターゲットビット数ＭＢ＿ＴＡＲＧＥＴと比較し、第５段目のために、Ｑ＿ＳＣＡＬＥ値をＱ＿ＳＣＡＬＥ＿ＣＯＤＥの１ステップ分増加又は減少する。この具体例では、Ｑ＿ＳＣＡＬＥ値は第５段目においてＱ＿ＳＣＡＬＥ＿ＣＯＤＥの１ステップ分増加している。入力データを第５段目に合わせるために、４回目のＭＢ遅延を行う。
【００９５】
第５段目において、データを値Ｑ＿ＳＣＡＬＥ＿ＣＯＤＥ＝（Ｑ＿ＢＡＳＥ＿ＣＯＤＥ＋８−４＋２＋１）を用いて量子化し、第５段目におけるデータ長を算出する。第５段のデータ長をターゲットビット数ＭＢ＿ＴＡＲＧＥＴと比較する。第５段のデータ長がターゲットビット数ＭＢ＿ＴＡＲＧＥＴより大きいときは、Ｑ＿ＳＣＡＬＥ値をＱ＿ＳＣＡＬＥ＿ＣＯＤＥの１ステップ分増加する。そうでないときは、Ｑ＿ＳＣＡＬＥ値は変更しない。この具体例では、Ｑ＿ＳＣＡＬＥ値は変更されていない。このようにして、２分探索アルゴリズムでは、マクロブロックに対してターゲットビット数ＭＢ＿ＴＡＲＧＥＴを超えない最小のＱ＿ＳＣＡＬＥ値を選択する。このＱ＿ＳＣＡＬＥ値はＱ＿ＡＬＬＯＣと呼ばれる。
【００９６】
２分探索の各段において、Ｑ＿ＳＣＡＬＥ値を減少する決定は、量子化ファクタＭＩＮＩＭＵＭ＿Ｑの条件に制約される。使用可能な最小のＱ＿ＳＣＡＬＥ＿ＣＯＤＥは、量子化ファクタＭＩＮＩＭＵＭ＿Ｑを表すＱ＿ＳＣＡＬＥ＿ＣＯＤＥであり（又はこれが存在しなければ、量子化ファクタＭＩＮＩＭＵＭ＿Ｑより大きな数を表す最初のＱ＿ＳＣＡＬＥ＿ＣＯＤＥである）、ここで、
ＭＩＮＩＭＵＭ＿Ｑ＝２＾（３−ＤＣＴ＿ＰＲＥＣＩＳＩＯＮ）
である。Ｑ＿ＳＣＡＬＥ値を減少させることにより、Ｑ＿ＳＣＡＬＥ値が使用可能な最小のＱ＿ＳＣＡＬＥ＿ＣＯＤＥより小さくなったときは、次段の２分探索の前に、Ｑ＿ＳＣＡＬＥ値を使用可能な最小のＱ＿ＳＣＡＬＥ＿ＣＯＤＥと等しくなるように設定する。
【００９７】
図１５は、２分探索器７００の各２分探索段における入力及び出力マクロブロックのタイミングを示す図である。
【００９８】
２分探索器７００は、無ひずみモード（ＤＰＣＭ）で符号化したマクロブロックに対しては、ＢＹＰＡＳＳモードで動作する。ＢＹＰＡＳＳモードでは、各２分探索処理の終了時に通常実行されるＱ＿ＳＣＡＬＥの切換は行われない。これにより、２分探索器７００の出力データは、入力データと等しい。
【００９９】
図１６は、逆戻り探索器８００の内部構成を示すブロック図である。この逆戻り探索器８００は、Ｑ＿ＳＣＡＬＥ抽出回路８１０と、Ｑ＿ＳＣＡＬＥスケール増分器（ｉｎｃｒｅｍｅｎｔｅｒ）８２０と、前処理器（ｐｒｅ−ｐｒｏｃｅｓｓｏｒ）８３０と、量子化器８４２及び誤差算出器８４４をそれぞれ有する６個の量子化部８４０と、マクロブロック遅延器８５０と、Ｑ＿ＳＣＡＬＥ選択器８６０とを備える。
【０１００】
逆戻り探索器８００の入力は、２分探索器７００の出力信号ＢＩＮ＿ＯＰ＿Ｄ１、ＢＩＮ＿ＯＰ＿Ｄ２である。この入力データには、各ＭＢの値Ｑ＿ＡＬＬＯＣが含まれている。Ｑ＿ＳＣＡＬＥ抽出回路８１０は、入力ビットストリームから量子化除数Ｑ＿ＳＣＡＬＥの値Ｑ＿ＡＬＬＯＣを抽出し、この値は、逆戻り探索処理で試験する最初の量子化スケールとして用いられる。各量子化部８４０は、２つの量子化スケールを試験する。Ｑ＿ＳＣＡＬＥ抽出回路８１０は、値Ｑ＿ＡＬＬＯＣをＱ＿ＳＣＡＬＥスケール増分器８２０に出力し、ここで、これらの値は、Ｑ＿ＳＣＡＬＥ＿ＣＯＤＥの１ステップ分だけ増加されて、量子化部８４０で試験される第２の量子化スケールとなり、この第２の値は量子化部８４０の量子化器８４２に入力として供給される。Ｑ＿ＳＣＡＬＥ抽出回路８１０から出力されるＭＢデータは、ＭＢ遅延器８５０に供給され、ここで１ＭＢ分遅延された後、Ｑ＿ＳＣＡＬＥ選択器８６０に入力として供給される。Ｑ＿ＳＣＡＬＥ抽出回路８１０からのＭＢデータは前処理器８３０にも供給されており、ここで、ＤＣＴ係数の６３個のＡＣ係数のうちの第１の３１個を繰り返して、各ＤＣＴブロックで２度発生するようにする。前処理器８３０からの出力は、６個の量子化部８４０のそれぞれに供給される。各量子化部８４０は、異なる２つの量子化レベルにおける量子化誤差を評価する。この１個の量子化部８４０当たり２つの量子化レベルの計算は、誤差計算にＤＣＴの３１個のＡＣ係数のみを用いているので可能である。この具体例では、ＤＣＴの第１の３１個のＡＣ係数を用いて誤差を計算しているが、代わりに、ＤＣＴの第２の３１個のＡＣ係数を用いてもよい。量子化器８４２は、第１の量子化除数を用いてＤＣＴの第１の３１個のＡＣ係数を量子化し、第２の量子化除数を用いてＤＣＴの第２の３１個ののＡＣ係数を量子化する。
【０１０１】
量子化除数の範囲を６個の量子化部８４０で試験する際、Ｑ＿ＳＣＡＬＥ＝Ｑ＿ＡＬＬＯＣから始め、量子化除数Ｑ＿ＳＣＡＬＥをＱ＿ＳＣＡＬＥ＿ＣＯＤＥの１ステップ分同時に増加して、全部で１２個までの量子化スケールを試験する。各量子化器８４２は、入力信号ＩＰ＿ＰＧＭが供給されており、この信号ＩＰ＿ＰＧＭは、８Ｈ×８Ｖのブロック内のサンプル位置に基づいて各サンプルの量子化を変える量子化重み付けマトリクスからなる。量子化器８４２は、量子化データを誤差算出器８４４に出力し、誤差算出器８４４は、実行された量子化に関する残差誤差（ｒｅｓｉｄｕａｌ　ｅｒｒｏｒ）を算出する。
【０１０２】
量子化処理の結果として、量子化された各ＤＣＴ係数は、関連する残差誤差を含んでおり、この残差誤差は、除算後の剰余（ｒｅｍａｉｎｄｅｒ）、量子化で使用したトータルの除数（ｔｏｔａｌ　ｄｉｖｉｓｏｒ）、及びその結果に適用した丸め方（ｒｏｕｎｄｉｎｇ）に依存する。任意のＤＣＴ係数をＣとすると、Ｃはトータルの除数ｑ、剰余ｒ、整数ｎの組合せとして次のように表すことができる。
【０１０３】
Ｃ＝ｎ＊ｑ＋ｒ
量子化後、係数は切捨ての丸めにより「ｎ」に、あるいは切上げの丸めにより「ｎ＋１」になる。したがって、逆量子化後の絶対誤差は、ｎが切捨てなら「ｒ」、ｎが切上げなら「ｑ−ｒ」と予想される。
【０１０４】
誤差算出器８４４は、量子化器８４２から丸め前の結果Ｃ／ｑを取り出し、「ｑ」を既知であり、マクロブロック全体について一定であるとして、この誤差算出器８４４は、各ＤＣＴ係数に対する残差誤差「ｒ」又は「ｑ−ｒ」を評価することができる。残差誤差を各ＤＣＴブロックの第１の（又は第２の）３１個のＡＣ係数について累算して、マクロブロック全体についてトータルの誤差を求める。
【０１０５】
６個の誤差算出器８４４の各々の出力は、Ｑ＿ＳＣＡＬＥ選択器８６０に供給され、Ｑ＿ＳＣＡＬＥ選択器８６０は、各マクロブロックに対して、最小の残差誤差を発生する、Ｑ＿ＦＩＮＡＬで示される量子化除数Ｑ＿ＳＣＡＬＥを選択する。ＭＢ遅延器８５０は、残差誤差の計算にかかる時間を補償するために設けられている。Ｑ＿ＦＩＮＡＬ値を遅延された入力データのビットストリームに挿入して、逆戻り探索器８００の出力信号ＢＫＳ＿ＯＰ＿Ｄ１、ＢＫＳ＿ＯＰ＿Ｄ２を形成する。逆戻り探索器８００の出力は、最終的な量子化器９００に入力として供給され、ここで、値Ｑ＿ＦＩＮＡＬによりデータは量子化され、その後、エントロピー符号化器１０００でハフマン符号化される。
【図面の簡単な説明】
【図１】既知の逆戻り探索法の問題を模式的に説明するための図である。
【図２】データ記録／再生装置又はデータ送信／受信システムと共に使用される、圧縮符号化装置及び対応する復号装置の模式図である。
【図３】図２のビットレート圧縮符号化装置を模式的に説明するための図である。
【図４】図２の符号化装置のビットレート圧縮処理で使用するパラメータの表である。
【図５】図２の復号装置を模式的に示した図である。
【図６】図３のシャッフル部におけるＤＣＴ＿ＰＲＥＣＩＳＩＯＮ検出回路により行われる計算を模式的に示した図である。
【図７】図３の符号化装置のビット割当器を模式的に説明するための図である。
【図８】図７のビット割当器により行われる計算を示すフローチャートである。
【図９】本発明の具体例に基づいた、調整逆戻り探索の利点を模式的に説明するための図である。
【図１０】Ｑ＿ＳＣＡＬＥに対するＭＢＵ＿ＤＣＴ＿ＢＩＴＳを説明するグラフである。
【図１１】全部で６個の試し量子化値について量子化が粗すぎる場合における、Ｑ＿ＳＣＡＬＥに対するＭＢＵ＿ＤＣＴ＿ＢＩＴＳのグラフである。
【図１２】６個の試し量子化値のいずれに対しても量子化が粗くない場合における、Ｑ＿ＳＣＡＬＥに対するＭＢＵ＿ＤＣＴ＿ＢＩＴＳのグラフである。
【図１３】図３に示す符号化装置の２分探索器の内部構成を模式的に示した図である。
【図１４】図１３の装置が行う５段構成の２分探索の説明するための図である。
【図１５】図１４の２分探索の各段におけるマクロブロック遅延を模式的に説明するための図である。
【図１６】図３に示す符号化装置の２分探索器を模式的に説明するための図である。
【図１】
2004129204.tif 000011
【図２】
2004129204.tif 000012
【図３】
2004129204.tif 000013
【図４】
2004129204.tif 000014
【図５】
2004129204.tif 000015
【図６】
2004129204.tif 000016
【図７】
2004129204.tif 000017
【図８】
2004129204.tif 000018
【図９】
2004129204.tif 000019
【図１０】
2004129204.tif 000020
【図１１】
2004129204.tif 000021
【図１２】
2004129204.tif 000022
【図１３】
2004129204.tif 000023
【図１４】
2004129204.tif 000024
【図１５】
2004129204.tif 000025
【図１６】
2004129204.tif 000026
【外国語明細書】
2004129204.tif 000027
2004129204.tif 000028
2004129204.tif 000029
2004129204.tif 000030
2004129204.tif 000031
2004129204.tif 000032
2004129204.tif 000033
2004129204.tif 000034
2004129204.tif 000035
2004129204.tif 000036
2004129204.tif 000037
2004129204.tif 000038
2004129204.tif 000039
2004129204.tif 000040
2004129204.tif 000041
2004129204.tif 000042
2004129204.tif 000043
2004129204.tif 000044
2004129204.tif 000045
2004129204.tif 000046
2004129204.tif 000047
2004129204.tif 000048
2004129204.tif 000049
2004129204.tif 000050
2004129204.tif 000051
2004129204.tif 000052
2004129204.tif 000053
2004129204.tif 000054
2004129204.tif 000055
2004129204.tif 000056
2004129204.tif 000057
2004129204.tif 000058
2004129204.tif 000059
2004129204.tif 000060
【図１】2004129204.tif 000061
【図２】2004129204.tif 000062
【図３】2004129204.tif 000063
【図４】2004129204.tif 000064
【図５】2004129204.tif 000065
【図６】2004129204.tif 000066
【図７】2004129204.tif 000067
【図８】2004129204.tif 000068
【図９】2004129204.tif 000069
【図１０】2004129204.tif 000070
【図１１】2004129204.tif 000071
【図１２】2004129204.tif 000072
【図１３】2004129204.tif 000073
【図１４】2004129204.tif 000074
【図１５】2004129204.tif 000075
【図１６】2004129204.tif 000076