(57)【要約】【課題】  少ない演算量で広範囲・高精度な動きベクトル探索方法及びその装置を提供する【解決手段】  原画像と参照画像に対し縮小した画像を各々生成する。縮小参照画像上の探索領域上で、所定間隔で検索し、動きベクトル候補を複数選択する。段階的に探索間隔を狭くして探索する。原解像度の参照画像上で縮小画像上で探索された動きベクトル候補が示す位置を中心にして、その周辺部を含めて動きベクトルを探索する。  【選択図】  図１
2009033266.tif 000002
【特許請求の範囲】
【請求項１】
動画像の圧縮符号化のための動きベクトル探索方法であって、
符号化対象画像と参照画像の解像度を縮小し、縮小符号化対象画像と縮小参照画像とを生成する解像度縮小工程と、
前記符号化対象画像を構成する複数のブロックのうち、動きベクトル探索対象のブロックの該符号化対象画像における位置に基づき、前記参照画像における探索領域を決定する決定工程と、
前記縮小参照画像から前記探索領域に対応する縮小探索領域を抽出し、動きベクトル探索を行うための複数の第１の探索点を該縮小探索領域に設定する探索点設定工程と、
前記縮小探索領域において、前記第１の探索点毎に、前記符号化対象画像における動きベクトル探索対象のブロックに対応する、前記縮小符号化対象画像の縮小ブロックの相関度を算出し、前記複数の第１の探索点のうち相関度上位の複数の第２の探索点を決定する第１の探索工程と、
前記第１の探索工程で得られた前記複数の第２の探索点のそれぞれの周囲に第３の探索点を設定し、該第２と第３の探索点に基づき、前記縮小探索領域における前記縮小ブロックの相関度を算出し、相関度が最も高い第４の探索点を決定する第２の探索工程と、
前記第２の探索工程で得られた前記第４の探索点の周囲に第５の探索点を設定し、該第４と第５の探索点に基づき、前記縮小探索領域における前記縮小ブロックの相関度を算出し、相関度が最も高い第６の探索点を決定する第３の探索工程と、
前記第３の探索工程で得られた前記第６の探索点に対応する、前記探索領域における第７の探索点と該第７の探索点の周囲の第８の探索点とを設定し、該第７と第８の探索点に基づき、前記探索領域における前記動きベクトル探索対象のブロックの相関度を算出し、相関度が最も高い第９の探索点を決定する第４の探索工程と、
前記第４の探索工程で得られた前記第９の探索点に基づいて、動きベクトルを算出する動きベクトル算出工程と
を備えることを特徴とする動きベクトル探索方法。
【請求項２】
前記第１の探索点は、前記縮小探索領域の中心周辺は第１の画素間隔で設定され、それ以外の領域は、前記第１の画素間隔よりも粗い第２の画素間隔で設定されることを特徴とする請求項１に記載の動きベクトル探索方法。
【請求項３】
前記第３の探索点は、前記第２の探索点を中心として第１の画素間隔で設定されることを特徴とする請求項１又は２に記載の動きベクトル探索方法。
【請求項４】
前記第５の探索点は、前記第４の探索点を中心として、前記第１の画素間隔よりも密な第３の画素間隔で設定されることを特徴とする請求項１又は２に記載の動きベクトル探索方法。
【請求項５】
前記第８の探索点は、前記第７の探索点を中心として、前記参照画像の解像度における前記第３の画素間隔で設定されることを特徴とする請求項４に記載の動きベクトル探索方法。
【請求項６】
動画像の圧縮符号化のための動きベクトル探索装置であって、
符号化対象画像と参照画像の解像度を縮小し、縮小符号化対象画像と縮小参照画像とを生成する解像度縮小手段と、
前記符号化対象画像を構成する複数のブロックのうち、動きベクトル探索対象のブロックの該符号化対象画像における位置に基づき、前記参照画像における探索領域を決定する決定手段と、
前記縮小参照画像から前記探索領域に対応する縮小探索領域を抽出し、動きベクトル探索を行うための複数の第１の探索点を該縮小探索領域に設定する探索点設定手段と、
前記縮小探索領域において、前記第１の探索点毎に、前記符号化対象画像における動きベクトル探索対象のブロックに対応する、前記縮小符号化対象画像の縮小ブロックの相関度を算出し、前記複数の第１の探索点のうち相関度上位の複数の第２の探索点を決定する第１の探索手段と、
前記第１の探索手段で得られた前記複数の第２の探索点のそれぞれの周囲に第３の探索点を設定し、該第２と第３の探索点に基づき、前記縮小探索領域における前記縮小ブロックの相関度を算出し、相関度が最も高い第４の探索点を決定する第２の探索手段と、
前記第２の探索手段で得られた前記第４の探索点の周囲に第５の探索点を設定し、該第４と第５の探索点に基づき、前記縮小探索領域における前記縮小ブロックの相関度を算出し、相関度が最も高い第６の探索点を決定する第３の探索手段と、
前記第３の探索手段で得られた前記第６の探索点に対応する、前記探索領域における第７の探索点と該第７の探索点の周囲の第８の探索点とを設定し、該第７と第８の探索点に基づき、前記探索領域における前記動きベクトル探索対象のブロックの相関度を算出し、相関度が最も高い第９の探索点を決定する第４の探索手段と、
前記第４の探索手段で得られた前記第９の探索点に基づいて、動きベクトルを算出する動きベクトル算出手段と
を備えることを特徴とする動きベクトル探索装置。
【請求項７】
請求項６に記載の動きベクトル探索装置を用いて動きベクトル探索を行い、符号化対象画像の圧縮符号化を行う符号化処理装置。
【請求項８】
請求項１乃至５のいずれか１項に記載の動きベクトル探索方法を、コンピュータに実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動きベクトル探索方法、動きベクトル探索装置、符号化装置及びコンピュータプログラムに関する。
【背景技術】
【０００２】
Ｈ.２６ｘやＭＰＥＧ等の符号化方式では、画像１フレームを複数のブロックに分割して、各ブロック単位に圧縮符号化を行う。圧縮符号化の方式には、時間的相関性を利用した符号化方式(inter符号化)および空間的相関性を利用した符号化方式(intra符号化)がある。時間的相関を利用した符号化方式はフレーム間の動きを探索し、当該ブロックの動きベクトルおよびブロック間差分を求めて符号化を行う。
【０００３】
最も相関の高い動きベクトルを求めるには全探索をする必要がある。しかし、例えば１６×１６画素のブロックを参照フレーム上の探索領域６４×６４画素位置全てと比較する場合、ＳＡＤ値で相関演算すれば、ブロック内の画素それぞれの差分の総和を取るのに１６×１６×２＝５１２回の加減算が必要となる。さらに各探索領域について演算する必要があるので６４×６４＝４０９６ポイントで繰りかえし演算して合計すると５１２Ｘ４０９６＝２０９７１５２回の演算と、４０９６ポイントの相関性判定処理が必要となり、計算量が膨大になってしまう。ここでの探索領域は、探索中心点（中心位置）についてであり、画像上では比較ブロックサイズ分さらに広がることになる。
【０００４】
そこで、探索回数を減らして適切な動きベクトルを高速に求めるために、対数サーチ方式や、階層サーチ方式（特許文献１を参照）などの様々な方式が提案されている。
【０００５】
対数サーチ方式は、図１２に示すように、まず第１段として、粗い探索点の間隔でｎ×ｎ点の動きベクトル探索を行い、最もマッチングのとれた位置を中心に、探索点の間隔を、第１段のときの半分にして第２段の探索を行う。同様の処理を複数段繰り返して、粗から密へ探索点の間隔を絞っていき動きベクトルを検出する方法である。n＝３で、３２×３２画素の探索範囲の場合、４段で終了し、探索点数は９＋８＋８＋８＝３３点ですむ。フルサーチの場合、３２×３２＝１０２４点の探索が必要であるから、約１／３３の処理量に削減される。
【０００６】
階層サーチ方式は、図１３のように、入力画像１３０３の解像度を落として順次低解像度の画像を生成し、最も低解像度の画像１３０１における所定探索領域から低解像度の画像１３０１の画素を用いて探索を開始する。そして探索結果を順次、次に低い解像度の所定探索領域の探索開始点に反映させていく。低解像度画像すなわちデータ量の少ない画像で高解像と同じ範囲を探索することで、演算量を少なくする事が可能となり、探索範囲を広げた時の比較演算回数の増加を抑えることができる。
【０００７】
しかしながらH.２６４およびMPEG符号化方式で用いられるブロックサイズすなわち動き探索を行う単位は最大でも１６×１６画素サイズであり、解像度を１／８にすると同じ画像空間では２×２画素になってしまう。この場合のブロックマッチングは計４画素どうしの比較となり、ブロックマッチングの精度は低下する。
【０００８】
特許文献１の階層サーチ方式は、ブロック単位の動きベクトル探索において、入力画像に対して２回のダウンサンプリングを行い、３階層の画像を用いて探索を行っている。このようにブロック単位の動きベクトル探索に使用する場合は一般的に３階層、すなわち解像度１／４、ブロックの大きさが４×４画素サイズまでの階層化しか行わないことが一般的である。
【特許文献１】特許第３６１５９６３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
対数サーチ方式は、特に線画部分などの高解像度部分では、初期段階での粗い探索位置とマッチングすべき位置が偶然合致している場合を除いて、探索初期段階で誤った動きベクトルを検出する場合がある。ゆえに、動きベクトルの精度の低下から、動き補償予測画像における予測誤差を大きくしてしまうという問題がある。
【００１０】
階層型サーチ方式は、階層を増やすことで広範囲のサーチを少ない演算回数で行えるが、低解像度の階層における探索精度が悪いため３階層程度の階層化が一般的である。その結果として階層型サーチ方式の特徴を活かし演算量を大きく減らすことができないという問題が生ずる。
【００１１】
そこで、本発明は少ない演算量で広範囲、かつ、高精度な動きベクトル探索を可能とすることを目的とする。
【課題を解決するための手段】
【００１２】
上記課題を解決するための本発明は、動画像の圧縮符号化のための動きベクトル探索方法であって、
符号化対象画像と参照画像の解像度を縮小し、縮小符号化対象画像と縮小参照画像とを生成する解像度縮小工程と、
前記符号化対象画像を構成する複数のブロックのうち、動きベクトル探索対象のブロックの該符号化対象画像における位置に基づき、前記参照画像における探索領域を決定する決定工程と、
前記縮小参照画像から前記探索領域に対応する縮小探索領域を抽出し、動きベクトル探索を行うための複数の第１の探索点を該縮小探索領域に設定する探索点設定工程と、
前記縮小探索領域において、前記第１の探索点毎に、前記符号化対象画像における動きベクトル探索対象のブロックに対応する、前記縮小符号化対象画像の縮小ブロックの相関度を算出し、前記複数の第１の探索点のうち相関度上位の複数の第２の探索点を決定する第１の探索工程と、
前記第１の探索工程で得られた前記複数の第２の探索点のそれぞれの周囲に第３の探索点を設定し、該第２と第３の探索点に基づき、前記縮小探索領域における前記縮小ブロックの相関度を算出し、相関度が最も高い第４の探索点を決定する第２の探索工程と、
前記第２の探索工程で得られた前記第４の探索点の周囲に第５の探索点を設定し、該第４と第５の探索点に基づき、前記縮小探索領域における前記縮小ブロックの相関度を算出し、相関度が最も高い第６の探索点を決定する第３の探索工程と、
前記第３の探索工程で得られた前記第６の探索点に対応する、前記探索領域における第７の探索点と該第７の探索点の周囲の第８の探索点とを設定し、該第７と第８の探索点に基づき、前記探索領域における前記動きベクトル探索対象のブロックの相関度を算出し、相関度が最も高い第９の探索点を決定する第４の探索工程と、
前記第４の探索工程で得られた前記第９の探索点に基づいて、動きベクトルを算出する動きベクトル算出工程と
を備えることを特徴とする。
【発明の効果】
【００１３】
本発明によれば、少ない演算量で広範囲、かつ、高精度な動きベクトル探索が可能となる。また、全探索での動きベクトルの検出精度を低下させる事なく、演算量を低減し演算コストの低減を図る事が可能となる。
【発明を実施するための最良の形態】
【００１４】
以下、添付する図面を参照して発明の実施形態を説明する。
【００１５】
［第１の実施形態］
図１を参照して、発明の実施形態に対応する動きベクトル探索方法に基づいた符号化処理装置の処理手順を説明する。
【００１６】
本実施形態では、動画像における符号化対象の画像を「符号化対象画像」と呼び、動きベクトル探索のために参照される時間的に前後した位置の画像を「参照画像」と呼ぶ。なお、図１は符号化対象画像内の１ブロックについての動きベクトル探索方法を示しているが、実際には画像を構成する複数ブロックの全てについて当該処理が適用される。
【００１７】
なお、ブロックの大きさは発明の実施に際して特に規定されるものではないが、本実施形態では原解像度において１６×１６画素で構成されるブロックを例に挙げて説明する。また、本実施形態では、符号化対象画像上のブロックと参照画像上の探索点を基準に設定されるブロックとの相関度を、各画素の差分の絶対値の総和を示すＳＡＤ（差分絶対値和）値により表す場合を説明する。但し、相関度の算出方法として、ＳＡＤはあくまで一例であって、これに限定されるものではないことは当業者であれば直ちに理解するであろう。
【００１８】
図１において、まずステップＳ１０１では、符号化対象画像および参照画像の縮小画像を作成する。縮小画像の作成方法は公知技術を用いれば良いが、画素中心位置の変化に注意する必要がる。図２の手法は画素中心位置が１／２画素ずれる場合である。図２では、原画像の隣接する４画素の輝度値（２５４、３、１０８、２７）を加算し、当該位置の画素値（３９２）としている。これにより、原画像に対して解像度が縦横それぞれ１／２、画素数１／４の縮小画像を作成することができる。この場合は、画素中心位置のずれを考慮してベクトル検索をする必要がある。
画像の低解像度化の手法はこれに限定される事なく、プレフィルタ処理の後にダウンサンプリングを行う手法でも良く、その場合は演算処理処理は増えるが画像中心位置がずれないのでより良い結果が得られる。その他の公知技術を用いても良い。
【００１９】
これ以降の説明では、縮小された符号化対象画像（縮小符号化対象画像）及び参照画像（縮小参照画像）上で動きベクトルを探索する際には、ブロックのサイズも同様にして解像度を縦横１／２に縮小して相関度を求める。即ち、縮小画像上では８×８画素のブロック単位でＳＡＤ値を算出する。以降、８×８画素のブロックを「縮小ブロック」と呼ぶ。また、低解像度処理による画素中心位置のずれが無いものとして説明する。
【００２０】
次に、ステップＳ１０２では、符号化対象画像上の動きベクトル探索対象のブロックの中心位置に基づいて、参照画像及び縮小参照画像から探索領域を抽出する。ここで、図３に示すように、探索領域は原解像度の参照画像について６４×６４画素領域が設定される。従って、原解像度と同じ空間範囲に対応する解像度縮小後の探索領域（縮小探索領域）は、３２×３２画素領域となる。
【００２１】
次に、ステップＳ１０３では、ステップＳ１０２で切り出した縮小探索領域にＮ個の探索点設定（第１の探索点の設定）を行い、第１の探索点毎に縮小ブロックとのＳＡＤ値を算出して相関度を求める。そして、Ｎ個の探索点（第１の探索点）について算出したＳＡＤ値のうち、最も値の小さい方から（相関度の高い方から）Ｍ個、本実施形態では３つの探索点（第２の探索点）を決定する。なお、相関度上位３つの探索点としたのは一例であって、相関度上位の２つ又は４つなどの２以上探索点であれば良い。従ってＭは２≦Ｍ＜Ｎの整数となる。
【００２２】
縮小探索領域における探索点（第１の探索点）の設定例は、図４に示す通りである。図４では、Ｎ＝４９として、４９個の探索点を設定した場合を示している。図４において、縮小探索領域は、３２×３２画素の領域であって、４画素毎に合計４９個の探索点が設定されている。このように本実施形態では、探索領域全面で均等な画素間隔でＮ点を設定したが、例えば次の様な設定としても良い。縮小探索領域の中心周辺の領域では第１の画素間隔（２画素間隔）で探索点を設定し、中心から離れたそれ以外の領域では第１の画素間隔よりも粗い第２の画素間隔（４画素間隔）で探索点を設定する。このような構成としたのは、探索点中心に近い程フレーム間の相関が高い傾向にある為であるが、その分演算量が増えることになる。従って、探索精度と演算量のトレードオフとなる。
【００２３】
続くステップＳ１０４では、ステップＳ１０３で決定された相関度の高い上位３探索点（第２の探索点）の各々周囲８点に探索点（第３の探索点）を設定し、探索点毎に縮小ブロックとのＳＡＤ値を算出して相関度を求める。そして、各探索点について算出した合計２７個のＳＡＤ値のうち、値が最も小さい（相関度の高い）探索点（第４の探索点）を決定する。
【００２４】
相関度の高い上位３探索点（第２の探索点）を基準とした周囲８点の探索点（第３の探索点）を設定例は、図５に示す通りである。図５において、３探索点（第２の探索点）を探索点５０１、５０２及び５０３で示している。各探索点の周囲には、±２画素の領域５０４、５０５及び５０６がそれぞれ設定され、８探索点（第３の探索点）が設定される。このように、本実施形態では、相関度の高い上位３探索点を基準として、第１の画素間隔（２画素間隔）で探索点を設定している。
【００２５】
次に、ステップＳ１０５では、ステップＳ１０４で決定された最も相関度の高い探索点（第４の探索点）を基準として、周囲８点に探索点（第５の探索点）を更に設定し、探索点毎に縮小ブロックとのＳＡＤ値を算出して相関度を求める。そして、各探索点について算出した合計９個のＳＡＤ値のうち、値が最も小さい（相関度の高い）探索点（第６の探索点）を決定する。
【００２６】
相関度が最も高い探索点（第４の探索点）を基準とした周囲８点の探索点（第５の探索点）を設定例は、図６に示す通りである。図６において、探索点６０１が、ステップＳ１０４における該相関度が最高の探索点（第４の探索点）である。探索点６０１の周囲には、±１画素の領域６０２が設定され、８探索点（第５の探索点）が設定される。このように、本実施形態では、相関度が最高の探索点を基準として、第１の画素間隔より密な第３の画素間隔（１画素間隔）で探索点を設定している。
【００２７】
次に、ステップＳ１０６では、ステップＳ１０５で決定された最も相関度の高い探索点（第６の探索点）に対応する位置にある、原解像度の探索領域上の点（第７の探索点）及びその周囲８点（第８の探索点）を探索点として設定する。そして、探索点毎に動きベクトル探索対象のブロックとのＳＡＤ値を算出して相関度を求める。そして、各探索点について算出した合計９個のＳＡＤ値のうち、値が最も小さい（相関度の高い）探索点（第９の探索点）を決定する。
【００２８】
相関度が最も高い探索点に対応する点（第７の探索点）及びその周囲８点（第８の探索点）の、原解像度の参照画像の探索領域での設定例は図７に示す通りである。図７において、探索点７０１が、ステップＳ１０５で縮小探索領域上において該相関度が最高と決定された探索点に対応する、原解像度の参照画像の探索領域上の点（第７の探索点）である。探索点７０１の周囲には、±１画素の領域７０２が設定され、８探索点（第８の探索点）が設定される。このように、本実施形態では、相関度が最高の探索点を基準として、原解像度での第３の画素間隔（原解像度で１画素間隔）で探索点を設定している。
【００２９】
次に、ステップＳ１０７では、ステップＳ１０６で相関度が最高と認定された探索点（第９の探索点）に基づいて、動きベクトル算出を行う。例えば、図７の探索点７０３が、相関度が最高であると認定された場合は、動きベクトルは、矢印７０４のように設定することができる。
【００３０】
次に、本実施形態における動きベクトル探索方式を採用した場合の演算量と、従来の動きベクトル探索方式を採用した場合の演算量とを比較して説明する。
【００３１】
図８は、各探索方式におけるＳＡＤ値の算出対象となる画素の数を示す。以下、ＳＡＤ値算出画素数と記す。このＳＡＤ値算出画素数が多いほど、動きベクトル探索に必要な演算量が多いことを意味する。なお、以下では、動きベクトル探索対象のブロックサイズを１６×１６画素として説明する。
【００３２】
まず、フルサーチ(６４×６４画素)は、探索領域縦横６４×６４画素をフルサーチ(全探索)する方式である。参照フレーム上の探索領域６４×６４画素の全てに対して１６×１６画素のブロックのＳＡＤ値算出を行なうので、ＳＡＤ値算出画素数は６４×６４×１６×１６＝１０４８５７６と画素なる。
対数サーチ(３２×３２画素)は、探索領域縦横３２×３２画素の対数サーチ方式である。対数サーチ(３２×３２画素)では４段階のサーチを行なうので、探索点は９＋８＋８＋８＝３３点となる。この３３点に対して１６×１６画素のブロックのＳＡＤ値算出を行なうので、ＳＡＤ値算出画素数は３３×１６×１６＝８４４８画素となる。
対数サーチ(６４×６４画素)は、探索領域縦横６４×６４画素の対数サーチ方式である。対数サーチ(６４×６４画素)は、５段階のサーチを行なう。探索点は９＋８＋８＋８＋８＝４１点となる。この４１点に対して１６×１６画素のブロックのＳＡＤ値算出を行なうので、ＳＡＤ値算出画素数は４１×１６×１６＝１０４９６画素となる。
【００３３】
４階層サーチ(６４×６４画素)は、探索領域縦横６４×６４画素の４階層サーチ方式である。この４階層サーチ方式は、具体的には、最も低い解像度の階層をフルサーチし、その後は最良結果を示す探索点周辺８点を加えて合計９点をサーチしていく方式である。階層０を原画像の解像度とし、階層３を最も低い解像度の階層としたとき、ＳＡＤ値算出画素数は以下のようになる。階層３は原画像の１／８の解像度であるので、探索領域は縦横８×８画素、ブロックのサイズは２×２画素である。階層３ではフルサーチを行なうので、探索点は８×８＝６４点となる。階層３のＳＡＤ値算出画素数は探索点６４点にブロックのサイズ２×２画素を掛けて、６４×２×２＝２５６画素となる。階層２は原画像の１／４の解像度であるので、探索領域は縦横１６×１６画素、ブロックのサイズは４×４画素である。階層２で最良結果を示した探索点及びその周辺８点に対してサーチを行なうので、階層２のＳＡＤ値算出画素数は、探索点９点にブロックのサイズ４×４画素を掛けて、９×４×４＝１４４画素となる。階層１は原画像の１／２の解像度であるので、探索領域は縦横３２×３２画素、ブロックのサイズは８×８画素である。階層２で最良結果を示した探索点及びその周辺８点に対してサーチを行なうので、階層１のＳＡＤ値算出画素数は、探索点９点にブロックのサイズ８×８画素を掛けて、９×８×８＝５７６画素となる。階層０は原画像の解像度であるので、探索領域は縦横６４×６４画素、ブロックのサイズは１６×１６である。階層１で最良結果を示した探索点及びその周辺８点に対してサーチを行なうので、階層０のＳＡＤ値算出画素数は、探索点９点にブロックのサイズ１６×１６画素を掛けて、９×１６×１６＝２３０４画素となる。以上より、階層０〜３のＳＡＤ値算出画素数合計は、２３０４（階層０）＋５７６（階層１）＋１４４（階層２）＋２５６（階層３）＝３２８０画素となる。
【００３４】
特許文献１の３階層サーチ(６４×６４画素)は、探索領域縦横６４×６４画素のブロック単位の動きベクトル探索において、入力画像に対して２回のダウンサンプリングを行い、３階層の画像を用いて探索を行う特許文献１の方法である。原画像の１／４の解像度である階層２ではフルサーチを行なうので、ＳＡＤ値算出画素数は探索領域１６×１６画素にブロックのサイズ４×４画素を掛けて、１６×１６×４×４＝４０９６画素となる。原画像の１／２の解像度である階層１では、階層２の探索結果と周辺ブロックとの相関性を基に３点の探索中心点を求め、各々の探索中心点に対して５×５画素の探索領域を設定する。よって、探索点は５×５×３＝７５点となり、階層１のＳＡＤ値算出画素数はブロックのサイズ８×８画素に探索点７５点を掛けて、８×８×７５＝４８００画素となる。原画像である階層０では、階層１の探索結果を基に探索中心点を求め、探索中心点に対して５×５画素の探索領域、即ち点５×５＝２５点の探索点を設定する。よって、階層０のＳＡＤ値算出画素数はブロックのサイズ１６×１６画素に探索点２５点を掛けて、１６×１６×２５＝６４００画素となる。以上より、特許文献１の３階層サーチ(６４×６４画素)のＳＡＤ値算出画素数は、６４００（階層０）＋４８００（階層１）＋４０９６（階層２）＝１５２９６画素となる。
【００３５】
本発明に関る方法(６４×６４画素)は、探索領域縦横６４×６４画素の本実施形態の探索方法である。図１のステップＳ１０２での探索点は、図４より４９点である。縮小画像に対してサーチを行なうので、ブロックのサイズは８×８画素である。よって、ステップＳ１０２でのＳＡＤ値算出画素数は、４９×８×８＝３１３６画素である。図１のステップＳ１０３での探索点は、図５より２４点である。よって、ステップＳ１０３でのＳＡＤ値算出画素数は、２４×８×８＝１５３６画素である。図１のステップＳ１０４での探索点は、図５より８点である。よって、ステップＳ１０４でのＳＡＤ値算出画素数は、８×８×８＝５１２画素である。図１のステップＳ１０５での探索点は、図５より９点である。よって、ステップＳ１０５でのＳＡＤ値算出画素数は、原画像に対するサーチであるのでブロックのサイズは１６×１６画素なので、９×１６×１６＝２３０４画素である。以上より、本発明に関る方法(６４×６４画素)のＳＡＤ値算出画素数は、２３０４（ステップＳ１０５）＋５１２（ステップＳ１０４）＋１５３６（ステップＳ１０３）＋３１３６（ステップＳ１０２）＝７４８８画素である。
【００３６】
次に、図９は動きの少ない画像及び動きの多い画像において、各フレームを１６×１６の大きさのブロックに分割して動き探索を行った時の、動きベクトル探索結果のＳＡＤ値を比較したものである。縦軸は１６×１６画素のブロック毎ＳＡＤの１フレームでの平均ＳＡＤ値であり、ＳＡＤ値が小さいほど動きベクトル探索方式の性能がよいことを示している。
【００３７】
図８及び図９から、本実施形態の動き探索方法は、演算量を対数サーチ（縦横６４×６４画素）の約７１％、３階層サーチ(特許文献１)の約４９％程に抑えながら、探索性能において３階層サーチ(特許文献１)に匹敵する性能を示している。
【００３８】
以上に説明したように、本実施形態の動きベクトル探索方法では、解像度を削減した縮小画像上での処理ステップで最も相関度の高い１点だけでなく、相関度が高い上位のＭ点（上記実施例では上位３点）を選択している。さらにその周囲（上記実施例では８点）の相関度を求める処理を行っている。これにより、解像度を削減した縮小画像上での探索段階で誤った動きベクトルを検出する確率を低減している。また、探索初期段階において、解像度を１／２に落とした縮小画像上で相関度を求めているため、演算量を従来の対数サーチ方式に比べて削減することができる。
【００３９】
さらに、本実施形態の動きベクトル探索方法では、原解像度の画像と１／２解像度の画像の２階層のみを用いている。よって、３つ以上の階層を用いる従来の階層サーチ方式よりも、低解像度の画像を作るための処理を削減することができる。また、解像度の低下を１／２に留めているので、低解像度の階層における探索精度の低下を最低限に抑えている。
【００４０】
［第２の実施形態］
次に、第１の実施形態で説明した動きベクトル探索方法を実行する符号化処理装置の処理手順について説明する。
本実施形態では、符号化対象画像は図１０における１００２のように、画像１００１をブロック単位に分割し、先頭ブロック１００２から終端ブロック１００３まで順に符号化が行われる。また、参照画像は、例えば符号化対象画像におけるブロック１００４を符号化している時には、当該ブロック及びその周辺領域を探索領域１００５として、参照画像の対応する領域が動きベクトルの探索範囲となる。ここで、探索領域１００５の参照メモリー内の画像データは毎回全てを更新(読み取り)する必要は無い。例えば、前のブロック(左隣)の動きベクトル探索における探索領域と重複する部分を再び利用し、重複しない部分１００６（探索領域の右側部分）だけを更新すればよい。
【００４１】
次に、図１１を参照して、本実施形態における符号化処理装置について説明する。図１１は、当該符号化処理装置１１００の構成の一例を示す図である。
【００４２】
図１１において１１１１は符号化処理の対象となる符号化対象画像である。１１１３は局所復号画像で参照画像である。
【００４３】
フレームメモリＡ（１１０１）には、符号化対象画像１１１１および参照画像１１１３が格納される。縮小画像作成部１１０２は、フレームメモリＡ（１１０１）に格納されている符号化対象画像１１１１と参照画像１１１３をの水平及び垂直の解像度をそれぞれ１／２に落とした縮小画像を作成する。
【００４４】
フレームメモリＢ（１１０３）は、解像度を落とした縮小画像が格納される。動きベクトル探索部１１０４は、フレームメモリＡ（１１０１）およびフレームメモリＢ（１１０３）にそれぞれ格納された画像を利用して、符号化対象画像１１１１の各ブロックについて動きベクトルを探索する。動き補償部１１１０は、動きベクトル探索結果と参照画像とから予測画像１１１４を生成し、減算器１１１５と、加算器１１１６へ出力する。
【００４５】
減算器１１１５は、フレームメモリＡ（１１０１）から出力された符号化対象ブロック画像と、動き補償部１１１０から出力された予測画像との差分によりブロック間差分データ（フレーム間予測誤差）を算出して、周波数変換部１１０５に出力する。
【００４６】
周波数変換部１１０５は、フレームメモリＡ（１１０１）から出力された符号化対象ブロック画像と、動き補償部１１１０から出力された予測画像との差分として得られるブロック間差分データを、ブロック係数データに変換する。量子化部１１０６はブロック係数データを量子化する。可変長符号化部１１０７は量子化されたブロック係数データに可変長符号化を施し、符号化対象画像の符号化処理結果である符号化データ１１１２を出力する。
【００４７】
逆量子化部１１０８は、量子化部１１０８で量子化されたブロック係数データを逆量子化する。逆周波数変換部１１０９は、逆量子化により得られたブロック係数データを再構成されたブロック間差分データに変換する。
【００４８】
加算器１１１６は、逆周波数変換部１１０９から出力された再構成されたブロック間差分データと、動き補償部１１１０から出力された予測画像とを加算して、符号化対象ブロック画像を再構成し局所復号画像として出力する。
【００４９】
次に、該符号化処理装置１１００における動作を説明する。入力された符号化対象画像１１１１は、まずフレームメモリＡ（１１０１）に書き込まれる。なお、フレームメモリＡ（１１０１）には、加算器１１１６で再構成された局所復号画像が参照画像として格納されている。縮小画像作成部１１０２は符号化対象画像１１１１および参照画像１１１３をフレームメモリＡ（１１０１）より読み出し、解像度を１／２に落とした縮小画像を作成し、フレームメモリＢ（１１０３）へ格納する。
【００５０】
動きベクトル探索部１１０４は、符号化対象画像１１１１と参照画像１１１３の縮小画像をフレームメモリＢ（１１０３）より読み出し、動き探索を行う。次に、フレームメモリＡ（１１０１）から元の解像度の符号化対象画像１１１１及び参照画像１１１３を読み出して動き探索を行い、最終的な動きベクトルとする。上記処理の詳しい手順は第１の実施形態において記述したためここでは省略する。
【００５１】
動き補償部１１１０は、動きベクトル探索結果と参照画像１１１３から予測画像１１１４を生成し、減算器１１１５へ出力する。減算器１１１５は、符号化対象画像１１１１と予測画像１１１４との差分を演算してブロック間差分データを生成し、周波数変換部１１０５へ出力する。
【００５２】
周波数変換部１１０５はブロック間差分データを周波数ドメインに変換し、量子化部１１０６へブロック係数データを送る。量子化部１１０６はブロック係数データを量子化し、可変長符号化部１１０７および逆量子化部１１０８へ送る。
【００５３】
可変長符号化部１１０７は量子化されたブロック係数データに可変長符号化を施し、符号化データ１１１２を出力する。逆量子化部１１０８は量子化されたブロック係数データに逆量子化を行い、再構成されたブロック係数データを逆周波数変換部１１０９へ送る。
【００５４】
逆周波数変換部１１０９は再構成されたブロック係数データを、加算器１１１６に出力する。加算器１１１６は、再構成されたブロック係数データと、動き補償部１１１０から出力された予測画像とに基づき再構成画像データを生成する。この再構成画像データは、次の符号化対象画像の参照画像となるものであり、フレームメモリＡ（１１０１）へ書き込まれる。
【００５５】
以上の処理を符号化対象画像１１１１を構成するブロックの数だけ行い、当該符号化対象画像の符号化が完了する。本実施形態では階層画像を格納するフレームメモリＢ（１１０３）のメモリ容量を、従来方式、例えば特許文献１の方式に比べて削減することができるため、本実施形態の装置を搭載する製品、例えばデジタルカメラなどのコストを削減することができる。
【００５６】
以上のように、本実施形態によれば、効率的に動きベクトル探索を行い、処理対象画像の圧縮符号化を実現することができる。
【００５７】
［その他の実施形態］
本発明の目的は、前述した機能を実現するコンピュータプログラムコードを記録した記憶媒体を、システムに供給し、そのシステムがプログラムコードを読み出し実行することによっても達成される。この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現し、そのプログラムコードを記憶した記憶媒体は本発明を構成する。また、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているオペレーティングシステム（ＯＳ）などが実際の処理の一部または全部を行い、その処理によって前述した機能が実現される場合も含まれる。
【００５８】
さらに、以下の形態で実現しても構わない。すなわち、記憶媒体から読み出されたプログラムコードを、コンピュータに挿入された機能拡張カードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込む。そして、そのプログラムコードの指示に基づき、その機能拡張カードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行って、前述した機能が実現される場合も含まれる。
【００５９】
本発明を上記記憶媒体に適用する場合、その記憶媒体には、先に説明したフローチャートに対応するプログラムコードが格納されることになる。
【図面の簡単な説明】
【００６０】
【図１】発明の第１の実施形態に対応する、動きベクトル探索方法の処理の一例示すフローチャートである。
【図２】画素中心位置がずれる階層画像の作成方法を説明するための図である。
【図３】発明の第１の実施形態に対応する、原画像と縮小画像の関係を説明するための図である。
【図４】発明の第１の実施形態に対応する、第１の探索点の設定例を示す図である。
【図５】発明の第１の実施形態に対応する、第３の探索点の設定例を示す図である。
【図６】発明の第１の実施形態に対応する、第５の探索点の設定例を示す図である。
【図７】発明の第１の実施形態に対応する、第７及び第８の探索点の設定例を示す図である。
【図８】発明の第１の実施形態に対応する、動きベクトル探索方式毎の演算回数の比較表である。
【図９】発明の第１の実施形態に対応する、動きベクトル探索方式毎の探索性能の比較グラフである。
【図１０】発明の第２の実施形態に対応する、ブロック単位の動き探索におけるブロック及び探索領域を説明するための図である。
【図１１】発明の第２の実施形態に対応する、符号化処理装置の構成の一例を示す図である。
【図１２】一般的な対数サーチ方式の説明図である。
【図１３】一般的な階層サーチ方式の説明図である。
【符号の説明】
【００６１】
１１００  符号化処理装置
１１０１  フレームメモリＡ
１１０２  縮小画像作成部
１１０３  フレームメモリＢ
１１０４  動きベクトル探索部
１１０５  周波数変換部
１１０６  量子化部
１１０７  可変長符号化部
１１０８  逆量子化部
１１０９  逆周波数変換部
１１１０  動き補償部
１１１１  符号化対象画像
１１１２  符号化データ
１１１３  参照画像
１１１４  予測画像
１１１５  減算器
１１１６  加算器
【図１】
2009033266.tif 000003
【図２】
2009033266.tif 000004
【図３】
2009033266.tif 000005
【図４】
2009033266.tif 000006
【図５】
2009033266.tif 000007
【図６】
2009033266.tif 000008
【図７】
2009033266.tif 000009
【図８】
2009033266.tif 000010
【図１０】
2009033266.tif 000011
【図１１】
2009033266.tif 000012
【図１２】
2009033266.tif 000013
【図１３】
2009033266.tif 000014
【図９】
2009033266.tif 000015