JP4669517B2 - 動き推定の実現方法 - Google Patents

Description

本発明はビデオデータ圧縮技術に関し、特にビデオデータ圧縮における動き推定の実現方法に関する。

マルチメディアのアプリケーションにおいて、ビデオデータには実際有効な情報及び冗長データを含む。冗長データは無駄なデータとして、伝送不要であり、且つビデオデータに大量の冗長データがあるため、ビデオデータの冗長データに対して圧縮を行うと、ビデオデータのデータ量を大きく低減することができる。これにより、ビデオデータの記憶とリアルタイム処理を極めて便利にすることが可能となる。

ビデオデータにおいて、冗長データの数、即ち冗長度は構成方面で強い時間相関性が表れる。その原因として、通常、画像における大部分の領域での信号の変化が非常に遅く、特にバックグランド部分がほとんど変わらないため、隣接するフレーム間におけるビデオ信号には比較的強い相関性、即ちフレーム間の相関性が存在する。そのため、フレーム間の相関性を無くすことができれば、ビデオデータを極めて圧縮することができる。

従来、一般に、動き推定方法によりフレーム間の相関性を無くす。即ち、画像の現在フレームのデータに対して、前フレームでそれに最もマッチングする領域を探索し、前フレームのデータに対する現在フレームのデータの動きベクトルを計算し、該動きベクトルを符号化する。ここで、動き推定方法のキーポイントは動きベクトルの決定であることが分かる。

具体的に実現するとき、動き推定方法は通常、ブロックマッチング法により実現される。ブロックマッチング法において、各フレームの画像は２次元のN×N画素のサブブロックに分割される。一般に、Nは16である。各サブブロック内のあらゆる画素が同じ平行運動を行うと想定し、現在フレームのN×N画素のサブブロックに対応する前フレームのサブブロックの隣接領域ウインドーでそれに最もマッチングするサブブロックを探索し、現在サブブロックと前フレームのマッチングブロックとの２次元平面上の変位は動き推定によって得られた動きベクトルである。

ブロックマッチング法におけるマッチングサブブロック探索方法は一般に全域探索法（full search method）である。全域探索法では現在フレームの各マクロブロックに対して、前フレームの特定範囲（通常は隣接領域）で各点のブロックマッチング値を計算し、該隣接領域の各点がマッチング点である。次に、最小のマッチング値に対応するマッチング点を最適なマッチング点とし、最適なマッチング点に対応する動きベクトルを現在マクロブロックの動きベクトルとする。通常、ブロックマッチング値は、マクロブロックと探索範囲内のマッチング点に対応するブロックとの間の一対一の画素点の階調値の差の絶対値の和であり、即ち差分絶対値和（SAD）である。前記マッチング点に対応するブロックはマッチング点が左上角にあるの、マクロブロックのサイズと同じブロックである。ブロックマッチング値、即ちSADの計算公式は以下の通りである。

ここで、Ｉ_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値が最小となる点を次回のダイヤモンド探索の中心点として、ステップ204に戻り、引き続きダイヤモンド探索を行う。

ステップ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画素のサブブロックである。

Cサブブロックは左上角の座標が(ｘ,ｙ+8)となる8×8画素のサブブロックである。

Dサブブロックは左上角の座標が(ｘ+8,ｙ+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)となるブロックマッチング値を計算し、ここで、
−ｍ≦ｕ≦ｍ，−ｎ≦ｖ≦ｎ であり、図3Bに示すように、マクロブロックの２つのサブブロックはそれぞれ以下の通りである。

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)となるブロックマッチング値を計算し、ここで、
−ｍ≦ｕ≦ｍ，−ｎ≦ｖ≦ｎ であり、図3Cに示すように、マクロブロックの２つのサブブロックはそれぞれ以下の通りである。

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画素サイズのブロックモードから動き推定を行う実施形態も除外しない。

本発明の上記各実施例では、設定された４種類のブロックモードはマクロブロック全体と、２つの横サブブロックと、２つの縦サブブロックと４つのサブブロックとを含む。本発明の他の実施例では、該４種類のブロックモードの任意の組合せが存在してもいい。例えば、２つの横サブブロックと２つの縦サブブロックである。又は、他の各ブロックモードが存在してもいい。それらにより本発明を具体的に実現する原理は上記実施例に係る手順の原理と同じである。

