(57)【要約】【課題】フレーム間差分符号化方式における動きベクトル探索精度を向上する。【解決手段】隣接画像を加算することで解像度を低下させた階層画像を複数階層作成し、最も低い解像度の階層画像において全探索を行い、探索結果の良い探索点から順に複数点選択し、次に低い解像度の階層画像において自身及び周辺８点の計９探索点で探索を行い、探索結果の最良なものをさらに次の解像度の階層画像において自身及び周辺８点の計９探索点で探索を行う。上記を繰り返し入力画像の解像度における探索結果を動きベクトルの最終的な探索結果とする。【選択図】  図１
2008301085.tif 000002
【特許請求の範囲】
【請求項１】
入力画像をブロック単位に分割し、参照画像を用いて処理対象のブロック毎の動きベクトル探索を行う動きベクトル探索装置であって、
前記入力画像の解像度を低下させて、解像度の異なる複数の階層画像を生成する階層画像生成手段と、
前記参照画像の解像度を低下させて、解像度の異なる複数の参照階層画像を生成する参照階層画像生成手段と、
前記複数の階層画像のうち最低解像度の第１の階層画像における前記処理対象の第１のブロックを選択し、該第１のブロックの画素データと、前記複数の参照階層画像のうち最低解像度の第１の参照階層画像において前記第１のブロックに対応して設定される第１の探索領域の全領域の画素データとの第１の相関を算出する第１の相関算出手段と、
前記第１の相関の高い、前記第１の参照階層画像における第１のブロック位置を、該第１の相関の高い順に所定数だけ選択する第１の選択手段と、
前記第１の階層画像よりも解像度が１階層分だけ高い第２の階層画像における前記処理対象の第２のブロックを選択し、該第２のブロックの画素データと、前記第１の参照階層画像よりも解像度が１階層分だけ高い第２の参照階層画像において、前記所定数の第１のブロック位置に基づいて設定される該所定数の第２の探索領域の画素データとの第２の相関を算出する第２の相関算出手段と、
前記第２の相関算出手段において、最も高い第２の相関が算出された、前記第２の参照階層画像における第２のブロック位置を選択する第２の選択手段と、
前記第２の階層画像よりも解像度が１階層分だけ高い第３の階層画像における前記処理対象の第３のブロックを選択し、該第３のブロックの画素データと、前記第２の参照階層画像よりも解像度が１階層分だけ高い第３の参照階層画像において、前記第２のブロック位置に基づいて設定される第３の探索領域の画素データとの第３の相関を算出する第３の相関算出手段と、
前記第３の相関算出手段において、最も高い第３の相関が算出された、前記第３の参照階層画像における第３のブロック位置を選択する第３の選択手段と、
前記第３の階層画像よりも解像度が１階層分だけ高い前記入力画像における前記処理対象の第４のブロックを選択し、該第４のブロックの画素データと、前記第３の参照階層画像よりも解像度が１階層分だけ高い前記参照画像において、前記第３のブロック位置に基づいて設定される第４の探索領域の画素データとの第４の相関を算出する第４の相関算出手段と、
前記第４の相関算出手段において、最も高い第４の相関が算出された、前記参照画像における第４のブロック位置に基づいて、動きベクトルを算出する動きベクトル算出手段と、
を備えることを特徴とする動きベクトル探索装置。
【請求項２】
入力画像をブロック単位に分割し、参照画像を用いて処理対象のブロック毎の動きベクトル探索を行う動きベクトル探索装置であって、
前記入力画像の解像度を低下させて、解像度の異なる複数の階層画像を生成する階層画像生成手段と、
前記参照画像の解像度を低下させて、解像度の異なる複数の参照階層画像を生成する参照階層画像生成手段と、
前記複数の階層画像のうち最低解像度の第１の階層画像における前記処理対象の第１のブロックを選択し、該第１のブロックの画素データと、前記複数の参照階層画像のうち最低解像度の第１の参照階層画像において前記第１のブロックに対応して設定される第１の探索領域の全領域の画素データとの第１の相関を算出する第１の相関算出手段と、
前記第１の相関の高い、前記第１の参照階層画像における第１のブロック位置を、該第１の相関の高い順に所定数だけ選択する第１の選択手段と、
前記第１の階層画像よりも解像度が１階層分だけ高い第２の階層画像における前記処理対象の第２のブロックを選択し、該第２のブロックの画素データと、前記第１の参照階層画像よりも解像度が１階層分だけ高い第２の参照階層画像において、前記所定数の第１のブロック位置に基づいて設定される該所定数の第２の探索領域の画素データとの第２の相関を算出する第２の相関算出手段と、
前記第２の相関算出手段において、最も高い第２の相関が算出された、前記第２の参照階層画像における第２のブロック位置を選択する第２の選択手段と、
前記第２の相関算出手段において、最も高い第２の相関が算出された、前記第２の参照階層画像における第２のブロック位置を選択する第２の選択手段と、
前記第２の階層画像よりも解像度が１階層分だけ高い第３の階層画像における前記処理対象の第３のブロックを選択し、該第３のブロックの画素データと、前記第２の参照階層画像よりも解像度が１階層分だけ高い第３の参照階層画像において、前記第２のブロック位置に基づいて設定される第３の探索領域の画素データとの第３の相関を算出する第３の相関算出手段と
を備え、
入力画像の解像度まで前記第３の相関算出手段及び前記第３の選択手段における処理を繰り返し、最後に選択されたブロック位置に基づき動きベクトルを算出することを特徴とする動きベクトル探索装置。
【請求項３】
入力画像をブロック単位に分割し、参照画像を用いて処理対象のブロック毎の動きベクトル探索を行う動きベクトル探索装置の制御方法であって、
前記入力画像の解像度を低下させて、解像度の異なる複数の階層画像を生成する階層画像生成工程と、
前記参照画像の解像度を低下させて、解像度の異なる複数の参照階層画像を生成する参照階層画像生成工程と、
前記複数の階層画像のうち最低解像度の第１の階層画像における前記処理対象の第１のブロックを選択し、該第１のブロックの画素データと、前記複数の参照階層画像のうち最低解像度の第１の参照階層画像において前記第１のブロックに対応して設定される第１の探索領域の全領域の画素データとの第１の相関を算出する第１の相関算出工程と、
前記第１の相関の高い、前記第１の参照階層画像における第１のブロック位置を、該第１の相関の高い順に所定数だけ選択する第１の選択工程と、
前記第１の階層画像よりも解像度が１階層分だけ高い第２の階層画像における前記処理対象の第２のブロックを選択し、該第２のブロックの画素データと、前記第１の参照階層画像よりも解像度が１階層分だけ高い第２の参照階層画像において、前記所定数の第１のブロック位置に基づいて設定される該所定数の第２の探索領域の画素データとの第２の相関を算出する第２の相関算出工程と、
前記第２の相関算出工程において、最も高い第２の相関が算出された、前記第２の参照階層画像における第２のブロック位置を選択する第２の選択工程と、
前記第２の階層画像よりも解像度が１階層分だけ高い第３の階層画像における前記処理対象の第３のブロックを選択し、該第３のブロックの画素データと、前記第２の参照階層画像よりも解像度が１階層分だけ高い第３の参照階層画像において、前記第２のブロック位置に基づいて設定される第３の探索領域の画素データとの第３の相関を算出する第３の相関算出工程と、
前記第３の相関算出工程において、最も高い第３の相関が算出された、前記第３の参照階層画像における第３のブロック位置を選択する第３の選択工程と、
前記第３の階層画像よりも解像度が１階層分だけ高い前記入力画像における前記処理対象の第４のブロックを選択し、該第４のブロックの画素データと、前記第３の参照階層画像よりも解像度が１階層分だけ高い前記参照画像において、前記第３のブロック位置に基づいて設定される第４の探索領域の画素データとの第４の相関を算出する第４の相関算出工程と、
前記第４の相関算出工程において、最も高い第４の相関が算出された、前記参照画像における第４のブロック位置に基づいて、動きベクトルを算出する動きベクトル算出工程と、
を備えることを特徴とする動きベクトル探索装置の制御方法。
【請求項４】
コンピュータを請求項１に記載のベクトル探索装置として機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は動きベクトル探索装置及びその制御方法、コンピュータプログラムに関する。
【背景技術】
【０００２】
Ｈ．２６xやＭＰＥＧ等の符号化方式では、画像１フレームを複数のブロックに分割して、各ブロック単位に符号化を行う。圧縮符号化の方式として、時間的相関性を利用した符号化方式(inter符号化)および空間的相関性を利用した符号化方式(intra符号化)がある。時間的相関を利用した符号化方式はフレーム間の動きを探索し、当該ブロックの動きベクトルおよびブロック間差分を求めて符号化を行う。
【０００３】
最も相関の高い動きベクトルを完全に求めるには全探索をする必要がある。しかし、例えば１６×１６画素のブロックを参照フレームの探索領域６４×６４画素全てと比較すると、１６×１６×６４×６４=１０４８５７６回の比較演算が必要となり、計算量が膨大なものになってしまう。
【０００４】
探索回数を減らして適切な動きベクトルを高速に求めることを目的として、対数サーチ方式や、階層サーチ方式など様々な方式が提案されている。
【０００５】
対数サーチ方式は、縦横１６画素を探索範囲とする動きベクトル探索の古典的な方式である。また、階層サーチ方式は、図８のように、入力画像８０１の解像度を落として順次低解像度の画像８０２及び８０３を生成し、最低解像度の画像８０３における探索ウィンドウ(サーチウィンドウ)から探索をはじめる。そして探索結果を順次、上位階層のサーチウィンドウの探索開始点に反映させていく。このような階層サーチ方式によれば、低解像度のデータ量の少ない画像において広い範囲を探索することで、探索範囲を広げた時の比較演算回数の増加を抑えることができる。
【０００６】
しかしながら、Ｈ.２６４およびＭＰＥＧ符号化方式で用いられるブロックサイズ、即ち動き探索を行う単位は、最大でも１６×１６サイズであり、解像度を１／８にすると２×２になってしまう。この場合のブロックマッチングは計４画素どうしの比較となり、ブロックマッチングの精度は低下する。
【０００７】
そこで、特許文献１は、ブロック単位の動きベクトル探索において、入力画像に対して２回のダウンサンプリングを行い、３階層の画像を用いた探索方式を提案している。このようにブロック単位の動き探索に使用する場合は一般的に３階層、すなわち解像度１／４、ブロックの大きさが４×４サイズまでの階層化しか行わないことが一般的である。
【特許文献１】特許３６１５９６３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
以上のように、階層型サーチは階層を増やすことで広範囲のサーチを少ない演算回数で行えるが、低解像階層での探索精度が低いために３階層程度の階層化しか行えず、結果として演算量をあまり減らすことができないという問題があった。
【０００９】
そこで、本発明は少ない演算量で広範囲・高精度な動きベクトル探索を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記課題を解決するための本発明は、
入力画像をブロック単位に分割し、参照画像を用いて処理対象のブロック毎の動きベクトル探索を行う動きベクトル探索装置であって、
前記入力画像の解像度を低下させて、解像度の異なる複数の階層画像を生成する階層画像生成手段と、
前記参照画像の解像度を低下させて、解像度の異なる複数の参照階層画像を生成する参照階層画像生成手段と、
前記複数の階層画像のうち最低解像度の第１の階層画像における前記処理対象の第１のブロックを選択し、該第１のブロックの画素データと、前記複数の参照階層画像のうち最低解像度の第１の参照階層画像において前記第１のブロックに対応して設定される第１の探索領域の全領域の画素データとの第１の相関を算出する第１の相関算出手段と、
前記第１の相関の高い、前記第１の参照階層画像における第１のブロック位置を、該第１の相関の高い順に所定数だけ選択する第１の選択手段と、
前記第１の階層画像よりも解像度が１階層分だけ高い第２の階層画像における前記処理対象の第２のブロックを選択し、該第２のブロックの画素データと、前記第１の参照階層画像よりも解像度が１階層分だけ高い第２の参照階層画像において、前記所定数の第１のブロック位置に基づいて設定される該所定数の第２の探索領域の画素データとの第２の相関を算出する第２の相関算出手段と、
前記第２の相関算出手段において、最も高い第２の相関が算出された、前記第２の参照階層画像における第２のブロック位置を選択する第２の選択手段と、
前記第２の階層画像よりも解像度が１階層分だけ高い第３の階層画像における前記処理対象の第３のブロックを選択し、該第３のブロックの画素データと、前記第２の参照階層画像よりも解像度が１階層分だけ高い第３の参照階層画像において、前記第２のブロック位置に基づいて設定される第３の探索領域の画素データとの第３の相関を算出する第３の相関算出手段と、
前記第３の相関算出手段において、最も高い第３の相関が算出された、前記第３の参照階層画像における第３のブロック位置を選択する第３の選択手段と、
前記第３の階層画像よりも解像度が１階層分だけ高い前記入力画像における前記処理対象の第４のブロックを選択し、該第４のブロックの画素データと、前記第３の参照階層画像よりも解像度が１階層分だけ高い前記参照画像において、前記第３のブロック位置に基づいて設定される第４の探索領域の画素データとの第４の相関を算出する第４の相関算出手段と、
前記第４の相関算出手段において、最も高い第４の相関が算出された、前記参照画像における第４のブロック位置に基づいて、動きベクトルを算出する動きベクトル算出手段と、
を備えることを特徴とする。
【発明の効果】
【００１１】
本発明の動きベクトル探索方式は、計算量および画像データ転送量を抑えつつ広範囲・高精度に動きベクトル探索を行うことを可能とする。
【発明を実施するための最良の形態】
【００１２】
以下、添付する図面を参酌して、発明の実施形態を説明する。
【００１３】
［第１の実施形態］
本実施形態の動きベクトル探索方法に基づいた符号化装置の処理手順について、図１のフローチャートを参照して説明する。ここで符号化される対象の入力画像を「符号化画像」、動きベクトル探索のために参照される、時間的に前後した位置の画像を「参照画像」と呼ぶ。なお、図１では、符号化対象画像中の処理対象の１ブロックについての動き探索方法を示すが、実際には画像を構成する全ブロックについて、ブロック毎に当該処理が適用される。
【００１４】
図１において、ステップＳ１０１において、符号化画像の階層画像生成処理及び参照画像の参照階層画像生成処理を行う。ここでは、図３ａに示すように隣接する４画素の輝度値を加算し当該位置の画素値とすることで、もとの画像に対して解像度が縦横それぞれ１／２、画素数１／４の階層画像を作成することができる。なお、階層画像作成の際に、加算の代りにサブサンプル手法を用いても良いが、その場合にはサブサンプルに伴う折り返し歪みを低減する低域通過フィルタ処理を行うと良い。また、加算により解像度を低くした画像を生成すると、画素の重心位置が変化してしまうが、その変化量を考慮して補正すれば良い。
【００１５】
なお、本実施形態では、符号化画像、参照画像それぞれに対し、オリジナルの解像度（階層１）から、縦横の解像度をそれぞれ１／２、１／４、１／８に低下させた階層画像を生成する。なお、以下では、符号化画像の階層画像を単に階層画像と呼ぶ一方、参照画像の階層画像については、区別のために参照階層画像ということがある。生成される階層画像は、第１の階層画像（階層４）、第１の参照階層画像（階層４）、第２の階層画像（階層３）、第２の参照階層画像（階層３）、第３の階層画像（階層２）、第３の参照階層画像（階層２）である。従って、図１ではｎ＝４となる。
【００１６】
ステップＳ１０２では、ブロック単位で動き探索を行うため、符号化画像から当該ブロックの画像データを、参照画像から動き探索を行う領域(サーチウィンドウ)の画像データを切り出す。階層１から４までのそれぞれの階層画像と参照階層画像について、それぞれ対応する画像空間領域を等しく切り出す。なお、探索領域としてのサーチウィンドウは、例えば、当該ブロック及びその周辺領域に相当する６４×６４画素で構成される。
【００１７】
図３ｂは、階層１から階層４までの参照階層画像から切り出したサーチウィンドウの一例を示す。図３ｂにおいて、ウィンドウ１００１、１００２、１００３及び１００４は、それぞれ、階層１、階層２、階層３及び階層４のそれぞれのサーチウィンドウを示す。なお、図３ｂでは、記載の容易のために、解像度の変更に基づく画素数の縮小（サイズの縮小）は考慮していない。即ち、図３ａに示すように、４画素の平均により求められた１画素のサイズを、従前の４画素分のサイズと同等に記載している。
【００１８】
ステップＳ１０３では、切り出されたブロックおよびサーチウィンドウの画像データのうち、階層ｎ、即ち最低解像度の階層４のデータ（第１のブロック）を用いて、サーチウィンドウ（第１の探索領域）内の画素データの全探索のブロックマッチングを行う。ここでは、まず当該ブロックの画素データと、サーチウィンドウ内の全領域から順次切り出した(以下、切り出したブロック位置のことを探索点と呼ぶ)、当該ブロックに対応する形状および大きさの画素データとを比較し相関算出（第１の相関算出）を行う。そして、相関の高い（符号化誤差の少ない）探索点（第１のブロック位置）を高い順に所定数（ｍ点）選択する（第１の選択）。なお、本実施形態では、ｍ＝１０の場合を説明する。
【００１９】
図３ｂでは、階層４のウィンドウ１００４において、Ｐ１からＰ１０までの探索点が求められた様子を示している。以下のステップでは、Ｐ１からＰ１０までの各探索点について処理を行う。
【００２０】
次に、ステップＳ１０４において、ループ変数ｉに初期値１を代入する。更に、ステップＳ１０５では、階層ｎ、即ち階層４についてステップＳ１０３での探索結果に含まれるｍ点のうち、ｉ番目に結果の良好な探索点Ｐｉを選択する。
続くステップＳ１０６では、階層ｎ−１、即ち階層３の符号化画像（第２の階層画像）と参照画像（第２の参照階層画像）とを用いて、計９探索点を探索領域（第２の探索領域）として探索を行う。この９探索点は、階層３のサーチウィンドウのＰｉに対応する探索点およびその上下左右斜め方向に隣接する１画素分ずらした８つの探索点により定義される。即ち、階層３における当該ブロック（第２のブロック）に対応する形状および大きさの画素データとを比較し相関算出（第２の相関算出）を行う。そして、最も相関の高い探索点を求める。本実施形態では１画素分ずらした合計９探索点で説明するが、全面探索でなければこの限りでは無く、演算量と符号化効率との兼合いとなる。
【００２１】
図３ｂでは、階層３のウィンドウ１００３において、Ｐ１からＰ１０までの探索点のそれぞれを基準に設定される９探索点の領域（第２の探索領域）を示している。例えば、領域１００５は、Ｐ１について設定された９探索点領域を示している。以下では、これらの９探索点で構成される各領域について処理を行う。
【００２２】
続くステップＳ１０７では、ループ変数ｉに１を加算する。ステップＳ１０８では、ループ変数ｉを探索点数ｍと比較し、ｉの方が大きければ（ステップＳ１０８において「ＹＥＳ」）ステップＳ１０９へ移行する。一方、ｉがｍ以下であれば（ステップＳ１０８において「ＮＯ」）、ステップＳ１０５に戻って、処理を継続する。即ち、ｍ＝１０となるＰ１０の探索点について階層３での探索が終わるまでステップＳ１０５からステップＳ１０８までの処理が繰り返される。
【００２３】
次に、ステップＳ１０９では、ループ変数ｊに初期値ｎ−２を代入する。なお、本実施形態では、ｎ＝４であるので、ｊ＝２となる。更に、ステップＳ１１０では、階層ｊ＋１において、９探索点で構成される合計９０探索点について行ったサーチの結果に基づき、最も相関の高い探索点（第２のブロック位置）Ｐｂを選択する（第２の選択）。例えば、階層３の場合には、ステップＳ１０５からＳ１０７において、Ｐ１からＰ１０までの各探索点に基づき９探索点で構成される領域について行ったサーチ結果から相関が最も高い探索点（第２のブロック位置）をＰｂとして選択する。
【００２４】
図３ｂでは、ウィンドウ１００３において設定された１０個の探索点のうち、Ｐ１を基準に設定された領域１００５内での探索点１００６が、階層３において最も相関の高い探索点（第２のブロック位置）Ｐｂとされた場合を示している。
【００２５】
続くステップＳ１１１では、階層ｊ、即ち、１階層分だけ解像度の高い階層に移り、Ｐｂに対応する探索点に基づき、９探索点領域（第３の探索領域）を設定する。その上で、階層ｊにおける符号化ブロック（第３のブロック）の画素データと、９探索点領域（第３の探索領域）内の画素データとを比較して相関算出（第３の相関算出）を行う。そして、最も相関の高い探索点（第３のブロック位置）を選択する（第３の選択）。
【００２６】
続くステップＳ１１２では、ループ変数ｊの値を１つ減らして、ステップＳ１１３に移行する。ステップＳ１１３では、ループ変数ｊを０と比較し、ｊ＝０であればステップＳ１１４へ移行し、０でなければステップＳ１１０に戻って処理を繰り返す。即ち、階層１での探索が終わるまでステップＳ１１０からＳ１１３のループが繰り返される。
【００２７】
図３ｂでは、階層２のウィンドウ１００２において、探索点（第２のブロック位置）１００６に基づく９探索点領域（第３の探索領域）１００７が設定され、該領域内で最も相関の高い探索点（第３のブロック位置）１００８が選択された場合を示す。また、階層１のウィンドウ１００１において、探索点（第３のブロック位置）１００８に基づく９探索点領域（第４の探索領域）１００９が設定されている。そして、該領域内で行われた相関算出（第４の相関算出）の結果として、最も相関の高い探索点（第４のブロック位置）１０１０が選択されている。
【００２８】
ステップＳ１１４では、階層１での探索で最も相関の高い点（第４のブロック位置、画素位置）に基づいて、動きベクトル算出を行う。図３ｂの場合には、探索点１０１０に基づいて、動きベクトルが算出される。
【００２９】
以上のように、本実施形態によれば、従来の階層サーチで行われてきた３階層サーチからさらに１階層分だけ解像度の低い階層を用いた４階層サーチを行う。そして、より解像度の低い、即ちデータ数が少ない低階層のみでフルサーチを行うために、動きベクトル探索における比較演算回数を大幅に削減することが可能である。また、フルサーチにおける探索結果を１つに絞り込まず、複数（上記では１０個）の候補を設定し、各候補について上位の階層における探索を行うことを特徴とする。
【００３０】
なお、上記で探索点を決定するための探索を行う際に、１画素単位の探索のみならず、半画素単位、或いは、４分の１画素単位の探索を行っても良い。
【００３１】
図４は、各探索方式における画素値の演算回数の比較表を示す。比較されるのは、探索範囲縦横３２画素のフルサーチ４０１、同１６画素の対数サーチ４０２、同３２画素の４階層サーチ４０３、同３２画素の本提案方式サーチ４０４、同３２画素の特許文献１の３階層サーチ４０５である。なお、４階層サーチ４０３では、最も低い解像度の階層をフルサーチし、その後は最良結果を示す探索点周辺９点をサーチしている。
【００３２】
また、図５は、動きの少ない画像及び動きの多い画像において、各フレームを１６×１６の大きさのブロックに分割して動き探索を行った時の、動きベクトル探索結果のＳＡＤを比較したものである。動きの少ない画像とは、ＢＴＡ標準動画像Ｎｏ.４に独自の画像ブレを付加したものであり、動きの多い画像は、ＢＴＡ標準動画像Ｎｏ.３５に独自の画像ブレを付加したものである。ＳＡＤとは、Sum of Absolute Differencesの略であり、画素ごとの絶対差分和を示す。このＳＡＤは、値が小さいほど動きベクトル探索方式の性能がよい。
【００３３】
図４、図５から、３階層サーチ（特許文献１）は、フルサーチに迫る探索性能を示す一方、比較演算回数が対数サーチの２倍程度に増大することが分かる。また、単純な４階層サーチ方式では、探索回数を対数サーチの１／２以下、３階層サーチ（特許文献１）の１／５に減らすことができるが、動きの少ない画像における探索性能は対数サーチ方式より下がることが判る。
【００３４】
これに対して本提案の動き探索方式では、探索回数を対数サーチの１／２、３階層サーチ（特許文献１）の１／４程度に抑えつつ、動きの少ない画像、動きの多い画像の双方で３階層サーチ(特許文献１)に匹敵する探索性能を示している。
【００３５】
次に、上述の動きベクトル探索方法を実行するための、符号化装置の動作について、図２のブロック図を参照して説明する。ここで符号化される対象の画像を符号化画像、動きベクトル探索のために参照される、時間的に前後した位置の画像を参照画像と呼ぶ。
【００３６】
符号化画像は、図６における６０１がブロック単位に分割され、６０２の先頭ブロックから６０３の終端ブロックまで順に符号化が行われる。また、参照画像は、例えば符号化画像におけるブロック６０４を符号化している時には、当該ブロック及びその周辺領域をサーチウィンドウ６０５として、参照画像の対応する領域が動きベクトルの探索範囲となる。ここで、サーチウィンドウ６０５の画像データは毎回全てを更新(読み取り)する必要は無い。すなわち前のブロック(左隣)の動きベクトル探索におけるサーチウィンドウと重複する部分を再び利用し、重複しない部分６０６、すなわちサーチウィンドウの右側部分だけを更新すればよい。
【００３７】
図２において、フレームメモリＡ（２０１）は、入力された符号化画像データ２１１および参照画像データ（局所復号画像データ）を格納するフレームメモリである。階層画像作成部２０２は、フレームメモリＡ（２０１）の画像データから解像度を落とした階層画像を作成する。フレームメモリＢ（２０３）は、解像度を落とした階層画像を格納するフレームメモリであり、符号化画像と参照画像それぞれの階層画像を格納する。
【００３８】
動きベクトル探索部２０４は、フレームメモリＡ（２０１）及びフレームメモリＢ（２０３）からの符号化画像と参照画像データに基づいて動きベクトルの探索を行う。動きベクトルの探索は前述の各階層画像について前述の方法で動き探索される。減算器２１３は、動き補償部２１０からの予測画像とフレームメモリＡからの符号化画像との差であるブロック間差分データを求める。周波数変換部２０５は、ブロック間差分データを周波数変換処理しブロック係数データに変換する。量子化部２０６は、ブロック係数データを量子化する。可変長符号化部２０７は、量子化されたブロック係数データを可変長符号化し、符号化データ２１２を出力する。
【００３９】
逆量子化部２０８は、量子化されたブロック係数データに逆量子化を行う。逆周波数変換部２０９は、再構成されたブロック係数データを画像空間のブロック間差分データに変換する。加算器２１４は、逆周波数変換部２０９の出力と動き補償部２１０の予測画像とを加算する。動き補償部２１０は、動きベクトル探索部２０４からの動きベクトル探索結果を用いて、フレームメモリＡから予測画像を減算器２１３に出力する。
【００４０】
以上の構成において、符号化画像データ２１１は、まずフレームメモリＡ（２０１）に書き込まれる。次に、階層画像作成部２０２は、符号化画像２１１および参照画像となる局所復号画像データをフレームメモリＡ（２０１）より読み出し、解像度を落とした階層画像を作成し、フレームメモリＢ（２０３）に格納する。
【００４１】
動きベクトル探索部２０４は、まず階層画像を解像度の低い順にフレームメモリＢ（２０３）より読み出し、順次動き探索を行う。最後に、フレームメモリＡ（２０１）より、オリジナルの解像度の符号化画像及び参照画像を読み出して動き探索を行い、最終的な動きベクトルを求める。動きベクトル探索部２０４における処理の詳細は、図１に基づいて説明したとおりであるので、ここでは省略する。
【００４２】
動き補償部２１０は、動きベクトル探索部２０４における動きベクトル探索結果を元に、局所復号画像データから、予測画像を求め、減算器２１３に出力する。減算器２１３では、符号化画像データと予測画像データとの差分を取る事で予測誤差を求め周波数変換部２０５へ送る。周波数変換部２０５は、予測誤差であるブロック間差分データを周波数ドメインのブロック係数データに変換し、量子化部２０６へブロック係数データを送る。量子化部２０６はブロック係数データを量子化し、可変長符号化部２０７および逆量子化手段２０８へ送る。
【００４３】
可変長符号化部２０７は、量子化されたブロック係数データに可変長符号化を施し、符号化データ２１２を出力する。逆量子化部２０８は量子化されたブロック係数データに逆量子化を行い、再構成されたブロック係数データを逆周波数変換部２０９へ送る。逆周波数変換部２０９は、再構成されたブロック係数データを画像空間でのブロック間差分データに変換し、加算器２１４へ送る。
【００４４】
加算器２１４は、画像空間でのブロック間差分データと予測画像とを加算して局所復号画像データ、すなわち次符号化対象画像の参照画像を求め、フレームメモリＡ２０１へ書き込む。
【００４５】
以上の処理をブロックの数だけ行い、当該符号化対象画像の符号化が完了する。
【００４６】
なお、図７は３階層サーチ（特許文献１）と、本提案方式サーチにおける画像データの転送量との比較例を示す。本提案方式では４階層の画像を作成するため、階層画像作成段階では、階層４の分だけ３階層サーチ（特許文献１）と比較してデータ転送量が若干多くなる。しかし、サーチを行う際には、３階層サーチ（特許文献１）に比べてデータを読み込む範囲が少ないため、結果的に１.５フレームサイズ分、データ転送量を少なくすることができる。
【００４７】
以上のように、本実施形態に説明した探索方式によれば、探索回数の減少と、高い探索性能とを両立することができる。また、データ転送料を少なくして、効率的な探索を行うことができる。
【００４８】
［その他の実施形態］
なお、本発明は、複数の機器（例えばホストコンピュータ、インタフェイス機器、リーダ、プリンタなど）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機、ファクシミリ装置など）に適用してもよい。
【００４９】
また、本発明の目的は、前述した機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムに供給し、そのシステムがプログラムコードを読み出し実行することによっても達成される。この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現し、そのプログラムコードを記憶した記憶媒体は本発明を構成する。また、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているオペレーティングシステム（ＯＳ）などが実際の処理の一部または全部を行い、その処理によって前述した機能が実現される場合も含まれる。
【００５０】
さらに、以下の形態で実現しても構わない。すなわち、記憶媒体から読み出されたプログラムコードを、コンピュータに挿入された機能拡張カードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込む。そして、そのプログラムコードの指示に基づき、その機能拡張カードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行って、前述した機能が実現される場合も含まれる。
【００５１】
本発明を上記記憶媒体に適用する場合、その記憶媒体には、先に説明したフローチャートに対応するプログラムコードが格納されることになる。
【図面の簡単な説明】
【００５２】
【図１】発明の実施形態に対応する動きベクトル探索処理の一例を示すフローチャートである。
【図２】発明の実施形態に対応する符号化装置の構成例を示す図である。
【図３ａ】発明の実施形態に対応する階層画像の作成方法を説明するための図である。
【図３ｂ】発明の実施形態に対応する探索点の設定および選択を説明するための図である。
【図４】動きベクトル探索方式に応じた演算回数の比較表である。
【図５】動きベクトル探索方式に応じた探索性能の比較グラフである。
【図６】発明の実施形態に対応する、ブロック単位の動き探索におけるブロック及びサーチウィンドウの説明図である。
【図７】動きベクトル探索方式に応じたメモリ転送量の比較表である。
【図８】階層型動きベクトル探索の従来法を説明するための図である。
【図１】
2008301085.tif 000003
【図２】
2008301085.tif 000004
【図３ａ】
2008301085.tif 000005
【図３ｂ】
2008301085.tif 000006
【図４】
2008301085.tif 000007
【図５】
2008301085.tif 000008
【図６】
2008301085.tif 000009
【図７】
2008301085.tif 000010
【図８】
2008301085.tif 000011