(57)【特許請求の範囲】
【請求項１】
画像シーケンスに対しモーション推定を行う装置であって、
（ａ）各画像に対し複数のレベルを有するＭ値ピラミッドを生成するＭ値ピラミッド生成手段であって、前記Ｍ値ピラミッドのそれぞれのレベルにおけるそれぞれの画素が、取り得るＭ個の値のうちの一つの値を有し、前記Ｍは整数であり、入力画像におけるそれぞれの画素が取り得る値Ｒとすると、２≦Ｍ＜Ｒの関係を満たし、前記各画像を複数のブロックに分割する、Ｍ値ピラミッド生成器と、
（ｂ）複数のタイリング・ブロック・サイズそれぞれに基づき、前記ブロック毎の複数のモーション・ベクトルを生成するモーション推定モジュールと、
（ｃ）前記複数のブロックの各々に対する少なくとも１つの前記モーション・ベクトルを前記Ｍ値ピラミッドのより低位のレベルに渡すモジュールと、を備え、
前記モーション推定モジュールは、
前記Ｍ値ピラミッドの最高レベルから前記Ｍ値ピラミッドのより低位のレベルへ階層的に、それぞれのタイリング・ブロック・サイズに基づき前記ブロック毎の複数のモーション・ベクトルを生成し、
前記複数のブロックの各々に対し３つのモーション・ベクトルを産み出すために、前記複数のブロックの各々についての３つのタイリング・ブロック・サイズに基づき前記ブロック毎の複数のモーション・ベクトルを生成する、ことを特徴とし、
前記渡すモジュールは、
前記Ｍ値ピラミッドの最低レベルの上位の全てのレベルに対し、前記Ｍ値ピラミッドのより高位のレベルから、前記複数のブロックの各々に対し前記３つのモーション・ベクトルを渡し、
最低レベルの直上のレベルから前記Ｍ値ピラミッドの最低レベルへ、前記複数のブロックの各々についての前記３つのモーション・ベクトルの１つのみを渡す、
ことを特徴とする、装置。
【発明の詳細な説明】
【０００１】
本書は、1997年12月31日に出願された、出願番号第09/002,258号の一部継続出願である。
【０００２】
【発明の属する技術分野】
本発明は一般に画像シーケンスの符号化システムに関わり、より詳細には、「多重スケール・ブロック・タイリングを用いて、ブロック・ベースのモーション推定に対するモーション・ベクトルを判断する際に計算量を削減し、かつモーション推定の確度を高める装置と随伴する方法に関わる。
【０００３】
【従来の技術】
ビデオ画像シーケンス等の画像シーケンスは、通常、画像フレームまたは画像映像を含む。移動物体を含むビデオの再生には、通常、秒当たり30フレームの画像フレーム速度が必要で、各フレームはおそらくはメガバイトを超す情報を含有している。結果として、このような画像シーケンスを伝送または格納するには、伝送帯域幅または格納容量のいずれかを大量に必要とする。必要となる伝送帯域幅または格納容量を減少させるために、フレーム・シーケンスは、シーケンス内の冗長情報が格納または伝送されないように圧縮される。テレビ、ビデオ会議や、CD-ROMのアーカイブは、効率的なビデオ・シーケンスの符号化からもたらされる利益の適用例である。
【０００４】
一般に、画像シーケンスを符号化するにあたっては、１シーンにおけるあるフレームから次のフレームへの物体のモーションに関する情報が、符号化処理において重要な役割を果たす。ほとんどの画像シーケンス内の連続フレーム間に高い冗長性が存在するために、モーション推定／補正として知られる手法を用いて、充分なデータ圧縮が達成できる。即ち、符号器は、符号化された領域に対してずれている領域に対する差分のみを符号化する。つまり、モーション推定は、１またはそれ以上の参照フレームに対する現行フレームの（例えば、ブロックまたはマクロブロック等の）領域についてのモーションの方向や大きさ（モーション・ベクトル）を判断する処理である。それに対して、モーション補正は、現行フレームの予測（予測画像）を生成するモーション・ベクトルを用いる処理である。現行フレームと予測フレーム間の差分は、結果として残余信号（エラー信号）を生じさせる。残余信号は現行フレーム自身より実質的に少ない情報を含有する。これにより、ビットの符号化における有意な保存が、残余信号と、残余信号に対応するモーション・ベクトルのみを符号化し伝送することにより実現される。
【０００５】
即ち、モーションを含むシーケンスにおいて、直前の先行フレームと、現行フレームと直前のフレーム間の差分を表示する残余信号を用いて現行フレームを再構築することができる。伝送器または符号器は、先行フレーム、残余信号、対応するモーション・ベクトルを受信器へ伝送する。受信器では、先行フレームを残余信号とモーション情報に組み合わせることにより、現行フレームが再構築される。結果として、２つの全体フレームではなく１つのみのフレームとその関連するモーション・ベクトルを伴う差分情報が伝送・受信される。
【０００６】
しかしながら、符号器の設計者は、モーション推定処理の精度を向上させて、残余信号を最小化する（即ち、符号化するビットを減少させる）よう試みるか、または、モーション推定処理においてより低い精度レベルを受認して、計算上のオーバーヘッドを最小化するよう試みるか、いずれかの方法に取り組まねばならない。つまり、フレーム・シーケンスからモーション・ベクトルを判断するには、フレーム間を集中して検索し、モーション情報を判断することが必要である。検索をより集中させることにより、より多くの計算周期を犠牲にしてより高精度のモーション・ベクトルの組が生成される。
【０００７】
例えば、多くのシステムが、いわゆるブロック・ベースのアプローチを用いてモーション情報を判断する。単一のブロック・ベースのアプローチにおいて、現行フレームは多くの画素ブロック（以下「現行ブロック」と称す）に分割される。これらの現行ブロック毎に、「最善に」現行ブロックと整合する画素ブロックに対する検索が、先行フレームの選択された検索領域内で行われる。この検索は通常、選択された現行ブロックを先行フレームの選択された検索領域内の似通った大きさの画素ブロックと反復比較することによって果たされる。一度ブロック整合が見出されると、現行フレーム内の現行ブロックの位置に対する従前フレームの検索領域における整合ブロックの位置がモーション・ベクトルを定義する。このアプローチ、即ち各現行ブロックの選択された検索領域全体との比較は、全体検索アプローチまたは網羅的検索アプローチとして知られている。網羅的検索アプローチによるモーション・ベクトルの判断は、特に検索領域がとりわけ大きい場合、計算が増大する。このように、これらのシステムはフレームを処理する際に比較的速度が遅くなりやすく、製造コストが高くなりやすい。
【０００８】
【発明が解決しようとする課題】
それ故に、ブロック・ベースのモーション推定についてのモーション・ベクトルを判断する際に計算量を削減する装置とそれに付随する方法が、本技術分野において求められている。
【０００９】
【課題を解決するための手段】
本発明の一実施形態は、「多重スケール・ブロック・タイリング」（Ｎスケール・タイリング）を採用して、ブロック・ベースのモーション推定についてモーション・ベクトルを判断する際に計算量を削減し、モーション推定方法の精度を高める装置および方法である。更に詳しくは、本発明は画像シーケンス内の各画像フレームをＭ値ピラミッドに分解する。次に、Ｎスケール・タイリングがＭ値ピラミッドとともに用いられ、階層的モーション推定がもたらされる。Ｎスケール・タイリングは、「Ｎ」個の異なる「タイリング・ブロック」サイズを用いて、フレームの現行ブロックに対してモーション推定を行う処理である。例えば、Ｎが３に設定された場合、３つのモーション・ベクトルが各フレーム内の各ブロックに対して生成される。即ち、ブロックは３つの異なるブロック・サイズまたはブロック・スケールにより「タイリング」される。従って、Ｎスケール・タイリングによる階層的モーション推定により、符号器は、考慮中のフレーム内のより大きな構造物のモーションとより小さな特徴のモーションを識別する。
【００１０】
本発明の教示は、添付図面と組み合わされた以下の詳細な説明を考察することにより、容易に理解できる。
【００１１】
【発明の実施の形態】
図１は、ブロック・ベースのモーション推定のためのモーション・ベクトルを判断するに際し計算量を減少させる、本発明の装置１００のブロック図を示す。本発明の好適な実施形態は以下に符号器を用いて説明されるが、本発明は、画像処理システム一般に採用可能であることは理解されるべきである。更に、本発明は、様々な符号化基準に準拠する符号器に採用され得る。これらの基準は、それに限定されるものではないが、Moving Picture Experts Group Standards（例えば、MPEG-1(11172-*)とMPEG-2(13818-*)）、H.261とH.263を含む。
【００１２】
装置１００は、符号器、またはより複雑なブロック・ベースのモーション補正符号化システムの一部である。装置１００は、モーション推定モジュール１４０と、モーション補正モジュール１５０と、任意の区分化モジュール１５１と、前処理モジュール１２０と、レート制御モジュール１３０と、変換モジュール１６０（例えばＤＣＴモジュール等）と、量子化モジュール１７０と、符号器１７０（例えば可変長符号化モジュール等）と、バッファ１９０と、逆量子化モジュール１７５と、逆変換モジュール１６５（例えば逆ＤＣＴモジュール等）と、減算器１１５と、加算器１５５とを備える。符号器１００は、複数のモジュールを備えるが、当業者には、様々なモジュールにより行われる機能は、図１に示すように分割されたモジュールに個別に分けられる必要はないことは理解されよう。 例えば、モーション補正モジュール１５０、逆量子化モジュール１７５および逆ＤＣＴモジュール１６５を備えるモジュールの組は、一般に「埋込み式復号器」として知られる。
【００１３】
図１は、パス１１０上の入力画像（画像シーケンス）を示し、入力画像は、ＭＰＥＧ基準に従いデジタル化され、輝度信号と２つの異なる色差信号（Ｙ、Ｃr、Ｃb）として表される。これらの信号は、各映像（フレーム）が複数のマクロブロックにより表されるように、更に複数の層に分割される。各マクロブロックは、４つの輝度ブロックと、１つのＣrブロックと、１つのＣbブロックを備え、ここでブロックは８×８のサンプル配列と定義される。映像をブロック単位に分割することにより、２つの連続する映像間の変化を識別する能力が向上し、かつ低振幅変換された係数の排除を介しての画像圧縮が改善される（以下に論考）。
【００１４】
以下の開示では、ＭＰＥＧ基準の用語が用いられるが、本発明においてマクロブロックまたはブロックという用語は、符号化の基礎に用いられる任意のサイズまたは形状の画素ブロックを説明するよう意図されている。広く定義すれば、「マクロブロック」は、単一の画素と同じだけ小さく、あるいはビデオ・フレーム全体ほどに大きくとらえられることもできる。
【００１５】
この好適な実施形態においては、デジタル化された入力画像信号は、前処理モジュール１２０において１つ以上の前処理工程を受ける。更に詳しくは、前処理モジュール１２０は、Ｍ値ピラミッド生成器１２２とブロック分類器１２４とを備える。Ｍ値ピラミッド生成器１２２は、平均フィルタ１２３ａと量子化器１２３ｂを採用し、平均フィルタ１２３ａと量子化器１２３ｂは、各フレームにフィルタをかけ、各フレームを複数の異なる解像度、即ち解像度のＭ値ピラミッドに量子化する。ここで各フレームの異なる解像度は、以下に説明されるように、階層的な方法で互いに相関づけられる。次に、解像度のピラミッドを用いて、ブロック分類器１２４は、領域（ブロック）を高アクティビティまたは低アクティビティの領域に素早く分類することができる。前処理モジュール１２０により行われる機能については、以下で詳細に説明する。
【００１６】
パス１１０上の入力画像は、モーション・ベクトルの推定のために、モーション推定モジュール１４０で受け取られる。モーション・ベクトルは、モーション補正により用いられる二次元ベクトルであり、モーション補正は、現行画像のブロックの座標位置から参照フレームの座標へオフセットさせる。現行フレーム内の変化のみが符号化され伝送されるので、チャンネルに伝送される情報量が減少されることにより、モーション・ベクトルの使用は画像圧縮を大いに向上させる。好適な実施形態において、モーション推定モジュール１４０は、前処理モジュール１２０からの情報も受け取り、これによりモーション推定処理の性能が高められる。
【００１７】
モーション推定モジュール１４０からのモーション・ベクトルは、サンプル値の予測効率を向上させるモーション補正モジュール１５０に受け取られる。モーション補正は、前もって復号されたサンプル値を含有する過去および／または未来の参照フレームへのオフセットを提供するためにモーション・ベクトルを用いた予測を含み、かつモーション補正は予測エラーを形成するために用いられる。つまり、モーション補正モジュール１５０は、前もって復号されたフレームとモーション・ベクトルを用いて、パス１５２上の現行フレームの推定（モーション補正された予測、または予測された画像）を構成する。この画像補正予測は、減算器１１５を介して、現行マクロブロックにおけるパス１１０上の入力画像から減算され、パス１５３上のエラー信号（ｅ）または予測残余を形成する。
【００１８】
予測残余信号は、例えばＤＣＴモジュール１６０等の変換モジュールに渡される。次にＤＣＴモジュールは、予測残余信号の各ブロックに対し、順方向離散的コサイン変換処理を加え、８×８ブロックのＤＣＴ係数の組を産み出す。離散的コサイン変換は逆が可能な離散的直交変換であり、ここでＤＣＴ係数は、コサインを基礎とする1組の関数の振幅を表す。
【００１９】
結果として生じる８×８ブロックのＤＣＴ係数は、量子化（Ｑ）モジュール１７０に受け取られ、ここでＤＣＴ係数が量子化される。量子化処理は、適切に丸められて整数値を形成する量子化値または量子化尺度の組により該ＤＣＴ係数を分割することによってＤＣＴ係数を表すときの、確度を減少させる。量子化値は、基礎関数の可視性に基づく（可視的な重み付き量子化として知られる）基準を用いて、各ＤＣＴ係数毎に個別に設定できる。この値を用いてＤＣＴ係数を量子化することにより、多くのＤＣＴ係数は０に変換され、これにより画像圧縮効率が改善される。
【００２０】
次に、結果として生じる８×８ブロックの量子化されたＤＣＴ係数は、信号接続１７１を介して、例えば可変長符号化モジュール等の符号器に受け取られる。ここで量子化係数の二次元ブロックは「ジグザグ」順に走査され、量子化ＤＣＴ係数の一次元ストリングに変換される。次に、可変長符号化（ＶＬＣ）モジュール１８０は、量子化ＤＣＴ係数のストリングと、マクロブロックの種類やモーション・ベクトル等のマクロブロックについての全ての副情報を符号化する。これにより、ＶＬＣモジュール１８０は、入力画像を有効データ・ストリームに変換する最終工程を行う。
【００２１】
データ・ストリームは、例えば「先入れ先出し」（ＦＩＦＯ）バッファ１９０等のバッファ内に受け取られる。異なる映像種類と可変長符号化を用いる結果として、ビット・レート全体が可変となる。つまり、各フレームを符号化するために用いられるビットの数は異なってよい。これにより、固定レート・チャンネルを含む適用にＦＩＦＯバッファが用いられ、ビット・レートをならすために符号器の出力がチャンネルに整合される。従って、ＦＩＦＯバッファ１９０からのパス１９５上の出力信号は入力画像１１０の圧縮表示であり、出力信号は記憶媒体または電気通信チャンネルに送られる。
【００２２】
レート制御モジュール１３０は、ＦＩＦＯバッファ１９０に入るデータ・ストリームのビット・レートをモニタし調整するよう機能し、データ・ストリームの伝送後に、復号器側（図示しない受信器またはターゲット記憶装置内）のオーバフローやアンダフローを防止する。固定レート・チャンネルは、復号器内の入力バッファ（図示しない）に一定レートでビットを搬送すると想定される。映像レートにより決定される規則的間隔で、復号器は即座に入力バッファから次の映像に対する全ビットを除去する。入力バッファ内のビットが少なすぎる、即ち、次の映像に対する全ビットが受け取られなかった場合、入力バッファはアンダフローし、エラーを生じさせる。同様に、入力バッファ内のビットが多すぎる、即ち、映像開始間で入力バッファの容量を超える場合、入力バッファはオーバフローし、オーバフロー・エラーを生じさせる。従って、レート制御モジュール１３０の仕事は、バッファ１９０の状況をモニタし、符号器により生成されるビット数を制御することであり、これにより、オーバフローやアンダフローの状態発生を防止する。レート制御方法は、量子化尺度を調整することにより符号化ビットの数を制御できる。
【００２３】
更には、量子化モジュール１７０から結果として生じる８×８ブロックの量子化ＤＣＴ係数は、信号接続１７２を介して、逆量子化モジュール１７５と逆ＤＣＴモジュール１６５に受け取られる。即ちこの段階では、次の符号化のために参照フレームとしてＩフレームとＰフレームが用いられるように、符号器は、データの復号により画像シーケンスのＩフレームとＰフレームを再生成する。
【００２４】
図２に、ブロック・ベースのモーション推定のためのモーション・ベクトルの判断に際して、計算量を減少させる方法２００のフローチャートを示す。つまり、方法２００は、整合が生じそうな最初の検索領域を素早く定義することにより、ブロック・ベースのモーション推定方法を改良する。
【００２５】
更に詳しくは、方法２００は、ステップ２０５から始まり、ステップ２１０に進む。ステップ２１０では、Ｍ値ピラミッド（またはＭ値平均ピラミッド）が、画像シーケンスの各画像フレーム毎に生成される。Ｍ値ピラミッドの生成方法について、図３、４、１０を用いて、以下詳細に説明する。
【００２６】
更に詳しくは、図１０に、画像に対しＭ値ピラミッドを生成する方法１０００のフローチャートを示す。この方法は、ステップ１００５から始まり、ステップ１０１０に進む。ステップ１０１０では、元の画像が画像の平均ピラミッドに分解される。
【００２７】
図３は、一般的な平均ピラミッド３００のブロック図を示す。ここで、平均ピラミッドは、複数のレベル３１０，３２０，３３０よりなる。最下のレベル３１０は、「ｘ」で表される複数の画素３１１を有する画像シーケンスからの元画像フレームである。通常、これらの画素はレンジを有する画素値により表されるが、この時該レンジは、画素値を表示するために割り当てられるビット数により制限されている。例えば、８ビットが割り当てられた場合、画素値は２５６の可能な値から１値を取り得る。
【００２８】
１つの平均ピラミッドにおいて、次に高位のレベルが、両方向への２の因子による低域フィルタリングとダウンサンプリングにより生成され、これにより、下位レベルの４つの画素値（子）から高位レベルとして単一画素値（親）を生成する。これは図３に示されるが、ここで４つの画素３１２ａ〜ｄの各組は、レベル３２０において、単一画素値３２１を生成するために用いられる。今度は、４つの画素値３２２ａの組がレベル３３０で単一画素値３３１を生成するために用いられ、以下同様である。ただし本発明は、３つのレベルを有する平均ピラミッドに限定されるものでないことは理解されるべきである。レベルの数は、一般に、画像のサイズと、次に低い解像度画像を生成するために選択されるダウンサンプリング因子により制限される。従って、平均ピラミッドのレベルの数は、特定のアプリケーションに対し選択され得る。
【００２９】
平均ピラミッドにおいて、親の画素値は、子の４つの画素値の平均をとることにより引き出され、故に平均ピラミッドという用語が用いられている。しかしながら、他の測度を用いて、他の種類のピラミッドを生成することができる。例えば測度は、４つの子の画素値の中央値に基づくことができる。あるいは、子の画素の周囲のより大きい領域を加重平均に用いて、汎用低域ピラミッドを得ることができる。
【００３０】
図１０に戻ると、次に方法１０００は、ステップ１０２０において、Ｍ値ピラミッドを前記平均ピラミッドから生成する。つまり、「Ｍ値ピラミッド」においては、各量子化された画素値が「Ｍ」個の可能な画素値のみを取り得るように、画素値が量子化される。例えば、Ｍが２であるならば、各量子化画素値は１または０の値のみを取り得る。即ち、結果として「二値ピラミッド」となる。
【００３１】
図４は、三値ピラミッドを生成する量子化処理のブロック図を示し、ここでＭは３である。更に詳しくは、８ビット画素値２５５（４１０ａ）は、子の画素と親の画素間の差分に基づき２ビット画素値１０（４２０ａ）に量子化される。つまり、親４３０ａと子４１０ａ〜ｄの各々との間で差分が計算され、４つの差分の各々が次に３つの可能値１０、００、０１に量子化される。従って、画素値１２８（４１０ｂと４１０ｃ）は画素値００（４２０ｂと４２０ｃ）に量子化され、画素値０（４１０ｄ）は画素値０１（４２０ｄ）に量子化される。これらの表示レベルは、モーション推定に用いるビット単位の排他的論理和ベースの費用関数に適切である。これらのレベルは、特徴検知およびブロック分類にも有用である。Ｍ値ピラミッドは画素値の確度を減少させ、これにより、画像内の「特徴」の迅速な検知が可能である。特徴は、例えば物体の端部等の、高アクティビティまたは高強度の領域と定義される。なお、レベル４１０および４３０は平均ピラミッドのレベルであり、一方でレベル４２０は、Ｍ値ピラミッドのレベルである（Ｍ＝３の時）。これらのピラミッドは両方とも、図４に示すように付加レベルを有することができるが、Ｍ値ピラミッドは、平均ピラミッドよりレベルが１低い。つまり、単一のＭ値ピラミッド・レベルを生成するには、２つの平均ピラミッド・レベル４１０及び４３０が必要とされる。
【００３２】
更には、画素値を表すために用いられるビット数の著しい減少は、モーション推定処理における計算上のオーバーヘッドの減少につながる。例えば、画素値が引き受けることのできる可能な値が少ないので、モーション推定処理において行われるブロック整合操作が促進され得て、これにより、ブロック整合処理全体が単純化される。
【００３３】
Ｍは任意の値でよいが、例えば二値ピラミッド等の「低い順位の」Ｍ値ピラミッドの分解は、例えば三値ピラミッド等の「高い順位の」Ｍ値ピラミッドよりノイズに対してより敏感であることが見出されている。つまり、二値ピラミッドにおける量子化された画素値は２つの可能な値から１つのみを取り得るので、ノイズによりエラーを生じる可能性があり、画素値は、０の代わりに値１を有するように、またはその逆を有するように、間違えて解釈されかねない。しかしながら、「高い順位の」Ｍ値ピラミッドは、より多くの計算上のオーバーヘッドを必要とする。従って、Ｍが２より大きい場合に、Ｍ値ピラミッド分解が最善に採用されることが見出されているが、特定のＭ値ピラミッド分解の選択は、しばしば特定のアプリケーションの要求により指示される。一度Ｍ値ピラミッドが生成されると、方法１０００はステップ１０３０において終了し、図２のステップ２２０に戻る。
【００３４】
ステップ２１０における重要な様態は、画像シーケンスにおける各入力画像に対し、Ｍ値ピラミッドを生成することであることは理解されるべきである。このように、好適な実施形態はＭ値平均ピラミッドを生成するが、例えばＭ値中央値ピラミッド、Ｍ値低域ピラミッド等の他の種類のＭ値ピラミッドも本発明に採用できる。
【００３５】
あるいは、Ｍ値平均ピラミッド分解の発明の概念は、式の形態で表現され得る。（ｉ，ｊ）は画像フレーム上での画素の位置を表し、Ｉ（ｉ，ｊ）は位置（ｉ，ｊ）での強度を表すものとする。更にｌは、０≦ｌ≦Ｌで、ピラミッド内のレベルを示すものとし、ここでＬは、該ピラミッドにおける最高のレベルである。すると、平均ピラミッドＸl（ｉ，ｊ）は、１≦ｌ≦Ｌのとき以下のように構成される。
【数２】
0004205858.tif 000002
ここで、Ｘ0（ｉ，ｊ）＝Ｉ（ｉ，ｊ）である。
【００３６】
図２に戻ると、以下ステップ２２０において、これらの平均ピラミッドからブロック内の特徴等の情報が抽出され得る。一実施形態において、ブロックはマクロブロックの８×８サブブロックであるが、本発明は、このブロック・サイズに限定されるものでないことは理解されるべきである。特に、端部のような特徴は、ブロック内の強度の変化から抽出され得る。この変化は、レベルｌ（０≦ｌ≦Ｌ−１）における平均値とレベルｌ＋１における平均値との差分を計算することにより表される。しかしながら、強固な特徴を得るために、かつ迅速なモーション推定を容易にするために、これらの差分は量子化され、Ｍ値ピラミッドを産み出す。Ｍ値ピラミッドの各レベルは、画像全体にわたるパターンを示し、該パターンは、端部やゼロ交差のような画像の特徴を識別するか、またはモーション推定を実行するために用いることができる。
【００３７】
例えば、画像の二値ピラミッドＢl（ｉ，ｊ）は、以下のように構築できる。
【数３】
0004205858.tif 000003
ここでｌは、二値ピラミッド内のレベルを示す。式１ａは、二値ピラミッドの２つの値（「０」と「１」）を定義する特定の条件（量子化工程）を示すが、特定のアプリケーションに従って他の条件または量子化工程を用いて、２つの値（「０」と「１」）を定義することができる。
【００３８】
あるいは、画像の三値ピラミッドＹl（ｉ，ｊ）を構築できる。例えば、Ｍ値ピラミッド（Ｍ＝３）におけるパターン値をＹl（ｉ，ｊ）で示すと、以下の式が表される
【数４】
0004205858.tif 000004
【００３９】
Quant[.]の引数をλで示す。例えば、閾値Ｔを有する三値ピラミッドの場合を考え、Ｙl（ｉ，ｊ）を以下のように定義する。
【数５】
0004205858.tif 000005
【００４０】
この定義は、量子化閾値Ｔ（例えば、好適実施形態において、Ｔは５と選択される）が特定のアプリケーションに対し適切に選ばれる場合に、対ノイズ強度において利点を有する。つまり、「不感帯」、例えば|λ|＜Ｔを定義することができ、ノイズに起因する画素値内のわずかな変動を効果的に除去することができる。これにより、ゼロ近辺の不感帯を有するいずれのＭ値ピラミッド（Ｍ＞２）においても、ノイズ感度の問題が最小になる。
【００４１】
比較的平板な領域（低アクティビティの領域）において、Ｙl（ｉ，ｊ）は、多数のゼロ（０）を含有し、一方、端部を含有する領域では、Ｙl（ｉ，ｊ）は、
多数の（１）を含有する。一度入力画像がＭ値ピラミッドに分解されると、入力画像のブロックが、Ｍ値ピラミッドＹl（ｉ，ｊ）を用いる特徴抽出のために分類され得る。つまり、Ｍ値ピラミッドを用いて、計算上の高オーバーヘッドを招くことなく、入力画像の特徴を迅速に検知することができる。検知された特徴を用いて、以下に論考するようなモーション推定処理や、例えば区分モジュール１５１を用いることによる、例えば画像内の領域（物体など）の区分化等の、他の画像処理工程を一層良くすることができる。区分化は、重要な画像処理工程であり、ここで画像の重要な領域が識別され、特別な処置がなされる。例えば、ビデオ会議の利用中の人の顔は、符号化ビットの割当をより多く受ける等の特別な画像処理を要求する。更には、区分化を用いて大きな対象を識別することができ、ここで広範なモーション推定が前記の大きな対象上に行い得る。
【００４２】
これまでの論考では、例として三値ピラミッドが用いられ、量子化閾値またはレベルを特徴識別および分類に割り振ることのできる、１つの可能な方法が示されていることが理解されるべきである。一般に、Ｍ≧２のＭ値ピラミッドを、特定のアプリケーションの要求および／または画像シーケンスの内容に依存する、量子化閾値の所定の割振とともに用いることができる。
【００４３】
図２に戻ると、Ｍ値ピラミッドが生成された後に、方法２００はステップ２２０に進み、ここでフレームのブロックは、Ｍ値ピラミッドを考慮して、低アクティビティまたは高アクティビティについて分類される。好適実施形態において「分類ブロック・サイズ」は８×８ブロックであり、該８×８ブロックは、１２８ビットにより表される６４Ｍ値の画素値を有する。２５の「アクティビティ閾値」が設定されるが、ここで、２５以上の画素値がゼロでなければ、８×８ブロックは、高アクティビティ・ブロックとして分類される。そうでない場合８×８ブロックは、低アクティビティ・ブロックとして分類される。更に高位のブロック分類、例えばマクロブロックを高アクティビティまたは低アクティビティのマクロブロックのいずれかに分類することもできる。好適実施形態において、高アクティビティとして分類される少なくとも１つのサブブロックを備えるマクロブロックによっても、マクロブロックは高アクティビティとして分類される。「分類ブロック・サイズ」および「アクティビティ閾値」は、特定のアプリケーションに従い調整され得て、好適実施形態において選択された上記の値に限定されるものではないことは理解されるべきである。
【００４４】
図２に戻ると、ブロック分類の後に、方法２００はステップ２３０に進み、ここでブロック分類を用いて、モーション推定処理が一層良く行われる。一般に、著しい画像の特徴を有する領域におけるモーション推定は、絞りの問題に起因する、変化に乏しい比較的「平板な領域」（例えば、画像内容が隣接ブロックに非常に近似している均一な領域）におけるモーション推定より信頼性が高い。それ故に、一般にモーション推定の信頼性を高めるために上記の分類方法が用いられる。しかしながら、モーション推定の適用において、Ｍ値の使用の前に、ブロックをその内容に関し前もって分類する必要はないことは理解されるべきである。つまり、本発明のＭ値ピラミッドを、（図２の破線で示すように）直接用いることにより、各種の、または異なるアーキテクチャのモーション推定方法の効率を高めることができる。
【００４５】
より詳しくは、モーション推定は一般に、ブロックごとにラスタ走査順に行われる。計算上のオーバーヘッドまたはコストは一般に、モーション推定処理の間、全ブロック上にわたり平均して分配される。本発明においては、まず「端部」ブロック（高アクティビティ・ブロック）のモーション推定が、Ｙl（ｉ、ｊ）および／またはＸl（ｉ，ｊ）に依存する費用関数を用いて行われる。このアプローチにより画像の特徴が強調され、センサ・ノイズ、量子化ノイズ、および照度変化があっても、強固で信頼性のあるモーション推定が提供される。費用関数の一例は、ピラミッドのＭ値レベル上でのビット単位の排他的論理和演算を含み得て、あるアーキテクチャ上での迅速な方法として実行され得る。費用関数を用いて、「最善の整合」が判断される。時間ｔ（現在のフレーム）におけるＭ値化されたブロック、Ｙl（ｉ，ｊ，ｔ）と、時間ｔ−１（前のフレーム）における他のＭ値化されたブロック、Ｙl（ｍ，ｎ，ｔ−１）を考察しよう。このとき費用関数は、以下のように表される。
【数６】
0004205858.tif 000006
ここで
0004205858.tif 000007
はビット単位の排他的論理和演算を表す。この費用関数は、元の８ビット画素強度値に用いられる標準的な「絶対差分」の費用関数に比して、実質的な計算の節減を産み出す。この手順は、Ｍ値ピラミッドをわたり階層的に行われる。
【００４６】
換言すれば、モーション推定方法は高アクティビティ・ブロックで始められる。図５は、複数のブロック５１０に分割かつ分類された入力フレーム５００を示す。好適実施形態において、２つのブロック５１０ａが高アクティビティ・ブロックとして分類される。このようにして、まずモーション推定がこれら２つのブロックにおいて行われる。実際に、これらの高アクティビティ・ブロック（高信頼性の「端部」ブロック）は、非常に高精度のモーション・ベクトルを提供する可能性が最も高いので、計算上のコストはこれら２つのブロックに対して上昇し得る。これにより、これら２つのブロックにおいて、画像フレーム５００における他のブロックにおいてよりも、より集中的なモーション推定が行われる。例えば、高アクティビティのブロックを分離してより高精度のモーション・ベクトルを得たり、「半画素」モーション推定をこれら２つのブロックにおいて行ったり、より精細な検索の方策を採用することができる。
【００４７】
次に、モーション推定が高アクティビティ・ブロックに対し完了した後に、続いてモーション推定は、画像における低アクティビティ・ブロック（「低信頼性」ブロック）に伝播する。しかしながら、この伝播は、分類から得られる領域または対象の区分に依存して知的に行われる。この伝播は、隣接するブロックのモーションに対しての初期化として端部ブロックのモーションを用い、かつこの初期化を洗練するため、比較的小さい検索範囲を用いることにより行われる。つまり、モーション推定処理は（例えばらせん順に）ブロック５１０ｂに伝播し、ここで、初期検索領域は高アクティビティ・ブロックのモーション・ベクトルから導かれる。次に、この伝播方策は続いて、例えばブロック５１０ｃ等の「平板な」ブロックに拡張される。「平板な」ブロックは「端部」ブロックに隣接しては置かれない。かつこの伝播方策は、精緻に検索される領域が比較的小さいので、迅速な計算が可能であるという利点を有する。更には、モーション推定は符号化をより円滑かつ容易に行い、このことはモーション情報がビットストリームの有意な部分を形成する「非常に低いビット・レート」（ＶＬＢＲ）の適用において大きな利点となる。更には、これらのより円滑なモーション推定は、一時的挿入の適用においてより良好に行われると期待できる。
【００４８】
最後に、半画素の洗練を用いモーション推定の確度を向上する場合、この分類方法は計算の節減ももたらす。半画素の洗練は「端部」ブロック上のみに行われ、比較的平板な画像領域上には行われない。
【００４９】
本発明の他の実施形態は、モーション推定を達成するためにＭ値ピラミッドによる「Ｎスケール・タイリング」を用いることを含む。更に詳しくは、この実施形態においては、４レベルの二値ピラミッドが以下の式により構築される。
【数７】
0004205858.tif 000008
ここで、Ｘl（ｉ，ｊ）はｌ番目のレベルの位置（ｉ，ｊ）におけるグレー・レベルを表し、Ｘo（ｉ，ｊ）は元の画像を示す。
【００５０】
次に、４レベルの二値ピラミッド画像は以下の式により構築される。
【数８】
0004205858.tif 000009
ここで、０≦ｌ≦２であり、
【数９】
0004205858.tif 000010
なお、本発明のＮスケール・タイリングの実施形態は、式（７）により表されるピラミッドの最高レベルを有する、修正された二値ピラミッドを採用する。しかしながら、本発明のＮスケール・タイリングの実施形態は、「拡張可能な階層的モーション推定を行う装置及び方法」と題され、1998年6月29日にここに同時に出願された添付特許出願（弁理士証明書SAR 12455、連番09/106,706、ここに参照として包含）に開示されるように、上記(例えば式１、１ａ、２等による)のようなＭ値ピラミッドと組み合わせて、または他の修正されたＭ値ピラミッドと組み合わせて実行され得る。
【００５１】
図１１は、Ｎスケール・タイリングによりＭ値ピラミッド上においてモーション推定を行う方法１１００のフローチャートを示す。更に詳しくは、方法１１００はステップ１１０５から始まりステップ１１１０に進む。ステップ１１１０では、（説明のためＭ＝２とする）二値ピラミッドの最高レベルから始まるＮスケール・タイリングが該ピラミッド上で行われる。一般に、モーション推定は、現行ブロック（例えば１６×１６画素のマクロブロック等）のモーション又は転置を推定するために行われる。ここで、フレーム全体が複数の重なり合わない現行ブロックに分割される。しかしながら、Ｎスケール・タイリングは、図７に示すように、「Ｎ」個の異なる「タイリング・ブロック」サイズを用いて、フレームの現行ブロックに対してモーション推定を行う処理である。
【００５２】
図７は、３スケール・タイリングが行われる画素ブロック７１０のブロック図を示す。更に詳しくは、ブロック７１０は、フレーム内の複数の８×８ブロックの１つである。好適実施形態において、モーション推定は、３つ（Ｎ＝３）の異なるブロック・サイズ、例えば８×８ブロック・サイズ７１０、８×４ブロック・サイズ７２０、４×８ブロック・サイズ７３０を用いて行われる。これにより、３つのモーション・ベクトルが各フレーム内の８×８ブロック毎に生成される。即ち、ブロックは、３つの異なるブロック・サイズまたはブロック・スケールにより「タイリング」される。本発明の１つの好適実施形態において、３スケール・タイリング（Ｎ＝３）が、最高レベル（Ｍ値ピラミッドの最低解像度）において行われ、これによりブロック毎に３つのモーション・ベクトルを生成する。
【００５３】
ステップ１１２０では、方法１１００は、次のレベルがＭ値ピラミッドの最低レベルであるかを問い合わせる。上記問い合わせに対し否定の回答がなされた場合、方法１１００はステップ１１３０に進む。ステップ１１３０では、３つのモーション・ベクトルがより低位のレベルに渡される。即ち、スケール毎の１つのモーション・ベクトルがＭ値ピラミッドのより低位のレベルに渡される。今度は、方法１１００は、次に低位のレベルのためにステップ１１１０に戻る。ステップ１１１０では、より高位のレベルから受け取られたモーション・ベクトルに基づいて洗練が行われ、より低位のレベルに渡される他の３つのモーション・ベクトルが産み出される。ここでモーション・ベクトルは各レベル毎等で洗練される。
【００５４】
しかしながら、ステップ１１２０での問い合わせに対し肯定の回答がなされた場合、方法１１００はステップ１１４０に進む。ステップ１１４０では、１つのモーション・ベクトルのみがレベル１から選択され、レベル０（Ｍ値ピラミッドの最低レベル（最高解像度））に渡される。レベル０に渡すべきレベル１からのモーション・ベクトルの選択は、ブロックに対するモーション補正予測誤差を最小化するモーション・ベクトルに基づく。なお、完全な解像度での目的のブロック・サイズは１６×１６である。次に、ステップ１１５０で、ステップ１１４０から渡されるモーション・ベクトルを用いて１６×１６ブロック毎に最終モーション・ベクトルが判断され、ステップ１１６０で方法１１００は終了する。
【００５５】
Ｍ値ピラミッドと組み合わせてＮスケール・タイリングを実施する特徴には、ブール域でモーション推定を行う能力が含まれる（Ｍ＝２の場合）。この特徴はフレーム・バッファとモーション推定器１４０間のデータ転送時間を短縮する。更には、３スケール・タイリングによりモーション推定を実施することにより、符号器は、考慮中のフレーム内のより大きな構造のモーションとより小さな特徴のモーションを識別する。例えば、モーション・ベクトルが、８×８ブロックの代わりに例えば４×８ブロックまたは８×４ブロック等の小さなタイリング・ブロックに関連する現行ブロックに対し選択された場合、現行ブロック内の「特徴」またはサブブロックに移動があると推量できる。これにより、フレームの現行ブロックに対し最後に選択されるモーション・ベクトルに対する、異なるタイリング・スケールの寄与を測るヒストグラムを設定できる。ヒストグラムを分析して、より大きい構造や構造内のより小さい特徴等のモーションを推定することができる。
【００５６】
この好適実施形態は３つのスケールを採用しているが、異なるブロック・サイズを有する「Ｎ」個のスケールを用いることができる。更には、本発明は、ブロック毎に任意の数のモーション・ベクトルがレベルからレベルへ渡され得るように修正可能である。
【００５７】
３スケール・タイリングによる上記の階層的モーション推定は、式の形式で表され得る。つまり、Ｆmは、画像フレーム・シーケンス中のｍ番目の画像フレームを示すものとし、ここで各フレームは、サイズ「ｓ」の重なり合わないブロックに区分される。結果として生じる区分またはタイリングは、解像度ｌにおいてＦml.sで表される。解像度ｌにおける画像フレームｍの座標ｘ＝［ｘ１，ｘ２］Tにおける画素の強度値は、Ｆml（ｘ）により示される。あるｓ＝［ｓ１，ｓ２］Tに対し、画像位置ｘに左上隅を持つ画素ブロックは、
【数１０】
0004205858.tif 000011
で表される。フレームｍからのブロックＢml（ｘ，ｓ）からの画素とフレームｍ−１からのブロックＢlm-1（ｘ，ｓ）の対応する画素の間の絶対差分（ＳＡＤ）は、以下の式により表される。
【数１１】
0004205858.tif 000012
フレームｍからのブロックＢml（ｘ，ｓ）からの画素とフレームｍ−１からのブロックＢlm-1（ｘ，ｓ）の対応する画素間の排他的論理和ブール演算
0004205858.tif 000013
の合計は、以下の式により示される。
【数１２】
0004205858.tif 000014
【数１３】
0004205858.tif 000015
【００５８】
Ｆo,sを、濃度ｋによる完全な解像度画像上に定義されるタイリングとする。より低解像度の画像に対して、３スケール・タイリングを｛Ｆl,s｝3l=1、｛Ｆl,s1｝3l=1、｛Ｆl,s2｝3l=1と考える。なお、ｓ１＝［ｓ1／２，ｓ2］Tおよびｓ２＝［ｓ1，ｓ2／２］Tであるが、他のブロック・サイズを用いることができる。
【００５９】
まず、４レベルのピラミッド（０−３レベル）のレベル３において、モーション・ベクトル場ｖ3s，ｖ3s1，ｖ3s2を以下の式のように定義する。
【数１４】
0004205858.tif 000016
【数１５】
0004205858.tif 000017
【数１６】
0004205858.tif 000018
ここで、Ω3＝｛ｖ：−ｄ3≦ｖ≦ｄ3｝
ここで、−ｄ3とｄ3は、それぞれ−Ｍ／８とＭ／８であり、Ｍは検索ウィンドウの画素数である。次に、レベル２とレベル１に対し、より低解像度ｌ＋１からより高解像度ｌ（ｌ＝２かつｌ＝１）へ、モーション・ベクトル場が以下の式に従い伝播される。
【数１７】
0004205858.tif 000019
【数１８】
0004205858.tif 000020
【数１９】
0004205858.tif 000021
つまり、より低解像度からのモーション・ベクトル場は、モーション・ベクトル場上で洗練を行う前に２倍にされる。
【００６０】
次に、解像度ｌにおけるモーション・ベクトル場を以下の式により洗練する。
【数２０】
0004205858.tif 000022
【数２１】
0004205858.tif 000023
【数２２】
0004205858.tif 000024
ここで、Ωl＝｛ｖ：−ｄl≦ｖ≦ｄl｝、−ｄlとｄlはそれぞれ−３と３である。
【００６１】
最後にレベル０に対して、
【数２３】
0004205858.tif 000025
【数２４】
0004205858.tif 000026
【数２５】
0004205858.tif 000027
【数２６】
0004205858.tif 000028
ここで、Ω0＝｛ｖ：−ｄ0≦ｖ≦ｄ0｝、−ｄ0とｄ0はそれぞれ−３と３である。
【００６２】
３スケール・タイリングによる二値ピラミッドを用いる本発明の階層的モーション推定により、計算コストの低い効率的なモーション推定方法が提供される。即ち、ビデオ画像の幅と高さがそれぞれＷとＨである場合、検索ウィンドウは±Ｍ個の画素を有する。従来の全検索ブロック整合方法には、単一画素の整合に対して１回の減算、１回の集積、１回の完全な演算が必要であった。これにより、計算量（フレーム当たりの演算）は以下の式により概算される。
【数２７】
0004205858.tif 000029
【００６３】
本発明に対しても、同一の全検索方法を用いることができる。レベル０におけるブロック・サイズは１６×１６である。同一の８×８ブロック・サイズをレベル１、レベル２、レベル３に用いる。レベル０、レベル１、レベル２における有効検索範囲は±３に設定される。レベル３における有効検索範囲は±Ｍ／８に設定される。
【００６４】
レベル３において、計算量は以下の式により概算される。
【数２８】
0004205858.tif 000030
【００６５】
レベル２とレベル１において、各８×８ブロックは４つの１６ビット・ベクトルにより表され得る。１６ビットの排他的論理和ブール演算子を、１つの１６ビット排他的論理和配列、６５，５３６エントリーを有するデュアル・ポートのルック・アップ・テーブル（ＬＵＴ）を用いて実施できる。次に、８×８ブロックは、基礎整合について４／６４の集積を必要とする。同様に、８×４ブロックは、基礎整合について２／３２の集積を必要とする。続いて、レベル２とレベル１における計算量は、以下の式により概算される。
【数２９】
0004205858.tif 000031
【００６６】
レベル０において、１６×１６ブロックは基礎整合について１６／２５６の集積を必要とする。計算量は、以下の式により概算される。
【数３０】
0004205858.tif 000032
【００６７】
それ故、本発明の計算量ＣHMEBPは、以下の式により概算され得る。
【数３１】
0004205858.tif 000033
【００６８】
最後にＣHMEBPとＣFULLの比は、以下の式により表される。
【数３２】
0004205858.tif 000034
【００６９】
このように、式（２９）により、従来の全検索方法と比して少ない本発明の計算量が示される。
【００７０】
なお、本発明は、Ｍ値ピラミッドのレベル全体を通じて一貫してＮスケール・タイリングを採用しているが、本発明はそれに限定されるものではない。実際、Ｎスケール・タイリングは、Ｍ値ピラミッドの各レベル内において調整され得る。つまり、各レベル内の異なるブロックの組に異なるＮスケール・タイリングを用いることができる。例えば、あるブロックが特に重要な場合、８×８ブロックに対し、５スケール・タイリングを用いることができる（例えば、１つの８×８タイリング・ブロック、２つの４×８タイリング・ブロックと８×４タイリング・ブロック）。対照的に、Ｍ値ピラミッドの同一レベルにおいてブロックが特に重要でない場合、８×８ブロックについて１スケール・タイリングを用い（例えば、１つの８×８タイリング・ブロック）、計算周期の数を削減することができる。このように、上記のブロック分類（高アクティビティと低アクティビティ）方法を用いて、Ｍ値ピラミッドの各レベルにおける各ブロック毎に用いるＮスケーリングのレベルを指示することができる。実際、他の任意のブロック分類方法を、本発明に関連させて用いることができる。
【００７１】
あるいは、可変タイリング・ブロック・サイズによる上記の階層的モーション・ベクトル推定方法を、図３に示すような平均ピラミッドにより実施できる。つまり、モーション推定は、Ｍ値ピラミッドの代わりに平均ピラミッド上で直接行われる。
【００７２】
即ち、平均ピラミッドの最上レベルにおいて、考慮中の現行フレームについてより大きい特徴のモーションとより小さな特徴のモーション間を識別する２つの異なるブロック・サイズによりモーション推定は行われる。更に詳しくは、１つの４レベル平均ピラミッドが上記式（５）に従い構築され、ここでＸl（ｉ，ｊ）はｌ番目のレベルの位置（ｉ，ｊ）におけるグレー・レベルを表し、Ｘ0（ｉ，ｊ）は元の画像を示す。
【００７３】
次に、階層的モーション推定が、平均ピラミッドの粗いレベルからより細かいレベルへ行われる。完全な解像度における１６×１６の目的ブロックを仮定すると、階層的モーション推定はレベル３から始まり、レベル３において、例えば、４×４ブロックと８×８ブロック（さらにタイリング・ブロックおよび／またはタイリング・ブロック・サイズを追加して用いることができる）等の２つのブロック・サイズに対し検索が行われる。
【００７４】
次に、レベル２とレベル１において、各候補モーション・ベクトルが２つの異なるスケールにおいて続いて洗練され、各スケールからの最善のモーション・ベクトルが更なる洗練のために次のレベルに伝播される。最後に、レベル０において、モーション補正予測誤差に基づき各ブロック毎に洗練するために、１つのモーション・ベクトルが選択される。平均ピラミッドと可変タイリング・ブロック・サイズによるこの階層的モーション推定の計算費用は、従来の階層的モーション推定方法よりも小さいが、上記のＭ値ピラミッドと可変タイリング・ブロック・サイズによる階層的モーション推定よりも大きい。
【００７５】
図８は、本発明を包含するウェーブレット・ベースの符号器８００を示す。符号器は、ブロック・モーション補正器（ＢＭＣ）かつモーション・ベクトル符号器８０４、減算器８０２、離散的ウェーブレット変換（ＤＷＴ）符号器８０６、ビット・レート制御器８１０、ＤＷＴ復号器８１２、出力バッファ８１４を含む。
【００７６】
一般に、上記のように、入力信号はビデオ画像（ビデオ・シーケンスのフレームを定義する画素の二次元配列）である。低ビット・レート・チャンネルを介して画像を正確に伝送するには、ビデオ・フレーム・シーケンスの空間的かつ時間的冗長を大幅に削減しなければならない。これは一般に、連続するフレーム間の差分のみを符号化し伝送することによりなされる。符号器は３つの機能を有する。第１に、ＢＭＣとその符号器８０４を用いて、フレーム間に生じるモーションを表す複数のモーション・ベクトルを産み出す。第２に、モーション・ベクトルに結び付けられた以前のフレームの再構築版を用いて現在のフレームを予測する。第３に、予測されたフレームが現在のフレームから減算され、受信器へのモーション・ベクトルとともに符号化され伝送される残余のフレームを産み出す。
【００７７】
離散的ウェーブレット変換は、ウェーブレット階層的サブバンド分解を行い、従来の技術である入力画像のウェーブレット・ツリー表示を産み出す。このような画像分解を成就するため、画像は２回のサブサンプリングを用いて、高水平・高垂直（ＨＨ）、高水平・低垂直（ＨＬ）、低水平・高垂直（ＬＨ）、低水平・低垂直（ＬＬ）の周波数サブバンドに分解される。次にＬＬサブバンドがさらに２回サブサンプルされ、ＨＨ、ＨＬ、ＬＨ、ＬＬのサブバンドの組を産み出す。このサブサンプリングは繰り返しなされ、図９に示されるようなサブバンドの配列を産み出す。図９では、３回のサブサンプリングがもちいられた。実際には６回のサブサンプリングを用いることが好ましい。サブバンド間の親子依存関係が、親ノードのサブバンドから子ノードのサブバンドを指し示す矢印のように示される。最低周波数サブバンドは左上ＬＬ1であり、最高周波数サブバンドは右下ＨＨ3である。この例において、全ての子ノードは１つの親を有する。サブバンド分解についての詳細な論考は、J. M. Shapiro, による「ウェーブレット係数のゼロツリーを用いる埋設画像の符号化（Embedded Image Coding Using Zerotrees of Wavelet Coefficients）」(IEEE Trans. on Signal Processing, 第41巻、 第12号、頁3445-62, 1993年12月)に記載されている。
【００７８】
図８のＤＷＴ符号器は、「幅先」または「深度先」のいずれかのパターンにウェーブレット・ツリーの係数を符号化する。幅先パターンは、ビット平面ずつのパターンのウェーブレット・ツリーを横断する。即ち、全ての親ノードを、次に全ての子を、次に全ての孫を、以下同様を量子化する。これに対し、深度先パターンは、子を介した低・低サブバンド（ＬＬ1）（トップ・ダウン）、または低・低サブバンドを介した子（ボトム・アップ）において、ルートから各ツリーを横断する。レート制御器８１０による適切な量子化レベルの選択は、上記のように、シーケンスの各フレーム内の各マクロブロック毎に、ビット・レートを制御する。このように本発明は、異なる変換を用いる各種符号器に適合し得る。
【００７９】
図６は、本発明の符号化システム６００を示す。符号化システムは、汎用コンピュータ６１０と各種入出力装置６２０を備える。汎用コンピュータは、中央処理装置（ＣＰＵ）６１２と、メモリ６１４と、画像のシーケンスを受け取り符号化する符号器６１６を備える。
【００８０】
好適実施形態においては、符号器６１６は上記のように単純に符号器１００と８００である。符号器６１６は、物理的装置で有り得て、通信チャンネルを介してＣＰＵ６１２に接続される。あるいは符号器６１６は、ソフトウェア・アプリケーション（または、例えば特殊用途向けＩＣ（ＡＳＩＣ）等のハードウェアとソフトウェアの組み合わせ）により代表される。この場合、該ソフトウェア・アプリケーションは、例えば磁気または光ディスク等の格納装置からロードされて、コンピュータのメモリ６１２に置かれる。このように、本発明の符号器１００は、コンピュータ可読媒体に格納され得る。
【００８１】
コンピュータ６１０は、キーボード、マウス、カメラ、ハンディ・ビデオコーダ、ビデオ・モニタ等の複数の入出力装置６２０、任意の数の映写装置、またそれに限定されるものではないが、テープ・ドライブ、フロッピー・ドライブ、ハード・ディスク・ドライブ、またはコンパクト・ディスク・ドライブを含む格納装置に接続され得る。入力装置は、符号化されたビデオ・ビットストリームを産み出すためにコンピュータに入力を提供するか、または、格納装置または映写装置からビデオ画像のシーケンスを受け取るよう機能する。最後に、通信チャンネル６３０が示され、ここで符号化システムからの符号化された信号は、（図示しない）復号システムへ転送される。
【００８２】
本発明の教示を包含する様々な実施形態をここに示し詳細に説明してきたが、当業者であれば、これらの教示を包含する他の多くの多岐にわたる実施形態を容易に考案できるであろう。
【図面の簡単な説明】
【図１】  ブロック・ベースのモーション推定に対しモーション・ベクトルを判断する際に計算量を削減する本発明の符号器のブロック図である。
【図２】  ブロック・ベースのモーション推定についてのモーション・ベクトルの判断に際しての計算量を減少させる方法のフローチャートである。
【図３】  一般的な平均ピラミッドのブロック図である。
【図４】  Ｍ値ピラミッドを生成する量子化処理のブロック図である。
【図５】  複数のブロックに分割かつ分類された入力フレームを示す図である。
【図６】  本発明の符号化システムを示す図である。
【図７】    ３スケール・タイリングによる画素ブロックのブロック図である。
【図８】  本発明の装置の第２の実施形態のブロック図である。
【図９】  ウェーブレット・ツリーのグラフ表示である。
【図１０】  画像に対しＭ値ピラミッドを生成する方法のフローチャートである。
【図１１】  Ｎスケール・タイリングによりＭ値ピラミッド上でモーション推定を行う方法のフローチャートである。
【図１】
0004205858.tif 000035
【図２】
0004205858.tif 000036
【図３】
0004205858.tif 000037
【図４】
0004205858.tif 000038
【図５】
0004205858.tif 000039
【図６】
0004205858.tif 000040
【図７】
0004205858.tif 000041
【図８】
0004205858.tif 000042
【図９】
0004205858.tif 000043
【図１０】
0004205858.tif 000044
【図１１】
0004205858.tif 000045