要するに、上記記載されたのは、本発明の好ましい実施例にすぎず、本発明の保護範囲を限定するものではない。本発明の精神と原則内で行われる種々の修正、均等切替、改善などは全て本発明の保護範囲内に含まれるべきである。

本発明の実施例１のフローチャートである。 本発明の実施例１で採用されるダイヤモンド探索モードのフローチャートである。 本発明の第１ブロックモードにより分割された計算ブロックを示す図である。 本発明の第２ブロックモードにより分割された計算ブロックを示す図である。 本発明の第３ブロックモードにより分割された計算ブロックを示す図である。 本発明の第４ブロックモードにより分割された計算ブロックを示す図である。 本発明の実施例２のフローチャートである。

符号の説明

１０１〜１１０ フローチャートのステップ
２０１〜２０９ フローチャートのステップ
４０１〜４１０ フローチャートのステップ

Claims (10)

1. 動き推定の方法であって、
   複数のブロックモードを設定するとともに、各ブロックモードに基づいて、現在マクロブロックを計算ブロックにそれぞれ分割するステップを含み、
   前記ブロックモードは、前記計算ブロックのサイズを定義するためのものであり、
   前記方法は、
   前記各ブロックモードに対して、現在マクロブロックにおける各計算ブロックの動きベクトルをポイント・バイ・ポイントで計算するステップと、
   前記各ブロックモードに対して、現在マクロブロックにおける全ての計算ブロックと、
   現在マクロブロックにおける計算ブロックの各動きベクトルに対応する前フレームにおけるブロックとのマッチング値の和をそれぞれ計算し、マッチング値の最小の和の値に対応するブロックモードを取得するとともに、取得されたブロックモードに対応する動きベクトルを現在マクロブロックの動きベクトルとするステップと、
   を含み、
   １つのブロックモードに対して１つの計算ブロックの動きベクトルをポイント・バイ・ポイントで計算するプロセスは、
   ａ．前記１つのブロックモードにおける１つの計算ブロックに対して、ダイヤモンド探索の開始点を決定するとともに、決定された開始点をダイヤモンド探索の中心点とし、前記１つの計算ブロックと、ダイヤモンド探索の中心点周囲の４つの点に対応するブロックとの間のマッチング値をそれぞれ計算するステップと、
   ｂ．所定の退出条件を満たすマッチング値があるかどうかを決定するステップと
   を含み、
   前記所定の退出条件を満たすマッチング値がある場合、前記ダイヤモンド探索の半径が１であるかどうかをさらに確認し、ダイヤモンド探索の半径が１である場合、退出条件を満たすマッチング値に対応する点の動きベクトルを前記１つの計算ブロックの動きベクトルとし、ダイヤモンド探索の半径が１でない場合、ダイヤモンド探索の半径を１に設定し、退出条件を満たすマッチング値に対応する点をダイヤモンド探索の新しい中心点とし、前記１つの計算ブロックと、ダイヤモンド探索の新しい中心点周囲の４つの点に対応するブロックとの間のマッチング値を計算し、最小のマッチング値を有する点の動きベクトルを前記１つの計算ブロックの動きベクトルとし、
   前記所定の退出条件を満たすマッチング値がない場合、最小のマッチング値を有する点をダイヤモンド探索の新しい中心点とし、１つの計算ブロックと、ダイヤモンド探索の新しい中心点周囲の４つの点に対応するブロックとの間のマッチング値を計算し、前記所定の退出条件を満たすブロックマッチング値があるまで、最小のマッチング値を有する点をダイヤモンド探索の新しい中心点とし、前記１つの計算ブロックと、ダイヤモンド探索の新しい中心点周囲の４つの点に対応するブロックとの間のマッチング値を計算し、
   前記現在ダイヤモンド探索の中心点周囲の４つの点は、それぞれダイヤモンド探索の中心点の上、下、左及び右であるとともに、４つの点の各々とダイヤモンド探索の中心点との間の距離が、ダイヤモンド探索の半径である、４つの点を含むことを特徴とする方法。
