"ビデオピクチャ内の、複数のサブブロックを含む画素ブロックを符号化する方法であって、前記ブロックの各サブブロック毎に、予測モードを用いて、当該サブブロックのオリジナル画素値と前記ブロックの境界の画素のセットから導出される前記サブブロックの予測値のセットとの差分に基づく歪み値を算出するステップと、全サブブロックの歪み値の全てが所定の歪み閾値を満たす場合、前記予測モードを用いて前記ブロックを符号化するステップとを有することを特徴とする方法。前記予測モードを第1の予測モード、前記歪み値を第1の歪み値、前記予測値のセットを第1の予測値セットとしたとき、前記方法は、前記第1の歪みの全てが、前記所定の歪み閾値を満たさない場合には、第2の予測モードを、前記各サブブロック毎の第2の歪み値を算出するために使用するステップと、前記ブロックの全サブブロックの前記第2の歪み値が前記所定の歪み閾値を満たす場合、前記第2の予測モードを用いて前記ブロックを符号化するステップとを更に有することを特徴とする請求項1に記載の方法。前記第2の歪み値の全てが前記所定の歪み閾値を満たさない場合に、第3の予測モードを用いて前記ブロックを符号化することを特徴とする請求項2に記載の方法。前記第3の予測モードは、前記第2の予測モードで特定されるパーティションサイズよりも小さいサイズの前記ブロックのパーティションサイズを特定することを特徴とする請求項3に記載の方法。前記境界の画素のセットは、水平、垂直方向の配列されたサブブロックにおける前記ブロックの境界上の画素であることを特徴とする請求項1に記載の方法。予測モードを用いて、各サブブロックの歪み値を算出する前記ステップは、予測モードに基づき前記ブロックの境界の画素のセットを識別するステップと、前記ブロックの識別された境界の画素を用いることで、前記サブブロックの歪み値のセットを導出するステップと、前記サブブロックのオリジナルの画素値と前記サブブロックについて導出した予測値のセットとの差分に基づき歪み値を計算するステップとを有することを請求項1に記載の方法。前記予測モードで識別される境界の画素のセットは、前記ブロックの左端列の画素を含むことを特徴とする請求項6に記載の方法。前記予測モードで識別される境界の画素のセットは、前記ブロックの上端行の画素を含むことを特徴とする請求項6に記載の方法。前記予測値は前記予測モードで識別される境界の画素のセットの平均値から導出されることを特徴とする請求項6に記載の方法。前記画素ブロックは16×16画素であり、当該ブロックの各サブブロックは4×4画素であることを特徴とする請求項1に記載の方法。前記ビデオイメージの画素セットを符号化する方法であって、複数の符号化モードから異なる符号化モード間の関係に基づき、前記複数の符号化モードから符号化モードセットを識別するステップと、ここで、前記複数の符号化モードの各々は前記ビデオ画像中の前記画素セットに隣接する複数の画素を参照するイントラ予測符号化モードである;前記符号化モードのセットの各々に関連するコスト値を演算するステップと、前記符号化モードセットにおける演算された最も低いコストを持つ第1の符号化モードを識別するステップと、前記符号化モードセットにおける2番目に低いコストを持つ第2の符号化モードを識別するステップと、前記複数のモードの中の他の符号化モードよりも、前記第1,第2の符号化モードと最も近い位置関係を持つ第3の符号化モードを識別するステップと、前記第3の符号化モードに関連するコスト値を演算するステップと、前記第1の符号化モード、前記第2の符号化モード、前記第3の符号化モードの中の最も低いコストを持つ符号化モードを選択するステップと、選択した最も低いコストを持つ符号化モードを用いて前記ビデオ画像の前記画素セットを符号化するステップとを有することを特徴とする方法。前記符号化モードセットは4×4配列のためのH.264codec標準の下で特定される9個の予測モード間の位置関係に基づいて識別されることを特徴とする請求項11に記載の方法。前記異なる符号化モード間の関係は、前記異なる符号化モードに関連する異なる予測アレイ間の位置及び論理関係によって定義されることを特徴とする請求項11に記載の方法。前記特定の符号化モードに関連する特定のコスト値は、前記特定の符号化モードを用いた画素セットの符号化するための歪みコスト値であることを特徴とする請求項11に記載の方法。前記符号化モードのセットは、DC符号化モードを含み、前記方法は、前記DC符号化モードが前記符号化モードセットにおける最も低いコスト値を持つ符号化モードである場合、前記DC符号化モードを用いて符号化するステップを更に有することを特徴とする請求項11に記載の方法。少なくとも1つのプロセッサによって実行され、請求項1乃至15のいずれか1項に記載のステップを実行する命令セットを有するコンピュータプログラムを格納したコンピュータ可読記憶媒体。請求項1乃至15のいずれか1項に記載のステップを実行する手段を有するコンピュータシステム。しかし、従来のアプローチは、他に4×4予測モードの9×16個の異なる組合わせに対するコストに、4つの16×16予測モードに対するコストを加算したものに対するコストを決定するステップを含む。ある実施形態の場合には、ビデオフレーム内のマクロブロックに対する符号化タイプ選択、および予測モード選択を決定するためのもっと効率的な方法を使用している。ある実施形態の場合には、一般的な方法は、1簡単に計算できるマクロブロックの属性に基づく符号化タイプ選択アルゴリズムにより、マクロブロックに対して最初に検討する符号化タイプ16×16または4×4を選択し、2ステップ1で16×16符号化タイプを選択した場合には、歪みしきい値に基づいて、従来の方法または改良した16×16予測モード探索アルゴリズムにより、マクロブロック上で使用することができる4つの16×16予測モードを検討し、3ステップ1で4×4符号化タイプを選択した場合には、予測モード間の位置関係に基づいて、従来の方法または改良した4×4予測モード探索アルゴリズムにより、マクロブロックの16個の各4×4ブロックに対して使用する4×4予測モードを選択する。2004年6月27日出願の画像の符号化および復号化EncodingandDecodingImagesという名称の米国仮出願第60/583,447号の内容は、参照により本明細書に明示的に組み込むものとする。以下の説明における、多数の詳細な点は説明のためのものである。しかし、通常の当業者であれば、本発明は、これらの特定の詳細な点を使用しなくても、実行することができることを理解することができるだろう。他の例の場合には、不必要な詳細な記述により、説明が分かりにくくならないように、周知の構造体およびデバイスをブロック図の形で示している。ある実施形態の場合には、ビデオフレーム内のマクロブロックに対する符号化タイプの選択および予測モードの選択を決定するためのもっと効率的な方法を使用している。ある実施形態の場合には、一般的な探索アルゴリズムは、下記の演算、すなわち、1符号化タイプ選択アルゴリズム簡単に計算できるマクロブロックの属性に基づくによる、マクロブロックに対して最初に検討する符号化タイプ16×16または4×4の選択。符号化タイプ選択アルゴリズムについては、I節で以下に説明する。2ステップ1で16×16符号化タイプを選択した場合の、歪みしきい値に基づいて、従来の方法または改良した16×16予測モード探索アルゴリズムによる、マクロブロック上で使用することができる4つの16×16予測モードの検討すなわち、試験。16×16予測モード探索アルゴリズムのある特定の状況の場合には、4×4符号化タイプの選択も行われることに留意されたい。このステップについては、II節で以下に説明する。3ステップ1で4×4符号化タイプを選択した場合の、予測モード間の位置関係に基づいて、従来の方法または改良した4×4予測モード探索アルゴリズムによる、マクロブロックの16個の各4×4ブロックに対して使用する4×4予測モードの選択を行うIII節で以下に説明する。探索アルゴリズムのステップ1において、符号化タイプ選択アルゴリズムが、最初の検討対象として16×16符号化タイプを選択した場合には、最終的に選択される符号化タイプは、16×16符号化タイプであっても、4×4符号化タイプであってもよいことに留意されたい。対照的に、符号化タイプ選択アルゴリズムが、最初の検討対象として4×4符号化タイプを選択した場合には、実際には、4×4符号化タイプが、マクロブロックに対する符号化タイプとして選択される。最初の検討対象として16×16符号化タイプを選択した場合には、マクロブロックに対する予測モードを決定するために、従来の方法または改良した16×16予測モード探索アルゴリズムが使用される。最初の検討対象として4×4符号化タイプを選択した場合には、マクロブロックに対する予測モードを決定するために、従来の方法または改良した4×4予測モード探索アルゴリズムが使用される。それ故、探索アルゴリズムにより最初の検討対象に対してどの符号化タイプを選択したかにより、予測モードを決定するために異なる探索アルゴリズム従来のまたは改良したが使用される。図1は、画素のマクロブロックに対する符号化タイプおよび予測モードを選択するための一般的な方法100のフローチャートである。ある実施形態の場合には、この一般的な方法100は、ビデオフレームを符号化するように構成されているソフトウェアおよび/またはハードウェアにより実行される。この方法は、画素のマクロブロックを受け取った時点でスタートする102において。ある実施形態の場合には、マクロブロックは、画素の16×16アレイであり、一方、他の実施形態の場合には、マクロブロックは異なるサイズの画素のアレイである。ある実施形態の場合には、マクロブロックは、4つの8×8のアレイに、または16個の4×4アレイに分割される。一方、他の実施形態の場合には、マクロブロックは、異なるサイズのブロック/アレイに分割される。次に、この方法は、符号化タイプ選択方法200により、マクロブロックに対して最初に検討する符号化タイプ16×16または4×4を選択する105において図2のところで以下に説明する。次に、この方法は、4×4符号化タイプを選択したかどうかを判断する110において。選択した場合には、この方法は、従来の方法、改良した4×4予測モード探索方法500により図5のところで以下に説明する、または他の4×4予測モード探索方法600により図6のところで以下に説明する、マクロブロックの16個の各4×4ブロックに対する予測モードを選択する115において。この方法が、4×4符号化タイプを選択しなかった場合には110-Noにおいて、この方法は、16×16予測モード図3のところで以下に説明するように、従来の方法または改良した16×16予測モード探索方法300により、または4×4符号化タイプを選択する120において。次に、この方法は、4×4符号化タイプを選択したかどうか120においてを決定する125において。選択した場合には、この方法は、ステップ115に進み、そこでマクロブロックの16個の各4×4ブロックに対する予測モードが選択される。この方法が、4×4符号化タイプを選択しなかったと判断した場合には125-Noにおいて、そのことは、特定の16×16予測モードが選択されたことを示す。ここでこの方法は終了する。I節:符号化タイプ選択アルゴリズムこの節においては、一般的探索アルゴリズムのステップ1の符号化タイプ選択アルゴリズムについて説明する。符号化タイプ選択アルゴリズムは、マクロブロックに対して最初に検討する符号化タイプ16×16または4×4を選択し、それによりマクロブロックに対してどの予測モード16×16モードまたは4×4モードを最初に検討するのかを決定する。符号化タイプ選択アルゴリズムは、簡単に決定することができるマクロブロックの属性を使用する。符号化タイプ選択アルゴリズムは、下記の演算を行う。1マクロブロックを4つの8×8ブロックに分割し、2各8×8ブロックの変化を計算し、所定のしきい値と比較する。例えば、所定のしきい値を、マクロブロックを含むフレーム内のすべての8×8ブロックの平均の変化に等しくセットすることができる。8×8ブロックの変化は、例えば、aブロック内のすべての画素値の平均を計算することにより、bブロック内の各画素を計算することにより:画素値-平均^2、cステップbのところで計算したすべての値を合計することにより、すなわち、ブロック内のすべての画素に対して測定したすべての値を合計することにより決定することができる。3所定のしきい値マクロブロックを16×16ブロック、または16個の4×4ブロックに符号化すべきかどうかを決定するために使用する属性である以下の変化を有するマクロブロック内の8×8ブロックの数を決定する。44つすべての8×8ブロックが所定のしきい値以下の変化を有している場合には、16×16符号化タイプが最初の検討対象として選択される。最初の検討対象として16×16符号化タイプが選択された場合には、最終的に選択される符号化タイプは、16×16符号化タイプであっても、4×4符号化タイプであってもよいことに留意されたい。マクロブロック上で使用する16×16予測モードは、従来の方法または改良した16×16予測モード探索アルゴリズムにより選択することができるII節のところで以下に説明する。54つの8×8ブロックの中のどれかが、所定のしきい値を超える変化を含んでいる場合には、4×4符号化タイプが選択される。それ故、次に、マクロブロックの16個の各4×4ブロック上で使用する4×4予測モードは、従来の方法または改良した4×4予測モード探索アルゴリズムにより決定されるIII節のところで以下に説明するように。符号化プロセスの量子化ステップで使用する量子化パラメータ値が、比較的高い場合には例えば、34を超える、符号化タイプ選択アルゴリズムの演算は、上記説明から若干ずれることに留意されたい。これらの実施形態の場合には、所定のしきい値は、量子化パラメータ値QPである係数によりスケーリングされるので、量子化パラメータ値が増大すると所定のしきい値が増大する。ある実施形態の場合には、スケーリング係数は1kQP-34という形のスケーリング式により計算される。ここで、kは定数である。他の実施形態の場合には、スケーリング係数は他のスケーリング式により決定される。次に、スケーリングしたしきい値を入手するために、所定のしきい値に所定のスケーリング係数が掛けられる。これらの実施形態の場合、4つの8×8ブロックの中のどれかがスケーリングしたしきい値を超える変化を有している場合には、マクロブロックは16個の4×4ブロックとして符号化される。この選択は、従来の方法または本発明の方法改良した4×4予測モード探索アルゴリズムのようなにより行うことができる。しかし、マクロブロックの4つのすべての8×8ブロックがスケーリングしたしきい値以下の変化を有している場合には、マクロブロックを16×16ブロックまたは16個の4×4ブロックとして符号化することができる。マクロブロック上で使用する16×16予測モードは、次に、従来の方法または改良した16×16予測モード探索アルゴリズムにより選択することができるII節のところで以下に説明する。4×4符号化タイプが選択した16×16予測モード上で選択された場合には、4×4予測モードを、従来の方法または本発明の方法改良した4×4予測モード探索アルゴリズムのようなにより選択することができる。図2は、画素のマクロブロックに対して符号化タイプを選択するための符号化タイプ選択方法200のフローチャートである。ある実施形態の場合には、この方法200は、ビデオフレームを符号化するように構成されているソフトウェアおよび/またはハードウェアにより実施される。ある実施形態の場合には、この符号化タイプ選択方法200は、図1のステップ105を含む。この方法200は、マクロブロックに対するしきい値の変化を測定する205においてことによりスタートする。ある実施形態の場合には、しきい値の変化は、マクロブロックを含んでいるフレーム内のすべての8×8ブロックの平均の変化に等しくセットされるすでに説明したように。他の実施形態の場合には、符号化プロセスの量子化ステップで使用する量子化パラメータ値が比較的高い場合には、決定したしきい値の変化は、量子化パラメータ値に従ってある係数によりスケーリングされるすでに説明したように。次に、この方法は、マクロブロックを4つの8×8ブロックに分割し210において、4つの各8×8ブロックに対する変化を測定する215において。次に、この方法は、4つのすべての8×8ブロックの変化が、しきい値の変化より小さいかどうかを判断する220において。小さい場合には、この方法は、マクロブロックに対して16×16符号化タイプを選択し225において、終了する。小さくない場合には、この方法は、マクロブロックに対して4×4符号化タイプを選択して230において、終了する。II節:16×16予測モード探索アルゴリズム一般的な探索アルゴリズムのステップ1の後で、最初に、検討対象として16×16符号化タイプが選択された場合には、16×16予測モードが試験される。この節においては、一般的な探索アルゴリズムのステップ2について説明する。H.264コーデック規格の場合には、DC、V垂直、H水平およびP平面から選択するために、4つの可能な16×16内部予測モードを使用することができる。ある実施形態の場合には、16×16予測モードを選択するために従来の方法を使用することができる例えば、4つの各16×16予測モードを決定し、コストが最も安いモードを選択することにより。他の実施形態の場合には、予測モードによる歪みに基づいて、マクロブロックに対する16×16予測モードを検討すなわち、試験するために、改良した16×16予測モード探索アルゴリズムを使用することができる。ある実施形態の場合には、16×16予測モード探索アルゴリズムは、今処理したマクロブロックに適用した場合に、特定の予測モードによる歪みを測定するために従来の方法を使用する。従来の方法の場合、この歪みは、1隣接する前に符号化したマクロブロックから画素値を検索することにより、2検索した画素値から新しい値を入手することにより、3入手した値により、今処理したマクロブロックに対する予測値を計算することにより、4今処理したマクロブロックの元の画素値と、計算した予測値との間の歪みを測定することにより決定される。しかし、従来の方法による歪みの測定は時間がかかる。他の実施形態の場合には、16×16予測モード探索アルゴリズムは、今処理したマクロブロックに適用した場合、特定の予測モードによる歪みを測定するためにより高速な推定方法を使用する。この推定方法は、特定の予測モードによる予測値の推定値エミュレーションを与え、推定した予測値の歪みを測定する。この推定方法の場合には、予測値は、境界のところで今処理したマクロブロックの画素値が、隣接するマクロブロックからの隣接する画素値に近いものと仮定して、今処理したマクロブロックからの画素値を使用して決定される。この推定方法を使用する歪みの測定は、もっと短い時間で行うことができる。何故なら、今処理したマクロブロックからの画素値は、他のマクロブロックからの画素値よりよく使用され、これにより検索時間が短縮するからである。この推定方法を使用すれば、精度をそんなに犠牲にしないで、歪み値を測定するのに必要な時間が有意に短縮する。ある実施形態の場合には、この推定方法のための疑似コードは下記の通りである。特定の予測モードの歪みを計算する方法が何であれ、16×16予測モード探索アルゴリズムは、下記の演算を行う。116×16DC予測モードを試験する。a16×16DC予測モードにより、マクロブロックの各4×4ブロック内で起きた歪みを測定する。b各4×4ブロック内の歪みが所定のしきい値より低い場合には、16×16DC予測モードがこのマクロブロックに対する予測モードとして選択され、16×16予測モード探索アルゴリズムは終了する。c任意の4×4ブロック内の歪みが所定のしきい値より大きい場合には、16×16予測モード探索アルゴリズムはステップ2に進む。216×16V予測モードを試験する。a16×16V予測モードにより、マクロブロックの各4×4ブロック内で起きた歪みを測定する。b各4×4ブロック内の歪みが所定のしきい値より低い場合には、16×16V予測モードがこのマクロブロックに対する予測モードとして選択され、16×16予測モード探索アルゴリズムは終了する。c任意の4×4ブロック内の歪みが所定のしきい値より大きい場合には、16×16予測モード探索アルゴリズムはステップ3に進む。316×16H予測モードを試験する。a16×16H予測モードによりマクロブロックの各4×4ブロック内で起きた歪みを測定する。b各4×4ブロック内の歪みが所定のしきい値より低い場合には、16×16H予測モードがこのマクロブロックに対する予測モードとして選択され、16×16予測モード探索アルゴリズムは終了する。c任意の4×4ブロック内の歪みが所定のしきい値より大きい場合には、16×16予測モード探索アルゴリズムは、16×16P予測モードおよび4×4符号化タイプを検討する。ある実施形態の場合には、2つの上記オプションの選択は、4×4予測モード探索アルゴリズムを使用することにより容易になるIII節のところで以下に説明する。他の実施形態の場合には、2つの上記オプション間の選択は、従来の方法により行うことができる例えば、16×16P予測モードおよび4×4符号化タイプを使用することにより最も低いコストを測定し、最も低いコストのオプションを選択することにより。図3は、画素の16×16マクロブロックの予測モードを選択するための16×16予測モード探索方法300のフローチャートである。ある実施形態の場合には、この方法300は、ビデオフレームを符号化するように構成されている、ソフトウェアおよび/またはハードウェアにより実施される。ある実施形態の場合には、この符号化タイプ選択方法300は、図1のステップ120を含む。ある実施形態の場合には、16×16予測モード探索方法は、特定の予測モードによるマクロブロック内の4×4ブロックの歪みを測定するために、従来の方法または改良した推定方法を使用するすでに説明したように。この方法300は、16×16DC予測モードによりマクロブロックの16個の各4×4ブロック内の歪みを測定する305においてことによりスタートする。次に、この方法は、16×16DC予測モードによるすべての4×4ブロック内の歪みが、所定のしきい値歪みより小さいかどうかを判断する310において。小さい場合には、16×16DC予測モードが、マクロブロックに対して予測モードとして選択され315において、この方法は終了する。この方法300が16×16DC予測モードによる任意の4×4ブロック内の歪みが所定のしきい値歪み以下でないと判断した場合には310-Noにおいて、この方法は、16×16V予測モードによるマクロブロックの16個の各4×4ブロック内の歪みを測定する320において。次に、この方法は、16×16V予測モードによるすべての4×4ブロック内の歪みが、所定のしきい値歪みより小さいかどうかを判断する325において。小さい場合には、16×16V予測モードがマクロブロックの予測モードとして選択され330において、この方法は終了する。この方法300が、16×16V予測モードによる任意の4×4ブロック内の歪みが所定のしきい値歪み以下でないと判断した場合には325-Noにおいて、この方法は、16×16H予測モードによるマクロブロックの16個の各4×4ブロック内の歪みを測定する335において。次に、この方法は、16×16H予測モードによるすべての4×4ブロック内の歪みが、所定のしきい値歪みより小さいかどうかを判断する340において。小さい場合には、16×16H予測モードがマクロブロックに対する予測モードとして選択され345において、この方法は終了する。この方法300が、16×16H予測モードによる任意の4×4ブロック内の歪みが所定のしきい値歪み以下でないと判断した場合には340-Noにおいて、この方法は、マクロブロックに対する予測モードとしての16×16P予測モードの設定、またはマクロブロックに対する4×4符号化タイプとの間で選択を行う350において。ある実施形態の場合には、2つの上記オプションの間の選択は、4×4予測モード探索アルゴリズム500を使用することにより容易になる図5のところで以下に説明する。他の実施形態の場合には、2つの上記オプションの間の選択は、従来の方法により行われるすでに説明したように。ここでこの方法は終了する。III節:4×4予測モード探索アルゴリズム一般的な探索アルゴリズムのステップ1の後で、4×4符号化タイプが最初の検討対象として選択された場合には、4×4予測モードがマクロブロックの16個の各4×4ブロックに対して選択される。この節においては、一般的な探索アルゴリズムのステップ3について説明する。ある実施形態の場合には、各4×4ブロックの4×4予測モードを選択するために従来の方法を使用することができる例えば、9つの各予測モードのコストを決定し、コストが最も安いモードを選択することにより。他の実施形態の場合には、4×4ブロックに対する4×4予測モードを選択するために、改良した4×4予測モード探索アルゴリズムを使用することができる。すでに説明したように、ビデオストリームは、各フレームが複数のマクロブロックからなる一連のビデオフレームからなる。マクロブロックは、通常、画素の16×16アレイであり他のサイズのマクロブロックも使用することができるが区画4×4画素アレイの区画などに分割される。H.264コーデック規格の場合には、フレームを内部符号化する場合、4×4アレイを符号化するのに9つの異なる方法があるすなわち、9つの内部4×4予測モードがある。これら9つのモードは、下記の通りである。0.内部_4×4_垂直1.内部_4×4_水平2.内部_4×4_DC3.内部_4×4_対角線_下_左4.内部_4×4_対角線_下_右5.内部_4×4_垂直_右6.内部_4×4_水平_下7.内部_4×4_垂直_左8.内部_4×4_水平_上各4×4アレイは、1つの予測モードだけで符号化される。通常、コストが最も安くなる予測モードが選択される。コストは、通常、歪みこの場合、歪みは、元の画素値と符号化された予測モード間の差を反映している、または歪みの加重平均および予測モードによるビット数この場合、歪みおよび/またはビット数が増大すると、コストが増大するに等しい。コストが最も安い最適の予測モード選択予測モードを決定するために、9つすべての予測モード間の全数探索を行うことができる。しかし、通常、9つすべての予測モード間の全数探索は効率的でない時間がかかりすぎるし、リソースの処理が多すぎる。ある実施形態の場合には、画素アレイに対する予測モードを決定するためのもっと効率的な方法が使用される。ある実施形態の場合には、画素アレイに対する予測モードを決定する際に、少ない数の予測モードを検討する探索アルゴリズムが使用される。この探索アルゴリズムは、もっと効率的であり、精度の低下も少ない。この探索アルゴリズムは、4×4アレイの可能な9つの予測モード間の論理的/位置的関係をベースとしている。図4は、4×4アレイの9つの予測モード間の論理的/位置的関係を示す概念図である。図4に示すように、円の周囲には8つの予測モード0、1、3、4、5、6、7および8が位置していて、1つの予測モード2は、円の中心に位置していて、予測モードはノードで表している。円上の2つの予測モードの間隔が近ければ近いほど、2つの予測モード間の論理的/位置的関係は強い。それ故、円上の相互間の間隔が遠ければ遠いほど、2つの予測モードの論理的/位置的関係は弱くなる。例えば、予測モード0および5は円上で相互に隣接しているが、このことはこれら2つの予測モード間に強い論理的/位置的関係が存在することを示す。もう1つの例を挙げると、予測モード0および1は、円上の対向する位置に位置しているが、このことは、これら2つの予測モード間の論理的/位置的関係が弱いことを示す。予測モード2は、円の中心に位置しているが、このことはこの予測モードが、他の予測モードのどれとも論理的/位置的関係を有さないことを示す。図4の概念図は、4×4アレイを内部符号化するためのH.264コーデック規格をベースとしている。今処理した4×4アレイの場合には、H.264規格の下の予測モードは、今処理したアレイに対して符号化する予測情報の基礎になる他の4×4アレイ本明細書においては、予測アレイと呼ぶの位置今処理した4×4アレイに対するを示す。例えば、予測モード0垂直は、今処理したアレイに対する予測アレイが、今処理したアレイの上に位置していることを示し、予測モード1水平は、今処理したアレイに対する予測アレイが、今処理したアレイの左に位置することを示す。それ故、予測モード間の論理的/位置的関係の強弱は、今処理した4×4アレイに対する予測モードが示す位置的関係に基づいてアクセスすることができる。例えば、予測モード0の予測モード1に対する論理的/位置的関係は弱い。何故なら、今処理したアレイ予測モード0が示す上に位置する予測アレイは、今処理したアレイ予測モード1が示すの左に位置する予測アレイに対して弱い論理的/位置的関係を有しているからである。この弱い論理的/位置的関係は、予測モード0および1が円の対向部分に位置する図4に反映されている。対照的に、予測モード0は、予測モード5に対して強い論理的/位置的関係を有する。何故なら、今処理したアレイ予測モード0で示すの中に位置する予測アレイは今処理したアレイ予測モード5で示すの上および右に位置する予測アレイに対して強い論理的/位置的関係を有しているからである。この強い論理的/位置的関係は、予測モード0および5が円上で隣接している図4に反映されている。円の周囲に位置する8つの予測モード0、1、3、4、5、6、7および8は、論理的/位置的に関連する予測モードの4つのグループに分けることができる。1.7、0および5垂直_左、垂直および垂直_右2.8、1および6水平_上、水平および水平_下3.7、3および8垂直_左、対角線_下_左および水平_上4.5、4および6垂直_右、対角線_下_右、および水平_下同じグループ内の予測モードは、相互に強い論理的/位置的関係を有する。ある実施形態の場合には、探索アルゴリズムは、最初に、予測モード2のコストと一緒に、各グループからの1つの予測モードのコストを決定する。次に、探索アルゴリズムは、最もコストが安い予測モードのこの組間の予測モードを決定する。コストが最も安い予測モードが、予測モードの特定のグループ内に位置している場合には、9つすべての可能な予測モードの最もコストが安いものがこの特定のグループ内に含まれている可能性が高い。それ故、次に、探索アルゴリズムは、特定のグループ内の最もコストが安い予測モードを決定し、最もコストが安い予測モードがアレイに対する最適の予測モードとして選択される。例えば、ある実施形態の場合には、探索アルゴリズムは、最初に、予測モード0、1、2、3および4のコストを決定する。この場合、予測モード0、1、3および4は、それぞれ異なるグループからのものである。予測モード0、1、3または4が、一組の予測モード0、1、2、3および4の中でコストが最も安い場合には、探索アルゴリズムは、前に決定した予測モードを含む予測モードのグループ内のコストが最も安いものを決定する。例えば、探索アルゴリズムが、予測モード1が、一組の予測モード0、1、2、3および4内でコストが最も安いと判断した場合には、探索アルゴリズムは、予測モード8、1および6のグループの中からコストが最も安いモードを決定し、コストが最も安い予測モードが最適な予測モードとして選択される。ある実施形態の場合には、探索アルゴリズムは、最初に、所定の一組の予測モードのコストを検討し比較する。この一組の予測モードはいくつかの予測モードを含んでいるが、9つのすべての可能な予測モードを含んでいるわけではない。ある実施形態の場合には、所定の一組の予測モードは、4つの各予測モードグループ図4のところで説明したからの1つの予測モードを含む。上記実施形態の場合には、所定の一組の予測モードは、予測モード0、1、2、3および4を含む。他の実施形態の場合には、所定の一組の予測モードは、他の予測モードを含む。探索アルゴリズムは、この一組の予測モード内の各予測モードのコストを決定する。この場合、C0、C1、C2、C3およびC4は、それぞれ予測モード0、1、2、3および4に対して決定したコストである。各予測モードに対するコストは、当業者であれば周知の方法により決定することができる。次に、探索アルゴリズムは、コストが最も安い予測モードの索引番号0、1、2、3または4を決定する。この場合、変数nは決定した索引番号を表すために使用される。これらの演算は、下式により表すことができる。ここで、GetIn1OfMinCostは、一組の予測モード例えば、0、1、2、3および4内の各予測モードに対するコストを決定する関数であり、コストが最も安い一組の中の予測モードの索引番号を決定する。次に、探索アルゴリズムは下記の演算を行う。ここで、xは画素アレイに対する最適な予測モード選択予測モードとして、最終的に選択される予測モードの索引番号である。それ故、探索アルゴリズムは、nが2に等しいかどうかを判断する。等しい場合には、選択した予測モードは予測モード2である。nが2に等しくない場合には、探索アルゴリズムはnが0に等しいかどうかを判断する。等しい場合には、探索アルゴリズムは選択した予測モードが、一組の予測モード7、0、5の中のコストが最も安い予測モードである。nが0に等しくない場合には、探索アルゴリズムはnが1に等しいかどうかを判断する。等しい場合には、選択した予測モードが、一組の予測モード8、1、6のコストが最も安い予測モードである。nが1に等しくない場合には、探索アルゴリズムはnが3に等しいかどうかを判断する。等しい場合には、選択した予測モードが、一組の予測モード7、3、8のコストが最も安い予測モードである。nが3に等しくない場合には、探索アルゴリズムは、nが4に等しいかどうかを判断する。等しい場合には、選択した予測モードが、一組の予測モード5、4、6のコストが最も安い予測モードである。図5は、マクロブロックの4×4アレイに対する予測モードを選択する4×4予測モード探索方法500のフローチャートである。ある実施形態の場合には、この方法500は、ビデオフレームを符号化するように構成されているソフトウェアおよび/またはハードウェアにより実施される。ある実施形態の場合には、4×4予測モード探索方法500は、図1のステップ115を含む。この方法500は、マクロブロックを16個の4×4アレイに分割する505においてことによりスタートする。次に、この方法は、第1の4×4アレイを処理のための現在の4×4アレイとしてセットする510において。現在の4×4アレイに対して、この方法500は、各予測モード0、1、2、3および4に対するコストを決定する515において。この方法は、コストが最も安い予測モードが2であるかどうかを判断する520において。2である場合には、この方法は、予測モード2を現在の4×4アレイに対する予測モードとしてセットする525において。次に、この方法は、処理するマクロブロック内に他の4×4アレイが存在するかどうかを判断する585において。存在する場合には、この方法は、次の4×4アレイを現在の4×4アレイとしてセットし590において、ステップ515に進む。存在しない場合には、この方法は終了する。この方法がコストが最も安い予測モードが2でないと判断した場合には520-Noにおいて、この方法はコストが最も安い予測モードが0であるかどうかを判断する530において。0である場合には、この方法は各予測モード7、0および5に対するコストを決定する535において。次に、この方法は、コストが最も安い予測モード予測モード7、0、5内のを現在の4×4アレイに対する予測モードとしてセットする540において。次に、この方法はステップ585に進む。この方法が、コストが最も安い予測モードが0でないと判断した場合には530-Noにおいて、この方法はコストが最も安い予測モードが1であるかどうかを判断する545において。1である場合には、この方法は各予測モード8、1および6に対するコストを決定する550において。次に、この方法は、コストが最も安い予測モード予測モード8、1、6内のを現在の4×4アレイに対する予測モードとしてセットする555において。次に、この方法はステップ585に進む。この方法が、コストが最も安い予測モードが1でないと判断した場合には545-Noにおいて、この方法はコストが最も安い予測モードが3であるかどうかを判断する560において。3である場合には、この方法は各予測モード7、3および8に対するコストを決定する565において。次に、この方法は、コストが最も安い予測モード予測モード7、3および8の中のを現在の4×4アレイに対する予測モードとしてセットする570において。次に、この方法はステップ585に進む。この方法が、コストが最も安い予測モードが3でないと判断した場合には560-Noにおいて、そのことは、最も安いコストの予測モードが4であることを示す。その場合、この方法は、各予測モード5、4および6に対するコストを決定する575において。次に、この方法はコストが最も安い予測モード予測モード5、4および6の中のを現在の4×4アレイに対する予測モードとしてセットする580において。次に、この方法はステップ585に進む。ある実施形態の場合には、この方法500は、各4×4アレイに対する予測モードの選択が、マクロブロック内の1つまたは複数の他の4×4アレイに対する前の予測モード選択に依存するマクロブロックの4×4アレイに対する予測モードを選択する。これらの実施形態の場合には、マクロブロックの各4×4アレイに対する予測モードの選択は、その頂部および左の隣接する4×4アレイに対する符号化した値すなわち、選択した予測モードにより異なる。それ故、これらの実施形態の場合には、この方法500は、マクロブロック内の頂部左の4×4アレイからスタートして予測モードを選択し右、次に下に進む。頂部および左の隣接する4×4アレイに対して前に選択した予測モードの場合には、この方法500は、処理中の現在の4×4アレイに対してコストが最も安い予測モード9つの予測モードの中のを選択する。そうするために、この方法500は、例えば、結果として得られる組合わせの全コストすなわち、16個の決定したコストの合計を計算することができる。A:別の予測モード探索アルゴリズム他の実施形態の場合には、他の予測モード探索アルゴリズムが、他の一組の演算を行う。最初に、他の探索アルゴリズムは、変数aが決定した索引番号を表すために使用される一組の予測モード0、1、3および4の中からコストが最も安い予測モードの索引番号を決定する。他の探索アルゴリズムは、また、変数bが決定した索引番号を表すために使用される一組の予測モード0、1、3および4の中から2番目にコストが安い予測モードの索引番号も決定する。さらに、この別の探索アルゴリズムは、また、変数nが決定した索引番号を表すために使用される一組の予測モード0、1、2、3および4の中からコストが最も安い予測モードの索引番号も決定する。これらの演算は下式で表すことができる。ここで、GetIn1OfSecondMinCostは、一組の予測モード例えば、0、1、3および4内の各予測モードに対するコストを決定する関数であり、2番目に安いコストの一組内の予測モードの索引番号を決定する。次に、この探索アルゴリズムは下記の演算を行う。ここで、xは、画素アレイに対して最適な予測モード選択予測モードとして最終的に選択される予測モードの索引番号である。それ故、探索アルゴリズムは、nが2に等しいかどうかを判断する。2に等しい場合には、選択した予測モードは予測モード2である。nが2に等しくない場合には、他の探索アルゴリズムは、aが0に等しいかどうかまたbが4に等しいかどうか、またはその逆であるかどうかすなわち、aが4に等しいかどうか、またbが0に等しいかどうかを判断する。等しい場合には、選択した予測モードが、一組の予測モード0、5、4の中のコストが最も安い予測モードである。aが0に等しくなく、bが4に等しくなく、またはその逆でもない場合には、他の探索アルゴリズムは、aが4に等しいかどうか、またbが1に等しいかどうか、またはその逆であるかどうかを判断する。そうである場合には、選択した予測モードが、一組の予測モード4、6、1のコストが最も安い予測モードである。aが4に等しくなく、bが1に等しくなく、またはその逆でもない場合には、他の探索アルゴリズムは、aが1に等しいかどうか、またbが3に等しいかどうか、またはその逆であるかどうかを判断する。そうである場合には、選択した予測モードが、一組の予測モード1、8、3のコストが最も安い予測モードである。aが1に等しくなく、bが3に等しくなく、またはその逆でもない場合には、他の探索アルゴリズムは、aが3に等しいかどうか、またbが0に等しいかどうか、またはその逆であるかどうかを判断する。そうである場合には、選択した予測モードが、一組の予測モード3、7、0のコストが最も安い予測モードである。図6は、マクロブロックの4×4アレイに対して予測モードを選択する他の4×4予測モード探索方法のフローチャートである。ある実施形態の場合には、他の4×4予測モード探索方法は600、図1のステップ115を含む。この方法600は、マクロブロックを16個の4×4アレイに分割する605においてことによりスタートする。次に、この方法は、第1の4×4アレイを処理のための現在の4×4アレイとしてセットする610において。現在の4×4アレイに対して、この方法600は各予測モード0、1、2、3および4に対するコストを決定する616において。この方法は、変数aを、予測モード0、1、3および4の中のコストが最も安い予測モードの予測モード索引に等しくセットする616において。この方法は、変数bを、予測モード0、1、3および4の中から2番目にコストが安い予測モードの予測モード索引に等しくセットする617において。この方法は、変数nを、予測モード0、1、2、3および4の中のコストが最も安い予測モードの予測モード索引に等しくセットする617において。この方法は、nが2に等しいかどうかを判断する620において。2に等しい場合には、この方法は、予測モード2を現在の4×4アレイに対する予測モードとしてセットする625において。次に、この方法は、処理するマクロブロック内に他の4×4アレイが存在するかどうかを判断する685において。存在する場合には、この方法は、次の4×4アレイを現在の4×4アレイとしてセットし690において、ステップ615に進む。存在しない場合には、この方法は終了する。この方法が、nが2に等しくないと判断した場合には620-Noにおいて、この方法は、上記条件aが0に等しく、bが4に等しく、またはその逆が真であるかどうかを判断する630において。真である場合には、この方法は、各予測モード0、5および4に対するコストを決定する635において。次に、この方法は、コストが最も安い予測モード予測モード0、5および4の中のを現在の4×4アレイに対する予測モードとしてセットする640において。次に、この方法はステップ685に進む。この方法が、上記条件aが0に等しく、bが4に等しく、またはその逆であるが真でないと判断した場合には630-Noにおいて、この方法は、上記条件aが4に等しく、bが1に等しく、またはその逆であるが真であるかどうかを判断する645において。そうである場合には、この方法は、各予測モード4、6および1に対するコストを決定する650において。次に、この方法は、コストが最も安い予測モード予測モード4、6、および1の中のを現在の4×4アレイに対する予測モードとしてセットする655において。次に、この方法はステップ685に進む。この方法が、上記条件aが4に等しく、bが1に等しく、またはその逆であるが真でないと判断した場合には645-Noにおいて、この方法は、上記条件aが1に等しく、bが3に等しく、またはその逆であるが真であるかどうかを判断する660において。真である場合には、この方法は、各予測モード1、8および3に対するコストを決定する665において。次に、この方法は、コストが最も安い予測モード予測モード1、8および3の中のを現在の4×4アレイに対する予測モードとしてセットする670において。次に、この方法はステップ685に進む。この方法が、上記条件aが1に等しく、bが3に等しく、またはその逆であるが真でないと判断した場合には660-Noにおいて、この方法は、上記条件aが3に等しく、bが0に等しく、またはその逆であるが真であるかどうかを判断する672において。真である場合には、この方法は、各予測モード3、7および0に対するコストを決定する675において。次に、この方法は、コストが最も安い予測モード予測モード3、7および0の中のを現在の4×4アレイに対する予測モードとしてセットする680において。次に、この方法はステップ685に進む。この方法が、上記条件aが3に等しく、bが0に等しく、またはその逆であるが真でないと判断した場合には672-Noにおいて、この方法は、予測モードを、変数nステップ618において決定したが示す予測モード、すなわち予測モード0、1、2、3および4の中のコストが最も安い予測モードに等しくセットする673において。次に、この方法はステップ685に進む。図7は、ある実施形態を実行するコンピュータシステム700である。コンピュータシステム700は、バス705、プロセッサ710、システムメモリ715、読出し専用メモリ720、永久記憶装置725、入力装置730、および出力装置735を含む。バス705は、すべてのシステム、周辺機器およびコンピュータシステム700の多数の内部装置と通信できるように接続しているチップセットバスを集合的に表す。例えば、バス705は、プロセッサ710を、読出し専用メモリ720、システムメモリ715、および永久記憶装置725と通信できるように接続している。読出し専用メモリROM720は、コンピュータシステムのプロセッサ710および他のモジュールが必要とする静的データおよび命令を記憶する。一方、永久記憶装置725は、読出し/書込みメモリ素子である。このデバイスは、コンピュータシステム700の電源をオフにした場合でも、命令およびデータを記憶している不揮発性記憶装置である。ある種の実施形態は、永久記憶装置725として、大量記憶装置磁気ディスクまたは光ディスクおよびその対応するディスクドライブなどを使用する。他の実施形態は、永久記憶装置として取り外すことができる記憶装置フロッピーディスクまたはzip登録商標ディスクおよびその対応するディスクドライブなどを使用する。永久記憶装置725のように、システムメモリ715は、読出し/書込みメモリ素子である。しかし、記憶装置725とは異なり、システムメモリは、ランダムアクセスメモリRAMのような揮発性読出し/書込みメモリである。システムメモリは、プロセッサが稼働時間中に必要とする命令およびデータの中のあるものを記憶する。ある実施形態を実行するために必要な命令および/またはデータは、システムメモリ715、永久記憶装置725、読出し専用メモリ720、またはこれら3つの任意の組合わせ内に記憶される。例えば、種々の記憶装置は、ある種の実施形態によるビデオデータストリームを符号化または復号化するための命令を含むことができ、および/またはビデオデータを含むことができる。これらの種々の記憶装置から、プロセッサ710は、ある種の実施形態の処理を実行するために実行する命令および処理するデータを検索する。これらの種々の記憶装置から、プロセッサ710は、ある種の実施形態の処理を実行するために実行する命令および処理するデータを検索する。バス705は、また、入力および出力装置730および735に接続している。入力装置730により、ユーザは、コンピュータシステム700に情報を入力することができ、コンピュータシステム700へのコマンドを選択することができる。入力装置730は、英数字キーボードおよびカーソルコントローラを含む。出力装置735は、コンピュータシステム700が生成する画像を表示する。出力装置は、プリンタおよび陰極線管CRTまたは液晶表示装置LCDのような表示デバイスを含む。最後に、図7に示すように、バス705は、また例えば、ネットワークアダプタ図示せずを通して、コンピュータシステム700をネットワーク765に接続している。このようにして、コンピュータシステム700は、コンピュータのネットワークの一部ローカルエリアネットワークLAN、ワイドエリアネットワークWANまたはイントラネットなど、またはネットワークのネットワークインターネットなどとなることができる。コンピュータシステム700のいくつかのまたは全部の構成要素は、ある種の実施形態と一緒に使用することができる。しかし、通常の当業者であれば、任意の他の構成も他の実施形態と一緒に使用することができることを理解することができるだろう。多数の特定の詳細を参照しながら本発明を説明してきたが、通常の当業者であれば、本発明の精神から逸脱することなしに、本発明を他の特定の形態内に埋設することができることを理解することができるだろう。例えば、本発明の多くの実施形態をマクロブロックを参照しながら説明してきたが、通常の当業者であれば、これらの実施形態は、画素値の任意の他のアレイと一緒に使用することができることを理解することができるだろう。"