(57)【要約】本発明は動き推定の実現方法を開示する。該方法は、複数のブロックモードを設定し、ブロックモードごとにより、現在マクロブロックを計算ブロックにそれぞれ分割するステップと、ブロックモードごとに対して、現在マクロブロックにおける全ての計算ブロックの動きベクトルをそれぞれ計算するステップと、ブロックモードごとに対して、現在マクロブロックにおける全ての計算ブロックと、それぞれの動きベクトルに対応するブロックとのマッチング値の和をそれぞれ計算し、最小の和の値に対応するブロックモードを取得し、取得されたブロックモードに対応する動きベクトルを現在マクロブロックの動きベクトルとするステップと、を含む。本発明は、動き推定においてブロックマッチング値の計算時間を大きく低減し、ビデオデータの圧縮速度を高め、ビデオデータのリアルタイム性のニーズを満足させ、ユーザの満足度を向上させる。
2008515298.tif 000002
【特許請求の範囲】
【請求項１】
動き推定の実現方法であって、
複数のブロックモードを設定し、ブロックモードごとにより、現在マクロブロックを計算ブロックにそれぞれ分割するステップＡと、
ブロックモードごとに対して、現在マクロブロックにおける全ての計算ブロックの動きベクトルをそれぞれ計算するステップＢと、
ブロックモードごとに対して、現在マクロブロックにおける全ての計算ブロックと、それぞれの動きベクトルに対応するブロックとのマッチング値の和をそれぞれ計算し、最小の和の値に対応するブロックモードを取得し、取得されたブロックモードに対応する動きベクトルを現在マクロブロックの動きベクトルとするステップＣと、
を含むことを特徴とするこの方法。
【請求項２】
ステップＢにおいて、最小の計算ブロックを含むブロックモードに対して、現在マクロブロックにおける全ての計算ブロックの動きベクトルを計算するステップは、最小の計算ブロックを含むブロックモードに対して、現在マクロブロックにおける全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算することを含むことを特徴とする請求項１記載の方法。
【請求項３】
ステップＢにおいて、他のブロックモードに対し現在マクロブロックにおける全ての計算ブロックの動きベクトルを計算するステップは、他の各ブロックモードに対して、それぞれ現在マクロブロックにおける全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算することを含むことを特徴とする請求項２に記載の方法。
【請求項４】
ステップＢにおいて、他のブロックモードに対し現在マクロブロックにおける全ての計算ブロックの動きベクトルを計算するステップは、他の各ブロックモードに対して、それぞれ、既に計算された各計算ブロックの動きベクトルの和を用いて現在マクロブロックにおける全ての計算ブロックの動きベクトルを得ることを含むことを特徴とする請求項２に記載の方法。
【請求項５】
ステップＢにおいて、他のブロックモードに対し既に計算された各計算ブロックの動きベクトルの和を用いて現在マクロブロックにおける全ての計算ブロックの動きベクトルを得る前に、
前記他のブロックモードにおける計算ブロックを構成する最小の計算ブロックのブロックマッチング値が既に計算されたかどうかを判断し、既に計算されたら、前記した他のブロックモードに対して、それぞれ既に計算された各計算ブロックの動きベクトルの和を用いて現在マクロブロックにおける全ての計算ブロックの動きベクトルを得るステップを続いて実行し、計算されていなければ、それぞれ前記他のブロックモードにおける全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算する
ことをさらに含む特徴とする請求項４記載の方法。
【請求項６】
前記既に計算された各計算ブロックの動きベクトルの和を用いて他のブロックモードにおける全ての計算ブロックの動きベクトルを得るステップは、前記他のブロックモードにおける全ての計算ブロックの動きベクトルを得るまで、前記他のブロックモードにおける現在計算ブロックを構成する各最小の計算ブロックのブロックマッチング値の和を前記他のブロックモードにおける現在計算ブロックの動きベクトルとすることを繰り返して実行することを含むことを特徴とする請求項４又は請求項５記載の方法。
【請求項７】
ステップＢにおいて、前記全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算するステップは、
ダイヤモンド探索の開始点を決定し、決定された開始点を現在ダイヤモンド中心点とするステップＢ１と、
現在のブロックモードに対する現在計算ブロックに対して、それぞれ現在計算ブロックと、現在ダイヤモンド中心点周囲の４つの点に対応するブロックとのブロックマッチング値を計算し、ブロックマッチング値が最小となる点を現在ダイヤモンド中心点とし、該ブロックマッチング値が所定の退出条件を満たすまで、現在ダイヤモンド中心点周囲の４つの点に対応するブロックのブロックマッチング値を計算し、退出条件を満たすブロックマッチング値に対応する点を最適なマッチング点とし、最適なマッチング点に対応する動きベクトルを現在計算ブロックの動きベクトルに決定し、現在のブロックモードに対する全ての計算ブロックの動きベクトルが決定されるまで、このステップを繰り返すステップＢ２と、
を含むことを特徴とする請求項２、請求項３又は請求項５記載の方法。
【請求項８】
ステップＢ２の前に、現在マクロブロックの動きベクトルの予測値及び現在のブロックモードに対する計算ブロックの第２閾値を決定し、決定された動きベクトルの予測値と第２閾値に基づいて、ダイヤモンド半径を決定することをさらに含み、
ステップＢ２において、前記現在ダイヤモンド中心点周囲の４つの点は、現在ダイヤモンド中心点の上、下、左及び右方向の、現在ダイヤモンド中心点との距離がそれぞれ決定されたダイヤモンド半径となる４つの点を含む、
ことを特徴とする請求項７記載の方法。
【請求項９】
前記現在マクロブロックの動きベクトルの予測値を決定するステップは、現在マクロブロックの左、正上及び右上のマクロブロックの動きベクトルのメディアン値を取得し、取得されたメディアン値を現在マクロブロックの動きベクトルの予測値に決定することを含むことを特徴とする請求項８記載の方法。
【請求項１０】
前記ダイヤモンド半径を決定するステップは、決定された現在マクロブロックの動きベクトルの予測値と現在マクロブロックの左、正上及び右上のマクロブロックの何れか１つの動きベクトルとが同じであり、且つ、前フレームの画像の現在位置のブロックの動きベクトルが０ではなく、且つ、決定された第２閾値が所定のブロック動き閾値より小さいことを満たしたら、ダイヤモンド半径を１に決定し、満たさなければ、ダイヤモンド半径を２に決定することを含むことを特徴とする請求項８記載の方法。
【請求項１１】
前記第２閾値を決定するステップは、現在のブロックモードに対する現在計算ブロックと、３つ方向以上の隣接点に対応するブロックとのブロックマッチング値に基づいて、第２閾値を決定することを含むことを特徴とする請求項８記載の方法。
【請求項１２】
ステップＢ１において、前記ダイヤモンド探索の開始点を決定するステップは、前フレームの画像の同一位置の動きベクトルと、動きベクトル（０，０）と、現在マクロブロックの左、正上及び右上のマクロブロックの動きベクトルとに基づいて、前記現在計算ブロックのブロックマッチング値を計算し、ブロックマッチング値が最小となる動きベクトルに対応する点をダイヤモンド探索の開始点に決定することを含むことを特徴とする請求項７記載の方法。
【請求項１３】
第１閾値を決定することをさらに含み、
ステップＢ２において、前記ブロックマッチング値が所定の退出条件を満たすことは、ブロックマッチング値が決定された第１閾値より小さいことであり、
ステップＢ２において、前記退出条件を満たすブロックマッチング値は第１閾値より小さいブロックマッチング値である、
ことを特徴とする請求項７記載の方法。
【請求項１４】
前記第１閾値を決定するステップは、現在のブロックモードに対する現在計算ブロックと、３つ方向以上の隣接点に対応するブロックとのブロックマッチング値に基づいて、第１閾値を決定することを含むことを特徴とする請求項１３記載の方法。
【請求項１５】
ステップＢ２において、ブロックマッチング値が所定の退出条件を満たした後、且つ、退出条件を満たしたブロックマッチング値に対応する点を最適なマッチング点とする前に、
決定されたダイヤモンド半径が１であるかどうかを判断し、１であれば、前記退出条件を満たしたブロックマッチング値に対応する点を最適なマッチング点とするステップを続いて実行し、１でなければ、現在の最適なマッチング点を現在ダイヤモンド中心点とし、ダイヤモンド半径周囲の４つの点に対応するブロックのブロックマッチング値を計算し、ブロックマッチング値が最小となる点を最適なマッチング点とし、該最適なマッチング点に対応する動きベクトルを現在計算ブロックの動きベクトルとする
ことをさらに含むことを特徴とする請求項１３又は請求項１４記載の方法。
【請求項１６】
前記ブロックマッチング値は、前記計算ブロックと探索点に対応するブロックとの一対一の画素点の階調値の差の絶対値の和であることを特徴とする請求項１記載の方法。
【請求項１７】
前記現在マクロブロックのサイズが１６×１６画素であることを特徴とする請求項１に記載の方法。
【請求項１８】
前記ブロックモードは、１６×１６画素、又は１６×８画素、又は８×１６画素、又は８×８画素、又は当該４者の任意の組合せであることを特徴とする請求項１７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はビデオデータ圧縮技術に関し、特にビデオデータ圧縮における動き推定の実現方法に関する。
【背景技術】
【０００２】
マルチメディアのアプリケーションにおいて、ビデオデータには実際有効な情報及び冗長データを含む。冗長データは無駄なデータとして、伝送不要であり、且つビデオデータに大量の冗長データがあるため、ビデオデータの冗長データに対して圧縮を行うと、ビデオデータのデータ量を大きく低減することができる。これにより、ビデオデータの記憶とリアルタイム処理を極めて便利にすることが可能となる。
【０００３】
ビデオデータにおいて、冗長データの数、即ち冗長度は構成方面で強い時間相関性が表れる。その原因として、通常、画像における大部分の領域での信号の変化が非常に遅く、特にバックグランド部分がほとんど変わらないため、隣接するフレーム間におけるビデオ信号には比較的強い相関性、即ちフレーム間の相関性が存在する。そのため、フレーム間の相関性を無くすことができれば、ビデオデータを極めて圧縮することができる。
【０００４】
従来、一般に、動き推定方法によりフレーム間の相関性を無くす。即ち、画像の現在フレームのデータに対して、前フレームでそれに最もマッチングする領域を探索し、前フレームのデータに対する現在フレームのデータの動きベクトルを計算し、該動きベクトルを符号化する。ここで、動き推定方法のキーポイントは動きベクトルの決定であることが分かる。
【０００５】
具体的に実現するとき、動き推定方法は通常、ブロックマッチング法により実現される。ブロックマッチング法において、各フレームの画像は２次元のN×N画素のサブブロックに分割される。一般に、Nは16である。各サブブロック内のあらゆる画素が同じ平行運動を行うと想定し、現在フレームのN×N画素のサブブロックに対応する前フレームのサブブロックの隣接領域ウインドーでそれに最もマッチングするサブブロックを探索し、現在サブブロックと前フレームのマッチングブロックとの２次元平面上の変位は動き推定によって得られた動きベクトルである。
【０００６】
ブロックマッチング法におけるマッチングサブブロック探索方法は一般に全域探索法（full search method）である。全域探索法では現在フレームの各マクロブロックに対して、前フレームの特定範囲（通常は隣接領域）で各点のブロックマッチング値を計算し、該隣接領域の各点がマッチング点である。次に、最小のマッチング値に対応するマッチング点を最適なマッチング点とし、最適なマッチング点に対応する動きベクトルを現在マクロブロックの動きベクトルとする。通常、ブロックマッチング値は、マクロブロックと探索範囲内のマッチング点に対応するブロックとの間の一対一の画素点の階調値の差の絶対値の和であり、即ち差分絶対値和（SAD）である。前記マッチング点に対応するブロックはマッチング点が左上角にあるの、マクロブロックのサイズと同じブロックである。ブロックマッチング値、即ちSADの計算公式は以下の通りである。
【０００７】
【数１】
2008515298.tif 000003
【０００８】
ここで、Ｉc(i,j)は現在マクロブロックの画素の階調値を表し、Ｉｒ(i+u,j+v)は前フレームのマッチングマクロブロックの対応画素の階調値を表し、(u,v)は動きベクトルである。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上記説明から分かるように、従来技術では、動きベクトル方法におけるブロックマッチング法を用いてフレーム間の相関性を無くす場合、全域探索法を用いてマッチングサブブロックを探索し、つまり、指定領域内の各点に対して探索を行わなければならない。この遍歴式の探索過程は巨大な計算量につながり、例えば、前フレーム32×32、即ち1024個の点の範囲で探索するとき、各マクロブロックは全て1024個の点を計算する必要がある。これにより、ビデオデータ圧縮の速度が極めて低減されて、ビデオデータのリアルタイム性に対するニーズを満足できないことになる。
【００１０】
本発明は、動き推定の計算量を減少し、ビデオデータ圧縮の速度を高めることができる、動き推定の実現方法を提供することを主な目的とする。
【課題を解決するための手段】
【００１１】
本発明の目的は下記の技術案によって実現されたものである。
【００１２】
動き推定の実現方法であって、
複数のブロックモードを設定し、ブロックモードごとにより、現在マクロブロックを計算ブロックにそれぞれ分割するステップAと、
ブロックモードごとに対して、現在マクロブロックにおける全ての計算ブロックの動きベクトルをそれぞれ計算するステップBと、
ブロックモードごとに対して、現在マクロブロックにおける全ての計算ブロックと、それぞれの動きベクトルに対応するブロックとのマッチング値の和をそれぞれ計算し、最小の和の値に対応するブロックモードを取得し、取得されたブロックモードに対応する動きベクトルを現在マクロブロックの動きベクトルとするステップCと、を含む。
【００１３】
ステップBにおいて、最小の計算ブロックを含むブロックモードに対して、現在マクロブロックにおける全ての計算ブロックの動きベクトルを計算するステップは、最小の計算ブロックを含むブロックモードに対して、現在マクロブロックにおける全ての計算ブロックの動きベクトルをポイント・バイ・ポイント（point by point）で計算することを含む。
【００１４】
ステップBにおいて、他のブロックモードに対し現在マクロブロックにおける全ての計算ブロックの動きベクトルを計算するステップは、他の各ブロックモードに対して、それぞれ現在マクロブロックにおける全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算することを含む。
【００１５】
ステップBにおいて、他のブロックモードに対し現在マクロブロックにおける全ての計算ブロックの動きベクトルを計算するステップは、他の各ブロックモードに対して、それぞれ、既に計算された各計算ブロックの動きベクトルの和を用いて現在マクロブロックにおける全ての計算ブロックの動きベクトルを得ることを含む。
【００１６】
ステップBにおいて、他のブロックモードに対し既に計算された各計算ブロックの動きベクトルの和を用いて前記他のブロックモードにおける全ての計算ブロックの動きベクトルを得る前に、
前記他のブロックモードにおける計算ブロックを構成する最小の計算ブロックのブロックマッチング値が既に計算されたかどうかを判断し、既に計算されたら、前記した他のブロックモードに対して、既に計算された各計算ブロックの動きベクトルの和を用いて前記他のブロックモードにおける全ての計算ブロックの動きベクトルを得るステップを続いて実行し、計算されていなければ、それぞれ前記他のブロックモードにおける全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算する
ことをさらに含む。
【００１７】
前記既に計算された各計算ブロックの動きベクトルの和を用いて他のブロックモードにおける全ての計算ブロックの動きベクトルを得るステップは、前記他のブロックモードにおける全ての計算ブロックの動きベクトルを得るまで、前記他のブロックモードにおける現在計算ブロックを構成する各最小の計算ブロックのブロックマッチング値の和を前記他のブロックモードにおける現在計算ブロックの動きベクトルとすることを繰り返して実行することを含む。
【００１８】
ステップBにおいて、前記全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算するステップは、
ダイヤモンド探索の開始点を決定し、決定された開始点を現在ダイヤモンド中心点とするステップB1と、
現在のブロックモードに対する現在計算ブロックに対して、それぞれ現在計算ブロックと、現在ダイヤモンド中心点周囲の４つの点に対応するブロックとのブロックマッチング値を計算し、ブロックマッチング値が最小となる点を現在ダイヤモンド中心点とし、該ブロックマッチング値が所定の退出条件（exit condition）を満たすまで、現在ダイヤモンド中心点周囲の４つの点に対応するブロックのブロックマッチング値を計算し、退出条件を満たすブロックマッチング値に対応する点を最適なマッチング点とし、最適なマッチング点に対応する動きベクトルを現在計算ブロックの動きベクトルに決定し、現在のブロックモードに対する全ての計算ブロックの動きベクトルが決定されるまで、このステップを繰り返すステップB2と、を含む。
【００１９】
ステップB2の前に、現在マクロブロックの動きベクトルの予測値及び現在のブロックモードに対する計算ブロックの第２閾値を決定し、決定された動きベクトルの予測値と第２閾値に基づいて、ダイヤモンド半径を決定することをさらに含み、
ステップB2において、前記現在ダイヤモンド中心点周囲の４つの点は、現在ダイヤモンド中心点の上、下、左及び右方向の、現在ダイヤモンド中心点との距離がそれぞれ決定されたダイヤモンド半径となる４つの点を含む。
【００２０】
前記現在マクロブロックの動きベクトルの予測値を決定するステップは、現在マクロブロックの左、正上及び右上のマクロブロックの動きベクトルのメディアン値を取得し、取得されたメディアン値を現在マクロブロックの動きベクトルの予測値に決定する。
【００２１】
前記ダイヤモンド半径を決定するステップは、決定された現在マクロブロックの動きベクトルの予測値と現在マクロブロックの左、正上及び右上のマクロブロックの何れか１つの動きベクトルとが同じであり、且つ、前フレームの画像の現在位置のブロックの動きベクトルが0ではなく、且つ、決定された第２閾値が所定のブロック動き閾値より小さいことを満たしたら、ダイヤモンド半径を１に決定し、満たさなければ、ダイヤモンド半径を2に決定することを含む。
【００２２】
前記第２閾値を決定するステップは、現在のブロックモードに対する現在計算ブロックと、３つ方向以上の隣接点に対応するブロックとのブロックマッチング値に基づいて、第２閾値を決定することを含む。
【００２３】
ステップB1において、前記ダイヤモンド探索の開始点を決定するステップは、前フレームの画像の同一位置の動きベクトルと、動きベクトル(0,0)と、現在マクロブロックの左、正上及び右上のマクロブロックの動きベクトルとに基づいて、前記現在計算ブロックのブロックマッチング値を計算し、ブロックマッチング値が最小となる動きベクトルに対応する点をダイヤモンド探索の開始点に決定することを含む。
【００２４】
前記動き推定の実現方法は、第１閾値を決定することをさらに含み、
ステップB2において、前記ブロックマッチング値が所定の退出条件を満たすことは、ブロックマッチング値が決定された第１閾値より小さいことであり、
ステップB2において、前記退出条件を満たすブロックマッチング値は第１閾値より小さいブロックマッチング値である。
【００２５】
前記第１閾値を決定するステップは、現在のブロックモードに対する現在計算ブロックと、３つ方向以上の隣接点に対応するブロックとのブロックマッチング値に基づいて、第１閾値を決定することを含む。
【００２６】
ステップB2において、ブロックマッチング値が所定の退出条件を満たした後、且つ、退出条件を満たしたブロックマッチング値に対応する点を最適なマッチング点とする前に、
決定されたダイヤモンド半径が1であるかどうかを判断し、１であれば、前記退出条件を満たしたブロックマッチング値に対応する点を最適なマッチング点とするステップを続いて実行し、1でなければ、現在の最適なマッチング点を現在ダイヤモンド中心点とし、ダイヤモンド半径周囲の４つの点に対応するブロックのブロックマッチング値を計算し、ブロックマッチング値が最小となる点を最適なマッチング点とし、該最適なマッチング点に対応する動きベクトルを現在計算ブロックの動きベクトルとする
ことをさらに含む。
【００２７】
前記ブロックマッチング値は、前記計算ブロックと探索点に対応するブロックとの一対一の画素点の階調値の差の絶対値の和である。
【００２８】
前記現在マクロブロックのサイズが16×16画素である。
【００２９】
前記ブロックモードは、16×16画素、又は16×8画素、又は8×16画素、又は8×8画素、又は当該４者の任意の組合せである。
【発明の効果】
【００３０】
上記から分かるように、本発明において、複数のブロックモードを設定し、ブロックモードに基づいてマクロブロック全体を１つ以上の計算ブロックに分割し、各ブロックモードにおける現在マクロブロックのあらゆる計算ブロックと、それぞれの動きベクトルに対応するブロックとのマッチング値の和を計算し、マッチング値の和が最小となるブロックモードに対応する動きベクトルを取得すべきマクロブロックの動きベクトルとする。このように、従来技術における遍歴式の探索・計算方法を行うことなく、動き推定の計算量を大きく簡略化させ、ビデオデータ圧縮の速度を高めている。また、本発明は、探索のたびに、最小の計算ブロックの、探索点に対するブロックマッチング値をポイント・バイ・ポイントで計算し、最小の計算ブロックの動きベクトルとブロックマッチング値を記録しておき、比較的大きな計算ブロックの、動きベクトルに対するブロックマッチング値を計算するとき、記録済みの最小の計算ブロックのブロックマッチング値に対して簡単な加算をすればいい。こうして、重複計算によるシステムオーバーヘッドの増大と演算時間の増加を避けることができる。動き推定の正確性と精度を保証する前提で、動き推定におけるブロックマッチング値の計算時間をさらに節約し、ビデオデータ圧縮の圧縮速度をさらに高めていることにより、ビデオデータのリアルタイム性のニーズを満足し、ユーザの満足度を向上させている。
【発明を実施するための最良の形態】
【００３１】
本発明の目的、技術案及びメリットをより明確にするように、図面と具体的な実施形態を参照して本発明をさらに説明する。
【００３２】
本発明の中心的な考えとして、複数のブロックモードを設定し、ブロックモードごとにより、現在マクロブロックを計算ブロックにそれぞれ分割し、ブロックモードごとに対して、現在マクロブロックにおける全ての計算ブロックの動きベクトルをそれぞれ計算し、ブロックモードごとに対して、現在マクロブロックにおける全ての計算ブロックとそれぞれの動きベクトルに対応するブロックとのマッチング値の和をそれぞれ計算し、最小の和の値に対応するブロックモードを取得し、取得されたブロックモードに対応する動きベクトルを現在マクロブロックの動きベクトルとする。
【００３３】
ここで、ブロックモードごとに対して、現在マクロブロックにおける全ての計算ブロックの動きベクトルをそれぞれ計算するとき、下記の２つの実現方式を採用することができる。
【００３４】
方式１で、ブロックモードごとに対して、全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算する。
【００３５】
方式２で、最小の計算ブロックを含むブロックモードに対して、全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算し、他のブロックモードに対して、既に計算された各計算ブロックの動きベクトルの和を用いて前記他のブロックモードにおける全ての計算ブロックの動きベクトルを得る。
【００３６】
上記２つの方式において、前記ポイント・バイ・ポイントで計算する手順を行うには、ダイヤモンド探索モードを用いることができる。
【００３７】
好ましくは、本発明で、ブロックモードを、マクロブロック全体と、２つの横サブブロックと、２つの縦サブブロックと、４つのサブブロックとを含む４種類に設定することができる。
【００３８】
以下、上記方式１と方式２に対しそれぞれ１つの具体的な実施例を挙げて本発明の具体的な実現手順を説明する。
【００３９】
下記の実施例において、設定されたブロックモードは上記４種類のブロックモードであり、且つマクロブロックのサイズは16×16画素である。
【００４０】
[実施例１]
図1は本発明の実施例１のフローチャートである。図１を参照して、本発明の動き推定の実現手順は具体的に以下のステップを含む。
【００４１】
ステップ101において、４種類のブロックモードを設定し、ブロックモードごとにより、計算ブロックの分割を行う。
【００４２】
ここで、第１ブロックモード〜第４ブロックモードをそれぞれマクロブロック全体、２つの横サブブロック、２つの縦サブブロック及び４つのサブブロックに設定し、図3A〜図3Dを参照して、４種類のブロックモードごとにより分割された計算ブロックはそれぞれ以下のとおりである。
【００４３】
第１ブロックモードで、マクロブロックを１つの16×16画素サイズの計算ブロックに分割する。
【００４４】
第２ブロックモードで、マクロブロックを２つの16×8画素サイズの計算ブロックに分割する。
【００４５】
第３ブロックモードで、マクロブロックを２つの8×16画素サイズの計算ブロックに分割する。
【００４６】
第４ブロックモードで、マクロブロックを４つの8×8画素サイズの計算ブロックに分割する。
【００４７】
ステップ102において、変数iをi＝1のようにし、現在マクロブロックに対し第１ブロックモードを応用する。
【００４８】
ここで、変数iは現在のブロックモードを記録するように設定され、これにより、後続する手順で、該変数iの値に基づいて、使用されたブロックモードと使用されていないブロックモードを決定する。
【００４９】
ステップ103において、現在マクロブロックの動きベクトルの予測値を取得する。
【００５０】
ここで、現在マクロブロックの動きベクトルの予測値は、現在マクロブロックの左、正上及び右上の３つのマクロブロックの動きベクトルのメディアン値であり、即ち、予測値の水平成分（horizontal component）は３つの動きベクトルの水平成分の中央値であり、予測値の垂直成分（vertical component）は３つの動きベクトルの垂直成分の中央値である。現在フレームにおいて、現在マクロブロックの左、正上及び右上のブロックの動きベクトルをそれぞれW1、W2及びW3として記せば、現在マクロブロックの動きベクトルの予測値はMedian(W1,W2,W3)である。現在マクロブロックの左にマクロブロックがなければ、W1を(0,0)とし、現在マクロブロックの上にマクロブロックがなければ、W2を(0,0)とし、現在マクロブロックの右上にマクロブロックがなければ、W3を(0,0)とする。
【００５１】
また、現在マクロブロックの左、正上又は右上のマクロブロックのブロックモードが第１ブロックモードでなければ、現在マクロブロックに最隣接するブロックの動きベクトルを現在マクロブロックの動きベクトルの予測値として取得し、現在マクロブロックに最隣接するブロックが２つあれば、該現在マクロブロックに最隣接する２つのブロックの動きベクトルの平均値を現在マクロブロックの動きベクトルの予測値として取得し、即ち２つの動きベクトルの水平成分と２つの動きベクトルの垂直成分でそれぞれ平均値を取る。
【００５２】
ステップ104において、現在ブロックモードと隣接するマクロブロックとのブロックマッチング値であるSAD値に基づいて、動き推定の第１閾値と第２閾値を決定する。
【００５３】
ここで、前記動き推定の第１閾値と第２閾値を決定する具体的な実現手順は以下のステップを含む。
【００５４】
（１）計算ブロックの左上角の画素の横座標xと縦座標yを決定し、現在ブロックモードにおける計算ブロックの幅wを決定する。
【００５５】
（２）xは0であり、且つyは0である場合、
現在ブロックモードは第１ブロックモードであるとき、第１閾値は512であり、第２閾値は1024であり、
現在ブロックモードは第２、３ブロックモードであるとき、第１閾値は256であり、第２閾値は512であり、
現在ブロックモードは第４ブロックモードであるとき、第１閾値は128であり、第２閾値は256である。
【００５６】
xとyは同時に0ではない場合、
a、現在ブロックモードは第１ブロックモードであるとき、
該計算ブロックと点(x-2,y)、(x-1,y)、(x-2,y+1)及び(x-1,y+1)に対応する４つのブロックとのブロックマッチング値の和SAD1と、該計算ブロックと点(x,y-2)、(x+1,y-2)、(x,y-1)及び(x+1,y-1)に対応する４つのブロックとのブロックマッチング値SAD2と、該計算ブロックと点(x+w,y-2)、(x+w+1,y-2)、(x+w,y-1)及び(x+w+1,y-1)に対応する４つのブロックとのブロックマッチング値SAD3とを計算し、第１閾値をSAD1、SAD2及びSAD3の最小値にし、第２閾値を第１閾値と128との和にし、且つ、第１閾値が512より小さければ、第１閾値を512に設定し、第１閾値が1024より大きければ、第１閾値を1024に設定し、第２閾値が1792より大きければ、第２閾値を1792に設定する。
【００５７】
b、現在ブロックモードは第２ブロックモードであるとき、
該計算ブロックと点(x-2,y)と(x-1,y)に対応する２つのブロックとのブロックマッチング値の和SAD1と、該計算ブロックと点(x,y-1)と(x+1,y-1)に対応する２つのブロックとのブロックマッチング値の和SAD2と、該計算ブロックと点(x+w,y-1)と(x+w+1,y-1)に対応する２つのブロックとのブロックマッチング値の和SAD3とを計算し、第１閾値をSAD1、SAD2及びSAD3の最小値にし、第２閾値を第１閾値と128との和にし、且つ、第１閾値が256より小さければ、第１閾値を256に設定し、第１閾値が512より大きければ、第１閾値を512に設定し、第２閾値が896より大きければ、第２閾値を896に設定する。
【００５８】
c、現在ブロックモードは第３ブロックモードであるとき、
該計算ブロックと点(x-1,y)と(x-1,y+1)に対応する２つのブロックとのブロックマッチング値の和SAD1と、該計算ブロックと点(x,y-2)と(x,y-1)に対応する２つのブロックとのブロックマッチング値の和SAD2と、該計算ブロックと点(x+w,y-2)と(x+w,y-1)に対応する２つのブロックとのブロックマッチング値の和SAD3とを計算し、第１閾値をSAD1、SAD2及びSAD3の最小値にし、第２閾値を第１閾値と128との和にし、且つ、第１閾値が256より小さければ、第１閾値を256に設定し、第１閾値が512より大きければ、第１閾値を512に設定し、第２閾値が896より大きければ、第２閾値を896に設定する。
【００５９】
d、現在ブロックモードは第４ブロックモードであるとき、
該計算ブロックと点(x-1,y)に対応するブロックとのブロックマッチング値SAD1と、該計算ブロックと点(x,y-1)に対応するブロックとのブロックマッチング値SAD2と、該計算ブロックと点(x+w,y)に対応するブロックとのブロックマッチング値SAD3とを計算し、第１閾値をSAD1、SAD2及びSAD3の最小値にし、第２閾値を第１閾値と64との和にし、且つ、第１閾値が128より小さければ、第１閾値を128に設定し、第１閾値が256より大きければ、第１閾値を256に設定し、第２閾値が448より大きければ、第２閾値を448に設定する。
【００６０】
ステップ105において、ダイヤモンド探索モードの半径を決定する。
【００６１】
ここで、下記条件a〜cを同時に満足すれば、ダイヤモンド探索半径を１に決定し、下記条件a〜cを同時に満足しなければ、ダイヤモンド探索半径を2に決定する。
【００６２】
a、現在マクロブロックの左、上及び右上のマクロブロックの動きベクトルが同じである。
【００６３】
b、前フレームの現在位置のブロックの動きベクトルは0でない。
【００６４】
c、第２閾値がブロックの動き閾値より小さい。
【００６５】
また、説明すべきことは、本ステップにおいて、ブロックの動き閾値は現在計算ブロックの動き幅の大きさを判断するための値であり、本実施例で、ブロックの動き閾値は384に設定されていいが、本発明では他の適宜なブロックの動き閾値を除外しないことである。
【００６６】
ステップ106において、決定された半径に基づいて、ダイヤモンド探索法を用いて現在マクロブロックにおける全ての計算ブロックの動きベクトルを推定し、退出条件を満たす際に最適なマッチング点に対応する動きベクトルを対応の計算ブロックの動きベクトルとする。
【００６７】
ステップ107において、現在ブロックモードにおける現在マクロブロックのブロックマッチング値SADを計算し、即ち、現在マクロブロックにおける全ての計算ブロックと前フレームの最適なマッチング点に対応するブロックとのSAD値の和を計算する。
【００６８】
ここで、現在ブロックモードが第１ブロックモードであるとき、現在マクロブロックのSAD値は16×16画素の計算ブロックと最適なマッチング点に対応するブロックとのSAD値である。
【００６９】
現在ブロックモードが第２ブロックモードであるとき、現在マクロブロックのSAD値は２つの16×8画素の計算ブロックとそれぞれの最適なマッチング点に対応するブロックとのSAD値の和である。
【００７０】
現在ブロックモードが第３ブロックモードであるとき、現在マクロブロックのSAD値は２つの8×16画素の計算ブロックとそれぞれの最適なマッチング点に対応するブロックとのSAD値の和である。
【００７１】
現在ブロックモードが第４ブロックモードであるとき、現在マクロブロックのSAD値は４つの8×8画素の計算ブロックとそれぞれの最適なマッチング点に対応するブロックとのSAD値の和である。
【００７２】
ステップ108において、変数iの値が4より小さいかどうかを判断し、小さければ、ステップ109を実行し、小さくなければ、直接ステップ110を実行する。
【００７３】
ステップ109において、i＝i+1のように設定し、現在マクロブロックに対し第iブロックモードを応用し、ステップ104に戻る。
【００７４】
ステップ110において、４種類のブロックモードにおける現在マクロブロックのSAD値を比較し、そのうちの最小の現在マクロブロックSAD値即ち最小の和の値に対応するブロックモードを取得し、取得されたブロックモードに対応する動きベクトルを現在マクロブロックの動きベクトルに決定する。
【００７５】
ここで、第１ブロックモードにおける現在マクロブロックのSAD値が最小であれば、現在マクロブロックにおける１つの16×16画素サイズの計算ブロックは１つの動きベクトルがある。
【００７６】
第２ブロックモードにおける現在マクロブロックのSAD値が最小であれば、現在マクロブロックにおける２つの16×8画素サイズの計算ブロックは自分の動きベクトルがある。
【００７７】
第３ブロックモードにおける現在マクロブロックのSAD値が最小であれば、現在マクロブロックにおける２つの8×16画素サイズの計算ブロックは自分の動きベクトルがある。
【００７８】
第４ブロックモードにおける現在マクロブロックのSAD値が最小であれば、現在マクロブロックにおける４つの8×8画素サイズの計算ブロックは自分の動きベクトルがある。
【００７９】
上記図1に示したステップ106において、ダイヤモンド探索方法により計算ブロックの動きベクトルを推定し、即ち、現在計算ブロックと最もマッチングする点を見付ける手順は図2を参照してよく、具体的に以下のステップを含む。
【００８０】
ステップ201において、現在計算ブロックに対しダイヤモンド探索を行う探索起点を取得する。
【００８１】
ここで、現在フレームにおいて現在計算ブロックの左、正上及び右上のブロックの動きベクトルをそれぞれV1、V2及びV3として記す。前フレームで現在計算ブロックの位置と同じブロックを同一位置ブロックと称し、動きベクトル(0,0)を用いてその位置を説明し、同一位置ブロックの実際の動きベクトルをV4として記す。現在計算ブロックと、(0,0)、V1、V2、V3及びV4に対応するブロックとの間の画素値のSADをそれぞれ計算し、そのうちの最小のSADに対応する点を探索起点として選択する。説明すべきことは、本ステップで、現在計算ブロックの左には計算ブロックがなければ、V1を計算しなく、現在計算ブロックの正上には計算ブロックがなければ、V2を計算しなく、現在計算ブロックの右上には計算ブロックがなければ、V3を計算しなく、現在フレームが本グループの画像の第１フレームであれば、V4を計算しないことである。
【００８２】
本ステップで、SAD値が第１閾値より小さいことを満足すれば、ステップ202に進み、満足しなければ、ステップ203に進む。
【００８３】
ステップ202において、今回探索するダイヤモンド半径が1であるかどうかを判断し、１であれば、ステップ209に進み、1でなければ、ステップ206に進む。
【００８４】
ステップ203において、ステップ201で取得された探索起点をダイヤモンドの中心点とする。
【００８５】
ステップ204において、予め決定したダイヤモンド半径に基づいて、ダイヤモンド周囲の４つの点、即ちダイヤモンドの中心点の上、下、左、右の方向にダイヤモンドの中心点との距離がダイヤモンド半径となる４つの点を決定し、現在計算ブロックとこの４つの点に対応するブロックとのSAD値をそれぞれ計算する。
【００８６】
本ステップで、SAD値が第１閾値より小さいことを満足すれば、ステップ202に進み、満足しなければ、ステップ205に進む。
【００８７】
ステップ205において、ステップ204で決定された４つの点に対応するブロックのSAD値が最小となる点を次回のダイヤモンド探索の中心点として、ステップ203に戻り、引き続きダイヤモンド探索を行う。
【００８８】
ステップ206において、現在ダイヤモンドの半径を1にし、第１閾値より小さいSAD値に対応する点を探索の中心点とする。
【００８９】
ステップ207において、計算ブロックと周囲の４つの点に対応するブロックとのSAD値をそれぞれ計算する。
【００９０】
ステップ208において、計算された最小のSAD値に対応する点を最適なマッチング点とし、現在のプロセスを終了する。
【００９１】
ステップ209において、第１閾値より小さいSAD値に対応する点を最適なマッチング点とする。
【００９２】
[実施例２]
図3Aを参照して、第１ブロックモードにより分割された計算ブロックは実際１つのマクロブロックであり、図内のBlockは画像の１つのマクロブロックを表し、マクロブロックのサイズは16×16画素であり、該マクロブロックの左上角の座標は(x,y)であり、動きベクトル(u,v)の隣接領域で現在マクロブロックの動きベクトルを探索する。ここで、
−ｍ≦ｕ≦ｍ，−ｎ≦ｖ≦ｎ  である。
【００９３】
図4は本発明の実施例２のフローチャートである。図3A〜図3D及び図4を参照して、本発明の動き推定の実現手順は具体的に以下のステップを含む。
【００９４】
ステップ401において、４種類のブロックモードを設定し、ブロックモードごとにより、計算ブロックの分割を行う。
【００９５】
ここで、第１ブロックモード〜第４ブロックモードをそれぞれマクロブロック全体、２つの横サブブロック、２つの縦サブブロック及び４つのサブブロックに設定し、図3A〜図3Dを参照して、４種類のブロックモードにより分割された計算ブロックはそれぞれ以下のとおりである。
【００９６】
第１ブロックモードで、マクロブロックを１つの16×16画素サイズの計算ブロックに分割する。
【００９７】
第２ブロックモードで、マクロブロックを２つの16×8画素サイズの計算ブロックに分割する。
【００９８】
第３ブロックモードで、マクロブロックを２つの8×16画素サイズの計算ブロックに分割する。
【００９９】
第４ブロックモードで、マクロブロックを４つの8×8画素サイズの計算ブロックに分割する。
【０１００】
ステップ402において、16×16画素のブロックサイズに従って、動きベクトルが(u,v)となるブロックマッチング値を計算し、ここで、
−ｍ≦ｕ≦ｍ，−ｎ≦ｖ≦ｎ  であり、図3Dに示すように、４つのサブブロックの位置は以下の通りである。
【０１０１】
Aサブブロックは左上角の座標が(ｘ,ｙ)となる8×8画素のサブブロックである。
【０１０２】
Bサブブロックは左上角の座標が(ｘ+8,ｙ+8)となる8×8画素のサブブロックである。
【０１０３】
Cサブブロックは左上角の座標が(ｘ,ｙ+8)となる8×8画素のサブブロックである。
【０１０４】
Dサブブロックは左上角の座標が(ｘ+8,ｙ)となる8×8画素のサブブロックである。
【０１０５】
この隣接領域内の各動きベクトルに対して、４つの8×8画素のサブブロックのブロックマッチング値をそれぞれ記録する。
【０１０６】
動きベクトルが(u,v)となるAサブブロックのブロックマッチング値はSAD_A(u,v)である。
【０１０７】
動きベクトルが(u,v)となるBサブブロックのブロックマッチング値はSAD_B(u,v)である。
【０１０８】
動きベクトルが(u,v)となるCサブブロックのブロックマッチング値はSAD_C(u,v)である。
【０１０９】
動きベクトルが(u,v)となるDサブブロックのブロックマッチング値はSAD_D(u,v)である。
【０１１０】
ここで、説明すべきものとして、第４ブロックモードに含まれる計算ブロックは他のブロックモードに比べて最小であるので、先に該第４ブロックモードにおける全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算し、具体的な計算方法は図2に示したダイヤモンド探索モードにより実現されることができる。
【０１１１】
ステップ403において、前記隣接領域内の16×16画素サイズのブロックの最小のブロックマッチング値をSAD1に設定する。
【０１１２】
ステップ404において、16×8画素のブロックサイズに従って、動きベクトルが(u,v)となるブロックマッチング値を計算し、ここで、
−ｍ≦ｕ≦ｍ，−ｎ≦ｖ≦ｎ  であり、図2Dに示すように、マクロブロックの２つのサブブロックはそれぞれ以下の通りである。
【０１１３】
Eサブブロックは左上角の座標が(ｘ,ｙ)となる16×8画素サイズのサブブロックである。
【０１１４】
Fサブブロックは左上角の座標が(ｘ,ｙ+8)となる16×8画素サイズのサブブロックである。
【０１１５】
この隣接領域内の各動きベクトルに対して、動きベクトルが(u,v)となるEサブブロックのブロックマッチング値は、動きベクトルが(u,v)となるAサブブロックとBサブブロックのブロックマッチング値の和SAD_A(u,v)＋SAD_B(u,v)であり、動きベクトルが(u,v)となるFサブブロックのブロックマッチング値は、動きベクトルが(u,v)となるCサブブロックとDサブブロックのブロックマッチング値の和SAD_C(u,v)＋SAD_D(u,v)である。
【０１１６】
ステップ405において、この隣接領域内のEサブブロックの最小のブロックマッチング値をSAD21に、この隣接領域内のFサブブロックの最小のブロックマッチング値をSAD22に設定すれば、
SAD2＝SAD21＋SAD22となる。
【０１１７】
ステップ406において、8×16画素のブロックサイズに従って、動きベクトルが(u,v)となるブロックマッチング値を計算し、ここで、
−ｍ≦ｕ≦ｍ，−ｎ≦ｖ≦ｎ  であり、図1cに示すように、マクロブロックの２つのサブブロックはそれぞれ以下の通りである。
【０１１８】
Gサブブロックは左上角の座標が(ｘ,ｙ)となる8×16画素サイズのサブブロックである。
【０１１９】
Hサブブロックは左上角の座標が(ｘ+8,ｙ)となる8×16画素サイズのサブブロックである。
【０１２０】
この隣接領域内の各動きベクトルに対して、動きベクトルが(u,v)となるGサブブロックのブロックマッチング値は、動きベクトルが(u,v)となるAサブブロックとCサブブロックのブロックマッチング値の和SAD_A(u,v)＋SAD_C(u,v)であり、動きベクトルが(u,v)となるHサブブロックのブロックマッチング値は、動きベクトルが(u,v)となるBサブブロックとDサブブロックのブロックマッチング値の和SAD_B(u,v)＋SAD_D(u,v)である。
【０１２１】
ステップ407において、この隣接領域内のGサブブロックの最小のブロックマッチング値をSAD31に、この隣接領域内のHサブブロックの最小のブロックマッチング値をSAD32に設定すれば、
SAD3＝SAD31＋SAD32となる。
【０１２２】
ステップ408において、8×8画素のブロックサイズに従って、動きベクトルが(u,v)となるブロックマッチング値を計算し、ここで、
−ｍ≦ｕ≦ｍ，−ｎ≦ｖ≦ｎ  であり、マクロブロックの４つのサブブロックはそれぞれAサブブロック、Bサブブロック、Cサブブロック及びDサブブロックであり、ステップ201で前記４つのサブブロックの隣接領域内のあらゆる動きベクトルに対するブロックマッチング値を記録しているので、
動きベクトルが(u,v)となるAサブブロックのブロックマッチング値はSAD_A(u,v)であり、
動きベクトルが(u,v)となるBサブブロックのブロックマッチング値はSAD_B(u,v)であり、
動きベクトルが(u,v)となるCサブブロックのブロックマッチング値はSAD_C(u,v)であり、
動きベクトルが(u,v)となるDサブブロックのブロックマッチング値はSAD_D(u,v)である。
【０１２３】
ステップ409において、この隣接領域内のAサブブロックの最小のブロックマッチング値をSAD41に、Bサブブロックの最小のブロックマッチング値をSAD42に、Cサブブロックの最小のブロックマッチング値をSAD43に、Dサブブロックの最小のブロックマッチング値をSAD44に設定すれば、
SAD4＝SAD41＋SAD42＋SAD43＋SAD44となる。
【０１２４】
ステップ410において、SAD1、SAD2、SAD3及びSAD4のうちの最小値に対応するブロックモードを現在マクロブロックの動き推定のブロックモードとし、現在マクロブロックの動き推定のブロックモードに対応する動きベクトルを現在マクロブロックの動きベクトルとする。
【０１２５】
本実施例で、全域探索を例としているが、本発明は全域探索方法のみに限定されず、3段探索（three step search）やダイヤモンド探索などのいかなる探索方法にも適用されることが可能である。最小の計算ブロックの、各動きベクトルに対するブロックマッチング値を先に記録さえすれば、後続する探索ステップで前のブロックマッチング値のデータを用いることができ、必要なのは簡単な加算を行うことだけである。
【０１２６】
しかしながら、動き推定を行うとき、新しい探索点（動きベクトル）又は補間点に対するブロックマッチング値を計算しなければならないが、前の探索ステップでは相応のブロックマッチング値が記録されていない可能性がある。この場合、記録済みのブロックマッチング値の情報を用いることが不可能になり、該計算ブロックのブロックマッチング値を改めてポイント・バイ・ポイントで計算する必要がある。従って、毎回計算ブロックの、ある探索点に対するブロックマッチング値を計算する前に、以下のステップを追加するようにすればよい。記録には、該計算ブロックを構成するサブブロックの、該探索点に対するブロックマッチング値があるかどうかを判断し、あれば、該計算ブロックを構成するサブブロックのブロックマッチング値に対し加算して計算ブロックのブロックマッチング値を得、なければ、図2に示したダイヤモンド探索モードを用いて該計算ブロックの、該探索点に対する動きベクトルをポイント・バイ・ポイントで計算する。
【０１２７】
また、上記実施例において、先に16×16画素サイズのブロックモードから動き推定を行う。このブロックモードの探索範囲が通常比較的に広いため、他のブロックモードにおける計算ブロックのブロックマッチング値を計算するとき、記録されたブロックマッチング値をより多く用いることができる。しかし、本発明は先に8×8画素サイズのブロックモードから動き推定を行う実施形態も除外しない。
【０１２８】
本発明の上記各実施例では、設定された４種類のブロックモードはマクロブロック全体と、２つの横サブブロックと、２つの縦サブブロックと４つのサブブロックとを含む。本発明の他の実施例では、該４種類のブロックモードの任意の組合せが存在してもいい。例えば、２つの横サブブロックと２つの縦サブブロックである。又は、他の各ブロックモードが存在してもいい。それらにより本発明を具体的に実現する原理は上記実施例に係る手順の原理と同じである。
【０１２９】
要するに、上記記載されたのは、本発明の好ましい実施例にすぎず、本発明の保護範囲を限定するものではない。本発明の精神と原則内で行われる種々の修正、均等切替、改善などは全て本発明の保護範囲内に含まれるべきである。
【図面の簡単な説明】
【０１３０】
【図１】本発明の実施例１のフローチャートである。
【図２】本発明の実施例１で採用されるダイヤモンド探索モードのフローチャートである。
【図３Ａ】本発明の第１ブロックモードにより分割された計算ブロックを示す図である。
【図３Ｂ】本発明の第２ブロックモードにより分割された計算ブロックを示す図である。
【図３Ｃ】本発明の第３ブロックモードにより分割された計算ブロックを示す図である。
【図３Ｄ】本発明の第４ブロックモードにより分割された計算ブロックを示す図である。
【図４】本発明の実施例２のフローチャートである。
【符号の説明】
【０１３１】
１０１〜１１０  フローチャートのステップ
２０１〜２０９  フローチャートのステップ
４０１〜４１０  フローチャートのステップ
【図１】
2008515298.tif 000004
【図２】
2008515298.tif 000005
【図３Ａ】
2008515298.tif 000006
【図３Ｂ】
2008515298.tif 000007
【図３Ｃ】
2008515298.tif 000008
【図３Ｄ】
2008515298.tif 000009
【図４】
2008515298.tif 000010
【手続補正書】
【提出日】平成19年3月28日(2007.3.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
動き推定の実現方法であって、
複数のブロックモードを設定し、ブロックモードごとにより、現在マクロブロックを計算ブロックにそれぞれ分割するステップＡと、
ブロックモードごとに対して、現在マクロブロックにおける全ての計算ブロックの動きベクトルをそれぞれ計算するステップＢと、
ブロックモードごとに対して、現在マクロブロックにおける全ての計算ブロックと、それぞれの動きベクトルに対応するブロックとのマッチング値の和をそれぞれ計算し、最小の和の値に対応するブロックモードを取得し、取得されたブロックモードに対応する動きベクトルを現在マクロブロックの動きベクトルとするステップＣと、
を含むことを特徴とするこの方法。
【請求項２】
ステップＢにおいて、最小の計算ブロックを含むブロックモードに対して、現在マクロブロックにおける全ての計算ブロックの動きベクトルを計算するステップは、最小の計算ブロックを含むブロックモードに対して、現在マクロブロックにおける全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算することを含むことを特徴とする請求項１記載の方法。
【請求項３】
ステップＢにおいて、他のブロックモードに対し現在マクロブロックにおける全ての計算ブロックの動きベクトルを計算するステップは、他の各ブロックモードに対して、それぞれ現在マクロブロックにおける全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算することを含むことを特徴とする請求項２に記載の方法。
【請求項４】
ステップＢにおいて、他のブロックモードに対し現在マクロブロックにおける全ての計算ブロックの動きベクトルを計算するステップは、他の各ブロックモードに対して、それぞれ、既に計算された各計算ブロックの動きベクトルの和を用いて現在マクロブロックにおける全ての計算ブロックの動きベクトルを得ることを含むことを特徴とする請求項２に記載の方法。
【請求項５】
ステップＢにおいて、
前記他のブロックモードにおける計算ブロックを構成する最小の計算ブロックのブロックマッチング値が既に計算されたかどうかを判断し、既に計算されたら、前記した他のブロックモードに対して、それぞれ既に計算された各計算ブロックの動きベクトルの和を用いて現在マクロブロックにおける全ての計算ブロックの動きベクトルを得るステップを続いて実行し、計算されていなければ、それぞれ前記他のブロックモードにおける全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算する
ことをさらに含む特徴とする請求項４記載の方法。
【請求項６】
前記既に計算された各計算ブロックの動きベクトルの和を用いて他のブロックモードにおける全ての計算ブロックの動きベクトルを得るステップは、前記他のブロックモードにおける全ての計算ブロックの動きベクトルを得るまで、前記他のブロックモードにおける現在計算ブロックを構成する各最小の計算ブロックのブロックマッチング値の和を前記他のブロックモードにおける現在計算ブロックの動きベクトルとすることを繰り返して実行することを含むことを特徴とする請求項４又は請求項５記載の方法。
【請求項７】
ステップＢにおいて、前記全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算するステップは、
ダイヤモンド探索の開始点を決定し、決定された開始点を現在ダイヤモンド中心点とするステップＢ１と、
現在のブロックモードに対する現在計算ブロックに対して、それぞれ現在計算ブロックと、現在ダイヤモンド中心点周囲の４つの点に対応するブロックとのブロックマッチング値を計算し、ブロックマッチング値が最小となる点を現在ダイヤモンド中心点とし、該ブロックマッチング値が所定の退出条件を満たすまで、現在ダイヤモンド中心点周囲の４つの点に対応するブロックのブロックマッチング値を計算し、退出条件を満たすブロックマッチング値に対応する点を最適なマッチング点とし、最適なマッチング点に対応する動きベクトルを現在計算ブロックの動きベクトルに決定し、現在のブロックモードに対する全ての計算ブロックの動きベクトルが決定されるまで、このステップを繰り返すステップＢ２と、
を含むことを特徴とする請求項２、請求項３又は請求項５記載の方法。
【請求項８】
ステップＢ２の前に、現在マクロブロックの動きベクトルの予測値及び現在のブロックモードに対する計算ブロックの第２閾値を決定し、決定された動きベクトルの予測値と第２閾値に基づいて、ダイヤモンド半径を決定することをさらに含み、
ステップＢ２において、前記現在ダイヤモンド中心点周囲の４つの点は、現在ダイヤモンド中心点の上、下、左及び右方向の、現在ダイヤモンド中心点との距離がそれぞれ決定されたダイヤモンド半径となる４つの点を含む、
ことを特徴とする請求項７記載の方法。
【請求項９】
前記現在マクロブロックの動きベクトルの予測値を決定するステップは、現在マクロブロックの左、正上及び右上のマクロブロックの動きベクトルのメディアン値を取得し、取得されたメディアン値を現在マクロブロックの動きベクトルの予測値に決定することを含むことを特徴とする請求項８記載の方法。
【請求項１０】
前記ダイヤモンド半径を決定するステップは、決定された現在マクロブロックの動きベクトルの予測値と現在マクロブロックの左、正上及び右上のマクロブロックの何れか１つの動きベクトルとが同じであり、且つ、前フレームの画像の現在位置のブロックの動きベクトルが０ではなく、且つ、決定された第２閾値が所定のブロック動き閾値より小さいことを満たしたら、ダイヤモンド半径を１に決定し、満たさなければ、ダイヤモンド半径を２に決定することを含むことを特徴とする請求項８記載の方法。
【請求項１１】
前記第２閾値を決定するステップは、現在のブロックモードに対する現在計算ブロックと、３つ方向以上の隣接点に対応するブロックとのブロックマッチング値に基づいて、第２閾値を決定することを含むことを特徴とする請求項８記載の方法。
【請求項１２】
ステップＢ１において、前記ダイヤモンド探索の開始点を決定するステップは、前フレームの画像の同一位置の動きベクトルと、動きベクトル（０，０）と、現在マクロブロックの左、正上及び右上のマクロブロックの動きベクトルとに基づいて、前記現在計算ブロックのブロックマッチング値を計算し、ブロックマッチング値が最小となる動きベクトルに対応する点をダイヤモンド探索の開始点に決定することを含むことを特徴とする請求項７記載の方法。
【請求項１３】
第１閾値を決定することをさらに含み、
ステップＢ２において、前記ブロックマッチング値が所定の退出条件を満たすことは、ブロックマッチング値が決定された第１閾値より小さいことであり、
ステップＢ２において、前記退出条件を満たすブロックマッチング値は第１閾値より小さいブロックマッチング値である、
ことを特徴とする請求項７記載の方法。
【請求項１４】
前記第１閾値を決定するステップは、現在のブロックモードに対する現在計算ブロックと、３つ方向以上の隣接点に対応するブロックとのブロックマッチング値に基づいて、第１閾値を決定することを含むことを特徴とする請求項１３記載の方法。
【請求項１５】
ステップＢ２において、
決定されたダイヤモンド半径が１であるかどうかを判断し、１であれば、前記退出条件を満たしたブロックマッチング値に対応する点を最適なマッチング点とするステップを続いて実行し、１でなければ、現在の最適なマッチング点を現在ダイヤモンド中心点とし、ダイヤモンド半径周囲の４つの点に対応するブロックのブロックマッチング値を計算し、ブロックマッチング値が最小となる点を最適なマッチング点とし、該最適なマッチング点に対応する動きベクトルを現在計算ブロックの動きベクトルとする
ことをさらに含むことを特徴とする請求項１３又は請求項１４記載の方法。
【請求項１６】
前記ブロックマッチング値は、前記計算ブロックと探索点に対応するブロックとの一対一の画素点の階調値の差の絶対値の和であることを特徴とする請求項１記載の方法。
【請求項１７】
前記現在マクロブロックのサイズが１６×１６画素であることを特徴とする請求項１に記載の方法。
【請求項１８】
前記ブロックモードは、１６×１６画素、又は１６×８画素、又は８×１６画素、又は８×８画素、又は当該４者の任意の組合せであることを特徴とする請求項１７に記載の方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
ステップBにおいて、
前記他のブロックモードにおける計算ブロックを構成する最小の計算ブロックのブロックマッチング値が既に計算されたかどうかを判断し、既に計算されたら、前記した他のブロックモードに対して、既に計算された各計算ブロックの動きベクトルの和を用いて前記他のブロックモードにおける全ての計算ブロックの動きベクトルを得るステップを続いて実行し、計算されていなければ、それぞれ前記他のブロックモードにおける全ての計算ブロックの動きベクトルをポイント・バイ・ポイントで計算する
ことをさらに含む。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
ステップB2において、
決定されたダイヤモンド半径が1であるかどうかを判断し、１であれば、前記退出条件を満たしたブロックマッチング値に対応する点を最適なマッチング点とするステップを続いて実行し、1でなければ、現在の最適なマッチング点を現在ダイヤモンド中心点とし、ダイヤモンド半径周囲の４つの点に対応するブロックのブロックマッチング値を計算し、ブロックマッチング値が最小となる点を最適なマッチング点とし、該最適なマッチング点に対応する動きベクトルを現在計算ブロックの動きベクトルとする
ことをさらに含む。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００８７
【補正方法】変更
【補正の内容】
【００８７】
ステップ205において、ステップ204で決定された４つの点に対応するブロックのSAD値が最小となる点を次回のダイヤモンド探索の中心点として、ステップ204に戻り、引き続きダイヤモンド探索を行う。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０１０２
【補正方法】変更
【補正の内容】
【０１０２】
Bサブブロックは左上角の座標が(ｘ+8,ｙ)となる8×8画素のサブブロックである。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０１０４
【補正方法】変更
【補正の内容】
【０１０４】
Dサブブロックは左上角の座標が(ｘ+8,ｙ+8)となる8×8画素のサブブロックである。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１１２
【補正方法】変更
【補正の内容】
【０１１２】
ステップ404において、16×8画素のブロックサイズに従って、動きベクトルが(u,v)となるブロックマッチング値を計算し、ここで、
−ｍ≦ｕ≦ｍ，−ｎ≦ｖ≦ｎ  であり、図3Bに示すように、マクロブロックの２つのサブブロックはそれぞれ以下の通りである。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１１７
【補正方法】変更
【補正の内容】
【０１１７】
ステップ406において、8×16画素のブロックサイズに従って、動きベクトルが(u,v)となるブロックマッチング値を計算し、ここで、
−ｍ≦ｕ≦ｍ，−ｎ≦ｖ≦ｎ  であり、図3Cに示すように、マクロブロックの２つのサブブロックはそれぞれ以下の通りである。
【手続補正９】
【補正対象書類名】図面
【補正対象項目名】図１
【補正方法】変更
【補正の内容】
【図１】
2008515298.tif 000011
【手続補正１０】
【補正対象書類名】図面
【補正対象項目名】図２
【補正方法】変更
【補正の内容】
【図２】
2008515298.tif 000012
【国際調査報告】
2008515298.tif 000013
2008515298.tif 000014
2008515298.tif 000015
2008515298.tif 000016