(57)【要約】【課題】  従来は、第一段階で求めた予測誤差が最小となる点ａから周囲８候補点の中に、最小予測誤差点が無い場合が多々あるため、直交変換後の残差成分が増加し、符号化効率が低下することがある。【解決手段】  第二段階探索領域Ａ決定部１２は、第一段階の最小予測誤差点ａを求めた探索領域における第一の画素間隔Ｒよりも間隔が小である第二の画素間隔ｒの探索領域を、最小予測誤差点ａが中心位置となるように配置した後、最小予測誤差点ａを含む範囲内で最小予測誤差点ｂの方向へ平行移動し、平行移動後の探索領域を第二段階探索領域Ａとして決定する。これにより、最小予測誤差点ａと最小予測誤差点ｂとの間の、最終の最小予測誤差点ｃが存在する可能性の高い領域を第二段階探索領域Ａとされ、最小予測誤差点ｃが存在する可能性の高い候補点を候補に入れつつ無駄な探索点を省くことができる。【選択図】            図１
2005123760.tif 000002
【特許請求の範囲】
【請求項１】
動画像の動き補償予測に必要な動きベクトルを検出する動きベクトル検出装置において、
第一段階探索として、第一の画素間隔の複数の探索点から、符号化画像信号と参照画像信号の各ブロック間の誤差評価値が最小となる第一の最小誤差評価値点を求める第一の最小誤差評価値点算出手段と、
前記第一の最小誤差評価値点の周囲の複数の候補点から第二の最小誤差評価値点を求める第二の最小誤差評価値点算出手段と、
第二段階探索として、前記第一の最小誤差評価値点と前記第二の最小誤差評価値点とが入力され、前記第一の画素間隔よりも間隔が小である第二の画素間隔の探索領域を、前記第一の最小誤差評価値点が中心位置となるように配置した後、前記第一の最小誤差評価値点を含む範囲内で前記第二の最小誤差評価値点の方向へ平行移動し、平行移動後の前記探索領域を第二段階探索領域として決定する第二段階探索領域決定手段と、
前記第二段階探索領域の中の探索点から誤差評価値が最小となる第三の最小誤差評価値点を求める第三の最小評価値点算出手段と、
前記第三の最小誤差評価値点に基づく動きベクトルを出力する動きベクトル出力手段と
を有することを特徴とする動きベクトル検出装置。
【請求項２】
動画像の動き補償予測に必要な動きベクトルを、コンピュータにより検出させる動きベクトル検出プログラムにおいて、
前記コンピュータを、
第一段階探索として、第一の画素間隔の複数の探索点から、符号化画像信号と参照画像信号の各ブロック間の誤差評価値が最小となる第一の最小誤差評価値点を求める第一の最小誤差評価値点算出手段と、
前記第一の最小誤差評価値点の周囲の複数の候補点から第二の最小誤差評価値点を求める第二の最小誤差評価値点算出手段と、
第二段階探索として、前記第一の最小誤差評価値点と前記第二の最小誤差評価値点とが入力され、前記第一の画素間隔よりも間隔が小である第二の画素間隔の探索領域を、前記第一の最小誤差評価値点が中心位置となるように配置した後、前記第一の最小誤差評価値点を含む範囲内で前記第二の最小誤差評価値点の方向へ平行移動し、平行移動後の前記探索領域を第二段階探索領域として決定する第二段階探索領域決定手段と、
前記第二段階探索領域の中の探索点から誤差評価値が最小となる第三の最小誤差評価値点を求める第三の最小評価値点算出手段と、
前記第三の最小誤差評価値点に基づく動きベクトルを出力する動きベクトル出力手段として機能させることを特徴とする動きベクトル検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は動きベクトル検出装置及び動きベクトル検出プログラムに係り、特に動画像の圧縮符号化の際の動き補償に必要な動きベクトルを検出する動きベクトル検出装置及び動きベクトル検出プログラムに関する。
【背景技術】
【０００２】
ＭＰＥＧ（Moving Picture Experts Group）に代表される動画像の圧縮符号化では、フレーム間の相関を用いて符号量を圧縮する動き補償予測符号化が多く用いられる。動き補償予測符号化では、符号化画像と参照画像のブロックの位置関係を示す動きベクトルが必要である。この動きベクトルは、ブロック間の誤差評価値が小さいほど動き補償予測をした際に、符号化効率が向上する。
【０００３】
上記の誤差評価値とは、一般に、ブロックマッチングを用いて、ブロック間の相違を絶対差分和や差分二乗和などで表現した予測誤差や、動きベクトル符号量やＤＣＴ（離散コサイン変換：Discrete Cosine Transform）係数符号量に基づいた、符号量換算などで表現したものである。以下、誤差評価値を小さくするための動きベクトル検出装置について予測誤差を例として説明する。
【０００４】
最も予測誤差が小さくなる動きベクトル検出装置として、フルサーチを用いた動きベクトル検出装置がある。フルサーチは動きベクトル探索範囲内のすべての候補点で、現フレームと参照フレームの各ブロックの画素データとの差分絶対値の総和を総当りに調べて、参照フレーム内の上記の総和が最も小さなブロックを参照ブロックとして最小の予測誤差を与える動きベクトルを検出する。フルサーチでは、探索範囲内において、必ず最小の予測誤差を持つ点が検出できるが、膨大な演算量が必要という課題がある。
【０００５】
この課題を解決する動きベクトル検出装置として、３ステップサーチを用いた動きベクトル検出装置が従来より知られている（例えば、特許文献１参照）。この特許文献１記載の動きベクトル検出装置では、図１４に示すように、第一段階として、動きベクトル検出範囲内の３０１で示す２画素おきの候補点群について最小予測誤差点ａを求め、第二段階として、第一段階で求まった最小予測誤差点ａと、最小予測誤差点ａから１画素おきの周囲８候補点３０３について最小予測誤差点ｄを求め、第三段階として、第二段階と同様に、第二段階で求まった最小予測誤差点ｄと、最小予測誤差点ｄから１／２画素おきの周囲８候補点３０５について最小予測誤差点ｅを求めることで、動きベクトルを検出する。この３ステップサーチでは、フルサーチと比較して演算量は削減されるが、第二段階、第三段階ともに８点の候補点について予測誤差を計算する必要があり、演算量はまだ多い。
【０００６】
そこで、上記の３ステップサーチの第二段階、第三段階の演算量を削減する動きベクトル検出装置も従来提案されている（例えば、特許文献２参照）。この特許文献２記載の動きベクトル検出装置では、図１５に示すように、第一段階で求めた最小予測誤差点ａから２画素おきの周囲８候補点４０１のそれぞれの予測誤差を記憶しておく。続いて、第二段階サーチにおいて、上記の最小予測誤差点ａと周囲の８候補点４０１の計９点の候補点のうち、周囲の８候補点のそれぞれの予測誤差を比較し、予測誤差の小さい順にｎ個（ｎ＜８）の候補点を選択する。ここで、一例として、ｎ＝３とし、図１６に４０１’で示す３つの候補点が予測誤差の小さい方から３つの候補点であるものとする。
【０００７】
また、第二段階サーチの候補点は図１６に４０２〜４０９で示すように、上記の最小予測誤差点ａに対して１／２画素おきの周囲８候補点であるが、この中で先に選択した３つの候補点４０１’に最も近い位置にある３つの黒四角印の候補点４０３、４０４、４０５が第二段階サーチの対象として選択される。
【０００８】
続いて、これら３つの黒四角印の候補点４０３、４０４、４０５のそれぞれについて予測誤差を求め、これらの予測誤差のうち最も小さな予測誤差の候補点を、その予測誤差と共に記憶する。最後に、第一段階での最小予測誤差点ａでの予測誤差と、第二段階での最小予測誤差の候補点の予測誤差とを比較し、値が小さい方の候補点を動きベクトルとして検出して出力する。
【０００９】
次に、特許文献２に記載の従来の動きベクトル検出装置の構成について図１７を用いて説明する。図１７は従来の動きベクトル検出装置の一例のブロック図を示す。従来の動きベクトル検出装置は、図１７に示すように、第一段階探索制御部３１と、第二段階探索点決定部３２と、符号化画像メモリ供給部３３と、参照画像メモリ供給部３４と、予測誤差演算部３５と、予測誤差及び計算点記憶部３６と、最小予測誤差点判定部３７と、隣接領域予測誤差記憶部３８と、最小予測誤差及び最小予測誤差点ａ記憶部３９と、最小予測誤差及び最小予測誤差点ｃ記憶部４０と、動きベクトル出力部４１とから構成されている。
【００１０】
第一段階探索制御部３１は、第一段階の画素間隔での探索点を、参照画像メモリ供給部３４に供給する。第二段階探索点決定部３２は、隣接領域予測誤差記憶部３８から第一段階で記憶した隣接領域の予測誤差が入力され、最小予測誤差及び最小予測誤差点ａ記憶部３９から最小予測誤差点ａが入力され、第一段階で記憶した最小予測誤差点ａと隣接領域の予測誤差から、第二段階の画素間隔での探索点を決定し、第二段階の画素間隔での探索点を、参照画像メモリ供給部３４に供給する。
【００１１】
符号化画像メモリ供給部３３は、本装置外部より符号化画像信号が入力され、符号化ブロックの画像を予測誤差演算部３５に供給する。参照画像メモリ供給部３４は、本装置外部より、参照画像信号が入力され、第一段階探索制御部３１又は第二段階探索点決定部３２から探索点が入力され、探索点の位置のブロックの画像を予測誤差演算部３５に供給する。
【００１２】
予測誤差演算部３５は、符号化画像メモリ供給部３３と、参照画像メモリ供給部３４からそれぞれのブロックの画像が入力され、両ブロック間の予測誤差を計算し、計算された予測誤差と計算点を予測誤差及び計算点記憶部３６に供給する。予測誤差及び計算点記憶部３６は、予測誤差演算部３５から予測誤差と計算点が入力され、予測誤差と計算点を記憶し、記憶した予測誤差と計算点を最小予測誤差点判定部３７に供給する。また、予測誤差及び計算点記憶部３６は、最小予測誤差点判定部３７から隣接領域の予測誤差を記憶するような命令が入力された場合は、計算点の周囲８候補点の予測誤差を、隣接領域予測誤差記憶部３８に供給する。
【００１３】
最小予測誤差点判定部３７は、第一段階探索中の場合は、予測誤差及び計算点記憶部３６から予測誤差と計算点が入力され、最小予測誤差及び最小予測誤差点ａ記憶部３９から今までの中の最小予測誤差が入力され、予測誤差及び計算点記憶部３６から入力された予測誤差を、最小予測誤差及び最小予測誤差点ａ記憶部３９から入力された最小予測誤差と比較することで、予測誤差及び計算点記憶部３６から入力された予測誤差が最小予測誤差かどうかを判定し、予測誤差及び計算点記憶部３６から入力された予測誤差が最小予測誤差だった場合、予測誤差及び計算点記憶部３６から入力された予測誤差と計算点を、最小予測誤差及び最小予測誤差点ａ記憶部３９に供給し、隣接領域の予測誤差を記憶するような命令を予測誤差及び計算点記憶部３６に供給する。
【００１４】
また、最小予測誤差点判定部３７は、第二段階探索中の場合は、予測誤差及び計算点記憶部３６から予測誤差と計算点が入力され、最小予測誤差及び最小予測誤差点ｃ記憶部４０から今までの中の最小予測誤差が入力され、予測誤差及び計算点記憶部３６から入力された予測誤差を、最小予測誤差及び最小予測誤差点ｃ記憶部４０から入力された最小予測誤差と比較することで、予測誤差及び計算点記憶部３６から入力された予測誤差が最小予測誤差かどうかを判定し、予測誤差及び計算点記憶部３６から入力された予測誤差が最小予測誤差だった場合、予測誤差及び計算点記憶部３６から入力された予測誤差と計算点を、最小予測誤差及び最小予測誤差点ｃ記憶部４０に供給する。
【００１５】
隣接領域予測誤差記憶部３８は、予測誤差及び計算点記憶部３６から計算点の周囲８候補点の予測誤差が入力され、計算点の周囲８候補点の予測誤差を記憶し、第一段階の探索終了後、周囲８候補点の予測誤差を、第二段階探索点決定部３２に供給する。最小予測誤差及び最小予測誤差点ａ記憶部３９は、第一段階探索中に、最小予測誤差点判定部３７において、最小予測誤差点が更新された場合に、最小予測誤差点判定部３７から最小予測誤差及び最小予測誤差点ａが入力され、最小予測誤差及び最小予測誤差点ａを記憶する。また、予測誤差及び計算点記憶部３６において、計算点が更新される毎に、最小予測誤差点判定部３７に最小予測誤差を供給し、第一段階の探索終了後、第二段階探索点決定部３２に最小予測誤差点ａを供給する。
【００１６】
最小予測誤差及び最小予測誤差点ｃ記憶部４０は、第二段階探索中に、最小予測誤差点判定部３７において、最小予測誤差点が更新された場合に、最小予測誤差点判定部３７から最小予測誤差及び最小予測誤差点ｃが入力され、最小予測誤差及び最小予測誤差点ｃを記憶する。また、最小予測誤差及び最小予測誤差点ｃ記憶部４０は、予測誤差及び計算点記憶部３６において、計算点が更新される毎に最小予測誤差点判定部３７に最小予測誤差を供給し、第二段階の探索終了後、動きベクトル出力部４１に、最小予測誤差点ｃを供給する。動きベクトル出力部４１は、最小予測誤差及び最小予測誤差点ｃ記憶部４０から最小予測誤差点ｃが供給され、最小予測誤差点ｃに基づく動きベクトルを出力端子４２から本装置外部に出力する。
【００１７】
次に、図１７中の隣接領域予測誤差記憶部３８の動作について、図１８のフローチャートを用いてより詳細に説明する。図１８は、従来の動きベクトル検出装置の隣接領域予測誤差記憶部３８の動作説明用フローチャートである。
【００１８】
まず、第一段階探索において（ステップＳ１）、予測誤差及び計算点記憶部３６から周囲８候補点の予測誤差が入力されたかどうか判定し（ステップＳ２）、入力された場合は、周囲８候補点の予測誤差を記憶（更新）し（ステップＳ３）、第一段階探索の次の探索点の動作に移る。予測誤差及び計算点記憶部３６から何も入力されなかった場合は、何もせずに第一段階探索の次の探索点の動作に移る。これを第一段階探索が終了するまで繰り返し（ステップＳ４）、第一段階探索終了時、周囲８候補点の予測誤差を第二段階探索点決定部３２に供給する（ステップＳ５）。
【００１９】
次に、図１中の第二段階探索点決定部３２の動作について、図１９のフローチャートを用いてより詳細に説明する。図１９は、従来の動きベクトル検出装置の第二段階探索点決定部３２の動作説明用フローチャートである。まず、隣接領域予測誤差記憶部３８から入力された、第一段階で求めた最小予測誤差点ａの周囲８候補点を、予測誤差の小さいものから順に並べる（ステップＳ１１）。並べられた周囲８候補点の予測誤差の小さい上位３点を、小さいものから順にｍｉｎ１，ｍｉｎ２，ｍｉｎ３とする（ステップＳ１２）。
【００２０】
続いて、最小予測誤差及び最小予測誤差点ａ記憶部３９から入力された、第一段階での最小予測誤差点ａから最終画素間隔ｒ（ｒ＜Ｒ）の周囲８候補点を求め、周囲８候補点をｃａｎ１〜ｃａｎ８とする（ステップＳ１３）。そして、ｃａｎ１〜ｃａｎ８の中でｍｉｎ１に最も近い点を第二段階探索点とする（ステップＳ１６）。
【００２１】
同様に、ｍｉｎ２，ｍｉｎ３についても最も近い点を第二段階探索点とする（ステップＳ１４〜ステップＳ１７）。このように求まった第二段階の探索点を参照画像メモリ供給部３４に供給する（ステップＳ１８）。なお、このフローチャートでは、周囲８候補点から３候補点を選択する方法を示したが、選択する候補点は７以下であれば何個でもよい。
【００２２】
【特許文献１】特開昭５５−１５８７８４号公報
【特許文献２】特開平１０−１６４５８６号公報
【発明の開示】
【発明が解決しようとする課題】
【００２３】
このように、従来の動きベクトル検出装置では、フルサーチや３ステップサーチの演算量を削減するために、第一段階として、参照フレーム上の画素間隔Ｒの候補点群から予測誤差が最小となる候補点ａを求めると共に、最小予測誤差点ａの周囲８候補点の予測誤差を記憶し、第二段階として、第一段階で求めた最小予測誤差点ａから画素間隔ｒ（ただし、ｒ＜Ｒ）の周囲８候補点の中から、第一段階で記憶した周囲８候補点の予測誤差を用いて、ｎ（ｎ＜８）個の候補点を選択し、選択されたｎ個の候補点について予測誤差が最小となる点を求めていた。
【００２４】
そのため、従来の動きベクトル検出装置では、例えば第一段階の画素間隔Ｒが２画素間隔で、第二段階の画素間隔ｒ（ｒ＜Ｒ）が１／２画素間隔などの場合、第一段階で求めた予測誤差が最小となる点ａから１／２画素間隔の周囲８候補点の中に、最小予測誤差点が無い場合が多々ある。当然その８候補点からｎ（ｎ＜８）個の候補点を選択しても、最小予測誤差点は無く、この中から動きベクトルとなる点を検出していたため、直交変換後の残差成分が増加し、符号化効率が低下するという課題がある。
【００２５】
本発明は以上の点に鑑みなされたもので、最小予測誤差点が存在する可能性の高い領域を、探索領域に決定することで精度の高い動きベクトル検出を実現し得る動きベクトル検出装置及び動きベクトル検出プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２６】
上記目的を達成するため、第１の発明の動きベクトル検出装置は、動画像の動き補償予測に必要な動きベクトルを検出する動きベクトル検出装置において、第一段階探索として、第一の画素間隔の複数の探索点から、符号化画像信号と参照画像信号の各ブロック間の誤差評価値が最小となる第一の最小誤差評価値点を求める第一の最小誤差評価値点算出手段と、第一の最小誤差評価値点の周囲の複数の候補点から第二の最小誤差評価値点を求める第二の最小誤差評価値点算出手段と、第二段階探索として、第一の最小誤差評価値点と第二の最小誤差評価値点とが入力され、第一の画素間隔よりも間隔が小である第二の画素間隔の探索領域を、第一の最小誤差評価値点が中心位置となるように配置した後、第一の最小誤差評価値点を含む範囲内で第二の最小誤差評価値点の方向へ平行移動し、平行移動後の探索領域を第二段階探索領域として決定する第二段階探索領域決定手段と、第二段階探索領域の中の探索点から誤差評価値が最小となる第三の最小誤差評価値点を求める第三の最小評価値点算出手段と、第三の最小誤差評価値点に基づく動きベクトルを出力する動きベクトル出力手段とを有することを特徴とする。
【００２７】
また、上記の目的を達成するため、第２の発明の動きベクトル検出プログラムは、上記の第１の発明の動きベクトル検出装置をコンピュータにより実現するためのプログラムとしたことを特徴とする。
【００２８】
上記の第１及び第２の発明では、第一段階で第一の最小誤差評価値点を求めた探索領域における第一の画素間隔よりも間隔が小である第二の画素間隔の探索領域を、第一の最小誤差評価値点が中心位置となるように配置した後、第一の最小誤差評価値点を含む範囲内で第二の最小誤差評価値点の方向へ平行移動し、平行移動後の探索領域を第二段階探索領域として決定するようにしたため、第一の最小誤差評価値点と第二の最小誤差評価値点との間の、最終の第三の最小誤差評価値点が存在する可能性の高い領域を第二段階探索領域とすることができる。
【発明の効果】
【００２９】
本発明によれば、第一段階で第一の最小誤差評価値点を求めた探索領域における第一の画素間隔よりも間隔が小である第二の画素間隔の探索領域を、第一の最小誤差評価値点が中心位置となるように配置した後、第一の最小誤差評価値点を含む範囲内で第二の最小誤差評価値点の方向へ平行移動し、平行移動後の探索領域を第二段階探索領域として決定することにより、第一の最小誤差評価値点と第二の最小誤差評価値点との間の、最終の第三の最小誤差評価値点が存在する可能性の高い領域を第二段階探索領域とするようにしたため、最終の最小誤差評価値点が存在する可能性の高い候補点を候補に入れつつ無駄な探索点を省くことができ、これにより、符号化効率を向上できると共に、演算量を削減できる。
【発明を実施するための最良の形態】
【００３０】
次に、本発明を実施するための最良の形態について図面と共に説明する。図１は本発明になる動きベクトル検出装置の一実施の形態のブロック図を示す。同図に示すように、本実施の形態の動きベクトル検出装置は、第一段階探索制御部１１と、第二段階探索領域Ａ決定部１２と、符号化画像メモリ供給部１３と、参照画像メモリ供給部１４と、予測誤差演算部１５と、予測誤差及び計算点記憶部１６と、最小予測誤差点判定部１７と、隣接領域最小予測誤差点ｂ記憶部１８と、最小予測誤差及び最小予測誤差点ａ記憶部１９と、最小予測誤差及び最小予測誤差点ｃ記憶部２０と、動きベクトル出力部２１とから構成されている。
【００３１】
かかる構成の本実施の形態の動きベクトル検出装置は、第一段階として、参照フレーム上の画素間隔Ｒの探索点群から予測誤差が最小となる候補点（最小予測誤差点）ａを求めると共に、最小予測誤差点ａの周囲８候補点の中の最小予測誤差点ｂを記憶し、第二段階として、第一段階で求めた最小予測誤差点ａと、最小予測誤差点ａの周囲８候補点の中の最小予測誤差点ｂに応じて、最小予測誤差点が存在する可能性の高い領域を、最終画素間隔ｒ（ｒ＜Ｒ）の探索領域Ａに決定することで、最小予測誤差点が存在する可能性の高い候補点を候補に入れつつ無駄な探索点を省き、符号化効率を向上し演算量を削減するものである。
【００３２】
ここで、第一段階探索制御部１１は、第一段階の画素間隔での探索点を参照画像メモリ供給部１４に供給する。第二段階探索領域Ａ決定部１２は、隣接領域最小予測誤差点ｂ記憶部１８から隣接領域最小予測誤差点ｂが入力され、最小予測誤差及び最小予測誤差点ａ記憶部１９から、第一段階の最小予測誤差点ａが入力され、第一段階で記憶した最小予測誤差点ａと隣接領域最小予測誤差点ｂから、第二段階での探索領域Ａを決定し、決定された探索領域内の探索点を、第二段階の探索点として参照画像メモリ供給部１４に供給する。
【００３３】
符号化画像メモリ供給部１３は、本装置外部より符号化画像信号が入力され、符号化ブロックの画像信号を予測誤差演算部１５に供給する。参照画像メモリ供給部１４は、本装置外部より参照画像信号が入力される一方、第一段階探索制御部１１又は第二段階探索領域Ａ決定部１２から探索点が入力され、その入力探索点の位置のブロックの参照画像信号を予測誤差演算部１５に供給する。
【００３４】
予測誤差演算部１５は、符号化画像メモリ供給部１３と、参照画像メモリ供給部１４からそれぞれのブロックの画像信号が入力され、入力された両ブロック間の予測誤差を計算し、計算して得た予測誤差と計算点を予測誤差及び計算点記憶部１６に供給する。予測誤差及び計算点記憶部１６は、予測誤差演算部１５から予測誤差と計算点が入力され、それら予測誤差と計算点を記憶し、記憶した予測誤差と計算点を最小予測誤差点判定部１７に供給する。また、予測誤差及び計算点記憶部１６は、最小予測誤差点判定部１７から隣接領域の予測誤差を記憶するような命令が入力された場合は、計算点の周囲８候補点の予測誤差を、隣接領域最小予測誤差点ｂ記憶部１８に供給する。
【００３５】
最小予測誤差点判定部１７は、第一段階探索中の場合は、予測誤差及び計算点記憶部１６から予測誤差と計算点が入力されると共に、最小予測誤差及び最小予測誤差点ａ記憶部１９から今までの中の最小予測誤差が入力され、予測誤差及び計算点記憶部１６から入力された予測誤差を、最小予測誤差及び最小予測誤差点ａ記憶部１９から入力された最小予測誤差と比較することで、予測誤差及び計算点記憶部１６から入力された予測誤差が最小予測誤差かどうかを判定し、予測誤差及び計算点記憶部１６から入力された予測誤差が最小予測誤差だった場合、予測誤差及び計算点記憶部１６から入力されたその予測誤差と計算点を、最小予測誤差及び最小予測誤差点ａ記憶部１９に供給する一方、隣接領域の予測誤差を記憶するような命令を予測誤差及び計算点記憶部１６に供給する。
【００３６】
また、最小予測誤差点判定部１７は、第二段階探索中の場合は、予測誤差及び計算点記憶部１６から予測誤差と計算点が入力されると共に、最小予測誤差及び最小予測誤差点ｃ記憶部２０から今までの中の最小予測誤差が入力され、予測誤差及び計算点記憶部１６から入力された予測誤差を、最小予測誤差及び最小予測誤差点ｃ記憶部２０から入力された最小予測誤差と比較することで、予測誤差及び計算点記憶部１６から入力された予測誤差が最小予測誤差かどうかを判定し、予測誤差及び計算点記憶部１６から入力された予測誤差が最小予測誤差だった場合、予測誤差及び計算点記憶部１６から入力されたその予測誤差と計算点を、最小予測誤差及び最小予測誤差点ｃ記憶部２０に供給する。
【００３７】
隣接領域最小予測誤差点ｂ記憶部１８は、予測誤差及び計算点記憶部１６から計算点の周囲８候補点の予測誤差が入力され、入力された計算点の周囲８候補点の予測誤差の中の最小予測誤差点ｂを計算し、第一段階の探索終了後、周囲８候補点の中の最小予測誤差点ｂを、第二段階探索領域Ａ決定部１２に供給する。
【００３８】
最小予測誤差及び最小予測誤差点ａ記憶部１９は、第一段階探索中に最小予測誤差点判定部１７において、最小予測誤差点ａが更新された場合に、最小予測誤差点判定部１７から最小予測誤差及び最小予測誤差点ａが入力され、最小予測誤差及び最小予測誤差点ａを記憶する。また、最小予測誤差及び最小予測誤差点ａ記憶部１９は、予測誤差及び計算点記憶部１６において、計算点が更新される毎に、最小予測誤差点判定部１７に最小予測誤差を供給し、第一段階の探索終了後、第二段階探索領域Ａ決定部１２に最小予測誤差点ａを供給する。
【００３９】
最小予測誤差及び最小予測誤差点ｃ記憶部２０は、第二段階探索中に最小予測誤差点判定部１７において、最小予測誤差点が更新された場合に、最小予測誤差点判定部１７から最小予測誤差及び最小予測誤差点ｃが入力され、最小予測誤差及び最小予測誤差点ｃを記憶する。また、予測誤差及び計算点記憶部１６において、計算点が更新される毎に、最小予測誤差点判定部１７に最小予測誤差を供給し、第二段階の探索終了後、動きベクトル出力部２１に最小予測誤差点ｃを供給する。
【００４０】
動きベクトル出力部２１は、最小予測誤差及び最小予測誤差点ｃ記憶部２０から最小予測誤差点ｃが供給され、最小予測誤差点ｃに基づく動きベクトルを、出力端子２２から本装置外部に出力する。
【００４１】
次に、隣接領域最小予測誤差点ｂ記憶部１８の動作について、図２のフローチャートを参照してより詳細に説明する。図２は図１の動きベクトル検出装置の隣接領域予測誤差点ｂ記憶部１８の動作説明用フローチャートである。
【００４２】
まず、第一段階探索を開始すると（ステップＳ２１）、予測誤差及び計算点記憶部１６から周囲８候補点の予測誤差が入力されたかどうか判定し（ステップＳ２２）、周囲８候補点の予測誤差が入力された場合は、周囲８候補点の予測誤差の最小予測誤差点ｂを計算し（ステップＳ２３）、計算された最小予測誤差点ｂを記憶（更新）し（ステップＳ２４）、第一段階探索の次の探索点の動作に移る（ステップＳ２５）。
【００４３】
他方、ステップＳ２２において、予測誤差及び計算点記憶部１６から何も入力されなかったと判定された場合は、何もせずに第一段階探索の次の探索点の動作に移る（ステップＳ２５）。これを第一段階探索が終了するまで繰り返し、第一段階探索終了時、最小予測誤差点ｂを第二段階探索領域Ａ決定部１２に供給する（ステップＳ２６）。
【００４４】
なお、図３に示すように、第一段階探索での最小予測誤差点ａが第一段階探索領域の端などの場合、第一段階探索での最小予測誤差点ａの周囲には５つの候補点１００の予測誤差しかなく、８つの候補点の予測誤差が無い場合があるが、この場合でも隣接領域予測誤差点ｂ記憶部１８は、存在する候補点（この場合５つの候補点１００）の予測誤差から、最小予測誤差点ｂを計算し、計算された最小予測誤差点ｂを、最小予測誤差点ｂとして第二段階探索領域Ａ決定部１２に供給する。このように、隣接領域予測誤差点ｂ記憶部１８は、どのような場合でも例外なく、隣接領域の最小予測誤差点ｂが求めることができ、これにより第二段階探索領域Ａ決定部１２に、例外なく第二段階探索領域Ａを決定させることができる。
【００４５】
次に、第二段階探索領域Ａ決定部１２の動作について図４のフローチャートを参照してより詳細に説明する。図４は図１の動きベクトル検出装置の第二段階探索領域Ａ決定部１２の動作説明用フローチャートである。まず、第一段階の画素間隔Ｒと最終画素間隔ｒ（ｒ＜Ｒ）から、第二段階探索領域Ａの大きさを決定する（ステップＳ３１）。例えば、第一段階の画素間隔Ｒが２画素間隔で、最終画素間隔ｒ（ｒ＜Ｒ）が１／２画素間隔の場合、水平方向３点、垂直方向３点で構成される９つの探索点からなる正方形領域といったように決定する。
【００４６】
続いて、決定された第二段階探索領域Ａを、最小予測誤差及び最小予測誤差点ａ記憶部１９から入力された、最小予測誤差点ａを中心に配置する（ステップＳ３２）。配置された第二段階探索領域Ａを、隣接領域最小予測誤差点ｂ記憶部１８から入力された、隣接領域最小予測誤差点ｂの方向へ平行移動する（ステップＳ３３）。
【００４７】
例えば、第一段階の画素間隔Ｒが２画素間隔で、最終画素間隔ｒ（ｒ＜Ｒ）が１／２画素間隔で、第二段階探索領域Ａが９つの探索点からなる正方形領域の場合であり、図５に示すように、隣接領域最小予測誤差点ｂが、第一段階最小予測誤差点ａの上方向にあった場合、第二段階探索領域Ａ決定部１２は、破線で示した第二段階探索領域Ａを、上方向に１／２画素平行移動して図５に実線で示した領域１０１とする。そして、平行移動した後の第二段階探索領域Ａ（１０１）内の９つの探索点を、第二段階の探索点として参照画像メモリ供給部１４に供給する（ステップＳ３４）。
【００４８】
なお、図６〜図１２に示すように隣接領域最小予測誤差点ｂが、第一段階最小予測誤差点ａの上方向以外にあった場合でも同様に、第二段階探索領域Ａを、隣接領域最小予測誤差点ｂの方向に平行移動することによって、第二段階探索領域Ａを決定する。すなわち、図６は、隣接領域最小予測誤差点ｂが、第二段階探索領域Ａ内の第一段階最小予測誤差点ａの右斜め上方向にあった場合の平行移動後の第二段階探索領域１０２を、図７は隣接領域最小予測誤差点ｂが、第二段階探索領域Ａ内の第一段階最小予測誤差点ａの右横方向にあった場合の平行移動後の第二段階探索領域１０３を、図８は隣接領域最小予測誤差点ｂが、第二段階探索領域Ａ内の第一段階最小予測誤差点ａの右斜め下方向にあった場合の平行移動後の第二段階探索領域１０４をそれぞれ示す。
【００４９】
また、図９は隣接領域最小予測誤差点ｂが、第二段階探索領域Ａ内の第一段階最小予測誤差点ａの下方向にあった場合の平行移動後の第二段階探索領域１０５を、図１０は隣接領域最小予測誤差点ｂが、第二段階探索領域Ａ内の第一段階最小予測誤差点ａの左斜め下方向にあった場合の平行移動後の第二段階探索領域１０６を、図１１は隣接領域最小予測誤差点ｂが、第二段階探索領域Ａ内の第一段階最小予測誤差点ａの左方向にあった場合の平行移動後の第二段階探索領域１０７を、図１２は隣接領域最小予測誤差点ｂが、第二段階探索領域Ａ内の第一段階最小予測誤差点ａの左斜め上方向にあった場合の平行移動後の第二段階探索領域１０８をそれぞれ示す。なお、探索領域の大きさや形が変われば、平行移動する画素数は1/2画素に限定されるものではなく、平行移動後の探索領域内に第一段階最小予測誤差点ａが含まれる範囲内で移動可能である。
【００５０】
このように、本実施の形態では、第一段階で求めた最小予測誤差点ａと、第一段階で求めた最小予測誤差点ａの周囲８候補点の中の最小予測誤差点ｂの間の領域は、最小予測誤差点が存在する可能性の高い領域であることに着目し、この領域を第二段階探索領域Ａに決定するようにしたので、符号化効率が向上する。また、図１３に示すように、従来の３ステップサーチでは、第一段階で求めた最小予測誤差点ａに対して、第二段階以降の探索点は１０９で示すように全部で１６（＝８＋８）点であったが、本装置の第二段階の探索点の数は図５〜図１２に示す第二段階探索領域Ａ（１０１〜１０８）内の８点のため、本実施の形態によれば、３ステップサーチと比較して、演算量が削減できる。
【００５１】
なお、本発明は上記の実施の形態に限定されるものではなく、例えば図４のフローチャート及び図５〜図１２では、隣接領域の候補点の数、第一段階画素間隔Ｒ、最終画素間隔ｒ（ｒ＜Ｒ）、第二段階探索領域の大きさ、平行移動の移動量を、具体的な数値を与えたが、数値はこの値でなくてもよいことは勿論である。
【００５２】
例えば、上記の第一段階の画素間隔Ｒを４画素間隔とし、上記の第二段階の画素間隔ｒを１画素間隔とした他の実施の形態によれば、前記の特許文献１と比較して、国際電気通信連合電気通信標準化部門（ＩＴＵ−Ｔ）のＨ.２６１等の規格の演算量を削減させることができ、前記の特許文献２と比較して、ＩＴＵ−Ｔ  Ｈ.２６１等の規格の符号化効率を向上させることができる。ＩＴＵ−Ｔ  Ｈ.２６１等の規格の動き補償予測では、１画素精度の動き補償予測を用いるためである。
【００５３】
また、上記の第一段階の画素間隔Ｒを２画素間隔とし、上記の第二段階の画素間隔ｒを１／２画素間隔とした更に他の実施の形態によれば、前記の特許文献１と比較して、国際標準化機構（ＩＳＯ）が規格化したＩＳＯ／ＩＥＣ  ＭＰＥＧ−１，ＭＰＥＧ−２や、ＩＴＵ−ＴによるＨ．２６３等の規格の演算量を削減させることができ、前記の特許文献２と比較して、上記のＩＳＯ／ＩＥＣ  ＭＰＥＧ−１，ＭＰＥＧ−２や、ＩＴＵ−ＴＨ．２６３等の符号化効率を向上させることができる。ＩＳＯ／ＩＥＣ  ＭＰＥＧ−１，ＭＰＥＧ−２や、ＩＴＵ−Ｔ  Ｈ.２６３等の動き補償予測では、１／２画素精度の動き補償予測を用いるためである。この実施の形態の動きベクトル検出装置では、図１に示した参照画像メモリ供給部１４として、１／２画素精度の画像メモリを持つことで、図１と同じ構成で実現できる。
【００５４】
更に、上記の第一段階の画素間隔Ｒを１画素間隔とし、上記の第二段階の画素間隔ｒを１／４画素間隔とした、別の実施の形態によれば、前記の特許文献１と比較して、国際標準化機構（ＩＳＯ）が規格化したＩＳＯ／ＩＥＣ  ＭＰＥＧ−４  ＡＳＰやＩＴＵ−Ｔ  Ｈ．２６４等の規格による演算量を削減させることができ、前記の特許文献２と比較して、ＩＳＯ／ＩＥＣ  ＭＰＥＧ−４  ＡＳＰやＩＴＵ−Ｔ  Ｈ.２６４等の符号化効率を向上させることができる。ＩＳＯ／ＩＥＣ  ＭＰＥＧ−４  ＡＳＰやＩＴＵ−Ｔ  Ｈ.２６４等の動き補償予測では、１／４画素精度の動き補償予測を用いるためである。この場合の動きベクトル検出装置は、図１に示した参照画像メモリ供給部１４として、１／４画素精度の画像メモリを持つことで、図１と同じ構成で実現できる。
【００５５】
１画素精度未満の画素は、１画素精度の画素を補完して作成されるため、第二段階の探索点の画素間隔ｒ（ｒ＜Ｒ）を１画素間隔未満とすると、第一段階で求める周囲８候補点の中の最小予測誤差点ｂと、第一段階で求める周囲８候補点の中の最小予測誤差点ｂから決定される第二段階の探索領域Ａの相関は、最終画素間隔ｒ（ｒ＜Ｒ）が１画素間隔以上の画素の場合の相関よりも高いため、第一段階で求める周囲８候補点の中の最小予測誤差点ｂの信頼度が高まり、符号化効率をより向上できる。
【００５６】
なお、第二段階探索領域Ａ内の探索方法は、上記の実施の形態で説明したフルサーチではなく、第一段階の最小予測誤差点ａ、隣接領域最小予測誤差点ｂ、第一段階画素間隔Ｒ、最終画素間隔ｒ（ｒ＜Ｒ）などを考慮してどのような探索方法を与えてもよい。例えば、第二段階探索領域Ａ内に探索初期位置を与え、公知の特許文献（特開２００３−８７７９９号公報）に記載されているような、与えられた探索初期位置より追跡的なサーチをしてもよく、この場合には、第二段階探索領域Ａ内のすべての点について探索をしなくて済み、演算量が更に削減される。
【００５７】
ここで、追跡探索中に、探索点が第二段階探索領域Ａの水平方向の端になった場合には、次の探索を垂直方向のみ行い、同様に探索点が第二段階探索領域Ａの垂直方向の端になった場合には、次の探索を水平方向のみ行う。そして、探索点が水平方向、垂直方向ともに端になった場合は探索を終了することで、第二段階探索領域Ａ内の候補点のみを探索しつつ、演算量を削減することができる。
【００５８】
なお、本発明は以上の実施の形態に限定されるものではなく、例えば、上記した動きベクトル検出装置の機能をコンピュータに実現させるためのプログラムを含むものである。このプログラムは、記録媒体から読みとられてコンピュータに取り込まれてもよいし、通信ネットワークを介して伝送されてコンピュータに取り込まれてもよい。また、以上の実施の形態では、誤差評価値の一例として予測誤差について説明したが、予測誤差以外の動きベクトル符号量やＤＣＴ係数符号量などを用いることも可能である。
【図面の簡単な説明】
【００５９】
【図１】本発明の動きベクトル検出装置の一実施の形態のブロック図である。
【図２】図１の動きベクトル検出装置の隣接領域最小予測誤差点ｂ記憶部の動作説明用フローチャートである。
【図３】図１の第一段階最小予測誤差点隣接領域図の一例（端の場合）である。
【図４】図１の動きベクトル検出装置の第二段階探索領域Ａ決定部の動作説明用フローチャートである。
【図５】図１の第二段階最小予測誤差点探索図の一例である。
【図６】図１の第二段階最小予測誤差点探索図（右上の場合）である。
【図７】図１の第二段階最小予測誤差点探索図（右の場合）である。
【図８】図１の第二段階最小予測誤差点探索図（右下の場合）である。
【図９】図１の第二段階最小予測誤差点探索図（下の場合）である。
【図１０】図１の第二段階最小予測誤差点探索図（左下の場合）である。
【図１１】第二段階最小予測誤差点探索図（左の場合）である。
【図１２】第二段階最小予測誤差点探索図（左上の場合）である。
【図１３】３ステップサーチの第二、第三段階探索図である。
【図１４】３ステップサーチの探索図である。
【図１５】第一段階最小予測誤差点隣接領域図である。
【図１６】従来の第二段階最小予測誤差点探索図である。
【図１７】従来の動きベクトル検出装置の一例のブロック図である。
【図１８】従来の動きベクトル検出装置の隣接領域予測誤差記憶部の動作説明用フローチャートである。
【図１９】従来の動きベクトル検出装置の第二段階探索点決定部の動作説明用フローチャートである。
【符号の説明】
【００６０】
１１  第一段階探索制御部
１２  第二段階探索領域Ａ決定部
１３  符号化画像メモリ供給部
１４  参照画像メモリ供給部
１５  予測誤差演算部
１６  予測誤差及び計算点記憶部
１７  最小予測誤差点判定部
１８  隣接領域最小予測誤差点ｂ記憶部
１９  最小予測誤差及び最小予測誤差点ａ記憶部
２０  最小予測誤差及び最小予測誤差ｃ記憶部
２１  動きベクトル出力部
１００  第一段階探索での最小予測誤差点ａの周囲の候補点
１０１〜１０８、Ａ  第二段階探索領域
ａ  第一段階最小予測誤差点
ｂ  第一段階周囲８候補点最小予測誤差点
【図１】
2005123760.tif 000003
【図２】
2005123760.tif 000004
【図３】
2005123760.tif 000005
【図４】
2005123760.tif 000006
【図５】
2005123760.tif 000007
【図６】
2005123760.tif 000008
【図７】
2005123760.tif 000009
【図８】
2005123760.tif 000010
【図９】
2005123760.tif 000011
【図１０】
2005123760.tif 000012
【図１１】
2005123760.tif 000013
【図１２】
2005123760.tif 000014
【図１３】
2005123760.tif 000015
【図１４】
2005123760.tif 000016
【図１５】
2005123760.tif 000017
【図１６】
2005123760.tif 000018
【図１７】
2005123760.tif 000019
【図１８】
2005123760.tif 000020
【図１９】
2005123760.tif 000021