(57)【要約】【課題】探索精度の低下を最小限に抑えて高速に動きベクトルを探索できる装置及び方法を提供する。【解決手段】初めに粗く探索をおこない、その探索結果を中心に細かい探索をおこなう多段探索において、１段目探索において隣接する複数のブロックをまとめて探索をおこない、探索の単位となった複数ブロックにつき一つの動きベクトルを検出する。２段目探索では、１段目段宅の結果を中心に１ブロックごとの探索をおこない、各ブロックの動きベクトルを求める。【選択図】    図１
2004229150.tif 000002
【特許請求の範囲】
【請求項１】
動画像の符号化における動きベクトルを探索する装置において、
対象画像および参照画像の縦方向及び横方向を縮小して縮小対象画像および縮小参照画像をそれぞれ生成する画像縮小手段と、
前記縮小対象画像および縮小参照画像に基づいて、隣接する複数個のブロックからなる探索単位で第１動きベクトルを探索する第１探索手段と、
前記第１動きベクトルにより決定される探索範囲内で、前記縮小前の画像解像度により１ブロック単位で第２動きベクトルを探索し前記動きベクトルを決定する第２探索手段と、
を有することを特徴とする動きベクトル探索装置。
【請求項２】
前記第１探索手段は、さらに、
前記動画像の動きの複雑度を判定する動き複雑度判定手段と、
前記動き複雑度に応じて、前記探索単位の大きさを変化させる探索単位決定手段と、
を有することを特徴とする請求項１記載の動きベクトル探索装置。
【請求項３】
動画像の符号化における動きベクトルを探索する方法において、
対象画像および参照画像の縦方向及び横方向を縮小して縮小対象画像および縮小参照画像をそれぞれ生成し、
前記縮小対象画像および縮小参照画像に基づいて、隣接する複数個のブロックからなる探索単位で第１動きベクトルを探索し、
前記第１動きベクトルにより決定される探索範囲内で、前記縮小前の画像解像度により１ブロック単位で第２動きベクトルを探索することで前記動きベクトルを決定する、
ことを特徴とする動きベクトル探索方法。
【請求項４】
前記探索単位の大きさは、前記動画像の動きの複雑度に応じてを変化させることを特徴とする請求項３記載の動きベクトル探索方法。
【請求項５】
動画像の符号化における動きベクトル探索を実行するコンピュータシステムにおいて、
対象画像データを格納する対象画像バッファと、
参照画像を格納する参照画像バッファと、
動画像の符号化における動きベクトル探索をコンピュータに実行させるための命令からなるプログラムを格納するメモリと、
前記プログラムを実行するプログラム制御プロセッサと、
を有し、前記プログラムは、少なくとも、
前記対象画像および前記参照画像を縮小し、縮小対象画像および縮小参照画像をそれぞれ生成する画像縮小部と、
前記縮小対象画像および縮小参照画像に基づいて第１動きベクトルを探索する際に隣接する複数のブロックを探索単位として一度に探索する第１探索部と、
前記第１動きベクトルにより決定される位置の探索範囲内で、前記縮小前の画像解像度により１ブロックごとに第２動きベクトルを探索して前記動きベクトルを決定する第２探索部と、
からなることを特徴とするコンピュータシステム。
【請求項６】
前記探索単位のブロック数は、前記動画像の動きの複雑さに応じて増減させることを特徴とする請求項５記載のコンピュータシステム。
【請求項７】
動画像の符号化における動きベクトル探索をコンピュータに実行させるための命令からなるコンピュータプログラムにおいて、
対象画像および参照画像の縦方向及び横方向を縮小して縮小対象画像および縮小参照画像をそれぞれ生成するステップと、
前記縮小対象画像および縮小参照画像に基づいて、隣接する複数個のブロックからなる探索単位で第１動きベクトルを探索する第１探索ステップと、
前記第１動きベクトルにより決定される探索範囲内で、前記縮小前の画像解像度により１ブロック単位で第２動きベクトルを探索することで前記動きベクトルを決定する第２探索ステップと、
を有することを特徴とするコンピュータプログラム。
【請求項８】
前記探索単位のブロック数は、前記動画像の動きの複雑さに応じて増減させることを特徴とする請求項７記載のコンピュータプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は動き補償予測符号化技術に係り、特に多段探索法で用いられる動きベクトル探索方法および装置ならびにコンピュータシステムに関する。
【０００２】
【従来の技術】
動画像信号を記録あるいは伝送する際の圧縮符号化では、符号化効率を高めるために画像フレーム間の相関を利用した符号化方法が一般に用いられる。画像フレーム間の相関を利用する符号化方式は動き補償予測符号化と呼ばれ、ＭＰＥＧ  （Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）２などで採用されている。
【０００３】
動き補償予測符号化では、フレーム間の映像の動きの情報（動きベクトル）と、動きベクトルによって生成される予測画像と符号化中のフレームとの差分画像（予測誤差）を符号化する。画像フレーム間の相関が大きければ、予測誤差が小さくなり、符号化する情報量を小さくでき圧縮率を向上させることができる。動き補償予測符号化では、一般に、フレームを１６×１６画素などの一定サイズのブロックに分割し、分割したブロックごとに動きベクトルを割り当てる。
【０００４】
具体的には、すでに符号化が完了しているフレーム（参照フレーム）の中から、ブロックごとに相関が最も大きくなる場所を探し、そのブロック間の差分を求め、符号化する。相関が大きくなる場所を探す処理を動きベクトル探索という。相関の大小は、参照フレームと符号化中フレームとのブロック内の各画素の差異を総和することで評価できる。
【０００５】
指定された探索範囲のすべての点を単純に探索し、相関の大きさを調べれば最適な動きベクトルが得られるが、この方法では演算量が極めて大きくなり現実的でない。演算量を削減するために、初めに粗く第１段の探索をおこない、その探索結果を中心にして細かい第２段の探索を行うのが一般的である。このような方法は多段探索法と呼ばれ、例えば非特許文献１などに開示されている。以下、多段探索法について簡単に説明する。
【０００６】
図７（Ａ）は、一般的な多段探索法を説明するための画素配列を示す模式図であり、（Ｂ）は第２段の探索の様子を示すシーケンス図である。例えば、初めに第１段の探索として２画素精度探索（図７（Ａ）の”１”でラベルされた位置の探索）を実行し、そのなかで最も相関が大きくなる位置を決定する。  続いて、第１段の探索結果である位置を中心に、第２段の探索として１画素精度探索（図７（Ａ）の”２”でラベルされた位置の探索）を実行し、その中で最も相関が大きくなる位置を最終的な動きベクトルとする。
【０００７】
通常、第１段の動きベクトル探索は、フレームをサブサンプリングして解像度を下げたフレームデータを用いる。例えば、フレームデータを縦横ともに半分にして第１段の動きベクトル探索をおこない、その探索結果の周囲を探索範囲として本来の解像度で第２段の探索を実行し、最終的な動きベクトルを求める。たとえば図７（Ｂ）に示すように、第２段の探索範囲が縦および横方向±１画素の範囲である場合には、探索範囲内のすべての位置（図７（Ｂ）の（ａ）〜（ｉ））でマッチングが行われる。
【０００８】
非特許文献２には、このように解像度を下げて動きベクトルを探索する方法の一例が開示されている。非特許文献２に記載された方法では、解像度を下げて縮小した画像による動きベクトル探索と本来の解像度の画像による動きベクトル探索の２種類の探索を行い、予測誤差が小さくなる探索結果を採用する。
【０００９】
たとえば、解像度を下げた探索では、まず符号化対象画像と参照画像とを共に水平方向のみＮ：１にサブサンプリングし、サブサンプリングされた画像上で動きベクトル探索をおこなう。このときサブサンプリングされた画像上ではブロックのサイズも縮小されるが、マッチング単位は本来の解像度のブロックサイズと同一にしている。つまり、本来の解像度でのブロックサイズが水平方向１６画素、垂直方向１６画素の場合、水平方向のみサブサンプリングしたことでブロックサイズは水平方向１６／Ｎ画素、垂直方向１６画素となるが、探索は水平方向１６画素、垂直方向１６画素のままでおこなう。したがって水平方向に隣接するＮ個のブロックを一度に探索することになる。これにより、もし解像度を下げた探索の探索結果が採用された場合には、隣接するＮ個のブロックで同じ動きベクトルを持つことになる。また、このときの動きベクトルの精度はサブサンプリングされた画像サイズに依存する。例えば水平方向２：１にサブサンプリングして探索をおこない、この探索結果が最終的な動きベクトルとして採用された場合、本来の解像度上で考えると１画素飛ばしの探索をおこなったことと等価な探索精度となる。
【００１０】
また、特許文献１（特開平１０−１９１３４７号公報）に開示された動き検出方法では、２つのブロックをまとめたセミグローバルブロックを求めて、それに隣接するブロックの動きベクトルを検出することでセミグローバルブロックの大まかな動きを検出する。そして、検出された大まかな位置をサーチ対象としてブロックごとの動きベクトルを検出する。同様に、特許文献２（特開平１０−１３８３５号公報）に開示された動き検出方法でも、複数ブロックのうちの１ブロックを代表させて探索している。
【００１１】
【非特許文献１】
Ｒｅｎｘｉａｎｇ  Ｌｉ  等、“Ａ  ｎｅｗ  ｔｈｒｅｅ−ｓｔｅｐ  ｓｅａｒｃｈ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｂｌｏｃｋ  ｍｏｔｉｏｎ  ｅｓｔｉｍａｔｉｏｎ”、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｉｒｃｕｉｔｓ  ａｎｄ  Ｓｙｓｔｅｍｓ  ｆｏｒ  Ｖｉｄｅｏ  Ｔｅｃｈｎｏｌｏｇｙ，  Ｖｏｌ．４，  Ｎｏ．４，  Ａｕｇｕｓｔ，  １９９４，  ｐｐ．４３８−４４１
【非特許文献２】
神田等  “ダウンサンプリングによる動きベクトルの広範囲探索”、  映像メディア処理シンポジウム（ＩＭＰＳ９６），  １９９６，  ｐｐ．９９−１００
【特許文献１】
特開平１０−１９１３４７号公報（要約、００２９〜００３１）。
【特許文献２】
特開平１０−１３８３５号公報（要約、００１８）。
【００１２】
【発明が解決しようとする課題】
しかしながら、非特許文献２で開示されている方法では、２種類の動きベクトル探索法を用いて探索を行っているために演算量が増加するという問題がある。
【００１３】
また、解像度を下げた探索の探索結果が採用された場合、隣接する複数のブロックで同一の動きベクトルとなり、かつ、粗い探索による探索結果がそのまま最終的な動きベクトルとなる。このために、画像中の細かい動きに対応することができなくなり探索精度が低下するという問題も生じる。
【００１４】
また、特許文献１に開示された方法では、セミグローバルブロックの動きを隣接するブロックの動きで代表させているために、セミグローバルブロック自体の動きを検出していない。特許文献２の方法も同様の代表探索を採用している。このために検索精度が大きく低下する場合が生じうる。
【００１５】
本発明の目的は、動きベクトルを高速に探索できる新規な動きベクトル探索方法および装置ならびにコンピュータシステムを提供することにある。
【００１６】
本発明の他の目的は、探索精度の低下を最小限に抑えて高速に動きベクトルを探索できる動きベクトル探索方法および装置ならびにコンピュータシステムを提供することにある。
【００１７】
【課題を解決するための手段】
本発明による動きベクトル探索装置および方法は、対象画像および参照画像の縦方向及び横方向を縮小して縮小対象画像および縮小参照画像をそれぞれ生成し、これら縮小対象画像および縮小参照画像に基づいて、隣接する複数個のブロックからなる探索単位で第１動きベクトルを探索する。検出された第１動きベクトルにより決定される探索範囲内で、縮小前の画像解像度により１ブロック単位で第２動きベクトルを探索し動きベクトルを決定する。さらに、動画像の動きの複雑度を判定し、動き複雑度に応じて探索単位の大きさを変化させることが望ましい。
【００１８】
通常の階層的動きベクトル探索では、１段目探索および２段目探索ともに、ブロックごとに探索をおこない各ブロックの動きベクトルを検出するが、本発明によれば、１段目の探索において隣接する複数のブロックをまとめて一括探索する。水平方向に隣接するＮブロック、垂直方向に隣接するＭブロックを一まとめにして一括探索すると、Ｎ×Ｍブロックにつき１つの動きベクトルを検出することになる。２段目探索においては、１段目探索の探索結果となった位置を中心として１ブロックごとに探索を行い、最終的な動きベクトルを決定する。最終的な動きベクトルはブロックごとに検出されるので、探索精度の低下を防ぐことができる。
【００１９】
このように１段目探索において、複数のブロックをまとめた探索単位で探索することにより、検出するベクトルの本数が少なくなる。したがって、ベクトル検出にかかる演算量が削減され、高速な動きベクトル探索を実現できる。なお、２段目探索においては１ブロックごとに動きベクトルを求めるため、動き探索の精度の低下は最小限に抑えられる。
【００２０】
また、１段目探索において複数のブロックを一度に探索することにより、最終的に得られる動きベクトルは隣接するブロック間でその差が小さくなる。そのため、動きベクトルを符号化するために必要となる符号量を少なくすることができ、ブロックデータの符号化のためにより多くの符号量を割り当てることができる。したがって、画質の低下は最小限に抑えられる。
【００２１】
【発明の実施の形態】
図１は、本発明による動きベクトル探索装置の第１実施形態を示すブロック図である。図１において、現フレームバッファ１０１には符号化中のフレームのデータが格納され、参照フレームバッファ１０２には参照フレームデータが格納されている。サブサンプリング処理部１０３は現フレームバッファ１０１および参照フレームバッファ１０２からそれぞれ現フレームデータおよび参照フレームデータを入力し、サンプリングによって縮小現フレームデータおよび縮小参照フレームデータを生成する。
【００２２】
第１段の動き探索処理部１０４は、縮小現フレームデータおよび縮小参照フレームデータを用いて動き探索を行い、その探索結果である第１段の動きベクトルの位置情報を第２段の動き探索処理部１０５へ出力する。第２段の動き探索処理部１０５は、現フレームバッファ１０１および参照フレームバッファ１０２から本来の現フレームデータ及び参照フレームデータを入力し、第１段の動きベクトルの位置を中心として詳細な動きベクトル探索を実行する。こうして、最終的な動きベクトルを決定する。
【００２３】
サブサンプリング処理１０３は縦／横の縮小をおこなう縮小処理部１１１を有し、縮小処理部１１１により縮小された縮小現フレームデータおよび縮小参照フレームデータは縮小現フレームバッファ１１２および縮小参照フレームバッファ１１３にそれぞれ格納される。第１段の動き探索処理部１０４は、後述するマッチング単抽出部１１４およびマッチング演算処理部１１５から構成される。次に、本実施形態の全体的動作について詳細に説明する。
【００２４】
図２は第１実施形態の全体的動作を示すフローチャートである。まず、縮小処理部１１１は、符号化しようとしている現フレームデータを現フレームバッファ１０１から入力してサブサンプリングする（ステップＳ２０１）。同様に、縮小処理部１１１は、参照フレームデータを参照フレームバッファ１０２から入力してサブサンプリングする（ステップＳ２０２）。
【００２５】
次に、フレームの先頭から第１段の探索処理を開始するため、縮小した現フレームの先頭のブロックにポインタを合わせ（ステップＳ２０３）、縮小したデータを用いた第１段の動き探索を開始する。まず、第１段の動き探索処理部１０４のマッチング単位抽出部２１１は、複数ブロックからなる予め指定されたマッチング単位（水平方向Ｎブロック×垂直方向Ｍブロック）を抽出する（ステップＳ２０４）。  ここで、ＮおよびＭは１以上の整数である。
【００２６】
続いて、マッチング演算処理部２１２は、抽出されたＮ×Ｍブロック領域をマッチング単位として、縮小画像上で動きベクトル探索を実行し（ステップＳ２０５）、現フレームの縮小画像と参照フレームの縮小画像との間で相関が一番高くなる位置を決定する。一つ目のブロックの探索が終了したら、まだ探索が行われていない隣接するブロックにポインタを移動させ（ステップＳ２０６）、フレーム内のすべてのブロックについて探索が終了するまで、同様の動きベクトル探索を繰り返す（ステップＳ２０７）。この第１段探索では、Ｎ×Ｍブロック領域をマッチング単位として一括探索されるために、各ブロックごとではなくＮ×Ｍブロックごとに１個の動きベクトルが検出される。
【００２７】
第１段の動きベクトル探索が終了すると（ステップＳ２０７のＹＥＳ）、第２段の動き探索処理部１０５は、現フレームの先頭のブロックにポインタを合わせる（ステップＳ２０８）。そして、第１段の探索で決定された動きベクトルを中心に、本来の画像解像度で動きベクトル探索を開始する。すなわち、第２段の動き探索では、第１段動き探索の結果である位置を中心に、１ブロックをマッチング単位として、マッチング処理をおこなう（ステップＳ２０９）。一つ目のブロックの探索が終了したら、次のブロックにポインタを移動させ（ステップＳ２１０）、すべてのブロックの探索が終了するまで第２段の動き探索を順次実行する（ステップＳ２０９〜Ｓ２１１）。フレーム内のすべてのブロックについて探索が終了していたら第２段の探索を終了させ（ステップＳ２１１のＹＥＳ）、最も相関が大きいと判定された位置を最終的な動きベクトルとする。
【００２８】
上述した第１実施形態における１段目の動きベクトル探索は、水平方向に隣接したＮブロックと垂直方向に隣接したＭブロックとからなる画素データをマッチング単位として実行される。そのために、検出される動きベクトルの個数を少なくすることができ、その結果探索に要する演算量が削減され、動きベクトル探索が高速化される。
【００２９】
第１段動き探索処理部１０４では、上述したように、Ｎ×Ｍブロック領域をマッチング単位として一括探索が実行されるために、Ｎ×Ｍブロックで同一の動きベクトルとなる。次に説明する本発明の第２実施形態は、このマッチング単位を画像の動きに応じて変化させることで探索精度の低下を最小限に抑えることが可能である。
【００３０】
図３は、本発明による動きベクトル探索装置の第２実施形態を示すブロック図である。なお、図３において、図１に示す第１実施形態と同じ機能を有するブロックには同じ参照番号を付して説明は省略する。第２実施形態は、第１段動き探索処理部３０４の構成及び動作が第１実施形態のそれらとは異なるので、以下、第１段動き探索処理部３０４について説明する。
【００３１】
図３に示すように、第２実施形態における第１段動き探索処理部３０４は、動き複雑度判定部３１４、マッチング単位決定部３１５、マッチング単位抽出部３１６、および、マッチング演算処理部３１７から構成されている。
【００３２】
動き複雑度判定部３１４は、縮小現フレームデータおよび縮小参照フレームデータをサブサンプリング処理部１０３から入力し、過去の動きベクトルの統計情報や予測誤差の大きさ等に基づいて動きの複雑さを判定する。たとえば、すでに動きベクトルを求めた近隣の複数ブロックにおいてベクトルの方向が一致していない場合、すなわち動きベクトルがバラバラの方向を指している場合に、動きが複雑であると判断する。近隣の複数ブロックにおける動きベクトルの方向の一致の程度（方向の分布の偏りなど）を数量化して動き複雑度を定めてもよい。
【００３３】
マッチング単位決定部３１５は、判定された動きの複雑さに応じてマッチング単位を変化させる。具体的には、動きが複雑であると判断される場合はマッチング単位を小さくする。これによって複雑な動きに対応することができる。また、動きが単調であると判断される場合はマッチング単位を大きくする。これによって探索に要する演算量を削減することができる。
【００３４】
マッチング単位抽出部３１６は決定されたマッチング単位を抽出し、以下、上述したように、抽出されたマッチング単位でマッチング演算処理部３１７がマッチング処理を実行する。
【００３５】
図４は第２実施形態の全体的動作を示すフローチャートである。まず、縮小処理部１１１は、符号化しようとしている現フレームデータを現フレームバッファ１０１から入力してサブサンプリングする（ステップＳ４０１）。同様に、縮小処理部１１１は、参照フレームデータを参照フレームバッファ１０２から入力してサブサンプリングする（ステップＳ４０２）。
【００３６】
次に、フレームの先頭から第１段の探索処理を開始するため、縮小した現フレームの先頭のブロックにポインタを合わせ（ステップＳ４０３）、縮小したデータを用いた第１段の動き探索を開始する。まず、動き複雑度判定部３１４は過去の動きベクトルの統計情報や予測誤差の大きさ等に基づいて動きの複雑度を判定し（ステップＳ４０４）、マッチング単位決定部３１５は判定された動きの複雑さに応じてマッチング単位の大きさを決定する（ステップＳ４０５）。
【００３７】
具体的には、動き複雑度が比較的大きいところではマッチング単位（水平方向Ｎブロック×垂直方向Ｍブロック）が小さくなり、動き複雑度が比較的小さいところ（動きの単調なところ）ではマッチング単位が大きくなるように、たとえばＮおよびＭの値を予め定めテーブル化して格納しておく。マッチング単位抽出部２１１は、決定されたマッチング単位のサイズに応じてマッチング単位を抽出する（ステップＳ４０６）。
【００３８】
続いて、マッチング演算処理部３１７は、抽出されたＮ×Ｍブロック領域をマッチング単位として、縮小画像上で動きベクトル探索を実行し（ステップＳ４０７）、現フレームの縮小画像と参照フレームの縮小画像との間で相関が一番高くなる位置を決定する。一つ目のブロックの探索が終了したら、まだ探索が行われていない隣接するブロックにポインタを移動させ（ステップＳ４０８）、フレーム内のすべてのブロックについて探索が終了するまで、同様の動きベクトル探索（ステップＳ４０４〜Ｓ４０８）を繰り返す（ステップＳ４０９）。この第１段探索では、Ｎ×Ｍブロック領域をマッチング単位として一括探索されているために、第１段探索結果はＮ×Ｍブロックで同一の動きベクトルとなる。
【００３９】
第１段の動きベクトル探索が終了すると（ステップＳ４０９のＹＥＳ）、第２段の動き探索処理部１０５は、現フレームの先頭のブロックにポインタを合わせる（ステップＳ４１０）。そして、第１段の探索で決定された動きベクトルを中心に、１ブロックをマッチング単位として、マッチング処理をおこなう（ステップＳ４１１）。一つ目のブロックの探索が終了したら、次のブロックにポインタを移動させ（ステップＳ４１２）、すべてのブロックの探索が終了するまで第２段の動き探索を順次実行する（ステップＳ４１１〜Ｓ４１２）。フレーム内のすべてのブロックについて探索が終了していたら第２段の探索を終了させ（ステップＳ４１３のＹＥＳ）、最も相関が大きいと判定された位置を最終的な動きベクトルとする。
【００４０】
このように、動きの複雑なところでは小さいマッチング単位で探索し、動きの単調なところでは大きいマッチング単位で探索するため、探索精度の低下をより小さくし、かつ高速な動きベクトル探索が可能となる。
【００４１】
【実施例】
次に、横方向の画素数が７２０、縦方向の画素数が４８０の動画像を符号化する場合を具体例として、本発明による動きベクトル探索方法について説明する。
【００４２】
符号化方式は横方向１６画素、縦方向１６画素を一つのブロックとして、ブロックごとに動きベクトルを割り当てる方式を採用しているものとし、第１段の動きベクトル探索のマッチング単位が水平方向２ブロック×垂直方向１ブロックに設定されているものとする。
【００４３】
図５は、本発明による動きベクトル探索方法の一実施例を説明するための模式的な流れ図である。まず、水平７２０画素×垂直４８０画素のオリジナルフレームデータ５０１を所定の縮小率（ここでは水平および垂直方向に１／２）でサブサンプリングし、水平３６０画素×垂直２４０画素の縮小フレームデータ５０２を生成する。このとき、１ブロックのサイズは、水平８画素×垂直８画素となる。
【００４４】
この縮小フレームデータ５０２を用いて、８×８ブロックの水平方向２個分となる水平１６画素×垂直８画素のサイズをマッチング単位として第１段の複数ブロック一括探索を実行する。上述したように、各ブロックにおいて、あらかじめ指定された探索範囲内のすべての点を探索し相関が最も大きくなる位置を探す。ここでは、第１段探索によって、探索中心から左に６画素（−６）、下に３画素の動きベクトル（−６，３）が特定されたと仮定する。
【００４５】
次に、第１段の探索で得られた探索結果の画素位置を本来の解像度の画素位置にマッピングする。ここでは、水平および垂直方向に２倍した位置（−１２，６）にマッピングされる。マッピングされた位置（−１２，６）とそれを中心とする周辺とが１ブロック（１６×１６）をマッチング単位として探索される。すなわち、第１段で一括探索した２つのブロックそれぞれについて、（−１２，６）に基づいて第２段の探索が実行される。このように第１段の探索結果は隣接する２つのブロックで同一のものになっているが、第２段の探索では１ブロックごとに探索を行うために、最終的に得られる動きベクトルはブロックごとに異なるものとなる。
【００４６】
このように動きベクトル探索を行うことで、通常の探索よりも高速でかつ精度の良く動きベクトルを検出することができる。
【００４７】
図６は、本発明による動きベクトル探索装置の他の実施形態であるコンピュータシステムを示すブロック図である。このコンピュータシステムには、プログラム制御プロセッサ６０１が装備されている。プログラム制御プロセッサ６０１には、現フレームバッファ６１１および参照フレームバッファ６１２の他に、必要なプログラムを格納したプログラムメモリ６０２と、縮小現フレームバッファ６１３および縮小参照フレームバッファ６１４を含む縮小フレームバッファ６０３と、が接続されている。
【００４８】
プログラムメモリ６０２には、本発明による動きベクトル探索を実行するためのメインプログラムの他に、上述した縮小処理部６１５、マッチング単位抽出処理部６１６、複数ブロックを一括探索する第１段動き探索処理部６１７、１ブロックごとの探索をおこなう第２段動き探索処理部６１８をそれぞれ機能的に実現するプログラムモジュールが格納されている。プログラムメモリ６０２には、更に動き複雑度判定部およびマッチング単位決定部が格納され、本発明の第２実施形態をインプリメントすることもできる。メインプログラムおよび各機能モジュールをプログラム制御プロセッサ６０１で実行することで、本発明による動きベクトル探索が実行される。
【００４９】
【発明の効果】
以上説明したように、本発明による動きベクトル探索方法及び装置は、サブサンプリングを行って第１の探索を実行する際に、隣接する複数ブロックを一括探索する。このように構成することで、演算量が削減され、動きベクトル探索を高速化できる。また、第２探索においては１ブロックごとに探索をおこなうため、動きベクトル探索の精度の低下は最小限に抑えることができる。
【００５０】
さらに、第１探索を実行する際に隣接する複数のブロックを一括探索するため、隣同士のブロックの動きベクトルの差が小さくなる。このため、動きベクトルを符号化するために必要となる符号量を少なくすることができ、ブロックデータの符号化のためにより多くの符号量を割り当てることができる。したがって、動きベクトル探索において若干の探索精度低下が見られるが、画質の低下は最小限に抑えることができる。
【００５１】
また、本発明によれば、第１の探索において動きの複雑度に応じてマッチング単位を変化させることができる。このために、動きの複雑なところではマッチング単位を小さくし、動きの単調なところでは大きくする、というように動きに応じた適切な探索が可能となり、探索精度の低下をより小さくし、かつ高速な動きベクトル探索が可能となる。
【図面の簡単な説明】
【図１】本発明による動きベクトル探索装置の第１実施形態を示すブロック図である。
【図２】第１実施形態の全体的動作を示すフローチャートである。
【図３】本発明による動きベクトル探索装置の第２実施形態を示すブロック図である。
【図４】第２実施形態の全体的動作を示すフローチャートである。
【図５】本発明による動きベクトル探索方法の一実施例を説明するための模式的な流れ図である。
【図６】本発明による動きベクトル探索装置の他の実施形態であるコンピュータシステムを示すブロック図である。
【図７】（Ａ）は、一般的な多段探索法を説明するための画素配列を示す模式図であり、（Ｂ）は第２段の探索の様子を示すシーケンス図である。
【符号の説明】
１０１  現フレームバッファ
１０２  参照フレームバッファ
１０３  サブサンプリング処理部
１０４  第１段動き探索処理部
１０５  第２段動き探索処理部
１１１  縮小処理部
１１２  縮小現フレームバッファ
１１３  縮小参照フレームバッファ
１１４  マッチング単位抽出部
１１５  マッチング演算処理部
３１４  動き複雑度判定度判定部
３１５  マッチング単位決定部
３１６  マッチング単位抽出部
３１７  マッチング演算処理部
６０１  プログラム制御プロセッサ
６０２  プログラムメモリ
６０３  縮小フレームバッファ
６１１  現フレームバッファ
６１２  参照フレームバッファ
６１３  縮小現フレームバッファ
６１４  縮小参照フレームバッファ
６１５  縮小処理
６１６  マッチング単位抽出
６１７  複数ブロックによる１段目探索
６１８  １ブロックごとの２段目探索
【図１】
2004229150.tif 000003
【図２】
2004229150.tif 000004
【図３】
2004229150.tif 000005
【図４】
2004229150.tif 000006
【図５】
2004229150.tif 000007
【図６】
2004229150.tif 000008
【図７】
2004229150.tif 000009