(57)【要約】  【課題】  整数画素以下の精度の動きベクトル検出に要する演算量を低減する。  【解決手段】  差分の正負符号を含む差分特徴量を差分評価値ＳＡＤとともに出力する差分評価値演算部と、隣接する参照ブロック間で差分特徴量を比較する差分特徴量比較部と、差分評価値ＳＡＤと差分特徴量比較結果により動きベクトル検出の終了を判定する終了判定部とを備え、整数画素精度の動きベクトルを検出した際に生成される上記の差分特徴量を用いて、高精度の動きベクトル検出を行う。  【選択図】  図１
2005253015.tif 000002
【特許請求の範囲】
【請求項１】
参照画像内に複数の参照ブロックを段階的に設定しながら、設定された参照ブロックの中から符号化対象画像内のカレントブロックとの類似度が最も高い第１最適ブロックを探索した後、前記参照ブロック間で画素補間して得た１つ以上の内挿ブロックを比較対象に加えて類似度が最も高い第２最適ブロックを求め、当該第２最適ブロックを基に整数画素以下の精度で動きベクトルを検出する動きベクトル検出装置であって、
前記設定された参照ブロックの各々について、前記カレントブロック及び前記参照ブロックの対応画素の差分の正負符号をブロック内の各画素について示す差分特徴量を算出する演算手段と、
隣接する参照ブロックについて算出された差分特徴量を比較することにより、当該隣接する何れの参照ブロックの類似度よりもそれらの間で画素補間して得られる内挿ブロックの類似度が高い可能性を示す比較結果を出力する比較手段と、
前記比較結果が所定の可能性を示す場合に前記第１最適ブロックの探索を終了すると判定する判定手段と
を備えることを特徴とする動きベクトル検出装置。
【請求項２】
前記演算手段は、前記対応画素の差分の正負符号のみをブロック内の各画素について示す差分特徴量を算出し、
前記比較手段は、前記差分特徴量により示される正負符号が不一致である画素の数を前記比較結果として出力し、
前記判定手段は、前記比較結果が所定のしきい値以上である場合に前記第１最適ブロックの探索を終了すると判定する
ことを特徴とする請求項１に記載の動きベクトル検出装置。
【請求項３】
前記演算手段は、前記対応画素の差分の正負符号に加え、差分の絶対量の量子化値をブロック内の各画素について示す差分特徴量を算出し、
前記比較手段は、前記差分特徴量により示される正負符号が不一致でありかつ量子化値が一致する画素の数を前記比較結果として出力し、
前記判定手段は、前記比較結果が所定のしきい値以上である場合に前記第１最適ブロックの探索を終了すると判定する
ことを特徴とする請求項１に記載の動きベクトル検出装置。
【請求項４】
参照画像内に複数の参照ブロックを段階的に設定しながら、設定された参照ブロックの中から符号化対象画像内のカレントブロックとの類似度が最も高い第１最適ブロックを探索した後、前記参照ブロック間で画素補間して得た１つ以上の内挿ブロックを比較対象に加えて類似度が最も高い第２最適ブロックを求め、当該第２最適ブロックを基に整数画素以下の精度で動きベクトルを検出する動きベクトル検出方法であって、
前記設定された参照ブロックの各々について、前記カレントブロック及び前記参照ブロックの対応画素の差分の正負符号をブロック内の各画素について示す差分特徴量を算出する演算ステップと、
隣接する参照ブロックについて算出された差分特徴量を比較することにより、当該隣接する何れの参照ブロックの類似度よりもそれらの間で画素補間して得られる内挿ブロックの類似度が高いか推定する推定ステップと、
肯定推定された場合に前記第１最適ブロックの探索を終了すると判定する判定ステップと
を含むことを特徴とする動きベクトル検出方法。
【請求項５】
前記推定ステップにおいて肯定推定された内挿ブロックのみを前記比較対象に加えて前記第２最適ブロックを求める
ことを特徴とする請求項４に記載の動きベクトル検出方法。
【請求項６】
参照画像内に設定した複数の参照ブロックの中から符号化対象画像内のカレントブロックとの類似度が最も高い第１最適ブロックを探索した後、前記参照ブロック間で画素補間して得た１つ以上の内挿ブロックを比較対象に加えて類似度が最も高い第２最適ブロックを求め、当該第２最適ブロックを基に整数画素以下の精度で動きベクトルを検出する動きベクトル検出方法であって、
前記参照ブロックの各々について、前記カレントブロック及び前記参照ブロックの対応画素の差分の正負符号をブロック内の各画素について示す差分特徴量を算出する演算ステップと、
隣接する参照ブロックについて算出された差分特徴量を比較することにより、当該隣接する何れの参照ブロックの類似度よりもそれらの間で画素補間して得られる内挿ブロックの類似度が高いか推定する推定ステップと、
を含み、
前記推定ステップにおいて肯定推定された内挿ブロックのみを比較対象に加えて前記第２最適ブロックを求める
ことを特徴とする動きベクトル検出方法。
【請求項７】
前記演算ステップは、前記対応画素の差分の正負符号のみをブロック内の各画素について示す差分特徴量を算出し、
前記推定ステップは、前記差分特徴量により示される正負符号が不一致である画素の数が所定のしきい値以上である場合に肯定推定する
ことを特徴とする請求項４乃至６の何れかに記載の動きベクトル検出方法。
【請求項８】
前記演算ステップは、前記対応画素の差分の正負符号に加え、差分の絶対量の量子化値をブロック内の各画素について示す差分特徴量を算出し、
前記推定ステップは、前記差分特徴量により示される正負符号が不一致でありかつ量子化値が一致する画素の数が所定のしきい値以上である場合に肯定推定する
ことを特徴とする請求項４乃至６の何れかに記載の動きベクトル検出方法。
【請求項９】
符号化対象画像の時間的な前後に表示される第１参照画像及び第２参照画像内にそれぞれ複数設定される第１参照ブロック及び第２参照ブロック、並びに当該第１参照ブロックと当該第２参照ブロックとの間で画素補間して得た１つ以上の時間内挿ブロックの中から、前記符号化対象画像内のカレントブロックとの類似度が最も高い最適ブロックを求め、当該最適ブロックを基に双方向に動きベクトルを検出する動きベクトル検出方法であって、
前記第１参照ブロックの中から類似度が最も高い第１最適ブロックを求めると共に、前記カレントブロック及び当該第１最適ブロックの対応画素の差分の正負符号をブロックの全画素について示す第１差分特徴量を算出する第１演算ステップと、
前記第２参照ブロックを段階的に設定しながら、設定された第２参照ブロックの中から類似度が最も高い第２最適ブロックを探索する探索ステップと、
前記設定された第２参照ブロックの各々について、前記カレントブロック及び前記第２参照ブロックの対応画素の差分の正負符号をブロックの全画素について示す第２差分特徴量を算出する第２演算ステップと、
前記第１差分特徴量と前記第２差分特徴量とを比較することにより、前記第１最適ブロック及び前記第２参照ブロックの何れの類似度よりもそれらの間で画素補間して得られる時間内挿ブロックの類似度が高いか推定する推定ステップと、
肯定推定された場合に前記第２最適ブロックの探索を終了すると判定する判定ステップと
を含むことを特徴とする動きベクトル検出方法。
【請求項１０】
前記第１演算ステップは、前記対応画素の差分の正負符号のみをブロック内の各画素について示す第１差分特徴量を算出し、
前記第２演算ステップは、前記対応画素の差分の正負符号のみをブロック内の各画素について示す第２差分特徴量を算出し、
前記推定ステップは、前記第１差分特徴量と前記第２差分特徴量とにより示される正負符号が不一致である画素の数が所定のしきい値以上である場合に肯定推定する
ことを特徴とする請求項９に記載の動きベクトル検出方法。
【請求項１１】
前記第１演算ステップは、前記対応画素の差分の正負符号に加え、差分の絶対量の量子化値をブロック内の各画素について示す第１差分特徴量を算出し、
前記第２演算ステップは、前記対応画素の差分の正負符号に加え、差分の絶対量の量子化値をブロック内の各画素について示す第１差分特徴量を算出し、
前記推定ステップは、前記第１差分特徴量と前記第２差分特徴量とにより示される正負符号が不一致でありかつ量子化値が一致する画素の数が所定のしきい値以上である場合に肯定推定する
ことを特徴とする請求項９に記載の動きベクトル検出方法。
【請求項１２】
参照画像内に設定した複数の参照ブロックの中から符号化対象画像内のカレントブロックとの類似度が最も高い第１最適ブロックを探索した後、前記参照ブロック間で画素補間して得た１つ以上の内挿ブロックを比較対象に加えて類似度が最も高い第２最適ブロックを求め、当該第２最適ブロックを基に整数画素以下の精度で動きベクトルを検出するためのコンピュータ実行可能なプログラムであって、
請求項４乃至８の少なくとも１つに記載のステップをコンピュータに実行させる
ことを特徴とするプログラム。
【請求項１３】
符号化対象画像の時間的な前後に表示される第１参照画像及び第２参照画像内にそれぞれ複数設定される第１参照ブロック及び第２参照ブロック、並びに当該第１参照ブロックと当該第２参照ブロックとの間で画素補間して得た１つ以上の時間内挿ブロックの中から、前記符号化対象画像内のカレントブロックとの類似度が最も高い最適ブロックを求め、当該最適ブロックを基に双方向に動きベクトルを検出するためのコンピュータ実行可能なプログラムであって、
請求項９乃至１１の少なくとも１つに記載のステップをコンピュータに実行させる
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像圧縮符号化などに用いられる動きベクトル検出を整数画素以下の精度で行うための装置、方法、及びプログラムに関し、特に動きベクトル検出に要する計算量を削減するための技術に関する。
【背景技術】
【０００２】
動画素データは一般に、あるフレームの画像と次のフレームの画像はよく似ているという性質を持つ。これを時間方向の冗長性と言うが、この性質の為に、フレーム間の差分を取る事により、各フレームの画素データを直接保存、もしくは伝送する方式に比べ、全体のデータ量を大幅に削減する事ができる。
動画素データの符号化方式の国際規格であるＭＰＥＧ（Moving Picture Experts Group）−１、−２、及び−４は、ＤＣＴ（Discrete Cosine Transformation ）変換と、動き補償（Motion Compensation）とを組み合わせた画像圧縮技術であり、上記動画素データの時間方向の冗長性を削減する為、フレーム間予測、及び動き補償（Motion Compensation）を行い、膨大な量の動画素データを効率良く圧縮している。
【０００３】
動き補償はまた、動きベクトル補正とも言い、時間軸方向に連続した２枚のフレームの画素データを比較することにより、画面上を移動する物体の動きの大きさと方向を示すベクトル量として動きベクトル（Motion Vector）を検出し、これをフレーム間の差分として符号化する。動きベクトルＭＶの検出には、まず、整数画素精度の動きベクトルＭＶの探索を行い、続いて半画素精度の動きベクトルＭＶ２の探索を行う。
【０００４】
（整数画素精度の動きベクトル検出）
図１０は、動きベクトル検出の概要を示す図である。同図に示すように、動きベクトルの検出においては、まず、時刻Ｔにおける符号化画像ＩT（現フレーム）を、縦横１６画素×１６画素のブロックに分割した中から、１つのブロック（カレントブロックという）を選択し、その左上端の座標を（ｘ，ｙ）とする。
【０００５】
次に、参照画像ＩT-1（参照フレーム）において、Ｘ方向、Ｙ方向、ともに１画素単位の動き量（ｄｘ，ｄｙ）を１つ与える毎に、前記カレントブロックの座標（ｘ，ｙ）の周囲に設定した、サイズＳＲｘ×ＳＲｙ（ブロック単位）の所定の探索範囲内において、左上端の座標が（ｘ＋ｄｘ，ｙ＋ｄｙ）であり、カレントブロックと同じサイズの領域が１つ定まるが、これを参照ブロックという。
【０００６】
上記の動き量（ｄｘ，ｄｙ）を少しずつ変化させながら、上記参照ブロックの画像パターンを、カレントブロックの画像パターンと比較し、その類似度を判定する。
２つの画像パターンの類似度を比較するための量を差分評価値と言い、後述の数式（７）に示す、差分絶対値和ＳＡＤ（Sum of Absolute Difference）や、数式（８）に示す、差分２乗和ＳＳＤ（Sum of Square Difference）などが用いられる。
【０００７】
複数の参照ブロック各々の画像パターンと、カレントブロックの画像パターンの類似度を比較した結果、最も類似度の高い参照ブロック（最適参照ブロックＭＢＫ）を選び、当該選ばれた最適参照ブロックＭＢＫの動き量（ｄｘ、ｄｙ）を、当該カレントブロックに対する整数画素精度の動きベクトルＭＶとする。
上記処理により、現フレーム内の全てのカレントブロックに対して、整数画素精度の動きベクトルＭＶ＝（ｄｘ、ｄｙ）を検出した後、更に精度を向上させる為、精度を半画素に向上させた、半画素精度の動きベクトル探索を行う。
【０００８】
（半画素精度の動きベクトル探索）
半画素精度の動きベクトル探索では、画素データの補間処理によって、「半画素精度の参照ブロック」を作成する。これは、当該検出された動きベクトルＭＶに対応する、画像類似度の高い参照ブロックＢＫの周辺において、隣り合った２つの参照ブロックに対し、画素データの補間（線形補間）を行う事により、それらの中間に位置する、半画素精度の参照ブロックＨＢＫを生成し、これらとカレントブロックとの画像パターンの比較を行う事により、整数画素精度の参照ブロックよりも更に画像類似度の高い参照ブロックを探索し、半画素精度の動きベクトルＭＶ２を検出するものである。
【０００９】
図２７は、半画素精度の動きベクトルＭＶ２の検出における、画素データの補間処理の概要を示す図である。整数画素精度の動きベクトルＭＶの検出で得られた、差分評価値ＳＡＤの最小値に対応した最適参照ブロックＭＢＫの周辺において、同図に示すような、隣り合った２つの画素の中点に対する画素データの補間を行う事により、半画素精度の参照画像を生成する。
【００１０】
図２８は、半画素精度の動きベクトル検出における探索位置を示す図である。同図に示すように、まず、整数画素精度の最適参照ブロックＭＢＫの左上端の画素Ｐ０から、最適参照ブロックＭＢＫに対する（半画素の）動き量を、それぞれ（ｄｘ２，ｄｙ２）＝｛  （−１／２，１／２）、（０，１／２）、（１／２，１／２）、（−１／２，０）、（１／２，０）、（−１／２，−１／２）、（０，−１／２）、（１／２，−１／２）  ｝とする事により、半画素ずつずらした８点、Ｐ１乃至Ｐ８を左上端とする、８個の半画素精度の参照ブロックＨＢＫ１乃至ＨＢＫ８を生成する。
【００１１】
図２９は、上記の様にして生成された、８個の半画素精度の参照ブロックＨＢＫ１乃至ＨＢＫ８の位置関係、及び重なり状態を示す図である。同図に示す様に、半画素ブロックＨＢＫ１乃至ＨＢＫ８は、その大半の画素が、他の半画素ブロックに重なっている。
半画素精度の参照ブロックを生成する為には、整数画素精度の参照ブロックの各画素データから、半画素の位置の画素データを補間する。例えば、図２７に示す４点、Ａ、Ｂ、Ｃ、Ｄの画素データから、これらの４点により囲まれる領域内の半画素位置にある５点、ｅ、ｆ、ｇ、ｈ、ｉの画素データを生成する際には、下記の数式（１）乃至数式（５）の様に、画素データを線形補間する。なお、下記の数式において、／／は、丸め付き平均を表す。
【００１２】
【数１】
2005253015.tif 000003
【００１３】
【数２】
2005253015.tif 000004
【００１４】
【数３】
2005253015.tif 000005
【００１５】
【数４】
2005253015.tif 000006
【００１６】
【数５】
2005253015.tif 000007
上記の様に、まず、整数画素の画素データを補間し、半画素位置にある各画素データを生成する事により、上記の最適参照ブロックＭＢＫを半画素シフトした、半画素精度の参照ブロックＨＢＫ１乃至ＨＢＫ８を生成する。次に、当該生成された８個の半画素精度の参照ブロックＨＢＫ１乃至ＨＢＫ８について、整数画素精度の場合と同様に、差分評価値ＳＡＤ１乃至ＳＡＤ８をそれぞれ算出し、前記の最適参照ブロックＭＢＫに対応するＳＡＤの最小値との比較を行う。
【００１７】
上記の比較により、８個の半画素精度の参照ブロックＨＢＫ１乃至ＨＢＫ８の内に、上記の最適参照ブロックＭＢＫに対応するＳＡＤの最小値よりも、更に小さい差分評価値ＳＡＤを与える参照ブロックが存在した場合には、その参照ブロックを、ＳＡＤの最小値を与えるブロックとし、当該参照ブロックに対応する動きベクトル（ｄｘ，ｄｙ）＋（ｄｘ２，ｄｙ２）＝（ｄｘ３，ｄｙ３）を、半画素精度の動きベクトルＭＶ２とする。
上記の様に、半画素精度の動きベクトルＭＶ２を検出する為には、半画素精度の参照ブロックＨＢＫ１乃至ＨＢＫ８を線形補間により生成し、さらに、それらについてのＳＡＤ演算は計８回必要となる。一方で、図１１（ｂ）に示す、ダイヤモンドサーチパターンを用いた整数画素精度の動きベクトル探索における、最小のＳＡＤ演算回数が、Ｐ０〜Ｐ４での計５回である事を考慮すると、半画素精度の動きベクトルＭＶ２の検出についても無視できない演算量を必要とする。
【００１８】
ところで、上記の半画素精度の動きベクトル探索を行っても、半画素精度の動きベクトルＭＶ２が必ずしも半画素位置に求められるとは限らない。画素データを補間する事により生成された、８個の半画素精度の参照ブロックＨＢＫ１乃至ＨＢＫ８について、差分評価値ＳＡＤ１乃至ＳＡＤ８をそれぞれ算出し、最適参照ブロックＭＢＫに対応した、整数画素精度のＳＡＤの最小値と比較した結果、８個の半画素精度の参照ブロックＨＢＫ１乃至ＨＢＫ８の内に、上記の整数画素精度のＳＡＤの最小値よりも、更に小さい差分評価値ＳＡＤを与える参照ブロックが存在しない場合には、元の整数画素精度の動きベクトルＭＶ＝（ｄｘ，ｄｙ）が、そのまま半画素精度の動きベクトルＭＶ２となる。この場合の半画素精度の動きベクトル探索に費やした演算処理は、無駄である。
【００１９】
このような無駄を防止する為には、半画素精度の動き検出を行う前に、半画素位置においてより小さい差分評価値ＳＡＤが得られるか否かを推定できれば良い。その為に、整数画素精度の動きベクトル検出の結果を用いて、図１１（ａ）に示す、Ｐ０の位置の差分絶対値和ＳＡＤ０と、周辺の整数画素Ｐ１乃至Ｐ８の位置の差分絶対値和ＳＡＤ１乃至ＳＡＤ８の平均、Ａ＝（ΣＳＡＤｉ）／８との差（Ａ−ＳＡＤ０）をとり、その絶対値｜Ａ−ＳＡＤ０｜が、予め設定したしきい値であるΘよりも大きい場合にのみ、半画素位置においてより小さい差分評価値ＳＡＤが得られると推定し、半画素精度の動きベクトル検出を行う技術が、下記の特許文献に開示されている。
【特許文献１】特開２０００−２７８６９６号公報
【発明の開示】
【発明が解決しようとする課題】
【００２０】
しかしながら、上記の従来技術によれば、中心位置の周囲の半画素位置においてより小さい差分評価値ＳＡＤが得られる可能性を一括して推定するものの、個々の半画素位置における個別の可能性について精度よく知ることができない。
そのため、より可能性が高い一部の半画素位置においてのみ動きベクトルを探索することにより計算量を細かく削減するといった方策を採ることができない。
【００２１】
さらに、前記従来技術では、整数画素精度の動きベクトルを求めた後、その周辺においてより小さい差分評価値を示す半画素位置を求めるので、特に当該整数画素精度の動きベクトルを局所探索により求める場合、探索経路の途中に好ましい差分評価値（例えば極小値）を示す半画素位置があったとしても無視してしまう。
そのため、好ましい動きベクトルを見逃してしまうだけでなく、局所探索を早期に終了させることができないので計算量の増大を招くこととなる。
【００２２】
本発明は上記問題点を解決する為になされたものであり、個々の半画素位置においてより小さい差分評価値が得られる可能性を半画素位置個別かつ高精度に推定すること、及び局所探索を従来よりも早期に終了させるための新たな条件を判定することにより、もって整数画素以下の精度の動きベクトルを従来よりも少ない計算量で検出する動きベクトル検出装置、動きベクトル検出方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２３】
上記目的を達成する為、本発明の動きベクトル検出装置は、参照画像内に複数の参照ブロックを段階的に設定しながら、設定された参照ブロックの中から符号化対象画像内のカレントブロックとの類似度が最も高い第１最適ブロックを探索した後、前記参照ブロック間で画素補間して得た１つ以上の内挿ブロックを比較対象に加えて類似度が最も高い第２最適ブロックを求め、当該第２最適ブロックを基に整数画素以下の精度で動きベクトルを検出する動きベクトル検出装置であって、前記設定された参照ブロックの各々について、前記カレントブロック及び前記参照ブロックの対応画素の差分の正負符号をブロック内の各画素について示す差分特徴量を算出する演算手段と、隣接する参照ブロックについて算出された差分特徴量を比較することにより、当該隣接する何れの参照ブロックの類似度よりもそれらの間で画素補間して得られる内挿ブロックの類似度が高い可能性を示す比較結果を出力する比較手段と、前記比較結果が所定の可能性を示す場合に前記第１最適ブロックの探索を終了すると判定する判定手段とを備える。
【００２４】
また、前記動きベクトル検出装置において、前記演算手段は、前記対応画素の差分の正負符号のみをブロック内の各画素について示す差分特徴量を算出し、前記比較手段は、前記差分特徴量により示される正負符号が不一致である画素の数を前記比較結果として出力し、前記判定手段は、前記比較結果が所定のしきい値以上である場合に前記第１最適ブロックの探索を終了してもよい。
【発明の効果】
【００２５】
この構成によれば、隣接する参照ブロックの対応画素の差分の正負符号の比較により、それらの間に得られる内挿ブロックの類似度がより高くなる可能性を示す比較結果を算出するので、内挿ブロック個別に結果が得られる。
隣接する参照ブロックの対応画素の差分の正負符号が不一致であれば当該対応画素値の間に前記カレントブロックの画素値があるから、当該対応画素を線形補間して得た内挿画素の値は前記カレントブロックの画素の値に近い。そのような対応画素の数である前記比較結果は、内挿ブロックの類似度がより高くなる可能性を精度良く示す。
【００２６】
さらに、前記比較結果に基づいて前記第１最適ブロックに関する部分探索を終了させるので、前記第１最適ブロックを部分探索する場合に探索経路の途中にある好ましい内挿ブロックの検出が可能になると同時に、当該部分探索に要する計算量が削減される。
また、前記動きベクトル検出装置において、前記演算手段は、前記対応画素の差分の正負符号に加え、差分の絶対量の量子化値をブロック内の各画素について示す差分特徴量を算出し、前記比較手段は、前記差分特徴量により示される正負符号が不一致でありかつ量子化値が一致する画素の数を前記比較結果として出力し、前記判定手段は、前記比較結果が所定のしきい値以上である場合に前記第１最適ブロックの探索を終了すると判定してもよい。
【００２７】
この構成によれば、前記差分の正負符号が不一致で、かつ差分の絶対量が量子化の分解能で一致する対応画素の数を前記比較結果とする。このような対応画素を線形補間して得た内挿画素の値は、量子化の分解能でちょうど前記カレントブロックの画素の値となるから、前記内挿ブロックの類似度がより高くなる可能性をさらに精度良く示すことができる。
【００２８】
本発明の動きベクトル検出方法は、参照画像内に複数の参照ブロックを段階的に設定しながら、設定された参照ブロックの中から符号化対象画像内のカレントブロックとの類似度が最も高い第１最適ブロックを探索した後、前記参照ブロック間で画素補間して得た１つ以上の内挿ブロックを比較対象に加えて類似度が最も高い第２最適ブロックを求め、当該第２最適ブロックを基に整数画素以下の精度で動きベクトルを検出する動きベクトル検出方法であって、前記設定された参照ブロックの各々について、前記カレントブロック及び前記参照ブロックの対応画素の差分の正負符号をブロック内の各画素について示す差分特徴量を算出する演算ステップと、隣接する参照ブロックについて算出された差分特徴量を比較することにより、当該隣接する何れの参照ブロックの類似度よりもそれらの間で画素補間して得られる内挿ブロックの類似度が高いか推定する推定ステップと、肯定推定された場合に前記第１最適ブロックの探索を終了すると判定する判定ステップとを含む。
【００２９】
また、前記演算ステップは、前記対応画素の差分の正負符号のみをブロック内の各画素について示す差分特徴量を算出し、前記推定ステップは、前記差分特徴量により示される正負符号が不一致である画素の数が所定のしきい値以上である場合に肯定推定してもよい。
これらの方法によれば、前記内挿ブロックの類似度がより高くなるか、前述した作用によって精度良く推定し、その結果に基づいて前記第１最適ブロックに関する部分探索を終了させるので、探索経路の途中にある好ましい内挿ブロックの検出が可能になると同時に、当該部分探索に要する計算量が削減される。
【００３０】
また、前記推定ステップにおいて肯定推定された内挿ブロックのみを前記比較対象に加えて前記第２最適ブロックを求めてもよい。
また、本発明の動きベクトル検出方法は、参照画像内に設定した複数の参照ブロックの中から符号化対象画像内のカレントブロックとの類似度が最も高い第１最適ブロックを探索した後、前記参照ブロック間で画素補間して得た１つ以上の内挿ブロックを比較対象に加えて類似度が最も高い第２最適ブロックを求め、当該第２最適ブロックを基に整数画素以下の精度で動きベクトルを検出する動きベクトル検出方法であって、前記参照ブロックの各々について、前記カレントブロック及び前記参照ブロックの対応画素の差分の正負符号をブロック内の各画素について示す差分特徴量を算出する演算ステップと、隣接する参照ブロックについて算出された差分特徴量を比較することにより、当該隣接する何れの参照ブロックの類似度よりもそれらの間で画素補間して得られる内挿ブロックの類似度が高いか推定する推定ステップと、を含み、前記推定ステップにおいて肯定推定された内挿ブロックのみを比較対象に加えて前記第２最適ブロックを求めてもよい。
【００３１】
これらの方法によれば、類似度がより高くなると推定される内挿ブロックのみを前記比較対象に加えるので、実際に類似度を算出する内挿ブロックの数を抑制し前記第２最適ブロックを求めるための計算量を削減することができる。
また、前記動きベクトル検出方法において、前記演算ステップは、前記対応画素の差分の正負符号に加え、差分の絶対量の量子化値をブロック内の各画素について示す差分特徴量を算出し、前記推定ステップは、前記差分特徴量により示される正負符号が不一致でありかつ量子化値が一致する画素の数が所定のしきい値以上である場合に肯定推定してもよい。
【００３２】
この方法によれば、前記内挿ブロックの類似度がより高くなるか、前述した作用によってさらに精度良く推定することができる。
本発明の動きベクトル検出方法は、符号化対象画像の時間的な前後に表示される第１参照画像及び第２参照画像内にそれぞれ複数設定される第１参照ブロック及び第２参照ブロック、並びに当該第１参照ブロックと当該第２参照ブロックとの間で画素補間して得た１つ以上の時間内挿ブロックの中から、前記符号化対象画像内のカレントブロックとの類似度が最も高い最適ブロックを求め、当該最適ブロックを基に双方向に動きベクトルを検出する動きベクトル検出方法であって、前記第１参照ブロックの中から類似度が最も高い第１最適ブロックを求めると共に、前記カレントブロック及び当該第１最適ブロックの対応画素の差分の正負符号をブロックの全画素について示す第１差分特徴量を算出する第１演算ステップと、前記第２参照ブロックを段階的に設定しながら、設定された第２参照ブロックの中から類似度が最も高い第２最適ブロックを探索する探索ステップと、前記設定された第２参照ブロックの各々について、前記カレントブロック及び前記第２参照ブロックの対応画素の差分の正負符号をブロックの全画素について示す第２差分特徴量を算出する第２演算ステップと、前記第１差分特徴量と前記第２差分特徴量とを比較することにより、前記第１最適ブロック及び前記第２参照ブロックの何れの類似度よりもそれらの間で画素補間して得られる時間内挿ブロックの類似度が高いか推定する推定ステップと、肯定推定された場合に前記第２最適ブロックの探索を終了すると判定する判定ステップとを含む。
【００３３】
また、前記第１演算ステップは、前記対応画素の差分の正負符号のみをブロック内の各画素について示す第１差分特徴量を算出し、前記第２演算ステップは、前記対応画素の差分の正負符号のみをブロック内の各画素について示す第２差分特徴量を算出し、前記推定ステップは、前記第１差分特徴量と前記第２差分特徴量とにより示される正負符号が不一致である画素の数が所定のしきい値以上である場合に肯定推定してもよい。
【００３４】
また、前記第１演算ステップは、前記対応画素の差分の正負符号に加え、差分の絶対量の量子化値をブロック内の各画素について示す第１差分特徴量を算出し、前記第２演算ステップは、前記対応画素の差分の正負符号に加え、差分の絶対量の量子化値をブロック内の各画素について示す第１差分特徴量を算出し、前記推定ステップは、前記第１差分特徴量と前記第２差分特徴量とにより示される正負符号が不一致でありかつ量子化値が一致する画素の数が所定のしきい値以上である場合に肯定推定してもよい。
【００３５】
これらの方法は、双方向に動きベクトルを検出する場合に、前述した作用を時間方向に生ぜしめる。それにより、時間内挿ブロックの前記カレントブロックとの類似度が、前記第１参照ブロック及び第２参照ブロックの前記カレントブロックとの類似度よりも高くなるか精度良く推定し、その結果に基づいて前記第２最適ブロックの部分探索を終了させるので、探索経路の途中にある好ましい時間内挿ブロックの検出が可能になると同時に、当該部分探索に要する計算量が削減される。
【００３６】
また、本発明は、前記の方法に含まれる各ステップをコンピュータに実行させるためのプログラムであってもよい。
このプログラムによって、前述した効果を有する動きベクトル検出をコンピュータを用いて実施することができる。
【発明を実施するための最良の形態】
【００３７】
以下、本発明の実施の形態について、図面を参照しながら説明する。
（実施の形態１）
本実施の形態の動きベクトル検出装置について、図面を参照しながら説明する。
＜構成＞
（ＭＰＥＧ処理装置２の全体構成、接続関係）
図１は、本実施の形態の動きベクトル検出装置１を主要部とした、ＭＰＥＧ処理装置２の構成を示す機能ブロック図である。
【００３８】
ＭＰＥＧ処理装置２は、具体的には、ＣＰＵ（Central Processing Unit）３、と当該ＣＰＵ３が実行するプログラムを記憶しているＲＯＭ(Read Only Memory)４、ＣＰＵ３がプログラムを実行する際の作業領域であるＲＡＭ(Random Access Memory)５、フレームメモリ６、及び動きベクトル検出装置１から構成されており、各種の命令、及びデータの転送を行うグローバルバス７を介して、相互に接続されている。
【００３９】
（ＣＰＵ３の構成、接続関係）
ＣＰＵ３は、グローバルバス７を介し、ＲＯＭ４、ＲＡＭ５、及び動きベクトル検出装置１と接続されている。
ＣＰＵ３は、ＲＯＭ４又はＲＡＭ５などのメモリに格納されている各種のプログラムやデータによって動作し、ＭＰＥＧ処理装置２の制御部１４（後述）からの送信要求に従い、ＭＰＥＧ処理装置２に対し、上記グローバルバス７を介して、画素データを転送する。
【００４０】
（フレームメモリ６の構成、接続関係）
フレームメモリ６は、現フレームメモリ８、及び参照フレームメモリ９から構成されており、グローバルバス７を介し、ＣＰＵ３、ＲＯＭ４、ＲＡＭ５、及び動きベクトル検出装置１と接続されている。
フレームメモリ６は、ＣＰＵ３によりデータ転送された、現フレームの画素データを現フレームメモリ８に格納する一方、同じくＣＰＵ３によりデータ転送された、参照フレームの画素データを参照フレームメモリ９に格納する。
【００４１】
当該データ転送され、格納された画素データは、制御部５からの送信要求に基づき、ＣＰＵ３によって、動きベクトル検出装置１に転送され、現フレームの各カレントブロックに対する動きベクトルの探索が行われる。
（動きベクトル検出装置１の構成、接続関係）
動きベクトル検出装置１は、カレントブロックメモリ１１、参照領域メモリ１２、アドレス生成部１３、制御部１４、及びデータパス部１５から構成されており、外部のＣＰＵ３、及びフレームメモリ６と、グローバルバス７を介して接続されている。
【００４２】
動きベクトル検出装置１は、ＣＰＵ３により、フレームメモリ６からデータ転送されたカレントブロックＣＢＫの画素データ、及び参照領域ＳＡの画素データを基に、動きベクトルＭＶの探索を行う。上記探索により検出された動きベクトルＭＶを、動き補償（ＭＣ）を行う後続の機能ブロック（不図示）に対して出力する。
（カレントブロックメモリ１１、及び参照領域メモリ１２の構成、接続関係）
カレントブロックメモリ１１、及び参照領域メモリ１２は、グローバルバス７に接続され、当該グローバルバス７を介し、外部と画素データの授受を行う。
【００４３】
カレントブロックメモリ１１、及び参照領域メモリ１２は、制御部１４の命令に基づき、ＣＰＵ３により、グローバルバス７を介し、フレームメモリ６の現フレームメモリ８から転送されたカレントブロックＣＢＫの画素データ、及び、フレームメモリ６の参照フレームメモリ９から転送された参照領域ＳＡの画素データをそれぞれ受け取り、格納する。
カレントブロックメモリ１１に格納されるデータは、現フレームの中の、カレントブロックＣＢＫの画素データであり、参照領域メモリ１２に格納されるデータは、参照フレームの中の、所定の探索領域に含まれる画素データである。
【００４４】
また、カレントブロックメモリ１１、及び参照領域メモリ１２にそれぞれ格納された画素データは、制御部１４が、アドレス生成部１３に対し、転送領域の先頭アドレスを指定するよう命令した後、所定の転送バイト数の画素データを、データパス部１５に対して転送する。
カレントブロックメモリ１１から転送されるデータは、カレントブロックＣＢＫの画素データである一方、参照領域メモリ１２から転送されるデータは、参照領域の中に含まれる、所定の参照ブロックＢＫの画素データである。従って、データ転送の際には、カレントブロックメモリ１１の画素データは、制御部１４が、データパス部１５に対し、全ての画素データを転送するのに対し、参照領域メモリ１２の画素データは、制御部１４が、当該参照ブロックＢＫの画素データの先頭アドレス、及び転送バイト数などを指定した上で、データパス部１５にデータ転送する。
【００４５】
当該転送されたカレントブロックＣＢＫの画素データ、及び参照ブロックＢＫの画素データに基づいて、データパス部１５は、画像の類似度を判定し、動きベクトルＭＶの探索を行う。
（アドレス生成部１３の構成、接続関係）
アドレス生成部１３は、カレントブロックメモリ１１、参照領域メモリ１２、制御部１４、及びデータパス部１５に接続される一方、グローバルバス７を介して、外部のフレームメモリ６に接続されている。
【００４６】
（アドレス生成部１３の機能）
アドレス生成部１３は、制御部１４からの命令に従い、グローバルバス７を介し、外部のフレームメモリ６に対して、画素データの転送を行う際の、転送元のアドレスを指定する一方、同じく制御部１４からの命令により、カレントブロックＣＢＫや、参照ブロックＢＫの画素データを読み出す為、当該ブロックの位置座標（ｘ、ｙ）、及び画面１ライン分のデータ長などを基に、当該ブロックの画素データの（先頭アドレス、データ長）の組を算出する。
【００４７】
当該算出された画素データの先頭アドレス、データ長を基に、制御部１４が、当該画素データが格納されたメモリから、カレントブロックＣＢＫ、及び参照ブロックＢＫなどの、必要な画素データを読み出し、カレントブロックメモリ１１、参照領域メモリ１２、及びデータパス部１５などの各転送先に転送する。
（制御部１４の構成、接続関係）
制御部１４は、具体的には、図中に表示しないＣＰＵ、当該ＣＰＵが実行する各種の制御プログラムを記憶しているＲＯＭ（不図示）、及び当該ＣＰＵがプログラムを実行する際の作業領域であるＲＡＭ（不図示）から構成されるコンピュータである。
【００４８】
上記ＣＰＵは、ＤＳＰ（Digital Signal Processor）であっても良く、後述する動きベクトル検出装置１の当該各部の機能は、上記ＣＰＵ、又はＤＳＰが、上記ＲＯＭ、又は図示しない外部の記憶装置に格納されたプログラム（後述する）に従って動作する事により実現される。
また、制御部１４は、アドレス生成部１３、及びデータパス部１５と接続され、また、グローバルバス７を介して、外部のＣＰＵ３と接続されている。
【００４９】
（制御部１４の機能）
制御部１４は、グローバルバス７を介して接続された外部のＣＰＵ３に対して、動きベクトル検出装置１に対してフレームメモリ８に格納された画素データを転送するよう命令する。その際の転送元のアドレスの指定は、制御部１４により、転送元のアドレス、及び転送バイト数などの指定を受けたアドレス生成部１３が、グローバルバス７を介して、ＣＰＵ３に対して指示を行う。
【００５０】
また制御部１４は、画素データのＭＰＥＧ処理が円滑に進むよう、動きベクトル検出装置１全体を制御する。更に、制御部１４は、アドレス生成部１３、及びデータパス部１５に対し、画素データを転送する際の転送元、及び転送先アドレスを指定するよう、アドレス生成部１３に命令し、当該指定された転送元のアドレスから、転送先のアドレスに対し、制御部１４が、所定のバイト数の画素データを転送する。
【００５１】
（データパス部１５の構成、接続関係）
データパス部１５は、内挿演算部２４、差分評価値演算部２１、差分特徴量比較部２２、及び終了判定部２３から構成されており、カレントブロックメモリ１１、及び参照領域メモリ１２、アドレス生成部１３、制御部１４とそれぞれ接続されている。
（データパス部１５の機能）
データパス部１５は、カレントブロックメモリ１１、及び参照領域メモリ１２から、それぞれカレントブロックＣＢＫ、及び参照ブロックＢＫの画素データが、制御部１４により、それぞれ転送される。
【００５２】
データパス部１５は、当該転送された、カレントブロックＣＢＫの画素データ、及び参照ブロックＢＫの画素データを基に、双方のデータの差分から、差分評価値ＳＡＤ、及び差分特徴量を算出する事により、整数画素精度の動きベクトルＭＶ、及び半画素精度の動きベクトルＭＶ２の探索を行う。
（差分評価値演算部２１の構成、接続関係）
図２は、差分評価値演算部２１の構成を示す機能ブロック図である。差分評価値演算部２１は、ＰＥアレー３０、アダーツリー４０、及び累積加算器５０から構成される。
【００５３】
（差分評価値演算部２１の機能）
差分評価値演算部２１は、カレントブロックメモリ１１から供給されるカレントブロックＣＢＫの画素データｃkl（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）、及び参照領域メモリ１２から供給される参照ブロックＢＫの画素データｓkl（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）を基に、下記の式（６）で示される差分評価値ＳＡＤ（ＢＫ）、及び式（７）で示される差分特徴量ＣＨＤ（ＢＫ）ｋｌを、それぞれ算出し、後続の処理部である差分特徴量比較部２２、及び終了判定部２３に対して、それぞれ出力する。
【００５４】
【数６】
2005253015.tif 000008
【００５５】
【数７】
2005253015.tif 000009
差分評価値ＳＡＤ（ＢＫ）は、ＰＥ３１乃至３８の８個並列に接続されたＰＥにより、３２周期（サイクル）毎に１個生成される一方、差分特徴量ＣＨＤ（ＢＫ）ｋｌは、毎周期（サイクル）８個同時に生成され、８ビットの差分特徴量バス５５を介し、毎周期８個並列に差分特徴量比較部２２に対して出力される。
【００５６】
（ＰＥアレー３０の構成、接続関係）
ＰＥアレー３０は、後述のＰＥ（Processing Element）を８個並列に並べて構成される。
上記８個のＰＥ（ｌ）（ｌ＝０、１、２、・・・、７）は、カレントブロックメモリ１１のポートｃ、及び参照領域メモリ１２のポートｓに、それぞれ接続されている。また、各ＰＥ（ｌ）の差分絶対値和出力端子は、アダーツリー４０の各入力端子に接続されている一方、差分特徴量出力端子は、差分特徴量バス４８を介し、差分特徴量比較部２２の入力端子に接続されている。
【００５７】
（ＰＥアレー３０の機能）
ＰＥアレー３０は、カレントブロックメモリ１１のポートｃ、及び参照領域メモリ１２のポートｓから、それぞれ供給されるデータｃkl、及びｓkl（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）を基に、差分絶対値｜ｃkl−ｓkl｜、及び差分特徴量ＣＨＤ（ＢＫ）ｋｌ＝ｓｇｎ（ｃkl−ｓkl）をそれぞれ算出する８個のＰＥ（ｌ）（ｌ＝０、１、２、・・・、７）により、上記の差分絶対値｜ｃkl−ｓkl｜、及び差分特徴量ＣＨＤ（ＢＫ）ｋｌ＝ｓｇｎ（ｃkl−ｓkl）を、変数ｋ（ｋ＝０、１、２、・・・、３１）で指定される各サイクルにおいて、同時に８個生成する。
【００５８】
なお、以下において、添字ｋ（ｋ＝０、１、２、・・・、３１）は、本実施の形態の動きベクトル検出装置の周期（クロックサイクル）を指定する一方、添字ｌ（ｌ＝０、１、２、・・・、７）は、８個並列に接続されたＰＥのうちの、ｌ番目のＰＥ（＝ＰＥ（ｌ））を指定するものとする。添字ｋの範囲は、０から３１までであるが、これは、本実施の形態の動きベクトル検出装置による各マクロブロックの画素データの処理が、３２サイクルを１単位として、一連の処理が行われる事を示している（動きベクトル検出装置としての実際の周期は、３２サイクルよりも長くなる）。
【００５９】
（ＰＥの構成、接続関係）
図３は、図２に示した８個のＰＥ３１乃至ＰＥ３８の、内部構成を示す機能ブロック図である。同図に示す様に、各ＰＥ（ｌ）（ｌ＝０、１、２、・・・、７）は、引算器６１、絶対値化器６２、レジスタ６３、及び符号化器６４から構成されている。
（ＰＥの機能）
各ＰＥ（ｌ）（ｌ＝０、１、２、・・・、７）は、カレントブロックメモリ１１のポートｃ、及び参照領域メモリ１２のポートｓから順次供給される、カレントブロック、及び参照ブロックの画素データｃkl、及びｓkl（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）に対し、差分絶対値｜ｃkl−ｓkl｜を算出する。
【００６０】
また、上記の画素データｃkl、及びｓklの差分（ｃkl−ｓkl）の符号ｓｇｎ（ｃkl−ｓkl）を、１ビットの情報“１”、又は“０” に変換し、差分特徴量ＣＨＤ（ＢＫ）ｋｌとする。
本実施例では、差分（ｃkl−ｓkl）の符号が正であれば、ビット“１”に変換し、０又は負であれば、ビット“０”に変換したものを、差分特徴量ＣＨＤ（ＢＫ）ｋｌとする。
【００６１】
上記の様にして、毎サイクル８個生成される差分絶対値｜ｃkl−ｓkl｜を、アダーツリー４０に出力する一方、差分特徴量ＣＨＤ（ＢＫ）ｋｌ＝ｓｇｎ（ｃkl−ｓkl）を、毎周期（サイクル）１個生成し、差分特徴量バス４８を介し、差分特徴量比較部２２に出力する。
（アダーツリー４０の構成、接続関係）
アダーツリー４０は、図２に示す様に、２個のデータを加算する複数個の加算器４１乃至加算器４７を、数段に渡って配置し、結合したものである。
【００６２】
アダーツリー４０の各入力端子は、８個のＰＥ３１乃至ＰＥ３８の各出力端子にそれぞれ接続される一方、各出力端子は、累積加算器５０の各入力端子にそれぞれ接続されている。
（アダーツリー４０の機能）
上記の並列に配置された８個のＰＥ３１乃至ＰＥ３８から出力される、複数個の差分絶対値｜ｃkl−ｓkl｜を、２個ずつ数段に渡って加算することにより、最終的に、各ＰＥが出力する上記データに対し、変数ｌ（ｌ＝０、１、２、・・・、７）に関して和を取ったものを、累積加算器５０に対して出力する。
【００６３】
（累積加算器５０の構成、接続関係）
図４は、累積加算器５０の構成を示す機能ブロック図である。同図に示すように、累積加算器５０は、加算器５１、及び累積レジスタ５２を含んで構成される。
（累積加算器５０の機能）
ＰＥアレー３０において、変数ｌで指定される各ＰＥ（ｌ）（ｌ＝０、１、・・・、７）からは、上記の演算を行った結果である差分絶対値｜ｃkl−ｓkl｜（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）に対し、アダーツリー４０、及び累積加算器５０が、変数ｌ、及びｋに関して、それぞれ和をとる事により、最終的に差分評価値ＳＡＤが算出される。当該算出された差分評価値ＳＡＤは、終了判定部２３に出力される。
【００６４】
（差分特徴量比較部２２の構成、接続関係）
図５は、差分特徴量比較部２２の構成を示す、機能ブロック図である。同図に示すように、差分特徴量比較部２２は、分岐器７０、バンク０乃至バンク４の５個の差分特徴量レジスタ７１乃至７５、加算器７６、比較器７７、及びカウンタ７８から構成されている。
（差分特徴量比較部２２の機能）
差分特徴量比較部２２が備える、５個の差分特徴量レジスタ７１乃至７５（それぞれ、バンク０乃至バンク４に対応する）は、探索パターンＳＰに含まれる探索中心Ｐ０、及び周囲の４点Ｐ１乃至Ｐ４の、計５点に対応しており、バンク０乃至バンク４の各バンクは、Ｐ０乃至Ｐ４の５点を左上端とする、各参照ブロックＢＫｎ（ｎ＝０、１、２、３、４）と、カレントブロックＣＢＫとの画素データの差分符号ＣＨＤ（ＢＫｎ）ｋｌを、それぞれ格納する。
【００６５】
上記のバンク０乃至バンク４の各バンクは、それぞれ８ｂｉｔ×３２バイト＝２５６ｂｉｔの容量があり、各バンクの１ビットが、対応する差分ブロックの、対応する差分画素データ（ｃkl−ｓkl）の符号である、差分特徴量ＣＨＤ（ＢＫ）ｋｌ＝ｓｇｎ（ｃkl−ｓkl）に、それぞれ対応している（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）。
【００６６】
上記の様にして、参照ブロックＢＫ０乃至ＢＫ４と、カレントブロックＣＢＫとの各画素データの差分（ｃkl−ｓkl(ｎ)）の符号、ｓｇｎ（ｃkl−ｓkl(ｎ)）（ｎは、参照ブロックＢＫ０乃至ＢＫ４のうちの１つを指定する為の変数であり、ｎ＝０、１、２、３、４）を、バンク０乃至バンク４の各バンクに格納した後、後述する、差分特徴量比較結果算出処理（図６参照）によって、バンク０と、バンクｎ（ｎ＝１〜４）との、それぞれ（ｋ、ｌ）の組で指定されるビット（ＣＨＤ（ＢＫ０）ｋｌ、及びＣＨＤ（ＢＫｎ）ｋｌ、ｎ＝１〜４）のビット値（“０”、又は“１”）を比較し、２つのバンク間で、ビット値が異なるビットの個数をカウントし、前記カウント値を比較したものを、差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）として、差分特徴量バス４８を介し、終了判定部２３に出力する。
【００６７】
上記の差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）は、差分特徴量ＣＨＤ（ＢＫｎ）ｋｌ＝ｓｇｎ（ｃkl−ｓkl(n)）を用いて、下記の数式（８）の様に表される。
【００６８】
【数８】
2005253015.tif 000010
上記の差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）は、探索パターンＳＰ＝｛Ｐ０、Ｐ１、Ｐ２、Ｐ３、Ｐ４｝内において隣接する、２つの参照ブロックＢＫ０と、ＢＫｎ（ｎ＝１、２、３、４）との間で、（ｋ、ｌ）で指定される各画素データの差分（ｃkl−ｓkl）の正負符号（差分特徴量ＣＨＤ（ＢＫ）ｋｌ）が、どれだけ反転しているかを示すものであり、この値が大きい程、ＢＫ０と、ＢＫｎ（ｎ＝１、２、３、４）との間の半画素位置に、半画素精度の最適参照ブロックＭＨＢＫが存在する可能性が高い。
【００６９】
図６は、差分特徴量比較部２２が行う、差分特徴量比較結果算出処理の手順を示すフローチャートである。
差分特徴量比較部２２は、まず、２５６個の差分特徴量ＣＨＤ（ＢＫ０）ｋｌ（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）を、バンク０に格納する（ステップＳ１００）。
【００７０】
次に、ｉに１をセット（ステップＳ１０１）した後、差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｉ）をゼロクリアする（ステップＳ１０２）。
次に、バンクｉに、２５６個の差分特徴量ＣＨＤ（ＢＫｉ）ｋｌ（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）を格納すると共に、比較器の入力１に、差分特徴量ＣＨＤ（ＢＫｉ）ｋｌを転送する（ステップＳ１０３）。
【００７１】
また、比較器の入力２には、バンク０に格納した差分特徴量ＣＨＤ（ＢＫ０）ｋｌを転送する（ステップＳ１０４）。
比較器７７の入力１、及び入力２に、差分特徴量ＣＨＤ（ＢＫｉ）ｋｌ、及びＣＨＤ（ＢＫ０）ｋｌがセットされた状態で、次の差分特徴量カウント処理（ステップＳ１０５；詳細は、後述）を実行し、当該処理で得られた差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｉ）を出力する（ステップＳ１０６）。
【００７２】
次に、ｉを“１”インクリメントし（ステップＳ１０７）、ｉが４以下であれば（ステップＳ１０８：Ｎｏ）、ステップＳ１０２に戻って、処理を継続する。一方、そうでなければ（ステップＳ１０８：Ｙｅｓ）、差分特徴量比較結果算出処理を終了する。
図７は、差分特徴量比較部２２が行う、差分特徴量カウント処理の処理手順を示すフローチャートである。
【００７３】
差分特徴量比較部２２は、まず、変数ｋ、及びｌに０をセットする（ステップＳ２００）。
次に、２つの参照ブロックＢＫｉ、及びＢＫ０に関する、２５６個の差分特徴量、ＣＨＤ（ＢＫｉ）ｋｌとＣＨＤ（ＢＫ０）ｋｌ（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）とを比較し、（ｋ、ｌ）の組を１つ定める事により指定される、それぞれの差分特徴量の値が、一致していなければ（ステップＳ２０１：Ｙｅｓ）、ＲＥＳ（ＢＫ０、ＢＫｉ）を、“１”インクリメントし、また一致していれば（ステップＳ２０１：Ｎｏ）、そのまま次のステップＳ２０３に進む。
【００７４】
次に、差分特徴量比較部２２は、変数ｌを“１”インクリメントする（ステップＳ２０３）し、
ｌが８以上でなければ（ステップＳ２０４：Ｎｏ）、ステップＳ２０１に戻り、次のｌに関する比較処理を繰り返す一方、ｌが８以上であれば（ステップＳ２０４：Ｙｅｓ）、ステップＳ２０５に進み、変数ｌに０をセットすると共に、変数ｋを“１”インクリメントする。
【００７５】
次のステップＳ２０６において、ｋが３２以上でなければ（ステップＳ２０６：Ｎｏ）、ステップＳ２０１に戻り、次のｋに関する比較処理を繰り返す一方、ｋが３２以上であれば（ステップＳ２０６：Ｙｅｓ）、差分特徴量カウント処理を終了し、呼び出し元にリターンする。
（終了判定部２３の構成、接続関係）
図８は、終了判定部２３の構成を示す機能ブロック図である。同図に示すように、終了判定部２３は、第１終了判定部８０、第２終了判定部８１、分岐器８２、及びＯＲ回路８３から構成される。
【００７６】
（終了判定部２３の機能）
終了判定部２３は、差分評価値演算部２１、差分特徴量比較部２２から、差分評価値ＳＡＤ、及び差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）を各々取得して、それぞれＳＡＤレジスタ９０、差分特徴量比較結果レジスタ９５に格納する。また、探索中心Ｐ０におけるＳＡＤの値、ＳＡＤ（Ｐ０）については、特にＳＡＤ０レジスタ９６に格納し、当該格納された各データをそれぞれ比較する事により、最適参照ブロックＭＢＫの局所探索を終了するか否かについて判定を行う。
【００７７】
上記判定について、終了判定部２３は、以下の３つの終了条件のうちのいずれかが満たされた場合には、動きベクトルの局所探索を終了する旨の判定を行う。
（Ａ）探索パターンＳＰの中心位置Ｐ０において、差分評価値ＳＡＤが最小値となった場合。
（Ｂ）探索回数Ｎｓが、探索打ち切り回数に達した場合。
【００７８】
（Ｃ）隣り合った２つの整数画素精度の参照ブロックＢＫ０、及びＢＫｎ（ｎ＝１、２、３、４）の差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）を比較する事により、半画素精度の最適参照ブロックＭＨＢＫが、この間に求められる可能性が高いと推定される場合。
上記の「終了条件」のうち、条件Ａ、又は条件Ｂが成立した場合には、第１終了判定部８０が、第１終了信号をＯＲ回路８３に出力し、条件Ｃが成立した場合には、第２終了判定部８１が、第２終了信号をＯＲ回路８３に出力する。
【００７９】
上記の第１終了信号、及び第２終了信号のうち、いずれかが出力された場合には、終了判定部２３は、局所探索を終了する為の終了通知を、制御部１４に対して出力する。
終了判定部２３から、上記の終了通知を受け取った制御部１４は、局所探索によって得られた動きベクトルＭＶを、制御部１４に転送すると共に、探索経路ＳＲ内で、ＳＡＤの最小値を与える参照ブロックの位置に関する情報を、「ＭＩＮＳＡＤ位置情報」として、制御部１４に通知した後、現フレームの、次の位置のカレントブロックに対する動きベクトル探索を行う為、整数画素精度の最適参照ブロックＭＢＫの探索処理を、同様に繰り返す。
【００８０】
（第１終了判定部８０の構成、接続関係）
第１終了判定部８０は、図８に示すように、現在のＳＡＤの値を記憶するＳＡＤレジスタ９０、これまでの探索によって得られたＳＡＤの最小値（ＭＩＮＳＡＤ）を記憶するＭＩＮＳＡＤレジスタ９１、それら２つのＳＡＤ値の大小を比較する比較器９２、及び、ＳＡＤの最小値（ＭＩＮＳＡＤ）を与える最適参照ブロックＭＢＫの探索を終了するか否かを判定する第１判定部９３を含んで構成される。
【００８１】
（第１終了判定部８０の機能）
第１終了判定部８０は、１つの探索パターンＳＰ内で算出される、複数の差分評価値ＳＡＤの値を比較する事により、半画素精度の最適参照ブロックＭＨＢＫの探索を終了するか否かの判定を行う。
（ＳＡＤレジスタ９０の構成、接続関係）
ＳＡＤレジスタ９の入力側は、差分評価値演算部２１から出力される差分評価値ＳＡＤを２方向に分岐する、分岐器８２の２つの出力のうちの一方に接続され、出力側は、比較器９２、及び第２判定部９７に接続されている。
【００８２】
（ＳＡＤレジスタ９０の機能）
ＳＡＤレジスタ９０は、差分評価値演算部２１から出力された差分評価値ＳＡＤの値を記憶する。
（ＭＩＮＳＡＤレジスタ９１の構成、接続関係）
ＭＩＮＳＡＤレジスタ９１の入力側は、比較器９２に接続され、出力側は、ＭＩＮＳＡＤ出力を再度比較する為に比較器９２の入力側に接続される一方、最終的なＭＩＮＳＡＤの値を出力する為に、終了判定部２３のＭＩＮＳＡＤ出力ポートに接続されている。
【００８３】
（ＭＩＮＳＡＤレジスタ９１の機能）
ＭＩＮＳＡＤレジスタ９１は、比較器９２と組み合わされる事により、ＳＡＤレジスタ９０に記憶された差分評価値ＳＡＤの最小値である、ＭＩＮＳＡＤの値を検出し、記憶する。
ＳＡＤレジスタ９０に記憶された差分評価値ＳＡＤの値と、ＭＩＮＳＡＤレジスタ９１に記憶された、差分評価値ＳＡＤの最小値ＭＩＮＳＡＤの値とを比較器９２が比較し、現在のＳＡＤの値の方が、ＭＩＮＳＡＤの値よりも小さければ、ＭＩＮＳＡＤレジスタ９１が記憶しているＭＩＮＳＡＤの値を、ＳＡＤレジスタ９０に記憶された現在のＳＡＤの値で更新する。
【００８４】
上記処理を繰り返した結果、得られる差分評価値ＳＡＤの最小値ＭＩＮＳＡＤの値を、終了判定部２３のＭＩＮＳＡＤ出力ポートから出力する。
（比較器９２の構成、接続関係）
比較器９２の入力側は、ＳＡＤレジスタ９０の出力側、及びＭＩＮＳＡＤレジスタ９１の出力側に接続される一方、出力側は、ＭＩＮＳＡＤ値出力ポートがＭＩＮＳＡＤレジスタ９１の入力側に接続される一方、比較結果出力ポートが第１判定部９３の入力側に接続されている。
【００８５】
（比較器９２の機能）
比較器９２は、２つの入力ポートにそれぞれ入力された、ＳＡＤレジスタ９０が出力する現在の差分評価値ＳＡＤの値と、ＭＩＮＳＡＤレジスタ９１が出力する差分評価値ＳＡＤの最小値ＭＩＮＳＡＤの値とを比較し、小さい方の値を、出力ポートからＭＩＮＳＡＤレジスタ９１に出力する。
【００８６】
（第１判定部９３の構成、接続関係）
第１判定部９３の入力側は、制御部１４のＳＡＤ位置出力ポート、探索回数出力ポート、及び比較器９２の比較結果出力ポートに接続され、出力側は、最終的なＭＩＮＳＡＤの値を与える位置を出力する為に、終了判定部２３のＭＩＮＳＡＤ位置出力ポートに接続され、また終了判定結果を出力する為にＯＲ回路８３の入力側にも接続されている。
【００８７】
（第１判定部９３の機能）
第１判定部９３は、制御部１４のＳＡＤ位置出力ポートから出力される、現在の探索位置（ＳＡＤ位置）に関する情報と、比較器９２の比較結果出力ポートから出力される、ＳＡＤレジスタ９０に格納された、現在の差分評価値ＳＡＤの値と、ＭＩＮＳＡＤレジスタ９１に格納された、それまでの探索によって得られたＳＡＤの最小値ＭＩＮＳＡＤとの大小について、比較器９２が比較した結果とを受け取る事により、現在の探索位置における探索パターンＳＰ内で算出される、複数（ｎｐ）個の参照ブロックの差分評価値ＳＡＤのうち、中央の探索中心における参照ブロックＢＫのＳＡＤ値が最小となった場合に、整数画素精度の最適参照ブロックＭＢＫの探索を終了する旨の判定を行う。
【００８８】
上記の終了条件Ａ、又は終了条件Ｂが成立し、整数画素精度の最適参照ブロックＭＢＫの探索を終了する判定を行った場合には、第１判定部９３は、第１終了信号をＯＲ回路８３に対して出力する。
（第２終了判定部８１の構成、接続関係）
第２終了判定部８１は、図８に示すように、差分特徴量比較結果レジスタ９５、ＳＡＤ０レジスタ９６、及び第２判定部９７を含んで構成される。
【００８９】
（第２終了判定部８１の機能）
第２終了判定部８１は、隣り合った２つの整数画素精度の参照ブロックＢＫ０と、ＢＫｎとの差分符号を比較する為の差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）を各々比較する事により、半画素精度の最適参照ブロックＭＨＢＫの探索を終了するか否かを判定する。
【００９０】
第２終了判定部８１の第２判定部９７では、ＳＡＤ０レジスタ９６、ＳＡＤレジスタ９０、及び差分特徴量比較結果レジスタ９５から、ＳＡＤ（Ｐ０）、ＳＡＤ（Ｐｎ）（ｎ＝１、２、３、４）、及び差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）を、それぞれ取得し、予め設定された所定のしきい値Ｔｈ１、及びＴｈ２を用いて、各ｎ（ｎ＝１、２、３、４）に対し、下記の２つの不等式
【００９１】
【数９】
2005253015.tif 000011
【００９２】
【数１０】
2005253015.tif 000012
が成立するか否かを判定する。
上記の不等式（９）、及び不等式（１０）が、ともに真であれば、第２判定部９７は、探索中心Ｐ０と周辺位置Ｐｎ（ｎ＝１、２、３、４）の、２つの整数画素精度の参照ブロックＢＫ０、及びＢＫｎの間に、半画素精度の最適参照ブロックＭＨＢＫが存在する可能性が高いとして、第２終了信号を出力する。
【００９３】
（内挿演算部２４の詳細）
（内挿演算部２４の構成、接続関係）
図９は、内挿演算部２４の構成を示す機能ブロック図である。同図に示すように、内挿演算部２４は、半画素ブロックメモリ１００、及び補間部１０１から構成される。
（内挿演算部２４の機能）
内挿演算部２４は、参照領域メモリ１２に格納された参照ブロックの画素データを取得し、当該取得された画素データを基に、補間部１０１が画素データの内挿補間を行う事により、半画素ブロックＨＢＫの画素データを生成する。生成された半画素ブロックＨＢＫの各画素データは、半画素ブロックメモリ１００に格納された後、差分評価値演算部２１で、半画素精度の差分評価値ＳＡＤを算出する事により、半画素精度の動きベクトルＭＶ２の検出を行う。
【００９４】
上記の終了判定部２３が、終了通知を出力した場合において、上記の終了条件Ｃにより、第２終了判定部８１が第２終了信号を出力した場合には、上記の探索中心Ｐ０と、ｎで指定される周辺位置Ｐｎ（ｎ＝１、２、３、４）の２つの整数画素精度の参照ブロックＢＫ０、及びＢＫｎの間に、半画素精度の最適参照ブロックＭＨＢＫが存在する可能性が高いと考えられる。
【００９５】
このＨＭＢＫが、実際にＳＡＤの最小値を与える参照ブロックであるかどうかを確かめる為、この２つの参照ブロックＢＫ０、及びＢＫｎとの間で、内挿補間により、実際に半画素精度の参照ブロックＨＢＫを生成し、差分評価値ＳＡＤ（ＨＢＫ）を算出し、整数画素精度の参照ブロックの差分評価値ＳＡＤ（Ｐ０）、及びＳＡＤ（Ｐｎ）と比較する。
上記差分評価値ＳＡＤの比較を行った結果、ＳＡＤ（ＨＢＫ）が、ＳＡＤ（Ｐ０）、及びＳＡＤ（Ｐｎ）よりも小さい場合には、２つの参照ブロックＢＫ０、及びＢＫｎの間の半画素位置にある、半画素精度の参照ブロックＨＢＫが、半画素精度の最適参照ブロックＭＨＢＫであり、これに対応する動きベクトルとして、半画素精度の動きベクトルＭＶ２が求められる。
【００９６】
＜動作＞
（ＭＰＥＧ処理装置２が、全体として行う動作）
動きベクトル検出装置１が、整数画素精度の動きベクトルを探索する方法について、各部の機能と対照しつつ、図面を参照しながら説明する。
図１０は、整数画素精度の動きベクトル探索の概要を示す図である。動きベクトルの検出においては、同図に示すように、まず、フレームメモリ６の現フレームメモリ８に格納された、時刻Ｔにおける符号化画像ＩT（現フレーム）を、マクロブロックと呼ばれる、縦横１６×１６画素のサイズの、互いに重なり合わない領域に分割した中から、所定の順序で１つずつ指定して行き、これをカレントブロックＣＢＫとする。現フレーム画像の符号化は、カレントブロックＣＢＫを単位として行う。
【００９７】
なお、本明細書中において、カレントブロックＣＢＫ、及び後述の参照ブロックＢＫは、ブロックの左上端にある画素の位置を代表点Ｐとし、Ｐ点の座標（ｘ，ｙ）を、当該ブロックの座標（ｘ，ｙ）とする。
上記指定されたカレントブロックＣＢＫの画素データを、ＣＰＵ３が、現フレームメモリ８から、カレントブロックメモリ１１に転送する。現フレームメモリ８に格納された１フレーム分の画素データの中から、カレントブロックＣＢＫの画素データを読み出す為に、アドレス生成部１３は、当該カレントブロックＣＢＫの位置座標（ｘ０、ｙ０）、及び画面１ライン分のデータ長を基に、当該カレントブロックＣＢＫの画素データの（先頭アドレス、データ長）の組を、１６ライン分算出する。当該算出された画素データの先頭アドレス、データ長を基に、ＣＰＵ３が、現フレームメモリ８からカレントブロックＣＢＫの画素データを読み出し、カレントブロックメモリ１１に転送し、格納する。当該格納されたＣＢＫの画素データは、制御部１４の命令により、後述する参照ブロックＢＫの画素データとの比較を行う際に、ＣＰＵ３が、データパス部１５に転送する。
【００９８】
次に、フレームメモリ６の参照フレームメモリ９に格納された、時刻（Ｔ−１）における参照画像ＩT-1（参照フレーム）内の、上記カレントブロックＣＢＫの座標（ｘ０，ｙ０）の周囲に、所定の広さ（Ｓｘ画素×Ｓｙライン）の探索領域ＳＡを設定する。
上記探索領域ＳＡの設定は、参照フレームメモリ９に格納された画素データの中から、アドレス生成部１３が、当該探索領域ＳＡの画素データの（先頭アドレス、データ長）の組を、Ｓｙライン分指定する事によって行われる。当該指定された画素データの先頭アドレス、データ長を基に、ＣＰＵ３は、参照フレームメモリ９から、探索領域ＳＡの画素データを読み出し、参照領域メモリ１２に転送し、格納する。
【００９９】
次に、上記設定された探索領域ＳＡにおいて、Ｘ、Ｙの各方向に１画素単位の動き量（ｄｘ，ｄｙ）を与える事により、縦横１６×１６の画素から構成され、左上端画素が、座標（ｘ＋ｄｘ，ｙ＋ｄｙ）の位置にあるブロックを指定し、これを参照ブロックＢＫとする。
参照ブロックＢＫの位置（ｘ、ｙ）の、カレントブロックＣＢＫの位置（ｘ０、ｙ０）からのシフト量として表される動き量（ｄｘ，ｄｙ）＝（ｘ、ｙ）−（ｘ０、ｙ０）は、例えば、（ｄｘ，ｄｙ）＝（０、０）を初期値としても良いし、また現在のカレントブロックＣＢＫの、１つ前のカレントブロックＣＢＫ´の動きベクトルＭＶ´＝（ｄｘ´，ｄｙ´）を初期値としても良い。
【０１００】
上記参照ブロックＢＫの画素データは、制御部１４の命令により、カレントブロックＣＢＫの画素データとの比較を行う際に、ＣＰＵ３が、当該指定された参照ブロックＢＫの画素データを、参照領域メモリ１２から読み出し、データパス部１５に転送する。参照領域メモリ１２に格納された、探索領域ＳＡの画素データの中から、参照ブロックＢＫの画素データを読み出す為に、アドレス生成部１３は、当該参照ブロックＢＫの位置座標（ｘ、ｙ）、及び領域１ライン分のデータ長を基に、当該参照ブロックＢＫの画素データの（先頭アドレス、データ長）の組を、１６ライン分算出する。当該算出された画素データの先頭アドレス、データ長を基に、ＣＰＵ３が、参照領域メモリ１２から、参照ブロックＢＫの画素データを読み出し、データパス部１５に転送する。
【０１０１】
制御部１４の命令により、動き量（ｄｘ，ｄｙ）が１画素ずつシフトされる毎に、上記参照ブロックＢＫは、探索領域ＳＡ内を移動し、その度に、上記参照ブロックＢＫの画素データが、ＣＰＵ３により、データパス部１５に転送される。データパス部１５は、当該転送された参照ブロックＢＫの画素データを基に、カレントブロックＣＢＫと、参照ブロックＢＫの画像パターンの類似度の比較を行う。
【０１０２】
画像パターンの類似度の比較は、まず、データパス部１５の差分評価値演算部２１が、双方の画像パターンから差分評価値、及び差分特徴量を算出し、次に、データパス部１５の差分特徴量比較部が、当該算出された複数の差分特徴量を比較する事によって、差分特徴量比較結果を生成する。
上記の差分評価値として、下記の数式（１１）に示す、差分絶対値和（ＳＡＤ：Sum of Absolute Difference）や、数式（１２）に示す、差分２乗和（ＳＳＤ：Sum of Square Difference）が用いられる。
【０１０３】
【数１１】
2005253015.tif 000013
【０１０４】
【数１２】
2005253015.tif 000014
なお、以下では、特に断らない限り、差分評価値として、差分絶対値和ＳＡＤを用いる。差分評価値として、差分２乗和ＳＳＤを用いる場合は、「ＳＡＤ」を、「ＳＳＤ」に読み替えると共に、差分の絶対値をとる演算を、差分を２乗する演算に置き換える。
上記の差分評価値（ＳＡＤ（ＢＫ））、及び差分特徴量比較結果（ＣＨＤ（ＢＫ）ｋｌ）は、終了判定部２３に出力され、終了判定部２３は、当該入力された、差分評価値、及び差分特徴量比較結果を用いて、動きベクトルＭＶの探索を終了するか否かの判定を行う。上記の差分評価値、及び差分特徴量が、所定の条件（後述）を満たす場合、終了判定部２３が、制御部１４に対して、終了信号を出力する事により、制御部１４は、動きベクトルＭＶの探索を終了する。
【０１０５】
動きベクトルＭＶの探索を終了する場合には、終了判定部２３が、差分評価値の最小値（ＭＩＮＳＡＤ）を与える参照ブロックＢＫを、当該カレントブロックＣＢＫに対する最適参照ブロックＭＢＫとし、当該最適参照ブロックＭＢＫの位置（ｘ、ｙ）を、ＭＩＮＳＡＤ位置情報として、制御部１４に通知する。
ＭＩＮＳＡＤ位置情報（ｘ、ｙ）の通知を受けた制御部１４は、当該ＭＩＮＳＡＤ位置情報（ｘ、ｙ）から、当該カレントブロックＣＢＫの位置（ｘ０、ｙ０）を引き算する事により、対応する動き量（ｄｘ，ｄｙ）を、下記の数式（１３）を用いて算出し、当該算出された動き量（ｄｘ，ｄｙ）を、当該カレントブロックＣＢＫに対する動きベクトルＭＶとして、図示しない、後続の処理部に対して出力する。
【０１０６】
【数１３】
2005253015.tif 000015
上記の処理を、現フレーム内の全てのカレントブロックＣＢＫに対して繰り返す事により、当該現フレームの、各マクロブロックに対応した動きベクトルＭＶ＝（ｄｘ、ｄｙ）が全て求められる。
なお、上記の動き量（ｄｘ，ｄｙ）は、１画素単位にシフトされる為、この場合に求められた動きベクトルＭＶを、整数画素精度の動きベクトルと言う。動きベクトル検出装置１は、整数画素精度の動きベクトルＭＶの探索を行った後、続いて、半画素精度の動きベクトルＭＶ２の探索を行う。整数画素精度の動きベクトルＭＶの探索結果を用いた、半画素精度の動きベクトルＭＶ２の探索については、後述する。
【０１０７】
（局所探索と探索経路ＳＲ）
整数画素精度の動きベクトル探索においては、動きベクトルＭＶ＝（ｄｘ、ｄｙ）をシフトする事により、参照ブロックＢＫが、参照フレーム内を動き回る範囲（探索範囲）の大きさが、全体の演算量に大きな影響を及ぼす。
参照ブロックＢＫが、１画面内を隈なく動き回り、上記の差分評価値ＳＡＤが最小となる位置を探索する方法は、全探索（フルサーチ）と呼ばれ、莫大な演算量を必要とする為、処理能力に余裕がある、据え置き型の機器で用いられる。一方、必要な演算量を大幅に削減する為に探索範囲を予め限定し、当該限定された範囲内においてのみ、上記差分評価値ＳＡＤが最小となる参照ブロックＢＫの位置を探索する方式を、局所探索という。局所探索は、携帯電話等の、データ処理容量が小さいモバイル型の機器などにおいて用いられる。
【０１０８】
（探索パターンＳＰ）
図１１は、局所探索において、差分評価値ＳＡＤの比較を行う探索パターンＳＰを示す図である。同図に示す探索パターンＳＰは、差分評価値ＳＡＤの最小値を与える位置を見つける為、ある点（図中のＰ０）を左上端とする参照ブロックＢＫに関する差分評価値ＳＡＤを比較する、周囲の参照ブロックＢＫの左上端の点（ブロックサーチパターンでは、図中のＰ１乃至Ｐ８、またダイヤモンドサーチパターンでは、図中のＰ１乃至Ｐ４）の配置パターンを示すものであり、パターンの中央に位置する点（ブロックサーチパターン、及びダイヤモンドサーチパターンにおける、パターン中央の点Ｐ０）を、探索中心と言う。
【０１０９】
上記の探索パターンＳＰを、下記の数式（１４）、及び数式（１５）の様に、記号的に表示する。
【０１１０】
【数１４】
2005253015.tif 000016
【０１１１】
【数１５】
2005253015.tif 000017
上記の各探索パターンにおいて、パターンに含まれる点の個数をｎｐとする。ブロックサーチパターンの場合では、ｎｐ＝９、ダイヤモンドサーチパターンの場合では、ｎｐ＝５である。
なお、以下では、特に断らない限り、探索パターンＳＰとしては、ダイヤモンドサーチパターンを用いるものとする。この場合、探索パターンに含まれる点の数は、ｎｐ＝５である。
【０１１２】
差分評価値ＳＡＤの最小値を与える点を見つける為、点Ｐ０を探索中心とし、点Ｐ０に関する差分評価値ＳＡＤ（Ｐ０）を、周囲の４点（ダイヤモンドサーチパターン）の差分評価値ＳＡＤ（Ｐｉ）と比較する（ｉ＝１、２、３、４）。
以下では、参照ブロックＢＫの左上端の点をＰとした場合、参照ブロックＢＫに対する差分評価値ＳＡＤ（ＢＫ）を、ＳＡＤ（Ｐ）とも表記し、上記２つの表現を適宜使い分ける。
【０１１３】
（探索経路ＳＲ）
図１２は、探索パターンＳＰとして、ダイヤモンドサーチパターン（Diamond Search Pattern；ｎｐ＝５）を用いた場合の、局所探索における探索経路ＳＲを示す図である。同図に示す探索経路ＳＲを、下記の数式（１６）の様に、記号的に表示する。
【０１１４】
【数１６】
2005253015.tif 000018
上記の探索経路ＳＲは、各探索位置Ｐｉ（ｉ＝ａ、ｂ、ｃ、ｄ）を探索中心Ｐ０とする、探索パターンＳＰ内の５点における差分評価値ＳＡＤ（Ｐｎ）（ｎ＝０、１、・・・、４）の値を比較した結果に応じて、動きベクトルＭＶ＝（ｄｘ、ｄｙ）をシフトする事により、図中の点Ｐａで示す探索初期位置から、最終の探索中心である点Ｐｄまで、探索中心Ｐ０が移動した事を示す。
【０１１５】
まず、図中の点Ｐａにおける差分評価値ＳＡＤ（Ｐ０）を算出する。次に、点Ｐａを探索中心Ｐ０とする、探索パターンＳＰに含まれる周囲の点Ｐ１乃至Ｐ４における差分評価値、ＳＡＤ（Ｐ１）乃至ＳＡＤ（Ｐ４）を算出し、それらの値を、ＳＡＤ（Ｐ０）と比較する。点Ｐａにおける差分評価値ＳＡＤ（Ｐ０）が、探索パターンＳＰに含まれる、各点の差分評価値ＳＡＤ（Ｐｉ）（ｉ＝０、１、・・・、４）の中で最小であれば、点Ｐａを、差分評価値ＳＡＤの最小値を与える点とし、動きベクトルＭＶの探索を終了する。
【０１１６】
一方、そうでなければ、ＳＡＤ（Ｐ１）乃至ＳＡＤ（Ｐ４）の中で、最小値を与える点に、探索中心Ｐ０を移動する。例えば、図１２の点Ｐｂにおける差分評価値ＳＡＤ（Ｐ３）が最小であれば、探索中心を点Ｐｂに移動する。この様にして、差分評価値ＳＡＤの比較を繰り返しながら、探索中心Ｐ０をＰａ→Ｐｂ→Ｐｃ→Ｐｄ と移動し、最後に点Ｐｄにおいて、差分評価値ＳＡＤ（Ｐ０）が、探索パターンＳＰの各点の差分評価値ＳＡＤ（Ｐ０）乃至ＳＡＤ（Ｐ４）の中で最小となった場合には、点Ｐｄ点を、差分評価値ＳＡＤの最小値を与える点とし、探索を終了する。
【０１１７】
このように、探索中心Ｐ０における差分評価値ＳＡＤ（Ｐ０）を、探索パターンＳＰ内の周囲の点Ｐ１乃至Ｐ４の差分評価値ＳＡＤ（Ｐ１）乃至ＳＡＤ（Ｐ４）と比較し、ＳＡＤ（Ｐ０）が最小となるまで、上記の探索処理を繰り返す。上記の探索処理が終了した場合、その時点における探索中心Ｐ０の位置が、差分評価値ＳＡＤの最小値を与える点であり、点Ｐ０を左上端とする参照ブロックＢＫが、最適参照ブロックＭＢＫとなる。上記探索の結果から、カレントブロックＣＢＫに対する、最適参照ブロックＭＢＫのシフト量（ｄｘ、ｄｙ）として、整数画素精度の動きベクトルＭＶが求められる。
【０１１８】
（整数画素精度の動きベクトルの探索処理）
図１３は、整数画素精度の動きベクトル探索の、処理手順を示すフローチャートである。
制御部１４は、ＣＰＵ３から動作開始の命令を受けると、まず、符号化の対象である符号化画像内のカレントブロックをフレームメモリ６の、現フレームメモリ８から読み出して、カレントブロックメモリ１１に格納すると共に、既に符号化された参照画像内の所定の範囲を、フレームメモリ６の、参照フレームメモリ９から読み出して、参照領域メモリ１２に格納する（ステップＳ３００）。
【０１１９】
次に、制御部１４は、探索パターンＳＰとして、図１１に示すような、ブロックサーチパターン、又はダイヤモンドサーチパターンのいずれかを選択すると共に、探索打切り回数を設定する（ステップＳ３０１）。
次に、探索回数Ｎｓに０をセット（ステップＳ３０２）した後、参照ブロックの所定の探索範囲ＳＡ内で、探索位置を決定し、それを探索中心Ｐ０とすると共に、アドレス生成部１３は、参照領域メモリ１２内において、Ｐ０を左上端とする参照ブロックの画素データのアドレスを生成する（ステップＳ３０３）。
【０１２０】
差分評価値演算部２１は、探索初期位置、及びサーチパターンが設定された後、探索中心Ｐ０を中心として、図１１に示すような、探索パターンＳＰ内の各位置Ｐ０〜Ｐ４における差分評価値ＳＡＤ（ＢＫｎ）（ｎ＝０、１、・・・、４）を計算し、差分特徴量比較部２２に出力する（ステップＳ３０４）。
同様に、差分評価値演算部２１は、前述の差分特徴量比較結果算出処理（図６参照）において、各ブロック当り２５６個の差分特徴量ＣＨＤ（ＢＫｎ）ｋｌを算出し、差分特徴量比較部２２に出力する（ステップＳ３０５）。
【０１２１】
上記の差分評価値ＳＡＤ（ＢＫｎ）、及び差分特徴量ＣＨＤ（ＢＫｎ）ｋｌ（ｎ＝０、１、・・・、４；ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）を受け取った差分特徴量比較部２２は、後述の第１終了判定処理（図１４参照）において、探索処理を終了するか否かの判定を行う（ステップＳ３０６）。
前記の第１終了判定処理においては、探索中心Ｐ０が最小ＳＡＤ位置となった場合、又は、探索回数が、予め設定した探索打ち切り回数に達した場合に、探索を終了する。探索パターンＳＰ内の各点Ｐ０〜Ｐ４の中で、ＳＡＤが最小となる位置ＭＩＮを検出する。最小ＳＡＤを与える位置ＭＩＮが、探索中心Ｐ０である場合（ＭＩＮ＝０）には、その位置Ｐ０が、最適参照ブロックＭＢＫであるとして、終了フラグを立てる。
【０１２２】
また、探索中心Ｐ０が、最小ＳＡＤを与える位置とならなくても、探索回数が、予め設定した探索打ち切り回数Ｎｓに達した場合には、同様に終了フラグを立てる。
第１終了判定処理からリターンした際に、終了フラグが立っている場合（ステップＳ３０７：Ｙｅｓ）、探索処理を終了する、一方、そうでなければ（ステップＳ３０７：Ｎｏ）、次のステップＳ３０８の、第２終了判定処理（図１５参照）に進む。
【０１２３】
ステップＳ３０８の第２終了判定処理については後述するが、第２終了判定部８１の第２判定部９７は、ＳＡＤ０レジスタ９６、ＳＡＤレジスタ９０、差分特徴量比較結果レジスタ９５から、それぞれＳＡＤ（Ｐ０）、ＳＡＤ（Ｐｎ）（ｎ＝１、２、３、４）、差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）、及び、予め設定したしきい値Ｔｈ１、Ｔｈ２を用いて、下記の不等式
【０１２４】
【数１７】
2005253015.tif 000019
【０１２５】
【数１８】
2005253015.tif 000020
が成立するか否かの判定を、各ｎ（ｎ＝１、２、３、４）について行い、上記不等式（１７）、及び不等式（１８）が、あるｎに対して、共に真となった場合、探索中心Ｐ０と、周辺Ｐｎ（ｎ＝１、２、３、４）との間の半画素位置での内挿予測の効果が大きいとして、終了フラグを立てる。
【０１２６】
第２終了判定処理からリターンした際に、終了フラグが立っている場合（ステップＳ３０９：Ｙｅｓ）、探索処理を終了する一方、そうでない場合（ステップＳ３０９：Ｎｏ）には、次のステップＳ３１０に進む。
次のステップＳ３１０において、アドレス生成部１３は、周辺の最小ＳＡＤ位置である探索パターン内の点Ｐ１乃至Ｐ４の内のいずれかの点に探索中心Ｐ０を移動（ステップＳ３１０）し、制御部１４は、探索回数Ｎｓに１を加算（ステップＳ３１１）し、再びステップＳ３０４に戻り、新しい位置におけるサーチパターン内の各点Ｐ０〜Ｐ４について、差分評価値ＳＡＤ（ＢＫｎ）、及び差分特徴量ＣＨＤ（ＢＫｎ）ｋｌ（ｎ＝０、１、２、・・・、４）を算出する演算を繰り返す。
【０１２７】
探索が終了した際には、差分評価値演算部２１は、制御部１４に対し、終了通知、及び動きベクトルＭＶを出力し、整数画素精度の動きベクトル探索処理を終了する。
（整数画素精度の動きベクトル探索終了後の処理）
終了判定部２３から、上記の終了通知を受け取った制御部１４は、局所探索によって得られた動きベクトルＭＶを、後続の処理部（不図示）に転送すると共に、探索経路ＳＲ内でＳＡＤの最小値を与える参照ブロックの位置に関する情報を、「ＭＩＮＳＡＤ位置情報」として制御部１４に通知した後、現フレームの、次の位置のカレントブロックに対する動きベクトル検出を行う為、最適参照ブロックＭＢＫの探索処理を繰り返す。
【０１２８】
（第1終了判定処理）
図１４は、終了判定部２３が行う、整数画素精度の動きベクトル探索の、第1終了判定処理の手順を示すフローチャートである。
終了判定部２３は、探索中心Ｐ０が、最小ＳＡＤ位置か否かを判定する（ステップＳ４００）。前記判断結果が肯定的な場合（ステップＳ４００：Ｙｅｓ）、差分評価値演算部２１は、探索中心Ｐ０の位置から、動きベクトルＭＶを算出（ステップＳ４０１）し、終了フラグを立てた後（ステップＳ４０２）、呼び出し元にリターンする。
【０１２９】
一方、ステップＳ４００において、判断結果が否定的な場合（ステップＳ４００：Ｎｏ）、終了判定部２３は、探索回数Ｎｓが、探索打切り回数に達したか否かを判断し（ステップＳ４０３）、前記判断結果が肯定的な場合（ステップＳ４０３：Ｙｅｓ）、同様にステップＳ４０２に進み、終了フラグを立ててリターンする。一方、前記判断結果が否定的な場合には（ステップＳ４０３：Ｎｏ）、終了フラグを立てずに、そのままリターンする。
【０１３０】
（第２終了判定処理）
図１５は、終了判定部２３が行う、整数画素精度の動きベクトル探索の、第２終了判定処理の手順を示すフローチャートである。
終了判定部２３は、まず、しきい値Ｔｈ１、Ｔｈ２を設定（ステップＳ５００）し、次に、ｎに１を代入する（ステップＳ５０１）。その後、ｎの各値に対して、数式（１７）に示した様に、ＳＡＤ（Ｐｎ）−ＳＡＤ（Ｐ０）＜Ｔｈ１が成立するか否か（ステップＳ５０２）を判定する。
【０１３１】
前記判定結果が肯定的な場合（ステップＳ５０２：Ｙｅｓ）、次に、数式（１８）に示した様に、ＲＥＳ（ＢＫ０、ＢＫｎ）＞Ｔｈ２が成立するか否かについて判断する（ステップＳ５０３）。前記判定の結果が肯定的な場合（ステップＳ５０３：Ｙｅｓ）、次のステップＳ５０４に進み、探索中心Ｐ０の位置から、動きベクトルＭＶを算出（ステップＳ５０４）した後、終了フラグを立てて（ステップＳ５０５）、リターンする。
【０１３２】
一方、ステップＳ５０２における判断結果が否定的な場合（ステップＳ５０２：Ｎｏ）、又はステップＳ５０３における判断結果が否定的な場合（ステップＳ５０３：Ｎｏ）、終了判定部２３は、ｎに１を加算（ステップＳ５０６）し、ｎの値が５（＝ｎｐ）以上であるか否かを判断（ステップＳ５０７）し、前記判断結果が否定的な場合（ステップＳ５０７：Ｎｏ）、ステップＳ５０２に戻り、次のｎの値に対して、ステップＳ５０２以下の処理を繰り返す一方、ｎの値が５（＝ｎｐ）以上の場合（ステップＳ５０７：Ｙｅｓ）には、そのままリターンする。
【０１３３】
（半画素精度の動きベクトルの探索処理）
図１６は、半画素精度の動きベクトル探索の、処理手順を示すフローチャートである。
整数画素精度の探索終了後は、図２８に示すような半画素位置の８点（Ｐ１〜Ｐ８）で、半画素精度のＳＡＤ演算を行い、整数画素精度の動きベクトルＭＶの探索で得られた、ＳＡＤの最小値との比較を行う事により、半画素精度の動きベクトルＭＶ２の探索を行う。
【０１３４】
図１３において示した、整数画素精度の動きベクトル探索のフローチャートの第２終了判定処理Ｓ３０８において、差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）の各値は、既に算出されている為、これらの値ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）の中から、最大値を与えるｎの値を求め、それをｒとする（ステップＳ６００）。
【０１３５】
ここで、差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）は、２つの参照ブロックＢＫ０、及びＢＫｎについて、カレントブロックＣＢＫとの画素データの差分を取ったものである、２つの「差分ブロック」（ＣＢＫ−ＢＫ０）、及び（ＣＢＫ−ＢＫｎ）の各画素データを比較し、その符号が反転している画素の個数を表す。
上記の差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）のうち、その最大値を与えるｒに対する差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｒ）は、４個のＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）の中で、差分符号が反転している画素の個数が最も多いものであり、差分符号が反転している画素の個数が多いという事は、２つの参照ブロックＢＫ０とＢＫｒとの中間において、半画素精度の参照ブロックＨＢＫｒを、補間により生成した場合、当該ＨＢＫｒに対する差分が、ほぼ０となる事、即ち、カレントブロックＣＢＫの画素データに、ほぼ等しい画素データを持つ最適参照ブロックＭＨＢＫとなる可能性が最も高いという事を示している。
【０１３６】
図１７は、差分符号が同符号の場合と、異符号（符号が反転している）の場合とを比較した図である。同図に示す様に、カレントブロックＣＢＫ、及び２つの参照ブロックＢＫ０、ＢＫ１について、（ｋ、ｌ）で指定される位置の画素データｃklと、skl（Ｐ０）、skl（Ｐｎ）（ｎ＝１、２、３、４）との差分（ｃkl−skl（Ｐ０））、（ｃkl−skl（Ｐｎ））を取った場合に、この２つの差分値が同符号の場合には、２点Ｐ０、及びＰｎの中点（（Ｐ０＋Ｐｎ）／２）の半画素位置における値は、０にはならない（（ａ）の場合）が、差分値が異符号の場合には、２点Ｐ０、及びＰｎの中点（（Ｐ０＋Ｐｎ）／２）の半画素位置における値が、ほぼ０になる（（ｂ）の場合）。
【０１３７】
何故なら、下記の数式（２０）の様に、異なる２点Ｐ０、及びＰｎ（ｎ＝１、２、３、４）に対して、それぞれ値Ｆ（Ｐ０）＝（ｃkl−skl（Ｐ０））、及びＦ（Ｐｎ）＝（ｃkl−skl（Ｐｎ））を対応させ、その間の任意の点Ｘ（Ｐ０≦Ｘ≦Ｐｎ、又はＰｎ≦Ｘ≦Ｐ０）に対して、下記の様な関数値Ｆ（Ｘ）を対応させる、任意の連続関数
【０１３８】
【数１９】
2005253015.tif 000021
を考えると、上記の異なる２点Ｐ０、及びＰｎにおける関数値Ｆ（Ｐ０）、及びＦ（Ｐｎ）が異符号であれば、２点Ｐ０、及びＰｎの間に、Ｆ（Ｐｚ）＝０となる点Ｐｚが、必ず存在するからである（中間値の定理）。
なお、上記の関数Ｆ（Ｘ）は、２点Ｐ０、及びＰｎにおける関数値が、Ｆ（Ｐ０）、及びＦ（Ｐｎ）であるものであれば何でも良いが、図１７では特に、Ｆ（Ｘ）を一次関数とし、２点Ｐ０、及びＰｎの間を、直線で線形補間した場合を示している。
【０１３９】
上記は、各ブロックにおいて、２つの変数（ｋ、ｌ）で指定される特定の１画素に注目した場合について述べたものであり、１６×１６個の画素から構成されるブロック全体では、上記の差分符号が異符号である画素の数をカウントする事により、２つの参照ブロックＢＫ０、及びＢＫｎの間に、半画素精度の最適参照ブロックＭＨＢＫが存在する可能性について評価する事ができる。
【０１４０】
即ち、２点Ｐ０、及びＰｎ（ｎ＝１、２、３、４）をそれぞれ左上端の点とする２つの差分ブロックＢＫ０、及びＢＫｎに関し、上記の差分（ｃkl−skl（Ｐ０））、及び（ｃkl−skl（Ｐｎ））の符号（＋、又は−）のみを、差分特徴量ＣＨＤ（ＢＫ０）ｋｌ、ＣＨＤ（ＢＫｎ）ｋｌとして取り出した後、前記２つの差分特徴量に含まれる２５６個の符号を、各々１つずつ取り出して比較する。これらの符号の比較を、２５６組全てについて行い、２つのブロック間で、符号の正負が変化しているものの個数をカウントする。
【０１４１】
前記カウントの結果を、差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）とし、この様にして得られた４個の差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）の中で、値が最大のものを、ＲＥＳ（ＢＫ０、ＢＫｒ）（１≦ｒ≦４）とすれば、２つのブロックＢＫ０、及びＢＫｒの間の半画素位置にある半画素ブロックＨＢＫ（０、ｒ）が、求める半画素精度の最適参照ブロックＭＨＢＫであり、この半画素精度の最適参照ブロックＭＨＢＫに対応するシフト量が、半画素精度の動きベクトルＭＶ２である。
【０１４２】
従って、本実施の形態の動きベクトル検出装置１は、半画素精度の動きベクトル検出を行う際に、背景技術の項で述べたような、処理負荷が重く、かつ画素データの冗長性の高い、半画素精度の参照ブロックを生成する事なく、半画素精度の動きベクトルＭＶ２を推定する事ができる。
上記のステップＳ６００における比較を行った結果、ｎ＝ｒ（１≦ｒ≦４）において、ＲＥＳ（ＢＫ０、ＢＫｎ）が最大となったとすると、Ｐ０とＰｒとの間の半画素位置が、半画素精度の動きベクトルＭＶ２に対応する位置である可能性が高いと推定される。
【０１４３】
次のステップＳ６０１において、Ｐ０とＰｒとの間の半画素位置Ｐｓ0、もしくは、隣接する斜め方向の半画素位置Ｐｓ1、Ｐｓ2をも含めた３点について、内挿演算部２４が、参照領域メモリ１２の画素データを半画素化する事により、半画素精度のブロックＨＢＫ０乃至ＨＢＫ２を生成する。
次に、差分評価値演算部２１が、上記３つの半画素精度の半画素精度のブロックＨＢＫ０乃至ＨＢＫ２について、差分評価値ＳＡＤ（ＨＢＫ０）乃至ＳＡＤ（ＨＢＫ２）を算出し（ステップＳ６０２）、整数画素精度の最小ＳＡＤ値と比較する（ステップＳ６０３）。
【０１４４】
上記の半画素位置Ｐｓ0、Ｐｓ1、Ｐｓ2の３点に対応するＳＡＤの値、ＳＡＤ（ＨＢＫ０）、ＳＡＤ（ＨＢＫ１）、ＳＡＤ（ＨＢＫ２）の内、整数画素精度の最小ＳＡＤ値（ＭＩＮＳＡＤ）よりも小さいものがある場合（ステップＳ６０３：Ｙｅｓ）には、その中でＳＡＤが最小となる半画素ブロックＨＢＫｍｉｎを検出（ステップＳ６０４）し、当該検出された半画素ブロックＨＢＫｍｉｎに対応した動き量が、半画素精度の動きベクトルＭＶ２となる（ステップＳ６０５）。
【０１４５】
一方、上記の３点の中に、整数画素精度の最小ＳＡＤ値（ＭＩＮＳＡＤ）よりも小さいものがない場合（ステップＳ６０３：Ｎｏ）には、整数画素精度の最小ＳＡＤ値（ＭＩＮＳＡＤ）に対応した動きベクトルＭＶが、そのまま半画素精度の動きベクトルＭＶ２となる（ステップＳ６０６）。
なお、上記の半画素精度の差分評価値ＳＡＤを算出する３点、Ｐｓ0、Ｐｓ1、Ｐｓ2は、必ずしも３点全てが必要ではなく、Ｐｓ0の１点のみについて、半画素精度の差分評価値ＳＡＤ（ＨＢＫ０）を算出し、整数画素精度の最小ＳＡＤ値（ＭＩＮＳＡＤ）と比較しても良い。
【０１４６】
この様に、整数画素精度の動きベクトル探索において算出した差分評価値ＳＡＤ（ＢＫ）、及び差分特徴量ＣＨＤ（ＢＫ）ｋｌのみを用いる事により、半画素精度の参照ブロックを生成する事なく、半画素精度の動きベクトルＭＶ２に対応する位置である可能性が高い点を推定できる事が、本実施の形態の動きベクトル検出装置の特長である。
なお、当該推定された半画素精度の動きベクトルＭＶ２に対応する位置が、実際に差分評価値ＳＡＤの最小値である事を確認する為に、当該位置（Ｐｓ0）、及びその周囲の２点（Ｐｓ1、及びＰｓ2）において、実際に画素データの補間を行って、半画素精度の参照ブロックＨＢＫを３個生成し、それらに対するＳＡＤの値を計算する事により、前記３点のうちのいずれかが、実際にＳＡＤの最小値を与える事を確認している。
【０１４７】
図１８は、上記の半画素精度の動きベクトルの探索処理を、例を挙げて説明した図である。同図の（ａ）は、１つの探索パターンＳＡ（ダイヤモンドサーチパターン、ｎｐ＝５）内において、差分特徴量比較結果の表を示す図であり、また、（ｂ）は、上記の探索パターンＳＡにおける、各点Ｐ０〜Ｐ４の配置を示す図である。なお、同図（ｂ）においては、半画素位置の点Ｐ５〜Ｐ７も表示している。
【０１４８】
図１８の（ａ）に示す差分特徴量比較結果の表において、「比較する参照ブロックの位置」の行の点の組（Ｐ０、Ｐｉ）（ｉ＝１、２、３、４）は、差分特徴量ＣＨＤ（ＢＫ）ｋｌ＝ｓｇｎ（ｃkl−ｓkl）を比較する２つの参照ブロックＢＫ０、及びＢＫｉ（ｉ＝１、２、３、４）の左上端の点が、Ｐ０、及びＰｉである事を示している。
「符号変化数」の行は、上記の２点（Ｐ０、Ｐｉ）の各組について、差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｉ）が対応する事を示し、その値を、次の「上記の値（例）」の行に、例として示している。
【０１４９】
図１６において示した、半画素精度の動きベクトルの探索処理におけるステップＳ６００において、同表における「上記の値（例）」の行に示す各値を比較する事により、ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）の中から、最大値を与えるｎの値が、ｎ＝２である事が分かり、従って、ｒ＝２となる。上記の比較により、次のステップＳ６０１では、ｒ＝２において、ＲＥＳ（ＢＫ０、ＢＫｒ）が最大となる為、図１８（ｂ）に示すＰ０とＰ２との間の半画素位置Ｐ５、もしくは、両隣の斜め方向（Ｐ０から見て）の半画素位置Ｐ６、及びＰ７をも含めた３点について、内挿演算部２４が、参照領域メモリ１２の画素データを半画素化し、半画素精度の参照ブロックＨＢＫ（Ｐ５）、ＨＢＫ（Ｐ６）、及びＨＢＫ（Ｐ７）を生成する。
【０１５０】
その後、ステップＳ６０２において、差分評価値演算部２１が、上記のＨＢＫ（Ｐ５）〜ＨＢＫ（Ｐ７）に対し、半画素精度の差分評価値ＳＡＤ（Ｐ５）〜ＳＡＤ（Ｐ７）を算出するＳＡＤ演算を行った後、次のステップＳ６０３において、整数画素精度の最小ＳＡＤの値（ＭＩＮＳＡＤ）と比較する。
次のステップＳ６０４において、上記の半画素位置Ｐ５、Ｐ６、Ｐ７の３点に対応するＳＡＤの値、ＳＡＤ（Ｐ５）〜ＳＡＤ（Ｐ７）の内、整数画素精度の最小ＳＡＤ値（ＭＩＮＳＡＤ）よりも小さいものがある場合には、ステップＳ６０４において、その点に対応する半画素精度のブロックを、ＳＡＤの最小値を与える半画素ブロックＨＢＫｍｉｎとし、ステップＳ６０５において、当該検出された半画素ブロックＨＢＫｍｉｎに対応する動きベクトルを、半画素精度の動きベクトルＭＶ２とする。
【０１５１】
一方、上記の３点、Ｐ５〜Ｐ７の中に、整数画素精度の最小ＳＡＤ値（ＭＩＮＳＡＤ）よりも小さいものがない場合には、ステップＳ６０６において、整数画素精度の最小ＳＡＤ値（ＭＩＮＳＡＤ）に対応した動きベクトルＭＶを、そのまま半画素精度の動きベクトルＭＶ２とする。
（まとめ）
このように、差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）を用いることで、処理負荷が重く、かつ画素データの冗長性が高い、半画素精度の参照ブロックＨＢＫを生成する処理を行う事なく、半画素精度の最適参照ブロックＭＨＢＫの位置を推定する事が出来る。
【０１５２】
勿論、当該推定された半画素精度の最適参照ブロックＭＨＢＫが、本当に差分評価値ＳＡＤの最小値を与えるか否かを確認する為には、整数画素精度の動きベクトル探索処理で得られた参照ブロックＢＫの周辺において、実際に、半画素精度の参照ブロックＨＢＫを１〜３個、画素データの補間により生成し、半画素精度の差分評価値ＳＡＤ（ＨＢＫ）を算出して、整数画素精度での最小ＳＡＤ値、ＳＡＤ（ＢＫ）と比較しなければばらないが、それでも、従来の様に、最初から８個の半画素ブロックＨＢＫを生成し、半画素精度の差分評価値ＳＡＤ（ＨＢＫ）をそれぞれ算出して、整数画素精度の差分評価値ＳＡＤ（ＢＫ）と比較する方式に比べれば、大幅に演算量を削減する事ができる。
【０１５３】
（実施の形態２）
実施の形態１では、半画素精度の最適参照ブロックＭＨＢＫの位置の推定に際し、画素データの差分の「符号」しか考慮していなかったが、本実施の形態では、ブロック間の画素データの差分の「符号」に加え、差分の「大きさ」を考慮する。これにより、半画素精度の最適参照ブロックＭＨＢＫの位置の推定精度が、実施の形態１よりも向上する。
【０１５４】
＜構成＞
本実施の形態では、ＰＥ１４１乃至１４８を含んで構成される差分評価値演算部１３０、及び差分特徴量比較部１３１が、実施の形態１と異なるが、上記以外の構成は全く同じである。なお、符号は、実施の形態１で説明したものと共通する部分には、同一の符号を付して、その説明を省略する。
【０１５５】
（ＰＥの構成）
図１９は、本実施の形態のＰＥ（ＰＥ１４１乃至１４８）の構成を示す機能ブロック図である。
本実施の形態では、ブロック間の画素データの差分の「符号」に加え、差分の「大きさ」を考慮する為、本実施の形態のＰＥ（ＰＥ１４１乃至１４８）は、図３に示す構成に加えて、更に量子化器１１０、及びビット結合器１１１を備える。
【０１５６】
上記の量子化器１１０、ビット結合器１１１は、差分絶対値｜ｃkl−ｓkl｜が算出された後、これを量子化器１１０が、下記の数式（２０）の様に量子化を行い、３ビットの差分量子化値ｑａｄ(ｋ、ｌ)を生成する。
【０１５７】
【数２０】
2005253015.tif 000022
得られた３ビットの差分量子化値ｑａｄ(ｋ、ｌ) （ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）に対し、ビット結合器１１１が、１ビットの差分符号ｓｇｎ（ｃkl−ｓkl）とビット列を結合し、４ビットとしたものを、本実施の形態の差分特徴量ＣＨＤ（ＢＫ）ｋｌとする。
【０１５８】
即ち、本実施の形態の差分特徴量ＣＨＤ（ＢＫ）ｋｌは、下記の数式（２１）で表される。なお、以下の数式において、演算“｜｜”は、「ビット列の結合」を表すものとする。
【０１５９】
【数２１】
2005253015.tif 000023
（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）
上記の量子化器１１０、及びビット結合器１１１により、上記の数式（２１）によって定義される差分特徴量ＣＨＤ（ＢＫ）ｋｌが生成され、差分特徴量バス１３５を介し、差分特徴量比較部１３１に出力される。差分特徴量ＣＨＤ（ＢＫ）ｋｌ＝ｓｇｎ（ｃkl−ｓkl）｜｜（差分量子化値）（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）を出力する差分特徴量バス１３５のバス幅は、３２（＝４ビット×８）ビットである。
【０１６０】
（ＰＥの機能）
本実施の形態のＰＥ１４１乃至１４８は、カレントブロックメモリ１１のポートｃ、及び参照領域メモリ１２のポートｓから順次供給される、カレントブロック、及び参照ブロックの画素データｃkl、及びｓkl（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）に対し、差分絶対値｜ｃkl−ｓkl｜を算出すると共に、画素データｃkl、及びｓklから生成される、１ビットの差分符号ｓｇｎ（ｃkl−ｓkl）、及び３ビットの差分量子化値ｑａｄ(ｋ、ｌ)を、ビット結合を行う事により、４ビットの差分特徴量ＣＨＤ（ＢＫ）ｋｌ（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）を毎周期（サイクル）１個生成し、差分特徴量バス１３５を介し、差分特徴量比較部１３１に出力する。
【０１６１】
（差分評価値演算部１３０の構成）
図２０は、本実施の形態の差分評価値演算部１３０の構成を示す機能ブロック図である。差分評価値演算部１３０は、実施の形態１の差分評価値演算部２１と比べて、８個のＰＥ（ＰＥ１４１乃至１４８）、及び３２ビットの差分特徴量バス１３５のみが異なるのみであり、他の部分は、実施の形態１と同じである。
【０１６２】
（差分評価値演算部１３０の機能）
差分評価値演算部１３０は、ＰＥ１４１乃至１４８の８個のＰＥにより、３２周期（サイクル）毎に１個生成される差分評価値ＳＡＤ（ＢＫ）を、終了判定部２３に対して出力する一方、毎周期（サイクル）並列に８個生成される４ビットの差分特徴量ＣＨＤ（ＢＫ）ｋｌ（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）を、３２ビットの差分特徴量バス１３５を介し、毎周期８個並列に差分特徴量比較部１３１に対して出力する。
【０１６３】
（差分特徴量比較部１３１の構成）
図２１は、本実施の形態の差分特徴量比較部１３１の構成を示す、機能ブロック図である。差分特徴量比較部１３１は、上記の３２ビット幅の差分特徴量バス１３５を介して、差分特徴量ＣＨＤ（ＢＫ）ｋｌを受け取り、対応する差分画素データ（ｃkl−ｓkl）の符号である、１ビットの差分符号ｓｇｎ（ｃkl−ｓkl）、及び３ビットの差分量子化値ｑａｄ(ｋ、ｌ)を、各差分ブロックに対応するバンクに、それぞれ格納する（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）。この為、バンク０乃至バンク４の容量は、３２ビット×３２×５＝１０２４×５ビットと、実施の形態１の各バンクの容量と比べ、４倍になっている。
【０１６４】
（差分特徴量比較部１３１の機能）
本実施の形態の差分特徴量比較部１３１は、バンク０乃至バンク４の各バンクが、３２ビット×３２＝１０２４ビットの容量があり、各バンクは、対応する差分ブロックの、対応する差分画素データ（ｃkl−ｓkl）の符号である、１ビットの差分特徴量＝ｓｇｎ（ｃkl−ｓkl）、及び３ビットの差分量子化値ｑａｄ(ｋ、ｌ)を、それぞれ格納する（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）と同時に、比較器１４７にも入力し、各ブロックの画素データから生成された差分特徴量の比較を行う事により、４個の差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）を生成し、終了判定部２３に対して出力する。
【０１６５】
図２２は、差分特徴量比較部１３１が行う、差分特徴量カウント処理の処理手順を示すフローチャートである。
差分特徴量比較部１３１は、まず、変数ｋ、及びｌに０をセットする（ステップＳ７００）。
次に、２つの参照ブロックＢＫｉ、及びＢＫ０に関する、２５６個の差分特徴量、ＣＨＤ（ＢＫｉ）ｋｌとＣＨＤ（ＢＫ０）ｋｌ（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）とを比較し、（ｋ、ｌ）の組を１つ定める事により指定される、それぞれの差分符号（ｓｇｎ（ｃkl−ｓkl））の値が、一致していなければ（ステップＳ７０１：Ｙｅｓ）、次のステップＳ７０２に進み、また一致していれば（ステップＳ７０１：Ｎｏ）、ステップＳ７０４に進む。
【０１６６】
同様に、（ｋ、ｌ）の組を１つ定める事により指定される、それぞれの差分量子化値ｑａｄ(ｋ、ｌ)の値が一致していれば（ステップＳ７０２：Ｙｅｓ）、次のステップＳ７０３に進み、ＲＥＳ（ＢＫ０、ＢＫｉ）を、“１”インクリメントした後、ステップＳ７０４に進み、また一致していなければ（ステップＳ７０２：Ｎｏ）、ステップＳ７０４に進む。
【０１６７】
次のステップＳ７０４において、差分特徴量比較部１３１は、変数ｌを“１”インクリメントする（ステップＳ７０４）し、ｌが８以上でなければ（ステップＳ７０５：Ｎｏ）、ステップＳ７０１に戻り、次のｌに関する比較処理を繰り返す一方、ｌが８以上であれば（ステップＳ７０５：Ｙｅｓ）、ステップＳ７０６に進み、変数ｌに０をセットすると共に、変数ｋを“１”インクリメントする。
【０１６８】
次のステップＳ７０７において、ｋが３２以上でなければ（ステップＳ７０７：Ｎｏ）、ステップＳ７０１に戻り、次のｋに関する比較処理を繰り返す一方、ｋが３２以上であれば（ステップＳ７０７：Ｙｅｓ）、差分特徴量カウント処理を終了し、呼び出し元にリターンする。
＜全体の動作＞
本実施の形態の動きベクトル検出装置の動作が、実施の形態１の動きベクトル検出装置１の動作と異なる点は、参照ブロックＢＫから生成される差分特徴量として、画素データの差分符号ｓｇｎ（ｃkl−ｓkl）だけでなく、差分の大きさ（｜ｃkl−ｓkl｜）をも考慮し、更にこれを所定の数値Ｑで除算する量子化を行った上で、差分データを比較する事により、半画素精度の参照ブロックＨＢＫの位置の推定を行う点である。
【０１６９】
より具体的には、１ビットの差分符号ｓｇｎ（ｃkl−ｓkl）と、３ビットの差分量子化値ｑａｄ(ｋ、ｌ)＝｜ｃkl−ｓkl｜／Ｑ（Ｑは、量子化の定数）からなる４ビットの差分特徴量ＣＨＤ（ＢＫ）ｋｌ（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）を生成し、４×８＝３２ビットの差分特徴量ＣＨＤ（ＢＫ）ｋｌを、比較器１４７に対して並列に入力し、比較する。
【０１７０】
ここで、画素データのビット数（符号ビットを除いた部分）がＭビット（Ｍ≧３）であるとすると、画素データの差分絶対値｜ｃkl−ｓkl｜も、Ｍビットである。これを量子化の定数Ｑで除算したものが、３ビットとなる為には、量子化の定数Ｑは、被除数を（Ｍ−３）ビット右シフトさせる数、即ち、Ｑ＝２M-3となる。例えば、画素データの符号を除いた部分が、７ビットで表される場合、これを量子化の定数Ｑで除算したものが３ビットとなる為には、量子化の定数Ｑは、Ｑ＝２7-3＝１６とする。
【０１７１】
比較器１４７には、８個の並列に接続されたＰＥから、４×８＝３２ビットの差分特徴量ＣＨＤ（ＢＫ）ｋｌが、３２ビットの差分特徴量バス１３５を介して、毎周期（サイクル）入力される。当該比較器１４７では、上記入力された差分特徴量ＣＨＤ（ＢＫ）ｋｌに対し、ビット毎の比較を行い、差分符号（ｓｇｎ（ｃkl−ｓkl））が不一致で、かつ差分量子化値（ｑａｄ(ｋ、ｌ)＝｜ｃkl−ｓkl｜／Ｑ）が一致する場合を“１”としてカウントし、それ以外を“０”として、カウンタ１４８に対して値を出力し、当該出力された比較結果を、カウンタ１４８がカウントする。
【０１７２】
上記の様にして、１ブロック分の画素全体について、カウンタ１４８がカウントした値を、差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）として、終了判定部２３に対して出力する。
終了判定部２３では、上記の４個の差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）の値をそれぞれ比較し、この値が最大となるものに対応した参照ブロックＢＫｒ（１≦ｒ≦４）と、ＢＫ０との中間の半画素位置を、半画素精度の最適参照ブロックＭＨＢＫが存在する可能性が、最も高い位置と推定する。上記以外の動作は、実施の形態１の動きベクトル検出装置１の動作と同様である。
【０１７３】
これにより、半画素精度の最適参照ブロックＭＨＢＫの位置に対する推定精度が、実施の形態１よりも向上するが、ここで、差分の大きさ（｜ｃkl−ｓkl｜）を考慮する際に、量子化を行う理由、及び差分の大きさ（｜ｃkl−ｓkl｜）を考慮する事により、半画素精度の動きベクトルＭＶ２の推定精度が向上する理由について、以下に説明する。
（差分の大きさを量子化する理由）
本実施例では、下記に述べる様に、画素データの差分符号ｓｇｎ（ｃkl−ｓkl）だけでなく、差分の大きさ（｜ｃkl−ｓkl｜）をも考慮するが、２つの整数画素Ｐ０、及びＰｉ（ｉ＝１、２、３、４）の間で、画素データの差分の絶対値｜ｃkl−ｓkl（Ｐ０）｜、及び｜ｃkl−ｓkl（Ｐｉ）｜の比較を行う場合、比較器１４７において、各ビット毎にビット値（“０”、又は“１”）の比較を行う。
【０１７４】
ここで、画素データのビット数（符号ビットを除いた部分）がＭビット（Ｍ≧３）であるとすると、比較器１４７において比較される２つの値｜ｃkl−ｓkl（Ｐ０）｜と｜ｃkl−ｓkl（Ｐｉ）｜も、Ｍビットであり、この為、比較器１４７が、｜ｃkl−ｓkl（Ｐ０）｜と｜ｃkl−ｓkl（Ｐｉ）｜とを比較して、「一致している」と判定するのは、上記２つのＭビットの値が、全て一致する場合のみである。一方、上記Ｍビットの値のうち、１ビットでも異なるビットがあれば、「一致していない」と判定する。
【０１７５】
この様に、比較器１４７における比較は、Ｍビットの完全一致であり、２Mの分解能（精度）があるが、本実施例の様に、画素データの差分絶対値の比が１：１であるか否かを比較する場合には、その様な高い分解能は必要ではなく、１０進数にして１桁〜２桁の分解能、つまり、３ビット〜５ビットの比較を行えば十分である。逆に、ビット数が高いままで比較を行うと、分解能が高すぎる為、殆どの場合に比が１：１と判定されずに、カウント値が大幅に減少してしまう。
【０１７６】
このように、予め量子化を行って、差分の絶対値の比が１：１かどうかを判定する場合、画素データの差分の大きさ（｜ｃkl−ｓkl｜）を、量子化の定数Ｑで除算した値である、差分量子化値（ｑａｄ(ｋ、ｌ)＝｜ｃkl−ｓkl｜／Ｑ）のビット幅が増えるに従って、推定精度が上がるが、その一方で、大きさの比が１：１であると判定されにくくなり、カウント値が相対的に減少する事により、逆に推定精度の低下を招く。つまり、差分量子化値（ｑａｄ(ｋ、ｌ)）のビット幅（大きさの精度）と、カウント値とは、互いに相補的（Complemental）な関係にあり、上記２つのうち、片方のみを大きくしても意味が無い。
【０１７７】
この為、差分の大きさを比較する際に、所定の値Ｑ（量子化の定数）で除算する「量子化」を行い、分解能を予め下げた上で、画素データの差分の絶対値（｜ｃkl−ｓkl｜）の比較を行う。本実施の形態では、上記の差分量子化値（ｑａｄ(ｋ、ｌ)）のビット幅を３ビットとし、差分符号（１ビット）と、差分量子化値（３ビット）とからなる、４ビットの差分特徴量ＣＨＤ（ＢＫ）ｋｌ（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）を用いる事にし、差分の大きさの比較の精度を３ビットに落とす事により、カウンタ１４８によるカウント値を増大させ、大きさの比較精度と、カウント値とのバランスを保っている。
【０１７８】
（差分の大きさを考慮する事により、半画素精度の動きベクトルの推定精度が向上する理由）
図２３は、  整数画素間（Ｐ０、及びＰｉ（ｉ＝１、２、３、４））で、画素データの差分（（ｃkl−ｓkl（Ｐ０））、及び（ｃkl−ｓkl（Ｐｉ）））の符号が反転する場合に、２点Ｐ０、及びＰｉの間を、当該画素データの差分絶対値に応じて、内分する点を示す図であり、（ａ）では、ｍ：ｎ＝１：１に内分し、（ｂ）では、ｍ：ｎ＝２：１に内分し、（ｃ）では、ｍ：ｎ＝１：２に内分する。なお、ｓkl（Ｐ０）、ｓkl（Ｐｉ）の表記は、それぞれ点Ｐ０、及びＰｉを左上端の点とする参照ブロックＢＫ（Ｐ０）、及びＢＫ（Ｐｉ）の、添字ｋ、ｌで指定される画素位置の画素データ（輝度）を表し、また、ｍ、ｎは、下記の式（２２）に示す様に、２点Ｐ０、及びＰｉにおける画素データの差分の絶対値を表す。また、２点を内分する比の例として、本図では３つの場合（１：１、２：１、１：２）しか示していないが、実際には、ｍ、ｎは正の整数であり、種々の値を取りうる一方、本実施例では、ｍ、ｎの比が、１：１か否かが重要である。
【０１７９】
【数２２】
2005253015.tif 000024
同図に示す様に、２点Ｐ０、及びＰｉの間の点Ｐ（Ｐ０≦Ｐ≦Ｐｉ、または、Ｐｉ≦Ｐ≦Ｐ０）における画素データの値を求める為に、「線形補間」を用いて、画素データを線形に補間する場合、２つのブロック間の差分の符号（＋／−）が反転しており、かつ、その大きさ（絶対値）の比が、ｍ：ｎ＝１：１ならば、２つのブロックの中間の半画素位置（（Ｐ０＋Ｐｉ）／２）において、差分が０となる。この場合、画素データの差分の直線補間によるゼロ交差点Ｐｃは、２点Ｐ０、及びＰｉの中点（Ｐ０＋Ｐｉ）／２である。
【０１８０】
一方、同図の（ｂ）、及び（ｃ）に示す様に、２つのブロック間の差分の大きさの比ｍ：ｎが、１：１でなければ、２つのブロック間をｎ：ｍに内分する点Ｐｃにおいて、画素データの差分が０となるが、この場合、ゼロ交差点Ｐｃは、ｍ：ｎ＝１：１でなければ、２点Ｐ１とＰ２の中点（（Ｐ１＋Ｐ２）／２）ではなく、従ってＰｃは、半画素位置ではない。
【０１８１】
つまり、画素データの差分の直線補間を行う場合、ゼロ交差点Ｐｃが、２点Ｐ１とＰ２の中点（（Ｐ１＋Ｐ２）／２）の半画素位置となるのは、ｍ：ｎ＝１：１の場合のみである。
従って、本実施の形態では、２つの参照ブロックＢＫ（Ｐ０）、及びＢＫ（Ｐｉ）（ｉ＝１、２、３、４）の差分特徴量ＣＨＤ（ＢＫ０）ｋｌ、及びＣＨＤ（ＢＫｉ）ｋｌ（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）を比較する場合、前記２つの差分特徴量の、添字ｋ、ｌで指定される各要素の上位１ビットの差分符号ｓｇｎ（ｃkl−ｓkl）が反転しており、かつ、下位３ビットの差分量子化値ｑａｄ(ｋ、ｌ) ＝｜ｃkl−ｓkl｜／Ｑが等しい場合についてのみカウントを行う事により、探索の優先順位を付ける。
【０１８２】
上記の比較、及びカウント処理を、添字ｋ、ｌ（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）の異なる全ての組合わせについて行い、各ブロックに含まれる２５６個全ての画素に対する当該比較が行われた結果、得られるカウント値を、差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｉ）（ｉ＝１、２、３、４）とする。
更に、添字ｉ（ｉ＝１、２、３、４）の各値に対する４個の差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｉ）を互いに比較し、それらの中で値が最大のものが、ＲＥＳ（ＢＫ０、ＢＫｒ）（１≦ｒ≦４）であったとすると、５個の点Ｐｎ（ｎ＝０、１、２、３、４）を含むダイヤモンドサーチパターン（図１１（ｂ）参照）ＳＰにおいて、探索中心Ｐ０から、周囲の点Ｐｒ（１≦ｒ≦４）に向かう方向において、１ブロック分２５６個の画素のうち、ＲＥＳ（ＢＫ０、ＢＫｒ）個の画素について、画素データの差分値（ｃkl−ｓkl）（ｋ＝０、１、２、・・・、３１；ｌ＝０、１、２、・・・、７）の符号が、２点Ｐ０、及びＰｒにおいて反転し、しかも各画素データをそれぞれ直線補間した場合、２点Ｐ０とＰｒとの中点において、画素データの差分を補間した値が、ゼロとなる事が分かる。
【０１８３】
これは、探索パターンＳＰの探索中心Ｐ０から、周囲の各点Ｐｉ（ｉ＝１、２、３、４）を見た場合、半画素精度の動きベクトルＭＶ２の終点は、点Ｐｒの方向にある事、即ち、ＭＶ２＝（Ｐ０＋Ｐｒ）／２である可能性が最も高い事を示しており、従って、本実施の形態の動きベクトル検出装置では、半画素精度の動きベクトルＭＶ２の終点が、（Ｐ０＋Ｐｒ）／２であると推定し、この点（Ｐ０＋Ｐｒ）／２、及び、それに最も隣接する２つの半画素位置（図１８（ｂ）参照）を加えた３点に対し、差分評価値ＳＡＤを算出する事により、実際にＳＡＤの最小値（ＭＩＮＳＡＤ）を与える点かどうか検証を行う。
【０１８４】
以上に述べた事により、本実施の形態の動きベクトル検出装置では、実施の形態１の動きベクトル検出装置１に比べて、半画素精度の動きベクトルＭＶ２の推定精度が向上する。
（実施の形態３）
実施の形態１、及び実施の形態２では、時間的に過去の参照画像から現在の符号化画像を予測する順方向動き予測のみを取り上げたが、本実施の形態では、順方向動き予測に加え、未来の参照画像から動きベクトルを予測する、逆方向動き予測を加えた双方向動き予測を行う。
【０１８５】
図２４は、上記の双方向動き予測の概要を説明する為の図である。Ｂピクチャの符号化方法は、過去と未来の双方向から動き予測を行う、「内挿的（interpolative）フレーム間予測符号化」を行う。「内挿的フレーム間予測符号化」では、順方向予測と、逆方向予測の２つの予測結果に対し、下記の数式（２３）の様に、対応する画素間で、平均化を行う。
【０１８６】
【数２３】
2005253015.tif 000025
上式において、ＢＫＦ、及びＢＫＢは、それぞれ順方向、及び逆方向の最適参照ブロックであり、双方向動き予測の最適参照ブロックは、これらの丸め付き平均によって与えられる。
この様に、時刻ｔ１のカレント画像を符号化するために、過去（時刻ｔ０）と、未来（時刻ｔ２）の画像を用いた「双方向動き予測」を行うと、片方向だけの場合と比べ、過去と未来の参照画像で、２倍のＳＡＤ演算を行う必要がある。
【０１８７】
本実施の形態の動きベクトル検出装置は、時刻ｔ０における差分特徴量、及び時刻ｔ２における差分特徴量とを比較し、順方向動き予測の結果を用いて、逆方向動き予測を行うことで、逆方向の動き予測に要する差分評価値ＳＡＤの演算回数を削減する。
＜構成＞
本実施の形態では、実施の形態１と同様、図１に示す動きベクトル検出装置１を用いて、双方向動き予測を行う。本実施の形態では、実施の形態１、及び実施の形態２の動きベクトル検出装置の、「双方向動き予測」への適用例を示す。
【０１８８】
＜動作＞
（整数画素精度の双方向動き予測）
図２５は、整数画素精度の双方向動き予測の処理手順を示すフローチャートである。
まず、整数画素精度の順方向動き予測により、過去の参照画像から全探索や局所探索等の方式で動きベクトルを検出し、その位置の参照ブロックを、順方向の整数画素精度の最適参照ブロックＢＫＦとする（ステップＳ８００）。なお、整数画素精度の順方向動き予測の処理手順は、図１３に示した、整数画素精度の動きベクトル探索のフローチャートと同じである。
【０１８９】
次に、整数画素精度の逆方向動き予測により、未来の参照画像から、全探索や局所探索等の方式で動きベクトルを検出し、その位置の参照ブロックを、逆方向の整数画素精度の最適参照ブロックＢＫＲとする（ステップＳ８０１）。なお、整数画素精度の逆方向動き予測の処理手順は、図１３に示した、整数画素精度の動きベクトル探索のフローチャートと同じであるが、逆方向動き予測の場合の第２終了判定処理は、図２６のフローチャートの手順（後述する）に従う。
【０１９０】
これらの順方向、及び逆方向の整数画素精度の最適参照ブロックＢＫＦ、ＢＫＲを、上述の式（２３）の様に平均化し、双方向動き予測の最適参照ブロックＢＫＢ＝（ＢＫＦ＋ＢＫＲ）／２を生成する（ステップＳ８０２）。
最後に、これらの整数画素精度の最適参照ブロックＢＫＦ、ＢＫＲ、ＢＫＢについてそれぞれ算出した、整数画素精度の差分評価値ＳＡＤを比較し、前記差分評価値ＳＡＤの最小値を与える最適参照ブロックに対応した動きベクトルを、整数画素精度において、最も効果的に予測できる予測方向の動きベクトルＭＶとして選択する（ステップＳ８０３）。
【０１９１】
なお、ステップＳ８００と、ステップＳ８０１とは、逆順でもよい。
ＭＰＥＧでは、半画素精度の動き補償が採用されているため、上記の整数画素精度の双方向動き予測を行った後、更にその周辺において、内挿予測により、半画素精度の双方向動き予測を行う。
（逆方向動き予測において用いる第２終了判定処理）
図２６は、上記の逆方向動き予測において用いる、整数画素精度の動きベクトル探索の、第２終了判定処理の手順を示すフローチャートである。
【０１９２】
終了判定部２３は、まず、しきい値Ｔｈ３、Ｔｈ４をセットする（ステップＳ９００）。
次に、整数画素精度の順方向動き予測において、順方向動きベクトルＭＶＦを検出した際の、順方向最適参照ブロックＭＢＫＦにおける順方向最小差分評価値ＭＩＮＳＡＤＦを終了判定部２３に、また、順方向差分特徴量ＲＥＳ（ＢＫＦ０、ＢＫＦｎ）（ｎ＝１、２、３、４）を差分特徴量比較部２２に、それぞれセットする（ステップＳ９０１）。
【０１９３】
次に、ｎに１を代入（ステップＳ９０２）した後、ｎの各値に対し、下記の（２４）式で示される不等式
【０１９４】
【数２４】
2005253015.tif 000026
が成立するか否かを判定する（ステップＳ９０３）。
前記判定の結果が肯定的な場合（ステップＳ９０３：Ｙｅｓ）、逆方向差分特徴量ＲＥＳ（ＢＫＲ０、ＢＫＲｎ）を、前記の順方向差分特徴量ＲＥＳ（ＢＫＦ０、ＢＫＦｎ）と比較した双方向差分特徴量比較結果ＲＥＳ（ＢＫＲ０、ＢＫＲｎ）−ＲＥＳ（ＢＫＦ０、ＢＫＦｎ）に対し、下記の（２５）式で示される不等式
【０１９５】
【数２５】
2005253015.tif 000027
が成立するか否かを判断する（ステップＳ９０４）。
上記の不等式（２４）、及び不等式（２５）が、共に真である場合（ステップＳ９０３：Ｙｅｓ、かつステップＳ９０４：Ｙｅｓ）、終了判定部２３は、時間方向の内挿予測である双方向予測の効果が大きいと判断し、逆方向の半画素精度の動きベクトルＭＶ２の探索を終了し、ステップＳ９０５に進んで、探索中心Ｐ０の位置から、逆方向の動きベクトルＭＶ２Ｒを算出し、終了フラグを立てて（ステップＳ９０６）、リターンする。
【０１９６】
一方、ステップＳ９０３、またはステップＳ９０４における判断結果が否定的な場合（ステップＳ９０３：Ｎｏ、又はステップＳ９０４：Ｎｏ）、終了判定部２３は、ｎに“１”を加算（ステップＳ９０７）し、ｎの値が４よりも大きいか否かを判断（ステップＳ９０８）し、前記判断結果が否定的な場合（ステップＳ９０８：Ｎｏ）、ステップＳ９０３に戻り、次のｎの値に対して、ステップＳ９０３、及びステップＳ９０４の条件が成立するか否かの判定を行う。一方、ｎの値が４よりも大きい場合（ステップＳ９０８：Ｙｅｓ）は、探索が終了した為、そのまま呼び出し元にリターンする。
【０１９７】
このようにして、順方向動き予測の結果を用いて、逆方向動き予測を行うことで、逆方向動き予測に要するＳＡＤ演算回数を削減できる。なお、上記不等式の判定は、式（２５）のみでもよく、また、順方向動き予測と、逆方向動き予測の順序は、逆にしてもよい。
（全体のまとめ）
以上の様に、実施の形態１乃至実施の形態３に述べた動きベクトル検出装置は、半画素精度の動きベクトル検出を行う際に、背景技術の項で述べたような、処理負荷が重く、かつ画素データの冗長性の高い、半画素精度の参照ブロックを生成する事なく、半画素精度の動きベクトルＭＶ２を推定する事ができる。
【０１９８】
（その他の変形例）
なお、本発明を上記の形態に基づいて説明してきたが、本発明は、上記の実施の形態に限定されないのはもちろんである。以下のような場合も本発明に含まれる。
（１）  実施の形態では、差分評価値演算部２１のＰＥアレー３０を構成するＰＥは、８個並列に接続されていなくても良い。ＰＥアレー３０が、ｎ個（ｎ＝１、２、３、・・・）のＰＥを並列に接続して構成される場合も、本発明に含まれる。その場合には、差分評価値演算部２１のアダーツリー４０を、ｎ個の同時生成される差分絶対値が、順次加算される様に構成する。
【０１９９】
（２）  半画素精度の動きベクトルの推定精度を向上させる為の差分量子化値のビット幅は、３ビットに限らない。差分量子化値のビット幅をｎビット（ｎ＝１、２、３、・・・）とする場合は、差分特徴量レジスタ、及び差分特徴量バスの幅を、８×（ｎ＋１）ビットにすると共に、当該差分特徴量を生成、又は比較を行うＰＥ内部の量子化器、ビット結合器、及び比較器などのビット幅を、ｎビットにする。
【０２００】
（３）  探索中心Ｐ０の周囲で差分評価値の比較を行う探索パターンＳＰは、図１１に挙げたブロックサーチパターン、又はダイヤモンドサーチパターンに限らない。探索パターンＳＰを、探索中心Ｐ０の周囲の点Ｐｉ（ｉ＝１、２、３、・・・）で構成される、任意の形状の点の集合として構成する場合も、本発明に含まれる。
探索パターンＳＰが、Ｐ０、及びその周囲のｍ個（ｍは正の整数）の点、Ｐｉ（ｉ＝１、２、３、・・・、ｍ）から構成される場合には、差分特徴量比較部２２の差分特徴量レジスタのバンクの数を（ｍ＋１）個とし、Ｐ０とＰｉ（ｉ＝１、２、３、・・・、ｍ）とを左上端の点とする参照ブロックＢＫ（Ｐ０）、及びＢＫ（Ｐｉ）の差分特徴量を、対応する各バンクにそれぞれ格納した後、ｉの各値に対して、２個の参照ブロックＢＫ（Ｐ０）と、ＢＫ（Ｐｉ）（ｉ＝１、２、３、・・・、ｍ）とで前記差分特徴量の比較を行い、差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫＲｉ）を生成する処理をｍ回繰り返し、それらの結果生成された、ｍ個の差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫＲｉ）（ｉ＝１、２、３、・・・、ｍ）を、終了判定部に出力する。
【０２０１】
（４）  実施の形態１乃至実施の形態３では、差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｉ）（ｉ＝１、２、３、４）を互いに比較し、それらの中で、値が最大のものが、ＲＥＳ（ＢＫ０、ＢＫｒ）（１≦ｒ≦４）であったとすると、サーチパターンＳＰにおいて、探索中心Ｐ０と、周囲の点Ｐｒ（１≦ｒ≦４）との中点Ｐｃ＝（Ｐ０＋Ｐｒ）／２において、半画素精度の動きベクトルＭＶ２の終点が存在する可能性が最も高いと推定したが、半画素精度の動きベクトルＭＶ２の終点が存在する可能性が高いと推定する点の個数は、１個に限らない。
【０２０２】
半画素精度の動きベクトルＭＶ２の終点が存在する可能性が高いと推定する点の個数をｍ個（ｍ＝１、２、３、４）とし、差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｉ）（ｉ＝１、２、３、４）の値が大きい順に優先順位を付け、点Ｐ０と点Ｐｉとの中点（（Ｐ０＋Ｐｉ）／２）の半画素位置、又はそれに最も隣接する半画素位置（図１８（ｂ）参照）を加えた複数の半画素位置について、優先順位が高い順に、差分評価値ＳＡＤを算出して比較する事により、ＳＡＤの最小値を与える半画素位置を探索してもよい。
【０２０３】
（５）  実施の形態２では、画素データの差分符号ｓｇｎ（ｃkl−ｓkl）だけでなく、差分絶対値（｜ｃkl−ｓkl｜）をも考慮し、これを量子化の定数Ｑで除算する量子化を行った上で、差分絶対値の比が１：１であるか否かの比較を行ったが、差分絶対値を比較する比の値は、１：１に限らない。
２点Ｐ０、及びＰｉの間の点Ｐ（Ｐ０≦Ｐ≦Ｐｉ、または、Ｐｉ≦Ｐ≦Ｐ０）における画素データの値を求める為に、「線形補間」を用いて画素データを補間する場合に、異なる２つの参照ブロックＢＫ（Ｐ０）、及びＢＫ（Ｐｉ）に対する差分絶対値の比較を行って、２つの差分絶対値の比が１：１の場合以外に、１：３、３：１の場合についても差分特徴量のカウントを行い、それらのカウント値に応じて、１／４画素精度の最適参照ブロックＭＱＢＫの位置推定を行う場合も、本発明に含まれる。
【０２０４】
差分絶対値の比が１：１の場合以外に、１：３、３：１の場合についても、差分特徴量のカウントを行う場合には、ビット毎の比較を行う比較器以外に、数値としての比較が行える新たな比較器を増設する一方、前記新たな比較器の出力をカウントする為のカウンタ、及びそれらのカウンタによるカウント値を格納する為の差分特徴量比較結果レジスタを増設する。
【０２０５】
更に、当該レジスタに格納されたカウント値を使用して各種処理を行うフローチャート、またはプログラムにおいても、差分特徴量比較結果ＲＥＳ（ＢＫ０、ＢＫｎ）（ｎ＝１、２、３、４）の個数が、５個以上に増加した場合に対応できる様にする。
（６）  実施の形態２では、画素データの差分符号ｓｇｎ（ｃkl−ｓkl）だけでなく、差分絶対値（｜ｃkl−ｓkl｜）をも考慮し、これを量子化の定数Ｑで除算する量子化を行った上で、差分絶対値の比が１：１であるか否かの比較を行ったが、差分絶対値を比較する比の値は、１：１に限らない。
【０２０６】
２点Ｐ０、及びＰｉの間の点Ｐ（Ｐ０≦Ｐ≦Ｐｉ、または、Ｐｉ≦Ｐ≦Ｐ０）における画素データの値を求める為に、画素データを線形補間を含む任意の方法で補間し、異なる２つの参照ブロックＢＫ（Ｐ０）、及びＢＫ（Ｐｉ）に対する差分絶対値の比較を行って、２つの差分絶対値の比が１：１の場合以外に、ｍ：ｎ（ｍ、ｎは、任意の正の実数）の場合についても差分特徴量のカウントを行い、それらのカウント値に応じて、半画素以上の精度の最適参照ブロックの位置推定を行う場合も、本発明に含まれる。
【０２０７】
上記の比較を行う場合は、前項（５）と同様、ビット毎の比較を行う比較器以外に、数値としての比較が行える新たな比較器を増設する一方、前記新たな比較器の出力をカウントする為のカウンタ、及びそれらのカウンタによるカウント値を格納する為の差分特徴量比較結果レジスタを増設する。また、当該レジスタに格納されたカウント値を使用して各種処理を行うフローチャート、またはプログラムを各々修正し、差分特徴量比較結果のデータ量増加に対応する。
【０２０８】
（７） 上記実施の形態、及び上記変形例をそれぞれ組み合わせて実施する場合も、本発明に含まれる。
（８）  上記第１、第２の実施の形態では、動きベクトル検出装置は、特有のハードウェアを備えた構成としているが、本発明はこれに限らず、汎用パソコンを準備し、これに本発明特有の動きベクトル検出動作を行うプログラムをインストールするようにして実施することもできる。
【産業上の利用可能性】
【０２０９】
本発明の動きベクトル検出装置は、ＭＰＥＧ方式等、動画像の予測符号化処理に用いられる動きベクトル検出装置として有用である。
【図面の簡単な説明】
【０２１０】
【図１】本実施の形態の動きベクトル検出装置１を主要部とした、ＭＰＥＧ処理装置２の構成を示す機能ブロック図である。
【図２】差分評価値演算部２１の構成を示す機能ブロック図である。
【図３】図２に示した８個のＰＥ３１乃至ＰＥ３８の、内部構成を示す機能ブロック図である。
【図４】累積加算器５０の構成を示す機能ブロック図である。
【図５】差分特徴量比較部２２の構成を示す、機能ブロック図である。
【図６】差分特徴量比較結果算出処理の手順を示すフローチャートである。
【図７】差分特徴量カウント処理の処理手順を示すフローチャートである。
【図８】終了判定部２３の構成を示す機能ブロック図である。
【図９】内挿演算部２４の構成を示す機能ブロック図である。
【図１０】動きベクトル検出の概要を示す図である。
【図１１】局所探索において、差分評価値ＳＡＤの比較を行う探索パターンＳＰを示す図である。
【図１２】探索パターンＳＰとして、ダイヤモンドサーチパターン（Diamond Search Pattern；ｎｐ＝５）を用いた場合の、局所探索における探索経路ＳＲを示す図である。
【図１３】整数画素精度の動きベクトル探索の、処理手順を示すフローチャートである。
【図１４】終了判定部２３が行う、整数画素精度の動きベクトル探索の、第1終了判定処理の手順を示すフローチャートである。
【図１５】終了判定部２３が行う、整数画素精度の動きベクトル探索の、第２終了判定処理の手順を示すフローチャートである。
【図１６】半画素精度の動きベクトル探索の、処理手順を示すフローチャートである。
【図１７】差分符号が同符号の場合と、異符号（符号が反転している）の場合とを比較した図である。
【図１８】半画素精度の動きベクトルの探索処理を、例を挙げて説明した図である。
【図１９】実施の形態２のＰＥ１４１乃至１４８の構成を示す機能ブロック図である。
【図２０】実施の形態２の差分評価値演算部１３０の構成を示す機能ブロック図である。
【図２１】実施の形態２の差分特徴量比較部１３１の構成を示す、機能ブロック図である。
【図２２】実施の形態２の差分特徴量カウント処理の処理手順を示すフローチャートである。
【図２３】整数画素間で、画素データの差分符号が反転する場合に、当該整数画素間を、当該画素データの差分の絶対値に応じて、内分する点を示す図である。
【図２４】双方向動き予測の概要を説明する為の図である。
【図２５】整数画素精度の双方向動き予測の処理手順を示すフローチャートである。
【図２６】逆方向動き予測において用いる、整数画素精度の動きベクトル探索の、第２終了判定処理の手順を示すフローチャートである。
【図２７】半画素精度の動きベクトルＭＶ２の検出における、画素データの補間処理の概要を示す図である。
【図２８】半画素精度の動きベクトル検出における探索位置を示す図である。
【図２９】生成された８個の半画素精度の参照ブロックＨＢＫ１乃至ＨＢＫ８の位置関係、及び重なり状態を示す図である。
【符号の説明】
【０２１１】
１              動きベクトル検出装置
２              ＭＰＥＧ処理装置
３              ＣＰＵ
４              ＲＯＭ
５              ＲＡＭ
６              フレームメモリ
７              グローバルバス
８              現フレームメモリ
９              参照フレームメモリ
１１            カレントブロックメモリ
１２            参照領域メモリ
１３            アドレス生成部
１４            制御部
１５            データパス部
２１            差分評価値演算部
２２            差分特徴量比較部
２３            終了判定部
２４            内挿演算部
３０            ＰＥアレー
３１            ＰＥ（０）
３２            ＰＥ（１）
３３            ＰＥ（２）
３４            ＰＥ（３）
３５            ＰＥ（４）
３６            ＰＥ（５）
３７            ＰＥ（６）
３８            ＰＥ（７）
４０            アダーツリー
４１〜４７      加算器
５０            累積加算器
５１            加算器
５２            累積レジスタ
５５            差分特徴量バス
６１            引算器
６２            絶対値化器
６３            レジスタ
６４            符号化器
７０            差分特徴量レジスタ（バンク０）
７１            差分特徴量レジスタ（バンク１）
７２            差分特徴量レジスタ（バンク２）
７３            差分特徴量レジスタ（バンク３）
７４            差分特徴量レジスタ（バンク４）
７５〜７６     分岐器
７７            比較器
７８            カウンタ
８０            第１終了判定部
８１            第２終了判定部
８２            分岐器
８３            ＯＲ回路
９０            ＳＡＤレジスタ
９１            ＭＩＮＳＡＤレジスタ
９２            比較器
９３            第１判定部
９５            差分特徴量比較結果レジスタ
９６            ＳＡＤ０レジスタ
９７            第２判定部
１００          半画素ブロックメモリ
１０１          補間部
１０５          符号化画像Ｉt
１０６          参照画像Ｉt-1
１１０          量子化器
１１１          ビット結合器
１２１            ＰＥ（０）
１２２            ＰＥ（１）
１２３            ＰＥ（２）
１２４            ＰＥ（３）
１２５            ＰＥ（４）
１２６            ＰＥ（５）
１２７            ＰＥ（６）
１２８            ＰＥ（７）
１３０            差分評価値演算部
１３１            差分評価値比較部
１３５            差分特徴量バス（３２ビット）
１４０            差分特徴量レジスタ（バンク０）
１４１            差分特徴量レジスタ（バンク１）
１４２            差分特徴量レジスタ（バンク２）
１４３            差分特徴量レジスタ（バンク３）
１４４            差分特徴量レジスタ（バンク４）
１４５〜１４６   分岐器
１４７            比較器
１４８            カウンタ
１５０            Ｉピクチャ
１５１            Ｐピクチャ
１５２            Ｂピクチャ
【図１】
2005253015.tif 000028
【図２】
2005253015.tif 000029
【図３】
2005253015.tif 000030
【図４】
2005253015.tif 000031
【図５】
2005253015.tif 000032
【図６】
2005253015.tif 000033
【図７】
2005253015.tif 000034
【図８】
2005253015.tif 000035
【図９】
2005253015.tif 000036
【図１０】
2005253015.tif 000037
【図１１】
2005253015.tif 000038
【図１２】
2005253015.tif 000039
【図１３】
2005253015.tif 000040
【図１４】
2005253015.tif 000041
【図１５】
2005253015.tif 000042
【図１６】
2005253015.tif 000043
【図１７】
2005253015.tif 000044
【図１８】
2005253015.tif 000045
【図１９】
2005253015.tif 000046
【図２０】
2005253015.tif 000047
【図２１】
2005253015.tif 000048
【図２２】
2005253015.tif 000049
【図２３】
2005253015.tif 000050
【図２４】
2005253015.tif 000051
【図２５】
2005253015.tif 000052
【図２６】
2005253015.tif 000053
【図２７】
2005253015.tif 000054
【図２８】
2005253015.tif 000055
【図２９】
2005253015.tif 000056