2. 前記ダイヤモンド探索の半径が１であるかどうかを確認する場合、現在マクロブロックの動きベクトルの予測値と、前記１つのブロックモードにおける１つの計算ブロックの第２閾値とを決定するとともに、前記第２閾値に基づいてダイヤモンド探索の半径を決定することによって、前記ダイヤモンド探索の半径は決定されることを特徴とする請求項１記載の方法。
3. 前記現在マクロブロックの動きベクトルの予測値を決定するプロセスは、
   現在マクロブロックの左のマクロブロック、正上のマクロブロック、及び右上のマクロブロックの動きベクトルのメディアン値を取得するステップと、
   取得されたメディアン値を現在マクロブロックの動きベクトルの予測値として決定するステップと、
   を含むことを特徴とする請求項２記載の方法。
4. 前記ダイヤモンド探索の半径が１であるかどうかを確認する場合、現在マクロブロックの左、正上及び右上のマクロブロックの動きベクトルが同じであり、現在位置での前フレームの画像におけるマクロブロックの動きベクトルが０ではなく、前記１つの計算ブロックの決定された第２閾値が所定のブロック動き閾値より小さい場合、ダイヤモンド半径を１に設定し、そうでない場合、ダイヤモンド半径を２に決定することによって、前記ダイヤモンド半径は決定されることを特徴とする請求項２記載の方法。
5. 前記１つの計算ブロックの第２閾値を決定するプロセスは、前記１つの計算ブロックと、前記１つの計算ブロックの３方向以上の隣接点に対応する計算ブロックとの間のマッチング値に基づいて、前記１つの計算ブロックの第２閾値を決定するステップを含むことを特徴とする請求項２〜４のいずれか１項記載の方法。
6. 前記ダイヤモンド探索の開始点を決定するプロセスは、
   １つの計算ブロック、および以下の動きベクトル、すなわち同一位置での前フレームにおける動きベクトルと、動きベクトル（０，０）と、前記１つの計算ブロックのマクロブロックの左ブロックの動きベクトルと、前記１つの計算ブロックの正上ブロックの動きベクトルと、前記１つの計算ブロックの右上ブロックの動きベクトルとに対応する各ブロックの間のマッチング値を計算するステップと、
   前記最小のマッチング値に対応する動きベクトルを有する点をダイヤモンド探索の開始点とするステップと、
   を含むことを特徴とする請求項１記載の方法。
7. 第１閾値を決定するステップをさらに含み、
   前記所定の退出条件は、マッチング値が第１閾値より小さいことであるとともに、前記退出条件を満たすマッチング値が第１閾値より小さいマッチング値であることを特徴とする請求項１記載の方法。
8. 前記第１閾値を決定するプロセスは、前記１つの計算ブロックと、前記１つの計算ブロックの３方向以上の隣接点に対応するブロックとの間のマッチング値に基づいて、第１閾値を決定するステップを含むことを特徴とする請求項７記載の方法。
9. 前記現在マクロブロックのサイズが１６×１６画素であり、
   複数のブロックモードを設定するとともに、各ブロックモードに基づいて、現在マクロブロックを計算ブロックにそれぞれ分割するプロセスは、
   現在マクロブロックを１つの１６×１６計算ブロックに分割するステップ、および／または
   現在マクロブロックを２つの１６×８計算ブロックに分割するステップ、および／または
   現在マクロブロックを２つの８×１６計算ブロックに分割するステップ、および／または
   現在マクロブロックを４つの８×８計算ブロックに分割するステップ
   を含むことを特徴とする請求項１に記載の方法。
