(57)【要約】本発明の動きベクトル探索では、探索した動きベクトルを記憶しておき、これらのすでに探索をおこなった隣接ブロックの動きベクトルの値を用い、この動きベクトルの水平、垂直各成分の絶対値の定数倍を探索範囲とすることで、少ない演算量で適切な探索範囲を決定する。
2005036887.tif 000002
【特許請求の範囲】
【請求項１】
動画像の符号化における動きベクトルを探索する動きベクトル探索装置において、
検出した動きベクトルを記憶する手段と、
探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段とを有し、
周囲ブロックの動きベクトルの値から算出された値を探索範囲として動きベクトル探索処理をおこなうことを特徴とする動きベクトル探索装置。
【請求項２】
前記探索範囲を決定する手段は、探索が完了した周囲ブロックにおける動きベクトルの大きさの整数倍を、探索範囲として決定する手段であることを特徴とする請求項１に記載の動きベクトル探索装置。
【請求項３】
前記探索範囲を決定する手段は、複数の周囲ブロックの動きベクトルの最大値に基づいて、探索範囲を決定する手段であることを特徴とする請求項１又は請求項２に記載の動きベクトル探索装置。
【請求項４】
前記探索範囲を決定する手段は、探索範囲を決定する過程において、得られた予測誤差の値が大きくなる場合は探索範囲が適切でないと判断し、探索範囲をあらかじめ定められた値とする手段を更に有することを特徴とする請求項１から請求項３のいずれかに記載の動きベクトル探索装置。
【請求項５】
探索領域の中心を隣接ブロックの動きベクトルの位置にシフトし、探索をおこなう手段を更に有することを特徴とする請求項１から請求項４のいずれかに記載の動きベクトル探索装置。
【請求項６】
前記探索範囲を決定する手段は、探索範囲の最大値及び最小値を予め設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する手段を更に有することを特徴とする請求項１から請求項５のいずれかに記載の動きベクトル探索装置。
【請求項７】
前記探索範囲を決定する手段は、すでに探索をおこなった隣接ブロックの動きベクトルの値を用い、動きベクトルの水平、垂直各成分の絶対値の定数倍を探索範囲として決定する手段であることを特徴とする請求項１から請求項６のいずれかに記載の動きベクトル探索装置。
【請求項８】
ビデオ符号化装置であって、
検出した動きベクトルを記憶する手段と、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段とを有し、周囲ブロックの動きベクトルの値から算出された値を探索範囲として動きベクトル探索処理をおこなう動きベクトル探索装置を有することを特徴とするビデオ符号化装置。
【請求項９】
前記探索範囲を決定する手段は、探索が完了した周囲ブロックにおける動きベクトルの大きさの整数倍を、探索範囲として決定する手段であることを特徴とする請求項８に記載のビデオ符号化装置。
【請求項１０】
前記探索範囲を決定する手段は、複数の周囲ブロックの動きベクトルの最大値に基づいて、探索範囲を決定する手段であることを特徴とする請求項８又は請求項９に記載のビデオ符号化装置。
【請求項１１】
前記探索範囲を決定する手段は、探索範囲を決定する過程において、得られた予測誤差の値が大きくなる場合は探索範囲が適切でないと判断し、探索範囲をあらかじめ定められた値とする手段であることを特徴とする請求項８から請求項１０のいずれかに記載のビデオ符号化装置。
【請求項１２】
前記動きベクトル探索装置は、探索領域の中心を隣接ブロックの動きベクトルの位置にシフトし、探索をおこなう手段を更に有することを特徴とする請求項８から請求項１１のいずれかに記載のビデオ符号化装置。
【請求項１３】
前記探索範囲を決定する手段は、探索範囲の最大値及び最小値を予め設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する手段を更に有することを特徴とする請求項８から請求項１２のいずれかに記載のビデオ符号化装置。
【請求項１４】
前記探索範囲を決定する手段は、すでに探索をおこなった隣接ブロックの動きベクトルの値を用い、動きベクトルの水平、垂直各成分の絶対値の定数倍を探索範囲として決定する手段であることを特徴とする請求項８から請求項１３のいずれかに記載のビデオ符号化装置。
【請求項１５】
動画像の符号化における動きベクトルを探索する方法において、
検出した動きベクトルを記憶しておき、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定し、周囲ブロックの動きベクトルの値から算出された値を探索範囲として動きベクトル探索処理をおこなうことを特徴とする動きベクトル探索方法。
【請求項１６】
探索範囲を、探索が完了した周囲ブロックにおける動きベクトルの大きさの整数倍に決定することを特徴とする請求項１５に記載の動きベクトル探索方法。
【請求項１７】
探索範囲を、複数の周囲ブロックの動きベクトルの最大値に基づいて決定することを特徴とする請求項１５又は請求項１６に記載の動きベクトル探索方法。
【請求項１８】
探索範囲決定の過程で、得られた予測誤差の値が大きくなる場合は探索範囲が適切でないと判断し、探索範囲をあらかじめ定められた値とすることを特徴とする請求項１５から請求項１７のいずれかに記載の動きベクトル探索方法。
【請求項１９】
探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定し、探索領域の中心を、隣接ブロックの動きベクトルの位置にシフトして探索をおこなうことを特徴とする請求項１５から請求項１８のいずれかに記載の動きベクトル探索方法。
【請求項２０】
探索範囲の最大値及び最小値を予め設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定することを特徴とする請求項１５から請求項１９のいずれかに記載の動きベクトル探索方法。
【請求項２１】
すでに探索をおこなった隣接ブロックの動きベクトルの値を用い、動きベクトルの水平、垂直各成分の絶対値の定数倍を探索範囲として決定することを特徴とする請求項１５から請求項２０のいずれかに記載の動きベクトル探索方法。
【請求項２２】
請求項１５から請求項２１のいずれかに記載の動きベクトル探索方法を用いて、ビデオ符号化を行うことを特徴とするビデオ符号化方法。
【請求項２３】
動画像の符号化における動きベクトル探索を実行するコンピュータシステムにおいて、
対象画像データを格納する対象画像バッファと、
参照画像を格納する参照画像バッファと、
動きベクトルを記憶する動きベクトルメモリと、
動画像の符号化における動きベクトル探索をコンピュータに実行させるための命令からなるプログラムを格納するプログラムメモリと、
前記プログラムを実行するプログラム制御プロセッサと
を有し、
前記プログラムは、前記プログラム制御プロセッサに、動きベクトルメモリ中に記憶されている周囲ブロックの動きベクトルの値をもとに算出される値を探索範囲として動きベクトル探索を行わせることを特徴とするコンピュータシステム。
【請求項２４】
前記プログラムは、前記プログラム制御プロセッサに、探索が完了した周囲ブロックにおける動きベクトルの大きさの整数倍を、探索範囲として決定させることを特徴とする請求項２３に記載のコンピュータシステム。
【請求項２５】
前記プログラムは、前記プログラム制御プロセッサに、複数の周囲ブロックの動きベクトルの最大値に基づいて、探索範囲を決定させることを特徴とする請求項２３又は請求項２４に記載のコンピュータシステム。
【請求項２６】
前記プログラムは、前記プログラム制御プロセッサに、得られた予測誤差の値が大きくなる場合は探索範囲が適切でないと判断させ、探索範囲をあらかじめ定められた値とさせることを特徴とする請求項２３から請求項２５のいずれかに記載のコンピュータシステム。
【請求項２７】
前記プログラムは、前記プログラム制御プロセッサに、探索領域の中心を隣接ブロックの動きベクトルの位置にシフトし探索をおこなうことを特徴とする請求項２３から請求項２６のいずれかに記載のコンピュータシステム。
【請求項２８】
前記プログラムは、前記プログラム制御プロセッサに、得られた予測誤差の値が大きくなる場合は探索範囲が適切でないと判断させ、探索範囲をあらかじめ定められた値とさせることを特徴とする請求項２３から請求項２７のいずれかに記載のコンピュータシステム。
【請求項２９】
前記プログラムは、前記プログラム制御プロセッサに、算出された探索範囲が、予め定められた探索範囲の最大値又は最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定させることを特徴とする請求項２３から請求項２８のいずれかに記載のコンピュータシステム。
【請求項３０】
前記プログラムは、前記プログラム制御プロセッサに、すでに探索をおこなった隣接ブロックの動きベクトルの値を用い、動きベクトルの水平、垂直各成分の絶対値の定数倍を探索範囲として決定させることを特徴とする請求項２３から請求項２９のいずれかに記載のコンピュータシステム。
【請求項３１】
コンピュータを制御し、動画像の符号化における動きベクトルを探索する動きベクトル探索プログラムであって、
前記動きベクトル探索プログラムは前記コンピュータに、
探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する機能と、
決定した探索範囲で動きベクトル探索処理を行う機能を実行させることを特徴とする動きベクトル探索プログラム。
【請求項３２】
前記動きベクトル探索プログラムは、前記コンピュータに、探索が完了した周囲ブロックにおける動きベクトルの大きさの整数倍を、探索範囲として決定する機能を実行させることを特徴とする請求項３１に記載のプログラム。
【請求項３３】
前記動きベクトル探索プログラムは、前記コンピュータに、複数の周囲ブロックの動きベクトルの最大値に基づいて、探索範囲を決定する機能を実行させることを特徴とする請求項３１又は請求項３２に記載の動きベクトル探索プログラム。
【請求項３４】
前記動きベクトル探索プログラムは、前記コンピュータに、探索範囲を決定する過程において、得られた予測誤差の値が大きくなる場合は探索範囲が適切でないと判断し、探索範囲をあらかじめ定められた値とする機能を実行させることを特徴とする請求項３１から請求項３３のいずれかに記載の動きベクトル探索プログラム。
【請求項３５】
前記動きベクトル探索プログラムは、前記コンピュータに、探索領域の中心を隣接ブロックの動きベクトルの位置にシフトし、探索をおこなう機能を実行させることを特徴とする請求項３１から請求項３４のいずれかに記載の動きベクトル探索プログラム。
【請求項３６】
前記動きベクトル探索プログラムは、前記コンピュータに、探索範囲の最大値及び最小値を予め設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する機能を実行させることを特徴とする請求項３１から請求項３５のいずれかに記載の動きベクトル探索プログラム。
【請求項３７】
前記動きベクトル探索プログラムは、前記コンピュータに、すでに探索をおこなった隣接ブロックの動きベクトルの値を用い、動きベクトルの水平、垂直各成分の絶対値の定数倍を探索範囲として決定する機能を実行させることを特徴とする請求項３１から請求項３５のいずれかに記載の動きベクトル探索プログラム。
【発明の詳細な説明】
【技術分野】  本発明は、動き補償予測符号化技術に関し、特に動きベクトル探索方法、動きベクトル探索装置及びその動きベクトル探索プログラムに関する。
【背景技術】  動画像信号を記録、あるいは伝送する際の圧縮符号化では、符号化効率を高めるために画像フレーム間の相関を利用した符号化方法が一般に用いられる。画像フレーム間の相関を利用する符号化方式は動き補償予測符号化と呼ばれ、ＭＰＥＧ（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  ＥＸｐｅｒｔｓ  Ｇｒｏｕｐ）などで採用されている。
動き補償予測符号化では、フレーム間における映像の動きの情報（動きベクトル）と、動きベクトルによって生成される予測画像と符号化中のフレームとの差分画像（予測誤差）を符号化する。画像フレーム間の相関が大きければ、予測誤差が小さくなり、符号化する情報量を小さくでき、圧縮率を向上させることができる。
動き補償予測符号化では、一般に、フレームを１６×１６画素などの一定サイズのブロックに分割し、分割したブロックごとに動きベクトルを割り当てる。具体的には、すでに符号化が完了しているフレーム（参照フレーム）の中から、ブロックごとに相関が最も大きくなる場所を探し、そのブロック間の差分を求め、符号化する。
相関が大きくなる場所を探す処理を動きベクトル探索という。相関の大小は、参照フレームと符号化中フレームとのブロック内の各画素の差異を総和することで評価できる。
動きベクトル探索の処理において、フレームのどの領域を探索するかは任意である。狭い範囲を探索すれば探索に要する演算量は少なくすむが、動きの大きな映像が入力された場合に適切な動きベクトルが検出できなくなり符号化効率が低下してしまう。一方、広い範囲を探索すれば動きの大きな映像に対して適切な動き補償予測が可能になり符号化効率は向上するが演算量が膨大になってしまう。従って、映像中の動きの大きさに応じて適応的に探索範囲を切替えることが望ましい。
動きベクトル探索において探索範囲を適応的に切替える装置の一例が、特開平５−３２８３３３（文献１）、特開２０００−１３４６２８（文献２）に記載されている。
文献１に記載されている動きベクトル探索装置は、図１に示すように、動きベクトル検出回路と、動きベクトルメモリと、探索範囲判定器と、探索範囲選択器とから構成されている。
このような構成を有する従来の動きベクトル探索装置はつぎのように動作する。
すなわち、動きベクトルメモリに蓄えられた過去に検出した複数の動きベクトルのヒストグラムを計測し、計測したヒストグラムに応じて適切な探索範囲が探索範囲判定器により決定される。探索範囲選択器では有限種類の探索範囲が用意されており、探索範囲判定器での決定に従い、１つの探索範囲が選択される。
文献２に記載されている動きベクトル探索装置では、まず一つおきのブロックの動きベクトルを先に求める。次にこの動きベクトルの値が、残りのブロックでの動きベクトル探索の探索範囲決定に利用される。
文献１で開示されている方法を用いた場合、過去に求めた動きベクトルのヒストグラムを常に計測しなければならないので、探索範囲を求めるために余分な演算量が必要になるという問題があった。また、最終的に用いられる探索範囲が有限種類しか用意されておらず、選択された探索範囲が最適なものではない可能性があった。
文献２で開示されている方法を用いた場合、先に動きベクトルを求めるブロックは探索範囲が固定されており、不適切な探索範囲で動きベクトル探索が実行される可能性があった。また、半分のブロックしか適応的に探索範囲を切替えることができないので、探索範囲を適応的に切替えることにより得られる効果が半減されるという問題があった。
【発明の開示】
そこで、本発明は上記課題に鑑みて発明されたものであって、その目的は、少ない演算量で探索範囲を決定し、適切な探索範囲で動きベクトル探索できる新規な動きベクトル探索方法、装置及びプログラムを提供することにある。
上記課題を解決する第１の発明は、動画像の符号化における動きベクトルを探索する動きベクトル探索装置において、検出した動きベクトルを記憶する手段と、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段とを有し、周囲ブロックの動きベクトルの値から算出された値を探索範囲として動きベクトル探索処理をおこなうことを特徴とする。
上記課題を解決する第２の発明は、上記第１の発明において、前記探索範囲を決定する手段は、探索が完了した周囲ブロックにおける動きベクトルの大きさの整数倍を、探索範囲として決定する手段であることを特徴とする。
上記課題を解決する第３の発明は、上記第１又は２の発明において、前記探索範囲を決定する手段は、複数の周囲ブロックの動きベクトルの最大値に基づいて、探索範囲を決定する手段であることを特徴とする。
上記課題を解決する第４の発明は、上記第１から第３のいずれかの発明において、前記探索範囲を決定する手段は、探索範囲を決定する過程において、得られた予測誤差の値が大きくなる場合は探索範囲が適切でないと判断し、探索範囲をあらかじめ定められた値とする手段を更に有することを特徴とする。
上記課題を解決する第５の発明は、上記第１から第４のいずれかの発明において、探索領域の中心を隣接ブロックの動きベクトルの位置にシフトし、探索をおこなう手段を更に有することを特徴とする。
上記課題を解決する第６の発明は、上記第１から第５のいずれかの発明において、前記探索範囲を決定する手段は、探索範囲の最大値及び最小値を予め設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する手段を更に有することを特徴とする。
上記課題を解決する第７の発明は、上記第１から第６のいずれかの発明において、前記探索範囲を決定する手段は、すでに探索をおこなった隣接ブロックの動きベクトルの値を用い、動きベクトルの水平、垂直各成分の絶対値の定数倍を探索範囲として決定する手段であることを特徴とする。
上記課題を解決する第８の発明は、ビデオ符号化装置であって、検出した動きベクトルを記憶する手段と、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段とを有し、周囲ブロックの動きベクトルの値から算出された値を探索範囲として動きベクトル探索処理をおこなう動きベクトル探索装置を有することを特徴とする。
上記課題を解決する第９の発明は、上記第８の発明において、前記探索範囲を決定する手段は、探索が完了した周囲ブロックにおける動きベクトルの大きさの整数倍を、探索範囲として決定する手段であることを特徴とする。
上記課題を解決する第１０の発明は、上記第８又は第９の発明において、前記探索範囲を決定する手段は、複数の周囲ブロックの動きベクトルの最大値に基づいて、探索範囲を決定する手段であることを特徴とする。
上記課題を解決する第１１の発明は、上記第８から第１０のいずれかの発明において、前記探索範囲を決定する手段は、探索範囲を決定する過程において、得られた予測誤差の値が大きくなる場合は探索範囲が適切でないと判断し、探索範囲をあらかじめ定められた値とする手段であることを特徴とする。
上記課題を解決する第１２の発明は、上記第８から第１１のいずれかの発明において、前記動きベクトル探索装置は、探索領域の中心を隣接ブロックの動きベクトルの位置にシフトし、探索をおこなう手段を更に有することを特徴とする。
上記課題を解決する第１３の発明は、上記第８から第１２のいずれかの発明において、前記探索範囲を決定する手段は、探索範囲の最大値及び最小値を予め設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する手段を更に有することを特徴とする。
上記課題を解決する第１４の発明は、上記第８から第１３のいずれかの発明において、前記探索範囲を決定する手段は、すでに探索をおこなった隣接ブロックの動きベクトルの値を用い、動きベクトルの水平、垂直各成分の絶対値の定数倍を探索範囲として決定する手段であることを特徴とする。
上記課題を解決する第１５の発明は、動画像の符号化における動きベクトルを探索する方法において、検出した動きベクトルを記憶しておき、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定し、周囲ブロックの動きベクトルの値から算出された値を探索範囲として動きベクトル探索処理をおこなうことを特徴とする。
上記課題を解決する第１６の発明は、上記第１５の発明において、探索範囲を、探索が完了した周囲ブロックにおける動きベクトルの大きさの整数倍に決定することを特徴とする。
上記課題を解決する第１７の発明は、上記第１５又は第１６の発明において、探索範囲を、複数の周囲ブロックの動きベクトルの最大値に基づいて決定することを特徴とする。
上記課題を解決する第１８の発明は、上記第１５から第１７のいずれかの発明において、探索範囲決定の過程で、得られた予測誤差の値が大きくなる場合は探索範囲が適切でないと判断し、探索範囲をあらかじめ定められた値とすることを特徴とする。
上記課題を解決する第１９の発明は、上記第１５から第１８のいずれかの発明において、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定し、探索領域の中心を、隣接ブロックの動きベクトルの位置にシフトして探索をおこなうことを特徴とする。
上記課題を解決する第２０の発明は、上記第１５から第１９のいずれかの発明において、探索範囲の最大値及び最小値を予め設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定することを特徴とする。
上記課題を解決する第２１の発明は、上記第１５から第２０のいずれかの発明において、すでに探索をおこなった隣接ブロックの動きベクトルの値を用い、動きベクトルの水平、垂直各成分の絶対値の定数倍を探索範囲として決定することを特徴とする。
上記課題を解決する第２２の発明は、上記第１５から第２１のいずれかの発明の動きベクトル探索方法を用いて、ビデオ符号化を行うことを特徴とする。
上記課題を解決する第２３の発明は、動画像の符号化における動きベクトル探索を実行するコンピュータシステムにおいて、対象画像データを格納する対象画像バッファと、参照画像を格納する参照画像バッファと、動きベクトルを記憶する動きベクトルメモリと、動画像の符号化における動きベクトル探索をコンピュータに実行させるための命令からなるプログラムを格納するプログラムメモリと、前記プログラムを実行するプログラム制御プロセッサとを有し、前記プログラムは、前記プログラム制御プロセッサに、動きベクトルメモリ中に記憶されている周囲ブロックの動きベクトルの値をもとに算出される値を探索範囲として動きベクトル探索を行わせることを特徴とする。
上記課題を解決する第２４の発明は、上記第２３の発明において、前記プログラムは、前記プログラム制御プロセッサに、探索が完了した周囲ブロックにおける動きベクトルの大きさの整数倍を、探索範囲として決定させることを特徴とする。
上記課題を解決する第２５の発明は、上記第２３又は第２４の発明において、前記プログラムは、前記プログラム制御プロセッサに、複数の周囲ブロックの動きベクトルの最大値に基づいて、探索範囲を決定させることを特徴とする。
上記課題を解決する第２６の発明は、上記第２３から第２５のいずれかの発明において、前記プログラムは、前記プログラム制御プロセッサに、得られた予測誤差の値が大きくなる場合は探索範囲が適切でないと判断させ、探索範囲をあらかじめ定められた値とさせることを特徴とする。
上記課題を解決する第２７の発明は、上記第２３から第２６のいずれかの発明において、前記プログラムは、前記プログラム制御プロセッサに、探索領域の中心を隣接ブロックの動きベクトルの位置にシフトし探索をおこなうことを特徴とする。
上記課題を解決する第２８の発明は、上記第２３から第２７のいずれかの発明において、前記プログラムは、前記プログラム制御プロセッサに、得られた予測誤差の値が大きくなる場合は探索範囲が適切でないと判断させ、探索範囲をあらかじめ定められた値とさせることを特徴とする。
上記課題を解決する第２９の発明は、上記第２３から第２８のいずれかの発明において、前記プログラムは、前記プログラム制御プロセッサに、算出された探索範囲が、予め定められた探索範囲の最大値又は最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定させることを特徴とする。
上記課題を解決する第３０の発明は、上記第２３から第２９のいずれかの発明において、前記プログラムは、前記プログラム制御プロセッサに、すでに探索をおこなった隣接ブロックの動きベクトルの値を用い、動きベクトルの水平、垂直各成分の絶対値の定数倍を探索範囲として決定させることを特徴とする。
上記課題を解決する第３１の発明は、コンピュータを制御し、動画像の符号化における動きベクトルを探索する動きベクトル探索プログラムであって、前記動きベクトル探索プログラムは前記コンピュータに、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する機能と、決定した探索範囲で動きベクトル探索処理を行う機能を実行させることを特徴とする。
上記課題を解決する第３２の発明は、上記第３１の発明において、前記動きベクトル探索プログラムは、前記コンピュータに、探索が完了した周囲ブロックにおける動きベクトルの大きさの整数倍を、探索範囲として決定する機能を実行させることを特徴とする。
上記課題を解決する第３３の発明は、上記第３１又は第３２の発明において、前記動きベクトル探索プログラムは、前記コンピュータに、複数の周囲ブロックの動きベクトルの最大値に基づいて、探索範囲を決定する機能を実行させることを特徴とする。
上記課題を解決する第３４の発明は、上記第３１から第３３いずれかの発明において、前記動きベクトル探索プログラムは、前記コンピュータに、探索範囲を決定する過程において、得られた予測誤差の値が大きくなる場合は探索範囲が適切でないと判断し、探索範囲をあらかじめ定められた値とする機能を実行させることを特徴とする。
上記課題を解決する第３５の発明は、上記第３１から第３４いずれかの発明において、前記動きベクトル探索プログラムは、前記コンピュータに、探索領域の中心を隣接ブロックの動きベクトルの位置にシフトし、探索をおこなう機能を実行させることを特徴とする。
上記課題を解決する第３６の発明は、上記第３１から第３５いずれかの発明において、前記動きベクトル探索プログラムは、前記コンピュータに、探索範囲の最大値及び最小値を予め設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する機能を実行させることを特徴とする。
上記課題を解決する第３７の発明は、上記第３１から第３６いずれかの発明において、前記動きベクトル探索プログラムは、前記コンピュータに、すでに探索をおこなった隣接ブロックの動きベクトルの値を用い、動きベクトルの水平、垂直各成分の絶対値の定数倍を探索範囲として決定する機能を実行させることを特徴とする。
【図面の簡単な説明】  図１は適応的に探索範囲変化させる動きベクトル探索法の従来例を示すブロック図である。
図２は本発明の実施例１の構成を示すブロック図である。
図３は本発明の実施例１の動作を示すフローチャートである。
図４は本発明の実施例２の動作の具体例を示す図である。
図５は本発明の実施例３の動作を示すフローチャートである。
図６は本発明の実施例４の動作を示すフローチャートである。
図７は本発明による動きベクトル探索装置の実施例であるコンピュータシステムを示すブロック図である。
図８は本発明の実施例１の具体的な動作を示す図である。
【発明を実施するための最良の形態】  本発明の動きベクトル探索装置は、動きベクトルを探索する動きベクトル探索処理部と、求めた動きベクトルを記憶しておく動きベクトルメモリと、探索範囲を決定する探索範囲算出処理部とを備えている。
探索範囲算出処理部は、動きベクトルメモリからすでに求めた隣接ブロックの動きベクトルを取出し、隣接ブロックの動きベクトルの値をもとに適切な探索範囲を決定する。このような構成を採用し、動きベクトル探索における探索範囲を決定することにより本発明の目的を達成することができる。
【実施例１】  本発明の第１の実施例について図面を参照して詳細に説明する。
図２を参照すると、本発明の第１の実施例における動きベクトル探索装置は、符号化中のフレームのデータを格納する現フレームバッファ２０１と、参照フレームを格納する参照フレームバッファ２０２と、動きベクトル探索処理をおこなう動き探索処理部２０３と、求めた動きベクトルを記憶しておく動きベクトルメモリ２０４と、探索範囲を決定する探索範囲算出処理部２０５とから構成されている。
次に、図２及び図３のフローチャートを参照し、実施例１の動作について詳細に説明する。
まず、現フレームバッファ２０１の先頭のブロックにポインタを合わせる（図３のステップＡ１）。
次に、現在ポイントされているブロックがフレームの先頭ブロックかどうかを調べる（ステップＡ２）。
先頭のブロックの場合は、水平方向探索範囲Ｘを初期値Ｘ０、垂直方向の探索範囲Ｙを初期値Ｙ０とする（ステップＡ３）。初期値Ｘ０とＹ０とはあらかじめ設定されているものとする。
一方、先頭のブロックでない場合は、次に動きベクトルメモリ２０４に格納されている左隣のブロックの動きベクトル（ｘ，ｙ）を読み出す（ステップＡ４）。
水平方向探索範囲Ｘを左隣のブロックの動きベクトル水平成分ｘの絶対値ａｂｓ（ｘ）のａ倍の値とする（ステップＡ５）。ここでａは任意の正数とする。ただし、ここでＸの値は水平方向最大探索範囲Ｘｍａｘと水平方向最小探索範囲Ｘｍｉｎの間に収まるようにクリッピングする（ステップＡ６）。尚、Ｘの値が水平方向最大探索範囲Ｘｍａｘ又は水平方向最小探索範囲Ｘｍｉｎを超える場合には、Ｘの値を水平方向最大探索範囲Ｘｍａｘ又は水平方向最小探索範囲Ｘｍｉｎとする。また、水平方向最大探索範囲Ｘｍａｘと水平方向最小探索範囲Ｘｍｉｎの値はあらかじめ設定されているものとする。
垂直方向探索範囲Ｙは左隣のブロックの動きベクトル垂直成分ｙの絶対値ａｂｓ（ｙ）のｂ倍の値とする（ステップＡ７）。ここでｂは任意の正数とする。ただし、ここでＹの値は水平方向最大探索範囲Ｙｍａｘと水平方向最小探索範囲Ｙｍｉｎの間に収まるようにクリッピングする（ステップＡ８）。尚、Ｙの値が水平方向最大探索範囲Ｙｍａｘ又は水平方向最小探索範囲Ｙｍｉｎを超える場合には、Ｙの値を水平方向最大探索範囲Ｙｍａｘ又は水平方向最小探索範囲Ｙｍｉｎとする。また、垂直方向最大探索範囲Ｙｍａｘと垂直方向最小探索範囲Ｙｍｉｎの値はあらかじめ設定されているものとする。
これらの処理は、探索範囲算出処理部２０５にておこなわれる。
次に探索範囲を（±Ｘ、±Ｙ）画素として動きベクトル探索をおこなう（ステップＡ９）。
次にステップＡ９で得られた動きベクトルを動きベクトルメモリ２０４に格納する（ステップＡ１０）。
これらの処理は動き探索処理部２０３にておこなわれる。
フレーム内のすべてのブロックについて動きベクトル探索処理が完了したかを調べる（ステップＡ１１）。
まだ動きベクトル探索をおこなっていないブロックがある場合は次のブロックにポインタを移動させ（ステップＡ１２）、ステップＡ２にもどり動きベクトル探索処理を継続する。すべてのブロックの処理が完了していれば、そのフレームの動きベクトル探索処理を終了する。
次に、具体的な実施例を用いて本発明を実施するための最良の形態の動作を説明する。
図８に示すように、左隣のブロックの動きベクトルを（ｘ，ｙ）＝（−４、３）とする。また、探索範囲の最大値を３１、最小値を５、ａの値を２、ｂの値を１とする。このとき水平方向探索範囲はａｂｓ（ｘ）×ａ＝４×２＝８、垂直方向探索範囲はａｂｓ（ｙ）×ｂ＝３×１＝３と算出される。これらの値はいずれも探索範囲の最大値と最小値の間にあるので、これらの値をそのまま用い、（±８，±３）画素の範囲で動きベクトル探索をおこなうことになる。
上述の構成によれば、隣接するブロックの動きベクトルの値を元に探索範囲を求めているため、少ない演算量で適切な探索範囲を決定することができる。一般に、隣接ブロック間では動きベクトルに高い相関関係がある。従って、本実施例の方法で求めた探索範囲は実際の映像の動きとも高い相関があるといえる。
また、本実施例では、隣接するブロックの動きベクトルの水平成分、垂直成分をそれぞれ独立に用いて探索範囲を決定している。従って、映像中の動きに応じて探索範囲の広さ（面積）だけでなくその形状も適応的に変化することができる。例えば、隣接ブロックが水平方向に長い動きベクトルをもつ場合、探索範囲も水平方向に長い形状となる。
【実施例２】  本発明の第２の実施例による動きベクトル探索装置について図４を参照して説明する。
第１の実施例では探索範囲を決定するために、左隣のブロックの動きベクトルの値を用いたが、実施例２では、探索範囲算出処理部２０５が、図４に示すようにすでに動きベクトルが求まっている複数の隣接ブロックから２つ以上のブロックを抽出し、各ブロックの動きベクトルの水平成分、垂直成分それぞれの絶対値の最大値を用いて実施例１のようにａ倍、ｂ倍することにより探索範囲を決定する。ここでａ，ｂは任意の正数とする。
図４では、左、左上、上、右上の４つのブロックの動きベクトルから探索範囲を決定している。
このように周囲の複数のブロックの動きベクトルの最大値を元に探索範囲を決定することにより、左隣のブロックとの間において映像の動きに相関が小さい場合でも適切な探索範囲を決定することが可能になる。
【実施例３】  本発明の第３の実施例による動きベクトル探索装置を説明する。
第３の実施例では、探索範囲算出処理部２０５は、探索範囲を決定すること過程で得られた予測誤差があらかじめ設定された閾値よりも大きくなった場合、探索範囲が適切でないと判断し、探索範囲を初期値に戻す例について説明する。
以下、図５のフローチャートを参照して、第３の実施例の動作を詳細に説明する。
まず、現フレームバッファの先頭のブロックにポインタを合わせる（図５のステップＢ１）。
次に、現在ポイントされているブロックがフレームの先頭ブロックかどうかを調べる（ステップＢ２）。
先頭のブロックの場合は、水平方向探索範囲Ｘを初期値Ｘ０、垂直方向の探索範囲Ｙを初期値Ｙ０とする（ステップＢ３）。初期値Ｘ０とＹ０はあらかじめ設定されているものとする。先頭のブロックでない場合は、一つ前のブロックの動きベクトル探索で得られた最小予測誤差の値を閾値Ｔｈと比較する（ステップＢ４）。
ここで閾値Ｔｈはあらかじめ設定された値とする。
最小予測誤差が閾値Ｔｈよりも大きい場合は、探索範囲が適切でないと判断し、ステップＢ３で探索範囲を初期値に戻す。
最小予測誤差が閾値よりも小さい場合、動きベクトルメモリ２０４に格納されている左隣のブロックの動きベクトルを読み出す（ステップＢ５）。
次に、水平方向探索範囲Ｘを一つ前のブロックの動きベクトル水平成分ｘの絶対値ａｂｓ（ｘ）のａ倍の値とする（ステップＢ６）。ここでａは任意の正数とする。ただし、ここでＸの値は水平方向最大探索範囲Ｘｍａｘと水平方向最小探索範囲Ｘｍｉｎの間に収まるようにクリッピングする（ステップＢ７）。尚、Ｘの値が水平方向最大探索範囲Ｘｍａｘ又は水平方向最小探索範囲Ｘｍｉｎを超える場合には、Ｘの値を水平方向最大探索範囲Ｘｍａｘ又は水平方向最小探索範囲Ｘｍｉｎとする。また、水平方向最大探索範囲Ｘｍａｘと水平方向最小探索範囲Ｘｍｉｎの値はあらかじめ設定されているものとする。
垂直方向探索範囲Ｙは左隣のブロックの動きベクトル垂直成分ｙの絶対値ａｂｓ（ｙ）のｂ倍の値とする（ステップＢ８）。ここでｂは任意の正数とする。ただし、ここでＹの値は水平方向最大探索範囲Ｙｍａｘと水平方向最小探索範囲Ｙｍｉｎの間に収まるようにクリッピングする（ステップＢ９）。垂直方向最大探索範囲Ｙｍａｘと垂直方向最小探索範囲Ｙｍｉｎの値はあらかじめ設定されているものとする。尚、Ｙの値が水平方向最大探索範囲Ｙｍａｘ又は水平方向最小探索範囲Ｙｍｉｎを超える場合には、Ｙの値を水平方向最大探索範囲Ｙｍａｘ又は水平方向最小探索範囲Ｙｍｉｎとする。また、垂直方向最大探索範囲Ｙｍａｘと垂直方向最小探索範囲Ｙｍｉｎの値はあらかじめ設定されているものとする。
これらの処理は、探索範囲算出処理部２０５にておこなわれる。
次に、探索範囲を（±Ｘ、±Ｙ）画素として動きベクトル探索をおこなう（ステップＢ１０）。
次に、ステップＡ１０で得られた動きベクトルを動きベクトルメモリに格納する（ステップＢ１１）。
次に、ステップＡ１０でおこなった動きベクトル探索の結果得られた予測誤差をメモリに格納する（ステップＢ１２）。
これらの処理は動き探索処理部２０３にておこなわれる。
フレーム内のすべてのブロックについて動きベクトル探索処理が完了したかを調べる（ステップＢ１３）。
まだ、探索処理をおこなっていないブロックがある場合は、次のブロックにポインタを移動させ（ステップＢ１４）、ステップＢ２にもどり動きベクトル探索処理を継続する。すべてのブロックの処理が完了していれば、そのフレームの動きベクトル探索処理を終了する。
上述の構成によれば、１フレームの動きベクトル探索中に、予測誤差があらかじめ設定された閾値よりも大きくなった場合に探索範囲が適切でないと判断し、探索範囲を初期値に戻す。従って、探索精度の低下を最小限に抑えることが可能となる。
第３の実施形においても、上述した第２の実施例のように周囲の複数のブロックの動きベクトルの絶対値の最大値を利用して探索範囲を決定することにより、左に隣接するブロック間の動きベクトルの相関が小さい場合でも適切な探索範囲を決定することが可能となる。
【実施例４】  本発明の第４の実施例による動きベクトル探索装置について説明する。
ブロック間の動きの相関が高い場合は、動きベクトル探索の探索範囲の中心位置を隣接ブロックの動きベクトルが指す位置にシフトすることにより、より狭い探索範囲で正しい動きを検出することが可能になり、さらに演算量を削減できる。そこで、愛４の実施例では、ブロック間の動きの相関が高い場合は、動きベクトル探索の探索範囲の中心位置を隣接ブロックの動きベクトルが指す位置にシフトする例を説明する。以下、図６のフローチャートを参照して動作を説明する。
まず、現フレームバッファの先頭のブロックにポインタを合わせる（図６のステップＣ１）。
次に、現在ポイントされているブロックがフレームの先頭ブロックかどうかを調べる（ステップＣ２）。
先頭のブロックの場合は、水平方向探索範囲Ｘを初期値Ｘ０、垂直方向の探索範囲Ｙを初期値Ｙ０とする（ステップＣ３）。初期値Ｘ０とＹ０はあらかじめ設定されているものとする。
先頭のブロックでない場合は、動きベクトルメモリ２０４に格納されている左隣のブロックの動きベクトルを読み出す（ステップＣ４）。
次に、水平方向探索範囲Ｘを左隣のブロックの動きベクトル水平成分ｘの絶対値ａｂｓ（ｘ）のａ倍の値とする（ステップＣ５）。ここでａは任意の正数とする。ただし、ここでＸの値は水平方向最大探索範囲Ｘｍａｘと水平方向最小探索範囲Ｘｍｉｎの間に収まるようにクリッピングする（ステップＣ６）。尚、Ｘの値が水平方向最大探索範囲Ｘｍａｘ又は水平方向最小探索範囲Ｘｍｉｎを超える場合には、Ｘの値を水平方向最大探索範囲Ｘｍａｘ又は水平方向最小探索範囲Ｘｍｉｎとする。また、水平方向最大探索範囲Ｘｍａｘと水平方向最小探索範囲Ｘｍｉｎの値はあらかじめ設定されているものとする。
垂直方向探索範囲Ｙは左隣のブロックの動きベクトル垂直成分ｙの絶対値ａｂｓ（ｙ）のｂ倍の値とする（ステップＣ７）。ここでｂは任意の正数とする。ただし、ここでＹの値は水平方向最大探索範囲Ｙｍａｘと水平方向最小探索範囲Ｙｍｉｎの間に収まるようにクリッピングする（ステップＣ８）。尚、Ｙの値が水平方向最大探索範囲Ｙｍａｘ又は水平方向最小探索範囲Ｙｍｉｎを超える場合には、Ｙの値を水平方向最大探索範囲Ｙｍａｘ又は水平方向最小探索範囲Ｙｍｉｎとする。また、垂直方向最大探索範囲Ｙｍａｘと垂直方向最小探索範囲Ｙｍｉｎの値はあらかじめ設定されているものとする。
これらの処理は、探索範囲算出処理部２０５にておこなわれる。
次に、探索中心を現在のブロックの位置から左隣のブロックの動きベクトル（ｘ，ｙ）だけ移動した場所とし（ステップＣ９）、探索範囲を（±Ｘ、±Ｙ）画素として動きベクトル探索をおこなう（ステップＣ１０）。
次にステップＡ１０で得られた動きベクトルを保存するために動きベクトルメモリに格納する（ステップＣ１１）。
これらの処理は動き探索処理部２０３にておこなわれる。
フレーム内のすべてのブロックについて動きベクトル探索処理が完了したかを調べる（ステップＣ１２）。
まだ探索処理をおこなっていないブロックがある場合は次のブロックにポインタを移動させ（ステップＣ１３）、ステップＣ２にもどり動きベクトル探索処理を継続する。すべてのブロックの処理が完了していれば、そのフレームの動きベクトル探索処理を終了する。
上述の如く、本実施例では、第１の実施例の構成に加えて、探索範囲の中心を隣接ブロックの動きベクトルが指す位置に移動させて動きベクトル探索を行っている。このことにより、ブロック間で動きベクトルの相関が大きい場合はより狭い探索範囲で正しい動きを検出することが可能となる。
尚、第４の実施例においても、第２の実施例のように周囲の複数のブロックの動きベクトルの絶対値の最大値を利用して探索範囲を決定することにより、探索精度を向上させることが可能になる。また、同様に第３の実施例のようにフレームの途中で探索範囲を初期値に戻すことで探索精度を向上させることも可能である。
【実施例５】  本発明の第５の実施例による動きベクトル探索装置を説明する。
第５の実施例では、上述した第１の実施例から第４の実施例に示される動きベクトル探索装置をコンピュータシステムにより実行する例を説明する。
図７はコンピュータシステムを示すブロック図である。
このコンピュータシステムには、プログラム制御プロセッサ７０１が装備されている。プログラム制御プロセッサ７０１には、現フレームバッファ７１１および参照フレームバッファ７１２の他に、必要なプログラムを格納したプログラムメモリ７０２と動きベクトルメモリ７１３、が接続されている。
プログラムメモリ７０２には、本発明による動きベクトル探索を実行するためのメインプログラムの他に、上述した動き探索処理部７１４、探索範囲算出処理部７１５をそれぞれ機能的に実現するプログラムモジュールが格納されている。メインプログラムおよび各機能モジュールをプログラム制御プロセッサ７０１で実行することで、本発明による動きベクトル探索が実行される。
以上説明した本発明によれば、以下のような効果が達成される。
第１の効果は、高速に動きベクトル探索ができることである。その理由は、適応的に探索範囲を切替え、動きの小さな映像では狭い探索範囲で探索をおこなうためである。
第２の効果は、高速に探索範囲を決定できることである。その理由は、隣接するブロックの動きベクトルの大きさのみを使い探索範囲を決定するためである。
第３の効果は、適切な探索範囲形状で動きベクトル探索ができることである。その理由は、隣接するブロックの動きベクトルの水平方向、垂直方向それぞれの大きさに応じて探索範囲を決定するためである。
第４の効果は、動きベクトルの符号化効率が向上することである。その理由は、探索範囲が隣接するブロックの動きベクトルから決定されるので隣接ブロック間でベクトルのちらばりが小さくなり、隣接ブロック間でのベクトル差分が小さくなる。そのため、隣接ブロック間の差分が符号化される動きベクトルの符号化効率が向上するからである。
【産業上の利用可能性】  本発明によれば、映像中のあるフレーム中の任意の画素群が他のフレーム中のどの部分に存在するかを調べるといった用途に適用できる。
【図１】
2005036887.tif 000003
【図２】
2005036887.tif 000004
【図３】
2005036887.tif 000005
【図４】
2005036887.tif 000006
【図５】
2005036887.tif 000007
【図６】
2005036887.tif 000008
【図７】
2005036887.tif 000009
【図８】
2005036887.tif 000010
【手続補正書】
【提出日】平成17年10月25日(2005.10.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【書類名】請求の範囲
【請求項１】動画像の符号化における動きベクトルを探索する動きベクトル探索装置において、
検出した動きベクトルを記憶する手段と、
探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段とを有し、
周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分でそれぞれ異なる正の定数を乗算し、これを探索範囲の一辺として動きベクトル探索処理をおこなうことを特徴とする動きベクトル探索装置。
【請求項２】前記探索範囲を決定する手段は、探索範囲の最大値及び最小値を、水平成分と垂直成分のそれぞれについて独立して設定しておき、算出された探索範囲が前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する手段を更に有することを特徴とする請求項１に記載の動きベクトル探索装置。
【請求項３】前記探索範囲を決定する手段は、探索範囲の最小値を、最大値とは独立に設定することを特徴とする請求項２に記載の動きベクトル探索装置。
【請求項４】動画像の符号化における動きベクトルを探索する動きベクトル探索装置において、
検出した動きベクトルを記憶する手段と、
探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段とを有し、
探索範囲の最大値及び最小値を、水平成分と垂直成分のそれぞれについて独立して設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する手段を更に有することを特徴とする動きベクトル探索装置。
【請求項５】ビデオ符号化装置であって、
検出した動きベクトルを記憶する手段と、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段とを有し、周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分でそれぞれ異なる正の定数を乗算し、これを探索範囲の一辺として動きベクトル探索処理をおこなうことを特徴とするビデオ符号化装置。
【請求項６】前記探索範囲を決定する手段は、探索範囲の最大値及び最小値を、水平成分と垂直成分のそれぞれについて独立設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する手段を更に有することを特徴とする請求項５に記載のビデオ符号化装置。
【請求項７】前記探索範囲を決定する手段は、探索範囲の最小値を、最大値とは独立に設定することを特徴とする請求項６に記載のビデオ符号化装置。
【請求項８】ビデオ符号化装置であって、
検出した動きベクトルを記憶する手段と、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段とを有し、探索範囲の最大値及び最小値を、水平成分と垂直成分のそれぞれについて独立して設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する手段を更に有することを特徴とするビデオ符号化装置。
【請求項９】動画像の符号化における動きベクトルを探索する方法において、
検出した動きベクトルを記憶しておき、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定し、周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分それぞれ異なる正の定数を乗算し、これを探索範囲の一辺として動きベクトル探索処理をおこなうことを特徴とする動きベクトル探索方法。
【請求項１０】探索範囲の最大値及び最小値を、水平成分と垂直成分のそれぞれについて独立して設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する手段を更に有することを特徴とする請求項９に記載の動きベクトル探索方法。
【請求項１１】探索範囲の最小値を、最大値とは独立に設定することを特徴とする請求項１０に記載の動きベクトル探索方法。
【請求項１２】動画像の符号化における動きベクトルを探索する方法において、
検出した動きベクトルを記憶しておき、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定し、探索範囲の最大値及び最小値を、水平成分と垂直成分のそれぞれについて独立して設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する手段を更に有することを特徴とする動きベクトル探索方法。
【請求項１３】請求項９から請求項１２のいずれかに記載の動きベクトル探索方法を用いて、ビデオ符号化を行うことを特徴とするビデオ符号化方法。
【請求項１４】動画像の符号化における動きベクトル探索を実行するコンピュータシステムにおいて、
対象画像データを格納する対象画像バッファと、
参照画像を格納する参照画像バッファと、
動きベクトルを記憶する動きベクトルメモリと、
動画像の符号化における動きベクトル探索をコンピュータに実行させるための命令からなるプログラムを格納するプログラムメモリと、
前記プログラムを実行するプログラム制御プロセッサと
を有し、
前記プログラムは、前記プログラム制御プロセッサに、動きベクトルメモリ中に記憶されている周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分でそれぞれ異なる正の定数を乗算し、これを探索範囲の一辺として動きベクトル探索を行わせることを特徴とするコンピュータシステム。
【請求項１５】前記プログラムは、探索範囲の最大値及び最小値を、水平成分と垂直成分のそれぞれについて独立して設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する手段を更に有することを特徴とする請求項１４に記載のコンピュータシステム。
【請求項１６】前記プログラムは、探索範囲の最小値を、最大値とは独立に設定することを特徴とする請求項１５に記載のコンピュータシステム。
【請求項１７】動画像の符号化における動きベクトル探索を実行するコンピュータシステムにおいて、
対象画像データを格納する対象画像バッファと、
参照画像を格納する参照画像バッファと、
動きベクトルを記憶する動きベクトルメモリと、
動画像の符号化における動きベクトル探索をコンピュータに実行させるための命令からなるプログラムを格納するプログラムメモリと、
前記プログラムを実行するプログラム制御プロセッサとを有し、
前記プログラムは、探索範囲の最大値及び最小値を、水平成分と垂直成分のそれぞれについて独立して設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する手段を更に有することを特徴とするコンピュータシステム。
【請求項１８】動画像の符号化における動きベクトルを探索するコンピュータにおける制御プログラムであって、
前記プログラムは前記コンピュータを、
探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段と、
決定した探索範囲で動きベクトル探索処理を行う手段を有し、
周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分それぞれ異なる正の定数を乗算し、これを探索範囲の一辺として動きベクトル探索を行わせるように機能させることを特徴とする制御プログラム。
【請求項１９】前記プログラムは前記コンピュータを、探索範囲の最大値及び最小値を、水平成分と垂直成分のそれぞれについて独立して設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する手段として機能させることを特徴とする請求項１８に記載のプログラム。
【請求項２０】前記プログラムは、探索範囲の最小値を、最大値とは独立に設定することを特徴とする請求項１９に記載のプログラム。
【請求項２１】動画像の符号化における動きベクトルを探索するコンピュータにおける制御プログラムであって、
前記プログラムは前記コンピュータを、
探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段と、
決定した探索範囲で動きベクトル探索処理を行う手段を有し、
前記プログラムは、探索範囲の最大値及び最小値を、水平成分と垂直成分のそれぞれについて独立して設定しておき、算出された探索範囲が、前記最大値又は前記最小値を超える場合には、前記最大値又は前記最小値を探索範囲として決定する手段として機能させることを特徴とするプログラム。




【手続補正書】
【提出日】平成18年5月24日(2006.5.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
動画像の符号化における動きベクトルを探索する動きベクトル探索装置において、
探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段を有し、
周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分でそれぞれ異なる正の定数を乗算し、
これを探索範囲の一辺として動きベクトル探索処理をおこなう装置であって、
前記垂直方向の乗算定数を前記水平方向の乗算定数よりも小さくすることを特徴とする動きベクトル探索装置。
【請求項２】
ビデオ符号化装置であって、
探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段とを有し、周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分でそれぞれ異なる正の定数を乗算し、これを探索範囲の一辺として動きベクトル探索処理をおこなう装置であって、
前記垂直方向の乗算定数を前記水平方向の乗算定数よりも小さくすることを特徴とするビデオ符号化装置。
【請求項３】
動画像の符号化における動きベクトルを探索する方法において、
探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定し、
周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分それぞれ異なる正の定数を乗算し、これを探索範囲の一辺として動きベクトル探索処理をおこなう方法であって、
前記垂直方向の乗算定数を前記水平方向の乗算定数よりも小さくすることを特徴とする動きベクトル探索方法。
【請求項４】
請求項３に記載の動きベクトル探索方法を用いて、ビデオ符号化を行うことを特徴とするビデオ符号化方法。
【請求項５】
動画像の符号化における動きベクトル探索を実行するコンピュータシステムにおいて、
対象画像データを格納する対象画像バッファと、参照画像を格納する参照画像バッファと、
動きベクトルを記憶する動きベクトルメモリと、動画像の符号化における動きベクトル探索をコンピュータに実行させるための命令からなるプログラムを格納するプログラムメモリと、
前記プログラムを実行するプログラム制御プロセッサとを有し、
前記プログラムは、前記プログラム制御プロセッサに、動きベクトルメモリ中に記憶されている周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分でそれぞれ異なる正の定数を乗算し、これを探索範囲の一辺として動きベクトル探索を行わせるプログラムであって、
前記垂直方向の乗算定数を前記水平方向の乗算定数よりも小さくすることを特徴とするコンピュータシステム。
【請求項６】
動画像の符号化における動きベクトルを探索するコンピュータにおける制御プログラムであって、前記プログラムは前記コンピュータを、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段と、
決定した探索範囲で動きベクトル探索処理を行う手段を有し、周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分それぞれ異なる正の定数を乗算し、これを探索範囲の一辺として動きベクトル探索を行わせるプログラムであって、
前記垂直方向の乗算定数を前記水平方向の乗算定数よりも小さくすることを特徴とする制御プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動き補償予測符号化技術に関し、特に動きベクトル探索方法、動きベクトル探索装置及びその動きベクトル探索プログラムに関する。
【背景技術】
【０００２】
動画像信号を記録、あるいは伝送する際の圧縮符号化では、符号化効率を高めるために画像フレーム間の相関を利用した符号化方法が一般に用いられる。画像フレーム間の相関を利用する符号化方式は動き補償予測符号化と呼ばれ、ＭＰＥＧ(Moving Picture Experts Group)などで採用されている。
【０００３】
動き補償予測符号化では、フレーム間における映像の動きの情報(動きベクトル)と、動きベクトルによって生成される予測画像と符号化中のフレームとの差分画像(予測誤差)を符号化する。画像フレーム間の相関が大きければ、予測誤差が小さくなり、符号化する情報量を小さくでき、圧縮率を向上させることができる。
【０００４】
動き補償予測符号化では、一般に、フレームを１６×１６画素などの一定サイズのブロックに分割し、分割したブロックごとに動きベクトルを割り当てる。具体的には、すでに符号化が完了しているフレーム（参照フレーム）の中から、ブロックごとに相関が最も大きくなる場所を探し、そのブロック間の差分を求め、符号化する。
【０００５】
相関が大きくなる場所を探す処理を動きベクトル探索という。相関の大小は、参照フレームと符号化中フレームとのブロック内の各画素の差異を総和することで評価できる。
【０００６】
動きベクトル探索の処理において、フレームのどの領域を探索するかは任意である。狭い範囲を探索すれば探索に要する演算量は少なくすむが、動きの大きな映像が入力された場合に適切な動きベクトルが検出できなくなり符号化効率が低下してしまう。一方、広い範囲を探索すれば動きの大きな映像に対して適切な動き補償予測が可能になり符号化効率は向上するが演算量が膨大になってしまう。従って、映像中の動きの大きさに応じて適応的に探索範囲を切替えることが望ましい。
【０００７】
動きベクトル探索において探索範囲を適応的に切替える装置の一例が、特開平５−３２８３３３（文献１）、特開２０００−１３４６２８（文献２）に記載されている。
【０００８】
文献１に記載されている動きベクトル探索装置は、図１に示すように、動きベクトル検出回路と、動きベクトルメモリと、探索範囲判定器と、探索範囲選択器とから構成されている。
【０００９】
このような構成を有する従来の動きベクトル探索装置はつぎのように動作する。
【００１０】
すなわち、動きベクトルメモリに蓄えられた過去に検出した複数の動きベクトルのヒストグラムを計測し、計測したヒストグラムに応じて適切な探索範囲が探索範囲判定器により決定される。探索範囲選択器では有限種類の探索範囲が用意されており、探索範囲判定器での決定に従い、１つの探索範囲が選択される。
【００１１】
文献２に記載されている動きベクトル探索装置では、まず一つおきのブロックの動きベクトルを先に求める。次にこの動きベクトルの値が、残りのブロックでの動きベクトル探索の探索範囲決定に利用される。
【００１２】
【特許文献１】特開平５−３２８３３３
【特許文献２】特開２０００−１３４６２８
【発明の開示】
【発明が解決しようとする課題】
【００１３】
文献１で開示されている方法を用いた場合、過去に求めた動きベクトルのヒストグラムを常に計測しなければならないので、探索範囲を求めるために余分な演算量が必要になるという問題があった。また、最終的に用いられる探索範囲が有限種類しか用意されておらず、選択された探索範囲が最適なものではない可能性があった。
【００１４】
文献２で開示されている方法を用いた場合、先に動きベクトルを求めるブロックは探索範囲が固定されており、不適切な探索範囲で動きベクトル探索が実行される可能性があった。また、半分のブロックしか適応的に探索範囲を切替えることができないので、探索範囲を適応的に切替えることにより得られる効果が半減されるという問題があった。
【００１５】
そこで、本発明は上記課題に鑑みて発明されたものであって、その目的は、少ない演算量で探索範囲を決定し、適切な探索範囲で動きベクトル探索できる新規な動きベクトル探索方法、装置及びプログラムを提供することにある。
【課題を解決するための手段】
【００１６】
上記課題を解決する第１の発明は、動画像の符号化における動きベクトルを探索する動きベクトル探索装置において、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段を有し、周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分でそれぞれ異なる正の定数を乗算し、これを探索範囲の一辺として動きベクトル探索処理をおこなう装置であって、前記垂直方向の乗算定数を前記水平方向の乗算定数よりも小さくすることを特徴とする。
【００１７】
上記課題を解決する第２の発明は、ビデオ符号化装置であって、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段とを有し、周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分でそれぞれ異なる正の定数を乗算し、これを探索範囲の一辺として動きベクトル探索処理をおこなう装置であって、前記垂直方向の乗算定数を前記水平方向の乗算定数よりも小さくすることを特徴とする。
【００１８】
上記課題を解決する第３の発明は、動画像の符号化における動きベクトルを探索する方法において、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定し、周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分それぞれ異なる正の定数を乗算し、これを探索範囲の一辺として動きベクトル探索処理をおこなう方法であって、前記垂直方向の乗算定数を前記水平方向の乗算定数よりも小さくすることを特徴とする。
【００１９】
上記課題を解決する第４の発明は、請求項３に記載の動きベクトル探索方法を用いて、ビデオ符号化を行うことを特徴とする。
【００２０】
上記課題を解決する第５の発明は、動画像の符号化における動きベクトル探索を実行するコンピュータシステムにおいて、
対象画像データを格納する対象画像バッファと、参照画像を格納する参照画像バッファと、動きベクトルを記憶する動きベクトルメモリと、動画像の符号化における動きベクトル探索をコンピュータに実行させるための命令からなるプログラムを格納するプログラムメモリと、前記プログラムを実行するプログラム制御プロセッサとを有し、前記プログラムは、前記プログラム制御プロセッサに、動きベクトルメモリ中に記憶されている周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分でそれぞれ異なる正の定数を乗算し、これを探索範囲の一辺として動きベクトル探索を行わせるプログラムであって、前記垂直方向の乗算定数を前記水平方向の乗算定数よりも小さくすることを特徴とする。
【００２１】
上記課題を解決する第６の発明は、動画像の符号化における動きベクトルを探索するコンピュータにおける制御プログラムであって、前記プログラムは前記コンピュータを、探索が完了した周囲ブロックの動きベクトルの大きさから探索範囲を決定する手段と、決定した探索範囲で動きベクトル探索処理を行う手段を有し、周囲ブロックの動きベクトルの水平成分および垂直成分それぞれについて大きさが最大となるものを選び、この大きさに水平成分、垂直成分それぞれ異なる正の定数を乗算し、これを探索範囲の一辺として動きベクトル探索を行わせるプログラムであって、前記垂直方向の乗算定数を前記水平方向の乗算定数よりも小さくすることを特徴とする。
【発明の効果】
【００２２】
以上説明した本発明によれば、以下のような効果が達成される。
【００２３】
第１の効果は、高速に動きベクトル探索ができることである。その理由は、適応的に探索範囲を切替え、動きの小さな映像では狭い探索範囲で探索をおこなうためである。
【００２４】
第２の効果は、高速に探索範囲を決定できることである。その理由は、隣接するブロックの動きベクトルの大きさのみを使い探索範囲を決定するためである。
【００２５】
第３の効果は、適切な探索範囲形状で動きベクトル探索ができることである。その理由は、隣接するブロックの動きベクトルの水平方向、垂直方向それぞれの大きさに応じて探索範囲を決定するためである。
【００２６】
第４の効果は、動きベクトルの符号化効率が向上することである。その理由は、探索範囲が隣接するブロックの動きベクトルから決定されるので隣接ブロック間でベクトルのちらばりが小さくなり、隣接ブロック間でのベクトル差分が小さくなる。そのため、隣接ブロック間の差分が符号化される動きベクトルの符号化効率が向上するからである。
【発明を実施するための最良の形態】
【００２７】
本発明の動きベクトル探索装置は、動きベクトルを探索する動きベクトル探索処理部と、求めた動きベクトルを記憶しておく動きベクトルメモリと、探索範囲を決定する探索範囲算出処理部とを備えている。
【００２８】
探索範囲算出処理部は、動きベクトルメモリからすでに求めた隣接ブロックの動きベクトルを取出し、隣接ブロックの動きベクトルの値をもとに適切な探索範囲を決定する。このような構成を採用し、動きベクトル探索における探索範囲を決定することにより本発明の目的を達成することができる。
【実施例１】
【００２９】
本発明の第１の実施例について図面を参照して詳細に説明する。
【００３０】
図２を参照すると、本発明の第１の実施例における動きベクトル探索装置は、符号化中のフレームのデータを格納する現フレームバッファ２０１と、参照フレームを格納する参照フレームバッファ２０２と、動きベクトル探索処理をおこなう動き探索処理部２０３と、求めた動きベクトルを記憶しておく動きベクトルメモリ２０４と、探索範囲を決定する探索範囲算出処理部２０５とから構成されている。
【００３１】
次に、図２及び図３のフローチャートを参照し、実施例１の動作について詳細に説明する。
【００３２】
まず、現フレームバッファ２０１の先頭のブロックにポインタを合わせる（図３のステップＡ１）。
【００３３】
次に、現在ポイントされているブロックがフレームの先頭ブロックかどうかを調べる（ステップＡ２）。
【００３４】
先頭のブロックの場合は、水平方向探索範囲Xを初期値X0、垂直方向の探索範囲Yを初期値Y0とする（ステップＡ３）。初期値X0とY0とはあらかじめ設定されているものとする。
【００３５】
一方、先頭のブロックでない場合は、次に動きベクトルメモリ２０４に格納されている左隣のブロックの動きベクトル(x,y)を読み出す（ステップＡ４）。
【００３６】
水平方向探索範囲Xを左隣のブロックの動きベクトル水平成分ｘの絶対値abs(x)のa倍の値とする（ステップＡ５）。ここでaは任意の正数とする。ただし、ここでXの値は水平方向最大探索範囲Xmaxと水平方向最小探索範囲Xminの間に収まるようにクリッピングする（ステップＡ６）。尚、Xの値が水平方向最大探索範囲Xmax又は水平方向最小探索範囲Xminを超える場合には、Xの値を水平方向最大探索範囲Xmax又は水平方向最小探索範囲Xminとする。また、水平方向最大探索範囲Xmaxと水平方向最小探索範囲Xminの値はあらかじめ設定されているものとする。
【００３７】
垂直方向探索範囲Yは左隣のブロックの動きベクトル垂直成分yの絶対値abs(y)のb倍の値とする（ステップＡ７）。ここでbは任意の正数とする。ただし、ここでYの値は水平方向最大探索範囲Ymaxと水平方向最小探索範囲Yminの間に収まるようにクリッピングする（ステップＡ８）。尚、Yの値が水平方向最大探索範囲Ymax又は水平方向最小探索範囲Yminを超える場合には、Yの値を水平方向最大探索範囲Ymax又は水平方向最小探索範囲Yminとする。また、垂直方向最大探索範囲Ymaxと垂直方向最小探索範囲Yminの値はあらかじめ設定されているものとする。
【００３８】
これらの処理は、探索範囲算出処理部２０５にておこなわれる。
【００３９】
次に探索範囲を（±X、±Y）画素として動きベクトル探索をおこなう（ステップＡ９）。
【００４０】
次にステップＡ９で得られた動きベクトルを動きベクトルメモリ２０４に格納する（ステップＡ１０）。
【００４１】
これらの処理は動き探索処理部２０３にておこなわれる。
【００４２】
フレーム内のすべてのブロックについて動きベクトル探索処理が完了したかを調べる（ステップＡ１１）。
【００４３】
まだ動きベクトル探索をおこなっていないブロックがある場合は次のブロックにポインタを移動させ（ステップＡ１２）、ステップＡ２にもどり動きベクトル探索処理を継続する。すべてのブロックの処理が完了していれば、そのフレームの動きベクトル探索処理を終了する。
【００４４】
次に、具体的な実施例を用いて本発明を実施するための最良の形態の動作を説明する。
【００４５】
図８に示すように、左隣のブロックの動きベクトルを（x,y）=（-4、3）とする。また、探索範囲の最大値を31、最小値を5、aの値を2、bの値を1とする。このとき水平方向探索範囲はabs(x)×a=
4×2 = 8、垂直方向探索範囲はabs(y)×b= 3×1 = 3と算出される。これらの値はいずれも探索範囲の最大値と最小値の間にあるので、これらの値をそのまま用い、（±8,±3）画素の範囲で動きベクトル探索をおこなうことになる。
【００４６】
上述の構成によれば、隣接するブロックの動きベクトルの値を元に探索範囲を求めているため、少ない演算量で適切な探索範囲を決定することができる。一般に、隣接ブロック間では動きベクトルに高い相関関係がある。従って、本実施例の方法で求めた探索範囲は実際の映像の動きとも高い相関があるといえる。
【００４７】
また、本実施例では、隣接するブロックの動きベクトルの水平成分、垂直成分をそれぞれ独立に用いて探索範囲を決定している。従って、映像中の動きに応じて探索範囲の広さ(面積)だけでなくその形状も適応的に変化することができる。例えば、隣接ブロックが水平方向に長い動きベクトルをもつ場合、探索範囲も水平方向に長い形状となる。
【実施例２】
【００４８】
本発明の第２の実施例による動きベクトル探索装置について図４を参照して説明する。
【００４９】
第１の実施例では探索範囲を決定するために、左隣のブロックの動きベクトルの値を用いたが、実施例２では、探索範囲算出処理部２０５が、図４に示すようにすでに動きベクトルが求まっている複数の隣接ブロックから２つ以上のブロックを抽出し、各ブロックの動きベクトルの水平成分、垂直成分それぞれの絶対値の最大値を用いて実施例１のようにa倍、ｂ倍することにより探索範囲を決定する。ここでａ，ｂは任意の正数とする。
【００５０】
図４では、左、左上、上、右上の４つのブロックの動きベクトルから探索範囲を決定している。
【００５１】
このように周囲の複数のブロックの動きベクトルの最大値を元に探索範囲を決定することにより、左隣のブロックとの間において映像の動きに相関が小さい場合でも適切な探索範囲を決定することが可能になる。
【実施例３】
【００５２】
本発明の第３の実施例による動きベクトル探索装置を説明する。
【００５３】
第３の実施例では、探索範囲算出処理部２０５は、探索範囲を決定すること過程で得られた予測誤差があらかじめ設定された閾値よりも大きくなった場合、探索範囲が適切でないと判断し、探索範囲を初期値に戻す例について説明する。
【００５４】
以下、図５のフローチャートを参照して、第３の実施例の動作を詳細に説明する。
【００５５】
まず、現フレームバッファの先頭のブロックにポインタを合わせる（図５のステップＢ１）。
【００５６】
次に、現在ポイントされているブロックがフレームの先頭ブロックかどうかを調べる（ステップＢ２）。
【００５７】
先頭のブロックの場合は、水平方向探索範囲Xを初期値X0、垂直方向の探索範囲Yを初期値Y0とする（ステップＢ３）。初期値X0とY0はあらかじめ設定されているものとする。先頭のブロックでない場合は、一つ前のブロックの動きベクトル探索で得られた最小予測誤差の値を閾値Thと比較する（ステップＢ４）。
【００５８】
ここで閾値Thはあらかじめ設定された値とする。
【００５９】
最小予測誤差が閾値Thよりも大きい場合は、探索範囲が適切でないと判断し、ステップＢ３で探索範囲を初期値に戻す。
【００６０】
最小予測誤差が閾値よりも小さい場合、動きベクトルメモリ２０4に格納されている左隣のブロックの動きベクトルを読み出す（ステップＢ５）。
【００６１】
次に、水平方向探索範囲Xを一つ前のブロックの動きベクトル水平成分ｘの絶対値abs(x)のa倍の値とする（ステップＢ６）。ここでａは任意の正数とする。ただし、ここでXの値は水平方向最大探索範囲Xmaxと水平方向最小探索範囲Xminの間に収まるようにクリッピングする（ステップＢ７）。尚、Xの値が水平方向最大探索範囲Xmax又は水平方向最小探索範囲Xminを超える場合には、Xの値を水平方向最大探索範囲Xmax又は水平方向最小探索範囲Xminとする。また、水平方向最大探索範囲Xmaxと水平方向最小探索範囲Xminの値はあらかじめ設定されているものとする。
【００６２】
垂直方向探索範囲Yは左隣のブロックの動きベクトル垂直成分yの絶対値abs(y)のb倍の値とする（ステップＢ８）。ここでｂは任意の正数とする。ただし、ここでYの値は水平方向最大探索範囲Ymaxと水平方向最小探索範囲Yminの間に収まるようにクリッピングする（ステップＢ９）。垂直方向最大探索範囲Ymaxと垂直方向最小探索範囲Yminの値はあらかじめ設定されているものとする。尚、Yの値が水平方向最大探索範囲Ymax又は水平方向最小探索範囲Yminを超える場合には、Yの値を水平方向最大探索範囲Ymax又は水平方向最小探索範囲Yminとする。また、垂直方向最大探索範囲Ymaxと垂直方向最小探索範囲Yminの値はあらかじめ設定されているものとする。
【００６３】
これらの処理は、探索範囲算出処理部２０５にておこなわれる。
【００６４】
次に、探索範囲を（±X、±Y）画素として動きベクトル探索をおこなう（ステップＢ１０）。
【００６５】
次に、ステップＡ１０で得られた動きベクトルを動きベクトルメモリに格納する（ステップＢ１１）。
【００６６】
次に、ステップＡ１０でおこなった動きベクトル探索の結果得られた予測誤差をメモリに格納する（ステップＢ１２）。
【００６７】
これらの処理は動き探索処理部２０３にておこなわれる。
【００６８】
フレーム内のすべてのブロックについて動きベクトル探索処理が完了したかを調べる（ステップＢ１３）。
【００６９】
まだ、探索処理をおこなっていないブロックがある場合は、次のブロックにポインタを移動させ（ステップＢ１４）、ステップＢ２にもどり動きベクトル探索処理を継続する。すべてのブロックの処理が完了していれば、そのフレームの動きベクトル探索処理を終了する。
【００７０】
上述の構成によれば、１フレームの動きベクトル探索中に、予測誤差があらかじめ設定された閾値よりも大きくなった場合に探索範囲が適切でないと判断し、探索範囲を初期値に戻す。従って、探索精度の低下を最小限に抑えることが可能となる。
【００７１】
第３の実施形においても、上述した第２の実施例のように周囲の複数のブロックの動きベクトルの絶対値の最大値を利用して探索範囲を決定することにより、左に隣接するブロック間の動きベクトルの相関が小さい場合でも適切な探索範囲を決定することが可能となる。
【実施例４】
【００７２】
本発明の第４の実施例による動きベクトル探索装置について説明する。
【００７３】
ブロック間の動きの相関が高い場合は、動きベクトル探索の探索範囲の中心位置を隣接ブロックの動きベクトルが指す位置にシフトすることにより、より狭い探索範囲で正しい動きを検出することが可能になり、さらに演算量を削減できる。そこで、愛４の実施例では、ブロック間の動きの相関が高い場合は、動きベクトル探索の探索範囲の中心位置を隣接ブロックの動きベクトルが指す位置にシフトする例を説明する。以下、図６のフローチャートを参照して動作を説明する。
【００７４】
まず、現フレームバッファの先頭のブロックにポインタを合わせる（図６のステップＣ１）。
【００７５】
次に、現在ポイントされているブロックがフレームの先頭ブロックかどうかを調べる（ステップＣ２）。
【００７６】
先頭のブロックの場合は、水平方向探索範囲Xを初期値X0、垂直方向の探索範囲Yを初期値Y0とする（ステップＣ３）。初期値X0とY0はあらかじめ設定されているものとする。
【００７７】
先頭のブロックでない場合は、動きベクトルメモリ２０4に格納されている左隣のブロックの動きベクトルを読み出す（ステップＣ４）。
【００７８】
次に、水平方向探索範囲Xを左隣のブロックの動きベクトル水平成分ｘの絶対値abs(x)のa倍の値とする（ステップＣ５）。ここでaは任意の正数とする。ただし、ここでXの値は水平方向最大探索範囲Xmaxと水平方向最小探索範囲Xminの間に収まるようにクリッピングする（ステップＣ６）。尚、Xの値が水平方向最大探索範囲Xmax又は水平方向最小探索範囲Xminを超える場合には、Xの値を水平方向最大探索範囲Xmax又は水平方向最小探索範囲Xminとする。また、水平方向最大探索範囲Xmaxと水平方向最小探索範囲Xminの値はあらかじめ設定されているものとする。
【００７９】
垂直方向探索範囲Yは左隣のブロックの動きベクトル垂直成分yの絶対値abs(y)のb倍の値とする（ステップＣ７）。ここでbは任意の正数とする。ただし、ここでYの値は水平方向最大探索範囲Ymaxと水平方向最小探索範囲Yminの間に収まるようにクリッピングする（ステップＣ８）。尚、Yの値が水平方向最大探索範囲Ymax又は水平方向最小探索範囲Yminを超える場合には、Yの値を水平方向最大探索範囲Ymax又は水平方向最小探索範囲Yminとする。また、垂直方向最大探索範囲Ymaxと垂直方向最小探索範囲Yminの値はあらかじめ設定されているものとする。
【００８０】
これらの処理は、探索範囲算出処理部２０５にておこなわれる。
【００８１】
次に、探索中心を現在のブロックの位置から左隣のブロックの動きベクトル(x,y)だけ移動した場所とし（ステップＣ９）、探索範囲を（±X、±Y）画素として動きベクトル探索をおこなう（ステップＣ１０）。
【００８２】
次にステップＡ１０で得られた動きベクトルを保存するために動きベクトルメモリに格納する（ステップＣ１１）。
【００８３】
これらの処理は動き探索処理部２０３にておこなわれる。
【００８４】
フレーム内のすべてのブロックについて動きベクトル探索処理が完了したかを調べる（ステップＣ１２）。
【００８５】
まだ探索処理をおこなっていないブロックがある場合は次のブロックにポインタを移動させ（ステップＣ１３）、ステップＣ２にもどり動きベクトル探索処理を継続する。すべてのブロックの処理が完了していれば、そのフレームの動きベクトル探索処理を終了する。
【００８６】
上述の如く、本実施例では、第１の実施例の構成に加えて、探索範囲の中心を隣接ブロックの動きベクトルが指す位置に移動させて動きベクトル探索を行っている。このことにより、ブロック間で動きベクトルの相関が大きい場合はより狭い探索範囲で正しい動きを検出することが可能となる。
【００８７】
尚、第４の実施例においても、第２の実施例のように周囲の複数のブロックの動きベクトルの絶対値の最大値を利用して探索範囲を決定することにより、探索精度を向上させることが可能になる。また、同様に第３の実施例のようにフレームの途中で探索範囲を初期値に戻すことで探索精度を向上させることも可能である。
【実施例５】
【００８８】
本発明の第５の実施例による動きベクトル探索装置を説明する。
【００８９】
第５の実施例では、上述した第１の実施例から第４の実施例に示される動きベクトル探索装置をコンピュータシステムにより実行する例を説明する。
【００９０】
図７はコンピュータシステムを示すブロック図である。
【００９１】
このコンピュータシステムには、プログラム制御プロセッサ７０１が装備されている。プログラム制御プロセッサ７０１には、現フレームバッファ７１１および参照フレームバッファ７１２の他に、必要なプログラムを格納したプログラムメモリ７０２と動きベクトルメモリ７１３、が接続されている。
【００９２】
プログラムメモリ７０２には、本発明による動きベクトル探索を実行するためのメインプログラムの他に、上述した動き探索処理部７１４、探索範囲算出処理部７１５をそれぞれ機能的に実現するプログラムモジュールが格納されている。メインプログラムおよび各機能モジュールをプログラム制御プロセッサ７０１で実行することで、本発明による動きベクトル探索が実行される。
【産業上の利用可能性】
【００９３】
本発明によれば、映像中のあるフレーム中の任意の画素群が他のフレーム中のどの部分に存在するかを調べるといった用途に適用できる。
【図面の簡単な説明】
【００９４】
【図１】図１は適応的に探索範囲変化させる動きベクトル探索法の従来例を示すブロック図である。
【図２】図２は本発明の実施例１の構成を示すブロック図である。
【図３】図３は本発明の実施例１の動作を示すフローチャートである。
【図４】図４は本発明の実施例２の動作の具体例を示す図である。
【図５】図５は本発明の実施例３の動作を示すフローチャートである。
【図６】図６は本発明の実施例４の動作を示すフローチャートである。
【図７】図７は本発明による動きベクトル探索装置の実施例であるコンピュータシステムを示すブロック図である。
【図８】図８は本発明の実施例１の具体的な動作を示す図である。
【符号の説明】
【００９５】
１０１    動きベクトル検出回路
１０２    動きベクトルメモリ
１０３    検索範囲判定器
１０４    検索範囲選択器
２０１    現フレームバッファ
２０２    参照フレームバッファ
２０３    動き探索処理部
２０４    動きベクトルメモリ
２０５    探索範囲算出処理部
７０１    プログラム制御プロセッサ
７０２    プログラムメモリ
７１１    現フレームバッファ
７１２    参照フレームバッファ
７１３    動きベクトルメモリ
７１４    動き探索処理
７１５    探索範囲算出処理
【国際調査報告】
2005036887.tif 000011
2005036887.tif 000012
2005036887.tif 000013
2005036887.tif 000014