(57)【要約】【課題】  動画像データの符号化におけるフレームレートの向上と高速処理の両立を実現する。【解決手段】  予測ベクトル算出部１７２は、既に動きベクトルが検出されている周辺ブロックの動きベクトルを用いて予測ベクトル（整数予測ベクトルおよび分数予測ベクトル）を算出する。判別部１７５、探索範囲指定部１７６、ベクトル算出部１７７、差分検出部１７８は、探索ブロックおよび探索範囲を整数予測ベクトル分オフセットして整数探索をおこない、整数動きベクトルを得る。判別部１７５は、得られた整数動きベクトルと整数予測ベクトルとが一致するか否かを判別し、一致する場合は、一致する場合は分数探索の探索範囲を狭くとるとともに、分数予測ベクトル分オフセットして分数探索をおこなう。一致しない場合は探索範囲を広くとって分数探索をおこなう。【選択図】  図２
2006014033.tif 000002
【特許請求の範囲】
【請求項１】
指定されたブロックに基づいて探索範囲を指定する探索範囲指定手段と、
前記探索範囲指定手段が指定した探索範囲内を整数探索および分数探索して、差分が最小となる位置を検出する探索手段と、
前記探索手段が検出した位置を示すベクトルを動きベクトルとして検出するベクトル検出手段と、
を備えた、ブロックマッチングにより動画像の動きベクトルを検出する動き検出装置であって、
指定されたブロックの周辺ブロックで既に検出された動きベクトルを用いて予測ベクトルを算出する予測ベクトル算出手段と、
整数探索により検出された動きベクトルと、前記予測ベクトル算出手段が算出した予測ベクトルの整数部分とが一致するか否かを判別する判別手段と、をさらに備え、
前記探索範囲指定手段は、前記判別手段の判別結果に応じて、分数探索の探索範囲を指定する、
ことを特徴とする動きベクトル検出装置。
【請求項２】
前記予測ベクトル算出手段は、周辺ブロックにおける整数探索で得られた整数動きベクトルに基づく整数予測ベクトルと、周辺ブロックにおける分数探索で得られた分数動きベクトルに基づく分数予測ベクトルとを算出し、
前記探索範囲指定手段は、指定されたブロックを前記整数予測ベクトル分オフセットした位置に基づいて、整数探索の探索範囲を指定する、
ことを特徴とする請求項１に記載の動きベクトル検出装置。
【請求項３】
前記探索範囲指定手段は、前記判別手段の判別結果に応じて、異なるサイズの探索範囲のうちのいずれかを分数探索の探索範囲に指定する、
ことを特徴とする請求項１または２に記載の動きベクトル検出装置。
【請求項４】
前記探索範囲指定手段は、
前記判別手段が一致すると判別した場合、より小さいサイズの探索範囲を分数探索範囲として指定し、
前記判別手段が一致しないと判別した場合、より大きいサイズの探索範囲を分数探索範囲として指定する、
ことを特徴とする請求項１乃至３のいずれか１項に記載の動きベクトル検出装置。
【請求項５】
前記探索範囲指定手段は、前記判別手段が一致すると判別した場合、前記整数予測ベクトルに基づく位置を前記分数予測ベクトル分オフセットした位置に基づいて分数探索範囲を指定する、
ことを特徴とする請求項１乃至４のいずれか１項に記載の動きベクトル検出装置。
【請求項６】
前記探索範囲指定手段は、前記判別手段が一致しないと判別した場合、前記探索手段が整数探索で検出した位置に基づいて分数探索範囲を指定する、
ことを特徴とする請求項１乃至５のいずれか１項に記載の動きベクトル検出装置。
【請求項７】
前記判別手段が一致すると判別した場合、
前記探索手段は、分数探索を省略し、
前記ベクトル検出手段は、前記予測ベクトル算出手段が算出した分数予測ベクトルを、当該ブロックにおける分数動きベクトルとする、
ことを特徴とする請求項１乃至４のいずれか１項に記載の動きベクトル検出装置。
【請求項８】
整数探索により得られた整数動きベクトルと、分数探索により得られた分数動きベクトルと、整数動きベクトルと分数動きベクトルとを合成して得られる動きベクトルと、をブロック毎に記憶する記憶手段をさらに備える、
ことを特徴とする請求項１乃至７のいずれか１項に記載の動きベクトル検出装置。
【請求項９】
コンピュータでブロックマッチングによる動き検出をおこなうためのプログラムであって、
コンピュータに、
指定されたブロックの周辺ブロックで既に検出されている動きベクトルを用いて整数予測ベクトルと分数予測ベクトルとを算出する機能と、
探索ブロックを整数予測ベクトル分オフセットさせる機能と、
オフセットした探索ブロックを探索中心として整数探索し、差分が最小となる整数位置を検出する機能と、
検出した整数位置に基づいて、前記整数予測ベクトルが実際の整数動きベクトルと一致するか否かを判別する機能と、
整数動きベクトルと整数予測ベクトルとが一致すると判別された場合、前記整数予測ベクトルに基づく位置を前記分数予測ベクトル分オフセットした位置に基づいて分数探索範囲を指定するとともに、該分数探索範囲のサイズを、異なるサイズのうちのより小さいサイズに設定する機能と、
整数動きベクトルと整数予測ベクトルとが一致しないと判別された場合、整数探索で検出された整数位置に基づいて分数探索範囲を指定するとともに、該分数探索範囲のサイズを、異なるサイズのうちのより大きいサイズに設定する機能と、
設定した分数探索範囲内で分数探索をおこなって、差分が最小となる分数位置を検出する機能と、
検出した整数位置と分数位置とに基づいて、当該ブロックの動きベクトルを算出して出力する機能と、
少なくとも算出した整数動きベクトルと、分数動きベクトルと、動きベクトルと、をブロック毎に記憶する機能と、
を実現させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動きベクトル検出装置、および、プログラムに関し、特に、ブロックマッチング方式の動き検出に好適な動きベクトル検出装置、および、プログラムに関する。
【背景技術】
【０００２】
動画像データを圧縮するための符号化処理においては、現画像上に設定したマクロブロックとの誤差が最小となる参照画像上のブロック（参照ブロック）を探索し、探索されたブロックと現マクロブロックに元々対応する参照画像上の位置とのずれ量を「動きベクトル」とし、この動きベクトルを示す付加情報を用いて動き補償することによって符号量を抑えることが一般的である。
【０００３】
このような参照画像上での参照ブロックの探索方法として、例えば、「フルサーチ手順」が知られている。この方法は、参照画像上の探索領域内すべてのブロックパターンについて演算をおこなうものである。ここで、ブロック間の動きベクトル検出には、例えば、差分絶対値和演算（Sum of Absolute Difference: SAD）が一般的に用いられるため、すべてのブロックパターンを対象とするフルサーチ手順では、検出が確実である反面、動きベクトル検出のための総演算量が莫大となってしまう。また、画像の変化が少ない場合でもすべてのブロックについて演算してしまうため、処理が効率的でない場合がある。
【０００４】
一方で、すべてのブロックパターンについて演算をおこなわず、数段階（例えば、３ステップ）の手順を経ることで簡易的に動きベクトル検出をおこなう「ステップサーチ手順」も知られている。ステップサーチ手順によれば、フルサーチ手順よりも総演算量が減少するものの、例えば、最初のステップでブロック選択を誤ってしまうと、それ以降復帰できないため、誤った動きベクトルを検出してしまうおそれがある。
【０００５】
このような問題を解消するため、既に検出された動きベクトルに基づいて探索範囲を決定する方法が提案されている（例えば、特許文献１、特許文献２）。特許文献１に記載の発明は、空間的・時間的に相関が高い参照フレームの動きベクトルからベクトルを予測し、予測したベクトルの大きさに応じた探索範囲を決定するものである。また、特許文献２に記載の発明は、フレーム内で位置の相関評価を求め、探索範囲を適応的に選択するものである。
【０００６】
しかしながら、これらの手法では、参照ブロックの探索精度が整数画素単位までであり、分数画素単位（例えば、１／２画素（pel）や１／４画素（pel）、など）での探索については考慮されていなかった。分数画素単位の動き補償は、画像のＳＮ比向上や低ビットレート化などを図ることができ、フレームレートの向上に有効であることが知られているが、上記従来の手法では、分数画素単位での探索が考慮されていないため、より良好なフレームレートでの動画像圧縮を実現することができない。
【０００７】
一方で、分数画素単位での演算には補間処理が必要となるため、このような付加的な演算により計算量が増大し、処理の高速化が困難となってしまうおそれも生じる。したがって、フレームレートの向上と処理の高速化を両立する手法の確立が望まれている。
【特許文献１】特開平５−３２８３３３号公報
【特許文献２】特開平８−０３２９６９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明は上記実状に鑑みてなされたもので、画像のフレームレート向上を妨げることなく、最適な分数位置まで含めた動きベクトル検出を高速に実行可能な動きベクトル検出装置等を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明の第１の観点に係る動きベクトル検出装置は、
指定されたブロックに基づいて探索範囲を指定する探索範囲指定手段と、
前記探索範囲指定手段が指定した探索範囲内を整数探索および分数探索して、差分が最小となる位置を検出する探索手段と、
前記探索手段が検出した位置を示すベクトルを動きベクトルとして検出するベクトル検出手段と、
を備えた、ブロックマッチングにより動画像の動きベクトルを検出する動き検出装置であって、
指定されたブロックの周辺ブロックで既に検出された動きベクトルを用いて予測ベクトルを算出する予測ベクトル算出手段と、
整数探索により検出された動きベクトルと、前記予測ベクトル算出手段が算出した予測ベクトルの整数部分とが一致するか否かを判別する判別手段と、をさらに備え、
前記探索範囲指定手段は、前記判別手段の判別結果に応じて、分数探索の探索範囲を指定する、
ことを特徴とする。
【００１０】
上記動きベクトル検出装置において、
前記予測ベクトル算出手段は、周辺ブロックにおける整数探索で得られた整数動きベクトルに基づく整数予測ベクトルと、周辺ブロックにおける分数探索で得られた分数動きベクトルに基づく分数予測ベクトルとを算出し、
前記探索範囲指定手段は、指定されたブロックを前記整数予測ベクトル分オフセットした位置に基づいて、整数探索の探索範囲を指定することが望ましい。
【００１１】
上記動きベクトル検出装置において、
前記探索範囲指定手段は、前記判別手段の判別結果に応じて、異なるサイズの探索範囲のうちのいずれかを分数探索の探索範囲に指定することが望ましい。
【００１２】
上記動きベクトル検出装置において、
前記探索範囲指定手段は、
前記判別手段が一致すると判別した場合、より小さいサイズの探索範囲を分数探索範囲として指定し、
前記判別手段が一致しないと判別した場合、より大きいサイズの探索範囲を分数探索範囲として指定することが望ましい。
【００１３】
上記動きベクトル検出装置において、
前記探索範囲指定手段は、前記判別手段が一致すると判別した場合、前記整数予測ベクトルに基づく位置を前記分数予測ベクトル分オフセットした位置に基づいて分数探索範囲を指定することが望ましい。
【００１４】
上記動きベクトル検出装置において、
前記探索範囲指定手段は、前記判別手段が一致しないと判別した場合、前記探索手段が整数探索で検出した位置に基づいて分数探索範囲を指定することが望ましい。
【００１５】
上記動きベクトル検出装置において、
前記判別手段が一致すると判別した場合、
前記探索手段は、分数探索を省略してもよく、この場合、
前記ベクトル検出手段は、前記予測ベクトル算出手段が算出した分数予測ベクトルを、当該ブロックにおける分数動きベクトルとしてもよい。
【００１６】
上記動きベクトル検出装置は、
整数探索により得られた整数動きベクトルと、分数探索により得られた分数動きベクトルと、整数動きベクトルと分数動きベクトルとを合成して得られる動きベクトルと、をブロック毎に記憶する記憶手段をさらに備えていることが望ましい。
【００１７】
上記目的を達成するため、本発明の第２の観点にかかるプログラムは、
コンピュータでブロックマッチングによる動き検出をおこなうためのプログラムであって、
コンピュータに、
指定されたブロックの周辺ブロックで既に検出されている動きベクトルを用いて整数予測ベクトルと分数予測ベクトルとを算出する機能と、
探索ブロックを整数予測ベクトル分オフセットさせる機能と、
オフセットした探索ブロックを探索中心として整数探索し、差分が最小となる整数位置を検出する機能と、
検出した整数位置に基づいて、前記整数予測ベクトルが実際の整数動きベクトルと一致するか否かを判別する機能と、
整数動きベクトルと整数予測ベクトルとが一致すると判別された場合、前記整数予測ベクトルに基づく位置を前記分数予測ベクトル分オフセットした位置に基づいて分数探索範囲を指定するとともに、該分数探索範囲のサイズを、異なるサイズのうちのより小さいサイズに設定する機能と、
整数動きベクトルと整数予測ベクトルとが一致しないと判別された場合、整数探索で検出された整数位置に基づいて分数探索範囲を指定するとともに、該分数探索範囲のサイズを、異なるサイズのうちのより大きいサイズに設定する機能と、
設定した分数探索範囲内で分数探索をおこなって、差分が最小となる分数位置を検出する機能と、
検出した整数位置と分数位置とに基づいて、当該ブロックの動きベクトルを算出して出力する機能と、
少なくとも算出した整数動きベクトルと、分数動きベクトルと、動きベクトルと、をブロック毎に記憶する機能と、
を実現させることを特徴とする。
【発明の効果】
【００１８】
本発明によれば、既に算出されている周辺ブロックの動きベクトルに基づいて予測ベクトルを算出し、整数探索で検出されるベクトルと予測ベクトルとが一致するか否かを判別し、判別結果に応じて分数探索の探索範囲を選択するので、フレーム間での相関が高いブロックの演算量を減少させることができ、フレームレートの向上を妨げることなく、最適な分数位置まで含めた動きベクトルを高速に検出することができる。
【発明を実施するための最良の形態】
【００１９】
本発明にかかる実施形態を、以下図面を参照して説明する。本実施形態では、動画像データの符号化を行う符号化装置に本発明を適用した場合を例に以下説明する。本実施形態にかかる符号化装置１００は、入力される動画像データを構成する所定単位（例えば、フレームやフィールド）の画像間での動き補償により次の画像を予測する予測差分符号化方式で動画像データを符号化するものとする。本実施形態では、入力される単位画像を「フレーム」とする。すなわち、本実施形態にかかる符号化装置１００は、インターフレーム予測による符号化をおこなう。なお、画像単位はフレームに限られず任意であり、例えば「フィールド」などであってもよい。
【００２０】
本実施形態にかかる符号化装置１００の構成を図１を参照して説明する。図１は、本実施形態にかかる符号化装置１００の機能構成を示す機能ブロック図である。
【００２１】
図示するように、本実施形態にかかる符号化装置１００は、変換部１１０と、量子化部１２０と、符号化部１３０と、逆量子化部１４０と、逆変換部１５０と、復元画像メモリ１６０と、動き検出部１７０と、動き補償部１８０と、から構成される。
【００２２】
変換部１１０は、入力されたフレームおよび差分データについて変換符号化をおこなうことでデータ圧縮をおこなう。本実施形態では、例えば、４×４ブロックの整数変換（Integer Transform）をおこなうことで、動画像データを空間周波数領域に変換する。すなわち、隣接画素との相関を利用して低域周波数領域に変換係数を偏らせることでデータ圧縮を行う。
【００２３】
量子化部１２０は、変換部１１０による変換係数の値を、例えば、量子化ステップ幅の倍数で表して量子化し、データ圧縮を行う。すなわち、変換部１１０での変換に用いられた変換係数が離散的なレベルにマッピングされる。このような量子化によって高い周波数の情報が取り除かれる。
【００２４】
符号化部１３０は、量子化部１２０で量子化されたデータを、例えば、エントロピー符号化して出力するものであり、ＶＬＣ（Variable Length Coding：可変長符号化）方式などの符号を用いて符号化する。より詳細には、例えば、指数ゴロム符号（Exponential Golomb Coding）や、CAVLC（Context-based Adaptive Variable Length Coding）などを用いる。さらに、生成する符号量を削減するために、CABAC（Context-based Adaptive Binary Arithmetic Coding）などの算術符号を用いて符号化してもよい。符号化部１３０で符号化されたデータ（以下、「符号化ビットストリーム」とする）は、所定の伝送媒体や記録媒体などに出力される。出力された符号化ビットストリームは、所定の復号化装置によって復号されて動画像データが再生される。
【００２５】
逆量子化部１４０は、量子化部１２０で量子化されたデータを逆量子化し、逆変換部１５０は、逆量子化部１４０で逆量子化されたデータを逆変換することで、量子化された入力データ（量子化フレーム）を復元する。
【００２６】
復元画像メモリ１６０は、例えば、半導体記憶素子などから構成される記憶装置であり、逆変換部１５０で復元されたフレーム（以下、「復元フレーム」とする）を格納する、いわゆるフレームメモリである。すなわち、出力された符号化フレームについての符号化前のデータを格納する。復元画像メモリ１６０に格納された復元フレームは、インター予測で参照される「参照フレーム」として用いられる。
【００２７】
動き検出部１７０は、現在の入力フレーム（現フレーム）と、現フレームの前のフレーム（参照フレーム）との差分を検出することで画像中の動体の動きを検出し、その動きのベクトル（動きベクトル）を求める。本実施形態では、現フレーム上に所定数の画素から構成されるマクロブロック（Macro Block: MB）を設定し、参照フレーム上でマクロブロックとの差分が最小となるブロック（参照ブロック）を探索し、これらの位置間のずれ量を示すベクトルを「動きベクトル」として検出する、いわゆる「ブロック・マッチング法」による動き検出をおこなう。
【００２８】
ここで、本実施形態の動き検出部１７０は、整数画素単位で動きベクトルを探索した後に分数画素単位で探索をおこなう、いわゆる「多段探索」により、分数単位までの動きベクトルを検出する。ここで、整数画素単位での探索を「整数探索」、分数画素単位での探索を「分数探索」とし、分数探索においては１／４画素単位の探索精度で探索をおこなうものとする。
【００２９】
また、本実施形態にかかる動き検出部１７０は、各マクロブロック毎に既に検出した動きベクトルに基づく「予測ベクトル」を算出し、動きベクトル検出対象となっているマクロブロック（以下、「現ブロック」とする）における動きベクトル検出に利用する。
【００３０】
動き補償部１８０は、動き検出部１７０が検出した動きベクトルに基づいて、前のフレームに対して動き補償する。すなわち、検出した動きベクトルに基づいて予測フレームを作成する。そして、入力フレームと予測フレームの差分が符号化対象となる。
【００３１】
本実施形態にかかる動き検出部１７０は、上述のように予測ベクトルを算出し、算出した予測ベクトルを用いることで、処理速度の高速化とフレームレートの向上を図るものである。このような動作を行う動き検出部１７０の構成を図２を参照して説明する。
【００３２】
図２は、動き検出部１７０の構成を示すブロック図である。図示するように、動き検出部１７０は、ＭＢ（マクロブロック）設定部１７１、予測ベクトル算出部１７２、ベクトルメモリ１７３、ベクトル選択部１７４、判別部１７５、探索範囲指定部１７６、ベクトル算出部１７７、差分検出部１７８、を備える。
【００３３】
ＭＢ設定部１７１は、入力された現フレーム上に、マッチング対象となるマクロブロックを設定する。ここで、マクロブロックとは、所定数の画素群から構成されたブロックであり、図３に示すように、一の現フレームＣＦ上に複数設定する。ＭＢ設定部１７１は、このように設定されたマクロブロックＭＢを、動きベクトルの検出対象として順次指定するものとする。本実施形態では、図３において矢印で示すように、左から右への指定を上から下に向かって順次おこなう。動きベクトル検出の対象として指定されたマクロブロックを以下「現ブロック」とする。
【００３４】
予測ベクトル算出部１７２は、ベクトルメモリ１７３に格納されている、既に検出された動きベクトルに基づいて、動きベクトル検出時に参照する予測ベクトルを算出する。ここで「予測ベクトル」とは、既に検出した動きベクトルを用いて、次のマクロブロックでの動きベクトルを予想したものである。本実施形態では、現ブロックの周辺の複数のマクロブロック（以下、「予測対象ブロック」とする）の動きベクトルのメジアン（中央値）を算出して予測ベクトルとする。したがって、本実施形態では、現ブロック周辺の３つのブロックの動きベクトルを用いることとする。例えば、図４（ａ）に示すような位置に現ブロックが指定されている場合、図４（ｂ）に示すように、ブロックＢ、Ｃ、Ｄを３つを予測対象ブロックとする。
【００３５】
ここでは、現ブロックとの相関が強いブロックを予測対象ブロックとして選択する。この場合、現ブロックの直上、直下、直左、直右に隣接しているブロックとの相関が高いと考えられる。したがって、図４（ｂ）の場合、ブロックＢ、Ｄ、Ｅ、Ｇが現ブロックと相関が強いと考えられるが、ブロックＥ、Ｇについてはまだ動きベクトルが検出されていないため、予測対象ブロックとすることはできない。この場合、ブロックＡ、Ｃのいずれかを選択することになる。ここで、ブロックＣはブロックＥとの相関が強いと考えられ、ブロックＡは既に予測対象ブロックとされているブロックＢ、Ｄと相関が強いと考えられる。このような場合は、ブロックＥとの相関が強いブロックＣを選択する。
【００３６】
予測対象ブロックとしてブロックＢ，Ｃ，Ｄが選択された場合、各ブロックで検出された動きベクトルをそれぞれ、Ｂ（ｘ、ｙ）、Ｃ（ｘ、ｙ）、Ｄ（ｘ、ｙ）とすると、予測ベクトル算出部１７２は、「median (B(x), C(x), D(x))」をｘ方向の予測ベクトル（予測ベクトル（ｘ））とし、「median (B(y), C(y), D(y))」をｙ方向の予測ベクトル（予測ベクトル（ｙ））とする。
【００３７】
このように、本実施形態における予測ベクトルの算出には、予測対象ブロックが３つ必要となるため、少なくとも４番目以降のマクロブロックでの動きベクトル検出において予測ベクトルが算出されることとなる。しかし、現ブロックの位置によっては、３つの予測対象ブロックが得られない場合もある（例えば、現ブロックがブロック行列の１行目にある場合や１列目にある場合など）。このような場合は、現ブロックが４番目以降のものであっても、予測ベクトルの算出をスキップしてもよい。上記のような３つの予測対象ブロックが得られる条件を、以下「予測ベクトル算出条件」とする。
【００３８】
本実施形態では、動きベクトルを整数画素単位と分数画素単位で求める。したがって、予測ベクトル算出部１７２は、整数動きベクトルと分数動きベクトルのそれぞれを用いて予測ベクトルを算出するものとする。すなわち、予測対象ブロックの整数動きベクトルのメジアンと、予測対象ブロックの分数動きベクトルのメジアンとをそれぞれ求める。以下、整数動きベクトルを用いて算出した予測ベクトルを「整数予測ベクトル」とし、分数動きベクトルを用いて算出した予測ベクトルを「分数予測ベクトル」とする。なお、予測ベクトルの算出は「メジアン」に限られず、例えば、複数の動きベクトルの平均などであってもよい。また、予測ベクトル算出部１７２は算出した整数予測ベクトルと分数予測ベクトルとを一時的に記憶する記憶領域を備えているものとする。
【００３９】
ベクトルメモリ１７３は、各マクロブロック毎に検出された動きベクトルの値（ベクトルデータ）を記憶する。ここで、ベクトルメモリ１７３に格納される動きベクトルは、図５に示すように、整数探索で検出されたベクトル（「整数動きベクトル」）、分数探索で検出されたベクトル（「分数動きベクトル」）、および、整数動きベクトルと分数動きベクトルとを合成した動きベクトル（「最終値」）である。ここで、「整数動きベクトル」は、現ブロックについての整数探索が終了した時点でベクトルメモリ１７３に格納され、「分数動きベクトル」は、現ブロックについての分数探索が終了した時点でベクトルメモリ１７３に格納される。また、整数動きベクトルと分数動きベクトルとを合成した最終値が、当該マクロブロックにおける動きベクトルとなる。ベクトルメモリ１７３は、少なくとも、１フレーム分のマクロブロックそれぞれで検出されたベクトルの値が記憶されるものとする。なお、ベクトルメモリ１７３の機能は、他の記憶装置や記憶領域（例えば、復元画像メモリ１６０など）によってなされてもよい。
【００４０】
ベクトル選択部１７４は、判別部１７５が出力する判別信号に基づき、予測ベクトル算出部１７２が算出した予測ベクトルか、ベクトルメモリ１７３に格納されている動きベクトルのいずれかを選択して取得して出力する。
【００４１】
判別部１７５は、現在の探索処理の種別が整数探索であるか分数探索であるかの判別、整数探索段階において検出される整数動きベクトルと整数予測ベクトルとが一致するか否かの判別、探索範囲の基準となる位置の判別、などの判別動作をおこない、判別結果を示す信号（以下、「判別信号」とする）を出力する。
【００４２】
探索範囲指定部１７６は、判別部１７５が出力した判別信号に基づいて、探索範囲のサイズを指定し、指定した探索範囲のサイズを示す信号（以下、「範囲情報」とする）を出力する。
【００４３】
ベクトル算出部１７７は、判別部１７５が出力した判別信号、および、探索範囲指定部１７６が出力した範囲情報に基づいて、指定された探索範囲における探索位置（ブロック）を示す探索ベクトルを算出して出力する。すなわち、指定された探索範囲内の探索ブロックを示すベクトルを出力することで、差分演算対象となる探索ブロックを順次指定する。ここで、ベクトル算出部１７７は、整数探索時には整数単位のベクトルを算出して出力し、分数探索時には、分数単位のベクトルを算出して出力する。なお、整数探索においては整数予測ベクトルを加算し、分数探索においては必要に応じて分数予測ベクトルを加算して出力することで、探索範囲と探索ブロックを予測ベクトル分オフセットさせる。
【００４４】
また、ベクトル算出部１７７は、整数探索で得られた整数動きベクトルと、分数探索で得られた分数動きベクトルとを加算し、現ブロックにおける動きベクトルの最終値として出力する。
【００４５】
なお、ベクトル算出部１７７は、算出したベクトルを示すベクトルデータを一時的に記憶する記憶領域を有しているものとする。この記憶領域は、少なくとも、各マクロブロックについての処理で算出したベクトルデータを、当該マクロブロックについての処理が終了するまで保持するものとする。
【００４６】
差分検出部１７８は、ベクトル算出部１７７が出力したベクトルが示す位置（ブロック）について、参照フレームと現フレームとの間で差分絶対値和演算をおこない、演算結果を出力する。
【００４７】
このような動き検出部１７０の各構成は、所定の制御信号によって制御されるものとする。このような制御信号は、例えば、ＣＰＵ（Central Processing Unit：中央演算処理装置）などから構成される符号化装置１００の制御部（不図示）より各部に供給されるものとすることができる他、外部装置などから供給されてもよい。
【００４８】
上記のように構成された符号化装置１００は、次のような手順で動画像データを符号化する。
【００４９】
符号化装置１００に入力された動画像データは、フレーム単位で変換部１１０および動き検出部１７０へ送られる。動き検出部１７０では入力フレームと参照フレームとの差分を検出することで動きベクトルを検出する。動き補償部１８０は、その動きベクトルに基づいて参照フレームを動き補償して予測フレームを生成する。そして、入力フレームと予測フレームとの差分が取られ、その差分データは、変換部１１０による変換と、量子化部１２０による量子化が行われた後に、符号化部１３０で符号化される。動き検出部１７０が検出した動きベクトルデータも符号化部１３０で符号化され、両データは多重化されて出力される。
【００５０】
一方、量子化部１２０で量子化された差分データは、逆量子化部１４０で逆量子化され、逆変換部１５０で逆変換されることにより復元される。復元された差分データと、動き補償部１８０が生成した予測フレームとが加算され、復元画像メモリ１６０に「復元フレーム」（復元画像）として格納される。復元画像メモリ１６０に格納された復元フレームは、「参照フレーム」（参照画像）として動き検出部１７０に入力される。動き検出部１７０では、入力された参照フレームと現フレームとの間の動き補償に用いる「動きベクトル」を検出する。
【００５１】
本実施形態にかかる動き検出部１７０は、いわゆるブロックマッチング法により現フレームと参照フレームとの差分ベクトルを求めるものである。すなわち、現フレーム上のマクロブロックと画素値が近似するブロックを参照フレーム上で探索し、探索されたブロック（参照ブロック）の位置とマクロブロックの位置とのずれを示すベクトルを「動きベクトル」として検出する。
【００５２】
ここで、本実施形態では、対象となるマクロブロックにおいて、上述した予測ベクトル算出条件が充足する場合、予測ベクトルを利用して動きベクトルを検出する。この場合の動き検出部１７０の動作（「動きベクトル検出処理」）を図６に示すフローチャートを参照して説明する。この「動きベクトル検出処理」は、動き検出部１７０に現フレームが入力されたことを契機に開始される。
【００５３】
処理が開始されると、まず、ＭＢ設定部１７１が現フレームにマクロブロックを設定し、設定したマクロブロックのいずれかを符号化対象ブロック（現ブロック）として指定する（ステップＳ１０１）。ここでは、上述したように、左上からの走査方向順に指定する（図３参照）。
【００５４】
本実施形態にかかる動き検出部１７０は、整数探索後に分数探索をおこなう多段探索により動きベクトルを検出するので、ＭＢ設定部１７１により符号化対象ブロックが指定されると、まず、整数画素単位で探索する「整数探索処理」を実行する（ステップＳ２００）。この「整数探索処理」を図７、８に示すフローチャートを参照して説明する。
【００５５】
処理が開始されると、予測ベクトル算出部１７２が、現ブロックについて予測ベクトルを算出可能か否かを判別する（ステップＳ２０１）。ここでは、上述した予測ベクトル算出条件が充足しているか否かを判別する。予測ベクトル算出条件が充足している場合は「予測ベクトル算出可能」であり、予測ベクトル算出条件が充足していない場合は「予測ベクトル算出不可」ということになる。予測ベクトル算出部１７２は、ベクトルメモリ１７３に格納されているブロック毎の動きベクトルデータを参照することで、現ブロックについて予測ベクトル算出条件が充足しているか否かを判別する。すなわち、動きベクトルの「最終値」が記録されていれば、そのブロックについての動きベクトルは既に検出されていることになるので、そのようなブロックが現ブロックの周囲に３つあるか否かをみることで、予測ベクトル算出条件を充足しているか否かを判別することができる。
【００５６】
予測ベクトルが算出可能である場合（ステップＳ２０１：Ｙｅｓ）、予測ベクトル算出部１７２は、該当する予測対象ブロックについての動きベクトルをベクトルメモリ１７３から取得する。この場合、３つの予測対象ブロックの動きベクトルを取得し、これらのメジアンをとることで予測ベクトルを算出する（ステップＳ２０２）。より詳細には、予測対象ブロックの整数動きベクトルを取得してメジアンをとることで「整数予測ベクトル」を算出し、予測対象ブロックの分数動きベクトルを取得してメジアンをとることで「分数予測ベクトル」を算出する。予測ベクトル算出部１７２は、算出した整数予測ベクトルと分数予測ベクトルを、現ブロックについての処理が終了するまで保持する。
【００５７】
判別部１７５は、現在の処理が整数探索であることを示す判別信号と、現ブロックＣＢを示す判別信号を、ベクトル選択部１７４と、探索範囲指定部１７６と、ベクトル算出部１７７に出力する。
【００５８】
判別部１７５から出力された判別信号が「整数探索」を示す場合、ベクトル選択部１７４は、予測ベクトル算出部１７２から整数予測ベクトルを選択して、ベクトル算出部１７７に出力する。すなわち、予測ベクトルは、現ブロックの周辺ベクトルで求められた動きベクトルに基づいて、参照ブロックの位置を予測したものなので、本実施形態では、整数探索時に、現ブロックに対応する探索ブロックを整数予測ベクトル分ずらしておき（オフセット）、その周辺で探索をおこなうことで、探索範囲を絞り込み、演算量の減少を図る。したがって、ベクトル算出部１７７において探索範囲と探索ブロックを整数予測ベクトル分オフセットさせるため、整数探索時には、ベクトル選択部１７４は整数予測ベクトルを選択する。
【００５９】
探索範囲指定部１７６は、判別部１７５が出力した判別信号に基づいて、整数探索時の探索範囲サイズと探索中心を指定する（ステップＳ２０３）。
【００６０】
本実施形態では、探索ブロック（＝マクロブロック）のサイズを、例えば、図９（ａ）に示すような、１６×１６整数画素とする。以下、整数探索における探索ブロックを「探索ブロックＳＢ１」とする。本実施形態では、探索ブロックＳＢ１を構成する各整数位置のいずれかを基準点（以下、「基準点ＯＰ１」とする）とし、その基準点の位置を指定することにより、探索ブロックＳＢ１の位置や探索中心を決定するものとする。ここでは、図９（ａ）に示すように、探索ブロックＳＢ１の左上頂部の整数位置を基準点ＯＰ１とする。
【００６１】
また、本実施形態では、整数探索の探索範囲（以下、「整数探索範囲ＳＡ１」とする）を、例えば、５×５整数画素とする。この場合、図９（ｂ）に示すように、探索ブロックＳＢ１の基準点ＯＰ１を中心とした５×５整数画素の範囲が整数探索範囲ＳＡ１となる。整数探索においては、探索ブロックＳＢ１の基準点ＯＰ１が、整数探索範囲ＳＡ１内の各整数位置となるよう、１整数画素分ずつずらしながら、現ブロックとの差分を演算していく。
【００６２】
上述したように、本実施形態の「整数探索」では、探索ブロックと探索範囲を整数予測ベクトル分オフセットする。したがって、「整数探索」が指定されると、まず、図１０（ａ）に示すように、現フレームＣＦ上で指定された現ブロックＣＢと同一の位置およびサイズのブロックが、探索ブロックＳＢ１＿ＩＮＴとして参照フレームＲＦ上に規定される。そして、予測ベクトルが算出可能である場合、探索ブロックＳＢ１＿ＩＮＴを整数予測ベクトル分オフセットしたところを起点として、同サイズのブロック（探索ブロックＳＢ１）を整数画素ずつずらしながら、現ブロックＣＢとのマッチングをとることになる。ここでは、探索ブロックＳＢ１＿ＩＮＴの基準点ＯＰ１を整数探索の原点（基準点ＯＰ１＿ＩＮＴ）とする。
【００６３】
すなわち、図１０（ｂ）に示すように、探索ブロックＳＢ１＿ＩＮＴの基準点ＯＰ１＿ＩＮＴを整数予測ベクトル分オフセットした位置を中心とした整数探索範囲ＳＡ１が規定される。このような場合、探索範囲指定部１７６は、例えば、探索の原点が基準点ＯＰ１＿ＩＮＴであること、探索範囲が５×５整数画素であること、ブロックサイズが１６×１６整数画素であること、および、予測ベクトルが算出可能であること、などを示す情報を範囲情報としてベクトル算出部１７７に出力する。
【００６４】
ベクトル算出部１７７は、探索範囲指定部１７６が出力した範囲情報に基づき、探索ブロックＳＢ１を示すベクトルを算出して順次出力する。ここでは、まず、基準点ＯＰ１＿ＩＮＴの位置を特定すると、基準点ＯＰ１＿ＩＮＴを示すベクトルに、ベクトル選択部１７４が選択した整数予測ベクトルを加算する。すなわち、加算後のベクトルは、図１０（ｂ）に示すような、基準点ＯＰ１＿ＩＮＴを整数予測ベクトル分オフセットした位置を示すベクトルである。
【００６５】
ベクトル算出部１７７は、図１１（ａ）に示すように、基準点ＯＰ１０が基準位置（すなわち、ブロックの左上頂部の整数位置）となる１６×１６整数画素の探索ブロックＳＢ１を設定する。このブロックは、探索の起点となるブロック（以下、「探索ブロックＳＢ１０」とする）である。ベクトル算出部１７７は、基準点ＯＰ１＿ＩＮＴを原点とした、探索ブロックＳＢ１０を示すベクトルを算出し、探索ブロックＳＢ１０を示す探索ベクトルとして差分検出部１７８に出力する。
【００６６】
ここで、ベクトル算出部１７７は、探索範囲指定部１７６の範囲情報に基づいて、図１１（ａ）に示すように、基準点ＯＰ１０を中心とした５×５整数画素の整数探索範囲ＳＡ１を設定する。そして、ベクトル算出部１７７は、図１１（ｂ）に示すような、探索ブロックＳＢ１０を１整数画素分ずらした探索ブロックＳＢ１１を示す探索ベクトルを算出して出力する。この場合、図１１（ｂ）に示すように、探索ブロックＳＢ１０の基準点ＯＰ１０を１整数画素分ずらした位置を次の基準点である基準点ＯＰ１１とし、この基準点ＯＰ１１を基準とした１６×１６の探索ブロックＳＢ１１を示すベクトルを探索ベクトルとして出力する。ここでは、探索ブロックＳＢ１０を示す探索ベクトルに、整数単位のずらし量とずらし方向を示すベクトル（図１１（ｂ）の矢印）を加算することで、探索ブロックＳＢ１１の探索ベクトルとすることができる。
【００６７】
このようにして、ベクトル算出部１７７は、探索ブロックＳＢ１０を起点として、基準点ＯＰ１が整数探索範囲ＳＡ１の各整数位置となる探索ブロックＳＢ１１〜ＳＢ１２４のそれぞれを示す探索ベクトルを順次出力する。この場合、例えば、図１１（ｃ）の矢印で示す順序で探索ブロックＳＢ１を１整数画素分ずつずらしていく。ベクトル算出部１７７は、このように整数予測ベクトル分オフセットした各探索ブロックＳＢ１を示す探索ベクトルを算出し（ステップＳ２０４）、順次ベクトル算出部１７７に出力する。ここで、整数予測ベクトル分オフセットした位置を中心に整数探索範囲ＳＡ１が設定されるので、探索範囲も整数予測ベクトル分オフセットされたこととなる。
【００６８】
差分検出部１７８は、このように整数予測ベクトルが加算された探索ベクトルに基づいてブロックマッチングをおこなう（ステップＳ２０５）。すなわち、整数予測ベクトル分オフセットされた探索ブロックＳＢ１０〜ＳＢ１２４のそれぞれと、現ブロックＣＢとの差分を、例えば、絶対値和演算により求める。差分検出部１７８は、各探索ブロックＳＢ１毎の演算結果を評価値として判別部１７５に出力する。
【００６９】
判別部１７５は、差分検出部１７８から取得した評価値に基づき、各探索ブロックＳＢ１のうち、現ブロックとの差分が最小となる評価値が得られた探索ブロックＳＢ１を、探索ブロックＳＢ１＿ｍｉｎとして特定する（ステップＳ２０６）。
【００７０】
判別部１７５は、特定した探索ブロックＳＢ１＿ｍｉｎが、探索ブロックＳＢ１０であるか否かを判別する。すなわち、現ブロックとの差分が最小となったブロックが、探索中心のブロックであるか否かを判別する（ステップＳ２０７）。探索ブロックＳＢ１＿ｍｉｎが探索中心（ＳＢ１０）である場合（ステップＳ２０７：Ｙｅｓ）、判別部１７５は、予測ベクトル算出部１７２が算出した「整数予測ベクトル」が、現ブロックでの「整数動きベクトル」である、すなわち、「整数予測ベクトルと整数動きベクトルが一致する」と判別し（ステップＳ２０８）、その旨を示す判別信号をベクトル選択部１７４に出力する。
【００７１】
ベクトル選択部１７４は、判別部１７５からの判別信号に応じて、予測ベクトル算出部１７２から整数予測ベクトルを取得し、ベクトルメモリ１７３に出力する。ベクトルメモリ１７３は、ベクトル選択部１７４が出力した整数予測ベクトルを現ブロックの「整数動きベクトル」として格納する（ステップＳ２０９）。
【００７２】
すなわち、探索ブロックＳＢ１＿ＩＮＴを整数予測ベクトル分オフセットさせた探索ブロックＳＢ１０と現ブロックＣＢとの差分が最小であるため、現ブロックに対する参照ブロックの整数画素単位での位置は、探索ブロックＳＢ１＿ＩＮＴを整数予測ベクトル分加えたものとほぼ同一とすることができる。したがって、整数探索をおこなう前に算出した整数予測ベクトルを、整数探索によって得られる整数動きベクトルと同一視することができる。
【００７３】
整数動きベクトルをベクトルメモリ１７３に格納すると、「整数探索処理」を終了し、図６に示す「動きベクトル検出処理」のフローに戻る。
【００７４】
一方、探索ブロックＳＢ１＿ｍｉｎが探索ブロックＳＢ１０ではない場合、探索ブロックＳＢ１＿ＩＮＴに対する、探索ブロックＳＢ１＿ｍｉｎの位置が実際の「整数動きベクトル」ということになる。この場合の探索ブロックＳＢ１＿ｍｉｎは、整数予測ベクトルで示される探索ブロックＳＢ１０をさらに整数画素分ずらしたブロックであるので、探索ブロックＳＢ１＿ｍｉｎを示すベクトル、すなわち、実際の整数動きベクトルと整数予測ベクトルとは一致しない。したがって、探索ブロックＳＢ１＿ｍｉｎが探索中心ではない場合（ステップＳ２０７：Ｎｏ）、判別部１７５は、現ブロックにおける整数探索で得られる整数動きベクトルと、予測ベクトル算出部１７２が算出した整数予測ベクトルとは一致しないと判別し（ステップＳ２２０：図８）、探索ブロックＳＢ１＿ｍｉｎとなった探索ブロックＳＢ１を指定する判別信号をベクトル算出部１７７に出力する。
【００７５】
ベクトル算出部１７７は、判別部１７５の判別信号に基づき、探索ブロックＳＢ１＿ｍｉｎとなった探索ブロックＳＢ１を示す探索ベクトルをベクトルメモリ１７３に出力する（ステップＳ２２１）。ベクトルメモリ１７３は、ベクトル算出部１７７が出力したベクトルを、現ブロックにおける「整数動きベクトル」として格納する（ステップＳ２２２）。
【００７６】
整数動きベクトルをベクトルメモリ１７３に格納すると、「整数探索処理」を終了し、図６に示す「動きベクトル検出処理」のフローに戻る。
【００７７】
なお、現ブロックについて予測ベクトルの算出が不可である場合（ステップＳ２０１：Ｎｏ）は、探索範囲指定部１７６が予測ベクトルを用いずに探索範囲を指定し（すなわち、整数予測ベクトル分オフセットさせない）、通常のブロックマッチング法によって整数動きベクトルを検出して（ステップＳ２１０）、処理を終了する。
【００７８】
本実施形態では、整数探索の後に分数探索をおこなう多段探索により動きベクトルを検出するので、「整数探索処理」が終了すると、「分数探索処理」が実行される（ステップＳ３００）。「分数探索処理」の詳細を図１２に示すフローチャートを参照して説明する。
【００７９】
ここで、対象となる参照フレームには、予め所定の補間処理により、分数画素単位に補間されているものとする。本実施形態では、１／４画素単位での分数探索をおこなうため、１／４画素単位に補間する。この場合、まず、例えば、「6tap FIR」などの補間手法により、図１３（ａ）に示すような１／２画素補間（半画素補間）をおこなう。これにより、各整数位置の中間位置（１／２位置）の画素値を得ることができる。半画素補間の後、さらに、例えば、「線形補間」などの補間手法により、図１３（ｂ）に示すような１／４画素補間をおこなう。これにより、各１／２位置の中間位置（１／４位置）の画素値を得ることができる。
【００８０】
以下、分数探索における探索ブロックを「探索ブロックＳＢ２」とし、探索ブロックＳＢ２の基準点を「基準点ＯＰ２」とする。なお、１／４画素補間されたフレームでの分数探索においては、探索ブロックＳＢ２のブロックサイズを１６×１６整数画素相当とする。その他、整数画素単位で指定されるサイズについても、相当するサイズが規定されるものとする。また、基準点ＯＰ２は、探索ブロックＳＢ２の左上頂部となる整数位置もしくは分数位置が該当する。
【００８１】
分数探索が開始されると、判別部１７５が、「整数探索処理」のステップＳ２０９での判別に基づいて、整数動きベクトルと整数予測ベクトルとが一致していたか否かを判別する（ステップＳ３０１）。
【００８２】
本実施形態では、整数予測ベクトルが実際の整数動きベクトルと一致していたか否かに応じて、分数探索における探索範囲の広さ（サイズ）と、分数予測ベクトルに基づく探索範囲の絞り込み要否などを決定する。
【００８３】
ここで、分数探索範囲のサイズとして、より小さいサイズの「狭範囲」と、より大きいサイズの「広範囲」の２種類を用意するものとし、整数予測ベクトルが実際の整数動きベクトルと一致していたか否かに応じて選択する。より詳細には、整数予測ベクトルが実際の整数動きベクトルと一致していた場合には「狭範囲」が選択され、一致していなかった場合には「広範囲」が選択される。
【００８４】
また、整数予測ベクトルが実際の整数動きベクトルと一致していた場合には、探索範囲を分数予測ベクトル分オフセットして探索範囲を絞り込む。
【００８５】
したがって、判別部１７５は、ステップＳ３０１での判別結果を示す判別信号、および、現在の探索処理が分数探索であることを示す判別信号などを、探索範囲指定部１７６、ベクトル算出部１７７、および、ベクトル選択部１７４に出力する。
【００８６】
探索範囲指定部１７６は、判別部１７５が出力した判別信号に基づき、まず分数探索の探索中心を指定する。ここで、整数予測ベクトルが実際の整数動きベクトルと一致していた場合、整数単位で現ブロックとの差分が最小であるブロックが探索ブロックＳＢ１０であるので、分数単位の探索中心を探索ブロックＳＢ１０とする。ここで、整数予測ベクトルが実際の動きベクトルと一致していたことから、ステップＳ２０２で算出した予測ベクトルは十分高い精度を持っていることとなる。したがって、分数単位での分数予測ベクトルについても十分高い精度があるといえるので、探索中心を分数予測ベクトル分オフセットさせることで、予め探索範囲を絞り込むことができる。
【００８７】
したがって、整数予測ベクトルが実際の整数動きベクトルと一致していた場合（ステップＳ３０１：Ｙｅｓ）、探索範囲指定部１７６は、まず探索ブロックＳＢ１０を指定し（ステップＳ３０２）、この探索ブロックＳＢ１０を分数予測ベクトル分オフセットさせる（ステップＳ３０３）。探索範囲指定部１７６は、分数予測ベクトル分オフセットしたブロック（以下、「探索ブロックＳＢ２０」とする）を分数探索の探索中心に指定するとともに、探索範囲のサイズを「狭範囲」に指定する（ステップＳ３０４）。この場合、探索範囲指定部１７６は、探索ブロックＳＢ１０の基準点ＯＰ１０を指定する情報、および、探索範囲のサイズが「狭範囲」であることを示す情報などを範囲情報としてベクトル算出部１７７に出力する。
【００８８】
このように、整数予測ベクトルと実際の整数動きベクトルとが一致していた場合には、分数探索の探索範囲および探索ブロックを分数予測ベクトル分オフセットするので、判別部１７５の判別信号に基づいて、ベクトル選択部１７４は予測ベクトル算出部１７２から「分数予測ベクトル」を取得して、ベクトル算出部１７７に出力する。
【００８９】
ベクトル算出部１７７は、探索範囲指定部１７６が出力した範囲信号に基づいて、まず、探索ブロックＳＢ１０の基準点ＯＰ１０を特定し、ここを分数探索の原点（ＯＰ２＿ＩＮＴ）とする。そして、ＯＰ２＿ＩＮＴの位置ベクトルに、ベクトル選択部１７４が選択した分数予測ベクトルを加算したベクトルが示す位置を、分数探索の探索中心となる探索ブロックＳＢ２０の基準点（基準点ＯＰ２０）とする。
【００９０】
ここで、ベクトル算出部１７７は、図１４（ａ）に示すような、分数探索範囲を決定するための基準となる範囲（以下、「基準範囲ＲＡ」とする）を設定する。図示するように、この基準範囲ＲＡは、基準点ＯＰ２０を中心とした３×３整数画素相当の範囲である。すなわち、整数単位で差分が最小とされた探索ブロックＳＢ１０の基準点ＯＰ１０を分数予測ベクトル分オフセットさせた基準点ＯＰ２０（分数位置）を中心とした３×３整数画素相当の範囲を基準範囲ＲＡとして設定する。
【００９１】
ここで、分数探索の探索範囲を基準範囲ＲＡに基づいて設定する。図１４（ｂ）は、１／４画素補間された基準範囲ＲＡを示す拡大図である。分数探索範囲のサイズが「狭範囲」の場合、探索範囲指定部１７６は、図１４（ｃ）に示すように、基準範囲ＲＡの中心である基準点ＯＰ２０の周囲８方向に隣接する３×３分数画素（１／４画素単位）の範囲を分数探索の範囲（以下、「分数探索範囲ＳＡ２Ｓ」とする）のサイズとする。このサイズは、探索中心の周囲８方向を１／４画素単位で探索するための最小限のサイズである。
【００９２】
整数予測ベクトルが実際の整数動きベクトルと一致した場合の分数探索では、このように規定した分数探索範囲ＳＡ２Ｓ内の各分数位置が基準位置（すなわち、ブロック左上頂部位置）となる１６×１６整数画素相当のブロックを分数探索の探索ブロックＳＢ２としてブロックマッチングをおこなう。この場合、ベクトル算出部１７７は、各探索ブロックＳＢ２を示すベクトルを算出して順次出力する。
【００９３】
すなわち、ベクトル算出部１７７は、図１５（ａ）に示すように、分数探索範囲ＳＡ２Ｓの各位置が基準位置（すなわち、ブロックの左上頂部位置）となる１６×１６整数画素相当の探索ブロックＳＢ２を設定する。このブロックは、探索の起点となるブロック（以下、「探索ブロックＳＢ２０」とする）である。ベクトル算出部１７７は、基準点ＯＰ２＿ＩＮＴを原点とした、探索ブロックＳＢ２０を示すベクトルを算出し、探索ブロックＳＢ２０を示す探索ベクトルとして差分検出部１７８に出力する。
【００９４】
続いて、ベクトル算出部１７７は、図１５（ｂ）に示すような、探索ブロックＳＢ２０を１分数画素分ずらした探索ブロックＳＢ２１を示す探索ベクトルを算出して出力する。この場合、図１５（ｂ）に示すように、探索ブロックＳＢ２０の基準点ＯＰ２０を１分数画素分ずらした位置を次の基準点（基準点ＯＰ２１）とし、この基準点ＯＰ２１が基準位置となる１６×１６整数画素相当の探索ブロックＳＢ２１を示すベクトルを探索ベクトルとして出力する。ここでは、探索ブロックＳＢ２０を示す探索ベクトルに、分数単位のずらし量とずらし方向を示すベクトル（図１５（ｂ）の矢印）を加算することで、探索ブロックＳＢ２１の探索ベクトルとすることができる。
【００９５】
このようにして、ベクトル算出部１７７は、探索ブロックＳＢ２０を起点として、基準点ＯＰ２が探索範囲ＳＡ２Ｓの各分数位置となる探索ブロックＳＢ２１〜ＳＢ２８のそれぞれを示す探索ベクトルを順次出力する。この場合、例えば、図１５（ｃ）の矢印で示す順序で探索ブロックＳＢ２を１分数画素分ずつずらしていく。ベクトル算出部１７７は、このように分数予測ベクトル分オフセットした各探索ブロックＳＢ２を示す探索ベクトルを算出し、差分検出部１７８に順次出力する。ここで、分数予測ベクトル分オフセットした位置を基準に探索範囲ＳＡ２Ｓが設定されるので、探索範囲も分数予測ベクトル分オフセットされたこととなる。
【００９６】
差分検出部１７８は、ベクトル算出部１７７が出力する探索ベクトルに基づいて、現ブロックＣＢとのマッチングをおこなう。すなわち、分数探索範囲ＳＡ２Ｓの各分数位置毎にブロックマッチングをおこなう（ステップＳ３０５）。ここでは、探索ブロックＳＢ１０から分数予測ベクトル分オフセットした探索ブロックＳＢ２０、および、この探索ブロックＳＢ２０を起点に１／４画素ずつずらした各探索ブロックＳＢ２１〜ＳＢ２８の画素値と、現ブロックＣＢの画素値との差分を、例えば、差分絶対値和演算により求める。差分検出部１７８は、分数位置毎の演算結果を評価値として判別部１７５に出力する。
【００９７】
判別部１７５は、差分検出部１７８から取得した評価値に基づき、差分が最小となる探索ブロックＳＢ２（以下、「探索ブロックＳＢ２＿ｍｉｎ」とする）を判別する。すなわち、差分が最小となる分数位置を特定する（ステップＳ３０６）。そして、探索ブロックＳＢ２＿ｍｉｎとされた探索ブロックＳＢ２を指定する判別信号をベクトル算出部１７７に出力する。
【００９８】
ベクトル算出部１７７は、判別部１７５が出力した判別信号に基づき、探索ブロックＳＢ２＿ｍｉｎとなった探索ブロックＳＢ２の探索ベクトルをベクトルメモリ１７３に出力する。
【００９９】
ベクトルメモリ１７３は、ベクトル算出部１７７が出力したベクトルを、現ブロックについての「分数動きベクトル」として格納する（ステップＳ３０７）。
【０１００】
つまり、整数予測ベクトルが整数動きベクトルと一致していた場合、整数単位で現ブロックと最も近似するブロックが探索ブロックＳＢ１０となるので、この探索ブロックＳＢ１０を中心に分数探索をおこなう。このとき、整数予測ベクトルが実際の整数動きベクトルと一致していたため、分数予測ベクトルの精度も高いといえる。したがって、探索ブロックと探索範囲を分数予測ベクトル分オフセットさせて探索範囲を絞り込み、分数探索にかかる演算量の減少を図る。さらに、分数予測ベクトルの精度が十分に高い場合、分数予測ベクトル分オフセットした探索ブロックと、実際の分数動きベクトルで示されるブロックとの誤差は極めて小さいことが予想される。このため、探索範囲を最小限の範囲（狭範囲）に設定し、その範囲内で探索ブロックＳＢ２を１／４画素ずつずらして現ブロックＣＢとの差分を求めることで、ブロックマッチングの演算量を最小限にする。
【０１０１】
そして、差分が最小となったブロック（探索ブロックＳＢ２＿ｍｉｎ）の位置を、分数予測ベクトル分オフセットする前の探索ブロックＳＢ１０を原点としたベクトルで求め、このベクトルを現ブロックについての「分数動きベクトル」とする。すなわち、現ブロックについての「分数動きベクトル」は、全体の動きベクトルから整数部分を除いたものであるので、探索中心である探索ブロックＳＢ１０からみた、探索ブロックＳＢ２＿ｍｉｎを示す分数ベクトルを、現ブロックについての「分数動きベクトル」とする。
【０１０２】
分数ベクトルがベクトルメモリ１７３に格納されると、「分数探索処理」を終了し、図６に示す「動きベクトル検出処理」のフローに戻る。
【０１０３】
一方、整数予測ベクトルが整数動きベクトルと一致しなかった場合（ステップＳ３０１：Ｎｏ）、判別部１７５は、その判別結果を示す判別信号、および、現在の探索処理が分数探索であることを示す判別信号などを、探索範囲指定部１７６、ベクトル算出部１７７、および、ベクトル選択部１７４に出力する。
【０１０４】
探索範囲指定部１７６は、判別部１７５が出力した判別信号に基づき、分数探索の探索中心を指定する。ここで、整数予測ベクトルが実際の整数動きベクトルと一致していなかった場合、整数単位で現ブロックとの差分が最小であるブロックは探索ブロックＳＢ１＿ｍｉｎであるので、この探索ブロックＳＢ１＿ｍｉｎを分数探索の探索中心とする。ここで、整数予測ベクトルが実際の動きベクトルと一致していないことから、ステップＳ２０２で算出した予測ベクトルの精度は高くないと考えられる。このため、探索中心を分数予測ベクトル分オフセットさせても効果的な絞り込みとならない可能性が高い。したがって、整数予測ベクトルと実際の整数動きベクトルとが一致していなかった場合には、分数予測ベクトルを用いたオフセットはおこなわない。
【０１０５】
すなわち、整数予測ベクトルが実際の整数動きベクトルと一致していなかった場合、探索範囲指定部１７６は、探索ブロックＳＢ＿ｍｉｎを分数探索の探索中心（以下、「探索ブロックＳＢ２０」とする）に指定するとともに（ステップＳ３０８）、探索範囲のサイズを「広範囲」に指定する（ステップＳ３０９）。この場合、探索範囲指定部１７６は、探索ブロックＳＢ＿ｍｉｎの基準点（「基準点ＯＰ１＿ｍｉｎ」とする）を指定する情報、および、探索範囲のサイズが「広範囲」であることを示す情報などを範囲情報としてベクトル算出部１７７に出力する。
【０１０６】
ここで、探索ブロックＳＢ＿ｍｉｎは、整数探索で得られた「整数動きベクトル」によって表されるものである。したがって、ベクトル選択部１７４は、判別部１７５の判別信号に基づき、ベクトルメモリ１７３に記録された「整数動きベクトル」を取得してベクトル算出部１７７に出力する。
【０１０７】
ベクトル算出部１７７は、ベクトル選択部１７４が出力した「整数動きベクトル」に基づいて、まず、探索ブロックＳＢ１＿ｍｉｎの基準点ＯＰ１＿ｍｉｎを特定する。ここでは、探索ブロックＳＢ１＿ＩＮＴの基準点である基準点ＯＰ１＿ＩＮＴを示すベクトルに、整数動きベクトルを加算することで、探索ブロックＳＢ１＿ｍｉｎの基準点ＯＰ１＿ｍｉｎを特定することができる。ベクトル算出部１７７は、このような基準点ＯＰ１＿ｍｉｎを、分数探索の探索中心となる探索ブロックＳＢ２０の基準点（基準点ＯＰ２０）とする（図１６（ａ））。この基準点ＯＰ２０は、分数探索の原点（ＯＰ２＿ＩＮＴ）でもある。
【０１０８】
ここで、ベクトル算出部１７７は、図１６（ｂ）に示すような、分数探索範囲を決定するための基準となる基準範囲ＲＡを設定する。図示するように、この基準範囲ＲＡは、基準点ＯＰ２０（整数位置）の周囲８方向に隣接する３×３整数画素の範囲である。すなわち、整数単位で差分が最小とされた探索ブロックＳＢ＿ｍｉｎの基準点ＯＰ１＿ｍｉｎ（基準点ＯＰ２０）の周囲８方向に隣接する３×３整数画素の範囲を基準範囲ＲＡとして設定する。
【０１０９】
ここで、分数探索の探索範囲を基準範囲ＲＡに基づいて設定する。図１７（ａ）は、１／４画素補間された基準範囲ＲＡを示す拡大図である。分数探索範囲のサイズが「広範囲」の場合、探索範囲指定部１７６は、図１７（ｂ）に示すように、基準範囲ＲＡの中心となる基準点ＯＰ２０（整数位置）の周囲８方向に隣接する整数位置を含まない範囲を、分数探索の範囲（以下、「分数探索範囲ＳＡ２Ｌ」とする）のサイズとする。ここで、隣接する整数位置を含まないのは、これらの整数位置については、前段の整数探索においてすでに演算対象とされているため、分数探索においては対象とする必要がないためである。したがって、このサイズは、１／４画素単位で探索する最大限のサイズである。すなわち、１／４画素精度の場合、「広範囲」として指定された分数探索範囲ＳＡ２Ｌのサイズは、図１７（ｂ）に示すように、７×７分数画素（１／４画素単位）となる。
【０１１０】
整数予測ベクトルが実際の整数動きベクトルと一致しなかった場合の分数探索では、このように規定した分数探索範囲ＳＡ２Ｌの各分数位置が基準点となる１６×１６整数画素相当のブロックを分数探索の探索ブロックＳＢ２としてブロックマッチングをおこなう。この場合、ベクトル算出部１７７は、各探索ブロックＳＢ２を示すベクトルを算出して順次出力する。
【０１１１】
すなわち、ベクトル算出部１７７は、分数探索範囲ＳＡ２Ｌの各分数位置が基準位置（すなわち、ブロックの左上頂部位置）となる１６×１６整数画素相当の探索ブロックＳＢ２を設定する。この場合、ベクトル算出部１７７はまず、図１８（ａ）に示すような、基準点ＯＰ２０が基準位置となる探索ブロックＳＢ２を設定する。このブロックは、探索の起点となるブロック（以下、「探索ブロックＳＢ２０」とする）である。ここで、探索ブロックＳＢ２０は、探索ブロックＳＢ１＿ｍｉｎと同一であるので、ベクトル算出部１７７は、整数探索において算出した、探索ブロックＳＢ１＿ｍｉｎを示す探索ベクトルを利用する。
【０１１２】
ベクトル算出部１７７は、図１８（ｂ）に示すような、探索ブロックＳＢ２０を１分数画素分ずらした探索ブロックＳＢ２１を示す探索ベクトルを算出して出力する。この場合、図１８（ｂ）に示すように、探索ブロックＳＢ２０の基準点ＯＰ２０を１分数画素分ずらした位置を次の基準点である基準点ＯＰ２１とし、この基準点ＯＰ２１を基準位置とする１６×１６整数画素相当の探索ブロックＳＢ２１を示すベクトルを探索ベクトルとして出力する。ここでは、探索ブロックＳＢ２０を示す探索ベクトルに、分数単位のずらし量とずらし方向を示すベクトル（図１８（ｂ）の矢印）を加算することで、探索ブロックＳＢ２１の探索ベクトルとすることができる。
【０１１３】
このようにして、ベクトル算出部１７７は、探索ブロックＳＢ２０を起点として、基準点ＯＰ２が分数探索範囲ＳＡ２Ｌ内の各分数位置となる探索ブロックＳＢ２１〜ＳＢ２４８のそれぞれを示す探索ベクトルを順次出力する。この場合、例えば、図１８（ｃ）の矢印で示す順序で探索ブロックＳＢ２を１分数画素分ずつずらしていく。ベクトル算出部１７７は、このような各探索ブロックＳＢ２を示す探索ベクトルを算出し、順次差分検出部１７８に出力する。
【０１１４】
差分検出部１７８は、ベクトル算出部１７７が出力する探索ベクトルに基づいて、現ブロックＣＢとのマッチングをおこなう。すなわち、分数探索範囲ＳＡ２Ｌの各分数位置毎にブロックマッチングをおこなう（ステップＳ３０５）。ここでは、探索ブロックＳＢ２０は探索ブロックＳＢ１＿ｍｉｎと同一であるので、差分演算の対象から除外する。したがって、探索ブロックＳＢ２０を起点に１／４画素ずつずらした各探索ブロックＳＢ２１〜ＳＢ２４８の画素値と、現ブロックＣＢの画素値との差分を、例えば、差分絶対値和演算により求める。差分検出部１７８は、分数位置毎の演算結果を評価値として判別部１７５に出力する。
【０１１５】
判別部１７５は、差分検出部１７８から取得した評価値に基づき、差分が最小となる探索ブロックＳＢ２（以下、「探索ブロックＳＢ２＿ｍｉｎ」とする）を判別する（ステップＳ３０６）。そして、探索ブロックＳＢ２＿ｍｉｎとされた探索ブロックＳＢ２を指定する判別信号をベクトル算出部１７７に出力する。
【０１１６】
ベクトル算出部１７７は、判別部１７５が出力した判別信号に基づき、探索ブロックＳＢ２＿ｍｉｎとなった探索ブロックＳＢ２の探索ベクトルをベクトルメモリ１７３に出力する。
【０１１７】
ベクトルメモリ１７３は、ベクトル算出部１７７が出力したベクトルを、現ブロックについての「分数動きベクトル」として格納する（ステップＳ３０７）。
【０１１８】
つまり、整数予測ベクトルが整数動きベクトルと一致していなかった場合、予測ベクトルの信頼度は高くないと考えられるので、分数予測ベクトルを用いて探索範囲を絞り込まずに分数探索をおこなう。この場合、整数探索で現ブロックとの差分が最小となった位置、すなわち、探索ブロックＳＢ＿ｍｉｎを分数画素分ずつずらしながら現ブロックとの間のブロックマッチングをとることで、現ブロックについての正確な分数動きベクトルを求めることができる。ここで、現ブロックについての「分数動きベクトル」は、全体の動きベクトルから整数部分を除いたものであるので、探索中心である探索ブロックＳＢ２０（＝探索ブロックＳＢ１＿ｍｉｎ）からみた、探索ブロックＳＢ２＿ｍｉｎを示す分数ベクトルを、現ブロックについての「分数動きベクトル」とすることができる。
【０１１９】
現ブロックにおける分数動きベクトルが検出されてベクトルメモリ１７３に格納されると、「分数探索処理」を終了し、図６に示す「動きベクトル検出処理」のフローに戻る。
【０１２０】
ここでは、判別部１７５が分数探索が終了したと判別し、その旨を示す判別信号をベクトル選択部１７４に出力する。ベクトル選択部１７４は、判別部１７５が出力した判別信号に基づき、、現ブロックで探索された「整数動きベクトル」と「分数動きベクトル」とをベクトルメモリ１７３から取得して、ベクトル算出部１７７に出力する。ベクトル算出部１７７は、ベクトル選択部１７４から出力された「整数動きベクトル」と「分数動きベクトル」とを加算し、現ブロックにおける動きベクトル（最終値）として、ベクトルメモリ１７３と動き補償部１８０に出力する（ステップＳ１０３）。
【０１２１】
すなわち、整数予測ベクトルと整数動きベクトルが一致していた場合は、「整数予測ベクトル」に分数探索で求めた「分数動きベクトル」を加えたものが最終値となる。一方、一致していなかった場合は、整数探索で求めた「整数動きベクトル」に分数探索で求めた「分数動きベクトル」を加えたものが最終値となる。
【０１２２】
ベクトルメモリ１７３は、ベクトル算出部１７７が出力したベクトルを、現ブロックにおける動きベクトル（最終値）として格納する。
【０１２３】
そして、現フレームのすべてのマクロブロックについて動きベクトルが検出されるまで、各マクロブロックについて上記処理をおこなう（ステップＳ１０４：Ｎｏ、Ｓ１０５）。すべてのマクロブロックについて動きベクトルが検出されると（ステップＳ１０４：Ｙｅｓ）、処理を終了する。
【０１２４】
このように各マクロブロック毎に動きベクトルが検出されると、動き補償部１８０によって動き補償されて予測フレームが作成される。そして、予測フレームと現フレームとの差分のみが符号化部１３０で符号化されて、符号化ビットストリームとして出力される。
【０１２５】
以上説明したように、本実施形態にかかる動き検出部１７０は、整数探索の後に分数探索をおこなう多段探索において、整数探索時に整数予測ベクトル分オフセットさせて探索をおこない、その結果得られた、差分が最小となる整数位置のベクトルを「整数動きベクトル」として検出する。そして、整数動きベクトルと整数予測ベクトルとが一致するか否かを判別し、一致する場合には、分数探索の探索範囲を狭くとるとともに、分数予測ベクトル分オフセットさせて分数探索する。一方、一致しない場合には、整数探索で最小差分となった整数位置を中心に、分数探索の探索範囲を広くとって分数探索をおこなう。
【０１２６】
上記の分数探索において、「狭範囲」である分数探索範囲ＳＡ２Ｓは、図１４（ｃ）に示すように、３×３分数画素分の範囲である。したがって、この場合のブロックマッチングは、探索ブロックＳＢ１０を分数予測ベクトル分オフセットした探索ブロックＳＢ２０〜ＳＢ２８のそれぞれと、現ブロックＣＢとの間でマッチングをとる。すなわち、「狭範囲」が指定された場合の演算回数は９回である。
【０１２７】
一方、「広範囲」である分数探索範囲ＳＡ２Ｌは、図１７（ｂ）に示すように、７×７分数画素分の範囲である。ここで、探索ブロックＳＢ２０（＝探索ブロックＳＢ１＿ｍｉｎ）については整数探索で演算されているので、「広範囲」が指定された場合のブロックマッチングは、探索ブロックＳＢ２１〜ＳＢ２４８のそれぞれと、現ブロックＣＢとの間でマッチングをとる。すなわち、「広範囲」が指定された場合の演算回数は４８回となる。
【０１２８】
「動き補償」による差分符号化は、平行移動している動体を示す動画像などを符号化（圧縮）する場合に効果的であることが知られている。このような動画像では、動体部分におけるブロック間の相関は高く、その関係は複数のフレーム間に渡って維持されると考えられる。したがって、本発明にかかる上記動作を適用することで、相関の高いブロックから算出された整数予測ベクトルを用いて探索範囲を絞り込んで整数探索をおこなって、整数予測ベクトルと実際の整数動きベクトルとが一致するかをみる。そして、整数予測ベクトルと実際の整数動きベクトルとが一致した場合には、予測ベクトルの信頼度が保証されるので、分数予測ベクトル分オフセットして探索範囲を絞り込み、さらにの分数探索範囲を「狭範囲」にする。この結果、動画像を分数画素レベルで符号化する際の演算量を大幅に削減することができ、特に、上記のような平行移動する動体を示す動画像などの場合に効果的となる。
【０１２９】
ここで、整数予測ベクトルが実際の整数動きベクトルと一致している場合は、分数予測ベクトルの信頼度も高いと考えられる。この場合、分数予測ベクトル分オフセットさせたブロックと、実際の分数動きベクトルで示されるブロックとの誤差は極めて小さいと考えられるので、分数探索のずらし量が最小限となる「狭範囲」の探索であっても、現ブロックとの差分が最小となる分数位置を探索することができる。
【０１３０】
一方、整数予測ベクトルが整数動きベクトルと一致しない場合は、分数予測ベクトルの信頼度も高くないと考えられる。この場合、整数探索で得られた「整数動きベクトル」で示されるブロックを用いて、隣接する整数位置を含まない範囲（「広範囲」）内で分数探索することで、現ブロックとの差分が最小となる分数位置を確実に検出する。
【０１３１】
すなわち、本実施形態にかかる動き検出部１７０によれば、フレームレートの向上につながる分数探索を含めた動き検出をおこないつつ、全体としての演算量の減少を図ることができる。この結果、分数探索によるフレームレートの向上と処理の高速化を両立させることができる。
【０１３２】
上記実施形態では、整数予測ベクトルと実際の整数動きベクトルとが一致した場合、より演算量の少ない「狭範囲」を指定して分数画素単位探索をおこなったが、一致した場合には分数探索を省略し、分数予測ベクトルを現ブロックの分数動きベクトルとしてもよい。すなわち、例えば、整数動きベクトルと整数予測ベクトルが一致することをもって、予測ベクトルの信頼性を保証できる場合には、その予測ベクトルの分数部分を現ブロックの分数差分ベクトルとして用いることができる。この場合、分数探索が省略されるので、現ブロックについての処理時間を短縮させることができる。
【０１３３】
上記実施形態では、ブロックサイズを１６×１６整数画素としたが、ブロックサイズは任意である。また、整数探索における整数探索範囲ＳＡ１を５×５整数画素としたが、整数探索における探索範囲のサイズも任意である。また、探索順序も任意である。
【０１３４】
なお、上記実施形態では、分数単位で探索可能な最小限の範囲を「狭範囲」とし、最大限の範囲を「広範囲」としたが、２つの異なるサイズであって、演算量の差がでるのであれば、分数探索範囲のサイズは任意である。また、上記実施形態では、探索範囲内のすべての位置で差分演算をおこなったが、探索範囲の画素数を間引きして差分演算をおこなってもよい。また、上記実施形態では、参照フレームのみを分数画素補間したが、現フレームも分数画素補間するようにしてもよい。
【０１３５】
なお、このような符号化装置１００から出力された符号化ビットストリームを復号する復号装置で動き検出をおこなう部分も、上記符号化装置１００の動き検出部１７０と同様の構成・動作とすることができる。すなわち、動画像データの符号化あるいは復号において、ブロックマッチングによる動き検出をおこなう部分を上記動き検出部１７０と同様の構成とすることにより、動画像の符号化および復号において、フレームレートの向上と処理高速化の両立を図ることができる。
【０１３６】
なお、上記実施形態にかかる動き検出部１７０の機能をソフトウェア処理によって実現してもよい。この場合、例えば、パーソナルコンピュータや動画像記録再生装置などの汎用装置で、これらの機能を実現するためのプログラムを実行することで、動き検出部１７０の機能を実現することができる。
【０１３７】
すなわち、汎用装置の記憶部に当該プログラムをインストールし、ＣＰＵなどの制御部がプログラムを実行する。この場合、以下のようなプログラムが実行されることで、汎用装置で本発明の実施形態にかかる動き検出部１７０の機能を実現することができる。
（１−１）「予測ベクトル算出プログラム」：既に動きベクトルが検出されているマクロブロックの動きベクトルに基づいて、現ブロックの動きベクトル検出時に用いる予測ベクトル（整数予測ベクトルと分数予測ベクトル）を算出するためのプログラム。
（１−２）「整数探索プログラム」：現ブロックに対応する参照フレーム上の探索ブロックを整数予測ベクトル分オフセットして整数探索し、現ブロックの画素値との差分が最小となる探索ブロックを示す整数位置を検出するためのプログラム。
（１−３）「判別プログラム」：整数探索で得られた実際の整数動きベクトルと整数予測ベクトルとが一致するか否かを判別するためのプログラム。
（１−４）「分数探索範囲指定プログラム」：整数予測ベクトルと実際の整数動きベクトルが「一致する」と判別された場合には、整数予測ベクトルが示す位置を分数予測ベクトル分オフセットした位置に基づいて分数探索の探索中心を指定するとともに、異なるサイズの探索範囲のうちのより小さいサイズの範囲（狭範囲）を分数探索範囲に指定し、「一致しない」と判別された場合には、整数動きベクトルが示す位置に基づいて分数探索の探索中心を指定するとともに、異なるサイズの探索範囲のうちのより大きいサイズの範囲（広範囲）を分数探索範囲に指定するためのプログラム。
（１−５）「分数探索プログラム」：参照フレーム上で指定された探索範囲内を分数画素単位で探索し、現ブロックの画素値との差分が最小となる探索ブロックを示す分数位置を検出するためのプログラム。
（１−６）「ベクトル算出プログラム」：検出された整数位置および分数位置に基づいて、現ブロックにおける整数動きベクトル、分数動きベクトル、および、動きベクトル（最終値）、などを算出するためのプログラム。
（１−７）「ベクトル記憶プログラム」：算出したベクトルの値を記憶装置に記憶するためのプログラム。
【０１３８】
上記プログラムを汎用装置で実行した場合、ＣＰＵなどの制御装置が、ＭＢ設定部１７１、予測ベクトル算出部１７２、ベクトル選択部１７４、判別部１７５、探索範囲指定部１７６、ベクトル算出部１７７、差分検出部１７８、などとして機能し、例えば、主記憶装置や外部記憶装置などの記憶装置がベクトルメモリ１７３などとして機能することとなる。
【０１３９】
これらのプログラムは、汎用装置等に予め組み込んで提供することができる他、プログラム自体を独立して提供してもよい。この場合のプログラムの配布方法は任意であり、例えば、CD-ROMやメモリカードなどの記録媒体に格納して配布可能であることはもとより、例えば、インターネットなどの通信媒体を介して配布してもよい。そして、配布されたプログラムを汎用コンピュータ装置等にインストールし、ＯＳ（Operation System：基本ソフトウェア）との協働などによって実行することで、上記動き検出部１７０の機能を実現することができる。
【０１４０】
また、本発明にかかる機能を実現するためのプログラムは、動画像の符号化・復号をおこなうための既存のプログラムとの協働により動作するようにしてもよい。すなわち、既存の動画像符号化・復号化プログラムに対する、いわゆるアップデートプログラムとして提供することで、既存の動画像符号化・復号化処理に上記のような動き検出動作を追加し、フレームレートの向上と処理の高速化を図ることができる。
【０１４１】
上記各実施形態の記載は、本発明を適用するための一例であり、本発明の範囲は上記各実施形態によって限定されるものではない。すなわち、上記実施形態以外の種々の形態で本発明が適用されてもよく、それらは本発明の範囲に含まれるものである。
【図面の簡単な説明】
【０１４２】
【図１】本発明の実施形態にかかる「符号化装置」の構成を示すブロック図である。
【図２】図１に示す「動き検出部」の構成を示すブロック図である。
【図３】現フレームに設定されるマクロブロックの例を示す図である。
【図４】予測ベクトルの算出動作を説明するための図であり、（ａ）は現ブロックの周辺ブロックの例を示し、（ｂ）は「予測対象ブロック」の例を示す。
【図５】図２に示す「ベクトルメモリ」に記録される内容の例を示す図である。
【図６】本発明の実施形態にかかる「動きベクトル検出処理」を説明するためのフローチャートである。
【図７】図６に示す「動きベクトル検出処理」で実行される「整数探索処理」を説明するためのフローチャートである。
【図８】図６に示す「動きベクトル検出処理」で実行される「整数探索処理」を説明するためのフローチャートである。
【図９】「整数探索」を説明するための図であり、（ａ）は探索ブロックの例を示し、（ｂ）は探索ブロックに設定される整数探索範囲の例を示す。
【図１０】「整数探索」を説明するための図であり、（ａ）は参照フレーム上に設定される探索ブロックの例を示し、（ｂ）は整数予測ベクトル分オフセットさせたときの整数探索範囲の例を示す。
【図１１】整数探索の探索動作を説明するための図であり、（ａ）は探索範囲が設定されたときの探索ブロックの例を示し、（ｂ）は探索ブロックを１整数画素分ずらした場合の例を示し、（ｃ）は探索ブロックを１整数画素分ずつずらす順序の例を示す。
【図１２】図６に示す「動きベクトル検出処理」で実行される「分数探索処理」を説明するためのフローチャートである。
【図１３】分数画素補間を説明するための図であり、（ａ）は１／２画素補間による分数位置の例を示し、（ｂ）は１／４画素補間による分数位置の例を示す。
【図１４】整数予測ベクトルと実際の整数動きベクトルが一致した場合の分数探索を説明するための図であり、（ａ）は基準点を分数予測ベクトル分オフセットさせたときの基準範囲の例を示し、（ｂ）は分数画素補間した基準範囲の例を示し、（ｃ）は「狭範囲」の分数探索範囲の例を示す。
【図１５】整数予測ベクトルと実際の整数動きベクトルが一致した場合の分数探索を説明するための図であり、（ａ）は探索範囲が設定されたときの探索ブロックの例を示し、（ｂ）は探索ブロックを１分数画素分ずらした場合の例を示し、（ｃ）は探索ブロックを１分数画素分ずつずらす順序の例を示す。
【図１６】整数予測ベクトルと実際の整数動きベクトルが一致しなかった場合の分数探索を説明するための図であり、（ａ）は分数探索の探索中心の例を示す図であり、（ｂ）は基準範囲の例を示す。
【図１７】整数予測ベクトルと実際の整数動きベクトルが一致しなかった場合の分数探索を説明するための図であり、（ａ）は分数画素補間した基準範囲の例を示し、（ｂ）は「広範囲」の分数探索範囲の例を示す。
【図１８】整数予測ベクトルと実際の整数動きベクトルが一致しなかった場合の分数探索を説明するための図であり、（ａ）は探索範囲が設定されたときの探索ブロックの例を示し、（ｂ）は探索ブロックを１分数画素分ずらした場合の例を示し、（ｃ）は探索ブロックを１分数画素分ずつずらす順序の例を示す。
【符号の説明】
【０１４３】
１００…符号化装置、１１０…変換部、１２０…量子化部、１３０…符号化部、１４０…逆量子化部、１５０…逆変換部、１６０…復元画像メモリ、１７０…動き検出部、１７１…ＭＢ設定部、１７２…予測ベクトル算出部、１７３…ベクトルメモリ、１７４…ベクトル選択部、１７５…判別部、１７６…探索範囲指定部、１７７…ベクトル算出部、１７８…差分検出部、１８０…動き補償部
【図１】
2006014033.tif 000003
【図２】
2006014033.tif 000004
【図３】
2006014033.tif 000005
【図４】
2006014033.tif 000006
【図５】
2006014033.tif 000007
【図６】
2006014033.tif 000008
【図７】
2006014033.tif 000009
【図８】
2006014033.tif 000010
【図９】
2006014033.tif 000011
【図１０】
2006014033.tif 000012
【図１１】
2006014033.tif 000013
【図１２】
2006014033.tif 000014
【図１３】
2006014033.tif 000015
【図１４】
2006014033.tif 000016
【図１５】
2006014033.tif 000017
【図１６】
2006014033.tif 000018
【図１７】
2006014033.tif 000019
【図１８】
2006014033.tif 000020