(57)【要約】【課題】  予測効率を向上させるための距離重み付け手段で探索順序を決める動きベクトル推定方法を提供する。【解決手段】第一画面に含まれる予定ブロックを参照して、該第一画面と時間的に近い第二画面に前記予定ブロックとのマッチングブロックを探索して、前記予定ブロックの動きベクトルを推定する距離重み付け手段で探索順序を決める動きベクトル推定方法において、前記第二画面に探索基点を選択して、該探索基点から距離重み付け手段で順次遠い位置に前記予定ブロックとのマッチングブロックを探索して、前記予定ブロックの動きベクトルを推定することを特徴とする距離重み付け手段で探索順序を決める動きベクトル推定方法である。動きベクトルが放射状に分配していることが多いため、本発明の距離重み付け手段で探索順序を決める方法は無駄な探索時間を削減することができる。【選択図】図７
2006254454.tif 000002
【特許請求の範囲】
【請求項１】
第一画面に含まれる予定ブロックを参照して、該第一画面と時間的に近い第二画面に前記予定ブロックとのマッチングブロックを探索して、前記予定ブロックの動きベクトルを推定する距離重み付け手段で探索順序を決める動きベクトル推定方法において、
前記第二画面に探索基点を選択して、該探索基点から距離重み付け手段で順次遠い位置に前記予定ブロックとのマッチングブロックを探索して、前記予定ブロックの動きベクトルを推定することを特徴とする距離重み付け手段で探索順序を決める動きベクトル推定方法。
【請求項２】
重み付け距離を下記の公式により算出し、
前記探索順序を最小の該重み付け距離の各ブロックから行うことを特徴とする請求項１記載の動きベクトル推定方法、
探索重み付け距離＝Ｈ（ｕ、ｖ）；
上記Ｈは所定の距離重み関数、ｕは上記探索基点との間の距離を表すＵ軸座標、ｖは上記探索基点との間の距離を表すＶ軸座標、上記Ｕ座標及びＶ座標は平面空間を構成させる基底関数。
【請求項３】
重み付け距離を下記の公式により算出し、
前記探索順序を最小の該重み付け距離の各ブロックから行うことを特徴とする請求項２記載の動きベクトル推定方法、
探索重み付け距離＝（絶対値（ｘ）＋絶対値（ｙ））；
ｘは上記探索基点との間の距離を表すＸ軸座標、ｙは上記探索基点との間の距離を表すＹ軸座標。
【請求項４】
重み付け距離を下記の公式により算出し、
前記探索順序を最小の該重み付け距離の各ブロックから行うことを特徴とする請求項２記載の動きベクトル推定方法、
探索重み付け距離＝最小値（開平（ｘ２＋ｙ２））；
ｘは上記探索基点との間の距離を表すＸ軸座標、ｙは上記探索基点との間の距離を表すＹ軸座標。
【請求項５】
重み付け距離を下記の公式により算出し、
前記探索順序を最小の該重み付け距離の各ブロックから行うことを特徴とする請求項２記載の動きベクトル推定方法、
探索重み付け距離＝F(u)＋G(v)＝F(abs(x))+G(abs(y))；
上記F(u)及びG(v)は、所定の距離重み関数表を参照して算出でき、ｘは上記探索基点との間の距離を表すＸ軸座標、ｙは上記探索基点との間の距離を表すＹ軸座標。
【請求項６】
前記公式のｕ及びｖ値の増加単位が整数であることを特徴とする請求項５記載の動きベクトル推定方法。
【請求項７】
前記公式のｕ及びｖ値の増加単位が非整数であることを特徴とする請求項５記載の動きベクトル推定方法。
【請求項８】
フルサーチ(Full Search)、ダイアモンドサーチ(Diamond Shape Search)、３段探索（Three Step Search）、４段探索(Four Step Search)、及び他の動き推定方法のいずれにも応用できることを特徴とする請求項１記載の動きベクトル推定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビデオ画像符号化に関する動き推定方法に関し、特に、距離重み付け(Distance Weighted)手段により順次動き推定を行う(Motion Estimation)方法に関する。
【０００２】
本願発明は、ここに引用して本明細書に組み込む出願日２００５年３月９日の台湾出願第０９４１０７１２５号における全開示内容に係り優先権主張するものである。
【背景技術】
【０００３】
図１において、MPEG画像のデータストリーム(Data Stream)は、一つ或いは複数のシーケンス（Sequence）から構成されている。上記各シーケンスには複数の画像グループ（Group of Pictures,  GOP）を含み、この画像グループは複数のフレーム(Frame)或いはピクチャ(Picture)から成る。フレームの属性により、Iフレーム（イントラ符号化画像）、Pフレーム（フレ−ム間順方向予測符号画像）及びBフレーム（双方向予測符号化画像）の三つのフレームタイプに分かれている。
【０００４】
上記三つのフレームは全て符号化することができる。画像圧縮処理を行うため、一般的にIフレームをカットインポイント（Cut-in Point)として、動きベクトル（Moving Vector）の推定に従って、Pフレーム及びBフレームの予測ができる。すなわち、Iフレーム或いはPフレームを参照フレームとして、Pフレームを予測することができ、Iフレーム及びPフレーム或いは二つのPフレームを参照フレームとして、Bフレームを予測することができる。そして、上記フレームを連続的に出力して、MPEG動画像をユーザに表示する。
【０００５】
MPEGの映像圧縮標準規格により、動きベクトルの推算に加え、動き補正(Motion Compensation)という技術もある。各ピクセル(Pixel)の輝度及びクロミナンスを記録して、フルサーチ(Full Search)の方式により二つの変化を記録して、直接動き補正を行う。しかし、この方式は膨大な計算機資源を浪費するという問題がある。したがって、現行方法は、各映像画面を複数のスライス(Slice)に分割して、このスライスを更に複数のマクロブロック(Micro Block、MB)に分割している。このマクロブロックは四つの輝度（Luminance）ブロック及び複数のクロミナンス（Chrominance）ブロックから成っており、最終的にこの各ブロック(Block)がMPEGデータの最小符号化ユニットとして定義される。
【０００６】
動きベクトルの推定及び動き補正技術によって、現画面が存在していた各ブロック及びその前の画面を基準に最適マッチングブロックを求め、計算された動きベクトル及び誤差データに基づいて、前の画面のブロックを調整して、現画面は得られる。計算された動きベクトルに基づいて、ブロックが適当な位置に転移される。誤差データは輝度及びクロミナンスの調整に使うことができる。重複のデータを記憶する必要がないため、記憶領域を削減でき、データ圧縮の目的も達成できる。
【０００７】
図２に示すように、前の画面から最適マッチングブロックを求める方法を、従来の３段探索の例で説明する。先ず定められた探索領域２１の中心を探索基点Ｔ０として、その近傍にある八点を探索点とする。この定められた探索領域２１を４×４画素範囲とした場合、それに最も類似度の高い点が探索領域２１の右下方探索点Ｔ１にあることを算出する。次に該探索点Ｔ１を中心として、探索領域２１を２×２画素範囲の探索領域２２へ小さくする。最後に、最も類似度の高い点が探索領域２２の右上方探索点Ｔ２にあることを求めて、それによって動きベクトルが定義される。
【０００８】
従来のダイアモンドサーチ(Diamond Shape Search; DSS)動き推定方法では、菱形(Rhombus)のような枠を探索領域とし、推定作業の動作は以下の様な手順で行う。
【０００９】
ステップ１：探索基点及び該探索基点を中心とする中空菱形の枠全ての九点から探索作業を行い、最も類似度の高い点が菱形の中心にあるとき、ステップ４を行い、最も類似度の高い点が菱形の枠にあるとき、ステップ２を行う。
【００１０】
ステップ２：該最も類似度の高い点を中心点として、もう一度菱形の枠を探索領域とする。
【００１１】
ステップ３：最も類似度の高い点が中心点にあるとき、ステップ４を行い、最も類似度の高い点が菱形の枠にあるとき、再度ステップ２を行う。
【００１２】
ステップ４：探索領域を小菱形（inner rhombus）（内側の五点）に小さくし、最も類似度の高い点が求められると、探索作業を止める。
【００１３】
図３Ａに示すように、ステップ１の説明によれば、最も類似度の高い点が中心１ａにあるので、ステップ４を行い、探索領域を小菱形（２、２ａ及び１ａを表示している点）に小さくして探索作業を行う。最後に、最も類似度の高い点２ａを得て、探索作業を止める。
【００１４】
図３Ｂに示すように、ステップ１の説明によれば、最も類似度の高い点が菱形の枠１ｂにあるので、ステップ２を行い、該最も類似度の高い点１ｂを中心点として、もう一度菱形の枠を探索領域とする。そしてステップ３を行い、最も類似度の高い点が菱形の枠２ｂにあるため、再度ステップ２を行い、もう一度菱形の枠を探索領域とする。最も類似度の高い点が中心２ｂにあるので、ステップ４を行い、探索領域を小菱形（４、４ｂ及び２ｂを表示している点）に小さくし、最後に、最も類似度の高い点４ｂを得て、探索作業を止める。
【００１５】
図４Ａ及び４Ｂに示すように、従来の動きベクトル判断方法は、主にラスタパターン探索法(Raster Pattern)及び渦巻きパターン探索法(Spiral Pattern)に基づいて探索を行う。ラスタパターン探索法は所定の探索領域で左から右に、そして上から下に、順次最も類似度の高い探索点を探す。渦巻きパターン探索法は所定の探索領域で、中心点から螺旋状に順次遠い探索点まで探索を行う。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
動きベクトルが放射状に分配される場合が多いことに鑑みると、本発明の距離重み付け手段により探索順序を決めることで、無駄な探索時間を削減することができる。
【００１７】
本発明の目的は、予測効率を向上させるために、距離重み付け手段で探索順序を決める動きベクトル推定方法を提供することにある。
【課題を解決するための手段】
【００１８】
上記目的を達成するために、本発明では第一画面に含まれる予定ブロックを参照して、該第一画面と時間的に近い第二画面に前記予定ブロックとのマッチングブロックを探索して、前記予定ブロックの動きベクトルを推定する距離重み付け手段で探索順序を決める動きベクトル推定方法において、
前記第二画面に探索基点を選択して、該探索基点から距離重み付け手段で順次遠い位置に前記予定ブロックとのマッチングブロックを探索して、前記予定ブロックの動きベクトルを推定することを特徴とする距離重み付け手段で探索順序を決める動きベクトル推定方法である。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の実施の形態について図面を参照しながら詳細に説明する。
【００２０】
図５に示すように、本発明に係る方法はMPEG画像データを圧縮するための画像エンコーダ1で行われるが、本発明は他の類似な画像圧縮を行うための画像処理システムにも応用できる。
【００２１】
前記画像エンコーダ１は前処理部(Preprocessor)１０、動き推算部(Motion Estimation)１１、動き補正部１２、動きベクトル符号化部(Motion Vector Encoding Unit)１３、テクスチャー符号化部(Texture Encoding Unit)１４、ビットストリーム合成部(Bit-Stream Composer)１５、及び、記憶部１６を備える。
【００２２】
入力画像１００が前記画像エンコーダ１に入力されるとき、定められた画面毎のマクロブロックデータが前記画像エンコーダ１の前処理部１０で定義され、記憶部１６に記憶される。そして、前記入力画像１００に含まれるマクロブロックデータは前記動き推算部１１で計算され，例えば、前及び後の画面とのマッチングブロックが計算されたら、全画面で各ブロックデータの動きベクトルデータ１０２が求められ、前記動き補正部１２に入力される。該動き補正部１２は前記動きベクトルを利用して、時間的に前或いは後の画面のマクロブロックデータを用いて、参照データ１０４を求める。そして、前記前処理部１０からの入力画像１００に含まれるマクロブロックデータ及び動き補正部１２からの参照データ１０４との差を求めて、誤差データ１０３が得られる。該誤差データ１０３は前記テクスチャー符号化部１４で計算され、圧縮のテクスチャー及び復号の参照データが求められる。
【００２３】
したがって、前記テクスチャー符号化部１４の離散コサイン変換部１４１は、各ブロックのピクセルデータの離散コサイン変換（DCT）係数を求める。そして、該ピクセルデータは周波数領域転換部１４２で時間領域から周波数領域に変換される。そして、量子化部１４３で量子化(Quantize)されて、多くの離散コサイン変換係数をゼロにして、更に高周波数成分を抽出する。そして、逆量子化部１４４で逆量子化されて、逆離散コサイン変換部１４５で逆離散コサイン変換係数を求め、そして前記動き推算部１１にフィードバック(Feedback)される。各動きベクトルは前記動きベクトル符号化部１３で符号化されたら、前記ビットストリーム合成部１５の可変長エンコーダ１５１に入力される。
【００２４】
一方、同一画面の各ブロック(Block)に含まれる余分な重複の情報は前記交流/直流予測部１４６（AC/DC Prediction）で抽出され、前記ジグザグスキャン部１４７でジグザグスキャンが行われ、量子化された離散コサイン変換係数を再配列する。すなわち、低周波係数を高周波係数の前に配列して、ジグザグスキャンされた離散コサイン変換係数はランレングス符号化(Run Length Encoding、RLE)される。最後に、ビットストリーム合成部１５のもう一つの可変長エンコーダ１５２で可変長符号化(variable length coding)され、その後ビットストリーム合成部１５で組み合われて、MPEG圧縮データを出力する。
【００２５】
図５及び６に示すように、本発明に係る距離重み付け手段で探索順序を決める動きベクトル推定方法の三つの好ましい実施形態は、画像エンコーダ１の動き推算部１１で行われる。しかし、本発明は他の実施形態にも応用でき、例えば従来のフルサーチ、ダイアモンドサーチ、３段探索、４段探索、及び他の動き推定方法のいずれにも応用できる。
【００２６】
本発明は第一画面５０１（現画面、Current Frame)に、含まれる予定ブロック５１から、これと時間的に近い第二画面５０２（参照画面、Reference Frame)に前記予定ブロック５１とのマッチングブロック５２を探索して、前記予定ブロック５１の動きベクトル５３を推定する。本発明は前記第二画面５０２にある方法で探索基点を選択して、該探索基点から距離重み付け手段で順次遠い位置のマッチングブロック５２を探索して、前記予定ブロック５１の動きベクトル５３を推定する。
【００２７】
本発明に係る距離重み付け手段で探索順序を決める動きベクトル推定方法において、公式１により重み付け距離の概念を説明する。
探索重み付け距離＝Ｈ（ｕ、ｖ）.....公式１
【００２８】
上記Ｈは所定の距離重み関数、ｕは上記探索基点との間の距離を表すＵ軸座標、ｖは上記探索基点との間の距離を表すＶ軸座標、上記Ｕ座標及びＶ座標は平面空間を構成させる基底関数(Bases)である。探索順序を最小の該重み付け距離の各ブロックから行う。
【００２９】
図７に示すように、本発明に係る距離重み付け手段で探索順序を決める動きベクトル推定方法の第１の好ましい実施形態において、公式２により重み付け距離を計算する。ｘは上記探索基点との間の距離を表すＸ軸座標、ｙは上記探索基点との間の距離を表すＹ軸座標である。探索順序を最小の該重み付け距離の各ブロックから行う。
探索重み付け距離＝（絶対値（ｘ）＋絶対値（ｙ））.....公式２
【００３０】
定められた探索領域２０１の中心点Ｍ１を探索基点（Original）として、計算された最小距離から探索を行う。例えば探索基点Ｍ１近傍にある４点から成る菱形領域から探索を行う。もし最も類似度の高いブロックを探せないなら、探索領域を前記菱形領域に基づいて、螺旋状で菱形の外縁にまだ探索していなかった領域に拡大する。同様の処理を繰り返して、最も類似度の高いブロックを求めるまで探索を行う。
【００３１】
図８に示すように、本発明に係る距離重み付け手段で探索順序を決める動きベクトル推定方法の第２の好ましい実施形態において、公式３により重み付け距離を計算する。ｘは上記探索基点との間の距離を表すＸ軸座標、ｙは上記探索基点との間の距離を表すＹ軸座標である。探索順序を最小の該重み付け距離の各ブロックから行う。
探索重み付け距離＝最小値（開平（ｘ２＋ｙ２））.....公式３
【００３２】
第１の好ましい実施形態の探索順序と同様に、第２の好ましい実施形態によって、定められた探索領域２０２の中心点Ｍ２を探索基点（Original）として、計算された最小距離から探索を行う。例えば探索基点Ｍ２自身（１）から探索を行い、順次探索基点Ｍ２近傍にある４点（２、３、４、５）の探索を行う。さらに探索基点Ｍ２からもっと遠い４点（６、７、８、９）の探索を行う。もし上記９点の中最も類似度の高いブロックを探せないなら、さらに探索領域を探索基点Ｍ２の外縁で、まだ探索していなかった複数探索点にまで拡大する。探索作業は依然として前記複数探索点の中の該探索基点Ｍ２と最も近い探索点から探索を行い、例えば先ず探索点（１０、１１、１２、１３）から行い、次に探索点（１４、１５、１６、１７、１８、１９、２０、２１）の順番で探索を行う。同様の処理を繰り返して、最も類似度高いブロックを求めるまで探索を行う。
【００３３】
本発明の第３の好ましい実施形態では、予めテーブルを参照して重み付け距離を転換し、公式４により重み付け距離を計算する。
探索重み付け距離＝F(u)＋G(v)＝F(abs(x))+G(abs(y)).....公式４
【００３４】
上記F(u)及びG(v)は、所定の距離重み関数表を参照しなから算出できる。ｘは上記探索基点との間の距離を表すＸ軸座標、ｙは上記探索基点との間の距離を表すＹ軸座標である。探索順序を最小の該重み付け距離の各ブロックから行う。表１及び表２により距離重み関数の例を示す、公式４にＦ（・）＝Ｇ（・）を設定する（つまり本実施例中、関数Ｇ及びＦは同じである）。
2006254454.tif 000003
【００３５】
上記表１及び表２において、上記ｕ、ｖの数は状況によって増やすことができる。したがって、上記ｕ及びｖと対応するF(u)の数も増える、これは上記表１及び表２に示すものに限定されるものではない。また、上記ｕ及びｖ値の増加単位は整数だけではなく、非整数でも上記距離重み関数表に入れることができる。例えば１／２、１／４及び１／８等が上記距離重み関数表に入れられ、これらは本発明の範囲から排除するものではない。
【００３６】
なお、本発明は前記実施の形態に限定されるものではなく、本発明の趣旨に基づいて種々変形させることが可能であり、それらを本発明の範囲から排除するものではない。
【００３７】
したがって、動きベクトルが探索基点から遠くまで放射状に分配される場合が多いことから、本発明の距離重み付け手段で探索順序を決める動きベクトル推定方法は、従来のラスタパターン探索法或いは渦巻きパターン探索法に比べ、より迅速にマッチングブロックを算出し、無駄な探索時間を削減することができ、予測効率も向上させることができる。
【図面の簡単な説明】
【００３８】
【図１】従来のMPEG画像データの構造を示す説明図である。
【図２】従来の３段探索方法を示す説明図である。
【図３】図３Ａ及び３Ｂは、従来のダイアモンドサーチ方法を示す説明図である。
【図４】図４Ａは従来のラスタパターン探索法を示す説明図であり、図４Ｂは従来の渦巻きパターン探索法を示す説明図である。
【図５】本発明に係るMPEG画像データを圧縮するための画像エンコーダを示すブロック図である。
【図６】本発明に係る距離重み付け手段で探索順序を決める動きベクトル推定方法に基づいて動きベクトルの推定方法を示す説明図である。
【図７】本発明に係る距離重み付け手段で探索順序を決める動きベクトル推定方法の第１の好ましい実施形態によって距離重み付け手段による探索順序を示す説明図である。
【図８】本発明に係る距離重み付け手段で探索順序を決める動きベクトル推定方法の第２の好ましい実施形態によって距離重み付け手段による探索順序を示す説明図である。
【符号の説明】
【００３９】
１  画像エンコーダ
１０  前処理部
１００  入力画像
１０１  現画像マクロブロックデータ
１０２  動きベクトルデータ
１０３  誤差データ
１０４  参照データ
１１  動き推算部
１２  動き補正部
１３  動きベクトル符号化部
１４  テクスチャー符号化部
１４１  離散コサイン変換部
１４２  周波数領域転換部
１４３  量子化部
１４４  逆量子化部
１４５  逆離散コサイン変換部
１４６  交流/直流予測部
１４７  ジグザグスキャン部
１５  ビットストリーム合成部
１５１，１５２  可変長エンコーダ
１６  記憶部
２０１，２０２  探索領域
Ｍ１, Ｍ２  探索基点
５０１  第一画面
５０２  第二画面
５１  予定ブロック
５２  マッチングブロック
５３  動きベクトル
【図１】
2006254454.tif 000004
【図２】
2006254454.tif 000005
【図３】
2006254454.tif 000006
【図４】
2006254454.tif 000007
【図５】
2006254454.tif 000008
【図６】
2006254454.tif 000009
【図７】
2006254454.tif 000010
【図８】
2006254454.tif 000011