(57)【特許請求の範囲】
【請求項１】
ビデオ圧縮のマッチングピクセルサブサンプリング動き推定方法であって、
第一フレームを複数のマクロブロックに分割する段階と、
第二フレームの候補マクロブロックペアに対して現マクロブロックペアのブロックマッチングを行う段階とを含み、
前記ブロックマッチングは、
サブサンプリングパターンに従って現マクロブロックペアと候補マクロブロックペアをサブサンプリングすることと、
現マクロブロックペアと候補マクロブロックペア間の誤差測定を計算することによって行われ、
前記サブサンプリングパターンは複数の繰り返しユニットから構成され、各繰り返しユニットは第一パターンユニットと第二パターンユニットを含む、マッチングピクセルサブサンプリング動き推定方法。
【請求項２】
前記パターンユニットのサイズは４×４ピクセルで、前記繰り返しユニットのサイズは４×８ピクセルである、請求項１に記載のマッチングピクセルサブサンプリング動き推定方法。
【請求項３】
前記第一パターンユニットはフォークィーンパターンの繰り返しユニットである、請求項２に記載のマッチングピクセルサブサンプリング動き推定方法。
【請求項４】
前記第二パターンユニットは前記第一パターンユニットから得られる、請求項１に記載のマッチングピクセルサブサンプリング動き推定方法。
【請求項５】
前記第二パターンユニットは前記第一パターンユニットを所定角度回転して得たものである、請求項４に記載のマッチングピクセルサブサンプリング動き推定方法。
【請求項６】
前記第二パターンユニットは前記第一パターンユニットを水平軸または垂直軸に沿ってミラーリングして得たものである、請求項４に記載のマッチングピクセルサブサンプリング動き推定方法。
【請求項７】
前記第二パターンユニットは前記第一パターンユニットを左または右へ所定列移動して得たものである、請求項４に記載のマッチングピクセルサブサンプリング動き推定方法。
【請求項８】
前記第二パターンユニットは前記第一パターンユニットを上または下へ所定行移動して得たものである、請求項４に記載のマッチングピクセルサブサンプリング動き推定方法。
【請求項９】
前記方法は更に、
複数の誤差測定を計算するために前記第二フレームの複数の候補マクロブロックペアに対して現マクロブロックペアのブロックマッチングを行う段階を繰り返す段階と、
前記複数の誤差測定のうち最小誤差測定に従って動きベクトルを定める段階とを含む、請求項１に記載のマッチングピクセルサブサンプリング動き推定方法。
【請求項１０】
前記誤差測定は、絶対差の和（ＳＡＤ（ｓｕｍ  ｏｆ  ａｂｓｏｌｕｔｅ  ｄｉｆｆｅｒｅｎｃｅｓ））である、請求項１に記載のマッチングピクセルサブサンプリング動き推定方法。
【請求項１１】
前記繰り返しユニットの第一パターンユニットと第二パターンユニットは水平または垂直方向に相互隣接する、請求項１に記載のマッチングピクセルサブサンプリング動き推定方法。
【請求項１２】
前記第一パターンユニットのサイズはＮ×Ｎピクセルである、請求項１に記載のマッチングピクセルサブサンプリング動き推定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は動き推定（ｍｏｔｉｏｎ  ｅｓｔｉｍａｔｉｏｎ、ＭＥ）に関し、特にビデオ圧縮においてマッチングピクセルサブサンプリング技術を実施する動き推定に関する。
【背景技術】
【０００２】
動き推定（ＭＥ）はビデオ圧縮においてビデオフレーム間の時間的冗長を減少させるために共通に利用されている技術である。同様に繰り返す類似したビデオセグメントを動きベクトル(motion  vector)に置き換えることにより、ビデオファイルを符号化するためのメモリ要求は従って減少する。これは多くの場合では、ビデオの品質を低下させたり犠牲にしたりすることなく、大きいビデオファイルのサイズを縮減できる。
【０００３】
図１は先行技術によるフレーム動き推定（フレームＭＥ）を表す説明図である。前述のように、動き推定の目的はビデオフレーム間の時間的冗長（ｔｅｍｐｏｒａｌ  ｒｅｄｕｎｄａｎｃｙ）の減少にあり、当該ビデオフレームは現フレーム１２０と基準フレーム１１０を含む。現フレーム１２０は、基準フレーム１１０内のさまざまな候補ＭＢと比較のためのビデオセグメントとして利用されるために複数のマクロブロック（ＭＢ）に分割される。ＭＢのサイズは計算効率と計算の正確性との望ましいかね合いにより変わりうるが、多くのアルゴリズムでは通常約１６×１６ピクセルである。一旦分割されると、現フレーム１２０内の各ＭＢは所定の誤差測定（ｅｒｒｏｒ  ｍｅａｓｕｒｅ）により基準フレーム１１０内のＭＢと比較され最良マッチング候補ＭＢが定められる。その後、フレーム間のマッチングＭＢを示すベクトル（動きベクトルとも称する）が示され、圧縮アルゴリズムにおいて現フレーム１２０の現ＭＢを置き換えるために使われる。図１に示す方法を利用すれば、現フレーム１２０の野球マクロブロック１２５は基準フレーム１１０の野球マクロブロック１１５とほどよく適合させることができる。動きベクトル１３０は基準フレーム１１０から現フレーム１２０へのマッチングマクロブロック間の変位を示す。
【０００４】
動きベクトルは実際のマクロブロックデータより保存に要するメモリが少ないので、圧縮アルゴリズムに動き推定を利用すれば、メモリ消費量は大幅に減少できる。復元のとき、動きベクトルで示される基準フレーム内のマクロブロックは現フレームの予測に用いられる。このような技術は動き補償予測または動き補償として知られている。動き補償の場合、動きベクトルで示される基準ブロック内のマッチングマクロブロックは復元後のフレームに複製される。図１に示す例を引き続き参照する。動き補償では、保存されるのを省かれた野球マクロブロック１２５は、動きベクトル１３０に基づいて現フレーム１２０において基準フレーム１１０の野球１１５に置き換えられる。
【０００５】
動き推定法を利用した圧縮ビデオから解凍されたビデオの品質は、動きベクトル探索用のアルゴリズムによって変わりうる。不正確な動きベクトルはずれた予測につながり、ビデオの品質を低下させうる。誤差測定は動き推定のブロックマッチング時、マクロブロック間の類似度を定量化するために用いられる。絶対差の和（ＳＡＤ：ｓｕｍ  ｏｆ  ａｂｓｏｌｕｔｅ  ｄｉｆｆｅｒｅｎｃｅｓ）と２乗誤差の和（ＳＳＥ：ｓｕｍ  ｏｆ  ｓｑｕａｒｅｄ  ｅｒｒｏｒ）は、ブロックマッチングに適用される常用の誤差測定の例である。
【０００６】
前記フレーム動き推定技術は通常、ビデオ画像の全フレームが連続的に示される順次走査方式のビデオソースに適用されるが、動き推定動作はインターレース方式のビデオにも適用できる。図２は先行技術によるインターレースビデオフレーム２００の構成を表す説明図である。インターレース方式のビデオでは、インターレースフレーム２００は偶数フィールド２１０（偶数の水平線から構成される）と奇数フィールド２２０（奇数の水平線を含む）を含む。インターレース方式のビデオの動き推定を行うときは、マクロブロックの全体を比較するのでなく、現フレーム内のマクロブロックの１フィールドと基準フレーム内のマクロブロックの１フィールドを比較する。これはフィールド動き推定（フィールドＭＥ）としても知られている。フレームＭＥとフィールドＭＥは両方ともインターレース方式のビデオに適用できるが、その結果は異なる。ビデオが静的であってビデオシーケンスの動きが限られた場合では、フレームＭＥはより良い結果を生成できる。しかし、ビデオが動的であってビデオシーケンスの動きが大きい場合では、フィールドＭＥがより良いマッチング結果を生成できる。フィールドＭＥとインターレース方式のビデオは当業者に周知のため、ここで説明を省略する。
【０００７】
マッチングマクロブロックを定めるときには、マッチングピクセルをサンプリングして計算の複雑性を減少させることができる。特性値（ＳＡＤ値またはＳＳＥ）を計算するために現ＭＢと候補ＭＢの一定のピクセルを選び、候補ＭＢ間の特性値を比較する。図３は３２×１６ピクセルのマクロブロックペアを２組マッチングしてＭＥを行う例を示し、そこでフォークィーン（ｆｏｕｒ−ｑｕｅｅｎ）サブサンプリングパターン３１０が用いられている。図３は１６×３２のマクロブロックペアをサンプリングする例を示す。この場合、現ＭＢと候補ＭＢはいずれも１６×３２ピクセルである。複数の４×４のブロックから４ピクセルずつ選び出すフォークィーンパターン３４０は繰り返して利用され、１６×３２のサブサンプリングパターンを形成する。サブサンプリングパターン３１０は現ＭＢペアと候補ＭＢペアの両方にも適用される。選出されたピクセルのみ誤差測定の計算に用いられる。
【０００８】
フレームＭＥのフォークィーンサブサンプリングパターンは均等に分散しているように見えるが、フィールドＭＥに適用すると、サブサンプリングパターン３２０と３３０は不均一となる。フィールドＭＥの均一なサンプル分布の欠如は、最適でないマッチング結果をもたらす可能性があり、圧縮ビデオの品質が低下しうる。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明の目的のひとつは、前記問題を解決するために、マッチングピクセルサブサンプリングを用いる動き推定を提供することにある。サブサンプリングパターンは順次走査方式とインターレース方式のビデオソースの両方にも適用され、フレームＭＥとフィールドＭＥの両方により均一なサンプル分布をもたらしうる。
【課題を解決するための手段】
【００１０】
本発明の実施例では、ビデオ圧縮のマッチングピクセルサブサンプリングを用いた動き推定方法を開示している。本方法ではまず第一フレームを複数のマクロブロックに分割してから、第二フレームの候補マクロブロックペアに対して現マクロブロックペアのブロックマッチングを行う。現マクロブロックペアと候補マクロブロックペアとが、サブサンプリングパターンに基づいてサンプリングされ、現マクロブロックペアと候補マクロブロックペア間の誤差測定の計算に備える。前記サブサンプリングパターンは複数の繰り返しユニットから構成され、各繰り返しユニットは第一パターンユニットと第二パターンユニットを含む。
【発明を実施するための最良の形態】
【００１１】
かかる方法の特徴を詳述するために、具体的な実施例を挙げ、図を参照にして以下に説明する。
【００１２】
先行技術の箇所で説明されたように、フレームＭＥとフィールドＭＥは、ビデオの相対並進運動（ｒｅｌａｔｉｖｅ  ｔｒａｎｓｌａｔｉｏｎａｌ  ｍｏｔｉｏｎ）に基づいて好ましいほうを選べば、両方ともインターレース方式のビデオに適用できる。しかし、インターレース方式のビデオを処理する場合では、フレームＭＥかフィールドＭＥでビデオを符号化するかは決めにくい。この場合、フレームＭＥとフィールドＭＥの両方を実行する必要があり、より良い計算結果を生み出せるほう（通常はＳＡＤ計算、または現フレームのマクロブロックと基準フレームのマクロブロックの相違性を定量化する他の誤差測定計算法で定められる）が選ばれる。したがって、レート歪み（Ｒ−Ｄ）性能を強化するために、フレームＭＥとフィールドＭＥのサブサンプリングパターンは誤差測定計算時に均一なサブサンプル分布を持たなければならない。計算の複雑性を減らすために、サブサンプリングパターンに用いられるサンプル点は通常、フレームＭＥとフィールドＭＥの両方にも再利用できる。したがって、本発明によるサブサンプリングパターンは、フレームＭＥとフィールドＭＥの両方でも良好な符号化結果を生じさせる。このサブサンプリングパターンは簡易なアルゴリズムで生成できる。
【００１３】
本発明によるサブサンプリングパターンは複数の繰り返しユニットを含み、各繰り返しユニットは異なるパターンユニットを少なくとも２つ含む。２つのパターンユニットは完全に異なるパターンか、またはあるパターンユニットと、このパターンユニットの反転、反射、左右移動、上下移動、または回転により得たものを含む。言い換えれば、第二のパターンユニットは第一のパターンユニットに対して反転、反射、移動、回転、または上記変換の如何なる組み合わせによっても取得できる。ある実施例では、パターンユニットのサイズはＮ×Ｎピクセルであり、繰り返しユニットのサイズはＮ×２Ｎピクセルである。異なるパターンユニットに基づくサブサンプリングパターンを提供すれば、インターレースビデオについてフレームＭＥとフィールドＭＥの両方のために均一で全般的なサンプル分布が得られる。これについて以下に詳述する。
【００１４】
図４は本発明のいくつかの実施例によるサブサンプリングパターンの構成を表す説明図である。現マクロブロックペアと候補マクロブロックペアのピクセルをサンプリングするためのサブサンプリングパターンは、複数の繰り返しユニットから構成される。例えば、１６×３２ピクセルのマクロブロックペアは図３に示すフォークィーンパターン３１０によりサンプリングされ、フォークィーンパターン３１０の繰り返しユニットは４×４ピクセルのパターンユニットである。本発明の実施例では、２またはそれ以上の４×４ピクセルのパターンユニットを組み合わせて、サブサンプリングパターンの繰り返しユニットを形成する。図４に示す例では、４×４ピクセルのパターンユニット４００は第一パターンユニットとして選ばれ、４１０、４２０または４３０から選ばれた第二パターンユニットと組み合わせられ４×８ピクセルの繰り返しユニットを形成する。第二パターンユニットは第一パターンユニットと異なるものでなければならないが、第一パターンユニットに由来するものであり得る。例えば、パターンユニット４１０は第一パターンユニット４００を左回りに９０度回転して得たもので、パターンユニット４２０は第一パターンユニット４００を垂直軸に沿ってミラーリングして得たもので、パターンユニット４３０は第一パターンユニット４００を水平軸に沿ってミラーリングして得たものである。第二パターンユニットが選ばれると、選ばれた２つのパターンユニットはサブサンプリングパターンの４×８ピクセルの繰り返しユニットを形成する。サブサンプリングパターンは、１６個の４×８ピクセル繰り返しユニットから構成され、動き推定の実行時に第一フレームの現マクロブロックペアと第二フレームの候補マクロブロックペアを適正にサンプリングするために用いられる。
【００１５】
図５は前掲例に引き続き、２つのパターンユニットを組み合わせて、サブサンプリングパターンの繰り返しユニットを形成する応用例を示す。本例では、第一４×４ピクセルパターンユニット５１０はサブサンプリングパターン５００の左上隅にある。本例による第二４×４ピクセルパターンユニット５２０は、第一パターンユニット５１０の垂直軸（または水平軸）に沿った反射である。サブサンプリングパターン５００は第一パターンユニットと第二パターンユニットを繰り返して構成したものである。全サブサンプリングパターン５００を利用すると、フレームＭＥの実行時にマクロブロックペアから均一な分布のサンプル点が抽出される。フィールドＭＥを実行するとき、上フィールドのサブサンプリングパターン５３０と下フィールドのサブサンプリングパターン５４０もマクロブロックペアから均一な分布のサンプル点を抽出する。図３に示す先行技術フィールドＭＥと比べて、交互配列される垂直線には未サンプリングの領域が存在しない。したがって、結果として生成したサブサンプリングパターン５００は、フレームＭＥとフィールドＭＥの両方にも適用できるような、より均一なサンプル分布を提供することができる。
【００１６】
注意すべきは、前掲例ではフォークィーンサブサンプリングパターンのパターンユニットと、フォークィーンサブサンプリングパターンのパターンユニットの複数の変形例を利用するが、本発明の代替実施例として、異なる複数のサブサンプリングパターン、例えば全サンプリングパターン、クォーターパターン（ｑｕａｒｔｅｒ  ｐａｔｔｅｒｎ）、またはエイトクィーンパターン（ｅｉｇｈｔ  ｑｕｅｅｎ  ｐａｔｔｅｒｎ）などのパターンユニットを利用することができる。現マクロブロックペアと候補マクロブロックペアをサンプリングするためのサブサンプリングパターンは、相違するパターンユニットを少なくとも２つ備え、種々の実施例で特定の圧縮またはサンプリング要求に応じて各種の変化を構成することができる。他の実施例として、サブサンプリングパターンの繰り返しユニットには、相違するパターンユニットが立ち並んでいる。例えば、第二パターンユニットを第一パターンユニットの右側に並べて８×４ピクセルの繰り返しユニットを形成することができる。
【００１７】
また、本発明によるサブサンプリングパターンのデザインはインターレース方式と順次走査方式のビデオソースの両方にも適用できる。順次走査方式のビデオのブロックマッチングユニットはマクロブロックでマクロブロックペアではないので、順次走査方式のビデオソース用のサブサンプリングパターンは１６×１６ピクセルであってもよい。
【００１８】
前述のように、サブサンプリングパターンは、誤差測定の計算のための現ＭＢペアと候補ＭＢペアの特定ピクセルを選ぶために利用される。基準フレームのサーチ領域内、複数の候補ＭＢペア間の誤差測定が相互比較され、複数の誤差測定のうち最小誤差測定に応じてマッチングＭＢペアの位置を示す動きベクトルが定められる。所用の誤差測定は実施例によって異なりうるが、絶対差の和（ＳＡＤ）を含むことができる。
【００１９】
図６に示すフローチャートではビデオ圧縮の動き推定の実施例を説明する。同一の結果が得られる限り、動き推定のステップは後掲の順序どおりに連続して実行する必要がなく、その間に他ステップが介在してもかまわない。本発明による方法は以下のステップを含む。
【００２０】
ステップ６１０：第一フレームを複数のマクロブロックに分割する。
ステップ６２０：第二フレームの候補マクロブロック（ＭＢ）ペアに対して現マクロブロックペアのブロックマッチングを行う。
ステップ６３０：サブサンプリングパターンに従って現ＭＢペアと候補ＭＢペアをサンプリングする。このサブサンプリングパターンは複数の繰り返しユニットから構成され、各繰り返しユニットは第一パターンユニットと第二パターンユニットを含む。
ステップ６４０：現ＭＢペアと候補ＭＢペア間の誤差測定を計算する。
【００２１】
図６に示す動き推定法の他実施例では、サブサンプリングパターンの形成に第三のパターンユニットを使用することができる。これは、サンプリング要求に応じて多様なサンプル分布を提供することに役立つ。
【００２２】
相違するパターンユニットからなるサブサンプリングパターンを提供することによって、インターレース方式のビデオでプロセスするフレームＭＥとフィールドＭＥの両方にも適用できるような均一な全般的サンプル分布が得られる。好ましい実施例では、サブサンプリングパターンは、第一パターンユニットから第二パターンユニットを取得することで容易に作り出され、かつ第一パターンユニットとして、マッチングピクセルサブサンプリングによく利用される従来のパターン（例えばフォークィーンパターン）のパターンユニットを利用してもよい。これは、ビデオ圧縮においてより効率的で効果的なサブサンプリングを用いた動き推定手順を可能にする。
【００２３】
以上は本発明に好ましい実施例であって、本発明の実施の範囲を限定するものではない。よって、当業者のなし得る修正、もしくは変更であって、本発明の精神の下においてなされ、本発明に対して均等の効果を有するものは、いずれも本発明の特許請求の範囲に属するものとする。
【図面の簡単な説明】
【００２４】
【図１】先行技術による動き推定（ＭＥ）を表す説明図である。
【図２】先行技術によるインターレースビデオフレームの構成を表す説明図である。
【図３】動き推定にフォークィーンサンプリングパターンを適用した場合のフレームサブサンプリングパターンとインターレースフィールドサンプリングパターンを表す説明図である。
【図４】本発明の実施例により取得したサブサンプリングパターンを表す説明図である。
【図５】本発明の実施例によるサブサンプリングパターンに由来する実施例を表す説明図である。
【図６】本発明による動き推定方法についての実施例を説明するプロセスフローチャートである。
【図１】
0004792072.tif 000002
【図２】
0004792072.tif 000003
【図３】
0004792072.tif 000004
【図４】
0004792072.tif 000005
【図５】
0004792072.tif 000006
【図６】
0004792072.tif 000007