(57)【特許請求の範囲】
【請求項１】
動きベクトル探索可能回数を１フレーム内の動きベクトル探索の処理単位ごとに設定し、
前記動きベクトル探索可能回数に基づいて前記１フレームに割り当てられた動きベクトル探索可能回数から現在の動きベクトル探索の対象である現処理単位の前処理単位までに要した動きベクトル探索回数を減じた値を前記１フレーム内で動きベクトル探索が行われていない残りの処理単位数で割った値を前記現処理単位の前記動きベクトル探索可能回数に設定し、
設定された複数の動きベクトル探索終了条件の内の少なくとも一の動きベクトル探索終了条件が満たされるときに動きベクトル探索を終了すること
を特徴とする追跡型動きベクトル探索方法。
【請求項２】
前記複数の動きベクトル探索終了条件は、
現処理単位内の画素のデータと参照画素のデータとの差分絶対値の総和の変化量が所定の回数、連続して一定値以下になることを含むこと
を特徴とする請求項１に記載の追跡型動きベクトル探索方法。
【請求項３】
前記複数の動きベクトル探索終了条件は、
現処理単位内の画素のデータと参照画素のデータとの差分絶対値の総和が一定値以下になることを含むこと
を特徴とする請求項１に記載の追跡型動きベクトル探索方法。
【請求項４】
１フレームに割り当てられた動きベクトル探索可能回数から現在の動きベクトル探索の対象である動きベクトル探索の現処理単位の前処理単位までに要した動きベクトル探索回数を減じた値を前記１フレーム内で動きベクトル探索が行われていない残りの処理単位数で割った値を前記現処理単位の前記動きベクトル探索可能回数に設定する手段と、
複数の動きベクトル探索終了条件を設定する手段と、
前記複数の動きベクトル探索終了条件の内の少なくとも一の動きベクトル探索終了条件が満たされるか否かを判定し、動きベクトル探索終了信号を出力する手段と
を有することを特徴とする追跡型動きベクトル探索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＭＰＥＧ４（Moving Picture Experts Group 4）エンコーダ等、動き補償を行う動画像エンコーダに使用して好適な追跡型動きベクトル探索方法及び装置に関する。
【０００２】
【従来の技術】
たとえば、ＭＰＥＧ４エンコーダにおいては、動きベクトルを用いた動き補償予測符号化処理が行われるが、動きベクトル探索方法の一例として、たとえば、フルサーチ（Full Search）法と呼ばれる方法が知られている。
【０００３】
フルサーチ法は、動きベクトル探索範囲の全探索点で、現フレームの輝度信号のマクロブロックの各画素のデータと参照フレームの参照ブロックの各画素のデータとの差分絶対値の総和（以下、単に「ＳＡＤ」という場合もある）を算出し、ＳＡＤが一番小さい参照ブロックを現フレームの輝度信号のマクロブロックと最もマッチングの良い参照ブロックとし、動きベクトルを算出するというものである。
【０００４】
たとえば、図１２に示すように、動きベクトル探索範囲が１５×１５画素である場合、フルサーチ法では、動きベクトル探索範囲の２２５個の全画素を探索点とし、これら２２５個の探索点の各々についてＳＡＤを算出し、ＳＡＤが一番小さい参照ブロックを現フレームの輝度信号のマクロブロックと最もマッチングの良い参照ブロックとし、動きベクトルを算出することになる。
【０００５】
このように、フルサーチ法は、動きベクトル探索範囲の全画素を探索点としてブロックマッチングを行う方法であり、局部最小に陥らないため、探索精度が高く、画質の向上を図ることができるという利点を有している。しかし、動きベクトル探索範囲の全画素を探索点としているため、探索回数は、たとえば、動きベクトル探索範囲が１５×１５画素である場合には２２５回、動きベクトル探索範囲が３１×３１画素である場合には９６１回となってしまう。
【０００６】
このため、フルサーチ法は、演算量が非常に大きく、リアルタイムシステムに適用することが実際には難しいという問題点を有している。そこで、演算量を削減した動きベクトル探索方法として、ＴＳＳ（Three Step Search）法と呼ばれる方法や、ＮＴＳＳ（New Three Step Search）法と呼ばれる方法や、サンプリング法と呼ばれる方法が提案されている。
【０００７】
ＴＳＳ法は、３回のステップで動きベクトルの探索を行う方法である。たとえば、図１３に示すように、動きベクトル探索範囲が１５×１５画素である場合、ＴＳＳ法では、まず、中心画素（０、０）と、その周辺の８個の画素、たとえば、画素（−４、−４）、（０、−４）、（４、−４）、（−４、０）、（４、０）、（−４、４）、（０、４）、（４、４）との合計９個の画素を１回目のステップでの探索点として、各探索点についてＳＡＤが算出される。
【０００８】
ここで、たとえば、探索点（−４、−４）のＳＡＤが一番小さい場合には、探索点（−４、−４）の周辺の８個の画素、たとえば、画素（−６、−６）、（−４、−６）、（−２、−６）、（−６、−４）、（−２、−４）、（−６、−２）、（−４、−２）、（−２、−２）を２回目のステップでの探索点として、各探索点についてＳＡＤが算出される。
【０００９】
ここで、たとえば、探索点（−２、−６）のＳＡＤが一番小さい場合には、探索点（−２、−６）の周辺の８個の画素、たとえば、画素（−３、−７）、（−２、−７）、（−１、−７）、（−３、−６）、（−１、−６）、（−３、−５）、（−２、−５）、（−１、−５）を３回目のステップでの探索点として、各探索点についてＳＡＤが算出され、たとえば、探索点（−２、−７）のＳＡＤが一番小さい場合には、座標（−２、−７）が動きベクトルとされる。
【００１０】
ＮＴＳＳ法は、ＮＳＳ法と同様に３回のステップで動きベクトルの探索を行う方法である。ＮＳＳ法と異なる点は、たとえば、図１４に示すように、１回目のステップでの探索点として、ＴＳＳ法の場合に設定される９個の探索点のほかに、中心座標（０、０）に隣接する８個の画素（−１、−１）、（０、−１）、（１、−１）、（−１、０）、（１、０）、（−１、１）、（０、１）、（１、１）を探索点として設定するという点である。
【００１１】
サンプリング法は、所定のパターンをなす一定の画素を探索点とするものであり、たとえば、図１５に示すように、動きベクトル探索範囲が１５×１５画素である場合、４×４個の画素、たとえば、画素（−７、−７）、（−３、−７）、（１、−７）、（５、−７）、（−７、−３）、（−３、−３）、（１、−３）、（５、−３）、（−７、１）、（−３、１）、（１、１）、（５、１）、（−７、５）、（−３、５）、（１、５）、（５、５）を探索点として、各探索点についてＳＡＤを算出し、ＳＡＤが一番小さい探索点の座標を動きベクトルとするものである。
【００１２】
ＴＳＳ法、ＮＴＳＳ法及びサンプリング法は、一定の探索範囲で、決まった探索パターンを用いるため、動きベクトル探索回数が一定となる。動きベクトル探索回数は、たとえば、動き探索範囲が１５×１５画素である場合、ＴＳＳ法では２５回、ＮＴＳＳ法では３３回、４×４サンプリング法では１６回であり、動きベクトル探索範囲が３１×３１画素である場合、ＴＳＳ法では３３回、ＮＴＳＳ法では４１回、８×８サンプリング法では６４回である。
【００１３】
フルサーチ法、ＴＳＳ法、ＮＴＳＳ法及びサンプリング法は、動きベクトル探索回数を固定とするものであるが、動きベクトル探索回数を不定とする動きベクトル探索方法も提案されている。一般に、追跡型動きベクトル探索方法と呼ばれるものであり、ＢＢＧＤＳ（Block-Based Gradient Descent Search）法やＤＳ（Diamond Search）法などがこれに含まれる。
【００１４】
追跡型動きベクトル探索方法は、探索原点（参照フレームの現フレームの輝度信号のマクロブロックと同じ位置）から所定の探索パターンに従って各探索点のＳＡＤを計算し、探索パターン中心の探索点のＳＡＤが一番小さくなるまで、次の探索パターン中心をＳＡＤが一番小さい探索点に移動させることにより、動きベクトルを算出するというものである。
【００１５】
図１６は追跡型動きベクトル探索方法の一例を説明するための図である。この例では、まず、画素（０、０）を探索原点とし、４個の画素（０、−１）、（−１、０）、（１、０）、（０、１）を探索点として４点探索が行われる。すなわち、これら４個の探索点（０、−１）、（−１、０）、（１、０）、（０、１）のＳＡＤが計算され、ＳＡＤが一番小さい探索点に探索パターン中心が移動される。ここで、たとえば、探索点（１、０）の探索点のＳＡＤが一番小さい場合、探索パターン中心が探索点（１、０）に移動される。
【００１６】
次に、３個の画素（１、−１）、（２、０）、（１、１）を探索点として３点探索が行われる。すなわち、これら３個の探索点（１、−１）、（２、０）、（１、１）のＳＡＤが計算され、探索点（１、０）の探索点のＳＡＤが一番小さい場合には探索が終了され、座標（１、０）が動きベクトルとされる。これに対して、探索点（１、−１）、（２、０）、（１、１）の中にＳＡＤの一番小さいものがある場合には、その探索点に探索パターン中心が移動され、３点探索が行われる。
【００１７】
ここで、たとえば、探索点（２、０）のＳＡＤが一番小さい場合、探索パターン中心が探索点（２、０）に移動され、３個の座標（２、−１）、（３、０）、（２、１）を探索点として３点探索が行われる。すなわち、これら探索点（２、−１）、（３、０）、（２、１）のＳＡＤが計算され、探索点（２、０）のＳＡＤが一番小さい場合には探索が終了され、座標（２、０）が動きベクトルとされる。これに対して、探索点（２、−１）、（３、０）、（２、１）の中にＳＡＤの一番小さいものがある場合には、その探索点に探索パターン中心が移動され、３点探索が行われる。
【００１８】
ここで、たとえば、探索点（３、０）のＳＡＤが一番小さい場合、探索パターン中心が探索点（４、０）に移動され、３点探索が行われ、以下、探索パターン中心のＳＡＤが一番小さくなるまで、同様の動作が繰り返される。
【００１９】
【発明が解決しようとする課題】
フルサーチ法、ＴＳＳ法、ＮＴＳＳ法及びサンプリング法は、動きが少ない場合であっても、予め決めた探索回数で動きベクトルを求めるため、無駄な計算を行う場合があるという問題点を有している。
【００２０】
これに対して、追跡型動きベクトル探索方法は、探索パターン中心の探索点のＳＡＤが一番小さくなるまで、動きベクトルの探索を続けるため、画像によっては、動きベクトルを早く検出することができる。しかし、画像によっては、時間が掛かることもあり、このような場合には、動きベクトルの探索を続けても、探索精度は上がりにくく、探索効率が悪くなる。
【００２１】
本発明は、かかる点に鑑み、動きベクトル探索の効率化を図ることができるようにした追跡型動きベクトル探索方法及び装置を提供することを目的とする。
【００２２】
【課題を解決するための手段】
本発明の追跡型動きベクトル探索方法は、動きベクトル探索可能回数を処理単位（たとえば、ＭＰＥＧエンコーダにおいては、輝度信号のマクロブロック）ごとに設定するというものである。
【００２３】
本発明の追跡型動きベクトル探索方法によれば、動きベクトル探索可能回数を処理単位ごとに設定するとしているので、無駄な動きベクトル探索を防ぐことができる。
【００２４】
本発明の追跡型動きベクトル探索装置は、動きベクトル探索可能回数を処理単位（たとえば、ＭＰＥＧエンコーダにおいては、輝度信号のマクロブロック）ごとに設定する手段を有するというものである。
【００２５】
本発明の追跡型動きベクトル探索装置によれば、動きベクトル探索可能回数を処理単位ごとに設定することができるので、無駄な動きベクトル探索を防ぐことができる。
【００２６】
【発明の実施の形態】
図１は本発明の追跡型動きベクトル探索装置の一実施形態の一部分を示す回路図である。本発明の追跡型動きベクトル探索装置の一実施形態は、ＭＰＥＧエンコーダの一部分を構成するものであり、本発明の追跡型動きベクトル探索方法の一実施形態を実行することができるものである。
【００２７】
図１中、１はエンコードする前の元画像データを入力してＭＰＥＧエンコーダ内の各部を制御するエンコーダ制御部、２はエンコーダ制御部１を介して供給される元画像データからＳＡＤの計算に必要な探索データを生成する探索データ生成部である。
【００２８】
３は探索データ生成部２からＳＡＤ計算スタート信号と現フレームの輝度信号のマクロブロックの画素のデータと参照フレームの輝度信号のマクロブロックの画素のデータが供給され、後述する探索順番制御部から順番に指示される探索点のＳＡＤを計算するＳＡＤ演算部である。
【００２９】
４は動きベクトル探索を制御する探索制御部であり、５はＳＡＤを計算する探索点の順番を制御する探索順番制御部であり、探索順番制御部５は、たとえば、図１６を使用して説明した方法と同様の方法で追跡型動きベクトル探索を行うことができるように探索順番制御を行う。
【００３０】
６はＳＡＤ演算部３から供給されるＳＡＤに基づいて動きベクトルを計算する動きベクトル計算部、７は動きベクトル探索を終了するか否かを判断し、動きベクトル探索を終了する場合には、動きベクトル探索終了信号を出力する探索終了判断部である。
【００３１】
図２は探索終了判断部７の構成を示す回路図である。図２中、８は探索データ生成部２から供給されるＳＡＤ計算スタート信号を起動信号として動きベクトル探索回数をカウントする探索回数カウンタ、９は動きベクトル探索終了信号をリセット信号として探索回数カウンタ８の出力値を記憶するレジスタである。本例では、１個の探索点のＳＡＤの計算を１回の動きベクトル探索回数とする。
【００３２】
１０は１フレームに割り当てられている動きベクトル探索可能回数とレジスタ９に記憶されている現マクロブロック（現に動きベクトル探索の対象とされているマクロブロック）の現動きベクトル探索回数を入力して、現マクロブロックの残りの動きベクトル探索可能回数を計算する残り探索可能回数計算ブロックである。なお、残り探索可能回数計算ブロック１０から出力される残りの動きベクトル探索可能回数の初期値は、現マクロブロックに割り当てられた探索可能回数である。
【００３３】
１１は条件１チェックブロックであり、条件１チェックブロック１１は、ＳＡＤ演算部３から供給される各探索点のＳＡＤと、探索回数カウンタ８から出力される現動きベクトル探索回数とを入力し、探索パターン中心の探索点のＳＡＤが一番小さくなっているか否かをチェックし、探索パターン中心の探索点のＳＡＤが一番小さくなっていると判定した時は、その出力Ｃ１を論理「1」とするものである。すなわち、条件１チェックブロック１１は、従来通常に採用されている動きベクトル探索終了条件を条件１とし、これを満たしているか否かをチェックするブロックである。
【００３４】
１２は条件２チェックブロックであり、条件２チェックブロック１２は、ＳＡＤ演算部３から供給される各探索点のＳＡＤと、閾値ＴＨＲ１、Ｎとを入力し、前回（［ｉ−１］回目）の動きベクトル探索でＳＡＤが最小であった探索点のＳＡＤ：minＳＡＤ［ｉ−１］と今回（［ｉ］回目）の動きベクトル探索でＳＡＤが最小であった探索点のＳＡＤ：minＳＡＤ［ｉ］の差分絶対値｜minＳＡＤ［ｉ］−minＳＡＤ［ｉ−１］｜がＮ回続いて閾値ＴＨＲ１より小さいことを条件２として、条件２を満たしているか否かをチェックし、これを満たしていると判定した時は、その出力Ｃ２を論理「１」とするものである。
【００３５】
１３は残り探索可能回数計算ブロック１０から出力される残りの動きベクトル探索可能回数を入力して条件２チェックブロック１２に対して、閾値ＴＨＲ１として所定の値Thr1_1、Thr1_2、Thr1_3（Thr1_1＜Thr1_2＜Thr1_3）を選択的に供給するセレクタ、１４は残り探索可能回数計算ブロック１０から出力される残りの動きベクトル探索可能回数を入力して条件２チェックブロック１２に対して、閾値ＮとしてＮ１、Ｎ２、Ｎ３（Ｎ１＞Ｎ２＞Ｎ３）を選択的に供給するセレクタである。
【００３６】
１５は条件３チェックブロックであり、条件３チェックブロック１５は、ＳＡＤ演算部３から供給される各探索点のＳＡＤと、閾値ＴＨＲ２とを入力し、今回（［ｉ］回目）の動きベクトル探索でＳＡＤが最小であった探索点のＳＡＤ：minＳＡＤ［ｉ］が閾値ＴＨＲ２より小さいことを条件３として、条件３を満たしているか否かをチェックし、これを満たしていると判定した時は、その出力Ｃ３を論理「１」とするものである。
【００３７】
１６は残り探索可能回数計算ブロック１０から出力される残りの動きベクトル探索可能回数を入力し、条件３チェックブロック１５に対して、閾値ＴＨＲ２として、所定の値Thr2_1、Thr2_2、Thr2_3（Thr2_1＜Thr2_2＜Thr2_3）を選択的に供給するセレクタである。
【００３８】
１７は条件４チェックブロックであり、条件４チェックブロック１７は、探索回数カウンタ８から供給される現動きベクトル探索回数ＣＮＴpresent_mbと、残り探索可能回数計算ブロック１０から供給される残りの動きベクトル探索可能回数の初期値、すなわち、現マクロブロックに割り当てられた動きベクトル探索可能回数ＣＮＴrest_aveを入力して、現動きベクトル探索回数ＣＮＴpresent_mbが割り当てられた動きベクトル探索可能回数ＣＮＴrest_aveを超えること（ＣＮＴpresent_mb＞ＣＮＴrest_ave）を条件４として、条件４を満たしているか否かをチェックし、これを満たしていると判定した時は、その出力Ｃ４を論理「１」とするものである。
【００３９】
ここに、現マクロブロックに割り当てられる動きベクトル探索可能回数ＣＮＴrest_aveは、数１で求めることができる。
【００４０】
【数１】
0004923368.tif 000002
【００４１】
但し、ＣＮＴframeは各フレームに割り当てられている動きベクトル探索可能回数、ＣＮＴpassedは前マクロブロックまでの動きベクトル探索回数の総和であり、数２で求められる。また、ＦＲＡＭＥ＿ＭＢ＿ＮＵＭは１フレーム内のマクロブロックの数、ＰＡＳＳＥＤ＿ＭＢ＿ＮＵＭは動きベクトル探索が終了したマクロブロックの数である。数１に示すように動きベクトル探索可能回数をマクロブロックごとに設定することが、本発明の追跡型動きベクトル探索方法の一実施形態である。
【００４２】
【数２】
0004923368.tif 000003
【００４３】
１８は条件１チェックブロック１１の出力Ｃ１と条件２チェックブロック１２の出力Ｃ２と条件３チェックブロック１５の出力Ｃ３と条件４チェックブロック１７の出力Ｃ４を入力し、これら出力Ｃ１、Ｃ２、Ｃ３、Ｃ４のいずれかが論理「１」となった時に、論理「１」からなる動きベクトル探索終了信号を出力するＯＲ回路である。
【００４４】
閾値ＴＨＲ１、Ｎ、ＴＨＲ２は、ＣＮＴpresent_mbとＣＮＴrest_aveとの差ΔＣＮＴ、すなわち、現マクロブロックの残りの動きベクトル探索可能回数ΔＣＮＴで決められるが、たとえば、表１に示すように、すなわち、ΔＣＮＴが大きければ、探索終了条件を厳しくし、ΔＣＮＴが小さくなるに従い、探索終了条件を緩めることで、マクロブロックごとに動きベクトル探索回数の上限を変化させることが、無駄な動きベクトル探索を防ぐ上で好適である。
【００４５】
【表１】
0004923368.tif 000004
【００４６】
本発明の追跡型動きベクトル探索装置の一実施形態は、たとえば、図１６に示すと同様に、４点探索に続いて３点探索を続け、動きベクトルを求めるものであるが、条件１チェックブロック１１の出力Ｃ１、条件２チェックブロック１２の出力Ｃ２、条件３チェックブロック１５の出力Ｃ３又は条件４チェックブロック１７の出力Ｃ４のいずれかが論理「１」になると、すなわち、条件１、条件２、条件３又は条件４のいずれかが満たされると、論理「１」からなる動きベクトル探索終了信号が出力され、現マクロブロックについての動きベクトル探索が終了となる。
【００４７】
ここで、たとえば、現マクロブロックについて、図３に示すように、Thr1_1＝５、Thr1_2＝１０、Thr1_3＝２０、Ｎ１＝４、Ｎ２＝３、Ｎ３＝２、Thr2_1＝３２、Thr2_2＝６４、Thr2_3＝１２８とし、図４に示すように、割り当てる動きベクトル探索可能回数を４０回、探索原点を（３、０）とし、動きベクトル探索回数が１〜１３回の間は、ＴＨＲ１＝Thr1_1＝５、Ｎ＝Ｎ１＝４、ＴＨＲ２＝Thr2_1＝３２、動きベクトル探索回数が１４〜２２回の間は、ＴＨＲ１＝Thr1_2＝１０、Ｎ＝Ｎ２＝３、ＴＨＲ２＝Thr2_1＝３２、動きベクトル探索回数が２３〜３１回の間は、ＴＨＲ１＝Thr1_3＝２０、Ｎ＝Ｎ３＝２、ＴＨＲ２＝Thr2_1＝３２とし（動きベクトル探索回数が３２回以降のＴＨＲ１、Ｎ、ＴＨＲ２は表示を省略している）、動きベクトルの探索を行うと、たとえば、図５に示すような動きベクトル探索結果を得ることができる。図５において、「４ｐ」は４点探索、「３ｐ」は３点探索、「ｍｖ」は動きベクトルを示している（以下、同様である）。また、図６は探索パターン中心の移動の様子を示している。
【００４８】
ここで、条件２チェックブロック１２を設けない場合には、動きベクトル探索回数が３１回では動きベクトル探索は終了せず、更に続いて動きベクトル探索を行うことになり、この場合、たとえば、図７に示すように、前回（［ｉ−１］回目）の動きベクトル探索でＳＡＤが最小であった探索点のＳＡＤ：minＳＡＤ［ｉ−１］と今回（［ｉ］回目）の動きベクトル探索でＳＡＤが最小であった探索点のＳＡＤ：minＳＡＤ［ｉ］の差分絶対値｜minＳＡＤ［ｉ］−minＳＡＤ［ｉ−１］｜の変化が小さく、これ以上、動きベクトル探索の必要がないにも関わらず、無駄な動きベクトル探索を行ってしまう場合が発生してしまう。
【００４９】
また、たとえば、現マクロブロックについて、図３に示すように、Thr1_1＝５、Thr1_2＝１０、Thr1_3＝２０、Ｎ１＝４、Ｎ２＝３、Ｎ３＝２、Thr2_1＝３２、Thr2_2＝６４、Thr2_3＝１２８とし、図８に示すように、割り当てる動きベクトル探索可能回数を４０回、探索原点を（８、−１）とし、動きベクトル探索回数が１〜１３回の間は、ＴＨＲ１＝Thr1_1＝５、Ｎ＝Ｎ１＝４、ＴＨＲ２＝Thr2_1＝３２、（動きベクトル探索回数が１４回以降のＴＨＲ１、Ｎ、ＴＨＲ２は表示を省略している）、動きベクトルの探索を行うと、たとえば、図９に示すような動きベクトル探索結果を得ることができる。図１０は探索パターン中心の移動の様子を示している。
【００５０】
ここで、条件３チェックブロック１５を設けない場合には、動きベクトル探索回数が１３回では動きベクトル探索は終了せず、更に続いて動きベクトル探索を行うことになり、たとえば、図１１に示すように、前回（［ｉ−１］回目）の動きベクトル探索でＳＡＤが最小であった探索点のＳＡＤ：minＳＡＤ［ｉ−１］と今回（［ｉ］回目）の動きベクトル探索でＳＡＤが最小であった探索点のＳＡＤ：minＳＡＤ［ｉ］の差分絶対値｜minＳＡＤ［ｉ］−minＳＡＤ［ｉ−１］｜の変化が小さく、これ以上、動きベクトル探索の必要がないにも関わらず、無駄な動きベクトル探索を行ってしまう場合が発生してしまう。
【００５１】
以上のように、本発明の追跡型動きベクトル探索装置の一実施形態においては、現マクロブロックについて、条件１（探索パターン中心の探索点のＳＡＤが一番小さくなっている）、条件２（現マクロブロックの画素のデータと参照画素のデータとの差分絶対値の総和の変化量が所定の回数、連続して一定値以下になる）、条件３（現マクロブロックの画素のデータと参照画素のデータとの差分絶対値の総和が一定値以下になる）又は条件４（現マクロブロックの動きベクトル探索回数が割り当てられた動きベクトル探索可能回数を超える）のいずれかの条件が満たされると、動きベクトル探索終了信号が出力され、現マクロブロックについての動きベクトル探索が終了となる。
【００５２】
したがって、たとえば、現動きベクトル探索回数が現マクロブロックに割り当てられた動きベクトル探索可能回数を超える（条件４を満たす）前に、現マクロブロックの画素のデータと参照画素のデータとの差分絶対値の総和の変化量が所定の回数、連続して一定値以下になると（条件２を満たすと）、動きベクトル探索終了信号が出力され、現マクロブロックについての動きベクトルの探索が終了とされる。この結果、たとえば、図７に示すように、前回の動きベクトル探索でＳＡＤが最小であった探索点のＳＡＤと今回の動きベクトル探索でＳＡＤが最小であった探索点のＳＡＤの差分絶対値の変化が小さく、これ以上、動きベクトル探索の必要がないにも関わらず、動きベクトル探索を続けてしまうという、無駄な動きベクトル探索を防ぐことができる。
【００５３】
また、現動きベクトル探索回数が現マクロブロックに割り当てられた動きベクトル探索可能回数を超える（条件４を満たす）前に、現マクロブロックの画素のデータと参照画素のデータとの差分絶対値の総和が一定値以下になると（条件３を満たすと）、動きベクトル探索終了信号が出力され、現マクロブロックについての動きベクトルの探索が終了とされる。この結果、たとえば、図１１に示すように、前回の動きベクトル探索でＳＡＤが最小であった探索点のＳＡＤと今回の動きベクトル探索でＳＡＤが最小であった探索点のＳＡＤの差分絶対値の変化が小さく、これ以上、動きベクトル探索の必要がないにも関わらず、動きベクトル探索を続けてしまうという、無駄な動きベクトル探索を防ぐことができる。
【００５４】
また、数２に示すように、１フレームに割り当てられた動きベクトル探索可能回数から前マクロブロックまでに要した動きベクトル探索回数を減じた値を残りの処理単位数で割った値を現マクロブロックの動きベクトル探索可能回数としているので、長い時間の無駄な動きベクトル探索を防ぐことができ、残りのマクロブロックについての動きベクトル探索時間に不足が生じないようにすることができる。
【００５５】
以上のように、本発明の追跡型動きベクトル探索装置の一実施形態によれば、ＭＰＥＧエンコーダにおいて、無駄な動きベクトル探索を行わないように動きベクトル探索を終了することができるので、動きベクトル探索の効率化を図ることができる。なお、本発明は、ＭＰＥＧエンコーダのみでなく、追跡型の動きベクトル探索を行う動画像エンコーダに広く適用することができる。
【００５６】
【発明の効果】
以上のように、本発明の追跡型動きベクトル探索方法によれば、動きベクトル探索可能回数を処理単位ごとに設定するとしているので、無駄な動きベクトル探索を防ぎ、動きベクトル探索の効率化を図ることができる。
【００５７】
本発明の追跡型動きベクトル探索装置によれば、動きベクトル探索可能回数を処理単位ごとに設定することができるので、無駄な動きベクトル探索を防ぎ、動きベクトル探索の効率化を図ることができる。
【図面の簡単な説明】
【図１】本発明の追跡型動きベクトル探索装置の一実施形態の一部分を示す回路図である。
【図２】本発明の追跡型動きベクトル探索装置の一実施形態が備える探索終了判断部の構成を示す回路図である。
【図３】本発明の追跡型動きベクトル探索装置の一実施形態の動作を説明するための図である。
【図４】本発明の追跡型動きベクトル探索装置の一実施形態の動作を説明するための図である。
【図５】本発明の追跡型動きベクトル探索装置の一実施形態の動作を説明するための図である。
【図６】本発明の追跡型動きベクトル探索装置の一実施形態の動作を説明するための図である。
【図７】本発明の追跡型動きベクトル探索装置の一実施形態の動作を説明するための図である。
【図８】本発明の追跡型動きベクトル探索装置の一実施形態の動作を説明するための図である。
【図９】本発明の追跡型動きベクトル探索装置の一実施形態の動作を説明するための図である。
【図１０】本発明の追跡型動きベクトル探索装置の一実施形態の動作を説明するための図である。
【図１１】本発明の追跡型動きベクトル探索装置の一実施形態の動作を説明するための図である。
【図１２】フルサーチ（Full Search）法を説明するための図である。
【図１３】ＴＳＳ（Three Step Search）法を説明するための図である。
【図１４】ＮＴＳＳ（New Three Step Search）法を説明するための図である。
【図１５】４×４サンプリング法を説明するための図である。
【図１６】追跡型動きベクトル探索方法の一例を説明するための図である。
【符号の説明】
１  エンコーダ制御部
２  探索データ生成部
３  ＳＡＤ演算部
４  探索制御部
５  探索順番制御部
６  動きベクトル計算部
７  探索終了判断部
８  探索回数カウンタ
９  レジスタ
１０  残り探索可能回数計算ブロック
１１  条件１チェックブロック
１２  条件２チェックブロック
１３  セレクタ
１４  セレクタ
１５  条件３チェックブロック
１６  セレクタ
１７  条件４チェックブロック
１８  ＯＲ回路
【図１】
0004923368.tif 000005
【図２】
0004923368.tif 000006
【図３】
0004923368.tif 000007
【図４】
0004923368.tif 000008
【図５】
0004923368.tif 000009
【図６】
0004923368.tif 000010
【図７】
0004923368.tif 000011
【図８】
0004923368.tif 000012
【図９】
0004923368.tif 000013
【図１０】
0004923368.tif 000014
【図１１】
0004923368.tif 000015
【図１２】
0004923368.tif 000016
【図１３】
0004923368.tif 000017
【図１４】
0004923368.tif 000018
【図１５】
0004923368.tif 000019
【図１６】
0004923368.tif 000020