10. 動き推定の方法であって、
    複数のブロックモードを設定するとともに、各ブロックパターンに基づいて、現在マクロブロックを計算ブロックにそれぞれ分割するステップを含み、
    前記ブロックモードは、前記計算ブロックのサイズを定義するためのものであり、
    前記方法は、
    前記現在マクロブロックが最小の計算ブロックに分割されるブロックモードに対して、現在マクロブロックの全ての最小計算ブロックの動きベクトルをそれぞれ計算するステップを含み、
    １つのブロックモードにおいて、現在マクロブロックから分割された計算ブロックが、他のブロックモードにおいて、現在マクロブロックから分割された計算ブロックよりも大きくない場合、前記１つのブロックモードは、現在マクロブロックが最小の計算ブロックに分割されるブロックモードとされるとともに、前記１つのブロックモードにおいて現在マクロブロックから分割された計算ブロックは、最小の計算ブロックとされ、
    前記方法は、
    前記現在マクロブロックが最小の計算ブロックに分割されるブロックモードに対して、現在マクロブロックの全ての最小計算ブロックと、現在マクロブロックの最小計算ブロックの各動きベクトルに対応する前フレームにおけるブロックとの間のマッチング値をそれぞれ計算するステップと、
    前記現在マクロブロックが最小の計算ブロックに分割されるブロックモードを除く、各ブロックモードに対して、現在マクロブロックにおける全ての計算ブロックの動きベクトルをそれぞれ計算するとともに、現在マクロブロックの全ての計算ブロックと、現在マクロブロックの計算ブロックの各動きベクトルに対応する前フレームにおけるブロックとの間のマッチング値をそれぞれ計算するステップと
    を含み、
    現在マクロブロックの１つの計算ブロックと、前記１つの計算ブロックの１つの動きベクトルに対応する前フレームにおけるブロックとの間のマッチング値を計算する際に、前記１つの計算ブロックを構成する最小の計算ブロックと、前記１つの計算ブロックを構成する最小の計算ブロックの１つの動きベクトルに対応する前フレームにおけるブロックとの間のマッチング値の和を、前記１つの計算ブロックと、前記１つの計算ブロックの１つの動きベクトルに対応する前フレームにおけるブロックとの間のマッチング値とし、
    前記方法は、
    各ブロックモードに対して、現在マクロブロックの全ての計算ブロックと、現在マクロブロックの計算ブロックの各動きベクトルに対応する前フレームにおけるブロックとの間のマッチング値の和をそれぞれ計算するステップと、
    マッチング値の最小の和を有するブロックモードを取得するとともに、取得されたブロックモードに対応する動きベクトルを、現在マクロブロックの動きベクトルとするステップと、
    を含み、
    １つのブロックモードに対して１つの計算ブロックの動きベクトルをポイント・バイ・ポイントで計算するプロセスは、
    ａ．前記１つのブロックモードにおける１つの計算ブロックに対して、ダイヤモンド探索の開始点を決定するとともに、決定された開始点をダイヤモンド探索の中心点とし、前記１つの計算ブロックと、ダイヤモンド探索の中心点周囲の４つの点に対応するブロックとの間のマッチング値をそれぞれ計算するステップと、
    ｂ．所定の退出条件を満たすマッチング値があるかどうかを決定するステップと
    を含み、
    前記所定の退出条件を満たすマッチング値がある場合、前記ダイヤモンド探索の半径が１であるかどうかをさらに確認し、ダイヤモンド探索の半径が１である場合、退出条件を満たすマッチング値に対応する点の動きベクトルを前記１つの計算ブロックの動きベクトルとし、ダイヤモンド探索の半径が１でない場合、ダイヤモンド探索の半径を１に設定し、退出条件を満たすマッチング値に対応する点をダイヤモンド探索の新しい中心点とし、前記１つの計算ブロックと、ダイヤモンド探索の新しい中心点周囲の４つの点に対応するブロックとの間のマッチング値を計算し、最小のマッチング値を有する点の動きベクトルを前記１つの計算ブロックの動きベクトルとし、
    前記所定の退出条件を満たすマッチング値がない場合、最小のマッチング値を有する点をダイヤモンド探索の新しい中心点とし、１つの計算ブロックと、ダイヤモンド探索の新しい中心点周囲の４つの点に対応するブロックとの間のマッチング値を計算し、前記所定の退出条件を満たすブロックマッチング値があるまで、最小のマッチング値を有する点をダイヤモンド探索の新しい中心点とし、前記１つの計算ブロックと、ダイヤモンド探索の新しい中心点周囲の４つの点に対応するブロックとの間のマッチング値を計算し、
    前記現在ダイヤモンド探索の中心点周囲の４つの点は、それぞれダイヤモンド探索の中心点の上、下、左及び右であるとともに、４つの点の各々とダイヤモンド探索の中心点との間の距離が、ダイヤモンド探索の半径である、４つの点を含むことを特徴とする方法。

Images