(57)【特許請求の範囲】
【請求項１】
参照フレーム画像内に存する複数の参照ブロックの内の一つを計算対象参照ブロックとして当該計算対象参照ブロックと対象フレーム画像内の動き検出対象ブロックとの残差計算を行う処理を、前記計算対象参照ブロックを所定の順番で変えながら繰り返し、前記動き検出対象ブロックとの残差が最小となるような参照ブロックを見つけ出し、当該参照ブロックの前記動き検出対象ブロックに対する変位を当該動き検出対象ブロックに関する動きベクトルとして算出する動きベクトル探索方法であって、
前記計算対象参照ブロックと前記動き検出対象ブロックとの残差計算処理を行う過程において、
当該計算対象参照ブロックに関する残差計算に用いられた画素の数である残差算出画素数が所定数に達するまでは、残差逐次検定法を採用して、当該残差算出画素数に対応した残差が所定の閾値を超えた場合には当該残差計算の打ち切りを行うこととし、
前記残差算出画素数が所定数に達した後は、前記残差計算の打ち切りを行わずに、当該計算対象参照ブロック内における残りの全ての画素に関して残差計算を行うこととした
ことを特徴とする動きベクトル探索方法。
【請求項２】
請求項１に記載の動きベクトル探索方法において、
当該動きベクトル探索方法は、プロセッサを有するコンピュータシステム上で実行されるものであり、
前記所定数は、当該動きベクトル探索方法を実行する前記プロセッサの種類に応じて定まるものである
ことを特徴とする動きベクトル探索方法。
【請求項３】
請求項１に記載の動きベクトル探索方法において、
当該動きベクトル探索方法は、プロセッサ及び記憶手段を有するコンピュータシステム上で実行されるものであり、
前記プロセッサの種類に応じた画素数を前記コンピュータシステムの記憶手段に予め記憶しておき、
当該動きベクトル探索方法を実行するにあたり、前記プロセッサの種類を判定するＩＤを読みとり、該ＩＤに対応する前記画素数を前記記憶手段から読み出し、この読み出した画素数を前記所定数とする
ことを特徴とする動きベクトル探索方法。
【請求項４】
演算・制御装置と、前記演算・制御装置に所定の処理を実行させるためのプログラムを格納すると共に前記演算・制御装置が前記プログラムを実行する際に一時記憶としても動作する記憶装置とを備え、前記演算処理が前記プログラムに従って前記所定の処理を実行することにより、参照フレーム画像を参照して対象フレーム画像内に存する動き検出対象ブロックに関する動きベクトルを探索するための動きベクトル探索装置であって、
前記所定の処理は、参照フレーム画像内に存する複数の参照ブロックの内の一つを計算対象参照ブロックとして当該計算対象参照ブロックと対象フレーム画像内の動き検出対象ブロックとの残差計算を行う残差計算処理を、前記計算対象参照ブロックを所定の順番で変えながら繰り返し、それにより、前記動き検出対象ブロックとの残差が最小となるような参照ブロックを見つけ出すと共に、当該参照ブロックの前記動き検出対象ブロックに対する変位を当該動き検出対象ブロックに関する動きベクトルとして算出するものであり、
前記残差計算処理は、当該計算対象参照ブロックに関する残差計算に用いられた画素の数である残差算出画素数が所定数に達するまでは、残差逐次検定法を採用して、当該残差算出画素数に対応した残差が所定の閾値を超えた場合には当該残差計算の打ち切りを行う一方、前記残差算出画素数が所定数に達した後は、前記残差計算の打ち切りを行わずに、当該計算対象参照ブロック内における残りの全ての画素に関して残差計算を行うものである
ことを特徴とする動きベクトル探索装置。
【請求項５】
請求項４に記載の動きベクトル探索装置において、
前記所定数は、当該動きベクトル探索方法を実行する前記演算・制御装置の種類に応じて定まるものである
ことを特徴とする動きベクトル探索装置。
【請求項６】
請求項４に記載の動きベクトル探索装置において、
前記記憶装置には、演算・制御装置の種類に応じた画素数を予め記憶しており、
前記所定の処理は、前記残差計算処理を実行するにあたり、前記演算・制御装置の種類を判定するＩＤを読みとり、該ＩＤに対応する前記画素数を前記記憶装置から読み出し、この読み出した画素数を前記所定数とする
ことを特徴とする動きベクトル探索装置。
【請求項７】
演算・制御装置及び記憶装置を備えたコンピュータシステムにおいて前記演算・制御装置に対して所定の処理を実行させ、前記コンピュータシステムを、参照フレーム画像を参照して対象フレーム画像内に存する動き検出対象ブロックに関する動きベクトルを探索するための動きベクトル探索装置として機能させるためのプログラムであって、
前記所定の処理は、参照フレーム画像内に存する複数の参照ブロックの内の一つを計算対象参照ブロックとして当該計算対象参照ブロックと対象フレーム画像内の動き検出対象ブロックとの残差計算を行う残差計算処理を、前記計算対象参照ブロックを所定の順番で変えながら繰り返し、それにより、前記動き検出対象ブロックとの残差が最小となるような参照ブロックを見つけ出すと共に、当該参照ブロックの前記動き検出対象ブロックに対する変位を当該動き検出対象ブロックに関する動きベクトルとして算出するものであり、
前記残差計算処理は、当該計算対象参照ブロックに関する残差計算に用いられた画素の数である残差算出画素数が所定数に達するまでは、残差逐次検定法を採用して、当該残差算出画素数に対応した残差が所定の閾値を超えた場合には当該残差計算の打ち切りを行う一方、前記残差算出画素数が所定数に達した後は、前記残差計算の打ち切りを行わずに、当該計算対象参照ブロック内における残りの全ての画素に関して残差計算を行うものである
ことを特徴とするプログラム。
【請求項８】
請求項７に記載のプログラムにおいて、
前記所定数は、当該プログラムを実行する前記演算・制御装置の種類に応じて動的に定まるものである
ことを特徴とするプログラム。
【請求項９】
請求項７に記載のプログラムにおいて、
前記残差計算処理の実行に先立って、演算・制御装置の種類に応じた画素数を前記記憶装置に記憶しておき、
前記残差計算処理を実行するにあたり、前記演算・制御装置の種類を判定するＩＤを読みとり、該ＩＤに対応する前記画素数を前記記憶装置から読み出し、この読み出した画素数を前記所定数とする
ことを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、動きベクトル探索方法、動きベクトル探索装置及びプログラムに関し、特に、残差計算を早期に打ち切ることによって、高速に探索を行う動きベクトル探索方法、動きベクトル探索装置及びプログラムに関する。
【０００２】
【従来の技術】
動画像は情報量が膨大であるため、その記録・伝送のためには効率の良い圧縮符号化が不可欠である。一般に、動画像は時間的および空間的に高い相関性を持っているため、それを利用することで大幅な圧縮が可能となる。
【０００３】
時空間的相関性を利用した動画像圧縮符号化の要素技術として、動き補償予測符号化技術が、ＭＰＥＧ−１／２／４などの国際符号化標準において広く用いられている。動き補償予測符号化技術とは、動画像を構成する各フレーム間の動きを検出し、検出された変位情報（以下、動きベクトルと呼ぶ）と、それによって生成される予測画像と元の画像との差分画像（以下、予測誤差画像と呼ぶ）とを、元の画像信号の代わりに符号化する技術である。動画像は一般に時間的相関性が大きいため、動きベクトルと予測誤差画像の持つ情報量は、元の画像の持つ情報量よりも小さくなる。よって、動き補償予測符号化技術を用いることで、高い圧縮率を得ることができる。
【０００４】
上記国際標準で用いられる動き補償予測符号化技術においては、動きを検出する単位として、符号化対象フレームを分割した小ブロックが用いられる。小ブロックの形状としては、１６×１６画素などの矩形領域が最も一般的である。検出の方法としては、ブロックマッチングアルゴリズムと呼ばれる手法が用いられる。これは、動きの検出単位である小ブロック（以下、動き検出対象ブロックと呼ぶ）に対して、符号化処理済の先行フレーム（以下、参照フレームと呼ぶ）内にある同サイズの部分画像（以下、参照ブロックと呼ぶ）を探索し、動き検出対象ブロックに最も合致する参照ブロックを検出する手法である。ブロック間の合致は、動き検出対象ブロックと参照ブロックとの間で各々対応する位置にある画素を比較し、画素間の差異を総和することによって評価できる。ブロック間の合致の評価値としては、人間の主観との相違と計算のしやすさとのトレードオフから、各画素の差分絶対値和（式１）もしくは差分二乗和（式２）を用いるのが最も一般的である。ここで、ｐ（ｉ，ｊ）は動き検出対象ブロック内の位置（ｉ，ｊ）にある画素の画素値、ｑ（ｘ，ｙ）（ｉ，ｊ）は動き検出対象ブロックからの変位（ｘ，ｙ）にある参照ブロック内の位置（ｉ，ｊ）にある画素の画素値、ＢＭＥ（ｘ，ｙ）は評価値を表す。評価値が小さいほどブロックが合致していることを表し、最小のＢＭＥ（ｘ，ｙ）を与える変位（ｘ，ｙ）が、求めるべき動きベクトルとなる。以下、このようにして得られるブロック間の合致の評価値を、残差と呼ぶ。また、ブロックマッチングアルゴリズムを用いて残差最小のブロックを探索する処理を、動きベクトル探索と呼ぶ。
【０００５】
【数１】
0003928699.tif 000002
【数２】
0003928699.tif 000003
【０００６】
図１は、動画像圧縮符号化における動きベクトル探索を説明するための模式図である。入力動画像として画像系列１０が与えられており、フレーム１２が現在の符号化対象フレームであるとする。参照フレーム１１は、符号化対象フレーム１２よりも先行して符号化が終了しているものが選ばれる。なお、ＭＰＥＧ−１／２／４などの国際符号化標準においては、フレームの時間順序と符号化順序が必ずしも一致しないため、参照フレーム１１が符号化対象フレーム１２に対して時間的に先行している必要はない。符号化対象フレーム１２は、ブロック１４のような小ブロックに分割され、各動き検出対象ブロックに対して動きベクトル探索が行われる。動きベクトルについて、近接フレーム間では、小さい動きほど発生確率が高いという一般的な性質がある。そのため、ブロック１４に対する動きベクトル探索は、参照フレーム１１全体に対してでなく、参照フレーム１１内で設定された探索領域１５の中で行われる。
【０００７】
図２は、動きベクトル探索の基本的な手続きの例を示すフローチャートである。まずステップＳ２０で、探索領域を設定する。ステップＳ２１で、次に残差計算を行う参照ブロックを選択する。このとき選ばれた参照ブロックの変位を（ｘ，ｙ）とする。ステップＳ２２で、定められた参照ブロックに対して残差計算を行う。ステップＳ２３で、得られた残差ＢＭＥ（ｘ，ｙ）を、過去の探索で得られた最小残差ＢＭＥｍｉｎと比較する。ＢＭＥ（ｘ，ｙ）がＢＭＥｍｉｎよりも小さければ、ＢＭＥｍｉｎを更新し、そのときの変位を（ｘｍｉｎ，ｙｍｉｎ）として記憶する（ステップＳ２４）。ただし、最初の参照ブロックに対しては、過去の最小残差は存在しないので、無条件にステップＳ２４に移行する。ステップＳ２５では、探索領域内で未評価の参照ブロックが残っているかどうかを調べる。残っていれば、新たな参照ブロックを設定して再び残差計算を行う（ステップＳ２１）。これを、探索領域内の全ての参照ブロックに対して繰り返す。探索が終了した時点で最小残差ＢＭＥｍｉｎを持つ参照ブロックの変位（ｘｍｉｎ，ｙｍｉｎ）が、動きベクトルとして求められる。図１の例においては、動き検出対象ブロック１４に対して、探索領域１５内で参照ブロック１３が残差最小であったとすると、ベクトル１６が動きベクトルとなる。
【０００８】
動画像圧縮符号化における動きベクトル探索以外の処理については、例えば特開２０００−２３６５５２号公報の中で述べられている。それらは本技術とは独立した技術であるため、詳細な説明は省略する。
【０００９】
ここで、このような圧縮符号化を行うにあたって、動きベクトル探索に要する演算量が問題となる。図１を例にとって説明する。図３は、図１の参照フレーム１１内の、探索領域１５周辺を拡大して示したものであり、１個の丸印が１画素に対応している。１フレームあたりの画素数をＸ×Ｙ、１ブロックあたりの画素数をＭ×Ｎ、探索領域の画素数をＶ×Ｗとすると、１つの動き検出対象ブロック１４に対して、探索領域１５の中で（Ｖ−Ｍ＋１）×（Ｗ−Ｎ＋１）通りの参照ブロックが存在する。ただし、ここでの説明においては、参照ブロックは整数画素単位で存在するものとしている。１参照ブロックあたりＭ×Ｎ画素分の残差を求める必要があるため、１画素分の残差を求めるのに必要な演算量を１とすると、動き検出対象ブロック１４に対して残差最小の参照ブロック１３を求めるために必要な演算量は（Ｖ−Ｍ＋１）×（Ｗ−Ｎ＋１）×Ｍ×Ｎとなる。符号化対象フレーム１２内には（Ｘ／Ｍ）×（Ｙ／Ｎ）個の動き検出対象ブロックが存在するため、１フレームあたりの総演算量は（Ｖ−Ｍ＋１）×（Ｗ−Ｎ＋１）×Ｘ×Ｙとなる。一般には、画像の解像度が増すにつれ、画素単位で見た相対的な動きが大きくなるため、Ｖ，ＷはそれぞれＸ，Ｙに比例して増大させる必要がある。したがって、動きベクトル探索に要する演算量は、ほぼ画像解像度Ｘ×Ｙの二乗に比例する。例えば（Ｘ，Ｙ）＝（６４０，４８０），（Ｍ，Ｎ）＝（１６，１６）のとき、探索領域を（Ｖ，Ｗ）＝（４６，４６）とすると、１フレームあたりの演算量は２９５，２１９，２００にも上る。また、上記国際標準においては、小数画素精度の動き補償予測符号化技術が用いられるため、動きベクトル探索に要する演算量はさらに増加する。
【００１０】
上記の理由から、動きベクトル探索の演算量削減が重要となる。ここで、動きベクトル探索とは、残差を評価関数とする探索によって、複数の参照ブロックから最適な参照ブロックを求める処理である。したがって、動きベクトル探索の演算量削減技術は一般に、（１）探索を行う参照ブロック数を削減するための技術と、（２）残差計算自体の演算量を削減するための技術と、の２種類の独立した技術に分けることができる。先に、１ブロックあたりの画素数をＭ×Ｎ、探索領域の画素数をＶ×Ｗとすると、１つの動き検出対象ブロックに対する動きベクトル探索に必要な演算量は（Ｖ−Ｍ＋１）×（Ｗ−Ｎ＋１）×Ｍ×Ｎとなることを述べた。この場合、（１）は（Ｖ−Ｍ＋１）×（Ｗ−Ｎ＋１）の項をより小さな値に置き換える技術にあたり、（２）はＭ×Ｎの項をより小さな値に置き換える技術にあたる。
【００１１】
探索ブロック数の削減技術の例としては、Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ刊行、“Ｍｏｔｉｏｎ  Ｅｓｔｉｍａｔｉｏｎ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｖｉｄｅｏ  Ｃｏｍｐｒｅｓｓｉｏｎ”（ＩＳＢＮ０−７９２３−９７９３−２）、６５〜６７頁などに記載されている木探索がある。これは、探索領域内の全ての参照ブロックに対して探索を行うのではなく、探索を数段階に分けて、各段で得られる残差最小ブロックの周囲に対して段階的に細かく探索を行う手法である。図４に木探索の例を示す。１段目は２画素精度で探索を行い、「１」と書いた位置にある参照ブロックについてのみ残差を計算する。ここで変位（−２，０）にある参照ブロックが残差最小であったとすると、２段目はその周囲の参照ブロックについてのみ１画素精度で探索を行う。×印をつけた位置にある参照ブロックは、探索を行わない。このようにすることで、残差計算を行う参照ブロック数を削減することができる。
【００１２】
一方、残差計算の演算量削減に関して、これまでに広く知られている手法に、１９７２年２月、アイ・トリプルイー・トランザクションズ・オン・コンピューターズ、第Ｃ−２１巻、第２号、１７９〜１８６頁（ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓｏｎ  Ｃｏｍｐｕｔｅｒｓ，  Ｖｏｌ．Ｃ−２１，  Ｎｏ．２，  Ｆｅｂｒｕａｒｙ，  １９７２，  ｐｐ．１７９−１８６）（以下、文献１と呼ぶ）に記載されている残差逐次検定法（Ｓｅｑｕｅｎｔｉａｌ  Ｓｉｍｉｌａｒｉｔｙ  Ｄｅｔｅｃｔｉｏｎ  Ａｌｇｏｒｉｔｈｍ）がある。これは、類似していないブロック間では画素毎の残差が大きく、これを逐次累算していく際に、その和が急激に増大するという性質に注目し、ある閾値によって残差計算を途中で打ち切るというものである。ブロック間の残差を式１や式２のような画素間の差異の総和として計算する場合、一般には演算器の制限から、いくつかの画素ごとに求めた残差（以下、部分残差と呼ぶ）を逐次累算していく方法がとられる。そこで、途中まで求めた残差と閾値とを比較し、残差が閾値を超えていれば、その参照ブロックの残差計算を打ち切り、次の参照ブロックの評価に移ればよい。これによって、全参照ブロックに対してＭ×Ｎ画素分の誤差を計算する必要がなくなり、残差計算に要する演算量を削減できる。
【００１３】
残差逐次検定法を用いる場合、残差計算を打ち切るための閾値をいかに設定するかが重要となる。閾値が大きすぎると、残差計算を打ち切ることのできる場合が少なくなり、演算量を十分に削減できない。逆に閾値が小さすぎると、不当に残差計算を打ち切ってしまい、動きベクトルを正しく求めることができなくなり、結果として符号化効率の低下をもたらす。文献１では、画像の統計的性質を調べ、類似していないブロック間での残差の期待値および標準偏差を用いて閾値を設定する手法が示されている。しかし、実用的観点から言えば、対象画像の性質を事前に知らなくても適用できる手法が望ましい。
【００１４】
そのような閾値の設定方法としては、１９７６年７月情報処理学会刊行、情報処理、第１７巻、第７号、６３４〜６４０頁の「残差逐次検定法による画像の重ね合わせ」（以下、文献２と呼ぶ）に開示されている閾値自動決定法がある。この方法は、閾値として、過去の残差の最小値を用いるものである。最初に走査する参照ブロックの残差計算においては、閾値を設定せずに最後まで残差を計算し、そこで得られた値を閾値とする。以降、それより小さな残差を持つ参照ブロックが発見されるたびに、その残差値を新たな閾値として再設定する。これは、最小残差を持つ参照ブロックのみが必要であり、それ以外の参照ブロックに対しては残差を正しく求める必要がない、という動きベクトル探索処理の持つ性質を利用したものである。この手法を用いると、不要な残差計算を途中で打ち切りつつ、確実に最小残差を持つ参照ブロックを求めることができる。
【００１５】
図５は、残差逐次検定法において過去の最小残差を閾値として用いる場合の、残差計算の手続きの一例を示したフローチャートである。まずステップＳ４０で、残差ＢＭＥ（ｘ，ｙ）を０に初期化する。ステップＳ４１で、ブロックの一部に対して部分残差を計算し、その結果をＢＭＥ（ｘ，ｙ）に加算する。ここで、ブロックの一部とは、１画素であってもよいし、前述のようにブロックが矩形領域である場合、１ライン分の画素集合であってもよい。これは、残差逐次検定法によって削減できる演算コストと、残差逐次検定法を用いることによって新たに発生する比較および条件分岐などの演算コストとのバランスを考慮して決定すべきものである。ステップＳ４１を終えた時点で、ブロック内の全画素に対して計算を終えていれば（ステップＳ４２）、残差計算を終了する。そうでない場合、残差計算を続ける前に、残差ＢＭＥ（ｘ，ｙ）を過去の最小残差ＢＭＥｍｉｎと比較する（ステップＳ４３）。残差ＢＭＥ（ｘ，ｙ）が過去の最小残差ＢＭＥｍｉｎよりも小さければ、ステップＳ４１に戻って残差計算を続行する。そうでなければ、そこで残差計算を打ち切る。以上の手続きを図２のステップＳ２２に対して適用することで、動きベクトル探索に要する演算量を削減できる。
【００１６】
図６は、残差逐次検定法の効果を説明するためのグラフである。ある参照ブロックに対して残差を逐次的に計算した場合に、残差がｆ５０（ｎ）のように推移した場合を考える。以下、このように計算の終了した画素数ｎに対応して変化する残差を、残差関数と呼ぶ。また、その画素数ｎを残差算出画素数と呼ぶ。残差関数ｆ５０（ｎ）では、ブロック内の総画素数Ｎｂｌｏｃｋよりも少ない画素数ｎ５０まで計算した時点で残差が閾値ＢＭＥｍｉｎを超えるので、そこで計算を打ち切ることができる。そのため、（Ｎｂｌｏｃｋ−ｎ５０）画素分の演算量を削減できる。また、残差が残差関数ｆ５１（ｎ）のように推移し、新しい最小残差ＢＭＥ５１が得られたとすると、ＢＭＥｍｉｎ＝ＢＭＥ５１と設定され、これが以降の参照ブロックに対する打ち切り閾値として用いられる。
【００１７】
その他の閾値の設定方法として、例えば特開２０００−６９８９４号公報に記載されている初期閾値の設定手法がある。それまでの最小残差を閾値とする上記の手法では、探索の初期段階では打ち切りが効果的に機能しない。そこで、単に探索初期位置にある参照ブロックの残差を初期値とするのではなく、探索原点での残差と、動き検出対象ブロックの平均値分離絶対値和のうち小さい方の値を初期値とすることで、初期閾値を小さな値に設定するというものである。
【００１８】
以上に挙げた従来手法においては、閾値は残差算出画素数に依存しない定数（以降、これを固定閾値と呼ぶ）である。一方、式１および式２に基づいて計算される残差関数は、逐次演算の過程で値が減少することがない広義の単調増加関数である。そのため、残差計算を打ち切るための閾値は、残差計算の初期段階ではより小さな値をとり、計算が進むにつれて増加するような可変値とした方がよい。そうすることで、精度をほぼ保ったままで、より演算量を削減できる。文献２には、残差算出画素数に応じた可変の閾値（以降、これを傾斜閾値と呼ぶ）の自動決定法についても開示されている。それは、文献１で示されている閾値設定手法における残差の期待値と標準偏差を、過去の最小残差を用いて近似的に置き換えるというものである。具体的には、残差算出画素数をｎとすると、式３で表されるＴ（ｎ）が閾値となる。括弧内を展開した第１項が残差の期待値の近似値、第２項が残差の標準偏差の近似値を表す。式中のＢＭＥｍｉｎは過去の最小残差、Ｎｂｌｏｃｋはブロック内総画素数、ｋは適当な正定数である。
【００１９】
【数３】
0003928699.tif 000004
【００２０】
上記の式３で表される傾斜閾値を用いると、ｎがＮｂｌｏｃｋに近づくとＴ（ｎ）がＢＭＥｍｉｎを上回る。これにより、無駄な残差計算が発生する。それを解決するため、文献２では、式４で表されるＴ´（ｎ）を閾値として設定する手法も示されている。ここで、ｍｉｎ（Ａ，Ｂ）は、ＡとＢのうち小さい方の値を表す。
【００２１】
【数４】
0003928699.tif 000005
【００２２】
【発明が解決しようとする課題】
しかしながら、上述した従来手法では、次のような問題があった。
【００２３】
第１の問題点は、固定閾値を用いる従来手法では、閾値が定数値であることから、十分な演算量削減ができないということである。一方、演算量削減のために閾値を小さくとると、不当に残差計算を打ち切ることによる精度低下の問題が発生する。残差関数は、逐次演算の過程で値が減少することのない広義の単調増加関数である。そのため、残差計算を打ち切るための閾値は、残差算出画素数が少ない間はより小さな値をとり、計算が進むにつれて増加するような傾斜閾値とした方が、演算効率の点で良い。すなわち、演算精度をほぼ保ったままで、より一層演算量を削減することができる。
【００２４】
第２の問題点は、過去の最小残差と画素数の関数によって残差の期待値と標準偏差を近似し、それに基づいて打ち切り閾値を設定する式３の従来手法では、打ち切り閾値を算出するための演算量が多いということである。傾斜閾値を用いる場合、残差計算途中で、打ち切り判定を行うたびに閾値を更新する必要が生じる。この従来手法では、閾値の更新に際して、乗算および平方根演算を用いて閾値を算出し直す必要がある。これらの演算は、一般に大きな演算量を要する。そのため結果として、かえって残差計算の演算量が増大してしまう可能性がある。また、メモリ上にテーブルを置くなどの手段を講じることにより閾値算出に要する演算量は削減できるが、これはメモリアクセスの増大を引き起こす。本質的な解決のためには、より少ない演算量で閾値を更新できる手法が必要である。
【００２５】
第３の問題点は、傾斜閾値と固定閾値を組み合わせる式４の従来手法では、複数の閾値を組み合わせることによって閾値との比較が煩雑になるということである。第２の問題点で述べたように、閾値の算出に要する演算量はできるだけ少ない方が良い。したがって、複数の閾値を組み合わせて用いるのではなく、単独で十分に機能する傾斜閾値を用いるのが良い。
【００２６】
第４の問題点は、上述の従来手法では、閾値との比較および条件分岐に要するコストを考慮していないということである。特にソフトウェア処理を考えた場合、これが問題になる。１つの参照ブロックに対する残差計算が進み、残りの画素数が少なくなるほど、残差計算の打ち切りによって削減される演算量は少なくなる。特に式１の差分絶対値和を用いる場合などは、個々の画素値から残差を計算する処理自体に必要な演算量はさほど多くない。一方、近年の汎用プロセッサでは、演算パイプラインの深化と分岐予測技術の採用により、分岐予測を誤った場合のペナルティが大きい。そのため、通常の算術演算の演算コストに比べて、条件分岐のコストが大きくなる。したがって、残差算出画素数が一定の画素数を超えると、残りの画素については閾値との比較および打ち切り処理を行わず、残り全ての残差計算を行った方が良い場合がある。前述の従来手法では、こうした場合について考慮されていない。
【００２７】
このように、先に述べた従来の動きベクトル探索手法は、これらの４点のうちいずれかの課題を持っており、効果的な演算量削減を達成できていない。
【００２８】
本発明は、上述した問題点を解消すべく、従来手法に比べてより少ない演算量で効率良く残差計算を打ち切る、高速で精度低下の少ない動きベクトル探索方法を提供することを目的とする。
【００２９】
また、本発明の他の目的は、そのような動きベクトル探索装置を提供することにある。
【００３０】
【課題を解決するための手段】
本発明による動きベクトル探索手法は、ブロックマッチングアルゴリズムを利用した動きベクトル探索手法であって、残差算出画素数の一次関数として式５の形で表される傾斜閾値を用い、残差計算処理（図８のＳ７３）において、計算途中の部分残差がその閾値を上回った場合には残差計算を途中で打ち切る（図１２のＳ８４）ことを特徴とする。
【００３１】
【数５】
0003928699.tif 000006
【００３２】
この方式においては、打ち切りに用いる閾値が、残差計算の初期段階では小さな値をとり、残差算出画素数の増加にしたがって増加する。これは広義の単調増加関数である残差関数の性質に合致するため、不要な残差計算を早期に打ち切り、精度低下を抑えて高速に動きベクトル探索を行うことができる。また本方式では、式５より導かれる式６を用い、閾値の初期値と増分とを残差計算に先立って求めておき、残差計算時には増分を順次累算していく（図１２のＳ８５）ことにより、閾値更新を加算のみで行うことができる。つまり、閾値更新に要する演算量はほとんどない。なぜならば、式６より、ｎ−ｋ画素分の部分残差に対する打ち切り閾値と、ｎ画素分の部分残差に対する打ち切り閾値との差が、残差算出画素数ｎに依存しない数ｂｋで表せるからである。これらの作用により、本発明によって、高速で精度低下の少ない動きベクトル探索方法を提供できる。
【００３３】
【数６】
0003928699.tif 000007
【００３４】
また、本発明による動きベクトル探索手法は、上記動きベクトル探索手法において、式５で表されるパラメータａ，ｂ（以下、この２つをあわせて閾値パラメータと呼ぶ）を、探索の過程で過去に得られた最小残差から算出するための閾値パラメータ算出処理（図８のＳ７６）を実行し、最小残差がより小さな値に更新されるたびに、それに応じて傾斜閾値をより小さな値に更新するようにしたことを特徴とする。
【００３５】
この手法においては、最小残差にしたがう傾斜閾値を用いることによって、さらに効率良く動きベクトル探索を行うことができる。これは、最小残差を超える残差をもつ参照ブロックは不要であるという、動きベクトル探索処理の性質に基づいている。また、一般に探索の過程において頻繁に最小残差が更新されることはないため、最小残差にしたがって閾値パラメータａ，ｂを更新することによる演算量増加はほとんどない。これにより、さらに高速で精度低下の少ない動きベクトル探索方法を提供できる。
【００３６】
また、本発明による動きベクトル探索手法は、前述の動きベクトル探索手法の残差計算処理において、ある一定の残差算出画素数を超えた場合には打ち切り判定を行わず、残り全ての画素に対して残差計算を行うようにしたことを特徴とする。
【００３７】
この方式においては、閾値に応じた打ち切り判定自体の演算コストを考慮して、不要な打ち切り判定処理を除去することにより、さらなる演算量削減および精度向上を達成できる。
【００３８】
【発明の実施の形態】
次に、本発明の実施の形態について、図面を参照して詳細に説明する。
【００３９】
（第１の実施の形態）
図７は、本発明の一実施の形態による動きベクトル探索装置を示したブロック図である。図７を参照すると、本発明の第１の実施の形態による動きベクトル探索装置は、演算・制御装置６０、記憶装置６１、入出力インタフェース６２を備えており、それらはバスを介して互いに接続されている。
【００４０】
演算・制御装置６０は、本実施の形態による動きベクトル探索プログラムを起動し、動きベクトル探索に必要な演算を行う。また、当該プログラムに従って、記憶装置６１および入出力インタフェース６２に制御信号を送信し、これらの装置を制御する。
【００４１】
記憶装置６１は、上記の動きベクトル探索プログラムを格納している。すなわち、演算・制御装置６０は、記憶装置６１に格納された動きベクトル探索プログラムに従って動作する。また、記憶装置６１は、動きベクトル探索に必要な各種データをも記憶する。具体的には、記憶装置６１は、次の３種類のデータを主に記憶する。第１には、本発明による動きベクトル探索プログラムを記憶する。第２には、動き検出対象ブロックおよび参照フレーム画像を記憶する。第３には、動きベクトル探索処理の過程で必要となる、参照ブロックの変位や残差値などの各種変数を一時的に記憶する。なお、ここで言う記憶装置６１は、ＲＡＭなどの主記憶の他、汎用ＭＰＵに含まれるレジスタや、キャッシュメモリ、ハードディスク装置など、あらゆる記憶装置を含むものとする。
【００４２】
入出力インタフェース６２は、演算・制御装置６０からの制御信号に応じて、動きベクトルに必要な各種データを外部から入力し、あるいは外部に出力するための媒介手段である。具体的には、動きベクトル探索の対象となる動画像を入力し、記憶装置６１に渡す。また、動きベクトル探索の結果として、動きベクトルやその指し示す参照ブロックの残差などを、必要に応じて出力する。
【００４３】
次に、図７および図８乃至１５を参照して本実施の形態の動作について詳細に説明する。
【００４４】
図８は、本実施の形態の動作を記述したフローチャートである。
【００４５】
探索に先立って、動き検出対象ブロックおよび参照フレーム画像が、入出力インタフェース６２から入力され、記憶装置６１に記憶されているものとする。演算・制御装置６０は、記憶装置６１に記憶された参照フレーム画像に対し、適当な探索領域を設定し、その探索領域を表す情報を記憶装置６１に記憶する（ステップＳ７０）。探索領域は例えば、動き検出対象ブロックと同位置にあるブロックから水平・垂直方向に（±１５，±１５）の範囲の矩形領域などに設定される。この場合、探索領域の左上隅の座標値と右下隅の座標値などを、記憶装置６１に記憶しておけばよい。
【００４６】
また、動きベクトル探索において用いる各変数を、記憶装置６１内に確保し、初期化を行っておく（ステップＳ７１）。以降の動作の説明においては明示しないが、変数の値を利用するときには、演算・制御装置６０が記憶装置６１に制御信号を送り、記憶装置６１内の当該変数を格納した領域から値を読み出す動作が行われるものとする。また、変数に値を代入するときには、演算・制御装置６０が記憶装置６１に制御信号を送り、記憶装置６１内の当該変数を格納すべき領域に、値を書き込む動作が行われるものとする。
【００４７】
本実施の形態では、最小残差を表す変数ＢＭＥｍｉｎと、その残差を与えた参照ブロックの変位を表す変数ｘｍｉｎおよびｙｍｉｎと、傾斜閾値の初期値を表す変数Ｔｉｎｉｔと、傾斜閾値の増分を表す変数ｄＴとを、記憶装置６１内に確保して利用する。これらの変数について、それぞれ詳しく説明する。
【００４８】
まず、ＢＭＥｍｉｎ、ｘｍｉｎ、ｙｍｉｎの３変数について説明する。動きベクトル探索は、最小残差を持つ参照ブロックを探索する処理であるから、探索の過程においては、過去の最小残差ＢＭＥｍｉｎを記憶しておく必要がある。また、最小残差を与えた参照ブロックの変位が求める動きベクトルとなるから、残差ＢＭＥｍｉｎを与えた参照ブロックの変位（ｘｍｉｎ，ｙｍｉｎ）を記憶しておく必要がある。探索開始時点では、過去の最小残差とその参照ブロックの変位は存在しないので、適当な初期値を与えておく。最小残差ＢＭＥｍｉｎの初期値としては、残差がとりうる最大値以上の定数ＢＭＥｍａｘを初期値としておくとよい。例えば、ブロックが８×８画素の矩形領域である場合、画素値が０から２５５までの値をとり、残差の評価値として式１の差分絶対値和を用いるとすると、ＢＭＥｍａｘ＝６４×２５５＝１６３２０などとするとよい。また、変位（ｘｍｉｎ，ｙｍｉｎ）としては、原点（０，０）を初期値としておくとよい。ただし、探索開始時に最小残差および変位の初期値としてどのような値を与えておくかは当業者において任意に定め得る事項である。
【００４９】
次に、本発明による動きベクトル探索に特有の変数Ｔｉｎｉｔ及びｄＴについて説明する。本発明の残差計算で用いる閾値は、式６で表されるように残差計算の進行に応じて累算によって更新される傾斜閾値である。そのため、最初の打ち切り可否判定における閾値Ｔｉｎｉｔと、閾値を更新するための増分ｄＴとを記憶しておく必要がある。例えば、一度に残差計算を行う画素数をｋとすると、閾値の初期値Ｔｉｎｉｔおよび増分ｄＴには、それぞれ、式５においてｎ＝ｋとおいたときの値ａ＋ｂｋと、式６の第２項ｂｋとを記憶しておくとよい。ｋの値は、残差計算を行う演算・制御装置６０の演算能力に応じて定められる。例えば、ブロックが８×８画素の矩形領域である場合、ｋを１水平ライン分の画素数８などに設定するのが一般的である。
【００５０】
ここで、初期閾値Ｔｉｎｉｔおよび増分ｄＴを算出するために必要な閾値パラメータａ，ｂは、残差算出画素数ｎがブロック内の総画素数Ｎｂｌｏｃｋに達したとき、閾値Ｔ（ｎ）が過去の最小残差ＢＭＥｍｉｎと等しくなるように設定するのがよい。つまり、適当な係数αを用いて、式７および式８のように閾値パラメータａ，ｂを設定し、閾値Ｔ（ｎ）を式９のように定めればよい。ＢＭＥｍｉｎを超える残差の計算は無駄であり、逆に残差がＢＭＥｍｉｎを下回るときに打ち切りを発生させると精度低下をもたらすからである。なお、α＝０とすると、固定閾値を用いる従来手法と同一になる。
【００５１】
【数７】
0003928699.tif 000008
【数８】
0003928699.tif 000009
【数９】
0003928699.tif 000010
【００５２】
さらに、閾値の傾きｂも最小残差ＢＭＥｍｉｎに応じて変化するようにするのが効果的である。つまり、適当な係数βを用いて、式１０および式１１のように閾値パラメータａ，ｂを設定し、閾値Ｔ（ｎ）を式１２のように定めればよい。最小残差が小さくなるにつれて閾値の傾きを小さくすることで、打ち切り速度と精度のバランスが適切に保たれるからである。なお、β＝０とすると、固定閾値を用いる従来手法と同一になる。
【００５３】
【数１０】
0003928699.tif 000011
【数１１】
0003928699.tif 000012
【数１２】
0003928699.tif 000013
【００５４】
ここで、係数βは０より大きく１より小さい任意の値をとるが、特に１に近い値にすると、残差計算の打ち切りが早くなり、効果的に演算量が削減される。しかし、βを１に近づけすぎると、残差関数の僅かな上下変動によっても残差計算が打ち切られてしまう可能性が高くなり、動きベクトル探索の精度低下をもたらす。従って、係数βをどのように設定するかは、計算量と探索精度のトレードオフを考慮し所望とする条件に応じてなされるべきである。
【００５５】
図９および図１０はそれぞれ、係数βを様々に変化させた場合の計算量の変化と誤差の変化を表したグラフである。これらのグラフは共に、解像度７２０×４８０画素の画像９種類を用い、本実施の形態の動きベクトル探索装置によって、１６×８画素サイズの矩形領域ブロックに対する動きベクトル探索を行った実験の平均結果である。実験においては、ｋ＝１６×２とした。図９は、残差計算が行われたライン数の平均値を示しており、数値が小さいほど計算量が削減されたことを表す。また図１０は、求められた動きベクトルの指す参照ブロックによって動き検出対象ブロックを置き換えて表現した場合の、元画像との信号対雑音比を示しており、数値が小さいほど誤差が大きいことを表す。図１０より、探索精度を重視したい場合には、係数βの値を１／２以下に設定すればよい。また、探索精度を多少落としても高速化を図りたい場合には、より１に近い、例えば３１／３２などの値に設定すればよい。これらの値は、当該動きベクトル探索装置に求められる計算量および探索精度に基づいて予め設定され、プログラム内の定数として記憶装置６１内に格納される。
【００５６】
なお、ここで述べたように閾値パラメータを過去の最小残差にしたがって設定する場合、初期閾値Ｔｉｎｉｔおよび増分ｄＴは過去の最小残差に依存するため、探索開始時点ではその値を求めることができない。そこで、記憶装置６１には、適当な初期値を記憶しておく。例えば、前述の定数ＢＭＥｍａｘを用いて、初期閾値ＴｉｎｉｔとしてＢＭＥｍａｘを記憶し、増分ｄＴとして０を記憶しておくとよい。ただし、探索開始時に初期値としてどのような値を与えておくかは当業者において任意に定め得る事項である。
【００５７】
ステップＳ７０およびステップＳ７１の初期設定が終わると、次に演算・制御装置６０は、ステップＳ７２で、探索領域内で次に評価すべき参照ブロックを一つ選択する。この選択された参照ブロックは、本明細書において計算対象参照ブロックともいう。この選択に際し、演算・制御装置６０は、選択した参照ブロックの変位（ｘ，ｙ）を記憶するための領域を記憶装置６１内に確保し、該変位（ｘ，ｙ）を記憶しておく。探索領域内での参照ブロックの選択順序としては、例えば、探索領域の中心にある参照ブロックを最初に選択し、以降その周囲を螺旋順に選んでいくという順序を用いる。このような探索順序例を、図１１に示す。
【００５８】
演算・制御装置６０は、記憶装置６１内に記憶された参照フレーム画像から、変位（ｘ，ｙ）によって指示される位置の参照ブロック（すなわち「計算対象参照ブロック」）を読み取ると共に動き検出対象ブロックを読み取って残差計算を行う（ステップＳ７３）。すなわち、ステップＳ７３は、一つの計算対象参照ブロックと動き検出対象ブロックとの残差を計算するステップである。このステップＳ７３の残差計算について、図１２を参照して詳細に説明する。
【００５９】
図１２は、本実施の形態の動作における残差計算の手続きを記述したフローチャートである。
【００６０】
まずステップＳ８０で、残差計算に用いる各変数を、記憶装置６１内に確保し、初期化を行っておく。本実施の形態の残差計算手続きにおいては、計算途中の残差を表す変数ＢＭＥ（本明細書において「一時的残差」とも言う。）と、残差算出画素数を表す変数ｎと、閾値を表す変数Ｔとを記憶装置６１内に確保して利用する。残差計算開始時点での初期値としては、ＢＭＥ＝０、ｎ＝０、Ｔ＝Ｔｉｎｉｔをそれぞれ記憶しておけばよい。
【００６１】
ステップＳ８０の初期設定が終わると、ステップＳ８１に移る。演算・制御装置６０は、２つのブロックの対応する画素対をｋ個、記憶装置６１から読み取り、式１にしたがって残差計算を実行する。演算・制御装置６０は、算出したｋ画素分の残差を変数ＢＭＥの値に加算し、得られた値を変数ＢＭＥに代入する。換言すると、演算・制御装置６０は、ｋ画素分の残差である部分残差を既に求められていた一時的残差（変数ＢＭＥ）に加算して、新たな一時的残差（更新された変数ＢＭＥ）を算出する。ここで、ブロック内での計算順序は任意であるが、図１３のような計算順序を用いるのが一般的である。図１３は、ブロックが８×８の矩形領域であり、ｋ＝１の場合の計算順序例を示している。例えばｋ＝８とすると、計算順序は図１４のようになる。次いで演算・制御装置６０は、変数ｎの値にｋを加算し、加算結果を変数ｎに代入する（ステップＳ８２）。
【００６２】
ステップＳ８３では、ブロック内の全画素について残差計算を行ったかどうかを調べる。演算・制御装置６０は、変数ｎの値を、ブロック内の総画素数Ｎｂｌｏｃｋと比較する。これが等しければ、残差計算を終了する。この場合、打ち切りなしに全画素について残差を計算したことになる。等しくない場合には、ステップＳ８４に移る。
【００６３】
ステップＳ８４では、現時点での部分残差を閾値と比較し、打ち切り可否判定を行う。演算・制御装置６０は、変数ＢＭＥの値を、変数Ｔの値と比較する。部分残差ＢＭＥが閾値Ｔよりも小さければ、変数Ｔの値に変数ｄＴの値を加算し、加算結果を変数Ｔに代入する（ステップＳ８５）。これによって閾値の更新が行われる。一方、ステップＳ８４において、部分残差が閾値以上であった場合には、ここで残差計算を打ち切る。この場合、変数ＢＭＥは、当該参照ブロックの残差を正しく保持していない。そのため、後続の最小誤差判定（ステップＳ７４）において、判断に誤りが生じる可能性がある。そこで本実施の形態では、残差計算を打ち切る場合、残差がとりうる最大値以上の定数ＢＭＥｍａｘを、変数ＢＭＥに代入する（ステップＳ８６）。
【００６４】
以上がステップＳ７３の残差計算の詳細である。このようにして当該参照ブロックの残差を求めたら、演算・制御装置６０は、ステップＳ７３において求められた変数ＢＭＥの値を、変数ＢＭＥｍｉｎの値と比較する（ステップＳ７４）。残差ＢＭＥが過去の最小残差ＢＭＥｍｉｎ以上であれば、ステップＳ７５とステップＳ７６を飛ばして、ステップＳ７７へ移る。一方、残差ＢＭＥが過去の最小残差ＢＭＥｍｉｎよりも小さければ、ステップＳ７５に移る。ステップＳ７５では、変数ＢＭＥｍｉｎに変数ＢＭＥの値を代入し、最小残差を更新する。同時に（ｘｍｉｎ，ｙｍｉｎ）に当該参照ブロックの変位（ｘ，ｙ）の値を代入し、最小残差を与えた参照ブロックの変位を更新する。
【００６５】
ステップＳ７５で最小残差および変位を更新したら、演算・制御装置６０は、新たな最小残差に応じて、初期閾値Ｔｉｎｉｔおよび増分ｄＴを算出し直す（ステップＳ７６）。例えば式１０および式１１を用いてＢＭＥｍｉｎから算出される閾値パラメータａ，ｂを用いて、変数Ｔｉｎｉｔにａ＋ｂｋを代入し、変数ｄＴにｂｋを代入する。求めた初期閾値および増分は、以降の参照ブロックに対する残差計算の打ち切り可否判定において用いる。
【００６６】
最後にステップＳ７７で、全ての参照ブロックに対して残差計算を終えたかどうかを判定する。まだ未評価の参照ブロックが残っている場合には、ステップＳ７２に戻る。以降、次の参照ブロックを選択し、ステップＳ７７までの処理を繰り返す。全ての参照ブロックに対して残差計算が終われば、そこで動きベクトル探索を終了する。演算・制御装置６０は、探索終了時点で記憶装置６１に記憶されている（ｘｍｉｎ，ｙｍｉｎ）を、動きベクトルとして入出力インタフェース６２に出力する。
【００６７】
なお、本実施例においては、図１２のようにループ形式で残差計算を行う手続きを説明したが、実際の残差計算のプログラム制御がループ形式である必要はない。ブロックの形状および大きさがあらかじめわかっていれば、定数ｋを定めることによりループ回数は定まるので、ループを展開してステップＳ８３を除去すればよい。
【００６８】
次に、本実施の形態の効果について説明する。
【００６９】
本実施の形態では、残差計算において、残差算出画素数ｎの一次関数として表される傾斜閾値を用いる。それにより、２つの効果・利点が生じる。
【００７０】
１つ目の利点は、残差計算の初期段階では打ち切り閾値を小さく設定できるので、効率的に残差計算を打ち切り、演算量を削減できることである。図１５は、本実施の形態の効果を説明するためのグラフである。ある参照ブロックに対して、残差が残差関数ｆ１２０（ｎ）のように推移する場合を考える。図のように、傾斜閾値Ｔ（ｎ）を用いることで、過去の最小残差ＢＭＥｍｉｎを閾値とする従来手法に比べ、演算量を削減できる。演算量の削減効果は、前述の図９のグラフからも見て取れる。β＝０の場合、すなわち固定閾値ＢＭＥｍｉｎを用いる従来手法とβが１に近い場合とを比較すると、演算量が半分近く削減されていることがわかる。また、精度低下がほぼ０とみなせる場合、すなわちβが１／２以下の場合においても、演算量が効果的に削減されていることがわかる。
【００７１】
２つ目の利点は、式６によって表されるように、残差算出画素数の増加に応じた傾斜閾値の更新を、加算のみを用いて行えることである。このため、残差の期待値と標準偏差の予測値に基づく傾斜閾値を用いる従来手法に比べ、閾値の算出に要する演算量を削減できる。また、固定閾値を用いる従来手法に比べても、傾斜閾値算出のための演算量増加はほとんどない。
【００７２】
また、本実施の形態では、傾斜閾値の係数を、その時点までで得られた最小残差に応じて更新する。このため、過去の最小残差が小さくなればなるほど、残差計算処理をより小さな値で打ち切ることができる。したがって、本実施の形態による動きベクトル探索手法によれば、上記の効果に加えて、動きベクトル探索に要する演算量がさらに効率良く削減されるという効果も得られる。最小残差の更新はそれほど頻繁には生じないため、このような閾値の更新に伴う演算量増加はほとんどない。
【００７３】
（第２の実施の形態）
次に、本発明の第２の実施の形態による動きベクトル探索装置とその動作について、図面を参照して詳細に説明する。本実施の形態のシステム構成は、記憶装置６１に格納された動きベクトル探索プログラムの一部が異なる点を除き、図７のブロック図に示した第１の実施の形態の構成と同じである。すなわち、本実施の形態は、その動作において、残差計算手続きが図１２ではなく図１６のように行われる点で、第１の実施の形態と異なる。
【００７４】
図１６は、本実施の形態の動作における残差計算の手続きを記述したフローチャートである。
【００７５】
ステップＳ８０とステップＳ８１は、第１の実施の形態における手続きと同じであるので、説明を省略する。演算・制御装置６０は、ステップＳ８１において部分残差計算を行ったのち、ステップＳ８４に進み、残差計算の打ち切り可否を判定する。部分残差ＢＭＥが閾値Ｔ以上であった場合には、残差計算を打ち切り、ステップＳ８６に進む。ステップＳ８６以降の処理は、第１の実施の形態と同じである。部分残差ＢＭＥが閾値Ｔよりも小さければ、ステップＳ８２に進んで残差算出画素数ｎを更新したのち、ステップＳ１３３に進む。
【００７６】
ステップＳ１３３では、ある一定の画素数Ｎｔｅｒｍまで残差計算が終了したかどうかを判断する。Ｎｔｅｒｍは、０より大きく、ブロック内総画素数Ｎｂｌｏｃｋより小さい正定数である。ただし、Ｎｔｅｒｍ＝Ｎｂｌｏｃｋ−ｋとおくと、第１の実施の形態と同じ動作になる。このＮｔｅｒｍの値は、部分残差計算を行う演算器の演算能力および条件分岐演算のコストバランスを考慮して決定されるべき数値である。演算・制御装置６０は、変数ｎの値を、定数Ｎｔｅｒｍと比較する。残差算出画素数ｎがまだＮｔｅｒｍに達していなければ、ステップＳ８５に進み、閾値Ｔに増分ｄＴを加算してステップＳ８１に戻る。残差算出画素数ｎがＮｔｅｒｍにまで達した場合は、ステップＳ１３７に進む。ステップＳ１３７では、ブロック内の残り全ての画素について残差計算を行い、得られた値を変数ＢＭＥの値に加算して、加算結果を変数ＢＭＥに代入する。残差計算を終了したら、図８のステップＳ７３に移る。以降の動作は、第１の実施の形態の動作と同じである。
【００７７】
ここで、Ｎｔｅｒｍについて具体例を挙げて説明しておく。図１７および図１８は、Ｎｔｅｒｍと計算量の関係を、実験結果により示したグラフである。解像度３５２×２４０画素の動画像２種類を用いて、本実施の形態の動きベクトル探索装置によって、１６×１６画素サイズの矩形領域ブロックに対して動きベクトルを探索する実験を行い、１組のブロック対に対する残差計算に要した平均クロック数を計測した。この実験においては、一度に残差計算を行う画素数はｋ＝１６×２とした。図１７、図１８共に、本発明による動きベクトル探索ソフトウェアプログラムを汎用プロセッサ上で動作させた結果であるが、図１７の実験では米国インテル社製のＰｅｎｔｉｕｍ（登録商標） IIIプロセッサを、図１８の実験では同社製のＰｅｎｔｉｕｍ（登録商標）４プロセッサを用いている。グラフより、Ｐｅｎｔｉｕｍ（登録商標） IIIプロセッサ上で動作させる場合にはＮｔｅｒｍ＝１６×１４、Ｐｅｎｔｉｕｍ（登録商標）４プロセッサ上で動作させる場合には、Ｎｔｅｒｍの値を１６×６とするのがよい。このようにプロセッサの種類によって相違があるのは、Ｐｅｎｔｉｕｍ（登録商標）４プロセッサは、Ｐｅｎｔｉｕｍ（登録商標） IIIプロセッサに比べて演算実行のパイプラインが２倍以上深く、条件分岐のコストが大きいからである。
【００７８】
なお、本実施例においては、Ｎｔｅｒｍは定数として説明した。しかし、図１７および図１８に示されるように、ハードウェア装置のアーキテクチャによって最適なＮｔｅｒｍの値は異なる。そして、本発明をソフトウェアプログラムとして実現する場合においては、同一プログラムが様々なプロセッサ上で動作するように実装した方が、可搬性の点で良い。したがって、Ｎｔｅｒｍの値を、プロセッサの種類に応じて変化する変数としてもよい。例えば、前述のＰｅｎｔｉｕｍ（登録商標） IIIプロセッサおよびＰｅｎｔｉｕｍ（登録商標）４プロセッサでは、プロセッサの種類を判定するＣＰＵＩＤ命令が備わっている。これを利用して、プロセッサの種類がＰｅｎｔｉｕｍ（登録商標） IIIプロセッサであればＮｔｅｒｍ＝１６×１４を記憶装置６１に格納し、Ｐｅｎｔｉｕｍ（登録商標）４プロセッサであればＮｔｅｒｍ＝１６×６を記憶装置６１に格納して、上記動作例においてこのＮｔｅｒｍの値を記憶装置６１から読み出して利用すればよい。
【００７９】
また、本実施例においては、図１６のようにループ形式で残差計算を行う手続きを説明したが、第１の実施の形態と同様に、実際の残差計算のプログラム制御がループ形式である必要はない。ブロックの形状および大きさがあらかじめわかっていれば、定数ｋを定めることにより適切なＮｔｅｒｍの値およびそれに応じたループ回数は定まるので、ループを展開してステップＳ１３３を除去すればよい。
【００８０】
次に、本実施の形態の効果について説明する。
【００８１】
残差計算の途中で閾値に基づく打ち切り判定処理を行うことは、打ち切りが発生した場合には演算量の削減に貢献するが、打ち切りが発生しなかった場合には逆に演算量の増加をもたらす。なぜならば、元の残差計算に、閾値との比較演算および条件分岐演算、ならびに閾値の更新演算が加わっているからである。特に条件分岐は近年の汎用プロセッサ上ではコストの大きい処理である。本実施の形態においては、残り画素に対する残差計算の演算量が打ち切り判定処理を行う場合よりも小さくなる時点で処理を切り替え、以降は打ち切り判定を行わずに全ての残差計算を行う。これにより、残差計算における演算コストをさらに削減することが可能となる。加えて、打ち切り可否判定の回数が減るので、誤った打ち切りによる動きベクトル探索精度の低下を抑えることができる。上記の理由から、第１の実施の形態の効果に加えて、演算量がさらに削減され、同時に動きベクトル探索の精度が向上するという効果が生じる。図１８のグラフに示されている実験結果からも、この効果がわかる。図１８の実験では、Ｎｔｅｒｍ＝１６×６とおくことで、画像の種類によって約１割程度の演算量削減効果が得られている。
【００８２】
次に、本発明の第３の実施の形態とその動作について、図面を参照して詳細に説明する。本実施の形態のシステム構成は、図７のブロック図に示した第１および第２の実施の形態の構成と同じである。本実施の形態は、その動作において、傾斜閾値の算出に用いられる式７乃至９における係数αあるいは式１０乃至１２における係数βを動的に変更する点で、第１および第２の実施の形態と異なる。
【００８３】
図１９は、本実施の形態の動作を記述したフローチャートである。ここでは、式１０乃至１２の閾値パラメータ設定式を用いる場合について説明するが、式７乃至９など他の閾値パラメータを用いてもよい。
【００８４】
ステップＳ７０は、第１の実施の形態における手続きと同じであるから、説明を省略する。次にステップＳ２０１で、記憶装置６１内に、変数βを記憶しておく領域を確保し、初期化する。演算・制御装置６０は、入出力インタフェース６２を通じて、現在利用可能な計算量を表す情報を受け取り、それに応じて適切な係数値を計算し、変数βに代入する。現在利用可能な計算量を表す情報とは例えば、動きベクトル探索処理を完了しなければならない時刻と現在時刻との差や、システムの動作周波数、ソフトウェア実装時のプロセッサの負荷率などが挙げられる。βの設定方法としては、計算量に対してある閾値を定めておいて、数段階にβの値を切り換える方法などが挙げられる。一例として、プロセッサの負荷率が９０％以上であればβ＝２５５／２５６として負荷を下げ、８０％から９０％までの間は通常の値としてβ＝１５／１６とし、負荷率が８０％を下回ればβ＝０として従来の固定閾値手法を用いる、といったように３段階に切り換える方法が考えられる。ただし、利用可能な計算量を表す情報として何を用い、それに基づいてどのようにβの値を変化させるかは任意である。
【００８５】
以降の動作は、ステップＳ７５とステップＳ７６の間にステップＳ２０６が含まれることを除き、図８が示す第１および第２の実施の形態の動作と同じである。ステップＳ２０６では、ステップＳ２０１と同様に、入出力インタフェース６２を通じて現在利用可能な計算量を表す情報を受け取り、演算・制御装置６０はそれに応じて係数βを更新し、記憶装置６１に記憶する。ステップＳ７１と同様、ステップＳ７６では、演算・制御装置６０はこのβの値を利用して初期閾値Ｔｉｎｉｔおよび増分ｄＴを計算する。ステップＳ７３の残差計算手続きは、第１の実施の形態の動作の一部である図１２の手続きを用いてもよいし、第２の実施の形態の動作の一部である図１６の手続きを用いてもよい。
【００８６】
なお、本実施例においては、初期閾値Ｔｉｎｉｔおよび増分ｄＴの計算を行う必要が生じるたびに係数βを更新する場合について説明したが、この更新は毎回必ず行う必要はない。例えばステップＳ２０６を除去して、探索開始時にのみ係数βを設定するようにしてもよい。
【００８７】
次に、本実施の形態の効果について説明する。
【００８８】
本実施の形態では、その時点で利用可能な計算量に応じて、動的に閾値パラメータを変更することにより、演算量と探索精度のトレードオフを適応的に制御できる。これによって、利用可能な計算量に制限がある場合において、負荷が大きい場合は演算量削減を優先し、負荷が小さい場合は探索精度を優先するといった柔軟な動きベクトル探索処理が行える。これは、ソフトウェアでの実時間動画像符号化システムなどにおいて有効である。
【００８９】
以上説明した第１乃至第３の実施の形態においては、打ち切りが発生した場合に最小誤差判定を誤らないための手続きとして、図１２および図１６のステップＳ８６のように、残差を十分大きな値ＢＭＥｍａｘに仮設定する手法をとった。しかし、本発明はこれに拘束されるものではなく、他の誤り回避手段をとってよい。例えば、ステップＳ８４で打ち切りが発生した場合には、ステップＳ７４からステップＳ７６までの手続きを飛ばして直接ステップＳ７７に移るようにしてもよい。図２０は、第１の実施の形態に対してそのような手続きを適用した例を示すフローチャートである。第２および第３の実施の形態に対しても、同様の手続きを適用できる。
【００９０】
また、上記実施の形態においては、ブロック内の画素の計算順序を図１３あるいは図１４のように設定しているが、本発明はそれに拘束されるものではなく、任意の計算順序を用いてよい。また、上記実施例では、ブロック内の全ての画素について計算を行っているが、演算量をさらに削減するために、ブロック内の一部の画素のみについて残差計算を行ってもよい。さらに、上記実施例においては、図１３のようにブロックが８×８の矩形領域の場合を説明したが、本発明はブロックの形状および大きさに何ら依存するものではない。
【００９１】
残差の評価値については、上記実施の形態においては差分絶対値和を用いて説明したが、本発明はこれに限定されるものではない。例えば、式２に示した差分二乗和を用いてもよいし、参照ブロックの変位に応じて重み付けを行ってもよい。本発明は、逐次計算が可能であり広義の単調増加関数となるような評価値でさえあれば、何ら評価値の形式に依存するものではない。
【００９２】
また、動きベクトル探索の際の探索領域および探索順序の設定は、上記実施の形態に限定されるものではない。任意の形状および大きさの探索領域を設定してよいし、その中でいかなる順序で参照ブロックを選択してもよい。さらに、上記実施の形態においては、探索領域内で整数画素単位の全参照ブロックについて残差計算を行う場合を説明したが、参照ブロックの選択方法はこれにも限定されない。例えば従来技術の項で述べた木探索を用いてもよいし、あるいは小数画素単位でさらに細かく参照ブロックを走査してもよい。
【００９３】
また、上記実施の形態で述べた手続きの流れにおいて、処理順序を変えても矛盾が生じない手続きについては、どのようなタイミングで処理を行ってもよい。例えば、図８のステップＳ７０とステップＳ７１の初期設定は逆の順序で行ってもよい。他に、図１２のステップＳ８３とステップＳ８４の判定は逆の順序で行ってもよい。これらの順序を入れ替えることによって、例えば全画素分の残差を計算した後に打ち切り可否判定を行うなど、無駄な処理が生じることになるが、本発明の効果はこれによって損なわれない。その他、残差計算途中での閾値Ｔの更新は、上記実施の形態においては、図１２のステップＳ８５など、次の部分残差計算（図１２ではステップＳ８１）を行う前に処理している。しかし、閾値更新のタイミングは、次回に部分残差と閾値との比較を行う時点までであればいつでもよい。例えば打ち切り閾値の初期値ＴｉｎｉｔとしてＴｉｎｉｔ＝ａ＋ｂｋではなくＴｉｎｉｔ＝ａを記憶しておき、ステップＳ８３とステップＳ８４の間で閾値更新を行ってもよい。本発明は、これらの手続き順序には何ら依存するものではない。
【００９４】
加えて、上記実施の形態においては、打ち切りに用いる閾値の記憶方法について、初期閾値Ｔｉｎｉｔ＝ａ＋ｂｋおよび増分ｄＴ＝ｂｋを記憶しておくよう説明したが、閾値の記憶方法は、これに限定されるものではない。前述のように、初期閾値としてＴｉｎｉｔ＝ａを記憶しておき、最初の打ち切り可否判定の前に閾値の更新を行うなどしてもよい。また、打ち切り可否判定の回数が２回以下の場合には、初期閾値と増分を記憶するのではなく、閾値を直接記憶してその記憶した閾値を用いるようにしてもよい。その場合、加算のみで閾値を更新できるという特徴は失われるが、効率良く早期に残差計算を打ち切ることができるという本発明の効果は損なわれない。すなわち、本発明は設定した傾斜閾値の記憶方法には何ら依存しない。
【００９５】
更に、上述した発明の実施の形態においては、動画像圧縮符号化において用いられる動きベクトル探索を例にとり説明したが、本発明の概念は動画像圧縮符号化のみに限定されるものではなく、パターンマッチング全般に適用することも可能である。例えば、本発明は、監視を目的として時間的に近接した画像間で物体の動きを検出する場合や、同一時刻に異なる方向から撮影された画像間で対応関係を検出するステレオマッチングなどの用途にも利用できる。本発明はまた、２枚の画像間で類似部分画像を探索する処理であれば適用可能であり、対象とする画像の種類および探索された動きベクトルの使用の目的に何ら依存するものではない。
【００９６】
【発明の効果】
以上説明したように、本発明の効果は、動きベクトル探索において、精度低下を抑えて演算量を削減できるということにある。
【００９７】
その理由は３つある。第１の理由は、残差算出画素数の一次関数として表される傾斜閾値を用いて残差計算を打ち切ることで、不要な残差計算を素早く打ち切ると同時に、閾値の計算に要する演算量を少なく抑え、残差計算の演算量を効率良く削減できるからである。第２の理由は、その閾値を過去の最小残差に基づいて更新することで、精度低下を抑えてさらに効率良く演算量を削減できるからである。第３の理由は、不要な閾値との比較および中断処理を取り除くことで、演算精度を保ちながら、さらに演算量を削減できるからである。
【図面の簡単な説明】
【図１】図１は、動き補償予測符号化における動き補償技術の模式図である。
【図２】図２は、動きベクトル探索の手続きを示すフローチャートである。
【図３】図３は、動きベクトル探索における演算量の大きさを説明するための模式図である。
【図４】図４は、動きベクトル探索における木探索の例を示す模式図である。
【図５】図５は、動きベクトル探索における残差計算の手続きを示すフローチャートである。
【図６】図６は、残差計算における残差逐次検定法の効用を説明するためのグラフである。
【図７】図７は、本発明の第１の実施の形態の構成を示すブロック図である。
【図８】図８は、本発明の第１の実施の形態の動作を示すフローチャートである。
【図９】図９は、本発明の第１の実施の形態において、式１０乃至１２における係数βを変化させた場合の計算量の変化を、実験結果に基づいて示したグラフである。
【図１０】図１０は、本発明の第１の実施の形態において、式１０乃至１２における係数βを変化させた場合の探索精度の変化を、実験結果に基づいて示したグラフである。
【図１１】図１１は、本発明の第１の実施の形態における探索順序の例を示す模式図である。
【図１２】図１２は、本発明の第１の実施の形態における残差計算の手続きを示すフローチャートである。
【図１３】図１３は、本発明による残差逐次検定法において設定されるブロック内の計算順序の例を示す模式図である。
【図１４】図１４は、本発明の第１の実施の形態において設定されるブロック内の計算順序の例を示す模式図である。
【図１５】図１５は、本発明の第１の実施の形態の効果を模式的に示すためのグラフである。
【図１６】図１６は、本発明の第２の実施の形態における残差計算の手続きを示すフローチャートである。
【図１７】図１７は、本発明の第２の実施の形態の効果を、実験結果に基づいて示したグラフである。
【図１８】図１８は、本発明の第２の実施の形態の効果を、実験結果に基づいて示したグラフである。
【図１９】図１９は、本発明の第３の実施の形態の動作を示すフローチャートである。
【図２０】図２０は、図８に示された第１の実施の形態による処理において、図１２のステップＳ８６を省略した場合の動作を示すフローチャートである。
【符号の説明】
１０  入力画像系列
１１  参照フレーム
１２  現符号化対象フレーム
１３  ブロック（動き検出対象ブロックと最も良く合致する参照ブロック）
１４  ブロック（動き検出対象ブロック）
１５  探索領域
１６  動きベクトル
６０  演算・制御装置
６１  記憶装置
６２  入出力インタフェース
【図１】
0003928699.tif 000014
【図２】
0003928699.tif 000015
【図３】
0003928699.tif 000016
【図４】
0003928699.tif 000017
【図５】
0003928699.tif 000018
【図６】
0003928699.tif 000019
【図７】
0003928699.tif 000020
【図８】
0003928699.tif 000021
【図９】
0003928699.tif 000022
【図１０】
0003928699.tif 000023
【図１１】
0003928699.tif 000024
【図１２】
0003928699.tif 000025
【図１３】
0003928699.tif 000026
【図１４】
0003928699.tif 000027
【図１５】
0003928699.tif 000028
【図１６】
0003928699.tif 000029
【図１７】
0003928699.tif 000030
【図１８】
0003928699.tif 000031
【図１９】
0003928699.tif 000032
【図２０】
0003928699.tif 000033