(57)【要約】【課題】  階層化された動きベクトル検出方法において、探索候補点数を削減し、効率的な探索処理を実現する。【解決手段】  複数の初期探索点近傍の画像と当該現在フレームの部分領域の画像との類似度を求める手段（Ｓ００１）と、複数の初期探索点毎の類似度の勾配から次の複数の探索候補点を設定する手段（Ｓ００２〜Ｓ００３）と、設定された複数の探索候補点近傍の画像と当該現在フレームの部分領域の画像との類似度を求める手段（Ｓ００４）と、当該求められた複数の探索候補点毎の最大の類似度を与える探索点候補の位置から当該現在フレームの部分領域の画像に対する動きベクトルを検出する（Ｓ００５〜Ｓ００６）動きベクトル検出方法。【選択図】  図２
2006254349.tif 000002
【特許請求の範囲】
【請求項１】
現在フレームの部分領域の画像が時間的に連続する参照フレームの画像のどの部分から移動したものかを示す動きベクトルを検出する動きベクトル検出方法において、前記参照フレーム上に設定される複数の初期探索点近傍の画像と当該現在フレームの部分領域の画像との類似度を求めるステップと、前記複数の初期探索点毎に求められた類似度の勾配または前記複数の初期探索点毎に求められた類似度の分布から次の複数の探索候補点を設定するステップと、当該設定された複数の探索候補点近傍の画像と当該現在フレームの部分領域の画像との類似度を求めるステップと、当該求められた複数の探索候補点毎の類似度のうち、最大の類似度を与える探索点候補の位置から当該現在フレームの部分領域の画像に対する動きベクトルを検出するステップを具備したことを特徴とする動きベクトル検出方法。
【請求項２】
前記複数の初期探索点は前記参照フレーム上に２画素精度で設定され、前記複数の探索候補点は前記参照フレーム上に１画素以下の精度で設定されることを特徴とする請求項１記載の動きベクトル検出方法。
【請求項３】
前記次の複数の探索候補点を設定するステップは、前記複数の初期探索点毎の類似度の値が大きい初期探索点近傍の探索候補点を優先的に候補として設定することを特徴とする請求項１記載の動きベクトル検出方法。
【請求項４】
前記複数の初期探索点毎の類似度を求めるステップは、前記複数の初期探索点近傍の画像と前記現在フレームの部分領域の画像との間の累積差分絶対値和を当該類似度の評価値として求めることを特徴とする請求項１記載の動きベクトル検出方法。
【請求項５】
前記複数の初期探索点は、所定の探索中心点近傍の画像と前記現在フレームの部分領域の画像との類似度の値及び前記所定の探索中心点の周囲の探索候補点近傍の画像と前記現在フレームの部分領域の画像との類似度の値とに基づいて反復的に探索を繰り返し、複数の初期探索候補点から類似度の値の大きい複数の初期探索点が定められることを特徴とする請求項１記載の動きベクトル検出方法。
【請求項６】
前記複数の初期探索点毎の類似度を求めるステップは、所定の探索範囲の探索候補点のうち、その一部となる探索点について前記類似度を計算することを特徴とする請求項１記載の動きベクトル検出方法。
【請求項７】
前記次の複数の探索候補点を設定するステップは、前記複数の初期探索点のうち、垂直または水平方向に隣接する複数の初期探索点毎の類似度の値を比較して、当該類似度の値が大きくなる前記参照フレームの垂直または水平方向に前記次の複数の探索候補点を設定することを特徴とする請求項１記載の動きベクトル検出方法。
【請求項８】
前記次の複数の探索候補点を設定するステップは、前記複数の初期探索点のうち、垂直または水平方向に隣接する複数の初期探索点毎の類似度の値を比較して、当該類似度の値の差が０または所定のしきい値以下であった場合には、当該隣接する複数の初期探索点の間の候補点を含めて前記次の複数の探索候補点を設定することを特徴とする請求項１記載の動きベクトル検出方法。
【請求項９】
現在フレームの部分領域の画像が時間的に連続する参照フレームの画像のどの部分から移動したものかを示す動きベクトルを検出する動きベクトル検出装置において、前記参照フレーム上に設定される複数の初期探索点近傍の画像と当該現在フレームの部分領域の画像との類似度を求める手段と、前記複数の初期探索点毎に求められた類似度の勾配または前記複数の初期探索点毎に求められた類似度の分布から次の複数の探索候補点を設定する手段と、当該設定された複数の探索候補点近傍の画像と当該現在フレームの部分領域の画像との類似度を求める手段と、当該求められた複数の探索候補点毎の類似度のうち、最大の類似度を与える探索点候補の位置から当該現在フレームの部分領域の画像に対する動きベクトルを検出する手段を具備したことを特徴とする動きベクトル検出装置。
【請求項１０】
前記複数の初期探索点は前記参照フレーム上に２画素精度で設定され、前記複数の探索候補点は前記参照フレーム上に１画素以下の精度で設定されることを特徴とする請求項９記載の動きベクトル検出装置。
【請求項１１】
前記次の複数の探索候補点を設定する手段は、前記複数の初期探索点毎の類似度の値が大きい初期探索点近傍の探索候補点を優先的に候補として設定することを特徴とする請求項９記載の動きベクトル検出装置。
【請求項１２】
前記複数の初期探索点毎の類似度を求める手段は、前記複数の初期探索点近傍の画像と前記現在フレームの部分領域の画像との間の累積差分絶対値和を当該類似度の評価値として求めることを特徴とする請求項９記載の動きベクトル検出装置。
【請求項１３】
前記複数の初期探索点は、所定の探索中心点近傍の画像と前記現在フレームの部分領域の画像との類似度の値及び前記所定の探索中心点の周囲の探索候補点近傍の画像と前記現在フレームの部分領域の画像との類似度の値とに基づいて反復的に探索を繰り返し、複数の初期探索候補点から類似度の値の大きい複数の初期探索点が定められることを特徴とする請求項９記載の動きベクトル検出装置。
【請求項１４】
前記複数の初期探索点毎の類似度を求める手段は、所定の探索範囲の探索候補点のうち、その一部となる探索点について前記類似度を計算することを特徴とする請求項９記載の動きベクトル検出装置。
【請求項１５】
前記次の複数の探索候補点を設定する手段は、前記複数の初期探索点のうち、垂直または水平方向に隣接する複数の初期探索点毎の類似度の値を比較して、当該類似度の値が大きくなる前記参照フレームの垂直または水平方向に前記次の複数の探索候補点を設定することを特徴とする請求項９記載の動きベクトル検出装置。
【請求項１６】
前記次の複数の探索候補点を設定する手段は、前記複数の初期探索点のうち、垂直または水平方向に隣接する複数の初期探索点毎の類似度の値を比較して、当該類似度の値の差が０または所定のしきい値以下であった場合には、当該隣接する複数の初期探索点の間の候補点を含めて前記次の複数の探索候補点を設定することを特徴とする請求項９記載の動きベクトル検出装置。
【請求項１７】
現在フレームの部分領域の画像が時間的に連続する参照フレームの画像のどの部分から移動したものかを示す動きベクトルを検出する動きベクトル検出プログラムにおいて、前記参照フレーム上に設定される複数の初期探索点近傍の画像と当該現在フレームの部分領域の画像との類似度を求める手順と、前記複数の初期探索点毎に求められた類似度の勾配または前記複数の初期探索点毎に求められた類似度の分布から次の複数の探索候補点を設定する手順と、当該設定された複数の探索候補点近傍の画像と当該現在フレームの部分領域の画像との類似度を求める手順と、当該求められた複数の探索候補点毎の類似度のうち、最大の類似度を与える探索点候補の位置から当該現在フレームの部分領域の画像に対する動きベクトルを検出する手順をコンピュータに実行させることを特徴とする動きベクトル検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＭＰＥＧ−２（Moving Picture Expert Group phase 2）やＭＰＥＧ−４（Moving Picture Expert Group phase 4）などの動画像の動き補償予測符号化を行う際に必要な動きベクトル検出に関するものである。
【背景技術】
【０００２】
ＭＰＥＧ−２などの蓄積、画像伝送を目的とした動画像符号化処理においては、画像フレーム相互間の相関を利用して動画像の情報量を削減して圧縮を実現する。ここで時間的に連続するフレーム画像間の各部分画像の動きを追う動きベクトル検出は、現画像内の複数の画素からなる部分画像（ブロック画像）を処理対象とし、この処理対象ブロックが、当該現画像に対する時間的に過去の画像のどの位置に存在するか（処理対象ブロックの画像が過去の画像のどの位置の画像に最も類似するか）をいわゆるブロックマッチング法により調べ、画像の動きの方向、及び量を示す動きベクトルを検出する。
【０００３】
この動きベクトル検出処理は、動画像圧縮符号化の処理全体において非常に大きな処理量を占めている。この問題に対する対策として、反復勾配法、すなわち画素信号の空間的勾配とフレーム間差分の関係から動きベクトルを推定する手法を収束するまで実行し、精度の高い動きベクトルを求める方法や、ダイヤモンドサーチ、すなわち大まかな動きベクトルを求めるサーチパターンに従って逐次的にフレーム間差分が極小となる動きベクトルを求めた後、細かな動きベクトルを求めるサーチパターンに従って動きベクトルを求める方法などの最急降下法に基づく動きベクトル検出方法がある。これらの手法は最も単純な動きベクトル探索方法である全探索法に比べ、大幅に必要演算量が低減されることが示されている。特に最急降下法の適用に先立って動きベクトルの尤度が最も高い点を初期探索点として設定することにより、演算量を更に削減できることが知られている。
【０００４】
また動きベクトル検出において、更に探索処理を削減するため、動きベクトルの探索は整数精度の動きベクトルを求めるステップの後に、サブピクセル精度の動きを求めるような、階層化を利用することが一般的である。
【０００５】
ここで精度良く初期探索点が求まると、動きベクトル探索の処理時間における最急降下法を適用している時間が短くなるものの、その後段のサブピクセル精度の動きベクトル探索にかかる時間が顕在化するという問題がある。
【０００６】
非特許文献１に示されるダイヤモンドサーチは、整数精度画素の動きベクトルを探索するための手法である。一方、ＭＰＥＧ−１／−２／−４あるいはＭＰＥＧ−４ ＡＶＣ／Ｈ．２６４（Advanced Video Coding/H.264）といった国際標準方式においては、動きベクトルの精度は０.５画素もしくは０.２５画素単位であり、特にＭＰＥＧ−４の一部のプロファイルやＭＰＥＧ−４ ＡＶＣ／Ｈ．２６４における０.５画素精度の動きベクトル探索においては、精度の高い画素間の補間を行うために、６タップのＦＩＲフィルタ（Finite Impulse Responseフィルタ）を用いることになっている。このため、ダイヤモンドサーチで求められた整数精度の動きベクトルの周囲をサブピクセル精度で全探索を行うと、検出に必要な処理量が大きくなり、ソフトウェアによるリアルタイム符号化の実現の障害となるほか、ハードウェアにおいては、動きベクトル探索処理に伴う消費電力や回路量の増大につながるという問題があった。
【０００７】
また非特許文献２に示されたダイヤモンドサーチを改良した手法によれば、整数精度画素の動きベクトル検出を実現することができる。この手法によれば、２画素精度の動きベクトル探索（一次探索）の後、最良の一次探索点を中心としてより詳細に探索を行ない、１画素精度の動きベクトル探索（二次探索）を実施することとなる。
【０００８】
しかし探索精度を確保し動きベクトル検出を実行するためには、一次探索後の詳細探索（二次探索）の候補点の数は少なくとも８点を確保する必要があり、その候補点（周囲の８画素）を中心とするブロックマッチング処理を８回繰り返して、コスト量を計算しなければならないという問題があった。よって動きベクトル探索における詳細探索（二次探索）演算処理量を削減できず、多くの映像において処理時間の短縮化も図れないという問題があった。
【非特許文献１】S. Zhu and K. K. Ma, "A new diamond search algorithm for fast block matching motion estimation," IEEE Trans. on Image Processing, vol. 9, no. 2, pp. 287-290, Feb. 2000
【非特許文献２】K.Ramkishor, PSSBK Gupta, et al., "Algorithmic Optimization for Software-Only MPEG-2 Encoding," IEEE Trans. on Consumer Electronics, Vol. ５０, No. １, Feb. ２００４
【発明の開示】
【発明が解決しようとする課題】
【０００９】
以上詳述した通り、従来の動きベクトル検出方法においては、動きベクトル探索範囲の階層化を図ることにより全体の演算処理量を削減しようとするが、詳細探索（二次探索）の探索候補点の数を絞り込むことができないため、二次探索の処理量を削減できず、処理時間の短縮化を図ることができないという問題があった。
【課題を解決するための手段】
【００１０】
上述の課題を解決し、目的を達成するために、本発明における動きベクトル検出方法は、現在フレームの部分領域の画像が時間的に連続する参照フレームの画像のどの部分から移動したものかを示す動きベクトルを検出する動きベクトル検出方法において、前記参照フレーム上に設定される複数の初期探索点近傍の画像と当該現在フレームの部分領域の画像との類似度を求めるステップと、前記複数の初期探索点毎に求められた類似度の勾配または前記複数の初期探索点毎に求められた類似度の分布から次の複数の探索候補点を設定するステップと、当該設定された複数の探索候補点近傍の画像と当該現在フレームの部分領域の画像との類似度を求めるステップと、当該求められた複数の探索候補点毎の類似度のうち、最大の類似度を与える探索点候補の位置から当該現在フレームの部分領域の画像に対する動きベクトルを検出するステップを具備したことを特徴とする。
【００１１】
また本発明の動きベクトル検出装置は、現在フレームの部分領域の画像が時間的に連続する参照フレームの画像のどの部分から移動したものかを示す動きベクトルを検出する動きベクトル検出装置において、前記参照フレーム上に設定される複数の初期探索点近傍の画像と当該現在フレームの部分領域の画像との類似度を求める手段と、前記複数の初期探索点毎に求められた類似度の勾配または前記複数の初期探索点毎に求められた類似度の分布から次の複数の探索候補点を設定する手段と、当該設定された複数の探索候補点近傍の画像と当該現在フレームの部分領域の画像との類似度を求める手段と、当該求められた複数の探索候補点毎の類似度のうち、最大の類似度を与える探索点候補の位置から当該現在フレームの部分領域の画像に対する動きベクトルを検出する手段を具備したことを特徴とする。
【００１２】
また本発明の動きベクトル検出プログラムは、現在フレームの部分領域の画像が時間的に連続する参照フレームの画像のどの部分から移動したものかを示す動きベクトルを検出する動きベクトル検出プログラムにおいて、前記参照フレーム上に設定される複数の初期探索点近傍の画像と当該現在フレームの部分領域の画像との類似度を求める手順と、前記複数の初期探索点毎に求められた類似度の勾配または前記複数の初期探索点毎に求められた類似度の分布から次の複数の探索候補点を設定する手順と、当該設定された複数の探索候補点近傍の画像と当該現在フレームの部分領域の画像との類似度を求める手順と、当該求められた複数の探索候補点毎の類似度のうち、最大の類似度を与える探索点候補の位置から当該現在フレームの部分領域の画像に対する動きベクトルを検出する手順をコンピュータに実行させることを特徴とする。
【発明の効果】
【００１３】
本発明によれば、２画素精度等の粗い精度で求められた動きベクトル探索結果を元に１画素精度や０．５画素精度のより詳細な動きベクトルを探索する等、探索精度の異なる複数の動きベクトル探索を階層的に実施する動きベクトル検出方法及び装置において、サブピクセル精度の動きベクトル探索においても探索点を削減することができ、動きベクトル探索の処理量を削減し、処理速度を向上させることができる。
【発明を実施するための最良の形態】
【００１４】
以下に添付図面を参照して、本発明にかかる動きベクトル検出方法及び装置の好適な実施の形態を詳細に説明する。
【００１５】
始めに本発明の動きベクトル検出方法及び装置を適用可能なＭＰＥＧ符号化装置全体のブロック図の例を図１に示す。ＭＰＥＧ符号化装置は、動き検出器１０１、 動き補償器１０２、フレームメモリ１０３、減算器１０４、加算器１０５、離散コサイン変換器（ＤＣＴ）１０６、逆離散コサイン変換器（逆ＤＣＴ）１０７、量子化器１０８、逆量子化器１０９、可変長符号化器１１０、量子化制御器１１１によって構成される。
【００１６】
過去に符号化された画像は、逆量子化器１０９、逆ＤＣＴ１０７され、フレームメモリ１０３に蓄積される。新たに符号化すべき画像が入力されると、動き検出器１０２により、当該入力画像の部分領域（マクロブロック）の画像がフレームメモリ１０３に蓄積された画像のいずれの部分から移動したものかを示す動きベクトルが検出される。動き検出器１０２で検出された動きベクトルとフレームメモリに蓄積された画像とから新たに符号化すべき画像に対する予測画像が生成され、この予測画像と入力画像との誤差情報が、ＤＣＴ係数に変換され（１０６）、量子化処理された後（１０８）、可変長符号化（１１０）されて圧縮符号化列（出力ビットストリーム）として出力される。
【００１７】
次に上記動き検出器１０１で用いられる動きベクトル検出方法、装置について詳細に説明する。図２は本発明の第１の実施の形態による動きベクトル検出方法を示すフローチャートである。図２は、大きく分けて粗い精度で動きベクトルを検出する処理(一次探索：Ｓ００１)と、その結果に応じて細かい精度で動きベクトルを検出処理(二次探索：Ｓ００２以降)に大別される。本実施の形態は、２階層の動きベクトル探索により、最終的に整数精度の動きベクトルを求めることを目的とするものである。
【００１８】
ステップＳ００１で求める１次探索（第１階層動きベクトル探索）のアルゴリズムとして、ここでは非特許文献２に示されるＳｈｏｒｔ  ＬＤＳＰ（Ｓｈｏｒｔ  Ｌａｒｇｅ  Ｄｉａｍｏｎｄ  Ｓｅａｒｃｈ  Ｐａｔｔｅｒｎ）と呼ばれる方法を用いるものと仮定する。なお、本発明はＳｈｏｒｔ  ＬＤＳＰに限定して適用可能なものではなく、ダイヤモンドサーチそのものにも適用可能であるし、その他の階層的なサーチ法にも適用可能である。
【００１９】
Ｓｈｏｒｔ  ＬＤＳＰを採用したときの動きベクトル探索のための初期探索点を図 ３に示す。ステップＳ００１では、図 ３に示したＳｈｏｒｔ  ＬＤＳＰの探索点を用いて、最急降下法に基づいて粗い精度の動きベクトルを求める。このフローチャートを図 ４に示す。
【００２０】
まず、ステップＳ１００において、参照画像Ｒ上に設定された探索中心点ｒ（ｘ０，ｙ０）∈Ｒと、現在の符号化画像Ｃ上の点ｃ（ｘ，ｙ）∈Ｃに位置するマクロブロック(１６×１６画素からなる矩形領域)との間でブロックマッチングを行い、探索中心点と現在のマクロブロックとの類似度を示すＳＡＤ(累積差分絶対値和)を以下の式に基づいて求める。
【数１】
2006254349.tif 000003
【００２１】
ＳＡＤの値が小さいということは、探索点と現在のマクロブロックとの差分が小さく、探索点と現在のマクロブロックとが類似していること（類似度の値が大きい）を示し、ＳＡＤが大きいということは、逆に類似していない（類似度の値が小さい）ということになる。すなわち、同一のマクロブロックに対するＳＡＤが異なる２つの探索点を比べた場合、ＳＡＤが小さい値を与える探索点が現在のマクロブロックとの差分が小さく、より良い動きベクトルを表す探索点であると言える。
【００２２】
なお、ＳＡＤを求める代わりにＳＳＤ(累積差分二乗和)を求める手法を用いても良く、本発明におけるブロックマッチングの処理はＳＡＤに限定されるものではない。また本実施例の説明においては、符号化対象画像と参照画像との「類似度（似ている度合い）」と言う概念でマッチングを評価するものとしたが、画像間の類似度が小さい場合を「コスト量の値が大きい（符号化に要する情報量が大きい）」と評価することにより、コスト量が小さい値を与える探索点を求めるように評価関数を定義してもよい。
【００２３】
ステップＳ１０１では点(ｘ０，ｙ０)を中心として、上下左右の各点(ｘ０，ｙ０＋２)、(ｘ０，ｙ０−２)、(ｘ０−２，ｙ０)、(ｘ０＋２，ｙ０)について式１と同様にＳＡＤを求める。これらのＳＡＤをそれぞれＳＡＤ１,ＳＡＤ２,ＳＡＤ３,ＳＡＤ４とすれば、これらは次式で求められる。
【数２】
2006254349.tif 000004
【００２４】
次にステップＳ１０２において、ＳＡＤ０〜ＳＡＤ４の値を比較し、ＳＡＤ０が最小であるかを判定する。もし、ＳＡＤ０が最小であった場合、点（ｘ０，ｙ０）を指し示す動きベクトルが、ステップＳ００１で求めるべき動きベクトルとなり、図４に示す処理を終了する。ＳＡＤ０が最小でない場合には、ステップＳ１０３にてＳＡＤ０〜ＳＡＤ４のうち最小となるＳＡＤを持つ点を新たな探索中心点とする。すなわち、
【数３】
2006254349.tif 000005
【００２５】
新しく設定した探索中心点のＳＡＤは既に計算済みであるから、新たなＳＡＤ０はステップＳ１０４で次式にしたがって求められる。
【数４】
2006254349.tif 000006
【００２６】
さらに、新しい探索中心点に対して上下左右の新たな探索点のうち１点は、既にＳＡＤを求めているので、ステップＳ１０５にて既に探索済みのＳＡＤを図５にしたがって代入する。
【００２７】
ステップ１０６では、ステップ１０５で「undefined」となったＳＡＤについて、式２に基づいて改めてＳＡＤを計算する。このようにして、新たに設定された探索中心点の上下左右のＳＡＤが求められると、ステップＳ１０２に戻り、改めてＳＡＤ０がＳＡＤ０〜ＳＡＤ４の中で最小であるか否かが判定される。
【００２８】
ステップＳ１０３からＳ１０６までの処理を、ステップＳ１０２の判定結果が真になるまで繰り返すことにより、符号化対象画像のマクロブロックと最も似通った参照画像の領域が２画素精度で選択され、その動きベクトルすなわち粗い精度の動きベクトルが求められる。
【００２９】
以上に示した処理がステップＳ１０１の処理であり、ここで求められた動きベクトルを
【数５】
2006254349.tif 000007
【００３０】
とおく。この時点で、ＳＡＤ１,ＳＡＤ２,ＳＡＤ３,ＳＡＤ４が、それぞれ探索点(ｘ０，ｙ０)に対して右, 下, 左, 上に２画素離れた探索点の類似度を示していることになる。
【００３１】
ステップＳ００２では、既に求められた周囲の探索点のＳＡＤから、１画素精度の動きベクトルが現在の動きベクトルＭＶ０に対して左右どちら側に存在するかを推定する。最急降下法によって動きベクトルが正しく求まるということは、ＳＡＤは隣接する探索点に対して滑らかに連続する関数となることが推定できる。したがって、ＳＡＤ１よりもＳＡＤ３が十分に大きければ、求めるべき１画素精度の動きベクトルはＭＶ０の右側にある可能性が高く、ＳＡＤ１よりもＳＡＤ３が十分に小さければ逆に左側にある可能性が高い。そこで、以上の仮定の下、次のような式にしたがって、水平方向の探索点の範囲を示すリストを決定する。
【数６】
2006254349.tif 000008
【００３２】
ここで、Ｘｌｉｓｔは現在の動きベクトルに対して、これから新たに探索する探索点の変位を表すリストであり、例えば(０,１)とは、水平方向には変化させない探索点と、右に１画素ずらした探索点に対してブロックマッチングを行うことを意味する。また、Ｔは所定のしきい値である。ＳＡＤが滑らかに連続する場合でも、その極小点付近で対称なカーブを描くとは限らない。このため、ＳＡＤ１とＳＡＤ３の差が大きくないときには、現在の動きベクトルの左右両方を調べる必要がある。
【００３３】
同様に、ＳＡＤ２よりもＳＡＤ４が大きければ、求めるべき１画素精度の動きベクトルはＭＶ０の下側にある可能性が高く、ＳＡＤ２よりもＳＡＤ４が小さければ、逆に上側にある可能性が高い。そこで、ステップＳ００３ では次式で垂直方向の探索点の範囲のリストＹｌｉｓｔを定める。
【数７】
2006254349.tif 000009
【００３４】
ステップＳ００４では、ステップＳ００２とＳ００３で求めた探索点のすべての組み合わせのうち、まだＳＡＤを求めていない探索点に対してＳＡＤを求める。この処理を擬似プログラムコードで書いた構成例を図７に示す。
【００３５】
図７において、初期探索点(ｘ０，ｙ０)におけるＳＡＤをＳＡＤ［０］に保存する（ステップ（ａ））。初期探索点の周囲の探索点で得られたＳＡＤ値の大小関係により、ｘ方向、ｙ方向の探索範囲を決定する（ステップ（ｂ））。この初期探索点（ｘ０，ｙ０））は現在の粗い精度の動きベクトルが指し示す点であるので、ＳＡＤを新たに計算する必要がない。それ以外の点は未探索であるため、それぞれのＳＡＤを求め、配列ＳＡＤ［ｊ］に保存する（ステップ（ｃ））。以上のような過程で、合計Ｎ個のＳＡＤ(ＳＡＤ［０］〜ＳＡＤ［Ｎ−１］)が求められる。
【００３６】
ステップＳ００５では、ステップＳ００１で求めた現在の動きベクトルが指し示すＳＡＤと、ステップＳ００４で求めたすべての探索点のＳＡＤを調査し、最小となるＳＡＤを求める。前述したように、ＳＡＤが小さいということは現在のマクロブロックと最も似た領域であるということを意味する。したがって、ステップＳ００６にて、求めた最小ＳＡＤに対応する探索点を１画素精度の動きベクトルとする。すなわち、整数精度動きベクトルＭＶintは次式にしたがって定義される。
【数８】
2006254349.tif 000010
【００３７】
ここで、arg min(x[０]…x[k-１])とは、配列x[０]〜x[k-１]までの最小値を選択し、そのインデックス番号を返す関数である。
【００３８】
非特許文献２に示された動きベクトル探索例では、周囲の探索点の大小にかかわらず、常に２画素精度動きベクトルの周囲８点を探索しなければならず、動きベクトルの探索処理（ブロックマッチング）が膨大となり、多数の処理時間を要していたが、本発明によれば、一次探索における各探索点のＳＡＤの勾配またはフレーム内分布を比較して、残差が小さい方向だけを探索するよう新たな動きベクトル探索点を制限的に設定することにより、上述した１画素精度の動きベクトルの探索点は３点に削減することができる（図６参照）。
【００３９】
ここで各探索点の類似度の勾配、すなわちＳＡＤの勾配とは各探索点におけるＳＡＤの値のフレーム内の変化の度合いを意味するものとする。そしてＳＡＤの値の大きさが大きくなる方向に新たな探索点を設定する。また各探索点の類似度のフレーム内分布、すなわちＳＡＤのフレーム内分布とは各探索点におけるＳＡＤの値のフレーム内の存在状態を意味するものとする。よって一次探索における各探索点のＳＡＤの値の分布を調べて、ＳＡＤの値の大きさが大きくなる方向に新たな探索点を設定する。
【００４０】
以上の一連の動作の例を、探索点の移動という形で表現した図を図８に示す。まず、最初の探索中心点が、５の位置にあったとする。Ｓｈｏｒｔ  ＬＤＳＰにしたがって、探索パターン１の領域の中央および頂点に位置する点５、６、７、８、９に対してＳＡＤを求める。
【００４１】
その結果、点９に対応するＳＡＤが最も小さかったとすると、次に点９を中心とするＳｈｏｒｔ  ＬＤＳＰ探索パターン２の頂点のうち未探索の点１０、１１、１２についてＳＡＤを求め、既に求めた点５、９を含め、最小のＳＡＤを持つ点を求める。この探索点が点１２だったとする。同様の手続きに従って、点６、１２、１４のＳＡＤを求め、点６、９、１２、１３、１４のうちＳＡＤが最小の探索点を求める。
【００４２】
その結果、探索パターンの中央の点１２が該当する点である場合、ここで２画素精度の動きベクトルの探索に相当するステップＳ００１が終了する。
【００４３】
次に、点１２と点６のＳＡＤの大きさを比較する。いま、点１２のＳＡＤが十分に小さいとする(ステップＳ００２)。同様に点９と点１４のＳＡＤの大きさを比較し、点１４のＳＡＤが十分に小さいとする(ステップＳ００３)。
【００４４】
この結果を反映して、１画素精度の動きベクトルとして探索すべき点が１６、１７、１８であることになる。非特許文献２に示された探索点はこれらの探索点に加え、点１５、１９、２０、２１、２２であるので、探索点が８点から３点に削減されたことになる。上記探索すべき点３点について、ＳＡＤを求め(ステップＳ００４)、点１２、１６、１７、１８のうちＳＡＤが最も小さい点を探す(ステップＳ００５)。
【００４５】
その結果、点１７が最小のＳＡＤを持つ点だったとすると、点１７を指し示す動きベクトルが求めるべき１画素精度の動きベクトルということになる(ステップＳ００６)。
【００４６】
図９は本発明の第２の実施の形態による動きベクトル検出方法を示すフローチャートである。このフローチャートは、先述の第１の実施の形態で示した１画素精度の動きベクトルを求めた後、０.５画素精度の動きベクトルを求める場合の例を示したものである。
【００４７】
ステップＳ３０１にて、１画素精度の動きベクトルが求まる。前述の第１の実施の形態で示した方法を用いて１画素精度の動きベクトルが求められていたとすれば、このときの１画素精度の動きベクトルが指し示す探索点の周囲に位置する既探索点は、例えば図１０に示したような点となる。
【００４８】
ステップＳ３０２では、既に０.５画素精度の動きベクトルの探索方向が決定可能であるか否かを判断する。先述の第１の実施の形態と同様の手法により探索する方向を特定するためには、上下左右の隣接する探索点のＳＡＤが必要である。しかしながら、既にステップＳ３０１で動きベクトルが存在する可能性の高い方向が特定済みであれば、これらのＳＡＤを測定するまでもなく探索方向が決定できる。
【００４９】
図１０の例で言えば、ステップＳ３０１の結果、点Ａが１画素精度の動きベクトルとして選択された場合、０.５画素精度の動きベクトルは右、下、右下のいずれかに存在する可能性が高い。したがって、この場合には探索方向が決定可能であると判断できる。このときにはステップＳ３０４の処理を行う。しかしながら、点Ｂ、Ｃ、Ｄが１画素精度の動きベクトルとして選択された場合には、０.５画素精度の動きベクトルを探索すべき方向は決定できない。この場合にはステップＳ３０３の処理を行う。
【００５０】
ステップＳ３０３では、隣接する上下左右の探索点のうち、まだＳＡＤを求めていない探索点について、ＳＡＤを求める。図１０の例で、１画素精度の動きベクトルが点Ｂを指し示していた場合には点ｅについて、Ｃを指し示していた場合には点ｆについて、Ｄを指し示していたときには点ｇと点ｈについてＳＡＤを求める。
【００５１】
ステップＳ３０５では、第１の実施の形態のステップＳ００２およびＳ００３と同様の手法を用いて、０.５画素精度の探索方向を決定する。すなわち、上下左右に隣接した探索点のＳＡＤの大小関係から、動きベクトルを探索する方向が決定される。
【００５２】
一方、ステップＳ３０４では、既に処理済のステップＳ３０１の結果から０.５画素精度の探索方向を決定する。
【００５３】
ステップＳ３０６では、既に説明したステップＳ００４と同様の方法で、０.５画素精度の探索点について、ＳＡＤを求める。さらに、ステップＳ３０７では、既に説明したステップＳ００５と同様の方法で０.５画素精度の動きベクトルを求める。
【００５４】
以上で述べたように、本発明は整数画素精度の動きベクトル探索と０.５画素精度の動きベクトル探索のいずれにおいても、処理量を削減することができるものである。ここで実施の形態として説明しない場合、例えば０.２５画素精度の動きベクトル探索の場合についても、ここで説明した方法がまったく同様に利用可能であることは言うまでもない。
【図面の簡単な説明】
【００５５】
【図１】本発明を適用可能な動画像符号化装置の全体構成を示す図
【図２】本発明の動きベクトル検出方法の第１の実施の形態を示すフローチャート
【図３】Ｓｈｏｒｔ  ＬＤＳＰにおける動きベクトル探索パターンを示す図
【図４】Ｓｈｏｒｔ  ＬＤＳＰを用いた最急降下法に基づく粗ベクトル探索を示すフローチャート
【図５】ＳＡＤの更新例を示す図
【図６】本発明の動きベクトル検出方法を用いた１画素精度の動きベクトル探索点の設定例を示す図
【図７】動きベクトル探索（ＳＡＤ演算）のプログラムコード例を示す図
【図８】本発明に基づく探索点の推移例を示した図
【図９】本発明の動きベクトル検出方法の第２の実施の形態を示すフローチャート
【図１０】本発明の動きベクトル検出方法を用いた半画素精度の動きベクトル探索点の設定例を示す図
【符号の説明】
【００５６】
１０１  動き検出器
１０２  動き補償器
１０３  フレームメモリ
１０４  減算器
１０５  加算器
１０６  離散コサイン変換器
１０７  逆離散コサイン変化器
１０８  量子化器
１０９  逆量子化器
１１０  可変長符号化器
１１１  量子化制御器
【図１】
2006254349.tif 000011
【図２】
2006254349.tif 000012
【図３】
2006254349.tif 000013
【図４】
2006254349.tif 000014
【図５】
2006254349.tif 000015
【図６】
2006254349.tif 000016
【図７】
2006254349.tif 000017
【図８】
2006254349.tif 000018
【図９】
2006254349.tif 000019
【図１０】
2006254349.tif 000020