(57)【特許請求の範囲】
【請求項１】
動画像に含まれる各フレーム画像が処理単位にて分割されたマクロブロック毎に検出された複数の動きベクトルを統計処理する統計処理部と、
第１フレーム画像と時間的に異なる参照フレーム画像に第１探索範囲を設定し、前記統計処理部の処理結果に基づいて前記第１探索範囲内に探索開始位置を設定し、前記統計処理部の処理結果に基づいて前記第１探索範囲内における探索方向を設定し、前記探索方向にしたがって前記探索開始位置より前記第１探索範囲内を探索し、前記第１フレーム画像に含まれる対象マクロブロックの動きベクトルを生成する動き探索部と、を有し、
前記動き探索部は、前記探索開始位置に候補ブロックを設定し、前記候補ブロックを前記探索方向にしたがって順次設定し、各設定位置における前記候補ブロックの評価値を算出し、前記評価値と判定しきい値とを比較し、比較結果に基づいて前記対象マクロブロックに対する動き探索処理を打ち切り、
前記動き探索部は、前の対象マクロブロックに対する動き探索処理の打ち切りがあったとき、前記対象マクロブロックに対する前記第１探索範囲の外側に第２探索範囲を設定すること、を特徴とする符号化回路。
【請求項２】
動画像に含まれる各フレーム画像が処理単位にて分割されたマクロブロック毎に検出された複数の動きベクトルを統計処理する統計処理部と、
第１フレーム画像と時間的に異なる参照フレーム画像に第１探索範囲を設定し、前記統計処理部の処理結果に基づいて前記第１探索範囲内に探索開始位置を設定し、前記統計処理部の処理結果に基づいて前記第１探索範囲内における探索方向を設定し、前記探索方向にしたがって前記探索開始位置より前記第１探索範囲内を探索し、前記第１フレーム画像に含まれる対象マクロブロックの動きベクトルを生成する動き探索部と、を有し、
前記動き探索部は、前記探索開始位置に候補ブロックを設定し、前記候補ブロックを前記探索方向にしたがって順次設定し、各設定位置における前記候補ブロックの評価値を算出し、前記評価値と判定しきい値とを比較し、比較結果に基づいて前記対象マクロブロックに対する動き探索処理を打ち切り、
前記動き探索部は、前の対象マクロブロックに対する動き探索処理の打ち切りがあったとき、前記対象マクロブロックに対する動き探索処理の処理時間を変更し、前記処理時間に基づいて前記判定しきい値を段階的に調整すること、を特徴とする符号化回路。
【請求項３】
動画像に含まれる各フレーム画像が処理単位にて分割されたマクロブロック毎に検出された複数の動きベクトルを統計処理する統計処理部と、
第１フレーム画像と時間的に異なる参照フレーム画像に第１探索範囲を設定し、前記統計処理部の処理結果に基づいて前記第１探索範囲内に探索開始位置を設定し、前記統計処理部の処理結果に基づいて前記第１探索範囲内における探索方向を設定し、前記探索方向にしたがって前記探索開始位置より前記第１探索範囲内を探索し、前記第１フレーム画像に含まれる対象マクロブロックの動きベクトルを生成する動き探索部と、を有し、
前記統計処理部は、前記第１フレーム画像に含まれる複数のマクロブロックの動きベクトルに基づく第１の統計動きベクトルと、前記第１フレーム画像より時間的に後方の第２フレーム画像に含まれる複数のマクロブロックの動きベクトルに基づく第２の統計動きベクトルと、を生成し、
前記動き探索部は、前記第１の統計動きベクトルと前記第２の統計動きベクトルとに基づいて前記探索開始位置と前記探索方向とを設定し、
前記動き探索部は、前記探索開始位置に候補ブロックを設定し、前記候補ブロックを前記探索方向にしたがって順次設定し、各設定位置における前記候補ブロックの評価値を算出し、前記評価値と判定しきい値とを比較し、比較結果に基づいて前記対象マクロブロックに対する動き探索処理を打ち切り、
前記動き探索部は、前の対象マクロブロックに対する動き探索処理の打ち切りがあったとき、前記対象マクロブロックに対する前記第１探索範囲の外側に、前記第１の統計動きベクトルの方向と前記第２の統計動きベクトルの方向とに基づいて、第２探索範囲を設定すること、を特徴とする符号化回路。
【請求項４】
前記統計処理部は、
前記第１フレーム画像に含まれる複数のマクロブロックの動きベクトルに基づく第１の統計動きベクトルと、前記第１フレーム画像より時間的に後方の第２フレーム画像に含まれる複数のマクロブロックの動きベクトルに基づく第２の統計動きベクトルと、を生成し、
前記動き探索部は、
前記第１の統計動きベクトルと前記第２の統計動きベクトルとに基づいて前記探索開始位置と前記探索方向とを設定すること、を特徴とする請求項１または２に記載の符号化回路。
【請求項５】
前記統計処理部は、
前記第１フレーム画像に含まれ前記対象マクロブロックに隣接する複数のマクロブロックにおいて、前記第１フレーム画像より時間的に前方の前記参照フレーム画像を参照する動きベクトルに基づいて前記第１の統計動きベクトルを生成し、
前記第２フレーム画像に含まれ前記対象マクロブロックと空間的に同一位置の参照マクロブロックと、前記参照マクロブロックに隣接する複数のマクロブロックとにおいて、前記参照フレーム画像を参照する動きベクトルとに基づいて前記第２の統計動きベクトルを生成すること、を特徴とする請求項３または４に記載の符号化回路。
【請求項６】
前記動き探索部は、
前記第１の統計動きベクトルの方向と前記第２の統計動きベクトルの方向とに基づいて、前記探索開始位置と前記探索方向を設定すること、を特徴とする請求項３〜５のいずれか一項に記載の符号化回路。
【請求項７】
前記動き探索部は、
前記第１探索範囲に対して、前記統計処理部の処理結果に基づく方向に前記第２探索範囲を設定すること、を特徴とする請求項１に記載の符号化回路。
【請求項８】
前記動き探索部は、
前記動き探索処理の打ち切りのタイミングに基づいて前記第２探索範囲の大きさを設定すること、を特徴とする請求項１または７に記載の符号化回路。
【請求項９】
前記マクロブロック毎に縮小画像を生成する縮小部と、
前記縮小部により参照フレームを縮小した縮小画像に設定した第３探索範囲を探索して縮小動きベクトルを検出する縮小動き探索部と、を有し、
前記動き探索部は、前記縮小動きベクトルに基づいて前記第１探索範囲の位置を設定すること、を特徴とする請求項１〜８のいずれか一項に記載の符号化回路。
【請求項１０】
動画像に含まれる各フレーム画像が処理単位にて分割されたマクロブロック毎に検出された複数の動きベクトルを統計処理し、
第１フレーム画像と時間的に異なる参照フレーム画像に第１探索範囲を設定し、
前記統計処理の処理結果に基づいて前記第１探索範囲内に探索開始位置を設定し、
前記統計処理の処理結果に基づいて設定した探索方向にしたがって前記第１探索範囲内を探索し、
前記第１フレーム画像に含まれる対象マクロブロックの動きベクトルを生成し、
前記探索開始位置に候補ブロックを設定し、前記候補ブロックを前記探索方向にしたがって順次設定し、各設定位置における前記候補ブロックの評価値を算出し、前記評価値と判定しきい値とを比較し、比較結果に基づいて前記対象マクロブロックに対する動き探索処理を打ち切り、
前の対象マクロブロックに対する動き探索処理の打ち切りがあったとき、前記対象マクロブロックに対する前記第１探索範囲の外側に第２探索範囲を設定すること、を特徴とする符号化方法。
【請求項１１】
動画像に含まれる各フレーム画像が処理単位にて分割されたマクロブロック毎に検出された複数の動きベクトルを統計処理し、
第１フレーム画像と時間的に異なる参照フレーム画像に第１探索範囲を設定し、
前記統計処理の処理結果に基づいて前記第１探索範囲内に探索開始位置を設定し、
前記統計処理の処理結果に基づいて設定した探索方向にしたがって前記第１探索範囲内を探索し、
前記第１フレーム画像に含まれる対象マクロブロックの動きベクトルを生成し、
前記探索開始位置に候補ブロックを設定し、前記候補ブロックを前記探索方向にしたがって順次設定し、各設定位置における前記候補ブロックの評価値を算出し、前記評価値と判定しきい値とを比較し、比較結果に基づいて前記対象マクロブロックに対する動き探索処理を打ち切り、
前の対象マクロブロックに対する動き探索処理の打ち切りがあったとき、前記対象マクロブロックに対する動き探索処理の処理時間を変更し、前記処理時間に基づいて前記判定しきい値を段階的に調整すること、を特徴とする符号化方法。
【請求項１２】
動画像に含まれる各フレーム画像が処理単位にて分割されたマクロブロック毎に検出された複数の動きベクトルを統計処理し、
第１フレーム画像と時間的に異なる参照フレーム画像に第１探索範囲を設定し、
前記統計処理の処理結果に基づいて前記第１探索範囲内に探索開始位置を設定し、
前記統計処理の処理結果に基づいて設定した探索方向にしたがって前記第１探索範囲内を探索し、
前記第１フレーム画像に含まれる対象マクロブロックの動きベクトルを生成し、
前記第１フレーム画像に含まれる複数のマクロブロックの動きベクトルに基づく第１の統計動きベクトルと、前記第１フレーム画像より時間的に後方の第２フレーム画像に含まれる複数のマクロブロックの動きベクトルに基づく第２の統計動きベクトルと、を生成し、
前記第１の統計動きベクトルと前記第２の統計動きベクトルとに基づいて前記探索開始位置と前記探索方向とを設定し、
前記探索開始位置に候補ブロックを設定し、前記候補ブロックを前記探索方向にしたがって順次設定し、各設定位置における前記候補ブロックの評価値を算出し、前記評価値と判定しきい値とを比較し、比較結果に基づいて前記対象マクロブロックに対する動き探索処理を打ち切り、
前の対象マクロブロックに対する動き探索処理の打ち切りがあったとき、前記対象マクロブロックに対する前記第１探索範囲の外側に、前記第１の統計動きベクトルの方向と前記第２の統計動きベクトルの方向とに基づいて、第２探索範囲を設定すること、を特徴とする符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
符号化回路、符号化方法に関する。
【背景技術】
【０００２】
従来、ＭＰＥＧ（Moving Picture Experts Group）やＨ．２６４等は、動画像の圧縮符号化の規格として知られている。これらの圧縮符号化を行う画像処理装置では、画面内予測（イントラ予測）や画面間予測（インター予測）を行う。画面間予測では、動き探索処理を行い、符号化対象の画面（現処理画像とよぶ）を分割したマクロブロック（ＭＢ）の動きベクトルを検出する。動き探索処理は、処理対象のマクロブロックと類似したブロックを、現処理画像と時間的に前後関係にある参照画像に設定した探索範囲の中から探し出す処理である。動き探索処理において、原処理画像に対して時間的に異なる画像における動きベクトルを用いて探索範囲を設定することがある（たとえば、特許文献１，２参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０００−３０８０６２号公報
【特許文献２】特開２００２−３３５５２９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、動画像を符号化する符号化回路において、符号化（画面間予測による符号化）の効率向上が求められる。
【課題を解決するための手段】
【０００５】
本発明の一観点によれば、動画像に含まれる各フレーム画像が処理単位にて分割されたマクロブロック毎に検出された複数の動きベクトルを統計処理する統計処理部と、第１フレーム画像と時間的に異なる参照フレーム画像に第１探索範囲を設定し、前記統計処理部の処理結果に基づいて前記第１探索範囲内に探索開始位置を設定し、前記統計処理部の処理結果に基づいて設定した探索方向にしたがって前記第１探索範囲内を探索し、前記第１フレーム画像に含まれる対象マクロブロックの動きベクトルを生成する動き探索部とを有し、前記動き探索部は、前記探索開始位置に候補ブロックを設定し、前記候補ブロックを前記探索方向にしたがって順次設定し、各設定位置における前記候補ブロックの評価値を算出し、前記評価値と判定しきい値とを比較し、比較結果に基づいて前記対象マクロブロックに対する動き探索処理を打ち切り、前記動き探索部は、前の対象マクロブロックに対する動き探索処理の打ち切りがあったとき、前記対象マクロブロックに対する前記第１探索範囲の外側に第２探索範囲を設定する。
【発明の効果】
【０００６】
本発明の一観点によれば、符号化効率を向上することができる。
【図面の簡単な説明】
【０００７】
【図１】符号化回路の概略構成図である。
【図２】動きベクトル検出部のブロック図である。
【図３】符号化するピクチャの説明図である。
【図４】ピクチャ間における前方参照の説明図である。
【図５】ピクチャ間における前方参照及び後方参照の説明図である。
【図６】マクロブロックの処理順序と動きベクトル予測値等の算出の説明図である。
【図７】（ａ），（ｂ）は現処理画像の動きベクトル探索を示す説明図である。
【図８】（ａ），（ｂ）は縮小画像の動きベクトル探索を示す説明図である。
【図９】（ａ），（ｂ）は縮小画像の動きベクトル探索を示す説明図である。
【図１０】（ａ），（ｂ）は現処理画像の動きベクトル探索を示す説明図である。
【図１１】（ａ）〜（ｆ）は動き探索における全探索の説明図である。
【図１２】現処理画像と探索範囲、探索結果を示す説明図である。
【図１３】本実施形態の処理を示すフローチャートである。
【図１４】比較例の処理を示すフローチャートである。
【図１５】統計処理に用いるマクロブロックを示す説明図である。
【図１６】（ａ）〜（ｅ）は、探索開始位置と探索方向の［ケース１］を示す説明図である。
【図１７】（ａ）〜（ｅ）は、探索開始位置と探索方向の［ケース２］を示す説明図である。
【図１８】（ａ）〜（ｅ）は、探索開始位置と探索方向の［ケース３］を示す説明図である。
【図１９】（ａ）〜（ｅ）は、探索開始位置と探索方向の［ケース４］を示す説明図である。
【図２０】（ａ）〜（ｅ）は、探索開始位置と探索方向の［ケース１０］を示す説明図である。
【図２１】（ａ）〜（ｅ）は、探索開始位置と探索方向の［ケース１１］を示す説明図である。
【図２２】（ａ）〜（ｅ）は、探索開始位置と探索方向の［ケース１２］を示す説明図である。
【図２３】（ａ）〜（ｅ）は、探索開始位置と探索方向の［ケース１３］を示す説明図である。
【図２４】（ａ）（ｂ）は、探索開始位置と探索方向の［ケース１４］を示す説明図である。
【図２５】探索開始位置と探索方向のケースを選択する処理を示すフローチャートである。
【図２６】探索開始位置と探索方向のケースを選択する処理を示すフローチャートである。
【図２７】（ａ）〜（ｃ）は［ケース１］による全探索の説明図である。
【図２８】（ａ）〜（ｃ）は［ケース１］による全探索の説明図である。
【図２９】（ａ）〜（ｃ）は［ケース１］による全探索の説明図である。
【図３０】動き探索処理の打ち切りと探索期間の説明図である。
【図３１】動き探索処理の打ち切りと探索期間の説明図である。
【図３２】動き探索処理の打ち切りと探索期間の説明図である。
【図３３】打ち切り処理のケースの選択を示すフローチャートである。
【図３４】打ち切り処理のケースの選択を示すフローチャートである。
【図３５】（ａ）は探索範囲の拡張を示す説明図、（ｂ）は探索方向の説明図である。
【図３６】（ａ）〜（ｄ）は、探索範囲の拡張の各ケースを示す説明図である。
【図３７】（ａ）〜（ｅ）は、探索範囲の拡張の各ケースを示す説明図である。
【図３８】（ａ）〜（ｄ）は、探索範囲の拡張の各ケースを示す説明図である。
【図３９】（ａ）〜（ｅ）は、探索範囲の拡張の各ケースを示す説明図である。
【図４０】探索範囲の拡張のケースを選択する処理を示すフローチャートである。
【図４１】探索範囲の拡張のケースを選択する処理を示すフローチャートである。
【図４２】探索範囲の拡張のケースを選択する処理を示すフローチャートである。
【図４３】探索範囲の拡張のケースを選択する処理を示すフローチャートである。
【発明を実施するための形態】
【０００８】
以下、一実施形態を説明する。
先ず、符号化回路の概略を説明する。
図１に示す符号化回路１０は、たとえばＭＰＥＧ２の規格にしたがって、入力画像１１を符号化した符号化信号１２を生成する。
【０００９】
マクロブロック分割部（ＭＢ分割部）２１は、入力画像１１を処理単位で分割した画像（マクロブロック（ＭＢ））を、減算器２２と動きベクトル検出部３２に出力する。
減算器２２は、マクロブックと、予測モード選択部３４から出力される予測画像との差分値を算出し、その差分値を出力する。直交変換量子化部２３は、上記差分値を直交変換した後に、量子化を行い、量子化したデータを出力する。直交変換は、たとえば離散コサイン変換（DCT:Discrete Cosine Transform）である。エントロピー符号化部２４は、直交変換量子化部２３により量子化されたデータを可変長符号化変換し、符号化信号１２を出力する。
【００１０】
逆量子化逆直交変換部２５は、直交変換量子化部２３により量子化されたデータを逆量子化した後、逆直交変換を行い、処理後のデータを出力する。逆直交変換は、たとえば逆離散コサイン変換（IDCT:Inverse DCT）である。加算器２６は、逆量子化逆直交変換部２５の出力データに、予測モード選択部３４から出力される予測画像を加算して参照画像を生成する。この参照画像は、現フレームバッファ２７に保持される。
【００１１】
フレーム内予測部２８は、現フレームバッファ２７に保持された参照画像を入力し、隣接ブロックからの画素レベルに基づいて、参照画像のフレーム内予測を行う。デブロッキングフィルタ２９は、現フレームバッファ２７に保持された参照画像を入力し、隣接する２つのマクロブロックの境界を平滑化して出力する。これにより、デブロッキングフィルタ２９は、画像を符号化した際に生じるブロック歪を減少させる。フレームバッファ管理部３０は、デブロッキングフィルタ２９の出力データをフレームバッファ３１に出力し、フレームバッファ３１はその出力データを記憶する。
【００１２】
動きベクトル検出部３２は、ＭＢ分割部２１から入力されたマクロブロック（ＭＢ）と、過去のフレームバッファ３１に格納された参照画像とを用いて、対象マクロブロックの動きベクトル（MV:Motion Vector）を検出する。動きベクトル（ＭＶ）は、通常、周辺領域との相関が高い。フレーム間予測部３３は、周辺領域の動きベクトル（ＭＶ）に基づいて動きベクトル予測値（MVP:Motion Vector Predictor）を算出する。さらに、フレーム間予測部３３は、対象マクロブロックの動きベクトル（ＭＶ）と動きベクトル予測値（ＭＶＰ）との間の予測差分値（MVD:Motion Vector Difference）を算出する。上記のエントロピー符号化部２４は、この予測差分値（ＭＶＤ）を含む符号化信号１２を出力する。復号化装置（図示略）において、予測差分値（ＭＶＤ）により動きベクトル（ＭＶ）を算出し、復号化した出力画像を生成する。
【００１３】
予測モード選択部３４は、フレーム間予測部３３とフレーム内予測部２８の予測誤差を比較し、当該マクロブロックを最も効率よく符号化することができる符号化モードを選択し、符号化モード情報を生成する。この符号化モード情報は、符号化対象情報として、エントロピー符号化部２４へ受け渡される。符号化モード情報には、マクロブロックを分割した分割マクロブロックのサイズと、分割マクロブロックをさらに分割したサブマクロブロックのサイズが含まれる。
【００１４】
図２に示すように、動きベクトル検出部３２は、縮小部４１、動き探索部４２、統計処理部４３、動き探索部４４を有している。
縮小部４１は、マクロブロック（ＭＢ）を所定の縮小率で縮小した縮小マクロブロック（ＳＭＢ）を生成する。縮小率は、たとえば水平方向と垂直方向にそれぞれ２分の１（１／２）である。縮小部４１は、たとえば、マクロブロック（ＭＢ）の画素を、画素の配列方向（縦方向及び横方向）に沿って１画素おきに間引いて縮小マクロブロックＳＭＢを生成する。縮小部４１は、生成した縮小マクロブロックＳＭＢをメモリ５０の縮小フレームバッファ５１に格納する。
【００１５】
縮小部４１は、フレーム画像を処理単位に分割したマクロブロック（ＭＢ）を順次縮小処理し、縮小マクロブロックＳＭＢを縮小フレームバッファ５１に格納する。したがって、縮小フレームバッファ５１には、各フレーム画像の縮小画像が格納される。つまり、原処理画像において、対象マクロブロックＣｕの縮小マクロブロックと、対象マクロブロックＣｕよりも過去に処理されたマクロブロック（ＭＢ）の縮小マクロブロックとが格納される。また、縮小フレームバッファ５１には、原処理画像と異なる時間に撮影され、原処理画像よりも前（過去）に処理された参照フレームの縮小画像が格納される。参照フレームは、原処理画像よりも前（過去）に撮影された前方参照フレームと、原処理画像よりも後（未来）に撮影された後方参照フレームを含む。
【００１６】
メモリ５０には記憶領域として、上記の縮小フレームバッファ５１と、対象マクロブロックバッファ５２と、動きベクトルバッファ５３が設定される。また、メモリ５０には、図１に示す現フレームバッファ２７、過去のフレームバッファ３１等の記憶領域が設定される。メモリ５０は、たとえばＳＤＲＡＭ（Synchronous Dynamic Random Access Memory）等のメモリモジュールとすることができる。このようなメモリモジュールは、たとえば、符号化回路１０の各機能部を含む半導体装置（ＬＳＩ）に接続される。
【００１７】
動き探索部４２は、対象マクロブロックに対応する縮小マクロブロックをメモリ５０の縮小フレームバッファ５１から読み出す。また、動き探索部４２は、参照画像を縮小した縮小参照画像を縮小フレームバッファ５１から読み出す。そして、動き探索部４２は、縮小マクロブロックを用いて縮小参照画像を探索し、縮小マクロブロックの動きベクトルＳＭＶを検出する。そして、動き探索部４２は、動きベクトルＳＭＶを動き探索部４４に出力する。
【００１８】
たとえば、動き探索部４２は、設定した探索範囲において、縮小マクロブロックＳＭＢと同じ範囲に含まれる画素を候補ブロックとする。動き探索部４２は、縮小マクロブロックＳＭＢに含まれる各画素の値と候補ブロックに含まれる各画素の値を比較し、評価値を算出する。評価値は、たとえば差分絶対値和（SAD:Sum of Absolute Difference）である。差分絶対値和は、対応する画素の値の差の絶対値の合計値である。なお、評価値として、ＳＡＴＤ（Sum of Absolute Transformed Difference）、差分二乗和（SSD:Sum of Squared Difference）、等を用いてもよい。
【００１９】
そして、動き探索部４２は、評価値に基づいて、対象の縮小マクロブロックＳＭＢに対応する候補ブロックを検出する。たとえば、動き探索部４２は、評価値が最小の候補ブロックを検出する。そして、動き探索部４２は、参照画像において、対象マクロブロックと空間的に同一位置にあるマクロブロック（仮想マクロブロック）から、検出した候補ブロックまでの移動量を算出する。動き探索部４２は、検出した候補ブロックの位置と、仮想マクロブロックの位置とに基づいて、移動量を算出する。この移動量は、縮小画像における対象マクロブロックの動きベクトルＳＭＶである。動きベクトルＳＭＶは、対象マクロブロックＣｕに対する候補ブロックの相対的な位置関係（ずれ量およびずれ方向）を示すデータ（情報）である。
【００２０】
統計処理部４３は、過去の動き探索処理によって検出した動きベクトル（ＭＶ）に基づいて、動き探索部４４における探索設定情報を生成する。探索設定情報は、たとえば、過去の動きベクトル（ＭＶ）を統計処理した統計動きベクトルである。
【００２１】
たとえば、統計処理部４３は、現処理画像において、処理対象のマクロブロック（ＭＢ）に隣接するマクロブロックの動きベクトルを動きベクトルバッファ５３から読み出す。そして、統計処理部４３は、読み出した動きベクトルを統計処理し、探索設定情報を生成する。統計処理は、たとえば平均値を算出する処理である。たとえば、統計処理部４３は、現処理画像で既に生成した動きベクトルの平均値を算出し、この平均値を第１の統計動きベクトルＭＶＳとする。
【００２２】
また、統計処理部４３は、現処理画像に対して後方の参照画像がある場合、その参照画像の動きベクトルを動きベクトルバッファ５３から読み出す。たとえば、統計処理部４３は、参照画像において、上記処理対象のマクロブロック（ＭＢ）と同じ位置にあるマクロブロック（以下、参照マクロブロック）の動きベクトルと、その参照マクロブロックの周辺領域のマクロブロックの動きベクトルを、動きベクトルバッファ５３から読み出す。そして、統計処理部４３は、参照画像の動きベクトルを統計処理し、探索設定情報を生成する。統計処理は、たとえば平均値を算出する処理である。たとえば、統計処理部４３は、後方参照画像の動きベクトルの平均値を算出し、この平均値を第２の統計動きベクトルＭＶＲとする。
【００２３】
動き探索部４４は、参照画像に対する探索範囲の探索条件を設定する。そして、動き探索部４４は、設定した探索条件にしたがって探索範囲を探索し、対象マクロブロックＣｕの動きベクトル（ＭＶ）を生成する。
【００２４】
探索条件は、探索開始位置と探索方向（探索順序，探索経路）を含む。
動き探索部４４は、統計処理部４３により生成した第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲに基づいて、探索範囲における探索開始位置と探索方向を設定する。探索開始位置は、探索範囲内において候補ブロックを最初に設定する位置である。探索方向は、候補ブロックの位置を設定する順序を示す情報である。
【００２５】
たとえば、動き探索部４４は、原寸サイズの参照画像において、対象マクロブロックと空間的に同一位置のマクロブロック（仮想マクロブロック）を中心とし、その仮想マクロブロックの周辺の８個のマクロブロックを含む探索範囲を設定する。そして、動き探索部４４は、第１の統計動きベクトルＭＶＳの方向と第２の統計動きベクトルＭＶＲの方向とに基づいて、探索開始位置と探索方向とを設定する。たとえば、動き探索部４４は、第１の統計動きベクトルＭＶＳの縦方向の成分と横方向の成分との比に基づいて、第１の統計動きベクトルＭＶＳの方向を、上下左右の８つの方向のいずれに該当するかを判定する。同様に、動き探索部４４は、第２の統計動きベクトルＭＶＲの縦方向の成分と横方向の成分との比に基づいて、第２の統計動きベクトルＭＶＲの方向を、上下左右の８つの方向のいずれに該当するかを判定する。そして、動き探索部４４は、判定した第１の統計動きベクトルＭＶＳの方向と第２の統計動きベクトルＭＶＲの方向とに基づいて、探索開始位置と探索方向とを設定する。
【００２６】
動き探索部４４は、参照画像に設定した探索範囲において、現処理画像の対象マクロブロックＣｕの大きさ（画素数）に応じた候補ブロックを順次設定する。そして、動き探索部４４は、各候補ブロックの評価値を算出する。評価値は、たとえば差分絶対値和（ＳＡＤ）である。なお、評価値として、差分二乗和（ＳＳＤ）、ＳＡＴＤ等を用いてもよい。
【００２７】
動き探索部４４は、基準しきい値αと、その基準しきい値αに基づいて設定する判定しきい値Ｇｊとをたとえばレジスタ４４ａに記憶している。動き探索部４４は、各候補ブロックについて算出した評価値と、判定しきい値Ｇｊとを比較する。そして、動き探索部４４は、判定しきい値Ｇｊより評価値が小さい場合、対象マクロブロックＣｕに対する動きベクトル探索処理を打ち切る。そして、動き探索部４４は、処理を打ち切ったときのサイクル数をたとえばレジスタ４４ａに記憶する。
【００２８】
サイクル数は、１つのマクロブロックについて動きベクトル（ＭＶ）の探索に要する時間である。たとえば、対象マクロブロックＣｕと１つの候補ブロックとの評価値の算出に要するサイクルを「１」とする。探索範囲の大きさをたとえば４８画素×４８画素とする。対象マクロブロックＣｕと候補ブロックの大きさをたとえば１６画素×１６画素とすると、縦方向と横方向にそれぞれ３３個（＝４８−１６＋１）の候補ブロックの設定が可能である。したがって、１つの探索範囲における動き探索処理のサイクル数は、１０８９（＝３３×３３）となる。
【００２９】
現処理画像において、対象マクロブロックＣｕの動きベクトル（ＭＶ）と、対象マクロブロックＣｕの周辺のマクロブロック（ＭＢ）の動きベクトル（ＭＶ）は、高い相関を示すことが多い。同様に、後方参照画像がある場合、その後方参照画像において、対象マクロブロックＣｕと空間的に同じ位置のマクロブロック（参照マクロブロックＣ１）を含む領域（参照領域）における動きベクトル（ＭＶ）は、対象マクロブロックＣｕの動きベクトル（ＭＶ）と高い相関を示すことが多い。つまり、周辺のマクロブロックや後方参照画像のマクロブロックの動きベクトルが示す方向に、対象マクロブロックＣｕと等しいまたは類似したブロックが存在することが多い。したがって、過去の処理において算出した動きベクトル（ＭＶ）に基づいて探索開始位置と探索方向を設定することで、探索開始から類似した候補ブロックを検出するまでに要する時間が短くなる。
【００３０】
そして、動き探索部４４は、上記の判定しきい値Ｇｊに基づいて、類似した候補ブロックを検出したときに、その探索範囲に対する動き探索処理を打ち切る。そして、動き探索部４４は、類似した候補ブロックの位置に基づいて、対象マクロブロックＣｕの動きベクトル（ＭＶ）を生成する。これにより、対象マクロブロックＣｕに対する動きベクトル（ＭＶ）の生成に要する時間が短くなり、探索処理の効率が向上する。
【００３１】
また、探索条件は、探索範囲の大きさ（サイズ，画素数）と探索範囲を拡張する方向を含む。
上記したように、動き探索部４４は、判定しきい値Ｇｊに基づいて、対象マクロブロックＣｕに対する動き探索処理を打ち切る。この場合、残りの処理期間を、次に処理するマクロブロック（ＭＢ）の処理期間として利用することができる。つまり、次に処理するマクロブロック（ＭＢ）における処理期間を長くすることができる。そして、１サイクルにおいて、１つの候補ブロックに対する評価値の算出を行う。したがって、処理期間は、評価値を算出する候補ブロックの数に対応する。つまり、上記の残りの処理期間に応じて、探索する領域を拡大することができる。
【００３２】
たとえば、上記した４８画素×４８画素の探索範囲を基準探索範囲とする。この基準探索範囲の外側において探索する領域を拡張探索範囲とする。動き探索部４４は、拡張探索範囲の大きさ（画素数）を、打ち切りのタイミング、つまりレジスタ４４ａに記憶したサイクル数に基づいて設定する。
【００３３】
動き探索部４４は、設定した探索範囲（基準探索範囲、拡張探索範囲）について、範囲に応じた期間を探索期間とする。そして、動き探索部４４は、探索期間を、複数の期間に分割し、各期間に対して、判定しきい値Ｇｊを調整する。たとえば、動き探索部４４は、分割した各期間について、判定しきい値Ｇｊを、期間の分割数に応じた値から基準しきい値αまで段階的に増加させる。
【００３４】
動き探索部４４は、基準探索範囲の探索に要する期間（基準探索期間）を所定数にて等分割したサイクル数を単位とし、探索期間を複数の期間に分割する。複数の期間のうち、最終の期間を除く期間において、設定した判定しきい値Ｇｊに基づいて探索処理の打ち切りを判定する。そして、設定した期間のうち、最終の期間では、最後の候補ブロックまで探索処理を行う。このように、対象マクロブロックＣｕに対する探索の開始時点では、より小さな判定しきい値Ｇｊにより候補ブロックの評価値を判定することで、精度の高い検出が可能となる。
【００３５】
また、動き探索部４４は、拡張探索範囲の設定位置を、上記の統計情報（第１の統計動きベクトルＭＶＳ，第２の統計動きベクトルＭＶＲ）に基づいて設定する。過去に処理したマクロブロックの動きベクトルに基づいて、拡張探索範囲を設定することで、対象マクロブロックＣｕの動きベクトルに応じた探索範囲を参照画像に対して設定することができる。したがって、対象マクロブロックＣｕの動きベクトルＭＶを効率よく検出することができる。また、動きベクトルＭＶを精度よく検出することができる。
【００３６】
また、探索条件は、探索範囲の位置（オフセット）を含む。
動き探索部４４は、動き探索の処理単位となるマクロブロック毎に、動き探索部４２から入力された動きベクトルＳＭＶに基づいて探索範囲の位置（オフセット）を設定する。ただし、動きベクトルＳＭＶは、縮小画像により探索された動きベクトルであるため、縮小率に応じて拡大した値（大きさ）で用いる。たとえば、上記の縮小部４１は、水平方向及び垂直方向の画素数をそれぞれ１／２にした縮小画像を生成し、動き探索部４２はその縮小画像を用いて動き探索処理を行う。したがって、動き探索部４４は、動きベクトルＳＭＶが示す水平方向及び垂直方向の値を２倍して用いる。
【００３７】
動き探索部４４は、参照画像として、過去のフレームバッファ３１に格納された復号画像を部分的に用いる。
動き探索部４４は、参照画像において、対象マクロブロックと等しい位置の参照マクロブロックの基準点（たとえば、マクロブロックの中心位置）から、動きベクトルＳＭＶに応じてずれた位置を探索中心とする。たとえば、動きベクトルＳＭＶの水平方向及び垂直方向の各値を、Ｖｘ，Ｖｙとする。この場合、基準点の座標（Ｐｘ，Ｐｙ）に対して、探索中心の座標（Ｓｘ，Ｓｙ）を、Ｓｘ＝Ｐｘ＋２Ｖｘ，Ｓｙ＝Ｐｙ＋２Ｖｙ，とする。そして、この探索中心として探索範囲の位置を設定する。
【００３８】
このように、縮小画像により検出した動きベクトルＳＭＶに基づいて探索範囲の位置を設定することで、対象マクロブロックＣｕの動きベクトルに応じた探索範囲を参照画像に対して設定することができる。したがって、対象マクロブロックＣｕの動きベクトルＭＶを効率よく検出することができる。また、動きベクトルＭＶを精度よく検出することができる。
【００３９】
ピクチャの種類と参照関係を説明する。
図３に示すように、４つの画像（ピクチャ）６１，６２，６３，６４は、この順番で撮影される。
【００４０】
ピクチャ６１はたとえばＩピクチャ（Ｉフレーム：Intra-coded Frame）であり、イントラ予測処理により符号化する。
ピクチャ６４はＰピクチャ（Ｐフレーム：Predicted Frame）である。このピクチャ６４に含まれるマクロブロック６４ａは、ピクチャ６１に含まれるマクロブロック６１ａと同一または類似している。ピクチャ６４の符号化処理において、ピクチャ６１を参照画像（前方参照画像）とした動きベクトル探索処理を行い、マクロブロック６４ａにおける参照情報を符号化する。
【００４１】
ピクチャ６２はＢピクチャ（Ｂフレーム：Bi-directional Predicted Frame）である。このピクチャ６２に含まれるマクロブロック６２ａは、前方ピクチャ６１に含まれるマクロブロック６１ｂと同一または類似している。また、このマクロブロック６２ａは、後方のピクチャ６４に含まれるマクロブロック６４ｂと同一または類似している。ピクチャ６２の符号化処理において、ピクチャ６１とピクチャ６４を参照画像（前方参照、後方参照、双方向参照）とした動きベクトル探索処理を行い、マクロブロック６２ａにおける参照情報を符号化する。
【００４２】
ピクチャ６３はＢピクチャである。このピクチャ６３に含まれるマクロブロック６３ａは、前方ピクチャ６１に含まれるマクロブロック６１ｃと同一または類似している。また、このマクロブロック６３ａは、後方のピクチャ６４に含まれるマクロブロック６４ｃと同一または類似している。ピクチャ６３の符号化処理において、ピクチャ６１とピクチャ６４を参照画像（前方参照、後方参照、双方向参照）とした動きベクトル探索処理を行い、マクロブロック６３ａにおける参照情報を符号化する。
【００４３】
次に、Ｐピクチャにおける参照画像とマクロブロック（ＭＢ）を説明する。
図４に示すように、３つの画像（ピクチャ）７１，７２，７３は、この順番で撮影される。現処理画像７３は、４つのマクロブロック７３ａ，７３ｂ，７３ｃ，７３ｄを含む。現処理画像７３はＰピクチャである。マクロブロック７３ａは、前方（現処理画像７３より時間的に過去）の参照画像７１のマクロブロック７１ａと同一または類似している。参照画像７１はＩピクチャまたはＰピクチャであり、現処理画像７３よりも前に符号化されている。したがって、現処理画像７３において、参照画像７１に含まれるマクロブロック７１ａを示す情報と差分を符号化する。
【００４４】
現処理画像７３のマクロブロック７３ｂは、前方の参照画像７２のマクロブロック７２ａと同一または類似している。参照画像７２はＩピクチャまたはＰピクチャであり、現処理画像７３よりも前に符号化されている。したがって、現処理画像７３において、参照画像７２に含まれるマクロブロック７２ａを示す情報と差分を符号化する。
【００４５】
同様に、現処理画像７３のマクロブロック７３ｃ，７３ｄは、前方の参照画像７２のマクロブロック７２ｂ，７２ｃと同一または類似している。現処理画像７３において、参照画像７２に含まれるマクロブロック７２ｂ，７２ｃを示す情報と差分を符号化する。
【００４６】
次に、Ｂピクチャにおける参照画像とマクロブロック（ＭＢ）を説明する。
図５に示すように、５つの画像（ピクチャ）８１，８２，８３，８４，８５は、この順番で撮影される。現処理画像８３は４つのマクロブロック８３ａ，８３ｂ，８３ｃ，８３ｄを含む。現処理画像８３はＢピクチャである。マクロブロック８３ａは、前方（現処理画像８３より時間的に過去）の参照画像８１のマクロブロック８１ａと同一または類似している。参照画像８１はＩピクチャまたはＰピクチャであり、現処理画像８３よりも前に符号化されている。したがって、現処理画像８３において、参照画像８１に含まれるマクロブロック８１ａを示す情報と差分を符号化する。
【００４７】
現処理画像８３のマクロブロック８３ｂは、前方の参照画像８２のマクロブロック８２ａと同一または類似している。また、マクロブロック８３ｂは、後方（現処理画像８３より時間的に未来）の参照画像８４のマクロブロック８４ａと統一または類似している。参照画像８４はＩピクチャまたはＰピクチャであり、現処理画像８３よりも前に符号化されている。したがって、現処理画像８３において、参照画像８２，８４に含まれるマクロブロック８２ａ，８４ａを示す情報と差分を符号化する。
【００４８】
現処理画像８３のマクロブロック８３ｃは、後方の参照画像８５のマクロブロック８５ａと同一または類似している。参照画像８５はＩピクチャまたはＰピクチャであり、現処理画像８３よりも前に符号化されている。したがって、現処理画像８３において、参照画像８５に含まれるマクロブロック８５ａを示す情報と差分を符号化する。
【００４９】
現処理画像８３のマクロブロック８３ｄは、前方の参照画像８２のマクロブロック８２ｂと同一または類似している。また、マクロブロック８３ｄは、後方の参照画像８４のマクロブロック８４ｂと統一または類似している。したがって、現処理画像８３において、参照画像８２，８４に含まれるマクロブロック８２ｂ，８４ｂを示す情報と差分を符号化する。
【００５０】
次に、ピクチャ内における処理順序と、動きベクトル予測値（ＭＶＰ），予測差分値（ＭＶＤ）の算出処理を説明する。
図６に示すように、１つのピクチャ（フレーム）９１は、マトリックス状に配列された複数個（８×６個）のマクロブロック（ＭＢ）を含む。各マクロブロック（ＭＢ）は、たとえば水平方向１６画素，垂直方向１６画素の画素マトリクスである。
【００５１】
符号化処理は、破線の矢印で示したように、ラスタスキャン方向に配置された複数のマクロブロックＭＢ毎に実施される。つまり、最上端のマクロブロックラインの左端のマクロブロックＭＢから右端のマクロブロックＭＢの順に実施される。次に、２段目のマクロブロックラインの左端のマクロブロックＭＢから右端のマクロブロックＭＢの順に符号化処理が実施される。以降、左端のマクロブロックＭＢから右端のマクロブロックＭＢの順に実施される符号化処理が、最下端のマクロブロックラインまで繰り返される。
【００５２】
処理対象のマクロブロックを「Ｃｕ」として示す。この対象マクロブロックＣｕの周辺のマクロブロック「Ａ」「Ｂ」「Ｃ」の動きベクトル（ＭＶＡ）（ＭＶＢ）（ＭＶＣ）に基づいて、動きベクトル予測値（ＭＶＰ）を算出する。動きベクトル予測値（ＭＶＰ）は、周辺のマクロブロック「Ａ」「Ｂ」「Ｃ」の動きベクトル（ＭＶＡ）（ＭＶＢ）（ＭＶＣ）の中間値である。つまり、動きベクトル予測値（ＭＶＰ）は、ＭＶＰ＝Ｍｅｄｉａｎ（ＭＶＡ，ＭＶＢ，ＭＶＣ），により算出される。なお、「Ｍｅｄｉａｎ」は、中間値を得る算術子である。そして、予測差分値（ＭＶＤ）は、対象マクロブロックＣｕの動きベクトル（ＭＶ）と動きベクトル予測値（ＭＶＰ）に基づいて、ＭＶＤ＝ＭＶ−ＭＶＰ，により算出される。
【００５３】
次に、動きベクトルの探索の概略を説明する。
図７（ａ）に示すように、現処理画像１２０に含まれる対象マクロブロックＣｕの動きベクトルを検出する。この検出において、現処理画像１２０と時間的に異なる画像であって、現処理画像１２０よりも前に符号化された参照画像１１０を用いる。この参照画像１１０において、対象マクロブロックＣｕと空間的に同一位置の仮想マクロブロックを含む探索範囲１１１を設定する。なお、対象マクロブロックＣｕに対応する仮想マクロブロックを明示するために同じ符号「Ｃｕ」を用いて示す場合がある。動き探索処理は、この探索範囲１１１内にあって、対象マクロブロックＣｕに対して評価値が最小の候補ブロックを探索する。
【００５４】
図７（ｂ）に示すように、探索範囲１１１の大きさは、仮想マクロブロックＣｕと、その仮想マクロブロックＣｕの周辺の８個のマクロブロックを含むように設定される。対象マクロブロックＣｕは、たとえば１６×１６画素の画素マトリックスである。これに基づき、たとえば、マクロブロック（ＭＢ）に対して水平方向と垂直方向にそれぞれ±１６画素を含むように探索範囲の大きさを設定する。このような設定の場合、探索範囲の大きさは、４８×４８画素（３×３マクロブロックを含む大きさ）となる。
【００５５】
ここで、探索範囲に対する全探索法を説明する。
先ず、図１１（ａ）に示すように、探索範囲１１１の左上に候補ブロック１１２を設定する。そして、この候補ブロック１１２に含まれる画素の画素値と、対象マクロブロックＣｕに含まれる画素の画素値とに基づいて、評価値を算出する。評価値は、上記したように、たとえば差分絶対値和（ＳＡＤ）である。このように算出した評価値を、候補ブロック１１２の位置情報に関連付けて記憶する。たとえば、この探索処理を図２に示す動き探索部４４にて実行する場合、記憶する領域は、たとえば動き探索部４４に含まれるバッファである。なお、以下の説明において算出する評価値についても同様に記憶する。
【００５６】
次に、図１１（ｂ）に示すように、探索範囲１１１において、候補ブロック１１２を、右側に１画素分ずらして設定する。そして、この候補ブロック１１２の評価値を算出する。このように、右側に向かって１画素ずつずらして設定した候補ブロックの評価値を算出する。そして、図１１（ｃ）に示すように、探索範囲１１１において、右端に設定した候補ブロック１１２の評価値を算出すると、上記と同様の処理を、１画素分下側にずらして設定した候補ブロックについて行う。
【００５７】
即ち、図１１（ｄ）に示すように、探索範囲１１１の左端において、上端から１画素分下がった位置に候補ブロック１１２を設定する。そして、この候補ブロック１１２の評価値を算出する。そして、図１１（ｅ）に示すように、探索範囲１１１において、候補ブロック１１２を、右側に１画素分ずらして設定する。そして、この候補ブロック１１２の評価値を算出する。このように、１画素ずつ候補ブロック１１２の設定位置をずらし、各位置に設定した候補ブロック１１２の評価値を算出する。そして、図１１（ｆ）に示すように、探索範囲１１１の右下に候補ブロック１１２を設定し、この候補ブロック１１２における評価値を算出する。
【００５８】
このように、探索範囲１１１に設定した全ての候補ブロック１１２の評価値を算出する。記憶した全ての評価値のうち、もっとも小さな評価値に関連付けた候補ブロック１１２の位置情報を得る。
【００５９】
たとえば、図１２に示すように、上記の動き探索により、評価値が最小の候補ブロック１１２を検出する。そして、参照画像１１０において、仮想マクロブロックＣｕから、検出した候補ブロック１１２までの移動量を算出する。この移動量は、対象マクロブロックＣｕの動きベクトルＭＶである。
【００６０】
次に、縮小画像による動き探索を説明する。
上記の図７（ａ）に示す現処理画像１２０と参照画像１１０とをそれぞれ縮小した縮小画像を生成する。
【００６１】
図８（ａ）に示すように、縮小処理画像１４０は、図７（ａ）に示す現処理画像１２０を、たとえば１／２に縮小したものである。同様に、縮小参照画像１３０は、図７（ａ）に示す参照画像１１０を、たとえば１／２に縮小したものである。縮小処理画像１４０に含まれる縮小マクロブロック１４１は、図７（ａ）に示す対象マクロブロックＣｕを１／２に縮小したものである。この縮小マクロブロック１４１に対して、空間的に同一位置の仮想マクロブロック１３１を中心とする探索範囲１３２を縮小参照画像１３０に設定する。
【００６２】
図８（ｂ）に示すように、探索範囲１３２の大きさは、仮想マクロブロック１３１と、その仮想マクロブロック１３１の大きさに応じて設定される。１つの縮小マクロブロック（ＳＭＢ）は、たとえば８×８画素の画素マトリックスである。これに基づき、たとえば、縮小マクロブロック（ＳＭＢ）に対して水平方向と垂直方向にそれぞれ±８画素を含むように探索範囲の大きさを設定する。このような設定の場合、探索範囲の大きさは、２４×２４画素となる。この探索範囲１３２において、対象マクロブロックＳＭＢを用いて探索する。
【００６３】
図９（ａ）に示すように、探索範囲１３２において、縮小マクロブロックＳＭＢに対する評価値が最も小さな候補ブロック１３３を検出する。そして、図９（ｂ）に示すように、仮想マクロブロック１３１に対する候補ブロック１３３の移動量（動きベクトルＳＭＶ）を算出する。このように検出した動きベクトルに基づいて、原画サイズの画像について、動きベクトルＭＶを検出する。
【００６４】
すなわち、図１０（ａ）に示すように、参照画像１１０において、上記のように検出した動きベクトルＳＭＶに基づいて、探索範囲を設定する。ただし、動きベクトルＳＭＶは、現処理画像１２０と参照画像１１０をそれぞれ１／２に縮小した縮小処理画像１４０と縮小参照画像１３０（図８（ａ）参照）により探索された動きベクトルである。このため、動きベクトルＳＭＶの水平方向の成分と垂直方向の成分をそれぞれ２倍した成分の仮想動きベクトルＰＭＶを算出する。この仮想動きベクトルＰＭＶは、対象マクロブロックＣｕに対して、評価値が最も小さい候補ブロックが存在しうる確立の高い場所を示す。
【００６５】
このため、図１０（ｂ）に示すように、仮想動きベクトルＰＭＶに応じて参照画像１１０における探索範囲を設定する。たとえば、仮想マクロブロックＣｕを中心とする探索範囲１１１を、仮想動きベクトルＰＭＶに応じてオフセットした探索範囲１１１ａを設定する。このように設定した探索範囲１１１ａは、中心部分において、対象マクロブロックＣｕに対応して、最も小さな評価値の候補ブロック１１２が存在する確立が高い。つまり、対象マクロブロックＣｕの画素との差が小さい画素が含まれる。一方、探索範囲１１１ａの外側であって、探索範囲１１１との間の領域には、対象マクロブロックＣｕの画素との差が大きい画素が含まれる。したがって、このようにオフセットした探索範囲１１１ａを設定することで、効率のよい探索を行うことができる。
【００６６】
図１３は、動きベクトル検出部３２において、１つのマクロブロック（ＭＢ）に対する処理を機能的に示すフローチャートである。動きベクトル検出処理を、このフローチャートにしたがって実施することもできる。
【００６７】
先ず、ステップ２０１において、現処理画像と参照画像を取得する。そして、ステップ２０２において、現処理画像と参照画像について、複数パターンの縮小画像を生成する。次に、ステップ２０３において、縮小画像（縮小処理画像、縮小参照画像）を用い、全探索法にしたがって探索を行い、対象マクロブロックの動きベクトルＳＭＶを検出する。
【００６８】
次に、ステップ２０４において、全画素探索完了したか否かを判定する。探索範囲に含まれる全画素について探索を完了していない場合（判定：ＮＯ）、ステップ２０５へ移行する。次いで、ステップ２０５において、打ち切り処理か否かを判定する。打ち切り処理ではない場合（判定：ＮＯ）、ステップ２０６へ移行する。
【００６９】
そして、ステップ２０６において、縮小画像により検出した動きベクトルＳＭＶに基づいて参照画像における探索範囲を設定する。さらに、原処理画像における動きベクトルと後方参照画像における動きベクトルの統計結果（統計動きベクトル）に基づいて探索開始位置Ｇｓと探索方向Ｓｄを設定する。そして、参照画像の探索範囲内を全探索法にしたがって探索を実施する。
【００７０】
次に、ステップ２０７において、前のマクロブロック（ＭＢ）に対する探索処理において、探索打ち切りがあったか否かを判定する。探索打ち切りがあった場合（判定：ＹＥＳ）、ステップ２０８へ移行する。一方、探索打ち切りがなかった場合（判定：ＮＯ）、ステップ２０４へ移行する。
【００７１】
ステップ２０８において、前のマクロブロック（ＭＢ）に対する探索処理においける打ち切りの状態に応じて探索範囲を拡大する。このとき、レジスタ４４ａに保持したサイクル数に基づいて拡大する領域の大きさを設定する。また、統計動きベクトルＭＶＳ，ＭＶＲに応じて、領域を拡大する方向を設定する。そして、ステップ２０４へ移行する。
【００７２】
ステップ２０４における判定において、全画素について探索を完了した場合（判定：ＹＥＳ）、ステップ２０９へ移行する。また、ステップ２０５における判定において、打ち切り処理の場合（判定ＹＥＳ）、ステップ２０９へ移行する。そして、ステップ２０９において、残りサイクル数をレジスタ４４ａに保持する。そして、対象マクロブロックＣｕに対する処理を終了する。
【００７３】
次に、比較例の処理を説明する。
図１４に示すように、ステップ４０１において、現処理画像と参照画像を取得する。ステップ４０２において、現処理画像と参照画像について、それぞれ１つの縮小画像（縮小処理画像、縮小参照画像）を生成する。ステップ４０３において、縮小画像（縮小処理画像、縮小参照画像）を用い、全探索法にしたがって探索を行い、対象マクロブロックの動きベクトルＳＭＶを検出する。ステップ４０４において、全画素探索完了したか否かを判定する。探索範囲に含まれる全画素について探索を完了した場合（判定：ＹＥＳ）、処理を終了する。全画素について探索を完了していない場合（判定：ＮＯ）、ステップ４０５に移行する。ステップ４０５において、検出した動きベクトルＳＭＶに基づいて参照画像における探索範囲を設定し、その探索範囲内を全探索法にしたがって探索を実施する。
【００７４】
次に、統計処理に用いる動きベクトルについて説明する。
図１５に示すように、４つの画像（ピクチャ）１５１，１５２，１５３，１５４は、この順番で撮影される。たとえば、ピクチャ１５１はＩピクチャまたはＰピクチャであり、ピクチャ１５４はＰピクチャであり、ピクチャ１５２，１５３はＢピクチャである。
【００７５】
たとえば、ピクチャ１５２を現処理画像とする。そして、この現処理画像１５２に含まれる対象マクロブロックＣｕの動きベクトルを検出する。このとき、現処理画像１５２において、左上のマクロブロック（ＭＢ）から、ラスタ方向（破線矢印にて示す）に沿って符号化処理され、これらのマクロブロック（ＭＢ）について動きベクトルが生成されている。これらのマクロブロックのうち、対象マクロブロックＣｕを中心とする参照領域１５２ａに含まれ、既に符号化処理されたマクロブロック（対象マクロブロックＣｕより濃いハッチングにて示されたマクロブロック）において、現処理画像１５２から前方の参照画像１５１を参照した動きベクトルを用いる。参照領域１５２ａは、たとえば、図７（ｂ）に示す探索範囲１１１と同じ大きさに設定される。これらのマクロブロックの動きベクトルを統計処理（平均化）して統計動きベクトルＭＶＣを生成する。
【００７６】
また、現処理画像１５２について後方のピクチャ（後方参照画像）１５４はＰピクチャであり、この後方参照画像１５４は、前方のピクチャ（前方参照画像）１５１を参照する。そして、この後方参照画像１５４に含まれる全てのマクロブロックは、現処理画像１５２よりも前に符号化され、それぞれの動きベクトルが生成されている。この後方参照画像１５４において、現処理画像１５２の対象マクロブロックＣｕと空間的に同一位置の参照マクロブロック（「Ｃ１」と表記）を中心とする参照領域１５４ａに含まれるマクロブロックにおいて、後方参照画像１５４から前方参照画像１５１を参照した動きベクトルを用いる。そして、後方参照画像１５４の動きベクトルを統計処理（平均化）して統計動きベクトルＭＶＲを生成する。
【００７７】
［探索開始位置と探索方向］
次に、探索開始位置と探索方向の各ケースを説明する。
図１６（ａ）に示すように、４つの画像（ピクチャ）１５１〜１５４において、現処理画像であるピクチャ１５２の参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、参照するピクチャ１５１において、探索範囲１５１ａに対して右上方向を示す。また、ピクチャ１５２の後方参照画像であるピクチャ１５４の参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、参照するピクチャ１５１において、探索範囲１５１ａに対して右上方向を示す。つまり、図１６（ｂ）に示すように、参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、右上方向を示す。また、図１６（ｃ）に示すように、参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、右上方向を示す。このような場合を［ケース１］とする。
【００７８】
図１６（ｄ）に示すように、［ケース１］では、探索範囲１５１ａにおいて、仮想マクロブロックＣ０に対して、右上方向に探索開始位置Ｇｓを設定する。そして、図１６（ｅ）に示すように、探索開始位置Ｇｓから左下方向に向かって斜めに探索するように、探索方向Ｓｄを設定する。なお、図において、四角で囲んだ数字は、探索順序を示す。このように、探索方向Ｓｄに対して、左右交互に探索する。
【００７９】
図１７（ａ）に示すように、ピクチャ１５２の参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、ピクチャ１５１において、探索範囲１５１ａに対して上方向を示す。また、ピクチャ１５４の参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、ピクチャ１５１において、探索範囲１５１ａに対して上方向を示す。つまり、図１７（ｂ）に示すように、参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、上方向を示す。また、図１７（ｃ）に示すように、参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、上方向を示す。このような場合を［ケース２］とする。
【００８０】
図１７（ｄ）に示すように、［ケース２］では、探索範囲１５１ａにおいて、仮想マクロブロックＣ０に対して、上方向に探索開始位置Ｇｓを設定する。そして、図１７（ｅ）に示すように、探索開始位置Ｇｓから下方向に向かって探索するように、探索方向Ｓｄを設定する。なお、図において、四角で囲んだ数字は、探索順序を示す。このように、探索方向Ｓｄに対して、左右交互に探索する。
【００８１】
図１８（ａ）に示すように、ピクチャ１５２の参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、ピクチャ１５１において、探索範囲１５１ａに対して左上方向を示す。また、ピクチャ１５４の参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、ピクチャ１５１において、探索範囲１５１ａに対して左上方向を示す。つまり、図１８（ｂ）に示すように、参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、左上方向を示す。また、図１８（ｃ）に示すように、参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、左上方向を示す。このような場合を［ケース３］とする。
【００８２】
図１８（ｄ）に示すように、［ケース３］では、探索範囲１５１ａにおいて、仮想マクロブロックＣ０に対して、左上方向に探索開始位置Ｇｓを設定する。そして、図１８（ｅ）に示すように、探索開始位置Ｇｓから右下方向に向かって斜めに探索するように、探索方向Ｓｄを設定する。なお、図において、四角で囲んだ数字は、探索順序を示す。このように、探索方向Ｓｄに対して、左右交互に探索する。
【００８３】
図１９（ａ）に示すように、ピクチャ１５２の参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、ピクチャ１５１において、探索範囲１５１ａに対して左方向を示す。また、ピクチャ１５４の参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、ピクチャ１５１において、探索範囲１５１ａに対して左方向を示す。つまり、図１９（ｂ）に示すように、参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、左方向を示す。また、図１９（ｃ）に示すように、参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、左方向を示す。このような場合を［ケース４］とする。
【００８４】
図１９（ｄ）に示すように、［ケース４］では、探索範囲１５１ａにおいて、仮想マクロブロックＣ０に対して、左方向に探索開始位置Ｇｓを設定する。そして、図１９（ｅ）に示すように、探索開始位置Ｇｓから右方向に向かって探索するように、探索方向Ｓｄを設定する。なお、図において、四角で囲んだ数字は、探索順序を示す。このように、探索方向Ｓｄに対して、左右交互に探索する。
【００８５】
上記の［ケース１］〜［ケース４］に対して、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲの方向がそれぞれ逆方向の場合がある。それらを［ケース５］〜［ケース８］とする。なお、探索開始位置と探索方向は、第１の統計動きベクトルＭＶＳ，ＭＶＲの方向に応じて、上記の［ケース１］〜［ケース４］に対して逆方向に設定される。このため、図面を省略する。
【００８６】
たとえば、第１及び第２の統計動きベクトルＭＶＳ，ＭＶＲが共に左下方向の［ケース５］では、探索範囲１５１ａにおいて、仮想マクロブロックＣ０に対して、左下方向に探索開始位置Ｇｓを設定する。そして、探索開始位置Ｇｓから右上方向に向かって斜めに探索するように、探索方向Ｓｄを設定する。そして、探索方向Ｓｄに対して、左右交互に探索する。
【００８７】
また、第１及び第２の統計動きベクトルＭＶＳ，ＭＶＲが共に下方向の［ケース６］では、探索範囲１５１ａにおいて、仮想マクロブロックＣ０に対して、下方向に探索開始位置Ｇｓを設定する。そして、探索開始位置Ｇｓから上方向に向かって探索するように、探索方向Ｓｄを設定する。そして、探索方向Ｓｄに対して、左右交互に探索する。
【００８８】
また、第１及び第２の統計動きベクトルＭＶＳ，ＭＶＲが共に右下方向の［ケース７］では、探索範囲１５１ａにおいて、仮想マクロブロックＣ０に対して、右下方向に探索開始位置Ｇｓを設定する。そして、探索開始位置Ｇｓから左上方向に向かって斜めに探索するように、探索方向Ｓｄを設定する。そして、探索方向Ｓｄに対して、左右交互に探索する。
【００８９】
そして、第１及び第２の統計動きベクトルＭＶＳ，ＭＶＲが共に右方向の［ケース８］では、探索範囲１５１ａにおいて、仮想マクロブロックＣ０に対して、右方向に探索開始位置Ｇｓを設定する。そして、探索開始位置Ｇｓから左方向に向かって探索するように、探索方向Ｓｄを設定する。そして、探索方向Ｓｄに対して、左右交互に探索する。
【００９０】
つまり、第１及び第２の統計動きベクトルＭＶＳ，ＭＶＲが同じ方向の場合、探索範囲において、仮想マクロブロックＣ０に対して、統計動きベクトルＭＶＳ，ＭＶＲの方向に探索開始位置を設定する。そして、統計動きベクトルＭＶＳ，ＭＶＲと逆方向の探索方向を設定する。
【００９１】
図２０（ａ）に示すように、ピクチャ１５２の参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、ピクチャ１５１において、探索範囲１５１ａに対して左下方向を示す。また、ピクチャ１５４の参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、ピクチャ１５１において、探索範囲１５１ａに対して右上方向を示す。つまり、図２０（ｂ）に示すように、参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、左下方向を示す。また、図２０（ｃ）に示すように、参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、右上方向を示す。このような場合を［ケース９］とする。なお、統計動きベクトルＭＶＳ，ＭＶＲの方向が逆、つまり第１の統計動きベクトルＭＶＳが右上方向、第２の統計動きベクトルＭＶＲが左下方向の場合もこの［ケース９］とする。
【００９２】
図２０（ｄ）に示すように、［ケース９］では、探索範囲１５１ａにおいて、仮想マクロブロックＣ０の左上の画素に探索開始位置Ｇｓを設定する。そして、図２０（ｅ）に示すように、探索開始位置Ｇｓから右上方向に向かって探索を開始し、渦巻き状に順次外側に向かって広がるように、探索方向Ｓｄを設定する。なお、探索方向Ｓｄにおいて、破線にて示す部分は、拡張探索範囲における探索順序を示す。
【００９３】
図２１（ａ）に示すように、ピクチャ１５２の参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、ピクチャ１５１において、探索範囲１５１ａに対して上方向を示す。また、ピクチャ１５４の参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、ピクチャ１５１において、探索範囲１５１ａに対して下方向を示す。つまり、図２１（ｂ）に示すように、参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、上方向を示す。また、図２１（ｃ）に示すように、参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、下方向を示す。このような場合を［ケース１０］とする。なお、統計動きベクトルＭＶＳ，ＭＶＲの方向が逆、つまり第１の統計動きベクトルＭＶＳが下方向、第２の統計動きベクトルＭＶＲが上方向の場合もこの［ケース１０］とする。
【００９４】
図２１（ｄ）に示すように、［ケース１０］では、探索範囲１５１ａにおいて、仮想マクロブロックＣ０に対して、上方向に探索開始位置Ｇｓを設定する。そして、図２１（ｅ）に示すように、探索開始位置Ｇｓから下方向に向かって探索を開始し、縦方向に長い矩形を渦巻き状に順次外側に向かって広がるように、探索方向Ｓｄを設定する。なお、探索方向Ｓｄにおいて、破線にて示す部分は、拡張探索範囲における探索順序を示す。なお、仮想マクロブロックＣ０に対して、下方向に探索開始位置Ｇｓを設定し、上方向に探索を開始するようにしてもよい。
【００９５】
図２２（ａ）に示すように、ピクチャ１５２の参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、ピクチャ１５１において、探索範囲１５１ａに対して右下方向を示す。また、ピクチャ１５４の参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、ピクチャ１５１において、探索範囲１５１ａに対して左上方向を示す。つまり、図２２（ｂ）に示すように、参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、右下方向を示す。また、図２２（ｃ）に示すように、参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、左上方向を示す。このような場合を［ケース１１］とする。なお、統計動きベクトルＭＶＳ，ＭＶＲの方向が逆、つまり第１の統計動きベクトルＭＶＳが左上方向、第２の統計動きベクトルＭＶＲが右下方向の場合もこの［ケース１１］とする。
【００９６】
図２２（ｄ）に示すように、［ケース１１］では、探索範囲１５１ａにおいて、仮想マクロブロックＣ０の左上の画素に探索開始位置Ｇｓを設定する。そして、図２２（ｅ）に示すように、探索開始位置Ｇｓから左上方向に向かって探索を開始し、渦巻き状に順次外側に向かって広がるように、探索方向Ｓｄを設定する。なお、探索方向Ｓｄにおいて、破線にて示す部分は、拡張探索範囲における探索順序を示す。
【００９７】
図２３（ａ）に示すように、ピクチャ１５２の参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、ピクチャ１５１において、探索範囲１５１ａに対して左方向を示す。また、ピクチャ１５４の参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、ピクチャ１５１において、探索範囲１５１ａに対して右方向を示す。つまり、図２３（ｂ）に示すように、参照領域１５２ａにおける第１の統計動きベクトルＭＶＳは、左方向を示す。また、図２３（ｃ）に示すように、参照領域１５４ａにおける第２の統計動きベクトルＭＶＲは、右方向を示す。このような場合を［ケース１２］とする。なお、統計動きベクトルＭＶＳ，ＭＶＲの方向が逆、つまり第１の統計動きベクトルＭＶＳが右方向、第２の統計動きベクトルＭＶＲが左方向の場合もこの［ケース１２］とする。
【００９８】
図２３（ｄ）に示すように、［ケース１２］では、探索範囲１５１ａにおいて、仮想マクロブロックＣ０に対して、左方向に探索開始位置Ｇｓを設定する。そして、図２３（ｅ）に示すように、探索開始位置Ｇｓから右方向に向かって探索を開始し、横方向に長い矩形を渦巻き状に順次外側に向かって広がるように、探索方向Ｓｄを設定する。なお、探索方向Ｓｄにおいて、破線にて示す部分は、拡張探索範囲における探索順序を示す。なお、仮想マクロブロックＣ０に対して、右方向に探索開始位置Ｇｓを設定し、左方向に探索を開始するようにしてもよい。
【００９９】
第１の統計動きベクトルＭＶＳの方向と第２の統計動きベクトルＭＶＲの方向が上記の何れにも当てはまらない場合を［ケース１３］とする。この［ケース１３］では、図２４（ａ）に示すように、探索範囲１５１ａにおいて、仮想マクロブロックＣ０に対して、左方向に探索開始位置Ｇｓを設定する。そして、図２４（ｂ）に示すように、探索開始位置Ｇｓから右方向に向かって探索を開始し、探索するラインを順次下にずらすように、探索方向Ｓｄを設定する。
【０１００】
次に、探索開始位置と探索方向の各ケースの選択処理の流れの一例を説明する。
図２５，図２６は、選択のフローチャートである。図２５，図２６において、現処理画像１５２（図１５参照）における第１の統計動きベクトルＭＶＳを「前方」、後方参照画像１５４（図１５参照）における第２の統計動きベクトルＭＶＲを「後方」と表記する。
【０１０１】
前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲの方向に応じて、［ケースｎ］の探索開始位置及び探索方向を設定する。
各［ケースｎ］の探索開始位置と探索方向は、たとえば、対象マクロブロックＣｕの座標値（たとえば、左上の画素の座標値）を基準とする相対的な位置及び方向である。また、各［ケースｎ］の探索開始位置と探索方向は、たとえば、テーブルのデータとして、レジスタ等に格納されている。
【０１０２】
先ず、図２５に示すように、ステップ２２１において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に右上方向の場合（判定：ＹＥＳ）、ステップ２２２において［ケース１］の探索開始位置及び探索方向を設定する。たとえば、レジスタから［ケース１］の情報として記憶された値を読み出し、それらの値を探索開始位置及び探索方向とする。ステップ２２３において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に上方向の場合（判定：ＹＥＳ）、ステップ２２４において［ケース２］の探索開始位置及び探索方向を設定する。ステップ２２５において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に左上方向の場合（判定：ＹＥＳ）、ステップ２２６において［ケース３］の探索開始位置及び探索方向を設定する。
【０１０３】
次に、ステップ２２７において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に左方向の場合（判定：ＹＥＳ）、ステップ２２８において［ケース４］の探索開始位置及び探索方向を設定する。ステップ２２９において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に左下方向の場合（判定：ＹＥＳ）、ステップ２３０において［ケース５］の探索開始位置及び探索方向を設定する。ステップ２３１において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に下方向の場合（判定：ＹＥＳ）、ステップ２３２において［ケース６］の探索開始位置及び探索方向を設定する。ステップ２３３において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に右下方向の場合（判定：ＹＥＳ）、ステップ２３４において［ケース７］の探索開始位置及び探索方向を設定する。ステップ２３５において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に右方向の場合（判定：ＹＥＳ）、ステップ２３６において［ケース８］の探索開始位置及び探索方向を設定する。
【０１０４】
次に、図２６に示すように、ステップ２３７において、前方つまり第１の統計動きベクトルＭＶＳが右上方向であって後方つまり第２の統計動きベクトルＭＶＲが左下方向の場合（判定：ＹＥＳ）、ステップ２３８において［ケース９］の探索開始位置及び探索方向を設定する。また、ステップ２３７において、上記と逆、つまり第１の統計動きベクトルＭＶＳが右上方向であって第２の統計動きベクトルＭＶＲが左下方向、またはその逆の場合、ステップ２３８において［ケース９］の探索開始位置及び探索方向を設定する。
【０１０５】
ステップ２３９において、前方つまり第１の統計動きベクトルＭＶＳが上方向であって後方つまり第２の統計動きベクトルＭＶＲが下方向、またはその逆の場合（判定：ＹＥＳ）、ステップ２４０において［ケース１０］の探索開始位置及び探索方向を設定する。ステップ２４１において、前方つまり第１の統計動きベクトルＭＶＳが左上方向であって後方つまり第２の統計動きベクトルＭＶＲが右下方向、またはその逆の場合（判定：ＹＥＳ）、ステップ２４２において［ケース１１］の探索開始位置及び探索方向を設定する。ステップ２４３において、前方つまり第１の統計動きベクトルＭＶＳが左方向であって後方つまり第２の統計動きベクトルＭＶＲが右方向、またはその逆の場合（判定：ＹＥＳ）、ステップ２４４において［ケース１２］の探索開始位置及び探索方向を設定する。そして、上記の方向以外の場合（ステップ２４３において判定：ＮＯ）、ステップ２４５において［ケース１３］の探索開始位置及び探索方向を設定する。
【０１０６】
次に、設定された探索開始位置と探索方向による全探索を説明する。なお、ここでは、探索開始位置を、図１６（ｅ）に示す［ケース１］の探索方向Ｓｄについて説明する。
先ず、図２７（ａ）に示すように、参照画像１５１の探索範囲１５１ａの右上端に候補ブロック１５１ｂを設定する。そして、この候補ブロック１５１ｂに含まれる画素の画素値と、対象マクロブロックＣｕに含まれる画素の画素値とに基づいて、評価値を算出する。評価値は、上記したように、たとえば差分絶対値和（ＳＡＤ）である。このように算出した評価値を、候補ブロック１５１ｂの位置情報に関連付けて記憶する。
【０１０７】
次に、図２７（ｂ）に示すように、探索範囲１５１ａにおいて、候補ブロック１５１ｂを、左下方向に１画素分ずらして設定する。そして、この候補ブロック１５１ｂの評価値を算出する。このように、左下に向かって１画素ずつずらして設定した候補ブロックの評価値を算出する。そして、図２７（ｃ）に示すように、探索範囲１５１ａにおいて、左下端に設定した候補ブロック１５１ｂの評価値を算出する。
【０１０８】
次に、図１６（ｅ）に示す２番目の探索方向Ｓｄにしたがって探索処理を行う。
即ち、図２８（ａ）に示すように、探索範囲１５１ａ右上端から１画素分左にずれた位置に候補ブロック１５１ｂを設定する。そして、この候補ブロック１５１ｂの評価値を算出する。そして、図２８（ｂ）に示すように、探索範囲１５１ａにおいて、候補ブロック１５１ｂを、左下方向に１画素分ずらして設定する。そして、この候補ブロック１５１ｂの評価値を算出する。このように、左下方向に１画素ずつ候補ブロック１５１ｂの設定位置をずらし、各位置に設定した候補ブロック１５１ｂの評価値を算出する。そして、図２８（ｃ）に示すように、探索範囲１５１ａの左端に候補ブロック１５１ｂを設定し、この候補ブロック１５１ｂにおける評価値を算出する。
【０１０９】
次に、図１６（ｅ）に示す３番目の探索方向Ｓｄにしたがって探索処理を行う。
即ち、図２９（ａ）に示すように、探索範囲１５１ａ右上端から１画素分下にずれた位置に候補ブロック１５１ｂを設定する。そして、この候補ブロック１５１ｂの評価値を算出する。そして、図２９（ｂ）に示すように、探索範囲１５１ａにおいて、候補ブロック１５１ｂを、左下方向に１画素分ずらして設定する。そして、この候補ブロック１５１ｂの評価値を算出する。このように、左下方向に１画素ずつ候補ブロック１５１ｂの設定位置をずらし、各位置に設定した候補ブロック１５１ｂの評価値を算出する。そして、図２９（ｃ）に示すように、探索範囲１５１ａの下端に候補ブロック１５１ｂを設定し、この候補ブロック１５１ｂにおける評価値を算出する。
【０１１０】
［探索処理における判定しきい値調整処理］
次に、動き探索処理の打ち切りに対する探索期間の拡張の各ケースについて説明する。
たとえば、図３０に示すように、Ｎ番目のマクロブロックＭＢ（Ｎ）に対する動き探索処理を行い、次いで（Ｎ＋１）番目のマクロブロックＭＢ（Ｎ＋１）に対する動き探索処理を行う。図３０において、１つのマクロブロックＭＢに対する動き探索処理にかかる期間を「Ｔ」とする。
【０１１１】
基準探索範囲の探索に要する期間を所定数（たとえば、「３」）にて等分割する。そして、上記の期間Ｔを分割した各期間を、処理の開始から順に、第１の期間、第２の期間、第３の期間とする。そして、第１の期間，第２の期間，第３の期間を、分割数と処理の開始からの期間の順番にしたがってそれぞれ、「１／３期間」，「２／３期間」，「３／３期間」とする。マクロブロックＭＢ（Ｎ）に対する動き探索処理における打ち切りの有無と、打ち切りのタイミングに応じて、マクロブロックＭＢ（Ｎ＋１）に対する動き探索処理について、判定しきい値Ｇｊの調整と、探索期間の拡張を行う。
【０１１２】
図３０に示すように、前のマクロブロックＭＢ（Ｎ）において、打ち切りがなかった場合、マクロブロックＭＢ（Ｎ＋１）に対する動き探索処理において、処理のタイミング（サイクル数）に応じたケースの判定しきい値Ｇｊを設定する。マクロブロックＭＢ（Ｎ＋１）の処理にしたがって、「１／３期間」では［ケース１］の判定しきい値Ｇｊを、「２／３期間」では［ケース２］の判定しきい値Ｇｊを、「３／３期間」では［ケース３］の判定しきい値Ｇｊを設定する。
【０１１３】
たとえば、基準しきい値αに基づいて、その基準しきい値αから［ケース１］の演算式に基づいて判定しきい値Ｇｊを算出する。算出のために用いる演算式は、たとえば、Ｇｊ＝（４／６）×α，である。また、［ケース２］の演算式は、たとえば、Ｇｊ＝（５／６）×α，である。また、［ケース３］の演算式は、たとえば、Ｇｊ＝（６／６）×α，である。
【０１１４】
図３０に示すように、前のマクロブロックＭＢ（Ｎ）において、「１／３期間」の期間内において打ち切りを行った場合、「２／３期間」と「３／３期間」に応じた大きさの拡張探索範囲を設定し、拡張探索範囲を探索する探索期間ＥＴとする。さらに、基準探索範囲の探索に要する期間を分割した期間（サイクル数）を単位として、探索期間ＥＴを分割して第１拡張期間と第２拡張期間を設定する。第１拡張期間を「Ｅ１」、第２拡張期間を「Ｅ２」とする。
【０１１５】
そして、マクロブロックＭＢ（Ｎ＋１）に対する動き探索処理において、処理のタイミング（サイクル数）に応じたケースの判定しきい値Ｇｊを設定する。マクロブロックＭＢ（Ｎ＋１）の処理にしたがって、「１／３期間」では［ケース４］の判定しきい値Ｇｊを、「２／３期間」では［ケース５］の判定しきい値Ｇｊを、「３／３期間」では［ケース６］の判定しきい値Ｇｊを設定する。さらに、拡張探索期間ＥＴにおいて、「Ｅ１」では［ケース７］の判定しきい値Ｇｊを、「Ｅ２」では［ケース８］の判定しきい値Ｇｊを設定する。
【０１１６】
たとえば、基準しきい値αに基づいて、その基準しきい値αから［ケース４］の演算式に基づいて判定しきい値Ｇｊを算出する。算出のために用いる演算式は、たとえば、Ｇｊ＝（２／６）×α，である。また、［ケース５］の演算式はたとえば、Ｇｊ＝（３／６）×α，である。また、［ケース６］の演算式はたとえば、Ｇｊ＝（４／６）×α，である。また、［ケース７］の演算式はたとえば、Ｇｊ＝（５／６）×α，である。また、［ケース８］の演算式はたとえば、Ｇｊ＝（６／６）×α，である。
【０１１７】
図３１に示すように、前のマクロブロックＭＢ（Ｎ）において、「２／３期間」の期間内において打ち切りを行った場合、「３／３期間」に応じた大きさの拡張探索範囲を設定し、拡張探索範囲を探索する探索期間ＥＴとする。
【０１１８】
そして、マクロブロックＭＢ（Ｎ＋１）に対する動き探索処理において、処理のタイミング（サイクル数）に応じたケースの判定しきい値Ｇｊを設定する。マクロブロックＭＢ（Ｎ＋１）の処理にしたがって、「１／３期間」では［ケース９］の判定しきい値Ｇｊを、「２／３期間」では［ケース１０］の判定しきい値Ｇｊを、「３／３期間」では［ケース１１］の判定しきい値Ｇｊを、「ＥＴ」では［ケース１２］の判定しきい値Ｇｊを設定する。
【０１１９】
たとえば、基準しきい値αに基づいて、その基準しきい値αから［ケース９］の演算式に基づいて判定しきい値Ｇｊを算出する。算出のために用いる演算式は、たとえば、Ｇｊ＝（３／６）×α，である。また、［ケース１０］の演算式はたとえば、Ｇｊ＝（４／６）×α，である。また、［ケース１１］の演算式はたとえば、Ｇｊ＝（５／６）×α，である。また、［ケース１２］の演算式はたとえば、Ｇｊ＝（６／６）×α，である。
【０１２０】
なお、図３１では、マクロブロックＭＢ（Ｎ）の「１／３期間」の後に、マクロブロックＭＢ（Ｎ＋１）に対する処理を行うように示している。これは、マクロブロックＭＢ（Ｎ）において処理が実施されなかった期間（「２／３期間」，「３／３期間」）と、マクロブロックＭＢ（Ｎ＋１）における拡張探索期間ＥＴとの対応関係を示すためである。マクロブロックＭＢ（Ｎ）における打ち切りは、「１／３期間」内で行われ、その打ち切りの後にマクロブロックＭＢ（Ｎ＋１）に対する処理を行う。このため、図３１に示すタイミングよりも前（図において左方向）においてマクロブロックＭＢ（Ｎ＋１）に対する処理が開始されることがある。なお、図３２についても同様である。
【０１２１】
各期間の判定は、たとえばサイクル数により行われる。たとえば、１つの候補ブロックの処理に必要な期間（サイクル）を「１」とする。基準探索範囲の大きさを４８画素×４８画素とすると、基準探索範囲の探索に要するサイクル数は「１０８９」となる。すると、「１／３期間」のサイクル数は「１」〜「３６３」となる。同様に、「２／３期間」のサイクル数は「３６４」〜「７２６」となり、「３／３期間」のサイクル数は「７２７」〜「１０８９」となる。さらに、拡張探索期間ＥＴにおいて、「Ｅ１」は「１０９０」〜「１４５２」、「Ｅ２」は「１４５３」〜「１８１５」となる。処理中のサイクルをｔとすると、サイクルｔが上記の範囲の何れに該当するかを判定することにより、各期間を判定することができる。
【０１２２】
次に、打ち切り処理の各ケースの選択を説明する。
図３３に示すように、ステップ２５１において、処理開始からの経過時間が全探索サイクル数の１／３以内つまり「１／３期間」に、前のマクロブロック（ＭＢ）に対する探索処理の打ち切りが行われたか否かを判定する。打ち切りが１／３以内ではない場合（判定：ＮＯ）、ステップ２５２に移行する。
【０１２３】
ステップ２５２において、前のマクロブロック（ＭＢ）に対する探索処理の打ち切りが、全探索サイクル数の２／３以内つまり「２／３期間」に行われたか否かを判定する。打ち切りが「２／３期間」内ではない場合（判定：ＮＯ）、ステップ２５３に移行する。つまり、前のマクロブロック（ＭＢ）に対する探索処理において打ち切りがなかった場合にステップ２５３に移行する。
【０１２４】
そのステップ２５３において、「１／３期間」か否かを判定する。「１／３期間」の場合（判定：ＹＥＳ）、ステップ２５４において、［ケース１］の判定しきい値Ｇｊを設定する。全探索法によって候補ブロックの評価値を算出し、その評価値と判定しきい値Ｇｊを比較する。評価値が判定しきい値Ｇｊ以内の場合に、その評価値の候補ブロックを採用し、対象マクロブロックＣｕの動きベクトルを算出する。
【０１２５】
上記のステップ２５３において「１／３期間」ではない場合（判定：ＮＯ）、ステップ２５５に移行する。ステップ２５５において、「２／３期間」か否かを判定する。「２／３期間」の場合（判定：ＹＥＳ）、ステップ２５６において、［ケース２］の判定しきい値Ｇｊを設定する。全探索法によって候補ブロックの評価値を算出し、その評価値と判定しきい値Ｇｊを比較する。評価値が判定しきい値Ｇｊ以内の場合に、その評価値の候補ブロックを採用し、対象マクロブロックＣｕの動きベクトルを算出する。
【０１２６】
上記のステップ２５５において「２／３期間」ではない場合（判定ＮＯ）、ステップ２５７において、［ケース３］の判定しきい値Ｇｊを設定する。全探索法によって候補ブロックの評価値を算出し、その評価値と判定しきい値Ｇｊを比較する。評価値が判定しきい値Ｇｊ以内の場合に、その評価値の候補ブロックを採用し、対象マクロブロックＣｕの動きベクトルを算出する。
【０１２７】
上記のステップ２５２において、前のマクロブロック（ＭＢ）に対する打ち切りが２／３以内つまり「２／３期間」に行われた場合（判定：ＹＥＳ）、ステップ２５８に移行する。
【０１２８】
そのステップ２５８において、「１／３期間」か否かを判定する。「１／３期間」の場合（判定：ＹＥＳ）、ステップ２５９において、［ケース９］の判定しきい値Ｇｊを設定する。全探索法によって候補ブロックの評価値を算出し、その評価値と判定しきい値Ｇｊを比較する。評価値が判定しきい値Ｇｊ以内の場合に、その評価値の候補ブロックを採用し、対象マクロブロックＣｕの動きベクトルを算出する。
【０１２９】
上記のステップ２５８において「１／３期間」ではない場合（判定：ＮＯ）、ステップ２６０に移行する。ステップ２６０において、「２／３期間」か否かを判定する。「２／３期間」の場合（判定：ＹＥＳ）、ステップ２６１において、［ケース１０］の判定しきい値Ｇｊを設定する。全探索法によって候補ブロックの評価値を算出し、その評価値と判定しきい値Ｇｊを比較する。評価値が判定しきい値Ｇｊ以内の場合に、その評価値の候補ブロックを採用し、対象マクロブロックＣｕの動きベクトルを算出する。
【０１３０】
上記のステップ２６０において「２／３期間」ではない場合（判定：ＮＯ）、ステップ２６２に移行する。ステップ２６２において、「３／３期間」か否かを判定する。「３／３期間」の場合（判定：ＹＥＳ）、ステップ２６３において、［ケース１１］の判定しきい値Ｇｊを設定する。全探索法によって候補ブロックの評価値を算出し、その評価値と判定しきい値Ｇｊを比較する。評価値が判定しきい値Ｇｊ以内の場合に、その評価値の候補ブロックを採用し、対象マクロブロックＣｕの動きベクトルを算出する。
【０１３１】
上記のステップ２６３において「３／３期間」ではない場合（判定ＮＯ）、ステップ２６４において、［ケース１２］の判定しきい値Ｇｊを設定する。全探索法によって候補ブロックの評価値を算出し、その評価値と判定しきい値Ｇｊを比較する。評価値が判定しきい値Ｇｊ以内の場合に、その評価値の候補ブロックを採用し、対象マクロブロックＣｕの動きベクトルを算出する。
【０１３２】
上記のステップ２５１において、前のマクロブロック（ＭＢ）に対する打ち切り処理が１／３以内つまり「１／３期間」に行われた場合（判定：ＹＥＳ）、図３４に示すステップ２６５に移行する。
【０１３３】
図３４に示すステップ２６５において、「１／３期間」か否かを判定する。「１／３期間」の場合（判定：ＹＥＳ）、ステップ２６６において、［ケース４］の判定しきい値Ｇｊを設定する。全探索法によって候補ブロックの評価値を算出し、その評価値と判定しきい値Ｇｊを比較する。評価値が判定しきい値Ｇｊ以内の場合に、その評価値の候補ブロックを採用し、対象マクロブロックＣｕの動きベクトルを算出する。
【０１３４】
上記のステップ２６５において「１／３期間」ではない場合（判定：ＮＯ）、ステップ２６７に移行する。ステップ２６７において、「２／３期間」か否かを判定する。「２／３期間」の場合（判定：ＹＥＳ）、ステップ２６８において、［ケース５］の判定しきい値Ｇｊを設定する。全探索法によって候補ブロックの評価値を算出し、その評価値と判定しきい値Ｇｊを比較する。評価値が判定しきい値Ｇｊ以内の場合に、その評価値の候補ブロックを採用し、対象マクロブロックＣｕの動きベクトルを算出する。
【０１３５】
上記のステップ２６７において「２／３期間」ではない場合（判定：ＮＯ）、ステップ２６９に移行する。ステップ２６９において、「３／３期間」か否かを判定する。「３／３期間」の場合（判定：ＹＥＳ）、ステップ２７０において、［ケース６］の判定しきい値Ｇｊを設定する。全探索法によって候補ブロックの評価値を算出し、その評価値と判定しきい値Ｇｊを比較する。評価値が判定しきい値Ｇｊ以内の場合に、その評価値の候補ブロックを採用し、対象マクロブロックＣｕの動きベクトルを算出する。
【０１３６】
上記のステップ２６９において「３／３期間」ではない場合（判定：ＮＯ）、ステップ２７１に移行する。ステップ２７１において、「Ｅ１」か否かを判定する。「Ｅ１」の場合（判定：ＹＥＳ）、ステップ２７２において、［ケース７］の判定しきい値Ｇｊを設定する。全探索法によって候補ブロックの評価値を算出し、その評価値と判定しきい値Ｇｊを比較する。評価値が判定しきい値Ｇｊ以内の場合に、その評価値の候補ブロックを採用し、対象マクロブロックＣｕの動きベクトルを算出する。
【０１３７】
上記のステップ２７１において「Ｅ１」ではない場合（判定ＮＯ）、ステップ２７３において、［ケース８］の判定しきい値Ｇｊを設定する。全探索法によって候補ブロックの評価値を算出し、その評価値と判定しきい値Ｇｊを比較する。評価値が判定しきい値Ｇｊ以内の場合に、その評価値の候補ブロックを採用し、対象マクロブロックＣｕの動きベクトルを算出する。
【０１３８】
［探索範囲の拡張］
次に、探索範囲の拡張と探索方向について説明する。
図３５（ａ）は、図１６（ａ）〜図１６（ｅ）に示す［ケース１］の第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲに対応する拡張探索範囲を示す。
【０１３９】
図３５（ａ）に示すように、参照画像１６０には、基準探索範囲１６１が設定される。この基準探索範囲１６１に対して、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲに基づいて、基準探索範囲１６１の右上に拡張探索範囲１６２が設定される。拡張探索範囲１６２は、たとえば、基準探索範囲１６１を、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲの方向に従って右上方向に延ばすように設定される。
【０１４０】
図３５（ｂ）に示すように、拡張探索範囲１６２における探索方向ＥＳｄは、基準探索範囲１６１における探索方向Ｓｄと同じ方向であり、同様の順序にしたがって探索するように設定される。たとえば、基準探索範囲１６１において、四角にて示す数字「１」〜「６５」にしたがって基準探索範囲１６１を探索した後、拡張探索範囲１６２を探索する。
【０１４１】
次に、探索範囲の拡張の各ケースを説明する。
図３６（ａ）〜図３６（ｄ），図３７（ａ）〜図３７（ｅ）は、「１／３期間」において動き探索処理を打ち切った場合の拡張探索範囲の大きさを示す。
【０１４２】
図３６（ａ）に示すように、［ケース１］の拡張探索範囲１６２は、上記したように、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に右上方向の場合である。ハッチングを付した領域は、探索開始位置を示す。図３６（ｂ）に示すように、［ケース２］の拡張探索範囲１６２は、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に上方向の場合である。拡張探索範囲１６２は、基準探索範囲１６１の上に設定される。図３６（ｃ）に示すように、［ケース３］の拡張探索範囲１６２は、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に左上方向の場合である。拡張探索範囲１６２は、基準探索範囲１６１の左上に設定される。図３６（ｄ）に示すように、［ケース４］の拡張探索範囲１６２は、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に左方向の場合である。拡張探索範囲１６２は、基準探索範囲１６１の左に設定される。
【０１４３】
探索開始位置と探索方向の設定と同様に、上記の［ケース１］〜［ケース４］に対して、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲの方向がそれぞれ逆方向の場合を［ケース５］〜［ケース８］とする。なお、拡張探索範囲は、第１の統計動きベクトルＭＶＳ，ＭＶＲの方向に応じて、上記の［ケース１］〜［ケース４］に対して逆方向に設定される。このため、図面を省略する。
【０１４４】
たとえば、第１及び第２の統計動きベクトルＭＶＳ，ＭＶＲが共に左下方向の［ケース５］では、基準探索範囲１６１の左下に拡張探索範囲１６２が設定される。また、第１及び第２の統計動きベクトルＭＶＳ，ＭＶＲが共に下方向の［ケース６］では、基準探索範囲１６１の下に拡張探索範囲１６２が設定される。また、第１及び第２の統計動きベクトルＭＶＳ，ＭＶＲが共に右下方向の［ケース７］では、基準探索範囲１６１の右下に拡張探索範囲１６２が設定される。そして、第１及び第２の統計動きベクトルＭＶＳ，ＭＶＲが共に右方向の［ケース８］では、基準探索範囲１６１の右に拡張探索範囲１６２が設定される。
【０１４５】
図３７（ａ）〜図３７（ｄ）は、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが互いに逆方向の場合における拡張探索範囲の設定を示す。
図３７（ａ）に示すように、［ケース９］の拡張探索範囲１６２ａ，１６２ｂは、第１の統計動きベクトルＭＶＳが右上方向、第２の統計動きベクトルＭＶＲが左下方向の場合である。基準探索範囲１６１の右上に拡張探索範囲１６２ａが設定され、基準探索範囲１６１の左下に拡張探索範囲１６２ｂが設定される。なお、上記に対して逆方向、つまり第１の統計動きベクトルＭＶＳが左下方向、第２の統計動きベクトルＭＶＲが右上方向の場合、同様に拡張探索範囲１６２ａ，１６２ｂが設定される。図３７（ｂ）に示すように、［ケース１０］の拡張探索範囲１６２ａ，１６２ｂは、第１の統計動きベクトルＭＶＳが上方向、第２の統計動きベクトルＭＶＲが下方向の場合、またはその逆の場合である。基準探索範囲１６１の上に拡張探索範囲１６２ａが設定され、基準探索範囲１６１の下に拡張探索範囲１６２ｂが設定される。
【０１４６】
図３７（ｃ）に示すように、［ケース１１］の拡張探索範囲１６２ａ，１６２ｂは、第１の統計動きベクトルＭＶＳが左上方向、第２の統計動きベクトルＭＶＲが右下方向の場合、またはその逆の場合である。基準探索範囲１６１の左上に拡張探索範囲１６２ａが設定され、基準探索範囲１６１の右下に拡張探索範囲１６２ｂが設定される。図３７（ｄ）に示すように、［ケース１２］の拡張探索範囲１６２ａ，１６２ｂは、第１の統計動きベクトルＭＶＳが左方向、第２の統計動きベクトルＭＶＲが右方向の場合、またはその逆の場合である。基準探索範囲１６１の左に拡張探索範囲１６２ａが設定され、基準探索範囲１６１の右に拡張探索範囲１６２ｂが設定される。
【０１４７】
第１の統計動きベクトルＭＶＳの方向と第２の統計動きベクトルＭＶＲの方向が上記の何れにも当てはまらない場合を［ケース１３］とする。この［ケース１３］では、図３７（ｅ）に示すように、基準探索範囲１６１の各辺、つまり基準探索範囲１６１を囲むように拡張探索範囲１６２が設定される。
【０１４８】
図３８（ａ）〜図３８（ｄ），図３９（ａ）〜図３９（ｅ）は、「２／３期間」において動き探索処理を打ち切った場合の拡張探索範囲の大きさを示す。
図３８（ａ）に示すように、［ケース２１］の拡張探索範囲１６３は、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に右上方向の場合である。拡張探索範囲１６３は、基準探索範囲１６１の右上に設定される。図３８（ｂ）に示すように、［ケース２２］の拡張探索範囲１６３は、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に上方向の場合である。拡張探索範囲１６３は、基準探索範囲１６１の上に設定される。図３８（ｃ）に示すように、［ケース２３］の拡張探索範囲１６３は、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に左上方向の場合である。拡張探索範囲１６３は、基準探索範囲１６１の左上に設定される。図３８（ｄ）に示すように、［ケース２４］の拡張探索範囲１６３は、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に左方向の場合である。拡張探索範囲１６３は、基準探索範囲１６１の左に設定される。
【０１４９】
探索開始位置と探索方向の設定と同様に、上記の［ケース２１］〜［ケース２４］に対して、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲの方向がそれぞれ逆方向の場合を［ケース２５］〜［ケース２８］とする。なお、拡張探索範囲は、第１の統計動きベクトルＭＶＳ，ＭＶＲの方向に応じて、上記の［ケース２１］〜［ケース２４］に対して逆方向に設定される。このため、図面を省略する。
【０１５０】
たとえば、第１及び第２の統計動きベクトルＭＶＳ，ＭＶＲが共に左下方向の［ケース２５］では、基準探索範囲１６１の左下に拡張探索範囲１６３が設定される。また、第１及び第２の統計動きベクトルＭＶＳ，ＭＶＲが共に下方向の［ケース２６］では、基準探索範囲１６１の下に拡張探索範囲１６３が設定される。また、第１及び第２の統計動きベクトルＭＶＳ，ＭＶＲが共に右下方向の［ケース２７］では、基準探索範囲１６１の右下に拡張探索範囲１６３が設定される。そして、第１及び第２の統計動きベクトルＭＶＳ，ＭＶＲが共に右方向の［ケース２８］では、基準探索範囲１６１の右に拡張探索範囲１６３が設定される。
【０１５１】
図３９（ａ）〜図３９（ｄ）は、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが互いに逆方向の場合における拡張探索範囲の設定を示す。
図３９（ａ）に示すように、［ケース２９］の拡張探索範囲１６３ａ，１６３ｂは、第１の統計動きベクトルＭＶＳが右上方向、第２の統計動きベクトルＭＶＲが左下方向の場合である。基準探索範囲１６１の右上に拡張探索範囲１６３ａが設定され、基準探索範囲１６１の左下に拡張探索範囲１６３ｂが設定される。なお、上記に対して逆方向、つまり第１の統計動きベクトルＭＶＳが左下方向、第２の統計動きベクトルＭＶＲが右上方向の場合、同様に拡張探索範囲１６３ａ，１６３ｂが設定される。図３９（ｂ）に示すように、［ケース３０］の拡張探索範囲１６３ａ，１６３ｂは、第１の統計動きベクトルＭＶＳが上方向、第２の統計動きベクトルＭＶＲが下方向の場合、またはその逆の場合である。基準探索範囲１６１の上に拡張探索範囲１６３ａが設定され、基準探索範囲１６１の下に拡張探索範囲１６３ｂが設定される。
【０１５２】
図３９（ｃ）に示すように、［ケース３１］の拡張探索範囲１６３ａ，１６３ｂは、第１の統計動きベクトルＭＶＳが左上方向、第２の統計動きベクトルＭＶＲが右下方向の場合、またはその逆の場合である。基準探索範囲１６１の左上に拡張探索範囲１６３ａが設定され、基準探索範囲１６１の右下に拡張探索範囲１６３ｂが設定される。図３９（ｄ）に示すように、［ケース３２］の拡張探索範囲１６３ａ，１６３ｂは、第１の統計動きベクトルＭＶＳが左方向、第２の統計動きベクトルＭＶＲが右方向の場合、またはその逆の場合である。基準探索範囲１６１の左に拡張探索範囲１６３ａが設定され、基準探索範囲１６１の右に拡張探索範囲１６３ｂが設定される。
【０１５３】
第１の統計動きベクトルＭＶＳの方向と第２の統計動きベクトルＭＶＲの方向が上記の何れにも当てはまらない場合を［ケース３３］とする。この［ケース３３］では、図３９（ｅ）に示すように、基準探索範囲１６１の各辺、つまり基準探索範囲１６１を囲むように拡張探索範囲１６３が設定される。
【０１５４】
次に、探索範囲を拡張する各ケースの選択処理の流れの一例を説明する。
図４０〜図４３は、選択処理のフローチャートである。図４０〜図４３において、現処理画像１５２（図１５参照）における第１の統計動きベクトルＭＶＳを「前方」、後方参照画像１５４（図１５参照）における第２の統計動きベクトルＭＶＲを「後方」と表記する。
【０１５５】
図４０に示すように、ステップ３０１において、前処理ＭＢを１／３の処理時間以内で終了したか否かを判定する。つまり、対象マクロブロックＣｕの１つ前に処理したマクロブロック（ＭＢ）において、そのマクロブロック（ＭＢ）に対する動き探索処理を、「１／３期間」で打ち切ったか否かを判定する。１／３処理時間以内に終了した場合（判定：ＹＥＳ）、ステップ３０２以降において、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲの方向について判定する。
【０１５６】
ステップ３０２において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に右上方向の場合（判定：ＹＥＳ）、ステップ３０３において［ケース１］の拡張探索範囲を設定する。ステップ３０４において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に上方向の場合（判定：ＹＥＳ）、ステップ３０５において［ケース２］の拡張探索範囲を設定する。ステップ３０６において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に左上方向の場合（判定：ＹＥＳ）、ステップ３０７において［ケース３］の拡張探索範囲を設定する。
【０１５７】
ステップ３０８において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に左方向の場合（判定：ＹＥＳ）、ステップ３０９において［ケース４］の拡張探索範囲を設定する。ステップ３１０において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に左下方向の場合（判定：ＹＥＳ）、ステップ３１１において［ケース５］の拡張探索範囲を設定する。ステップ３１２において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に下方向の場合（判定：ＹＥＳ）、ステップ３１３において［ケース６］の拡張探索範囲を設定する。
【０１５８】
次に、図４１に示すステップ３１４において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に右下方向の場合（判定：ＹＥＳ）、ステップ３１５において［ケース７］の拡張探索範囲を設定する。
【０１５９】
ステップ３１６において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に右方向の場合（判定：ＹＥＳ）、ステップ３１７において［ケース８］の拡張探索範囲を設定する。
【０１６０】
ステップ３１８において、前方つまり第１の統計動きベクトルＭＶＳが右上方向であって後方つまり第２の統計動きベクトルＭＶＲが左下方向、またはその逆の場合（判定：ＹＥＳ）、ステップ３１９において［ケース９］の拡張探索範囲を設定する。ステップ３２０において、前方つまり第１の統計動きベクトルＭＶＳが上方向であって後方つまり第２の統計動きベクトルＭＶＲが下方向、またはその逆の場合（判定：ＹＥＳ）、ステップ３２１において［ケース１０］の拡張探索範囲を設定する。
【０１６１】
ステップ３２２において、前方つまり第１の統計動きベクトルＭＶＳが左上方向であって後方つまり第２の統計動きベクトルＭＶＲが右下方向、またはその逆の場合（判定：ＹＥＳ）、ステップ３２３において［ケース１１］の拡張探索範囲を設定する。ステップ３２４において、前方つまり第１の統計動きベクトルＭＶＳが左方向であって後方つまり第２の統計動きベクトルＭＶＲが右方向、またはその逆の場合（判定：ＹＥＳ）、ステップ３２５において［ケース１２］の拡張探索範囲を設定する。
【０１６２】
そして、上記の方向以外の場合（ステップ３２４において判定：ＮＯ）、ステップ３２６において［ケース１３］の拡張探索範囲を設定し、選択処理を終了する。
図４０に示すステップ３０１において、前処理のマクロブロック（ＭＢ）が１／３処理時間以内に終了していない場合（判定：ＮＯ）、図４２に示すステップ３２７に移行する。そのステップ３２７において、前処理ＭＢを２／３の処理時間以内で終了したか否かを判定する。つまり、対象マクロブロックＣｕの１つ前に処理したマクロブロック（ＭＢ）において、そのマクロブロック（ＭＢ）に対する動き探索処理を、「２／３期間」で打ち切ったか否かを判定する。２／３処理時間以内に終了していない場合（判定：ＮＯ）、選択処理を終了する。一方、２／３処理時間以内に終了した場合（判定：ＹＥＳ）、ステップ３２８以降において、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲの方向について判定する。
【０１６３】
ステップ３２８において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に右上方向の場合（判定：ＹＥＳ）、ステップ３２９において［ケース２１］の拡張探索範囲を設定する。ステップ３３０において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に上方向の場合（判定：ＹＥＳ）、ステップ３３１において［ケース２２］の拡張探索範囲を設定する。
【０１６４】
ステップ３３２において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に左上方向の場合（判定：ＹＥＳ）、ステップ３３３において［ケース２３］の拡張探索範囲を設定する。ステップ３３４において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に左方向の場合（判定：ＹＥＳ）、ステップ３３５において［ケース２４］の拡張探索範囲を設定する。
【０１６５】
ステップ３３６において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に左下方向の場合（判定：ＹＥＳ）、ステップ３３７において［ケース２５］の拡張探索範囲を設定する。ステップ３３８において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に下方向の場合（判定：ＹＥＳ）、ステップ３３９において［ケース２６］の拡張探索範囲を設定する。
【０１６６】
次に、図４３に示すステップ３４０において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に右下方向の場合（判定：ＹＥＳ）、ステップ３４１において［ケース２７］の拡張探索範囲を設定する。ステップ３４２において、前方、後方、つまり第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲが共に右方向の場合（判定：ＹＥＳ）、ステップ３４３において［ケース２８］の拡張探索範囲を設定する。
【０１６７】
ステップ３４４において、前方つまり第１の統計動きベクトルＭＶＳが右上方向であって後方つまり第２の統計動きベクトルＭＶＲが左下方向、またはその逆の場合（判定：ＹＥＳ）、ステップ３４５において［ケース２９］の拡張探索範囲を設定する。ステップ３４６において、前方つまり第１の統計動きベクトルＭＶＳが上方向であって後方つまり第２の統計動きベクトルＭＶＲが下方向、またはその逆の場合（判定：ＹＥＳ）、ステップ３４７において［ケース３０］の拡張探索範囲を設定する。
【０１６８】
ステップ３４８において、前方つまり第１の統計動きベクトルＭＶＳが左上方向であって後方つまり第２の統計動きベクトルＭＶＲが右下方向、またはその逆の場合（判定：ＹＥＳ）、ステップ３４９において［ケース３１］の拡張探索範囲を設定する。ステップ３５０において、前方つまり第１の統計動きベクトルＭＶＳが左方向であって後方つまり第２の統計動きベクトルＭＶＲが右方向、またはその逆の場合（判定：ＹＥＳ）、ステップ３５１において［ケース３２］の拡張探索範囲を設定する。そして、上記の方向以外の場合（ステップ３５０において判定：ＮＯ）、ステップ３５２において［ケース３３］の拡張探索範囲を設定し、選択処理を終了する。
【０１６９】
以上記述したように、本実施形態によれば、以下の効果を奏する。
（１）統計処理部４３は、動画像に含まれる各フレーム画像が処理単位にて分割されたマクロブロック毎に検出された複数の動きベクトルを統計処理する。動き探索部４４は、現処理画像と時間的に異なる参照画像に探索範囲を設定し、統計処理部４３の処理結果に基づいて、探索範囲内に探索開始位置を設定する。そして、動き探索部４４は、統計処理部４３の処理結果に基づいて設定した探索方向にしたがって探索範囲内を探索し、現処理画像の対象マクロブロックの動きベクトル（ＭＶ）を生成する。
【０１７０】
対象マクロブロックＣｕの動きは、周辺のマクロブロックの動きと関連性が高いことが多い。したがって、周辺のマクロブロックにおける動きベクトルを統計処理した第１の統計動きベクトルＭＶＳに基づいて探索開始位置と探索方向を設定することで、探索開始から短い経過時間にて対象マクロブロックＣｕに類似した候補ブロックを検出し、対象マクロブロックＣｕの動きベクトル（ＭＶ）を検出することができる。これにより、符号化の効率を向上することができる。
【０１７１】
（２）統計処理部４３は、現処理画像に含まれるマクロブロックについて、前方の参照画像を参照した動きベクトルを統計処理して第１の統計動きベクトルＭＶＳを生成する。また、統計処理部４３は、現処理画像が参照する後方の参照画像に含まれるマクロブロックについて、前方の参照画像を参照した動きベクトルを統計処理して第２の統計動きベクトルＭＶＲを生成する。そして、動き探索部４４は、第１の統計動きベクトルＭＶＳと第２の統計動きベクトルＭＶＲとに基づいて、探索開始位置と探索方向とを設定する。これにより、予測精度を向上することができる。
【０１７２】
（３）動き探索部４４は、候補ブロックの評価値と判定しきい値Ｇｊを比較し、比較結果に応じて、対象マクロブロックＣｕに対する動き探索処理を打ち切るようにした。そして、動き探索部４４は、設定した探索範囲を探索する期間において、判定しきい値Ｇｊを段階的に、基準しきい値αまで増加させるようにした。したがって、基準しきい値αより小さな評価値の候補ブロックを検出することが可能となる。評価値が小さな候補ブロックは、対象マクロブロックＣｕとの画素の差が少ないため、符号化されたコード量が少なくなる。これにより、符号化の効率を向上することができる。
【０１７３】
（４）動き探索部４４は、前の対象マクロブロックＣｕに対する動き探索処理を打ち切った場合に、対象マクロブロックＣｕに対して参照画像に設定する探索範囲（基準探索範囲）の外側に拡張探索範囲を設定した。そして、対象マクロブロックＣｕにおいて、前の対象マクロブロックＣｕにおいて打ち切ったタイミングに応じた期間、探索期間を増加させる。これにより、対象マクロブロックＣｕを含む現処理画像に対する探索期間を増加させることなく、対象マクロブロックＣｕに対する探索範囲を大きくすることができる。そして、拡張探索範囲において、基準探索範囲内よりも評価値が小さな候補ブロックが検出されれば、符号化されたコード量が少なくなる。これにより、符号化の効率を向上することができる。
【０１７４】
尚、上記各実施形態は、以下の態様で実施してもよい。
・上記実施形態の動き探索部４４において、拡張探索範囲の設定を省略してもよい。この場合、各対象マクロブロックの動き探索処理を打ち切ることで、動きベクトル（ＭＶ）を利用する回路における処理の時間に余裕ができ、効率のよい処理を行うことが可能となる。
【０１７５】
・上記実施形態の動きベクトル検出部３２において、縮小部４１と動き探索部４２を省略してもよい。
・上記実施形態において、基準探索範囲の探索に要する期間を３分割したが、２分割、または４分割以上としてもよい。また、分割した処理期間のサイクル数が異なっていてもよい。たとえば、第１期間を１／２とし、第２，第３期間をそれぞれ１／４とする。また、第１期間を１／２，第２期間を１／３，第３期間を１／６とする。
【０１７６】
・上記実施形態において判定しきい値Ｇｊを算出するための演算式は一例であり、演算式を適地変更してもよい。また、判定しきい値Ｇｊをたとえばテーブルデータによって求めるようにしてもよい。
【０１７７】
・上記実施形態の動き探索部４４において、第１の統計動きベクトルＭＶＳに基づいて探索開始位置、探索方向、等を設定してもよい。
【符号の説明】
【０１７８】
４３  統計処理部
４４  動き探索部
１５１  参照画像（前方参照画像）
１５１ａ  探索範囲
１５１ｂ  候補ブロック
１５２  現処理画像
１５４  参照画像（後方参照画像）
１６０  参照画像（前方参照画像）
１６１  基準探索範囲（第１探索範囲）
１６２，１６２ａ，１６２ｂ  拡張探索範囲（第２探索範囲）
１６３，１６３ａ，１６３ｂ  拡張探索範囲（第２探索範囲）
１３０  縮小参照画像
１３１  マクロブロック（仮想マクロブロック）
１３２  探索範囲（第３探索範囲）
Ｃｕ  対象マクロブロック
Ｃ０  仮想マクロブロック
Ｃ１  参照マクロブロック
Ｇｓ  探索開始位置
Ｓｄ  探索方向
ＭＶＳ  第１の統計動きベクトルＭＶＳ
第２の統計動きベクトルＭＶＲ
【図１】
0006394876.tif 000002
【図２】
0006394876.tif 000003
【図３】
0006394876.tif 000004
【図４】
0006394876.tif 000005
【図５】
0006394876.tif 000006
【図６】
0006394876.tif 000007
【図７】
0006394876.tif 000008
【図８】
0006394876.tif 000009
【図９】
0006394876.tif 000010
【図１０】
0006394876.tif 000011
【図１１】
0006394876.tif 000012
【図１２】
0006394876.tif 000013
【図１３】
0006394876.tif 000014
【図１４】
0006394876.tif 000015
【図１５】
0006394876.tif 000016
【図１６】
0006394876.tif 000017
【図１７】
0006394876.tif 000018
【図１８】
0006394876.tif 000019
【図１９】
0006394876.tif 000020
【図２０】
0006394876.tif 000021
【図２１】
0006394876.tif 000022
【図２２】
0006394876.tif 000023
【図２３】
0006394876.tif 000024
【図２４】
0006394876.tif 000025
【図２５】
0006394876.tif 000026
【図２６】
0006394876.tif 000027
【図２７】
0006394876.tif 000028
【図２８】
0006394876.tif 000029
【図２９】
0006394876.tif 000030
【図３０】
0006394876.tif 000031
【図３１】
0006394876.tif 000032
【図３２】
0006394876.tif 000033
【図３３】
0006394876.tif 000034
【図３４】
0006394876.tif 000035
【図３５】
0006394876.tif 000036
【図３６】
0006394876.tif 000037
【図３７】
0006394876.tif 000038
【図３８】
0006394876.tif 000039
【図３９】
0006394876.tif 000040
【図４０】
0006394876.tif 000041
【図４１】
0006394876.tif 000042
【図４２】
0006394876.tif 000043
【図４３】
0006394876.tif 000044