(57)【要約】【課題】動画像符号化処理におけるフィールド動きベクトル検出処理において、動きベクトルの検出処理時間を削減する動きベクトル検出装置を得ること。【解決手段】カレントブロックと参照ブロック間の動きベクトルの検出において、部分探索領域決定部１０１３は、参照ブロックの一部である領域を部分探索領域と決定し、探索終了領域決定部１０１４は、動きベクトルが領域内に含まれる場合に探索を終了する探索終了領域を決定し、動きベクトル決定部１０１５は、カレントブロックの画素と参照ブロックの部分探索領域内でずらした画素との総ての評価値を各々のフィールド動きベクトルについて算出し、最小の評価値となる動きベクトルを選択し、選択された動きベクトルがすべて探索終了領域内であれば、それをフィールド動きベクトルとし、探索終了領域外であれば、さらに動きベクトルの探索を続ける。【選択図】        図２
2006101239.tif 000002
【特許請求の範囲】
【請求項１】
処理対象となる対象画像に含まれるカレントブロックと参照対象となる対象画像に含まれる参照ブロックとの相対的な位置を示す複数の動きベクトルを検出する動きベクトル検出装置において、
前記参照ブロック内の前記動きベクトルの探索領域の一部である部分探索領域を決定する部分探索領域決定手段と、
前記部分探索領域内の一定の領域である探索終了領域を決定する探索終了領域決定手段と、
前記カレントブロックの画素値と前記参照ブロックの前記部分探索領域内に座標を変更した探索点に対応する画素値との類似度を示す評価値を求め、前記評価値が最小となる前記複数の動きベクトルを検出し、検出された前記複数の動きベクトルのすべてが前記探索終了領域決定手段によって決定された前記探索終了領域に含まれる場合には、当該動きベクトルを前記カレントブロックと前記参照ブロックとの間の動きベクトルと決定し、検出された前記複数の動きベクトルの少なくとも一つが前記探索終了領域に含まれない場合に当該複数の動きベクトルのうちの一つが指し示す探索点の座標を前記部分探索領域内の中心座標に設定する動きベクトル決定手段と、を備え、
前記部分探索領域決定手段は、さらに前記動きベクトル決定手段で設定した前記中心座標に基づいて、前記部分探索領域を決定すること、
を特徴とする動きベクトル検出装置。
【請求項２】
前記部分探索領域決定手段は、前記参照ブロック内の前記探索領域としてＮ×Ｍ(Ｎ、Ｍは整数)画素の矩形の領域を前記部分探索領域と決定し、
前記探索終了領域決定手段は、前記部分探索領域に対してｋ画素(ｋはｋ≧１なる整数)内側に存在する（Ｎ−２ｋ）×（Ｍ−２ｋ）画素の矩形の領域を前記探索終了領域とすることを特徴とする請求項１に記載の動きベクトル検出装置。
【請求項３】
前記動きベクトル決定手段は、前記対象画像および前記参照画像がインターレース画像である場合に、前記カレントブロックをトップフィールドとボトムフィールドに、前記参照ブロックをトップフィールドとボトムフィールドに分割し、前記カレントブロックのトップフィールドと前記参照ブロックのトップフィールド間の前記評価値と、前記カレントブロックのトップフィールドと前記参照ブロックのボトムフィールド間の前記評価値と、前記カレントブロックのボトムフィールドと前記参照ブロックのトップフィールド間の前記評価値と、前記カレントブロックのボトムフィールドと前記参照ブロックのボトムフィールド間の前記評価値を求めること、
を特徴とする請求項１または請求項２に記載の動きベクトル検出装置。
【請求項４】
前記動きベクトル決定手段は、前記カレントブロックと前記参照ブロックとの間の画素値の類似度と、前記動きベクトルと隣接するブロックから予測される予測動きベクトルとの差分値と、前記動きベクトルの大きさを示す値とを加算したものを前記評価値とすること、
を特徴とする請求項１〜３のいずれか一つに記載の動きベクトル検出装置。
【請求項５】
前記部分探索領域決定手段は、前記部分探索領域から前記動きベクトルが存在し得ない領域を除外した領域を前記部分探索領域と決定すること、
を特徴とする請求項１〜４のいずれか一つに記載の動きベクトル検出装置。
【請求項６】
前記部分探索領域決定手段は、前記部分探索領域からMPEG方式のf_codeパラメータで制限される動きベクトルの範囲外またはMPEGで参照を禁止されている画面外を除外した領域を前記部分探索領域と決定すること、
を特徴とする請求項５に記載の動きベクトル検出装置。
【請求項７】
処理対象となる対象画像に含まれるカレントブロックと参照対象となる対象画像に含まれる参照ブロックとの相対的な位置を示す複数の動きベクトルを検出する動きベクトル検出方法において、
前記参照ブロック内の前記動きベクトルの探索領域の一部である部分探索領域を決定する部分探索領域決定ステップと、
前記部分探索領域内の一定の領域である探索終了領域を決定する探索終了領域決定ステップと、
前記カレントブロックの画素値と前記参照ブロックの前記部分探索領域内に座標を変更した探索点に対応する画素値との類似度を示す評価値を求め、前記評価値が最小となる前記複数の動きベクトルを検出し、検出された前記複数の動きベクトルのすべてが前記探索終了領域決定ステップによって決定された前記探索終了領域に含まれる場合には、当該動きベクトルを前記カレントブロックと前記参照ブロックとの間の動きベクトルと決定し、検出された前記複数の動きベクトルの少なくとも一つが前記探索終了領域に含まれない場合に当該複数の動きベクトルのうちの一つが指し示す探索点の座標を前記部分探索領域内の中心座標に設定する動きベクトル決定ステップと、を備え、
前記部分探索領域決定ステップは、さらに前記動きベクトル決定ステップで設定した前記中心座標に基づいて、前記部分探索領域を決定すること、
を特徴とする動きベクトル検出方法。
【請求項８】
処理対象となる対象画像に含まれるカレントブロックと参照対象となる対象画像に含まれる参照ブロックとの相対的な位置を示す複数の動きベクトルを検出する動きベクトル検出プログラムにおいて、
前記参照ブロック内の前記動きベクトルの探索領域の一部である部分探索領域を決定する部分探索領域決定ステップと、
前記部分探索領域内の一定の領域である探索終了領域を決定する探索終了領域決定ステップと、
前記カレントブロックの画素値と前記参照ブロックの前記部分探索領域内に座標を変更した探索点に対応する画素値との類似度を示す評価値を求め、前記評価値が最小となる前記複数の動きベクトルを検出し、検出された前記複数の動きベクトルのすべてが前記探索終了領域決定ステップによって決定された前記探索終了領域に含まれる場合には、当該動きベクトルを前記カレントブロックと前記参照ブロックとの間の動きベクトルと決定し、検出された前記複数の動きベクトルの少なくとも一つが前記探索終了領域に含まれない場合に当該複数の動きベクトルのうちの一つが指し示す探索点の座標を前記部分探索領域内の中心座標に設定する動きベクトル決定ステップと、を備え、
前記部分探索領域決定ステップは、さらに前記動きベクトル決定ステップで設定した前記中心座標に基づいて、前記部分探索領域を決定すること、
をコンピュータに実行させることを特徴とする動きベクトル検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像符号化で必要となる動きベクトルを検出する動きベクトル検出装置、動きベクトル検出方法、およびその方法をコンピュータで実行させるプログラムに関するものである。
【背景技術】
【０００２】
従来、コンピュータにおける中央処理プロセッサ（ＣＰＵ）の動作速度の向上には、VLIW、SIMD、Super Scalar, Super Pipelineといった高速化手法が広く使われている。ここではパイプライン処理に関して説明する。非特許文献１によれば、典型的な５段パイプライン処理では、一つの命令を実行するのに次の５つのステージを経由する。（１）命令フェッチ、（２）命令デコード、（３）命令実行、（４）メモリアクセス、（５）書き込みの５つである。
【０００３】
このような５段パイプラインのプロセッサでは、１つの命令の実行を完結するのに５サイクルの時間を要することになる。パイプライン処理を採用することで、１ステージの処理を単純化することができ、プロセッサの動作速度を高速化することができる。
【０００４】
一方、パイプライン処理においてプロセッサの命令実行を阻害する要因として分岐ハザードと呼ばれる現象がある。パイプライン処理では一つのインストラクション（命令）を遂行するのに複数サイクルかかるため、条件分岐の場合に当該条件が成立するか否かが判明するまでに時間がかかる。このため、条件の成立/不成立が判明するまでＣＰＵの動作がストールするという現象が発生する。この現象についてハードウェア的に分岐予測と呼ばれる手法により回避する手法が広く用いられているが、本来設定された条件が１００％予測できることは少なく、その分のオーバーヘッドは依然として存在する。特に近年のＣＰＵではパイプラインが数十段にもなっており、分岐予測がはずれたときのペナルティが大きくなる傾向にある。
【０００５】
また、もう一つのＣＰＵの高速化技術であるＳＩＭＤ（Single Instruction/Multiple Data）は、複数の同一の処理を並列化して処理できるプロセッサであり、ＭＰＥＧ符号化においてはＤＣＴ、動き補償、動きベクトル検出などに用いられている。特にIntel社のPentium（登録商標）プロセッサでは、８画素から１６画素ものデータに対して、その差分の絶対値和を求める命令(PSADBW命令)が用意されており、これを用いると動きベクトル検出が高速に実行できることが知られている。
【０００６】
このようなＣＰＵの高速化技術の進化に伴い、ＭＰＥＧ−２／ＭＰＥＧ−４に代表される画像符号化および復号化をソフトウェアベースで行うことが一般化してきている。現在、パーソナルコンピュータ上でソフトウェアでテレビ放送の画像符号化復号化を行い、ハードディスクレコーダとして使用するような応用が広く行われている。
【０００７】
このような応用の背景には、先述のＣＰＵの高速化とともに、ＭＰＥＧ符号化における動きベクトル検出のアルゴリズム的な高速化が寄与している。その例として、特許文献1における動きベクトル検出の手法について説明する。
【０００８】
まず、この高速アルゴリズムでは、まず最初に動きベクトルの初期候補点(以下初期ＭＶ候補点)を求める。これは、最も単純な例では探索範囲の中央位置（p0）に配置する。次に、その初期ＭＶ候補点を中心とするカレントブロックと動きベクトル探索対象となるブロック(以下参照ブロックと呼ぶ)との間の相関を計算する。先述のPentium（登録商標）プロセッサでは、PSADBW命令を用いることで相関計算を高速に実行できる。
【０００９】
続いて、ＭＶ候補点の周囲８点についてp0と同様に相関を計算し、合計９点の中でどの点が最もカレントブロックと相関が高いかを調べる。いま、仮にp0以外の点が最も相関が高いとすると、ＭＶ候補点の相関関係が最も高いという条件を満たさないために、新たなＭＶ候補点を定め、新たなＭＶ候補点を中心とした９点についてカレントブロックとの相関を計算する。ここで既に相関を求めている周辺画素は、新たなＭＶ候補点も相関が小さいことが既知であるため、再度計算する必要はない。その後、他の周辺画素の中で最も相関の高い点を検索し、新たなＭＶ候補点が最も相関が高い場合には新たなＭＶ候補点が動きベクトルを示す探索点であるとして処理を終了する。
【００１０】
以上のような、探索開始点の周辺を調べて勾配法的なアプローチで動きベクトルを検索するアルゴリズムは、他にもいくつか提案されている。例えば非特許文献２に示す動きベクトル探索は広く知られている手法の一つである。
【００１１】
このような手法の特徴は、先述の初期ＭＶ候補点をうまく予想することで、動きベクトルの誤検出を防ぎ画質劣化を避けながら動きベクトルの検出に伴う計算コストを大幅に削減することができることである。非特許文献２によれば、動きベクトルの探索範囲を±７(動きベクトルとしてとりうる値が水平垂直とも−７〜＋７に限定)とした場合、探索点全てについて相関を調べるフルサーチと呼ばれる手法に比べて探索点数を７％程度にまで削減でき、処理の高速化を実現できる。
【００１２】
【特許文献１】特開２００１−２８７５４号公報
【非特許文献１】D.A.Patterson/J.L.Hennessy: Computer Organization & Design
【非特許文献２】Shan Zhu et al. "A New Diamond Search Algorithm for Fast Block Matching Motion Estimation", IEEE Transactions on Image Processing, Vol. 9, No. 2, Feb. 2000
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかしながら、上記特許文献１のような動きベクトルの探索範囲に比べて実際に探索する点数を大幅に減らす手法においては、ブロック同士の相関を求める処理に比べて、新たな探索点を特定する処理や画素データの読み込み処理が相対的に大きくなるという問題が発生する。
【００１４】
まず、個々の探索点について探索範囲内に入っているかを検査する処理が必要となる。なお、探索範囲とは、MPEG-1やMPEG-2, MPEG-4においてf_codeと呼ばれるパラメータ表現可能な動きベクトルの範囲や、参照フレームにおいて画面外を指さない範囲を意味する。
【００１５】
また、ある探索点の類似度を算出する場合、例えば、PowerPCに実装されるAltiVec命令セットで実装した場合を考えると、PowerPCアーキテクチャにおいては、１２８ビットのレジスタにメモリの内容を読み出す場合、対象メモリのアドレスは１６バイト単位にアライメントされていなければならない。このため、任意の参照画素を中心としたブロックの画素を読み出す場合には、一度１６バイトアラインメントされた連続する３２バイトを読み出し、その３２バイトから対象となる連続する１６バイトを並び替える必要があり、本質とは異なる処理であるデータの読み出しと整形といった処理にも多くの時間を費やすことがわかる。特に、近年のＣＰＵの高速化が１年で２倍近い伸びを示しているのに対し、メモリのアクセス速度はそれほどの伸びを示していないことから、データをメモリからレジスタに転送する際に発生するオーバーヘッドは、インストラクション数以上に大きな影響を与える。
【００１６】
特に、インターレース信号を扱う場合には、topフィールドからtopフィールド、topフィールドからbottomフィールド、bottomフィールドからtopフィールド、bottom フィールドからbottom フィールドと４種類の動きベクトルを検出しなければならなく、それぞれの動きベクトルを検出するたびに先述の条件判断やデータ読み出し/整形といったオーバーヘッドとなる処理を行っていては処理効率が著しく悪化する。
【００１７】
従来のフルサーチに基づく動きベクトルでは、それぞれのフィールドの動きベクトルの探索範囲が同一であれば、４種類のベクトルを求める際の条件判断・データ読み出し/整形は共通化でき、前述のオーバーヘッドは１／４に押さえられるが、上述の特許文献１で示した手法や非特許文献２で示した手法では、各フィールドベクトルが参照すべき画素が分散するために、このオーバーヘッドを共通化することができない。このため、探索点数が１／１０以下に減少したとしても、実際の実行速度は１／１０にまで削減できないという問題が発生する。
【００１８】
本発明は、上記の点に鑑みてなされたものであり、フルサーチに比べて大幅に探索点数を削減しつつ、従来の高速動きベクトル検出アルゴリズムに付随する処理のオーバーヘッドを削減することを目的とする。
【課題を解決するための手段】
【００１９】
上述した課題を解決し、目的を達成するために、本発明は、処理対象となる対象画像に含まれるカレントブロックと参照対象となる対象画像に含まれる参照ブロックとの相対的な位置を示す複数の動きベクトルを検出する動きベクトル検出装置において、前記参照ブロック内の前記動きベクトルの探索領域の一部である部分探索領域を決定する部分探索領域決定手段と、前記部分探索領域内の一定の領域である探索終了領域を決定する探索終了領域決定手段と、前記カレントブロックの画素値と前記参照ブロックの前記部分探索領域内に座標を変更した探索点に対応する画素値との類似度を示す評価値を求め、前記評価値が最小となる前記複数の動きベクトルを検出し、検出された前記複数の動きベクトルのすべてが前記探索終了領域決定手段によって決定された前記探索終了領域に含まれる場合には、当該動きベクトルを前記カレントブロックと前記参照ブロックとの間の動きベクトルと決定し、検出された前記複数の動きベクトルの少なくとも一つが前記探索終了領域に含まれない場合に当該複数の動きベクトルのうちの一つが指し示す探索点の座標を前記部分探索領域内の中心座標に設定する動きベクトル決定手段と、を備え、前記部分探索領域決定手段は、さらに前記動きベクトル決定手段で設定した前記中心座標に基づいて、前記部分探索領域を決定すること、を特徴とする。
【発明の効果】
【００２０】
本発明によれば、部分探索領域決定手段によって、参照ブロック内の動きベクトルの探索領域の一部である部分探索領域を決定し、探索終了領域決定手段によって、部分探索領域内の一定の領域である探索終了領域を決定し、動きベクトル決定手段によって、カレントブロックの画素値と参照ブロックの部分探索領域内に座標を変更した探索点に対応する画素値との類似度を示す評価値を求め、評価値が最小となる複数の動きベクトルを検出し、検出された複数の動きベクトルのすべてが探索終了領域に含まれる場合には、当該動きベクトルをカレントブロックと参照ブロックとの間の動きベクトルと決定し、検出された複数の動きベクトルの少なくとも一つが探索終了領域に含まれない場合に当該複数の動きベクトルのうちの一つが指し示す探索点の座標を前記部分探索領域内の中心座標に設定し、部分探索領域決定手段は、さらに動きベクトル決定手段で設定した中心座標に基づいて、部分探索領域を決定することにより、動きベクトルを検出するための探索点を削減することができ、処理時間が削減されるという効果を奏する。
【発明を実施するための最良の形態】
【００２１】
以下に添付図面を参照して、この発明にかかる動きベクトル検出装置の最良な実施の形態を詳細に説明する。
【００２２】
図１は、本発明の動きベクトル検出装置を含む動画像符号化装置の全体構成を示すブロック図である。動画像符号化装置１００は、動き検出器（ＭＥ）１０１と、動き補償器（ＭＣ）１０２と、離散コサイン変換器（ＤＣＴ）１０３と、量子化器（Ｑ）１０４と、可変長符号化器（ＶＣＬ）１０５と、逆量子化器（ＩＱ）１０６と、逆離散コサイン変換器（ＩＤＣＴ）１０７とから構成されている。
【００２３】
動き検出器１０１は、外部から取得した動画像に含まれる画像から動きベクトル検出を行う。動き補償器１０２は、動きベクトル検出が行われた後の画像データを取得し、画像データとローカルデコード画像により動き補償を行う。動き検出器１０１は、本発明でいう動きベクトル検出装置を構成する。
【００２４】
ここで、動きベクトルとは、前フレームから現フレームまでの間に、被写体が動いた方向と距離を表す動き位置情報をいう。
【００２５】
離散コサイン変換器１０３は、動き補償器１０２によって得られた残差信号に対して、離散コサイン変換を行う。量子化器１０４は、離散コサイン変換後の画像データに対して量子化を行う。可変長符号化器１０５は、量子化された動画像に対して符号化を行う。
【００２６】
逆量子化器１０６は、量子化器１０４から量子化後の動画像を取得し、取得した動画像に対して逆量子化を行う。逆離散コサイン変換器１０７は、逆離散コサイン変換を行う。これにより、ローカルデコードが得られる。逆離散コサイン変換器１０７は、ローカルデコード画像を動き補償器１０２に送る。
【００２７】
図２は、図１に示した動き検出器の詳細な機能構成を示すブロック図である。動き検出器１０１は、検索参照範囲決定部１０１１と、初期ＭＶ候補点算出部１０１２と、部分探索領域決定部１０１３と、探索終了領域決定部１０１４と、動きベクトル決定部１０１５とから構成されている。
【００２８】
検索参照範囲決定部１０１１は、処理対象である１６×１６画像のカレントブロックに対応する参照画像の１６×１６画素のブロックが存在しうると思われる領域を決定するものである。一般的には、カレントブロックと同一位置にある１６×１６画素のブロックを中心として、一定の範囲にある領域が検索参照範囲となる。ここでいう一定の範囲とは、例えば水平方向に±Ｒｈ画素、垂直方向に±Ｒｖ画素をカバーする、水平２×Ｒｈ＋１６画素、垂直２×Ｒｖ＋１６画素の矩形領域となることが多い。多くの場合、Ｒｈ＝２４、Ｒｖ＝１６程度の値をとる。
【００２９】
初期ＭＶ候補点算出部１０１２は、カレントブロックの初期ＭＶ候補点を算出するものである。
【００３０】
部分探索領域決定部１０１３は、カレントブロックの画素と参照ブロックの画素との間の評価値を算出するため、参照ブロックの探索点を初期ＭＶ候補点からずらして探索する範囲を示す部分探索領域を決定するものである。また、決定した部分探索領域が参照できない画素を含んでいる場合には、部分探索領域から参照できない画素を除外するものである。
【００３１】
探索終了領域決定部１０１４は、後述の動きベクトル決定部１０１５で検出された動きベクトルが収束していることを判断するための終了探索領域を決定するものである。
【００３２】
動きベクトル決定部１０１５は、カレントブロックの探索点と参照ブロックの部分探索領域の範囲内でずらした探索点のそれぞれとの評価値を算出し、部分探索領域内でずらした探索点の画素値等に基づいて算出した評価値のうち、最小の評価値を持つ動きベクトルを、カレントブロックと参照ブロックとの間の動きベクトルと決定するものである。なお、ここで扱う画像は、インターレース画像であると仮定する。インターレース画像では、1フレームがトップフィールドとボトムフィールドに分かれているため、ここで出力する動きベクトルはカレントブロックがトップフィールドであり参照ブロックがトップフィールドであるＭＶtop_top、カレントブロックがトップフィールドであり参照ブロックがボトムフィールドであるＭＶbot_top、カレントブロックがボトムフィールドであり参照ブロックがトップフィールドであるＭＶtop_bot、カレントブロックがボトムフィールドであり参照ブロックがボトムフィールドであるＭＶbot_botの４種類である。
【００３３】
次に、以上のように構成されている動き検出器による動きベクトル検出処理について説明する。図３−１、図３−２は、検索参照範囲決定部、初期ＭＶ候補点算出部、部分探索領域決定部、探索終了領域決定部、動きベクトル決定部が行う動きベクトル検出処理手順を示すフローチャートである。
【００３４】
まず、検索参照範囲決定部１０１１は、処理対象である１６×１６画像のカレントブロックと参照対象である検索参照範囲を決定し、カレントブロックの１６×１６画素をトップフィールド（１６×８画素）とボトムフィールド（１６×８画素）に分け、検索参照範囲の参照画素をトップフィールドとボトムフィールドに分けて記憶する（ステップＳ３００１）。
【００３５】
図４は、１６×１６画素のブロックをトップフィールドとボトムフィールドに分けた記憶状態の一例を示す説明図である。これにより、カレントブロックは、カレントブロックのトップフィールドとカレントブロックのボトムフィールドに分けて記憶されることにより、カレントブロック（１６×１６画素）の２つのブロック（１６×８画素）が記憶されていることとなる。同様に、検索参照範囲の参照画素についてもトップフィールドとボトムフィールドに分けて記憶される。
【００３６】
次に、初期ＭＶ候補点算出部１０１２は、動きベクトルの初期ＭＶ候補点を求める（ステップＳ３００２）。具体的には、周囲のブロックの動きベクトルを参照し、そこからカレントブロックの動きベクトル（ｘp，ｙp）を予測し、その予測ベクトルが指し示す点を初期ＭＶ候補点とするものである。例えば、ＭＰＥＧ−２の場合、（ｘp，ｙp）は左隣のマクロブロックの動きベクトルそのものとなるが、この予測方式は規格によって異なり、ＭＰＥＧ−４では左隣のほかに左上および直上のマクロブロックから計算される。
【００３７】
図５は、参照ブロックのトップフィールドおよびボトムフィールドに設定された初期ＭＶ候補点、部分探索領域、探索終了領域の一例を示す説明図である。初期ＭＶ候補点は、参照ブロックのトップフィールドに１点（５１）と、ボトムフィールドに１点（５４）の合計２点が設定される。本来、この２点の初期ＭＶ候補点はまったく独立していても構わないが、本実施の形態では、両方の候補点がフレーム内で隣り合っているものとする。なお、図５では、トップフィールドとボトムフィールドを分けているため、候補点が隣り合っている本実施の形態の場合は、同一座標となる。
【００３８】
部分探索領域決定部１０１３は、ＭＶ候補点を中心とした７×７画素の矩形領域を部分探索領域とする（ステップＳ３００３）。図５で説明すると、ＭＶ候補点（５１、５４）を中心とした、Ｘ軸方向に−３〜＋３、Ｙ軸方向に−３〜＋３の領域が部分探索領域（５２、５５）である。なお、図５で示した領域５２、５５は、カレントブロックのＭＶ候補点（５１、５４）に対応する画素について探索を行う領域である。実際にはカレントブロック自体がそれぞれのフィールドにつき１６×８画素の面積を持っているため、部分探索領域で実際に計算が行われる画素データは５２、５５で示した領域に対してＸ軸方向に１５画素、Ｙ軸方向に７画素延長された領域に含まれる画素となる。
【００３９】
探索終了領域決定部１０１４は、部分探索領域決定部１０１３で決定した部分探索領域の内側の５×５画素の矩形領域を終了探索領域とする（ステップＳ３００４）。図５で説明すると、ＭＶ候補点（５１、５４）を中心とした、Ｘ軸方向に−２〜＋２、Ｙ軸方向に−２〜＋２の領域が探索終了領域（５３、５６）である。
【００４０】
部分探索領域決定部１０１３は、決定した部分探索領域が動き検出範囲を超えているか否かを判断し、動き検出範囲を超えている場合には、動き検出範囲外を含まないように部分探索領域を変形する（ステップＳ３００５）。例えば、ＭＰＥＧ規格においては、動きベクトルの範囲はf_codeと呼ばれるパラメータで制限され、また、ＭＰＥＧ−１やＭＰＥＧ−２規格においては画面外のブロックを参照することが禁止されているため、参照が制限、禁止される領域を、部分探索領域から除外するものである。
【００４１】
図６は、部分探索領域と除外領域の一例を示す説明図である。当初部分探索領域は７×７画素の領域（６２）であるが、探索範囲の境界（６１）から超えた範囲（６３）を除外した、６×６画素の領域が新たな部分探索領域となる。一般に、f_codeで制限される領域や画面の形状は矩形であるため、変形後の部分探索領域は矩形形状である。
【００４２】
動きベクトル決定部１０１５は、探索範囲内で評価値が最小となる動きベクトルをフィールドごとに求める（ステップＳ３００６）。具体的には、まず、選択された部分探索領域内の探索点のそれぞれについて、ブロックマッチングを用いた評価値Ｅの計算を行う。評価値Ｅは、次のように４種類求めることができる。
【００４３】
参照ブロックのトップフィールドとカレントブロックのトップフィールドとの間の動きベクトルに対する評価値は、数式（１）で求めることができる。
【数１】
2006101239.tif 000003
【００４４】
参照ブロックのボトムフィールドとカレントブロックのトップフィールドとの間の動きベクトルに対する評価値は、数式（２）で求めることができる。
【数２】
2006101239.tif 000004
【００４５】
参照ブロックのトップフィールドとカレントブロックのボトムフィールドとの間の動きベクトルに対する評価値は、数式（３）で求めることができる。
【数３】
2006101239.tif 000005
【００４６】
参照ブロックのボトムフィールドとカレントブロックのボトムフィールドとの間の動きベクトルに対する評価値は、数式（４）で求めることができる。
【数４】
2006101239.tif 000006
【００４７】
ここで、座標（ｘ0，ｙ0）は、カレントブロック（１６×１６画素）の左上端の座標を示し、ｗ１、ｗ２は重み付け係数を示す。
【００４８】
評価値Ｅは、動きベクトル候補（ｘ，ｙ）に対し、左上の画素の座標が（ｘ0＋ｘ，ｙ0＋ｙ）の位置にある参照ブロックの画素値と、左上の画素の座標が（ｘ0，ｙ0）の位置にあるカレントブロックの画素値との差分値と、隣接するブロックから予測される動きベクトル（ｘp，ｙp）との差分値と、動きベクトル候補（ｘ，ｙ）の大きさから求められる。ここで、ｒtop（ｘ，ｙ）は、参照ブロックのトップフィールドにおける座標（ｘ，ｙ）の位置の画素値であり、ｒbot（ｘ，ｙ）は、参照ブロックのボトムフィールドにおける座標（ｘ，ｙ）の位置の画素値である。また、ｃtop（ｘ，ｙ）は、カレントブロックのトップフィールドにおける座標（ｘ，ｙ）の位置の画素値であり、ｃbot（ｘ，ｙ）は、カレントブロックのボトムフィールドにおける座標（ｘ，ｙ）の位置の画素値である。
【００４９】
評価値Ｅは、カレントブロックの座標（ｘ，ｙ）に対し、部分探索領域であるＭＶ候補点からｘを−３〜＋３（７画素）、ｙを−３〜＋３（７画素）の範囲でずらした参照ブロックの座標に対応する評価値を求める、すなわち、７×７＝４９回の評価値を計算するものであり、その上で最小となる評価値を選択するものである。
【００５０】
図７は、ＭＶ候補点と動きベクトルの一例を示す説明図である。カレントブロックのＭＶ候補点（７１）の座標（ｘ，ｙ）に対応する、参照ブロックのＭＶ候補点（７１）から右にずれた座標（ｘ＋２，ｙ）での評価値Ｅが最小となった場合には、カレントブロックの左上の座標（ｘ0，ｙ0）（７４）を基点した動きベクトル（ｘ＋２−ｘ0，ｙ−ｙ0）（７５）が当該フィールドでの動きベクトルとなる。
【００５１】
また、評価値Ｅは上述の通り、数式（１）〜（４）より、各２種類のフィールドの組合せである４種類の評価値（Ｅtop,top、Ｅbot,top、Ｅtop,bot、Ｅbot,bot）について求め、４種類それぞれの最小の評価値を採る動きベクトルを求める。
【００５２】
動きベクトル決定部１０１５は、各フィールドの動きベクトルのうち、評価値が最大となる動きベクトルを動きベクトルＭＶmaxとして選択する（ステップＳ３００７）。すなわち、４種類の最小の評価値を持つ動きベクトルのうち、最大の評価値を持つ動きベクトルは、さらに遠い座標の画素について評価値を求めた場合に、よりマッチした画像を検索することが可能であると考えられるため、評価値が最大となる動きベクトルを仮に動きベクトルＭＶmaxとして選択するものである。
【００５３】
図８は、評価値を算出した結果求められた各フィールドの動きベクトルの一例を示す説明図である。図８の８１は、参照ブロックのトップフィールドとカレントブロックのトップフィールドとの間の動きベクトルであり、図８の８２は、参照ブロックのトップフィールドとカレントブロックのボトムフィールドとの間の動きベクトルである。また、図８の８３は、参照ブロックのボトムフィールドとカレントブロックのトップフィールドとの間の動きベクトルであり、図８の８４は、参照ブロックのボトムフィールドとカレントブロックのボトムフィールドとの間の動きベクトルである。ステップＳ３００７では、これら４種類の動きベクトルのうち、最大の評価値を持つ動きベクトルを動きベクトルＭＶmaxとして選択する。
【００５４】
動きベクトル決定部１０１５は、動きベクトルＭＶmaxが指し示す探索点が探索終了領域決定部１０１４で決定した探索終了領域に属しているか否かを判断する（ステップＳ３００８）。探索点が探索終了領域に属していると判断した場合には（ステップＳ３００８：Ｙｅｓ）、動きベクトル決定部１０１５は、それぞれのフィールドの組み合わせに対応する動きベクトルＭＶtop_top、ＭＶbot_top、ＭＶtop_bot、ＭＶbot_botについて、これまで探索してきた動きベクトル候補点の評価値が最小であるベクトルを動きベクトルとし（ステップＳ３００９）、動きベクトル検出処理を抜ける。
【００５５】
これは、動きベクトルＭＶmaxが探索終了領域の内側に存在する場合に、さらに外側を探索すると評価値が増大する可能性が高いため、動きベクトルの探索を終了するものである。
【００５６】
探索点が探索終了領域に属していないと判断した場合には（ステップＳ３００８：Ｎｏ）、動きベクトルＭＶmaxが指し示す探索点を新たなＭＶ候補点とし（ステップＳ３０１０）、ステップＳ３００３に戻り、さらに新たなＭＶ候補点に対応する部分検索領域を決定し、動きベクトルの検出を続ける。
【００５７】
これは、探索点が部分探索領域に含まれるが、探索終了領域に含まれない領域に属している場合は、さらにその外側を探索することにより、評価値の小さな動きベクトルが検出できる可能性があると考えられるため、探索点を新たなＭＶ候補点として動きベクトル検出処理を続けるものである。
【００５８】
このように、部分探索領域を全体の探索領域に対して十分に小さく設定することにより、全体の探索領域の総ての画素に対して評価値を算出し動きベクトルを検出する処理に比べ、探索点を大幅に削減できるため、処理時間を短縮することができる。また、初期に設定した部分探索領域内で動きベクトルが検出できない場合でも、部分探索領域を変更することにより、十分に広範な領域で動きベクトルの検出が可能であるため、動きベクトル検出の漏れを生じることは少ない。
【００５９】
さらに、４種類のフィールド動きベクトルを同時に同じ探索領域内で求めることで、メモリアクセス１回で４回分の動きベクトル探索を行うことができるため、メモリからレジスタへの転送やデータ整形のためのオーバーヘッドを従来の１／４に削減することができ、動きベクトル検出の処理時間を短縮することができる。また、部分探索領域から予め探索範囲外の探索点を除外することができるため、探索点ごとの探索範囲内外の判断が不要となり、動きベクトル検出の処理時間を短縮することができる。
【００６０】
また、本実施の形態は、（１）キャッシュメモリが存在しない、（２）キャッシュメモリの代わりとなるローカルメモリ（ソフトウェアプリフェッチ技術を利用）のアクセス速度が演算速度に比べて遅いという特徴があるｃｅｌｌプロセッサにおいて用いることにより、オーバーヘッドの削減に特に有効である。
【００６１】
図９は、本実施の形態にかかる動きベクトル検出装置のハードウェア構成を示す図である。動きベクトル検出装置は、ハードウェア構成として、動きベクトル検出装置における検索参照範囲決定処理、初期ＭＶ候補点算出処理、部分探索領域決定処理、探索終了領域決定処理、動きベクトル決定処理を実行する検索参照範囲決定プログラム、初期ＭＶ候補点算出プログラム、部分探索領域決定プログラム、探索終了領域決定プログラム、動きベクトル決定プログラムおよび画像データなどが格納されている外部メモリ９６と、外部メモリ９６内のプログラムに従って動きベクトル検出装置の各部により検索参照範囲決定処理、初期ＭＶ候補点算出処理、部分探索領域決定処理、探索終了領域決定処理、動きベクトル決定処理等を実行する処理ユニット９１と、ワークエリアが形成され、動きベクトル検出装置の制御に必要な種々のデータを記憶するローカルメモリ９３と、処理を監視して画像の入出力を行うメインプロセッサ９４と、各部を接続するバス９５と、外部メモリ９６とローカルメモリ９３との間でデータの転送を行うＤＭＡコントローラ９２とを備えている。これらのうち外部メモリを除く各部はＬＳＩ９７としてひとつのパッケージ上に配される。
【００６２】
外部メモリ９６は通常、高速なＤＲＡＭで構成され、内部に格納される動きベクトル検出装置における検索参照範囲決定プログラム、初期ＭＶ候補点算出プログラム、部分探索領域決定プログラム、探索終了領域決定プログラム、動きベクトル決定プログラムは、メインプロセッサ９４によって外部に用意されたＲＯＭやハードディスクなどから電源投入後に外部メモリ９６へ転送される。
【００６３】
図９のような構成では、画像が格納されている外部メモリ９６からカレントブロックや参照画像を読み込む場合に、その都度ＤＭＡコントローラ９２にリクエスト信号を送出し、外部メモリ９６からローカルメモリ９３へ画像データが到達するのを待機しなければならない。このため、いわゆるパーソナルコンピュータのように画像データを即座に扱うことができず、メモリアクセスに要する時間が画像データを処する時間に比べ大きくなる。このため、本実施の形態に示すメモリアクセス時間を抑制して演算を行う動きベクトル検出方法が、従来の動きベクトル検出方法に比べて高速な動作を実現することができる。
【００６４】
以上、本発明を実施の形態を用いて説明したが、上記実施の形態に多様な変更または改良を加えることができる。
【図面の簡単な説明】
【００６５】
【図１】本発明の動きベクトル検出装置を含む動画像符号化装置の全体構成を示すブロック図である。
【図２】図１に示した動き検出器の詳細な機能構成を示すブロック図である。
【図３−１】検索参照範囲決定部、初期ＭＶ候補点算出部、部分探索領域決定部、探索終了領域決定部、動きベクトル決定部が行う動きベクトル検出処理手順を示すフローチャートである。
【図３−２】検索参照範囲決定部、初期ＭＶ候補点算出部、部分探索領域決定部、探索終了領域決定部、動きベクトル決定部が行う動きベクトル検出処理手順を示すフローチャートである。
【図４】１６×１６画素のブロックをトップフィールドとボトムフィールドに分けた記憶状態の一例を示す説明図である。
【図５】参照ブロックのトップフィールドおよびボトムフィールドに設定された初期ＭＶ候補点、部分探索領域、探索終了領域の一例を示す説明図である。
【図６】部分探索領域と除外領域の一例を示す説明図である。
【図７】ＭＶ候補点と動きベクトルの一例を示す説明図である。
【図８】評価値を算出した結果求められた各フィールドの動きベクトルの一例を示す説明図である。
【図９】本実施の形態にかかる動きベクトル検出装置のハードウェア構成を示す図である。
【符号の説明】
【００６６】
１００  動画像符号化装置
１０１  動き検出器
１０２  動き補償器
１０３  離散コサイン変換器
１０４  量子化器
１０５  可変長符号化器
１０６  逆量子化器
１０７  逆離散コサイン変換器
１０１１  検索参照範囲決定部
１０１２  初期ＭＶ候補点算出部
１０１３  部分探索領域決定部
１０１４  探索終了領域決定部
１０１５  動きベクトル決定部
【図１】
2006101239.tif 000007
【図２】
2006101239.tif 000008
【図３−１】
2006101239.tif 000009
【図３−２】
2006101239.tif 000010
【図４】
2006101239.tif 000011
【図５】
2006101239.tif 000012
【図６】
2006101239.tif 000013
【図７】
2006101239.tif 000014
【図８】
2006101239.tif 000015
【図９】
2006101239.tif 000016