(57)【特許請求の範囲】
【請求項１】
一連のフレームによってビデオシーケンスを表すデジタルビデオシステム圧縮フォーマットであって、該一連のフレームは前フレームおよび該前フレームに続く現フレームを含み、該一連のフレームは全て所定の時間間隔で分離されており、該一連のフレームのそれぞれは所定の位置を持つ複数のブロックに分割され、前記各ブロックは所定の輝度画素データマトリクスを含む同じサイズを有する、デジタルビデオシステム圧縮フォーマットにおいて、前記現フレームにおける前記一連のブロック内の輝度画素データマトリクスによって表される画像における前記各ブロックの、前記前フレームにおける対応するブロックサイズの該輝度画素データマトリクスからの位置変化をサーチする方法であって、
ａ）現フレーム内で第１のブロックを選択するステップと、
ｂ）該現フレーム内の該第１のブロックに対応する初期候補マトリクスとして、前記前フレーム内の前記第１のブロックと同じブロックサイズの輝度画素データマトリクスを選択し、選択された前記初期候補マトリクスの輝度画素データと、前記第１のブロックの輝度画素データとの差の絶対値の和（ＳＡＤ）を計算することにより初期動きサーチポイントのＳＡＤ（ＳＡＤ＿ｉｎｉｔ）を導出するステップと、
ｃ）前記第１のブロックよりも前にサーチされた所定の個数のブロック間の前記ＳＡＤの平均値を短期平均値（ＳＡＤ ａｖｅ）として求めるステップと、
ｄ）前記初期候補マトリクスの周囲に位置する輝度画素データマトリクスのブロックをサーチウィンドウと規定するステップと、
ｅ）該サーチウィンドウの各ブロックから、前記第１のブロックの輝度画素データに最も近い輝度画素データを有するブロックを見つけて、見つけられたブロックの中心と前記初期候補マトリクスの中心との間の間隔を低減するための処理を、規定される反復回数（ＭＥ＿ｓｔｅｐ）にわたって実施することによって、前記サーチウィンドウサイズを変化させるステップと、
ｆ）ステップｅ）において、前記サーチウィンドウサイズから最終的に見つけられたブロックと前記第１のブロックとの位置を比較するステップとを包含し、
前記ステップｅ）において、前記短期平均値（ＳＡＤ ａｖｅ）が、複数フレーム間における前記ＳＡＤの平均値である長期平均値（ＳＡＤ ａｖｅＬＴ）より所定量大きい場合には、予め設定された平均反復回数（Ｍｅ ｓｔｅｐＡＶＥ）を増加させ、前記短期平均値（ＳＡＤ ａｖｅ）が前記長期平均値（ＳＡＤ ａｖｅＬＴ）より所定量小さい場合には、前記平均反復回数（Ｍｅ ｓｔｅｐＡＶＥ）を減少させる処理を行った後、前記初期動きサーチポイントのＳＡＤ（ＳＡＤ ｉｎｉｔ）が前記短期平均値（ＳＡＤ ａｖｅ）より小さい場合には、前記平均反復回数（Ｍｅ ｓｔｅｐＡＶＥ）から所定の値を引いた値を前記反復回数（ＭＥ＿ｓｔｅｐ）とし、前記初期動きサーチポイントのＳＡＤ（ＳＡＤ ｉｎｉｔ）が前記短期平均値（ＳＡＤ ａｖｅ）より大きい場合には、前記平均反復回数（Ｍｅ ｓｔｅｐＡＶＥ）から所定の値を足した値を前記反復回数（ＭＥ＿ｓｔｅｐ）とすることを特徴とする方法。
【請求項２】
前記ステップｅ）において、前記第１のブロックの輝度画素データに最も近い輝度画素データを有するブロックを、前記サーチウィンドウの各ブロックのそれぞれと、前記第１のブロックとの前記ＳＡＤの計算を行うことによって見つけるようになっている、請求項１に記載の方法。
【請求項３】
前記ステップｆ）の後に、
ｇ）該ステップｆ）にて最終的に見つけられたブロックと前記第１のブロックとの前記ＳＡＤを最小ＳＡＤ（ＳＡＤ ｍｉｎ）として求めて、求められた前記最小ＳＡＤ（ＳＡＤ ｍｉｎ）で前記長期平均値（ＳＡＤ ａｖｅＬＴ）を更新するステップをさらに包含する、請求項２に記載の方法。
【請求項４】
前記ステップｇ）において、前記最小ＳＡＤ（ＳＡＤ ｍｉｎ）にて前記短期平均値（ＳＡＤ ａｖｅ）を更新するステップをさらに包含する、請求項３に記載の方法。
【請求項５】
前記ステップｇ）において、１フレーム内のブロック数に応じて前記短期平均値（ＳＡＤ ａｖｅ）をさらに更新する、請求項４に記載の方法。
【請求項６】
前記ステップｇ）において、複数のフレーム内の合計ブロック数に応じて前記長期平均値（ＳＡＤ ａｖｅＬＴ）をさらに更新する、請求項４に記載の方法。
【請求項７】
前記ステップｆ）の後に、前記ステップａ）〜ｆ）の処理が繰り返される構成であって、前記ステップｆ）の後に実施されるステップａ）において、前記第１ブロックに隣接するブロックを第１ブロックとし、該ステップａ）に続くステップｂ）において、該ステップａ）の前段の前記ステップｆ）にて該第１ブロックについて以前に予測された位置変化に応じて前記初期候補マトリクスが選択される、請求項１に記載の方法。
【請求項８】
前記ステップａ）において前記現フレームの最後のブロックが第１のブロックとされ、前記ステップｆ）の後に、前記ステップａ）〜ｆ）の処理が繰り返される構成であって、
前記ステップｆ）の後に実施されるステップａ）において、前記現フレームに連続するフレームの最初のブロックが第１のブロックとされ、
該該ステップａ）に続くステップｂ）において、該ステップａ）の前段の前記ステップｆ）にて該第１のブロックについて以前に予測された位置変化に応じて前記初期候補マトリクスが選択される、請求項１に記載の方法。
【請求項９】
前記ステップｄ）において、前記サーチウィンドウは、前記初期候補マトリクスと、該初期候補マトリクスの周囲に位置する８個のブロックとによって構成される、請求項１に記載の方法。
【請求項１０】
前記ブロックはそれぞれ１６×１６個の輝度画素データマトリクスを含むマクロブロックであり、前記反復回数（ＭＥ＿ｓｔｅｐ）は最大５である、請求項１に記載の方法。
【請求項１１】
前記ステップｇ）の後に、前記ステップａ）〜ｇ）の処理が繰り返される構成であって、該繰り返されるステップｇ）において、求められた前記最小ＳＡＤ（ＳＡＤ ｍｉｎ）と、更新された前記短期平均値（ＳＡＤ ａｖｅ）と、１フレーム内のマクロブロック数（ｎｕｍＭＢ）と、前段のステップｇ）にて求められた前記短期平均値（ＳＡＤ ａｖｅ）０とに基づいて、前記短期平均値（ＳＡＤ ａｖｅ）が、
（ＳＡＤ＿ａｖｅ）＝（（ｎｕｍＭＢ−１）（ＳＡＤ＿ａｖｅ）0＋ＳＡＤ＿ｍｉｎ）／ｎｕｍＭＢ
によって更新される、請求項５に記載の方法。
【請求項１２】
前記繰り返されるステップｇ）において、前記マクロブロックの位置変化評価（ＳＡＤ  ｖａｒ）が、
（ＳＡＤ＿ｖａｒ）＝√［（（ｎｕｍＭＢ−１）＊（（ＳＡＤ＿ｖａｒ）0）2＋（（ＳＡＤ＿ｍｉｎ）−（ＳＡＤ＿ａｖｅ））2）／ｎｕｍＭＢ］
によって求められる、請求項１１に記載の方法。
【請求項１３】
前記繰り返されるステップｇ）において、前段のステップｇ）にて更新された長期平均値を（ＳＡＤ ａｖｅＬＴ）０とすると、前記長期平均値（ＳＡＤ ａｖｅＬＴ）が、
（ＳＡＤ＿ａｖｅＬＴ）＝（（ｎｕｍＭＢｓＬＴ−１）（ＳＡＤ＿ａｖｅＬＴ）0＋ＳＡＤ＿ｍｉｎ）／ｎｕｍＭＢｓＬＴ
によって更新される、請求項６に記載の方法。
【請求項１４】
前記ステップｅ）において、前記反復回数（ＭＥ＿ｓｔｅｐ）が、
１）（ＳＡＤ＿ｉｎｉｔ）＜（ＳＡＤ＿ａｖｅ）−（ＳＡＤ＿ｖａｒ）である場合には、  （ＭＥ＿ｓｔｅｐ）＝（ＭＥ＿ｓｔｅｐＡＶＥ）−２、
２）（ＳＡＤ＿ｉｎｉｔ）＜（ＳＡＤ＿ａｖｅ）である場合には、
（ＭＥ＿ｓｔｅｐ）＝（ＭＥ＿ｓｔｅｐＡＶＥ）−１、
３）（ＳＡＤ＿ｉｎｉｔ）＜（ＳＡＤ＿ａｖｅ）＋（ＳＡＤ＿ｖａｒ）である場合には、  （ＭＥ＿ｓｔｅｐ）＝（ＭＥ＿ｓｔｅｐＡＶＥ）、
４）（ＳＡＤ＿ｉｎｉｔ）＜（ＳＡＤ＿ａｖｅ）＋２（ＳＡＤ＿ｖａｒ）である場合には、
（ＭＥ＿ｓｔｅｐ）＝（ＭＥ＿ｓｔｅｐＡＶＥ）＋１、
５）前記１）〜４）以外の場合には、
（ＭＥ＿ｓｔｅｐ）＝（ＭＥ＿ｓｔｅｐＡＶＥ）＋２
によって求められる、請求項１２に記載の方法。
【請求項１５】
前記平均反復回数（ＭＥ＿ｓｔｅｐＡＶＥ）は４の値で初期化され、前記平均反復回数（ＭＥ＿ｓｔｅｐＡＶＥ）が
１）（ＳＡＤ＿ａｖｅ）＞ａ0（ＳＡＤ＿ａｖｅＬＴ）／ａ1である場合には、
（ＭＥ＿ｓｔｅｐＡＶＥ）＝（ＭＥ＿ｓｔｅｐＡＶＥ）＋１、
２）（ＳＡＤ＿ａｖｅ）＜ａ2（ＳＡＤ＿ａｖｅＬＴ）／ａ1である場合には、
（ＭＥ＿ｓｔｅｐＡＶＥ）＝（ＭＥ＿ｓｔｅｐＡＶＥ）−１
（但し、ａ0＞ａ1＞ａ2＞０）
によって求められる、請求項１に記載の方法。
【請求項１６】
前記ａ0の値が１０であり、前記ａ1の値が８であり、前記ａ2の値が７である、請求項１５に記載の方法。
【請求項１７】
前記ステップｅ）において、前記見つけられたブロックの中心と前記初期候補マトリクスの中心との間の間隔は、前記各中心同士を分離する画素数をｓとすると、
ｓ＝２(ME step-1)
として計算されて、計算されたｓの値を２で割って得られる画素数が反復処理の度に低減される、請求項１に記載の方法。
【請求項１８】
一連のフレームによってビデオシーケンスを表すデジタルビデオシステム圧縮フォーマットであって、該一連のフレームは前フレームおよび該前フレームに続く現フレームを含み、該一連のフレームは全て所定の時間間隔で分離されており、該一連のフレームのそれぞれは所定の位置を持つ複数のブロックに分割され、前記各ブロックは所定の輝度画素データマトリクスを含む同じサイズを有する、デジタルビデオシステム圧縮フォーマットにおいて、前記現フレームにおける前記一連のブロック内の輝度画素データマトリクスによって表される画像における前記各ブロックの、前記前フレームにおける対応するブロックサイズの該輝度画素データマトリクスからの位置変化をサーチする方法であって、
ａ）現フレーム内で第１のブロックを選択するステップと、
ｂ）該現フレーム内の該第１のブロックに対応する初期候補マトリクスとして、前記前フレーム内の前記第１のブロックと同じブロックサイズの輝度画素データマトリクスを選択し、選択された前記初期候補マトリクスの輝度画素データと、前記第１のブロックの輝度画素データとの差の絶対値の和（ＳＡＤ）を計算することにより初期動きサーチポイントのＳＡＤ（ＳＡＤ＿ｉｎｉｔ）を導出するステップと、
ｃ）前記第１ブロックよりも前にサーチされた所定の個数のブロックのそれぞれの前記ＳＡＤの平均値を短期平均値（ＳＡＤ ａｖｅ）として求めるステップと、
ｄ）前記初期候補マトリクスの周囲に位置する輝度画素データマトリクスのブロックをサーチウィンドウと規定するステップと、
ｅ）該サーチウィンドウの各ブロックから、前記第１のブロックの輝度画素データに最も近い輝度画素データを有するブロックを見つけて、見つけられたブロックの中心と前記初期候補マトリクスの中心との間の間隔を低減するための処理を、反復回数（ＭＥ＿ｓｔｅｐ）にわたって実施することによって、前記サーチウィンドウサイズを変化させるステップと、
ｆ）ステップｅ）において、前記サーチウィンドウサイズから最終的に見つけられたブロックと前記第１のブロックとの位置を比較するステップとを包含し、
前記ステップｅ）において、前記第１のブロックに隣接するブロックに対するサーチによって、または、前記前フレーム内の前記第１のブロックに対するサーチによって、見つけられたブロックについて以前に予測された位置変化に応じて前記初期候補マトリクスが選択され、
前記ステップｅ）において、前記短期平均値（ＳＡＤ ａｖｅ）が、複数フレームにおける前記ＳＡＤの平均値である長期平均値（ＳＡＤ ａｖｅＬＴ）より所定量大きい場合には、予め設定された平均反復回数（Ｍｅ ｓｔｅｐＡＶＥ）を増加させ、前記短期平均値（ＳＡＤ ａｖｅ）が前記長期平均値（ＳＡＤ ａｖｅＬＴ）より所定量小さい場合には、前記平均反復回数（Ｍｅ ｓｔｅｐＡＶＥ）を減少させる処理を行った後、初期動きサーチポイントのＳＡＤ（ＳＡＤ ｉｎｉｔ）が前記短期平均値（ＳＡＤ ａｖｅ）より小さい場合には、前記平均反復回数（Ｍｅ ｓｔｅｐＡＶＥ）から所定の値を引いた値を前記反復回数（ＭＥ＿ｓｔｅｐ）とし、初期動きサーチポイントのＳＡＤ（ＳＡＤ ｉｎｉｔ）が前記短期平均値（ＳＡＤ ａｖｅ）より大きい場合には、前記平均反復回数（Ｍｅ  ｓｔｅｐＡＶＥ）から所定の値を足した値を前記反復回数（ＭＥ＿ｓｔｅｐ）とすることを特徴とする方法。
【請求項１９】
前記ステップｅ）において、前記第１のブロックの輝度画素データに最も近い輝度画素データを有するブロックを、前記サーチウィンドウの各ブロックのそれぞれと、前記第１のブロックとの前記ＳＡＤの計算を行うことによって見つけるようになっている、請求項１８に記載の方法。
【請求項２０】
前記ステップｆ）の後に、
ｇ）該ステップｆ）にて最終的に見つけられたブロックと前記第１のブロックとの前記ＳＡＤを最小ＳＡＤ（ＳＡＤ  ｍｉｎ）として求めて、該最小ＳＡＤ（ＳＡＤ  ｍｉｎ）にて前記短期平均値（ＳＡＤ ａｖｅ）を更新するステップをさらに包含する、請求項１９に記載の方法。
【請求項２１】
前記ステップｇ）の後に、
ｉ）前記ステップｇ）で求められた前記最小ＳＡＤ（ＳＡＤ  ｍｉｎ）で前記長期平均値（ＳＡＤ ａｖｅＬＴ）を更新するステップをさらに包含する、請求項２０に記載の方法。
【請求項２２】
前記ステップｇ）において、１フレーム内のブロック数に応じて前記短期平均値（ＳＡＤ  ａｖｅ）をさらに更新する、請求項２０に記載の方法。
【請求項２３】
前記ステップｇ）において、複数のフレーム内の合計ブロック数に応じて前記長期平均値（ＳＡＤ  ａｖｅＬＴ）をさらに更新する、請求項２２に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に、ビデオ撮像システムにおける動き予測(motion estimation)に関する。詳しくは、連続するビデオフレームでの画像間の位置の変化を予測するのに必要なサーチ時間を短縮する方法に関する。
【０００２】
【従来の技術】
ビデオ情報フォーマットは、テレビ画面に映すのに、またはビデオテープに記録するのに適したビジュアル情報を与える。一般に、ビデオデータは階層構造で編成されている。ビデオシーケンスはフレーム群に分割され、各群は一連の単一フレームにより構成され得る。各フレームはほぼ静止画に等しく、静止画は、連続的な動きの表現をシミュレートするのに十分な頻度で更新される。フレームはさらに、スライス、すなわち水平方向のセクションに分割され、誤差回復のシステム設計の補助となる。各スライスは、誤差がスライスを超えて伝播しないように個別にコード化される。スライスはマクロブロックよりなる。Ｈ．２６ＰおよびＭＰＥＧ−Ｘ標準では、マクロブロックは、ビデオフォーマットにより異なるが、１６×１６個の輝度画素および対応する数の色差画素よりなる。マクロブロックは常に整数個のブロックを有し、８×８画素マトリックスが最小コード化ユニットである。
【０００３】
ビデオデータの伝送または格納を必要とするアプリケーションではビデオ圧縮は重要な要素である。圧縮技術は、前フレームに格納されている情報を再利用することによる動き（時間的な冗長）を補償する。圧縮はまた、空間ドメインのデータを周波数ドメインに変換することによっても行われる。動きの補償によって時間的な冗長を、および離散コサイン変換（ＤＣＴ）などの変換によって空間的な冗長を活用するハイブリッドデジタルビデオ圧縮は、Ｈ．２６ＰおよびＭＰＥＧ−Ｘ国際標準において基礎として採用されている。図１は、ビデオエンコードシステム（従来技術）のブロック図である。
【０００４】
このようなビデオ圧縮システムでは、伝送データの流れを減らすために、動き予測は重要である。動き予測は、２つのフレーム、すなわちエンコードされる現フレームおよび参照フレームとも呼ばれる既にコードされたフレームにわたって行われ、これら２つのフレーム間のビデオデータの一致を引き出す。実際には、動き予測を含むビデオ圧縮は、マクロブロックに関して行われ、ハードウェアおよびソフトウェアの具現化を促進する。動き予測は、１６×１６の輝度画素マトリックスを用いて各マクロブロックに対して行われる。次に、動き予測の結果が、マクロブロックのすべてのブロックに対して適用される。現フレーム内のマクロブロックに対しては、最後のフレームの最良一致領域が現在のマクロブロックのための予測(prediction)データとして使用され、一方、予測誤差、すなわちマクロブロックデータから予測値を差し引いた余りが時間的なデータ冗長から除去される。時間的な冗長とは、現フレームデータのうちの前フレームから予測され得る部分をいう。冗長の除去、すなわち予想値を差し引くことにより、データの繰り返し部分をエンコードする必要がなくなる。
【０００５】
時間的な冗長を除去した後、ビデオ圧縮はさらに、隣接する予測誤差画素間の相関を除去することによって実現される。これは、ビデオデータに内在する空間的な冗長を除去することである。これは、離散コサイン変換（ＤＣＴ）によって実現され、これにより、周波数ドメイン内でコンパクトな表示が得られ、引き続いて、変換された係数を量子化して顕著な係数のみが保存される。ＤＣＴおよび量子化は、各８×８ブロックに対して個別に行われる。
【０００６】
各マクロブロックに対する動き予測の目標は、前フレーム内に、現在のマクロブロックを最良に表す１６×１６データ領域を見つけることである。データ一致のための動き予測基準は様々なものがある。最終的には、最小のビットストリームを生成するようにビデオソースコード化をリンクする基準が最良の圧縮性能を実現する。実際において、動き予測は、量子化係数のソースコード化とは異なるプロセスである。すなわち、動き予測は、最後のビットストリームをチェックせずに行われ、これにより、コンピュータ計算が恐ろしく複雑になるのが回避される。さらに、各マクロブロック内の動き予測に対して、輝度データのみが使用され、これが輝度および色差の両方のコード化に適用される。輝度画素しか取り扱わないことにより手順が簡略化される。また、人間の視覚系は色の変化より輝度の変化に対してより高い感度を有する。動き予測基準は、周波数ドメインを含む様々なドメインで調査されたが、有効であり且つ幅広く適応している基準は、差の絶対値の和（ＳＡＤ）である。ＳＡＤは、動き予測をコード化効率性と関連付けるために正確な表示を与えることが分かっている。これは、コンピュータ計算上簡単であり、また、例えば、最小平均２乗誤差測定よりはるかに高速である。
【０００７】
（ｘ，ｙ）位置のマクロブロックにおいて、現在のマクロブロックと（ｖｘ，ｖｙ）によってオフセットされる前フレームの１６×１６ブロックとの間のＳＡＤは、以下で表される。
【０００８】
【数１】
0003793657.tif 000002
ここで、ｐ（ｘ＋ｉ，ｙ＋ｊ）は、現フレームの現在のマクロブロック内の画素値であり、ｑ（ｘ＋ｉ＋ｖｘ，ｙ＋ｊ＋ｖｙ）は、現在のマクロブロックから（ｖｘ，ｖｙ）だけオフセットした１６×１６ブロック内の、前フレームの画素値である。合計指数ｉおよびｊは、マクロブロック領域をカバーする。ＳＡＤ（ｖｘ，ｖｙ）が予め特定されたサーチ範囲内における最小値である場合は、（ｖｘ，ｖｙ）がそのマクロブロックのための動きベクトルである。
【０００９】
動き予測サーチ範囲（Ｍ，Ｎ）は（ｖｘ，ｖｙ）の最大値であり、現在のマクロブロックと比較されるマクロブロックサイズのマトリックスを含む、前フレーム内のデータのウィンドウを規定する。正確に言えば、サーチウィンドウは、動きを表すのに十分な大きさでなければならない。一方、動き予測の計算は非常に複雑であるため、実際の目的においては、サーチ範囲は制限されなければならない。図２は、現フレームの現在のマクロブロックと前フレームのサーチウィンドウとの間の空間的な関係を示す図（従来技術）である。動きベクトル範囲を（Ｍ，Ｎ）と規定すると、サーチウィンドウサイズは（１６＋２Ｍ，１６＋２Ｎ）である。ＴＶまたは映画のシーケンスでは、動きベクトル範囲は、様々なタイプの動き内容を収容するのに十分な大きさでなければならない。ビデオ会議およびビデオ電話機のアプリケーションでは、サーチ範囲はもっと小さくてもよい。従って、サーチ範囲の選択は、アプリケーションと配布可能な技術の利用可能性との組み合わせである。
【００１０】
動き予測サーチ範囲が得られると、計算要件は、動きベクトルを得るためにサーチウィンドウをカバーする正確な方法によって大きく左右される。徹底サーチ方法、すなわち全動き予測サーチは、最良の一致を見つけるためにサーチウィンドウ内のすべての候補ブロックをカバーする。この場合には、各マクロブロックに対する動きベクトルを得るために、コスト関数を（２Ｍ＋１）＊（２Ｎ＋１）回計算する必要がある。この計算コストはソフトウェア具現化にとってはあまりにも高すぎる。
【００１１】
計算コストを減らすために、入れ子式サーチおよびステップサーチなどの様々な異なる方法が用いられている。固定ステップサーチ法は、有効性と複雑性との間に良好な均衡を有し、動きの予測で広範囲に使用されている。図３は、固定ステップ動き予測法を示すフローチャート（従来技術）である。
【００１２】
固定ステップ動き予測法は、最良の一致を見つけるためにサーチウィンドウ内の固定数のステップを使用する。このとき次のステップに進む毎にサーチウィンドウは小さくなる。この方法は、前フレーム内のターゲットサーチウィンドウ有効領域内に均一に配分された９個のポイントにより開始される。９ポイントのそれぞれは、マクロブロックサイズの領域または輝度画素マトリックスの左上の隅を表す。現在のステップで最小ＳＡＤを有するマトリックスが、次のステップのための開始点（サーチ格子の新しい中心）として使用される。次のステップは、サーチポイントまたはマトリックス間の距離を半分にして、同じ方法で行われる。直前のステップのサーチポイント間の間隔をｗとすると、現在のステップでの間隔はｗ／２である。この手順は最後のステップまで続けられ、最後のステップでは、９個のサーチポイントすべてが隣接し、整数個の画素のためのズームインはもはや不可能である。図４は、図３のステップサーチ法での最後の３つのステップを示す例（従来技術）である。この例は、水平方向および垂直方向の（−７，＋７）の動きベクトル範囲をカバーする。動きベクトル範囲が（−１５，＋１５）の場合は、４つのステップが必要である。
【００１３】
（−１５，＋１５）の動きベクトル範囲では、コスト関数計算の回数は（９＋８＋８＋８）＝３３である。すなわち、最初のステップでは９回のＳＡＤ計算が行われる。ＳＡＤが最も低いマトリックスが第２のサーチステップに（中心として）含まれるため、第２のサーチステップでは８回のＳＡＤ計算が必要なだけである。同様に、ステップ３および４でも、８回のＳＡＤ計算が必要なだけである。１６×１６の画素サーチウィンドウ内のすべてのマトリックスのＳＡＤをチェックするのに必要な計算回数に比べて、固定ステップ法で必要な計算回数は少ない。フルサーチで（２＊１５＋１）＊（２＊１５＋１）＝９６１回のコスト関数計算が必要である。フルサーチと比べると、計算は３．４％へと飛躍的に減少する。
【００１４】
【発明が解決しようとする課題】
しかし、固定ステップ法は、前フレームの初期開始マトリックスの正確度、または近隣のマクロブロックのためになされる動き予測の正確度には反応しない。例えば、前フレームと現フレームとの間でマクロブロック内に動きがない場合は、サーチでの開始マトリックスは最も低いＳＡＤを持つことが多い。この場合は、上述のように、３３回の計算すべてを行うのは無駄である。一方、フレーム間の大きな動きがある場合は、上述のような固定ステップ予測法では、３３回の計算を行ったとしても、最良のＳＡＤを有するマトリックスを見つけることはできないかもしれない。例えば、最良のＳＡＤを有するマトリックスは、３２×３２マトリックスによって規定される初期サーチから外れているかもしれない。この場合には、本来のサーチ領域が４８×４８マトリックスによって規定される方がましであり得る。初期固定ステップサーチウィンドウを４８×４８マトリックスを収容するように永久に設定することは可能であるが、この場合、すべての予測が５ステップ、すなわち４１回の計算（９＋８＋８＋８＋８）を必要とし、これは平均的な変化の少ない動きの場面では無駄である。
【００１５】
２つの連続するビデオフレームで表される画像に僅かな動きしかないとき、固定ステップ動き予測法と共に使用するために、サーチウィンドウサイズを縮小して必要な計算回数を減らす方法が利用可能であることが望ましい。
【００１６】
２つの連続するフレームで表される画像に飛躍的な動きがあるとき、固定ステップ動き予測と共に使用するために、ウィンドウサイズを大きくする方法が利用可能であることが望ましい。
【００１７】
隣接するマクロブロック内の動き予測から計算される、位置の平均的な変化に応じてサーチウィンドウサイズを調節する、固定ステップ動き予測法と共に使用される方法が望ましい。
【００１８】
【課題を解決するための手段】
本発明による一連のフレームによってビデオシーケンスを表すデジタルビデオシステム圧縮フォーマットは、該一連のフレームは前フレームおよび該前フレームに続く現フレームを含み、該一連のフレームは全て所定の時間間隔で分離されており、該フレームは所定の位置を持つ複数のブロックに分割され、各ブロックは所定の輝度ピクセ輝度トリクスを含むサイズを有する、デジタルビデオシステム圧縮フォーマットにおいて、該現フレームにおける一連のブロック内の輝度画素データマトリクスによって表される画像の、該前フレームにおける対応するブロックサイズの該輝度画素データマトリクスからの位置変化を効果的に予測する方法であって、ａ）該現フレーム内で第１のブロックを選択するステップと、ｂ）該現フレーム内の該第１のブロックに対応する初期候補マトリクスとして、該前フレーム内のブロックサイズの該輝度ピクセ輝度トリクスを選択するステップと、ｃ）前ブロック位置変化予測値から導出されるフレーム間の輝度画素データの短期平均比較値を与えるステップと、ｄ）該ステップｃ）で与えられた輝度画素データの短期平均比較値に応じて、該候補マトリクスを中心とするサーチウィンドウサイズを計算するステップと、ｅ）該サーチウィンドウ内で均一に分布した複数のブロックサイズの輝度ピクセ輝度トリクスからの該輝度画素データを、該現フレーム内の第１のブロックの該輝度画素データと比較して、該現フレーム内の該第１のブロックの該輝度画素データに最も類似する輝度画素データを有する新たな候補マトリクスを選択するステップであって、これにより該サーチウィンドウサイズがフレーム間の動きの履歴と共に変化するステップと、を包含し、そのことにより上記目的が達成される。
【００１９】
前記サーチウィンドウ内のブロックサイズのマトリクス間の最小間隔が与えられ、前記ステップｅ）の後に、ｆ）該ステップｅ）を実行する度に該サーチウィンドウ内に位置する複数のブロックサイズのマトリクス間の間隔を低減するステップと、ｇ）１）該複数のブロックサイズのマトリクス間の該間隔が該最小間隔以上である場合には該ステップｅ）に戻り、２）該複数のブロックサイズのマトリクス間の該間隔が該最小間隔未満である場合には次に進むようにして、該サーチを反復するステップと、ｈ）該ステップｅ）を最後に実行したときに選択された最終候補マトリクスの輝度画素データを、前記現フレーム内の前記第１のブロックの輝度画素データと比較して、輝度画素データの最終比較値を計算し、これにより該最終候補マトリクスと該第１のブロックとの間のブロック位置の差によってフレーム間の動きを記述するベクトルを与えるステップとをさらに包含してもよい。
【００２０】
前記ステップｈ）の後に、ｉ）該ステップｈ）で計算された前記輝度画素データの最終比較値で、前記輝度画素データの短期平均比較値を更新するステップであって、これにより、次回の位置変化予測の前記ステップｃ）のために該短期平均値が更新されるステップをさらに包含してもよい。
【００２１】
前記ステップｉ）の後に、ｊ）該ステップｉ）において更新された前記輝度画素データの短期平均比較値で、サーチウィンドウサイズの長期平均値を更新するステップと、ｃ1）前記ステップｃ）の後で、前記ステップｄ）の前に、該サーチウィンドウサイズの長期平均値を与えるステップと、をさらに包含し、該ステップｄ）は、該サーチウィンドウサイズの長期平均値に応じて該サーチウィンドウサイズを計算するステップを含み、これにより、次回のブロック位置変化予測の前記ステップｃ1）の準備のために該長期平均値が該ステップｊ）において更新されてもよい。
【００２２】
前記ステップｊ）の後に、ｋ）前記ステップｈ）で計算された前記輝度画素データの最終比較値で、輝度画素データの長期平均比較値を更新し、これにより前記第１のブロックの前記位置変化予測値で該長期平均値を更新するステップをさらに包含し、該ステップｊ）は、該輝度画素データの長期平均値に応じて該長期平均サーチウィンドウサイズを更新するステップを含んでもよい。
【００２３】
前記ステップｅ）は、前記サーチウィンドウ内の前記複数のブロックサイズのマトリクスのそれぞれと前記現フレーム内の前記第１のブロックとの間における輝度画素データの差の絶対値の和（ＳＡＤ）の計算を行うことによって輝度画素データを比較するステップを含み、最小のＳＡＤを持つブロックサイズのマトリクスが、前記ステップｅ）〜ｆ）の次回の実行時の候補マトリクスとして選択され、前記ステップｈ）は、前記輝度画素データの最終比較値として該最小ＳＡＤ（ＳＡＤ＿ｍｉｎ）を用いて該ブロックサイズのマトリクスの計算を行うステップを含んでもよい。
【００２４】
前記ステップｂ）の後で、前記ステップｃ）の前に、ｂ1）該ステップｂ）で選択された前記初期候補マトリクスと、前記現フレーム内の前記第１のブロックとの間のＳＡＤを計算することによりＳＡＤ＿ｉｎｉｔを導出するステップをさらに包含し、前記ステップｄ）は、該ステップｂ1）で計算されたＳＡＤ＿ｉｎｉｔに応じて前記サーチウィンドウサイズを計算するステップを含んでもよい。
【００２５】
前記ステップｋ）は、輝度画素データの長期平均比較値として長期平均値（ＳＡＤ＿ａｖｅＬＴ）を含み、該ステップｋ）は、前記ステップｈ）で計算されたＳＡＤ＿ｍｉｎでＳＡＤ＿ａｖｅＬＴを更新するステップを含み、これにより、前記第１のブロックの位置変化が予測された後にＳＡＤ値でＳＡＤ＿ａｖｅＬＴが更新されてもよい。
【００２６】
前記ステップｄ）は、前記ブロックサイズのマトリクス間の間隔が前記最小間隔になるまでに必要な前記ステップｅ）〜ｆ）の反復回数（ＭＥ＿ｓｔｅｐ）で前記サーチウィンドウサイズを規定するステップを含み、該ステップｅ）は、該ＭＥ＿ｓｔｅｐの値に応じて、該サーチウィンドウ内で比較される該複数のブロックサイズマトリクスを初期的に分布させるステップを含んでもよい。
【００２７】
前記ステップｉ）は、前記輝度画素データの短期平均比較値としてＳＡＤの短期平均値（ＳＡＤ＿ａｖｅ）を含み、該ステップｉ）は、前記ステップｈ）で計算されたＳＡＤ＿ｍｉｎでＳＡＤ＿ａｖｅを更新するステップを含み、これにより、前記第１のブロックの位置変化が予測された後にＳＡＤ値でＳＡＤ＿ａｖｅが更新されてもよい。
【００２８】
前記ステップｉ）は、１フレーム内のブロック数に応じてＳＡＤ＿ａｖｅを計算するステップを含み、前記ステップｋ）は、複数のフレーム内の合計ブロック数に応じてＳＡＤ＿ａｖｅＬＴを計算するステップを含んでもよい。
【００２９】
前記ステップｂ）は、隣接ブロックについて前に予測した位置変化に応じて前記初期候補マトリクスを選択するステップを含み、これにより、該第１のブロックの該予測処理を開始するために中間予測が用いられてもよい。
【００３０】
前記ステップｂ）は、前記前フレーム内の前記第１のブロックについて前に予測した位置変化に応じて前記初期候補マトリクスを選択するステップを含み、これにより、該第１のブロックの該予測処理を開始するために中間予測が用いられてもよい。
【００３１】
前記ステップｅ）は、整数個の画素間隔によって均一に分割された、前記サーチウィンドウ内の少なくとも８個のブロックサイズマトリクスからの輝度画素データを比較するステップを含んでいてもよい。
【００３２】
前記輝度画素ブロックはそれぞれ１６×１６個の輝度画素を含むマクロブロックであり、前記ステップｄ）は、最大５のＭＥ＿ｓｔｅｐを使用し、前記ステップｇ）は、最大５回の前記ステップｅ）〜ｆ）の反復を含んでもよい。
【００３３】
前記ステップｉ）の後に、ｌ）前記ステップｈ）で計算されたＳＡＤ＿ｍｉｎと、該ステップｉ）において更新されたＳＡＤ＿ａｖｅと、１フレーム内のマクロブロック数とに応じて、ＳＡＤの分散（ＳＡＤ＿ｖａｒ）を計算するステップと、ｃ2）前記ステップｃ）の後で、前記ステップｄ）の前に、ＳＡＤ＿ｖａｒを与えるステップとをさらに包含し、該ステップｄ）は、該ＳＡＤ＿ｖａｒに応じてＭＥ＿ｓｔｅｐを計算するステップを含み、これにより、次回のブロック位置変化予測の前記ステップｃ2）の準備のためにＳＡＤ＿ｖａｒが該ステップｌ）において更新されてもよい。
【００３４】
前記ステップｉ）が以下に示すＳＡＤ＿ａｖｅの計算を含み、（ＳＡＤ＿ａｖｅ）＝（（ｎｕｍＭＢ−１）（ＳＡＤ＿ａｖｅ）0＋ＳＡＤ＿ｍｉｎ）／ｎｕｍＭＢ、（ＳＡＤ＿ａｖｅ）0は前回のマクロブロック位置変化予測からのＳＡＤ＿ａｖｅであり、ｎｕｍＭＢは１フレーム内のマクロブロック数であってもよい。
【００３５】
前記ステップｋ）が以下に示すＳＡＤ＿ａｖｅＬＴの計算を含み、（ＳＡＤ＿ａｖｅＬＴ）＝（（ｎｕｍＭＢｓＬＴ−１）（ＳＡＤ＿ａｖｅＬＴ）0＋ＳＡＤ＿ｍｉｎ）／ｎｕｍＭＢｓＬＴ、（ＳＡＤ＿ａｖｅＬＴ）0は前回のマクロブロック位置変化予測で計算されたＳＡＤ＿ａｖｅＬＴであり、ｎｕｍＭＢｓＬＴは複数のフレーム内の合計ブロック数であってもよい。
【００３６】
前記ステップｄ）が以下に示すＭＥ＿ｓｔｅｐの計算を含んでいてもよい。ａ）もし、ＳＡＤ＿ｉｎｉｔ＜ＳＡＤ＿ａｖｅ−ＳＡＤ＿ｖａｒである場合には、ＭＥ＿ｓｔｅｐ＝ＭＥ＿ｓｔｅｐＡＶＥ−２とし、ｂ）そうでない場合にもし、ＳＡＤ＿ｉｎｉｔ＜ＳＡＤ＿ａｖｅである場合には、ＭＥ＿ｓｔｅｐ＝ＭＥ＿ｓｔｅｐＡＶＥ−１とし、ｃ）そうでない場合にもし、ＳＡＤ＿ｉｎｉｔ＜ＳＡＤ＿ａｖｅ＋ＳＡＤ＿ｖａｒである場合には、ＭＥ＿ｓｔｅｐ＝ＭＥ＿ｓｔｅｐＡＶＥとし、ｄ）そうでない場合にもし、ＳＡＤ＿ｉｎｉｔ＜ＳＡＤ＿ａｖｅ＋２（ＳＡＤ＿ｖａｒ）である場合には、ＭＥ＿ｓｔｅｐ＝ＭＥ＿ｓｔｅｐＡＶＥ＋１とし、ｅ）そうでない場合には、ＭＥ＿ｓｔｅｐ＝ＭＥ＿ｓｔｅｐＡＶＥ＋２とする。
【００３７】
ＭＥ＿ｓｔｅｐＡＶＥは４の値で初期化され、前記ステップｊ）が以下に示すＭＥ＿ｓｔｅｐＡＶＥの計算の更新を含んでもよい。
ａ）もし、ＳＡＤ＿ａｖｅ＞ａ0（ＳＡＤ＿ａｖｅＬＴ）／ａ1である場合には、ＭＥ＿ｓｔｅｐＡＶＥ＝ＭＥ＿ｓｔｅｐＡＶＥ＋１とし、ｂ）そうでない場合にもし、ＳＡＤ＿ａｖｅ＜ａ2（ＳＡＤ＿ａｖｅＬＴ）／ａ1である場合には、ＭＥ＿ｓｔｅｐＡＶＥ＝ＭＥ＿ｓｔｅｐＡＶＥ−１とする（但し、ａ0＞ａ1＞ａ2＞０である）。
【００３８】
ステップｊ）において、ａ0の値が１０であり、ａ1の値が８であり、ａ2の値が７であってもよい。
【００３９】
前記ステップｅ）は、前記ステップｄ）で計算された前記ＭＥ＿ｓｔｅｐの値を用いて、前記サーチウィンドウ内の隣接するマクロブロックサイズのマトリクスの中心を初期的に分離する画素数であるｓを計算するステップを含み、ｓは、ｓ＝２(ME#step-1)として計算され、前記ステップｆ）は、該ｓの値を２で割ることにより、該ステップｅ）〜ｆ）を実行する度に該サーチウィンドウ内のマクロブロック間の間隔を低減するステップを含んでもよい。
【００４０】
前記ステップｌ）は以下のようにＳＡＤ＿ｖａｒを計算するステップを含み、ＳＡＤ＿ｖａｒ＝√［（（ｎｕｍＭＢ−１）＊（（ＳＡＤ＿ｖａｒ）0）2＋（ＳＡＤ＿ｍｉｎ−ＳＡＤ＿ａｖｅ）2）／ｎｕｍＭＢ］、（ＳＡＤ＿ｖａｒ）0は、前回のマクロブロック位置変化予測からのＳＡＤ＿ｖａｒであってもよい。
【００４１】
本発明の別の実施形態では、一連のフレームによってビデオシーケンスを表すデジタルビデオシステム圧縮フォーマットであって、該一連のフレームは前フレームおよび該前フレームに続く現フレームを含み、該一連のフレームは全て所定の時間間隔で分離されており、該フレームは所定の位置を持つ複数のブロックに分割され、各ブロックは所定の輝度ピクセ輝度トリクスを含むサイズを有する、デジタルビデオシステム圧縮フォーマットにおいて、該現フレームにおける一連のブロック内の輝度画素データマトリクスによって表される画像の、該前フレームにおける対応するブロックサイズの輝度画素データマトリクスからの位置変化を効果的に予測する方法であって、ａ）該現フレーム内で第１のブロックを選択するステップと、ｂ）該現フレーム内の該第１のブロックに対応する初期候補マトリクスとして、該前フレーム内のブロックサイズの輝度ピクセ輝度トリクスを選択するステップと、ｃ）前ブロック位置変化予測値から求められるフレーム間の輝度画素データの短期平均比較値を与えるステップと、ｄ）サーチパターンを規定するために該ステップｃ）で与えられた該短期平均値を用いて、該候補マトリクスの周囲の輝度画素エリア内をサーチして該第１のブロックの輝度画素データと比較して最も近いブロックサイズの最終候補マトリクスを見つけるステップであって、これにより、位置変化の履歴によって該サーチパターンが規定されるステップとを包含し、そのことにより上記目的が達成される。  前記ステップｄ）の後に、ｅ）前記第１のブロックの前記輝度画素データの比較値および該ステップｄ）で計算された前記最終候補マトリクスで、前記輝度画素データの短期平均比較値を更新するステップであって、これにより、次回のブロック位置変化予測の前記ステップｃ）の準備のために該短期平均値が変更されるステップさらに包含してもよい。
【００４２】
前記ステップｄ）の後に、ｆ）前記第１のブロックの輝度画素データの比較値および該ステップｄ）で計算された前記最終候補マトリクスで、輝度画素データの長期平均比較値を更新するステップをさらに包含してもよい。
【００４３】
ｇ）前記ステップｆ）の後に、前記ステップｅ）で更新された前記輝度画素データの短期平均比較値と、該ステップｆ）で更新された前記輝度画素データの長期平均比較値とに応じて、サーチパターンサイズの長期平均値を更新するステップと、ｃ1）前記ステップｃ）の後で、前記ステップｄ）の前に、サーチパターンサイズの長期平均値を与えるステップと、をさらに包含し、該ステップｄ）は、該サーチパターンサイズの該長期平均値に応じて該サーチパターンを規定するステップを含んでもよい。
【００４４】
前記ステップｄ）は、前記サーチウィンドウ内の前記複数のブロックサイズのマトリクスのそれぞれと前記現フレーム内の前記第１のブロックとの間における輝度画素データの差の絶対値の和（ＳＡＤ）の計算を行うことによって輝度画素データを比較するステップを含み、最小ＳＡＤ（ＳＡＤ＿ｍｉｎ）を持つブロックサイズのマトリクスの計算は、該第１のブロックと前記最終候補マトリクスとの間での輝度画素データの比較であってもよい。
【００４５】
前記ステップｃ）は、輝度画素データの短期平均比較値としてＳＡＤの短期平均値（ＳＡＤ＿ａｖｅ）を含み、該ステップｅ）は、前記ステップｄ）で計算されたＳＡＤ＿ｍｉｎでＳＡＤ＿ａｖｅを更新するステップを含み、これにより、次回のブロック位置変化予測の該ステップｃ）の準備のために、該ＳＡＤ＿ａｖｅが該ステップｅ）におけるＳＡＤ値で更新されてもよい。
【００４６】
前記ステップｆ）は、輝度画素データの長期平均比較値として長期平均値（ＳＡＤ＿ａｖｅＬＴ）を含み、該ステップｆ）は、前記ステップｄ）で計算されたＳＡＤ＿ｍｉｎでＳＡＤ＿ａｖｅＬＴを更新するステップを含み、これにより、前記ステップｇ）のために、ＳＡＤ＿ａｖｅＬＴが該ステップｆ）におけるＳＡＤ値で更新されてもよい。
【００４７】
前記ステップｅ）は、１フレーム内のブロック数に応じてＳＡＤ＿ａｖｅを更新するステップを含み、前記ステップｆ）は、複数のフレーム内の合計ブロック数に応じてＳＡＤ＿ａｖｅＬＴを更新するステップを含んでもよい。
【００４８】
前記ステップｂ）は、隣接ブロックについて前に予測した位置変化に応じて前記初期候補マトリクスを選択するステップを含み、これにより、前記第１のブロックの前記予測処理を開始するために中間予測が用いられてもよい。
【００４９】
前記ステップｂ）は、前記前フレーム内の前記第１のブロックについて前に予測した位置変化に応じて前記初期候補マトリクスを選択するステップを含み、これにより、該第１のブロックの該予測処理を開始するために中間予測が用いられてもよい。
【００５０】
前記ステップｅ）の後に、ｈ）前記ステップｄ）で計算されたＳＡＤ＿ｍｉｎと、該ステップｅ）において更新されたＳＡＤ＿ａｖｅと、１フレーム内のマクロブロック数とに応じて、ＳＡＤの分散（ＳＡＤ＿ｖａｒ）を計算するステップと、ｃ2）前記ステップｃ）の後で、前記ステップｄ）の前に、ＳＡＤ＿ｖａｒを与えるステップとをさらに包含し、該ステップｄ）は、該ＳＡＤ＿ｖａｒに応じて前記サーチパターンを規定するステップを含んでもよい。
【００５１】
本発明のさらに別の実施形態によると、一連のフレームによってビデオシーケンスを表すデジタルビデオシステム圧縮フォーマットであって、該一連のフレームは前フレームおよび該前フレームに続く現フレームを含み、該一連のフレームは全て所定の時間間隔で分離されており、該フレームは所定の位置を持つ複数のマクロブロックに分割され、各マクロブロックは、１６×１６の輝度ピクセ輝度トリクスを含むサイズを有するデジタルビデオシステム圧縮フォーマットにおいて、該現フレームにおける一連のマクロブロック内の輝度画素データマトリクスによって表される画像の、該前フレームにおける対応するマクロブロックサイズの輝度画素データマトリクスからの位置変化を効果的に予測する方法であって、ａ）該現フレーム内で該一連のマクロブロックの中から次のマクロブロックを選択するステップと、ｂ）隣接ブロックについて前に予測した位置変化に応じて、該ステップａ）で選択されたマクロブロックに対応する初期候補マトリクスとして該前フレーム内のマクロブロックサイズの輝度ピクセ輝度トリクスを選択し、これにより第１のブロックの予測処理を開始するために中間予測が用いられるステップと、ｃ）該ステップａ）で選択されたマクロブロックと、該ステップｂ）で選択された初期候補マトリクスとの間のＳＡＤ（ＳＡＤ＿ｉｎｉｔ）を計算するステップと、ｄ）前ブロック位置変化予測値から導出されるフレーム間の輝度画素データの短期平均比較値ＳＡＤ（ＳＡＤ＿ａｖｅ）を与えるステップと、ｅ）複数のマクロブロック位置変化予測値によって求められるＭＥ＿ｓｔｅｐの長期平均（ＭＥ＿ｓｔｅｐＡＶＥ）を与えるステップと、ｆ）以前の位置変化予測値から導出されるＳＡＤの分散（ＳＡＤ＿ｖａｒ）を与えるステップと、ｇ）ブロックサイズのマトリクス間の間隔が最小間隔になるまでに必要なサーチの反復回数（ＭＥ＿ｓｔｅｐ）を計算するステップであって、該ＭＥ＿ｓｔｅｐの計算は、ＳＡＤ＿ｉｎｉｔ、ＳＡＤ＿ａｖｅ、ＭＥ＿ｓｔｅｐＡＶＥおよびＳＡＤ＿ｖａｒの値に応じて行われるステップと、ｈ）該ステップｇ）で計算された該ＭＥ＿ｓｔｅｐの値に応じて、可能性のある候補マトリクス間の初期間隔（ｓ）を計算するステップと、ｉ）該ステップａ）で選択されたマクロブロックと、隣接するマトリクスの中心間の間隔がｓである少なくとも８つの均一に分布したマクロブロックサイズのマトリクスとの間のＳＡＤを計算し、これにより、最小ＳＡＤ（ＳＡＤ＿ｍｉｎ）を持つ新たな候補マトリクスの位置を特定するステップと、ｊ）１）ｓが該最小間隔以上である場合には、ｓを２で割ってｓの値を新たな値にして該ステップｉ）へと進み、２）ｓが該最小間隔未満である場合には、次に進むようにして、該サーチ処理を反復するステップと、ｋ）該ステップｉ）の最後の実行時に最終候補マトリクスを選択して、該ステップａ）で選択された該ブロックと比較し、これにより、ＳＡＤ＿ｍｉｎを計算するステップと、ｌ）次のマクロブロックの位置変化予測において該ステップｇ）でＭＥ＿ｓｔｅｐを計算する際に使用するために、該ＳＡＤ＿ｍｉｎでＳＡＤ＿ａｖｅ、ＭＥ＿ｓｔｅｐＡＶＥおよびＳＡＤ＿ｖａｒを更新するステップと、ｍ）該ステップａ）���進み、該一連のマクロブロックの中の該ステップａ）で選択されたマクロブロックの次のマクロブロックについて該位置変化予測処理を繰り返すステップであって、これにより１回の位置変化予測に必要なサーチ反復回数は、それまでに予測を行ったマクロブロックにおけるＳＡＤの履歴に応じて変化するステップとを包含し、そのことにより上記目的が達成される。
【００５２】
現フレームの一連のブロック内の輝度画素データマトリックスによって表される画像の位置の変化を、前フレームの対応するブロックサイズ輝度画素データマトリックスから効率的に予測する方法が提供される。この方法は、ビデオシーケンスを、すべてが所定の時間間隔で分離された、現フレームの直前の前フレームを含む一連のフレームで表すデジタルビデオシステム圧縮フォーマットに適用される。フレームは所定の位置を有する複数のブロックに分割され、各ブロックは、所定の輝度画素マトリックスを含む大きさを有する。この方法は、
ａ）現フレームの最初のブロックを選択するステップと、
ｂ）前フレームのブロックサイズ輝度画素マトリックスを、現フレームの最初のブロックに対応する初期候補マトリックスとして選択するステップと、
ｃ）前のブロック位置変化予測から引き出される、フレーム間の輝度画素データの短期平均比較を与えるステップと、
ｄ）ステップｃ）で提供された輝度画素データの短期平均比較に応じて、候補マトリックスを中心とするサーチウィンドウサイズを計算するステップと、
ｅ）サーチウィンドウ内に均一に配分される複数のブロックサイズ輝度画素マトリックスからの輝度画素データを、現フレームの最初のブロックの輝度画素データと比較して、現フレームの最初のブロックの輝度画素データに最も類似する輝度画素データを有する新しい候補マトリックスを選択し、これによりサーチウィンドウサイズがフレーム間の動きの履歴により変動する、ステップと、を包含する。
【００５３】
ステップｅ）に続いて、
ｆ）ステップｅ）の各繰り返しの後、サーチウィンドウ内に位置する複数のブロックサイズマトリックス間の間隔を縮小するステップと、
ｇ）複数のブロックサイズマトリックス間の間隔が、ユーザ規定の最小間隔サイズに一致するまでステップｅ）〜ｆ）を繰り返し、ステップｅ）の最後の繰り返しでの最後の候補マトリックスを選択するステップと、
ｈ）ステップｅ）の最後の繰り返しで選択された最後の候補マトリックスの輝度画素データを、現フレームの最初のブロックの輝度画素データと比較して、輝度画素データの最後の比較の計算を行い、これにより最後の候補マトリックスと最初のブロックとの間のブロック位置の差がフレーム間の動きを示すベクトルを与える、ステップと、よりなるステップがさらに包含される。
【００５４】
最後の候補マトリックスが見つかった後、短期平均比較は、ステップｈ）で計算された輝度画素データの最後の比較により更新される。サーチウィンドウサイズはまた、サーチウィンドウサイズの長期平均を用いて計算される。長期サーチウィンドウサイズは、輝度画素データの新しい短期平均比較の計算に応じて更新される。長期平均サーチウィンドウサイズはまた、輝度画素データの長期平均比較により計算される。これはステップｈ）の後で更新される。
【００５５】
典型的には、輝度画素データは、輝度画素データの差の絶対値の和（ＳＡＤ）の計算を介して比較される。ステップｅ）では、ＳＡＤが最も小さいブロックサイズマトリックスが、ステップｅ）〜ｆ）の次の繰り返しにおける候補マトリックスとして選択され、ステップｈ）は、輝度画素データの最後の比較として最小ＳＡＤ（ＳＡＤ＿ｍｉｎ）の計算を含む。さらに、輝度画素データの短期（ＳＡＤ−ａｖｅ）および長期平均（ＳＡＤ＿ａｖｅＬＴ）比較の両方を生成するために、ＳＡＤ情報が使用される。ＳＡＤ＿ａｖｅを計算するためにはフレーム内の全マクロブロック数もまた使用され、ＳＡＤ＿ａｖｅＬＴを計算するためには、いくつかのフレームからのマクロブロックの合計数が使用される。
【００５６】
方法は、ブロックサイズマトリックス間の間隔が最小間隔になるまでに必要とされるステップｅ）〜ｆ）の繰り返し回数（ＭＥ＿ｓｔｅｐ）に関連してサーチウィンドウサイズを規定することを包含する。この場合は、ステップｅ）は、ＭＥ＿ｓｔｅｐの値に応じてサーチウィンドウ内に比較される複数のブロックサイズマトリックスを先ず配分することを包含し、ステップｆ）は、繰り返し毎にサーチウィンドウサイズを半分にすることを包含する。
【００５７】
新規な動き予測アルゴリズムであるＡＭＥＳＳＡＤ（adaptive motion estimation based on statistical sum of absolute difference「差の絶対値の統計和に基づく適応型動き予測」）が提供される。本アルゴリズムは、ＳＡＤ（sum of absolute difference「差の絶対値の和」）の統計的分布に基づいて動きサーチステップサイズを適応的に求める。つまり、あるフレーム中のある部分における動きを予測するためのサーチステップサイズは、同じフレームの隣接部分から得たＳＡＤ値を用いて計算される。本発明による効率的なサーチ手順によって、Ｈ．２６ＰおよびＭＰＥＧ−Ｘ規格のビデオ圧縮のような、動き補償および変換を利用したハイブリッドビデオコーダー(coder)の実施を向上する。固定ステップサイズの動き予測と比較して、本発明による適応型アルゴリズムは、動き予測、ひいては全体的なビデオエンコード速度を向上する。さらに、本発明のアルゴリズムでは、動きの度合いによって各領域を差別化し、動きの内容がより豊富なローカルエリアまたはローカルフレームに対してより多くの動き予測リソースを割り当てるので、多くの場合、向上した画質が得られる。
【００５８】
【発明の実施の形態】
ハイブリッドビデオコーデック（codec）は、動き補償を用いて、連続するフレームにおけるビデオデータ時間冗長度を解消または低減する。物理的世界を表す場合、ビデオシーケンスにおける動きフローはほぼ円滑である。即ち、ビデオデータの一次微分は、時間方向に非常に相関する。このことは、任意の動きアクティビティが多数のフレームにわたる高フレームレートビデオシーケンスにおいて特に当てはまる。
【００５９】
以下に説明する、差の絶対値の統計和に基づく適応型動き予測（ＡＭＥＳＳＡＤ）のアルゴリズムは、動きベクトルの連続性を利用して、各マクロブロックに動き予測特性を動的に且つ効率的に割り当てることによって、固定ステップ動き予測を向上する。このアルゴリズムはまた、速い動きを有する物体の動き速度はより速く変化し、遅い動きを有する物体の動き速度はより遅く変化するという前提に基づいている。即ち、動きを有する領域は、ビデオデータにおいて高２次微分を有する可能性が高い。局部的（フレーム内）には、豊富な動き内容を有するマクロブロックには、より長い動き予測ステップが割り当てられる。静的バックグラウンドタイプのマクロブロックには、より短い動き予測ステップが割り当てられる。（数フレームにわたる）長期処理では、激しい動きを有するフレームのセグメントは、より長い平均動き予測ステップを有する。一方、軽い動きを有するフレームのセグメントは、本発明のアルゴリズムによる統計的分析に基づく、短い平均動き予測ステップを有する。
【００６０】
ＡＭＥＳＳＡＤの使用により、固定ステップ動き予測と比べて、向上した動き予測速度が得られる。多くの場合、アルゴリズムの適用により、ビデオのより高い視覚的品質も得られる。
【００６１】
図５は、現フレームの一連のブロックにおいて輝度画素データのマトリクスによって表される画像位置の変化を、前フレームの輝度画素データの対応するブロックサイズのマトリクスから効率的に予測する方法を説明するためのフローチャートである。ステップ１０で、ビデオシーケンスが一連のフレームで表される圧縮フォーマットを有するデジタルビデオシステムを与える。具体的には、一連のフレームは、現フレームの前フレームを含む。すべてのフレームは、所定の時間間隔で分離される。フレームは、所定の位置で複数のブロックに分割され、各ブロックは、輝度画素の所定のマトリクスを含むような大きさを有する。例えば、ブロック１は、固定位置を有し、各々の連続するフレームにおいて同じ画素マトリクスを含む。典型的には、輝度画素のブロックはマクロブロックであり、各マクロブロックは、輝度画素の１６×１６マトリクスを含む。しかし、本発明は、任意の大きさの画素ブロックに適用可能である。以下に説明する種々の統計的パラメータは、アプリケーションプログラムの始めにゼロに初期化され、その後、各マクロブロックについて動き補償が計算されると、更新される。
【００６２】
ステップ１２で、現フレームの第１のブロックを選択するか、または、現フレームにおける一連のマクロブロックのその次のマクロブロックを選択する。典型的には、各ブロックはアドレスで識別され、隣接するブロックは連続するアドレスを有する。本発明の方法は、予測されるマクロブロックの連続的な順序がフレームの左上から右下に移動する場合によりよく作用するが、本発明の方法はまた、各ブロックを順序付けおよび選択して予測するその他の手段にも適用可能である。
【００６３】
ステップ１４で、前フレームの輝度画素のブロックのサイズのマトリックスを、現フレームの最初のブロックに対応する初期候補マトリクスとして選択する。好適な実施形態では、ステップ１４は、隣接するブロックについて以前に予測された位置変化に応じて初期候補マトリクスを選択するステップを包含する。このように、フレーム内予測（intra prediction）を用いて、最初のブロックについて予測プロセスを開始する。典型的には、最初のブロックの直ぐ左および上ブロックが用いられる。
【００６４】
本発明の幾つかの局面では、ステップ１４は、前フレームの最初のブロックについて以前に予測された位置変化に応じて初期候補マトリクスを選択するステップを包含し、これにより、フレーム間予測（inter prediction）を用いて、最初のブロックについての予測プロセスを開始する。
【００６５】
ステップ１６で、以前のブロック位置変化予測値から得られる、フレーム間の輝度画素データの短期平均比較値を与える。ステップ１６は、本発明の核心である。フレーム間で劇的な動きがある場合には探索ウィンドウを拡大し、フレーム間で動きがほとんどない場合には探索ウィンドウを縮小するという柔軟性を本発明に与えるのは、以下に説明する、探索ウィンドウサイズを決定するプロセスにステップ１６を包含することによるものである。以下により詳細に説明するように、ステップ１６の短期平均値は、隣接するマクロブロックの輝度画素比較値に非常に依存し、特に、ステップ１２で最初のブロックの選択の直前に行われたマクロブロック位置変化予測値に非常に依存する計算値である。
【００６６】
ステップ１６で与えられた短期間平均を用いて探索パターンを規定するステップ１８は、候補マトリクスの周囲にある輝度画素の領域を探索して、最初のブロックの輝度画素データに最も匹敵する最終候補ブロックサイズマトリクスを見つけるステップを包含し、これにより、位置変化の履歴によって、探索パターンが規定される。
【００６７】
ステップ１８の後のステップ２０は、平均化統計値を更新するステップを包含する。具体的には、ステップ２０は、輝度画素データの短期間平均比較値を、ステップ１８で計算された最初のブロックおよび最終候補マトリクスの輝度画素データの比較値で更新する第１のサブステップ（図示せず）を包含し、これにより、短期平均値は、ステップ１６でその次の位置変化予測値を与えるために、変更される。ステップ１８の後の第２のサブステップ（図示せず）は、最初のブロックおよび最終候補マトリクスの輝度画素データの比較値で、輝度画素データの長期平均比較値を変更または更新するステップを包含する。
【００６８】
第２のサブステップの後の、ステップ２０の第３のステップ（図示せず）で、第１のサブステップで更新された輝度画素データの短期平均比較値と、第２のサブステップで更新された輝度画素データの長期平均比較値とに応じて、探索パターンサイズの長期平均値を更新する。好適な実施形態では、ステップ１６とステップ１８の間のさらなるステップ１６ａ（図示せず）で、以前のブロック位置変化予測値において計算された探索パターンサイズの長期平均値を与え、ステップ１８は、長期平均探索パターンサイズに応じて探索パターンを規定するステップを包含する。初期化後にマクロブロックを予測する特殊な場合、ステップ２０の第１、第２および第３のサブステップで用いられる値はゼロであるか、またはユーザによって規定される値である。
【００６９】
図５に示す方法は、ステップ２０の後、ステップ１２またはステップ２２に進む。プロセスは、ステップ１２に戻り、ステップ１２において予測されたばかりの第１のブロックに続いて、次のマクロブロックに対して位置変化予測プロセスを連続して繰り返す。プロセスは、ステップ１２からステップ２０を連続して繰り返し、実質的にすべてのビデオフレームにおける実質的にすべてのマクロブロックの動きを予測する。ステップ２２は、方法の終了を示す。得られる積は、マクロブロック位置の変化の予測であり、サーチパターンサイズ、またはサーチ反復数は、フレーム間の動きの履歴、または前に予測されたマクロブロック間のＳＡＤの履歴と共に変化する。
【００７０】
ステップ１８は、サーチウィンドウにおける複数のブロックサイズマトリクスのそれぞれと、現フレームにおける第１のブロックとの間の輝度画素データの差の絶対値の和（ＳＡＤ）を計算することによって輝度画素データを比較することを含む。従って、最小ＳＡＤ（ＳＡＤ＿ｍｉｎ）を用いたブロックサイズマトリクスの計算は、第１ブロックと最終候補マトリクスとの間の輝度画素データの比較である。
【００７１】
ステップ１６は、輝度画素データの短期平均比較としてＳＡＤ（ＳＡＤ＿ａｖｅ）の短期平均を含む。次に、ステップ２０の第１サブステップは、ステップ１８で計算されたＳＡＤ＿ｍｉｎでＳＡＤ＿ａｖｅを更新することを含む。このように、ＳＡＤ＿ａｖｅは、ステップ２０における次のブロック位置変化予測の準備のためのステップ２０の第１サブステップにおけるＳＡＤ値で更新される。
【００７２】
ステップ２０の第２サブステップは、輝度画素データの長期平均比較として長期平均（ＳＡＤ＿ａｖｅＬＴ）を含む。即ち、第２サブステップは、ステップ１８で計算されたＳＡＤ＿ｍｉｎでＳＡＤ＿ａｖｅＬＴを更新することを含む。このように、ＳＡＤ＿ａｖｅＬＴは、第３サブステップにおける準備のためのステップ２０の第２サブステップにおいてＳＡＤ値で更新される。
【００７３】
ステップ２０の第１サブステップは、フレーム内のブロックの総数（例えば、現フレーム内のブロックの総数）に応じて、ＳＡＤ＿ａｖｅを更新することを含む。本発明のいくつかの局面において、フレームは、９９個のブロックを含む。同様に、ステップ２０の第２サブステップは、複数のフレームにおけるブロックの総数に応じて、ＳＡＤ＿ａｖｅＬＴを更新することを含む。本発明のいくつかの局面において、３フレームにおけるマクロブロックの数（３×９９）が用いられる。
【００７４】
本発明の好ましい実施態様において、ステップ２０の第４サブステップ（不図示）は、ステップ２０の第１サブステップの後、ステップ１８において計算されたＳＡＤ＿ｍｉｎ、ステップ２０の第１サブステップにおいて更新されたＳＡＤ＿ａｖｅ、およびフレーム内のマクロブロックの数に応じて、ＳＡＤ（ＳＡＤ＿ｖａｒ）の変動を計算する。ＳＡＤ＿ｖａｒが用いられるとき、ステップ１６ｂ（不図示）は、ステップ１６の後であって、ステップ１８の前に、ＳＡＤ＿ｖａｒを提供し、ステップ２０は、ＳＡＤ＿ｖａｒに応じてサーチパターンを規定することを含む。ＳＡＤ＿ａｖｅ、ＳＡＤ＿ａｖｅＬＴ、およびＳＡＤ＿ｖａｒの詳細な定義は、以下に提供される。
【００７５】
図６は、図５のフローチャートのさらに詳細な図である。ステップ１０、１２、１４および１６は、図５および図６の両図におけるステップと実質的に同じであり、ここでは繰り返し説明しない。図６を参照すると、ステップ３８は、ステップ１６において提供される輝度画素データの短期平均比較値に応じて、ステップ１４において選択された候補マトリクスを中心とした、サーチウィンドウサイズを計算する。ステップ３８は、ブロックサイズマトリクス間のスペーシングが、最小スペーシングになるまで必要なステップ４０から４２の反復（ＭＥ＿ｓｔｅｐ）数でサーチウィンドウサイズを規定することを含む。あるいは、潜在的な候補マトリクス間の初期スペーシングは、ステップ３８において計算されたＭＥ＿ｓｔｅｐに応じて計算される。
【００７６】
ステップ４０は、サーチウィンドウ内で均一に分布した輝度画素の複数のブロックサイズマトリクスからの輝度画素データと、現フレーム内の第１ブロックの輝度画素データとを比較する。通常、輝度画素のブロックは、それぞれが、１６×１６マトリクスの輝度画素を含むマクロブロックである。このように、現フレーム内の第１ブロックの輝度画素データに最も類似した輝度画素データを有する新しい候補マトリクスが選択される。サーチパターンの計算を助ける平均を用いることによって、サーチウィンドウサイズは、フレーム間の動き履歴と共に変化する。ステップ４０は、最初、ＭＥ＿ｓｔｅｐの値に応じて、サーチウィンドウ内で比較される複数のブロックサイズマトリクスを分布させる。ステップ４０の第１の反復における初期分布の後、ステップ４０の次の反復はすべて、サーチウィンドウサイズを半分に減少させる。
【００７７】
サーチウィンドウにおけるブロックサイズマトリクス間の最小スペーシングが提供される。計算は、最小スペーシング１画素を形成するか、または隣接する画素間に距離を形成することによって簡単にされる。しかし、本方法は、任意のスペーシング、または画素ロケーション間のサブスペーシングに適用可能である。
【００７８】
ステップ４２は、ステップ４０の後、ステップ４０を繰り返す度に、サーチウィンドウ内に配置された複数のブロックサイズマトリクス間のスペーシングを減少させる。このように、サーチフィールドは、新しい候補マトリクスのサーチを繰り返す度に、前のフレームの領域にさらに狭くフォーカスされるようになる。
【００７９】
決定ブロック４４は、以下のようにサーチを繰り返す。
【００８０】
複数のブロックサイズマトリクス間のスペーシングが最小スペーシングよりも大きいかまたは等しいとき、プロセスは、ステップ４０に戻り、複数のブロックサイズマトリクス間のスペーシングが最小スペーシングよりも小さいとき、プロセスは、ステップ４６まで連続する。
【００８１】
ステップ４６は、ステップ４０の最終反復において選択された最終候補マトリクスの輝度画素データと、現フレーム内の最初のブロックの輝度画素データとを比較し、輝度画素データの最終比較を計算し、それによって、最終候補マトリクスと最初のブロックとの間のブロック位置における相違が、フレーム間の動きを記載するベクトルを与える。プロセス中のこのステップにおいて、第１のブロックについての変化位置予測は完了する。しかし、プロセスは、第１のブロックに続く一連のマクロブロック内の次のマクロブロックの位置の変化を予測するのに必要な統計学を続いて準備する。
【００８２】
本発明の１つの局面において、ステップ３８は、５の最大ＭＥ＿ｓｔｅｐを用いることを含む。あるいは、決定ブロック４４は、ステップ４０において潜在的な候補ブロック間の最少スペーシングが得られたか否かに関する決定に応じて、ステップ４０から４２に、最大５の反復を繰り返させる。本発明の方法には、ＭＥ＿ｓｔｅｐの値が５を越えるかまたは５未満になることを防止するものは何もなく、数字は、速度とは対照的に、精度に対する必要性に応じて変化する（計算の数が減少する）。ＴＶまたは映画シーケンスなどの応用によっては、運動内容が大きく、精度が重要であり、ＭＥ＿ｓｔｅｐは、５を越える。ビデオおよび電話会議では、ＭＥ＿ｓｔｅｐは、場合によっては、５未満に減少するので、他の情報は、運動内容が小さいときに通信され得る。
【００８３】
ステップ４６に続くステップ４８は、一連のマクロブロック中における現在の予測の最初のブロックに続く次のマクロブロックに対して位置予測がなされたとき、ＡＭＥＳＳＡＤ法の次の繰り返しにおけるステップ１６で与えられる輝度画素データの短期平均比較を更新する。ステップ４８で計算された短期平均は、ステップ４６で計算された輝度画素データの最終比較によって更新されることにより、最初のブロックの現在の予測が行われた後に短期平均をステップ４８で変更する。ステップ４８で計算された短期平均はこれで、プロセスの次の繰り返しにおけるステップ１６（一連のマクロブロック中における最初のマクロブロックに続くマクロブロックに対する位置変化予測がなされる）において提供のための準備が整ったことになる。
【００８４】
上述のように、マクロブロックはスライスにグループ分けされる。スライスの１グループが１フレームを構成する。典型的には、マクロブロックはスライス中において連続して並べられることにより、マクロブロック予測は常に同じ順番でなされる。スライス中の各マクロブロックが予測されると、プロセスは次のスライスに続く。フレームの最後という特殊な状況においては、最後のスライスの最後のマクロブロックが、次のフレーム中の最初のスライスの最初のマクロブロックのステップ１６で用いられる短期平均をステップ４８において更新する。すなわち、現フレームの最初のスライス中において最初に発生するマクロブロックは、参照フレーム中の最後のスライスの最後のマクロブロックに続いて予測される。あるいは、現フレームの最初のブロックの予測には、前フレーム中のユーザ定義されたマクロブロックを用いる。
【００８５】
ステップ４８に続くステップ５０は、サーチウィンドウサイズの長期平均を、ステップ４８で更新された輝度画素データの短期平均比較によって更新する。本発明の１局面において、ステップ１６の後かつステップ３８の前に、追加的なステップ１６ａ（図示せず）においてサーチウィンドウサイズの長期平均を提供する。この場合、ステップ３８は、前のブロック変化予測のステップ５０で計算された、ウィンドウサーチサイズの長期平均に応じて、サーチウィンドウサイズを計算することを包含する。すなわち、最初のマクロブロックの予測プロセスの終わりにおいて、新しく更新された短期平均を用いて、ステップ１６ａにおいて次のブロックの位置変化予測の準備のため、ステップ５０におけるサーチウィンドウサイズの長期平均を更新する。次に、画素データの短期平均およびサーチウィンドウの長期平均を、一連のマクロブロック中において最初のマクロブロックに続くマクロブロックのステップ３８において、ＭＥ＿ｓｔｅｐの計算に用いる。換言すれば、ステップ３８において、ローカルＭＥ＿ｓｔｅｐをＭＥ＿ｓｔｅｐおよびＭＥ＿ｓｔｅｐＡｖｅのローカル平均について決定する。ＭＥ＿ｓｔｅｐＡｖｅは、ローカル決定プロセスの外部で決定される。ユーザ定義されてもよく、また、後述のＳＡＤ長期挙動によって更新され得る。ＭＥ＿ｓｔｅｐＡｖｅは、複数のマクロブロック位置平均予測にわたって得られた、実効的なＭＥ＿ｓｔｅｐ平均である。
【００８６】
本発明のいくつかの局面においてＭＥ＿ｓｔｅｐの決定において用いられる、動き予測ステップＭＥ＿ｓｔｅｐＡｖｅにおける長期平均は、ユーザ指定である。下記に、ＭＥ＿ｓｔｅｐＡｖｅ変数をユーザが予め定義した値から適応型に更新するモデルを作成している。
【００８７】
１ビデオフレーム中において、マクロブロックは異なる動きの程度を有している。ローカル動き予測サーチウィンドウサイズは、ローカルＳＡＤ統計分布に基づいて決定される。長期的には（すなわちビデオシーケンス中の数フレームにわたって）、各フレームは異なる動き内容を有している。動きが少ないフレームのセグメントについては、より小さいサーチウィンドウを動き予測に用いることによって計算を減らすことが望ましい。動き内容が多大であるときは、サーチウィンドウは、動きベクトルの大きな変化に十分対応できるほど大きくなければならない。
【００８８】
ステップ５２は、輝度画素データの長期平均比較を、ステップ４６で計算された輝度画素データの最終比較によって更新する。この結果、長期平均は、次のマクロブロックを予測する際に用いられる最初のブロックの位置変化予測によって更新される。本発明のいくつかの局面において、ステップ５０は、長期平均サーチウィンドウサイズを、輝度画素データの長期平均に応じて更新することを包含する。図６においてステップ５２がステップ４８の後かつステップ５０の前に示されているのは、ステップ５２の結果をステップ５０で行われる計算に用いているからである。
【００８９】
フレーム間の輝度画素データを比較するための様々な手段が存在する。これらの方法のうちいくつかは、最小２乗平均誤差測定および、周波数領域における量子化ＤＣＴ係数の和を包含する。差の絶対値の和（ＳＡＤ）法は、計算が単純でありかつ有効な比較手段であることがわかっている。本発明の好適な実施態様において、ステップ３８は、サーチウィンドウ内の複数のブロックサイズのマトリクスの各々と、現フレームの最初のブロックとの間の輝度画素データの差の絶対値の和（ＳＡＤ）を計算することによって、輝度画素データを比較することを包含する。最小のＳＡＤを有するブロックサイズのマトリクスを、ステップ４０〜４２の次の繰り返しの際の候補マトリクスとして選択する。さらに、ステップ４６は、最小のＳＡＤ（ＳＡＤ＿ｍｉｎ）を有するブロックサイズのマトリクスを、輝度画素データの最終比較として計算することを包含する。
【００９０】
本発明のいくつの局面は、さらなるステップとして、ステップ１４の後かつステップ１６の前に、ステップ１４ａ（図示せず）を包含する。ステップ１４ａは、ステップ１４で選択された初期の候補マトリクスと現フレームの最初のブロックとの間のＳＡＤを計算することにより、ＳＡＤ＿ｉｎｉｔを導出する。この場合ステップ３８は、ステップ１４ａで計算されたＳＡＤ＿ｉｎｉｔに応じてサーチウィンドウサイズを計算することを包含する。
【００９１】
各マクロブロックの動き予測の初めに、ステップ１４において、動き予測を開始するための初期中心動きポイントを選択する。この初期ポイント（ｘｉ，ｙｉ）は、同一フレーム中の周囲のマクロブロックから予測されるか（フレーム内予測）、最後の参照フレームの動き予測結果から予測される（フレーム間予測）。初期動きサーチポイントのＳＡＤはＳＡＤ＿ｉｎｉｔである（ステップ１４ａ）。ＭＥ＿ｓｔｅｐＡｖｅ（前のブロック予測のステップ５２）について、ＳＡＤ＿ｉｎｉｔをＳＡＤ＿ａｖｅ（前ブロック予測のステップ４８）と比較し、ＳＡＤ＿ｖａｒ（前ブロック予測のステップ５４として後述部分で導入する）をスケール化係数として用いることにより、ＭＥ＿ｓｔｅｐ（ステップ３８）が選択される。ＭＥ＿ｓｔｅｐは、ＳＡＤ＿ｉｎｉｔに関するガウス分布モデルに従って割り当てられる。ＳＡＤ＿ｉｎｉｔが小さければ、ＭＥ＿ｓｔｅｐも小さくなる。
【００９２】
ＳＡＤ＿ｉｎｉｔ（ステップ１４ａ）は、最初のマクロブロックについて、マクロブロックの動き予測（ＭＥ）のちょうど開始時に計算されたＳＡＤであることに留意されたい。一方、ＳＡＤ＿ｍｉｎは、ＭＥの最後（ステップ４６）でのＳＡＤである。これらは一般に値が異なっている。ＳＡＤ＿ｉｎｉｔは、ＭＥステップサーチの中心開始ポイントについて計算されたＳＡＤ値である。ＳＡＤ＿ｍｉｎは、全てのサーチポイントについての最小値である。ＳＡＤ＿ｉｎｉｔはＭＥサーチステップを決定するために用いられる。ＳＡＤ＿ｍｉｎはＭＥ統計パラメータを更新するために用いられる。
【００９３】
ステップ４８は、輝度画素データの短期間平均比較としての、ＳＡＤ（ＳＡＤ＿ａｖｅ）という短期間平均を含む。従って、ステップ４８は、ステップ４６で計算したＳＡＤ＿ｍｉｎで、ＳＡＤ＿ａｖｅを更新することを含む。このようにして、ＳＡＤ＿ａｖｅは、第１のブロックの位置変化が評価された後のＳＡＤ値で更新される。ステップ４８はさらに、フレーム内のブロックの数に応じてＳＡＤ＿ａｖｅを計算することを含む。特に、ステップ４８は、以下のＳＡＤ＿ａｖｅの計算を含む。
【００９４】
【数２】
0003793657.tif 000003
上記式において、（ＳＡＤ＿ａｖｅ）0は前のマクロブロック位置変化評価からのＳＡＤ＿ａｖｅであり、ｎｕｍＭＢはフレーム内のマクロブロックの数である。
【００９５】
ステップ５２は、輝度画素データの長期間平均比較としての、（ＳＡＤ＿ａｖｅＬＴ）という長期間平均を含む。すなわち、ステップ５２は、ステップ４６で計算したＳＡＤ＿ｍｉｎで、ＳＡＤ＿ａｖｅＬＴを更新することを含む。それにより、ＳＡＤ＿ａｖｅＬＴは、第１のブロックの位置変化が評価された後のＳＡＤ値で更新される。ステップ５２はさらに、複数のフレーム内のブロックの総数に応じてＳＡＤ＿ａｖｅＬＴを計算することを含む。特に、ステップ５２は、以下のＳＡＤ＿ａｖｅＬＴの計算を含む。
【００９６】
【数３】
0003793657.tif 000004
上記式において、（ＳＡＤ＿ａｖｅＬＴ）0は前のマクロブロック位置変化評価から計算されたＳＡＤ＿ａｖｅＬＴであり、ｎｕｍＭＢｓＬＴはユーザにより定義された複数のフレーム内のマクロブロックの総数である。
【００９７】
長期間統計ウィンドウ長ｎｕｍＭＢｓＬＴは、ｎｕｍＭＢよりも大きく、通常、いくつかのフレーム、例えば、３フレームをカバーする。ＳＡＤ＿ａｖｅＬＴは、各マクロブロックに関して、ＳＡＤ＿ａｖｅでゼロに初期化され、動き評価の完了時に更新される。
【００９８】
典型的には、ステップ４０は、輝度画素データまたはＳＡＤを、ステップ１２で選択されたマクロブロックとサーチウィンドウ内で画素間隔の総数によって均一に分離された少なくとも８ブロックサイズのマトリクスとの間で比較することを含む。本発明の方法は様々なサーチウィンドウ形状と候補マトリクス形状とに適用可能であるが、サーチの標準的固定ステップ法での使用に関して周知であるように、正方形のサーチウィンドウサイズが有効であることが判明している。上述し且つ図４に示すように、固定ステップ法においては、８つの潜在的候補マトリクスが、サーチウィンドウの辺に沿って配置され、各隅に１マトリクスずつ配置されている。第９番目のマトリクスは中央に位置している。最小のＳＡＤ値を有する候補マトリクスが次のサーチ反復において中央マトリクスとして用いられるため、ステップ４０の次反復において中央マトリクス用のＳＡＤ値を計算する必要がない。特定の環境において、サーチウィンドウは、いくつかの潜在的候補マトリクスがフレーム外または「スクリーン」外に位置するように、位置づけられている。これらの場合、フレーム外の候補マクロブロック用にＳＡＤ値を計算する必要がない。
【００９９】
本発明のある局面において、ステップ４８の後のステップ５４は、ステップ４６で計算されたＳＡＤ＿ｍｉｎ、ステップ４８で更新されたＳＡＤ＿ａｖｅ、およびフレーム内のマクロブロックの数に応じてＳＡＤ（ＳＡＤ＿ｖａｒ）の変化を計算する。ＳＡＤ＿ｖａｒは、前のマクロブロック位置変化評価から導かれた更新された値である。特に、ステップ５４は、以下のＳＡＤ＿ｖａｒの計算を含む。
【０１００】
【数４】
0003793657.tif 000005
上記式において、（ＳＡＤ＿ｖａｒ）0は、前のマクロブロック位置変化評価からのＳＡＤ＿ｖａｒであり、「ｓｑｒｔ」は、「〜の平方根」を表す。
【０１０１】
本発明のある局面において、ステップ１６の後で且つステップ３８の前に更なるステップ１６ｂ（図示せず）が含まれる。ステップ１６ｂは、ＳＡＤ＿ｖａｒを供給する。ステップ４８、５０および５２の他の統計と同様、ステップ５４で更新されたＳＡＤ＿ｖａｒ値がステップ１６ｂで供給されて、ＡＭＥＳＳＡＤ法の次反復のステップ３８で用いられることにより、第１のブロックに続く次のマクロブロックの位置変化が評価される。ステップ３８は、前のブロック評価のステップ５４で計算されてステップ１６ｂで供給されたＳＡＤ＿ｖａｒに応じてＭＥ＿ｓｔｅｐを計算することを含む。特に、ステップ３８は、以下のＭＥ＿ｓｔｅｐの計算を含む。
【０１０２】
【数５】
0003793657.tif 000006
本発明の方法は、ステップ５４に続いてステップ１２に戻り、位置変化評価用の一連のマクロブロック内の次のマクロブロックの選択を行う。あるいは、上記方法は、動き評価プロセスの最終ステップであるステップ５６に進む。ステップ５６において、サーチウィンドウサイズは、フレーム間の動きの履歴に伴って変化する。方法がステップ１２に進むと、ステップ４８、５０および５２で更新された統計パラメータは、最も最近処理されたマクロブロックについて、ｎｕｍＭＢの長さを有するスライディングウィンドウに亘ってＳＡＤ統計を有効に表す。
【０１０３】
ステップ５０において、ＭＥ＿ｓｔｅｐＡｖｅは、最近のｎｕｍＭＢマクロブロックの統計的ＳＡＤ挙動を表すＳＡＤ＿ａｖｅを、ｎｕｍＭＢｓＬＴマクロブロックに亘ってＳＡＤ＿ａｖｅＬＴで表される長期傾向と比較することにより、ｎｕｍＭＢの長さを有する局部ウィンドウ用に決定される。有効なＭＥ＿ｓｔｅｐＡｖｅは、ＳＡＤ＿ａｖｅとＳＡＤ＿ａｖｅＬＴとの差違を閾値とすることに割り当てられる。ＳＡＤ＿ａｖｅがＳＡＤ＿ａｖｅＬＴよりもある程度小さいということは、局部フレームがより小さい全体動きを有することを意味し、従って、ステップ平均ＭＥ＿ｓｔｅｐＡｖｅは減少する。その逆もまた同様である。
【０１０４】
本発明のある局面において、ＭＥ＿ｓｔｅｐＡｖｅは、４の値で初期化され、ステップ５０は、以下のように、ＭＥ＿ｓｔｅｐＡＶＥの計算を更新することを含む。
【０１０５】
【数６】
0003793657.tif 000007
上記式においてａ0＞ａ1＞ａ2＞０である。
【０１０６】
ａ0、ａ1およびａ2の値は、評価手順が用いられる特定の環境に従って変化する。１つの有用な順番付けは、ステップ５０において、ａ0の値を１０にし、ａ1の値を８にし、ａ2の値を７にすることである。
【０１０７】
本発明のある局面において、ステップ４０は、ステップ３８で計算されたＭＥ＿ｓｔｅｐの値を用いて、ｓを計算することを含む。指定子ｓは、まずサーチウィンドウ内の隣接するマクロブロックサイズのマトリクスの中心（または上左隅）を分離する画素の数を表す。その場合、ｓは以下のように計算される。
【０１０８】
【数７】
0003793657.tif 000008
次に、ステップ４２は、ｓの値を２で割ることにより、ステップ４０〜４２を実行する度にサーチウィンドウ内のマクロブロック間の間隔を低減するステップを含む。
【０１０９】
図７は、図６に記載された変数の相対的な範囲を示す。ＳＡＤ＿ｉｎｉｔ、ＳＡＤ＿ｍｉｎおよびＭＥ＿ｓｔｅｐは完全にローカルな値とし、現マクロブロック内でのみ使用する。ＳＡＤ＿ａｖｅ、ＳＡＤ＿ｖａｒおよびＭＥ＿ｓｔｅｐＡＶＥは短期値とする。アプリケーションに応じて、これらの変数の公式(formula)を変化させることによって、最新の更新をより強調したり、あるいは軽めに扱ったり(de-emphasize)する。
【０１１０】
ＭＥ＿ｓｔｅｐのローカル適応およびＭＥ＿ｓｔｅｐＡｖｅの短期適応を組み合わせることによる全体的な効果として、比較的小さなステップサイズが比較的動きの少ない領域に割り当てられ、比較的大きなステップサイズが難しい領域に割り当てられる。長期的には、ＭＥ＿ｓｔｅｐＡｖｅは、ＳＡＤ＿ａｖｅＬＴとの比較においてＳＡＤ＿ａｖｅの変化に応じて変化する。ローカルフレームのある範囲内において、各マクロブロックについての動き予測ステップサイズを、そのマクロブロックの動きを隣接するマクロブロックと比較することによってさらに適応的に求める。
【０１１１】
以下に、ＡＭＥＳＳＡＤアルゴリズムの疑似コードを示す。
【０１１２】
【表１】
0003793657.tif 000009
図８に、本発明による方法を固定ステップ法と比較するために、あるビデオ画像の１フレームを例示する。フレーム内の３つのマクロブロックにラベルを付けている。マクロブロックｉ６０は、ほとんど動きのない領域である。マクロブロックｊ６２は、マクロブロックｉ６０よりは動きのある領域であり、マクロブロックｋ６４は、最も動きの大きい領域である。
【０１１３】
固定ステップサイズサーチでは、マクロブロックｉ６０の動きベクトルが（１，−１）であることを求めるために４ステップを必要とする。ここでは、ある位置から右および下方向への移動を正（＋）の移動とし、上および左方向への移動を負（−）の移動とする。図９は、固定ステップサイズ法（従来技術）を用いた場合の、図８のマクロブロックｉ６０に対するサーチ手順を示す。中心のスタート位置が（０，０）である。各サーチステップでの最小ＳＡＤのサーチポイントに星印を付けている。マクロブロックｉ６０の移動は最小であるので、初めの３サーチステップの間、最小ＳＡＤ点は常に中心である。即ち、このサーチにおける初期スタート位置として用いるブロックサイズのマトリクスは、最小ＳＡＤ値を用いて最終的に選択したマトリクスと同じである。
【０１１４】
図１０は、ＡＭＥＳＳＡＤアルゴリズムに従って図８のマクロブロックｉ６０に対して行われる１ステップサーチを示す。ＡＭＥＳＳＡＤアルゴリズムを用いる場合、アルゴリズムは、マクロブロックのＳＡＤが小さいことを決定するので、マクロブロックの動き予測は１ステップのみで行われる。マクロブロックに対するＳＡＤは非常に小さく、マクロブロックに対するの動きベクトルは、初めに予測した動きベクトルに非常に近いか、または等しい。これにより、演算量を大幅に節約しながら同じ動きベクトルを得ている。一般に、ＡＭＥＳＳＡＤアルゴリズムを用いて得られる動きベクトルは、固定ステップサイズ法で得られるベクトルに非常に近いか、または等しい。
【０１１５】
図１１は、図８のマクロブロックｊ６２に対する固定ステップサイズサーチ手順を示す（従来技術）。マクロブロックｊ６２の場合、４ステップのサーチを行うことにより動きベクトル（１，−２）が得られる。図１２は、図８のマクロブロックｊ６２のサーチにおいて、ＡＭＥＳＳＡＤアルゴリズムによって決定されるサーチパスを示す。マクロブロックｊ６２の場合、そのＳＡＤ値の統計的挙動に基づいて、ＡＭＥＳＳＡＤアルゴリズムは３ステップのサーチを行う（マクロブロックｊ６２のＳＡＤ値は、ＳＡＤ平均値付近である）。やはりこの例でも、結果的に同じ動きベクトルが得られている。図１１と図１２を比較すると、ＡＭＥＳＳＡＤ法では、まるまる１回分のサーチ（即ち、８回のコスト演算）が節約できていることが分かる。
【０１１６】
図１３は、図８のマクロブロックｋ６４について、ＡＭＥＳＳＡＤアルゴリズムおよび固定ステップサイズアルゴリズムによって決定される同じサーチパスを示す。最後に、マクロブロックｋ６４は、非常に大きな動きを持つマクロブロックの例であり、良好な一致を見つけるには、大きなサーチ範囲を用いた広範な動きベクトルサーチが必要である。マクロブロックｋ６４は、ＳＡＤの平均よりも大幅に大きいＳＡＤ値を有し、その偏差はＳＡＤの分散よりも大きい。このような場合、ＡＭＥＳＳＡＤアルゴリズムは、フルステップサーチ（４ステップ）を行うことになる。
【０１１７】
ＡＭＥＳＳＡＤモデルは、典型的なビデオシーケンスにおいて、画素データが連続的であり、連続フレーム間の移動もなめらかであることを利用している。さらに、大きな動きベクトルの領域は大きな動きベクトル変化に関連する。本発明の新規なＡＭＥＳＳＡＤアルゴリズムは、ローカルな動きの統計的挙動に応じて、適応的に演算量を割り当てることによって、固定ステップサイズサーチアルゴリズムを改良する。結果的に、本発明のアルゴリズムは、動きベクトル精度を維持しながら、全体の動き予測演算量を低減する。大量の実験結果から、本発明のアルゴリズムによって動き予測速度が最大約３５％上昇することが示された。
【０１１８】
本発明のアルゴリズムは、シーケンスの初めには、最大範囲の動き予測サーチを行う。これにより、予測された複数の動きベクトルが実際の動きベクトルに適時に収束することを確実にする。本発明のＡＭＥＳＳＡＤ動きサーチアルゴリズムは、プラットホームから独立しており、ハードウェアおよびソフトウェアのいずれにも容易に適用できる。さらに、本アルゴリズムは、動きのあるシーケンス内の複数フレーム間にわたって、または１フレーム内において、複数の領域を効果的に差別化するので、動きの多い領域により多くの力が注がれる。結果的に、動きの豊富な内容を持つオブジェクトは、より正確な動きベクトルでコード化される。一般に、このようなオブジェクトはフォアグランドに相当し、より重点が置かれるオブジェクトである。比較的動きの少ない内容を持つオブジェクトは、固定ステップサイズサーチと比べて比較的精度の低い動き動きベクトルを用いてコード化される。ビデオシーケンスにおいて視覚的に重要なオブジェクトは、質がより高くなるようにコード化される。これにより、多くの場合、より良い画質が得られる。
【０１１９】
本発明によるＡＭＥＳＳＡＤ法を、現フレームにおいてマクロブロックを選択し、基準フレームにおいて対応するマクロブロック内でサーチを行う場合について説明した。本方法は、この反対の処理（基準フレームにおいてマクロブロックを選択し、現フレーム内において対応するマクロブロックサイズのマトリクスについてサーチを行う処理）にも適用可能である。さらに、本方法は、色差データ画素を使用する場合、または、輝度画素および色差画素を組み合わせて使用する場合にも適用可能である。本発明のＡＭＥＳＳＡＤ法のその他の更新例および実施例も当業者には可能である。
【０１２０】
【発明の効果】
本発明によれば、隣接するマクロブロック内の動き予測から計算される、位置の平均的な変化に応じてサーチウィンドウサイズを調節する、固定ステップ動き予測法と共に使用される方法が提供される。
【０１２１】
本発明によって、Ｈ．２６ＰおよびＭＰＥＧ−Ｘ規格のビデオ圧縮のような、動き補償および変換を利用したハイブリッドビデオコーダーの実施を向上する。固定ステップサイズの動き予測と比較して、本発明による適応型アルゴリズムは、動き予測、ひいては全体的なビデオエンコード速度を向上する。さらに、本発明のアルゴリズムでは、動きの度合いによって各領域を差別化し、動きの内容がより豊富なローカルエリアまたはローカルフレームに対してより多くの動き予測リソースを割り当てるので、多くの場合、向上した画質が得られる。
【図面の簡単な説明】
【図１】ビデオエンコード方法のブロック図である（従来技術）。
【図２】現フレームの現在のマクロブロックと前フレームのサーチウィンドウとの間の空間的な関係を示す図である（従来技術）。
【図３】固定ステップ動き予測法を示すフローチャートである（従来技術）。
【図４】図３のステップ−サーチ法での直前の３ステップを示す例（従来技術）を示す図である。
【図５】現フレームの一連のブロック内の輝度画素データマトリックスによって表される画像の位置の変化を、前フレームの対応するブロックサイズ輝度画素データマトリックスから効率的に予測する方法を示すフローチャートである。
【図６】図５のフローチャートをもっと詳細に示すフローチャートである。
【図７】図６に示した変数の相対的な範囲を示す図である。
【図８】本発明の方法を固定ステップ法と比較するためのビデオ画像フレームの例を示す図である。
【図９】固定ステップ法を用いた、図８のマクロブロックｉに関連するサーチ手順（従来技術）を示す図である。
【図１０】ＡＭＥＳＳＡＤアルゴリズムにより行われる、図８のマクロブロックｉのためのワンステップサーチを示す図である。
【図１１】図８のマクロブロックｊのための固定ステップサーチ手順（従来技術）を示す図である。
【図１２】図８のマクロブロックｊのサーチのためのＡＭＥＳＳＡＤアルゴリズムによって決定されるサーチパスを示す図である。
【図１３】図８のマクロブロックｋのための、ＡＭＥＳＳＡＤおよび固定ステップアルゴリズムの両方によって決定される同じサーチパスを示す図である。
【符号の説明】
６０  マクロブロックｉ
６２  マクロブロックｊ
６４  マクロブロックｋ
【図１】
0003793657.tif 000010
【図２】
0003793657.tif 000011
【図３】
0003793657.tif 000012
【図４】
0003793657.tif 000013
【図５】
0003793657.tif 000014
【図６】
0003793657.tif 000015
【図７】
0003793657.tif 000016
【図８】
0003793657.tif 000017
【図９】
0003793657.tif 000018
【図１０】
0003793657.tif 000019
【図１１】
0003793657.tif 000020
【図１２】
0003793657.tif 000021
【図１３】
0003793657.tif 000022