(57)【要約】情報圧縮システム、より特定的には、ビデオ供給源フォーマッティング及びコンテンツのパラメータ並びに符号化されたビデオフォーマッティングパラメータに従って、ビデオ情報符号化システムを適応する方法と装置を提供する。図示するように、ビデオ情報を符号化して、フレームグループ（ＧＯＦ）の情報構造に従った符号化済み情報ストリームを発生させる。この場合、このＧＯＦ構造と、オプションとしてのビット予算は、このビデオ情報ストリーム中の（例えば３：２プルダウン処理に起因する）情報不連続性と冗長情報の存在にそれぞれ反応して修正される。【選択図】図１
2004503951.tif 000002
【特許請求の範囲】
【請求項１】
符号化システムであって、
複数の情報フレーム（ＩＮ）を受信して処理し、これによって複数の予備処理された情報フレーム（ＩＮ’）を発生するプリプロセッサ（１０１、１０２）であり、前記プリプロセッサは、前記複数の情報フレーム内でフレーム間情報不連続性を識別して印を発生するプリプロセッサ（１０１、１０２）と、
実質的にフレームグループ（ＧＯＦ）情報構造に従って前記複数の予備処理された情報フレームの各々を符号化するエンコーダ（１０４）と、
前記複数の情報フレーム内の前記フレーム間情報不連続性の前記印（ＳＣＮ、ＳＣＰ）に反応して前記ＧＯＦ情報構造を適応するコントローラ（１４０）と
を備える符号化システム（１００）。
【請求項２】
前記コントローラが、前記複数の情報フレーム内の冗長情報に反応して、前記ＧＯＦ情報構造に関連したビット割り当てレベルを適応し、
前記プリプロセッサが、前記複数の情報フレーム内での冗長情報のを識別して印（Ｒ＿ＴＯＰ、Ｒ＿ＢＯＴ）を発生する、請求項１に記載の符号化システム。
【請求項３】
前記プリプロセッサが各情報フレームを空間的に分解して、個別の詳細ピラミッドを形成し、
前記エンコーダが、前記詳細ピラミッドを用いて、前記複数の予備処理された情報フレームの非アンカー情報フレームの上方領域の動作を推定する動作推定モジュールを備える、請求項１に記載の符号化システム。
【請求項４】
前記プリプロセッサが前記詳細ピラミッドの各々をそれぞれの圧縮されたデータ詳細ピラミッド表示物にパッキングし、
前記動作推定モジュールが、前記圧縮済みデータ詳細ピラミッド表示物を利用して動作を推定する、請求項３に記載の符号化システム。
【請求項５】
前記エンコーダがさらに、
前記エンコーダが発生した各アンカーフレームを復号化するアンカーフレームデコーダ（１２５、１３０）と、
復号化された各アンカーフレームをそれぞれの圧縮済みデータ表示物にパッキングするデータパッカー（１３２）と、
各圧縮済みデータアンカーフレーム表示物を記憶するメモリー（１７０）と、
を備える、請求項４に記載の符号化システム。
【請求項６】
前記コントローラが、二次レート歪みモデルに従って前記ＧＯＦ情報構造と関連するビット割り当てレベルを適応する、請求項１に記載の符号化システム。
【請求項７】
前記エンコーダが複数の処理エレメント（１４００）を備え、各処理エレメントが、符号化されている処理済みの情報フレームのそれぞれの部分を符号化するように適応されており、前記それぞれの部分が、符号化されている情報フレームのスライス、マクロブロック又はブロックの内の１つを含む、請求項１に記載の符号化システム。
【請求項８】
各処理エレメントが、
符号化されている前記処理済み情報フレームの前記部分を基準情報フレームの対応する部分に関連付ける半画素動作ベクトルを発生する動作推定モジュール（１４１０）と、
符号化されている前記処理済み情報フレームの前記部分のコーディングモードを選択するモード選択モジュール（１４２０）であり、前記モード選択モジュールが前記半画素動作ベクトルを利用して前記コーディングモードを選択するモード選択モジュール（１４２０）と
を備える、請求項７に記載の符号化システム。
【請求項９】
各処理エレメントがさらに、
符号化されている前記処理済み情報フレームの前記部分をコーディングする、離散コサイン変換（ＤＣＴ）モジュール（１４４０）、量子化（Ｑ）モジュール（１４５０）及び可変長コーディング（ＶＬＣ）モジュール（１２０）の直列カップリング物と、
前記量子化（Ｑ）モジュールが発生した量子化済み情報ストリームに反応して前記基準情報フレームの部分を発生する、逆量子化（Ｑ−１）モジュール（１４６０）と逆離散コサイン変換（ＩＤＣＴ）モジュール（１４７０）の直列カップリング物と、
符号化されている前記処理済み情報フレームの前記部分を、前記動作推定モジュールが発生した情報と前記基準情報フレームとに従って予測する動作補償モジュール（１４８０）と
を備える、請求項８に記載の符号化システム。
【請求項１０】
符号化システムであって、
複数の情報フレーム（ＩＮ）を受信して処理し、これによって複数の処理済み情報フレーム（ＩＮ’）を発生するプリプロセッサ（１０１、１０２）であり、前記プリプロセッサが、前記複数の情報フレーム内でフレーム間情報不連続性の印（ＳＣＰ、ＳＣＮ）を識別して発生するプリプロセッサ（１０１、１０２）と、
実質的にフレームグループ（ＧＯＦ）情報構造に従って前記複数の予備処理済み情報フレームの各々を形成するそれぞれの複数の予備処理済み情報フレーム部分の各々を符号化する複数のエンコーダ（１４００）と、
前記複数の情報フレーム内での前記フレーム間情報不連続性の前記印に反応して前記ＧＯＦ情報構造を適応するコントローラ（１４０）と
を備え、前記それぞれの部分が、符号化されている情報フレームのスライス、マクロブロック又はブロックの内の１つを含む符号化システム。
【請求項１１】
前記処理エレメントの各々が、動作推定機能と符号化モード判断機能の双方に対して半画素動作推定データを利用し、また、前記半画素推定データがキャッシュメモリー中に記憶される、請求項１０に記載の符号化システム。
【請求項１２】
前記プリプロセッサが、符号化されている各それぞれの処理済み情報フレームと関連する複数の詳細ピラミッドＰＧの各々のパッキング済みデータ表示物を発生するデータパッカー（１０２−３）を含み、
前記処理エレメントの各々が、前記基準情報フレームと関連する複数の詳細ピラミッドの各々のそれぞれパッキング済みデータ表示物を発生するそれぞれのデータパッカー（１３２）を含む、請求項１１に記載の符号化システム。
【請求項１３】
映像フレームのシーケンスを符号化する方法であって、
前記情報フレームシーケンスのある部分を処理して、処理済み情報フレームシーケンスと、前記処理済み情報フレームシーケンス内のフレーム間情報不連続性と冗長情報のそれぞれの印とを発生する工程と、
フレームグループ（ＧＯＦ）情報構造とビット予算に実質的に従って符号化する工程であり、符号化済みの情報フレームシーケンスを発生する前記処理済み情報フレームシーケンスが、前記ＧＯＦ情報構造によって決定されたタイプのアンカーフレームを含む工程と、
前記処理済み情報フレームシーケンス内のフレーム間情報不連続性の前記印に反応して前記ＧＯＦ情報構造を適応する工程と、
前記処理済み情報フレームシーケンス内の冗長情報の前記印に反応して前記ビット予算を適応する工程と
を含む方法。
【請求項１４】
前記ＧＯＦ情報構造を適応する前記工程が、
内部コーディング済みアンカーフレームとして、前記情報不連続性に一時的に続くアンカーフレームを定義する工程と、
予測的にコーディングされたアンカーフレームとして、前記情報不連続性に一時的に続く別のアンカーフレームを定義する工程と
を含む、請求項１３に記載の方法。
【請求項１５】
前記ビット予算を適応する前記工程が、
前記処理済み情報フレームシーケンス内の前記冗長情報を除去する工程と、
前記除去された冗長情報と関連するビット割り当てレベルに従って前記ビット予算を増加させる工程と
を含む、請求項１３に記載の方法。
【請求項１６】
前記処理工程がさらに、
前記複数の情報フレームの空間的雑音パラメータと一時的雑音パラメータの内の少なくとも一方を測定する工程と、
前記空間的雑音パラメータが空間的雑音しきい値レベルを超えるとそれに反応して、空間的平滑化機能を前記処理済み情報フレームシーケンスを形成する前記情報フレームの内の１つ以上に付与する工程と、
前記一時的雑音パラメータが一時的雑音しきい値レベルを越えるとそれに反応して一時的平滑化機能を前記処理済み情報フレームシーケンスを形成する前記情報フレームの内の１つ以上に付与する工程と
を含む、請求項１３に記載の方法。
【請求項１７】
前記処理済み情報フレームシーケンスを形成する前記情報フレームの各々をそれぞれの詳細ピラミッド中に分解する工程をさらに含み、
前記処理済み情報フレームシーケンスを符号化する前記工程が、
各非アンカーフレームを形成する複数の情報フレーム領域の各々に対して、前記それぞれの詳細ピラミッドを用いてそれぞれのフレーム間動作パラメータを推定する工程と、
各非アンカーフレームを形成する前記複数の情報フレーム領域の各々に対して、それぞれのコーディングモードを決定する工程と、
前記それぞれのコーディングモードに従って、前記複数の情報フレーム領域の各々を符号化する工程と、
を含み、
各非アンカーフレームを形成する前記情報フレーム領域の内の少なくとも２つが、パイプライン式に動作するそれぞれの処理エレメントを用いて実質的に同時に処理される、請求項１３に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本出願は、１９９８年４月３日に提出され、ここに参照して組み込まれる米国暫定出願第６０／０８０，５３６号（代理人整理番号第１２４１４Ｐ号）の恩典を請求するものである。
【０００２】
この出願は、全て参照してここに組み込まれる、１９９８年６月２６日に提出された米国特許出願第０９／１０５，７３０号（代理人整理番号第１２４１１号）、１９９８年９月１１日に提出された第０９／１５１，４２５号（代理人整理番号第１２４１４号）及び１９９８年１１月１９日に提出された第０９／１９６，０７２号（代理人整理番号第１２６２６Ａ号）の一部継続出願である。
【０００３】
本発明は一般的には情報圧縮システムに関し、より特定的には、ビデオ供給源フォーマッティング及びコンテンツのパラメータ並びに符号化されたビデオフォーマッティングパラメータに従ってビデオ情報符号化システムを適応する方法と装置に関する。
【０００４】
【従来の技術】
送信される予定のデータを、利用可能帯域幅がより効果的に用いられるように圧縮されるような通信システムががいくつか存在する。例えば、動画エクスパートグループ（ＭＰＥＧ）はディジタルデータ送出システムに関するいくつかの基準を発行してきた。その第１の基準は、ＭＰＥＧ−１として知られているがＩＳＯ／ＩＥＣ基準１１１７２のことであり、参照してここに組み込まれる。ＭＰＥＧ−２として知られる第２の基準はＩＳＯ／ＩＥＣ基準１３８１８のことであり、参照してここに組み込まれる。圧縮ディジタルビデオシステムが、次世代テレビシステム委員会（ＡＴＳＣ）ディジタルテレビ基準文書Ａ／５３に記載されており、ここに参照して組み込まれる。
【０００５】
上に参照した基準は、ディジタル通信システム内で固定長又は可変長のデータ構造を用いてビデオ情報、オーディオ情報及び他の情報を圧縮したり送出したりすることにすべてが適するデータの処理と操作を記載している。特に、上に参照した基準及び他の「ＭＰＥＧ様の」基準及び技法では、図示するように、フレーム内コーディング技法（例えば、ランレングスコーディング、ハフマンコーディングなど）とフレーム間コーディング技法（例えば、前方・後方予測コーディング、動作補償など）を用いてビデオ情報を圧縮する。具体的には、ビデオ処理システムでは、ＭＰＥＧ及びＭＰＥＧ様のビデオ処理システムでは、ビデオフレームをフレーム内及び／又はフレーム間動作補償符号化あるなしにかかわらずビデオフレームを予測ベースで圧縮符号化することを特徴としている。
【０００６】
ビデオ情報を符号化する際に、符号化プロセスをビデオ供給源フォーマッティングパラメータや符号化済みビデオフォーマッティングパラメータに適応するのが望ましいことが分かっている。不運にも、ビデオ符号化プロセスをこのように適応すると、処理パワーとメモリーの要件という点で極端に高価なものとなりやすい。このため、ビデオエンコーダの設計者は一般に、様々なパラメータを近似させて、計算上及び記憶上のオーバーヘッドを特定の応用分野（例えば、専門的な用途や消費者的な用途）で定められる「まともな」レベルにまで軽減する。
【０００７】
したがって、ビデオ供給源フォーマッティングパラメータと符号化済みビデオフォーマッティングパラメータに対してビデオ符号化プロセスを適用し及び／又は強化するためのロバストで計算的に効果的な方法と装置を提供することによって上記の問題を処理するのが望ましいことが分かっている。具体的には、広範囲の符号化ビットレートにわたって洗練されたロバストなビデオ品質と共に比較的低い計算的複雑性とメモリー帯域幅の要件を提供する、ＭＰＥＧ−２ビデオ符号化方法と装置などのビデオ符号化方法と装置を提供することが望ましいことが分かっている。
【０００８】
【課題を解決するための手段】
本発明は、図示するように、ビデオ情報ストリームを符号化して、フレームグループ（ＧＯＦ）情報構造に従った符号化済み情報ストリームを発生するための方法と装置を含む。本発明の様々な実施形態では、ビデオ情報ストリームにおける、（例えば、３：２プルダウン処理に起因する）情報の不連続性と冗長情報の存在にそれぞれ反応したＧＯＦ構造とビット予算に対する修正がなされる。本発明のさらなる実施形態ではピラミッド処理技法、パックデータ表示及び他の方法を用いて、符号化環境下でメモリーリソース及び／又は処理リソースを高度に効果的に利用するようにしている。
【０００９】
具体的には、本発明による符号化システムは：実質的にフレームグループ（ＧＯＦ）情報構造に従った複数の予備処理済み情報フレームの各々を符号化するエンコーダと、前記複数の情報フレーム内のフレーム間情報不連続性に反応してＧＯＦ情報構造を適応するコントローラと、複数の情報フレームを受信して処理して、複数の予備処理された情報フレームを発生するプリプロセッサであり、前記プリプロセッサが前記複数の情報フレーム内でのフレーム間情報不連続性の印を識別して発生するプリプロセッサと、を含んでいる。
【００１０】
【発明の実施の形態】
本発明の教示は添付図面と共に以下の詳細な説明を読めば容易に理解することが可能である。分かりやすいように、図面全体にわたって同一の部品には可能な限り同一の参照番号を用いている。
【００１１】
以下の説明を検討すれば本発明の教示内容が、容易に利用できる情報符号化システム、特にビデオ情報符号化システムであり得ることが当業者に明瞭に理解されよう。
【００１２】
ＭＰＥＧ様符号化システムの高レベルブロック図を図１に示す。図１のＭＰＥＧ様符号化システム１００は、複数の未圧縮情報フレームからなる入力情報ストリームＩＮ、具体的にはビデオ情報ストリームを形成する一連の画像を受信して、フレームグループ（ＧＯＦ）又は画像グループ（ＧＯＰ）データ構造に公称的に従う符号化された出力情報ストリームＯＵＴを生成する。各ＧＯＦ／ＧＯＰデータ構造は、極大サイズのＭ個のフレームを持つ複数のサブＧＯＦ又はサブＧＯＰデータ構造として配置されるＮ個のフレームから成る。各サブＧＯＦ／ＧＯＰはそれぞれのアンカーフレーム（例えば、Ｉフレーム又はＰフレーム）、及び選択的に１つ以上の非アンカーフレーム（例えば、Ｂフレーム）を含む。
【００１３】
具体的には図１のＭＰＥＧ様符号化システム１００は、第１プリプロセッサ１０１、第２プリプロセッサ１０２、コントローラ１４０、符号化モジュール１０４、及び出力バッファ１６０から成る。
【００１４】
第１プリプロセッサ１０１は入力情報ストリームＩＮを受けそれを処理して、予備処理をされた入力ビデオ情報ストリームＩＮ′を生成する。第１プリプロセッサ１０１は以下の機能的構成部品を含む：３：２プルダウンプロセッサ１８１、情景変化検出器１８２、雑音減少プレフィルタ１８３、及びサブＧＯＰバッファ１８４である。第１プリプロセッサ１０１の作動方法を図２を参照して以下により詳細に説明する。
【００１５】
３：２プルダウンプロセッサ１８１は入力ビデオ情報ストリームＩＮをフレーム毎に処理し、それに応じて、入力ビデオ情報ストリームＩＮ内における３：２プルダウン処理されたビデオ情報の存在（例えば、固有の２４ｆｐｓ）又は不在（例えば、固有の３０ｆｐｓ）を示す制御信号ＰＤを本発明の１つの実施形態において生成する。３：２プルダウン指示制御信号ＰＤはコントローラ１４０に結合する。３：２プルダウンプロセッサ１８１は、入力ビデオ情報ストリームＩＮ内の「余分な」ビデオ情報の識別及び除去を支援することによって、符号化される情報の量を減少させるために用いられる。すなわちプルダウンが復元されて、その結果生じた情報フレームは、進行的な（すなわち非インターレースの）方法で符号化モジュール１０４によりコーディングされる。３：２プルダウンプロセッサ１８１の出力は情景変化検出器１８２に結合する。
【００１６】
本発明の１つの実施形態では、３：２プルダウンプロセッサ１８１は「フィールド識別」方法を利用し、入力情報ストリームＩＮ内の連続するフィールドを比べて、そのフィールドが内在するビデオ情報の３：２プルダウン処理を示すような方法で繰り返されているかどうかを確認する。この実施形態ではプルダウンプロセッサ１８１は制御信号Ｒ＿ＴＯＰ及び制御信号Ｒ＿ＢＯＴを生成する。制御信号Ｒ＿ＴＯＰは、ビデオフレームの頂部フィールド内のビデオ情報が直前のビデオフレームの頂部フィールド内のビデオ情報と事実上同じであるかどうかを示すために用いられる。同様に制御信号Ｒ＿ＢＯＴは、ビデオフレームの底部フィールド内のビデオ情報が直前のビデオフレームの底部フィールド内のビデオ情報と事実上同じであるかどうかを示すために用いられる。
【００１７】
例示の３：２プルダウンプロセッサ及び制御機能は、１９９８年９月１１日出願の米国特許出願第０９／１５１，４２５号（代理人整理番号第１２４１４号）において開示されており、その全てを参照してここに組込む。フィールド同士の比較を実行するのに要する計算量は、絶対差合計（ＳＡＤ）法を用いて、連続する情報フレームの（頂部又は底部）フィールドの部分的フィールド比較だけを行うことによって選択的に減少できる。
【００１８】
情景変化検出器１８２は、ビデオ情報ストリームＩＮ（又は３：２プルダウン処理された入力ビデオ情報ストリームＩＮ）内の情景変化又は情景切り取りのような、情報の不連続性を識別するために用いられる。情報の不連続性の検出に応答して、情景変化検出器１８２は不連続性を示す第１制御信号ＳＣＮ及び第２制御信号ＳＣＰを生成する。具体的には、第１及び第２の情景変化指示制御信号ＳＣＮ及びＳＣＰはコントローラ１４０に結合されて、次の（すなわち未だ符号化されていない）サブＧＯＰ（ＳＣＮ）における情景変化、及び現在の（すなわち現在符号化されつつある）サブＧＯＰ（ＳＣＰ）における情景変化をそれぞれ示すために用いられる。すなわち情景変化検出器の作動は、２つのフレーム間の相違が内在ビデオ内で発生した情景変化による相違かどうかを確認するために２つの情報フレームが比較されるということに基づいたルックアヘッドである。
【００１９】
雑音減少プレフィルタ１８３は、適応可能な非線型雑音減少フィルタから成り、それはガウスの雑音、散弾雑音及びテープ雑音等の異なるタイプの雑音を減少させる一方で、ビデオ情報の場合には高い忠実度を持つエッジ及び他のハイコントラスト詳細等の高周波情報を保持する。雑音減少プレフィルタ１８３は、フレーム毎に、又はサブＧＯＰバッファ１８４内に記憶されている全サブＧＯＰ上で動作する。当業者は１つ以上の周知の非線型雑音減少フィルタを適切に本発明に適用することが容易にできよう。例えば有限インパルス応答中央ハイブリッド（ＦＭＨ）フィルタを用いて図１の雑音減少プレフィルタ１８３を実現することができる。
【００２０】
サブＧＯＰバッファ１８４は前記のように、サブＧＯＰを形成するいかなるアンカーフレーム及びいかなる関連の非アンカーフレームをも保存できる。第１プリプロセッサの様々な工程（すなわち、３：２プルダウン処理、情景変化検出、及びフィルタリング）の完了後、処理されたサブＧＯＰは予備処理を施された入力ビデオ情報ストリームＩＮ′として、第２プリプロセッサ１０２及び符号化モジュール１０４に結合される。
【００２１】
コントローラ１４０は、入力情報ストリームＩＮ、３：２プルダウン指示制御信号ＰＤ、Ｒ＿ＴＯＰ及びＲ＿ＢＯＴ、及び情景変化指示制御信号ＳＣＮ及びＳＣＰを受信し処理して、符号化モジュール１０４を制御するために用いられる様々な制御信号を生成する。具体的にはコントローラ１４０は以下の制御信号を生成する：画像タイプ制御信号ＰＴは、符号化されているサブＧＯＰのアンカーフレームＧＯＰの所望のフレームタイプ（すなわち、Ｐ−フレーム又はＩ−フレーム）を指示するために用いられる。ＧＯＰ構造制御信号ＧＳは、ＧＯＰ構造（例えば、図２を参照して以下に説明されるような変数ｎＰｕ、ｎＢｕ、ｎＢｏ等）へのいかなる変化をも指示するために用いられる。進行的フレーム制御信号ＰＦは、情報フレームの進行的符号化を指示するために用いられる。「頂部フィールド第１／繰り返し第１フィールド」制御信号ＲＢＦは、符号化されるフレームが繰り返される素材を含み従って繰り返し素材無しに符号化できることを指示するために用いられる。フレームレート制御信号ＦＲは、符号化されるビデオ情報ストリームの所望のフレームレート（すなわち、秒当たりのフレーム数）を指示するために用いられる。さらに、量子化モジュール制御信号ＣＱ及び離散コサイン変換モジュール制御信号ＣＤがコントローラ１４０によって生成される。
【００２２】
（１つ以上の制御信号ＳＣＮ及びＳＣＰによって指示されるように）入力情報ストリームＩＮ内のフレーム間の情報不連続性に応答して、情報の不連続性に引き続く第１のアンカーフレームはＩフレームから成り、一方情報の不連続性に先行する第１のアンカーフレームはＰフレームから成るように、コントローラ１４０は符号化された出力情報ストリームＯＵＴを適応させる。各ＧＯＦ／ＧＯＰ構造に割当てられるビット予算内のビットは、新たなＧＯＦ／ＧＯＰの開始直前のフレームの内部を符号化することによって「浪費」されない。
【００２３】
（１つ以上の制御信号ＰＤ、Ｒ＿ＴＯＰ、Ｒ＿ＢＯＴによって示されるように）入力情報ストリームＩＮ内に３：２プルダウン処理されたビデオ素材が存在するとそれに応答して、コントローラ１４０は入力情報ストリームＩＮから「過剰の」又は重複するビデオ情報を取り除き、それによって情報ストリームＩＮの残余の部分を符号化するために用いられるビット数を増加させる。
【００２４】
このようにしてコントローラ１４０はが３：２プルダウンプロセッサ１８１及び情景変化検出器１８２と協力することによって、符号化モジュール１０４は（３：２プルダウン処理された素材を伴った又は伴わない）情景変化にわたって円滑かつ高性能な符号化を行うことができるようになる。この様な方法によって、符号化されたビデオストリームＯＵＴ内の情景変化後の視覚的アーチファクトが、比較的低いビットレートにおいても著しく減少する。さらにプルダウンされた素材が、低い実フレームレートを用いることによってより高性能でコーディングされる。
【００２５】
符号化モジュール１０４は予備処理された入力情報ストリームＩＮ′を受信し符号化して、フレームグループ（ＧＯＦ）又は画像グループ（ＧＯＰ）データ構造に実質的に適応する符号化された情報ストリームＳ１０４を生成する。符号化された情報ストリームＳ１０４は出力バッファ１６０に結合する。コントローラ１４０によって生成された制御信号Ｃ１及び出力バッファ１６０によって生成されたレート制御信号ＲＣに応答して、符号化モジュール１４０は、ＧＯＦ又はＧＯＰデータ構造、ビット割当て、量子化スケール及び符号化処理の他のパラメータに適応する。符号化モジュール１０４は、処理されるマクロブロックのために選択される符号化モード（すなわち、フレーム内符号化されるか又はフレーム間符号化されるか）を指示するモード判断信号ＭＤを生成する。さらに符号化モジュール１０４内の動作推定モジュール１５０は、第２プリプロセッサ１０２によって生成された幾つかの制御信号に応答する。
【００２６】
符号化モジュール１０４は、減算器１５５、モード判断モジュール１０５、離散コサイン変換（ＤＣＴ）モジュール１１０、量子化Ｑモジュール１１５、可変長コーディング（ＶＬＣ）モジュール１２０、逆量子化器（Ｑ−１）１２５、逆離散コサイン変換（ＤＣＴ−１）モジュール１３０、選択的データパッカー１３２、減算器１５６、動作補償モジュール１４５、動作推定モジュール１５０、及びアンカーフレーム記憶モジュール１７０から成る。レート制御機能はレートコントローラ１４０によって実行される。
【００２７】
減算器１５５は、信号経路ＩＮ′上の入力マクロブロックから信号経路ＰＦ上の予測されるマクロブロックを減じることによって、残余信号（また当技術において単に残余又は残余マクロブロックとも呼ばれる）を発生する。
【００２８】
モード判断モジュール１０５は、減算器１５５から残余マクロブロック（すなわち、予測されるマクロブロック）を、又信号経路ＩＮ′から入力マクロブロックを受取る。予測マクロブロックが入力マクロブロックと実質的に類似している（すなわち、残余は相対的に小さく、非常に少ないビットを用いて容易にコーディングできる）場合は、モード判断モジュール１０５はフレーム間符号化のために減算器１５５から残余信号を選択する。すなわち、マクロブロックは補償されたマクロブロックすなわち動作ベクトル及び関連する残余として符号化される。しかしながら予測マクロブロックと入力マクロブロックとの間の差がかなりある場合には、その残余をコーディングするのは高くつく。従ってシステムは、動作補償された残余マクロブロックを符号化するよりも入力マクロブロックを直接符号化することによってより効率的に動作する。
【００２９】
上記の選択処理はコーディングモードの選択として周知である。入力マクロブロックの符号化はフレーム内コーディングと呼ばれ、残余のコーディングはフレーム間コーディングと呼ばれる。これら２つのモード間の選択はフレーム内−フレーム間−決定（ＩＩＤ）として周知である。ＩＩＤは一般に、先ず残余マクロブロック（ＶａｒＲ）の変化、及び入力マクロブロック（ＶａｒＩ）の変化を計算することによって計算される。コーディングの決定はこれらの値に基づく。この決定を行うために用いることができる幾つかの関数がある。例えば、最も簡単な関数を用いると、ＶａｒＲがＶａｒＩよりも小さければＩＩＤはフレーム間モードを選択する。逆に、ＶａｒＩがＶａｒＲよりも小さければＩＩＤはフレーム内モードを選択する。
【００３０】
代りに、図１のＭＰＥＧ様エンコーダ１００内での使用に適したモード判断方法が、１９９５年１０月２６日出願の米国特許出願第０８／５４７，７４１号（代理人整理番号第１１８１９号）に開示されており、それを参照してここに組込む。簡単に言えば、第０８／５４７，７４１号出願には、各マクロブロックをコーディングするために要する全ビット数は２つの部分からなり、１つは動作ベクトルをコーディングするのに必要なビットでありもう１つは予測残余をコーディングするのに必要なビットである。動作ベクトルのコーディングのためのビット数は一般にルックアップテーブルから得られる。予測残余をコーディングするためのビット数は、その変化の値に正比例し、量子化ステップ（量子化のスケール）の値に逆比例するという想定によって得られる。この想定を用いれば、マクロブロックをコーディングするのに必要な全ビット数が各コーディングモードに対して計算されて比較される。最小ビット数でコーディングモードを選択することにより、本発明は実際に実用化するための複雑さの度合いの低い最適に近い解法を得る。
【００３１】
選択されたブロック（すなわち、予備処理された入力マクロブロック又は残余マクロブロック）はその後ＤＣＴモジュール１１０に結合される。ＤＣＴモジュール１１０はレートコントローラ１４０によって生成された制御信号ＣＤに応答して、選択されたブロックを処理し、例えばＤＣＴ係数の例えば８×８ブロックの１セットを生成する。ＤＣＴモジュール１１０によって生成されるＤＣＴ係数は量子化モジュール１１５に結合される。
【００３２】
量子化モジュール１１５はレートコントローラ１４０によって生成された制御信号ＣＱに応答して、受信されたＤＣＴ係数を量子化し、量子化された出力ブロックを生成する。量子化のプロセスによって、整数値を作るための適当な丸めを伴う量子化値の１セットによりＤＣＴ係数を割ることによってＤＣＴ係数を表す際の精度が落ちる。量子化されたＤＣＴ係数は可変長コーディング（ＶＬＣ）モジュール１２０及び逆ＤＣＴモジュール１２５に結合される。
【００３３】
それからＶＬＣモジュール１２０は周知の可変長コーディング及びランレングスコーディング方式を用いて、受信され量子化されたＤＣＴ係数（例えば、８×８ブロックの量子化されたＤＣＴ係数）及びマクロブロックについての副次情報を符号化する。
【００３４】
動作の予測及び補償を行うために、符号化モジュール１０４は参照フレームとして用いるための符号化されたアンカーフレームを再び生成する。この機能は逆量子化モジュール１２５、逆ＤＣＴモジュール１３０及び選択的にデータパッカー１３２によって実行される。
【００３５】
具体的には、逆量子化（Ｑ−１）モジュール１２５は量子化されたＤＣＴ係数（例えば、８×８ブロックの量子化されたＤＣＴ係数）を処理して、それぞれのＤＣＴ係数を生成する。逆ＤＣＴモジュール１３０はそれぞれのＤＣＴ係数を処理して、復号化されたされた誤差信号を生成する。ＤＣＴ−１モジュール１３０によって生成された誤差信号は加算器１５６の入力に結合される。ＤＣＴ−１モジュール１３０はまた、引き続く符号化のための参照フレームとして用いるためにデータを符号化することによって、入力映像シーケンスのＩフレーム及びＰフレームを再生成するために機能する。この参照情報は情報ストリームＡＩＮとしてアンカーフレームメモリー１７０に結合される。データパッカー１３２は、その情報をアンカーフレームメモリー１７０内に記憶するのに先立って、参照情報ストリームＡＩＮをパックするために選択的に用いられる。
【００３６】
動作推定モジュール１５０は予備処理された入力情報ストリームＩＮ′及び記憶されたアンカーフレーム情報ストリームＡＯＵＴを受取る。記憶されたアンカーフレーム情報ストリームＡＯＵＴはアンカーフレーム記憶モジュール１７０によって生成され、それは逆ＤＣＴモジュール１３０によって生成された入力アンカーフレーム情報ストリームＡＩＮを記憶する。簡単に言えば、記憶されたアンカーフレーム情報ストリームＡＯＵＴは、符号化モジュール１０４によって現在符号化されているＧＯＦ又はＧＯＰのフレーム間コーディングされたアンカーフレームの復号化されたバージョンを表す。
【００３７】
動作推定モジュール１５０は、予備処理された入力情報ストリームＩＮ′及び記憶されたアンカーフレーム情報ストリームＡＯＵＴを用いて、動作ベクトルを推定する。動作ベクトルは２次元のベクトルであり、現在の画像内のブロックの座標位置からのオフセットを行って参照フレーム内に適応するための動作補償に用いられる。参照フレームは、前方予測されコーディングされたフレーム（Ｐフレーム）又は双方向（すなわち、前方及び後方）予測されたフレーム（Ｂフレーム）であり得る。動作ベクトルは動作補償モジュール１４５及びＶＬＣモジュール１２０に結合される。
【００３８】
動作推定モジュール１５０は、全画素動作推定器１５１及び半画素動作推定器１５２を含むように選択的に実現される。全画素動作推定器１５１は全画素動作ベクトルＦＰＭＶ及び全画素歪み信号（すなわち、２つの画素ブロック間の相違の程度）ＦＰＤを応答的に生成する。半画素動作推定器１５２は、全画素動作ベクトルＦＰＭＶ及び全画素歪み信号ＦＰＤを用いて、半画素動作ベクトルＨＰＭＶ及び半画素歪み信号ＨＰＤを応答的に生成する。選択的な半画素動作ベクトルＨＰＭＶ及び半画素歪み信号ＨＰＤはモード判断モジュール１０５に結合されるものとして表され、そこでそれらはモード判断の精度を増大させるために効果的に利用される。
【００３９】
動作補償モジュール１４５は動作ベクトルを受取ってサンプル値の予測効率を高める。動作の補償は動作ベクトルを用いた予測を伴い、予測の誤差を形成するために用いられる先行して復号化されたサンプル値を含む過去及び／又は未来の参照フレーム内にオフセットを施す。具体的には、動作オフセットモジュール１５０は先行して復号化されたアンカーフレーム及び動作ベクトルを用いて、現在のフレームの推定を組立てる。さらに、動作推定モジュール及び動作補償モジュールによって実行される機能は、復号モジュール例えば単一ブロックの動作補償器内で実現可能であることが当業者に理解されよう。
【００４０】
所与のマクロブロックに対して動作補償予測を実行するのに先立って、コーディングモードが選択されなければならない。コーディングモード判断の分野においては、ＭＰＥＧ及びＭＰＥＧ様の標準が複数の異なるマクロブロックのコーディングモードを提供する。具体的にはＭＰＥＧ−２は、フレーム内モード、無動作補償モード（ＮｏＭＣ）、前方／後方／平均フレーム間モード、及びフィールド／フレームＤＣＴモードを含むマクロブロックコーディングモードを提供する。
【００４１】
ひとたびコーディングモードが選択されれば、動作補償モジュール１４５は、過去及び／又は未来参照画像に基づくブロックのコンテンツの経路ＰＦ上に、動作補償された予測フレーム（例えば、予測された映像）を生成する。経路ＰＦ上のこの動作補償された予測フレームは、減算器１５５を通じて、現在のマクロブロック内の入力情報フレームＩＮ′（例えば、ビデオ映像）から減算されて、誤差信号又は予測残余信号を形成する。予測残余信号を形成することによって入力ビデオ映像内の冗長情報が効果的に取除かれる。前記のように、予測残余信号はさらなる処理のためにモード判断モジュール１０５に結合される。
【００４２】
ＶＬＣエンコーダ１２０によって生成されたＶＬＣデータストリームは、バッファ１６０、具体的にはＧＯＰデータ構造に従って少なくとも１つ以上の符号化サブＧＯＰを保持することができる「先入先出」（ＦＩＦＯ）バッファ内で受け取られる。出力バッファ１６０はその利用レベルを示すレート制御信号ＲＣを生成する。
【００４３】
異なる画像タイプの使用及び可変長コーディングの結果、出力バッファ１６０内への全ビットレートが変更可能となる。すなわち、各フレームのコーディングに使われるビット数が異なり得る。出力情報ストリームＯＵＴを例えば記憶媒体又は通信チャネルに結合するための固定レートチャネルを含む応用例においては、出力バッファ１６０は、エンコーダ出力をビットレート平滑化のためのチャネルに一致させるのに用いられる。従って出力バッファ１６０の出力信号ＯＵＴは、予備処理済入力情報ストリームＩＮ′の圧縮された表現である。
【００４４】
図１に示されるレート制御モジュール１４０は、マイクロプロセッサ１４０−４とともに、同時符号化−適応フレーム切替方式２００及び／又は「オンデマンド」符号化−適用フレーム切替方式４００を記憶するためのメモリー１４０−８を含む。マイクロプロセッサ１４０−４は、電源、クロック回路、キャッシュメモリー等の従来型サポート回路１４０−６とともに、ソフトウェア体系を支援する回路と協同する。従って、ソフトウェア処理等のここで議論された処理工程のいくつかは、例えばマイクロプロセッサ１４０−４と協同して様々な工程を実行する回路のようなハードウェアの中で実行できると考えられる。コントローラ１４０はさらに、様々な符号化モジュール（１０４及び１０２）と選択器（１０４）間のインタフェースを形成する入出力回路１４０−２を含む。コントローラ１４０は本発明による様々な制御機能を実行するようにプログラムされた汎用コンピュータとして示されているが、本発明はまた特定用途向け集積回路（ＡＳＩＣ）としてのハードウェア内でもまた実現可能である。従ってここで（例えば、図２Ａから２Ｃに関連して）説明された全てのプロセス又は方法の工程は、ソフトウェア、ハードウェア、又はそれらの組合せによって同等に実行されるものと広義に解釈されることを意図したものである。
【００４５】
レート制御モジュール１４０の主要なタスクは出力バッファ１６０の十分さ又は利用レベルを管理することであり、その出力バッファから一定の出力ビットレートが送信チャネルへ与えられる。符号化レートが、各映像及び映像の連続のコンテンツに依存して著しく変化したとしても、一定のビットレートは維持されなければならない。出力バッファ１６０は、その利用レベルを示すレート制御信号ＲＣを生成する。
【００４６】
レート制御モジュール１４０はレート制御信号ＲＣを用いて、（制御信号ＣＱ経由の）ＤＣＴ係数の量子化に用いられる量子化スケール（工程のサイズ）及び／又はシステムによりコーディングされた制御信号ＣＤ経由のＤＣＴ係数の数のような、符号化処理の様々なパラメータに適応する。すなわち、画像の全シーケンスにわたる均等な視覚的特性を維持しつつ画像に対する目標ビットレートが達成されるように、各フレームについて量子化器のスケールが選択される。この様にして、レート制御モジュール１４０は、ＶＬＣ１２０によって生成される出力情報ストリームのビットレートを制御し、それによって出力バッファ１６０の適切な利用レベルを維持する。
【００４７】
本発明の１つの実施形態では、レート制御モジュール１４０は二次レート−歪みモデルを用いたフレームレベル目標決定方式に従って動作し、それは１９９６年１０月２３日出願の米国特許出願第０８／７３８，２２８号（代理人整理番号第１１８３５号）の中で説明されており、参照してここに組込まれる。簡単に言えば、開示されている二次レート歪みモデルはＱにおける二次モデルを提供して、使用されるビット数をモデル化するが、標準のＴＭ−５レート制御モデルは一次モデルを利用する。すなわち、先行して符号化された情報フレーム部分（例えば、フレーム、スライス又はマクロブロック）に割当てられたビット数を大まかに調べて先行符号化部分の複雑さのレベルを決定し、それに応じて符号化される現在の又は引き続く部分の複雑さレベルを決定するレートコントローラによって、レート制御が改善される。従ってより高精度のビット利用モデルによって、ビット予算をより高精度に管理することができる。
【００４８】
レート制御モジュール１４０の別の重要なタスクは、エンコーダによって生成されるビットストリームが、出力情報ストリームＯＵＴから成る送信を受取る（例えば、図示されない受信機又は目標記憶デバイス内の）デコーダ内の入力バッファにおけるオーバーフロー又はアンダーフローが無いことを保証することである。オーバーフロー及びアンダーフローの制御は、エンコーダ内の仮想的バッファを維持しかつ監視することによって行われる。仮想的バッファはビデオバッファリング検証器（ＶＢＶ）として知られる。正しいデコーダ入力バッファビットの制御を保証するために、エンコーダのレート制御プロセスによって、各画像さらには各画像を構成する画素の各マクロブロックについて、ビット割当量（ここではビット予算とも呼ばれている）が確立される。それぞれのビット予算内にあるそれぞれのビット数を用いてブロック及び全体の画像をコーディングすることにより、ＶＢＶはオーバーフロー又はアンダーフローしない。ＶＢＶはデコーダの入力バッファを反映するので、ＶＢＶがアンダーフロー又はオーバーフローしなければ、デコーダの入力バッファはアンダーフロー又はオーバーフローしない。
【００４９】
図２Ａと図２Ｂはともに図１のＭＰＥＧ様符号化システムに用いるのに適応したレート制御方法２００の工程系統図を表す。図２Ａと図２Ｂは、図２Ａに概略的に表される方法で配置されて方法２００の全体が一緒に見られるように意図されている。以下の議論では一般に次のことが前提となっている、すなわちフレームレートに関わりなくＭＰＥＧ様符号化システム１００は動作して、所定の画像グループ（ＧＯＰ）情報構造に従って受信済ビデオ情報ストリームＩＮを符号化するが、その構造においては各ＧＯＰには所定のビット数（Ｒ）が割り当てられて、一定のビットレート出力ストリームＯＵＴが出力バッファ１６０により生成される。すなわち、２つのＩフレーム間の距離Ｎと２つの連続した参照フレーム間の距離Ｍは、符号化のプロセスにわたって同一に保たれている。さらに、１つのモード変化の極大点がいかなる２つの連続する参照フレーム間にも存在することが前提されている。
【００５０】
図２Ａと２Ｂのレート制御方法２００は、受信済ビデオ情報ストリームＩＮ内のモード変化（すなわち、２４ｆｐｓ←→３０ｆｐｓ）の検出に応答して、ＴＭ−５レート制御アルゴリズムによって用いられるレート制御パラメータ（Ｒ）を変化させて、ＧＯＰビット割当て内に残っているビット数を指示する。この様にして、ＴＭ−５レート制御アルゴリズムは、そのようなモード変化に応じて適切に機能するように作られる。
【００５１】
例えば図１のＭＰＥＧ様符号化システム１００が符号化のためにビデオ情報ストリームＩＮを受取ったときに、方法２００はステップ２０５に入れられる。方法２００はそれからステップ２１０に進み、ＧＯＰシーケンスの第１ＧＯＰの処理に先立って、ＲＳＬＡＣＫがゼロに初期化される。変数ＲＳＬＡＣＫは先行して符号化されたＧＯＰのビットのオーバー／アンダーランを指示するために使われる。すなわちＲＳＬＡＣＫは、先行ＧＯＰが割当てられたよりも少ないビット（アンダーラン）又は多いビット（オーバーラン）で符号化されことを指示する。従って現在処理されているＧＯＰは、先行するオーバー／アンダーランを（必ずしもオフセットによってではないが）オフセットする傾向があるようなやり方で符号化される。それから方法２００はステップ２１２に進む。
【００５２】
ステップ２１２では、３つの変数（ｎ２０、ｎ３０及びＧＯＰＢＩＴＳ）がゼロに初期化される。第１の変数ｎ２０は、２４ｆｐｓ動作モードで符号化される処理中のＧＯＰ内のフレーム数を示すために用いられる。第２の変数ｎ３０は、３０ｆｐｓ動作モードで符号化される処理中のＧＯＰ内のフレーム数を示すために用いられる。第３の変数ＧＯＰＢＩＴＳは、処理中のＧＯＰ内のビデオフレームを符号化するためにこれまで使われた全ビット数を表示する。この情報は、符号化中のビデオストリームのフォーマットの変化によって生じる動作モード間の遷移中にＧＯＰの持続時間を動的に更新するために利用される。それから方法２００はステップ２１５に進む。
【００５３】
ステップ２１５では、受信済ビデオ情報ストリームＩＮのモードについての照会が行われる。すなわち入力ビデオストリームＩＮは現在、固有の３０ｆｐｓビデオストリーム（例えば、「標準の」ＮＴＳＣストリーム）から成るか、又は固有の２４ｆｐｓビデオストリーム（例えば、３０ｆｐｓストリームを形成するための３：２プルダウン処理に従って処理される２４ｆｐｓの動画）から成るかについての照会が行われる。受信済情報ストリームのモードを識別するための例示の方法を図３、４、及び５を参照して以下に説明する。
【００５４】
ステップ２１５での照会で、受信済ビデオ情報ストリームＩＮが３０ｆｐｓビデオ素材から成ることが示された場合、方法２００はステップ２２５に進み、変数ＦＲＡＭＥＲＡＴＥが３０に初期化される。方法２００はそれからステップ２３０に進む。ステップ２１５の照会で、受信済ビデオ情報ストリームＩＮが２４ｆｐｓビデオ素材から成ることが示された場合は、方法２００はステップ２２０に進み、そこで変数ＦＲＡＭＥＲＡＴＥが２４に初期化される。それから方法２００はステップ２３０に進む。
【００５５】
ステップ２３０では、処理すべき画像グループ（ＧＯＰ）内に残っているビット数（Ｒ）が（次の）等式１に従って計算され、ＴＭ−５反応パラメータ（ｒ）が（次の）等式２に従って計算される。ここで、
“Ｒ”は、現在のＧＯＰに対するビット割当て内に残るビット数であり、
“ＲＳＬＡＣＫ”は、先行して符号化されたＧＯＰのビットのオーバー／アンダーランであり、
“ＮＰ”は、現在のＧＯＰ内に残るＰフレームの数であり、
“ＮＢ”は、現在のＧＯＰ内に残るＢフレームの数であり、
“ＢＩＴＲＡＴＥ”は、符号化された結果のビットストリームのビットレートであり、
“ＦＲＡＭＥＲＡＴＥ”は、ステップ２１５から２２５について２４又は３０であり、及び
“ｒ”は、ＴＭ−５レート制御アルゴリズムで用いられる反応パラメータである。
【００５６】
【式１】
2004503951.tif 000003
【００５７】
【式２】
2004503951.tif 000004
【００５８】
現在のＧＯＰ（Ｒ）に対するビット割当て内に残るビット数と反応パラメータ（ｒ）を計算した後、変数ＧＯＰＳＴＡＲＴが計算された値Ｒに等しく設定されて、方法２００はステップ２３５に進み、そこでモードの変化が発生したかどうか（すなわち、２４ｆｐｓ→３０ｆｐｓ又は３０ｆｐｓ→２４ｆｐｓ）についての照会がなされる。ステップ２３５における照会で、２４ｆｐｓモードから３０ｆｐｓモードへのモード変化が示された場合は、方法２００はステップ２３６へ進む。ステップ２３５における照会で、３０ｆｐｓモードから２４ｆｐｓモードへのモード変化が示された場合は、方法２００はステップ２３７へ進む。ステップ２３５における照会でモード変化が起こらなかったことが示された場合は、方法２００はステップ２３８へ進む。
【００５９】
ステップ２３８において変数Ｒは、ＧＯＰＳＴＡＲＴ−ＧＯＰＢＩＴＳに等しくなるように設定される。すなわちＧＯＰビット割当て（Ｒ）内に残るビット数は、初期ビット割当て（ＧＯＰＳＴＡＲＴ）マイナス使用されたビット数（ＧＯＰＢＩＴＳ）に等しくなるように設定される。それから方法２００はステップ２６０へ進む。
【００６０】
ステップ２６０では、現在処理されているＧＯＰ内の現在処理されているビデオフレームを形成する各マクロブロックについて、量子化パラメータ（ｓ）が計算される。それから方法２００はステップ２６２へ進む。
【００６１】
ステップ２６２では、例えばＴＭ−５レート制御アルゴリズムに従ってフレームが符号化される。符号化されるフレームタイプを決定するのに用いられる画像グループ（ＧＯＰ）構造が、図２Ｃの方法に従って選択的に変更される。以下にそれをより詳細に説明する。
【００６２】
方法２００はそれからステップ２６５に進み、そこで変数ＮＰ（現在のＧＯＰ内に残るＰフレームの数）及びＮＢ（現在のＢフレーム内に残るＢフレームの数）の値が必要に応じて調整される。方法２００はそれからステップ２６６へ進む。
【００６３】
ステップ２６６では、現在符号化されているモードについての、すなわちステップ２６２で符号化されたフレームは２４ｆｐｓ又は３０ｆｐｓ固有モードフレームのどちらであるかについての、照会が行われる。ステップ２６６での照会の結果、ステップ２６２で符号化されたフレームが３０ｆｐｓフレームだった場合は、方法２００はステップ２６７へ進み、そこで変数ｎ３０が１つ増分される。それから方法２００はステップ２７０に進む。ステップ２６６での照会の結果、ステップ２６２で符号化されたフレームが２４ｆｐｓだった場合は、方法２００はステップ２６８に進み、そこで変数ｎ２０が１つ増分される。方法２００はそれからステップ２７０に進む。
【００６４】
ステップ２７０で、変数ＧＯＰＢＩＴＳが調整される。変数ＧＯＰＢＩＴＳは、処理されているＧＯＰ内のビデオフレームを符号化するためにこれまで使われた全ビット数を表示する。従って変数ＧＯＰＢＩＴＳは、処理されているＧＯＰ内の直近のフレームを処理するのに使われる（ヘッダ情報及び他のビット消費情報を含む）ビットの量によって増大させられる。方法２００はステップ２７５に進む。
【００６５】
ステップ２７５では、直近に符号化されたフレームが処理中のＧＯＰの最後のフレーム（すなわち、ＧＯＰフレームの終点）か否かについて照会が行われる。ステップ２７５での照会の結果が否定的であれば、方法２００はステップ２１５に進む。
【００６６】
ステップ２７５での照会の結果が肯定的であれば、方法２００はステップ２８０に進み、そこで変数ＲＳＬＡＣＫがＲに等しくなるように設定される。Ｒは処理されているＧＯＰに対するビット割当て内に残るビット数を表示するので、さらにＧＯＰは現在処理されているので、Ｒに対するゼロ以外の全ての値は、割当てられたビット予算の利用不足（Ｒ＞０）又は利用過剰（Ｒ＜０）を表す。ビット割当てのこのオーバー／アンダーフローは先行して符号化されたＧＯＰから残っている全てのオーバー／アンダーフローに加えられて、符号化プロセスのあいだ利用可能な帯域幅が最大限に利用される。例えば利用不足のビット予算は、次のＧＯＰのＩフレームを増加したビット数で符号化することによって、及び符号化処理を質的に強化するための他の周知の方法によって、用いることができる。それから方法２００はステップ２１２へ進む。
【００６７】
ステップ２３６及び２３７の双方において、３つの変数の値が計算される。具体的には、第１の変数ｎＢｕは、新しい動作モード（すなわち、モード変化の検出後に導入されたモード）でコーディングされるために残留するＢフレームの数を示す値に等しく、第２の変数ｎＰｕは、新しい動作モードでコーディングするために残留するＰフレームの数を示す値に等しく、第３の変数ｎＢｏは、古い動作モード（すなわち、モード変化検出以前のモード）でコーディングされるために残留するＢフレームの数を示す値に等しい。ステップ２３６の実行後、方法２００はステップ２４０に進む。ステップ２３７の実行後、方法２００はステップ２５０に進む。
【００６８】
ステップ２４０では、現在処理中のＧＯＰ内に残っているビット数（Ｒ）が（次の）等式３によって計算され、一方ステップ２５０では、現在処理中のＧＯＰ内に残っているビット数（Ｒ）が（次の）等式４によって計算される。ここで、“ｎ２０”は、２４ｆｐｓ動作モード中に符号化された現在のＧＯＰ内のフレーム数であり、
“ｎ３０”は、３０ｆｐｓ動作モード中に符号化された現在のＧＯＰ内のフレーム数であり、
“ｎＢｕ”は、（モード変化検出後の）新しいモードでコーディングされるために残留するＢフレームの数であり、
“ｎＰｕ”は、新しいモードでコーディングされるために残留するＰフレームの数であり、および
“ｎＢｏ”は、古いモードでコーディングされるために残留するＢフレームの数である。
【００６９】
【式３】
2004503951.tif 000005
【００７０】
【式４】
2004503951.tif 000006
【００７１】
ステップ２４０で現在処理中のＧＯＰ内に残っているビット数（Ｒ）を計算した後、方法２００はステップ２４５に進み、そこで（次の）等式５に従って反応パラメータ（ｒ）が計算される。方法は次にステップ２６０に進む。
【００７２】
【式５】
2004503951.tif 000007
【００７３】
ステップ２５０で現在処理中のＧＯＰ内に残っているビット数（Ｒ）を計算した後、方法２００はステップ２５５に進み、そこで（次の）等式６に従って反応パラメータ（ｒ）が計算される。方法はそれからステップ２６０に進む。
【００７４】
【式６】
2004503951.tif 000008
【００７５】
上記のビット割り当て方法は、式１から６に関連して上述したように、閉じた形態で解くことができる二次レートモデルに基づいている。利点として、図２のビット割り当て方法は、図２のＴＭ５の線形モデルを用いて達成されるより正確なフレームレベル目標ビット割り当てを提供する。上記の方法は、Ｉフレーム、Ｐフレーム及びＢフレーム上にビットを適切に分布させることによって時間的なバッファ変動を制限し均一な品質を提供する。このようにして、低ビットレートにおける市販のエンコーダに共通のＩフレーム、Ｐフレーム及びＢフレーム上で品質が変動することに起因する従来の「パルス化」アーチファクトが避けられる。そのうえ、テレシネ変換（すなわち、３：２プルアップ処理）を利用することによって、２４ｆｐｓビット割り当て、情景遷移でのＧＯＰ構造の適応及びビット割り当て、符号化１０４に対するレートコントローラ１４０が出力する制御信号によって、結果得られる符号化済みビデオストリームは、平滑な情景間遷移とフレーム内ビット割り当てを提供しながらも利用可能ビット予算を固化的に利用することを保証する。
【００７６】
図２Ｃに、情報不連続性（情景変化など）の存在／不在に反応して所定の画像グループ（ＧＯＰ）情報構造を適応的に修正する方法２６２のフローチャートを示す。具体的には、図２Ｃの方法２６２は、情景変化に反応して発生するような、緊密近似のＩフレームの符号化を避け易いように事前定義済みＧＯＰ構造を適応する。すなわち、ある情景の最終サブＧＯＰ内のアンカーフレームが、ＩフレームではなくＰフレームとして符号化され、その一方では、次の情景の第１のアンカーフレームがＩフレームとして符号化され、これによって、ＧＯＰに割り当てられたビット予算をより効果的に利用する。
【００７７】
ＧＯＰ方法２６２は、例えば図２のレート制御方法２００がステップ２６２（すなわち、フレームが符号化される）を実行すると、ステップ２６２−２で入力される。方法２６２は次にステップ２６２−４に進み、ここで、情景変化制御信号ＳＣＰとＳＣＮの状態が検査される。次に方法２６２はステップ２６２−６に進む。
【００７８】
ステップ２６２−６で制御信号ＳＣＰとＳＣＮがそれぞれ０と１に等しいかどうか照会される。ステップ２６２−６における照会が肯定的に回答された（情景変化が現在のサブＧＯＰ中で発生した）場合、方法２６２はステップ２６２−８に進む。ステップ２６２−６での照会に対する回答が否定的である場合、方法２６２はステップ２６２−１０に進む。
【００７９】
ステップ２６２−８で、現在のサブＧＯＰのアンカーフレームがＰフレームとして符号化される。次に方法２６２はステップ２６２−２０に進み、ここから脱出する。
【００８０】
ステップ２６２−１０では、制御信号ＳＣＰが１に等しいかどうか照会される。すなわち、前に符号化されたサブＧＯＰ中で情景変化が発生したことを制御信号ＳＣＰが示しているかどうか照会される。ステップ２６２−１０での照会に対する回答が肯定的である場合、方法２６２はステップ２６２−１２に進み、ここで、現在のサブＧＯＰのアンカーフレームがＩフレームとして符号化される。次に方法２６２はステップ２６２−２０に進み、ここから脱出する。ステップ２６２−１０での照会に対する回答が否定的である場合、方法２６２はステップ２６２−１６に進む。
【００８１】
ステップ２６２−１６では、現在のサブＧＯＰのアンカーフレームはＧＯＰ構造による。符号化されるフレームがアンカーフレームでない場合、このフレームはＧＯＰ構造ベースで符号化される。次に、方法２６２はステップ２６２−２０に進み、ここから脱出する。
【００８２】
図２Ｃの方法では、情報のサブＧＯＰを、例えばサブＧＯＰバッファ１８４によってバッファリングすることが必要である。本発明の１つの実施形態では、このようなサブＧＯＰバッファは用いられていない。この実施形態では、参照してここにその全体が組み込まれる１９９８年６月２６日に提出された米国特許出願第０９／１０５，７３０号（代理人整理番号第１２４１１号）の教示を利用している。具体的には、サブＧＯＰバッファが欠落している本発明の１つの実施形態では、各アンカーフレームをＩフレームとＰフレーム双方として符号化される。情景変化の際には、Ｐフレームをアンカーフレームとして用い、次のアンカーフレームをＩフレームとして符号化する。入力サブＧＯＰバッファだけが欠落している本発明の別の実施形態では、出力サブＧＯＰバッファを用いて符号化済みサブＧＯＰを記憶するようになっている。情景変化の際には、出力サブＧＯＰバッファに記憶されているアンカーフレームが必要に応じて再符号化されて、ある情景の最後のサブＧＯＰ内のＰフレームと新しい情景の最初のサブＧＯＰ内のＩフレームを用意する。
【００８３】
図３に、図１のＭＰＥＧ様のエンコーダ１００で使用するのに適した方法のフローチャートを示す。具体的には、図３の方法３００を用いて、サブＧＯＰを形成する複数の受信された情報フレームの符号化を制御する。方法３００はステップ３１０で入力されステップ３１５に進む。
【００８４】
ステップ３１５で、情報フレーム、例えばビデオ情報フレームが入力情報ストリームＩＮから受信されてサブＧＯＰ記憶用バッファ１８４に記憶される。次に、方法３００はステップ３２０に進む。
【００８５】
ステップ３２０で、ステップ３１５で受信された情報フレームが前に受信された情報フレームとフィールド単位で比較される。すなわち、前の情報フレーム（すなわち、受信された最後のビデオフレームに次ぐフレーム）の頂部フィールドが受信された情報フレーム（すなわち、受信された最後のビデオフレーム）の頂部フィールドと比較される。同様に、前の情報フレームの底部フィールドが受信された情報フレームの底部フィールドと比較される。この比較の結果を用いて、図１を参照して上述したように、プリプロセッサ１０１の３：２プルダウンプロセッサ１８１が発生した制御信号ＳＣＰとＳＣＮの状態を変更する。次に、方法３００はステップ３２５に進む。
【００８６】
ステップ３２５では、情景変化の有無がコントローラに示される。すなわち、プリプロセッサ１０１の情景変化検出器１８２を図１を参照して上述したように利用して、情景変化指示制御信号ＳＣＰとＳＣＮを発生する。次に、方法３００はステップ３３０に進む。
【００８７】
ステップ３３０では、入力簿でイストリーム中のいかなるフィールドの繰り返しもコントローラに示される。すなわち、プリプロセッサ１０１の３：２プルダウンプロセッサ１８１は、フィールドベース比較ステップ３２０で誘導された情報を利用して、なんらかのフィールドが繰り返されたかどうかをフレーム毎に判断する。頂部フィールドが繰り返されていたらそれは制御信号Ｒ＿ＴＯＰによって示され、一方、底部フィールドの繰り返しは制御信号Ｒ＿ＢＯＴによって示される。次に、方法３００はステップ３３５に進む。
【００８８】
ステップ３３５では、フレームのサブＧＯＰに対する全てのフレームレベル判断が完了したかどうか照会される。すなわち、なんらかの情景変化又は３：２プルダウン情報がサブＧＯＰ全体の各フレームに対して決定されるように、サブＧＯＰバッファ１８４中に記憶されている入力フレームが処理されたかどうかについて判断される。ステップ３３５での照会に対する回答が否定的である（すなわち、記憶されているサブＧＯＰが完全には処理されていない）場合、方法３００はステップ３１５に進み、ここで、サブＧＯＰの次の入力フレームが受信されてサブＧＯＰバッファ中に記憶される。ステップ３３５での照会に対する回答が肯定的である場合、方法３００は次にステップ３４０に進む。
【００８９】
ステップ３４０では、サブＧＯＰバッファ１８４に記憶されている情報フレームのサブＧＯＰはエンコーダ１０４にカップリングされて、ここで符号化される。このカップリングされたサブＧＯＰの符号化は、この開示のどこかに記載されている方法に従って実行される。次に、方法３００はステップ３１５に進み、ここで、次のサブＧＯＰの最初の情報フレームが受信されてサブＧＯＰバッファ１８４に記憶される。
【００９０】
既述したように、図１のＭＰＥＧ様の符号化システムでの使用に適したフィールド間輝度又はクロミナンス区別法を利用した３：２プルダウン検出方法が、米国特許出願第０９／１５１，４２５号に詳述されている。フィールド区別計算を加速し、また、メモリー帯域幅を減少させるために、ここに開示する区別技法（ルマ繰り返しフィールド検出器）がオプションとして、次の方法に従って２つのフィールドを比較する：第１に、例えば、各マクロブロック（例えば、１マクロブロック＝８ｘ行ｘ１６画素）中の１つの行に沿った同じパリティの連続輝度フィールド内での絶対差（ＳＡＤ）の和が計算される。第２に、この絶対差（ＳＡＤ）の和の計算値が上限しきい値Ｔ＿ＭＢ＿ＨＩＧＨより大きい場合、第２のフィールドは第１のフィールドの繰り返しではなく、この方法は終了する。第３に、ＳＡＤの計算値が上限しきい値レベルＴ＿ＭＢ＿ＨＩＧＨ未満である場合、そのフィード中の次のマクロブロックに進み、ステップ１から３を繰り返す。第４に、ＳＡＤの計算値が上限しきい値レベルＴ＿ＭＢ＿ＨＩＧＨ以下であり下限しきい値レベルＴ＿ＭＢ＿ＬＯＷ以上である場合、マクロブロック全体にわたってＳＡＤを計算する。第５に、ＳＡＤがマクロブロックＴ＿ＭＢ上でしきい値より大きい場合、第２のフィールドは第１のフィールドの繰り返しではない。繰り返しである場合、次のマクロブロックに進み、上記のステップを繰り返す。最後に、全てのマクロブロックが処理された結果、ＳＡＤの合計値がフレームＴ＿ＦＲ上でしきい値を越えない場合、第２のフィールドは第１のフィールドの繰り返しである。
【００９１】
このような多段しきい値付けによって、誤警告の可能性が軽減される。また、これらのしきい値によって、フィールドが正確な繰り返しとなることを妨げかねないトランスコーディング誤差を明瞭化することが可能となる。これらのしきい値は、３：２プルダウン素材の大集合に基づいて実験的に到達させることができる。
【００９２】
受信されたサブＧＯＰを予備処理したら、予備処理された入力情報ストリームＩＮ内の情報フレームは符号化モジュール１０４と第２のプリプロセッサ１０２にカップリングされる。
【００９３】
図１に戻ると、第２のプリプロセッサ１０２は予備処理された入力情報ストリームＩＮ’を受信して処理し、これによってピラミッド情報ストリームＰＧと、オプションとして、ブロック分類ストリームＢＣを発生する。第２のプリプロセッサ１０２は次の機能的構成部品を含んでいる：ピラミッド発生器１０２−２、オプションのデータパッカー１０２−３及びオプションのブロック分類器１０２−４である。
【００９４】
ピラミッド発生器１０２−２は、予備処理された入力情報ストリームＩＮ’内のフレームを空間的に分解して、フレーム、奇数フィールド及び偶数フィールドの低域通過ピラミッドを誘導する。次に、アップサンプリングされた下位レベルを減算することによって、詳細なピラミッドが作成される。詳細画素が２つのレベルに量子化されて、１画素当たり１ビットを用いて表される。画素値を表示するために使用されるビットの数がこのようにしてかなり減少するため、例えば、符号化モジュール１０４内での動作推定プロセスにおける計算上オーバーヘッドが減少する。例えば、動作推定プロセスで実行されるブロック整合動作を加速させることができるが、その理由は、画素値が取ることができる値がほとんどなく、従って全体的なブロック整合プロセスが簡略化されるからである。
【００９５】
オプションのデータパッカー１０２−３を用いて、図９から１２を参照して以下に説明するパック戦略を用いて、結果としてのピラミッドを表示するデータをパックする。オプションのデータパッカー１０２−３を用いて、例えば、符号化モジュール１０４内での動作推定プロセスで利用されるメモリーリソースの量を減少させる。簡単に言えば、平均データ及び／又はＭ進法データが「パック」されて定義済みデータワードとなり、これによって計算上の要件とメモリー帯域幅上の要件とを達成する。すなわち、Ｍ進法ピラミッドを表すデータを、以降の記憶、検索及び処理などの動作が効率的に実行されるような非常に特定的な仕方で配置する。例えば、１つの３２ビットワードを用いて、あるピラミッドの画素ブロック内の１行全体の画素を表すようにする。このようにして、動作推定に用いられるピラミッドの全体サイズが（４から８桁だけ）減少する。
【００９６】
オプションのデータパッカー１０２−３を用いると、パックされた表示データは図１のＭＰＥＧ様の符号化システム１００の他の部分で使用しなければならない。具体的には、符号化システム１０４は、ピラミッド情報ストリームＰＧを表すパック済みデータを処理することが可能でなければならない。
【００９７】
オプションのブロック分類器１０２−４を用いて、ブロックとマクロブロックを、例えば動作推定プロセスでより効率的にこれら両者を比較できるように分類する。例えば、ブロックを「アクティビティレベル」で分類されるが、この場合、アクティビティのレベルは非ゼロ画素の数、又は画素もしくはなんらかの他のパラメータの範囲又は時計的分布に関連する。
【００９８】
図７に、平均ピラミッドが複数のレベル７１０、７２０及び７３０を含む平均ピラミッド７００を発生するために用いられる量子化プロセスを表すグラフである。最下位レベル７１０は、「ｘ」で表される複数の画素７１１を有する映像シーケンスから取ったオリジナルの映像である。一般的に、これらの画素は、画素値を表すために割り当てられるビットの数によって制限される範囲を有する画素値によって表される。例えば、８個のビットが割り当てられた場合、画素値は２５６の考えられる値の内の１つの値をとる。
【００９９】
平均ピラミッドにおいては、次に高いレベルが双方向での低域通過フィルタリングと２桁ダウンサンプリングによって発生され、これによって、より下位のレベルでの４つの画素値（子）からより高位のレベルの単一の画素値（親）を発生する。この様子を図７に示すが、ここでは、４つの画素７１２ａから７１２ｄの各集合を用いて、レベル７２０で１つの画素値７２１を発生する。次に、４画素値７２２ａの集合を用いて、レベル７３０の１つの画素値７３１を発生する、という具合に次々に画素値を発生する。本発明は３つのレベルを有する平均ピラミッドに制限されないことが理解されよう。レベルの数は一般的に、映像のサイズと、次に低い解像度を持つ映像を発生させるために選択されたダウンサンプリング係数と、によって制限される。したがって、平均ピラミッドのレベルの数は特定の用途に応じて選択することができる。
【０１００】
平均ピラミッドにおいては、親画素値は、その４つの子画素値の平均値を取ることによって誘導されるため、この平均ピラミッドという用語が付いている。しかしながら、他の尺度や計測法を用いて、他のタイプのピラミッドを発生させても良いが、例えば４つの子画素値の中央値に基づく尺度を用いてもよい。代替例として、子画素の周辺のより大きい領域を加重平均値に対して用いて一般的な低域通過ピラミッドを得てもよい。
【０１０１】
Ｍ進法ピラミッドにおいては、画素値は、量子化された各画素が「Ｍ」個の可能な画素値しか取り柄内容に量子化される。例えば、Ｍが２に等しい場合、量子化された各画素は０又は１しか取ることができない、すなわちその結果「二進法ピラミッド」となる。
【０１０２】
図８に、Ｍが３に等しい場合の三進法ピラミッドを発生するために用いられる量子化プロセスを表すグラフを示す。具体的には、８ビットの画素２５５（８１０ａ）を、子画素と親がその差に基づいて２ビット画素値１０（８２０ａ）に量子化する。すなわち、親８３０ａとその子８１０ａから８１０ｄの各々との間の差を計算するが、この場合、４つの差の各々が次に、３つの可能な値１０、００及び０１に量子化される。このように、画素値１２８（８１０ｂと８１０ｃ）が画素値０１（８２０ｂと８２０ｃ）に量子化され、画素値０（８１０ｄ）が画素値０１（８２０ｄ）に量子化される。これらの表示レベルは、動作推定で用いられるビット毎ＸＯＲベースの費用関数に適している。これらのレベルはまた、特徴検出とブロック分類に有用である。Ｍ進法ピラミッドは画素値の精度を減少させ、これによって、映像内の「特徴」を迅速に検出することが可能となる。
【０１０３】
特徴とは項アクティビティ又は強度の領域、例えば物体のエッジであると定義される。レベル８１０と８３０は平均ピラミッドのレベルであり、一方、レベル８２０はＭ進法ピラミッド（ここでＭ＝３）のレベルであることに注意すべきである。これらのピラミッドは双方共が、図８に示すように追加のレベルを有するが、Ｍ進法ピラミッドは常に平均ピラミッドのレベルより１つレベルが低い。すなわち、１つのＭ進法ピラミッドレベル８２０を発生するためには２つの平均ピラミッドレベル８１０と８３０を必要とする。
【０１０４】
Ｍは任意の正の整数値でよいが、二進法ピラミッドの分解は雑音に対して敏感であることが分かっている。すなわち、量子化された画素値は可能な２つの値しか取り得ないので、雑音は誤差を導入しかねず、このような場合、画素値は０と１を互いに誤って有するものと誤解釈されかねない。このような過剰感度のため、特徴のあるなしが誤解釈されかねない。したがって、Ｍ進法ピラミッドの分解はＭが３以上である場合に用いるのがベストであることが分かっている。
【０１０５】
代替例として、Ｍ進法平均ピラミッドの分解を式という形態で表現できる。（ｉ，ｊ）で映像フレーム上での画素位置を表し、Ｉ（ｉ，ｊ）で位置（ｉ，ｊ）での強度を表すものとする。さらに、ｌがピラミッド内のレベルを表し、０＝ｌ＝Ｌとするが、ここでＬはピラミッド中での最高位レベルであるとする。すると、平均ピラミッドＸ１（ｉ，ｊ）、１＝ｌ＝Ｌが次のように構成される：
【０１０６】
【式７】
2004503951.tif 000009
【０１０７】
ここで、Ｘ０（ｉ，ｊ）＝Ｉ（ｉ，ｊ）である。
【０１０８】
これらの平均ピラミッドから、図６を参照して以下に既述するようにブロック内の特徴を抽出することができる。この好ましい実施形態では、ブロックはマクロブロックの８ｘ８サブブロックであるが、本発明はっこのブロックサイズに限られるわけではないことを理解すべきである。特に、エッジなどの特徴はブロック内の強度の変動から抽出することができる。この変動は、レベルｌ、０＝ｌ＝Ｌ−１での平均値とレベルｌ＋１での平均値間の差を計算することによって表される。しかしながら、ロバストな特徴を得るため、また、高速動作粋推定を容易化するために、この差をＭこのレベルを用いて量子化して、量子化された値をｌｏｇ２Ｍビットを用いて表示する。これによって、エッジやゼロ交差などの映像特徴を識別するために用いられる映像に関するパターンを作成する。このパターン値をＹ１（ｉ，ｊ）で表すと次式のようになる：
【０１０９】
【式８】
2004503951.tif 000010
【０１１０】
Ｑｕａｎｔ［？］の引数をλで表す。例えば、しきい値Ｔを持つ三進法ピラミッドの場合を考えると、Ｙ１（ｉ，ｊ）は次のようになる：
【０１１１】
【式９】
2004503951.tif 000011
【０１１２】
この定義は、量子化しきい値Ｔ（例えば、この実施形態ではＴは５に選択される）を特定の応用分野に対して適切に選べば雑音ロバスト性という利点がある。すなわち、雑音による画素値のささいな変動を効果的に除去できる「デッドゾーン」、例えば｜λ｜＜Ｔを定義することができる。したがって、ゼロ近辺のデッドゾーンを有するいかなるＭ進法ピラミッド（Ｍ＞２）も二進法ピラミッドで見られるような雑音感度問題を最小化する。
【０１１３】
比較的平坦な領域（低アクティビティの領域）では、Ｙ１（ｉ，ｊ）は多くのゼロ（０）を含み、一方エッジを含む領域では、Ｙ１（ｉ，ｊ）は複数個の１を含んでいる。入力映像がＭ進法ピラミッドに分解されると、この入力映像中のブロックはＭ進法ピラミッドＹ１（ｉ，ｊ）を用いて特徴を抽出するという目的のために分類することができる。すなわち、Ｍ進法ピラミッドを用いて、高い計算オーバーヘッドを招くことなく入力映像中の特徴を迅速に検出できる。この検出された特徴を用いて、以下に説明するような動作推定プロセス又は他の映像処理ステップ、例えばセグメント化モジュール１５１を用いての、例えば映像内の領域（物体など）のセグメント化を強化することができる。セグメント化は重要な映像処理ステップであり、この場合、映像中の重要な領域を識別して特殊な処理を受けるようにすることができる。例えば、ビデオ会議に応用した場合に人の顔は、コーディングビットをより多く割り当てるなどの特殊な映像上の処理を必要とすることがある。加えて、セグメント化を用いて大型の物体を識別できるが、この場合、グローバルな動作推定がこれらの大型の物体に対して実行できる。
【０１１４】
先行する説明では零として三進法ピラミッドを用いて、量子化しきい値又はレベルを特徴の識別と分類のために割り当てられる１つの可能な方法を示していることを理解すべきである。一般に、Ｍ＞２であるＭ進法ピラミッドを、映像シーケンスの特殊な応用及び／又はコンテンツの要件に依存する量子化しきい値を特定的に割り当てて用いることができる。
【０１１５】
図６に、ブロックベースの動作推定のために動作ベクトルを決定する際の計算上の複雑性を減少させるための方法のフローチャートを示す。すなわち、方法６００は、整合が発生しそうな初期探索領域を迅速に定義することによってブロックベースの動作推定方法を強化するものである。
【０１１６】
具体的には、方法６００はステップ６０５で始まりステップ６１０に進み、ここで、Ｍ進法ピラミッド（又はＭ進法平均ピラミッド）を、予備処理された入力情報ストリームＩＮ’内の映像シーケンス中の各映像フレームに対して発生する。ステップ６１０での重要な側面は映像シーケンス中の入力映像の各々に対してＭ進法ピラミッドが発生されることであることを理解すべきである。したがって、この好ましい実施形態がＭ進法平均ピラミッドを発生するとはいえ、他のタイプのＭ進法ピラミッド、例えばＭ進法平均ピラミッド、Ｍ進法低域通過ピラミッドなどを本発明で用いてもよい。次に、方法６００はオプションステップ６１５に進む。
【０１１７】
オプションステップ６１５では、ステップ６１０で発生されたＭ進法ピラミッドは、後で例えば符号化モジュール１０４の動作推定プロセスで使用するためにパッキングされて記憶される。このＭ進法ピラミッドのデータのパック動作と記憶動作は図９から１２を参照して以下に詳述する。加えて、適当な方法が、その全体を参照してここに組み込む１９９８年１１月１９日発行の米国特許出願第０９／１９６，０７２号（代理人整理番号第１２６２６Ａ）に開示されている。次に、方法６００はオプションステップ６２０に進む。
【０１１８】
オプションステップ６２０では、フレーム中のブロックが、Ｍ進法ピラミッドを見て低アクティビティであるか高アクティビティであるかという点で分類される。この好ましい実施形態では、「分類ブロックサイズ」は、１２８ビットで表される６４個のＭ進法画素値を有する８ｘ８ブロックである。２５以上の画素値が非ゼロであれば８ｘ８ブロックが高アクティビティブロックと分類される場合、「アクティビティしきい値」は２５であると設定される。そうでない場合、８ｘ８ブロックは低アクティビティブロックと分類される。追加のより高いブロックの分類、例えば、マクロブロックを高アクティビティ又は低アクティビティをマクロブロックとして分類することが可能である。この好ましい実施形態では、高アクティビティとして分類される少なくとも１つのサブブロックを含むようなマクロブロックは、高アクティビティとしても分類されることになる。「分類ブロックサイズ」と「アクティビティしきい値」を特定の応用分野に対して調整することが可能であり、したがって、この好ましい実施形態で選択されたこれらの値に制限されることはないことを理解すべきである。次に、方法６００はオプションステップ６３０に進む。
【０１１９】
ステップ６３０では、ブロック分類を用いて、符号化モジュール１０４の動作推定プロセスを強化する。一般に、重要な映像特徴を持った領域での動作推定は、アパーチュア問題によるほとんど無変化の比較的「平坦な領域」（例えば、隣り合ったブロック動詞の映像のコンテンツが非常に類似している一様な領域）での動作推定より信頼性が高い。したがって、上記の分類方法を用いて、一般的な動作推定の信頼性を高める。すなわち、本発明を用いて、様々なタイプ又は異なったアーキテクチャの動作推定方法の性能を高めることができることを理解すべきである。
【０１２０】
具体的には、動作推定は一般的に、ラスタースキャン順序でブロック毎に実行される。計算上のオーバーヘッドすなわち費用は一般的に、動作推定プロセス中で全てのブロックにわたって均一に分配される。本発明では、エッジブロック（高アクティビティブロック）における動作推定は最初に、Ｙ１（ｉ，ｊ）及び／又はＸ１（ｉ，ｊ）に依存する費用関数を用いて実行することができる。この方式によって映像中の特徴を強調することができ、センサー雑音、量子化雑音及び証明変化の存在下でもロバストで信頼性の高い動作推定値が提供される。費用関数のある例では、ある種のアーキテクチャに対する高速方法として実現することが可能な、ピラミッド中のＭ信号レベルに対するビット毎のＸＯＲ演算を必要とすることがある。この費用関数を用いて、「最良の正号」を決定することができる。時点ｔ（現行フレーム）におけるＭ進法値ブロックＹ１（ｉ，ｊ）と時点ｔ−１（前のフレーム）における別のＭ進法値ブロックＹ１（ｍ，ｎ，ｔ−１）を考える。すると、費用関数は次にようになる：
【０１２１】
【式１０】
2004503951.tif 000012
【０１２２】
ここで、シグマはブロック内の画素を表し、（Ｘ）はビット毎のＸＯＲ演算を表す。
【０１２３】
この費用関数は、オリジナルの８ビット画素強度値に対して用いられる標準の「絶対差」費用関数と比較してかなりの計算の節約をもたらす。この手順をＭ進法ピラミッド上で階層的に実行する。言い換えれば、この動作推定方法は高アクティビティブロックから開始される。
【０１２４】
複数のブロックに分割され、その内の２つが高アクティビティブロックと分類された入力映像フレームの場合を考える。したがって、動作推定を最初にこの２つのブロックに対して実行する。事実、計算費用はこの２つのブロックの場合は高くなるかもしれないが、その理由は、これらの高アクティビティブロック（高信頼性エッジブロック）は非常に高い精度の動作ベクトルを提供しやすいからである。したがって、より集約的な動作推定を入力映像フレーム中の他のブロックよりこの２つのブロックに対して実行する。例えば、この２つの高アクティビティブロックを分割して、より正確な動作ベクトルを得ることができ、「半画素」動作推定をこの２つのブロック中で実行することが可能であったりより細密な探索戦略を用いてもよい。
【０１２５】
次に、この高アクティビティブロックに対する動作推定が完了したら、次に動作推定はその映像中の低アクティビティブロック（「低信頼性」ブロック）に伝搬する。しかしながら、この伝搬は、分類から得られる領域又は物体のセグメント化に依存してインテリジェントに実行される。この伝搬は、隣同士のブロックの動作のための初期化としてのエッジブロックの動作と、この初期化を洗練させるための比較的小さい探索範囲を用いて実行される。すなわち、動作推定プロセスは、高アクティビティブロックに近接したブロックに（例えば、螺旋順序で）伝搬する。次に、この伝搬戦略は、エッジブロックに隣接した又は近接した平坦ブロックにまで拡大される。
【０１２６】
このようにして、動作推定探索範囲が迅速にしかも比較的低い計算上の複雑さで洗練される。さらに、結果得られる動作推定値はより平滑でより符号化しやすく、これによって、動作情報がビットストリームのかなりの部分を占める非常に低いビットレート（ＶＬＢＲ）応用分野では大きな利点となっている。さらに、これらのより平滑な動作推定値は、一時的内挿をする応用分野ではより性能がよいものと期待される。最後に、この分類方法は又、半画素を洗練させて動作推定値の精度を増すと計算回数の節約をもたらすが、その理由は、半画素の洗練動作はエッジブロックに対してだけ実行され、映像の比較的平坦な領域には実行されないからである。
【０１２７】
図１のＭＰＥＧ様エンコーダのメモリーリソース要件をさらに減少させるために、本発明のある実施形態では、主要な４つの要素を提供しているがそれは：１）平均ピラミッド及び／又はＭ進法ピラミッドの作成；２）作成された平均ピラミッドとＭ進法ピラミッドを表すデータのパッキングとメモリー中への記憶；３）このパッキングされたデータをレジスタに移動させてアーキテクチャ計算に用いる；４）このデータを用いて整合誤差計算に用いる。これら４つの主要な用度を以下に説明する。
【０１２８】
この４つの主要な要素の内の最初の要素は、平均ピラミッド及び／又はＭ進法ピラミッドの作成動作を含んでいる。この開示の前の部分では平均ピラミッド及び／又はＭ進法ピラミッドの作成に適した方法と装置を述べているので、このような作成はこれ以上詳細には説明しない。しかしながら、本発明による計算上の複雑性の減少を理解するためには、平均ピラミッド又はＭ進法ピラミッドを作成するために必要とされる計算上の負荷を理解することが重要である。図示の例をここで提示する。
【０１２９】
ビデオストリームをＪ＋１子のレベルに分解し、レベル０が最も細密でありＪが最も粗であると仮定する。ＭＰＥＧ−２の主要プロフィール＠主要レベルビデオストリームの場合、Ｊの一般的な値は３である。Ｐをレベル０での画素の数とすると、レベルＪにおける画素の数はＰ／４Ｊとなる。
【０１３０】
平均ピラミッドの場合、Ｊ＝０以外のいかなる特定のレベルＪにおいても、特定のレベルに対する値を発生するために必要な計算は、画素１つ当たり３つの加算と１つのシフトを含む。Ｊ＝０の場合、平均ピラミッドはオリジナルの映像自身であり、計算は必要ない。したがって、それを発生するための演算の総数は４／３＊Ｐであり、Ｊが大きい場合の限界内である。
【０１３１】
Ｍ進法ピラミッドの場合、Ｊ＝０以外のいかなる特定のレベルＪにおいても、特定のレベルに対する値を発生するために必要な計算は、画素１つ当たり３つの加算と１つのシフトを含む。すなわち、Ｍ進法ピラミッドは０からＪ−１までの全てのレベルでの計算が必要である。さらに、各画素に対して、Ｍ−１回の比較動作を実行する必要がある。したがって、計算の回数はＪが大きい場合の限界内である４／３＊Ｐ＊（Ｍ−１）である。
【０１３２】
上記の４つの主要要素の内の第２の要素は、作成された平均ピラミッドとＭ進法ピラミッドを表すデータをパッキングしてメモリー中に記憶する動作を含む。本発明の少なくとも１つの実施形態が利用する動作推定スキームは、例えばＭ進法データを定義済みのデータワード中に「パッキング」して計算上の要件とメモリー帯域幅要件を達成することに依存している。すなわち、Ｍ進法ピラミッドを表すデータを、後続の記憶、検索及び処理などの動作が効率的に実行されるように非常に特定的な方法で配置する。Ｍ進法データのこの「パッキング」は、一般のマイクロプロセッサ又はコンピュータアーキテクチャで用いられるような本発明による方法を高速でソフトウエア的に実現するためには重要である。
【０１３３】
的確にパッキングできるかどうかは動作推定のためのブロックサイズ、すなわち各画素での状態の数Ｍと特定のアーキテクチャの場合のレジスタサイズとによって異なる。例えば、一般的な画素ブロックサイズ（すなわち、Ｎ１ｘＮ２ブロック、ここでＮ１は行の数であり、Ｎ２は列の数を示す）は１６ｘ１６、１６ｘ８又は８ｘ８個の画素ブロック（すなわち、Ｎ２＝１６又はＮ２＝８）である。Ｍ個のレベルを表すために用いられるビットの数はＮであり、Ｎは歪みを計算する正にその方法によって異なる。
【０１３４】
歪みは２つの画素ブロック同士間の非類似性の尺度である。例えば、符号化される画素ブロックと基準のが素ブロック間の歪みは、この２つのブロック間で倫理的排他ＯＲ（ＸＯＲ）演算を実行することによって計算される。歪みはこのＸＯＲ演算から結果とし得られる”１”の数に等しい。１がない（すなわち、歪みがゼロに等しい）場合、画素ブロックは正確に整合していることになる。多くの１、例えばしきい値レベルを越える数の１がある場合、画素ブロックは整合しない。１の数がしきい値未満であれば、画素ブロックは正確に整合していないまでも非常に類似している。歪みをこのように計算すると、ＮはＭ−１にもなる。Ｍ＝３の場合、Ｎ＝２で一般的に十分である。
【０１３５】
図９に本発明を理解する際に有用な画素情報を表すパッキングされた又はブロッキングされたデータを示す。具体的には、図９は複数の画素ブロックを示しており、その各々の画素ブロックが複数のそれぞれのワード（図では４つのワードが示されている）によって表され、各々のワードが複数の画素（図では４つの画素が示されている）を表す情報を含んでいる。これらのブロックは垂直方向デマケーションＶＢ１及びＶＢ２並びに水平方向デマケーションＨＢ１及びＨＢ２によって示される。各「ｘ」はＭ個の状態を有する１つの画素を表し、画素の各ボックス化されたグループが１つのデータワードを表す。
【０１３６】
図９に、レジスタサイズＮ＊Ｎ２がワードサイズに等しい場合を示す。すなわち、３２ビットというレジスタサイズによって、三進法ピラミッド（Ｍ＝３、Ｎ＝２）の１６ｘ１６画素ブロックのライン全体を示すことができる。
【０１３７】
しかしながら、各画素の状態の数（Ｍ）、行の数（Ｎ１）、列の数（Ｎ２）及び処理されている特定のピラミッドレベル（Ｊ）によっては、レジスタサイズＮ＊Ｎ２はワードサイズより大きくなったり小さくなったりする。レジスタサイズＮ＊Ｎ２がワードサイズより大きい場合、ライン中のデータを表すのに２ワード以上を使用する必要がある。レジスタサイズＮ＊Ｎ２がワードサイズ未満であれば、図１０を参照して以下の述べるようにデータは冗長記憶内容とオーバーラップさせて記憶させてもよい。
【０１３８】
図１０に、本発明を理解する際に有用な画素情報を表すパッキングされた又はブロッキングされたデータを図示する。具体的には、図１０は複数の画素ブロックを示しているが、その各々の画素ブロックが複数のそれぞれのワード（図では４ワード）によって表され、各々のワードが複数の画素（図では４画素）を表す情報を含んでいる。これらのブロックは、垂直方向デマケーションＶＢ１からＶＢ４と水平方向デマケーションＨＢ１とＨＢ２によって示される。各「ｘ」はＭこの状態を有する１つの画素を表し、画素の各ボックス化されたグループが１つのデータワードを表す。
【０１３９】
図１０は、レジスタサイズＮ＊Ｎ２がワードサイズ未満であり、このため、データが冗長記憶内容とオーバーラップするように記憶される場合を示している。この２つの４ビット画素ブロックは垂直方向デマケーションラインの両側からの画素を含んでいることに注意されたい。したがって、各ワードはそのブロックからのデータと、水平方向に互いに隣接する２つのブロックからのデータとを、を含んでいる。より細かいレベルで小さい探索範囲を持つ階層的な動作推定スキームでは、この方法は負荷の数を非常に小さい数値に保ち、これによって、メモリーの帯域幅を減少させている。オーバーラップがない場合、基準フレーム中のブロックが水平方向ブロック境界に対応しない場合には、隣接する水平方向ブロックに対応する追加のワードをロードする必要がある。
【０１４０】
パッキングプロセスでは、各画素に対して２つのＡＬＵ演算並びにシフト演算及び論理ＯＲ演算が必要である。したがって、非オーバーラップパッキングの場合（図９を参照）、画素毎の演算数は８／３Ｐである。オーバーラップパッキングの場合（図１０を参照）、さらなるシフトとＯＲ演算が必要である。
【０１４１】
４つの主要な要素の内の第３の要素は、パックされたデータをレジスタ中に移動させて算術計算できるようにする動作を含む。具体的には、この主要な４つの要素の内の第３の要素はメモリー帯域幅問題、すなわち、レジスタに対するデータの出し入れの速度とこのような移動の必要は発生回数を含意している。
【０１４２】
図５に、本発明の理解に有用な計算デバイスのある部分、特にメモリー帯域幅問題を示す。具体的には、図５は汎用、メモリーモジュール５１０、キャッシュメモリーモジュール５２０、データバス５３０、汎用レジスタ５４０及び算術／論理演算ユニット（ＡＬＵ）５５０を備えるマイクロプロセッサ又はコンピュータアーキテクチャのある部分を示している。汎用レジスタファイルは、複数のレジスタグループを含むものと考えられる。
【０１４３】
例えばＭ進法ピラミッドを表すパッキングされたデータはメモリーモジュール５１０に記憶される。このデータの処理、例えば動作推定プロセスを実行するには、最初に、データを汎用レジスタファイル５４０に移動させる必要がある。これは、所望のデータワードをキャッシュメモリーモジュール５２０から又は、必要に応じて、メモリーモジュール５１０から直接に検索することによって達成される。このデータはメモリーモジュール５１０から信号経路Ｓ１を介してキャッシュメモリーモジュール５２０に、またキャッシュメモリーモジュール５２０からデータバス５３０を介して汎用レジスタファイル５４０にカップリングされる。次に、このデータは、反応レジスタファイル５４０中の複数のレジスタファイル５４０又はレジスタグループの内の１つに記憶される。
【０１４４】
このデータに対して算術演算又は論理演算を実行するために、このデータは第１の信号経路Ｓ２（又はＳ３）を介してＡＬＵ５５０にカップリングされる。ＡＬＵ５５０によって実行される算術演算又は論理演算が第２のオペランドを必要とする場合、この第２のオペランドが第２の信号経路Ｓ３（又はＳ２）を介してＡＬＵ５５０にカップリングされる。すると、ＡＬＵ５５０の出力は汎用レジスタファイル５４０内のレジスタに記憶される。次に、この記憶された出力はメモリーキャッシュ５２０を介してメモリー５１０に記憶され、これによってデータバス５３０と信号経路Ｓ１を利用する。
【０１４５】
画素を表すデータワードが汎用レジスタファイル５４０中のレジスタ又はＡＬＵ５５０の算術／論理処理エレメントのサイズより大きい場合、データワードはインクレメント的に処理される。すなわち、データワードは、データワード全体が処理されるまで、適切なサイズを持つ一連のサブワードとして処理される。
したがって、データワードへの画素情報の表示を、汎用レジスタファイル５４０又はＡＬＵ５５０の算術又は論理処理エレメントに制約することによって、データワードは一連のサブ演算によってではなく１回の演算によって処理される。
【０１４６】
主要な４つの要素の内の第４の要素に関連して説明される誤差計算を実行するためには、後で処理するためにデータを表す画素を様々なレジスタに入れる必要がある。簡単に言えば、誤差計算を用いて、画その強度レベルの整合を発見して、ある時間にわたる画像内（例えば、連続する映像フレーム内）の画素ブロックの動作を識別する支援とする。したがって、図５に示す計算装置を、例えば図１のＭＰＥＧ様符号化システム１００の動作推定モジュール１５０部として用いてもよい。
【０１４７】
オリジナルの映像の画素ブロック中の各画素の強度レベルを８ビットで表し、レジスタサイズが３２ビットに等しいとすると、画素ブロックのほんの小部分を１時にレジスタ中にロードできるに過ぎない。したがって、画素の強度レベルをオリジナル映像（すなわち、Ｊ＝０）に整合させる際には、多くの検索や処理や記憶の動作を実行して、２つの画素を比較しなければならない。しかしながら、Ｍ進法では、画素ブロックと関連する強度レベルデータのほとんど（又はすべての）が一時にロードされ、これによってメモリー帯域幅要件をかなり節約する。多くの場合、現行の（オリジナルの）映像は動作推定の開始時にレジスタ中にロードでき、また、その特定のブロックの探索時全体にわたってそこに常に留まる。
【０１４８】
本発明を表すパックされたデータを用いた整合する画素ブロックの探索を次に説明する。この探索は、現行画素ブロック内の画素の画素強度レベルを例えば先行するフレームの選択された探索領域中の画素から成る類似サイズのブロックと比較するステップを含む。したがって、処理されている基準フレームの現行画素ブロックを例えばレジスタファイル５４０中にロードする必要がある。ここに説明するパッキング方法を利用して、ライン内の多くの画素に対応するＭ進法値が１ワード中に記憶される。例えば、｛Ｍ＝３、Ｎ＝２、Ｎ２＝１６｝の場合、１６の３２ビットワードを例えばレジスタファイル５４０のレジスタにロードする必要がある。
【０１４９】
説明の目的上、探索範囲は−Ｋ１からＫ１という垂直方向探索範囲と＋Ｋ２からＫ２という水平方向探索範囲から成り、ここで、Ｋ１は垂直方向を示し、２Ｋ＋１は行の数を示し、Ｋ２は水平方向を示し、２Ｋ２＋１は列の数を示すものと仮定する。
【０１５０】
最初のステップはゼロ探索ベクトルデータをレジスタ中にロードすることである。ゼロ探索ベクトルデータは、（例えば、粗ピラミッドレベルからの）前の推定値に基づいたゼロ洗練値を含むことがある。ゼロ探索ベクトルはブロック境界と整合する場合、すなわち、オーバーラップした記憶内容が境界との不整合を覆うに十分である場合、そのブロックに対応するワードをロードする必要があるだけである。そうでない場合、２集号以上のワードをロードして、このロードされたワード集合に対してシフト、マスク及び論理ＯＲ演算を実行して、データをレジスタ内で適切に整合させる必要がある。
【０１５１】
現行ブロックと現時点で識別された探索ブロック間の誤差が次に計算される。整合することがわかったら、現行ブロックと関連する動作ベクトルが決定される。基準フレーム中の次の画素ブロックが現行ブロックとして選択され、「新しい」現行画素ブロックに対する探索プロセスが繰り返される。
【０１５２】
整合しないことが認められた場合、水平方向の探索に移行する。すなわち、探索ウインドウが、例えば１画素分だけ水平方向にシフトする。さらに、負荷の数が、水平方向基準ブロックがブロック境界に沿って存在するかどうかによって異なる。次に、現行ブロックと現時点で識別されている探索ブロック間の誤差を計算して整合するかどうかを識別するステップが繰り返される。これらのステップは、水平方向探索範囲が検査されるまで繰り返される。
【０１５３】
水平方向探索範囲が現行ブロックに対する整合を発見することなく検査されたら、探索ウインドウは垂直方向に１ラインだけシフトして、水平方向探索範囲全体（−Ｋ２からＫ２）が（整合が発見されるまで）再度検査される。このプロセスは、探索範囲中の全ての垂直方向位置（２Ｋ１＋１位置）で繰り返される。これは重複がない場合である。
【０１５４】
主要な４つの要素の内の第４の要素は、整合誤差の計算用のデータの使用を含んでいる。例えば、現行ブロック（ｃｉ）が前の又は基準のブロック（ｐｉ）と整合するかどうか（すなわち、同じか又は類似しているか）を判断するために、２つのブロックを排他ＯＲ（ＸＯＲ）演算して結果を出す。その結果中の１の数がこの２つのワード間の不整合の数である。不整合の数がゼロ（すなわち、結果がゼロ）又はしきい値未満であれば、現行ブロック（ｃｉ）は前の又は基準のブロック（ｐｉ）と整合していると言われる。探索を実行するときに、この誤差計算は、現行ブロック（ｃｉ）と整合する前の又は基準のブロック（ｐｉ）が見つかるまで繰り返し実行される。
【０１５５】
上記のパッキング・記憶方法を利用することによって、誤差整合計算を実行するために必要とされる処理とメモリー帯域幅は大幅に減少する。そのうえ、データがパッキングされてオーバーラップするように記憶されると、検査中の前の又は基準のブロック（ｐｉ）に起因しないエラー誤差計算結果中のいかなる不整合も無視される。
【０１５６】
図１１に、本発明の理解に役立つ画素情報を表すパッキングされた又はブロックかされたデータを図示する。具体的には、図１１は複数の画素ブロックを示し、各画素ブロックはそれぞれが複数のそれぞれのワード（図では４ワード）によって表され、各ワードは、複数の画素（図では４画素）を表す情報を含む。これらのブロックは垂直方向でマーケーションＶＢ１からＶＢ４及び水平方向デマケーションＨＢ１とＨＢ２によって示される。各「ｘ」が、Ｍ個の状態を有する１つの画素を表し、各ボックス化された画そのグループが１つのデータワードを表している。
【０１５７】
図１１に、画素ブロックの１つのラインを提供する、非鎖線で示された、２つのワードからの情報を含む鎖線で示された現行ブロックｃｉを示す。したがって、各ラインに対する２ワードの各々の全体を用いる誤差計算は上記のように実行されるが、現行ブロックｃｉの外部のデータに起因する結果としてのワードの部分は単に、整合があったかどうかの判断の際には無視される。これは、各ブロックライン中の全てのワードに対して実行し、その結果を累積する必要がある。
【０１５８】
本発明の１実施形態では、ＸＯＲ結果の内の１つが、例えばサイズ２５６のテーブルに関してテーブルルックアップによってカウントされる。この実施形態では、ＸＯＲ結果を保持しているレジスタ内の適切なビットがバイトに分割され、テーブルルックアップが実行されて、累積されたＸＯＲ結果が加算されて最終的な誤差数字となる。
【０１５９】
既述したように、Ｍ進法ピラミッドは平均ピラミッドから構築される。したがって、平均ピラミッドは現行のＭ進法ピラミッドレベルにとって利用可能である（すなわち、平均ピラミッドはＭ進法ピラミッドの構築中に記憶されて、必要に応じて検索され得る）。また、平均値はブロック境界内に存在する各ブロックに対して利用可能であると仮定されるが、その理由は、この情報が平均ピラミッド中の最も粗であるレベルから得ることができるからである。
【０１６０】
平均ピラミッド情報を整合判断基準の１部として用いる場合、各シフト演算にとって、シフトされた基準ブロックに対する平均を計算する必要がある。水平方向シフトの場合、これは２Ｎ１個の負荷と、Ｎ１回の減算と、Ｎ１回の加算とに等しく、さらに水平方向では、２Ｎ２個の負荷と、Ｎ２回の加算とＮ２回の減算を必要とする。また、平均整合は一般的には、平均の誤差をＸＯＲの誤差を合成するには１回の減算と１つの加算を必要とする。
【０１６１】
三進法ピラミッド例との平均整合演算を実行するには、１６のワードをレジスタ中のロードして平均値から減算し、１６の新しいワードを次にレジスタにロードして平均値に加算する。平均ピラミッドがオーバーラップパッキングされて記憶された（図１０を参照して上述した）場合、乗算又は除算（シフト演算を用いて実行されることがある）を実行するために追加の演算が必要となり得ることに注記すべきである。したがって、平均計算を１回実行するには３２回の負荷演算と３４回の算術又は論理演算が必要である。１つの平均値整合に必要な計算の総数は３６プラス、あらゆる乗算と除算（図では４つ）の回数である。
【０１６２】
全探索ブロック整合を直接的に適応することは極めて非効率的であるので、本発明の方法を高速化する階層的スキームを考慮するのが有用である。一般的な階層的なスキームにおいては、初期レベルピラミッドは映像から構築される。より粗である各ピラミッドレベルはフィルタリングされ、（粗雑であるという点で）先行する映像ピラミッドのサブサンプリング版となる。動作は最初にピラミッドのより粗であるレベル（範囲が最も細密でオリジナルの解像度における範囲よりはるかに低いレベル）で推定され、次に、小さいウインドウ上での探索が洗練されるより細密なレベルに伝搬する。範囲はより細密な解像度（より多くの画素があり、したがって、整合誤差計算はより多くの計算を必要とする）では全く小さいので、最も細密なレベルでの全探索ブロック整合動作に関する計算数がかなり減少する。
【０１６３】
強度ベースの整合の替わりにＭ進法整合のレベルの１部（又はすべて）を用いることによって、特定のレベルにおける計算上の負荷が２桁だけ減少し、メモリー帯域幅要件が６から７桁だけ減少する。これによって、Ｍ進法ピラミッド計算にとって必要とされる余分の計算が相殺され、計算回数とメモリー帯域幅がかなり減少する。また、Ｍ進法ピラミッドも、映像予備処理及びブロック分類（例えば、上記のようなもの）などの他の目的にも有用であり、また、余分の計算リソースを、例えば本発明を用いるビデオエンコーダ内の別のモジュール中で利用してもよいことに注意されたい。
【０１６４】
本発明を、Ｍ進法ピラミッドから得た特徴ベクトルに基づいた動作推定スキームの文脈内で説明した。この動作推定スキームは、類似の階層的動作推定スキームより高速であり、また、メモリー帯域幅要件が少ない。本発明は特に、本発明の計算上の利点とメモリー帯域幅上の利点をよりよく図示するために例示の三進法ピラミッド（Ｍ＝３）応用例の文脈内で説明した。他のＭ値、他のブロックサイズ及び類似物を用いても類似の利点が認識されよう。当業者及び本発明を知った者は、添付クレームの範囲内である他の順列に本発明の教示を容易に応用できるであろう。
【０１６５】
パックデータ構造又はワードは、少なくとも２つの画素に関連する情報を含んでいる。パックデータ構造は、連続する論理ＯＲ演算とシフト演算を用いて、データセグメント（例えば、バイト）を表す２つ以上の画素をより大きいデータワード（例えば、３２ビットワード）中に挿入して、パックデータ構造を形成することによって形成される。次に、パックデータ構造は、後続の処理を容易化する様な仕方で記憶される。例えば（上述したように）、４つの８ビット画素を１つの３２ビットデータ構造中に記憶させ、８個の３２ビットデータ構造を用いて１つの画素ブロックを記憶する。このように、後続のブロックレベル処理を、パックデータ構造を利用して効率的に実行する。
【０１６６】
ブロックの１行当たりのワードの数（ＷＰＲ）は次式で計算される：
【０１６７】
【式１１】
2004503951.tif 000013
【０１６８】
ここで、ＭｊはレベルＪのＭ進法ピラミッドであり、ＷＩＤＴＨはＭ進法ピラミッドの幅であり、ＨＥＩＧＨＴはＭ進法ピラミッドの高さであり、ＢＬＫ＿ＷＩＤＴＨはＭ信号ピラミッド内の画素ブロックの幅であり、Ｎは１画素当たりのビット数であり、Ｎ＿ＯＶＥＲＬＡＰ＿Ｌは、パッキングしている際のブロックの左側でオーバーラップする画その数であり、ＷＯＲＤＳＩＺＥはブロックがパッキングされるデータタイプのサイズ（ビット数）であり、Ｎ＿ＵＮＵＳＥＤ＿ＢＩＴＳは、ＷＯＲＤＳＩＺＥのサイズを有するデータタイプを表すパッキングされたデータ中の不使用ビットの数である。
【０１６９】
ＷＯＲＤＳＩＺＥは様々なデータをパッキングする前に選択されたり固定されたりすることに注意すべきである。加えて、パッキングされたデータは、パッキングされるワード中のあらゆる可能なビット位置を占めるわけではないことが決定される（例えば、３つの８ビット画素表示物を３２ビットワード中にパッキングする）。したがって、ＷＰＲはワード中の不使用ビット数によって修正される。
【０１７０】
形成された１つの重要なパックデータ構造はパッキングされたフレームを含むが、この場合、パッキングされたフレーム内の各ワードは複数行の内の１つ、すなわち画素ブロック内のＭ進法画素の行全体又は部分的な行を含む。パッキングされたフレーム内の各ワードもまた、オーバーラップパッキングのために水平方向に隣り合った画素ブロックの対応する行からの追加の画素を含んでいる。このようなパッキングされたフレームはオプションのデータパッカー１３２によって発生されてアンカーフレームメモリー１７０に記憶される。
【０１７１】
本発明の冗長記憶実施形態では、各データワードは、これまた別のデータワードに含まれる画素情報を含むことに注意することが重要である。すなわち、第１のデータワードは第１の複数の水平方向は位置画素用の画素情報を含み、第２のデータワードは、第２の複数の水平方向は位置が素用の画素情報を含み、第１と第２の複数の水平方向は位置が素は共通の（すなわち、共用の）が素情報を含んでいる。
【０１７２】
同様に、本発明のオーバーラップ記憶実施形態では、各データワードは少なくとも２つの画素ブロックから成る隣り合った行からのが素情報を含む。すなわち、データワードは、第１の画素ブロックの行ともう１つの隣接した画素ブロックの隣接した行からの画素情報を含んでいる。
【０１７３】
利点として、図１２の方法１２００の場合のように、対応する行からの追加の画素は、画素ブロック内のＭ進法画素の内の複数行、全体行又は部分的行と共にレジスタ中にロードされる。このように、画素ブロック内のＭ進法画素の内のロードされた複数行、全体行又は部分行は、単なるＸＯＲ演算とロード演算ではなくＸＯＲ演算とシフト演算を用いて迅速に処理されて、水平方向探索を実行する。
【０１７４】
図１２に、本発明による画素ブロック整合のための探索方法のフローチャートを示す。具体的には、図１２は、例えば、各々の予測モード符号化済みブロック、動作ベクトル及び残余又は誤差情報を準備するブロックベースのエンコーダでの使用に適す探索方法を示す。このようなエンコーダの効率にとっては、予測されている画素ブロックと同一な少なくとも類似の画素を示す動作ベクトルを提供し、これによって、残余又は誤差情報が可能な限り減少するようにすることが重要である。したがって、図１２の探索方法は、映像又は映像ピラミッド中の各画素ブロックに対して、基準の映像又は映像ピラミッド中の画素ブロックの整合（又は類似性）を識別するために用いると利点がある。
【０１７５】
方法１２００は、現行の画素ブロック（例えば、予測される画素ブロック）を、例えば図１２を参照して上述したように処理され記憶された記憶済みの映像又は映像ピラミッド内の画素情報と比較する。
【０１７６】
図１２の方法１２００は、パッキングされたドメイン基準映像又はパッキングされたドメイン基準映像ピラミッドを使用して用いれば利点がある。例えば、低域通過フィルタリングされサブサンプリングされた現行の画素ブロックをほぼ同じ粗雑さを持つ映像ピラミッド（例えば、現行の画素ブロックとＪ＝３という粗雑さを持つ基準映像ピラミッド）を比較することによって、各現行画素ブロックの整合（又は整合の欠如）を発見するに必要な処理時間を軽減できる。
【０１７７】
図１２の方法はステップ１２０２で入力されてステップ１２０４に進み、ここで、現行画素ブロックは例えば、予測的に符号化される映像フレーム（又は関連の映像ピラミッド）の第１の画素ブロックに等しいように設定される。現行画素ブロックは基準の映像又は映像ピラミッドを形成するパッキング済みドメイン画素ブロックと比較されるので、第１画素ブロックは、基準映像又は映像ピラミッド様に使用される特定のパッキング済みドメイン表示物に従って（必要に応じて）フォーマッティングされて、現行の画素ブロックとして単数（又は複数の）レジスタに記憶される。方法１２００は次にステップ１２０６に進む。
【０１７８】
ステップ１２０６では、ゼロ探索ベクトルが１つ以上のレジスタにロードされる。すなわち、特定の探索範囲にとって十分な左右のオーバーラップするデータを含むパッキングされたデータドメイン基準ワード（又は基準ブロック）が１つ以上のレジスタにロードされる。オーバラップするパッキング済みデータを基準ワード（又はブロック）のパッキング済みデータと共にロードすることによって、整合動作を、さらなるロード動作無しで限られた範囲内で実行する。複数のワードを用いて形成されているゼロ探索ベクトルの場合、ゼロ探索ベクトルが複数のワードから抽出されて、基準映像又は映像ピラミッドに対して用いられる特定のパッキング済みドメイン表示物に従って（必要に応じて）フォーマッティングされる。ゼロ探索ベクトルデータは、例えば、前の（すなわち、より粗である）ピラミッドを用いて与えられた先連度を含むか又は、このゼロ探索ベクトルデータは単に、探索される領域の左上部分を含む。この方法１２００は次にステップ１２０８に進む。
【０１７９】
ステップ１２０８では、現行ブロックと探索ベクトルデータによって識別された探索間の誤差が計算される。例えば、現行画素ブロックは探索ベクトルデータによってその位置を識別された画素ブロックとＸＯＲ演算されて、この２つの画素ブロック間の歪み（すなわち、差）が決定される。この歪みは、既述したように、２つの画素ブロック同士間の差（ＳＡＤ）の和を含んでいる。論理ＸＯＲ比較の場合、このＳＡＤは二進法の１のカウント値を含むが、この場合、１は各々が、基準の画素ブロックの対応するビット又は画素と整合しない現行画素ブロックのビット又は画素を表している。この歪みの大きさは、２つの画素ブロック間の整合（完全な整合では歪みはゼロ）又は整合の欠如を示している。方法１２００は次にステップ１２１０に進む。
【０１８０】
ステップ１２１０では、ステップ１２０８の計算の結果整合が発見されたかどうか照会される。すなわち、ステップ１２１０では、２つの画素ブロックに対する排他委的演算すなわち論理演算によって与えられた二進法の１の数が整合又は近整合を示すしきい値レベル未満であるかどうか照会される。ステップ１２１０での照会に対する回答が肯定的であれば、方法１２００はステップ１２１４に進む。ステップ１２１０での照会に対する回答が否定的であれば、方法１２００はステップ１２１４に進む。
【０１８１】
ステップ１２１４では、動作ベクトルが決定される。すなわち、現行画素ブロックと整合する画素ブロックに対して現行ブロックを関連付ける動作ベクトルが決定される。例えばビデオエンコーダ中での後続の符号化ステップの間、現行画素ブロックは動作ベクトル（整合する基準ブロックを指示する）と残余（現行画素ブロックと整合する画素ブロック間の符号化済みの差）として符号化される。方法１２００は次にステップ１２１６に進む。
【０１８２】
ステップ１２１６では、現行の画素ブロックが現行の映像又は映像ピラミッドの再度の画素ブロックであるかどうか照会される。ステップ１２１６での照会に対する回答が肯定的であれば、方法１２００はステップ１２２０に進み、脱出する。ステップ１２１６での照会に対する回答が否定的であれば、方法１２００はステップ１２１８に進む。
【０１８３】
ステップ１２１８では、現行画素ブロックと識別された画素ブロックは、予測的に符号化される映像フレーム内の次の画素ブロックに等しくなるように設定される。次の画素ブロックは次に、現行画素ブロックとして１つ以上のレジスタに記憶される。方法１２００は次にステップ１２０６に進み、ここでプロセスが繰り返される。
【０１８４】
ステップ１２１２では、ステップ１２０８で現行画素ブロックと探索ベクトル出たによって識別された基準フレームの画素ブロック間の差の計算値が記憶される。具体的には、排他的論理ＯＲ（ＸＯＲ）演算で得られた１の数によって決まる誤差レベル又は歪みの場合、１の数を示す数値（すなわち、１の数の和）が記憶されて基準画素ブロックと関連付けされる。方法１２００は次にステップ１２２２に進む。
【０１８５】
ステップ１２２２では、探索ウィンドウが水平方向にシフトする。すなわち探索ウィンドウは例えば１画素分だけ左又は右へ水平にシフトする。本発明の１つの実施形態では、ステップ１２０６で初期値のゼロはベクトルデータを探索して、参照フレームの左上方においてウィンドウを記述する。この実施形態では、探索ウィンドウは参照フレームの全範囲にわたって左から右へ水平にシフトする。参照フレームの端に達すると、ウィンドウは１つのラインによって垂直下方にシフトし、さらに１画素分だけ右から左へシフトする。方法１２００は次にステップ１２２４へ進む。
【０１８６】
事前定義された範囲内での探索ウィンドウのシフトは追加データのロードすることなしに達せされる。その理由は、レジスタファイル内にロードされた参照画素ブロック（又はその部分）はパックされたドメインデータの左右のオーバーラップ部分のいくつか又は全てを含むからである。従ってシフト操作はロードされた参照画素のブロック行を現在の画素のブロック行に再整合する。例えば、±２画素の水平探索範囲が１６ビット行の画素に用いられ、またステップ１２０６で２０ビットワードがレジスタ内にロードされれば、レジスタの再ロードを行うこと無く５回のシフト及び比較操作を実行することができる。これはメモリリソース利用におけるかなりの節約を意味する。事前定義されたオーバーラップ範囲を超えた場合には、レジスタ内にロードされた様々なワードを（シフト及び論理和の操作を用いて）フォーマッティングすることが必要となる。
【０１８７】
ステップ１２２４では、水平方向の範囲オーバー状態が存在するかどうかについて照会がなされる。すなわち、ステップ１２２４における探索ウィンドウの水平方向シフトが探索されている参照フレームの境界を超えたかどうかについて照会が行われる（例えば、５回のシフト及び）。選択的にオーバーラッピング記憶方法が用いられている場合は、ステップ１２２４での照会によって、その範囲オーバー部分（例えば、右への範囲オーバー、又は左への範囲オーバー）がシフト動作によって超えられたかどうかが示される。ステップ１２２４での照会が否定的な回答を得た場合は、方法１２００はステップ１２０８に進む。ステップ１２２４での照会に肯定的な回答があった場合は、方法１２００はステップ１２２６へ進む。
【０１８８】
ステップ１２２６では、探索ウィンドウは例えば１つのラインによって垂直にシフトする。本発明の１つの実施形態では、探索ウィンドウは水平の範囲オーバー状態が存在するまで右にシフトした後、１つのラインによって下方にシフトする。その後、ステップ１２２４における照会によって記されたように左の境界が横断されるまで、探索ウィンドウの水平シフトは右から左に進行する。次に方法１２００はステップ１２２８に進む。ステップ１２２８では、垂直方向の範囲オーバー状態が存在するかどうかについての照会がなされる。すなわち垂直シフトが、検査されている参照フレームを超えたかどうかについての参照が行われる。ステップ１２２８での照会に否定的な回答があれば、方法１２００はステップ１２０８に進む。ステップ１２２８での照会に肯定的な回答があれば、方法１２００はステップ１２３０に進む。
【０１８９】
ステップ１２３０では、最小記憶誤差が現在の画素ブロックに対する整合として選択される。すなわちステップ１２３０で、現在の画素ブロックに対する可能な整合の全てが検査され、各検査の誤差がステップ１２１２で記憶された。ステップ１２３０では、現在の画素ブロックが誤差についての最小差を持つ画素ブロックと関連するように、最小誤差が選択される。標準的なビデオエンコーダの場合この最小誤差がある閾値レベルを超えると、ビデオエンコーダは現在の画素ブロックのフレーム内コーディングの実行を選択できる。同様に誤差が第２の閾値レベルより低ければ、ビデオエンコーダは現在の画素ブロックのフレーム間コーディングの実行を選択して、フレーム間コーディング済画素ブロックを運動ベクトルと残余の誤差に関連付けることができる。次に方法１２００はステップ１２１４へ進む。
【０１９０】
図１２を参照して上述した方法１２００は、画素ブロックベースによる画素ブロックの歪み計算を用いることによって画素ブロックに整合する。すなわち比較される２つの画素ブロックはそれぞれレジスタファイル内にそっくりロードされる。複数の水平位置のそれぞれに対して、各レジスタファイルの排他的論理和の演算が実行される（すなわち、現在の画素ブロックは（全てのオーバーラップを含む）参照画素ブロックに関して複数の水平位置を通じてシフトする）。この方法は非常に良く機能する、とはいってもそれは必然的に画素ブロックを保持するために十分な数のレジスタを必要とする。今度はレジスタ制約下の処理環境内での使用に適した方法を図１３を参照して説明する。
【０１９１】
部分歪み測定法を用いて現在のブロックと探索ブロック間の誤差を計算する方法を図１３に示す。具体的に言えば図１３には、（全歪みの値ではなくて）部分歪み値を生成するための（画素別ではなくて）行毎の方法１３００が示される。図１３の部分歪み方法１３００の教示内容は図１２に関連して既述されたより一般的な場合にも容易に適用できる。
【０１９２】
図１３の方法１３００は、比較とシフトの機能を繰り返し実行することによって、現在の画素ブロック内のＮ画素の各行を参照画素フレーム内の画素の対応する行全体の複数のＮ画素部分と比較する。すなわち現在の画素ブロックは、参照画素フレーム内の画素の対応する行の部分と比較される。現在の画素ブロックの各行が参照画素フレーム内のそれぞれの対応する行と比較された後、現在の画素ブロックの行と参照画素ブロックの行との間の対応が垂直にシフトされて、処理が繰り返される。
【０１９３】
例えば８行画素ブロックを用いる本発明の実施形態では、現在の画素ブロックの８行が参照画素フレームの対応する８行と比較される（例えば、現在の画素ブロックの行１から８が参照画素フレームの行１から８に対応する）。次に行間の対応が１行だけ垂直にシフトされ（すなわち、現在の画素ブロックの行１から８は今度は参照画素フレームの行２から９に対応する）て、図１３の方法１３００が繰り返される。全ての行が比較されるまでこのプロセスが繰り返される。
【０１９４】
図１３の方法１３００はステップ１３０５に入ってステップ１３１０に進む。ステップ１３１０では、現在の画素ブロックの第１行が第１レジスタ内に記憶される。方法１３００は次にステップ１３１５に進み、そこで現在選択されている参照ブロックの第１行と全てのオーバーラップが第２レジスタ内に記憶され得る。方法１３００は次にステップ１３２０へ進む。
【０１９５】
ステップ１３２０では、第１レジスタと第２レジスタのコンテンツ間の歪みが計算されて部分（すなわち、画素全体に関しての部分的）歪みとして記憶される。すなわち第１レジスタと第２レジスタに排他的論理和の演算が行われて結果をもたらす。その結果における「１」の数が累算されて、部分歪みと見なされる値を生成する。そしてその部分歪みは記憶される。方法１３００は次にステップ１３２５に進む。
【０１９６】
ステップ１３２５では、第２レジスタが１画素値（すなわち、Ｎビット）だけシフトされる。次に方法１３００はステップ１３３０に進み、そこでレジスタの境界が超えられたかどうかについての照会が行われる。すなわち、ステップ１３２５でのＮビットのシフト操作によって、第１レジスタ内に記憶された画素の行が第２レジスタ内に記憶されたいかなる（又は不十分な）画素とももはや整合しないかどうかについての照会が行われる。ステップ１３３０での照会に否定的な回答があれば、方法１３００はステップ１３３５へ進む。ステップ１３３０での照会に肯定的な回答があれば、方法１３００はステップ１３４０へ進む。
【０１９７】
ステップ１３４０では、参照画素フレームからの新たなワードと全てのオーバーラップが第２レジスタ内にロードされる。すなわち第２レジスタの先行してロードされた画素に（参照フレーム内で）水平方向に近接する画像グループが第２レジスタ内にロードされる。方法１３００は次にステップ１３４５に進み、そこで新しいワードが必要に応じて（すなわち、新しいワードがパックされたデータ表示に適合しなければ）フォーマッティングされる。方法１３００は次にステップ１３２０へ進む。
【０１９８】
ステップ１３３５では、計算（ステップ１３２０）とシフト（ステップ１３２５）のステップが、適切な水平方向の探索位置（すなわち、参照画素フレーム内の画素の位置）のそれぞれに対して実行されたかどうかについての照会が行われる。ステップ１３３５での照会が否定的な回答を得た場合は、方法１３００はステップ１３２０に進む。ステップ１３３５での照会が肯定的な回答を得た場合は、方法１３００はステップ１３５０に進む。
【０１９９】
ステップ１３５０では、ブロック内の全ての行が検査されたどうかの照会が行われる。すなわち、計算（ステップ１３２０）とシフト（ステップ１３２５）のステップを通じて、参照画素フレーム内の画素の適切な近接行が対応する現在の画素ブロック行と比較されたかどうかについて照会が行われる。ステップ１３５０での照会が否定的な回答を得れば、方法１３００はステップ１３５５に進む。ステップ１３５０での照会が肯定的な回答を得れば、方法１３００はステップ１３６５に進む。
【０２００】
ステップ１３５５では、現在の画素ブロックの次の行が第１レジスタ内に記憶される。次に方法１３００はステップ１３６０に進み、そこで参照画素ブロックの次行プラス全てのオーバーラップが第２レジスタ内に記憶される。次に方法１３００はステップ１３２０へ進む。
【０２０１】
ステップ１３６５では、記憶された部分歪みが処理されて、現在の画素ブロックと参照画素ブロック間の相関関係についての指示が与えられる。すなわち、現在の画素ブロックの行の各水平位置について計算された部分歪みの値が、画素ブロックの他の行の各対応水平位置について計算された対応する部分歪みと関連付けられる。この様にして、現在のブロックと参照画素ブロックを関連付ける全体的な又は全歪みの値が決定される。
【０２０２】
参照画素フレーム内の垂直方向探索位置のそれぞれについて、図１の方法１３００が繰り返される。図１３の方法１３００は、現在の画素ブロックを複数の水平に近接する画素ブロックと比較することに注意されたい。例えば４×４画素ブロックが４×６参照ブロックと比較される場合には、部分歪み測定法が各行に対して実行される。従ってその機能は現在の画素ブロック行のそれぞれを３つの別個の参照画素ブロックの対応する行と比較することである。
【０２０３】
図１３の方法１３００では、特定の水平探索位置に対応する部分歪みはそれらが利用可能になるにつれて蓄積され、それによって探索を実行する処理システムのレジスタの要件を低減することは注意すべき重要な点である。
【０２０４】
本発明の１つの重要な実施形態は、レジスタのリソースが、現在の画素ブロック行、（全てのオフセットを含む）対応する参照ブロック行、及び処理される部分歪み測定値の全部を記憶することができないような「レジスタ制約下の」処理システムの場合に特に有効である。そのようなシステムでは方法１３００は水平方向探索位置の「バッチ」を処理するように適応することができる。例えば４×４現在画素ブロックと対応する４×９参照画素ブロックの場合には、方法１３００を用いて各行を２度処理することができる。具体的には、現在行と参照行との６回の比較を行う代りに、方法１３００は３回の比較を２セット行うように適応する。この様にして、画素データを記憶し歪みの結果を蓄積するのに必要なリソースが低減される。
【０２０５】
本発明の１つの実施形態では、データのパッキングが「リアルタイム」で実行される。すなわち、パッキング方法１２００において例えばそれぞれのステップ１２０６と１２０８の間に実行されるシフトと論理和の演算は、（例えば、ピラミッド計算のための）Ｍ進法ピラミッドの計算中に実行される。この様にしてメモリ帯域幅の利用及びパックされていないＭ進法の値の記憶が回避される。例えば図７の方法７００において、ステップ２１０と２１５は結合されて、ステップ２１０は参照フレームの１部分のＭ進法ピラミッドを構成し、一方ステップ２１５は（ステップ２１０で先に処理された）Ｍ進法ピラミッドの先に構成された部分をパックし記憶する。
【０２０６】
本発明の１つの実施形態では前記の動作推定機能の実施後、エンコーダ１０４はマクロブロックのパイプライン式方法を利用して残余の符号化機能を遂行する。マクロブロックのパイプライン化は、次のマクロブロックに進む前にマクロブロックを完全に処理することによってメモリ帯域幅の要件を最小化するために用いられる。すなわちパイプライン式の実施形態は、次のマクロブロックを処理するのに先立って各マクロブロックに対して多くの符号化ステップを実行する。この様にして、大きなマクロブロック（すなわち、映像フレーム）グループを処理するのに必要な「読込み、処理、記憶」の計算の繰り返しを著しく減少させることができる。
【０２０７】
パイプライン式アーキテクチャは複数の処理エレメント（ＰＥ）を用いて実現され、各ＰＥはそれぞれの例えばマクロブロックを処理して処理済マクロブロックを生成する。例えば各ＰＥは符号化モジュール１０４のために実行される機能の少なくとも一部を含むプロセッサ機能から構成されており、従って各ＰＥは、各マクロブロックに対する例えば動作推定、モード判断、動作補償、ＤＣＴ変換及び量子化の諸機能を遂行する。通常のメモリモジュールを全てのＰＥのために用いてもよいが、各ＰＥはメモリと関連付けられている。エンコーダ１０４の逆量子化、逆ＤＣＴ変換及び可変長コーディングの諸機能をまた各ＰＥの機能の中に包含して、（その効果において）ＰＥが単一マクロブロックの符号化専用の全符号化モジュールから成るようにすることができる。複数のＰＥの出力は出力バッファ１６０にカップリングされる。
【０２０８】
本発明の１つの実施形態において、符号化されるフレームがＰフレーム又はＢフレームの場合には、１９９７年１２月３１日出願の米国特許出願第０８／００２，２５８号（代理人整理番号第１２４５５号）に開示され参照してここに組込まれる方法を用いて、３つの大きさのタイリングを持つ２進法ピラミッド動作推定法（ＢＰＭＥ）が実行される。簡単に言えば、フレーム、奇数フィールド及び偶数フィールドに対して動作推定が実行される。フレームがＢフレームの場合は、前方及び後方動作推定の両方が実行される。パックされた画素記憶を持つＢＰＭＥによって、必要な演算の数とともにメモリ帯域幅の要件も効果的に低減される。各プロセッサが映像（例えば、スライス、マクロブロック又はブロック）のそれぞれの部分を処理するように作動する、パイプライン又は多重プロセッサ配置内の複数のプロセッサを、利用可能なメモリリソースに応じて選択的に用いることによって、ＢＰＭＥの手順はさらに加速される。プロセッサ間のデータアクセス時間を最小化するために、パイプライン又は多重プロセッサ配置の処理エレメント（ＰＥ）はオーバーラッピングデータ領域を選択的に利用し、それによってプロセッサ間のデータをコピーする操作の必要性を低下させる。
【０２０９】
パイプライン化された処理アーキテクチャ内のマクロブロックを処理する方法の工程系統図を図４に示す。具体的に言えば、図４の方法４００は多重処理環境内の複数の処理エレメントのそれぞれによって用いられ、そこではあるマクロブロックを次のマクロブロックに進む前に完全に処理することによって、メモリ帯域幅が最小化される。図４の方法４００は多重処理環境に良く適しているが、もちろん単一の処理エレメントだけを用いて実行してもよい。方法４００は１６×１６マクロブロックの例で議論されるが、方法４００の教示に従って他の領域サイズも処理可能であることは当業者に容易に理解されよう。
【０２１０】
処理される情報フレーム内のマクロブロックが、マクロブロックに対して「最良の」動作推定に帰結する動作推定処理を受けた後で、方法４００はステップ４０５に入る。次に方法はステップ４１０に進む。
【０２１１】
ステップ４１０では、現在のフレームのマクロブロックに対する１６×１６画素領域がキャッシュメモリ内にロードされる。次に方法はステップ４１５へ進む、そこではフレームモードに対する最良の動作推定を中心とする１８×１８画素領域（又はフィールドモードに対する最良の動作推定を中心とする１８×１０画素領域）が、それぞれの参照フレームからメモリ内にロードされる。
【０２１２】
ステップ４１０で利用された参照フレームが例えば連続するステップ４１５−１及び４１５−２に従って生成される。具体的には、ステップ４１５−１では双線形の補間法を用いて参照フレーム領域が補間され、ステップ４１５−２では９個の半画素位置のそれぞれに対する絶対差合計（ＳＡＤ）が計算される。次にモード判断の基準としての平均２乗誤差を用いて、最良の半画素動作推定が各モード（フレームモード又はフィールドモード）に対して選択される。この様にして、ロードする最大画素数は例えばＰフレームに対しては１３００となり、Ｂフレームに対しては２７００となる。ライン方向の補間を行うことによってデータサイズが適度なレベル１のキャッシュサイズ内に効果的に保たれる。従って
データの入手不可能性に起因する、キャッシュミスに対するサイクルペナルティ及び中央処理装置／ディジタル信号プロセッサ（ＣＰＵ／ＤＳＰ）のアイドリング時間が減少する。
【０２１３】
１８×１８画素領域をメモリ内にロードした（ステップ４１５）後、方法４００はステップ４２０に進み、そこでマクロブロックレベル量子化器のスケールが例えばレート制御モジュールによって計算される。次にマクロブロックレベル量子化器のスケールはモード判断モジュールと量子化モジュールに渡される。例示の実施形態では、量子化器のスケール計算は従来型のＴＭ５の方法では行われない。むしろ量子化器のスケール計算は、この開示内の別の場所で説明される方法に従って（例えば、モデルベースのフレームレベル量子化でバッファ飽和度ベースの量子化器スケールを平均することによって）行われ、それによって映像フレーム全体にわたって平滑な映像の質を保証する。方法４００は次にステップ４２５に進む。
【０２１４】
ステップ４２５ではコーディングモードが選択される。モード判断モジュールは先ず、半画素動作補償された歪みに基づいて、頂部から頂部と頂部から底部フィールド、及び底部から頂部と底部から底部フィールドの間で、フィールドを決定するための選択を行う。次にそれはまた必要に応じて、マクロブロック間の変化及びフレーム差の変化を計算する。代りに、フレーム差の変化は情景変化の検出中にプリプロセッサ内で計算されて、データへの再アクセスを最少化する。他のモードに対しては、半画素への細分それ自体において得られる歪みが用いられる。動作ベクトルをコーディングするのに要するビット数とオーバーヘッドビットが、各モードについて推定される。レート制御モジュール１４０はマクロブロックレベル量子化器のスケールを計算してそれをモード判断モジュール１０５へ渡す。マクロブロックに対する最良のモード判断は、その基礎を所与のマクロブロック量子化器スケールにおけるレート及び歪みの双方に置くことによって実現される。この機能を実行するための適切な装置が、１９９６年１０月２３日に出願され、参照してその全体がここに組込まれる米国特許第０８／７３８２２８号の中でより詳細に説明されている。方法４００は次にステップ４３０に進む。
【０２１５】
ステップ４３０では動作補償が要求されているかどうかについての照会が行われる。ステップ４３０での照会が否定的な回答を得た場合は、方法４００はステップ４４５へ進む。ステップ４３０での照会が肯定的な回答を得た場合は、方法４００はステップ４３５へ進む。
【０２１６】
ステップ４３５では、最良の動作推定としてキャッシュ内に現在記憶されているデータを用いて半画素の補償が繰り返される。さらにマクロブロックについてのクロミナンス成分がロードされて、動作補償の操作で用いられる。方法は次にステップ４４０へ進み、そこで動作補償された予測がマクロブロックから減算されて、残余が得られる。方法は次にステップ４４５に進む。
【０２１７】
ステップ４４５では例えば処理されている６つのマクロブロックのそれぞれに対して離散コサイン変換が実行される。方法は次にステップ４５０に進み、そこで変換された値はレート制御モジュールによって計算された量子化マトリックスと量子化スケールファクタを用いて量子化され、次にステップ４５５に進みそこで、ＶＬＣモジュールは動作ベクトルと量子化済ＤＣＴ係数を符号化する。動作ベクトルと量子化済ＤＣＴ係数は出力バッファと逆ＤＣＴモジュールにカップリングされる。次に方法４００はステップ４６０に進む。
【０２１８】
ステップ４６０では、逆量子化モジュールと逆ＤＣＴモジュールが残余を、それらがデコーダによって見られるように復元する。方法４００は次にステップ４６５に進み、復元された残余が予測に加算されて、再構成されたマクロブロックを得る。キャッシュサイズがより多くのマクロブロックを組込むことを可能にするならば、次のモジュールに行く前に（１つのマクロブロックではなくてむしろ）１セットのマクロブロック上で各モジュールの動作を繰り返すことによって、命令帯域幅を最小化できる。命令アクセスがより通常であるので、先取りメカニズムを持つアーキテクチャは前もって命令を容易に取出すことができて、それらをどのような待ち時間も無しに利用可能にする。パラレルプロセッサ又は単一命令（ＳＩＭＤ）プロセッサについては、複数のマクロブロックを単一命令ストリームで同時に処理することができる。これを図１４Ａと１４Ｂを参照して以下により詳細に説明する。方法４００は次にステップ４７０に進む。
【０２１９】
ステップ４７０では、フレームの最後のマクロブロックが処理されたかどうかについての照会が実行される。ステップ４７０での照会が否定的な回答を得た場合は、方法４００はステップ４７５へ進み、そこでフレーム内の次のマクロブロックが検索されて、ステップ４１０に進み検索されたマクロブロックが処理される。ステップ４７０での照会の回答が肯定的であれば、方法４００はステップ４８０に進みそこでそれは終了する。
【０２２０】
図１のＭＰＥＧのようなエンコーダ内で用いるのに適したパイプライン化された処理アーキテクチャを図１４Ａに示す。具体的には、図１４Ａは複数の処理エレメント（ＰＥ）１４００−１から１４００−Ｎから成る符号化装置の一部を表す。各ＰＥは命令バスＩ経由で命令（例えば、符号化命令）を、データバスＤ経由でデータ（例えば、マクロブロック）を受取る。各ＰＥはそれに応答して処理済出力データ（例えば、符号化されたマクロブロック）を生成する。
【０２２１】
本発明の１つの実施形態では、図１４Ａの複数のＰＥは単一命令複数データストリーム（ＳＩＭＤ）処理システムとして配置され、そこで各処理エレメントはプロセス、例えばスライス、マクロブロック又はブロック等の符号化されている情報フレームのそれぞれの部分を処理するために動作する。例えば図１４Ａは処理エレメントＰＥ１−ＰＥＮを、マクロブロック１（ＭＢ１）からマクロブロックＮ（ＭＢＮ）をそれぞれ処理して処理済マクロブロックＭＢ１゛からＭＢＮ゛を生成するものとして表している。
【０２２２】
特定の処理エレメントにマクロブロックを処理させるために必要な命令ストリームは同じなので、各処理エレメント１４００−１から１４００−Ｎはコントローラ（図示せず）から同じ命令を受取る。しかしながら、複数命令単一データストリーム（ＭＩＭＤ）処理システムは実行されて比較可能な結果を得ることができる。この様にして処理タスクは複数のプロセッサ間で分割することができ、それによって情報フレーム全体を符号化するための時間を減らすことができる。動作推定の場合には、複数命令複数データ処理システムを用いて、異なる処理エレメントを処理中情報フレームの各スライスに割り当てることができる。
【０２２３】
図１４Ａのパイプライン化された処理アーキテクチャ内での使用に適した処理エレメントの実施形態を図１４Ｂに示す。具体的には処理エレメント１４００はエンコーダの以下の機能的構成部品の直列接続で構成される：半画素解像度（ＨＰＲ）動作推定機能１４１０、モード判断機能１４２０、予測機能１４３０、離散コサイン変換（ＤＣＴ）処理機能１４４０、量子化（Ｑ）機能１４５０、逆量子化（Ｑ−１）機能１４６０、逆ＤＣＴ機能１４７０、及び再構成機能１４８０。
【０２２４】
さらにキャッシュメモリ１４９０が１つ以上の機能的構成部品に動作可能にカップリングされて、情報の一時記憶装置を作る。例えば動作推定機能１４１０によって生成された半画素解像度歪みがキャッシュメモリ１４９０内に記憶され、引き続いてモード推定機能１４２０によって使用される。図１４Ｂの処理エレメント１４００の機能的構成部品のそれぞれは、図１を参照して上述された対応する機能的構成部品と実質的に同じ方法で動作するので、処理エレメントの機能的構成部品を詳細に説明することはしない。
【０２２５】
ＭＰＥＧのような符号化システム１００は複数のモジュールから構成されるが、様々なモジュールによって実行される諸機能を図１に示すように分離したモジュールに孤立化させる必要は無いことが当業者に理解されよう。例えば動作補償モジュール１４５、逆量子化モジュール１２５及び逆ＤＣＴモジュール１３０から成るモジュールのセットは一般に「埋込式デコーダ」として周知である。さらに様々な予備処理機能（１０１及び１０２）及びレート制御機能（１４０）が、単一の処理エレメント（例えば、マイクロプロセッサ又はディジタル信号プロセッサ（ＤＳＰ））、又は並列処理の構成で配置された又はそれぞれの機能に関連した独立モジュールとして配置された複数の処理エレメントによって実行することができる。上記のアーキテクチャは、例えばＤＣＴ及び量子化タスクのようなある高度に複雑な計算タスクのための特殊目的ハードウェアを用いて実行することができる。
【０２２６】
本発明はこれらの処理を行うためのコンピュータ実現型の処理及び装置の形態で具体化することができる。本発明はまた、ＣＤ−ＲＯＭ、ハードディスクドライブ、又は他のコンピュータ読込可能記憶媒体のような具体的な媒体の中で実現されるコンピュータプログラムコードの形態で具体化することができ、そこではコンピュータプログラムコードがコンピュータ内にロードされてそれによって実行されるとき、そのコンピュータは本発明を実行するための装置となる。本発明はまた、例えば記憶媒体内に記憶されたものであれ、コンピュータ内にロードされ及び／又はコンピュータにより実行されるものであれ、又は例えば電線、ケーブル、光ファイバ、電磁放射線等のなんらかの送信媒体を伝って送信されたものであれ、コンピュータプログラムコードの形態で具体化することができ、そこではコンピュータプログラムコードがコンピュータ内にロードされてそれによって実行されるとき、そのコンピュータは本発明を実行するための装置となる。汎用マイクロプロセッサ上に実現されるとき、コンピュータプログラムコードのセグメントはマイクロプロセッサを構成して特定の論理回路を形成する。
【０２２７】
本発明の教示を具体化する様々な実施形態をここで詳細に示し説明したが、当業者はこれらの教示をさらに具体化する多くの他の様々な実施形態を容易に考案することができよう。
【図面の簡単な説明】
【図１】
ＭＰＥＧのような符号化システムの高レベルブロック図である。
【図２】
図１のＭＰＥＧのような符号化システムでの使用に適した適応レート制御方法のフローチャートである。
【図２Ａ】
図１のＭＰＥＧのような符号化システムでの使用に適した適応レート制御方法のフローチャートである。
【図２Ｂ】
図１のＭＰＥＧのような符号化システムでの使用に適した適応レート制御方法のフローチャートである。
【図２Ｃ】
図１のＭＰＥＧのような符号化システムでの使用に適した適応レート制御方法のフローチャートである。
【図３】
図１のＭＰＥＧのような符号化システムでの使用に適した方法のフローチャートである。
【図４】
パイプライン式処理アーキテクチャでマクロブロックを処理する方法のフローチャートである。
【図５】
本発明を理解する際に有用な計算デバイスの１部分の図である。
【図６】
ブロックベースの動作推定用の動作ベクトルを決定する際の計算上の複雑さを軽減する方法のフローチャートである。
【図７】
平均ピラミッドを発生するために用いられる量子化プロセスを示すグラフである。
【図８】
Ｍが３である、三進法ピラミッド？を発生するために用いられる量子化プロセスを示すグラフである。
【図９】
本発明を理解する際に有用な画素情報をパックデータ又はブロックデータで表示した図である。
【図１０】
本発明を理解する際に有用な画素情報をパックデータ又はブロックデータで表示した図である。
【図１１】
本発明を理解する際に有用な画素情報をパックデータ又はブロックデータで表示した図である。
【図１２】
本発明による画素ブロック整合を探索する方法のフローチャートである。
【図１３】
本発明による画素ブロック整合を探索する方法のフローチャートである。
【図１４Ａ】
図１のＭＰＥＧのようなエンコーダでの使用に適したパイプライン式処理アーキテクチャの図である。
【図１４Ｂ】
図１４Ａのパイプライン式処理アーキテクチャでの使用に適したエレメント処理の実施形態である。
【図１】
2004503951.tif 000014
【図２Ａ】
2004503951.tif 000015
【図２Ｂ】
2004503951.tif 000016
【図２Ｃ】
2004503951.tif 000017
【図３】
2004503951.tif 000018
【図４】
2004503951.tif 000019
【図５】
2004503951.tif 000020
【図６】
2004503951.tif 000021
【図９】
2004503951.tif 000022
【図１２】
2004503951.tif 000023
【図１３】
2004503951.tif 000024
【国際公開パンフレット】
2004503951.tif 000025
2004503951.tif 000026
2004503951.tif 000027
2004503951.tif 000028
2004503951.tif 000029
2004503951.tif 000030
2004503951.tif 000031
2004503951.tif 000032
2004503951.tif 000033
2004503951.tif 000034
2004503951.tif 000035
2004503951.tif 000036
2004503951.tif 000037
2004503951.tif 000038
2004503951.tif 000039
2004503951.tif 000040
2004503951.tif 000041
2004503951.tif 000042
2004503951.tif 000043
2004503951.tif 000044
2004503951.tif 000045
2004503951.tif 000046
2004503951.tif 000047
2004503951.tif 000048
2004503951.tif 000049
2004503951.tif 000050
2004503951.tif 000051
2004503951.tif 000052
2004503951.tif 000053
2004503951.tif 000054
2004503951.tif 000055
2004503951.tif 000056
2004503951.tif 000057
2004503951.tif 000058
2004503951.tif 000059
2004503951.tif 000060
2004503951.tif 000061
2004503951.tif 000062
2004503951.tif 000063
2004503951.tif 000064
2004503951.tif 000065
2004503951.tif 000066
2004503951.tif 000067
2004503951.tif 000068
2004503951.tif 000069
2004503951.tif 000070
2004503951.tif 000071
2004503951.tif 000072
2004503951.tif 000073
2004503951.tif 000074
2004503951.tif 000075
2004503951.tif 000076
2004503951.tif 000077
2004503951.tif 000078
2004503951.tif 000079
2004503951.tif 000080
2004503951.tif 000081
2004503951.tif 000082
2004503951.tif 000083
2004503951.tif 000084
2004503951.tif 000085
2004503951.tif 000086
2004503951.tif 000087
2004503951.tif 000088
2004503951.tif 000089
2004503951.tif 000090
2004503951.tif 000091
2004503951.tif 000092
2004503951.tif 000093
2004503951.tif 000094
2004503951.tif 000095
2004503951.tif 000096
2004503951.tif 000097
2004503951.tif 000098
【国際調査報告】
2004503951.tif 000099
2004503951.tif 000100
2004503951.tif 000101