(57)【要約】【課題】探索精度を維持しながらも計算量を大幅に軽減し、高能率に複数のブロックサイズによる動き探索を行って動きベクトルの検出を可能とする。【解決手段】処理対象画像データと複数の参照画像データとを用いて動きベクトルを検出する動きベクトル検出装置であって、処理対象画像データを分割した大ブロックにより第１の参照画像データについて動きベクトル探索を行い、マッチング誤差が最小となる位置で大ブロックをより小さなブロックサイズに分割する。この小ブロックにおけるマッチング誤差により他の参照画像データについての動きベクトル探索に用いるブロックサイズを決定する。【選択図】図１ａ
2008017209.tif 000002
【特許請求の範囲】
【請求項１】
処理対象画像データと複数の参照画像データとを用いて動きベクトルを検出する動きベクトル検出装置であって、
前記処理対象画像データの第１のブロックサイズの第１の画像データとの第１のマッチング誤差が最小となる、前記複数の参照画像データのうち第１の参照画像データの前記第１のブロックサイズの第２の画像データを決定し、該第１の画像データと該第２の画像データとに基づく第１の動きベクトルを検出する第１の動きベクトル検出手段と、
前記第１の画像データを、前記第１のブロックサイズより小さい第２のブロックサイズの複数の第３の画像データに分割し、最小となる前記第１のマッチング誤差から、該複数の第３の画像データのそれぞれに対応する複数の第２のマッチング誤差を抽出する第１の抽出手段と、
前記第１の抽出手段により抽出された前記複数の第２のマッチング誤差に基づいて、前記複数の参照画像データを利用した動きベクトルの検出に用いる第３のブロックサイズを決定する第１の決定手段と
を備えることを特徴とする動きベクトル検出装置。
【請求項２】
前記第３のブロックサイズが第１のブロックサイズと一致する場合に、
前記第１の動きベクトル検出手段は、前記第１のブロックサイズを用いて、前記第１の参照画像データ以外の参照画像データを利用して前記第１の動きベクトルを更に検出することを特徴とする請求項１に記載の動きベクトル検出装置。
【請求項３】
前記第１の決定手段は、前記複数の第２のマッチング誤差のうち、第１の閾値よりも大きい第２のマッチング誤差が存在する場合に、前記第３のブロックサイズを前記第１のブロックサイズを予め定められた条件に従って分割したブロックサイズに決定することを特徴とする請求項１又は２に記載の動きベクトル検出装置。
【請求項４】
前記第３のブロックサイズが、第１のブロックサイズより小さく前記第２のブロックサイズより大きい場合に、
前記処理対象画像データにおける前記第３のブロックサイズの第４の画像データとの第３のマッチング誤差が最小となる、前記複数の参照画像データの前記第３のブロックサイズの第５の画像データを決定し、該第４の画像データと該第５の画像データとに基づく第２の動きベクトルを検出する第２の動きベクトル検出手段を
更に備えることを特徴とする請求項１乃至３のいずれかに記載の動きベクトル検出装置。
【請求項５】
前記第３のブロックサイズが、前記第２のブロックサイズである場合に、
前記第１の画像データにおける前記第２のブロックサイズの第４の画像データとの第３のマッチング誤差が最小となる、前記第１の参照画像データの前記第２のブロックサイズの第５の画像データを決定し、該第４の画像データと該第５の画像データとに基づく第２の動きベクトルを検出する第２の動きベクトル検出手段と、
前記第４の画像データを、前記第２のブロックサイズより小さい第４のブロックサイズの複数の第６の画像データに分割し、最小となる前記第３のマッチング誤差から、該複数の第６の画像データのそれぞれに対応する複数の第４のマッチング誤差を抽出する第２の抽出手段と、
前記第２の抽出手段により抽出された前記複数の第４のマッチング誤差に基づいて、前記複数の参照画像データを利用した動きベクトルの検出に用いる第５のブロックサイズを決定する第２の決定手段と
を更に備えることを特徴とする請求項１乃至３のいずれかに記載の動きベクトル検出装置。
【請求項６】
前記第５のブロックサイズが前記第２のブロックサイズと一致する場合に、
前記第２の動きベクトル検出手段は、前記第２のブロックサイズを用いて、前記第１の参照画像データ以外の参照画像データを利用して前記第２の動きベクトルを更に検出することを特徴とする請求項５に記載の動きベクトル検出装置。
【請求項７】
前記第２の決定手段は、前記複数の第４のマッチング誤差のうち、第２の閾値よりも大きい第４のマッチング誤差が存在する場合に、前記第５のブロックサイズを前記第２のブロックサイズを予め定められた条件に従って分割したブロックサイズに決定することを特徴とする請求項５又は６に記載の動きベクトル検出装置。
【請求項８】
前記第５のブロックサイズが前記第２のブロックサイズと一致しない場合に、
前記処理対象画像データにおける前記第５のブロックサイズの第７の画像データとの第５のマッチング誤差が最小となる、前記複数の参照画像データの前記第５のブロックサイズの第８の画像データを決定し、該第７の画像データと該第８の画像データとに基づく第３の動きベクトルを検出する第３の動きベクトル検出手段を更に備えることを特徴とする請求項５乃至７のいずれかに記載の動きベクトル検出装置。
【請求項９】
前記第１のブロックサイズは、１６画素×１６画素のブロックサイズであって、
前記第２のブロックサイズは、８画素×８画素のブロックサイズであって、
前記第４のブロックサイズは、４画素×４画素のブロックサイズであることを特徴とする請求項５乃至８のいずれかに記載の動きベクトル検出装置。
【請求項１０】
処理対象画像データと複数の参照画像データとを用いて動きベクトルを検出する動きベクトル検出方法であって、
前記処理対象画像データの第１のブロックサイズの第１の画像データとの第１のマッチング誤差が最小となる、前記複数の参照画像データのうち第１の参照画像データの前記第１のブロックサイズの第２の画像データを決定し、該第１の画像データと該第２の画像データとに基づく第１の動きベクトルを検出する第１の動きベクトル検出工程と、
前記第１の画像データを、前記第１のブロックサイズより小さい第２のブロックサイズの複数の第３の画像データに分割し、最小となる前記第１のマッチング誤差から、該複数の第３の画像データのそれぞれに対応する複数の第２のマッチング誤差を抽出する第１の抽出工程と、
前記第１の抽出工程において抽出された前記複数の第２のマッチング誤差に基づいて、前記複数の参照画像データを利用した動きベクトルの検出に用いる第３のブロックサイズを決定する第１の決定工程と
を備えることを特徴とする動きベクトル検出方法。
【請求項１１】
前記第３のブロックサイズが第１のブロックサイズと一致する場合に、前記第１のブロックサイズを用いて、前記第１の参照画像データ以外の参照画像データを利用して前記第１の動きベクトルが更に検出されることを特徴とする請求項１０に記載の動きベクトル検出方法。
【請求項１２】
前記第１の決定工程では、前記複数の第２のマッチング誤差のうち、第１の閾値よりも大きい第２のマッチング誤差が存在する場合に、前記第３のブロックサイズが前記第１のブロックサイズを予め定められた条件に従って分割したブロックサイズに決定されることを特徴とする請求項１０又は１１に記載の動きベクトル検出方法。
【請求項１３】
前記第３のブロックサイズが、第１のブロックサイズより小さく前記第２のブロックサイズより大きい場合に、
前記処理対象画像データにおける前記第３のブロックサイズの第４の画像データとの第３のマッチング誤差が最小となる、前記複数の参照画像データの前記第３のブロックサイズの第５の画像データを決定し、該第４の画像データと該第５の画像データとに基づく第２の動きベクトルを検出する第２の動きベクトル検出工程を
更に備えることを特徴とする請求項１０乃至１２のいずれかに記載の動きベクトル検出方法。
【請求項１４】
前記第３のブロックサイズが、前記第２のブロックサイズである場合に、
前記第１の画像データにおける前記第２のブロックサイズの第４の画像データとの第３のマッチング誤差が最小となる、前記第１の参照画像データの前記第２のブロックサイズの第５の画像データを決定し、該第４の画像データと該第５の画像データとに基づく第２の動きベクトルを検出する第２の動きベクトル検出工程と、
前記第４の画像データを、前記第２のブロックサイズより小さい第４のブロックサイズの複数の第６の画像データに分割し、最小となる前記第３のマッチング誤差から、該複数の第６の画像データのそれぞれに対応する複数の第４のマッチング誤差を抽出する第２の抽出工程と、
前記第２の抽出工程において抽出された前記複数の第４のマッチング誤差に基づいて、前記複数の参照画像データを利用した動きベクトルの検出に用いる第５のブロックサイズを決定する第２の決定工程と
を更に備えることを特徴とする請求項１０乃至１２のいずれかに記載の動きベクトル検出方法。
【請求項１５】
前記第５のブロックサイズが前記第２のブロックサイズと一致する場合に、前記第２のブロックサイズを用いて、前記第１の参照画像データ以外の参照画像データを利用して前記第２の動きベクトルが更に検出されることを特徴とする請求項１４に記載の動きベクトル検出方法。
【請求項１６】
前記第２の決定工程では、前記複数の第４のマッチング誤差のうち、第２の閾値よりも大きい第４のマッチング誤差が存在する場合に、前記第５のブロックサイズが前記第２のブロックサイズを予め定められた条件に従って分割したブロックサイズに決定されることを特徴とする請求項１４又は１５に記載の動きベクトル検出方法。
【請求項１７】
前記第５のブロックサイズが前記第２のブロックサイズと一致しない場合に、
前記処理対象画像データにおける前記第５のブロックサイズの第７の画像データとの第５のマッチング誤差が最小となる、前記複数の参照画像データの前記第５のブロックサイズの第８の画像データを決定し、該第７の画像データと該第８の画像データとに基づく第３の動きベクトルを検出する第３の動きベクトル検出工程を更に備えることを特徴とする請求項１４乃至１６のいずれかに記載の動きベクトル検出方法。
【請求項１８】
前記第１のブロックサイズは、１６画素×１６画素のブロックサイズであって、
前記第２のブロックサイズは、８画素×８画素のブロックサイズであって、
前記第４のブロックサイズは、４画素×４画素のブロックサイズであることを特徴とする請求項１４乃至１７のいずれかに記載の動きベクトル検出方法。
【請求項１９】
請求項１０乃至１７のいずれかに記載の動きベクトル検出方法をコンピュータに実行させるためのコンピュータプログラム。
【請求項２０】
請求項１９に記載のコンピュータプログラムを記憶したコンピュータで読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動きベクトル検出装置、動きベクトル検出方法、コンピュータプログラム及び記憶媒体に関する。
【背景技術】
【０００２】
近年、マルチメディアに関連する情報のデジタル化が急進しており、それに伴い映像情報の高画質化に向けた要求が高まっている。具体的な例として放送メディアの従来の７２０×４８０画素のSDから、１９２０×１０８０画素のHDに移行が行われつつあることを挙げることが出来る。しかしながら、この高画質への要求は同時にデジタルデータの増大を引き起こし、従来の性能を上回る圧縮符号化技術及び復号化技術が求められている。
【０００３】
これらの要求に対し、ＩＴＵ−Ｔ  ＳＧ１６やＩＳＯ／ＩＥＣ  ＪＴＣ１／ＳＣ２９／ＷＧ１１の活動で画像間の相関を利用したフレーム間予測を用いた符号化圧縮方式の標準化作業が進められている。
【０００４】
この中でも、現状最も高能率符号化を実現しているといわれる符号化方式にＨ．２６４／ＭＰＥＧ−４  ＰＡＲＴ１０（ＡＶＣ）（以下、Ｈ．２６４と呼ぶ）がある。Ｈ．２６４の符号化・復号化の仕様については、例えば特許文献１に開示されている。
【０００５】
また、Ｈ．２６４で新たに導入された技術のひとつとして、図２に示すような予測符号化を行う画素ブロックのパーティションを複数種用意し、細かい画素単位の動き量を検出し、予測誤差が最小のものを選択して符号量をより低減する技術がある。このようなパーティションは、マクロブロックパーティションと呼ばれる。
【０００６】
ここで、図２を用いてマクロブロックパーティションについて詳細に説明する。Ｈ．２６４では、図２(i)に示すようにＭＰＥＧ２で用いられているサイズである１６×１６画素を最大のブロックサイズを有するマクロブロックタイプとする。その上で、更に図２の（ii）から（iv）を含めた合計４種類の中から予測符号化に使用するマクロブロックパーティションを選ぶことが可能である。なお、このマクロブロックパーティションの選択は、予測符号化に使用するマクロブロックサイズを、１６×１６画素、１６×８画素、８×１６画素、８×８画素のいずれかから選択することと等価である。
【０００７】
更に、図２（iv）に示す８×８画素で構成されるマクロブロックについては、それぞれより細かいサブマクロブロックに分割できる。ここでは、図２（v）から(viii)に示すように、最小４×４画素のブロックサイズを有するサブマクロブロックを使用して、４種類のサブマクロブロックパーティションのいずれかに分割をすることが可能である。この場合、サブマクロブロックパーティションの選択は、予測符号化に使用するサブマクロブロックサイズを、８×８画素、８×４画素、４×８画素、４×４画素のいずれかから選択することと等価である。
【０００８】
つまり、予測符号化に使用するマクロブロックパーティションは、全部で１９種類の中から選ぶことになる。このうち、３種類は、サブマクロブロックパーティションの対象とならないマクロブロックパーティション（図２（i）から（iii））の数である。また、残りの１６種類は、図２（iv）においてサブマクロブロックパーティションの対象となるマクロブロック数：４と、図２(v)から(viii)のサブマクロブロックパーティション数：４との積による。
【０００９】
また、Ｈ．２６４では、図５に示すように符号化対象フレーム（ＣＦ）内のマクロブロック毎に複数の参照フレーム（ＲＦ１〜ＲＦ５）から符号化効率の良い参照フレームを選択し、ブロック毎にどのフレームを用いるかを指定できる。よって、同一の符号化対象フレームＣＦ内のマクロブロックであっても、異なる参照フレームが選択される場合がある。このように、Ｈ．２６４では、複数の参照フレームを用いて、動きベクトル検出のための複数の探索階層が設定されることとなる。
【００１０】
この結果、より細かい画像単位で動き情報を探索し、動き情報の精度の向上を実現している。
【特許文献１】特開２００５−１６７７２０号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、ＭＰＥＧ２がマクロブロック１種類しか有しないのに比べ、Ｈ．２６４は、１９種類ものパーティション数を有し、パーティションに含まれるブロックの全てについて動きベクトルの評価を行えば膨大な演算が必要となる。また、Ｈ．２６４では、複数の探索階層（複数の参照フレーム）を用いて動きベクトル検出を行えるため、各探索階層について全てのパーティションの評価を行おうとすれば、やはり膨大な演算が必要となる。
【００１２】
また、ビデオカムコーダなどのモバイル機器の場合には、演算負荷の増大は駆動するバッテリー消費量の増大に結びつき、撮影時間が短くなってしまう問題がある。
【００１３】
本発明は、このような問題点に鑑みてなされたものであり、探索精度を維持しながらも計算量を大幅に軽減し、高能率に複数のブロックサイズによる動き探索を行って動きベクトルの検出を可能とすることを目的とする。
【課題を解決するための手段】
【００１４】
上記課題を解決するために、本発明は、処理対象画像データと複数の参照画像データとを用いて動きベクトルを検出する動きベクトル検出装置であって、前記処理対象画像データの第１のブロックサイズの第１の画像データとの第１のマッチング誤差が最小となる、前記複数の参照画像データのうち第１の参照画像データの前記第１のブロックサイズの第２の画像データを決定し、該第１の画像データと該第２の画像データとに基づく第１の動きベクトルを検出する第１の動きベクトル検出手段と、前記第１の画像データを、前記第１のブロックサイズより小さい第２のブロックサイズの複数の第３の画像データに分割し、最小となる前記第１のマッチング誤差から、該複数の第３の画像データのそれぞれに対応する複数の第２のマッチング誤差を抽出する第１の抽出手段と、前記第１の抽出手段により抽出された前記複数の第２のマッチング誤差に基づいて、前記複数の参照画像データを利用した動きベクトルの検出に用いる第３のブロックサイズを決定する第１の決定手段とを備えることを特徴とする。
【発明の効果】
【００１５】
本発明によれば、探索精度を維持しながらも計算量を大幅に軽減し、高能率に複数のブロックサイズによる動き探索を行って動きベクトルを検出することが可能となる。
【発明を実施するための最良の形態】
【００１６】
以下に、添付する図面を参照して、本発明の実施形態を説明する。
【００１７】
まず、図１ａに、本発明の実施形態に係る画像処理装置としての画像圧縮符号化装置の全体構成の一例を示す。
【００１８】
この動画像圧縮符号化装置は、カメラ部２００、減算器２００１、整数変換部２００２、量子化部２００３、エントロピー符号化部２００４、逆量子化部２００５、逆整数変換部２００６、加算器２００７を有する。また、フレームメモリ２００８及び２０１２、イントラ予測部２００９、スイッチ２０１０及び２０１５、デブロッキングフィルタ２０１１、インター予測部２０１３、動き検出部２０１４を更に有する。そして、カメラ部２００から入力された画像データを分割することによりブロックを構成し、ブロック単位に符号化処理を行い符号化データを出力する。続いて、Ｈ．２６４の符号化処理について説明する。
【００１９】
まず、減算器２００１はカメラ部からの入力される画像データから予測画像データを減算し画像残差データを出力する。予測画像データの生成については後述する。整数変換部２００２は、減算器２００１から出力された画像残差データを、ＤＣＴ変換等により直交変換処理して変換係数を出力する。そして、量子化部２００３は上記変換係数を所定の量子化パラメータを用いて量子化する。エントロピー符号化部２００４は、量子化部２００３で量子化された変換係数を入力し、これをエントロピー符号化して符号化データとして出力する。
【００２０】
一方、量子化部２００３で量子化された変換係数は予測画像データの生成にも使われる。逆量子化部２００５は、量子化部２００３で量子化された変換係数を逆量子化する。さらに、逆整数変換部２００６は逆量子化部２００５で逆量子化された変換係数を、逆ＤＣＴ変換等により逆整数変換し、復号画像残差データとして出力する。加算器２００７は、復号画像残差データと予測画像データとを加算し、再構成画像データとして出力する。
【００２１】
再構成画像データはフレームメモリ２００８に記録されるが、デブロッキングフィルタ処理を行う場合はデブロッキングフィルタ２０１１を介して記録される。また、デブロッキングフィルタ処理を行わない場合はデブロッキングフィルタ２０１１を介さずフレームメモリ２０１２に記録される。スイッチ２０１０は、デブロッキングフィルタ処理を行うか行わないか選択する選択部である。再構成画像データの中で、以降の予測で参照される可能性があるデータは、フレームメモリ２００８または２０１２に参照フレームデータとして暫くの期間保存される。また、デブロッキングフィルタ２０１１はノイズを除去する為に用いられる。
【００２２】
イントラ予測部２００９は、フレームメモリ２００８に記録された画像データを用いてフレーム内予測処理を行い、予測画像データを生成する。また、インター予測部２０１３はフレームメモリ２０１２に記録された参照画像データを用いて動き検出部２０１４によって検出された動きベクトル情報に基づいてフレーム間予測処理を行い予測画像データを生成する。動き検出部２０１４は、フレームメモリ２０１２に記録された参照画像データを用いて、入力画像データにおける動きベクトルを検出し、検出した動きベクトル情報をインター予測部２０１３とエントロピー符号化部２００４へ出力する。スイッチ２０１５は、イントラ予測、インター予測のどちらを用いるか選択するための選択部である。イントラ予測部２００９からの出力とインター予測部２０１３からの出力の一方を選択して、選択された予測画像データを減算器２００１、加算器２００７へ出力する。
【００２３】
次に、本実施形態に対応する動きベクトル検出装置としての動き検出部の具体的構成及びその動作を説明する。図１ｂは、本実施形態に対応する動き検出部の具体的構成の一例を示す図である。また、図３は、本実施形態に対応する動き検出部における、入力画像データ中の１つのマクロブロックについて、動きベクトルを検出し、マクロブロックパーティションを決定する処理の一例を示すフローチャートである。なお、本実施例では符号化方式としてＨ．２６４の場合を例にあげて説明するが、本発明は他の符号化方式に適用してもよい。
【００２４】
入力端子１には、動きベクトル検出対象（処理対象）の画像信号である入力画像データが、カメラ部２００から大ブロック動きベクトル検出部３に入力される。また、入力端子２には、既に符号化され局部復号化された画像信号が参照画像データとしてフレームメモリ２０１２から入力され、参照画像記憶部４に記憶される。
【００２５】
ステップＳ１００では、探索階層が最上位の探索階層に設定される。本実施形態では、複数の探索階層、即ち複数の参照フレームについて動きベクトル検出を行うこととし、入力画像データの直近に符号化された参照フレームを「最上位の探索階層」とする。また、参照フレームのうち、最も符号化された時期が古いものを「最下位の探索階層」という。探索階層を更新する場合には、「最上位の探索階層」から「最下位の探索階層」まで、符号化時期の順に更新していく。例えば、図５の場合、ＲＦ１は「最上位の探索階層」に相当し、ＲＦ５は「最下位の探索階層」に相当する。また、探索階層を更新する場合には、ＲＦ１、ＲＦ２、ＲＦ３、ＲＦ４、ＲＦ５の順で更新される。なお、図５では、Ｈ．２６４の規格に従い探索階層を５階層としているが、これはあくまで例示であって、階層数はこれに限定されるものではない。
【００２６】
次に、ステップＳ１０１では、マッチング位置の設定処理が行われる。ここで、マッチング位置の設定とは、符号化処理対象フレームである入力画像データについて、参照フレーム（探索階層）における参照画像データの位置の決定を意味する。仮に、以前の探索階層において、参照フレームと入力画像データとの間に動きベクトルが検出済みでない場合には、初期動きベクトルとして零を設定し、入力画像データにおけるブロック位置と同じブロック位置にマッチング位置を設定する。この際、大ブロック探索モードをオフに設定する。大ブロック探索モードとは、１６×１６画素サイズのマクロブロック（大ブロック）での探索を下位の探索階層を通じて行うモードである。この大ブロック探索モードがオンに設定されている場合には、これ以降中ブロック或いは小ブロックによる探索は行われない。また、より上位の探索階層で動きベクトルが検出され、かつ、大ブロック探索モードがオンになっている場合には、当該動きベクトルを初期動きベクトルとして、マッチング位置を設定する。
【００２７】
次に、ステップＳ１０２では、大ブロック動きベクトル検出部３が、マッチング誤差MAEbigを算出する。このマッチング誤差MAEbigは、入力端子１からの入力画像データの１６×１６画素サイズのマクロブロック（大ブロック）と参照画像記憶部４から入力される大ブロックの参照画像データとについて算出される。マッチング誤差は、例えば、比較される両ブロックの画素値の差分を求めることにより算出することができる。マッチング誤差MAEbigは各探索階層について算出され、最終的に探索範囲（全探索階層）におけるマッチング誤差MAEbigが最も小さくなる時の動きベクトルと、その時のマッチング誤差とが求められる。この動きベクトルを「最終的な動きベクトル」という。
【００２８】
次に、ステップＳ１０３では、大ブロック探索モードがオンに設定されているか否かを判定する。もし、大ブロック探索モードがオンならば（ステップＳ１０３において「ＹＥＳ」）、ステップＳ１１８に移行する。ステップＳ１１８では、探索階層が最下位の探索階層か否かを判定する。もし最下位の探索階層と判定された場合には（ステップＳ１１８において「ＹＥＳ」）、ステップＳ１１７へ移行する。ステップＳ１１７では、最終マクロブロックパーティション・最終動きベクトル決定部１１が、マクロブロックパーティションが大ブロックであるという情報及び最終的な動きベクトルを、大ブロック動きベクトル検出部３から受信する。送信する。一方、最下位の探索階層でないと判定された場合には（ステップＳ１１８において「ＮＯ」）、ステップＳ１１９に移行して、探索階層を１つ更新し、一つ下位の探索階層についてステップＳ１０１からの処理を継続する。
【００２９】
一方、大ブロック探索モードがオフならば（ステップＳ１０３において「ＮＯ」）、ステップＳ１０４に移行する。ステップＳ１０４では、ステップＳ１０２で求めた動きベクトルとマッチング誤差MAEbigとを中ブロック誤差抽出部５に送信する。
【００３０】
中ブロック誤差抽出部５は、図４（ａ）に示すように大ブロック４００を８×８画素サイズのマクロブロック４０１から４０４（以下、中ブロックと呼ぶ）に分割した後、各中ブロックのマッチング誤差を抽出する。ここで抽出されるマッチング誤差は、中ブロック４０１につきMAEmid(0)、中ブロック４０２につきMAEmid(1)、中ブロック４０３につきMAEmid(2)、中ブロック４０４につきMAEmid(3)とする。抽出された各マッチング誤差は、第一マクロブロックパーティション決定部６に送信される。なお、図４（ａ）は大ブロック４００のマッチング誤差MAEbigが120の時、各中ブロックのマッチング誤差がMAEmid(0)＝10、MAEmid(1)=10、MAEmid(2)=30、MAEmid(3)=70の例を示している。
【００３１】
次に、ステップＳ１０５において、第一マクロブロック（ＭＢ）パーティション決定部６は、現在の探索階層における各中ブロックのマッチング誤差と閾値とを比較し、以下のような条件でマクロブロックパーティションを決定する。ここでは、図２の(i)から（iv）のいずれかのマクロブロックパーティションが選択される。即ち、ここでは、１６×１６画素、１６×８画素、８×１６画素、又は、８×８画素のいずれかのブロックサイズが選択されることとなる。なお、以下において、閾値ThlとThmとの間には、Thl＜Thmの関係が成立する。
【００３２】
（条件１）
MAEmid(0)＜Thl, MAEmid(1)＜Thl, MAEmid(2)＜Thl, MAEmid(3)＜Thl  のとき、
マクロブロックパーティションを図２の（ｉ）にする。
【００３３】
（条件２）
MAEmid(0)＜Thl, MAEmid(1)＜Thl, MAEmid(2)＜Thl, MAEmid(3)≧Thl のとき、
MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）及び（ｉｉｉ）にする。
MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉｉ）にする。
MAEmid(1)+MAEmid(3)≧Thm, MAEmid(2)+MAEmid(3)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）にする。
MAEmid(1)+MAEmid(3)≧Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｖ）にする。
【００３４】
（条件３）
MAEmid(0)＜Thl, MAEmid(1)＜Thl, MAEmid(2)≧Thl, MAEmid(3)＜Thl のとき、
MAEmid(0)+MAEmid(2)＜Thm, MAEmid(2)+MAEmid(3)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）及び（ｉｉｉ）にする。
MAEmid(0)+MAEmid(2)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉｉ）にする。
MAEmid(0)+MAEmid(2)≧Thm, MAEmid(2)+MAEmid(3)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）にする。
MAEmid(0)+MAEmid(2)≧Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｖ）にする。
【００３５】
（条件４）
MAEmid(0)＜Thl, MAEmid(1)＜Thl, MAEmid(2)≧Thl, MAEmid(3)≧Thl のとき、
マクロブロックパーティションを図２の（ｉｉ）にする。
【００３６】
（条件５）
MAEmid(0)＜Thl, MAEmid(1)≧Thl, MAEmid(2)＜Thl, MAEmid(3)＜Thl のとき、
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(1)+MAEmid(3)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）及び（ｉｉｉ）にする。
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(1)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）にする。
MAEmid(1)+MAEmid(0)≧Thm, MAEmid(1)+MAEmid(3)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉｉ）にする。
MAEmid(1)+MAEmid(0)≧Thm, MAEmid(1)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｖ）にする。
【００３７】
（条件６）
MAEmid(0)＜Thl, MAEmid(1)≧Thl, MAEmid(2)＜Thl, MAEmid(3)≧Thl のとき、
マクロブロックパーティションを図２の（ｉｉｉ）にする。
【００３８】
（条件７）
MAEmid(0)＜Thl, MAEmid(1)≧Thl, MAEmid(2)≧Thl, MAEmid(3)＜Thl のとき、
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(0)+MAEmid(2)＜Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）及び（ｉｉｉ）にする。
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(0)+MAEmid(2)≧Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）にする。
MAEmid(1)+MAEmid(0)≧Thm, MAEmid(0)+MAEmid(2)＜Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉｉ）にする。
それ以外の時
マクロブロックパーティションを図２の（ｉｖ）にする。
【００３９】
（条件８）
MAEmid(0)＜Thl, MAEmid(1)≧Thl, MAEmid(2)≧Thl, MAEmid(3)≧Thl のとき、
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(0)+MAEmid(2)＜Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）及び（ｉｉｉ）にする。
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(0)+MAEmid(2)≧Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）にする。
MAEmid(1)+MAEmid(0)≧Thm, MAEmid(0)+MAEmid(2)＜Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉｉ）にする。
それ以外の時
マクロブロックパーティションを図２の（ｉｖ）にする。
【００４０】
（条件９）
MAEmid(0)≧Thl, MAEmid(1)＜Thl, MAEmid(2)＜Thl, MAEmid(3)＜Thl のとき、
MAEmid(0)+MAEmid(1)＜Thm, MAEmid(0)+MAEmid(2)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）及び（ｉｉｉ）にする。
MAEmid(0)+MAEmid(1)＜Thm, MAEmid(0)+MAEmid(2)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）にする。
MAEmid(0)+MAEmid(1)≧Thm, MAEmid(0)+MAEmid(2)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉｉ）にする。
MAEmid(0)+MAEmid(1)≧Thm, MAEmid(0)+MAEmid(2)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｖ）にする。
【００４１】
（条件１０）
MAEmid(0)≧Thl, MAEmid(1)＜Thl, MAEmid(2)＜Thl, MAEmid(3)≧Thl のとき、
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(0)+MAEmid(2)＜Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）及び（ｉｉｉ）にする。
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(0)+MAEmid(2)≧Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）にする。
MAEmid(1)+MAEmid(0)≧Thm, MAEmid(0)+MAEmid(2)＜Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉｉ）にする。
それ以外の時
マクロブロックパーティションを図２の（ｉｖ）にする。
【００４２】
（条件１１）
MAEmid(0)≧Thl, MAEmid(1)＜Thl, MAEmid(2)≧Thl, MAEmid(3)＜Thl のとき、
マクロブロックパーティションを図２の（ｉｉ）にする。
【００４３】
（条件１２）
MAEmid(0)≧Thl, MAEmid(1)＜Thl, MAEmid(2)≧Thl, MAEmid(3)≧Thl のとき、
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(0)+MAEmid(2)＜Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）及び（ｉｉｉ）にする。
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(0)+MAEmid(2)≧Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）にする。
MAEmid(1)+MAEmid(0)≧Thm, MAEmid(0)+MAEmid(2)＜Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉｉ）にする。
それ以外の時
マクロブロックパーティションを図２の（ｉｖ）にする。
【００４４】
（条件１３）
MAEmid(0)≧Thl, MAEmid(1)≧Thl, MAEmid(2)＜Thl, MAEmid(3)＜Thl のとき、
マクロブロックパーティションを図２の（ｉｉ）にする。
【００４５】
（条件１４）
MAEmid(0)≧Thl, MAEmid(1)≧Thl, MAEmid(2)＜Thl, MAEmid(3)≧Thl のとき、
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(0)+MAEmid(2)＜Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）及び（ｉｉｉ）にする。
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(0)+MAEmid(2)≧Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）にする。
MAEmid(1)+MAEmid(0)≧Thm, MAEmid(0)+MAEmid(2)＜Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉｉ）にする。
それ以外の時
マクロブロックパーティションを図２の（ｉｖ）にする。
【００４６】
（条件１５）
MAEmid(0)≧Thl, MAEmid(1)≧Thl, MAEmid(2)≧Thl, MAEmid(3)＜Thl のとき、
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(0)+MAEmid(2)＜Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）及び（ｉｉｉ）にする。
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(0)+MAEmid(2)≧Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）にする。
MAEmid(1)+MAEmid(0)≧Thm, MAEmid(0)+MAEmid(2)＜Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉｉ）にする。
それ以外の時
マクロブロックパーティションを図２の（ｉｖ）にする。
【００４７】
（条件１６）
MAEmid(0)≧Thl, MAEmid(1)≧Thl, MAEmid(2)≧Thl, MAEmid(3)≧Thl のとき、
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(0)+MAEmid(2)＜Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)＜Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）及び（ｉｉｉ）にする。
MAEmid(1)+MAEmid(0)＜Thm, MAEmid(0)+MAEmid(2)≧Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉ）にする。
MAEmid(1)+MAEmid(0)≧Thm, MAEmid(0)+MAEmid(2)＜Thm, MAEmid(1)+MAEmid(3)＜Thm, MAEmid(2)+MAEmid(3)≧Thm のとき、
マクロブロックパーティションを図２の（ｉｉｉ）にする。
それ以外の時
マクロブロックパーティションを図２の（ｉｖ）にする。
【００４８】
ここで、例えばThl=15、Thm＝40とすると図４（ａ）の例では、上記の（条件４）の場合が適用され、マクロブロックパーティションとして図２の（ｉｉ）が選択される。なお、マクロブロックパーティションが図２の（ｉ）になった場合には、大ブロック探索モードがオンに設定される。また、図２の（ｉ）以外のマクロブロックパーティションが選択された場合は、大ブロック探索モードの設定はオフのまま維持される。
【００４９】
次に、ステップＳ１０６では、大ブロック探索モードがオンに設定されているか否かを再度判定する。上記のように、ステップＳ１０５において、マクロブロックパーティションとして図２の（ｉ）のタイプが選択された場合には大ブロック探索モードがオンに設定される。そこで、大ブロック探索モードがオンに設定されていると判定された場合には（ステップＳ１０６において「ＹＥＳ」）、ステップＳ１２０に移行して、探索階層を１つ更新してステップＳ１０１に戻る。ステップＳ１０１では、ステップＳ１０２において大ブロック動きベクトル検出部３で既に算出済の動きベクトルを用いて新たなマッチング位置を設定し、最下位階層まで大ブロックでの探索を繰り返す。
【００５０】
このように、下位階層の探索で用いるマクロブロックパーティションを限定することで、全てのマクロブロックパーティションで探索を行った場合に比べ、演算処理を大幅に削減することができる。
【００５１】
一方、大ブロック探索モードがオフに設定されていると判定された場合には（ステップＳ１０６において「ＮＯ」）、ステップＳ１０７に移行する。ステップＳ１０７では、中ブロック動きベクトル検出部７が、第一マクロブロックパーティション決定部６からマクロブロックパーティションと動きベクトルを取得し、該動きベクトルを用いてマッチング位置を決定する。
【００５２】
次に、ステップＳ１０８では、取得したマクロブロックパーティションを用いて、各ブロック毎に参照画像記憶部４から入力される参照画像データとのマッチング誤差MAEmidを算出する。マッチング誤差MAEmidは各探索階層について算出され、最終的に探索範囲（全探索階層）におけるマッチング誤差MAEmidが最も小さくなる時の動きベクトルと、その時のマッチング誤差とが求められる。この動きベクトルを「最終的な動きベクトル」という。なお、このとき、マクロブロックパーティションとして図２（ｉｖ）以外が選択されている場合には、中ブロック探索モードをオンに設定する。一方、図２（ｉｖ）が選択されている場合には、中ブロック探索モードをオフに設定する。
【００５３】
次に、ステップＳ１０９では、中ブロック探索モードがオンに設定されているか否かを判定する。中ブロック探索モードとは、「中ブロック」での探索を下位の探索階層を通じて行うモードである。この中ブロック探索モードがオンに設定されている場合には、これ以降大ブロック或いは小ブロックによる探索は行われない。
【００５４】
ステップＳ１０９で、中ブロック探索モードがオンに設定されていると判定された場合には（ステップＳ１０９において「ＹＥＳ」）、ステップＳ１２１に移行する。ステップＳ１２１では、探索階層が最下位の探索階層か否かを判定する。もし最下位の探索階層と判定された場合には（ステップＳ１２１において「ＹＥＳ」）、ステップＳ１１７へ移行する。ステップＳ１１７では、最終マクロブロックパーティション・最終動きベクトル決定部１１が、そのときのマクロブロックパーティションの情報と最終的な動きベクトルとを中ブロック動きベクトル検出部７から受信する。一方、最下位の探索階層でないと判定された場合には（ステップＳ１２１において「ＮＯ」）、ステップＳ１２２に移行して、探索階層を１つ更新し、一つ下位の探索階層についてステップＳ１０７からの処理を継続する。
【００５５】
これにより、下位階層の探索で用いるマクロブロックパーティションを限定することで、全てのマクロブロックパーティションで探索を行った場合に比べ、演算処理を大幅に削減することができる。
【００５６】
ステップＳ１０９で、中ブロック探索モードがオフに設定されていると判定された場合には（ステップＳ１０９において「ＮＯ」）、ステップＳ１１０に移行する。ステップＳ１１０では、中ブロック誤差抽出部５で用いられたマクロブロックパーティションが図２（ｉｖ）のパターンであるか否かを判定する。もし、図２（ｉｖ）のパターンでないと判定された場合は（ステップＳ１１０において「ＮＯ」）、ステップＳ１２１に移行して上記の処理を行う。一方、図２（ｉｖ）のパターンであると判定された場合には（ステップＳ１１０において「ＹＥＳ」）、ステップＳ１１１に移行する。
【００５７】
ステップＳ１１１では、小ブロック誤差抽出部８が、中ブロック動きベクトル探索部７から、中ブロックでの各マッチング誤差と動きベクトルを取得する。
【００５８】
小ブロック誤差抽出部８は、図４（ｂ）に示すように８×８画素のマクロブロック４１０を更に４×４画素サイズのサブマクロブロック４１１から４１４（以下、小ブロックと呼ぶ）に分割した後、各小ブロックごとのマッチング誤差を抽出する。ここで抽出されるマッチング誤差は、小ブロック４１１につきMAElow(0)、小ブロック４１２につきMAElow(1)、小ブロック４１３につきMAElow(2)、小ブロック４１４につきMAElow(3)とする。抽出された各マッチング誤差は、サブマクロブロックパーティション決定部９に送信される。なお、図４（ｂ）はマクロブロック４１０のマッチング誤差MAElowが30の時、各小ブロックのマッチング誤差がMAElow(0)＝3、MAElow(1)=3、MAElow(2)=7、MAElow(3)=17の例を示している。
【００５９】
なお、ステップＳ１１１移行の処理は、図２（ｉｖ）の８×８画素のマクロブロックの１つずつについて、それぞれ実行される。これにより、各マクロブロック毎に、サブマクロブロックパーティションが決定され、決定されたサブマクロブロックパーティションに応じた動きベクトルの検出が行われる。
【００６０】
ステップＳ１１２においてサブマクロブロック（ＳＭＢ）パーティション決定部９は、現在の探索階層における各小ブロックのマッチング誤差と閾値を比較し、以下のような条件でサブマクロブロックパーティションを決定する。ここでは、図２の(v)から（viii）のいずれかのサブマクロブロックパーティションが選択される。即ち、ここでは、８×８画素、８×４画素、４×８画素、又は、４×４画素のいずれかのブロックサイズが選択されることとなる。なお、以下において、閾値ThllとThmlとの間には、Thll＜Thmlの関係が成立する。
【００６１】
（条件１’）
MAElow(0)＜Thll, MAElow(1)＜Thll, MAElow(2)＜Thll, MAElow(3)＜Thll のとき、
サブマクロブロックパーティションを図２の（ｖ）にする。
【００６２】
（条件２’）
MAElow(0)＜Thll, MAElow(1)＜Thll, MAElow(2)＜Thll, MAElow(3)≧Thll のとき、
MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）及び（ｖｉｉ）にする。
MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉ）にする。
MAElow(1)+MAElow(3)≧Thml, MAElow(2)+MAElow(3)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）にする。
MAElow(1)+MAElow(3)≧Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉｉ）にする。
【００６３】
（条件３’）
MAElow(0)＜Thll, MAElow(1)＜Thll, MAElow(2)≧Thll, MAElow(3)＜Thll のとき、
MAElow(0)+MAElow(2)＜Thml, MAElow(2)+MAElow(3)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）及び（ｖｉｉ）にする。
MAElow(0)+MAElow(2)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉ）にする。
MAElow(0)+MAElow(2)≧Thml, MAElow(2)+MAElow(3)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）にする。
MAElow(0)+MAElow(2)≧Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉｉ）にする。
【００６４】
（条件４’）
MAElow(0)＜Thll, MAElow(1)＜Thll, MAElow(2)≧Thll, MAElow(3)≧Thll のとき、
サブマクロブロックパーティションを図２の（ｖｉ）にする。
【００６５】
（条件５’）
MAElow(0)＜Thll, MAElow(1)≧Thll, MAElow(2)＜Thll, MAElow(3)＜Thll のとき、
MAElow(1)+MAElow(0)＜Thml, MAElow(1)+MAElow(3)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）及び（ｖｉｉ）にする。
MAElow(1)+MAElow(0)＜Thml, MAElow(1)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）にする。
MAElow(1)+MAElow(0)≧Thml, MAElow(1)+MAElow(3)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉ）にする。
MAElow(1)+MAElow(0)≧Thml, MAElow(1)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉｉ）にする。
【００６６】
（条件６’）
MAElow(0)＜Thll, MAElow(1)≧Thll, MAElow(2)＜Thll, MAElow(3)≧Thll のとき、
サブマクロブロックパーティションを図２の（ｖｉｉ）にする。
【００６７】
（条件７’）
MAElow(0)＜Thll, MAElow(1)≧Thll, MAElow(2)≧Thll, MAElow(3)＜Thll のとき、
MAElow(1)+MAElow(0)＜Thml, MAElow(0)+MAElow(2)＜Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）及び（ｖｉｉ）にする。
MAElow(1)+MAElow(0)＜Thml, MAElow(0)+MAElow(2)≧Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）にする。
MAElow(1)+MAElow(0)≧Thml, MAElow(0)+MAElow(2)＜Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉ）にする。
それ以外の時
サブマクロブロックパーティションを図２の（ｖｉｉｉ）にする。
【００６８】
（条件８’）
MAElow(0)＜Thll, MAElow(1)≧Thll, MAElow(2)≧Thll, MAElow(3)≧Thll のとき、
MAElow(1)+MAElow(0)＜Thml, MAElow(0)+MAElow(2)＜Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）及び（ｖｉｉ）にする。
MAElow(1)+MAElow(0)＜Thml, MAElow(0)+MAElow(2)≧Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）にする。
MAElow(1)+MAElow(0)≧Thml, MAElow(0)+MAElow(2)＜Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉ）にする。
それ以外の時
サブマクロブロックパーティションを図２の（ｖｉｉｉ）にする。
【００６９】
（条件９’）
MAElow(0)≧Thll, MAElow(1)＜Thll, MAElow(2)＜Thll, MAElow(3)＜Thll のとき、
MAElow(0)+MAElow(1)＜Thml, MAElow(0)+MAElow(2)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）及び（ｖｉｉ）にする。
MAElow(0)+MAElow(1)＜Thml, MAElow(0)+MAElow(2)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）にする。
MAElow(0)+MAElow(1)≧Thml, MAElow(0)+MAElow(2)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉ）にする。
MAElow(0)+MAElow(1)≧Thml, MAElow(0)+MAElow(2)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉｉ）にする。
【００７０】
（条件１０’）
MAElow(0)≧Thll, MAElow(1)＜Thll, MAElow(2)＜Thll, MAElow(3)≧Thll のとき、
MAElow(1)+MAElow(0)＜Thml, MAElow(0)+MAElow(2)＜Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）及び（ｖｉｉ）にする。
MAElow(1)+MAElow(0)＜Thml, MAElow(0)+MAElow(2)≧Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）にする。
MAElow(1)+MAElow(0)≧Thml, MAElow(0)+MAElow(2)＜Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉ）にする。
それ以外の時
サブマクロブロックパーティションを図２の（ｖｉｉｉ）にする。
【００７１】
（条件１１’）
MAElow(0)≧Thll, MAElow(1)＜Thll, MAElow(2)≧Thll, MAElow(3)＜Thll のとき、
サブマクロブロックパーティションを図２の（ｖｉ）にする。
【００７２】
（条件１２’）
MAElow(0)≧Thll, MAElow(1)＜Thll, MAElow(2)≧Thll, MAElow(3)≧Thll のとき、
MAElow(1)+MAElow(0)＜Thml, MAElow(0)+MAElow(2)＜Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）及び（ｖｉｉ）にする。
MAElow(1)+MAElow(0)＜Thml, MAElow(0)+MAElow(2)≧Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）にする。
MAElow(1)+MAElow(0)≧Thml, MAElow(0)+MAElow(2)＜Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉ）にする。
それ以外の時
サブマクロブロックパーティションを図２の（ｖｉｉｉ）にする。
【００７３】
（条件１３’）
MAElow(0)≧Thll, MAElow(1)≧Thll, MAElow(2)＜Thll, MAElow(3)＜Thll のとき、
サブマクロブロックパーティションを図２の（ｖｉ）にする。
【００７４】
（条件１４’）
MAElow(0)≧Thll, MAElow(1)≧Thll, MAElow(2)＜Thll, MAElow(3)≧Thll のとき、
MAElow(1)+MAElow(0)＜Thml, MAElow(0)+MAElow(2)＜Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）及び（ｖｉｉ）にする。
MAElow(1)+MAElow(0)＜Thml, MAElow(0)+MAElow(2)≧Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）にする。
MAElow(1)+MAElow(0)≧Thml, MAElow(0)+MAElow(2)＜Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉ）にする。
それ以外の時
サブマクロブロックパーティションを図２の（ｖｉｉｉ）にする。
【００７５】
（条件１５’）
MAElow(0)≧Thll, MAElow(1)≧Thll, MAElow(2)≧Thll, MAElow(3)＜Thll のとき、
MAElow(1)+MAElow(0)＜Thml, MAElow(0)+MAElow(2)＜Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）及び（ｖｉｉ）にする。
MAElow(1)+MAElow(0)＜Thml, MAElow(0)+MAElow(2)≧Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）にする。
MAElow(1)+MAElow(0)≧Thml, MAElow(0)+MAElow(2)＜Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉ）にする。
それ以外の時
サブマクロブロックパーティションを図２の（ｖｉｉｉ）にする。
【００７６】
（条件１６’）
MAElow(0)≧Thll, MAElow(1)≧Thll, MAElow(2)≧Thll, MAElow(3)≧Thll のとき、
MAElow(1)+MAElow(0)＜Thml, MAElow(0)+MAElow(2)＜Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)＜Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）及び（ｖｉｉ）にする。
MAElow(1)+MAElow(0)＜Thml, MAElow(0)+MAElow(2)≧Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉ）にする。
MAElow(1)+MAElow(0)≧Thml, MAElow(0)+MAElow(2)＜Thml, MAElow(1)+MAElow(3)＜Thml, MAElow(2)+MAElow(3)≧Thml のとき、
サブマクロブロックパーティションを図２の（ｖｉｉ）にする。
それ以外の時
サブマクロブロックパーティションを図２の（ｖｉｉｉ）にする。
【００７７】
ここで、例えばThll=4、Thml＝10とすると図４（ｂ）の例では、上記の（条件４’）の場合が適用され、サブマクロブロックパーティションとして図２の（ｖｉ）が選択される。なお、サブマクロブロックパーティションが図２の（ｖ）になった場合には、中ブロック探索モードがオンに設定される。また、図２の（ｖ）以外のサブマクロブロックパーティションが選択された場合は、中ブロック探索モードの設定はオフのまま、小ブロック探索モードがオンに設定される。
【００７８】
次に、ステップＳ１１３において、小ブロック探索モードがオンに設定されているか否かが判定される。小ブロック探索モードがオンの場合には（ステップＳ１１３において「ＹＥＳ」）、ステップＳ１１４に移行する。この場合、８×８画素のマクロブロックが、図２（ｖ）以外のサブマクロブロックパーティションが選択されたこととなる。一方、小ブロック探索モードがオフの場合には（ステップＳ１１３において「ＮＯ」）、中ブロック探索モードがオンに設定されており、ステップＳ１２１に移行する。この場合、８×８画素のマクロブロックについて、図２（ｖ）のサブマクロブロックパーティションが選択されたこととなるので、８×８画素の中ブロックについて動きベクトル検出が行われる。
【００７９】
ステップＳ１１４では、小ブロック動きベクトル探索部１０が、中ブロック動きベクトル検出部７から、サブマクロブロックパーティションの情報と動きベクトルとを取得する。小ブロック動きベクトル探索部１０は、該動きベクトルを用いて新たなマッチング位置を設定する。
【００８０】
次に、ステップＳ１１５では、小ブロック動きベクトル探索部１０が、サブマクロブロックパーティションで参照画像記憶部４から入力される参照画像データとの探索範囲におけるマッチング誤差MAElowを算出する。マッチング誤差MAElowは各探索階層について算出され、最終的に探索範囲（全探索階層）におけるマッチング誤差MAElowが最も小さくなる時の動きベクトルと、その時のマッチング誤差とが求められる。この動きベクトルを「最終的な動きベクトル」という。
【００８１】
続くステップＳ１１６では、探索階層が最下位の探索階層か否かを判定する。もし最下位の探索階層と判定された場合には（ステップＳ１１６において「ＹＥＳ」）、ステップＳ１１７へ移行する。ステップＳ１１７では、最終マクロブロックパーティション・最終動きベクトル決定部１１が、そのときのサブマクロブロックパーティションの情報と最終的な動きベクトルとを小ブロック動きベクトル探索部１０から受信する。一方、最下位の探索階層でないと判定された場合には（ステップＳ１１６において「ＮＯ」）、ステップＳ１２３に移行して、探索階層を１つ更新し、一つ下位の探索階層についてステップＳ１１４からの処理を継続する。
【００８２】
最終マクロブロックパーティション・最終動きベクトル決定部１１は、ステップＳ１１７において、マクロブロックパーティションの情報と最終的な動きベクトルの情報とを受信する。これらの情報は、上記のように、大ブロック動きベクトル検出部３、中ブロック動きベクトル検出部７及び小ブロック動きベクトル検出部１０のいずれかから送信される。続くステップＳ１２４では、最終マクロブロックパーティション・最終動きベクトル決定部１１は、受信した情報を、動き検出部２０１４の外部のインター予測部２０１３とエントロピー符号化部２００４に送信する。
【００８３】
以上の実施形態では、全てのブロックサイズについて探索画素精度を水平方向、垂直方向ともに一画素として実施することができる。その一方で、探索階層に応じて探索精度を異ならせても良い。
【００８４】
例えば、上位階層で水平方向での探索精度を１画素飛びにし、下位階層では水平方向、垂直方向ともに一画素精度で探索を行う場合を考える。
ここで、上位階層で水平方向、垂直方向ともに一画素精度で探索を行っていた時のマクロブロックのサイズが水平１６×垂直１６だった場合、探索精度が水平１画素飛びで同一探索範囲に相当するマクロブロックサイズは水平８×垂直１６になる。この時、ブロックの分割は水平４×垂直８で行い、閾値との比較を行うことができる。その結果に従い、下位階層で使用するブロックサイズを決定し、下位階層では水平方向、垂直方向ともに一画素精度の探索を行うことができる。
【００８５】
以上の発明の実施形態によれば、大きなサイズのマクロブロックタイプから、複数の探索階層について使用する適切なマクロブロックパーティションを絞り込んでいくことが可能である。これにより、複数の参照フレームのそれぞれについて、全てのマクロブロックパーティション及びサブマクロブロックパーティションに対して動き探索を行わなくてもよい。よって、動き検出に関する演算負荷を大幅に低減することができる。その結果として、装置のバッテリー消費量を押さえることができ、高画質対応のビデオカメラシステムでも長時間撮影を実現することができる。
【００８６】
［その他の実施形態］
なお、本発明は、複数の機器（例えばホストコンピュータ、インタフェイス機器、リーダ、プリンタなど）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機、ファクシミリ装置など）に適用してもよい。
【００８７】
また、本発明の目的は、前述した機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムに供給し、そのシステムがプログラムコードを読み出し実行することによっても達成される。この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現し、そのプログラムコードを記憶した記憶媒体は本発明を構成する。また、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているオペレーティングシステム（ＯＳ）などが実際の処理の一部または全部を行い、その処理によって前述した機能が実現される場合も含まれる。
【００８８】
さらに、以下の形態で実現しても構わない。すなわち、記憶媒体から読み出されたプログラムコードを、コンピュータに挿入された機能拡張カードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込む。そして、そのプログラムコードの指示に基づき、その機能拡張カードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行って、前述した機能が実現される場合も含まれる。
【００８９】
本発明を上記記憶媒体に適用する場合、その記憶媒体には、先に説明したフローチャートに対応するプログラムコードが格納されることになる。
【図面の簡単な説明】
【００９０】
【図１ａ】発明の実施形態に対応する画像処理装置の全体構の一例を示す図である。
【図１ｂ】発明の実施形態に対応する動きベクトル検出装置の構成の一例を示す図である。
【図２】動きベクトル検出のために用いるブロックサイズの一例を示す図である。
【図３】発明の実施形態に対応する動き検出部における、入力画像データ中の１つのマクロブロックについて、動きベクトルを検出し、マクロブロックパーティションを決定する処理の一例を示すフローチャートである。
【図４】発明の実施形態に対応する、大ブロック、中ブロック、小ブロックにおけるマッチング誤差の内訳を説明するための図である。
【図５】複数の参照フレームから動き情報を検出する概念を説明するための図である。
【図１ａ】
2008017209.tif 000003
【図１ｂ】
2008017209.tif 000004
【図２】
2008017209.tif 000005
【図３】
2008017209.tif 000006
【図４】
2008017209.tif 000007
【図５】
2008017209.tif 000008