(57)【要約】  ビデオシーケンスフレームのブロック１２２〜１２６を分解する方法３００において、ブロック１２２〜１２６の寸法の一方又は双方が所定の最小寸法に等しいか否かについて判断される。寸法の一方又は双方が所定の最小寸法に等しいことに応じて、ブロック１２２〜１２６の動きベクトル１３２が送出される。寸法の双方が所定の最小寸法よりも大きいことに応じて、ブロック１２２〜１２６の動きベクトル１３２が求められ、ブロック１２２〜１２６が２つのウェッジ１３０ａ、１３０ｂに区画され、ブロック１２２〜１２６が４つのＮ／２×Ｎ／２サブブロック１２２〜１２６に分割され、これらのステップは、寸法の一方又は双方が所定の最小寸法に等しくなるまで、４つのＮ／２×Ｎ／２サブブロック１２２〜１２６のそれぞれに対して繰り返される。【選択図】図３Ａ
2010508706.tif 000002
【特許請求の範囲】
【請求項１】
ビデオシーケンスフレームを分解する方法（３００）であって、前記ビデオシーケンスフレームは、複数のブロック（１２２〜１２６）によって表され、
前記複数のブロック（１２２〜１２６）の少なくとも１つのブロックについて、
（ａ）前記少なくとも１つのブロックの寸法の一方又は双方が所定の最小寸法に等しいか否かを判断すること（３０４）と、
（ｂ）前記寸法の一方又は双方が前記所定の最小寸法に等しいことに応じて、前記ブロック（１２２〜１２６）の動きベクトル（１３２）を送出すること（３０６）と、
（ｃ）前記寸法の双方が前記所定の最小寸法よりも大きいことに応じて、
（ｉ）前記ブロック（１２２〜１２６）の動きベクトル（１３２）を求めること（３０８）と、
（ｉｉ）前記ブロック（１２２〜１２６）を２つのウェッジ（１３０ａ、１３０ｂ）に区画する（partitioning）こと（３０８）であって、前記ウェッジ（１３０ａ、１３０ｂ）のそれぞれは、異なる動きベクトル（１３２）に関連付けられる、区画すること（３０８）と、
（ｉｉｉ）前記ブロック（１２２〜１２６）を４つのＮ／２×Ｎ／２サブブロック（１２２〜１２６）に分割すること（３０８）と、
（ｉｖ）前記寸法の一方又は双方が前記所定の最小寸法に等しくなるまで、前記４つのＮ／２×Ｎ／２サブブロックのそれぞれに対してステップ（ａ）〜（ｃ）を繰り返すことと
を含む方法。
【請求項２】
前記ブロック（１２２〜１２６）をウェッジ（１３０ａ、１３０ｂ）に区画すること（３０８）は、
前記ブロック（１２２〜１２６）のウェッジ（１３０ａ、１３０ｂ）への区画を、事前に選択されたウェッジ（１３０ａ、１３０ｂ）のセットに制限すること
をさらに含み、
該事前に選択されたウェッジ（１３０ａ、１３０ｂ）のセットは、
前記ブロック（１２２〜１２６）におけるすべての可能なウェッジ区画のサブセット
を含み、
それによって、前記ウェッジ（１３０ａ、１３０ｂ）の検索に関連付けられる計算要件を大幅に削減する
請求項１に記載の方法。
【請求項３】
前記ブロック（１２２〜１２６）をウェッジ（１３０ａ、１３０ｂ）に区画すること（３０８）は、
２つのウェッジ（１３０ａ、１３０ｂ）の１つがゼロ動きベクトル（１３２）を有するように、前記ブロック（１２２〜１２６）を前記２つのウェッジ（１３０ａ、１３０ｂ）に区画すること（３０８）
をさらに含む
請求項１又は２に記載の方法。
【請求項４】
前記ウェッジ（１３０ａ、１３０ｂ）の前記動きベクトル（１３２）は残差を含み、
該方法は、
前記ゼロ動きベクトル（１３２）を含む前記ウェッジ（１３０ａ、１３０ｂ）の前記残差をゼロに量子化すること（４０４）であって、それによって、前記ウェッジ（１３０ａ、１３０ｂ）の前記動きベクトル（１３２）を搬送するレートを削減する、量子化すること（４０４）
をさらに含む請求項３に記載の方法。
【請求項５】
前記ブロック（１２２〜１２６）をウェッジ（１３０ａ、１３０ｂ）に区画すること（３０８）は、
前記ウェッジ（１３０ａ、１３０ｂ）のそれぞれの前記動きベクトル（１３２）を、前記ブロック（１２２〜１２６）の空間的近傍からの動きベクトル（１３２）の比較的小さなセットに制限することであって、それによって、前記ウェッジ（１３０ａ、１３０ｂ）を検索することに関連付けられる計算要件を削減する、制限すること
をさらに含む
請求項１〜４のいずれかに一項に記載の方法。
【請求項６】
前記ブロック（１２２〜１２６）をウェッジ（１３０ａ、１３０ｂ）に区画すること（３０８）は、
前記ブロック（１２２〜１２６）を２つのウェッジ（１３０ａ、１３０ｂ）及び該２つのウェッジ（１３０ａ、１３０ｂ）の間の可変の厚さの平行バンドに区画すること（３０８）
をさらに含み、
前記２つのウェッジ（１３０ａ、１３０ｂ）のそれぞれ及び前記平行バンドは、異なる動きベクトル（１３２）に関連付けられる
請求項１〜５のいずれか一項に記載の方法。
【請求項７】
ステップ（ｉｉ）における前記ブロックをウェッジに区画すること（３０８）は、前記ウェッジ（１３０ａ、１３０ｂ）のそれぞれの残差を与え（yield）、
該方法は、
前記残差を正方形ブロックに結合して（４０２）、該正方形ブロックを単一ブロック変換の使用によって符号化すること、及び
２つの別個の形状適応型変換（shape-adaptive transform）を使用して前記残差を符号化すること（１０２）
の一方をさらに含む請求項１〜６のいずれか一項に記載の方法。
【請求項８】
ビデオシーケンスフレームを符号化するためのエンコーダ（１１２）であって、前記ビデオシーケンスフレームは、第１の寸法セットを有する複数のブロック（１２２〜１２６）によって表され、
該エンコーダ（１１２）は、
ウェッジ区画器（２２４）と、
ブロック分割器（２２２）と、
動き推定器（２２６）と、
前記少なくとも１つのブロック（１２２〜１２６）を２つのウェッジ（１３０ａ、１３０ｂ）に区画することに関連付けられる前記動きベクトル（１３２）の第１のメトリックを計算し、前記少なくともブロックをサブブロック（１２２〜１２６）に分割することに関連付けられる前記動きベクトル（１３２）の第２のメトリックを計算するように構成される誤差計算機（２２８）と
を備え、
少なくとも１つのブロック（１２２〜１２６）について、コントローラ（２０４）は、
（ａ）前記少なくとも１つのブロック（１２２〜１２６）の前記寸法の一方又は双方が所定の最小寸法に等しいか否かを判断し、
（ｂ）前記寸法の前記一方又は双方が前記所定の最小寸法に等しいことに応じて、前記動き推定器（２２６）を実施して、前記少なくとも１つのブロックの動きベクトル（１３２）を推定し、
前記寸法の双方が前記所定の最小寸法よりも大きいことに応じて、
（ｃ）前記動き推定器（２２６）を実施して、前記少なくとも１つのブロック（１２２〜１２６）の動きベクトル（１３２）を推定し、
（ｄ）前記ウェッジ区画器（２２４）を実施して、前記複数のブロック（１２２〜１２６）の前記少なくとも１つのブロック（１２２〜１２６）を２つのウェッジ（１３０ａ、１３０ｂ）に区画し、
（ｅ）前記ブロック分割器（２２２）を実施して、前記少なくとも１つのブロック（１２２〜１２６）を、第２の寸法セットを有するサブブロック（１２２〜１２６）に分割して、該サブブロック（１２２〜１２６）のそれぞれについて（ａ）〜（ｅ）を実行する
ように構成される
エンコーダ。
【請求項９】
前記コントローラ（２０４）は、２つのウェッジ（１３０ａ、１３０ｂ）の一方がゼロ動きベクトル（１３２）を有するように、前記ウェッジ区画器（２２４）を実施して、前記ブロック（１２２〜１２６）を前記２つのウェッジ（１３０ａ、１３０ｂ）に区画するようにさらに構成される
請求項８に記載のエンコーダ。
【請求項１０】
１つ又は複数のコンピュータプログラムが実施化されるコンピュータ可読ストレージ媒体であって、
前記１つ又は複数のコンピュータプログラムは、ビデオシーケンスフレームを分解する方法（３００）を実施し、前記ビデオシーケンスフレームは、複数のブロック（１２２〜１２６）によって表され、
前記１つ又は複数のコンピュータプログラムは、
前記複数のブロック（１２２〜１２６）のそれぞれの寸法の一方又は双方が所定の最小寸法に等しいか否かを判断する（３０４）ための命令と、
前記寸法の一方又は双方が前記所定の最小寸法に等しいブロック（１２２〜１２６）について、前記ブロック（１２２〜１２６）の動きベクトル（１３２）を送出するための命令と、
前記寸法の双方が前記所定の最小寸法よりも大きいブロック（１２２〜１２６）について、
前記ブロック（１２２〜１２６）の動きベクトル（１３２）を求める（３０８）ための命令と、
前記ブロック（１２２〜１２６）を２つのウェッジ（１３０ａ、１３０ｂ）に区画する（３０８）ための命令であって、前記ウェッジ（１３０ａ、１３０ｂ）のそれぞれは、異なる動きベクトル（１３２）に関連付けられる、区画する（３０８）ための命令と、
前記ブロック（１２２〜１２６）を４つのＮ／２×Ｎ／２サブブロック（１２２〜１２６）に分割する（３０８）ための命令と、
前記寸法の一方又は双方が前記所定の最小寸法に等しくなるまで、前記４つのＮ／２×Ｎ／２サブブロック（１２２〜１２６）のそれぞれに対してステップ（ａ）〜（ｃ）を繰り返すための命令と
から成る命令セットを含む
コンピュータ可読ストレージ媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビデオシーケンスフレームを分解する方法に関する。
【背景技術】
【０００２】
通常、ビデオシーケンスの時間変動は、カメラ又は物体の動きによって生じる。
この動きの補償が利用可能である場合、比較的コンパクトな動き情報で、ビデオ画像予測シーケンスの改善も可能である。これによって、ビデオ圧縮アルゴリズムは、許容可能な品質のレベルで、ビデオシーケンスを送信するのに必要なデータ量を大幅に削減することが可能になる。
【０００３】
国際ビデオ符号化標準規格Ｈ．２６４、ＭＰＥＧ−４パート１０、又はアドバンスビデオ符号化（Advance Video Coding：ＡＶＣ）のもとでは、符号化プロセスは、１６×１６ピクセルのマクロブロックの単位を使用して行われる。
加えて、動き補償は、通常、４分木分解でマクロブロックを正方形又は長方形のサブマクロブロックに区画することによって行われる。
この動き補償技法では、サイズＮ×Ｎの各リーフ（leaf）レベルブロックが、異なる動きベクトル及び符号化モードに関連付けられる。
その上、残差は、適切な変換、並びにその後に続く量子化及びエントロピー符号化を使用して符号化される。
【０００４】
従来の技法は、カメラ又は物体の動きの補償において、それ以前の技法を上回る改良を与えてきた。
しかしながら、従来の４分木分解は、正方形又は長方形のマクロブロック及びサブマクロブロックに制限されるので、マクロブロックの形状は、通常、移動物体の形状の輪郭に対応していない。
マクロブロック及びサブマクロブロックの固定した形状のため、同じマクロブロックが、異なる動きを有するいくつかの領域を含む状況では、符号化効率は大幅に低減される。
【発明の概要】
【０００５】
本発明にかかる方法は、ビデオシーケンスフレームを分解する方法（３００）であって、前記ビデオシーケンスフレームは、複数のブロック（１２２〜１２６）によって表され、前記複数のブロック（１２２〜１２６）の少なくとも１つのブロックについて、（ａ）前記少なくとも１つのブロックの寸法の一方又は双方が所定の最小寸法に等しいか否かを判断すること（３０４）と、（ｂ）前記寸法の一方又は双方が前記所定の最小寸法に等しくなることに応じて、前記ブロック（１２２〜１２６）の動きベクトル（１３２）を送出すること（３０６）と、（ｃ）前記寸法の双方が前記所定の最小寸法よりも大きくなることに応じて、（ｉ）前記ブロック（１２２〜１２６）の動きベクトル（１３２）を求めること（３０８）と、（ｉｉ）前記ブロック（１２２〜１２６）を２つのウェッジ（１３０ａ、１３０ｂ）に区画する（partitioning）こと（３０８）であって、前記ウェッジ（１３０ａ、１３０ｂ）のそれぞれは、異なる動きベクトル（１３２）に関連付けられる、区画すること（３０８）と、（ｉｉｉ）前記ブロック（１２２〜１２６）を４つのＮ／２×Ｎ／２サブブロック（１２２〜１２６）に分割すること（３０８）と、（ｉｖ）前記寸法の一方又は双方が前記所定の最小寸法に等しくなるまで、前記４つのＮ／２×Ｎ／２サブブロックのそれぞれに対してステップ（ａ）〜（ｃ）を繰り返すこととを含む。
【図面の簡単な説明】
【０００６】
本発明の特徴は、図面に関連した以下の説明から当業者に明らかになるであろう。
【０００７】
【図１Ａ】本発明の一実施形態によるビデオ符号化システムの簡単化した機能ブロック図である。
【図１Ｂ】本発明の一実施形態による、エンコーダがマクロブロックを分解することができる方法の機能ブロック図である。
【図１Ｃ】本発明の一実施形態による連続的なウェッジの例を示す。
【図１Ｄ】本発明の一実施形態による離散的なウェッジの例を示す。
【図２】本発明の一実施形態による、図１Ａに示すビデオ符号化システムのブロック図である。
【図３Ａ】本発明の一実施形態による、ビデオシーケンスフレームを分解する方法のフロー図を示す。
【図３Ｂ】本発明の一実施形態による、ビデオシーケンスフレームを分解する方法のフロー図を示す。
【図３Ｃ】本発明の一実施形態による、ビデオシーケンスフレームを分解する方法のフロー図を示す。
【図４】本発明の一実施形態による、分解されたビデオシーケンスフレームを処理する方法のフロー図を示す。
【図５】本発明の一実施形態による、ブロックを符号化する方法のフロー図を示す。
【図６】本発明の別の実施形態による、ブロックを符号化する方法のフロー図を示す。
【発明を実施するための形態】
【０００８】
簡単にするために且つ例示を目的として、本発明の一例示の実施形態を主に参照することによって本発明を説明する。
以下の説明では、本発明の徹底した理解を提供するために、多数の具体的な詳細が述べられる。
しかしながら、これらの具体的な詳細に限定されることなく本発明が実施されうることは、当業者には明らかであろう。
それ以外の場合には、本発明を不必要に不明瞭にしないように、既知の方法及び構造は詳細に説明されていない。
【０００９】
本明細書では、ビデオコーデックの残差およびレート歪効率等の１つ又は複数のメトリックを向上させるための方法及びシステムが開示される。
より詳細には、本明細書で開示される方法及びシステムは、マクロブロックをサブブロックに区画するだけでなく、適切な場合にはそれらのブロックをウェッジレット（wedgelet）にも区画する技法を用いる。
ウェッジレット又はウェッジは、ブロック内の任意の合理的に適した且つ所望のロケーションに形成することができ、縦の線及び横の線に制限されないので、ブロックと比較して、画像のエッジを表す際に比較的効率が良い。
加えて、異なる動き補償を特定のブロックの異なるウェッジに使用して、ブロック内の動作をより正確に補償することができ、したがって、残差、レート歪効率等を向上させることができる。
【００１０】
また、本明細書では、ブロックを区画すること（partitioning）に関連付けられる計算複雑度を大幅に削減する方法及びシステムも開示される。
換言すれば、本明細書で開示される方法及びシステムは、ブロックが区画される箇所を選択する比較的高速で且つ計算複雑度の少ない方法を可能にする一方、それにもかかわらず、残差を実質的に最小にし、且つ／又は、レート歪効率を実質的に最大にすることを提供する。
【００１１】
まず図１を参照して、本発明の一例によるビデオ符号化システム１０２の簡単化した機能ブロック図１００が示されている。
以下の本明細書では、ビデオ符号化システム１０２は、特定の特徴を含むものとして特に参照されるが、ビデオ符号化システム１０２は、追加のコンポーネントを含むことができ、本明細書で説明されるそれらのコンポーネントのいくつかは、ビデオ符号化システム１０２の範囲から逸脱することなく削除及び／又は変更することができることが理解されるべきである。
【００１２】
図１Ａに示すように、ビデオ符号化システム１０２は、エンコーダ１１２、量子化器１１４、及びエントロピー符号化器１１６を含む。
作動中、ビデオ符号化システム１０２は、ビデオソース１１０からビデオコンテンツを受信する。
ビデオソース１１０には、データストレージデバイス、ネットワーク、インターネット、別個のコンピューティングデバイス等の任意の合理的に適切なソース（source）が含まれ得る。
加えて、ビデオコンテンツには、アナログビデオ又はデジタルビデオが含まれ得る。
【００１３】
以下の本明細書でより詳細に説明されるように、ビデオ符号化システム１０２は、一般に、ビデオソース１１０から受信されたビデオコンテンツに対してさまざまな符号化機能を実行し、それによって、符号化ビデオ１１８を出力する。
或る点について、ビデオ符号化システム１０２は、ビデオコンテンツに対して動き推定オペレーション又は動き補償オペレーションを実行することができる。
一般的に言えば、動き推定は、ビデオシーケンスから動き情報を抽出するのに使用される一組の技法を指す。
ＭＰＥＧ標準規格は、順方向予測、逆方向予測、又は平均といった動き補償のタイプに応じて、１つのマクロブロック当たり１つ又は２つの動きベクトルを提供することによって動き情報を表す。
加えて、動き推定は、マクロブロックの最適な動きベクトル又はほぼ最適な動きベクトルを見つけるプロセスも含み得る。
【００１４】
例として、エンコーダ１１２は、第１の時刻にサンプリングされた現フレームにおけるマクロブロックからのビデオコンテンツの動きを、第２の時刻にサンプリングされた基準フレームにおける同様のサイズのマクロブロックで推定することができる。
この第２のサンプル時刻は、現フレームのサンプル時刻よりも前とすることができる。
【００１５】
ビデオコンテンツの動きを推定する際に、図１Ｂに関して以下で本明細書でより詳細に説明されるように、エンコーダ１１２は、ビデオコンテンツをシーケンシャルなフレームに分解することができ、それらのシーケンシャルなフレームをさまざまなサイズのブロック及びさまざまな位置のウェッジにさらに分解することができる。
ブロック及びウェッジのロケーション及びサイズは、たとえば、フレームに含まれる物体のエッジに基づくことができる。
加えて、エンコーダ１１２は、さまざまなサイズのブロック及びさまざまな位置のウェッジの動きベクトル及び残差（予測誤差）を計算及び符号化することができる。
エンコーダ１１２は、動きベクトルを計算することができる。動きベクトルは、現在のマクロブロックと、照合された先行マクロブロックとの間の関係を識別する。
たとえば、動きベクトルは、第１のマクロブロックと第２のマクロブロックとの間のピクセルの位置の変化を識別することになる。
加えて、ブロック及びウェッジのそれぞれは、異なる動きベクトル及び符号化モードに関連付けられ得る。
【００１６】
エンコーダ１１２は、先に符号化されたフレームからの動きに基づく予測後、又は、現フレームのすでに符号化された部分からのイントラ予測後のいずれかで取得された残差も求めることができる。
この残差も、適切な変換、並びにその後に続く量子化及びエントロピー符号化を使用して符号化することができる。
ウェッジに区画されたブロックの場合、ウェッジを結合するブロックベースの変換を使用して残差を符号化することもできるし、個々のウェッジについてのより適切な形状適応型変換（shape-adaptive transform）を使用して残差を符号化することもできる。
【００１７】
一般的に言えば、動きベクトルとは、照合マクロブロックの任意のピクセルの座標に追加されるときに、現マクロブロックの座標を提供する値である。
動き推定手順はマクロブロックに基づくベクトルを提供するので、通常ならばピクセル単位で行われるさらなるすべての計算は、マクロブロック単位で行われる。
したがって、この動き推定方法が必要とする計算能力は、他のピクセルごとの近似技法よりも少ない。
【００１８】
次に図１Ｂを特に参照して、本発明の一例による、エンコーダ１１２がマクロブロック１２２を分解することができる方法の機能ブロック図１２０が示されている。
機能ブロック図１２０の以下の説明は、マクロブロック１２２を分解することができるさまざまな異なる方法の一方法にすぎないことが理解されるべきである。
加えて、マクロブロック１２２を分解する方法は、マクロブロック１２２に含まれるピクセルのさまざまな特性に依存する場合があり、したがって、マクロブロック１２２ごとに変化することも理解されるべきである。
【００１９】
エンコーダ１１２は、ビデオコンテンツを複数のフレームに事前に分解しておくことができる。加えて、エンコーダ１１２は、複数のフレームの少なくとも１つを複数のマクロブロック１１２に事前に分解しておくことができる。
マクロブロック１１２は、Ｈ．２６４、ＭＰＥＧ−４パート１０、及びＡＶＣで標準的なように、たとえば、それぞれ１６×１６ピクセルを含むことができる。
【００２０】
エンコーダ１１２は、マクロブロック１２２のいくつか又はすべてを８×８ピクセルのサブブロック１２４のセットにさらに分解することができる。
エンコーダ１１２は、４分木分解技法で知られているように、８×８ピクセルのサブブロック１２４のいくつか又はすべてを４×４ピクセルのサブブロック１２６にさらに分解することができる。
一般的に言えば、エンコーダ１１２は、マクロブロック１２２に含まれる移動物体の輪郭形状に基づいてどのマクロブロック１２２のどのセクションをさらに分解すべきかを判断することができる。
【００２１】
従来、マクロブロック１２２の分割は、正方形及び長方形に限られており、したがって、ブロック１２２〜１２６の形状は、通常、移動物体の輪郭形状に正確に対応していない。
したがって、同じブロック１２２〜１２６内の異なるセクションが異なる動きベクトルを有する場合に、符号化効率は低減される。
【００２２】
一例によれば、以下の本明細書でより詳細に説明するように、ブロック１２２〜１２６の１つ又は複数は、ウェッジレット１３０ａ及び１３０ｂの使用によってさらに分解することができる。ウェッジレット１３０ａ及び１３０ｂは、図１Ｂに示すように、ブロック１２２〜１２６を通るスライス線１２８の挿入によって形成される。
より詳細には、エンコーダ１１２は、画像の幾何学的構造をより正確に捉えることに向けて、マルチスケールウェッジレット１３０ａ、１３０ｂのフレームワークを用いることができ、それによって、従来の技法を上回って符号化効率を改善することができる。
ウェッジ１３０ａ、１３０ｂは、任意のサイズのブロック１２２〜１２６に挿入可能であるので、マルチスケールとみなされる。
【００２３】
例として、エンコーダ１１２は、ブロック１２２〜１２６をスライス線１２８に沿って２つのウェッジ１３０ａ、１３０ｂに分割することによって、Ｎ×Ｎブロック１２２〜１２６にウェッジを挿入することができる。
スライス線１２８は、方位角θを有することができ、ブロック１２２〜１２６の中心ｏから距離ｒに配置され得る。
スライス線１２８及びウェッジ１３０ａ、１３０ｂを有するブロック１２２〜１２６の描写は、図１Ｃ及び図１Ｄに提供されている。
図１Ｃに示すスライス線１２８は連続的であり、図１Ｄに示すスライス線１２８は離散的である。
たとえば、図１Ｃに示す連続的なスライス線１２８は、スライス線１２８の実際のロケーションを示し、図１Ｄに示すスライス線１２８は、スライス線１２８上に配置されたピクセルがウェッジ１３０ａ、１３０ｂのどちら側に入るのかに基づいた、スライス線１２８の離散化されたバージョンを示している。
スライス線１２８は、スライス線１２８がピクセルのどちら側に配置されるのかを決定することによって、スライス線１２８（図１Ｃ）に沿ったピクセルのそれぞれについて離散化することができる。
スライス線１２８がピクセルの中心に直接配置される状況では、スライス線１２８は、その選択がデコーダと一貫している限り、ピクセルのいずれの側にも配置され得る。
【００２４】
エンコーダ１１２は、スライス線１２８がブロック１２２〜１２６のどの位置も通るようにスライス線１２８を位置づけることができる。
エンコーダ１１２は、方位角θ及び距離ｒの空間を適切な間隔でサンプリングすることによって、Ｎ×Ｎブロック１２２〜１２６におけるすべてのウェッジ区画１３０ａ、１３０ｂのセットを生成することができ、Ｎｗ個のエントリーの辞書を与えることができる。
このＮｗ個のエントリーの辞書は、方位角θ及び距離ｒの増分精度（increment precision）等の設計パラメータに依存し得る。
【００２５】
理想的には、すべての可能なブロックの組み合わせのすべての可能なウェッジ１３０ａ、１３０ｂのセグメント化は、最良のウェッジ１３０ａ、１３０ｂを求めるように予測されるべきである。
しかしながら、ブロック１２２〜１２６の区画ストラテジーの数は極めて大きい場合があるので、本発明の一例によれば、最良の区画ストラテジーの高速検索方法を用いることができる。
より詳細には、ブロック１２２〜１２６内のすべてのウェッジ区画の可能性を試験する代わりに、たとえば、適切なブロックパーティションのより小さなサブセットを任意のスケールで事前に選択することができる。
【００２６】
一例によれば、Ｎ×Ｎブロック内において、キャニー（Canny）、ゾーベル（Sobel）等のエッジ検出アルゴリズムを使用し、その後にしきい値処理オペレーションを続けることができる。
これによって、エッジを示すブロックと同じサイズの２次元論理アレイが与えられる。
次に、肯定応答を有するピクセルは、（ｘ，ｙ）対を与えるユークリッドピクセル座標にマッピングされ、（最小二乗誤差に基づく）線形回帰がこれらの点に適用される。
その結果は、直線の一般式ｙ＝ａｘ＋ｂ又はｘ＝ｃ（回帰が関数でないとき）となる。
この直線は、極座標に変換され、ウェッジ区画に関連付けられる。
（ｘ０，ｙ０）をブロックの中心とし、Ｎをブロックサイズとし、θ０を、ａｘ０＋ｙ０＋ｂが正であるときはθ０＝０度となり、そうでないときはθ０＝１８０度となるようなａｘ０＋ｙ０＋ｂの符号に依存するオフセットとする。
この場合、ｒ及びθの開始点（シード）が見つけられる。
【００２７】
【数１】
2010508706.tif 000003
【００２８】
及び
【００２９】
【数２】
2010508706.tif 000004
【００３０】
これら回帰の結果をｘ＝ｃ内にケーシング（case）して、
【００３１】
【数３】
2010508706.tif 000005
【００３２】
及び
【００３３】
【数４】
2010508706.tif 000006
【００３４】
を取得することができる。
【００３５】
ここで、θ０は、Ｎ／２＋ｃ＞０である場合にはθ０＝９０度であり、そうでない場合にはθ０＝２７０度であるようなＮ／２−ｃの符号に依存するオフセットである。
【００３６】
開始シードｒseed及びθseedから、パラメータｒ及びθ０＝９０度を［ｒseed−Δｒ，ｒseed＋Δｒ］及び［θseed−Δθ，θseed＋Δθ］の範囲内において増分δｒ及びδθでそれぞれわずかに変化させることによって、ウェッジ１３０ａ、１３０ｂのセットを事前に選択することができる。
【００３７】
別の例によれば、ブロック１２２〜１２６内に複数の移動エッジ又は移動テクスチャがあるとき等、一定の場合には、カノニカル４分木（canonical quadtree）区画を行うこともできる。
いずれの点に関しても、動き推定及び区画検索は、事前に選択されたウェッジのセットに制限することができ、これによって、ウェッジ１３０ａ、１３０ｂを検索する際の計算要件を大幅に削減することができる。
【００３８】
ウェッジ１３０ａ、１３０ｂを検索する際の計算要件は、本発明のさらなる例によれば、第２の比較的効率的な検索ストラテジーを実施することによって大幅に削減することができる。
この第２の比較的効率的な検索ストラテジーは、ブロック１２２〜１２６のいずれかのウェッジ１３０ａ、１３０ｂの１つがゼロ動きベクトルを有するか否かを判断することを含む。
ウェッジ１３０ａ、１３０ｂの対におけるウェッジ１３０ａ、１３０ｂの１つは、たとえば、ビデオキャプチャデバイスが静止しており、物体が静止した背景の前を移動している状況では、ゼロ動きベクトルを有することができる。
これらの場合、ゼロ動きベクトルを有するそれらのウェッジ１３０ａ、１３０ｂの予測誤差は、比較的小さい。
【００３９】
したがって、十分大きなウェッジについて十分小さな予測誤差を有するウェッジ１３０ａ、１３０ｂの決定を通じて、大幅に最適化されたウェッジ１３０ａ、１３０ｂを求めることができる。
加えて、マスキングされた動き検索によって、残りのウェッジ１３０ａ、１３０ｂの動きベクトル１３２を容易に計算することができる。ここで、対象となる領域は、ウェッジ１３０ａ、１３０ｂに含まれないブロック１２２〜１２６の部分のそれらのピクセルのみを含むバイナリマスクによって規定される。
或る点に関して、この例は、ウェッジにされたブロックについて単一の動きベクトルを送出することができるので、動き情報を搬送するレートを削減することができる。
【００４０】
さらなる例によれば、ウェッジ１３０ａ、１３０ｂの１つが、ゼロ動きベクトルを有し、且つ、予測残差が、形状適応型変換のすべての変換係数が０に量子化されるという目標品質と比較して十分小さい状況では、ウェッジ１３０ａ、１３０ｂは、従来のビデオ符号化の「ＳＫＩＰ（スキップ）」モードと類似の方法で取り扱われ得る。
【００４１】
さらに別の例によれば、ウェッジ１３０ａ、１３０ｂの１つの動きベクトルは、現ブロック１２２〜１２６の空間的近傍からの比較的小さな動きベクトルのセットに制限することができる。
この例では、エンコーディングは、上述したゼロ動きベクトルの場合と同様に進む。ここで、すべての可能な予測判断材料（predictor）の動きベクトルは、最良のウェッジを求めて試験される。
【００４２】
さらなる例によれば、ゼロ動きベクトルを有するウェッジ１３０ａ、１３０ｂについて予測残差を０に量子化することができ、それによって、これらのウェッジ１３０ａ、１３０ｂの動き情報を搬送するレートを削減することができる。
【００４３】
図１Ｂを再び参照して、エンコーダ１１２は、Ｎ×Ｎブロック１２２〜１２６のいずれをもウェッジ１３０ａ、１３０ｂに分割することができる。
エンコーダ１１２は、さらに、ウェッジ１３０ａ、１３０ｂのそれぞれについて動き推定を独立に行うことができ、それによって、ウェッジ１３０ａ、１３０ｂを含むブロック１２２〜１２６のそれぞれについて２つの動きベクトル１３２を生成することができる。
したがって、動きベクトル１３２に関連付けられる残差のそれぞれを別々に符号化することもできるし、以下の本明細書で説明するように、それらの残差を結合して、単一の残差として符号化することもできる。
【００４４】
次に図２を参照して、一例によるビデオ符号化システム１０２のブロック図２００が示されている。
ブロック図２００の以下の説明は、ビデオ符号化システム２０２が構成され得るさまざまな異なる方法の一方法にすぎないことが理解されるべきである。
加えて、ビデオ符号化システム２０２は、追加のコンポーネントを含むことができること、及び、本明細書で説明するコンポーネントのいくつかは、ビデオ符号化システム２０２の範囲から逸脱することなく除去及び／又は変更され得ることが理解されるべきである。
【００４５】
ビデオ符号化システム１０２は、一般のコンピューティング環境を備えることができ、ビデオ符号化システム１０２のさまざまなオペレーションを制御するように構成されるコントローラ２０４を含む。
コントローラ２０４には、マイクロプロセッサ、マイクロコントローラ、特定用途向け集積回路（Application specific integrated circuit：ＡＳＩＣ）等が含まれ得る。
ビデオ符号化システム１０２のさまざまなコンポーネントを連結するように動作するシステムバス２０６によって、ビデオ符号化システム１０２のさまざまなコンポーネントへデータを送信することができる。
システムバス２０６は、いくつかのタイプのバス構造の任意のものを表す。これらのバス構造には、たとえば、メモリバス、メモリコントローラ、周辺バス、アクセラレーティッドグラフィックスポート、さまざまなバスアーキテクチャの任意のものを使用するプロセッサバス等が含まれる。
【００４６】
コマンド、命令、データ等の情報をビデオ符号化システム１０２に入力するのに、１つ又は複数の入力デバイス２０８を用いることができる。
入力デバイス２０８には、たとえば、ホストコンピュータ、キーボード、マウス、スキャナ、ディスクドライブ、着脱可能媒体、フラッシュドライブ等が含まれ得る。
また、１つ又は複数のビデオソース１１０も示されている。ビデオソース１１０には、入力デバイス２０８又は別個のデバイスが含まれ得る。
入力デバイス（複数可）２０８及びビデオソース（複数可）１１０またはこれらのいずれか（入力デバイス（複数可）２０８及び／又はビデオソース（複数可）１１０）は、たとえば、画像、画像のフレーム、ビデオフレーム、又はビデオ画像の表現（すなわち、符号フォーマットのビデオ画像。後の本明細書では、簡単にするために「ビデオ画像」として参照される）をビデオ符号化システム１０２に入力するのに使用することができる。
図示するように、入力デバイス（複数可）２０８及びビデオソース（複数可）は、システムバス２０６に連結されたインターフェース２１０を通じてコントローラ２０４に接続される。
しかしながら、入力デバイス（複数可）及びビデオソース（複数可）１１０は、パラレルポート、ＵＳＢポート等の他の従来のインターフェース及びバス構造によって連結することもできる。
図示していないが、インターフェース２１０は、システムバス２０６を他のコンピュータシステムと連結するインターフェースとして動作することもできる。
【００４７】
コントローラ２０４は、システムバス２０６を通じてメモリ２１２に接続され得る。
一般的に言えば、メモリ２１２は、ビデオ符号化システム１０２の機能を提供するソフトウェア、アルゴリズム等のストレージを提供するように構成され得る。
例として、メモリ２１２は、オペレーティングシステム２１４、アプリケーションプログラム２１６、プログラムデータ２１８等を記憶することができる。
この点に関して、メモリ２１２は、ＤＲＡＭ、ＥＥＰＲＯＭ，ＭＲＡＭ、フラッシュメモリ等の揮発性メモリ及び不揮発性メモリを組み合わせたものとして実施され得る。
加えて又は代替的に、メモリ２１２は、フロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、他の光媒体又は磁気媒体等の着脱可能媒体からの読み出し及びそれらの着脱可能媒体への書き込みを行うように構成されるデバイスも備えることができる。
【００４８】
コントローラ２０４は、システムバス２０６を通じてエンコーダ１１２、量子化器１１４、及びエントロピー符号化器１１６にも接続され得る。
一例では、エンコーダ１１２、量子化器１１４、及びエントロピー符号化器１１６は、１つ又は複数の離散コンポーネントから成るハードウェアを備えることができる。
加えて又は代替的に、エンコーダ１１２、量子化器１１４、及びエントロピー符号化器１１６は、たとえば、メモリ２１２に記憶されたソフトウェアを備えることができる。
いずれの点に関しても、本明細書でより詳細に説明するように、コントローラ２０４は、エンコーダ１１２、量子化器１１４、及びエントロピー符号化器１１６を実施又は起動して、ビデオソース（複数可）から受信されたビデオコンテンツを符号化するように構成され得る。
コントローラ２０４は、エンコーダ１１２とは別個のコンポーネントを形成するものとして描かれ説明されてきたが、エンコーダ１１２の範囲から逸脱することなく、コントローラ２０４は、エンコーダ１１２の一部を成すことができ、この場合、エンコーダ１１２は、コントローラ２０４及び本明細書で説明したコントローラ２０４の機能を含む。
【００４９】
図２に示すように、エンコーダ１１２は、フレーム分解器２２０、ブロック分割器２２２、ウェッジ区画器２２４、動き推定器２２６、及び誤差計算機２２８を含む。
エンコーダ１１２に含まれるこれらの要素２２０〜２３０は、ソフトウェアモジュール、ハードウェアコンポーネント、又はそれらの組み合わせを備えることができる。
コントローラ２０４は、要素２２０〜２３０を実施又は起動して、ビデオシーケンスフレームを分解し、ビデオシーケンスフレームに含まれる動きを推定することができる。
【００５０】
加えて、コントローラ２０４は、量子化器１１４を実施又は起動して、ビデオシーケンスフレームの符号化された部分を量子化することができ、エントロピー符号化器１１６を実施又は起動して、符号化されたビデオシーケンスフレームをエントロピー符号化することができる。
その上、コントローラ２０４は、符号化されたビデオ１１８を、１つ又は複数のアダプタ２３２を通じてビデオ符号化システム１０２の外部へ送信又は別の方法で送出することができる。
第１の例では、符号化されたビデオ１１８は、内部ネットワーク、外部ネットワーク（インターネット）等のネットワークによって別のコンピューティングデバイスへ送出され得る。
第２の例では、符号化されたビデオ１１８は、ディスプレイ、プリンタ、ファクシミリマシン等の１つ又は複数の出力デバイスへ出力され得る。
【００５１】
次に図３Ａを参照して、一例によるビデオシーケンスフレームを分解する方法３００のフロー図が示されている。
方法３００は、一般化された実例を表していること、及び、方法３００の範囲から逸脱することなく、他のステップを追加することもできるし、既存のステップを除去、変更、又は再配列することもできることが当業者には明らかなはずである。
【００５２】
方法３００の説明は、図２に示すブロック図２００を参照して行われ、したがって、図２で引用された要素を参照する。
しかしながら、方法３００は、ブロック図２００で述べた要素に限定されるものではないことが理解されるべきである。
それどころか、方法３００は、ブロック図２００で述べたものとは異なる構成を有するシステムによって実施され得ることが理解されるべきである。
【００５３】
一般的に言えば、方法３００を実施して、さまざまな状況のウェッジ１３０ａ、１３０ｂを含むように、４分木分解等の動き推定モデルを拡張することができ、それによって、ビデオコーデックの残差、レート歪効率等の１つ又は複数のメトリックを向上させることができる。
或る点に関して、ウェッジ１３０ａ、１３０ｂは、相対的により正確な移動物体のエッジ表現を提供するので、１つ又は複数のメトリックが向上され得る。
【００５４】
方法３００において、ビデオ符号化システム１０２は、ビデオシーケンスフレーム３０１の形のビデオコンテンツ又はビデオシーケンスフレーム３０１を表すデータを受信することができる。
ステップ３０２において、コントローラ２０４は、エンコーダ１１２、より詳細にはフレーム分解器２２０を起動又は実施して、ビデオシーケンスフレーム３０１のそれぞれを、第１の寸法セットＮ×Ｎを有するマクロブロック１２２に分解することができる。
フレーム分解器２２０は、たとえば、４分木分解技法を用いて、図１Ｂに示すようにビデオシーケンスフレーム３０１を分解することができる。
【００５５】
ステップ３０４において、コントローラ２０４は、エンコーダ１１２、より詳細にはフレーム分解器２２０を起動又は実施して、マクロブロック１２２の第１の寸法セットの一方又は双方が所定の最小寸法（Ｎｓ）に等しいか否かを判断することができる。
この所定の最小寸法（Ｎｓ）は、エンコーダ１１２がマクロブロック１２２を分解することができる最小のリーフレベルのブロックサイズとして定義することができ、通常、４×４ピクセルである。
【００５６】
所定の最小寸法に等しい第１の寸法セットの一方又は双方を有するマクロブロック１２２のそれぞれについて、ステップ３０６に示すように、方法３００は終了し得る。
換言すれば、それらのマクロブロック１２２は、その最小のリーフレベルのブロックサイズに到達しているので、それ以上さらにサブブロックに分解され得ない。
一方、マクロブロック１２２は、方法４００（図４）に関して以下で示すように、さらに処理され得る。
【００５７】
所定の最小寸法に等しい第１の寸法セットの一方も双方も有しないマクロブロック１２２のそれぞれについて、コントローラ２０４は、エンコーダ１１２、より詳細には動き推定器２２６を起動又は実施して、マクロブロック１２２の動きベクトルを求めることができる。コントローラ２０４は、ステップ３０８に示すように、この動きベクトルをデコーダへ送出することができる。
【００５８】
加えて、ステップ３０８において、コントローラ２０４は、エンコーダ１１２、より詳細にはウェッジ区画器２２４を起動又は実施して、それらのマクロブロック１２２を２つのウェッジ１３０ａ、１３０ｂに区画することができる。
ウェッジ区画器２２４は、限られたスプライス（splice）のコードブックから最良のスライス線１２８を見つけて、マクロブロック１２２を２つのウェッジ１３０ａ、１３０ｂに分割することができる。
一例では、マクロブロック１２２をウェッジ１３０ａ、１３０ｂに区画する方法を求める際に、ウェッジ区画器２２４は、すべての可能なウェッジ１３０ａ、１３０ｂの組み合わせを評価して、どの組み合わせが大幅に最適化されたレート歪効率を与えるのかを判断することができる。
他の例では、ウェッジ区画器２２４は、上記で論述した最良の区画ストラテジーの高速検索方法の１つ又は複数を用いることができる。
【００５９】
別の例によれば、区画器２２４は、マクロブロック１２２を区画する際にバンド／ウェッジモデル（band and wedge model）を用いることができる。
画像が移動物体を含むとき、２つのケースが起こり得る。
ケース（１）：先行（基準）フレームから現フレームにおいてアンカバード背景（uncovered background）を有するブロック１２２〜１２６。
ケース（２）：先行（基準）フレームから現フレームにおいてアンカバード背景を有しないブロック。
【００６０】
ケース（１）では、たとえば、物体が左から右に移動している場合、これは、その物体の左エッジに位置するブロックについて当てはまる可能性がある。
この場合、区画器２２４は、バンドウェッジモデルを用いることができる。
バンド／ウェッジモデルのもとでは、２本の平行線が、ブロック１２２〜１２６を通る。
バンドの一方の側にある一方のウェッジ１３０ａは、相対的に小さな予測誤差を有する動きベクトル１３２を有する。
バンドの他方の側にあるウェッジ１３０ｂは、異なる動きベクトル１３２を有するが、相対的に小さな予測誤差も与える。
ウェッジ１３２ａ、１３２ｂ間のバンドは、アンカバード背景に対応するので、相対的に高い予測誤差を有する。
直線について上記で論述した極モデルを使用すると、バンドの平行線は、角度を固定し、中心からの距離のみを変更することによって取得され得る。
【００６１】
ケース（２）では、たとえば、物体が左から右に移動している場合、これは、その物体の右エッジに位置するブロックについて当てはまる可能性がある。
この場合、区画器２２４は、上記で論述したように、ブロック１２２〜１２６を２つのウェッジ１３０ａ、１３０ｂに区画することができる。
【００６２】
一例によれば、背景は、静止しているものと仮定することができる。
この例では、ケース１及びケース２におけるウェッジ１３０ａ、１３０ｂの１つは、ゼロ動きベクトルを有することができる。
したがって、ゼロ動きベクトルをチェックすることができ、ブロック１２２〜１２６の残差をしきい値と比較することができる。
誤差が、所望のエンコーディング品質と比較してゼロである十分大きなウェッジ１３０ａ、１３０ｂが存在する場合、ケース（１）又はケース（２）を保持していると仮定することができる。
加えて、最良の動きベクトルを求めてブロックの残りの部分を検索することができる。
最良の動きベクトルが一旦見つかると、誤差パターンをさらにチェックして、平行線を越えた箇所では誤差が小さくなる当該平行線を識別することができるか否かを判断することができる。
その上、ケース（１）を実行することができ、非ゼロ動きベクトルのウェッジ１３０ａ、１３０ｂのみの動きベクトルを送出することができ、バンドを符号化することができる。
一方、平行線を識別できない場合、ケース（２）を実行することができ、非ゼロ動きベクトルを有するウェッジ１３０ａ、１３０ｂを符号化して送出することができる。
【００６３】
さらなる例によれば、ゼロ動きベクトルの検索による第１の線区間が知られている場合、検索されるあらゆる候補動きベクトルについて、ウェッジ区画器２２４は、スライス線１２８に垂直な線上への投影の符号に注意することによって、その動きベクトルがケース（１）に属すべきか又はケース（２）に属すべきかを判断することができ、また、ケース（１）の場合には、平行線が幾何学的形状によって含まれるべきであり、その線の周りのみを検索することができる。
この例は、ウェッジ１３０ａ、１３０ｂを検索する際の複雑度をより良く減少させるために実行されうる。
【００６４】
加えて、ステップ３０８において、コントローラ２０４は、エンコーダ１１２、より詳細にはブロック分割器２２２を起動又は実施して、マクロブロック１２２を、第２の寸法セットを有する４つのサブブロック１２４に分割することができる。
換言すれば、Ｎ×Ｎマクロブロック１２２を、Ｎ／２×Ｎ／２寸法を有するように分割することができる。
加えて、ステップ３０４〜３０８をサブブロック１２４について繰り返すことができる。
【００６５】
次に図３Ｂ及び図３Ｃを参照して、一例による、ビデオシーケンスフレームを分解する方法３５０のフロー図が一括して示されている。方法３５０が、一般化された実例を表していること、及び、方法３５０の範囲から逸脱することなく、他のステップが追加され、既存のステップが除去、変更、又は再配列され得ることは、当業者には明らかなはずである。
【００６６】
方法３５０は、図３Ａの方法３００に関して上述したステップの多くを含んでいる。
したがって、それらのステップは、図３Ｂのステップ３０２〜３０８に関して本明細書では詳細に論述されない。
【００６７】
いずれにしても、ステップ３０８において、コントローラ２０４は、エンコーダ１１２、より詳細には動き推定器２２６及び誤差計算機２２８を起動又は実施して、ウェッジ１３０ａ、１３０ｂの最良の予測判断材料を求めることができる。
より詳細には、たとえば、動き推定器２２６は、インター予測判断材料（inter-predictor）を用いて、基準フレームに基づきウェッジ１３０ａ、１３０ｂのそれぞれの動きベクトルを求めることができる。
加えて又は代替的に、動き推定器２２６は、イントラ予測判断材料（intra-predictor）を用いて、近傍ブロックの選択されたピクセルに基づき動きベクトルを求めることもできる。
【００６８】
誤差計算機２２８は、インター予測判断材料及びイントラ予測判断材料の双方によって予測された動きベクトルの残差を計算することができ、動きベクトルのいずれが最小の残差を有するのかを判断することができる。
したがって、ステップ３０８において、一例によれば、最良のウェッジ１３０ａ、１３０ｂは、最小の残差を与える組み合わせを含むことができる。
別の例によれば、最良のウェッジ１３０ａ、１３０ｂは、大幅に最適化されたレート歪効率を与えるウェッジ１３０ａ、１３０ｂの組み合わせを含むことができる。
【００６９】
加えて、ステップ３０８において、コントローラ２０４は、エンコーダ１１２、より詳細には動き推定器２２６及び誤差計算機２２８を起動又は実施して、サブブロック１２４の最良の予測判断材料を求めることができる。
より詳細には、たとえば、動き推定器２２６は、インター予測判断材料を用いて、基準フレームに基づきサブブロック１２４のそれぞれの動きベクトルを求めることができる。
加えて又は代替的に、動き推定器２２６は、イントラ予測判断材料を用いて、近傍ブロックの選択されたピクセルに基づき動きベクトルを求めることもできる。
【００７０】
誤差計算機２２８は、インター予測判断材料及びイントラ予測判断材料の双方によって予測された動きベクトルの残差を計算することができ、動きベクトルのいずれが最小の残差を有するのかを判断することができる。
別の例によれば、誤差計算機２２８は、動きベクトルのいずれが、大幅に最適化されたレート歪効率に関連付けられているのかに基づいて、この計算を行うことができる。
【００７１】
ブロック分割器２２２及びウェッジ区画器２２４は、インター予測判断材料及びイントラ予測判断材料の一方又は双方を用いて、ウェッジ１３０ａ、１３０ｂ及びサブブロック１２４を予測することができる。
加えて、エンコーダ１１２は、異なるインター予測判断材料及びイントラ予測判断材料を実施して、ウェッジ１３０ａ、１３０ｂ及びサブブロック１２４を予測することもできる。
例として、エンコーダ１１２は、複数のインター予測判断材料及びイントラ予測判断材料を実施することができ、ウェッジ１３０ａ、１３０ｂ及びサブブロック１２４のそれぞれについての最良のものを選択することができる。
ウェッジ１３０ａ、１３０ｂ及びサブブロック１２４のそれぞれについての最良の予測判断材料には、たとえば、最小の残差又は最良のレート歪効率をもたらす予測判断材料が含まれ得る。
【００７２】
したがって、ステップ３０８において、その第１の寸法セットが所定の最小寸法を超えるマクロブロック１２２は、ウェッジ１３０ａ、１３０ｂへの区画及びサブブロック１２４への分割の双方が行われる。
加えて、マクロブロック１２２のそれぞれについての動きベクトルは、その動きベクトルの残差又はレート歪効率と共に求められる。
ステップ３１０において、コントローラ２０４は、エンコーダ１１２を起動又は実施して、マクロブロック１２２の動きベクトルのレート歪効率（ＲＤａ）、ウェッジに区画されたマクロブロック１２２の動きベクトルのレート歪効率（ＲＤｂ）、及びサブブロック１２４の動きベクトルのレート歪効率（ＲＤｃ）を計算することができる。
例として、これらのレート歪効率は、
（５）  Ｊ（ｐ）＝Ｄ（ｐ）＋λＲ（ｐ）
によって計算することができる。
【００７３】
式（５）において、ｐは、全体的なマクロブロック区画ストラテジーを指す一方、Ｒ（ｐ）は、ウェッジ１３０ａ、１３０ｂ、動きベクトル及び残差の搬送において取得されるレートを指す。
換言すれば、Ｒ（ｐ）は、搬送される１つのマクロブロック１２２当たりのビットを指す。
Ｄ（ｐ）は、区画ストラテジーｐに対応する歪（たとえば、平均二乗誤差（ＭＳＥ）、差分絶対値和（ＳＡＤ）等）である。
加えて、λは、ラグランジュ乗数である。ラグランジュ乗数は、レートと歪との間のトレードオフファクタとして定義することができる。
【００７４】
圧縮のため、エンコーダ１１２は、ビデオフレームを分解する際にどのマクロブロック区画ストラテジーが使用されたのかをデコーダに通知する。
Ｂ（ｐ）が、ｐをエンコーディングするのに費やされたビット数であると仮定し、Ｖ（ｐ）が、区画ストラテジーｐに関連付けられる動きベクトル１３２及び区画ストラテジーｐに関連付けられる残差補償Ｒres（ｐ）をエンコーディングするのに費やされたビット数であると仮定すると、Ｒ（ｐ）は、
（６）  Ｒ（ｐ）＝Ｖ（ｐ）＋Ｂ（ｐ）＋Ｒres（ｐ）
として定義することができる。
【００７５】
一般的に言えば、残差Ｒres（ｐ）は、従来の変換ベースの符号化で圧縮され得る。
さらに、固定された量子化行列について、歪Ｄは、区画ストラテジーｐと共に変化することはあまりない。
したがって、Ｄを一定とみなすと、次のコスト（cost）が取得される。
（７）  Ｊ（ｐ）＝Ｒ（ｐ）
【００７６】
ステップ３１２において、コントローラ２０４は、エンコーダ１１２を実施又は起動して、レート歪効率（ＲＤａ）、（ＲＤｂ）及び（ＲＤｃ）を比較し、レート歪効率を大幅に最適化することができる。
レート歪効率（ＲＤａ）が最良であると判断された場合、ステップ３１４に示すように、コントローラ２０４は、マクロブロック１２２の動きベクトルを符号化して送出することができ、ステップ３０６に示すように、方法３５０は終了し得る。
一方、レート歪効率（ＲＤｂ）が最良であるとコントローラ２０４が判断した場合、ステップ３１６に示すように、コントローラ２０４は、マクロブロック１２２をウェッジ１３０ａ、１３０ｂに区画することを選択することができる。
加えて、ウェッジ１３０ａ、１３０ｂに区画されたそれらのマクロブロック１２２について、ステップ３０６に示すように、方法３００は終了し得、図４に関して以下の本明細書で論述するように、それらのマクロブロック１２２はさらに処理され得る。
【００７７】
加えて、レート歪効率（ＲＤｃ）が最良であると判断された場合、ステップ３１８に示すように、コントローラ２０４は、マクロブロック１２２をサブブロック１２４に分割することを選択することができる。
加えて、ステップ３２０において、コントローラ２０４は、エンコーダ１１２を再び起動又は実施して、サブブロック１２４の寸法が所定の最小寸法（Ｎｓ）に等しいか否かを判断することができる。
所定の最小寸法に等しい第２の寸法セットの一方又は双方を有するサブブロック１２４のそれぞれについて、ステップ３０６に示すように、方法３５０は終了し得る。
【００７８】
図３Ｃに示すように、所定の最小寸法に等しい第２の寸法セットの一方も双方も有しないサブブロック１２４のそれぞれについて、コントローラ２０４は、エンコーダ１１２、より詳細には動き推定器２２６を起動又は実施して、ステップ３２２に示すように、Ｎ／２×Ｎ／２サブブロック１２４の動きベクトルを求めることができ、コントローラ２０４は、それらの動きベクトルをデコーダへ送出することができる。
【００７９】
加えて、ステップ３２２において、コントローラ２０４は、エンコーダ１１２、より詳細にはウェッジ区画器２２４を起動又は実施して、それらのサブブロック１２４を２つのウェッジ１３０ａ、１３０ｂに区画することができる。
加えて、ステップ３２２において、コントローラ２０４は、エンコーダ１１２、より詳細にはブロック分割器２２２を起動又は実施して、サブブロック１２４を、第３の寸法セットを有するさらなる４つのサブブロック１２６に分割することができる。
換言すれば、Ｎ／２×Ｎ／２サブブロック１２４を、Ｎ／４×Ｎ／４寸法を有するように分割することができる。
【００８０】
したがって、ステップ３２２において、その第２の寸法セットが所定の最小寸法を超えるサブブロック１２４は、ステップ３０８に関して上記で論述したような方法で、ウェッジ１３０ａ、１３０ｂへの区画及びさらなるサブブロック１２６への分割の双方が行われる。
ステップ３２４において、コントローラ２０４は、エンコーダ１１２を起動又は実施して、ステップ３１０に関して上述した方法と同様の方法で、サブブロック１２４の動きベクトルのレート歪効率（ＲＤｃ）、ウェッジに区画されたサブブロック１２４の動きベクトルのレート歪効率（ＲＤｄ）、及びさらなるサブブロック１２６の動きベクトルのレート歪効率（ＲＤｅ）を計算することができる。
【００８１】
ステップ３２６において、コントローラ２０４は、エンコーダ１１２を実施又は起動して、レート歪効率（ＲＤｃ）、（ＲＤｄ）、及び（ＲＤｅ）を比較することができる。
レート歪効率（ＲＤｃ）が最良であると判断された場合、ステップ３２８に示すように、コントローラ２０４は、サブブロック１２４の動きベクトルを符号化して送出することができる。
一方、レート歪効率（ＲＤｄ）が最良であると判断された場合、ステップ３３０に示すように、コントローラ２０４は、サブブロック１２４をウェッジ１３０ａ、１３０ｂに区画することを選択することができる。
加えて、ウェッジ１３０ａ、１３０ｂに区画されたそれらのサブブロック１２４について、ステップ３０６に示すように、方法３５０は終了し得る。
【００８２】
レート歪効率（ＲＤｅ）が最良であると判断された場合、ステップ３３２に示すように、コントローラ２０４は、サブブロック１２４をさらなるサブブロック１２６に分割することを選択することができる。
加えて、ステップ３３４において、コントローラ２０４は、エンコーダ１１２を再び起動又は実施して、さらなるサブブロック１２６の寸法が所定の最小寸法（Ｎｓ）に等しいか否かを判断することができる。
所定の最小寸法に等しい第２の寸法セットの一方又は双方を有するさらなるサブブロック１２６のそれぞれについて、ステップ３０６に示すように、方法３５０は終了し得る。
【００８３】
一方、所定の最小寸法に等しい第２の寸法セットの一方も双方も有さないさらなるサブブロック１２６のそれぞれについて、ステップ３２２〜３３４を繰り返すことができる。
加えて、ブロック１２２〜１２６のすべてが最小のリーフレベルのブロックサイズに到達するか又はウェッジ１３０ａ、１３０ｂに区画されるまで、ステップ３２２〜３３４を繰り返すことができる。
【００８４】
ビデオシーケンスフレームに対する方法３５０の実施を通じて、フレームのレート歪効率を大幅に最適化する構成を有するブロック１２２〜１２６及びウェッジ１３０ａ、１３０ｂを含むように、そのフレームを分解することができる。
【００８５】
加えて、図４に示すように、コントローラ２０４は、複数の分解されたビデオシーケンスフレームをさらに処理して、分解されたビデオシーケンスフレームを出力に適したものとすることができる。
【００８６】
図４は、一例による、分解されたビデオシーケンスフレームを処理する方法４００のフロー図をより詳細に示している。
方法４００が一般化された実例を表していること、及び、方法４００の範囲から逸脱することなく、他のステップが追加され、既存のステップが除去、変更、又は再配列され得ることは、当業者には明らかなはずである。
【００８７】
ステップ４０２において、コントローラ２０４は、エンコーダ１１２を起動又は実施して、ステップ３０８及び３２０において計算された動きベクトル１３２及び予測誤差等の残差を符号化することができる。
ブロック１２２〜１２６及びウェッジ１３０ａ、１３０ｂの動きベクトル１３２は、適切な変換の使用によって符号化することができる。
ブロック１２２〜１２６の残差は、正方形ブロック変換（square block transform）の計算によって符号化され得、係数が与えられる。
【００８８】
一方、ウェッジ１３０ａ、１３０ｂについては、２つの異なるオプションのもとで、残差を符号化することができる。
第１のオプションのもとでは、単一のブロック１２２〜１２６のウェッジ１３０ａ、１３０ｂに関連付けられる残差を正方形ブロックに結合することができ、単一ブロック変換を計算することができる。
第２のオプションのもとでは、たとえば、形状適応型ＤＣＴといった別個の形状適応型変換を各残差について計算することができる。
どのオプションを実施するのかの選択も、レート歪効率最適化方式に基づき得る。
換言すれば、コントローラ２０４は、最良のレート歪効率を与えるオプションを実施することができる。
【００８９】
ブロック１２２〜１２６のウェッジ１３０ａ、１３０ｂの１つが、所望の品質と比較してゼロ予測誤差を有する場合に、形状適応型ＤＣＴ等のさまざまな既知の形状適応型変換が提案されてきた。
これらの場合に、既知の形状適応型変換の１つを使用して、ゼロ予測誤差を有しないウェッジ１３０ａ、１３０ｂの残差を符号化することができる。
別の例として、ゼロ予測誤差を有しないウェッジ１３０ａ、１３０ｂのピクセルを、充填アルゴリズムによって充填することができ、次いで、標準のブロックとして符号化することができる。
適切な充填アルゴリズムの一例は、ウェッジ１３０ａ、１３０ｂの無関係のピクセルが、関係のあるピクセルの平均で充填されるアルゴリズムである。
【００９０】
ステップ４０４において、コントローラ２０４は、量子化器１１４を起動又は実施して、任意の合理的に適切な量子化技法によって、符号化された動きベクトル及び符号化された残差を量子化することができる。
加えて、ステップ４０６において、コントローラ２０４は、エントロピー符号化器１１６を起動又は実施して、たとえば、符号長を量子化された動きベクトル符号及び残差符号の確率と一致させるために、任意の合理的に適切な符号化技法によって、量子化された動きベクトル符号及び残差符号に符号を割り当てることができる。
【００９１】
ステップ４０８に示すように、コントローラ２０４は、オプションとして、符号化されたビデオフレーム１１８を１つ又は複数の出力デバイスに出力することができる。
ウェッジ１３０ａ、１３０ｂを有するブロック１２２〜１２６について、ウェッジ１３０ａ、１３０ｂの１つがゼロ動きベクトルを有する場合、コントローラ２０４は、どのウェッジ１３０ａ、１３０ｂがゼロ動きベクトルを有し、どのウェッジ１３０ａ、１３０ｂが非ゼロ動きベクトルを有するのかを示す１ビットを送信することができ、２つの動きベクトルの代わりに単一の動きベクトルを送出することができる。
【００９２】
次に図５を参照して、一例による、ブロック１２２〜１２６を符号化する方法５００のフロー図が示されている。
方法５００が一般化された実例を表していること、及び、方法５００の範囲から逸脱することなく、他のステップが追加され、既存のステップが除去、変更、又は再配列され得ることが、当業者には明らかなはずである。
【００９３】
方法５００の説明は、図２に示すブロック図２００を参照して行われ、したがって、図２で引用された要素を参照する。
しかしながら、方法５００は、ブロック図２００で述べた要素に限定されるものではないことが理解されるべきである。それどころか、方法５００は、ブロック図２００で述べたものとは異なる構成を有するシステムによって実施され得ることが理解されるべきである。
【００９４】
一般的に言えば、方法３５０と同様に、方法５００を実施して、さまざまな状況でウェッジ１３０ａ、１３０ｂを含むように動き推定モデルを拡張することができ、それによって、ビデオコーデックのレート歪効率を向上させることができる。
【００９５】
図５に示すように、ビデオ符号化システム１０２は、Ｎ×Ｎブロック１２２〜１２６を受信することができる。
ステップ５０２において、コントローラ２０４は、エンコーダ１１２、より詳細には動き推定器２２６及び誤差計算機２２８を起動又は実施して、Ｎ×Ｎブロック１２２〜１２６の最良の予測判断材料を求めることができる。
より詳細には、たとえば、動き推定器２２６は、インター予測判断材料を用いて、基準フレームに基づきＮ×Ｎブロック１２２〜１２６の動きベクトルを求めることができる。
加えて又は代替的に、動き推定器２２６は、イントラ予測判断材料を用いて、近傍ブロックの選択されたピクセルに基づき動きベクトルを求めることもできる。
誤差計算機２２８は、インター予測判断材料及びイントラ予測判断材料の双方によって予測された動きベクトルの残差を計算することができ、動きベクトルのいずれが最小の残差を有するのかを判断することができる。
したがって、ステップ５０２において、一例によれば、最良の予測判断材料は、最小の残差を与える予測判断材料を含むことができる。
別の例によれば、最良の予測判断材料は、大幅に最適化されたレート歪効率を与える予測判断材料を含み得る。
【００９６】
ステップ５０４において、コントローラ２０４は、エンコーダ１１２を起動又は実施して、Ｎ×Ｎブロック１２２〜１２６の寸法の一方又は双方が所定の最小寸法（Ｎｓ）に等しいか否かを判断することができる。
上記で論述したように、所定の最小寸法は、エンコーダ１１２がブロック１２２〜１２６を分解することができる最小のリーフレベルのブロックサイズの寸法として定義され得、通常、４×４ピクセルである。
【００９７】
ステップ５０６において、Ｎ×Ｎブロック１２２〜１２６の第１の寸法セットの一方又は双方が所定の最小寸法（Ｎｓ）に等しい場合、方法４００（図４）に示すように、Ｎ×Ｎブロックの動きベクトル及び残差を符号化し、量子化し、エントロピー符号化することができる。
【００９８】
一方、寸法のいずれもが所定の最小寸法（Ｎｓ）に等しくない場合、ステップ５０８に示すように、コントローラ２０４は、ステップ５０２において求められた残差を第１のしきい値（Ｔ１）と比較することができる。
この第１のしきい値（Ｔ１）は、一般に、動きベクトル予測について求められる所定の品質レベルとして定義され得、たとえば、残差のどのレベルが許容可能であるのかを示すトレーニングデータに基づくことができる。
加えて、第１のしきい値（Ｔ１）は、ブロック１２２〜１２６のサイズが異なれば変化し得る。
【００９９】
残差が第１のしきい値（Ｔ１）未満である場合、ステップ５０６を実行することができる。
したがって、方法４００（図４）に示すように、Ｎ×Ｎブロックの動きベクトル及び残差を符号化し、量子化し、エントロピー符号化することができる。
【０１００】
一方、残差が第１のしきい値（Ｔ１）よりも大きい場合、ステップ５１０に示すように、コントローラ２０４は、エンコーダ１１２、より詳細にはウェッジ区画器２２４を起動又は実施して、Ｎ×Ｎブロック１２２〜１２６を２つのウェッジ１３０ａ、１３０ｂに区画することができる。
ステップ３０８（図３Ａ）に関して上述したように、ウェッジ区画器２２４は、限られたスプライスのコードブックから最良のスライス線１２８を見つけて、Ｎ×Ｎブロック１２２〜１２６を２つのウェッジ１３０ａ、１３０ｂに分割することができる。
Ｎ×Ｎブロック１２２〜１２６をウェッジ１３０ａ、１３０ｂに区画する際に、ステップ５１２に示すように、コントローラ２０４は、エンコーダ１１２、より詳細には動き推定器２２６及び誤差計算機２２８を起動又は実施して、ウェッジ１３０ａ、１３０ｂの最良の予測判断材料を求めることができる。
【０１０１】
より詳細には、たとえば、動き推定器２２６は、インター予測判断材料を用いて、基準フレームに基づきウェッジ１３０ａ、１３０ｂのそれぞれの動きベクトルを求めることができる。
加えて又は代替的に、動き推定器２２６は、イントラ予測判断材料を用いて、近傍ブロックの選択されたピクセルに基づき動きベクトルを求めることもできる。
【０１０２】
誤差計算機２２８は、インター予測判断材料及びイントラ予測判断材料の双方によって予測された動きベクトルの残差を計算することができ、動きベクトルのいずれが最小の残差を有するのかを判断することができる。
したがって、ステップ５１２において、一例によれば、最良のウェッジ１３０ａ、１３０ｂは、最小の残差を与えるウェッジ１３０ａ、１３０ｂの組み合わせを含み得る。
別の例によれば、最良の予測判断材料は、大幅に最適化されたレート歪効率を与えるウェッジ１３０ａ、１３０ｂの組み合わせを含むことができる。
【０１０３】
ステップ５１４において、コントローラ２０４は、ステップ５１２において求められた残差を第２のしきい値（Ｔ２）と比較することができる。この第２のしきい値（Ｔ２）は、第１のしきい値（Ｔ１）と異なり得る。
第２のしきい値（Ｔ２）は、一般に、動きベクトル予測について求められる所定の品質レベルとして定義され得、たとえば、残差のどのレベルが許容可能であるのかを示すトレーニングデータに基づき得る。
加えて、第２のしきい値（Ｔ２）は、ブロック１２２〜１２６のサイズが異なれば変化し得る。
【０１０４】
残差が第２のしきい値（Ｔ２）未満である場合、ステップ５０６を実行することができ、それによって、方法４００（図４）に示すように、ウェッジ１３０ａ、１３０ｂの動きベクトル及び残差を符号化することができる。
【０１０５】
一方、残差が第２のしきい値（Ｔ２）よりも大きい場合、ステップ５１６に示すように、コントローラ２０４は、エンコーダ１１２、より詳細にはブロック分割器２２２を起動又は実施して、Ｎ×Ｎブロック１２２を、第２の寸法セットを有する４つのサブブロック１２４に分割することができる。
換言すれば、Ｎ×Ｎブロック１２２を、Ｎ／２×Ｎ／２寸法を有するように分割することができる。
【０１０６】
ブロック１２２又はそのサブブロック１２４、１２６がステップ５０６においてすべて符号化されるまで、ステップ５０２〜５１６を繰り返すことができる。
加えて、方法５００も、残っているブロック１２２〜１２６があれば、そのブロックについて繰り返すことができる。
【０１０７】
次に図６を参照して、別の例による、ブロック１２２〜１２６を符号化する方法６００のフロー図が示されている。
方法６００が一般化された実例を表していること、及び、方法６００の範囲から逸脱することなく、他のステップを追加され、既存のステップが除去、変更、又は再配列され得ることは、当業者には明らかなはずである。
【０１０８】
方法６００の説明は、図２に示すブロック図２００を参照して行われ、したがって、図２で引用された要素を参照する。
しかしながら、方法６００は、ブロック図２００で述べた要素に限定されるものではないことが理解されるべきである。
それどころか、方法６００は、ブロック図２００で述べたものとは異なる構成を有するシステムによって実施され得ることが理解されるべきである。
【０１０９】
一般的に言えば、方法５００と同様に、方法６００を実施して、さまざまな状況でウェッジ１３０ａ、１３０ｂを含むように動き推定モデルを拡張することができ、それによって、ビデオコーデックのレート歪効率を向上させることができる。
【０１１０】
図６に示すように、ビデオ符号化システム１０２は、Ｎ×Ｎブロック１２２〜１２６を受信することができる。
図５のステップ５０２に関して上記で論述したように、ステップ６０２において、コントローラ２０４は、エンコーダ１２２、より詳細には動き推定器２２６及び誤差計算機２２８を起動又は実施して、Ｎ×Ｎブロック１２２〜１２６の最良の予測判断材料を求めることができる。
【０１１１】
図５のステップ５０４に関して上記で論述したように、ステップ６０４において、コントローラ２０４は、エンコーダ１１２を起動又は実施して、Ｎ×Ｎブロック１２２〜１２６の寸法の一方又は双方が所定の最小寸法（Ｎｓ）に等しいか否かを判断することができる。
加えて、ステップ６０６において、Ｎ×Ｎブロック１２２〜１２６の第１の寸法セットの一方又は双方が所定の最小寸法（Ｎｓ）に等しい場合、方法４００（図４）に示すように、Ｎ×Ｎブロックの動きベクトル及び残差を符号化し、量子化し、エントロピー符号化することができる。
【０１１２】
一方、寸法のいずれもが所定の最小寸法（Ｎｓ）に等しくない場合、ステップ６０８に示すように、コントローラ２０４は、エンコーダ１１２、より詳細にはウェッジ区画器２２４を起動又は実施して、Ｎ×Ｎブロック１２２〜１２６を２つのウェッジ１３０ａ、１３０ｂに区画することができる。
ウェッジ区画器２２４は、ステップ３０８（図３Ａ）及びステップ５１０（図５）に関して上述したように、限られたスプライスのコードブックから最良のスライス線１２８を見つけて、Ｎ×Ｎブロック１２２〜１２６を２つのウェッジ１３０ａ、１３０ｂに分割することができる。
Ｎ×Ｎブロック１２２〜１２６をウェッジ１３０ａ、１３０ｂに区画する際に、ステップ６１０に示すように、コントローラ２０４は、エンコーダ１１２、より詳細には動き推定器２２６及び誤差計算機２２８を起動又は実施して、ステップ５１２（図５）に関して上記で論述したように、ウェッジ１３０ａ、１３０ｂの最良の予測判断材料及び動きベクトルの残差を求めることができる。
【０１１３】
ステップ６１２において、コントローラ２０４は、エンコーダ１１２を起動又は実施して、ステップ６２０及びステップ６１０において見つけられた予測判断材料のいずれが全体的に最良の予測判断材料であるのかを判断することができる。
すなわち、コントローラ２０４は、予測判断材料のいずれが、最小の残差及び最大のレート歪効率の一方又は双方を与えるのかを判断することができる。
ウェッジ１３０ａ、１３０ｂに区画されたブロック１２２〜１２６は、通常、符号化される場合に、より多くのビット数を必要とするので、この比較を行う際に、コントローラ２０４は、ウェッジ１３０ａ、１３０ｂに対して行われた予測からもたらされる残差にペナルティファクタを追加することができる。
このペナルティファクタは、たとえば、トレーニングに基づくアドホックな方法で定義され得る。このアドホックな方法は、さまざまなペナルティファクタ及び関連付けられる残差の試験を通じて開発され得る。
【０１１４】
ステップ６１４において、コントローラ２０４は、ステップ６１２で求められた全体的に最良の予測判断材料からもたらされた残差を第３のしきい値（Ｔ３）と比較することができる。この第３のしきい値（Ｔ３）は、図５に関して論述した第１のしきい値（Ｔ１）及び第２のしきい値（Ｔ２）と異なり得る。
この第３のしきい値（Ｔ３）は、一般に、動きベクトル予測について求められる所定の品質レベルとして定義され得、たとえば、残差のどのレベルが許容可能であるのかを示すトレーニングデータに基づくことができる。
加えて、第３のしきい値（Ｔ３）は、ブロック１２２〜１２６のサイズが異なれば変化し得る。
【０１１５】
残差が第３のしきい値（Ｔ３）未満である場合、ステップ６０６を実行することができ、それによって、方法４００（図４）に示すように、ウェッジ１３０ａ、１３０ｂの動きベクトル及び残差を符号化することができる。
【０１１６】
一方、残差が第３のしきい値（Ｔ３）よりも大きい場合、ステップ６１６に示すように、コントローラ２０４は、エンコーダ１１２、より詳細にはブロック分割器２２２を起動又は実施して、Ｎ×Ｎブロック１２２を、第２の寸法セットを有する４つのサブブロック１２４に分割することができる。
換言すれば、Ｎ×Ｎブロック１２２を、Ｎ／２×Ｎ／２寸法を有するように分割することができる。
【０１１７】
ブロック１２２又はそのサブブロック１２４、１２６が、ステップ６０６においてすべて符号化されるまで、ステップ６０２〜６１６を繰り返すことができる。
加えて、方法６００も、残っているブロック１２２〜１２６があれば、そのブロックについて繰り返すことができる。
【０１１８】
方法３００、３５０、４００、５００、及び６００において例示された動作のいくつか又はすべてを、ユーティリティ、プログラム、又はサブプログラムとして、任意の所望のコンピュータアクセス可能媒体に収容することができる。
加えて、方法３００、３５０、４００、５００、及び６００は、コンピュータプログラムによって実施化することができ、コンピュータプログラムは、アクティブ及び非アクティブの双方のさまざまな形態で存在することができる。
たとえば、コンピュータプログラムは、ソースコード、オブジェクトコード、実行可能コード、又は他のフォーマットのプログラム命令で構成されるソフトウェアプログラム（複数可）として存在することができる。
上記のいずれも、コンピュータ可読媒体上で実施化することができ、コンピュータ可読媒体には、圧縮された形態又は圧縮されていない形態のストレージデバイス及び信号が含まれる。
【０１１９】
例示のコンピュータ可読ストレージデバイスには、従来のコンピュータシステムのＲＡＭ、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、及び磁気ディスク若しくは磁気テープ又は光ディスク若しくは光テープが含まれる。
例示のコンピュータ可読信号は、搬送波を使用して変調されているかを問わず、インターネット又は他のネットワークを通じてダウンロードされた信号を含めて、コンピュータプログラムをホスティング又は実行するコンピュータシステムがアクセスするように構成可能な信号である。
上記の具体例には、ＣＤ  ＲＯＭ上のプログラムの配布又はインターネットのダウンロードを介したプログラムの配布が含まれる。
或る意味では、インターネット自体、抽象的なエンティティとして、コンピュータ可読媒体である。
同じことは、一般のコンピュータネットワークにも当てはまる。
したがって、上述した機能を実行することができるどの電子デバイスも、上記に列挙された機能を実行することができることが理解されるべきである。
【０１２０】
本明細書で説明及び図示されたものは、その変形のいくつかと共に本発明の好ましい実施形態である。
本明細書で使用された用語、説明、及び図は、単に例示として述べられたものであり、限定を意図するものではない。
本発明の範囲内で多くの変形が可能であることを当業者は認識するであろう。本発明の範囲は、以下の特許請求の範囲及びその均等物によって画定されるように意図されている。特許請求の範囲において、すべての用語は、別段の指定がない限り、その最も広い合理的な意味が意図されている。
【符号の説明】
【０１２１】
１０２  ビデオ符号化システム
１１０  ビデオソース
１１２  エンコーダ
１１４  量子化器
１１６  エントロピー符号化器
１１８  符号化されたビデオ
２０４  コントローラ
２０６  システムバス
２０８  入力デバイス
２１０  インターフェース
２１２  メモリ
２１４  オペレーティングシステム
２１６  アプリケーション
２１８  プログラムデータ
２２０  フレーム分解器
２２２  ブロック分割器
２２４  ウェッジ区画器
２２６  動き推定器
２２８  誤差計算機
２３２  アダプタ
【図１Ａ】
2010508706.tif 000007
【図１Ｂ】
2010508706.tif 000008
【図１Ｃ】
2010508706.tif 000009
【図１Ｄ】
2010508706.tif 000010
【図２】
2010508706.tif 000011
【図３Ａ】
2010508706.tif 000012
【図３Ｂ】
2010508706.tif 000013
【図３Ｃ】
2010508706.tif 000014
【図４】
2010508706.tif 000015
【図５】
2010508706.tif 000016
【図６】
2010508706.tif 000017
【国際調査報告】
2010508706.tif 000018
2010508706.tif 000019