(57)【要約】【課題】ビデオエンコーディングにおける動き推定を行うための技術【解決手段】現在のブロックにとって最もよく適合する予測因子ブロックが、現在エンコードされているピクチャの現在のブロックと現在のブロックに空間的あるいは時間的に近接するブロックの動きベクトルを用いて配置される候補ブロックとを比較することにより配置される。所与の近接ブロックが使用可能な動きベクトルを有していない場合、別の近接ブロックが用いられる。時間的に近接するブロックは、現在のブロックよりも先にエンコードされる最後のピクチャ中のブロックである。さらに、候補ブロックは、現在のブロックと候補ブロックとを比較するために用いられるプロセッサのローカルＲＡＭ内部に収まる探索空間の最小化された部分を規定するために用いられる。この最小化された探索空間は、２フェーズ方法で用いられる。【選択図】図２
2006217644.tif 000002
【特許請求の範囲】
【請求項１】
デジタル表現された複数のピクチャのシーケンスの基準ピクチャに含まれる複数の候補領域のうちの１つが予測因子領域として考慮されるべきか否かを決定する方法であって、該予測因子領域は、該デジタル表現された複数のピクチャのシーケンスの現在のピクチャにおける現在の領域の値を予測するために使用され、
該デジタル表現された複数のピクチャのシーケンスは複数のピクチャを含み、該複数のピクチャのうち特定の時刻における１つが該現在のピクチャとして定義されており、
該現在のピクチャは複数の領域を含み、該現在のピクチャの該複数の領域のうち該特定の時刻における１つが該現在の領域として定義されており、
該方法は、
該現在の領域に近接する複数の近接領域であって、該現在のピクチャ内の領域およびエンコードされた最後のピクチャ内の領域を含む複数の近接領域に対して、それぞれが所定のベクトル値を有する複数の動きベクトルを決定する工程と、
該複数の近接領域に対して各動きベクトルの該所定のベクトル値を該基準ピクチャ内の領域の空間的位置に加算することにより、該複数の候補領域を生成する工程であって、各動きベクトルの該所定のベクトル値と該基準ピクチャ内の該領域の空間的位置とを加算した結果として、該複数の候補領域のそれぞれに対する空間的位置を生じさせ、該基準ピクチャ内の該領域の空間的位置は、該現在のピクチャ内の該現在の領域の空間的位置と同一である、工程と、
該複数の候補領域のそれぞれにおけるピクセル情報と該現在の領域におけるピクセル情報とを比較することにより、該複数の候補領域のそれぞれに対して適合基準スコアを決定する工程と、
最も低い適合基準スコアを有する候補領域を該予測因子領域として割り当てる工程と
を含み、
該複数の候補領域を生成する該工程は、該基準ピクチャと、該エンコードされた最後のピクチャと、該現在のピクチャとの間の時間的な関係に基づいて、該所定のベクトル値をスケーリングすることによって、該エンコードされた最後のピクチャ内に含まれる近接領域に対応する候補領域を生成する工程を含む、方法。
【請求項２】
前記複数のピクチャの他のピクチャに関連して各ピクチャが捕捉された時間を追跡するように、該複数のピクチャの各々は時間的基準に関連付けられており、該複数のピクチャは変数Ｐｉによって表され、ここで、添え字ｉは、該時間的基準を表す、請求項１に記載の方法。
【請求項３】
前記複数のピクチャは、表示順序Ｐｋ、Ｐｍ、Ｐｖを有し、ここで、ｋ＜ｍ＜ｖであり、
該複数のピクチャは、該複数のピクチャがエンコードされる順序である伝送順序を有し、前記エンコードされた最後のピクチャ内に含まれる前記近接する領域の前記所定のベクトル値は、該近接する領域の空間的位置を示すＸ座標値およびＹ座標値を有する、請求項２に記載の方法。
【請求項４】
前記表示順序が前記伝送順序と同一であり、かつ、前記エンコードされた最後のピクチャが「過去」の基準ピクチャである場合には、該エンコードされた最後のピクチャ内に含まれる前記近接する領域に対応する前記候補領域が、
ｆｌｏｏｒ（Ｘ（（ｖ−ｍ）／（ｍ−ｋ））＋０．５）と、
ｆｌｏｏｒ（Ｙ（（ｖ−ｍ）／（ｍ−ｋ））＋０．５）とによって、該近接する領域の前記所定のベクトル値のＸ座標値およびＹ座標値をそれぞれスケーリングすることによって生成される、請求項３に記載の方法。
【請求項５】
前記表示順序が前記伝送順序と同一であり、かつ、前記エンコードされた最後のピクチャおよび前記現在のピクチャが同じ「過去の」基準ピクチャを使用する場合には、該エンコードされた最後のピクチャ内に含まれる前記近接する領域に対応する前記候補領域が、
ｆｌｏｏｒ（Ｘ（（ｖ−ｋ）／（ｍ−ｋ））＋０．５）と、
ｆｌｏｏｒ（Ｙ（（ｖ−ｋ）／（ｍ−ｋ））＋０．５）とによって、該近接する領域の前記所定のベクトル値のＸ座標値およびＹ座標値をそれぞれスケーリングすることによって生成される、請求項３に記載の方法。
【請求項６】
前記表示順序が前記伝送順序と同一でなく、かつ、前記エンコードされた最後のピクチャおよび前記現在のピクチャが同じ「未来」の基準ピクチャを使用する場合には、該エンコードされた最後のピクチャ内に含まれる前記近接する領域に対応する前記候補領域が、
ｆｌｏｏｒ（Ｘ（（ｖ−ｍ）／（ｖ−ｋ））＋０．５）と、
ｆｌｏｏｒ（Ｙ（（ｖ−ｍ）／（ｖ−ｋ））＋０．５）とによって、該近接する領域の前記所定のベクトル値のＸ座標値およびＹ座標値をそれぞれスケーリングすることによって生成される、請求項３に記載の方法。
【請求項７】
前記表示順序が前記伝送順序と同一でなく、かつ、前記エンコードされた最後のピクチャが、ＰｋがＰｖに対して「過去」の基準ピクチャであり、ＰｖがＰｍに対して「未来」の基準ピクチャであることを除いて、前記基準ピクチャである場合には、該エンコードされた最後のピクチャ内に含まれる前記近接する領域に対応する前記候補領域が、
ｆｌｏｏｒ（Ｘ（（ｍ−ｖ）／（ｖ−ｋ））＋０．５）と、
ｆｌｏｏｒ（Ｙ（（ｍ−ｖ）／（ｖ−ｋ））＋０．５）とによって、該近接する領域の前記所定のベクトル値のＸ座標値およびＹ座標値をそれぞれスケーリングすることによって生成される、請求項３に記載の方法。
【請求項８】
前記表示順序が前記伝送順序と同一でなく、かつ、前記エンコードされた最後のピクチャが、ＰｖがＰｋに対して「未来」の基準ピクチャであり、ＰｋがＰｍに対して「過去」の基準ピクチャであることを除いて、前記基準ピクチャである場合には、該エンコードされた最後のピクチャ内に含まれる前記近接する領域に対応する前記候補領域が、
ｆｌｏｏｒ（Ｘ（（ｋ−ｍ）／（ｖ−ｋ））＋０．５）と、
ｆｌｏｏｒ（Ｙ（（ｋ−ｍ）／（ｖ−ｋ））＋０．５）とによって、該近接する領域の前記所定のベクトル値のＸ座標値およびＹ座標値をそれぞれスケーリングすることによって生成される、請求項３に記載の方法。
【請求項９】
前記エンコードされた最後のピクチャ内の前記近接領域は、該エンコードされた最後のピクチャにおいて、前記現在のピクチャにおける前記現在の領域の位置と同じ空間的位置にある、請求項１に記載の方法。
【請求項１０】
前記複数の候補領域のそれぞれに対して空間的領域を割り当て、該割り当てられた空間的領域のそれぞれに対して座標を定義し、該複数の候補領域のうちの一対の候補領域であって、該一対の候補領域に割り当てられた該空間的領域に対して定義された座標が、他のどの一対の候補領域よりも大きな探索空間を定義する極値を定義する一対の候補領域を決定することによって、前記決定工程において決定された前記複数の候補領域を用いて探索空間を計算する工程
をさらに含む、請求項１に記載の方法。
【請求項１１】
前記探索空間をプロセッサの内部にあるコンピュータ読み取り可能な格納媒体にローディングする工程をさらに含み、
該プロセッサは、該コンピュータ読み取り可能な格納媒体に配置される該候補領域におけるピクセル情報と該現在の領域におけるピクセル情報とを比較する、請求項１０に記載の方法。
【請求項１２】
前記探索空間を計算する前記工程は、複数の探索空間を計算することを含む、請求項１０に記載の方法。
【請求項１３】
前記複数の探索空間を計算する前記工程は、
前記空間的領域に等しい初期探索空間であって、前記より大きな探索空間を定義する極値を定義する座標を有するように決定された前記一対の候補領域に対して定義された前記座標に等しい座標を有する初期探索空間を定義することと、
該初期探索空間のそれぞれに対して該複数の候補領域のうちの１つの候補領域であって、他の候補領域の空間的領域の座標と該初期探索空間の座標との距離に比べて該初期探索空間の座標から最小の距離である座標を有する空間的領域を有する候補領域を決定することと、
該初期探索空間のそれぞれに対して該初期探索空間の空間的領域の座標の極値によって定義される空間的領域を有する新たな探索空間を定義することであって、該候補領域の該空間的領域は、該最小の距離である座標を有する空間的領域を有している、ことと、
該新たな探索空間が該複数の候補領域の空間的領域を含む空間的領域を有するまで、該初期探索空間のそれぞれに対して該複数の候補領域のうちの１つを決定する工程と該新たな探索空間を定義する工程とを繰り返すことと
を含む、請求項１２に記載の方法。
【請求項１４】
前記複数の候補領域を用いて決定された前記予測因子領域におけるピクセル情報と前記現在の領域におけるピクセル情報との間の適合が、第１の閾値を満足するほど近くない場合には、該複数の候補領域のうちのいくつかを用いて決定された該予測因子領域上にセンタリングされた該探索空間における領域と該現在の領域とを比較することにより該予測因子領域を発見し、そうでない場合には、該複数の候補領域のうちのいくつかを用いて決定された該予測因子領域を該予測因子領域にする工程をさらに含む、請求項１に記載の方法。
【請求項１５】
前記複数の候補領域のうちのいくつかを用いて決定された予測因子領域上にセンタリングされた前記探索空間における領域を比較する前記工程において、該探索空間は非矩形である、請求項１４に記載の方法。
【請求項１６】
前記複数の候補領域のうちのいくつかを用いて決定された予測因子領域上にセンタリングされた前記探索空間における領域を比較する前記工程において、該領域は、該複数の候補領域のうちの該いくつか以外の該複数の候補領域のうちのいくつかを用いて決定される該予測因子領域からの距離が増大する順に前記現在の領域と比較される、請求項１５に記載の方法。
【請求項１７】
前記領域は、第２の事前に決定された閾値を満足するほど十分に近い前記現在の領域と適合するものが発見されるまで比較される、請求項１６に記載の方法。
【請求項１８】
前記第２の閾値を満足するために必要な前記適合は、前記第１の閾値を満足するために必要な適合よりも近い、請求項１７に記載の方法。
【請求項１９】
計算を行うためのプロセッササイクルの割当てにおいて利用可能なプロセッササイクル数に応じて、前記予測因子領域上にセンタリングされた前記探索空間を動的にサイジングする工程をさらに含む、請求項１５に記載の方法。
【請求項２０】
前記現在の領域に対する前記少なくとも１つの別の候補領域の位置に応じて、前記探索空間を動的に形成する工程をさらに含む、請求項１５に記載の方法。
【請求項２１】
前記現在の領域が前記現在のピクチャにおいて有する空間的位置と同じ空間的位置を前記基準ピクチャにおいて有する前記基準ピクチャ内の領域を第１の候補領域として選択する工程と、
前記第１の候補領域内のピクセル情報と前記現在の領域内のピクセル情報との間の適合が第３の閾値を満足するほど近くない場合には、前記複数の候補領域についての工程を進め、そうでない場合には、該第１の候補領域を前記予測因子領域にする工程と
をさらに含む、請求項１７に記載の方法。
【請求項２２】
前記第３の閾値は、前記第１の閾値よりも大きく、該第１の閾値は前記第２の閾値よりも大きい、請求項２１に記載の方法。
【請求項２３】
前記複数の候補領域のそれぞれは、矩形である、請求項１に記載の方法。
【請求項２４】
コンピュータプロセッサに請求項１に記載の方法を実行させるためのプログラムを記録したコンピュータ読み取り可能な格納媒体。
【請求項２５】
デジタル表現された複数のピクチャのシーケンスの基準ピクチャにおける探索空間の部分を規定する方法であって、複数の候補領域の中から予測因子領域に対して探索が該探索空間の部分内で行われ、該予測因子領域は、該デジタル表現された複数のピクチャのシーケンスの現在のピクチャにおける現在の領域の値を予測するために使用され、
該デジタル表現された複数のピクチャのシーケンスは複数のピクチャを含み、該複数のピクチャのうち特定の時刻における１つが該現在のピクチャとして定義されており、
該現在のピクチャは複数の領域を含み、該現在のピクチャの該複数の領域のうち該特定の時刻における１つが該現在の領域として定義されており、
該方法は、
該現在の領域に近接し、かつ、それぞれが所定の値を有する動きベクトルを含む該現在のピクチャ内の該複数の領域の各領域およびエンコードされた最後のピクチャにおける領域に対して、
該複数の近接領域に対して各動きベクトルの該所定のベクトル値を該基準ピクチャ内の領域の空間的位置に加算することにより、該複数の候補領域を生成する工程であって、各動きベクトルの該所定のベクトル値と該基準ピクチャ内の該領域の空間的位置とを加算した結果として、該複数の候補領域のそれぞれに対する空間的位置を生じさせ、該基準ピクチャ内の該領域の空間的位置は、該現在のピクチャ内の該現在の領域の空間的位置と同一である、工程と、
該複数の候補領域を用いて該探索空間の部分を規定する工程と
を含み、
該複数の候補領域を生成する該工程は、該基準ピクチャと、該エンコードされた最後のピクチャと、該現在のピクチャとの間の時間的な関係に基づいて、該所定のベクトル値をスケーリングすることによって、該エンコードされた最後のピクチャ内に含まれる近接領域に対応する候補領域を生成する工程を含む、方法。
【請求項２６】
前記複数のピクチャの他のピクチャに関連して各ピクチャが捕捉された時間を追跡するように、該複数のピクチャの各々は時間的基準に関連付けられており、該複数のピクチャは変数Ｐｉによって表され、ここで、添え字ｉは、該時間的基準を表す、請求項２５に記載の方法。
【請求項２７】
前記複数のピクチャは、表示順序Ｐｋ、Ｐｍ、Ｐｖを有し、ここで、ｋ＜ｍ＜ｖであり、
該複数のピクチャは、該複数のピクチャがエンコードされる順序である伝送順序を有し、前記エンコードされた最後のピクチャ内に含まれる前記近接する領域の前記所定のベクトル値は、該近接する領域の空間的位置を示すＸ座標値およびＹ座標値を有する、請求項２６に記載の方法。
【請求項２８】
前記表示順序が前記伝送順序と同一であり、かつ、前記エンコードされた最後のピクチャが「過去」の基準ピクチャである場合には、該エンコードされた最後のピクチャ内に含まれる前記近接する領域に対応する前記候補領域が、
ｆｌｏｏｒ（Ｘ（（ｖ−ｍ）／（ｍ−ｋ））＋０．５）と、
ｆｌｏｏｒ（Ｙ（（ｖ−ｍ）／（ｍ−ｋ））＋０．５）とによって、該近接する領域の前記所定のベクトル値のＸ座標値およびＹ座標値をそれぞれスケーリングすることによって生成される、請求項２７に記載の方法。
【請求項２９】
前記表示順序が前記伝送順序と同一であり、かつ、前記エンコードされた最後のピクチャおよび前記現在のピクチャが同じ「過去の」基準ピクチャを使用する場合には、該エンコードされた最後のピクチャ内に含まれる前記近接する領域に対応する前記候補領域が、
ｆｌｏｏｒ（Ｘ（（ｖ−ｋ）／（ｍ−ｋ））＋０．５）と、
ｆｌｏｏｒ（Ｙ（（ｖ−ｋ）／（ｍ−ｋ））＋０．５）とによって、該近接する領域の前記所定のベクトル値のＸ座標値およびＹ座標値をそれぞれスケーリングすることによって生成される、請求項２７に記載の方法。
【請求項３０】
前記表示順序が前記伝送順序と同一でなく、かつ、前記エンコードされた最後のピクチャおよび前記現在のピクチャが同じ「未来」の基準ピクチャを使用する場合には、該エンコードされた最後のピクチャ内に含まれる前記近接する領域に対応する前記候補領域が、
ｆｌｏｏｒ（Ｘ（（ｖ−ｍ）／（ｖ−ｋ））＋０．５）と、
ｆｌｏｏｒ（Ｙ（（ｖ−ｍ）／（ｖ−ｋ））＋０．５）とによって、該近接する領域の前記所定のベクトル値のＸ座標値およびＹ座標値をそれぞれスケーリングすることによって生成される、請求項２７に記載の方法。
【請求項３１】
前記表示順序が前記伝送順序と同一でなく、かつ、前記エンコードされた最後のピクチャが、ＰｋがＰｖに対して「過去」の基準ピクチャであり、ＰｖがＰｍに対して「未来」の基準ピクチャであることを除いて、前記基準ピクチャである場合には、該エンコードされた最後のピクチャ内に含まれる前記近接する領域に対応する前記候補領域が、
ｆｌｏｏｒ（Ｘ（（ｍ−ｖ）／（ｖ−ｋ））＋０．５）と、
ｆｌｏｏｒ（Ｙ（（ｍ−ｖ）／（ｖ−ｋ））＋０．５）とによって、該近接する領域の前記所定のベクトル値のＸ座標値およびＹ座標値をそれぞれスケーリングすることによって生成される、請求項２７に記載の方法。
【請求項３２】
前記表示順序が前記伝送順序と同一でなく、かつ、前記エンコードされた最後のピクチャが、ＰｖがＰｋに対して「未来」の基準ピクチャであり、ＰｋがＰｍに対して「過去」の基準ピクチャであることを除いて、前記基準ピクチャである場合には、該エンコードされた最後のピクチャ内に含まれる前記近接する領域に対応する前記候補領域が、
ｆｌｏｏｒ（Ｘ（（ｋ−ｍ）／（ｖ−ｋ））＋０．５）と、
ｆｌｏｏｒ（Ｙ（（ｋ−ｍ）／（ｖ−ｋ））＋０．５）とによって、該近接する領域の前記所定のベクトル値のＸ座標値およびＹ座標値をそれぞれスケーリングすることによって生成される、請求項２７に記載の方法。
【請求項３３】
前記動きベクトルの前記所定の値は、任意の大きさを有し得る、請求項２５に記載の方法。
【請求項３４】
前記探索空間の部分が該複数の候補領域の全てを含むように、前記複数の候補領域を用いて該探索空間の部分を決定する工程をさらに含む、請求項２５に記載の方法。
【請求項３５】
コンピュータ読み取り可能な格納媒体に配置される前記候補領域におけるピクセル情報と前記現在の領域におけるピクセル情報との比較を実行するプロセッサの内部にあるコンピュータ読み取り格納媒体に前記探索空間の部分をローディングする工程をさらに含む、請求項２５に記載の方法。
【請求項３６】
前記探索空間の部分を計算する前記工程は、該探索空間の複数の部分を計算することを含む、請求項３４に記載の方法。
【請求項３７】
前記探索空間の複数の部分を計算する前記工程は、
前記空間的領域に等しい初期探索空間であって、前記より大きな探索空間を定義する極値を定義する座標を有するように決定された前記一対の候補領域に対して定義された前記座標に等しい座標を有する初期探索空間を定義することと、
該初期探索空間のそれぞれに対して該複数の候補領域のうちの１つの候補領域であって、他の候補領域の空間的領域の座標と該初期探索空間の座標との距離に比べて該初期探索空間の座標から最小の距離である座標を有する空間的領域を有する候補領域を決定することと、
該初期探索空間のそれぞれに対して該初期探索空間の空間的領域の座標の極値によって定義される空間的領域を有する新たな探索空間を定義することであって、該候補領域の該空間的領域は、該最小の距離である座標を有する空間的領域を有している、ことと、
該新たな探索空間が該複数の候補領域の空間的領域を含む空間的領域を有するまで、該初期探索空間のそれぞれに対して該複数の候補領域のうちの１つを決定する工程と該新たな探索空間を定義する工程とを繰り返すことと
を含む、請求項３６に記載の方法。
【請求項３８】
前記探索空間の複数の部分のうち１つは、前記現在の領域が前記現在のピクチャにおいて有する空間的位置と同じ空間的位置を前記基準ピクチャにおいて有する該基準ピクチャ内の領域を有し、
該探索空間の複数の部分は、該現在の領域が該現在のピクチャにおいて有する空間的位置と同じ空間的位置を該基準ピクチャにおいて有する該基準ピクチャ内の領域を含む該探索空間の複数の部分のうちの１つから、前記プロセッサの内部にある前記コンピュータ読み取り格納媒体に別個にロードされる、請求項３６に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連特許出願の相互参照）
（発明の背景）
１．発明の分野
本発明は概して、デジタルピクチャのエンコーディングシーケンスに関し、よ
り詳細には、デジタルピクチャのシーケンスをエンコーディングする間に行われ
る動き推定動作に関する。
【背景技術】
【０００２】
２．従来技術の説明
以下の従来技術についての説明では、最初に総括的にデジタルピクチャの圧縮
について、次いで現在実施されている動き推定について、そして最後に現在の技
術の問題点について議論する。
【０００３】
デジタルピクチャの圧縮
デジタルピクチャはもともとは、コンンピュータシステムのメモリにおいて、
ピクチャエレメントまたはピクセルのアレイとして表される。各ピクセルは、ピ
クチャにおける１つの点を表す。ピクセル自体はデータのアイテムであり、この
データのアイテムの内容が、ピクセルにより表される点がデジタルピクチャにお
いてどのように見えるかを決定する。デジタルピクチャの品質はもちろん、ピク
チャ中のピクセル数とピクセル中のビット数とに依存する。ピクチャ中のピクセ
ル数が多いほど、解像度が良くなり、各ピクセル内のビット数が多いほど、各ピ
クセルはピクセルにより表される画像内の点についてより多くの情報を格納する
ことができる。例えば、ピクセル内のビット数が多いほど、ピクセルはより多く
の色の差異を表現することができる。
【０００４】
上記のような理由のため、高品質なデジタルピクチャを表示するためにもとも
とは用いられたピクセルのアレイは、非常に大型であり、かつ大量のメモリを必
要とする。特に問題なのは、該当するデジタルピクチャが、適切な順序でかつ適
切なタイミングで見られると動画を構成するピクチャのシーケンスの一部である
場合のアレイのサイズである。ピクチャのシーケンスを表示する装置は、それら
を格納するだけでなく、動画についてのタイミング要求を満たすようそれらを十
分に高速に読み出しかつ表示しなければならない。
【０００５】
このタイミングおよび格納の問題は、デジタルピクチャのシーケンスを限られ
た帯域を有する媒体を用いて格納量が限られている受信器に分配する場合、特に
深刻となる。この問題が当てはまる例としては、デジタルテレビ、テレビ会議、
およびテレビ電話がある。これらのアプリケーションでは、ピクチャのシーケン
スを、テレビ放送チャンネルもしくはケーブルテレビチャンネル、電話線、また
はコンピュータネットワークを用いて、ピクチャを格納するためのメモリ量が限
られている、テレビジョンセット、テレビ電話、またはパーソナルコンピュータ
のような、比較的低コストな消費者のデバイスに送信しなければならない。これ
らのアプリケーションはしたがって、デジタルピクチャを圧縮することによりピ
クチャを送信する際に必要な帯域および／またはそのピクチャを送信先に格納す
るために必要な格納量を低減する何らかの方法が見付けられた場合にのみ、経済
的に実施可能である。
【０００６】
この技術分野においては、デジタルピクチャのシーケンスを圧縮するための多
くの異なる技術が開発された。これらの技術の１つとしては、デジタルビデオを
圧縮するためのＭＰＥＧ−２規格がある。ＭＰＥＧ−２規格については、１９９
６年１１月にＵＲＬのｈｔｔｐ：／／ｗｗｗ．ｃｄｒｅｖｏｌｕｔｉｏｎ．ｃｏ
ｍ／ｔｅｘｔ／ｍｐｅｇｉｎｆｏ．ｈｔｍ．のアドレスにおいて閲覧可能であっ
た「Ｂａｃｋｇｒｏｕｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  ｏｎ  ＭＰＥＧ−１  ａ
ｎｄ  ＭＰＥＧ−２  Ｔｅｌｅｖｉｓｉｏｎ  Ｃｏｍｐｒｅｓｓｉｏｎ」におい
て説明されている。これらの技術の全ては、デジタルピクチャのシーケンスが冗
長情報を大量に含んでいる点を利用したものである。１つのタイプの冗長性は、
空間的なものである：任意のピクチャにおいて、空間的に互いに接近したピクセ
ルは、類似の特性を有する傾向がある。こういった理由のため、ピクチャを空間
的に隣接するピクセルの領域のセットとして表現することがしばしば可能となる
。領域はもちろんオーバーラップし得る。領域が矩形の場合、それをブロックと
呼ぶ。ピクチャの所与の領域がピクチャの別の領域に大きく類似するがその別の
領域と同一ではない場合、その所与の領域におけるピクセルを、その所与の領域
を別の領域と所与の領域との間の差として記述する表現と取り替えることができ
る。
【０００７】
ピクチャのシーケンスにおける別のタイプの冗長性は、時間的なものである；
シーケンス内の所与のピクチャがシーケンス内の先行または後続ピクチャに外観
が大きく類似することはごく頻繁におこる；したがって、所与のピクチャ内の領
域と先行または後続するピクチャ（本明細書中、これを「基準」ピクチャと呼ぶ
）の中の領域との間の「差」を表す所与のピクチャの表現を作成し、この表現を
ピクセルのアレイとしての表現の代わりに用いることにより、所与のピクチャを
圧縮することが可能となる。
【０００８】
図１は、所与のピクチャと基準ピクチャとの間の差を表すための１つの方法を
示す。デジタル基準ピクチャ１０１は、メモリにおいてピクセル１０５のアレイ
として表現される。このピクチャは、ブロック１０３にさらに分割される。ブロ
ック１０３の各々は典型的には、１６×１６ピクセルの正方形である。基準ピク
チャ１０１内のオブジェクト１０７は、隣接する４つのブロック１０３（すなわ
ち、ブロック１０３（ｍ、ｎ）、（ｍ＋１、ｎ）、（ｍ、ｎ＋１）、および（ｍ
＋１、ｎ＋１））内に含まれる。ここで、ｍおよびｎは、ブロックの左上隅部の
ｘおよびｙ座標を示す。所与のピクチャ１０９において、オブジェクト１０７は
、異なる位置（すなわち、ブロック１０３（ｂ、ｓ）、（ｂ＋１、ｓ）、（ｂ、
ｓ＋１）および（ｂ＋１、ｓ＋１））にあるが、それ以外の点ではオブジェクト
１０７は、基準ピクチャ１０１におけるのと同じ外観を実質的に有する。そうい
った理由のため、オブジェクト１０７は、所与のピクチャ１０９の圧縮表現にお
いて、基準イメージ１０１内のオブジェクト１０７との差として記述され得る。
差としては、以下の２種類の差、すなわち、
所与のピクチャ１０９におけるオブジェクト１０７の位置変化および
所与のピクチャ１０９におけるオブジェクト１０７の外観における任意の変化
がある。第１の種類の差は、基準ピクチャ１０１におけるオブジェクト１０７の
位置からピクチャ１０９におけるオブジェクト１０７へのオフセットを用いて記
述され得る。第２の種類の差は、基準ピクチャ１０１におけるオブジェクト１０
７の外観とピクチャ１０９におけるオブジェクト１０７の外観との差を用いて記
述され得る。この外観の変化は、オブジェクト１０７に入射する照度の変化また
はｘ軸、ｙ軸もしくはピクチャ平面に垂直なｚ軸周りでの回転によるオブジェク
トのひずみもしくはせん断変形などの要因により生じ得る。
【０００９】
先程説明したような圧縮技術を使用すると、市販のデジタルテレビ、デジタル
通信会議、およびデジタルテレビ電話に典型的な帯域およびメモリ制約条件を満
足するのに十分に小さいデジタルピクチャのシーケンスの圧縮された表現を作成
することが可能になる。本明細書中、デジタルピクチャのピクセル表現からデジ
タルピクチャの圧縮表現を製作することを、ピクチャを「エンコードする」とい
う。
【００１０】
「ハイブリッドな」ビデオコーディング方法において、時間的な冗長性は典型
的には、１つ以上の「基準ピクチャ」内のデータからエンコード中のピクチャ（
すなわち、「現在の」ピクチャ）内のブロックデータを予測することにより除去
される。エンコーダエンジン（すなわち、プロセッサ上で実行するエンコーディ
ングソフトウェアまたはマイクロコード）が現在のピクチャを圧縮している時点
では、このような基準ピクチャは既に圧縮された後であり、恐らく送信もされた
後である。しかし、これらの基準ピクチャは、後続のピクチャを圧縮する際に基
準ピクチャとして用いられる予定であるため、エンコーダエンジンがこのような
基準ピクチャを圧縮している間、エンコーダエンジンは、後で検索および基準ピ
クチャとして使用可能なよう、これらの基準ピクチャを再構成およびメモリ内に
保有する。エンコーダエンジンは、メモリ内の圧縮された基準ピクチャを再構成
することにより、エンコーダエンジンによりエンコードされたピクチャをデコー
ドすることが可能な「デコーダエンジン」をシミュレートする。これは、デコー
ダエンジンはデジタルピクチャ用の受信器の一部であり、オリジナルのピクチャ
へのアクセスを有しておらず、圧縮の結果の信号損失（すなわち劣化）を本来的
に示す再構成されたピクチャのみにアクセスを有するためである。
【００１１】
動き推定およびブロックマッチング規準
ビデオ信号は高速な動きを示すことができるため、動き推定／補償技術を用い
て、基準ピクチャ内の異なる空間オフセットにおける同一サイズのブロックによ
って現在のピクチャにおけるブロックのデータを予測することを可能とすること
により、時間的冗長性を活用することが最大限に達成される。ブロックに基づい
た動き推定／補償技術では、最適ではないのだがコスト的に効率の良いマルチメ
ディアシステムにおける実用面での理由のため、並進運動のみを仮定する。すな
わち、ブロックは移動はしたが回転はしなかったものと仮定する。したがって、
ブロックに基づいた動き推定／補償方法は、最もハイブリッドなビデオコーディ
ング方法の一部であり、ＭＰＥＧ−１［１］、ＭＰＥＧ−２［２］、Ｈ．２６１
［３］、およびＨ．２６３［４］などの全ての既存のビデオコーディング規格の
キー的要素である。動き推定は、現在のピクチャにおいて現在エンコーディング
されている「現在のブロック」に最もよく適合する基準ピクチャ内のブロックを
見付けるプロセスである。現在のピクチャに最もよく適合する基準ピクチャ内の
ブロックは、「予測因子」と呼ばれる。なぜならば、このブロックは、予測因子
ブロックに対する現在のブロックの動きおよびピクセル値を予測するからである
。
【００１２】
一例としては、多くの既存のビデオコーディング規格の場合のようにブロック
サイズが１６×１６ピクセルで、基準ピクチャ内の対応する「探索空間」（すな
わち、エンコーエィングエンジンが予測因子を探す基準ピクチャの一部分）が６
４×４８に等しいサイズである場合、動き推定のジョブは、探索空間において現
在のブロックにとって最適な予測因子である連続した１６×１６のブロックを見
付けることである。したがって、１６１７（すなわち、４９×３３）個の「候補
ブロック」、すなわち、探索空間において、現在のブロックについての予測因子
の候補である１６×１６のブロックがある。予測因子は、現在のブロックと各候
補とをマッチングさせることにより、候補の中から選択される。現在のブロック
と最もよく適合する候補が予測因子である。
【００１３】
動き推定の上記の部分を「ブロックマッチング」と呼ぶ。ブロックマッチング
は、マッチング規準を用いて行われる。典型的なマッチング規準は、ピクセル誤
差絶対値の和（ＳＡＥ）およびピクセル誤差の２乗和（ＳＳＥ）である。誤差お
よび差という言葉は、当業者にとっては同じ文脈中において同じ意味として用い
られる点に留意されたい。したがって、ＳＡＤおよびＳＡＥは、同一のブロック
マッチング計算を指す。同様に、ＳＳＤおよびＳＳＥは同じである。
【００１４】
例えば、探索空間における各オフセット（ｕ、ｖ）についてのＳＳＥは、以下
のように定義される。
【００１５】
【数１】
2006217644.tif 000003
【００１６】
ここで、Ｐcurrは現在のピクチャにおいて動き推定を用いて予測されるブロック
であり、Ｐrefは基準ピクチャの探索空間における候補ブロックであり、Ｐcurr
からベクトル（ｕ、ｖ）分だけ変位している。この実施例において６４×４８の
探索空間が現在のブロックと同心であると仮定すると、候補ブロックのオフセッ
ト範囲は、水平方向に−２４から＋２４、垂直方向に−１６から＋１６となる。
しかし、これはもちろん、本明細書中開示されている本発明の必要条件ではない
。
【００１７】
例えば、探索空間における各オフセット（ｕ、ｖ）についてのＳＡＥは、以下
のように定義される：
【００１８】
【数２】
2006217644.tif 000004
【００１９】
マッチング規準を全体的に最小化する候補ブロックが、最もよく適合するブロッ
クとして選択され、その最もよく適合するブロックに対応する現在のブロックの
座標からの変位が現在のブロックの「動きベクトル」となる。この動きベクトル
は、エンコーダエンジンにより生成された圧縮ビデオストリームから完全に復元
できるようエンコードされ、これにより、現在のピクチャの再構成の際に、規格
に対応したデコーダエンジンは動き補償を行うことができる。したがって、動き
推定の出力は、現在のブロックの動きベクトルであり、これは、予測因子の対応
する隅部の座標から現在のブロックの左上隅部分の座標への変位を示すものであ
る。
【００２０】
デジタル化されたビデオシーケンスにおいて、各ピクチャは３つの情報面から
なる。１つの面は輝度であり、２つの面はクロミナンスである。動き推定は典型
的には、輝度領域において行われるのに対し、動き補償は、ピクチャを再構成す
るために３つの面全てについて行われなければならない。各情報面は、８ビット
の数値（すなわちバイト）からなる。典型的には、輝度面の寸法は、ピクチャの
解像度と等しく、各ピクセルは独自の８ビットの輝度表現を有する。
【００２１】
例えば、ＳＳＥは、各候補について、２５６の減算、２５６の平方動作（すな
わち、乗算）、および２５５の加算を必要とする。ＳＡＥでは、上記の乗算動作
を絶対値と取り換える。計算複雑性がより低いマッチング規準は、予測能力が劣
るため、実際に用いられることはめったにない。したがって、動き推定は、ＳＡ
ＥまたはＳＳＥマッチング規準を用いても、計算集約型の動作である。さらに、
現在のピクチャにおける各ブロックについて、規準ピクチャにおいて考慮される
候補ブロックのそれぞれについてマッチング規準を計算しなければならない。Ｃ
ＣＩＲ６０１解像度（７２０×４８０）と等しいサイズのピクチャは、個別に動
き推定を受ける１３５０個のオーバラップしていない１６×１６のブロックを有
する。６４×４８のサイズの探索空間（すなわち、１６１７個の候補ブロック）
について、各候補ブロックを考慮する動き推定システムを有するエンコーダエン
ジンは、ピクチャを１秒当たり３０ピクチャのレートでエンコードしながら、ブ
ロックマッチング規準をピクチャ当たり約２，１８２，９５０（１３５０×１６
１７）回計算しなければならない。したがって、動き推定は典型的には、ハイブ
リッドビデオコーディング方法のうち最も計算集約型の要素である。
【００２２】
上述した全探索動き推定方法は、マッチング規準に対して全体的に最小のスコ
アを生成する予測因子ブロックが探索空間に配置されることを保証するが、大量
の計算能力を必要とする。この方法は、高コストなエンコーダエンジンをまかな
うことができるならばうまく働く。しかし、エンコーダエンジンがテレビ電話の
ような一般消費者システムの一部である場合、問題が生じる。このコストによる
制約により、低コストなデジタル信号プロセッサ（ＤＳＰ）またはＲＩＳＣプロ
セッサのような比較的低コストなプロセッサを用いてエンコーダエンジンを実現
することが要求され、その一方で全探索の動き推定方法の要求はその低コストプ
ロセッサの能力を超える。このような状況では、いわゆる「高速」動き推定方法
を用いなければならない。
【００２３】
高速動き推定方法
高速動き推定方法の目的は、現在のブロックと比較される候補ブロックの数を
低減することである。これらの方法の欠点は、現在のブロックと実際に最もよく
適合する候補が予測因子として選択される保証が無いということである。この方
法の最終結果は、計算サイクルが低減されることにより、ピクチャの質の低下も
しくは圧縮度の低下またはその両方が発生することである。提案される方法は、
以下のように分類することができる。
１．探索空間において、予測因子としてみなされる候補ブロックの数をヒューリ
スティックスを用いて低減する方法。このような方法の例としては、対数探索お
よび３段階探索方法がある。
２．ブロックマッチング規準を計算する際のピクセル数と、考慮される候補ブロ
ックの数とを同時に低減する階層型探索方法。これらの方法は、水平および垂直
方向に２倍の間引きまたはローパスフィルタリングを行うことにより、現在およ
び基準のピクチャの解像度を連続的に低下させる。ブロックのマッチングは、利
用可能な最低解像度で行われ、その結果は、次に高い解像度にマッピングされ、
マッピングされた最もよく適合するブロックの周囲に位置する、変位した限られ
た数のブロック候補が考慮される。
３．現在のブロックに近接するブロックの動きベクトルを用いて候補ブロックを
配置する方法。
【００２４】
前半の２つの方法のさらなる詳細については、Ｖ．Ｂｈａｓｋａｒａｎおよび
Ｋ．ＫｏｎｓｔａｎｔｉｎｉｄｅｓによるＫｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐ
ｒｅｓｓ、１９９５の「Ｉｍａｇｅ  ａｎｄ  Ｖｉｄｅｏ  Ｃｏｍｐｒｅｓｓｉ
ｏｎ  Ｓｔａｎｄａｒｄｓ」と、Ｋ．Ｒ．ＲａｏおよびＪ．Ｊ．Ｈｗａｎｇによ
るＰｒｅｎｔｉｃｅ  Ｈａｌｌ  Ｐｒｅｓｓ、１９９６の「Ｔｅｃｈｎｉｑｕｅ
ｓ  ＆  Ｓｔａｎｄａｒｄｓ  ｆｏｒ  Ｉｍａｇｅ、Ｖｉｄｅｏ、ａｎｄ  Ａｕ
ｄｉｏ  Ｃｏｄｉｎｇ」とを参照されたい。３番目の方法の例については、Ｊｕ
ｎａｖｉｔ  Ｃｈａｌｉｄａｂｈｏｎｇｓｅ、Ｓｕｎｇｏｏｋ  ＫｉｍおよびＣ
．−Ｃ．Ｊａｙ  ＫｕｏによるＰｒｏｃｅｅｄｉｎｇｓ、Ｖｉｓｕａｌ  Ｃｏｍ
ｍｕｎｉｃａｔｉｏｎｓ  ａｎｄ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ  ’９６
、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｏｃｉｅｔｙ  ｆｏｒ  Ｏｐｔｉｃａｌ  Ｅ
ｎｇｉｎｅｅｒｉｎｇ、ｖｏｌ．２７２７、ｐｐ．６４５−６５６の「Ｆａｓｔ
Ｍｏｔｉｏｎ  Ｖｅｃｔｏｒ  Ｅｓｔｉｍａｔｉｏｎ  ｆｏｒ  Ｖｉｄｅｏ  
Ｃｏｄｉｎｇ  Ｂａｓｅｄ  ｏｎ  Ｍｕｌｔｉｒｅｓｏｌｕｔｉｏｎ−Ｓｐａｔ
ｉｏ−Ｔｅｍｐｏｒａｌ  Ｃｏｒｒｅｌａｔｉｏｎｓ」を参照されたい。
【００２５】
この３段階動き推定方法は例えば、探索空間を間引きサンプリングすることに
より候補ブロック数を低減する。＋／−７の範囲の動きベクトルについては、こ
の３段階方法では３段階を１セットとして進行する。各段階において、前段階で
の候補予測因子のセットにおいて発見された最もよく適合する規準スコアに従っ
て、探索空間の位置を連続的に微調整し、残りの考慮中の候補ブロックのウィン
ドウサイズを連続的に低減する。第１の段階では最初に、原点の候補を含む基準
ピクチャにおいて現在のブロックの原点から＋／−４の範囲の空間的に対応する
オフセットで９個の候補を調べる。すなわち、考慮される９個の予測因子の座標
は、（０、０）、（４、０）、（−４、０）、（０、４）、（０、−４）、（４
、４）、（４、−４）、（−４、−４）、および（−４、４）である。最小マッ
チング規準値を有するオフセットは次に、新しい原点の周囲の＋／−２のオフセ
ットにおいて別の８個の候補を調べるための原点として用いられる。最後に、第
２段階で発見された最もよく適合するものが、＋／−１のオフセットにおける別
の８個の候補の新しい原点として用いられる。第３の段階の最後に発見された変
位は、現在のブロックの予測因子として働く。全てにおいて、この方法は典型的
には、２５個の異なるオフセット（第１段階について９個のオフセット、第２段
階について８個のオフセット、および第３段階について８個のオフセット）にお
ける候補についてマッチング規準を計算することを必要とする。この方法は、探
索空間のサイズに依存する点に留意されたい。探索空間が＋／−１５の範囲の動
きベクトルをサポートするために拡張された場合は、考慮されるオフセット数は
６５個に増加する。これは、探索空間を水平および垂直方向に４つおきに間引き
サンプリングすることにより、第１段階は４９個のオフセットからなるためであ
る。
【００２６】
別の高速動き推定方法は、上記の３段階方法と同じ原理で動作する。この対数
探索では、＋／−７の動きベクトル範囲での上記３段階探索と同じオフセットを
用いて探索空間の粗い間引きサンプリング〜細かい間引きサンプリングを行う。
しかし、＋／−１５の動きベクトル範囲については、この対数探索では、探索空
間の間引きサンプリングが＋／−８、＋／−４、＋／−２、＋／−１のオフセッ
トにおいて行われる４つの段階が必要となる。＋／−１５の動きベクトル範囲に
ついてこの方法を用いて調べた候補位置は３３個未満であるが、この方法の成績
は、良くない。なぜならば、この方法では、探索空間の局所的最小値を反映する
予測因子を発見する可能性がより大きいからである。
【００２７】
現在のブロックに近接するブロックを用いる技術のための出発地点を形成する
洞察としては、現在のブロックに密接に関連する領域が、現在のブロックと同じ
様式で移動する可能性が非常に高いことがある。したがって、密接に関連する領
域におけるブロックの動きベクトルが分かっている場合、その現在のブロックは
その動きベクトルを有している可能性が高い。従って、これらの関連するブロッ
クのうちの１つからの動きベクトルを用いて規準ピクチャ内に現在のブロックに
対する候補ブロックを配置することは道理に適っている。候補ブロックとは単に
、関連するブロックからの動きベクトルが候補ブロックに適用されると、現在の
ブロックとなるような基準ピクチャ内の位置を有する、基準ピクチャ内のブロッ
クのことである。さらなる洞察としては、デジタルピクチャにおいて、別のブロ
ックに関連するブロックはその別のブロックにごく近接して配置されやすいこと
である。この近接化は、以前にエンコードされたピクチャにおけるブロックまた
は現在のピクチャにおけるブロックのどちらにも関連し得る。したがって、現在
のブロックにごく近接するブロックを用いて配置された候補ブロックを用いて予
測因子の探索を開始するだけで、現在のブロックの予測因子を発見するために比
較されなければならないブロックの数を実質的に低減することがしばしば可能と
なる。このようなブロックは、以下において「近接」ブロックと呼ばれる。
【００２８】
Ｃｈａｌｉｄａｂｈｏｎｇｓｅらの参照文献の技術では、現在のピクチャおよ
び現在のピクチャに先行するピクチャにおける近接ブロックを用いて最適な候補
を発見し、その最適な候補をさらなる高精度化を行うための出発地点として用い
る。このさらなる高精度化では、最適な候補の周囲の８つの点を探索し、その探
索で発見された最適な候補をさらなる８つの点で用いるといった具合のことを、
マッチング結果が閾値未満に達するまで継続する。この技術に関する別の変更例
が示されており、上記参照文献ではまた、階層型探索においてこの技術をいかに
して用いるかについて開示している。
【発明の開示】
【発明が解決しようとする課題】
【００２９】
公知の動き推定技術の問題点
上述した高速動き推定技術は全て、候補ブロック数と最適な予測因子が見つか
る可能性との間の望ましくないトレードオフを生じる。さらに、どの高速動き技
術においても、一般消費者向けに構成されたデジタルシステムではメモリに厳し
い制約が有り、その結果探索空間のサイズも厳しく制約されるという点を考慮に
入れていない。詳細には、一般消費者向けに構成されたデジタルシステムでは、
ＤＳＰ内部のＲＡＭに含まれるデータ上で最も効率良く動作するデジタル信号プ
ロセッサ（ＤＳＰ）を用いる。その結果、探索空間全体をＤＳＰ内部のＲＡＭに
転送することができた場合、探索が最も効率良く行われる。このように探索空間
のサイズには制約があるため、探索技術は、探索空間が予測因子を含む可能性が
非常に大きいことを保証しなければならない。上述した方法では、探索空間にお
いてブロックのサブセットのみを候補として考慮しているため、探索空間が含ま
れている探索空間またはメモリを効率的に使用できていない。その上、上述した
方法において候補を調べる範囲を効率的に増やすための唯一の方法は、ＤＳＰ内
部のＲＡＭ量を増やすことである。したがって、上記の方法は、一般消費者向け
に構成されたシステムにおいて用いられた場合、必然的に劣った動き推定を発生
させる。
【００３０】
一度に１つの候補ブロックを、ＤＳＰ外部のメモリからＤＳＰデータＲＡＭ内
部に転送するのは実際的ではない点に留意されたい。なぜならば、隣接する候補
ブロックは共通して１５または１６ものカラム（またはロウ）を有し得、さらに
はそのような転送はリアルタイムシステムに深刻な遅延を課すからである。した
がって、所与の動作でできるだけ多くの面積の探索空間をＤＳＰデータＲＡＭ内
部へ転送する方がより効率的である。上記の問題は、階層型探索方法の場合に特
に深刻になる。上記の方法では、現在のピクチャおよび基準ピクチャのマルチ解
像バージョンのために、さらなるメモリを必要とする。上記の方法ではまた、基
準ピクチャの異なる解像度のデータを格納および検索するために、外部メモリへ
の多重アクセスを必要とする。
【００３１】
本明細書中に開示する技術の目的は、現在のブロックに対して予測因子ブロッ
クを配置する方法を提供することにより、上述した動き推定についての問題を解
消することである。この方法は、メモリの効率的な使用を必要とするエンコーデ
ィングシステムに特に良く適応されている。
【課題を解決するための手段】
【００３２】
（発明の要旨）
上記目的は、現在のブロックに近接するブロックから動きベクトルを取り、そ
の動きベクトルを現在のブロックに適用して候補ブロックを基準ピクチャ内に配
置し、そしてその候補ブロックを用いて探索空間の一部を規定することにより達
成される。上記のように規定された探索空間は概して、ブロック比較を行うため
に用いられるプロセッサの内部ＲＡＭにその全体がロードされるのに十分に小さ
いが、プロセッサの内部ＲＡＭの外部メモリへの単純な射影に限定されない。
【００３３】
本発明の別の局面は、現在の最適な候補上にセンタリングされた非矩形探索空
間を用いて予測因子ブロックの探索をさらに精製し、近接するブロックの数およ
び位置を動的に変化させて、予測因子の探索を限定するための改良された技術を
含む。これらの近接するブロックの動きベクトルを用いて、近接するブロックに
ついての動きベクトルの利用可能性と、プロセッササイクルの利用可能性と、以
前に決定された動きベクトルの数値とによって示されるように候補ブロックを配
置する。
【００３４】
本発明のさらに別の目的および利点は、以下の詳細な説明および図面を読めば
、本発明が関連する技術分野の当業者にとって明らかである。
【発明を実施するための最良の形態】
【００３５】
（詳細な説明）
図面中、参照番号は、少なくとも３桁である。右側の２桁は図面中の参照番号
であり、これらの左側の桁は、その参照符号により示されるアイテムが初出する
図面番号である。例えば、参照番号が２０３のアイテムは、図２に初出する。
【００３６】
以下の詳細な説明は、まず、好適な実施形態において、候補ブロックがどのよ
うに選択されるかを説明し、次に、この技術に従って選択された候補ブロックが
、どのように新たな技術に要求される探索空間を予測するために使用され得るか
を示す。
【００３７】
（本技術の好適な実施形態：図２）
好適な実施形態において、先ほど説明した技術は、現在のブロックについての
予測因子を２フェーズ探索する際に使用される。第１フェーズが、予測因子が探
索されるエリアを局限し、第２フェーズが、予め規定された２次元探索空間（こ
の空間の形状は、予め規定されるかまたは第１フェーズの結果によって決定され
る）内での探索の精度を高める。この探索は、適切な予測因子が見つかるとすぐ
に、いずれかのフェーズにおいて終了する。第１フェーズは、４個以上の近接ブ
ロックおよび現在のブロックの位置を使用して、基準ピクチャ内に、対応する候
補ブロックを配置する。近接ブロックは２つの特性を有する。すなわち、
・近接ブロックは、現在のブロックに、特に近く近接している。
・近接ブロックが動きベクトルを有する場合、その動きベクトルは既に計算され
ている。
現在のブロックについての予測因子であると考えられる程度に十分に近い、現在
のブロックと適合する候補ブロックが見つかった場合、探索は第１フェーズにお
いて終了する。このような候補ブロックが見つからない場合、第１フェーズにお
いて見つかった最適候補のまわりを徐々に拡張するらせんを形成する順序で、基
準ピクチャにおける候補ブロックを用いて探索が続行される。十分に近い適合す
るブロックが見つかった場合、または、第２フェーズの探索空間内の全候補ブロ
ックが現在のブロックと比較された場合のいずれかの場合に、探索は終了する。
好適な実施形態において、同時に観察した場合、候補ブロックは、ダイヤモンド
形状を形成し、このダイヤモンドの中央に、第１フェーズからの最良の候補が位
置する。
【００３８】
近接ブロックを使用して候補ブロックを配置することの利点は、第１フェーズ
において使用される近接ブロックについての動きベクトルが、第１フェーズの開
始よりも前に既知である点にある。結果的に、これらの動きベクトルを使用して
、第１フェーズについての探索空間を決定し得、この探索空間は、第１フェーズ
の開始前に、ＤＳＰの内部ＤＲＡＭにプリロードされ得る。さらに、第１フェー
ズによって提供される最良の候補ブロックは、第１フェーズについての探索空間
内に存在し、且つ、第２フェーズについての所定のサイズのダイヤモンド形状の
中心として使用されるので、第１フェーズについての探索空間は、探索空間内の
ブロックの任意のブロック上に中心を有するダイヤモンド形状を取り囲むより大
きな矩形の探索空間へと拡張され得、この拡張された探索空間は、第１フェーズ
の開始前に、ＤＳＰの内部ＤＲＡＭにプリロードされ得る。
【００３９】
（フェーズ１：図２および図６）
図２は、探索の第１フェーズについて初めに考慮される近接ブロック２０２を
示す。以下に詳細に説明するように、より多くの近接ブロックが使用され得るか
、または、他のブロックが図２の近接ブロックの代わりに用いられ得る。現在の
ブロック２０３および近接ブロック２０２を用いて、基準ピクチャ１０１の探索
空間２１９内の、現在のピクチャ２０１の現在のブロック２０３についての予測
因子が見つけられる。好適な実施形態において、現在のピクチャ２０１のエンコ
ーディングは、ラスタスキャンの順序で行われる。つまり、現在のピクチャのブ
ロックは行にエンコードされ、各行内のブロックは左から右へとエンコードされ
、行はピクチャの上端から下端へと処理される。したがって、現在のブロックを
含む行より上の行に含まれるブロックが既にエンコードされており、同様に、現
在のブロックの行内の現在のブロックの左側のブロックがエンコードされている
。これらのブロックは既にエンコードされているので、それらが有し得るいずれ
の動きベクトルも既に利用可能である。好適な実施形態において、５個の候補ブ
ロックが、最小４個の近接ブロックおよび現在のブロックを用いて見つけられ得
る。第１フェーズにおける使用のためにまず考慮された４個の近接ブロックは、
エンコードされる最後のピクチャ２２０の１つのブロック、および現在のピクチ
ャ２０１の３つのブロックである。エンコードされる最後のピクチャ２２０の１
つのブロックは、現在のブロックが現在のピクチャ２０１内に有するのと同じｘ
ｙ座標をピクチャ２２０内に有する。本明細書中、現在のブロックと同じ座標を
有する異なるピクチャ内のブロックを、「空間的に対応する」ブロックと呼ぶ。
現在のピクチャ２０１内の３つの近接ブロックは、現在のブロック２０３に「隣
接する」３つのブロックであり、既に動きベクトルを有し得る。本明細書中、「
隣接する」とは、少なくとも、現在のブロックの縁または角に接触する角を有す
ることを意味する。したがって、５つの候補ブロックを配置するために使用され
るブロックは、以下の通りである。
１．基準ピクチャの空間的対応ブロック（ＲＰＳＣＢ）２２７を配置するために
使用される、現在のブロック（ＣＢ）２０３。（ＲＰＳＣＢ２２７は、現在のブ
ロック２０３と同じｘｙ座標を有する基準ピクチャ１０１内のブロックであり、
言い換えると、基準ピクチャ１０１内のブロックであって、これに対して現在の
ブロック２０３が動きベクトル（０，０）を有するブロックである。）
２．現在のブロック２０３と同じｘｙ座標を有する最後にエンコードされたピク
チャ２２０内の、最終ピクチャの空間的対応ブロック（ＬＰＳＣＢ）２２１。
３．現在のピクチャ内の、西側の隣接ブロック（ＷＡＢ）２０５。
４．北側の隣接ブロック（ＮＡＢ）２０７。
５．北東側の隣接ブロック（ＮＥＡＢ）２０９。
【００４０】
好適な実施形態において、現在のピクチャ２０１およびエンコードされた最後
のピクチャ２２０はそれぞれ、ピクチャ内の各ブロックへのエントリを有する、
関連するルックアップテーブルを有する。動きベクトルがブロックについて計算
された場合、ブロックへのエントリは、ブロックの動きベクトルを含む。動きベ
クトルが計算されなかった場合、エントリはヌル値を含む。例えば、図２におい
て、現在のピクチャ２０１はルックアップテーブル２１０を有し、このテーブル
２１０内には近接ブロック２０２についての動きベクトルについてのエントリが
含まれる。エントリ２１３は、近接ブロック２０７についての動きベクトルを有
する。これは、北側の隣接動きベクトル（ＮＡＭＶ）である。エントリ２１５は
、近接ブロック２０９についての動きベクトルを有する。これは、北東側の隣接
動きベクトル（ＮＥＡＭＶ）である。エントリ２１７は、近接ブロック２０５に
ついての動きベクトルを有する。これは、西側の隣接動きベクトル（ＷＡＭＶ）
である。同様に、エンコードされた最後のピクチャ２２０についてのルックアッ
プテーブル２１８内に、近接ブロック２２１についての動きベクトルエントリ２
２９がある。これは、ＬＰＳＣＢ動きベクトル（ＬＰＳＣＢＭＶ）である。
【００４１】
上記５つの近接ブロックについての動きベクトルを用いて、５個の候補ブロッ
クを基準ピクチャ１０１内に配置する。候補ブロックの１つは、基準ピクチャ１
０１内のＲＰＳＣＢブロック２２７である。残り４個の候補ブロックは、現在の
ピクチャ２０１またはエンコードされた最後のピクチャ２２０内の近接ブロック
の１つについての動きベクトルを、基準ピクチャ１０１内のブロック２２７のｘ
ｙ座標（ｉ，ｊ）に適用することにより配置される。したがって、候補ブロック
２２５は、動きベクトル（ａ，ｂ）を座標（ｉ，ｊ）に適用して、候補ブロック
２２５について座標（ｉ＋ａ，ｊ＋ｂ）を得ることにより、近接ブロック２０５
からの動きベクトル（ａ，ｂ）２１７を用いて配置される。ブロック２２７に対
して動きベクトル（０，０）を有する、現在のピクチャ２０１内のブロックは、
当然現在のブロック２０３である。したがって、５個の候補ブロックは次のよう
に説明し得る。
１．基準ピクチャ１０１のＲＰＳＣＢブロック２２７。
２．動きベクトル２１７をＲＰＳＣＢ２２７の座標（ｉ，ｊ）に適用することに
より得られたオフセットにおける候補ブロック。
３．動きベクトル２１３を座標（ｉ，ｊ）に適用することにより得られたオフセ
ットにおける候補ブロック。
４．動きベクトル２１５を座標（ｉ，ｊ）に適用することにより得られたオフセ
ットにおける候補ブロック。
５．動きベクトル２２９を座標（ｉ，ｊ）に適用することにより得られたオフセ
ットにおける候補ブロック。
【００４２】
ＲＰＳＣＢ２２７に対する現在のブロック２０３の動きベクトルは、当然（０
，０）であり、実際に、現在のブロック２０３がＲＰＳＣＢ２２７に対してごく
わずか動いた場合または全く動かなかった場合に、現在のブロック２０３はＲＰ
ＳＣＢ２２７に適合する。
【００４３】
上記についての詳細は、図６に示され得る。図６は、ハイブリッド動き推定技
術の好適な実施形態の両フェーズについてのフローチャート６０１である。この
技術は、３つの閾値を含む。３つの閾値の由来を以下に説明する。直後の説明に
において、本発明者らは、フェーズ１  ６０３についてのみ取り扱う。この説明
において、丸括弧内の参照番号はフローチャート６０１内のブロックを示す。Ｓ
ＴＡＲＴ  ＨＭＥ６０４で始めると、第１のステップは、現在のブロック２０３
をＲＰＳＣＢ２２７と比較することにより、ＲＰＳＣＢ２２７に対する現在のブ
ロック２０３の動きについてテストする（６０５）。この比較が、適合基準が第
１の閾値を下回るような、現在のブロック２０３とＲＰＳＣＢ２２７との適合を
示した場合、現在のピクチャと基準ピクチャ１０１との間には、現在のブロック
２０３に対する動きはほとんどまたは全くないという、非常に高い可能性が存在
する（６０７）。この場合、ＲＰＳＣＢ２２７は現在のブロック２０３について
の予測因子であり、他の候補を試験する必要がない。したがって、矢印６０８に
よって示すように、この方法はすぐにステップ６１９へと進み、その後６２１に
おいて終了する。
【００４４】
適合基準が第１の閾値を下回らない場合、残り４個の近接ブロック２０５、２
０７、２０９、および２２１についての動きベクトルを用いて、探索空間２１９
内に候補ブロック２２５を配置する（６０９）。各候補ブロック２２５は、その
後、上で説明したように現在のブロック２０３と比較され、最良の適合ブロック
が、つまり、最も低い適合基準スコアを有するブロックが、予測因子として選択
される（６１１）。この予測因子が、第２の閾値よりも小さな適合基準スコアを
有する場合（６１３）、この予測因子は、現在のブロック２０３についての予測
因子として選択され、矢印６１５によって示されるように、この方法は、上述の
ように、ブロック６１９および６２１を介して終了する。さもなければ、この方
法は、フェーズ２  ６２３を続ける（矢印６１７）。フェーズ２について、以下
により詳細に説明する。
【００４５】
（ＬＰＳＣＢ２２１から、候補ブロックを配置する）
エンコードされた最後のピクチャ２２０は、必ずしも基準ピクチャである必要
はない。例えば、連続する双方向（Ｂ型）ピクチャがＭＰＥＧビデオデコーディ
ング規格で伝送される場合、エンコードされた最後のピクチャはＢピクチャであ
り得、したがって基準ピクチャではない。また、エンコードされた最後のピクチ
ャは、必ずしも、現在のピクチャよりも先に表示されるピクチャである必要はな
い。例えば、ＭＰＥＧビデオデコーディング規格では、予測されたピクチャ（Ｐ
型）は、Ｂピクチャよりも先に伝送されるが、Ｂピクチャよりも後に表示される
。この場合、Ｐピクチャが基準である。ＭＰＥＧビデオデコーディング規格は、
ＩＳＯ／ＩＥＣ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄ  ＩＳ  １１
１７２−２、“Ｉｎｆｏｒｍａｔｉｏｎ  ｔｅｃｈｎｏｌｏｇｙ−Ｃｏｄｉｎｇ
ｏｆ  ｍｏｖｉｎｇ  ｐｉｃｔｕｒｅｓ  ａｎｄ  ａｓｓｏｃｉａｔｅｄ  ａ
ｕｄｉｏ  ｆｏｒ  ｄｉｇｉｔａｌ  ｓｔｏｒａｇｅ  ｍｅｄｉａ  ａｔ  ｕｐ
ｔｏ  ａｂｏｕｔ  １．５  Ｍｂｉｔｓ／ｓ−Ｐａｒｔ  ２：  Ｖｉｄｅｏ”
（１９９３）、およびＩＴＵ−Ｔ  Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  Ｈ．２６２
（１９９５）、“Ｇｅｎｅｒｉｃ  ｃｏｄｉｎｇ  ｏｆ  ｍｏｖｉｎｇ  ｐｉ
ｃｔｕｒｅｓ  ａｎｄ  ａｓｓｏｃｉａｔｅｄ  ａｕｄｉｏ：  ｖｉｄｅｏ”  
（ＩＳＯ／ＩＥＣ  １３８１８−２）に、詳細に説明されている。以下に詳細に
示すように、最後のピクチャ２２０内の近接ブロック２２１から得られる候補は
、ブロック２２１の動きベクトルから直接得られ得るか、または、時間領域で、
その動きベクトルのＸＹ座標を比例的にスケーリングすることにより「計算」さ
れ得る。
【００４６】
（エンコードされた最後のピクチャ内の動きベクトルからオフセットされた候
補ブロックの計算）
以下の説明はまず、エンコードされたビデオ画像のシーケンス内で起こり得る
ピクチャ間の時間関係について説明し、その後、これらの時間関係が、ＬＰＳＣ
Ｂ２２１が近接ブロックである候補ブロック２２５を判定するために使用される
動きベクトルの計算に、どのように影響するかを説明する。
【００４７】
デジタルビデオシーケンスは、シーンがフィールド（インターレースされたピ
クチャ）またはフレーム（プログレッシブピクチャ）の連続するピクチャとして
捕捉されるカメラにおいて発生する。ピクチャは、カメラによって、特定のピク
チャレートで捕捉される。例えば、ＮＴＳＣカメラは、約６０ヘルツでフィール
ドを捕捉する。カメラからのピクチャがアナログフォーマットである場合、これ
らのピクチャはデジタル化され、エンコーダエンジンによって、要求された空間
解像度へと空間的にスケーリングされる。一旦デジタルフォーマットになると、
時間の基準は、各ピクチャと関係付けられて、他のピクチャと関連してそれが捕
捉された時間の経過を追跡し、したがって、それらの「表示順序」の維持を容易
にする。したがって、カメラによって生成される通常のシーケンスは、Ｐ1，Ｐ2
，Ｐ3，Ｐ4，Ｐ5，．．．Ｐk（下付記号はピクチャの表示順序を示す）によって
示される。
【００４８】
テレビ電話アプリケーションで用いられるような、マルチメディアシステムに
おけるリアルタイム型の費用効果が高いエンコーダエンジンは、処理能力が制限
されているので、エンコーダエンジンは、カメラがピクチャを出力する速度より
も遅い速度でピクチャをエンコードし得る。さらに、エンコーダエンジンの「速
度制御」構成要素は、その計算負荷またはその「出力バッファ」の満杯度に基づ
いて、ピクチャのエンコーディングを動的に控え得る。その結果、圧縮および伝
送されたピクチャシーケンスから得られる実際のピクチャのセットは、エンコー
ダエンジンが捨てねばならないピクチャに対応するギャップを有し得る。例えば
、圧縮されたピクチャシーケンスは、可能性としては、Ｐ1，Ｐ5，Ｐ8，Ｐ11，
Ｐ14，．．．Ｐkであり得る。というのは、
１．エンコーダエンジンは、毎秒１０ピクチャで動作するように設計（企図）さ
れており、
２．シーケンスの最初のピクチャは、動き推定によって提供される優れたデータ
低減能力の恩恵を受けないので、シーケンスの最初のピクチャが「出力バッファ
」をあふれさせるからである。
つまり、この例において、エンコーダエンジンは、３つのピクチャ毎に圧縮を行
うように設計されているが、Ｐ1は圧縮された形態でビット数が多くなるので、
エンコーダエンジンは、Ｐ2からＰ4までを無視する必要がある。その後、Ｐ5が
到着するまでに、エンコーダエンジンの「出力バッファ」は、Ｐ5の圧縮が可能
になるように十分に排出される。
【００４９】
さらに、多くのエンコーディングスキームにおいて、全てのエンコードされた
ピクチャが基準ピクチャであるわけではない。これらのスキームにおいて、この
ようなエンコードされた非基準ピクチャは、基準ピクチャの間に挿入される。こ
のようなスキームは、計算能力のより小さな、規格に対応したデコーダエンジン
によって、時間的なピクチャスケーラビィリティ（つまり、ピクチャドロッピン
グ）を可能にするか、および／または、圧縮されたデジタルビデオストリーム内
のランダムアクセスを可能にする。最後に、ピクチャがエンコードされる順序は
、それらピクチャの表示順序と異なり得る。ここでの例はＭＰＥＧであり、ＭＰ
ＥＧは、ピクチャが未来の基準ピクチャを参照できるようにすることにより、高
度な動きのあるビデオシーケンスのより効率的な圧縮を達成する。エンコーダエ
ンジンがピクチャをエンコードする順序は、ピクチャの「伝送順序」である。
【００５０】
以下のケースは、エンコードされた最後のピクチャ中の、空間的に対応するブ
ロックの動きベクトルからの候補ブロックの変位の計算を例示する。この計算は
、
１．寄与した動きベクトルの座標（ｘ，ｙ）、ならびに
２．・基準ピクチャ、
・エンコードされた最後のピクチャ、および
・現在のピクチャ
の時間関係
に依存する。
【００５１】
全てのピクチャは、エンコーダエンジンに提供された、表示順（Ｐa，Ｐb，Ｐ
c，Ｐd，Ｐe，．．．．Ｐi，Ｐj，Ｐk，．．．．）を有するシーケンスの一部で
あると仮定する。ここで、時間関係は、ａ＜ｂ＜ｃ＜ｄ＜ｅ＜．．．．ｉ＜ｊ＜
ｋ．．．であることを意味する。以下の説明を一般化するために、本発明者らは
、下付文字ｋ、ｍ、およびｖを、ｋ＜ｍ＜ｖの「表示順」条件で、しかし、ピク
チャ間の時間的相違（つまり、どれだけの時間的隔たりが存在するか）への制約
なしに用いる。
【００５２】
以下のケースの全てにおいて、計算された変位（ｎｅｗＸ，ｎｅｗＹ）の結果
、そのエリアのいずれかの部分が、許可された探索空間の境界を越えて（つまり
、許容された動きベクトルの範囲外に）はみ出した候補ブロックが得られる場合
、この候補ブロックは無視されるか、または、下で説明する「境界条件」に照ら
して適格な別の候補ブロックと交換される。
【００５３】
以下の各ケースにおいて、前の伝送されたピクチャの２つの時間関係が要求さ
れるので、計算は、３番目に圧縮されるピクチャ（つまり、「伝送順」で３番目
のピクチャ）にのみ適用可能である。
【００５４】
ケース１−表示順＝伝送順；
エンコードされた最後のピクチャは「過去の」基準ピクチャでもある
表示順のピクチャ；                      Ｐk，Ｐm，Ｐv
ピクチャの伝送順序
−現在のピクチャ；                    Ｐk，Ｐm，Ｐv  （表示順と同じ）
現在のピクチャの前に
エンコードされた最後のピクチャ；      ＿，Ｐk，Ｐm
現在のピクチャについての基準ピクチャ；  ＿，Ｐk，Ｐm
このとき、ピクチャＰvについて：
【００５５】
【数３】
2006217644.tif 000005
【００５６】
ここで、「ｆｌｏｏｒ」関数が意味する切り捨て操作の前に０．５を加えること
によって最も近い整数へ丸められる。このケースは、Ｈ．２６１およびＨ．２６
３ビデオコーディングにおいて典型的である。詳細については、ＩＴＵ−Ｔ  Ｒ
ｅｃｏｍｍｅｎｄａｔｉｏｎ  Ｈ．２６１  （１９９３）：“Ｖｉｄｅｏ  ｃｏ
ｄｅｃ  ｆｏｒ  ａｕｄｉｏｖｉｓｕａｌ  ｓｅｒｖｉｃｅｓ  ａｔ  ｐ×６４
ｋｂｉｔｓ／ｓ”、およびＤｒａｆｔ  ＩＴＵ−Ｔ  Ｒｅｃｏｍｍｅｎｄａｔｉ
ｏｎ  Ｈ．２６３  （１９９？）：“Ｖｉｄｅｏ  ｃｏｄｅｃ  ｆｏｒ  ｌｏｗ
ｂｉｔｒａｔｅ  ｃｏｍｍｕｎｉｃａｔｉｏｎｓ”を参照。
【００５７】
ケース２−表示順＝伝送順；
エンコードされた最後のピクチャおよび現在のピクチャが、同じ「過去の
」基準ピクチャを使用する
表示順のピクチャ；                      Ｐk，Ｐm，Ｐv
ピクチャの伝送順序
−現在のピクチャ；                    Ｐk，Ｐm，Ｐv  （表示順と同じ）
現在のピクチャの前に
エンコードされた最後のピクチャ；      ＿，Ｐk，Ｐm
現在のピクチャについての基準ピクチャ；  ＿，Ｐk，Ｐk
このとき、ピクチャＰvについて：
【００５８】
【数４】
2006217644.tif 000006
【００５９】
ビデオエンコーダエンジンの仕様およびシンタックスによって許容される場合、
このケースは、規格に対応したデコーダエンジンが、「後方への」時間的スケー
ラビリティについて、ＰmまたはＰvのいずれかを落とすことを可能にする。
【００６０】
ケース３−表示順および伝送順が異なる；
エンコードされた最後のピクチャおよび現在のピクチャが、同じ「未来の
」基準ピクチャを使用する
表示順のピクチャ；                      Ｐk，Ｐm，Ｐv
ピクチャの伝送順序
−現在のピクチャ；                    Ｐv，Ｐk，Ｐm
現在のピクチャの前に
エンコードされた最後のピクチャ；      ＿，Ｐv，Ｐk
現在のピクチャについての基準ピクチャ；  ＿，Ｐv，Ｐv
このとき、ピクチャＰmについて：
【００６１】
【数５】
2006217644.tif 000007
【００６２】
ビデオエンコーダエンジンの仕様およびシンタックスによって許容される場合、
このケースは、シーンの変化を示す高度な動きのあるビデオを圧縮するのに有用
である。
【００６３】
ケース４−表示順および伝送順が異なる；
ＰkがＰvに対して「過去」の基準ピクチャであり、ＰvがＰmに対して「未
来」の基準ピクチャであることを除いては、エンコードされた最後のピクチャは
基準ピクチャでもある
表示順のピクチャ；                      Ｐk，Ｐm，Ｐv
ピクチャの伝送順序
−現在のピクチャ；                    Ｐk，Ｐv，Ｐm
現在のピクチャの前に
エンコードされた最後のピクチャ；      ＿，Ｐk，Ｐv
現在のピクチャについての基準ピクチャ；  ＿，Ｐk，Ｐv
このとき、ピクチャＰmについて：
【００６４】
【数６】
2006217644.tif 000008
【００６５】
ビデオエンコーダエンジンの仕様およびシンタックスによって許容される場合、
このケースは、規格に対応したデコーダエンジンが、「後方への」時間的スケー
ラビリティについて、ＰmもしくはＰmおよびＰvの両方のいずれかを落とす（ド
ロッピングする）ことを可能にする。
【００６６】
ケース５−表示順および伝送順が異なる；
ＰvがＰkに対して「未来」の基準ピクチャであり、ＰkがＰmに対して「過
去」の基準ピクチャであることを除いては、エンコードされた最後のピクチャは
基準ピクチャでもある
表示順のピクチャ；                      Ｐk，Ｐm，Ｐv
ピクチャの伝送順序
−現在のピクチャ；                    Ｐv，Ｐk，Ｐm
現在のピクチャの前に
エンコードされた最後のピクチャ；      ＿，Ｐv，Ｐk
現在のピクチャについての基準ピクチャ；  ＿，Ｐv，Ｐk
このとき、ピクチャＰmについて：
【００６７】
【数７】
2006217644.tif 000009
【００６８】
（フェーズ１において他の近接ブロックを使用する：図３および図４）
図３に示すように、北西側の隣接ブロック３０１は、他の近接ブロック２０２
と同様の様態で、候補ブロック２２５の配置するために、フェーズ１において使
用され得る。ブロック３０１は、６番目の候補ブロックを配置するために使用さ
れ得るか、または、近接ブロック２０５、２０７、または２０９のうち１つの近
接ブロックの代わりに使用され得るかのいずれかである。後者の場合、エンコー
ダエンジンは、どの隣接ブロックが、現在のピクチャ２０1における動きベクト
ルの既に決定された各ブロックについての予測因子についての動きベクトルを提
供したかを記録しておき、この情報を使用して、４個の隣接ブロック（北西側、
北側、北東側、西側）のうちの、どの３個の隣接ブロックが、それらの動きベク
トルが、現在のブロックについての予測因子として寄与するように用いられるべ
きかを判定する。不十分な動き推定能力（つまり、見つかった最良マッチング誤
差が受け入れられない）のために、他のブロック２０５、２０７、または２０９
の１つがピクチャ内（つまりピクチャの右端部分）に無い場合、もしくは、残り
の３つの隣接ブロックの１つ（または１つ以上）に動きベクトルが存在しない場
合に、北西側のブロックは、代わりのブロックとしても機能する。
【００６９】
ハイブリッド動き推定（ＨＭＥ）法の「フェーズ１」の間に使用される近接ブ
ロック２０２のセットは、さらに、ブロック２２７、２２１、２０５、２０７、
２０９、３０１に制限されない。図４に示すように、動き推定が既に行われた現
在のピクチャにおける近接ブロックからの動きベクトルを用いることにより、追
加候補２２５が獲得され得る。これらの追加近接ブロックを、図４の、斜線領域
４０１内の６個のブロックとして示す。ＨＭＥ法の「フェーズ１」において使用
され得る近接ブロックの数に対する制約は、ＤＳＰ型エンコーディングエンジン
の計算能力、および、ＨＭＥのフェーズ２のブロックマッチング計算のためにプ
ロセッササイクルを残しておく必要性によって課せられる。近接ブロックが現在
のブロックに近いほど、同様の並進運動を示す可能性が高くなる。したがって、
好適な追加近接ブロックは、西側、北西側、北側、および北東側のブロックに隣
接するブロックである。これらの追加ブロックを斜線領域４０１として示す。エ
ンコーダエンジンが余剰のプロセッササイクルを有する場合、または、既にフェ
ーズ１において使用されている近接ブロックのどれもが候補ブロックを提供でき
ない場合、斜線で示すブロックは、ＨＭＥ法の「フェーズ１」において、近接ブ
ロックとして使用され得る。
【００７０】
（ハイブリッド動き推定のフェーズ２：図５および図６）
「フェーズ１」において見つかった最良の適合基準スコアがＴｈｒｅｓｈｏｌ
ｄ２を超える場合、探索空間のどこかに、現在のブロックに対するより良い適合
が存在し得ると仮定する。したがって、ハイブリッド動き推定法は「フェーズ２
」へと続く。「フェーズ２」において、フェーズ１によって配置された予測因子
（ここで、Ｐｒｅｄｐｈａｓｅ１と呼ぶ）を中心とする領域内で、より良好な予
測因子が探される。
【００７１】
現在のブロックに対するより良い予測因子が、Ｐｒｅｄｐｈａｓｅ１の位置の
ごく近くに存在するという仮定の下で、ＨＭＥ法を「フェーズ２」に進める。テ
レビ電話システム等の低帯域幅のアプリケーションについて、ＨＭＥ法は、（矩
形の領域ではなく）ダイヤモンド形状の領域またはエリア５０５上で、より良い
候補ブロックを探す。図５は、「１」から「２１」までの番号が付されたブロッ
クから構成された領域５０５、および、探索空間２０１における、領域５０５の
Ｐｒｅｄｐｈａｓｅ１  ５０１との関係を示す。図５において、番号「１」のブ
ロックとして示した探索エリアの中心は、１６×１６個のＰｒｅｄｐｈａｓｅ１
ブロック５０１を示す。しかし、実際には、残りのブロックが中心から１ピクセ
ル分変位しているのだが、らせん順探索の説明を単純化するために、これら残り
のブロックも１６×１６中心ブロックと同じサイズで示す。図５における寸法に
よって示すように、中心ブロックを除く全てのブロックが、１６×１６ブロック
ではなく、１ピクセル分の変位を示す。
【００７２】
「フェーズ２」の間に、矩形領域５０３がＰｒｅｄｐｈａｓｅ１上にセンタリ
ングされた場合であっても、最良の適合基準スコアを示す候補ブロックは、矩形
領域５０３によって制限されたダイヤモンド形状領域５０５内に見つかる傾向に
ある。その結果、ＨＭＥ法は、ダイヤモンド形状領域の外側に変位した候補ブロ
ックを省略することにより、追加計算を節約する。節約された計算は、その後、
ダイヤモンド形状領域を拡大するために使用され、可能性としてよりよい適合基
準スコアに至り得る追加候補ブロックを考慮することを可能にする。さらに、ダ
イヤモンド形状領域は、図５に示すように、垂直方向の位置よりも、水平方向の
候補変位を考慮して設計される。なぜなら、家庭における通常の家庭用テレビ電
話のピクチャは、カメラをパンすること（つまり、居間の中で家族のメンバーを
撮影するためにパンすること）が原因で、水平方向のような動きを示す傾向にあ
るからである。
【００７３】
ＨＭＥ法の「フェーズ２」において、ダイヤモンド形状領域内でのらせん探索
は、好適には、増加する番号ラベルで示されるような特定の順序で行われて、計
算がさらに最小化される。候補ブロックがＰｒｅｄｐｈａｓｅ１  ５０１に近づ
くほど、Ｐｒｅｄｐｈａｓｅ１  ５０１におけるスコアより良い適合基準スコア
を有する可能性が高くなる。したがって、候補ブロックは、（Ｐｒｅｄｐｈａｓ
ｅ１  ５０１から離れて）反時計回り（あるいは時計回り）のらせんの、外側に
向かう順に考慮される。
【００７４】
Ｐｒｅｄｐｈａｓｅ１  ５０１よりも良い予測因子を配置するために使用され
る方法を、図６のフェーズ２  ６２３に示す。ステップ６２５において、ダイヤ
モンド形状領域５０５が設定され、その後、現在のブロック６２９との適合につ
いての適合基準スコアが十分に低い（つまり、好適な実施形態において、ｔｈｒ
ｅｓｈｏｌｄ３よりも低い）候補が見つかるまで、または、ダイヤモンド５０５
内の全候補を調べ終わるまで、ブロック６２７、６２９、６３１、６３７から構
成されたループが実行される。前者（ブロック６３１および矢印６３３）の場合
、候補ブロックは予測因子であり、この方法は、ステップ６１９および６２１を
経て終了する。後者（ブロック６３７および矢印６４１）の場合、適合基準につ
いて最小スコアを有するフェーズ２候補ブロックが予測因子であり、この方法は
、ブロック６４３、６４５、および６２１を経て終了する。
【００７５】
ダイヤモンド５０５はＰｒｅｄｐｈａｓｅ１  ５０１上にセンタリングされる
ので、Ｐｒｅｄｐｈａｓｅ１  ５０１からの、ブロック２〜２１の変位のルック
アップテーブルによって設けられ得、フェーズ２の間に調べられる候補のアドレ
スは、このルックアップテーブルを用いて計算され得る。図２における、ダイヤ
モンド形状領域の外側の矩形５０３の斜線領域は、「フェーズ２」の間は使用さ
れないが、実際上の理由から、「フェーズ２」の実行のためにＤＳＰデータＲＡ
Ｍ内に存在することが必要な有効領域は、完全な２２×２２矩形領域５０３（４
８４バイト）である。１６×１６ブロックを超えて要求される有効エリアは、各
方向に３ピクセル分ずつ拡張したエリアである。このＤｅｌｔａは、以下に説明
する、「フェーズ１」について要求される探索空間エリアの計算に組み込まれる
。あるいは、このデータ転送は、「フェーズ１」の間にＰｒｅｄｐｈａｓｅ１  
５０１が判定された直後に、早急に処理され得る。一連のステップを用いて最終
結果を「目指す」高速動き推定法（上述）との差異として、ＨＭＥ法のさらなる
新規性は、ターゲット（Ｐｒｅｄｐｈａｓｅ１）上にマッピングされた非矩形探
索エリア、およびこの縮小された探索エリア内でのらせん順探索を用いる。
【００７６】
（フェーズ２のための、他の動作モード）
より能力の高いプロセッサおよび／または余剰のＤＳＰデータＲＡＭを使用す
る場合、ＨＭＥ法の「フェーズ２」についての探索エリアは、図２に示す特定の
領域サイズまたは形状に制限されずに、さらなる変位により増大し得る。
【００７７】
ＨＭＥ法で使用されるプロセッササイクルの数は、満足できる予測因子がどれ
だけ素早く見つかるかに応じて変化するので、本発明の異なる動作モードにおい
て、フェーズ２探索空間領域のサイズは、余剰なプロセッササイクルに基づいて
動的に変更され得る。
【００７８】
別の異なる動作モードにおいて、この領域の形状は、
１．現在のブロックに対するＰｒｅｄｐｈａｓｅ１  ５０１の位置、ならびに動
きベクトルがＰｒｅｄｐｈａｓｅ１  ５０１に寄与するブロックの相対位置、ま
たは
２．現在のブロックに対する、「フェーズ１」における候補ブロックの組の大ま
かな配向
に基づいて、予め規定された形状のセットから動的に選択されるか、または、カ
スタマイズされる。したがって、候補ブロックの組の大まかな配向のＹ成分がＸ
成分よりもかなり大きな場合、垂直方向にバイアスされたダイヤモンド形状領域
が使用される。したがって、本発明のさらなる特徴は、ダイヤモンド形状領域の
歪みおよび配向を動的に調節し得ることである。しかし、「フェーズ２」探索空
間領域の形状を動的に計算するために、「フェーズ２」探索順序のための形状お
よびその関連するルックアップテーブルを、予め規定された形状の小さなセット
から選択する動作のモードが好ましい。予め規定された形状の、ある特定の有用
なセットは、４個のダイヤモンド形状のエントリ（水平方向にバイアスされたエ
ントリ、別の垂直方向にバイアスされたエントリ、および２つの対角方向にバイ
アスされたエントリ（一方は４５度に配向され、他方は１３５度に配向される）
）からなる。
【００７９】
（Ｔｈｒｅｓｈｏｌｄ１、Ｔｈｒｅｓｈｏｌｄ２、およびＴｈｒｅｓｈｏｌｄ
３の決定）
一般に、Ｔｈｒｅｓｈｏｌｄ１、Ｔｈｒｅｓｈｏｌｄ２、およびＴｈｒｅｓｈ
ｏｌｄ３がある。この理由の１つは、一般に、プロセッサが予測因子を見つける
ためにより多くのサイクルを費やすにつれ、予測因子と現在のブロックとの間の
適合はより良くなることである。別の理由は、動きベクトルが、圧縮されたビデ
オストリームに要求されるシンタックスおよび意味的規則によって特定されるよ
うに、現在のブロックについての動きベクトルの大きさと、現在のピクチャ内の
以前にエンコードされたブロックの動きベクトルの大きさとの間の、大きさの差
としてエンコードされることである。結果的に、大きさの差が大きくなるにした
がい、ブロックの圧縮表現において、大きさを示すために、より多くのビットが
要求される。
【００８０】
各閾値は、固定された成分に、動的に決定されたΔ値を加えることにより計算
される。１６×１６個のブロックおよびＳＡＥマッチング基準を使用し、１１２
Ｋｂｓのデータレートを有する好適な実施形態において、
Ｔｈｒｅｓｈｏｌｄ１＝５１２＋Δ1
Ｔｈｒｅｓｈｏｌｄ２＝５１２＋Δ2
Ｔｈｒｅｓｈｏｌｄ３＝５１２＋Δ3
（Δ1＞Δ2＞Δ3）である。Δの値は、次のように決定される。
【００８１】
Δ1：この値はエンコーダの速度制御機構によって制御される。毎秒１５フレ
ームのＱＣＩＦ解像度ピクチャ（つまり１７６×１４４）について、１２８０の
最大値を有し得る。
【００８２】
Δ2：０．２５（Δ1−Δ3）
Δ3：ｆ（ピクチャ解像度、ピクチャレート、データレート、およびＤＳＰサ
イクル）。ここで、Δ3の値は、インターバル［０，５１２］に亘って変化し得
る。
１１２Ｋｂｓデータレートで、Ｔｈｒｅｓｈｏｌｄ１は、［５１２，１０２４］
に亘って変化し得る。
【００８３】
（境界条件）
圧縮されたいくつかのブロックについて、１つ以上の近接ブロックは、使用可
能な動きベクトルを有さないことがある。このようなケースは、近接ブロックが
現在のピクチャの境界の外側にある場合、または、不十分な動き推定能力のため
に、動きベクトルが存在しない場合（つまり、見つかった最良マッチング誤差が
受け入れられず、指定されたブロックが動き推定されずに圧縮された場合）に起
こる。近接ブロックによって特定された候補ブロックのいずれかの部分が、許可
された探索空間の境界の外側に存在する場合、同様の状況が起こる。これらの状
況の３つ全てにおいて、上述し、且つ図３および図４において説明したように、
置換近接ブロックが使用される。
【００８４】
以下は、候補ブロックが未確定である他の状態からなる。
【００８５】
・現在のブロックは、現在のピクチャの第１の「行のブロック」（つまり、Ｍ
ＰＥＧにおける第１のスライス、またはＨ．２６３におけるＧＯＢ）内にあり、
現在のピクチャは、動き推定が行われる第１のピクチャである。
【００８６】
・現在のブロックは、並列処理環境においてプロセッサに送信されたピクチャ
のあるセクション内の、第１の「行のブロック」内にある。つまり、ピクチャは
セクションに分割され、各セクションは「ブロックの行」の連続するセットであ
り、エンコーダエンジンは、各セクション上でＨＭＥ法を並列に独立して実行す
る複数のプロセッサ（例えば、Ｔｅｘａｓ  Ｉｎｓｔｒｕｍｅｎｔ  ＤＳＰ  Ｔ
ＭＳ３２０Ｃ８０）を有する。
このような場合、未確定の動きベクトルが、それぞれ（０，０）に設定されるか
、または、ハイブリッド動き推定法が、従来の高速動き推定法を用いて、これら
のブロック上で動き推定を行う。
【００８７】
（ＨＭＥ法のための、探索空間２１９の要求される部分の動的計算：図７〜図
１２）
明らかに、方法６０１のフェーズ１のために、基準ピクチャ１０１の、ＤＳＰ
の内部ＲＡＭ内に存在する必要のある部分は、フェーズ１において使用されてい
る候補ブロックを含む部分である。候補ブロックの位置は、近接ブロックの動き
ベクトルから計算し得、これらの位置は、フェーズ１の前に既知である。その結
果、本明細書中で「要求される部分」と呼ぶ、探索空間２１９の、候補ブロック
を含む部分を、フェーズ１より前に決定し得、また、フェーズ１より前にＤＳＰ
の内部ＲＡＭにロードし得る。さらに、フェーズ２に要求される探索空間の部分
は、また、候補ブロックの位置から計算し得、その結果、両フェーズについて要
求される部分は、内部ＲＡＭにロードされ得る。
【００８８】
図１２は、ビデオピクチャ符号化システム１２０１のブロック図であり、ＤＳ
Ｐ１２２３とシステム１２０１の残りの部分との関係を示す。システム１２０１
は、ビデオカメラ１２０３からアナログイメージを受け取る。これらのアナログ
イメージは、Ａ／Ｄ変換器１２０５においてデジタル表現に変換され、デジタル
化されたピクチャデータを、ＦＩＦＯメモリ１２１７を介してルーティングする
ことにより、外部ＲＡＭ１２０７に入力され、コントロールロジック１２１８に
よって制御される。コントロールロジック１２１８はまた、外部ＲＡＭ１２０７
およびＤＳＰ１２２３の動作を調整する。外部ＲＡＭ１２０７は、２つのピンポ
ン型のピクチャバッファ１２０８および１２１０を含み、このうち一方は、目下
エンコードされつつある現在のピクチャ２０１を常に含み、他方は、カメラ１２
０３から、エンコードされる次のピクチャ１２０９を受け取っている。外部ＲＡ
Ｍ１２０７は、バッファ１２１２内に、現在のピクチャ２０１をエンコードする
ために必要なデジタル基準ピクチャの再構成された表現をさらに含む。現在のピ
クチャが圧縮されると、そのデコードされた表現は、１２１２において再構成さ
れる。現在のピクチャは、次のピクチャの圧縮のために、基準ピクチャとして使
用されることが決められている。１２１２における再構成は、エンコードされた
デジタルピクチャを、エンコードしたのと同様にデコードすることにより行われ
る。探索空間２１９を有する再構成された基準ピクチャ１０１を示す。出力バッ
ファ１２１１は、それがエンコードされた状態の、圧縮された表現での現在のピ
クチャ２０１を受け取り、システムの残りの部分に対してエンコードされたピク
チャを出力する。出力バッファは、出力されずに残っている圧縮されたフォーマ
ットの、エンコードされた最後のピクチャの部分を含み得る。
【００８９】
外部ＲＡＭ１２０７のさらなる部分が、現在のピクチャ２０１をエンコードす
る際にＤＳＰ１２２３によって使用されるデータを含む。ＨＭＥ法６０１におい
て使用される閾値１２１３と、現在のピクチャ２０１およびエンコードされた最
後のピクチャ２２０についての動きベクトルのルックアップテーブル２１０およ
び２１８とが、このデータに含まれる。外部ＲＡＭ１２０７は、ＤＳＰ１２２３
がエンコーディング動作を行う場合に実行するプログラムコード１２１５を最終
的に含む。
【００９０】
ＤＳＰ１２２３は、３つの主要な構成要素（ＤＳＰハードウェア１２２７、命
令ＲＡＭ１２２９、およびデータＲＡＭ１２３１）を有する。ＤＳＰハードウェ
ア１２２７は、処理演算を実際に実行する回路を含み、命令ＲＡＭ１２２９は、
ＤＳＰプログラムコード１２１５の、実行中の動作にＤＳＰ１２２３が目下必要
とする部分を含み、データＲＡＭ１２３１は、実行中の動作において、ＤＳＰ１
２２３によって目下使用中または生成中のデータを含む。ＤＳＰ１２２３は、バ
スインターフェース（ＢＩ）１２２５を介して、アドレスバス１２１９およびデ
ータバス１２２１に接続される。アドレスバス１２１９およびデータバス１２２
１は、外部ＲＡＭ１２０７に接続される。したがって、ＤＳＰ１２２３は、ＲＡ
Ｍ１２０７からデータを読み出し、且つＲＡＭ１２０７にデータを書き込み得る
。しかし、ＲＡＭ１２０７からの読み出しおよびＲＡＭ１２０７への書き込みは
、データＲＡＭ１２３１からの読み出しおよびデータＲＡＭ１２３１への書き込
みよりもかなり遅い。その結果、ＤＳＰ１２２３を使用する最も効率的な方法は
、ＤＳＰ１２２３によって実行される特定の一連の演算に要求される全てのデー
タを、その一連の演算の開始前に、データＲＡＭ１２３１にロードすることであ
る。より詳細には、ＨＭＥ法６０１を実行するための、ＤＳＰ１２２３の効率的
な使用は、現在のブロック２０３、探索空間１２１９の要求された部分、ルック
アップテーブル２１０および２１８、ならびに閾値１２１３が、ＨＭＥ法６０１
の開始よりも前に、ＤＳＰ１２２３にロードされることを要求する。
【００９１】
図７は、要求された部分７０１、ならびに、要求された部分７０１の、探索空
間２１９および５個の候補ブロック２２５（１．．．５）との関係を示す。候補
ブロック２２５（１）は、現在のブロック２０３に空間的に対応する、基準ピク
チャのブロック２２７である。残りの候補ブロックを配置するために使用される
動きベクトルを、ブロックの丸括弧内に書き込んだ。部分７０１を確立する際の
第１のステップは、全ての候補ブロックが部分７０１に含まれる必要のある場合
に必要な境界を決定することである。通常、隣接ブロックの動きベクトルは高い
相関関係を有するので、全ての候補ブロックを含む部分７０１は、ＤＳＰデータ
ＲＡＭに収まる程度に十分小さな、基準ピクチャ１０１の探索空間２１９内の単
一のエリアである。このような場合、図７に示すように、外部ＲＡＭ１２０７か
ら内部データＲＡＭ１２３１へと要求された部分７０１を移動するのに、一回の
転送で済む。しかし、候補ブロックの間の相違が大きいことが原因で、計算され
た探索空間エリアが大きい場合、単一の矩形であり、且つ、内部ＤＳＰデータＲ
ＡＭに収まる程度に十分小さな部分７０１は存在し得ない。この場合、収まる程
度に十分小さな要求された部分７０１は、探索空間２１９の、２個以上の、連続
しない、ひょっとしたら重なり合っているかもしれない矩形セクションから構成
される。この場合、各矩形セクションは、外部メモリから内部ＤＳＰデータＲＡ
Ｍへと別個に転送する必要がある。以下、全ての候補を含む探索空間２１９にお
いて、２個の最小サイズの矩形を配置する方法について説明する。ほとんど全て
のケースにおいて、２個の最小サイズの矩形は、ＤＳＰの内部ＲＡＭに同時に収
まる程度に十分小さい。
【００９２】
探索空間エリア計算法の、パート２の結果のあり得る例を、図８〜図１１に示
す。図８において、探索空間の、未使用の垂直矩形セクションは、探索空間の上
端から下端へと延びる。このようなセクションをセクションＶと呼ぶ。要求され
た矩形領域Ｂ  ８０３の左側に対する、要求された矩形領域Ａ  ８０１の右側の
位置は変動し得る。矩形領域は、交差するか、バラバラにされるか（つまり、こ
れら領域の間に、別の未使用の垂直矩形セクションが存在し得る）、または、図
示のように、一致した辺を有する。したがって、３個までの未使用垂直矩形セク
ションが存在し得る（１つは領域Ａの左、１つは領域の間、もう１つは領域Ｂの
右）。セクションＮＷ、ＮＥ、ＮＥ、およびＳＥは、サイズが変動する。セクシ
ョンＮＷ、ＮＥ、ＮＥ、およびＳＥのいずれかは存在しないことがあり得る。候
補ブロックＲＰＳＣＢ２２７は、常に、２個の要求された領域８０１および８０
３の一方によって取り囲まれる。
【００９３】
同様に、計算された探索空間エリアは、１個以上の未使用水平矩形セクション
になり得る。図９は、探索空間の左側から右側へと延びるセクションＨ１および
Ｈ２を示す。図９はまた、要求された領域８０１および８０３が互いに関連し得
る、つまり、要求された領域８０１および８０３が交差部９０５を有する、多く
の様態のうちの１つを示す。要求された領域８０１および８０３が互いに関連し
得る他の２つの様態を、図１０および図１１に示す。
【００９４】
（探索空間２１９の要求された部分７０１を計算する方法）
要求された部分７０１は、ＨＭＥ法のフェーズ１の間に、ある手法を用いて計
算される。この手法では、まず、単一の矩形から構成された、要求された部分７
０１を計算し、単一の矩形がＤＳＰの内部ＲＡＭに収まらないほど大きな場合は
、２つの最小の矩形の要求された領域８０１および８０３から構成された要求さ
れた部分７０１を計算する。
【００９５】
パート１−単一矩形エリア計算法
１．各フェーズ１候補ブロック２２５を見つけ、探索空間２１９にマッピング
する。候補ブロック２２５の座標が、その左上隅に対応する（つまり、動きベク
トルがブロックの左上隅を指す）ことを思い出されたい。
【００９６】
２．候補２２５のＸ成分およびＹ成分の極値を見つける。
【００９７】
３．以下に示す１組の式を用いて、候補２２５の境界を形成する矩形領域の範
囲を見つける。
【００９８】
ｎｅｗ＿Ｘ＿ｍｉｎ  ＝  ｍｉｎ＿Ｘ−Ｄｅｌｔａ
ｎｅｗ＿Ｘ＿ｍａｘ  ＝
ｍａｘ＿Ｘ  ＋  Ｘ＿ｂｌｏｃｋ＿ｄｉｍｅｎｓｉｏｎ  ＋  Ｄｅｌｔａ  
ｎｅｗ＿Ｙ＿ｍｉｎ  ＝  ｍｉｎ＿Ｙ−Ｄｅｌｔａ
ｎｅｗ＿Ｙ＿ｍａｘ  ＝
ｍａｘ＿Ｙ  ＋  Ｙ＿ｂｌｏｃｋ＿ｄｉｍｅｎｓｉｏｎ  ＋  Ｄｅｌｔａ  
図７は、これらの式の項が、要求された部分７０１にどのように関係するかを示
す。Ｄｅｌｔａは、ＨＭＥ法のフェーズ２において使用されるエリア５０３を収
容するために、要求された部分７０１に追加される余分な量である。要求された
部分７０１が探索空間２１９の境界または基準ピクチャ１０１の周囲の外側には
み出さないように、Ｄｅｌｔａは、必要な場合には、適切に切り取られる（値が
減少される）。好適な実施形態において、Ｄｅｌｔａ＝３である。
【００９９】
４．得られた、要求された部分７０１が、内部ＤＳＰデータＲＡＭに収まる程
度に十分小さい場合、矩形領域をＤＳＰデータＲＡＭに転送する旨の要求が発送
され、要求された部分７０１を計算する方法は、この時点で終了する。そうでな
い場合、この方法は以下に示すように継続する。
【０１００】
パート２−２個の矩形エリアについての、候補ブロッククラスタリング法
パート２は、静的クラスタリング法と同様である。しかし、サンプルを集合体
にまとめる従来の方法は、サンプルの、集合体の重心への距離に依存する。サン
プルは点であり、集合体はそれらの重心（集合体の構成要素（つまりサンプル）
の平均）によって表現される。本発明者らのサンプルは、矩形領域に集める必要
のあるブロック（２−Ｄエリア）であり、必ずしも、最小総面積の要求された部
分７０１となる２つの矩形エリアを形成しないので、この平均化の効果は望まし
くない。
【０１０１】
５．大きく離れた２つの候補ブロック２２５（Ｂ１およびＢ２）を見つけ、そ
れらを初期ガイドに指定して、残りのフェーズ１候補ブロック２２５を集める。
この時点で、Ｂ１およびＢ２は、探索空間の、２つの別個の矩形領域８０１およ
び８０３（Ｒ１およびＲ２）として機能する。探索空間は、大きくなって、残り
のフェーズ１候補ブロック２２５を組み込む。好適な実施形態において、５個の
フェーズ１候補ブロック２２５があるので、２つの矩形領域のうちの一方に、３
つの候補をマッピングする必要がある。各候補ブロック２２５は、左上隅の座標
によって規定される。矩形領域８０１および８０３の各々は、その面積ならびに
各領域に集められた候補のＸ成分およびＹ成分の極値から構成された４つの隅に
よって規定される。つまり、矩形領域の左上隅は（Ｘｍｉｎ，Ｙｍｉｎ）に位置
し、右下隅は（Ｘｍａｘ，Ｙｍａｘ）に位置し、左下隅は（Ｘｍｉｎ，Ｙｍａｘ
）に位置し、右上隅は（Ｘｍａｘ，Ｙｍｉｎ）に位置する。
【０１０２】
６．残りの（つまり、マッピングされていない）候補ブロック２２５それぞれ
から、Ｂ１およびＢ２への距離を計測する。これは、Ｒ１およびＲ２が、当初は
、それぞれＢ１およびＢ２に相当する点であるからである。
【０１０３】
７．矩形領域への最小距離を示す候補は、その領域に集められる。しかし、複
数の候補が、所与の矩形領域への同じ最小距離を示す場合、各候補は、それぞれ
の矩形領域に集められる。
【０１０４】
８．修正された矩形領域の４隅の座標は、吸収された候補のＸおよびＹ成分を
、矩形領域の前の極値と比較することにより計算される。修正された矩形領域の
面積が計算される。Ｒ１およびＲ２の一方または両方が、ステップ７に依存して
修正され得る。
【０１０５】
９．いずれかの候補が、２つの矩形領域の一方にマッピングされずに残った場
合、ステップ１０へと続く。そうでない場合は、終了する。
【０１０６】
１０．残りの候補Ｂiの各々について：
ＢiがＲ１に追加される場合に得られる面積を計算する。
【０１０７】
ＢiがＲ２に追加される場合に得られる面積を計算する。
【０１０８】
１１．矩形領域に集められることによってその矩形領域に加えられる増加面積
が最小である候補ブロックが、その矩形領域に集められる。しかし、複数の候補
ブロックが同じ最小増加面積を示す場合、各々がそれぞれの矩形領域に集められ
る。
【０１０９】
１２．修正された矩形領域の４隅は、吸収された候補のＸおよびＹ成分を、矩
形領域の前の極値と比較することにより計算される。修正された矩形領域の新た
な面積が保存される。Ｒ１およびＲ２の一方または両方が、ステップ１１に依存
して修正され得る。
【０１１０】
１３．候補のいずれかが、２つの矩形領域の一方にマッピングされずに残った
場合、ステップ１０へ進む。
【０１１１】
１４．ステップ３の式を適用することにより、Ｒ１およびＲ２によって境界が
定められた探索空間エリアの矩形領域は、それぞれ、各方向に延びる。
【０１１２】
パート２は、最も小さな総面積（つまり、ＤＳＰデータＲＡＭに転送するのに
要求される最小データ量）となる要求された探索空間エリアの２つの矩形領域の
計算を保証する。この保証を提供しない本発明の異なる態様において、矩形領域
の増加面積ではなく、候補と矩形エリアの最も近い隅との距離が、クラスタリン
グの基準として使用される。単純であるが、最小総面積を生成する可能性がより
低い本発明の第３の異なる態様において、ステップ７からステップ１３は、１つ
のステップに置き換えられる。すなわち、残りの候補の各々は、Ｂ１およびＢ２
の最も近い方にマッピングされるというステップである。探索空間の複数の矩形
領域を連続的に転送する必要がある場合、（０，０）オフセットを含む領域が、
常に最初に転送される。
【０１１３】
あまり一般的ではないが、ＨＭＥ法のいくつかのインプリメンテーション（つ
まり、極めて大きな探索領域）は、外部メモリから内部ＤＳＰデータＲＡＭへと
３回以上転送することを要求する。このような場合、探索空間の複数の矩形セク
ションを運ぶために、連続して転送を行う必要がある。最悪の場合、矩形領域の
集合体が内部ＤＳＰデータＲＡＭに収まらない場合、残りの候補のために要求さ
れる探索空間は、探索空間のサブセットの候補についてマッチング基準の計算を
行う間に、内部データＲＡＭに転送され得る。本明細書中、ちょうど説明した要
求された部分７０１を計算する方法は、候補ブロックを配置するために使用され
る近接ブロックの動きベクトルの大きさに対していかなる制限も課さないことに
留意されたい。
【０１１４】
上記の説明から明らかなように、上述の、探索空間２１９の要求された部分７
０１の面積を計算する方法は、ＤＳＰの内部ＤＲＡＭと共に使用することに限定
されず、探索空間のいくつかの部分を、比較を行っているプロセッサによりアク
セス可能なメモリへと移動させるのが有利ないかなる状況においても使用し得る
。
【０１１５】
（結論）
上記の「詳細な説明」は、「詳細な説明」に開示された動き検出の技術が関連
する分野の当業者に、本発明者らが現在知っている、本発明の技術の実行のベス
トモードを開示した。本発明の技術が関連する分野の当業者にすぐにわかるよう
に、本発明の技術の、他の多くのインプリメンテーションが可能である。正確な
インプリメンテーションは、当然、使用されるエンコーディングスキームおよび
エンコーディングを行うのに使用されるハードウェアに依存する。所与のインプ
リメンテーションにおいて本方法についての閾値を決定する様態は、エンコーデ
ィングスキーム、ハードウェア、およびエンコーディングが行われるアプリケー
ションの種類に依存する。
【０１１６】
他の変形例は以下を含む。ブロックの時間的予測は、必ずしも、基準ピクチャ
内の同じサイズのブロックから得る必要はない。したがって、ブロックのいくつ
かの部分（例えば、４分の１の部分）は、基準ピクチャ内の等しい寸法のサブブ
ロックから時間的に予測され得る。さらに、現在のブロックについての予測因子
は、必ずしも、単一の基準ピクチャから得る必要はなく、いくつかの基準ピクチ
ャから得られた予測因子から最良の予測因子を選択することにより生成され得る
。あるいは、予測因子は、例えば、荷重平均を用いることにより、基準ピクチャ
からの予測因子を組み合わせることによって生成され得る。さらに、エンコーダ
エンジンは、元のピクチャ、または、それらをエンコーディングしたものから再
構成されたピクチャのいずれかである基準ピクチャを用い得る。しかし、規格に
対応したデコーダエンジンがピクチャの展開および再構成の間に生成するのと等
価なデジタルエラー信号を生成するためには、エンコーダエンジンは、再構成さ
れたバージョンの基準ピクチャを用いる必要がある。さらに、予測因子を見つけ
るために比較される領域は、形状が矩形である必要はなく、動的に近接ブロック
を選択し、探索の第２のフェーズにおいて使用されるエリアを形成する情報は、
インプリメンテーションによって異なる。
【０１１７】
「詳細な説明」は、動き推定技術のインプリメンテーションを１つしか記載し
ておらず、動き推定技術の原理を組み込んだ他の多くのインプリメンテーション
が可能であるので、「詳細な説明」は、あらゆる点で例示的であり、制限的では
ないと理解する必要があり、本明細書中に開示された本発明の範囲は、「詳細な
説明」から決定されるのではなく、特許法によって許可される最大限の範囲で解
釈された請求の範囲から決定されることは明らかである。
【図面の簡単な説明】
【０１１８】
【図１】デジタルピクチャエンコーディングの概要を提供する図である。
【図２】好適な実施形態において用いられる近接ブロックおよび候補ブロックを示す図である。
【図３】現在のピクチャにおける近接ブロックを示す図である。
【図４】現在のピクチャにおけるさらなる近接ブロックを示す図である。
【図５】ＨＭＥ方法の第２フェーズにおける候補ブロックを示す図である。
【図６】ＨＭＥ方法の好適な実施形態のフローチャートである。
【図７】探索空間の必要部分を示す図である。
【図８】必要部分の計算を示す第１の図である。
【図９】必要部分の計算を示す第２の図である。
【図１０】必要部分の計算を示す第３の図である。
【図１１】必要部分の計算を示す第４の図である。
【図１２】好適な実施形態が実現されるエンコーディングシステムの関連部分のブロック図である。
【図１】
2006217644.tif 000010
【図２】
2006217644.tif 000011
【図３】
2006217644.tif 000012
【図４】
2006217644.tif 000013
【図５】
2006217644.tif 000014
【図６】
2006217644.tif 000015
【図７】
2006217644.tif 000016
【図８】
2006217644.tif 000017
【図９】
2006217644.tif 000018
【図１０】
2006217644.tif 000019
【図１１】
2006217644.tif 000020
【図１２】
2006217644.tif 000021