(57)【要約】【課題】動画像情報を高能率符号化する動き補償予測符号化に用いられ、省メモリ化と演算処理量の削減の図れる動きベクトル検出装置及び動きベクトル検出プログラムを提供する。【解決手段】動きベクトルの検出範囲内の画素の前記検出範囲の中心からの距離に応じて、前記検出範囲内の画素に対してブロックマッチングにおける比較対象となる動き検出対象ブロック内の画素の間引き率を設定する間引き率設定手段と、前記設定された間引き率に応じて、ブロックマッチングに用いる前記動き検出対象ブロック内の画素及び前記検出範囲内の画素を間引く間引き手段とを設ける。【選択図】      図１
2004260251.tif 000002
【特許請求の範囲】
【請求項１】
入力画像を所定数の画素単位毎にブロック化し、前記入力画像において各ブロックを順次動き検出対象ブロックとして設定し、参照画像において前記動き検出対象ブロックに応じて順次検出範囲を設定し、前記各動き検出対象ブロック内の画素と前記各検出範囲内の画素とを比較して、ブロックマッチングにより前記各動き検出対象ブロック毎に動きベクトルを求める動画像の動きベクトル検出装置において、
前記検出範囲内の画素の前記検出範囲の中心からの距離に応じて、前記検出範囲内の画素に対してブロックマッチングにおける比較対象となる前記動き検出対象ブロック内の画素の間引き率を設定する間引き率設定手段と、
前記設定された間引き率に応じて、ブロックマッチングに用いる前記動き検出対象ブロック内の画素及び前記検出範囲内の画素を間引く間引き手段と、
を設けたことを特徴とする動きベクトル検出装置。
【請求項２】
請求項１記載の動きベクトル検出装置において、
動き検出対象ブロックに設定されたブロックに隣接する、既に動きベクトルが求められているブロックの動きベクトルを用いて、予め定められている所定方法に従って求められる予測動きベクトルに応じて、前記動き検出対象ブロックに対して設定される前記検出範囲の中心位置を移動させる検出範囲移動手段を設けたことを特徴とする動きベクトル検出装置。
【請求項３】
請求項１記載の動きベクトル検出装置において、
前記間引き率設定手段は、動き検出対象ブロックに設定されたブロックに隣接する、既に動きベクトルが求められているブロックの動きベクトル、及び前記検出範囲の中心からの距離に応じて、前記間引き率を設定するものであることを特徴とする動きベクトル検出装置。
【請求項４】
動画像である入力画像を所定数の画素単位毎にブロック化し、前記入力画像において各ブロックを順次動き検出対象ブロックとして設定し、参照画像において前記動き検出対象ブロックに応じて順次検出範囲を設定し、前記各動き検出対象ブロック内の画素と前記各検出範囲内の画素とを比較して、ブロックマッチングにより前記各動き検出対象ブロック毎に動きベクトルを求める動作をコンピュータに行わせる動きベクトル検出プログラムにおいて、
前記検出範囲内の画素の前記検出範囲の中心からの距離に応じて、前記検出範囲内の画素に対してブロックマッチングにおける比較対象となる前記動き検出対象ブロック内の画素の間引き率を設定する間引き率設定手機能と、
前記設定された間引き率に応じて、ブロックマッチングに用いる前記動き検出対象ブロック内の画素及び前記検出範囲内の画素を間引く間引き機能と、
をコンピュータに実行させることを特徴とする動きベクトル検出プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は動画像情報を高能率符号化する動き補償予測符号化における動きベクトル検出に係り、特に省メモリ化と演算処理量の削減の図れる動きベクトル検出装置及び動きベクトル検出プログラムに関する。
【０００２】
【従来の技術】
動画像符号化として、従来から動き補償予測が用いられている。動き補償予測はＭＰＥＧなど国際標準方式でも広く用いられていて、ブロック毎に画像間予測を行なう際に動画像の動きに合わせて画像の各ブロックを移動させてから予測する。動き補償予測は一般に１６×１６画素または８×８画素単位で行われ、動きベクトルもその単位で求められる。
【０００３】
以下、上記のような動き補償予測を行う従来の符号化装置について図面及びフローチャートに基づき説明する。図  １４は従来の動き補償予測を行う符号化装置の構成例を示すブロック図である。また図  １５は従来の動き補償予測を行う符号化装置を説明するフローチャートである。
【０００４】
入力された画像信号は、動き検出器１１１に与えられる一方、減算器１０１において動き補償予測器１１０から与えられる画像間予測信号が減算され、予測誤差となってＤＣＴ１０２に与えられる（ステップＳ１０３）。ＤＣＴ１０２は８×８画素単位で離散コサイン変換（ＤＣＴ）の変換処理を行い、得られた係数を量子化器１０３に与える（ステップＳ１０４）。量子化器１０３は所定の量子化ステップ幅で係数を量子化し、固定長の符号となった係数を可変長符号化器１０４と逆量子化器１０６に与える（ステップＳ１０５）。可変長符号化器１０４は２次元の８×８個の係数を１次元に変換し、係数をハフマン符号で符号化し、ハフマン符号列は多重化器１０５に与えられる（ステップＳ１０６）。
【０００５】
一方、逆量子化器１０６及び逆ＤＣＴ１０７ではＤＣＴ１０２及び量子化器１０３の逆処理が行われ、予測誤差を再生する（ステップＳ１０９及びステップＳ１１０）。得られた予測誤差には加算器１０８で予測信号が加算され参照画像となり（ステップＳ１１１）、画像メモリ１０９に蓄えられる（ステップＳ１１２）。画像メモリ１０９は参照画像を動き検出器１１１と動き補償予測器１１０に与える。
【０００６】
動き補償予測器１１０は、動き検出器１１１から与えられる動きベクトルに従って、画像メモリ１０９に蓄積されている画像をブロック毎に移動させ、画像間予測信号を得る（ステップＳ１０２）。動き補償予測により得られた画像間予測信号は、減算器１０１及び加算器１０８に与えられる。動き検出器１１１では、動き補償予測のブロック単位で画像メモリ１０９に蓄積されている参照画像をハーフペル単位で移動させて入力画像とブロックマッチングを取り、最もマッチングのとれた移動を動きベクトルとする（ステップＳ１０１）。得られた動きベクトルは動き補償予測器１１０の他に、動きベクトル符号化器１１２にも与えられる。動きベクトル符号化器１１２では、所定の手順で求められた予測動きベクトルと符号化対象となるブロックの動きベクトルを水平成分、垂直成分毎に比較し、その差分値を符号化する（ステップＳ１０７）。符号化された動きベクトルの符号列は多重化器１０５で、画像間予測誤差の符号列と多重化される（ステップＳ１０８）。
【０００７】
ここで、従来の動き補償予測における動きベクトルの検出手法について説明する。動きベクトルの検出手法にはブロックマッチング法がよく利用されている。このブロックマッチング法は、動き検出対象ブロック（Ｎ×Ｎ画素）を参照画像中の検出範囲内の画像と画素単位で全ての位置毎にマッチングをとり、マッチング評価関数を計算し、最もマッチングのとれた位置、すなわち最もマッチング評価関数の値が小さくなる位置を動きベクトルとする手法である。マッチング評価関数としては、例えばブロック内の全画素について、画素毎の画素値の差分の絶対値の和をとったもの（絶対値差分和）が使われる。
【０００８】
フルサーチ法の場合は、検出範囲内の全ての位置においてブロックマッチングが行われるため計算量が膨大になるという問題がある。このため、３ステップサーチ法（例えば「会議テレビ信号の動き補償フレーム間符号化」（信学技報ＩＥ８１−５４  １９８１−７）を参照）や階層化サーチ法（例えば、「階層画素情報を用いた動画像における動き量検出方式」電子情報通信学会論文誌Ｄ−ＩＩ  Ｖｏｌ．Ｊ７２−Ｄ−ＩＩ  Ｎｏ．３ｐｐ．３９５−４０３  １９８９年３月を参照）などの簡略化手法が提案されている。
【０００９】
３ステップサーチ法は、図  １６に示すように、検出範囲内の全ての位置をサーチする代わりに、まず第１段として、粗い間隔で３×３の９点のサーチを行い、最もマッチングのとれた位置を中心に、サーチする間隔を、第１段のときの半分にして第２段の検出を行う。同様の処理を複数段繰り返して、粗から密へ検出点の間隔を絞っていき動きベクトルを検出する方法である。±７画素の検出範囲の場合、３段で終了する。フルサーチ法の場合と比較すると処理量に大きく削減される。ただし、線画部分などの高解像度部分では、最初の方の段階での粗い検出位置とマッチングすべき位置がたまたま合っている場合を除いて、検出初期段階で誤った動きベクトルを検出する場合があり、実際の動き補償予測画像における予測誤差を大きくしてしまうという問題がある。
【００１０】
これに対して、階層化サーチ法は、低域通過型フィルタおよびサブサンプリングによって、水平・垂直方向について、各々１／２ずつ解像度を落した複数解像度の多階層画像を生成し、低解像度階層画像から動きベクトルを検出し、順次１つ上の階層での検出動きベクトルを参照しながら次階層の動きベクトル検出を行う方法で、各階層の動きベクトル検出はブロックマッチング法を用いる。
【００１１】
なお、以下の説明では、低解像度画像を下位の階層画像とし、高解像度画像を上位の階層画像と定義する。各階層での検出範囲の大きさは通常固定されていて、例えば水平・垂直±２画素の５×５＝２５点を検出位置とする。各階層の検出範囲の中心位置は、１つ上の階層での検出動きベクトルを２倍にした位置が使われる。
【００１２】
図  １７は、階層化サーチ法における検出範囲の中心位置の設定を説明する図である。下位階層において、始点１０を中心として検出範囲１１で動きベクトル検出を行った結果、動きベクトル１２が検出されたとする。上位階層では、動きベクトル１２を２倍した位置２０を中心として検出範囲２１で動きベクトルを検出する。
【００１３】
以下、上記のような階層化サーチを行う動き検出器１１１について図面及びフローチャートに基づき説明する。図  １８は、階層化サーチを行う従来の動き検出器の構成例を示すブロック図である。また図  １９及び図  ２０は階層化サーチを行う従来の動き検出器を説明するフローチャートである。
【００１４】
入力画像は階層レベル１サブサンプル器２１１に与えられる。階層レベル１サブサンプル器２１１は入力された画像を水平方向及び垂直方向に１／２にサブサンプルして階層レベル１の入力画像を作成し、画像メモリ２１２及び階層レベル０サブサンプル器２２１に与える。参照画像は階層レベル１サブサンプル器２１４に与えられる。階層レベル１サブサンプル器２１４は入力された画像を水平方向及び垂直方向に１／２にサブサンプルして階層レベル１の参照画像を作成し、画像メモリ２１３及び階層レベル０サブサンプル器２２４に与える（ステップＳ２０１）。
【００１５】
階層レベル０サブサンプル器２２１は入力された画像を水平方向及び垂直方向に１／２にサブサンプルして階層レベル０の入力画像を作成し、画像メモリ２２２に与える。階層レベル０サブサンプル器２２４は入力された画像を水平方向及び垂直方向に１／２にサブサンプルして階層レベル０の参照画像を作成し、画像メモリ２２３に与える（ステップＳ２０２）。階層レベル０動きベクトル決定器２２０は、検出開始点を（０，０）、検出範囲を±１、マッチングブロックサイズを４×４に設定して（ステップＳ２０３〜ステップ２０６）、画像メモリ２２２内の階層レベル０の入力画像と画像メモリ２２３内の階層レベル０の参照画像から絶対値差分和が最小となる位置の階層レベル０動きベクトルＶ（０）を求め（ステップＳ２０７）、Ｖ（０）を階層レベル１動きベクトル決定器２１０に与え、次の階層レベルに進む（ステップＳ２０８）。
【００１６】
階層レベル１動きベクトル決定器２１０は、検出開始点をＶ（０）を２倍にスケーリングした位置、検出範囲を±１、マッチングブロックサイズを８×８に設定して（ステップＳ２０４〜ステップ２０６）、画像メモリ２１２内の階層レベル１の入力画像と画像メモリ２１３内の階層レベル１の参照画像から絶対値差分和が最小となる位置の階層レベル１動きベクトルＶ（１）を求め（ステップＳ２０７）、Ｖ（０）を階層レベル２動きベクトル決定器２００に与え、次の階層レベルに進む（ステップＳ２０８）。階層レベル２動きベクトル決定器２００は、検出開始点をＶ（１）を２倍にスケーリングした位置、検出範囲を±１、マッチングブロックサイズを１６×１６に設定して（ステップＳ２０４〜ステップ２０６）、入力画像と参照画像から絶対値差分和が最小となる位置の階層レベル１動きベクトルＶ（２）を求め（ステップＳ２０７）、Ｖ（２）を動きベクトルとして出力する。ここで、動きベクトルの決定（ステップＳ２０７）について説明する。
【００１７】
各階層レベルの動きベクトル検出範囲内でブロックマッチング（ステップＳ２５１）をして、ブロックマッチングの評価値を評価し（ステップＳ２５２）、その評価値が最小であればそれを動きベクトルとし（ステップＳ２５３）、そうでなければ次の検出点についてブロックマッチング（ステップＳ２５１）を行う。
【００１８】
なお、階層化サーチ法には、各階層での動き検出対象ブロックの大きさを、階層によらず一定の画素数とする方法（従って低解像度階層ほど実際の画像上でのブロックサイズは大きくなる）と、各階層のサブサンプル比率に応じて、動き検出対象ブロックの大きさを変え、実際上の画像において同じ領域の動きベクトル検出を行う方法とがある。
【００１９】
このような階層化サーチ法では、低域通過型フィルタおよびサブサンプリングによって多階層画像を生成して各階層の動き検出を行うため、３ステップ法で動きベクトルを誤検出するような高解像度の部分に対しても、動きベクトルの誤検出を回避することができ、誤検出の場合の、実際の動き補償予測画像における予測誤差も３ステップサーチ法に比べて大きくない。
【００２０】
表１は動きベクトルの検出範囲が±７である場合のフルサーチ法におけるマッチングブロックサイズ、検出範囲、検出点数、差分演算回数を示している。表２は動きベクトルの検出範囲が±７である場合の３ステップサーチ法における各ステップでのマッチングブロックサイズ、検出範囲、検出点数、差分演算回数を示している。表３は、動きベクトルの検出範囲が±７である場合の階層化サーチ法における各階層でのマッチングブロックサイズ、検出範囲、検出点数、差分演算回数を示している。表１、表２、及び表３から３ステップサーチ法における差分演算回数はフルサーチ法における差分演算回数と比較して１／９に削減されている。また階層化サーチ法における差分演算回数はフルサーチ法における差分演算回数と比較して約１／２１に削減されている。ただし、階層化サーチ法では階層レベル１及び階層レベル０の画像メモリが必要となる。
【００２１】
【表１】
2004260251.tif 000003
【００２２】
【表２】
2004260251.tif 000004
【００２３】
【表３】
2004260251.tif 000005
【００２４】
【特許文献１】
特開平７−１５４８０１号公報
【００２５】
【非特許文献１】
「会議テレビ信号の動き補償フレーム間符号化」（信学技報ＩＥ８１−５４  １９８１−７）
【００２６】
【非特許文献２】
「階層画素情報を用いた動画像における動き量検出方式」（電子情報通信学会論文誌Ｄ−ＩＩ  Ｖｏｌ．Ｊ７２−Ｄ−ＩＩ  Ｎｏ．３ｐｐ．３９５−４０３  １９８９年３月）
【００２７】
【発明が解決しようとする課題】
フルサーチ法はブロックマッチングを用いる動きベクトル検出としては最高の精度を得ることができる。しかし、フルサーチ法では処理量は膨大であるという問題がある。階層化サーチ法はフルサーチよりも検出精度は劣るが、検出範囲内を均一に動きベクトルを検出する特徴を有している。しかし、階層化サーチ法では、高周波成分で各階層レベルにおける入力画像と参照画像のための画像メモリが必要となる問題がある。また、３ステップサーチ法では画像メモリは必要ないが、線画部分などの高解像度部分では、最初のステップで誤った動きベクトルを検出した場合には正しい動きベクトルが得られない問題がある。
【００２８】
本発明は以上の点を鑑みてなされたもので、動きベクトルの検出範囲の中心点からの距離に応じてブロックマッチングに用いる画素を間引くことで、演算量を削減し、余計な画像メモリを必要としない精度の良い動きベクトル検出装置びプログラムを提供することを目的とする。
【００２９】
【課題を解決するための手段】
そこで上記課題を解決するために本発明は、下記の装置及びプログラムを提供するものである。
（１）  入力画像を所定数の画素単位毎にブロック化し、前記入力画像において各ブロックを順次動き検出対象ブロックとして設定し、参照画像において前記動き検出対象ブロックに応じて順次検出範囲を設定し、前記各動き検出対象ブロック内の画素と前記各検出範囲内の画素とを比較して、ブロックマッチングにより前記各動き検出対象ブロック毎に動きベクトルを求める動画像の動きベクトル検出装置において、
前記検出範囲内の画素の前記検出範囲の中心からの距離に応じて、前記検出範囲内の画素に対してブロックマッチングにおける比較対象となる前記動き検出対象ブロック内の画素の間引き率を設定する間引き率設定手段と、
前記設定された間引き率に応じて、ブロックマッチングに用いる前記動き検出対象ブロック内の画素及び前記検出範囲内の画素を間引く間引き手段と、
を設けたことを特徴とする動きベクトル検出装置。
（２）  上記（１）記載の動きベクトル検出装置において、
動き検出対象ブロックに設定されたブロックに隣接する、既に動きベクトルが求められているブロックの動きベクトルを用いて、予め定められている所定方法に従って求められる予測動きベクトルに応じて、前記動き検出対象ブロックに対して設定される前記検出範囲の中心位置を移動させる検出範囲移動手段を設けたことを特徴とする動きベクトル検出装置。
（３）  上記（１）記載の動きベクトル検出装置において、
前記間引き率設定手段は、動き検出対象ブロックに設定されたブロックに隣接する、既に動きベクトルが求められているブロックの動きベクトル、及び前記検出範囲の中心からの距離に応じて、前記間引き率を設定するものであることを特徴とする動きベクトル検出装置。
（４）  動画像である入力画像を所定数の画素単位毎にブロック化し、前記入力画像において各ブロックを順次動き検出対象ブロックとして設定し、参照画像において前記動き検出対象ブロックに応じて順次検出範囲を設定し、前記各動き検出対象ブロック内の画素と前記各検出範囲内の画素とを比較して、ブロックマッチングにより前記各動き検出対象ブロック毎に動きベクトルを求める動作をコンピュータに行わせる動きベクトル検出プログラムにおいて、
前記検出範囲内の画素の前記検出範囲の中心からの距離に応じて、前記検出範囲内の画素に対してブロックマッチングにおける比較対象となる前記動き検出対象ブロック内の画素の間引き率を設定する間引き率設定手機能と、
前記設定された間引き率に応じて、ブロックマッチングに用いる前記動き検出対象ブロック内の画素及び前記検出範囲内の画素を間引く間引き機能と、
をコンピュータに実行させることを特徴とする動きベクトル検出プログラム。
【００３０】
【発明の実施の形態】
（第１実施例）
以下、本発明の第１実施例について図面及びフローチャートに基づき説明する。図  １は本発明に係る動きベクトル検出器の第１実施例を用いた符号化装置の一実施例を示すブロック図である。図  １は、従来の動きベクトル検出器を用いた符号化装置の例である図  １４と同じ構成である。ただし、動き検出器１１１の動作が従来例と異なる。図  １で減算器１０１、ＤＣＴ１０２、量子化器１０３、可変長符号化器１０４、多重化器１０５、逆量子化器１０６、逆ＤＣＴ１０７、加算器１０８、画像メモリ１０９、動き補償予測器１１０、及び動きベクトル符号化器の動作は従来例と同じである。
【００３１】
図  ２は本発明の第１実施例を用いた符号化装置の一実施例を説明するフローチャートである。図  ２は、従来の動きベクトル検出器を用いた符号化装置を説明するフローチャートである図  １５と同じ手順である。ただし、手順Ｓ１０１の動作が従来例と異なる。図  ２で手順Ｓ１０２、手順Ｓ１０３、手順Ｓ１０４、手順Ｓ１０５、手順Ｓ１０６、手順Ｓ１０７、手順Ｓ１０８、手順Ｓ１０９、手順Ｓ１１０、手順Ｓ１１１、及び手順Ｓ１１２は従来例と同じである。
【００３２】
以下、本実施例における動きベクトル検出器の従来例との違いを図面及びフローチャートに基づき説明する。図  ３は動きベクトル検出器の第１実施例を示すブロック図である。図  ４は動きベクトル検出器の第１実施例を説明するフローチャートである。
【００３３】
ブロックマッチング設定器３０１はあらかじめ決められた（ステップＳ３０１）方法に従って動きベクトルの検出範囲の中心からの距離に応じてブロックマッチングに用いる画素の間引き率を設定し（ステップＳ３０２）、その情報を動きベクトル決定器３００、間引き器３０２、３０３に与える。間引き器３０２は与えられた間引き率に従って入力画像を間引き、間引いた入力画像を動きベクトル決定器３００に与える（ステップＳ３０３）。間引き器３０３は与えられた間引き率に従って参照画像を間引き、間引いた参照画像を動きベクトル決定器３００に与える（ステップＳ３０４）。
【００３４】
動きベクトル決定器３００は与えられた間引き率に従って、ブロックマッチングを行い（ステップＳ３０５）、ブロックマッチングの評価値を評価し（ステップＳ３０６）、その評価値が最小であればそれを動きベクトルとし（ステップＳ３０７）、そうでなければ次の検出点に移る。動きベクトル検出範囲内のブロックマッチングが全て終了すると、動きベクトルを出力する。
【００３５】
本実施例における動きベクトルの検出範囲の中心からの距離に応じてブロックマッチングに用いる画素の間引き率を設定する方法について図  ５を用いて説明する。
【００３６】
動きベクトルは１６×１６画素のブロック単位で求め、動きベクトルの検出範囲は水平方向、垂直方向に±７画素であるとする。ブロックマッチングに用いる画素の間引き率を検出範囲の中心からの距離に応じて３段階のマッチングレベルに分けるとする。図  ５において検出中心位置５０は動きベクトルを（０，０）とした位置であるとし、検出中心位置５０を中心として水平方向、垂直方向に±２画素の範囲を第１の検出範囲５１とする（マッチングレベル１）。第１の検出範囲５１から検出中心位置５０を中心として水平方向、垂直方向に±４画素の範囲を第２の検出範囲５２とする（マッチングレベル２）。第２の検出範囲５２から検出中心位置５０を中心として水平方向、垂直方向に±７画素の範囲を第３の検出範囲５３とする（マッチングレベル３）。第１の検出範囲５１、第２の検出範囲５２、第３の検出範囲５３のそれぞれにブロックマッチングに用いる画素の間引き率を割り当てる。
【００３７】
第１の検出範囲５１の中では図  ６（Ａ）で示されるように、動きベクトル検出の対象となるブロックの全画素をブロックマッチングに用いる。マッチング評価関数Ｆ（ｘ，ｙ）は式１で表すことができる。ここでｘ、ｙは検出位置の水平位置、垂直位置であり、ＣｕｒＰｉｘｅｌ（ｉ，ｊ）は入力画像の動きベクトル検出の対象となるブロック内の画素であり、ＲｅｆＰｉｘｅｌ（ｉ，ｊ）は検出位置における参照画像のブロック内の画素である。
【００３８】
【数１】
2004260251.tif 000006
第２の検出範囲５２の中では図  ６（Ｂ）で示されるように、動きベクトル検出の対象となるブロックに対して水平方向、垂直方向にそれぞれ１／２間引いた画素をブロックマッチングに用いる。マッチング評価関数Ｆ（ｘ，ｙ）は式２で表すことができる。
【００３９】
【数２】
2004260251.tif 000007
第３の検出範囲５３の中では図  ６（Ｃ）で示されるように、動きベクトル検出の対象となるブロックに対して水平方向、垂直方向にそれぞれ１／４間引いた画素をブロックマッチングに用いる。マッチング評価関数Ｆ（ｘ，ｙ）は式３で表すことができる。
【００４０】
【数３】
2004260251.tif 000008
以上のようにして求めたマッチング評価関数Ｆ（ｘ，ｙ）の値が最小となる位置を動きベクトルとする。
【００４１】
検出範囲の中心からの距離が大きくなるに従って、ブロックマッチングに用いる画素の間引き率を大きくするのは、人間の目の視覚特性に基づいた処理である。一般的に人間の目は動きの早いものに対しては認知力が低下するという特性があり、この特性を利用した処理である。認知力の高い小さな動きを高精度で検出し、認知力の低い大きな動きについては精度を落として検出することを特徴としている。
【００４２】
表４は動きベクトルの検出範囲が±７である本実施例における各マッチングレベルにおけるブロックマッチングブロックサイズ、検出範囲、検出点数、差分演算回数を示している。表１、表２、表３と比較すると、本実施例の差分演算回数はフルサーチ法における差分演算回数と比較して約１／５に削減されている。検出点数がフルサーチと同じ２２５であるため検出した動きベクトルの精度は高い。３ステップサーチ法と比較すると差分演算回数は１．６８倍になっているが、３ステップサーチ法のように検出点数を減らしていないため、線画部分などの高解像度部分において誤った動きベクトルを検出する確率は極めて低く、高精度な動きベクトルを得ることができる。階層サーチ法と比較すると差分演算回数は約４倍になっているが、階層化サーチ法のように各階層レベルにおける入力画像と参照画像のための画像メモリが不要である。
【００４３】
【表４】
2004260251.tif 000009
（第２実施例）
本発明の第２実施例について図面及びフローチャートに基づき説明する。図  ７は本発明に係る動きベクトル検出器の第２実施例を用いた符号化装置の一実施例を示すブロック図である。図  ７は、図  １に示す符号化装置と同じ構成である。ただし、動き検出器１１１の動作が図  １に示す符号化装置と異なる。図  ７で、減算器１０１、ＤＣＴ１０２、量子化器１０３、可変長符号化器１０４、多重化器１０５、逆量子化器１０６、逆ＤＣＴ１０７、加算器１０８、画像メモリ１０９、動き補償予測器１１０、及び動きベクトル符号化器１１２の動作は図  １に示す符号化装置と同じである。
【００４４】
以下、第２実施例における動きベクトル検出器の第１実施例との違いを図面及びフローチャートに基づき説明する。図  ８は動きベクトル検出器の第２実施例を示すブロック図である。図  ８は、第１実施例を示す図  ３と比較して、動きベクトル予測器３０４が増えている。また、間引き設定器３０１、動きベクトル決定器３００の動作が本発明の第１実施例と異なる。図  ８で、間引き器３０２、３０３の動作は本発明の第１実施例と同じである。図  ９は動きベクトル検出器の第２実施例を説明するフローチャートである。図  ９は本発明の第１実施例を説明した図  ４と比較して、手順Ｓ３００が増えている。また、手順Ｓ３０１が本発明の第一の実施例と異なる。
【００４５】
動きベクトル予測器３０４は予測動きベクトルを所定の手順で求め（ステップＳ３００）、間引き設定器３０１に与える。間引き設定器３０１は与えられたは与えられた予測動きベクトルに従って、動きベクトルの検出範囲の中心からの距離に応じたブロックマッチングに用いる画素の間引き率を設定する（ステップＳ３０１）。動きベクトルの検出範囲内のブロックマッチングが終了すると、動きベクトル決定器３００は動きベクトルを動きベクトル予測器３０４に与え、動きベクトルを出力する。
【００４６】
予測動きベクトルを求める手順について図  １０を用いて説明する。図  １０において、ブロックＸの予測動きベクトルであるＭＶｐ（Ｘ）を求める。ブロックＸの隣接ブロックＡ、Ｂ、Ｃのそれぞれの動きベクトルをＭＶ（Ａ）、ＭＶ（Ｂ）、ＭＶ（Ｃ）とする。最も単純な方法として、左隣のブロックの動きベクトルを用いてＭＶｐ（Ｘ）＝ＭＶ（Ｃ）とする方法がある。これらはＭＰＥＧ−２などで用いられている方法である。またＭＶ（Ａ）、ＭＶ（Ｂ）、ＭＶ（Ｃ）の水平方向、垂直方向それぞれの値の中央値をとる方法もある。この方法はＭＰＥＧ−４で用いられている方法であり、ＭＶ（Ａ）＝（０，２）、ＭＶ（Ｂ）＝（１、−１）、ＭＶ（Ｃ）＝（３，３）であれば、ＭＶｐ（Ｘ）＝（１，２）となる。
【００４７】
本実施例における動きベクトルの検出範囲の中心からの距離に応じてブロックマッチングに用いる画素の間引き率を設定する方法について図  ５と図  １１を用いて説明する。予測動きベクトルＭＶｐ（ｘ，ｙ）に応じて、第１の検出範囲であるＲａｎｇｅ１（ｘ，ｙ）及び第２の検出範囲であるＲａｎｇｅ２（ｘ，ｙ）が式４に従って変化する。
【００４８】
【数４】
2004260251.tif 000010
例えば、ＭＶｐが（０，０）であれば、検索範囲の中心位置５０は（０，０）となり、間引き率の設定範囲は第一の実施例と同じ図  ５となる。ＭＶｐが（３，３）であれば、検索範囲の検出中心位置５０は（０，１）となり、間引き率の設定範囲は図  １１となる。図  １１において検出中心位置５０を中心として水平方向、垂直方向に±２画素の範囲を第１の検出範囲５１とする（マッチングレベル１）。第１の検出範囲５１から検出中心位置５０を中心として水平方向、垂直方向に±４画素の範囲を第２の検出範囲５２とする（マッチングレベル２）。第２の検出範囲５２の外側を第３の検出範囲５３とする（マッチングレベル３）。それぞれのマッチングレベルは表４で示されている。
【００４９】
本実施例では、間引き率の設定範囲の計算に平行移動の例をあげたが、これらに拡大や縮小の計算を加えても良い。例えば、動きの小さな入力画像に対しては、図  １２のように、検出中心位置５０を（０，０）とし、水平方向、垂直方向に±１画素の範囲を第１の検出範囲５１（マッチングレベル１）とし、第１の検出範囲５１から検出中心位置５０を中心として水平方向、垂直方向に±２画素の範囲を第２の検出範囲５２（マッチングレベル２）とし、第２の検出範囲５２の外側を第３の検出範囲５３（マッチングレベル３）として、マッチングレベル１、マッチングレベル２の範囲を小さくすることで演算量をさらに減らすことが可能となる。
【００５０】
この場合の各マッチングレベルにおけるブロックマッチングブロックサイズ、検出範囲、検出点数、差分演算回数を表５に示す。この場合には差分演算回数は３ステップサーチ法とほぼ同じになる。このように入力画像の動きの大小に合わせて間引き率の設定を変化させることで、演算量をより小さくすることが可能である。
【００５１】
【表５】
2004260251.tif 000011
また、ＭＶｐを利用した間引き率設定方法において、動きベクトルの検出範囲の中心をＭＶｐとして移動させる方法もある。例えば、ＭＶｐが（０，１）である場合に、動きベクトルの検出範囲の中心を（０，１）に移動させる。この結果は図  １１と同じになる。動きが大きな入力画像に対しても、予測動きベクトルが正しく予測できる限りにおいて、動きベクトルの検出範囲の中心をＭＶｐに合わせて移動させることによって、動きベクトルの検出範囲の広い、演算量の少ない、且つ精度の高い動きベクトルを検出することができる。
【００５２】
次に、隣接するブロックの動きベクトルに応じてブロック内の画素を間引く率を設定する方法について説明する。本実施例においては隣接するブロックの動きベクトルとしてＭＶｐを用いる。ＭＶｐが（０，３）であるような水平方向に移動するような動きに対しては図  １３のような水平重視型の間引き率を設定する。検出中心位置５０を（２，０）とし、水平方向±３画素、垂直方向に±１画素の範囲を第１の検出範囲５１（マッチングレベル１）とし、第１の検出範囲５１から検出中心位置５０を中心として水平方向±４画素、垂直方向に±２画素の範囲を第２の検出範囲５２（マッチングレベル２）とし、第２の検出範囲５２の外側を第３の検出範囲５３（マッチングレベル３）とする。
【００５３】
ＭＶｐが（３，０）であるような垂直方向に移動するような動きに対しては図  １３のような垂直重視型の間引き率を設定する。検出中心位置５０を（０，２）とし、水平方向±１画素、垂直方向に±３画素の範囲を第１の検出範囲５１（マッチングレベル１）とし、第１の検出範囲５１から検出中心位置５０を中心として水平方向±２画素、垂直方向に±４画素の範囲を第２の検出範囲５２（マッチングレベル２）とし、第２の検出範囲５２の外側を第３の検出範囲５３（マッチングレベル３）とする。このようにすることで、動きベクトルの検出範囲の広い、演算量の少ない、且つ精度の高い動きベクトルを検出することができる。
【００５４】
即ち、隣接するブロックの動きベクトルに応じてブロック内の画素を間引く率を設定する場合に、水平方向の移動であると判断される場合には垂直方向の画素を間引き率を大きくして垂直方向の移動であると判断される場合には水平方向の画素を間引く率を大きくするようにする。
【００５５】
なお、本発明は、上記した動きベクトル検出器の機能をコンピュータに実現させるためのプログラムを含むものである。このプログラムは、記録媒体から読みとられてコンピュータに取り込まれてもよいし、通信ネットワーク等を介して伝送されてコンピュータに取り込まれてもよい。
【００５６】
【発明の効果】
本発明は、検出範囲の中心からの距離に応じてブロックマッチングに用いる画素の間引き率を変化させることで、演算量を減らし、余計な画像メモリを必要とせず、動きの小さな動画像に対しては特に精度の高い動きベクトルを検出することができる。
【００５７】
また、予測動きベクトルに応じて動きベクトルの検出範囲の中心位置を移動させるようにした場合には、動きの大きな動画像に対しても、演算量を減らし、余計な画像メモリを必要とせず、精度の高い動きベクトルを検出することができる。
【００５８】
また、隣接するブロックの動きベクトルに応じてブロックマッチングに用いる画素の間引き率を変化させるようにした場合には、さらに演算量を減らし、余計な画像メモリを必要とせず、精度の高い動きベクトルを検出することができる。
【図面の簡単な説明】
【図１】本発明に係る動きベクトル検出器の第１実施例を用いた符号化装置の一実施例を示すブロック図である。
【図２】本発明の第１実施例を用いた符号化装置の一実施例を説明するフローチャートである。
【図３】動きベクトル検出器の第１実施例を示すブロック図である。
【図４】動きベクトル検出器の第１実施例を説明するフローチャートである。
【図５】間引き率の設定範囲を示す図である。
【図６】ブロックマッチングに用いる画素の例を示す図である。
【図７】本発明に係る動きベクトル検出器の第２実施例を用いた符号化装置の一実施例を示すブロック図である。
【図８】動きベクトル検出器の第２実施例を示すブロック図である。
【図９】動きベクトル検出器の第２実施例を説明するフローチャートである。
【図１０】予測動きベクトルを求める手順を示す図である。
【図１１】間引き率の設定範囲を示す図である。
【図１２】間引き率の設定範囲を示す図である。
【図１３】間引き率の設定範囲を示す図である。
【図１４】従来の動き補償予測を行う符号化装置の構成例を示すブロック図である。
【図１５】従来の動き補償予測を行う符号化装置を説明するフローチャートである。
【図１６】３ステップサーチ法を説明するための図である。
【図１７】階層化サーチ法を説明するための図である。
【図１８】階層化サーチを行う従来の動き検出器の構成例を示すブロック図である。
【図１９】階層化サーチを行う従来の動き検出器を説明するフローチャートである。
【図２０】階層化サーチを行う従来の動き検出器を説明するフローチャートである。
【図１】
2004260251.tif 000012
【図２】
2004260251.tif 000013
【図３】
2004260251.tif 000014
【図４】
2004260251.tif 000015
【図５】
2004260251.tif 000016
【図６】
2004260251.tif 000017
【図７】
2004260251.tif 000018
【図８】
2004260251.tif 000019
【図９】
2004260251.tif 000020
【図１０】
2004260251.tif 000021
【図１１】
2004260251.tif 000022
【図１２】
2004260251.tif 000023
【図１３】
2004260251.tif 000024
【図１４】
2004260251.tif 000025
【図１５】
2004260251.tif 000026
【図１６】
2004260251.tif 000027
【図１７】
2004260251.tif 000028
【図１８】
2004260251.tif 000029
【図１９】
2004260251.tif 000030
【図２０】
2004260251.tif 000031